Least Squares Regression Can Exhibit Under-Parameterized Double Descent

Authors: xinyue  li
rishi  sonthalia
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 21:23:57

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.

Main paper: 
 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 of parameters for a fixed number of training data points is U-shaped (Figure 1a 1 ). 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 1b 2 ). This second descent has been termed as double descent and occurs in the over-parameterized regime, which is 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. Many different theories have been postulated for the appearance of the peak. The prevalent theory is that when the model is under-parameterized, the learning is constrained. This constraint on the 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] [5] [6] [7] [8] [9] [10] [11] [12] [13] and kernelized regression [14] [15] [16] [17] [18] [19] [20] [21] [22] . These works show that there exists a peak at the boundary between the under and 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 a 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 overparameterized regime and ignores the under-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-parameterized 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 underparameterized regime. • Modifying the Alignment. For the first example, we consider a spiked covariate model, where one eigendirection dominates, and the regression target only depends on the dominant eigendirection.For this model, we consider the ridge regularized problem with ridge parameter µ 2 and show that the ridge parameter µ 2 controls the alignment between the targets y and the singular vectors V . We show that for µ > 0 the peak occurs in the under-parameterized regime (Theorem 2). Specifically, when the ratio of the dimension to the number of training data points c is equal to (1 + µ 2 ) -1 (c := d/n = 1/(1 + µ 2 )). • Modifying the Spectrum For the second example, we consider training data that is a mixture of isotropic Gaussian vectors and vectors from along a fixed direction z. By varying the mixture proportions (π 1 , π 2 ), we can modify the spectrum of the covariance matrix. We show that the expected risk displays under-parameterized double descent (Theorem 4), with the peak occurring when c := d/n = π 1 ). • 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 µ, the risk curve does not display a 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 3 highlights two less-studied properties that influence the location of the peak. Section 4 presents the first of the two examples of underparameterized double descent. This model also shows that a double descent in the norm of the estimator does not translate to a double descent in the risk. Finally, Section 5 presents the second example of under-parameterized double descent. 
