Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold

Authors: Sixin Zhang
Primary area: optimization
Keywords: min-max algorithm, differential game, Riemannian manifold, Wasserstein GAN

Abstract:
We study min-max algorithms to solve zero-sum differential games on
Riemannian manifold.
Based on the notions of
differential Stackelberg equilibrium
and differential Nash equilibrium on Riemannian manifold,
we analyze the local convergence of 
two representative deterministic simultaneous algorithms $\tau$-GDA and $\tau$-SGA
to such equilibria.
Sufficient conditions are obtained to establish the linear convergence rate
of $\tau$-GDA based on the Ostrowski theorem on manifold and spectral analysis. 
To avoid strong rotational dynamics in $\tau$-GDA, 
$\tau$-SGA is extended from
the symplectic gradient-adjustment method in Euclidean space.
We analyze an 
asymptotic approximation of $\tau$-SGA 
when the learning rate ratio $\tau$ is big. 
In some cases, it can achieve a faster convergence rate 
to differential Stackelberg equilibrium compared to $\tau$-GDA. 
We show numerically how the insights obtained from the
convergence analysis may improve
the training of orthogonal Wasserstein GANs using 
stochastic $\tau$-GDA and $\tau$-SGA on simple benchmarks.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 1, 6

Reviews and discussion:
<thread>
creation date:
1730714182875

thread_type:
official_review

<thread_object>
creator: reviewer_shdj

<content>
summary:
This paper investigates the local convergence of simultaneous minimax algorithms to differential Stackelberg equilibrium (DSE) and differential Nash equilibrium (DNE) on Riemannian manifolds. The authors study two representative deterministic algorithms, $\tau$-GDA and $\tau$-SGA. For $\tau$-GDA, they derive sufficient conditions for convergence to DSE and DNE. For $\tau$-SGA, they analyze an asymptotic variant and demonstrate a faster convergence rate to DSE under specific conditions. Furthermore, the authors conduct numerical experiments to explore the behavior of stochastic versions of the two algorithms.

strengths:
1. **Significance**: This paper addresses the more general nonconvex-nonconcave setting, extending previous results to Riemannian manifolds.
2. **Comprehensiveness**: It provides a range of results by examining two types of equilibrium points, two algorithms, and extensive numerical results.

weaknesses:
1. **Limited Comparative Analysis and Interpretation**: The relationship and comparative insights between the theoretical results could be strengthened. Here are some examples.
* (i) The paper examines two equilibrium points, DSE and DNE, where DNE is a subclass of DSE with stricter definitions. Convergence to DNE would be expected to require fewer restrictions or achieve a faster rate. Theorems 3.2 and 3.3 support the former expectation, as the range of $\tau$ in Theorem 3.3 is broader than in Theorem 3.2, yet no convergence rate is provided for Theorem 3.3.
* (ii) The authors seem to aim to show the superiority of $\tau$-SGA over  $\tau$-GDA. However, by comparing Theorems 3.2 and 3.4, the range of $\tau$ ensuring convergence for asymptotic $\tau$-SGA exceeds that of $\tau$-GDA only if $\| C + \theta BB^\top \| < \| C \|$. Further discussion on practical ways to ensure this condition or examples where it holds would be helpful. Additionally, there is no theoretical counterpart to Theorem 3.3 for $\tau$-SGA. While $\tau$-SGA is proposed to avoid rotational dynamics, this advantage is demonstrated only in numerical results (e.g., Figure 1), not theoretically, leaving theoretical support insufficient.

2. **Unclear Analysis for (Asymptotic) $\tau$-SGA**: 
* (i) In line 327, the asymptotic analysis requires $\theta$ to be of constant order. Why, then, are parameters $\mu$ and $\tau+1$ introduced in Eqs. 12 and 13, and what is their significance?
* (ii) If the authors aim to show the superiority of $\tau$-SGA, Theorem 3.4 alone is insufficient, and Figure 1's simple example is not enough to establish the similarity between $\tau$-SGA and its asymptotic variant. The claim "Theorem 3.4 is valid for $\tau$-SGA" in line 363 lacks rigor. If deriving a theoretical result for $\tau$-SGA is challenging, additional numerical experiments for the asymptotic $\tau$-SGA$ should at least be provided.

questions:
1. In line 277, what is the order of $\gamma^{\cdot}(M)$? Could the authors provide an intuitive explanation of this function?
2. The computation of $\tau$-SGA involves a matrix-vector product. Are the benefits sufficient to justify the additional computational cost?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730780678686

thread_type:
official_review

<thread_object>
creator: reviewer_ftu6

<content>
summary:
This paper studies min-max algorithms to solve zero-sum differential games on Riemannian
manifold

strengths:
No

weaknesses:
This paper does not have any interesting parts. Firstly, the Riemannian optimization is not practical. Furthermore, could you show some practical utilization of your algorithms?

questions:
I think that this manuscript contributes nothing in science expect some hard understanding of mathematical symbols.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730960083353

thread_type:
official_review

<thread_object>
creator: reviewer_bh31

<content>
summary:
Using the concepts of DSE and DNE on Riemannian manifolds, the author derives conditions on the range of τ and learning rate of x to ensure linear convergence of τ-GDA to DSE and DNE.

It introduces a novel algorithm τ-SGA to enhance the convergence of τ-GDA, allowing a broader range of τ for convergence when τ is large, and achieving faster local convergence than τ-GDA.

Applying these insights, the author improves the training of orthogonal Wasserstein GANs. Numerical results show that enhanced convergence of stochastic τ-GDA and τ-SGA can improve the learned generator on simple benchmarks.

strengths:
This article provides sufficient conditions for the local convergence of τ-GDA and τ-SGA to differential equilibrium on a Riemannian manifold, where the author proves a linear convergence rate of τ-GDA to DSE and DNE, depending on the spectral radius of the Jacobian at equilibrium. THe author introduces τ-SGA on Riemannian manifolds to further improve this rate.

weaknesses:
- Some key terms could benefit from further explanation or intuitive insights. For example, what are the underlying intuitions behind the linear transformations in (9) and (10)?

- It appears that several theorems are extensions of those from the Euclidean case. What are the main differences or key insights that allowed these results to be successfully extended to the Riemannian manifold?

- Given the author's claim of linear convergence rates for the proposed methods, are there any experimental results to support this?

questions:
Question for Theorem 3.1. (Ostrowski Theorem on manifold)

- The author indicates that the theorem is analogous to the theorem in the Euclidean case. Is the Euclidean version of the theorem also based on the spectral radius of a linear transformation similar to (9)? 

- What is the size of the local convergence radius around ( 𝑥*, 𝑦*)? 

- How can one ensure that the initialization lies within this local neighborhood? Does the initialization used in experiments satisfy this requirement? 

- What is the reasoning behind assuming a small spectral radius for 𝐷𝑇* ?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731040583779

thread_type:
official_review

<thread_object>
creator: reviewer_v3po

<content>
summary:
This paper analyzes the local convergence of the deterministic τ-GDA and τ-SGA algorithms to differentiable equilibria in min-max games on Riemannian manifolds. Using the Ostrowski theorem, sufficient conditions on the algorithm hyperparameters (in particular, on the learning ratio τ) are given for linear-rate local convergence to Differentiable Stackelberg Equilibria (DSE) for both τ-GDA and Asymptotic τ-SGA (an approximation to τ-SGA that is amenable to easier analysis). Local convergence to Differentiable Nash Equilibria (DNE) is also given for τ-GDA.

This paper marks the first time that τ-SGA has been written for Riemannian manifolds, and the authors put it forth as an algorithm that can solve the problem of τ-GDA’s slow convergence rate in certain settings. Both theory and example are given to show that Asymptotic τ-SGA can be locally convergent at a smaller τ compared to τ-GDA, and with a faster rate; moreover, in Euclidean space the rate guarantee outperforms that of the extra-gradient method, which has been used to overcome the slow convergence rate of τ-GDA but is costly in Riemannian space. Experiments also show that the gap between Asymptotic τ-SGA and the true τ-SGA is small, so the theoretical results should also hold for the more natural τ-SGA.

Finally, the paper applies stochastic τ-GDA and τ-SGA to train orthogonal Wasserstein GANs with a discriminator parametrized in the Stiefel manifold. It is shown that even with good initialization a small τ may cause τ-GDA to oscillate with high amplitude, but that τ-SGA can converge even at those small values of τ.

strengths:
Overall, this paper seems like a significant algorithmic contribution with sound theoretical grounding. The authors extend known, tight local convergence results for τ-GDA from Euclidean space to Riemannian manifolds and introduce τ-SGA to the context of Riemannian manifolds. Both in theory and practice τ-SGA is shown convincingly to be able to achieve (local convergence) in settings where τ-GDA cannot, highlighting its usefulness in this setting of Riemannian min-max problems with minimal assumptions (just f twice continuously differentiable).

The paper is generally well written. The sections on differentiable equilibria, algorithms, and local convergence read especially well, with much background and explanation given to readers. Motivations and the context of prior work and clearly written.

weaknesses:
While it is clearly stated in the introduction that global convergence is difficult to achieve in this setting and local convergence (to differentiable equilibria) may be all we can get theoretically, it is not clear what these limitations mean, or are expected to mean, in practice. The experiments are set up to show local convergence after good initialization, but it is not clear what the good initialization entails or if τ-SGA can be used when you are not near a DSE. Also maybe some comment could be made about the existence and significance of DSE in the settings provided (e.g., the Wasserstein GANs), and about other methods for doing min-max Riemannian optimization in these setting (e.g., over Steifel manifolds).

I also find the writing of the GAN experiments and their setups/parameters/initialization a bit terse and less clearly written than what comes before, with a few things in particular lacking explanation. I ask some questions about this below.

questions:
From the experiments, it seems like τ-SGA is used as a sort of “last mile” algorithm to guarantee fast convergence after good initialization/pretraining (either via ansatz in the analytical examples of Figure 1 or via τ-GDA for the GANs). Is this a reasonable interpretation of the authors’ proposed use of τ-SGA, and is there any reason that τ-GDA—in particular, alternating τ-GDA—is used to pretrain the GANs?

