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, Stiefel, or Grassmann manifolds—is a cornerstone of modern computational tasks, including Principal Component Analysis (PCA), matrix completion, and dictionary learning. While Riemannian Gradient Descent (RGD) is the standard tool for these problems, achieving "acceleration" comparable to Nesterov’s methods in Euclidean space has proven difficult.

Existing Riemannian Nesterov methods are often theoretical constructs that are difficult to apply in practice. They typically require precise knowledge of the Lipschitz constant ($L$) and strong convexity parameter ($\mu$), and they rely on computationally expensive operations like the exponential map and parallel transport. This paper introduces RiemNA (Riemannian Nonlinear Acceleration), a simple and efficient strategy to accelerate Riemannian gradient methods by extrapolating previous iterates directly on the manifold.

The RiemNA Framework

Instead of modifying the gradient descent step itself, RiemNA acts as a "wrapper" that takes a sequence of iterates produced by an underlying solver (like RGD) and uses extrapolation to identify a more optimal point.

The Extrapolation Process

  1. Iterate Collection: The algorithm maintains a window of recent points ($x_0, \dots, x_{k+1}$).
  2. Residual Computation: The differences between consecutive points are mapped into a single tangent space using vector transport.
  3. Residual Minimization: A small, regularized linear system is solved to find weights ($c_i$) that minimize the combined residual. This is the "nonlinear" component, as the weights are data-dependent.
  4. Manifold Averaging: The iterates are combined using these weights via a weighted Riemannian average. The authors demonstrate that this can be achieved through a recursive scheme, a tangent space scheme, or the Fréchet mean.

Crucially, the authors prove that this framework maintains acceleration guarantees even when using general retractions and vector transports, which are significantly cheaper to compute than exact geodesic operations.

Key Insights and Advantages

Asymptotic Optimality without Constants

RiemNA matches the optimal convergence rate of Nesterov acceleration as it approaches the solution. Unlike traditional methods, it does so without requiring the exact values of $L$ or $\mu$, making it a "plug-and-play" solution for practical optimization.

Computational Efficiency

Most theoretical Riemannian papers insist on the exponential map for proofs. RiemNA demonstrates that first-order approximations (retractions) are sufficient to maintain acceleration. By avoiding the heavy computational tax of parallel transport and exponential maps, RiemNA achieves significant wall-clock speedups.

Robustness

The method is robust to the choice of the regularization parameter ($\lambda$) and the memory depth ($m$). Experiments suggest that a small memory of 5 to 10 iterates is often sufficient to achieve superior performance.

Experimental Evaluation

The paper evaluates RiemNA across several manifold optimization problems:

  • Sphere Manifold: Computing the leading eigenvector of large symmetric matrices.
  • SPD Manifold: Computing the Fréchet mean of Symmetric Positive Definite matrices.
  • Stiefel Manifold: Solving the Orthogonal Procrustes problem.
  • Grassmann Manifold: Solving nonlinear eigenspace problems (total energy minimization).

In almost all tests, RiemNA outperformed state-of-the-art Riemannian Nesterov methods (such as RAGD and RNAG) in terms of runtime. While the iteration counts were often comparable, RiemNA's iterations are "lighter," leading to faster overall convergence to high precision (e.g., a gradient norm of $10^{-6}$).

Limitations and Future Work

While RiemNA offers significant practical benefits, its theoretical acceleration guarantees are asymptotic, meaning they are most effective as the algorithm approaches a local minimizer. To handle the initial phase of optimization, the authors suggest "safeguarding"—only accepting an extrapolated step if it successfully reduces the objective function.

Future research directions include extending this extrapolation scheme to stochastic Riemannian gradients, which would have significant implications for deep learning on manifolds, and exploring its application to more complex solvers like Riemannian Conjugate Gradient.

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 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.
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