Riemannian Accelerated Gradient Methods via Extrapolation

Andi Han, Bamdev Mishra, Pratik Jawanpuria, Junbin Gao
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:1554-1585, 2023.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Riemannian Accelerated Gradient Methods via Extrapolation %A Andi Han %A Bamdev Mishra %A Pratik Jawanpuria %A Junbin Gao %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-han23a %I PMLR %P 1554--1585 %U https://proceedings.mlr.press/v206/han23a.html %V 206 %X 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.
APA
Han, A., Mishra, B., Jawanpuria, P. & Gao, J.. (2023). Riemannian Accelerated Gradient Methods via Extrapolation. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:1554-1585 Available from https://proceedings.mlr.press/v206/han23a.html.

Related Material