Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper studies a truncated KRR method and shows how the alignment of the target function with the kernel improves the performance of the TKRR. The paper also sheds light on a situation when the TKRR can achieve parametric rates of convergence - something which is not possible for KRR. Both a theoretical analysis and a simulation study is included in the paper.
strengths_and_weaknesses: The paper is sufficiently novel and studies a very interesting variant of KRR, namely, TKRR and demonstrates both theoretically and empirically the strength of TKRR, in particular, when the target function is aligned with the kernel function. The paper is well-written and the ideas and the results are presented clearly. 
questions: None.
limitations: No potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers kernel ridge regression (KRR)  and its truncated version for estimating a target function contaminated with the i.i.d. noise. Two situations are considered depending on the target alignment (TA) scores, which are the coefficients of projection of the underlying target vector on the eigenvalues of normalized empirical kernel matrix K. 1)TA scores are non-zero in a few consecutive components, in which they sampled as i.i.d. with non-zero mean, 2) TA scores are decaying polynomially as well as eigenvalues of $K$. In the first example, the authors demonstrate possible non-monotonous behavior of the MSE depending on truncation parameter r, and other parameters fixed. In the second one, four performance regimes are considered for truncated and full KRR based on the strength of alignment of the target function with the eigenvectors of $K$. If the target alignment coefficients decay fast, then with the proper truncation and smoothing parameter the MSE achieves a better rate than the full KRR with the parametric rate as the limit in the decay parameter.

strengths_and_weaknesses: Strengths:
The paper is easy to follow and well written. The examples considered serve as a good illustration of the double-descent phenomenon in RKHS and the dependence of generalization performance of the (T)KRR  on properties of RKHS and on how well the underlying function is aligned with the eigenvectors of $K$.
  
Weaknesses:
-  I am not sure I understand section 3.1, see the questions below. 
- The evaluation is illustrative enough, but only uses the artificial dataset. 

Minor details:
- w is used for both noise  in (1) and coefficient vector in (3)
- is $\sqrt{N}$ needed in the formula between the lines 117-118?  
- misprint:  $-1$ in the power of $\sigma/n$ in 192 

questions: Is the statement about the solution of (6) being not unique correct? 
(6) is a ridge regression problem with a design matrix with $r$ orthogonal columns, $r<n$  (see line 128)?  
In the supplementary material (17) has a non-unique solution, at the same time 
$$\tilde{S}^*_{\mathbf{x}}(w)(x) = \frac{1}{\sqrt{n}}\sum_{j=1}^n w_j \tilde{\mathbb{K}}(x,x_i) = \frac{1}{\sqrt{n}} \sum_{k=1}^r \mu_k \phi_k(x) \sum_{j=1}^n \phi_k(x_j)  w_j  =  \sum_{k=1}^r \mu_k \phi_k(x)   u_k^{\top} w.$$
 Multiple solutions in terms of $w$  in (17) come from the fact that $w$ contains an arbitrary vector, that lies in the subspace orthogonal to the one spanning $\{u_1,\dots,u_r\}$, but taking $u_k^{\top} w$ leaves only one solutions?

It would be worth commenting the results of the submission in comparison with Tsigler, A., & Bartlett, P. L. (2020). Benign overfitting in ridge regression. arXiv preprint arXiv:2009.14286.

----------------
I increased the rating after the authors commented on the questions.
limitations: The limitations and well addressed in the work. No negative societal impact is anticipated.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The manuscript provides an analysis of truncated kernel ridge regression. In particular, the authors show how alignment of the target function influences convergence rates, and identify scenarios in which TKRR exhibits stronger guarantees than ridge regression. In addition, they show examples in which generalisation performance of TKRR demonstrates non-monotonicity and phase transition behaviour in regularisation and truncation parameters.
strengths_and_weaknesses: Strengths:

The main result of the paper is the exact expression for mean squared error of TKRR from which the authors derive two interesting conclusions:
1. They demonstrate how a non-monotonous behaviour of the generalisation performance with respect to truncation parameter takes place, which provides a new insight into double-descent phenomena  
2. They derive stronger convergence results for TKRR (compared to canonical KRR) in case of strong alignment between the target and kernel functions, which are new to the best of my knowledge

Weaknesses:

1. All analysis in the paper is performed in the fixed design setting. In the conclusion the authors state that it can be extended to the random design model. However it’s outside of my area of expertise, so I cannot judge how straightforward/possible that extension is, taking into account also that TKRR itself is data-dependent
2. Theoretical results presented in the paper indicate importance of the noise level for selection of a suitable truncation parameter. This is also supported by simulation results, where figure 2a demonstrates that whether choosing a larger r (already being in decreasing error regime) is a beneficial approach depends on the noise level. With this in mind, I believe the manuscript would benefit from a more thorough discussion of this aspect of the problem, in particular what can be deducted from the theoretical results and what only from the simulations/experiments
3. I found reading of the manuscript rather strenuous. While in parts it can be attributed to its level of technicality, I would suggest the authors to consider some re-organisation of the material. In particular, I would recommend at least partially incorporating discussion currently presented in Appendix D2 and D3 into the main text, potentially at the expense of the proofs in Section 7.
4. In line 240, I believe the reference should be to Proposition 2a instead of Theorem 2.
questions: Please, see weaknesses section above and correct/comments on any misunderstandings from my side
limitations: Yes, they have
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: this submission studies how the alignment between target function and the kernel in logistic kernel regression (KRR) can improve the regression fidelity. Kernel spectral truncation is used to adjust the alignment. The results indicate that: 1) for polynomial alignment, there is a regime that kernel truncation (TKRR) archives the parametric rate O(\sigma^2/n) which is faster than full KRR; 2) for bandlimited alignment, TKRR exhibits multiple descents. 

strengths_and_weaknesses: Strength
theoretical novelty: this is the first work to study the impact of target alignment for KRR

Weakness
practical significance: it’s not clear how useful the findings about the alignment and concentration would be in practice. It heavily relies on the spectrum of f^* which is unknown, and no side information is known about it in this setting.  
writing needs improvement: while the overall story is clear, this paper involves a lot of notations, where some details can be deferred to the appendix. 

questions: The connection to generalization is unclear. It’s mentioned in lines 59-61 that the results can be extended to generalization error. The setting however seems to be a pure inference task, with no training involved and no training/test data defined separately. This needs to be clarified.
The relation between \lambda and r is not clear. It seems that both of them are playing as regularization parameters and not clear if in certain regimes they overlap. A counter plot similar to Fig. 1 & 2 would be useful to clarify this issue for the readership.
It would be interesting to discuss connections to to singular value thresholding in the context of  (e.g., nuclear norm based regularization) which truncates certain singular value directions that are less aligned with the signal of interest. 
In Fig. 2 (left) for noise intensity 0.18 and higher, it seems that the best choice for truncation is r=0. What does that mean?

limitations: They are properly discussed.
review_title: null

Meta-review: metareview: The reviewers all found that the paper is interesting and contributes interesting new results. The reviewers have made several useful constructive comments that the authors are strongly encouraged to take into account.
confidence: Certain
Decision: Accept