Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality

Summary

This paper concerns the overfitting behaviour of Gaussian kernel ridge regression (KRR) with varying bandwidth or dimensionality. The contribution is two-fold: 1. In fixed-dimension, the ridgeless solution of Gaussian KRR is not consistent with any varying or tuned bandwidth. 2. In high dimension with input dimension $d=2^{2^l}$, sample size $m=2^{2^{2^l}}$ for any arbitrary integer $l$, the overfitting of Gaussian KRR is benign. All the results are under the Gaussian universality Ansatz and the (non-rigorous) risk predictions in terms of the kernel eigenstructure introduced in [Simon2023]. Reference: - James B. Simon, Madeline Dickens, Dhruva Karkada, and Michael R. DeWeese. The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks. arXiv preprint arXiv:2110.03922, 2021.

Strengths

The two contributions are novel.

Weaknesses

However, I have serious concerns about the assumptions made in this paper. Firstly, the eigenframework under the Gaussian Universality Ansatz (GUA) is non-rigorous and actually fails to explain the catastrophic overfitting of NTK in fixed dimensions, as reported in \cite{Barzilai2023} and \cite{Cheng2024}. I am uncertain whether benign overfitting would still hold in high-dimensional settings. This paper does not offer experimental validation either, so I cannot ensure the correctness of the claim for Gaussian kernels (not its proxy under GUA). Secondly, the catastrophic overfitting of Gaussian kernels with fixed bandwidth is well-known. It is not difficult to imagine that Gaussian KRR with varying bandwidth remains inconsistent. While the first contribution of this paper is novel, I question whether it is significant enough for paper acceptance, especially given my concerns regarding the second contribution. Reference: - Barzilai, Daniel, and Ohad Shamir. "Generalization in kernel regression under realistic assumptions." arXiv preprint arXiv:2312.15995 (2023). - Cheng, Tin Sum, et al. "Characterizing overfitting in kernel ridgeless regression through the eigenspectrum." arXiv preprint arXiv:2402.01297 (2024).

Questions

The most important question would be if the authors could provide some experimental validations on these two claims.

Rating

3

Confidence

4

Soundness

2

Presentation

3

Contribution

1

Limitations

All assumptions are stated in the claims. However, as mentioned before, GUA and Eigenframework assumptions are too unrealistic and might provide wrong results.

Summary

This paper discusses the generalization ability of Gaussian kernel interpolation, an interesting topic. However, the authors sidestep the most challenging part by assuming the 'Gaussian universality ansatz,' which significantly simplifies the problem. With this assumption, their work essentially consists of elementary computations. Furthermore, their argument heavily relies on the earlier work by Lijia Zhou, James B. Simon, Gal Vardi, and Nathan Srebro, titled 'An agnostic view on the cost of overfitting in 473 (kernel) ridge regression,' an arXiv preprint with the identifier arXiv:2306.13185, published in 2023."

Strengths

A detailed calculation of the eigenvalue structure of the Gaussian kernel with various bandwidths has been performed. This could be valuable for future studies.

Weaknesses

No significant contribution was made to the kernel interpolation problem itself. The major workhorse was developed in earlier work by Lijia Zhou, James B. Simon, Gal Vardi, and Nathan Srebro, as detailed in their paper titled 'An agnostic view on the cost of overfitting in 473 (kernel) ridge regression,' published as an arXiv preprint with the identifier arXiv:2306.13185 in 2023.

Questions

Perhaps due to my lack of knowledge, could the author elaborate on their contributions beyond the detailed computation of the Gaussian kernel with varying bandwidths?

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

None.

Summary

This paper looks at the problem of kernel (ridgeless) regression with Gaussian kernel and data on a sphere. The paper studies two cases, first we fix the dimension $d$ and are allowed to send the number of data points $m \to \infty$ and the width of the kernel $\tau_m \to 0$, second, we are allowed to scale $d$. For both problems they study how a quantity known as the predicted risk scales. *It is important to note that the paper assumes that this is a good estimate of the true excess risk, which is not immediately evident and I think requires more justification (see weaknesses).* In the first case they show that if $\tau_m$ goes to zero too quickly, we have tempered overfitting for the *preditcted risk* and that it has a worse risk than the null estimator. If it goes to 0 too slowly, then we have catastrophic overfitting for the *predicted risk*, and that if it goes to zero at the appropriate rate, we have tempered overfitting again and that we may outperform the null estimator. The paper also presents some results about the case when $d$ scales as well.