In Theoerems 3.2 and 3.4, after the main statements there are additional (“furthermore…”) statements for when γ is fixed exactly depending on L_g/L_s. Is this reasonable given that L_g depends on the DSE, which is not known in advance? (Maybe this is not so important, but as it is written I am not sure what the significance of these “furthermore” statements is.)

τ-SGA has an additional hyperparameter θ (or μ) to tune compared to τ-GDA, and in the GAN example of Table 2 a “suitable choice” of θ seems to have been made. Does the value of θ matter much, and how is it chosen?

I am not so familiar with the way “retraction” is used in Section 3.1, though it does not affect much as the algorithms are easily understood. Perhaps some quick definition or source could be given?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731061519224

thread_type:
official_review

<thread_object>
creator: reviewer_lg9l

<content>
summary:
This paper extends the analysis of the local convergence of two-time-scale $\tau$-GDA and $\tau$-SGA methods to the differential Stakelberg equilibrium (DSE) of Euclidean min-max problem to the Riemannian min-max problem. This paper first generalizes the notion of DSE in the Euclidean space to the Riemannian manifold (in Section 2.1), using a local coordinate chart. Then, the authors provide a sufficient condition (in Theorem 3.1) for the fixed point method to have a local linear convergence. Based on Theorem 3.1, this paper shows a specific sufficient condition for the $\tau$-GDA to locally linearly converge to DSE in Theorem 3.2. In addition, the authors generalize $\tau$-SGA for Riemannian min-max problem, which is originally developed to mitigate undesirable rotational dynamics encountered by $\tau$-GDA in the Euclidean space. In the Euclidean space, extragradient (or optimistic gradient) method is widely used to relieve such rotational behavior, but its Riemannian version, named RCEG, is computationally expensive. This paper claims that their $\tau$-SGA equipped with auto-differentiation may have computational benefit over RCEG. Experiments on a toy example and a more realistic Orthogonal WGAN problem empirically confirm this paper's theoretical findings.

strengths:
Existing results on local convergence to DSE and DNE in nonconvex-nonconcave min-max problems in Euclidean space are crucial. Thus, while its extension to Riemannian manifolds may seem straightforward, it is a significant and non-trivial advancement. Although I was not able to check all the details of the proof, the parts I checked looked correct.

weaknesses:
Missing preliminaries for non-experts on Riemannian manifold: For example, adding the definition of Riemannian gradient/Hessian/cross-gradient, the role of local coordinate chart and the relation between $f$ and $\bar{f}$ would help readers to better understand the context.

questions:
- lines 45-47 could be improved to better explain this paper's focus on differential equilibriums (DNE and DSE). This could have been local Nash and local minimax points. Then why differential equilibrium? 
- Table 1 is confusing: What is your focus here? The title should be more specific to make a point. Isn't Nash equilibrium found by Zhang et al. (2023) DNE? This is not clear in the table. Also, your result is local (both in optimality and convergence) while others might be global. I am not sure whether local/global should be discussed in the table, but I am sure that this table needs to be reorganized and rewritten.
- I suggest rewriting Definition 3.1 to make it more explicit that it defines local linear convergence.
- line 276: Were you trying to say that $M$ with eigenvalues with only negative real parts?
- lines 524-525: I don't follow what do you mean here.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper extends the analysis of local convergence for deterministic $\tau$-GDA and $\tau$-SGA algorithms to min-max problems on Riemannian manifolds, generalizing concepts like Differentiable Stackelberg Equilibrium (DSE) and Differentiable Nash Equilibrium (DNE) from Euclidean spaces. Using theoretical tools like Ostrowski's theorem, the authors provide sufficient conditions for local linear convergence of $\tau$-GDA and a faster convergence rate for an asymptotic variant of $\tau$-SGA, which addresses the slow convergence and undesirable rotational dynamics of $\tau$-GDA. Unlike the computationally expensive Riemannian extragradient methods, $\tau$-SGA offers practical advantages with minimal performance gaps between its theoretical and natural forms. Empirical validation includes training orthogonal Wasserstein GANs on the Stiefel manifold, demonstrating $\tau$-SGA's robustness and improved convergence even under challenging parameter settings.

This paper seems like a significant algorithmic contribution with sound theoretical grounding. The authors extend known, tight local convergence results for τ-GDA from Euclidean space to Riemannian manifolds and introduce τ-SGA to the context of Riemannian manifolds. Existing results on local convergence to DSE and DNE in nonconvex-nonconcave min-max problems in Euclidean space are crucial. Thus, while its extension to Riemannian manifolds may seem straightforward, it is a significant and non-trivial advancement. Both in theory and practice τ-SGA is shown convincingly to be able to achieve (local convergence) in settings where τ-GDA cannot, highlighting its usefulness in this setting of Riemannian min-max problems with minimal assumptions (just f twice continuously differentiable).

The paper is generally well written. The sections on differentiable equilibria, algorithms, and local convergence read especially well, with much background and explanation given to readers. Motivations and the context of prior work and clearly written.