On the Role of Optimization in Double Descent: A Least Squares Study
Authors: Ilja Kuzborskij
Csaba Szepesvari
Omar Rivasplata
Amal Rannen-Triki
Razvan Pascanu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Double Descent
Optimization Error
Excess Risk
Generalization
Least Squares

Abstract: Empirically it has been observed that the performance of deep neural networks steadily improves with increased model size, contradicting the classical view on overfitting and generalization. Recently, the double descent phenomenon has been proposed to reconcile this observation with theory, suggesting that the test error has a second descent when the model becomes sufficiently overparameterized, as the model size itself acts as an implicit regularizer. In this paper we add to the growing body of work in this space, providing a careful study of learning dynamics as a function of model size for the least squares scenario. We show an excess risk bound for the gradient descent solution of the least squares objective. The bound depends on the smallest non-zero eigenvalue of the sample covariance matrix of the input features, via a functional form that has the double descent behaviour. This gives a new perspective on the double descent curves reported in the literature, as our analysis of the excess risk allows to decouple the effect of optimization and generalization error. In particular, we find that in the case of noiseless regression, double descent is explained solely by optimization-related quantities, which was missed in studies focusing on the Moore-Penrose pseudoinverse solution. We believe that our derivation provides an alternative view compared to existing works, shedding some light on a possible cause of this phenomenon, at least in the considered least squares setting. We empirically explore if our predictions hold for neural networks, in particular whether the spectrum of the sample covariance of features at intermediary hidden layers has a similar behaviour as the one predicted by our derivations in the least squares setting.

