Riemannian accelerated gradient methods via extrapolation

Andi Han, Bamdev Mishra, Pratik Jawanpuria, Junbin Gao

Abstract

In this paper, we propose a simple acceleration scheme for Riemannian gradient methods by extrapolating iterates on manifolds. We show when the iterates are generated from Riemannian gradient descent method, the accelerated scheme achieves the optimal convergence rate asymptotically and is computationally more favorable than the recently proposed Riemannian Nesterov accelerated gradient methods. Our experiments verify the practical benefit of the novel acceleration strategy.

Introduction

Optimization on Riemannian manifolds—such as spheres, sets of rotation matrices, or positive definite matrices—is essential for modern machine learning tasks like principal component analysis (PCA), dictionary learning, and optimal transport. While standard Riemannian Gradient Descent (RGD) is a staple, researchers have sought "accelerated" versions similar to Nesterov’s method in Euclidean space.

However, existing Riemannian Nesterov methods face two significant hurdles. First is the computational cost, as they rely on expensive operations like "exponential maps" and "parallel transport." Second is hyperparameter sensitivity, requiring precise knowledge of smoothness ($L$) and strong convexity ($\mu$) constants, which are rarely available in practice. This paper introduces RiemNA (Riemannian Nonlinear Acceleration), an extrapolation-based approach that is both faster and more "plug-and-play."

Methodology: Riemannian Nonlinear Acceleration

RiemNA generalizes "Nonlinear Acceleration" (also known as Anderson Acceleration) to the manifold setting. Instead of simply taking a step in the direction of the current gradient, RiemNA analyzes a window of previous iterates and computes a "weighted average" to predict a more optimal next point.

The algorithm's core technical components include:

  • Weighted Riemannian Averaging: A recursive method to average points on a manifold using retractions.
  • Residual Minimization: Solving a small linear system to find weights that minimize the norm of weighted residuals (gradients) from previous steps.
  • General Retractions and Vector Transport: Unlike previous methods, RiemNA is compatible with general "retractions" and "vector transports." These first-order approximations are significantly cheaper to compute than exact geometric operators.

Experimental Evaluation

The authors evaluated RiemNA on four benchmark manifold optimization problems: the Sphere manifold (leading eigenvector computation), the SPD manifold (Fréchet mean), the Stiefel manifold (Orthogonal Procrustes problem), and the Grassmann manifold (nonlinear eigenspace problem).

Convergence performance on the Sphere manifold comparing RGD, RAGD, RNAG, and RiemNA.

Across these applications, RiemNA consistently demonstrated superior performance:

  • Iteration Efficiency: RiemNA matched or exceeded Nesterov-style methods in iteration counts.
  • Wall-clock Speedup: Due to its reliance on cheaper retractions rather than exact exponential maps, RGD+RiemNA consistently outperformed state-of-the-art methods like RNAG in total runtime.
Wall-clock time comparison on the SPD manifold, highlighting the efficiency of RiemNA.

Key Insights and Discussion

A major theoretical contribution is the proof of asymptotic optimality. RiemNA achieves the optimal $O(1/k^2)$ convergence rate as it nears the solution without requiring prior knowledge of $L$ or $\mu$. Furthermore, the method is geometry agnostic, making it remarkably robust because the acceleration is driven by the sequence of iterates rather than explicit manifold curvature.

Limitations and Future Work

While promising, the current theoretical guarantees focus on local convergence, meaning acceleration is guaranteed once the algorithm is near the optimal solution. Global acceleration remains an open challenge. Additionally, the method introduces a small memory overhead by storing past iterates, and future work aims to extend this extrapolation logic to stochastic Riemannian optimization for handling noisy gradients in high-dimensional settings.

Summary updated

Abstract

In this paper, we propose a simple acceleration scheme for Riemannian gradient methods by extrapolating iterates on manifolds. We show when the iterates are generated from Rieman- nian gradient descent method, the accelerated scheme achieves the optimal convergence rate asymptotically and is computationally more favorable than the recently proposed Riemannian Nesterov accelerated gradient methods. Our experiments verify the practical benefit of the novel acceleration strategy.
BibTeX
@misc{han2022riemannian,
  author = {Andi Han and Bamdev Mishra and Pratik Jawanpuria and Junbin Gao},
  title = {{Riemannian accelerated gradient methods via extrapolation}},
  year = {2022},
  eprint = {2208.06619},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.06619},
}
Figure