# Optimal Rates and Saturation for Noiseless Kernel Ridge Regression

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 58 references that are in the map.
- First posted on arXiv 24 Feb 2024.

## Builds on (most cited first, 18 of 18)

- [DGM: A deep learning algorithm for solving partial differential equations](https://mlsanity.com/paper/1708.07469/) (2017)
- [The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problems](https://mlsanity.com/paper/1710.00211/) (2017)
- [Solving high-dimensional partial differential equations using deep learning](https://mlsanity.com/paper/1707.02568/) (2017)
- [Deep Potential Molecular Dynamics: a scalable model with the accuracy of quantum mechanics](https://mlsanity.com/paper/1707.09571/) (2017)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [On the Optimality of Misspecified Kernel Ridge Regression](https://mlsanity.com/paper/2305.07241/) (2023)
- [On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay](https://mlsanity.com/paper/2309.13337/) (2023)
- [Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields](https://mlsanity.com/paper/2305.00322/) (2023)

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

- [A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression](https://mlsanity.com/paper/2410.17796/) (2024)
- [Cubit: Token Mixer with Kernel Ridge Regression](https://mlsanity.com/paper/2605.06501/) (2026)
- [Spectral Convergence of Random Feature Method in Multiple Dimensions](https://mlsanity.com/paper/2609.03401/) (2026)

## Abstract (arXiv)

Kernel ridge regression (KRR), also known as the least-squares support vector machine, is a fundamental method for learning functions from finite samples. While most existing analyses focus on the noisy setting with constant-level label noise, we present a comprehensive study of KRR in the noiseless regime -- a critical setting in scientific computing where data are often generated via high-fidelity numerical simulations. We establish that, up to logarithmic factors, noiseless KRR achieves minimax optimal convergence rates, jointly determined by the eigenvalue decay of the associated integral operator and the target function's smoothness. These rates are derived under Sobolev-type interpolation norms, with the L2 norm as a special case. Notably, we uncover two key phenomena: an extra-smoothness effect, where the KRR solution exhibits higher smoothness than typical functions in the native reproducing kernel Hilbert space (RKHS), and a saturation effect, where the KRR's adaptivity to the target function's smoothness plateaus beyond a certain level. Leveraging these insights, we also derive a novel error bound for noisy KRR that is noise-level aware and achieves minimax optimality in both noiseless and noisy regimes. As a key technical contribution, we introduce a refined notion of degrees of freedom, which we believe has broader applicability in the analysis of kernel methods. Extensive numerical experiments validate our theoretical results and provide insights beyond existing theory.