# Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm

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

## Key facts

- Cited by 114 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2017.

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

- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [The Inductive Bias of Quantum Kernels](https://mlsanity.com/paper/2106.03747/) (2021)
- [Optimal Rates for Regularized Conditional Mean Embedding Learning](https://mlsanity.com/paper/2208.01711/) (2022)
- [Sharp Spectral Rates for Koopman Operator Learning](https://mlsanity.com/paper/2302.02004/) (2023)
- [A Simple Model of Inference Scaling Laws](https://mlsanity.com/paper/2410.16377/) (2024)
- [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)
- [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)
- [The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods](https://mlsanity.com/paper/2111.07167/) (2021)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [Augmented balancing weights as linear regression](https://mlsanity.com/paper/2304.14545/) (2023)
- [On the Optimality of Misspecified Kernel Ridge Regression](https://mlsanity.com/paper/2305.07241/) (2023)
- [Efficient Conditionally Invariant Representation Learning](https://mlsanity.com/paper/2212.08645/) (2022)
- [On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay](https://mlsanity.com/paper/2309.13337/) (2023)
- [Kernel interpolation generalizes poorly](https://mlsanity.com/paper/2303.15809/) (2023)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Practical Kernel Tests of Conditional Independence](https://mlsanity.com/paper/2402.13196/) (2024)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [Minimax Optimal Kernel Operator Learning via Multilevel Training](https://mlsanity.com/paper/2209.14430/) (2022)
- [On the Saturation Effect of Kernel Ridge Regression](https://mlsanity.com/paper/2405.09362/) (2024)
- [An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings](https://mlsanity.com/paper/2110.14868/) (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)
- [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)
- [Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay](https://mlsanity.com/paper/2401.01599/) (2024)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)

## Abstract (arXiv)

Learning rates for least-squares regression are typically expressed in terms of L2-norms. In this paper we extend these rates to norms stronger than the L2-norm without requiring the regression function to be contained in the hypothesis space. In the special case of Sobolev reproducing kernel Hilbert spaces used as hypotheses spaces, these stronger norms coincide with fractional Sobolev norms between the used Sobolev space and L2. As a consequence, not only the target function but also some of its derivatives can be estimated without changing the algorithm. From a technical point of view, we combine the well-known integral operator techniques with an embedding property, which so far has only been used in combination with empirical process arguments. This combination results in new finite sample bounds with respect to the stronger norms. From these finite sample bounds our rates easily follow. Finally, we prove the asymptotic optimality of our results in many cases.