More is Better: when Infinite Overparameterization is Optimal and Overfitting is Obligatory
Authors: James B Simon
Dhruva Karkada
Nikhil Ghosh
Mikhail Belkin
Venue: ICLR 2024 poster (2024)
Keywords: overparameterization
interpolation
random feature regression
kernel regression
generalization
overfitting
Primary area: learning theory
TL;DR: We show that (a) random feature regression strictly benefits from additional features and (b) a realistic class of kernel learning task requires (near-)zero regularization to reach optimal performance.

Abstract: In our era of enormous neural networks, empirical progress has been driven by the philosophy that *more is better.*
Recent deep learning practice has found repeatedly that larger model size, more data, and more computation (resulting in lower training loss) optimizing to near-interpolation improves performance. In this paper, we give theoretical backing to these empirical observations by showing that these three properties hold in random feature (RF) regression, a class of models equivalent to shallow networks with only the last layer trained.

Concretely, we first show that the test risk of RF regression decreases monotonically with both the number of features and samples, provided the ridge penalty is tuned optimally. In particular, this implies that infinite width RF architectures are preferable to those of any finite width. We then proceed to demonstrate that, for a large class of tasks characterized by powerlaw eigenstructure, training to near-zero training loss is *obligatory:* near-optimal performance can *only* be achieved when the training error is much smaller than the test error. Grounding our theory in real-world data, we find empirically that standard computer vision tasks with convolutional neural kernels clearly fall into this class. Taken together, our results tell a simple, testable story of the benefits of overparameterization and overfitting in random feature models.

Published as a conference paper at ICLR 2024
MORE IS BETTER IN MODERN MACHINE LEARNING: WHEN INFINITE OVERPARAMETERIZATION IS OPTIMAL
AND OVERFITTING IS OBLIGATORY
James B. Simon* UC Berkeley & Imbue
Dhruva Karkada UC Berkeley
Nikhil Ghosh UC Berkeley
Mikhail Belkin UC San Diego
ABSTRACT
In our era of enormous neural networks, empirical progress has been driven by the philosophy that more is better. Recent deep learning practice has found repeatedly that larger model size, more data, and more computation (resulting in lower training loss) improves performance. In this paper, we give theoretical backing to these empirical observations by showing that these three properties hold in random feature (RF) regression, class of models equivalent to shallow networks with only the last layer trained.
Concretely, we first show that the test risk of RF regression decreases monotonically with both the number of features and the number of samples, provided the ridge penalty is tuned optimally. In particular, this implics that infinite width RF archi- tectures are preferable to those of any finite width. We then proceed to demonstrate that, for a large class of tasks characterized by powerlaw eigenstructure, training near-zero training loss obligatory: near-optimal performance can only be achieved when the training error is much smaller than the test error. Grounding our theory in real-world data, find empirically that standard computer vision tasks with convolutional neural tangent kernels clearly fall into this class. Taken together, our results tell simple, testable story of the benefits of overparameteriiation,, overfitting, and more data in random feature models.
INTRODUCTION
It is an empirical fact that more is better in modern machine learning. State-of-the-art models are commonly trained with as many parameters and for as many iterations as compute budgets allow, often with little regularization. This ethos of enormous, underregularized models contrasts sharply with the received wisdom of classical statistics, which suggests small, parsimonious models and strong regularization to make training and test losses similar. The development of new theoretical results consistent with the success of overparameterized, underregularized modern machine learning has been a central goal of the field for some years.
How might such theoretical results look? Consider the well-tested observation that wider networks virtually always achieve better performance, so long as they are properly tuned (Kaplan et al.) 2020 Hoffmann et al. 2022 Yang et al. (022). Let & (n, w, 0) denote the expected test error of network with width w and training hyperparameters 0 when trained on n samples from an arbitrary distribution. A satisfactory explanation for this observation might be hypothetical theorem which states the following:
wf w, then min (n, w/ 0) min Ew w. 0).
0
Such a result would do much to bring deep learning theory up to date with practice. In this work, we take a first step towards this general result by proving in the special case of RF regression that is, for shallow networks with only the second layer trained. Our Theorem [ states that, for RF regression, more features (as well as more data) is better, and thus infinite width is best. To our knowledge, this is the first analysis directly showing that for arbitrary tasks, wider is better for networks of a certain architecture.
How might a comparable result for overfitting look? It is by now established wisdom that optimal performance in many domains is achieved when training deep networks to nearly the point of
jamess s mon@berkeley.edd

---

Published as a conference paper at ICLR 2024
interpolation (i.e. zero training error), with train error many times smaller than test error Neyshabur et al. (2015); Zhang et al. (2017): [Belkin et al. (2018), Appendix F Hf & Belkin (2021) p. However, unlike the statement "wider is better," the statement "interpolation is optimal" cannot be true for generic task distributions: we can see this a priori by noting that any fitting at all can only harm us if the task is pure noise and the optimal predictor is thus zero. Indeed. Nakkiran & Bansal (2020) and Mallinar et al. (2022) empirically observe that training to interpolation harms the performance of real deep networks on sufficiently noisy tasks. This suggests that we instead ought to seek an appropriate class C of model-task pairs - idcally general enough to include realistic tasks such that a hypothetical statement of the following form is true:
For model-task pairs in C, at optimal regularization, it holds that Rir/te == Err Eye
< 1.
Here we have defined the fitring ratio Ray/te to be the ratio of train error En and test error & and we have suppressed the arguments of & and &. for the sake of generality, We take step towards this general result, too, by proving a sharp statement to this effect for kernel ridge regression (KRR), including anfinite-feature RF regression and infinite-width neural networks of any depth in the kernel regime (Jacot et al. [2018] Lee et al. (019)) Letting C. be the set of tasks with powerlaw eigenstructure (Definition 2. our Theorem 2 states that under mild conditions on the powerlaw exponents, not only is Ra/e < at optimal regularization, but in fact this overfitting is obligatory: attaining near-optimal
test error requires that Re/tte < 1 Crucially, we put our proposed explanation to the experimental test: we clearly find that the eigenstrruture of standard computer vision tasks with convolutional neural kernels displays powerlaw decay in satisfaction of our "obligatory overfitting" criteria, and indeed optimality occurs at Ru//te for these tasks (Figure
All our main results rely on closed form estimates for the train and test error of RF regression and KRR in terms of task eigenstructure. We derive such an estimate for RF regression, and our "more is better" conclusion (Theorem [ follows quickly from this general result. This estimate relies on Gaussian universality ansatz (which we validate empirically) and becomes exact in an appropriate asymptotic limit, though we see excellent agreement with experiment even at modest size. When we study overfitting in KRR. which is the infinite- feature limit of RF regression, we use the featuree-fatuuee limit of our eigenframework. which recovers a well-known risk estimate for (kernel) ridge regression extensively investigated in the recent literature (Sollich) 2001 Bordelon et al. 2020 Jacot et al., 2020a; Dobriban & Wager] 2018: Hastie et af.. 2022)) We solve this eigenframework for powerlaw task eigenstructure, obtaining an expression for test error in terms of the powerlaw exponents and the fitting ratio Rur/te (Lemma and our "obligatory overfitting" conclusion (Theorem 2 and Corollary [ follows from this general result. Remarkably, we find that real datasets match our proposed powerlaw structure so well that we can closely predict test error as a function of RTy/te purely from experimentally extracted values of the powerlaw exponents a, / (Figure 2) To conclude, we return to the question of how one ought to view modern machine learning, suggesting some intuitions consistent with our findings.
Concretely, our contributions are as follows:
We obtain general closed-form estimates for the train and test risk of RF regression in terms of task cigenstructure (Section
We conclude from the general estimate for test risk that, at optimal ridge parameter, more features and more data are strictly beneficial (Theorem
We study KRR for tasks with powerlaw eigenstructure, finding that for a subset of such tasks, overfitting is obligatory: optimal performance is only achieved at small or zero regularization (Theorem 2).
We demonstrate that standard image datasets with convolutional kernels satisfy our criteria for obligatory overfitting (Figure 2
'This is in contrast with the proposed phenomenon of "benign overfitting" (Bartlett et al. 2020 Tsigler
& Bartlett] (023) in which interpolation (i.e. training to zero train loss) is merely harmless, incurring only aub-leading-owe oodder cost relative optimal regularization. In our "obligatory overfitting" regime, interpolation necessary, and not interpolating incurs leading-order cost.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
The benefits of overparameterizatoon Much theoretical work has aimed to explain the benefits of overparameterization. Belkin et al. (2019) identify a "double-descent" phenomenon in which, for certain underregularized learning rules, increasing overparamettrrization improves performance. Ghosh & Belkin (2023) show that only highly overparameterized models can both interpolate noisy data and generalize well. Roberts et al. (2022); ; Atanasov et al. (2023); Bordelon & Pehlevan (2023) show that neural networks of finite width can be viewed as (biased) noisy approximations to their inith counterparts, with the noise decreasing as width grows, which is consistent
with our conclusion that wider is better for RF regression. Nakkiran et al. (202I) prove that more features benefits RF regression in the special case of isotropic covariates; our Theorem [ extends their results to the general case, resolving conjecture of theirs. Concurrent work (Patil & Du 2023) also resolves this conjecture, showing sample-wise monotonicity for ridge regression. Yang & Suzuki (2023) also show that sample-wist monotonicity holds for isotropic linear regression given optimal dropout regularization. Kelly et al. (2022) study RF regression for time series, showing that more overparameeerization strictly improves certain performance measures of interest in financial forecasting. It has also been argued that overparameterization provides benefits in terms of allowing efficient optimization (Jacot et al.] 2018: Liu et al. [0222. network expressivity (Cybenko 1989 Lu
ct al. 2017). and adversarial robustness Bubecck & Sellke, 2021).
The generalization of RF regression. RF (ridge) regression was first proposed by Rahimi & Recht (2007) as a cheap approximation to KRR. Its generalization was first studied using classical capacity- based bounds Rahimi & Recht ( Rudi & Rosasco (007)). In the modern era, RF regression has seen renewed theoretical attention due to its analytical tractability and variable parameter count. Gerace et al.] (2020) find closed-fore equations for the test error of RF regression with a fixed projection matrix. Jacot et al. (2020b) show that the average RF predictor for a given dataset resembles a KRR predictor with greater ridge parameter. Mei & Montanari (2019): Mei et al.) (2022) find closed-form equations for the average-case test error of RF regression in the special case of high-dimensional isotropic covariates. Maloney et al. (2022) find equations for the average test error of a general model of RF regression under a special "teacher equals student" condition on the task eigenstructure, and |aahh (203) similarly solved RF regression for the case of zero ridge. We report a general RF eigenframework that subsumes many of these Glseed-form solutions as special cases (see Appendix F.. Our eigenframework can also be extracted, with some algebra, from replica calculations reported by Atanasov el al. (2023) (Section D.5.2) and Zavatone- Veth & Pehlevan (2023) (Proposition 3.1).
Interpolation is optimal. Many recent works have aimed to identify settings in which optimal generalization on noisy data may be achieved by interpolating methods, including local interpolating
schemes (Belkin et al. 2018) and ridge regression (Liang & Rakhlin 2020 Muthukumar et al. 2020 Koehler et al. 2021 Bartlett et al.) 2020 Tsigler & Bartlett [023] Zhou et 2023). However, is not usually the case in these works that (near- (etar-)intepollatoon is required to generalize optimally, as seen in practice. We argue that this is because these works focus entirely on the model, whereas one must also identify suitable conditions on the task being learned in order to make such a claim. Several papers have described ridge regression settings in which negative ridge parameter is in fact optimal (Kobak et al. 2020 Wu & Xu 2020 Tsigler & Bartlett 2023). We consider only nonnegative ridge in this work to align with deep learning, but our findings are consistent with the task criterion found by Wu & Xu 22020 2 In a similar spirit, Cheng et al. (2022) prove in Bayesian linear regression setting that for low noise, algorithms must fit substantially below the noise floor to avoid being suboptimal.
3 PRELIMINARIES
We will work in a standard supervised setting: our dataset consists of n samples X' = (2; ) sampled i...d. from a measure Ha over Rd. We wish to learn target function f. (which we assume to be square-integrable with respect to μt), and are provided noisy training labels y )_ where y/- f- (z:) + (O o²) with noise level x² 2 O. Once learning rule returns predicted function f. we evaluate its train and test mean-squared error, given by MSF E,((s)) - )² and MSE Ex-p, (f(x) (x)) + 0² respectively.
Some of our results - for example, Corollary i give inequalities which, if satisfied, imply that zero ridge is optimal. It is generally the case that, when such an inequality is satisfied strictly (i.e. we do not have equality), a negative ridge would have heen optimal had we allowed it.
3

---

Published as a conference paper at ICLR 2024
RF regression is learning rule defined by the following procedure. First, sample k weight vectors {w, [00) i.i.d. from some measure Poi over IR?. We then define the featurization transformation db x +> (Q(w,,)))
where g RR x TRd R a feature function which square-integrable with respect to foe and piz. Finally, we perform standard linear ridge regression over the featurized data: that is, we output the function f(x) a" (x)), where the weights a are given by (IIT + 8kIz)= - B with v ((b(z)).... (bxx) and 0 a ridge parameter. If the feature function has the form g(w,ar = h(w" x)) with d and some nonlinearity h, then this model is precisely shallow neural network with only the second layer trained.
RF regression is equivalent to kernel ridge regression
(x) k (Kxx ;
where the vector [kax)); = (xx m.) and matrix [Kxxli = R (z) contain evaluations of the (stochastic) random feature kernel (xxxx') g(w,
x²). Note that as k the kernel converges in probability its expectation (xxxx') _ ((x,x') == Ew () and RF regression converges KRR with the deterministic kernel K.
3.1 SPECTRAL DECOMPOSITION OF AND THE GAUSSIAN UNIVERSALITY ANSATZ Here say what mean by "task eigenstructure" in RF regression. Consider the bounded linear operator T: (pw) + (12()z) defined as
(Tu)(a) - Sfe v(w)g(w, x ddd (w:).
The operator T' is a Selbbett-Sehmitt operator which the singular value decomposition can be applied to (Kato 2013). That is, there is an orthonormal basis (G) of (Ker T) S (1w(ww) and an orthonormal basis ) of ((z) such that TG: = VA,Ø,. Here {>r] are the non-negative eigenvalues indexed in decreasing order and {ø, j are the corresponding eigenfunctions of the integral operator Σ (3(mx) - (3(pz) given by
(Eu)(v) - -/6- ((=)K(( (x).
-
If we denote T (px))) + (pw) as the adjoint of T. then E = TT* Moreover, the feature function admits the decomposition g(w,,) = E. ( (x)), where the convergence is in T,2 (pw & ). The decomposition of the deterministic kernel K is given by
(xx, y) En (g(,, x)g(wr, x')]= = Σ (xdr(1)o.(y).
Note that the learning problem is specified entirely by (n, k, (Ar), (2r). (s.). (d.}).
The functions (Gi) {ør} viewed random variables induced by juw and Hsr respectively can have a complicated distribution. However, since the functions form orthonormal bases, we know that the random variables are uncorrelated and have second moments equal to one that is, Eurau (C
Ez-ua (ox))))) (x))) dy.- To make progress, throughout the text will use the following Gaussian universality ansatz and assume that the distributions may be treated uncorrelated Gaussians:
Assumption (Gaussian universality ansatz). The expected train and test error are unchanged if we replace {S.) {or by random Gaussian functions {š.), {or} such that when sampling w ~ Pww the values } are i..dd. samples from N(0, 1), and likewise for x Pz and (o))
Assumption A seems strong first glance. It is made plausible by many comparable universality results in random matrix theory which state that, when computing certain scalar quantities derived from large random matrices, only the first two moments of the elementwise distribution matter (up to some technical conditions), and the elements can thus be replaced by Gaussians for more convenient analysis (Davidson & Szarek 2001 Tao 2023p. Assumption AJholds provably for RF regression in certain asymptotic settings see, example. (Mei & Montanari 2019 Mei et al. 2022). Most encouragingly. recent results for the test error of KRR derived using a comparable condition show
excellent agreement with the test error computed real data at moderate sample size (Sollich) 2001
4

---

Published as a conference paper at ICLR 2024
Bordelon al. 2020 Jacot al. 2020a; Simon et al. 2021 Loureiro et al., 2021 Wei et al. 2022)
so we might expect to observe a similar universality RF regression. Indeed, we will shortly validate Assumption A empirically, demonstrating excellent agreement between predictions for Gaussian statisties and RF experiments with real data (Figure D) Given that our ultimate goal is understand learning from real data, this empirical agreement is reassuring.
Under this universality ansatz, the statisties of the eigenfunctions may be neglected, and the learning task is specified entirely by the remaining variables (n, k, 6, { {v;}). We will now give a set of closed-form equations which estimate train and test error in terms of these quantities.
MORE DATA AND FEATURES ARE BETTER IN RF REGRESSION
4.1 THE OMNISCIENT RISK ESTIMATE FOR RF REGRESSION
In this section, will first state risk estimate for RF regression, which will enable to conclude that more data and features are better.
Let K, 7 2 0 be the unique nonnegative scalars such that
Σ
A
and
k
X
(2)
X
7
K
A
+
Let Es A and = Ei K,ty
d
The test and train error of RF regression are given
1.ty
approximately by
xA k 7)
MSEec R E
Σ
of
+ o²
(3)
1
glk +=
d +7
n(k--)) 4)
82
MSE &
Exe.
(4)
n²
Following Breiman Freedman [9833) : Wei ct al. 2022), ) we refer to Equation as the omniscient risk estimate for RF regression because it relies ground-truth information about the task (i.e., the true eigenvalues {},} and target eigencoefficients (v:)). We refer to the boxed equations, together with estimates for the bias, variance, and expectation of given in Appendix E.5 as the RF eigenframework: Several comments are now in order.
Like the framework of Bach (2023), our RF eigenframework is expected to become exact (with the error hidden by the "x"" going zero) in a proportional limit where n, k, and the number of cigenvalues diverge together. However, we will soon see that it agrees well with experiment even at modest k. This eigenframework generalizes and unifies several known results which we elaborate upon in Appendix F
Deriving the omniscient risk estimate for RF regression. We give complete derivation of our RF eigenframework in Appendix [ and give a brief sketch here. It is obtained from the fact that RF regression is KRR (c.f. Equation] with a stochastic kernel. As discussed in the introduction, many recent works have converged on an omniscient risk estimate for KRR under the universality ansatz, and if we knew certain eigenstatistics this known estimate for KRR and be done. Our main effort is in estimating these eigenstatistics using handful of random matrix theory facts, after which we may read off the omniscient risk estimate for RF regression. Our derivation is nonrigorous, but we conjecture that it can be made rigorous with explicit error bounds decaying with n. k as in Cheng & Montanari (022)).
the stochastic RF kernel K, we could simply insert them into
Plan of attack. Our approach for the rest of the paper will be to rigorously prove facts about the deterministic quantities Ene and &nr given by our omniscient risk estimates in Equations 3 and 4
4.2 THE "MORE IS BETTER" PROPERTY RF REGRESSION
We now state the main result of this section.
MMore precisely: in this limit, one can consider taking -> 1yn, ht + 77K, and duplicating each eigenmode Alternatvell, eigenmodes can be sampled from a fixed
times for integer n) and then taking spectral distribution.
5

