An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression
Authors: Lijia Zhou
James B Simon
Gal Vardi
Nathan Srebro
Venue: ICLR 2024 poster (2024)
Keywords: kernel ridge regression
cost of overfitting
benign overfitting
tempered overfitting
Primary area: learning theory
TL;DR: We study the cost of overfitting in noisy kernel ridge regression (KRR)

Abstract: We study the cost of overfitting in noisy kernel ridge regression (KRR), which we define as the ratio between the test error of the interpolating ridgeless model and the test error of the optimally-tuned model. We take an ``agnostic'' view in the following sense: we consider the cost as a function of sample size for any target function, even if the sample size is not large enough for consistency or the target is outside the RKHS. We analyze the cost of overfitting under a Gaussian universality ansatz using recently derived (non-rigorous) risk estimates in terms of the task eigenstructure. Our analysis provides a more refined characterization of benign, tempered and catastrophic overfitting (cf. Mallinar et al. 2022).

Published as a conference paper at ICLR 2024
AN AGNOSTIC VIEW ON THE COST OF OVERFITTING IN (KERNEL) RIDGE REGRESSION
Lijia Zhou
James B. Simon
University of Chicago
UC Berkeley and Generally Intelligent james. s simnnberreeeey edu
zlj@uchicago. edu
Gal Vardi
Nathan Srebro
TTI-Chicago and Hebrew University galvardi@ttic..
TTT-Chicago nati@ttic. edu
ABSTRACT
We study the cost of overfitting in noisy kernel ridge regression (KRR), which we define the ratio between the test error of the interpolating ridgeless model and the test error of the optimally-tuned model. We take an "agnostic" view the following sense: we consider the cost function, even if the sample size is not large enough for consistency or the target is outside the RKHS. We analyze the cost of overfitting under Gaussian universality ansatz using recently derived mno-rigooous) risk estimates in terms of the task eigenstructure. Our analysis provides a more refined characterization of benign, tempered and catastrophic overfitting (cf. Mallinar et al., 2022).
function of sample size for any target
INTRODUCTION
The ability of large neural networks to generalize, even when they overfit to noisy training data (Neyshabur et al., 2015; Zhang et al., 2017; Belkin et al., 2019), has significantly challenged our starting point for understanding overfitting in deep
understanding of the effect of overfitting. learning is to understand the issue in kernel methods, possibly viewing deep learning through their kernel approximation (Jacot al., 2020). Indeed, there is much progress understanding the effect of overfitting in kernel ridge regression and ridge regression with Gaussian data. It has been shown that the test error the minimal norm interpolant can approach Bayes optimality and so overfitting is "benign" (Bartlett et al., 2020; Muthukumar et al., 2020; Koehler et al., 2021; Wang et al., 202 1; Donhauser et al., 2022). In other situations such as Laplace kernels and ReLU neural tangent kernels, the interpolating solution is not consistent but also not "catastrophically" bad, which falls into an intermediate regime called "tempered" overfitting (Mallinar et al., 2022).
However, the perspective taken in this line of work differs from the agnostic view of statistical learning. These results typically focus on asymptotic behavior and consistency of a well-specified model, asking how the limiting behavior of interpolating learning rules compares to the Bayes error (the smallest risk attainable by any measurable function of the feature x). In contrast, the agnostic PAC model (Vapnik& & Chervonenkis, 1971; Haussler, 1992; Shalev-Shwartz & Ben-David, 2014) does not require any assumption on the conditional distribution of the label In particular, the conditional expectation Ely[2] [=] is not necessarily member of the hypothesis class and does not need to have small Hilbert norm in the Reproducing Kernel Hilbert Space (RKHS). Instead, the learning rule is asked to find a model whose test risk can compete with the smallest risk within the hypothesis class, which can be quite high if predictor in the hypothesis class can attain the Bayes error. In these situations, the agnostic PAC model can still provide a meaningful learning guarantee.
Furthermore, we would like to isolate the effect of overfitting (i.e. underregularizing, and choosing to use a predictor that fits the noise, instead of compromising on empirical fit and choosing a predictor that balances empirical fit with complexity or norm) from the difficulty of the learning problem and appropriateness of the model irrespective of overfitting (i.e. even we were to not overfit and instead optimally balance empirical fit and norm, in ridge regression). A view which considers

---

Published as a conference paper at ICLR 2024
only the risk of the overfitting rule (e.g. Mallinar al., 2022) confounds these two issues. Instead, would like to study the direct effect of overfitting: how much does it hurt to overfit and use ridgeless regression compared to optimally tuned ridge regression.
In this paper, we take an agnostic view to the direct effect of overfitting in (kernel) ridge regression. Rather than comparing the asymptotic risk of the interpolating ridgeless model to the Bayes error, we compare it to the best ridge model in terms population error as a function of sample size, and measure the cost of overfitting as ratio. We show that the cost of overfitting can be bounded by using only the sample size and the effective ranks of the covariance, even when the risk of the optimally-tume model high relative to the Bayes error. Our analysis applies to any target function (including ones with unbounded RKHS norm) and recovers the matching upper and lower bounds from Bartlett et al. (2020), which allows us to have a more refined understanding of the benign overfitting. In addition to benign overfitting, we show that the amount of "tempered" overfitting can also understood using the cost of interpolation, and we derive the necessary and sufficient condition for "catastrophic" overfitting (Mallinar et al., 2022). Combining these results leads to refined notion of benign, tempered, and catastrophic overfitting (focusing on the difference versus the optimally tuned predictor), and characterization the effective rank rę at some index k. We further apply our results to the setting of inner product kernels in the polynomial regime (Ghorbani al., 2021; Mei al., 2022; Misiakiewicz, 2022) and recover the multiple descent curve.
function of sample size based computing
PROBLEM FORMULATION
Let X' be an abstract input space and K X x X' - positive semi-definite kernel".
2.1 BI-CRITERION OPTIMIZATION KRR
Given a data set Dn consisting of (I1, vi),.., (In, Nn. E X x R sampled from some unknown joint distribution D, order to find a predictor with good test error R(f), we solve the bi-criterion optimization:
min R()), ll
SEH
where ll is the Hilbert norm in the RKHS and the test error and training error (in square loss) of predictor f is given by
R(f) : B - w]
and R(f)= = (f(e)) - 2:
1=1
The Pareto-frontier of the bi-criterion problem (1) corresponds to the regularization path {fs) given by the sequence of problems:
arg min R(f) + 5
fl
JeH
n
By the representation theorem, fa has the explicit closed form:
(2) where K(D,,, .) R² ((D D,)) E Raxn Y E R are given by [K(D,, K( x), [K,,,, D,),,,s = K(I,, 2 and [ = yt. The interpolating "ridgeless" solution (minimal norm interpolant) is the extreme Pareto point and obtained by taking 5- 0+:
is(x)) K(Dn, TTTT (K D.)) + ōT.)
fo arg min Il
SEN:R())=
Even though fo has the minimal norm among all interpolants, the norm of fo will still be very large because it needs to memorize all the noisy training labels. In this paper, we are particularly interested in the generalization performance of the ridgeless solution fo. which minimizes the training error in the bi-criterion problem (1) too much
li... (i) Va, x' E X, K(x,)1 K(x', and (ii) Vn N, æi, Jn E X. C1 E R, it holds that E Ep Gey K(),,,,) 2 0.
2

---

