The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers
Authors: Preetum Nakkiran
Behnam Neyshabur
Hanie Sedghi
Venue: ICLR 2021 Poster (2021)
Keywords: generalization
optimization
online learning
understanding deep learning
empirical investigation

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. 

Published as a conference paper at ICLR 2021
THE DEEP BOOTSTRAP FRAMEWORK: GOOD ONLINE LEARNERS ARE GOOD OFFLINE GENERALIZERS
Preetum Nakkiran
Behnam Neyshabur
Hanie Sedghi
Harvard University"
Blueshift, Alphabet
Google Research, Brain team haedgh @goog] e.com
preetumêcs. ha rvard.edi
neyshabur@googlee.
ABSTRACT
We propose new framework for reasoning about generalization in deep learning.
The core idea is to couple the Real World, where optimizers take stochastic gradi- ent steps on the empirical loss, to 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 evi- dence that this gap between worlds be small in realistic deep learning settings, in particular supervised image classification. For example, CNNs generalize bet- ter than MLPs image distributions in the Real World, but this is "because" they optimize faster on the population loss in the Ideal World. This suggests our frame- work a useful tool for understanding generalization in deep learning, and lays a foundation for future research in the area.
INTRODUCTION
Real World (solid) vs. Ideal World (dashed)
0.9
Ideal World Test
0.8
Real World Test
0.7
World Train
Real World: SGD on empirical loss
Soft-Error
0.6
0.5
0.4
Ideal World: SGD on population loss
0.3
V/T-B/4
0.2
ResNet18
0.0
5000
10000
15000 20000 25000 30000 35000 40000
SGD Iterations
Figure 1: Three architectures trained from scratch on CIFAR-5m, a CIFAR-10-like task. The Real World is trained 50K samples for 100 epochs, while the Ideal World is trained on 5M samples in pass. The Real World Test remains close to Ideal World Test, despite a large generalization gap.
The goal of generalization theory in supervised learning to understand when and why trained models have small test error. The classical framework of generalization decomposes the test error of model fr as:
TestError(f.) TrainError(fAA) + (TsstEmror(()) (f) TrainEEror((f))
Generalization gap
and studies each part separately (e.g. Vapnik and Chervonenkis (1971); Blumer et al. (1989); Shalev- Shwartz and Ben-Davia (2014)). Many works have applied this framework to study generalization of deep networks (e.g. Bartlett (1997); Bartlett et al. (1999); Bartlett and Mendelson (2002); Anthony and Bartlett (2009); Neyshabur et al. (2015b); Dziugaite and Roy (2017); Bartlett et al. (2017); Neyshabur al. (2017); Harvey al. (2017); Golowich et al. (2018); Arora et al. (2018; 2019);

---

Published as a conference paper at ICLR 2021
Allen-Zhu et al. (2019); Long and Sedghi (2019): Wei and Ma (2019)). However, there least two obstacles to understanding generalization of modern neural networks via the classical approach.
1. Modern methods can interpolate, reaching TrainError O, while still performing well. In these settings, the decomposition of Equation (I) does not actually reduce test error into two different subproblems: it amounts to writing TestError 0 + TestError. That is, understanding the generalization gap here is exactly equivalent to understanding the test error itself.
2. Most if not all techniques for understanding the generalization gap (e.g- uniform con- vergence, VC-dimension, regularization, stability, margins) remain vacuous (Zhang al., 2017; Belkin et al., 2018a;b; Nagarajan and Kolter, 2019) and not predictive (Nagarajan and Kolter, 2019; Jiang et al., 2019; Dziugaite al., 2020) for modern networks.
In this work, we propose an alternaee approach to understanding generalization to help overcome these obstacles. The key idea is to consider an alternate decomposition:
TestError = TestError (iid) (TestError(fe) - TestError (fta))
(2)
A: Online Learning
B: Bootstrap error
where Jr is the neural-network after L optimization steps (the "Real World"), and fhd is network trained identically to ft, but using fresh samples from the distribution in each mini-batch step (the "Ideal World"). That is, fild is the result of optimizing the population loss for steps, while fo is the result of optimizing on the empirical loss as usual (we define this more formally later).
This leads to a different decoupling of concerns, and proposes alternate research agenda to un- derstand generalization. To understand generalization in the bootstrap framework, it is sufficient to understand:
(A) Online Learning: How quickly models optimize on the population loss, in the infinite-data regime (the Ideal World).
(B) Finite-Sample Deviations: How closely models behave in the finite-data vs. infinite-data regime (the bootstrap error).
Although neither of these points are theoretically understood for deep networks, they are closely related rich areas in optimization and statistics, whose tools have not been brought fully bear on the problem of generalization. The first part (A) is purely a question in online stochastic op- timization: We have access to a stochastic gradient oracle for population loss function, and we are interested in how quickly an online optimization algorithm (e.g. SGD, Adam) reaches small population loss. This problem well-studied in the online learning literature for convex functions (Bubeck, 2011; Hazan, 2019; Shalev-Shwartz et al., 201 1), and is an active area of research in non- convex settings (Jin et al., 2017: Lee et al., 2016; Jain and Kar, 2017: Gao et al., 2018; Yang et al., 2018; Maillard and Munos, 2010). In the context of neural networks, optimization is usually studied on the empirical loss landscape (Arora et al., 2019; Allen-Zhu et al., 2019), but we propose study- ing optimization the population loss landscape directly. This highlights key difference in our approach: we never compare test and train quantities- we only consider test quantities.
The second part (B) involves approximating fresh samples with "reused" samples, and reasoning about behavior of certain functions under this approximation. This is closely related to the nonpara- metric bootstrap in statistics (Efron, 1979; Efron and Tibshirani, 1986), where sampling from the population distribution is approximated by sampling with replacement from an empirical distribu- tion. Bootstrapped estimators are widely used in applied statistics, and their theoretical properties are known in certain cases (e.g. Hastie et al. (2009); James et al. (2013); Efron and Hastie (2016); Van der Vaart (2000)). Although current bootstrap theory does not apply neural networks, is conceivable that these tools could eventually be extended to our setting.
Experimental Validation. Beyond the theoretical motivation, our main experimental claim that the bootstrap decomposition is actually useful: in realistic settings, the bootstrap enror is often small, and the performance of real classifiers is largely captured by their performance in the Ideal World. Figure shows one example of this, as a preview of our more extensive experiments in Section 4. We plot the test error of a ResNet (He et al., 2016 an MLP, and a Vision Transformer (Dosovitskiy et al., 2020) a CIFAR- 10- task, over increasing minibatch SGD iterations. The Real World is trained on 50K samples for 100 epochs. The Ideal World is trained on 5 million samples with a single pass. Notice that the bootstrap error is small for all architectures, although the generalization
2

---

Published as a conference paper at ICLR 2021
gap can be large. In particular, the convnet generalizes better than the MLP finite data, but this is "because" it optimizes faster on the population loss with infinite data. See Appendix D.1 for details.
Our Contributions.
We propose the Deep Bootstrap framework for understanding generalization in deep learning, which connects offline generalization online optimization. (Section 2). Validation: We give evidence that the bootstrap error is small realistic settings for su- pervised image classification, by conducting extensive experiments on large-scale tasks (including variants of CIFAR- 10 and ImageNet) for many architectures (Section 4). Thus,
Framework:
The generalization of models is largely determined by their optimization speed online and offline learning.
Implications: We highlight how our framework can unify and yield insight into important phenomena in deep learning, including implicit bias, model selection, aata-augmentation and pretraining (Section 5). In particular:
Good models and training procedures are those which (1) optimize quickly in the Ideal World and (2) do not optimize too quickly in the Real World.
Additional Related Work. The bootstrap error is also related to algorithmic stability (e.g. Bousquet and Elisseeff (2001); Hardt (2016)), since both quantities involve replacing samples with fresh samples. However, stability-based generalization bounds cannot tightly bound the bootstrap error, since there are many settings where the generalization gap is high, but bootstrap error is low.
THE DEEP BOOSTRAP
Here we more formally describe the Deep Bootstrap framework and our main claims. Let F denote learning algorithm, including architecture and optimizer. We consider optimizers which can be used in online learning. such as stochastic gradient descent and variants. training in the "Real World": using the architecture and optimizer specified by F, train set of n samples from distribution D, for optimizer steps. Let Train=(D, oo, I) denote this same optimizer operating on the population loss (the "Ideal World"). Note that these two procedures use identical architectures, lcarning-rate schedules, mini-batch size, etc the only difference is, the Ideal World optimizer sees fresh minibatch of samples in each optimization step, while the Real World reuses samples in minibatches. Let the Real and Ideal World trained models be:
Trains (D, n, t) denote
Real World:
ft <- Train (D, n,,)
Ideal World:
f <- (D, t)
We now claim that for all until the Real World converges, these two models ft, ft have similar test performance, In our main claims, we differ slightly from the presentation in the Introduction in that we consider the "soft-error" of classifiers instead of their hard-errors. The soft-accuracy of classifiers defined the softmax probability the correct label, and (soft-error) = 1 (soft-accuracy). Equivalently, this is the expected error of temperature- samples from the softmax distribution. Formally, define as the bootstrap error the gap in soft-error between Real and Ideal worlds at time t:
TestSoftError (ft) = (fstSofftErrorr((("))))) + E(n, D,F,t)
(3)
Our main experimental claim is that the bootstrap error is uniformly small in realistic settings.
Claim (Bootstrap Error Bound, informal) For choices of (n, D,F) corresponding to realistic settings in deep learning for supervised image classification, the bootstrap error e(n, D, D,F. 1) is small for all < To- The "stopping time" " To is defined as the time when the Real World reaches small training error (we 1%) that is, when Real World training has essentially converged.
The restriction on < To is necessary, since as + op the Ideal World will continue to improve, but the Real World will some point essentially stop changing (when train error ss 0). However, claim that these worlds are close for "as long as we can hope" " as long as the Real World optimizer is still moving significantly.
3

---

Published as a conference paper at ICLR 2021
Error vs. Soft-Error. We chose to measure soft-error instead of hard-error in our framework for both empirical and theoretically-motte motivated reasons. Empirically, we found that the bootstrap gap is often smaller with respect to soft-errors. Theoretically, we want define the bootstrap gap such that it converges to O as data and model size are scaled to infinity. Specifically, if we consider an overparameterized scaling limit where the Real World models always interpolate the train data, then Distributional Generalization (Nakkiran and Bansal, 2020) implies that the bootstrap gap for test error will not converge on distributions with non-zero Bayes risk. Roughly, this is because the Ideal World classifier will converge to the Bayes optimal one (argmax, P(y((z)), while the Real World interpolating classifier will converge to a sampler from p(y|z)) Considering soft-errors in- stead of errors nullifies this issue. We elaborate further on the differences between the worlds in Section 6. See also Appendix C for relations to the nonparametric bootstrap (Efron, 1979).
3 EXPERIMENTAL SETUP
Our bootstrap framework could apply to any setting where an iterative optimizer for online learning is applied in an offline setting. In this work we primarily consider stochastic gradient descent (SGD) applied to deep neural networks for image classification. This setting is well-developed both in practice and in theory, and thus serves as an appropriate first step to vet theories of generalization, done in many recent works (e.g. Jiang et al. (2019); Neyshabur et al. (2018); Zhang et al. (201 7); Arora et al. (2019)). Our work does not depend on overparameterization- it holds for both under and over parameterized networks, though it is perhaps most interesting in the overparameterizze setting. We now describe our datasets and experimental methodology.
3.1 DATASETS
Measuring the bootstrap error in realistic settings presents some challenges, since we do not have enough samples to instantiate the Ideal World. For example, for a Real World CIFAR-10 network trained on 50K samples for 100 epochs, the corresponding Ideal World training would require million samples (fresh samples in each epoch). Since do not have 5 million samples for CIFAR- 10, we use the following datasets as proxies. More details, including sample images, in Appendix E.
CIFAR-5m. We construct a dataset of 6 million synthetic CIFAR-10-like images, by sampling from the CIFAR-10 Denoising Diffusion generative model of Ho et al. (2020), and labeling the unconditional samples by 98.5% accurate Big-Transfer model (Kolesnikov et al., 2019). These are synthetic images, but close to CIFAR-I0 for research purposes. For example, a WideResNe128-10 trained on 50K samples from CIFAR-5m reaches .%% test accuracy on CIFAR-10 test set. We use 5 million images for training. and reserve the rest for the test set. We plan to release this dataset.
ImageNet-DogBird To test our framework in more complex settings, with real images, we con- struct a distribution based on ImageNet ILSVRC-2012 (Russakovsky et al., 2015). Recall that we need a setting with a large number of samples relative to the difficulty of the task: if the Real World performs well with few samples and few epochs, then we can simulate it in the Ideal World. Thus, we construct a simpler binary classification task out of ImageNet by collapsing classes into the superclasses "hunting dog" and "bird." This is roughly balanced task with 155K total images.
3.2 METHODOLOGY
For experiments on CIFAR-5m, we exactly simulate the Real and Ideal worlds as described in Sec- tion 2. That is. for every Real World architecture and optimizer we consider, we construct the corresponding Ideal World by executing the exact same training code, but using fresh samples in each epoch. The rest of the training procedure remains identical, including data-augmentation and learning-rate schedule. For experiments on ImageNet-DogBirce we do not have enough samples to exactly simulate the Ideal World. Instead, we approximate the Ideal World by using the full training set (N 155K) and data-augmentation. Formally, this corresponds to approximating Train (D, oc, t) by Trainy (D, 155K, t). In practice, we train the Real World on n = 10K sam- ples for 120 epochs, so we can approximate this with less than 8 epochs on the full 155K train set. Since we train with data augmentation (crop+resize+flpp) each of the repetitions of each sample will undergo different random augmentations, and thus this plausibly approximates fresh samples.
4

---

Published as a conference paper at ICLR 2021
Real vs. Ideal Worlds
Real vs. Ideal World: DARTS
y=x
resnet18
0.40
0.6
resnet34
Ideal Soft-Error
vgg16
Ideal Soft- Coft-Error
0.35
0.20
0.5
Train Error
vgg11_ bn
0.30
myrtles
0.15
densenet40_3
0.25
0.3
densenet40_]
0.10
alexnet
0.20
0.2
MLP[3x2048]
0.05
MLP[3x128]
0.15
0.2
0.4
0.6
0.2
0.3
0.4
Real Soft-Error
Real Soft-Error
(a) Standard architectures.
(b) Random DARTS architectures.
Figure 2: Real vs Ideal World: CIFAR-5m. SGD with 50K samples. (a): Varying learning-rates
0.1 0.01
0.00000 (A). (b): Random architectures from DARTS space (Liu et al., 2019).
Stopping time. We stop both Real and Ideal World training when the Real World reaches a small value of train error (which set as 1% in all experiments). This stopping condition is necessary, as described in Section 2. Thus, for experiments which report test performance "at the end of training", this refers either when the target number of epochs is reached, or when Real World training has converged (< 1% train error). We always compare Real and Ideal Worlds after the exact same number of train iterations.
MAIN EXPERIMENTS
We now give evidence to support our main experimental claim, that the bootstrap error E is often small for realistic settings in deep learning for image classification. In all experiments in this section, we instantiate the same model and training procedure in the Real and Ideal Worlds, and observe that the test soft-error close at the end of training. Full experimental details are in Appendix D.2.
CIFAR-5m. In Figure 2a we consider a variety of standard architectures on CIFAR-5m -mm, from fully- connected nets to modern convnets. In the Real World, we train these architectures with SGD n = 50K samples from CIFAR-5m, for 100 total epochs, with varying initial learning rates. We then construct the corresponding Ideal Worlds for each architecture and learning rate, trained in the same way with fresh samples each epoch. Figure 2a shows the test soft-error of the trained classifiers in the Real and Ideal Worlds at the end of training. Observe that test performance very close in Real and Ideal worlds, although the Ideal World sees 100 unique samples during training.
To test our framework for more diverse architectures, we also sample 500 random architectures from the DARTS search space (Liu et al., 2019). These are deep convnets of varying width and depth, which range size from 70k 5.5 million parameters. Figure 2b shows the Real and Ideal World test performance at the end of training these are often within 3%.
ImageNet: DogBird. We now test various ImageNet architectures on ImageNet-DogBird. The Real World models are trained with SGD tation. We approximate the Ideal World by training on 155K samples as described in Section 3.2. Figure 3a plots the Real Ideal World test error at the end of training, for various architectures. Figure 3b shows this for ResNet- 18s of varying widths.
10K samples with standard ImageNet data augmen-
5 DEEP PHENOMENA THROUGH THE BOOTSTRAP LENS
Here we show that our Deep Bootstrap framework can be insightful to study phenomena and design choices in deep learning. For example, many effects in the Real World can be seen through their corresponding effects in the Ideal World, Full details for experiments provided in Appendix D.
Model Selection in the Over- and Sadder-paramtterii Regimes. Much of theoretical work in deep learning focuses overparameterizee networks, which are large enough fit their train sets.
5

---

Published as a conference paper at ICLR 2021
Real vs. Ideal Worlds
Real vs. Ideal Worlds: ResNet18
0.35
ymx
0.16
y-x
wiath-96
Ideal Soft-Error
0.30
vagi6
Ideal Soft Error
0.14
width=32
width-64
0.25
*g011
width=24
mobilonst.12
0.12
width=15
0.20
resnent50 32o4d
aleanet
width=12
resner50
bagnet53
0.10
width-8
wisth-10
0.15
Eegret12
Bagnett
Sconv?
0.08
0.10
0.06
0.05
0.1
0.2
0.3
0.075
0.100 0.125 Soft-Error
0.150
Real Soft-Error
(a) Standard architectures.
(b) ResNet-188 of varying width.
Figure 3: ImageNet-DogBirr, Real World models trained on 10K samples.
However, in modern practice, state-of-the-ard networks can be either depending on the scale of data. For example, SOTA models on 300 million JFT images or billion
under-parameteent
Instagram images are underfitting, due to the massive size of the train set (Sun al., 2017; Mahajan et al., 2018). In NLP, modern models such as GPT-3 and T5 are trained on massive internet-text datasets, and so are solidly in the underparameterized regime (Kaplan al., 2020; Brown et al., 2020: Raffel et al., 2019). We highlight one surprising aspect of this situation:
The same techniques (architectures and training methods) are used in practice in both over- and ander-paramelerized regimes.
For example, ResNet-101 101 competitive both billion images of Instagram (when it is underpa- rameterized) and on 50k images of CIFAR-10 (when it is overparameterized) This observation was made recently Bornschein et (2020) for overparameterized architectures, and is also consistent with the conclusions of Rosenfeld et al. (2019). It apriori surprising that the same architectures do well in both over and underparameterized regimes, since there are very different considerations in each regime. In the overparameterized regime, architecture matters for generalization reasons: there are many ways fit the train set, and some architectures lead SGD to minima that generalize better. In the underparameterized regime, architecture matters for purely optimization reasons: all models will have small generalization gap with billion+ samples, but we seek models which are capable of reaching low values of test loss, and which do quickly (with few optimization steps). Thus, should be surprising that in practice, we use similar architectures in both regimes.
Our work suggests that these phenomena are closely related: If the boostrap error is small, then we should expect that architectures which optimize well in the infinite-data (underparameterizee)) regime also generalize well in the finite-data (overparameterrized) regime. This unifies the two apriori different principles guiding model-selection in over and under--parameterized regimes, and helps understand why the same architectures are used in both regimes.
Implicit Bias via Explicit Optimization. Much recent theoretical work has focused on the implicit bias of gradient descent (e.g. Neyshabur et al. (2015a); Soudry et al. (2018); Gunasekar et al. (2018b;a); Ji and Telgarsky (2019); Chizat and Bach (2020)). For overparameterized networks, there are many minima of the empirical loss, some which have low error and others which have high test error. Thus studying why interpolating networks generalize amounts to studying why SGD "biased" towards finding empirical minima with low population loss. Our framework suggests an alternate perspective: instead of directly trying to characterize which empirical minima SGD reaches, it may be sufficient to study why SGD optimizes quickly on the population loss. That is, instead of studying implicit bias of optimization on the empirical loss, could study explicit properties optimization on the population loss.
The following experiment highlights this approach. Consider the D-CONV and D-FC architectures introduced recently by Neyshabur (2020). D-CONV is deep convolutional network and D-FC its fully-connected counterpart: an MLP which subsumes the convnet in expressive capacity. That is, D-FC is capable representing all functions that D-CONV can represent, since it replaces all conv layers with fully-connected layers and unties all the weights. Both networks reach close to 0 train

---

Published as a conference paper at ICLR 2021
Real World vs. Ideal World: Varying Train Size
Real vs. Ideal World (CIFARR55m
0.6
y-x
n=5000
0.5
0.6
n=10000
n=25000
Real In-1000)
Test Soft-Error
0.4
Ideal Soft-Eror
0.5
n=50000
(n=2000)
0.3
0.4
0.2
(nw 100000
0.1
0.0
5000
10000
15000 20000 25000 30000 35000 40000
0.1
0.2
0.3
0.4
0.5
0.6
0.7
SGD iterations
Real Error-rrar
(a) ResNet-18, 18, varying samples.
(b) All architectures, varying samples.
Figure 4: Effect of Sample Size.
error 50K samples from CIFAR-5m, but the convnet generalizes much better. The traditional explanation for this is that the "implicit bias" of SGD biases the convnet to a better-generalliingg minima than the MLP. We show that, in fact, this generalization is captured by the fact that D- CONV optimizes much faster on the population loss than D-FC. Figure Sc shows the test and train errors of both networks when trained on 50K samples from CIFAR-5m, in the Real and Ideal Worlds. Observe that the Real and Ideal world test performances are nearly identical.
Sample Size. In Figure 4, we consider the effect of varying the train set size in the Real World. Note that in this case, the Ideal World does not change. There are two effects of increasing n: (1) The stopping time extends- Real World training continues for longer before converging. And (2) the bootstrap error decreases. Of these, (1) is the dominant effect. Figure 4a illustrates this behavior in detail by considering a single model: ResNet-18 on CIFAR-5m. We plot the Ideal World behavior of ResNet-18, as well as different Real Worlds for varying n. All Real Worlds are stopped when they reach < 1% train error, as we do throughout this work. After this point their test performance is essentially flat (shown as faded lines). However, until this stopping point, all Real Worlds are roughly close to the Ideal World, becoming closer with larger n. These learning curves representative of most architectures in our experiments. Figure 4b shows the same architectures of Figure 2a, trained on various sizes of train sets from CIFAR-5m. The Real and Ideal worlds may deviate from each other at small n, but become close for realistically large values of
Data Augmentation. Data augmentation in the Ideal World corresponds to randomly augmenting each fresh sample before training on it (as opposed to re-using the same sample for multiple aug- mentations). There are 3 potential effects of data augmentation in our framework: (1) it can affect the Ideal World optimization, (2) can affect the bootstrap gap, and (3) it can affect the Real World stopping time (time until training converges). We find that the dominant factors are (1) and (3), though data augmentation does typically reduce the bootstrap gap as well, Figure 5a shows the ef- fect of data augmentation on 18 18 for CIFAR-5m In this case, data augmentation does not change the Ideal World much, but it extends the time until the Real World training converges. This view suggests that good data augmentations should (1) not hurt optimization in the Ideal World (i.e., not destroy true samples much), and (2) obstruct optimization in the Real World (so the Real World can improve for longer before converging). This is aligned with the "affinity" and "diversity" view of data augmentations in Gontijo-Loper et al. (2020). See Appendix B.3 for more figures, including examples where data augmentation hurts the Ideal World.
Pretraining. Figure 5b shows the effect of pretraining for Image-GPT (Chen et al., 2020), trans- former pretrained for generative modeling ImageNet. We fine-tune iGPT-S 2K samples of CIFAR-10 (not CIFAR-5m, since we have enough samples in this case) and compare initializing from an early checkpoint vs. the final pretrained model. The fully-pretrained model generalizes bet- ter in the Real World, and also optimizes faster in the Ideal World. Additional experiments including -etgeeee--retrainee Vision Transformers (Dosovitskiy et al., 2020) are in Appendix B.5.
Random Labels. Our approach of comparing Real and Ideal worlds also captures generalization in the random-label experiment of Zhang et al. (2017). Specifically, if we train on a distribution with purely random labels, both Real and Ideal world models will have trivial test error.
7

---

Published as a conference paper at ICLR 2021
Real Ideal: Lifect Data
Real vs Ideal: GPage-GPT
Real vs. Ideal: Architectural
No
Early ckpt
ideal Worlds
Data Aug
0.7
rinel Capt
Ideal Worlds
0.7
ideal Worlds
D-CONV
"Pain
SoltEre)
0.6
Test Soft Enarr
0.6
0.5
0.5
0.5
0.4
0.4
0.4
0.3
0.2
0.1
0.3
0.0
5000
10000
15000
20000
0.0
25
50
75
100
125
150
0.0
10000
20000
30000
40000
SGD lterations
Adam Iterations
5GD Iterations
(a) Data Aug: ResNet-18. 18.
(b) Pretrain: Image-GPT (n = 2K).
(c) Implicit Bias.
Figure 5: Deep Phenomena in Real vs. Ideal Worlds.
6 DIFFERENCES BETWEEN THE WORLDS
In framework, we only compare the test soft-error of models in the Real and Ideal worlds. We do not claim these models are close in all respects-ii in fact, this is not true. For example, Figure 6 shows the same ResNet-18s trained in the Introduction (Figure 1), measuring three different metrics in both worlds. Notably, the test loss diverges drastically between the Real and Ideal worlds, although the test soft-error (and a lesser extent, test error) remains close. This because training to convergence in the Real World will cause the network weights to grow unboundedly, and the softmax distribution to concentrate (on both train and test). In contrast, training in the Ideal World will generally not cause weights to diverge, and the softmax will remain diffuse. This phenomenon also means that the Error and Soft-Error are close the Real World, but can be slightly different in the Ideal World, which is consistent with our experiments.
Real vs. Ideal: SoftError
Real vs. Ideal: Error
Real vs. Ideal: Lass
Real
1.4
Real Test
Train
Train
Train
0.7
Idcal Test
0.7
Ideal Test
1.2
ideal Test
0.6
0.6
1.0
Sotteror
0.5
0.5
Losg
0.0
0.6
0.2
0.2
0.1
0.1
0.0
10000
20000
J0000
40000
10000
20000
30000
40000
0
10000
20000
30000
40000
SGD Iter lterations
SGD Iterations
SGD Iterations
Figure 6: SoftError vs. Error vs. Loss: ResNet-18.
7 CONCLUSION AND DISCUSSION
We propose the Deep Bootstrap framework for understanding generalization in deep learning. Our approach is to compare the Real World, where optimizers take steps on the empirical loss, to an Ideal World, where optimizers have infinite data and take steps on the population loss. We find that in modern settings, the test performance of models is close between these worlds. This establishes new connection between the fields of generalization and online learning: models which learn quickly (online) also generalize well (offline). Our framework thus provides a new lens on deep phenomena, and lays promising route towards theoretically understanding generalization in deep learning.
Limitations. Our work takes first steps towards characterizing the bootstrap error E, but fully un- derstanding this, including its dependence on problem parameters (n, D, F, t), is an important area for future study. The bootstrap error is not universally small for all models and learning tasks: for example, we found the gap was larger at limited sample sizes and without data augmentation. More- over, it can be large in simple settings like linear regression (Appendix A), or settings when the Real World test error is non monotonic (e.g. due to epoch double-decent (Nakkiran et al., 2020)). Nevertheless, the gap appears to be small in realistic deep learning settings, and we hope that future work can help understand why.
8

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
Work completed in part while PN was interning at Google. PN also supported in part by a Google PhD Fellowship, the Simons Investigator Awards of Boaz Barak and Madhu Sudan, and NSF Awards under grants CCF 1565264, CCF 1715187 and IIS 1409097.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. Advances in neural information processing systems, pages 6158-6169, 2019.
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundationss cambridge university press, 2009.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. arXiv preprint arXiv: 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332, 2019.
Peter L Bartlett. For valid generalization the size of the weights is more important than the size of the network. In Advances in neural information processing systems, pages 134-140, 1997.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-453 2002.
Peter I. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. In Advances in neural information processing systems, pages 190-196, 1999.
Peter I. Bartlett, Dylan J Foster, and Matus Telgarsky. Speetrally-normaaizzed margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6240-6249, 2017.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances in neural information processing systems, pages 2300-2311, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. arXiv preprint arXiv:1802.01 2018b.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://wwe wandb. com/ Software available from wandb.com.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-cherronenkis dimension. Journal of the ACM (JACM), 36(4))929-99))) 965, 1989.
Jörg Bornschein, Francesco Visin, and Simon Osindero. Small data, big decisions: Model selection
in the small-data regime. ICML, 2020.
Olivier Bousquet and André Elisseeff. Algorithmic stability and generalization performance, In Advances in Neural Information Processing Systems, pages 196-202, 2001.
Wieland Brendel and Matthias Bethge. Approximating cnns with bag-of-local-featree models
works surprisingly well imagenet. arXiv preprint arXiv:1904.00760, 2019.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. arXiv preprint arXiv:2005.14165, 2020.
Sébastien Bubeck. Introduction online optimization. Lecture Notes, 2, 2011. 1.

---

Published as a conference paper at ICLR 2021
Mark Chen, Alec Radford, Rewon Child, Jeff Wu, Heewoo Jun, Prafulla Dhariwal, David Luan, and Ilya Sutskever. Generative pretraining from pixels. In Proceedings of the 37th International Conference Machine Learning, 2020.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprini arXiv:2002.04488, 2020.
Terrance Deesies and Graham W Taylor. Improved regularization convolutional neural networks with cutout. arXiv preprint arXiv: 170..0/770..05555 2017.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architec- ture search. In International Conference on Learning Representations, 2020. URL https: / //openeeeviww....
ZKBKDr.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 1929, 2020.
Gintare Karolina Dziugaite and Daniel Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M Roy. In search of robust measures of generaliza- tion. Advances in Neural Information Processing Systems, 33, 2020.
B. Efron. Bootstrap methods: Another look at the jackknife. Ann. Statist. 7(1):1-26, 01 1979. doi: 1//21//////117344455
URLhttpss / /dii wtt.ee.org/.....1111111 aos hate////////113455555 1176344552.
Bradley Efron and Trevor Hastie. Computer age statistical inference, volume 5. Cambridge Univer- sity Press, 2016.
Bradley Efron and Robert Tibshirani. Bootstrap methods for standard errors, confidence intervals, and other measures of statistical accuracy. Statistical science, pages 54-75, 1986.
Bradley Efron and Robert J Tibshirani. An introduction to the bootstrap. CRC press, 1994.
Chuang Gan, Jeremy Schwartz, Seth Alter, Martin Schrimpf, James Traer, Julian De Freitas, Jonas Kubilius, Abhishek Bhandwaldar, Nick Haber, Megumi Sano, et al. Threedworld: A platform for interactive multi-modal physical simulation. arXiv preprint arXiv:2007.0499 2020.
Xiand Gao, Xiaobo Li, and Shuzhong Zhang. Online learning with non-convex losses and non- stationary regret. In International Conference on Artificial Intelligence and Statistics, pages 235- 243, 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
Raphael Gontijo-Lopes, Sylvia Smullin, Ekin Cubuk, and Ethan Dyer. Affinity and diversity: Quantifying mechanisms of data augmentation. arXiv preprint urXiv:2002.08999 2020.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprini 002.v:8802.0824: 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018b.
Moritz Hardt. Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International Conference on Machine Learning, pages 1225-1234 PMLR, 2016.
10

---

Published as a conference paper at ICLR 2021
Charles R. Harris, K. Jarrod Millman, St'efan J. der Walt, Ralf Gommers, Pauli Virtanen, David Couraaeaau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fern andez del R' i0, Mark Wiebe, Pearu Peterson, Pierre G' Marchatt, Kevin Shep- pard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-3362 September 2020. doi: 10.1038/ 441586-020-2649-22 URL https: doi org 10.1008 41586 020- 2649-2.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension bounds for piece- wise linear neural networks. In Conference Learning Theory, pages 1064-1068, 2017. 2017.
Trevor Hastic, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Flad Hazan. Introduction to online convex optimization. arXiv preprint arXiv: 0e0.99999952777 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pages 630-645. Springer, 2016b.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. arXiv preprint arxiv:2006. 11239, 2020.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and patlern recognition, pages 4700 2017.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. arXiv preprint arXiv:2006.07322, 2020.
D. Hunter. Matplotlib: 2d graphics environment. Computing in Science & Engineering, 9(3): 90-95, 2007. doi: 10. 109/MCSE.2007.55
Plotly Technologies Inc. Collaborative data science, 2015. URL httttts/s///pt.11
Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. arXiv preprint arXiv:1712.07897, 2017.
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction statistical learning, volume 112. Springer, 2013.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent nonseparable data. In Conference on Learning Theory, pages 1772-1798, 2019.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv:1912.022778 2019.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. arXiv preprint arXiv: 703.. 008800 2017.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0830 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Large scale learning of general visual representations for transfer. arXiv preprint 19/2 2019.
11

---

Published as a conference paper at ICLR 2021
A. Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Computer Science Department, University of Toronto, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference on learning theory, pages 1246-1257, 2016.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019. URL https: htttps://openneeiee: net/ / Eorum? i SleYHoC5FX.
Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. arXiv preprint arXiv: pet.:/9055..220 2019.
Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens van der Maaten. Exploring the limits of weakly supervised pretraining. Proceedings of the European Conference on Computer Vision (ECCV), pages 181-196, 2018.
Odalric-Ambryn Maillard and Rémi Munos. Online learning in adversarial lipschitz environments. In Joint European Conference on Machine Learning and Knowledge Discovery Databuses, pages 305-320. Springer, 2010.
Wes McKinney al. Data structures for statistical computing in python. In Proceedings the 9th Python in Science Conference, volume 445, pages 51-56. Austin, TX, 2010.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning, 2019.
Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. arXiv preprint arXiv:2009.08092, 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference on Learn- ing Representations, 2020. URL https: opwpreviee.eeeeeeee net/ forum? www.ummmddllladtttt...
Behnam Neyshabur. Towards learning convolutions from scratch. arXiv preprini arXiv:2007. 2020.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. ICLR (Workshop), 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401, 2015b.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09664, 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of paramtarrattiiizaioon in generalization of neural networks. arXiv preprint arXiv:1805.12000 2018.
David Page. How train your resnet, 2018
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages
12

---

Published as a conference paper at ICLR 2021
Curran Associates, Inc., 2019. URL http:///////pppee....rro.o.oo/ap
pdf.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.1068: 2019.
Jonathan Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference on Learning Representa- lions, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 11(3))211-252, 2015. doi: 10. 1007/s 1263-015-0816-y.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chii Chich Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4520, 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Shai Shalev-Shwartz et al. Online learning and online convex optimization, Foundations and trends in Machine Learning, 4(2):107-194, 2011.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822 2878, 2018.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable ef- fectiveness of data in deep learning era. In Proceedings of the IEEE international conference computer vision, pages 843-852, 2017.
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Applications, XVI(2))264 2600000,, 1971.
Colin Wei and Tengyu Ma. Improved sample complexities for deep neural networks and robust classification via an all-layer margin. In International Conference on Learning Representations, 2019.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, al. Huggingface's 's transformers: State-of-the-ar natural language processing. ArXiv, pages arXiv-1910, 2019.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492-1500, 2017.
Lin Yang, Lei Deng, Mohammad H Hajiesmaili, Cheng Tan, and Wing Shing Wong. An optimal algorithm for online non-convex learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(2):1-25, 2018.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016.
Wide residual networks.
arXiv preprint
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
13

---

Published as a conference paper at ICLR 2021
A TOY EXAMPLE
Here we present theoretically-nssired toy example, giving a simple setting where the bootstrap gap is small, but the generalization gap is large. We also give analogous example where the bootstrap error is large. The purpose of these examples is (1) to present a simple setting where the bootstrap framework can be more useful than studying the generalization gap. And (2) to illustrate that the bootstrap gap is not always small, and can be large in certain standard settings.
We consider the following setup. Let pass regression setting, where have a distribution over (ar, y) E IR R. and we care about mean-square-error instead of classification error. That is, for a model f. we have TestMSE(f) == (x))(((x)) - y)²]. Both our examples are from the following class of distributions in dimension 1000.
x (0,
y ((3",
where 3 E Rdd is the ground-truth, and a pointwise activation function. The model family is linear,
fz(2) == (3,z)
draw n samples from the distribution, and train the model fa using full-batch gradient descent on the empirical loss:
TrainMSE(fo) = Σ((a)) - w1)²
1 -1 y/1 -yl2
chose 3 C1, and covariance to be diagonal with 10 eigenvalues of 1 and the remaining eigenvalues of 0.1. That is, is essentially 10-dimensional, with the remaining coordinates "noise."
The two distributions are instances the above setting for different choices of parameters.
Setting A. Linear activation a (xx) With 20 train samples.
Setting B. Sign activation (xx) sgn (z). With n = 100 train samples.
Setting A is standard well-specified linear regression setting. Setting B is a misspecified regression setting. Figure shows the Real and Ideal worlds these settings, for gradient-descent on the empirical loss (with step-size 7 0.1). Observe that in the well-speeified Setting A, the Ideal World performs much better than the Real World, and the bootstrap framework is not as useful. However, in the misspecified Setting B, the bootstrap gap remains small even as the generalization gap grows.
Real Ideal: Toy Setting
Real Ideal: Toy Setting
1.0
1.0
Train
Train
Real Test
Real Test
0.8
Ideal Test
0.8
Ideal Test
Test MSE
0.6
Test MSE
0.4
0.4
0.2
0.2
0.0
0.0
0
20
40
60
80
100
20
80
100
GD Iterations
GD Iterations
Figure 7: Toy Example. Examples of settings with large and small bootstrap error.
This toy example is contrived to help isolate factors important in more realistic settings. We have observed behavior similar to Setting B in other simple settings with real data, such regression MNIST/Fashion-MNIIST, as well as in the more complex settings in the body of this paper.
14

---

Published as a conference paper at ICLR 2021
B ADDITIONAL FIGURES
B.1 INTRODUCTION EXPERIMENT
Figure shows the same experiment Figure 1 in the Introduction, including the train enror in the Real World. Notice that the bootstrap error remains small, even as the generalization gap (between train and test) grows.
Real World (solid) vs. Ideal World (dashed)
MLP[5x2048]
0.8
ResNet18
ViT-B/4
Test Soft-Error
0.6
Ideal World Test
World Test
0.5
Real World Train
0.3
0.1
10000
15000 20000
30000 35000 40000
SGD Iterations
Figure 8: The corresponding train soft-errors for Figure 1.
B.2
DARTS ARCHITECTURES
Figure 9 shows the Real vs Ideal world for trained random DARTS architectures.
Real Ideal World: DARTS
Real vs. Ideal World: DARTS
0.40
0.25
0.25
Ideal Soft-Er Error
0.35
0.20
Ideal Ideal Soft-Error
0.22
0.20
Train Error
0.30
0.20
0.15
0.18
0.10
0.10
0.20
0.16
0.05
0..05
0.15
0.14
0.2
0.3
0.125
0.150 0.175 0.200 0.225 0.250 Real Soft-Error
Real Soft-Error
(a) All architectures.
(b) High accuracy architectures.
Figure 9: Random DARTS Architectures. Panel (b) shows zoomed view of panel (a).
B.3 EFFECT OF DATA AUGMENTATION
Figure 10 shows the effect of data augmentationnn in the Ideal World, for several selected architectures on CIFAR-5m. Recall that data augmentation in the Ideal World corresponds to randomly augment- ing each fresh sample once, opposed to augmenting the same sample multiple times. We train with SGD using the same hyperparameters as the main experiments (described in Appendix D.2). We use standard CIFAR- 10 data augmentation: random crop and random horizontal flip.
The test performance without augmentation is shown as solid lines, and with augmentation as dashed lines. Note that VGG and ResNet do not behave differently with augmentation, but augmentation significantly hurts AlexNet and the MLP. This may be because VGG and ResNet have global spatial pooling, which makes them (partially) bhift-invariant, and thus more amenable to the random crop- ping. contrast, augmentation hurts the architectures without global pooling, perhaps because for these architectures, augmented samples appear more out-of-distributiin..
15

---

Published as a conference paper at ICLR 2021
Effect of Data-Aug in Ideal World
alexnet
0.8
MLP[3X2048]
resnet18
0.7
vggl1_br bn
(with data-aug)
0.6
Test Soft- Soft-Erra Error
0.4
0.3
0.1
0.0
5000
10000
15000 20000 25000 30000 35000 40000
SGD Iterations
Figure 10: Effect of Data Augmentation in the Ideal World.
Figure 1la shows the same architectures and setting Figure but trained without data augmenta- tion. That is, we train on 50K samples from CIFAR-5m, using SGD with cosine decay and initial learning rate (0.1, 0.01, 0.0013.
Figure 1lb shows learning curves with and without data augmentation of ResNet-18 18 on = 10k: samples. This is the analogous setting Figure 5a in the body, which is for 50k samples.
Real vs. Ideal Worlds (no data aug)
Real vs Ideal: Effect of Data Aug
y=x
No Data Aug
MLP[3x128]
With Data Aug
MLP[3x2048]
0.7
Ideal Worlds
Ideal Soft-Eror
0.5
ResNet18
Test Soft- Soft-Eroo Error
0.6
Train
alexnet
0.5
densenet40
densenet40_8
0.4
mCNN
0.3
0.3
vggl1_bn
0.2
0.2
0.4
0.6
2000
4000
6000
Real Soft-Error
SGD Iterations
(a) No Data-augmenntatin. Compare to Figure 2.
(b) ResNet-18 18 on 10K samples.
Figure 11: Effect of Data Augmentation.
B.4 ADAM
Figure 12 shows several experiments with the Adam optimizer (Kingma and Ba, 2014) in place of SGD. We train all architectures on 50K samples from CiFAR-5m, with aata-augmentttiinn, batchsize 128, using Adam with default parameters (Ir=0.001, 3 = 0.9, B2 0.999).
B.5 PRETRAINING
B.5.1 PRETRAINED MLP
Figure 14 shows the effect of pretraining for an MLP (3x2048) on CIFAR-5m, by comparing training from scratch (random initialization) training from ImageNet- pretrained pretriedddre initialization. The pretrained MLP generalizes better in the Real World, and also optimizes faster in the Ideal World. We fine tune on 50K samples from CIFAR-5m, with data-augmentation.
16

---

Published as a conference paper at ICLR 2021
Real World (solid) vs. Ideal World (dashed)
Real vs. Ideal Worlds: Adam
0.9
MLP[3x2048]
0.45
y=x
VGG-11
0.40
resnet18
ResNet18
resnet34
Test Soft-Error
Ideal Worlds
Soft Error
0.35
densenet40_2
Train
densenet40_1
0.5
0.30
vgg11_bn bnn
0.4
0.25
myrties
0.3
alexnet
0.20
MLP(3x2048)
0.2
MLP[3x128]
0.15
0.1
0.10
10000
20000
30000
40000
0.1
0.2
0.3
0.4
Adam Iterations
Soft-Error
(a) Real vs. Ideal learning curves.
(b) Real vs. Ideal world at the end of training.
Figure 12: Adam Experiments. For various architectures on 50K samples from CIFAR-5m.
For seaageNet-pretraiin Adam with default settings, and batchsize 1024. We use standard ImageNet data augmentation (random resized crop + horizontal flip) and train for 500 epochs. This MLP achieves test accuracy 21% % and train accuracy 30% on ImageNet. For fine-tuning, we adapt the network to 32px input size by resizing the first layer filters from 224x224 32x32 via bilinear interpolation. We then replace the classification layer, and fine-tune the entire network on CIFAR-5m.
train the MLP[3x2048] on full ImageNet (224px, 1000 classes), using
B.5.2 PRETRAINED VISION TRANSFORMER
Figure shows the effect pretraining for Vision Transformer (ViT-B/4). We compare ViT-B/4 trained from scratch to training from an ImageNet- Figure 13 indicates the pretraining strategy, and the weight of the line indicates the measurment (Ideal World test error, Real World test error, or Real World train error). We fine tune on 50K samples from CIFAR-5m, with standard CIFAR-10 10 data augmentation. Notice that pretrained ViT generalizes better in the Real World, and also optimizes correspondingly faster in the Ideal World.
initialization. The color of line in
Effect Pretraining: VIT-B/4
0.9
VIT-B/4 (Random Init)
0.8
VIT-B/4 (ImageNet Pretrain)
0.7
Ideal World Test
Test Soft-Erro
0.6
Real World Test
Real World Train
0.5
0.4
0.3
0.2
0.1
0.0
0
5000
10000 15000 20000 25000 30000 35000 40000
SGD Iterations
Figure 13: Real vs. Ideal Worlds for Vision Transformer CIFAR-5m, with and w/o pretraining.
Both VIT models are fine-tuned using SGD identical to Figure 1 in the Introduction, described in Section D. For ImageNet pretraining, we train on ImageNet resized to 32 x 32, after standard data augmentation. We pretrain for 30 epochs using Adam with batchsize 2048 and constant learning rate le-4. We then replace and zero-initialize the final layer in the MLP head, and fine-tune the full model for classification CIFAR-5m. This pretraining process it not extensive in Dosovitskiy et al. (2020); we use to demonstrate that our framework captures the effect of pretraining in various settings.
17

---

Published as a conference paper at ICLR 2021
Real vs Ideal: Effect of Pretraining
Real vs Ideal: Effect of LR Drop
0.9
Random
Real Test
0.8
0.8
Pretrained Init
Real Train
0.7
Ideal Worlds
0.7
Ideal Test
Test Test Soft-Erro
0.6
Train
0.6
SoftError
0.5
0.5
0.4
0.4
0.3
0.3
0.1
0.1
10000
20000
30000
40000
5000
10000
15000
20000
SGD Iterations
SGD Iterations
Figure 14: ImageNet- MLP[3x2048J.
Figure 15: Effect of Learning Rate Drop.
B.6 LEARNING RATE
Figure 2a shows that the Real and Ideal world remain close across varying initial learning rates. All of the figures in the body use cosine decay learning rate schedule, but this is only for simplicity; we observed that the effect of various learning rate schedules are mirrored in Real and Ideal worlds. For example, Figure 15 shows a ResNet18 in the Real World trained with SGD for 50 epochs on CIFAR-5m, with a step-wise decay schedule (initial LR 0.1, dropping by factor 10 at 1/3 and 2/3 through training). Notice that the Ideal World error drops correspondingly with the Real World, suggesting that the LR drop has similar effect the population optimization as it does the empirical optimization.
B.7 DIFFERENCE BETWEEN WORLDS
Figure 16 shows test sofor test error, and test loss for the MLP from Figure 1.
Real Ideal: SoftError
Real Ideal:
Real Ideal:
Real Train
0.0
Real Train Ideal Test
0.7
Ideal Test
0.7
0.6
0.6
1.0
Softrmor
0.8
0.4
0.6
0.3
0.3
0.4
0.2
0.2
0.2
Real Train
Ideal Test
0
10000
20000
30000
40000
0
10000
20000
30000
40000
0
10000
20000
30000 40000
SGD Iterations
SGD iterations
SGD Iterations
Figure 16: SoftError vs. Error vs. Loss: MLP(5x2048).
B.8 ERROR VS. SOFTERROR
Here we show the results of several of our experiments we measure the bootstrap gap with respect Test Error instead of SoftError. The bootstrap gap often reasonably small even with respect to Error, though it is not as well behaved as SoftError.
Figure 17 shows the same setting as Figure 2a in the body, but measuring Error instaed of SoftError.
B.8.1 TRAINING WITH MSE
We can measure Test Error even for networks which do not naturally output probability distribu- tion. Here, we train various architectures on CIFAR-5m using the squared-loss (MSE) directly on logits, with no softmax layer. This follows the methodology in Hui and Belkin (2020). We train all Real- World models using SGD, batchsize 128, momentum 0.9, initial learning rate 0,002 with cosine decay for 100 epochs.
18

---

Published as a conference paper at ICLR 2021
Real vs. Ideal Worlds
y=x
0.5
resnet18
resnet34
vgg16
Ideal Error
0.4
vggl1_br
myrtles
0.3
densenet40 32
densenet40
0.2
alexnet
MLP[3x2048]
MLP[3x128]
0.1
0.1
0.2
0.3
0.4
0.5
Reall Error
Figure 17: Measuring Test Error instead of SoftError. Compare to Figure 2a
Figure 18 shows the Test Error and Test Loss in the Real and Ideal Worlds. The bootstrap gap, with respect to test error, for MSE-trained networks is reasonably small though there are deviations in the low error regime. Compare this to Figure 2a, which measures the SoftError for networks trained with cross-entropy.
Real Ideal World Error (MSE-trained)
Real vs. Ideal World Loss (MSE-trained)
y=x
0.5
y=x
0.35
resnet34
resmet34
resnet18
resnet18
0.30
vgg16
0.4
vgg16
Ideal Error
vgg11 bn
vggll_br bnn
0.25
densenet40 32
Ideal MSE
densenet40
alexnet
alexnet
0.20
denserete40_1
12
densemet40 12
MLP[3x2048)
MLP[3x2048)
0.15
MLP[3x128]
0.2
MLP(3x128)
0.10
Real Error
Real MSE Loss
(a) Test Error.
(b) Test Loss.
Figure 18: Real vs. Ideal: Training with Squared Loss.
19

---

Published as a conference paper at ICLR 2021
C BOOTSTRAP CONNECTION
Here we briefty describe the connection between our Deep Bootstrap framework and the nonpara- metric bootstrap of Efron (1979).
For an online learning procedure F and sequence of labeled samples {z; let Train (x) 22....) denote the function which optimizes on the samples ø1, T2,-.. in sequence, and outputs the resulting model. (For example, the function which initializes network of certain architecture, and takes successive gradient steps on the sequence of samples, and outputs the resulting model).
For given (n, D, t), define the function G X I follows. G takes input labeled samples } and outputs the Test Soft-Error (w.r.t D) of training on the sequence {zi That is,
G( 22, 24) TestSoftErrooo (Train (#1, 22, .2,...,
Now, the Ideal World test error is simply G evaluated on iid samples D:
Ideal World: (=s = G((x,)) where D
The Real World, using train set of size n < t, is equivalent' to evaluating G' on examples sampled with replacement from train of size n. This corresponds training on the same sample multiple times, for f total train steps.
Real World: TestSoftErrorp(f) = G((E)) where S~ D'
Here, the samples म; are drawn with replacement from the train S. Thus, the Deep Bootstrap error G(( G((x;)) measures the deviation of certain function when it is evaluated on samples v.s. on
which is exactly the form of bootstrap error in applications of the nonparametric bootstrap (Efron, 1979; Efron and Tibshirani, 1986; 1994).
'Technically we do not sample-wine healle-wthh-rppaeemeee in the experiments, we simply reuse each sample a fixed number of times (once in each epoch). We describe it it to the nonparametric hootstrap.
here to more clearly relate
20

---

Published as a conference paper at ICLR 2021
D APPENDIX: EXPERIMENTAL DETAILS
Technologies. All experiments run NVIDIA VI00 GPUs. We used PyTorch (Paszke al., 2019), NumPy (Harris et al., 2020), Hugging Face transformers (Wolf et al., 2019), pandas (McKinney al., 2010), W&B (Biewald, 2020), Matplotlib (Hunter, 2007), and Plotly (Inc., 2015).
D.1 INTRODUCTION EXPERIMENT
All architectures in the Real World are trained with n = 50K samples from CIFAR-5m, using SGD on the cross-entropy loss, with cosine learning rate decay, for 100 epochs. We use standard CIFAR- 10 data augmentation of random crop+horizontal flip. All models use batch size 128, so they see the same number of samples at each point in training.
The ResNet is a preactivation ResNet18 (He et al., 2016b), the MLP has 5 hidden layers of width 2048, with pre-activation batch norm. The Vision Transformer uses the ViT-Base configuration from Dosovitskiy et al. (2020), with a patch size of 4 x 4 (adapted for the smaller CIFAR-10 10 image size of 32 x 32). We use the implementation from ht https: / thub. com/ luci drains// vit ppttorc. We train all architectures including ViT from scratch, with no pretraining. ResNets and MLP initial learning rate 0.1 and momentum 0.9. ViT uses initial LR 0.01, momentum 0.9, and weight decay le-4. We did not optimize ViT hyperparameters as extensively as in Dosovitskiy al. (2020); this experiment only demonstrate that our framework is meaningful for diverse architectures.
Figure plots the Test Soft-Error over the course of training, and the Train Soft-Error the end of training. We plot median over 10 trials (with random sampling of the train set, random initialization, and random SGD order in each trial).
D.2 MAIN EXPERIMENTS
For CIFAR-5m we use the following architectures: AlexNet (Krizhevsky et al., 2012), VGG (Si- monyan and Zisserman, 2015), Preactivation ResNets (He et al., 2016b), DenseNet (Huang et al., 2017). The Myrtle5 architecture is 5-layer CNN introduced by (Page, 2018).
In the Real World, we train these architectures cross-entropy loss. All models are trained with SGD with batchsize 128, initial learning rate {0.1, 0.01, 0.001}. cosine learning rate decay, for 100 total epochs, with data augmentation: dom horizontal flip and RandomCrop (32, paddi 4g=4). We plot median over 10 trials (with random sampling of the train set, random initialization, and random SGD order in each trial).
50K samples from CIFAR-5m using
DARTS Architectures. We sample architectures from the DARTS search space (Liu et al., 2019), implemented in the codebase of Dong and Yang (2020). We follow the parameters used for CIFAR- 10 in Dong and Yang (2020), while also varying width and depth for added diversity. Specifically, we use 4 nodes, number of cells E 51, and width E {16, 64). We train all DARTS architectures with SGD, batchsize 128, initial learning rate 0.1, cosine learning rate decay, for 100 total epochs, with standard augmentation (random crop+flip).
are trained with SGD, batchsize 128, learning rate 0.01, momentum 0.9, for 120 epochs, with standard ImageNet data augmentation (ran- dom resized crop to 224px, horizontal flip). We report medians over 10 trials for each architecture.
NetgeNet: DogBird All architectures for ImageNet-Dogle
We additional include the ImageNet architectures: BagNet (Brendel and Bethge, 2019), MobileNet (Sandler et al., 2018), and ResNeXt (Xie et al., 2017). The architectures SCONV9 and SCONV33 refer to the S-CONV architectures defined by Neyshabur (2020), instantiated for ImageNet with base-width 48, image size 224, and kernel size (9, 33) respectively.
D.3 IMPLICIT BIAS
We use the D-CONV architecture from (Neyshabur, 2020), with base width 32, and the correspond- ing D-FC architecture. PyTocch specification of these architectures are provided in Appendix F for convenience. We train both architectures with SGD, batchsize 128, initial learning rate 0.1, cosine
21

---

Published as a conference paper at ICLR 2021
learning rate decay, for 100 total epochs, with random crop + horizontal flip data auttenagmmnttiion. We plot median errors over 10 trials.
D.4 IMAGE-GPI GPT FINETUNING
We fine-tune iGPT-S, using the publicly available pretrained model checkpoints from Chen et al. (2020). The "Early" checkpoint in Figure 5b refers to checkpoint 131000, and the "Final" check- point is 1000000. Following Chen et al. (2020), we use Adam with (Ir 0.003, 81 0.9, 82 0.95), and batchsize 128. We do not use data augmentation. For simplicity, we differ slightly from Chen et al. (2020) in that we simply attach the classification head to laverage-pooled] last transformer layer, and we fine-tune using only classification loss and not the joint genera- tive+classification loss used Chen et al. (2020). Note that we fine-tune the entire model, not just the classification head.
22

---

Published as a conference paper at ICLR 2021
E APPENDIX: DATASETS
E CIFAR-5M
CIFAR- 5m a dataset of 6 million synthetic CIFAR-IO-like images. We release this dataset publicly on Google Cloud Storage, as described in
pmntt/reeuum////m c far
The images are RGB ative model of Ho et al. (2020) trained on the CIFAR-10 train set (Krizhevsky, 2009). We use the publicly available trained model and sampling code provided by the authors at https: //gi thub. com/ hoom/hofe www.jjanathaooooooooo fameho//difuuus fus on. We then label these unconditional samples by 98.5% accurate fig-Transfer model (Kolesnikov et al., 2019). Specifically, we use the pre- trained BiT-M-R 152xx model, fine-tuned on CIFAR- 10 using the author-provided code at https: / //githab. com/ hon/googgee wesearcch/ble wwwpaarhhaagttaaaaaaaaaaaa trnssfe.... use 5 million images for training, and reserve the remaining images for the test set.
32px. We generate samples from the Denoising Diffusion gener-
The distribution of CIFAR-5m is of course not identical to CIFAR-10, but is close for research purposes. For example, we show baselines of training network on 50K samples of either dataset (CIFAR-5m, CIF,R-10), and testing on both datasets. Table shows a ResNet18 trained with standard aata-auumeenttiion, and Table 2 shows WideResNer28-I1 10 (Zagoruyko and Komodakis, 2016) trained with cutout augmentation (De Vries and Taylor, 2017). Mean of 5 trials for all results. In particular, the WRN-28-10 10 trained on CIFAR-5m achieves 91.2% test accuracy on the original CIFAR-10 10 test set. We hope that as simulated 3D environments become more mature (e.g. Gan et al. (2020)), they will provide a source of realistic infinite datasets use in such research.
Random samples from CIFAR-50 5m are shown in Figure 19, For comparison, we show random sam- ples from CIFAR-10 in Figure 20.
Trained On
Test Error On
Trained On
Test Error On
CIFAR-10
CIFAR-5m
CIFAR-10
CIFAR-5m
CIFAR-10
0.050
0.096
CIFAR-10 CIFAR-5m
0.032 0.088
0.091
CIFAR-5m
0.110
0.106
0.097
Table I: R on CIFAR-10/5m
Table 2: WRN28-10 + cutout on CIFAR-10/5m
E.2 IMAGENET: DOGBIRD
The ImageNet-DogBird task is constructed by collapsing classes from ImageNet. The task is to distinguish dogs from birds. The dogs are all ImageNet classes under the WordNet synset "hunting dog" (including 63 ImageNet classes) and birds are all classes under synset "bird" (including 59 ImageNet classes). This is a relatively easy task compared to full ImageNet: on 10K samples from ImageNet- ImageNet-DogBird, with standard ImageNet data augmentation, test accuracy 95%. The listing of the ImageNet wnids included in each class is provided below.
ResNet-18 18 trained achieve
Hunting Dugs (n2087122): n02091031, R02097047, n02080364, n02094633, no2097658, n32089070, n02390622, m02095314,
aC2102040, a02097133, a0209605L, a02098105, D02C95E83, ad2100235, n02099267, #02102318, 602097474, 602C90721, 222162915, 202095370, 282091635, 202059429, n02C90379, 20209<258, n02100593, =02092002, n02053428, n02c99413,
nc209 1298, 502093154, nu20961 76, n02051032, n02096436, n02081394, nu2092339, 102093/12, n02088631, n02093661,
5C2098286, 202096585, 202093991, 502100877, s0209(116, 202101388, n02089973, 002083C94, n02089466, 002C93853,
aC2088228, 202102493, a02101536, 202089867, n02c99601, n02102177, n02101005, 502091136, 502100735, n02C99869,
262093256,
/2099/209, 002091465, n02091244, n02c96294
Binds
(n1503661):
n31855679, 5015604'9, n02009229, n01614925, nd1 530515, n01799484, n02007558, n01 860187,
nc1820506, n01817953, a01833803, 202058221, n01806567, 201558993, n02056570, 5017978B5, n02018207, n01828970,
aC2017213, 002006636, a01608432, n01618515, 002C19795, n01622779, n01502220, 002013705, n01536433, D02027492,
aC2012849, n02051845, a01824575, ab1516318, n82002556, n01819313, n01806143, n00003344,, nB1501694, r00164388,
aC2025239, a02002724, a01843065, ab1514859, 001796340, a01855032, n01580077, s01807495, n01847020, n01532829,
n61527596, n01531179, n0203:110, n01514568, n02028035, n01795595, n01592084, n01518878, n01829415, n02009912,
RC2011460
23

---

Published as a conference paper at ICLR 2021
Figure 19: CIFAR-5m Samples. Random samples from each class (by row).
24

---

Published as a conference paper at ICLR 2021
Figure 20: CIFAR-10 Samples. Random samples from each class (by row).
25

---

Published as a conference paper at ICLR 2021
wire-haired fox terrier
nonwich terrier
nonaegian elkhound
lhasa
basset
brittany spaniel
english springer
german short haired pointer
english springer
gordon, setter
silky terrier
cocker spaniel
jacama
great grey ow!
bald eagle
goose
albatross
humminggird
ptarmigan
water ouzel
hummingbird
european gellinule
egret
Figure 21: ImageNet-DogBiin Samples. Random samples from each class. Annotated by their original ImageNet class for reference.
26

---

Published as a conference paper at ICLR 2021
F D-CONV, D-FC ARCHITECTURE DETAILS
For convenience, we provide PyTorch specifications for the D-CONV and D-FC architectures from Neyshabur (2020) which we use in this work.
D-CONV. This model has 6563498 parameters.
Network(
(features): Sequential
(0): Conv2d (3, 32, kernel_size= (3, 3), stride= (1, 1), padding= (1, 1)
bias=False)
(1): BatchNorm2d (32, eps=le-05, momentum=0.1, affine=True)
(2) ReLJ(inplace-
(3): C3nv2d(32, 64, kernel size (3, 3), stride (2, 2), padding (1, 1)
bias=False)
(4) BatchNorm2d eps=le-05, momentum=0.1, affine=True)
(5) (eleeinglaee=-rue)
(6) Conv2d 64, kernel_size=08 (3, 3), stride= (1, 1), padding= (1, 1)
bias=False)
(7) Batchhorm22 eps=le-05, momentum=0.1, affine-True)
(8) ReLJ Rell(inplace-True)
(9) Conv2d 128, kernel Bernel_size=(3, 3), stride= (2, 2), (odding=(1, 1)
bias=False)
(10) BatchNorm22d122 (128, eps-le-05, uomentum=0.1. affine-True)
(11) (e1l((nnpaae--Tue)
(12) Conv2a(128, 128, kernel_size= (3, 3), stride= (1, 1), padding=(1, 1)
bias=False)
(13) BatchNorm2d eps=1e-05, momentum=0.1, affine=True)
(14) Renlainneee-=
(15) Conv2d 256, pernel_size=t 3), stride= (2, 2), padding= (1, 1)
bias=False)
(16) BatchNorm2dd255, eps-1e-05, momentum-0.1. affine-True)
(17) Reld([nplace==Tue)
(18) : Conv2d(256, 256, kernel sinel_size=(13 3), stride= 1), padding= 1)
bias-False)
(19) BatchNormm2d(55,, eps=1e-05, momentum=0.1, affine=True)
(20) Rel0/(nnpace=-rue)
(21): Conv2d(256, 512, kernel_size- (3, 3), stride= (2, 2), padding= (1, 1)
bias-False)
(22) (512, eps=1e-05, momentum=0.1, affine=True)
(23) (inlaaceTrr))
(classifier): Sequential
(0) Linear (1_aaarri__fatturee==2200 out fut_feeature=2043
bias=False)
(1) BatchNormid eps=le-05, momentun=0.1, affine-True)
(2): ReLU Ritl
(3): : Dropout inplace=Fasse)
(4): Linear (in__eatuuree--2004 out_featurrs=10, bias-True)
D-FC. This model has 1170419722 parameters.
Network (features): Sequential
(0): Linear fdn_featuree=3072, out_ fettfuuuuree=2255,, bias=False)
(1): Batchhorrldd327688, eps=le-05, momentum=0.1, affine=True
(2): : (inpaaaeee))))
(3): : Linear (ieariin_fetureees22222
out__faature=-1684, 63884, bias=False)
27

