Multiple Descent: Design Your Own Generalization Curve
Authors: Lin Chen
Yifei Min
Mikhail Belkin
amin karbasi
Venue:  (2021)
Keywords: multiple descent
interpolation
overparametrization

Abstract: This paper explores the generalization loss of linear regression in variably parameterized families of models, both under-parameterized and over-parameterized. We show that the generalization curve can have an arbitrary number of peaks, and moreover, locations of those peaks can be explicitly controlled. Our results highlight the fact that both classical U-shaped generalization curve and the recently observed double descent curve are not intrinsic properties of the model family. Instead, their emergence is due to the interaction between the properties of the data and the inductive biases of learning algorithms. 

Under review as a conference paper at ICLR 2021
MULTIPLE DESCENT: DESIGN YOUR OWN GENERAL- IZATION CURVE
Anonymous authors Paper under double-blind review
ABSTRACT
This paper explores the generalization loss of linear regression in variably parame- terized families of models, both under- parametrratte and over peraammeettiiz We show that the generalization curve can have an arbitrary number of peaks, and moreover, locations of those peaks can explicitly controlled. Our results high- light the fact that both classical U-shaped generalization curve and the recently observed double descent curve are not intrinsic properties of the model family, In- stead, their emergence is due the interaction between the properties of the data and the inductive biases of learning algorithms.
INTRODUCTION
The main goal of machine learning methods is to provide an accurate out-of-sample prediction, known generalization. For fixed family of models, common way to select model from this family is through empirical risk minimization, i.e., algorithmically selecting models that minimize the risk on the training dataset. Given variably parameterized family of models, the statistical learning theory aims to identify the dependence between model complexity and model performance. The empirical risk usually decreases monotonically as the model complexity increases, and achieves its minimum when the model is rich enough to interpolate the training data, resulting in zero (or near- function of model complexity
zero) training error. In contrast, the behaviour of the test error is far more complicated. Indeed, in this paper we show how to construct a model family for which the generalization curve can be fully controlled (away from the interpolation threshold) in both and wver-parameterized regimes. Classical statistical learning theory supports U-shaped curve of generalization versus model complexity (Geman et al. 1992 Hastie et al.) 2009). Under such a framework, the best model is found at the bottom of the U-shaped curve, which corresponds to appropriately balancing under-fitting and over-fitting the training data. From the view of the bias-variance trade-off, higher model complexity increases the variance while decreasing the bias. A good choice of model complexity achieves a relatively low bias while still keeping the variance under control. On the other hand, model that interpolates the training data is deemed to over-fit and tends to worsen the generalization performance due to the soaring variance.
Although classical statistical theory suggests pattern of behavior for the generalization the interpolation threshold, it does not describe what happens beyond the interpolation threshold, commonly referred as the over-parameterized regime. This is the exact regime where many modern machine learning models, especially deep neural networks, achieved remarkable success. Indeed, neural networks generalize well even when the models are complex that they have the potential to interpolate all the training data points (Zhang et al., 2017 Belkin et al. 2018b Ghorbani al. 2019 Hastie al. 2019).
up to
Modern practitioners commonly deploy deep neural networks with hundreds of millions or even billions of parameters. has become widely accepted that large models achieve performance supe- rior to small models that may be suggested by the classical U-shaped generalization curve (Bengio ct al. 2003 Krizhevsky et al. 2012 Szegedy et al., 2015 He et al. 2016 Huang et al. 2019). This indicates that the test error decreases again once model complexity grows beyond the interpolation
threshold, resulting in the so called double-descent phenomenon described in (Belkin et al. 201 Sa), which has been broadly supported by empirical evidence (Neyshabur et al. 2015 Neal et al. [0088] Geiger et al. 2019; 2020) and confirmed empirically on modern neural architectures by Nakkiran al. (2019). On the theoretical side, this phenomenon has been recently addressed by several works

---

Under review as a conference paper at ICLR 2021
on various model settings. In particular, Belkin et al. (2019a) proved the existence of double-descent phenomenon for linear regression with random feature selection and analyzed the random Fourier feature model (Rahimi & Recht 2008). |Mei & Montanari (2019) also studied the Fourier model and computed the asymptotic test error which captures the double-descent phenomenon. [Bartlett et al. (2020); Tiiller & Bartleu (2020) analyzed and gave explieit conditions for "benign overfitting" in linear and ridge regression, respectively. In a recent work, [Caron & Chretien (2020) provided a finite sample analysis of the nonlinear function estimation and showed that the parameter learned through empirical risk minimization converges to the true parameter with high probability as the model complexity tends infinity, implying the existence of double descent.
Among all the aforementioned efforts, one particularly interesting question is whether one can ob- serve more than two descents in the generalization curve. In recent work, d' A'Ascoli et al. (2020)
empirically showed a sample-wise triple-descent phenomenon under the random Fourier feature model. Similar triple-descent was also observed for linear regression (Nakkiran et af., 2020). More rigorously, Liang et al. (2020) presented an upper bound on the risk of the minimum minimum-norm inter- polation versus the data dimension in Reproducing Kernel Hilbert Spaces (RKHS), which exhibits multiple descent. However, bound does not imply the existence of a multiple-descent generalization curve. In this work, we study the multiple descent phenomenon by addressing the following questions:
multiple-descen
upper bound without a properly matching lower
Can the existence of a multiple descent generalization curve be rigorously proven?
Can arbitrary number of descents occur?
Can the generalization curve and the locations of descents be designed?
In this paper, we show that the answer to all three of these questions is yes. Further related work is presented in Appendix A
Our Contribution. We consider the linear regression model and analyze how the risk changes as the dimension of the data grows. In the linear regression setting, the data dimension is equal to the dimension of the parameter space, which reflects the model complexity. We rigorously show that the multiple descent generalization curve exists under this setting. To our best knowledge, this is the first work proving a multiple descent phenomenon for any learning model.
Our analysis considers both the underparameterized and overparameterized regimes. In the over- parameterized regime, we show that one can control where a descent or an ascent occurs in the generalization curve. This is realized through our algorithmic construction of a feature-revealing process. To be more specific, we assume that the data is in R.D. where 1) can arbitrarily large or even essentially infinite. We view each dimension of the data as a feature. We consider linear regression problem restricted on the first features, where d < D. New features are revealed by increasing the dimension of the data. We then show that by specifying the distribution of the newly revealed feature to be either a standard Gaussian or a Gaussian mixture, one can determine where an ascent descent occurs. In order to create ascent when new feature is revealed, it is sufficient that the feature follows a Gaussian mixture distribution. In order to have descent, is sufficient that the new feature follows standard Gaussian distribution. Therefore, in the overparameterized regime, we can fully control the occurrence of a descent and an ascent. As a comparison, in the underparameterized regime, the generalization loss always increases regardless of the feature distri- bution. We also consider a dimension-normalizee normalized version of the generalization loss, under which we show that the generalization curve exhibits multiple descent in the underparameterized regime. Generally speaking, we show that we are able to design the generalization curve.
On the one hand, we show theoretically that the generalization curve is malleable and can be con- structed in an arbitrary fashion. On the other hand, we rarely observe complex generalization curves in practice, besides carefully curated constructions. Putting these facts together, we arrive at the conclusion that realistic generalization curves arise from specific interactions between properties of typical data and the inductive biases of algorithms. We should highlight that the nature of these interactions is far from being understood and should be an area of further investigations.
PRELIMINARIES AND PROBLEM FORMULATION
Notation. For x E R and d < D, we let a11 : d E Rd denote a d-dimensional vector with x|1 d) x; for all S < d. For matrix A Rexd we denote its Moore-Penrose pseudoinverse by
2

---

