On Optimal Early Stopping: Overparametrization versus Underparametrization
Authors: Ruoqi Shen
Liyao Gao
Yian Ma
Venue: ICLR 2022 Submitted (2022)
Keywords: Early stopping
Overparameterization
Implicit regularization
Generalization
Learning theory

Abstract: Early stopping is a simple and widely used method to prevent over-training neural networks. We develop theoretical results to reveal the relationship between optimal early stopping time and model dimension as well as sample size of the dataset for certain linear regression models. Our results demonstrate two very different behaviors when the model dimension exceeds the number of features versus the opposite scenario. While most previous works on linear models focus on the latter setting, we observe that in common deep learning tasks, the dimension of the model often exceeds the number of features arising from data. We demonstrate experimentally that our theoretical results on optimal early stopping time corresponds to the training process of deep neural network. Moreover, we study the effect of early stopping on generalization and demonstrate that optimal early stopping can help mitigate ''descent'' in various settings.

Under review as a conference paper at ICLR 2022
ON OPTIMAL EARLY STOPPING: OVERPARAMETRIZA- TION VERSUS UNDERPARAMETRIZATTIN
Anonymous authors Paper under double-blind review
ABSTRACT
Early stopping is a simple and widely used method to prevent over-training neu- ral networks. We develop theoretical results reveal the relationship between optimal early stopping time and model dimension as well as sample size of the dataset for certain linear regression models. Our results demonstrate two very dif- ferent behaviors when the model dimension exceeds the number of features versus the opposite scenario. While most previous works on linear models focus on the latter setting, we observe that in common deep learning tasks, the dimension of the model often exceeds the number of features arising from data. We demon- strate experimentally that our theoretical results optimal early stopping time corresponds to the training process of deep neural network. Moreover, we study the effect of early stopping generalization and demonstrate that optimal early stopping can help mitigate "double descent" in various settings.
INTRODUCTION
Generalization, accuracy, and computation are three of the major aspects in deploying large scale machine learning models. They are often brought together into an optimization framework, where the first two aspects concern stationary solution and the last aspect concerns convergence proper- ties of the algorithm. As a result, most previous works have analyzed them separately, seeking to strike a balance between generalization and accuracy first then understand computational complex- ity (Zhang 2002). These approaches often design a regularizer in the form of a penalty term added the objective function (c.f., Nakkiran al. 2020b and references therein). While this method is effective in many settings, it can prove challenging to determine the regularization that guaran- tees appealing behaviors. Adding to the complication the fact that they are often designed to avoid overfitting when the optimization algorithm converges. It is not obvious how the behavior will change the algorithm stops before the convergence of the optimization procedure.
Recent success of deep learning models combined with gradient based optimization has prompted increasingly many works to focus on blending the computation aspect into the picture of ceneralizationaaccuree
tradeoff (Du et al. 2018). Such approaches often leverage implicit proper- ties of the optimization algorithms in conjunction of the model and the data structures and are thus referred to as implicit regularization methods. In training of deep neural networks, techniques such as stochastic gradient descent, batch normalization (Toffe & Szegedy) (015)), and dropouts (Srivas- tava al. 2014) widely used to grant generalization properties implicitly.
In this paper, we study regularization via early stopping (Morgan & Bourlard, 1989 Zhang & Yu 2005 Yao et al. 2007). While in practice, early stopping often forced by computational budget constraints, we focus on its efficacy in avoiding overfitting towards the training dataset. In the presence of label noise, in particular, we study the common strategy of concluding the training process at the optimal early stopping time, which achieves the lowest test risk before it increases again. One crucial question is how this optimal early stopping time relates to the model size and sample size. Answering this question not only provides guidance for the model training process in practice, but also contributes to the understanding of the generalization property of different models.
A Conundrum Optimal Early Stopping (Ali et al. 2019) studied the regularization effect of carly stopping on least square regression, but did not provide explicit characterization of the optimal early stopping time with respect to the model and data complexity. As first step,

---

