Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning

We study the error and sample complexity of semi-supervised learning by Laplacian Eignmaps at the limit of infinite unlabeled data. We provide a bound on the error, and show that it is controlled by the graph Laplacian regularizer. Our analysis also gives guidance to the choice of the number of eigenvectors k to use: when the data lies on a d-dimensional domain, the optimal choice of k is of order (n/\log(n))^\fracdd+2, yielding an asymptotic error rate of (n/\log(n))^-\frac22+d. [pdf]