TY - JOUR
T1 - Kernel truncated randomized ridge regression
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
AU - Jun, Kwang Sung
AU - Cutkosky, Ashok
AU - Orabona, Francesco
N1 - Funding Information:
The authors thank Junhong Lin, Lorenzo Rosasco, and Alessandro Rudi for the comments and discussions on this work. This material is based upon work supported by the National Science Foundation under grant no. 1908111 “Collaborative Research: TRIPODS Institute for Optimization and Learning”.
Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85090171187&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090171187&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85090171187
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
SN - 1049-5258
Y2 - 8 December 2019 through 14 December 2019
ER -