Approximate Manifold Regularization: Scalable Algorithm and Generalization Analysis

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 semi-supervised 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.

Authors

• Jian Li
• Yong Liu
• Rong Yin Institute of Information Engineering, CAS School of Cyber Security, University of Chinese Academy of Sciences
• Weiping Wang Institute of Information Engineering, Chinese Academy of Sciences

Keywords

• Machine Learning Applications: Big data; Scalability
• Machine Learning: Dimensionality Reduction and Manifold Learning
• Machine Learning: Semi-Supervised Learning