# Understanding Riemannian Acceleration via a Proximal Extragradient Framework

arXiv: https://arxiv.org/abs/2111.02763 · HTML: https://mlsanity.com/paper/2111.02763/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 4 Nov 2021.

## Builds on (most cited first, 19 of 19)

- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Optimization Techniques on Riemannian Manifolds](https://mlsanity.com/paper/1407.5965/) (2014)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [Adaptive regularization with cubics on manifolds](https://mlsanity.com/paper/1806.00065/) (2018)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [An accelerated first-order method for non-convex optimization on manifolds](https://mlsanity.com/paper/2008.02252/) (2020)
- [An Optimal High-Order Tensor Method for Convex Optimization](https://mlsanity.com/paper/1812.06557/) (2018)
- [Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method](https://mlsanity.com/paper/1706.04680/) (2017)
- [Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes](https://mlsanity.com/paper/1910.12375/) (2019)
- [First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow](https://mlsanity.com/paper/1912.09276/) (2019)
- [No-go Theorem for Acceleration in the Hyperbolic Plane](https://mlsanity.com/paper/2101.05657/) (2021)
- [A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities](https://mlsanity.com/paper/2103.15270/) (2021)
- [Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods](https://mlsanity.com/paper/2102.02045/) (2021)
- [A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives](https://mlsanity.com/paper/2106.15536/) (2021)

## Built on by (most cited first, 3 of 3)

- [Riemannian accelerated gradient methods via extrapolation](https://mlsanity.com/paper/2208.06619/) (2022)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Changes from Classical Statistics to Modern Statistics and Data Science](https://mlsanity.com/paper/2211.03756/) (2022)

## Abstract (arXiv)

We contribute to advancing the understanding of Riemannian accelerated gradient methods. In particular, we revisit Accelerated Hybrid Proximal Extragradient(A-HPE), a powerful framework for obtaining Euclidean accelerated methods citepmonteiro2013accelerated. 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.