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

Preetum Nakkiran, Behnam Neyshabur, Hanie Sedghi

Harvard University, Google Brain

Presenters: Chris Zhang, Dami Choi, Anqi (Joyce) Yang

Generalization theory

Goal: Understand when and why trained models have small test error

Problem 2: �Since our current bounds for this are all expressed in terms of function capacity, they turn vacuous when applied to overparameterized neural networks

Problem 1: �Modern methods can often achieve zero training error. The resulting equation becomes trivial

Deep Bootstrap Framework

Key idea: Consider alternative test error decomposition

Online learning: What is the test error after training for t steps on completely fresh data?

​

How fast does the model optimize the population loss in the ideal world?

​

Online learning: What is the test error after training for t steps on completely fresh data?

​

How fast does the model optimize the population loss in the ideal world?

​

Bootstrap Error: How much does the real world differ from the ideal world?

​

What effect does reusing data instead of having access to unlimited fresh data have on test error?

Main result of the paper

In typical deep learning setups, the bootstrap error is seen to be very small!

​

What small bootstrap error looks like…

For different architectures as well…

Even when overfitting … !

What does this imply

To try to understand performance in

• Offline
• Real world, finite-data
• Overparameterized

​

settings ...

What does this imply

To try to understand performance in

• Offline
• Real world, finite-data
• Overparameterized

​

settings ...

We can study the

• Online
• ideal world, infinite-data
• Underparameterized

​

setting (borrowing literature from online learning community, etc.)

​

What does this imply

Summary: Good online learners are good offline generalizers

Main Experiment

Measuring Bootstrap Error Empirically

Problem: Typically we don’t have infinite data.�How to simulate Ideal World for tasks we care about (e.g CIFAR-10)?

​

​

Measuring Bootstrap Error Empirically

​

​

​

• Metric: Soft-error instead of hard error
• Measure bootstrap error until Real World training converges
• 1% training soft-error
• Real World and Ideal World executes exact same training code
• Optimizer, Data-augmentation, learning rate schedule, hyperparameters, etc.

Bootstrap error is small for various architectures and learning-rates

CIFAR-5m

ImageNet-DogBird

Some phenomena �through the lens of the�Bootstrap Framework

Model Selection in different data-size regimes

​

​

Deep learning theory focuses on overparameterized networks

​

But data is big enough nowadays to take us into the underparameterized regime

• 300 million JFT image data set
• 1 billion Instagram image dataset
• Internet-text datasets for GPT3

​

​

Model Selection in different data-size regimes

​

Why are the same techniques (architectures and training methods) used in practice in both over- and under-parameterized regimes?

​

Intuitively a priori,

• Over-parameterized regime - architecture matters for generalization reasons
• Under-parameterized regime - architecture matters for optimization reasons

�

Model Selection in different data-size regimes

​

Bootstrap framework: ��If bootstrap error is small

architectures which perform well in the online setting (underparameterized regime)

also generalize in the offline setting (overparameterized regime)

​

Hence why it’s not too surprising that the same methods work well in both regimes

Implicit Bias via Explicit Optimization

​

​

One line of work studies the effect of implicit bias of gradient descent.

• Consider a CNN and an MLP which subsumes the CNN
• Both find local minima that have similar training accuracy

Traditional explanation: SGD implicitly biases CNN to better generalizing local minima compared to MLP

Implicit Bias via Explicit Optimization

Deep bootstrap framework:

Instead of studying which empirical minima SGD converges upon, �study why SGD quickly optimizes the population loss.

​

Generalization is captured by the fact tha CNN optimize population loss much faster than MLP

​

Ablations

What affects the bootstrap error?

• Real World sample size
• Data augmentation
• Test metric

Effect of sample size

• Increasing the sample size => stopping time extends
• Bootstrap error is more or less small until stopping time

Effect of data augmentation

• Data augmentation affects the stopping time more than the bootstrap gap
• Might hurt the performance in the Ideal World

Effect of test metric

• Bootstrap gap is not small for all test metrics
• Huge gap for loss makes sense
• Training to convergence in Real World causes network weights to grow => softmax distribution concentrates.

Summary

• New framework to understand generalization in deep learning.
• Generalization in offline learning => optimization in online learning

Limitations

• The gap is not universally small for all models and tasks
• Lack of theory or explanation
• We don’t understand why the gap is small given that we’re overfitting on the training set (~99% training soft-error)
• We attempted to understand this in toy setting (colab notebook link)