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