First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
Authors: Michael Jordan
Tianyi Lin
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Venue: NeurIPS 2022 Accept (2022)
Keywords: min-max optimization
riemannian optimization
robust manifold
robust PCA
Geodesic-convex-concave function

Abstract: From optimal transport to robust dimensionality reduction, many machine learning applications
can be cast into the min-max optimization problems over Riemannian manifolds. Though many
min-max algorithms have been analyzed in the Euclidean setting, it has been elusive how these
results translate to the Riemannian case. Zhang et al. (2022) have recently identified that geodesic convex
concave Riemannian problems admit always Sion’s saddle point solutions. Immediately, an important
question that arises is if a performance gap between the Riemannian and the optimal Euclidean space
convex concave algorithms is necessary. Our work is the first to answer the question in the negative:
We prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate at a
linear convergence rate at the geodesically strongly convex concave case, matching the euclidean one.
Our results also extend to the stochastic or non-smooth case where RCEG & Riemanian gradient
ascent descent (RGDA) achieve respectively near-optimal convergence rates up to factors depending
on curvature of the manifold. Finally, we empirically demonstrate the effectiveness of RCEG in
solving robust PCA.

First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
Michael Jordan
Emmanouil V. Vlatakis-Ckaragkounis University of California, Berkeley
Tianyi Lin
(jordances,
iactandsssddrree darren line, emvlatakis() berkeley edu
Abstract
From optimal transport to robust dimensionality reduction, plethora of machine learning applications can be cast into the min-max optimization problems over Riemannian manifolds. Though many min-max algorithms have been analyzed in the Euclidean setting, it has proved elusive to translate these results to the Riemannian case. Zhang et al. have recently shown that geodesic convex concave Riemannian problems always admit saddle- -oint solutions. Inspired by this result, we study whether a performance gap between Riemannian and optimal Euclidean space convex concevee algorithms is necessary. We answer this question in the negative- we prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at linear rate in the geodesically strongly- convex-concave case, matching the Fuclidean result. Our results also extend the stochastic or non-smooth case where RCEG and Riemanian gradient ascent descent (RGDA) achieve near-optimal convergence rates up to factors depending curvature of the manifold.
Introduction
Constrained optimization problems arise throughout machine learning, in classical settings such as dimension reduction [2], dictionary learning [3, 4], and deep neural networks [5], but also emerging problems involving decision-making and multi-agent interactions. While simple convex constraints (such as norm constraints) can be easily incorporated in standard optimization formulations, notably (proximal) gradient descent [6-10], in range of other applications such matrix recovery [11, 12], low-rank matrix factorization [13] and generative adversarial nets [14], the constraints are fundamentally nonconvex and are often treated via special heuristies.
Thus, general goal is to design algorithms that systematically take account of special geometric structure of the feasible set [15-17]. A long line of work in the machine learning (MI.) community has focused on understanding the geometric propertics of commonly used constraints and how they affect optimization; [see, e.g., 18-26]. A prominent aspect of this agenda has been the re- expression of these constraints through the lens of Riemannian manifolds. This has given rise to new algorithms [27, 28] with wide range of ML applications, inclduing online principal component analysis (PCA), the computation of Mahalanobis distance from noisy measurements [29], consensus distributed algorithms for aggregation in ad-hoc wireless networks [30] and maximum likelihood estimation for certain non- Gaussian (heavy- or light-tailed) distributions [31].
Going beyond simple minimization problems, the robustification of many MI. tasks can be formulated as min-max optimization problems. Well-known examples in this domain include adversarial machine learning [32, 33], optimal transport [34], and online learning [9, 35, 36]. Similar to their minimization counterparts, non-convex constraints have been widely applicable to the min-max optimization as well [37-41]. Recently there has been significant effort in proving tighter results either under more structured assumptions [42-52], and/or obtaining last-iterate convergence guarantees [38, 40, 48, 53-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

62] for computing min-max solutions in coneeve settings. Nonetheless, the analysis of the iteration complexity in the general non-convex non-concave setting still in its infancy [63, 64]. In response, the optimization community has recently studied how to extend standard min-max optimization algorithms such as gradient descent ascent (GDA) and extragradient (EG) to the Riemannian setting. In mathematical terms, given two Riemannian manifolds M,N and a function f:Mx.. + R. the Riemannian min-max optimization (RMMO) problem becomes
min max (z, v)- # yEN
The change of geometry from Euclidean Riemannian poses several difficulties. Indeed, fun- damental stumbling block has been that this problem may not even have theoretically meaningful solutions. In contrast with minimization where an optimal solution in bounded domain is always guaranteed [65], existence of such saddle points necessitates typically the application of topological fixed point theorems [66, 67]. KKM Theory [68]). For the case of convex-concave f with compact sets X' and y. Sion [69] generalized the celebrated theorem [70] and guaranteed that a solution (x*, y²) with the following property exists
min (I,, w²) = f(=", v²) max f(= =EX
yEy
However, at the core of the proof of this result is ingenuous application of Helly's 's lemma [71] for the sublevel sets of f. and, until the work of Ivanov [72], it has been unclear how to formulate an analogous lemma for the Riemannian geometry. As result, until recently have extensions of the min-max theorem been established, and only for restricted manifold families [73-75].
Zhang et al. [1] was the first to establish min-max theorem for flurry of Riemannian manifolds equipped with unique geodesics. Notice that this family is not mathematical artifact since encompasses many practical applications of RMMO, including Hadamard and Stiefel ones used in PCA [76]. Intuitively, the unique geodesic between two points of a manifold is the analogue of the a linear segment between two points in convex set: For any two points æ 22 E X, their connecting geodesic is the unique shortest path contained X that connects them.
Even when the RMMO is well defined, transferring the guarantees of traditional min-max optimization algorithms like Gradient Ascent Descent (GDA) and Extra-Gradien (EG) to the Riemannian case is non-trivial. Intuitively speaking, in the Euclidean realm the main leitmotif of the last-iterate analyses the aforementioned algorithms is a proof that 6, = || 212 is decreasing over time. To achieve this, typically the proof correlates de and 5 via a "square expansion." namely:
| - x 11
x 11 + |0--1 - xz 12 2 21",I-11 x4)
g2
29 Coa(()
Notice, however that the above expression relies strongly on properties of Euclidean geometry (and the flatness of the corresponding line), namely that the the lines connecting the three points T₁, 2t-1 and x² form triangle; indeed, it is the generalization of the Pythagorean theorem, known also as the law of cosines, for the induced triangle (ABC) := {(T,, 11-1, x² x²)). In a uniquely geodesic manifold such triangle may not belong to the manifold as discussed above. As a result, the difference of distances to the equilibrium using the geodesic paths d x²) - al (x;-1, x=) generally cannot be given in closed form. The manifold's s curvature controls how close these paths are to forming a Euclidean triangle. In fact, the phenomenon of distance distortion, as is typically called, was hypothesised by Zhang et al. [1, Section 4.2] to be the cause of exponential slowdowns when applying EG to RMMO problems when compared to their Euclidean counterparts.
Multiple attempts have been made to bypass this hurdle. Huang et al. [77] analyzed the Riemannian GDA (RGDA) for the non-convex non-concave setting. However, they do not present any last-iterate convergence results and, even in the average/best iterate setting, they only derive sub-optimal rates for the geodesic convex-concave setting due to the lack of the machinery that convex analysis and optimization offers they derive sub-optimal rates for the geodesic convex-concave case, which is the problem of our interest. The analysis of Han et al. [78] for Riemannian Hamiltonian Method (RHM), matches the rate of second-order methods in the Euclidean case. Although theoretically faster terms of iterations, second-order methods are not preferred in practice since evaluating second order derivatives for optimization problems of thousands to millions of parameters quickly becomes prohibitive. Finally, Zhang et al. [1] leveraged the standard averaging output trick in EG to derive sublinear convergence rate of O(L/e) for the general geodesically convex-concan Riemannian
2

---

framework. In addition, they conjectured that the use of a different method could close the exponential gap for the geodesically strongly-conver Soonvee-ttrongy-ooom
scenario and its Euclidean counterpart.
Given this background, a crucial question underlying the potential for successful application of first-order algorithms to Riemannian settings is the following:
Is a performance gap necessary between Riemannian and Euclidean optimal convex-concave algorithms in terms of accuracy and the condition number?
1.1 Our Contributions
Our aim in this paper is to provide an extensive analysis of the Riemannian counterparts of Euclidean optimal first-order methods adapted to the manifold-constraingg setting. For the case of the smooth objectives, we consider the Riemannian corrected extragradient (RCEG) method while for non- smooth cases, we analyze the textbook Riemannian gradient descent ascent (RGDA) method. Our main results are summarized in the following table.
Alg: RCEG. Smooth setting with E-Lisschitz Grudient (cf. Assumption 2.1. 3.1 and 3.2)
Perf. Measure
Setting
Complexity
Theorem
Last-Iterate
Det. GSCSC
N(VTO+ + { (og(())
Thm. 3.1
In
Last-Iterate
Stoc. GSCSC
M(VTO + 50 log(())
deEa log(!)) Thm. 3.2 x
Avg-Iterate
GCC
[1, Thm.1]
Avg-lterate
Stoc. GCC
o ( (LVT
Thm. 3.3
Alg: RGDA. Nonsmooth setting with L--lipschitz Function (cf. Assumption D.1 and D.2)
Last-Iterate
Det. GSCSC
L'
Thm. D.1
a
Last-Iterate
Stoc. GSCSC
(L 11'+o"1 Ka
Thm. D.3
Avg-Iterate
Det. GCC
L'Ea
Thm. D.2
Avg-Iterate
Stoc. GCC
2 TEa
Thm. D.4
For the definition of the acronyms, Det and Stoc stand for deterministic and stochastic, respectively. weteely-oove--stoooeee crtongly-concave (cf. Assumption 3.1 or
GSCSC and GCC stand for geodesically Assumption D.I) and geodesically convex-concave (cf. Assumption 3.2 or Assumption D.2). Here E (0, 1) is the accuracy. L, l the Lipschitzness of the objective and its gradient,
l/p j is the condition number of the function, where y is the strong convexity parameter, (To, E Eu) are curvature parameters (cf. Assumption 2.1), and o² the variance of a Riemannian gradient estimator.
Our first main contribution is the derivation of linear convergence rate for RCEG, answering the open conjecture of [1] about the performance gap of single-loop extragradient methods. Indeed, while a direct comparison between dit (zz, (#), and di (x;-1,x²) is infeasible, we are able to establish a relationship between the iterates via appeal to the duality gap function and obtain a contraction in terms of (2,, xr). In other words, the effect of Riemannian distance distortion is quantitative (the contraction ratio will depend on it) rather than qualitative (the geometric contraction still remains under proper choice of constant stepsize). More specifically, we use da (Ir, + d + y²) and d' (2++11 .x')== + dk y²) to bound a gap function defined by [( [[r,,y"~- f(x"""" " (t). Since the objective function is geodesically strongly-convex wwwnnglyycooee-sttongyyyoooom strongly-concave, we have [(t,, - f(x "o"", ūt) is lower bounded by & (dd((á x²)² + d )²) Then, using the relationship between (I Be) and (ft, 1t), we conclude the desired results in Theorem 3. Notably, approach is not affected by the nonlinear geometry the manifold.
Secondly, we endeavor to give systematic analysis of aspects of the objective function, including its smoothness, its convexity and oracle access. we shall see, similar to the Euclidean case, better finite-time convergence guarantees are connected with geodesic smoothness condition. For the sake of completeness, in the paper's supplement we present the performance of Riemannian GDA for the full spectrum of stochasticity for the non-smooth case. More specifically, for the stochastic setting, the key ingredient to get the optimal convergence rate to carefully select the step size such that the noise of the gradient estimator will not affect the final convergence rate significantly. As highlight, such

---

The inverse technique has been used for analyzing stochastic RCEG in the Euclidean setting [79] and our analysis can be seen as the extension the Riemannian setting. For the nonsmooth setting, the analysis is relatively simpler compared to smooth settings but we still need to deal with the issue caused by the nonlinear geometry of manifolds and the interplay between the distortion Riemannian metries, the gap function and the bounds of Lipschitzness of our bi-objective. Interestingly, the rates we derive are near optimal in terms of accuracy and condition number of the objective, and analogous to their Euclidean counterparts.
2 Preliminaries and Technical Background
We present the basic setup and optimality conditions for Riemannian min-max optimization. Indeed, focus some of key concepts that need from Riemannian geometry, deferring fuller presentation, including motivating examples and further discussion of related work, to Appendix A-C.
Riemannian geometry. An n-dimensional manifold M is topological space where any point has neighborhood that is homeomorphic to the n-dimensional Euclidean space. For each æ E M, each tangent vector is tangent to all parametrized curves passing through æ: and the tangent space M of manifold M at this point defined as the set of all tangent vectors. A Riemannian manifold M smooth manifold that is endowed with smooth ("Riemannian")) metric (+ 1) on the tangent space T for each point æ E M. The inner metric induces a norm llz on the tangent spaces.
A geodesic can be seen as the generalization of an Euclidean linear segment and is modeled as smooth curve (map), y [0, 1] + M, which locally distance minimizer. Additionally, because of the fla-flatness of manifold different relation between the angles and the lengths of an arbitrary geodesic triangle is induced. This distortion can be quantified via the sectional curvature parameter MM thanks to Toponogov's theorem [80, 81]. A constructive consequence of this definition are the
Positive Curvature
Zero Curvature
Negative Curvature
AM
K.M 0
K.M < 0
trigonometric comparison inequalities (TCIs) that will be essential in our proofs; see Alimisis et al. [82, Corollary 2.1] and Zhang and Sra [83, Lemma 5] for detailed derivations. Assuming bounded sectional curvature, TCIs provide a tool for bounding Riemannian "inner products" that more troublesome than classical Euclidean inner products.
The following proposition summarizes the TCIs that we will need; note that if Kmin fimax (i.e., Euclidean spaces), then the proposition reduces to the law of cosines.
Suppose that M is Riemannian manifold and let A be geodesic triangle in M with the side length and let A be the angle between and Then, we have
Proposition 2.1
If M that is upper bounded by fimax > and the diameter of M is bounded by x then <Mmaax"
a² 2 (Kmax, c) + è² cbs(os
where E(K, c) == :0 for K < 0 and E(K, c) == c/Kcot(c//k < 1.forx>. 0. If K is lower bounded by Kmiin then
a²
E(Kmin, c) .b +22 cosc (A);
where co
> if < and E(1, c) : if 2
Also, in contrast to the Euclidean case, I and frr) do not lie in the same space, since M and T.M respectively are distinct entities. The interplay between these dual spaces typically is carried out via the exponential maps. An exponential map at a point E M is a mapping from the tangent space T.M to M. In partieular, y == Exp, (w) E M defined such that there exists geodesic 7 [0, + M satisfying (0) I, (1) and 7((0)

---

map exists since the manifold has a unique geodesic between any two points, which we denote as Exp,- .M + M,M. Accordingly, we have (I, y) |Exp ( (y)llz is the Riemannian distance induced by the exponential map.
Finally, in contrast again Fuclidean spaces, cannot compare the langent vectors at different points z, y E M since these vectors lie in different tangent spaces. To resolve this issue, it suffices to define transport mapping that moves a tangent vector along the geodesics and also preserves the length and Riemannian metric (:)) indeed, we can define parallel transport F T.M + T M such that the inner product between any u, T.M is preserved: i.e.. (u, v)2 (T)))),T())))
T&M
M
Expx (v)
Riemannian min-max optimization and function classes. We let M and V be Riemannian manifolds with unique geodesic and bounded sectional curvature and assume that the function f : .M x N + R is defined on the product of these manifolds. The regularity conditions that we impose on the function f are as follows.
Definition 2.1 A function M X + IR geodesically T--Lipschitz for Vz, x' E M and by. v' EN, the following statement holds true: (f y) ((aa'''))) S I(dy(a, x') + dx(y, v)), Additionally, function f is also differentiable, it is called geodesically E-smooth for Vx, x' M and Vy. y E N, the following statement holds true,
Ilgrad_ y) T grad f( y''ll Iggrad (I, v) y grad g f('', ((', ,y''ll
((dm(x,>)) + dy(y, & (dd
where (grad ( 1/), gr [ ,')) E T. x Tyy.N is the Riemannian gradient of I at (x', v/), I is the parallel transport of M from x' x, and 1 is the parallel transport of N from of to y. of
Definition 2.2 A function f M x N + R is geodesically soongly-coveex.ttrnngy--ccaaee with the modulus μs > O if the following statement holds true,
f(x'.)) 2 f(x, y) + j. (xr,)) y).
+ # (dd((,, x'))
for each E N, for each x E .M.
fx,,8) S [(x v) + (subgrad, J y). Exp, (w')) ((dr(,,)))),
where (subgrad,,f v²), subgrad, ('''v))) E T. x T is Riemannian subgradient of f at point (x', (x',y'). A function is geodesically convex-concave if the above holds true with 0.
Following standard conventions in Riemannian optimization [1, 82, 83], we make the following assumptions on the manifolds and objective functions:"
Assumption 2.1 The objective function f .M x N - R and manifolds M and N satisfy
1. The diameter of the domain {(I, y) E M x N -00 f(z,w) < +00} is bounded by D >>> 0. M,N admit unique geodesic paths for any (z, y). (a' (z', MxN.
3. The sectional curvatures of M and N are both bounded in the range [Kmiin Kmaax with femin S 0.
If Emma > 0, assume that the diameter of manifolds is bounded by "Nimax"
Under these conditions, Zhang et al. [1] proved an analog of Sion's 's minimax theorem [69] in geodesic metric spaces. Formally, we have
max min [(x v) = min max f(x v), = yEN
NEN WEM
which guarantees that there exists least one global saddle point (x*,y*) E . x V such that minzeM f (z, ==)=====>>) f(x", y²) maX fx .v). Note that the unicity of geodesics assumption potorithm--ndeeeendee
and imposed for guaranteeing that suddle-point solution always exist. Even though this rules out many manifolds of interest, there are still many manifolds that satisfy such conditions. More specifically, the Hadamard manifold (manifolds with non-positive curvature, Emax 0) has a unique geodesic between any two points. This also becomes a common regularity condition in Riemannian optimization [82, 83). For any point (x. M A,, the duality gap f(, f(x*, ÿ) thus gives an optimality criterion.
'In particular, our assumed upper and lower bounds Kmin, Kmax guarantee that TCIs in Proposition 2.1 can be used in our analysis for proving finite-time convergence.
5

---

Algorithm 1 RCEG
Algorithm 2 SRCEG
Input: initial points (Jo, yo) and stepsizes vj > O.
Input: initial points (Jo, yo) and stepsizes 17 O. for t 0, 2....... ['- do
for t === O, 1.2,... ..., T do
Query (d fyy < (grad_/(ax ve), grad, ( w.)),
Query (g2 92) as noisy estimator of Rieman- nian gradient of at a point (2),.tt..
the Riemannian gradient of f at point (1) Mr)
Be f Expx, (-77 g.).
3; + fx,+,x,,666 (- -2)))-
ÿt 4 +xp,, (1) g.)-
tt < 1-Exp (17 9.)-
Query (Ø [6) + (grad_ (it, De), grad, 9c)),
Query (0'. 0g.) as noisy estimator of Rieman-
the Riemannian gradient of at point (Bt, (t)
nian gradient of f at a point (0z, Dt).
Tt+1 + Expx, (-n 02 + Expa, (x+))-
2141 Exp2, (-1 02 + Exp (2x)). Mt+1 t- Exp,, (n g + Expo, (v:)).
Mt++ 4 Exp,, (1 0 + Exp, (ve)).
end for
end for
Definition 2.3 A point (.) M A is e-saddle point of geodesically convex-concave function f(.-)) if f(, y") f(x'. .0)" S where (x",y") E E x N is a global saddle point.
conneglyyoovvee--ttongyyyoooooo concave with >> 0, it is not difficult to verify the uniqueness of global saddle point (z* yy" E M x N. Then, we can consider the distance gap (d(E, x²)) + (d(U, y²) y²))² as an optimality criterion for any point (8,9) E M x N.
In the setting where f is geodesically
Definition 2.4 A point (.. ú) E M is an e-saddle point of a geodesically strongly-corvex- strongly-concave function f(.,)) if (d(E, + (d(ū.y"))² S e, where (x",y*) E M x N is a global saddle point. If f is also geodesically E-smooth, we denote k = as the condition number.
Given the above definitions, can ask whether it is possible find an c-saddle point efficiently not. In this context, Zhang et al. [1] have answered this question in the affirmative for the setting where is geodesically Ê-smooth and geodesically convex-concave; indeed, they derive the convergence rate of Riemannian corrected extragradient (RCEG) method in terms of time-average iterates and also linear rate in terms of last ilerates when conjecture that RCEG does not guarantee convergence www.ssty-oooocaaatte due to the existence of f is geodesically t-smooth and geodesically strongly-conven catss--ooov----ongeee distance distortion; see Zhang et al. [1. Section 4.2]. Surprisingly, we show in Section that RCEG with constant stepsize can achieve last-iterate convergence at linear rate. Moreover, we establish the optimal convergence rates of stochastic RCEG for certain choices of stepsize for both geodesically convex-concave and geodesically
coreel-ooooeexstoogyyyoooeeee settings.
3 Riemannian Corrected Extragradient Method
In this section, revisit the scheme of Riemannian corrected extragradient (RCEG) method proposed by Zhang et al. [1] and extend to a stochastic algorithm that we refer to as stochastic RCEG. We present our main results
optimal last-iterate convergence guarantee for the geodesically setting (both deterministic and stochastic) and a time-average convergence guarantee for the geodesically convex-concave setting (stochastic). This complements the time-average convergence guarantee for geodesically convex-concave setting (deterministic) [1, Theorem 4. I] and resolves an open problem posted in Zhang al. [1, Section 4.2].
3.1 Algorithmic scheme
The recently proposed Riemannian corrected extragradient (RCEG) method [1] is natural extension of the celebrated extragradient (EG) method to the Riemannian setting. Its scheme resembles that of EG in Euclidean spaces but employs a simple modification in the extrapolation step to accommodate the nonlinear geometry of Riemannian manifolds. Let us provide some intuition how such modifications work.
We start with basic version of EG as follows, where M and N are classically restricted to be convex constraint sets in Euclidean spaces:
proj 17 V.l(a)))))) I++1 + proj - r) Va.(Er.
ft.
g + projy + Vyl(ze, (2)
Mtt1 + proj (ye- + V V (2,, It)).

---

Turning to the setting where M and N are Riemannian manifolds, the rather straight- forward way to do the generalization is to replace the projection operator by the corre- sponding exponential map and the gradient by the corresponding Riemannian gradient. For the first line of Eq. (2), this approach works and leads to the following updates:
Exp,
3t i1 f
17 Aggrdd
1I grad (ft,
De
L f Exp2, (-n (Tre, Yt)), Ut + Exp,, ( Vt).
However, we encounter some issues for the second line of Eq. (2): The aforementioned ap- proach leads to some problematic updates, Iz-1 + Exp,, (-1)- gradzf((e (1a, Dc)) and M++1 <- Expy, (17 grad, (āz, it)): indeed, the exponential maps ExPx, (+) and ExP (.) are defined from Tr.M to M and from N to N respectively. However, we have -grad f Dc) E M and grad, (i)) E N. This motivates us to reformulate the second line of Eq. (2) as follows:
Tz-1 t pr (az 77- [ Ue) (x -.)c- M++1 P +1- V V De) + (ye 9.))
In the general setting of Riemannian manifolds, the terms 2, - Lt and y/ - de become Expa, 1 (x+) E M and Exp (w:) E Ny This observation yields the following updates:
Iz-1 t Exp,, (-n gr de) Expa. (a)),, Ú < Expg, (1 grad ( Uc) Exp (w:)).
We summarize the resulting RCEG method in Algorithm and present the stochastic extension with noisy estimators of Riemannian gradients of ff in Algorithm 2.
3.2 Main results
We present our main results on global convergence for Algorithms and 2. To simplify the presenta- tion, we treat separately the following two cases:
The objective funnctivv f is geodesically E-smooth and geodesically strongly-convex- strongly-concave with ps O.
Assumption 3.1
Assumption 3.2 The objective function f is geodesically E-smooth and geodesically convex-concave.
Letting .y" E M x N be global saddle point of (which exists under either Assumption 3. or 3.2), we let Do = (dm((r, x²) )²))² + (dar(yo y²² and k = f//z for geodesically strongly- convex-strongly-come
setting. For simplicity of presentation, we also define ratio T(: that
measures how non- non-flatness changes in the spaces: T[Kming Nimax] c) our results for Algorithm in the following theorem.
{(Kmiin))) [(smaxx.c)
2 1. We summarize
Theorem 3.1 Given Assumptions 2.1 and 3.1. and letting n min(1/((2 En (2p)), there
exists some > 0 such that the output of Algorithm I satisfies that (d(xT, x²))² (d(yr, ((yrry"))² y)2) S (i.e., an e-saddle point of f in Definition 2.4) and the total number of Riemannian gradient evaluations bounded by
o (((vo++)) log Do
1
(Do))
S.
where = T[Mminn kmax), D) 2 measures how non-flatness changes in M and N and E. {(Kiaax D)= < is properly defined in Proposition 2.1.
Remark 3.1 Theorem 3.1 illustrates the last-iterate convergence of Algorithm I for solving geodesi- problems, thereby resolving an open problem delineated by Zhang et al. [1]. Further, the dependence k. and 1/e cannot be improved since it matches the lower bound established for min-max optimization problems in Euclidean spaces [84]. However, we believe that the dependence
cally woanglly-coveesstrnll--oooooo
and & is not tight, and it is of interest to either improve the rate or establish lower bound for general Riemannian min-mac optimization.
7

---

The current theoretical analysis covers local geodesic strong convex-strong cononaee settings. The key ingredient is how define the local region; indeed. if we say the set of {(x,)) UM(x.x" S 5, (y. y²) S 8) is local region where the function is geodesic strong- strong-concave. Then, the set of {(x. [[r.y)= : (dM(a,, x2) + dyr(ytyy)) S 8²) must be contained in the above local region and the objective function is also geodesic strong woong--ooeex-strongg connuvee. If (Io, Ho) E (((xx)) y) : (dM(2, x=) + +dy(Je. (dy()..""))) S. 8²), our theoretical analysis guarantees the last-iterate linear convergence rate. Such argument and definition of local region were standard for min-max optimization in the Euclidean setting; see Liang and Stokes [55, Assumption 2.1 J. For an important optimization problem that is globally geodesically
Remark 3.2
cowver-stronnyyy refer to Appendix B where Robust matrix Karcher mean problem indeed the desired one.
In the scheme of SRECG, we highlight that (g) and (gh, Ht.) are noisy estimators of Riemannian gradients of f at (It; y1) and (6e. Dt). is necessary to impose the conditions such that these estimators are unbiased and has bounded variance. By abuse of notation, we assume that
9 (2r, 31) + c g grad, (6;, Dc) E
9 = grad, f yt) + Egi
(3)
S grad f
Uc) + Ey-
where the noises (5% 5 and (Ét, (t) independent and satisfy that
E = O, B B[C[]] O,
Eis = O, B = O,
Bill 1| + || - 0² BII + - 0².
(4)
We are ready to summarize our results for Algorithm 2 in the following theorems.
Theorem 3.2 Given Assumptions 2.1 and 3.1, letting Eq. (3) and Eq. (4) hold with a > O and letting So ([log(T)++ogg(r Duo 91) there exists some T > 0 such that the pf 2/2++ + (d(yr, v {)²] S c and the total number of noisy
7 > O satisfy r min{, 241./70' 2p" output of Algorithm 2 satisfies that E [d((rr, xx)x,,x))) Riemannian gradient evaluations is bounded by
o
(((VOO
Do
E log
(
log
So
1.2e
where To T[ Mimin Kmmax), D) 2 measures how non-flatness changes in M and N and E E(Kimaxs D) S is properly defined in Proposition 2.1.
Theorem 3.3 Given Assumptions 2.1 and 3.2 and assume that Eq. (3) and Eq. (4) hold with >
and let r) > 0 satisfies that 1) min 40 V to Torh
1
Do there exists some T > 0 such that the output
of Algorithm 2 satisfies that [ 3²) fx" DT)l S and the total number of noisy Riemannian gradient evaluations is bounded by
( (DO'TO TO
o L
o
where To = T[KKmin Km D) measures how non- non-flatness changes in M and N and Eo E(Nmiin D) 2 1 is properly defined in Proposition 2. The time-average iterates (øT, (r) E M
can be computed by (To, Fo) = (0,0) and the inductive formula: Tt+1 Expa, (44 ExpE, (ix)) and 1 = ExPg. [II Exp 1 (ix)) ) for all 1. - - 0,,,,..,,
Remark 3.3 Theorem 3.2 presents the last-iterate convergence rate of Algorithm 2 for solving problems while Theorem 3.3 gives the time-average convergence rate when the function f is only assumed to be geodesically convex-concave. Note that we carefully choose the stepsizes such that our upper bounds match the lower bounds established for stochastic min-max optimization problems in Euclidean spaces [79, 85, 86], in terms of the dependence on K, 1/c and o², up to log factors.
geodesically soggel-ooooes-sstogly-ooomm
Discussions: The last-iterate linear convergence rate in terms of Riemannian metrics is only limited to geodesically strongly convex-concave cases but other results, c.g., the average-iterate sublinear
8

---

convergence rate, are derived under more mild conditions. This is consistent with classical results in the Euclidean setting where geodesic convexity reduces to convexity; indeed, the last-iterate linear convergence rate in terms of squared Euclidean norm is only obtained for strongly convex-concnt cases. As such, our setting is not restrictive. Moreover, Zhang et al. [1] showed that the existence of global saddle point is only guaranteed under the geodesically convex-concave assumption. For or geodesically
geodesically nonconvex-coneee might not exist and new optimality notions are required before algorithmic design. This question remains open in the Euclidean setting and is beyond the scope of this paper. However, we remark that an interesting class of robustification problems nonconvex-nonconee min-max problems in the in the Riemannian setting; see Appendix B.
eereonnvee-nocconavee cases, a global saddle point
Euclidean setting can be geodesically
Experiments
We present numerical experiments on the task of robust principal component analysis (RPCA) for symmetric positive definite (SPD) matrices. In particular, we compare the performance of Algorithm I and 2 with different outputs, i.c., the last iterate (IT, yr) versus the time-average iterate (ØT, Ör) (see the precise definition in Theorem 3.3). Note that our implementations of both algorithms are based on the MANOPT package [87]. All the experiments were implemented in MATLAB R2021b on a workstation with 2.6 GHz Intel Core i7 and 16GB of memory. Due to space limitations, some additional experimental results are deferred to Appendix G.
Experimental setup. The problem of RPCA [88, 89] can be formulated as the Riemannian min-max optimization problem with an SPD manifold and sphere manifold. Formally, we have
max min MEM #ES4
Mx
a(M, M.)
TI
In this formulation, a: > 0 denotes the penalty parameter, [Milie(n) is sequence of given data SPD matrices, MMSD = {M E Raxd M > 0, = } denotes the SPD manifold, S = {2 E Rd ||ك||| = 1} denotes the sphere manifold and d(;,-) : .Misp x .MEsD + IR is the Riemannian distance induced by the exponential map on the SPD manifold MESD- As demonstrated by Zhang et al. [1], the problem of RPCA is noncomvex-nonconean from Euclidean perspective but is locally geodesically droogll-coomes--trrwy wwwp:/wwwwwtttgoooo/ooooeoo conccave and satisfies most of the assumptions that we make this paper. In particular, the SPD manifold is complete with sectional curvature in [- 2.2 1] [90] and the sphere manifold is complete with sectional curvature of 1. Other reasons why we use such example are: (i) it is a classical one in ML; (ii) Zhang et al. [1] also uses this example and observes the linear convergence behavior; (iii) the numerical results show that the unicity of geodesics assumption may not be necessary in practice; and (iv) this is application where both min and max sides are done on Riemannian manifolds.
Following the previous works of Zhang et al. [1] and Han et al. [78), we generate sequence of data matrices M, satisfying that their eigenvalues are the range of (0.2, 4.5). our experiment, we fix a = 1.0 and also vary the problem dimension d E (25, 50, 100). The evaluation metric is set as gradient norm. We set n 40 and n 200 in Figure and 2. For RCEG, we set r) = 1 where l >>00 0 is selected via grid search. For SRCEG, we set 77 = min f 2 ? where f, > 0 are selected via grid search. Additional results the effect of stepsize are summarized in Appendix G.
1
Experimental results. Figure/ summarizes the effects of different outputs for RCEG; indeed, RCEG-last and RCEG-avg refer to Algorithm 1 with last iterate and time-average iterate respectively. is clear that the last iterate of RCEG consistently exhibits linear convergence to an optimal solution theoretical results in Theorem 3.1. In contrast, the average iterate
in all the settings, verifying of RCEG converges much slower than the last iterate of RCEG. The possible reason is that the problem of RPCA is only locally geodesically the iterates generated during early stage will significantly slow down the convergence of RCEG.
and averaging with
Figure 2 presents the comparison between SRCEG (with either last iterate or time-average iterate) and RCEG with last-iterate; here, SRCEG-last and SRCEG-avg refer to Algorithm with last iterate and time-average iterate respectively. We observe that SRCEG with either last iterate or average iterate converge faster than RCEG at the early stage and all of them finally converge to an optimal solution. This demonstrates the effecttivnnes and efficiency of SRCEG in practice. It is also worth

---

Dimension225
Dimersion-50
Dimension10 100
GradNomm
Gradhomm
Gradhoum
14-
RC RCEG-i BC EC-ang
R-E RCEG.agy
RCFG-last RCEG-ang
Data Parss
Datia Pars
Data PaNs
Figure I: Comparison of last iterate (RCEG-last) and time-average iterate (RCEG-avg) for solving the RPCA problem in Eq. (5) with different problem dimensions d {25, 50, 1003. The horizontal axis represents the number of data passes and the vertical axis represents gradient norm.
S5rencee-25
Brvenddon...
Lerondionn 50
PCS SPi20 last S8i00 ong
55025 ep)
SNCES-193
Oata Fasz
Figure 2: Comparison of RCEG and SRCEG for solving the RPCA problem in Eq. (5) with different problem dimensions d E (25, 50). The horizontal axis is the number of data passes and the vertical axis is gradient norm.
mentioning that the difference between last-iterate convergence and time-average-ieerate convergence is not as significant as in the deterministic setting. This is possibly because the technique of averaging help cancels the negative effect of imperfect information [91, 92].
5 Conclusions
Inspired broadly by the structure of the complex competition that arises in many applications of robust optimization in ML, we focus the problem of min-max optimization in the pure Riemannian setting (where both min and max player are constrained in a smooth manifold). Answering the open question of Zhang al. [1] for the geodesically (strongly) convex-concave case, we showed that the Riemannian correction technique for EG matches the linear last-iterate complexity of their Euclidean counterparts in terms of accuracy and conditional number of objective for both deterministic and stochastic case. Additionally, we provide near-optimal guarantees for both smooth and non-smooth min-max optimization via Riemannian EG and GDA for the simple convex-concave case.
As consequence of this work numerous open problems emerge; one immediate open question for future work is to explore whether the dependence on the curvature constant is also tight. Additionally, another generalization of interest would be to consider the performance of RCEG in the case of Riemannian Monotone Variational inequalities (RMVI) and examine the generalization of Zhang et al. [1] existence proof. Finally, there has been recent work in proving last-iterate convergence in the convex-concave setting via Sum-Of-Squares techniques [62]. It would be interesting examine how one could leverage this machinery in a non-Fuclidean but geodesie-mettri--riende framework.
Acknowledgements
We would like to thank the area chair and five anonymous referees for constructive suggestions that improve the paper. This work was supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number
1--0044---1-276- and by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-2941 The work of Michael I. Jordan also partially supported by NSF Grant IIS- 1901252. Emmanouil V. Mataaki-GGaragkkoum is grateful for financial support by the Google-Simons Fellowship. Pancretan Association of Amer- ica and Simons Collaboration on Algorithms and Geometry. This project was completed while he was a visiting research fellow at the Simons Institute for the Theory of Computing. Addition- ally, he would like to acknowledge the following series of NSF-CCF grants under the numbers 1763970/21077 001000711111311 155/18 14873.
10

---

References
[1] P. Zhang, Zhang, and S. Sra. Minimax in geodesic metric spaces: Sion's theorem and algorithms. ArXiv Preprint: 2202.06950, 2022. 1, 2, 3, 5, 6, 7, 9, 10, 20, 25, 29, 32
[2] N. Boumal and P-A. Absil. RTRMC: A Riemannian trust-region method for low-rank matrix
completion. In NIPS, pages 406-414, 2011. 1,22
[3] J. Sun, Q. Qu, and J. Wright. Complete dictionary recovery over the sphere I: Overview and the geometric picture. IEEE Transactions on Information Theory, 63(2):853-88) -844, 2016. 1, 22
[4] J. Sun, Q. Qu, and J. Wright. Complete dictionary recovery the sphere II: Recovery by Riemannian trust-region method. IEEE Transactions on Information Theory, 63(2):885-914
2016. 1,
[5] L. Huang, X. Liu, B. Lang, A. Yu, Y. Wang, and B. Li. Orthogonal weight normalization: solution to optimization over multiple dependent stiefel manifolds in deep neural networks. In AAAI, pages 3271-3278, 2018. 1, 22
[6] G. Raskutti and Mukherjee. The information geometry of mirror descent. IEEE Transactions Information Theory, 61(3):155111457, 2015.
[7] A. Giannou, E. V. VatakissGGaargkkouni and P. Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT,
pages 2147-2148, PMLR, 2021.
[8] A. Giannou, E. Vlatakis- SaaaaiiiGaarakoouniis and P. Mertikopoulos. On the rate of convergence of regularized learning in games: From bandits and uncertainty to optimism and beyond. In NeurIPS, pages 22655- 222666. 2021.
[9] K. Antonakopoulos, E. V. Belmega, and P. Mertikopoulos. Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach. In ICLR, 2020. URL https:// openreview bvenreview.net/forume
[10] E. V. VaaakkssGKaargkouuii L. Flokas, T. Lianeas, P. Mertikopoulos, and G. Piliouras. No- regret learning and mixed Nash equilibria: They do not mix, In NeurlPS, pages 1380-1391, 2020.
[11] M. Fornasier, H. Rauhut, and R. Ward. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM Journal Optimization, 21(4):161-11600 2011.
[12] E. J. Candes, M. B. Wakin, and S. P. Boyd. Enhancing sparsity by reweighted & minimization. Journal of Fourier Analysis and Applications, 14(5):877-905, 2008
[13] A. Han, B. Mishra, P. K. Jawanpuria, and J. Gao. On Riemannian optimization over positive definite matrices with the Bures- Wasserstein geometry. In NeurIPS, pages
2021.
[14] I. Goodfellow, J. Abuget-Abadii, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. In NIPS, pages 2672-2680, 2014. 1
[15] J. Mei, Y. Gao, B. Dai, C. Szepesvari, and D. Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In ICML, pages
PMLR, 2021.
[16] S. Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels. Les équations aux dérivées partielles, 17:87-89, 1963.
[17] B. T. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 3(4):643-653, 1963.
[18] R. Ge, F. Huang, Jin, and Y. Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In COLT, pages 797-842. PMLR, 2015. 1
[19] A. Anandkumar and R. Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. COLT, pages 81 102. PMLR, 2016.
[20] S. Sra and R. Hosseini. Geometric optimization in machine learning. In Algorithmic Advances in Riemannian Geometry and Applications, pages 73-91. Springer, 2016.
[21] C. Jin, R. Ge, Netrapalli, M. Kakade, and M. Jordan. How to escape saddle points efficiently. In ICML, pages 1724-1732. PMLR, 2017.
[22] R. Ge, C. Jin, and Zheng. No spurious local minima in nonconvex low rank problems: unified geometric analysis. In ICML, pages 1233-1242, PMLR, 2017.
11

---

[23] S. S. Du, C. Jin, J. D. Lee, M. I. Jordan, B. Póczos, and A. Singh. Gradient descent can take exponential time escape saddle points. In NIPS, pages 1067-1077, 2017.
[24] S. Reddi, M. Zaheer, S. Sra, Poczos, F. Bach, R. Salakhutdinov, and A. Smola. A generic approach for escaping saddle points. In AISTATS, pages 1233-1242. PMLR, 2018.
[25] C. Criscitiello and N. Boumal. Efficiently escaping saddle points on manifolds. In NeurIPS, pages 5987-5997, 2019. 20
[26] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68
12):1-29, 2021.
[27] S. Sra and R. Hosseini. Conic geometric optimization the manifold of positive definite matrices. SIAM Journal on Optimization, 25(1):713-739 2015.
[28] R. Hosseini and S. Sra. Matrix manifold optimization for Gaussian mixtures. In NIPS, pages 910-918, 2015. 1
[29] S. Bonnabel. Stochastic gradient descent Riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217-2222, 2013. 20
[30] R. Tron, B. Afsari, and R. Vidal. Riemannian consensus for manifolds with bounded curvature. IEEE Transactions on Automatic Control, 58(4):921-934 2012.
[31] A. Wiesel. Geodesic convexity and covariance estimation. IEEE Transactions on Signal
Processing, 60(12)6182-611 2012.
[32] A. Kumar, P. Sattigeri, and P. T. Fletcher. Semi-supervised learning with GANs: Manifold invariance with improved inference. In NIPS, pages 5540-5550, 2017. 1
[33] N. Chen, A. Klushyn, R. Kurle, X. Jiang, J. Bayer, and P. Smagt. Metrics for deep generative models. In AISTATS, pages 1540-1555 15500 PMLR, 2018.
[34] T. Lin, C. Fan, N. Ho, M. Cuturi, and M. I. Jordan. Projection robust Wasserstein distance and Riemannian optimization. In NeurIPS, pages 9383-9397, 2020. 1,
[35] P. Mertikopoulos and W. H. Sandholm. Riemannian game dynamics. Journal of Economic Theory, 177:315-364, 2018.
[36] I. M. Bomze, P. Mertikopoulos, W. Schachinger, and M. Staudigl. Hessian barrier algorithms for linearly constrained optimization problems. SIAM Journal on Optimization, 290222100--
2127, 2019.
[37] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter. GANs trained by two time-scale update rule converge to local nash equilibrium. In NIPS, pages 6629 6629-6640, 2017.
[38] C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In NIPS, pages 2256-9266, 2018.
[39] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel. The mechanics of N-player differentiable games. In ICML,, pages 354-363. PMLR, 2018.
[40] P. Mertikopoulos, B. Lecouat, H. Zenati, C-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-pond poiit problems: Going the extra(-gradien) mile. In ICLR, 2019. URL htt.htttss//ppeeeee///
n (ttt///ooummiidBBg1i) C9KQ.
[41] C. Jin, P. Netrapalli, and M. I. Jordan. What is local optimality in minimax optimization? In ICML, pages 4880-4889, PMLR, 2020. I
[42] K. K. Thekumprampil, P. Jain, P. Netrapalli, and S. Oh. Efficient algorithms for smooth minimax optimization. In NeurIPS, pages 12680-12691, 2019.
[43] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving class of non- convex min-max games using iterative first order methods. In NeurlPS, pages 14934 14942, 2019.
[44] S. Lu, I. Tsaknakis, M. Hong, and Y. Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. IEEE Transactions Signal Processing, 68:3676-3691, 2020.
12

---

[45] W. Azizian, I. Mitliagkas. S. Lacoste-Jullis and G. Gidel. A tight and unified analysis of gradient-basee methods for a whole spectrum of differentiable games. In AISTATS, pages 2863-2873. PMLR, 2020.
[46] J. Diakonikolas. Halpern iteration for near-optimal and parameter-free free monotone inclusion and strong solutions to variational inequalities. In COLT, pages 1428-1451. PMLR, 2020.
[47] N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-coneee saddle point problems. In COLT, pages 1758-1784, PMLR, 2020.
[48] T. Lin, C. Jin, and M. I. Jordan. Near-optimal algorithms for minimax optimization. In COLT, pages 2738-2779. PMLR, 2020. 1
[49] T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for noncomvex-concat minimax problems. In ICML., pages 6083-6093. PMLR, 2020.
[50] M. Liu, H. Rafique, Q. Lin, and T. Yang. First-order convergence theory for weakly-convex- weakly-concave min-max problems. Journal of Machine Learning Research, 1-34,, 2021.
[51] D. M. Ostrovskii, A. Lowy, and M. Razaviyayn. Efficient search of first-order Nash equilibria in nonconvex-concan smooth min-max problems. SIAM Journal on Optimization, 31(4): 2508-255 2538, 2021.
[52] W. Kong and R. D. C. Monteiro. An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. SIAM Journal on Optimization, (1(4225558-2 --8525555.8 2021.
[53] C. Daskalakis and I. Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In ITCS, 2019.
[54] L. Adolphs, Daneshmand, A. Lucchi, and T. Hofmann. Local saddle point optimization: curvature exploitation approach. In AISTATS, pages 486-495. PMLR, 2019.
[55] T. Liang and J. Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In AISTATS, pages 907-915, PMLR, 2019. 8
[56] G. Gidel, R. A. Hemmat, M. Pezeshki, R. Le Priol, G. Huang, Lacoste-Julien, and
I. Mitliagkas, Negative momentum for improved game dynamics. In AISTATS, pages 1802- 1811, PMLR, 2019.
[57] E. Mazumdar, L. Ratiff, and S. S. Sastry, On gradient- based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
[58] M. Liu, Y. Mroueh, J. Ross, W. Zhang, X. Cui, P. Das, and T. Yang. Towards better under- standing of adaptive gradient algorithms in generative adversarial nets. In ICLR, 2020. URL
net/ ftrumoormmm// idd=SxxII00mtat
[59] A. Mokhtari, A. Ozdaglar, and S. Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTAYS, pages 1497-1507. PMLR, 2020.
[60] E. Y. Hamedani and N. S. Aybat. A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM Journal Optimization, 31(():1229-133) 1329, 2021.
[61] J. Abernethy, K. A. Lai, and A. Wibisono. Last-iterate convergence rates for min-max optimization: Convergence of Hamiltonian gradient descent and consensus optimization. In ALT, pages 3-47. PMLR, 2021.
[62] Cai, A. Oikonomou, and W. Zheng. Tight last-iterate convergence of the extragradient method for constrained monotone variational inequalities. ArXiv Preprint: 2204.09228, 2022.
2, 10
[63] E. V. Vlatakis- Saaakis-Gkarakkounnis. L. Flokas, and G. Piliouras. Poincaré recurrence, cycles and spurious equilibria in dradient- In NeurlPS, pages 10450-10461, 2019. 2
for non-convex non-concave zero-sum games.
[64] E. V. VaaakissGGaarakkouniis I.. Flokas, and Piliouras. Solving min-max optimization with
hidden structure via gradient descent ascent. In NeurIPS, pages 2373-2386, 2021. 2
13

---

[65] J. Fearnley, P. W. Goldberg, A. Hollender, and R. Savani. The complexity of gradient descent:
CLS PPADD PLS. In STOC, pages 46-59, 2021.
[66] L. E. J. Brouwer. Über abbildung von mannigfaltigkeiten. Mathematische Annalen, 71(1):
97-115, 1911. 2
[67] S. Kakutani. A generalization of Brouwer's 's fixed point theorem. Duke Mathematical Journal, 8(3):457-45 1941. 2
[68] B. Knaster, C. Kuratowski, and S. Mazurkiewicz. Ein beweis des fixpunktsatzes für dimensionale simplexe. Fundamenta Mathematicae, 14(1):132-137, 1929.
[69] M. Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176, 1958.
2, 5, 20
[70] J. V. Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100(1):295-322)
1928. 2
[71] E. D. Helly. Über mengen konvexer körper mit gemeinschaftliche punkte. Jahresberichi der Deutschen Mathematiker- Vertteeirrrrriinnnn 32: 52:175-176, 1923.
[72] S. Ivanov. On Helly's theorem in geodesic spaces. Electronic Research Announcements, 21: 109, 2014. 2
[73] H. Komiya. Elementary proof for Sion's minimax theorem. Kodai Mathematical Journal, 11 (1):5-7, 1988. 2, 20
[74] A. Kristály. Nash-type equilibria on Riemannian manifolds: A variational approach. Journal Mathématiques Pures et Appliquées, 101(5):660-66 688, 2014.
[75] S. Park. Riemannian manifolds are KKM spaces. Advances the Theory of Nonlinear Analysis and its Application, 3(2):64-73, 2019. 2, 20
[76] J. Lee, G. Kim, M. Olfat, M. Hasegawa-Johnson, and C. D. Yoo. Fast and efficient MMD-based fair PCA via optimization over Stiefel manifold. In AAAI, pages 7363-7371, 2022. 2
[77] F. Huang, S. Gao, and H. Huang. Gradient descent ascent for min problems on Riemannian
manifolds. ArXiv Preprint: 2010.06097, 2020. 2, 20
[78] Han, Mishra, P. Jawanpuria, Kumar, and J. Gao. Riemannian Hamiltonian methods
for min-max optimization manifolds. ArXiv Preprint: 2204. 11488, 2022. 2, 20
[79] G. Kotsalis, G. Lan, and T. Li. Simple and optimal methods for stochastic variational inequal- ities, I: operator extrapolation. SIAM Journal on Optimization, 32(3):2041227733 2022.
8
[80] J. Cheeger and D. G. Ebin. Comparison Theorems in Riemannian Geometry, volume 9. North-Holland Amsterdam, 1975.
[81] Y. Burago, M. Gromov, and G. Perel' man. A. D. Alexandrov spaces with curvature bounded below. Russian Mathematical Surveys, 47(2):1, 1992. 4
[82] F. Alimisis, A. Orvieto, G. Bécigneul, and Lucchi. A continuous- timm perspective for modeling acceleration in Riemannian optimization. In AISTATS, pages 1297-1307. PMLR, 2020. 23
[83] H. Zhang and S. Sra. First-order methods for geodesically convex optimization. In COLT, pages 1617 6177-1638. PMLR, 2016. 4, 5, 19, 23
[84] J. Zhang, M. Hong, and S. Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, pages 1-35, 2021. 7
[85] A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[86] A. Fallah, A. Ozdaglar, and S. Pattathil. An optimal multistage stochastic gradient method for minimax problems. In CDC, pages 3573-3579. IEEE, 2020. 8
[87] N. Boumal, B. Mishra, P-A. Absil, and R. Sepulchre. Manopt, a Matlab toolbox for op- timization manifolds. Journal of Machine Learning Research, 15()):1455-1459, 2014.
[88] Candès, X. Li, Ma, and J. Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
14

---

[89] M. Harandi, M. Salzmann, and R. Hartley. Dimensionality reduction on SPD manifolds: The aware methods. IEEE Transactions on Pattern Analysis and Machine emergence of geometry -wwar Intelligence, 40(1):48 62, 2017. 9
[90] C. Criscitiello and N. Boumal. An accelerated first-order method for non-convex optimization on manifolds. Foundations of Computational Mathematics, pages 1-77, 2022.
[91] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015. URL https://openrevi httprrewiwwweeeeeeeeeeeeeeeeeeee met/forunt i id=8gmddujyyy1 10
[92] YazIeı, C-S. Foo, S. Winkler, K-H. Yap. Piliouras, and V. Chandrasekhar, The unusual effectiiennes of averaging in GAN training. In ICLR, 2019. URL https://openrevieer 10
[93] Burago, I. D. Burago, Y. Burago, S. Ivanov, V. Ivanov, and S. Ivanov. Course in Metric Geometry, volume 33. American Mathematical Soc., 2001. 19,
[94] J. Lee. Introduction to Smooth Manifolds, volume 218. Springer Science & Business Media, 2012. 19
[95] P-A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms Matrix Manifolds. Princeton University Press, 2009. 19, 20
[96] Boumal, P-A. Absil, and C. Cartis. Global rates of convergence for nonconvex optimization
manifolds. IMA Journal of Numerical Analysis, 39(1):1-33, 2019. 19
[97] H. Kasai and B. Mishra. Inexact trust-region algorithms on Riemannian manifolds. In NeurIPS, pages 4249-4260, 4260,, 2018. 19
[98] J. Hu, A. Milzarek, Z. Wen, and Y. Yuan. Adaptive quadratically regularized Newton method for Riemannian optimization. SIAM Journal on Matrix Analysis and Applications, 39(3): 1181-1207, 2018.
[99] J. Hu, B. Jiang, L.. Lin, Z. Wen, and Y. Yuan. Structured quasi-Newton methods for optimization with orthogonality constraints. SIAM Journal on Scientific Computing, 41(4): 2019. 19
[100] Z. Wen and W. Yin. A feasible method for optimization with orthogonality constraints. Mathematical Programming, 142(1-2):397-434, 2013, 19
[101] B. Gao, X. Liu, X. Chen, and Y. Yuan. new first-order algorithmic framework for optimiza- tion problems with orthogonality constraints. SIAM Journal on Optimization, 28(1):302-333 2018.
[102] H. Liu, A. M-C. So, and W. Wu. Quadratic optimization with orthogonality constraint: explicit lojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods. Mathematical Programming, 178(1-2):11--66) 2019. 19
[103] J. Zhang, S. Ma, and S. Zhang. Primal-dual optimization algorithms over Riemannian mani- folds: An iteration complexity analysis. Mathematical Programming, 184(1):445-490, 2020. 19
[104] P-A. Absil and S. Hosseini. A collection of nonsmooth Riemannian optimization problems. In
Nonsmooth Optimization and Its Applications, pages 1-15. Springer, 2019. 19
[105] O. P. Ferreira and P. R. Oliveira. Subgradient algorithm on Riemannian manifolds. Journal of Optimization Theory and Applications, 97(1):93-104, 1998. 19
[106] G. C. Bento, O. P. Ferreira, and J. G. Melo. Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds. Journal of Optimization Theory and Applications, 173(2):548-56) 2017. 19, 20
[107] O. P. Ferreira and P. R. Oliveira. Proximal point algorithm on Riemannian manifolds. Opti- mization, 51(2):557-270, 2002. 20
[108] S. Chen, S. Ma, A. M-C. So, and T. Zhang. Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM Journal on Optimization, 30(1):210-25) 239, 2020. 20
[109] X. Li, S. Chen, Z. Deng, Q Qu, 7. Zhu, and A. Man-Cho So. Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM Journal on Optimization, 1605):660--1634 2021. 20
15

---

[110] H. Zhang, S. J. Reddi, and S. Sra. Riemannian SVRG: Fast stochastic optimization on Riemannian manifolds. In NeurIPS, pages 4592-4600, 2016. 20
[111] Tripuraneni, N. Flammarion, Bach, and M. I. Jordan. Averaging stochastic gradient descent on Riemannian manifolds. In COLT, pages 650-687, 2018.
[112] G. Becigneul and O-E. Ganea. Riemannian adaptive optimization methods. In ICLR, 2019. URL petttps:/oppereviiee
[113] H. Kasai, P. Jawanpuria, and B. Mishra. Riemannian adaptive stochastic gradient algorithms
matrix manifolds. In JCML, pages 3262-3271, 2019. 20
[114] Y. Sun, N. Flammarion, and M. Fazel. Escaping from saddle points Riemannian manifolds. In NeurlPS, pages 7274-7284, 2019. 20
[115] B. Martinet. Régularisation d' d'inéquations variationnelles par approximations successives. rev.
française informat. Recherche Opérationnelle, 4:154-158, 1970. 20
[116] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-895) 1976. 20
[117] D. Ruppert. Efficient estimations from a slowly convergent Robbins-Monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988. 20
[118] T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-855 1992.
[119] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-169, 2009. 20
[120] H. H. Bauschke and L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces, volume 408. Springer, 2011. 20
[121] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. 20
[122] A. Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004. 20
[123] F. Facchinei and J-S. Pang. Problems. Springer Science & Business Media, 2007. 20
Variational Inequalities and Complementarity
[124] Li, G. López, and Martín-Márquez Monotone vector fields and the proximal point algorithm on Hadamard manifolds. Journal of the London Mathematical Society, 79(3): 063-683, 2009. 20
[125] J. H. Wang, G. López, Martin-Márquez, and C. Li. Monotone and accretive vector fields on Riemannian manifolds. Journal of Optimization Theory and Applications, 146(())691-708,
2010. 20
[126] O. P. Ferreira, L. R. Pérez, and S. Z. Németh. Singularities of monotone vector fields and an
extragradient-type algorithm. Journal of Global Optimization, 31(1):133-151, 2005, 20
[127] A. Ben-Tal, L. EL Ghaoui, and A. Nemirovski. Robust Optimization, volume 28. Princeton University Press, 2009. 20
[128] J. Hu, X. Liu, Z.W. Wen, and Y-X. Yuan. A brief introduction to manifold optimization.
Journal of the Operations Research Society of China, 8(2):199-248, 2020. 20
[129] X. Pennec, P. Fillard, and N. Ayache. Riemannian framework for tensor computing. International Journal of Computer Vision, 66(1):41-66, 2006. 21
[130] P. T. Fletcher and S. Joshi. Riemannian geometry for the statistical analysis of diffusion tensor data. Signal Processing, 87(2):250 262. 2007. 21
[131] Bergmann and Herzog. Intrinsic formulation of KKT conditions and constraint qual- ifications on smooth manifolds. SIAM Journal on Optimization, 29(4):2423-244 2019.
[132] T. Lin, Zheng, Chen, M. Cuturi, and M. Jordan. On projection robust optimal transport: Sample complexity and model misspecification. In AISTATS, pages 262-270. PMLR, 2021. 21
16

---

[133] B. Vandereycken. Low-rank matrix completion by Riemannian optimization. SIAM Journal on Optimization, 23(2):1214-1266 2013. 22
[134] P. Jawanpuria and B. Mishra. A unified framework for structured low-rank matrix learning. In ICMI, pages 2254-2263. PMLR, 2018. 22
[135] M. Bacak. Convex Analysis and Optimization in Hadamard Spaces, volume 22. Walter de Gruyter GmbH & Co KG, 2014. 22
[136] P. Petersen. Riemannian Geometry, volume 171. Springer, 2006. 23
[137] K. L. Chung. On stochastic approximation method. The Annals of Mathematical Statistics, pages 463-483, 1954. 32
17

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], , or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical work that does not have any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Proof detailsa deferred to the supplementary material.
you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyper-parameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
you used crowd- soodd-ouuring or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
18


Reviews:
[{"review_id": "fiyGoS26krL", "reviewer": "Reviewer_rCdg", "summary": "The authors show that a previous algorithm from [1] (Sion’s theorem and algorithms, Zhang et al) achieves linear convergence rate for the last iterate in the (geodesically) strongly convex-strongly concave settings.\n\nThey also prove some guarantees under the assumption of a noisy gradient oracle, though of course a dependence on $1/\\epsilon$ appears, as well as in the non-strongly convex case and non-smooth cases. These guarantees appear to match the best Euclidean guarantees apart from curvature parameters.", "questions": "1. Not sure if it's just me, but the figure in 3.1 is unreadable.\n2. Can you give a reference for where RPCA is defined and used? \n3. It might be appropriate to mention that in curvature -1, the condition number of g-convex functions has to depend on the radius and so sometimes the linear convergence rate is vacuous.\n4. How were difficulties in previous upper bound proof attempts for the linear convergence guarantee overcome? ", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is (1) the detailed description of the performance of Riemannian extragradient in various scenarios. The novel technical accomplishment is the proof of linear convergence rate in the strongly convex, strongly concave setting. The writing and clarity is high quality. It makes another recent result in [1], a  generalization of Sion's min-max theorem to the uniquely geodesic setting, more constructive.\n\nI do take issue with the lack of examples mentioned for interesting Riemannian convex-convave problems. I think the reader has to take this on faith a bit. The main experimental example, robust PCA, needs Riemannian geometry to even formulate it. It would be nice to have a more natural example. \n\nAs one of the main strengths in the paper appears to be a proof which had heretofore eluded the community, it would help to mention what caused problems before and how the new proof overcomes those issues. Because I didn't find much discussion on this I have no way of knowing if the result is believable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fa_FFZG3ILv", "reviewer": "Reviewer_LyY4", "summary": "The paper provides optimal convergence guarantees for the Riemannian corrected extragradient method (proposed in [1]) for geodesically strongly convex-strongly concave min-max optimization problems. A stochastic version of the algorithm is also discussed.", "questions": "My main question is on the applicability of the analysis as described in the previous section.\n\nAlso, I think the second part of Definition 2.2 since you have again convexity instead of concavity.", "limitations": "The authors discuss the limitations of their work. There is no direct societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is very well-written in all its aspects and the technical work seems solid. The analysis answers a conjecture raised in [1], for an algorithm that is a reasonable adaptation of a similar Euclidean algorithm. Experimental results are also presented.\n\nWeaknesses: Some parts of the proofs are hard to follow. Maybe this paper is a bit packed mathematically for the neurips community. My most serious concern is that the set of applications of geodesic strong convexity-strong concavity is exceptionally poor. Namely, the authors mention the problem of robust PCA as an application of their theoretical analysis, but this analysis cannot be applied to this problem because it is only *locally* strongly convex-strongly concave. This can have tremendous difference from *global* strong convexity-strong concavity, because one needs to ensure that an iterate of the algorithm remains in the set that the algorithm satisfies this property. This is usually impossible when the analysis is done for function values (Theorem 3.3) and for stochastic algorithms in general (Theorems 3.2,3.3). Even when the analysis is done for distances like in Theorem 3.1, one needs to ensure that $d_M(x_t,x^*) \\leq d_M(x_0,x^*)$ and $d_N(y_t,y^*) \\leq d_N(y_0,y^*)$ for all $t$. This is not clear to me because the contraction is only for the sum $d^2_M(x_t,x^*)+d^2_N(y_t,y^*)$. Thus, the paper is left without a concrete application of the theoretical analysis and this is the only reason I give a rejection score, which I would be happy to raise either if the authors can fix at least the analysis of their deterministic algorithm to cover also *local* strong convexity-strong concavity or can if they suggest a different important optimization problem that is actually *globally* strongly convex-strongly concave.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dEWinZ-Xn2", "reviewer": "Reviewer_3XLa", "summary": "The authors explore the complexity of min-max problems defined on Riemannian manifolds. They prove, among others, linear convergence of the last iterate of RCEG, a result that was unknown in the literature, and explore stochastic and nonsmooth variants.", "questions": "- Which nonconvex constraints do appear in GANs? (first paragraph of the introduction)\n- on p. 2, line 77-78, \"for the non-convex non-concave setting, deriving ...for the convex case\". What is convex here?\n- please add the definition of the acronyms in the table in Section 1.1\n- how do you define the diameter of a manifold, in Prop. 2.1? Are you restricting here youselves to a closed manifold?)\n- Def. 2.2: shouldn't the second inequality be in the opposite direction?\n- I am quite concerned about the unicity of geodesics assumption. In particular, this seems to rule out many manifolds of interest, including those of positive curvature (the sphere, the Stiefel manifold, the orthogonal group). Am I right to understand that this assumption is violated by your experimental section (see eq. 5)?\n- How does this unicity assumption interact with your assumption on the sectional curvature, in regard of the previous comment?\n- In Thm. 3.1, do kappa_min and kappa_max refer to the curvature of M or of N?\n", "limitations": "I do not expect this work to have any societal impact.", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper addresses an interesting topic. It is overall well-written, though there remains typos and inaccuracies at some places in the presentation. I am not very comfortable with the content and presentation of the results. Most of the paper is devoted to a presentation of the underlying assumptions of the convergence analysis, while those are already extensively presented in [1].  On the other hand, very little intuition is given to the new findings compared with [1] (understanding why the convergence guarantees for RCEG of this paper are stronger than in [1] would require to read in detail the appendix). \nGiven the fact that most of pages 1-2, 4-5 are already in [1], I would advise the authors to significantly shrink those sections, refering where applicable to [1], and give much more intuition on their main contributions:\n- how do the authors achieve stronger guarantees than in [1] for RCEG?\n- what are the changes needed to extend the proof to the sochastic setting?\n- what are the changes needed to consider the nonsmooth setting?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V2bCMbVboHi", "reviewer": "Reviewer_KFH3", "summary": "This paper provides an extensive analysis of the Riemannian counterparts of Euclidean optimal first-order methods adapted to the manifold-constrained setting and  proves that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at a linear rate in the geodesically strongly- convex-concave case and extents it to the stochastic or non-smooth case.Some experiments have verified theoretical results.\n\n", "questions": "1. The first figure in Section 3 is not very clear and lacks labels;\n2. In the experimental section, It would be good if there were more comparison algorithms.", "limitations": "1. The first figure in Section 3 is not very clear and lacks labels;\n2. In the experimental section, It would be good if there were more comparison algorithms.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think the paper is solid and novel enough. The authors prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at a linear rate in the geodesically strongly convex-concave case, matching the Euclidean result. Their results also extend to the stochastic or non-smooth case where RCEG and Riemanian gradient ascent descent (RGDA) achieve near-optimal convergence rates up to factors depending on curvature of the manifold.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "4YBZgNfbnGk", "reviewer": "Reviewer_Zici", "summary": "The paper analyzes first-order methods for min-max optimization on Riemannian manifolds. Problems of this form arise in a variety of settings, including optimal transport and adversarial learning. The main focus of the paper is on investigating the existence of a fundamental \"performance gap\" between Riemannian and Euclidean approaches for min-max optimization. The authors show that a Riemannian method (RCEG) matches the performance of its Euclidean counterpart in the geodesically strongly convex-concave case.", "questions": "See limitations.", "limitations": "1. Since the paper analyzes potential performance differences of Euclidean and Riemannian methods, it would have been good to compare against Euclidean methods in the experiments. \n2. The theory is limited to the geodesically strongly convex-concave case. How restrictive is this? E.g., among the examples listed in the introductions, to which does the theory apply? Can you comment on any challenges in extending the present theory to less restrictive cases, which are understood in the Euclidean setting?\n3. In sec. 4, l. 300, what does \"appears to be locally geodesically strongly convex-concave\" mean? Can this be shown?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strength*\nThe paper addresses an important problem, which arises frequently in machine learning applications and is therefore very timely. The paper carefully reviews the existing literature and does a good job of explaining its contribution, especially with respect to Zhang et al. (2022), on which it directly builds.\n\n*Weaknesses*\nSee limitations below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept