An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression

We thank the reviewer for their favorable evaluation!

Regarding the reliance on the results of Simon et al. (2021): We note that the framework we take as our starting point is not only due to them: the KRR generalization equations we use (Eqs. 8-10 in our work) are obtained also in the seven other works cited at the top of Section 2.3, all of which have appeared in major peer-reviewed venues. Some of these, including Hastie et al. (2019), permit the data to be slightly different from Gaussian (e.g., covariates independent and sub-Gaussian), which is a bit weaker than a strict Gaussian design ansatz, but still a strong assumption. We will reword to make it clearer that these works are also sources for the framework.

Regarding the use of the Gaussian design ansatz (GDA) at all (or perhaps some slightly weaker cousin): while we agree that one would ideally avoid its use, the GDA has become a standard part of the ML theory toolkit because (a) predictions generated using the GDA often match real, non-Gaussian experiment remarkably well, and (b) the GDA permits one to obtain sharp closed-form expressions in many cases. To our knowledge, no starting assumption for the feature distribution of KRR which is both more realistic and equally tractable is known.

To the reviewer’s question regarding experimental results for the Gaussian equivalence approximation, we note that prior works give thorough empirical verification of the claim that $R(\hat{f_\delta}) \approx \tilde{R}(\hat{f}_\delta)$. Among those we cite at the top of Section 2.3, in particular, Jacot et al (2020), Canatar et al (2021), Simon et al. (2021), and Wei et al (2021) give experimental results for this claim.

Thanks for your feedback!

Regarding the focus on (kernel) ridge regression: Indeed, as with other prominent papers on interpolation learning, we focus on ridge regression. Ridge regression is both a fundamental and important problem in its own right, and also seen by the community (and by us) as an important “base case” to study in understanding interpolation learning. Extending the analysis from l2 regularized regression (as in this paper) to l2 regularized large-margin classification (as in SVMs) would be interesting and indeed non-trivial, in the same way that extending previous non-agnostic analysis from ridge regression to large margin classification was.

Regarding the questions:

• Our results can be applied to understand overfitting with neural networks in the kernel regime. As discussed in, e.g., Mallinar et al. (2022), prior work showed that the spectrum of ReLU NTKs has the same decay rate as the Laplace kernel, namely, power law decay. As we show in Example 4, it implies that the NTK exhibits tempered overfitting. We will add a remark on this issue.
• Difference from Bartlett et al. (2020): The fundamental difference, which we discuss in the introduction, is that our work takes an agnostic view and directly studies the cost of overfitting by comparing an interpolating predictor to a non-overfitting ridge predictor, instead of focusing on consistency as in Bartlett. One implication of this view is that our technical requirements that allow for benign overfitting are weaker than the requirements from Bartlett et al. (see the discussion in page 5 after Theorem 2). Moreover, a major contribution of our work is the characterization of benign/tempered/catastrophic overfitting using the ratio $k/r_k$. Such a characterization did not appear in previous works. Our proof technique is different from Bartlett et al., since we rely on the estimate from Eq. (10) and they relied on a more direct analysis.
• The work [1] characterized benign overfitting in SGD and compared it to ridge/ridgeless regression. Still, the conceptual differences between our work and Bartlett et al. which we discussed above apply also in comparison to [1].

Thanks for your feedback! Your comments will greatly help us in improving the paper.

Criticism: The worst-case bounds achieved in this agnostic model are tight only in unrealistic cases.

Our Response (elaborated below): This is not the case. They are per-instance tight much more generally, qualitatively per-instance tight in broad generality, and since they are worst-case tight they also shed light on what can be said only based on the data distribution.

Elaboration: It is true that in the paragraph you mention, at the top of page 5 (we assume you meant before eq 12, rather than before eq 11), we give the signal-less case ($v_i=0$) to argue tightness. But this is not necessary for tightness, it is merely the easiest argument to show the worst-case tightness in (12). We regret that this created an impression as if this is the only situation where $\tilde{C} \geq \mathcal{E_0}$. In fact, in the paragraph following (12) we provide a lower bound we should have emphasized much more: $\tilde{C} \geq \mathcal{E_0} \frac{\sigma^2}{\tilde{R}(\hat{f}_{\delta^*})}$.

This shows that $\tilde{C} \rightarrow \mathcal{E_0}$ (i.e. $\mathcal{E_0}$ precisely captures the cost of overfitting) whenever $\tilde{R}(\hat{f}_{\delta^*}) \rightarrow \sigma^2$, i.e. whenever optimal tuned ridge is consistent (approaches the Bayes error). Thus, the upper bound is tight much more generally (recall that much of the prior literature focuses on such a consistent setting, and that this is also generically the case when $n\rightarrow\infty$ while the source distribution is fixed). We should have said this explicitly and emphasized this.

