Optimal Regularization can Mitigate Double Descent
Authors: Preetum Nakkiran
Prayaag Venkat
Sham M. Kakade
Tengyu Ma
Venue: ICLR 2021 Poster (2021)
Keywords: double descent
generalization
regularization
regression
monotonicity

Abstract: Recent empirical and theoretical studies have shown that many learning algorithms -- from linear regression to neural networks -- can have test performance that is non-monotonic in quantities such the sample size and model size. This striking phenomenon, often referred to as "double descent", has raised questions of if we need to re-think our current understanding of generalization. In this work, we study whether the double-descent phenomenon can be avoided by using optimal regularization. Theoretically, we prove that for certain linear regression models with isotropic data distribution, optimally-tuned $\ell_2$ regularization achieves monotonic test performance as we grow either the sample size or the model size.
We also demonstrate empirically that optimally-tuned $\ell_2$ regularization can mitigate double descent for more general models, including neural networks.
Our results suggest that it may also be informative to study the test risk scalings of various algorithms in the context of appropriately tuned regularization.

Published as a conference paper at ICLR 2021
OPTIMAL REGULARIZATION CAN MITIGATE DOUBLE DESCENT
Preetum Nakkiran Harvard University
Prayaag Venkat
Harvard University
preetumêcs harvard.edu
pvenkatēg. harvard.
Sham Kakade
Tengyu Ma
Microsoft Research & University of Washington shamêcs, washington edu
Stanford University
tengyuma@stanforrd. edu
ABSTRACT
Recent empirical and theoretical studies have shown that many learning algo- rithms from linear regression to neural networks have test performance that is non-monotonic in quantities such the sample size and model size. This strik- ing phenomenon, often referred we need to re-think our current understanding of generalization. In this work, we study whether the double-descent phenomenon regularization. Theoretically, we prove that for certain linear regression models with isotropic data distribution, optimally-tuned Eg regularization achieves mono- tonic test performance we grow either the sample size or the model size. We also demonstrate empirically that optimally-tuned & regularization can mitigate double descent for more general models, including neural networks. Our results suggest that may also be informative to study the test risk scalings of various algorithms in the context of appropriately tuned regularization.
"double descent", has raised questions of if
be avoided by using optimal
INTRODUCTION
Recent works have demonstrated a ubiquitous "double descent" phenomenon present in a range of machine learning models, including decision trees, random features, linear regression, and deep neural networks (Opper) 1995| [2011] Advani & Saxe 2017): Spigler et al. [0018] Belkin et al. 2018
Geiger al. 2019b; Nakkiran al. 20200 Belkin et al. 2019
Hastie et al. [019 Bartlett et al.
2019
Muthukumar et al. 2219 Bibas et al. 2019 Mitra 2019
Mei & Montanari 2019 Liang &
Rakhlin [0088]
et al. 2019 Xu Hsu 2019 Derezúíki al., | Lampinen & Ganguli
2018 Deng et al. 2019 Nakkiran 2019). The phenomenon is that models exhibit peak of high test risk when they are just barely able to fit the train set, that is, to interpolate. For example, as we increase the size of models, test risk first decreases, then increases model size is close to the training data size, and then decreases again in the overparameterized regime. Also surprising is that Nakkiran al. (2020) observe double descent sample size, i.e. for a fixed model, training the model with more data can hurt test performance.
peak around when effective
increase
These striking observations highlight potential gap in understanding of generalization and an opportunity for improved methods. Ideally, we seek to use learning algorithms which robustly improve performance the data or model size grow and do not exhibit such unexpected non- monotonic behaviors. In other words, we aim to improve the test performance in situations which would otherwise exhibit high test risk due double descent. Here, natural strategy would be to use regularizer and tune its strength on a validation set. This motivates the central question of this work:
When does optimally tuned regularization mitigate or remove the double-descent phenomenon?
Another motivation is the fact that double descent is largely observed for unregularized or under- regularized models in practice. As example, Figure shows simple linear ridge regression

---

