Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games
Authors: Yang Cai
Argyris Oikonomou
Weiqiang Zheng
Venue: NeurIPS 2022 Accept (2022)
Keywords: learning in games
smooth monotone games
last-iterate convergence rate
Nash equilibrium

Abstract: We study the question of last-iterate convergence rate of the extragradient algorithm by Korpelevich [1976] and the optimistic gradient algorithm by Popov [1980] in multi-player games. We show that both algorithms with constant step-size have last-iterate convergence rate of $O(\frac{1}{\sqrt{T}})$ to a Nash equilibrium in terms of the gap function in smooth monotone games, where each player's action set is an arbitrary convex set. Previous results only study the unconstrained setting, where each player's action set is the entire Euclidean space.  Our results address an open question raised in several recent work by Hsieh et al. [2019], Golowich et al. [2020a,b], who ask for last-iterate convergence rate of either the extragradient or the optimistic gradient algorithm in the constrained setting. Our convergence rates for both algorithms are tight and match the lower bounds by Golowich et al. [2020a,b]. At the core of our results lies a new notion -- the tangent residual, which we use to measure the proximity to equilibrium. We use the tangent residual (or a slight variation of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient algorithm) and prove that it is non-increasing between two consecutive iterates.

Fimite-Time Last-Iterate Convergence for Learning in Multi-Player Games
Yang Cai Yale University vang.ca@@yale.euu
Argyris Oikonomou Yale University argyissookooomo@@yal.eeuuu
Weiqiang Zheng Yale University
weigiang,zheng@yall.edde
Abstract
We study the question of last-iterate convergence rate of the extragradient algorilhm by [Kor76] and the optimistic gradient algorithmm by [Pop80] in multi- player games. We show that both algorithms with conslant step-size have last-iterate convergence rate of O VT to a Nash equilibrium terms of
the gap function in smooth monotone games, where each player's action set is an arbitrary convex set. Previous results only study the unconstrained setting, where each player's action set is the entire Euclidean space. Our results address an open question raised in several recent works [HIMM19, GPD20, GPDO20], which ask for last-iterate convergence rate of either the extragradient or the optimistic gradient algorithm in the constrained setting, Our convergence rates for both algorithms are tight and match the lower bounds by [GPD20, GPDO20J. At the core of our results lies a new notion the tangent residual, which we use to measure the proximity to a Nash equilibrium. We use the tangent residual (or modification of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient algorithm).
1 Introduction
We consider learning in monotone games,, a class of multi-player games introduced by [Ros65] that include many well studied games, e-g,, two-player zero-sum games, convex-concave games, A-cocoercive games [L.ZM]20], zero-sum polymatrix games [BF87, DP09, CD11), and zero-sum socially-concat games [FDMN09]. We focus on the following question: Can we obtain last-iterate convergence rate to Nash equilibrium in monotone games when all players act according to simple learning algorithm?
We adopt the multi-player online learning model introduced in [CBL06], where players interact with each other repeatedly. At every time step f, every player E N1) chooses
an action z, from her action set Z which we assume to be a closed convex set in R"; We
say the game is unconstrained if z RR for each player i. Player i's loss function e(0) (-) is determined based on the underlying game and the actions of the other players in round t.
Player receives the loss p(( (z,") well as some additional feedback that informs her how to improve her decisions in the future. In this paper, we assume that each player receives the
gradient feedback, i.e,, player receives the vector ve,") (z, (2()). We make an additional mild assumption that the game is smooth, i.e., all players' gradients are Lipschitz. Smoothness is a natural assumption that is satisfied in most applications and also made in the majority of works concerning monotone games.
36th Conference Neural Information Processing Systems (NeurIPS 2022).

---

Game class
Setting
Step size
Convergence rate
O(c=)) (see e.g., [Tsse95|
Strongly monotone
general
constant
[LS19, MOP19, ZMM 21))
Cocoercive
unconstrained
constant
0 T [LZM]20]
general
constant
Asymptotic [Pop80, HIMMI9]
Asymptotic (see e.g., [ZMM 17] [ZMA 18, MZ19, HAM21J)
Monotone
general
decreasing
unconstrained
constant
0 [GPD20]
general
constant
0 [This paper]
Table 1: Last-iterate convergence for no-regret learning in smooth monotone games with perfect gradient feedback. (*) The results hold for variationally stable games. (f) The result holds under an additional second-order smoothness assumption.
The standard metric to quantify an online learning algorithm's 's performance is the regret.
Formally, the regret of player i is defined as the difference between Σ (z(()) player
i's cumulative loss, and min E e() (z), the loss incurred by the best fixed action in hindsight. An online learning algorithm is no-regret if, even under an adversarially chosen
loss sequence ( he) its regret at the end of round T is sublinear in T.
vast literature on learning in games discusses the convergence to a Nash equilibrium using no-regret learning algorithms. However, most of the results concern only the time-average convergence, i.e., the convergence of the time average of the joint action profile, rather than the last-iterate convergence, i.e., the convergence of the joint action profile. From game-theoretic perspective, the last-iterate convergence is more appealing compared to only the last-iterate convergence provides description of the evolution of the overall behavior of the players. In contrast, the trajectory of the players' joint action may be cycling around in the space perpetually while still converges in the time-average sense as demonstrated by IMPP18]. Recently, a line of work is de- voted to obtain last-iterate convergence smooth monotone games [ZMB+17, 1MM+ ZMA+18, DP18, MOP19, HIMM19, LNPW20, GPD20, LZMJ20, ZMM+21]. However, un- less the game is strongly monotone or unconstrained, only asymptotic convergence is known. Moreover, many of these results crucially rely on decreasing step-size, which, as pointed out by [L.ZM220J, is unnatural from an economic point of view, because it treats newly acquired information with decreasing importance. Hence, the following question is of particular interest and is raised as open question in [HIMM19, LZMJ20, GPD20J.
the time-average convergence,
Can establish last-iterate rates if all players of a constrained smooth monotone game (*) act according to a no-regret learning algorithm with constant step size?
[LZM]20] first realizes the importance of question (*) and takes initial steps towards ad- dressing it. They show that all players follow the gradient descent algorithm with constant
has last- iterate convergence rate of O } to a Nash equilibrium in terms of the gap function. For smooth strongly monotone games, a subclass of A-cocoercive games, linear last-iterate con- vergence rates are known [Tse95, Mal15, LS19, MOP19, 22M+21]. Despite the generality of A-cocoercive games, several fundamental classes of games such as two-player zero-sum games, zero-sum polymatrix games [BF87, DGP09, CD11] and its generalization zero-sum socially-concave games [EDMN09] are monotone but not X-cocoercive. [GPD20] extends the result to smooth monotone games with an O( last-iterate convergence rate using VT different algorithm the optimistic gradient by [Pop80] under an additional second-order smoothness assumption. Note that gradient descent has been observed to fail to converge in even two-player zero-sum games (see e.g., [DISZ17]), so different algorithm is indeed needed. However, the results by [LZM]20] and [GPD20] only consider unconstrained games, while in most game-theoretic settings, the players' actions are constrained. For example, in finite games, a player is restricted to choose distribution over her finite set of actions. We summarize the results for last-iterate convergence in monotone games in Table 1.
step size, then for all smooth A-cocoercive games, the joint action (z 24
(N))

---

Our Contributions. Our first contribution is to provide an affirmative answer to question (*).
Contribution 1: In Theorem 3, we show that if all players of a constrained smooth monotone game act according to the optimistic gradient algorithm, which is no-regret, with a constant step size, then their joint action exhibits last-iterate convergence rate
of O in terms of the gap function (Definition 2) to a Nash equilibrium.
Our result holds in the constrained setting and does not rely on the second-order smoothness assumption made in [GPD20]. Moreover, our upper bound is tight and matches the lower bound of [GPD20].
The problem of finding a Nash equilibrium in a smooth monotone game is essentially equivalent to solving a Lipschitz and monotone variational inequality (VT) (Definition 5 in Appendix D which has been studied since the 1960s [HS66, Bro65, LS67, BS68, Sib70]. There is a vast literature on solving VIs, and we refer the reader to [FPO7] for further references. The extragradient (EG) algorithm by [Kor76] and the optimistic gradient (OG)
algorithm by [Pop80] are arguably the two most classical and popular methods for solving monotone VIs. Despite the long history, the last-iterates of both algorithms to asymptotically converge to solution of the monotone and Lipschitz VI, but no upper bounds on the rate of convergence had been provided for the general setting.
only known
We provide the first and tight last-iterate convergence rate of O VT in terms of the gap function for both EG and OG with constant step size for solving Lipschitz and monotone VIs (Theorem and Theorem 10 in Appendix I).
Contribution 2:
Our analysis of OG for monotone games directly applies to monotone VIs. To be more consistent with our discussion of ÔG, we state our last-iterate convergence rate of EG in the context of online learning in monotone games (Theorem 3).3 Prior to our work, last-iterate convergence rate of EG only exists in the unconstrained setting. [GPDO20] shows a O VT upper bound in terms of the gap function under an additional second-order smoothness condition. [GLG21] improves the result and shows that the same upper bound holds without the second-order smoothness condition but still requires the setting to be unconstrained.
Our Analysis. As mentioned in [GPD20], "The lack of existence of a natural potential function in general monotone games is significant challenge in establishing last-iterate convergence." Indeed, many of the natural quantities such as the gap function, the norm of the gradient, the difference of two consecutive iterates are provably non-monotone even in bilinear games. See Appendix] for more discussion and examples. We propose notion that (i) measures the proximity to a Nash equilibrium, and (ii) can be used to construct natural potential functions to analyze both EG and OG in monotone games. We call the new notion the tangent residual, which can be viewed as the norm of the gradient projected to the tangent cone of the current iterate (Definition 4). The tangent residual plays a crucial role in our analyses for both algorithms. Unlike the other quantities mentioned above, we show that the tangent residual is monotonically decreasing and has a last-ilerale convergence rate of O( VT
for EG. For OG, we prove that a small modification of the tangent residual is monotonically decreasing, which implies that the tangent residual has a last-iterate convergence rate of O( ((7)). Using the convergence rate of the tangent residual, we can easily derive the last-
iterate convergence rate of other classical performance measures such as the gap function and the total gap function. However, we suspect these rates can be challenging to obtain directly without the help of potential function. Finally, we establish the monotonicity of our potential functions using computer-aided proofs based on sum-of-squares (SOS)
TTecnicallly, the definition of Lipschitz and monotone VI captures finding Nash equilibrium in smooth monotone game as a special case, but the difference has little impact on our analyses, and our results hold for Lipschitz and monotone VIs.
2The last-iterate asymptotic convergence of FG can be found in [Kor76] and [FP07], and the last-iterate asymptotic convergence of OG can be found in [Pop80] and [HIMM199.
Allhoough EG is not no-regret learning algorithm (see Proposition 10 in [GPD20]), it is neverthe- less simple and natural learning algorithm.
3

---

programming [Nes00, Par00, Par03, Las01, Lau09]. Lau09. Indeed, our potential function of OG is directly constructed using SOS programming. Additionally, our computer-aided proofs can be easily verified by humans. We think the tangent residual and the SOS-based analysis might be of independent interest. See Section 4.2, Appendix B, and Appendix C for more discussion.
1.1 Related Work
Last-Iterate Convergence Rate for EG/OG like Algorithms. [GPDO20, GPD20] show lower bound of Q vT for solving bilinear games using any p-SCLI algorithms, which include EG and OG. In the unconstrained setting, if we further assume that either the game is strongly monotone or the payoff matrix A in a bilinear game has all singular values bounded away from 0, linear convergence rate is known for EG, OG, and several of their variants [DISZ17, GBV+18, LS19, MOP19, PDZC20, ZY19). The results for the constrained setting are sparser. Unless the game is strongly monotone, most results only guarantee asymptotic convergence, i.e, converge in the limit, [DP18, LNPW20]. Finally, recent paper by [WIZZ121b] provides linear convergence rate of OG for bilinear games when the domain is a polytope. They show that there is a problem dependent constant 0 < < 1 that depends on the payoff matrix of the game as well as the constraint set, so that the error shrinks by a 1 - c factor per iteration. However, C may be arbitrarily close to 0, even if we assume the corresponding operator to be L-Lipschitz. Overall, their "problem-dependent bound is incomparable and complements the worst-case view taken in this paper, where we want to derive the worst-case convergence rate for all smooth and monotone games. Our results are the first last-iterate convergence rates in this worst-case view and match the lower bounds by [GPDO20, GPD20J.
Other Algorithms and Performance Measures. is well-known that both EG [Nem04]
and OG |HIMM19, MOP20J have time-average convergence rate of o in terms of the gap function for smooth monotone games. Other than the gap function, one can also measure the convergence using the norm of the operator if the setting is unconstrained, or the natural residual (Definition in Appendix E) or similar notions the setting is constrained. In the unconstrained setting, [Kim21], [YR21], and [LK21] provide algorithms
that obtain O(2 ( convergence rate in terms of the norm of the operator, which is shown to be optimal by [YR21] for Lipschitz and monotone VIs. In the constrained setting, [Dia20] shows the same ((7) convergence rate under the extra assumption that the operator is cocoercive and loses an additional logarithmic factor when the operator only monotone. I last-iterate convergence rate in terms of the natural residual or Our result implies a O /
the gap function for both EG and OG. A main motivation of this paper is theorete,,,,,, that is, we would like to view natural learning algorithms as models of agents' behavior in online learning and understand the speed for the overall behavior to converge to a Nash equilibrium. Although some of the results above are natural for games, they either only hold in the unconstrained setting or do not converge in the last-iterate sense. From this game-theorete view point, we believe understanding the last-iterate convergence rate of these natural learning algorithms is an important problem.
Preliminaries
is the l norm and (x)) denotes inner product on R". A continuous game G is denoted as (W, hieN]. (f (ie(N) where there are N players N {1,.... NJ. Player i E A chooses action from closed convex set (i) Rd such that Eg == Ile C R" and wants to minimize her cost function f(i 2g + R. For each player i, we denote by z--i the vector of actions of all the other players and by zf) the action of player i. When players play according to action profile z E Zg, player i receives gradient feedback V V_af (2(1), (z(1),..,,z))) (..,,(())) A Nash equilibrium of game G is an action profile z' Zg such that f (2') S (2((1) z 6) for any z0(0) 2
We consider the Euclidean Space (R", || II), where || |

---

Let (.)() (V I0 (f ((,.., Jin (()) be an operator that maps any joint action in Z to the corresponding joint gradient feedback vector in RR. When G is clear from context, we omit the subscript and write FZ(2) (2g resp.) as F(z) (2 resp.).
Nash Equilibria of Monotone Games. Throughout this paper, we focus on smooth monotone games (Definition 1). It is well known that finding Nash equilibrium of monotone game is exactly the same as finding solution to the variational inequality with monotone operator Fg (Lemma 1).
Definition 1 ((Ros651). We say game G is L-smooth and monotone if the operator Fg is L- Lipschitz (i..., Vz 2, L. ||z 11--2- z'1 [lFg(z) Fg(('))l) (I) and monotone (ie.., V'z z Z, (Fg(z) - Fg(22), z 2 0).
Remark 1 (Monotone and Concave Games). For any monotone game = (2()
(C(N)) the monotonicity condition implies that for any fixed 2(-1), player i's cost function is convex in 2!i. Thus, all monotone games are concave games. However, the converse is not true as illustrated in the following example.
Consider a two player game G where player 1 (or player 2) chooses action x E R (or y E R),, and (x, y) f(2)) (x, = x y. Clearty, (() (x,,) (or f(2) y)) is convex
their cost functions are f()) (x,
in x (or y) if we fix (or x). is not hard to see that Fg (x, = (y,x) for any x, E R. Therefore,
the game is not monotone as (Fg(x,y) - Fg x), (x (y,x)) = - 2 y)² < 0 for any + y.
Lemma (1.4.2 Proposition [ For a monotone game 9, an action profile z" is a Nash equilibrium if and only if (Fg(z"),z* =2) S 0, E Z.
Remark 2. One sufficient condition for a Nash equilibriumm z" to exist is when the set Z is bounded, but there are also other sufficient conditions that apply to unbounded Z. See [FP07] for more details. Throughout this paper, we only consider monotone games that have a Nash equilibrium.
Definition 2 (Gap and Total Gap Function). For a monotone game G, two stan- dard ways to measure the proximity of an action profile E Z to Nash equilib- rium, are by its gap function and total gap function. Let D be a fixed parame- ter. The gap function is defined as GAFg,D(Z) =max:eZ2B(a.)) (Fg(z),2-z)) z), where D), is a ball with radius D centered at z. The total gap function is defined as TGA = LieN (z) - min .D) (100))))
When G and D are clear from context, we omit subscripts and write the gap function (total gap function resp.) at z as GAP(Z) (TGAP(z) resp.).
Remark 3. The total gap function is the sum of the suboptimality gaps, i.e., a player i's suboptimality
gap is her cost under minus her cost after best responding to z(-i) within B (z((i, D). As the suboptimality gap is nonnegative for every player, a small total gap implies that no player can deviate from their current action to significantly improve their cost, and the action profile is close to a Nash equilibrium. Thus the total gap is O if and only if players are at a Nash Equilibrium.
In Lemma 2, we show that the gap function with radius D is an upper bound of the total gap with radius VN' where N is the number of players, so if an action profile has small gap function, then again no player can deviate to significantly reduce their cost. A corollary of Lemma 1, is that the gap function is 0 if and only if players are at Nash Equilibrium.
D
The Optimistic Gradient Algorithm. Let wy be the action profile played at day k and assume that player updates her action according to the OG algorithm. For arbitrary 2
(i)
and " player's 's i action day k + is wht such that (i)
(1)
(w) (?))
2k-1 17
V 20)
and w ( R+1 = IZ
(
V (1) (wo (1)
4hen Z is bounded, we choose D to be the diameter of Z. When 2 is unbounded, the standard choice is to choose D so that all the iterates of the algorithms are guaranteed to maintain in the ball B(z, D). See Appendix D for more details.
5

---

Note that action 2 is not being played by player i and is only used compute action 2 When all the players update their actions according to OG with step-size '/, let wo = (w)) (1) ...., wo and = (2) (..))))))))) Then at day k + 1, players pick action
profile Wk+1, where:
Ex = z [2x-1 =)(==)]
Wk+1 I1z [2x - F)(())))
(1)
Clearly, the OG update rule is well defined for any operator F and any closed convex set 2, and this is how the OG algorithm is defined for variational inequalities.
The Extragradient Algorithm. Let 2 be the action profile played at day 2k and assume that all players update their actions according to EG with step-size y,. Then players play according to action profile
at day 2k + and action profile 2x+1 at day 2k 2, where:
1 1
xx+1 = 1l [2k - FF(z)),
ZR+1 = Il z - F)
(2)
Similarly, the EG update rule is well defined for any operator F and any closed convex set 2. For the rest of the paper, we only consider the case where all players use the OG (or EG) algorithm with constant step-size We omit superscripts that denote players' identity and use Expression (1) (or Expression (2)) for the update rule when players use OG (or EG).
3 The Tangent Residual and Its Properties
We formally introduce our key performance measure, the tangent residual. We define the tangent residual over operators rather than games, as it will be easier to provide intuition behind its formulation.
Definition 3 (Unit Normal Cone). Given closed convex set Z C R" and a point E Z, we denote by Ng (z) = (v E R" (u,z' (1)= < 0,4z' E Z) the normal cone of Z at point z and by Nz(z) = {u E N (z) : ||ا|| < } the intersection of the unit ball with the the normal cone of Z at Note that (z) is nonempty and compact for any E Z, as (0, (0 E Nz(z).
Definition 4 (Tangent Residual). Given an operator F 2 + R" and closed convex set Z, let
(2) == (z' E IR" (z',a) < 0, Va E Nz(z)}
} be the tangent cone of 2, and define Jz(z) [z] + (z)... The langent residual of at E 2 is defined as r'an (F,2) (z) == || |2(2|| F(z)] z||.
An equivalent definition is plan (() := |11((2)112 max (E))(;)), (a, F())22 (F(z)A)
Remark 4. We show the equivalence of the two definitions of tangent residual in Lemma 5 in Appendix D. We may use either of them depending on which one is more convenient.
When the convex set Z and the operator F are clear from context, we are going to omit the subscript and denote the unit normal cone N(z) Nz(z) and the tangent residual as p(("(2) (F (z). Although the definition is slightly technical, one can think of the tangent
residual as the norm of another operator F, which is projected all directions that are not "blocked" by the boundary of Z if one takes an infinitesimally small step c F(z), which is the same as projecting F to 1z(2), Intuitively, if the tangent residual small, then the next iterate will not be far away from the current one.
Tangent Residual and Its Connection with Games. Given monotone game G, we denote by G (z) (Fg. (z). In the next lemma, we argue that a small tangent residual implies
$Interested readers can find a thorough introduction of the tangent cone and its definition for general feasible sets in Chapter 6.A of [RW09]. When the feasible set is convex, Theorem 6.9 of [RW09] provides more succinct definition of the tangent cone and normal cone. When the feasible set is closed convex set, Corollary 6.30 of [RW09] further states that the tangent cone is the polar cone of the normal cone, As we consider closed convex sets in our paper, we choose to define the tangent cone for closed and convex sets directly as the polar cone of the normal cone, as it is the most convenient definition for us.

---

small gap and total gap, hence it suffices to show that the last-iterate has small tangent residual. The proof is postponed to Appendix E.
Lemma 2. [Adapted from Theorem 10 in [GPDO20] and Proposition 2 in [GPD20]] Let g = (N, (2"))e {f(i (E(N)) be monotone game where {2() )ieN are closed convex sets. For 2 E 2, we have GAPg, - D. D.rg((2) (z) and TGAPg,D(Z) S GAP GAPg..DD(())))) VN
Last-Iterate Convergence Rate for EG and OG
We prove the last-iterate convergence rate for EG and OG. We first describe our proof plan.
Proof Plan. Our analyses for both algorithms follow the same three-step procedure: (i) define potential function that measures the proximity to Nash equilibrium of the current iterate; (ii) prove a best-iterate convergence rate, that is, show that in 7 steps, there exists one iterate whose potential function is small; (iii) show that the potential function is non- increasing, so the last-iterate is the best-iterate, and the best-iterate convergence rate becomes the last-iterate convergence rate.
The first major challenge we face is to choose the appropriate potential functions. In the unconstrained case, the central quantity is the norm of the operator Fg. The key component of the analyses [LZM]20, GPDO20, GPD20, GLG21] is to establish that the norm of the operator Fg at the last iterate (also the T-th iterate) is upper bounded by O + which
implies
O 1 last-iterate convergence rate for the gap function. In the constrained setting, vT
the norm of the operator is poor choice to measure the proximity to a Nash equilibrium, as it can be far away from even at a Nash equilibrium.
Potential function for EG. We use the tangent residual as the potential function for EG. Our starting point is to find suitable generalization for the norm of the operator in the constrained setting. A standard generalization is the natural residual (Definition Appendix E), which takes the constraints into account and is guaranteed to converge to 0 at the Nash equilibrium. Unfortunately, we observe that the natural residual is not monotonically decreasing even in basic bilinear games, making it difficult directly analyze. Similar non- monotonicity has been observed for several other natural performance measures such as || - Zx 1/2|1," 6 || Z 11|1, max (F(z), - z) and max,c (F(z;), Z - z), leaving all these quantities unsuitable as a potential function. See more discussion in Appendix J. Indeed, tangent residual is the only natural generalization of the norm of the operator that always monotone in our numerical experiments.
in
Potential function for OG. We choose the potential function $(2,, Wk) = [[F(z)) F(=x))11 +z))(2 in our analysis for OG. The potential function can be interpreted as the squared tangent residual plan(zz)? and extra correction term [[F(z)) 1( The potential function is discovered via SOS programming, with more details in Section 4.2.
4.1 Best-Iterate Convergence
En route establish the last-iterate convergence EG and OG, we first show a weaker guar- antee known as the best-iterate convergence. In Lemma 3 we show that when all the players use EG for 2- T steps (OG for T steps), then there exists f* E [T] where pl (2r+1) 0 VT
(#D2,,, S ((+) resp.). The proof for EG builds upon the proof for the best-iterate w.r.t. E x 4 by [Kr766, FP07], while the proof for OG builds upon the best-iterate proof for | - w by [WLZL21a, HIMM19]. The proof of Lemma is in Appendix F.
Lemma 3. Let (A, (0) heN, (
Hie(N) be L-smooth and monotone game where (2()) JieN are closed corvex sets and let z" be a Nash Equilibrium of G. Assume that all the players
61|ze 2x+1/2|1 is proportional to the norm of the operator mapping introduced in [Dia20].
7

---

update their actions using the F.G algorithm with arbitrary starting action profile zo and step-size ry E (0, 1). Then for and any T 0, there exists E
[T] such that:
plun (zp 11) 1 1+ (n 1
I|e -
"f vT WV1-(nL)
Assume that all the players update their actions using the OG algorithm with arbitrary starting action profiles 20,00 and step-size 1j E (0, 2t) Then for and any T > 0, there exists t" E [T] such that:
[4+ 61 617 ((r,,w))) - 172
2 ||z0 ==
161/2 611
1w2 -
-001=))))) =0ll²)
1 1 4,2
4.2 Monotonicity of the Potentials
In this section, we prove that y!m (zx) (#(2z, resp.) is non-increasing across iterates of EG (OG resp.), which, in combination with Lemma 3, implies the last-iterate convergence rate of smooth monotone games when all players update their actions using EG (OG resp.).
SOS Programming. Suppose we want to prove that a polynomial g(x) E R[x] is non- negative over semialgebraic set S = {x gi(x) < 0, vi E (x), = 0, vi [N]), where each (x) (1;
resp.) is also polynomial. One way is to construct a certificate of non-negativrty, by providing
of nonnegative coefficients {p: 2 O]ie(M] and (e(N such that g(x) + Li[ P: (((x) + LicIN] 9: hx(x) ) is a SOS polynomial. Surprisingly, if g(x) is indeed non-negative over S, a certificate of non-negativity always exists as guaranteed by foundational result in real algebraic geometry the Krivine-Stengla Positivestellen- satz |Kri6,, Ste74J, generalization of Artin's resolution of Hilbert's 17th problem |Art27]. The SOS programming [Nes00, Par00, Par03, Las01, Lau09] is systematic way to search for such certificate using semidefinite programming. See Appendix B for details.
Our approach is to apply SOS programming to search for a certificate of non-negativity for (zz))z) p (21+1)² ) and (Zz,, wx) - Φ( Wx+1) for every k, over a semialgebraic set defined by the update rule of the corresponding algorithm and set of constraints Z.
Two important challenges with this approach is that the number of variables depends on the dimension of 2 and there are infinitely many constraints associated with the problem (e.g. the set { (F(z) - F(z'), z - z') 2 0,,z''' E 2)). We provide a detailed exposition for the reduction of the number of constraints and the efficient formulation into a SOS program in Appendix G.3, where we prove the monotonicity of our potential function for EG in both the unconstrained and constrained settings.
Searching for the potential functions. The potential function of our analysis of OG is directly discovered using an SOS program. The program || (((2=+)))(2,|((((a)))) tan (2,) - (=*((x+1)² under (i) the constraint that the linear combination is non- increasing, and (ii) the constraints induced by properties of the operator F(.), the update rule of OG and the set Z (See Appendix G.3 for a demonstration of the induced semialgebraic set of EG algorithm).
formulated by searching over linear combinations of (FF()))
and
Our basis functions are chosen in way that we can search over all candidate potential
functions that are linear combination of (i) pla ,l,)(2z))² and (ii) any squared norms of a linear combination of F(zz), F(wr)) Observe that the difference between two consecutive iterates of any of the above functions can be expressed we chose.
linear combination of the basis functions
We then use the linear combination output by the SOS program as the potential function in our analysis. We believe our heuristic for finding a potential function could be useful in
To avoid finding the trivial linear combination, i.e, all coefficients equal to U, we also use the objective function in the SOS program to encourage a non-trivial solution if one exists by, for example, maximizing the sum of the coefficients of the linear combination.

---

other settings. In general, one first choose collection of basis functions that may be part of a potential function, then use SOS programming to search over all linear combinations of the basis functions subject to the constraint that the linear combination is non-negative to discover the potential function.
Initially, our candidate potential functions included the squared tangent residuals evalu- ated at 2ę and wy and all degree-2 monomials of all vectors of interest. In other words, we searched over all linear combinations of (i) y (zx) pfan (ax)) and (ii) any linear com- bination of degree-2 monomials of Zk, F(zx), W0, F(wx), subject to the constraint that the candidate potential function is non-negative. We included the tangent residuals in the basis of our potential functions due to their central role in the analysis of the EG algorithm (we show that the tangent residual is non-increasing across the iterates of the EG algorithm in Theorem 2).
We also observed that any non-zero linear combination of only the tangent residuals evalu- ated at z and wy is not monotone for the OG algorithm. Motivated by this, we enlarged the basis to include the degree-2 monomials of 2,, F(2x), WK, F(wy) so that we had the flex- ibility to introduce very flexible class of potentials functions, we gradually removed elements in the basis, and the basis that we selected in the paper was minimal basis such that: (i) it contains non-increasing potential function and (ii) it enjoys best-iterate convergence (See Lemma 17 in Appendix H.2) and (iii) the discovered potential function bounds the gap functions.
extra correction term in the potential function. Starting from this
We establish the monotonicity of the potential functions in Theorem and Theorem 2, which are both stated for general monotone operators over convex sets rather than games for technical convenience. We turn our attention back to games in Section 4.3 where we provide formal last-iterate convergence guarantees for smooth monotone games.
4.2.1 Monotonicity of ( wx) for OG in the Unconstrained Setting
To better illustrate our approach, we prove in Theorem 1 the monotonicity of @ (zz, wy) for the OG algorithm in the unconstrained setting. Note that this is already strengthening of [GPD20], where we provide a simple potential function that can be used to directly argue that [|F(z))11 O without making any second-order smoothness assumption.
Theorem 1. Let F: : Z - R" be monotone and L-Lipschitz operator. For any Zk, We R", the unconstrained OG algorithm with step-size 17 (0, + satisfies ( w)) 2 $ (zk+11, (2K+1,We+1).
Proof. Since F is monotone and I--Lipschitz, we have (F(zx+1) F(zx), 2x+1) S 0 and 1[ - 1(*x+1)]1 L2| w - Z 2|2 < O. We simplify them using the update rule of OG and 122 < 1. In particular, we replace zt zk+1 by (F( and wx+1 Zk+1 with () - F(wx).
(F(zx41) - F(zz), F(w2+1)) 00
(3)
[[F(W++1) - F(Zx+1))I - [1(((+++1)- - F(xx)11 s o.
1
(4)
It not hard to verify the following identity:
[[F(()) F(w;))) 1|F(z))1 [[F((++1) - F( ||
1
+2 LHS of Inequality(3) + + LHS of Inequality(4. 2 =11(((()) + F(wx+1) -(F()))))((22)))1
2F(22))
Thus, || [((()) F(wx)) 2 ([=(z)) [[F(z++1) F(w2+1)l1 + |[F(Z++1)11
4.2.2 Constrained EG and OG
In the constrained setting, the approach is more complicated due to the projections and we postpone any exposition Appendix G.3. We state the results in the following theorem.
in the unconstrained setting, rao (F.R (z) = [[

---

Theorem 2. Let Z C RD be closed convex set and F: 2 R" be monotone and L-L.ischhtzz operator. For any Zk E 2, the EG algorithm with step-size if (0, 1.) satisfies y (zx) Z plan (zx+ 1). Moereover, for any Zr, WP: E 2, the OG algorithm with step-size nf E (0, xt) satisfies (Z2,, wK) 2 ① (2x+1, (x)1), where (2x, wpg = [1F(zz) - F(xx))l² pla (zx)² 2 for all k.
4.3 Last-lterate Convergence of EG and OG
In this section, we formally combine Lemma 3 and Theorem to show the last-iterate convergence of EG and OG with respect to the tangent residual, gap function, and the total gap function. Recall that when all the players update their actions using the EG algorithm, then Zę is the action profile played at day 2 k and =x+ is the action played at day 2- + 1, while when all the players update their action profile using the OG algorithm, then wy is the action profile they play at day k. The formal proof of Theorem 3 is postponed at Appendix F.
Theorem 3. Let G = (N, (z HieN, (f hiN() be an L-smooth and monotone game where ( HeN are closed convex sets and let z" a Nash Equilibrium of G. Assume that all the players update their actions using the EG algorithm with arbitrary starfing action profile zo and slep-size
E (0, 1). Let Do = 3|:0-221 11|l then for and any T > 0 and D > 0,
(1-(11
GAP(ZT) TGAP(ZT) S
Do WVT TGAP(2T14)
pla (ZT),
max
D
VN.D
Jan (an GAP(ZT14)
(1+ n1) Do nVT
max
(ZT+1),
D
VN-D
When all the players update their actions using the OG algorithm with arbitrary start-
v2(21
ing action profiles zo, wo and step-size 1f E (0, H) Denote Do = v1 4-1
V 11+661L4) - 2=11 (16 + 617 L1)l[wo zoll². Then for any >> Oand > 0,
( (1TT(111)))) GAP(WT TGAP(WT)1))
Do NVT
max
<
D
V
For EG, according to our bound in Theorem 3, the optimal value of 17 is
1 which implies
V2L'
that for any D 2 0, GAP(ZT) < 20 |DL
and when D 2 ||zo - 2*11, then GAP(ZT) < 6D'L. vT
vT
For OG initialized with Wh = Zo, by numerically optimizing the bound on Theorem 3, we set 17 to be 0:4 in which case for D
> ||zo 11 GAP(WT+1) <
26.82021 Both upper VT
bounds matches the Q D2L) lower bound for EG, OG, and more generally all P-SCLI /T
algorithms [GPDO20, GPD20J in terms of the dependence on D, L,, and T.
In Appendix we show that EG and OG algorithm also have last-iterate convergence for monotone variational inequalities with respect to several standard performance measures (See Appendix D for the formal definition of monotone variational inequality).
5 Conclusion
We provide the first and tight last-iterate convergence rate of the EG and OG algorithm for smooth monotone games and Lipschitzs and monotone VIs. Our proof is based on the tangent residual, which is a new proximity measure to Nash equilibrium, and an accompanying SOS-based analysis. We believe our techniques may be useful in the study of last-iterate convergence for other algorithms.
Acknowledgement: This work was supported by a Sloan Foundation Research Fellowship and the NSF Award CCF-1942583 (CAREER). Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing.
10

---

References
[Art27] Emil Artin. Über die zerlegung definiter funktionen in quadrate. In Abhandlun- gen aus dem mathematischen Seminar der Universität Hamburg, volume 5, pages 100-115. Springer, 1927. Issue: 1.
[BF87] LM Bregman and IN Fokin. Methods of Determining Equilibrium Situations in Zero-Sum Polymatrix Games. Optimizatsia, 40(57):70-82, 1987.
[Bro65] Felix E. Browder. Nonlinear monotone operators and convex sets in Banach spaces. Bulletin of the American Mathematical Society, (15))-880-785, 1965.
[BS68] Haïm Brezis and Moise Sibony. Méthodes d' d'approximation d'itération pour les opérateurs monotones. Archive for Rational Mechanics and Analysis, 28(1):59-82, January 1968.
[CBL06] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cam- bridge University Press, 2006.
[CD11] Yang Cai and Constantinos Daskalakis. On Minmax Theorems for Multiplayer Games. In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algoritiums (SODA), Proceedings, pages 217-234. Society for Industrial and Applied Mathematics, January 2011.
[COZ22] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate conver- gence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities (version 2), 2022.
[DGP09] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The Complexity of Computing Nash Equilibrium. STAM Journal on Computing, 39(1):195-259, 2009.
[Dia20] Jelena Diakonikolas. Halpern Iteration for Near-Optimal and Parameter- Free Monotone Inclusion and Strong Solutions to Variational Inequalities. ar Xii::20002.08872 [cs, math], April 2020. arXiv: 2002.08872.
[DISZ17] Constantinos
Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arviv preprint xrxio1111..01411, 2017.
[DP09] Constantinos Daskalakis and Christos H. Papadimitriou. On Network Gen- eralization of the Minmax Theorem. In Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming: Part II, ICALP '09, pages 423-434, Berlin, Heidelberg, July 2009, Springer-Verlag.
[DP18] Constantinos Daskalakis and Ioannis Panageas. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. page 18 pages, 2018. Artwork Size: 18 pages Medium: application/ppi / Publisher: Schloss Dagstuhl Leibniz-Zentrum fuer Informatik GmbH, Badern/SSarbruece Germany Version Number: 1.0.
[DT14] Yoel Drori and Mare Teboulle. Performance of first-order methods for smooth convex minimization: novel approach. Mathematical Programming, 145(1):451- 482, 2014. Publisher: Springer.
[DTdB21]
Radu-Alexandru Dragomir, Adrien B. Taylor, Alexandre d' d'Aspremont, and Jérôme Bolte. Optimal complexity and certification of bregman first-order methods. Mathematical Programmning, 2021.
[EDMN09] Eyal Even-Dar, Yishay Mansour, and Uri Nadav. On the convergence of regret minimization dynamics in concave games. In Proceedings of the forty-first annul ACM symposium on Theory of computing, pages 523-532, 2009.
11

---

[FMP18] Mahyar Fazlyab, Manfred Morari, and Victor M Preciado. Design of first- order optimization algorithms via sum-of-squares programming. In 2018 TEEE Conference on Decision and Control (CDC), pages 4445-4452. IEEE, 2018.
[FPO7]
Francisco Facchinei and Jong-Shi Pang. fies and Complementarity Problems. Springer, 2007.
Variational Inequali-
[GBV 18] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks, Xiv preprint ar Xiv:18880 10551, 2018.
[GLG21] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient Method: 50(1/K); Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity. arXiv:2110.04261 [cs, math], October 2021.
arXiv: 2110.04261.
[GMG 22] Baptiste Goujaud, Céline Moucer, François Glineur, Julien M. Hendrickx, Adrien B. Taylor, and Aymeric Dieuleveut. Pepit: computer-assisted worst-case analyses of first-order optimization methods in python. CoRR, abs/2201 /201..00004 2022.
[GPD20] Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. arXir:2010.13724 [cs, math], October 2020. arXiv: 2010.13724.
[GPDO20] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last Iterate is Slower than Averaged Iterate in Smooth Convex- Concave Saddle Point Problems. 0kio:2002.00057 [cs, math, statl, July 2020. arXiv: 2002.00057.
[HAM21] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adap- tive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium. arXio:2104.12761 [cs, math], April 2021. arXiv: 2104.12761.
[HMМ199] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-graddiet methods. In Ad- vances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
[HS66] Philip Hartman and Guido Stampacchia. On some non-linear elliptic differential- fineettiialfuniiiinall equations. Acta Mathematica, 115(none):211-310, January 1966. Publisher: Institut Mittag-Leflerr
[im21] Donghwan Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190(1):57-87, November 2021.
[Kor76] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[Kri64] Jean-Louis Krivine. Anneaux préordonnés. Journal d' l'analyse mathématique, 12:p- 307-326, 1964. Publisher: Springer.
[Las01] Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):76--117, 200, Publisher: SIAM.
[Lau09] Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geomelry, pages 157-270. Springer, 2009.
[LK21] Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex-nonconea minimax problems. In Annual Conference on Neural Information Processing Systems, 2021.
12

---

[LNWW20] Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Last iterate convergence no-regret learning: constrained min-max optimization for convex-concave landscapes. 4rXie:2002.06768 [cs, statt, February 2020. arXiv: 2002.06768.
[LRP16] Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints. SIAM Journal Optimization, 26(1):57- January 2016. arXiv: 1408.3595.
[LS67] J. L. Lions and G. Stampacchia. Variational inequalities. Communi- cations Pure and Applied Mathematics, 20(3):493-519, 1967. -eprint:
[LS19] Tengyuan Liang and James Stokes. Interaction matters: A note on non- asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMLR, 2019.
[LZM]20] Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games. In Proceedings of the 37th International Conference on Machine Learning, pages 6161- 6171. PMLR, November 2020. ISSN: 2640-3498.
[Mal15] Yu Malitsky. Projected Reflected Gradient Methods for Monotone Variational Inequalities. SIAM Journal on Optimization, 25(1):502-520, January 2015. arXiv: 1502.04968.
[MOP19] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach. #xXi::1901.0851 [cs, math, staf], September 2019.
arXiv: 1901.08511.
[MOP20] Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of (1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM J. 3 2020.
2020.
[MPP18] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twentyy-inth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-27111111 2713-2777..0 SIAM, 2018.
[MZ19] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Math. Program., 173(1- 2):46-5007, 2019.
[Nem04] Arkadi Nemirovski. Prox-method with rate of convergence O (1/t) for varia- tional inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229- 251, 2004. Publisher: SIAM.
[Nes00] Yurii Nesterov. Squared functional systems and optimization problems. In High performance optimization, pages 405-440. Springer, 2000.
[Par00] Pablo A. Parrilo. Structured semidefinite programs and semialgebraic geometry
methods in robustness and optimization. California Institute of Technology, 2000.
[Par03] Pablo A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programmingg 96(2):933-320, May 2003.
13] Antonis Papachristodoulou, James Anderson, Giorgio Valmorbida, Stephen Prajna, Pete Seiler, Pablo Parrilo, Matthew M. Peet, and Declan Jagt. Sostools version 4.00 sum of squares optimization toolbox for matlab, 2013.
13

---

[PDZC20] Wei Peng, Yu-Hong Dai, Hui Zhang, and Lizhi Cheng- Training GANs with centripetal acceleration. Optimization Methods and Software, 35(3):955- 2020.
Publisher: Taylor & Francis.
[Pop80] Leonid Denisovich Popov. modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845 848, 1980. Publisher: Springer.
[Ros65] J. B. Rosen. Existence and uniqueness of equilibrium points for concave nt- person games. Econometrica, 33(3):520-534 1965.
[RTBG20] Ernest K. Ryu, Adrien Taylor, Carolina Bergeling, and Pontus Giselsson. Op- erator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization, 30(3) 2020.
[RW09] R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis. Springer Science & Business Media, 2009.
[Sib70] Moïse Sibony. Méthodes itératives pour les équations inéquations aux dérivées partielles non linéaires de type monotone. CALCOLO, 7(1):55-183, March 1970.
[Ste74] Gilbert Stengle. nullstellensatz and a positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207(2):87-97, June 1974.
[THG17a] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Exact Worst- case Performance First-order Methods for Composite Convex Optimization. SIAM Journal on Optimization, 27(3):1283-1313, January 2017. arXiv: 1512.07516.
[THG17b] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Performance estimation toolbox (PESTO): automated worst-case analysis of first-order opti- mization methods. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 1278-1283. IEEE, 2017.
[Tse95] Paul Tseng- On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathemalics, 60(1):237- 252, June 1995.
[TVT21] Sandra SY Tan, Antonios Varvitsiotis, and Vincent YF Tan. Analysis of op- timization algorithms via sum-of-squares. Journal of Optimization Theory and Applications, 190(1):56-811 81, 2021.
[WLZ121a] Chen-Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate Convergence of Decentralized Optimistic Gradient Descent/ Ascent in Infinite- horizon Competitive Markov Games. arXiv:2102.04544 [cs, stat], July 2021. arXiv: 2102.04540.
[WLZ121b] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Lin- ear Last-iterate Convergence in Constrained Saddle-point Optimization. arXiv:2006.0951 [cs, stat], March 2021. arXiv: 2006.09517.
[YR21] TaeHo Yoon and Emnest K. Ryu. Accelerated Algorithms for Smooth Convex- Concave Minimax Problems with $ mathcal| Rate on Squared Gradient Norm. arXiv:2102.0792 [math]] June 2021. arXiv: 2102.07922.
[ZBLG21] Guodong Zhang, Xuchan Bao, Laurent Lessard, and Roger B. Grosse. A unified analysis of first-order methods for smooth games via integral quadratic constraints. Journal of Machine Learning Research, 22:103:11103:3, 2021.
[ZMA $18] Zhengyuan Zhou, Panayotis Mertikopoulos, Susan Athey, Nicholas Bambos, Peter W. Glynn, and Yinyu Ye. Learning in games with lossy feedback. In Annual Conference on Neural Information Processing Systems, pages 5140-5150, 2018.
14

---

[ZMB 17] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W Glynn, and Claire Tomlin. Countering Feedback Delays in Multi-Agent Learning. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[ZMM 17] Zhengyuan Zhou, Panayotis Mertikopoulos, Aris L. Moustakas, Nicholas Bambos, and Peter Glynn. Mirror descent learning in continuous games. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), 2017.
[ZMM+21] Zhengyuan Zhou, Panayotis Mertikopoulos, Aris L. Moustakas, Nicholas Bambos, and Peter Glynn. Robust Power Management via Learning and Game Design. Operations Research, 69(1)3331-345, January 2021.
[ZY19] Guojun Zhang and Yaoliang Yu. Convergence gradient methods on bilinear zero-sum games. Xiv preprint ar axX::19988005669 2019.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Our results theoretical.
We state the assumptions of our results in the statements of the lemmas.
(c) Did you discuss any potential negative societal impacts of your work? [No] Societal Impacts are discussed in Appendix A.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions clearly stated in the statement of the theorems (e.g. Theo-
rem 3).
(b) Did you include complete proofs of all theoretical results? [Yes] We include proof for all theoretical results either the main body or the appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? []
(d) Did you include the total amount of compute and the type of resources used
(e.g,, type GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g,, code, data, models) or curating surating/releasing releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material
URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating: curating? [N/A]
(e) Did you discuss whether the data you are bssing/curatinng contains personally
identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screen- shots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "ubh8HuialtC", "reviewer": "Reviewer_ZxuX", "summary": "This paper studies the last-iterate convergence rate to a Nash equilibrium in monotone games (with gradient feedback). It extends previous work to analyze the convergence of no-regret learning algorithm with constant step size in (possibly) constrained games. The authors propose a novel notion, namely the tangent residual, and use it to discover the potential function to show that the extragradient algorithm and the optimistic gradient algorithm have tight last-iterate convergence rates. ", "questions": "- On the search for the potential functions: are the potentials discovered by the SOS program unique (given a set of basis functions)? If not, do we have a solution selection problem (i.e., different potential might provide different rates?) \nCan you please give some intuition of the choice of the basis functions in line 302 (or this choice simply comes from the needs in the proof)?\nWhat is the running time/ complexity of SOS programing (e.g., w.r.t. the number of basis functions)?\n\n- On parameters tuning: Is the parameter $eta$ in Lines 349 and 350 are chosen to give the optimal constants in the convergence rates? If not, can we do it (and get rid of the bigO notation)? Technically, the choice of D can be any upper-bound of the one given in Lines 349 and 350, right? Notably, we can also use the popular choice as stated in footnote 4?\n\n- Perspective: can this line of work be extended to stochastic gradient feedback case? (see e.g., discussion in Appendix A.4, of [GPD20])\n", "limitations": "the authors adequately addressed the limitations and potential societal impact of their work", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well-written. The achieved results are quite interesting and relevant. The proofs and appendix are very detailed and provide strong supports for the claimed results. The tangent residual notion and the proposed computer-aided proof technique are, as far as I know, novel in this research context; moreover, they might be useful beyond the scope of this paper.\n\nWeaknesses: no major weaknesses. Optimally tuning parameters of the algorithms (and explicitly determining the constants in convergence rates) might make the results clearer. \n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eRSEyZsdeqM", "reviewer": "Reviewer_3NQG", "summary": "This paper studies the last iterate rate of convergence of extra gradient and optimistic gradient algorithms in smooth monotone games with continuous convex action sets. More specifically, the authors prove that if players employ those algorithms with a constant step size they achieve last iterate convergence rate $O(1/\\sqrt{T})$.", "questions": "I would like to ask about the definition provided in this paper for the tangent cone. I am not familiar with this definition, could the authors provide some reference for it?\n", "limitations": "This paper has no negative societal impact. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written and clear. The technique used for finding the potential function needed to prove the result is novel and interesting. \nI consider the contribution of this paper clear and quite important, since it complements and extends existing results from the unconstrained to the constrained setting.\n\n\nMinor comments: In line 231 there is a typo - hence (an) it suffices.\nLine 276: action -> action.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cZyweK1xWkl", "reviewer": "Reviewer_x4Lr", "summary": "The paper focuses on proving last iterate convergence for both Extra Gradient and Optimistic Gradient Descent methods for monotone games in both constrained and unconstrained settings (these setting captures convex-concave min-max optimization for example where the operator is monotone). The authors show tight last-iterate convergence of $O(1/\\sqrt{T})$ without any uniqueness assumptions that prior works had consider (without proving rates). Please note that there were works that established last iterate convergence that the dependence on the parameters of the game were not clear (it might be exponential for example in the size of the game). The authors show dependence that is polynomial in the parameters of the game (Lipschitz constant and diameter of the domain for constrained). The idea is first to establish best iterate convergence and then show that the tangent residual (effectively the Hamiltonian) is a potential function.  ", "questions": "My only question is if these results can be generalized for weak MVI type functions/problems. ", "limitations": "The work is theoretical.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1) The paper is well written and the proof is elegant. \n2) The problem was an open-question that researchers were actively working on including the reviewer.\n3) The result does not hide any exponential dependence on the size of the game, it is very clean with normal assumptions.\n\nCons:\n1) The idea of using sum of squares was already in the literature to construct/prove potential functions. This fact though does not decrease the significance of this work.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QxkxhonnRZv", "reviewer": "Reviewer_bUVX", "summary": "This paper provides the first last-iterate convergence rates of extragradient algorithm (EG) or the optimistic gradient algorithm (OG) to Nash equilibrium of constrained smooth monotone games in terms of the gap function and Lipschitzs and monotone variational inequality, which match the existing lower bounds $\\mathcal{O}(T^{-1/2})$. Tangent residual is proposed as a new proximity measure to a Nash equilibrium and used for convergence analysis.", "questions": "(1) Why does contribution 1 on page 3 not include EG? \n\n(2) Typo in Table 1: \"cocoercive\". \n\n(3) Typo in Line 95: \"require**s** the setting to be unconstrained\". \n\n(4) In Definition 1, you might use parentheses like (that is, ...), (i.e. ...), since at first sight, I misunderstood the formula after i.e. as equivalent to the condition that $F_{\\mathcal{G}}$ is both monotone and Lipschitz. Also,  $F_{\\mathcal{G}}$ is monotone if and only if $f^{(i)}$ is convex for any $i$, yes? If yes, You might add that intuition. \n\n(5) In Definition 2, both gap functions are non-negative, and become 0 if and only if $z$ is a Nash equilibrium, right? If yes, you might write down this intuition to help readers outside this area understand. Also, a larger (total) gap function value indicates a larger distance (and thus smaller proximity) to Nash equilibrium, right? If yes, I think it better to describe the gap functions as distance measures (instead of proximity) to Nash equilibrium. \n\n(6) Is it convenient to clarify the intuition of the notions in Definitions 3? \n\n(7) $r_{\\mathcal{G}}^{\\text{nat}}$ appears in line 230 for the first time so here you may cite Definition 7 in Appendix E. (In Line 254, it should be Appendix E, not D.)\n\n(8) Are the potential differences $r^{tan}(z_k)^2-r^{tan}(z_{k+1})^2$ and $\\Phi(z_k,w_k)-\\Phi(z_{k+1},w_{k+1})$ polynomial? If not, how can you apply SOS programming to them? \n\n(9) It seems better to compute for more iterations in the experiments and plot the potential function value and the performance measures in Appendix J, to show that all of them approach 0 (yes?), and only the potential function value decreases. ", "limitations": "In the checklist, item 1b said \"Did you describe the limitations of your work? [Yes] Our results are theoretical. We state the assumptions of our results in the statements of the lemmas.\" Do you consider the assumptions as limitations? If yes, do you intend to weaken them in future works? \n\t\nThe end of the introduction also proposes a future direction to apply the techniques of this paper to stochastic gradient feedback, which implies a limitation and its solution. ", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The algorithms and problem settings exist in the literature, but the non-asymptotic convergence rate in constrained smooth monotone games is new and tight, and the notion of tangent residual and the choice of potential functions for convergence analysis are novel. Hence, I think the originality is sufficient.\n\t\nQuality: This is a complete piece of work with both strengths and weaknesses. The claims are well supported by the theoretical analysis which looks reasonable, elaborate, and sophisticated (I have read the Lemmas and theorems but have not checked the proof). The experiments look reasonable to me, but it seems that the numerical evidence can be stronger if the authors compute for more iterations in the experiments and plot the potential function value and the performance measures in Appendix J. (see my final question for detail). \t\n\t\nClarity: The submission is very clear and well organized. The intuition behind some notions could be clarified as elaborated in my questions.   \n\t\nSignificance: The results look important to me since it provides the first non-asymptotic convergence rate in constrained smooth monotone games, which also matches the lower bound. ", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept