Provable More Data Hurt in High Dimensional Least Squares Estimator
Authors: Zeng Li
Chuanlong Xie
QINWEN WANG
Venue:  (2021)

Abstract: This paper investigates the finite-sample prediction risk of the high-dimensional least squares estimator. We derive the central limit theorem for the prediction risk when both the sample size and the number of features tend to infinity. Furthermore, the finite-sample distribution and the confidence interval of the prediction risk are provided. Our theoretical results demonstrate the sample-wise non-monotonicity of the prediction risk and confirm ''more data hurt'' phenomenon.

Under review as a conference paper at ICLR 2021
PROVABLE MORE DATA HURT IN HIGH DIMENSIONAL LEAST S SQUARES ESTIMATOR
Anonymous authors Paper under double-blind review
ABSTRACT
This paper investigates the finite-sample prediction risk of the high-dimensional least squares estimator. We derive the central limit theorem for the prediction risk when both the sample size and the number of features tend to infinity. Fur- thermore, the finite-sample distribution and the confidence interval of the predic- tion risk are provided. Our theoretical results demonstrate the sample-wise non- monotonicity of the prediction risk and confirm "more data hurt" phenomenon.
INTRODUCTION
More data hurt refers to the phenomenon that training on more data can hurt the prediction per- formance of the learned model, especially for some deep learning tasks. Loog et al. (2019) shows that various standard learners can lead to sample-wise non-monotonicity. Nakkiran et al. (2019) experimentally confirms the sample-wise non-monotonicity of the test accuracy on deep neural net- works. This challenges the conventional understanding in large sample properties: if an estimator is consistent, more data makes the estimator more stable and improves its saite performance. Nakkiran (2019) considers adding one single data point to a linear regression task and analyzes its marginal effect to the test risk. Dereziński al. (2019) gives exact con-asympootic risk of the high-dimensional least squares estimator and observes the sample-wise non-monotynicity on mean square error. For adversarially robust models, Min al. (2020) proves that more data may increase the gap between the generalization error of adversarially. trained models and standard models. Chen al.] (2020) shows that more training data causes the generalization error to increase in the strong adversary regime. In this work, we derive the finite-sample distribution of the prediction risk under linear models and prove the "more data hurt" phenomenon from an asymptotic point of view.
Intuitively, the "more data hurt" stems from the "double descent" risk curve: as the model com- plexity increases, the prediction risk of the learned model first decreases and then increases, and then decreases again. The double descent phenomenon can be precisely quantified for certain sim- ple models (Hastie et al. (2019): Mei & Montanari 2019); Ba et al. (2019); Belkin et al. (2019); Bartlett et al. (2020); Xing al. (2019)) Among these works, Hastie et al. (2019) and Mei & Mon- tanari (2019) use the tools from random matrix theory and explicitly prove the double descent curve of the asymptotic risk of linear regression and random features regression in high dimensional setup.
Ba et al. (2019) gives the asymptotic risk of two-layer neural networks when either the first or the second layer trained using gradient flow.
The second decline of the prediction risk in the double descent curve is highly related to the more data hurf phenomenon. In the wvee-parameterized regime when the model complexity is fixed while the sample size increases, the degree of perr-araaeeterizatonn decreases and becomes close to the interpolation boundary (for example p/n 1 in Hastie et al. (2019). in which a high prediction risk is achieved. However, the existing asymptotic results, which focus on the first-order limit of the fact, the "double descent"
prediction risk, cannot fully describe the more data hurt phenomenon. curve is a function of the limiting ratio lim p/n, which may not be able to characterize the empirical prediction risk in finite sample situations. There will be a non-negligible discrepancy between the empirical prediction risk and its limit, especially when the sample size dimension is small. Fine- grained second-order results are thus needed to fully characterize such discrepancy and further, a confidence band for the prediction risk can be constructed to evaluate its finite sample performance. We take Figure D as an example to illustrate this. According to the first-order limit, given a fixed dimension p- T00, the prediction risks at sample size n 90 and 98 are about 10.20 and

---

Under review as a conference paper at ICLR 2021
49.02. More data hurt seems true. However, the 95% confidence interval of the prediction risks with sample size 98 is [4.91, 142.12]. which contains the risk for n = 90. Then more data hurt is not statistically significant. Hence. in this work, we characterize the second-order fluctuations of the prediction risk and make attempts to fill this gap. We employ the linear regression task in Hastie et al. (2019) Nakkiran (2019), and introduce new tools from the random matrix theory, e-g. the central limit theorems for linear spectral statistics in Bai & Silverstein (2004); Bai et al. (2007). to derive the central limit theorem of the prediction risk.
Consider a linear regression task with n data points and features, the setup of the more data hurt similar to that in the classical asymptotic analysis in Van der Vaart (2000). According to the classical asymptotic analysis with fixed and n - oo, the least square estimator is unbiased and vn-connistentt to the ground truth. This implies that the more data will not hurt and even improve the prediction performance. However, the story is very different in the werr-parameterized regime. The prediction risk doesn't decrease monotonously with when p > n. More data does hurt in the werrpaarameterized case. In the following, we will justify this phenomenon by developing the second-order asymptotic results as both n and p tend to infinity. We assume p/n + c, and denote 0 n1 < n2 < +oc, C1 p/nz and C2 p/nz. Then the direct comparison of the prediction risk between sample sizes nı and f2 can be decomposed into three parts: (i) the gap between the finite- sample risk under n = n4 and the asymptotic risk with
C1; (ii) the gap between the finite-sample risk under π = n2 and the asymptotic risk with c = 02: (iii) the comparison between two asymptotic risks under c = Cj and c c2. Theorem and 2 of Hastie al. (2019) give answers to the task (iii). For (i) and (ii), we develop in this paper the convergence rate and the limiting distribution of the prediction risk as n, p + to0, p/n + c. Furthermore, the confidence interval of the sampee risk can be obtained as well.
Density
Confidence Interval
25.0
17.5
15.0
12.5
60
100
0.0
175
Sample Size
Sample Size
Figure 1: Sample-wise double descent. We take p = 100 and S n S 200. Left: The conditional
density of the prediction risk when sample size varies from 1 to 200. According to the conditional distribution of the prediction risk, we can observe the sample-wise double descent phenomenon. Right: The 95%--cnfidence band (point-wise) of the prediction risk. In the pee-pparameterized regime 1 S n < 100, there exists some pairs (nl n22), 1 S Mn < n2 < 100 such that the upper boundary of the confidence interval n is smaller than the lower boundary of the confidence interval at 122. This confirms the more data hurt phenomenon.
The main goal of this paper is to study the second order asymptotic behavior of two different types of conditional prediction risk in the linear regression model. One is Rx,a (3) given both the training data and regression coefficient while the other is Rx 3) given the training data only. We summarize our main results as follows: (1) The regression coefficient is set to be either random or nonrandom to cover more cases. Different convergence rates and limiting distributions of both prediction risk are derived under various scenarios. (2) In particular, the finite-sample distribution of the conditional prediction risk given both the training data and regression coefficient derived and the sample-win wise double descent is characterized in Theorem 4.2 and Theorem 4.5 (see Figure [. Under certain assumptions, the more data hurt phenomenon can be confirmed by comparing the confidence intervals built via the central limit theorems. (3) Our results incorporate non-Gause Gaussian observations. For Gaussian data, the limiting mean and variance in the central limit theorems have simpler forms, see Section 4.2 and for more details.
The rest of this paper is organized as follows. Section 3 introduces the model settings and two different prediction risk. Section 4 presents the main results CLT' for the types of risk with
2

---

Under review as a conference paper at ICLR 2021
conducts simulation experiments to verify the main results. All the technical proofs and lemmas are relegated to the appendix in the supplementary file.
discussion. Section 5
RELATED WORK
Double Descent The double descent curve describes how generalization ability changes as model capacity increases. It subsumes the classical -arrane trade-off, U-shape curve, and further show that the test error exhibits a second drop when the model capacity exceeds the interpolation threshold (Belkin et al. (2018); Geiger al. (2019); [Spigler al. (2019); Advani & Saxe (2017)) The double descent phenomenon has been quantified for certain models, including two-layer neural networks via non- con-asymptotic bounds or asymptotic risk (Belkin et al. (2019); MMtthukumrr et al. (2020); Hastie et al. 2: Mei & Montanari ): Ba et al. (2019). As our results are based on the linear regression, we mainly focus on the literature of linear models. Muthukumar et al. (2020) and Bartlett et al. (2020) derive the generalization bounds for over- weerparamettried linear models and show the benefits of the interpolation. Hastie et al.] (2019) gives the first-order limit of the gen- eralization error for linear regressions
n - +00. Dereziński et al. (2019) provides an exact non-asymptotic expression for double descent of the high-dimensional least square estimator. Wu & Xu (2220) extends the first-order limit of the prediction error of the generalized weighted ridge estimator to more general case with anisotropic features and signals. MMntanari et al. (2019), Deng et al. (019) and Kini & Thrampoulidis) (2020) investigate the sharp asymptotic of binary classifica- tion tasks with the max-margin solution and the maximum likelihood solution. |Emami et al. (2020) and Gerbelot et al. (2020a) consider the double descent in generalized linear models. Furthermore, the double descent phenomenon is also observed on linear tasks with various problems and assump-
tions, e.g. LeJeune et al. (2020); Gerbelot et al. (2020b); Javanmard et al. (2020); Daar & Baraniuk 2020);; Xu & Hsu (2019): : Dar et al. (2020). Xing et al. (2019) sharply quantifies the benefit of in- terpolation in the nearest neighbors algorithm. Mei & Montanari (2019) derives the limiting risk on the random features model and shows that minimum generalization error is achieved by highly over- parametrized interpolators. [Ba et al. (2019) gives the limiting risk of the regression problem under two-layer neural networks. However, the existing asymptotic results focus on the first-order limit of the prediction risk and do not indicate the convergence rate. There are very few second-order results in the literature, [hhnn& & Bellee (2020) establishes the asymptotic normality for the derivatives of 2-layers neural network, but not the exact limiting distribution of the risk. In this work, we are the first to develop results on second-order fluctuations of the prediction risk in linear regressions and provide its corresponding confidence intervals. The more data hurt phenomenon is further justified from the asymptotic point of view.
Random Matrix Theory The primary tool for analyzing the second-order fluctuations of prediction risk comes from random matrix theory. In particular, [Bai & Silverstein (2004) refines the central limit theorem for linear spectral statistics of large dimensional sample covariance matrix with gen- eral population and the population is not necessary to be Gaussian. Similar central limit theorems are also developed for other random matrix ensembles, see Sinai & Soshnikov (1998); Bai & Yao 2005); Zheng (2012). Other than the central limit theorem for linear spectral statistics, [Bai et al. 2007 and Pan & Zhou (2008) study the asymptotic fluctuation of eigenvectors of sample covari- ance matrices. Bai & Yao (2008) considers the fluctuation of quadratic forms. All these technical tools and results are adopted and fully utilized in this paper, especially those related to Stieltjes transform, which are closely connected to the prediction risk studied in this paper.
PRELIMINARIES
3.1 PROBLEM, DATA AND ESTIMATOR
Suppose that the training data { (x;, y,) E R. x RR, 1 = 1,2,...,n] is generated independently from the model (ground truth or teacher model):
y; = 3" x; + Es.
and (x,, (Px, P.), i= 1,
(1)
Here, Px is a distribution on R such that Exx,) = 0, Cov(x;) = Σ, and P. is a distribution on R such that B(()) 0, Var(e))
o². In particular, the coordinates of x; are not necessarily
3

---

Under review as a conference paper at ICLR 2021
independent, that is, E is not restricted be diagonal. To proceed further, denote
Xaxp (x1, ,,,..., x,)" y= (Y::)2......) ....)))
The minimum & norm (min-norm) least squares estimator, of y on X, is defined by
B = arg min ly - X,3| (X'X y'y,
(2)
where (X"X) denotes the Penoose pseudoinverse of X"X.
x)+
3.2 BIAS, VARIANCE AND RISK
Similar to Hastie al. 2019), we define two different types of out-of-sample prediction risk. The first one is given by
Rx -
(3)
where Xy Px a test point and is independent of the training data, and the notation || stands for Σ,3. Here B is assumed to be random vector independent of xo. In this definition, the expectation E stands for the conditional expectation for xu, , and / when X is given. According to the bias-variance decomposition,
have Rx (8, B3 (3, Vx (3,, B), where
Bx (x {
| 2 x
and (x = Tr Trr[Cov(BX>) X)E).
(4)
Plugging the model [I] into the min-norm estimator the bias and variance terms can be rewritten as
-
} and (x(3,3)= T)
n
where Σ - X'Xnn is the (uncentered) sample covariance matrix of X. and II = Ip Σ Σ is the projection onto the null space of X.
The second type of out-of-sample prediction risk is defined as
Rx.a(B 3) = - =
(5)
where
0² TT Σ).
Bx Bx,,( 13"TIE11 and Vx,,(3,33) 1- (x
In this definition, the parameter 3 is assumed to given. The expectation the conditional expectation for Xo and 3 when X and B are given. This is consistent with the commonly-used testing procedure, in which trained model is evaluated by the average loss unseen testing data.
4 MAIN RESULTS
Before stating our main results, we briefly highlight the challenges we faced in proving the more data hurt phenomenon. First, the finite-sample behaviors of the prediction risk is required. Hastic ct al. 2019) gives the first-order limits of both Rx,a(3, 3) and [x 3) as n,p - too and should fix p and
(0, +oo). However, to prove the more data hurt phenomenon, investigate the finite-sample risk with sample size n varies. This implies that only knowing the first- order limit is not enough, the convergence rate is also needed. To solve this problem, we have derived the central limit theorems for both Rx, (B, B) and (3, (),, respectively, which characterize the second-order fluctuations of the risk. Then we can figure out the finite-sample behavior of the risk by computing the gap between the risk and its limit. The confidence intervals of the risk can be further obtained. Second, the parameter B also contributes randomness to the finite-sample risk, which further influences the convergence rate. To analyze the contribution of 3,, we need to make of the technical tools and asymptotic results for cigenvectors and quadratic forms developed in Bai et al. (2007) and Bai & Yao (2008). Another interesting finding is that, in the parepparamtterized regime such that > n, the two types of out-of-sample prediction risk Rx (B. 3) and Rx (8, (3) enjoy different convergence rates.
p/n
4

---

Under review as a conference paper at ICLR 2021
4.1 ASSUMPTIONS AND MORE NOTATIONS
As follows are some notations used in this paper. The x p identity matrix is denoted by Ip. For symmetric matrix A E IRpx,, define its empirical spectral distribution
F (x) P 1=1
5 (()(A) S x}
where 1 {-} is the indicator function and (A), - 1,2,... ... are the cigenvalues of A. The notation
4 stands for the convergence distribution. Ze//2 the a upper quantile of the standard normal distribution, (A) and Amin (A) denote the largest and smallest eigenvalues of A, respectively.
Here we list all the assumptions for X and /3 needed under different scenarios:
(A) x, ~ Px of the form x, Σ1/22,, where 2j is a p-length random vector with i.i.d. entries that have zero mean, unit variance, and finite 4-th order moment B(z4)) 14.
1,... .P.j = -....... n..
(B1) E deterministic positive definite matrix, such that < co S Amin Σ C₁ for all n. p and some constants co. e₁. As co, we assume that the empirical spectral distribution p2 converges weakly to a probability measure H.
Amax
(B2) Σ is an identity matrix, Σ Ip-
(C1) G is nonrandom constant vector, and || = 3
(C2) 3 Pg independent of X and follows multivariate Gaussian distribution Ng r² Ip).
Throughout this paper, we consider the limiting distributions and the convergence rates of the out- of- sample prediction risk when n + oo such that p/n = Cn + & (0, oo). ). If >>>>> 1, the sample size is smaller than the number of parameters p. call this case "over-parametrizedd" Otherwise when e < I, we call it
4.2 UNDER- PEEEER-PPAMMRIZEEEE ASYMPTOTICS
In this section, we focus the risk of the min-norm estimator in the under- pander-prrmmetrized regime. According Theorem of Hastie et al. (0119). both (x,a(B3 3) and Bx Bx (3) converge to d²c/(1 - c) almost surely. The following Theorem 4.1 and 4.2 show that both Bx 3) and (x, B) converge to o²c/(1 - c) at the rate 1/p. Furthermore, the limiting distributions are de- rived by making use of the CLT for linear spectral statisties of large-dimensional sample covariance matrices.
Theorem 4.1. Suppose that the training data is generated from the model ( and the assumptions (A) and (B1) hold. Then the first type of out-of of-sample prediction risk Rx (6. (3 of the min-norm estimator 22) satisfies that, as n.P > si such that p/n = Cn + +
c,O² _ ) 4 N(e, oH),)
p (x
1-
(6)
where
20² 1c-
0 2222 -3) and o: 20 (c 1)
c20r(Vs- -3)
Me
+
+
1-c
(1 c)²
Conclusively,
P(La,e S Rx (x,3)) S Un,e) + a
where 1 a the confidence level and
C2 1 [ Za/20e), La.c 1-cn p
c, 1
Ua,e 1 1- Cn
- (Me + La)20a))
p
Under the assumptions of Theorem 4.1 we know that II I, S. and
(x = Vx Vx.a = 0²
(x = _x,,(0, = 0,
Tr Σ)
n
Thus (x, (3) equals to Rx, Rx, (3) and the two risk share the same asymptotic limit.
5

---

Under review as a conference paper at ICLR 2021
Theorem 4.2. Under the assumptions of Theorem 4.1 the second type of out-of-sample prediction
risk (x,3(3,3) of the min-norm estimator c < 1,
2 satisfies that, n, p oo such that p/ Cn.
p(Rx,o(3.3) 1 Cn
G,
4 N(He,
and
P(L.. S Rx B) S Ua.o) +
where Mes oe, Lag and U are the same those in Theorem 4.1
4.3 OVER-PAPE PARAMETRIZED ASYMPTOTICS
In this section, consider the min-norm estimator 2 in the over werrparraeetrizes case >> 1. The bias term, either Bx (3, (3) (3, B), is generally nonzero. According Lemma 2 in Hastie al. 2019), both Bx (3, 3) and (x,,(3, 3) converge to (1 - 1/c) as n. P + +oo and p/n + c > 1. This implie that the bias term can influence the asymptotic behavior of the prediction risk, including the convergence rate. Hence to derive the CLT of the out-of-sample prediction risk, we need to consider both the bias and variance terms in
In the following, we investigate the asymptotic properties of the two prediction risk (x 3) and (,, B) under various combinations of the assumptions (Al), (B2) for X and scenarios (CI), (C2) for both random and nonrandom B.. We start with the case when ,3 is a constant vector.
Theorem 4.3. Suppose that the training data is generated from the model ( and the assumptions (A), (B2) and (C1) hold. Then the first type of sample prediction risk Rx (B, B) of the min- norm estimator 2 satisfies that, as nt, + 0o such that p/n = Go e1
vp Rx (3.3) (1
Cn -T ---------
1 1
o²
4 N(P,,1, o21))
(8)
Cn
where Me,11 = and 0² = 2(1-1) nr A more practical version is to replace Pe,1 and 0²,1 with
ca
a² 0²(u3 - 3)
and 5e. = 2(c - 1) 1 203001
11 c)2 + (Us - 3)
Pe,1
+
vD
(1 1 c)2
c-1
6²
(c 1)2
Conclusively,
P(Ta,e S (x S Ua,e) - -0,
where - a is the confidence level and
a²
La,e = (1
)r²
(Mc,1 7ra22o,1);
On
Cn -
vp
Ua. (1
)r²
+
vp ( Za/2ōc.)).
On
On -
Remark 4.1. Under assumption (CI), Bx(,, = Bx.o(,, and Rx(3, = (3x,((,,9) Thus Theorem 4.3 still holds if we replace Rx(8. 3) with (x,,(B,3),
Remark 4.2. Under Assumption (B2), the eigenvector of Σ is asymptotically Haar distributed. Therefore, the bias term Bx (3, B) is only related to the length of B. However, in the anisotropic settings with general E, the eigenvector of the Σ is no longer asymptotically Haar distributed. The limiting behavior of Bx( (3) heavily relies on the interaction beiween B and the eigenvectors of E. Therefore, we conjecture that there is universal convergence rate for the bias term Bx ()
that can cover arbitrary non-random ( and anisotropic Σ in the over-parametrized case, not to mention the prediction risk Rx B). 3). A small simulation experiment is conducted in Appendix G
confirm our conjecture on this point.
Next consider the case when B is random vector that follows assumption (C2).

---

Under review as a conference paper at ICLR 2021
Theorem 4.4. Suppose that the training data is generated from the model 1. and the assumptions
(A), (B2) and (C2) hold. Then as n.P - oo such that p/n = Cn + c
> 1, the first type of
out-of-sample prediction risk Rx (3. (3 of the min-norm estimator satisfies,
P (x) - (1- ))²2
On -1
o² 4 N(He2,
Cn
where
20²01 olln -3) and o² (1 - -c)4
+ co' - 3) (c 1)2
He,2
(1 c]-
c-1
Hence we have
P(la,e S () < Ua,)) 1 a,
where
La.e =
0²
+ (1
1
)n² +
(Me.2 - Zo.2
On -
Cn
Ua, = 0²
- )n² + } (Mc2 + Zz/20o.2).
1
+ (1
On
Cn
As for Rx,,( we have the following theorem. Theorem 4.5. Suppose that the training data is generated from the model 1 and the assumptions (A), (B2) and (C2) hold. Then, as n. + oo such that p/n = Cn out-of-sample prediction risk Rx,a( (3, () of the min-norm estimator ② satisfies,
1, the second type of
vo{ (x (1 1r- o² --- 4 N(ue, &.3))
(10)
Cn
where Me.3 O and o²,3 = 2(11 - 2) A more practical version is to replace pe,3 and o²,3 with
Des = vD c1-c)2 c-1 } and 0e.3 2(1 - + 15 20
1 2a2 (²((3-3)
(1-c)) + co - 3)
(c - 1)2
The corresponding (1 -coffideeeecce interval is given by
P(La.c S Rx ( B) S Un.)) + 1 1-11 a,
(11)
with
La,
0²
+ (1
_)²
1 )1²
1
(Wes Zz,22e,3),
Cn -1
Cn
vD
02
1 Cn
Va, = Cn
-1-
+ (1
Te (Me, + Lal20ca).
Note that besides the leading constants in (e,,) the version (Fe.3, 3e.3) also contains smaller order lerms, including terms of order O(1/ /P) in Be,3 and terms of order O(1/p) in Je33 These smaller order terms will vanish when p and n grow very large, but for finite sam- ple situations, these smaller order terms will provide a finer approximation for the finite sample distribution of Rx.a(,,,) (). As shown in the following experiments, these terms have indeed made non-negligible contributions to fitting the empirical distribution of (x. which sheds new lights for practitioners.
Remark 4.3.
Remark 4.4. we compare the results in Theorem 4.3 3andd 4.5 we will find out that Rx( (3) with constant 3 and Rx,a(,, (3) with random share the same first-order limit and second-order error rate -1/2)) This is quite intuitive because both risk treat B as a constant. Their differences are reflected in their limiting variances. Nevertheless, it's very interesting to observe from Theorem 4.4 that, Rx (B, 3) with random 3 under the prrr-parametrized case has smaller second-order error rate Opp )) It enjoys the same rate as the under-parametre parametrized case in Theorem 4.1 A possible explanation would be that averaging over the randomness in B can partially offset the curse of dimensionality that Rx (g. (3 achieves the same error rate for all p, n combinations.
Remark 4.5. It's s's worth mentioning that the only assumption regarding data distribution is assump- tion (A), where only finite fourth order moment is required. Non- Gann-aaasianttt allows our theoretical results more widely applied.
7

---

Under review as a conference paper at ICLR 2021
4.4 DISCUSSION
In this section, we first make short conclusion of what we have done theoretically in this paper and further discuss some possible directions of extension.
We have systematically investigated the second-order fluctuations of two types of prediction risk, (3, (3) and (3, B). for the high dimensional least square estimators B3. Theorem [. and 4.4 are for (3) while Theorem 4.2 and 4.5 are for (3, B). Both fixed effect and ran- dom effect of the regression coefficients ,3 are discussed following the settings in [Hastie et al.
2019 , (x 3) and ( (3 are the same when /3 is nonrandom as established in Theo- rem Asymptotic results are categorized into the under-parametrized case (p < n)) and the over parametraaedee case (p > n.)
Although the first-order limits of the prediction risk in high dimensional linear models have already been well studied in recent years, including general extensions to anisotropic features and signals in Wu & Xu 2020 the "double descent" risk curve is just function of the limiting ratio lim n.. There is still a noon-negliibble discrepancy between the finite-sample prediction risk and its first-order limit on the "double descent" curve. How large is this discrepancy? How fast does the risk converge to its limit? Our CLTs provide answers to such questions and give a fine-grained characterization of the second-order fluctuations of the prediction risks. Not only explicit forms of the leading constants in the limiting means and variances are shown in the main theorems, smaller order terms are also derived to improve the empirical performance for practitioners.
It is also important to recognize the limitations of our results. First, the present paper only concerns linear regression tasks since the linear regression task simple but important as well. Some recent works linearize neural networks at the initialization and employ Neural Tangent Kernels (Jacot et al. 2018) to approximate the training procedure of strongly over-parametrized neural network by solving linear regression task, e.g. Du et al.] (2018); Arora et al. (2019)] Lee et al. (0019) Though the setting considered in this paper is simple and limited, the problem has not however been fully understood so far in the literature. Therefore, we among the first to take the task and develop the second-order fluctuation results for the prediction risk. Second, we assume general covariance Σ and non-Gaussianity for the under- saiter--prmmerrzeedd case, which fits the most updated and realistic settings in the literature, however we only investigate the isotropic settings while still allow for non- -ou-Gaussiy under pree-arrmettiztioon.. We haven't I extended it to the more general anisotropic settings yet. The reasons are two-fold. On the one hand, according to Wu & Xu (2020), the first-order limits depend on the Stieltjes transforms of the unknown spectral distribution of E. Since Σ is unknown, we cannot obtain any explicit characterization of the first-order limits, not to mention the second-orde fluctuations. The CLTs would only be written as certain complicated implicit functions of Σ and would be too abstract to evaluate practically. More restrictions would be imposed on E to guarantee the second-order convergence. On the other hand, from the technical perspective, the techniques required for anisotropic over-parametrized cases are very different from the isotropic cases due to difference in the bias-variance decomposition in 44. The tools in random matrix theory have not been fully developed yet for anisotropic cases. Since have considered various scenarios in this paper, including random and nonrandom signals /3 for both conditional and unconditional risks, will take great efforts and continuous work to extend all of them to the most general settings, which would lead to many subsequent works in the field of machine learning and random matrix theory literature.
EXPERIMENTS
In this section, we carry out simulation experiments to examine the central limit theorems and the corresponding confidence intervals in Theorem aeeeorem44.)aang (.2 and Theorem [.5) We generate data points from the linear model (1) and directly compute the prediction risk via the bias-variance decomposition in (4). The generative distribution Px is taken to be the standard normal distribution. The noise distribution P. is taken to be N(0, 1). In the following, we present the gap between the sinite-sample distribution of the prediction risk and the corresponding limiting distribution to check the central limit theorems and use the cover rate to measure the effectiveness of the confidence intervals. More simulation results, including cases with non-Gaussian distributions for Px and P. are relegated to the Appendix due space limitations.
8

---

Under review as a conference paper at ICLR 2021
Example 1. This example examines the results in Theorem 4.2 We define statistic
T P
[ de
0² _ de
Me
According to Theorem 4.2 Tn weakly converges to the standard normal distribution as n, P + oc. In this example, 1/2 and 50, 100, 200. The finite-sample distribution of Tn is presented by the histogram of T, in Figure 2 with 1000 repetitions, where the solid blue curve stands for standard normal density function. It can be seen that the sinite-sample distribution of T, is very consistent with the standard normal distribution, especially when n. p become larger. When a = 0.05, the empirical cover rates of the 95%-confidence interval are 94.2%, 93.5% and 95.3% for p 50, 100 and 200, respectively. All these experiments verify the correctness of our theoretical results.
Normal
Normal
Normal
89
03
p-30
p-109
p-200
Dersity
0.3
03
81
03
B1
Figure 2:
The histogram of Tn. The solid line is the density of the standard normal distribution.
Example 2. This example verifies the results in Theorem 4.5
Here we define two statistics:
Tw,0
vp
Rx,a(33,)) - -01
)n²
3e,3
0,3
c,3
vp
0²
Mo.3
Tn,1
- (1 (x
)n²
Cn
Cn
According to Theorem 4.5 both Tn.0 and Tn,1 weakly converge to the standard normal distribution as n. p + +00. Compared to Tn,o. Tn,1 provides a better approximation for the finite sample distri- bution of Rx.a( (3) because it contains smaller order terms in the asymptotic mean and variance. We take 3/2 and p 150,300, 300, 450. Similarly the finite-sample distributions of Tu,o and Tn are presented by the histogram of Tv.0 and 1x,1 with 1000 repetitions. The comparison between these two statistics is shown Figure 3 It can also be seen that the finite sample distributions of Tn.0 and Tn,1 both match the standard normal distribution quite well, especially Tu with more precise characterization. The empirical cover rates of the 95%-confidence interval (II) are 93.8%, 94.7% and 94.4% for 150, 300 and 600 respectively, which further shows the validity of our theoretical results.
0.5
1-0
p-300
p-000
6--
844
Densig
0.3
02
T,,0
p-130
p0000
p-800
Density
0.3
Dereitty
Density
82
83
82
60
T
To.11
Figure 3: The histograms of Tn,o and Ta The solid line is the density of the standard normal distribution.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in neural networks. arXiv preprint arXiv:1710.03661 2017.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang. Generalization of two- layer neural networks: An asymptotic viewpoint. In International Conference on Learning Rep- resentations, 2019.
Zhidong Bai and Jack W. Silverstein. CIt for linear spectral statistics of large-dimensional sample covariance matrices. The Annals of Probability, 52:5536536 2004.
Zhidong Bai and Jianfeng Yao. On the convergence of the spectral empirical process of wigner matrices. Bernoulli, 1156:1059--092, 2005.
Zhidong Bai and Jianfeng Yao. Central limit theorems for eigenvalues in a spiked population model. Annales de I'IIP Probubilités statistiques, 44(3)4447477, 2008
Zhidong Bai and YongQua Yin. Limit of the smallest eigenvalue of a large dimensional sample covariance matrix. In Advances In Statistics, pp. 108-127. World Scientific, 2008.
Zhidong Bai, Baiqi Miao, and Guangming Pan. On asymptotics of eigenvectors of large sample covariance matrix. The Annals of Probability, 1534)1153 2007.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. stat, 1050:28, 2018.
Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. arXiv preprint urXiv:1903.0757/ 2019.
Lin Chen, Yifei Min, Mingrui Zhang, and Amin Karbasi. More data can expand the generalization gap between adversarially robust and standard models. arXiv preprint arXiv:2002.04725. 2020.
Yehuda Dar and Richard G Baraniuk. Double double descent: On generalization errors in transfer learning between linear regression tasks. arXiv preprint arXiv:2006. 07002, 2020.
Yehuda Dar, Paul Mayer, Lorenzo Luzi, and Richard Baraniuk. Subspace fitting meets regression: The effects of supervision and orthonormality constraints on double descent of generalization errors. arXiv preprint arXiv:2002. 10614, 2020.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. arXiv preprint arXiv:1911.05822 2019.
Michal Dereziński, Feynman I Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. arXiv preprint arXiv:1912.04533, 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes parrmaarameteriied neural networks. In International Conference Learning Representations, 2018.
Melikasadat Emami. Mojtaba Bahraee-Ardaker Parthe Pandit, Sundeep Rangan, and Alyson K Fletcher. Generalization error of generalized linear models in high dimensions. arXiv preprint 18Xiv:2005.001890 2020.
Mario Geiger, Stefano Spigler, Stéphane d' Ascoli, Levent Sagun, Marco Beity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition as a paradigm to understand the loss landscape of deep neural networks. Physical Review E, 100(1):0121 2019.
10

---

Under review as a conference paper at ICLR 2021
Cedric Gerbelot, Alia Abbara, and Florent Krzakala. Asymptotic errors for teacher-student con- vex generalized linear models (or: How to prove kabashima's 's replica formula). arXiv preprint 201.0020006.68881,, 2020a.
2020a..
Cédric Gerbelot, Alia Abbara, and Florent Krzakala. Asymptotic emrors for convex penalized linear regression beyond gaussian matrices, arXiv preprini (rXXi::0002.03372. 2020b.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-
dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08500 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems, pp. 8571- 8580, 2018.
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. arXiv preprint arXiv:2002. /0477, 2020.
Ganesh Kini and Christos Thrampoulidis. Analytic study of double descent in binary classification: The impact of loss. arXiv preprint arXiv:2001.11572, 2020.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pp. 8572-8583, 2019.
Daniel LeJeune, Hamid Javadi, and Richard Baraniuk. The implicit regularization of ordinary least squares ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 3525- 3535, 2020.
Marco Loog, Tom Viering, and Alexander Mey. Minimizers of the empirical risk and risk mono- tonicity. Advances in Neural Information Processing Systems, pp. 7478-7487, 2019.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint 1908. 2019.
Yifei Min, Lin Chen, and Amin Karbasi. The curious case of adversarially robust models: More data can help, double descend, or hurt generalization. arXiv preprint arXiv:2002.11088, 2020.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max- margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint 1rXiv:1911.01544 2019.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless inter- polation of noisy data in regression. IEEE Journal on Selected Areas Information Theory, 2020.
Preetum Nakkiran. More data hurt for linear regression: Sample-wise double descent. arXiv preprint
2019.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference Learn- ing Representations, 2019.
G. M. Pan and W. Zhou. Central limit theorem for lignal-o-intteferee ratio of reduced rank linear receiver. Ann. Appl. Probab., 1232 06 2008. doi: 10.1214/07-AAP47. URL https://doi org.org///ooooo 10.
12 1214407--
Yiwei Shen and Pierre C Bellec. Asymptotic normality and confidence intervals for derivatives of 2-layers neural network in the random features model. In Neural Information Processing Systems, 2020.
Ya Sinai and Alexander Soshnikov. Central limit theorem for traces of large random symmetric matrices with independent matrix elements. Boletim da Sociedade Brasileira de Matemática- Bulletin/Brazälian Matheattcal Society, 1911):1224 1998.

---

Under review as a conference paper at ICLR 2021
S Spigler, M Geiger, S d' Ascoli, L Sagun, G Biroli, and M Wyart. A jamming transition from under- to over-varaeee preeraatmtttinnoonnn affects generalization in deep learning. Journal of Physics A: Mathemat- ical and Theoretical, 52(47):474001, 2019.
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
Denny Wu and Ji Xu. On the optimal weighted 12 regularization in overparametrized linear regres- sion. arXiv preprint arXiv:2006.05800 2020.
Yue Xing, Qifan Song, and Guang Cheng. Benefit of interpolation in nearest neighbor algorithms.
arXiv preprint arXiv: 1909. 10009.117000 11720, 2019.
Ji Xu and Daniel J Hsu. On the number of variables to use in principal component regression. In Advances in Neural Information Processing Systems, pp. 5094-5103, 2019.
Shurong Zheng. Central limit theorems for linear spectral statistics of large dimensional f-matrices.
Annales de I'IHP Probabilités statistiques, 48(2)4444476, 2012.
Shurong Zheng, Zhidong Bai, and Jianfeng Yao. Substitution principle for clt of linear spectral statistics of high-dimensional sample covariance matrices with applications hypothesis testing. The Annals of Statistics, 43(2):546-591, 2015.
A PROOF OF THEOREM AND THEOREM 4.2
Let X /2 According to the Bai-Yin theorem Bai & Yin 2008 ) the smallest eigenvalue of Z Z'Z/n is almost surely larger than (1 v2)2/2 for sufficienlly large n. Thus
Amin
X 12
Amnn
Z"Z 72
CD
v
which implies that the matrix X X//n is almost surely invertible for large n. By Section 3.2 II = 0,
Bx Bx ( = Bx (,,, 0 and Vx (8, Vx (3, B). Thus the CLT of Rx (3, () is same to that of Rx,,( g). For simplicity, we focus on Rix (33 () in the following. Notice that
Vx () = 2
o²
Tr
(x-1))
1/2
Z
Σ 111//
0²
1
o²p
-FF (s)
where Fz the spectral measure of Z/Z According to Theorem of Hastie (2019). as n.P + oo such that p/n = On + E (0, co), F2(x) weakly converges to the standard Marcenko-
Pastur law Fe(x)) and
1 dd(((s) -2 - (x( + oZc
c
Here the standard Marcenko-Pasttu law Fz(x)) has density function
Pc(x)) = {
1
(b 2)(r a), a S x S b,
0,
O.W.,
where a = (1- (1-v002, = (1+ + 2 and (x has point mass 1 - at the origin if > 1. Hence
o²p
Rx Rx(33 (3, - 1- -n
Cn
dFz(s) - 02cn d (s)
ozen /
1 (dF ddF. (s)).
12

---

Under review as a conference paper at ICLR 2021
According to Theorem 1.1 of Bai BaB
& Silverstein (0004,
p (3) o² Ca)
--cn 4 (H),
(12)
where
0²c 1 cm m1
m2
He
2 J {1 cm(( (2((()))111 + m(2) 2 dz
(13)
o² c21(11 - -3)
f 1 cm(2) (1 + m (2) -3
2ti bn = cmn 2) (1 + m (z)) ) dz,
o o²c² p $
d
2T Pc, Cc
22 (m(21) ml [2 dzi
m(z1)
d
ml 22 dzzd2z
(14)
o 0² (us 3)
dml و dm (22).
2
c, c, 22 (1 (1+ ml (2) ))²(1 + m (22))
Here the contours in (13) and (14) are closed and taken in the positive direction in the complex plane, enclosing the support of Fz, i.e. [11 v0)², (1 + 2. The Stieltjes transform m(z) satisfies the equation
m
1 m
To further simplify the integrations in Me and oe, let = = 1 + velrs + p/²) + and perform change of variables, then we have
Vor (1+ Vereyz de
m
Velr d
de dz
dgC rga
dm-
1 Verg'
and when & moves along the unit circle |&| = 1 on the complex plane, will orbit around the center point c along an ellipse which enclosing the support of Fz. Thus
0²c Φ
cm 2) (1 + m=())
He
2τi j 2 (1 - c2(2)2(11 + m(2)) (22) dz
o² 0²clvs - 3) of cm(2) (1 + m(2))
(2 11 m(2)) 2 dz
2mi
9221 - cm( (2m(2)((1)
0cc
1
2xi 11-= r( (e)c+rr)(1 + vorE)(E - F) + dE
0² 0²clus - 3) o
(fC rc)(1 vore) de
2
[8|=1
0²2
0²
(2
(c 1)2
1 1-c
As for o?, note that
dm
2ii Jn
21 (m, m2
1
Ver
= 2mi /61/=1 1 velriei mrl ) +c (m, + itvon )2 Eir del
1
Veria
2mi [[l==1 (51 + -=-((iii 1) ((riSive 1)mz + 1) dFi
(c 1) [(c 1)m 112
13

---

Under review as a conference paper at ICLR 2021
therefore
o²2
2 H
1
dmg dm2
2122(11 m2)²
2 2
$
dm2
2ti |6z/=1 22(c - 1)((c (c 1)m2 - 13
20¹²²² c²
ver2Ez
20
(c vo-))(++vvb)) d32 (c 1)a
2τi
|k2/=1
Meanwhile,
1 1
1
21 (1 m111))² dun(z1)
2Tí In
2Ti |El== vot(1 rE) df 1
1
c- 1'
hence
0 0 3) of $
000 3)
( (2))d(()) (1 c)²
dm
4x
Cc Sc
21 (1 (1+ ++(m)))) + m=22)
and
2c ( -3)
0²
(c 1)2
(1-c)2
Let
Tn p [Bx(3, - -0² Cn Hc
0e
- Cn p
According to 12 we have
P(Lao S Rx, s Ua,)) = ((-2a/12 S Tn S Ba/2) + a,
where
La.
0²
Cn
- (Jo Zaf20o)
1
Cn
p
Ua,c
0²
On
+
1
(Het Za.200c)
1 --
p
B PROOF THEOREM 4.3
Notice that
Bx (x,
(I Σ+Σ)
lim Br (I, - (E++
111
lim 2BT -1B -
Since G is constant vector, Theorem 1.3 in |ann & Zhou (2008) regarding eigenvectors. Their works investigate the sample co- variance matrix Ap Tp X, 1/2 /n, where T, is p p nonnegative definite Hermitian matrix with square root T and X, is an n p matrix with i.i.d. entries (Xij)nxp Let UT denote the spectral decomposition of Ap where A, diag(A1. .Ap) and Up is unitary ma- trix consisting of the orthonormal eigenvectors of Ap. Assume that pp is an arbitrary nonrandom unit vector and y (y1, W/.- yT UØa, up two empirical distribution functions based on eigenvectors and eigenvalues are defined as
make of the results in Theorem 3 in Bai et al. (2007) and
-x) = Σ
I 11 <)), FAx(x) 1 P Σ 1045
1
t=1
14

---

Under review as a conference paper at ICLR 2021
Then for a bounded continuous function ((z), have
Σ Eiyp)o(A,)) Σ 9(2,) o(z)dF (x) g(z)ddAA(())
The results in Bai et al. (2007) and Pan & Zhou 2008 show that
Lemma B.1. (Theorem 3 Bai et al. (2007) and Theorem 1.3 Pan Zhou (2088) Suppose that
(1) Xs ' are Li.d. satisfying E(x.y) - O. E([x;)] (2) = 1 and E(xxay|*) < oc;
(2) Tp E CP, ||mpl| = 1, lim p/n o0):
(3) Tp is nonrandom Hermitian non-negative definite with with its spectral norm bounded in p. Ty - m (z),
with Hp = =FT, 3 H a proper distribution function and (Tp where m (z) denotes the Stieltjes transform of H (t);
(4) 91.-.. 9k are analytic functions on an open region of the complex plain which contains the real interval
lim inf Amiin (o.)((((11 vol², sim Amaz (Tp) (o.)(((( + vor):
(5) as n. p + co,
sup /n x [ mpp... (2)T, Ip) By f +m By (2) dH dH) - 0.
Define Gp(z) = vn(FF FA)())), then the random vectors
(f (l) -f
forms right sequence and converges weakly to a Gaussian vector Ngi. Nga with mean zero and covariance function
[ (1(21)92(2) 22122(22 21 2m) m,
(32mg 2 d21d22.
Cov(xg: X
2T C.
The contours C₁ C2 are disjoint, both contained in the analytic region the functions (gl, .9k) and enclose the support of Fe..H, for all large p.
(6) If ((x) satisfies
f (1+ tr )1 (1+ + (2222)
dH(())
dH(I)
dH
1 (21)
1 fm((2) x22
then the covariance function can be further simplified to
2 2 of g1 (1)))))))))))))()))))))))))))))) (z) - (o) (1))dFF)))))) (00) / (a(t)dFFcH()))
Cov Xgx)
Recall that Bx (B.3)) lim 21F + -1 Let g(z) = 1/(x/ 2) and a. B/r. Then we have
f (()) = (
-v ( ( 0 8f g(w))dP...((5)
where Fe, (x) the standard Marcenko-Paune law. It not difficult to check that under Assump- tions (A1), (B1) and (CI), all the conditions (1)-66 in Lemma B.I are satisfied.
To proceed further, denote a = (1 2o)² b == (1+ If replaced by G,, and b are denoted by an and bn respectively. By some algebraic calculations, we have
f glo)dFF.. (x)
b
1
2T V(nn x)(x On )d
Gp
T + z
an
1
- 1 + Cn + 2 + 2c, 1) + (1 + 2)
(1
Cp.
2c,
15

---

Under review as a conference paper at ICLR 2021
and
2
(ʃ (o(=))&FF((0)) - (1 (1tt))//F(coooffaarrraoo) (((o)aF((C0))
Var(xg)
2 (1 (
1
1
1
+
(bb - (0-2)(2 - a dz
22
(0 + z)²
2TCx
2 (1 1, ) +
bb
1
2Tex (bb-20 - 2) - a)dx)
c' 2
+ 2
Therefore,
2-0+ lim 2 ʃ g(z)dFe, cn (r)= =
2(c
lim 2² Var(x)) and
cd
Cp
Furthermore, as n, p + 00, p/n = =c, + +c> 1,
vn (x(x( (1
_
1 )r²)
4 N (0.
2(c 2(c- pd)
Cn
o
This can be rewritten
(x -1 )
4 N N(0 2
Gn
Next we deal with the variance term 1x( According to the Assumption (BI), the variance term is
Vx o² Tr
Σ
5
where 8,, i = I,...,, n are the nonzero eigenvalues of X'X/n. Let (4i i = 1,... n} denote the non-zero eigenvalues of XX" /p, then we have
(x 0² n
Σ
1
o2n
dFxxT
o²
4
P
c-1
By interchanging the role of p and from the result in Theorem
4.1
as n. - 00, p/n C.
c >>> 1, we have,
Σ
n
1
n d N
d'
d(44-3 3)
2d
d(us 3)
4
1
c
(d' 1)2 c (c'
- 1)a
(1 c²22
1=1
where da n/p 1/Cms d'
1/c. This result can be rewritten
Σ t
n
p
4 N (1 c)2 + (v4 -3 20
cl4 - 3) (c- 1)2
+
Cn -1
c-1 (1-
Hence the CLT of (3, is given by
p( (Vxx - On -- $ N
o²
ca2
o² 0²(4z - 3) 20 co (1g -3))
+ c-1 (1 c)- (c 1)2
(1 c)2
Notice that Cov Cor(Bx(3, (8, V2 3))
0. According to the consistency rate and the limiting
(3 3), we know that the bias (x is the leading term of distribution of (x 3) and Vx (3, B). This implies that
vpf V (x - (1- 1
-1- -1------------------ - - NO.002.)
where 02 = 2(c - //2 A practical version of this CLT is given by
v [x (1
o²
}
d N (ie,,,
Cn
Cn
where
1 f ca2
02u 3)} c-1 f
Pe,1
+
vpl (1
c)2
2(c 2 1)
1 2c
+ co (1/ c0(
3)
02 =
p
o)a
(c-
16

---

Under review as a conference paper at ICLR 2021
C
PROOF OF THEOREM 4.4
First we consider the bias term Bx (3) By Assumption (A1), (B1), and (C2),
Bx 3) = E| X = [
Tr (T - Σ 3)
r² Tr(I, Σ사Σ} = 11 - -1/p).
Alternatively, we can rewrite the bias as
Bx (3,
lim Eld - -1)
2++0+
lim E[2 =I,) 3|
2
lim 2 Tr Σ + 21p)
p
Define that (z) = = I==+ = Notice that f (z)l and [z) are bounded above. By the
Arzela-Ascoli theorem, deduce that (2) converges uniformly to its limit. Under Assumption (C2), by the Moore-Osgood theorem, almost surely,
2 Tr(E zIp)
lim (B( lim lim n.p-200
2-0 np
p
2
I -xx + zIn
lim
lim
2 Tr
2- t
In fact.
lim (x 2-50 n.o++00
x² lim lim 2=m(-2),
where (2) is the Stieltjes transform of empirical spectral distribution of ing to Theorem 2.1 in /Zheng et al. (2015) and Lemma 1.1 Bai & Silverstein 2004), the truncated
X /n. Accord-
version of pmm, (2) m(2)) converges weakly to two-dimensional Gaussian process (-) satis- fying
cm 3 (1 + m
c(vs 3)m²
E[M(=)]
+
(1 + m) {(1 m)² cm {(1 + m) 2m
and
2{ m' (21 )m (22)
1
(o)(M(2))
(m(21) ) m (22)))²
(21
)2
c(us - 3)m (2) )m (22) (1 (( (1 m (22))
where m m=)) represents the Stieltjes transform of limiting spectral distribution of companion matrix XXT -///n satisfying the equation
m 22) = 1-c
+ cm()).
When > n, we can actually solve m(z) equation and obtain that
-1 2 +
/-4: + (1 - c 2)
m(())
2z
m(2) 1-c z +
42 + (1 + 2)
2cz
17

---

Under review as a conference paper at ICLR 2021
Therefore, by some algebraic caleulations, we have
lim ()(3,3) = lim r² lim (- = lim zm((=) ())(-2) + =(1 - - -
n-p-300
n.p-900
2 2+0
2+0
lim n
22 lim +
2 "1
m, (3) = y² lim 2m(-2)
m,
P
C 2-
= (1
Moreover,
Var (a)(
lim Cov (2) 21 72タ
2m 2m'(2) (z) 3(m 3(m
dl4 3) (=))² (1+ m()))*
6(m' 62))
By substituting of the explicit form of ml m(=), we can easily derive that
lim 2B[M(-2)) = 0, lim 2² VaraaaaMMM = 0,
which means that the second-order limit of (x is still r² 1/c). All in all, Bx 2x. B) is identical with constant r² (1 1/c) in distribution.
On the other hand, by Assumption (B1),
o² Vx (x 3)
0² a [T(
Σ
72
n
8;
where 8; i = L...., ........ n are the nonzero eigenvalues of X'XXXn. /n. Similar to the proof of Theorem 4.3 the CLT of (x (3 is given by
Cn. --1 $ N cO2
0² 3)
20
+ co - 33
v(Vx(0,99) - Combining the results of Bx (3, and Vx (3,,,3), we have
c]
c-1
(1 -c-
(c 1)2
3),
p Rx (3, - 22
1
o²
4 N(Hn2,002))
Cn -1
Cn
where
co2
0² 0² 3)
20004
co (Vi -3)
Ha.2 = (1 (1-c) c)-
c-1
6e2 =
(1 (1-c)a
+
(c- 1)²
D PROOF OF THEOREM 4.5
Note that under Assumption (BI) and (C2), Bx,,(3,3) = 3 = (I, - Σ)EB we directly consider (T, - E E, we can make use of the asymptotic results for quadratic forms Theorem 7.2 in Bai Yao (2008) stated as follows.
E
Lemma D.I. (Theorem 7.2 in Bai & Yao (2008)) Let =An (n) be sequence of n x real symmetric matrices, {x.),E
sequence of i.i.d. K dimensional real random vectors, with E(x,) = B(x,x7) = (1xz K and [[[[xx11] < co. Denote
x; =; Kx1, X(e) (xe1," ". xxn)", 1. K, 1,....
assume the following limits exist
1 " (2),),
w= lim
0 == lim
Tr A
n=
1=1
Then the K-dimensional random vectors
1
Zn = (x1, Zn Vn converge weakly to zero-mean Gaussian vector with covariance matrix D + D2 where
(X(0) - THe Tr(An)): 1 1
Dijer ( ) [Dalee- (0 -)( + +22) 1 1 f, < K.
18

---

Under review as a conference paper at ICLR 2021
According to the results in Lemma D.1
let A, = II I
1, - E. then have, as p 00.
r²
vD
gT
Tm(m]] } 4 N(0, = +
where
1 6
w lim
IT 153
0
lim pox
Tr((T22 =
1=1
and
& = w [ - T = w E(3,) - 1)r²
& = (0 w0 + 720) 2( - w)r
Since in the proof of Theorem 4.4 we have already shown that
Tr(II) = -1
In particular, if (3 follows multivariate Gaussian distribution, i.e. 3 ~ No,0, [1t)), 1 (n4)
then as + oo,
vp Bx,a( - 21 -1-11-0 -1 - N (0. (0,2(1 2(1
Moreover, Vx. (3 we have already proved in Theorem 4.4 that 0² (v (11-3) 2c 04
Cn - 4 N
a²
co2
3)
co 3)
p(Vx, ((3,,)(3,33)
(1-c) c)2
c-1 c)-
(c- 1)2
Note that Cov(Bx,ale 3), (3, 3)) = 0. According to the consistency rate of (x,,( 3) and (x, B), we know that the bias (3 3) is the leading term of Rx,a( B). This implies that
vof Rx (x,e(0,)) (1 -
2
Cn
where = = - 1/c). A practical version of this CLT is given by
v Rx. - -
1 -(1-))
o²
(ien, o23),
On
where
1 f ca2
0² - 3)
Ne,3
vp
(1 c)2
c- f
1 )rd
1s 0c
co 3) (c- 1)2
02 2(1
+
1 (1 0)¹
E MORE EXPERIMENTS
E MORE RESULTS OF EXAMPLE
This example checks Theorem
4.2
We define a statistic
Ta P [xx(3,3) - 0²
_0 Cn
Pg
1-111 Cn
Te
According to Theorem 4.2 T, weakly converges the standard normal distribution as as p -> co. In this example, c = 1/2 and p 50, 100, 200. To make sure the assumption (A) holds, the generative distribution Px is taken to be the standard normal distribution, the centered gamma with shape 4.0 and scale 0.5, and the normalized Student-t distribution with 6.0 degree of freedom. The finite- sample distribution of T,, is estimated by the histogram of T, under 1000 repetitions. The results presented in Figure One can find that the fmite-sample distribution of T, tends to the standard normal distribution as n,p + +oc. When a = 0.05, the empirical cover rates of the 95% 95% -onfccnnee interval are reported in Figure
19

---

Under review as a conference paper at ICLR 2021
Normal
Normal
Normal
0.4
0.4
0.4
Densiyy
Density
0.2
0.1
01
03
Gamma
Gamma
Gamma
81
05
0.5
pa50
pa 100
p=220
0.3
Density
Density
63
0.2
0.2
0.2
0.
0.0
0.0
Tn
To
t-distribution
t-distribution
t-distribution
p-30
p-100
p-200
0.4
0.2
Density
Density
0.-
0.1
0.3
00
Figure 4: The histogram of Tn, The solid line the density of the standard normal distribution.
Normal
Gamma
t-distribution
0.97
0.97
587
0.95
0.55
2.95
Cover Rate
0.84
Cover
0.2
0.92
2.02
125 150
175
200
0.90
30
100
15C
200
0
75
125
275
Figure 5: The cover rate of the confidence interval
as creases. The confidence level is 95%.
20

---

Under review as a conference paper at ICLR 2021
E.2 MORE RESULTS OF EXAMPLE 2
The Example 2 checks Theorem
4.5
Here we consider the standardized statistics:
To,0 = vp
Rx (1-
)r²
o²
3
033
On
On
c,3
Tu.1 vP
1 - )r²
0²
Rx (3, 0z,3
Gn
Ca
c,3
According to the central limit theorem 10 and its practical version, both Tu.0 and Tv,1 weakly converge to the standard normal distribution as n. - +00. We take e = 2 and p = 100, 200, 400. The finite-sample distributions of n,oo and Tn,1 are estimated by the histogram of T,,0 and n. under 1000 repetitions. The results are presented in Figure G and Figure When a 0.05, the empirical cover rates of the coofddonieeecee interval [1] are reported in Figure 8
Normal
Normal
Normal
100
p=200
pm400
0.4
0.
0.4
0.1
0.3
Density
0.3
02
61
0.3
Tiuk
Gamma
Gamma
Gamma
0.5
05
0.5
p-100
p0200
p-600
044
0.4
Derbil
0.3
Denstry
0.2
92
0.
Tr.0
Tr.
Te.0
t-distribution
t-distribution
t-distribution
0.5
p-100
p=200
p-400
0.4
0.3
Demolly
0.3
0.3
01
63
80
00
02
-4
-2
1,,0
Te.D
1x.0
Figure 6: The histogram of Tn. The solid line is the density of the standard normal distribution.
21

---

Under review as a conference paper at ICLR 2021
Normal
Normal
p=100
P=400
041
0.
0.4
Density
0.3
Density
84
61
0.
T
Gamma
Gamma
Gamma
0.5
45
0.5
p.100
pm200
p=660
Densioy
Density
0.2
0.2
0.2
Tr.1
T
Tn. t-dlstribution
t-dlstribution
t-distribution
p=200
p=200
p=400
0.2
Density
0.3
Density
0.3
0.
01
0.
80
Tr,1
Tw.1
Figure 7: The histogram of Tn,1- The solid line the density of the standard normal distribution.
Normal
Gamma
t-distribution
0.97
0.97
287
Cover Rate
Cover Rate
0.30
0:35
200
Cover
0.34
0.94
0.9
25
175
0:92
100
196
75
125
275
Figure 8: The cover rate of the confidence interval
11
as creases. The confidence level is 95%.
22

---

Under review as a conference paper at ICLR 2021
E.3
EXAMPLE 3
This example checks Theorem
4.3
To proceed further, we denote two statistics:
To,2
vp
{
(3, -(1 -11
-
)r²
o²
Mo.1
0c,1
On
On
0,,
Tw.3 vP
1 - )r²
2
Me.11
Rx (3, - (1
0c,1
Cn
Cn
0c,1
According to the central limit theorem ( and its practical version, both Tn and T,.3 weakly converge to the standard normal distribution as n. p.p-> - +0c. We take e = 2 and p = 100, 200, 400. The finite-sample distributions of n,2 and Tu.3 are estimated by the histogram of T,2 and n3 under 1000 repetitions. The results are presented at Figure and Figure T One can see that the sample distributions of Tu,2 and Tv.3 sinite-sample performance of Th is better than that of T2.2 When a 0.05, the empirical cover rates of the 95%-confidence interval (9 are reported in Figure 11
close to the standard normal distribution, and the
Normal
Normal
Normal
0.4
0.4
0.4
0.3
Censity
0.3
Deasty
0.3
0.2
02
0.2
0.1
0.
Tru2
Gamma
Gamma
Gamma
0.5
05
0.5
p=100
p-200
p=:40
031
Density
0.3
Denaity
02
92
0.2
0/
0.0
0.
Ta.2
T
Te.2
t-distribution
t-distribution
t-distribution
p-100
202
p-400
0.4
0.2
Dersilyy
0.3
0.3
0.2
0.1
0.
00
0.
-4
Te.2
T
Figure 9: The histogram of T2.2- The solid line is the density of the standard normal distribution.
23

---

Under review as a conference paper at ICLR 2021
Normal
Normal
Normal
p=100
P=400
041
0.4
0.3
Demsity
0.3
04
61
0.
Gamma
Gamma
Gamma
0.5
45
0.5
p.100
pm200
p=660
Dendity
Dereily
0.3
Density
0.2
02
0.2
Tr.3
TrL3
Tv.3 t-distribution
t-distribution
t-distribution
p=200
p-200
p=400
0.4
0.2
Dernolky
0.3
0.3
0.
011
03
00
1,,3
fn.3
Figure 10: The histogram of Tn,3. The solid line the density the standard normal distribution.
Normal
Gamma
t-distribution
0.97
0.97
287
0.20
2.95
Cover Rate
0.94
0.90
0.84
Cover
0.92
0.92
262
0.5
25
75
175
100
196
75
125
175
Figure 11: The coverage of confidence interval 9 as p increases. The confidence level is 95%.
24

---

Under review as a conference paper at ICLR 2021
F
AN EXAMPLE FROM FIGURE
1
Confidence Interval
142.12
Risk
300
10.20
4.91
Sample Size
Figure 12: According to the first-order limit, given a fixed dimension y 100, the prediction risks at sample size 90 and 98 about 10.20 and 49.02. More data hurt scems true. However, the 95% confidence interval the prediction risks with sample size 98 is [4.91, 142. which contains the risk for 90. Then more data hurt is not statistically significant.
G AN ANISOTROPIC EXAMPLE FOR REMARK
In the over perr-parameterized case, the bias term Bx ( 3) = IIETE is non-zero while the variance
term (,, () remains the same under- parameterized case. Therefore in this section, we conduct small simulation examine the fluctuation of the bias Bx for both isotropic and anisotropic Σ in the over-paran peee-parameterized case with non-random ,3 satisfying Assumption (C1). In particular, in the following we set r
We consider both localized and delocalized B such that
1. Localized case: B1 = (1, 0, ,0);
2. Delocalized case: B3 vp (1,
and both the isotropic and anisotropic Σ
3. Identity case: E = Ipi
4. Compound symmetric case: Σg = 0.54, 0.51,
Then we fix p/n = 2 and let vary from 10 to 300, we present in Figure 13 the empirical variance of /p* Bx and p Bx under various combinations Σ and with 1000 replications.
From the plot on the top left panel in Figure 13 we can see that the variance of /p Bx for both 3 and 32 remain constant as grows, which indicates that the convergence rate Bx is 1/ vP under the isotropic case regardless of localized or delocalized B. As for the anisotropic case on the top right corner, the variance of vp* * Bx stabilizes for 31, while decays for B2, which indicates that convergence rate of Bx under (Eg, 32) and (E2, B1) are different.
This simulation result further confirms our conjecture that the over over-paranen werrparamettrried case, there is no universal CLT for the prediction risk Rx (33 ()) under the anisotropic setting for non-random B.
25

---

Under review as a conference paper at ICLR 2021
9.
Variance of (Blas*, p)
Variance of (Bias V (p)
81
Variance of (Biastp)
Variance of (Blas-p)
P:
P
Figure 13: The upper panel is the empirical variance of /p Bx, the lower panel is for p Bx.
26


Reviews:
[{"review_id": "wiWgUIkr7Mj", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides the central limit theorem type of results for generalization error of high-dimensional least squares estimator. \n\nStrength: It is nice to know that the finite sample prediction error converges to its asymptotic limits in the CLT style. Previous results have shown that the prediction error converges to the asymptotic limit, but it is unclear how fast the convergence speed. This CLT type of results provides the answer and this explains why empirical simulations have shown good accuracy for a sample size of just 300-500. I think it is a nice piece of result to be added to the current double descent literature.   \n\nWeakness: One major concern is although CLT type of results is interesting, whether the overall level of contribution of the paper meets the standard of acceptance or in other words whether the story of CLT is complete. This paper seems to be on the borderline and the story looks to be only half-written. First, this paper only focused on the cases when features are isotropic or signals are isotropic. Recent double descent works have extended this setting to both anisotropic features and anisotropic signals (e.g. https://arxiv.org/abs/2006.05800) and those settings are more realistic and more interesting. Secondly, although $\\sqrt{n}$ convergence is probably the optimal speed, it is good to have a lower bound result to rigorously show it. The story of this paper will be more complete if the authors can also show results on these two points.  \n\nIn summary, I like the CLT type of result, but I recommend a weak accept because of the simple setting. I will give an 8 if the authors can extend their results to the most updated settings in this linear regression model and complete the lower bound results. Further, I think the authors can simplify their theorems and assumption quite a lot once they study the general anisotropic settings. It gives better clarity.   ", "extra_scores": {}, "extra_text": {}}, {"review_id": "9StQWaACyPc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**: In this article, the authors characterized the second-order fluctuation of the prediction risk of the (min-norm) least square estimator, by assuming an underlying noisy teacher model $y_i = \\beta^T x_i + \\epsilon_i$, in the regime where the data dimension $p$ and the number of training samples $n$ grow large at the same pace. Results in both the under-parameterized (Theorem 4.1 and 4.2) and over-parameterized regimes (Theorem 4.3-4.5) were provided, under the statistical model where the data $x_i$ are zero-mean random vectors with **generic** i.i.d. entries and then \"rotated\" to have some possible covariance structures. Numerical experiments for relatively small values of $n,p$ were conducted to support the theoretical assessment.\n\n**Strong points**: The authors provided a solid contribution to the theoretical understanding of high-dimensional (over-parameterized) machine learning systems that are of growing interest today. The technical tool of the CLT for linear spectral statistics introduced here is popular in RMT literature and may be of independent interest to the machine learning community. To the best of my knowledge, there are very few results on the second-order fluctuations of the prediction, one possibly relevant paper is \"Asymptotic normality and confidence intervals for derivatives of 2-layers neural network in the random features model\" at NeurIPS 2020.\n\n**Weak points**: This article could be strengthened by summarizing more explicitly the lessons to be learned for practitioners.\n\n**Recommendation**: This is a good paper that made solid contributions to the theoretical understanding of high-dimensional least squares estimators and consequently, shed interesting light on the future design of more elaborate machine learning systems. I thus recommend it for publication at ICLR.\n\n**Detailed comments**: \n\n* Sec 1 introduction: \"However, the existing asymptotic results, which focus on the first order limit of the prediction risk, cannot exactly guarantee the more data hurt phenomenon\": it would be helpful to provide a more concrete illustrating example for the insufficiency of the first-order analysis, or perhaps simply refer to the discussion above Figure 1 below.\n* The x- and y-axes are hardly visible in Figure 1, and the same applies to other figures in this article as well.\n* below (1): is the independence between the entries of $\\mathbf{x}_i$ necessary, should this be stated here?\n* Theorem 4.3, 4.4 and 4.5: it would be helpful to comment here that only the case of **identity data covariance** is considered here, is the general covariance case easily follows, with just more complicated expressions, or there may be some technical challenge to master?\n* Since the theoretical results in the paper are \"universal\" with respect to the distribution of the entries of $\\mathbf{x}$, it would be good to provide numerical experiments on non-normal data to better illustrate the contribution of this work, or at least, to mention explicitly that experiments **on more general data distribution** are available in the Appendix.\n* In Figure 3, we observe that the statistic $T_{n,0}$ fits less well the theoretical prediction (at least compared to $T_n$ in Figure 2 or $T_{n,1}$ in Figure 3), could the authors provide any theoretical justification or intuition on this?\n\n\n**After rebuttal**:  I've read the authors' feedback and my score remains the same.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8_Mrnhrtoo", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the phenomenon of double descent, also referred to as \"more data hurts\", in high dimensional linear regression using the least square estimator.  In the same setup, previous sharp results were already established in the asymptotic regime. Non-asymptotic results are also known but are less precise. The authors of this paper try to provide a new type of results that fill the gap between the two regimes (asymptotic vs non-asymptotic). To do so they have managed to derive second order (CLT type) asymptotic results for different risks based on more refined random matrix theory results.\n\n#######################################################################\npros:\n\nAsymptotic confidence intervals for different prediction risks  are derived. These results seem new. One of the main applications of the main results is a better explanation of the more data hurts phenomenon. Indeed, using just first order asymptotic results we had to take both n and p to infinity and compare the ratios p/n. Using the finite-sample results in this paper we can now fix p (large enough) and see that, in the overparameterized regime, a larger n leads to a larger prediction risk. \n\n#######################################################################\ncons:\n\nWhile the statistical decomposition of the risk was already known, the novelty of the results in the present paper are only based on known results from random matrix theory which limits its theoretical contribution. Also, Section 4 needs more discussion. As a reader, I was felt abandoned at the end of Section 4, where the it just ended after stating the results. I think at this stage the authors should take the time to explain more their results and how they are different from previous ones. In particular by saying \"explicitly\" what happens when the sample size grows. Although that was clear from your introduction, but it is always good to draw conclusions for the reader after you state your results and remind your contributions.\n\n#######################################################################\nScore:\n\nThis paper is well written and the proofs seem sound to me. Overall, I think the present paper is marginally above the acceptance threshold because it seems like an incremental work over previous asymptotic results by using well established CLT results from random matrix theory.\n\nTypos:\n\n* In assumption (B1), did you mean $\\lambda_{\\min}$ instead of $\\lambda$?\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper derives CLT type results for the minimum $\ell_2$ norm least squares estimator allowing both n and p to grow.

Pros:
As one reviewer puts it: Asymptotic confidence intervals for different prediction risks are derived. These results seem new. 

Cons:
It's not clear what has been gained by having these results, other than having them.

Reasoning:
Staring at Figure 1 for a while, what jumps out is how little the CI matters. Unless $p\approx n$, the band is essentially uniform around the first-order result derived elsewhere. The claim the authors seem to make at the bottom of page 1 is that, "supposing I have 90 observations and 100 predictors, it may not be so bad to collect 8 more observations. Even though on average I'm worse off, perhaps not for my data?" The flip side of this argument is "why am I using min-norm OLS"? I think that the authors are making the wrong argument in this paper. The point of analyzing this problem is not to understand what happens when $p\approx n$ but to understand why $p \gg n$ is good, and thereby try to justify parameter explosion in deep learning. I should be looking at the left side of Figure 1, not the center. Even the language "more data hurt" is the wrong statement. The point isn't to show that collecting data is bad but to justify adding parameters. We should say "more parameters help". If the authors' proof technique added to the understanding in that case, then this paper would be more convincing. As is, I find it hard to overrule with the reviewers who appear to be mainly on the fence with little enthusiasm.

Decision: Reject