Under review as a conference paper at ICLR 2022
Optimal early stopping time
dfer 100
width width 20
Optinal early stapping
Empirical bounds
Toating Enor
width 60
700
600
2000
500
P 10
Empirical bounds
10
20
30
40
50
80
10a
10a
10a
10*
15
Mudel midth
Model size
Figure 1: Left: Optimal early stopping time vs. model width for CIFAR-100 100 with 20% label noise trained using ResNet networks with convolutional layers of widths (d. 2d, 4d, 8d]. Right: Testing error vs. time for CIFAR-100 with 20% label noise trained using ResNet networks using different model widths.
Figure 2: Optimal early stop- ping time vs. hidden layer width trained using two-layer ReLU networks generated points of = 10 clus- ters with 20% label noise.
randomly
compute the optimal early stopping time of the model studied (Ali et al. 2019) and discover that under the setting adopted therein, the optimal early stopping time increases along with the model size. However, this trend is contrary to what we observed in traning neural networks. We observed that when training popular datasets such MNIST, CIFAR-10/100 using deep neural networks, the optimal early stopping time decreases as the model size increases (see Figure [ These two contradicting trends indicate that previous theoretical models not sufficient to explain what happens in practice.
Overparametrization vs. Underparamettization We noticed that despite the huge models used to train those datasets, their labels are actually generated by low dimensional representations or features (See Section 4.2). Previous theoretical works have primarily focused on the case where the model dimension is approximately the same or less than the number of features instead of the opposite scenario (Ali et al., 2019 Belkin et al.) 2020 Nakkiran et al., 2020b). To complete the missing pieces in previous analyses, we propose new model where the label is generated by low-dimensional transformation of the input data. We define the case where the model size is larger than the number of features as being overparametrized. We verify experimentally that this overparametrized case better reflects what happens in training neural networks. This new over- parametrization setting demonstrates very different behavior from the previous theoretical model, which resolves the contradiction we previously observed.
We illustrate both theoretically and experimentally that the optimal stopping time behaves very dif- ferently when the number of features smaller (overparametrization)) or larger (underparametriza- tion) than the model size. In the overparametrization setting, the optimal early stopping time de- creases as the model dimension increases or the sample size decreases, similar to what we observe when training deep neural networks for image classification tasks. On the other hand, in the under- parametrization setting, the optimal early stopping time increases as the model dimension increases or as the number of samples increases. We corroborate experimentally that these trends persist when training various linear models and neural networks (e.g., Figure
Generalization of the early stopped-modek Even for the same model, stopping at the optimal early stopping time versus after the training converges can lead to solutions with very different generalization properties. Another problem we study how the test risk of models changes as a function of other training parameters when stopped at the optimal early stopping time. In particular, has been shown that without regularization, the test risk can exhibit the so-called "double descent" phenomenon (Belkin et al., 2018 Nakkiran et al.) (020a),, where the risk function of model size or sample size experience two distinct phases of descent. This phenomenon can make deciding the best model parameters challenging. We demonstrate that early stopping helps mitigate double descent in multiple settings.
1.1 RELATED WORKS
The test risk of simplified machine learning models has been studied in long line works. A par- tial list of papers that studied linear models similar to ours includes (Bartlett al.) 2020 Chen al.
2

---

Under review as a conference paper at ICLR 2022
2020a
Dobriban et al. 2018 Hastie et al. 2019: Montanari et al. 2019 Mitra 2019 Muthukumar
ct al.
2020)
Regularization is widely used in training machine learning models to prevent overfitting (Dobriban
ct al.
2018 Dobriban & Sheng 2020 Hastic ct al., 2019 Kobak et al. 2020 Mei & Montanari Nakkiran et al. 2020b) studied the test risk of ridge regression. In addition, lot of recent
2019
works studied the theoretical guarantee of implicit regularization in model training (Dereziñski et al.)
2019
Vaskevicius et al. 2019 HaoChen et al. 2020, Blanc al., 2020 Razin & Cohen 2020). In
our work, we focus on regularization using early stopping. (Li al. 2020) proved that early stopping
robust label noise in certain settings. (Ali al., 2019 2020) related the risk of ridge regression
to that of early stopping. (Vaškevičius et al., (020) studied early stopped mirror descent. Our work
characterizes the time that achieves the optimal stopping in various settings and demonstrates how optimal early stopping affects generalization.
The double descent phenomenon has a long history of being studied the literature. (Loog et al, 2020) gave brief history of the early works studying this topic. A partial list of works that tackled related problem in the setting of least square regression includes (Belkin et al. 20188) 2020. Bartlet
et al. 2020 Deng et al. 2019; Hastie et al. 2019 Mei & Montanari, 2019 9 Muthukumar et al. 2020
d' Ascoli et al. 2020 Chen et al. 2020a] Yang et al. (020). (Nakkiran et al. (2020a) demonstrated
double descent can also occur
function of number of samples. (Nakkiran et al. 2020b) shows
that optimal regularization can mitigate double descent. Our work differs from previous works by
studying the effect of early stopping double descent.
Finally, our work studies the low rank structure of the feature representations. (Li et al. 2018 Dusenberry al., 2020) have also empirically explored and leveraged this property.
OVERPARAMETRIZATION
In this section, introduce and analyze the overparamettizzation setting, where the model size exceeds the number of features. This setting completes the missing piece of previous theoretical analysis on large models with excessive parameters. For data (ar, v), the input x: E TR is from high dimensional space. The label E is generated from a low-dimensional feature representation 2 RP, p S d. which is mapped from by low-dimensional transformation. A lot of common deep learning applications falls under this setting. Despite the huge model size used, the underlying feature space dimension can be low. For example, we observe that the labels y in CIFAR1O. 10, a widely used image classification problem with 10 classes, can be generated by feature space of dimension a little more than 10 (See Section 4.2)
Formally, we consider the following linear regression problem with d > Let the covariate/input matrix X E Raad be a random matrix such that each entry of it is generated from (00, 1) indepen- dently. Let I1, "i.... In be the row vectors of the matrix X. For semi-orthogonal matrix P E 1 with p < d and some unknown parameter 0",
the response is generated by
V/- PPx,, 8*) ct.
where the label noise e, ~ NO, o²) is independent of æ; and is generated independently for each (I,, y1). Let e E R² be the vector with entries given by eG.
We let Sover denote the overparametrization setting studied in this section. This setting is inspired by the overparametrization property of many real datasets and models. For example, classify images using deep neural network, the labels can usually be determined by features extracted from certain important parts of the images. The other parts of the image, though do not contribute to the label much, are still input to the model. When the neural network is wide, the network has the ability to extract far more features than what contribute to the label. This character of the deep neural network is what the setting Sover attempts to model.
Our data assumption has been studied in many related literature (Belkin et al. 2020 Nakkiran et al., 2020b). Our analysis only relies the concentration property of singular values of the data matrix X, so it is possible relax the data assumptions on X to bounds on the minimum and maximum singular values of the data matrix (Vaswani & Nayer 2016). The linear model has been widely used as the first step to study more complicated models as well due to its simple form (Bartlett et al.
2020 Chen al. 2020a Dobriban et al. 2018: Hastie al., 2019 Montanari et al.) 2019 Mitra
3

---

