# How many samples are needed to leverage smoothness?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 34 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [High-dimensional analysis of double descent for linear regression with random projections](https://mlsanity.com/paper/2303.01372/) (2023)
- [Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon](https://mlsanity.com/paper/1812.11167/) (2018)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [An elementary analysis of ridge regression with random design](https://mlsanity.com/paper/2203.08564/) (2022)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Interpolation and Learning with Scale Dependent Kernels](https://mlsanity.com/paper/2006.09984/) (2020)

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

- [The Galerkin method beats Graph-Based Approaches for Spectral Algorithms](https://mlsanity.com/paper/2306.00742/) (2023)

## Abstract (arXiv)

A core principle in statistical learning is that smoothness of target functions allows to break the curse of dimensionality. However, learning a smooth function seems to require enough samples close to one another to get meaningful estimate of high-order derivatives, which would be hard in machine learning problems where the ratio between number of data and input dimension is relatively small. By deriving new lower bounds on the generalization error, this paper formalizes such an intuition, before investigating the role of constants and transitory regimes which are usually not depicted beyond classical learning theory statements while they play a dominant role in practice.