Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper studies optimistic gradient descent ascent (OGDA) and optimistic multiplicative weights update (OMWU) in the constrained convex-concave min-max optimization setting. For OMWU, under the assumption of unique minimum, the authors show linear rate of convergence of bilinear minmax problems over simplices. For OGDA in constrained setting, the authors show linear convergence under some error bound conditions which the authors name as saddle-point restricted secant inequality (SPRCI). Moreover, the authors prove $1/\sqrt{T}$ rate for the average of duality gap for OGDA.

Even though the results of the paper can be significant, the authors fail to mention important related works, therefore it is not clear how the contributions of the paper adds onto what is already known in these related works. Below I will list my concerns:

OMWU:
- For OMWU, the authors state that even though the analysis might look similar to Daskalakis&Panaegas, the new analysis is *very* different. Here, I would like to see more explanations. What are the different tools that the authors use to improve Daskalakis&Panaegas? I do not find it convincing when I see subjective adjectives such as "very different" analysis: I would like to see what exactly the contribution of the analysis on top of Daskalakis&Panaegas. It does not need to be very low-level details, but I would like to see some high level discussion of the novelty of the techniques here. 

Looking at the analysis of Thm 3, I see that the authors use some local arguments depending on $T_0$ to get a term $\alpha^{T_0 - t}$ for some $\alpha$. Then the authors make $\alpha^{T_0}$ to the constant. Here, my concern is that a constant exponential in $T_0$ might be too large. For example, how does this rate compare to standard sublinear rate of OMWU? If the constants of the linear rate are very pessimistic, then both in theory and in practice, sublinear rate might be better.

OGDA:
- I think the main reference the authors are missing is FORB by [1]. FORB is known to be equivalent to OGDA in the unconstrained setting. Therefore, it can be seen as a specific version of OGDA in constrained case. How does the constrained OGDA the authors propose in this paper differ from FORB which is already given in constrained setting?

For instance, FORB gets $1/T$ rate [2] for the average of duality gap, whereas this paper gets $1/\sqrt{T}$. Why does the rate degrade in this paper? It is well known for VIs that the average of duality gap has $1/T$ rate as in [2], then one can use convexity to convert this rate to a rate on the averaged iterate. It is worth noting that the rate referred in this paper due to Golowich et al., is on the last iterate, therefore not comparable to this paper. It is known in Golowich et al., and earlier due to [7] that $1/\sqrt{T}$ is essentially tight for last iterate. However, for the averaged duality gap this paper considers this is not the case, and $1/T$ is known to be obtained with averaging ([2] and many others).

- There exist a big literature on error bound conditions [6], which I suspect to be related to SPRSI proposed in this paper. I think the authors need to add the related work on metric subregularity (MS) and compare their results with the algorithms utilizing metric subregularity for linear convergence [3, 4, 5]. Moreover, I think it is necessary to see the relation of SPRSI with metric subregularity. For example, it is well known that MS holds for piecewise linear quadratic functions which include the setting of bilinear games over polytopes that the authors consider. Moreover, MS also holds for strongly convex strongly concave games. I suspect using MS in FORB analysis can directly yield similar linear convergence rates to this paper. Then, what is the advantage of SPRSI and the new constrained OGDA compared to FORB?

Moreover, since the contribution of the paper is on linear convergence, how tight is the rate, and how good the condition SPRSI for detecting structure? For example, what happens when the problem is strongly convex-concave, how is the rate derived in this paper, compare to linear rate of [1] and others on similar algorithms? Similarly, can the authors compute the linear rate explicitly for some toy problems and then compare with the performance in practice to see tightness?

========= after discussion with authors ========
During the discussion phase, the authors addressed my concerns and improved their results. Therefore I increase my score to reflect this.

[1] Malitsky, Yura, and Matthew K. Tam. "A forward-backward splitting method for monotone inclusions without cocoercivity." SIAM Journal on Optimization 30.2 (2020): 1451-1472.

[2] Böhm, Axel, et al. "Two steps at a time--taking GAN training in stride with Tseng's method." arXiv preprint arXiv:2006.09033 (2020).

[3] Latafat, Puya, Nikolaos M. Freris, and Panagiotis Patrinos. "A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization." arXiv preprint arXiv:1706.02882 (2017).

[4] Liang, Jingwei, Jalal Fadili, and Gabriel Peyré. "Convergence rates with inexact non-expansive operators." Mathematical Programming 159.1-2 (2016): 403-434.

[5] Alacaoglu, Ahmet, Olivier Fercoq, and Volkan Cevher. "On the convergence of stochastic primal-dual hybrid gradient." arXiv preprint arXiv:1911.00799 (2019).

[6] Rockafellar, R. Tyrrell, and Roger J-B. Wets. Variational analysis. Vol. 317. Springer Science & Business Media, 2009.

