Spectral Multiplicity Entails Sample-wise Multiple Descent
Authors: Lin Chen
Song Mei
Venue: ICLR 2022 Submitted (2022)

Abstract: In this paper, we study the generalization risk of ridge and ridgeless linear regression. We assume that the data features follow a multivariate normal distribution and that the spectrum of the covariance matrix consists of a given set of eigenvalues of proportionally growing multiplicity. We characterize the limiting bias and variance when the dimension and the number of training samples tend to infinity proportionally. Exact formulae for the bias and variance are derived using the random matrix theory and convex Gaussian min-max theorem. Based on these formulae, we study the sample-wise multiple descent phenomenon of the generalization risk curve, i.e., with more data, the generalization risk can be non-monotone, and specifically, can increase and then decrease multiple times with more training data samples. We prove that sample-wise multiple descent occurs when the spectrum of the covariance matrix is highly ill-conditioned. We also present numerical results to confirm the values of the bias and variance predicted by our theory and illustrate the multiple descent of the generalization risk curve. Moreover, we theoretically show that the ridge estimator with optimal regularization can result in a monotone generalization risk curve and thereby eliminate multiple descent under some assumptions. 

Under review as a conference paper at ICLR 2022
SPECTRAL MULTIPLICITY ENTAILS MULTIPLE DESCENT
SAMPLE-WISE
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, study the generalization risk of ridge and ridgeless linear regres- sion. We assume that the data features follow a multivariate normal distribution and that the spectrum of the covariance matrix consists of a given set of eigenval- ues of proportionally growing multiplicity. We characterize the limiting bias and variance when the dimension and the number of training samples tend to infinity proportionally. Exact formulae for the bias and variance are derived using the ran- dom matrix theory and convex Gaussian min-max theorem. Based these formu- lae, we study the sample-wise multiple descent phenomenon of the generalization risk curve, i.e., with more data, the generalization risk can be non-monotone, and specifically. can increase and then decrease multiple times with more training data samples. We prove that sample-wise multiple descent occurs when the spectrum of the covariance matrix is highly ill-conditioned. We also present numerical re- sults to confirm the values of the bias and variance predicted by our theory and illustrate the multiple descent of the generalization risk curve. Moreover, we the- oretically show that the ridge estimator with optimal regularization can result in a monotone generalization risk curve and thereby eliminate multiple descent under some assumptions.
INTRODUCTION
The double/multiple descent phenomenon attracted recent research attention due to (Belkin et al., 2019). This line of work focuses on the parameter-wise double/multiple descent phenomenon of the risk curve (Bartlett et al., 2020; Tsigler& & Bartlett, 2020; Belkin et al., 2019; 2020; Chen et al., 2020a; Liang et al., 2020; Advani al., 2020; Bös & Opper, 1998; Krogh & Hertz, 1992; Le Cun al. 1991; Mei & Montanari, 2019; Opper et al., 1990; Vallet et al., 1989; Watkin et al., 1993). The classical learning theory shows that when the number of parameters (which reflects the model com- plexity) increases, the test error (generalization risk) first decreases due to more fitting power, and then increases due to overfitting. The generalization risk attains a peak at the interpolation threshold (the number of parameters equals the number of data points so that the model interpolates the data). This results a U-shaped risk curve if we plot the test error versus the number of parameters. The double descent risk curve posits that the risk will decrease (again) if one further increases the model complexity beyond the interpolation threshold (Belkin et al., 2019). Thus there is a second descent in addition the first one in the U-shaped stage of the curve. Belkin al. (2019) presented empiri- cal results and showed the existence of such double descent behavior in the random Fourier features model, the fully connected neural network, and the random forest model. Prior to (Belkin et al., 2019), earlier studies of the shape and features of the risk curve in a number of contexts include (Vallet et al., 1989; Opper et al., 1990; Le Cun al., 1991; Krogh Hertz, 1992; Bös & Opper, 1998; Watkin et al., 1993; Advani et al., 2020). Loog et al. (2020) presented a prehistory of the double descent phenomenon. Belkin et (2020) proved the double descent curve the Gaussian model and the Fourier series model. Mei & Montanari (2019) theoretically established the double descent curve of the random features regression. Bartlett et al. (2020); Tsigler & Bartlett (2020) characterized the conditions for ridgeless and ridge linear regression problems, respectively, under which the minimum norm interpolants achieve near-optimal generalization risk. Liang et al. (2020) showed that the test error of the minimum-nowe interpolator of data in reproducing kernel Hilbert space is upper bounded by a multiple descent curve as the model complexity increases. They also presented numerical result supporting that the test error itself exhibits multiple descent curve.

---

Under review as a conference paper at ICLR 2022
Chen et al. (2020a) proved that the multiple descent curve does exist for the minimum- norm inter- polator in linear regression and that the curve can be even designed.
Following the parameter-win wise double descent, research interest extended to epoch-wise and sample- wise double descent (Nakkiran et al., 2020; Chen et al., 2020b; Min et al., 2021; Nakkiran et al,, 2021). Nakkiran et al. (2020) observed from their numerical result that the generalization risk periences a double descent as one keeps the model size fixed and increases the training time. They called this observation epoch-wise double descent. Nakkiran et al. (2020) also noted sample-wise non-monotonicity, which means that more data can hurt generalization. Nakkiran et al. (2021) proved that for isotropic features, optimally regularized ridge regression yields a monotonic gener- alization risk curve with more samples. Nakkiran et al. (2021) also showed that if the features are formed by projecting high-dimensional isotropic data to random low-dimensional space (say, d- dimensional), the optimally regularized ridge regression has a monotonic generalization risk curve with increasing (the model size). Sample-wise non-monotonicity and double descent was also observed in (Chen et al., 2020b; Min et al., 2021) in adversarially trained models. C oomared to (Wu & Xu, 2020; ichi Amari et al., 2021; Dobriban & Wager, 2018; Richards et al., 2021), in what follows, we highlight tion is providing a rigorous proof for the existence of sample- wise (test error vs. the number of training samples) double and multiple descent in linear regression. However, (Richards et al., 2021) only mentioned parameter-wise double descent (test error vs. model capacity) in their related work. (ichi Amari et al., 2021) only mentioned epoch-wise (test error vs. training time) double descent in Appendix A.2. Neither (Richards et al.. 2021) nor (ichi Amari et al., 2021) mentioned multiple descent. Second, we made and theoretically proved the observation that an ill-conditioned covari- ance matrix is sufficient condition for the existence of sample- wise multiple descent. To the best of our knowledge, our work the first paper that pointed this out. Third, we solved the Stieltjes transform explicitly and derived explicit formulae for the risk and variance in our setup. In addition, we also provided rigorous treatment to the ridgeless setting and also obtained explicit formulae for it. Fourth, there is another difference between our paper and the papers that the reviewer mentioned. (Wu & Xu, 2020; ichi Amari ct al., 2021; Dobriban & Wager, 2018; Richards et al., 2021) assumed the prior. In our paper, do not assume
contributions and the differences from them. First, our major contribu-
prior on the true linear model and takes expectation a prior on the true linear model and our risk does not take the expectation over a random true linear model.
In the setting of generally anisotropic features, this paper gives an asymptotic characterization of the generalization risk curve with more samples. The asymptotic regime is an approximation for large n, d and can also shed light on practical machine learning problems. We first introduce our problem setup.
1.1 PROBLEM SETUP
Let Σ E Rdxd be a positive semi-definite matrix which is termed the covari- ance matrix, and let 0" E IRd. The eigenvalues of Σ are Ai...., Am with multiplicity di....,d dm. respectively. We have d = Σmm d, Assume that Ai. Am are fixed, distinct, all positive, and do not depend on d (i.e., for all d, the eigenvalue of E are always Ai...., dm). We assume the following data distribution D for (z. y) E Id x R:
Data Distribution
x N(O,E), y= +c,
where x and are independent and e ~ (10 o²). In practice, there are natural random variables x that satisfy our assumption. For example, assume that we want to use machine to measure the length of several objects and use machine B to measure their temperature. The measured lengths and temperatures follow an i.i.d. Gaussian distribution. However, the variance of measurement of machine A is different from that of machine B. Then we consider the random vector formed by the .......6. fn), where 4 and f; are the length and temperature of object i, respectively. This results in block-structured covariance matrix. When we measure more objects, the size of the covariance matrix tends to infinity. Second, the motivation came from (Nakkiran et al., 2021). (Nakkiran al., 2021) observed empirically in their Figure 2 that when the covariance matrix has a block structure (specifically, there are only two fixed different eigenvalues 10 and 1), the expected excess risk exhibits multiple descent. We quantitatively studied this observation and
measurements x (4,,..., Ln,
2

---

Under review as a conference paper at ICLR 2022
obtained the related formulae. The excess risk of estimator A R is given by
R(0) - EugyDD [v-- T=o)²² -
Assume that the training data {(zi, Wt) C IRd x IR is drawn i..dd from D. Write
1/1
X
E Ruxd y
E R
(I)
I
yn
We have y = X0 + E, where E ~ (O, I2))
Ridge Estimator and Minimum-Norm Estimator
Definition 1 (Ridge estimator). The ridge estimator 0x,na IR (A 0) solves the following minimization problem
min
|x0 y12 + 1
6E
Definition 2 (Minimum-norm estimator). The minimum-norm estimator (also known as the ridge-
less estimator) 0 E IRd solves the following minimization problem
min
|l1l such that ||X yll2
min |
y112
BERd
BER
We are interested in the expected excess risk of fx which is given by
Rxnd E (0xna))
The expectation is taken over the randomness of the training data {(r,, y.))==
Asymptotic Regime Let II, E Raxd be the orthogonal projection to the eigenspace of A4. This paper focuses on the asymptotic behavior of the expected excess risk of @x,,d where n, de - +00, d:/n + 24 (zz fixed positive constant), and ||I,,0112 ll тι- In other words, interested
lim
Rxn.d.
d
||TT, 11 -
1.2 OUR CONTRIBUTIONS
Our contributions are summarized as follows.
1. We obtain the formulae for the limiting bias and variance, and thereby the limiting risk. We use two methods to obtain these formulae. Specifically, we obtain the limiting bias and variance by solving the Stieltjes transform and computing its derivatives and antideriva- tives. We also use convex Gaussian min-max theorem (CGMT) (Thrampoulidis et al., 2015) to compute the limiting variance. The advantage the CGMT method that is more mathematically tractable for the ridgeless estimator. Through the CGMT approach, we obtain a closed-form formula for the variance in the underparameterized regime and simplify the formula for the variance in the overparameterized regime. Moreover, based on the simplified formula, we deduce a closed-form expression for the variance if the covari- ance matrix of the data distribution has different eigenvalues.
2. We find and theoretically prove that sample-wise multiple descent happens when the co- variance matrix has eigenvalues of very different orders of magnitude (thus the covariance matrix is highly ill-conditioned).
3. We show that if the true linear model 0* satisfies ||II,0*|2 / de optimal regulariza-
tion (i.c., pick À that minimizes the generalization risk of 0x,..)) results monotone generalization risk curve-in other words, with optimal regularization, data samples
3

---