Strengths

The paper uses the predicted risk as an estimate of the true risk. The prdicted risk is given by $$ \tilde{R}(\tilde{f}\_{\delta}) = \mathcal{E}\_\delta \left(\sum\_{i=1}^\infty (1-\mathcal{L}\_{i,\delta})^2 \beta_i^2 + \sigma^2 \right) $$ Where $\beta_i$ are the coefficients of the target function in the eigenbasis of the kernel function and $\mathcal{E}, \mathcal{L}$ are coefficients based on eigenvalues and $\sigma^2$ is the noise variance. *If we assume that this is a good estimate of the excess risk*. Then to understand the risk, we have reduced the problem to understanding how $\mathcal{E}, \mathcal{L}$ **and** $\beta_i$ scale. **This paper studies how $\mathcal{E}_0$ scales by providing some bounds on the eigenvalues of the Gaussian kernel function. This I think is the primary contribution of the paper.** However, there are some issues, see weaknesses.

Weaknesses

There are a few weaknesses. The current reject score is due to my concerns with the proofs. 1) **Theorem 1** I have some concerns with the results in Theorem 1. Theorem 1 states that unless we meet some very specific conditions, the null predictor (i.e. the zero function) outperforms kernel ridge regression. This seems quite surprising to me. Taking a closer look at the proof, we see that proof is broken down into two Lemmas. One proves the upper bounds, the other lower bounds. However, Lemma 1, only deals with $\mathcal{E}_0$. However, I think something has to be said about $\sum\_{i=1}^\infty (1-\mathcal{L}\_{i,\delta})^2 \beta_i^2$. If I understand correctly, when we change $m$, we change the width, which changes the kernel function. However, since $\lambda_i$ and $\phi_i$ are the dependent on $K$. Hence $\beta_i$ which are the coefficients of $f$ in this eigenbasis are dependent on $m$. Hence $\sum\_{i=1}^\infty (1-\mathcal{L}\_{i,\delta})^2 \beta_i^2$ has a subtle dependence on $m$ which I think needs to be accounted for. Because apriori it is not clear to me that this is bounded in $m$. That is, $\sum_i \beta_i^2(m) = S(m)$ could be unbounded in $m$. I did not go through the lower bound proofs as carefully, but I do think the the dependence of $\beta_i$ on $m$ is addresses. Please correct me if I am wrong. Hence I think either another assumption needs to be added (and if it is added a discussion of its reasonableness would be appreciated) or that terms needs to be explicity dealt with. 2) Eigenlearding Framework and Predicted Risk In general, I would prefer results showing that the predicted risk is a good estimate of the true risk. The paper on lines 116-131 attempt to this. However, the primary papers that have been cited [1,12,25] are all about **linear** regression and not **kernel** regression. Specifically, they all assume that $y_i = \beta^T x_i + \epsilon_i$ and that we are fitting a linear function. This is not quite the setting of this paper, as we have an infinite dimensional feature vector space that we are working in. Hence I do not think those papers are sufficient theoretical justification. My other concern with this, is that the discussion from lines 98-111 **do not assume that** $y = f(x) + \epsilon_i$ which I think is needed in [47]. The paper presents for general distributiuons on $\mathcal{X}$ and $\mathcal{Y}$. I do not think the eigenlearning framework captures the following situation $x_i = z_i + \epsilon_j$ and $y_i = f(z_i)$, but the paper here, as written, would claim this. See [A,B] for papers that address such a situation, [B] even has results on benign overfitting. [A] Sonthalia, Rishi and Raj Rao Nadakuditi. “Training Data Size Induced Double Descent For Denoising Feedforward Neural Networks and the Role of Training Noise.” Trans. Mach. Learn. Res. 2023 (2023): n. pag. [B] Kausik, C., Srivastava, K., & Sonthalia, R. (2023). Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers.TMLR 2024 3) References I think the long list of references on lines 45-48 need to be changed. The paper should either further subcategorize them, or cite fewer papers. In the case that the authors decide to further subvategorize them. I think they are missing some references [A,B,C,D]. Additionally, some papers are cited twice, see 25, 26, and 23, 24. [C] Xiao, L., Hu, H., Misiakiewicz, T., Lu, Y., & Pennington, J. (2022). Precise Learning Curves and Higher-Order Scalings for Dot-product Kernel Regression. Neural Information Processing Systems. [D] Hu, H., Lu, Y.M., & Misiakiewicz, T. (2024). Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime. ArXiv, abs/2403.08160.

