Implicit Riemannian Optimism with Applications to Min-Max Problems
Authors: Christophe Roux
David Martínez-Rubio
Sebastian Pokutta
Venue: ICML 2025 poster (2025)
Keywords: Riemannian Optimization
Optimistic algorithms
Online Optimization
Min-Max optimization
Primary area: theory->online_learning_and_bandits

Abstract: We introduce a Riemannian optimistic online learning algorithm for Hadamard manifolds based on inexact implicit updates. Unlike prior work, our method can handle in-manifold constraints, and matches the best known regret bounds in the Euclidean setting with no dependence on geometric constants, like the minimum curvature. Building on this, we develop algorithms for g-convex, g-concave smooth min-max problems on Hadamard manifolds. Notably, one method nearly matches the gradient oracle complexity of the lower bound for Euclidean problems, for the first time.

Implicit Riemannian Optimism with Applications to Min-Max Problems
Christophe Roux David Martinez-Rubio 123 Sebastian Pokutta" 12
Riemannian optimization methods have many application in machine learning such as hyperbolic embeddings (Sala et al., 2018), hyperbolic neural networks (Ganea et al., 2018; Chami et al., 2019), Gaussian mixture models (Hosseini & Sra, 2015), the Karcher mean (Karcher, 1977), dictionary learning (Cherian & Sra, 2017; Sun et al., 2017), low-rank matrix completion (Vandereycken, 2013; Mishra & Sepul- chre, 2014; Tan al., 2014; Cambier & Absil, 2016; Heidel & Schulz, 2018), (), and optimization under orthogonality con- straints (Edelman et al., 1998; Lezcano-Casale & Martínez- Rubio, 2019).
Abstract
We introduce a Riemannian optimistic online learning algorithm for Hadamard manifolds based on inexact implicit updates. Unlike prior work, our method can handle in-manifold constraints, and matches the best known regret bounds in the Euclidean setting, removing the dependence on geometric constants, like the minimum curvature. Building on this method, we develop multiple algorithms for g-convex, g-concave smooth min- max problems on Hadamard manifolds. Notably, one method nearly matches the gradient oracle complexity of the lower bound for Euclidean prob- lems, for the first time.
In this work, we analyze Riemannian optimization in the online setting where an agent receives an arbitrary, possibly adversarial, sequence of Riemannian loss functions and selects actions before knowing the loss functions. Its goal is to minimize the cumulative values of the losses associated to the actions it chooses, i.e., its regret. In particular, we are interested in optimistic methods, which allow the agent to improve its regret whenever the environment is not fully adversarial by predicting the next loss based on a hint.
1. Introduction
Riemannian optimization refers to the optimization func- tions defined over Riemannian manifolds. Such problems arise when the constraints of Euclidean optimization prob- lems can be viewed as Riemannian manifolds, such as the symmetric positive-definite cone, the sphere, or the set of orthogonal linear layers for neural network. This Rieman- nian formulation enables us to leverage the geometric struc- ture of such problems by viewing them as unconstrained problems on a manifold.
Online optimistic Riemannian algorithms were analyzed by Hu et al. (2023a); Wang al. (2023b). Both works face issues with circular arguments related to the geometry of the manifold. Hu et al. (2023a) consider the constrained setting but can only guarantee the actions to lie in a neighborhood of the constraint set. The size of this neighborhood depends on the step size, which in turn depends on a geometric factor dependent on the neighborhood's s size. Wang et al. (2023b) consider the unconstrained setting but their step sizes depend the diameter of the set in which the iterates stay set via geometric constants, which again influence the size of this set. They address this issue by assuming that the method's iterates stay in a compact set whose diameter is known a-priori.
Further, some non-convex Euclidean problems, such as op- erator scaling optimistic likelihood estimation become geodesically convex, i.e., convex along all geodesics, when viewed as Riemannian optimization problems under the right metric (Allen-Zhu et al., 2018; Nguyen et al., 2019).
'Fqual contribution (arbitrary order). 'uuee Institute Berlin, Germany Technische Universität Berlin. Germany CCarlos University of Madrid, Spain. Correspondence to: Christophe Roux <roux @ zib.de>, David Martinez-Rubic <marrinez-
Such circular relationships between step sizes and other problem parameters, which depend on the size of the set in which the iterates lie via geometric terms occur in many Riemannian optimization settings and lead to unfinished analyses, cf. Martínez-Rubio et al. (2024).
Proceedings of the 42nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Chen & Orabona (2023); Choi et al. (2023); Ajalloeian et al. (2020); Dixit et al. (2019) study implicit online algorithms in the Euclidean setting. However, implicit optimistic algo- rithms have not been developed, even in the Euclidean case.
Most of the non-local notations in this work have a link to their definitions, using this code, such as Exp,, which links to where this notation is defined the exponential map of manifold from point Jr.

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Our optimistic algorithm RIOD is based on two-step im- plicit update rule, i.e., on minimizing a regularized version of the full loss hint function, instead of a linearized ver- sion thereof. This is important since the linear approxima- tions of geodesically convex (g-convex) are neither g-convex nor g-concave. Further, we chose a two-step variant even though there are optimistic methods requiring just one step in the Euclidean setting, since subtracting a full g-convex hint function loss would yield potentially hard non g- convex subproblem.
scent (CRGD) introduced in Hartínez-Rubio al. (2024), we achieve near-optimal gradient oracle complexity of O (LIe/s) and ((L/u) for μ = 0 and μ > 0, respec- tively, for an duality gap, matching Euclidean algorithms up to logarithmic factors. In partieular, the complexity only has logarithmic dependence on Ç, a geometric term arising from the curvature of the manifold, defined in the next sec- tion, for the first time. Note that implementing the CRGD update steps might be hard computational problem. Never- theless, this is surprising result given that in the g-convex and T-smooth minimization setting the best known rates of Ō CLR proven in Martínez-Rubio et al. (2023) do not match the Euclidean rates of O(y LR /E) (Nesterov, 2005), where R is the initial distance to a minimizer.
In contrast to previous works, RIOD can enforce in- manifold constraints without relying on strong assumptions and has regret guarantees independent of geometric terms, matching the regret guarantees of Fuclidean algorithms. Further, the regret guarantees allow for inexact updates under a certain precision criterion, which can be implemented cheaply for smooth losses. Given that our assumption covers the Eu- clidean space as a special case, this algorithm might be of independent interest for the online optimization community.
Implementing RIODA using Riemannian Gradient Descent (RGD) in the unconstrained setting, we improve the com- plexity from (R(("RRR/ /e) (Martinez-Rubio et al., 2024) to Ō({²LR² /E). among the algorithms that do not require the knowledge of the initial distance to the solution.
Application for online Riemannian optimization include online formulations of the Karcher mean, covariance estima- tion and robust subspace recovery (Karcher, 1977; Wiesel, 2012: Zhang, 2015). Another notable application of online optimistic methods is to solve L-smooth and g-convex, g- concave min-max problems. To that end, the problem is interpreted as a two-player, zero-sum game and the strate- gies of both variables are updated based on online optimistic algorithms. This means that both players use gradient based methods and hence adapt their strategy in an incremental fashion. This knowledge can be leveraged using optimism, which leads to faster rates, see Orabona (2019, Chapter 11.5) for an introduction to this approach in the Euclidean setting.
In the constrained setting implementing RIODA using Pro- jected RGD (PRGD), we improve the gradient oracle com- plexity by a factor of Ō(C..5) compared to the prior best rate (Martínez-Ruul
et al., 2023). Furthermore, the algorithm does not require the knowledge of the Lipschitz constant of f in the constraint set. We validate our theoretical results by running experiments on the robust Karcher mean problem in the symmetric positive definite manifold and the hyperbolic space, see Appendix E.
Contributions.
RIOD An inexact Riemannian implicit online op- timistic algorithm for the constrained setting on Hadamard manifolds matching the best known Eu- clidean regret bounds, while not relying on strong as- sumptions present in prior works. The regret bound does not depend on Ç, a term arising from the geometry of the manifold.
Applications of g-convex, g-concave and L-smooth min- max problems in machine learning include the robust Karcher mean, distributionally robust linear quadratic con- trol and more generally the distributionally robust version of any finite-sum, g- g-convex optimization problem (Zhang et al., 2023; Jordan et al., 2022; Taskesen et al., 2023). Further, we believe that Riemannian min-max algorithms represent a promising method to solve distributionally robust opti- mization problems with ambiguity sets based on parametric probability distributions as their parameter space can often be seen as Riemannian manifold, see (Brigant et al., 2023). Other Riemannian min-max problems, which do not satisfy the g-convex, g- g-concave and L-smooth conditions include geometry-awan robust PCA and projection-robust optimal transport (Horev et al., 2017; Jiang& & Liu, 2023).
RIODA An inexact Riemannian implicit algorithm for min- max optimization on Hadamard manifolds with and without in in-manifold constraints.
Different implementations of the update rules of RI- ODA using first-order methods, which improve on prior works by either reducing the complexity or not requir- ing the knowledge of certain parameters. Notably, one variant nearly achieves the optimal Euclidean gradient oracle complexity, by removing the dependence on Ç up to log factors This result is in contrast to smooth g- convex minimization, where we know that at least there is an extra curvature survature-dependent dependent additive penalty, linear on Ç. over the rate of the Fuclidean-optima accelerated solutions, cf. (Criscitiello & Boumal, 2023).
Building on our online algorithm RIOD, we introduce RI- ODA, an inexact and implicit min-max algorithm for pos- sibly constrained problems based on updating both vari- ables based on the RIOD update rule. Implementing the update rules using Composite Riemannian Gradient De-
2

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
1.1. Preliminaries
0 and S, = 1 otherwise, and 6, def TVEmax cot(r /kmax)
if Rmmx and 6, der otherwise. is S 1 Sr-
A Riemannian manifold (M, g) is real C manifold M equipped with Riemannian metric g. which assigns smoothly varying and positive definite inner product to each E .M. For E M, denote by T.M the tangent space of M at x. For vectors U, w E T,M, we use (v, w)x, and ||l| =s V(u, v)2 for the metric's inner product and norm, and omit x when it is clear from context. A geodesic of M of unit speed that is work.
We denote the closed Riemannian ball of center x and radius by B(z, Px(x)) arg minge d(y, x) denotes the metric projection onto a set X. Note that for some sets, such as the Riemannian ball, Px can solved in closed form (Martinez-Rubio & Pokutta, 2023). The big-O notation O()) omits log factors. We refer Petersen (2006); Bacák (2014) for an overview of the Riemannian geometry used in this
length is a curve 7 : [0, E + locally distance minimizing.
The exponential map Exp3- : TTM - M takes a point E M, and a vector e E T.MM and returns the point y we obtain from following the geodesic from x in the direction for length ||o|], if this is possible. We denote its inverse by Log, (-). It is well defined for uniquely geodesic mani- folds, i.e., manifolds where every two points in that space are connected by one and only one geodesic, so we have (v),, = y and Log, (v) = u. We denote the distance between two points by d(xry) y) = [[Tog, (v)l.. The manifold M comes with natural parallel transport of vectors be- tween tangent spaces, that formally is defined from the Levi- Civita connection V. In that case, we use [v) Ty to denote the parallel transport of a vector in T.M to TyM along the unique geodesic that connects x to y.
1.2. Related Work
Online Convex Optimization (OCO). Online optimiza- tion is modeled as sequential game between an agent and its environment, where in each round t the agent chooses an action 2, from some convex set X. Then, the environment reveals a convex loss function & and the agent pays the loss (x+). Note that no assumptions are made about the environment, it could also act adversarially. The goal of the agent is to choose the sequences of action I; such that they minimize the difference between the cumulative losses paid by the agent and the losses associated to fixed ac- tion X, i.c., its regret, RT(u) def Ei= ke(xz) f.(u). While the OCO setting covers wide range of settings, it can be overly pessimistic as real-world settings are rarely fully adversarial. The goal of optimistic methods is to im- prove the regret in settings that are not fully adversarial by predicting the next loss based on additional information about the environment, encoded by a hint. The regret of these methods depends on how well the hint approximates the real loss.
The sectional curvature of a manifold M at a point x E M for 2-dimensional space V C T.M is the Gauss curvature of (V) x. A Hadamard manifolds is complete simply-connected Riemannian manifold of non- positive sectional curvature, which is in particular uniquely geodesic.
A set X' is said to be g-convex if every two points are connected by a geodesic that remains in X. For two points z, E X. let 7 : [0 + M be a constant speed geodesic joining x and y such that 7(0) (11 y, then call function f g-convex in X if ((((()) S (f(x) + (1 ())(2) for all æ, X. A differ- entiable function is j-strongly g-convex (resp., L-smooth) in X, if we have ! (resp. 2) for any two points y E X:
Another development in online optimization is the use of implicit updates. Typically, online optimization algorithms compute their next action minimizing the loss linearized at 2, plus a regularizer. Implicit algorithm instead minimize the full loss function plus a regularizer, which is typically not solvable in closed form, hence the name. Recent works show improved regret guarantees for implicit versions of on- line mirror descent and follow the regularized leader (Cam- polongo & Orabona, 2020; Chen & Orabona, 2023). Some works also provide regret guarantees that allow for inexact solutions of the implicit updates (Chen & Orabona, 2023; Choi et al., 2023; Ajalloeian et al., 2020; Dixit et al., 2019).
and
pd(a, (0([,,))' 4) 1 2
2 Ld(x,y)²
Log,
(oog.()))
2
The function g-convex if μa = 0. Note the dependence on X' is important, since for j--strongly g-convex and L- smooth function, the condition L/u depends on the size of X (Crisciticllo & Boumal, 2023, Proposition 53). A function f is G-Lipschitz in X if (x) f(v)l Gd(x,y)
Online Riemannian Optimization. The OCO framework has been extended to the Riemannian setting for g-convex loss functions. Bécigneul & Ganea (2019) provide O(VT) regret guarantees for adaptive online algorithms on Carte- sian products of Riemannian manifolds. Wang et al. (2021) provide regret bounds for Lipschitz and g-convex Rieman- nian online optimization in the full information as well as the bandit and two-point feedback setting. Hu et al. (2023b)
for all x, y E X.
Given r > 0, and a uniquely geodesic Rieman- nian manifold M with sectional curvature bounded in [Kminn [m Then, we define the geometric constants S,
T TV [ [ coth(r (Irmm = O(1 + +r rrr/l (aaaa) if Kyiin <
3

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
analyze projection-free Riemannian methods in Hadamard manifolds using a linear minimization separation oracle in both the full-information as well as the bandit setting. Maass et al. (2022) provide regret guarantees for zeroth- order methods in Hadamard manifolds.
Table I: Comparison of Riemannian online algorithms. Our contribution is in bold. The entries in column Rr denote the regret, where r) > 0 is parameter chosen by the algorithm. In column X, // indicates that the algorithm can enforce constraints. M denotes the manifolds, where H denotes Hadamard manifolds, E denotes the Euclidean space and M denotes general Riemannian manifolds. GGarantees in terms of improper regret. The geometric term Ç. 6 are with respect to a domain which is not guaranteed to be bounded.
Hu et al. (2023a) introduce an optimistic algorithm for Hadamard manifolds with in-manifold constraints where the hint is an arbitrary vector in the tangent space of secondary iterate sequence M2 E M. This method achieves improper regret bounds of OnςVT + D²), where VT - E (b)())) Mell measures how well the hint predicts the loss functions. Improper regret is a relaxed notion where the agent's 's actions may lie outside the con- straint set while the comparator must remain inside. Since the algorithm cannot guarantee that actions stay within the constraint set, a circular dependency arises: the size of the neighborhood around the constraint set depends on the step size, which in turn depends on function properties and ge- ometric factors within this neighborhood. Consequently, it is unclear whether improper regret bounds translates to classical regret bounds.
RT 0 D2 + [V1)
X
M
RIOD
/
H
0 3
O-RCEG [HGA23]12
+ (VT
X
H
ROOGD [WYH+23]
O ne" (V, B
X
M
OOMD [RS13]
o + nVF
/ E
Table 2: Comparison of Riemannian min-max algorithms for ju-strongly g-convex, strongly g-concave and L-smooth problems. The entries of μ 0 and μ > 0 contain the convergence rates for the two settings. The entries in col- umn M denote the manifolds, where H denotes Hadamard manifolds and M denotes general Riemannian manifolds. In column X. / indicates that the algorithm can enforce constraints. In column R? and G?, / means that the algo- rithm can be run without knowledge of the initial distance R def d(z1, x²) + d((1,, y² to a solution and Lipschitz con- stant G of the function in the optimization domain, respec- tively. Note that D refers to the diameter of the constraint set and R def G/T. + D. 'The iterates are not guaranteed to stay in a bounded domain. "In addition, they achieve a last-iterate rate of O So_ LB for μ === 0. 'The algorithm b g²
Wang al. (2023b) prove regret optimistic regret bounds for general Riemannian manifolds without in in-manifolds con- straints. They consider the specific case where the hint function is M₁-- = ( is fixed to the loss gradient from the last iteration. Therefore, their regret guarantee O(D² + 17 s,sp((p++)) scales with the gradient variation tp
V+ def Ei= max,ex [[V[(x)) - (x)). Further, the step size of the algorithm depends on the size of the optimization domain via geometric terms, which again in- fluences the size of the optimization domain, leading to circular relationship. They rely on the assumption that the iterates stay in a pre-defined domain without a mechanism of enforcing it. Since the loss functions change in every round, this assumption does not need to hold in practice.
has faster rates in the fine-grained setting where the strong g g-convexity and smoothness constants can vary between the variables. *Mattínez- Mubioo et al. (2023) showed that the iterates stay in a bounded set.
Riemannian Min-Max Algorithms We limit our discus- sion to the smooth and g-convex, g-coneave setting. Zhang et al. (2023) introduced Riemannian Corrected Extra Gra- dient (RCEG), a variation of the Euclidean Extra Gradient (EG) algorithm and showed convergence rates, that are op- timal up to geometric factors, for unconstrained g-convex, g-concave min-max problems on general Riemannian man- ifolds. Jordan et al. (2022) extended the analysis to the j--strongly g-convex, g-concave setting. Both works rely on the assumption that iterates of RCEG stay in bounded domain without a mechanism to enforce it. Martínez- Rubio et al. (2023) remove this assumption by showing that the iterates of RCEG naturally stay in a compact set around a solution without impacting the rates by modifying the step size. Further, they introduce their algorithm RAMMA for Hadamard manifolds, which achieves faster rates with
Algorithm /= ==
#>0 0
M X
R?
G?
RIODACRGD
0 o(Solat)
H V / /
RIODAPRGD
/ /
RIODARGD
ŌlCR Lie
OIGH
H X / /
[MRP24]
Ö(c Lie)
Ö(ck) 0(5)
H X V V
[CJL+23]]
M X
[WYH+23]
o
Ga Lnn
M X X X
by
[HWW+23)3
o
Sa
LR
Ö LIsA + R² Kmmn)
M X X X
pdR
[MRC+23]]
4.5 L.
olsasb 4 L n o Vinl Vonk
H V X X
[MLV22]
M X x
[ZZS23]
O
V Vans
M X x /
4

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
respect to function parameters in the fine-grained settings, where the smoothness and strong g-convexity parameters can vary between variables at the cost of worse dependence on Ç. They achieve, among others, the optimal O (1/VE) rates with respect to 6 for the strongly g-convex, g-concave setting. While RAMMA can handle in-manifold constraints, the algorithm has five loops, making it complex to imple- ment. Further, requires the knowledge of the Lipschitz constant G' in the constrained setting and the initial distance to solution R in the unconstrained setting,
consist of minimizing
Σ (eis (z))), (Me, Loge, (z)) + d(z,, x)
21j
where l,. 2y and M, refers to the loss, the action and the hint in round t. This function is neither g-convex nor star g-convex in general as each linearized function is only star g- convex with respect one point. On the other hand, it is pos- sible to implement OFTRL without linearizing the loss func- tions, i.e., minimizing Ei= (xx + (xx) + 2n) d(xz, =z)².
The following works consider the more general case of vari- ational inequalities with monotone and Lipschitz operators, which encompass smooth and g g-convex, g g-concave min- max problems as special cases. Hu et al. (2023c) introduce two variants of the EG algorithm in general Riemannian manifolds, focusing on last-iterate convergence in the g- convex, g-concave setting. Cai et al. (2023) show linear convergence rates independent of geometric terms such as Ç in terms of the gradient norm in general Riemannian mani- folds. However, they rely on the assumption that the iterates stay in a bounded domain without a mechanism to enforce it. Martinez-Rubio et al. (2024) introduce an inexact proximal point algorithm achieving accelerated rates. Implementing their update rule using the algorithm by Cai et al. (2023), they show that the iterates naturally stay in bounded do- main and achieve accelerated rates without requiring prior knowledge of the initial distance to a solution, for the first time.
If the loss functions 4 and the hint function é are g-convex, the update rule is also g-convex. Further, the analysis of OFTRI, can be extended the full-loss setting, both in the Euclidean and Riemannian setting. However, this approach is computationally impractical as it would require minimiz- ing the sum of an increasing number of functions, making each iteration progressively more expensive to implement.
The original OOMD algorithm, due to Chiang et al. (2012) and further generalized by Rakhlin & Sridharan (2013b), is based on updating two iterate sequences, referred to as the primary and secondary iterates é, and x4, where the agent chooses the primary iterates 7, as actions. After the loss is observed in round t, the secondary iterate is updated based on the classical online mirror descent rule, i.e., T++1 + arg min, ( (z))), + 27 || =z.l2. Then, the primary iterate is updated by ut+1 f arg min, (Me, 2²) + 2n ||
Z(+1 1|? ensuring that the results stays close to the secondary iterate. Note that the secondary iterate is independent of the primary iterate, mcaning that the agent always maintains a more conservative action from which it can compute an improved action based on the hint. This way the agent can benefit from the hint without accumulating errors arising when the hint does not perfectly predict the next loss. The method in Hu et al. (2023a) is based on this approach.
Lastly, lower bounds specific to Riemannian optimization where established in (Hamilton & Moitra, 2021; Criscitiello & Boumal, 2021; 2023). These bounds hold for the L- smooth and g-convex minimization problem, which is a special case of g-convex, g-concave and T-smooth min-max optimization, and thus they apply to our min-max setting.
2. Riemannian Implicit Optimistic Online Gradient Descent
Joulani et al. (2017) introduced a single-iterate OOMD variant that corrects prediction errors by subtracting the previous round's hint at each iteration, i.e., I++1 + arg m (xr) + M,- M,-1, + 3 || x2+1 12 thereby removing the need for secondary iterate. Wang et al. (2023b) adapted this approach to the Riemannian set- ting for the special case where M,- = V[, by parallel- transporting the correction term to the tangent space of the current iterate, i.e. F++1 < arg min,
Before discussing the technical details of RIOD, we present the motivations underlying its design. There are two fam- ilies of online optimistic algorithms, namely optimistic bollowtte-regularize--lee
(OFTRL) (Rakhlin & Sridha- ran, 20)3a) and optimistic online mirror descent (OOMD) (Chiang et al., 2012; Rakhlin& & Sridharan, 2013b).
(2V(, (2V(( Te 1 (x) Logz, (I)) + 27 _,d(,, 12
In the Riemannian setting, a function linearized at a point E E M is defined with respect to the tangent space T&M star g-convex (and
Neither method can easily be extended to enforce in- manifold constraints. Recall that enforcing constraints is imperative for us since we aim to design an algorithm that does not suffer from a recurrent relationship between the size of the optimization domain and the step size. In general, the analysis of algorithms enforcing in mn-aniifldd constraints can be challenging in Riemannian manifolds. For manifolds
and is not g-convex. However, star g-concave) at T. that is, convex (concave) along the geodesic going through x. Thus, the OFTRL update rule for the action in round l. + 1 in the Riemannian setting would
5

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
with positive curvature, the metric projection is a non- expansive operator (Wang et al., 2023a, Section 6.1). Even in Hadamard manifolds, where the metric projection is non- expansive, the analysis remains challenging. Indeed, the first proof of linear convergence of PRGD for constrained strongly g-convex and smooth minimization problems in Hadamard manifolds without any non-standard assumptions was only recently established (Martínez-Rutle Rubio et al., 2023).
removing the dependence on <p. matching the best known Euclidean rates.
We also establish dynamic regret bound for RIOD in The- orem 7, which compares the agent's 's actions against se- quence of comparators rather than a single fixed comparator.
Theorem 1 (RIOD). [4] Let M be a Hadamard manifold
with sectional curvature in mimin 0). Further, for t E [T], let the loss and hint functions l,,4, :M - R. be g-convex, and L-smooth in a compact and g-convex set X S M with D def diam(X)) For nj > 0 we have for any u E X that
To address the challenges arising from the constraints, we propose an implicit algorithm based on the two-step OOMD, where the loss functions are not linearized. We do use a two-step approach in order to obtain a hint-correction term which makes the subproblems g gocve...
3D2
T
RT(u)= S 2m
+
In our algorithm RIOD, &e and zt serve as primary and sec- ondary iterates respectively. After playing Tt the algorithm computes the secondary iterate rt+1 via an implicit gradient step on the loss function & received that round. Rather than playing - 1 in the next round, the agent selects a hint func- tion l to predict 1++1 and takes an implicit step on that function to determine the next action ø++1- As in OOMD, the secondary iterates 24 are independent of the primary iter- ates T. thus preventing error accumulation from imperfect hint predictions.
This result assumes that the hint function & also satisfies smoothness and g-convexity, as 4. In the linearized setting, the hint function is typically derived from the gradient of a function, such as the loss from the last round, as we do in our minmax application, making this a reasonable assump- tion. Further, the smoothness assumption can be removed when exact minimizers of the subproblems are found, as smoothness is only required to control the error induced in the inexact case.
Algorithm 1 Riemannian Implicit Optimistic Online Gradi-
We now discuss how the update rules in Lines 4 and 6 can be implemented up to the required precision. Importantly, in the online setting, the regret depends only on the cumu- lative cost Σ i (x paid for the agent's 's actions, and is independent of the gradient oracle complexity. Note that & and E, are T-smooth and g-convex in X' by assumption. The regularizer 1/2 2z,² is ((D/n)-smoot and (l/n)-strongly g-convex, cf. Corollary 16, and hence L, and L. are both (1/n) L/nn-strongll g-convex and (L+ + (p//)///soooo functions. Therefore, we can efficiently implement the update rule us- ing PRGD or CRGD, two minimization methods with linear convergence rates in this setting, defined by the following update rules. For L-smooth function F' M + R.
ent Descent (RIOD)
Input:
Compact constraint set X' C M with diameter D, sectional curvature lower bound Kmii initial point i E X. smoothness constant L of loss and hint function & and e,, and proximal parameter rj > 0.
Definitions:
The alg. does not compute these quantities.
Exact solutions:
duf
arg min [x(x)) duf (,(x) + d(x x()),
2m
xEx
del
arg mig (x) del lx(z) + 1 d(x, 21)3}
27
xEX Precision parameter:
E, def max (1+1) (5 22"
48/6 +8 10)
F++1 Px (Exp., (-L-VF(x))),
(PRGD)
87
1: & - 0
and for composite function F def f + g
2: for 1= T do
3: Choose l
Ls
3441 f- arg min ((nnn((([(xx)))))) Loga, (v))+ d( 2 +g()))
4: Play ãe + (exd(xr,
of L.(x) in X
yEX
2
5: Receive C,
(CRGD)
6: Fe+1 + (f,d(2,, (2) miniiiiee of I4(x:) in X
where ʃ is -moothh see Appendix D.2 for more details. Note that L, and L, have condition number Ln + -Cp In comparison, the regularizer is (1/n) "n)-soooylly convex and smooth and the condition number becomes L1) in Euclidean space. This means that the curvature of the manifolds in- troduce an extra dependence on { since the convergence rate of PRGD depends on the condition number. We can circumvent this issue by leveraging the composite structure
7:
end for
The following result shows an optimistic regret guarantee for Hadamard manifolds with in-manifold constraints, im- proving on Hu et al. (2023a), as it can enforce the iterates to stay in X' and therefore achieves classical regret bound in- stead of an improper one. Further, the regret improved by
6

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
of b and L, using CRGD, as its convergence rate depends on composite condition number, in this case the smooth- ness constant of & and & divided by the strong g-convexity constant of the regularizer, i.e., Lnj. Implementing each step of CRGD requires solving a potentially more expensive subproblem than PRGD. The subproblem in PRGD can be implemented easily at the cost of introducing a dependence on ( on the computational time of the algorithm. In the fol- lowing statement, specify the gradient oracle complexity of implementing the implicit update steps using PRGD and CRGD.
A common method to solve min-max problems is to use proximal algorithms (Tseng, 1995), which requires solving regularized min-max problem at every iteration. However, for constrained min-max problems, we are not aware of any explicit method providing convergence rates. In contrast, RIODA only requires access to a g-convex minimization method, making it possible to implement the update rule using existing methods. The only other Riemannian min- max method that can handle constraints RAMMA (Martínez- Rubio et al., 2023) is also based on reducing the min-max problem to series of minimization problems.
Corollary 2 (Implementing RIOD). [1] For the implemen- tation of the update rules in Lines 4 and 6 of Algorithm 1, we require Õ((Ln + R)) gradient oracle calls to l and Ee at iteration t using PRGD or Õ(1 + Ln) using CRGD (this includes a logarithmic dependence on ((mma)). Here G/L+ D, where G is the Lipschitz constants of & and l, in X. Note that these implementations do not require the knowledge G.
Theorem 3 (RIODA). I Let M, be Hadamard man- iffods with sectional curvature in [Kmin: OJ and X C M, Y C N be compact and g-convex sets. Consider the J : M N - R. which is g-convex, g-concave and L-smooth in X x y. Further, let (x",8") be a saddle point of (P) and (ăT, ûT) be the ouiput of Algorithm 2 after T iterations. Then have f fārr,y") f(x", .yr) S after T = BLL'1 I iterations, and T = 17 log ALR8 1. if f
R def
P
is also p-strongly g-convex, strongly g-concave in X x V.
Since l, and & are differentiable in the compact set X' they are automatically Lipschitz continuous, so this does not need to be assumed separately.
In order to obtain the full gradient oracle complexity of RIODA, we need take into account the number of gradient evaluations required to compute the update rule at every iterations. This is different from the online setting where we mainly care about regret which does not necessarily coincide with the gradient oracle complexity.
3. Min-Max Optimization
Consider the following possibly constrained min-max opti- mization problem
In the following, we show that similarly to RIOD, the update rule can be implemented efficiently. In particular, by our choice of 1) = 1/(4L), the condition number of the sub- problems becomes 1 + <n. and the composite condition number becomes 1/4.
min max fxx, v)
(P)
ZEA yEy
where f is g-convex, g-concave and L-smooth and X C M and y C N. We call a function f g-convex, g-concave in X x y if f(:.g) and -f(x,-) are g-convex for all r E X' and y E V, and L-smooth X' x y if v. y), V (z, -). (z,(z,)), Vyf(-y) are L-Lipschitz for all E X and y E V. We write (x", ,y²") for solutions of (P), R d(x),=") + d(yi,y") y²) for the initial distance and, if finite, D det di) + diamn))).
Corollary 4 (Implementing RIODA). [1] We use the nota- tion from Algorithm 2. For the implementation of the update rules in Lines 2 and 3 of Algorithm 2, we require Ö(C D& R) gradient oracle calls per iteration using PRGD or Õ(1) using CRGD (this includes logarithmic dependence on ((mmin)). ). Here R. del
G/L+ D. where G is the Lipschitz
constant of f in X x y. We refer to these algorithms as RIODAPRGD and RIODACRGD. respectively. Note that these implementations do not require the knowledge G.
We introduce a new method to solve (P) based on updating r and y in parallel using RIOD. We make the following vari- able choices for x: Te + Tez Fe +- Te, (((x:) < f(x Dt), (x(x) + fax 31) and u & I². For y. we set F4, + Vt. T + Mr. (x)) ff v). ((x) + f( v). u + y² We refer to the resulting algorithm as Riemannian Implicit Optimistic Gradient Descent-Ascen (RIODA),
Since the update rule of ã, is independent of Tt. both steps can be implemented in parallel. The same holds for r++1 and M++11
The rates of RIODAPRGD improve over RAMMA (Martínez- Rubio et al., 2023), the only other method for constrained, smooth and g-convex, g-concave min-max problems, by a factor of Ō(c -3.5) and also do not require the knowledge of the initial distance It and the Lipschitz constant G.
app-op arg min, (f(x, 31) 2, d(z, ) 5.+ aapppoxx arg max,, (f v) 2n d(y. yz)² }
2+41 + approx. arg min,, (f(x,, 0.) 2n d(z, 2}
1/+1 approox arg max, ,, (f y) 2n d(y. ))
We can also use RIODA to solve (P) without in manifold constraints as a reduction from RIOD. While RIOD requires
See Algorithm 2 for a detailed description of the algorithm.
7

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
compact constraint, the reduction works because we can show that the iterates of RIODA naturally stay in a ball around solution (x", y²"). Hence, one can add any hypo- thetical constraints which contain this ball without modify- ing the algorithm as they are guaranteed to never be active.
This means that the rates of RIODACRGD improve over the prior state of the art in the constrained setting by O(S2²).
We empirically validate our theoretical results in Ap- pendix E on constrained formulation of the robust Karcher mean problem, testing RIODApRGI on both the symmetric positive definite manifold and the hyperbolic space.
Theorem 5 (RIODA unconstrained). [4] Let M, .N be Hadamard manifolds with sectional curvature in min 0). Consider the bi-fumction f : .M x N + R. which is g- convex, 8-concave and I--smooth in 2- = B(x", ,8)) x Byy", 88)), where (x",y") is a saddle point of f. Then the iterates of Algorithm stay in Z. Let (IT. be the output of Algorithm 2 after T iterations. Then we have [(T "r² ) - [xx" (1)) S E after T = [ iterations and T = 177
It might seem that the nearly curvature- -nnppdddrd-deeeeeeentt rates of T ( and T = PLLpp) for f 0 and μ > O, respectively, achieved by RIODACRGD, are incompatible with existing lower bounds. Indeed, Criscitiello & Boumal (2023) established a lower bound of T = 52(CR) gradient oracle queries for L-smooth and g-convex minimization problems in the hyperbolic space, which is special case of our g- g-convex, g-concave and L-smooth min-max setting,
(2LR²) 1 if f is in addition p-strongly g-convex, strongly g-concave in Z.
-1 log
For μ 0, the lower bound assumes that E = OLR2 /SR), which implies that our upper bound of T = Ö(LRR) /e) is larger than f2(SR), showing that the lower and upper bounds are consistent. Note that the lower bound is based on a func- tion defined in the hyperbolic space, where the initial gap Ö ((TTt/CR) (Criscitiello & Boumal, 2023, Proposition 13), meaning that their assumption on is justified.
In the following, we quantify the complexity of implement- ing the update rules using the minimization algorithms RGD, defined by the update rule for a L-smooth function
F++1 + ExP22 (-I.-VV)<t:)),
and CRGD, see Appendix D.2. We use CRGD for un- constrained problems even though the analysis only covers the compact case, since the composite condition number of Lt, i.e., Ln = 1/4, is smaller than one and we show that in this case, the distance of the iterates of CRGD to the optimizer is non-increasing Corollary 24. Hence we can add a hypothetical constraint which contains a ball around the optimizer with radius slightly larger than the initial distance to the optimizer. this is guaranteed to never be inactive.
For μ > O, we note that the condition number of func- tions in the hyperbolic space in a ball of radius I is lower bounded by T//1 2 Sr (Martínez-Rubio, 2020, Proposi- tion 29). Hence our upper bound does not contradict the lower bound. Criscitiello & Boumal (2021) also develop similar lower bounds for the case μ > 0 in broader class of Hadamard manifolds. A similar argument via (Crisci- tiello & Boumal, 2023, Proposition 53) shows there is no contradiction with our bounds either.
Corollary 6 (Implementing RIODA - unconstrained). [L] Consider the setting of Theorem 5. Assume in addition that is g-convex, g-concave and L-smooth in B(x", x B(y", .8). Then we require (1) gradient oracle calls for implementing the update rules in Lines 2 and 3 of Algo- rithum 2 using CRGD (this includes logarithmic depen- dence on (Fmial) and the iterates stay in that set. If f is g-convex, 8-concave and L-smooth in B(x" D) B(v", D) with D det R(13CRR + +9), then we require Ō(C)) gradient oracle calls using RGD and the iterates stay in that set. We refer to these algorithms RIODACRGO and RIODARGD respectively. Neither method requires prior knowledge of the initial distance to the saddle point R.
This shows that while the rates of RIODACRED do not ex- plicitly depend on CR (up to a log factor), they inevitably have an implicit dependence on the geometry, which is due to the fact above regarding the minimum condition number for this class of problems depending on the geometry. For well-conditioned functions or if the required precision is not too high, the hardness arising from the geometry dominates whereas whenever L/p p >> C2 or LR2 / >> <R the hardness arising from the function dominates.
4. Conclusion
We presented RIOD, a new optimistic online learning al- gorithm for Riemannian manifolds which can handle in- manifold constraints and achieves regret bounds that match the best known Euclidean rates. Based on RIOD, we devel- oped RIODA, novel algorithm for min-max optimization on Riemannian manifolds. We proposed multiple implemen- tations of RIODA, with one variant achieving convergence rates that match the Euclidean rates up to logarithmic factors, for the first time.
Compared to RIPPA (Martínez-Rubio et al., 2023), the only other min max algorithm which does not require knowl- edge of R, the complexity of RIODARGD is reduced by a factor of Ō(CH). The rates of RIODACRGD recover the op- timal Euclidean rates and are independent Ç, up to log fac- tors. Further, note that implementing the subroutines of RAMMA with CRGD leads to total oracle complexities of O LIe and O ( for y=0 and p>00, respectively.
R 5
8

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Impact Statement
age geomstats. ACM Trans. Math. Softw. 49(4:344:1 34:26, 2023. doi: 10.1145/3627338. URL https:
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Cai, Y., Jordan, M. I., Lin, T., Oikonomou, A., and Vlatakis- Gkaragkounis, E.-V. wrwaatur--indeenddee last-iterate convergence for games riemannian manifolds. arXiv preprint arXiv:2306. 6611,, 2023.
Acknowledgements
This research was partially funded by the Research Campus Modal funded by the German Federal Ministry of Educa- tion and Research (fund numbers 05M144ZAM. well the Deutsche Forschungsgemmiischattt (DFG) through the DFG Cluster of Excellence MATH (EXC-
Cambier, L. and Absil, P. Robust low-rank matrix com-
pletion by Riemannian optimization. SIAM Scientific Computing, 38(5), 2016. doi: 10. 10.1137/15M10021153.. URL httts: http:/::///ooo//////////// 10.1137/15110025155555 025153.
2046/1, project ID 390685689). David Martínez-Rubio was partially funded by the project IDEA-CM (TEC-2024/COM-
Campolongo, N. and Orabona, F. Temporal variability in implicit online learning. In Advances in Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems 2020,
89).
References
NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: https: http::///proceelnggsneeeiige
Ajalloeian, A., Simonetto, A., and Dall' Anese, E. Inex- act online proximal-gradien method for time-varying convex optimization. In 2020 American Control Con- ference (ACC), pp. 2850-2857, 2020. doi: 10.23919/ ACC45564..020.9147445
paper/2020/hant 9239ee199844BBccc311114000022223 Abstract.html.
Chami, I., Ying, Z., Ré, C., and Leskovec, Hy- perbolic graph convolutional neural networks. In
Alimisis, F., Orvieto, A., Bécigneul, G., and Luc- chi. A. A continuous-time perspective for mod- eling acceleration in riemannian optimization. In The 23rd International Conference on Artificial Intel- ligence and Statistics. AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], pp. 1297-1307, 2020. URL httt:://proceednns..m..... v1 08/08/aa m00niis220ahtmm
Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14 8-14, 2019.
2019, Vancouver, BC, Canada, pp- URL https://rocceeding...ee
paper/2019 9/ 9/has// 10577/0eaadddeecccccdddaa0000 Abstract.html.
Allen-Zhu, Z., Garg, A., Li, Y., de Oliveira, R. M., and Wigderson, A. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Diakonikolas. I., Kempe, D., and Henzinger, M. (eds.), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 172-181. ACM, URL https:
Chen, K. and Orabona, F. Generalized implicit follow-the-reeee www.tthe-regulaize---eeeooo leadder In International Confer- ence on Machine Learning. ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, pp. 1826-4838, 2023. URL htt.httss//prrccediigee wttp:/ss......prs//2/22.222 chen23t.htm..
2018. doi: 10. 000114433187453318888 //doi.org//ttio 0.1 45/ 31555//11888555533
Cherian, A. and Sra, S. Riemannian dictionary learning and sparse coding for positive definite matrices. IEEE Trans. Neural Networks Learn. Syst. 28(12):2859-28 22,1, 2017. doi: 10. 10.1109/TNNLS.2016 206622601111677 URL https:/ http://.....00/r0000222222222330
Bacák, M. Convex analysis and optimization in Hadamard spaces, volume 22. Walter de Gruyter GmbH & Co KG, 2014.
Bécigneul, G. and Ganea, O. Riemannian adaptive optimiza- tion methods. In 7th International Conference Learn- ing Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: / //openreview.net// wtt.://ett/orrmmmddr.eee.c.
Chiang, C., Yang, T., Lee, C., Mahdavi, M., Lu, C., Jin, R., and Zhu, S. Online optimization with gradual variations. In COLT 2012 The
25th Annual Conference on Learning Theory, June
25-27, 2012, Edinburgh, Scotland, pp. 6.1-6.20,
Brigant, A. L., Deschamps, J., Collas, A., and Miolane,
2012. URL
N. Parametric information geometry with the pack-
v23/ wwwpchhaa///c/cccc hawgg///chhagg2.....
9

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Choi, W., Lee, M.-S., and Yun, S.-B. Inexact online prox- imal mirror descent for time-varying composite opti- mization. CoRR, abs/2304.04710, 2023. URL https:
Horev, I., Yger, F,, and Sugiyama, M. Geometry-aware principal component analysis for symmetric positive def- inite matrices. Mach. Learn. 106(4):493-222, 2017. doi: 10. 10.1007/S100944006--5660 doi.org/ 0.100.0.000//11111111
/ //arxxi.crg/aaae
URL https: 6-5005-5.
Criscitiello, C. and Boumal, N. Negative curvature obstructs acceleration for geodesically convex opti- mization, even with exact first-order oracles. CoRR, abs/2111.13263, 2021. URL //tpiv////xxxx/g///// abs/2111.13265
Hosseini, R. and Sra, S. Matrix manifold optimization for Gaussian mixtures. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp- 910-918, 2015. URL http: http://pppss..scc//pppps
Criscitiello, C. and Boumal, N. Curvature and complexity: Better lower bounds for geodesically convex optimization. In Neu, G. and Rosasco, L. (eds.), The Thirty Sixth An- nual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pp. 2969-3013. PMLR, 2023. URL https: ht v195 1155/rriscitieell23.....
5812-matrix-mani htwp---mmiiiodoooooooooooooo---- imization- for- maz-gaussiin-mixxuuee
Hu, Z., Wang, G., and Abemetty, J. D. Minimizing Dy- namic Regret on Geodesic Metric Spaces. In Proceedings of Thirty Sixth Conference Learning Theory, pp. 4336- 4383. PMLR, July 2023a.
Dixit, R., Bedi, A. S., Tripathi, R., and Rajawat, K. Online learning with inexact proximal online gradient descent al- gorithms. IEFE Trans. Signal Process., 133881133-11322
Hu, Z., Wang, G., and Abernethy, J. D. Riemannian projection-free online learning. In Oh, A., Nau- mann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.). Advances in Neural Information Processing Systems 36: Annual Conference on Neu- ral Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023b. URL http: http:::/ppapers.ips.cco paper.flles/papor/233//aatt
2019. doi: 10. 1091TS/T 2018 2890368. / wwt..oogg11.1100000
URL ht wwt...........003...
Edelman, A., Arias, T. A., and Smith, S. T. The geome- try of algorithms with orthogonality constraints. SIAM
Matrix Analysis Applicattoons, 20(2):303-3533 1998.
doi: 10. 10.11377508554778995990544 URL https://
88050049227F6622b91111099988
doi.org/10.1133 /od.ccr/1/011177/899944888888889
Ganea, O., Bécigneul, G., and Hofmann, T. Hyperbolic neural networks. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 5350-5360, 2018.
Hu, Z. Wang. G., Wang. X., Wibisono, A., Aber-
nethy, J. and Tao, M. Extragradient type methods for riemannian variational inequality problems. arXiv preprint arXiv:2309. /4/55v1,, 2023c. URL https:
/ //arxiv.org
http:///ooocceeegs.eeeeeoe ps..c.......iii.ooooo paper/2018/ban hhahh//h/hhhhh/// Abstract.html.
Jiang, B. and Liu, Y. A riemannian exponential augmented lagrangian method for computing the projection robust wasserstein distance. In Advances in Neural Informa- tion Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16. 2023, 2023. URL. http: htttp://paper..nig http//ppprssss..oo
Hamilton, L. and Moitra, A. A no-go theorem for robust acceleration in the hyperbolic plane. In Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, Decem- ber 6-14, 2021, virtual, pp. 3914-3924, 2021. URL https: paper/2021/hash. 2016546922263324f1cffee Abstract.html.
paper wtweee/fileespppe//222//////////
Jordan, M.. Lin, T., and Vlatakis- Baatakis-Gkragkoumiis E.-V. First- Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces. Advances in Neural Information Process- ing Systems, 35:6557-655 6574, December 2022.
Heidel, G. and Schulz, V. A Riemannian trust-region method for low-rank tensor completion. Numerical Lin.
Joulani, P., György, A., and Szepesvári, C. modular analysis of adaptive (non-)convee optimiza- tion: Optimism, composite objectives, and varia-
Alg. with Applic.. 25(6), 2018. doi: 10. 10.1002/nla.1155. URL https::/p//......... http:::://blorrg//1000//.///aaa 0000
10

---

Martinez-Rubio, D., Roux, C., Criscitiello, C., and Pokutta, S. Accelerated methods for rieman- nian min-max optimization ensuring bounded ge- ometric penalties. CoRR, Abs/2305.16145 2023. doi: 10.48550/axXi.22355.1111 Implicit Riemannian Optimism with Applications to Min-Max Problems
tional bounds. In International Conference on Algo- rithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan, pp. 681-720, 2017. URL http:/ http:://p.cceediggss....... v7 v76/joul jol.ooolllnneiie lani17..htmm
tion. In 53rd IEEE Conference on Decision and Con- trol, CDC 2014, Los Angeles, CA, USA, December 15-17, 2014, pp. 1137-1142, 2014. doi: 10.1109/ CDC.2014.7039554 URL https://doi.org:
Karcher, H. Riemannian center of mass and mol- lifier smoothing. Communicationn Pure and Applied Mathematics, 30(5):509-541, 1977. doi: URL
Nesterov, Y. E. Smooth minimization of non-smooth functions. Math. Program., 103(1):127-152, 2005. doi: 10. 10.10071100107-0000555--- URL https://
co1.orgg00.0007/11110--0-4---000
httpps://oonIneallbrrrryyx.ys. abs/10010002/paa.11300000
Nguyen, V. A., Shafieczadkh-Abaddhh S., Yue, M.,
Kuhn, D., and Wiesemann, W. Calculating optimistic likelihoods using (geodesically) convex optimization. In Advances in Neural Information Processing Systems 32:
Lezcano-Casado, M. and Martinez-Rubio, D. Cheap orthogonal constraints in neural networks: A sim- ple parametrization of the orthogonal and unitary group. In Proceedings of the 36th International Con- ference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 3794-3803, 2019. URL http: httt:://proceedingge rt..resss. caa.aaaooocaaaadoa..hh.....
Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019.
Vancouver, BC, Canada, pp. 13920-13931, 2019.
URL attpss:/procceddngg...t paper/2019/han 02lelle7770011aa0044440444555553 Abstract.html.
Maass, A. I., Manzie, C., Nesic, D., Manton, J. H., and Shames, I. Tracking and regret bounds for online zeroth- order euclidean and riemannian optimization. SIAM J. Optim., 32()):4446244 2022. doi: 10.1117721M140055511
Orabona, F. A modern introduction to online learn- ing. CoRR, abs/1912.13213, 2019. URL http://
URL /ttp://///...ooo../.11111/1/////
Martinez-Rubio. D. Global Riemannian accelera- tion in hyperbolic and spherical spaces. arXiv preprint arXiv:2012.03616 2020. URL https:// arxiv.org/ httprr//abb/2202..111555.
Petersen, P. Riemannian geometry, volume 171. Springer, 2006. ISBN 978-0-387-29403--.
Rakhlin, and Sridharan, K. Online learning with predictable sequences. In COLT 2013 The 26th Annual Conference on Learning Theory, June 12-14. 2013, Princeton University, NJ, USA, pp. 993-1019, 2013a. URL http::://pocceeddngee v30 v30/Rakhlin1333 1.hmmlll..
Martinez-Rubio, D. and Pokutta, S. Accelerated rie- mannian optimization: Handling constraints with prox to bound geometric penalties. In Neu, G. and Rosasco, I. (eds.), The Thirty Sixth Annual Confer- ence on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Ma- chine Learning Research, pp. 359-393. PMLR, 2023. www.lr.pes///.. /v/ess martinez- rubi rrw.eez--rurooaa.hmtt.
Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Burges, C. J. C., Bottou, L., Ghahramani, Z., and Weinberger, K. Q. (eds.), Advances in Neural Information Pro- cessing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Pro- ceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 3066-3074, 2013b. URL https: /ttt://ttt//ppppr/oeiiiiioeeeee paper/2013/han httpss/////oeeedggggeeer....e. (oad4499bbb Abstract.html.
URL
URL https://
Martínez-Rubio, D., Roux, C., and Pokutta, S. Convergence and trade-offs in riemannian gradient descent and rieman- nian proximal point. CoRR, abs/2403.10429, 2024. URL https: /tt/aaxxvvvioooo htttp:::/aaxxi..r//bbaa. http:/orrr/abb///33102222222
Sala, F,, Sa, C. D., Gu, A., and Ré, C. Representation tradeoffs for hyperbolic embeddings. In Dy, J. G. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stock- holmsmässan, Stockholm, Sweden, July 10- 15, 2018
Mishra, B. and Sepulchre, R. R3MC: Riemannian three-factor algorithm for low-rank matrix comple-

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
volume 80 of Proceedings of Machine Learning Re- search, pp. 4457-4466. PMLR, 2018. URL http:// sathtt...
Wang, X., Tu, Z., Hong, Y., Wu, Y., and Shi, G. Online optimization riemannian manifolds. J. Mach. Learn. Res., 24:84:1 2023a. URL http:// /ttp://///l.//////// papera 2ttp:///2222111..tmmmm.m
Sun, J., Qu, Q.. and Wright, J. Complete dictionary re- covery over the sphere II: recovery by Riemannian trust- region method. IEEE Trans. Inf. Theory, 63(2):885911 914, 2017. doi: 10.1109/T1T 2016 2632149 URL https: 201.11199//7..0000 211.011109/1122222662222221
Wang. X., Yuan, D., Hong, Y., Hu, Z., Wang, L., and
Shi, G. Riemannian optimístic algorithms. arXiv
preprint arXtv:2308.16004V/ 2023b. URL https: 2tt.//aabb/33300000000
Tan, M., Tsang, I. W., Wang, L., Vandereycken, B., and Pan, S. J. Riemannian pursuit for big matrix recov- ery. In Proceedings of the 31th International Confer- ence on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pp. 1539-1547, 2014. URL http: //pprocediiggs... www.llrpppesssseo.o wwt.ppprrssss/eeaaes httpr/////vv///aaa....ama 4.tmml.
Wiesel, A. Geodesic convexity and covariance estima- tion. IEEE Trans. Signal Process, 60(12):6182-618) 2012. doi: 10.11009TSPP221222221888 URL https:
Zhang, H. and Sra. S. First-order Methods for Geodesi- cally Convex Optimization. 1xXiv:160.00605: [cs, math, stat), February 2016. URL http:// /ttp/x.xxivirr////// abs/ 0as/1602.06055 arXiv: 1602.06053.
Taskesen, B., Iancu, D. A., Koçyigit, Ç., and Kuhn, D. Distributionally robust linear quadratic control. In Oh, A., Naumann, TT, Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Infor- mation Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL http: http://pppprs.sscc..o..// paper files/paper/20233/aaaa
Zhang, P. Zhang. J., and Sra, S. Sion's minimax the- orem in geodesic metric spaces and a riemannian ex- tragradient algorithm. SIAM J. Optim., 33(4):2885- 2908, 2023. doi: 10. 10.1137/22M1505447.. URL https:
Zhang. T. Robust subspace recovery by tyler's m-estimator. Information and Inference: A Journal of the IMA, (1):1-21, 11 2015. ISSN 2049-8764. doi: 10.1093/ imaiai/iav012. URL https://Abb.oorg/10.0033
33246222122288922994553588888882 Abstract-Conffeeece.hhi
Townsend, J., Koep, N., and Weichwald, S. Pymanopt: A python toolbox for optimization on manifolds using auto- matic differentiation. Journal of Machine Learning Re- search, 17(137):1-5, 2016. URL http: /tle://mmmree jmlr.org/
imaiai/iav012.
Tseng, P. On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math., 60(1-2):237) 252, June 1995. ISSN 0377-0427. doi: 10.00066037700427744000004 URL ht https: /
(94) 00094-H.
Vandereycken, Low-rank matrix completion by Rieman- nian optimization. SIAM Journal on Optimization, 23 (2):1214-1236, 2013. doi: 10. 10845768. URL https: httt::://dbi.orr/10000 00..111111111117111
Wang, X., Tu, Z., Hong, Y., WU, Y., and Shi, G. No- regret online learning over riemannian manifolds. In Advances in Neural Information Processing Sys- tems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021. Decem- ber 6-14, 2021, viriual, pp. 28323-28335. 2021. URL https::/procediing..r paper/2021/hash/ 2e188411733aadddeee44422222200 Abst.hact.
12

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
A. RIOD proof
Theorem (RIOD). [1] Let M be a Hadamard manifold with sectional curvature in [Kmins 0j. Further, for E [T], let the loss and hint functions l, : M be g-convex, and L-smooth in a compact and g-coveex set X S M with D diam(X). For 1j > O we have for any u E X that
3D2 Rr(u)=
Σ (=1
+
2n
Proof. (Theorem 1) The proof follows directly from Theorem 7 by setting u, = u for all t E (T) and Jr = 0.
Theorem 7 (RIOD). Let M be Hadamard manifold with sectional curvature in [M OJ. Further, let l, Ee M - R be j-stroongly g-convex, and L-smooth in a compact and g-convex set X C M with diam(X)) D and 2 O. Then for > 0 we have for any (wx)ce(Zy E X that
2PrD +3D2
Σ ((())) - (((4))
2n
T
(1( -V((==)12 11 u)))
where Pr del Ei= d(us, 1441).
Proof of Theorem 7. Using the notation of Algorithm 1, we define E, def 2ne, and recall that Lr(x) L((z) + 27 d(x
and T.(xx) (xx)+ + 2n d(x, 2. Note that I. and T., are (ttronly g-convex in X, because the regularizer ž, 2,,(,, x2) is (tro)ystrongly g-convex in X' by the first part of Fact 15 since V V=(dd(z,,) y)²) LLg and M is a Hadamard manifold and 8D By the (1/n)-strong g-convexity of L, and L, in X the error criteria of x++1 and 3t in Algorithm 1 and the optimality of itt1 and T7, we have that
d( ) 2n((F(T4+1)) ()( E,d(se, 21+1²
(2)
and
((,,,7)² s (n(((( L.(37)) s (ad(z1,5))
(3)
We also have
((())41) - ((m) = (x((111))))))))))) (1((11)) + (e(x(41) l((we)
1 1
((1 + (LL+E)d((z+1111 d(2 + (V4((1441), -Logo,, (ue) - 4 d(r u2)
S 21)
2
② 1
(4)
((1 + E,)d(xi+ 0.)2 2()141,0:)))> 1 "
(Log.in,, (Dt), Log (we) " 1(
21
1 (d(z), uz)² (1+ pm) u.)² a(0,,0111 + E,d(xe, 2 12))
2m
where 1 holds by the enror criterion of Fe41 defined in Line 6, i.e. Le(xe+1) Lr(x)+1) S d x(41)², and the j--ttrong g-convexity of & between को+1 and ue. Further, 2 holds since xf41 is the optimizer of L, and the first-order optimality condition, i.c., (Vl((z(+1) " Loge,, (zt), -Loge; (ue)) I 0 and (3 holds by Fact 15 noting that dn 1 since M a Hadamard manifold. Further, we have
1 (Logzr (Iz), Loge; (x(+1))
(V)()))) Logg, (I++1))
<
17
(5)
1
-(37 d(3;,,,))))
2n
13

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
where ! holds first-order optimality condition of L, with minimizer s7. and ② holds by Fact 15 noting that ón M Hadamard manifold. Using the previous inequalities, obtain
(xx)) Ee(we) (Tx) (x(x441) (e(xe+1) (u(
(VL( -Logs, (5++1)) + (((++11)))++)))))))))))))))))))) (x(1)) + (V), Log2; (1++1))
+ 2m
(d(2t, 11+1) - d( xe+1) d( )²)
(6)
1 (d(se; 2 (1 + un)d
(Bs())s) - -Log,, (5(+1)) (V,) Logs; (I++1)) + 2n
(-d( - - xz)²² E,d(at, x1+1)²)
2n
where 1 holds by (5) and the g-convexity of l between ãn and r 2 holds by (4). We want to obtain a computable optimism term, ie, a term that depends on the difference between the gradients of the loss function & and the hint function & evaluated a point we know or can compute. Since computing the exact optimizer žद of L is in general not possible, we bound (52), Logzz (Iz+1)) by term dependent on the gradient evaluated at the inexact point or ie.. Viz(Fz). Adding and subtracting terms, get
(Vl(()), Logaz (z++1)) (vi((1)) - 1 V(r(;)) Loga; (x++ 1)) + (1 St
(āt), Logaz (I++1))
(V)()))) - 2 (Z,( Logs; (I++1)) + (V (2. Logg, (f++1))
T V4, (fx)) Loga; (#++1) 2 Logs, (r 1)
(7)
where we used Gauß's Lemma in I ie., (I (i.), I th Logg, (+++1));; (V)) Logg, (z(41))2, for the second summand. Note that this is the term wanted obtain. We now go bound the other two terms. For the first of the two error terms, we have,
(v(())) - (ir( VéL((t)) Logar (#++1)) S - v(c(())) d(z), S Ld(ai, a.)( 2441)
(8)
1 =(o))
BnL'd 2 8n)
id x,))
8n)
where 1 holds by the Cauchy-Schward inequality, 2 holds by the L-smoothness of i, 3 holds by Young's inequality and 4 by (3). Before we bound the second error term, consider
2 D + (d(n 2++1) + (.1))))))))) < 2(1 + 2) ( (1,, + d d( (17,
(9)
2(1 + 2/ K6 mi (2d (22 2;)² 3d( x(41)
where D def
max (d(ār, xe+ 1), d(īz xz+1)) } Here, ! holds by the definition of <D. 2 holds by applying (a + +)² <
2a² + 262 for a, twice and 3 also uses the last inequality and the triangle inequality. We now bound the second error
term in (7) as follows.
T Vogs) (I1+1)-A - -
8. Loga, (#++1)) & [V,((z))1 ||Log (I1+1) E Log,, (#1+1)ll
[V. Pd( ( 21 + 48| En)
8 Sp
4(1 + 48 18/1 Mini
ET)
EA,
(10)
4 EDi
[(. + 48 48/ Minin |ET)
A
Ae d( x141)²
d(E,, 87)² +
2
EA.
24m
16m
5 EAr
(1((( -1 + 48 Kmmi 17)
A.
D. d( x241
+
End(,1, 2 +
2
A
24m
16n
14

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
where ! holds by the Cauchy-Schwar inequality, ② holds by Proposition 18 with D max(d(5r (441) ((+1)) 3 holds by Young's inequality for any E > 0 and A E (0, 4 holds by (9), 5 holds by (3). Using (8) and (10) to bound (6) yields.
1 (d(1e, u²) (1 un)d(2(411 u)9 + EA.
(Ga) lo(ve) S (V)((E)) vāo( -Logs, (I1+1)) +
2n
A - d( d(E;, r1+1) )² + 24
2m
+ 21)
| ((2(22))
+ 48 1 1n) + 812 +
D./12) - 1) d(žt x1)))
(1I)
1
$
v((())) (V.)
-Lgg,, (I1+1)) + (- d #1+1) + E1 + A, )d(s), 1241)²
1 (d(x), + (A. - 1)d(02+2,))3))
1
d((zit u1)²+ EA,
2n
2
2
3
2m
(( [V( + 48 Kmin (n) + 81 + 1))++11))) -1) d(ø); 21)))
2n
where 1 holds by noting that 4, E (0, 1) and applying the following bound to 1/1 d u
- -dli411 uz) - d(z u1)² + d(Ir+1, d(zi+1; u²
+ 22 (ux), LoBerti (z(+2)) d(ø++1, u)) 4²
d(a+11 u² + 2d( u)d(
(12)
I d(z u²)² + Aed(Z(+1, u=) + A, d(I 2141)
d(x441 u2)² Sed(Ec+1, u,)2 + E, d( x141)
Here ② holds by applying Fact 15 and dropping the negative term -d(x441, )2 3 holds by the Cauchy-Schwarz
inequality, 4 holds by applying Young's 's inequality and (5) holds by (2). We now use the following bound for the strong g-convexity term (d( u2)² in (11),
1 d a
d( 4 )z S d(ret1, u,)² M8011 S
(13)
where 1 holds by the triangle inequality and 2 holds by (2). Using (13) to bound (11), we obtain
((%)) le(1x) < (V.)
(ā.), -Log,, (1++1)) 27 (d(zee, u.) 2 (d(xe,u)²+ (A. - 1 1m)
2 (1144),)11))
E..
2
1
3
+
d( 2141)² (2 A, )d( 2i4 12
2n
4
1
+ 2n
+ 48/ (n) + 81) 22 +1) -1) d(3ī,
(14)
Let us briefly comment on why we bounded the two terms depending on d( 42 differently. If we had bounded them
both using (12), we would have obtained (A, 1 [) p7))d u)) and since A > O, this means that the update rule of
Algorithm is not a contraction in the min-max setting where all u, correspond to the saddle point (x* """""" ), see Theorem 3.
On the other hand, if we had bounded both terms using (13), we would have obtained =(I+ d(Iz+11 uz)2, which would have meant that this term does not telescope out with 27 d(1, ) later in the proof. We now bound our error dependent on
15

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
d(x1 2 such that we can cancel it out with the negative terms which come up in the analysis. We bound,
(011 )²
2d 22, 27)² 2d(a7, 21+1)
2d #7) 4d( m++1 )2 + 4d (1+1) )
(15)
a5), 4d r4+1) + 48, 1
where ! and 2 follow by the triangle inequality, 3 follows by (2). Hence, by rearranging and noting that &, 1/4by definition, we obtain
2 d 2x,,
4
x1+1) 2 (1 4E,)
d(
(16)
1- 42,
Using this inequality, we get
1 (d(rs,, u1) + (A, (m/2))d(0++11
(Gee) (x(we) S (Vl((t)) vi.( -Logs, (1++1)) +
2n
(17)
1 (CC, - (34 + (C, 1)d( (2 + ED.
+ 2n
where
C det
Et
9 + 8n7 L A,=' (4+ 2nl V((( 48 48/mmmmml)))
45,
(2
2E, + 27¹)
2ml V 48| =8L3?? + +1] }.
max
+ Eτ
1- 4E,
1 4E,
A,
We now address the mismatch between d(z,, 4 and d(z)+1,
Σ d(z,,u)) - -d(2441 u2)
Σ ue);, ((1411,441)) ((00-1,44))) d(xe41,
1=1
r
d(æ), (1)),u1)² d(IT+I, 2+
Σ
d d(zet1, 2411) d( d(E(+1, 22)
(18)
2
2 d(æ1, d()1,11)² - d(IT+1, 22+1)² 2 2D Σ d(ue, u++1),
1=1
= Pr
where 1 holds by telescoping the first two summands and 2 holds by
3 dit+11, 121) u1) S d(ue, (d()) 11+1) + d(r,11 ue) S 2d(ms, DD
where we apply the triangle inequality d(r141, (02441,,+1] 1) S d(z uz) + d(ui, ue+1) in and in ④ we use that ue+1)
d(zr41, (411), d(z u.) S D. Summing (17) from t 1 and using (18), we get
T
((())) - ((())) v d(z1, u1)² d(xr+I,UT+1) 2T1) + 2Dr
T
(o.)))) Vi((E,) LLgge (I++1))
27
(19)
+ 20
T
[c, - )+,
(C, - 1)d( x2)
In d d(
4t 12
+
A, (Fn + d( )
2
2m
1=1
Further, choosing E t D2 /n and A, (++1)-2 we have that
1 T
1 D2
T
2 D2
AD2 + d(x uz)
A 71
(20)
27
1 t=1
16

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
where ! holds since the x441 and uy lie in X' and ( holds by Proposition 14. We obtain
T ((+)) - Ee(())) - d(zi, d(xT+1, w1+1)² 2 +22
T
( - -Log,, (I(+1))
21y
1=1
(21)
T
+
1 (C-- - 3/)d) + (C2 - xz)
d( ux)
21j
2
Further, we bound
(V(())) v((())) -Logs, (11+1)) 2 (V))(t)) v(((a)ll -d( vlVV(())) v2((111 +
1 d(
4n
nl ((..)) - V(((,,11 + 1 (;) + d(ii, xt+1)
2n
where we use Cauchy-Schward in ① Young's inequality in 2 and the triangle inequality and (3) in 3 Bounding d(xi, )² < D2, we obtain
T
(VV - v&(E,)1? 1 (( 2P +D2
Σ (Gx) - E((w)) 5
27
4
t=1
1
((C +0 -r) (C,-
1/4) (5+
211
2P D + +3
+
Σ
(lI - v2(2,112- 1 "((z+11 1)))
27
4
1=1
Here I holds because our choice of & ensures that C E. 5.
B. RIODA proof
Lemma 8 (Online-to-Minmal Reduction). Let M, N be Hadamard manifolds with sectional curvature in [8min 0] and X C C, C N be compact and g-convex sets. Consider the bi-function f .M X + R. which is p-SCSC and L-smooth in X' x Y. Further, let (x",y" ) be a saddle point of f. Consider two instantiations of Algorithu &running for the x and variables in parallel. In particular, for I, let āt & Iz, It. +- Iz, le(x) + f(x, 1t), fe(x) + f(x,y1)) St x sT, E x Ey
and un & x². For y, let Ve + yb Hs + Nt. Ee(x) + -( Pe(xx) + - Ee + e%, E + Ey and us + y²- Then we have that
f(2z,8") -fa""""""a""""" S
(d(y). v²)² + x1)=,,,=)2=-
- 1 -A,
(dd 8²)² + d(x 22)))
2n
I (CT -3/4)
d(Ff 11+1)² 2 T.+ (Ch -3/4)
d(ūh v1+1) )2 + (Frr + D1/2
2n
2n
(C+
+ 45, - 1)
22,) + (Ct + 48, 11) d(
+ L(1 28,) +
d(Di.)))2
[((1 (E,)
2m
27
where & del 2n max e") and
Et
CF
(9+ + A (4+ 2n v1 (2 + +48 48 (mmia
1 48,
(22)
C2
Et
19+88
+ - (4+ 2n v, fz, 3e (1" + 48 kmmm in)
48,
Proof. Following the proof of Theorem 7 until (17) for both the instantiations of Algorithm updating x and y and summing
17

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Algorithm 2 Riemannian Implicit Optimistic Gradient Descent-Ascent (RIODA)
Input:
Sets X _ M. S N,, sectional curvature Kmin= initial points (æ1, v1) X x x',, smoothness and strong g g-convexity constants L and y of and final precision total number of iterations T.
Definitions:
o The algorithm does not compute these quantities.
Proximal parameter r) + 47,
(x, f(z v) + 2n [x) 2nj dyy yr)
Exact solutions:
it
arg min H2(2, yt) and sit1
arg min He (ar Ut)
ZEX
ZEX
Vi
def arg max Ha v) and 2b41 yEy
der
arg min Hi (āt.v)
Constrained case:
Knowledge of G is not required, see Corollary 4
μ = 0: min 1/8. ((t (40 + /L/////6 + 12/mmin L)))
> 0: E min 1/8, (max (tax((t+)) (t+ (1,, + G² /LE//4 + m//il// I/)))) /z))""}
Unconstrained case:
Knowledge of R is not required, see Corollary 6
== 0: E min
1, (2(1+ + 1)3 2385 R Miimmll 1)) }}
p> 0: 6, min 1, (8T(37 2 (imiill) |
1: for 1 to 7 do
2: i (E,d(xt, 23) ) minimizer of Hz(z, v.), de +- (E,d(y), -maximizzee of He(Fe, v) ( minimizer of He (+ vi+1) 1)) mmaximierr H2 y)
3: xt+1 (E 21 )²)
4: end for
Output: ãт, Dr if > 0, else uniform geodesic average of (ă1, F1), (ir, 3r) defined by (GEO-AVG).
the bounds, we obtain,
f( f(x' .v¹) + f(x" .v²) - f(x", ((=""00) (1)
1
(dyve.0') 2- + d(zr, )²² (A. 1 un/ (d] 3²² + x1)x11,2)))111
2nj
(Vy Wif( (1 Vuf(Ee, 31). -Logy, (1(+2)) Vuf(ias 0.) V.f( 91), LLog,, (I1+1))
(C7 3/4) x(+1)2 (C7 - 3/4)
d(ÿrt yl+1)2 (C7 - 1) d(ī; x1)2
(C7 (C%-1) 1)
d(zt. y1)² + (Ex + 1./2
2n
2n
2n
21
(23)
We have that
(V.((I,, ff It), LLog, (U++1)) + (V..(a.. Vaf vt), -Loga, (1++1))
Vy me) v, Ul d(Tr, 11+1 + /.. Var we)l ((T1,
Ld(Gr, zn )d(ie 11+1 v(1) + Ld(ūe. 31 dd(r
3 L
2 (d) + d(ūr 22+1) d(ūr. + ((+)?))))))))
< I(1 + 3 d(y.. 0z) + L(d(Tt 2 + d(ū 22.1)
Here we use the inequality in 1 follows by applying the T-ssmoothness of f. Young's inequality in
18

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
and by the triangle inequality and the error criteria of by and De. i.e., d(0,, Fe 11+1) )² d(Tr, vx)²² < (2d mx) (z) - 2d( -1: and analogously for y. It follows that
[(T,, - [(x", .be)= S 2n
(d(v), 1²)² + d(zr, x² (A: - 1 1111m/2 + d(xe+11²))))
+ 1++ (CT -3/4)
d( St+1) ) + 1.+ -3/4)
d(T Vt+1) )2 + (Eer + Ery) D1/2
2n
21
(C, + -E -5--1) 1)
d(Ft. + (((1+2E)) + (CF + 45
+ L(1 + 28r)
+
d x())
21
27
which concludes the proof.
Theorem 3 (RIODA), [&] Let M, N be Hadamard manifolds with sectional curvature in [Kmin O] and X C C. C be compact and g-convex sets. Consider the f :M x N - R, which is g-convex, g-concave and L-smooth in X' x y. Further, let (x" .v") be a saddle point (P) and (TT, (T) be the oulput of Algorithm 2 after T iterations. Then we have f(TT, "orr,y") - f(x", (() S E after T = 8LR2 iterations, and T = -177 log strongly g-concave in X x y
ALR 1. i is also u-strongly g-convex,
Proof. (Theorem 3) Let EG def 21 max }. Hence by (2) and (3), we have that (( S E,d(a,, )² d( #;)² s E,d(n,, d(ve+1, s E,d(ur. vi+1) d(0 02)² < E 02) (24)
By Lemma 8, we have that
1
[(Tr,1") - f(x", S
(d(y), v²)² + x(xx,x))²+ (A. 11 1mn d(sx4112))3)
21
L (CT -3/4)
d(žī x2+1)2 22+ + L (C/4)/4)
+
d(ūt y1+1)² + (Ex + E,)
(25)
2m
2n
(C
+ 4E,- - -1) 1) d(Fr. + [((1
[[11+22) + 25,)+ + (C) + 48 -1)
1)
+
L(1 + 2E,)
+
d (
2m
21
with
C duf
Ee
9 + TT?
T.2 2, + 1.=1 4 27| V 2zf (E) + 48 18/mmm (1)
4E,
D.
CP def
E
9 + 2 + :,
4+ 2nl V (x De (EE + 48 48)m In)
4E,
A:
By our choice of e and 1 as well as Ez, E, and A,, which we specify below for μ = and μ > separately, we have that max CT) + 58, S 1 /4 and hence (25) can be bounded by
1 (d(y). y²)² + x(),,x')) + (A. - -1 (nm2) + (()+),,")))++(
f(2..8)) 00) < 2n
(26)
We now analyze the g-convex and the strongly g-convex cases separately.
Case م = O. We set A. = (t + 1)-2 and Eg = Fry = e/6.. By definition, the LHSS of (26) is non-negative, hence by dropping it and rearranging we obtain
d( + d(x+11, < (1 4 )² 3- d(za, 22)
(27)
& (d(en.v') + d(z1, )
II
+
EQ
Σ
A 2(d(2), (id()n.")²² + d(21, + te/2
1 -
A
2 1=1
19

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
where ! follows by repeatedly applying this inequality and since - A1 < 4/3 and 2 holds by definition of A and Proposition 10. Summing (26) from = 1 to T, dividing by T and telescoping the sum, it follows that
T Σ T t=1
T
A((d(v++.)))) + d(Ic+1,x"))
EAC
(f(Z),))) ((=",,)) -
R2
+
+
21/7
2t/T
47
R nT
4LR
2T
T
2'
where ① holds (27), Proposition 14 and dropping the negative terms and 2 by the definition of 1/(LL) and T 1.
By applying (GEO-AVG) to the sequence (it, ūt), we obtain
T
[(Tr,y") [x= UT) S T
Σ (f( - (.)))
Hence after T the g-convex case.
8LR [ iterations of Algorithm 2, we have that f(or, f(x", (e")gr)== S E. This concludes the proof for
Case μ > O. We set A, = mi ) E2 Ey = E/4. 4. By definition, the LHS of (26) is non-negative, hence by rearranging we obtain
d(v++1, (00))-d((411))
d(0+11, x*) 51 (1+ pn/2 -
2(11, +
ET) 21 pm/2) 1)
(1 + un 4) 4 (d(y). )² + d(z,, x²)) +
ET
212
where 1 holds by the definition of A, Then by repeatedly applying the inequality, we have
)( + d(x S (1 + pmn R22
ETj
S (1+
1
RR + S
exp
4p
R²
+
8
16L
4L
17L
4L,
R=1
where 1 holds since E 1-2
x² 6
< 2 and by definition of r 1 14T.) and 2
holds by the following inequality
1 1+ #/666) =1 1/(16L) 1 1+//(161)
1
$1 I exp
(28)
17T.
17T.
which holds as u/L S and 1 + x S exp(x). Hence, running Algorithm 2 for T' that
17L log
1LR
iterations implies
d(uT "² + d(ær, xx x²)² 2T.
Dropping the non- non-positee nonpiosieive distance from (26) for x- and using the definition of n, we obtain
[(ār, f(x", iT) < 2L(d(yr,"") + d(xr xx )2) S e,
which concludes the proof.
Theorem 5 (RIODA unconstrained). [1] Let M, N be Hadamard manifolds with sectional curvature in [Kmin 0).
Consider the bi-function f M N + R. which is g-convex, g-concave and L-smooth in Z B(x* 88)) B(y",
where (x", (e")y") is saddle point of f. Then the iterates of Algorithm 2 stay in Z. Let (IT, .r) be the output of Algorithm 2
after T iterations. Then we have f(T .1") - f(x", "a",,y" yr) S s after T = GLR iterations and T = 177 log 2LR if
addition y-strongly g-convex, strongly g-concave in 2.
20

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Proof. (Theorem 5) Let E der 2ny max {Eg, e. Hence by (2) and (3), we have that
((14) S E 1)41)² ). d( I #f) (1 s End(ye. 12 d(ūr. 01) V E yv ve
(29)
We show that the iterates stay in a bounded set B(x", 7R) x B ,7). In particular, we show via induction that d(xr, + d(yi,y") y²) I 2R and then show that x²) + d(ūe: y²) I 7R and ((1++1,2²") + d(y++1, ,,)++,,y") < 7R. For t= 1, we have that d(x1, x²) + d(y1, 3²) S 2R by definition. Assume that d(I;, x*) + d(y.. y²) s 2R holds, now we will
prove that it also holds for + 1. We have that
d(ze, 2t) + d(ye, Vi)
2(0,,2") + d(Di: y*) S d( #f) + d(ūr, 02) + d( x*) + +d(
+ dd0;, + d( v*)
4
7
(d( + d(ye, v )) + (d(z) x²) + diūt y²)
(d(Ie, x*) + d(y,, y
(30)
where ① holds by the triangle inequality, 2 holds by (29) and v S 1/4, 3 since d( x²) + d(ir x²) S (d)=)(((==x=*) + ((vr."")) by Proposition 9.
holds by the triangle inequality and 4 holds
Further, we have that
d(z++1x²)) + d(21+1.83)
2 d d(Fr41, + d( vi+1) + d( x²) + d(yi41:
1
S 4
(d(ze, o d(yn v(+1)) + d d(a x²) d(si+1:9))
(31)
3 1
5 4 (d(x"_:=²)) + d(vi+1.9"))
2 4 (d(xz)x') + d(y.. ))) +
7 (d(x), x²) + d(ye, y²)),
2
where I holds by the triangle inequality, ② holds by (29) and vl, S 1/4, 3 holds by the triangle inequality and 4 holds since d(zi=1:00 x²) + d(vi+1, )²) < 4o (d(x,,,')) + d(y,, v²)) by Proposition 9. We have thus established that Tt. TT-1 1 and Tt. V1+1 lie in B(x 7R) and Bly", 7R), respectively. Recall that by assumption, f is μ-SCSC and L-smooth in B(x*, 8R) x B(y", 8R). Therefore, we can apply Lemma 8 with X' t- B(x", 8R) and y + Bly 8R) as the iterates are guaranteed to lie in the interior of the sets and hence the constraints are never active. Thus, applying Lemma 8 with
Eg = d(a,);)) and Ey d(v.)))²
we obtain
89
8n
f(ā(.8) - f-'=fff0000 S 2m
(du,.v'' + d(I x )²² + (A. - 1 p2n/2)(d( + d(z141,2))3))
(C-33/4)
d (( + [.+ (C% -3/4)
T, +
d(ūt 11+1)²
21
21
(CH² + 42, -3/4) ((it.00)² + [((1 [((++2E) 28,) + (CT + -3/4) d(i;; x2)2
+ L(1 + ((1+)2e)+* +
2n
27
(32)
where
OF def
(9+ A, (4+ 2ml
V.J 31 (E, 48 48/k5min (n)) + 8r7² I?2)
1 4E,
CH def
&
(9 + A,1 (4 2m f 3) "
48 (8mmm In) + 817² r.2). T.))
4E,
We need to ensure that max (TT, C + 52, I 1/8 in order to cancel out the summands in the second and third line of (32).
Therefore, we show bound for CF and C in order to finish the induction argument. Note that
1
13 (d(x), x²) + v")).
it) + d(vi. D.) S d(x),x") + d(y,, v") + 0(x"x;)) + d'y""0 <
(33)
4
21

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
where ! holds by the triangle inequality and 2 holds by Proposition 9. Squaring (33) and noting that a² +12 s (a+b)² < 2(a² b2) for a, O, have
((), + d(ye, 0,)² 22(d(xr, + d(yt, )))
(34)
Further, we have
2 P V (zI( VVaa( well S Ld( + " "0s, #2)
17L
[V.. will S IV
d( x;)
(35)
Here holds by the triangle incquality, 2 holds by smoothness of f between ot and ot, which both lie in B(x* 7R/ 22
by the induction assumption, and (30). The optimality condition of ë7, i.., v.f( v1) ") Logaa (2t) was also
used. Lastly, 3 follows by definition of = 1/L4)) and by (29) and vēr I 1/4. Analogously one can show that V U+)l S 17L. d(ue, V7). Using these bounds and the definition of 7,, we obtain
4
E
E
(10 A, (22 (0) (((mini)))))))
(10 + A, (22 2385 (
t
4
(36)
2
(10 A, (22+ + (e: 37) (
E
(10 A," (22 + 2385R2 [ |
4
4E,
where for both incqualities, ! follows by (35) and 2 follows by (34) and the induction hypothesis. Our bounds C7 and Cf and our choice of Ez. Ex, Fy and well as Ae, which we specify below for O and 0 separately, ensure that max(Cr (CT, C.T + 56, S 188 and the update rules in Lines 2 and 3 can be implemented efficiently. Hence we have,
1 (d(m.. v²)² x(x,, + (A. um/ 2m/2)) + d(xx11,²))))
[(ir, 5") [a" D.) <
(37)
2n
We now analyze the g- g-convex and the strongly g-convex separately.
Case μ 0. We set A. (t (1+1)-=² 1) By definition, the LHS of (37) is non-negative, hence by rearranging obtain
x(ze41,")) d(yc+1, d( x²)² 2 + d(vi, ①
(d(x),"*)² d(y), )3) II i-A: A:
1
A A
(38)
2(d(x1, +of++ddyiis d(vi,
where ① follows by repeatedly applying this inequality and ② holds by Proposition 10. Noting that a² + 62 < (a + b) < 2(a² + +²) for a, >> O, this proves the induction statement, d(z x²) + d(31+1, v") s 2R. Summing (37) from = 1 to T, dividing by T and telescoping the sum, it follows that
T Σ (f(a..))) f(x")())))) = (d(x), d(vi,""'' 2n7
T (x((xx)x*))) + d(vi.y" (2)
T
+
27/T
1=1
x2) + d(vi, 3²
d(æ1, d(vi, y²)²
3 6LR
2
Σ D.
20/T
1/
where 1 holds by (38), 2 holds by Proposition and by definition of r) and R. By applying (GHO-AVG) to the sequence (Zt, Dr), obtain
T
1 f(x" UT) < T
E (((Tn)))) (("))))).
Hence after T 66RR2 [
iterations of Algorithm 2, we have that f(Er,y") - f(x".11 S E. This concludes the proof for
the g-convex case.
22

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Case μ
We 4, 42. By definition, the LHS of (37) is non-negative, hence by rearranging and using the
definition of A obtain
1
d(yc+1.8") "alin""""(((()00"""" -
1 um/4 / (d(pe 3²)² +
-14
(d(v). v²)² + d(xx,,"))),
exp
17L
where ! holds by (28). Noting that a² 12 S (a + b)² 2(a² b²) for a, b 0. This proves the induction statement, as d(0(41,2") d( 2R. Then by repeatedly applying the inequality, we have
- -tp
d(Ur+1.v)) + x") 3 exp
R².
17L
Hence, running Algorithm for T 17L log 22R iterations implies that
d y y²²² + d(or, x²)² 2L
Dropping negative terms from (37) for 1 <- T and using the definition of n, we obtain
f(ăT,y") f(x",' .ar""))))))) (T) s 2L(d(UT, + d(xr, x²)²) Se.
which concludes the proof.
C. Implementing RIOD and RIODA
In this section, we use xf and ãī refer to the 7-th iterates of subroutines minimizing L, and L, starting from Tt, i.c. T, = 20- Further, if F is the last iterate, we write 27 = R. and x.. I1+11
Corollary 2 (Implementing RIOD). [L] For the implementation of the update rules in Lines 4 and 6 of Algorithm we require Ö(Ln + {D)S gradient oracle calls & and é, at iteration using PRGD or O + Lm) using CRGD (this includes a logarithmic dependence on ( Here R del G LL D, where G is the Lipschitz constants of f and l in X. Note that these implementations do not require the knowledge of G.
Note that we provide the analysis for the criterion öt but the analysis for 2++1 follows by the same arguments. Since is differentiable, there exists a constant 2 such that [|V[,()]] G for all x the compact set X, which implies G-Lipschitzness. Note that L, is (L + (p/n)-smooth and (1/n)-strongly g-convex in X, since the regularizer 25 d(x )² 22 is (Sn/ (Gp/n)-smooti and 1 -stoo-str g-convex in X by Fact 15. Further we have for i E X' that
Proof. (Corollary 2)
S G D
[+ = (z)( 7 L'og S [+)(())) +q
7
where 1 follows since & is G-Lipschitz and x, E X, which implies that i. is (G + D/n)-Lipschitz. Recall that we require the following for the subproblem
L.(T.) L.(5)) S End(xr, 22)².
(39)
In the following, we compute the gradient oracle complexity of ensuring (39) using the upper bound G in order to show the worst-case complexity. We then show that the criterion also be implemented in way that adapts to the local gradient norm and does not require knowledge of G.
PRGD. By Fact 21, running T iterations of PRGD on Lt starting at 24, have that
(L + Cp/nSs
- d(Ie; 27)2
L.(ā;) L.(3)) <
exp
2
4(L1+ +(bn
23

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
where R=
G4D/n Lt<n/7'
Hence, it sufficient run PRGD for
7 -= C RDDCCllog log (L+
Et
iterations order to satisfy (39), We now show that this criterion can be implemented without knowledge of G. We have that
1-4(Ln 4(Ln+ + (1-a(e)+
2
r-1
L,( - ((ū)) & (i)()T))) - Lo()))
S (Lx(z)) - L(()))
II
1
(D)SR
4(LM + SD)SR.
i=1
L + (D/n)S d(zr, #7)²
T-1
II
1 4(Tmr CD)SR.
2
where Rt def (Z)(())) - 1 Logz; (z+))l((L + Cn/n). Here ① holds by Fact 21, 2 by
+
repeatedly applying the prior inequality and 33 by (Martínez-Rubic & Pokutta, 2023, Lemma 18). It follows that need to run PRGD for 2 iterations until
(I. + CD/n)SR Ro
II i=1
1
+
1V( + 48 | Kinn D)}
Se
2
A(L CD)CR.
81)
Note that (i.(;;)) criterion can be checked with little computational overhead.
-f (2x) has to be computed anyways for each iterations of PRGD, hence this
CRGD. After iterations of CRGD on L, starting from Izs we have
(.(T) (L (xt) S exp (-(r-1) min
L
1 d( a;)² (Tmy)"
1
(40)
Here used Proposition 22 and Corollary 23 with f +- &, and g d(. x2)² noting that L, is (L/n)-strongly g-convex 2n
and & is I-smooth. Hence it is sufficient to run CRGD for = O ((1 Ln) log (4)) iterations order to satisfy (39).
We now show that this criterion can be implemented without knowledge of G. By (40), it follows that we need CRGD for r > 1 iterations until
exp ((( - 1) min
ALaj 11111
1) < (ax +r)2 2 2n
( + 48/ Kmii 1))
8n
Note that (.,) = (i, Log (z:) has to be computed anyways for each iterations of CRGD, hence this criterion can be checked with little computational overhead.
Corollary 4 (Implementing RIODA). [L] We use the notation from Algorithm 2. For the implementation of the update rules in Lines 2 and 3 of Algorithu 2, we require Ō(LDSR) gradient oracle calls per iteration using PRGD Õ(1) using CRGD (this includes a logarithmic dependence on [8min (). Here ît auf L + D, where the Lipschitz constant of f in x y. We refer to these algorithms as RIODAPRGD and RIODACRGD. respectively. Note that these implementations do not require the knowledge of G.
Proof. (Corollary 4) We discuss the implementation of the criteria for x, but the proof for y follows analogously. The proof follows by applying Corollary 2 to the update rules of x and y. taking into account the definitions of e, and v) in Algorithm 2 and the following properties of f. We have that (x) = f far w:) + 2n d(rr xxa²² 22 is (L + Sp/n)-smooth -mmooth and (1/n) (1/n)-stonggly g-convex, because fx, 34) is T-smooth and the regularizer 1 2n d(x,, )2 is (Sp/n) hoonn-smooth and (1/n)-stronlyy g-convex in
24

---

57 Implicit Riemannian Optimism with Applications to Min-Max Problems
X' by Fact 15. Further, since f(s ve) is differentiable, there exists a constant G, such that [V m1) S G for all X.
Since f( (e) is also g-convex, this implies G-Lipschitzness. It follows that
[V of v.) -1 L (Ix) & (f, + + d(z, G 4LD,
where 1 follows since z+) is G-Lipschitz and 2; De E X. This implies that L2 is (G + 4LD))-.ipschiz.
Corollary 6 (Implementing RIODA- unconstrainedd) [4] Consider the setting of Theorem 5. Assume in addition that f is g-convex, g-concave and T-smooth in , x , Then we require ((1) gradient oracle calls for implementing the update rules in Lines 2 and 3 of Algorithm 2 using CRGD (this includes a logarithmic dependence on (auin) and the iterates stay in that set. If is g-convex, g-concave and L-smooth in B(x", D) x B ,D) with D duf R(13CsR + 9), then we require Ö(CR) gradient oracle calls using RGD and the iterates stay in that set. We refer to these algorithms as RIODACRGD and RIODARGD. respectively. Neither method requires prior knowledge of the initial distance to the saddle point R.
Proof. (Corollary 6) We discuss the implementation of the criteria for x, but the proof for y follows analogously. Recall that we have
&
&t
C
(10 + 4, (22 + 109d(2,, "3) (smmin))) 2
(10 + 4, (22 + 2385 R² ( D)
4E,
1 - 4E
(41)
C
(10 + A,-² (22 + 109d(ve. 0,) ((
(10 + A, (22 2385 (
4E
4E
We will make use of 2 to compute the worst-case complexity of implementing the criterion using R and 1 to analyze the implementation that adapts the value of ((I,,,t) or d(yt, )²
CRGD. Recall that (x) = fax ve) + L d(x, )² and (x(x) = fz, v.) + by d(r, 2,)2 with 1j = 1/(41))) Note that I,
and L, are stronystrongly g-convex and f is L-shooth in x E B(x", 8R). Then we have
3
13
d( ;.) S 2 r d(z x7) 1 2 (d(z), + d(z),x)))
S R
(42)
4
and
1 d( stt1) < 2
2 Td(t,, + d(si
R
(43)
where for both inequalities, 1 holds by repeatedly applying Corollary 24, 2 holds by the triangle inequality and 3 holds by Proposition 9, since x*) + d(yt, y²) < 2R and, O. Hence we have for any 2 0
1 d(E S x)) + d(0; x²)
2
13
9 +
R
4
2
and
1 d(xT, x²) S d(a) d(a), + d(zi+1
②
57
41
x²)
R,
16
8
where for both inequalities, ! holds by the triangle inequality and 2 holds by (42) and (43) and Proposition 9. As described in Corollary 2, the complexity of implementing the criterion using CRGD is O (log(L/ex)).
We now show that this criterion can be implemented without knowledge of R. We have by (40) that
[x())) - [.,) < 2T 22-T 27)2
25

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Note that
2 dxr,, #2)² 2 2d( kz)2 2d(T,, 17)² 2 2d(x,, kz)2 8 d())
(44)
3 + d( 27) 3d 2z)²
where ! holds by the triangle inequality, 2 holds by (29) and Es, and (3) by rearranging. Applying this bound to the is sufficient to ensure
RHS of 1 in (41), it follows that choosing = min 1/8, (A, (32 (3, + 327d #f) (m D) "
C + 5E, S 1/8. It follows that it is enough to run CRGD for 2 1 iterations until
2 S E = minn 1/8, ((t + (32 + 327d( 23 ( 1)) }
for μ = and
2 s E, = min 1/8, 4L (p(25 220d(x,, 27
(mmin))) ( "}
for μ > 0. Note that VL,()7) = (ā)( - 1 Logz: (zx) has to be computed anyways for each iterations of CRGD and d(z,, Ø7) [Loga (Ix)ll, hence this criterion can be checked with little computational overhead.
RGD. Applying Fact 20 to i. and L,, we have for the iterates of RGD that
1 + V5
1 v5
d(a 2,) - 2
Sal 2,) and d(x], S
(45)
2
for all т 2 0. Further, we have after iterations that
(L + (D/N)d(or,33)) x7)²
L,(3.) - L,(3)) S exp
{D
2
and
-T
(L (Dpn)d((ra x141)²
[,(x41)- (x( S exp
{D
2
where
D 1 V5 max (f Saler
We go on to bound D. Note that
2 13
d(z,, σi) d(xx,x)) + d(x"" ,5) R < 8R,
(46)
and
+ xb+1) 2 2 1
41
d(r,, xin) d(xx, d(=
R < 8R
(47)
16
where for both inequalities, I holds by the triangle inequality and 2 holds by Proposition 9. Further,
+
V5
9 2 2
d(it, x*) d(T x4) + d(=",, ,,)
R
86RR -
2
and
1 d(x x²) S x44)) + d(z x R
2 1 + v5
(8CRR + 8 $
41
where for both inequalities, ① holds by the triangle inequality and 2 holds by applying (46) to (45). It follows that
D R R133<R + 9) and hence (p O (C2). The complexity of implementing the criterion O (C2 log (e.))
26

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
We show that it is possible implement without the knowledge of R. We address the first obstacle as in the CRGD implementation by noting that choosing Er min (1/8, (32 + 32, (())) }}}
is sufficient to ensure
C + 58, I 1/8. But the number of iterations still depends on R via GR- To circumvent this, assume ||VL, v & dnf =,d(,...E.*" We show this suffices satisfy the criterion. We have 2+22
1
L (it) (..))) + (fx, Logs, (Ti)) + d( a(T,; xT)²
21j
2 (x.) + min
(V))) Loga, (2)) + 2m
dl d 2)²
(48)
ZEM
2 "
L(())) 2 Vi)(2)))?
where ! holds by the (1/n) g-convexity of Lu 2 by noting that
arg min zEM
Loga, (=)) (Vin(
1 =d(ūr; =) Expa,
arg Nygmin|
|| (7x - -u112.
( (-n)))
2m
ve
We have
3 2 7 (Z:)1 S nεe/2.
d( x2)² -.,
(49)
2n
where ! holds by the (1/1) (1/n)-strong g-convexity of L. 2 holds by (48) and 3 holds by assumption. Hence, in order to satisfy the criterion, i.e. (G.) (xt) S end(ar, 8f) )2, we require
Sed( Tz)² n2,/2 + 4np
S srd(xn,
Note that
d(x, 22)2 2 2d( Ft, 27)² + 2d( 3g)² I 2d( #;2 20eed( 2,)²
+ 27E
(50)
3.) 2(1 ne))d
where I holds by the triangle inequality, 2 by (49) and by definition of é, and 3 holds by rearranging. Hence we conclude that
nē./2 = End( 21) 1 2(1 ne)))
S e,d(xr,
+ 477
2 + 477
where 1 holds by (50).
D. Technical Results
Proposition 9. Let M, N be Hadamard manifolds with sectional curvature in [K 0). Consider the bi-function f:Mx x N + R, which is CC and L-smooth in X x Y, where X def B(x", D), y Bly", D) where (x" y" is saddle point of f and D det 3(d(I,, x²) ) + d(ye, v))). Further, let āt. Wr æb-1 and Vit1 be defined in Algorithm 2 for the unconstrained case and S 1/4L. Then, we have that
d(īt,a") + v0) < (d(y), y²) + ((x1,x"))
and
41
d(xī-1,²") ) + d(vi+1. 3²) <
(d(u,, v²) )+ + d(zr,
16
27

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Proof. Let H) = f(a.y) + 2n 2(( bn d. y*()) = arg yey Hz y). x² x²) der
arg mig (z v). x² =²") min f(x,v")+ + 2n 21) and y² (x") = maxgey f(",,) we have x² arg gex f(a, 3²) and y² arg maxyey f(x",)) y). Note that (x', (E)) (x+ (y*). ).y y (x*)) and
1 d(y y1) Further,
27
(att (1)), (xx)) lie in X' y by definition. Using (Martinez-Rubio & Pokutta, 2023, Lemma 10), we obtain that
d( x (v" )) d(z;,x"), d(y,, (101)"(x"))) (x")) S v().
(51)
Note that H₂ is (1/1)-SCSC in X' v and V (z,, -) and HeH y) are L-Lipschitz for all x E X and y E Y, respectively. Hence, applying Martínez-Rubii et al., 2023, Lemma 40) to H2, we have that (y) and y (x) are (Ia)-Lipschitz for all x E X' and y E y, respectively and in particular, we have
x x (wi) s Lnd(un,v"), d(x ((at(w"): (w"),
d(yt(x"), (ax)) S Lnd(xe, x²) dlyt(x"), (+)) - Lnd((s,
(52)
(y'), x (1))) & Lnd(ūr,y").
(53)
follows that,
d(x",x* (v.) + d(y', yt (xx))
d(x" x (y²)) + d(y', y (x')) + d(x (w"), xx (wi) + d(y' (x"), (x.)
d(sr, xt (v")) d(y (x }) (1 + Ln) (d(yt, wn) + d(are,))))
(54)
9 [d v²) + d(a,;))))
(2 + Im)(d(ue. v¹) + d(a, x*))
where ! follows by the triangle inequality, ② follows by the triangle inequality and (52), 3 follows by (51) and 4 by definition of 17- Note that by (54), have that xt (w:) and yt (2%) lie in the interior of X and y respectively and hence the constraints B(x D) and Byy" ,D) are inactive. Recall that 2t arg MMM f(z, vi) + 2n d,(x,x)) and ūt = arg maX [(x,,y) 21 d(y, )² hence we have that म = x+ (v.). of = (xx).. Further, we have that
d(z", x (i:)) + d(y"2 yy (&+) S d(æ", x xx (v")) + d(y,, y² (x")) + d(r + (y"). ) x (j:)) + d(y (x"), ),y" (ix))
S d(zr, xt (y') + d(ye, y (x + d(yt, v²) + d(z,, x²) + Lnddiir 4²) + d d(āzzx²))
9hn (d(y). v") d(z x²))
41
(2 +
(d [((r. y") d(xx,="))
16
(55)
where ( follows by the triangle inequality, 2 follows by the triangle inequality and (53), 3 follows by (51) and (54)
with 3े = x+ (11), Di = y+ (x²) and (4) by definition of Note that by (55), we have that (wt) and yt (āx) lie in the interior of X and y respectively and hence the constraints B(x", D) and By"", D) are inactive. Recall that a;- = arg min (xx ūt) + 2, d(( and Vit1 = arg max, f(Tr: y) 27 I d(y, )², hence we have that 2++1 = x (7r). v6.1 (Z.).
Proposition 10. For e > 1, and T E No we have that
II t=0
T
1
cC +
1-
(c (c- +
c c
Proof. We show II 1-((+e)-7
c(c+T) (e-1) (++++1 by induction. The statement holds for T 0. Now assume that the
statement holds for T - 1. Then the statement also holds for T, which can be shown by noting that 1 below holds by the induction hypothesis and rearranging
T 1
!
clc + T) 1 = (c- 1)(c + T T++) (c- 1)(c + T) - (T c)
c T
I t
<
28

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Note that in the following proposition, we specify where require the smoothness and g-convexity to hold, which is important for the analysis in the paper.
Proposition 11. Let M be a Riemannian manifold and les J : .M- - R be g-convex and L-smooth in X' = B(x", ,2((2, )")),
where x² arg MM (x) and ε E M. Further, let x+ def
then it is
1 2T.
-(0)) ((x)) f(x) - f(x").
Proof. First, note that
! d(x,,x² x²) S d(x +)++ d(z, x2)
V ((,x=) S 2d( x²)
(56)
where ! holds by the triangle inequality, 2 the update rule of x+ and by Vf(x*) = 0. 3 holds by the L-smoothness of ff in X. This implies that x+ E X. Then we have,
f(xt)-
Log, L 2
d(z,xt)²
[
2L
where ! holds by L-smoothness of f in X' and since xt E X by (56), 2 by the update rule of xt. Finally, by definition of x², we have that fx=) S fxx*) and follows that f()) f(xx)(++++) S f(x)-((x"))
Proposition 12. Let M be a Riemannian manifold and X C M be closed and g g-coveex set and let f :M - R be j--ttrongly g-convex and differentiable in X. Then, it holds for all x; y X that
pd(æ, v)² S (Vf(z) f -Lozz
In particular, it follows that
pd(x, [ [+)
f.)(1)
Proof. By p-strong g-convexity of f, have
f(x) - f()) s (Vf(x); - Log, (1))
142 d( y)²
1
f(y) f(x) v (Vf(y), - Log, (x))
d( x, y) 2
1
Adding both inequalities, have
pd(3, y)²² < (V) - -Tog (y))
Further bounding the right hand side using the Cauchy- Schwarz inequalities and dividing by d(x, 8), we have
pd(z, y) < fz) - r.v
Proposition 13. Let M be a Riemannian manifold and C M be a closed and g-convex set and let f M - R be g-convex, lower semicontinuous and proper in X. Then holds that
0 S (g" L.o..- S (g. LLgg (x*)), EX
where 9" E 0f(x)) and g E 0f()).
Proof. By g-convexity of f. we have (g, Log,, (x*) S f(x') f(x) S (g" -Lg..- (z)). By the first-order optimality condition, for optimizer x" of f. we have 0 5 (g" Logg- (x)) for all x E X, which concludes the proof.
Proposition 14, We have that T
[111 Σ 1.
Proof.
T
T+1
Σ
<
π²
1
1
(L+ 1)2
12
12
6
1=1
1=1
29

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
D.I. Geometric results
Fact 15 (Riemannian Cosine-Law Inequalities). For the vertices 2, p.P E M of uniquely geodesic triangle of diameter D,
have
6D
1
(Logz (v), Loga (p)) 2 d(x, u)² + 2 d(p, xx²²
d)p v)2
2
and
LD d(c,,y² u) x) 2
1
(L),a(y), Logg (p)) -
d(pp y)²
See (Martínez-Rubio & Pokutta, 2023) for a proof.
Corollary 16. Under the assumptions of Fact 15, the squared distance function pd(,,p)² is Cn-smooth and ôp-strongly g-convex in the geodesic triangle defined by the vertices x, y. p E M.
Proof. The proof follows directly by noting that the first equation of Fact 15 implies bp-strong g-convexity and the second equation implies -D- smoothttssss..
Remark 17. In spaces with lower bounded sectional curvature, if we substitute the constants Sp in the previous Fact 15 by the tighter constant and Sd(p.y) the result also holds. See (Zhang Sra, 2016).
We note that if min < 0, is CD ④(1 + DV
(K )) and therefore if e is a constant, have SoD O(DD). If Kinin 2 0 it is S, 1, for all r 2 0, so it also holds SeD (Sp)).
Proposition 18. Let M be Hadamard manifold with sectional curvature lower bounded by Emin then for x, D,P E M it holds.
|1 Log (p) Log, (p) S ((Kming D)d(I,8). y):
(57)
where D der maxfd(x, d).
Proof. Let (x) 1 [(xx,)) Then V=dp(z) = -Log, (p) and (p(x) is )-mmothh between x and p as the eigenvalues of the Hessian of (x) are upper bounded by Sa(e,p) by Alimisis et al. (2020, Lemma 2). Note that the smoothness constant increases with the distance to p. Since Hadamard manifolds, the distance between and other points in the geodesic triangle defined by x, y, p is maximized at the vertices, then pp is So smooth in this geodesic triangle, and thus we have that
2
(v) ( (v)l [IT (p) Log,, (p)ll (Dd(a,
Fact 19 ((Zhang et al., 2023), Lemma C.2). Suppose f is geodesically convex-concave. Then for any iteration (xe, we), the geodesic averages (t), i.e.
[a441 Exps, (++1 Loga, (2+41))
(o v1) (1),
LE (1,...,T -1}:
(GEO-AVG)
De+1 = ExPy, (147 Logg, (I++1))
satisfy for any positive integer T,
T f(Tr,)) - f(x, (x,Trr) Dr) < - f(x,
D.2. G-convex minimization
Fact 20 (Riemannian Gradient Descent (RGD)). Consider a uniquely geodesic Riemannian manifold M with sectional curvature in [Kiiin kmax] and a function f M - R which is p-strongly g g-convex and L-smooth in B(x", (1 + V5)d(ra, x² (R/22) C M. Then the iterates of RGD, iee, Ze+1 f- ExPx. (- [ satisfy Rt. E and we obtain an E-minimizer in O L log( Ldiza.=")? iterations.
8
See Martínez-Rubin al. (2024, Proposition 2) for the proof.
30

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Fact 21 (Projected Riemannian Gradient Descent (PRGD)). Let J M IR be a p-strongly 8-convex, L-smooth and function R Lp/ L. after
1p- finnciitt.uuctionn in g-convex compact subset X C M of a Hadamard manifold M. For initial point zo E X and
22nL log
[f(xo) [f(00)=((2') ,
2L log
LSgd (20, (20,,²") x²)
T 2 min
8
1
2
steps of PRGD with update rule 2141 c Px (Exps, (-ž we have f(xr) f(x²) S
See Martínez- et al. (2023, Proposition 6) for the proof.
We note that the original convergence result of Composite Riemannian Gradient Descent (Martínez-Rubie et al., 2024, Proposition 5) contains a minor error. The following proposition a corrected version.
Proposition 22 (Composite Riemannian Gradient Descent (CRGD)). Let M be uniquely geodesic Riemannian manifold and let X' C M be compact and g-convex. Let f .M- -> R be g-convex and L-smooth in X and g M - R be g-convex. proper and lower semicontinuous in X such that F def f + g is p-strongly g-convex in X, and x² del arg min F(x). Define the update rule of CRGD as follows
L F141 arg min (VS(os), Loga, (v)) ((..,))² + s(v)
yEX
Then
F( F(x*) C(F(()))- - F(x))), where C del 1 1- (/-1/(A))
L 1/2 if < 1/2
and in particular
F(TT) - F(x")
F(x*))
Proof. We first note that the arg min in the update rule exists. Since g is proper, lower semicontinuous and g-convex in X, we have that y def X dom (g) non-empty, closed and if x E y and v E 0g(x), we have that {y E 3 L dd u)2 + (u, (V), & L d(r,, x) } is compact by strong convexity of +> d(x,, )² We also have that {y Y d( y) + (V)()) Logz, (v)) S x)),,, + (Ix), Log2, (r)))} is compact. The union of these two compact sets is compact and if we consider not in this union, have 2 below
L (Vf(),), (z)) + d(a,, =)² 9 + g(2) [V(x),, (z)) + d(xr, g(z)
=(()))) + (v, (z)
2
2
L
((a)),Toog (x)) d(x,,,)) g(x),
2
where 4 uses 0g(r). This means that the minimization problem can be constrained to this union only and since it is compact the arg min exists.
Now we prove the convergence result. We have
L ((f))((((())).. zi)a + dz x1)² + g(2)
F(x+11)
min x
F(x) + - d(x,, d(xx,ar)²
min sEx
[F((**) + (1 - -a)) + Laz
min aE(0,1]
2 d(x", xrr)
(58)
F(x:) 1 1- T,
min xc(0,1]
(F(sz) - F(x')))
p1
1
F(x:) min
(F(z.) - F(x"))
4L' 2
31

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Above, ! holds by smoothness and the update rule of the composite Riemannian gradient descent algorithm. The g- convexity of f implies 2). Inequality 3 results from restricting the min the geodesic segment between x" and 22 that Exp2, (aLogg, (x*) + (1 a)) Log (2z)). We also use the g-convexity of F. In ④ we used strong convexity of F to bound _d(=", xx1²² I (xt) - F(=)). Finally, in ( we substituted by the value that minimizes the expression, which
max 1, 1/2LL. Subtracting F(x=) ) to the inequality above yields
F(z141)-F(( - = (1-min/ min
{ { dl (4L'2)
()) (F(x:)-F(x")
This bound does not improve for L// S 1/2. We can further improve the bound for L/μu S 1/2. Indeed, we have
1 L d(
2 L (F((x) 2²)
F(1(+1) F(x'
2
where 1 holds by Corollary 23 and 2 holds by j-strrong g-convexity of F in X. Subtracting F(x") to the inequality ahove yields
- - (F(()))
For L/μ S 1/2, we have L/P S (1 min { 21). Recursively applying the inequalities from t = to T yields
1 w/(AL) if L/p 1/2 if Lf 1/2
s CO (F(zg) F(x")), where del
Corollary 23 (Composite warm start). Consider the setting of Proposition 22. Then, have for all a X that
F(I+1) - F()) 2)).
for all E X. Corollary 24. Let M be finite-dimensional uniquely geodesic Riemannian manifold. Further let f be L-smooth and g-convex in X and let g be g-convex, lower semicontinuous and proper X such that F del f + g is p-strongly g-convex in X, where X B(x", (1 + x))) for some c > and x= arggin min F(x)). Let
Proof. The proof follows from in (58) by noting that min F(x)+ dd(,, S
L arg min { [og (v)) 2 d( v)² + s(v)
+ def
BEM
Then, if L/p S
L d(x 10t,x1/= < d((xxx')² s d(x,,')²
1
Proof. Let the following be the optimizer, constrained to X.
(Vf(z), (v)) _ ((2, ((o,v))+o(v)) aw))
L
+ def arg min
BEX
Then we have
2 L 1 2 (F(*)) -(x))))((())) dxt x)²² <
where ! hold by p-strong g convexity of X and 2 implies that the constraints are inactive and x -
follows by Corollary 23, Hence 5 lies in the interior of X,, which
32

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
E. Experiments
consider a robust version of the Karcher mean (Karcher, 1977) for points Ui......b. U/ E M. Previous works controlled the degree of robustness through regularization (Zhang et al., 2023; Jordan al., 2022), i.e.
min max ZEM BEEM
F(u, (y), (y....., (un.ton........ vn)) der 1 d(r, 1.)²
n Y
Σ
d(y Di)
(59)
n1
where y controls the amount of robustmess. We formulate robust Karcher variant based constraints, i..,
min max Flrr, (yi,.... yn)),
(60)
zEM B.E
where V/ dnl Bly,, R) for all i E [n]. This formulation allows for a more fine- tme-grained influence of the robustness via the radius of the constraints balls.
We implement the experiments using the Pymanopt Library (Townsend et al., 2016) in the symmetric positive definite (SPD) manifold s def {M Rdxd; M = =M .M > 0} equipped with the intar-iivvariant metric and the d-dimensional (n)) in terms of the duality gap
hyperbolic space Hd. We measure the performance of point (#, (01.....9.))
max F(2, (yI....,, Un)) - min F(x, (ū).... (DI....,9)) 9n))) BEE
ZEM
Note that for both (59) and (60), we require > (D. where H is the diameter a the set containing x and Øi. order to ensure that the problem is g-convex, g-concave. In the following, show that is sufficient to choose D der 1+ R based how generate instances of (60). First, we generate random point on the manifold using the man fo 1 d randdm__opppe _ommppoiiii p nt () function. Then, we generate the centers y/4 Logg Logg(t:/llee (lg) based on sampling random tangent vectors e E Ty using the manifold the Karcher mean of the points ......, Nn. i... KM(Y yn) = arg min 2n
() function. That way, we know that all y: Byg 1). This ensures that L Ei= d(x, y1) also lies in B 1)
by Ruuboo et al. (2024, Proposition 30). Since we constrain the variables ÿi to lie By, R), we have that yi E B(g. 1 + R.) and follows that KM )n) also lies in B 1 + R) by Martinez-Rubee et al. (2024, Proposition 30).
We have that (y)..... Vn)) is 1-strongly g-convex and (7 -nt-stnnyyyy g-concave, for y Cp. That means that ensure in particular that the problem is strongly g-convex and strongly g-concave.
We run RIODAPRGD on (60) with a fixed number of 3 PRGD steps per subroutine, which means that each iteration of RIODAPRGD require 12 PRGD steps. Setting / = 0.01 and ? = SD ensures that the problem is strongly g-concave in (y1...., yn.) as our bound on is loose. For the experiments, RIODAPRGD is run for 1k iterations, corresponding to 12k gradient oracle calls. The step size (10-1, 10-2 10-3) of PRGD and the proximal parameter 1) E (10-1, 10-2) are optimized find the best hyperparameters via grid search.
The following two figures show the convergence behavior of RIODApRGD in terms of the duality gap for experiments run in both the hyperbolic space 150000 and the SPD manifold $100 each with = 50 points. We observe linear convergence in both cases, which aligns with our theoretical analysis.
33

---

Implicit Riemannian Optimism with Applications to Min-Max Problems
Hd with d 5000 and 50 centers
10a
100
Duality Gap
10
10
10-6
200
400
600
800
1000
Iterations
Figure I: Convergence of RIODAPRGD the robust Karcher mean problem (60) in terms of the duality gap with À 0.01,
0.01
S with d= 100 and n 50 centers
100
Duality Gap
10-1
10-2
200
400
600
800
1000
Iterations
Figure 2: Convergence of RIODApRGD on the robust Karcher mean problem (60) in terms of the duality gap with X 0.1. 0.0001
34


Reviews:
[{"review_id": "TtUb8zohGx", "reviewer": "Reviewer_qPnh", "summary": "This paper proposes implicit Riemannian optimistic online methods for problems with g-convex and g-concave objectives, accommodating in-manifold constraints and matching state-of-the-art Euclidean rates. The analysis removes the dependence on geometric constants which closes the gap between the Riemannian problem and its Euclidean counterpart, in some sense. The principle is applied to the (Riemannian) minmax problem and obtains new results. Experiments on the Karcher mean problem are implemented to demonstrate the effectiveness of the proposed methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Experiments in online learning settings would strengthen the paper\n \nWe note that the online learning setting assumes an adversarial agent generating losses against our algorithm. This means that in order to empirically validate the bound, we would need to craft a worst-case adversary to play against our algorithm. This is not only impractical, but it is also undesirable since online learning is a framework that says that we perform well with respect to the best fixed action, and so one also wants to see if it also performs well in favorable scenarios.\n\nIn the literature, typical ways of validating online learning bounds in practice are settings where losses are unpredictable, just as the landscape of min max optimization losses.\n\n> One of the main contributions emphasized by the authors is the removal of dependence on geometric constants (e.g., $\\zeta$ ) from complexity bounds. Could the authors provide intuitive explanations regarding why the proposed framework successfully circumvents this geometric hurdle, whereas previous methods have not?\n\nThere are several independent factors that made our final result possible. We found that (A) implicit (proximal) approaches make the outer loop of our algorithms be free of these constants if used with optimism, as opposed to most of prior work that uses explicit methods and have to rely on the use of Riemannian Cosine-Law Inequalities introducing $\\zeta$ factors (Appendix D.1). Then (B), achieving such implicit optimism requires a careful structure where losses are not linearized since the linearizations are not g-convex (unlike in the Euclidean space). Finally (C) the use of a subroutine such as CRGD as opposed to the most commonly used Riemannian Gradient Descent ones makes the inner problem be also free of these constants, up to a log factor.\n\n> The comparison presented in Table 2 clearly outlines the superiority of this work over existing methods. It would be insightful to experimentally compare the CRGD-based version and other proposed methods with some of the algorithms listed in Table 2.\n\nWe focused on showcasing that we can effectively optimize problems with in-manifold constraints, which was not possible to optimize before, except with RAMMA in [Martínez-Rubio et al. (2023)](https://arxiv.org/abs/2305.16186). While this method is of theoretical interest, as it establishes new upper bounds, it is highly complex and consists of 5 loops, making it impractical.\n\n> In line 225 (right column)...\n\nThanks for pointing this typo out, it should have been \\( \\sum_{i=1}^{t}\\ell_i(x) +\\tilde{\\ell}_t(x) + \\frac{1}{2\\eta}d(x_t,x)^2 \\).\n\n> Corollary 2 reveals that implementing the proposed framework with PRGD still introduces dependence on the geometric constant while using CRGD does not. Is the removal of geometric constants primarily due to the choice of the optimization subroutine (CRGD) rather than the proposed framework (RIOD) itself?\n\nNote that in the online setting, the regret depends only on the cumulative cost $\\sum_{t=1}^T \\ell_t(x_t)$ paid for the agent's actions, and is independent of the oracle complexity. Hence, the improved **regret** guarantees (table 1) are independent of the oracle complexity of the optimization subroutine used to compute the actions. \n\nThe improvement in terms of the regret is achieved via our inexact implicit optimistic technique. Corollary 2 only discusses the oracle complexity of implementing the subproblems up to the specified precision, which is orthogonal to the regret. Removing the geometric constant in the subroutine is mostly due to CRGD. On the other hand, when applying our method to optimization, the complexities do multiply, making necessary to be free of these constants at both levels, but CRGD only adds a log factor. \n\nThe design of the subroutine with our implicit approach has other advantages orthogonal to the use of CRGD or any other subroutine, such as removing the need to know the initial distance a priori or the Lipschitz constant (see table 2).\n\nWe appreciate that the reviewer found the paper well-written and valued our results in Riemannian online learning and minmax problems, overcoming several difficulties in existing work. If you now have a better opinion of our work, we kindly ask you to consider increasing your score.", "claims_and_evidence": "The paper is well-written, and the presentation of Table 1 and Table 2 is detailed, clarifying contributions to Riemannian optimization, online learning, and minmax problem.", "methods_and_evaluation_criteria": "The extension to minmax problem is interesting, which broadens the work's applicability in machine learning community.", "theoretical_claims": "The theory is solid, and the method (RIOD), with the min-max extension (RIODA) is shown to yield good regret and oracle-complexity bounds that overcome difficulties in existing work.", "experimental_designs_or_analyses": "The experiments provided in this paper are limited exclusively to the minmax setting. However, since the original motivation of this work is to address the **Riemannian online learning problem**, the minmax experiments should serve as an illustrative application rather than the primary experimental validation. Expanding the experimental section to assess performance in online learning settings would significantly strengthen the paper and better align with its stated purpose.", "relation_to_broader_scientific_literature": "The extension to Riemannian minmax problem is interesting, which broadens the application of Riemannian optimisatoin.", "essential_references_not_discussed": "It seems that all the highly related references are discussed.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See questions.", "questions_for_authors": "1. One of the main contributions emphasized by the authors is the removal of dependence on geometric constants (e.g., $\\zeta$) from complexity bounds. Could the authors provide intuitive explanations regarding why the proposed framework successfully circumvents this geometric hurdle, whereas previous methods have not?\n2. Corollary 2 reveals that implementing the proposed framework with PRGD still introduces dependence on the geometric constant $\\zeta$ while using CRGD does not. This raises a natural question: **is the removal of geometric constants primarily due to the choice of the optimization subroutine (CRGD) rather than the proposed framework (RIOD) itself?** Clarifying this point would help better highlight the true sources of improvement in the paper.\n3. Adopting CRGD as a subroutine removes dependence on $\\zeta$. However, implementing the CRGD update steps might introduce additional computational complexity in practice. Therefore, it would be valuable to experimentally implement and compare the CRGD-based version of the algorithm, rather than limiting the discussion solely to theoretical advantages.\n4. In line 225 (right column), where the author explains OFTRL algorithms without linearizing the loss functions, the statement \"minimizing $\\sum_{i=1}^t\\ell_i(x_i)+\\tilde{\\ell}_t(x_t)+\\frac{1}{2\\eta}d(x_t,x)^2$\" seems confusing in that the variable $x$ only appears in the last term of the objective.\n5. The comparison presented in Table 2 clearly outlines the superiority of this work over existing methods. However, in Appendix E, the implementation only includes the proposed approach. It would be insightful to experimentally compare the proposed methods with some of the algorithms listed in Table 2. \n\nI would like to increase my grade if the concerns are addressed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iHsMW6ghzM", "reviewer": "Reviewer_fAnn", "summary": "In this paper the authors consider Riemannian optimism on Hadamard manifolds.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Experimental results\n\nWe note that as stated in the paper, we did provide experiments in Appendix E with an implementation of our method, in a constrained problem setting, an application that only one other method (RAMMA, an impractical method) could tackle before, showing that now it is possible to efficiently solve such problems.\n\nThe Hadamard assumption is standard in the field and quite general (accelerated minimization algorithms [[1]](https://proceedings.mlr.press/v195/martinez-rubio23a.html), lower bounds, [[2]](https://proceedings.neurips.cc/paper_files/paper/2021/hash/201d546992726352471cfea6b0df0a48-Abstract.html), [[3]](https://proceedings.mlr.press/v178/criscitiello22a.html), online learning [[4]](https://www.jmlr.org/papers/v24/21-1308.html), [[5]](https://proceedings.neurips.cc/paper/2021/hash/ee389847678a3a9d1ce9e4ca69200d06-Abstract.html), [[6]](https://proceedings.mlr.press/v195/hu23a.html), among many others [[7]](https://www.tandfonline.com/doi/abs/10.1080/02331934.2020.1810248), [[8]](https://www.tandfonline.com/doi/full/10.1080/02331934.2022.2088369), [[9]](https://www.tandfonline.com/doi/full/10.1080/01630563.2018.1553887), [[10]](https://link.springer.com/article/10.1007/s10208-023-09628-5), [[11]](https://searchworks.stanford.edu/view/13531274), [[12]](https://www.sciencedirect.com/science/article/pii/S0362546X02002663)).\n\nThe Hadamard case is challenging enough, note that besides other optimization problems listed above, **7 papers before ours** study our minmax problem and none of them could achieve our parameter freeness, or working with constraints or achieving the optimal convergence rates. Similarly, for the online learning case, prior work could not achieve the optimal regret, while at the same time they had unreasonable assumptions, like some circularity between the step sizes (requiring a specific bound on the iterates a prior) and where the iterates lied.", "claims_and_evidence": "Theoretical paper, no evidence presented.", "methods_and_evaluation_criteria": "None present.", "theoretical_claims": "Yes, they were briefly checked.", "experimental_designs_or_analyses": "None.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The authors claim that their concentration bounds no longer rely on the curvature of the space is a strength, however, Hadamard manifolds have non-positive curvature. The issue I see with this is that positively curved spaces are the challenging manifolds, in a sense. For instance, in the estimation of the Karcher mean, there are strong limitations on positively curved spaces but on non-positively curved spaces there is no such issues. Generally speaking, non positively curved manifolds behave very similar to Euclidean spaces and thus I don't see the results of this paper as being surprising. Lastly, the main paper didn't have any experimental or simulation results which I see as a huge limitation.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XWMCeRsvo4", "reviewer": "Reviewer_kVH1", "summary": "This paper studies Riemannian online optimization and min-max optimization. The authors propose a novel online optimistic Riemannian optimization algorithm with inexact updates, which achieves optimal dynamic regret, and also enforces in-mainfold constraints. The authors then applied their online optimization method to Riemannian min-max optimization and obtain either reduced complexity or same rates without requiring the knowledge of certain parameters.\n\n## Updated Review ###\n\nI have read the rebuttal and the other reviews. I would like to thank the authors for their detailed feedback, which addresses most of my major concerns. Regarding the issue raised by Reviewer fAnn, I agree with the authors that online learning on Hadamard manifolds is a challenging problem, and there has been a long line of research in this area.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> this paper does not have experiments.\n\nWe note that as we stated in the paper, we did provide experiments in Appendix E to validate our theory, with an implementation of our method in a constrained problem setting, for an application that only one other method (RAMMA, an impractical method) could tackle before.\n\n> to implement the proposed algorithm we need to solve two optimization problems at each round, which requires multiple queries of the gradients, and it makes the setting not truly \"online\"\n\nThe action $\\tilde{x}_t$ which RIOD chooses at time $t$ is computed based on an implicit step on the hint function $\\tilde{\\ell}_t$ and the loss from the previous round $\\ell_{t-1}$ (this dependence is implicit via the iterate $x_{t}$). RIOD **does not** require the knowledge of the loss function $\\ell_t$ before choosing its action. Therefore, our algorithm fits in the classical online optimization setting, which assumes that after choosing an action, the agent observes the **full** loss function $\\ell_{t-1}$ and does not specify what the agent does with it: querying the gradient more than once is always permitted.\n\nNote that one of the previous optimistic methods in Riemannian optimization [Hu et al. (2023)](https://proceedings.mlr.press/v195/hu23a.html) also queries the gradient more than once per round.\n\nIn fact, in many other online learning settings **exact minimization** of the previous loss plus possibly some regularizer is assumed, and some other online learning papers studied implicit updates where several gradients are taken [Kivinen & Warmuth (1997)](https://www.sciencedirect.com/science/article/pii/S0890540196926127), [Campolongo & Orabona (2020)](https://proceedings.neurips.cc/paper/2020/hash/9239be5f9dc4058ec647f14fd04b1290-Abstract.html) [Chen & Orabona (2023)](https://proceedings.mlr.press/v202/chen23t.html) with some advantages over explicit methods. Note however that no work obtained an optimistic online learning algorithm using implicit updates.\n\n\n> However, in this paper (i.e., lines 4 and 6 of Algorithm 1), to implement the proposed algorithm we need to solve two optimization problems at each round, which [...] [introduces] extra dependence on $L$ and $\\zeta$\n\nThe error criteria of the updates in lines 4 and 6 of Algorithm 1 depend on $L$ and $\\zeta$, but this only introduces a logarithmic dependence when using CRGD. In any case, the regret metric is independent of the gradient complexity so this does not imply a dependence on $L$ and $\\zeta$ in the regret bounds, not even a logarithmic one.\n\n> Finally, in Corollary 2, it says that the number of implements depend on $\\eta$;, so I am not sure how to set the number of implements if eta is not known (since $eta=1/sqrt{V_T}$ and $V_T$ is not known).\n\nIn general, RIOD works for any $\\eta>0$ in contrast to the previous explicit optimistic methods, which require $\\eta\\lesssim 1/L$ (and possibly require some geometric terms in the Riemannian setting) in order to show the regret bound, that matches the OOMD [Rakhlin et al. (2013)](https://proceedings.neurips.cc/paper/2013/hash/f0dd4a99fba6075a9494772b58f95280-Abstract.html). As for [Rakhlin et al. (2013)](https://proceedings.neurips.cc/paper/2013/hash/f0dd4a99fba6075a9494772b58f95280-Abstract.html), in this work we do not focus on adapting for the best value of \\eta. But we note that (A) we did not require this to obtain optimal convergence for smooth g-convex g-concave optimization and (B) in the general case, when $V_T$ is not known in advance, we can follow the method laid out in Theorem 3, [Zhao et al, (2020)](https://proceedings.neurips.cc/paper_files/paper/2020/hash/939314105ce8701e67489642ef4d49e8-Abstract.html), which is based on using an expert meta-algorithm, that is not dependent on the type of algorithm being run. This methods was shown to work in the Riemannian setting in [Hu et al. (2023)](https://proceedings.mlr.press/v195/hu23a.html). \n\n> Since in the sub-problems, the number of iterations depend on $\\zeta$, I think the final \"real\" regret should also depend on zeta, as the total number of iterations is not $T$ (but $T$ times the number of inner iterations).\n\nIn the online setting, the computational or gradient complexity is an independent metric from the regret, so there is no extra factor. But indeed in the minmax problem both metrics multiply in order to obtain the total gradient complexity, that yields our rates in Table 2, which contain a dependence on $\\zeta$ for PRGD or RGD, but only a logarithmic factor for CRGD. This showcases the power of CRGD when it comes to reducing the subproblem complexity.\n\nWe appreciate that the reviewer found the paper well-written and valued our results in Riemannian online learning and minmax problems, overcoming several difficulties in existing work. If you now have a better opinion of our work, we kindly ask you to consider increasing your score.", "claims_and_evidence": "The claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The evaluation Criteria are dynamic regret for online optimization convergence rate for min-max optimization, which are standard.", "theoretical_claims": "All theoretical claims are accompanied by proofs.", "experimental_designs_or_analyses": "this is a theory paper and does not have experiments.", "relation_to_broader_scientific_literature": "This paper did a good job on discussing and comparing with previous work. I particularly appreciate the two tables on page 4, which clearly present all the convergence results and conditions for existing methods.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengthes:\n\nThe major advantage of the proposed method is that it is the first algorithm for minimizing the dynamic regret on Riemannian manifold that can **enforce in-manifold constraints**, which is a significant and important contribution to this area. In previous work, such as [Hu et al. (2023a)], the algorithm can only minimize \"improper\" dynamic regret, that is, the decision set is larger than the competitor. This is not very satisfying as it means that the learner can pick decisions outside of the constrained set. This paper successfully solved this problem with novel inexact updates. \n\nMoreover, the authors applied their optimism methods for Riemannian min-max optimizaiton, which improve on prior works by either reducing the complexity or not requiring the knowledge of certain parameters.\n\nWeaknesses:\n\nMy major concern about the proposed methods is about the computational complexity. \n\nIn [Hu et al. (2023a)] and [Wang et al. (2023b)], the algorithms are usually iterative, that is, to update the decision, the algorithm only need to query the Rimannian gradients **once** and commit the update. However, in this paper (i.e., lines 4 and 6 of Algorithm 1), to implement the proposed algorithm we need to solve two optimization problems at each round, which requires multiple queries of the gradients, and it makes the setting not truly \"online\" and also introduce extra dependence on L and \\zeta. Finally, in Corollary 2, it says that the number of implements depend on \\eta, so I am not sure how to set the  number of implements if eta is not known (since eta=1/sqrt{V_T} and V_T is not known). \n\nSince in the sub-problems, the number of iterations depend on \\zeta, I think the final \"real\" regret should also depend on zeta, as the total number of iterations is not T (but T times the  number of inner iterations).", "other_comments_or_suggestions": "Please see above.", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aO6caYLzcp", "reviewer": "Reviewer_D6BU", "summary": "This paper studies Riemannian online optimization as well as min-max optimization problems. The main contribution is to propose algorithms for these problems and provide theoretical analyses.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> For online Riemannian optimization, the authors apparently remove a spurious curvature-dependent term from the upper bound in previous analyses. However, curvature-dependent terms re-appear in the time-complexity in the inner steps of their algorithm.\n\nNote that in the online setting, the computational or gradient oracle complexity is a metric independent from the regret. That being said, in minmax and other applications, both metrics translate to computational or gradient oracle complexity, since they are multiplied to obtain the final complexity. \n\nThe implementation using our CRGD subroutine has an oracle complexity which **does not introduce curvature terms**, except in a mild logarithmic term. This showcases the power of CRGD when it comes to reducing the subproblem complexity. We provided the time complexity of PRGD as well, for comparison, since it is a widely used and natural subroutine, this one does have curvature terms.\n\n> It appears that the main improvement relative to previous work is the removal of pre-existing assumptions that circularly linked the curvature and the step-sizes, those being difficult to verify.\n\nWe would like to note that beyond the contribution mentioned by the reviewer we also improve in the following:\n\n - Our method can explicitly handle bounded in-manifold constraints, which are interesting in their own right, since constraints are also critical for online optimization algorithms, even in the Euclidean setting.\n\n - We further obtain important new results in min-max optimization.\n    - Our methods reduce the computational complexity with respect to other constrained methods, it obtains a near optimal gradient oracle complexity, and does not require the knowledge of the initial distance to a solution $R$ and the Lipschitz constant $G$ (see table 2). \n    - It was previously unknown if achieving our rate was possible, since in fact in g-convex and $L$-smooth minimization, nearly matching Euclidean upper bounds is impossible due to lower bounds implying an inherent hardness coming from the geometry, but we showed that the minmax problems are of a different nature.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did check the proofs in any detail.", "experimental_designs_or_analyses": "There are no experiments, but I don't think they are necessary.", "relation_to_broader_scientific_literature": "For online Riemannian optimization, the authors apparently remove a spurious curvature-dependent term from the upper bound in previous analyses. However, curvature-dependent terms re-appear in the time-complexity in the inner steps of their algorithm. It appears that the main improvement relative to previous work is the removal of pre-existing assumptions that circularly linked the curvature and the step-sizes, those being difficult to verify.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qMnGMqyrVr", "reviewer": "Reviewer_hBQp", "summary": "The paper addresses online optimization and min-max optimization on Hadamard manifolds. The authors propose a Riemannian optimistic online learning algorithm called RIOD, designed to match state-of-the-art Euclidean regret bounds while handling in-manifold constraints. Leveraging RIOD, they develop a min-max solver that likewise exhibits near-optimal rates and can enforce constraints.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for their time taken revising our manuscript, as well as the appendix and the experimental section.", "claims_and_evidence": "The claims are well supported.", "methods_and_evaluation_criteria": "The paper addresses the previously incomplete story of optimistic methods on manifolds by introducing implicit updates that exactly preserve in-manifold constraints. This resolves the limitation that arises in other works.", "theoretical_claims": "The theorems and propositions are well posed and formally proved.", "experimental_designs_or_analyses": "The experiments are well designed.", "relation_to_broader_scientific_literature": "Most prior works either avoided constraints or accepted “improper” iterates that stray from the feasible set. By contrast, RIOD ensures proper iterates with classical regret bounds.", "essential_references_not_discussed": "The references are well discussed.", "other_strengths_and_weaknesses": "The results in the paper are novel and strong. This work is a substantial step in unifying the benefits of optimistics online learning with the geometry of negatively curved manifolds.", "other_comments_or_suggestions": "No comments", "questions_for_authors": "No questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All the reviewers are appreciative of the work and believe that the paper presents interesting insights for enforcing the manifold constraint. The proposed updates are definitely novel. A concern which has been raised is the lack of experiments.
Decision: Accept (poster)