The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers

Preetum Nakkiran, Behnam Neyshabur, Hanie Sedghi

Introduction

The Deep Bootstrap Framework proposes a paradigm shift in how we understand generalization in deep learning. It suggests that generalization is essentially a byproduct of fast online optimization. By demonstrating that the "Bootstrap Error"—the performance gap between training on finite data versus an infinite stream of fresh samples—is surprisingly small in realistic settings, the authors show that a model’s ability to generalize is largely determined by how quickly it learns from the true underlying distribution.

The Problem with Classical Generalization

Classical generalization theory faces a crisis when applied to deep learning. Traditional metrics like VC-dimension or Rademacher complexity attempt to bound the "generalization gap" (the difference between test and train error). However, modern neural networks often interpolate: they reach near-zero training error yet still perform excellently on unseen data. In this regime, the generalization gap simply equals the test error, rendering the classical decomposition ($Test = Train + Gap$) uninformative.

Furthermore, classical theory struggles to explain why certain architectures (like Convolutional Neural Networks) generalize better than others (like Multi-Layer Perceptrons) when both are perfectly capable of fitting the training set. This paper seeks a new framework that explains generalization through the lens of optimization rather than mere capacity control.

The Deep Bootstrap Framework

The authors introduce a novel decomposition of test error by comparing two hypothetical scenarios:

  1. The Real World (Offline Learning): An optimizer takes $t$ steps on a finite dataset of $n$ samples, re-using samples across multiple epochs.
  2. The Ideal World (Online Learning): An optimizer takes $t$ steps, but receives a fresh, i.i.d. sample from the true population distribution at every single step.

They define the Bootstrap Error as the difference in test performance between these two worlds. Their central claim is that for realistic deep learning tasks, this error is remarkably small.

Test soft-error over SGD iterations for different architectures in the Real vs. Ideal worlds.

To make this comparison rigorous, the authors use "soft-error" (the softmax probability assigned to incorrect labels) rather than "hard-error" (0/1 classification). They also define a "stopping time" $T_0$, which marks when the Real World model has essentially converged (e.g., reached 1% training error).

Simulating the Ideal World

To simulate the "Ideal World," which requires millions of fresh samples, the authors utilized:

  • CIFAR-5m: A novel dataset introduced in this paper consisting of 6 million synthetic images generated by a Denoising Diffusion Probabilistic Model trained on CIFAR-10. This allows them to treat the generative model as the "true distribution" and sample fresh data for every SGD step.
  • ImageNet-DogBird: A binary classification task derived from ImageNet-2012 by collapsing classes into "hunting dogs" and "birds" (155K total images), providing a more complex, real-world image distribution to test the framework.

Key Insights and Results

Optimization is Generalization

The core insight is that the reason a CNN generalizes better than an MLP isn't necessarily due to better "regularization," but because it is a faster online learner. It reaches a lower population loss more quickly when given infinite data. The fact that we reuse data in the Real World (multiple epochs) doesn't fundamentally change the optimization path compared to the Ideal World, at least until the model starts to converge on the training set.

Empirical Consistency Across Architectures

Across various architectures (ResNets, MLPs, Vision Transformers), the test error in the Real World closely tracks the test error in the Ideal World.

Scatter plots demonstrating the strong correlation between Real and Ideal world soft-errors across various architectures.

On CIFAR-5m, the performance ranking of architectures in the Real World (CNN > ViT > MLP) is identical to their ranking in the Ideal World. The CNN's superior generalization is effectively "explained" by its faster optimization on the population loss.

Unifying Regimes and Redefining "Good" Models

This framework bridges the gap between under-parameterized and over-parameterized regimes. In both cases, the goal is the same: optimize the population loss as quickly as possible. A "good" model is redefined as one that:

  1. Optimizes quickly in the Ideal World.
  2. Doesn't "notice" the finite nature of the Real World too early (keeping Bootstrap Error low).

Additionally, the framework sheds light on common practices:

  • Data Augmentation: Helps primarily by extending the "stopping time"—it prevents the model from fitting the finite training set too quickly, keeping the Real World optimization path aligned with the Ideal World for longer.
  • Pretraining: Pretrained models generalize better because they start the optimization process at a point where the population loss is already low, effectively "skipping" the early, high-error phase of online learning.

Limitations and Future Work

While powerful, the framework has limitations. The authors acknowledge that the Bootstrap Error is not always small; it can be large with extremely small sample sizes, in specific linear regression distributions, or in "double descent" scenarios. Furthermore, while the empirical evidence is strong, there is currently no mathematical proof for why the Bootstrap Error is small for deep neural networks.

Future research should focus on understanding the "online learning" speed of different architectures and optimizers, as this appears to be the primary driver of offline generalization.

Summary updated

Abstract

We propose a new framework for reasoning about generalization in deep learning. The core idea is to couple the Real World, where optimizers take stochastic gradient steps on the empirical loss, to an Ideal World, where optimizers take steps on the population loss. This leads to an alternate decomposition of test error into: (1) the Ideal World test error plus (2) the gap between the two worlds. If the gap (2) is universally small, this reduces the problem of generalization in offline learning to the problem of optimization in online learning. We then give empirical evidence that this gap between worlds can be small in realistic deep learning settings, in particular supervised image classification. For example, CNNs generalize better than MLPs on image distributions in the Real World, but this is "because" they optimize faster on the population loss in the Ideal World. This suggests our framework is a useful tool for understanding generalization in deep learning, and lays the foundation for future research in this direction.
BibTeX
@inproceedings{nakkiran2021deep,
  author = {Preetum Nakkiran and Behnam Neyshabur and Hanie Sedghi},
  title = {{The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=guetrIHLFGI},
}
Figure