Questions

Please see weaknesses

Rating

6

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

The limitations are well discussed.

Summary

The paper investigates the overfitting behavior of Gaussian Kernel Ridge Regression (KRR) in high-dimensional settings, focusing on how the model performance is influenced by the choice of the bandwidth parameter and sample size. They aimed to provide a more comprehensive picture of overfitting with Gaussian KRR by studying the overfitting behavior with varying bandwidth or with arbitrarily varying dimension, including sub-polynomially. In particular, they showed that for fixed dimension, even with varying bandwidth, the interpolation learning is never consistent and generally not better than the null predictor (either the test error tends to infinity or is finite but it is almost always not better than the null predictor). For increasing dimension, they gave an upper and lower bound on the test risk for any scaling of the dimension with sample size, which indicates in many cases whether the overfitting is catastrophic, tempered or benign. They showed the first example of sub-polynomially scaling dimension that achieves benign overfitting for the Gaussian kernel. Additionally, they showed that a class of dot-product kernels on the sphere is inconsistent when the dimension scales logarithmically with sample size.

Strengths

The presentation of the paper looks really in good order with adequate clarifications and rich literature reviews. The motivation is clear to me. The proof provided also looks correct in general., They clearly provided an upper and lower bound on the test risk for any scaling of the dimension with sample size, which provides a clear and comprehensive understanding on the issue of overfitting with Gaussian KRR, which is not restricted on particular regimes, while it also discovers new result for sub-polynomially varying dimension. I found the proof technique quite interesting and insightful. Although the contribution is not extremely outstanding or groundbreaking, the results completely reflect the effect of varying bandwidth or dimensionality in a very comprehensive way and it certainly facilitates the understanding of this issue and also provides a very insightful theoretical guidance of picking these crucial parameters.

Weaknesses

The first and a clear weakness would be lack of experiments. Since the results in the paper focus on the overfitting behavior with varying bandwidth or with arbitrarily varying dimension, including sub-polynomially, it should benefit a lot and is very instructive to study the real effects guided by the theories on the simulated or real-word datasets. The results should be sensitivity to tuning parameters. The paper highlights the complexity of balancing these parameters but does not provide robust, practical guidelines for optimal tuning. Different data distributions and kernel eigenstructures result in non-uniform impacts of the tuning parameters, complicating the tuning process further. It is better the paper could consider more general date distributions in Assumption 2 or at least can provide some insights on how the results may vary given different date distributions.

Questions

Can you explain the theoretical basis for the catastrophic overfitting observed with certain bandwidth scalings and the choice of kernels intuitively? What are the practical guidelines for choosing the bandwidth parameter in real-world applications since there is no experiment? How does the proposed method perform across different types of data distributions besides Assumption 2?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

Summary

