Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
Open accessAbstract
We study optimization of finite sums of geodesically smooth functions on Riemannian manifolds. Although variance reduction techniques for optimizing finite-sums have witnessed tremendous attention in the recent years, existing work is limited to vector space problems. We introduce Riemannian SVRG (RSVRG), a new variance reduced Riemannian optimization method. We analyze RSVRG for both geodesically convex and nonconvex (smooth) functions. Our analysis reveals that RSVRG inherits advantages of the usual SVRG method, but with factors depending on curvature of the manifold that influence its convergence. To our knowledge, RSVRG is the first provably fast stochastic Riemannian method. Moreover, our paper presents the first non-asymptotic complexity analysis (novel even for the batch setting) for nonconvex Riemannian optimization. Our results have several implications; for instance, they offer a Riemannian perspective on variance reduced PCA, which promises a short, transparent convergence analysis.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The Poincaré ball has a Riemannian manifold structure, so Equation (2) can be optimized via stochastic Riemannian optimization methods such as RSGD or RSVRG.
“Since the Poincaré Ball has a Riemannian manifold structure, we can optimize Equation (2) via stochastic Riemannian optimization methods such as RSGD [5] or RSVRG [34].”
From Poincaré Embeddings for Learning Hierarchical Representations (2017) · cites this paper as [34]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Stochastic Gradient Descent on Riemannian Manifolds
Bonnabel, S. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2254619 · Cited by 540 · see citing works
Flagged first, then by citations
Research works printed but not linked: 37
- P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
- A. Agarwal and L. Bottou. A lower bound for the optimization of finite sums. In Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pages 78-86, 2015.
- Z. Allen-Zhu and E. Hazan. Variance reduction for faster non-convex optimization. arXiv:1603.05643, 2016. · arXiv
- F. Bach and E. Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n). In Advances in Neural Information Processing Systems, pages 773-781, 2013.
- R. Bhatia. Positive Definite Matrices. Princeton University Press, 2007.
- D. A. Bini and B. Iannazzo. Computing the karcher mean of symmetric positive definite matrices. Linear Algebra and its Applications, 438(4):1700-1710, 2013.
- A. Cherian and S. Sra. Riemannian dictionary learning and sparse coding for positive definite matrices. arXiv:1507.02772, 2015. · arXiv
- M. Congedo, B. Afsari, A. Barachant, and M. Moakher. Approximate joint diagonalization and geometric mean of symmetric positive definite matrices. PloS one, 10(4):e0121423, 2015.
- A. Defazio, F. Bach, and S. Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In NIPS, pages 1646-1654, 2014.
- A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2):303-353, 1998.
- D. Garber and E. Hazan. Fast and simple pca via convex optimization. arXiv preprint arXiv:1509.05647, 2015. · arXiv
- S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
- P. Gong and J. Ye. Linear convergence of variance-reduced stochastic gradient without strong convexity. arXiv preprint arXiv:1406.1102, 2014. · arXiv
- R. Hosseini and S. Sra. Matrix manifold optimization for Gaussian mixtures. In NIPS, 2015.
- B. Jeuris, R. Vandebril, and B. Vandereycken. A survey and comparison of contemporary algorithms for computing the matrix geometric mean. Electronic Transactions on Numerical Analysis, 39:379-402, 2012.
- C. Jin, S. M. Kakade, C. Musco, P. Netrapalli, and A. Sidford. Robust shift-and-invert preconditioning: Faster and more sample efficient algorithms for eigenvector computation. arXiv:1510.08896, 2015. · arXiv
- R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323, 2013.
- H. Kasai, H. Sato, and B. Mishra. Riemannian stochastic variance reduced gradient on grassmann manifold. arXiv preprint arXiv:1605.07367, 2016. · arXiv
- J. Konečnỳ and P. Richtárik. Semi-stochastic gradient descent methods. arXiv:1312.1666, 2013. · arXiv
- X. Liu, A. Srivastava, and K. Gallivan. Optimal linear representations of images for object recognition. IEEE TPAMI, 26(5):662-666, 2004.
- M. Moakher. Means and averaging in the group of rotations. SIAM journal on matrix analysis and applications, 24(1):1-16, 2002.
- E. Oja. Principal components, minor components, and linear neural networks. Neural Networks, 5(6): 927-935, 1992.
- P. Petersen. Riemannian geometry, volume 171. Springer Science & Business Media, 2006.
- S. J. Reddi, A. Hefny, S. Sra, B. Póczós, and A. Smola. Stochastic variance reduction for nonconvex optimization. arXiv:1603.06160, 2016. · arXiv
- H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22: 400-407, 1951.
- R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo method, volume 707. John Wiley & Sons, 2011.
- M. Schmidt, N. L. Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. arXiv:1309.2388, 2013. · arXiv
- O. Shamir. A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate. In International Conference on Machine Learning (ICML-15), pages 144-152, 2015.
- S. Sra and R. Hosseini. Geometric optimisation on positive definite matrices for elliptically contoured distributions. In Advances in Neural Information Processing Systems, pages 2562-2570, 2013.
- J. Sun, Q. Qu, and J. Wright. Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method. arXiv:1511.04777, 2015. · arXiv
- M. Tan, I. W. Tsang, L. Wang, B. Vandereycken, and S. J. Pan. Riemannian pursuit for big matrix recovery. In International Conference on Machine Learning (ICML-14), pages 1539-1547, 2014.
- C. Udriste. Convex functions and optimization methods on Riemannian manifolds, volume 297. Springer Science & Business Media, 1994.
- B. Vandereycken. Low-rank matrix completion by Riemannian optimization. SIAM Journal on Optimiza- tion, 23(2):1214-1236, 2013.
- A. Wiesel. Geodesic convexity and covariance estimation. IEEE Transactions on Signal Processing, 60 (12):6182-6189, 2012.
- L. Xiao and T. Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
- H. Zhang and S. Sra. First-order methods for geodesically convex optimization. arXiv:1602.06053, 2016. · arXiv
- T. Zhang, A. Wiesel, and M. S. Greco. Multivariate generalized Gaussian distribution: Convexity and graphical models. Signal Processing, IEEE Transactions on, 61(16):4141-4148, 2013.
Cited by
Sorted by citations
Poincaré Embeddings for Learning Hierarchical Representations
Nickel, M., & Kiela, D. (2017) · arXiv · doi:10.48550/arxiv.1705.08039 · Cited by 667 · see citing works
- Authors
- Zhang, H., Reddi, S. J., & Sra, S.
- Affiliations
- Massachusetts Institute of Technology (US)
- Carnegie Mellon University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2016
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1605.07147
- OpenAlex
- W2549348365
- Cited by
- 140
- References
- 1
- Citations by year
- 2026: 2 · 2025: 8 · 2024: 9 · 2023: 9 · 2022: 14 · 2021: 17 · 2020: 30 · 2019: 25 · 2018: 18 · 2017: 7 · 2016: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Mathematics › Applied Mathematics › Geometric Analysis and Curvature Flows
- Keywords
- variance reduction, Riemannian manifolds, finite-sum optimization, non-convex optimization, geodesic convexity, manifold curvature
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