prior work on double descent: 
 In this section, we present the current prevailing theories for the occurrence of local maximums in the risk curve. Concretely, consider the following simple linear model that is a special case of the general models studied in [5, 8, 11, 23] amongst many other works. Let x i ∼ N (0, I d ) and let β ∈ R d be a linear model with ∥β∥ = 1. Let y i = β T x i + ξ i where ξ ∼ N (0, 1). Then, let β opt be the minimum norm solution to arg min β ∥β T X trn -βT X trn + ξ trn ∥, where ξ trn ∈ R n×1 . One important quantity is the aspect ratio of X. Specifically, for a d × n matrix, the aspect ratio is c := d/n. With this terminology, we see that a model is under-parameterized if c < 1 and over-parameterized when c > 1.Table 1 : Table showing various assumptions on 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, see Appendix F.1. The peak happens at c = 1, on the border between the under and over-parameterized regimes. 2. Further, at c = 1 the training error equals zero. Hence, this is the interpolation point. 3 . The peak occurs due to the expected norm of the estimator β opt blowing up near the interpolation point.This is further validated by works that study ridge regularized regression [23] [24] [25] [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 of regularization results in the magnitude of the peak in the generalization getting smaller until a 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 under-parameterized regime for the above model.Subsequently, works such as [10, 23, [28] [29] [30] [31] show that there can be multiple descents in the overparameterized 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 3 in [30] , show that the peaks only occur if the model is over-parameterized. Further Chen, Min, Belkin, and Karbasi [27] show that by considering a variety of product data distributions, any shaped risk curve can be observed in the over-parameterized 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.1. Regularization can reduce the effective dimensionality of the model and move the peak to the right into the over-parameterized regime [32] . 2. For random feature models, we see that the random initialization results in a second peak in the over-parameterized regime [30] . 3. Due to the data having a complex covariance structure, any shaped risk curve is possible in the over-parameterized regime [27] .Other works [33] [34] [35] [36] have considered the problem for other loss models and shown a variety of different risk curves can exist. Table 1 summarizes some of the prior work.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 [24] and Kausik, Srivastava, and Sonthalia [37] consider the unregularized problem and show that the peak occurs at 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 LocationIn 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 under-parameterized regime. We begin with definitions and notations. Throughout the paper, we assume that training data X = [x 1 . . . x n ] ∈ R d×n and y = [y 1 . . . , y n ] ∈ R k×n . We are interested in the standard ridge regularized least squares problem.min β ∥y -βT X∥ 2 F + µ 2 ∥ β∥ 2In the unregularized case, the minimum norm solution is given by βT = yX † , where X † is the Moore-Penrose Pseudoinverse of X. Prior work on linear models has shown that a double descent in the risk is due to a double descent in the norm of the estimator. Suppose X = U ΣV T is the SVD, β ∈ R d×1 , then using unitary invariance, we have that∥ β∥ 2 = rank(X) i=1 (yV ) 2 i σ 2 iwhere σ i is the ith singular value. Hence, this is controlled by 1. The alignment between y and V . Here V are the eigenvectors of the data gram matrix.2. The spectrum of the gram matrix X T X.Many prior works deal with the alignment in one of two ways. If y = β T X + ξ, with ξ having an isotropic distribution, then prior works either assume that β has an isotropic distribution [4, 5, 42] or they assume that X is isotropic Gaussian or that x i = Σ1/2 z i , where z i is from an isotropic Gaussian [23, 43] and Σ is a deterministic matrix. For example, if β has an isotropic distribution, taking the expectation with respect to β, ξ we get thatE β,ξ ∥ β∥ 2 = E[β 2 1 ]∥XX † ∥ 2 F + E[ξ 2 1 ] rank(X) i=1 1 σ 2 i .This quantity is then studied by looking at the distribution of the spectrum as d, n → ∞. Definition 1. Given a random matrix A, if λ 1 , . . . , λ k are its eigenvalues. Then the empirical spectral distribution (ESD) is the following sum of Dirac delta measureν k = 1 k k i=1 δ λiand the limiting spectral distribution ν is a measure such that ν k → ν weakly almost surely.In general, the limiting distribution ν c depends on the limiting aspect ratio (i.e., d/n → c). Definition 2. Given a measure ν c that is supported on the interval J ⊂ R, the Stieljtes transform ism νc (ζ) = E λ∼νc 1 λ -ζ , ζ ∈ C \ J.One common assumption is that the limiting distribution of the empirical spectral distribution is the Marchenko-Pastur distribution [44] . Other limiting distributions have been considered in [5, 45, 46] . For the Marchenko-Pastur distribution, it is known (see, for example, Lemma 5 in [24] ) thatm νc (0) = E λ∼νc 1 λ = c 1-cHence, the risk is governed by the value of the Stieljtes transform of the limiting spectrum at ζ = 0. In particular, for the above example, the location of the peak of the risk as a function of c depended on the location of the peak of c → m νc (0) =: G(c).Hence the risk depends on both the spectrum and the alignment between y and V . Thus, the peak occurs at c = 1 because of the following two conditions.Alignment of y and right singular vectors of X Assumption 1. If X = U ΣV T is the SVD, then yV is isotropic.Assumption 2. The function c → m νc (0) =: G(c) has a local maximum at c = 1.In this paper, we show that violating either one of the above two assumptions can move the peak from the interpolation point into the under-parameterized regime. 
if: 
 p > q, E λp-µ 2 λ 2 p = c 1+c+µ 2 c 2 √ (-1+c+µ 2 c) 2 +4µ 2 c -1 2 + o(1). 4. If p < q, E λq-µ 2 λ 2 q = 1+c+µ 2 c 2 √ (1-c+cµ 2 ) 2 +4c 2 µ 2 -1 2 + o(1).Proof. Notice that if λ is an eigenvalue of A (so unshifted).λ λ + µ 2 = 1 - µ 2 λ + µ 2 and λ (λ + µ 2 ) 2 = 1 λ + µ 2 - µ 2 (λ + µ 2 ) 2Then use Lemmas 7, and 8 to finish the proof.Bounding the Variance. Lemma 10. Let η n be a uniform measure on n numbers a 1 , . . . , a n such that η n → η weakly in probability. Then for any bounded continuous function f1 n n-1 i=1 f (a i ) → E x∼η [f (x)].Proof. Using weak convergence1 n n i=1 f (a i ) → E x∼η [f (x)].Then using the boundedness of f , we get,1 n n-1 i=1 f (a i ) - 1 n n i=1 f (a i ) = - 1 n f (a n ) → 0.Lemma 11. Let η n be a uniform measure on n numbers a 1 , . . . , a n such that η n → η weakly in probability. Let s be a uniformly random unit vector in R m independent of η n . Suppose n/m → ζ ∈ (0, 1]. Then for any bounded function f ,E s n i=1 s 2 i f (a i ) → ζE x∼η [f (x)]andE s   n i=1 s 2 i f (a i ) 2   -E s n i=1 s 2 i f (a i ) 2 → 0.Proof. The first limit comes directly from weak convergence.For the second, notice,n i=1 s 2 i f (a i ) 2 = n i=1 s 4 i f (a i ) 2 + i̸ =j s 2 i s 2 j f (a i )f (a j ) = n i=1 s 4 i f (a i ) 2 + n i=1 s 2 i f (a i ) j̸ =i s 2 j f (a j ).Taking the expectation with respect to s we get,E s   n i=1 s 2 i f (a i ) 2   = 1 m 2 + O(m) n i=1 f (a i ) 2 + 1 m 2 + O(m) n i=1 f (a i ) j̸ =i f (a j )Then using Lemma 10 for any fixed i, we have,1 m j̸ =i f (a j ) → ζE x∼η [f (x)].Thus, as n → ∞, we have,E s   n i=1 s 2 i f (a i ) 2   → ζ 2 E x∼η [f (x)] 2 .Then sinceE s n i=1 s 2 i f (a i ) 2 → ζ 2 E x∼η [f (x)] 2 .Thus, the variance goes to zero.The interpretation of the above Lemma is that the variance of the sum decays to zero as m → ∞. Lemma 12. Suppose A is an p by q matrix such that the entries of A are independent and have mean 0, variance 1/p, and bounded fourth moment.Let Â = [A µI] ∈ R p×q+p . Let x ∈ R p and ŷ ∈ R p+q be unit norm vectors such that ŷT = [y T 0 p ]. Then 1. If p < q, then E[Tr(x T ( Â ÂT ) † x] = √ (1-c+µ 2 c) 2 +4µ 2 c 2 -1-µ 2 c+c 2µ 2 c + o(1). 2. If p > q, then E[Tr(x T ( Â ÂT ) † x] = √ (-1+c+µ 2 c) 2 +4µ 2 c-1-µ 2 c+c 2µ 2 c + o(1). 3. If p < q, then E[Tr(ŷ T ( ÂT Â) † ŷ] = c 1+c+µ 2 c 2 √ (1-c+µ 2 c) 2 +4c 2 µ 2 -1 2 + o(1). 4. If p > q, then E[Tr(ŷ T ( ÂT Â) † ŷ] = c 1+c+µ 2 c 2 √ (-1+c+µ 2 c) 2 +4µ 2 c -1 2 + o(1). 
alignment mismatch: 
 In this section, we present the first example that exhibits double descent in the under-parameterized regime. This model violates Assumption 1.For any k ≤ d, let β ∈ R d×k be fixed such that the operator norm ||β T || is Θ(1). Let X trn ∈ R d×n be the signal matrix and A trn ∈ R d×n be the noise matrix. Then, the ridge regularized least square estimator W opt is the minimum norm solution toEQUATIONGiven test data X tst + A tst , the mean squared generalization error is given byEQUATIONAssumption 3. Let U ⊂ R d be a one dimensional space with a unit basis vector u. Then let X trn = σ trn uv T trn ∈ R d×n and X tst = σ tst uv T tst ∈ R d×ntst be the respective SVDs for the training data and test data matrices. We further assume thatσ trn = O( √ n) and σ tst = O( √ n tst ).There are no assumptions on the distribution of v trn , v tst besides having unit norm. First, we see that the data X + A has a spiked covariance, with the dominant eigendirection closely aligned with u. Since the targets only depend on X, we consider A to represent noise. Even with the rank 1 assumption, the model captures many different scenarios. If k = 1, then the problem is similar to error-in-variables regression. If k = d and β = I, then this is the supervised denoising problem. If the columns of X trn are all ±u and β = u, then this captures the binary classification problem (with MSE loss) for two Gaussian clusters centered at u and -u with labels ±1.Assumptions about A. The analysis works for general assumptions in [24] . For simplicity, we assume that the matrix A has I.I.D. entries drawn from a normalized Gaussian. Assumption 4. The entries of the matrices A ∈ R d×n are I.I.D. from N (0, 1/d).We begin by providing a formula for the generalization error given by Equation 2for the least squares solution given by Equation 1. All proofs are in Appendix E.Theorem 1 (Generalization Error Formula). Suppose the training data X trn and test data X tst satisfy Assumption 3 and the noise A trn , A tst satisfy Assumption 4. Let µ be the regularization parameter. Then for the under-parameterized regime (i.e., c < 1) for the solution W opt to Problem 1, the generalization error or risk given by Equation 2 is given byR(c, µ) = cσ 2 trn (σ 2 trn + 1)) 2dτ 2 1 + c + µ 2 c (1 -c + µ 2 c) 2 + 4µ 2 c 2 -τ -2 cσ 2 trn (σ 2 trn + 1)) 2d +τ -2 σ 2 tst n tst +o 1 d ,where1 τ = 2∥β T u∥ 2 + σ 2 trn (1 + c + µ 2 c -(1 -c + µ 2 c) + 4µ 2 c 2 ).Sketch. The proof proceeds in four key steps. First, we use the Sherman-Morrison formula for 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.Since the focus is on the under-parameterized regime, Theorem 1 only presents the underparameterized case. The over-parameterized case can be found in Appendix E.3. Due to the complexity of the expression, it is difficult to discern how the risk scales with respect to the training data signal strength σ 2 trn , the regularization strength µ, or the aspect ratio c. Since the focus of the paper is the scaling with respect to c, we present the connection between the risk curve and c in the main text. However, the shape of the risk curve with respect to the other parameters is also interesting and can be found in Appendix D.To understand the shape of the risk curve as c varies, we first consider that data scaling regime. That is, fix d and change n. The following theorem 2 shows that the risk curve is theoretically guaranteed to have a peak at c = 1 1+µ 2 . Theorem 2 (Under-Parameterized Peak). Let µ ∈ R >0 , σ 2 trn = n = d/c and σ 2 tst = n tst , and d is sufficiently large, so that the error term o(1/d) is small, then the risk R(c) from Theorem 1, as a function of c, has a local maximum in the under-parameterized regime at c = 1 1+µ 2 .Theorem 2 contrasts with prior works, in which double descent occurs in the over-parameterized regime or on the boundary between the two regimes. We numerically verify the predictions from Theorems 1 and 2. Figure 2 shows that the theoretically predicted risk matches the numerical risk, thus verifying that double descent occurs in the under-parameterized regime. We now show that the peak occurs due to a 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∥β T [X trn 0 d×d ] Xtrn -W ([X trn 0 d×d ] + [A trn µI] Âtrn ])∥ 2 F .In this expression, y = β T Xtrn = (β T u)[v T trn 0 p ]. Hence the direction is given by vT trn = [v T trn 0 p ]. The right singular vectors of Xtrn + Âtrn are more difficult to compute,thus we use proxies. Since Xtrn is rank 1, we use the right singular vectors of Âtrn as a proxy. Lemma 5 in the appendix, shows that if A = U ΣV T , then we can express Âtrn as Û Σ V T , where Û = U , Σ2 = Σ 2 + µ 2 I, andV = V 1:p Σ Σ-1 µU Σ-1 ∈ R n+d×d . Here V 1:d are the first d columns of V . Then, y V = (β T u)(v T trn V 1:d )Σ Σ-1 . Since V 1:d came from a Gaussian random matrix, (v T trn V 1:d) has isotropic entries. However, the diagonal matrix Σ Σ-1 results in the entries of y V not being isotropic. Note when µ = 0, Σ Σ-1 = I, hence it is isotropic. Hence, µ controls the deviation from isotropy.We use ΣT ΣI as a proxy for the spectrum of the sample covariance. By Lemma 5, we have that ΣT Σ = Σ T Σ+µ 2 . We know that the limiting spectrum for Σ T Σ is the Marchenko-Pastur distribution for which the map G(c) = m νc (0) has a maximum for c = 1. Shifting the spectrum changes the magnitude of the peak but does not change the location. This suggests that the peak occurs due to the misalignment between the target vector and the right singular vectors of the input data.Ablation experiment To verify that the location of the peak is due to the misalignment, we conduct two experiments. First, we solve the unregularized problem. However, we change the spectrum of the noise matrix A trn . That is, instead of using A trn = U ΣV T , we use Ã = U (Σ 2 + µ 2 I) 1/2 V T . If the spectrum was the primary factor determining the location of the peak, the peak should occur at c = 1/(1 + µ 2 ). However, as seen in Figure 3a it still occurs at c = 1. Second, we replace V with a uniformly random orthogonal matrix Q4 . Clearly, yQ is now isotropic. Figure 3b shows that, in this case, the peak moves to the over-parameterized regime. Generalization Risk = 1Figure 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-parameterized regime. Hence, this model goes against prior expectations, with the peak moving to the left into the under-parameterized regime. However, there might still be some connection between the training error 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 a weak connection with the third derivative of the training error.Prior double descent theories suggest that double descent occurs due to the norm of the estimator increasing and then decreasing. This is true for the above model where we fixed d and varied n. However, the connection breaks if 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 underparameterized double descent. However, as we increase µ, the risk curve becomes monotonic. Nevertheless, as shown in Figure 5 , for larger values of µ, there is still a peak in the curve for the norm of the estimator ∥W opt ∥ 2 F . Hence, the curve for the norm of the estimator exhibits underparameterized double descent even if the risk does not. This is further highlighted in Figure 6 . 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 a local maximum in theE ∥W opt ∥ 2 F curve for c < 1. Theorem 3 (∥W opt ∥ F Peak). If σ tst =√ n tst , σ trn = √ n and µ is such that p(µ) < 0, then for fixed n that is sufficiently large enough, we have that E [∥W opt ∥ F ] versus c = d/n curve has a local maximum in the under-parameterized regime at c = (µ 2 + 1) -1 .  
shifting local maximum for stieljtes 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 c → m νc (0) does not occur at c = 1. We show that the maximum can be chosen to be any value in (0, 1). We consider the following mixture model. Let π 1 , π 2 be mixture weights such that π 1 + π 2 = 1. Then, with probability π 1 , the data is sampled from N (0, 1 d I) and with probability π 2 , the data point is αz for fixed z ∈ R d and α ∼ N (0, 1). For this model, the uncentered covariance matrix is given by Then, the expected excess risk for a solution β compared to β isE[xx T ] = π 1 E x∼N (0, 1 d I) [xx T ] + π 2 E[α 2 zz T ] = π 1 d I + π 2 zz T .R = E[∥β T x -βT x∥ 2 |X] = E π 1 d ∥β T -βT ∥ 2 + π 2 ∥(β -β) T z∥ 2 |X . Let X trn = [A zv T ] ∈ R d×n, where the A ∈ R d×n-k with each column a data point sampled I.I.D. from N (0, 1 d I) and v ∈ R k is the vector with random coefficients in front of z. Let β ∈ R d be the target regressor function and let y T = β T X trn + ξ T trn , where ξ T trn has I.I.D. entries from a standard normal. Let β T opt = y T X T trn (X trn X T trn ) -1 be the minimum norm. Then, Theorem 4 shows that the peak occurs when d/n = c = π 1 < 1. To experimentally verify Theorem 4, we consider two cases, one where we enforce β ⊥ z and one where we do not. As seen in Figure 7 , Theorem 4 is accurate for both cases. This suggests that the β ⊥ z assumption seems to only be needed for simplifying the proof. = π1c π1-c c < π 1 π 1 π1 c-π1 + 1 -π1 c ∥β∥ 2 d -(β T z) 2 ∥z∥ 2 d c > π 1 .Theorem 4 is quite surprising as it shows that the only peak in the risk curve occurs in the underparameterized regime. One might assume that is 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 a regularizer and removes the peak altogether. Xu and Hsu [39] , also looks at a 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 k coordinates are non-zero).They again see a 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-parameterized 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-parameterized double descent. If we had only low-dimensional data, then the peak "should" move into the over-parameterized regime. This is because if the true dimensionality of the data is r < d. Then, one might think that the peak occurs when the number of training data points n equals r since that is the interpolation point 5 . We are in 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 in a one-dimensional space. Hence, it only affects the top eigenvalue. Since the Stieljtes 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 Stieljtes transform of the ESD at 0. We expect the above intuition to hold, even when replacing rank 1 with rank r for any fixed small r.Connection to Prior Double Descent Theory For this example, it is easy to show that there is a strong connection to prior double descent theory. Specifically, even though we cannot interpolate the data, the minimum training error will occur at c = π 1 . 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 [11] (which is the case when π 2 = 0), we see that the π 2 > 0 results in sifting the peak to π 1 and rescales the variance by π 1 . However, we also see an additional correction term in the overparameterized regime:1 - π 1 c - (β T z) 2 ∥z∥ 2 dHere we see that the term depends on the alignment between the target β and the spike direction z. 
conclusion: 
 This paper presents two simple models with double descent in the under-parameterized 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 on 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 under-parameterized regime. The first model shows that ridge regularization can create a misalignment between targets and singular vectors, leading to a peak at c = 1/(1 + µ 2 ). 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 = π 1 . These findings challenge several prevailing theories about double descent. They show that peaks need not occur at or beyond the interpolation threshold and that a peak in the estimator'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.  
safeguards: 
 Question: Does the paper describe 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)?Answer: [NA] Justification: This is a theoretical work Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a 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 is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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 a theoretical work Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This is a 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 a theoretical work Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: 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 F. 6 We verify the conjectured formula as well as the role of low dimensionality using MNIST data. Specifically, we project the data onto a r-dimensional subspace. We then add noise to the low-dimensional representation and then solve the denoising problem. The left two figures in Figure 8 show that the phenomenon exists for low-dimensional data. That is, we see that a peak occurs in the under-parameterized regime, and the location of the peak seems to occur at 1 µ 2 +1 . However, running the same experiment without projecting to a low-dimensional space (right figure) results in very different phenomena. We no longer see double descent at all. Hence we see that if a peak occurs, then its location does not depend on the dimension. However, the occurrence of the peak does depend on the dimension. Thus, we see that this complements the results in [38] . To show that under-parameterized peak occurs for 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 2 • 784 2 parameters. Let V be a random 10-dimensional subspace. We project our data onto V, add noise to the low dimensional representation, and train our network to remove this noise. We use full batch gradient descent with weight decay of 0.001 to train the model for 500 epochs with a learning rate of 2 × 10 -2 . We test it on the complete MNIST test data. Figure 9 shows the training error and generalization error as a function of the number of training data points. As seen in the figure, we have multiple peaks in the under-parameterized regime, and the peaks in the risk correspond to local minimums in the training error. Interestingly, the risk curve here exhibits 4 peaks! 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 in the under-parameterized regime, the mechanisms that create these peaks are likely to be different. As seen in the prior section, the peak occurs in the interior of the under-parameterized regime and not on the border between the under-parameterized and over-parameterized regimes. We have also seen that it does not necessarily occur whenever there is a peak in the norm of the estimator. The final postulate for where the peak occurs is that it occurs when we first hit zero training error.In this section, we explore the connection between the training error and the risk. Theorem 5 derives a formula for the training error in the under-parameterized regime. Theorem 5 (Training Error). Let τ be as in Theorem 1. The training error for c < 1 is given byE Atrn [∥X trn -W opt (X trn + A trn )∥ 2 F ] = τ -2 σ 2 trn (1 -c • T 1 ) + σ 4 trn T 2 + o(1),whereT 1 = µ 2 2 1 + c + µ 2 c (1 -c + µ 2 c) 2 + 4µ 2 c 2 -1 + 1 2 + 1 + µ 2 c -(1 -c + µ 2 c) 2 + 4c 2 µ 2 2c ,andT 2 = (µ 2 c + c -1 -(1 -c + µ 2 c) 2 + 4c 2 µ 2 ) 2 µ 2 c + c + 1 2 (1 -c + µ 2 c) 2 + 4c 2 µ 2 + 1 2 .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 to signal the location of the peak in the generalization error curve.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. For example, the peak could correspond to a local minimum of the training error, or it could correspond to a point where the training error or its derivatives suddenly change. The first, a local minimum, is easy to 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 10 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, it 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 of the peak.It has been seen in prior work that the amount of noise added to the input data can be viewed as a 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 is equivalent to the strength of the signal σ trn ) and the strength of the ridge regularizer µ. It is interesting to analyze the trade-off between the two regularizers and the generalization error. Optimal σ trn First, we fix µ and determine the optimal σ trn . Figure 11 displays the generalization error versus σ 2 trn curve. The figure shows that the error is initially large but then decreases until the optimal generalization error. The generalization error when using the optimal σ trn is also shown in Figure 11 . Here, unlike [23] , picking the optimal value of σ trn does not mitigate double descent. Proposition 1 (Optimal σ trn ). The optimal value of σ 2 trn for c < 1 is given byσ 2 trn = σ 2 tst d[2c(µ 2 + 1) 2 -2T (cµ 2 + c + 1) + 2(cµ 2 -2c + 1)] + Ntst(µ 2 c 2 + c 2 + 1 -T ) Ntst(c 3 (µ 2 + 1) 2 -T (µ 2 c 2 + c 2 -1) -2c 2 -1) .Additionally, it is interesting to determine how the optimal value of σ trn depends on both µ and c.Figure 12 shows that for small values of µ ∈ (0.1, 0.5), as c changes, there exists an (inverted) double descent curve for the optimal value of σ trn . However, for the data scaling regime, the minimum of this double descent curve does not 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 σ 2 trn ≈ dµ 2 . Thus, for higher values of ridge regularization, it is preferable to have higher-quality data.Optimal Value of µ We now explore the effect of fixing σ trn and then changing µ. Figure 13 , shows a U shaped curve for the generalization error versus µ, suggesting that there is an optimal value of µ, which should be used to minimize the generalization error. Next, we compute the optimal value of µ using grid search and plot it against c. Figure 14 shows double descent for the optimal value of µ for small values of σ trn . Thus, for low SNR data, we see a double descent, but we do not for high SNR data.Finally, for a given value of µ and c, we compute the optimal σ trn . We then compute the generalization error (when using the optimal σ trn ) and plot the generalization error versus µ curve. 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 σ trn are jointly computed using grid search for µ ∈ (0, 100] and σ trn / √ n ∈ (0, 10]. Figure 16 shows the results. Specifically, σ trn is at the highest possible value (so best quality data), and then the model regularizes purely using the ridge regularizer. This results in a monotonically decreasing generalization error curve. Thus, in the data scaling model, there is an implicit bias that favors one regularizer over the other. Specifically, the model's implicit bias is to use higher quality data while using ridge regularization to regularize the model appropriately. It is surprising that the two regularizers are not balanced. Figure 16 : Trade-off between the regularizers. The left column is the optimal σ trn , the central column is the optimal µ, and the right column is the generalization error for these parameter restrictions. Figure 17 : Trade-off between the regularizers. The left column is the optimal σ trn , the central column is the optimal µ, and the right column is the generalization error for these parameter restrictionsNext we look at the trade-off between σ trn 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.We begin by noting, β T = (β T opt X + ξ trn )X † trn . Thus, we have,∥β∥ 2 = Tr(β T β) = Tr(β T opt X trn X † trn (X † trn ) T X trn β opt ) + Tr(ξ trn X † trn (X † trn ) T ξ T trn ) + 2 Tr(β T opt X trn X † trn X † trn ) T ξ T trn .Taking the expectation, with respect to ξ trn , we see that the last term vanishes.Letting X trn = U X Σ X V T X . We see that using the rotational invariance of X, U X , V X are independent and uniformly random. Thus, s := β T opt U X is a uniformly random unit vector. Thus, we see,E Xtrn,ξtrn Tr(β T opt X trn X † trn (X † trn ) T X trn β opt ) = min(d,n) i=1 E[s 2 i ] = min 1, 1 cSimilarly, we see,E Xtrn,ξtrn ξ trn X † trn (X † trn ) T ξ T trn = min(d,n) i=1 E 1 σ i (X trn ) 2Multiplying and dividing by d, normalizes the singular values squared of X trn so that the limiting distribution is the Marchenko Pastur distribution with shape c. Thus, we can estimate using Lemma 5 from Sonthalia and Nadakuditi [24] to get,c 1-c + o(1) c < 1 1 c-1 + o(1) c > 1 .Finally, the cross-term has an expectation equal to zero. Thus,E Xtrn,ξtrn [∥β opt ∥ 2 ] = 1 + c 1-c c < 1 1 c + 1 c-1 c > 1Then we have,β T β opt = β T opt X trn X † trn β opt + ξ trn X † trn β optThe second term has an expectation equal to zero, and the first term is similar to before and has an expectation equal to min 1, 1 c .Theorem 4 (Under-parametrized Peak). For the above model, if k/n → π 2 , and d/n → c, then the expected risk is given by R= π1c π1-c c < π 1 π 1 π1 c-π1 + 1 -π1 c ∥β∥ 2 d -(β T z) 2 ∥z∥ 2 d c > π 1 .Proof. We begin with c < π 1 . Here, since AA T is invertible, we can see thatβT = β T A zv T + ξ T A T vz T AA T + ∥v∥ 2 zz T -1Let us focus on the term without the ξ. Using the Sherman Morrison formula and the orthogonality of β and z, we see thatβ T A zv T A T vz T AA T + ∥v∥ 2 zz T -1 = β TThus, we get thatβT = β T + ξ T A T vz T AA T + ∥v∥ 2 zz T -1For this model, the uncentered covariance matrix is given byE[xx T ] = π 1 E x∼N (0, 1 d I) [xx T ] + π 2 E[α 2 zz T ] = π 1 d I + π 2 zz T .Then, the expected excess risk for a solution β compared to β isR = E[∥β T x -βT x∥ 2 |X] = E π 1 d ∥β T -βT ∥ 2 + π 2 ∥(β -β) T z∥ 2 |X .The first term is given byE[∥β -βT ∥ 2 |X] = E ξ T A T vz T AA T + ∥v∥ 2 zz T -1 2 |XTaking the expectation over ξ, we get that the expected excess risk is given byTr A T vz T AA T + ∥v∥ 2 zz T -2 A zv T = Tr AA T + ∥v∥ 2 zz T -1Again, using the Sherman-Morrison formula, we get thatTr((AA T + ∥v∥zz T ) -1 ) = Tr((AA T ) -1 - ∥v|| 2 1 + ∥v|| 2 z T (AA T ) -1 z Tr z T (AA T ) -2 zSuppose ν is the limiting distribution of the empirical spectral distribution for the non-zero eigenvalues. Then using the concentration results from [24] , we see that the error can be expressedTr((AA T ) -1 - ∥v|| 2 1 + ∥v|| 2 z T (AA T ) -1 z Tr z T (AA T ) -2 z = d•E λ∼ν 1 λ - ∥v∥ 2 1 + ∥v∥ 2 E λ∼ν 1 λ E λ∼ν 1 λ 2The second term of the expected risk isEQUATIONAgain, if we take the expectation over ξ and write as a trace, we getTr(z T (AA T ) -1 - (AA T ) -1 ∥v∥ 2 zz T (AA T ) -1 1 + ∥v∥ 2 z T (AA T ) -1 z z) = z T (AA T ) -1 z 1 + ∥v∥ 2 z T (AA T ) -1 zAgain, this can expressed asE λ∼ν 1 λ 1 + ∥v∥ 2 E λ∼ν 1 λPutting it all together, the expected excess risk isπ 1 E λ∼ν 1 λ + π 2 E λ∼ν 1 λ 1 + ∥v∥ 2 E λ∼ν 1 λ - π 1 d ∥v∥ 2 1 + ∥v∥ 2 E λ∼ν 1 λ E λ∼ν 1 λ 2If we then send n, k, d to infinity, while noting that ∥v∥ → ∞, then we get then limiting riskπ 1 E λ∼ν 1 λ = π 1 c π 1 -cFor the d > n -k case, AA T is no longer invertible. Hence, we need to replace the inverse with pseudoinverse. Hence, we have thatβT = β T A zv T + ξ T A T vz T AA T + ∥v∥ 2 zz T †We now expand the pseudoinverse using Theorem 1 from [47] . To write is succinctly, let M = AA T , P = (I -M M † ), γ = z T P z, and τ = z T M † z to get that(AA T + ∥v∥ 2 zz T ) † = (AA T ) † - 1 γ (AA T ) † zz T P + P zz T (AA T ) † + (1 + ∥v∥ 2 )τ ∥v∥ 2 γ 2 P zz T PNote that P is the projection onto the orthogonal complement of the range of A. Hence we see that M P = M † P = 0. Thus, multiplying through, and setting terms to zero, we see that(M + ∥v∥ 2 zz T )(M + ∥v∥ 2 zz T ) † = M M † - 1 γ M M † zz T P + ∥v∥ 2 zz T M † - 1 γ ∥v∥ 2 zz T M † zz T P - 1 γ ∥v∥ 2 zz T P zz T M † + (1 + ∥v∥ 2 τ ) γ 2 zz T P zz T PUsing the fact that z T P z = γ, z T M † z = τ and cancelling, we get(M + ∥v∥ 2 zz T )(M + ∥v∥ 2 zz T ) † = M M † - 1 γ M M † zz T P - 1 γ ∥v∥ 2 zz T M † zz T P + (1 + ∥v∥ 2 τ ) γ zz T P = M M † - 1 γ M M † zz T P - 1 γ ∥v∥ 2 zτ z T P + (1 + ∥v∥ 2 τ ) γ zz T P = M M † - 1 γ M M † zz T P + 1 γ zz T P = M M † + I -M M † 1 γ zz T P = M M † + 1 γ P zz T PThus, the first two terms in the error areπ 1 d ∥β -β∥ 2 + π 2 ∥β T z -βT z∥ 2Let us look at the second term first. Here we see thatβT z = β T M M † + 1 γ P zz T P z = β T (M M † z + P z)Thus, we see thatβ T z -βT z = β T z -β T (M M † z + P z) = β T (I -M M † )z -β T (I -M M † )z = 0For the first term, we first note thatβ T -βT = β T -β T M M † + 1 γ P zz T P = β T P - 1 γ β T P zz T PTo compute the norm, we expand and getβ T P 2 + 1 γ 2 Tr β T P zz T P P zz T P β - 2 γTr β T P zz T P P βNoting that P is a projection matrix, so P P = P and using z T P Z = γ, we get that this term simplifies toβ T P 2 - 1 γ Tr β T P zz T P βNote that the subspace for P comes from a Gaussian random matrix. Hence is uniformly random. HenceE β T P 2 = 1 - n -k d ∥β∥ 2 = 1 - π 1 c ∥β∥ 2Similarly, E -1 γ Tr β T P zz T P β = 1 - π 1 c (β T z) 2 ∥z∥ 2For the next two terms, we need to first simplifyA T vz T (AA T + ∥v∥ 2 zz T ) †Substituting in our formulas and noticing thatA T P = 0 and A T M † = A †we get thatA T vz T (AA T + ∥v∥ 2 zz T ) † = A † -1 γ A † zz T P -0 + 0 vz T M † -1 γ τ vz T P -vz T M † + 1+∥v∥ 2 τ ) ∥v∥ 2 γ vz T P = A † -1 γ A † zz T P -1 γ τ vz T P + 1 γ τ vz T P + 1 ∥v∥ 2 γ vz T P = A † -1 γ A † zz T P 1 ∥v∥ 2 γ vz T PThen we have thatE ξ T A T vz T (AA T + ∥v∥ 2 zz T ) † 2 = A T vz T (AA T + ∥v∥ 2 zz T ) † 2 = Tr   A † -1 γ A † zz T P 1 ∥v∥ 2 γ vz T P T A † -1 γ A † zz T P 1 ∥v∥ 2 γ vz T P   = Tr M † - 1 γ m † zz T P - 1 γ P zz t M † + 1 + ∥v∥ 2 τ ∥v∥ 2 γ 2 P zz T P = Tr M † -Tr 1 γ M † zz T P -Tr 1 γ P zz T M † + Tr 1 + ∥v∥ 2 τ ∥v∥ 2 γ 2 P zz T PUsing the cycling invariance of the trace and the fact that M † P = 0, we get thatE ξ T A T vz T (AA T + ∥v∥ 2 zz T ) † 2 = Tr M † + 1 + ∥v∥ 2 τ ∥v∥ 2 γThe last equality is obtained using cyclic invariance, the fact that P 2 = P , and γ = z T P z. Using Lemma 6 for p = n -k and q = d, we get that asymptotically,π 1 d Tr(M † ) = π 2 1 c -π 1 .Note that we similarly get that asymptotically,π 1 d τ = 1 d π 2 1 c -π 1 → 0.Thus, the contribution to the risk from this term is π 2 1 c-π1 . Finally, for the last term, we have thatA T vz T (AA T + ∥v∥ 2 zz T ) † z = A † z -1 γ A † zz T P z 1 ∥v∥ 2 γ vz T P z = 0 v ∥v∥ 2Thus,E ξ T A T vz T (AA T + ∥v∥ 2 zz T ) † z 2 = 1 ∥v∥ 2Note that ∥v∥ 2 ≈ k and hence this term is aympotitcally zero. Putting it all together, we get the needed result.The proof structure closely follows that of [24] .First, we decompose the error. Since we are not in the supervised learning setup, we do not have standard definitions of bias/variance. However, we will call the following terms the bias/variance of the model. First, we recall the following from [24] . Lemma 1 (Sonthalia and Nadakuditi [24] ). If A tst has mean 0 entries and A tst is independent of X tst and W , then EQUATION-W Y trn ∥ 2 F + µ 2 ∥W ∥ 2 F is equivalent to solving arg min W ∥ Xtrn -W Ŷtrn ∥ 2 F . Thus, W opt = arg min W ∥ Xtrn -W Ŷtrn ∥ 2 F = Xtrn Ŷ † trn .Expanding this out, we get the following formula for Ŵ . Let û be the left singular vector and vtrn be the right singular vectors of Xtrn . Note that the left singular does not change after ridge regularization, so û = u. Let ĥ = vTtrn Â † trn , k = Â † trn u, ŝ = (I -Âtrn Â † trn )u, t = vtrn (I -Â † trn Âtrn ), γ = 1 + σ trn vT trn Â † trn u, τ = σ 2 trn ∥ t∥ 2 ∥ k∥ 2 + γ2 . Proposition 2. If γ ̸ = 0 and A trn has full rank then W opt = σ trn γ τ u ĥ + σ 2 trn ∥ t∥ 2 τ u kT Â † trn .Proof. Here we know that u is arbitrary. We have that Âtrn has full rank. Thus, the rank of Âtrn is d, and the range of Âtrn is the whole space. Thus, u lives in the range of Âtrn . In this case, we want Theorem 3 from [47] . We definep = - σ 2 trn ∥ k∥ 2 γ tT -σ trn k and qT = - σ trn ∥ t∥ 2 γkT Â † trn -ĥ.Then we have,( Âtrn + σ trn uv T trn ) † = Â † trn + σ trn γ tT kT Â † trn - γ τ pq T .Note that, by our assumptions, we have t = vtrn (I -Â † trn Âtrn ), and (I -Â † trn Âtrn ) is a projection matrix, thus To compute W opt = Xtrn ( Xtrn + Âtrn ) † = σ trn uv T trn ( Âtrn + σ trn uv T trn ) † , using γ -1 = σ trn vT trn Â † trn u = σ trn ĥu, we multiply this through.σ trn uv T trn ( Âtrn + σ trn uv T trn ) † = σ trn uv T trn ( Â † trn + σ trn γ tT kT Â † trn - γ τ pq T ) = σ trn u ĥ + σ 2 trn ∥ t∥ 2 γ u kT Â † trn + σ trn γ τ uv T trn σ 2 trn ∥ k∥ 2 γ tT + σ trn k qT = σ trn u ĥ + σ 2 trn ∥ t∥ 2 γ u kT Â † trn + σ 3 trn ∥ k∥ 2 ∥ t∥ 2 τ uq T + σ trn γ(γ -1) τ uq T .Then we have,σ 3 trn ∥ k∥ 2 ∥ t∥ 2 τ uq T = σ 3 trn ∥ k∥ 2 ∥ t∥ 2 τ u - σ trn ∥ t∥ 2 γ kT Â † trn -ĥ = - σ 4 trn ∥ k∥ 2 ∥ t∥ 4 τ γ u kT Â † trn - σ 3 trn ∥ k∥ 2 ∥ t∥ 2 τ u ĥ and σ trn γ(γ -1) τ uq T = σ trn γ(γ -1) τ u - σ trn ∥ t∥ 2 γ kT Â † trn -ĥ = - σ 2 trn ∥ t∥ 2 (γ -1) τ u kT Â † trn - σ trn γ(γ -1) τ u ĥ.Substituting back in and collecting like terms, we get,σ trn uv T trn ( Âtrn + σ trn uv T trn ) † = σ trn 1 - σ 2 trn ∥ k∥ 2 ∥ t∥ 2 τ - γ(γ -1) τ u ĥ+ σ 2 trn ∥ t∥ 2 γ - σ 2 trn ∥ k∥ 2 ∥ t∥ 4 τ γ - ∥ t∥ 2 (γ -1) τ u kT Â † trn .We can then simplify the constants as follows.1 - σ 2 trn ∥ k∥ 2 ∥ t∥ 2 τ - γ(γ -1) τ = τ -σ 2 trn ∥ k∥ 2 ∥ t∥ 2 -γ 2 + γ τ = γ τ and ∥ t∥ 2 γ - σ 2 trn ∥ k∥ 2 ∥ t∥ 4 τ γ - ∥ t∥ 2 (γ -1) τ = ∥ t∥ 2 τ -σ 2 trn ∥ k∥ 2 ∥ t∥ 2 -γ2 + γ τ γ = ∥ t∥ 2 τ .This gives us the result.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 W opt is the solution to Equation 1, thenX tst -W opt X tst = γ τ X tst .Proof. To see this, note that we have n + M > M .X tst -W opt X tst = X tst - σ trn γ τ u ĥuv T tst - σ 2 trn ∥ t∥ 2 τ u kT Â † trn uv T tst = X tst - σtrn γ τ uv T trn Â † trn uv T tst - σ 2 trn ∥ t∥ 2 τ u kT Â † trn uv T tst .Note that γ = 1 + σ trn vT trn Â † trn u. Thus, we have that σ trn vT trn Â † trn u = γ -1. Substituting this into the second term, we get,X tst -W opt X tst = X tst - γ(γ -1) τ uv T tst - σ 2 trn ∥ t∥ 2 τ u kT Â † trn uv T tst .For the third term, since k = Â † trn u, kT Â † trn u = kT k = ∥ k∥ 2 . Substituting this into the expression, we get thatX tst -W opt X tst = X tst - γ(γ -1) τ uv T tst - σ 2 trn ∥ t∥ 2 ∥ k∥ 2 τ uv T tst .Since X tst = uv T tst , we get,X tst -W opt X tst = X tst 1 - γ(γ -1) τ - σ 2 trn ∥ t∥ 2 ∥ k∥ 2 τ .Simplify the constants using τ = σ 2 trn ∥ t∥ 2 ∥ k∥ 2 + γ2 , we get,τ + γ -γ2 -σ 2 trn ∥ t∥ 2 ∥ k∥ 2 τ = γ τ .Lemma 3 (Sonthalia and Nadakuditi [24] ). If the entries of A tst are independent with mean 0, and variance 1/d, then we have thatE Atst [∥W opt A tst ∥ 2 ] = Ntst d ∥W opt ∥ 2 . Lemma 4.If γ ̸ = 0 and A trn has full rank, then we have that∥W opt ∥ 2 F = σ 2 trn γ2 τ 2 Tr( ĥT ĥ) + 2 σ 3 trn ∥ t∥ 2 γ τ 2 Tr( ĥT kT Â † trn ) + σ 4 trn ∥ t∥ 4 τ 2 Tr(( Â † trn ) T kk T Â † trn ) ρ .Proof. We have∥W opt ∥ 2 F = Tr(W T opt W opt ) = Tr σ trn γ τ u ĥ + σ 2 trn ∥ t∥ 2 τ u kT Â † trn T σ trn γ τ u ĥ + σ 2 trn ∥ t∥ 2 τ u kT Â † trn = σ 2 trn γ2 τ 2 Tr( ĥT u T u ĥ) + 2 σ 3 trn ∥ t∥ 2 γ τ 2 Tr( ĥT u T u kT Â † trn ) + σ 4 trn ∥ t∥ 4 τ 2 Tr(( Â † trn ) T ku T u kT Â † trn ) = σ 2 trn γ2 τ 2 Tr( ĥT ĥ) + 2 σ 3 trn ∥ t∥ 2 γ τ 2 Tr( ĥT kT Â † trn ) + σ 4 trn ∥ t∥ 4 τ 2 Tr(( Â † trn ) T kk T Â † trn ).Where the last inequality is true due to the fact that ∥u∥ 2 = 1.Step 4: Estimate With Random Matrix Theory Lemma 5. Let A be a p × q matrix and let Â = [A µI] ∈ R p×q+p . Suppose A = U ΣV T be the singular value decomposition of A. If Â = Û Σ V T is the singular value decomposition of Â, then Û = U and if p < qΣ =      σ 1 (A) 2 + µ 2 0 • • • 0 0 σ 2 (A) 2 + µ 2 0 . . . . . . . . . 0 0 • • • σ p (A) 2 + µ 2      ∈ R p×p , and V = V 1:p Σ Σ-1 µU Σ-1 ∈ R q+p×p . Here V 1:p are the first p columns of V .Proof. Since p < q, we have that U ∈ R p×p , Σ ∈ R p×p are invertible. Here also consider the form of the SVD in which V T ∈ R p×q .We start by nothing that Û Σ2 Û T = Â ÂT = AA T +µ 2 I = U (Σ 2 +µ 2 I p )U T . Thus, we immediately see that σ i ( Â) 2 = σ i (A) 2 + µ 2 and that Û = U . Finally, we see,V T = Σ-1 U T Â = Σ-1 ΣV T 1:p µ Σ-1 U T Lemma 6. Let A be a p × q matrix and let Â = [A µI] ∈ R p×q+p . Suppose A = U ΣV T be the singular value decomposition of A. If Â = Û Σ V T is the singular value decomposition of Â, then Û = U and if p > q Σ =             σ 1 (A) 2 + µ 2 0 • • • 0 • • • 0 0 σ 2 (A) 2 + µ 2 0 . . . . . . . . . . . . 0 0 • • • σ q (A) 2 + µ 2 0 µ . . . . . . 0 0 0 • • • 0 • • • 0 µ             ∈ R p×p .Here we will denote the upper left q × q block by C. Further,V = V Σ T 1:q,1:q C -1 0 µU 1:q C -1 U q+1:p ∈ R q+p×p .Proof. Since p > q, we have that U ∈ R p×p and we have that Σ ∈ R p×q . Here V T ∈ R q×q is invertible.We start with nothing,EQUATION1:q,1:q 0 0 0 q-p + µ 2 I q U T .Thus, we immediately see that for i = 1, . . . , p σ i ( Â) 2 = σ i (A) 2 + µ 2 and for i = p + 1, . . . , q, we have that σ i ( Â) 2 = µ 2 and that Û = U .Then, we see,V T = Σ-1 U T Â = Σ-1 ΣV T µ Σ-1 U T .Note that Σ has 0 for the last p -q entries. Thus,EQUATIONSimilarly, due to the structure of Σ, we see,µ Σ-1 U T = [µC -1 U T 1:q µ 1 µ U T q+1:p ].Lemma 7. Suppose A is an p by q matrix such that p < q, the entries of A are independent and have mean 0, variance 1/p, and bounded fourth moment. Let c = p/q. Let Â = [A µI] ∈ R p×q+p . Let W p = Â ÂT and let W q = ÂT Â. Suppose λ p is a random non-zero eigenvalue from the largest p eigenvalues of W p , and λ q is a random non-zero eigenvalue of W q . Then 1.E 1 λp = E 1 λq = √ (1+µ 2 c-c) 2 +4µ 2 c 2 -1-µ 2 c+c 2µ 2 c+ o(1).2. E 1λ 2 p = E 1 λ 2 q = µ 2 c 2 +c 2 +µ 2 c-2c+1 2µ 4 c √ 4µ 2 c 2 +(1-c+µ 2 c) 2 + 1 2µ 4 1 -1 c + o(1).Proof. First, we note that the non-zero eigenvalues of W p and W q are the same. Hence we focus on W p . W p is nearly a Wishart matrix but is not normalized by the correct value. However, cW p does have the correct normalization.Due to the assumptions on A, we have that the eigenvalues of cAA T converge to the Marchenko-Pastur. Hence since the eigenvalues of cW p are(cλ p ) i = cσ i (A) 2 + cµ 2 ,we can estimate them by estimating cσ i (A) 2 with the Marchenko-Pastur [44, [50] [51] [52] [53] . In particular, we want the expectation of the inverse. We need to use the Stieljes transform. We know that if m c (z) is the Stieljes transform for the Marchenko-Pastur with shape parameter c, then if λ is sampled from the Marchenko-Pastur distribution, thenm c (z) = E λ 1 λ -z .Thus, we have that the expected inverse of the eigenvalue can be approximated m(-cµ 2 ). We know that the Steiljes transform:EQUATIONThus, we have,E 1 cλ p = m(-cµ 2 ) = (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c 2 .Canceling 1/c from both sides, we get,E 1 λ p = (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c .Then for the estimate of E 1/λ 2 p , we need to compute the derivative of the m c (z) and evaluate it at -cµ 2 . Hence, we see,m ′ c (z) = (c -z + -4cz + (1 -c -z) 2 -1)(c + z + -4cz + (1 -c -z) 2 -1) 4cz 2 -4cz + (1 -c -z) 2 .Thus,E 1 c 2 λ 2 p = m ′ c (-cµ 2 ) = (c + µ 2 c + 4µ 2 c 2 + (1 -c + µ 2 c) 2 -1)(c -µ 2 c + 4µ 2 c 2 + (1 -c + µ 2 c) 2 -1) 4µ 4 c 3 4µ 2 c 2 + (1 -c + µ 2 c) 2 .Canceling the 1/c 2 from both sides, we get,E 1 λ 2 p = (c + µ 2 c + 4µ 2 c 2 + (1 -c + µ 2 c) 2 -1)(c -µ 2 c + 4µ 2 c 2 + (1 -c + µ 2 c) 2 -1) 4µ 4 c 4µ 2 c 2 + (1 -c + µ 2 c) 2 .Multiplying out and simplifyingE 1 λ 2 p = µ 2 c 2 + c 2 + µ 2 c -2c + 1 2µ 4 c 4µ 2 c 2 + (1 -c + µ 2 c) 2 + 1 2µ 4 1 - 1 c .Lemma 8. Suppose A is an p by q matrix such that p > q, the entries of A are independent and have mean 0, variance 1/p, and bounded fourth moment. Let c = p/q. Let Â = [A µI] ∈ R p×q+p . Let W p = Â ÂT and let W q = ÂT Â. Suppose λ p is a random non-zero eigenvalue of W p , and λ q is a random eigenvalue from the largest q eigenvalues of W q . Then 1.E 1 λq = E 1 λp = √ 4µ 2 c+(-1+c+µ 2 c) 2 -c-µ 2 c+1 2µ 2+ o(1).2. E 1λ 2 q = E 1 λ 2 p = 1-2c+c 2 +µ 2 c+µ 2 c 2 2µ 4 √ 4µ 2 c+(-1+c+µ 2 c) 2 + (1 -c) 1 2µ 4 + o(1).Proof. First, we note that the non-zero eigenvalues of W p and W q are the same. Hence we focus on W p . Due to the assumptions on A, we have that the eigenvalues of A T A converge to the Marchenko-Pastur with shape c -1 . Hence if λ p is one of the first q eigenvalues of W p , we see,E 1 λ p = m c -1 (µ 2 ) = (1 + µ 2 -1/c) 2 + 4µ 2 /c -1 -µ 2 + 1/c 2µ 2 /c .Then for the estimate of E 1/λ 2 p , we need to compute the derivative of the m c -1 (z) and evaluate it at -µ 2 . Hence, we see,E 1 λ 2 p = (1/c + µ 2 + 4µ 2 /c + (1 -1/c + µ 2 ) 2 -1)(1/c -µ 2 + 4µ 2 /c + (1 -1/c + µ 2 ) 2 -1) 4µ 4 /c 4µ 2 /c + (1 -1/c + µ 2 ) 2 = (1 + µ 2 c + c 4µ 2 /c + (1 -1/c + µ 2 ) 2 -c)(1 -µ 2 c + c 4µ 2 /c + (1 -1/c + µ 2 ) 2 -c) 4µ 4 c 4µ 2 /c + (1 -1/c + µ 2 ) 2 = (1 + µ 2 c + 4µ 2 c + (-1 + c + µ 2 c) 2 -c)(1 -µ 2 c + 4µ 2 c + (-1 + c + µ 2 c) 2 -c) 4µ 4 4µ 2 c + (-1 + c + µ 2 c) 2This can be further simplified to1 -2c + c 2 + µ 2 c + µ 2 c 2 2µ 4 4µ 2 c + (-1 + c + µ 2 c) 2 + (1 -c) 1 2µ 4 + o(1)We will also need to estimate some other terms. Lemma 9. Suppose A is an p by q matrix such that the entries of A are independent and have mean 0, variance 1/p, and bounded fourth moment. Let Â = [A µI] ∈ R p×q+p . Let W p = Â ÂT and let W q = ÂT Â. Suppose λ p , λ q are random non-zero eigenvalues of W p , W q from the largest min(p, q) eigenvalues of W p , W q . Then1. If p > q, E λp-µ 2 λp = c 1 2 + 1+µ 2 c- √ (-1+c+µ 2 c) 2 +4µ 2 c 2c + o(1). 2. If p < q, E λq-µ 2 λq = 1 2 + 1+µ 2 c- √ (1-c+µ 2 c) 2 +4c 2 µ 2 2c+ o(1).Proof. Let us start with p < q.Let Â = Û Σ V T , where Σ is p × p. Then we see,( Â ÂT ) † = Û Σ-2 Û T .Where Û is uniformly random. Thus similar to [24] , we can use Lemma 7 to get,E[Tr(x T ( Â ÂT ) † x] = (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c + o(1).On the other hand, for p > q, we have that only the first q eigenvalues have the expectation in Lemma 8 The other p -q are equal to 1 µ 2 . Thus, we see,E[Tr(x T ( Â ÂT ) † x] = 1 c 4µ 2 c + (-1 + c + µ 2 c) 2 -c -µ 2 c + 1 2µ 2 + o(1) + 1 - 1 c 1 µ 2 = 4µ 2 c + (-1 + c + µ 2 c) 2 + c -µ 2 c -1 2cµ 2 .Again let us first consider the case when p < q. Then we have,( ÂT Â) † = V Σ-2 V T = V 1:p Σ Σ-1 µU Σ-1 Σ-2 Σ-1 ΣV T 1:p µ Σ-1 U T .Since ŷ has zeros in the last p coordinates, we see,ŷT ( ÂT Â) † ŷ = y T V 1:p Σ Σ-4ΣV T 1:p y. Thus, we can use Lemma 9 to estimate this as,c 1 + c + µ 2 c 2 (1 -c + cµ 2 ) 2 + 4c 2 µ 2 - 1 2 + o(1).The extra factor of c comes from the sum of p coordinates of a uniformly unit vector in q dimensional space. And for p > q, we have that the estimate isc 1 + c + µ 2 c 2 (1 + µ 2 -1/c) 2 + 4µ 2 /c - 1 2 + o(1).For the variance term, use Lemma 11. For three of the cases, the limiting distribution is the Marchenko-Pastur distribution. For the other case, the limiting measure is a mixture of the Marchenko-Pastur and a dirac delta at 1/µ 2 .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 thatE Atrn ∥ ĥ∥ 2 =        c 1+c+µ 2 c 2 √ (1-c+µ 2 c) 2 +4µ 2 c 2 -1 2 + o(1) c < 1 c 1+c+µ 2 c 2 √ (-1+c+µ 2 c) 2 +4µ 2 c -1 2 + o(1) c > 1 and that V(∥ ĥ∥ 2 ) = o(1).Proof. Here we see that ∥ ĥ∥ 2 = Tr(v T trn ( ÂT trn Âtrn ) † vT trn ). Thus, using the Lemma 12 we get that if c < 1E[∥ ĥ∥ 2 ] = c 1 + c + µ 2 c 2 (1 -c + µ 2 c) 2 + 4µ 2 c 2 - 1 2 + o(1)and if c > 1E[∥ ĥ∥ 2 ] = c 1 + c + µ 2 c 2 (-1 + c + µ 2 c) 2 + 4µ 2 c - 1 2 + o(1).Lemma 14. We haveE Atrn ∥ k∥ 2 =    √ (1-c+µ 2 c) 2 +4µ 2 c 2 -1-µ 2 c+c 2µ 2 c + o(1) c < 1 √ (-1+c+µ 2 c) 2 +4µ 2 c-1-µ 2 c+c 2µ 2 c + o(1) c > 1 and that V(∥ k∥ 2 ) = o(1). Proof. Since k = Â † trn u, we have that ∥ k∥ 2 = Tr(u T ( Âtrn ÂT trn ) † u). According to the Lemma 12, if c < 1 E[∥ k∥ 2 ] = (1 -c + µ 2 c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c + o(1)and if c > 1E[∥ k∥ 2 ] = (-1 + c + µ 2 c) 2 + 4µ 2 c -1 -µ 2 c + c 2µ 2 c + o(1).Lemma 15. We have thatE Atrn ∥ t∥ 2 =    1 2 1 -c -µ 2 c + (1 -c + µ 2 c) 2 + 4c 2 µ 2 + o(1) c < 1 1 2 1 -c -µ 2 c + (-1 + c + µ 2 c) 2 + 4µ 2 c + o(1) c > 1and we have thatV(∥ t∥ 2 ) = o(1)Proof. Here we see that t = vtrn (I -Â † trn Âtrn ). Thus, we see that∥ t∥ 2 = ∥v trn ∥ 2 -vT trn Â † trn Âtrn vtrn = 1 -vT trn Â † trn Âtrn vtrn . If V ∈ R p+q×p+q , we have that Â † trn Âtrn = V I p 0 0 0 q V T .Then if p < q using Lemma 6 and the fact that the last p coordinates of vtrn are 0, we see thatvT trn Â † trn Âtrn vtrn = v T trn V 1:p Σ Σ-2 ΣV T 1:p v trn .Then using Lemma 9 to estimate the middle diagonal matrix, we get thatE[∥ t∥ 2 ] = 1 -c 1 2 + 1 + µ 2 c -(1 + µ 2 c -c) 2 + 4c 2 µ 2 2c = 1 2 1 -c -µ 2 c + (1 -c + µ 2 c) 2 + 4c 2 µ 2 + o(1).Similarly for c > 1, we have thatE[∥ t∥ 2 ] = 1 - 1 2 + c + µ 2 c -c (1 + µ 2 -1/c) 2 + 4µ 2 /c 2 + o(1) = 1 2 1 -c -µ 2 c + (-1 + c + µ 2 c) 2 + 4µ 2 c + o(1).The variance of Â † trn Âtrn is also o(1) using Lemma 11.Lemma 16. We have thatE Atrn [γ] = 1 and V(γ) = O(σ 2 trn /d).Proof. Noting that Â = U Σ V T , we have thatγ = 1 + σ trn vT trn Â † trn u = 1 + σ trn min(n,d) i=1 σ i ( Â) -1 âi b i .Here âT = vT trn V and b = U T u. U is a uniformly random rotation matrix that is independent of Σ and V . Thus, taking the expectation with respect to A trn , we get that the expectation is equal to zero.For the variance, let us first consider the case when c < 1. For this case, we have thatV = V 1:d Σ Σ-1 µU Σ-1 . Thus, letting a T = v T trn V 1:d , we get that γ = 1 + d i=1 σ i (A) σ 2 i (A) + µ 2 a i b i .Squaring and taking the expectation, we see thatE[γ 2 ] = 1 + σ 2 trn n E λ∼µc λ (λ + µ 2 ) 2 + o σ 2 trn n .Similarly for c > 1, we have thatE[γ 2 ] = 1 + σ 2 trn d E λ∼µc λ (λ + µ 2 ) 2 + o σ 2 trn d .Lemma 17. We have thatE Tr(( Â † trn ) T kk T Â † trn ) = E [ρ] =    µ 2 c 2 +c 2 +µ 2 c-2c+1 2µ 4 c √ 4µ 2 c 2 +(1-c+µ 2 c) 2 + 1 2µ 4 1 -1 c + o(1) c < 1 1-2c+c 2 +µ 2 c+µ 2 c 2 2µ 4 c √ 4µ 2 c+(-1+c+µ 2 c) 2 + 1 -1 c 1 2µ 4 + o(1) c > 1and that V(ρ) = o(1).Proof. Here we have thatρ = Tr( kT ( ÂT trn Âtrn ) † k) = Tr(u T ( Âtrn ÂT trn ) † ( Âtrn ÂT trn ) † u). We first notice that ( Âtrn ÂT trn ) † ( Âtrn ÂT trn ) † = Û T Σ2 Û .Thus using Lemmas 7 and 8, we see that if c < 1E[ρ] = µ 2 c 2 + c 2 + µ 2 c -2c + 1 2µ 4 c 4µ 2 c 2 + (1 -c + µ 2 c) 2 + 1 2µ 4 1 - 1 cand if c > 1E[ρ] = 1 c 1 -2c + c 2 + µ 2 c + µ 2 c 2 2µ 4 4µ 2 c + (-1 + c + µ 2 c) 2 + (1 -c) 1 2µ 4 + 1 - 1 c 1 µ 4 = 1 -2c + c 2 + µ 2 c + µ 2 c 2 2µ 4 c 4µ 2 c + (-1 + c + µ 2 c) 2 + 1 - 1 c 1 2µ 4 .The variance being o(1) comes from Lemma 11 again.Lemma 18. We have that E Atrn Tr( ĥT kT Â † trn ) = 0 and the variance is o(1).Proof. Letting Â = U Σ V T , we get that Tr( ĥT kT ÂT ) = u T U Σ-3 V T vT trn . Then again since U is uniformly random and independent of Σ and V , the expectation is equal to zero. The variance is computed similarly to Lemma 16.Step 5: Putting it together Lemma 19. We have thatE τ σ 2 trn =    1 σ 2 trn + 1 2 1 + µ 2 c + c -(1 -c + µ 2 c) 2 + 4µ 2 c 2 + o(1) c < 1 1 σ 2 trn + 1 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c + o(1) c > 1and that V(τ /σ 2 trn ) = o(1).Proof. Using the fact that all of the quantities concentrate, we can use the previous estimates. Specifically, we use that|E[XY ] -E[X]E[Y ]| ≤ V[X]V[Y ]. Thus, since our variances decay, we can use the product of the expectations. Further,|V[XY ]| = |V[X]V[Y ] + E[X] 2 V[Y ] + E[Y ] 2 V[X] -2E[X]E[Y ]Cov(X, Y ) + Cov(X 2 , Y 2 ) -Cov(X, Y ) 2 | ≤ |V[X]V[Y ] + E[X] 2 V[Y ] + E[Y ] 2 V[X]| + 2|E[X]E[Y ]| V[X]V[Y ] + |V[X]V[Y ]| + | V[X 2 ]V[Y 2 ]|.Thus, since the variances individually go to 0, we see that the variance of the product also goes to 0. Then using Lemma 15 and 14, we have that if c < 1E ∥ t∥ 2 ∥ k∥ 2 = 1 2 1 + µ 2 c + c -(1 -c + µ 2 c) 2 + 4µ 2 c 2 + o(1)and V(∥ t∥ 2 ∥ k∥ 2 ) = o(1). Then since|V[X + Y ]| ≤ |V[X] + V[Y ]| + 2 V[X]V[Y ]we have that using Lemma 16, that if c < 1E τ σ 2 trn = 1 σ 2 trn + 1 2 1 + µ 2 c + c -(1 -c + µ 2 c) 2 + 4µ 2 c 2 + o(1)and that that variance is o (1) .If c > 1 E τ σ 2 trn = 1 σ 2 trn + 1 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c + o(1).Lemma 20. We have thatE Atrn 1 σ 2 trn ∥ ĥ∥ 2 + ∥ t∥ 4 ρ =        c(1+σ -2 trn ) 2 µ 2 c+c+1 √ (1-c+µ 2 c) 2 +4µ 2 c 2 -1 + o(1) c < 1 c(1+σ -2 trn ) 2 µ 2 c+c+1 √ (-1+c+µ 2 c) 2 +4µ 2 c -1 + o(1) c > 1and that the variance is o(1).Proof. Similar to Lemma 19, we can multiply the expectations since the variances are small. For c < 1, simplifying, we get thatE Atrn 1 σ 2 trn ∥ ĥ∥ 2 + ∥ t∥ 4 ρ = c(1 + σ -2 trn ) 2 µ 2 c + c + 1 (1 -c + µ 2 c) 2 + 4µ 2 c 2 -1 + o(1)and if c > 1, we get thatE Atrn 1 σ 2 trn ∥ ĥ∥ 2 + ∥ t∥ 4 ρ = c(1 + σ -2 trn ) 2 µ 2 c + c + 1 (-1 + c + µ 2 c) 2 + 4µ 2 c -1 + o(1)and the variance decays since the variances decay individually.Lemma 21. We have thatE Atrn ∥W opt ∥ 2 F = σ 4 trn τ 2        c(1+σ -2 trn ) 2 µ 2 c+c+1 √ (1-c+µ 2 c) 2 +4µ 2 c 2 -1 + o(1) c < 1 c(1+σ -2 trn ) 2 µ 2 c+c+1 √ (-1+c+µ 2 c) 2 +4µ 2 c -1 + o(1) c > 1 and that V(∥W opt ∥ 2 F ) = o(1).Proof. Follows immediately from Lemmas 4, 17, 18, and 20.Theorem 1 (Generalization Error Formula). Suppose the training data X trn and test data X tst satisfy Assumption 3 and the noise A trn , A tst satisfy Assumption 4. Let µ be the regularization parameter. Then for the under-parameterized regime (i.e., c < 1) for the solution W opt to Problem 1, the generalization error or risk given by Equation 2 is given byR(c, µ) = cσ 2 trn (σ 2 trn + 1)) 2dτ 2 1 + c + µ 2 c (1 -c + µ 2 c) 2 + 4µ 2 c 2 -τ -2 cσ 2 trn (σ 2 trn + 1)) 2d +τ -2 σ 2 tst n tst +o 1 d , where 1 τ = 2∥β T u∥ 2 + σ 2 trn (1 + c + µ 2 c -(1 -c + µ 2 c) + 4µ 2 c 2 ).Proof. Rewriting Theorem 6. For the over-parameterized case, we have that the generalization error is given byR(c, µ) = τ -2 σ 2 tst N tst + cσ 2 trn (σ 2 trn + 1)) 2d 1 + c + µ 2 c (-1 + c + µ 2 c) 2 + 4µ 2 c -1 + o 1 d , where τ -1 = 2 2 + σ 2 trn (1 + c + µ 2 c -(-1 + c + µ 2 c) + 4µ 2 c) .Proof. Rewriting Proof. First, we compute the derivative of the risk. We do so using SymPy and get the following expression.4c 4cµ 2 + µ 2 -1 cµ 2 -c + 1 -µ 2 + 1 4c 2 µ 2 + (cµ 2 -c + 1) 2 d 4c 2 µ 2 + (cµ 2 -c + 1) 2 cµ 2 + c -4c 2 µ 2 + (cµ 2 -c + 1) 2 + 1 2 + 2c µ 2 + 1 4c 2 µ 2 + cµ 2 -c + 1 2 -4cµ 2 + µ 2 -1 cµ 2 -c + 1 cµ 2 + c + 1 d 4c 2 µ 2 + (cµ 2 -c + 1) 2 3 2 cµ 2 + c -4c 2 µ 2 + (cµ 2 -c + 1) 2 + 1 2 + 2 4c 2 µ 2 + cµ 2 -c + 1 2 3 cµ 2 + c -4c 2 µ 2 + (cµ 2 -c + 1) 2 + 1 6 M 4c 2 µ 2 + (cµ 2 -c + 1) 2 7 2 cµ 2 + c -4c 2 µ 2 + (cµ 2 -c + 1) 2 + 1 7We can then compute the limit as c → 0 + . Again using SymPy we see thatlim c→0 + ∂ ∂c R(c, µ 2 ; σ 2 trn = d/c) = 1 d > 0. Let T (c, µ) = c 2 µ 4 + 2c 2 µ 2 + c 2 + 2cµ 2 -2c + 1To find the critical point, we shall write the derivative as one fraction of the form d, T ) .∂ c R(c, µ) = -2 (cµ 2 + c -1)P (c, µ, d, T ) Q(c, µ,Here we see thatP (c, µ, d, T ) = c 2 µ 4 + 2c 2 µ 2 + c 2 + 2cµ 2 + 1 -(cµ + c + 1) √ T and Q(c, µ, d, T ) = d(cµ 2 + c + 1 - √ T ) 2 T 3/2We can see that the numerator is zero at c = (1 + µ 2 ) -1 . To evaluate the denominator at this point, we first get thatEQUATIONwhereT 1 = µ 2 2 1 + c + µ 2 c (1 -c + µ 2 c) 2 + 4µ 2 c 2 -1 + 1 2 + 1 + µ 2 c -(1 -c + µ 2 c) 2 + 4c 2 µ 2 2c ,andT 2 = (µ 2 c + c -1 -(1 -c + µ 2 c) 2 + 4c 2 µ 2 ) 2 µ 2 c + c + 1 2 (1 -c + µ 2 c) 2 + 4c 2 µ 2 + 1 2 .Proof. Note that we have:E Atrn ∥X trn -W opt Y trn ∥ 2 F n = 1 n E Atrn ∥X trn -W opt (X trn + A trn ))∥ 2 F = 1 n E[∥X trn -W opt X trn ∥ 2 ] + 1 n E[∥W opt A trn ∥ 2 ] + 2 n E Tr((X trn -W opt X trn ) T W opt A trn ) .First, by Lemma 2, we have X trn -W opt X trn = γ τ X trn . Then,E[∥X trn -W opt X trn ∥ 2 ] = γ2 τ 2 E[∥X trn ∥ 2 ] = γ2 σ 2 trn τ 2 . Then, let us look at the E Atrn [∥W opt A trn ∥ 2 F ] term. E Atrn [∥W opt A trn ∥ 2 F ] = E[Tr(A T trn W T opt W opt A trn )] = σ 2 trn γ2 τ 2 E[Tr(A T trn ĥT u T u ĥA trn )] + σ 3 trn γ∥ t∥ 2 τ 2 E[Tr(A T trn ĥT u T u kT Â † trn A trn )] + σ 3 trn β∥ t∥ 2 τ 2 E[Tr(A T trn ( Â † trn ) T ku T u ĥA trn )] + σ 4 trn ∥ t∥ 4 τ 2 E[Tr(A T trn ( Â † trn ) T ku T u kT Â † trn A trn )] = σ 2 trn γ2 τ 2 E[Tr( ĥA trn A T trn ĥT )] + σ 3 trn γ∥ t∥ 2 τ 2 E[Tr( kT Â † trn A trn A T trn ĥT )] + σ 3 trn γ∥ t∥ 2 τ 2 E[Tr( ĥA trn A T trn ( Â † trn ) T k)] + σ 4 trn ∥ t∥ 4 τ 2 E[Tr( kT Â † trn A trn A T trn ( Â † trn ) T k)] = σ 2 trn γ2 τ 2 E[Tr(v T trn Â † trn A trn A T trn ( Â † trn ) T vT trn )] + σ 3 trn γ∥ t∥ 2 τ 2 E[Tr(u T ( Â † trn ) T Â † trn A trn A T trn ( Â † trn ) T vT trn )] + σ 3 trn γ∥ t∥ 2 τ 2 E[Tr(v T trn Â † trn A trn A T trn ( Â † trn ) T Â † trn u)] + σ 4 trn ∥ t∥ 4 τ 2 E[Tr(u T ( Â † trn ) T Â † trn A trn A T trn ( Â † trn ) T Â † trn u)] = σ 2 trn γ2 τ 2 E[Tr(v T trn Â † trn A trn A T trn ( Â † trn ) T vT trn )] + σ 4 trn ∥ t∥ 4 τ 2 E[Tr(u T ( Â † trn ) T Â † trn A trn A T trn ( Â † trn ) T Â † trn u)].Then, we look at the Tr((X trn -W opt X trn ) T W opt A trn ) term. By Lemma 2, we have X trn -W opt X trn = γ τ X trn . Then, In conclusion, we have the training error:γE Atrn ∥X trn -W opt Y trn ∥ 2 F n = γ2 σ 2 trn nτ 2 + σ 2 trn γ2 nτ 2 E[Tr(v T trn Â † trn A trn A T trn ( Â † trn ) T vT trn )] + σ 4 trn ∥ t∥ 4 nτ 2 E[Tr(u T ( Â † trn ) T Â † trn A trn A T trn ( Â † trn ) T Â † trn u)] + 2 σ 2 trn γ2 nτ 2 E Tr vT trn Â † trn A trn v trn .Now we estimate the above terms using random matrix theory. Here we focus on the c < 1 case. For c < 1, we note thatÂ † trn A trn A T trn ( Â † trn ) T = V Σ-1 ΣΣ T Σ-1 V T . Thus, for c < 1 vT trn Â † trn A trn A T trn ( Â † trn ) T vtrn = d i=1 a 2 i σ i (A) 4 (σ i (A) 2 + µ 2 ) 2where a T = v T trn V 1:d . Taking the expectation, and using Lemma 9 we get thatE Atrn vT trn Â † trn A trn A T trn ( Â † trn ) T vtrn = c 1 2 + 1 + µ 2 c -(1 -c + µ 2 c) 2 + 4c 2 µ 2 2c + µ 2 1 + c + µ 2 c 2 (1 -c + cµ 2 ) 2 + 4c 2 µ 2 - 1 2 + o(1).Using Lemma 11, we see that the variance is o(1). Similarly, we have that( Â † trn ) T Â † trn A trn A T trn ( Â † trn ) T Â † trn = U Σ-2 ΣΣ T Σ-2 U T .Thus, again, using a similar argument, we see thatE Atrn Tr(u T ( Â † trn ) T Â † trn A trn A T trn ( Â † trn ) T Â † trn u) = 1 + c + µ 2 c 2 (1 -c + cµ 2 ) 2 + 4c 2 µ 2 - 1 2 + o(1)and again using Lemma 11, the variance is o(1). Finally,Â † trn A trn = V Σ-1 ΣV.Thus,Tr(v T trn Â † trn A trn v trn = d i=1 a 2 i σ i (A) 2 σ i (A) 2 + µ 2 .Thus, using Lemma 9, we get thatE Atrn Tr(v T trn Â † trn A trn v trn = 1 2 + 1 + µ 2 c -(1 -c + µ 2 c) 2 + 4c 2 µ 2 2c + o(1)and using Lemma 11, the variance is o(1). Then, similar to the proof of Theorem 1, we can simplify the above expression to get the final result.Proposition 1 (Optimal σ trn ). The optimal value of σ 2 trn for c < 1 is given byσ 2 trn = σ 2 tst d[2c(µ 2 + 1) 2 -2T (cµ 2 + c + 1) + 2(cµ 2 -2c + 1)] + Ntst(µ 2 c 2 + c 2 + 1 -T ) Ntst(c 3 (µ 2 + 1) 2 -T (µ 2 c 2 + c 2 -1) -2c 2 -1) .Proof. Let σ := σ 2 trn andF = τ -2 σ 2 tst N tst + 1 d (σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ) .Notice that only τ is a function of σ, ∥ ĥ∥ 2 2 , ∥ t∥ 2 2 , and ∥ k∥ 2 2 are all functions of µ. Then∂F ∂σ = τ -2 1 d (∥ ĥ∥ 2 2 + 2σ∥ t∥ 4 2 ρ) -2τ -3 ∂τ ∂σ σ 2 tst N tst + 1 d σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ = τ -2 1 d (∥ ĥ∥ 2 2 + 2σ∥ t∥ 4 2 ρ) -2τ -3 ∥ t∥ 2 2 ∥ k∥ 2 2 σ 2 tst N tst + 1 d (σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ) = τ -2 1 d (∥ ĥ∥ 2 2 + 2σ∥ t∥ 4 2 ρ) -2τ -1 ∥ t∥ 2 2 ∥ k∥ 2 2 σ 2 tst N tst + 1 d (σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ) .The optimal σ * satisfies ∂F ∂σ | σ=σ * = 0. Thus, we can solve the equationτ -2 = 0 or 1 d (∥ ĥ∥ 2 2 + 2σ∥ t∥ 4 2 ρ) -2τ -1 ∥ t∥ 2 2 ∥ k∥ 2 2 σ 2 tst N tst + 1 d (σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ) . Let α := ∥ t∥ 2 2 ∥ k∥ 2 2 , δ := d σ 2 tst Ntst . Then τ -2 = 0 =⇒ σ = - 1 ∥t∥ 2 2 ∥k∥ 2 2 .Notice that σ < 0 implies σ trn is an imaginary number, something we don't want. Thus, we look at the other expression.0 = 1 d (∥ ĥ∥ 2 2 + 2σ∥ t∥ 4 2 ρ) -2τ -1 ∥ t∥ 2 2 ∥k∥ 2 2 σ 2 tst N tst + 1 d (σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ) = 1 d (∥ ĥ∥ 2 2 + 2σ∥ t∥ 4 2 ρ) -2τ -1 α δ d + 1 d (σ∥ ĥ∥ 2 2 + σ 2 ∥ t∥ 4 2 ρ) . [α = ∥ t∥ 2 2 ∥ k∥ 2 2 ]1. We denote the minimum norm linear denoiser W opt by just W in this subsection. It is given byW opt = -U Σ trn H -1 1 K T Â † trn + U Σ trn H -1 1 Z T (QQ T ) -1 H 2.The test error when X tst = U L is given byE Âtrn 1 N tst ∥U Σ trn H -1 1 Z T (QQ T ) -1 Σ -1 trn L∥ 2 F + σ 2 tst d ∥W opt ∥ 2 F , where Q = V T (I -Â † trn Âtrn ), H = V T trn Â † trn ,1 K = -Â † trn U Σ trn , Z = I + V T trn Â † trn U Σ trn , H 1 = K T K + Z T (QQ T ) -1 Z. For c < 1, we have that if d < N then E[Σ -1 trn K T KΣ -1 trn ] = (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c + o(1) I r and if d > N then E[Σ -1 trn K T KΣ -1 trn ] = 4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c + o(1) I r . When d < N then E[Σ -1 trn K T Â † trn ( Â † trn ) T KΣ -1 trn ] = µ 2 c 2 + c 2 + µ 2 c -2c + 1 2µ 4 c 4µ 2 c 2 + (1 -c + µ 2 c) 2 I r + 1 2µ 4 1 - 1 c I r + o(1), if d > N then E[Σ -1 trn K T Â † trn ( Â † trn ) T KΣ -1 trn ] = 1 -2c + c 2 + µ 2 c + µ 2 c 2 2cµ 4 4µ 2 c + (-1 + c + µ 2 c) 2 I r + (1 - 1 c ) 1 2µ 4 I r + o(1).We have thatE[QQ T ] = c 1 2 + 1 + µ 2 c -(-1 + c + µ 2 c) 2 + 4µ 2 c 2c + o(1).andE[(QQ T ) -1 ] = 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c + o(1).When d < N we have thatE[HH T ] = c 1 + c + µ 2 c 2 (1 -c + µ 2 c) 2 + 4c 2 µ 2 - 1 2 I r + o(1)and when d > N , we haveE[HH T ] = c 1 + c + µ 2 c 2 (-1 + c + µ 2 c) 2 + 4µ 2 c - 1 2 I r + o(1). When d < N , we have E[∥W ∥ 2 F ] = µ 2 c 2 + c 2 + µ 2 c -2c + 1 2µ 4 c 4µ 2 c 2 + (1 -c + µ 2 c) 2 + 1 2µ 4 1 - 1 c Tr   (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c 2 c 1 + c + µ 2 c 2 (1 -c + µ 2 c) 2 + 4c 2 µ 2 - 1 2 Tr(Σ -2 ) Tr   (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + o(1), when d > N this is estimated by E[∥W ∥ 2 F ] = 1 -2c + c 2 + µ 2 c + µ 2 c 2 2cµ 4 4µ 2 c + (-1 + c + µ 2 c) 2 + (1 - 1 c ) 1 2µ 4 Tr   4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c 2 c 1 + c + µ 2 c 2 (-1 + c + µ 2 c) 2 + 4µ 2 c - 1 2 Tr(Σ -2 ) Tr   4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + o(1). When d < N the test error R(W, X tst ) for W = W opt is given by R(W, X tst ) = 1 N tst Tr(( 4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 ) -2 ) 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Tr(Σ -2 ) + σ 2 tst d µ 2 c 2 + c 2 + µ 2 c -2c + 1 2µ 4 c 4µ 2 c 2 + (1 -c + µ 2 c) 2 + 1 2µ 4 1 - 1 c Tr   (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + σ 2 tst d 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c 2 c 1 + c + µ 2 c 2 (1 -c + µ 2 c) 2 + 4c 2 µ 2 - 1 2 Tr(Σ -2 ) Tr   (1 + µ 2 c -c) 2 + 4µ 2 c 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + o(1), when d > N this is estimated by R(W, X tst ) = 1 N tst Tr(( 4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 ) -2 ) 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Tr(Σ -2 ) + σ 2 tst d 1 -2c + c 2 + µ 2 c + µ 2 c 2 2cµ 4 4µ 2 c + (-1 + c + µ 2 c) 2 + (1 - 1 c ) 1 2µ 4 Tr   4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + σ 2 tst d 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c 2 c 1 + c + µ 2 c 2 (-1 + c + µ 2 c) 2 + 4µ 2 c - 1 2 Tr(Σ -2 ) Tr   4µ 2 c + (-1 + c + µ 2 c) 2 -1 -µ 2 c + c 2µ 2 c I r + 2 1 + µ 2 c + c -(-1 + c + µ 2 c) 2 + 4µ 2 c Σ -2 -2   + o(1).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, N trn , N tst , d, σ trn , σ tst , and µ. For each trial, we sampled u, v trn , v tst uniformly at random from the appropriate dimensional sphere. We also sampled new training and test noise for each trial. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: This is a theoretical work that helps build an understanding of existing phenomena.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 or 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Image source[1]Image source[3]38th Conference on Neural Information Processing Systems (NeurIPS 2024).All code for the experiments can be found at https://github.com/rsonthal/Under-Parameterized-Double-DescentWe obtain such a matrix by computing the full SVD of a Gaussian random vector in PytorchAt least for 1-dimensional targetsWhile these are currently presented as a conjecture. This is because we only computed the expectation terms. Careful analysis of the variance would allow us to formalize the statement. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
questions: 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.



Does $\left\|W_{opt}\right\|_F$ in Line 240 indicate its expectation?



I recommend the authors to double check the overall text and equations. Here is a list of errata & typos.

Note that from the equation between Line 119 and Line 120, $\hat \beta\in\\mathbb{R}^{d\times k}$.

* Line 120: $\hat\beta = y X^\dagger$ -> $\hat \beta = \left(X^\dagger\right)^Ty^T$

* Displayed Equation between Lines 123-124: The denominator seems wrong. The following should be correct:

$$
\left\|\hat\beta\right\|^2 = \sum_{i=1}^{\mathrm{rank}\left(X\right)}\frac{\left(y V\right)_i^2}{\sigma_i^2}
$$

* 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$.

* Displayed equation between Lines 137-138: $z\in \mathbb{C}\setminus J$ -> $\zeta\in \mathbb{C}\setminus J$

* Lines 239-240: Is "for $n$ large enough and $d=cn$" a typo of "for $n$ and large enough $d=cn$"?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: 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: limitations: See above.
paper_summary: paper_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.
In 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.
Some numerical results are provided to support the theoretical analysis.
strength_weakness: strength_weakness: While this paper looks interesting, it is a bit hard for me to really understand the results and contribution.
I think making precise the dimension settings (relation between $n, d, n_{tst})$ will address this issue, see some of my detailed comments below.
Another 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.
questions: 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).
* it seems that the footnotes 3 and 4 are missing?
* 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$?
* 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?
* 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?
* 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. 
* 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)?
* line 207 -208: $\hat \Sigma^T \hat \Sigma = \Sigma^T \Sigma + \mu^2$ a typo here?

---
I thank the authors for their detailed reply, which helps me better understand their theoretical results and their contribution I increase my score accordingly. 

I, nonetheless, feel that there are a few typos that need be fixed and clarifications needed, in the current version of the paper.
limitations: limitations: I do not see any potential negative social impact of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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).
- 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?
questions: questions: - What do the authors exactly mean by input and output noise?
- In Table 1 (page 3), where are the footnotes related with numbers 3 and 4?
- In Figure 3, what ablation experiments do the authors refer to?
limitations: 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."
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 

- Table 1: What does 1/Low mean? The superscript 3 leads to nowhere.
- 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.
- 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.
- 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.
- 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?
- 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.
questions: 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: limitations: Yes

Comments: title: Reply
Score raised
comment: Thank you for the detailed response to the questions. It help me to understand this work more. I have been increased my score by 1.
Dear authors, thank you for your reply. It has nicely addressed my concerns. I have thus increased my score by 1.
Thank you to the authors for addressing my questions, they have helped me better understand the paper.
Dear reviewer, 

Thank you for the feedback and help in improving the paper. We also thank the reviewer for increasing their score.
We thank the reviewer again for their feedback and will incorporate the same.
Dear authors, 

I've read your responses to my comments, as well as your responses to all other reviewers' comments, and I've increased my score (moving from "6: Weak Accept" to "7: Accept"). I thank you for your detailed reply.

Best
I thank the authors for their detailed reply, which helps me better understand their theoretical results and their contribution
I increase my score accordingly.
I, nonetheless, feel that there are a few typos that need be fixed and clarifications needed, in the current version of the paper.