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 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.
Cite
Text
Li et al. "Approximate Manifold Regularization: Scalable Algorithm and Generalization Analysis." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/400Markdown
[Li et al. "Approximate Manifold Regularization: Scalable Algorithm and Generalization Analysis." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/li2019ijcai-approximate/) doi:10.24963/IJCAI.2019/400BibTeX
@inproceedings{li2019ijcai-approximate,
title = {{Approximate Manifold Regularization: Scalable Algorithm and Generalization Analysis}},
author = {Li, Jian and Liu, Yong and Yin, Rong and Wang, Weiping},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2019},
pages = {2887-2893},
doi = {10.24963/IJCAI.2019/400},
url = {https://mlanthology.org/ijcai/2019/li2019ijcai-approximate/}
}