On the Role of Optimization in Double Descent: A Least Squares Study
Iija Kuzborskij DeepMind
Csaba Szepesvári University of Alberta DeepMind Edmonton, Canada
Omar Rivasplata University College London
Amal Rannen-Triki DeepMind
Razvan Pascanu
DeepMind
Abstract
Empirically has been observed that the performance of deep neural networks steadily improves with increased model size, contradicting the classical view on overfitting and generalization. Recently, the double descent phenomenon has been proposed reconcile this observation with theory, suggesting that the error has a second descent when the model becomes sufficiently overparameterized, as the model size itself acts as an implicit regularizer. this paper we add the growing body of work in this space, providing careful study of learning dynamics as function of model size for the least squares scenario. We show an excess risk bound for the gradient descent solution of the least squares objective. The bound depends on the smallest non-zero eigenvalue of the sample covariance matrix of the input features, via functional form that has the double descent behaviour. This gives a new perspective on the double descent curves reported in the literature, as our analysis of the excess risk allows to decouple the effect of optimization and generalization error. particular, we find that in the case noiseless regression, double descent is explained solely by optimization-relan related quantities, which was missed studies focusing on the Moore-Penrose pseudoinverse solution. We believe that our derivation provides an alternative view compared to existing works, shedding some light on possible cause of this phenomenon, at least in the considered least squares setting. We empirically explore if our predictions hold for neural networks, in particular whether the spectrum of the sample covariance features at intermediary hidden layers has similar behaviour the one predicted by our derivations in the least squares setting.
Introduction
Deep Neural Networks optimized by Gradient Descent (GD) methods have shown amazing versatility across large range of domains. One of their most intriguing features is their ability perform better with scale. Indeed, some of the most impressive results [see e.g. Brock et al., 2021, Brown al., 2020, Senior et al., 2020, Schrittwieser al., 2020, Silver et al., 2017, He et al., 2016 and references therein] have been obtained often by exploiting this fact, leading to neural network models that have at least as many parameters as the number of examples in the dataset they are trained on. Empirically, the limitation on the model size seems to be mostly imposed by hardware or compute. From a theoretical point of view, however, this property is quite surprising and counter-intuitive. as one would expect that in such extremely overparameterized regimes the learning would be prone to overfitting [Hastie et al., 2009, Shaley-Shwartz and Ben-Davil 2014].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Recently Belkin et al. [2019] proposed Double Descent (DD) phenomenon as an explanation. They argue that the classical view of overfitting does not apply in extremely overparameterized regimes, which were less studied prior to the emergence of the deep learning era. The classical view in the parametric learning models was based on error curves showing that the training error decreases monotonically when plotted against model size, while the corresponding test errors displayed U-shape curve, where the model size for the bottom of the U-shape was taken to be a "sweet spot" Ief. Belkin et al., 2019, Fig. IA] achieving an ideal trade-off between model size and generalization. Here, larger model sizes than the aforementioned ideal were thought to constitute the 'overfitting" regime, since the gap between the test error and the training error increased.
Excess risk Opt. error
1.8
1.5
1.0
0.5
66
3G
0.5
60
8G
100
23
384
Cecass risk testrmate: T 100
Eccesn mic (astimate) 7 1000
Cocess risk [estimate! T- 10000
0.000
0.000
6.00
5.00
1075
8.00
8.05
00001
100
6.00
Polerr
Opt. cmre (etimotto 100
Opt enay Oedimaatol T 3080
Dgt. cmmr (estoratio) 7 10000
6.25
0.30
6.15
Testure
(asture dimendic
Teatire cimem133
Figure 1: Evaluation of a synthetic setting inspired by Belkin et al. [2020]. We consider a linear regression problem (n = 20, d E [100]). where regression parameters are fixed, and instances are sampled from truncated (to [-1, 1) normal density. GD is run with learning
0.05 and initialization drawn from N/O0, J I)) The first row demonstrates behavior of excess risk (see Eq. (1)), the second shows an estimate of excess risk (on 10 held-out points), and the third shows an estimate of the optimization error.
The classical U-shape test error curve dwells in what is now called the under-parameterizer regime, where the model size is smaller than the size of the dataset. Arguably. the restricted model sizes used in the past were tied to the available computing power. By contrast, is common nowadays for model sizes to be larger than the amount of available data, which is called the over weer-paaaeteerize regime. The divide between these two regimes is marked by a point where model size matches dataset size, which can be called the interpolation threshold [ef. Belkin et al., 2019, Fig. 1BJ.
The work of Belkin al. [2019] argues that as model size grows beyond the interpolation threshold, one will observe a second descent of the test error that asymptotes in the limit to smaller values than those in the underparameterrized regime, which indicates better generalization rather than overfitting. To some extent this was already known in the nonparametric learning where model complexity scales with the amount of data by design (such as nearest neighbor rules and kernels), yet one can generalize well and even achieve statistical consistency [Györfi et al., 2002]. This has lead to a growing body of works trying to identify the mechanisms behind DD, to which the current manuscript belongs too. We refer the reader to Section 2, where the related literature is discussed. Similar to these works, our goal also to understand the cause DD. this paper we explore a finite-time GD solution to least squares problems that allows us to work with analytic expressions for all the quantities involved. Fig. provides a summary of our findings. particular, shows the behaviour of the risk (or the expected loss of the algorithm) in linear regression setting with random inputs

---

and noise-free labels, for which in Section 3 we prove bound that has the form
(1- ax min
2T
||00112
Vn
Here labels are generated as Y = x w" for some unknown ground truth model w" E R and for positive matrix M). The
random inputs X E Rd on a unit sphere [| = V MX factor a is a constant learning rate, and n is the number of examples in the training set. Note that the feature dimension d coincides with the number of parameters in this particular setting, hence > n is the overparameterized regime. The quantity Xmin is the smallest positive eigenvalue of the sample covariance matrix of the inputs, and it is of special importance: We observe that the shape of the bound is controlled by Xmin via the exponential term, which increases as X decreases while it decreases as X grows, resulting in a peaked shape of the bound. In Fig. we observe peaking behavior not only in the risk but also in the quantity that we label 'optimization error' which is this special term of the risk bound that is purely related to optimization. The peaking behaviour of the risk-the Mean Squared Error (MSE) in case of the squared loss- was observed and studied in a number of settings [Belkin et al., 2019, Mei and Montanari, 2019, Derezinski et al., 2020] sometimes relating it to A/tip however, to the best of our knowledge the connection between the peaking behavior and optimization so far received less attention. In the absence of label noise, we conclude that DD manifests due to the optimization process. On the other hand, when label noise is present, in addition to the optimization effect, X also has effect the generalization error.
Our contributions: Our main theoretical contribution is presented in Section In particular, Section 3.1 focuses on the noise-free free least squares problem, Section 3.2 adds noise the problem, and Section 3.3 deals with concentration the sample-dependent X around its population counterpart. The essential idea of the proof of our main result is outlined in Section 5. Sections 4 and 6 provide some discussion on the implications of our findings and an empirical exploration of the question whether simple neural networks have a similar behaviour than that of the least squares setting.
Notation:
The linear algebra and analysis notations used in this work are defined in Appendix A. We briefly mention here that we denote column vectors and matrices with small and capital bold letters, respectively, e.g. = (a1, 012,--. (a.....-0a, aa) Red and A E Rd xd2, Singular values of a rectangular matrix A E Rn are denoted by Smax (A) 31 (A) ... SA) Smin (A). The rank of A is r = max(k s4 (A) > 0}. The eigenvalues of a Positive Semi-Definite (PSD) matrix M Rdd are non-negative and are denoted Amax (M) = (M .... 2 >a(M) = Amin (M), while ( denotes the smallest positive (non-zero) eigenvalue.
2 Related Work
To the best of our knowledge DD was first mentioned by Vallet et al. [1989]. who observed the phenomenon for the Moore-Penrosee pseudo-inverse solutions (see [Loog et al., 2020] for brief history). The recent literature revisited DD) mainly considering ordinary least squares with the explicit solution given by the Moore-Penrose pseudo-inverse. These works have focused on instance-specific settings (making distributional assumptions on the inputs) while arguing when the analytic pseudo- inverse solutions yield DD behaviour [Belkin et al., 2020]. This was later extended setting showcasing the control of DD by the spectrum of the feature matrix [Derezinski et al., 2020]. In this paper we also argue that the spectrum of the covariance matrix has a critical role in DD, however we take into account the effect of GD optimization, which was missed by virtually all the previous literature due to their focusing on analytic solutions. The effect of the smallest non-zero eigenvalue on DD, through a condition number, was briefly noticed by Rangamani et al. [2020]. In this work we carry out a more comprehensive analysis and show how the excess risk of GD is controlled the smallest eigenvalue. In particular, X+ has a U-shaped behaviour as the number of features increases, and we give a high-probability characterization of this behavior when inputs are subgaussian. To some extent, this is a non- asymptotic manifestation of the Bai- Yin law, whose connection DD in an asymptotic setting was noted by Hastie al. [2019, Theorem 1].
more general
Some interest was also dedicated to the effect of bias and variance of DD [Mei and Montanari, 2019] in the same pscudo-inverse setting, while more involved fine- fine-grained analysis was later carried out
3

---

by Adlam and Pennington [2020]. In this work we focus on the influence of the optimization error, which is complementary to the bias-variance effects (typically we care about it once optimization ervor is negligible).
The DD behaviour also observed beyond least squares, for instance in neural networks and other interpolating models [Belkin et al., 2019]. To some extent a formal connection to neural networks was first made by Mei and Montanari [2019] who studied the asymptotic behaviour of the risk under the random feature model, when nt dimput, ddP - oo while having Jippu and pippat fixed. Later on, with the popularity of the Neural Tangent Kernel (NTK) [Jacot et al., 2018] this connection became clearer as, within the NTK theory interpretation, shallow neural networks can be paralleled with kernelized predictors [Bartlett al., 2021]. A detailed experimental study of DD in deep neural networks was carried out by [Nakkiran et al., 2019], who showed that various forms of regularization mitigate DD. Our results imply that (z-regularization in least squares (ridge regression) makes X well-controlled and therefore mitigates the peak. The same should carry over to the early-stopping in least squares (Yao et al., 2007] and to early stopping in shallow neural networks [Ji et al., 2021, Richards and Kuzborskij. 2021, Kuzborskij and Szepesvári, 2021].
g
In this work, we explain DD in least squares solution obtained by GD through the spectrum of the features, where optimization error has visible role. While we do not present formal results for neural networks, we nevertheless empirically investigate on shallow neural networks whether our conclusions extend to neural nets as would be suggested by the NTK theory.
3 Excess Risk of the Gradient Descent Solution
We focus on the Gradient Descent (GD) algorithm, treated as a measurable map A S x Rd - Rd where S = 2" is the space of size-n training sets. Consider learning problem where hypotheses parameterized by weight vectors w E Rd. The risk of a given w is L(w), and the empirical risk of w over sample S' is (tw). GD is applied to minimize the empirical risk. Given training set S E S and an initialization point wo E Rd, we write As(wo) to indicate the output obtained recursively by the standard GD update rule with some fixed step size >> 0, i.e. As(wo) wT, where
w. w; - a VLs(w,
1= 1=1....,
It is well-known that in the overparameterized regime > n)) GD is able achieve zero empirical loss. Therefore, rather than focusing on the generalization gap I.(As (wo)) (s(A((w)) is more natural to compare the loss of As to that of the best possible predictor. Thus, we consider the excess risk defined as
& I(As(wo)) I(ww),
w arg min L(w). weRd
3.1
Least Squares with Random Design and No Label Noise
We first consider a noise-free linear regression model with random inputs:
Y = X "
where the random input X E Id is distributed according to some unknown distribution Px supported on unit shpere X|] M v X MX 1 for positive definite matrix M Rdxd), After observing a training sample 5 = ((X [X,, 1, Y Y)) we run GD to minimize the empirical squared loss:
(s(w) = 2n
w T Y.)?
The sample covariance matrix is E (XiX +....... +X, XxX [1 n Let E USV be the Singular Value Decomposition (SVD) with orthogonal matrices U = [u]..... ual and V = [o,,..., u,), and scaling matrix S diag (ii.. Aaa) where π, Ax( 2)) are in the decreasing order: X 2 2o ... Xo 2 The matrix E might be degenerate Os = 0), and the non-degenerate part given by U, = [u1, Ur. V, = (u....,, U. and S, = diag (?,,..., .is....,,),,, where = rank (E). We use the shorthand X X t Σ AE( for the minimal positive (non-zero) eigenvalue, and
denote M- U,U. Note that M M. Now we state main result in this setting.

---

Theorem 1. For any wD E R and x > O, with probability at least -e over inputs
Er S (1 - at ) 1100" woll? 2 +
12
(vind+ + vo) (1|woll? + 21110*1133)
Vn
Proof. The theorem is a corollary of Theorem below, whose proof is given in Appendix C.
Looking at Theorem 1, we can see that the excess risk is bounded by the sum of two terms. Note that the second term is negligible in many cases (consider the limit of infinite data) and additionally it is a term that remains constant during training as it does not depend on training data. Therefore, we are particularly interested in the first term of the bound, which data-dependent and arises due to optimization error of the algorithm. This term increases as X decreases and it decreases as X grows, which results in peaked shape. As we will see in the following Section 3.3, given mild assumptions on the input distribution, this is precisely the behaviour of X Interestingly, only the first term in this bound is source of the peak, which suggests that in a setting without the label noise, optimization error is the sole source of DD. Next we consider the case with label noise.
3.2 Least Squares with Random Design and Label Noise
Now, in addition to random inputs we introduce label noise into our model:
Y X wn t
where we have random variable e, independent from X, such that E[e] and E[c²] = o2. Theorem 2. For any wo IRd and
O, with probability least e over inputs
Xa) S (1 x 22 1 - woll + 40²
-2
E(ET| X
X
min
12 Vlnd+ v |10001 + 21/201
112
0²
x
The proof is in Appendix C. Comparing to Theorem 1, the theorem gains two noise-dependent terms, namely 4(o² (n22/n)(()) (2thi)))) and o² +.. +,.)) The former closely resembles the term controlling the generalization gap in the analysis of ridge regression [Shalev- [Shalev-Shwarzz and Ben- Ben-David, 2014, Cor. 13.7], however, unlike ridge regression, here we have dependence non-zero eigenvalue instead of a regularization parameter. The latter is due to convergence of GD to the Moore-Penrose pseudo-inverse solution. This term can be further upper-bounded by o²r and the last component in the bound is of order (||2*1|2 2 /²r/Stum)/ /n. Thus, long as * min Z r, we should have a non-vacuous bound even in the overparameterized setting. In the next section we try understand when this is the case by looking at the concentration of X
the smallest
3.3 Concentration of the Smallest Non-zero Eigenvalue
In this section we take look at the behaviour of Anjn assuming that input instances XI,..., x are i.i.d. random vectors, sampled from some underlying marginal density that meets some regularity requirements (Definitions and below) so that we may use the results from random matrix theory [Vershynin, 2012]. Recall that Σ ( +.... + X, x,,X,,,) X,,) is the covariance matrix of the input features. We focus on the concentration of X = - (E) around its population counterpart - X+ (E), where Σ is the population covariance matrix: Σ = x
In particular, the Bai- Yin limit characterization of the extreme eigenvalues of sample covariance matrices [Bai and Yin, 1993] implies that x has almost surely asymptotic behavior (1 (1- /d/n)² as the dimensions grow to infinity, assuming that the matrix D := [X...... Xx,] E R has independent entries. We are interested in the non-asympiotic version of this result. However, unlike Bai and Yin [1993], we do not assume independence of all entries, but rather independence of observation vectors (columns of TT. This will be done by introducing a distributional assumption: assume that observations are nub-Gaussian and isotropic random vectors.
5

---

Definition 1 random vectors). A random vector X E R is sub Gaussian if the random variables X y are sub-Gaussian for all E R.. The sub-Gaussian norm of random vector X IR. d defined
X
sup sup =21 LVD
1
B|Ix
y/
Definition (Isotropic random vectors). A random vector X E TRd is called isotropic if its covariance is the identity: X I. Equivalently, X is isotropic if [X x) ||2:| for all x E R..
Let E' be the Moore-Penrone pseudoinverse of Σ. In Appendix D we prove the following.
Lemma (Smallest non-zero eigenvalue of sample covariance matrix). Let D [X 15,,... x
Rdxa be a matrix with ii.d. columns, such that max; [Xillvz S K, and let E = D D/n, and
E = X x Then, for every 2 O, with probability at least 1 - =e= we have
2
min
Σ
min (Σ) 1 1-K2²
K2
c
d
for d
n
furthermore,,, assuming that || Vd a.s. for all i [ni], we have
2
/ (v= K2 (c+ (c+6// (1)
Amii (2)
for n2 < d,
min
where we have an absolute constant 23.5 (9()).
Lemma 1 is -symptoti result that allows us to understand the behaviour of X and hence the behaviour of the excess risk bound that depends on this quantity, for fixed dimensions. We will exploit this fact in the following section in which we discuss the implications of our findings.
4 Discussion
The above concentration inequalities for X+ combined with Theorem 1, in the overparameterized regime (d >> n)) give us
Er x (v vn vn- 1-11))
2T
||20 112.
similar bound holds in the underparameterized case (d < n) replacing the term (Vd -n- with (vū - vd - 1)2. Note that the term multiplying the learning rate is /d/n in accordance with the Bai- Bin limit which says that asymptotically X (vd/n 1)2. is
1/v
interesting see how (1 al /d/n - 1)2) 27 varies with model size d for a given fixed dataset size n and fixed number of gradient updates T. Setting 7 d/n and considering the cases 7 + (underparameterized regime), 7 ~ 1 (the peak), and > 1 (overparameterized regime) it becomes evident that this term has double descent behaviour. Thus, the double descent is captured in the part of the excess risk bound that corresponds to learning dynamics on the space spanned by M.
Similarly, we can now consider the scenario with label noise: we can similarly bound the excess risk, following the same logic as for noise-free case; however we have an additional dependence on d² via the term 4(o² (2 -2 While this does not interfere with the double descent shape as we change model size, does imply that the peak is dependent the amount of noise: The more noise in the learning problem, the larger we expect the peak at the interpolation threshold to be.
While the presence of the double descent has been studied by several works considering pseudoinverse solutions, our derivation provides potentially new interesting insights. Optimization plays role the
(()+ = max (0, m}
We use S g when there exists universal constant C such that Cg uniformly all arguments.

---

appearance of DD and its impact depends on the strength of the label noise. In the noise- free setting, DD curves seem to be solely due to optimization. In the presence of noise, there relationship between the strength of label noise and the shape of the DD curve: The larger the noise is, the larger the peak in DD curve. This agrees with the typical intuition in the underparmetrized regime that the model fits the noise when it has enough capacity, leading towards a spike in test error. However, due to the dependence x min+ it is subdued the model size grows.
Connection to neural networks. Taking some inspiration from our observations for least squares, it is natural to ask whether we can observe a similar effect in neural networks trained by GD. One argument here could be to decompose learning in neural networks into feature extraction and linear prediction components, and to check whether X+ of features obtained from the intermediary layers could exhibit the behaviour leading to the double descent. This in particular might be significant if we think of the last layer of the architecture as a least squares problem (assuming we are working with mean squared error), and all previous layers some random projection, ignoring that learning affecting this projection as well. It is also interesting to investigate the behaviour of X in combination with techniques used by practitioners, such as batch-norm [Ioffe and Szegedy, 2015], layer-norm [Ba et al., 2016], and residual connections [He et al., 2016], which are typically used in recent architectures, ensuring that features of intermediary layers are well "conditioned". In Section 6 we empirically look at some of these questions.
From a theoretical point of view, one possibility for adapting our results to neural network learning could be to consider Neural Tangent Kernel (NTK) framework [Jacot al., 2018]. Interestingly, this may require results on the concentration of the neural tangent random feature covariance matrix. For shallow networks the concentration phenomena for NTK matrices are expected to be similar as presented in our work [TTropp. 2012]. For deep networks, the spectrum of an NTK matrix is not well-understood and this is an active area of research itself [Nguyen et al., 2021] with open questions. which would be interesting to explore in the future work.
Proof idea
The proof of our main result (Theorem 2) rests upon the observation that under GD optimizing an overparameterized least squares objective, the iterates span a low-dimensional subspace given by the eigenvectors of sample covariance matrix. This is captured by the following straightforward decomposition (see Appendix C for the rest of the proof):
Proposition 1. For any wi E IRd,
ET S ||As(wo) - As(w") + [|As(w")
w0I1
+ +
E112 (IlAs (woo)l + |1²x)13))
(3)
Here, the first term (1) vanishes as long as the algorithm-map As is contractive on the aforementioned subspace, which we show in Appendix C.1 thanks to the closed-form expression of GD iterates.
Term (2) captures algorithm's 's sensitivity to the label noise: How far would GD go when initialized the minimum of the risk? Indeed, is easy see that when there is no label noise, term (2) is zero (one can demonstrate it by the descent lemma). In the presence of noise, matters are more complicated, and we employ a more or less standard technique where we recursively track the distance between GD iterates and "virtual" iterates, which are obtained as if we could remove the noise. This results in bound 4(o² //n) ( which is shown in Appendix C.3.
Finally, term (3) is essentially a concentration of the sample covariance matrix and ensuring that the norm of the solution remains well-behaved, see Appendix C.2. The concentration of the sample covariance matrix is due the matrix Chernoff inequality [Tropp. 2012]. We control the norm of the solution by relating it to the Moore-Penrose pscudoinverse solution which can be written in closed-form expression. This makes it easy to see that when the label noise is absent, the norm depends only on w" and wy- On the other hand, when the noise is present the behaviour of the bound will depend on behaviour of min as discussed in Section 3.2.
7

---

Ieerations 3000
number Iteratfors 10000
number of
agjn
Plx. Sep.TT/AAAAR
500 150 190 1018
30t Lie dec 198
30mh 05e 260 000
190 30c 1988 35th 2016 eds sox
158 506 Da0o 3MC 1900 20m 2018 eds edd
150 2000
300 580 3000 2016 100 ado
(b)
MNIST
ittrration 1000
numbber Sterations 10000
number Lorations
alpte 0.03
alph 0.05
abt
(a)
(b)
FashionMNIST
Figure Training one hidden layer networks of increasing width on MNIST (top) and FNSH (bottom): (a) Minimum positive eigenvalue of the intermediary features at initialization (b) Test emror and corresponding minimum eigenvalue the intermediary features different iterations
Empirical exploration in neural networks
The first natural question to ask whether the observed behaviour for the least squares problem reflected when working with neural networks. To explore this hypothesis, and to allow tractability of computing various quantities of interest (like ) focus MNIST and FashionMNIST datasets. We follow the protocol used by Belkin et al. [2019], relying on squared error loss. In order increase the model size we simply increase the dimensionality of the latent space, and rely on gradient descent with a fixed learning rate and a training set of 1000 randomly chosen examples for both datasets. More details be found in Appendix G.
hidden layer MLPs the
Fig. provides the main findings on this experiment. Similar to the Fig. 1, we depict columns showing snapshots at different number of gradient updates: 1000, 10000 and 100000. The first row shows test eиror (number of miss- mlas-classified examples out of the test examples) computed on the full test of 10000 data points which expected shows the double descent curve with peak around 1000 hidden units. Note that the peak is relatively small, however the behaviour seems consistent under random seeds for the MNIST experiment." The second and potentially the more interesting one looks at the X computed on the covariance of the activations of the hidden layer, which as predicted by our theoretical derivation shows dip around the interpolation threshold, giving the expected U-shape. Even more surprisingly this shape seems to be robust throughout learning, and the fact that the input weights and biases are being trained seems not to alter it, thus suggesting that our derivation might provide insights the behaviour of deep models.
'The error bars for the test error in all the other experiments are estimated by splitting the test set into 10 subsets.

---

1000
Reralions 10000
of 100000
0.00
indilatten
1880
3340
1800
180
6058
3008
1409
2009
2000
13:
1000
2000
1800
180
180
4000
1429
2000
30
(b)
Figure 3: Training networks of increasing width with I and 3 hidden layers MNIST: (a) Minimum positive eigenvalue of the intermediary features at initialization (b) Test error and corresponding minimum eigenvalue of the intermediary features at different iterations
Following this, if we think of the output layer as solving a least squares problem, while the rest of the network provides projection of the data, we can consider what can affect the conditioning of the last latent space of the network. We put forward the hypothesis that X is not simply affected by the number parameters, but actually the distribution of these parameters the architecture matters.
To test this hypothesis, we conduct an experiment where we compare the behavior of a network with a single hidden layer and network with three hidden layers. For both networks, we increase the size of the hidden layers. For the deeper network, we consider either increasing the size of all the hidden layers or grow only the last hidden layer while keeping the others to a fixed small size, creating a strong bottleneck in the network. Fig. 3 shows the results obtained with the former, while the effect of the bottleneck can be seen in Appendix F. We first observe that for the three tested networks, drop in the minimum eigenvalues happens when the size of the last hidden layer reaches the number of training samples, as predicted by the theory. The magnitude of this drop and behavior across the different tested sizes depends however the previous layers. In particular, bottleneck yields features that are more ill-conditioned than the network with wide hidden layers, where the width of the last layer its Moreover, from Fig. 3, we can clearly see that the features obtained by the deeper network have a bigger drop in the minimum eigenvalue, which results, expected in higher increase in the test error around the interpolation threshold.
observe that the
not compensate for the existence of the bottleneck.
It is well known that depth can harm optimization making the problem ill-conditioned, hence the reliance on skip-connections and batch normalization [De and Smith, 2020] to train very deep architectures. Our construction provides way of reasoning about double descent that allows to factor in the ill-conditioning of the learning problem. Rather than focusing simply on the model size, it suggests that for neural networks the quantity of interest might also be X for intermediary features, which is affected by size of the model but also by the distribution of the weights and architectural choices. For now we present more empirical explorations and ablations in Appendix G, and put forward this perspective as a conjecture for further exploration.
Conclusion and Future Work
In this work we analyse the double descent phenomenon in the context the least squares problem. We make the observation that the excess risk of gradient descent controlled by the smallest positive eigenvalue, X+ - of the feature covariance matrix. Furthermore, this quantity follows the Bai-Yin law with high probability under mild distributional assumptions on features, that is, it manifests a U- shaped behaviour as number of features increases, which we argue induces a double descent shape of the excess risk. Through this we provide connection between the widely known phenomenon and optimization process and conditioning of the problem. We believe this insight provides a different perspective compared existing results focusing on the Poorr-Penrooe pscudo-invers solution.

---

While we do not show the same formally for the more complex learning scenario of neural networks, our work conjectures the connection between the known double descent shape and model size is through Ami of the features extracted from the intermediary layers. For the least squares problem Xti correlates strongly with model size (and hence feature size). However this might not necessarily be always true for neural networks. For example we show empirically that while both depth and width increase the model size, they might affect X differently. We believe that our work could enable much needed effort, either empirical or theoretical, disentangle further the role of various factors, like depth and width or other architectural choices like skip connections on double descent.
Acknowledgements
We thank the anonymous reviewers for their helpful comments.
Csaba Szepesvári gratefully acknowledges funding from the Canada CIFAR AI Chairs Program, the Natural Sciences and Engineering Research Council (NSERC) of Canada, and the Alherta Machine Intelligence Institute (Amii).
Omar Rivasplata gratefully acknowledges funding from the U.K. Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/5526636/,, and sponsorship from DeepMind. This work was done while Omar was research scientist intern DeepMind.
References
A. Brock, S. De, S. L. Smith, and K. Simonyan. Nigh-performance large-scale image recognition without normalization. arXiv:2102.06171, 2021.
Brown, B. Mann, N. Ryder, M. Subbiah, Kaplan, Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, and A. Askell. Language models are few-shot learners. urXiv:2005.14166 2020.
A. W Senior, R. Evans, Jumper, J. Kirkpatrick, L. Sifre, Green, C. Qin, A. Zidek, Alexander WR Nelson, and A. Bridgland. Improved protein structure prediction using potentials from deep learning. Nature, 577(7792):06-771, 2020.
Schrittwieser, Antonoglou, Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, and T. Graepel. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):6044609) 2020.
D. Silver, J. Schritwieser, K. Simonyan, Antonoglou, A. Huang, A. Guez, Hubert, L. Baker, M. Lai, and A. Bolton. Mastering the game of go without human knowledge. Nature, 550(7676): 354-359, 2017.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, edition, 2009.
S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
M. Belkin, D. Hsu, S. Ma, and Mandal. Reconciling modern machine-learning practice and the classical varianar trade-off. Proceedings of the National Academy of Sciences, 116(32): 15849-15854, 2019. Previously 11X1v:1812.11118.
M. Belkin, D. Hsu, and Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-1180) 2020. Accessed from arXiv:1903.075:
L. Györfi, M. Kohler, A. Krzyzak, and H. Walk. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019.
10

---

M. Derezinski, F. T. Liang, and M. W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Vallet, J.-G. Cailton, and Ph. Refregier. Linear and nonlinear extension of the pseudo-inverse solution for learning boolean functions. EPL (Europhysics Letters), 94):311, 1989.
M. Loog, T. Viering, A. Mey, J. H. Krijthe, and D. M.J. Tax. A brief prehistory of double descent. Proceedings of the National Academy of Sciences, 1 117(20):0625--0000) 2020.
A. Rangamani, L. Rosasco, and T. Poggio. For interpolating kernel machines, minimizing the norm of the erm solution minimizes stability, 2020.
T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv:1903.083: 1903.0850,, 2019.
B. Adlam and J. Pennington. Understanding double descent requires fine-grained birs-variance decomposition. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: convergence and generalization in neural networks. In Conference on Neural Information Processing Systems (NeurlPS). 2018.
L.. Bartlett, A. Montanari, and A. Rakhlin, Deep learning: statistical viewpoint. Acta Numerica, 2021. URL https: //arxvv....i////// org/ abs abss/103..am 09177. To appear.
Nakkiran, G. Kaplun, Y. Bansal, T. Yang. B. Barak, and I. Sutskever. Deep double descent: Where
bigger models and more data hurt. In International Conference Learning Representations (ICLR), 2019.
Y. Yao, I. Rosasco, and A. Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-315, 2007.
Z. Ji, D. Li, and M. Telgarsky. 2021.
neural networks are consistent. arXiv:210..05932.
D. Richards and I. Kuzborskij. Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kerne. In Neural Information Processing Systems (NeurIPS), 2021.
I. Kuzborskij and C. Szepesvári. Nonparametric Regression with Shallow Overparamettrrized Neural Networks Trained by GD with Early Stopping. In Conference on Learning Theory (COLT), 2021.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, Theory and Applications, pages 210-268. Cambridge University Press, 2012.
Z.-D. Bai and Y.-Q. Yin. Limit of the smallest eigenvalue of large dimensional sample covariance matrix. Annals of Probubility, 21(3): 1993.
S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), 2015.
L. J. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization. CoRR, abs/1607.06450, 2016.
J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-4344 2012.
Q Nguyen, M. Mondelli, and G. F. Montufar, Tight bounds on the smallest eigenvalue the neural tangent kernel for deep relu networks. In International Conference on Machine Learning (ICML), 2021.
S. De and S. Smith. Batch normalization biases residual blocks towards the identity function in deep networks. In Conference on Neural Information Processing Systems (NeurIPS). 2020.
A. Ben-Israel and A. Charnes. Contributions the theory of generalized inverses. Journal of the Society for Industrial and Applied Mathematics, 11(3):667 -666,76699,60 1963.
S. d' Ascoli, I.. Sagun, and G. Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? In Conference on Neural Information Processing Systems (NeurIPS), 2020.


Reviews:
[{"review_id": "wStH974jaR_", "reviewer": "Reviewer_XaVR", "summary": "This paper studies the double descent phenomenon of linear least squares problems from an optimization point of view. Specifically,  the contributions of the paper lie in two parts: (1) for a linear least squares problem, an upper bound for the excess risk after T gradient descent iterations is derived by a contraction property of GD. The upper bound depends on the smallest non-zero singular value of the feature matrix, which is also related to the smallest nonzero eigenvalue of the Gram matrix. (2) The concentration of the smallest nonzero eigenvalue around its population counterpart is studied, and the discrepancy of the two is controlled. The control is provided separately for under-parameterized and over-parameterized cases, using existing random matrix theories. \n\nCombining the two components above, an upper bound of the excess risk is provided that shows a peak at the interpolation threshold. The bound depends on the number of parameters d, the number of data n, as well as the number of iterations T, hence it is optimization related. This bound only characterizes the peak at d=n, but does not characterize the first descent in the under parameterized regime. \n\nFinally, numerical experiments on nonlinear models such as neural networks are provided to show the similar double descent phenomenon and the behavior of the smallest singular value of the feature matrix. Here, the feature is taken to be the output of the second last layer. ", "questions": "", "limitations": "", "rating": 4, "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": "This paper tries to study and explain the double descent phenomenon from a new perspective. However, it does not provide much new insight for the phenomenon. The reasons are as follows:\n1. The object lying in the center of the analysis---the smallest nonzero eigenvalue of the Gram matrix---is the well known cause of the double descent phenomenon in linear least squares problems (including the random feature models), and is also extensively studied. In the works focusing on minimal norm solutions or ridge regression solutions, the same quantity is also studied and identified to be the factor that leads to the DD phenomenon. \n2. The upper bound for the excess risk only considers the smallest nonzero eigenvalue of the Gram matrix, which means it only controls the slowest component in the dynamics. Hence, the bound becomes tight only when the number of iterations, T, becomes large. Before this, the components corresponding to big eigenvalues dominate the dynamics and the DD phenomenon does not appear. This is showed by the empirical results in the paper. However, once T is sufficiently big such that the component of the smallest eigenvalue dominates the dynamics, the GD solution is already close to the minimal norm solution or the l2 regularized solutions studied in previous works. Therefore, the so-called \"the roll of optimization\" does not make much sense. Especially considering that the loss function is actually convex and any reasonable optimization algorithm will converge to a global minimum. \n3. For a linear least squares problem, the GD solutions and the corresponding population risk can be written down in close form. Hence, the reviewer does not see the necessity to derive the excess risk bounds via indirect approach such as (\\Delta, M)-admissible. Also, the (\\Delta, M)-admissible condition does not help extend the analysis to non-linear cases. \n\nSome other comments:\n1. Shown by numerical experiments on neural networks, it seems the peak of the generalization error happens when the width approximately equals the number of data. This is different that shown in Belkin et.al, in which the the generalization error peaks when the number of parameters = number of data * number of classes. Hence, this is like a different kind of \"double descent\". It is possible to provide more explanation on this phenomenon using the techniques employed in the paper?\n2. Some notations are confusing. For example, (a) the excess risk is denoted by E(w^*) while w^* is actually a fixed point. It is better to use E(A_S(W_0)) to highlight the dependence of the excess risk with the GD solution.  (b) the data us denoted by a capital X, which it is mentioned that vectors are denoted by boldface lower case letters. This causes confusion. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and societal impact of the work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jODTff_p5FX", "reviewer": "Reviewer_rFdx", "summary": "The paper studies the phenomenon of double descent (DD), and how different parameters of the problem affect this phenomenon. First, the authors show several theoretical results on linear predictors in the over-parameterized regime, with and without label noise. These results indicate that a certain eigenvalue of the data matrix affects the generalization error. Next, several experiments are shown on the MNIST and FashionMNIST datasets, that there is a correlation between this eigenvalue and the DD phenomenon.", "questions": "", "limitations": "", "rating": 4, "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 that DD is still not well understood, and studying it is important and interesting. Also, the connection between DD and certain parameters of the data or optimization is an interesting observation. On the other hand, I think this paper makes a weak case for why these parameters actually affect DD, especially on the experimental part, and vaguely connects the theory presented in the paper with the experiments. In more details:\n\nFor the theoretical part:\n1) I think the main idea is nice, studying linear regression in the case where d>n (more parameters than data examples), which is a less studied case in the literature. \n\n2) Viewing section 2 as a whole, it is hard to grasp a single conclusion on how the excess risk behaves. It would have been much clearer if there was a single theorem that shows a bound on the excess risk when d goes to infinity. In both theorems 2 & 3, there are terms where it is not clear how they behave (e.g. E[||w^*||^2]_{I-M}).\n\n3) To emphasize the previous point, two parameters are considered (n and d), and throughout the section it is unclear which one is considered to be larger. I assume the authors meant that d>n (since this is the over-parameterized case), but in line 163 (and Appendix F) it seems the E[||w^*||^2]_{I-M} term only goes to zero with large n, as well as the noise in Theorem 3. What happens in the over-parameterized regime when n is fixed and d goes to infinity? I think this is the interesting case when studying DD.\n\n4) Section 3 is very unclear. What are the assumptions made in the equation after line 216? What are the main conclusions of this section? There are very long paragraphs, where the bottom line isn’t clear.\n\nFor the empirical part\n1) I think this is the main weak point of the paper. The connection between the experiments and the theory is not well grounded. Also, the experiments are very lacking and not convincing enough.\n\n2) To emphasize, the theoretical part focuses on a certain eigenvalue of the data matrix. This eigenvalue has no connection at all to the optimization process and is fixed. On the other hand, in the theoretical part the authors consider the eigenvalue of the output of some intermediary layer, which changes through the optimization process. Why not take the eigenvalue of the data itself? And if the authors already decide to take the eigenvalue of an intermediary layer, I suggest taking the eigenvalue of all layers and comparing them. \n\n3) The only datasets used are MNIST and FashionMNIST which I think are very small and not very hard to learn, even with simple models. To give a more convincing argument I suggest using larger and harder datasets (e.g. CIFAR 10/100, ImageNet).\n\n4) The models considered are very small, e.g. one hidden layer and three hidden layers. I suggest experimenting on more realistic models and see if this eigenvalue has the same effect. Also, to experiment on other architectures such as ConvNets.\n\n5) There are no experiments on regularization (e.g. L1/L2, Dropout, BatchNorm). Regularization techniques might mitigate the effect of this eigenvalue on the DD phenomenon. Without these experiments, it is hard to evaluate whether this phenomenon is due to the effects of this eigenvalue, or some other property that can be mitigated using regularization techniques.\n\n6) In line 308 it says that ablation studies are in Appendix H. The only experiment in Appendix H is a three-layer network with or without skip connections. I suggest adding significantly more ablation studies to give a more convincing case.\n\nSome more issues:\n\n1) Why do the authors show the experiments for a different number of iterations? The reason is not explained in the paper, this is very confusing and takes three times as much space. I think the point of DD is looking at a trained model, if the authors want to emphasize some idea for an untrained model (e.g. after T=1000 iterations) then they should explain it.\n\n2) There are confusing notational issues throughout the paper: the parameters alpha and T are shown in the introduction, but are defined only in section 2. Some notations are used in the main part of the paper, but are only defined in the appendix (e.g. ||A||_M norm). It is OK to define some notations in the appendix, but if something appears in the main part of the paper, then I think it should be defined there.\n\n3) Line 131, what does it mean that \\Delta and W_0 are independent? Each coordinate of W_0 is i.i.d Gaussian, so how can it be dependent on \\Delta. Is it meant to be that \\Delta is independent of d?\n\n4) In all the theorems, why is W_0 upper case? This is a vector, and the notations state that vectors are lower case, also w and w^* are lower case.\n\n5) The figures are extremely small and hard to read. I suggest the authors to remove the different number of iterations experiments and just show how the trained model behaves, this will save much space and will allow to give much bigger and clearer figures.\n\n6) In lines 699-700 it states that “the deeper the network the harder it is to train them”, while Figure 6 shows the opposite, that deeper networks achieve smaller test error. \n\n7) The title is “On the Role of Optimization in Double Descent..”, while the paper studies how a certain eigenvalue of the data matrix affects DD. \n\n8) The \"related work\" section is in the appendix. Although this is allowed, in my opinion, this is bad practice. This section is a crucial part of the paper and helps the reader to evaluate its contribution and novelty, based on previous works that were done in the same area.\n\nSome typos and other minor issues:\n\n1) Sometimes “optimization” is used and other times “optimisation”. Both are OK, but the authors should be consistent and choose one form.\n\n2) Title of Section 3: parammeterization → parameterization\n\n3) In figure 1, “The first row demonstrates behavior of (1)...” what is (1)? The hyperlink points to the introduction section.\n\n4) First sentence of appendix F, should it be the over-parameterized case?\n\n\nTo improve the paper I suggest making a more thorough experimental study. This includes more realistic datasets, different architectures, Verify whether the conclusions hold with different regularization schemes, and conduct more ablation studies. Also, to connect the empirical results to the theoretical study I suggest looking at different architectures and network depths, and calculate the eigenvalue for more intermediary layers (including for the data itself). It will also help if the theoretical part will have a single corollary or theorem on how the excess risk behaves when d->\\infty, without any unclear terms such as E[||w^*||^2]_{I-M}.\n\n-------------Update after rebuttal---------------\n\nAfter reading the author's response my concerns remain, and I retain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "NAS-YlvpXoT", "reviewer": "Reviewer_g8ya", "summary": "This paper studies the double descent (DD) phenomena for least squares and proves upper bounds for excess risk of gradient descent. For both cases with and without label noise, the upper bound involves a term $E[(1-\\alpha \\hat{\\lambda}\\_{\\min}^+)^{2T}]$, where $T$ is the training time, $\\alpha$ is the learning rate, $\\hat{\\lambda}\\_{\\min}^+$ is the smallest positive eigenvalue of the covariance matrix of training inputs.\n\nThe most important observation in this paper is that the peak of the double descent curve around $d \\approx n$ can be related to $\\hat{\\lambda}\\_{\\min}^+$. By a non-asymptotic version of Bai-Yin limit, $\\hat{\\lambda}\\_{\\min}^+$ could be very small when  $d \\approx n$, and thus $E[(1-\\alpha \\hat{\\lambda}\\_{\\min}^+)^{2T}]$ can be very close to $1$ when $T$ is finite.\n\nExperiments show that $\\hat{\\lambda}\\_{\\min}^+$ for intermediate features correlates with the double descent curve of test error.", "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 like the idea of relating DD to the smallest positive eigenvalue $\\hat{\\lambda}\\_{\\min}^+$ of the covariance matrix, which seems to give a fairly new perspective on the DD curves. But I'm not an expert in DD as I only read a few related papers. Thus I think a detailed comparison with previous papers is important for me to have a proper evaluation for this paper. However, the related work section is in the appendix, not in the main body of the paper. Also, comparisons with some closely related papers are not detailed enough. The authors mentioned that [Derezinski et al., 2020], [Rangamani et al., 2020], [Hastie et al., 2019] also noted that $\\hat{\\lambda}_{\\min}^+$ is important in explaining double descent, but the key difference to the current paper is not very clear to me if I only read the related work section. I would suggest the authors add more details:\n\n1. What are the assumptions on the data distribution in previous works? How do they compare with those in the current paper?\n2. How do those papers find the connection between DD and $\\hat{\\lambda}_{\\min}^+$ without studying GD optimization?\n3. If they prove double descent without considering GD optimization, does it mean optimization is not a crucial factor to make double descent occur? The authors claim that the current paper is superior as it considers GD optimization, but it should be justified that GD optimization is crucial in the first place.\n\nUnlike some previous papers, this paper does not assume an explicit formula for the data distribution. This is an advantage of this paper as it can hold for broader settings. However, this also makes it impossible to derive an exact formula for excess risk. Alternatively, the authors study the upper bounds, but no lower bound is given. Lower bounds are especially important for explaining the peak because having an upper bound $\\approx 1$ can be either because there is a peak or the upper bound is not tight enough. I would like to see the authors' argument about the tightness of the upper bounds. Empirical evaluations for those upper bounds may also help.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The major limitation of this paper is that it only provides the upper bounds, as discussed above.\n\nBesides this, the theoretical analysis of this paper only holds for least squares and cannot be extended easily to deep neural nets. But the authors did MLP experiments on MNIST to show that similar phenomena can happen for intermediate features, and I understand that studying deep neural nets is hard.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers reached a consensus by which the paper is not ready for publication.  Several concerns were raised, most notably:

* Only an upper bound on the excess risk is derived, which is insufficient for establishing a double descent phenomenon (for that, a matching lower bound is required).

* While experiments indicate that the upper bound may be tight after many iterations, it seems that in the early phases of a run it is not.  This is particularly problematic since in late stages of a run the model may in fact be close to convergence, and at convergence optimization reaches the Moore-Penrose solution, which was heavily analyzed in prior work (hinting that the regime in which the analysis is valid is one that is already well understood).

* The experiments on deep neural networks are somewhat disconnected from the theory, and this warrants a more thorough empirical investigation.

I encourage the authors to make use of the above feedback in revising their paper towards future submission.
Decision: Accept (Poster)