Towards Riemannian Accelerated Gradient Methods

Abstract

We propose a Riemannian version of Nesterov's Accelerated Gradient algorithm (RAGD), and show that for geodesically smooth and strongly convex problems, within a neighborhood of the minimizer whose radius depends on the condition number as well as the sectional curvature of the manifold, RAGD converges to the minimizer with acceleration. Unlike the algorithm in (Liu et al., 2017) that requires the exact solution to a nonlinear equation which in turn may be intractable, our algorithm is constructive and computationally tractable. Our proof exploits a new estimate sequence and a novel bound on the nonlinear metric distortion, both ideas may be of independent interest.

arXiv commentPublished in 31th Annual Conference on Learning Theory (COLT'18)

References in corpus (12)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Metric measure spaces with Riemannian Ricci curvature bounded from below
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Global rates of convergence for nonconvex optimization on manifolds
• Stochastic Variance Reduction for Nonconvex Optimization
• A geometric alternative to Nesterov's accelerated gradient descent
• From Averaging to Acceleration, There is Only a Step-size
• Accelerated Methods for Non-Convex Optimization
• First-order Methods for Geodesically Convex Optimization
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Riemannian stochastic variance reduced gradient on Grassmann manifold

Cited by in corpus (16)

• Riemannian Adaptive Optimization Methods
• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Trivializations for Gradient-Based Optimization on Manifolds
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Gradient descent in hyperbolic space
• Accelerated Optimization With Orthogonality Constraints
• Momentum Improves Optimization on Riemannian Manifolds
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
• A universal framework for learning the elliptical mixture model
• Solving Optimization Problems over the Stiefel Manifold by Smooth Exact Penalty Function
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Momentum Accelerates Evolutionary Dynamics
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems