Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs
This provides a theoretically grounded, manifold-adaptive method for statisticians and machine learning practitioners working with high-dimensional data, though it is incremental in extending existing graph-based regularization theory.
The paper tackles nonparametric regression using Laplacian smoothing on graphs, establishing that it achieves minimax optimal estimation and testing rates over Sobolev spaces, with rates depending only on the intrinsic manifold dimension rather than the ambient space dimension.
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 $\widehat{f}$, and a goodness-of-fit test also based on $\widehat{f}$. These upper bounds match the minimax optimal estimation and testing rates of convergence over the first-order Sobolev class $H^1(\mathcal{X})$, for $\mathcal{X}\subseteq \mathbb{R}^d$ and $1 \leq 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 $\mathcal{X} \subseteq \mathbb{R}^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 $\mathcal{X}$ were a full-dimensional set in $\mathbb{R}^d$.