# Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 86 references that are in the map.
- First posted on arXiv 14 Nov 2021.

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

- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms](https://mlsanity.com/paper/1805.09450/) (2018)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Spectral Convergence of the connection Laplacian from random samples](https://mlsanity.com/paper/1306.1587/) (2013)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Spectral Analysis Of Weighted Laplacians Arising In Data Clustering](https://mlsanity.com/paper/1909.06389/) (2019)
- [Geometric structure of graph Laplacian embeddings](https://mlsanity.com/paper/1901.10651/) (2019)
- [A maximum principle argument for the uniform convergence of graph Laplacian regressors](https://mlsanity.com/paper/1901.10089/) (2019)
- [A Spectral Series Approach to High-Dimensional Nonparametric Regression](https://mlsanity.com/paper/1602.00355/) (2016)
- [Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic](https://mlsanity.com/paper/1312.3291/) (2013)
- [Principal Component Projection Without Principal Component Analysis](https://mlsanity.com/paper/1602.06872/) (2016)
- [Cluster Trees on Manifolds](https://mlsanity.com/paper/1307.6515/) (2013)
- [Faster Principal Component Regression and Stable Matrix Chebyshev Approximation](https://mlsanity.com/paper/1608.04773/) (2016)
- [Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG](https://mlsanity.com/paper/1910.06517/) (2019)

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

- [Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression](https://mlsanity.com/paper/2311.00140/) (2023)
- [Rates of Convergence for Regression with the Graph Poly-Laplacian](https://mlsanity.com/paper/2209.02305/) (2022)
- [The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data](https://mlsanity.com/paper/2212.14514/) (2022)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [Understanding the Effect of GCN Convolutions in Regression Tasks](https://mlsanity.com/paper/2410.20068/) (2024)

## Abstract (arXiv)

In this paper we study the statistical properties of Principal Components Regression with Laplacian Eigenmaps (PCR-LE), a method for nonparametric regression based on Laplacian Eigenmaps (LE). PCR-LE works by projecting a vector of observed responses bf Y = (Y1,ldots,Yn) onto a subspace spanned by certain eigenvectors of a neighborhood graph Laplacian. We show that PCR-LE achieves minimax rates of convergence for random design regression over Sobolev spaces. Under sufficient smoothness conditions on the design density p, PCR-LE achieves the optimal rates for both estimation (where the optimal rate in squared L2 norm is known to be n-2s/(2s + d)) and goodness-of-fit testing (n-4s/(4s + d)). We also show that PCR-LE is manifold adaptive: that is, we consider the situation where the design is supported on a manifold of small intrinsic dimension m, and give upper bounds establishing that PCR-LE achieves the faster minimax estimation (n-2s/(2s + m)) and testing (n-4s/(4s + m)) rates of convergence. Interestingly, these rates are almost always much faster than the known rates of convergence of graph Laplacian eigenvectors to their population-level limits; in other words, for this problem regression with estimated features appears to be much easier, statistically speaking, than estimating the features itself. We support these theoretical results with empirical evidence.