Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Just interpolate: Kernel “Ridgeless” regression can generalizeThe Annals of Statistics, 2020
- Optimal rates for spectral algorithms with least-squares regression over Hilbert spacesApplied and Computational Harmonic Analysis, 2020
- Nonparametric stochastic approximation with large step-sizesThe Annals of Statistics, 2016
- Robust linear least squares regressionThe Annals of Statistics, 2011
- On Early Stopping in Gradient Descent LearningConstructive Approximation, 2007
- Risk bounds for statistical learningThe Annals of Statistics, 2006
- Optimal Rates for the Regularized Least-Squares AlgorithmFoundations of Computational Mathematics, 2006
- A Second-Order Perceptron AlgorithmSIAM Journal on Computing, 2005
- On the Generalization Ability of On-Line Learning AlgorithmsIEEE Transactions on Information Theory, 2004
- ESTIMATING THE APPROXIMATION ERROR IN LEARNING THEORYAnalysis and Applications, 2003