# Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces

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

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2018.

## Built on by (most cited first, 30 of 59)

- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Optimal Rates for Regularized Conditional Mean Embedding Learning](https://mlsanity.com/paper/2208.01711/) (2022)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains](https://mlsanity.com/paper/2305.02657/) (2023)
- [Generalization Ability of Wide Neural Networks on ℝ](https://mlsanity.com/paper/2302.05933/) (2023)
- [Learning linear operators: Infinite-dimensional regression as a well-behaved non-compact inverse problem](https://mlsanity.com/paper/2211.08875/) (2022)
- [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)
- [Learning the optimal Tikhonov regularizer for inverse problems](https://mlsanity.com/paper/2106.06513/) (2021)
- [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)
- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [On the Saturation Effect of Kernel Ridge Regression](https://mlsanity.com/paper/2405.09362/) (2024)
- [Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms](https://mlsanity.com/paper/2405.14778/) (2024)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [Optimal Rate of Kernel Regression in Large Dimensions](https://mlsanity.com/paper/2309.04268/) (2023)
- [Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay](https://mlsanity.com/paper/2401.01599/) (2024)
- [Marginal Density Ratio for Off-Policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/2312.01457/) (2023)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal](https://mlsanity.com/paper/2411.19653/) (2024)
- [Sobolev Norm Learning Rates for Conditional Mean Embeddings](https://mlsanity.com/paper/2105.07446/) (2021)
- [Data splitting improves statistical performance in overparametrized regimes](https://mlsanity.com/paper/2110.10956/) (2021)
- [Radial Basis Function Approximation with Distributively Stored Data on Spheres](https://mlsanity.com/paper/2112.02499/) (2021)
- [Online nonparametric regression with Sobolev kernels](https://mlsanity.com/paper/2102.03594/) (2021)
- [Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?](https://mlsanity.com/paper/2108.11872/) (2021)
- [Generalization Ability of Wide Residual Networks](https://mlsanity.com/paper/2305.18506/) (2023)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [Overcoming Saturation in Density Ratio Estimation by Iterated Regularization](https://mlsanity.com/paper/2402.13891/) (2024)

## Abstract (arXiv)

In this paper, we study regression problems over a separable Hilbert space with the square loss, covering non-parametric regression over a reproducing kernel Hilbert space. We investigate a class of spectral/regularized algorithms, including ridge regression, principal component regression, and gradient methods. We prove optimal, high-probability convergence results in terms of variants of norms for the studied algorithms, considering a capacity assumption on the hypothesis space and a general source condition on the target function. Consequently, we obtain almost sure convergence results with optimal rates. Our results improve and generalize previous results, filling a theoretical gap for the non-attainable cases.