Approximate Manifold Regularization:
Scalable Algorithm and Generalization Analysis
Abstract
Graph-based semi-supervised learning is one of
the most popular and successful semi-supervised
learning approaches. Unfortunately, it suffers from
high time and space complexity, at least quadratic
with the number of training samples. In this paper, we propose an efficient graph-based semisupervised algorithm with a sound theoretical guarantee. The proposed method combines Nystrom
subsampling and preconditioned conjugate gradient descent, substantially improving computational
efficiency and reducing memory requirements. Extensive empirical results reveal that our method
achieves the state-of-the-art performance in a short
time even with limited computing resources