The authors derive estimates of the population risk of the kernel (ridgeless) regression estimator for spherical data when either the kernel bandwidth or the dimension of the data depends on the number of training points $m$. To do so, authors rely on the eigenframework and prior work, which provides (under assumptions on the distributions of the random variable $\phi(X)$ where $\phi$ is the kernel feature map and $X$ is the input random variable) formulas for the population risk of the kernel ridge regression estimator as a function of the eigenvalues of the kernel integral operator. Using these formulas, authors then derive nonasymptotic estimates of these quantities in order to establish the limit value of the risk, as well as its dependency w.r.t $m$ and $d$. They obtain that - for a fixed dimension, overfitting is always harmfull (tempered or catasrophic) unless the bandwidth scales in precisely in $m^{-1/d-1}$ in which case overfitting is shown to be tempered for large enough noise in the data (Theorem 1) - for a fixed bandwidth, but varying dimensionthey derivelower and upper bound on the population risk. This allows them to - recover known results stating that when the dimension size increases polynomially with sample size, overfitting is benign or tempered - show that when the dependency is logarithmic, overfitting is not benign (under additional assumptions verified for the gaussian kernel) - show that when the dependency is subpolynomial $\exp(\sqrt{m)$ scaling, overfitting can be benign

Strengths

The paper is clear, with a good effort spent on litterature review and comparison with prior work. The main technical contributions seem to be bounds on the spectra of dot-product kernels on the sphere, which if novel (I am not an expert of this domain) could be of independent interest and are welcomed.

Weaknesses

- This paper investigates the behavior of **ridgeless** (e.g. no RKHS norm penalty) kernel estimators, something which should be made clearer. For example, kernel ridge regression is part of the paper title, whereas the paper does not study kernel ridge regression. - The eigenframework which they use rely on a number of assumptions to be valid.

Questions

In the analysis, the data is assumed to be on the sphere. Can the authors comment on how they expect the results to change for data distributed on the whole of $\mathbb R^d$? Typos: l 294 l 298

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Mentioned in weaknesses.

Please read rebuttal and comment

Dear reviewers, could you have a look at the authors response and comment on them if you have done so, yet. So far, we have quite a bit of a spread in the opinions, so we need a discussion to converge. thanks in advance your area chair

Thank you for your response

Thank you to the authors for their response. Regarding 2 - reading again that section of the paper, it think it would help guide the reader unfamiliar with this literature if the authors explained how the predicted risk expression is obtained. For instance, quoting [38], "[BCP20] presents two different approaches to obtain this analytical expression: a continuous approximation to the learning curves inspired by the Gaussian process literature [Sol01], and replica method with a saddle-point approximation". A sentence along these lines could be helpful to make this formula less "magic".

Regarding the contribution of the paper

We thank the reviewers for their continued feedback. We feel some reviewers are dismissive of the contribution of analyzing the Gaussian kernel under the eigenframework. Indeed, we are relying on the eigenframework predictions, which are a powerful (but non-rigorous) tool, and proving the eigenframework predictions for the Gaussian kernel would be very important (and difficult) contribution. We acknowledge that understanding the limitations of eigenframework is an important research direction, but we point to both empirical [7,38] and theoretical evidence [38] that the eigenframework holds well for the Gaussian kernel. Taking an extreme analogy, we feel that dismissing work because it relies on the eigenframework is analogous to dismissing hardness results relying on NP!=P because "the hard part was done by Cook, Lewin and Karp” or “more interesting is to prove NP!=P", or asking if the hardness result can be relaxed to "avoid this assumption". This analogy is extreme and we are not saying the eigenframework is at the same status as NP!=P, but more direct analogies are other papers relying on the eigenframework (e.g. [1, 7, 12, 25, 47, 54, 63]), or with a more historical perspective, the entire body of work relying on the Parisi predictions for the Sherrington-Kirkpatrik Ising Model, a spin glass model (e.g. by Mazard, Parisi, Virasoro and many others), which was only much later proven rigorously by Talagrand. Yes, we are using a tool (the eigenframework predictions) that involved some heavy lifting, but that is the point of a tool - to allow for simplified further analysis. The analysis we do using this tool is highly non-trivial at the technical level and is not just a simple application of Zhou et al 2023 [63]. First, for fixed dimension, our technical contribution is deriving the dependence of the eigenvalues of the Gaussian kernel on the bandwidth (Theorem 8) and hence understanding how the test risk depends on the bandwidth (Theorem 1). Second, for increasing dimension, our technical contribution is deriving upper and lower bounds for the test risk that work for any scaling of the dimension and sample size (Theorems 2 and 3), by introducing the “upper and lower index” (Definition 1). We agree that proving the eigenframework predictions rigorously for a Gaussian kernel (i.e. lifting the GUA assumptions) would indeed be a strong contribution, but we are very explicit on exactly what we rely on, what is new, what is rigorous, and what is an assumption. We do not think the fact that we do not prove all of this in a single paper should diminish the contribution of what we actually do.