---

Published as a conference paper at ICLR 2024
Gaussian RF @ Gaussian data
Random ReLU features & CIFARIO
4 100
ridge 5
3x 10
experiment
101
train (theory)
2x 10
test (theory)
10
MSE
optiimal ridge
104
100
10a
6010
4 1010
10a
10
10a
10a
101
10a 10a
number of random features k
Figure I: At optimal ridge, more features monotonically improves test performance. Train and test errors for RF regression closely match Equations (3) and (4) for both synthetic Gaussian data and CIFARIO with random ReLU features. Plots show traces with n 256 samples and varying number of features k. See Appendix A for experimental details and more plots.
Theorem 1 (More is better for RF regression). Let (n, k, 8) denote E with n samples, k features, and ridge 8 with any task eigenstructure {Xi (v:) Let n' 2 2 0 and k' 2 k 2 0. It holds that
min Ene W, 8') S min Exe (nc 8),
(5)
8'
with strict inequality so long as (n, k) + (n', k') and E, X > (i.e., the target has nonzero learnable component).
The proof, given in Appendix G is elementary and follows directly from Equation Theorem states that the addition of either more data or more random features can only improve generalization error so long as we are free to choose the ridge parameter 6. It is counterintuitive from the perspective of classical statistics, which warns against overparameteriiation: by contrast, we that performance increases with additional overparameterizatton, with the limiting KRR predictor being the optimal stochastic approximation to
learning rule. However, this is sensible if one views RF regression KRR: the more features, the better the approximation to the ideal limiting process. This interpretation lines up nicely with recent theoretical intuitions viewing infinite-width deep networks noiseless limiting processes (Bahri et al. 202T Atanasov et al. 2023 Yang et al.) 2022).
4.3 EXPERIMENTS: VALIDATING THE RF EIGENFRAMEWORK
We perform RF regression experiments using real and synthetic data. Synthetic experiments use Gaussian data (0, diag (A+)) with X; = i-13 and simple projection features g ((w 27) = w x with Gaussian weights w ~ (O, La). Experiments with real datasets use random ReLU features g(w, xx) = ReLU(wi z) with Gaussian weights w ~ (O, 2Iz); the corresponding theoretical predictions use task eigenstructure extracted numerically from the full dataset. The results, shown in Figure T and elaborated in Appendix A show excellent agreement between measured test and train errors and our theoretical predictions. The good match to real data justifies the Gaussian universality ansatz used derive the framework (Assumption A).
5 OVERFITTING IS OBLIGATORY FOR KRR WITH POWERLAW EIGENSTRUCTURE
Having established that more data and more features are better for RF regression, now seek an explanation for why "more fitting" - that is, little to no regularization - is also often optimal. As we now know that infinite-feature models are always best, in our quest for optimality we simply take k - oo for the remainder of the paper and study the KRR limit. When it - oo, our RF eigenframework reduces to the well-established omniscient risk estimate for KRR, which we write explicitly in Appendix I.T We will demonstrate that overfitting is obligatory for class of tasks with powerlaw eigenstructure.
Defining "overfitting." How should one quantify the notion of "overfitting"? some sense, we mean that the optimal ridge parameter d, which minimizes test error & is "small." However, d, will usually decay with n, so unclear how define "small." In this work, we define overfitting via the fitting ratio Ruy/te = E EurEEe E [0. 11. which has the advantage of remaining order unity even as n diverges. The fitting ratio is strictly increasing function of the ridge 8, with Ruy/te when 5 and Ryyr 1 as 8- xo. Therefore, rather than minimizing & with respect to 5 [0, oo),

---

Published as a conference paper at ICLR 2024
equivalently minimize E with respect Ru/le" E [0. 1). We will take the term "oveefitting" to mean that Ru/te <>
Definition (Optimal ridge, test error, and fitting ratio), The optimal ridge d., optimal test error & and optimal fitting ratio Rir/to are equal to the values of these quantities at the ridge that minimizes test error. That is,
6, arg min Exe,
Ege Ewl6=6,.
Rit/te Rus/te 1==6.
(6)
If the optimal fitting ratio R Re/te" == arg min Ene is small - that is, if R 1r/tc < - we may say that overfitting is optimal. If it is also true that any Ru/le" > Ris/te gives higher test error, we say that
overfitting is obligatory.
In this section, we will describe a class of tasks with powerlaw eigenstructure for which overfitting is provably obligatory. For all powerlaw tasks, we will find that Riz/te is bounded away from (Theorem Given an additional condition namely, noise not too big, and an inequality satisfied by the exponents - we find that Ri// = (Corollary D. Remarkably, when we examine real learning tasks with convolutional kernels, we will observe powerlaw structure in satisfaction of this obligatory overfitting condition, and indeed we will see that Ri///e 0.
Definition 2 (ar, powerlaw eigenstructuree. A KRR task has a, 8 powerlaw eigenstructure for exponents a > 1, E (1,2a + 1) there exists an integer by > 0 such that, for all 2 ip. the task cigenvalues and cigencoeffients obey A = i and o. = i-
In words, task has 3 powerlaw eigenstructure if the task cigenvalues {A, and squared eigencoefficients {u, ) have powerlaw tails with exponents a, B. The technical condition & < 2a + 1 needed for our proofs is mild, and we will find it is comfortably satisfied in practice.
Target noise. We will permit tasks to have nonzero noise. However, we must be mindful of a subtle but crucial point: do not want to take fixed noise variance o² @(1), independent of n. The reason is that the unlearned part of the signal will decay with n, so x² does not decay, the noise will eventually overwhelm the uncaptured signal. At this point, we might as well be training on pure noise. this case, maximal regularization is optimal, and the model cannot possibly benefit from overfitting, as discussed in Section | We give a careful justification of this key point and compare with the benign overfitting literature in Appendix H
We instead consider the setting where the noise 0² scales down in proportion to the uncaptured signal To do so, we
=²= Ewlor=8-o
where o = ((1) is the relative noise level and E is the test error at noise and zero ridge. This scaling also has the happy benefit of simplifying many of our final expressions. (We note that this question of noise scaling will ultimately prove purely academic when we turn to real datasets, we will find that all are very well described with o² identically zero.)
We now state our main results.
Theorem 2. Consider a KRR task with a, 3 powerlaw eigenstructure. Let the optimal fitting ratio and optimal test risk be given by Definition 1 At optimal ridge, the fitting ratio is
Rij/te 2 + Onn7)
(8)
where y. is either the unique solution to
a- (a- 1 1)3r. + ala- -) -1))) - -2.00-0--2-- =0
(9)
over v. E 1), or else zero if no such solution exists, and 7: min(1, 2a 3). Furthermore, this fitting ratio is the unique optimum (up to error decaying in n)) in the sense that
Exe
> 1 + Co (V - Coapte-VRiipee RRijue)
2
+ O(n
(10)
8
(a-1)² a²
where Ca =
7

---

Published as a conference paper at ICLR 2024
The first part of Theorem gives an equation whose solution is the optimal fitting ratio Rifte under powerlaw eigenstructure. The second part is strong- sroog-convexitty-ttyy guarantee that, unless we indeed tuned near Ri we will obtain test error E worse than optimal by a constant factor greater than one. The proof of Theorem consists of direct computation of & at large n,, together with the 6² The difficulty lies largely in the technical task of bounding error
observation that Rayle= zz2zz. terms. We give the proof Appendix
The optimal fitting ratio Riytte given by Theorem will always be bounded away from 1. This implies that some overfitting will always be obligatory in order to reach near-optimal test error. The following corollary, which follows immediately from Theorem 2 gives a necessary and sufficient condition under which Rif/ ~ 0 and interpolation (i.e. zero ridge) is obligatory.
Corollary 1. Consider KRR task with o; powerlaw eigenstructure. The optimal fitring ratio vanishes that Rig/1e -+
if and only
oet < 3-a
(11)
ala-1
First, we must have at otherwise, the RHS of Equation 11 is negative. Larger 33 means that the error decays faster with n (Cui et al. 2021). so 3 2 a amounts to a requirement that the task is sufficiently easy Second, we must have sufficiently small noise relative to the uncaptured signal & ===6=0. More noise is permissible when the difference B a is greater, which is sensible since noise serves to make a task harder. The fact that zero regularization can be the unique optimum label noise is surprising from the perspective of classical statistics, which cautions against fitting below the noise level.
Corollary 1 gives an elegant picture of what makes a task interpolation-fries
with nonzero
With zero noise. Theorem simplifies to the following corollary for the optimal fitting ratio:
Corollary 2. Consider a KRR task with a, 3 powerlaw eigenstructure. When 0² 0, the optimal fitting ratio at large n converges to
(a-9)²
if <
Rif
(12)
0
if 2
Corollary 2 implies in particular that even if is slightly smaller than a, we will still find that R 2
O.
5.1 EXPERIMENTS: OVERHITING IS OBLIGATORY FOR MNIST, SVHN AND CIFARIO IMAGE DATASETS
We ultimately set out to understand an empirical phenomenon: the optimality of interpolation in many deep learning tasks. Having proposed model for this phenomenon, is crucial that we now turn back to experiment and put it to the empirical test. We do so now with standard image datasets learned by convolutional neural tangent kernels. Running KRR with varying amounts of regularization, we observe that R Rs 0 and (near-) sitarr)interollation is indeed obligatory for all three datasets (Figure 2}. This is due to both favorable task structure and low intrinsic noise: as we add artificial label noise, R is no longer zero, in accordance with Corollary I We also find that adding label noise increases Ri/e in accordance with our theory.
Even more remarkably, we find excellent quantitative fit our Lemma TO which predicts E as function of Ruj/ue ax, B, o up to a multiplicative constant. This surprising agreement attests that, insofar as the effect of regularization is concerned, the relevant structure of these datasets can be summarized by just the two scalars ox B. These experiments resoundingly validate our theoretical picture for the examined tasks.
Measuring the exponents a. B3. We examine three standard image datasets MNIST, SVHN. and CIFARIO - and run KRR with the Myrtle convolutional neural tangent kernel (Shankar et al. 2020).
'More precisely. since larger corresponds to stronger inductive biases, 3 means that in some sense "the task is no harder than the model anticipated."
8

