A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression

Summary

The authors address the problem of kernel ridge regression with a finite rank kernel, in the under-paramatrized regime. They prove sharper upper bounds on the test error, compared to previous existing works.

Strengths

The discussion is very well-written and easy to follow, with a number of illustrations being provided to set up the problem. Careful and detailed comparison to previous work is given, making it easy to understand the novelty of the present manuscript. Overall, the addressed problem is an important one, and I believe the derived bound will be of interest to the community. I have not checked the proof, and therefore give a low confidence score.

Weaknesses

I do not have any major concern. A minor remark is that while all experimental details are provided in Appendix D, it would be good to add at least a short description of the target functions and regularization used in Fig.1 and 2 in the main text or in the corresponding captions.

Questions

- (minor) While the comparison with the bound of [6] in Fig. 2 is compelling, is there a reason why the bound of [30] is not also plotted? Its addition, or a brief sentence justifying its non-inclusion, would be welcome.

Rating

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

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

The paper highlights the inadequacy of existing statistical learning guarantees for general kernel regressors when applied to finite-rank kernels. The authors have addressed this issue by developing non-asymptotic upper and lower bounds for the test error of finite-rank kernel ridge regression. These new bounds are more precise than the previously established ones and are applicable for any regularization parameters. This research provides a more dependable framework for utilizing finite-rank kernels in machine learning applications.

Strengths

1. The paper addresses an important gap in the current understanding of machine learning algorithms by developing more accurate and reliable bounds for finite-rank kernel ridge regression, which is frequently used in practical applications. 2. The research provides a more precise and dependable framework for using finite-rank kernels in machine learning problems, which could result in better performance and more efficient algorithms.

Weaknesses

1. The paper only considers under-parameterized regime. 2. Low bound is a main argument of this paper, but all details are given in the Appendix.

Questions

1. It looks a little bit weird that you don't need to take $\lambda=O(N^\theta)$ for some $\theta<0$ to balance the bias and variance. Any insights for this? 2. In Theorem 4.1 and Corollary 4.3.1, what are the mild conditions on the kernel K? I cannot find the mild condition on input distribution either.

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

The authors have adequately addressed the limitations.

Summary

This paper analyzes the test error of ridge regression with a finite rank kernel. The finite rank kernel appears in several practical settings such as transfer learning and random neural networks. The authors provide a new analysis in this setting using tools from random matrix theory. A detailed comparison to other generalization bounds is presented.

Strengths

1. New generalization results in a practical and challenging setting. 2. New analysis techniques.

Weaknesses

1. The comparison to standard generalization results is not clear (Eq. (12)). Both bounds scale as $\sqrt{\frac{\log(n)}{n}}$. It is not clear which one is tighter. 2. The technical details of the proof are not given and the novelty of the analysis is not explained in detail. Instead, most of the paper is devoted to a discussion and experiments. 3. There are some unclear technical issues (see questions below).

Questions

1. The bound in Theorem 4.1 and the bound in Eq. (12) both scale as $\sqrt{\frac{\log(n)}{n}}$. Which one is tighter and why? What is C in Eq. (12)? 2. The test error definition is not standard: Shouldn’t the label be $y$ in the MSE and not $\tilde{f}$? Is the definition of the test error the same in other works? Also, the bias-variance decomposition does not seem to be standard. Usually the learned predictor is the same in the bias expression (e.g., see the Wikipedia definition of bias-variance decomposition), whereas here the predictor is different: it changes from $f_{Z,\lambda}$ to $f_{(X,f(X)),\lambda)}$. Is this standard for analyzing kernel methods? 3. Where in the analysis is the under-parameterized assumption ($M <N$) needed? 4. In Eq. (10) if $\tilde{\gamma}_{>M} = 0$, the bias is exactly zero for all $N$? Is this a mistake?

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

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Limitations are not discussed in detail. Some of the limitations are mentioned throughout the paper. Maybe it will be helpful to add a limitations section and summarize all limitations.

Summary

The paper studies the kernel ridge regression under the non-asymptotic setting. The authors give the upper and lower bounds for bias and variance term, respectively. The authors argue the results improve upon those in Bach 2023.

Strengths

The paper is well-structured. The authors give rigorous proofs, following by careful experiments.

Weaknesses

1. The paper requires further improvement and polishing in writing. To name a few, line 57-58; line 107-110. 2. The paper would benefit from a more consistent and standardized use of symbols and notations. For example, in line 90, it would be better to use L_2(\rho) instead of L_\rho^2. In lien 92, the notation of \tilde{f}(\textbf{X}) is not proper. In Definition 3.1, it would be better to include the decreasing order of eigenvalues in the statement rather than adding an additional remark 3.2. In line 200-207, notation K^{(\infty)} 3. As mentioned in Bach 2023, more refined bounds can be found in Rudi et al. 2015, Rudi and Rosasco 2017. However, the authors failed to mention them and other related results in the comparison. In the absence of such comparisons, it is hard to tell the novelty and improvements of the current submission. 4. The dependency of \lambda seems to be incorrect for the variance term. 5. Given Corollary 4.3.1 in the submission, I cannot see significant improvements against those in Bach 2023. Also, the authors did not give a proper explanation for considering \lambda goes to 0.

Questions

Could the authors mention the lower bound for the problem? With optimal choice of \lambda, we can derive the optimal upper bound for the test error. However, the current result does not show a bias-variance tradeoff with respect to \lambda. Could the authors explain?

Rating

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

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

1 poor

Limitations

No.

Summary

This paper gives a refined analysis of the test error of kernel ridge regression with a finite kernel in the underparametrized regime, where the rank M of the kernel is smaller than the number of data points N. The analysis improves upon previous ones by providing tighter non-asymptotic upper and lower bounds, which remain tight even as the ridge parameter goes to zero. When the target function lies in the RKHS, the bounds show that estimation is consistent as N goes to infinity.

Strengths

The paper is well written and clear. The authors state the contributions clearly and compare carefully with previous work. Establishing tight bounds for this basic learning setting is an important problem.

Weaknesses

No major weaknesses, just some minor typos. I would also suggest that the authors include the explicit lower bounds in the main paper. Given that this a major focus of the paper it should not be required for the reader to go to the appendix. It would also be nice for the appendix to give a bit clearer account for the technical differences in the proof techniques of their bounds versus previous ones.

Questions

- Can the authors elaborate the technical difficulties in extending beyond the finite rank setting, or even when M ~ N? Can analogous results be shown when the kernel is approximately low rank? - It is unclear that realistic NTK or random features will fall in this underparametrized regime. Can the authors give elaborate if this should be the case? Is it possible to experiment in more realistic NTK settings to truncate the kernel and apply the bounds?

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

No limitations. Authors give some directions or future work.

Acknowledgement

I thank the authors for the explanations. I wish to stand by my original score, and stress once again that my assessment is limited by my inability of checking the proof, whence low confidence.

Acknowledgement

Thank the authors for addressing my concerns. I keep my score unchanged.