[edit]
Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:901-908, 2011.
Abstract
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))dd+2, yielding an asymptotic error rate of (n/log(n))−22+d.