Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors explain the slow convergence of the Nonparametric Kernel regression with ridge regularization in the regime where the true prediction function is too smooth compared with that of the kernel. 

Two parameters have been introduced: although not explicitly explained, \beta controls the span of the kernel in the RKHS, and \alpha controls the smoothness of the true prediction function compared with the used kernel. When \alpha=2, the smoothness is equal to the that of the kernel, and if \alpha > 2, the prediction function is smoother than the used kernel. In this case, the convergence can be slow even though generally the smooth functions are preferred for generalization.

The authors provided an analysis on this regime and showed some experiments confirming the derivation.
strength_and_weaknesses: The paper is partially interesting in terms of considering an unexplored regime where our model is too complex compared with the true prediction function. I am not an expert who can look into the details of the proof, but the derived result seems to provide a clear interpretation and the coincidence with the experiments.

However in practice, the proposed saturation effect can be addressed by changing the kernel functions.

clarity,_quality,_novelty_and_reproducibility: In terms of the clarity and novelty, the paper is fine.

summary_of_the_review: The focus of the paper is on the regime where the prediction function is too smooth compared with that of the kernel function. I find the paper  interesting and think the paper can be published at ICLR, but I am not an expert to provide reviews for the quality of the proof techniques.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the saturation effect of kernel ridge regression (KRR), providing a proof of the conjecture. The main result is a lower bound on the generalization error which suggests that KRR cannot achieve the information theoretical lower bound when the smoothness of the underground truth function exceeds certain level.
strength_and_weaknesses: The paper presents new insights into the saturation phenomenon: the optimally tuned KRR can achieve the minimax rate $n^{-\alpha/(\alpha+\beta)}$ when the smoothness of the underlying truth function is within certain threshold; however, the rate for the estimator is bounded from below by $n^{-2/(2+\beta)}$ if the smoothness exceeds the threshold. This could be a useful contribution to learning theory.
clarity,_quality,_novelty_and_reproducibility: - Novelty: the paper proves a commonly observed conjecture which has impact on the theoretical understanding of KRR.
- Clarity: I found the paper well-written and easy to follow. 
- Quality: the theoretical proof looks solid.


summary_of_the_review: Overall, I think this is an interesting paper with solid theoretical contributions to kernel methods.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the saturation effect of KRR. Under some additional assumptions, the paper provides a lower bound of the rate of generalization error for the case where $f\in[\mathcal{H}]^\alpha$ for some $\alpha>2$. The proposed lower bound matches the existing upper bound when $\alpha>2$ and verifies the saturation effect of KRR.
strength_and_weaknesses: The paper is well-written and easy to follow. The authors provide proof of a long-standing conjecture about the information-theoretical lower bound of KRR. The theoretical contribution is significant.

However, I still have some concerns about the assumptions. The lower bound is obtained under different assumptions than the upper bound. The upper bound (prop 2.2) requires the distributions satisfying conditions (B') and (C), while the proposed lower bound (thm 3.1) requires Assumption 1 and 2. Thus I do not think this paper completely proves the conjecture since it is still unknown whether the proposed lower bound can be obtained under condition (B') and (C).

I'm also confused about the assumptions on the noise. Notice that condition (C) assumes the momentum of the noise is upper bounded but Assumption 2 requires the noise to be non-vanishing. These two assumptions seem somewhat opposite. I hope the authors can provide a detailed discussion of the required assumptions.

minors:

Line 2 of thm 3.1: "satisfies the that" -> "satisfies that"
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear and of high quality. The theoretical contributions are novel.
summary_of_the_review: Overall, I think this paper provides an important contribution to the saturation effect of KRR. But the authors need to provide more discussions on the additional assumptions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper is dedicated to a theoretical analysis of the saturation effect, that is the gap between information theoretical lower bound on the generalization error of KRR and the actual error. This effect has been widely observed in practices. The main result of the paper is given in Theorem 3.1, that deduces a lower bound on the accuracy of KRR under assumptions (A) eigenvalues decay rate, 1) smoothness of kernel and 2) lower bound on the variance of noice. 
strength_and_weaknesses: I have not checked mathematical proofs completely, though major arguments seems to be correct. 

First general question that appears after reading the article is: can the condition (2) be weakened. Does the saturation effect disappear is we have zero noise? E.g. what changes if we set sigma=0 in numerical experiments of Section 4? From the bias-variance decomposition formula on page 4 it seems that the effect should disappear, because the variance term will disappear. Could you comment on that.
clarity,_quality,_novelty_and_reproducibility: A narrative is clear and justified. For me it is hard to judge the originality, because I am not familiar with earlier papers on the saturation effect. 
summary_of_the_review: A paper is theoretical. Statements are justified. Since ICLR is more oriented towards experiments, a paper needs to enhance experimental section. Is everything understood with the saturation effect after that theory was built, or something is still present in experiments that was not covered by theory?
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the so-called saturation effect of kernel ridge regression (KRR), ie, the inability of KRR to achieve proper learning when the smoothness of the underground truth function exceeds certain level. This is a theoretical paper addressing and answering a longstanding conjecture on this saturation effect.

+ technically clear and sound paper
+ solves a conjecture important on KRR, a widely used ML learning algorithm
- write-up: there are many typos to be corrected



justification_for_why_not_higher_score: The impact of the paper for the ICLR community, more on the empirical and deep learning side, could be limited.
justification_for_why_not_lower_score: The technical quality of the production is solid, solving a longstanding conjecture.
Decision: Accept: poster