Published as a conference paper at ICLR 2024
2.2 MERCER'S DECOMPOSITION
Though the setting for KRR is very generic, we can understand it as (linear) ridge regression. By Mercer's theorem (Mercer, 1909), the kernel admits the decomposition
K (xx,
Σ (1o)(()((z))
(3)
where 0; X' + R form complete orthonormal basis satisfying Ez (z) O otherwise, and the expectation is taken with respect to the marginal distribution of x given by D. For example, X {21,-.. "0.,:..,... 3 has finite cardinality M and x is uniformly distributed over X. then (3) can be found by the spectral decomposition of the matrix (() E RMMM given by (K( = K (x (,)) When x uniformly distributed over the sphere in IRd or the boolean hypercube {-1, 1]d then { can be taken to be the spherical harmonics or the Fourier- Walsh (parity) basis. In the case that K is the Gaussian kernel or polynomial kernel, the eigenvalues (A:) has closed-form expression in terms of the modified Bessel function or the Gamma function (Minh et al., 2006).
and
Therefore, instead of viewing the feature x as an element of X. we can consider the potentially infinite-dimensional real-valued vector (xx)) (i (2) (r))...) and denote the design matrix V (1)(),), (.22)..... Then we can write K(x,x') = (v(x)), =xx") and understand the predictor in (2) as
fs(x) (xx)) T (TVT + -1
= (wi, (xx))
where Wi = T (T.TT + +-,1)) simply the ridge regression estimate with respect to the data set (V, Y). For predictor of the form ((x = (w, (x)) its Hilbert norm is given by ||/ - ||
The Bayes-optimal target function is (x) = (Pe We may expand this function in the kernel eigenbasis as fz) = Σ; (z)((z), where } are eigencoefficients. Let the noise level be
² ((y))=((yyS((())
2.3 CLOSED-FORM RISK ESTIMATE FOR (KERNEL) RIDGE REGRESSION
A great number of recent theoretical works have converged powerful set of closed-fome equations which estimate the test risk of KRR in terms of task eigenstructure (Hastie et al., 2019; Wu & Xu, 2020; Jacot et al., 2020; Canatar et al., 2021; Loureiro al., 2021; Mel & Ganguli, 2021; Richards et al., 2021). We shall use the risk estimate from these works as our starting point. These equations rely on (some variant of) the following Gaussian design ansatz:
Assumption (Gaussian design ansatz). When sampling (x,-) D, the eigenfunctions are either Gaussian in the sense that (1()) ~ (O, diag (Ar)), or else we have Gaussian universality in sense that the expected test risk is unchanged we replace (xxx) with (xx), where is Gaussian in this manner.
Remarkably, Assumption appears to hold even for many real datasets: predictions computed for Gaussian design agree excellently with kernel regression experiments with real data (Canatar et al., 2021; Simon et al., 2021; Wei et al., 2022). We will take Assumption 1 henceforth.
We now state the "omniscient risk estimate" presented by this collection of works. 2 First, let the effective regularization constant Ki be the unique nonnegative solution to
X
8
Σ
X
+
K6
166
Using Ks, we can define
A
C.,6
and
Es
(5)
X; Kg
E, C7
We adopt the notation of Simon et al. (2021), but the risk estimates of all mentioned works equivalent. We take the term "omniscient risk estimate" from Wei al. (2022).
3

---

Published as a conference paper at ICLR 2024
where refer Lis the learnability of mode and Es the overfitting coefficient. test risk over datasets is then given approximately by
The expected
= = =5 Es ( +02
(6)
The "se" in (6) can be given several meanings. Firstly, it becomes equivalence in an appropriate asymptotic limit in which n and the number of eigenmodes in a given eigenvalue range both grow proportionally large (Hastie et al., 2019; Bach, 2023). Secondly, with fixed task eigenstructure, the error incurred can be bounded by a decaying function of n (Cheng & Montanari, 2022). Thirdly, numerical experiments attest that the error is small even quite modest (Canatar et al., 2021; Simon et al., 2021). For the rest of this paper, we will simply treat as an equivalence, formally proving facts about the omniscient risk estimate R((f)). Thus, our results follow by analyzing the expression from (6).
COST OF OVERFITTING
The sensible and traditional approach to learning using a complexity penalty, such as the Hilbert norm || fl is to use Pareto point (point on the regularization path) of the bi-criteria problem (1) that minimizes some balanced combination of the empirical risk and penalty (the "structural risk") so as to ensure small population risk. Assumptions about the problem can help us choose which Pareto optimal point, i.e. what value of the tradeoff parameter 8, to use. Simpler and safer is to choose this through validation: calculate the Pareto frontier (aka regularization path) on half the training data set, and choose among these Pareto points by minimizing the "validation error" on the held-out half of the training set. Here we do not get into these details, and simply compare to the best Pareto point:
R(fa-) = inf R(fs)- 520
Although we cannot find fo- exactly empirically, it useful as an oracle, and studying the gap versus this ideal Pareto point provides an upper bound on the gap versus any possible Pareto point (i.e. with any amount of "ideal" regularization). And in practice, as well as theoretically, a validation approach as described above will behave very similar to fs.. We therefore define the cost of overfitting as the (multiplicattive) gap between the interpolating predictor fo and the optimaly regularized fa-: Definition 1. Given any data distribution D over X' x R and sample size N, we define the cost of overfitting as
R(fo) inf R(ss)' and its prediction based on (6) n)), = inf 820 R(($s)
R(fo)
C(D,n)
It is possible to directly analyze R(fa) and R(fs-) (or their predictions based on (6)) in order to study the cost of overfitting. However, any bound on R(fo) or R(fs-) will necessarily depend on the target function. Instead, we show that there is much simpler argument to bound the cost of overfitting.
Theorem 1. Consider Eo defined (5) with 5 then it holds that
Č(D, n) S Eg.
(7)
Proof. Observe that
R((xx)) = inf &s
Σ -1--)1))2 2 +02
820
inf
Σ (1- - (1-6),))22 L
820
Σ (1 Lx,) 203 +02
where we use the fact that (1 - 22 decreases as decreases, and K3 decreases as 5 decreases.
The proof concludes by observing (1 2 + R((oo)/o.
4

---

Published as a conference paper at ICLR 2024
Indeed, (4) and (5) used to define En does not depend the target coefficients. It is also straightforward check that if e2 then R(fo) Ego and R(f&-) o² by choosing 8 oc, and Č(D,n) Eg for any n. This shows that (7) is the tightest agnostic bound on the cost of overfitting:
Vr(z) Eo- = sup C(D,n)
P(y
where &g on the left-hand-side depends only on the marginal P(æ), while Č(D, n) depends on both the marginal P(z) and the conditional z))
More generally, it is clear that we have the lower bound
o²
Č(D,n) 2 Eo R(fs.)
due to the non-negativity of 2z in (6). Thus, from the above and Theorem 1, we have o² R(fs)
C(D.n) < 1. Therefore, if x² R(fs-)
n. - oc, namely, the optimal-tunek ridge is consistent, ((D.)) 1. That in this case Eo precisely captures the cost of overfitting. Eo
Eo
then
If the optimal-tuned ridge is not consistent, (7) might be a loose upper bound on Č(D, n). However, under our assumption, even in this case Eg still captures the qualitative noisy overfitting behavior in the following sense: If lim En- = 1, we have benign overfitting, i.e. Č + 1, regardless of the target; If l Eg oo and の² > 0, then we have catastrophic overfitting, i.e. Ö + oc, regardless of the target; If 1 < lim Eo co then overfitting is either benign or tempered.
Finally, we note that the argument the proof of Theorem shows something more: for any
< 8", it holds that R(fs) S. EgR(ff-) I fo-)). Therefore, the quantity & bounds the cost of overfitting not only for the interpolating solution, but also for any ridge model with sufficiently small regularization parameter 8. Consequently, if & is close to one, then the risk curve will become flat once all of the signal is fitted (for example, see Figure of Zhou et al. (2021)), exhibiting the double descent phenomenon instead of the classical U-shape curve (Belkin et al., 2019). Similar results the flatness of the generalization curve are proven Tsigler & Bartlett (2020) and Zhou et al. (2021).
3.1 BENIGN OVERFITTING
In this section, we discuss when &n can be close and so overfitting is benign. Note that the target coefficients play no role at all in our analysis. To further upper bound the cost of overfitting, we will introduce the notion of effective rank (Bartlett et al., 2020).
Definition 2. The effective ranks of covariance matrix with eigenvalues {M in descending order are defined as
Eist d
RR = (Eishd)) EiSt
Tk
and
AR+1
The two effective ranks are closely related to each other by the relationship Ta S Rs S <i and are equal is the identity matrix (Bartlett al., 2020). Roughly speaking, the minimal norm interpolant can approximate the target in the span of top k eigenfunctions and use the remaining components of x to memorize the residual. large effective rank ensures that the small cigenvalues of E are roughly equal to each other and so it is possible evenly spread out the cost of overfitting into many different directions. More precisely, we show the following finite-sample bound on &p. which decreases as increases if k o(n) and R₂ w()):
Theorem 2. For any k < n, it holds that
22
71
Eo
1
(8)
R
The conditions that l: = o(n) and Rş. w()) are two key conditions for benign overfitting in linear regression (Bartlett et al., 2020). They require additional assumption that ro o(n) for
5

---

Published as a conference paper at ICLR 2024
consistency, which is sufficient for the consistency of the optimally tuned model when the target is well-specified. Our Theorem provides a more refined understanding of benign overfitting: at finite sample n. if we can choose small & such that Rş is large relative to then the interpolating ridgeless solution nearly as good as the optimally tuned model, regardless of whether the optimally tuned model can learn the target. Furthermore, of Theorem 4 in Bartlett et al. (2020), though our proof technique is completely different and simpler since we have closed-form expression. Since Eg- (1 E. (3,))
also recover version of the matching lower bound
it suffices to lower bound
1 >: 27,0
Theorem 3. Fix any b b>> O. there exists such that n S k + bri, then let be the first such integer. Otherwise, pick k = nt. It holds that
n Σ ch 2 max
1
k n1
n
2
k
(b 1)2
R
+
T2
For simplicity, unless is small relative to n. Even Conversely, if both k/n and n/ R& are small, then to and we have identify the necessary and sufficient condition for Eo + 1.
take b = 1 in the lower bound above. We see that Eg cannot be close to 1
is small, the first term (9) requires n/ R& to be small.
apply Theorem 2 show that & is close
Corollary 1. For any n. E N, let kin be the first integer k < n such that n S + rk. Then Eo - 1f and only if
Kn lim +20000 n2
n
and
lim 1-000 R
0.
(10)
Though Corollary 1 is stated as asymptotic result, the spectrum is allowed to change with the sample size n and the target function plays no role in condition (10). Next, we apply our results to some canonical examples where overfitting is benign.
Example 1 (Benign covariance from Bartlett et al. (2020)).
A = i log - for some a >
In this case, can estimate
Σ Ax
dr (a- 1) log 11k---1(- +1)
k+1 x log" x
i>k
1
Σ x
dr + 1)(a 20g (k)
k + Jk
llog
k>
and so
(k: + 1)(2a - 1) log 2a 1 = (klg
Rs 2
(a 1)² log 20-2 2 + 1)
Then by choosing &
vlogn we have o(n) and R2 = w(n) because R O(log n).
Example (Junk features from Zhou al. (2020)).
if S ds if ds + 1 <is ds + dj
A
J
if > ds + dj.
In this case, is routine to check Rs = d, by choosing k = ds. Letting ds = o(n) and d, = w()).
Theorem shows that E,- + 1.
Finally, we show our bound (8) also applies to isotropic features in the proportional regime even though overfitting not necessarily benign.
Example 3 (Isotropic features in the proportional regime).
1 if < d 0 otherwise
A
for 7n and y >

---

Published as a conference paper at ICLR 2024
In this case, it is easy to check that 7% d k and so k + 7 = d
and Rn 0. The first
condition in (10) holds because kn/n = 0. However, the second condition in (10) does not hold
because Rg d lo and n/ Rk. 1/7 > 0. Plugging in k 0 to Theorem 2, obtain
The above upper bound is tight when v = 0 because is well-known that the proportional regime (for example, Hastie al. (2019) and Zhou et al. (2021)), it holds that
lim R(fo) 0² 7 --1
3.2 TEMPERED OVERFITTING
Theorem 2 allows us to understand the cost overfitting when is benign. However, it is not informative when no amount of "tempered" overfitting based on the ratio k/Tx over a finite range of indices.
satisfies R& n. In Theorem below, provide estimate for the
Theorem 4. Fix any e E (0, n/ro) and consider ky, ku E N given by
k == max {A: 2 k + ET S n} ku = min f
(1 + m.)
Then holds that
AK+1 XR+2 6
1k+1
& S (1+
max kskkck
(II)
To interpret (1I), we first suppose that the spectrum }A.} does not change with n and has infinitely many non-zero eigenvalues (which is the case in Example 4 and 5 below). For any fixed c 0, k must increases n increases. If & is large, then it is usually the case that da+1 = X or the ratio is bounded. Letting e = 1, we can understand (11) as & I 1+ k.
In particular, r = (,))), then & is bounded and overfitting cannot be catastrophic. Conversely, we show that overfitting catastrophic when тą = =o(k) in section 3.3 below. Therefore, the condition lim k/rx
is both necessary and sufficient for catastrophic overfitting: En - co. Furthermore, we argue that (11) is also sufficient for benign overfitting in some settings: lim4-+o k/Tx= O, then have limn-re Eo < (1 + e)² for any >> 0, and thus Eo - 1. Example 4 (Power law decay from Mallinar et al. (2022)).
A a for some a > 1.
In this case, we can estimate
x oo dx
Σ >;
-a dr
1
(a - 1)(k + 1)a-1
(a - 1)
k+1
i>k
600
I -20 dx
T 2a dr
(2xx 1) + 1)2a-1
(2a - 1)k2a-1
k+1
i>k
k
and so
k k+1
h
a-1
(a - 1a
(a (1.
Tk
k: +1
Therefore, we have li k/rk aa -- and so &n S a, which agrees with Mallinar et al. (2022).
We remark that the Laplace kernel and ReLU NTK restricted the hypersphere have power law decay (Geifman et 2020).
3.3 CATASTROPHIC OVERFITTING
We first state a generic non non- as-mmtommiiiccccc lower bound on E = (1- 1. E. C3,0) -1 and then discuss the implication for catastrophic overfitting increases.
7

---

Published as a conference paper at ICLR 2024
Theorem 5. For any k 2 it holds that
Σ
k k 12 + rk
(12)
For any > 0, rk: = o(k) and we consider k (1 + e)m, then it is straightforward from (12) that lim,-+00 Σ, 2%,0 2 e)- Since the choice of arbitrary, have limm-+oo n Σ, Ci 1
and so Eo > 00.
Example 5 (Exponential decay).
d =
In this case, we can estimate
Σ 12ck
E e de
and Mı and ra/k O. Theorem 5 implies that overfitting is catastrophic, as expected from Mallinar et al. (2022).
Since Theorem and are agnostic and non-asymptotic, characterization of whether overfitting is benign, tempered, or catastrophic, resolving an open problem² raised by Mallinar et al. (2022):
them obtain elegant
Theorem 6. Suppose that the spectrum {Ai} is fixed n increases and contains infinitely many non-zero eigenvalues.
(a) If lime k/Tk- O, then overfitting is benign: lim,-+00 Eo 1.
(b) If limg- k/Tr (0, oo), then overfitting is tempered: limn-soo En E (1,
(c) If 1om k/TK oc, then overfitting is catastrophic: lim,-+00 Eg 20.
APPLICATION: INNER-PRODUT KERNELS IN THE POLYNOMIAL REGIME
In this section, consider KRR with inner-product kernels in the polynomial regime (Ghorbani et al., 2021; Mei et al., 2022; Misiakiewicz, 2022). Let's take the distribution of x to be uniformly distributed over the hypersphere in Rd the boolean hypercube. Denote V/--1 to be the subspace of all polynomials of degree < i - 1 and (dd, () Oa(d') be the dimension of the subspace Vi of degree-l polynomials orthogonal to V-i-1- Moreover, denote P to be the projection onto V [T] and P>11 to be the projection onto its complement. Let {Yka 1x2.0..0..EE..... be the polynomial basis with respect to D (e.g. spherical harmonics or parity functions).
Inner-product kernels. Consider kernels of the form K K(x,x²) = ha (x, x')/d), then admits the eigendecompositon in the polynomial basis:
(ax(h) Yks (ko (xs)
K K(x, x<x,x'==
Σ
B(d, k)
DE (B(,A)))
We also expand the target in the kernel eigenbasis and define (x) E Exe(B(a))) Uka (n.))). Interestingly, the eigenvalues of K with respect to D have block diagonal structure. The block diagonal structure a consequence of the
the distribution x.
Polynomial regime. Consider the regime d' where / is not integer. We will choose k in Theorem to include the first [1] blocks. Then
k b(d,k) θ
Σ dh )
= (d o(n).
"See footnote 11 their paper. The settings they consider (c.g., clause (a) of Theorem 3.1 with 8 > 0) always satisfy R((fs)) a and lim R(ffo) lim Eo d.
8

---

Published as a conference paper at ICLR 2024
and
(Ex> ExE(B(aN)
B(d.k)
Rg
17)
Exsuy (h)
Σk>11 Ese[B(ddo)] 2 B(d, = ((d = w(1).
B(d.A)
Hence, the cost of overfitting is small when / is bounded away from the integers. To obtain bound on the error of the ridgeless solution, it suffices to analyze the error of the optimally regularized model, which can be easily done with uniform convergence. Using the predictions from Simon et al. (2021), we can also recover a type of uniform convergence known as "optimistic rate" (Panchenko, 2002: Srebro et al., 2010; Zhou et al., 2021), which is suitable for the square loss.
Theorem 7. Fix any k E N and let
(k2 + nn3. For any 8 2 0, it holds that
Eiii Aolllfoll
(1 (I- V (((fs) S
Note that the error of the predictor Pstyf is approximately
2
Σ Σ
=² + +1
(13)
A> LU ((d,))
and we can tune 8 to match the training error of fa- to (13) and the Hilbert norm satisfies Il 1l fl because fs is Pareto-optimal. Moreover, the expected norm of the feature is
S
(ax(h) B(d,k) k)
E (a))(h);
k>10 WE B((dk))
A>
and if [| (Eis11) (t)x o(n). then lim R(fo-) 0² + 11 In Ghorbani et al. (2021) and Mei et al. (2022), it shown that the above is not jusjust an upper bound. In fact, it holds that lim R(fo) = =0 + | and our application is tight in this case.
5 CONCLUSION
Understanding the effect of overfitting is fundamental problem in statistical learning theory. Contrary to the traditional intuition, prior works have shown that predictors that interpolate noisy training labels can achieve nearly optimal test error when the data distribution is well-specified. In this paper, we extend these results to the agnostic case and we use them to develop a more refined understanding of benign, tempered, and catastrophic overfitting. To the best of our knowledge, our work is the first to connect the complex closed-form risk predictions and the effective rank introduced by Bartlett (2020) to establish a simple and interpretable learning guarantee for KRR. As we can see in Corollary and Theorem 6, the effective ranks play crucial role in the analysis and tightly characterize the cost of overfitting in many settings.
An interesting future direction may be asking whether results extend other settings, such as kernel SVM, since our theory agnostic to target. We hope that the theory of KRR and ridge regression with Gaussian features can lead us toward better understanding of generalization in neural networks.
ACKNOWLEDGMENTS
This research was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of Deep Learning.

---

Published as a conference paper at ICLR 2024
REFERENCES
Francis Bach. High-dimentn dith-dimensional analysis of double descent for linear regression with random projections. arXiv preprint arXiv:230..01372, 2023.
Peter I., Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117745):30063-3077 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the bias varianar trade-off. Proceedings of the National Academy of Sciences, 116 152):15849-15854 2019.
Abdulkadir Canatar, Blake Bordelon, and Cengiz. Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):1-12, 2021.
Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint arXiv:2210.08571, 2022.
Konstantin Donhauser, Nicolo Ruggeri, Stefan Stojanovie, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effects of inductive bias. 2022.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the laplace and neural tangent kernels. Advances in Neural Information Processing Systems, 33:1451-1461 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1054, 2021.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of Stutistics, 2019.
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation, 100(1):78-150) 1992.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. Advances in Neural Information
Processing Systems, 2020.
Frederic Koehler, Lijia Zhou, Danica Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting. In Advances in Neural Information Processing Systems, 2021.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare 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.
Neil Rohit Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: taxonomy of overfitting. Advances in Neural Information Processing Systems, 2022.
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.
Gabriel C. Mel and Surya Ganguli. A theory of high dimensional regression with arbitrary correlations between input features and target functions: Sample complexity, multiple descent curves and hierarchy of phase transitions. In International Conference on Machine Learning, volume 139, pp. 2021.
James Mercer. Functions of positive and negative type, and their connection the theory of integral equations. Philosophical Transactions of the Royal Society of London, 209:4-415, 1909.
10

---

Published as a conference paper at ICLR 2024
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing. In International Conference on Computational Learning Theory, 2006.
Theodor Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv:2204. 10425, 2022.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 2020.
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 Learning Representations Workshop, 2015.
Dmitry Panchenko. Some extensions of an inequality of vapnik and chervonenkis. Electronic Communications Probability, 7:55-65, 2002.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics ridge(less) regression under general source condition. In International Conference Artificial Intelligence and Statistics, volume 130, pp. 3889-33997, 2021.
Shai Shalev-Shwatz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
James B Simon, Madeline Dickens, Dhruva Karkada, and Michael DeWeese. The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks. arXiv:21 2021.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss, 2010.
Alexander Tsigler and Peter I.. Bartlett. Benign overfitting in ridge regression. 2020.
Vladimir Vapnik and Alexey Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its applications, XVI(2):264-288 1971.
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum 11 11-norm interpolation of noisy data. 2021.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In International Conference Machine Learning. Proceedings of Machine Learning Research, 2022.
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regression. In Advances in Neural Information Processing Systems, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. On uniform convergence and low-norm interpolation learning. In Advances in Neural Information Processing Systems, 2020.
Lijia Zhou, Frederic Koehler, Danica J. Sutherland, and Nathan Srebro. Optimistic rates: A unifying theory for interpolation learning and regularization in linear regression. In ACM / IMS Journal of Data Science, 2021.
Lijia Zhou, Frederic Koehler, Pragya Sur, Danica Sutherland, and Nathan Srebro. A non-asymptotic moreau envelope theory for high-dimensional generalized linear models. In Advances in Neural Information Processing Systems, 2022.
11

---

Published as a conference paper at ICLR 2024
A SUPPLEMENTAL PROOFS
In the appendix, we give proofs of all results from the main text. Our proofs very self-contained and only use elementary results such as the Cauchy-Sehie Schwarz inequality.
A. UPPER BOUNDS
The main challenge for analyzing Eo from equation (5) is that the effective regularization Ko defined by the non-linear equation (4), which does not have simple closed-fone form solution. However, the following lemma can provide an estimate for Kg in terms of the effective rank.
Lemma 1. For any N4 it holds that
Eishde A
k & Tk
-1)
-1)
Kg
and Ro 2 Act1
(14)
Rs
n
Moreover, for any ho < n, holds that
-1
Eish
Ko <
1
Proof. From the Cauchy-Schwerr Schwwrz inequality, we show that
2
2
Σ A
= Σ
VolAi + KK)
d + K5u
A
Σ Ae i>
di + +
Ko
i>b
d
+ KD
n
Σ
K0
A
i>b
Rearranging in terms of ko proves the first incquality. Moreover, it holds that
A
X
n
Ai +
Ko
Ai +
iSk
i>k
kdR+1
Σisk X
Ap+1
Ki
Ak-1 + Ko
which can be rearranged to the second lower bound. Finally, observe that
A
Σise A
n1 Σ
k
+
Kig
and rearranging concludes the proof of the last inequality.
In particular, when there exists such that 1: o(n) and R₁ = w()). then ni R3 Eish Ai/n. Using lemma 1, we can show Theorem 2.
Theorem 2. For any io it holds that
k:
-2
Eo
1
1
(8)
71
R
12

---

Published as a conference paper at ICLR 2024
Proof. For any 2 0, by the definition (4), we have
8
X
Σ
Ki8
X
+
KS8
A
A K8
X +
Kg
i>k
A
kk +
Ai-
(ri + ki8)
i>k
Rearranging, we get
k
5.
X
(15)
Eisk
A
x8)?
At the same time, we can use the definition (4) again and (15) to show that
A
X
2
5
Σ
Σ
1,8
n1
12
d
+
Ki
Ai
+ 158
Aj
8
(16)
n
k&8)
K8
k
A
5
n
Eish di
1116
Plugging in 8 = 0 and Lemma 1, we have
1
Kig (n - k))
-11
k
-2
Eo 1
10
Σ iik d
=
1
R
provided that Rs T1.
Using the second part of equation (14), we can show similar bound that depends rk, which is smaller than Rg, but has better dependence k. Theorem 8. For any lo <, it holds that
-1
71
Eo S
+
Tk
+
Proof. For holds that X S dut1 and by Lemma we have
ktr
Ko
Ki
A + Ko
Ao+1 + Ko
ktrr
k + Tk
Finally, by equation (4), we have
1
X
Ko
E9
n
X; + Kg X + Ko
1
n
A
Kg 2 Kg
k+
n
1o + rk
Taking the inverse on both hand side concludes the proof.
Finally, we prove Theorem 4. The proof goes through a different argument to avoid the dependence on k/n because we might need to choose t = 2(n) when overfitting tempered.
13

---

Published as a conference paper at ICLR 2024
Theorem 4. Fix any n//r) and consider ki, Ru E N given by
h = max (k: 2 0: or S n)
k, min 2 (1 + c )
Then it holds that
Ak+1 AR+2
1 k
Eo - (1 c)²
max k
(11)
TTk
Proof. If < n/ro. then it clear that k 2 (1+c-) In satisfies + 2 (1+6-)) because гы 2 0. Then both ky and ky are well-defined. To show that both are finite, we observe that ky k + ETk, by definition and ky (1 ') because it is defined as the minimum k.
satisfies erg S is also clear that choosing
Next, let k' be the smallest integer such that λ&. I cRo. We will show that k* is also well defined and h E [kj + 2, ku + 1]. Note that for any h < n, we can apply Lemma to show
EiseA CRO n- n n
CTk
Ak+1-
Therefore, by our definition of ky and k", holds that Ak+t1 > END 2 AR= Since the eigenvalues are sorted, it must hold that k* > ki + 1. On the other hand, for any l E N. we also apply Lemma I to show
CRO 2 AktIc ( (k+ (k+rk-+
By our definition of ki and k", it holds that Ak I chi and so k' S ku + 1. Finally, since we have X A cKo for all 2 k2' and A CRi, we can check that
= 1 =-=11
1 Σ
1,0 Σ
X
() + Ko)²
K0
A
() + KO)² 2
12k
Eizk-- di -1--1
Σ
A> (1+
(1 + ))
A
12k"
Th
(1 c)²
Recall that An' - 12 kı + and so by definition of k1, we have A - 1 + er > n. Therefore,
holds that
Eo < (1 (1+ 1 - -1 erk-11
Pk- -
- 1kk" - 2) +
= (1 c1+
dp. E T2- -
where in the last step we use
Eishe
Σiske di
rk-
Ag--1
\
Ak+
Ax- -1-
The rest follows from the fact that k= 2 E [hit, ku - 1).
A.2 LOWER BOUNDS
We will now prove two lower bound for Eg.
14

---

Published as a conference paper at ICLR 2024
Theorem 3. Fix any b 0. If there exists i such that I k + brk, then let k. be the first such integer. Otherwise, pick = n. It holds that
1 Σ f% max
k n
b
k
1
(b+1)2
1)2
R
+ 1
n
Proof. First, suppose that there exists k < n such that n I k + br and let is be the first such integer. Then we can rearrange n S br into
Li>h> n
AR+1
and since A AR+1 for i > k. we apply the above and equation (14) of Lemma show that
A
E 2
Ai + Ko
i>k
Eisk X2
k Y2
1
(b En n-k
Ae) (b+ 1)2
R3
+
n
Moreover, by the definition of k. must have k - 1 + br which can be rearranged to
A Eisk-1i A k
bro
by equation (14) of Lemma again. Then for any S have 2 A bng and Ko < A1/b. Therefore, we have
Σ
A A
2 k
Kg
$Sk
Finally, if there no such k, then the first inequality is trivial. Moreover, we have n > n - 1 br
which rearranges to An 2 E X >> blg. Therefore, by all i n, we have X 2 A, > bko and
the rest of the proof is the same.
Theorem 5. For any & 2 n, it holds that
2
Σ
C7 2 k
(12)
k - n + Tk
Proof. By the Cauchy-Schwarz inequality, have
A
n
A
+
Ko
Kg
iSA
Σist A
A
Vk.
No
A + Kep
isk
By Lemma I, we have Kg 2 Ac+1
letre 1). Combine with above, we obtain
n
2
n
S
nTk
+ Vi
+ 2k n
A +
Kg
isk
Rearranging gives us
n
n
<
Σ
A
Vk k +
A; + Kgg
isk
which implies that
Σ 22 2 Σ
x;
k
A + Kip
k rk
11
i<k
15

---

Published as a conference paper at ICLR 2024
A.3 TAXONOMY OF OVERFITTING
Theorem 6. Suppose that the spectrum {Ai) is fixed as n increases and contains infinitely many non-zero eigenvalues.
(a) If lim k/Tk O, then overfitting is benign: limn-+oo Eo =
(b) If limg-soo k/rk E (0, oo), then overfitting is tempered: limm- Eg E o0).
(c) If lim k/rk = oc, then overfitting is catastrophic; lim Eo = 00.
Proof. We will show each clause separately.
(a) For any > O, we can pick = en in Theorem 2 and obtain the following:
(1 (1- 1
Eo s - c)²
Since we have
Σ x S Ak+1 Σ A
R& Tk: Tk:
1>k
1>*
we can send n - oo and k/ Rs S k
+ 0. Therefore, holds that
1
lim E n-000
61-
Since the choice of E >> can be made arbitrarily small, we have the desired conclusion by taking + 0.
(b) If [k/rr} converges non-zero constant, then the sequence must be bounded. In particular, there exists M > 0 such that T < kM for all k. we let = 1/(3M) in Theorem 3, then for all A n/2, it holds that
1 bM
2n n
k + br k(1+ + bM) -
S
< n
2
3
Then we need to choose h: n/2 in Theorem and
1
Σ 1,0 2
1
2(1 3M)
and so limn-+x0 E > 1. Similarly, there also exists > 0 such that rx mk for all k. Then by choosing
k I+m and Theorem 8, we have
A Eo S (1-=)
(1
n
22
1 mk
=
VT
<
oc.
(c) We will apply Theorem 5. For any
O, choose t: (1 E)n, get
2
Σ
2 1.0
1
Th +
n
1
h
Therefore, if = o(k), then
lim 000
1+c
However, since the choice of e arbitrary, then we can send e - The desired conclusion follows by En = (1 E, C3,0)
Remark 1. As mentioned in the main text, it is also possible to use Theorem 4 to show the upper bounds the proof of Theorem 6 above. For simplicity, we use a different argument here by applying Theorem 2 and 8.
16

---

Published as a conference paper at ICLR 2024
B UNIFORM CONVERGENCE
In this appendix, we show that the predictions from Simon et al. (2021) can establish type of uniform convergence guarantee known as "optimistic rate" (Panchenko, 2002; Srebro al., 2010) along the ridge path, which maybe of independent interest. We briefly mention the uniform convergence result in section the main text.
In particular, the tight result from Zhou et al. (2021) avoids any hidden multiplicative constant and logarithmic factor present in previous works and can be used to establish benign overfitting, However, their proof techniques depend on the Gaussian Minimax Theorem (GMT) and are limited to the setting of Gaussian features. We recover their result Theorem 7 here with a (non-rigorous) calculation that extends beyond the Gaussian case.
B. FORMULA FOR TRAINING ERROR AND HILBERT NORM
We first provide closed-form expression for the training error and Hilbert norm of fs. By the predictions from Simon et al. (2021), we know that
8²
R(fs)
R(fs)
n²K9
and we can use section 4.1 of Simon et al. (2021) to compute the expected Hilbert norm:
| +
Var[ó:]
1.fol =
A
)
R(f
C
1,80
+
X
C
i((fss)
C
A
A;
Therefore, will just the expression:
R(fa)
llfal
Σ
Σ
(17)
(Ax + ks))
n
(A4 + k
B.2 OPTIMISTIC RATE
Theorem 7. Fix any le N and let (K22 2km)/n². For any 8 2 O, it holds that
(1 - e) ---ey R((6)) v (((a))s s Eis l
Proof. Applying equation (6) and (4), we can write the difference
(i( 1-o--Vick RR(f)) =
8
Vi((fa)
A
Vi(fo).
n
Ao + Ki6
17

---

Published as a conference paper at ICLR 2024
By the Cauchy-Schward inequality, for any & N, we have
2
2
Σ
A
X
-
k
A + Ki8
+
Ki
i>k
k.2 + 2k
Σ
di
Kig
X3 + Kis
S 22 + +km +
A (Ar + K38)
ΣN
Link
By the expression (17), we have
-
k.2 + 2km
i((f))
A (Ai + kz)? )2
(+ Ne E>k
RR(fs)) +
n²
1>k
22 + 2km
[I.fa 7
(Eised)) Ar)
R(fs))
n²
n
Vo, show that then using v S vx
v /M(fa) v (((fs) s
k2 + 2kn R((
(Eisa Ar)
+
n2
T
122 + 2kn
llfalliee (2isk Ar)
R((6)) +
n2
n
Rearranging concludes the proof.
B.3 NORM ANALYSIS
Theorem 9. For any I E U {00} and k E N such that R2 > n, it holds that
n (0² + Eisi
+ 1 Rs
Eisk di
Proof. When d holds that
Eei
Σ
A
X? (Ar + ko)²
E
d + Kg
Kig Σ + k0)
X;
by applying (5) and (4). Therefore, the second term in (17) can be simplified as
R(f())
d = Eo (E, (1 - 2o? + 0²) n
Σ E2 no)²
Eoro
(1 L
0²
No
K0
Σ
Kg
0
1/
(A: + Ki
K0
by the definition in (6). Plugging in, we arrive at
?
l = Σ
\ + Ko
K0
18

---

Published as a conference paper at ICLR 2024
To handle situations where f is not in the RKHS, observe that for any I, we have
Σ
d + Kg
+
K0
+
Kg
i
i>!
i
i>!
and
1
a²
1/
X
Ko
The proof concludes by plugging in Lemma 1.
Finally, we can plug in the norm bound of Theorem 9 into Theorem establish benign overfitting. as in Koehler et al. (2021); Zhou et al. (2022).
Corollary 2. For any E N U {oo} and k E N such that (k/n)² - 2(k/nn < and Rs > n. Let = (k2 + 2kn)/n², then it holds that
(Eish Ar) (Eisi
+ +(1-
-1
(1 c))o))((f)) -
n1
1/
2
(18)
n
R
i>!
19


Reviews:
[{"review_id": "z0LlhCEwn2", "reviewer": "Reviewer_pfdC", "summary": "This work study the cost of over fitting in kernel ridge regression. It is reflected by the ratio of the test error without regularizer and the optimally tuned model. It provides the necessary and sufficient conditions of three types of overfitting, benign overfitting, tempered overfitting, catastrophic overfitting. The analysis is under an “agnostic” view.", "questions": "1. Theorem 2 and 3 depend on $R_k$, while Theorem 4, 5, 6 depend on $r_k$. What’s the connection of these results, or are they independent?\n\n2.  Although assumption 1 is commonly used in the literature, I’m still curious whether the analysis can work for some different assumptions. What key property of the Gaussian distribution is used in the proof?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The work is well organized. It studies three types of overfitting: benign overfitting, tempered overfitting, and catastrophic overfitting separately.\n\n2. The work proves matching upper and lower bounds. It gives a necessary and sufficient condition, dependent on the effective ranks of the covariance matrix, $\\lim_{k\\rightarrow \\infty} k/r_k$, to determine whether the overfitting is benign, tempered, or catastrophic. This resolves an open problem in Mallinar et al. (2022)\n\n3. The work provides several concrete examples to exhibit how their results work.", "weaknesses": "1. For people unfamiliar with the literature, some concepts are hard to understand, for example,  “omniscient risk estimate” and the “cost of overfitting.” Can you provide more intuition about these parts?\n\n2. This work focuses on the specific problem of linear ridge regression. The analysis highly depends on the concrete structure of this problem. It might be hard to generalize to other problems of interest.\n\n3. For a purely theoretical paper, this work provides its main results directly, without mentioning the techniques or the difficulty of the proof. Highlighting the techniques used can help the readers understand this paper's technical contribution. For example, when comparing with Bartlett et al. (2020), the paper says, \"Our proof technique is completely different and simpler since we have a closed-form expression.\" This, however, is not helpful enough because it does not provide any equation or concrete comparison to show what the closed-form expression is and where the key difference is.", "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": "MDnFe5q02i", "reviewer": "Reviewer_mrDt", "summary": "This paper studies the cost of not regularizing in kernel ridge regression. Suppose you draw some data iid from a distribution, and build a kernel matrix for this data. We could then consider two different Kernel Ridge Regression (KRR) estimators that we learn from this data:\n1. The KRR estimator with the best possible regularization (this minimizes the true population risk)\n2. The KRR estimator with zero regularization (this minimizes training set error)\n\nThe paper asks when the second estimator, which has zero training error because it overfits the training data, has similar true population risk as the first (and statistically optimal) estimator. Specifically, the paper is interested in bounding the ratio of these risks:\n$$\n\\text{ratio} = \\frac{\\text{Risk of unregularized model}}{\\text{Risk of perfectly regularized model}} \\geq 1\n$$\n\nThe paper is interested in the _agnostic_ setting, where we do not assume that the labeled data points are generated, or even well approximated, by a KRR estimator. Specifically, suppose we fix a distribution over input features $x$ (and hence a fixed distribution over kernel matrices) and are allowed to vary the conditional distribution of labels $y | x$. Then, **what is the maximum value that the above ratio can take?**\n\nThe paper provides bounds on this maximum ratio, denoted $\\mathcal{E}_0$. At the core of the paper is Theorem 6, which provides a tight characterization for which kernels have a benign, tempered, or catastrophic concern about overfitting:\n- Overfitting is _benign_ if this worst-case ratio has $\\mathcal{E}_0 \\rightarrow 1$ as the sample size $n\\rightarrow\\infty$\n- Overfitting is _tempered_ if this worst-case ratio has $\\mathcal{E}_0 \\rightarrow c>1$ as the sample size $n\\rightarrow\\infty$\n- Overfitting is _catastrophic_ if this worst-case ratio has $\\mathcal{E}_0 \\rightarrow \\infty$ as the sample size $n\\rightarrow\\infty$\n\nFinite sample guarantees are also given throughout the paper, and those theorems are the focus of the paper. Though, Theorem 6 above, conveys that message most concisely.\n\nThe paper is purely theoretical, and has no experiments.", "questions": "These are really small questions or recommended edits. You don't need to respond to these; make these edits if you want to.\n\n1. [page 2] It feels weird to call (4) representer theorem. It's really just like kernel ridge regression. In my mind, the second line of equation (7) feels more like a representer theorem. This could just be a difference of perspective though.\n1. [page 3] I have no idea what spherical harmonics or the Fourier-Walsh (parity) basis are, nor how they apply here. I'd cite something here.\n1. [page 3] The omiscient risk estimate and equations (8) and (9) remind me of various ideas from various papers not discussed here. You don't need to discuss them, but I figured I should mention them since they seem relevant:\n    - The effective regularization constant seems similar to the parameter $\\gamma$ in equation (2) on page 3 of _[Precise expressions for random projections: Low-rank approximation and randomized Newton](https://arxiv.org/pdf/2006.10653.pdf)_\n    - The $\\mathcal{L}\\_{i,\\delta}$ values seems to be exactly _ridge leverage scores_, so that for instance $\\sum\\_i \\mathcal{L}\\_{i,\\delta}$ is the intrinsic dimension of the kernel. See eg _[Fast Randomized Kernel Ridge Regression with Statistical Guarantees](https://proceedings.neurips.cc/paper_files/paper/2015/file/f3f27a324736617f20abbf2ffd806f6d-Paper.pdf)_ or _[Fast Randomized Kernel Ridge Regression with Statistical Guarantees](https://arxiv.org/pdf/1511.07263.pdf)_ or _[Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://arxiv.org/pdf/1804.09893.pdf)_.\n1. [page 4] For reader like me, who forget what pareto-optimal is, move the parenthetical \"(point on the regularization path)\" earlier in the paper to the first use of the word \"pareto\"\n1. [page 5] The statement that $k = o(n)$ and $R_k = \\omega(n)$ is one condition, not two. It's not well defined to say that $R_k = \\omega(n)$ without a notion of how large $k$ is. Really, this statement is \"$R_k = \\omega(n)$ for some $k = o(n)$\", which is clearly a single condition.\n1. [page 6] At the end of example 1, explicitly note that $\\mathcal{E}_0 \\rightarrow 1$.\n1. [page 7] It's kinda weak that the tempered overfitting doesn't have any matching lower bound part. We are already given the freedom to pick a really adversarial $y|x$ distribution, so it'd feel much more satisfying if the example could fully indulge a proof that $1 < \\lim_{n\\rightarrow\\infty} \\mathcal{E}_0 < \\infty$. This might be hard, but it'd be a good payoff for strengthening the paper.\n1. [page 8] Theorem 6 should be MUCH EARLIER in the paper. It's really clean and is nice to glance at and understand. It would be nice to first see this limiting result, and then see the finite-sample complexity statements that make it up. We could also then always compare a finite sample complexity result back to Theorem 6 from the (eg) introduction, making everything feel more soundly tied together into a comprehensive story.\n1. [page 8] I'd change the language a bit in the theorem to recall that $\\mathcal{E}_0$ is a worst-case across all $y|x$:\n    - _then overfitting must be benign_\n    - _then overfitting can only be tempered_\n    - _then overfitting can be catastrophic_\n\n    These phrases make it clear that, eg, $\\mathcal{E}_0 \\rightarrow 1$ means that you must always be benign while $\\mathcal{E}_0 \\rightarrow 3$ means that some $y|x$ can achieve this $\\text{ratio}$ of 3 but not that all $y|x$ distributions must do this.\n1. [page 8, just above \"inner-product kernels\"] What is $\\mathcal{D}$?\n1. [page 8, equation (20)] What is $\\mu_{d,k}$?\n1. [page 8, below equation (20)] What does i mean for the eigenvalues a matrix to have block-diagonal structure? The eigenvalues don't define a matrix.\n1. [page 8, equation (22)] How does this bound on $R_k$ translate to a sufficiently tight bound on $r_k$? If $R_k = \\omega(n)$ then we only know that $r_k = \\omega(\\sqrt{n})$, right?\n1. [page 8, below equation (22)] Where and why do we need $\\ell$ to be bounded away from being an integer?\n1. [page 9, before \"conclusion\"] Spell out how these limits in this last paragraph imply that you're in the benign regime.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper asks and interesting questions and formalizes this question nicely. Understanding the worst-case values of this $\\text{ratio}$ across all conditional distributions $y|x$ is a good framework. The question carries sufficient significance in producing a fairly thorough understanding of a fundamental ML task (KRR) with and without regularization.\n\nThe paper makes a good effort in making the story of the results pretty clear -- we start with a naturally interesting problem, formalize it mathematically, apply a reasonable approximation and assumption, and then tackle benign, tempered, and catastrophic overfitting. The fairly mathematical results are presented nicely, which short theorem statements and clearly worked out examples demonstrating the impact of the theorems. While I sometimes wish the intuitive takeaway of these theorems was more clearly discussed, the many rigorous theoretical examples were nice to see worked out.\n\nAll of this is well executed, and piles up enough for the paper to earn a weak accept.", "weaknesses": "### Overview\nThe paper has some presentation and significance issues. I'll give my opinions and thoughts at the top of this box, and back it up with evidence at the bottom of this box.\n\nFor significance, the worst-case bounds achieved in this agnostic model are tight only in unrealistic cases. Specifically, the worst-case ratio $\\mathcal{E}_0$ should only be representative of the $\\text{ratio}$ for a real ML task if the Bayes-Optimal estimator is the always-zero function.\n\nIt's understandable and reasonable that we give guarantees in the worst case, but the fact that the worst-case is achieved by an unrealistic setting means that I'm skeptical that this theory can precisely characterize when overfitting actually is benign or catastrophic. The result is nice either way, but any practical takeaways will further require understanding the gap between $\\mathcal{E}_0$ and $\\text{ratio}$. This harms significance, but is not a deal breaker.\n\n\n$\\phantom{.}$\n\nThe paper also suffers from a lack of clear discussion of the mathematics involved. This is felt in two key ways: there are no proof sketches or intuitive justifications for why the theorems should be true; and there are no good intuitions given for key mathematical properties of a kernel used in the theorems. The lack of proof sketches harms my confidence that the results are correct, but frankly the results feel believable, so I'm not really marking down a lot here (though the paper would be significantly improved from just a bit of discussion of what the proofs look like).\n\nThe really painful point here is about the **Effective Rank** of a matrix. On page 5, Definition 2 introduces the values $r\\_k$ and $R\\_k$, both called the _effective rank_ of a matrix. $r\\_k$ and $R\\_k$ can differ by upwards of a quadratic factor, but no intuitive understanding of the difference between these definitions is given. Further, it's not even clear why we call these \"ranks\" -- usually the rank of a matrix has no notion of starting to count only from the $k^{th}$ eigenvalue.\n\nTheorems throughout the paper depend on both $r\\_k$ and $R\\_k$, though $r\\_k$ appears more often. I have no understanding of what these value really mean, so when I see Theorem 6 on page 8, I'm not really clear what's going on. This theorem me if our kernel matrix lies in the benign or tempered or catastrophic setting, depending on the limit $\\lim\\_{k\\rightarrow\\infty} \\frac{k}{r\\_k}$. Is this limit a way of characterizing the rate of decay of a spectrum? What kinds of spectra ___intuitively___ make this limit large or small?\n\nThis lack of discussion really hurts the clarity of the takeaway from the paper.\n\n---\n\n### Evidence\n1. $\\mathcal{E}_0$ _only matches_ $\\text{ratio}$ _if the optimal KRR estimator is the always zero estimator_:\n\n    This follows from the top of page 5, before equation (11). This paragraph says that $\\text{ratio} = \\mathcal{E}_0$ if we have $v_i = 0$ for all $i=1,...,\\infty$. Here, $v_i$ is the $i^{th}$ coefficient in the expansion $f^*(x) = \\sum\\_{i=1}^\\infty v_i \\phi_i(x)$ where $f^*$ is the Bayes-optimal estimator and $\\phi_i$ is a function in the Mercer-theorem-decomposition of the kernel function. Essentially, since $v_i=0$ for all $i$, we get that $f^*(x)=0$ everywhere, and hence that $\\mathcal{E}_0 = \\text{ratio}$ only if the Bayes-Optimal estimator is always zero.\n\n2. _There are no proof sketches_:\n\n    This is in all of the theorems except Theorem 1, which is proven in the body of the paper. Theorems 2 and 3 on page 5 are good examples though. It's just a theorem statement with discussion of the implication of the theorem. No justification for the correctness of the theorem is given.\n\n3. _$r\\_k$ and $R\\_k$ can differ by upwards of a quadratic factor._\n\n    See page 5, just below equation (13)\n\n4.  _Usually the rank of a matrix has no notion of starting to count only from the $k^{th}$ eigenvalue._\n\n    This even holds for \"smooth\" notions of the rank of a matrix, like the intrinsic dimension $tr(K(K+\\lambda I)^{-1})$ or the stable rank $\\frac{\\tr(A)}{\\|\\|A\\|\\|_2}$.", "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": "0fRhIRouWz", "reviewer": "Reviewer_avrM", "summary": "This paper focuses on focuses on studying the cost of overfitting in noisy kernel ridge regression. The authors define this cost as the ratio of the test error of the interpolating ridgeless model to the test error of the optimally-tuned model. The approach is agnostic and provides a more refined characterization of benign, tempered, and catastrophic overfitting.", "questions": "The insights derived about overfitting in kernel ridge regression present significant theoretical understanding. How can these insights be effectively applied or adapted to other prevalent machine learning models and algorithms, such as neural networks or support vector machines? \n\nYour paper shares some commonalities in terms of quantitative aspects with the study by Bartlett et al. (2020). Could you elucidate the key differences in your analysis compared to Bartlett et al.'s work? Additionally, during your analytical process, what were the most significant challenges encountered, and how did these differ from the challenges faced in the Bartlett et al. (2020) study?\n\nThe paper seems to be closely related to [1], which establishes a connection between the benign overfitting observed in ridge regression and that in SGD. Could the authors comment on the relationship/difference with [1]?\n\n[1] Zou, et al. \"Benign overfitting of constant-stepsize sgd for linear regression.\" Conference on Learning Theory. PMLR, 2021.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors offer an intricate and comprehensive examination of closed-form risk estimates in kernel ridge regression (KRR), along with a nuanced analysis of the conditions that lead to overfitting being benign, tempered, or catastrophic. The utilization of Mercer’s decomposition and the application of bi-criterion optimization within the KRR framework are particularly notable aspects of the study. Additionally, the paper is well-organized, presenting its complex ideas in a coherent structure. The inclusion of specific, practical examples to illuminate the theoretical concepts significantly enhances the paper’s clarity.", "weaknesses": "The paper maintains a highly specialized focus, concentrating predominantly on kernel ridge regression. This narrow scope raises questions about the generalizability of its findings to other model types, such as kernel SVM, which may not align precisely with the conditions and scenarios discussed. Despite its comprehensive and in-depth theoretical analysis, a notable limitation is the absence of empirical validation. The inclusion of studies utilizing synthetic or real-world data to substantiate the theoretical claims would greatly enhance the robustness and applicability of the paper's conclusions.", "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": "DgWm61vJSI", "reviewer": "Reviewer_oHx9", "summary": "This paper studies overfitting of kernel ridge regression (KRR) through the so-called prediction of the cost-of-overfitting:\n$$\n\\tilde{C}(\\mathcal{D},n) = \\frac{\\tilde{R}(\\hat{f}\\_{0})}{\\inf\\_{\\delta>0}\\tilde{R}(\\hat{f}\\_{\\delta})}\n$$\nwhere the input has size $n$ drawn from the distribution $\\mathcal{D}$ ; and $\\hat{f}\\_\\delta$ denotes the KR regressor with ridge $\\delta>0$; $\\tilde{R}(\\hat{f}\\_{\\delta})$ is an estimation of the KRR test error. Hence the metric $\\tilde{C}(\\mathcal{D},n)$ measures the ratio of the test error of the RKHS interpolant to the optimal regularised regressor and hence has range $(1,\\infty]$. \n\nThis paper derives non-asymptotic bounds on the cost-of-overfitting which are independent to target function and hence agnostic. As $n\\to\\infty$, these bounds recover the classification result of overfitting from [Mallinar2022]. \n\nThe paper is built upon the (maybe too idealised) Gaussian Design ansatz and the test error estimation result from [Simon2021], and aims to shade light to realistic scenarios of kernel training.", "questions": "I think the weakness I stated above is unavoidable. But if we do not focus on the cost-of-overfitting but its prediction (definition 1), every proof is rigorous and correct. The only question would be the non-rigorous prediction $C(\\mathcal{D},n)\\approx\\tilde{C}(\\mathcal{D},n)$. It would be nice if there is at least some experimental results supporting it.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Originality: This paper is the first paper combining the insight from [Simon2021] and the idea from [Barlett2020] to derive a refined proof for [Mallinar2022]. \n\nQuality: The paper offers an elegant proof with detailed motivation for the definitions and intuition for the formulae, and extends the results from previous work. I have checked the proofs in details. It seems that they are all correct and I cannot see any typos from the paper.\n\nClarity: Definitions, theorems and proofs are clearly stated. Notations are standard and clean. Paper is easy to follow.\n\nSignificance: The simple and elegant argument surely serves its purpose in machine learning theory. The agnostic point of view about overfitting is also insightful for any future study.", "weaknesses": "The only potential flaw that I can see is the use of the result from [Simon2021]. Although the Gaussian Design Ansatz is widely accepted in machine learning theory, the equation (10) comes from [Simon2021] which used the rotational invariance of Gaussian, which seems to be too strong for realistic case. I wonder, if the argument of this paper can still be applicable in more realistic setup. \n\nAs stated in the abstract :\"We analyze the cost of overfitting under a Gaussian universality ansatz using recently derived (non-rigorous) risk estimates in terms of the task eigenstructure.\" I guess that this is addressing the use of the result from [Simon2021], which was rejected by a conference before.", "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)