Under review as a conference paper at ICLR 2022
2019 Muthukumar al. 2020). It is possible to extend results to non- con-linear settings such the random feature setting. this paper, we stick to the simplest model so that we can get a simple and explicit characterization of the optimal early stopping time.
For fixed semi-orthogonal matrix and parameter 0*, let Dr.0- be the joint distribution of a single data point (I: y) given P and 0* For estimator B3, define the population risk
R Dr. [(0) B) 5)²
We consider the standard linear least squares problem
min SER
|1y x1
Applying gradient flow starting from 0 equation 2 gives continuous differential equation over time t,
X - (t)) n
(x,
with an initial condition 9x., (0) = 0. We can solve the differential equation exactly and obtain
B(1) = (x (1 exp (-iX X/n)) X y.
2019). Here, for any matrix A, exp (A) is defined as exp(A) := =n= nf. In practice, one would discretize the gradient flow and perform gradient descent. We discuss the error due to such discretization in Appendix
for all t 2 (Ali et al.
4"
For any fixed dataset y E R" and X E Raxd given by fixed P and 6, let (t) be the gradient flow solution standard linear regression problem at time We further assume that P e Rexd is uniformaly random semi-or cemi-orthogonal matrix.
Our goal study the expected risk of the estimator (x) over P and e. We denote the expected risk at time for dataset size n. as
Rx,8- (t) = Ep., [R))x
We study the optimal early stopping time, the time & that achieves the first local minimum of the expected risk. We characterize the optimal early stopping time for different parameter choices. We let lopt denote the optimal stopping time, omitting (X,0*) when clear from context,
dt (xx <
< and d dt Rx,o--t) (f)= -
Top (X, (X,0*) mint t s.t.
(5)
2.1 OPTIMAL EARLY STOPPING TIME
With the gradient flow solution 8x.y- we can derive high probability upper and lower bound on topt-
Theorem 1 (Optimal early stopping time in overparametrization setting). In setting Saver. for fixed parameter 0* and noise variance o², when n S d, let 7
//tty/lon For y S 1, with vd
probability at least 2 over the randomness of X, the optimal early stopping time top satisfies
log 1+ (1- ??² 1
(1+ (1 + v 18
n
n
tops <
log
1+
(1+ 17)2
o²
(1 v-)
o²
When n > d, lety = Vd+ of the optimal earty stopping time tops satisfies
Va
For 2 1, with probability at least 1 over the randommess
log (1+
1 2 (1(1-1)
1 {
1100112 d
2 n
1100011
< top S
log
1
1
11
(1
v
2
v
4

---

Under review as a conference paper at ICLR 2022
Note that our definitions of y differ slightly in the case n d and d, but they are both of order θ (2). Theorem gives an approximation of the optimal stopping time up constant 4d).omitting the < topt I When y 2 (roughly n 2 4d), emitting the dogarithmie-tera
long 7 is constantly bounded away from 1. When y 1 (roughly
logarithmic terms. 4d
12 3(++n) log
Ado S hopt S
5m log (1 3=1l-"1 d+n
do Combining these two cases shows that
when y is bounded away from 1, topt is about θ
When y is very close to 1, the upper bound on fom in Theorem can be loose. We show in Appendix that in the asymptotic case where C
22
log
d+n
still holds when and d are large and ||0_| lower bounded, the approximation hopt - Ô 2++
< < 4. In the asymptotic analysis we also achieve tighter constants in the bounds of the optimal early stopping time. Furthermore, in Appendix [F] using numerical experiments, we show that our theoretical result can be good approximation of the optimal stopping time for all 7.
Now, we discuss some implications of Theorem 1 The following lemma computes Rx (Nupi), the expected risk time fupt. and holds for all input matrix X regardless of how is generated.
Lemma For all n, P, d E N such that & d. let X E Raxd and 0" E RD be fixed. Let A 2 ... 2 Xa be the eigenvalues of the matrix I X X. Then,
n
Rx, = 0² + Σ exp 2t
10011 d
0² Σ
1 (1- 01- (x-eex(-tda))= (6) H #0}
In equation 6 the second term is the approximation error due to early stopping. The third term is due to overfitting to the label noise, which increases as the training time increases. In presence of label noise, the optimal early stopping finds the balance point of these two terms.
Theorem shows that the optimal early stopping time is roughly θ n+ when and d are around the same order. When n > d, the optimal early stopping time is roughly O(log "). It implies that when the number of features is smaller than the model dimension, optimal early stopping time increases as n increases or d decreases. Section F. corroborates this trend using experiments. In addition, we show in Section 4.2 and Section 4.3 that training deep neural networks large real datasets can also follow these two trends. An intuitive explanation of such phenomenon is when the sample size large, the label noise has less effect on model training, so the model can be trained longer before overfitting starts. On the contrary, when d increases, the number of parameters is large so that even small updates of each parameter can result in overfitting.
2.2 RISK MONOTONICITY
It has been observed empirically that without early stopping other types of regularization, when the number of samples n increases, the test error can experience double descent in presence of label noise. However, optimal early stopping can possibly mitigate the double descent phenomenon Nakkirrnn et al. 2020a). In Proposition] I we bound the expected risk at the optimal stopping time for varying data size and attempt explain this phenomenon.
Proposition 1. In setting Sower for fixed parameter 6* and noise variance 0². Let tops an/(n+ + d) for some constant a. Let X 2 ... 2 Xa be the eigenvalues of the matrix LXTX. X. Then,
Ri < Ex Rxx (lopt) S R2-
where
|10^12 and R Rı ao?
=2 +Ex Ex
Σ exp (-2mmd;/d)
Ri and R2 decrease monotonically as n increases.
Theorem I shows that the optimal early stopping time is roughly tapı n+d for a small constant up the logarithmic factors. When ||o|| is not too small, equation gives small region that o²
bounds the expected risk at Topt- We are able to show that both the upper and the lower bounds of the
5

---

Under review as a conference paper at ICLR 2022
region decrease increases. This implies that optimal early stopping mitigate sample-wiss double descent. We use experiments to corroborate our computation and give more details on this observation in Section and Appendix
related question whether stopping at optimal early stopping time can mitigate the double descent due to increasing model size d. (Nakkiran al.) 2020a) observed that double descent can still exist optimal early stopping. An theoretical analysis of this question can be an interesting future direction.
3 UNDERPARAMETRIIATION
In this section, we study the underparametrization setting, where the number features exceeds the model size. This setting shows very different behavior from the overparametrization setting. In this setting, the label is generated by some covariate 2, which is in nigh-dimensional space, but the model only has access to a low-dimension projection of 2.
Formally, we consider the following linear regression problem with d E p. Let the covariate matrix Z E Rexp be random matrix such that each entry of it is generated from (V,,, 1) independently. Let 21,..., Zn be the row vectors of the matrix Z. For some unknown paratmeter l", the reponse is generated by
(zi, 0-) +
where the label noise G NN, o²) is independent of 2; and y:- For a semi-orhotgonal matrix P E Rexd with d S p, let X ZP. we apply gradient flow on (X, (X.y). For fixed semi-orthogome matrix P and parameter 8*, let D D, be the joint distribution of single data point (ar, y). For an estimator 3, define the population risk
R(3) E(E.))~Dpp [ ((6,3)-T)) - 7)²
Similar as in the overparametrizations setting, we consider the gradient flow solution (equation 4 of standard linear least square problem (equation 2). For any fixed dataset y IR"" and E kg given by fixed Z, P and e, let (x,y(() (() be the solution of the gradient flow given in equation We further assume that P Roxd is a uniformly random semi-orthogonal matrix.
We let Sunder denote the above setting. Sunder studies the case where we only have partial access to the features that determine the label y and train the model on what is available.
Our goal to study the expected risk of the estimator (1, over Z, and We denote the expected risk over 7, P and at time f. as
Ro (t) Ez,r, (R()x,,(t)))-
Note that here in Sunders we take expectation on Z when computing the expected risk. In Sover- we do not take expectation X and instead get a high probability bound X. This slight difference is due to the different methods we use in analyzing these two settings. We study the optimal early stopping time, the time that achieves the first local minimum of the expected risk. We charaterize the optimal early stopping time for different choices of and d. We let lapt denote the optimal stopping time, omitting 6* when clear from context,
Eope (0*) = min t s.t. Rg- (t') < 0 for 0 < t' < and d Ro- (1) = O.
dl
di
We able give linear approximation of the optimal stopping time, hopt- Theorem 2 (Optimal early stopping time in underparametrizzation setting). In setting Sunder for fixed parameter 0r and noise variance o², if (8n + 9d 16) I|o 122 S pa² + 110011 the optimal early stopping time lope satisfies
1 2
2n 2n|0 0 1
S laps <
2 2 (p d) 100113)
po² + (p d) 1
Theorem 2 aaprooxmmates the early optimal stopping top up to a constant when p is larger that n and d by constant factor. For that is close p, numerical experiments show that the approximation

---

Under review as a conference paper at ICLR 2022
11|10-11 113
(p--) 16-12 still holds. Theorem implics that when the number of features is larger
than the model dimension, optimal early stopping time increases as n or d increases. An intu- itive explanation is when the model is when the model size and the sample size are small, the model does not have enough information to train so that the model tends to fit the noise easier.
Proposition 2.
In setting Sunder, for fixed parameter 0* and noise variance o², lef Topt
-|
Then, when (8n + 9d + 16) 110-11 S po² + + 1100 l2g. we have
pa
(p 10 12
R1 S Ro. (Fop) - R2,
where R₁= = 0² + 110111
2nd 13 po 1 and R2 0² + 110 1(p20* + 1)
3nd
Here, Rí 2 0.8R2 and both Ri and R2 decrease when d and n increase.
Proposition gives an upper bound and lower bound on the risk at the approximated optimal early stopping time. Under the ussumption d and n are small, R1 and Rg give tight region (R1 2 0.8Rg). Proposition 2 supports the observation that risk at optimal early stopping time monotonically decreases as n and d increases. Numerical experiments are presented in Section F.
4 EXPERIMENT
In this section, we run simulations for settings Sover and Sunder and demonstrate that training deep neural networks also follows the trends our theoretical analysis identifies. We provide additional experimental results in Appendix
4.1
LINEAR REGRESSION
(We moved the experiments results on linear regression to the appendix so we can have more space to address the comments from the reviewers.)
4.2 DEEP LEARNING WITH NEURAL NETWORKS
We study the optimal early stopping time in neural network training. We demonstrate that datasets MNIST, CIFAR-10 and CIFAR- 100 have low-rank representations. Such representations show that training common deep neural networks on these datasets falls under the overparametriiztion setting. Then, we demonstrate experimentally that the optimal early stopping time follows the pattern we identify for the overparametrization setting.
mnist
1.0
cifar 10
1.0
cifer 100 Singular values
value
0.0
Singular values
0.8
Singular values
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
100
102
100
10a
100
10a
10a
10a
10a
Index
Index
Indax
Figure 3: Scaled singular values of representations obtained from MNIST, CIFAR-10 and CIFAR- 100.
Existence of low-rank structure in image classification. Many previous works observe that low-rank structures exist and can be leveraged in deep image classification tasks (Van der Maaten & Hinton| 2008 Dusenberry et al., 2020). This structure facilitates the self-supervised learning and transfer learning paradigm where image features are learned and fixed close to the input layer, re- ducing the complexity of laaee-to-label mapping. Then only the last layer is trained to adapt to and classify out-of-domain images (Chen et al. 2020b). We follow this approach and demonstrate the existence of the low-rank structures in Figure 3 where we plot the singular values of the representa- tions of MNIST, 10, and CIFAR- -00. First, we train CNN/ResNet-60 (He et al. 201 6a b) to convergence with zero training loss (no label noise). Then, obtain the representations produced by the trained neural networks on MNIST, CIFAR-10, and CIFAR- 100. Even when trained with a very wide neural network, only the first 10/100 singular values of the representations are significant
7

---

Under review as a conference paper at ICLR 2022
compared to the others. This suggests that low-rank feature representations of the datasets exist. We believe this phenomenon may be of independent interest to understanding neural networks.
misst
dfar10
cifar 100
Emprical bounds
Emptrical bounds
Empirical bounds
4000
1500
Optimal early stopping time
1000
1000
2000
2000
500
10
30
40
50
10
20
60
20
30 Madel
40
50
Model width
(A1)
(B1)
(C1)
mnist Empir bounds
ctfar
2000
cifar 100
800
Empiical bounds
Empi ical bounds
400
1500
600
1000
800
200
10000
30000 40000 36300 80000
10000
20000
30000
40000
50000
30000
30000
Sample
Sample 5.ze
Samale sot
(A2)
(B2)
(C2)
Figure 4: In (A1) (B1) (CI), optimal early stopping time decreases with increasing model sizes for MNIST, CIFAR-10, 10, and CIFAR-100. In (A2) (B2) (C2), optimal early stopping time increases with increasing sample sizes for MNIST, CIFAR-10, and CIFAR-100.
Overparameteriiation behavior in image classification using neural networks In this section, we study the optimal early stopping time of MNIST, CIFAR-10, and CIFAR-100, We train MNIST using a fully connected network, and CIFAR- 10/100 using ResNet. Part of our code in this part builds open source code from (Nakkiran et al. 2020a). We add 20% of label noise to all datasets For MNIST, a simple ReLU network with one hidden layer is used. We vary the hidden layer width over d [10,
For CIFAR- 10/100. we widths (d. 2d, 4d, 8d] for different layer depths. The sample size ranges
family of ResNet networks with
convolutional layers from = [Le. 2e ..., 6e*] for MNIST, and [le 2e be.,...,eer 5e for CIFAR-IO/100. Inputs are normalized to [-1, 1, 1] with standard data-augmentation We use stochastic gradient descent with cross-entropy loss, learning rate 7) 0.1 for MNIST, CIFAR-10, and rj = 0.05 for CIFAR- -100 and minibatch size B = 512. The optimal stopping time is computed as topt = T/T where T is the epoch with the optimal early stopping performance. To select the optimal stopping time, we first apply moving averaging window with length 5 to mitigate the effect of mini-batch noise. After smoothing, we select the point with the optimal stopping time with the first minimal testing error (the lowest point of the first "valley', ignoring small local minima).
We show in Figure 4 the optimal early stopping time for all three datasets with varying n and d. In (A1) (A2) (A3), we observe that the optimal early stopping time decreases with increasing model width. In (B1) (B2) (B3), we observe that the optimal early stopping time increases with larger sam- ple sizes. Due to the existence of low-rank representations, Figure under the overparametriza- tion setting even for small d. The observations are consistent with our theoretical analysis and the experimental results linear models in the overparametrization setting. When trained with ultra small d < 10, the models show great instability. We provide additional experimental results sup- porting the underparamettrzztioon setting in Section 4.3
4.3 CLASSIFICATION USING TWO-LAYER NEURAL NETWORKS
Training datasets like CIFAR- 10/100 using ultra small models is unstable, so in this section, we use simpler datasets to verify our theoretical results for the underparametrizzaton setting. In this experi- ment, we use make classification function sklearn (Pedregosa et al.) 2011 to generate clusters of make.
points normally distributed around vertices of high-dimensional hypercube and assigns an equal number of clusters to each class. We generate 2000 samples (50-50 train-test split) of 20 dimen- sions/features, but only p 10 dimensions/features of each sample informative features. We add 20% label noise to the dataset. The optimal stopping time is selected similarly as in Section
8

---

Under review as a conference paper at ICLR 2022
We train the data using two-layer ReLU networks with varying hidden layer width d. The blue in Figure | gives 0.5 standard deviation of 6 runs and the blue line gives the mean. In Figure P when d p 10, we observe the underparamattization behavior where the optimal early stopping time increases as the model size increases. When d 2 10 = p. the optimal stopping time decreases with d. We can further observe that the test loss decreases with increasing model sizes at the optimal early stopping time.
Optimal early stopping time
2.1
800
=
Empirical bounds
700
1.8
500
==
1.-
Empinical bounds
10
15
20
10
15
Model
(a]
[b]
Figure 5: (a) Optimal stopping time as a function of model size. (b) Test loss as a function of model size.
CONCLUSION AND FUTURE WORK
In this paper, propose new model of overparametrization to study the optimal early stopping time. This model captures the phenomenon that the model size usually exceeds number of features in practice. We believe this model of overparametrization One future direction is the performance of other optimizers or techniques, e.g., stochastic gradient descent data augmentation, early stopping time and the resulting model. Future works can explore other regularization properties of this early stopped model, e.g., whether this early stopping helps when there is a domain shift in the testing dataset.
be of independent interest.
this model. Moreover, we give explicit characterization of the
Another direction worth exploring is extend results nonlinear settings. Extending result to the lazy training regime of neural networks (c.g., random feature regime and neural tangent kernel regime) can be relatively straightforward. One approach to first locate the features extracted at initizalition and then show how gradient flow progresses on the features extracted. Theoretical analysis of the non-lazy training is still largely open question, extending this result to non-lazy setting can be more challenging. To extend this result to the non-lazy setting for fully nonlinear neural network model, one needs to study how the features extracted change and how weights on the features change at the same time.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous- timm view of early stopping for least squares regression. The 22nd International Conference Artificial Intelligence and Statistics Pp. 1370-1378. PMLR, 2019.
Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In Proceedings of the 37th International Conference on Machine Learning
pp. 233 233.244.PP PMLR, 2020.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences 117(49).30063-30077 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the bias-variance trade-off. arXiv preprint arXiv: 18111112.111111 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM 2020.
Journal on Mathematics of Data Science
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. In Conference learning theory pp. 483-513, PMLR, 2020.
Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. arXiv preprint arXiv:2008.0103: 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning pp. 1597-1607. PMLR, 2020b.
Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprint arXiv:2006.095 2020.
Kenneth R Davidson and Stanislaw J Szarek. Local operator theory, random matrices and banach spaces. Handbook of the geometry of Banach spaces 133,7-366):31, 2001.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- 2019.
dimensional binary linear classification. arXiv preprint
Michal Dereziński, Feynman Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. arXiv preprint 1rXiv:1912.0455 2019.
Edgar Dobriban and Yue Sheng. Wonder: Weighted one-shot distributed ridge regression in high dimensions. Journal of Machine Learning Research 21(66))1-52,, 2020.
Edgar Dobriban, Stefan Wager, et al. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statisties ,46(1):247-27, 2018.
Simon Du, Wei Hu, and Jason Lee. Algorithmic regularization in learning deep homogencous models: Layers are automatically balanced. arXiv preprint 11X.vv1880600000 2018.
Michael Dusenberry, Ghassen Jerfel, Yeming Wen, Yian Ma, Jasper Snock, Katherine Heller, Balaji Lakshminarayanan, and Dustin Tran. Efficient and scalable bayesian neural nets with rank-1 factors. In International conference on machine learning pp. 2782 2782-2792. PMLR, 2020.
Jeff HaoChen, Colin Wei. Jason D Lec, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006.0888
2020.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:
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 pp. 770-778, 20.
10

---

Under review as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual
networks. In European conference on computer vision pp. 630-645. Springer, 2016b.
Roger A Horn and Charles R Johnson. Matrix analysis Cambridge university press, 2012.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning pp. 448-456. PMLR, 2015,
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez, The optimal ridge penalty for real-world high-dimensional data be zero negative due the implicit ridge regularization. Journal of Machine Learning Research 21(169):1-16 2020.
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint trXiiv1804.08836 2018.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. International Conference on Artificial Intelligence and Statistics ppp 4313 4324. PMLR, 2020.
Marco Loog. Tom Viering, Alexander Mey, Jesse H Krijthe, and David MJ Tax. A brief prehistory of double descent. Proceedings the National Academy of Sciences 1172200;:0625-10626 2020.
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv:1908.05355 2019.
Partha Mitra. Understanding overfitting peaks generalization error: Analytical risk curves for 1.2 and 1.1 penalized interpolation. arXiv preprint arXiv:1906.0360 1999906666667 2019.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max- margin linear classifiers: High-dimensions asymptotics in the overparametrized regime. arXiv preprint arXiv: 2019.
Nelson Morgan and Hervé Bourlard. Generalization and parameter estimation in feedforward nets: Some experiments. Advances in neural information processing systems 2:630-637, 1989.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal Selected Areas in Information Theory I(I): 67-83,22 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference Learn- ing Representations 2020a.
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint arXiv:2003.01897 2020b.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 11122825-288 2830, 2011.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms, arXiv preprint arXiv:2005.06330 006399 2020.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research 15()):122911958 2014.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research ()1 2008
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems. 332:2972-2983, 2019.

---

Under review as a conference paper at ICLR 2022
Tomas Vaškevičius, Varun Kanade, and Patrick Rebeschini. The statistical complexity of early- stopped mirror descent. arXiv preprint arXiv:2002.00189 ,0200.
Namrata Vaswani and Seyedehsara Nayer. A simple generalization of result for random matrices arXiv preprint arXiv:1612.00127 2016.
with independent sub-gaussian
Zitong Yang. Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for generalization of neural networks. In International Conference on Machine Learning pp. 10767-10777. PMLR, 2020.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn- ing. Constructive Approximation 2612))289-315, 2007.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research 2(Mar):527-550, 2002.
Tong Zhang and Bin Yu. Boosting with early stopping: Convergence and consistency. The Annals of Statistics 133(4):158--157, 2005.
12


Reviews:
[{"review_id": "rfol-Ipbal1", "reviewer": "Reviewer_dczT", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "I quickly checked the proof and did not find an obvious flaw. \n\nPros:\n\n1. The problem is interesting and important. Early stopping has a long history of being used as a regularization of machine learning algorithms. \n\n2. The results are insightful for me. The main results about the overparameterization setting agree with some empirical findings and make a step towards understanding the training procedure of machine learning algorithms.  \n\nCons:\n\n1. The data distribution and problem are restrictive. I understand that this is an early theoretical attempt and I notice that the authors also find some related work falls into the same setting. However, the approaches in this paper rely on the assumption that the estimation can be expressed as a function of early stopping time. I worry that it would be highly nontrivial to extend the results to real settings. \n\n2. Technically, the results of Theorem 1 and 2 are not directly comparable because Theorem 1 presents high probability bounds while Theorem 2 presents deterministic bounds with a further assumption on the data distribution. It may be confusing to present the main claims in parallel without discussing the differences in the two settings.", "summary_of_the_paper": "This paper studies an interesting and important problem: what is the optimal early stopping time (considering the model dimension and sample size, especially under an overparameterization setting)? The data distribution is synthetic. Considering a standard linear least squares regression problem, the gradient flow is expressed as a differential equation. Further, solving the differential equation, the estimator can be expressed as a function of the time and data. Given such a result from an earlier work, the paper studies the optimal stopping time that minimizes the expected risk and presents high probability (upper and lower) bounds for the overparameterization setting. It suggests that with a high probability, the optimal early stopping time is $\\tilde{\\Theta}(\\frac{n}{n+d})$, which implies that the optimal early stopping time increases as $n$ increases and $d$ decreases. The paper also shows that the bounds decrease as $n$ increases, which implies that optimal early stopping can mitigate sample-wise double descent. Empirical results validate the theory.", "summary_of_the_review": "Overall this is an interesting theoretical paper with its limitation. Currently, I tend to accept it.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kEr68NipMC", "reviewer": "Reviewer_EU5H", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "# Pros:\n+ The different behaviors of optimal stopping time for gradient flow in over- or under-informative settings seem to be interesting and novel.\n+ The observation from neural network experiments are also inspiring.\n\n\n# Cons:\n- First of all, the terminology of \"overparameterization\" and \"underparameterization\" are rather mis-leading!!!! In literature, those terminologies are widely used to refer to regimes where the number of parameter is larger/smaller than the number of data. However in this paper, if I understand it correctly, the authors aim to mean two different feature generating processes. More concretely, let $X$ be feature, $Z$ be the hidden variable and $Y$ be the response, then the two regimes in Markov chain can be represented as \n$$\nX \\\\to Z \\\\to Y\n$$ \nand \n$$\nX \\\\leftarrow Z \\\\rightarrow Y\n$$\nI would rather refer these two regimes as \"over-informative\" and \"under-informative\". Better to avoid misleading here.\n\n- Beyond terminologies, I would say the paper needs some further revision, at least in terms of languages. For a few examples:\n   * the first two paragraphs in Sec 1 could use some references. \n   * Sec. 1, Over- vs. Under-parameterization paragraph: I am not sure whether or not these are \"discovered\" by the authors. There are a number of references in Sec. 4.2 that seem to suggest low-dim data structure is known. Could use some clarification here. \n   * The paragraph above Sec. 1.1. \"early-stopped models\" \n   * It is such a mess when introducing $P$ --- is it deterministic or random?\n\n- Paragraph below Thm1. The claims about case $ n \\gg d$ is clearly incorrect. Note that $n / (d+n)  = \\Theta(1)$, but $\\log (1 + \\Theta(n / d)) \\gg 1$, so the logarithmic factors are actually leading factors. All the following claims need revision. \n\n- As for the Theorems, I find the feature assumption is too strong to be interesting. For example in Thm1, it assumes $x \\sim N(0,1)$. This is too specialized and is basically equivalent to a 1-dimensional problem. Thm1 could be more interesting if can cover $x \\sim N(0,H)$ where $H$ is a general PSD matrix. Similar assumptions on hidden variable is also made for Thm2.\n\n- Finally, I feel the main conclusion of this work is less surprising (or interesting), given the fact that the different behaviors of optimal early stopping is in fact caused by **different data generating process** instead of **different regimes of number of parameter vs. number of data**. In the first setting of the paper, which is also the traditional setting we see in literature, the feature contains full information for recovering the label, and the optimal stopping time is obtained by balancing the bias vs. variance error. In this case, it is very clearly one needs to stop earlier with a smaller $n$ or larger $d$ to avoid overfitting. In the second setting, it is more like an issue of insufficient observation, and no wonder one can stop latter as $d$ increases (where the information in features increases). I do not think this is beyond the traditional statistics wisdom. \n\n\n\n\n\n\n\n", "summary_of_the_paper": "This paper studies the optimal early stopping time of gradient flow for linear regression in two regimes: over-informative features or under-informative features, where the first regime means the features contain sufficient information to generate the response, while the second regime means responses rely on additional information beyond those in the features. In the two different regimes, the paper shows that the optimal early stopping time behaves quite differently. Theory are built for linear regression, and experimental verifications are performed in both toy data and neural networks.", "summary_of_the_review": "The current paper is misleading and needs a significant revision. Based on my current understanding, the paper is less interesting as suggested by the title. I cannot recommend acceptance given the current version. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UWDyJ_gn5yN", "reviewer": "Reviewer_6rDq", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "*Strong point(s) of the paper*\n\n- The authors obtain novel theoretical results on the optimal stopping times for gradient flow under a linear model (with Gaussian data/noise assumptions), refining the initial theory built up by Ali et al. (2019).\n\n- Their theoretical analysis explicitly separates the over-parametrized and under-parametrized settings (e.g., whether the number of model parameters in larger than the number of data features or not), obtaining distinct insights for each of these settings, with empirical tests that are designed to invesigate the \"sharpness\" of this distinction. This distinction is, at least in extreme cases, quite important, and additional insights both in theory and practice are of value.\n\n\n*Weak point(s) of the paper*\n\n- I felt that the theoretical results were poorly explained, given the context of previous work such as Ali et al. (2019). In section 2.1, the authors just say \"we can derive a high probability upper and lower bound on (the optimal stopping time)\" and give the result, without any discussion of the technical side of this. Since Ali et al. say that controlling the optimal stopping time is \"difficult\" (their Rmk 4), one would expect that the authors here would describe what assumptions or techniques made it possible for them to solve this difficulty. Since this previous work did not (as far as I can tell) make any Gaussian assumptions on the data, one expects that the Gaussianity might play an important role in the authors' analysis, but since this is not described, the reader is left wondering. One is also left wondering if it would be straightforward to obtain high-probability bounds on the risk, since bounds are with high probability for the stopping time control.\n\n- While I would not say the writing itself is poor, it is rather careless in many places. Some are notation issues, others are explanation issues. Here are a few representative examples:\n  - The matrix exponential (p.4) is not introduced anywhere as far as I can see. \n  - On p.6, the authors say that \"Theorem 2 implies that when the number of features is larger than the model dimension, optimal early stopping time increases as $n$ and $d$ increases.\" This is a very broad statement; in reality, doesn't it depend on how fast $n$ and $d$ respectively increase? A similar statement is on p.7 for the under-parametrized case.\n  - In the experimental section, there is very little information on how the optimal stopping times are actually computed, and a brief glance at the supplementary materials does not shed any more light on this.\n", "summary_of_the_paper": "This work looks at implicit (algorithmic) regularization of learning algorithms, with a particular focus on the impact of early stopping in the context of iterative gradient-based learning algorithms.\n\nThe model of interest is a linear model with additive random noise, and for their analytical entry point, the authors consider the gradient flow differential equation as in Ali et al. (2019), i.e., a typical gradient descent update in the limit where step size is taken to zero. They provide confidence intervals for the optimal early stopping time (optimal in terms of the expected squared error) and subsequently derive upper/lower bounds in expectation for the risk achieved at such the optimal early stopping time.\n\nIn addition, the authors carry out empirical analysis of optimal stopping times for both linear and non-linear models, over a range of sample size, data dimension, and model dimension settings. They argue that well-trained neural networks admit \"low-rank\" representations which are akin to the over-parametrized linear model that they study in theory.", "summary_of_the_review": "To the best of my understanding, the theoretical results obtained by the authors (optimal stopping time control + resulting risk bounds) are new and provide more refined insights that the existing literature with respect to the impact of sample size and dimensionality, despite the limiting Gaussian assumptions. In addition, while the experimental section could use a lot more exposition, from what I can tell the design is straightforward and natural considering the theoretical results the authors want to verify. My overall take on this paper is that there are some results of value here, but the paper itself needs some work, so I am left on the borderline with this work, tending to accept, but with the caveat that I am not very familiar with the developments in this line of work since Ali et al.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ABFzvjn_KtT", "reviewer": "Reviewer_Y1pf", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "I think the main contribution of the paper is the analysis of optimal early stopping in overparameterized regime. However, I think the definition of “overparameterized regime“ in this paper is different from what is usually used in the literature. Specifically, the definition in the paper doesn’t take into account the number of examples, but only the number of features and model size. I think the authors should clarify what do they mean by “model size” in general (e.g. in neural networks), is it the number of parameters? The width of the network ? \n\nAnother relevant paper in the overparameterized regime:\n\nVaskevicius et al, Implicit regularization for optimal sparse recovery. NeurIPS 2019.\n\nHowever, I think the novelty of the paper is quite limited. The underparametererized setting was previously analyzed in Nakkiran et al., 2020b, where the effect of regularization is studied, and it is well known that $L_2$ regularization is strongly related to early stopping. For example, Nakkiran et al., 2020b showed that the expected test risk of the optimally-regularized model is monotonic in the model size (theorem 3 therein). Also, the optimal ridge parameter $\\lambda\\sim\\frac{1}{d}$ (lemma 3 therein), and since stopping time decreases when $\\lambda$ increases, the optimal stopping time is monotonic in model size, which is also the result in this paper. The authors claim that “optimal early stopping can help mitigate double descent in various settings” – this should be compared to similar results in Nakkiran et al., 2020b for $L_2$ regularization.\n\nComments and questions about the empirical part:\n\nI think the empirical part with neural networks should be improved:\n\n-\tIs it possible to show that the results hold when changing the model size by changing the depth and not width ?\n-\tWould be good to show that the results hold when playing with the amount of label noise.\n-\tI think Figure 13 should go more to the right (more epochs) to see the entire curve.\n-\tIn figures 11,12 – can you explain how $a,b$ are selected ?\n-\tIn figure 14 – is the test loss correspond to optimal early stopping time ?\n", "summary_of_the_paper": "In this paper the authors analyze early stopping in linear regression. The authors show that the optimal early stopping time behaves differently in overparameterized and underparameterized regimes. Specifically, the optimal early stopping time decreases when increasing model size in the overparameterized regime, but increases with model size in the underparameterized regime. Some empirical results demonstrate the theoretical results in linear regression and deep neural networks.", "summary_of_the_review": "Overall, I think the theoretical contribution is rather limited given the work of Nakkiran et al., 2020b, and the empirical part should be improved. Therefore, I don’t recommend the paper for acceptance at this stage.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of characterizing the optimal early stopping time in overparameterized learning as a function of model dimension and sample size. To do this the paper uses an explicit form of the gradient flow from prior work to present high probability bounds in the over-parameterized setting and characterizes various properties of the optimal stopping time. The authors also conduct various experiments to verify the theory. The reviews though the paper was interesting and insightful. They also raised some concerns about the (1)restrictiveness of the distributional assumptions, (2) poor explanation of the theoretical results, and (3) novelty with respect to other work and (4) other technical issues. The discussion and response mitigated these concerns but the reviewers decided to mostly keep their original score. My own reading of the paper is that there are good ideas in this paper and I agree with the authors that some of the technical issues raised by the reviewers is incorrect. However, it is also clear that the paper needs a bit more work to put it into the right context and also the proof need to be more clearly and carefully written before this paper can be accepted. Therefore I recommend rejection but encourage the authors to submit to a future ML venue after a thorough revision.
Decision: Reject