Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds

Abstract

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.

This is the final version that appeared in NIPS 2016. Our proof of Lemma 2 was incorrect in the previous arXiv version. (9 pages paper + 6 pages appendix)

References in corpus (6)

• Stochastic Variance Reduction for Nonconvex Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Variance Reduction for Faster Non-Convex Optimization
• Approximate Joint Diagonalization and Geometric Mean of Symmetric Positive Definite Matrices
• First-order Methods for Geodesically Convex Optimization
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation

Cited by in corpus (39)

• Hyperbolic Graph Convolutional Neural Networks
• Riemannian Adaptive Optimization Methods
• Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Generating valid Euclidean distance matrices
• Trivializations for Gradient-Based Optimization on Manifolds
• Efficiently escaping saddle points on manifolds
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Escaping from saddle points on Riemannian manifolds
• Fast, asymptotically efficient, recursive estimation in a Riemannian manifold
• Momentum Improves Optimization on Riemannian Manifolds
• No-go Theorem for Acceleration in the Hyperbolic Plane
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• A universal framework for learning the elliptical mixture model
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• Hyperbolic Busemann Learning with Ideal Prototypes
• Convergence Analysis of Riemannian Stochastic Approximation Schemes
• Learning Polynomials of Few Relevant Dimensions
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces
• Tangent Space Separability in Feedforward Neural Networks
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• A Brief Introduction to Manifold Optimization
• On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
• From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
• Riemannian stochastic recursive momentum method for non-convex optimization
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning
• Bounding the expected run-time of nonconvex optimization with early stopping
• A Semismooth Newton based Augmented Lagrangian Method for Nonsmooth Optimization on Matrix Manifolds
• Riemannian Proximal Policy Optimization
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• The duality structure gradient descent algorithm: analysis and applications to neural networks
• Manifold Optimization Assisted Gaussian Variational Approximation
• Riemannian Stochastic Hybrid Gradient Algorithm for Nonconvex Optimization