Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration

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.

References in corpus (5)

• Risk bounds for statistical learning
• Random design analysis of ridge regression
• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning

Cited by in corpus (6)

• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Interpolating Predictors in High-Dimensional Factor Regression
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Gradient Descent in RKHS with Importance Labeling
• Towards Sharp Analysis for Distributed Learning with Random Features
• Learning curves for Gaussian process regression with power-law priors and targets