Averaging Stochastic Gradient Descent on Riemannian Manifolds

Abstract

We consider the minimization of a function defined on a Riemannian manifold $\mathcal{M}$ accessible only through unbiased estimates of its gradients. We develop a geometric framework to transform a sequence of slowly converging iterates generated from stochastic gradient descent (SGD) on $\mathcal{M}$ to an averaged iterate sequence with a robust and fast $O(1/n)$ convergence rate. We then present an application of our framework to geodesically-strongly-convex (and possibly Euclidean non-convex) problems. Finally, we demonstrate how these ideas apply to the case of streaming $k$-PCA, where we show how to accelerate the slow rate of the randomized power method (without requiring knowledge of the eigengap) into a robust algorithm achieving the optimal rate of convergence.

COLT 2018

References in corpus (2)

• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Stochastic Composite Least-Squares Regression with convergence rate O(1/n)

Cited by in corpus (18)

• Riemannian Adaptive Optimization Methods
• Gradient descent algorithms for Bures-Wasserstein barycenters
• Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• Escaping from saddle points on Riemannian manifolds
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• Convergence Analysis of Riemannian Stochastic Approximation Schemes
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Momentum Accelerates Evolutionary Dynamics
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• Riemannian information gradient methods for the parameter estimation of ECD: Some applications in image processing
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• Gen-Oja: A Two-time-scale approach for Streaming CCA