1 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 in 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 a range of other applications such as 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 heuristics.

Thus, a 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 (ML) community has focused on understanding the geometric properties of commonly used constraints and how they affect optimization; [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 a 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 ML 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]–[62] for computing min-max solutions in convex-concave settings. Nonetheless, the analysis of the iteration complexity in the general non-convex non-concave setting is 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 \(\mathcal{M}, \mathcal{N}\) and a function \(f: \mathcal{M}\times \mathcal{N}\to \mathbb{R}\), the Riemannian min-max optimization (RMMO) problem becomes \[\min_{x \in \mathcal{M}} \max_{y \in \mathcal{N}} f(x, y).\] The change of geometry from Euclidean to Riemannian poses several difficulties. Indeed, a fundamental stumbling block has been that this problem may not even have theoretically meaningful solutions. In contrast with minimization where an optimal solution in a 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 \(\mathcal{X}\) and \(\mathcal{Y}\),  [69] generalized the celebrated theorem [70] and guaranteed that a solution \((x^\star,y^\star)\) with the following property exists \[\min_{x\in\mathcal{X}} f(x,y^\star) = f(x^\star,y^\star) = \max_{y\in\mathcal{Y}} f(x^\star,y).\] However, at the core of the proof of this result is an ingenuous application of Helly’s lemma [71] for the sublevel sets of \(f\), and, until the work of [72], it has been unclear how to formulate an analogous lemma for the Riemannian geometry. As a result, until recently have extensions of the min-max theorem been established, and only for restricted manifold families [73]–[75].

[1] was the first to establish a min-max theorem for a flurry of Riemannian manifolds equipped with unique geodesics. Notice that this family is not a mathematical artifact since it 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 \(x_1,x_2 \in \mathcal{X}\), their connecting geodesic is the unique shortest path contained in \(\mathcal{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-Gradient (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 \(\delta_t=\|x_t-x^*\|^2\) is decreasing over time. To achieve this, typically the proof correlates \(\delta_t\) and \(\delta_{t-1}\) via a “square expansion,” namely: \[\label{eq:square-expansion} \underbrace{\|x_{t-1}-x^*\|^2}_{\alpha^2} = \underbrace{\|x_{t}-x^*\|^2}_{\beta^2} + \underbrace{\|x_{t-1}-x_{t}\|^2}_{\gamma^2}-\underbrace{2\langle x_{t}-x^*,x_{t-1}-x_{t}\rangle}_{2\beta\gamma\cos(\hat{A})}.\tag{1}\] 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 \(x_t\), \(x_{t-1}\) and \(x^*\) form a triangle; indeed, it is the generalization of the Pythagorean theorem, known also as the law of cosines, for the induced triangle \({(ABC)}:=\{(x_{t},x_{t-1},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_\mathcal{M}^2(x_{t}, x^* ) - d_\mathcal{M}^2(x_{t-1}, x^* )\) generally cannot be given in a closed form. The manifold’s curvature controls how close these paths are to forming a Euclidean triangle. In fact, the phenomenon of distance distortion, as it is typically called, was hypothesised by [1] 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. [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 [78] for Riemannian Hamiltonian Method (RHM), matches the rate of second-order methods in the Euclidean case. Although theoretically faster in 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, [1] leveraged the standard averaging output trick in EG to derive a sublinear convergence rate of \(O(1/\epsilon)\) for the general geodesically convex-concave Riemannian framework. In addition, they conjectured that the use of a different method could close the exponential gap for the geodesically strongly-convex-strongly-convex 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:

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-constrained 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.

For the definition of the acronyms, Det and Stoc stand for deterministic and stochastic, respectively. GSCSC and GCC stand for geodesically strongly-convex-strongly-concave (cf. Assumption 2 or Assumption 4) and geodesically convex-concave (cf. Assumption 3 or Assumption 5). Here \(\epsilon \in (0, 1)\) is the accuracy, \(L,\ell\) the Lipschitzness of the objective and its gradient, \(\kappa=\ell/\mu\) is the condition number of the function, where \(\mu\) is the strong convexity parameter, \((\tau_0,\underline{\xi}_0, \overline{\xi}_0)\) are curvature parameters (cf. Assumption 1), and \(\sigma^2\) is the variance of a Riemannian gradient estimator.

Our first main contribution is the derivation of a 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 \(d_\mathcal{M}^2(x_t, x^*)\) and \(d_\mathcal{M}^2(x_{t-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 \(d_\mathcal{M}^2(x_t, x^*)\). 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 a proper choice of constant stepsize). More specifically, we use \(d_\mathcal{M}^2(x_t, x^\star) + d_\mathcal{N}^2(y_t, y^\star)\) and \(d_\mathcal{M}^2(x_{t+1}, x^\star) + d_\mathcal{N}^2(y_{t+1}, y^\star)\) to bound a gap function defined by \(f(\hat{x}_t, y^\star) - f(x^\star, \hat{y}_t)\). Since the objective function is geodesically strongly-convex-strongly-concave, we have \(f(\hat{x}_t, y^\star) - f(x^\star, \hat{y}_t)\) is lower bounded by \(\frac{\mu}{2}(d_\mathcal{M}(\hat{x}_t, x^\star)^2 + d_\mathcal{N}(\hat{y}_t, y^\star)^2)\). Then, using the relationship between \((x_t, y_t)\) and \((\hat{x}_t, \hat{y}_t)\), we conclude the desired results in Theorem 2. Notably, our approach is not affected by the nonlinear geometry of the manifold.

Secondly, we endeavor to give a systematic analysis of aspects of the objective function, including its smoothness, its convexity and oracle access. As we shall see, similar to the Euclidean case, better finite-time convergence guarantees are connected with a 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 is to carefully select the step size such that the noise of the gradient estimator will not affect the final convergence rate significantly. As a highlight, such technique has been used for analyzing stochastic RCEG in the Euclidean setting [79] and our analysis can be seen as the extension to 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 of Riemannian metrics, 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, we focus on some of key concepts that we need from Riemannian geometry, deferring a fuller presentation, including motivating examples and further discussion of related work, to Appendix 6-8.

2.0.0.1 Riemannian geometry.

An \(n\)-dimensional manifold \(\mathcal{M}\) is a topological space where any point has a neighborhood that is homeomorphic to the \(n\)-dimensional Euclidean space. For each \(x \in \mathcal{M}\), each tangent vector is tangent to all parametrized curves passing through \(x\) and the tangent space \(T_x \mathcal{M}\) of a manifold \(\mathcal{M}\) at this point is defined as the set of all tangent vectors. A Riemannian manifold \(\mathcal{M}\) is a smooth manifold that is endowed with a smooth (“Riemannian”) metric \(\langle \cdot, \cdot\rangle_x\) on the tangent space \(T_x \mathcal{M}\) for each point \(x \in \mathcal{M}\). The inner metric induces a norm \(\|\cdot\|_x\) on the tangent spaces.

A geodesic can be seen as the generalization of an Euclidean linear segment and is modeled as a smooth curve (map), \(\gamma: [0, 1] \mapsto \mathcal{M}\), which is locally a distance minimizer. Additionally, because of the non-flatness of a manifold a 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 \(\kappa_\mathcal{M}\) thanks to Toponogov’s theorem [80], [81].

A constructive consequence of this definition are the trigonometric comparison inequalities (TCIs) that will be essential in our proofs; see [82] and [83] for detailed derivations. Assuming bounded sectional curvature, TCIs provide a tool for bounding Riemannian “inner products” that are more troublesome than classical Euclidean inner products.

The following proposition summarizes the TCIs that we will need; note that if \(\kappa_{\min} = \kappa_{\max} = 0\) (i.e., Euclidean spaces), then the proposition reduces to the law of cosines.

Also, in contrast to the Euclidean case, \(x\) and \(v=\textrm{grad}_x f(x)\) do not lie in the same space, since \(\mathcal{M}\) and \(T_x \mathcal{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 \(x \in \mathcal{M}\) is a mapping from the tangent space \(T_x \mathcal{M}\) to \(\mathcal{M}\). In particular, \(y := \textrm{Exp}_x(v) \in \mathcal{M}\) is defined such that there exists a geodesic \(\gamma: [0, 1] \mapsto \mathcal{M}\) satisfying \(\gamma(0) = x\), \(\gamma(1) = y\) and \(\gamma'(0) = v\). The inverse map exists since the manifold has a unique geodesic between any two points, which we denote as \(\textrm{Exp}_x^{-1}: \mathcal{M}\mapsto T_x \mathcal{M}\). Accordingly, we have \(d_\mathcal{M}(x, y) = \|\textrm{Exp}_x^{-1}(y)\|_x\) is the Riemannian distance induced by the exponential map.

Finally, in contrast again to Euclidean spaces, we cannot compare the tangent vectors at different points \(x, y \in \mathcal{M}\) since these vectors lie in different tangent spaces. To resolve this issue, it suffices to define a transport mapping that moves a tangent vector along the geodesics and also preserves the length and Riemannian metric \(\langle \cdot, \cdot\rangle_x\); indeed, we can define a parallel transport \(\Gamma_x^y: T_x \mathcal{M}\mapsto T_y \mathcal{M}\) such that the inner product between any \(u, v \in T_x \mathcal{M}\) is preserved; i.e., \(\langle u, v\rangle_x = \langle \Gamma_x^y(u), \Gamma_x^y(v)\rangle_y\).

2.0.0.2 Riemannian min-max optimization and function classes.

We let \(\mathcal{M}\) and \(\mathcal{N}\) be Riemannian manifolds with unique geodesic and bounded sectional curvature and assume that the function \(f: \mathcal{M}\times \mathcal{N}\mapsto \mathbb{R}\) is defined on the product of these manifolds. The regularity conditions that we impose on the function \(f\) are as follows.

Following standard conventions in Riemannian optimization [1], [82], [83], we make the following assumptions on the manifolds and objective functions:¹

Under these conditions, [1] proved an analog of Sion’s minimax theorem [69] in geodesic metric spaces. Formally, we have \[\max_{y \in \mathcal{N}} \min_{x \in \mathcal{M}} f(x, y) = \min_{x \in \mathcal{M}} \max_{y \in \mathcal{N}} f(x, y),\] which guarantees that there exists at least one global saddle point \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) such that \(\min_{x \in \mathcal{M}} f(x, y^\star) = f(x^\star, y^\star) = \max_{y \in \mathcal{Y}} f(x^\star, y)\). Note that the unicity of geodesics assumption is algorithm-independent and is imposed for guaranteeing that a saddle-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, \(\kappa_{\max} = 0\)) has a unique geodesic between any two points. This also becomes a common regularity condition in Riemannian optimization [82], [83]. For any point \((\hat{\mathbf{x}}, \hat{\mathbf{y}}) \in \mathcal{M}\times \mathcal{N}\), the duality gap \(f(\hat{x}, y^\star) - f(x^\star, \hat{y})\) thus gives an optimality criterion.

In the setting where \(f\) is geodesically strongly-convex-strongly-concave with \(\mu > 0\), it is not difficult to verify the uniqueness of a global saddle point \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\). Then, we can consider the distance gap \((d(\hat{x}, x^\star))^2 + (d(\hat{y}, y^\star))^2\) as an optimality criterion for any point \((\hat{\mathbf{x}}, \hat{\mathbf{y}}) \in \mathcal{M}\times \mathcal{N}\).

Given the above definitions, we can ask whether it is possible to find an \(\epsilon\)-saddle point efficiently or not. In this context, [1] have answered this question in the affirmative for the setting where \(f\) is geodesically \(\ell\)-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 conjecture that RCEG does not guarantee convergence at a linear rate in terms of last iterates when \(f\) is geodesically \(\ell\)-smooth and geodesically strongly-convex-strongly-concave, due to the existence of distance distortion; see [1]. Surprisingly, we show in Section 3 that RCEG with constant stepsize can achieve last-iterate convergence at a linear rate. Moreover, we establish the optimal convergence rates of stochastic RCEG for certain choices of stepsize for both geodesically convex-concave and geodesically strongly-convex-strongly-concave settings.

3 Riemannian Corrected Extragradient Method↩︎

In this section, we revisit the scheme of Riemannian corrected extragradient (RCEG) method proposed by [1] and extend it to a stochastic algorithm that we refer to as stochastic RCEG. We present our main results on an optimal last-iterate convergence guarantee for the geodesically strongly-convex-strongly-concave 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] and resolves an open problem posted in [1].

3.1 Algorithmic scheme↩︎

Table 1: RCEG

The recently proposed Riemannian corrected extragradient (RCEG) method [1] is a 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 a basic version of EG as follows, where \(\mathcal{M}\) and \(\mathcal{N}\) are classically restricted to be convex constraint sets in Euclidean spaces: \[\label{def:EG} \begin{array}{rclcrcl} \hat{x}_t & \leftarrow & \textrm{proj}_\mathcal{M}(x_t - \eta \cdot \nabla_x f(x_t, y_t)), & & \hat{y}_t & \leftarrow & \textrm{proj}_\mathcal{N}(y_t + \eta \cdot \nabla_y f(x_t, y_t)), \\ x_{t+1} & \leftarrow & \textrm{proj}_\mathcal{M}(x_t - \eta \cdot \nabla_x f(\hat{x}_t, \hat{y}_t)), & & y_{t+1} & \leftarrow & \textrm{proj}_\mathcal{N}(y_t + \eta \cdot \nabla_y f(\hat{x}_t, \hat{y}_t)). \end{array}\tag{2}\]

Turning to the setting where \(\mathcal{M}\) and \(\mathcal{N}\) are Riemannian manifolds, the rather straightforward way to do the generalization is to replace the projection operator by the corresponding 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: \[\hat{x}_t \leftarrow \textrm{Exp}_{x_t}(-\eta \cdot \textrm{grad}_x f(x_t, y_t)), \quad \hat{y}_t \leftarrow \textrm{Exp}_{y_t}(\eta \cdot \textrm{grad}_y f(x_t, y_t)).\] However, we encounter some issues for the second line of Eq. 2 : The aforementioned approach leads to some problematic updates, \(x_{t+1} \leftarrow \textrm{Exp}_{x_t}(-\eta \cdot \textrm{grad}_x f(\hat{x}_t, \hat{y}_t))\) and \(y_{t+1} \leftarrow \textrm{Exp}_{y_t}(\eta \cdot \textrm{grad}_y f(\hat{x}_t, \hat{y}_t))\); indeed, the exponential maps \(\textrm{Exp}_{x_t}(\cdot)\) and \(\textrm{Exp}_{y_t}(\cdot)\) are defined from \(T_{x_t} \mathcal{M}\) to \(\mathcal{M}\) and from \(T_{y_t} \mathcal{N}\) to \(\mathcal{N}\) respectively. However, we have \(-\textrm{grad}_x f(\hat{x}_t, \hat{y}_t) \in T_{\hat{x}_t}\mathcal{M}\) and \(\textrm{grad}_y f(\hat{x}_t, \hat{y}_t) \in T_{\hat{y}_t}\mathcal{N}\). This motivates us to reformulate the second line of Eq. 2 as follows: \[x_{t+1} \leftarrow \textrm{proj}_\mathcal{M}(\hat{x}_t - \eta \cdot \nabla_x f(\hat{x}_t, \hat{y}_t) + (x_t - \hat{x}_t)), \quad y_{t+1} \leftarrow \textrm{proj}_\mathcal{N}(\hat{y}_t + \eta \cdot \nabla_y f(\hat{x}_t, \hat{y}_t) + (y_t - \hat{y}_t)).\] In the general setting of Riemannian manifolds, the terms \(x_t - \hat{x}_t\) and \(y_t - \hat{y}_t\) become \(\textrm{Exp}_{\hat{x}_t}^{-1}(x_t) \in T_{\hat{x}_t} \mathcal{M}\) and \(\textrm{Exp}_{\hat{y}_t}^{-1}(y_t) \in T_{\hat{y}_t} \mathcal{N}\). This observation yields the following updates: \[x_{t+1} \leftarrow \textrm{Exp}_{\hat{x}_t}(-\eta \cdot \textrm{grad}_x f(\hat{x}_t, \hat{y}_t) + \textrm{Exp}_{\hat{x}_t}^{-1}(x_t)), \quad \hat{y}_t \leftarrow \textrm{Exp}_{\hat{y}_t}(\eta \cdot \textrm{grad}_y f(\hat{x}_t, \hat{y}_t) + \textrm{Exp}_{\hat{y}_t}^{-1}(y_t)).\] We summarize the resulting RCEG method in Algorithm 1 and present the stochastic extension with noisy estimators of Riemannian gradients of \(f\) in Algorithm [tbl:alg:SRCEG].

3.2 Main results↩︎

We present our main results on global convergence for Algorithms 1 and [tbl:alg:SRCEG]. To simplify the presentation, we treat separately the following two cases:

Letting \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) be a global saddle point of \(f\) (which exists under either Assumption 2 or 3), we let \(D_0 = (d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2 > 0\) and \(\kappa = \ell/\mu\) for geodesically strongly-convex-strongly-concave setting. For simplicity of presentation, we also define a ratio \(\tau(\cdot, \cdot)\) that measures how non-flatness changes in the spaces: \(\tau([\kappa_{\min}, \kappa_{\max}], c) = \tfrac{\overline{\xi}(\kappa_{\min}, c)}{\underline{\xi}(\kappa_{\max}, c)} \geq 1.\) We summarize our results for Algorithm 1 in the following theorem.

In the scheme of SRECG, we highlight that \((g_x^t, g_y^t)\) and \((\hat{g}_x^t, \hat{g}_y^t)\) are noisy estimators of Riemannian gradients of \(f\) at \((x_t, y_t)\) and \((\hat{x}_t, \hat{y}_t)\). It is necessary to impose the conditions such that these estimators are unbiased and has bounded variance. By abuse of notation, we assume that \[\label{def:noisy-model} \begin{array}{lcl} g_x^t = \textrm{grad}_x f(x_t, y_t) + \xi_x^t, & & g_y^t = \textrm{grad}_y f(x_t, y_t) + \xi_y^t, \\ \hat{g}_x^t = \textrm{grad}_x f(\hat{x}_t, \hat{y}_t) + \hat{\xi}_x^t, & & \hat{g}_y^t = \textrm{grad}_y f(\hat{x}_t, \hat{y}_t) + \hat{\xi}_y^t. \end{array}\tag{3}\] where the noises \((\xi_x^t, \xi_y^t)\) and \((\hat{\xi}_x^t, \hat{\xi}_y^t)\) are independent and satisfy that \[\label{def:noisy-bound} \begin{array}{lclcl} {\mathbb{E}}[\xi_x^t] = 0, & & {\mathbb{E}}[\xi_y^t] = 0, & & {\mathbb{E}}[\|\xi_x^t\|^2 + \|\xi_y^t\|^2] \leq \sigma^2, \\ {\mathbb{E}}[\hat{\xi}_x^t] = 0, & & {\mathbb{E}}[\hat{\xi}_y^t] = 0, & & {\mathbb{E}}[\|\hat{\xi}_x^t\|^2 + \|\hat{\xi}_y^t\|^2] \leq \sigma^2. \end{array}\tag{4}\] We are ready to summarize our results for Algorithm [tbl:alg:SRCEG] in the following theorems.

3.2.0.1 Discussions:

The last-iterate linear convergence rate in terms of Riemannian metrics is only limited to geodesically strongly convex-concave cases but other results, e.g., the average-iterate sublinear 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-concave cases. As such, our setting is not restrictive. Moreover,  [1] showed that the existence of a global saddle point is only guaranteed under the geodesically convex-concave assumption. For geodesically nonconvex-concave or geodesically nonconvex-nonconcave cases, a global saddle point 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 are nonconvex-nonconcave min-max problems in the Euclidean setting can be geodesically convex-concave in the Riemannian setting; see Appendix 7.

4 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 1 and [tbl:alg:SRCEG] with different outputs, i.e., the last iterate \((x_T, y_T)\) versus the time-average iterate \((\bar{x}_T, \bar{y}_T)\) (see the precise definition in Theorem 4). 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 a 2.6 GHz Intel Core i7 and 16GB of memory. Due to space limitations, some additional experimental results are deferred to Appendix 12.

4.0.0.1 Experimental setup.

The problem of RPCA [88], [89] can be formulated as the Riemannian min-max optimization problem with an SPD manifold and a sphere manifold. Formally, we have \[\label{prob:RPCA} \max_{M \in \mathcal{M}_{\textrm{PSD}}^d} \min_{x \in \mathcal{S}^d}\left\{ -x^{\top}Mx - \frac{\alpha}{n}\sum_{i=1}^{n}d(M, M_i)\right\}.\tag{5}\] In this formulation, \(\alpha > 0\) denotes the penalty parameter, \(\{M_i\}_{i \in [n]}\) is a sequence of given data SPD matrices, \(\mathcal{M}_{\textrm{PSD}}^d = \{M \in \mathbb{R}^{d \times d}: M \succ 0, M = M^\top\}\) denotes the SPD manifold, \(\mathcal{S}^d = \{x \in \mathbb{R}^d: \|x\| = 1\}\) denotes the sphere manifold and \(d(\cdot, \cdot): \mathcal{M}_{\textrm{PSD}}^d \times \mathcal{M}_{\textrm{PSD}}^d \mapsto \mathbb{R}\) is the Riemannian distance induced by the exponential map on the SPD manifold \(\mathcal{M}_{\textrm{PSD}}^d\). As demonstrated by [1], the problem of RPCA is nonconvex-nonconcave from a Euclidean perspective but is locally geodesically strongly-convex-strongly-concave and satisfies most of the assumptions that we make in this paper. In particular, the SPD manifold is complete with sectional curvature in \([-\frac{1}{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) [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 an application where both min and max sides are done on Riemannian manifolds.

Following the previous works of [1] and [78], we generate a sequence of data matrices \(M_i\) satisfying that their eigenvalues are in the range of \([0.2, 4.5]\). In our experiment, we fix \(\alpha=1.0\) and also vary the problem dimension \(d \in \{25, 50, 100\}\). The evaluation metric is set as gradient norm. We set \(n=40\) and \(n=200\) in Figure 4 and 5. For RCEG, we set \(\eta = \frac{1}{2\ell}\) where \(\ell > 0\) is selected via grid search. For SRCEG, we set \(\eta_t = \min\{\frac{1}{2\ell}, \frac{a}{t}\}\) where \(\ell, a > 0\) are selected via grid search. Additional results on the effect of stepsize are summarized in Appendix 12.

4.0.0.2 Experimental results.

Figure 4 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. It is clear that the last iterate of RCEG consistently exhibits linear convergence to an optimal solution in all the settings, verifying our theoretical results in Theorem 2. In contrast, the average iterate of RCEG converges much slower than the last iterate of RCEG. The possible reason is that the problem of RPCA is only locally geodesically strongly-convex-strongly-concave and averaging with the iterates generated during early stage will significantly slow down the convergence of RCEG.

Figure 5 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 [tbl:alg:SRCEG] 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 effectiveness and efficiency of SRCEG in practice. It is also worth mentioning that the difference between last-iterate convergence and time-average-iterate 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 on 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 [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 a 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 [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 to examine how one could leverage this machinery in a non-Euclidean but geodesic-metric-friendly framework.

Acknowledgments↩︎

This work was supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764 and by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-2941. The work of Michael I. Jordan is also partially supported by NSF Grant IIS-1901252. Emmanouil V. Vlatakis-Gkaragkounis is grateful for financial support by the Google-Simons Fellowship, Pancretan Association of America 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. Additionally, he would like to acknowledge the following series of NSF-CCF grants under the numbers 1763970/2107187/1563155/1814873.

6 Related Work↩︎

The literature for the geometric properties of Riemannian Manifolds is immense and hence we cannot hope to survey them here; for an appetizer, we refer the reader to [93] and [94] and references therein. On the other hand, as stated, it is not until recently that the long-run non-asymptotic behavior of optimization algorithms in Riemannian manifolds (even the smooth ones) has encountered a lot of interest. For concision, we have deferred here a detailed exposition of the rest of recent results to Appendix 6 of the paper’s supplement. Additionally, in Appendix 7 we also give a bunch of motivating examples which can be solved by Riemannian min-max optimization.

6.0.0.1 Minimization on Riemannian manifolds.

Many application problems can be formulated as the minimization or maximization of a smooth function over Riemannian manifold and has triggered a line of research on the extension of the classical first-order and second-order methods to Riemannian setting with asymptotic convergence to first-order stationary points in general [95]. Recent years have witnessed the renewed interests on nonasymptotic convergence analysis of solution methods. In particular, [96] proved the global sublinear convergence results for Riemannian gradient descent method and Riemannian trust region method, and further demonstrated that the Riemannian trust region method converges to a second-order stationary point in polynomial time; see also similar results in some other works [97]–[99]. We are also aware of recent works on problem-specific methods [100]–[102] and primal-dual methods [103].

Compared to the smooth counterpart, Riemannian nonsmooth optimization is harder and relatively less explored [104]. A few existing works focus on optimizing geodesically convex functions over Riemannian manifold with subgradient methods [83], [105], [106]. In particular, [105] provided the first asymptotic convergence result while [83] and [106] proved an nonasymptotic global convergence rate of \(O(\epsilon^{-2})\) for Riemannian subgradient methods. Further, [107] assumed that the proximal mapping over Riemannian manifold is computationally tractable and proved the global sublinear convergence of Riemannian proximal point method. Focusing on optimization over Stiefel manifold, [108] studied the composite objective function and proposed Riemannian proximal gradient method which only needs to compute the proximal mapping of nonsmooth component function over the tangent space of Stiefel manifold. [109] consider optimizing a weakly convex function over Stiefel manifold and proposed Riemannian subgradient methods that drive a near-optimal stationarity measure below \(\epsilon\) within the number of iterations bounded by \(O(\epsilon^{-4})\).

There are some results on stochastic optimization over Riemannian manifold. In particular, [29] proved the first asymptotic convergence result for Riemannian stochastic gradient descent, which is extended by a line of subsequent works [110]–[113]. If the Riemannian Hessian is not positive definite, some recent works have suggested frameworks to escape saddle points [25], [114].

6.0.0.2 Min-Max optimization in Euclidean spaces.

Focusing on solving specifically min-max problems, the algorithms under euclidean geometry have a very rich history in optimization that goes back at least to the original proximal point algorithms [115], [116] for variational inequality (VI) problems; At a high level, if the objective function is Lipschitz and strictly convex-concave, the simple forward-backward schemes are known to converge – and if combined with a Polyak–Ruppert averaging scheme [117]–[119], they achieve an \(O(1/\epsilon^2)\) complexity² without the caveat of strictness [120]. If, in addition, the objective admits Lipschitz continuous gradients, then the extragradient (EG) algorithm [121] achieves trajectory convergence without strict monotonicity requirements, while the time-average iterate converges at \(O(1/\epsilon)\) steps [122]. Finally, if the problem is strongly convex-concave, forward-backward methods computes an \(\epsilon\)-saddle point at \(O(1/\epsilon)\) steps; and if the operator is also Lipschitz continuous, classical results in operator theory show that simple forward-backward methods suffice to achieve a linear convergence rate [120], [123].

6.0.0.3 Min-Max optimization on Riemannian manifolds.

In the case of nonlinear geometry, the literature has been devoted on two different orthogonal axes: a) the existence of saddle point for min-max objective bi-functions and b) the design of algorithms for the computation of such points. For the existence of saddle point, a long line of recent work tried to generalize the seminal minima theorem for quasi-convex-quasi-concave problems of [69]. The crucial bottleneck of this generalization to Riemannian smooth manifolds had been the application of both Knaster–Kuratowski–Mazurkiewicz (KKM) theorem and Helly’s theorem in non-flat spaces. Before [1], the existence of saddle points had been identified for the special case of Hadamard manifolds [73]–[75], [106].

Similar with the existence results, initially the developed methods referred to the computation of singularities in monotone variational operators typically in hyperbolic Hadamard manifolds with negative curvature [124]. More recently,  [77] proposed a Riemannian gradient descent ascent method (RGDA), yet the analysis is restricted to \(\mathcal{N}\) being a convex subset of the Euclidean space and \(f(x, y)\) being strongly concave in \(y\). It is worth mentioning that for the case Hadamard and generally hyperbolic manifolds, extra-gradient style algorithms have been proposed [125], [126] in the literature, establishing mainly their asymptotic convergence. However it was not until recent [1] that the riemannian correction trick has been analyzed for the case of the extra-gradient algorithm. Bearing in our mind the higher-order methods, [78] has recently proposed the Riemannian Hamiltonian Descent and versions of Newton’s method for for geodesic convex geodesic concave functions. Since in this work, we focus only on first-order methods, we don’t compare with the aforementioned Hamiltonian alternative since it incorporates always the extra computational burden of second-derivatives and hessian over a manifold.

7 Motivating Examples↩︎

We provide some examples of Riemannian min-max optimization to give a sense of their expressivity. Two of the examples are the generic models from the optimization literature [95], [127], [128] and the two others are the formulations of application problems arising from machine learning and data analytics [34], [129], [130].

In addition to these examples, it is worth mentioning that Riemannian min-max optimization problems contain all general min-max optimization problems in Euclidean spaces and all Riemannian minimization or maximization optimization problems. It is also an abstraction of many machine learning problems, e.g,. principle component analysis [2], dictionary learning [3], [4], deep neural networks (DNNs) [5] and low-rank matrix learning [133], [134]; indeed, the problem of principle component analysis resorts to optimization problems on Grassmann manifolds for example.

8 Metric Geometry↩︎

To generalize the first-order methods in Euclidean setting, we introduce several basic concepts in metric geometry [93], which are known to include both Euclidean spaces and Riemannian manifolds as special cases. Formally, we have

A path \(\gamma: [0, 1] \mapsto X\) is a continuous mapping from the interval \([0, 1]\) to \(X\) and the length of \(\gamma\) is defined as \(\textrm{length}(\gamma) :=\lim_{n \rightarrow +\infty} \sup_{0 = t_0 < \ldots < t_n = 1} \sum_{i=1}^n d(\gamma(t_{i-1}), \gamma(t_i))\). Note that the triangle inequality implies that \(\sup_{0 = t_0 < \ldots < t_n = 1} \sum_{i=1}^n d(\gamma(t_{i-1}), \gamma(t_i))\) is nondecreasing. Then, the length of a path \(\gamma\) is well defined since the limit is either \(+\infty\) or a finite scalar. Moreover, for \(\forall \epsilon > 0\), there exists \(n \in \mathbb{N}\) and the partition \(0 = t_0 < \ldots < t_n = 1\) of the interval \([0, 1]\) such that \(\textrm{length}(\gamma) \leq \sum_{i=1}^n d(\gamma(t_{i-1}), \gamma(t_i)) + \epsilon\).

We can see from Definition 6 that a set of length spaces is strict subclass of metric spaces; indeed, for some \(x, x' \in X\), there does not exist a path \(\gamma\) such that its length can be approximated by \(d(x, x')\) for some tolerance \(\epsilon > 0\). In metric geometry, a geodesic is a path which is locally a distance minimizer everywhere. More precisely, a path \(\gamma\) is a geodesic if there is a constant \(\nu > 0\) such that for any \(t \in [0, 1]\) there is a neighborhood \(I\) of \([0,1]\) such that, \[d(\gamma(t_1),\gamma(t_2)) = \nu|t_1 - t_2|, \quad \textrm{for any } t_1, t_2 \in I.\] Note that the above generalizes the notion of geodesic for Riemannian manifolds. Then, we are ready to introduce the geodesic space and uniquely geodesic space [135].

Trigonometric geometry in nonlinear spaces is intrinsically different from Euclidean space. In particular, we remark that the law of cosines in Euclidean space (with \(\|\cdot\|\) as \(\ell_2\)-norm) is crucial for analyzing the convergence property of optimization algorithms, e.g., \[\|a\|^2 = \|b\|^2 + \|c\|^2 - 2bc\cos(A),\] where \(a\), \(b\), \(c\) are sides of a geodesic triangle in Euclidean space and \(A\) is the angle between \(b\) and \(c\). However, such nice property does not hold for nonlinear spaces due to the lack of flat geometry, further motivating us to extend the law of cosines under nonlinear trigonometric geometry. That is to say, given a geodesic triangle in \(X\) with sides \(a\), \(b\), \(c\) where \(A\) is the angle between \(b\) and \(c\), we hope to establish the relationship between \(a^2\), \(b^2\), \(c^2\) and \(2bc\cos(A)\) in nonlinear spaces; see the main context for the comparing inequalities.

Finally, we specify the definition of section curvature of Riemannian manifolds and clarify how such quantity affects the trigonometric comparison inequalities. More specifically, the sectional curvature is defined as the Gauss curvature of a 2-dimensional sub-manifold that are obtained from the image of a two-dimensional subspace of a tangent space after exponential mapping. It is worth mentioning that the above 2-dimensional sub-manifold is locally isometric to a 2-dimensional sphere, a Euclidean plane, and a hyperbolic plane with the same Gauss curvature if its sectional curvature is positive, zero and negative respectively. Then we are ready to summarize the existing trigonometric comparison inequalities for Riemannian manifold with bounded sectional curvatures. Note that the following two propositions are the full version of Proposition 1 and will be used in our subsequent proofs.

9 Riemannian Gradient Descent Ascent for Nonsmooth Setting↩︎

In this section, we propose and analyze Riemannian gradient descent ascent (RGDA) method for nonsmooth Riemannian min-max optimization and extend it to stochastic RGDA. We present our results on the optimal last-iterate convergence guarantee for geodesically strongly-convex-strongly-concave setting (both deterministic and stochastic) and time-average convergence guarantee for geodesically convex-concave setting (both deterministic and stochastic).

9.1 Algorithmic scheme↩︎

Compared to Riemannian corrected extragradient (RCEG) method, our Riemannian gradient descent ascent (RGDA) method is a relatively straightforward generalization of GDA in Euclidean spaces. More specifically, we start with the scheme of GDA as follows (just consider \(\mathcal{M}\) and \(\mathcal{N}\) as convex constraint sets in Euclidean spaces), \[\label{def:GDA} \begin{array}{rclcrcl} x_{t+1} & \leftarrow & \textrm{proj}_\mathcal{M}(x_t - \eta_t \cdot g_x^t), & & y_{t+1} & \leftarrow & \textrm{proj}_\mathcal{N}(y_t + \eta_t \cdot g_y^t). \end{array}\tag{6}\] where \((g_x^t, g_y^t) \in (\partial_x f(x_t, y_t), \partial_y f(x_t, y_t))\) is one subgradient of \(f\). By replacing the projection operator by the corresponding exponential map and the gradient by the corresponding Riemannian gradient, we have \[x_{t+1} \leftarrow \textrm{Exp}_{x_t}(- \eta_t \cdot g_x^t), \quad y_{t+1} \leftarrow \textrm{Exp}_{y_t}(\eta_t \cdot g_y^t).\] where \((g_x^t, g_y^t) \leftarrow (\textrm{subgrad}_x f(x_t, y_t), \textrm{subgrad}_y f(x_t, y_t))\) is one Riemannian subgradient of \(f\). Then, we summarize the resulting scheme of RGDA method in Algorithm 2 and its stochastic extension with noisy estimators of Riemannian gradients of \(f\) in Algorithm [tbl:alg:SRGDA].

Table 2: RGDA

9.2 Main results↩︎

We present our main results on the global convergence rate estimation for Algorithm 2 and [tbl:alg:SRGDA] in terms of Riemannian gradient and noisy Riemannian gradient evaluations. The following assumptions are made throughout for geodesically strongly-convex-strongly-concave and geodesically convex-concave settings.

Imposing the geodesically Lipschitzness condition is crucial to achieve finite-time convergence guarantee if we do not assume the geodesically smoothness condition. Note that we only require the lower bound for the sectional curvatures of manifolds and this is weaker than that presented in the main context.

Letting \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) be a global saddle point of \(f\) (it exists under either Assumption 4 or 5), we let \(D_0 = (d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2 > 0\) and summarize our results for Algorithm 2 in the following theorems.

In the scheme of SRGDA, we highlight that \((g_x^t, g_y^t)\) is a noisy estimators of Riemannian subgradient of \(f\) at \((x_t, y_t)\). It is necessary to impose the conditions such that these estimators are unbiased and has bounded variance. By abuse of notation, we assume that \[\label{def:noisy-model-RGDA} \begin{array}{lcl} g_x^t = \textrm{subgrad}_x f(x_t, y_t) + \xi_x^t, & & g_y^t = \textrm{subgrad}_y f(x_t, y_t) + \xi_y^t, \end{array}\tag{7}\] where the noises \((\xi_x^t, \xi_y^t)\) satisfy that \[\label{def:noisy-bound-RGDA} \begin{array}{lclcl} {\mathbb{E}}[\xi_x^t] = 0, & & {\mathbb{E}}[\xi_y^t] = 0, & & {\mathbb{E}}[\|\xi_x^t\|^2 + \|\xi_y^t\|^2] \leq \sigma^2. \end{array}\tag{8}\] We are ready to summarize our results for Algorithm [tbl:alg:SRGDA] in the following theorems.

10 Missing Proofs for Riemannian Corrected Extragradient Method↩︎

In this section, we present some technical lemmas for analyzing the convergence property of Algorithm 1 and [tbl:alg:SRCEG]. We also give the proofs of Theorem 2, 3 and 4.

10.1 Technical lemmas↩︎

We provide two technical lemmas for analyzing Algorithm 1 and [tbl:alg:SRCEG] respectively. Parts of the first lemma were presented in [1]. For the completeness, we provide the proof details.

Since \(f\) is geodesically \(\ell\)-smooth, we have the Riemannian gradients of \(f\), i.e., \((\textrm{grad}_x f, \textrm{grad}_y f)\), are well defined. Since \(f\) is geodesically strongly-concave-strongly-concave with the modulus \(\mu \geq 0\) (here \(\mu = 0\) means that \(f\) is geodesically concave-concave), we have \[\begin{align}\\ & \overset{\textrm{Definition~\ref{def:SCSC}}}{\leq} & - \langle \textrm{grad}_x f(\hat{x}_t,\hat{y}_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle + \langle \textrm{grad}_y f(\hat{x}_t,\hat{y}_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \tfrac{\mu}{2}(d_\mathcal{M}(\hat{x}_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(\hat{y}_t, y^\star))^2. \end{align}\] Since \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) is a global saddle point of \(f\), we have \(f(\hat{x}_t, y^\star) - f(x^\star, \hat{y}_t) \geq 0\). Recalling also from the scheme of Algorithm 1 that we have \[\begin{align} x_{t+1} & \leftarrow & \textrm{Exp}_{\hat{x}_t}(-\eta \cdot \textrm{grad}_x f(\hat{x}_t,\hat{y}_t) + \textrm{Exp}_{\hat{x}_t}^{-1}(x_t)), \\ y_{t+1} & \leftarrow & \textrm{Exp}_{\hat{y}_t}(\eta \cdot \textrm{grad}_y f(\hat{x}_t,\hat{y}_t) + \textrm{Exp}_{\hat{y}_t}^{-1}(y_t)). \end{align}\] By the definition of an exponential map, we have \[\label{inequality:RCEG-opt} \begin{array}{lcl} \textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1}) & = & -\eta \cdot \textrm{grad}_x f(\hat{x}_t,\hat{y}_t) + \textrm{Exp}_{\hat{x}_t}^{-1}(x_t), \\ \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}) & = & \eta \cdot \textrm{grad}_y f(\hat{x}_t,\hat{y}_t) + \textrm{Exp}_{\hat{y}_t}^{-1}(y_t). \end{array}\tag{9}\] This implies that \[\begin{align} - \langle \textrm{grad}_x f(\hat{x}_t,\hat{y}_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle & = & \tfrac{1}{\eta} (\langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1}), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star)\rangle - \langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle), \\ \langle \textrm{grad}_y f(\hat{x}_t,\hat{y}_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle & = & \tfrac{1}{\eta} (\langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle). \end{align}\] Putting these pieces together yields that \[\begin{align}\\ & & + \tfrac{1}{\eta} (\langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle) - \tfrac{\mu}{2}(d_\mathcal{N}(\hat{y}_t, y^\star))^2. \end{align}\] Equivalently, we have \[\begin{align} \label{inequality:RCEG-key-first}\\ & & + \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \tfrac{\mu\eta}{2}(d_\mathcal{N}(\hat{y}_t, y^\star))^2. \nonumber \end{align}\tag{10}\] It suffices to bound the terms in the right-hand side of Eq. 10 by leveraging the celebrated comparison inequalities on Riemannian manifold with bounded sectional curvature (see Proposition 5 and 6). More specifically, we define the constants using \(\overline{\xi}(\cdot, \cdot)\) and \(\underline{\xi}(\cdot, \cdot)\) from Proposition 5 and 6 as follows, \[\overline{\xi}_0 = \overline{\xi}(\kappa_{\min}, D), \qquad \underline{\xi}_0 = \underline{\xi}(\kappa_{\max}, D).\] By Proposition 5 and using that \(\max\{d_\mathcal{M}(\hat{x}_t, x^\star), d_\mathcal{N}(\hat{y}_t, y^\star)\} \leq D\), we have \[\label{inequality:RCEG-key-second} \begin{array}{lll} - \langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle & \leq & - \tfrac{1}{2}\left(\underline{\xi}_0(d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{M}(\hat{x}_t, x^\star))^2 - (d_\mathcal{M}(x_t, x^\star))^2\right), \\ - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle & \leq & - \tfrac{1}{2}\left(\underline{\xi}_0(d_\mathcal{N}(\hat{y}_t, y_t))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 - (d_\mathcal{N}(y_t, y^\star))^2\right). \end{array}\tag{11}\] By Proposition 6 and using that \(\max\{d_\mathcal{M}(\hat{x}_t, x^\star), d_\mathcal{N}(\hat{y}_t, y^\star)\} \leq D\), we have \[\langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1}), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle \leq \tfrac{1}{2}\left(\overline{\xi}_0(d_\mathcal{M}(\hat{x}_t, x_{t+1}))^2 + (d_\mathcal{M}(\hat{x}_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2\right).\] and \[\langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle \leq \tfrac{1}{2}\left(\overline{\xi}_0(d_\mathcal{N}(\hat{y}_t, y_{t+1}))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right).\] By the definition of an exponential map and Riemannian metric, we have \[\label{inequality:RCEG-key-third} \begin{array}{lll} d_\mathcal{M}(\hat{x}_t, x_{t+1}) & = & \|\textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1})\| \overset{\textrm{Eq.~\eqref{inequality:RCEG-opt}}}{=} \|\eta \cdot \textrm{grad}_x f(\hat{x}_t,\hat{y}_t) - \textrm{Exp}_{\hat{x}_t}^{-1}(x_t)\|, \\ d_\mathcal{N}(\hat{y}_t, y_{t+1}) & = & \|\textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1})\| \overset{\textrm{Eq.~\eqref{inequality:RCEG-opt}}}{=} \|\eta \cdot \textrm{grad}_y f(\hat{x}_t,\hat{y}_t) + \textrm{Exp}_{\hat{y}_t}^{-1}(y_t)\|. \end{array}\tag{12}\] Further, we see from the scheme of Algorithm 1 that we have \[\begin{align} \hat{x}_t & \leftarrow & \textrm{Exp}_{x_t}(-\eta \cdot \textrm{grad}_x f(x_t, y_t)), \\ \hat{y}_t & \leftarrow & \textrm{Exp}_{y_t}(\eta \cdot \textrm{grad}_y f(x_t, y_t)). \end{align}\] By the definition of an exponential map, we have \[\textrm{Exp}_{x_t}^{-1}(\hat{x}_t) = -\eta \cdot \textrm{grad}_x f(x_t, y_t), \qquad \textrm{Exp}_{y_t}^{-1}(\hat{y}_t) = \eta \cdot \textrm{grad}_y f(x_t, y_t).\] Using the definition of a parallel transport map and the above equations, we have \[\textrm{Exp}_{\hat{x}_t}^{-1}(x_t) = \eta \cdot \Gamma_{x_t}^{\hat{x}_t}\textrm{grad}_x f(x_t, y_t), \qquad \textrm{Exp}_{\hat{y}_t}^{-1}(y_t) = - \eta \cdot \Gamma_{y_t}^{\hat{y}_t}\textrm{grad}_y f(x_t, y_t)\] Since \(f\) is geodesically \(\ell\)-smooth, we have \[\begin{array}{lll} \|\textrm{grad}_x f(\hat{x}_t,\hat{y}_t) - \Gamma_{x_t}^{\hat{x}_t}\textrm{grad}_x f(x_t, y_t)\| & \leq & \ell(d_\mathcal{M}(\hat{x}_t, x_t) + d_\mathcal{N}(\hat{y}_t, y_t)), \\ \|\textrm{grad}_y f(\hat{x}_t,\hat{y}_t) - \Gamma_{y_t}^{\hat{y}_t}\textrm{grad}_y f(x_t, y_t)\| & \leq & \ell(d_\mathcal{M}(\hat{x}_t, x_t) + d_\mathcal{N}(\hat{y}_t, y_t)). \end{array}\] Plugging the above inequalities into Eq. 12 yields that \[\max\left\{d_\mathcal{M}(\hat{x}_t, x_{t+1}), d_\mathcal{N}(\hat{y}_t, y_{t+1})\right\} \leq \eta\ell(d_\mathcal{M}(\hat{x}_t, x_t) + d_\mathcal{N}(\hat{y}_t, y_t)).\] Therefore, we have \[\begin{array}{lll} \langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1}), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle & \leq & \tfrac{1}{2}\left(2\overline{\xi}_0\eta^2\ell^2((d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2) + (d_\mathcal{M}(\hat{x}_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2\right), \\ \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle & \leq & \tfrac{1}{2}\left(2\overline{\xi}_0\eta^2\ell^2((d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2) + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right). \end{array}\] Plugging the above inequalities and Eq. 11 into Eq. 10 yields the desired inequality. \(\Box\) The second lemma gives another key inequality that is satisfied by the iterates generated by Algorithm [tbl:alg:SRCEG].

Using the same argument, we have (\(\mu=0\) refers to geodesically convex-concave case) \[\begin{align}\\ & \leq & - \langle \textrm{grad}_x f(\hat{x}_t,\hat{y}_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle + \langle \textrm{grad}_y f(\hat{x}_t,\hat{y}_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \tfrac{\mu}{2}(d_\mathcal{M}(\hat{x}_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(\hat{y}_t, y^\star))^2. \end{align}\] Combining the arguments used in Lemma 1 and the scheme of Algorithm [tbl:alg:SRCEG], we have \[\begin{align} - \langle \hat{g}_x^t, \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle & = & \tfrac{1}{\eta} (\langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1}), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star)\rangle - \langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle), \\ \langle \hat{g}_y^t, \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle & = & \tfrac{1}{\eta} (\langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle). \end{align}\] Putting these pieces together with Eq. 3 yields that \[\begin{align} \label{inequality:SRCEG-key-first}\\ & & + \tfrac{1}{\eta} (\langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle) - \tfrac{\mu}{2}(d_\mathcal{M}(\hat{x}_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(\hat{y}_t, y^\star))^2 \nonumber \\ & & + \langle \hat{\xi}_x^t, \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star)\rangle - \langle \hat{\xi}_y^t, \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle. \nonumber \end{align}\tag{13}\] By the same argument as used in Lemma 1, we have \[\label{inequality:SRCEG-key-second} \begin{array}{lll} - \langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_t), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle & \leq & - \tfrac{1}{2}\left(\underline{\xi}_0(d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{M}(\hat{x}_t, x^\star))^2 - (d_\mathcal{M}(x_t, x^\star))^2\right), \\ - \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_t), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle & \leq & - \tfrac{1}{2}\left(\underline{\xi}_0(d_\mathcal{N}(\hat{y}_t, y_t))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 - (d_\mathcal{N}(y_t, y^\star))^2\right), \end{array}\tag{14}\] and \[\begin{array}{lll} \langle \textrm{Exp}_{\hat{x}_t}^{-1}(x_{t+1}), \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0\eta^2\|\hat{g}_x^t - \Gamma_{x_t}^{\hat{x}_t} g_x^t\|^2 + (d_\mathcal{M}(\hat{x}_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2\right), \\ \langle \textrm{Exp}_{\hat{y}_t}^{-1}(y_{t+1}), \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0\eta^2\|\hat{g}_y^t - \Gamma_{y_t}^{\hat{y}_t} g_y^t\|^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right). \end{array}\] Since \(f\) is geodesically \(\ell\)-smooth and Eq. 3 holds, we have \[\begin{align} \|\hat{g}_x^t - \Gamma_{x_t}^{\hat{x}_t} g_x^t\|^2 & \leq & 3\|\hat{\xi}_x^t\|^2 + 3\|\xi_x^t\|^2 + 6\ell^2(d_\mathcal{M}(\hat{x}_t, x_t))^2 + 6\ell^2(d_\mathcal{N}(\hat{y}_t, y_t))^2, \\ \|\hat{g}_y^t - \Gamma_{y_t}^{\hat{y}_t} g_y^t\|^2 & \leq & 3\|\hat{\xi}_y^t\|^2 + 3\|\xi_y^t\|^2 + 6\ell^2(d_\mathcal{M}(\hat{x}_t, x_t))^2 + 6\ell^2(d_\mathcal{N}(\hat{y}_t, y_t))^2. \end{align}\] Therefore, we have \[\begin{align}\\ & \leq & 6\overline{\xi}_0\eta^2\ell^2((d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2) + \tfrac{3}{2}\overline{\xi}_0\eta^2(\|\hat{\xi}_x^t\|^2 + \|\xi_x^t\|^2 + \|\hat{\xi}_y^t\|^2 + \|\xi_y^t\|^2) \\ & & + \tfrac{1}{2}\left((d_\mathcal{M}(\hat{x}_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right). \end{align}\] Plugging the above inequalities and Eq. 14 into Eq. 13 yields that \[\begin{align}\\ & & + 6\overline{\xi}_0\eta\ell^2((d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2) + \tfrac{3}{2}\overline{\xi}_0\eta(\|\hat{\xi}_x^t\|^2 + \|\xi_x^t\|^2 + \|\hat{\xi}_y^t\|^2 + \|\xi_y^t\|^2) \\ & & - \tfrac{1}{2\eta}\underline{\xi}_0\left((d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2\right) - \tfrac{\mu}{2}(d_\mathcal{M}(\hat{x}_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(\hat{y}_t, y^\star))^2 \\ & & + \langle \hat{\xi}_x^t, \textrm{Exp}_{\hat{x}_t}^{-1}(x^\star)\rangle - \langle \hat{\xi}_y^t, \textrm{Exp}_{\hat{y}_t}^{-1}(y^\star)\rangle. \end{align}\] Taking the expectation of both sides and using Eq. 4 yields the desired inequality. \(\Box\)

10.2 Proof of Theorem 2↩︎

Since Riemannian metrics satisfy the triangle inequality, we have \[(d_\mathcal{M}(\hat{x}_t, x^\star))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 \geq \tfrac{1}{2}((d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2) - (d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2.\] Plugging the above inequality into the inequality from Lemma 1 yields that \[\begin{align}\\ & \leq & \left(1 - \tfrac{\mu\eta}{2}\right)\left((d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right) + (4\overline{\xi}_0\eta^2\ell^2 + \mu\eta - \underline{\xi}_0)((d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2. \end{align}\] Since \(\eta = \min\{\frac{1}{4\ell\sqrt{\tau_0}}, \frac{\underline{\xi}_0}{2\mu}\}\), we have \(4\overline{\xi}_0\eta^2\ell^2 + \mu\eta - \underline{\xi}_0 \leq 0\). By the definition, we have \(\tau_0 \geq 1\), \(\kappa \geq 1\) and \(\underline{\xi}_0 \leq 1\). This implies that \[1 - \tfrac{\mu\eta}{2} = 1 - \min\left\{\tfrac{1}{8\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\} > 0.\] Putting these pieces together yields that \[\begin{align} (d_\mathcal{M}(x_T, x^\star))^2 + (d_\mathcal{N}(y_T, y^\star))^2 & \leq & \left(1 - \min\left\{\tfrac{1}{8\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\}\right)^T(d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2 \\ & \leq & \left(1 - \min\left\{\tfrac{1}{8\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\}\right)^T D_0. \end{align}\] This completes the proof.

10.3 Proof of Theorem 3↩︎

Since Riemannian metrics satisfy the triangle inequality, we have \[(d_\mathcal{M}(\hat{x}_t, x^\star))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2 \geq \tfrac{1}{2}((d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2) - (d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2.\] Plugging the above inequality into the inequality from Lemma 2 yields that \[\begin{align}\\ & & + (6\overline{\xi}_0\eta\ell^2 + \tfrac{\mu}{2} - \tfrac{1}{2\eta}\underline{\xi}_0){\mathbb{E}}\left[(d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2\right] - \tfrac{\mu}{4}{\mathbb{E}}\left[(d_\mathcal{M}(\hat{x}_t, x^\star))^2 + (d_\mathcal{N}(\hat{y}_t, y^\star))^2\right] + 3\overline{\xi}_0\eta\sigma^2. \end{align}\] Since \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) is a global saddle point of \(f\), we have \({\mathbb{E}}[f(\hat{x}_t, y^\star) - f(x^\star, \hat{y}_t)] \geq 0\). Then, we have \[\begin{align}\\ & \leq & \left(1 - \tfrac{\mu\eta}{2}\right){\mathbb{E}}\left[(d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right] + (12\overline{\xi}_0\eta^2\ell^2 + \mu\eta - \underline{\xi}_0){\mathbb{E}}\left[(d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2\right] \\ & & + 6\overline{\xi}_0\eta^2\sigma^2. \end{align}\] Since \(\eta \leq \min\{\frac{1}{24\ell\sqrt{\tau_0}}, \frac{\underline{\xi}_0}{2\mu}\}\), we have \(12\overline{\xi}_0\eta^2\ell^2 + \mu\eta - \underline{\xi}_0 \leq 0\). This implies that \[{\mathbb{E}}\left[(d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(y_{t+1}, y^\star))^2\right] \leq \left(1 - \tfrac{\mu\eta}{2}\right){\mathbb{E}}\left[(d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right] + 6\overline{\xi}_0\eta^2\sigma^2.\] By the definition, we have \(\tau_0 \geq 1\), \(\kappa \geq 1\) and \(\underline{\xi}_0 \leq 1\). This implies that \[1 - \tfrac{\mu\eta}{2} \geq 1 - \min\left\{\tfrac{1}{48\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\} > 0.\] By the inductive arguments, we have \[\begin{align} {\mathbb{E}}\left[(d_\mathcal{M}(x_T, x^\star))^2 + (d_\mathcal{N}(y_T, y^\star))^2\right] & \leq & \left(1 - \tfrac{\mu\eta}{2}\right)^T\left((d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2\right) + 6\overline{\xi}_0\eta^2\sigma^2\left(\sum_{t=0}^{T-1} \left(1 - \tfrac{\mu\eta}{2}\right)^t\right) \\ & \leq & \left(1 - \tfrac{\mu\eta}{2}\right)^T D_0 + \tfrac{12\overline{\xi}_0\eta\sigma^2}{\mu}. \end{align}\] Since \(\eta = \min\{\frac{1}{24\ell\sqrt{\tau_0}}, \frac{\underline{\xi}_0}{2\mu}, \tfrac{2(\log(T) + \log(\mu^2 D_0 \sigma^{-2}))}{\mu T}\}\), we have \[\begin{align} \left(1 - \tfrac{\mu\eta}{2}\right)^T D_0 & \leq & \left(1 - \min\left\{\tfrac{1}{48\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\}\right)^T D_0 + \left(1 - \tfrac{\log(\mu^2 D_0 \sigma^{-2}T)}{T}\right)^T D_0 \\ & \overset{1 + x \leq e^x}{\leq} & \left(1 - \min\left\{\tfrac{1}{48\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\}\right)^T D_0 + \tfrac{\sigma^2}{\mu^2 T}, \end{align}\] and \[\tfrac{12\overline{\xi}_0\eta\sigma^2}{\mu} \leq \tfrac{24\overline{\xi}_0\sigma^2}{\mu^2 T}\log\left(\tfrac{\mu^2 D_0 T}{\sigma^2}\right).\] Putting these pieces together yields that \[{\mathbb{E}}\left[(d_\mathcal{M}(x_T, x^\star))^2 + (d_\mathcal{N}(y_T, y^\star))^2\right] \leq \left(1 - \min\left\{\tfrac{1}{48\kappa\sqrt{\tau_0}}, \tfrac{\underline{\xi}_0}{4}\right\}\right)^T D_0 + \tfrac{\sigma^2}{\mu^2 T} + \tfrac{24\overline{\xi}_0\sigma^2}{\mu^2 T}\log\left(\tfrac{\mu^2 D_0 T}{\sigma^2}\right).\] This completes the proof.

10.4 Proof of Theorem 4↩︎

By the inductive formulas of \(\bar{x}_{t+1} = \textrm{Exp}_{\bar{x}_t}(\tfrac{1}{t+1} \cdot \textrm{Exp}_{\bar{x}_t}^{-1}(\hat{x}_t))\) and \(\bar{y}_{t+1} = \textrm{Exp}_{\bar{y}_t}(\tfrac{1}{t+1} \cdot \textrm{Exp}_{\bar{y}_t}^{-1}(\hat{y}_t))\) and using [1], we have \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq \tfrac{1}{T}\left(\sum_{t=0}^{T-1} f(\hat{x}_t, y^\star) - f(x^\star, \hat{y}_t)\right).\] Plugging the above inequality into the inequality from Lemma 2 yields that (recall that \(\mu = 0\) in geodesically convex-concave setting here) \[\begin{align}\\ & & + \tfrac{1}{T}\left(6\overline{\xi}_0\eta\ell^2 - \tfrac{1}{2\eta}\underline{\xi}_0\right)\left(\sum_{t=0}^{T-1} {\mathbb{E}}\left[(d_\mathcal{M}(\hat{x}_t, x_t))^2 + (d_\mathcal{N}(\hat{y}_t, y_t))^2\right]\right) + 3\overline{\xi}_0\eta\sigma^2. \end{align}\] Since \(\eta \leq \frac{1}{4\ell\sqrt{\tau_0}}\), we have \(6\overline{\xi}_0\eta\ell^2 - \tfrac{1}{2\eta}\underline{\xi}_0 \leq 0\). Then, this together with \((d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2 \leq D_0\) implies that \[{\mathbb{E}}[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T)] \leq \tfrac{D_0}{2\eta T} + 3\overline{\xi}_0\eta\sigma^2.\] Since \(\eta = \min\{\frac{1}{4\ell\sqrt{\tau_0}}, \tfrac{1}{\sigma}\sqrt{\tfrac{D_0}{\overline{\xi}_0 T}}\}\), we have \[\tfrac{D_0}{2\eta T} \leq \tfrac{2\ell D_0\sqrt{\tau_0}}{T} + \tfrac{\sigma}{2}\sqrt{\tfrac{\overline{\xi}_0 D_0}{T}},\] and \[3\overline{\xi}_0\eta\sigma^2 \leq 3\sigma\sqrt{\tfrac{\overline{\xi}_0 D_0}{T}}.\] Putting these pieces together yields that \[{\mathbb{E}}[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T)] \leq \tfrac{2\ell D_0\sqrt{\tau_0}}{T} + \tfrac{7\sigma}{2}\sqrt{\tfrac{\overline{\xi}_0 D_0}{T}}.\] This completes the proof.

11 Missing Proofs for Riemannian Gradient Descent Ascent↩︎

In this section, we present some technical lemmas for analyzing the convergence property of Algorithm 2 and [tbl:alg:SRGDA]. We also give the proofs of Theorem 7, 8, 9 and 10.

11.1 Technical lemmas↩︎

We provide two technical lemmas for analyzing Algorithm 2 and [tbl:alg:SRGDA] respectively. The first lemma gives a key inequality that is satisfied by the iterates generated by Algorithm 2.

Since \(f\) is geodesically strongly-concave-strongly-concave with the modulus \(\mu \geq 0\) (here \(\mu = 0\) means that \(f\) is geodesically concave-concave), we have \[\begin{align}\\ & \leq & - \langle \textrm{subgrad}_x f(x_t, y_t), \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle + \langle \textrm{subgrad}_y f(x_t, y_t), \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle - \tfrac{\mu}{2}(d_\mathcal{M}(x_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(y_t, y^\star))^2. \end{align}\] Recalling also from the scheme of Algorithm 2 that we have \[\begin{align} x_{t+1} & \leftarrow & \textrm{Exp}_{x_t}(-\eta_t \cdot \textrm{subgrad}_x f(x_t, y_t)), \\ y_{t+1} & \leftarrow & \textrm{Exp}_{y_t}(\eta_t \cdot \textrm{subgrad}_y f(x_t, y_t)). \end{align}\] By the definition of an exponential map, we have \[\label{inequality:RGDA-opt} \begin{array}{lcl} \textrm{Exp}_{x_t}^{-1}(x_{t+1}) & = & -\eta_t \cdot \textrm{subgrad}_x f(x_t,y_t), \\ \textrm{Exp}_{y_t}^{-1}(y_{t+1}) & = & \eta_t \cdot \textrm{subgrad}_y f(x_t, y_t). \end{array}\tag{15}\] This implies that \[\begin{align} - \langle \textrm{subgrad}_x f(x_t, y_t), \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle & = & \tfrac{1}{\eta_t} \langle \textrm{Exp}_{x_t}^{-1}(x_{t+1}), \textrm{Exp}_{x_t}^{-1}(x^\star)\rangle, \\ \langle \textrm{subgrad}_y f(x_t, y_t), \textrm{Exp}_{y_t}^{-1}(y^\star) \rangle & = & \tfrac{1}{\eta_t} \langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle. \end{align}\] Putting these pieces together yields that \[\begin{align} \label{inequality:RGDA-key-first}\\ & & + \tfrac{1}{\eta_t}\langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle - \tfrac{\mu}{2}(d_\mathcal{M}(x_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(y_t, y^\star))^2. \nonumber \end{align}\tag{16}\] It suffices to bound the terms in the right-hand side of Eq. 16 by leveraging the celebrated comparison inequalities on Riemannian manifold with lower bounded sectional curvature (see Proposition 6). More specifically, we define the constants using \(\overline{\xi}(\cdot, \cdot)\) and \(\underline{\xi}(\cdot, \cdot)\) from Proposition 6 as follows, \[\overline{\xi}_0 = \overline{\xi}(\kappa_{\min}, D).\] By Proposition 6 and using that \(\max\{d_\mathcal{M}(x_t, x^\star), d_\mathcal{N}(y_t, y^\star)\} \leq D\), we have \[\begin{align} \langle \textrm{Exp}_{x_t}^{-1}(x_{t+1}), \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0(d_\mathcal{M}(x_t, x_{t+1}))^2 + (d_\mathcal{M}(x_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2\right), \\ \langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0(d_\mathcal{N}(y_t, y_{t+1}))^2 + (d_\mathcal{N}(y_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right). \end{align}\] Since \(f\) is geodesically \(L\)-Lipschitz, we have \[\|\textrm{subgrad}_x f(x_t,y_t)\| \leq L, \quad \|\textrm{subgrad}_y f(x_t,y_t)\| \leq L.\] By the definition of an exponential map and Riemannian metric, we have \[\begin{array}{lll} d_\mathcal{M}(x_t, x_{t+1}) & = & \|\textrm{Exp}_{x_t}^{-1}(x_{t+1})\| \overset{\textrm{Eq.~\eqref{inequality:RGDA-opt}}}{=} \|\eta_t \cdot \textrm{subgrad}_x f(x_t, y_t)\| \leq \eta_t L, \\ d_\mathcal{N}(y_t, y_{t+1}) & = & \|\textrm{Exp}_{y_t}^{-1}(y_{t+1})\| \overset{\textrm{Eq.~\eqref{inequality:RGDA-opt}}}{=} \|\eta_t \cdot \textrm{subgrad}_y f(x_t, y_t)\| \leq \eta_t L. \end{array}\] Putting these pieces together yields that \[\begin{align} \langle \textrm{Exp}_{x_t}^{-1}(x_{t+1}), \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0 \eta_t^2 L^2 + (d_\mathcal{M}(x_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2\right), \\ \langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0 \eta_t^2 L^2 + (d_\mathcal{N}(y_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right). \end{align}\] Plugging the above inequalities into Eq. 16 yields the desired inequality. \(\Box\) The second lemma gives another key inequality that is satisfied by the iterates generated by Algorithm [tbl:alg:SRGDA].

Using the same argument, we have (\(\mu=0\) refers to geodesically convex-concave case) \[\begin{align}\\ & \leq & - \langle \textrm{subgrad}_x f(x_t, y_t), \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle + \langle \textrm{subgrad}_y f(x_t, y_t), \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle - \tfrac{\mu}{2}(d_\mathcal{M}(x_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(y_t, y^\star))^2. \end{align}\] Combining the arguments used in Lemma 3 and the scheme of Algorithm [tbl:alg:SRCEG], we have \[\begin{align} - \langle g_x^t, \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle & = & \tfrac{1}{\eta_t}\langle \textrm{Exp}_{x_t}^{-1}(x_{t+1}), \textrm{Exp}_{x_t}^{-1}(x^\star)\rangle, \\ \langle g_y^t, \textrm{Exp}_{y_t}^{-1}(y^\star) \rangle & = & \tfrac{1}{\eta_t}\langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle. \end{align}\] Putting these pieces together with Eq. 7 yields that \[\begin{align} \label{inequality:SRGDA-key-first}\\ & & + \tfrac{1}{\eta_t}\langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle - \tfrac{\mu}{2}(d_\mathcal{M}(x_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(y_t, y^\star))^2 + \langle \xi_x^t, \textrm{Exp}_{x_t}^{-1}(x^\star)\rangle - \langle \xi_y^t, \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle. \nonumber \end{align}\tag{17}\] By the same argument as used in Lemma 3 and Eq. 7 , we have \[\begin{align} \langle \textrm{Exp}_{x_t}^{-1}(x_{t+1}), \textrm{Exp}_{x_t}^{-1}(x^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0(d_\mathcal{M}(x_t, x_{t+1}))^2 + (d_\mathcal{M}(x_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2\right), \\ \langle \textrm{Exp}_{y_t}^{-1}(y_{t+1}), \textrm{Exp}_{y_t}^{-1}(y^\star) \rangle & \leq & \tfrac{1}{2}\left(\overline{\xi}_0(d_\mathcal{N}(y_t, y_{t+1}))^2 + (d_\mathcal{N}(y_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right), \end{align}\] and \[\begin{array}{lll} d_\mathcal{M}(x_t, x_{t+1}) & = & \|\textrm{Exp}_{x_t}^{-1}(x_{t+1})\| \;= \;\|\eta_t \cdot g_x^t\| \;\leq \;\eta_t (L + \|\xi_x^t\|), \\ d_\mathcal{N}(y_t, y_{t+1}) & = & \|\textrm{Exp}_{y_t}^{-1}(y_{t+1})\| \;= \;\|\eta_t \cdot g_y^t\| \;\leq \;\eta_t (L + \|\xi_y^t\|). \end{array}\] Therefore, we have \[\begin{align}\\ & \leq & \tfrac{1}{2}\overline{\xi}_0\eta_t^2(4L^2 + 2\|\xi_x^t\|^2 + 2\|\xi_y^t\|^2) + \tfrac{1}{2}\left((d_\mathcal{M}(x_t, x^\star))^2 - (d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2 - (d_\mathcal{N}(y_{t+1}, y^\star))^2\right). \end{align}\] Plugging the above inequalities into Eq. 17 yields that \[\begin{align}\\ & & + \overline{\xi}_0\eta_t(2L^2 + \|\xi_x^t\|^2 + \|\xi_y^t\|^2) - \tfrac{\mu}{2}(d_\mathcal{M}(x_t, x^\star))^2 - \tfrac{\mu}{2}(d_\mathcal{N}(y_t, y^\star))^2 + \langle \xi_x^t, \textrm{Exp}_{x_t}^{-1}(x^\star)\rangle - \langle \xi_y^t, \textrm{Exp}_{y_t}^{-1}(y^\star)\rangle. \end{align}\] Taking the expectation of both sides and using Eq. 8 yields the desired inequality. \(\Box\)

11.2 Proof of Theorem 7↩︎

Since \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) is a global saddle point of \(f\), we have \(f(x_t, y^\star) - f(x^\star, y_t) \geq 0\). Plugging this inequality into the inequality from Lemma 3 yields that \[(d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(y_{t+1}, y^\star))^2 \leq (1 - \mu\eta_t)\left((d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right) + 2\overline{\xi}_0\eta_t^2 L^2.\] Since \(\eta_t = \frac{1}{\mu}\min\{1, \frac{2}{t}\}\), we have \[(d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(y_{t+1}, y^\star))^2 \leq (1 - \tfrac{2}{t})\left((d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right) + \tfrac{8\overline{\xi}_0 L^2}{\mu^2 t^2}, \quad \textrm{for all } t \geq 2.\] Letting \(\{b_t\}_{t \geq 1}\) be a nonnegative sequence such that \(a_{t+1} \leq (1 - \frac{P}{t})a_t + \frac{Q}{t^2}\) where \(P > 1\) and \(Q > 0\). Then, [137] proved that \(a_t \leq \frac{Q}{P-1}\frac{1}{t}\). Therefore, we have \[(d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2 \leq \tfrac{8\overline{\xi}_0 L^2}{\mu^2 t}, \quad \textrm{for all } t \geq 2.\] This completes the proof.

11.3 Proof of Theorem 8↩︎

By the inductive formulas of \(\bar{x}_{t+1} = \textrm{Exp}_{\bar{x}_t}(\tfrac{1}{t+1} \cdot \textrm{Exp}_{\bar{x}_t}^{-1}(x_t))\) and \(\bar{y}_{t+1} = \textrm{Exp}_{\bar{y}_t}(\tfrac{1}{t+1} \cdot \textrm{Exp}_{\bar{y}_t}^{-1}(y_t))\) and using [1], we have \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq \tfrac{1}{T}\left(\sum_{t=0}^{T-1} f(x_t, y^\star) - f(x^\star, y_t)\right).\] Plugging the above inequality into the inequality from Lemma 3 yields that (recall that \(\mu = 0\) in geodesically convex-concave setting and \(\eta_t = \eta = \tfrac{1}{L}\sqrt{\tfrac{D_0}{2\overline{\xi}_0 T}}\)) \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq \tfrac{1}{2\eta T}\left((d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2\right) + \overline{\xi}_0 \eta L^2.\] This together with \((d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2 \leq D_0\) implies that \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq \tfrac{D_0}{2\eta T} + \overline{\xi}_0\eta L^2.\] Since \(\eta = \tfrac{1}{L}\sqrt{\tfrac{D_0}{2\overline{\xi}_0 T}}\), we have \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq L\sqrt{\tfrac{2\overline{\xi}_0 D_0}{T}}.\] This completes the proof.

11.4 Proof of Theorem 9↩︎

Since \((x^\star, y^\star) \in \mathcal{M}\times \mathcal{N}\) is a global saddle point of \(f\), we have \({\mathbb{E}}[f(x_t, y^\star) - f(x^\star, y_t)] \geq 0\). Plugging this inequality into the inequality from Lemma 4 yields that \[{\mathbb{E}}\left[(d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(y_{t+1}, y^\star))^2\right] \leq (1 - \mu\eta_t){\mathbb{E}}\left[(d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right] + 4\overline{\xi}_0\eta_t^2(L^2 + \sigma^2).\] Since \(\eta_t = \frac{1}{\mu}\min\{1, \frac{2}{t}\}\), we have \[{\mathbb{E}}\left[(d_\mathcal{M}(x_{t+1}, x^\star))^2 + (d_\mathcal{N}(y_{t+1}, y^\star))^2\right] \leq (1 - \tfrac{2}{t}){\mathbb{E}}\left[(d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2\right] + \tfrac{16\overline{\xi}_0(L^2 + \sigma^2)}{\mu^2 t^2}, \quad \textrm{for all } t \geq 2.\] Applying the same argument as used in Theorem 7, we have \[(d_\mathcal{M}(x_t, x^\star))^2 + (d_\mathcal{N}(y_t, y^\star))^2 \leq \tfrac{16\overline{\xi}_0(L^2 + \sigma^2)}{\mu^2 t}, \quad \textrm{for all } t \geq 2.\] This completes the proof.

11.5 Proof of Theorem 10↩︎

Using the same argument, we have \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq \tfrac{1}{T}\left(\sum_{t=0}^{T-1} f(x_t, y^\star) - f(x^\star, y_t)\right).\] Plugging the above inequality into the inequality from Lemma 4 yields that (recall that \(\mu = 0\) in geodesically convex-concave setting and \(\eta_t = \eta = \tfrac{1}{2}\sqrt{\tfrac{D_0}{\overline{\xi}_0(L^2 + \sigma^2)T}}\)) \[{\mathbb{E}}[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T)] \leq \tfrac{1}{2\eta T}\left((d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2\right) + 2\overline{\xi}_0 \eta(L^2 + \sigma^2).\] This together with \((d_\mathcal{M}(x_0, x^\star))^2 + (d_\mathcal{N}(y_0, y^\star))^2 \leq D_0\) implies that \[{\mathbb{E}}[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T)] \leq \tfrac{D_0}{2\eta T} + 2\overline{\xi}_0\eta(L^2 + \sigma^2).\] Since \(\eta = \tfrac{1}{2}\sqrt{\tfrac{D_0}{\overline{\xi}_0(L^2 + \sigma^2)T}}\), we have \[f(\bar{x}_T, y^\star) - f(x^\star, \bar{y}_T) \leq 2\sqrt{\tfrac{\overline{\xi}_0(L^2 + \sigma^2)D_0}{T}}.\] This completes the proof.

12 Additional Experimental Results↩︎

We present some additional experimental results for the effect of different choices of \(\alpha\) as well the effect of different choices of \(\eta\) for for RCEG. In our experiment here, we set \(n=40\) consistently.

Figure 6 presents the performance of RCEG when \(\alpha=2.0\). We observe that the results are similar to that summarized in Figure 4. In particular, the last iterate of RCEG consistently achieves the linearly convergence to an optimal solution in all the settings. In contrast, the average iterate of RCEG converges much slower than the last iterate of RCEG. Figure 7 summarizes the effect of different choices of \(\eta\) in RCEG. We observe that setting \(\eta\) as a relatively larger value will speed up the convergence to an optimal solution while all of the choices here lead to the linear convergence. This suggests that the choice of stepsize \(\eta\) in RCEG can be aggressive in practice.

References↩︎