The Deep Bootstrap: Good Online Learners are Good Offline Generalizers

Preetum Nakkiran, Behnam Neyshabur, Hanie Sedghi

Introduction: The Generalization Mystery

The central goal of statistical learning theory is to explain generalization: why does a model trained on a specific dataset perform well on unseen data? Classically, theorists decompose test error into two parts: Train Error + Generalization Gap.

However, modern deep neural networks often achieve near 0% training error, perfectly interpolating the data. In this regime, the classical equation becomes a tautology: "Test Error = 0 + Test Error," providing no actual insight. Furthermore, traditional bounds like VC-dimension or uniform convergence are notoriously vacuous for massive, overparameterized networks. This paper introduces the "Deep Bootstrap" framework, which reframes generalization by bypassing training error entirely.

The Deep Bootstrap Framework

Instead of comparing training error to test error, the authors propose comparing two identical training setups:

  1. The Real World (Offline Learning): A model is trained on a finite dataset of size $n$ for $t$ steps. Because the dataset is finite, the optimizer (e.g., SGD) reuses samples across multiple epochs.
  2. The Ideal World (Online Learning): An identical model is trained for $t$ steps, but it sees a fresh, unseen batch of samples at every single step. It never reuses data, meaning it directly optimizes the true "population loss."

The Bootstrap Error is defined as the difference in test performance between the Real World and Ideal World models at step $t$. To ensure proper scaling, the authors measure "soft-error" (1 minus the softmax probability of the correct label) rather than hard classification error.

Methodology: Simulating the Infinite

To simulate the "Ideal World," the authors required massive datasets to ensure models never saw the same image twice. They introduced CIFAR-5m, a synthetic dataset of 6 million CIFAR-10-like images generated using a state-of-the-art Denoising Diffusion model and labeled with a Big-Transfer (BiT) model. They also utilized ImageNet-DogBird, a binary classification subset of ImageNet large enough to approximate the Ideal World via heavy data augmentation.

Results: Generalization is Optimization

The core finding of the paper is that the Bootstrap Gap is surprisingly small. In realistic deep learning settings, the test performance of the Real World model closely tracks the Ideal World model until the Real World model converges (reaches <1% training error).

Test soft-error of Real World (solid) vs. Ideal World (dashed) models across different architectures. The models track each other closely throughout training.

As shown in the figure above, architectures like ResNet18, ViT-B/4, and MLPs all exhibit this tracking behavior. This suggests that the mystery of offline generalization can be reduced to a question of online optimization: a model generalizes well on finite data simply because it is the type of architecture that optimizes quickly on infinite data.

This relationship holds across a vast array of configurations. The authors tested standard architectures (VGG, DenseNet, AlexNet) and 500 random DARTS architectures, finding that the test soft-error of Real and Ideal world models consistently remained within 1% to 3% of each other.

Correlation between Real and Ideal World soft-errors across various standard architectures (left) and 500 random DARTS architectures (right).

Key Insights

  • Unifying Regimes: Engineers use the same architectures (ResNets, Transformers) whether they have 50,000 images or 1 billion. This framework explains why: architectures that optimize efficiently in the infinite-data regime naturally generalize well in the finite-data regime.
  • Implicit Bias: Rather than studying why SGD is biased toward "good" minima on empirical landscapes, this framework suggests we should study why SGD optimizes quickly on the true population landscape.
  • Data Augmentation: In this view, data augmentation doesn't drastically change Ideal World performance. Instead, it delays the "stopping time" in the Real World, preventing the model from converging too quickly and allowing it to track the Ideal World's continuous improvement for longer.
  • Pretraining: Pretrained weights improve Real World generalization by mirroring a massive speedup in Ideal World optimization.

Limitations and Future Work

The bootstrap error is not universally small. It can widen if the sample size is too small, if data augmentation is removed, or in certain toy settings like misspecified linear regression. It also struggles with non-monotonic error behaviors like epoch double-descent. Future work is needed to formally characterize the conditions under which the bootstrap error remains small based on data distribution, architecture, and sample size.

Summary updated

BibTeX
@inproceedings{nakkiran2021deep,
  author = {Preetum Nakkiran and Behnam Neyshabur and Hanie Sedghi},
  title = {{The Deep Bootstrap: Good Online Learners are Good Offline Generalizers}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=guetrIHLFGI},
}
Figure