[7] Davis, Damek, and Wotao Yin. "Convergence rate analysis of several splitting schemes." Splitting methods in communication, imaging, science, and engineering. Springer, Cham, 2016. 115-163.
review_title: Interesting results, however key comparisons with related works are missing, making it difficult to gauge the significance

final_score: rating: 7: Good paper, accept
review_content: This paper studies the performance of optimistic multiplicative weights update (OMWU) and optimistic gradient descent (OGDA) in constrained zero-sum settings and provide linear convergence rate guarantees. For OMWU in bilinear games over the simplex, they show that when the equilibrium is unique, linear last-iterate convergence is achievable with a constant learning rate. In the case of projected OGDA algorithm, they introduce a sufficient condition under which it convergence fast with a constant learning learning rate. They show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption.

This is overall a nice paper that extends and improves our understanding about optimistic versions of OMWU and OGDA especially in constrained bilinear zero-sum games. The paper does a good job at explaining technical improvements over prior results in the area and particularly the works by Daskalakis and Panageas and Hsieh et al. 

The experimental section could be slightly improved. For example in the case of OMWU it is seems hard to detect whether the error curve is best fit by an exponential even after the initial slower phase. It would be very interesting to see numerical estimation of the base of these exponents and see how close they match their theoretical bounds. Also the question about OMWU with a continuum of equilibria could be explored experimentally as well. Do experiments support fast convergence in this case? 

Overall, this is a nice paper and I recommend acceptance.

Related references: 
In terms of fast convergence in bilinear zero-sum games with fixed learning rates
[1] Proves that even with large fixed learning rates the average duality gap of alternating GDA in unconstrained bilinear zero-sum games converges to zero at a rate of O(1/t). [2] proves O(1/sqr{t}) convergence under arbitrarily large learning rates for a variant of GDA (Follow the regularized leader with Euclidean regularizer) in small constrained bilinear zero-sum games, despite divergence of the day-to-day behavior to the boundary.

[3, 4] OMWU is shown to stabilize fast in bilinear constrained zero-sum games in a different sense by arguing exponentially fast shrinking of the volume of sets of initial conditions in the dual/payoff space. 
 

[1] Bailey et al. Finite Regret and Cycles with Fixed StepSize via Alternating Gradient Descent-Ascent. COLT 2020.
[2]  Bailey, Piliouras. Fast and Furious learning in zero-sum games: vanishing regret with non-vanishing step sizes. Advances in Neural Information Processing Systems. 2019.
[3] Cheung, Piliouras. Chaos, Extremism and Optimism: Volume Analysis of Learning in Games. arXiv preprint arXiv:2005.13996 (2020).

review_title: Good paper, improves our understanding of OMWU, OGDA in zero-sum games

final_score: rating: 7: Good paper, accept
review_content: This paper studies Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for solving minimax problem. For OMWU, it shows that if the equilibrium is unique and the objective is x^Ty, then a constant linear stepsize results in a linear convergence for the last iterate. For OGDA, it shows that, with constant stepsize, the average duality gap converges with slow rate. Moreover, it shows that under an extra condition, the last iterate converges linearly as well.

***
Strength: The paper is solid in theorem and the proof seems correct as far as I checked. It is in a good writing and highly readable. The convergence is interesting and novel in the sense that it shows explicit linear rate with constant stepsize.

***
Concern: My main concern is about the SP-RSI. Considering it has not beed discussed in other papers, it would be better to provide a more general nonlinear objective class (besides bilinear games on polytopes) that satisfies this condition. Moreover, the role of constraint set in this paper is not clear to me. Is the constraint sets X and Y essential to the problem? What's the difficulty in constrained minimax over unconstrained minimax?

***
For future improvement, I suggest to discuss SP-RSI more deeply, since this condition is added to overcome the intermediate difficulty in technical proof. Also the authors can be more clear about the role of constraint sets. If noting special, it'd better not emphasize the setting is constrained.

***
During rebuttal: I thank the toy examples provided by the authors. 

review_title: Recommendation to Accept

final_score: rating: 6: Marginally above acceptance threshold
review_content: In this paper, the authors consider the convergence of optimistic gradient for constrained saddle-point optimization. Saddle-point problems are very popular in the ML community and lead to non-trivial extensions of the usual (projected) gradient methods. Typically, first-order methods for saddle-point problems are based on the Extra-Gradient algorithm; however, this methods implies two oracle calls per iterations which is undesirable in game theoretical contexts. Fortunately, single call variants have been introduced in the literature to overcome this drawback. Although they all resort to the same algorithm/principle when there are no constraints; single call variants are different in the constrained case. Here, the authors consider the Optimistic Gradient variant (sometimes also called Past-Extra Gradient) and show last-iterate convergence rates under more general constrained case than the previous literature.

