# Sample complexity and effective dimension for regression on manifolds

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2020.

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

- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [Harmless interpolation in regression and classification with structured features](https://mlsanity.com/paper/2111.05198/) (2021)
- [Model-agnostic Measure of Generalization Difficulty](https://mlsanity.com/paper/2305.01034/) (2023)
- [Deep Networks Provably Classify Data on Curves](https://mlsanity.com/paper/2107.14324/) (2021)
- [Breaking Neural Network Scaling Laws with Modularity](https://mlsanity.com/paper/2409.05780/) (2024)
- [Spectral Algorithms on Manifolds through Diffusion](https://mlsanity.com/paper/2403.03669/) (2024)
- [On the Intrinsic Dimensions of Data in Kernel Learning](https://mlsanity.com/paper/2601.16139/) (2026)
- [Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds](https://mlsanity.com/paper/2410.14539/) (2024)

## Abstract (arXiv)

We consider the theory of regression on a manifold using reproducing kernel Hilbert space methods. Manifold models arise in a wide variety of modern machine learning problems, and our goal is to help understand the effectiveness of various implicit and explicit dimensionality-reduction methods that exploit manifold structure. Our first key contribution is to establish a novel nonasymptotic version of the Weyl law from differential geometry. From this we are able to show that certain spaces of smooth functions on a manifold are effectively finite-dimensional, with a complexity that scales according to the manifold dimension rather than any ambient data dimension. Finally, we show that given (potentially noisy) function values taken uniformly at random over a manifold, a kernel regression estimator (derived from the spectral decomposition of the manifold) yields minimax-optimal error bounds that are controlled by the effective dimension.