Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers kernel ridge regression under the Gaussian design and derives decay rates of the excess generalization error under capacity and source conditions. The analysis reveals interesting phase transition phenomena in the noiseless and noisy regimes.
main_review: The presented decays rates of the excess generalization error of kernel ridge regression (KRR) under Gaussian design and the observed phase transition phenomena are of interest. The first result in (9) is the excess error of effectively non-regularized KRR, which transitions from a fast decay to a plateau with no decay as the sample size $n$ increases. The second result in (10) is the excess error of effectively regularized KRR, which transitions from a fast decay to a slower decay as $n$ increases. The results in (11) and (12) are the excess error of optimally regularized KRR, which transitions from a fast decay (optimal rate in noiseless regime) to a slower decay (optimal rate in noisy regime) as $n$ increases. The numerical experiments also verify their theoretical claims about the crossover from the noiseless to noisy regime. Overall, the paper is well written and the results are theoretically sound. It sheds light on how the decay rates of the excess error of KRR depend on the regularization decay strength, capacity, source, and noise variance. The Gaussian design is a rather strong condition for KRR, is it possible to remove this assumption in the future study?

After Rebuttal

I thank the authors for addressing my concerns.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This submission studies the asymptotic generalization error of kernel ridge regression (KRR) under Gaussian design with specific eigen-decay conditions. Major contributions include (i) specifying the decay rate of the generalization error based on the noise level and source / capacity conditions of the kernel / target function, (ii) identifying different regimes of learning, and (iii) deciding the optimal ridge regularization. Theoretical results are verified in various experiments.
main_review: ## Strength

The excess risk of kernel regression has been extensively studied in the nonparametric regression literature. This paper provides a somewhat unifying perspective, which takes into account the noise level, different eigen-decay conditions and regularization strength.   
The analysis builds upon recently derived precise asymptotics for ridge regression under general feature covariance and target function, and it is nice to see that these elusive asymptotic formulas can be used to provide quantitative understanding of classical machine learning models (instead of only generating good-looking double descent figures). To my knowledge, the different regimes of learning is an interesting contribution, and the matching empirical results on realistic datasets demonstrate the practical relevance of the theory. 

## Weakness

1. The considered model is a bit idealized. I initially thought that the Gaussian design refers to the input features (as in [41] in the reference list), but instead it is directly assumed that the kernel features are Gaussian. It might be a good idea to comment on this gap, and whether the findings can be translated to the other setting via Taylor expansion on the kernel matrix. 

2. Related to the previous point, due to the assumed Gaussian features, it seems that the generalization error of the studied estimator in the proportional limit has already been derived in prior works (e.g., [35][37]). The authors should comment on whether this is the case and the improvement over previous results. 
For example, prior works in the proportional scaling usually assumed the population eigenvalues to be bounded away from 0, which cannot capture the power law decay. Would this be an advantage of the new analysis?

3. As the authors noted, the derivation of the excess risk rate is not completely rigorous due to the order of limits taken. While the empirical results are reassuring, would it be possible for certain terms that vanish in the proportional limit (and thus omitted in the asymptotic formulas) to reappear and dominate the rate when $p/n\to 0$?

**Additional Comments and Questions**

1. In the proportional limit, [35] showed that the optimal ridge regularization can be negative in the noiseless case under specific source conditions. Is it possible to observe similar phenomenon under the power-law eigen-decay setting? If not, what might be the reason for this difference?

2. Is there an intuition of why the power-law decay is a good fit for MNIST? The decaying eigenvalues for the capacity condition seems reasonable, but I don't really know why the source condition also follows a similar decay. 

3. (minor) The reference [21] in Section 4 cannot handle the varying source condition due to the isotropic prior on the true coefficients. A more appropriate reference would be the general result of [35][37].  
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors evaluate the excess error of Kernel Ridge Regression, in a unified manner by considering general settings for regularization and noise levels, as well as a power-law decay for the eigenvalues of feature covariance. The main results can be summarized in Figure 1, where one particularly observes the transitions between different regimes. Numerical results on real-world datasets such as MNIST, Fashion MNIST, and Superconductivity are also reported.
main_review: The paper is in general well written and easy to follow, the transition from the noiseless to noisy values reported here is, to the best of my knowledge, characterized for the first time in the general setting. I believe this work is of general interest to the NeurIPS community.