It is true that when $\tilde{R}(\hat{f}_{\delta^*}) > \sigma^2$, i.e. optimal tuned ridge is far from Bayes optimality, we could have $\mathcal{E_0}$ be a loose upper bound on $\tilde{C}$. But even in this case, $\mathcal{E_0}$ still captures the qualitative (if not quantitative) noisy overfitting behavior in the following way:

• If $\mathcal{E_0} = 1$ we have benign overfitting ($\tilde{C}=1$) regardless of the target, since $\tilde{C} \leq \mathcal{E_0}$ for any target.
• If $\mathcal{E_0} \to \infty$ and $\sigma^2>0$ then we have catastrophic overfitting ($\tilde{C}\to\infty$) regardless of the target, since $R(\hat{f}_{\delta^*}) < \infty$ and

$\tilde{C} \geq \mathcal{E_0} \frac{\sigma^2}{\tilde{R}(\hat{f}_{\delta^*})}$.

• If $1 < \mathcal{E_0} < \infty$ and $\sigma^2>0$, then overfitting is either benign or tempered ($1\le\tilde{C}<\infty$), since $\tilde{C} \leq \mathcal{E_0}<\infty$.

All the above is independent of the target, as long as $\sigma^2>0$ (ie we are in a noisy setting, which is where we typically talk about overfitting). Thus, $\mathcal{E_0}$ does capture the qualitative overfitting behavior (up to the indistinguishability of benign and tempered fitting in the third case). This discussion should of course be much more explicit in the paper.

Finally, according to eq (12), $\mathcal{E_0}$ is the tightest possible “agnostic” bound on $\tilde{C}$. i.e. that does not depend on the target $f_*$ but only on the data distribution. Part of the goal of the paper is to study just how much such an agnostic view can characterize overfitting behavior, and this is the answer—it’s tight in some senses (discussed above), but is inherently not tight in a generic quantitative sense (and this is just reality, it is not due to loose analysis).

Disclaimer: all the above discussion is of course based on the eigenframework and valid under it.

Lack of clear discussion of the mathematics involved. The formal proofs are indeed a bit technical, and follow by analyzing the estimate from Eq. (10). We will try to add more intuitive explanations in the main text.

Regarding the comment on the effective ranks. In our work, we used the definitions from the seminal work of Bartlett et al. (2020), which were also used in many other works on benign overfitting. The term “effective ranks” is used in the literature to describe these quantities. We understand your criticism regarding this term, but we preferred to be consistent with prior works. Perhaps a better way to write the limit $\lim_{k \to \infty} \frac{k}{r_k}$ that avoids $r_k$ altogether is:
$\lim_{k \to \infty} \frac{k \lambda_k}{\sum_{i>k} \lambda_i}$
This perhaps gives a better intuitive sense of how spectral decay controls $\mathcal{E_0}$ and thus overfitting behavior.

We thank you for the additional questions and recommended edits, and we will address them in the final version.

Thanks for your feedback!

Regarding the weaknesses:

1. Regarding giving more intuition on terms used: As we mention in footnote 2, “omniscient risk estimate” is just a term that Wei et al. (2022) gave to the estimate which we provide in Eq. (10). The “cost of overfitting” is the main new concept we introduce: it is defined formally in Definition 1, and intuitively it compares a predictor which is obtained as a result of extreme overfitting and interpolation to the “optimal” non-overfitting predictor, and thus captures the “cost” (in terms of test error blow-up) of this overfitting.
2. As with many other recent papers on interpolation learning (including some very high profile papers), we focus on ridge (and kernel) regression. Ridge regression is a fundamental and important problem in its own right, and also seen by the community (and by us) as an important “base case” to study in understanding interpolation learning, even if specific techniques will not generalize to other problems. Indeed, the specific way we bound the “cost of overfitting” might not generalize, but a major contribution here is introducing an agnostic view of studying overfitting/interpolation and defining the “cost of overfitting”, and we believe strongly that this approach is very relevant much more generally.
3. The proofs follow by analyzing the estimate from Eq. (10), which gives a closed-form expression for the risk. We will add a short discussion about it.

Regarding the questions:

1. These results are not directly comparable, except for the fact that we can use the relationship $r_k \leq R_k \leq r_k^2$ which we mention in page 5 after Eq. (13).
2. Strict Gaussianity isn’t actually required – the same eigenframework holds for a variety of distributions that are “close enough to Gaussian” (e.g. sub-Gaussian covariates, or “random-looking” feature vectors that satisfy some delocalization property). The key intuition is that these distributions form an equivalence class in that all are asymptotically described by the same eigenframework. The Gaussian distribution just happens to be the member of this class which is easiest to work with, so it is canonically chosen as the defining member. Empirically, it appears that feature distributions in real kernel tasks also lie in this Gaussian equivalence class (or at least close to it). This seems reasonable, but it is not yet understood why this is.