---

Published as a conference paper at ICLR 2021
(4) (1tchNormldd16384, eps=1e-05, momentum=0.1, affine=True)
(5) : (iLU(innaace==rrue))
(6) Lineur((h__fotuures=111138 out out_feattue--16384, bias=False)
(7): : (atchhoormld116384,, eps=1e-05, 05, momentum=0.1, affine=True)
(8) Reti((nnaaac==TTru))
(9) Linear(in_ffatturee-13333. fut_feaaures-8192, bias-False)
(10): BatchNoozmld(11922 -p
eps-le-05,
momentun-0.1, affine-True)
(11) Relld(Linplacce=IIzze)
(12) Lineartin__fatuure====122, out_features=8192, bias=False)
(13) BatchNoomlld(8122, O,
0 affine=True)
(14) Reilo((inpllac===Trre)
(15) (inesr(inn_eetttre==8122 out_festures=4096, bias=False)
(16) BatcchNo:m14(4096, -ps- mo affine=Irue)
(17) Reld(innplace-Irue)
(18) Linear(in__feeturee==00000 out_
out_features==496, bias=False)
(19) : BatchNo:mmdd(096,, ep=--- 0 1, affine=True)
eps=1e-05,
(20) Reild(inpplac==True))
(21): Linear(in_feattrre==0000 out_feature==2048, bias-False)
(22): BatchNoomldd22488 05, momentun=0.1, affine=True)
(23): (e10(innpa))=TTru)
(classifier): (
(0): (inaarrin__faatuuee==223
2etffeatures=2088, bias=False)
(1): BatchNormld eps=le- 05, momentum=0.1. affine-True)
(2): ReLU ReLJ(inplace=TTue)
(3): pp=pout inplace=False)
(4): Linear (in features=2048,, out features=10, bias=True)
28


