Riemannian Accelerated Gradient Methods via Extrapolation
Andi Han, Bamdev Mishra, Pratik Jawanpuria, Junbin Gao
Abstract
In this paper, we propose a convergence acceleration scheme for general Riemannian optimization problems by extrapolating iterates on manifolds. We show that when the iterates are generated from the Riemannian gradient descent method, the scheme achieves the optimal convergence rate asymptotically and is computationally more favorable than the recently proposed Riemannian Nesterov accelerated gradient methods. A salient feature of our analysis is the convergence guarantees with respect to the use of general retraction and vector transport. Empirically, we verify the practical benefits of the proposed acceleration strategy, including robustness to the choice of different averaging schemes on manifolds.
BibTeX
@InProceedings{pmlr-v206-han23a,
title = {Riemannian Accelerated Gradient Methods via Extrapolation},
author = {Han, Andi and Mishra, Bamdev and Jawanpuria, Pratik and Gao, Junbin},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {1554--1585},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/han23a/han23a.pdf},
url = {https://proceedings.mlr.press/v206/han23a.html},
abstract = {In this paper, we propose a convergence acceleration scheme for general Riemannian optimization problems by extrapolating iterates on manifolds. We show that when the iterates are generated from the Riemannian gradient descent method, the scheme achieves the optimal convergence rate asymptotically and is computationally more favorable than the recently proposed Riemannian Nesterov accelerated gradient methods. A salient feature of our analysis is the convergence guarantees with respect to the use of general retraction and vector transport. Empirically, we verify the practical benefits of the proposed acceleration strategy, including robustness to the choice of different averaging schemes on manifolds.}
}