Under review as a conference paper at ICLR 2022
always improve generalization. Thus there is sample-wise double or multiple descent. This provides a theoretical proof of a phenomenon observed (Nakkiran et al., 2021) that optimal regularization can mitigate double descent for anisotropic data. Note that without regularization, there will be a blow-up in expected excess risk when n = d (the linear model exactly interpolates the data) and therefore, there is no samplewise descent across the under- and over-parameterized regimes.
PRELIMINARIES
Notation Write [m] for (1, m... Let i denote the imaginary unit. a E I² and R a positive semidefinite matrix, write | - Vx Σx. For a vector æ, let ||-I|, and Il-I12 denote the e and (2 norm, respectively. Let ( denote the Hadamard (entry-wise) product between vectors. Write - and || IIa for the spectral matrix norm and Frobenius matrix norm, respectively, Let & denotes the Loewner order. For two square matrices and B of the same size, write x B if B A is positive semidefinite. Define spec (A) as the set of all eigenvalues of A. Let (d)
{A E Raxd
AAT A A = Ia} denote the set of d d orthogonal matrices. Define Sd &
{or E Rd |||||| = r). Denote almost sure convergence by ",, and convergence in probability plim
and P.
Ridge Estimator and Minimum-Norm Estimator We begin with the equivalent characteriza- tions of the ridge and minimum- norm estimator. An equivalent characterization of the ridge estima- tor nd is
0x,n. (xTx + x X (AmI, + XXT)= y
(2)
The second equality in Equation (2) is because of the Mheeman--Morison-Wooonn proof of Equation (2) can be found in (Tsigler & Bartlett, 2020).
formula. A
An equivalent definition of the minimum-norm estimator du,n,d is that d solves the following minimization problem
min ||0|] such that X X0 = x BER
Thus we have
B (x x)²+ x-= (XxT)+
where A+ denotes the pseudo-inverse of A. The second and third equalities are because of the identity X+ = xx+ X = x (XxT)* The minimum- estimator is the limit of the ridge estimator nn as + 0+:
0 = lim dx X-
This is limx-so T
(nnt, + XXX) identity
because of the
limx (xT X + AnTa) -1 xT
Bias-Varinn
Variance Decomposition of Expected Excess Risk estimator 0 equals the norm of 0*:
We first show that the excess risk of an
R(0)= (2 (y To 0)² -(y (y-xxTo TTo) Fy (x (0- (0--)))² 0))²|
(0 - 0) T > (0+ - -0] = |100 - -0133
For the ridge estimator, the expected excess risk is
ax,d,n
=E |110* x
+ (XT) + +
=E [I[(Ea - XT (n,, + XXT)- - (n>Ln + XX XX
-E [II(4a - Xx - XX -xx))'xx0011 x)0 + E (ndln + +XX
xx - + +o2Etr -E [I[(La - x (nA,, - -
(EXX, + x
Bx.da Vx.dn-
(3)

---

dpï Then J is given by Under review as a conference paper at ICLR 2022
For the minimum-nomn estimator, the expected excess risk is
Ro.d,n = E |10 - x + +
E [|(T= [[ x)) 0r x=11
EE' |I(la - (11a-xxx]] x) 0 011(3]
+ E X E {
=E [I(Ta x x) 0 11 + o E (xx) Σx*]
A Bo,d,n + Vo,d.n
We call dx, and Bu,d,n the bias term, and call dn, and Vo.d.n the variance term. The bias and variance for the minimum-norm estimator are the limit of their counterpart for the ridge estimator Vo,d.. (this can be shown by
À + 0+, i.e., limx->o Bx.d.n Bo,d. and limx-o+ V2,d,n Lebesgue's 's dominated convergence theorem, see our proof in Lemma and Lemma 6, respectively).
3
MAIN RESULTS
3.1 LIMITING RISK AND SAMPLE-WISE MULTIPLE DESCENT
We study the limiting bias and variance for linear regression problem in which the data distribution follows a multivariate normal distribution, the spectrum of the covariance matrix exhibits block structure and tends to discrete distribution. Thanks to the random matrix theory, obtain the formulae (presented in Theorem 1) for the limiting bias and variance, and thereby the total risk.
We use two methods to obtain these formulac. The first method is through the Stieltjes transform of the matrix 1 X The central quantity for computing the limiting bias and variance through the first method is the solution p" the optimization problem Equation (5) in Item of of Theorem 1. Item 1 guarantees the existence of a solution and determines its optimality condition Equation (6). Item 2 computes the Jacobian matrix of p" with respect A; and provides a closed-form formula to compute the Jacobian matrix. Equation (9) and Equation (10) in Item give the formulae for the limiting bias obtained by the first method. Equation (11) and Equation (12) give the limiting variance.
The second method is through the convex Gaussian min-max theorem (CGMT) (Thrampoulidis et al., 2015). The central quantity is the solution r" to the minimax optimization problem Equa- tion (8) in Item 3. We use CGMT obtain the formulae for the variance term. They are presented in Equation (13) and Equation (14) in Item 4.
Theorem 1. The following statements hold:
1. There exists a minimizer p E TR that solves
inf PER
log
x
Xipj
+
Σ
Pj
Pj (log 23
+11)
(5)
j=1
j=1
The minimizer p" satisfies
A X E A1p3
+
0,
Vi E [m].
Pi
2. Let p² E m be minimizer of Equation (5) and J
R mm be the Jacobian
8x
matrix Jij any
== (diag (A) + (A + T p²) Im (z 1 pa=pp)\TT> (p=="")p" - diag (p*))
and the matrix (diag (2) + (2 T p²) Im (z p²) AT) is always invertible.
3. Define r = (ri,...,,T.) Fm)) A =
Am), and
0(r,, A) 2r,
1+ Σ ?? 2r Σ
Ver +
Σ
1 r Xv?
Ne
kE|m]
[m(m]
1E(m)
5

---

Under review as a conference paper at ICLR 2022
For any K₁ 2 2 and Kv 2 2 (2+ we have
max min OSTiSk, S.
((,,,,)
min max OSriSK, ogrisk,
(rr, X) max min (r min max (T,, A)
7.20 r:20
2,20 2,
and the above optimization problem has solution.
4. Let r (ri....., m solve Equation (8). Define q (ni/21
nen )m) and view
A = (AI,..., )m) as a column vector. The limiting bias is given by
lim n.d: +000
Bx.di = T 100p++JXX J2022,
(9)
d
||11, 2-
lim -.d
Bo,d,n
lim q (AOp*+JJ x-00+
(10)
d,/n-z
||1,001 |11,001,- 2-
The limiting variance is given by
Vx o 2 (0" +JA
2
lim n.d: +000
(11)
(A+) pr)²
d: /n/n=z
10R (0 + (
lim n.d, +400
Vo.dn = 0² lim A-10+
(12)
(1+) p²)²
d dn/++2:
m
lim 1000 d
Vx,dn 0²
2
(13)
i=1
lim Vo,d, 0²
lim X-+0+
(14)
d: d=/n+
Figure 1 illustrates the theoretical and numerical values of the bias, variance, and total risk. We observe a triple descent in Figure la where the covariance matrix has three blocks, and a quadruple descent in Figure 1b where the covariance has four blocks. In the three-block example, we set X >> A >> \ (A1 1, Àg 100, As 1000), In the four-block example, we set X > A > X À (A) = 1, = 100, Ag = 10 A = 10"). For the values of other parameters, please refer to the caption of Figure Our findings provide an explanation for the occurrence of sample-wise multiple descent: it occurs when the covariance matrix is highly ill-conditioned. Moreover, we find that the generalization risk curve is continuous in ridge regression (A while blows up at n in ridgeless regression (A = 0). We can see the singularity (at n = d = 200) of the ridgeless generalization risk curve in Figure 2a.
Following Theorem 1, we focus on the variance in the ridgeless case (A = 0) and further study the expressions in Equation (13) and Equation (14). We find that the variance exhibits sharply different behaviors in the underparamettrrzze and overparameterized regimes. Recall that we will let n, d, >> +oo and keep d//n - 2,. Then d/n Σieim) 2, If lim d/n = Eielm) 2i > 1, we are in the underparameterized regime. this regime, the bias vanishes and therefore the risk equals the variance. If lim d/n < 1, we are in the overparameterized regime.
Theorem 2. Ifd/n + Eie(m) 24 > 1 and r (ri..... rmm) solves
min 20
subject to
Σ 4E(mJ
+1+1= Σ VeTii
sE(m]
SE [m]
then have an optimality condition for r":
r
X;
V - 13 A r3
1.j E [m].
(15)
rj
/2j

---

Under review as a conference paper at ICLR 2022
200
1002
Verb 500
150
Med
Expocizd Rick
Expicadd
6001
-0811
200
50
100
150
203
250
302
50
100
150
200
250
300
Number of Somples
Number of Samples
(a) Sample-wise Triple Descent
(b) Sample-wisc quadruple de-
scent
Figure 1: Figure la and Figure lb illustrate sample-wist wise triple and quadruple descent, respectively.
We specify the parameters that we used follows. Figure la: There are 3 blocks. We set di 60
d2 = d3 40, A = 1, A2 = 100, A = 1000, | O' 2|2 = || ||2 = 0.1 and ||T200 I|, 1. The
36, 80, 136, respectively. Figure lb: There are 4 blocks. We set dj d2 = d3 = d1 = 40, A = L, A2 = 100, A = 10a, a 107, and |1I,0'1| = 0.01(i E [4]). The four descents occur around n 1,37, 80, 120, 150, respectively. In the legend, the items starting with "T." are theoretical values predicted by Theorem 1. Items starting with "N." are numerical values. We plot two curves for the variance in Figure la. "T. Varl" is obtained by Equation (11) of Theorem I. "T. Var2" is obtained by Equation (13).
three descents occur at
where A VEre(m) r72 + Moreover, we have limn,d:-4e d:0+ Vo,d,n o² limx-s+ Ei r²2.
d
If Ifd/n Eielml 2i 1, then we have
0² Eve(m) 24
lim n. +000
Vo,dn
1 1 Eie(m)
de n
Corollary 1. If m 1 and d/n + 21 > 1, we have lim Vo,d,n = 0² =1-
d,/n-22.
Proof. In the case m 1, we have rf solves min., 20 J r subject to V Vziri. The equality constraint gives r - Then by Theorem 2, the limiting variance is 0 o²
In Theorem 2, we find that in the underparameterizzed regime, r" solves an equality-constrained minimization problem. In the proof of Theorem we see that the equality constraint is feasible in the underparameterrzed regime but infeasible in the overparameterized regime. Moreover, we present an optimality condition for r', which will be used Theorem (m 2) case. If the data distribution is isotropic (which means that the covariance matrix is scalar matrix), Collorary shows that the limiting variance is o² T which agrees with (Hastie et al., 2019, Theorem 1).
study the two-block
In the overparameterized regime, however, we find that the limiting variance does not depend on the spectrum (Ai,..., Am Jf of the covariance matrix and only depends on the noise intensity a and the ratios lim de/n.. This agrees with (Hastie et al., 2019, Proposition 2).
In Theorem we study the case m and present concrete closed-form formula for the limiting variance in the overparameterized regime. Recall that the limiting variance in the underparameter-
ized regime has a closed-form 0² Engim #t_ I- zt
for general m, as shown in Theorem 2.
Theorem 3. Ifm 2 and d/n 21 22 1, we have
92 +1
lim Vo.dn 0²
n.d: +000
q²(21 - 1) + 29
21
22
+
22
d:/n-zz

---

Under review as a conference paper at ICLR 2022
Varl
20
1.0
100
300
400
Number ammlees
(a)
(b)
Figure 2: Figure 2a: We illustrate sample-wise triple descent of the variance term in ridgeless regression (A 0). There are 2 blocks. We set d1 = 80 d2 = 120, ê = and X2 = 100. The two descents occur around n 125, 200, respectively. In the legend, "T. Var" denotes the theoretical values predicted by Theorem 3. "N. Var" denotes the numerical values. Figure 2b: Function f()) defined in Equation (17) with
where
A1 (21
X2 22) + (A1 (31 - 1) A2 -2)) 22112
(16)
2 22
We illustrate the theoretical values predicted by Theorem (overparameterized regime) and Theo- rem 2 (underparameterrized regime) in Figure 2a and compare the numerical values.
Corollary (Triple descent in the two-block case), Assume 2, 22, d/n + 221. and X2/>1 = g. Define fo(() = lim,,d,-He Vo,d, We have
d//n+2
<<l,
I-C
S(C)
lim Sp(C) e+++o
o²
2-
2
-1)
1 <<<<2 <2
(17)
<> 2
C-2
There exists Si, S2, S3; Ça and co such that for all e Co, we have (((Ci) 0, f((()) > 0, (((aa) < O, and (Ca) 0.
Proof. The case ( is already given in Theorem 2. In the sequel, assume 1. Define g in Equation (16). We have
+ V 45(e 1)2 4(e 1)2 (S- - 2) 2
2ç0
Recall Theorem 3, we get
2 +1)
202
fo(C) lim
Vo,d, d./n-2i
++00
( (
+ 1)2
(q2
+1)
(9+1)²
-2
9241
Direct calculation yields
2
{<1,
1-
lim fe()) g+
2
+
-1)
1<s<2,
(-1
2-
(>2.
2
<<1,
g(C) A lim ((()) =
1<(<2,
++
(C-3(22)
2
2
{>2.
2-2
8

---

2 and A2 > Y1. Note that a larger Ç = lim d/n reflects a relatively smaller n. If (((() < 0, then fo(() decreases on neighborhood of ( and therefore the limiting variance increases with relatively larger n. As becomes relatively larger, we see an increasing stage, a decreasing stage, and finally an increasing stage order in the overparameterized regime (n d). When we further increase n and enter the underparameterized regime, we observe decreasing stage. We illustrate f()) in Figure 2b. In Figure 2b, we observe two singularities at Ç = and Ç 2. Under review as a conference paper at ICLR 2022
The function g( > 0f Ç E (V2,2) and have 9(5) < 0f v2 or 2. Pick {1 >
C2 /2 C3 > > Ça- Then we have g(()) < 0, ((2)) > 0, g(a)) < 0, and g((,) > 0. There
exists 20 such that for all & 2o. we have ((() < 0, fg((2) 0, fg < 0, and ((((a) < 0. D
Collorary 2 theoretically proves that there exists triple descent when
3.2 OPTIMAL REGULARIZZTION MONOTONIZES GENERALIZATION RISK CURVE
Recall the definition of the ridge estimator in Definition Since this subsection concerns sample- wise monotonicity, we add a subscript to X and (they are defined by Equation (1) in Section 1.1) to emphasize that they consist of data items. Therefore we write
1 θ nnd arg min lly, x, 110112
B n
In this subsection, under assumption, show that optimal regularization (i.e., pick À that min- imizes the generalization risk of (x, results in monotone generalization risk curve-in other words, with optimal regularization, more data always reduces the generalization risk. The assump-
tion is that ||11,0'12 v de i.e., the squared norm of the projection of 0 onto each eigenspace of the covariance matrix is proportional to the dimension of that eigenspace. (Nakkiran et al., 2021) showed by numerical results that optimal regularization can mitigate double descent for anisotropic data distribution. We give a partial theoretical proof of their observed phenomenon.
To ease the notation, reflects a relatively larger n (in the limit). Theorem 4 shows that with the optimal regularization, the limiting risk is an increasing function of 71,...> 7m-
7 A lim n/d d; rather than 2, lim d, /n in Theorem 4 because larger
Theorem (Optimal regularization). If
d2
|1,00 1l2 V d
(18)
then there exists a function g(7,, 7m) such that g(T2...., Ym) ) is increasing in every 7/ and
inf E Ex,.. |00n - 8-11 (fn.....mm)
lim n,d, +00 AS0 n/d4-%
CONCLUSION
We studied the generalization risk (test error) versus the number of training samples in ridgeless regression. Under the assumption that the data distribution is Gaussian and the spectrum distribu- tion of its covariance matrix converges to a discrete distribution, we obtained the exact formulae for the limiting bias and variance terms using the random matrix theory when the dimension and the number of training samples go to infinity in proportional manner. Using these formulae, we proved the sample-wise multiple descent phenomenon of the generalization risk Moreover theoretically showed that the ridge estimator with optimal regularization can result in a monotone generalization risk curve and thereby eliminate multiple descent under some assumptions.
REFERENCES
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High- dimessiimnsional dynamics of gener- alization error in neural networks. Neural Newworks, 132:428 446, 2020.

---

Under review as a conference paper at ICLR 2022
Zhi-Dong Bai and Yong- Qua Yin. Limit of the smallest eigenvalue of large dimensional sample covariance matrix. In Advances In Statistics, pp. 108-127. World Scientific, 2008.
Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(44)):00033330077 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical viri-variance trade-off. Proceedings of the National Academy of Sciences, 156(32):15849-155
2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 167::116 2020.
Siegfried Bös and Manfred Opper. Dynamics of batch training in perceptron. Journal of Physics A: Mathematical and General, 31(21):4835, 1998.
Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your generalization curve. arXiv preprint arXiv:2008.01036 2020a.
Lin Chen, Yifei Min. Mingrui Zhang, and Amin Karbasi. More data can expand the generalization gap between adversarially robust and standard models. In International Conference on Machine Learning, pp. 1670-1680. PMLR, 2020b.
Donald L Cohn, Measure theory. Springer, 2013.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 19X.vv9903008600 2019.
Shun ichi Amari, Jimmy Ba, Roger Baker Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization? In International Confer- ence on Learning Representations, 2021. URL https: /wpp//eveeeeeeeeeeeee/ee net forum? iid
Anders Krogh and John A Hertz. Generalization in a linear perceptron in the presence of noise. Journal of Physics A: Mathematical and General, 25(5):1135 135, 1992.
Yann Le Cun, Ido Kanter, and Sara Solla. Eigenvalues of covariance matrices: Application to neural-network learning. Physical Review Letters, 66(18):2396, 1991.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, pp. 2683-2711 PMLR, 2020.
Liese and K.J. Miescke. Statistical Decision Theory: Estimation, Testing, and Selection. Springer Series in Statistics. Springer New York, 2008. ISBN 9780387731940.
Marco Loog, Tom Viering, Alexander Mey, Jesse H Krijthe, and David MJ Tax. brief prehistory of double descent. Proceedings of the National Acudemy of Sciences, 117(2)): 10625-10626 2020.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications Pure and Applied Mathematics, 2019.
Yifei Min, Lin Chen, and Amin Karbasi. The curious of adversarially robust models: More data can help, double descend, or hurt generalization. Conference on Uncertainty in Artificial Intelligence, 2021.
10

---

Under review as a conference paper at ICLR 2022
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference on Learn- ing Representations, 2020. URL https: / www.review.eeeeeooe nett/forumm.d--lgglallee.
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. In International Conference on Learning Representations, 2021. URL
https:/
fltts::/opeereeee wpe.review.eeeeeeeeeeee /ttt///ouum////eeeeeeeeeeeeeat forum?id=7R8 Ed
M Opper, Kinzel, J Kleinz, and Nehl. On the ability of the optimal perceptron to generalise. Journal of Physics A: Mathematical and General, 23(11), 1990.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regres- sion under general source condition. International Conference on Artificial Intelligence and Statistics, pp. 3889-3887 PMLR, 2021.
Walter Rudin. Principles of mathematical analysis. New York, NY: McGraw-Hill, Inc., 3 edition, 1976.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. Proceedings of Machine Learning Research, 40:1683-1709, 2015.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
FF Vallet, J-G Cailton, and Ph Refregier. Linear and nonlinear extension of the pseudo-inverse solu- tion for learning boolean functions. EPL (Europhysics Letters), 94):3115, 1989.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Timothy LH Watkin, Albrecht Rau, and Michael Bichl. The statistical mechanics of learning a rule. Reviews of Modern Physics, 65(2):499, 1993.
Denny Wu and Ji Xu. On the optimal weighted 4.2 regularization overparameterized linear re- gression. arXiv preprint 2rXiv:2006.05880, 2020.

---

Under review as a conference paper at ICLR 2022
Notation
Comments
Σ PAP
Raxd O(d) Raxd Rd Roxd Rdxn
Covariance matrix of data
A (di, Amtdm)
& lr
X = ZT 1/2 = (I1,..., kn)
(10 Σ)
Z (Zz,... 7m
Z; Ruxd, Each entry follows N(0, 1).
Table 1: Notation
A EIGENDECOMPOSITTIO AND MORE NOTATION
Write Σ PAPT, where an orthogonal matrix and = diag (di Am E Rdxd diagonal matrix. Write A_ min X; and X max4e[m] As We can generate I1...... from standard normal random vector 24 (0, La) by setting I; PA1/22, Therefore, if E R2d ,we get
(
x = F1
In = 1/2 21
2n ) = PA
Take the transpose gives X ATA Note that every entry of Z Rdx= follows i..d (0 1). Write Z in a row-partitionel form
Z
7
ZT
where Z4 R_xd, Write P in column-pariitioned form
P P=
Pm. )
where P. IRdxd: Recall that II, E _add denotes the orthogonal projection to the eigenspace of d5. We have II; = P,P.T Define O' A p and write it in row-partitioned form
PTT 0
0
=
(19)
P. 0
0'
where 0f E Rdd Then |00/112 ||pT7 0-11,
||I,,0 112 We summarize part of the |...T 0011,
notation above in Table
B BIAS AND VARIANCE UNDER EICENDECOMPOSITION
Lemma 1 characterizes the smallest and largest eigenvalue of ZTz (if nz/d + < 1) and Z2 (if d n/d + 1). Recall that we study the asymptotic regime d./n n Therefore Σsc(m 25
Lemma ((Bai & Yin, 2008, Theorem 2)). Let Z E dd be a random matrix whose entries are i.dd (00, 1) random variables. As n. d +00, n/d - y (0, we have
TTZ
7 %
lim Amio
(1 vr)² lim Amax
= -1+ 2
d
d
almost surely. If E (1, as n, d + toc, 12/d + we have
22
(1 v//7)² lim Amaa
1ZZ
=(1 (1+ v1/T7)
lim Amin
n
almost surely.
12

---

Under review as a conference paper at ICLR 2022
Lemma 2 (Corollary 5.35 (Vershynin, 2010)). Let A be N matrix whose entries in- dependent standard normal random variables. Then for every t 2 0, with probability at least 1 2 2exp (-t²/2)
one has
VN vn 1 Smin (A) S Smax A) S V vn 1,
where 8min (m) and maa (A) are the smallest and largest singular value of A. Lemma 3. Let E Rd be a random matrix whose entries are i.id. NO, 1) random variables, where d d(n) satisfies lim,-ro d(n) 7.- There exists universal positive constants C1 C2, such that for all N, we have
1 0 Ci < 11
1
- (Z) S
- max (2) < C2.
Proof. Since d(n)) with loss of generality, assume n/d 7 E (0, Take t = invñ Lemma 2, where
2 - 1) 0. With probability at least 1 - -//// we have
vd vn ci v S Smin (2) S 8max (2) Vd v
Therefore, we deduce
(V - 1-0 01 1 miau (2) S smax (Z) <
( d (V
(
Define C1 = ( 1) > 0 and C2 = ( +1)+
Then there exists universal constant N1
such that for all N1, with probability at least -2 oin/2 we have
1
1
0c C1 < minn (2) S max (Z) < C2.
Define event En = [C1 < 1
min (Z) < 1 max (Z) < C2) Then we have (r(En) S 2e cd/n//
Since En21 Pr {En} < 2n>1 2e -2nn/2 oc, then the probability that infinitely many of En
occur i.e..
Pr lim En =0.
Therefore, there exists a universal constant N₂ such that for all n > N₂, E,, does not happen, in other words,
1 sm (Z) S 0 Ci
1 -2 mmx (2) C2
n
holds.
Lemma 4. Let Z E IRdxn be random matrix whose entries are i.i.d. N 1) random variables. and let p be a fixed positive integer which viewed as a constant and hidden in S. If n. x we have Et (ZZ")= x n², Er (ZZT)² n2, and E 12112 S np/2
Proof. We have
Etr [ZZ = =E
Σ (EId]JE[M]]
E2iy nd = n2?
27
Write Z
where 2; E R and 24 I.). We have E (2, (2T22;) E 1112il6
2/
n(n + 2). For i * j. we deduce E (2] 2,)2²² = E (122ll2 |25 uT TT)² where u, v ~ Unif (Sn-1)
and || || u, are independent. Then we get
(,) (||2a)) || s. s,)² E (s. 8,)² = n''Eu, = nn. n
= n.
13

---

Under review as a conference paper at ICLR 2022
As result, we have
Etr (ZZ (zzT)² 2 = =B =B 11
Σ E E 2/) dn(n + 2) + (d - -d) x
By (Vershynin, 2018), there exists a universal constant C > 0 such that for any t > 0,
P P(1Z]l, > C (Vī+ vd+t)} 20- Define K C V vd) Then we have
P 1 > K +1) 2e 2/
(20)
Recall l((2) -000 x=-1e a--le-ddr. Setting t CV ū in the equation below yields
- tm dt 2 - du = -r (2) x 1.
Then we can bound the following integral
111i 2 t pt dt
K
(11111 2 + t p (t KY de
e/c2 (t+ K)P-1 dt
e -// (101 + kP- dt
-1100 1- + kP-1 100 e-P10² dt
En
where the first inequality is because of Equation (20). We are in a position to bound E 2
E 2
00
P PIIZI 2 u} du
P | 2 f) pt dt
K
P 2( ž t) pt dt ( IP 1111211 t) ptP-1
Snp/2 + (p-1)/2
Snp/2
where the first inequality is because
K
P (12112 t) p f#t pf--1 KPP S np12
Lemma 5. The following equation for the bias term Bx, (defined in Equation (3)) holds
Bx,d
=E
2/2
Ia
11/2 (ndI, TT AZ)
Z ZT 1/2 0'133
(21)
-1
=R
||A
Ta
A1/2 A1/2 nd
0' 1
(22)
Moreover, we have [Bx S 110* and limx-so1 Bxda Bo,d,.- For all sufficiently large n and such that n/ + - E (0, we have I d bounded and uniformly equicontinuous with respect (0, oc).
Bxrd S -10 Therefore, {Bx,aa) } is uniformly
ax
14

---

Under review as a conference paper at ICLR 2022
Proof. Introduce the shorthand notation M = Al/2ZZ A//2 B A= La + 2 M E Raxd,
N nhd, + Z T AZ E R= and Q L2 AA/-NN----- -iTA--ZTA - Rdddd Because
x (nNn + XXXX = PA'/22 (nd + +zAA2) AT
we have
Bx.d =B (11a PA Z (nA1, + AZ) - 2 AT12PTTT y0 10 PPAP
=E 1////2 - (ndt, + - AZ) 22/2 0112]
E
|IAV2Q011
Using the Sherman-Morrison- -Woobbrro formula yields
1
1
1 - 1 zZ A12) -1
N-1
I
Z 1/2
[
1
nd
(nA)²
nd
1
In TTA
A1/2)
11/22
nd
1
(n2- Z A1/2 M)
(23)
nd
It follows that
Q
= la
=Ia 1 (In T (nAla M) 11/27 z A/2
nd
ld nd
M
(I2 (nNl + +M)- M)
M
=Id
[Ia (nAla + M) (nAIa + M - ndla))
nd
la M (ndla + +M)
-1 la + nd
M
=A 1
Therefore, deduce
Bx,d = E ||A//2
la+
_ M) nd
1
0'113
=E 11 1013
Because |||//|| S and (Ia A/1 T A 1/2 -1
S 1, we have
| 1/2 A 0 - | 11 = -10 12
Therefore [Bx,, S 100 11001 Moreover, by the dominated convergence theorem,
lim Bx. = Bo.d,n A
We compute the derivative of -1:
dA-1 dA -
dA
-A-2
dA
nd²
The matrix M A1/2ZZT 4/2
E Rdxd is positive semidefinite and its d - n smallest eigenvalues are zeros. Its non-zero eigenvalues are the same as the non-zero eigenvalues of z AZ Because all eigenvalues of zTAZ AZ are positive almost surely, the spectrum of M consists of d zeros and the n
15

---

Under review as a conference paper at ICLR 2022
spectrum of Alaz, A z
We study the range of the spectrum of Al
Because x_ 2 5
A
x
n we deduce
n
Z ZTAZ AZ
2
A_ (1 v17) 2
Amin
A-Amin
(24)
11
AZ
2
[+ v1/7) 2
Amax
S Am
+ }
(25)
T1
Define L1 = A_mni
z and La = X4
We get lim L =
n/d-n<l
d_ - 11/11/)
2
lim +oo Le = 2+ (1+ v1/7) 2 n/d-t<1
and
AZ
spec
S [L1, L2]
n
We bound || A - 8112
M
M -3
MA 31
=n
la +
n
nd
=n
max
&Espec af
(1 + s/X)
-11
max
.E <E(UUsspec AT n
(1+ 8/A)
max sEspec 2 ZTAZ ) (1 1+8// 8/A)
g.
Sn max 1E(1n,12
(1 + x/2)
We compute dA 11111/2-110 1-
d
d AA
dA
nx² TT
AA- -M 0'
na² (A~20))* T +M-A-+ (1-10)
Next, we bound
|1/2 A 0 11]]
d
Bx,d
d
||MA--AA -AA- + AMA- 10111
<
|MM
2
AA- 10'1
n1
||MA-
3
AAA 11, 1001/
n
n2 ||MA~ -3 |1, AAA -1 || 110
(1 + 3/3)3 10012
2
max LE
where the last inequality is because | = ||A||2 S A_ S 1. Define f(s) (1+s/1)33-
Because f'(s) X9(2-25) the function is increasing [0, x/2] and decreasing on [A/2, +00). (A+s)+
16

---

Under review as a conference paper at ICLR 2022
If À < 2L1, we have
L
L6l11 (1 8/2)
max
3
(1 L1/AjS
It follows that
1 L
L1d
L1 (A L1)
1
X2
(1+ L1
(A+ L))
max xe
S
In
If X 2 2T,, we get
1 max
1
L
L2d
1 5
1 L1
X2 الما (1 + 8/A)
X2
(1+ L2/A)²
max xE(2L2,00)
(A + Ln)
3
2
L2
2f, < X < 2L2, we obtain
1
8
1
max
2 L
2
L
(1 + s/A)²
In all three cases, we show that
x max,e(Li,da)
[1+a/2}² S +.
It follows that
d da 11
S L1
100112
110112
|10'11 2
Amin
ZTZ
Amin
ZTz n
12
By Lemma 3, there exists a universal constant no such that for all >> no, one has
1.
Amin
21
Thus we conclude that
d ||A//
A-
A-
$10011
dA
We can exchange differentiation and expectation and get
d =
d ||A
Bx.d
E dA
10
dA
and
Bxdn
= E
1/4/2
A
100'
x 1011
dd
Lemma 6. The following equation for the variance term holds
VA,dn =0 (Anta 1 T A1/2) -1 A1/2212
=OPEIIAZ (Anl, + Z AZ) -1 112.
Moreover, for all sufficiently large n and d such that n/dd -> 7 F 1, we have Iim Vx.dn Vo.d,n [V S and 1 Vn S Therefore, (Vxa,) is uniformly bounded and uniformly 00).
equicontinuous with respect
Proof. As in the proof of Lemma 5, define M A1/22ZZA A/22 Rdxd and N AT Raxe, Recalling Σ PAP and X Z AT we have
VA,dmn Er [XEX] (nAL, + XXX)
=o tr [z A²
"ot [N-1 zT A
= |AZN-1 ?
17

---

Under review as a conference paper at ICLR 2022
Recalling Equation (23) yields
AZN-1
AZ -n--- A (nnlan M) A1/2%) M)-1A1/2
nX
1 1/ (Tn. M (nATa + My- A1/2%
nd
=/ (ndld + 1
Define R= A1/2 Bdd We get
(ndla + M) A 1/22 = (nAIa + RR R.
Notice that 0 < a < b, then al. + RR $ bla + RR.. We deduce
(bT + RR 2 - (aJa + RR R
2 = (b2 a²) La + 2 (b - a) RR 7 70.
Thus (bIa + RRT)² > (ala + RRT) )² which implies (bIa + RR -2 x (ola + RRT) -2
We
get
RT (bla + RR -2
R क R (ala + RR -2 R.
ir R (bla + RRT)
2 R) S Lr R (ala RR )
Let Ao (-) denote the smallest non-zero eigenvalue of a positive semidefinite matrix. We bound the Frobenius norm
(nAaa + MM A |
F
R (ndla + RRT) RR)
-r
lim R (ndla + RRT) -2 X-0+
Str
(R. RR)*
ur
(ZTAN AZ)
Sur (Z 2)
It follows that
|AZZN
1 1 A (nAla + -)- A 1/22
1
smn(aNl - -A- (z = tr (
If nn/d 7 < the matrix ZTZ is full-rank almost surely. Then, using the formula for the mean of inverse Wishart distribution, we have Etr =)== tr E [z z) tr (-
1. If
ne/d + 7 > 1, the matrix ZZ is full-rank almost surely. Similarly, we have E tr (ZZ (ZZT)+ E (ZZT) x 1. By the dominated convergence theorem, we have lim Vx,,n = Vo,d,n-
Moreover, Vx,d,n S TE FF|JAZN-11 1|2 S 1. -
Next we bound
ax V (0). Because
dN -N-1 N - 2, we deduce d
d JAAZN
d
d d
(N-1 ZJ AZZN-1) AN--ZTAZZN-T -2 TZT A2ZN
S..
On the other hand, we have
tr TT A2NN 99
tr (N-3/22) 3/2 A²ZN 3/2)
Sir Ur 3/3322 AZN 3/2
tr (z AZN-3)
Σ
(An + 8)3
.Espoc(Z" AZ)
18

---

Under review as a conference paper at ICLR 2022
Because the number of non-zero eigenvalues of Z" AZ equals rank (Z" AZZ d x get
d ||AZN-1|2 ntr (Z AZZZZ S n² max sEspec (ZT AZ) (An 5) sEspec
max
dd
M10 (A + s)s
If y < 1, the matrix AZ is full-rank almost surely. By Equation (24) and Equation (25) in the
proof of Lemma 5, there exists universal positive constants C₁ and C2 such that spec
A S
[C1, C2] for all sufficiently large and d such that n/d 7 < 1. If 1, the non-zero eigenvalues
of z" AZ and M are the same. The matrix M is full-rank almost surely. Thus spec
2 AZ
\(0} =
spec (M) Because y A - S yTy. y.
.M
x
1122Z A
y
ZZ n
y
ZZ y
n y
22 11
Amin
min m=00
min 8=0
2
min
Amin
n
A y
y
y
Similarly, we get
M
77%
mma
Amax
n
π
Therefore, there exists universal positive constants C1 and C2 such that
Z AZ
T
T 7
spec
[00
S
C2
n
n
7
Thus in both cases, have shown that there exists universal positive constants C₁ and C2 such that
Z AZ
{0} S Ciimmin
(TT2) Z
spec
C222max
n
n
n2
1zTz)
(2TZ). As result, we get
Define L1 = C1 Amin
and L2 = C2dmar
JAZN
112
S max SE L1 (A + s)²
dx
Define f(s)
[Ate)T Because (s(s) = [A+sJa
2-2s the function f is increasing on [0, A/2] and
decreasing on [2/2, +00). If 2 2L2 or X S 2L,, we get
8
L
L 1
max eE[Ln.Lal
()+s)3
(1+
(A+ (x+
L
2f < < 2L2, we get
8
max La) (A 8)
12 I
As result, for all sufficiently large n, we have
dx JAZN-
112
max LT
(A + s)
8
L
<
2
2 S
2 n
1,
where the final inequality is because of Lemma 3, We can exchange the expectation and differenti- ation and obtain
d
Vx,,n
FFF d dA
||AZN-1|3
dx
and
d
Vi,dn
d 50²B
|
212
$
dd
d
19

---

Under review as a conference paper at ICLR 2022
C LEMMAS ON STIELTJES TRANSFORM
Definition 3 (Stieltjes transform). The Stieltjes transform of a distribution with cumulative distri- bution function F' is defined by
1 sF(2) / X-2 dF(A H 32 0})
Lemma 7 (Theorem 4.3 (Bai & Silverstein, 2010)). Suppose that the entries of X CR are complex random variables that are independent for each n and identically distributed for all n and satisfy E [ Ern 13] 1. Also, assume that Tn diag(Ti,..... Tph Ti is real, and the empirical distribution function of {TI..... Tp) converges almost surely to probability distribution function as n + CC. The entries of both Xn and Tn may depend on n, which suppressed for brevity. Set Bn = An + X where X is the conjugate transpose of Xn, An is Hermitian, n satisfying FA,. + FA almost surely, where FAA is a distribution function (possibly defective) on the real line. Assume also that Xn. Tm, and An are independent. When p = p(n) with p/n + y > as n + 0o, then, almost surely, FB,, the empirical spectral distribution of the eigenvalues of Bn. converges vaguely. as n + oc, to (nonrandom) distribution function F, where for any = E C+ = CEECI C 3z 0}, Stieltees transform = =[(z) the unique solution C+ to the equation
{=
/
(T)
8 = SA 2 2
1 1 T8
where A is the Stielijes transform of FA. Lemma 8. If the functions fas 9a I + R satisfy fa(x) -9((z) - 0 uniformly - +oC, then lima-++00 (infzer f(x) - inf ((x) O.
Proof. Because fa(xx) Ia (x)x) + uniformly as a + +oc, we have for Vl > 0, there exists N N(e) such that for Ya > N(e) and Vx E I, it holds that (x) ga(x)) < Therefore, we get
9a (x) < fa(x) < (x) +c.
Thus we obtain
inf fa(x) S fa(x) < (x(r) +c *EI
inf ga()) (a(x) fa(z), zEl
which in turn implies
inf fa(x) S inf ga (x) + xEI
zel
inf 9a (I) - inf fa(x). ZET
zéi
follows that linfzer fa( infrer ga (x)) S e. In other words, we proved
lim
inf f(x) - inf
-inn-innggg ((()(()))
a0++00
ZEI
zer
Lemma 9, Define N Anla + Z AZ. Then we have
lim
tr tr 1N-
d
inf
log A Σ
dips
Σ 5E|ml
Ps 23
log
Pi
+
+ :1)
n.d: +00 d:/n-t2;
dA
PERT
24
FE[m)
(26)
1
N
2; log Pi +11 +1)) (27)
lim
log det
inf
log
x+ Σ
depi
Σ
Pi 12-24
n.d: ++00 n
12.
mERT
2,
d//n=1::
$E(m]
[Eim]
20

---

Under review as a conference paper at ICLR 2022
Proof. Proof of Equation (26). We apply Lemma 7 with An 0nxn- X, = = Raxd Tn = A, and Bn Z AZ. The distribution function of Onxn converges to 1,50 and its Stieltjes transform is (2 - = = The empirical distribution function Am is Hn,d, (t) Eie(m) d 11SA, Recall d:/n + 24- Thus
of (A.....,A
d./d - z//h K, where d/n - y y= EjE(m) øj. The empirical distribution function converges to (t) Eie(m] y Lesa, Then the empirical speetral distribution of the eigenvalues of 1 Z AZ converges vaguely to nonrandom distribution function F and its Stieltjes transform is
1 tr T1
1 Z
s(2) lim
AZ -2n
lim
tr (Z"AZ AZ -2nIn)
+ d//n=z,
d, n=
(this is because of (Bai & Silverstein, 2010, Theorem B.9)). By Lemma 7, s(z) is the unique solution in C+ to the equation
(TH(
s(2) = 8A
2
1 1
d; Ese(ml 1+):s(2)
which gives
s(x) 2
Σ ic(m)
Aizz
-1
+ Xe5(2)
We want to prove Equation (26) first The lefthand side of Equation (26) equals
lim tr (AnI, + 2 AZ)= =(-A).
n.d. d:/n=s;
Because the matrix AZ is positive semidefinite and thereby all of its cigenvalues are non- negative, its limiting spectral distribution supported on [0, oo). The Stieltjes transform s(x) of the limiting spectral distribution can be continuously extended to (-oo, 0). Therefore, for AA 0, s(-A) is the unique solution to the following equation
X
a(-1)
=1
(28)
{
We will verify that
m
m
inf PERT
log
+ X
Σ
App3
+
Σ
Pj
Pi + 1) 2j 20
dA
2j
j=1
satisfies Equation (28). Take minimizer pa of Equation (5). Using the envelope theorem yields
d inf dλ PER
Pi + 11) Ps 2, (log
log A
Xpp3
+
Σ
(29)
2j
x+ ΣØ=ı Asp3
j=1
Plugging the righthand side of Equation (29) into Equation (28), we get
1
\
A+
1.
m X
App]
Σ
2,p
Rewriting the above equation yields
m
A
m
Σ
App
X Th
App
It suffices to show that each summand on the lefthand side equals its counterpart on the righthand side
X
Aop;
A
X
Appj
21

---

Under review as a conference paper at ICLR 2022
We need to show
21 = =1
Pf
X+ X+ Ajp
which is equivalent to Equation (6) and therefore holds. Hence we have proved Equation (26).
Proof of Equation (27). We use denote the indices n, d,. Define
m
Pi + 11)
h(A) = inf P
log
A
+
Agps
+
Σ
Pj 2j flog
Zj
==1
j=1
First, we want to show that lim
(h(Ap)
- log Ao) 0. Define
+0
1 m
m
log Pi + 1 ))
(a( = log
1
Agps
+ +
Pj 2j
Ao j=l
2j
j=l
(p)) =
Pj Zj
log
Pi +1
Zj
The Hessian matrix of (p)) is diag
mm pm
which is positive definite since 2,y Ps > 0. There-
fore, q(p) is convex and the minimum of (()) on TET is attained at p = where 2 = (21,..., 2m O. Because lim 120 (p)
The minimum is inf R ((p) (z))
too, there ex- ists a universal constant K1 > ||z||2 > such that (p) > bx (x,(2) for all |lll|2 > K1. De- fine E = {p E R
|lell2 - K1 }. We have 2 E E inf 1xo (p) = inf perpeRy L,, (p), and inf q(p) = pnp g(p) 0. Therefore, we get
h(Ao)= - log Ào inf Lao (p) = inf Lxo (p) - inf g(p).
(30)
PERT
PEE
PEE
On E, there exists a universal constant K₂ > O such that EjE(ml Aip5 < K2. Thus on E, we deduce
K2
0 < (p) g(p) = log
1 1 Ao j=1
Σ
Aaps
< log
1+
Ao
The right-hand side log uniformly for p E. By Lemma 8, we get
+
K2
+ as Au + to0.
Thus lim
(1 - -(()) =
Au
lim inf Lxn (p) - inf ((p) =0. PER
Ao +00
PER
Recalling Equation (30) yields
lim (h(Aa) - log Ao) 0.
(31)
Au +00
Define (A) = n. log det N. ".. Second, we want to show lim, Sa(A) = h(A), where lim, means
We have La (A) (No) = 1h, Io (x))dx for VA, Ao > 0. follows that
limn,d;-+to
d//n=;
(A) M(A)) s (A)( M(A) + h(Aa) f20) + fa(A)) log An log do h(Ap)] $ (A(()) -((A) h((o)) (Ao) - (Ao))
log Aol + llog Ao - h(Ao)l
h Ao
(b(()) - M(AO)) + (la log Aol + flog Ao a(>o))
Taking lim sup, on both sides gives
lim sup (A) - A(A)) S limsup
f2(x)dd (M(A) - m(Ao))
+limsup (Ao) - llg Aol dol+llgg logg do - h(Aa))
Ao
(32)
22

---

Under review as a conference paper at ICLR 2022
Recall (A) tr and lima (A) h'(A) (this is exactly Equation (26)). Because
tr N = tr N < x and Sh da +00, by the dominated convergence theorem, we have
lim [" fa(x)dx= I h'(x)dr h(2) h(Ao).
follows that
lim sup L (x)dx (h(2) - n(Ao))) = lim I fo (x)dx (z)d (h(2) n(2o)) 0. (33)
Since
fa (Ao) λo log det (JoTn + - N TTAZZZ AZ log det (AoIa) = log det and the matrix
In + ZTAZ)
AZ
ndu
nAo 1 TT AZ is positive semidefinite, we have
fa(2o) log do 0.
We have
(a() - -log An
1 let
1 2 AZ
In +
n
ndo
1
d+ 'z' %
log det
det
In
+
ndo
d+
Z T 2
< log
+
Amax
An
Z Z
Amax
11
Then taking lim, we get
x+
T
lim sup (Aoo log Aol = lim sup (fa()o) - log 1o) 5
lim Amax
Ao
m
Xu
(34)
where the last inequality is because sup Amax
(1 v
x 1 by Lemma 1.
Using Equation (32), Equation (33) and Equation (34) gives
1
lim (A) A(A)) S
+ llog Au - h(>o)l
Ao
Then taking lim oo and recalling Equation (31) yields
lim (A) f(()) = lim (A) h(A)l 0.
Therefore, conclude lim,, fa( h(A).
Lemma 10. Define N AnI
TTAA AnI + Eie(m) 7.Z4..T. The following equation holds
lim n.d, +00 d
E
② 1
log det
N
inf PER
log
X Σ
Appt
+ Σ <c(m)
(p:
24 log
Ps
+11)
+11
0A n
n
0):
*E(ma)
(35)
lim u.d, +oc
E
0
log det
N
82
inf PERpi
log
X+ Σ
Aipi
+ Σ
Pi - 24
Pt + log 2i
Ox n
d//n-ts.
sE(m)
TE(m)
(36)
23

---

Under review as a conference paper at ICLR 2022
Proof. Proof of Equation (35). We use to denote the indices n, d; and use lim to denote
limn,d,--a Define fa()s) = 1 log det N
n fa = ad; in log det N1. and n
dz/n=s:
))
Pi + log
M(As) = inf PERT
log
A+
Aspi
+
Pi
21
iE [m]
*E
We have
N n
zTZ
In + 7 2 2) nd
log det
S
log det (Nn + x+
log + log det
n
n
n
n
By Lemma 3, there exists a universal constant C' > 0 such that for all sufficiently large
d z z S log + 2)
C)
log det
In +
n
nd
Therefore, we get
N S log (A + C)
log det
n
By the dominated convergence theorem and Lemma 9 (specifically, Equation (27)), obtain
lim fa (A:) = 1(As).
(37)
Because
θ 1
N
log det
[2 N 12,)
(Z Z.)
θA m
n
An
and E A Lr (Z 2:)] < +00, we can interchange the differentiation and the expectation and get
N
N
(a(Aa)
log det
=
log det 71
(38)
aA:
n
04:
Thus we deduce
E
log det
= E2
log det
S E
Oλ; log det
<
E
tr (z, 2;)
OA
0A;
An
By Lemma 4, Etr (Z, Z:)
n² and therefore
E
tr ( ZJ]
The function sequence
Amz
(f%) is uniformly bounded.
Then we want show that ($'} is uniformly equicontinuous by showing that (.") is uniformly bounded. Because
02
N tr [2,TN-2
Z Zz
2
log det
S
tr
ax3 n
n
n2a
Z Z:
27
and E nd
+00, we can interchange the differentiation and the expectation and
get
8 log det
N
a
0
N
82
N
E
log det
log det n2
0x?
n
n2.
Ox? n
Therefore, we deduce
O2 log det n
N
82 1
N
TTT2, Z, n
< EE
log det
<
Etr
aA?-
0x? n
7
n12
2, 2, uniformly equicontinuous.
Again, by Lemma 4,
n. follows that
1 Etr nx.
2 2,
2
< x
Therefore (f2) is
n
n
We want to show lima fa (As) h((A,) by contradiction. If is not true, there exists 0 and
subsequence ( such that S (Ax) M(a)) 2 Let E
[a, X
0) be
24

---

Under review as a conference paper at ICLR 2022
closed interval that contains A, The subsequence (fa,] } is uniformly bounded and uniformly equicontinuous. By the Arzela-Ascoli theorem, there exists subsequence { that converges uniformly on A E. Recall lim, (ax) = h(&,) (Equation (37)). Thus liny Saz, (2+) h(A,).
By (Rudin, 1976, Theorem 7.17), for X E we have
lim Fay, (2x) 1i())))))))
J
This is a contradiction. Hence, we have shown that lima (A,) I((),,, which exactly Equa- tion (35) (recall fa (Ax)
& aA, +/f log det Ni
E
1 log det N in Equation (38)).
83. n
n
Proof of Equation (36). Define ga()))
+ log det
0 aa n log det Then
0A:
d'aAA) ax
d2 E
n log det N1 = 32,
DA, log det
We have
0
log det N
02 n
1 tr (Z.Z, N N N-
1
tr (2,
N2,,
n
1 1z,
n
1
12
2
2
1|
12,1
12
X2n²
where the last inequality is because
|N- -
1 Am
Jn
1
If # by Lemma 4, we have
F
A
1
1 X2
X2n² 1 12
E
EIZI 2 11,
X²n²
If i j. by Lemma 4, we have
X
B12
1
n
X
As result, get
82 0x n log det
N
1
n2 22n
n n
X2
Thus we can interexchange ax, cause (A,)) < E Dxjox, for Ay.
à and expectation, and get g',)),)
E
2² log dot N Be- 0x n
1 n log det | S t.. the function sequence {g',} uniformly bounded
25

---

Under review as a conference paper at ICLR 2022
Define L = ZJ Z, and W Zj P.,N-12,
Zy.
We have
0s
N
log det
0x n
n
2
tr
()
1
tr (L 2,T2322 2,4)
An
1
(2 (2,2,)² (--
tr
An?
[|,,2] N-12
An2
|| 1/ |,,2, 11: 112.12
An2
| 1 12.12
33
2 1 1..12.
3
where the first inequality is because W < Xm 2j Zg and the third inequality is because N < An In
and then ||~-1 < /n < में By Lemma 4, we have E 1|2 S n² and E 1|2 2 S n. If i A j. then Zj and Z, are independent, and we deduce
1 1370
1
E
If = j, we have
1
11
E
|1
3
X3,
1
As result, we deduce E we have
Dazax,
8a
1 log det
N n
=
Ty,
82
xo
1
N log det
= (Ag). Moreover,
g3
N log det
(2;)) < E
2
ax5ax,
23
Therefore (g') is uniformly equicontinuous. Define
a inf PERT
wi w),,,)
log A +
Σ Aepi
+
Σ
+ Pi 24 log 2,
Od
[E(m)
VE mm]
We want to show by contradiction that lim, 9¹ (Az) = w/ (Az). Assume that it is not true. Then there exists > O and a subsequence {sh,,} such that I9', (2₂) w (A2))) > Since {9', } is uniformly bounded and uniformly equicontinuous, by the Aizela-Ascoll theorem, there is subse- quence { } that converges uniformly closed interval F. containing Ay. Equation (35) shows that lim, Bo (X²) = w())). It follows that lim, Jeur (A₂) = w()z). By (Rudin, 1976, Theorem 7.17), for A4 E E, we have
lim Han, (2₂) = w/' w'())),
which is contradiction. Therefore, have shown that lim,, g. (2y) w w'(y,,, which is exactly Equation (36).
26

---

Under review as a conference paper at ICLR 2022
D PROOF OF THEOREM
D.1 PROOF OF ITEM
Define ((p) - log (A+2 Asps) + 23 2z 2 + 1))
The func-
tion g(p) is continuously differentiable on IRT
The boundary of RR is ORT
{o R. | E [m]] P; 2 0) A (3i E [m], - 0)}.
Because lim g(p)
limaçae- t0 (p) +o0, there exists a minimizer p² E RT of g()).
Taking the derivative with respect to pi gives
0
log
X
+
+
Σ
Pj
Pj +11) 20
A A + Σ f=1
21
Op:
2j
Aypj
Pi
j=1
3=1
Setting it to zero gives Equation (6).
D.2 PROOF OF ITEM 2
Recall Equation (6)
A
2
1
=0,
Vie [m].
2gp3
Rewriting the above equation gives
(a
- p3)
A +
N:PR
= >xpp
Vi [m].
k=1
Rewriting it in the linear algebraic form yields
p²) (A+ p') (A+ x
Applying ax both sides and using the implicit function theorem, we get
- p²) (p+ J) J (A xT = diag (A) J + diag (p*)
Arranging the above equation yields
(diag (A) + (A+ A p¹) Im (z - p²) p²) (z-p''= -dig (p')
Define a = A X p. diag (A) + () + T p') 1m = diag (A) aln and B diag (A) +
(A X p*) Im - - pー) T A - (z - p²) A T. The matrix determinant lemma gives
det (B) = (1 - X A (z pz)) det (A)
Recall Equation (6) again and we have
\ + 40
P4
We have
a
Σ
Aapi (1 - -p2/2))
iE(m)
X + Σ tapl
Σ
Aspl (1- (1-p2/z)) p(/2z)
kc(m]
rE[m]
A (p:)
= Σ
> 0.
8 mm]
It follows that
Σ [ie(m)
Xxp; (1 p2/24) 1.
27

---

Under review as a conference paper at ICLR 2022
Then compute X AA" (z (z-p"):
p²):
A 1 (z - p²)
A (z p.)
X; +a
[m
X (z+ p5)
iE [m(m
P
Asps (1 - p2/z)) 1. Σie(
a
> 0. Therefore, det B & 0 and the matrix B is invertible. Thus we get 1 - A A (z- (z-))>
D.3 PROOF OF ITEM 3
Lemma 11. Define AnTa + ZTAZZ, 7 Eielm) 26 r (ri,..., Tm). = (A1, Am).
and
), 2r:
+
2r
Varri
Σ
ri Ar?
A
iE mm)
ic/m]
iE(mi
244 224 (2+
For any K, 2 and K₂ 2
we have
h
lim tr N
lim
Etr Ntr
n.d dz/n+z,
n.d. no0 dz/n-zz
max min )(r,I,,)) 0griSK, KSnSSK OSriSk
min ogrisk, ogr.gk.
,(T,r,A) = max min ((r, r, A) r.20 22
min max (rr,,
r.20
(39)
If is a solution to the optimization problem in Equation (39), then
1 1+
j
Σ マグ
+ + Ar?
(40)
j=l
r
ri
r/v=
(41)
+ Σm
Moreover, we have
r
max min ((r,, A) 0g n00 r.20
X?
Proof. Let g ~ (O0, be multivariate standard normal random vector. We have
tr -1
-Eg9 N-1 9
-B, sup LER
(2g - -TNN)
=E, sup LERn
(29 T t TT TT AZt n2 (111)
-B, sup inf IER" weRd
(20 1 2n AZl. n Au nd [1(12)
-g inf sup tER" ueRd
T AZt Tt
u Au +
2 nd 11113
1
= 2E, inf LER"
sup ueRd
T Zt g T
t
T A
4 + nnd 11112]
2
2
28

---

Under review as a conference paper at ICLR 2022
We view
inf sup YERR wERd
uu Zt got
A u 2 ||t||/
(42)
the primal optimization (PO) problem in the convex Gaussian min-max theorem (CGMT) (Thram- poulidis et al., 2015).
The KKT conditions for Equation (42) give
zTu u nAl 0,
Zt A - 0.
Solving the above equations gives
N 9: u == AZN 9. With probability at least 1 - 4 4epp (c > 0 is universal constant), have |19||2 2 and |||| S vd 2 - (2 / vn. Therefore, we get
1 2/n 2 Avn ||u|2 $ A | ||||| - A+ (2+ v Vn.
| || N ||g|| 2 An
2X+ (2 + v7)
A/n
22+ (2+
Write a
:
where us Rd. For all K. 2 Kn 2
2 x
the opti-
Uym
mal solutions 8 and u" to Equation (42) satisfy vn 11 < K2 and |luell S K2 for all i E [m] with probability at least 1 - 4 exp(-cnn) Define S, (t E R /n S K2) and S, = {uE ||ue|] < K,,, Vi E [m]]. We use to denote the indices n, d; and use lim, to
denote limn, -+ Define event
00000
d:/n=::
E. { inf sup
2 T Zt
g
-u - A [(111)
inf sup rES. weS,
n Zt g 20
1 u + nd |||1
(ER" WERd
Then with probability at least 4 eexp( -nn, we have 1" S, and Sg. Therefore the event Eg occurs with probability at least 1 exppppp2e (nn), which yields
P P (EE)) I 4 cxx((-en).
Since Enzi 4exp(-enn < +oc, by Borel-Cantelli lemma, we have
P lim E = 1 (lim inf E. }}=
P
Then with probability 1, all but finitely many E. occur. Then almost surely there exists no such that for all n > no, Ea occurs.
The auxiliary optimization (AO) problem
inf sup teS, ueS.
[Itllg of Tu [ull22911 t- gtt -u TA - u +
nd ||e|
| v Exe(on r/0z
11 ll
1
inf sup uSr.sk, k
5
dr?
Vn
2
ve(mi
3c/m]
sup 0 KS
inf
1 *E[m)
??
galll rr
+
Σ
11a1,ell2
1
Σ
1
2
xr?
Vn
2
A
iE
[m]
where Φi ~ ~N(0 02 NN0 In), and Ø3 NNO, Tx)-
29

---

Under review as a conference paper at ICLR 2022
Taking d, - too with d//n 2 constant, the strong law of large numbers gives
ng
r
Vn
mE/m]
s [m)
dj
91. lla
V
ng
Vaj.
vn
/dz
Define
9
||g
1
Xa (r(,))= =
n2
rı + rt
Vn
r3
2
Σ
A
r
+
2
k [m]
xc [m]]
iE *E|m
It is stochastic process on (ra; [0, Ki] x [0, Kw. 1h
We have
lim Xa (r,,r) = X (Fu,r) = TT, + Σ
+r
Vzri
Σ
+ Ar?
2
d
2
sElm]
mE[m]
sE/m]
almost surely. Since vI + x² convex and increasing and the function
||1||2 convex,
thus /I- ||r1 is convex in and then - V Eieim r? llssll concave in Because - Eiglm) A is concave in and Eiemml ear in r, we deduce that Na (). concave r. By (Liese & Miescke, 2008, Lemma 7.75), suPrejo.K_]"" aXa (rr,r) - X (rr,r) + 0 almost surely. Then for Ve O, there exists no(e), (c), do.a(e), do, such that for all >> no(c), de > do,(t), |d// z4 (t) and for all r E [0, K., we have
vn T. -VI+ || Il a vn
vn 11 r is lin-
X (re,r) - ( r) < X (),r)) +c.
Thus we obtain
X (rr, r) - - Xa(ri,)) sup Xa(re.))
re]0,K,)"
Xa(ror) < X (rr,r) +ES sup X(r,r)+ +e, re
which in turn implies
sup k.) m
X ( - 65 sup Xa(ri,))
r
sup Xa(rir) sup rejo.K.."
X(r,r) +c.
re[o,K.]]
It follows that suPre(o, (Ft,r) suprejo,K,I X(r.r) I e. In other words, we showed
Ya (rt) - (r:)) +
almost surely, where Y (rt) = suPre[o. X, (T.,)) and Y (r.) = suPre X(r,,
Because X, (re, r) is convex in rt, then Y (rr) = suprejo.k.I (a r) is convex in rt- By (Liese & Miescke, 2008, Lemma 7.75) again, SUP,, Va (rt) (rx)) + 0 almost surely. A similar argument shows that
inf Ya (re) - inf Y (r.) mee(o,K,)
= inf k.),0.k. reju
sup Na( inf sup r
X(r,,r) +
k.])oKK.)
almost surely.
30

---

Under review as a conference paper at ICLR 2022
Therefore, obtain
inf sup
[1tl12 g1 u + Ilull2 g
1 gTt
A--u-
2 nd |||112
2
rESt uss
= inf sup os osr.sk
+
93
T1
+
r2
|19 ns
Σ
+
72
A
2
sE[m]
sc/ml
KE mi
inf SSnsKeosr:sa
sup
-t 1+ Σ
? + Σ
Σ
- ク
1
(43)
2
A
2
ie(mi
[m(m]
VE [m
Define event
Aa
inf sup AER" ueRd
u T Zt gtt
-1
T A''-- uu +
2nd [10
M
2
1
1
Bg
inf sup SE ueS.
Tt - g
u
A - +
nd
|1116
11
> 7
2
2
C. = inf sup SE u.
[1 91 Tu=- + || 1 1
1
2"
A
u
nd |1112]
- 1 >m]
Recall
{ inf sup u Zt 9 gt A- -u + nd [1113) TAA
1 u + nd [1:1]]
1
}
E.
inf sup rES, weS..
u Zt 9 T
A
IER" uERd
2
2
We have Aa n Ea S Ba. Equation (43) gives lim, IP [Ca] for any T > because almost sure convergence implies convergence in probability. By the convex Gaussian min-max theorem (Thrampoulidis al., 2015), we have
P[Ba] < 2P (Ca).
It follows that
PP (Aa) P n Taking lim supa on both sides, because lim sup, P PBa} < 2 lim sup P P(Ca} = 0, we get
< P (Ba) + +P(E) < 2P (Ca) +
limsup IP {Aa} < sup P (Fa) < lim lumsup E 0,
a
where the second inequality is because of the reverse Fatou's 's lemma. Thus
inf sup " 7t - g
1 -u u
T
nd |11 2 Es n.
EE dERd
2
2
Therefore, we deduce
E Ps 2 inf 0sris K. osr.ska
+ Pt Σ
Σ
+
+
sup
-Tt +
VeT:
2
Ni
[E(m)
ic(m)
(E(m)
sup inf ukr,š osrisk.
2rt 1+
2r: ?
Verri
+
2, o Xr?
[E(m)
ic(m]
sup inf 0 osrisk.
(44)
1 ||91|2 and E An |10112 = x0. by the dominated convergence theorem Because lg N < Xm
1
for convergence in probability (Cohn, 2013, Proposition 3.1.6), get
lim tr N-1 lim E, NN max min Mrr, r, 05r.5k, 0Sr,5k.
(45)
31

---

Under review as a conference paper at ICLR 2022
Note that 2 Eie(m) of is convex in r, -2,, Eie(m) 2 is linear in r, and Eie(m (m) xtr
is strongly convex in r. Thus & is strongly convex in r. Note that 2r 1 Eie(m) 17 2r [me(m] Vziri is linear in and that -Arī is strongly concave in rt. Thus & is strongly concave rt. Then has a unique saddle point (r7. r") on [0, Ki) x [0, K,] that satisfies min 1 (re, rejü,K.."" "M re(o,KKl
max ku ".
min max (rr, r) 1 (rī,r"),
(46)
where the first equality is due Sion's minimax theorem.
Since (tr | S I. using the dominated convergence theorem and combining Equation (45) and Equation (46) yields
lim tr N-1
max min (rr.r,,) = min max 1),, OSriSK OSrISk,
osrisk, osrisk,
By the uniqueness of the limit, the right-hand side maxegrik, minogrisk, A(r,, r, 2) and minggres. K. maxognsk, 0(r,, r. A) do not depend on K2 and K, as long as Kr 2 fandK, 2 22 (2+v7) Thus have
Etr N-1
max min 0(ri, X) min max (rr, r,) r.20 r:20
r.20 r20
If rf then 8 (0, min K.." Eie(m) x 0. Thus r' must be zero However,
0 2X 0) = 3 4x
> 0 (0,r*) Therefore r > O. We compute the partial derivative
09
2r
2r112 +2 A
Ör:
1+ Liemm] 1
If rr = 0,, we have
00
-2 <.
Ör; 0,,=0,,-77
Therefore, one can increase rf and make max,,e|o.K) miDrelo.K."" O (r,, smaller, which results in contradiction. Thus r. > 0. Thus the minimax value attained when r2, r; > 0 for all E [m].
To obtain the optimality condition, compute the partial derivatives
00 1
2
2
Σ
rivzi
2Xrt:
Ör:
(E(m)
kE(m)
00
2r.
2r. /
zi
-
Ør:
Eie(m) r?
Xi
Setting them to zero gives the optimality condition for rī, ri,,...... Thh and yields Equation (40) and Equation (41).
Using the envelope theorem, we get
max min 0(r,, A) 0x, r. [.) rE (0,K,, @d(r; r", A Am)
r
X
Lemma 12. Define N -nnl + -T AZ. The following equation holds
02
m
m
n.d. +00 de/n=zz
lim
E
Od
(N-1)
axoax
inf PERm
log
A+
Xipj
Σ
Pg
2, (log
Pi
2j
+
11
X?
j
jml
32

---

Under review as a conference paper at ICLR 2022
where r" is solution supr,>0 rm A(r
......, A1 ....... Am) and
OTe, Tiy..., mms A1; ....,,, Am) 2r:
+
Σ
2r Σ
V
+
1
r
Ar?
A
iE(m)
mm(m
ie(m]
Proof. Since
tr (N-1) ir (2 N- S
tr (Z) 2.) (An)²
1
(47)
ax:
and E [Am)²
tr (7 2.) = 1 (by Lemma 4), using the dominated convergence theorem gives
E
ir (N-N) = Etr (N-N
ax;
We use to denote the indices n, d; and use lim to denote limm d, +0000 d//==;;
Define fa(Xi)
[og (A+E Aips)) + EiE(m) Ps - (log Ls +1)] and h()s)) = supr inf mo 30 0(re, r'm
Eir (N-1), ((4)) = th in PERT PERT
2,
Fm, (h....,mm) Because |tr (N-1) S
tr (1 [n) I 1
x and lim tr (N-1) 9(4;) (by Lemma 9), we have Lemma 9 lima fa (Xi)
lima Etr (N-1)
g(x)). Lemma 11 shows lima (da) h().). Therefore lim, fa()s)
g(A,) = h(A.).
Because of Equation (47), we have (A,)
E.r (N-1) and
DA.
à Etr (N (N-1) = E ax,
Od, tr (N-1)
tr (N-1)
1 2 X2
(s,(A:) = and therefore { is uniformly bounded for A₁ Because
S E
02 (NV-))
0x3
2 tr (N Z N-1 N-1)
(N-1 (2:ZT)² N-
An
1
tr (Z,Z, N 22,2,)
An
ir (2,2T)²²
(An)3
and E [An) tr (7,7,T )²=
x x
(by Lemma 4), using the dominated convergence theorem yields
82
8
8²
E
ax3
tr (N
07:
E
0xi
tr
(N
=
tre
E
Moreover, we have
02
z 1 x3
1
(A S
are tr (N-
Thus { is uniformly equicontinuous for di We want show that lim,, (aa) g(())) by contradiction. Assume that it is not true. Then there exists 0 and a subsequence { such that f (Ax) - g((2,) > c. Since {Fay } is uniformly bounded and uniformly equicontinuous for X E E (E is any closed finite interval containing X²), by the Arzela-Ascoli theorem, there exists a subsequence (fa..) j that converges uniformly on E. Since lim fai, (2x) = g(>z), by (Rudin,
1976, Thoerem 7.17), we have
lim fo,, (Ax) g(()
which yields a contradiction. Therefore, we have limq (At) = g(A)). Recall g(Ar) h(w,) for any X > 0. Then by the final part of Lemma 11, we have lima f2,)) (Ax)) 1((2.) 22
X2
33

---

Under review as a conference paper at ICLR 2022
D.4 BIAS
Lemma 13. Suppose that U ~ Deemm) Unif (O (d:)) and V are two independent d x random
matrices such that V -L UVUT, where d Σi= di Let 0 Rdd be fixed vector. Write
0
:
where 0; 18d,, Let
Om
Unif (gd. (110:l2))
[m]
be a random vector independent of and let = diag (Az Idi
Amtdm E Raxd. Then we have
[2] = E
|| |
E
//
Proof. Recall UAU
A and noticing
UT d. we get
E
1
A
=B
=E
uUvVU AUVUT 8]
=E
AUUUTAVUT
0
=E
AvR 22
Lemma 14. Define
④ diag (111112/d, dd,.......
113/11//d 12//m)
and
1 (ndI, + ZT AZ) -1 1/2 Then have
Bx,d |10-11 2IE ir (ASG) + Etr (SASE)
Proof. Recall Equation (22) in Lemma
Bxd = E ||///2
Ia + nd
A2/2ZZ A1/2
0'112
Let U Diemm) Unif (O(d,) be random matrix independent of Z. Because UZ - Z, we have
1 1/2z 1/2 4 + nd
1
AUPUZZUUAAR (1a la nx n A1/22 11/22 UT.
la nX
Define 0
Dilm Unif(S4:-1(H)))) ((10) (2)). Lemma 13 gives
Bx.
=E
1/A1/2 Ia nX
1/2 zz A3/2)
011
EE
||2//2 (Is 5) 01
=F
[1 010
[0ll
To ASO]
+ E 0 SASØ
E
E
- E
34

---

Under review as a conference paper at ICLR 2022
Notice that |0] 1|0'11 and è E [0T Because θ commutes with A, we have (SAŒ)-
(SSA) ir (ASS) light of these, we deduce
Bxdd, |10'11 - Err (ASÕ) Etr (SΛ6) + Etr (SASE)
110'12 21 tr (ASO) + Etr (SAS6).
Lemma 14 expresses the bias Bx,d,n the sum of three terms.
Computing 1011A Note that 110112 = O' AO' = -ie(m)) A 111112 Therefore,
lim n. n.d, 4000 di/n= [11,0 1111,"112-*71
110'11 q (z)
Computing I tr A
Define N = Anrl + -T AZ = Anda + Eie(m)) A,2,2, We have
Etr ASS
22 (nAIn + AZ)
tr
=E tr
(ZTAZZZN))
10113
Σ X
E ur (2:2, N-1)
d;
mE(mm
X² 11 " E
0 1
=
04, log det
d;
mm
1012 n
log det
d,
0x:
72
*E(m]
where the second inequality is because & commutes with 332 and the final equality is because of Equation (38). Taking lim v.d:+ and using Lemma 10 gives da/n=as
||I1, 11g -m
A8Th a
2i log +1))
lim n.d +00
Etr (ASØ)=
Σ 3E|ml
inf
log
+
Σ Aspi
Σ aE/ml
Pi
Pi 24
PERm
de/n=z || 112
FE(m]
Using the envelope theorem yields
0 inf
24 log fi +11 +1)) Eie(m Pi
P
24 p
log
ApPi
OA; PERm
Asp;
(m]
(E(m]
where the final equality because of Eqqution (6) in Item Therefore, we deduce
lim n.d toc
Etr
(AS²)= = Σ
Xm 2,
P
Pi 2; (1-
q (AO(z-p'))
A
d:/n-t2.
mE/m]
[II, [1,
35

---

Under review as a conference paper at ICLR 2022
Computing E tr (ASS)
We have
E SASé)
E
A 1
EEtr
ZT A' A²ZN-1
tr ir
IT AOZN AN
Bi [2 N 222 N
d;
mm
jE[m)
X 1
n2
82
N log det
E
d
mm
jElm]
where the third equality is because commutes with A1/2.
Taking lim no
and using
dn/n-2
||TT, 11 12--
Lemma 10 gives
+1))
lim +00
Etr (SASE)= mm(m]
Aan 23
inf PER
log
A + Σ
Appl
p
21
log
Pt
21
d ||I1,6 | -7%
jE(ml
AE [m)
Write A (AI,..., Am) and ( Let p" E RT be minimizer of Equation (5) 0o' and J = dx E Rmmx be the Jacobian matrix Jig = api ax,
Recall Item
(diag (A) + (A+ AT)") Im (z p = (z - p-)p))e pT diag (p') Using the envelope theorem, we have
aY;
0 inf log
PERT
Σ Aep 16/m]
Σ [E(m]
P
21
log 21
Pl + +11)
A + Σ
P
dept
pt X X
pr
Recall Equation (6) yields
p
p
pr
Xi
Differentiating the above equation with respect to xy gives
82
+11)
07,0
PER
inf
log
A +
Σ
depl
+
Σ
PI
log P
21
LE
[E(m)
0 24
>iJis
(zi pt) deg
X?
It follows that
lim n.d,
Etr (SAS
di/n-zzi
|111,0 1,
Xm
Σ 23 Xo + (2,
pp)) 8eg
Σ
21
X2
[e(m]
jE[m]
Jiz + (2i - _p)) 8e8
A
[JE(m]
T
(A 2 (z - p²))== + Jr 02)
36

---

Under review as a conference paper at ICLR 2022
Putting all three terms together, we have
lim Bx,d,n =q (A z) 2q (A (z(z)")))+ (z- (1) =q (AOp' = JA
n.d
d:/n-ta 112,6)
Since [Bx,, is uniformly bounded and uniformly equicontinuous for X (0, 1] by Lemma 5, [Bxd can be extended continuously to [0, 1] and the family of extended functions is still uni- formly bounded and uniformly equicontinuous for À E [0, 1]. By the Arzela-Ascoli theorem, [Byd,n] converges uniformly to the limit. By the Moore-Osgood theorem, we can exchange the two limits lim n.d++aa and l and get
d./n-
|IT, -1
lim n.d.+0
Bo,d,n
lim n.d. +00
lim Bx,d,- = lim lim X-0+
Bx,d,- = q (A@0" + JA la-0
2-50+
-
d,/n-+2;
d./n-t4 (1T.0112-90
d,/n=a
[|TT,0" ||TT,0"11a 122-
[|T,0"11,-") 1m
D.5 VARIANCE
Define N = ndIn + ZT AZ. Recalling Lemma gives
V3,dn
EEIIAZN- 11 1
X tr (Z 2
1=1
tr (N (N-1)) Og
=
1=1
Using Lemma 12, we get
lim Vx,d,
n.d, -00
d/n-28
lim
E
tr (N-1)
n.d, 000
di di/n
lim nI. 000
E
aii tr (N-1)
d. n2
m
82
m
m
li L2 +1)
inf PERm
log
A
Σ
Aipj
+ Σ
Pj 2, (log
2j
j=1
j=1
Using the envelope theorem, we deduce
Pi +1 +1))
aA
inf m
log
A + Apps
+
Pj - 2j
log
23
x+ m Σラm
j=1
1=1
Then we take FA,
a
and obtain
02
m
m
Pi + 11) Pj zy (log
inf ax,rx PERm
log
A Σ Xyps
+ Σ
zj
5=1
1=1
1
X =0,
Σラ Aipj
p3 + Eselm AjJJi
(1 + Eye(mi A1p;)
37

---

Under review as a conference paper at ICLR 2022
As result,
P +
+Ijeeim AzJJi =0= (102) T
(0r + +J
lim VA,da 0²
X
n.d, +00 d2/2-22
a Eje[m }
(A+AT
By Lemma 12, the variance is given by
m
lim VA,dn lim
2
tr (N-1)
0²
n.d
d
i=1
where solves
sup inf
2ri
1 Σ r 1m(m]
2r, Σ (E(m)
V +
Σ 4E[m]
1 X
xr?
r. 21 ym 20
Since [VA.d.) is uniformly bounded and uniformly equicontinuous with respect X E (0. 1] by Lemma 5, [Vi,a..) can be extended continuously to [0, 1] and the family of extended functions still uniformly bounded and uniformly equicontinuous. By the Arzela-Ascoli theorem, (Vx.a.) converges uniformly to the limit. By the Moore Moore-Osgood theorem, we can exchange the two limits lim,,d, +00 and lim and get
d, 4//
lim lim VA,dn lim lim VA,dn 0² 22
A=
n. n. - 2-0 n.d. dz/n=aa
d./n-22i
i=1
E PROOF OF THEOREM 2
We use Theorem to prove Theorem 2. As Theorem I, let solve minl,20 max, ((r, r, X), where 0 is defined in Equation (7). Note that 0 is quadratic function of rı. Define A
Eig(m] r² +1, B. Eie(m) Vairi, A v Eie(m) rt² + 1, and B Eie(m) V Then
A-B and get
B 2 (A
(A B)²
min max (r., 1r r, A) 4220 r.20
min 7:20
+
min ri20
Ai p
A
Ai
kE[m]
iE (E(m)
Taking the partial derivative with respect to Ti gives
i (A (A-B)² B)
2
=
A
B
T1
2z
+
T4
Ör;
A
X
A
X;
AE(m)
Setting it to zero gives the optimality condition for r::
A
B*
r A"
r
Vz
i
[m].
(48)
It follows that
Vzi
r //
i,j e [m].
/
Some algebraic manipulation in the above equation yields
r X;
V=A² - r3
4.j [m].
rj
2
A=jA"-r3 r3
38

---

Under review as a conference paper at ICLR 2022
Define z (mm)) Then
| Eie(m) 24-
By Cauchy-Schwarr Schwarz inequality, if d/n
Eiemm| 24
B
Σ ve(mi
2i
||||| < ||r||2 < V |r|2 + A.
Thus there does not exist such that A = B. If d/n Eielm| 2, 1, then B is feasible for For example, set
Vz.
(12l
1) |
We have
|z||
B (r,
1
A V + |r
B.
2
If ||||| > 1, since A = B is feasible, then
(A- B)²
lim min A-01 r20
min Σ
2
A
220
A
xE(m)
A= B iE 1mmm]
If [||2]]] < 1, then A - B always holds. To be precise, we have
- BN ( |1r11/ 1- [1tlla) +1-1|1l))) ((1- --llllll)) [1x112
|||||| > 1, then (1 - / h |r|| > 1 - V V If |r|1 S 1, then v /1r112 + 1- ||r|| 2 /2
Thus there exists a universal constant Co = (1 v
V (V2 1) > 0 such that
A- B 2 Co.
Recall Equation (48). We have
Ar X
(A' (A' B²)
i [m].
A"
Taking limx- since A - B" 2 Co does not go to zero, we have
r
Va 0, i e [m].
A*
Then we get
22 2i, E [m].
+
Σ Σje(m)
Summing all E [m] yields
Eie(m 132
|z/|| 1+ Eie (m) 1,2
Therefore, we have
m
Σ Exe(m) 26
lim Vo.d.n o² lim n.d: +00 dz/n-
0² 1 Eie(m) (mi) 24
r
39

---

Under review as a conference paper at ICLR 2022
PROOF OF THEOREM 3 F
Define A" V Viemm 1?² + and B Eie(m) V Equation (15) Theorem 2 yields
ri
V - ri
X2 VzgA*
Using the constraint A = B", we get
A1 ( B -r)
X2 V 22 r3
Define y - We have the following equation
A1 (g(21 - 1) /2122)
=
A2 (9V/122 + 22 1)
Solving the above equation yields
(1 - X2 (1 22) + 1(1 (2) 1) X2 =2)) + 22
(49)
2)2 221221122
Here discard the negative root. Let 112 + 132² r2 (1 q2). ?? yields
1 x = r (1v
v22)² 2²
(1V + V=2)²
1 q2
Solving from the above equation gives
12 1
I (: - 1) + 24 / 21 + 22
Therefore,
q² +1
lim d./n+3
Vo.dn
02(21 - 1) + 24
21 22
G PROOF OF THEOREM
Instead of considering the l specified in Equation (18). we first consider a Bayesian setting where 8" NN(( (0, La). Later, will show that the setup in Equation (18) is asymptotically (as d; oo) equivalent to this Bayesian setting. The precise meaning of equivalence will also be presented later. Our strategy
be divided into steps. The first step is to show that the Bayes risk of the Bayes estimator is monotonically decreasing in the sample size n. The second step is to translate the sample-wise monotonicity of the Bayes estimator to the excess risk of the optimally regularized estimator a,, in the setup of Equation (18).
Recall that since we are interested in sample-wise monotonicity, we add subscript to X and (they are defined by Equation (1) in Section 1.1) emphasize that they consist of data items. In this Bayesian setting, the likelihood function of 8" is
[Eiejm (3): (0", 221))² (0',,))))
|x - Nn 112
L (8" Nn)
II L (8" I 1.) exp :E(m]
exp
202
202
(- 110-12). Therefore, the posterior density
The density of the prior of 0* is proportional to exp of 6* is given by
dd|o0
| - yn
p (0") (nnYn) x exp
2
2
40

---

Under review as a conference paper at ICLR 2022
As result, the posterior distribution of 6* is Gaussian. The Bayes estimator is
Bayes (X,,yn) = arg min Eg- 1|0 0- 1-
Taking the derivative with respect to 0 gives
00 g xp, |00 11 = =2 - -8))
Setting the above equation to zero yields E (Bsayes (Xn,yn) Eg Ep(0" 10000 (x.N8.)0))) and there- fore
Bayes (X,,yn) mp(8 N = =E [0*) Nnl arg min [110011 1 yn
σ²
The final equality is because the posterior mean of a Gaussian distribution equals its mode.
Define the Bayes risk
R2 - N1. [1@ansss (N) - -8u112]
Write X' =Rd and y = R. Define
1o ( (x)) -0 001
R2 inf xxxxx"-
have
R² =
inf
Eg B1r yx), 01/20
0.20 x
inf xx*"x=--3"
Eg 110 (((2..)))
| - -511200
B E1/20" 1Nn - -1 |
1/1/20Boyes
(N,
Rn.
where the third equality is because the conditional expectation minimizes the E loss. Next, want to show that R,+1 Rys i.e., the Bayes risk the Bayes estimator is monotonically decreasing in the sample size
|10 (Xn+1, 0"
inf Ra+1 0:x0111 xy++1 aRd
|1o (Xn. - 0-112 1
S inf 6xx"xy"-
10.
Rn.
Then we want to show that R. equals the Bayes risk the optimally regularized estimator Ox,
Rs inf Eg (g X20
@
Σ
Since R. = infa.x" x -R Es, x..y 00 (X)) - 00 -0-1² we get
Rn < inf Fo (
@ - 0-
A20
41

---

Under review as a conference paper at ICLR 2022
On the other hand, recalling Bayye (n) = arg ming [dlo1l2 +
I1x [
0 022e and
o²
a .,dd
Rn = Eg=~N(0, No. ||@aayee (X) - 0+ x
we deduce
1 - Ar
Rn 2 inf Re Rg
A20
Σ
Therefore we deduce R,, inf Eg (0. (a). @xxnd gr
As result, establish
sample-wise monotonicity of the Bayes risk of optimal regularized axmd
Ro+1 inf Bag....41.ya Xut1 0 0=1 S inf Ra.,x..y X..yn
0 |x.md - 0r 0=1 Rr
(50)
X
X
In what follows, we show that if 0 is given by Equation (18), the excess risk of dx,n, is asymptoti- cally equal to its Bayes risk when 9" ~ ~N, Ta):
lim d,000
Ex..y
[0xm, - 0" Eg ~NT (a)
Bxnga 00xma 0- | = 0.
We abuse the notation in the above equation. The 0r in Exn.n 10Am - 0nl satisfies Equation (18),
while the l* in Egg (000 Ex,.y' @ 0r follows normal distribution (0 Fda). By Σ
2
0r are as defined in Table 1 (where P is an orthogonal matrix and A (A Am Iam) E Raxd is diagonal matrix), for fixed 0
Lemma 5 and Lemma 6, if E PAPT and 0' = T
have
Ex Ex,,y 10an 0-)
= Exn.Nn
||A//2 la + nd
1 - 1/222Z A122
0'11
+ -Ox ||AZ (AnIn + _ AZ)
113
where every entry of % _dxn follows i.d.d A/ 1). If -N LL)) we have 0' N00 4
Since the variance term o'Ex..y ||AZ (AnI, + 2T AZ) - I13 does not depend on 0", the two variance terms cancel out and get
E Ex,,y
0 0xnd
00133
- Eg. -o Ex..N 1 - 0- 0-113
1 Al/2 77 7 -1 1
||///2 [T+
112
nd
Ex..y.
||A//2
Ia+ nd
1/2 T1112 112)
8112
For U Oiefm) Unif (O (d:)). we have
Ia+ nd
1/2 1/ A11/2
d la+ nx
A U UTA
=U
Ia+ nd
A1/2ZZ UT.
By Lemma 13, for (and thereby 0') specified in Equation (18), we get
Ex,,y.
||A//2 la
1 1/2 12 1/12)
A1/2)
0'113
Ex Ex,Nda Nn.d
|A
la+
1 1/ 1112211 A
$11
nd
nd
where
Unif (0 = Unif (sd:-1 (Vasfd)
1 m
ic mm]
42

---

Under review as a conference paper at ICLR 2022
In the Bayesian setting, if 0' ~ NO0 L.a). then UT oT ~N Ia). We have
-1
2
(Pr=W(0.1aa).... |an - 00 = (()))
APPPU
La+ 1/2 zz 12 A
U 0'
nd
-1
=Ex At/2 Ia+ nd
12/22Z A
where & TT ~ (o, [.)-
ltd Unif (5): h iid. (d:), and define
Next, we want to couple and sh. Let 8,
~
ddi/ds1
/1/dds
7 1
v dm/ dsm
hm/ dsm
We have |0l|2 1 and
h
m
1| =
i=1
d3
h;
1 1111-
1
V
d
de
By the strong law of large numbers, limd, h2/ds = 1 almost surely. Thus we get timd,-+oodd./dde || v via Vi and - 1 - -b112 = 0 almost surely (re- call that we will let dj + +oo and d + for some constant is > 0. Because
|| S and (Ia ax AZ/2ZZ A2/2) S |all2 = 1. we bound the norm of
Q A 1/2 (La + nd 2Z A2/2) - as follows
llQ11, s ||Ae |
(1at nd
1
-11
S 1.
follows that
Ex Ex. .n.
1100112 - Ex.
[1Q011
< Ex Nn.d.w
110011 - 11Qv11
Ex, Ex..Nos Nnrw
(1Q@612 + (1@wll2) Q0 1Q2l121
Ex Nn.
[[110]12 + l1vill2 11Q(0 12)
E Xn. vno.
110 16--4112-
where the last inequality is because || + ||+l| S for all sufficiently large d. We know that fima,-++o.dd// |1 2112 almost surely. To apply Lebesgue's dominated convergence theorem, need to find dominating integrable random variable. In fact, 1 + || dominates
|| - 2
Ø 1b112 S ||0l|2 + 11 1 + 112122
/ (a))
It is integrable because E || = EE dominated convergence theorem yields
1. Application of Lebesgue's
lim //d/dd/u
E Ex
[1Q011
Ex Ex an.sh [10012]] = 0.
43

---

Under review as a conference paper at ICLR 2022
Therefore, conclude that
Ex..n 10m - 001 -10 Bxn @x 0r
lim d, 4-+000 do d=+is
and this convergence is uniform and d (0) follows that
lim Ex... | 0²1 Eg N Ex.. n.d +000 2
@ann Ex
8- 0-113
and this convergence is uniform (0, oo).
By Lemma (the proof is similar when we replace by n, - c0,n/ds + 7),, we have
|0xmd - 0* 11 inf I8 N Bx Ex,.n 10 - 0- =0. (51) inf Ex,,y ASO
lim n,d-000 n/d, +
ASO
Define fa(A) 10 (1)) Ex...r 10xmd 0r 0/
We to denote the indices n, dj. By
Lemma 5 and Lemma 6, we have
10 Ex,.. @ 8r 00| Eg (V | 11
Therefore (A)} is uniformly bounded for A Since Ex..y. 10 - 001
- 110111 and
Eg- (0 ||0 1| = 1, we have
d dA Eg No0. Nn |0nn 0" = Eg NN 11a dx Ex..y |0.m - 8* -011 21.
d
As result, (A)) is uniformly equicontinuous for and in particular À E (0, M] for any M > O. Therefore (A) can be extended continuously to [0, MJ and the family of extended functions still uniformly bounded and uniformly equicontinuous. Recall that 0" ~(O, La). we have 8' ~ NO, Ta). As in Equation (19), write l' in a row-partiiioned form
0
0'
A
where 0g Rd, Then ||I1,01|, = 110/12 (d.)
((dh) V as n, d; +00
d;
and nt/d; + Y. where = (75 EjE(m) 75 to h(), n..... ). By the Arzela-Ascoli theorem, lim, fa( = h(A, ...... 7m) uniformly on [0, M). Therefore, as d; and n/d, Yi by Lemma 8, we have
1
By Theorem 1, [A)} converges pointwise, say,
inf Be-~M(0, Ex.,y. 1onn -001 + inf I(A, ......, 7m) XE(O.M]
AE(o,M)
Recalling OBayes (Xn,yn) arg ming 1011
1x
022s n
and
R, Egr ||oaaess (Xn
0r 27 inf Egg Bi | 1 0-1 X20
x.
For all M > Cm == 20 Eielmi 1 2 odd (recall d
Eielml ) we have
75
inf (/s (Aand 0r XE(O.M]
inf Bo-~N Ex,.y. @ 0r|13
220
inf h(A, "i...., 7m). AE(O.M]
44

---

Under review as a conference paper at ICLR 2022
The uniqueness of limits implies that in M] h(A, ...... 7mm is independent of M as long M o². As result, if M Cas, inf h((,, ..... 7m), which yields
have inf xn h(1, ...... -Ym)
inf 100 0xan 0 X
+ inf h(,, : mm)
(52)
A20
Equation (50) implies imf 1(A,, ....... 7m) is decreasing in every Tv- Combining Equation (51) and Equation (52) gives
inf Ex..y [2nn =01 + inf h(A, 71 Tm 200
A20
45


Reviews:
[{"review_id": "qb0PNr557WV", "reviewer": "Reviewer_Xsqg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths of the paper:\n1.\tThe paper tackles an important problem very relevant to the ICLR community.\n2.\tIt provides a deep theoretical analysis of a specific setting and the proofs appear non-trivial. The main contributions of the paper are novel.\n\n\nWeaknesses of the paper:\nOverall the paper is reasonably well-written but the writing can improve in certain aspects. Some comments and questions below.\n1.\tIt is not apparent to the reader why the authors choose an asymptotic regime to focus on. My understanding is that the primary reason is easier theoretical tractability. It would help the reader to know why the paper focuses on the asymptotic setting.\n2.\tIt is unclear in the write-up if sample-wise descent occurs only in the over-parameterized regime or not. Pointing this explicitly in the place where you list your contributions would help. More broadly, it is important to have a discussion around these regimes in the main body and also a discussion around how they are defined in the asymptotic regime would help.\n3.\tThe paper is written in a very technical manner with very little proof intuition provided in the main body. It would benefit from having more intuition on the tools used and the reasons the main theorems hold.\n4.\tGiven that prior work already theoretically shows that sample-wise multiple descent can occur in linear regression, the main contribution of the paper appears to be the result that optimal regularization can remove double descent even in certain anisotropic settings. If this is not the case, the paper should do a better job of highlighting the novelty of their result in relation to prior results.\n\nI am not too familiar with the particular techniques and tools used in the paper and could not verify the claims but they seem correct.", "summary_of_the_paper": "The paper builds on a very recent line of work studying the “multiple descent” phenomenon. \nMultiple descent is known to occur along many axes: (i) number of parameters, (ii) train time, (iii) amount of train data. The current paper focuses on studying the theoretical rates for (iii) in the asymptotic regime where the number of samples and the dimensionality of data tend to infinity at similar rates.  This covers both under and over-parameterized settings.\nIn this limiting regime, the main results of the paper are:\n1.\tComputing formulae for the excess risk of the least squares estimator and the ridge regression estimator in a specific setting.\n2.\tUsing 1, they show that if the covariance matrix of data is ill-conditioned, then multiple descent can happen.\n3.\tThey also show that under an assumption on the scaling of the projections of the true parameter to the eigen-spaces of the eigenvalues of the covariance matrix, an optimal amount of regularization ridge regression estimator avoids multiple descent even in anisotropic settings which is novel.\n\n", "summary_of_the_review": "The problem of multiple descent is an important scientific question which is relevant to the ICLR community. The contributions of the current paper are novel. The techniques used appear novel as well. However the degree of significance of the results is not fully clear. The paper would benefit from a deeper discussion around this.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Zm5ui6Daks6", "reviewer": "Reviewer_6s7y", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This authors devoted a lot of effort to rigorously prove the generalization error formulas in the proportional limit.  \nUnfortunately, my impression is that most of the theorems in this submission are essentially re-derivation of existing results from the following papers (some of these prior results actually allow for weaker assumptions):   \n* Dobriban and Wager, Annals of Statistics 2017. https://arxiv.org/pdf/1507.03003.pdf. \n* Wu and Xu, NeurIPS 2020. https://arxiv.org/pdf/2006.05800.pdf. \n* Richards et al., AISTATS 2021. https://arxiv.org/pdf/2006.06386.pdf.\n* Amari et al., ICLR 2021. https://arxiv.org/pdf/2006.10732.pdf.  \n\nNote that all of these papers have been publicly available for more than one year, so I think it is no longer the case that this new submission can be considered as concurrent work. \n\nSpecifically,   \n1. in terms of the risk formula, [Wu and Xu] and [Richards et al.] derived the limiting risk under the same problem setup for general regularization parameter $\\lambda$, whereas [Amari et al.] focused on the bias-variance decomposition in the ridgeless limit. All these works built upon a generalized Marchenko-Pastur theorem, as well as [Dobriban and Wager], which showed that the limiting variance can be related to the Stieltjes transform and its derivative (sometimes referred to as the \"derivative trick\"). \nThese results cover Theorem 1 and 2 in the current submission. \n2.  The two block ($m=2$) case was already studied in Section 3 of [Richards et al.], Appendix A.4 of [Amari et al.], and Section 5 of [Wu and Xu]. In particular, the closed-form expression of the Stieltjes transform (and therefore the limiting variance) has been derived in Appendix A.6 of [Richards et al.] and Appendix D.10 of [Amari et al.], and the resulting \"multiple descent\" has also been reported. These results cover Theorem 3 and Corollary 2 in the current submission. \n3. Theorem 4 in this submission is analogous to Proposition 7 in [Wu and Xu], which states that under an isotropic prior on the true parameters $\\theta^*$, the optimally-tuned ridge regression estimator has monotonically decreasing generalization error with respect to $\\gamma=n/d$, and thus avoids multiple descent; this is basically equivalent to the projection formulation in Theorem 4 (the bias term in the generalization error only depends on the projection of $\\theta^*$ onto the eigenspace of $\\Sigma$).  \n\n\n**Additional Comments** \n\n- At a high level, I personally do not find counting the number of peaks in the risk curve to be that interesting of a research problem, as least in the case of minimum $\\ell_2$-norm interpolation. It is rather intuitive that one can engineer the features such that the sample covariance matrix becomes ill-conditioned once in a while, and it is not clear if this specific phenomenon has wider implications in practical machine learning problems. \n\n- (minor) Note that the Gaussian assumption has already been relaxed to bounded moments in the Stieltjes transform-based analysis, e.g., [Dobriban and Wager] and [Wu and Xu]. Hence I'm not sure if there's any benefit of introducing CGMT to this problem (which limits the analysis to Gaussian features). \n\n- (minor) In Corollary 2, why is $\\varrho\\to\\infty$ a well-defined limit? Intuitively, wouldn't this violate the condition that the eigenvalues do not depend on $d$ which goes to infinity?", "summary_of_the_paper": "Derived the asymptotic generalization error (squared loss) of the minimum $\\ell_2$-norm interpolator under general Gaussian design. The precise asymptotic formulas reveal that the risk curve can be non-monotonic and exhibit multiple peaks (in the variance term), depending on the spectral properties of the feature covariance matrix $\\Sigma$. ", "summary_of_the_review": "Due to the significant overlap with prior results, I cannot recommend acceptance. I'm happy to adjust my score if the authors can clarify how the current submission differs from (and improves upon) all the aforementioned papers. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Q1g8kEobQjF", "reviewer": "Reviewer_RwFH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and technically sound as far as I can tell. I enjoy reading Theorem 1, which uses two different approaches to derive the same limits in a way that can mutually corroborate each other, and believe this closed-form result will have future impact on other topics. The theoretical result is further supported by clean experiments up to high precision. I believe it is a mathematically strong paper that is among top quality in this venue.\n\nHowever, I have reservations regarding the motivation, at least it is not nicely explained.\n1. As the title suggests, the authors are working on sample-wise multiple descents. They made this clear in the INTRODUCTION by citing (Nakkiran et al.,2021;Chen et al., 2020b; Min et al., 2021). However, I believe the authors are working on something else by their setup in section 1.1 'Asymptotic Regime' as $n,d\\to\\infty$. In words, not only the sample size goes to infinity but also the feature size goes to infinity in proportion. First of all, this is not sample-wise descents in prior works, where $d$ is fixed! A better description of this work is on sample-feature-wise multiple descents. Second, this seems to limit the application as in most tasks the number of features is fixed. Whether the theoretical results in this work shed any light on real cases needs at least empirical evidence.\n2. Can the authors give some motivation on why to assume $\\|\\Pi_i\\theta^*\\|_2→\\eta_i$. I understand its use in theory but what does this assumption mean in words?\n\nOther minor points: the paper seems very sloppy, e.g. Page 4 'Bias-Variance Decomposition of Expected Excess Risk', the first line of equations misses a square; in CONCLUSION section, the first sentence should have ridge regression besides ridgeless; in the same section, \"risk curve.Moreover\"->\"risk curve. Moreover\"; there are multiple places where the lines are out of margin, e.g. Equation (8); the appendices are not well-referenced, e.g. after reading Theorem 1, I tried to look for the proofs but there is no hyperlink that should link to Appendix C. Same thing happens to other results wherever appendices should be clearly referenced.", "summary_of_the_paper": "This paper studies the generalization risk of ridge and ridgeless linear regression under Gaussian data and Gaussian noise settings. The limiting bias and variance are described in closed-form. The analysis leverages random matrix theory and CGMT. The authors show that sample-wise multiple descent phenomenon can take place or be avoided if optimal regularization is applied.", "summary_of_the_review": "This paper is technically very strong and well-supported by experiments. I believe it is among top 20% of accepted ICLR papers. However, the motivation of the problem is less clear which requires non-trivial improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2a4vQNSThgF", "reviewer": "Reviewer_7ii8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n* The paper is well written\n* Technical contributions are sound and somewhat interesting\n\nWeaknesses\n* Some assumptions are unclear if they are mild or why they are assumed in the first place. For instance, assuming fixed eigenvalues looks like a rather strange assumption at first glance, and authors do not provide any intuition why this is assumed and how restrictive it is. To me, that assumption is an artifact for the proof techniques, which undermines the contributions of the paper.\n", "summary_of_the_paper": "Authors study the generalization risk of ridge and ridgeless linear regression. It is assumed that the data follows a multivariate normal distribution and there is also an assumption on the spectrum of the covariance matrix. Among the contributions, the authors show a formula for the limiting bias and variance, show that sample-wise multiple descent happens when the covariance matrix is highly ill-conditioned, and study optimal regularization.", "summary_of_the_review": "After my first read of the paper, I am recommending a weak accept. My concerns are more about the assumptions and the lack of discussions about them. I would appreciate it if the authors can comment on this matter.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors analyze linear regression with gaussian covariates in an
asymptoptic setting, where the number of examples and the number of
covariates go to infinity together.  They identify conditions
on the covariance under which "multiple descent" occurs, and
conditions under which a regularization removes this effect.

Concerns were raised that the overlap between this paper and previous
research was too substantial for it to be published in ICLR.  These
persisted after the authors' response and the discussion period.
Decision: Reject