ML Anthology

MASAGA: A Linearly-Convergent Stochastic First-Order Method for Optimization on Manifolds

Reza Babanezhad, Issam H. Laradji, Alireza Shafaei, Mark Schmidt
ECML-PKDD 2018 pp. 344-359
doi:10.1007/978-3-030-10928-8_21 /ecmlpkdd/2018/babanezhad2018ecmlpkdd-masaga/

Abstract

We consider the stochastic optimization of finite sums over a Riemannian manifold where the functions are smooth and convex. We present MASAGA, an extension of the stochastic average gradient variant SAGA on Riemannian manifolds. SAGA is a variance-reduction technique that typically outperforms methods that rely on expensive full-gradient calculations, such as the stochastic variance-reduced gradient method. We show that MASAGA achieves a linear convergence rate with uniform sampling, and we further show that MASAGA achieves a faster convergence rate with non-uniform sampling. Our experiments show that MASAGA is faster than the recent Riemannian stochastic gradient descent algorithm for the classic problem of finding the leading eigenvector corresponding to the maximum eigenvalue. Code related to this paper is available at: https://github.com/IssamLaradji/MASAGA .

PDF ECML-PKDD Semantic Scholar

Cite

Text

Babanezhad et al. "MASAGA: A Linearly-Convergent Stochastic First-Order Method for Optimization on Manifolds." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2018. doi:10.1007/978-3-030-10928-8_21

Markdown

[Babanezhad et al. "MASAGA: A Linearly-Convergent Stochastic First-Order Method for Optimization on Manifolds." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2018.](https://mlanthology.org/ecmlpkdd/2018/babanezhad2018ecmlpkdd-masaga/) doi:10.1007/978-3-030-10928-8_21

BibTeX

@inproceedings{babanezhad2018ecmlpkdd-masaga,
  title     = {{MASAGA: A Linearly-Convergent Stochastic First-Order Method for Optimization on Manifolds}},
  author    = {Babanezhad, Reza and Laradji, Issam H. and Shafaei, Alireza and Schmidt, Mark},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2018},
  pages     = {344-359},
  doi       = {10.1007/978-3-030-10928-8_21},
  url       = {https://mlanthology.org/ecmlpkdd/2018/babanezhad2018ecmlpkdd-masaga/}
}