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

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 69 references that are in the map.
- First posted on arXiv 3 Jun 2021.

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

- [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)
- [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)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates](https://mlsanity.com/paper/1706.10003/) (2017)
- [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)
- [Hypothesis Testing for High-Dimensional Multinomials: A Selective Review](https://mlsanity.com/paper/1712.06120/) (2017)
- [Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic](https://mlsanity.com/paper/1312.3291/) (2013)
- [Cluster Trees on Manifolds](https://mlsanity.com/paper/1307.6515/) (2013)

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

- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression](https://mlsanity.com/paper/2311.00140/) (2023)
- [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)
- [A Unified Analysis of Multi-task Functional Linear Regression Models with Manifold Constraint and Composite Quadratic Penalty](https://mlsanity.com/paper/2211.04874/) (2022)
- [Nonparametric regression on random geometric graphs sampled from submanifolds](https://mlsanity.com/paper/2405.20909/) (2024)
- [Skeleton Regression: A Graph-Based Approach to Estimation with Manifold Structure](https://mlsanity.com/paper/2303.11786/) (2023)
- [Estimating a Function and Its Derivatives Under a Smoothness Condition](https://mlsanity.com/paper/2405.10126/) (2024)
- [Understanding the Effect of GCN Convolutions in Regression Tasks](https://mlsanity.com/paper/2410.20068/) (2024)
- [Node Regression on Latent Position Random Graphs via Local Averaging](https://mlsanity.com/paper/2410.21987/) (2024)
- [Joint estimation of smooth graph signals from partial linear measurements](https://mlsanity.com/paper/2505.23240/) (2025)
- [STARK denoises spatial transcriptomics images via adaptive regularization](https://mlsanity.com/paper/2512.10994/) (2025)
- [Stabilizing Transformer Training Through Consensus](https://mlsanity.com/paper/2601.22614/) (2026)

## Abstract (arXiv)

In this paper we study the statistical properties of Laplacian smoothing, a graph-based approach to nonparametric regression. Under standard regularity conditions, we establish upper bounds on the error of the Laplacian smoothing estimator widehatf, and a goodness-of-fit test also based on widehatf. These upper bounds match the minimax optimal estimation and testing rates of convergence over the first-order Sobolev class H1(X), for Xsubseteq ℝd and 1 ≤ d < 4; in the estimation problem, for d = 4, they are optimal modulo a log n factor. Additionally, we prove that Laplacian smoothing is manifold-adaptive: if X subseteq ℝd is an m-dimensional manifold with m < d, then the error rate of Laplacian smoothing (in either estimation or testing) depends only on m, in the same way it would if X were a full-dimensional set in ℝd.