Linear Last-iterate Convergence in Constrained Saddle-point Optimization
Authors: Chen-Yu Wei
Chung-Wei Lee
Mengxiao Zhang
Haipeng Luo
Venue: ICLR 2021 Poster (2021)
Keywords: Saddle-point Optimization
Optimistic Mirror Decent
Optimistic Gradient Descent Ascent
Optimistic Multiplicative Weights Update
Last-iterate Convergence
Game Theory

Abstract: Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for saddle-point optimization have received growing attention due to their favorable last-iterate convergence. However, their behaviors for simple bilinear games over the probability simplex are still not fully understood --- previous analysis lacks explicit convergence rates, only applies to an exponentially small learning rate, or requires additional assumptions such as the uniqueness of the optimal solution.

In this work, we significantly expand the understanding of last-iterate convergence for OGDA and OMWU in the constrained setting. Specifically, for OMWU in bilinear games over the simplex, we show that when the equilibrium is unique, linear last-iterate convergence is achievable with a constant learning rate, which improves the result of (Daskalakis & Panageas, 2019) under the same assumption. We then significantly extend the results to more general objectives and feasible sets for the projected OGDA algorithm, by introducing a sufficient condition under which OGDA exhibits concrete last-iterate convergence rates with a constant learning rate. We show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption. Our condition also holds for strongly-convex-strongly-concave functions, recovering the result of (Hsieh et al., 2019). Finally, we provide experimental results to further support our theory. 

Published as a conference paper at ICLR 2021
LINEAR LAST-ITERATE CONVERGENCE STRAINED SADILE-POINT OPTIMIZATION
IN CON-
Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo University of Southern California (chenyu. wei, leechung, mengxi ao. zhang, ha penge @ussc edu
ABSTRACT
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for saddle-point optimization have received growing attention due to their favorable last-iterate convergence. However, their behaviors for simple bilinear games over the probability simplex are still not fully under- stood - previous analysis lacks explicit convergence rates, only applies to an exponentially small learning rate, or requires additional assumptions such as the uniqueness of the optimal solution.
In this work, we significantly expand the understanding of last-iterate convergence for OGDA and OMWU in the constrained setting. Specifically, for OMWU in bilinear games over the simplex, we show that when the equilibrium is unique, lin- ear last-iterate convergence is achieved with a learning rate whose value is set a universal constant, improving the result of (Daskalakis & Panageas, 2019b) un- der the same assumption. We then significantly extend the results to more general objectives and feasible sets for the projected OGDA algorithm, by introducing a sufficient condition under which OGDA exhibits concrete last-iterate convergence rates with constant learning rate whose value only depends on the smoothness of the objective function. We show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption. Our condition also holds for atrongl--convex-stoom concave functions, recovering the result of (Hsieh et al., 2019). Finally, pro- vide experimental results to further support our theory.
INTRODUCTION
Saddle-point optimization in the form of mine maxy f(x, y) dates back to (Neumann, 1928), where the celebrated minimax theorem was discovered. Due to advances Generative Adversarial Net- works (GANs) (Goodfellow et al., 2014) (which itself is saddle-point problem), the question of how to find good approximation of the saddle point, especially via an efficient iterative algorithm, has recently gained significant research interest. Simple algorithms such Gradient Descent Ascent (GDA) and Multplicatiive Weights Update (MWU) are known to cycle and fail to converge even in simple bilinear cases (see e.g., (Bailey & Piliouras. 2018) and (Cheung & Piliouras, 2019)).
Many recent works consider resolving this issue via simple modifications of standard algorithms, usually in the form of some extra gradient descent/ascent steps. This includes ods (EG) (Liang & Stokes, 2019; Mokhtari et al., 2020b), Optimistic Gradient Descent Ascent (OGDA) (Daskalakis al., 2018; Gidel et al., 2019 Mertikopoulos et al., 2019). Optimistic Mul- tiplicative Weights Update (OMWU) (Daskalakis & Panageas, 2019b; Lei et al., 2021), and others. In particular, OGDA and OMWU are suitable for the repeated game setting where two players repeatedly propose 2; and y/: and receive only fæf( yt) and V, Vyf y:) respectively feed- back, with the goal of converging to a saddle point or equivalently Nash equilibrium using game theory terminology. One notable benefit of OGDA and OMWU is that they are also no-regret al- gorithms with important applications in online learning, especially when playing against adversarial opponents (Chiang et al., 2012; Rakhlin & Sridharan, 2013).
meth-
Despite considerable progress, especially those for the unconstrained setting, the behavior of these algorithms for the constrained setting, where and y are restricted to closed convex sets X' and

---