---

Published as a conference paper at ICLR 2024
CIFAR1O: (é, (1.17, 1.14)
SVHN: (á. B) = (1.22, 1.20)
MNIST: (á. 3) (1.12, 1.36)
100
test MSE
Fully interplating
hally interolaann
fully Interpolating
noise ded
50
experiment
10a1
theory (uncorrpped)
theory (noise added)
10a1
10
0.0
1.0
fitting ratio Rin/to
MSE
MSE
Figure 2: Overfitting is obligatory in standard computer vision tasks. We run KRR with convolutional NTKs on three tasks using varying ridge parameter and label noise, measuring test error and the fitting ratio Ru/ww- We then compare to theoretical predictions (c.f. Lemma 10 computed
from measured powerlaw exponents à, B. When no noise is added, we observe that the optimal fitting ratio is R ~ 0 (blue vertical dotted line) and (near-)interpolation is required to achieve optimal error. These tasks have low intrinsic noisc, and as label noise is added, R becomes nonzero, as predicted by Corollary [ Curves with noise added are rescaled to preserve total task power. See Appendix B for exponent measurements and Appendix for full experimental details.
We also report results for F-MNIST in Appendix We wish to check for powerlaw decay x xx i-a and of x i and estimate the exponents a, B.
We measure a using the method of Wei et al. 2022)) Assuming X; x i-a, it is easily shown that at zero ridge, the implicit regularization constant & in the eigenframework decays with n as <(n) x n n (sec c.g. our Lemma Wei et al. (0022) show, theoretically under Gaussian universality and empirically for real data, that k(n) is well approximated by x(n) 2 Tr Ti[K,l where K,, is the empirical kernel matrix plotting many points (n, Tr[K, n I E R.2 on a log-log plot and fitting a line.
samples. An estimate à of the true exponent a may thus be extracted by
To measure B, we make use of the eigenframework prediction that, with n samples, zero ridge, and = zero noise, the test risk decays as MSE (n) = (ne x n -(8-1) (see e.g. Cui et al. (2021) ) or our Lemma 3). Like with we can thus extract an estimate ,9 of the true exponent by plotting many points (n, (. E 2 on log-log plot and fitting line.
DISCUSSION
The present work is part of the research program aiming understand the shortcomings of classical learning theory and to develop analyses suitable to machine learning as it exists today. We have presented two tractable models capturing the "more is better" spirit of deep learning, but we cannot consider this quest done until we have not only transparent models but also coherent new intuitions to take the place of appealing but outdated classical ones. To that end, we propose a few here.
One well--eellbelleved classical nugget of wisdom is the following: Overparameterization is harmful because it permits models to express complicated, poorly-generalizing solutions. Taking inspiration from our RF models, perhaps ought instead to believe the following: Overparameterization is desirable because bigger models more closely approximate an ideal limiting process with infinitely many parameters. Overparameterization does permit a model to express complicated, poorly- generalizing solutions, but does not mean that will actually learn such thing: models are simple creatures and tend not to learn unnecessarily complication without good reason to.
Another classical view is that interpolation is undesirable because if a model interpolates, it has fit the noise, and so will generalize poorly. Our story with KRR suggests that perhaps we should instead hold the following belief: So long as the inductive bias of the model is a good match for the task and the noise is not too large, additional regularization is unnecessary, and it is optimal to fit with train error much less than test error.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
IS thanks Alex Maloney, Alex Wei, Ben Adlam, Berfin Şimşek, Blake Bordelon, Jacob Zavatone- Veth, Francis Bach, Michael Weese, and Theo Misiakiewiez for useful discussions the generalization of RF regression, as well as Roman Novak and Song Mei for useful discussions on the eigenstructure of image tasks early in the development of empirical measurements. JS used Zymbolic for rapid math typesetting. JS gratefully acknowledges support from the National Science Foundation Graduate Fellow Research Program (NSF-GRFP) under grant DGE 1752814, MB acknowledges support from National Science Foundation (NSF) and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning hhttps: : deep coundatioon. ai/) through awards DMS-203 1883 and #814639 and the TILOS institute (NSF CCF-2112665). This work used the programs (1) XSEDE (Extreme science and engineering discovery environment) which is supported by NSF grant numbers ACI-1548555 1548562, and (2) ACCESS (Advanced cyberinfrastructure coordination ecosystem: services & support) which is supported by NSF grants numbers #2138259, #2138286, #21 #2337777, #2137603, and #21 13829.. Specifically, we used the resources from SDSC Expanse GPU compute nodes, and NCSA Delta system, via allocations TG-CIS220009.
SUMMARY OF CONTRIBUTIONS
IS developed the main theoretical results, wrote the manuscript, and led the team logistically. DK developed and performed all experiments and assisted in writing. NG aided in framing the overall narrative, assisted in writing, and provided key technical insights during the development of the theory. MB proposed this line of study and provided overarching guidance throughout the project.
REFERENCES
Alexander Atanasov, Blake Bordelon. Sabarish Sainathan, and Cengiz Pehlevan. The onset of variance-limited behavior for networks in the lazy and rich regimes. In The Eleventh International Conference on Leurning Representations, 2023.
Francis Bach. High-dimension analysis of double descent for linear regression with random projections. arXiv preprint arXiv:2503.01372, 2023.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06700) 2021.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1177449:30003-30007 2020.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31, 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnin practice and the classical bias- variance trade-off. Proceedings of the National Academy of Sciences, 116632):15849-1555 2019.
Blake Bordelon and Cengiz Pehlevan. Dynamics of finite width kernel and prediction fluctuations in mean field neural networks. arXiv preprint arXiv:2304.03400 2023.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1034-1034. PMLR, 2020.
Leo Breiman and David Freedman. How many variables should be entered in a regression equation? Journal of the American Statistical Association, 78(381):131-16, 1983.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34:28811 1-28222, 2021.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model align- ment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1):1-12, 2021.
10

---

Published as a conference paper at ICLR 2024
Chen Cheng and Andrea Montanari. arXiv:2210.08571, 2022.
Dimension free ridge regression. arXiv preprint
Chen Cheng. John Duchi, and Rohith Kuditipudi. Memorize to generalize: on the necessity of interpolation in high dimensional linear regression. In Conference on Learning Theory, pp- 5528-55600 PMLR, 2022.
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34: 34:10131-10143, 2021.
George Cybenko.
Approximation by superpositions a sigmoidal function. Mathematics of control, signals and systems, 2(4): -14,,, 1989.
Kenneth R. Davidson and Stanislaw Szarek. Chapter 8 local operator theory, random matrices and banach spaces. In Handbook of the Geometry of Banach Spaces, volume of Handbook of the Geometry of Banach Spaces, pp. 317-366. Elsevier Science V., 2001.
Edgar Dobriban and Stefan Wager. High-dimensional asympe of predictions: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. General- isation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pp. -452-3462. PMLR, 2020.
Nikhil Ghosh and Mikhail Belkin. A universal trade-off between the model size, test loss, and training loss of linear predictors. SIAM Journal on Mathematics of Data Science, 5(4):977-1004, 2023,
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-96 2022.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203. 15556, 2022.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy classification tasks. International Conference on Learning Representations, 2021.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. Advances in neural information processing systems, 33:15568-115 15578, 2020a.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler. and Franck Gabriel. Implicit regularization of random feature models. In International Conference on Machine Learning, pp. 4641-4640. PMLR, 2020b.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836 2020.
Tosio Kato. Perturbation theory for linear operators, volume 132. Springer Science Business Media, 2013.
Bryan T Kelly, Semyon Malamud, and Kangying Zhou. The virtue of complexity in return prediction. Technical report, National Bureau of Economic Research, 2022.
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. The Journal of Machine Learning Research, (11):6663-6877 2020.

---

Published as a conference paper at ICLR 2024
Frederic Koehler, Lijia Zhou, Danica J Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting. Advances in Neural Information Processing Systems, 34:20657-20668, 2021.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Representations (ICLR), 2018.
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Jachoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Tengyuan Liang and Alexander Rakhlin. Just interpolla: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-15
2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in weer-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward refined taxonomy of overfitting. NeurIPS, 2022.
Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:2210.1685. 2022.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications Pure and Applied Mathematics, 2019.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3 84, 2022.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1): 67-83, 2020.
Preetum Nakkiran and Yamini Bansal. Distributional generalization: new kind of generalization. arXiv preprint 20Xx:2000.00092... 2020.
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. In International Conference Learning Representations, ICLR, 2021.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In International Conference on Learning Representations, 2015.
12

---

Published as a conference paper at ICLR 2024
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference Learning Representations, 2020.
Pratik Patil and Jin-Hong Du Generalized equivalences between subsampling and ridge regularization. arXiv preprint arXiv:2305. 18496, 2023.
Ali Rahimi and Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), volume 3, pp. 5, 2007.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems (NeurIPS), Curran Associates, Inc., 2008.
pp. 1313-1320.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. In International Conference on Artificial Intelligence and Statistics, pp. 3889-3897. PMLR, 2021.
Daniel A. Roberts, Sho Yaida, and Boris Hanin. Frontmatter. Cambridge University Press, 2022.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in neural information processing systems, 30, 2017.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich- Keil, Jonathan Ragan Kellan,, Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. In International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 8614-8622 PMLR, 2020.
James B Simon, Madeline Dickens, Dhruva Karkada, and Michael R DeWeese. The eigenlearning framework: A conservation law perspective kernel ridge regression and wide neural networks. arXiv preprint 10.00221 2021.
Peter Sollich. Gaussian process regression with mismatched models. In Advances in Neural Information Processing Systems, pp. 519-526. MIT Press, 2001.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124000 2020.
Terence Tao. Topics in random matrix theory, volume 132.
American Mathematical Society, 2023.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. J. Mach. Learn. Res., 24:123-1, 2023.
Nikhil Vyas, Alexander Atanasov, Blake Bordelon, Depen Morwani, Sabarish Sainathan, and Cengiz Pehlevan. Feature-leariig networks are consistent across widths at realistic scales. arXiv preprint arXiv:230S.18411 2023.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning. Proceedings of Machine Learning Research, 2022.
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33:10112-10123, 2020.
Greg Yang and Edward Hu. Tensor programs iv: Feature learning in infinite-width neural networks. In International Conference on Machine Learning, pp. 11727-11737. PMLR, 2021.
Greg Yang, Edward J Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao. Tensor programs Tuning large neural networks via zero-shot hyperparameter transfer. arXiv preprint arXiv:2203.0344 2022.
Tian-Le Yang and Joe Suzuki. Dropout drops double descent. arXiv preprint arXiv:2305.16172 2023.
13

---

Published as a conference paper at ICLR 2024
Jacob A Zavatone- Veth and Cengiz Pehlevan. Learning curves for deep structured gaussian feature models, arXiv preprint arXiv:2303. 00564, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations (ICLR). OpenReview.net, 2017.
Lijia Zhou, James B Simon, Gal Vardi, and Nathan Srebro. An agnostic view on the cost of overfitting in (kernel) ridge regression. arXiv preprint arXiv:2306. 13185, 2023.
14

---

Published as a conference paper at ICLR 2024
A EXPERIMENTAL VALIDATION OF OUR EIGENFRAMEWOND FOR RF REGRESSION
We validate our RF eigenframework by comparing its predictions against two examples of random feature model:
Random Gaussian projections. We draw latent data vectors æ ~ NO, Im) from an isotropic Gaussian in a high dimensional ambient space (dimension m = 10
5 The target function is linear
as = v" x + &, where the target coefficients follow powerlaw v; = vi- 8 with 3 = 1.5, and & (0, is Gaussian label noise with o² = 0.5.
We construct random features (b))) W Here, W E R has elements drawn i.i.d. from (0, t). A d ... Am) is diagonal matrix of kernel eigenvalues, A; = i- with = 1.5. With this construction, the full-featured kernel matrix is (in expectation over the features)
Ew [ = x"AXX AX, with [X] = [x1 -.)]
Random ReLU features. CIFARIO input images are normalized global mean 0 and standard deviation 1. The labels are binarized (with y = 1) into two classes: things one can ride (airplane, automobile, horse, ship, truck) and things one ought not ride (bird, cat, deer, dog, frog). Thus the target function is scalar.
The features are given by (bx = ReLU where W E R has elements drawn i.i.d. from (O, ), with din 3072. With this construction, the limiting infinite-feature kernel is in fact the "NNGP kernel" of an infinite-width l-hidden-layer ReLU network (Neal 1996 Lee et al. 2018).
Theoretical predictions. The RF framework is omniscient risk estimate, have on hand the cigenvalues of the anliniteffeature kernel K and the eigencoefffcients of the target function w.r.t to K. For the synthetic data, we dictate the eigenstructure by construction: A; i 11. and 2 1.5 For random ReLU features, we use the neural tangents library (Novak et al. (2020) to compute the NNGP kernel matrix of CIFARIO, I0, and then diagonalize it to extract the eigenstructure. (We diagonalize an n 30000 subset of the kernel matrix since this is the largest matrix we can diagonalize on a single A A100 GPU without resorting to distributed eigensolvers.)
it, must
When evaluating our eigenframework, we numerically solve Equation 2 for and y. This can prove a slightly finicky process. We use an inner-loop outer-loop routine as follows. In the inner loop, is fixed, we solve for such that n E. X equal the discrepancy in the other equation. the outer loop, we optimize is to drive that error signal to zero.
A, + K. and we return the error signal k >; A,
x;+r y
Experimental details. We vary [10*, 10 k [10*, 104) 8 [10-3, 102). We perform 45 trials of each experimental run at a given (n, k, 6); however, in each trial we fix the size-n dataset as vary the random features.
Additional plots. We report additional comparisons between RF experiments and our theory in Figures and
Code availability. Code reproduce all experiments is available at htttp::/github..o akarkada/more is -iwpsreee---bettterreeeee
'In the main text, we purported draw the data anisotropically as (O0 A). For explanation here. introduce A at the random projection stage, which amounts to the same thing.
15

---

Published as a conference paper at ICLR 2024
Random ReLU features CIFAR10
Gaussian RF Gaussian data
expertmentt
ridge à
train (theory) test (thorry)
101
optimaa ridge
10
MSE
10
10P
10P
10
10
10
10
10
number of random features &
10
10a
10a
101 102
10
number of training samples
Figure 3: Empirical verification of the RF eigenframework. We plot various traces of train and test error, both experimental and theoretical as predicted by Equations (3) and 44. for two random feature models. (top row, same Figure I We fix the trainset size n 256 and vary the number of
features ht (bottom row) We fix the number of random features k = 256 and vary the training set
size n. Note that in this row, the classical underparametrized regime is to the right of the interpolation threshold, and the modern overparametrized regime to the left.
16

---

Published as a conference paper at ICLR 2024
2
8
8= 2
8= 2
10
10a
test mse (theory)
10a
m&se
101
10a
number of training samples
104
10
test mse (experiment)
10a
10a
10
-1P
train mse (theory)
10a
10a
10
10
train mse (experiment)
10a
10a
10a
10
10a
10
10"10"
10a
10
10º10'
10²
10a
10'10"
10
10a
10
number of random features
Figure 4: For RF regression with synthetic data, we show heatmaps of average train and test MSE as function of training set size and number of random features k. We vary the ridge parameter 6 from underregularized (left column) to overregularized (right column). the underregularized setting, the signature double descent peak (bright diagonal) separates the classical regime (upper triangle) from the modern interpolating regime (lower triangle). In the overregularized setting, the model fails to interpolate the training data even at low Our theory accurately captures these phenomena. Note: at each the same batch of random datasets for all k, resulting in horizontal stripes visible low n that may be ignored as artifacts.
17

---

Published as a conference paper at ICLR 2024
B TECHNIQUES FOR MEASURING POWERLAW EXPONENTS IN KRR TASKS
Our analysis of overfitting in kernel regression relies on an assumption of "powerlaw eigenstructure" (Definition 2) characterized by two exponents a, 3. Here describe procedures for measuring a, 3 for real datasets.
Extracting a from the effective regularization x(n).
The KRR eigenframework on which our results are based entails the computation of an intermediate quantity which serves as an "effective regularization constant" (Simon et al., 2021 Bordelon et al. 2020 Jacot et al., 20200a Wei et al. (022). This quantity decreases as more data added: writing as a function of n, one usually finds decay as r((n) x An 0 In our case, if indeed we have X oc i i for large i, then we expect that k(n) x i-9
Fortunately, Wei et al. (2022) describe method by which x(n) may be experimentally measured. Under a reasonable Gaussian universality assumption, they find that k(n) x Tr(K,
where K an empirical kernel matrix computed from n samples. When we plot points (n, Tr Tr(K,""]- on a log-log plot for many values of n for the four datasets we study, we indeed see a clear linear tail indicative of powerlaw decay of s(n) and whose slope á we can easily extract after performing linear fit. We show these linear fits in Figure 5
Extracting / from the test error (
As discussed in the main text, we generally expect true risk at zero ridge and zero noise decay proportionally to the uncaptured signal (SFie(n) (n) x Ei>n of = n (0-1). For the four datasets we study, we indeed see linear decay when we plot points (n, (n)) We fit line and extract 3 as the slope. We show these plots and linear fits in Figure 5
log-log plot.
Intuitions about powerlaw eigenstructure. Having measured powerlaw structure in several image datasets, now give some informal discussion of how this structure might be interpreted. Informally, powerlaw eigenstructure describes the structure of natural data in two ways:
The eigenvalues of the kernel roughly decay as a powerlaw: X; i-a (Equivalently, the spectrum of the covariance matrix of the data distribution in the kernel's feature space decay as a powerlaw.) Since X; represents a kernel's 's "willingness" to learn eigenmode i, we may interpret representing the kernel's parsimony: in modeling the data, kernel with large a tends to overattribute explanatory power to its top n eigenmodes, confidently neglecting its tail eigenmodes.
The target function, expressed vector in the kernel's eigenbasis. has components whose squares roughly decay as a powerlaw: uf i i Since larger 3 implies a greater proportion of total task power in the top eigenmodes, we may interpret ,3 representing the target function's 's comprehensibility (to the kernel learner): targets with large 3 are easier to learn.
These informal interpretations suggest that kernel is well-suited to learn task if a is sufficiently small compared to J. Otherwise, the kernel is simply too parochial to learn the intricacies of the target function; such a kernel will generalize poorly in the absence of regularization. This intuition is made precise in Corollary
Remark. Powerlaw eigenstructure is a remarkable constraint. There is no clear reason why arbitrary data distributions and target functions should have this structure, and yet observe that natural data do. This fact is both a miracle and a blessing for theorists, as strongly restricts the class of data distributions we need concern ourselves with to explain the behavior of deep neural networks. It remains major open question to fully explain and characterize the powerlaw structure of natural data with respect to neural kernels.
'Mallinar et al. 2022 find that s(n) in fact be off of A,. by log factors for certain exotic "benign overhiting" spectra, but this beyond our scope here.
18

---

Published as a conference paper at ICLR 2024
CIFAR10
SVHN
FMNIST
MNIST
10a
1.17
á à= 1.22
à= 1.17
1
10.
10
10
109
10P
107
10"
10P
10" training samples n
10
10P
10a
10P
102
107
empirical eigvals X;
10a2
105
10a
1-117
LIT
L12
10a1
10a
102
10'
10"
10
10*
10
10a
10*
10a
102
10*
mode index
best MSE (3-1)
-= 1.14
3 1.20
Ô= 1.18
1.36
1041
102
10'
10F
10" training samples n
10a
empirical eigcoeffs* 6/
10:2
10-5
2-1.14
10a
102
10
109
10
109
10
102
10
mode index
Figure 5: For the four vision tasks studied (columns), show techniques for measuring (first row) and (third row). the powerlaw decay the tails (solid line) and report the corresponding exponent measurements (text). These plots are generated by studying increasingly large x training- data kernel matrices. For visual comparison, we include the empirical eigenstructure (eigenvalues and squared eigencoefficients of the full training-dar -atin kernel matrix, second and fourth rows respectively), along with a powerlaw decay with our measured exponent (solid line). Note that linear fits to the empirical eigenstructure (rows two and four) would be worse than to our proxy measurements (rows one and three).
19

---

Published as a conference paper at ICLR 2024
C COMPARISON: PROXY MEASUREMENTS OF a, 3 RECOVER TRUE EXPONENTS MORE ACCURATELY THAN MORE DIRECT MEASUREMENTS
Our theory for overfitting relies on the ansatz of powerlaw task eigenstructure that, at large i, task eigenvalues and eigencoefficients decay as A; x i- and vi x 8-8. Prior works, including Spigler et al. 22020); Lee et al. (2020) [Bahri et al. (202T). extracted the exponents a, 3 from direct measurements of X and of for full datasets. However, as detailed in Appendix B, we instead extract a, 3 more indirectly from the proxy quantities λ and Eg. The purpose of this appendix is to explain flaw in the direct method and thereby motivate this proxy method.
We begin by describing the direct method. First, one computes an empirical kernel matrix K,, on a dataset of size n. Since K,, is real symmetric, we may numerically diagonalize it as K,, - & A Tr_ nIn, and A = diag(Aı..... A..) is a diagonal matrix of n estimated eigenvalues. One then projects the labels onto the kernel eigenvectors to find the target eigencoefficient vector =
where "
n Th y. Finally, one plots the computed eigenvalues and target eigencoefficients (or a tailsum thereof) on log-log plot and performs linear fits, extracting powerlaw exponents from the slopes.
The essential problem with the direct method is fiiite-sample-sizee effects resulting from the finiteness of n. For example, the extracted eigenvalues (A+) may be viewed as an estimation of the first ground-truth eigenvalues (X,) but one generally expects this estimation to be accurate only for indices < n. In practice, we find it often unclear for what range of indices we may say that "i < n²" and that we may therefore trust our estimated eigenvalues. This is not trivial problem: we find that the error and ambiguity thereby induced can be quite large!
Synthetic powerlaw data, (a, = (1.1, 1.3)
10
A
0.90
101
R
1.13
B 1.37
D
1.30
digewaahee
10-
100
eigoowt Boowfrnllsm trlsum
10p
Mww and
201
10
empirical A,
empirical
E10
true.. A,
104
trac x]
10
10a
16
10P
100
10P
10
10
10P
mode index
train somples n
mode Index
tevin sumples
Figure 6: Proxy methods for estimating a, B have lower error than direct powerlaw fits to task eigenstructure. We generate n 2000 samples of synthetic Gaussian data with ground- truth powerlaw eigenstructure A; = i i-1.1 of = i-3 and compare direct and proxy methods of estimating these exponents. (A,C) We diagonalize the empirical kernel, extracting estimated
eigenvalues (A)== and eigencoefficients (0.)== We plot the empirical eigenvalues and the tailsum of the empirical eigencoefficients. We observe that these do not clearly lie on a line on a log-log plot red flag but nonetheless depict reasonable attempts (gray lines) to fit lines. (For the eigenvalues, we do not use the first ~ 20 cigenvalues in our linear fit, since in practice the top eigenvalues usually do not obey the powerlaw in the tail and must be discarded.) The estimated exponents (á, 3) (0.90, 1.37) thus obtained have fairly high error from the ground-truth values. For visual comparison, we underlay the ground -round-truth eigenvalues and eigencoefficient tailsums (blue dots in both plots). (B,D) We estimate a, / from proxy measurements as described in Appendix B The resulting estimates (å, 3) = (1.13, 1.30) are much closer to the ground-truth values. The error in a is primarily due to the technical detail that our synthetic powerlaw data has a finite maximum index fmax = 3 x 10 for computational feasibility, whereas the theory on which this estimate is based assumes mma DC.
This is best illustrated with an example. To compare the accuracy of direct and proxy methods for exponent measurement, we construct synthetic task with Gaussian data with powerlaw eigenstructure with a = 1.1 and 3 = 1.3 and try out both methods for recovering these exponents. The results are illustrated in Figure 6 For eigenvalues, we find that only the first few eigenvalues are recovered accurately, and attempted fits to the middle or tail of the spectrum yield large measurement errors. This is important because, in practice, the first few eigenvalues typically do not follow the powerlaw of the tail, leaving the experimenter with few or no clean power eigenvalues to which to fit line. However, our proxy measurement recovers decent approximation to the true a. For eigencoefficients, since individual eigencofficients generally look noisy and require smoothing
a powerlaw,
20

---

Published as a conference paper at ICLR 2024
follow Spigler et al. 2020) and plot the tailsum Σح>ر 0j as function of i, which is expected to decay as i -0-01), the same exponent as that test error. Here, too, we observe significant finite-size effects and are unable to observe the ground-truth -ruth powerlaw, but recover the true 5 with excellent accuracy from plot of error vs. sample size.
21

---

Published as a conference paper at ICLR 2024
D EXPERIMENTAL VALIDATION OF THEORY FOR POWERLAW TASKS
We compute neural tangent kernel matrices for the Myrtle- 10) convolutional architecture on four stan- dard computer vision datasets: CIFAR-10, Street View House Numbers, FashionMNIST, and MNIST. For each, we perform kernel regression varying the ridge and added label noise. We additionally measure the eigenstructure exponents and / using the techniques described in Appendix B We use these measurements predict the train and test error of these kernel learners and find excellent match with experiment (Figure 7
Experimental details. We the neural tangents library (Novak (2220) to compute the convolutional NTK matrices (CNTKs). takes about four A100 GPU-days to compute each CNTK. We normalize each dataset have global mean 0 and standard deviation 1. We do not binarize the labels: the learning task one-hot 10-class regression. For experiments with label noise, the added noise is Gaussian vector whose norm has total variance x² = oet EEe = (see After adding noise, we normalize all label vectors to have unit norm so that all curves in Figure intersect at (Rir/te E = 1).
Equation 7.
In Figure 2 and Figure 7, each theory curve is vertically shifted by a constant multiplicative prefactor which is chosen such that the theory curve agrees with the experimental data at Ru/le = 0. This post-hoc fit is required because the derivation of Lemma I0 assumes the cigencoefficients follow powerlaw with prefactor unity (i.e., ii Ai-9 with
), while the true eigencoefficients will be scaled, i.e. ui Ai- 8 for some + which may not be easy measure. For this reason, we choose to simply fit the prefactor. When looking at Figure 2 then, we get theory-experiment match at Ruyle- for free, and the interesting fact is that also have agreement for Ru/le (0,
Code availability. Code to reproduce all experiments is available at https://github. com/ akarkada maoodddammor-eeeeeee isttorreees-eeteerr
22

---

Published as a conference paper at ICLR 2024
CIFAR10 (a, 5) Ri (1.17, 1.14)
SVHN (a, se (1.22, 1.20)
FMNIST
MNIST (a,5) x (1.12) 1.36)
(a, 8) P3 (1.17, 1.18)
10"
test test MSE
fally Interpoo
added
0.0
1.0
0.5
1.0
0.0
1.0
0.5
1.0
Rey/te
109
MSE
theory
test moe (expt)
(expt)
10
10
10a
10a
10
103
109
10a
10
10
109
102
10
10a
109
10a
ridge
100
test test MSE
Reslie lines
10-1
Rizu
Righ 10
10a
10a
10
10a
10a1
10"
10a
10a
10P
10a
10"
train MSE
Figure 7: Top row. We extend the experiment shown in Figure 2 to the FashionMNIST dataset. Theoretical predictions using measured exponents accurately capture the obligatory overfitting phenomenon. Middle row. We plot experimental test and train error function of ridge. Bottom row. We plot experimental test error function of train error. Contours of constant Ru/ie parallel diagonals.
23

---

Published as a conference paper at ICLR 2024
E DERIVATION OF THE RF EIGENFRAMEWORK
In this appendix, we give a derivation of the eigenframework giving the train and test risk of RF regression which we report in Section 4 Our plan of attack is as follows. First we will recall from the literature the comparable eigentramework for KRR, expressing in a manner convenient for our task. We will then explicitly write RF regression as an instance of KRR with a stochastic kernel. This framing will make it clear that, if we could understand certain statisties of the (stochastic) eigenstructure of the RF regression kernel, we could directly plug them into the KRR eigenframework. We will then use single asymptotic random matrix theory identity to compute the various desired statistics. Inserting them into the KRR eigenframework, we will arrive at our RF eigenframework.
Our derivation will be nonrigorous in that we will gloss over technical conditions for the applicability of the KRR eigenframework for the sake of simplicity. Nonetheless, we will have strong evidence that our final answer is correct by its recovery of known results in various limits of interest (Appendix and by its strong agreement with real data (Figure 1.
E. RECALLING THE KRR EIGENFRAMEWORK,
We now state the omniscient risk estimate for KRR (or equivalently linear ridge regression) under Gaussian design which has been converged upon by many authors in recent years (Sollich 2001
Bordelon et al. 2020 Jacot et al. 2020a Simon et al. 2021; Loureiro et al., 202 Dobriban &
Wager 2018 Wu & Xu 2020; Hastie et al. 2022 Richards et al. 2021). We phrase the framework
in slightly different way than in Appendix 1.1 which will be more suitable to our current agenda.
As in the main text, let the Mereer decomposition of the kernel K be K(z,x') E (z)),, where { are complete basis of eigenfunctions which are orthonormal with respect to the data measure Pzz- We still assume our Gaussian universality ansatz (Assumption A over the eigenfunctions {p.
We will find it useful to pack the eigenvalues into the (infinite) matrix A = diag A1, Az....), .), the target cigencoefficients into the (infinite) vector v = (V1, u2....), and the set of eigenfunctions evaluated on any given data point into the (infinite) vector Φ(x) ( Using this
notation, the kernel function is given by
K K(x, x', =(x))
(13)
The KRR eigenframework appearing in these prior works is as follows First, let K 2 be the unique nonnegative solution to the equation K
n
Tr A +
(14)
RT
Then test and train MSE are well-approximated by
Ele
π
v v+o2]
(15)
A + ART
Tr
A
A+RI
82
Er n² R2
Exe.
(16)
The "z" in 15 can be given several meanings. Firstly, it becomes an equivalence in an asymptotic limit in which and the number of eigenmodes in a given eigenvalue range (or the number of duplicate copies of any given eignemode) both grow large proportionally (Hastie et al. 2022] Bach 2023). This is often phrased as sampling a proportional number of new eigenmodes from fixed measure. Secondly, with fixed task eigenstructure, the error incurred can be bounded by a decaying function of (Cheng & Montanari 2022). Thirdly, numerical experiments find small error even at quite modest n (Canatar et al. 2021 Simon et al. 202I). For the purposes of this derivation, we will simply treat it as an equivalence.
7 'll the prior works cited at the start the subsection find the same cigenframework. As of the time of writing, Cheng & Montanari (2022) give probably the most rigorous and general derivation for this eigenframework and could be taken as the canonical source if one is required. *For two commuting matrices A, B, we will sometimes abuse notation slightly to write A
place of
B
AB B-' A.
24

---

Published as a conference paper at ICLR 2024
E.2 REFRAMING RF REGRESSION KRR WITH STOCHASTIC EIGENSTRUCTURE.
We now turn to RF regression. Recall from the main text that RF regression is equivalent to KRR with the random feature kernel
1 k E g(w, x)g(;;,,))))
R (2x x')
(17)
with sampled i.idd from some measure Recall also that there exists a spectral decomposition
g(w 2)
(18)
where ( and (=)) are sets of eigenfunctions which are orthonormal over Pz and pas respec- decreasing sequence of nonnegative scalars. Note that the limiting kernel probability, from which we see that we are indeed justified in reusing notation (Ae, oi) from the previous subsection.
tively, and (Ai) as - oo is lim K' (2r, x') = K (x, = E,
Note that write this kernel as
k(xxx)) k
(19)
1,1'=1
ZZT k
()))²
1/2 (xx'),
(20)
where we define the projection matrix (Z) رJ (ww,), Comparing with Equation 13 and examining
our KRR eigenframework, we see that, under Assumption we can predict the risk of RF regression as follows.
First, define
Ä = 1/2 ZZT
1/2
(21)
k
Then, let A be the unique nonnegative solution to the equation
8
n
Tr
+
(22)
+
kl
Then test and train MSE will be apro-aapro by
vT
kl
v+02
(23)
2
+ RT
n
Tr
A+ral
82
&
Exe.
(24)
ni R
We refer to this boxed set of equations the partially-evaluated RF eigenframework because they are written in terms of the random projection Z, which we still have to deal with.
E.3 BUILDING UP SOME USEFUL STATISTICS OF Á
The problem with the eartially-evaluated RF eigenframework is of course that do not know the stochastic eigenstructure matrix Á. To make progress, again turn to Gaussian universality ansatz (Assumption A}. Under this assumption, we may replace the columns of with i.i.d. isotropic Gaussian vectors, which amounts replacing the whole of Z with i.i.d. samples from (0, 1).
We now leverage a basic random matrix theory fact for such Gaussian matrices leveraged in many recent analyses of ridge regression with random design (Jacot al. 2020a Simon et al. 202 Bach
25

---

Published as a conference paper at ICLR 2024
2023 First, let y 2 0 be the unique nonnegative solution to kw
=
Σ
(25)
+
The final term is Inc instead of simply & as might be expected from the form of this fact in other 7
works because of the factor of & in Equation 21 we have that
Then, under the Gaussian design assumption on Z,
A
Ez À
(26)
+ RI
A+
This equation is useful because reduces statistic of the stochastic eigenstructure matrix Á into function of the known eigenvalue matrix A.
The meaning of "*"""" The ">"" in Equation 26 can be given various technical interpretations.
generally becomes an equivalence the proportional limit described in the following sense: consider fixing integer y > 1 and increasing ymn, -> np, and also duplicating each eigenmode times. As 17 - oc, we reach the proportional limit. For the purposes of this derivation, we will simply treat it as equivalence.
We now bootstrap this relation to obtain four more relations. We state these relations and then justify them.
KI
I
Ez
(27)
A
+
RI
+
+
Á
A
KA
Ez
0x7,
(28)
+ +1
(A
KA
15z
0x7
(29)
A + s
2
(A + 7
I
KA
Ez
(A + 71+ 0x7
(30)
A + kl
A + 1
Taking derivative of Equation 25 and performing some algebra, we have that
8x7
(31)
2
h: - Σi
We obtain Equation 27 by simply subtracting both sides of Equation 26 from the identity matrix
We obtain Equation 29 by taking a derivative of Equation Squation[26]war with respect to K. We obtain Equation 30
by taking derivative of Equation 27 with respect to Finally, we obtain Equation 28 from the
identity
2 K.
A+xl
(A+AT)=
E.4 INSERTING IDENTITIES INTO THE EVALUALE RF EIGENFRAMEWORK.
We are in a position to insert Equations 26 30 into the partially-evaluate RF eigenframework to get closed-form results. We will generally trust that scalar quantities concentrate that is, for some matrix M and vector z of interest, we will have that TrMM] ~ [r[ and z Mz ~ Eiz Mz). with small enough error that we can neglect it.
We start with Equation 22 defining k. Inserting Equation 26 into the trace, it becomes
71
(32)
Inserting Equations
28 and into Equation
30
23
we get that
E
72
Σ de Ny
(Ni Ad: (1
Omn
) )op +
(33)
E,
>
kd
d
26

---

Published as a conference paper at ICLR 2024
Inserting Equation 31 for O,y and simplifying with the definitions
Σ,
and q
X,77
E: Artt and the fact that (k 2) as per Equation 25 we arrive at the RF eigenframework
we report in the main text.
Remark implicit constants. The KRR eigenframework started with had only one implicit constant и, which could be understood two ways. First, it is given by the inverse of the trace of the inverse of the empirical kernel matrix: k R ir(Kxx Wei et al. (2022). Second, acts as an eigenvalue threshold: modes with X; >> K are learned, and modes with X; < K are not. In the RF eigenframework, we have two implicit constants, x: and y. This new x still serves the first role:
Tr
However, it is now 7 that acts as the learnability threshold for eigenvalues.
XX
E.5 ADDITIONAL ESTIMATES: BIAS, VARIANCE, AND MEAN PREDICTOR
Test mean squared error is canonically split into bias term (equal to the error of the "average" predictor) and a variance term (equal to the rest of the error). In the case of RF regression, a subtle question is: the average with respect what? We could consider an average with respect only random datasets, only random feature sets, or both at the same time. Jacot et al. (2020b) take a features-only average. Here will take the other two.
In the main text, we denote the random dataset by X. Let us also denote the random RF weights as W. We then denote the data-averaged bias and variance to be
BIASJ == -Ew
E EENNE
[Bx[f(x)] - f((x)) +
(34)
VARa := -EE, [Ranepp [J(z)) - -xx[[()))
(35)
Similarly, we let the data-and aeddfffuur--veeraaee bias and variance be
BIASar ExNu=
[Bw,x(f(x)] fx)))) +o²
(36)
VAR Ew,x
Egen, (f(x) -w.x((()))
(37)
Fortunately, the KRR eigenframework gives us an equation for the data-averaged bias and variance: the data-averaged bias is the term in big parentheses in Equation [5] while the variance is the rest (see Simon et al. (2021)). This tells us that the averaged bias and variance are the following:
BIASJ 2 By = Σ
?
Ed;
of +
(38)
A A1t
(Ar + 7) 9)
VAR R: Va == & BIASH-
(39)
The more interesting case is perhaps the data-and-featurr-avv ( case is simply [x((()) AtRT
bias and variance. Jacot et al.
(2020a): Canatar et al. ) Simon et al. (2021) found that the data-averaged predictor in the KRR
A
(xx), so in our case it will be
Á
Ex[f(r) = T
((x).
(40)
À kl
Taking the feature average, we conclude that
Ew,x(/ Ew T Ä
A
((x)
= T A
((x).
(41)
A+k
That is, [x[s(x)] ~ Σ, 2 (.0) We thus conclude that the date-and-fentur--vvrraed bias and variance are given as follows:
BIAS R Bar := Σ A
2 +02
(42)
+
VAR R Var := Es BIAS
(43)
27

---

Published as a conference paper at ICLR 2024
E.6 EVEN AT FIXED RIDGE, MORE IS BETTER FOR BIAS TERMS
Increasing n and & (and keeping ó constant) strictly decreases both data-averaged and data-and- eeauure-veerage bias. To see this, we fist note the following proposition, which follows from Equation
Proposition (Derivatives of implicit constants). Let D == kNō + (= - (kmn + +76) > Then we have that
7.7 7(7 w)d
(44)
D
1²(7 k))Zz 9)
0₂K
(45)
D
kyn2
0,7 D
(46)
0₂K x² (Kr + (2 - 9)7)
(47)
D
In particular, note that when we increase n, we decrease both constants When we increase we decrease y but increase K.
is immediate from Equations 38 and 422 that increasing & decreases both BIASar and BIAS It is immediate also that increasing n decreases BIASar. but since increasing decreases K, it is not apparent that B BIASa also decreases. However, we not need to show this: is apparent from Equation 68 that the bias of KRR is sample-wise monotonic in this sense for any task eigenstructure, and RF regression (being simply a special case of KRR with stochastic task eigenstructure) will simply inherit this property. All together, we see that increasing either n or k will decrease both k for
BTAS, and BT Any region of increasing error encounters when increasing example, at double-descent peak - can thus be pinned on (one or another notion of) the variance.
F TAKING LIMITS OF THE RF EIGENFRAMEWORK
In Section we report an omniscient risk estimator giving the expected test risk of RF regression in terms of task eigenstructure. Here we demonstrate that, by taking certain limits, we can recover several preiiuusl-repooree results from our general framework. For easier reference, we repeat Equations 2 here:
A
(48)
A
ke
k = Σ
+
(49)
d
+
Y
F.1 THE LIMIT OF LARGE k: RECOVERING THE KRR EIGENFRAMEWORS
RF regression converges to ordinary KRR in the limit of large k and so we expect to recover the known KRR eigenframework. As k co, find that 7 1. Therefore and find that simply satisfies = E, A. 7,tm
discard Equation 49)
as we get in the case of KRR.
Equation reduces to
&E
Σ
0 + o2
(50)
q
Ai +
which is precisely the omniscient risk estimator for KRR (compare with e.g. Simon et al. (2021)
For this informal discussion, will be a little fast and loose with terminology: when 5 - 0+, will find that these partial derivatives may be instead of strictly negative, and when say e.g. that derived quantity increases with k zero ridge really mean that it increases remains the same.
28

---

Published as a conference paper at ICLR 2024
F.2 THE LIMIT OF ZERO RIDGE: RECOVERING THE RIDGELESS FRAMEWORK OF BACH (023
Bach 2023) report an omniscient risk estimator for ridgeless RF regression. We should recover this result from our framework when we take 6 0+ (Note that we cannot simply set 8 0 as
Equations (48) and (49) do not always have solutions, but we will have no trouble taking the limit 5 + 0+ Like Bach (2023). we will handle this in two cases.
Case 1: n k. When k, we will still have > even as + - Observe that y is determined
by the constraint that
Ei
A X
Plugging into Equation 48 gives that
KK 7
n + k
(51)
k: n
(52)
k
Sticking in these substitutions into Equation and simplifying substantially, we find that
E = 71
n- Σ
+ k
n
Σ \
0 +02
(53)
+7
which matches the result Bach (2023).
Case 2: > k. When > k, the constraint that & = E. Actty Equation we find that
we have that x > 0 as d + 0+. Therefore ? is determined by Inserting these facts into
A
We also have that = 2 = E. Aity"
Ec
Σ A +
2 +02
Σ
2 U \i
7
+ 0²
(54)
kg
This also matches the result of Bach (003)).
Remark. We can observe the following proposition from the above 0+ liimt of the RF eigenframework:
Proposition (Monotonic improvement after the double-descent peak). With 8 0+, we have that
8% < 0 when k > %
85 <0 when n > k.
Proof. First, let us take k > n. From our discussion of "Case 1," we see that further increasing A: will leave y unchanged, which leaves q unchanged. The only effect is thus to decrease the prefactor k-n of the second term of Equation 53 which decreases E
Now 1et us take k. From our discussion of "Case 2," see that further increasing n leaves unchanged. It is similarly immediate from Equation [54 that the result is to decrease &
Proposition 2 states that, at zero, ridge, increasing the larger of k further can only improve test performance. Phrased another way, it's s all downhill after the double-descent peak. Though this fact is elementary, we do not know of any existing proof in the literature.
F.3 ET AL.. 2022)
STUDENT EQUALS TEACHER: RECOVERING THE RF RISK ESTIMATOR OF MALONEY
Maloney et al. (002) work out risk estimator for ridgeless RF regression under the "student equals teacher" condition that X; of and o² 8 0. Inserting these into Equations 53) and (54) and exploiting the fact that z = min(n, k) when 8 = 0 to simplify the resulting expressions, we find that
7 for k, for k.
(55)
Again using the fact that min(n, k), these can be further unified (using the notation of Maloney et al. (2022) as
J A for n < k. for n >
E
(56)
where A > is the unique nonnegative solution to 1 E: the main result of Maloney al. 2002
A mA++
with min(n, (n,k) k). This is
29

---

Published as a conference paper at ICLR 2024
F.4 HIGH-DIMENSIONAL ISOTROPIC ASYMPTOTICS: THE SETTING OF MEI & MONTANARI (2019)
Here compute the predictions of our framework in the setting of Mei & Montanari 2019), who study RF regression with isotropic covariates on the high-dimensional hypersphere. The essential feature of their setting is that task eigenvalues group into degenerate sets: we first have one eigenvalue of size (1), then d eigenvalues of size (d then ((d) eigenvalues of size (d)²), and so on. We take doo with n/d + rn/d; k/d + Tk/a with Tafd, Tk/d = ((1). In this setting, we expect to perfectly learn the Oth-order modes, partially learn the Ist-order modes, and completely fail to learn the higher-order modes.
Let Ie denote the set of eigenvalue indices corresponding to degenerate level é 2 0. Let p LiET, A, be the total kernel power in level and u2z to denote Emze pe. Let Pt = EiET "f be the total target power in level l and P>e to denote Emzt Pr. Let us write Ag= A1, etc. to denote the value of the degenerate eigenvalue at level L.
In this setting, we will find that 7, (dd=l). Equation 2
simplify in this setting to
> Ai
+ P22 de
k
X
Ks
and
(57)
d
Ai
Nit9
dy
Here the z hides 0(1) terms that asymptotically vanish. These equations can be solved analytically numerically for 7, K. Note that if one wishes to work in the large-d limit, one might prefer to solve for y := dr and R == dx as follows:
111 8+
M22
Tw/d
111 + 7
R
and
Tk/d R
111
+ Tk/d- +
7
(58)
The advantage of the above equations is that all quantities are O(1) after one replaces n/d, k/d with the appropriate (1) ratios.
2 = d One then has z dx dxtt d Mits and q = d (x)t))
2 Let = =2/d = O(1) and
mits
q= q/d (l). Equation 3
then reduces to
Eee 83
701 27 Ta/a 9)
M1 +
(y + 5)2 1
-
1
p1 +
P22 P22 + d2
(59)
We expect this is equivalent to the risk estimate of Mei & Montanari (2019 's Definition 1, as they solve the same problem, but we have not directly confirmed equivalence.
F.5 HIGH-DIMENSIONAL ISOTROPIC ASYMPTOTICS: THE SETTING OF MEI ET AL. (0022
In followup work to Mei & Montanari (2019) in the linear regime, Mei et al.
2022) study RF
regression in the same hyperspherical setting, but in a polynomial regime which do k de with a, b > 0, a + b, and a, b & 10
In this regime, working through our equations, find the following. First, let [min(a, b) When a b and thus >> k, find that 7 R uioe and R R 8 > n, we find that y zv #5et5 and x Rs 7. In either case, we find that 2, 9 & min(k: n). and so the prefactor in Equation becomes equal to 1, with the whole estimate simplifying to
n < 7. When < b and thus
E P>c + 0
(60)
That is, all signal of order & < c is perfectly captured and all signal of order é is fully missed (but not overfit), with e set by the minimum of and k. This is precisely the conclusion of et al. (2022).
F.6 SANITY CHECK: THE LIMIT OF INFINITE RIDGE
It is casily verified that, as R oo, we find that K, y co, and 2, > 0 and thus Enc- = E, +o2
as expected.
Technically they abstract the hyperspherical setting to generic setting with suitably gapped eigenspectrum. but the essential features the same.
30

---

Published as a conference paper at ICLR 2024
F.7 INTERESTING CASE: THE LIMIT OF LARGE
Here we report an additional limit which, to our knowledge, has not appeared in the literature. When + oo with & finite, we have that > and thus / k. The risk estimator then reduces to
E = Σ -
7 o +
(61)
This resembles the bias term of the KRR risk estimator with is samples, with the sole difference being the replacement
2
G PROOF OF THEOREM
Proof. First consider increasing - n'. Examining Equations 2 we see that we may always increase 5 such that R and y remain unchanged and still satisfy both equations, and thus 2 and q are also unchanged. Turning to Equation 3 we see that increasing n + n' while keeping K, ", k, 2, q fixed can only decrease Eg,, as this only serves to decrease the (always positive) prefactor.
Next consider increasing + k.. From Equations 2 we see that it is always possible to increase 5 so that y remains unchanged (and 2, remain unchanged) and increases. Increasing & decreases the prefactor in Equation 3 because d g(kk=2))+=² dic n(k-q) = (x-g)² (k-q)² S 0, and increasing is and k. manifestly decreases the term in square brackets, and so overall & decreases.
To show that this inequality is strict in both cases, all we require is that q >> which only requires that the optimal 8 is not positive infinity. To show this, we first observe that as - oc, then K, y grow proportionally. with a nn 1. is then easy expand Equation in terms of large 8, using the facts that = -- Σx d + 0(x 2) and q 7² Σ; XP + +()-3)) Inserting these expansions,
we find that
Ege = (1 | 2 Σ X + +0 ))
Σ [ ut 00 -2 -
Σ Nuy + +0(7
(62)
lim E 6
2g Σ Aief + -2
(63)
From the negative y- term in this expansion, it is clear that the optimal y is finite so long as >; dzof > 0, and thus the inequality in the theorem is strict.
H NOISE SCALING AND COMPARISON WITH BENIGN OVERFITTING
Here we give further justification of our decision to scale the noise down with n as 0² o Eulor=s-n which amounts to o² x n (3-1), This turns out to be a subtle but very important point which differentiates (Bartlett et al.) 2020; Tsigler& Bartleti] 2023). These other works take a fixed, positive noise level after all, there appears priori to be no reason why the noise and has long been the standard setup in the statistics literature. One essential
approach and conclusions from those of the benign overfitting" literature
x² -==011 (1). This is well-motivated should change with consequence of this setup - which we argue here is in fact somewhat misleading - is that, once n grows large, the noise inevitably dominates the signal. Concretely, one can decompose the portion of test risk coming from the (deterministic) signal and that coming from the noise, and so long as the signal lies in the RKHS of the model and the ridge is not very large, at large n the contribution to test error due to the noise dominates that coming from the signal.
We can see this clearly from the omniscient risk estimate for KRR which we use in the text. Examining Equation 65- Equation 68| it is easily seen that as n grows, the implicit regularization will decay to zero so long as 8 = o(n) (for example, if it is constant). So long as the overfitting coefficient En does not explode as n grows (and it usually does not, and will never if d (1)). the contribution to & from the signal {4:} } will decay to zero because (1 - C,) = A=+ + 0. However, the contribution
from the noise will still remain Ego² O(1). Our foremost consideration in this case becomes guaranteeing that & + 1. The esoteric eigenvalue decay X; 8 log -" with y > 1 found by Bartlett et al. (2020) achieves this, as shown by Mallinar et al. (202)).
Once we reach this "noise-dominating" regime, our task was irrelevant: to leading order, we might as well assume it is pure noise. This simplifies the question of overfitting dramatically and, we argue,
31

---

Published as a conference paper at ICLR 2024
too much. Indeed, when training and testing on pure noise, the best one can hope to do is to fit as little as possible, because the Bayes-optimal predictor is uniformly zero. The optimal ridge is thus large, and zero ridge is suboptimal: the best we can hope for is that the suboptimality of zero ridge costs us only an o,, (1, penalty in test error. That is, at best, interpolation is permissible (or "benign"), )); it is never preferable. This is emphatically not the regime we actually see in deep learning: one often finds that training to interpolation is often indeed strictly beneficial (practitioners wouldn't train for so many extra iterations if they weren't I strictly helping!), and indeed Nakkiran & Bansal (2020);
Mallinar et al. (2022) simply run experiments in which neural networks are fit to interpolation on data with controlled noise levels and find that interpolation is not benign but rather incurs a finite cost in test error. This suggests that we should seek theoretical settings where interpolation is beneficial on tasks that resemble real data but harmful on pure noise, which is our contribution in Section S
As discussed above, the essential problem here is that finite noise inevitably grows to dominate uncaptured signal. The solution to scale down noise proportional to the uncaptured signal as we do in Section [5] This puts both sources of error on an equal footing and enables us to make a nontrivial comparison between the two. As we show in Section [5] we do in fact need to consider the details of the target function to understand overfitting in modern machine learning (or at least KRR on image datasets), and choosing a scaling that does not wash out all signal is crucial. analyses like those performed by (Bartlett et al. 2020 Tsigler & Bartlett Mallinar et al. 2022 Zhou et al., 2023) cannot resolve target-dependent effects.
2023
may seem aesthetically repugnant to have a² scale in any way with n. The noise level surely fixed quantity; how can it change with the number of samples? In reality, this is simply a way of viewing whatever noise level we see in an experiment. As we increase n, we will indeed find that ofd indeed increases (because the noise remains the same, but the uncaptured signal decays), but because we will never have infinite n. in practice, we will always observe a finite (or zero) value of o At finite n, this o may be large small compared with the uncaptured signal. Our scaling boils down to choice to treat of as an order-unity quantity that one must consider carefully. The naive scaling with o² (1) amounts to a choice to treat o as infinite and dominating in the large-n regime in which one proves theorems.
Since we are developing theory we wish to describe a set of real experiments, the choice of which scaling is preferable ought thus to be put to the empirical test. In experiments, we find that of is indeed small for the datasets we examine, which we view as affirming our choice to do theory in a regime in which the noise is not necessarily dominant.
Put another way, because we will always observe a finite oi in practice, we take limit that resembles this situation, with signal and noise of the same order, but enables one to prove theorems as one can at large n. Figure 2 Jattests that the real experiments are well-described by our limit, and would be poorly-described by a limit which takes oial + CO.
We note that this business of how to scale quantities so effects of interest do not vanish is loosely similar to how the "neural tangent kernel" limit (Jacot et al. 2018) steadily loses feature learning as width grows, while the "u-parameterization" line of work (Yang& & Hu 2021 changes the layerwise scalings so feature change is no longer washed out by feature initialization. Yang et al. (2022); Vyas) al. (023) observe that, when trying to understand a finite network using theory for infinite networks, one should scale up using the j-parameteerization - not the neural tangent kernel parameterization infinite-wide
and this gives a (somewhat) pheoreticalll-ttactale
model which quantitatively captures the finite network one started with. Similarly, we find that scaling o² in the manner we describe and not keeping it ((1) gives a tractable limit that closely resembles our experiments.
H.1 RECOVERING BENIGN OVERFITTING FROM OUR RESULTS
That said, since we worked out our theory with of as a free variable, we can always recover the benign overfitting "noise- dominnttdd case by simply taking setting of = 0(n ( + oo post hoc, which gives 2² = (1). (This will be nonrigorous, since some of the formal statements of Appendix assumed 2 (1)) and would need to be reworked slightly, but this is technicality. and we will find that the limit of large o can be taken with no difficulty.)
Test error in terms of fitting ratio with dominant noise. When 02 > 1, Lemma 10 reduces to approximately
E
(64)
1+ (a 1), Ru/lee
32

---

Published as a conference paper at ICLR 2024
where we have neglected sub-leading- ledeeiinnngereerr order error terms. Equation 64 tells two useful facts. First, in our powerlaw setup, interpolation in this noise-dominated regime will always hurt us, specifically by factor of ox. (This is consistent with the analysis of Mallinar et al. (2022), who find that the zero-ridge overfitting coefficient is ε=|s=0
a + on (1)). Second, as we take the limit a 1. the additional "cost of interpolation" goes to zero, and we recover benign overfitting. We now see that the peculiar eigenvalue decay A; x i log ? found to give benign overfitting is essentially a way to take the limit + without incurring the divergence in kernel norm one gets at exactly
1.
Viewing such benign spectra as effectively having a + 1, we now see that as a consequence of our powerlaw analysis that for any target function with 3 > and no noise, we expect zero ridge to be required for optimal fitting. We thus conjecture that ridge regression with the benign spectra already identified in the literature in fact exhibits obligatory overfilting for a wide set of reasonable target functions long as there is no noise!
Illustrating benign overfitting in our framework. Figure depicts the approach to benign overfit- ting - 1. Figure shows how taking this limit actually makes overfitting obligatory if the target function is noiseless.
noise-dominated regime (a
2.0
test error En (arb. units)
1.5
1.0
0.5
a 1.01
0=1.2
1.05
a= 1.5
G 1.1
2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
fitting ratio Rtyo
Figure 8: When the target function dominated by noise, taking a + 1 in our analysis recovers benign overfitting. This plot shows theoretical fitting ratio test error curves generated from Equation 64 As a approaches 1, it ceases to matter what fitting ratio one regularizes to: the test ratio is Bayes-optimal (up to sub-leading-order terms). Note the lack of resemblance between these theoretical noise-dominated curves and the experimental curves of Figure [ Curves with a illustrate "tempered overfitting" à la Mallinar et al. (2022).
1.3, o =
== 1,15 =0
1.05, 2
test ertar Eie Gab.. units)
100
10a
10a
10-1
10
0.5
fitting ratio Rugie
& E.
filling ralio Ruyo
fitting ratio Rute
Figure 9: The a + 1 eigenspectra known to exhibit benign overfitting in fact give obligatory overfitting on noiseless target functions. This plot shows theoretical fitting ratio vs. test error curves assuming powerlaw cigenstructure and no noise, generated from Lemma I0 Each plot takes fixed eigenvalue exponent and varying eigencoefficient exponent B. Dots show the location of the minimum of each curve. As per Corollary [] interpolation (Ru//t = 0) is optimal when / 2 a. As approaches 1 (plots left to right), interpolation becomes optimal for all target functions with powerlaw decay.
H.2 RELATION TO "TEMPERED OVERFITTING"
Mallinar et al. 2022) describe a fitting behavior they term "tempered overfitting" in which training beyond optimal regularization to the point of interpolation incurs penalty test error which
33

---

Published as a conference paper at ICLR 2024
not negligible (as in benign overfitting) and is also not arbitrarily large, but rather takes the form of some multiplicative factor (1). particular, they find that kernel regression with powerlaw eigenspectra X ~ i- exhibits tempered overfitting in the noise-dominated regime, with the proportionality constant in fact equal to a. This is reflected in Figure [
We find that these same spectra may exhibit obligatory overfitting when the targets also have powerlaw structure and the noise is not dominant. The task eigenstructures consider here will generally be tempered as soon as interpolation is no longer optimal that is, as soon as the condition of Corollary | is violated.
34

---

Published as a conference paper at ICLR 2024
1 PROOFS: KRR WITH POWERLAW STRUCTURE
Here we will derive picture of the train and test risk of KRR under powerlaw eigenstructure, The ultimate goal is to arrive at Theorem 2 giving the optimal fitting error ratio for exponents a, 3 and noise level. Along the way, we will derive closed-form equations for many quantities of interest, including the test risk & (Lemma TO). which are plotted as theory curves in Figure 2 All results in this appendix will assume powerlaw task eigenstructure as per Definition that is, there exists some positive integer o O(1) such that, for all i 2 io. it holds that X i and e, = i i (We do still assume that the eigenvalues are indexed in decreasing order, even though the first to 1 will not be exactly powerlaw.)
I.1 RECALLING THE KRR EIGENFRAMEWORK
We begin by stating the k - Do limit of the RF eigenframework of Section 4 In this limit, we recover a known risk estimate for KRR (or equivalently linear ridge regression) that has been converged upon by many authors in recent years (Sollich, 2001 Bordelon et al. [020 Jacot et al. 2020a Simon ct al. 2021; Loureiro et al. 2021 Dobriban & Wager 2018 Wu & Xu 2020; Hastie et al. 2022 Richards et 2021)
a result which we actually bootstrapped to derive our RF eigentramework
(Appendix E.. We also recall this same eigenframework at the start of Appendix F]
This risk estimate
as follows:
Let be the unique nonnegative solution to
8
Σ
+ K
= n.
(65)
A₂ +
Then test risk is given approximately by
MSE ~ E == EoB,
(66)
where the overfitting coefficient & is given by
En
(67)
n Σi
Aith
and the bias is given by
B
U + 0².
(68)
Ai +
K
As discussed in Appendix E. the "A"" in 66 can be given several meanings. Firstly, it becomes an equivalence in an asymptotic limit in which n and the number of eigenmodes a given eigenvalue range (or the number of duplicate copies of any given eignemode) both grow large proportionally (Hastic et al. 2022] Bach 2023). This often phrased as sampling a proportional number of new eigenmodes from a fxxed measure. Secondly, with fixed task cigenstructure, the error incurred can be bounded by decaying function of (Cheng & Montanari] (2022). Thirdly, numerical experiments find small error even at quite modest n (Canatar et al., 2021 Simon et al. (202). As with the RF eigenframework, in this paper will simply treat an equivalence, formally proving facts about the risk estimate Eic-
Recall that all sums run from i = 1 to oo. Train risk is given by
82
MSE Rs Enr ==
E,e
(69)
?
and so the fitting error ratio is given roughly by
MSEn
En 52
so Ruftte
(70)
MSE
& n²x²²
Recall that the noise level defined relative to the zero-noise-zerr-ridee risk
o² oe
E
(71)
We will assume throughout that a > and (1. 2a + +1). We will also assume n 2 1. We will generally use an asterisk to demarcate quantities which occur at the optimal ridge w.r.t. test risk. For example, 8_ arg ming E and K., k|8=6,, and Ri R 1==6--
35

---

Published as a conference paper at ICLR 2024
It is worth noting that have two varying parameters in our system: the sample size and the ridge 6. Other quantities, like x or Ry/we may seen as functionn n and d. When we state scaling results using big-O-style notation, they will describe scaling with respect to that is, (f 6)) means that there exist constants no, C' > such that, for all n 2 no, it holds that x S Cf(nn,) 8). We will allow ō to vary arbitrarily, including as function of n.
1.2 CONTINUUM APPROXIMATIONS TO SUMS
Our main trick will be approximating the sums appearing in the eigenframework by integrals. The primary technical difficulty will be in bounding the error of these approximations (though we will ultimately find that these errors do not present a problem). Upon a first reading of this appendix, a reader may wish to simply ignore all error terms to grasp the overall flow of the argument.
Various quantities in this appendix will have complicated prefactors depending on the exponents a and B. These prefactors often cancel and simplify in the final accounting III is useful at first to pay less attention to these prefactors and more attention to how quantities scale with respect to, for example, n (which will be large) and i (which will small).
Here we state continuum approximations to the three eigensums of the eigenframework.
Lemma (Continuum approximations to eigensums). The sums appearing in the KRR eigenframe- work can be approximated as follows:
X;
π K 1 +0(1),
1/a
(72)
A + a aa)
8
A
7(a
x -1/a + +(1),
(73)
Xi + R
a² sin(
D6
2 a(a BB+1) 1)
2-1
+ +0(22
2/
k
(74)
di + 16
a sin T (8-1)
Proof. First, we argue that we may disregard the first in = (1) terms in these sums and replace them with their ideal powerlaw values A = and r²² = =i 8_ For the first two sums, note that replacing the first in terms (or neglecting the first in terms entirely) only incurs an ((1) error, which is the size of the error terms in Equations
(72) and (7) anyways. For the third sum, note that replacing the first
in terms (or neglecting the first to terms entirely) only incurs ((x²) error, which is at most the
size of the error term in Equation 74 anyways. We may thus proceed assuming perfect powerlaw structure, with io 1.
To prove the first clause, we note that the summand is monotonically decreasing, and thus use integrals to bound the sum as
a
i
di
di
1.
(75)
i
a +
The LHS integral evaluates a sin( a)) x 1/a which is sufficient to give Equation
72
Equation 73 is obtained in exactly the same way.
Equation 74 is obtained in the same way, except that the summand is no longer monotonically-
decreasing if / E (2a, 2a + 3). instead monotonically increasing to a maximum of size ((x3/a) at index 2max = 8-1/ 12a 3) 1//x//1/-///// + O(1) before monotonically decreasing to zero. Splitting the sum into increasing and decreasing parts and again using integrals to bound the sum gives Equation 74
We will more or less never again need to worry about the constant cutoff index io and can forget about it now, Our conclusions will live in the regime of large n, and in this regime, it will be sufficient to have powerlaw tails, and we can simply neglect constant number of eigenmodes at
Remark.
The authors are grateful for the existence of computer algehra systems.
36

---

Published as a conference paper at ICLR 2024
low index. One should usually expect the sub-leading-orde enror terms will carry around to be smaller the smaller in is and the less the task deviates from perfect powerlaw eigenstructure, however (though one likely ought to consider some measure of total deviation rather than simply the cutoff in).
Remark. In several places in this appendix. including Equation 74 we will encounter the fraction (a - 3 + 1)/ (B - 1).a). This is nominally undefined when / = a + 1. However, this discontinuity disappears with application of I. H''otiial''s 's rule, simplifying evaluating the integral to arrive at the RHS of Equation 74] if we specify that / = a + 1, then e.g. Mathematica informs us that the integral evaluates to the result of applying L'Hopital's rule to the general form.) Rather than treat the case = a + specially, we will simply gloss over it with the understanding that L. Hopital's 's rule ought to be used to resolve this undefined fraction.
/o. (Indeed, when
1.3 THE ZERO-NOISE-ZRRO-RRE
TEST RISK
Because the noise level defined normalized fashion by o² - d Evel=====u we need to find the zero-noise-zen -iie-ooo---ero--rdgge risk Eeloo=-m- before we can study the noise in the general case. The cero-noise-zero-eee zero-ridge risk also an interesting object in its own right.
Lemma (Zero-ridge implicit regularization). A1 = O, the implicit regularization & is given by
k|6=0= = (a
sin iiisiniTi/a (T/a) n a + 0 (nn-(att)).
(76)
Proof. This follows straightforwardly from inserting Equation 72 into Equation 65
Lemma (Zero-noise-zero-ride test risk). At o² = 0 and å = 0, the test risk & is given by
T²(a + 1)
Eelo2=6=0 a sin s(8-1)
13-1) + +(n +n
(77)
(sin(T/aa))
Proof.
This follows from inserting Equation 76 the continuum approximations of Lemma then inserting the results into the the eigenframework to get Exe, and finally simplifying.
Remark. In the process of doing this, one finds (after surprising cancellation) that the overfitting coefficient is simply Eols=o o = a + O(n bn1 as previously reported by Mallinar et al. (2022)
1.4 TEST RISK IN TERMS OF x
We now turn back to the general case in which noise and regularization are nonzero. The following lemma gives test risk in terms of the implicit regularization x.
Lemma 4.
12
E
a² (isin(T/a)) 11/aa 1/a
a(a-1)
a(a 18+10 1)
R
9-1 +
a
a sin s(8-1) (sin(T/a))8-1 " n (8-1)
B B+1) 1)
a² sin
π (8-1)
+O + n² R//a). (78)
Proof. This lemma follows from inserting Lemmas I and into the definition of E
Lemma S.
Ω On (n-a)) a) & =Ω
Ω min (re 01 and thus E.e S (n -(--1))
Proof. The fact that Ω (n~ follows from the fact that kls-n O -9) and is monotoni- cally increasing function 5.
To see that & 2 (min
we return the definition of & It is easily that E, = O1), because Eolá=o (1), Eo 2 and Eo monotonically decreases with 8, so need only examine the bias to understand the size of Ese in a scaling sense. Because a² = O(1), we -,)
have that x² = o Euelo==60 = O(n Onn-((11)) -(-1)) Examining the eigensum E, - 2, e? it easily
seen that at all modes i i' for some i' = O(max(1, -1/0)) will have that L. g-
t-
37

---

Published as a conference paper at ICLR 2024
say, which tells us that Eie Si d Ω follows from this.
The second clause of the lemma
The third clause of the lemma follows from the insertion of the first statement into the second. L
Lemma 6. At optimal regularization, we have that Eip = O (8-1), O(n -9), and thus 5. = =0 =an))a)1)
Proof. The first clause of this lemma follows from the lower bound on & given by LemmaB5and the fact that Eiela-o (n (8-1)) (which itself follows from inserting Lemma into Lemma Given this, the second clause of Lemma assures us that K₂ O(n as desired 13 The bound on 6, follows from
saturate this lower bound in scaling sense because do already at zero ridge,
Equation 72 and Equation 65
Remark. Lemma is useful because it tells us that, at optimal ridge, the enror terms in Lemma will indeed decay faster with than & itself.
I.5 RELATING K. AND Ray/te
Lemma 7, The fitting ratio is given in terms of k by
Ru//ve 1 - n V
x- 1/a O(n
(79)
asin((T/o)
Solving for K, we have
-a
K (asin(tTT)) n (1-VRu Riy/te + On Onn-))
(80)
Proof. This lemma follows directly from Equations (65
70 and
Remark. A minor annoyance the usage of Equation 80 is that, when Raj/ve is too close to the O(n"') term can affect to leading order. As a patch avoid this, we will initially restrict the domain of study to Rur/te E [0, for some n-independent constant e >> O. We are then assured that
K
(innn())))
π
n (1-VRuu(()) Ru,(we)
+ OOnn OOnn(ees (nn-(a-1)))
(81)
The fact that K increases monotonically with Ruy/te (Lemma 8 will let us extend results of interest to the small region Ruy/ee E (1 c, 1). As far as the study of the optimal regularization point go, we need not consider this small edge region in the following sense:
Lemma 8.
The fitting error ratio Ryfie E [0. 1) and implicit regularization [Mi]s=o, 0o) are monotonically-inerene functions of each other.
Proof. This lemma is apparent from the fact that Ru/wve
(1-
A1 Netk
Lemma 9, The optimal value of the fitting error ratio is bounded away from 1 in the sense that there exists a constant > 0 such that Ruj/ee S c' O(n
Proof. We know from Lemma that K. O(n We then obtain the desired result from Equation 79
1.6 PUTTING IT ALL TOGETHER: TEST RISK IN TERMS OF Ruyle
The following lemma gives the test risk & in terms of the fitting error ratio Ru/ite and is the basis for our ultimate conclusions about the optimal fitting error ratio.
IIt might seem that need to be mindful of the cutoff index up which do necessarily have powerlaw cigenstructure, but we do not actually: because in = @(1), we will still have i' = 0fmax(11,="0 1//))) 13 "Seenn this made easier by writing out scaling notation explicitly - e.g.. E. Q(n ((8-1) means that there exists constant Ai > 0 such that &n .n (8-1) for sufficiently large n, and solving for constants which are sufficient to give the desired new statements.
and then
38

---

Published as a conference paper at ICLR 2024
Lemma 10. Let c > 0 be an n-independent constant. Then for Rus/ie E [0, c), we have that
-(3-1)
T - (
E = =x==a (a a B 1) sin (1))
csc
1
(ooid + (1- 11-VRuth Rulle)
-(B-1)
- (8-1)
x 1 (a 1) Ru/ie
n
+ O(n -8 + -n 2
(82)
where the suppressed constants in the Onn + n 22) term may depend on
Proof. This lemma follows from insertion of Equation 81 into Lemma
Lemma 11. Let abbreviate Rajee and let e be the n-independent constant from Lemma
10
Then for Re//te E [0, 1 - c), we have that the second derivative of the log of the train error obeys
d²
(a 1)2
3 8-1+ aB13 - 1)(1 r) -
o + +O(n -1 + n -20t8-11
log E
+
2r
(1+ + (1 a1-
+l-r
(83)
2 (a- + OnO 22-8--1)) a²
(84)
and thus sufficiently large n, Eu is strongly logarithmically convex w.E.f т.
Proof. This lemma follows from taking two derivatives of Ene as given by Lemma
Lemma 12. For all Rut/le
E (0,1), we have that
E E.
2
+
(a (a-1)²
Rur//e
V Rigpse) + +OOn + (2224+811)
(85)
2a²
Proof. It is easy to see that this holds for all Ris/te E 10, 10,1-6 c) for any constant 0. Indeed, it follows directly from Lemmal II Note that
(a 1)2
(V Ru,pue Rijfie) On + - (86)
log E log E
20²
so
E E
exp
1)²
(VRus/le - Rijiie
21 }
+0(n Onn +n
- -20t8-1).
(87)
201
which yields Equation 85 using the fact that ex > 1 x for x E R. We now need to assure ourselves that this bound still holds for Ru/ite (1 1). Intuitively, the test tisk will generally explode as
Ruy/te + 1, growing from O(n O(n (3-1) to ((1), so we should expect this lower bound to hold near Ruyie = 1 with little trouble. Since the error terms we have been carrying around grow large in this region, we will need to rely on Lemmas 5 and g for support.
First, observe that there exist constants B1, 71 such that, if
ELe Bin (9-1) for all n4
(88)
on the region Ray/ E (1-c, 1), then Equation 85 will hold this region. (For example, one might set Ray/Le = 1 on the RHS of Equation 85 then use the fact that & = ((n (9-1) (Lemma G) then
increase the constant a small amount to absorb the O(n 1 + n 22-2++-11 error term. ) Then note that, by Lemma 5 there exist constants B2, n2 such that
E 2 B2 -99-)//
for all 122-
(89)
Thus, provided that >> max(n1, n2), are assured of Equation 88 so long i small enough that > (B2/ ) ()) -a We can identify such sufficiently small by looking at Equation 79 which tells us that so long as n3 for some n2, we can be assured that & is sufficiently large when Rur/te = - for
T/ (a sin)=/a)). The fact that x monotonically increases with Ray/re (Lemma 8) assures us that x will remain sufficiently large for all Ruyre E (1 1), and thus Equation 88 will continue to hold. This patches over our edge and completes the proof. nT
(B,/ / B2)
39

---

Published as a conference paper at ICLR 2024
Lemma 13. The value of the fitting envor ratio that minimizes the test ervor is
Riz/ie = r + O( 16-1 22++-11)
(90)
where v. is either the unique solution to
a - (ax 1)3r ala -
- -)
(91)
overr, E 10,1) or else zero if no such solution exists.
Proof. First, let the constant e in Lemma 10 be less than //, where c' is the constant prescribed
by Lemma 9 that we are assured that Rujie [0, 2c). Because the error terms are small
relative the quantity itself in the region Ruyle E [0, c). we may simply take a derivative of
Eie in terms of Re/te as given by Lemma 10 setting dr = 0. This yields Equations (90) and (1) We are assured that this equation function we differentiated to obtain is strongly log-convex for E [0, 1). as shown in proving Lemma IT] If this equation has no solution, this implies that there must be no local minimum on the domain, so the minimum over the domain must lie at (or more precisely, because we have error terms, close to) an endpoint that is, at either Ru/ic- = 0 + On - Rufie = 1 c O( 72), where min 2a - 3 + 1). However, we chose c to be small enough that Ru/tte < 2c + O(n")). so we can eliminate the right endpoint, and we have that R2//1c O(n7)) as desired.
dEn.
have only one solution
the domain of interest because the
Remark. It is worth emphasizing that, because we were free from the beginning to choose to be quite small, the rather technical patch business in the preceding proof not really all that important and can be glossed over on first reading. It is, however, nice to have for completeness, as covering the whole region Re//te E [0, 1) permits the final theorem statement to be simpler.
1.7 STATING THE FINAL THEOREM Putting together Lemmas 12 and 13 gives us Theorem 2
40


Reviews:
[{"review_id": "E338aTgWg7", "reviewer": "Reviewer_xXiV", "summary": "This work provides a unified formulation of the generalization error for random feature (RF) and kernel ridge regressions (KRR). While it is heuristically derived, it covers some expressions of the generalization error obtained in the previous work and gives us a quantitative understanding depending on the width (# of random features), sample size, teacher noise, and ridge penalty. This theoretical evaluation matches well empirical experiments. In addition, by focusing on the KRR limit, the authors succeeded in obtaining a more detailed evaluation for the case of power-law eigenstructure. That is, they provide an explicit formulation of the generalization error depending on the exponents of the student's and teacher's eigenstructures.", "questions": "**Major ones**\n\n(i)  Regarding Weakness (i), eq.(13) seems a starting point to derive the omniscient risk estimate. However, the authors give not enough explanation on how and which paper has derived this equation.  As long as I know, Sollich, 2001, Bordelon et al., 2020 obtained this expression for KRR by using some heuristic derivations. Did the other work that you cited, i.e., Jacot et al., 2020a; Simon et al., 2021; Loureiro et al., 2021; Dobriban &Wager, 2018; Wu & Xu, 2020; Hastie et al., 2020; Richards et al., 2021,  explicitly give this expression (13) as well? If so, under what conditions does each study derive? Are they mathematically rigorous?  Because this equation is the starting point of all other analyses, it should be clearly and carefully described. \n\n(ii) I am confused about what the authors try to claim in Figure 2. Do you intend to claim that overfitting is obligatory only for the noiseless case ($\\sigma_{rel}^2=0$)? For $\\sigma_{rel}^2>0$, the minimal test MSE is obtained for non-zero fitting ratios. This implies that the generalization is the best for non-overfitting situations and the overfitting seems *not* obligatory. This point is unclear.\n \n**Minor ones**\n\n(iii) In Section 5, the authors focused on the KRR limit (k -> infty). I am curious about at what point the finite-k case becomes hard to analyze. \n\n(iv) Page 6: The definition of the fitting ratio seems to be wrong. It should not be R_tr /te:=E_te/E_tr but \nwould be E_tr/E_te.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "(i) While there are numerous individual analyses of RF and KRR under various conditions, this study attempts to provide a unified perspective. This endeavor, even if the derivation is heuristic, will be important for establishing a foundation for understanding.\n\n(ii) While tackling such a significant (big) question, the study also provides technically solid contributions. In particular, this work gives novel continuum approximations for the generalization errors depending on the power-law eigenstructures (in particular, Lemma 1,10). This enables us to quantitatively understand the obligatory conditions for the \"more is better\" in the case of overfitting. This work also includes other technically solid and informative results such as remarks on the appropriate scaling of target noise (eq. 7), connection to the previous work (Section E), and the sophisticated evaluation of the power-law eigenstructures (Section B).\n\n(iii) The paper is very well structured and articulated, with various efforts made to facilitate the reader's comprehension. This implies the author's deep understanding of RF and KRR.", "weaknesses": "(i) While the analysis for the power-law eigenstructure is solid and concrete, the other part seems not so surprising as the theory. I mean, the heuristic derivation is rather straightforward.  It seems that the authors just substituted a heuristically-derived terms for the kernel matrix of RF (eqs.26-30) into a well-known expression of the generalization error (eqs.13, 14). I understand that providing a unified formulation itself is a very curious and interesting attempt, though.  Please refer to my Question (i) for more details. \n\n\n\n(ii) The definition of overfitting in this paper is unique, and its relation to the ridgeless case seems unclear. considering a ridgeless case seems appropriate when talking about overfitting to training samples. Indeed, Mei & Montanari 2019 have reported a certain condition where generalization error is minimized in a ridgeless setting and this was one of the main contributions.\nIn contrast, the current study does not directly analyze the ridgeless case but rather allows a non-zero fitting ratio in its analysis. For example, while Theorem 2 contemplates the optimal ridge, it's not explicitly stated when the optimal ridge becomes zero. I am also curious whether the noise condition in Corollary 1 works as a necessary and sufficient condition where the ridge-less case gives the best performance (I mean, the generalization error is minimized).", "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": "", "extra_scores": {}}, {"review_id": "zWYMu6kh2o", "reviewer": "Reviewer_S1iV", "summary": "The paper studies how scaling the model size and the dataset size affects the performance of random features models.\nWhile \"classical\" learning theory predicts that scaling the model can hurt performance, causing the model to overfit the data, this seems not to be true when learning with modern tools, e.g. neural networks. In practice, it seems that the bigger the model is, the better the performance it gets.\nThis paper recovers this behavior in the setting of learning ridge regression with random features. Namely, the authors establish that, for a correctly tuned ridge regression, the model's test error always improves with the number of features and the number of training samples. That is, the \"double descent\" phenomenon can be eliminated by correctly tuning the model's parameters. Additionally, the authors show that overfitting is necessary to achieve good performance in some settings with low noise. That is, not only overfitting doesn't hurt performance, but it also enables reaching optimal test error.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper shows two important results on the behavior of random feature models: first, that they can always improve with scale (both in terms of number of features and number of examples), and second, that overfitting might be necessary in some problem settings. To my understanding, these results unify previously studied settings, and present theoretical results that are more aligned with behaviors of large models in practice. The experiments seem to be convincing that the assumptions made in the analysis are reasonable in practical settings.", "weaknesses": "One point that I think the authors should clarify is in which cases the analysis is \"rigorous\", in a sense that the results follow from the problem assumptions, and in which cases the derivations are loose. It would be helpful, even for the \"nonrigorous\" steps, where some quantity is approximated, to state what are the precise bounds on the estimations. For the theorem statements in the paper, the way they are currently written, it is not clear if they truly follow from the assumptions, or are there some additional approximations (beyond the one covered in Assumption A) that are used in the analysis.\n\nAdditionally, for the results in Section 5, it is not clear what is the role that the noise plays in the analysis. Clearly, for large enough noise, overfitting hurts performance, i.e. - there is a predictor for which train error might be high (or even very high). While I understand that the noise might need to be scaled down (i.e., not analyze the setting of constant noise), it seems that the results in the paper only cover relatively low noise setting. What happens for higher noise levels? Do we expect overfitting to be unnecessary, or even hurt performance?\n\nMinor:\nPage 7, Target noise paragraph - \"unlike is conventional\" is probably a typo.", "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": "", "extra_scores": {}}, {"review_id": "O3EgicSQNk", "reviewer": "Reviewer_cEFV", "summary": "This paper aims to provide theoretical backing for the recent empirical study about the scaling \"law\" of large language models, i.e. larger model size + more data + more compute = more performance. To this end, the authors propose to study the random-feature (RF) regression model and show that their approximation to the test error strictly decreases when more data points and more width are provided. Then, they characterize which tasks obtain optimal performance when the training error is much smaller than the test error. Finally, some empirical evidence supporting the theory is provided.", "questions": "1. Could the authors please address the above concerns?\n2. The authors mentioned that \"we do not want to take a fixed noise variance\" and then argued that it is better to scale it proportional to the uncaptured signal. I'm not sure if this is realistic since $\\sigma^2$ is the aleatoric (irreducible) uncertainty inherent in the data (think about the noise resulting from some measurement error in a sensor). How do you handle this, then? Maybe you should instead argue using the language of GPs, and thus give you the freedom to talk about _epistemic uncertainty_, which decreases as $n$ increases?\n3. How should one relate Thm. 1 and Fig. 1? In the former, the test error should always decrease, but in the latter, the test error saturates. Note that, I think Fig. 1 is the \"correct\" behavior: kernel machines are not powerful and thus the test error is bounded away from zero, higher than DNN's. (As for the train error, this seems fine since infinite-width => linearity => quadratic loss => global optimum is achievable.)\n4. How does this paper relate to the work of [Bowman & Montufar (NeurIPS 2022)](https://arxiv.org/abs/2206.02927), which also studies the large-width large-data regime?\n\nThanks!", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is very well written and polished. I believe the idea is original, although I'm not very familiar with this field beyond the standard NTK/NNGP theory (see my question below, though)---my confidence reflects this. The presentation is in general, clear; although some specific parts can be improved. More importantly, the paper's aim to formalize the common beliefs in the field---in what people call scaling \"law\"---is laudable.", "weaknesses": "First, as I mentioned before, in some parts, the presentation can be improved. Here is a non-exhaustive list:\n\n1. How are the approximations of the train and test errors on page 4 derived. I think it is crucial to at least provide intuitions about them and quantify the approximation errors. This is because much of the results of the paper rely on those approximations.\n2. The term \"interpolation\" keeps coming up without being defined. Maybe it is obvious for people in this specific field; however, for the benefit of a broader audience, the authors should be more verbose.\n\nSecond, I'm unsure about the significance of the theoretical results. Mainly because the authors claim that the test error becomes better as $n$, $k$ increase because the RF model converges to the kernel regression limit. However, it is a bit hard to believe since kernel machines (RFs, GPs) are in general worse than their finite-width NNs counterpart (kernel machines = linear models => no representation learning). As the authors mentioned on page 5, Thm. 1 works since intuitively RF -> kernel machine; the latter is the ideal limiting process. If this is the case, doesn't this imply that GPs should be better than standard NNs?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)