Least Squares Regression Can Exhibit Under-Parameterized Double Descent
Authors: Xinyue Li
Rishi Sonthalia
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning Theory
Generalization
Random Matrix Theory
High Dimensional Statistics
Primary area: learning_theory
TL;DR: We show that the current theory for double descent is incomplete

Abstract: The relationship between the number of training data points, the number of parameters, and the generalization capabilities of models has been widely studied. Previous work has shown that double descent can occur in the over-parameterized regime and that the standard bias-variance trade-off holds in the under-parameterized regime. These works provide multiple reasons for the existence of the peak. We postulate that the location of the peak depends on the technical properties of both the spectrum as well as the eigenvectors of the sample covariance. We present two simple examples that provably exhibit double descent in the under-parameterized regime and do not seem to occur for reasons provided in prior work.

Least Squares Regression Can Exhibit Under-Parameterized Double Descent
Xinyue Li Applied Math, Yale University xinyue. 1i 11.x17288yale edu
Rishi Sonthalia Math, Boston College rishi. sonthal www.alaaaa........o edu
Abstract
The relationship between the number of training data points, the number of parame- ters, and the generalization capabilities of models has been widely studied. Previous work has shown that double descent can occur in the over-pane wver-paaameterized regime and that the standard bias-variance trade-off holds in the under-parameteriin regime. These works provide multiple reasons for the existence the peak. We postulate that the location of the peak depends on the technical properties of both the spectrum as well as the eigenvectors of the sample covariance. We present two simple examples that provably exhibit double descent in the ander-parameterized regime and do not seem to occur for reasons provided in prior work.
Introduction
This paper demonstrates interesting new phenomena that suggest that our understanding of the relationship between the number of data points, the number of parameters, and the generalization error is incomplete, even for simple linear models. The classical bias-variance theory postulates that the generalization risk versus the number parameters a fixed number training data points
U-shaped (Figure b. However, modern machine learning has shown that if we keep increasing the number of parameters, the generalization error eventually starts decreasing again 2 3 (Figure
L. This second descent has been termed double descent and occurs in the over- parameterized regime, which when the number of parameters exceeds the number of data points. Understanding the location and the cause of such peaks in the generalization error is of significant importance.
Totel Coer
under underr-paramtterin
over-parameterizen
Test risk
Risl
"classical"
"modern" interpolating regime
regime
Blas?
Training risk
interpolation threshold
Compiexity
Capacity of H.
Classical Bias Variance Trade-off.
(b) Modern Double Descent.
Figure 1: Bias-variance trade-of off and double descent.
Many different theories have been postulated for the appearance of the peak. The prevalent theory that when the model is under-paramettrizee,, the learning constrained. This constraint on the
Image source Image source
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

learning results in increased variance until the interpolation point. After this point, there exists a high dimensional space of solutions, and learning methods, such as gradient descent, pick solutions that generalize well. This conjecture has been empirically validated for deep neural networks. Due to the challenges of analyzing deep neural networks, theoretical understanding of this phenomenon has focused on linear models- linear regression [4)3 and kernelized regression (14)22). These works show that there exists a peak at the boundary between the under and over- over-parameterized regimes. Hence validating the above postulated theory for their setting. Careful theoretical analysis then shows that the generalization error can be decomposed into various terms, one of which is the norm of the estimator. Specifically, it has been shown that the curve for the norm of the estimator versus the dimension of the data also exhibits double descent, with the peak occurring at the same point as the peak in the generalization error curve. In most cases, this is the only term in the decomposition that exhibits double descent. This leads to second theory for the occurrence of the peak, that is, the peak in the generalization error for linear models occurs due to the norm of the estimator blowing up.
Contributions. Since understanding the reasons that peaks occur is of critical importance, it is crucial that we have a robust theory for their appearance. However, most work focuses on the over- parameterized regime and ignores the mnder-parameterized regime. This is because it is commonly believed that the variance is monotonic in the under- parameterized regime. We show that this is not true and present two simple examples that exhibit double descent in the under-parant paader-prammttriieed regime.
Why does the Peak Occur. We argue that the location of the peak depends on two factors: the alignment between the targets y and singular vectors V of the training data matrix and the spectrum of the data. We show that by modifying these quantities appropriately, we can move the peak into the underparameterizzd regime.
Modifying the Alignment. For the first example, we consider a spiked covariate model, where one cigendirection dominates, and the regression target only depends on the dominant cigendirection. For this model, we consider the ridge regularized problem with ridge parameter μ₂² and show that the ridge parameter μ² controls the alignment between the targets y and the singular vectors V. We show that for μ. > 0 the peak occurs in the under-parann paterrrrraameezzeeddd regime (Theorem 2). Specifically, when the ratio of the dimension to the number of training data points e is equal to (1 + 2²)-
(c = d/n- = 1/(1 + )²))).
Modifying the Spectrum For the second example, we consider training data that is mixture of isotropic Gaussian vectors and vectors from along fixed direction z. By varying the mixture proportions (TI W2), we can modify the spectrum of the covariance matrix. We show that the expected risk displays andatt-ara double descent (Theorem T. with the peak occurring when c = d/n = I.).
Norm of the estimator. We further analyze the first example and show that if we fix the number of training data points n and vary the dimension d of the problem, then for large values of μu, the risk curve does not display double descent. However, the curve for the norm of the estimator does display descent. Thus, the peak in the norm of the estimator does not imply a peak in the generaliation error.
Organization. The rest of the paper is organized as follows. Section 2 presents a quick overview of prior work on double descent for linear models. Section highhlghss two less-studied properties that influence the location of the peak. Section 3 presents the first of the two examples of under- parameterized double descent. This model also shows that a double descent in the norm of the estimator does not translate double descent in the risk. Finally, Section presents the second example of under- mnder-parameterizee double descent.
Prior Work on Double Descent
In this section, we present the current prevailing theories for the occurrence of local maximums the risk curve. Concretely, consider the following simple linear model that is a special case of the general
11 23 amongst many other works. Let I; ~ AO(,, Ia) and let 3 E Rd be a linear model with 3 L.t v. 3d x, + & where & ~ (O,0,) 1). Then, let Bope be the minimum norm solution to arg ming 118" -3 X + Errall where Eirn E 1 One important quantity the aspect ratio of X. Specifically, for a d x n matrix, the aspect ratio e == d/n. With this terminology, we see that model is under- padaeeparameterized if 1 and over- aver-parameterized when > 1.
models studied in 5
8
2

---

