On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay

Summary

This paper provides a rigorous analysis of the asymptotic rates of kernel ridge regression. Building on works which analyzed the Gaussian design case, this work recovers the same rates using less severe restrictions on the distribution of features. The novel contribution here beyond similar works of Li et al 2023 (a,b) is to characterize the rate of the bias term. The authors derive a complete phase diagram of the possible behaviors and provide the optimal scaling of the ridge parameter $\lambda \sim n^{-\theta}$. They provide experiments on simple sinusoidal regression problems where eigenvalues and eigenfunctions are exactly known and show that the theoretical rates match the experimental rates.

Strengths

This paper gives a rigorous analysis of kernel regression rates when eigenvalues fall in a power law $\lambda_i \sim i^{-\beta}$. The specifically novel contribution in this work is obtaining the rate of decay of the bias term and giving an exact set of assumptions that give these rates (embedding index, source condition, Holder condition on kernel, etc). The analysis recovers known (correct) results, which have been proven in the worst case, and calculated exactly under Gaussian design assumptions. The authors also provide empirical evidence to support their claimed rates on a toy data distribution, which is good for a theory paper.

Weaknesses

**Obtained learning curves pre-exist in the literature** The rates obtained match prior non-rigorous analyses and so do not exhibit *new* behaviors over what has been studied in the prior works. That said, the rigorous proof under relaxed set of conditions is still useful. **Title seems too broad** The title seems to cover too much territory. I would recommend a more descriptive title like "Rigorous analysis of bias and variance rates for KRR" **Relevant works** While the paper does mostly a good job of citing relevant prior works, it misses a few relevant works on this area 1. [Spigler et al 2019](https://arxiv.org/abs/1905.10843) which obtains rates in the noiseless regime using statistical physics techniques. 2. [Canatar et al 2021](https://www.nature.com/articles/s41467-021-23103-1), which also gives the bias and variance terms for noisy kernel ridge regression under the Gaussian design with the replica method. 3. [Simon et al 2023](https://openreview.net/forum?id=FDbQGCAViI), which uses a different heuristic to derive the average case KRR learning curve and introduces the idea of 'learnabilities' as a way of reasoning about the KRR predictor.

Questions

1. Can similar analysis techniques be applied to other decay rates? Suppose the eigenvalues fell not as a power law but instead exponentially fast $\lambda_i = e^{- i \beta}$. Could the same techniques be used to prove rates in this case ? Another setting of interest are polynomial regression problems in high dimension such as those studied by [Canatar et al 2021](https://www.nature.com/articles/s41467-021-23103-1). Is a rigorous proof of these curves possible as well in the high dimensional limit? 2. The authors claim that "that the benign overfitting phenomenon may not exist if one trains a very wide neural network." Which of the results in the paper do the authors thinks support this claim? Typos 1. line 6 "attentions" should be "attention" 2. line 17 "arisen" -> "arising" 3. line 32 "attentions" -> "attention" 4. line 86 "orders" -> "order" 5. line 291 "mistery" -> "mystery"

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors address the technical limitation of their current approach in the $\theta \geq \beta$ regime and leave the solution open as a future problem.

Summary

This paper analyzed generalization error rates for the Kernel Ridge Regression (KRR) problem. The authors make use of several generic assumptions, including (i) eigenvalue decay, (ii) Embedding index, (iii) source condition, and (iv) Holder continuity of the kernel. It is worth noting that assumptions (i), (ii), and (iv) are generally applicable to popular kernels. The findings of this study align with previous knowledge: in the absence of noise, interpolation achieves optimality, while in the presence of noise, a well-known Bias-Variance tradeoff emerges.

Strengths

1. The paper is well-written, exhibiting a high level of clarity and coherence in its structure and language. 2. The main result presented in the paper is not only insightful but also highly intriguing, contributing valuable insights to the research area. 3. The authors have demonstrated diligent referencing and citation of relevant prior work, showcasing a thorough understanding of the existing literature in the field.

Weaknesses

While I believe the paper is well-written, I feel that there are some areas where the authors assume background knowledge from the reader or make claims without providing adequate supporting discussions. I have identified a few specific points that I believe could benefit from clarification or additional explanation: 1. The contribution section appears to be highly technical. It would be helpful to provide a high-level, less technical overview of the contributions before diving into the specifics. For example, it would be beneficial to provide a brief explanation of the significance of variables such as β and s, as these variables are not defined prior to that section. 2. In line 47, it is mentioned that "our results...MAY suggest the benign...". The term "may" introduces uncertainty, but it is unclear how this conclusion was reached or what factors contribute to this interpretation/uncertainty. It seems that the authors may have intended to convey that since wide neural networks are essentially kernels, and the rates clearly demonstrate that noise impairs generalization, it is unlikely for the noise to have a benign effect. If this is indeed the case, it would be helpful to present this point in a clearer and less convoluted manner. 3. The second row of Figure 1 mentions "overfitting" and "underfitting," but there is no prior discussion or explanation of these terms in the paper. It would be beneficial to define these terms and provide some context.This would enhance the understanding of the results presented in the figure. Overall the second row figures were unclear to me. 4. In line 290, the statement mentions that "These results will help us better understand the generalization mistery of neural networks." It is unclear how this conclusion was reached or what specific discussions led to it. It would be valuable to elaborate on the implications of the results and provide a more thorough explanation of how they contribute to a better understanding of the generalization of neural networks.(by the way "mistery" is a typo!) Overall, by addressing these points, the paper can become more accessible to a broader range of readers and ensure a clearer understanding of the key concepts and conclusions.

Questions

In addition to Weaknesses section I have Following questions, I understand assumption 2 and 3 are common for these kind of analysis. But would you please elaborate, 1. What is the significance of the "embedding index"? What are the implications if α << 1/β or α >> 1/β? 2. What are the limitations of assumption 3? From my understanding, as "s" increases, the function f* becomes smoother since it belongs to H^s. Could you please clarify when this assumption holds or fails? I am willing to increase my score if the authors address these questions in Weaknesses/Questions sections.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

See weaknesses and questions.

Summary

The authors focus on the learning curve of kernel ridge regression, an important topic in theoretical machine learning, which is also used to approximate the generalization ability of 'lazy trained/NKT regime' neural networks. The authors provide a nearly full characterization of the learning curve in the setting of Source/Capacity conditions, considering the effects and interplay of the regularization parameter, the source condition, and the noise, rigorously closing many gaps in the literature, and in particular the picture arising from recent works in Neurips. The paper's contributions include: * Providing sharp estimates of the asymptotic orders of the bias term when the regularization parameter is not too small. This result holds for both well-specified and misspecified cases, improving the upper bounds given in previous research. * Showing an upper bound of the bias term in the nearly interpolating case. This upper bound is tight and matches the information-theoretic lower bound. * Providing learning curves of KRR for both noisy and noiseless cases, and the interplay between the two.

Strengths

I believe this is a strong paper. Most recent arguments on the learning curve of kernel methods were not entirely rigorous, and are based on the ‘Gaussian design’ assumption, which is certainly very restrictive. Even within the realm of Gaussians, Bordelon et al used a non-rigorous the replica method, while Cui et al used results from CGMT, but extrapolated their domain of validity. Random matrix arguments were also used by Jin et al, but some gap existed in the argument. This paper bridges the mathematical gap and manages to prove rigorously a nearly complete picture, removing the Gaussian assumptions. It closes a clear gap in the mathematics of Kernel ridge regression.

Weaknesses

I do not believe the paper has any particular weaknesses.

Questions

* I would be interested to know more about the limitation of the predictions. Removing the Gaussian assumption is quite a feat, but are they any restrictions on the data structure except the power law distribution/embedding dimension? Indeed, it seems there are only Eigenvalue decay assumptions in the paper! Do this means that any distribution of data in the RKHS is OK and that only the Covariance matrix matters? It would help me immensely to be explicit and to give counter examples. * With respect to Cui et al, it seems to me that the authors prove their entire phase diagram (Theorem 1 and 2), except for the left region of the blue region in Fig. 1 of Cui et al. I believe. The regime where θ ≥ β, is also very interesting, and I would be interested in understanding the reason why it is harder to control. Is it a possibility that in this region the data structure becomes relevant so that the Gaussian assumption is needed or do the authors believe it is only a technical problem? I remember a similar problem arises in Jacot et al.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

From a theoretical point of view, the paper is certainly addressing its limitation and has no ethical issue that I can foresee. It would still be interesting to be given the code to reproduce the figure in the supplementary material.

Summary

The paper studies the asymptotics of kernel ridge regression learning curves when the kernel eigenvalues and the ridge parameter both obey a power law.

Strengths

1. The paper is readable and well written. 2. It derives asymptotic results for KRR for a specific choice of kernel eigenvalues and regularization. 3. The introduction of technical definitions is clear, and sufficient background for previous results is provided.

Weaknesses

1. The claims of the paper are confusing to me. The double-descent phenomena (in this case sample-wise in the noisy case) implies that there is a second descent after the U-shaped curve, while the authors did not seem to reproduce that result. 2. The learning curves plotted in Figure 1. are with respect to the ridge parameter, while learning curves often refer to the generalization error as a function of training set size. 3. Experiments are not sufficient to demonstrate the tightness of the theoretical results. 4. The references (Bordelon et al. [2020], Cui et al. [2021]) cited in the paper demonstrate near perfect agreement with experimental learning curves despite the Gaussian assumption, but a discussion relating those results to the theory here is missing. 5. The claim regarding wide neural networks and benign overfitting stated in line 47 is neither explained nor demonstrated by experiments. 6. In general, a clear comparison to previous literature is missing, and it is hard to understand the novelty brought by this paper.

Questions

1. In line 56, $s$ is not defined. Also, it does not match the main result (i.e. it should be $s \geq 2$ rather than $s \geq 1$). 2. In random matrix theory, precise asymptotics can be obtained by relying on Gaussian equivalence principles and provide almost perfect learning curves for kernel regression (see Cui et.al. 2021). What insights the theory developed here brings in addition to the previous results and why do you think Gaussian assumption works so well?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

1 poor

Limitations

The limitations section is missing.

Summary

This paper studies the generalization error/excess risk of the kernel ridge regression (KRR). Using the classical bias-variance decomposition, the authors gives bounds on the bias term, which is claimed to be tighter than previous literatures. Together with the variance term results from another paper "Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a.", the authors conclude the bounds on the excess risk asymptotic in the sample size, where the effect of the decay of the ridge is stated explicitly.

Strengths

The paper gives a comprehensive reviews on the excess risk of KRR. There are experiments in both main text and appendix supporting the claimed result.

Weaknesses

My biggest concern would be that this paper is merely an incremental paper from "Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a." According to the remarks 3.3 and 3.5, the main theorems 3.2 and 3.4 basically recover the results from previous works: "Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007. doi: 10.1007/ s10208-006-0196-8.", "Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131–10143, 2021." and "Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly, March 2023a." Other than tightening the bounds, I hardly see more novelty or improvement from the main result.

Questions

Could you explain more on the novelty of the paper?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

This is a theoretical paper, where the assumptions 1-5 are stated clearly. The authors has remarked that these assumptions hold in general settings.

Response to Authors

The authors gave very useful answers to my questions. I agree that the proposed title "On the asymptotic learning curve of KRR under power law decay" or something like it may be more descriptive of the contributions of the present work. The authors acknowledge that their results operate in fixed dimension but point out that the high dimensional limit could be an interesting future direction. I now understand the comment on benign overfitting in ReLU neural networks as a statement about the zero (or small) $\lambda$ limit and how it is not necessarily compatible with good generalization. Based on these answers, I will increase my score.