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

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 bf Y = (Y1,ldots,Yn) 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 L2 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.