Table I: Table showing various assumptions the data and the location of the double descent peak for linear regression and denoising. We only present a subset of references for each problem setting. For the low rank setting in this paper, Appendix F
Noise
Ridge Reg.
Dim.
Peak Location
Reference
Input
Yes
Under-paut pareerr-aatterzeedd
This paper. This paper
Output
No
Full
Under- Under-paramnen parameterized
Input
No
Low
Interpolation point
24 37
Input
Yes
Full
Interpolation point
38
Output
No
Full
Over- peeeppaaattrizz//neeppplleee point
Output
Yes
Full
Over- paraameterizzcd//neepplltooo point
Output
No
Low
Over Over weee-prcameeeriicc//eeepppioiiip point
Output
Yes
Low
weer-prrannterizee//nepppoooiiio point
40
Output
Low
No peak
Finally, the interpolation point, i.e., the point which we can exactly fit the training data, is assuming we have full-rank data.
Then, the excess risk R and the expected norm of Bopt be expressed follows:
{ 1 + e<1
<< 1
and
Popt
- 1++ c>1
c>1
In this model, there are few important features that are ubiquitous in many prior double descent studies for linear models:
1. The peak happens e 1, the border between the under and over-parameterizzed regimes.
2. Further, at = the training error equals zero. Hence, this the interpolation point.
3. The peak occurs due to the expected norm of the estimator Sopt blowing up near the interpolation point.
This is further validated by works that study ridge regularized regression 23 26
Works such as 23 have shown that optimally regularized regression no longer exhibits double descent. Further, increasing the amount of regularization from zero to the optimal amount regularization results the magnitude of the peak in the generalization getting smaller until peak no longer exists. However, the location of the peak does not change by changing the amount of regularization. Further, Chen, Min, Belkin, and Karbasi [27] proved that double descent cannot take place in the paddtt-prrmmeterizeed regime for the above model.
28 31 show that there can be multiple descents in the over- parameterized regime. Specifically. d' Ascoli, Sagun, and Biroli (30) show that the first peak in triple descent is due to the norm of the estimator peaking and that the second peak is due to the initialization of the random features. Their results, Figure in (30), show that the peaks only occur if the model is parameterized. Further Chen, Min, Belkin, and Karbasi (27) show that by considering variety of product data distributions, any shaped risk curve can be observed in the over-parumeterized regime. Finally, Curth, Jeffares, and van der Schaar [32] says that the peak occurs at the point of effective dimensionality of the model and not the true dimensionality. Here, we see that there are three other reasons provided for the occurrence of peaks in the risk curve.
Subsequently, works such 10
23
Regularization can reduce the effective dimensionality of the model and move the peak to the right into the wer-parameterizeed regime (32).
2. For random feature models, we see that the random initialization results in a second peak in the over parameterzee regime [30].
3. Due to the data having a complex covariance structure, any shaped risk curve is possible in the peeepparamttrizeed regime (27).
Other works (3] have considered the problem for other loss models and shown a variety of different risk curves can exist. Table summarizes some of the prior work.

---

Double Descent with Input Noise. There has also been prior work that studies double descent for
models with input noise rather than output noise [24 37 38). From these Sonthalia and Nadakuditi (4) and Kausik, Srivastava, and Sonthalia (37) consider the unregularized problem and show that the peak occurs the boundary. Dhifallah and Lu (38) considers ridge regularization with isotropic
Gaussian data and again sees that the peak occurs at the boundary.
3 Spectral Properties of the Data Affect the Peak Location
In this section, we identify two important spectral properties that govern the location of the peak. In later sections, we delve into two examples that modify these properties and move the peak into the ander-parameteriieed regime. We begin with definitions and notations. Throughout the paper, we assume that training data X [x] In. E IR and y = [V ..., R We are interested in the standard ridge regularized least squares problem.
min Ily 3 XI 1111
In the unregularized case, the minimum norm solution is given by 3 yxt, where Xt is the Moore-Penree Penrose Pseudoinverse of X. Prior work on linear models has shown that a double descent in the risk is due to double descent in the norm of the estimator. Suppose X UVVT is the SVD, B Rdx1, then using unitary invariance, we have that
| rank X) Σ
(yV)
where is the ith singular value. Hence, this is controlled by
1. The alignment between y and Here V are the eigenvectors of the data gram matrix.
2. The spectrum of the gram matrix XT
Many prior works deal with the alignment in of ways. If 3 E. with & having isotropic distribution, then prior works either assume that 33 has an isotropic distribution (4 42 or they assume that is isotropic Gaussian or that x; = 11/² z4. where 2; is from an isotropic Gaussian 23 43) and Σ a deterministic matrix. For example, if has an isotropic distribution, taking the expectation with respect to B, & we get that
rank ())
E3, [1 = E| ELS
Σ
This quantity is then studied by looking at the distribution of the spectrum as d, n + cc. Definition 1. Given random matrix A, if >,,..., > are its eigenvalues. Then the empirical spectral distribution (ESD) is the following sum of Dirac delta measure
8
and the limiting spectral distribution is measure such that " + v weakly almost surely.
In general, the limiting distribution ve depends on the limiting aspect ratio (i.c., d/n c). Definition 2. Given a measure Ve that is supported on the interval J c. R. the Stieltjes transform is
1 ] SECIJ.
My, (C) = EX~r
One common assumption is that the limiting distribution the empirical spectral distribution Marchenko-Passee distribution (44). Other limiting distributions have been considered in (5) 45 46
the
For the Marchenko-Pastu distribution, it is known (see, for example, Lemma (24 that
1
c<l
my. (0) EAwee
e>1

---

Hence, the risk is governed by the value of the Stieltjes transform of the limiting spectrum at 0. In particular, for the above example, the location of the peak of the risk function of depended on the location of the peak of
C. - my (0) =: G(c)-
Hence the risk depends on both the spectrum and the alignment between y and V. Thus, the peak occurs at = because of the following two conditions.
Alignment of y and right singular vectors of
Assumption 1. X UEVT is the SVD, then yV is isotropic.
Stieltjes Transform Peak Assumption
Assumption 2.
The function + my (0) =: G(c) has a local maximum at =
In this paper, show that violating either one of the above two assumptions can move the peak from interpolation point into the inder-parameterized regime.
Alignment Mismatch
In this section, we present the first example that exhibits double descent in the under-parameterized regime. This model violates Assumption
4.1 Model Assumptions
For any k S d, let Rdxk be fixed such that the operator norm ||BT || @(1). Let Xten E Rdxx be the signal matrix and Atrn Ædx= be the noise matrix. Then, the ridge regularized least square estimator W ope is the minimum norm solution to
Wopt opt
arg min 1| Xtrn
WX Atmr) 11
W
Given test data Xest Aests the mean squared generalization error is given by
x Xest
Wopt + Aest) 1b
R(Wopt =E EEr
(2)
That
Assumption 3. Let U C. Id be dimensional space with unit basis vector Then let Xtrn Otrn -rrruuy E Bd and Xist = Ttaeuiys E Bddxast be the respective SVDs for the training data and test data matrices. We further assume that Otrn O(vr) and dist O (tatt.
There are no assumptions on the distribution of Utrn, Vtst besides having unit norm. First, we see that the data X + A has a spiked covariance, with the dominant cigendirection closely aligned with u. Since the targets only depend on X, we consider A to represent noise. Even with the rank I assumption, the model captures many different scenarios. If k then the problem is similar to error-in-vaan invviiabllees regression. If k = d and B I, then this is the supervised denoising problem. If the columns of Xtrn are all +u and 3 u, then this captures the binary classification problem (with MSE loss) for two Gaussian clusters centered at u and -u t with labels +1.
Assumptions about A. The analysis works for general assumptions in (24). For simplicity, we assume that the matrix A has LLD. entries drawn from normalized Gaussian. Assumption 4. The entries of the matrices A E Bdxxa are I.I.D. from ((00 1/d).
4.2 Expected Risk and Peak Location
We begin by providing formula the generalization error given by Equation for the least squares solution given by Equation [ All proof' are in Appendix
5

---

Theorem 1 (Generalization Error Formula). Suppose the training data Xtrn and test data Xtst satisfy Assumption 3 and the noise Atrn:Asst satisfy Assumption 4 parameter. Then for the uuder-parameterzzer regime (i.e, < for the solution Wapt to Problem
Let μ be the regularization
the generalization error or risk given by Equation 2 given by
cotr (o +1))
1 +Fc
00 (o + +1)
gitt +0 Dest
(2)
R(c, u)
+T
2d1
V(1-o+ c+ c2) + 2
2d
where
1
2 21 ul
2 Pm (1 + c p²c v(1 c c + 4112(2)
Sketch. The proof proceeds in four key steps. First, we use the Sherman- pseudoinverses [47]. Next, we decompose the error into constituent dependent quadratic forms. Through random matrix theory and concentration of measure arguments, we demonstrate that each quadratic form concentrates around a deterministic value characterized by the Stieltjes transform of the limiting empirical spectral distribution. Finally, we establish concentration bounds for the products and sums of these dependent forms, yielding the desired error rate.
formula for
regime, Theorem | only presents the under- Since the focus is on the wver-paramterized case can be found in Appendix EE3] Due to the parameterized case. The over complexity of the expression, it is difficult to discern how the risk scales with respect to the training data signal strength dinn. the regularization strength μu, or the aspect ratio c. Since the focus of the paper the scaling with respect to c, we present the connection between the risk curve and in the main text. However, the shape of the risk curve with respect to the other parameters also interesting and can be found in Appendix [
To understand the shape of the risk curve as e varies, we first consider that data scaling regime. That is, fix d and change The following theorem 2 shows that the risk curve is theoretically guaranteed to have a peak at T+
Theorem 2 Sander-Parameterizee Peak). Let μ. E R20, sufficiently large, so that the error term o(1/d) small, then the risk from Theorem as function of c, has a local maximun in the eeder-paramettriied regime at c 1+p²
d/c and oist = Dest and d is
Theorem 2 contrasts with prior works, in which double descent occurs in the over- parameterizeed regime or the boundary between the two regimes. We numerically verify the predictions from Theorems I andd 2 F sshows shows that the theoretically predicted risk matches the numerical risk, thus verifying that double descent occurs in the under- paddee--rrmeetrrizeed regime!
Generalization Errer
Repuretteteed Rogims
Emipiicil piz
Generalizaaion Eror
6:20120
Empercall
Generalization Error
6:00111
Under Reyere
Experce
606-
Paak
0.00113
620118
Puak
8.00103
8.00115
yiz
0.00
8-00/04
8:00107
8.00004
000111
6.00105
533 625
dfN
2000
200
200
1.7 2207
330 011 1000 150 2000
Figure 2: Figure showing the theoretical risk curve from Theorem D and empirical values in the data scaling regime for different values of μ. [(L.) μ 0.1, (C) μ 1, (R) μ 2]. Here Otrn. = ots = / /itst: 1000, nist 1000. For each empirical point, we ran least 100 trials. More
details can be found in Appendix G
3 All code for the experiments can be found at http:://hhhhb.comm/oontllllleen
Double.
Descent

---

4.3 The Peak Occurs Due to Alignment Mismatch
We now show that the peak occurs due mismatch between the target vector and the right singular vectors of the input data. To begin, note that the ridge regularized problem can be written as follows
1|
[trrn Oaxd - ([[[
Oaxa] [Atrn Jul II
N
Agen
In this expression, y = Xtrm (3"T))(( [M( 0p] Hence the direction is given by o = [v Opl- The right singular vectors of Xtrn Atr are more difficult to compute,thus we use proxies. Since Xern is rank 1, we use the right singular vectors of Atr proxy. Lemma in the appendix, shows that if A UEVT, then
express Aer as UΣVT, where Ü -.. = 1²1, and
Vi E
V-
E gu+ddd Here Vind are the first d columns of V. Then,
pUS-1
yV = (8 ()F Viaa)
Since Vidd came from a Gaussian random matrix, (6 Via) has isotropic entries. However, the diagonal matrix - results in the entries of yV not being isotropic. Note when = 0, ΣΣ = L, hence it isotropic. Hence, μ controls the deviation from isotropy.
We use ΣT proxy for the spectrum of the sample covariance. By Lemma - p²2. We know that the limiting spectrum for 2 is the Marchenko-Pass distribution for which the map G(c) my (0) has a maximum for 1. Shifting the spectrum changes the magnitude of the peak but does not change the location. This suggests that the peak occurs due the misalignment between the target vector and the right singular vectors of the input data.
have that
Ablation experiment To verify that the location of the peak is due to the misalignment, two experiments. First, we solve the unregularized problem. However, we change the spectrum of the noise matrix Atr-- That is, instead of using Atr = UEVT, we use Å U( + 1,2r))/277 If the spectrum was the primary factor determining the location of the peak, the peak should occur 1= + 2²) However, seen in Figure 3 it still occurs uniformly random orthogonal matrix Q Clearly, yQ is now isotropic. Figure 3 shows that, in this case, the peak moves the over- wver-parameterized regime.
conduct
1. Second, replace V with
p=1
Generalization Risk
Generalization Risk
30.
201
Figure 3: Risk for the ablation experiment. Left: Empirical Expected Risk when using for the noise. Right: Empirical risk when we replace V with a random orthogonal matrix.
Connection to Prior Double Descent Theory Prior double descent theory postulates that the peak for the ridge regularized model occurs at the interpolation point for the unregularized model or further to the right into the over-paran wer-paraaeterized regime. Hence, this model goes against prior expectations, with the peak moving to the left into the under-parametenn some connection between the training erтor and the location of the peak. For example, the peak may correspond to a local minimum of the training loss. We explore this in Appendix C and see only weak connection with the third derivative of the training error.
regime. However, there might still be
'ee obtain such matrix by computing the full SVD of Gaussian random vector in Pytorch

---

4.4 Peak in the Norm of the Estimator Does Not Imply a Peak in the Risk
Prior double descent theories suggest that double descent occurs due to the norm of estimator increasing and then decreasing. This is true for the above model where we fixed d and varied How- ever, the connection breaks we fix n and vary d instead (parameter scaling regime). This difference between the two regimes is due to the normalization considered and has been observed before (30].
Figure 4 shows that for the parameter scaling regime, for small values of μ. we see under- parameterized double descent. However, as we increase μ,, the risk curve becomes monotonic. Nevertheless, as shown in Figure for larger values of μ. there is still peak the curve for the norm of the estimator [ ope i.. Hence, the curve for the norm of the estimator exhibits under- parameterized double descent even if the risk does not. This is further highlighted in Figure O Here, we see that even though the variance is non-monotonic, the risk is dominated by the bias term. Thus, we show that a peak in the generalization error for linear models does not imply a peak in the norm of the estimator. The following theorem provides local maximum in the E [ opt [px] curve for 1.
Theorem (|) ll Peak). o = Rist trn = V and y is such that p(u) < O, then for fixed that is sufficiently large enough, have that E [|pelll versus d/n curve has local regime al (u² 1)_
maximum in the
0.010
Under
brosttal
Under Regine
Generalization Errer
0.010
Uedet legire
Irp p/r
phr Prok
zh
Generalization
Bag me
1,866
8.006
0.004
0.004
0.322
0.022
c= d/Nem
c= d/Ners
c= d//enn
Figure 4: Figure showing the theoretical risk curve from Theorem 1 and empirical values in the parameter scaling regime for different values of μ [(L) μ = 0.1, (C) = 0.2, (R) μ = 0.5]. Here, only μ = 0.1 has local peak. Here n = Tist = 1000 and dern = dest = /1000. Each empirical point is average of 100 trials.
Error
0.111
10
0330
1.0
Generailzattoon Error
0.330
0.000
0.co9.
8.000
0.c0-
8.066
0.007
Genera
3.
04
0.00
0.004
0.005
6.022
0.04.
1375 1,00
1:12 3:30 1,775
1,200
3.0
1.09
1,235
3.000
1.0.5
1.000
[[]]
(a)
1. 0.1
(b)
(c)
2
Figure 5: Figure showing generalization error versus E [ opt [ for three different values of μ..
for the parameter scaling regime
Shifting Local Maximum for Stieltjes Transform as a Function of c
In this section, we present the next example of under-parameterized double descent that violates Assumption 2 In particular, the maximum of the map ++ my. (0) does not occur at 1. We show that the maximum can be chosen to be any value in (0, 1). We consider the following mixture model. Let Tı, T2 be mixture weights such that π + π2 1. Then, with probability Ti, the data is sampled from (00 7) and with probability T2, the data point is az for fixed 2 E IRd and a ~ N(0 1). For this model, the uncentered covariance matrix is given by
Bxr x E E
[x="
22
H I + T222
d
8

---

6.8012
Empiiaal
120
Emprrall Theay
0.02
Emprica Theel
110
7
Gentrolization
Under Tarameturiad
0.005
Under Parameaaree
6-00366
2.01
6,8364
100
1:0
Under Tar amratetree
0,002
600300
325 636
1.0
130
723
0:55
di
did
(a) Bias
(b) |
(c) Generalization Error
Figure 6: Figure showing the EE' [ opt
oWooellll) [1 and the generalization error in the parameter scaling
regime for 1, ten VT, and tst Mist. Here 1000 and Rest 1000. For each empirical data point, we ran at least 100 trials. More details can be found in Appendix
Then, the expected excess risk for solution 3 compared to / is
R = Ei1l8"> x BT x = I. 13 3/ + 3 -=)
Let Xtrn [A zu'1 Rdx_ where the A Rdxa-k with each column data point sampled I.I.D. from (0, 7) and E R* is the vector with random coefficients in front of Let / E IR& be the target regressor function and let y" "x
8d Xtrn Eir where </i has LLID, entries from a standard normal. Let Pepu = =y"X7 1 (Xtrn X trn -rrm- be the minimum norm. Then, Theorem 4/ shows that the peak occurs when d/n
T1 < 1. To experimentally verify Theorem 4 we consider two cases, one where enforce 3 1 2 and one where we do not. As seen in Figure 7 Theorem I accurate for both cases. This suggests that the 3 assumption seems to only be needed for simplifying the proof.
10
Emprirical Risk
10a
Emprirical Risk Theoretical Risk
Theoretical Risk
10
10a
Risk
Risk
10
10a
100
109
0.4
0.6
0.8
1.0
1.2
0.4
0.6
0.8 Man
1.0
1.2
Mon
Figure Figure showing under- sateer-pratttrizeed double descent. (Left) We have d 2. (Right) We
have B 1 z. The solid blue line represents the theoretical estimate from Theorem 4 and the scatter points are from empirical experiments with 600. For the empirical points, we average over 50 trials. The dashed vertical purple line is π.
Theorem 4 (Under-parametting Peak). For the above model, if + nT, and d/n c, then the Wi
n
expected risk is given by R
=1 (
12
2) E
m
n
Theorem is quite surprising as it shows that the only peak in the risk curve occurs in the under- parameterized regime. One might assume that due to the low rankness of the data from the second mixture. While this is true, prior work does not indicate that this is the reason. Specifically, Huang, Hogg, and Villar [41] shows that projecting onto low-dimensional versions of the data acts as regularizer and removes the peak altogether. Xu and Hsu (39), also looks similar problem, but they consider isotropic Gaussian data and project onto the first p components. In this case, the data is artificially high-dimensional (since only the first & coordinates non-zero).

---

They again see peak at the interpolation point (n p). Wu and Xu [40] also looks at a version of Principal Component Regression in which the data dimension is reduced. That is, the data is not embedded in high-dimensional space anymore. Wu and Xu 40) sees a peak at the boundary between the under and over- weer-paaameterized regions. Finally, Sonthalia and Nadakuditi (24) and Kausik, Srivastava, and Sonthalia (37) look at the denoising problem for low-dimensional data and have peaks at c = 1. Therefore, prior work does not immediately imply that low dimensional data results in under-parameterizee double descent. If we had only low-dimensional data, then the peak "should" move into the werrpaaametterzee regime. This is because the true dimensionality of the data is < d. Then, one might think that the peak occurs when the number of training data points equals r since that is the interpolation point" F
We are the over parameterized regime since d' > r = n.
We can understand this phenomenon as follows. The data from the second mixture does not affect the smallest eigenvalue of the covariance matrix. This is because the second mixture lives a one-dimensional space. Hence, it only affects the top eigenvalue. Since the Stieltjes transform at 0 is dominated by the behavior of the smallest non-zero eigenvalue, data from the second mixture has very little effect on the Stieltjes transform of the ESD at O. We expect the above intuition to hold, even when replacing rank 1 with rank for any fixed small r.
Connection to Prior Double Descent Theory For this example, it is easy to show that there is strong connection to prior double descent theory. Specifically, even though we cannot interpolate the data, the minimum training error will occur at πj. Further, we see that the blow-up in the excess risk is due to the norm of the estimator blowing up.
Additionally, we see that comparing with the result from (which is the case when T2 = 0), we see that the n. > 0 results in sifting the peak to πı and rescales the variance by T1. However, we also see an additional correction term in the overparameterized regime:
(1 (1-
(8T=)² T=lled
Here we see that the term depends on the alignment between the target ,3 and the spike direction 2.
6
Conclusion
This paper presents two simple models with double descent in the under- mnder-parameterizee regime. While such peaks seem limited to special cases, understanding the cause is important for a complete understanding of the double descent phenomenon. Our analysis reveals that the location of peaks depends critically two properties: the alignment between targets and the eigenvectors of the training data gram matrix and the behavior of the Stieltjes transform of the limiting empirical spectral distribution.
We demonstrate that violating either of these properties can shift the peak into the palleer-rramterizeeed regime. The first model shows that ridge regularization can create a misalignment between targets and singular vectors, leading to peak at c = 1/(1 + μ²)). The second model, using a mixture of isotropic Gaussian vectors and directional vectors, demonstrates that modifying the spectrum can result in a peak at c = Ti. These findings challenge several prevailing theories about double descent. They show that peaks need not occur at beyond the interpolation threshold and that peak in the estimator's 's norm does not necessarily imply a peak in the generalization error.
Investigating the interaction between spectral properties and generalization in deep neural networks to provide a general theory of double descent is an important avenue for future work. Understanding whether similar phenomena occur in other architectures and the implications for model selection and regularization remain open questions.
References
Scott Fortmann- Roe. Understanding the Bias- Variance Tradeoff, June 2012. URL: http: [1]
//scort. fortmann roe cwm/ wttpe./o///.cc//aaaaaaiiiooo huml (cited on page l).
'At least for 1-dimensional targets
10

---

[2] Manfred Opper and Wolfgang Kinzel. Statistical Mechanics of Generalization. Models of Neural Networks III: Association, Generalization, and Representation. 1996 (cited on page D
[3] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling Modern Machine- Learning Practice and the Classical Bias-Ves Variance Trade-off. Proceedings of the National Academy of Sciences, 2019 (cited on pa
[4] Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High dithesiinniii Dynamics of Generalization Error Neural Networks, Neural Networks, 2020 (cited on pages
[5]
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: ridge regres- sion and classification. The Annals of Statistics, 2018 (cited on pages 20
[6] Gabriel Mel and Surya Ganguli. A Theory of High Dimensional Regression with Arbitrary Correlations Between Input Features and Target Functions: Sample Complexity, Multiple Descent Curves and Hierarchy of Phase Transitions. In Proceedings of the 38th International Conference on Machine Learning, 2021 (cited on page
[7] Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai. Harmless Interpolation of Noisy Data in Regression. 2019 IEEE International Symposium on Information Theory (ISIT), 2019 (cited on 2.
[8] Peter Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign Overfitting in Linear Regression. Proceedings of the National Academy of Sciences, 2020 (cited on pages 2
[9]
Mikhail Belkin, Daniel Hsu, and Xu. Two Models of Double Descent for Weak Features.
SIAM Journal on Mathematics of Data Science, 2020 (cited on page 2
[10] Michal Derezinski, Feynman T Liang, and Michael W Mahoney. Exact Expressions for Double Descent and Implicit Regularization Via Surrogate Random Design. In Advances in Neural
Information Processing Systems, 2020 (cited on pages 3)
[11] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High- Dimensional Ridgeless Least Squares Interpolation. The Annals of Statistics, 2022 (cited on
pages 2 IOp.
[12] Bruno Loureiro, Gabriele Sicuro, Cedric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborova. Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions. In Advances in Neural Information Prucessing Systems, 2021 (cited on page 2
[13] Chen Cheng and Andrea Montanari. Dimension Free Ridge Regression. arXiv preprint 2022 (cited on page
arXiv:2210.0857
[14] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization Error of Random Feature and Kernel Methods: Hypercontractivity and Kernel Matrix Concentration. Applied and Computational Harmonic Analysis, 2022 (cited on page 2
[15] Song Mei and Andrea Montanari. The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve. Communications on Pure and Applied
Mathematics, 75, 2021 (cited on page 2
[16] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A Mean Field View of the Landscape of Two-layer Neural Networks. Proceedings the National Academy of Sciences the the United States of America, 2018 (cited on page
[17] Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Covariate Shift in High- High-Dimenssioal Random Feature Regression. ArXiv, 2021 (cited on page 2).
[18] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. Generalisation Error in Learning with Random Features and the Hidden Manifold Model. In Proceedings of the 37th International Conference on Machine Learning, 2020 (cited on [).
[19] Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and Rich Regimes Overparametrized Models. In Proceedings of Thirly Third Conference on Learning Theory, 2020 (cited on
page 2}
[20] Bruno Loureiro, C'edric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc M' ezard, and Lenka Zdeborov'a Learning Curves of Generic Features Maps for Realistic Datasets with a Teacher-Student Model. In NewrIPS, 2021 (cited on page 2
11

---

[21] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of Lazy Training of Two-layers Neural Network. In Advances in Neural Information Processing Systems, 2019 (cited on page().
[22] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When Do
Neural Networks Outperform Kernel Methods? In Advances in Neural Information Processing Systems, 2020 (cited on page(2).
[23] Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal Regularization can Mitigate Double Descent. In International Conference on Learning Representations, 2020 (cited on pages 2
[24] Rishi Sonthalia and Raj Rao Nadakuditi. Training data size induced double descent for denoising feedforward neural networks and the role of training noise. Transactions on Machine
Learning Research, 2023 (cited on pages 3 10 20
21
24
26
31).
[25] Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The Optimal Ridge Penalty for Real-
World High- Tigh--Dimensional Data Can Be Zero or Negative Due to the Implicit Ridge Regulariza-
tion. Journal of Machine Learning Research, 2022 (cited on page 3)
[26] Fatih Furkan Yilmaz and Reinhard Heckel. Regularization-We Wise Double Descent: Why Occurs and How to Eliminate it. In IEEE International Symposium on Information Theory,
2022 (cited on page 3
[27] Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple Descent: Design Your Own Generalization Curve. Advances in Neural Information Processing Systems, 2021 (cited on 33
[28] Lechao Xiao and Jeffrey Pennington. Precise learning curves and higher-order scaling limits for dot product kernel regression. arXiv preprint arXiv:2205. 14846, 2022 (cited on page 3) Ben Adlam and Jeffrey Pennington. The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization. In International Conference on Machine Learning. 2020 (cited page 3)
[29]
[30] Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple Descent and the Two Kinds of Overfitting Where and Why Do They Appear? In Advances in Neural Information Processing Systems, 2020 (cited on pages ().
[31] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. I. Linearized Two-layers Neural Networks in High Dimension. The Annals of Statistics, 2021 (cited on
3
[32] Alicia Curth, Alan Jeffares, and Mihaela van der Schaar. A u-turn on double descent: re- thinking parameter counting in statistical learming. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL: htttt:://
net formm m ?id=
00128X2T2b (cited on page 3)
[33] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. Information and Inference: A Journal of the IMA,
1 1(2):433-495, 2022 (cited on page B
[34] Ganesh Ramachandra Kini and Christos Thrampoulidis. Analytic study of double descent in binary classification: the impact of loss. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2527-2532. IEEE, 2020 (cited on page 3)
[35] Pragya Sur and Emmanuel J Candès. A modern maximum-likelibood theory for high- dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29): 14516-14555555 2019 (cited on page 3
[36] Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova.
The role of regularization in classification of high-dimensional noisy gaussian mixture. In International conference on machine learning, pages 6874-6883. PMLR, 2020 (cited on 33
[37]
Chinmaya Kausik, Kashvi Srivastava, and Rishi Sonthalia. Generalization Error without Independence: Denoising, Linear Regression, and Transfer Learning, 2023 (cited on pages 3
10
42
[38]
Oussama Dhifallah and Yue Lu. On the inherent regularization effects of noise injection during training. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Reseurch, pages 2665-2675. PM 18-24
24 Jul 2021. URL.: https: /aas://proceed wwtrocceeings....o ngs. bog..ne ml press/ v139/ dhidallllal Fal.aaallllllla la. html (cited on pages
12

---

[39] Ji Xu and Daniel J Hsu. On the number of variables to use in principal component regression. Advances in neural information processing systems, 2019 (cited on pages 9p.
[40] Denny Wu and Ji Xu. On the Optimal Weighted \ell_2 2 Regularization Overparameterizee
Linear Regression. Advances in Neural Information Processing Systems, 2020 (cited pages 3
10).
[41]
Ningyuan Huang, David W. Hogg, and Soledad Villar. Dimensionality reduction, regulariza- tion, and generalization in overparameterized regressions. SIAM Journal on Mathematics of Data Science, 2022 (cited on pages 3
[42]
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee. In International Conference on Learning Representations, 2020 (cited on page(4)
[43] Yutong Wang, Rishi Sonthalia, and Wei Hu. Near-interpolators: rapid norm growth and the trade-off between interpolation and generalization. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelli- gence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 4483 4491. PMLR, February 2024. URL: / pwwcee/iiocceesssssoooooes mir press v238
wang24k. html (cited on page 4).
[44] Vladimir Marcenko and Leonid Pastur. Distribution of Eigenvalues for Some Sets of Random
Matrices. Muthematics of The Ussr-sbornik, 1967 (cited on pages 4 28).
[45] Lucas Benigni and Sandrine Péché. Eigenvalue distribution of some nonlinear models of random matrices. Electronic Journal of Probability, 26:1-37, 2021 (cited 4.
[46] Olivier Ledoit and Sandrine Péché. Eigenvectors of some large sample covariance matrix ensembles. Probubility Theory and Related Fields, 151(1):233-66,, 2011 (cited page 4
[47] Carl D. Meyer Jr. Generalized Inversion of Modified Matrices. SIAM Journal Applied
Mathematics, 1973 (cited on pages 22 24).
[48] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin. Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: an imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'clé Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc., 2019. URL: /tttt::/ppaprssse http::///pppprr...u..pppppppppep paper/ 9015 Sato0s--pttthcaaaee an imperatiiiis style high wewfohheeoooooeoeeeoec deep
cc/
Bearing--lbbrry..ps.
[49] Chris M. Bishop. Training with Noise is Equivalent to Tikhonov Regularization. Neural Computation, 1995 (cited on I7g.
[50] Friedrich Götze and Alexander Tikhomirov. The Rate of Convergence for Spectra of GUE and
LUE Matrix Ensembles. Central European Journal of Mathematies, 2005 (cited on page 28
[51] Friedrich Götze and Alexander Tikhomirov. Rate of Convergence to the Semi-Circular Law. Probability Theory and Related Fields, 2003 (cited on page 28)
[52] Friedrich Götze and Alexander Tikhomirov. Rate of Convergence in Probability the Marchenko-Pastur Law. Bernoulli, 2004 (cited on p8).
[53] Z. Bai, Baiqi. Miao, and Jian Maan-Feng. Yao. Convergence Rates of Spectral Distributions of Large
Sample Covariance Matrices. SIAM Journal on Matrix Analysis and Applications, 2003 (cited on page
13

---

10
the location of the peak seems to occur n²4T- However, rumning the projecting to low-dimensional space (right figure) results in very different phenomena. We Generalizationn Errrr
Generaal lzation Etror
Emprical Theery
Generaliiattonn Error
0.0073
Erppiccl Theary
9.05
0.01
0.00
0.002
Undee Fareddar ond
0.00
0000
Uneer Parameerzed
1.0
C= diNgg
== d/Nen
d//0m
Figure 8: Generalization Error for low-dimension MNIST using linear denoiser. For the left figure, we use 10 dimensions and lr 0.1. For the central figure, we use 5 dimensions and 1. For the right figure, use 784 dimensions and μ 1.
A Higher Rank for Denoising Model
One might be led to believe that the restriction that the data lie on a line embedded in high dimensional space is crucial to the appearance of this phenomenon. However, this is not true. As long as the rank of the data is relatively low, for the input noise setting. we can see this phenomenon. Hence, we extend our results beyond the one-dimensional case to the low-dimensional case. Due to space constraints, the conjectured formula for the risk is in Appendix P as well the role of low dimensionality using MNIST data. Specifically, then add noise to the low-dimensional representation and then
We verify the conjectured formula
project the data
onto a r-dimensional subspace. solve the denoising problem. The left two figures in Figure show that the phenomenon exists for low-dimensional data. That is, we see that a peak occurs in the muder-parameterizee regime, and experiment without
longer see double descent at all. Hence we see that a peak occurs, then its location does not depend on the dimension. However, the occurrence of the peak does depend the dimension. Thus, that this complements the results in 38
'While these are currently presented as conjecture. This is because we only computed the expectation terms. Careful analysis of the variance would allow to formalize the statement.
14

---

10-8+1.271e-3
1,27
Generalization Error
1.26 -
Train Error
1.25
1.24 x
1,23 1030"
6
1.22 -
1.5
2.0
2.5
3.0
2.5
3.0
C d/Nem
C= d/Num
Figure 9: Generalization Risk and Training error for denoising low-dimensional version MNIST using 1-hidden layer neural network. Here d = 2 784.
B Non-Linear Model
To show that under-paramnn paader-prrameerizzedd peak occurs for non- non-linear models. We conducted an experiment on MNIST with a 1-hidden layer neural network with a width of 784. The network has no bias, so has 7842 parameters. Let V be a random 10-dimensional subspace. We project our data onto add noise to the low dimensional representation, and train our network remove this noise. We use full batch gradient descent with weight decay 0.001 to train the model for 500 epochs with learning rate of 2 x 10-2 We test it on the complete MNIST test data. Figure 9 shows the training error and generalization error as function of the number of training data points. As seen in the figure, we have multiple peaks in the minimums in the training error. Interestingly, the risk curve here exhibits peaks!
regime, and the peaks in the risk correspond to local
There are, however, many crucial differences between the peaks for this neural network case and the linear model case. First, the location of the peak does not seem to depend on the strength of the ridge regularization. Second, the peak seems to directly correspond to the local minimums of the training error. Hence, while we see peaks the under-parameterized regime, the mechanisms that create these peaks are likely to be different.
15

---

5.20
Paning tmee Bervative
Eeperiaa
Paring briet
3.50
0.58
Thaiiing Ener 3rd Dervarie
Traring Erir
Srip
ad Dellettve
2.04
Hitimum
633
9.02
0.4
9.00
diNen
d/Nin
Figure 10: Figure showing the training error, the third derivative of the training error, and the location of the peak of the generalization error for different values of μu ((L) μ = 1, (C) = 2] for the data scaling regime. (R) shows the location of the local minimum of the third derivative and 41
C Training Error
As seen in the prior section, the peak occurs in the interior of the mnder-parameterizeed regime and not on the border between the under- parameterized and over wee-parameterized regimes. We have also seen that it does not necessarily occur whenever there is peak in the norm of the estimator. The final postulate for where the peak occurs is that occurs when we first hit zero training error.
In this section, we explore the connection between the training emorr and the risk. Theorem 5 derives a formula for the training error in the under- mnder-parameterized regime.
Theorem (Training Error). Let T be as in Theorem
The training error for is given by
Edcrn |||
W oope (Xern + Atr))ll T (ofm (1-c.T;) + tra T2) + o(1),
12 2
1 12c
1 +-pcc v(1 c + /2))² + 4c2
where Ti
c1 4122 -1
+
2c
and
pc+c++1 1²0}² + 46 +²2
T2 --= -1 12)
Since we are studying the ridge regularized problem, it is impossible for the training error to be exactly equal to 0. Hence, we may expect the peak to correspond to other features of the training error curve. Given the analytical formula for the training error, we can compute the derivatives. We found that the training error curve does not seem signal the location of the peak in the generalization eтror curve.
Since studying the ridge regularized problem, it is impossible for the training error to be exactly equal to O. Hence, we may expect the peak to correspond to other features of the training curve. For example, the peak could correspond to local minimum of the training error, could correspond to a point where the training error or its derivatives suddenly change. The first, a local minimum, is easy see from the plot of the training error, but the second can be more subtle as we do not usually have access to the derivatives. However, since we have an analytical formula for the training error, we can compute the derivatives.
Figure plots the location of the peak and the training error. Here, the figure shows that the training error curve does not seem to signal the location of the peak in the generalization error curve. However, shows that for the data scaling regime, the peak roughly corresponds to a local minimum of the third derivative of the training error. While the minimum of the third derivative is difficult to interpret, as we can see from the third plot in Figure 10 the minimum seems to closely track the location the peak.
16

---

D Regularization Trade-off
It has been seen in prior work that the amount of noise added to the input data can be viewed as regularizer [24] 49) In our setup, we have two different regularizers: the amount of noise added to the data (since we are dealing with linear models, this equivalent the strength of the signal o and the strength of the ridge regularizer μs. It is interesting to analyze the trade-off between the two regularizers and the generalization error.
casora
1.0
CoaiNes
Figure 11: The first two figures show the drn versus risk curve for c 0.5, μ 1 and c 2, pz 0.1 with d 1000. The second two figures show the risk when training using the optimal Oern for the data scaling and parameter scaling regimes.
Optimal trn First, we fix and determine the optimal Oren- Figure T1 displays the generalization error versus obn curve. The figure shows that the error initially large but then decreases until the optimal generalization error. The generalization error when using the optimal Oven is also shown in Figure Here, unlike
23 picking the optimal value of Ttrn does not mitigate double descent.
Proposition 1 (Optimal otr)). The optimal value of of for 1 given by
Ore o 1)² 102-21(60 (cp" + + + 2(cu² 2c + 1)] Nest (p²2 à -1-11
(c (12 + 1)² T( c
2c
Additionally, it is interesting to determine how the optimal value of otn depends on both and c. Figure 12 shows that for small values of μa (0.1, 0.5), changes, there exists (inverted) double descent curve for the optimal value of Otrn- However, for the data scaling regime, the minimum of this double descent curve does nol match the location for the peak of the generalization error. Further, as the amount of ridge regularization increases, the optimal amount of noise regularization decreases proportionally; optimal or s3 du²2. Thus, for higher values of ridge regularization, is preferable to have higher-qualie data.
Optimal Value of μ We now explore the effect of fixing Ttrn and then changing μa. Figure 13 shows a U shaped curve for the generalization error versus suggesting that there is an optimal value of μ. which should be used minimize the generalization error. Next, we compute the optimal value of μ using grid search and plot it against Figure [4 shows double descent for the optimal value z for small values of Otnn. Thus, for low SNR data, we see double descent, but we do not for high SNR data.
Finally, for given value of μı and c, compute the optimal Otrn- We then compute the generalization error (when using the optimal otr)) and plot the generalization error versus l curve. Figure [5] displays a very different trend from Figure 13 Instead of having a U-shaped curve, we have
Optimal (Nve
632
opcimal ce PNm
3.-
Mrstum
optimal (Nees
1.77
2.60
1.50
2.0
1.25
330
Vier
1.00
2.5
130
0:2
0.30
0.70
1.00 122 150 175 2.00 C- diNbn
0.25
2000 6.50
375
2.0 :25 c=d/Non
150 1:75
Figure 12: The first figure plots the optimal of /n versus curve. The middle figure plots the optimal a nn versus e in the data scaling regime for μ = 0.5, and the last figure plots the optimal orn/n n versus in the parameter scaling regime for = 0.1.
17

---

Generalization Error
0.010
Generalization Error
0.008
0.008
0.006
0.006
0.004
0.004
0.002
Theoret ca Empricaal Min mum
Theeret.c ca
Empinical Min mum
0.002
10
(a) c
0.5
(h)
Figure 13: Figure showing the generalization error versus μ for irn and o Nist
Optimalj 12
Optimal Ja
Optimal A.
03
Oton 0.2
(b) Otrn 0.3
(c) dema R 1
Figure 14: Figure for the optimal value of verses for different values of dtrn
0.5
Generalization Rlsk
Generalization Risk
10450"
(a) 0.5
(b) cb)
Figure 15: Figure showing the generalization error versus for the optimal oi and ois Nest-
monotonically decreasing generalization error curve. This suggests that we can improve generalization by using higher-quality training while compensating for this by increasing the amount of ridge regularization.
Interaction Between the Regularizers The optimal values of / and dern are jointly computed using grid search for μ E (0, 100) and Otrn/ / /nn E (0, 10). Figure 16 shows the results. Specifically, Otrn is at the highest possible value (so best quality data), and then the model regularizes purely monotonically decreasing generalization error curve. Thus, in the data scaling model, there is an implicit bias that favors one regulurizer over the other. Specifically, the model's implicit bias to use higher quality dota while using ridge regularization to regularize the model appropriately. It is surprising that the two regularizers not balanced.
using the ridge regularizer. This results
18

---

Optimal Nom
Generalization
2000/11
Optimal
3
Figure 16: Trade-off between the regularizers. The left column is the optimal Otrn the central column the optimal jr, and the right column is the generalization error for these parameter restrictions.
lizaation Emro
Optimal 8un
Km
(a) 0.1 S / < and 0.1 S own
S 10
General izattiiin Error
Optinal 8m
Optimal M.
6.
1.0
(b) 0.1 S / S 100 and Oen S
Figure 17: Trade-off between the regularizers. The left column is the optimal Otrns the central column the optimal μr, and the right column is the generalization error these parameter restrictions
Next look at the trade-off between Oern and μ for the parameter scaling regime. We again see, Figure 17,, that the model implicitly prefers regularizing via ridge regularization and not via input data noise regularizer.
19

---

E
Proofs
E.1 Linear Regression
We begin by noting,
BT = -Popp + (ern)
Thus, we have,
|| 3)
Trr(ppp Xon (X(rn) (opt + Tr(Strn (X. ( " + (T opp Xern Xtra Str..
that the last term vanishes. Taking the expectation, with respect to Eerns Letting Xt Ux Σx V.. We that using the rotational invariance of X, Ux. Vx are independent and uniformly random. Thus, s Pope Ux is uniformly random unit vector.
Thus, we see,
min(d.n)
Tr(S X (Xtrm)² Xerrn
E[s min 1 (1:))
E Xeen Sten
Similarly, we see,
min(d,n)
E Ex fom Strm
Σ
Multiplying and dividing by d, normalizes the singular values squared of Xtrn so that the limiting distribution is the Marchenko Pastur distribution with shape c. Thus, we can estimate using Lemma from Sonthalia and Nadakuditi (24) to get,
+0 +(l)
c <<
c <>
Finally, the cross-term has an expectation equal to zero. Thus,
1 + I e<1
E Exern& Sopt [2] =
1 + e>l
Then we have,
BBBoptt = 3 Xtrn + Etrn Exm Xten
The second term has expectation equal to zero, and the first term is similar before and has expectation equal to min 1,
E.2 Proof for Output Noise Model
Theorem 4 (Under--arametriize Peak). For the above model, if n2, and d/n c, then the
expected risk is given by R
.
x c-RI
(1
188
(8 =)²
Proof. We begin with c < Ti. Here, since AAT is invertible, we can see that
AT (AAT + ||u]|222T)~
ST (BT [A zu +
02""
Let us focus the term without the &. Using the Sherman Morrison formula and the orthogonality of B and z, we see that
[AT) u2 (AAT + +11e1|2227)-- gr
(5T [A
zu 20?
20

---

Thus, we get that
AAT (AAT + 11011222")) -1
3 = 3" + ET
Uz
For this model, the uncentered covariance matrix is given by
Blax") ] = क lB (0 + m2lBla² =2 ==²|=
11 I + =22=
d
Then, the expected excess risk for solution / compared to /3 is
R = BillsT= -=
T d
|3 1 + T2ll(3 B) =1|11
The first term is given by
AT u2?
+ [|00|2222)) ) XX
E|ll 3 - 3 ||
E
ST
(AA"
Taking the expectation over ç, we get that the expected excess risk given by
AAT 1uz"
(AAT + 101122=")~² [A 2071)
Tr ((1AT + [|01(2222) -
Tr
Again, using the Sherman-Morrison formula, we get that
| 2
Tr(AAA") Tr((AA" + -((o)==")"")<<((((>>>>>>)>)))> 1 + ||||| - (="(AA")-~a)
Suppose is the limiting distribution the empirical spectral distribution for the non-zero eigenvalues. Then using the concentration results from 24 we see that the error can be expressed
|0l|
|0|
1
Tr((AA")-
(AAT)-I2 Tr (s (AA") d-Ex~u
2E
E
Anw
X2
The second term of the expected risk is
AT u2
E"
(AA" + [|ll|| =)]l==²)²
Again, if we take the expectation over & and write trace, we
1 (2 Tr(2T (1ANF)-1 (AAT)
=7(AAT)-2
2)= 1- 2T (1AAT((1)-11
Again, this expressed
E
1
1
|||||| 2Axe
Putting all together, the expected excess risk is
E
Ex-p
|0
BA
T2
E
|0|
E
d |||||
2B
X2
If we then send n, k, to infinity, while noting that ||a||| + co, then we get then limiting risk
For the d > - k case, AAT is longer invertible. Hence, we need to replace the inverse with pseudoinverse. Hence, we have that
[AT v2T
8 = (8 [A
20T + +T)
(AA" + ||001222T)
21

---

We now expand the pseudoinverse using Theorem 1 from [47]. To write is succinctly, let M AA", P = (1 MMM) 7 =" P2, and T 2" M 2 to get that
? = 1
P2e (AAT))) (<xx))))) + (1 + ||ull?)r
(AA" +
Pzz"P
||01
Note that P is the projection onto the orthogonal complement of the range of A. Hence we see that MP = Mt = 0. Thus, multiplying through, and setting terms to zero, we see that
(M + 1012222 (M + | 2z = MM - MM zz P + ||011222 M
1111222" M 2 111111222 P22"
(1 + [| 22 P22 P
?2
Using the fact that 2= = 2 M 2 r and cancelling, we get
(M + ||0||2 (1(2222)))))))) (M + = MM - -MMMiZZTP
1 =1ul1p=== T TT + (1+ [|01 =z
7
=MMi 1 -MMM 21-
-101//2T2 P (1+ [|0|(T]] 22 TPP
7
7
-MM² MM2 ITTTTTTTT P ----22
-22
= -MMi (T (T-MM)) 1
2 P
7
= MM + P22TP
Thus, the first two terms in the error are
Ti | B112 + T2 T2113T= 2- -T =112
d
Let us look at the second term first. Here we see that
8²2= 8" (MM +
1 P22" 9
2= )
( Pz)
Thus, we see that
BT - =
=T======== - - P2)
= 3d (I MMM)² (I MM1)
= 0
For the first term, we first note that
3- 3T 3r - -B" MM + P
1 -8T PTzzTT P
= =BT P
To compute the norm, we expand and get
||BT pl 2 + 7
Tr (8
PPzTT
2 Tr
7
22

---

Noting that P is projection matrix, so PP = P and using PZ = ?, we get that this term simplifies to
1 2 Tr (8
Note that the subspace for P comes from Gaussian random matrix. Hence is uniformly random. Hence
71 [10" (1
|| = -11-1)
- ||
d
Similarly,
1 Tr (8t P2z PS)
-11-²) (8"²)
Ti
E
||=1|2
For the next two terms, we need to first simplify
Aa
(AA* + +111||2227]
u2
Substituting in our formulas and noticing that
A P and A Mt At
we get that
AAT uz (AA" + -110112227]
At 1 A 0+0+
U2 UZTM M
+ p uzz M + 1+1|ai r1) 2
10 U2
At -
TUZ To.TPtp 1 TT22
15 02 TPPPP P
At T
| 0z P
Then we have that
A T
11
137
AT 122
(AAT + +11012227)1 2
(AAT + 110112227)1
(1
- At At
At At 12 TTp p
11ul 1 u2T TP
1|ll T P
Tr
(M
m zz T
1
P +
1 ||u0|2T P=z P22TP)
|101
7
Ir (M+) Ir (MM Ir P= + 11
1
1 (1+10111 11111 Pax xT
Using the cycling invariance of the trace and the fact that M p =0, O, we get that
AT uzu (AAT
11011222 Tyy
| Tr (Mt)
1 + 2//
E
|10112
The last equality is obtained using cyclic invariance, the fact that p2 = P. and Lemma 6 for p I and g d, we get that asymptotically,
Pz. Using
x7
Tr(M*) c n²
Note that we similarly get that asymptotically.
1
T
+ 0.
d
d
23

---

Thus, the contribution to the risk from this term C- Finally, for the last term, we have that
AA 027
A A 21
Pz
(AA" +
|| vz
T
Thus,
E
Aa u
(AA" + +11111222))
1
|0||
Note that ||a|| xe & and hence this term is aympotitcally zero. Putting it all together, get the needed result.
E.3
Proofs for Theorem
The proof structure closely follows that of 24
E.3.1 Step 1: Decompose the error into bias and variance terms.
First, we decompose the error. Since we are in the supervised learning setup, we do have standard definitions of bias/variance. However, we will call the following terms the bias/variance of the model. First, recall the following from [24].
Lemma 1 (Sonthalia and Nadakuditi (24)). If Atst has mean O entries and Aest is independent of Xtst and W, then
E X1st
WY [12]] = E.. X1st W X 1
E W Aest 1i
(3)
Bias
Variance
E.3.2 Step 2: Formula for Wopt
Here, compute the explicit formula for W Wapt in Problem I Let Å [Aern pll, X
[Xtrn 0] and Perm Xeen + Atrn- Then solving arg minw | WYenn 13 + 1+pp20 + 11 is equivalent to solving arg minw [|&trn - W l2 Thus, Wope = arg migmin 1| W Xim ei frn- Expanding this out, we get the following formula for W. Let â be the left singular vector and 6rm be the right singular vectors of Xar.- Note that the left singular does not change after ridge regularization, so å u. Let h 6t Atrm k = Atr,, $ (1 Atr u.
i= 6trn (I A Atrr), & = 1 + otrn Atr, u, orr 10 R2.
Proposition 2. If + 0 and Atrn has full rank then
Ttrn wh +
oimllit2 uk?" Atrm-
W
Proof. Here we know that u is arbitrary. We have that Age has full rank. Thus, the rank of Agn is d, and the range of A is the whole space. Thus, u lives in the range of Aern- In this case, we want Theorem from 47 We define
|1661 FT Ttrnk and q" Tern 1|tl bT At.. h.
Then have,
(Aern + Ttrn utru Al.n. +
Tern Fongfry FT'..' Atn
Note that, by our assumptions, we have Ötrn(I At Arrn), and (T Atmm A a projection matrix, thus
24

---

6 ET 6 (1 A AlrnAArn) /
orr (1 Alra Arro) (T(( Alrn Arm)) "
To compute W Wopt Xtrn (Xtrn + Atra)t oen onnu (Aern + Otnn t using ? - 1 =
Otrn Dy A u Oeenluu, multiply this through.
Ttrn atenlitrr (Aern otrnuttrn) ) Otrn ue (A
jT' Alrn 7 Ina
9
-rmn @imlléi12 uh" w
Orrn? 2 ue
otrn
|kl1 &r + oomnh G"
orn uhrnhh- + Pirn ormll0]2
uk² Alrn + 0bral111111 un
9 Otrn 7(9 - 1) ua¹
7
Then we have,
o 1111111011
Otra ttral/@l?? 1.T Alro
uq"
u
of
||
Aon 11:11211811 wh
ukT At
and
Otrn Otrni(f - 1) uG Otrn 1(9 - 1) 1
( Tern 0tral1i11
RTT Atrn - h
7
amm [16112(7 - 1) uk= Alrn. 9 1 uh.
4
Substituting back in and collecting like terms, we get,
oi
1111111012
7(9- ((1-1) 1) wh+
Otrn ueruur T + Ozrn (0 Tern
1
7
[1011
11:1
11012(6 - 1)
ukT Atrn.
PG
7
We can then simplify the constants as follows.
0 kr
18
1) 7(9
$ o 111111111@1 - 72 + 2
and
118112 ( o 121811 72 + ?)
|
15 1)
||21
trn
7
7
This gives us the result.
25

---

E.3.3 Step 3: Decompose the terms into a sum of various trace terms.
For the bias and variance terms, we have the following two Lemmas.
Lemma 2. If Wopt is the solution to Equation 7 then
Xest
Wopt Xest = X1st-
Proof. To see this, note that we have M > M.
Otrn?
uhuwvee 2rmlli112 uh A us
Nest
W Xest
Xest
Xest
Otrn? uit Abrn un
uk" Alrn u.
Note that 9 1 oen TT Abm. Thus, we have that Tern oT Al. u = o 3-1. Substituting this into the second term, we get,
W Xost = Xist 3(8 ((9-1)
Irn |1 uhT At uv uui
Xtst
For the third term, since ks = Atro U, RTT Atm 11 = =kTk= || Substituting this into the expression, we get that
7/8 1)
o |111
Xist - Wopt Xest = Xest
7 uuist
40
Since Xest uv/ar we get,
969 1-
Pen 11 |1211 11:1112 9(--1)
-
Xest
W Xest = Xest
7
Simplify the constants using i = 11/22111111111 42, we get,
$ + 72
of.
8|| 1111
Lemma (Sonthalia and Nadakuditi (24). If the entries of Aist are independent with mean 0, and variance 1/d, then we have that E W opt Assel1]= Nust [|
Lemma 4. f + and Asro has full rank, then we have that
22 32 Tr(hTh)
+2 oi oimnl 11:112 1 Tr(h? RT Alow) +
[ opt 11
(T((Atmn)) TRkT Alra)
2
G2
Proof. We have
W opell = Tr(WT opt
W Wopt)
TTr (
Jorn wh 2rm 1111
whe Alom)
T uh +
[ 7
wh: Alm..) ))
7
7
0 2
0 1112
Tr IT uu)) +
Tr(hi uonTuaull Tukk A
72
ot 11:1
Tr((Atmm)
I "Tuu" wut Atmm)
+
f2
0 22
of 18.
111l Ir((At)))T Atr.).
Tr +
Tr Atraa
72
72
72
Where the last incquality is true due to the fact that || 1.
26

---

E.3.4 Step 4: Estimate With Random Matrix Theory
Lemma 5. Let A be a x q matrix and let Å = [A μI] Rexqtp, Suppose A UEVT be the singular value decomposition of A. If A ÜSVT is the singular value decomposition of A, then Ú = and if <
(A)2 +
V 0z (A)2 + 2
Σ
E RPxp,
0
0
(o) n2
and
VIPDISI1 MUI
V =
E R.tpxp
Here Vi.p are the first p columns V.
Proof. Since p < q, we have that U RPXp, E E RPXP invertible. Here also consider the form of the SVD in which VT E RPx9.
We start by nothing that ŪÉST = AAT = AAT +p - U(E++( Thus, we immediately that a; (A) + 222 and that Ú UU
Finally, we see,
PT -ー= Å EVVVV -
Lemma 6. Let A be a x q matrix and let À == [A μI] E Rexetr, Suppose A = UEV" be the singular value decomposition of A. If Á = UÊVT is the singular value decomposition of A, then Ú = U and if
oi (A)² + +12
0
0
O2 (A) + n
0
0
(A)2
+
11
TRPx
1
0
0
0
0
Here we will denote the upper left q block by C. Further,
V
VET
11 C-1
0
E Rotpxp
Uptisp]
Proof. Since p q. we have that E RexP and we have that E RPx9 invertible.
Here VT E Raxa is
We start with nothing,
(Fiigg
0 + 12I1 UT.
ÚÊ AÄT = AAT + 121=1U
0g-p
Thus, we immediately see that for i = 1,... = + 4² and for = p 1,..., we have that (A)) = 22 and that Ú = U.
Then, see,
VT = デ 1TT À = IE-VV -Ê-LUT.
Note that Σ has 0 for the last p y entries. Thus,
[ [C
S-1EV
0q-p.
27

---

Similarly, due to the structure of Σ, we see.
1 = 1
U Ugtipl
Lemma 7. Suppose A is an p by q matrix such that p < 9, the entries of A are independent and have
mean O, variance 1/p, and bounded fourth moment. Let p/q. Let À = [A [T] E IRxxatV, Let W, ÅÂ and let Wa = ÅT Å. Suppose Xp is a random non-zero eigenvalue from the largest eigenvalues of Wn and by random non-zero eigenvalue of Wq. Then
(1448e 4244 -1------- o(1).
1.
E
Ap
2u²e
pe 20+1 + 1 (1 - 2) + o(1).
2.
E
E
2p 2p=ee/4p2""
(1
Proof. First, we note that the non-zero eigenvalues of Wp and Wa are the same. Hence we focus on Wp. W is nearly a Wishart matrix but is not normalized by the correct value. However, cW, does have the correct normalization.
Due to the assumptions on A, we have that the eigenvalues of CAA converge to the Marchenko- Pastur. Hence since the eigenvalues of cWp are
(cAp): ca, (A)2 cp²
estimate them by estimating ca, (AA2 with the Marchenko-Pastue 44 50 53 In particular,
we want the expectation of the inverse. We need to use the Stieljes transform. We know that m.(2)
the Stieljes transform for the Marchenko-Pastur with shape parameter c, then X is sampled from the Marchenko-Pasee distribution, then
1
(²(2) E
A
Thus, we have that the expected inverse of the eigenvalue can be approximated m(-c42). We know that the Steiljes transform:
1 -
V (1 -2 c)²
4c2
m=(2) =
-22c
Thus, we have,
v(1 p²c 1 c)2 + 4p22 - p2c+c
E
m(-cp²)-
cdp
21
Canceling 1/c from both sides, we get,
V(I+ w1 c)2 + 41222 - pcc+c
E
2
Then for the estimate of E [1] we need to compute the derivative of the m2(2) and evaluate -cp? Hence, we see,
m'(2)) = (c- (c-2+ 2 v- 4cz + - c c-2)² 2)2 ()(c + 2 + / 4cz + (1 c- 2)2 -1) 1)
Aoz2 / 4ez + (1-c-2 2)²
Thus,
ml((-cp2)
222
1&c+ pe+
24 + ct 12cf2 1)(c p2c + (1- 12cp 1)
4u-c² / + c 222022
28

---

Canceling the 1/c² from both sides, we get,
p2c Vap2e + (1 -1- - 1)(c 100-)))e--eeee p²c v4p2 (1 c+ p²o)²
4ntcr 411202 + (1-ct 1Rc0}
Multiplying out and simplifying
+ p.c -c 41222 + c 12o 24x
1
1 -
E
x
Lemma 8. Suppose A is an by matrix such that > the entries of A are independent and have
mean O, variance l/p, and bounded fourth moment. Let c = p/q. Let A [A [l] E R Let W, AA and let Wg A Å. Suppose Ap is random non-zero eigenvalue of W p. and b, is random eigenvalue from the largest eigenvalues of W.. Then
v (-pet((-ttta2e0-0 pot1 + o(1)
1.
E
E
Aq
2p"
1-20 +p + (1 c) Znz + o(1).
2.
E
E
2n² (-
Proof.
First, we note that the non-zero eigenvalues of Wp and Wa are the same. Hence we focus on Wp. Due to the assumptions on A, we have that the eigenvalues of AT A converge to the Marchenko- Pastur with shape c-1, Hence if Xo is one of the first q eigenvalues of W,, see,
1 Ap
v² 1/c)² - -
1² 1/c
E
m (1²)
24²² /c
Then for the estimate of IE [1/ we need to compute the derivative of the m. (2) and evaluate at 2 Hence, we see,
(L/c+ n²² ( -2) n1² +
22)2 -1)
/p/p://///+111/////10/1 11212
(1 + p2 (14petc///p//+++
-)1 ov AAp / (1-1/+
4ytcy quAc/442/0/ ( 112/2
(1+pec+ Appc (-1+c+ -1- p2c /4p2c+ (-1+c++++++ 1202
4p (-1 p²c²
This can be further simplified
1 1 2 e² + v²
1
+ o((
24 / + (-1+c+++++++++ pc
2411
We will also need to estimate some other terms.
Lemma 9. Suppose
an p by q matrix such that the entries of A are independent and have mean
variance 1/p, and bounded fourth moment. Let À = [A μl] E RPxxtp, Let W,, = ÅÄT and let W = A Å. Suppose Aps Ag are random non-zero eigenvalues of Wp, W from the largest min(p, q) eigenvalues of W,, Wap Then
1t 2c) o11)
1. 1f q. E
Ap
=
2c
1+ c- v (1 1l-ctupr +46 4²
2. pfp < 4,
+ o().
Ag
2c
29

---

3. 1fp q. E
Ap-n"
x2
=c
2/1-Icctpe
1-ct'c
1 +0(1).
4. 1fp < E
l+ttye
- +(1).
2 2
Proof. Notice that if À is an eigenvalue of A (so unshifted).
112 and
112
+ n =
À + n2
A ++2 (A+
Then use Lemmas and 8 to finish the proof.
Bounding the Variance.
Lemma 10. Let Th. be a uniform measure on n. numbers a1,...; On such that 17" + 7) weakly in probability. Then for any bounded continuous function f
f(a:) - Eanylf(x))
11
Proof. Using weak convergence
(ass) + Bxxa(((x))
==1
Then using the boundedness of we get,
f(a:) 1 Σ f(ai)= --a)==(((a)) 0.
Lemma 11. Let TJn be a uniform measure on numbers 01,... Op such that the + 7 weakly in probability. Let be uniformly random unit vector in TR independent of Tn- Suppose n/ m - (0, 11. Then for any bounded function f.
12
E,
Σ
Maii) +(eemnl(x))
:i=1
and
)1
27
Eg
Σ
2
- E,
Σ
8 ((s)
+0 0.
i=1
Proof. The first limit comes directly from weak convergence. For the second, notice,
Σ f(a)))))
ffa 2+ {tst(())((a))))))))))))))))))))) Σ sff(a))
Σ
2
Σ 83f(a))
1=1
Taking the expectation with respect to s we get,
Σ 2 fla())))
1
Σ f(ai)2
1
Σ f(as) Σ f(az)
m² + ((m)
m² + ((m)
Then using Lemma 10 for any fixed i, we have,
E(a)) + [f
30

---

Thus, as n2 - 0o, we have,
27 ot f(a))
Σ
1=1
Then since
2 + [(
E
fai))
Thus, the variance goes to zero.
The interpretation of the above Lemma is that the variance of the sum decays to zero m + Lemma 12. Suppose A is an by q matrix such that the entries of A are independent and have mean O. variance 1/p. and bounded fourth moment. Let = [A pl] E RPxxtp, Let x E R and E Iett be unit norm vectors such that 8² lv 0p]. Then
1. p < q. then ((TT(="(AAAT)
(1-c+u2e) 14222-1-peet + +o().
2u²e
2. p 4. then B[Th(=" (AA""
1 Pote
+ o(())
2yre
3. pf q. then B[Tr(0" (A" A) 6] [V(l=ct==o)++ee"" 1 + +o(1).
1tctu²e
4. 1f 4. then B[Tr(j" (""T"""(AAAAA AA
2/1-1totp00) - $) + o(1)
1+0t130
The variance of each above is o1).
Proof. Let us start with < q.
Let Å = USVT, where E is p x p. Then we see,
( 2
Where Ü is uniformly random. Thus similar to
24 we can use Lemma 7 to get,
E[Tr(>" (AA"))))A)))=)== V1I
c)²
4p - -pc + o(1)
2p2c
On the other hand, for p q. we have that only the first 9 eigenvalues have the expectation in Lemma S The other p- are equal to f.2. Thus, we see,
44pc+ (-1+c+ 2²cf² - c u²c+1 + o(1) ) + (1--2) μ
[[Tr(> (AAT)(()AA) _ c
2p
V4yicc (-1 1-1cc 22e2 -cw2c-1
2cp²
Again let first consider the case when p < q. Then have,
A = EI-I
8
-S--177.
Since ý has zeros in the last p coordinates, we see,
8" A'' of E
Thus, we can use Lemma to estimate this as,
1 + 12c
c
+ +
2 2 (1 c cu2)² 402 2
31

---

The extra factor of e comes from the sum of coordinates of a uniformly unit vector in dimensional space. And for p > q, we have that the estimate
( e 2 2 (1+ 1/0)3 + 4p2/c 2/ + o(1).
1 1 c + c²c
For the variance term, use Lemma [1 For three of the cases, the limiting distribution is the Marchenko- Pastur distribution. For the other case, the limiting measure is mixture of the Marchenko-Paste and a dirac delta at 1/1x²
The rest of the lemmas in this section are used to compute the mean and variance of the various terms that appear in the formula of W opt.
Lemma 13. We have that
2 (1-ctuRoo 3 + +o(1) e<l
Itctute
[1811]]
B
2) 2/ + +01 - e>1 1
1+ctHee
and that V(]1A]13) o(1).
Proof. Here we see that
| -Tr( (Af tnn Aern) 1 (t
Thus, using the Lemma 12 get that if c <
c 1.²c
E|| |]] = 21 c 2²c22 + 1426
2) +
and c >
1 1 w²c
B[[AD1]] = =
2 (- 22c)2 4ppc 2) + +0(1).
Lemma 14. We have
o(1) c<l
Aern [1A11p]
24
2r) 1-
+ o(1) <>l
21
and that v([1k]12) = o(1).
Proof. Since k = Alrmn u, we have that
| = Tr(u" (Aemm A A.rr
According to the Lemma 12 if c <
E| V(1 c+ 22c)222 + + - -1 -1
+
2
and if >>
|| V(-1+c+ - p2c+c
+ (1).
2p
Lemma 15. We have that
c- 12c+ Wo + +o(1) e<l
A [|101]]
- c c / -1-1+c+po03 4 + o(1) c>1
and we have that V(11f13) = o(1)
32

---

Proof.
Here we see that f = Eern Aemu). Thus, we see that
|1112 = Veeen 112 Vprn At Atr Armndrrn
obbn A Bern-
If V E Retoxpto we have that
A Atm = [38
0 DT. 0g
Then p q using Lemma 6 and the fact that the last p coordinates of Byyn are O, we that
Urn 4im Arm Bern = oirn ViP E. - V Vtrn.
Then using Lemma 9 to estimate the middle diagonal matrix, we get that
1 1²c v(1+ 11++pcc c)2 +)2 4c2p²
B[][[| = c 2 +
2c
1 (1 1-c- r2 v(1 (1 + o(1)
Similarly for 1, have that
1110|1 (1
c+ c+ (efe-c((11 (1 1/c} 4p2/c +0
2
1 (1 11-c- p2c (-1+ 41i²c) + d(1).
2
The variance of Aem is also o(1) using Lemma 11
Lemma 16. We have that Errn [6] 1 and O())=/
Proof. Noting that A = U.VT, we have that
min(n.d)
9 = 1 + Jern ST Afr u= = 1+ Otnn
Σ
(i aab.
1=1
Here a² = - V and = UTu u. U is a uniformly random rotation matrix that is independent of Σ and V. Thus, taking the expectation with respect to Atro, we get that the expectation is equal to zero. For the variance, let first consider the case when 1. For this case, have that
V HUE-1
V
Thus, letting a =orn Vı.d. get that
(A)
1
(A) + 112 a.b.
Squaring and taking the expectation, we see that
Bh +
Irrn E
Exwae
(A + 22222 2222
+ 0
2
frm
Similarly for >> 1, we have that
o E Ex-ue
El +
+
(1 + 22y83
d
33

---

Lemma 17. We have that
1² 1²22+c²² c-221- + 1 (1 - 2) + + c<1
E (r(((Atn) Rkk Abrn)
[lp
2 22 c2+(1-ct+20
+ (1 - -) 2 +0(1) e>1
24000/4800= (-1+ctp2))
and that V(p) (1).
Proof. Here we have that
p Tr(k" (Apm (k)) 'r(u" (Atrn ( (AtrnAgrn
We first notice that Thus using Lemmas
(Aem ) AernAtinn UTSS..
7 and
g
we see that < 1
11222 + 0² 1icc 2c
1 (1-2)
Elp]
2 Ap2c2 + (1 + 2²c
241²
and c
- 2e + e + + 1F=
(1-
[ppl
c)
+
6
2p / 4/2 (-1 + c+ 122)22
2/r²
- 2c e² 120 1222
1
1
2p 4 (-1 c)
2414*
The variance being o(1) comes from Lemma Lemma 18. We have that
again.
E E
Tr(h" Abrr))
and the variance is o(1).
Proof. Letting À A= U.VT, we get that
Tr(h""A = uTUS - opn
Then again since U is uniformly random and independent of E and V. the expectation is equal to zero. The variance is computed similarly to Lemma 16
E.3.5
Step 5: Putting it together
Lemma 19.
We have that
2e c /(1 - 22 + 4 +0(1) e<l
E
Orn
+
2
1 + -e - V - 22 4w2c + o() <>1 1
Gira
and that ((T/o
=
Proof. Using the fact that all of the quantities concentrate, we can use the previous estimates. Specifically, we use that
E| E[ S V
Thus, since our variances decay, we can use the product of the expectations. Further,
|XXY|| = [[X]][y] + E x [[y]"v[X]
+ Cov(X2, 2EIX]E1Y)Co((X,))
y2) -ovv(X
< [VX]V] E X + E|Y] VX + [V[]]][ + (BWVV|I++++VVV]]0v vVXx2v((y
Thus, since the variances individually go to O, we see that the variance of the product also goes to 0. Then using Lemma 15 and 14 have that if <
(1 (I+pect-- V(1 c pPc)2 4/²c2 + o(1)
E
34

---

and [(]E]//||111 = o()). Then since
V + Y|I S [ + V|У] + + V(VVY
we have that using Lemma
that if <
1 ( + 2
+ c -1 + 4p²c2 + o
orn
and that that variance is (1). lfc1
1
--tpeetc-v(-1ttee p2)) + +4220) + o(1)
E
trr
Oen
2
Lemma 20. We have that
a(l-ouma)
aeooo1
+ +0(1) e<1
-10l
1 111l11 + [1811pp
E Eeern
Oirn
dll al1-0
+ o(1) e>i 1
V--1tctp208+44p8
and that the variance is o(1).
Proof. Similar to Lemma 19 we can multiply the expectations since the variances are small. For < 1, simplifying, we get that
Aeen
1111+ 11/11p|
c(1 + opm)
Va- PPcc + 412c2 -1) + o(1)
pe
trn
2
and if get that
| 1111-p c(1 trr)
p²e pe+c++
V(-1+c+ 22c2 + 4u²c -1) + +o(1)
EAion
oimm
2
and the variance decays since the variances decay individually. Lemma 21. We have that
a(l+o 2
(1 (1-ctpec)+tppe -1) + t(l c<l
a eete+1
oi 72
E
||| opt 11
c(l+omm)) 2)
V(-Itct="e)+tppp -1) + +(( e>1
petot1
and that V(II opt (12:) o(1)
Proof. Follows immediately from Lemmas
17 18 and 20
Theorem 1 (Generalization Error Formula). Suppose the training data Xten and test data Xtst satisfy Assumption 3 and the noise Atra Atst satisfy Assumption 4 Let be the regularization parameter. Then for under-pane parametreeee regime (i.e., < for the solution W opt to Problem
the generalization error or risk given by Equation 2 given by
co?n (o + +))
1 u2c
2 tra
(0 + +1)
+T +o (2).
isst
R(c, (t)
2dT2
(1-c+ c+ p2c2 + 2
2d
where
1
2 2T ull
7
2 2 0 2+02 (1 + + p²e -11- (2))++++++++ 2
42 //t we can the concentration from Lemmas
Proof. Rewriting 2 as 73/of-0
16 and
19
Then using
Lemma 21 we get the needed result.
35

---

Theorem 6. For the over-parameterized case, we have that the generalization error is given by
i + +1)
co
V + 4 1) + 2
1 12e
R[c, =-2
lst
+
Nost
2d
2
where: T
2 Prm (1 + c+ p²cc
p(c) + 41²²c)
2/ we can the concentration from Lemmas 16 and 19 Proof. Rewriting f as 72/02mn
Then using
Lemma 21
we get the needed result.
E.4 Proof of Theorem
Theorem 2 Sander-Parameterrized Peak). Let μ.. E R30. = d/c oist Tesa and d is sufficiently large, so that the error term o(1/d) is small, then the risk from Theorem as function of c, has local maximun in the under--parmmeterized regime at 14p2
Proof. First, we compute the derivative of the risk. We do so using SymPy and get the following expression.
Acyp² (122 - 1) - (12 +1) v /402p22 + (cx2 c+ c)
4e
d
(cc2 + (cH2 - -c+ -u-2 - 40202 + (cp² c c+1)² 1)2 +1
(122 + 1) (4c2 + (eu² 1cp2-ctto -c+1)²) -44CH² + (1² - 1) (ou² - c+ 1)) (cp² + +c+1)
d (4c221 + (ep2 - -c+1) (cL2 (op2+e- +c- / 402 2 + (142 c c+1) 1)2 +
6)
(1022 + (cp2 - -c+ c+1))) cu2 +c- 4-c-v422 1422p2 + (cp2 c 1)2 1)2 +1
2
M (Ac2/2 (cp2- -c+ (()))((())))))) (cp2+c- - 422 2 (cp2 1)²
1
We can then compute the limit as c + 0+. Again using SymPy we see that
lim 2 R(c, p:: p2:
of.. d/c) >
c+ dc
Let
T(c, = 20² 1² ²² 2cp2 2c
To find the critical point, we shall write the derivative as one fraction of the form
-2(00 R.R(c. = - (cp² + 1),(c,d,d Q(c.u,d,T)
Here we see that
((),,,TT)=(tt =
202 p2 + 2 20p²² + (ep+c+1)V
and
Qcc,u.d,T) d(cp1² c VT)273/2
We see that the numerator is zero at (1 + 2 -1 To evaluate the denominator at this point, we first get that
44²
T((1 + +1) (122)
2 +1 < 4
36

---

Thus, we see that the denominator is
d d
2p
4u²
3/2
+
11 +
Since T((1 + (1(1++1))11 1,) < 4, we have that
2p
2
0
1 +
Hence the denominator is non-zero. Thus, we see that (1 + 1 is critical point.
Next want show that this point is local maximum. To do so, compute the second derivative and evaluate at c = (1 + n y Using SymPy, we get that the value of the second derivative at this point is
(x² 1)4 (4p² +3 44² p2
A² +1)
8d μr² (n² UV -====++++11>
To that it is maximum, we need to show that the above is negative. We begin by showing that the denominator positive. Since Sdux > O, we only need to look at the second term. Using arithmetic mean and geometric mean inequality,
see that
122 + 1 +1
MV +1 v p2( +1)
=
1² +1
2
Hence the denominator is positive. To show that the numerator is negative, have the following
44² + 3/ - 41² 112 + - vp² + +1<0 + 44² + < (4p² + 12 +1
16p + 9 24 (16μ²* + 8p²3 (1
112
1
16p² +8 <
(16 + 8p² + 1)
112
4
Where allowed square both sides because both quantities are non-negative. Thus, see get the needed result.
E.5 Proof of Theorem
Theorem 3 ([ lF Peak). If Otst -Titstt Otrn /nn and μ is such that p(Js) < O. then for fixed n that is sufficiently large enough, we have that E []] W [pellr] versus c = d/n curve has a local maximun in the under-parann datamerarreeeer regime
(μ² + 1)
Proof. Here we note that the expression for the norm of W same proof structure as Theorem 2 Differentiating with respect c, we see that the numerator the form
Wapt opt is given by Lemma 21 We follow the
(cp² + - 1c1)) u,,
When the denominator
(cp² +u+1+1
Where is as is in the proof of Theorem 2 Again at when e = 1/(2²+11 We see that the denominator is positive because /T 2. Hence again, we have critical point c = (1 + -²
E.6
Proof of Theorem 5
Theorem 5 (Training Error). Let T be as in Theorem The training error for is given by
E [||
W Wope(Xem + Arr))l = - (o (1 c.)i + oi T2) + o(1),
37

---

where Ti 2
1 + c²c
1
1 p.c
(1-ct w p2
1)
+ +²²
c 22202=220 + 1122
2c
and
xcc++11
T2 1-=0fete-1----ct--ee 4
+ 2 2 c c u2²cc + 4c2
Proof. Note that we have:
Xtrn
W Wont 1
EA
E Aern [||Xern Wope (Xpe(Xern Atrr))
Elll W Wope-eenl [2]] + _ - Wope oopeAern [13]
+
2 + E [Tr((Xern - Wope Xern) (eenn""ooooalaeee Aent)
n
First, by Lemma 2 we have Xtrn W opt Xenn. Then, E[] W Wope Wernll $
12] o Then, let us look at the EE Ae.. Ill Atrn [1:]] term.
E Arr [I| opt Aem 11:11 = (l W. opt
Wopt Atrn)
52
E[Tr(A h2 u² uhhtmm))
F2
1012
E[ Af fo ot ukf M Armi)
72
3 trn
31141
E[ AT (Atra) Rou" Atra)
42
|0
E[Tr (Atrr)) low" ui? A(mn)er))
f2
Prn E(Tr(hA A7 hT)]
42
1211
9
E
TT("" Atrn Aer ATm {rt)
72
o
Tr (T Afr (Atrmn (Ti)
F2
E[TT(R2 RT Atro Atrn Afrn (Abrr))) TT]]]
72
Irn 62
ETTr( Atr A (Atrml (o
72
0 trn
7
1012
E[Tr(u" (At..)"
A Aern ( of
72
1012
7
At A AT (Atrm)) )T Alr.. u)] B[Tr(u (TTTT(T(AAtT) (Atrn)" At Atrn Afr (Atrm) Atmm
E[Tr( ST
72
#2
12
ETT Atrn A ATr (At Torn)
72
E[Tr(u (Aton)" A Aern Alo AT Atrm u)].
42
38

---

Then, we look at the Tr((Xemn - W Wope Xtrn) ( W Aer)) term. By Lemma 2 we have Xern Wo Xorn Xten- Then,
Tr((X trn W Atrn)
2 - Tr (2
[Tera wh+ Lirllt]2 uh Abroo Aern
Otrn? 72
Tr (Xtmuuheem)
72
pim alll1e
Tr (xfrnke uk Al AlrnA Aer
72
ttrn
9
Tr (ttnnter
of Abon Acrn)
42
311011
Tr (Otrn (Armm) AornAer
42
trn
42
(or (orm Aten AtrnWtou)
Tr
42
0
111011
Tr (iT (iT(Abrm)) (Atmn) (a Aton Aerntrr))
72
ira
42
Tr (ot Atrn Aernllen)
42
In conclusion, we have the training error:
|| X
W Wops Vtrn 1/
82 nf²
2 72
E
+
E(Tr(Ui Atrn Aern ATm (Almn) ? Totrr)
nf2
am 1141
Tr(T("" (Airm))
Ato Aten Afr (Atrn) Abrnn!)
n³²
o 22
2
Tr
nf2
Now estimate the above terms using random matrix theory. Here focus the 1 case. For C < 1, we note that
Atr Aern Afrm (T
Thus, for <
o (A)² (a: + 22)²
T Arm Atrn ATra (Atrr) Titnn
1=1
where at U. Vist. Taking the expectation, and using Lemma
9 we get that
Eawr (.T Air Atrn AT (Abmm) ) [8mm
+ 12c /(1 122)2 4c2 + 12 2 c cx2)2 + 462 22
1 c 1ie
2/ 1)
+ +
2c
Using Lemma II we see that the variance is o(1). Similarly, we have that
(Almm) )"r Alrn Aur AT (Atm.)) A),,, = 255-""""-----
Thus, again, using similar argument, we see that
1 P2cc
E (rtt)((A),))) (AI,.) o Alrm Aurn (A)mm) Al. u) 2 (1 c cu² + 4
2 + +
and again using Lemma [I the variance is o(1) Finally,
Atrn VV-'EV.
39

---

Thus,
2 oi(A)²
Tr At AtrnAAnnAnnn Atrn
a
(A(2 11?"
Thus, using Lemma 9 we get that
1 1 1²c v c - 2²c)²
4c2
E Tr(6pm Alr Aer Utrn
+ o(1)
2
2c
and using Lemma 11, the variance is (1). Then, similar the proof of Theorem the above expression to get the final result.
we can simplify
E.7 Proof of Proposition]
1
Proposition 1 (Optimal trn). The optimal value of o for < 1 is given by
d2 1)2 1 (cp + +c+ 2(cp² 2c 1)] + Nost ( + +1
(c (12 + + c2 + 1) 2c 1)
Proof. Let o == oim and
(
pis Nest + (o + +
F F=
Notice that only is function of o, [1 |1013. and |1 all functions of μ.. Then
OF -2 1 Oo d
(15 20 (1112p) 27
Ōr
oist
+ d (allilB -2(((()))))))
1
Zo
Nist
ria 1 (o11i11 + [001111BBB++ + oflll1))))
- (1l (1R/ 1/ 20 ((ll)p))) 25 -- - =1181111
Nis:
Peat Nest
= --- (11111 + 20(1(11pp) - 2T - 11011111111
The optimal 0² satisfies aF
do l==- 0. Thus, solve the equation
oia Nest
7 -- 0
d (11i1 + 20 18150) 2r
1101111111 1
Let a = 12. =
go Nett
Then
22
||
Notice that a < implics Jern is an imaginary number, something we don't want. Thus, we look at the other expression.
0 j (111112 + 10(1)) - 27 27 |
I
oi Nest
jalliill + o(((((1)p))
(11i) + (0(1)) -2 2r 8
+ + (011611+++2(/133)))))
a= |11131181111
d
40

---

Then multiplying through by d and 5
0 + < + 2o (012p) 20(66 |/ + 0010((22)
[ 1+ 1000 00
= + 2101
+ ail al| + 2011012p00 2ad 20e1111B00 20 20100/200
+ 2 + alIi11800 2ad - 2ax 2o.o.....
Then solving for σ, we get that
2ad |1Al2
2d] |100|1 Nost
2||8|1 p ailA||2
Nist (211 |
Then we use the random matrix theory lemmas to estimate this quantity.
41

---

Proof of low-rank case
Similar to the proof in 37 we conducted the low rank case.
We begin by defining some notation. Let Xtrn UEro Virn Here U is d x with U I, Enrn r x r, and Vern is r x (d + N). All of the following matrices are full rank.
1. Xirn and Xest is d (d + N) with rank Xmm [Xern 0]
2. Xemn = UEV, by the singular value decomposition. Let Xest = U..
3. U d x with UTU Ixr- V is x (d+ N).
4. Etrn is r, with rank r.
5. Airn [Arrn pll.
6. Atrn is x (N + d) with rank d.
7. Atm is (N + d) (N + d).
8. H is (N d). with rank r.
9. K is (N + d) x r, with rank r.
10. Z i xr, with rank r.
H1 xs with rank r.
12. Agn - =
13. Ú is idx x d unitary.
14. E is d d.
For rank data and < N, with N. the following true.
1. We denote the minimum norm linear denoiser Wopt by just in this subsection. It given by
W opp -EErr KT blo Utmml1 (QQ")~11
2. The test error when Xest = UL is given by
Pae I opt
E Aera
+ d
Nest
where Q= = ( At Agm)) H1 = VT A K= A U2mm Z = 1 + V At U Mern.
11 = KTK- + L (QQ)Q") -1
For < 1, we have that if d <
N then
V(1 pCc p²c- c)2 + 4pp2c22 - 1 + +o(1) I
c
E E Kd K [
212c
and if d > N then
-pcpppe +o(1) I.
E KJ KY-l1=
241²c
When d < N then
126² + 2 1²c 1 2c
1
1 (1- 1. o(1),
E KT At (Át )rH K KE
1
2 2 + (1 + 22)22
id then
1 1- 2c 2² +
+ 22
1
E E[ KT Atrm T
1 (1 2) 24
I, o(1).
20px
42

---

We have that
[[QQ"]= = (1 1 p²c v(-l+ct 22c22 4p²c
+ +0(1).
2c
and
2
EIQQ))
+ o11.
1 preec v-1++c+ /20 + 4
When d N have that
1 l+c
E[HH*]=C =
1. + d(1)
2/11 c+ p2o2 + 42 2)
and when N, we have
1 w²c
E[HH* 22(11++ 22222 + 4 2)
I, +
When d < N, we have
1222 + 2 + p.c- 2c
1 (1-2)
E [] =
24 411262 + (1 + p2c)2
24r
[[I+ w²c c)² + 111222 - p-cc
Tr
Is
1 - V +Po} + 4112 x'2
2
2 V
1 12c
1
1 1+ - 222
+
4112c
2 - c 12 402 2
V(++pe -2c c)2 41126 - - - c2c
2
Tr
E-2
2
1 1 -cc (1-1-V(-1cco 1
122022 + 412cc
+ o(1),
when d > N this is estimated by
1 - 2c p
1
E
B|]
+
204r (-
2/
(-1+c+ -1- protc 1 +
Tr
1 + pe - v(-1+ + c c + 1 S-2
24
2
2
1 1+c+ 12c
1
+
IH(I-9)
1t - 122022 41126
2v(-1+ct [20)= + x 41i2c
2
-2
2
Tr
D-2
212c
1 p-cc - 22) 4
+o().
43

---

When d < N the test error R(W, Xest) for W = Wopt is given by
A4 + (- c+ x2
/= p C 1r
R(W, ((s)) = Tr((
Neat
21²c
2
+
2--
1+ ++ p.c ((-1 c /==c22 + 4110c
2
v( ((- + + 2) + 411 TT
1 + p.c+
Jist
2 + 8 + prc 2c +1
2p (1-2))
+ d
24 42220² + (1 + p²²c)2
[[1+ 12- - 0)² + 411² w I
Tr
1?o)2 41pc 5-2
21²c
1t - p
2
2
1 1 PCC
!
+
Tr(I-
d
11+pec ( c2cc 4112c
2/(1 - 12)z + 4
2
[V[++ pi= c)2 + 4/1202 - - caccc
Tr
2122
1 ( 122222 + 4
+ (1);
when d > N this is estimated by
R(W, X1St) = Tr(( V (-I++++
+ pPcf2
p²c p²cec
Nest
2112c
2
+
--
1+ p2p -
411²c
2
Tr
1 + -
22 + ApFc
det
1- 2 1 22c2
1
+
+ (1
d
2ccu / ( ct 22c)2
c 2pt
(-1+ 1-p-1-
Tr
1,
2/
v[1 - w2of2 + 1112c
2
+ Pit
2
l+c+
1
Tr
d
1 11ppccc-v(--ee 12c 41zc
(-1+++c+ wFcf2 + 4wFc
2
(-1+c++(1+c+pe)) p²cp - 12c+c
2
Tr
4
2-2
24²c
1 u2c + c- --peeec p²c)) + 4
+ o(1).
G Experiments
All experiments were conducted using Pytorch and run on Google Colab using an A100 GPU. For each empirical data point, we did at least 100 trials. The maximum number of trials for any experiment was 20000 trials.
For each configuration of the parameters, Ner, Neat, d, Otrn, Ttst and For each trial, we sampled u, Vten, Vest uniformly random from the appropriate dimensional sphere. We also sampled new training and test noise for each trial.
44

---

For the data scaling regime, we kept d = 1000 and for the parameter scaling regime, we kept Ntr 1000. For all experiments, Nest 1000.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Both the abstract and introduction reference the main two Theorems (Theorem and Theorem 2). Additionally, both put them in the context of prior work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We believe the main purpose of the paper is to show that certain phenomenon exists and are very careful with our assumptions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
45

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All statements have corresponding detailed proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have very few experiments. However, for each one we have a section in the appendix with the needed details and have provided code as part of the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
46

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We include the code as part of the submission. All data used is synthetic or already open source.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips.c cc/
public/ des Subee ss coooooollll oonoolcc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. httpcc/ppuuu httpp//blcccc/eeeep guidees////ee Sed/CodeSuull www.bmsssooooliiii..
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have very few experiments. However, for each one we have section in the appendix with the needed details and have provided code as part of the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[No]
Justification:
The paper is theory paper about mean behavior under a variety concentra- tion results.
Guidelines:
47

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Google Collab with an A100 was used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htt:t::ttp://eee ipsarripp.. ips wwtpcc/cpcccccteecccccccc wtw.bl/iiieccchccciieeeeeeeeee csGuide iees
nes?
Answer: [Yes]
Justification:
Guidelines:
The paper conforms with the code of ethics.
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdictio))
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This theoretical work that helps build understanding of existing phe- nomena.
48

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is theoretical work
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We credit pytorch.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
49

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papelpappssss wwwwhhocee com/ cataaaaasseseee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This is theoretical work
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This is theoretical work
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This is theoretical work
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
50

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "kagi0hVMsK", "reviewer": "Reviewer_4Q1q", "summary": "The authors show several facts about the double descent phenomena for the linear regression model with L2 loss and Frobenius norm regularization. They show taking different assumption from previous work moves the peak of the risk of the problem from the interpolation point into the under-parameterized regime. Provided theorems concretely describe the position of peak risk, including separating the risk into several terms: bias and the norm of the estimator. The authors also provide derivations (appendix) and experiments.", "questions": "Line 190: Is the assumption \"$d$ is sufficiently large\" used only to assume $o\\left(1/d\\right)=0$ in the Equation between Lines 177 & 178? If so, clarifying it in the main text would be better.\n\n\n\nDoes $\\left\\|W_{opt}\\right\\|_F$ in Line 240 indicate its expectation?\n\n\n\nI recommend the authors to double check the overall text and equations. Here is a list of errata & typos.\n\nNote that from the equation between Line 119 and Line 120, $\\hat \\beta\\in\\\\mathbb{R}^{d\\times k}$.\n\n* Line 120: $\\hat\\beta = y X^\\dagger$ -> $\\hat \\beta = \\left(X^\\dagger\\right)^Ty^T$\n\n* Displayed Equation between Lines 123-124: The denominator seems wrong. The following should be correct:\n\n$$\n\\left\\|\\hat\\beta\\right\\|^2 = \\sum_{i=1}^{\\mathrm{rank}\\left(X\\right)}\\frac{\\left(y V\\right)_i^2}{\\sigma_i^2}\n$$\n\n* Line 129: It would be better to add a couple of words emphasizing $\\Sigma_n^{1/2}$ indicates the diagonal matrix $\\Sigma$ in $X=U\\Sigma V^T$ for readability. $\\Sigma_n^{1/2}z_i$ looks like a summation symbol. I first thought it is a typo of $\\sum_{i=1}^{1/2}z_i$.\n\n* Displayed equation between Lines 137-138: $z\\in \\mathbb{C}\\setminus J$ -> $\\zeta\\in \\mathbb{C}\\setminus J$\n\n* Lines 239-240: Is \"for $n$ large enough and $d=cn$\" a typo of \"for $n$ and large enough $d=cn$\"?", "limitations": "Does the previous work (peak at interpolation point, using Assumptions 1 and 2) also rely on Assumptions 3 and 4? Or are you using just a different set (A 2 & 3 & 4) of assumptions which is a neither necessary nor sufficient condition of one of the previous work (A 1 & 2)? It should be stated more clearly.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Their analysis is thorough. Especially, reasoning change of trends of risks in Figure 4 through the term of the norm of the estimator supports the reliability of the results. They clarify proof steps in the appendix. Experiments provided to support each theorem also look thorough.", "weaknesses": "The authors results which do not coincide with prior theory are based on different assumptions. Can the authors discuss how wider cases covered by their assumption?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our analysis thorough, especially the reasoning for the trends. We now address the reviewer's concerns. \n\n> The authors results which do not coincide with prior theory are based on different assumptions. Can the authors discuss how wider cases covered by their assumption?\n\nWe believe that much prior work assumes Assumptions A1 (alignment between $y$ and $V$) and A2 (Stieljtes Transform Peak). **In our paper, we want to construct examples that violate these two assumptions.** Hence, the example in Section 4 makes assumptions A3 and A4 (not A1 and A2), while the example in Section 5 is a mixture of a high-dimensional Gaussian and a one-dimensional Gaussian. \n\nAssumptions A3 and A4 exist in prior work such as [24,37]. These works do have a peak at $c=1$. In our paper, setting $\\mu = 0$ recovers [24]. Appendix A, F has the corresponding result for which setting $\\mu = 0$ recovers [37]. \n\nThe mixture example can be viewed as an extension of prior theory presented in papers such as Dobriban and Wager, and Hastie et al., by taking data distributions that satisfy their assumptions and creating a mixture with a distribution supported on a lower dimensional set. Setting $\\pi_1 = 1$ (i.e., removing the low dimensional component) recovers an example that satisfies their assumptions\n\nFinally, we would like to highlight some prominent examples that explicitly assume A1 and A2 or their assumptions imply A1 and A2 are satisfied. \n\n**Dobriban and Wager, 2015**\n\n*A1*\n\nAssume that $\\beta$ (and hence $y$) has an isotropic distribution (Assumption B in the arxiv version). Hence, $y^T V$ has an isotropic distribution. Hence, they assume A1. \n\n*A2*\n\nThe paper assumes assumption A and that the operator norm of the expected sample covariance is uniformly bounded. These assumptions then satisfy the assumptions of Theorem 1.1 in [BZ08], which implies that the Stieljtes transform of the limiting distribution satisfies \n\n$$ m(z) = \\int \\frac{1}{t(1-c-czm) - z} dH(t), $$ \n\nwhere $H$ is the limiting distribution of the population covariance matrix, our assumption A2 is concerned about the function $c \\mapsto m(0)$. Here, we see that \n\n$$ m(0) = \\int \\frac{1}{t(1-c)} dH(t) $$ \n\nThis function is clearly maximum when $c = 1$. Hence, it satisfies assumption A2. \n\n**Hastie, Montanari, Rosset, Tibshirani, 2020**\n\n*A1*\n\nThey assume that data $x_i \\sim \\mathcal{N}(0,\\Sigma)$. If the $x_i$ are the columns of $X = U\\Sigma V$ (as is the notation in our paper). Then $XX^T/n = U\\Sigma\\Sigma^T U^T / n$ is the sample covariance. Hence, it is not dependent on $V$. Hence, this implies that the distribution of $V$ doesn't impact the sample covariance matrix. Hence, we believe this is similar to assuming that $V$ is uniform. Hence, assuming $y^T V $ is istropic. \n\n*A2*\n\nSimilar to the Dobriban paper, their data satisfies the assumption of Theorem 1.1 in [BZ08].\n\n[BZ08] Zhidong Bai and Wang Zhou. Large sample covariance matrices without independence structures in columns.\n\n> Line 190: Is the assumption \" is sufficiently large\" used only to assume $o(1/d) = 0$ in the Equation between Lines 177 & 178? If so, clarifying it in the main text would be better.\n\nThe reviewer is right. We shall clarify this. \n\n> Does $\\|W_{opt}\\|$ in Line 240 indicate its expectation?\n\nYes, thank for yo pointing this out, we shall correct this. \n\n> I recommend the authors to double check the overall text and equations. Here is a list of errata & typos.\n\nWe thank the reviewer for the typos found. We shall correct them. \n\n> Does the previous work (peak at interpolation point, using Assumptions 1 and 2) also rely on Assumptions 3 and 4? Or are you using just a different set (A 2 & 3 & 4) of assumptions which is a neither necessary nor sufficient condition of one of the previous work (A 1 & 2)? It should be stated more clearly.\n\nSome prior work assumes A3 and A4 (such as [24,37], setting $\\mu = 0$ in our result recovers those results); however, other prior work does not. The key fact is that A1 and A2 are true in prior work in these prior works. \n\n---------\n\nWe hope that we have addressed all of the reviewers' concerns and questions and improved their opinion of our work. If the reviewer has further concerns, please let us know.", "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": "", "extra_scores": {}}, {"review_id": "KSo60cAzCe", "reviewer": "Reviewer_4cXR", "summary": "The paper considers the problem of linear least squares. Its main contribution is presenting two examples of double descent in the under-parameterized regime.", "questions": "I have no questions. It should be noted that I am not an expert in the exact area of double descent. I am not very familiar with the proof techniques used in the literature and am unable to make comments on technical depth.", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written: Related works are sufficiently discussed (to my knowledge); the introduction is well-motivated and easy to follow; theorems are often followed by examples, figures, and illustrations helping the reader understand the results.\n- The problem the paper investigates and the perspective the paper takes is quite interesting. While the mainstream research in the field focuses on double descent in the case of over-parameterization, the paper analyzes under-parametrization in-depth and presents several results that improve one's understanding of double descent.", "weaknesses": "- The paper takes unconventional notations that make the paper more challenging to penetrate. For example, it uses row vector notations and writes vector-matrix multiplication $\\beta^\\top X$ rather than the more common matrix-vector multiplication $X^\\top \\beta$. Sometimes I also found that the notations of singular vector $u$ and regularization parameter $\\mu$ can be confusing as they look similar.\n- The two examples the paper offered are indeed examples. The reason is that the paper's assumptions are quite strong. For example, Assumption 3 assumes the test and training data matrices are both of rank $1$, and Theorem 4 has the orthogonality assumption $\\beta^\\top z=0$ which greatly simplifies the model and analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our paper well-written and our perspective interesting. We now address the reviewer's concerns. \n\n> Notation\n\nWe shall fix $\\beta^T X$ to $X^T\\beta$ to align the paper better with the prior convention. We shall change the font for the $u$ to clarify the difference. \n\n> Strong Assumptions\n\nWe agree with the reviewer that some of our assumptions are strong. However, we believe that this helps us highlight the dependence of the location on the peak on 1) the alignment between $y$ and $V$ and 2) The peak in the Stieljtes transforms curve at 0. \n\nHowever, here we discuss some relaxations of the assumptions. \n\n------------\n\nFor rank 1 assumptions, we refer the reviewer to Appendix A and Appendix F, where we provide a conjectured formula for general rank $r$  data as well as numerical verification of the conjecture. \n\n-------------\n\nFor the orthogonality assumption, this is primarily to simplify the proof. **Please note that in the numerical simulations displayed on the left of Figure 7, $\\beta$ is not orthogonal to $z$.** This version of the result can be proved. \n\nWe will update the paper with the result without assuming orthogonality. Here are the proof changes sketched out. \n\nIf we do not make this assumption, Then at the bottom of page 19, we would have an additional term: \n\n$$ \\frac{\\|v\\|^2}{1+\\|v\\|^2 z^T(AA^T)^{-1}z} \\beta^T z z^T(AA^T)^{-1} $$\n\nThus, on line 565, when we compute the excess risk, instead of \n\n$$\\mathbb{E}\\left[\\left\\|\\left\\|\\xi^T \\begin{bmatrix} A^T \\\\ vz^T \\end{bmatrix} \\left(AA^T + \\|v\\|zz^T\\right)^{-1} \\right\\|\\right\\|^2 | X \\right],$$ \n\nwe would have \n\n$$\\mathbb{E}\\left[\\left\\|\\left\\|\\xi^T \\begin{bmatrix} A^T \\\\ vz^T \\end{bmatrix} \\left(AA^T + \\|v\\|zz^T\\right)^{-1} +  \\frac{\\|v\\|^2}{1+\\|v\\|^2 x^T(AA^T)^{-1}z} \\beta^T z z^T(AA^T)^{-1}\\right\\|\\right\\|^2 | X \\right]$$\n\nThen, we can expand the term norm into parts and see that the cross terms are zero due to $\\xi$ being independent from $z, A$ and having mean zero. The first term would be \n\n$$\\mathbb{E}\\left[\\left\\|\\left\\|\\xi^T \\begin{bmatrix} A^T \\\\ vz^T \\end{bmatrix} \\left(AA^T + \\|v\\|zz^T\\right)^{-1} \\right\\|\\right\\|^2 | X \\right],$$ \n\nwhich have already shown how to compute the expectation. For the second term, to understand the contribution of the norm of this term, we would need to compute \n\n$$  \\left(\\frac{\\|v\\|^2}{1+\\|v\\|^2 z^T(AA^T)^{-1}z}\\right)^2 \\text{Tr}(z^T(AA^T)^{-2} z) $$\n\nUsing the estimates from lines 568-570 and the same concentration results from [24], we see that this concentrates around\n\n$$ \\left(\\frac{\\|v\\|^2}{1+\\|v\\|^2\\mathbb{E}\\_{\\lambda \\sim \\nu}\\left[\\frac{1}{\\lambda}\\right]}\\right)^2 \\mathbb{E}\\_{\\lambda \\sim \\nu}\\left[\\frac{1}{\\lambda^2}\\right] $$\n\nThen, since the covariance for the Gaussian part is $\\frac{\\pi_1}{d} I$. Multiplying, we get that this term goes to zero as $d \\to \\infty$. Hence, the error formula is unchanged. \n\n------------\n\nWe hope that this has addressed the concerns of the reviewers and improved their opinion about our work. If the reviewer has further concerns, please let us know.", "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": "", "extra_scores": {}}, {"review_id": "Y4TYYTFiev", "reviewer": "Reviewer_LfUR", "summary": "In this paper, the authors focus on the generalization performance of linear least squares regression and show the existence of double descent generalization curve  in the under-parameterization regime.\nIn particular, the authors argue, in the linear model in (1) under study (which is slightly different from standard linear models in the literature, but well motivated), that the generalization risk can have a peak in the under-paramererized regime that is due to the alignment between singular space of data and the target, and spectrum of data covariance, instead of the raw dimension ratio or the explosion of the estimator norm.\nSome numerical results are provided to support the theoretical analysis.", "questions": "* line 35: when summarizing the contribution of this work, it would be helpful to forward point to the corresponding theoretical result and/or definition, for the sake of a precise statement of the technical result or the definition (for example, the spiked covariate model).\n* it seems that the footnotes 3 and 4 are missing?\n* Equation after line 123: I am a bit confused here. What is the purpose here? Is $\\hat \\beta$ still the min norm solution, then what is $\\beta$?\n* To make Definition 1 more rigorous, perhaps say here that the convergence of ESD holds in a weak sense as $k \\to \\infty$, or something like that?\n* Theorem 1: perhaps say somewhere in the theorem that this result holds in the asymptotic setting as $n,d,n_{tst}$ going to infinity at the same pace?\n* Honestly, I do not understand this result. It seems to me that my previous comment is wrong, and that the result in Theorem 1 does NOT hold in the limit of $n,d,n_{tst} \\to \\infty$ together, or at least, $n_{tst}$ and $n$ can be much larger than $d$. Some specifications and discussions are needed here. \n* Theorem 2 looks interesting. Could the authors comment more on this? For example, note that taking $\\mu = 0$ is (more or less) similar to the ridgeless case in the literature. There, according to Theorem 2, we should have a at $c = 1$, as in accordance with \"classical\" double descent.  So, should we understand Theorem 2 as an extension of \"classical\" double descent to the regularized setting? Or is this due to the model in (1) and (2)?\n* line 207 -208: $\\hat \\Sigma^T \\hat \\Sigma = \\Sigma^T \\Sigma + \\mu^2$ a typo here?\n\n---\nI thank the authors for their detailed reply, which helps me better understand their theoretical results and their contribution I increase my score accordingly. \n\nI, nonetheless, feel that there are a few typos that need be fixed and clarifications needed, in the current version of the paper.", "limitations": "I do not see any potential negative social impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem under study is of significance.\nThe message of this paper looks interesting. But I find it a bit hard to really understand the results and contribution, see my comments below.", "weaknesses": "While this paper looks interesting, it is a bit hard for me to really understand the results and contribution.\nI think making precise the dimension settings (relation between $n, d, n_{tst})$ will address this issue, see some of my detailed comments below.\nAnother issue is the contribution: while Theorem 1 is rather general, the discussion thereafter seems all special cases: For example Theorem 2 is a special case, and the results in Sec 4.3 and 4.5 are essentially numerical. The discussions in Sec 5 is interesting but again a very special setting (mixture model of multivariate Gaussian and a fixed direction) without any motivation. It is thus difficult for me to evaluate the significance of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that the problem we study is significant and that the findings are interesting. We now address the reviewer's concerns.\n\n> Another issue is the contribution: while Theorem 1 is rather general ... It is thus difficult for me to evaluate the significance of this work.\n\nThe paper's main purpose is to attempt to understand the reasons peaks occur in the excess risk curve and their locations. Prior work has phrased this as occurring due to overparameterization and the location being on the boundary of the under and overparameterized regimes. Additionally, some prior work [32] has criticized parameter counts as a measure of complexity, saying that parameter counts might overestimate the true complexity. Hence, shifting the boundary between under and over-parameterized to the **right, not the left**. \n\nWe question this narrative. In particular, we show that the location of the peak is determined by technical reasons in random matrix theory **and not because it is the boundary between over and under-parameterized**. To show this, we present the two conditions in **Section 3 and, in particular, lines 145 to 148 highlight them again.** The rest of the paper then presents two examples where each example violates exactly one of the conditions, and we show that the peak moves to the left. \n\nIn particular, our examples let us move the peak to the left and control its location.\n\n> Scaling of $d$, $n$, and $n_{tst}$\n\nThis is a great question. Our results are valid for **any** $n$, $d$, and $n_{tst}$. However, they are only meaningful when $n$ and $d$ are large, and $d$ and $n$ are proportional. Note that we assume that $\\sigma^2_{tst} = O(n_{tst})$. The last error is mostly independent of the scaling of $n_{tst}$. \n\nThis can be seen as follows. The primary proof technique is concentration of measure. In particular, we want to show that the risk concentrates. Theorem 1 can be interpreted as saying when $c = d/n$ that (grouping the first and second term together)\n\n$$ \\left|\\mathcal{R}(c, \\mu) - \\frac{\\sigma\\_{trn}^2(\\sigma\\_{trn}^2 + 1)}{2d\\tau^2} \\left( \\frac{c(1+c+\\mu^2 c)}{\\sqrt{(1-c+\\mu^2 c)^2+4\\mu^2 c^2}} - 1\\right)  - \\frac{\\sigma\\_{tst}^2}{\\tau^2 n\\_{tst}} \\right| = o\\left(\\frac{1}{d}\\right) = o\\left(\\frac{1}{n}\\right) $$\n\nHence, we show that the error concentrates around the above expression with an error of order $o\\left(\\frac{1}{d}\\right)$. Hence if $d,n$ are small, the error might be large, however, if $d,n$ are large then the error will be small. \n\nTo make sure this is meaningful, suppose $\\sigma_{trn}^2 = \\Theta(n) = \\Theta(d)$ (we are assuming $n$ and $d$ are proportional) and $\\sigma_{tst}^2 = \\Theta(n_{tst})$. Then we see that $\\tau^2 = \\Theta(n^2) = \\Theta(d^2)$. Then we see that the first term $\\frac{\\sigma_{trn}^2(\\sigma_{trn}^2 + 1)}{2d\\tau^2} \\left( \\frac{c(1+c+\\mu^2 c)}{\\sqrt{(1-c+\\mu^2c)^2+4\\mu^2c^2}} - 1\\right)$ is $\\Theta(1/d) = \\Theta(1/n)$. The final term $\\frac{\\sigma_{tst}^2}{\\tau^2 n_{tst}}$ of order $\\Theta(1/d^2)$. Thus, the whole expression is of order $\\Theta(1/d)$, while the error goes to zero faster. \n\n> line 35: when summarizing the contribution of this work, it would be helpful to forward point to the corresponding theoretical result and/or definition, for the sake of a precise statement of the technical result or the definition (for example, the spiked covariate model).\n\nThank you for this suggestion. We had forward pointers to the Theorems; however, we shall do this for the definitions as well. \n\n> Footnote links\n\nWe apologize for this. \n\nFootnote 3 points to Appendix A and F, which discuss the low-rank version of Theorem 1. Appendix A provides numerical experiments to verify the formula, and Appendix F has a statistical physics-type derivatization for the error. \n\nFootnote 4 states that [41] only considers optimal regularization. \n\n> Line 123\n\nApologies, it should be $\\hat{\\beta}$ on line 123 and the equation should be $\\frac{(y^TV)_i^2}{\\sigma_i^2}$\n\n> Definition 1\n\nThank you, we shall add the phrase. \n\n> Theorem 1: perhaps say somewhere in the theorem that this result holds ...\n\nand \n\n> Honestly, I do not understand this result...\n\nPlease see our response on the scaling on $d$ and $n$. *It is imperative that we clarify any concerns about the theoretical results. Please let us know if something is still unclear.*\n\n> Theorem 2 looks interesting...\n\nSetting $\\mu = 0$ exactly recovers the result from [24], so it is an extension of that result. It is not a direct extension of the results in, say, Dobriban and Wager, Hastie et al., or Bartlett et al. Those settings are different. \n\nIn our setting we have low dimensional signal, the response depends on the signal and have noise on the inputs. In the setting of Dobriban and Wager, Hastie et al., or Bartlett et al., we have full dimensional signal and noise on the outputs. The regularized extension for these works can be seen in [11,23]. Here, we see double descent for certain $\\mu$, and for the optimal $\\mu$, we do not. **However, the peak does not move!**. This and more prior work are summarized in Table 1. \n\nIn our work, the peak moves $\\mu$, which is quite surprising. *Classical wisdom would states* that increasing $\\mu$ would *increase* the regularization, hence would *decrease* the complexity of the model. Hence, we would need *a larger* number of parameters to overfit. Hence, the peak would move to the *right* in the overparameterized regime. \n\nHowever, we show that the peak moves to **left**!\n\n> Line 207-208\n\nApologies, that is a typo. It should read $\\hat{\\Sigma}^T \\hat{\\Sigma} = \\Sigma^T \\Sigma + \\mu^2 I$. \n\n\nWe thank the reviewer again for their detailed comments. We hope that our response addressed all of the concerns. We would be eager to continue the conversation if there are any more concerns. \n\nWe hope that the response has improved the reviewer's opinion on our work.", "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": "", "extra_scores": {}}, {"review_id": "MGhz59CdBK", "reviewer": "Reviewer_RQj2", "summary": "The authors explore the double descent phenomenon, postulating that the location of the peak (that separates the \"classical\" and the \"modern\" interpolating regime) depends on the properties of the spectrum and the eigenvectors of the sample covariance. In particular, the authors show that the violation of one of two assumptions (assumption 1: Alignment of y and right singular vectors of X; assumption 2: Stieljtes Transform Peak Assumption) can move the peak from the interpolation point into the under-parameterized regime. They also present two simple examples that exhibit double descent in the under-parameterized regime and do not seem to occur for reasons provided in prior work.", "questions": "- What do the authors exactly mean by input and output noise?\n- In Table 1 (page 3), where are the footnotes related with numbers 3 and 4?\n- In Figure 3, what ablation experiments do the authors refer to?", "limitations": "- In my opinion, the authors do not sufficiently discuss the limitations of the work performed. In fact, in the NeurIPS Paper Checklist, they only state that \"We believe the main purpose of the paper is to show that a certain phenomenon exists and are very careful with our assumptions.\"", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles a very important research topic, and tries to understand the reasons behind the location of the peak in double descent. \n- The work seems rigorous and the contributions relevant. \n- Overall, the paper is well-written and reasonably clear.", "weaknesses": "- The conclusions of the paper are very brief and, from my point of view, not very informative (see section 6 in the paper). In relation to this, I also perceive a certain imbalance in the weight of the two examples provided: while the first (the one related to \"Alignment Mismatch\") occupies 3 pages of the work, the second example (\"Shifting Local Maximum for Stieljtes Transform as a Function of c\") is addressed more hastily (one page).\n- The volume of information provided by the paper is very high. From this point of view, I think it would be positive to recapitulate and indicate clearly, and in a simple and intuitive way, the way in which the risk curves shown throughout the paper are created (Figures 2, 4 and 6). The same applies to Figure 3: what ablation experiments do the authors refer to?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that the paper tackles a very important research topic, is rigorous with relevant contributions, and is well written. We now address the reviewer's concerns. \n\n> The conclusions of the paper are very brief and, from my point of view, not very informative (see section 6 in the paper). In relation to this, I also perceive a certain imbalance in the weight of the two examples provided: while the first (the one related to \"Alignment Mismatch\") occupies 3 pages of the work, the second example (\"Shifting Local Maximum for Stieljtes Transform as a Function of c\") is addressed more hastily (one page).\n\nWe agree that the conclusions are short. In the final version of the paper, we shall increase the length of the conclusions to make it more substantive while balancing the two examples. In particular, we will add the stronger version of Theorem 4 mentioned in the response to reviewer 4cXR. \n\n> The volume of information provided by the paper is very high. From this point of view, I think it would be positive to recapitulate and indicate clearly, and in a simple and intuitive way, the way in which the risk curves shown throughout the paper are created (Figures 2, 4 and 6). The same applies to Figure 3: what ablation experiments do the authors refer to?\n\nThank you for the feedback. We shall do so. \n\nThe ablation experiment is described on lines 212 to 218, where we break the misalignment in two ways. \n\nFirst, we consider the unregularized problem and artificially shift the spectrum of the noise matrix. This results in the shifted noise matrix having the same spectrum as the effective spectrum in the regularized problem. However, the alignment wasn't broken, so we see the peak at 1. Figure 3 (left). \n\nSecond, for the regularized problem, we artificially fixed the alignment and noticed that the peak is now in the over-parameterized regime. \n\nHence, the experiment validates the theory that the location of the peak was due to the misalignment. \n\n> What do the authors exactly mean by input and output noise?\n\nConsider a linear function $y = \\beta^T x$. This is a function that we are trying to fit. However, if we had access to exactly the correct inputs $x$ and outputs $y$, then solving the problem would be easy, and we would never see a double descent. To see double descent, we need to introduce noise into the problem. This can be done in two ways. \n\n1. Output noise. That is, we do not receive the responses $y$, but noisy versions, so $y = \\beta^T x + noise$. \n2. Input noise. Now, instead of getting noisy $y$ measurements. We get the true measurements $y$ but receive noisy inputs $x$. \n\n> In Table 1 (page 3), where are the footnotes related with numbers 3 and 4?\n\nWe apologize for this.\n\nFootnote 3 points to Appendix A and F, which discuss the low-rank version of Theorem 1. Appendix A provides numerical experiments to verify the formula, and Appendix F has a statistical physics-type derivatization for the error. \n\nFootnote 4 states that [41] only considers optimal regularization.\n\n> In Figure 3, what ablation experiments do the authors refer to?\n\nThe ablation experiment is described on lines 212 to 218, where we break the misalignment in two ways. \n\nFirst, we consider the unregularized problem and artificially shift the spectrum of the noise matrix. This results in the shifted noise matrix having the same spectrum as the effective spectrum in the regularized problem. However, the alignment wasn't broken, so we see the peak at 1. Figure 3 (left). \n\nWe hope that this has addressed the concerns of the reviewers and improved their opinion about our work. If the reviewer has further concerns, please let us know,", "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": "", "extra_scores": {}}, {"review_id": "jubc9CfbGU", "reviewer": "Reviewer_SLpr", "summary": "The paper aims to understand the phenomenon of double descent in regression, and helps complement existing knowledge about the phenomenon by proving that double descent can occur even in the under-parametrized regime, going against previous intuition. They also prove that the peak in the norm of the estimator does not imply a peak in the risk.", "questions": "Figure 2: I see a clear peak, but I do not see an initial “descent”. Is there something I am missing here? Why does the model have best generalization at $c = 0$? I am guessing that the focus of the study is on the peak, although that is not the full picture of double descent as I am not seeing the initial descent. That is okay, but just make clear why there is no initial descent.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Quality and Clarity: Contextualization relative to prior work is good, Table 1, for example, provides a very concise and insightful summary of existing results. \n\nOriginality: The paper considers an original viewpoint on the problem of double-descent, namely they realize that violating either Assumptions 1 or 2 can cause the peak to move into the under-parametrized region. To the best of my knowledge, this had not been noticed before. \n\nSignificance: This result is significant, as it addresses the prominent double-descent phenomenon in machine learning, which is an important primitive for understanding generalization and other properties of estimators operating on high-dimensional data. They also prove that a peak in the norm of the estimator does not imply a peak in risk, and this is important as it goes against some of the intuition provided in earlier works.", "weaknesses": "Clarity: Although the contextualization relative to prior work is good, I find that the paper lacks in clarity. In particular, it is not exceptionally well written, and leaves some sections with much to be desired in terms of exposition. Specific examples are: \n\n- Table 1: What does 1/Low mean? The superscript 3 leads to nowhere.\n- Middle of page four: “Hence, this is controlled by 1. The alignment…, 2. The spectrum”. What exactly is being controlled here? And why exactly is it controlled by 1. and 2. ? This is not immediate to me, and I think this needs to be made more precise.\n- Over-use of italics in the introduction makes it hard to know what to focus on. I would recommend maximum one italicized sentence per paragraph.\n- Section 4.1: be more precise about the model, I don’t know what it is at this point. I later identify that $X + A$ represents the spiked data, but this must be made clear earlier on.  I find“Let A be the noise matrix” to not be clear enough.\n- Theorem 1: a comment on the proof technique for this theorem would be helpful, even if you have already mentioned it previously (or given the intuition). Also, the interpretation of Theorem 1 is not clear until we read Theorem 2, could you interpret Theorem 1 a bit more and specifically identify what it says that is not said in Theorem 2? Is Theorem 2 just a corollary of Theorem 1?\n- The first sentence of the abstract is not clear. Overall, the abstract may need to be rewritted in a more professional manner, not referring to previous works as \"believing\" in something, but something more precise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the paper's good contextualization, its original viewpoint, and its significant result. \n\nWe now address the reviewer's concerns. \n\n> Clarity: Although the contextualization relative to prior work is good, I find that the paper lacks in clarity. In particular, it is not exceptionally well written, and leaves some sections with much to be desired in terms of exposition. Specific examples are:\n\nWe thank the reviewer for pointing out these concerns. We shall address them in the revised version of the paper. \n\n> Table 1: What does 1/Low mean? The superscript 3 leads to nowhere.\n\nSubscript 3 points to Appendices A and F, which present a conjectured formula for the low-rank case with experimental evidence. We shall update the table only to say 1, the rank considered in the main text. \n\n> Middle of page four: “Hence, this is controlled by 1. The alignment…, 2. The spectrum”. What exactly is being controlled here? And why exactly is it controlled by 1. and 2. ? This is not immediate to me, and I think this needs to be made more precise.\n\nWe apologize there was a typo in the equation, it should read $\\sum_{i=1}^r \\frac{(y^T V)_I^2}{\\sigma_i^2}$. \n\nThis quantity depends on two things: the product $y^TV$, which we call the alignment, and $\\sigma_i^2$, which is the spectrum. \n\n> Over-use of italics in the introduction makes it hard to know what to focus on. I would recommend maximum one italicized sentence per paragraph.\n\nWe thank the reviewer for the feedback and shall reduce the number of italicized phrases. \n\n> Section 4.1: be more precise about the model, I don’t know what it is at this point. I later identify that $X + A$ represents the spiked data, but this must be made clear earlier on. I find“Let A be the noise matrix” to not be clear enough.\n\nWe shall add a definition for the spiked model in section 4.1 \n\n> Theorem 1: a comment on the proof technique for this theorem would be helpful, even if you have already mentioned it previously (or given the intuition). \n\nWe shall add the following small proof sketch to the paper.\n\n*Sketch:* The main steps for the proof are as follows. First, we use the results from [49], which is like a Sherman Morrison formula but for pseudoinverses. Following this, we rewrite the error as a sum and product of various dependent quadratic forms. We then use ideas from random matrix theory and concentration of measure to show that each quadratic form concentrates on a deterministic number that depends on the Stieljtes transform of the limiting empirical spectral distribution. We then show that the product/sums of dependent forms also concentrate. This gives us the error rate as well. \n\n> Also, the interpretation of Theorem 1 is not clear until we read Theorem 2, could you interpret Theorem 1 a bit more and specifically identify what it says that is not said in Theorem 2? \n\nTheorem 1 provides the complete error curve as a function of $c$, not just where the maximum is. Prior works such as [24,48] have shown that noise on the independent variable acts as a regularizer. Hence, we have two regularizers for the problem - the noise and the ridge regularization. It is interesting to explore their tradeoffs. We do this in Appendix D. We shall expand on this in the main text. \n\n> Is Theorem 2 just a corollary of Theorem 1?\n\nTheorem 2 can be viewed as a corollary of Theorem 1. It follows by taking the leading terms in Theorem 1 and doing calculus (compute the first derivative to find the critical point and the second to check that it is a maximum). \n\n> The first sentence of the abstract is not clear. Overall, the abstract may need to be rewritted in a more professional manner, not referring to previous works as \"believing\" in something, but something more precise.\n\nWe thank the reviewer for pointing out this concern and shall change the phrasing to make it clearer. \n\n> Figure 2: I see a clear peak, but I do not see an initial “descent”. Is there something I am missing here? Why does the model have best generalization at $c = 0$? I am guessing that the focus of the study is on the peak, although that is not the full picture of double descent as I am not seeing the initial descent. That is okay, but just make clear why there is no initial descent.\n\nThe reviewer is correct that there is no initial descent. This is actually quite common for linear models. See Hastie et al (2020) for many such examples. \n\nWhether the error is minimum at $c = 0$ vs $c = \\infty$ is quite interesting and related to benign overfitting. $c~0$ is the case when $n >> d$. Hence, we have a lot of data points. Hence, classically, we hope for consistent estimators. Hence, we can expect to do well. \n\nThe $c ~\\infty$ case is when $d >> n$. This is the largely overparameterized case. If the global minimum is here, this suggests that the model exhibits benign overfitting. \n\nFor our examples, benign overfitting seems absent, and hence, the minimum is at $c = 0$.\n\nWe hope this has addressed the reviewers' concerns and improved their opinion about our work. If the reviewer has further concerns, please let us know,", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their time, effort, and feedback. 

The paper's main purpose is to attempt to understand the reasons peaks occur in the excess risk curve and their locations. Prior work has phrased this as occurring due to overparameterization and the location being on the boundary of the under and overparameterized regimes. Additionally, some prior work [32] has criticized parameter counts as a measure of complexity, saying that parameter counts might overestimate the true complexity. Hence, shifting the boundary between under and over-parameterized to the right, not the left.

We question this narrative. In particular, we show that the location of the peak is determined by technical reasons in random matrix theory and not because it is the boundary between over and under-parameterized. To show this, we present the two conditions. The rest of the paper then presents two examples where each example violates exactly one of the conditions, and we show that the peak moves to the left.

We would also like to summarize the strengths of the paper as highlighted by the reviewers. We address the concerns of the reviewers in the individual responses. 

1. Paper studies as Important Problem. \
    a. Reviewer LfUR - "The problem under study is of significance."\
    b. Reviewer RQj2 - "The paper tackles a very important research topic, and tries to understand the reasons behind the location of the peak in double descent."\
    c. Reviewer SLpr - "addresses the prominent double-descent phenomenon in machine learning, which is an important primitive for understanding generalization and other properties of estimators operating on high-dimensional data"



2. The persecpective of the paper is new, interesting, and rigorous. \
    a. Reviewer 4Q1q - "Their analysis is thorough.", "Experiments provided to support each theorem also look thorough."\
    b. Reviewer 4cXR - "The problem the paper investigates and the perspective the paper takes is quite interesting.", " presents several results that improve one's understanding of double descent."\
    c. Reviewer RQj2 - "The work seems rigorous and the contributions relevant."\
    d. Reviewer SLpr - "The paper considers an original viewpoint on the problem of double-descent", "This result is significant"

We hope that our responses address the reviewers concerns. If there are concerns that have not been addressed or need further discussion please let us know.

Meta-review: The paper investigates the double descent phenomenon in linear regression. Specifically, the authors present two examples of double descent in the under-parameterized regime. The reviewers appreciated the contribution, found the paper well-written and clear, and liked how it positions itself with respect to previous work. Therefore, I recommend acceptance.
Decision: Accept (poster)