Published as a conference paper at ICLR 2021
Test Risk for Regularized Regression
7.00
2
N
1.3
Expacted Excess Teat Bo0k
1.2
2 Mae
Figure I: Test Risk vs. Num. Samples for Isotropic Ridge Regression in = 500 dimensions. Unregularized regression is non-monotonic in samples, but optimally- regularized regression (A Aopt) is mono- tonic. In this setting, the optimal regularizer Aopt does not depend on number of samples n (Lemma 2), but this is not always true see Figure 2
1.00
0.75
0.5
0.2
Num Samples
setting in which the unregularized estimator exhibits double descent, but an optimally-tuned regu- larizer has monotonic test performance.
We study this question from both a theoretical and empirical perspective. Theoretically, we start with the setting of high-dimensional linear regression. Linear regression is sensible starting point to study these questions, since it already exhibits many of the qualitative features of double descent in more complex models (e.g. [elkinn al. (2019); (Hastie al. (2019) and further related works in Section I.I]. Our work shows that optimally -uned ridge regression can achieve both sasple-wise monotonicity and model-size-wiee monotonicity under certain assump- tions. Concretely, we show
Our Contributions:
1. Sample-wise monotonicity: In the setting of well-specified linear regression with isotropic features/covariates [.. we prove that optimally-tune ridge regression yields monotonic test performance with increasing samples. That is, more data never hurts for optimally-tuned ridge regression. (See Theorem
Model-wise monotonicity: We consider setting where the input/covariate lives in high- dimensional ambient space with isotropic covariance. Given fixed model size d (which might be much smaller than ambient dimension), we consider the family of models which first project the input random d-dimensional subspace, and then compute linear function in this projected "feature space." " (This is nearly identical to models of double-descent considered in HHattic et al. 2019 Section 5.1)). We prove that in this setting,
grow the model-size, optimally-tuned rigge regression over the projected features has monotone test performance. That is, with optimal regularization, bigger models are always better or the same. (See Theorem 3
Monotonicity in the real-world: We also demonstrate several richer empirical settings where optimal & regularization induces monotonicity, including random feature classifiers and convolu- tional neural networks. This suggests that the mitigating effect optimal regularization may hold more generally in broad machine learning contexts. (See Section 5
few remarks are in order:
Problem-specific vs Minimax and Bayesian. It is worth noting that our results hold for all linear ground-truths, rather than holding for only the worst-case ground-truth or a random ground-trute truth. Indeed, the minimax optimal estimator or the Bayes optimal estimator are both trivially sample wise and model-wisc monotonic with respect to the minimax risk or the Bayes risk. However, they do not guarantee monotonicity of the risk itself for given fixed problem. In particular, there exist minimax optimal estimators which are not momple-monotonic the sense we desire.
Universal vs Asymptotic. We also remark that our analysis is not only non-asymptotic but also works for all possible input dimensions, model sizes, and sample sizes. To our knowledge, the results herein the first asymayymto sample-wise and model-wiss monotonicity results for linear regression. (See discussion of related works Hastie et al. (2019); Mei & Montanari (2019) for related results in the asymptotic setting). Our work reveals aspects of the problem that not
2

---

Published as a conference paper at ICLR 2021
present in prior asymptotic works. For example, empirically show that optimal regularization can eliminate even "triple descent" in ridge regression (Figure 2). Moreover, we show that for non- Gaussian covariates, optimally-tunee ridge regression is not always sample-monotonic: we give
counterexample in Section 4
Towards a more general characterization. Our thcoretical results crucially rely the covariance of the data being isotropic. A natural next question is and when the same results can hold more generally. A full answer to this question is beyond the scope of this paper, though we give the following results:
Optimally-tuned ridge regression is not always ample for certain non-Gaussian data distribution and heteroscedastic noise. We are not aware of prior work pointing out this fact. (See Section for the counterexample and intuitions.)
we show a counterex-
2. For non-isotropic Gaussian covariates, we can achieve sample-wise monotonicity with regularizer that depends on the population covariance matrix data. This suggests unla- beled data might also help mitigate double descent in some settings, because the population covariance can be estimated from unlabeled data. (See Appendix B).
3. For non-isotropic Gaussian covariates, we conjecture that optimally-tuned ridge regression is sample-monotont even with a standard le regularizer (as in Figure 2 We derive a sufficient condition for this conjecture. Due that current random matrix theory may be insufficient to verify this conjecture, we verify it numerically on a wide variety of cases. (See Appendix B for details).
The last two results above highlight the importance of the form of the regularizer, which leads the open question: "How do we design good regularizers which mitigate or remove double descent?" We hope that our results can motivate future work on mitigating the double descent phenomenon, and allow us to train high performance models which do not exhibit nonmonotonic behaviors.
1.1 RELATED WORKS
The study of nonmonotonicity learning algorithms existed prior to double descent and has a long history going back to (at least) Trunk (1979) and LnCun et al. [ Cun et a (1991), where the former was largely empirical observations and the latter studied the sample non-nommonotonicity of unregularized linear regression in terms of the eigenspectrum of the covariance matrix; the difference to our works is that we study this in the context of optimal regularization. In fact, Duin (1995) 2000): Opper (2001); [oog & Duin (2012). Loog et al. (2019) introduces the same notion of risk monotonicity which we consider, and studies several examples of monotonic and non-monotonic procedures.
Double descent of test risk as a function of model size was considered recently in more generality by Belkin et al. (2018). Similar behavior was observed empirically in earlier work in somewhat more restricted settings Trunk (1979); Opper [1955] 2001); Skurichina & Duin (2022): [ee Cun et al. (19T]] LeCun et al. (1991) and more recently in Advani & Saxe (2017); Geiger et al. (2019a);
Spigler et al. (2188) Neal et al. (2018). Recently Nakkiran et al. (2020) demonstrated a generalized double descent phenomenon on modern deep networks, and highlighted "sample non-monotonicity"
as an aspect of double descent.
A recent stream of theoretical works consider model-wise double descent in simplified settings often via linear models for regression or classification. This also connects to works on high- dimentional regression in the statistics literature. A partial list of works in these areas include
Belkin et al. (2019); Hastic et al.) (2019): Bartlett et al. (2019); Muthukumar et al.] (2019): Bibas
al. (2019); Mitra 2209% Mei Montanari (2019); Liang & Rakhlin (2018); [Ling et al. (2019):
Xu & Hsu Derezinsk et al. (2019): Lampinen & Ganguli (018)) Deng et al. (2019) Nakki-
ran (2019) 9): Mahdaviych Naulet 2019); Dobriban et (2018); Dobriban & Sheng 2019) Kobak
et al. (2018). Of these, most closely related to our work are Hastie et al. (2019): Dobriban et al.
(2018); Mei & Montanari (2019). Specifically, Hastie et al. (2019) considers the risk of unregular- ized and regularized linear regression in asymptotic regime, where dimension d and number of samples n scale to infinity together, at a constant ratio d/n. In contrast, we show non-asymptotic results, and are able to consider increasing the number of samples for fixed model, without scaling
3

---

Published as a conference paper at ICLR 2021
both together. Mei & Montanari (2019) derive similar results for unregularized and regularized ran- dom features, also in an asymptotic limit. The non-asymptotic versions of the settings considered in Hastie et al. (2019) are almost identical to ours for example. projection model in Section Bis nearly identical to the model in Hastie et al. [201 Section 5.1). Finally, subsequent to our work, A'Accoli al. (2200) identified triple descent in asymptotic setting.
SAMPLE MONOTONICITY IN RIDGE RIDGRESSION
In this section, we prove that opiimally-regulaizzz ridge regression has test risk that monotonic in samples, for isotropic gaussian covariates and linear response. This confirms the behavior empir- ically observed in Figure [ We also show that this monotonicity is not "fragile", and using larger than larger regularization is still sample-monotonie (consistent with Figure
Formally, we consider the following linear regression problem in d dimensions. The input/covariate Rd generated from (0, Ia), and the output/response is generated by y (z, 3r) + E with E ~ NO0 o²) for some unknown parameter 3 E IRd. We denote the joint distribution of (zz y) by D. We are given n training examples {z y:) } i..d sampled from D. We aim to learn linear model (z) = (zz, (3) with small population risk R(3) == B(z.a))=Dl (2) (3 y) For simplicity, let X I be the data matrix that contains x.! 's contains the responses Y 's as entries. For any estimator (X,, 77) function of n samples, define the expected risk of the estimator as:
and let ÿ E R be column vector that
R(S,)=
EE [R(3,
X X,y-Dn
We consider the regularized equrrss estimator, also known the ridge regression estimator. For given À > 0, define
BB. == argmin X3 v112 + 1|1811k (XT x Xaa) -
Here La denotes the d dimensional identity matrix. Let X be the optimal ridge parameter (that achieves the minimum expected risk) given n samples: Xop := argmin H(,B.,)) Let 3er" be the estimator that corresponds the A That is, ,0pt argmin X| 5 Aap |/112-
Our main theorem in this section shows that the expected risk of अ0te monotonically decreases as n increases.
Theorem 1. In the setting above, the expected test risk of optimally-eggllarized well-specified isotropic linear regression is monotonic in samples. That is, for all f3 E R.d and all d E N, n E N. o
R(Seet S (
The above theorem shows a strong form of monotonicity, since it holds for every fixed ground- truth (3,' and does not require averaging over any prior on ground-truths. Moreover, it holds non- asymptotically, for every fixed n, d E N. Obtaining such non-asymptotic results is nontrivial, since cannot rely concentration properties of the involved random variables.
In particular, evaluating R(3:5) as a function of the problem parameters (n,0, and d) techni- cally challenging. In fact, we suspect that a simple closed form expression does not exist. The key idea towards proving the theorem
derive a "partial evaluation" the following lemmas shows that we can write R R( ) in the form of [Eg((, a, n, d, f.²)) where y E Rd contains the singular val- ues of X. We will then couple the randomness of data matrices obtained by adding single sample, and use singular value interlacing to compare their singular values.
Lemma 1. In the setting of Theorem [ let 7 (?i..... 71a) be the singular values of the data matrix X E Rnd (If n < d, we pad the 7/2 = 0 > n.) Let In be the distribution of Then, the expected test risk is
d || 11X2// 02n?
R(Bn.)) =
E (
+
(1 + X)2
4

---

Published as a conference paper at ICLR 2021
From Lemma | the below lemma follows directly by taking derivatives to find the optimal X. Lemma 2. In the setting of Theorem [ the optimal ridge parameter is constant for all n: Xn.
1|3-111 Moreover, the optimal expected test risk can be written as
da²
0²
R R(
Σ
+ +
2 do
/1
(
Proofs of Lemma 1 and 2 are deferred to the Appendix, Section A.1 Theorem
Now we are ready to prove
Proof of Theorem 7 Let X E [ and X E 1xdd be any two matrices which differ by only the last row of X. By the Cauchy interlacing theorem Theorem 4.3.4 of (Horn al. (1990) Le.f.LLemma 3.4 of Marcus al. (2014), the singular values of X and X are interlaced: Vi (X) 2 (X) 2 (xX) where (.()) is the i-th singular value.
we couple X and X, it will induce a coupling IT between the distributions Tu+1 and Ta, of the singular values of the data matrix for + 1 and samples. This coupling satisfies that 7 2 % with probability for ( [(x), {7+)) ~ II. Now, expand the test risk using Lemma 2 and observe that each term in the sum of Equation below monotone decreasing with 7/- Thus:
R(
E (m Ma)
0
(4)
2
d²
Σ
+ o²
(5)
( (m....
7
+ d
/13
R
(6)
By similar techniques, we can also prove that overregularizution -tha is, using ridge parameters À larger than the optimal value- still monotonic. This proves the behavior empirically observed in Figure
Theorem 2. In the same setting as Theorem over-regularized regression is also monotonic in samples. That is, for all d N, E N. 0, Rdd, the following holds
XA R(B4+1A) S R(3n,))
where X
2
||3
Proof. In Section A.I
MODEL-WISE MONOTONICITY IN RIDGE REGRESSION
In this section, show that for certain family of linear models, optimal regularization prevents model-wise double descent. That is, for fixed number of samples, larger models are not worse than smaller models.
We consider the following learning problem. Informally, covariates live in a p-dimensional am- bient space, and consider models which first linearly project down to random d-dimensional subspace, then perform ridge regression in that subspace for some d < Formally, the covari- ate E RP is generated from A' Tp), and the response is generated by -N o²) and for some unknown parameter 0 E RP. Next, examples {(2s, 11) ) sampled i.i.d from this distribution. For a given model size d < p, we first sample a random or- thonormal matrix P E ddxp which specifies model. We then consider models which operate on (o, 8:) E Rd x R, where o; Pr, We denote the joint distribution of (z, y) by D. Here, we emphasize that p is some large ambient dimension and d < p is the size of the model we learn.
() with
5

---

Published as a conference paper at ICLR 2021
For fixed P. we want to learn linear model fz(ā) (2. (ā. for estimating y, with small mean squared error on distribution: R3(3)= E( (ū, -) For samples (zi, 1.), let X e IRxp be the data matrix, X X p Ruxd be the projected data matrix and 7 E R" be the responses. For any estimator 3 X 57) as a function of the observed samples, define the expected risk of the estimator as:
( = E
E
[R .))
X DD
We consider the regularized least-squares estimator. For a given À >> 0, define
Bax :- argmin X 3 5 11 (X"X X + Ma) '
(8)
B
Let bo be the optimal ridge parameter (that achieves the minimum expected risk) for a model of size d, with samples: x :- argminx20 R( R(Ba,))). Let 3 be the estimator that corresponds to the Ad that is Sopt == argming | - 012 + 11 B- Now, our main theorem in this setting shows that with optimal & regularization, test performance is monotonic in model size.
Theorem 3. In the setting above, the expected test risk of the optimally tonic in the model size d. That is, for all E N, A E RP, S p. n E N. a 0, we have
model is mono-
R
R (()
The proof of Theorem is in Appendix A.2 and follows closely the proof of Theorem
4 COUNTEREXAMPLES TO MONOTONICITY
In this section, show that optimally samples. We give numeric counterexample in d = 2 dimensions, with non- -an-aussiian covariates and heteroscedastic noise. This does not contradict our main theorem Section since this distribution is not jointly Gaussian with isotropic marginals.
ridge regression is not always monotonic in
Counterexample. Here we give an example of a distribution (x, y) for which the expected error of samples. This
ridge regression with n = 2 samples is worse than with counterexample is most intuitive to understand when the ridge parameter À is allowed to depend on the specific sample instance (X, 57) as well as + We sketch the intuition for this below. Consider the following distribution on (z, y) in = dimensions. This distribution has one "clean" coordinate and one "noisy" coordinate. The distribution is: (x, 3) = (ē1, 1) with probability 1/2, and (ær, y) (02, #10) w.p. 1/2. Where 10 is uniformly random independent noise. This distribution is "well- specified" in that the optimal predictor is linear in z: Eyyy]r] (3* 2) for 3 []. However, the noise is heteroscedastic.
For 1 samples, the estimator can decide whether to use small À or large À depending on if the sampled coordinate is the "clean" or "noisy" one. Specifically, for the sample (x. y): If = E, then the optimal ridge parameter is À 0. If x: ε2 then the optimal parameter is cc.
For n = 2 samples, with probability 1/2 the two samples will hit both coordinates. In this case, the estimator must chose a single value of À uniformly for both coordinates. This yields to suboptimal tradeoff, since the "noisy" coordinate demands large regularization, but this hurts estimation on the "clean" coordinate.
turns out that a slight modification to the above also serves as a counterexample to monotonicity (and not on the instance X, y)-
when the regularization parameter À is chosen only depending The distribution is: (x. y) = (č1, w.p. 0.98 and (x, y) = (Z2, +00 w.p. 0.02. This distribution has the following property.
Theorem 4. There exists a distribution 'D over (a. for x E TR. E R with the following prop- erties. Let 3on be the pptimally-regularizze ridge regression solution for n samples (X,ğ) from D. Then:
'Recall, our model of optimal ridge regularization from Section 2 only allows À to depend on n (not on
X, v).

---

Published as a conference paper at ICLR 2021
1. D is "well-specified" in that Eplyla] is linear function of
2. The expected test risk increases as a function of between n and Specifically
R R ((
Proof. For samples, it can be confirmed analytically that the expected risk R( 8.157. This is achieved with À = 400/2401 z 0.166597. For n samples, it can be confirmed numerically (via Mathematica) that the expected risk R(5 8.179. This is achieved with 0.642525.
EXPERIMENTS
We now experimentally demonstrate that optimal & regularization can mitigate double descent, in more general settings than Theorems and
5.1 SAMPLE MONOTONICITY
Here we show various settings where optimal & regularization empirically induces sample- monotonic performance.
Nonisotropic Regression. We first consider the setting Theorem ! but with non-isotropic co- variantes x. That is, we perform ridge regression on samples (I,z). where the covariate x E Rd generated from (0, M) for ا + L7- As before, the response is generated by (z,8*) with ~ NO0, 2²) for some unknown parameter 8 Rdd. We consider the same ridge regression estimator, An,x argming |X3 e 1|
Test Risk for Reqularized Regression
Calimully
Expected Tex Bakk
Figure 2: Test Risk Num. Samples for Non-Isotropic Ridge Regression in d 30 dimensions. Unregularized re- gression is non-monotonic in samples, but optimally-regulariiee regression is monotonic. Note the optimal regulariza- tion À depends on the number of samples
Kum Sumples
Figure shows one instance of this, for a particular choice of Σ and 6*. The covariance Σ is diagonal, with Σ,, = for i S and Σ,; for i 15. That is, the covariance has one "large" eigenspace and one "small" eigenspace. The ground-truth 5" 0.1c; + cz0. which lies almost entirely within the "small" eigenspace of Σ. The noise parameter a 0.5.
We see that unregularized regression (A = 0) actually undergoes "triple descent") in this setting, with the first peak around 15 samples due the 15-dimensional large eigenspace, and the sec- ond peak at n = d. In this setting, opeimally-regularized ridge regression is empirically monotonic in samples (Figure 2 Unlike the isotropic setting of Section 2 the optimal ridge parameter X, is no longer a constant, but varies with number of samples n.
"See also the "multiple descent" behavior of kemne interpolants in Liang al. 2020

---

Published as a conference paper at ICLR 2021
Random ReLU Features. We consider random ReLU features, in the random features framework of Rahimi & Recht (2008). For a given number of features D. and number of samples n. the random feature classifer is obtained by performing regularized linear regression the embedding á == RcLU(wx)), where W E IR. Dxd is matrix with each entry sampled i.i.d N 1/Vd) and ReLU applies pointwise. This is equivalent to a 2-layer fully-connected neural network with a frozen (randomly-inttialize)) first layer, trained with & loss and weight decay. In Appendix A.4 apply random features to Baahion-MNIST(Iiaa et al. (2017). From Appendix Figure 4a
we see that underregularized models are non moootonnic but optimal lz regularization monotonic in samples. Moreover, the optimal ridge parameter À appears to be constant for all n. similar to our results from the isotropic setting in Theorem
5.2 MODEL-SIZE MONOTONICITY
Here empirically show that optimal & regularization can mitigate model-wise double descent.
Random ReLU Features. We consider the same experimental setup as in Section but now fix number samples n,, and vary the number random features D. This corresponds to varying the width of the corresponding 2-layer neural network. Figure 4b in Appendix [A.4] shows the test error of the random features classifier, for n = 500 train samples and varying number of random features. We see that underregularized models undergo model-wist double descent, but optimal &g regularization prevents double descent.
Convolutional Neural Networks. We follow the experimental setup of Nakkiran et al.] (2020) for model- wise double descent, and add varying amounts of lg regularization (weight decay). We chose the following set- ting from Nakkiran et al. (200)), be- cause it exhibits double descent with no added label noise. We con- sider the same family of 5-layer con- volutional neural networks (CNNs) from Nakkiran
Regulartzation: CIFAR-100
000000
000
Tout Enerr
Er
64
al.) (2020), con-
sisting of 4 convolutional layers of widths [k. 2k, 4k: 8&) for varying E
CNN Model Size (width)
N. We train and test CIFAR- 100 (Krizhevsky et al. 2009), an im- age classification problem with 100 classes. Inputs are normalized to []1, and we standard data-augmentation of random horizontal flip and random crop with 4- pixel padding. All models are trained using Stochastic Gradient Descent (SGD) on the cross-entropy loss, with step size 0.1/ OT1/VLT/512 +1 at step T. We train for 1e6 gradient steps, and use weight decay À for varying A. Due optimization instabilities for large X, we use the model with the min- imum train loss among the last 5K gradient steps. Figure showws the test error of these models on CIFAR- 100. Although unregularized and under-reguarized models exhibit double descent, the test error of optimally reguulaieeg models is largely monotonie. Note that the optimal regularization À varies with the model size no single regularization value is optimal for all models.
Figure 3: Test Error vs. Model Size for 5-layer CNNs on CIFAR-100, with & regularization (weight decay). Note that the optimal regularization À varies with n.
DISCUSSION AND CONCLUSION
In this work, we study the double descent phenomenon in the context of optimal regularization. We show that, while unregularized or under-regularized models often have non-monotonic behavior, appropriate regularization can eliminate this effect.
Theoretically, we prove that for certain linear regression models with isotropic covariates, optimally- tuned & regularization achieves monotonic test performance as we grow either the sample size or the model size. These the first non-asymptotic monotonicity results are aware of in linear
8

---

Published as a conference paper at ICLR 2021
regression. We also demonstrate empirically that optimally-tuned &z regularization mitigate double descent for more general models, including neural networks. We hope that our results can motivate future work mitigating the double descent phenomenon, and allow us to train high performance models which do not exhibit unexpected nonmonotonic behaviors.
Open Questions. Our work suggests a number of natural open questions. First, it is open to prove (or disprove) that optimal ridge regression is sample-monotonic for non-isotropic Gaussian covariates. We conjecture that is, and outline a potential route to proving this (via Conjectures [] and 2 in the Appendix). Second, more broadly, it is open to prove sample-wise monotonicity for more general (non-linear) models with appropriate regularizers. Finally, is open to understand why large neural networks in practice often sample-monotonic in realistic regimes of sample sizes, even without careful choice of regularization.
model-wiss
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in neural networks, arXiv preprint arXiv: 17000:6770 2017.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. arXiv preprint arXiv:1906. 1300, 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the biai-variance trade-off. arXiv preprint arXiv: (112.18811.111111 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv 2019.
preprint
Koby Bibas, Yaniv Fogel, and Meir Feder. A new look at old problem: A universal learning approach to linear regression. arXiv preprint 19X5v:/905.4470 2019.
Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where why do they appear? arXiv preprint 200v::2000.030099 2020.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. arXiv preprint 19x: 191.5582. 2019.
Michat Dereziáski, Feynman Liang, and Michael W. Mahoney, Exact expressions for double descent and implicit regularization via surrogate random design, 2019.
Edgar Dobriban and Yue Sheng. Wonder: Weighted one-shot distributed ridge regression in high dimensions. arXiv preprint arXiv:1903.09920 2019.
Edgar Dobriban, Stefan Wager, et al. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Robert PW Duin. Small sample size generalization. In Proceedings of the Scandinavian Confer- ence on Image Analysis, volume 2, pp. 957-964. PROCEEDINGS PUBLISHED BY VARIOUS PUBLISHERS, 1995.
Robert PW Duin. Classifiers in almost empty spaces. In Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, volume 2, pp. 1-7. IEEE, 2000.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' A'Ascoli, Giulio Biroli, Clément Hongler, and Matthicu Wyart. Scaling description of generalization with number of parameters in deep learning. arXiv preprint 1xXiv:1901.01600 2019a.
Mario Geiger, Stefano Spigler, Stéphane d' Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition as paradigm to understand the loss landscape of deep neural networks. Physical Review E, 100(1):012115 2019b.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation, 2019.

---

Published as a conference paper at ICLR 2021
Roger A Horn, Roger A Horn, and Charles R Johnson. Matrix Analysis. Press, 1990.
Cambridge University
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. Optimal ridge penalty for real-world high- dimensional data can be zero negative due the implicit ridge regularization. arXiv preprint 17X.::/805.10930 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Andrew Lampinen and Surya Ganguli. An analytic theory generalization dynamics and transfer learning in deep linear networks. arXiv preprint arXiv: 1809. 2018.
Yann Le Cun, Ido Kanter, and Sara A Solla. Eigenvalues of covariance matrices: Application to neural-network learning. Physical Review Letters, 66 (6)32,,,,, 1991.
Yann LeCun, Ido Kanter, and Sara A Solla. Second order properties of error surfaces: Learning time
and generalization. In Advances in neural information processing systems, pp. 118-924, 1991.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can gener-
alize. arXiv preprint 1108:01800.003330 2018.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the risk of minimum-now norm interpolants and restricted lower isometry of kernels. arXiv preprint arXiv:1908.10220 2019.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai On the multiple descent of minimum-nome interpolants and restricted lower isometry of kernels. 2020.
Marco Loog and Robert PW Duin. The dipping phenomenon. In Joint IAPR International Work- shops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 310-317 Springer, 2012.
Marco Loog, Tom Viering, and Alexander Mey. Minimizers of the empirical risk and risk mono- tonicity. In Advances in Neural Information Processing Systems, pp. 7476-7485, 2019.
Yasaman Mahdaviyeh and Zacharie Naulet. Asymptotic risk of least squares minimum norm esti- mator under the spike covariance model. arXiv preprint 1xXi::1112.33421, 2019.
Adam W Mareus, Daniel Spielman, and Nikhil Srivastava. Ramanujan graphs and the solution of the kadison-singer problem. arXiv preprint arXiv:1408.44 4421, 2014.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprini vrXiv:/908.05330 2019.
Partha Mitra. Understanding overfitting peaks in generalization error: Analytical risk curves for 12 and Il penalized interpolation. ArXiv, 0bs/1906.03661 2019.
Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai. Harmless interpolation of noisy data in regression. arXiv preprint arXiv:/903.09: /90./9999.99 2019.
Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv 2019.
preprint urXiv:19/2.077
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference on Learn- ing Representations, 2020. JRLhttpa hatpo::///ppereeee www.review..eeeeooo .wt.//ee//eeeee..eee peee:/fooummmdddllgss44-3
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and loannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. arXiv preprint arXiv: 18.881000000 0005919, 2018.
Manfred Opper. Statistical mechanics of learning: Generalization. The Handbook of Brain Theory and Neural Networks, 922-925., 1995.
Manfred Opper. Learning to generalize. Frontiers of Life, 3(part 2), pp. pp.763-775., 2001.
10

---

Published as a conference paper at ICLR 2021
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008.
Marina Skurichina and Robert PW Duin. Bagging, boosting and the random subspace method for linear classifiers. Pattern Analysis & Applications, 5(2): 2002.
Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to prraeaarattiinttionn affects loss landscape and generaliza- tion, arXiv preprint arXiv: 1010v088100090000 2018.
Gerard Trunk. A problem of dimensionalityy; A simple example. IEEE Transactions on pattern analysis and machine intelligence, (3):306-307, 1979.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint (00.:::778,77777,, 2017.
Ji Xu and Daniel J Hsu. On the number of variables to use in principal component regression. In Advances in Neural Information Processing Systems, pp. 5095-5104, 2019.

---

Published as a conference paper at ICLR 2021
A APPENDIX
In Section A. and A.2 we provide the proofs for sample-monotonicity and model-size monotonic-
ity. In Section A.4 include additional and omitted plots. In Section B investigate whether monotonicity provably holds in more general models, and present a monotonicity conjecture for non-isotropic covariates.
A.
SAMPLE MONOTONICITY PROOFS
First we prove Lemma I
Proof of Lemmal 7
For isotropic z, the test risk related to the parameter error as:
R(ß) = (s.n))
((xx B) y)
[1(0, B - 8*) + n)
z~NNO.1a),.~
|| 31 +
Plugging in the form of Bn, and expanding:
R(Br,)): E
[R(Gn.))
Xm
=E(llAnA - B- + o²
E X A1) 11 X 31 +02
X.y
[|[Xx*x xX) + 1) - 1-11 +02
=BIIIX"X 11 x" -
-
lX X1) x n
X,
x - +
" X x 0
Now let X UEVT be the full singular value decomposition of X, with U E Raxn E E Raxd V E Rdxd, Let (7,... 78) denote the singular values, defining % = for > min(n, Then, continuing:
R((B.a)) = E [|diag((
+
E Σ
+ +
(9)
(
+
X)2
7
E
||diaa|(
))
+
E
+ o²
(10)
2~Unif([]
Ila8d
E)
7/ +
(x + X)2
||
2
+ t
E Σ Σ
7
2
+ t
(11)
d
( A)2
(7) + イ3²
||3 13 o²
227
1+
(12)
(7/ + 2)²
In Line (10) follows because by symmetry, the distribution of V is uniformly random orthonormal matrix, and Σ is independent of V. Thus, VT is distributed as a uniformly random point on the unit sphere of radius ||,8111 [|2-
Next prove Lemma
12

---

Published as a conference paper at ICLR 2021
Proof of Lemma
2
First, determine the optimal ridge parameter. Using Lemma
have
① R(Bm,))= = Ob (1)m--77))
/d+ o2n?
01
(7 + A)
7
= 20113~122/d 0²)
E
(7) + X)3
(T)
Thus, 0% ((Br,))) =0 x
do² and we conclude that X
do²
11
|| 112
For this optimal parameter, the test risk follows from Lemma
R( R(3 n.)=)
(13)
d
+ +
(14)
Li=l V do 2
/
Proof of Theorem 2 We follow a similar proof strategy as in Theorem we invoke singular value interlacing (% 2 7%) for the data matrix when adding single sample. We then apply Lemma to argue that the test risk varies monotonically with the singular values.
We have
113-1122206 0277
R(Bm.N)
E
(1 X)2
S(m))
and compute how each term in the sum varies with 7::
0 Σ S(m) = S(y))
0%
0%
( (220% 27/
2| 11222 do (1 A)
(7 + X)3
Thus we have
d
8
A
S(x) 50
(15)
2-1--12
By the coupling argument in Theorem this implies that the test risk is monotonic:
R(31+12)
R(Baa))
d
Σ s(1))
E
Σ
S(%k))
E
i=1
aiml
Σ S(%))
s(x))
(16)
((.)..)))
<
(17)
where II is the coupling. Line
17 follows from Equation (15). and the fact that the coupling obeys
%, > T.
13

---

Published as a conference paper at ICLR 2021
A.2 PROJECTION MODEL PROOFS
Lemma 3. For all 0 E IRP, d, n E N, and À > O, let X E RaxP be a matrix with iid. (( 1) entries. Let P E _dxp be random orthonormal matrix. Define X == XPP. Let (......, 7m) be the singular values of the data matrix X E Bx for i > min(n, d)). Let a be the distribution of singular values (mm)...mm)).
max(n, d) (with % for
Then, the optimal ridge parameter constant for all d: Xa
p²a² बाo.
where we define 0²
o² + -=111013 Moreover, the optimal expected test risk can be writlen as
P
R(
Proof. This proof follows exactly analogously as the proof of Lemma from Lemma I in Sec- tion A.1
Lemma 4. For all 0 E IR, d, n E N. and > O, let Raxp be a matrix with i.idd N0, entries. Let P E Raxp be a random orthonormal matrix. Define X == XPT and 8 := P8.
Let (71...., Pmm be the singular values of the data matrix X E RRd for m == max(n, d) (with T1 for min(n, d)). Let I' be the distribution of singular values (?1,...:7m) 7mm)
Then, the expected test risk is
R(Ba,)) =
E x.y-Da
(Rx(aax(Xx)))
= 0² + (1
11011
p (a
101 + - 1101
+
(7 + A)
(m
Proof of Lemma directly that:
We first define the parameter that minimizes the population risk.
follows
Bp = argmin Rp(33= = PO
BERd
First, we can expand the risk
R(θ) = E [((Px, 33 - =)
(18)
(7.0)~
E
((sr, PT 0) + 1)
(19)
(Bw)>-Drr-N
0² + +110 PTBII
(20)
= o² + 110 - 3-113 + ||P 3r - PT 312
pTT
(21)
+ 2(( 3²) pT 8r PTT (3)
(22)
0² + |10 - pTp 3-1 + || - PT 313
(23)
= 0² + 100 - pm
P0l p0 1 + 1133" - -B11
(24)
The cross terms in Line 3* satisfies P(6" PT
vanish because the first-order optimality condition for 3r implies that 0. We now simplify each of the two remaining terms.
First, we have that:
d
E|10
E P
PT P0 = (1
0
(25)
p
14

---

Published as a conference paper at ICLR 2021
since pTP is orthogonal projection onto random d-dimensional subspace.
Now, recall we have = X00 + 7) where 1) ,N(0,, IQ.)) Expand this as:
7 = XO + 7
(26)
XP" P0 X(1 - PT P)0 +1
(27)
X +
(28)
where := ([--11PPpp)) Note that conditioned on P. the three terms X, and are conditionally independent, since pT and (I pTPP) P) project X onto orthogonal subspaces. And further, E N/ [1 pd m))
E E |13 - 3 P P
(29)
= =E E |1
3
(30)
P
= =E E
|1(X X X7) (x*++++**)))) 3
(31)
E ||(X* A7) xT 18
(32)
P "
+ +1[(X + - 5 1 + 11 A
(33)
(34)
Now, since X is conditionally independent of conditioned on P.
E E || X + A7) $112
(35)
P
X.meeP
E E P XIP
III(X
X + X1)
X
E |1
(36)
E|P
EII(X
X + + -
E [1
(37)
=EII(X X + -
(1| P'' P)0
(by definition of E)
P.X
= X7 x
|2:
P
10
(38)
p
where Line (37) holds because the marginal distribution of X does not depend on P.
Similarly,
E |1X* XI) n P X.nllp
(39)
0² B'
XI -
X +
(40)
Now let X U be the full singular value decomposition of X, with U E pax" Σ Raxd V E [gdxd, Let (7.... 7m) denote the singular values, where m = max(n, d) and defining 7. 0 for i min(n,d) d).
Observe that by symmetry, X - XPT and P are independent, because the joint distribution (X, P) is equivalent the distribution (XQ, PQ) for random orthonormal Q RRxx Thus X and
15

---

Published as a conference paper at ICLR 2021
3 = P9 are also independent, and we have:
E X
X
-X X8* -
(41)
-
E E [I|diag(
{
7/2 + }) 3)1
(42)
3' V.
E
[|]diag(
(1
})V
3-1
(43)
8+ V.:.
7/
+ x
-X (1
E
E
||<diag(
))=1
(44)
8
*~Unni((]
11222 1)
+ A
113-11
2
X2
E 1**
2 +
2j2
(45)
1 P011
X²
(46)
h X)2
p
d
(47)
Aj2
Finally, continuing from Line 33 we can use Lines
38
40
and
(4
to write:
EE E |1B 1=
(48)
X,
= (o² + p
11013) E X + -
(49)
X²
+
101 1 E
(50)
+ A|2
p d
(0²
+
1
1
E
(51)
p
D
(7F + Aj2
d
A²
+
1101
2 E
(52)
(72 + A)2
202
+ R-d 10 13 +
10118
=
E
(7 + A)²
(53)
Now, we can continue from Line 24p. and apply lines 25 to conclude:
B[R(,)] = 0² + E110 PT
PO
1 + ElI
1118--1133 31
d
0² + (1
10100
p'
(02 + p-d
d |10| 100 + / 110113X2
+ E
(1 + A)²
Proof of Theorem This follows analogously to the proof of Theorem 1 Let X, and X be the observed data matrices for d and + 1 model size. As in Theorem [ there exists a coupling II between the distributions Fa and Ta41 of the singular values of X, and X such that these singular values are interlaced.
16

---

Published as a conference paper at ICLR 2021
Thus by Lemma S
0²
R(32T) = 0²
E
(m
2
0²
d
101
2 σ²
E
Σ
Tm
7/
02
1=1
R 2+1)
A.3 NONISOTROPIC REDUCTION
Here observe that results isotropic regression in Section 2 also imply that ridge regression can made sample-monotonic even for non-isotropic covariates, an appropriate regularzier is applied. Specifically, the regularizer depends the covariance the inputs. This follows from general equivalence between the non-isotropic and isotropic problems.
Lemma 5. For all n E N, N, R, R, covariance Σ Rdxdd PSD matrix Rdxdd and ground-truth 3 E IRS, the following holds.
Consider the following two problems:
Regularized regression on isotropic covariates, and an M-regularizer That is, suppose n samples (I, y) are drawn with covariates ~ NNO,, Ta) and response = (3" x) + N (0, o²). Let X E gaxd be the matrix of covariates, and ÿ the vector of responses. Consider
Bx = argmin X - 312 + Al
(54)
Let R - Exx, 11B
112] ²² be the expected test risk of the above estimator.
2. Regularized regression with covariance E, and an (2 That is,
suppose samples (ž, y) are drawn with covariates NN,,E) and response y (z",0) + +NO a2), for
--
Let E nxd be the matrix of covariates, and y the vector of responses. Consider
4x argmin | - m1 + || /
(55)
Let R R z" = + o² be the expected test risk of the above estimator.
Then, the expected test risks of the above two problems are identical:
R
Proof of Lemma The distribution of X the Problem equivalent XΣ where as in Problem Thus, the two settings are equivalent by the change-of-
1//2.. Specifically,
ΣΛ == argmin | T + /2ME1/2
(56)
2
argmin |xy
v + Ao 1/2 MY
(57)
argmin
12 v1 + X 1 /2
(58)
1-1/2 argmin | गl + A3 M3
(59)
8-11/22
17

---

Published as a conference paper at ICLR 2021
Further, the response (2", .)) (B, x²), and the test risk transforms identically:
=
E 2l 2" 23115 + o²
(60)
X,y
E [113 11 +
(61)
X.9
R
(62)
This implies that if the covariance Σ is known, then ridge regression with a E-1 regularizer is sample-monoton
Theorem 5. For all n. E R, covariance E E Rdddd and ground-truthe 3 E Rd the following holds.
Suppose n samples (x. u) are drawn with covariates I ~ -N(0, Σ) and response = (3* 2) + (0,00 o²). Let X E Raxd be the matrix covariates, and the vector of responses. For X 0. consider the ridge regression estimator with ) -regularize:
Bn,x =- argmin || 1713 1111133
(63)
3- 6² be the expected test risk of the above estimator. Let Xop be the optimal ridge parameter (that achieves the minimum expected risk) given n samples:
Let R=
A
argmin R(3r,2)
(64)
And let 3%th be the estimator that corresponds to the Na. Then, the expected test risk of optimally- regularized linear regression monotonic in samples:
R R( S ((t)
Proof. This follows directly by applying the reduction in Lemma 5 for M La to reduce to the isotropic case, and then applying the monotonicity of isotropic regression from Theorem I
A.4 ADDITIONAL PLOTS
We apply random features Fashion-MNIST Xiao al. (017). image classification problem with 10 classes. Input images x E Rd are normalized and flattened to [_,,1] for d = 784. Class labels are encoded as one-hot vectors y E {ci.....ii } C R0
B TOWARDS MONOTONICITY WITH GENERAL COVARIATES
Here we investigate whether monotonicity provably holds in more general models, inspired by the experimental results. As a first step, we consider Gaussian (but not isotropic) covariances and homeostatic noise. That is. we consider ridge regression in the setting of Section 2 but with x (0, Σ), and y (r. 3r*) + N(0, a²). this section, we observe that ridge regression can monotonic with a modified regularizer. We also conjecture that ridge regression be made sample-monotonic
sample- monotonic without modifying the regularizer, and we outline a potential proof strategy along with numerical evidence.
B. ADAPTIVE REGULARIZATION
The results isotropic regression in Section imply that ridge regression be made sample- monotonic even for non-isotropic covariates, if an appropriate regularizer is applied. Specifically, the appropriate regularizer depends on the covariance of the inputs. For A (0, 2), the following estimator
X: â..A := argming | - / + A|| 1 2 This follows directly from Theorem [ by applying change-of variable: full details of this equiva- lence are in Section A.3 Note that the population covariance Σ is not known, it can potentially be estimated from unlabeled data.
monotonic for optimally-tum
18

---

Published as a conference paper at ICLR 2021
Test Error for Regularized Random Features
Test Error for Regularized Random Fealures
2=2
0.1
38-
2-2
4-20
Expected Text Eron
0.1
Expected
641
34-
63
Num Samples
Model Size (Num Features)
(a) Test Classification Error vs. Number of Train- ing Samples.
(b) Test Classification Error vs. Model
Size
(Numbber of Random Features).
Figure 4: Double-descent for Random ReLU Features. Test classification error as a function of model size and sample size for Random ReLU Features on Fashion-MNIST, Left: with D 500 features. Right: with n = 500 samples. See Figures 7 for the corresponding test Mean Squared
Error. See Appendix D of Nakkiran et al. (2020) for the performance of these unregularized models plotted across Num. Samples x Model Size simultaneously.
Effect Regularization: CNNs CIFAR-100
wnight riecyy -
weight decay 0,2006
weight dieny
meight diecay 0.305
0.8
weight decay 0.21
Train
02
CNN Model Size (width)
Figure 5: Train Error Model Size for 5-layer CNNs on CIFAR-100, with b regularization
(weight decay).
B.2 TOWARDS PROVING MONOTONICITY
We conjecture that optimally-regularizee ridge regression is sample-monotonic for non-isotropic covariates, even without modifying the regularizer (as suggested by the experiment Figure We derive a sufficient condition for monotonicity, which we have numerically verified in a varicty of instances. Specifically, we conjecture the following.
Conjecture 1. For all d E N, and all PSD covariances Σ Rdxd, consider the distribution (x, y) where x ~ (0, Σ), and y ~ (e, N(0, Then, we conjecture that the expected test risk of the ridge regression estimator: Bn.2 == argning ||X 5 B|sll|k for optimally-tumed is monotone non-increasing in number of samples n. That is, for all n E N,
inf R(Ba+1.)) < inf R(,r.)) X
(65)
A20
where we define B., lim -0 3n, Xty.
19

---

Published as a conference paper at ICLR 2021
Train MSE for Reqularized Regression
00"2
do"2
60"2"
A- d0
2.0
Expected Train MSE
1.0
30
50
Samples
Figure 6: Train MSE vs. Num. Samples for Non-lsotropic Ridge Regression in d = 30 dimensions,
in the setting of Figure Plotting train MSE: 1| y7 l.
Test MSE for Regularized Random Features
2.00
2-2 A 70
2=
A=2 'd
An
1.50
Expected Test MSE
1.00
0.50
0.00
1000
Samples
Figure 7: Test Mean Squared Error vs. Num Train Samples for Random ReLU Features on Fashion- MNIST, with D 500 features.
present technical conjecture in random matrix theory (Conjecture which suffices to prove Conjecture [ Proving this Conjecture()Iprseeet
In Appendix B.3
a number technical chaglenges, but we have numerically verified it in variety of cases. It can also be shown that Conjecture is true when Q = T, corresponding to isotropic covariates. We prove the reduction between Conjecture and Appendix B.3
B.3 MONOTONICITY CONJECTURE PROOFS
In order establish Conjecture it is sufficient prove the following technical conjecture.
20

---

Published as a conference paper at ICLR 2021
Test MSE for Regularized Random Features
2,00
2 2d
A 2d
2
A- 2d
1.50
Expected Test MSE
1.00
0.50
0.00
1000
Model Size (Num Features)
Figure 8: Test Mean Squared Error vs. Num Features for Random ReLU Features on Fashion- MNIST, with n 500 samples.
Conjecture 2. For all N, d n1, following holds.
symmetric positive definite matrix Q E Raxd the
Define
G = X E + xQ)
where X E Bund is sampled with each entry i.i.d. // 1). Similarly, define
H : X xQ)
The expected test risk for samples can be expressed as:
= G + oo'H H + to²
(66)
Then, we conjecture that the following two conditions hold.
1.
G G
(67)
2.
dGR/dd id) dH /d> - 0
(G) - G (H) H
(68)
Lemma 6. Conjecture implies Conjecture
Proof. By the reduction in Section A.3 showing monotonicity for non-isotropic regression with an isotropic regularizer is equivalent to showing monotonicity for isotropic regression with a non- isotropic regularizer. Thus, we consider the latter. Specifically, Conjecture is equivalent showing monotonicity for the estimator
Bn,A argmin X - +
(69)
(70)
where & AO0 7) is isotropic, and
(x, B*) + 00,
21

---

Published as a conference paper at ICLR 2021
Now, letting Q = E-!, the expected test risk of this estimator for samples is:
R(Bm.))
E 1115ma 1-1 0
X.9
E [1(XX x +xA0)=1xx* 3 -
XW
(x--)( [||XX -Q) + 3
- =EIlIXX AQ) X2 X5 - 83 + II - xQ)
= XQ) +
+Y -Q-0- - + + x
=X2 = AQ) 10
+ 10)
= XAQ) 0²
G 0² H3 +
Consider the infimum
inf R(3m,a) X20
(71)
We consider several cases below.
Case (1). Suppose the infimum in Equation 71 is achieved in the limit À - +oc. In this case, monotonicity trivially holds, since
lim R(Sm,)) R(O) lim R(Bx+1,)
Case (2). Suppose the infimum in Equation 71 achieved by some X X in the interior of the set (0, oc).
Because x((r..) is continuous and differentiable in À for all (0, o0), have that X must satisfy the following first-order optimality condition:
dR..Bn.))
0
(72)
dX
A=
dG
dH
(B+)T
8
0
(73)
dA
d1
A=
We will later use this condition show monotonicity.
Case (3). Suppose the infimum in Equation 71 is achieved at opt = 0. Recall, we define Bn,o ==
limx-10+ An,x- This means that,
dR(3
-
dG dd
dHs
3r
+
o²
2 0
(74)
dd
A==
d)
A==
Note that since dH < 0, both Equations that
73 and
74
Case (2) and Case (3) respectively imply
0² (T*)T( dG? )
(75)
/
A A=
Now, assuming Conjecture we will show that the choice of oot in Cases (2) and (3) has non- increasing test risk for (n + T) samples. That is,
2 R((B+1.x))
This implies the desired monotonicity, since R(3 R(33+1,N7) 2 R(B (1(0+11
22

---

Published as a conference paper at ICLR 2021
We first consider the case when Hx assumption, we have
Hx*1 >>=> 2 0. In this case, because G³
-x*11
20by by
R(, =( = (8*)T(GT
+ to Gg
- -
(76)
1=
2 0
(77)
Otherwise, assume. H Hxx A= A= S 0. Then we have:
R(Om.xx)) - -R(8 (80)=((") x 10- o -
(78)
(H A=
dG", di
2
- - (3
dHH /dx
Am
(by Equation 75). and 1
11
- 0)
G2tt (H) 1 dGz /dd
(8
3"
(79)
dHR/d2
1==
= Conjecture 2
20
(80)
desired.
23


Reviews:
[{"review_id": "wW5XLve9llz", "reviewer": "AnonReviewer1", "summary": "", "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_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider the problem of double descent in regularized linear regression estimators, and show that, with optimal regularization, such problems can be totally mitigated when the covariates are isotropic gaussian. Additionally, the authors show that there exist cases where ridge regression is provably non-monotonic in its average risk. These theoretical results are complemented with some empirical results on ridge regression and small scale neural networks.\n\nThe phenomenon of double descent has gathered substantial interest in the past couple of years, and this paper presents an interesting contribution towards cementing our understanding in the context of double descent in linear models. Although the obtained results are perhaps not overly surprising given the strong connection between the ridge estimator and linear regression with isotropic gaussian variables and homoskedastic gaussian noise, the finite-sample proofs characterize the phenomenon in a concise manner. The paper is clearly written, and exposes the results in a clear and accessible fashion. However, the impact of this paper is limited by the fact that the general phenomenon of regularization avoiding double descent is well-known (if not necessarily in such an explicit setup, at least from considerations in the Bayes-risk or minimax-risk framework, and penalized regression in general), and that interest in double descent mostly stems from the existence of this behavior in unregularized settings.\n\nOther notes: there are some typos (especially in the appendix):\nP.16 regularzier -> regularizer\nP. 17 homeostatic -> homoskedastic\n\n=====================\n\nUpdate after author response: I thank the authors for their responses. I broadly agree with the points brought up by the other reviewers, and despite some weaknesses brought up by various reviewers, this paper is a good contribution to the community. I have brought my score from 6 to 7.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dn3-o2c5hpa", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the double-descent phenomenon from a theoretical perspective. It proves that for certain linear regression tasks, optimally-tuned L-2 regularized model is able to achieve monotonic test performance as the sample size or the model size increases. Empirical results on the effect of L-2 regularization on the double-descent phenomenon are provided for more general models and tasks.\n\n\nPros:\n\n+ The motivation of studying the double-descent phenomenon with optimal regularization is well-explained in the introduction. Connections and comparisons with existing related works are discussed clearly.\n\n+ The presented theoretical results on the linear regression model are non-asymptotic, which is new and different from existing works. The theoretical results are discussed with enough details such that I can easily follow the Lemmas and Theorems.\n\n\nCons:\n\n- My main concern is the generality of the results. The paper mainly focuses on a simplified linear regression model, where the response variable is linearly generated using some ground-truth parameters \\beta^*. One question is whether the results apply to the agnostic settings (the relationship between x and y is unknown)? Moreover, going beyond regression tasks, can we draw the same conclusion for classification tasks? \n\n- The experiments need to be more extensive and better-explained, especially for the CIFAR-100 experiments. This is an image classification task, which is different from previously introduced regression setting. It is important to discuss this difference clearly at the beginning. In addition, the author uses a 5-layer CNN architecture, whereas the state-of-the-art CIFAR-100 results adopts a much larger architecture. Varying architecture size and even considering more image benchmarks would strengthen the experiments.\n\n\nMinor Comments:\n\n1. For Figure 3, it seems that for certain model size, the optimally-regularized test error is much lower than any other one. How do you compute the optimally regularized curve in Figure 3?\n\n===== Post-Discussion Update =====\n\nI thank the authors' efforts for responding my questions. Overall, I find the results presented in the paper interesting and worth publishing. It would be nice to extend the results to more general settings.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9lknDoIrEpm", "reviewer": "AnonReviewer2", "summary": "", "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_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "he paper studies the surprising phenomenon of “double descent” in machine learning models which has recently come into light through many prior works. The phenomenon is used to describe the behavior of test performance of an estimator as the model parameters (complexity) or the number of samples are increased. It is observed that in many cases, the test error first decreases then increases attaining a peak and then starts to decrease again as the number of model parameters (or samples) are increased. This pervades many different models including neural networks, decision trees and linear regression.\nPrior works have noted that this occurs primarily for unregularized or under-regularized models and that leads to the motivating question for this work: can optimal regularization remove double-descent? The paper studies this question from a theoretical and empirical perspective. \nTheoretical: For the setting of linear regression the authors show that an optimal amount of l2 regularizer added to the objective completely removes the double descent phenomenon with respect to both number of samples and number of model parameters. \nEmpirical: For random feature classifiers and convolutional neural networks, the authors empirically show that an optimal amount of l2 regularization removes the appearance of double descent curves.\n\nIn terms of the theoretical analysis provided in this paper, a highlight is that the results are non-asymptotic and the Theorems identify precise values of the different parameters when the double descent phenomenon disappears. \nThe theoretical results have the caveat that they apply only when the input data is Gaussian. If the data is not Gaussian, l2 regularization might not be able to remove double descent as the authors demonstrate via the means of a counterexample. Moreover, if the covariates are not isotropic, then the authors conjecture but cant prove that optimal l2 regularization suffices.\n\nIn my view, the paper takes an important question and analyzes it well from a theoretical angle and also provides empirical evidence to back up its main message in more complex models. The proofs are non-trivial and I think the paper adds value in improving our understanding of the double descent phenomenon by providing a clear picture of the non-asymptotic regime.\n\n\nQuestions:\n1. If I recall prior works correctly, many of them point out that double descent continues to hold even under different regularization schemes both theoretically and empirically. What changed here or what were the prior works missing? I am asking this because based on prior work your result sends a conflicting message that we can get rid of double descent and also not sacrifice performance at the same time.\n2. Curious to hear what happens if we look at deeper neural networks? Could the optimal regularization amount be so high that it starts to hurt performance?\n3. Equation (9) in the Appendix would benefit from more explanation. In particular, the calculation showing how we arrive at the singular values of the matrix (X^TX + lambdaI)^-1X^T.\n\nMinor typos:\n1. Abstract: “quantities such as the …”\n2. Extra bracket in definition of lambda_n^opt on page 4\n\n\n-------------\n\nThank you to the authors for their response. It has helped clear some questions I had in mind. I am keeping my rating.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0uLR7_q331c", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the double descent phenomena -- for increasing sample/model size -- in linear ridge regression. When the model is well-specified and the features are drawn from an isotropic Gaussian distribution, for the optimal (or larger than optimal) ridge regularization parameter, the authors show that there will be no double descent with respect to the sample size, i.e. the test error monotonically decreases as a function of the sample size. Furthermore, under a (randomly) projected feature space model, they showed that the test performance is also monotone with respect to projection size. The authors verify some of the the theoretical findings in practice, and show that the same insights carry over for more complicated models.\n\n++:\nThe paper studies a fundamental question in theoretical machine learning.\nThe claims are supported both by clean theoretical results as well as empirical evaluations.\n\n--:\nThe proof techniques seem to heavily depend on the specific choice of the loss function and the regularizer, that is, the mean squared loss and the ridge penalty. It is not clear if the techniques can generalize to other settings.\n\nQuestion / Minor Comment:\nThe paper puts forward the idea that double descent is an artifact of underregularization. To be more precise, the main takeaway from the paper is that optimal \\ell_2-regularization can mitigate double descent, provably in certain linear ridge regression problems; and in practice, in certain deep learning problems. A natural question is if authors have observed similar phenomena under different regularization techniques, including other norm-based penalties, or the more exotic ones from the deep learning literature.\nI suggest that in the experiments section, you clearly state how you obtain the optimal regularization parameter in each of the subsections.\nWhy does the experiments section only cover the “sample monotonicity” part of the theoretical results (Theorems 1 and 2)? I think it helps if you verify Theorem 3 as well.\nCan you comment on the requirement d <= p in Theorem 3? It’s true that d > p will not give a subspace of the p-dimensional ambient space, but one can perhaps extend the setting to d > p requiring that P^T P = I_p. \n\nOverall, I enjoyed reading the paper and recommend it for acceptance in ICLR. The paper is well-written for the most part. I found the theoretical results insightful, and well-supported by experiments.\n\n\n\n#####################################\nI have considered the rebuttal as well as other comments in my final recommendation.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Quality: the paper takes an important question and analyzes it well from a theoretical angle; it also provides empirical evidence to back up its main message in more complex models. The proofs are non-trivial. The paper adds value in improving our understanding of the double descent phenomenon by providing a clear picture of the non-asymptotic regime.

Clarity: The motivation of studying the double-descent phenomenon with optimal regularization is well-explained in the introduction. Connections and comparisons with existing related works are discussed clearly. The paper is clearly written, and exposes the results in a clear and accessible fashion. 

Originality: The presented theoretical results on the linear regression model are non-asymptotic, which is new and different from existing works. 

Significance: The proof techniques seem to heavily depend on the specific choice of the loss function and the regularizer, that is, the mean squared loss and the ridge penalty. It is not clear if the techniques can generalize to other settings, which affects its significance.

Main Pros:
- the paper takes an important question and analyzes it well from a theoretical angle. The proofs are non-trivial; the paper adds value in improving our understanding of the double descent phenomenon by providing a clear picture of the non-asymptotic regime.

Main Cons:
- Generality of the results. The paper mainly focuses on a simplified linear regression model, where the response variable is linearly generated using some ground-truth parameters \beta^*. 
- The experiments need to be more extensive and better-explained, especially for the CIFAR-100 experiments. It is important to discuss this difference clearly at the beginning. 
Decision: Accept (Poster)