Understanding Riemannian Acceleration via a Proximal Extragradient Framework

Jikai Jin, Suvrit Sra
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:2924-2962, 2022.

Abstract

We contribute to advancing the understanding of Riemannian accelerated gradient methods. In particular, we revisit “\emph{Accelerated Hybrid Proximal Extragradient}” (A-HPE), a powerful framework for obtaining Euclidean accelerated methods \citep{monteiro2013accelerated}. Building on A-HPE, we then propose and analyze Riemannian A-HPE. The core of our analysis consists of two key components: (i) a set of new insights into Euclidean A-HPE itself; and (ii) a careful control of metric distortion caused by Riemannian geometry. We illustrate our framework by obtaining a few existing and new Riemannian accelerated gradient methods as special cases, while characterizing their acceleration as corollaries of our main results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-jin22a, title = {Understanding Riemannian Acceleration via a Proximal Extragradient Framework}, author = {Jin, Jikai and Sra, Suvrit}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {2924--2962}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/jin22a/jin22a.pdf}, url = {https://proceedings.mlr.press/v178/jin22a.html}, abstract = {We contribute to advancing the understanding of Riemannian accelerated gradient methods. In particular, we revisit “\emph{Accelerated Hybrid Proximal Extragradient}” (A-HPE), a powerful framework for obtaining Euclidean accelerated methods \citep{monteiro2013accelerated}. Building on A-HPE, we then propose and analyze Riemannian A-HPE. The core of our analysis consists of two key components: (i) a set of new insights into Euclidean A-HPE itself; and (ii) a careful control of metric distortion caused by Riemannian geometry. We illustrate our framework by obtaining a few existing and new Riemannian accelerated gradient methods as special cases, while characterizing their acceleration as corollaries of our main results.} }
Endnote
%0 Conference Paper %T Understanding Riemannian Acceleration via a Proximal Extragradient Framework %A Jikai Jin %A Suvrit Sra %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-jin22a %I PMLR %P 2924--2962 %U https://proceedings.mlr.press/v178/jin22a.html %V 178 %X We contribute to advancing the understanding of Riemannian accelerated gradient methods. In particular, we revisit “\emph{Accelerated Hybrid Proximal Extragradient}” (A-HPE), a powerful framework for obtaining Euclidean accelerated methods \citep{monteiro2013accelerated}. Building on A-HPE, we then propose and analyze Riemannian A-HPE. The core of our analysis consists of two key components: (i) a set of new insights into Euclidean A-HPE itself; and (ii) a careful control of metric distortion caused by Riemannian geometry. We illustrate our framework by obtaining a few existing and new Riemannian accelerated gradient methods as special cases, while characterizing their acceleration as corollaries of our main results.
APA
Jin, J. & Sra, S.. (2022). Understanding Riemannian Acceleration via a Proximal Extragradient Framework. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:2924-2962 Available from https://proceedings.mlr.press/v178/jin22a.html.

Related Material