Multiple Descent: Design Your Own Generalization Curve
Authors: Lin Chen
Yifei Min
Misha Belkin
amin karbasi
Venue: NeurIPS 2021 Poster (2021)
Keywords: generalization
double descent
multiple descent

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, the locations of those peaks can be explicitly controlled. Our results highlight the fact that both the 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. 

Multiple Descent: Design Your Own Generalization Curve
Lin Chen
Yifei Min
Simons Institute for the Theory of Computing University of California, Berkeley CA 94720 1in. wwwn@berkeeey...... edu
Department of Statistics and Data Science Yale University CT 06511 yifei weteiiimi@yall...o
Mikhail Belkin
Amin Karbasi
Halıroğlu Data Science Institute University of California, San Diego CA 92093
School of Engineering and Applied Science
Yale University CT 06511 amin, www.aairbaiiiioo. wwweaaasssaaleeeeeeeeeeeeeeeeeee edu
mbelkin@ucsd edu
Abstract
This paper explores the generalization loss of linear regression in variably param- eterized families of models, both under-pante aadder-prametriieed and werrparamettrized. We show that the generalization curve can have an arbitrary number peaks, and moreover, locations of those peaks 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.
Introduction
The main goal of machine learning methods is to provide an accurate out-of-sample prediction, known generalization. For a 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 rich enough to interpolate the training data, resulting in zero (or near-zero) training error. In contrast, the behaviour of the test enror function of model complexity 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 ander-parameterizee and over- weer-paramtterized regimes. Classical statistical learning theory supports U-shaped curve of generalization versus model complexity [31, 33). Under such 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-vart variance trade-off, higher model complexity increases the variance while decreasing the bias. A model with an appropriate level of complexity achieves 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 fit and tends to worsen the generalization performance due to the soaring variance.
Although classical statistical theory suggests a pattern of behavior for the generalization curve up the interpolation threshold, does not describe what happens beyond the interpolation threshold,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

commonly referred to as the over parametttteee 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 so complex that they have the potential to interpolate all the training data points [61, 10, 32, 34).
Modern practitioners commonly deploy deep neural networks with hundreds of millions or even billions of parameters. It has become widely accepted that large models achieve performance superior to small models that may be suggested by the classical U-shaped generalization curve [13, 38, 55, 35, 36). 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 [9], which has been broadly supported by empirical evidence [49, 48, 29, 30] and confirmed empirically on modern neural architectures by Nakkiran et al. [46]. On the theoretical side, this phenomenon has been recently addressed by several works on various model settings. particular, Belkin et al. [11] proved the existence of double-descent phenomenon for linear regression with random feature selection and analyzed the random Fourier feature model [50]. Mei and Montanari [44] also studied the Fourier model and computed the asymptotic test error which captures the double-descent phenomenon. Bartlett et al. [8], Tsigler and Bartlett [56] analyzed and gave explicit conditions for "benign overfitting" in linear and ridge regression, respectively. Caron and Chretien [16] 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 to infinity, implying the existence of double descent. Liu et al. [42] studied the high dimensional kernel ridge regression in the under- and over werrpaarametrrieed regimes and showed that the risk curve can be double descent, bell-shaped, and monotonically decreasing.
Among all the aforementioned efforts, one particularly interesting question is whether one can observe more than two descents in the generalization curve. d' d'Ascoli et al. [21] empirically showed sample- wise triple-descent phenomenon under the random Fourier feature model. Similar triple-descent was also observed for linear regression [47]. More rigorously, Liang et al. [41] presented an upper bound on the risk of the minimum-now norm interpolation versus the data dimension in Reproducing Kernel Hilbert Spaces (RKHS). which exhibits multiple descent. However, multiple-descen upper bound without a properly matching lower bound does not imply the existence of multiple-descon generalization curve. In this work, we study the multiple descent phenomenon by addressing the following questions:
* Can the existence of multiple descent generalization curve be rigorously proven?
Can an 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 Section 2.
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.
Our analysis considers both the underparametrized and overparametrized regimes. the over- parametrized regime, we show that one can control where descent or an ascent occurs in the generalization curve. This is realized through our algorithmic construction of reature-revcaling process. To be more specific, we assume that the data is in R., where D can be arbitrarily large or even essentially infinite. We view each dimension of the data as a feature. We consider a lincar regression problem restricted increasing the dimension of the data. We then show that by specifying the distribution of the newly revealed feature to be either standard Gaussian ascent or descent occurs. In order to create an ascent when a new feature is revealed, it is sufficient that the feature follows Gaussian mixture distribution. In order have descent, it is sufficient that the new feature follows a standard Gaussian distribution. Therefore, in the overparametrized regime, we can fully control the occurrence of a descent and an ascent. As a comparison, in the un- derparametrized regime, the generalization loss always increases regardless of the feature distribution. Generally speaking, we show that we are able design the generalization curve.
the first d features, where d < D. New features
revealed by
Gaussian mixture, one can determine where an

---

