Towards Riemannian Accelerated Gradient Methods
This work addresses the challenge of efficient optimization on manifolds for applications in machine learning and geometry, offering a computationally tractable alternative to existing methods.
The authors tackled the problem of accelerating gradient methods on Riemannian manifolds by proposing a Riemannian version of Nesterov's Accelerated Gradient algorithm (RAGD), showing that it achieves accelerated convergence for geodesically smooth and strongly convex problems within a neighborhood whose radius depends on condition number and sectional curvature, unlike prior methods that required intractable exact solutions.
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.