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.
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.
Notation:
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-asy 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 - 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
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-Gaussiar 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 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. SeA.TT/AAAA
500 150 196 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 2000 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- clas-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 bias-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...vi////// 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 Overparametterized 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": "obOgFBshpho", "reviewer": "Reviewer_bMDY", "summary": "This paper proves an excess risk bound for linear least squares regression problems in an overparametrized setting which takes into account (a proxy of) the condition number of the optimization when done via Gradient Descent. The bound allows to shed a new light on the Double Descent phenomenon. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "The main originality here is to argue that DD is a result of optimizing the parameters using gradient descent and that its precise form depends mainly on the minimal positive eigenvalue of the sample covariance matrix.\n\nThis point of view is, in my knowledge, new and the bounds shown are sharp enough to allow some meaningful analysis. In particular, there seems to be a nice fit between predictions of the theory and the empirical results.\n\nRegarding presentation, I think the writing could be improved. The text is quite dense and the paper wasn't easy to read in some places. I also think that theorems 2 and 3 could be summarized as the same result. This would free some space to transfer some experiments and discussions from the appendix.\n\nMy main problem with this work, which is also acknowledged by the authors at the last section, is its lack of applicability to deep neural architectures: while the tools of analysis are presented as being potentially useful for modern models (in the abstract and in the introduction), nothing here points to the truth of that and I don't see how the same type of bounds could be proved for actual DNNs.\n\nAnother more minor point is the dependence on the number of steps T: It is known that there is a DD phenomenon wrt T, and this is not represented in the proven bounds as I understand them.\n\nEdit after rebuttal: I thank the authors for their answer to my review. I hope they will be able to incorporate them in the camera ready version of the paper. I think this is a good contribution and raise my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical and there are no such considerations here. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "m3ojRpvNEoi", "reviewer": "Reviewer_uq7X", "summary": "This paper deals with the double descent phenomenon in the setting of least-squares regression by gradient descent. Similarly to a number of recent works, it shows a double descent behavior for the excess risk: a U shaped curve until the number of features coincides with the number of datapoints. The main contribution of the paper is to relate this peak around interpolation to the learning dynamics of the problem at hand. More precisely, the main result (Theorem 1) is an upper bound on the excess risk where the dynamics of learning are explicitly present. This result is specialized to the case of least-squares with random design in the noiseless setting (Theorem 2) and with Gaussian noise independent from the inputs (Theorem 3). In both these cases, the dominating term is controlled by the smallest non-zero singular value of the sample covariance matrix. Therefore, under some assumption on the data, one can get precise asymptotics by using the Bai-Yin result. This is done in Section 2.3 in a non-asymptotic fashion. The paper concludes by an empirical study on neural networks with one and 3 hidden layers, showing a link between the smallest eigenvalue of the covariance of the intermediary features at initialization and the test error.  ", "questions": "", "limitations": "", "rating": 8, "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": "***Main comments***\n\nThe paper is overall very interesting, and well-written. The proofs are correct as far as I can tell, I have only one small technical question detailed below. I think that the link between optimization and double descent was not addressed by previous work and is a very exciting new avenue of research. The precise expressions obtained in the paper depend on strong assumptions and in the particular case of least-squares. These are the main limitations of the paper. The empirical argument does not seem so strong.  More detailed comments follow:\n\n - statement of Theorem 2: the reason for a high probability statement in Theorem 2 is unclear to me. Maybe I am missing something here, but the only sources of randomness here are S (the sampling) and W_0 (the initialization). As far as I understand the proof of Theorem 1, from which Theorem 2 is a consequence, the expectation is taken with respect to both these sources of randomness. Therefore it seems that this statement should not be there. This statement is also not present in the Appendix. The same question holds for Theorem 3. I will increase my score if this is properly addressed by the authors.\n\n - l. 47: my understanding of Belkin et al. '19 is that the test error *can* be lower in the overparametrized regime, but not necessarily. \n\n - stochastic gradient descent: the main optimization tool for recent architectures is SGD. Can the present analysis be extended to SGD instead of GD? The main obstruction seems to be proving that SGD is (\\Delta,\\Mhat)-admissible, with of course another \\Delta. What would be \\Delta in that case. \n\n***Typos and minor comments***\n\n - l. 211: parammetrization -> parametrization\n - Figure 2 and 3 are hard to read, I would suggest using bigger fonts for the x- and y-axis.\n\n***After rebuttal***\n\nThe authors have properly addressed my concerns, I am therefore increasing my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "HAooNRjyKjA", "reviewer": "Reviewer_bWET", "summary": "This paper studies the double descent behaviour in the context of least squares, using a theoretical analysis of the spectrum of the feature covariance matrix. It conjectures that the double descent (in this case) is a consequence of the behaviour of the smallest positive eigenvalue.", "questions": "", "limitations": "", "rating": 7, "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": "In summary the paper is very well written and flows nicely. The double descent behaviour remains a major open question un deep learning theory. Although the analysis in this paper is restricted to the least squares case, it is still a valuable contribution to the litterature.\n\nDetails and questions:\n\n- The main result is that the U-shaped curve of the smallest positive eigenvalue of the feature covariance matrix is the reason behind the double descent behaviour (in the least squares case), this is reflected in the generalization bound provided in the paper. The empirical results confirm the theoretical claims.\n\n- Extending the analysis to deep networks might not be feasable, but I believe that using a simplification of deep nets such as the NTK regime (linearized) might be a very nice addition to this paper.\n\n- Recent works have shown a triple descent behaviour for deep nets (e.g. d'Ascoli et al. Triple descent and the two kinds of overfitting: Where & why do they appear?). Could the authors comment on how the smallest positiove eigenvalue behaves in this case? (since the U shaped curve would no longer explain the triple descent )", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the double descent phenomenon for least-squares regression with gradient descent optimization, showing a double descent behavior for the excess risk, and relating this peak around interpolation to the learning dynamics of the optimization algorithm.  All reviewers agreed that the paper made a useful contribution for the community.
Decision: Accept (Poster)