The paper offers a strict improvement over known results of the literature. It can definitively interesting for specialists and may lead to interesting developments. More precisely, they replace the "locally strongly convex + sufficiently small stepsize" condition of e.g. [Hsieh2019, Th. 2] to "introduced SP-RSI +  near-usual stepsize" and still manage to show linear convergence. While this is interesting, in the present version, the presentation of the paper fails to meet the expectations for a paper that tackles a very specific technical point by not being pedagogical and clear enough. I am rather convinced of the interest of the approach regarding the linear convergence with multiple minimizers but the point 2 and 3 page 8 (global vs local and stepsize) are not completely conving since they may be related to the implicit unit diameter of X.

All in all, while the paper have merits, the lower quality of presentation and discussion of the results on this very technical matter makes me lean towards rejection.

Concerns:
* In the introduction (typically the second paragraph), I feel that the "oracle call difference" between (EG) and (OGDA) is not clear and may confuse an inexperienced reader. 
* Since the authors base their analysis on a template inequality (Lemma 1); what would happen for other single call variants such as the reflected gradient (see Chambolle and Pock " A first-order primal-dual algorithm for convex problems withapplications to imaging") or "optimistic" (Daskalakis et al. "Training GANs with optimism")? 
* A drawback of the paper is the lack of a conducting thread along the paper. After the first  3 sections, we go from "Matrix games with OMWU" to "general case + RSI w/ OGDA" then back to matrix games  w/ OGDA. If the authors want to point out the condition RSI and their analysis then this should go first and maybe a section for matrix games w/ two subsections 1) OGDA 2) OMWU would be interesting. In addition, would it be possible to derive a similar RSI w/ KL divergences to get similar results for OMWU?
* [SP-RSI 1] seems taylored for matrix games, I have trouble to see when else this could be applied (or when beta can be > 0). Theorem 9 should be more "explained" I guess.
* [SP-RSI 2] looks like a generalization of strong convexity. What bothers me is that i) the fact that F is monotonous should be recalled here otherwise this might be confusing; ii) since we are in the smooth case, this only works if \|z-z*\|<=1 i.e. assumption 1 (note here that the assumptions are defined but not actually mentioned in the results). Would the constants change is \|z-z'\|>1 ?  
* Is there a direct link between these conditions and Kurdyka/Lojasiewicz-type rule. This is especially striking since Th.8 and more precisely appendix C share similarities with the Theorem 5 of "On the convergence of the proximal algorithm for nonsmooth functions involving analytic features" by Attouch and Bolte.

Minor comments/typos:
* From what I get, the main result concerns: Saddle-point + Constraints + Non-strongly convex/usual stepsize; this should be more explicit in the introduction/Sec. 2, maybe with a table recalling related results (eg. the unconstrained case).
* (OGDA) and (OMWU) are basically the same algorithm with two different metrics (as stated in Sec. 3), it can thus be troubling to see them opposed in the first two sections without this precision.
* I am not sure that the 1/sqrt(T) average duality gap rate should be put forward in the intro since it may blur the whole message. 
* Average-iterate cv: another reason not to do averaging is the lack of guarantee for non-convex losses.
* I find the notation "dist" for "\|x-Pi(x)\|^2" troubling due to the square. Using dist for the same quantity without the square (or renaming dist^2) would be less confusing for me (typically in Lemma 1).
* In "Other notations", in supp(u), I think u is supposed to be in the positive orthant.
* OGDA seems actually referred to as "Past extra-gradient" in [Hsieh2019], "single call" is just the class of variants of EG w/ one call per step.
* In the matrix game at the bottom of p4: is it standard to take entries in [-1,1] or is it just to have L=1? The equilibrium may not be unique without conditions here.
* The top of page 5 is nice to read and explains well the general reasoning without having to specifically look into the tedious proof in appendix. However, in Theorem 3 the result is not so explicit: C_4 could be made explicit since it is not so complicated as I see from the appendix.
* I found the proofs rather hard to follow e.g. the proof of Theorem 5 is broken down several interdependent claims but the lack of text make them hard to digest.

review_title: Review

Meta-review: The authors propose to provide fast convergence results for the OGDA and OMWU algorithms based on a reinterpretation of the metric subregularity in the saddle point problem setting. During the rebuttal period, the paper improved significantly, not only due to the diligence of the authors but also due to reactive reviewers that provided extremely constructive comments. The technical developments are quite nice: Lemma 2 allows constant step-size parameter as compared to Daskalakis and Panageas, followed by Theorem 3, which establishes the first linear rate under the saddle point metric subregularity. The numerical demonstrations are also helpful in driving the point home. Although it is not surprising that the shape of the polytope matters, it is still impactful to see the linear rate. 


ps. The authors should consider including a related work comparison to the reflected FB algorithm in [1] since it reduces to the FoRB and it also provides convergence analysis for the sequence in the general monotone inclusions. 

[1] Cevher and Vu, "A reflected forward-backward splitting method for monotone inclusions involving Lipschitzian operators,'' 
https://arxiv.org/pdf/1908.05912.pdf
Decision: Accept (Poster)