Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning
Xueyuan Zhou, Nathan Srebro · 2011
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)) d d+2, yielding an asymptotic error 2 − rate of (n / log(n)) 2+d.