Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors explore the complexity of min-max problems defined on Riemannian manifolds. They prove, among others, linear convergence of the last iterate of RCEG, a result that was unknown in the literature, and explore stochastic and nonsmooth variants.
strengths_and_weaknesses: The paper addresses an interesting topic. It is overall well-written, though there remains typos and inaccuracies at some places in the presentation. I am not very comfortable with the content and presentation of the results. Most of the paper is devoted to a presentation of the underlying assumptions of the convergence analysis, while those are already extensively presented in [1].  On the other hand, very little intuition is given to the new findings compared with [1] (understanding why the convergence guarantees for RCEG of this paper are stronger than in [1] would require to read in detail the appendix). 
Given the fact that most of pages 1-2, 4-5 are already in [1], I would advise the authors to significantly shrink those sections, refering where applicable to [1], and give much more intuition on their main contributions:
- how do the authors achieve stronger guarantees than in [1] for RCEG?
- what are the changes needed to extend the proof to the sochastic setting?
- what are the changes needed to consider the nonsmooth setting?
questions: - Which nonconvex constraints do appear in GANs? (first paragraph of the introduction)
- on p. 2, line 77-78, "for the non-convex non-concave setting, deriving ...for the convex case". What is convex here?
- please add the definition of the acronyms in the table in Section 1.1
- how do you define the diameter of a manifold, in Prop. 2.1? Are you restricting here youselves to a closed manifold?)
- Def. 2.2: shouldn't the second inequality be in the opposite direction?
- I am quite concerned about the unicity of geodesics assumption. In particular, this seems to rule out many manifolds of interest, including those of positive curvature (the sphere, the Stiefel manifold, the orthogonal group). Am I right to understand that this assumption is violated by your experimental section (see eq. 5)?
- How does this unicity assumption interact with your assumption on the sectional curvature, in regard of the previous comment?
- In Thm. 3.1, do kappa_min and kappa_max refer to the curvature of M or of N?

limitations: I do not expect this work to have any societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides an extensive analysis of the Riemannian counterparts of Euclidean optimal first-order methods adapted to the manifold-constrained setting and  proves that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at a linear rate in the geodesically strongly- convex-concave case and extents it to the stochastic or non-smooth case.Some experiments have verified theoretical results.


strengths_and_weaknesses: Overall, I think the paper is solid and novel enough. The authors prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at a linear rate in the geodesically strongly convex-concave case, matching the Euclidean result. Their results also extend to the stochastic or non-smooth case where RCEG and Riemanian gradient ascent descent (RGDA) achieve near-optimal convergence rates up to factors depending on curvature of the manifold.
questions: 1. The first figure in Section 3 is not very clear and lacks labels;
2. In the experimental section, It would be good if there were more comparison algorithms.
limitations: 1. The first figure in Section 3 is not very clear and lacks labels;
2. In the experimental section, It would be good if there were more comparison algorithms.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper analyzes first-order methods for min-max optimization on Riemannian manifolds. Problems of this form arise in a variety of settings, including optimal transport and adversarial learning. The main focus of the paper is on investigating the existence of a fundamental "performance gap" between Riemannian and Euclidean approaches for min-max optimization. The authors show that a Riemannian method (RCEG) matches the performance of its Euclidean counterpart in the geodesically strongly convex-concave case.
strengths_and_weaknesses: *Strength*
The paper addresses an important problem, which arises frequently in machine learning applications and is therefore very timely. The paper carefully reviews the existing literature and does a good job of explaining its contribution, especially with respect to Zhang et al. (2022), on which it directly builds.

*Weaknesses*
See limitations below.
questions: See limitations.
limitations: 1. Since the paper analyzes potential performance differences of Euclidean and Riemannian methods, it would have been good to compare against Euclidean methods in the experiments. 
2. The theory is limited to the geodesically strongly convex-concave case. How restrictive is this? E.g., among the examples listed in the introductions, to which does the theory apply? Can you comment on any challenges in extending the present theory to less restrictive cases, which are understood in the Euclidean setting?
3. In sec. 4, l. 300, what does "appears to be locally geodesically strongly convex-concave" mean? Can this be shown?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors show that a previous algorithm from [1] (Sion’s theorem and algorithms, Zhang et al) achieves linear convergence rate for the last iterate in the (geodesically) strongly convex-strongly concave settings.

