The algorithm essentially selects a random subset of training points and learns a (truncated) kernel ridge regression function on the selected subset. Under certain characteristic assumptions on the complexity of the function class in which the optimal function lies and on the complexity of the RKHS, the paper shows that the algorithm achieves optimal generalization guarantees. This is an improvement over the existing results in this setting in one of the regimes of the problem space. Additionally, the authors show that under a zero Bayes risk condition, the algorithm achieves a faster convergence rate to the Bayes risk. The main contribution of the paper lies in adapting the proof techniques used in the online kernel regression literature to the standard kernel regression setting.

After a careful discussion among the reviewers, there is a clear consensus that the paper provides a solid contribution to the community. As a result, I would recommend acceptance for publication at NeurIPS2019. One important concern that came up during the discussion is that it is unclear under which regime the paper is focusing on. As a result, it becomes difficult for the reviewers and readers to assess the actual contribution. For example, the authors need to clarify that the paper needs \beta \geq 1/2 to hold and that it considers *only* the case \alpha 1 .

In this paper we consider the nonparametric least square regression in a Reproducing Kernel Hilbert Space (RKHS). We propose a new randomized algorithm that has optimal generalization error bounds with respect to the square loss, closing a long-standing gap between upper and lower bounds. Moreover, we show that our algorithm has faster finite-time and asymptotic rates on problems where the Bayes risk with respect to the square loss is small. We state our results using standard tools from the theory of least square regression in RKHSs, namely, the decay of the eigenvalues of the associated integral operator and the complexity of the optimal predictor measured through the integral operator.

In this paper we consider the nonparametric least square regression in a Reproducing Kernel Hilbert Space (RKHS). We propose a new randomized algorithm that has optimal generalization error bounds with respect to the square loss, closing a long-standing gap between upper and lower bounds. Moreover, we show that our algorithm has faster finite-time and asymptotic rates on problems where the Bayes risk with respect to the square loss is small. We state our results using standard tools from the theory of least square regression in RKHSs, namely, the decay of the eigenvalues of the associated integral operator and the complexity of the optimal predictor measured through the integral operator. Papers published at the Neural Information Processing Systems Conference.