TY  - CONF
A1  - Martínez-Rubio, David
A1  - Pokutta, Sebastian
T1  - Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties
T2  - Proceedings of Thirty Sixth Conference on Learning Theory
N2  - 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 \emph{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 (Kim and Yang, 2022) 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.
Y1  - 2023
UR  - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8893
UR  - https://proceedings.mlr.press/v195/martinez-rubio23a.html
VL  - 195
SP  - 359
EP  - 393
ER  -