# Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 87 references that are in the map.
- First posted on arXiv 26 Nov 2022.

## Builds on (most cited first, 30 of 43)

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group](https://mlsanity.com/paper/1901.08428/) (2019)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [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)
- [Generalization in Deep Networks: The Role of Distance from Initialization](https://mlsanity.com/paper/1901.01672/) (2019)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [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)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization](https://mlsanity.com/paper/1910.10782/) (2019)
- [Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices](https://mlsanity.com/paper/1507.02772/) (2015)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization](https://mlsanity.com/paper/1706.03267/) (2017)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [An accelerated first-order method for non-convex optimization on manifolds](https://mlsanity.com/paper/2008.02252/) (2020)
- [Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1811.08109/) (2018)
- [Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles](https://mlsanity.com/paper/2111.13263/) (2021)
- [R3MC: A Riemannian three-factor algorithm for low-rank matrix completion](https://mlsanity.com/paper/1306.2672/) (2013)
- [Global Riemannian Acceleration in Hyperbolic and Spherical Spaces](https://mlsanity.com/paper/2012.03618/) (2020)
- [Accelerated Gradient Methods for Geodesically Convex Optimization: Tractable Algorithms and Convergence Analysis](https://mlsanity.com/paper/2202.02036/) (2022)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)

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

- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)
- [Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties](https://mlsanity.com/paper/2305.16186/) (2023)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds](https://mlsanity.com/paper/2510.21468/) (2025)

## Abstract (arXiv)

We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We achieve the same convergence rates as Nesterov's accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Crucially, we can enforce our method to stay within a compact set we define. Prior fully accelerated works resort to assuming that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods of limited applicability. For our manifolds, this solves the open question in [KY22] about obtaining global general acceleration without iterates assumptively staying in the feasible set. In our solution, we design an accelerated Riemannian inexact proximal point algorithm, which is a result that was unknown even with exact access to the proximal operator, and is of independent interest. For smooth functions, we show we can implement the prox step inexactly with first-order methods in Riemannian balls of certain diameter that is enough for global accelerated optimization.