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

Abstract

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 Y = (Y_1,,Y_n) 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 L^2 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.

Tasks

Reproductions