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

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.

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."

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.

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.

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

We thank all of the reviewers for their thoughtful feedback. In the attached PDF, we provide empirical evidence that our predictions are correct. We focus on the finite-dimensional case because of computational constraints. In Figure a, we consider the first case of Theorem 1, namely when the bandwidth $\tau_m = o(m^{-\frac{1}{d-1}})$. It shows that the test error tends to something equal to or larger than the test risk of the null predictor. In Figure b, we consider the second case, i.e $\tau_m = \omega(m^{-\frac{1}{d-1}})$ and the plot shows that the test error increases with sample size, which aligns with the claim that it diverges as the sample size $m$ increases. In Figure c, we consider the case when $\tau_m = \Theta(m^{-\frac{1}{d-1}})$ and the plot shows that for some noise level (which is high enough), the predictor is worse than the null predictor, as predicted by our theorem. We will add these simulations to the final version of the paper.

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

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.

The paper investigates how the "predicted risk" of kernel rigdeless regression behaves for Gaussian kernels on the sphere if the width changes with the sample size. The first main result shows that catastrophic or tempered behavior of this risk surrogate occurs depending on how the width changes. The second main result establishes a similar result for more general kernels (without a width parameter) if the dimension increases.

The paper enjoyed serious reviews as well as a productive rebuttal phase. Most concerns centered around: a) the used eigenframework, b) the Gaussian universality assumption, and c) the novelty of the technical contribution. In view of a) the authors argued with a list of recent papers working with the same assumption. However, about half of these papers have not been published, yet, and hence it is probably too early for a decisive conclusion about this framework. However, I would argue for an "in dubio pro accept" approach as the alternative (if applied consistently in all areas of ML) would substantially slow down scientific progress. Issue b) is actually closely related to a) for the paper under review as it provides a "justification" for a). In view of c) the authors made a convincing case that they do not simply apply the work of others.

Overall, I agree with the outcome of the discussion which went in favor of accepting the paper despite the fact that some parts (e.g. Example 1) could certainly be improved or clarified.