Reviews:
[{"review_id": "xJ21Na-pLTH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "######################################################################\n\n1.  Paper Summary \n\nThe authors propose a bootstrap framework for understanding generalization in deep learning.  In particular, instead of the usual decomposition of test error as training error plus the generalization gap, the bootstrap framework decomposes the empirical test error as online error plus the bootstrap error (the gap between the population and empirical error).  The authors then demonstrate empirically on variants of CIFAR10 and a subset of ImageNet that the bootstrap error is small on several common architectures.  Hence, the empirical test error is controlled by the online error (i.e. a rapid decrease in the error in the online setting leads to low test error).  The authors then provide empirical evidence to demonstrate that same techniques perform well in both over and under-parameterized regimes.  \n\n######################################################################\n\n2. Strengths\n\n2.1. The bootstrap framework presented for understanding generalization is novel to the best of my knowledge and provides an interesting connection between optimization in online learning and generalization in offline learning.  \n\n2.2. When the bootstrap error is low, the bootstrap framework implies that understanding generalization reduces to understanding optimization in the online setting.  This perspective provides an alternative to characterizing the implicit bias of deep networks when explaining generalization in deep networks.  \n\n2.3. The authors present significant empirical evidence that the bootstrap error (in terms of soft error) is consistently low in image classification settings across a number of architectures.   \n\n######################################################################\n\n\n3. Concerns\n\n3.1. While at first this framework serves as a very appealing alternative to the classical decomposition, the fact that the bootstrap error is low seems heavily reliant on the soft-error only found in the classification networks using a softmax on the outputs.  In particular, the authors focus on the soft-error in their decomposition throughout the work, but in Appendix A and in section 6, it appears that the MSE/cross entropy loss produce a significant bootstrap gap.  At first, this may seem innocuous, but if this bootstrap gap is low only for soft error, this would imply that we need to then focus on understanding how quickly the population soft error decreases, which to the best of my knowledge is a very different object of study in optimization than the MSE or cross entropy loss.  \n\n3.2.  In light of the previous point, I feel that the following experiment could help solidify whether the bootstrap error is indeed low for convolutional networks used for classification. When using the square loss for classification as is done in (https://arxiv.org/abs/2006.07322) (for example on the CIFAR10 setting), is the bootstrap error still low or is the bootstrap error being low really only a side effect of measuring soft-error? This experiment should resolve the authors' claim with the gap in Figure 6c being large due to unbounded weights when minimizing the empirical loss.  \n\n3.3. (Minor) I have a hard time understanding how strong some of the claims are in the paper.  In particular, the authors claim a main implication as \"The same techniques [...] are used in practice in both over- and under-parameterized regimes.\"  Do the authors mean to claim that a technique that is successful in the over-parameterized regime is also successful in the under-parameterized regime? They do state this in briefly on page 6, but it seems to be claimed less strongly in the introduction.  Additionally, in light of the fact that there are cases where the bootstrap error is high, the claim that \"the generalization of models in offline learning is largely determined by their optimization speed in online learning\" may need to be more precise.\n\n######################################################################\n\n4. Score and Rationale\n\nOverall, I currently vote for rejecting. However, my decision is borderline.  In particular, while I find the authors' bootstrap framework appealing in that it could nicely connect generalization and optimization, I am concerned about the results relying heavily on the soft-error (especially since the softmax activation is not necessary for deep networks to perform well on test data).  I am definitely open to changing my review provided that the authors are able to address my concerns about the soft-error above.  \n\n######################################################################\n\n\n5. Questions \n\nPlease clarify the questions listed in the concerns section above.  \n\n######################################################################\n\n6. Post-rebuttal Updates\n\nIn light of the authors new experiments and response, I have increased my score.  The bootstrap error shows slight deviations under the MSE, and thus, I do feel that the scope of generality of this work is still limited.  However, I feel that the presented framework is novel and the experiments consistently demonstrate that the bootstrap error is consistently low under soft-error in a number of settings.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "oOC3cvQAMHU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper defines a metric of generalization gap between the ideal world and real-world via 'bootstrap approximation', and seeks to use his gap to explain some phenomena.\n\nAlthough I have respect for this paper trying to define some statistical terms in the deep learning society, I have a very strong concern about the novelty, as it appears to be whether trivial or hard to understand. For example, I could relate to the empirical finding that bootstrap error defined in claim 1 is uniformly small, but I personally believe that the 'TestSoftError' defined in 3 should dominate the generalization error and the paper circumvents this term to study some term that is way non-significant, especially considering how the datasets are built around CIFAR or DOG-bird, via simple data augmentation that is frequently used in vision society. The problem being mentioned in the paper, i.e. 'Most if not all techniques for understanding the generalization gap (e.g. uniform convergence, VC-dimension, regularization, stability, margins) remain vacuous', appears to be not tackled at all in this paper, which, in its main effort, to discuss generalization.\n\nSection 5 says some practical suggestions to train deep networks, which seem to be not persuasive, especially that the ideal world error might be harder to measure than that in the real world, according to the paper. On top of this, why these factors such as sample size, model selection, are not to be tuned even better if that were through the lens of other metrics, such as gradient norms, validation error, etc.", "extra_scores": {}, "extra_text": {}}, {"review_id": "aL1FzVAOrcx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies generalization through a novel \"bootstrap\" framework relating the test loss from training on a finite fixed training set to the loss when training on fresh samples at each iteration. The framework is quite novel and suggests alternative perspectives on understanding empirical phenomena such as the success of overparametrization, data augmentation, and implicit biases. \n\nPositives:\n- The paper is clearly written\n- The empirical bootstrap phenomenon is very interesting and the experimental results are quite surprising.\n\nCons:\n- The paper could benefit from some more prominent discussion of settings where the bootstrap error is small vs large. It was briefly mentioned in this sentence in the conclusion: \" The bootstrap error is not universally small for all models and\nlearning tasks: for example, we found the gap was larger at limited sample sizes and without data\naugmentation. \" Space permitting, it would be helpful and more convincing if more details were provided about settings where the bootstrap error could be large. \n- The choice of soft error to compute the bootstrap error seems somewhat ad-hoc, especially for the datasets studied where the Bayes optimal risk is presumably quite low. For example, it seems like ImageNet-DogBird should be quite easy to separate unambiguously. \n\nSome other comments and questions: \n- It would be interesting to hear the authors thoughts on the feasibility of rigorously analyzing the bootstrap error. Are there any obstacles to analyzing this error that arise in the prior literature? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0-gcF18uxC", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a bootstrap framework to study the generalization problem of deep learning, by decomposing the traditional test error into an ‘Ideal World’ test error plus the gap between. Empirically, it demonstrates that such gap (soft-error) is small in supervised image classification for typical deep learning model architectures. It then proposes to explain several phenomena in deep learning using the bootstrap framework. I appreciate the authors' efforts on conducting extensive experiments related to deep learning generalization.\n\nPros:\n\n+ The proposed decomposition of test error is new to the field.\n\n+ The presented experiments are extensive, which connected to various important aspects in deep learning. \n\n\nCons:\n\n- My main concern is that the motivation of the proposed bootstrap framework is unclear. I have a hard time understanding how the proposed framework overcomes the two major obstacles of classical approaches listed in the introduction section. Why are the subproblems presented in (2) easier than the original one? \n\n- Classical generalization bounds (although can be vacuous in some scenarios) are mostly theoretically-derived, which are able to characterize the dependencies of the error term on parameters, such as input dimension, sample size and model class complexities. However, the main claim of the paper (claim 1 in Page 3) is a pure experimental claim. The paper will be much stronger, if claim 1 can be characterized theoretically with bounds on the error term (even in a simplified setting).\n\n- The implications of the proposed framework and results on how to improve the existing deep learning methods are not clear to me. Assuming the bootstrap error is always small, then how can one modify the current deep learning training method to reduce the ‘Ideal World’ test error? \n\n- Characterizing the ‘Ideal World’ test error requires a significant large amount of labeled inputs for supervised image classifications. The paper construct synthetic datasets by first generating images using an unconditional generative model, then labeling the images using a pretrained classification model. How do you guarantee the label quality for the whole generated dataset? Why not directly use a conditional generative model?\n\nMinor Comments:\n\n1. The mathematical definitions of test error and test soft error are not provided. I would recommend the authors to lay out these metrics in the main body of the paper to add clarity.\n\n\n===== Post-Discussion Update =====\n\nI appreciate the authors' efforts for responding my concerns and comments. The provided response and the update of the introduction do help better explain the motivations and the implications of the proposed generalization framework. Therefore, I raise my previous rating a little bit to reflect this. \n\nAlthough the proposed framework may suggests a potentially-interesting future direction for the deep learning research community, it still does not fully convince me its feasibility. In particular, the paper would be much stronger, if the author can dig deeper with the Real-World test (soft) error, which I view it as the end-goal of a real-world classification system, to provide more specific directions on how to make it smaller, or more importantly, how it changes the current deep learning training paradigm.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is proposing a new framework for understanding generalization in the deep learning. The main idea is considering the difference of stochastic optimization on a population risk and optimization on an empirical risk. The classical theory considers the difference of empirical risk and population risk. This basically translates the practical motivation from finding good function classes to finding good optimizers which can re-use the data effectively. Although the paper provides no theoretical result, it provides an interesting empirical study. The paper somewhat demonstrates that SGD on deep networks is somehow good at re-using the same data. I believe this angle is very novel and might hope to future theoretical discoveries. The paper is reviewed by four reviewers and two of them argue its acceptance and two of them argue rejection. After discussion, this status remained and I carefully read and reviewed the paper. Here are the major issues raised by the reviewers:

- R#1: The paper is missing a theoretical study. The implications on the practical deep learning is not clear.
- R#2: Choice of the soft-error is particular to the task and how to go beyond soft-max is not clear.
- R#3: Finds the paper not novel as well as trivial or hard to understand.
- R#4: The choice of soft error is ad-hoc.

I believe the issues raised by R#3 are not justified. First of all, novelty is very clear and. appreciated by other reviewers. Moreover, the paper is rather easy to understand and the results are very farm from trivial. However, the other issues raised by other reviewers are valid. Specifically, soft-error seems to be a limitation of the study. However, the authors respond to this concern and reviewer increases their score. I believe the theory is lacking but the paper is simply showing this novel approach and its empirical validity. A theory to explain this phenomenon would be amazing but not necessary for publication. Similarly, without a theory it is hard to expect any practical implication. Overall, I believe the paper is an interesting and novel one which will likely to lead additional work in the area. Considering we are still far from a satisfying theory of generalization for deep learning and the role of the optimization is clear, this angle worth sharing with the community. Hence, I decide to accept. However, I have some concerns which should be addressed by the camera-ready. 

- Claims should be revised and authors should make sure they have enough evidence for them. For example, authors provide no satisfying evidence for random labels or very limited evidence for pre-training. I strongly recommend authors to either remove some of these discussions or present in a fashion which is not a result but part of the discussion for future research.
- A section about limitations should be added. Specifically, the soft-error choice should be discussed in this limitation section.
- Discussion section should be extended with the pointers to the relevant work on bootstrap literature as well as suggestions to the theoreticians. Not providing any theoretical result is always fine but authors should understanding why is it hard to make theoretical statements and where to search them.
Decision: Accept (Poster)