Detailed comments:
* Page 2, "Related work" section: the reference is missing for "the related Gaussian Process literature".
limitations_and_societal_impact: The authors adequately addressed the possible limitations of their approach. This work is mainly theoretical and algorithmic and I do not see any possible negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes an asymptotic analysis of the excess generalization error of kernel ridge regression under a gaussian design. In summary, the authors identify four regimes of functioning of kernel ridge regression as a function of the number of samples and the regularization parameter. These regimes allow unifying the theory of kernel ridge regression which had been performed previously in extreme cases (without noise, with noise but optimal regularization parameter).
main_review: ** Overall review **

1-Strong Points: The insights drawn are quite interesting, seem quite valid empirically on synthetic data, and allows for unifying the kernel ridge regression methods. The article is well written

2-Weak Points: The experiments in real data are not so convincing. It consists of self-added noise on the existing dataset (MNIST) which is far to be realistic. The question is how the theory can actually help to understand the excess generalization error of kernel ridge regression applied on existing datasets (which are already noisy by being collected manually, by humans, ...). Adding Gaussian noise is the same as creating synthetic data. The authors should also detail/motivate more the power-law decay assumption (should it model realistic features extracted from real dataset? Some real-world examples (figures of eigenvalues of the features co-variance) where this happens would also be interesting.)

** Detailed review **

1-Line 28: ... regression and are --> ... regression are

2-Line 59: a reference is missing

3-Line 96/97 Why is it important to assume this power-law decay (theoretical traceability, insights from experiments?). It should be good to precise.

4-In the paragraph Capacity and source coefficients, the authors should try to give a better interpretation, i.e., what does equation (7) mean in plain English?

5- The authors should try to make as possible their figure reproducible. For example, in Figure 3, it is impossible for a practitioner to obtain the figure (which kernel has been used for example, ...)

6-Line 177: for the the ---> for the

7-In figure 5, there is a reference for figures above and below.

8-The real data experiments on MNIST and Fashion MNIST are quite toyed examples and not really real data experiments. What is the motivation to add noise to the labels?

9- It would be better to make some connection between these predictions and the theoretical and exact large dimensional analysis of kernel ridge regression from Random Matrix Theory (RMT)? (How do they differ? Is the prediction of RMT be recovered?). There is a discussion in the last paragraph of 'Related work' but never discussed afterward in the main results.


limitations_and_societal_impact: The limitations of the works are put in the work. For suggestions, the authors should consider trying to do some real-world experiments that are not played, clarify more specifically the link with exact (and not the order of magnitude as a function of sample size) asymptotic performed in RMT or at least what is the further insights with respect to reference [21] for example.
review_title: null

Meta-review: This paper studies asymptotic analysis of the excess generalization error of kernel ridge regression under a gaussian design. The authors identify four regimes of functioning of KRR as a function of the number of samples and the regularization parameter. These regimes allow unifying the theory of kernel ridge regression which had been performed previously in extreme cases. Numerical results on real-world datasets are also reported.

All the reviewers agree that the paper is well written, easy to follow and brings interesting theoretical insights. It’s pointed out that the paper provides `a missing point of view of asymptotic analysis of ridge regression of general interest to the ML` (reviewer `Z2bD`), `transition from the noiseless to noisy values reported here is, to the best of my knowledge, characterized for the first time in the general setting` (reviewer `rxhv`), `sheds light on how the decay rates of the excess error of KRR depend on the regularization decay strength, capacity, source, and noise variance` (reviewer `5R13`) and `different regimes of learning is an interesting contribution, and the matching empirical results on realistic datasets demonstrate the practical relevance of the theory` (reviewer `Jd5V`). Some of the limitations and concerns raised are addressed during the discussion period (authors promised to clarify limitations regarding the noise assumption and their potential robustness in the revision). In the end, all reviewers recommended for acceptance  (3 accepts, 1 weak accept). The AC believes this is a solid work that would be of interest to the broad NeurIPS audience. 

Decision: Accept (Poster)