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

Preetum Nakkiran, Behnam Neyshabur, Hanie Sedghi

TL;DR

This paper introduces the "Deep Bootstrap" framework, which reframes generalization in deep learning by comparing a model trained on real data (Real World) to one trained on infinite data (Ideal World). They propose that if the difference between these two worlds (the "bootstrap error") is small, then good online optimization performance directly translates to good offline generalization, offering a new lens to understand why certain architectures generalize well.

What Problem Does This Paper Address?

Understanding why deep neural networks generalize well, especially in the over-parameterized regime where they can perfectly fit the training data, remains a significant challenge. Traditional generalization theories often become vacuous for modern networks. The authors aim to provide a new framework that decouples the problem of generalization into two more tractable parts: how well a model optimizes on the population loss (Ideal World) and how closely its finite-data performance matches this ideal (bootstrap error). This approach seeks to explain phenomena like why certain architectures (e.g., CNNs) outperform others (e.g., MLPs) even when both can achieve near-zero training error.

Methods

The core of the paper is the "Deep Bootstrap" framework. It decomposes the test error of a model $f_t$ (trained for $t$ steps on $n$ samples) into:

$ \text{TestError}(f_t) = \text{TestError}(f_{t}^{\text{iid}}) + [\text{TestError}(f_t) - \text{TestError}(f_{t}^{\text{iid}})] $

where:

  • $f_t^{\text{iid}}$ is a model trained for $t$ steps on infinite samples drawn from the true data distribution (the "Ideal World").
  • $f_t$ is the model trained for $t$ steps on a finite dataset of $n$ samples (the "Real World").
  • The term $[\text{TestError}(f_t) - \text{TestError}(f_{t}^{\text{iid}})]$ is termed the "bootstrap error."

The authors hypothesize that in realistic deep learning settings, this bootstrap error is small. This implies that generalization is primarily determined by how quickly a model can optimize on the population loss (the "online learning" aspect in the Ideal World). They use "soft-error" (1 - softmax probability of the correct label) as their primary metric, arguing it has better theoretical properties for convergence.

Datasets

  • CIFAR-5m: A newly constructed dataset of 6 million synthetic CIFAR-10-like images generated using a Denoising Diffusion generative model and labeled by a Big-Transfer model. This dataset was created to provide a larger-than-CIFAR-10 distribution for simulating the "Ideal World" scenario.
  • ImageNet-DogBird: A binary classification task derived from ImageNet by collapsing classes into "hunting dog" and "bird" categories. This was used to test the framework on a more complex, real-world image dataset.
  • CIFAR-10: Used for comparison and in some fine-tuning experiments.

Key Insights and Ideas

  • Generalization as Online Optimization: The framework suggests that good offline generalization is largely a consequence of good online optimization performance on the population loss. If the bootstrap error is small, then models that learn quickly in the "Ideal World" will also generalize well in the "Real World."
  • CNNs vs. MLPs Explained: The framework provides an explanation for why CNNs often generalize better than MLPs. It's not necessarily due to a different "implicit bias" in the Real World, but because CNNs can optimize faster on the population loss in the Ideal World.
  • Bootstrap Error is Key: The authors' main empirical claim is that the bootstrap error is surprisingly small in many realistic deep learning scenarios, especially for image classification. This makes the Ideal World performance a strong predictor of Real World performance.
  • Unifying Over/Under-parameterized Regimes: The framework offers a way to unify understanding across different parameterization regimes. Architectures that optimize well in the infinite-data (under-parameterized) regime should also generalize well in the finite-data (over-parameterized) regime if the bootstrap error is small.
  • Soft-Error vs. Hard-Error: The use of soft-error is motivated by theoretical convergence properties and empirical observations that the bootstrap gap is often smaller for soft-errors.

Key Results

  • Small Bootstrap Error: Across various architectures (ResNets, MLPs, ViTs) and datasets (CIFAR-5m, ImageNet-DogBird), experiments consistently show that the bootstrap error (difference in test soft-error between Real and Ideal Worlds) is small, especially as training progresses and data size increases.
  • Real vs. Ideal World Alignment: Figures 2 and 3 show that the test soft-errors of models trained in the Real World and Ideal World are often very close, particularly for standard architectures.
  • Data Augmentation and Pretraining Effects: The framework captures the benefits of data augmentation and pretraining, showing that they often lead to faster optimization in the Ideal World and improved generalization in the Real World.
  • Optimizer Behavior: Experiments with Adam show similar trends to SGD, with the bootstrap error remaining small.
  • Toy Example: A carefully constructed toy example demonstrates settings where the bootstrap error can be small even when the generalization gap is large, and vice-versa, highlighting the framework's ability to disentangle these factors.

Limitations and Future Work

  • Bootstrap Error Dependence: The authors acknowledge that the bootstrap error $\epsilon$ is not universally small for all models, learning tasks, or settings (e.g., it can be larger at limited sample sizes or without data augmentation, and in linear regression). Fully understanding its dependence on parameters like $n, D, F, t$ is an important area for future study.
  • Theoretical Guarantees: While the framework is empirically validated, strong theoretical guarantees for the smallness of the bootstrap error in deep learning are still lacking.
  • Non-monotonic Test Error: The framework's applicability might be limited in settings where Real World test error is non-monotonic (e.g., due to epoch double-descent), as the stopping time $T_0$ is defined by training error convergence.
  • Future Research: The authors suggest that their framework lays a foundation for future research into understanding generalization by focusing on online optimization properties and the bootstrap error. They also propose it can provide a new perspective on phenomena like implicit bias, model selection, and the benefits of data augmentation and pretraining.

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 a foundation for future research in the area.
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