Abstract:
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}^m.
