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

arXiv: https://arxiv.org/abs/1905.10680 · HTML: https://mlsanity.com/paper/1905.10680/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2019.

## Built on by (most cited first, 12 of 12)

- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [On the Optimality of Misspecified Kernel Ridge Regression](https://mlsanity.com/paper/2305.07241/) (2023)
- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Failure and success of the spectral bias prediction for Kernel Ridge Regression: the case of low-dimensional data](https://mlsanity.com/paper/2202.03348/) (2022)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Spectrally Transformed Kernel Regression](https://mlsanity.com/paper/2402.00645/) (2024)
- [Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds](https://mlsanity.com/paper/2410.14539/) (2024)
- [Optimal and Structure-Adaptive CATE Estimation with Kernel Ridge Regression](https://mlsanity.com/paper/2602.18958/) (2026)
- [Stochastic gradient descent with initial regularization](https://mlsanity.com/paper/2608.22953/) (2026)

## Abstract (arXiv)

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.