On the one hand, we show theoretically that the generalization curve is malleable and can be constructed 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.
2 Related Work
Our work is directly related to the recent line of research in the theoretical understanding of the double descent [11, 34, 60, 44] and the multiple descent phenomenon [41, 39]. 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. [22] proposed selection procedure for the regularization parameter. Advani and Saxe [1] analyzed the generalization neural networks with mean squared error under the asymptotic regime where both the sample size and model complexity tend to infinity. Richards et al. [52] proved for least square regression in the asymptotic regime that the dimension-to-saan tossttpe----eeizeee ratio d/n grows, additional peak can occur in both the variance and bias due to the covariance structure of the features. As a comparison, in this paper the sample size is fixed and the model complexity increases. Rudi and Rosasco [53] studied kernel ridge regression and gave an upper bound on the number of the random features to reach certain risk level. Our result shows that there exists natural setting where by manipulating the random features one can control the risk curve.
pver-Prrameterzztton and Interpolation. The double descent occurs when the model complex- ity reaches and increases beyond the interpolation threshold. Most previous works focused proving an upper bound or optimal rate for the risk. Caponnetto and De Vito [15] gave the optimal rate for least square ridge regression via careful selection of the regularization parameter. Belkin et al. [12] showed that the optimal rate for risk can be achieved by a model that interpolates the training data. In series of work on kernel regression with regularization parameter tending to zero (a.k.a. kernel ridgeless regression), Rakhlin and Zhai [51] showed that the risk is bounded away from zero when the data dimension is fixed with respect the sample size. Liang and Rakhlin [40] then considered the case when d x showed empirically the multiple descent phenomenon and proved a risk upper bound that can be small given favorable data and kernel assumptions. Instead of giving a bound, our paper presents an exact computation of risk in the cases of underparametrized and overparametrized linear regression, and proves the existence of the multiple descent phenomenon. Wyner et [59] analyzed AdaBoost and Random Forest from the perspective of interpolation. There has also been line of work on wide neural networks [4 6, 23, 3, 58, 14, 2, 18, 62, 54].
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. [46] empirically observed the epoch-wise double-descent and sample-wise non-monotonicity for neural networks. Chen et al. [19] and Min et al. [45] identified and proved the sample-wise double descent under the adversarial training setting, and Javanmard et al. [37] discovered double-descent under adversarially robust linear regression. Loog et al. [43] showed that empirical risk minimization can lead to sample-wiss wise non-monotomicity in the standard linear model setting under various loss functions including the absolute loss and the 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. [20] demonstrated the double descent curve of the generalization errors of subspace fitting problems. Fei et al. [28] studied the risk-sample tradeoff in reinforcement learning.
3 Preliminaries and Problem Formulation
Notation. For E Rd and d D, we let 2|1 d) IRd denote d-dimensional vector with x[1 d] xi for all i d. For matrix A e ga denote its Moore-Penrose
3

---