Published as a conference paper at ICLR 2021
Y' respectively, is still not fully understood. This is even true when f is a bilinear function and X' and y/ are simplex, known as the classic two-player zero-sum games in normal form. or simply matrix games. Indeed, existing convergence results the last iterate of OGDA or OMWU for matrix games are unsatisfactory - they lack explicit convergence rates (Popov, 1980; Mertikopou- los al., 2019), only apply exponentially small learning rate thus not reflecting the behavior of the algorithms in practice (Daskalakis & Panageas, 2019b), or require additional conditions such as uniqueness of the equilibrium or a good initialization (Daskalakis & Panageas, 2019b).
Motivated by this fact, in this work, we first improve the last-iterate convergence result of OMWU for matrix games. Under the same unique equilibrium assumption as made by Daskalakis & Panageas (2019b), we show linear convergence with a concrete rate in terms of the Kullback-Leible divergence between the last iterate and the equilibrium, using a learning rate whose value set to a universal constant.
We then significantly extend our results and consider OGDA for general constrained and smooth convex-concave saddle-point problems, without the uniqueness assumption. Specifically, we start with proving average duality gap convergence of OGDA at the rate of (11/VT) af- ter T iterations. Then, to obtain a more favorable last-iterate convergence terms of the dis- tance to the set of equilibria, we propose a general sufficient condition on N. and f. called Saddle-Poid Metric Subregularity (SP-MS), under which we prove concrete last-iterate conver- gence rates, all with constant learning rate and without further assumptions.
Our last-iterate convergence results of OGDA greatly generalize that of (Hsieh et al., 2019, The- orem 2), which itself is consolidated version of results from several earlier works. The key im- plication of our new results is that, by showing that matrix games satisfy our SP-MS condition, we provide by far the most general last-iterate guarantee with linear convergence for this problem ing OGDA, Compared to that of OMWU, the convergence result of OGDA holds more generally even when there are multiple equilibria.
More generally, the same linear last-iterate convergence holds for any bilinear games over polytopes since they also satisfy the SP-MS condition as we show. To complement this result, we construct an example of a bilinear game with a non-poloyee non-polytope feasible set where OGDA provably does not ensure linear convergence, indicating that the shape of the feasible set matters.
Finally, we also provide experimental results to support our theory. In particular, we observe that OGDA generally converges faster than OMWU for matrix games, despite the facts that both prov- ably converge exponentially fast and that OM OMUU is often considered more favorable compared to OGDA when the feasible set is the simplex.
2 RELATED WORK
Average-iterate convergence. While showing last-iterate convergence has been challenging task, it is well-known that the sverage-iterate of many standard algorithms such as GDA and MWU enjoys a converging duality gap at the rate of O(//VT) (Freund & Schapire, 1999). A line of works show that the rate can be improved to (1/T)) using the "optimistic" version of these algorithms such as OGDA and OMWU (Rakhlin & Sridharan, 2013; Daskalakis et al., 2015; Syrgkanis et al., 2015). For tasks such training GANs, however, average-iterate convergence is unsatisfactory since averaging large neural networks is usually prohibited.
Extra-Gradient (EG) algorithms. The saddle-point problem fits into the more general variational inequality framework (Harker & Pang, 1990). A classic algorithm for variational inequalities is EG, first introduced in (Korpelevich, 1976). Tseng (1995) is the first to show last-iterate convergence problems. Recent
for EG in various settings such bilinear or works significantly expand the understanding of EG and its variants for unconstrained bilinear prob- coweeeesttoooollyyyoooooo
lems (Liang& & Stokes, 2019), unconstrained et al., 2020b), and more (Zhang et al., 2019; Lin et al., 2020; Golowich et al., 2020b).
problems (Mokhtari
The original EG is not applicable
repeated game setting where only one gradient evaluation is possible in each iteration. Moreover, unlike OGDA and OMWU, EG is shown to have linear regret against adversarial opponents, and thus it is not no-regret learning algorithm (Bowling, 2005;
2

---

Published as a conference paper at ICLR 2021
Golowich et al., 2020a). However, there "single-call variants" of EG that address these issues. In fact, some of these versions coincide with the OGDA algorithm under different names such as modified Artow-Hurwic method (Popov, 1980) and "extrapolation from the past" (Gidel et al., 2019). Apart from OGDA, other single-call variants of EG include Reflected Gradient (Malitsky, 2015; Cui & Shanbhag, 2016; Malitsky & Tam) and Optimistic Gradient (Daskalakis et al., 2018; Mokhtari et al., 2020a). These variants are all equivalent in the unconstrained setting but differ in the constrained setting. To the best of our knowledge, none of the existing results for any single-call variant of EG covers the constrained bilinear case (which is one of our key contributions).
Error Bounds and Metric Subregularity To derive linear convergence for variational inequality problems, error bound method is a commonly used technique (Pang, 1997; Luo & Tseng, 1993). For example, it is a standard approach to studying the last-iterate convergence of EG algorithms (Tseng, 1995; Hsieh et al., 2020; Azizian et al., 2020). An error bound method is associated with an error function that gives every point in the feasible set a measure of sub-optimality that is lower bounded by the distance of the point to the optimal set up to some problem dependent constant. If such a error function exists, linear convergence can be obtained. The choice of the error function depends on the feasible region, the objection function, and the algorithm. Common error functions include natural residual functions (lusem et al., 2017; Malitsky, 2019) and gap functions (Larsson & Patriksson, 1994; Solodov & Tseng, 2000; Chen et al., 2017). Our method to derive the last-iterate convergence for OGDA can also be viewed as an error bound method.
Metric subregularity is another important concept derive linear convergence via some Lipschitz behavior of a set-valued operator (Leventhal, 2009; Liang et al., 2016; Alacaoglu et al., 2019; Latafat al., 2019). Metric subregularity is closely related error bound methods (Kruger, 2015). In fact, as we prove in Appendix F, one special case of our condition SP-MS (that allows us to show linear convergence) is equivalent metric subregularity of an operator defined in terms of the normal cone of the fcasible set and the gradient of the objective. This is also the reason why we call our condition Saddle-Point Metric Subregularity. Although metric subregularity has been extensively used in the literature, to the best of our knowledge, our work is the first to use this condition to analyze OGDA.
OGDA and OMWU. Recently, last-iterate convergence for OGDA has been proven in vari- ous settings such as convex-concave problems (Daskalakis et al.. 2018), unconstrained bilinear problems (Daskalakis & Panageas, 2018; Liang & Stokes, 2019), sroongly-covve--ttee -troogly problems (Mokhtari et al., 2020b), and others (e.g. (Mertikopoulos et al., 2019))-
However, the behavior of OGDA and OMWU for the constrained bilinear case, or even the special case of classic matrix games, appears to be much more mysterious and less understood. Cheung & Piliouras (2020) provide an alternative view on the convergence behavior of OMWU by studying volume contraction in the dual space. Daskalakis & Panageas (2019b) show last-iterate convergence of OMWU for matrix games under a uniqueness assumption and without concrete rate, Although it is implicitly suggested in (Daskalakis & Panageas, 201 2019b;a) that a rate (1/T1/99) is possible, it is still not clear how to choose the learning rate appropriately from their analysis. As mentioned, our results for OMWU significantly improve theirs, with a clean linear convergence rate using a constant learning rate under the same uniqueness assumption, while our results for OGDA further remove the uniqueness assumption.
NOTATIONS AND PRELIMINARIES
We consider the following constrained saddle-point problem: mingex maXyey f(x, y), where X' and y are closed convex sets, and f is a continuous differentiable function that is convex in z for any fixed y and concave in y for any fixed x. By the celebrated minimax theorem (Neumann, 1928), we have min max,eyy f(z, y) = max,ey m f(x y).
The set of minimax optimal strategy is denoted by X' argmin maxyey f(x, y). and the set of maximin optimal strategy is denoted by ) = argmax Dey minzex f(Ø, y). It is well-known that X and y' are convex, and any pair (x", y²) E X x y" is a Nash equilibrium satisfying f("", y) S f(=", yy) < f(.,y') for any (z,y) E X y.
For notational convenience, we define Z = X x y and similarly Z' = X x y" For a point (x. y) E Z, we further define f(z) =f fax y) and F(z) (V=I(x, (x,y), -...Vy/(ee Vyl(a,y)) y)).
3

---

Published as a conference paper at ICLR 2021
Our goal is to find point 2 that is close to the set of Nash equilibria 2", and con- sider three ways of measuring the closeness. The first one is the duality gap, defined as (z(2)= = myxy'ey f(x,
min f(x', .y), which is always non-negative since m ey f(x,zy)= 2
f(x,)) y) 2 ein y(a'yy).
The second one is the distance between and 2'. Speccfiiallyy, for any closed set A. we define the projection operator A as (a) = argmin a' E.A ||a - a'll (throughout this work || represents L2 norm). The squared distance between and Z" is then defined as dist?(z. (2,2*) = || - 1I.. (x)]l
yy) is The third one is only for the case when X' and y are probability simplices, and x" (x", (x")y")
the unique equilibrium. In this case, we use the sum of Kullback-Leibler divergence KL(x"* x)) + KL y) to measure the closeness between 2 = (az, y) and z", where KL, x²) E ti In ai xs"
With slight abuse of notation, use KL(z, x') to denote (L(xxx') + (3).y'')
Other notations.
We denote the (d - 1)-dimensional probability simplex as Aa = {u E R4 : S u, 1}. For convex function t/. the corresponding Bregman divergence is defined as (u = (1)) (V)))()) u v- If şi is y-strongly convex in a domain, then D& v) 2 alluu - vll for any u, v in that domain. For u E R", we define supp(u) = {i: u, > 0}.
d
Optimistic Gradient Descent Ascent (OGDA). Starting from an arbitrary point (क), 91) (ro, yo) from Z, OGDA with step size 17 > 0 iteratively computes the following for f 1,
Z₁- = xx @..- - v/ ( 9.)1)))) 1)),
Le41 = Ix ( - 17 (2,,
y: Hy (7. + V (x)))))))))))
Dc+1 l + V (f
Note that there are several slightly different versions of the algorithm in the literature, which differ in the timing of performing the projection. Our version is the same as those in (Chiang al., 2012; Rakhlin& & Sridharan, 2013). It is also referred to as "single-call extra-gradient" in (Hsieh et al., 2019), but it does not belong to the class of "extra-gradient" methods discussed in (Tseng, 1995; Liang& & Stokes, 2019; Golowich et al., 2020b) for example.
Also note that OGDA only requires accessing f via its gradient. In fact, only one gradient at the point (zt, yr) is needed for iteration t. This aspect makes it especially suitable for a repeated game setting, where in each round, one player proposes x, while another player proposes ye. With only the information of the gradient from the environment (Va.(az,, ye) for the first player and V V (xx yt) for the other), both players can execute the algorithm.
Optimistic Multiplicative Weights Update (OMWU). When the feasible sets X' and y are prob- ability simplices as and Ay for some integers M and N, OMWU is another common iterative algorithm to solve the saddle-point problem. For simplicity, we assume that it starts from the uni- form distributions (i) = (æo, yo) = (f# 1x), where 1, is the all-one vector of dimension d. Then OMWU with step size 17 > 0 iteratively computes the following for t 1,2.....
Lt exp( (V az f ( 1))))
Te, exp( -1) (V V (2,, y:)).)
Ft,i E, Thi exp( 1 V /. (0.-1, (0,1, 11))))
Tet1.i =
Tis Σ,
(V ( v:))g)
1 exp(n( V,, a 1));
D0,1 (V y:)):)
Vt.1 Σ, Di, exp(n (V, of (x B (1-1)))))
L(+1. E, Des exp(n (V yf (z,, y)))))
OMWU and OGDA as Optimistic Mirror Descent Ascent. OMWU and OGDA can be viewed as special cases of Optimistic Mirror Descent Ascent. Specifically, let regularizer ((u) denote the negative entropy Σ, ua In u, for the case of OMWU and (half of) the L2 norm square ||2 for the case of OGDA (so that D Du,u,, v) is KL(u, v) and 11lu - v| respectively). Then using the shorthands 2, (I,, 31)) and 2, (#,, ÿ.) and recalling the notation defined earlier:
2 = X x y and F(z) = (V (ær, v). VyJ( y) one can rewrite OMWU/OGDA compactly
as
2: = argmin #e2
mパ F F(z + (z &.)
(I)
2111 argmin {nlz, F(zz)) + (= } #c2
(2)
4

---

Published as a conference paper at ICLR 2021
By the standard regret analysis of Optimistic Mirror Descent, have the following important lemma, which is readily applied to OMWU and OGDA when & is instantiated as the corresponding regularizer. The proof is mostly standard (see e.g., (Rakhlin & Sridharan, 2013, Lemma 1)). For completeness, we include it in Appendix B.
Lemma 1. Consider update rules Eq. (1) and Eq. (2) and define dist 2²) = || x' + lly y Il Suppose that vp satisfies (zp z') 2 (2, (e some p 2 1, and F satisfies (F(z), F(z')) I L'distt(z, for 2 1 with 1 for any E 2 and any 1 12 1, we have
p + = 1. Also, assume that rj S s1.
1 Then
(2.)))) (z. - 2) < (z
(u(2,,241) (ELt,,,, 15 (z 2,) + To D (t
4 CONVERGENCE RESULTS FOR OMWU
In this section, we show that for a two-player zero-sum matrix game with a unique equilibrium, OMWU with constant learning rate converges the equilibrium exponentially fast. The assump- tion and the algorithm are the same as those considered in (Daskalakis & Panageas, 2019b), but our analysis improves theirs in two ways. First, we do not require the learning rate to be exponentially smaller than some problem-dependent quantity. Second, we explicitly provide a linear convergence rate. In Section we further remove the uniqueness assumption and significantly generalize the results by studying OGDA.
Gy for some matrix To show the last-iterate convergence of OMWU, we first apply Lemma with Dv(u, v) = KL(u,, v)), = z² (the unique equilibrium of the game matrix G) and (p,4) = (1, The constant can be chosen as since dist (F(z), F(z')) = max, [Glyy - y'), max, |G (x x') r')),s" S lly
In matrix game we have X = -AM, y AN. and f(z) G E [-1,
|| + || - I'll? = dist (2, z'). Also notice that F(z.)((z: (z:-2" = f(0,, y:) - f(x ye) + fax y²) - f(x,, y:) = f(xr, y²) - f(x', y1) 2
by the optimality of z². Therefore, we have when 17 S //4
,L( 2441) < KL(2" 21 KL (L,1111 zx) - 15 KL [1, 2,) + 1 KL (2,, 21-1). 16
16
Defining O, KL(z* 2.) + 1e KL 12- and G (L( z1) KL Z,), we rewrite the above as
0 < θ 15
(3)
From Eq. (3) it clear that the quantity O is always non-increasing in / due to the non-negativity of G. Furthermore. the more the algorithm moves between round and round + 1 (that is, the larger
Se is). the more O, decreases.
To establish the rate of convergence, a natural idea is to relate &. back θ or O For example, if we can show Ç 2 c0,41 for some constant c >> 0, then Eq. (3) implies O,41 S θ 15c O
which further gives 0.41 Σ (1+ + 15c) -1
16 O. This immediately implies a linear convergence rate for O as well as KL(2", 2.) since KL(z", 2.) < O..
Moreover, notice that to find such c, it suffices to find a c' > O such that & 2 d'KI(2", 22+1). This because it will then give G. 2 16 KL 2:) + c 2 1/ KL + l5c! KL(2", 2,+1) 2 16 10+11, and thus c 2 m1n
16
min 15c'
15e' satisfies the condition.
16
From the discussion above, we see that establish the linear convergence of KL(2", 2,), we only need to show that there exists some c' > 0 such that KL( 21) + KL( 2,) 2 e'KL(z', 2441). this inequality that when 2 is far from the equilibrium 2" (i.e., KL 22" 2 is large), the algorithm should have large move between round t and t + 1 making KI (2,+1,1, 2.) + (L, 2,) large.
The high-level interpretation
In our analysis, we use a two-stage argument to find such c'. In the first stage, we only show that KL( 2,) + KL 2,) 2 é" "KL("", 22412² for some c" > O, and use to argue slower convergence rate KL(2", 2.) = o ( Then in the second stage, we show that after ε, and 2 become close enough to z", we have (L 2.) (L, 2,) c'KL(z", ε441 for some c' > 0.
5

---

Published as a conference paper at ICLR 2021
This kind of two-stage argument might be reminiscent of that used by Daskalakis & Panageas (2019b); however, the techniques we use are very different. Specifically, Daskalakis & Panageas (2019b) utilize tools of "spectral analysis" similar to (Liang & Stokes, 2019) and show that the OMWU update can be viewed as a "contraction mapping" with respect to a matrix whose eigen- value is smaller than 1. Our analysis, the other hand, leverages analysis of online mirror descent, starting from the "one-step regret bound" (Lemmaa I) and making use of the two negative terms that are typically dropped in the analysis. Importantly, our analysis does not need an exponentially small learning rate required by (Daskalakis & Panageas, 2019b). Thus, unlike their results, our learning rate is kept as a universal constant in all stages. The arguments above are formalized below:
AN. and G [-1, 1JMxN Assume that there exists a unique Nash equilibrium z" and S S Then, there exists a constant C₁ that depends on G such that for any t 2 1, OMWU ensures
Lemma 2. Consider matrix game f(, y) x GTy with X AM, y
KL( 21) + KL(Z,, 2n) n/ CIKKL(Z ( 2
Also, there is constant { >> 0 that depends G (defined in Definition 2) such that as long as max(11=* Eell1, 1|" z =
- 71. then
KL((2+12 2.) + (I 2,) 2 C/CC2K(2"",
for another constant C2 > that depends on G.
With Lemma 2 and the earlier discussion, the last-iterate convergence rate of OMWU established: Theorem 3. For matrix game [(x,, y) x: Gy with unique Nash equilibrium z", OMWU with a learning rate 1) S & guarantees KL(z". ,izz="=]) x,) I Cs(1 + Ca) where C3, C1 >> 0 are some constants depending on the game matrix G.
Proofs for this section are deferred to Appendix D,, where all problem-dependens constants are spec- ified as well.' I To the best of our knowledge, Theorem 3 gives the first last-iterate convergence result for OMWU with concrete linear rate. We note that the uniqueness assumption is critical for our analysis, and whether this is indeed necessary for OMWU is left as an important future direction.
5 CONVERGENCE RESULTS FOR OGDA
In this section, we provide last-iterate convergence results for OGDA, which are much more general than those in Section 4. We propose a general condition subsuming many well-studied cases, un- der which OGDA enjoys a concrete last-iterate convergence guarantee in terms of the L2 distance between &, and Z The results in this part can be specialized to the setting of bilinear games over simplex, but the unique equilibrium assumption made in Section 4 and in (Daskalakis & Panageas, 2019b) is no longer needed.
Throughout the section we make the assumption that f is L-smooth: Assumption 1. For any 2, z' E Z. [z()) F(z')l < L||= z'| holds.? 2
To introduce our general condition, we first provide some intuition by applying Lemma 1 again. Letting v (u) 1 | in Lemma 1, we get that for OGDA, for any
and any t 2 1,
(n.) (z,
|| - 2|1² - || =||² ||54|| 2:112 1 2, 11 + 1 2 112
Now we instantiate the inequality above with z = T1 (2.) E 2" Since TT (2.) is an
equilibrium, we have F(z,) ( (z+ 2) 2 fax yt) fax y: f y) f( y:) = / faxt, y)
f(z, y:) 0 by the convexity/concaviiy of f and the optimality of z. and thus
[ 11z- (2-)) 2 11 (E))) || z, 2 13 2 2, + +
'On might tind that the constant Cs is exponential in some problem-dependeer quantity To. However, this simply a loose bound in exchange for more concise presentation our proof in fact shows that when t < To. the convergence is of slower 1/t rate, and when t 2 To, the convergence is linear without this large constant. 2This is equivalent to the condition (F(),, F(z')) < (2 z') in Lemma with p 2, hence the same notation L..

---

Published as a conference paper at ICLR 2021
Further noting that the left-hand side is lower bounded by dist dist (+ 2*) by definition, arrive at
15 dist (2,+1, & dist (2,, 2*) - || - zpl1²
| -2,12 + 1 1| 21-111
I6
Similarly, we define θ = || II 2- (2:]1?+ + 10 -1-1112 11? Ge || =el1? + || and rewrite the above as
2n 11?
0:1 S θ: 5
(4)
As in Section 4, our goal now is to lower bound & by some quantity related to dist ( Z*), and then use Eq. (4) to obtain a convergence rate for ④ In order incorporate more general objective functions into the discussion, in the following Lemma 4, we provide an intermediate lower bound for St, which will be further related to dist? (2 Z*) later.
Lemma 4, For any t 2 0 and x' E Z with x' * 2441, OGDA with S SL ensures
[F(2+1))
(2 2')1
32
|3++1 -el1 + 22 2
(5)
81
|2 =2112
where [a]+ A max(a, 0}, and similarly, x' # zt+1.
[((x+1) (2141 - x²)]
32
| 2++1/1++ 1i Eet1l 12
81 1²²
(6)
2z1+1 - =2112
We note that a direct consequence of Lemma 4 is an "average duality gap" guarantee for OGDA when is bounded:
1 T Σ a(2))
1 T
Σ
y'ey (f(a). f(a', vi)) 0
D TIVT
max
where D - su || 2 is the diameter of Z (the duality gap may be undefined when Z is unbounded). We are not aware of any previous work that gives this result for the constrained case. See Appendix E for the proof of Eq. (7) and comparisons with previous works.
However, to obtain last-iterate convergence results, we need make sure that the right-hand side of Eq. (5) is large enough. Motivated by this fact, we propose the following general condition f and Z to achieve so.
Definition "Saddle-Point Metric Subregularity (SP-MS)). The SP-MS condition is defined as: for any 2 with x" IIz.
F(z) (z =z') 2 C ==1
sup z'ez
(SP-MS)
2 z'1l
holds for some parameter B 2 0 and C 0.
We call this condition Saddle-Point Metric Subregularity because the case with B = 0 is equivalent to one type of metric subregularity in variational inequality problems, as we prove in Appendix F. The condition is also closely related to other emror bound conditions that have been identified for variational inequality problems (e.g., Tseng (1995); Gilpin et al. (2008); Malitsky (2019)). Although these works have shown that under similar conditions their algorithms exhibit linear convergence, to the best of our knowledge, there no previous work that analyzes OGDA or other no-regret learning al algorithms using such conditions.
SP-MS covers many standard settings studied in the literature. The first and perhaps the most impor- tant example is bilinear games with polytope feasible set, which in particular includes the classic two-player matrix games considered in Section 4.
Theorem 5, A bilinear game f(x, y) = x Gy with X C RM and y C RN being polytopes and G E IR X X satisfies SP-MS with 0.
7

---

Published as a conference paper at ICLR 2021
We emphasize again that different from Lemma 2, Theorem 5 does not require unique equilibrium. Note that we have not provided the concrete form of the parameter C' in the theorem (which depends on X, }r and G), but it can be found in the proof (see Appendix G). The next example shows that soongll--ovvee-sttongyy--oooo
problems are also special cases of our condition.
Theorem 6. If is strongly convex in a and strongly concave in y. then SP-MS holds with 3 = 0.
Next, we provide a toy example where SP-MS holds with 3 > O.
Theorem 7. Let X' = y
[(a.b) 0 < a. < 1, a + b 13. > 2 be an integer, and fax y) = 21//1 vpth Then SP-MS holds with 2n 2.
With this general condition, we are now able to complete the loop. For any value of 3, we show the following last-iterate convergence guarantee for OGDA.
Theorem 8. For any S ZL. SP-MS holds with 3 = 0, then OGDA guarantees linear last-iterate convergence:
dist (2,, 2*) S (Adistt(2)))) (2), 21) Cs)'
(8)
on the other hand, if the condition holds with /3 > 0, then we have a slower convergence:
$
$
2
dist² (21, 2-) s 32
1 1
dist (ast((2, (21, 24) +2
t
3
C5
where Cg - min
C2 81
2 1
We defer the proof Appendix and make several remarks. First, note that based on a convergence
result (z,, 2*), one can immediately obtain convergence guarantee for the duality gap
ay (zz) as long as f is also Lipschitz. This is because (z)) S maxx' y/ f(z y') - f(x", v') +
f(x', - f(x', v.) s O(Iaa, x'1| + |/.. v'll) =0 o (z,, 2+)) where (x" y²) 11z- (z.). While this leads stronger guarantees compared to Eq. (7), we emphasize that the latter holds even without the SP-MS condition.
Second, our results significantly generalize (Hsieh et al., 2019, Theorem 2) which itself is consol- idated version of several earlier works and also shows a linear convergence rate of OGDA under a condition stronger than our SP-MS with 3 0 discussed carlier. More specifically, our results show that linear convergence holds for a much broader set of problems. Furthermore, we also show slower sublinear convergence rates for any value of 0, which is also particular, we empirically verify that OGDA indeed does not converge exponentially fast for the toy example defined in Theorem 7 (see Appendix A).
far as know. In
Last but not least, the most significant implication of Theorem is that it provides by far the most general linear convergence result for OGDA for the classic two-player matrix games, or more gen- erally bilinear games with polytope constraints, according to Theorem 5 and Eq. (8). Compared to recent works of (Daskalakis & Panageas, 2018; 2019h) for matrix games (on OGDA or OMWU), our result is considerably stronger: 1) we do not require unique equilibrium while they do; 2) linear convergence holds for any initial points ε, while their result only holds if the initial points are in small neighborhood of the unique equilibrium (otherwise the convergence is sublinear initially); ST.
3) our only requirement on the step size is 1) S 1. while they require an exponentially small n), which does not reflect the behavior of the algorithms in practice. Even compared with our result in Section 4, we see that for OGDA, the unique equilibrium assumption is not required, and we do not have initial phase of sublinear convergence in Lemma 2. In Appendix A, empirically show that OGDA often outperforms OMUU when both are tuned with a constant learning rate.
After first version of this paper. we found that (Gilpin et al.. 2008, Lemma 3) gives a simpler proof for our Theorem 5. Although their lemma only focuses on the case where the feasible sets are probability simplices, it can be directly extended to the case of polytopes.
In fact, any over our proof. We use < R7, simply for consistency with the results for OMWU (where ry cannot be set any larger due to technical reasons).
2C is enough achieve linear convergence rate for OGDA, one can verify by going
8

---

Published as a conference paper at ICLR 2021
5
-5
-10
-15
-MWU--tt-011
OMWU-em-022
-20
0M
-MMWU-em-1
-MWWU-eta5
-25
OMWU-eta=10
OGDA-eta-0.123
OGDA-eta=0.25
DGDA-eta-0.3
-35
0.5
1.5 2
2.5
x10
Figure 1: Experiments of OGDA and OMWU with different learning rates for matrix game fæx y) = x Gy. "OGDA/OMW SEGDA//OW--ea--n" represents the curve of OGDA/OMWU with learning rate 1/. The configuration order in the legend is consistent with the order of the curves. For OMWU, 2 11 makes the algorithm diverge. The plot confirms the linear convergence of OMWU and OGDA, although OGDA generally observed to converge faster than OMWU.
One may wonder what happens if bilinear game has a non-polytope constraint. It turns out that in this case, SP-MS may only hold with 3 >> 0, due to the following example showing that linear convergence provably does not hold for OGDA when the feasible set has a curved boundary.
Theorem 9. There exists bilinear game with non-polytope feasible set such that SP-MS holds with 3 = 3, and dist? d 2*) = (11 holds for OGDA.
This example indicates that the shape of the feasible set plays important role in last-iterate conver- gence, which may be an interesting future direction to investigate, This is also verified empirically our experiments (see Appendix A).
EXPERIMENTS FOR MATRIX GAMES
In this section, we provide empirical results on the performance of OGDA and OMWU for matrix games on probability simplex. We include more empirical results in other settings in Appendix A. We set the size of the game matrix to be 32 x 32, then generate random matrix with each entry Gi3 drawn uniformly at random from [-1, 1, 1). and finally rescale its operator norm to 1. With probability the game has unique Nash Equilibrium (Daskalakis & Panageas, 2019b).
We compare the performances of OGDA and OMWU. For both algorithms,, we choose a series of different learning rates and compare their performances, as shown in Figure 1. The æ-axis represents time step t, and the y-axis represents In (KL(2*, .x)) (we observe similar results using dist? (z" =x) or the duality gap as the measure; see Appendix A. Note that here we approximate x by running OGDA for much more iterations and taking the very last iterate. We also verify that the iterates of OMWU converge to the same point as OGDA.
see that all curves eventually become straight line, supporting our linear conver- gence results. Generally, the slope of the straight line is larger for a larger learning rate 7). However, the algorithm diverges when exceeds some value (such 11 for the case of OMWU). Comparing OMWU and OGDA, we see that OGDA converges faster, which is also consistent with our theory compares the bounds Theorem and Theorem (with the value of the constants revealed in the proofs). We find this observation interesting, since OMWU is usually considered more favorable for problems defined over the simplex, especially in terms of regret minimization. Our experiments suggest that, however, in terms of last-iterate convergence, OGDA might perform even better than OMWU.
From Figure
Note that in this case the projection step of OGDA can he implemented in O(M M N+N time (Wang& & Carreira-Perpimán, 2013).

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
The authors would like to thank the anonymous reviewers for providing highly constructive com- ments which bring about significant improvement of the result during the rebuttal phase. CL would like thank Yu-Guan Hsieh for many helpful discussions on error bounds and metric subregularity The authors are supported by NSF Awards IIS- 1755811 and IIS-1943607.
REFERENCES
Ahmet Alacaoglu, Olivier Fercoq, and Volkan Cevher. On the convergence of stochastic primal-dual 2019.
hybrid gradient. arXiv preprint
Waiss Azizian, Joannis Mitliagkas, Simon Lacoste-Juliss and Gauthier Gidel. A tight and unified analysis of gradient-based methods for whole spectrum of differentiable games. In International Conference on Artificial Intelligence and Statistics, 2020.
James P Bailey and Georgios Piliouras. Multiplicative weights update zero-sum games. In Pro- ceedings of the 2018 ACM Conference Economics and Computation, 2018.
Michael Bowling. Convergence and no-regret in multiagent learning. In Advances in neural infor- mation processing systems, pp. 209-216, 2005.
Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Accelerated schemes for a class variational incqualities. Mathematical Programming, 2017.
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference Learning Theory, pp. 807-834, 2019.
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. Advances in Neural Information Processing Systems, 2020.
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pp. 6-1, 2012.
Shisheng Cui and Uday Shanbhag. On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. In 2016 IEEE 55th Conference Decision and Control (CDC), 2016.
Constantinos Daskalakis and Toannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246,
2018.
Constantinos Daskalakis and loannis Panageas, Last-iterate convergence: Zero-sum games and con- strained min-max optimization. Smooth Games Optimization and Machine Learning Workshop (NeurIPS 2019), 2019a.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. Innovations in Theoretical Computer Science, 2019b.
Constantinos Daskalakis, Alan Deckelbaum, Anthony Kim, et al. Near-optimal no-regret algorithms for zero-sum games. Games and Economic Behavior. 2015.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations, 2018.
Damek Davis. Lecture 5, mathematical programming I, 2016a. Available at people people.orie. orie. cornel 1 aadu/ddd95/teee h lec./.cc055000 pdf.
Damek Davis. Lecture 6, mathematical programming I, 2016b. Available at people, orie. haw.:a3000eeee..pppep.e pdf.
cornel
10

---

Published as a conference paper at ICLR 2021
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):7--103, 1999.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. vari- ational inequality perspective generative adversarial networks. International Conference Learning Representations, 2019.
Andrew Gilpin, Javier Peña, and Tuomas Sandholm. First-order algorithm with o (In (I/e)) conver- gence for e-equilibrium in two-person zero-sum games. In AAAI, 2008
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi- player games. Advances in Neural Information Processing Systems, 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. Conference on Learning Theory, 2020b.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, 2014.
Patrick T Harker and Jong-Shi Pang. Finieeddimensional variational inequality and nonlinear com- plementarity problems: survey of theory, algorithms and applications. Mathematical program- ming, 1990.
Yu-Guan Hsieh, Franck Tutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Advances in Neural Information Processing Systems, 2019.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggres- sively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 2020.
Alfredo N lusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extragra- dient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 2017.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. 1976.
Alexander Y Kruger. Error bounds and metric subregularity. Optimization, 2015.
Torbjöm Larsson and Michael Patriksson. A class of gap functions for variational inequalities. Mathematical Programming, 1994.
Puya Latafat, Nikolaos Freris, and Panagiotis Patrinos. A new randomized block-coordinate primal-dual proximal algorithm for distributed optimization. IEEE Transactions Automatic Control, 2019.
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Last iterate convergence in no- regret learning: constrained min-max optimization for convex-concave landscapes. The 24nd International Conference on Artificial Intelligence and Statistics, 2021.
Leventhal. Metric subregularity and the proximal point method. Journal of Mathematical Analysis and Applications, 2009.
Jingwei Liang, Jalal Fadili, and Gabriel Peyré. Convergence rates with inexact non-expansive oper- ators. Mathematical Programming, 2016.
Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local conver- gence of generative adversarial networks. In The 22nd International Conference Artificial Intelligence and Statistics, 2019.
Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. Conference Learning Theory, 2020.

---

Published as a conference paper at ICLR 2021
Zhi Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 1993.
Yu Malitsky. Projected reflected gradient methods for monotone variational inequalities.
SIAM
Journal on Optimization, 2015.
Yura Malitsky, Golden ratio algorithms for variational inequalities. Mathematical Programming. 2019.
Yura Malitsky and Matthew K Tam. A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization.
Panayotis
Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial
regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium
Discrete Algorithms, 2018.
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan- Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of (1//k) for optimistic gradient and extra gardiggrddent methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-3251 2020a.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. The 22nd Inter- national Conference on Artificial Intelligence and Statistics, 2020b.
John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 1928.
Jong-Shi Pang. Error bounds in mathematical programming. Mathematical Programming, 1997.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 1980.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013.
Michael V Solodov and Paul Tseng. Some methods based on the d-gap function for solving mono- tone variational inequalities. Computational optimization and applications, 2000.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence regu- larized learning in games. In Advances in Neural Information Processing Systems, 2015.
Paul Tseng, On linear convergence of iterative methods for the variational inequality problem. 1995.
Weiran Wang and Miguel A Carreira-Perpinán. Projection onto the probability simplex: An efficient algorithm with simple proof, and an application. arXiv preprint 1rX9vv1309.110 2013.
Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems. arXiv preprint arXiv:1912.07449 2019.
12

---

Published as a conference paper at ICLR 2021
A MORE EXPERIMENT RESULTS
A. MORE EMPIRICAL RESULTS FOR MATRIX GAMES
Here, we provide more plots for the same matrix game experiment described in Section Specif- ically, the left plot in Figure 2 shows the convergence with respect to In || =*I1. while the right plot shows the convergence with respect to the logarithm of the duality gap In(ay(z:)) in (max, (G' (t) min))G One can see that the plots are very similar those Figure 1.
-0
15
10
20
DMATH-B-E2
0224-22901233
OS0A 2204-2206.12
Figure 2: Experiments of OGDA and OMWU with different learning rates on matrix game (æx y) x. Gy. where we generate E 32x32 with each entry G.5 drawn uniformly random from 1, 1] and then rescale G's operator norm to 1. "OGDA/OMW, (OMWU-etazi" represents the curve of ROGDA/OMWE with learning rate n). The configuration order the legend consistent with the order of the curves. For OMWU, Z 11 makes the algorithm diverge. The plot confirms the linear convergence OMWU and OGDA, although OGDA is generally observed to converge faster than OMWU.
A.2 MATRIX GAME ON CURVED REGIONS
Next, we conduct experiments on a bilinear game similar to the one constructed in the proof of Theorem 9. Specifically, the bilinear game is defined by
f(x, v) 22//1 2132:
X = y ((. 0 a 1 a" b).
For any positive integer n, the equilibrium point of this game is (0, 0) for both x and Note that in Theorem 9, we prove that OGDA only converges at rate no better than 12(1tt2 ) in this game when 2.
Figure 3 shows the empirical results for various values of n. In this figure, we plot || 2* versus time step f in log-log scale. Note that in a log-log plot, straight line with slope implies convergence rate order (()), that is, a sublinear convergence rate. clear from Figure 3 that OGDA indeed converges sublinearly for all n, supporting our Theorem 9.
A.3
GAMES
In this section, we use the same experiment setup for stonnglycomvex-ssronyyyyooo games in (Lei et al., 2021), where
f(x y) = x - + 2r131, and x y ((a,b).0 a. 5. a
The equilibrium point is (0, 1) for both æ and y. Figure 4, we present the log plot of =1--=" ver- time step / and compare OGDA with OMWU using different learning rates as in Appendix A. The straight line of OGDA implies that OGDA algorithm converges exponentially fast, supporting Theorem 6 and Theorem 8. Also note that here, OGDA outperforms OMWU, which is different from the empirical results shown in (Lei et al., 2021). We hypothesize that this is because they use different version of OGDA.
13

---

Published as a conference paper at ICLR 2021
0
-4
In 22
-10
2
6 In(1)
10
12
Figure 3: Experiments of OGDA on matrix games with curved regions where f(x, y) = T2//1
3i 0122, X' x= y A {(a, b). 0 < a < 2. 0 < b 2F, a" < b). and n 2, 4, 6, 8. This figure is log-log plot of =|= 211 versus and it indicates sublinear convergence rates of OGDA in all these games.
-15
In[
OMWU-eta=0001
-20
OMWU-eta=0..1
OMWU-eta=0.2
OMWU-eta=0.5
-25
OMWU-cta=1
DGDA-eta-0.122
DGDA-eta-0.22
-30
0
20
40
60
80
100
120
140
t
Figure 4: Experiments on a soanggyyyooveex-stoonlyyyooooooo 2z131 and X' = y {(a, b), < o, < 1, + = 1}. The figure is showing In || =01 versus the time step t. The result shows that OGDA enjoys linear convergence and outperforms OMWU in this case.
game where f(x, y) = x - vी +
14

---

Published as a conference paper at ICLR 2021
0
In( 21
-3
11
6
In(1)
Figure 5: Experiments OGDA on a set of games satisfying SP-MS with , > 0, where f(x, y) x I191 - 3 for some integer n 2 2 and = y å {(,,b).00 S a, b < 1, a + = 1}. The result shows that OGDA converges to the Nash equilibrium with sublinear rates in these instances.
A.4 AN EXAMPLE WITH 3 > 0 FOR SP-MS
We also consider the toy example in Theorem 7, where fxx y) = z² - - - for some integer
and X' y A {(a, b), 0 < b < 1, a a+ 1}. The equilibrium point is (0, 1) for both and y. We prove in Theorem 7 that SP-MS does not hold for /
but does hold for 8 = 2n 2.
The point-wiss convergence result is shown in Figure which is again log-log plot of || 2" versus time step t. One can observe that the convergence rate of OGDA sublinear, supporting our theory again.
A.5 MATRIX GAMES WITH MULTIPLE NASH EQUILIBRIA
Finally, we provide empirical results for OGDA and OMWU in matrix games with multiple Nash equilibria, even though theoretically we only prove linear convergence results for OMWU assuming that the Nash equilibrium is unique. We consider the following game matrix
1
1
0
1
0
G =
-1
1
0
0
0
0
-1
1
0
-1
2
The value of G is 0. To verify this, consider 2p Yo maxye4, 2 Gy minges, T "yyo Direct calculation gives the following set of Nash equilibria.
0). Then have for
X" = {aa).
y" E As = 82 Ys!
2 yss S 91 S 2ys
Figure 6 shows the point-wise convergence result. I (z) is the projection of %, on the set of Nash gquilibria. One observe from the plots that both OGDA and OMWU achieve linear convergence rate in this example. We thus conjecture that the uniqueness assumption for Theorem be further relaxed.
15

---

Published as a conference paper at ICLR 2021
[nd]iTee Lnd ml0
-14
OMMUU =b-0
ONWIU cb-0
ONWiU-elamt
-16
eb
-18
500
-10
120
ONWUU-U-03
-30
0GD4 ab-0.122
OWWil-atent
0EDA ob-0
06:04-91-005
500
1000
1500
2000
2500
300D
3500
4000
4500
5000
0-
-0
Lajoy
20
-22
DNWU 05a-3.2
-14
DNWU e2--2.5
-16
DGDA eb-
-18
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
Figure 6: Experiments of OGDA and OMWU with different learning rates on a matrix game with multiple Nash equilibria. JOGDA/OMWU-eta--- represents the curve of OGDA/OMWU with leamiing rate 77. We observe from these plots that both OGDA and OMWU enjoy linear con- vergence rate, even though we are only able show the linear convergence of OMWU under the uniqueness assumption.
16

---

Published as a conference paper at ICLR 2021
B LEMMAS FOR OPTIMISTIC MIRROR DESCENT
We prove Lemma I in this section. To do so, we use the following two lemmas.
Lemma 10. Let A be convex set and u' argmin f(u', g) Dulul, u)}. Then for any u E E,A
(u' (u'-u", gg) S Dw(u' u) Dolu", u') Do u).
(10)
Proof. Since (u''', u) = (1n)) (b)) (V)((u), ut -u). by the first-order optimality condition
of u', we have
g + vo(u') (v)))) (u" - -u') O.
On the other hand, notice that the right-hand side of Eq. (10) is
v(u") (vx) (Vv(u)) u² - u)
v(u") + v(x)) + (Vv(u'), u² =u')
(uu)) + +v())= + (Vv(u), u' u) (Vi((') (V)(u,, u n²).
Therefore, Eq. (10) is equivalent to (g + Vu((2)) - Veb(u), u² - u²) 2 0. which we have already shown above.
Lemma 11. Suppose that so satisfies (ar x²) 2 211:0 - x. a111, l1 for some p 2 1, and let u1 A (a convex set) be related by the following:
argmin ((u'g.)) + D (u'; u)},
w'EA
U2 argmin ((u', 92) + (u', u)} u'
Then we have
au uu2lp
1 92 lq
where q 2 and 1 +
=1.
p
Proof.
By the first-order optimality conditions of un and u2 we have
u1) 2 0, (Vv(ua) Vv)(a) 92, ui u2) 0.
(Vu((t)) - ((b( + 91, u2
Summing them up and rearranging the terms, we get
(uz U1 91 92) 2 (V)(w)) Vvl(u), un U2))
(1I)
By the condition v. have (V U1 U2) > vuu)) (us)) 11l
u2l1 and (Vu((z)) u2 un) 2 (u2) (un) + 211u, uu u2 12 Summing them up we get (Vv(un)
Veb(u)) u1 u2) 2 [uu - u2 1| Combining this with Eq. (11) we get
(uz - ui 91 g2) 2 || - u2l1
Since (u2 u1, 91
92) < [u - uellel1 g2lla by Hölder's inequality, we further get Uu
uzllp lg 92llg-
Proof of Lemma 1. Considering Eq. (2), and using Lemma 10 with = 2,, w = 2,41, u" 2,
and g = Fzz)) we get
F2(1)) (2 2) < Des (2, Dz 2441) D (2 21).
Considering Eq. (1), and using Lemma 10 with u 2, u' = 21. 2² = 2,41, and g (2 we get
(F(z)1) (z+ 2411 (2,1,, Ex) (2 21) - Dol2,, 2i).
17

---

Published as a conference paper at ICLR 2021
Summing up the two inequalities above, and adding 1, (F((z) F(z(-1)) (zi Ee41) to both sides, we get
nf (#1) (z1 - x) $ (2, - (2, Ze+1) - (2(2,1, (2, 21) (1(((())) - F(z1-1)) (2: 2(+1):
(12)
Using Lemma 11 with u - Tc, u1 = 21, U2 = 2141. - and g2 = v/Va (z1). we
get 1 1|p S -
Similarly, we have 1/ Di+illp 7/ V y fz())
V f Therefore, by Hölder's inequality, we have
(F(z)) F(2(-1)) (z E++1)
S <n| Te+1 / - (=f(z)) + nlye F 3 - vuf(2)))l -Vy//\
= dist (F(z)) F(z-1))
s n/ L dist د/ ( 1(-
(by assumption)
- 64
dist 2,, 21 1)-1)
(by our choice of 17)
Continuing from Eq. (12), we then have
(F(()) x) x)
Dz0 2c) (z, 2441) (Er+1,, Dol2is 2,) d Zt; 2t-1)
1
< Do (z, 21) - (2, 2.41) (2. 21) (2, 2,) + dist (ze, 2e) + / dist (2,, 11
32
32
(1/u + v1ß 1 (1|u|pp + || >22 + 2||b113)
$ (2,(2,2)) - Dz 2041) D2 21) (2 21
D v (21, 2,) + 16
Do z111)
16
(by the assumption on +
15
(2, (1,,22)-D,aee (z, 2++1) -
D (z 2,)
De (Z,, z(-))
16
16
This concludes the proof.
C AN AUXILIARY LEMMA ON RECURSIVE FORMULAS
Here, provide auxiliary lemma that gives explicit bound based on particular recursive formula. This will be useful later for deriving the convergence rate.
Lemma 12. Consider non-negative sequence (Bi)t=12,... that satisfies for some p > 0 and g O,
B441 S B, - -q 1L 2
g(1+p)BB 1.
Then B, S + where e = max
B1,
2 9
Proof. We first prove that B+ < B, y12 BB++1 Notice that since B, are all non-negative, by the
first condition, we have Bu+1 < B, < ... < B,. Using the fundamental theorem of calculus, we have
B,
(
Bi f
BP+1
Bptl
(
dr (p+1)
d'dr S (p + 1)(B, B
Biss
dx
B441
and thus
Bi4 S B, - -Bpttt < B, 91p+11 + q(p + 1) (B. - B1+1) B.
18

---

Published as a conference paper at ICLR 2021
By rearranging, get
Bo+1 - (1-
qBB
B1 - 1 qB
B, Br - B
+ a(1 + B,
2
where the last inequality is because q(1 + B) S + B) 1
Below use induction to prove B, ct where max Bi,
2 p This clearly holds 4p
for & 1. Suppose that it holds for 1 ,...., Note that the function f(Bt) (1 BB Be is
increasing in B, as (B,) = 1 2(++1) B. 2 g B 2 induction hypothesis and get
0. Therefore, we apply the
Bu+1 - (1 (1-2
9 BD
B₁ - (1 (1- 9 10t
2 ct
= et
! p+ 1 S ct
1-1-
( s 300t1 by the definition of c)
2
p
c(t 1)
where the last inequality is by the fundamental theorem of calculus:
+1+11+ L"d
dr )
fdd
1 (-)) x 11-1- -
x
ddr
1140 dx
11t
1+1
x -1- da
S -t -1-__
p
p
This completes the induction.
D PROOFS OF LEMMA 2 AND THEOREM 3
In this section, we consider f(x, y) x Gy with X = AM and y = AN being simplex and G [- M We assume that G has unique Nash equilibrium z² (x y²) The value of the game is denoted as p miDæe maxyey x Gy m&Xyey min x: Gy x x Gy".
Before proving Lemma and Theorem 3, in Section D.I, we define some constants for later analysis; in Section D.2, we state more auxiliary lemmas, which are useful when proving Lemma 2 and Theorem Scction D.3.
D.1 SOME
CONSTANTS
First, define constant that is determined by G. Definition 2.
c min
min iqsupp(a>))
(Gy"): P.
max (G x (GTx"); iquppp))"
E (0, 1].
The fact & < can be shown by:
& miniggappte= (Gy" p max (G x²)
|yy loo | +IG x <
2
2
while the fact & > is direct consequence of Lemma C.3 of Mertikopoulos al. (2018), stated below.
Lemma 13 (Lemma C.3 of Mertikopoulos et al. (2018)), Let E M be a game matrix for two-player zero-sum game with value Then there exists Nash equilibrium (x" ,y") such that
(Gy == p
Vi supp(a*), Vi $ supp(æ"),
(Gy );
(G x²); =0
Vi E supp(y");
(G x");<] <p
iA & (upp(y")
19

---

Published as a conference paper at ICLR 2021
Below, we define (²(2)=Vv(22 -x) ())),, where
V*(x) - {o E AM, supp(æ) supp(æ"))
and
V2 _ yy y AN. supp(y) S supp(y")) }}
Definition 3.
[x - xx)) GGy
x T G(y y
Cp
max TEAM (x ()) | x²
min
-
min 2
max
y y/11
Note that in the definition e2 and cy. the outer minimization is over an open set, which may make the definition problematic as the optimal value may not be attained. However, the following lemma shows that c₂ and cy are well-defined.
Lemma 14. og and Cy are well-defined, and Cas Cy S
Proof. We first show Or and cy are well-defined. To simplify the notations, we define ziin einpe)) x and X' & fo : E AM, x - x0111 2 rimi and define yini and ) similarly. We will show that
(x x²) xT"TTT Gy
x G y) yy" y
C
min max =EX ()) x x=1l
Cg
min max yEy eXV
which are well-detined as the outer minimization is now over a closed set. Consider Cz. it suffices show that for any æ E A M such that j x and æ
x0|l
|| < aiin there exists x' AM such
that || - x x=112 2min and
(
x²) x
Gy
(x' TGy
Vy.
(13)
x²1l
||00
x
In fact, we can simply choose x' = xx (x x²)
x² mmin
We first argue that æ' is still in A M-
1 x- x
||:
For each j E [K], if at - 2 2 0, we surely have n/ 2 x + > 0; otherwise, xÿ > Iz 2 0 and
thus j E supp(x") and x; 2 x which implies 2'} 2 2
T--2-11 2 x min 2 0.
In addition, Σ En 1. Combining these facts, have xf E AAM
Moreover, according to the definition of æ', - 2iin holds. Also, since x² and x= xx' are parallel vectors, Eq. (13) is satisfied. The arguments above show that the eg Definition 3 is well-defined real number. The case of cy is similar.
Now we show 0 < Ca. Gy < 1. The fact that C, S 1 is a direct consequence of G being in [-1, M Below, we use contradiction to prove that cy > O. First, if Gy < 0, then there exists y * y" such that = Gyy < x= Gy. This contradicts with the fact that (x",, y²) is the equilibrium.
On the other hand, if c, = O, then there is some + y such that
max E T G(y - y) = 0. (X)
(14)
20

---

Published as a conference paper at ICLR 2021
Consider the point y y 2 (y-y") (recall the definition of & in Definition 2 and that 0 <<>>> 1), which lies on the line segment between y and y. Then, for any a E X,
Gy'
Σ
Σ
GGy's')ss
(Esupp(<")
(
Σ
(z,(Gy)) uzlly'' y²lli) +
Σ
xy (G yy')); + +.;
iEsupp(=))
(using Giy E [-1, -1] for the first part and y' y { y²) for the second)
(z.(Gy") ) 2,1lv' yy (11 +
Σ
D&P
sEsupp(x*)
(using Eq. (14) and (Gy" ) = p for all i supp(x"))
Σ i(supp(æ=))
(Is (GG"") )) +
T&P
iEsupp(æ"))
(using y' - yy -f - y²) and ly y²11 S 2)
Tif +
Σ (Esupp(a*)
TAP
(by the definition of {
iEsupp(æ*) p.
This shows that mingeX x' Gy' 2 p. that is, y' * y² is also a maximin point, contradicting that x" is unique. Therefore, cy has to hold, and so does O9 0 by the same argument.
Finally, we define the following constant that depends on G: Definition 4.
In(MN) 23
min exp jEmpp(2=)
D.2 AUXILIARY LEMMAS
All lemmas stated in this section is for the case f(x, y) = x T Gy with Z = AM x An and unique Nash equilibrium 2" (x", yy")
Lemma 15. For any E Z, we have
max F(z) (z- x') 2 OlIz* 2/11
x2E
for C= min(an Gy) E (0,
Proof. Recall that x= Gy" is the game value and note that
max F(z) (z z') max 2') Gy x Gly' (2) =2E
-y) max
=x"Gy + x T Gy
(2)
max (p - TT Gyy max =X)
(x: TTy'' - p)
y))
max x¹ GGy" y) + max v'E""(")
(x x x²) Gy
(Lemma 13)
x'EV
2 cylly" - U|l + Cz --" - x||1
(by Definition 3)
min Cy ) 2||²" 2||1,
which completes the proof.
Lemma 16. For any z E Z, we have
( 24
KI,(2, 2) <
Σ
S
2/ 2//1.
2i
miniesmp(x=)) 2i
(x>ppp(=*)
#(mpp(=**
21

---

Published as a conference paper at ICLR 2021
Proof. Using the definition of the Kullback-Leibl divergence, we have
2 I3
mza) Iz
(x] xx:)
KL(x", x)) Σ F3 In
In
In
where the first inequality is by the concavity of the In(-) function, and the second inequality is be- cause In(1 + u) S u. Considering E supp(x=") and i & supp(æ") separately in the last summation,
we have
Σ
12)²
(x) x4)
(x:))
(xf xz)
F1
xEsupp(=**
Esuup((c'
(Euupp(a")
(xsupp(=*)
The case for KL y) is similar. Combining both cases finishes the proof of the first inequality (recall that KL(=", 2) is defined as KL(x", x) + KL(Y", The second inequality is straightfor- ward:
(Ef 2:)
Σ xEsupp(=*)
Σ
23 min 2i
Σ
2
zil +
1zsl
2x
#=xupp(=")
(Exupp(=")
s(supp(2*)
1 - 2 /2-
muppe 24
Lemma 17. For S I. g. OMWU guarantees 72,, S 2e, S 2 and 22, S S4t1 S $2.
Proof. This is shown directly by the update of ãe:
Tr. exp (-n) < F De,s exp (-n- (Gy():
21, exp (n) exp(-1)
cxp (n)
E3 Ft. exp (-1) (Gy))
So by the condition on y, have 3 S exp(-2n) 3z,s 54 S exp(21) -z,s S f The cases for æt, y and ye are similar.
Lemma 18. For any two probability vectors u, if for every entry i, f4; S S Ju then
[u--)) < kL(u,v) Σ
(2) (0)-u.)²
<
Proof. Using the definition of the Kullback- divergence, we have
KL(u, v) Σ
Ui In Ui
U; Ui
(0; - uz
(0) u;)
>
Wi
Ui
3
KL v) = Σ
Uq In Vi Ui
<
Σ
Ui
(vz u;)3
(Us u )2
1
4
where the first inequality is because In( +a) S a- f/a² for - S a < 4, and the second inequality is because In(1 + a) 2 a² for < < 2. The third inequality is by using the condition
|u, v/| < } uq.
Lemma 19. For all E supp(z*) and t, OMWU guarantees 2, 2 (E is defined in Definition 4).
Proof. Using Eq. (3), we have
KL O2 ..: 16
KL 20) KL(x",21) KL(=",21
(15)
where the last equality is because & Zg
LM
IN).
M
22

---

Published as a conference paper at ICLR 2021
Then, for any supp(=") ). we have
In
In
KL(=",
20) - - 2j in S KL(=", - - 2j in
j
Σ
2j
In
In(MN).
Therefore, we conclude for all t and E supp(z*), Ee, satisfies
In(MN)
[I(MNN
2 2 exp
min jEsup((=*)
exp
27
23
D.3 PROOFS OF LEMMA AND THEOREM 3
Proof of Lemma 2. Below we consider any z' E Z such that supp(>') S supp(=*), that is, x' e (2). Considering Eq. (1), and using the first-order optimality condition of 2 we have
(Ve(2 - V + (=())) Txx - -2+11 0,
where ((x)) = Ei Zi pj. Rearranging the terms and we get
E+t1,
- Ff (z:) (E x = -V (z'- 2(41) = = (4) 2441,) In
2,,
(16)
The left hand side of Eq. (16) lower bounded as
FF (zi) (El+1 x') nF (2(+1) T (2141 x') + (F (zi) F (2(+1)) T (2141 z²)
2 nF (2(+1) ) (2141 - -z') - 1/| F (z.) - F (8(+1) 1100 || - -2'11
2 nF (2++1) ) (2141 =z') 4n 2| 2141 [|
F (z1) - F (2++1) 11 S 1|z - 111 S 4)
nF (2(+1) " (2141
z') 2 || 2 I
(n S 1/8)
on the other hand, the right hand side of Eq. (16) is upper bounded by
E4t1.
Σ (2/ - -2441,) In
Σ
In
KL(
(supp(2') S supp(=*))
2,,
2,
=Esupp(=*)
Σ
In
1.
2,,i
=Esup((**) )
max In | E441.b - Reg In | 2,, Ze+1.
Σ
2
2 1,
=Euup((**)
1241,,1 - 20,
In 1+
min 10 20,1)
iEsupp(**)
E Er.1l
Σ
(In(1 a) s a and Lemma 17)
(Esupp(=*)
Combining the bounds on the two sides of Eq. (16), we get
4
2241
2cal
1 |1 2.+1ll1.
oF (Ze+1)² (E1+1 x') <
Σ
*
23

---

Published as a conference paper at ICLR 2021
Since z' can be chosen any point in V²(2), further lower bound the left-hand side above using
Lemma 15 and get
E1+1, - E,,l
n/||1=" -itt1ll -
-/1=: - -2+t1lla
3
2,,1
1Esupp(z*)
4
|2+11
2 + =22
2112z 22+1l11,
(Lemma 19)
3P
<
(1 - E + || 2011l12)
(17)
3e
where the last inequality uses S 1. With the help of Eq. (17), below we prove the desired inequalities.
Case 1. General case.
KL
21+1, 21) + KLL(zz 2t)
1
1
> |a++1 xz [7 +
Vi+1 - yelli 2 21 zell? + 13: Dell (Pinsker's inequality)
2
2
2
|8 - x111 +
1 - 21l
(a² + 2 (a + b)3)
4
1
1
2
|
- 21li
(11 - 2:lli + || 2elli)
16
8
1
|
|| 2
(a² b2 2 2/ 8) and triangle inequality)
16
16
1
(|
11|11 + || 2
(a + 1 > (a. + b)
32
1
BenC'
- -2+111
(Eq. (17))
32
C212
c2222
x (KL(z" 22-112²
,L(2",2(+1)) 2.
(Lemmaa 16 and Lemma 19)
64
64
This proves the first part of the lemma with Ci = e02 /64.
Case 2. The case when max -
211113 S
ng T0
(I((2+1:;2) 22) + (1((2;22) 2x)
(21+1,5 21,1)2
+ (z 20.0)2
2 Σ
(Lemma 17 and Lemma 18)
2441.
2
(2441,1 - 2x,)²
(21,5 2,,
2
Σ
+
(Lemma 17)
4
2,,5
2
s(supp(=')
(2441,5
-2,,)
IV
Σ
(18)
Zz,b
1x)upp(=*)
Below we continue to bound Σ )(supp(==*)
By the assumption, we have 1/v.- -0-
4n'l 11 < :
which by Lemma 13 and Definition 2 implies
n
Vi E supp(="),
(Gy)); (Gy"):
p
< p +
10
10
10"
9
Vi & supp(æ"),
(Gy,); 2 (Gy");
> E
>
+
10
10
10
24

---

Published as a conference paper at ICLR 2021
We also have || x²111 S 10 Σ (xuppp( Dt.j S
75
Then, for i & supp(æ"). we have
100
exp( ( (n)())))))))
Be+1,1 =
Σ, Bis (xp(-n((yy)))
Lt, exp(- (Gy)).)
jExupp(x*) Ft.j exp( (Gy))))
Tr.1 exp( (ppppppppppppppp 2
Σ jecupp(a" : Te. exp( (n f
8 Te, exp (- 10 ng)
E ))
(t.s)
Ft.s exp
8 15)
I Lz,
1 -2255
of
10
where the last inequality is because exp(-0.80) 00.
1 0.5u for E [0, 1]. Rearranging gives
1-0.1a
T++1.1
E0,5l 2
n252 8411.
3t,
Lt,i
where the last step uses Lemma 17. The case for ÿt is similar, we have
x
241,6
Combining this with Eq. (18), we get
1/52
KL KL((241, KL 2,) 2
24+1,5-
(19)
(xxupp(=*)
Now combine two lower bounds of KL( 2z) + KL 2.). Using an intermediate step in Case 1, and Eq. (19), we get
1
KL (L z1) + KL(Z,, 2,)
(KL 21) + KL 2,)) + (KL(2 + KL 20)
2
C2
n752
||2"
-2241 6 11:
2--1,
128
128
(Esupp(>*)
C22
1
| - =2"1
20-1.
128
E2c
30
((supp(>*)
é 2222
112-11- - 21
Σ E
128
(E 1, < 1, and S 1)
,
(Lemma 16 and Lemma 19)
128
This proves the second part of the lemma with C2 eC2
Now are ready to prove Theorem 3.
Proof of Theorem 3. As argued in Section 4, with θ = KL(z", 2,) + 16 KL,,, 2T-1) and G. =
KL 21) + KL 2,), we have (see Eq. (3))
044 S θ 15 St.
25

---

Published as a conference paper at ICLR 2021
We the proceed as,
KL (2411, + 1
20
C
KL 22411 21) +
KL(z" 2441)²
(Lemma 2)
2KL (2 x,)²+ c ,L 22+1)²
(by Lemma 17 and Lemma 18)
2
C²
(KL(2)+1, )² + KL(2", (2+1))²)
2
(C1 eC²/64 I 1/64 shown in the proof of Lemma 2)
C2 (KI,(2+11, 21) + KL[(2, 1))
4
C
2 4
07+1
Therefore, ,++1 5 O 13y Cs O O. 15n C₁ 0 Also, recall 21 20 (1u 1x 6n+ MN and thus θ KL(z*, 21) S (M Therefore, the conditions of Lemma 12 are satisfied with p 1 and q MNN and we conclude that
64
C,
+ C²
where C' max (In(MN), 128+2 In(MN)
128+2 Lu(MN) C5
Next we prove the main result. Set To =
12800C" 1"
For 2 To, we have using Pinsker's inequality,
4C'
n/²g²
2 - 22el1 s 21|2= - 2zlli 2|1yy* uill s 4KL 2n) -
To
100
||= - zell? < 21 - 2.-1 + 2 - 2
I 411x* 8.+1 41 x; 11? + 411yy T 11 + 411 -::-1---ll---
< 8KI.(2,, 2241) 8KI, 2t)
128C"
- 1280 S
To
100"
Therefore, when t 2 To. the condition of the second part of Lemma is satisfied, and we have
1
2 (2 2)) +
C2
KL( 2x)
KL("", 2241)
(by Lemma 2)
2
C2 O++1.
(C2 C
2//2/115 1228 < 1/128 shown in the proof of Lemma 2)
2
Therefore, when t 12 To. 0.41
0
15n2 32
O,+1, which further leads to
θ, S0. (1+ 15
To
S0 (1
C5
To-t
<I(MNN) 1+ 15n/²C2 To-t
32
32
32
where the second inequality uses Eq. (15). The inequality trivially holds for t < To as well, so it holds for all
We finish the proof by relating KL(z*, 2:) and O(+1- Note that by Lemma 16, Lemma 17, and Lemma 19, we have
2z
1|2
16
2,
||2 2,41 112 + 12441 - 2e
KL(x", (2) 5
<
I 4
min:esupp(=))
27,6
9c2
62
26

---

Published as a conference paper at ICLR 2021
We continue to bound the last term
2
2 + || 2,112
e²
wi+1 xx 11+1/12- +11l/*
112 + ||0++1 x2,12 + 11 yell
4
62
x
Te+1lli
112
+
111" yo+1
12 +
|
xz
11 + 1 yell?
4
(|a2112 S
|a|l]))
128
KLL 21+11
KL (1(++11, 21)
(Pinsker's inequality)
22
16
16
128
O1+1.
22
Combining everything, we get
V128
128 128In(MN)
15ryAC2
(L(2",z)) S V0+1
1
32
which completes the proof.
E PROOFS OF LEMMA 4 AND THE SUM-OF-DUALITY-GAP BOUND
Proof of Lemma 4. Below we consider any x' * 2 Z. Considering Eq. (1) with (u, I|uu v11 and using the first-order optimality condition of E we have
(a++1 - 2)(2)()))) (z' 2+11) 2 0, (zt+1 21+1 ((F(2))) (x' - -z+11 2 0.
Rearranging the terms and we get
(2 - T.)T(2² (z' 2++1) 2 1)())) (2(+1 - 22)
= 11(++))) T (E1+1 z²) + 17 (F(z.) - F(2++))) (ž441 - 2¹)
2 (2(+)))) ( (8e+1 =z') 1 - 2.+11l|2++1 - x'1l
2 nF((++)) T (Ee+1 -2') || E+ 11111111111 - 2'1l.
and (Z++1 - 2.41) - 2141) 2 (1)) (2++1 - =1)
nF ) (E1+1 - x²) + 17 (F(z)) F(z(+1) (x1+1 - =²)
2 n (2(+1) T (Z141 - -z/) nL|l= z1+1 11|1l1 |x+1 =z'll
n) ) (2++1 - z²) - 5 1 z
z ||| z'1|-
Here, for both block, the third step uses Hölder's inequality and the smoothness condition Assump- tion 1, and the last step uses the condition 77 I 1/(8L). Upper bounding the left-hand side of the two inequalities by || - 2 2 - z'll and ||ze+1 1=+1ll|za - z'll respectively and then rearranging, we get
| ='1l (1Eiit -Zell + E - 21tall 2 (F((2))) ((2+1 - =²),
|21+1 - z'1l (12-11 E+t1ll + 811 g||z (111l1 (F((211) T - z²).
Therefore, we have
2 2 | - -2el + 11 E(+1ll)
(F((21+1) ) [T]]((2l (2(41 - 2'113
|| - 2/12
1 |1 24t1ll)
(1(((()+1)) (z1+1 x2') x2)13
|a1+ E
|| - =2112
27

---

Published as a conference paper at ICLR 2021
Finally, by the triangle inequality and the fact (a + b)2 s 2a + +b??, we have
[|:+ Ee1l 5 E11ze Sst2ll)
2
|| Eell
8
9
2t
Ee+1l) 11l
2
|
x/ ||
+
2 -
8
81
(112
2/12 + ||
E(+1113)
32
2
| 2++1l [511z1 2e+1ll
1111
1+1l
+|| El+1ll
2 E++1ll + 9 || - 2++1l)
1A
81
(1|
20111
+ ||, 12+1l1),
32
which finishes the proof.
Next, we use Eq. (4) and Eq. (6) to derive a result on the convergence of "average duality gap" across time. First, we use the following lemma to relate the right-hand side of Eq. (6) the duality gap of zz.
Lemma 20. Let Z be closed and bounded. Then for any z E Z, we have ar(z) S max F2)) (z-
Proof. This a direct consequence of the convexity of ʃ(, y) and the concavity of ((x, )):
(z(2)= max (f v/) f(x.v)) f(z y) f(x' ('Xx
Tyy (Vul(a,,)) (y' y) v.)(2,))) y) (ar x²)) max F(z) (z 2²).
max (a' (xXxx)
z'eZ
With Lemma 20, the following theorem can be proven straightforwardly
Theorem 21. Let Z be closed and bounded. Then OGDA with n S BE ensures + ET az((z) =
O TVT for any T, where D A sup,,>'E2 || 2'|l-
Proof. We first bound the sum of squared duality gap as (recall Gi = || - ze|12 + || - 2
(a)(21)
maxF(z)) (2) -z')
(Lemma 20)
z'EZ
1=1
t=1
81
(G-1+ G1)l22 =2112
(Lemma 4)
32n
D2
T
0
(0,-1- 0 9,+0, θ. - -
(Eq. (4))
D2
=
0
(telescoping)
112
Finally, by Cauchy-Schwarz inequality, we get $ -T S I az(21)²
0
nvT
28

---

Published as a conference paper at ICLR 2021
This theorem indicates that a (zt) is converging to A rate of ay(2i) O1 ( would be compatible with the theorem, but not directly implied by it. In a recent work, Golowich et al. (2020b) consider the unconstrained setting and show that the extra-gradient algorithm obtains the rate (2x) = O (() ). under an extra assumption that the Hessian of f is also Lipschitz (since Golowich et al. (2020b) study the unconstrained setting, their duality gap a is defined only with respect the best responses that lie within a ball radius centered around the equilibrium). Note that the extra-gradient algorithm requires more cooperation between the two players compared to OGDA and is less suitable for a repeated game setting.
F THE EQUIVALENCE BETWEEN SP-MS AND METRIC SUBREGULARITY
In this section, we formally that show our SP-MS condition with _ = 0 is equivalent to metric subregularity. Before introducing the main theorem, we introduce several definitions. We let Z S 2 [ TRKK (2" and Z follow the same definitions as in our main text). First, we define the element- to-set distance function
Definition The element-to-set distance function d: RK 2 IR is defined as d(z,S) inf || ='11.
The definition of metric subregularity involves a set-valued operator T 2 + 2 which maps an element of Z to set in I
Definition 6. A set-valued operator T is called metric subregular at (z for E T(z) if there exists K > and a neighborhood Qt of & such that
d(v T(z)) 2 nd(z, (v))
for all z E where x E (T- = u E Txx). If 2, we call T globally metric subregular.
The following definition of normal cone is also required in the analysis:
Definition 7. The normal cone of Z at point z is N(2) ig 2)) 0, Vz' Z (we omit its dependence on Z for simplicity). Equivalently, (z) is the polar cone of the convex set Z z (a property that we will use in the proof).
Now ready to show that our SP-MS condition with 8 is equivalent to metric subregularity of the operator N + F, defined via: (N + F)()) = tg + F(z) g E [N))
Theorem 22. Let 2 E Z". Then the following two statements are equivalent:
(W+ + F) is globally metric subregular at (z* (²*,)) .0) with O;
For all z E 2",", maxzez F(z)
(x-z') x- 2 kdl(z,
Proof. Let T = N F. Notice that
z E 2
22' - F(2)) (x)) + O (N F)().
Therefore, T(x") indeed holds, and we have T 7'((0) Z This means that the first statement in the theorem is equivalent to
d( Tx)) 2 kd(z, T (0)) + d(O,N(()) + F(z)) 2 nd(z, 2").
This inequality holds trivially when 2 E Zz, Thus, to complete the proof, it suffices to prove that d(0,,((z) + F(z)) max F(2) T =-= for E z To do so, that
(==z')
d(0))(()) + F()))
= d(- =d(-F()),N(z)) =(>= - (-x))(- =[(W)())-F(33)]
29

---

Published as a conference paper at ICLR 2021
where (z) = (g g - 0. Vn (2)) is the polar cone of (2) and the last step is by Moreau's 's theorem. Now consider the projection -F(z) onto the polar cone (z):
argmin (x) (x)*(z)
|| F(z) y|
argmin (2F Tx y |
(x)*
2F(2) y (EA"(=)
argmin
11vll + 113111
|y
argmin A20, (E)* ||
(2)F(z) 2 x²)
where the last equality is because (z) cone. Next, we find the 2" and X that alize the last argmin operator: notice that the objective is increasing in F(z) 2, so z= argmingex ||=||= (F(z) =}, and thus A = =F(22) when F(z) z S and X = otherwise. Therefore.
[-==))( = X max {0.
max - -F(2) 2 (x)
Note that (2) is the polar cone the conic hull of 2 - z. Therefore, Nerrefore,N((1) = (ConicHulll z)) ConicHull 2 z) and
max { max 0, max - F(=) = 0, max F(z)T (EN
=2)
x'E2
1| - =||
Finally, note that when = E 2\2"" 2", we have maxz'ez F(z)T(2 -2)) > 0. Combining all the facts above, have shown dz), + F(=)) maxz F(z)
(=-2")
xx-x
G PROOF OF THEOREM
Proof of Theorem 5. Let p milgex m x Gy maXyey min x Gy be the game value. this proof, we prove that there exists some c > such that
max x Gy p c|ı (x)] s'Ey
(20)
for all x E X. Similarly we prove
p TT Gy 2 clyy Ny (y)l
max
x'EX
for y E y. Assume that the diameter of the polytope is D co. Then combining the two proves
F(z) T (z =²))
1
1
max F(z) (z z') =²)= D
max Gty min ar
Gy
2 z'll
D x'
x²'
c
(ly Hy- (2)l1 + || II. (z) || Il (z)]l,
D
meaning that SP-MS holds with 3 = 0. We break the proof into following several claims.
Claim 1. X, are polytopes, then x and y* are also polytopes.
Proof of Claim 1. Note that X {ar E X max x. Gy S p). Since y is a polytope, the maximum is attained at vertices of y: Therefore, x can be equivalently written as { X maxyev(y) Gy S p}. where V(D/) is the set of vertices of y. Since the constraints of X' are all linear constraints, X' is polytope.
TTy
With Claim without loss of generality write x
X² = fx E RM a < bi, for 1,... L,
c. x S di, for = I,..., K}
30

---

Published as a conference paper at ICLR 2021
where the a,-a x Σ by constraints come from X' and the c. v d, constraints come from maxyev(y) x: Gy S p. Below, we refer to a a: S b, as the feasibility constraints, and c. x S d; the optimality constraints. fact, one can identify the i-th optimality constraint as C; Gy (8) and d3 p. where yd is the i-th vertex of y. This is based our construction of X in the proof of Claim 1. Therefore, K = [V())
Since Eq. (20) clearly holds for x E 2",, below, we focus on an x E X' and let x Ix (a)).
We say constraint is light at a: if a. x² by or e. x= di- Below we assume that there are & tight feasibility constraints at and k tight optimality constraints at x:". Without loss of generality, we assume these tight constraints correspond to I,..., and I,..., respectively. That is,
a x bs. for i 1, 1,..., c x=x== di, for i 1, ,,..., k.
Claim 2. x violates at least one of the tight optimality constraint at x².
Proof of Claim We prove this by contradiction. Suppose that satisfies all l: tight optimality constraints at x². Then a must violates some of the remaining K - k optimality constraints (oth-
erwise æ E X²)). Assume that it violates constraints K I..... ......K K for some 1 S K k. Thus, we have the following:
c a d. for i = 1.... K n; c x d: for i = K
1, K.
Recall that c. x² < de for i = i there exists some x' that lies strictly between a and x that makes all constraints hold (notice that and x' both satisfy all feasibility constraints), which contradicts with 11x- (xx-(x)= x²
n and c: x= < d, for all i = K + 1,..., K. Thus,
Claim 3. maxyey (x Gyy' pp) maxie(1...... of (x x²).
Proof of Claim Recall that we identify e; with Gy and d, = =p. Therefore,
max (x Gyy -) max iE(I...., ((D)) (c. x di) 2 max il(l...))
(c] d:) max c. c (w==
y' Ey
iE :E(I.....))
where the last equality is because cj x² d; for I....,k. k.
Recall from linear programming literature Davis (2016a;b) that the normal cone of expressed as follows:
X at x= is
No. { x''= x² x MRM (Ix- -
Σ p:a; Σ qec:
p 2:2 0, qi
The normal cone of X at x' consists of all outgoing normal vectors of X originated from x". Clearly, x belongs No.. However, besides the fact that we also have the additional constraints that x E X. We claim that in our case, x - x" lies in the following smaller cone (which subset of N
is a normal vector of X
Claim 4.
x-xx belongs to
k
Ma.
paa +
a.c: P
2 O, q 20 a
T
Σ p.a. + Σ
C.c, 1=1
< 0, Vj = 1, 1.....J
1=1
1=1
Proof of Claim As argued above, x - xx E No., and thus x x² can be expressed as
Σlm P;a, + Ek= q:c; with 2 0. 2 0. To prove that x - x" E Mar, we only need to prove that it satisfies the additional constraints, that is.
a, (x - x²)
<0, 0, Vi = I,...fl.
31

---

Published as a conference paper at ICLR 2021
This is shown by noticing that for all == 1, I....,
a (x - x²) ) = (a. x² -b;) + a; (x x²)
(the i-th constraint is tight at x²)
a, (x* + x x bi
a x b; S 0.
(x X)
Claim 5. x-x can be written as D p;a; + + qic, with pa C' - x+1 for all i and some problem-dependent constant <0.
Proof of Claim Notice that Furthermore, |-==="
20-" ||-==1|| ||
E MM (because 0 x xx E Ma and Mz is a cone).
-- E {v
E RM ||0|
S 1}. Therefore, x- -----1 Ma n {o E BM
|| I 1). which is bounded subset of the cone Ma..
Below we argue that there exists large enough C" > such that
:e:: PS... S O², vij 2 M N || s 1}
p.a +
P.
To see this, first note that P is polytope. For every vertex T of P, the smallest C" such that T belongs to the left-hand side is the solution of the following linear programming:
min C s.t. 1 = p:a; + qcc, 0 0 C.. P..q..C
Since T E Mar, this linear programming is always feasible and admits finite solution C₁ Do. Now let C" = max C. where V(P) is the set of all vertices of P. Then since any v E P can be expressed as a convex combination of points in V(P), a can be also be expressed as Ei P:a.
Σ C;C; with 0 S Pt, C
x x--=" can be represented Σ p.a. + q.c, with 0 S Pt. q S C². This further To sum up.
implies that x x can be represented as Di= P.a; + Ei= q.e, with 0 S Ps qi S C" x Notice that C" only depends on the set of tight constraints at x".
Finally, we are ready combine all previous claims and prove the desired inequality.
Define A, A a. (ac x²) and C, _ cT (ar x*). ). By Claim 5, we can write æ xx as Σ( p:a; + Σ Ei=1 dcc; with 0 S pi, I I x=1 and thus,
b P.A Σ g.C. Σ pia + Σqc qc
(x (x-x") = || x11
On the other hand, since x² E Ma by Claim 4, we have
Σ
P:A: = Σ
paa (x - x=)
1=1
1=1
and
Σ C.C. <
max [E(I....k)
C2
Σ
max
C. 10'1--1--" x
[e(1....k)
1=1
where in the first inequality we use the fact p; 2 0, and in the second inequality we use the fact
max 43 Ct > (by Claim 2) and q C²
x=
32

---

Published as a conference paper at ICLR 2021
Combining the three inequalities above, get
max Ci iE iE(
[ 1.
kC
Then by Claim 3,
max (a: Gty -P) iE k)
2 max
C 2
x x=1
y'EN
kC"
Note that k and C' only depend on the set of tight constraints at the projection point x", and there only finitely many different sets of tight constraints. Therefore, we conclude that there exists a constant > 0 such that m (x: Gy' - p) 2 c| - x=I holds for all x and x", which completes the proof.
H PROOF OF THEOREM AND THEOREM
Proof of Theorem 6. Suppose that f is g-strongly-convex in æ and r-strooglyycooncaee in y, and let
(x", (x",y") E Z*. Then for any (x, y) we have
f(a.y) - f(==; y) S V=f(a, y) (x - x²)
?
2 x x 13,
f(z, - f(z y) - v fz, y) (y' y)
2 yyy
y y²
Summing up the two inequalities, and noticing that f(x, y²) f(x", 2 0 for any ,0"")"" E 2", we get
P(z) x²) 2 2 x= =1
and therefore, for $ Z',
F(z)T [z - 2*)
2 2
2 ==11.
2/ 201
which implies SP-MS with B = 0 and C = 7/2.
Proof of Theorem 7. First, we show that f has a unique Nash Equilibrium 2" (a* yy)
((0, 1), 1)). As f is strictly monotone decreasing function with respect to y1. we must have
oi 0 and 35 = 1. In addition, x = (0, 1). maxyey f(x, y) = minyey yr" = 0. If
+ (O. 1). then by choosing y² (0. 1). fax, yy) _ >> Therefore, we have xx (0, 1), which proves that the unique Nash Equilibrium is x=' = (0, 1), y" (0.
Second, we show that f satisfies SP-MS with $ have
fact, for any z (x, y) # 2", we
2nx
1
2n 1
1/1
T2 1
F(z) (z 2z==")- =
2ny
+ 21
1/1
L1/2
2n (1)
2n 2n
1/1
x7 + 11
> 4n
(Jensen's 's incquality)
2
(a + 12)
2n-2 2
Note that ||2 - 2² = V
(1- 22r7 1 -277. Therefore, we have
F(z] (z-z") アーー Iz z²| 2n-11 This shows that f satisfies SP-MS with 3 = 2n 2 and
2m-22
33

---

Published as a conference paper at ICLR 2021
1 PROOF OF THEOREM 8
Proof of Theorem 8. As argued in Section 5, with +: = =| - 11z--1z-(p (2:)1 + T - 21-1
<: - 1|:41 - =ıl1² + || 2 11, we have (see Eq. (4))
0+11 S θ 4
(21)
Below, we relate &e to O.+1 using the SP-MS condition, and then apply Lemma 12 to show
2dist (21, 21 C²)
if 0,
0.5
{[(1 1 + (+) $ dist (21, (21, )++ + (c
(22)
1 if B 0,
c,0 81 22
} as defined the statement of the theorem, This enough to prove
where C5= min| the theorem since
dist (ze, 2²) < || - 11z-
< 2|| - 1l (2 + 21|2+11 =zel?
I 320,+1 S 32
Next, we prove Eq. (22). We first show simple fact by Eq. (21):
16
16
| 2:11² S Ge S 15
θ S ... S
(23)
15
Notice that
1
220-1
-2
(1|2+11 21112 + || Eell²)
2
2
1
1672
(F(2++1) T ((t++1 - -z')]
2 -| - =2
81
z'EZ
sup
12 2/11
(Lemma 4)
1
2
12
2111 112 +
|| -Ilz. -112-(21+1) 11 21((++11)
(SP-MS condition)
81
160
1
15
} (12.111 2(0+1]) + +112,1 II
min
81
2
160,
(by Eq. (23))
16
1
15
(1E441- - -1 - 11 (2++1) 13)
0+1
min
28 81
2
320,
(by Hölder's inequality: (a (1+1)(( + 1)²² 2 (a + 8)111)
min
Cs
1
A
θ
3+1
(recall that Cj = minf 16 }11
23
10,
=C'O
(define C' min
Cs 2
Combining this with Eq. (21), we get
O < - C+0 8+1
(24)
When 3 0. Eq. (24) implies O.41 < (1 + - which immediately implies O, < (1 +
C5) - θ < 20, (1 + Ct When 3 > 0, Eq. (24) is of the form specified in Lemma 12 with
p 3 and C". Note that the second required condition is satisfied: C3 + 1)0f < Therefore, by the conclusion of Lemma 12,
2+1
< 1.
2-4
2
2
2
3/
4
+ < max
1
max
,40
t
C²B
C5
B
4
2
t 3
<
1 + 4
θ
+ 2
3
C
Eq. (22) is then proven by noticing that θ dist?
1isst((21,)) 27).
34

---

Published as a conference paper at ICLR 2021
J PROOF OF THEOREM 9
Proof of Theorem 9. Consider the following 2 x bilinear game with curved feasible sets:
0
f(z x Gy
[2]
22
//
1
0
y/2
X y y: 5 y1 - 2
0
0 02 S
32
Ø1 2
2
4'
0 0.
y2
1/2 2 11
4'
Below, we use Claim 1 Claim 5 to argue that if the two players start from To = Yo = 30 70
( t), and use any constant learning rate // S - then the convergence is sublinear in the sense that
= - 11 || 2 (11/t). Then, in Claim 6, we show that in this example, SP-MS holds with / = 3.
Claim 1.
The unique equilibrium x- y O.
When = O. clearly m f(x, y²) = O. When x # O, we prove maxyey f(æ, y") > 0
below. If r o O, we let ví = _ and 1/2 ta²² 2 (which satisfies y' E )), and thus
1 " 1(x, 3') 021/ x11/22 x1 2 x1
4 1 0.
If 1 0 but 22 # O, we let v 2. 1/2 1. and thus
f(æ, y¹) σ2ví 215/2 = 22 > 0.
Thus, maxyey f(x, y²) > 0 if x + 0, and x² = 0 is the unique optimal solution for æ. By the symmetry between x and y (because solution for y is y" 0.
G ), we can also prove that the unique optimal
Claim 2. Suppose that In = yo = En = go = ( 1). Then, at any step E [T), we have æ = yr and C. = Dr and all æt yt, 3t, ÿ. belong to {u E TR.2 u2 = uf)
We prove this by induction. The base case trivially holds. Suppose that for step t, we have æ; = yr. 3, = Dr, and Ft; yt, T,, Dt {u R² u2 w. Then consider step 1. According to the dynamic of OGDA, we have
Ut,
Ft,1 + 1/8,,2
} 1
11x
17
Ut.1
11x
Fr,2
(25)
Vr.2
1 + 199t.22
x(+1
11x
Øt+1
7)
I1,x
1/.,1
Tz+1.2 1/1
Di+1
Hy
Øc + 17
x2,2
Ily
Tr.1 + 1/-2,22
[221
11.2
11-2,1
F2,2
11+1,1 + 1722,22
Vt+1 1ly
Mc+1 +
1ly
-It,11
1i+1,2
1f
According to induction hypothesis, we have 3.41
Do+1, which further leads to 2z+1 = Yi+1-
Now we prove that for any satisfics that क = Zz. value theorem, there exists
E1 D2
such that æ 2 0, 32 and x2 < x
Tj
IIx
T2
r2
Otherwise, suppose that . T2. Then according to the intermediate
Z T2
that lies in the line segment of
xi [2
and
T such that 7 T2
T2
Moreover, as Z1 IV
I 0,
x2
32 < 3. we know that
X. Therefore, we have
- æ|| < || 1r 2=1. which leads contradiction.
35

---

Published as a conference paper at ICLR 2021
Now consider T(+1- According to induction hypothesis, we have ( + 1121.22 27 B,,2 2
22 7M1,11 If equalities hold, trivially we have $111,1 2 ,2 1,2 according to Eq. (25). Otherwise, as Ft. + 2 O, _t,2 1W,.1 S 2. according to the analysis above, we also have
12-1,1 =
f+412. Applying similar analysis to 4 tt+1 and yt+1 finishes the induction proof.
Claim 3.
With r S 1 the following holds for all 2 1, 61
1
1
2 1 2T,,,
(26)
T2 E [2,-1,1
4, 21-1 + 4n
(27)
We prove the claim by induction on L. The case I trivially holds. Suppose that Eq. (26) and Eq. (27) hold at step l. Now consider step + 1.
Induction to get Eq. (27).
According to Claim 2, we have
E + na? o
Tt+1 = 1xx Ft --
11.2 1/,1
1xx
1701,,1
and 0.41 (u, v² for some [0. 1/]. Using the definition of the projection function, we have
T++11 = argminn (fa1 + n - u) 2 + (0) 1 x²²²²
A argmin g(u).
Me [0.
Now show that argmin (u) argmin (u)) Note that
Vg(u)= = 2(u Te, - m3 + 4u (u² + quet,1 27,1)
(28)
Therefore, when Y.4 using 2t, S 1.4 we have
Vg(u)= 21pr2 21por,11 2
(29)
which means g(u) > ((2)) On the other hand, when u < 0, using Tt, S 2.
we have
Vg(u)= 2u 4u < O,
(30)
which means g(u) > g()). Combining Eq. (29) and Eq. (30), we know that argmin,ueo, g() =
argmin s(u). Therefore, T1+1, is the unconstrained minimizer of convex function g(u), which
means (9( = O. Below we use contradiction to prove that Et+1, 2 _t,1 4n If 1--1,1 < f.,1 4n
Eq. (28) and get
Vg(ā++1,11 = 2( 2,,1 nmīī,) + 48 (21+1,1 + 11t111 fh,1)
< 2( 22(-4p - n + 18 (1 8m + 1617 2 21111)
17 22
11/111
+4t41,1 (2n 8n + 16
(Eq. (26))
17 22
<
15711
+ +48
(2n) + 161
2
17
< 2
no,
+ +4( - 4n0%, (2 + 167
(T+-11 < 8r,1 - -4102,)
2 1
1
2
+
641
25 25, 32, 256n 2
<
1
n
22
167
256
(ft,1 $ $
2
50,
36

---

Published as a conference paper at ICLR 2021
which leads to contradiction. Similarly, if T2+1,1 > Dt, + 4m07,1 we have
Vg(T++1.1) 2( ŁT,1 ) 11.11,1 ( + 1JE111 - (2.1)
> 2(4 -1 ) + 4 (y + 811711 + 161/2//11)
2 0.
(Egq. (26))
The calculations above conclude that
T++1.1 [ 4, Rt,1 41
(31)
Induction to get Eq. (26). Similarly, we have
{ (fe+1,1 + yol,1 - -u)² u)²+ ++++((22)) (f - - 1 -m?) - argmin
74111 argmin x
(c(0.
Vh(u) = 2(u -f,41,1 - ( + 4u(u2² + 172111 n 1741,1),
and Vh(s++1.1) 0. 1141 15 have
Vh(T+111) 2(1 - -141,11 - no7,1)) + 41 (5 + q,1,1 - (141,1)
< -14111 2n - 3x 1, + 211
(I1+1,1 < (001111) S F1. $ 2
0.
141111 > 27 1,11- we also have
Vh(2141.1) = 2(E4+1.1 - f14111 - ( + 4r (1 + 114111 - 21+1,1)
27++1,1 20 + +24
111
(01+1,1 > 27,+
2 27+1111 2n0 + 241
811(3r,11 - A
(Eq. (31))
2 28+11 2n + 24 + 8m - 4n )
(Eq. (26))
28 + 20pe41 + +24
32n""0,, 11,1
2+1.1
1 2
2 27,41.1 +
1
+ 24 ++,11
22n"2²,,221
(Eq. (26))
4
0.
(n S 64 Lt, S 2
Both lead to contradiction. Therefore, we conclude that xc-1 [5 22 22,,,,1, which finishes the induction proof.
Claim 4. 1t,1 2 R.,1 4np7,1 for 2 1.
The case / = holds trivially. For / 2 2, we prove this by contradiction. Using the definition of the projection function, we have:
1141.1 argmin { (a++1.1 + n2î, 1 u)² ++2 77 11r.1-11' -u²)²] e argmin/(ul) we [.
ue(o.
Similar to the analysis Claim 3, we have argmin ue 2o hu()) = argmin Mu,,, which means that Vh(I++11) = 0. Note that S गी and 0 < Tt,1 S according to Eq. (26) and Eq. (27), we have
31
33
3 E [ 4n Te,1 1 + 4n
C
Tt,1
St.1
32
32
which means that
[
16
64
F1,1
E
It 20
C
7 1,1,,
T++1.1
(32)
2
33
31
37

---

Published as a conference paper at ICLR 2021
If 11411 < F441,1 - -411 show that Vh(1441,1) O. In fact,
Vh(1(41,1) = - - + 40 (z + 1111,1 - -1(1111)
< <2(-An n ) + 421 (1
81 + 161
42 c2
64
111111111 1
1,141,11
81 1617 (6m7212+11) #141.11
(Eq. (32))
31
42 c2
64
111,1111 + 451+1,1
1,141111
+ 16n7:/41111
31
42 22
64
17 +4(ft+1,11
41
+
1617 1617
31
641
32111
256 7
T1+1,1
$ 167 2t,1
23
256 #1,1
(Tr,1 S 2)
00
which leads to contradiction. Therefore, we show that Ft,1 2 Tt,1 - 4n07,,1 for all 2
Claim 5. n
04 we have | - x01 Q(1/t).
Now we are ready to prove 2| - - 2 (1//t). First we show L., 2 27 for all t 2 1 by induction. The case = 1 trivially holds. Suppose that holds at step t. Considering step 1+ 1, we have
E1+1,1 2 _t, - 4
(Claim 3)
1
St,
(n S
16
2 S 5c,1 S 1 and 1 is increasing when
8)
2t 64t
(t 2 1)
2( + 1)
Therefore, ft,1 2 20
vt 2 1. This, by Claim 4 and the analysis above, shows that
Ft,1 2 Gr,1 41 2(1 +
Note that according to Claim 1, x² = 0. Therefore, we have || 111 finishes the proof.
2 Ft,1 2
which
2(+1))
Claim 6. In this example, SP-MS holds with B This can be seen by the following:
F(x) T (x x²)
2 max Fz)) T (z z') zEZ
max 2'EZ
22 2/
(a T Gyy - x -Gy
max d'EXy'Ey
max r'E
{-211/2 + æ2جÍ + x'1122 22y1}
2 2 + 22 + v/2 y
(picking y D2, V/2 22, = 32 z/2 v2)
1
2
(0I, 9! S 2
2 --2 5²
1
(I)
12 + 01 + v
(x2 2 (07, v2))
1
1
(01 22
v v2
CCauchy-Schwar
16
1
2 zz 11
(z* = (0,00000
16
38

---

Published as a conference paper at ICLR 2021
which implies B 3.
39


Reviews:
[{"review_id": "qLfT_o_H9Py", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nAll 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.\n\nConcerns:\n* 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. \n* 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\")? \n* 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?\n* [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.\n* [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 ?  \n* 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.\n\nMinor comments/typos:\n* 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).\n* (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.\n* 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. \n* Average-iterate cv: another reason not to do averaging is the lack of guarantee for non-convex losses.\n* 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).\n* In \"Other notations\", in supp(u), I think u is supposed to be in the positive orthant.\n* 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.\n* 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.\n* 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.\n* 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "mF_bV64807N", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nEven 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:\n\nOMWU:\n- 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. \n\nLooking 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.\n\nOGDA:\n- 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?\n\nFor 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).\n\n- 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?\n\nMoreover, 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?\n\n========= after discussion with authors ========\nDuring the discussion phase, the authors addressed my concerns and improved their results. Therefore I increase my score to reflect this.\n\n[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.\n\n[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).\n\n[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).\n\n[4] Liang, Jingwei, Jalal Fadili, and Gabriel Peyré. \"Convergence rates with inexact non-expansive operators.\" Mathematical Programming 159.1-2 (2016): 403-434.\n\n[5] Alacaoglu, Ahmet, Olivier Fercoq, and Volkan Cevher. \"On the convergence of stochastic primal-dual hybrid gradient.\" arXiv preprint arXiv:1911.00799 (2019).\n\n[6] Rockafellar, R. Tyrrell, and Roger J-B. Wets. Variational analysis. Vol. 317. Springer Science & Business Media, 2009.\n\n[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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VipahfFX4V8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n***\nStrength: 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.\n\n***\nConcern: 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?\n\n***\nFor 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.\n\n***\nDuring rebuttal: I thank the toy examples provided by the authors. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5W6_ZHZO2iV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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. \n\nThe 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? \n\nOverall, this is a nice paper and I recommend acceptance.\n\nRelated references: \nIn terms of fast convergence in bilinear zero-sum games with fixed learning rates\n[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.\n\n[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. \n \n\n[1] Bailey et al. Finite Regret and Cycles with Fixed StepSize via Alternating Gradient Descent-Ascent. COLT 2020.\n[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.\n[3] Cheung, Piliouras. Chaos, Extremism and Optimism: Volume Analysis of Learning in Games. arXiv preprint arXiv:2005.13996 (2020).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)