Under review as a conference paper at ICLR 2021
A+ E Raxn, We use the big O notation O and write variables in the subscript of O if the implicit constant depends on them. For example, On.d, (1) is a constant that only depends on n, d, and a.
fa) and g(o) are functions of o, write f(o) g(o) if lim f(a) = 1. It will be given in the context how we take the limit.
g(a)
Distributions. Let 02) (u, E I) and N(, 2) (μ E R" L E R=x*) denote the univariate
and multivariate Gaussian distributions, respectively, where I R" and Σ |xxx= is positive semi-definite matrix. We define family of trimodal Gaussian mixture distributions as follows
N Namix
NV a²
1 N [N(-,, NN(,,
o(,
For an illustration, please see Fig.
0.
0.3
M
0.8
4.4
02
033
03
0.1
00
(a) (O), 1) feature
(b) Aaa feature, (a 0.3)
(c) feature, (a = 0.2)
Figure 1: Density functions of the ((, 1) and W feature. new entry is independently sampled from the 1-dimensional distribution being either a standard Gaussian or trimodal Gaussian mixture. Smaller a leads to higher concentration around each modes.
Let (2,, A) denote the noncentral chi-squared distribution with & degrees of freedom and the non- centrality parameter A. For example, if X, NN,,, 1) (for 1.2...., k) are independent Gaus- sian random variables, we have E X? ~ (k, A). where À = Ei= n²- We also denote by xk) the (central) chi-squared distribution with & degrees and the F didtttributton by F(d1, d2) where dj and d2 the degrees of freedom.
Problem Setup. Let #1...., In IR be column vectors that represent the training data of size and let Fiest R² be column vector that represents the test data. We assume that they are all independently drawn from a distribution
itd D.
F Fay Frest
Let us consider a linear regression problem on the first d features, where d < D for some arbitrary large D. Here, d can be viewed as the number of features revealed. The design matrix A equals [z1]] [1 .I....,,,u, 2I[ d|j E Ra The true linear model is 8 Rd The noise R" follows the multivariate standard Gaussian distribution. NO0, 2 I.)) Let x = Zres[[ : d) denote the first features of the test data.
For the underparameterized regime where d < n, the least square solution on the training data is A+ AA,3* + +)) For the overparameterized regime where > n, A+ *AA3" + the minimum-norm solution. In both regimes we consider the solution 3 & A+ (A3* + E). The excess gemeralization loss on the test data is then given by
T 33) 2 - (y--x TT)
La
x (T - 8+)) 27
E
(x ((A+ 1)3² + + [|
E
E
[ ((TTAA---N)) 118 + [ At&)2]
IE (x (A=T(A-A-A)) 11 + =
3

---

Under review as a conference paper at ICLR 2021
where y x gr + Elest and Eest nf) We call the term E [x (A* 1- - the bias and call the term 2 (I(AT) In this paper, we assume and the noise level 1) 1. this settings, we get
the variance.
La (AT)
Remark 1. In the underparametrized regime, if D is continous distribution (our construction presented later satisfies this condition), the matrix A has independent column almost surely. this case, have A+ A = 7 and therefore the bias E [(x: _ (A+ A T),9*)3 ) vanishes irrespective of the true linear model 3 In other words, in the underparametrized regime, La equals 17 (AT) for all B*.
We would like to study the change in the loss caused by the growth in the number of features re- vealed. Note that the product (A+) x sums over d dimensions. Once reveal new feature, which
[ b
TT
equivalent to adding a new row 6 to A and new component y to z, the product
sums over d + dimensions. As result, compare quantities of different dimensions, need to normalize the generalization loss by the dimension. We define the dimension-nnomallzze general- ization loss L/ follows
I'a E d
La
d
Local Maximum and Multiple Descent. We say that a local maximum occurs at dimension d 2 if 1/ L' and E' 1/411 Intuitively, local maximum occurs if there is an increasing stage of the generalization loss, followed by a decreasing stage, as the dimension d grows. Additionally, we define L & -oo. If the generalization loss exhibits a single descent, based on our definition, unique local maximum occurs d For double-descent generalization curve, a local maximum occurs at two different dimensions. In general, if we observe a local maximum at K different dimensions we call it K-descent.
UNDERPARAMETERIZA REGIME
First, we present our main theorem for the underparametrized regime below, whose proof is deferred to the end of Section 3 It states that the un-normalized generalization loss La is always non- decreasing as grows. Moreover, is possible have an arbitrarily large ascent, i.e., La+1 La > C' for any C' >>0 0.
Theorem 1 (Proof in Appendix B.I. If d < we have La+1 2 distribution. Moreover, for any C 0, there exists a distribution D such that Ld+1 Lo > C.
La irrespective of the data
For the dimension normalized generalization loss L'g. there be both ascents and descents. And is possible to specify where the local peaks the generalization curve occur.
ciimensionnnommalized
Theorem (Underparameterizeed regime). Let D + < 22n. For any 1 < d1 < d2 <222... .... < dx < D where dj+1 1 dj 2 2, there exists a distribution D such that local maximum of the Lt2 curve occurs at d,.
Note that the assumption dj+1-44 1 2 2 is necessary because two local maxima may not be adjacent.
We present an example in Fig. 2
Remark (D can be product distribution). As will be clear later in the proof of Theorem the
distribution D can be made as simple as product distribution D = Dj x ... X DD such that Fijj itd D, for all < S n, where D, is either sampled from A/ 1) or Gaussian mixture Ammix for some o, > As a consequence, by permuting the order of D.'s the product distribution, can change the order of revealing the features.
Remark 3 (Kernel regression on Gaussian data). In light of Remark 2 D can be chosen to be product distribution that consists of only NO, 1) and Amix, Note that can simulate A/mix
4

---

Under review as a conference paper at ICLR 2021
Local Max
Local Max
Local
[o, A
(o, 1) N
(o
6
11 14
Dimension data d
Figure 2: Illustration of multiple descent for the dimension-normaaized generalization loss T as function of the dimension d. A local maximum occurs d if 4/-1 L'd L' The triplet I'g-1 L'g. I'a+1 then form an ascent/descent, which is marked by the shaded area. Local maxima are marked by the dotted lines. Adding a new feature with a Gaussian mixture distribution increases the loss, while adding one with a univariate Gaussian distribution decreases the loss. Therefore, Gaussian mixture feature followed by Gaussian feature creates one ascent/descent.
with (N0 1) through the inverse transform sampling. To see this, let Fx and Fage be the edf of (V( 1) and N respectively. If X 1), have F) Unif( 1)) and therefore @o (X) Aatay (Fx(o.1)(X)) ~ Narr fact, we can use multivariate Gaussian D' ((O,TDxXD) and sequence of non-linear kernels k(L (ar, y) & (ollidd (ilid where the feature map af (x) A |o (x1), (222)). (a()....))a()))
Rd Here is simple rule for defining Øy: D; = (0, 1). we set Φy to the identity function. If Dj = ANaaii we set dj to SPay. Thus, the problem becomes kernel regression problem on the standard Gaussian data.
Getting back Theorem 2 us discuss how we will construct such a distribution DD inductively. We fix Again, denote the first features of Tiss by x - Treu[1 : d]. Let us consider adding an additional component to the training data x [1 d]. ..,
d] and test data so that we increment the dimension by 1. Let b; E denote the additional component that we add to vector v; (so that the new vector is [x,[1 d] b,)T. Similarly, let E R denote the additional component that we add to the vector z. We form the column vector [b,....,buy E I" that
collects all additional components that add to the training data.
We consider the change in (dimension-normalizee) generalization loss as follows
A
L441 Lt
(1(A)
TT
y
(I)
1
(At))
L/411 L's
+
bT
y
Note that the components bi..... bn, y are i.i.d. Lemma relates the pscudo-inverse [A, to that of A
Lemma 3 (Proof in Appendix B.2h. Let A E Igaxd and O + b R where > d 1. BTT
Additionally, let P AA+ and Q = b6+ = 16p and define 2 & (T If z # and the columnwise partitioned matrix [A, b) has linearly independent columns, have
ATT TT
= [
NT |bb
[I+
66 (A+)T
(I-AA!))
||bl -6 D AA-
161 AA
A
[T- Q] + 1-tr(PQ) (A+)
(I-P)b
(J-PPP
- (A)(T "
5

---

Under review as a conference paper at ICLR 2021
In our construction of D, the components Dj all continuous distributions. The matrix I- P is an orthogonal projection matrix and therefore rank( - P) = n As a result, it holds almost surely that 6 * 0, # O, and [A, b] has linearly independent columns. Thus the assumptions of Lemma are satisfied almost surely. In the sequel, we assume that these assumptions are always fulfilled.
Lemma 4 (Proof in Appendix B.3). Assume d, d + 2 and P are fixed, where P Raxx is an orthogonal projection matrix whose rank is d. Define
(I-P)b where = [b,,,.., b,....,,]]] bn] E IR".
||b|1
If y: by.... bn iid Ntnix we have B = On (1) and RRly /b (1 P)b] = O On,do (1).
Theorem provides an upper bound for the following quantity
E
(at) T x
A,
d+1
if bi,..., bn, y are i.i.d. according to .V(0,)) 1) or N This quantiry is similar to the difference between the dimension-normalizze generalization loss E It but with expectation only over b and y-
Theorem 5 (Proof in Appendix B.4). Conditioned on A and the following statements hold:
(a) If + < 22n and bi.....
......., bn y
sid
N(O, 1). we have
Es
A
(A+)
(((A))=11(((2))) (d 2) d(d + 1)2(n 2)
(2)
d+1
(b) If +2 < n and bi.....
bys y
sid ~
Nuris
we have
( al|
Enyy
(1),
d
where On,d,o (1) is universal constant that only depends on d and a.
Corollary 6. Assume d + 2 < /2n. If either bi..... bn. sid and by taking expectation over all random variables, we have
~ N(0, 1) or bi...., b ~ Narx
odd
On,d. (E) (AA))
d
T
We will use Theorem 5 in two different ways. The first way is presented in Corollary 6 like show inductively (on d) that T'a is finite for every d. Provided that able to guarantee finite E Corollary iiplies that T'y is finite for every if the components are always sampled from (0, 1) or Mais.
We would
Alternatively, we can use Theorem to create a descent, i.c., make L'at1 < L/g- light of 2 to make the left-hand side negative, need
d d- (-II(At) TT =2) (d+ 0,
which is equivalent to
2 1 (At)
1
x
d(2n - (d + 2))²
One we take expectation over A and x, we need the above equation to hold in expectation in order create a descent, i.e.,
L' d(2n (d + 2))²
Provided that L'2 can be made sufficiently large, letting L'p satisfy the above inequality and then adding additional (0, 1) entry will lead to 1'441 achieved by adding an entry sampled from A mix when the data dimension increases from 1 to in the previous step. Indeed, Theorem 7 shows that adding a A /mix feature can increase the loss by arbitrary amount.
L'g. Making a large L'g in turn, can be

---

Under review as a conference paper at ICLR 2021
Theorem 7 (Proof in Appendix
B.5 For any C >
and E
(|[(A x012 400, there exists
such that if ....... nn y
Rid
Mai we have
E
[|(At)==]1
>,
M
A +
7 (A+) x =
1
1
E
>C
d
b
y
We are now ready to prove Theorem
2
Proof of Theorem
2 We construct D inductively. Let D, - (0, When d = 1, we have
A [ dl..................... .n, d]] [21,1..... Fn,1] 1 R
which is a column vector. Therefore, A+ =
As a result, we get A ||
|x|² ||
4 = E (A+)) E
2
where x ~ (O, 1) and |A|l ~ (n).
Since we will set Dj (for 2 2) to either NNO, 1) or Nu by Corollary 6. we have D/j41 Onj.o,- (L)). By induction, obtain that L2 finite for all 1 i
We define do & O. Assume that we have determined distributions D Dı...., Dd, +1 where 0 S j <
K. We set Day+2..... -1 to N 1). For Da,.: by Theorem 7 we pick od,+1 such that if Dajt1 Od,+1"
Ammix we have
L'ajt1 > max L'a L'afti-1 di+i (2n - (dz+1 + 2)2)
(3)
Next, we Dd141+1 (), Taking the expectation of (2) in Theorem over all random variables, we have
dst1 43 (2n (d,+1 2)
L' L'a I' S d=+1(ds+1 + 1) 4 2)
< 0,
where the last inequality is due to So far we have constructed local maximum at dj+1. By induction, we conclude that local maximum occurs every d,-
L
Remark 4. From Remark 2 and the proof of Theorem 2 it is clear that D Di a product distribution. The construction in the proof also shows that the generalization curve is actually determined by the specific choice of the D.'s. Note that permuting the order of D,'s 's is equivalent to changing the order by which the features are being revealed (i.e., permuting the entries of the data x; 's) Therefore, given the same data points T1, FT, E RDD we can create many different generalization curves simply by changing the order of the feature-revealing process.
Dn is
4 OVERPARAMETERIZED REGIME
In this section, we study the multiple decent phenomenon in the overparameterized regime. Note solution here. As stated in the following theorem, we require d 2 n 8, which means d starts at roughly the same order as n. In other words, the result covers almost the entire spectrum of the overparameterized regime.
that stated in Section 2 consider the minimum-
Theorem 8 (Overparameterized regime). Let < D - 9. Given any sequence A Ant9.
A D where Aa {t.t), there exists a distribution D such that for every n + 8 < d 1, we have
>> Lai A
{> Lig <
if Aa
L
D'an
Lai =A==
L/
if = 1
7

---

Under review as a conference paper at ICLR 2021
Ania
Ants
Am400
Autil
An-12
Anti
La Lit
t
nH8
n+9
n+10
n+11
n+12 n+13 n+14
Dimension of data d
Figure 3: Illustration of the multiple descent phenomenon for the generalization loss Le (or the dimension dimension-normalizee normalized generalization loss L3) versus the dimension of data d in the overparameter- ized regime starting from d decrease as specified by the sequence = {4, 1:4: f,hh...... }. Adding new feature with Gaus- sian mixture distribution increases the loss, while adding one with Gaussian distribution decreases the loss.
8. One can fully control the generalization curve to increase
In Theorem the sequence An+8, Ant9, ... D just used to specify the increas- ing/decreasing behavior of the T'a sequence for d > 8. Compared to Theorem 2 for the un- derparameterized regime, where one able to fully control the ascents but only partially control the descents, Theorem indicates that one is able fully control both ascents and descents in the overparameterized regime by placing an ascent/descent wherever one desires. Fig. 3 illustrates an example.
Lemma gives the pseudo-inverse of when > n.
Lemma 9 (Proof in Appendix C.I). Let A Raxd and R=x!, where n S d. Assume that matrix A and the columuwise partitioned matrix B & [A, have linearly independent rows. Let GTG
G a (AAT)-1 Rax" and u -
&R' 1x We have
1+bT Gb
A 6
[1 - bu) (At)
Lemma 10 establishes finite expectation for several random variables. These finite expectation re- sults necessary for Theorem 11 and Theorem 12 to hold. Technically, they are the dominating random variables needed in Lehesgue's dominated convergence theorem. Lemma 10] indicates that the first n 8 distributions
guarantee these finite expectations, suffices normal distribution and then set D.+s..... DD to either Gaussian or Gaussian mixture distribu- tion. In fact, Theorem and Theorem we always add a Gaussian distribution or a Gaussian mixture.
the standard
Lemma 10 (Proof in Appendix
Let D D1 x
x Dp be a product distribution where
(a) Da = if 1f
8; and
(b) Da is either (0, o.) or Nami for > n +
Let Diadd denote D ... x Da- Assume that every row of A E Baxd and x E [Rdx1 are i.idd. and follow Pistt- For any d such that n +8 S d S D, all of the followings hold:
B[I(A B[I(AA)Txx11 xx]1 < + x0,
B ((AAT)-1))
00,
(4)
E Amax ((AA)) (()(A))))((Aat)) (((((((+]]] Tx|l + +0,
B[A 2m ((AAT) (-)AA))))(((A)))) ( "x| 00.
Theorem feature.
shows that in order to have Laf1 < La and L/41 < L/g. it suffices to add a Gaussian
8

---

Under review as a conference paper at ICLR 2021
Theorem 11 (Appendix
C.3
If [[] 0 and all equations in 4 hold, there exists
such that if y. bi bi.....
by
Hid ~ (10, o²), we have
A
L8+1
Ld
E
(At)
<0,
y
1 +
AAT
1/ L'd
E
E
(At) x <0.
b
Theorem 12 shows that adding Gaussian mixture feature can make Lati La and E' L'
Theorem (Proof Appendix C.4 Assume ([I(A+)T=<)) +o0. For any C 0, there exist
,4, a > 0 such that ify, bi:... ... bn
sd Ammxx we have
2
A T
La+1 Ltd = E
E
(|(AA)
C,
y
TATT
L'a41 L'a
E
E 7 (At)
C
d
b
The proof of Theorem 8 immediately follows from Theorem and Theorem
12
Proof of Theorem 8 We construct the product distribution D IT Da. We set Da (0,
for d = 1 either 4 or
For
< D, Da is either (O, oz) or Nmmix depending Aa being
First show that for each step d, the assumption [AI A)* x>1= > 0 of Theorem 11 sat- isfied. If [A *)*==1]] 0, we know that (A A) x 0 almost surely. Since D is a con- tinuous distribution, the matrix has full row rank almost surely. Therefore, rank((4 +))
almost surely, which implies x & ker(A" A)+ In other words, (A A) A) o almost surely. We reach a contradiction. Moreover, by Lemma
rank(A) A A) = n almost surely. Thus dim ker( A A)+ = d - n <
10 the assumption ES| (A+ [1|2 < +oo of Theorem 12 is also satisfied.
If A = 4. by Theorem 11 there exists σa 0 such that if Da NN(0, a)), then La < La- 1 and 11 1/ Similarly if Ad-1 f. by Theorem 12 there exists aa and paa such that Da A guarantees La La-1 and It2 > I/--1-
CONCLUSION
Our work proves that the expected risk of linear regression can manifest multiple descents when the number of features increases and sample size is fixed. This is carried out through an algorith- mic construction of a Ceature-revealing process where the newly revealed feature follows either Gaussian distribution or Gaussian mixture distribution. Notably, the construction also enables us to control local maxima the underparameterized regime and control ascents/descents freely in the overparameteriiee regime. Overall, this allows us design the generalization curve away from the interpolation threshold. We conjecture that the same multiple-descent generalization curve can occur in non-lineat neural networks and we humbly suggest that entities with infinite computational powers investigate this phenomenon.
REFERENCES
Madhu S Advani and Andrew Saxe. High-dimensione dynamics of generalization error in neural networks. arXiv preprint 1711::171 2017.
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of gener- alization error in neural networks. Neural Neworrs, 132:428-44 446, 2020.

---

Under review as a conference paper at ICLR 2021
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252,, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. 8141-81500 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML, pp- 477-502, 2019b.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2019c.
Jerzy K Baksalary and Oskar Maria Baksalary. Particular formulae for the moore-penrose inverse of a columnwise partitioned matrix. Lineur algebra and its applications, 421(1):16-23) 2007.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. stat, 1050:28, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In International Conference on Machine Learning, pp. 541-549, 2018b.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.077 075571, 2019a.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contra- dict statistical optimality? In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1611-1619, 2019b.
Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. A neural probabilistic 2003.
language model. Journal of machine learning research,
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances Neural Information Processing Systems, pp. 10836-10846, 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Emmanuel Caron and Stephane Chretien. A finite sample analysis of the double descent phe- nomenon for ridge function estimation. arXiv preprint arXiv:2007. /2882, 2020.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. arXiv preprint arXiv:2009.1063 10683, 2020.
Lin Chen, Yifei Min, Mingrui Zhang, and Amin Karbasi. More data can expand the generalization gap between adversarially robust and standard models. ICMI., 2020.
Yehuda Dar, Paul Mayer, Lorenzo Luzi, and Richard G Baraniuk. Subspace fitting meets regression: The effects of supervision and orthonormality constraints on double descent of generalization errors. In ICML., 2020.
Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprint arXiv:2006. 03509, 2020.
Emesto De Vito, Andrea Caponnetto, and Lorenzo Rosasco. Model selection for regularized least- squares algorithm in learning theory. Foundations of Computational Mathematics, 5(1):59-85, 2005.
10

---

Under review as a conference paper at ICLR 2021
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019.
2019.
Mario Geiger, Stefano Spigler, Stéphane d' Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition paradigm understand the loss landscape of deep neural networks. Physical Review E, 100(1):012115 15, 2019.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' A'scolli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2)003401, 2020.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural computation, 4(1):1-58, 1992.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv: 12191, 2019.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08555 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. In Advances in neural information processing systems, pp- 103-112, 2019.
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoff's in adversarial training for linear regression. In Conference on Learning Theory, 2020.
Alex Krizhevsky, Iya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeles" regression can general- ize. Annals of Statistics, pp. to appear, 2019.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum norm norm interpolants and restricted lower isometry of kernels. In COLT, 2020.
Marco Loog, Tom Viering, and Alexander Mey. Minimizers of the empirical risk and risk mono- tonicity. Advances in Neurul Information Processing Systems, pp. 7478-7487, 2019.
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and double descent curve. arXiv preprint 0xXiv:/90..05333 2019.
Yifei Min, Lin Chen, and Amin Karbasi. The curious case of adversarially robust models: More data can help, double descend, or hurt generalization. arXiv preprint arXiv:2002.11080 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.02292, 2019.
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint arX1v:2003.01897. 2020.

---

Under review as a conference paper at ICLR 2021
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. arXiv preprint arXiv:1810.0855000 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In ICLR (Workshop), 2015.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008.
Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels a high- dimensional phenomenon. In Conference Learning Theory, pp- 2595-26233 2019.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. arXiv preprint arXiv:2006.063786, 2020.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances Neural Information Processing Systems, pp. 3215-3225, 2017.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1-9, 2015.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
Dietrich von Rosen. Moments for the inverted wishart distribution. Scandinavian Journal of Statis- tics, pp. 97-109, 1988.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, pp. 9712-9724, 2019.
Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of ad- aboost and random forests as interpolating classifiers. The Journal of Machine Learning Research, 18( 11:111581119999 2017.
and Daniel Hsu. On the number variables to use in principal component regression. In Advances in Neural Information Processing Systems, pp. 5094-5103, 2019,.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109(3)4477-492, 2020.
12

---

Under review as a conference paper at ICLR 2021
A FURTHER RELATED WORK
Our work is directly related to the recent line of research in the theoretical understanding of the
double descent (Belkin et al. 2019a| Hastie et al. 2019 Xu & Hsu 2019 Mei & Montanari] 2019) and the multiple descent phenomenon (Liang et al. 2020). Here we briefly discuss some other work that is closely related to this paper.
Least Square Regression. In this paper we focus on the least square linear regression with no regularization. For the regularized least square regression, De Vito et al. (2005) proposed selection procedure for the regularization parameter. [Advani & Saxe (2017) analyzed the generalization of neural networks with mean squared emoo under the asymptotic regime where both the sample size and model complexity tend to infinity. Richards et al. (2020) proved for least square regression in siciiiontt-smpllee size ratio d/ n grows, an additional peak can
the asymptotic regime that as the occur in both the variance and bias due to the covariance structure of the features. As a comparison, in this paper the sample size fixed and the model complexity increases. Rudi & Rosasco (2017) studied kernel ridge regression and gave upper bound on the number of the random features to reach certain risk level. Our result shows that there exists a natural setting where by manipulating the random features one can control the risk curve.
Pree-aarmmtttiiztionn and Interpolation. The double descent occurs when the model com- plexity reaches and increases beyond the interpolation threshold. Most previous works focused on proving upper bound optimal rate for the risk. Caponnetto & De Vitol (007) gave the optimal rate for least square ridge regression via careful selection of the regularization parameter. [Belkin al. (2019b) showed that the optimal rate for risk can be achieved by model that interpolates the training data. In a series of work on kernel regression with regularization parameter tending zero (a.k.a. kernel ridgeless regression), Rakhlin & Zhai (2019) showed that the risk is bounded away from zero when the data dimension is fixed with respect to the sample size. Liang & Rakhlin (2019) then considered the case when d > n and proved risk upper bound that can be small given favorable data and kernel assumptions. Instead of giving a bound, our paper presents an exact com- putation risk in the cases of underparameterized and overparameterized linear regression, and proves the existence of the multiple descent phenomenon. WWyner et al. (2017) analyzed AdaBoost and Random Forest from the perspective of interpolation.
There has also been a line of work on
wide neural networks (Arora al. 2019a c Du al. 2019 Allen-Zhu al. 2019 Wei al., 2019
Cao & Gu 2019 Advani et al. 2020 Chen & Xu 2020 Zou et al. 2020).
Sample-wise Double Descent and Non-monotonicity. There has also been recent development beyond the model-complexity double-descent phenomenon. For example, regarding sample- wise non-monotonicity, Nakkiran et al. (2019) empirically observed the epoch-wise double-descent and sample-win wise non-monotonicity for neural networks. Chen et al. (2020) and Min et al. (2020) iden- tified and proved the sample-wise double descent under the adversarial training setting, and Javan- mard al. (2020) discovered double-descent under adversarially robust linear regression. Loog et al. (2019) showed that empirical risk minimization can lead to sample-wise non-monotonicity in the standard linear model setting under various loss functions including the absolute loss and the
sasple-wise
squared loss, which covers the range from classification to regression. We also refer the reader to their discussion of the earlier work on non-monotonicity of generalization curves. Dar et al. (2020) demonstrated the double descent curve of the generalization enrors of subspace fitting problems.
B PROOFS FOR UNDERPARAMETRIZER REGIME
B. PROOF OF THEOREM
I
Proof. We follow the notation convention in I
xx
L4t1 - La E
E
)((T))
2z1
bT
13

---

Under review as a conference paper at ICLR 2021
A T
Recall n and the matrix B' fat matrices. As result, x' &
A
is size (d + 1) x n. Both matrices B' and 2 AT are
bt
x
we have
B
min ||=||-. Since {= | B'z - r'} S {= Bz æ). we get |B+t 2 |Btx||.
| r/1
min
||
||
2: aazaaa
8:
Therefore, we obtain
Ld+1 La.
The second part the theorem, which says that any C there exists distribution such that La+1 La > C, follows directly from Theorem 7
B.2 PROOF OF LEMMA
Proof. By (Baksalary Baksalary 2007 Theorem 1), we have
A 6t
(1 (1- (
(S-P)6 (I-P))
Define A ATD E RRd Since has linearly independent columns, the Gram matrix non-singular. The Sherman-Morrison formula gives
A
(IT(-Q)))--1 (AT ATA A
rr
G Gr G
G-
-G-1 +
|
| 1bp--TG-- TG-T
| G-1r
where we use the facts = b and AG-1 (AT) in the last equality. Therefore, deduce
( ||6|22 - r G-1,
A(A (1 - -)-)-1 = AG-
AG AT AT (A+)T
-A+)
|bb12 - TG-rr
AA LA+bb" bb
(At)T
| T G-1
PQ
(At)T.
r GT-
||b
Observe that
T G
6T A(A A)- AAA
6T
[|6]
1161 =
Therefore, obtain the desired expression.
B.3 PROOF OF LEMMA 4
Lemma 13 shows that noncentral x2 distribution first-order stochastically dominates a central x² distribution of the same degree of freedom. It will be needed in the proof of Lemma
Lemma 13. Assume that random variables X > 0, we have
2 A) and Y 2*),,, where À 0. For any
P(X 2 P(Y 2 c).
In other words, the random variable X (first-order) stochastically dominates Y.
Proof. Let Y1, X2,.... X₁ ddd N(O0 1) and X, ~ N(VA,1) and all these random variables are jointly independent. Then X E X? x2 A) and Y A y E x? (k).
14

---

Under review as a conference paper at ICLR 2021
It suffices to show that P(X' 2 c)
P(Y'
c). equivalently, P([ 1)1 c) >
(O, 1)] e) for all > 0 and l have
- X 0. Denote Fe(() (P 1)1 2 c) and
r - 112
c R
x²
Fe(m)= - V
exp
dx =
exp
dx,
2
2
2
and thus
dFc(u)
1
(c-
11²
12)²)
exp
exp
0.
dp
2t
2
2
This shows (( 1)1 2 c) > (O 1)1 2 c) and we are done.
Proof of Lemma 4 Since b; Rd A/mix we can rewrite a + where oN(0, and the entries of u satisfy u, rid Unif((-1,0,1)) Furthermore, u and w are independent. Note that for any fixed and d, the support of u is finite and its cardinality only depends on n. Therefore, only need to show that conditioning on the expectation over w is On.d. (1). In other words, for
any fixed u, we want to show E., [1/2 ul = On,d.a (1) and E, (1- P1b = (1)
Note that since /² first-order stochastically dominated by (1, we have
Ely 2 ul Ely" - o² =2 20
Therefore, it remains show En [1/z
(1), (u + w) T P(u (u + w) (T(I- Pbb (u + w) (I P)(u + w)
u] O dd a (1) and EnD b [T-P-Pj PJh
Note that
1 b Tb
Since P is an orthogonal projection, there exists an orthogonal transformation depending only on P such that
(u + w) P(u + w) = 10(u+ + T Da(O(u + w)] where Da = diag([1.... ..... 1......00
.......) 0)) with d diagonal entries equal and the others equal to O. We denote ū = Ou)), which is fixed (as and O are fixed), and t O(w) ~ (N0 In). It follows that
(u + 6) ( Da(ū 1
w 2i d+1 (ū: + w:
Σd Di=l
Σ (i. + n, /02
2
(ū ū)) (1 Da)(ū +w)
2i (ū: + wi 2/22
Observe that
d Σ ut
Σ iml
úu + de 02
d. d.1
n
12 Σ
Σ
(ū, + x ~ x²
n - d,
i=d+1
i=d+1
and that these two quantities are independent. It follows that
E
Σ i4s w.,) 2//)2/02
d
By Lemma 13 the denominator Di 1 (ū+ + 2/2 first-order stochastically dominates 22
d). Therefore, we have
1
1
1
E
d4 (ū+ w 0/2
2 d)
n
2
15

---

Under review as a conference paper at ICLR 2021
Putting the numerator and denominator together yields
d V Ei=1 uf
d vd
IE
+++
S1+
d-2 O (1).
n-d-2
Similarly, we have
1
1
(T
p)b
41
E
Ou + w) Da) (u + w
11
1/02
Σ a
(ū: + 22:
1
1
<
E
0
x d)
g² n 2-2
= O (1).
B.4 PROOF OF THEOREM 5
Proof. First, rewrite the expression follows
2
x
(At)
1
d+1
bT
V
(S)
(I (1-Q))
2
(I- 6 61 Pyb
-
1
x012
(d + 1ya
d
where P, = are defined Lemma 3 Since y has mean and is independent of other random variables, so that the cross term vanishes under expectation over and yy:
Esy ( (T-+
(1-P)6 =0, PQ/=)att))) x, bT P)b )
where () denotes the inner product. Therefore taking the expectation of (5) over b and yields
/ (At)T
(6)
d +
b
EB,y
|11 (1--111 () P0(=(A//=)AA)) xx12 d ((At) T +
1
(I - P)b
(d l)z
(d + 1)²
TT PTb
1 (d + 1)2
(1=0)(++Q/>>3a++)) (1 (1(At) 2
(I- P)b
Es.y
bT P)b y/
We simplify the third term. Recall that I - P - P AA+ is an orthogonal projection matrix and thus idempotent
(I- P)b
y2
y²
(1 ?)b|2 DT(I - P}b
(9)
PJb"
(b - PJb)2
16

---

Under review as a conference paper at ICLR 2021
Thus have
|]
En
d+1
A
b
x
y
-
7 (at)
(10)
1 (d + 1)2
[[|- [[1-Q])++Q/>44+++
x11 (1 (((AAt)
x112 +
y²
bT p)b
(11)
We consider the first and second terms. We write (A+)Tx x and define of the first and second terms equals
b¹ (1-P1)
The sum
1611
1 2101/ TM + t8)u
-
(12)
where 5 + and
QQ+QP
(2- QPQ + QPQQQ
1 22
M - Q
2²
The rank of M most 2. To see this, we re-write M the following way
P +
2
2
PQPQ
PQ
M = Q
PQ
P M1 + M2
22
Notice that rank (M) - rank(Q). rank(Ma) S rank(Q), and rank(Q) 1. follows that rank(M) S rank(M)) + rank(M, = 2. The matrix M has at least n - 2 zero eigenvalues. We claim that M has two non-zero eigenvalues and they are - 1/2 < 0 and
Since
rank(PQ) S rrank(Q)
and
tr(PQ) T Ph
||bl2
2,
thus PQ has unique non-zero eigenvalue 2. Let u * O denote the corresponding eigenvector such that PQu - z)u. Since im P and a projection, we have Pu u. Therefore can verify that
Mu (1 )
To show that the other non-zero eigenvalue of M is 1, we compute the trace of M
tr(M) tr(Q) PPQ()))
2 1
tr((PQ)))
+
tr(PQ)+
z2
22
where we use the fact that tr(() =1 (etrr(Qq PQ)
= 12
tr((PQ)))= tr P66 P66
tr (6 (b) Pb)
(1 2)²
|bb|
|b]
We have shown that M has eigenvalue 1 - 1/2 and M has at most two non-zero eigenvalues. Therefore, the other non-zero eigenvalue is ttr(MMM (M) - (1 - 1/2) 1.
We are now in position to upper bound 12 as follows:
TM + 87) < -(1 - 1/= 0)]1=]1 < -1 -1- 1/= 1/2
Putting all three terms of the change in the dimensiion-normalized generalization loss yields
1
(
E
+
bT
3/
y²
Eb.y
-(1
1/2 + 2/1)/1012
(d
1)²
b (I P)b
17

---

Under review as a conference paper at ICLR 2021
For bi....,bb bn. y sid (0, we have Ely?] = 1. Moreover, b" bT (1- - P)6 follows x²(n d) a dis-
tribution. Thus (7- follows an inverse-chi-squee -hi-squrred distribution with mean n-d-2 Therefore
the expectation E8| (7-P)) p7b a-d-2 Notice that 1/2 follows a + n-a (d, n - d) distribution and thus 1 = a-d-2 As result, we obtain
Esy
A
+
2
(at)To
1
d+1
T
31
1
d
2
1
||011
12 - d - ( 1)²
7
| (d 2) d(d + 1)2(n - d 2)
For b,, ......,,........................ .i.... Rid Nay Lemma
implies that
Es,y [1/2] < (1),
and
y²
Ed.y ( PJb On.d,o().
Therefore, we conclude that
Es.y
1
1
(A+)
On,,,(()).
d+1
TT
y
d
B.5
PROOF OF THEOREM 7
Proof. We start from
Taking expectation over all random variables gives
A
+
1 (At)
E
d+1
TT
V
[|(1- ((1-Q) () (At) x1|2 (1+ 1 )11(At)
y2
B
(d + 1)2²
bT(1 P)b
-(1+ 1 { 2 (A+) T x +
y22
E
(d+ 1)2
Our strategy to choose a so that Σ b3
is sufficiently large. This is indeed possible as we
immediately show. Define independent random variables u Uni,((-1,0,1)) and w ~ (0, Since y has the same distribution as + w, have
2
Ely² B[(u w) Esl²)] + Elw?
3
On the other hand,
E
Σ
11 1=1
6.
2 P(max [ba| (O) E
Σ
62
max i
[b:
1=
[P([11] S 50))" E
max |by
<
6
-i=l
1
t²
exp
dt
3
20
no?
5"na2
18

---

Under review as a conference paper at ICLR 2021
Together have
y
E
5n+
1=
Since
E
A T
+
x V
x
dE
d++1
b
y
have
lim E a-0+
A
x
)((At)
x|l
TT
A
1 (A+)
a-0+
lim E
d+1
TT
T
+00
which completes the proof.
C PROOFS FOR OVERPARAMETRIZED REGIME
C.1 PROOF OF LEMMA 9
Proof. Since A and B have full row rank, (AAT)-1 and (BBT)-1 exist. Therefore we have
B B B (BBB)=
The Sherman Sherman-Morrison Morrison formula gives
Gbb G b G Gbu = G(T -bu)-
(BB (BB (AAT + 6b -bb)-1
Hence, we deduce
[AG bm) bTG bu)
A bu) b bT bu)
[A+ bbu)
B+ = [A, [A,b] bu) =
Transposing the above equation yields to the promised equation.
C.2 PROOF OF LEMMA 10
Proof. Let us first denote
2 (A+)T
and
G (A mg
First note that by Cauchy-Schward inequality, it suffices to show there exists D such that B[A4 (G) too and ||| < too.
We define Ad E IRaxd to be the submatrix of A that consists of all rows and first d columns. Denote
G3 a (A,44)-1 Raxx
We will prove E(A (G)) < +o0 by induction.
The base step is Note that since G 8 is almost surely positive definite,
Recall PIim+s:: N'O,, Ints). We show E. E[[muxx (Gn+s))* t00.
A max (Gn-s)] E[Amax ( (G), G1+))) < Eir((
Etr((AntsATTas) (18
19

---

Under review as a conference paper at ICLR 2021
By choice of a1. the matrix (An+sA14s)"1 is inverse Wishart matrix of size with (n + 8) degrees of freedom, and thus has finite fourth moment (see, for example, Theorem 4.1 in (von Rosen 1988)). then follows that
B[Amax (Gn+s)] & tr(B([AntsA ")) < +00.
For the inductive step, assume max (Ga) +00 for some d 2 n ++ 8. We clai that
Amax (Gd-1) S Amax (Ga),
equivalently,
Amin (AaAd) S Amin(Ad: A
Indeed, this follows from the fact that
A < A + 6b A
under the Loewner order, where b E m is the (d 1)-th column of A. Therefore, we have
E (Ga+1)] S Eix (Ga))
and by induction, we conclude that | (G)l +o0 for all 2 8.
Now we proceed to show |||b||| < +00. We have
||ا|| = [[(AA)) Az < [[AAT]] Allop ||x]||
where || alop denotes the 8² + 62 operator norm. Note that
Alli, >max Xmax (((AAT)-*A) (AAT)-1A)
2ax (AT(A
Amax ((=T)))T==²a)))
where the last equality uses the fact that A ATAATT)-2 is positive semidefinite. Moreover, we deduce
[(AAT)) A Amax (AT(AAT)-3A)
S tr (ATA 3-2A)
tr ) - AAAT)
tr ((AAT)-2).
Using the fact that AsA & A established above, induction gives
(=A (An+8A74s)
It follows that
[[[AAT)- s trr
( (An+t8AT+t) tr (E (AA+sA)T+s 99) < t00, (13)
where again that fact that inverse Wishart matrix (An48A74s) has finite second moment.
Next, demonstrate E||==|| +00. Recall that every D, is either Gaussian Gaussian mixture distribution. Therefore, every entry of x has a subgaussian tail, and thus E|| < 400. Together with 13 and the fact that and A are independent, we conclude that
E || E ( 1 E [||=|||] < +00.
20

---

Under review as a conference paper at ICLR 2021
C.3 PROOF OF THEOREM 11
Proof.
The randomness comes from A, I, y and b. We first condition on A and æ being fixed.
Let G è (AAT)-1 E _=xx" and v
1+b 11x. Define
- (A+)
r 1
H bb
We compute the left-hand side take the expectation over only for the moment
Bg
A
x
[[(A+)Tx=]] x=1
bt
Ey [|(T - bu) To + u T "||* ||
[[ -bu)² Tell"
v11 + Ey y11 ||u||2
(E 0)
(I( -bu) (ou)Tel) u|12 + By [v+] |Gbl1 2
||/|1
Let us first consider the first and third terms of the above equation:
[I(T bu) '012 ||,1 = T. ((T - bb) - bu) - 1) v
= (bu + TTb² bbu 6 )
-T HGG HGG GH GH HG² H V.
r2
Write G = VAVT, where A = (ii An) E Bxxx is diagonal matrix (): > 0) and
V E R=x" is an orthogonal matrix. Recall b ~ In). Therefore w & V ~ NO0, In)). Taking the expectation over b, we have
HG GH
V BOTVA+ AV 06 V
Tww A Awn
Es
A+D V
VEW
VT.
+ w Aw
Let R. 2 En
yow A+Arr
We have
14:00 Aw
2
R4 = Ew
= o2EunN(O.1n)
>0
1 Σ Di=1 Xwu?
1 02
En djn?
and i ifii*1 + j.
(A; A1
Ry Ew
1 I+ Xw?
Notice that for any w and j. it has the same distribution if we replace wy by -wy As result,
[A, (,)w;(-u;)
Rgg Ew
RRg. + Σi dmw?
Thus the matrix R is diagonal matrix and
A Aiag(v) R ==
1 I+ Av
Thus get
HG + GH
GV diag(v)
Es,A
20 Eu-NNo,L.).
1 o2v Av
Moreover, by the monotone convergence theorem, we deduce
GV diag(u)2VT
lim By-N1o,..))... a+0
= BynN(o...) [-v] GV d
1 U Av
= E =Ei-uTGa
21

---

Under review as a conference paper at ICLR 2021
It follows that - 0 E
HG GH -20 Gol = 22 [e] (AAT)- -t]] -20 Bil(A A)+x113).
Moreover, by
we have
E (AAT)
w0 S E Mmmax
< +00
Next, we study the term HG²H/1²2
HG²
VA
BB,
,2
VA+TTVAVTb
ww A A?ww T (1+w Aw) vv Tr (1 + p2vT Au)z
=o N(O.L)
Again, by the monotone convergence theorem, we have
vv A
E lim a
V
VT
(1+ (1+02v o Av)?
-.. [U Vev A T [Tu]
= =EA,a
TV 21 + In Σ x VT
im1
=Ep [u" (2G² + (r((G)))))
It follows that as + 0
HG²H
,2
o o'E [o" (2G² + Lz o]
= =
+ )
Moreover, by we have E [2]((AA))- + tr((AAT))
||
< (n + 2) [>m ((AAT))>)((At)) 2011] +00.
We apply similar method to the term |GO|L We deduce
||/b|
GT
V
22
(1 1 + Gb)
VAVT
It follows that
|b
w T Aww
v A2
E
E Vw
= =²²B -OB...NO...)
(1+ + TT Aw)2
(1+02v' Av)2
The monotone convergence theorem implies
v A p2u Anja
lim Bo-A(O.))) 0+00
Ely A3v) R|(r(G?))
Thus get + 0+
E, E, |Gbb|
o "'E(tr(T)))
x²
where E[tr(GG)) < ((AA )-)) < + xc.
((AAT)
Putting all three terms together, we have + 0+
Lat1 Lt ~ - 20 2
[I (AT A) =>
Therefore, there exists o > 0 such that L La < O. Furthermore, we deduce
L'441 - L' d²
(Lo71 - La) < <.
22

---

Under review as a conference paper at ICLR 2021
C.4 PROOF OF THEOREM 12
Proof. Again we first condition on A and a being fixed. Let G (AAT)-² E Ruxa and v - G IR lx as defined in Lemma We also define the following variables:
146TG6
(A+) x,
- 1 Gb.
Gb.
We compute L/441
L'a but take the expectation over only for the moment
A
1 d
(A+)
y
d + 1
6
y
BBy [|(T - bu)
v + u y/ 112 -
(d + 1)2
1
(II(T - bbu) u1l + Ryyll yl1 - (1 + 1/d)
(Flv) 0)
(d + 1)2
||Gb|12
(I(T-
+ Eyl p² (1 1/d))| Tull bu)
bu)
(14)
(d 1)2
Our strategy is make Ely have
arbitrarily large. To this end, by the independence of and b
|Gbll
Gb
E g.b
y²
p²
22
By definition of A Mimix with probability 2/3, y is sampled from either N(,, or N N((H,,0)) which implies E[y²] 2 ju². For each 6,, we have
1
P(|b./ E (o)) 2 4
Also note that is positive definite. It follows that
||
||GU|
(Amin (G) b1)
A ())
Es
E.
2 Eb (1 + Amax 6)]661122
2
22
(1)b)Gb)2
12
(1 4m (G)no2)²
Altogether we have
|1Gb1 x2
1
n (G)
By Bygb
y²
3 12 (1 + 4n 2))
Let = 1/02 and have
Gb p2
1
nx2 min (G)
lim a
y²
> lim E., +-
3 12t a² + 4n 22)
1
n min (G)
EAr
+
33 12"
o² + Amx (2)
+00,
where switch the order of expectation and limit using the monotone convergence theorem. Taking full expectation over A, x. and of (14) and using the assumption that E||/||2 < +00 we have
Gb
L'441 L'g (d + 1)2
BAz bu) 0112 + E
y²
- (1 E Axmllll))) + to0
22
0+. In addition, we have 0+
La+1 - La 2 d² (L'411 - L'd) + t00.
23


Reviews:
[{"review_id": "qsa7qxh0vUa", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the double/multiple descents of the prediction error curve for linear regression in both the under-parameterized and over-parameterized regime. \n\nThe strength: while many papers have studied the double descent for linear regression estimate or the minimum $\\ell_2$ norm solution,  this paper shows multiple descents when d=O($\\sqrt{n}$) a setting is barely studied by others. Further, while multiple descents have been numerically discovered by other concurrent works, they have theoretically proved that such multiple descents exist.  \n\nThe weakness: The major weakness of the paper is the model settings. Specifically, 1) it is unclear why the prediction error is normalized by the number of features, and 2) the bias term is left out in the prediction error due to the true coefficients being zero and only the variance term is considered. First, for normalization, the authors claim that this normalization is necessary for comparison. Indeed, the entire results are hinged on this normalization, i.e., without the normalization, the proof can NOT show the existence of the multiple descents neither in under-parameterized regime nor overparameterized regime. The reasons I found this normalization is weird are the following:\n\ni) Normal linear regression problem does not have such normalization on the prediction error. It is unclear why we want to divide a one-dimensional error by the feature size.\n\nii) Other double descent works mainly deliver two messages:\n\na) Given a fixed sample size, what is the best model gives the best estimate of the response. The answer is a larger model, i,e, adding more features, may help. (e.g. Xu's PCR paper)\n\nb) Given a fixed feature size, what is the best sample size that gives the best estimate of the response. The answer is using a smaller sample size may help. (e.g. Hastie's double descent paper)\n\nFor both cases, I do not see any reason to normalize the prediction error of response by feature size. If this normalization is for the purpose of the model selection penalty, it is unclear why we should encourage a larger model instead of penalizing it.   \n\nA reasonable quantity for such normalization is the MSE of the coefficient, i.e., $\\|\\hat{\\beta}-\\beta^*\\|^2$. There are many applications where people are more interested in the coefficients rather than the response. Maybe the authors should consider this quantity instead of the prediction error. \n\nFor the second weakness of the model settings, the bias term has been left out of the prediction error when the true coefficients are assumed to be all zero. Because of this setting, all features are just pure noise, irrelevant to the response. Then, we can check that 0 is the best estimate when all features are just pure noise, and it seems that there is no motivation for us to learn anything from the random noise. If the main purpose of this paper is to deliver a message that using only irrelevant features and adding more of them can help to improve the prediction error, this effect is known already in those double descent paper in the overparameterized regime. Showing multiple descents does not add much value because it never beats the trivial estimate 0 in this setting.   \n\nBecause of these major weakness, I recommend rejection for this paper. But I will possibly change my evaluation if the authors can provide a very convincing explanation of the model settings and motivation.\n\nBesides these, another suggestion for the paper is that the proof of the Theorems and the statement of Lemmas takes a lot of places. I think they can be replaced by more detailed discussions of the model settings and messages or conclusions from the main theorems. For example, is there any intuition about what kind of multiple descents curve is more favorable? Also, despite the attractive title, I think it is still hard to design the generalization curve without taking the bias term into consideration. The room can be left for the analysis of the bias term.   \n\nAfter response:\nThanks for addressing the concern about normalization. It appears that other reviewers have a concern about such normalization as well. I suggest the authors remove the results with normalization entirely from the main paper and only have it in the appendix for anyone that is interested in such normalization. \n\nOn the other hand, without normalization, the results have changed for the under-parameterized regime (which makes more sense to me) and the proof looks quite different in the over-parameterized regime as well. I did not have time to check the proof and I believe it is better to resubmit the paper as new because of the major changes. \n\nFinally, I still have concerns about the fact that only variance is discussed. I suggest the authors state their results in a setting where both bias and variance exists and the features added to the model are related to the response. Otherwise, it is a weird message that it is good to add pure noise as features. It feels like although we can design multiple descents in the overparameterized regime when noise is large, it is very likely that the 0 estimate achieves the best prediction risk. So there is no point to go into overparameterization and multiple descents at all.    \n\nIn summary, I have raised the score to 5. I believe it can be 6 or 7 if all issues are addressed, but I am afraid that the paper looks basically new after these changes and thus I am not sure whether it should be still considered for this conference.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ejq5mzQAtb", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n\nThe paper proves that the generalization curve of a linear regression problem can be designed. The paper discusses both the under-parameterized and over-parameterized case and shows that the generalization curve can be designed in either case. The paper presents only theoretical results.\n\n\n##########################################################################\nReason for score:\n\nMy vote is for accepting the paper. The subject it addresses is of importance and I believe the results that are presented are of sufficient interest.\n\n##########################################################################\nPros:\n\n1. The generalization error is an important aspect for ML algorithms. The paper addresses the case of linear regression, one of the simplest ML algorithms. However, showing that the generalization error can be controlled even for a simple model as this is nonetheless important.\n\n2. The paper is well written, the problem it addresses is clearly discussed and the development of the proposed method is well detailed.\n\n\n##########################################################################\nCons:\n\n1. I would have liked to have some numerical examples to illustrate the design of the generalization curve for a simple case. \n\n2. In the setting in the paper you draw the new elements either from a normal distribution or from a mixture distribution when you increase the dimension. In a practical settings, where I already have the data, do such hypothesis still remain true?\n\n\n##########################################################################\nMiscellaneous:\n\n1. Could you please elaborate on the statement that 'the true linear model is \\beta = 0 \\in R^{d}'. For me it is not clear what is the purpose of the statement, do you mean that the model parameters are all zero? \n\n2. There are some typos present, for example 'The quantiry ...' in the paragraph after lemma 3, they should all be spotted by a spell checker. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "EKmfeSbj2ZJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Previous work has shown peaks in generalization error as the capacity of the model increases (called the double-descent phenomenon). The submitted paper proposes methods for generating data that would arbitrarily change the number and positions of peaks in a generalization-vs-capacity curve for linear regression, where the number of features controls the capacity,  and shows that properties of data can play an important role in this phenomenon.\n\nThis paper tackles an important problem in a quite active area of research with clear presentation and coherent organization. Existence of this data serves as an impossibility result that shows that relating the double descent phenomenon to the properties of model and interpolation without further assumptions on the data is futile. However, there is a critical discrepancy between the generalization curves studied in this paper and previous work that I describe below and, therefore, I'm leaning towards rejection. I will raise my score if the authors can show that the effects on the number and positions of the peaks hold in the original setting, as I believe this is an important paper otherwise.\n\nThe generalization error in this paper is normalized by the square of the number of features and this can have major effects on the shape of generalization-vs-capacity curve. The number of features is what controls the capacity so, for example, if the regular (unnormalized) error is flat across different capacities, the normalized curve will be a decreasing sequence.\n\nNeither the generalization error in a classical bias-variance curve nor the error that matters to a practitioner is normalized. I skimmed through the double descent paper by Belkin et al and they also seem to be using the typical generalization error which is not normalized.\n\nThe motivation for normalization in the paper is that the closed form error, $||(A^\\top)^+x||^2$, sums over d dimensions and so the generalization error has to be normalized by d^2. This does not seem right. $(A^\\top)^+$ itself has factors that sum over d dimensions and are then inverted, so the effect of d will cancel out.\n\nMinor remarks:\n- \\beta and A are not clearly defined in the problem setup.\n\n--\nUpdate: The issue with normalization is fixed in the new version and I am increasing my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "1sONZs-1wg", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Short summary:\nThe paper claims that the double descent phenomenon arises from 'specific interactions between properties of typical data and the inductive biases of algorithms' and constructs a distribution that generates an arbitrary generalization curve for linear regression, specifically building a multiple descent generalization curve both in the under and overparametrized regimes. \n\nThe model that is used in the paper is a linear regression model over an increasing (in a revealing manner) set of coordinates or features. The authors construct the distribution that gives the peaks at custom coordinates by having features being independent  standard normal when they want the test error to decrease and to be a (independent) mixture of gaussians when they want the test to increase.\n++++++\nMain points:\nWhile the math to my understanding is clean and the exposition is clear, my main concern is how the authors relate their findings to Double Descent. This worries me in two related ways. First, from the perspective of the complexity of the model.  While adding a dimension to the linear regression adds a parameter, I'm skeptical how this relates to the complexity of the model in how we view complexity in machine learning and in the research area of double descent in particular. I would be much more convinced if the authors could show a case where adding a feature in the random features sense where the features are of the whole vector (say apply a random rotation and then do the inverse transform sampling) or adding a neuron in a two layer network and still being able to decrease/increase performance arbitrarily (or close to it in some sense).  Even doing the same as in https://arxiv.org/pdf/1903.07571.pdf, where they choose a random set of indices of increasing cardinality would convince me much more. The second related issue, is the distribution of the features. I would not mind it if the classifier would use the features uniformly, but increasing/decreasing the hardness of the distribution at each coordinate feels very artificial in the following sense: Assume that the first coordinate is the label (or something close to it), but the next coordinates are pure noise. Then both our train and test will increase when we increase the number of features. In my intuition, this is very far from what is studied and claimed in the double descent literature (for example in the sense of Belkin's interpolation point or Nakkiran's Model Complexity, we expect the train error to decrease when model capacity increases). \n\nI do believe that the question of whether we can construct an arbitrary generalization curve is very important and that it should be studied and explored more deeply, but I'm not convinced by the set-up in this paper. I would be willing to change my opinion in the case the authors will address the above points in a satisfactory manner. \n\nMinor comments:\n1) The related work in the body of the paper is lacking:\n  (i)  One notable paper that should be present is: Advani & Saxe 17' https://arxiv.org/abs/1710.03667.  \n  (ii) While Nayshabur 15' observe the double decent without realizing it and Neal 18' study the bias-variance tradeoff, Nakkiran 19' https://arxiv.org/abs/1912.02292 is the first to demonstrate it in a convincing fashion and should be cited as such. \n2) I would appreciate an explanation for why the loss is scaled by $1/d^2$, this feels rather arbitrary. \n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While there was some interest in the analysis, the consensus view was that the original treatment was not sufficiently well-motivated, and the revision was too dissimilar from the original submission for it to be evaluated for publication in this year's ICLR.
Decision: Reject