They also prove some guarantees under the assumption of a noisy gradient oracle, though of course a dependence on $1/\epsilon$ appears, as well as in the non-strongly convex case and non-smooth cases. These guarantees appear to match the best Euclidean guarantees apart from curvature parameters.
strengths_and_weaknesses: The strength of this paper is (1) the detailed description of the performance of Riemannian extragradient in various scenarios. The novel technical accomplishment is the proof of linear convergence rate in the strongly convex, strongly concave setting. The writing and clarity is high quality. It makes another recent result in [1], a  generalization of Sion's min-max theorem to the uniquely geodesic setting, more constructive.

I do take issue with the lack of examples mentioned for interesting Riemannian convex-convave problems. I think the reader has to take this on faith a bit. The main experimental example, robust PCA, needs Riemannian geometry to even formulate it. It would be nice to have a more natural example. 

As one of the main strengths in the paper appears to be a proof which had heretofore eluded the community, it would help to mention what caused problems before and how the new proof overcomes those issues. Because I didn't find much discussion on this I have no way of knowing if the result is believable.
questions: 1. Not sure if it's just me, but the figure in 3.1 is unreadable.
2. Can you give a reference for where RPCA is defined and used? 
3. It might be appropriate to mention that in curvature -1, the condition number of g-convex functions has to depend on the radius and so sometimes the linear convergence rate is vacuous.
4. How were difficulties in previous upper bound proof attempts for the linear convergence guarantee overcome? 
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper provides optimal convergence guarantees for the Riemannian corrected extragradient method (proposed in [1]) for geodesically strongly convex-strongly concave min-max optimization problems. A stochastic version of the algorithm is also discussed.
strengths_and_weaknesses: Strengths: The paper is very well-written in all its aspects and the technical work seems solid. The analysis answers a conjecture raised in [1], for an algorithm that is a reasonable adaptation of a similar Euclidean algorithm. Experimental results are also presented.

Weaknesses: Some parts of the proofs are hard to follow. Maybe this paper is a bit packed mathematically for the neurips community. My most serious concern is that the set of applications of geodesic strong convexity-strong concavity is exceptionally poor. Namely, the authors mention the problem of robust PCA as an application of their theoretical analysis, but this analysis cannot be applied to this problem because it is only *locally* strongly convex-strongly concave. This can have tremendous difference from *global* strong convexity-strong concavity, because one needs to ensure that an iterate of the algorithm remains in the set that the algorithm satisfies this property. This is usually impossible when the analysis is done for function values (Theorem 3.3) and for stochastic algorithms in general (Theorems 3.2,3.3). Even when the analysis is done for distances like in Theorem 3.1, one needs to ensure that $d_M(x_t,x^*) \leq d_M(x_0,x^*)$ and $d_N(y_t,y^*) \leq d_N(y_0,y^*)$ for all $t$. This is not clear to me because the contraction is only for the sum $d^2_M(x_t,x^*)+d^2_N(y_t,y^*)$. Thus, the paper is left without a concrete application of the theoretical analysis and this is the only reason I give a rejection score, which I would be happy to raise either if the authors can fix at least the analysis of their deterministic algorithm to cover also *local* strong convexity-strong concavity or can if they suggest a different important optimization problem that is actually *globally* strongly convex-strongly concave.


questions: My main question is on the applicability of the analysis as described in the previous section.

Also, I think the second part of Definition 2.2 since you have again convexity instead of concavity.
limitations: The authors discuss the limitations of their work. There is no direct societal impact.
review_title: null

Meta-review: metareview: The paper analyzes the performance of a few of the recent algorithms for min-max optimization over manifolds. The analysis is extensive and is interesting in its own respect. In the final version, please address the comments of the reviewers.


confidence: Certain
Decision: Accept