  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} = (Y_1,\ldots,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
\emph{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.
