mlsanityData to 7 Oct 2026

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

arXiv 2106.01529 ↗First posted 3 Jun 2021math.ST stat.ML stat.THcited by 13

Not on the map. Why?

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.

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

Builds on

12 of 69 references.

References · 12

  1. 2018Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operatorcited by 70
  2. 2014Trend Filtering on Graphscited by 45
  3. 2015A variational approach to the consistency of spectral clusteringcited by 28
  4. 2018Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithmscited by 22
  5. 2016Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smootherscited by 20
  6. 2019Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphscited by 18
  7. 2017Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Ratescited by 11
  8. 2019A maximum principle argument for the uniform convergence of graph Laplacian regressorscited by 9
  9. 2016A Spectral Series Approach to High-Dimensional Nonparametric Regressioncited by 8
  10. 2013Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statisticcited by 7
  11. 2017Hypothesis Testing for High-Dimensional Multinomials: A Selective Reviewcited by 7
  12. 2013Cluster Trees on Manifoldscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 2; 2024: 5; 2025: 2; 2026: 1.

13 papers.

Sort:

  1. 2021Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphscited by 5
  2. 2023Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regressioncited by 5
  3. 2022The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Datacited by 3
  4. 2024Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmapscited by 2
  5. 2022A Unified Analysis of Multi-task Functional Linear Regression Models with Manifold Constraint and Composite Quadratic Penaltycited by 1
  6. 2024Nonparametric regression on random geometric graphs sampled from submanifoldscited by 1
  7. 2023Skeleton Regression: A Graph-Based Approach to Estimation with Manifold Structurecited by 0
  8. 2024Estimating a Function and Its Derivatives Under a Smoothness Conditioncited by 0
  9. 2024Understanding the Effect of GCN Convolutions in Regression Taskscited by 0
  10. 2024Node Regression on Latent Position Random Graphs via Local Averagingcited by 0
  11. 2025Joint estimation of smooth graph signals from partial linear measurementscited by 0
  12. 2025STARK denoises spatial transcriptomics images via adaptive regularizationcited by 0
1 more
  1. 2026Stabilizing Transformer Training Through Consensuscited by 0