|ااا pseudoinverse by A Id and denote its spectral norm by |||||| supay00 T where || ll2 the Euclidean norm for vectors. If a vector, its spectral norm ||||| agrees with the Euclidean norm ||l|22- Therefore, we write ||||| for ||v||2 to simplify the notation. 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,da (1) is a constant that only depends on n. d, and Ø. If f and g(or are functions of write f() ~ g(o) if lim f(a) 1. will given in the context how we take the limit. g(a)
Distributions. Let Wu, o²) (u, R) and ((, 2) (μ E R", L E IXx")) denote the univariate and multivariate Gaussian distributions, respectively, where μ In and E _ is positive semi-definite matrix. We define family of trimodal Gaussian mixture distributions as follows
1 I N(0 1 [(((-1,02)+ N 3
N mmix
For an illustration, please see Fig. 1.
0.3
0.4
5,04
02
0.3
0.3
0.
00
(a) (0, 1) feature
(b) NN feature, (or 0.3)
(c) No,i feature, (a = 0.2)
Figure 1: Density functions of the N 1) and A/mix feature. new entry is independently sampled from the 1-dimensional distribution being either a standard Gaussian or trimodal Gaussian mixture. Smaller a leads higher concentration around each modes.
Let Ak; A) denote the noncentral chi-squared distribution with & degrees of freedom and the non-centrality parameter X. For example, if X, ~ N(p,, 1) (for = 1, ..2.....k) are independent Gaussian random variables, have Σ X² (K, A), where À E /J We also denote by (k) the (central) chi-squared distribution with A degrees and the F-distribution by F(d1, d2) where dj and d2 are the degrees of freedom.
Problem Setup. Let Zi.... In E RDD be column vectors that represent the training data of size and let Frest DRD be column vector that represents the test data. We assume that they are all independently drawn from a distribution
sid D.
Pri Prest
Let us consider a linear regression problem on the first d features, where S D for some arbitrary large D. Here, d can be viewed as the number of features revealed. Then the feature vectors are B1...., En. where ï; = xz[1 d] E Rd denotes the first d entries z,. The corresponding response variable y satisfies
y/1 == i 1,....,,
where the noise & ~ (O, 2) We use the same setup as in [34] (see Equations (1) and (2) in [34]). Moreover, in another closely related work [41], if the kernel is set the linear kernel, it equivalent to our setup.
I Next, we introduce the estimate 3 of and its excess generalization loss. Let = (E1, denote the noise vector. The design matrix equals [Z1...., J..] E Raxd Let x Jeest [1 d) denote the first d features of the test data. For the underparametrized regime where d < the least square solution on the training data + (A,3 + E). For the overparametrized regime where d n, A (A, + E) is the minimum-norm solution. In both regimes consider the solution

---

3 (A3 + E). The excess generalization loss on the test data is then given by
- x T 2 (xT (3 - 31)
Ld P
(y xy-xx) 3)
= (xT ((A+ 1)3 + A)))
= IE ((c"(AAA-188)) + [ A+te22]
= E (A* 1)3) + , [| )
(1)
where y = 1 + Stest and Etest ~ n²) We call the term E [< [A+ 1 1)8) the bias and call the term E (P (AT)) the variance.
The next remark shows that in the underparametrized regime, the bias vanishes. The vanishing bias in the underparametrized regime is also observed by Hastie et al. [34] and shown in their Proposition 2.
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. In this case, have A A I and therefore the bias E [(x (A+ A T) vanishes irrespective of B. In other words, the underparameetrized regime, La equals 17 (A f11
According to Remark 1, we have La (AA) 2/| in the underparamctrized regime. It also holds the overparametrized regime when = 0. Without loss of generality, we assume 7) = in the underparametrized regime (for all (). In the overparametrrieed regime, also assume 17 = 1 for the 3 = 0 case. In this case, we have
La (II(AAA) ) +1
(2)
We assume a general 17 (i.e., not necessarily being 1) the overparametrized regime when | is non-zero.
We would like study the change in the loss caused by the growth in the number of features revealed. Recall La = [B] > Once we reveal new feature, which adds new row b to A and a
A
new component 01 to æ, we have Lat1 E
G1
Local Maximum and Multiple Descent. Throughout the paper, we say that local maximum occurs at dimension d 2 1 if La-1 < La and L, > Ld+1- Intuitively, local maximum occurs if there is an increasing stage of the generalization loss, followed by decreasing stage, as the dimension grows. Additionally, we define Lo - oc. If the generalization loss exhibits a single descent, based on our definition, a unique local maximum occurs at d = 1. For double-descent generalization curve, a local maximum occurs two different dimensions. In general, if we observe local maxima at multiple dimensions, we say there is a multiple descent.
4 Underparametrized Regime
First, we present our main theorem for the underparametrizzed regime below, whose proof is deferred to the end of Section 4. It states that the generalization loss La is always non-decreasing as d grows. Moreover, is possible to have an arbitrarily large ascent, i.e., La+1 La > for any C >>
Theorem (Proof in Section 4.1). Ifd < n, we have La+1 2 La irrespective of the data distribution. Moreover, for any C > 0, there exists a distribution D such that Lat1 La > C.
Remark (D can be product distribution). The first part of Theorem holds irrespective of the data distribution. For the second part of the theorem ( i.e. for any C' > 0 there exists a distribution such that La+1 La > C) to hold, one extremely simple and elegant choice of the distribution D is product distribution D D1
DD such that Tij std Dj for all 1 S i S n, where D, is Gaussian mixture Amiix for some o, 0. Since the second part of Theorem is of independent interest, the result is summarized by Theorem 4.
5

---

Remark (Kernel regression on Gaussian data). In light of Remark 2, D can be chosen to be product distribution that consists A Note that one can simulate Amii with No 1) through the inverse transform sampling. To see this, let Fx(0,1) and Expes be the edf N 1) and Naii respectively. X ~ NNO,, 1). we have (x((o1)(X)) ~ Unif((0, 1)) and therefore (X) & (Ex)(o.))())) ~ Noais. In fact, we can use multivariate Gaussian D = -N(0, DXD) Agg
and a sequence of non-linear kernels (( x²) - (ol::I (f)) (x=dd())) where the feature map is all:d (x) - [01( (2(22),..... (a()))) E R Here is a simple rule for defining Φy: Dj = N /miix we set Φ to iPa, Thus, the problem becomes kernel regression problem on the
standard Gaussian data.
The first part of Theorem 1, which says that La is increasing (or more precisely, non-decreasing), agrees with Figure [11] and Proposition of [34]. In [34], they proved that the risk increases with y = d/n. Note that, first glance, Theorem may look counterintuitive since it does not obey the classical U-shaped generalization curve. However, we would like to emphasize that the U-shaped curve does not always occur. Figure and Proposition 2 of these two papers respectively. there is no U-shaped curve. The intuition behind Theorem I is that in the underparametrized setting, the bias always zero and as approaches n, the variance keeps increasing.
Coming to the second part of Theorem 1, we now discuss how we will construct such a distribution D inductively to satisfy L La C. We fix d. Again, denote the first d features of Tiest by A Frea cd. Let add an additional component the training data 21 [1 cl] -.... Fx, [1 and test data x so that the dimension is incremented by 1. Let b, R denote the additional component that add the vector I; (so that the new vector is given as [x,[L d] d]',,,] 6.] Similarly, let
aj E IR denote the additional component that we add to the test vector æ. We form the column vector
b = [b,,.. ,b,....,6 6,,] E R" that collects all additional components that we add the training data.
We consider the change in the generalization loss as follows
A
Ld41 La= = E
((At)
x=1
a1
Note that the components b,,.... ......,,. bns are i.i.d. The proof of Theorem starts with Lemma 2 which
TA
relates the pseudo-inverse of 6] to that of AT. In this way, can decompose
x
6T
into multiple terms for further careful analysis in the proofs hereinafter.
Lemma 2 (Proof in Appendix B.1). Let A E R and O + E Rax1 where n 2 d + Additionally, let P AA- and Q bb+ columnwise partitioned matrix [A, b) has linearly independent columns, we have
A4 aala. and define (T-PPP If + and the [b]l
A 6t
= [1
M 13T>
[
AA+M
(A+)
(1-AA+)
[b
AA-B
|6
AA
[I (I-Q)(I+ + [-ir(p
PQ
(A+)
(J-P)b
(I-PPP
(1- + PQ (A+)T
(I-Ph
(T(1-P
In our construction of D, the components D, are all continuous distributions. The matrix / - P is an orthogonal projection matrix and therefore rank(/ P) that b * 0, 2 * 0, and [A, b) has linearly independent columns. Thus the assumptions of Lemma 2 are satisfied almost surely. In the sequel, we assume that these assumptions are always fulfilled.
d. As a result, it holds almost surely
Theorem guarantees that if La = E ||((A)TT Tal
finite and the (d + 1)-th features b1...., bn a1
+
i..d, sampled from A/ 1) or Mmis Lu41
x
is also finite.
TT
a1

---

Theorem 3 (Proof in Appendix B.2). Let 2 be as defined in Lemma 2. bl, bas are ii.d. and follow a distribution with mean zero, conditioned on A and I, we have
A 6T
[1(At)==]]
of
Bb.ar
Bo.as
69 6T P)b
bys ai iid No0 1), conditioned on and x, we have
In particular, if 2 n and b
(n - 2) <(A)) +1
Eb
b
n d
If d 2 and bi.... ....... bn a1
sid
Ami conditioned on A and x, we have
A TT
+
(n 2 1+ vd) || [A
+ 2/(30?) +1 n d
x
Using Theorem 3, we can show inductively (on d) that La is finite for every d. Provided that we are able to guarantee finite L1, Theorem implies that La finite for every d if the components are always sampled from (0, 1) or No...
Making a large La can be achieved by adding an entry sampled from N when the data dimension increases from d to in the previous step. Theorem 4 shows that adding N feature increase the loss by arbitrary amount, which turn implies the second part Theorem 1.
Theorem (Proof in Appendix B.4). For any C > and (A+)Txll +o0, there exists
such that if bi....., b,, 01 rid No,, we have
E
A TT
- [[(A))==)))
> >C
a1
We are now ready prove Theorem 1.
4.1 Proof of Theorem
Proof. We follow the notation convention (3):
A
+
2
Ld41
La
E
(1 )
b
a1
A
Recall d and the matrix B' fat matrices. As result, r'
is of size (d + 1) x n. Both matrices B' and B 2 AT
bT
x
we have
a1
|B* =
min
|
|| x
min || 2:
2:
Since {2 B'x 2') S {z Bz z). we get | x'112 2 Bt2l1 Therefore, we obtain La+1 2 La- The second part follows from Theorem
Remark 4. Remark and the proof of Theorem 4 indicate that D D2 x.. Do is a product distribution. The construction in the proof also shows that the generalization curve is determined by the specific choice of the D.'s s. Note that permuting the order of D.'s is equivalent 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 Tı, 2n E R.D, one can create different generalization curves simply by changing the order of the feature-revealing process.
7

---

Anea
Ants
Am+to
A
A
A
t
n+08
n+9
n+10
n+11
n+12 n+13 n+14
Dimension data d
Figure 2: Illustration of the multiple descent phenomenon for the generalization loss La versus the dimension of data in the overparametrized regime starting from d n One can fully control the generalization curve to increase or decrease specified by the sequence A {J, 1, 4. T,h.... Adding new feature with Gaussian mixture distribution increases the loss, while adding one with Gaussian distribution decreases the loss.
5 Overparametrized Regime
In this section, we study the multiple decent phenomenon in the overparametrized regime. Note that as stated in Section we consider the minimum-none morm solution here. We first consider the case where the model B 0 and La is as defined in (2). Then discuss the setting
O.
As stated in the following theorem, require we can still say that starts at roughly the same order as n. In other words, the result covers almost the entire spectrum of the overparametrized regime.
This is merely technical requirement and
Theorem 5 (Overparamettrized regime, 3 0). Let n A ++ A t D where Aa (t, there exists distribution D such that for every + < d < 1, we have
D Given any sequence
>> Ld.
if =1 Aa = 4.
Ld-1
< Las
In Theorem 5, the sequence An A....... AD-1 is just used specify the increasing/decrrasingg behavior of the La sequence for d > 8. Compared to Theorem for the underparametrized regime, where La always increases, Theorem indicates that one is able fully control both ascents and descents in the overparametrized regime. Fig. 2 is an illustration.
We now present tools for proving Theorem 5. Lemma gives the pseudo-inverse of A when d >> n. Lemma 6 (Proof in Appendix C.I). Let A E RRaxd and Rax1, where n d. Assume that matrix A and the columnwise partitioned matrix B & [A, have linearly independent rows. Let TTG.
G A (AAT)-1 E Raxn and u A
E 1x1, We have
Gb 5
A TT
+ [I bu) (AA)
Lemma establishes finite expectation for several random variables. These finite expectation results are necessary for Theorem 8 and Theorem 9 to hold. Technically, they are the dominating random variables needed Lebesgue's dominated convergence theorem. Lemma indicates that to guarantee these finite expectations, it suffices to set the first n + 8 distributions to the standard normal distribution and then set - DD to either a Gaussian or Gaussian mixture distribution. In fact, in Theorem 8 and Theorem 9, we always add Gaussian distribution Gaussian mixture.
Lemma (Proof in Appendix C.2). Let D D
DD be product distribution where
(a) Da = N'(O 1,.,.... + 8; and Nmix (b) Da is either NO x2) Noss for d > 8.
8

---

Let Diddd denote D1 x ... x Da. Assume that every row of A E Raxd and z E Raxi are i..d and follow Disd For any d such that n + I d < D, all of the followings hold:
B x=11²] + 000
E MAx ((AAT) +00
(4)
B[Amax ((AA")=))I(Att)) x=1²] + 00; I
x0.
Theorems and 9 are the key technical results for constructing multiple descent in the over- parametrized regime. One can create descent (Ld+1 < La) by adding Gaussian feature (Theo- rem 8) and create an ascent (La+1 > La) by adding a Gaussian mixture feature (Theorem 9).
Theorem (Proof Appendix C.3). If If (AT A)+ +)+?] > 0 and all equations (4) hold, there
exists such that (1, b1,.................. ................................ bn N o²), we have
säd
A
La+1
Ld E
B (A+) x
0.
Theorem shows that adding a Gaussian mixture feature can make Lat1 Ld.
Theorem 9 (Proof in Appendix C.4). Assume [B]((At)Tz1]) +00. For any C 0, there exist p. O such that if (1, bi...., bn A we have
Ta+1 Ltd =
E
A b
(AA))
E
C.
a1
The proof of Theorem immediately follows from Theorem 8 and Theorem
Proof of Theorem 5. We construct the product distribution = =I Da. We set Da = NO0 1) for 1..... n 8. For n + 8 < d < D, Da is either (N o.)) or Nami depending on Aa being either or 1.
First we show that for each step the assumption E| [ + E|I(A" A)+x||²]] O, we know that (AT
of Theorem is satisfied. If almost surely. Since D is a continuous distribu-
tion, the matrix A has full row rank almost surely. Therefore, rank((A" A)+) rank(A" (AA) A)+ TTA)* d n < d almost surely, which implies & ker(AT A)+. In other words. (AA A) x # 0 almost surely. We reach a contradiction. Moreover, by Lemma 7, the assumption E|| (A++ x1| < +oo of Theorem 9 is also satisfied.
almost surely. Thus dim ker( AT
If Aa-1 4, by Theorem 8, there exists σa > 0 such that if Da N'0 o2), then La < La-1- Similarly if Aa-1 t. by Theorem 9, there exists aa and μa such that Dj = -Amix Gasia guarantees
La > TTd-1-
Gaussian 3 setting, In what follows, we study the case where the model / is non-zero. In partieular, we consider setting where each entry of / is wi.d. (00, p²). Recalling (1), define the biases
Ea ( 1)3), Eat1 A (IT .
3 B1
T)
and the expected risks
A
L A E 7 (IAT)
L A E[Es+1] + 2
TT
where 3 ~ No0, Laa) and B ~ A0, p²). The second term in L and Leep is the variance term. Note that I.OXP is the expected value of La in (1) and averages over B3. Theorem 10 shows that one can add a Gaussian mixture feature in order to make 4+1 > Lap, and add a Gaussian feature in order to make 1441 L...
exp

---

Theorem 10 (Proof in Appendix C.S). Let 01 $1 E R. x Ráxi, 3 Ráxi, A Raxd and b Rnx1, where n I d. Assume that 2, a1 ..0.81.55 3, A. are jointly independent, [ST, 31]]" NO ((0,pTTT+1) Moreover, assume that the matrix [A, b] has linearly independent rows almost surely. The following statements hold:
(a) ff, b1....,by bn sid Nuix for any C O, there exist p., a such that Leep Nosus
l.d > C.
d+1
ud (b) Ifa bi...,,,,, bn NN there exists a > such that for all
B (AI 1
S "V
E A x1 21
we have Lap L
Theorem 10 indicates that for obeying normal distribution, curve as desired by adding a Gaussian or Gaussian mixture feature properly. We make this con- struction explicit for any desired generalization curve in (the proof of) Theorem 11. Similar to the construction in the underparametrized regime (for all (9) and overparametrivaaion regime (for 3 = 0), the distribution D can be made product distribution.
still construct generalization
Theorem 11 (Overparamettizzed regime, .3 being Gaussian). Let D Given any sequence
A 8 An Antg..... A where Aa E {t, }}. there exists > 0 and distribution D such that for
[O, p²) and every n S S D 1, we have
>
CNN
if Ad =t
exp L
d+1
< exp
if A =
Proof of Theorem 11. Define the design matrix A. A [ dl...., d]] Rxdd Similar to the proof of Theorem 5, we construct the product distribution D II Da. We set Da = NO 1) for d = I,...,7 n + S. For n + 8 < d < D. Da is either (0, o²)) or A ymis depending on Aa being either or 1.
A 1 1, by Theorem 10, there exists aa and paa such that Da Amix Gasiaa guarantees L > exp
If Ad-1 L. define
E (A] Ad-1) + Tieat [1 d 1]
m
E|| A d- Meeu [1 d 1] +
By Theorem 10, there exists aa take
0 such that if p S pa and Dj ((0,00) then 1. <
We d-1-
exp
p min
Pd
d: --
Conclusion
Our work proves that the expected risk 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 feature-revealing process where the newly revealed feature follows either a Gaussian distribution to control local maxima in the underparametrized regime and control ascents/descents freely in the overparametrized regime. Overall, this allows to design the generalization curve away from the interpolation threshold.
Gaussian mixture distribution. Notably, the construction also enables us
We believe that our analysis of linear regression in this paper is good starting point for explaining non-monotonic generalization curves observed in machine learning studies. Extending these results to more complex problem setups would be meaningful future direction.
10

---

Funding Transparency Statement
LC: Funding in direct support of this work: postdoctoral research fellowship by the Simons Institute for the Theory of Computing, University of California, Berkeley, and Google PhD Fellowship by Google. Additional revenues related to this work: internships at Google.
MB acknowledges support from NSF ISS-1815697, and the support of the NSF and the Simons Foundation for the Collaboration the Theoretical Foundations of Deep Learning through awards DMS-2031883 and #8 14639.
AK: Funding in direct support of this work: NSF (II--184003)) and ONR (N00014-19-1-2406)
References
[1] M. S. Advani and A. M. Saxe. High-dimensional dynamics of generalization error in neural networks. arXiv preprint 170:0:17/ 2017.
[2] M. S. Advani, A. M. Saxe, and H. Sompolinsky. High-dimensionn dynamics of generalization error in neural networks. Neural Networks, 132:428 446, 2020.
[3] Z. Allen-Zhu. Y. Li. and Z. Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252, 2019.
[4] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, pages 8141-8150, 2019.
[5] S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML, pages 477-502, 2019.
[6] S. Arora, S. S. Du, Z. Li, R. Salakhutdinov, R. Wang. and D. Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2019.
[7] J. K. Baksalary and O. M. Baksalary. Particular formulae for the moore-penrose inverse of a columnwise partitioned matrix. Linear algebra and its applications, 421(1):16-23, 2007.
[8] L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression. Proceedings the National Academy of Sciences, 2020.
[9] M. Belkin, Hsu, Ma, and Mandal. Reconciling modern machine learning and the bias-variance trade-off. star, 1050:28, 2018.
[10] M. Belkin, Ma. and Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541-549, 2018.
[11] M. Belkin, D. Hsu, and J. Xu. Two models of double descent for weak features. arXiv preprint 2019.
WwXiv:/903.007
[12] M. Belkin, A. Rakhlin, and A. B. Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619, 2019.
[13] Y. Bengio, R. Ducharme, P. Vincent, and C. Jauvin. neural probabilistic language model. Journal of machine learning research, (3FFb)::137-1153: 2003.
[14] Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pages 10836-10846, 2019.
[15] A. Caponnetto and De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.

---

[16] E. Caron and S. Chretien. A finite sample analysis of the double descent phenomenon for ridge function estimation. arXiv preprint arXiv:2007 12882, 2020.
[17] M. Caron, Bojanowski, A. Joulin, and M. Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV),
pages 132-149, 2018.
[18] L. Chen and S. Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In ICLR, 2021.
[19] L. Chen, Y. Min, M. Zhang, and A. Karbasi. More data expand the generalization gap between adversarially robust and standard models. International Conference on Machine Learning, pages 1670-1680. PMLR, 2020.
[20] Y. Dar. P. Mayer, L. Luzi, and R. G. Baraniuk. Subspace fitting meets regression: The effects of supervision and orthonormality constraints on double descent of generalization errors. In ICMI., 2020.
[21] S. d' Ascoli, L. Sagun, and G. Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprint arXiv:2006.0355 2020.
[22] E. De Vito, A. Caponnetto, and L. Rosasco. Model selection for regularized least-squares algorithm in learning theory. Foundations of Computational Mathematics, 5(1):59-85, 2005,
[23] Du, J. Lee, H. Li, Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685, 2019.
[24] Y. Fei and Y. Chen. Exponential error rates of sdp for block models: Beyond grothendieck's inequality. IEEE Transactions on Information Theory, (5(1):551-571 2018.
[25] Y. Fei and Y. Chen. Hidden integrality of sdp relaxations for sub-gause uab-gaussian mixture models. In Conference On Learning Theory, pages 1931-1965. PMLR, 2018.
[26] Y. Fei and Y. Chen. Achieving the bayes error rate in stochastic block model by sdp, robustly. In Conference on Learning Theory, pages 1235-1269. PMLR, 2019.
[27] Y. Fei and Chen. Achieving the bayes error rate synchronization and block models by sdp, robustly. IEEE Transactions Information Theory, (6266666999-99886666 2020.
[28] Y. Fei, Z. Yang. Y. Chen, Z. Wang. and Q Xie. Risk-sensitive reinforcement learning: Near- optimal risk-sample tradcoff in regret. arXiv preprint arXiv:2006. 2020.
[29] M. Geiger, S. Spigler, S. d' Ascooli L. Sagun, M. Baity-Jesi, G. Biroli, and M. Wyart. Jamming transition as a paradigm to understand the loss landscape of deep neural networks. Physical Review E, 100(():00) (00(1):012115,2) 2019.
[30] M. Geiger, A. Jacot, S. Spigler, F. Gabriel, L.. Sagun, S. d' Ascoli, G. Biroli, C. Hongler, and M. Wyart. Scaling description of generalization with number of parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2):024001, 2020.
[31] S. Geman, F. Bienenstock, and R. Doursat. Neural networks and the bias/variance dilemma. Neural computation, 4(1):1-58, 1992.
[32] B. Ghorbani, S. Mei, Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv: 2019.
[33] T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science Business Media, 2009.
[34] Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 1903.09630.000.. 2019.
[35] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
12

---

[36] Y. Huang, Y. Cheng, A. Bapna, O. Firat, D. Chen, M. Chen, H. Lee, J. Ngiam, Q. V. Le, Y. Wu, al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. In Advances in neural information processing systems, pages 103-112, 2019.
[37] A. Javanmard, M. Soltanolkotabi, and H. Hassani. Precise tradeoff's in adversarial training for linear regression. In Conference on Learning Theory. 2020.
[38] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097- 1105, 2012.
[39] Y. Li and Y. Wei. Minimum norm interpolators: Precise asymptotics and multiple descent. arXiv preprint arXiv:21 2021.
[40] T. Liang and A. Rakhlin. Just interpolate: Kernel "ridgeles" regression can generalize. Annals of Statistics, page to appear, 2019.
[41] T. Liang, A. Rakhlin, and X. Zhai On the multiple descent of minimum-non norm interpolants and restricted lower isometry of kernels. In COLT, 2020.
[42] Liu, Z. Liao, and J. Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In International Conference on Artificial Intelligence and Statistics, pages 649-657, PMLR, 2021.
[43] M. Loog, T. Viering, and A. Mey. Minimizers of the empirical risk and risk monotonicity. In Advances in Neural Information Processing Systems, pages 7478-7487, 2019.
[44] S. Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv: 05355, 2019.
[45] Y. Min, L. Chen, and A. Karbasi. The curious case of adversarially robust models: More data can help, double descend, or hurt generalization. arXiv preprint arXiv:2002. / 2020.
[46] P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv preprint 1rXiv:191,.02292, 2019.
[47] P. Nakkiran, P. Venkat, S. Kakade, and T. Ma. Optimal regularization can mitigate double descent. arXiv preprint vrXiv:2003.01897 2020.
[48] B. Neal, S. Mittal, Baratin, V. Tantia, M. Scicluna, S. Lacoste-Julien, and Mitliagkas. modern take on the bias-variance tradeoff in neural networks. arXiv preprint arX1v:1810.08591, 2018.
[49] B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In ICLR (Workshop). 2015.
[50] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pages 1 1177-1184, 2008.
[51] A. Rakhlin and X. Zhai. Consistency of interpolation with laplace kernels is a high-dimensional phenomenon. In Conference on Learning Theory, pages 2595-2623, 2019.
[52] D. Richards, J. Mourtada, and L. Rosasco. Asymptotics of ridge (less) regression under general source condition. arXiv preprint arXiv:2006.06:3 06386, 2020.
[53] A. Rudi and L. Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, pages 3215-3225, 2017.
[54] G. Song, R. Xu, and J. Lafferty. Convergence and alignment of gradient descent with random back propagation weights. arXiv preprint
2021.
[55] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1-9, 2015.
13

---

[56] A. Tsigler and P. L. Bartlett. Benign overfitting in ridge regression. arXiv:2009. 14286, 2020.
arXiv preprint
[57] D. von Rosen. Moments for the inverted wishart distribution. Scandinavian Journal of Statistics, pages 97-109, 1988.
[58] C. Wei, J. D. Lee, Q. Liu, and T. Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pages 9712-9724, 2019.
[59] A. J. Wyner, M. Olson, J. Bleich, and D. Mease. Explaining the success of adaboost and random forests as interpolating classifiers. The Journal of Machine Learning Reseurch, 18(1): 1558-1590, 2017.
[60] J. Xu and D. J. Hsu. On the number of variables to use in principal component regression. In Advances in Neural Information Processing Systems, pages 5094-5103, 2019.
[61] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
[62] D. Zou, Y. Cao, D. Zhou, and Q. Gu. Gradient descent optimizes over over-parameterized deep relu networks. Machine Learning, 109(3):467-499) 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
14

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "xTNIJtSK0x", "reviewer": "Reviewer_qLTq", "summary": "I have read other reviewers' comments and the author response.\nI lower my score due to the following reasons: 1) changing the feature dimension $d$ doesn't change the groundtruth function, which makes the problem setting questionable. 2) the response to the issue \"\\sigma should be taken far smaller than O(1/5^n)\" is unsatisfactory, which makes the result unattainable. \n=============================================\nThis paper studies the multiple descent of the excess risk for linear regression in under/over-parameterized regimes. In the under-parameterized regime, Theorem 3.1 includes two parts: one is showing that the loss $L_d$ non-decreases with $d$ independent of the data distribution; the other is $L_{d+1} - L_d > C$. In the over-parameterized regime, the authors provide the multiple descents in Theorem 5 under $\\beta = 0$ and Theorem 11 with $\\beta$ being Gaussian.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The quality of this paper is good but there are several points that I concern:\n\n**Problem settings:**\n\nThe target function is assumed to be linear, low-dimensional ($d<D$), which is fair and standard in interpolation learning. \nHowever, it appears a little strange to me when the authors consider a linear regression over its partial features (i.e., $d<D$) so as to tune $d$. I do understand that, in linear regression, adding one dimension to features is equivalent to increasing the model complexity (strictly speaking, at least non-decreasing). This operation/setting can be also found in [51]. However, a learning problem often corresponds to a given/fixed d. A common way is to tune the number of samples n instead of d, which is more reasonable in practice. So is it possible to transform the results via tuning $d$ in this paper to the standard tuning $n$ setting, e.g., [Liu, Liao, and Suykens AISTATS2021] on kernel regression in high dimensions?\n\n\n**Technical details:**\n\nThe proof in this paper largely depends on taking $\\sigma  \\rightarrow 0_+$. This might be unattainable in some cases. Here I take one example to illustrate this.\nI’m questionable the second part in Theorem 3.1, i.e., the proof of Theorem 4. \nFirst, the constant $C$ in fact depends on $\\sigma$?\nSecond, the employed strategy in the proof is to derive the lower bound in line 600 such that the second term in line 595 is sufficiently large. To this end, the authors derive this lower bound as the exponential decreasing order of n. In this case, \\sigma should be taken far smaller than $O(1/5^{n})$ if we want to ensure the non-negativity of line 599. However, this might be unattainable in practice. For example, if we only consider n=100 samples, sigma should be taken as 1e-70 order. Accordingly, this condition should be better re-organized. In theory, it could be possible to derive a polynomial order (at most) of $n$ in line 599? In experiment, Theorem 4 can be experimentally validated on some synthetic datasets: obtaining A and x, and seeking for potential solutions of $C$ and $\\sigma$.   \n\n\n**Minor issues:**\n\n1．\tThe authors claim that “To our best knowledge, this is the first work proving a multiple descent phenomenon for any learning model.” In line 67. I suggest the authors polish this sentence if [34] is taken into consideration.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ix9RVjobQ7_", "reviewer": "Reviewer_sF9e", "summary": "This paper studies the generalization error of the min-l2 norm solutions of linear regression. Authors claim that their analytical results can explain the multiple peaks in the generalization curve with respect to the number of features. However, the system model and some fundamental steps of the analysis are problematic, which makes me doubt the correctness of the paper.", "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": "The problem setup in this paper seems not correct. Generally speaking, the output of the training data y is given beforehand and shouldn’t depend on the number of features d (or any other manually chosen parameters) used in the linear regression. However, the problem setup on page 3 states that y=\\tilde{x}^T\\beta+noise, where \\tilde{x}=x[1:d] depends on d, and thus y depends on d. That makes the generalization error curve with respect to d in this paper useless because the error curve is not for one specific ground-truth function but for different ground-truth functions when d changes. In order to study the effect of the number of features on the generalization error, a more correct setup should be y=x^T\\beta+noise instead of y=\\tilde{x}^T\\beta+noise. Authors can take the following paper as an example: “M. Belkin, D. Hsu, and J. Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.07571, 2019.”\n\nIn Eq.(1) (the generalization error), it is unclear what random variable (e.g., training input, test input, noise in the training input) in each step the expectation is based on. Besides, the second step of Eq.(1) seems incorrect, i.e. E[(y-x^T\\hat{beta})^2-(y-x^T\\beta)^2] is not equal to E[(x^T(\\hat{beta}-\\beta))^2].\n\nRemark 1 is incorrect. Authors claim that A^+A=I, which is wrong. I think the correct one should be E[A^+A]=I where the expectation is on the design matrix A (i.e., the training input x).\n\nRemark 1 implies that the bias term is always zero in the under-parameterized region and authors completely discard the bias term in Eq.(2). This contradicts the well-known bias-variance tradeoff curve (the U-shape curve) in the under-parameterized region of linear regression. Similarly, Theorem 1 says that L_d is always increasing with respect to d, which also contradicts the known U-shape curve. The authors explain on page 5 that a \"U-shaped curve does not always occur\" and use the Prop.2 of [28] as evidence. However, Prop.2 of [28] describes the situation that the number of features and the number of training input go to infinity at a constant ratio, which is not relevant to the situation in this paper where both the number of features and the number of training inputs are finite. Besides, I haven't seen any literature (including [28]) that says \"U-shape curve does not occur in the under-parameterized region\". Indeed, \"U-shape curve does not occur\" is a very strong statement and should deserve more careful justification. For example, authors should clearly point out why the classical derivation of bias-variance tradeoff does not hold here. Is it because this paper uses a different setup? Or is it because the classical derivation of the bias-variance tradeoff is totally wrong?\n\nOverall, the setup and some fundamental steps of the derivation seems problematic and the main result contradicts the well-known bias-variance tradeoff result in the under-parameterized region, which jeopardizes the credibility and the contribution of this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Qa0om0s4vP", "reviewer": "Reviewer_wnTz", "summary": "The authors systematically study a simple linear regression setup where an arbitrary number of ascents and descents can be obtained in the risk. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: Multiple-descent curves are studied in several works as cited in the paper. As far as I know, this one is unique in proposing an algorithmic construction of input data distribution. \n\nSignificance: It is an interesting example setup that anyone who works on this subject should keep in mind. \n\nClarity: The paper is written very clearly and has a good structure. \n\nQuality: Although I could not check the appendix due to time constraints, I did not detect any issues in theorems neither proofs. \n\nI have two comments:\n- line 68: \"for any learning model\". The authors consider a very constrained setup of linear regression, not any general learning model. \n- line 311: Conjecture for neural networks. In my opinion, a conjecture needs some level of motivation. This sentence seems very off. In the paper, the model size grows as the input data dimensionality grows. In neural networks, the model size is totally independent of the data. The more obvious difference is non-linearity. Please remove this conjecture, or justify it with regards to your setup. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theory work without a clear societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "EboIDVsStMu", "reviewer": "Reviewer_w6vd", "summary": "=================================\nFINAL UPDATE AFTER DISCUSSION PHASE\n\nAs the authors addressed the points that came up during the discussion phase (which made me initially lower the score), I revert back to my initial scoring of accept.\n\n\n===================================\nUPDATE AFTER INITIAL DISCUSSION PHASE\n\nThe authors addressed my own points, but following the discussion with the other reviewers I decided to lower my score. It was pointed out that the data generation process depends on the model-dimension, and thus the resulting investigation is not about 'generalization curves' as claimed by the authors, but rather about the generalization behavior of different interpolation regimes. While I believe the contribution is still valuable, some explanations and need be changed (which may be possible in a camera ready version).\n\n( For example I don't believe anymore that the paper indeed answers the question: 'Can the existence of a multiple descent generalization curve be rigorously proven?'.)\n\n==================================\n\nThe paper analyses the behavior of generalization curves of linear regression wrt an increasing feature dimensionality. The paper constructs specific examples that can generate any ascending/ descending behavior of the curve, for both the under and overparametrized case. Their construction highlights that ascending/ descending behavior of the generalization curve is not inherent to the model family, but rather a result of the data distribution in combination with the model.", "questions": "", "limitations": "", "rating": 7, "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 review:\n\nStrength:\n+ Fairly polished\n+ Main story is easy enough to follow, despite some parts being rather technical\n+ Original\n+ Technically sound (checked some proofs of Section 3, not from 4) \n\nWeaknesses:\n- Some remarks are missed on me \n- No discussion\n\nDetailed review:\n\nThe paper considers learning curves, a topic that recently gained traction again. Previous works report various types of multiple descending behaviors, either empirical or theoretical, but this works provides, to the best of my knowledge, the most rigorous and general example that highlights this behavior. As I don't see any major flaws, I will thus vote to accept the paper. \n\nThere are some remarks in the paper that got missed on me: \n\nRemark 2: In particular the part 'For the second part ... we can change the order of the features'. \nAt this stage of the paper it is pretty unclear how the product relates to C. But more importantly: We can change the order of the features, but what is the consequence of that/ why is that an interesting observation?\n\nRemark 3: I missed a bit the point of the remark. Is it just to demonstrate that sampling from $N^{mix}_{\\sigma,1}$ is not difficult, or is there more to it?\n\nLine 181: $x_1$ is not the best choice for the additional feature of the test vector as $x_1$ is also a training sample. For me sticking to the $b$ notation, e.g. $b^0$ or $b^{test}$, would be better to follow. \n\nThe Gaussian $\\beta$ setting:\n\nIt is a bit curious to me that we have now a distribution of $\\beta$. I did not check the proof of Theorem 10, but from the statements it seems like it also works for a single $\\beta$, by looking at the statements for $\\rho \\to 0$. It would be good if you could comment on that. Do we need it? Is it there to be more general? What do we lose/maintain if we assume a single $\\beta$. \n\nI personally find the conclusion a bit weak. I would like to see more of a discussion. You conjecture that multiple descents also occur for NN, is that based on any observation or intuition? In the beginning you state that those curves are rarely seen in practice. Does your work now shed a new light on that observation? Or at least point into a new direction to tackle it?\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for this submission. Overall, the paper presents an interesting perspective on the fact that the generalization curve can have multiple descents, and that the locations can be explicitly controlled. 

The paper well-motivates the approach. The authors have provided extensive responses to the concerns raised and the AC + reviewers really thank them for their effort. Overall, the new results obtained during the rebuttal definitely improve the quality of the paper. We all believe that the inclusion of these results during the rebuttal period is something that does not heavily change the message of this paper.

There was discussion and consensus that this work is interesting. However, there are definitely points that need to be handled, based on the discussion so far. Having in mind issues/concerns raised by the reviewers, the main points of reviewers during further discussion were that this paper deserves publication, given the promised fixes by the authors during the discussion period.
Decision: Accept (Poster)