Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Authors: Yang Cai
Gabriele Farina
Julien Grand-Clément
Christian Kroer
Chung-Wei Lee
Haipeng Luo
Weiqiang Zheng
Venue: NeurIPS 2024 poster (2024)
Keywords: Last-Iterate Convergence
Zero-Sum Games
Optimistic Multicaptive Weights Update
Optimistic Gradient
Primary area: algorithmic_game_theory
TL;DR: We prove that a broad class of algorithms that do not forget the past quickly, including OMWU and OFTRL, all suffer arbitrarily slow last-iterate convergence even in simple zero-sum games.

Abstract: Self play via online learning is one of the premier ways to solve large-scale zero-sum games, both in theory and practice. Particularly popular algorithms include optimistic multiplicative weights update (OMWU) and optimistic gradient-descent-ascent (OGDA). While both algorithms enjoy $O(1/T)$ ergodic convergence to Nash equilibrium in two-player zero-sum games, OMWU offers several advantages, including logarithmic dependence on the size of the payoff matrix and $\tilde{O}(1/T)$ convergence to coarse correlated equilibria even in general-sum games. However, in terms of last-iterate convergence in two-player zero-sum games, an increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks at a rate of $(1/\sqrt{T})$, while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose? Somewhat surprisingly, we show that the former is true. More generally, we prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small $\delta>0$, there exists a $2\times 2$ matrix game such that the algorithm admits a constant duality gap even after $1/\delta$ rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-regularized-leader algorithms.

Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Yang Cai Yale
Gabriele Farina MIT gfarina@mit.ee edu
Julien Grand-Clément
HEC Paris
yang. cai @yale.
grand-cl wat.ccllmmnttee........
Christian Kroer
Chung-Wei Lee
Haipeng Luo USC
Columbia ck2945@columbia.edd edu
USC LeechungQusc.edu
haipengl@usc.edt
Weiqiang Zheng Yale
weiqiang- zhengdyale.edi
Abstract
Self-play via online learning is one of the premier ways to solve large-scale two- player zero-sum games, both in theory and practice. Particularly popular algo- rithms include optimistic multiplicative weights update (OMWU) and optimistic seweeentdddseet--ssceee (OGDA). While both algorithms enjoy O(1/T) ergodic convergence to Nash equilibrium two-player zero-sum games, OMWU offers several advantages including logarithmic dependence the size of the payoff matrix and ((1TT) convergence to coarse correlated equilibria even in general- sum games. However, in terms of last-iterate convergence in two-player zero-sum games, increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks rate of (1/VT), while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose? Somewhat surpris- ingly, show that the former is true. More generally, we prove that broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small 8 0. there exists 2 matrix game such that the algorithm ad- mits a constant duality gap even after 1/6 rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-ress thiee--guarized---ee -eader algorithms.
Introduction
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games. Major examples include super-human AIs for Go. Poker [Brown and Sandholm, 201 8], and human-level AI for Stratego [Perolat et al., 2022] and alignment of large language models [Munos et al., 2023]. In particular, Optimistic Multiplicative Weights Update (OMWU) and Optimistic Gradient Descent-Ascent (OGDA) are two of the most well-known online learning algorithms. When applied to learning two-player zero-sum game via self-play for T rounds, the average iterates of both algorithms are known to be an (11/T) approximate Nash equilibrium [Rakhlin and Sridharan, 2013. Syrgkanis et al., 2015), while other algorithms, such vanilla Multiplicative Weights Update
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(MWU) and vanilla Gradient Descent-Ascent (GDA), have slower ergodic convergence rate of O(1/VT).
For multiple practical reasons, there is growing interest in studying the last-iterate convergence of these learning dynamics [Daskalakis and Panageas, 2019, Golowich et al., 2020b, Wei et al., 2021, Lee et al., 2021]. In this regard, existing results seemingly exhibit a gap between OGDA and OMWU the duality gap of the last iterate of OGDA is known to decrease at rate of O(1/VT) [Cai et al., 2022, Gorbunov et al., 2022], with no dependence on constants beyond the dimension and the smoothness of the players' utility functions of the game.' ! In contrast, the existing convergence rate for OMWU depends on some game- deme-dependent constant that could be arbitrarily large, even after fixing the dimension and the smoothness constant of the game [Wei et al., 2021].² Given the fundamental role of OMWU in online learning and its other advantages over OGDA (such as its logarithmic dependence on the number of actions), it is natural to ask the following question:
Is the potentially slow last-iterate convergence an inherent disadvantage of OMWU?
Main Results. In this work, we show that the answer to this question is yes, contrary to a common belief that better analysis and better last-iterate convergence results similar to those of OGDA are possible for OMWU. More specifically, we show the following.
Theorem (Informal). For OMWU with constant step size, there is no function f such that the corresponding learning dynamics {(x', ./ 1/) 1 in two-player zero-sum games [0, [jdixda has last-iterate convergence rate of f(d1, T). More specifically, no function f can satisfy
1. DualityGap(1" .y²)) S f(d1, T) for all matrices [0,1]d xd2 and T 2 1.
2. limy f(d1, d2, T) - 0.
Our findings show that, despite the significantly superior regret properties of OMWU compared to OGDA, its last-iterate convergence properties remarkably worse. In turn, this counters the viewpoint that "Follow-the tegetehullarizedd Lataariiedd-Leeerrr Leader (FTRL) is better than Online Mirror Descent (OMD)" [van Erven, 2021]: crucially, while OMWU is instance of (optimistic) FTRL, OGDA is an instance of optimistic OMD that cannot be expressed in the FTRL formalism.
We further show that similar negative results extend to several other standard online learning algo- rithms, including a close variant of OGDA. More concretely, our main results are as follows.
We identify a broad family of Optimistic FTRL (OFTRL) algorithms that do not forget about the past quickly. We prove that, for any sufficiently small 8 >> 0, there exists 22x 2 two-player zero-sum game such that, even after 1/8 iterations, the duality gap of the iterate output by these algorithms is still a constant (Theorem 1). This excludes the possibility of showing ggae-indeeendee last-iterate convergence rate similar to that of OGDA.
We prove that many standard online learning algorithms, such OFTRL with the entropy regu- larizer (equivalently, OMWU), the Tsallis entropy family of regularizers, the log regularizer, and the squared Euclidean norm regularizer, all fall into this family of non-forgetful algorithms and thus all suffer from the same slow convergence. Also note that Optimistic OMD (OOMD), another well-known family of algorithms, is equivalent to OFTRL when given a Legendre regularizer. Therefore, OOMD with the entropy, Tsallis entropy, and log regularizer also suffer the same issue.*
Finally, we also generalize our negative results from 2 games to 2n x 2n games for any positive integer n,, strengthening our message that forgetfulness is generally needed in order to achieve fast last-iterate convergence.
'In finite two-player zero-sum games, the dependence is polynomial in the number of actions and the largest absolute value in the payoff matrix.
"W note that there are also iinear-rate last-iterate results for OGDA when we allow dependence on such constants; see [Wei et al., 2021].
è Under the same condition, OGDA has a last-iterate convergence rate of polyfdr.da).
VT
"We focus on optimistic variants of these algorithms since it is well-known that their vanilla version does not converge in the last iterate at all, see e.g. [Mertikopoulos et al., 2018, Daskalakis and Panageas, 2018, Bailey and Piliouras, 2018, Cheung and Piliouras, 2019].

---

Entropy (OMWU)
Log regularizer
Sq. Fuclidean norm
OGDA
1.0
1.0
1.0
1.0
0.8
0.8
0.8
0.8
0.6
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.6
0.8
1.0
0.6
1.0
0.6
0.8
1.0
0.8
[1]
[1]
[1
10-
Equiibrium gap
10-1
10-1
10-
10-2
10-3
10-2
10"-
10-22
10
10
10a
10
10a
10
10a
10
10
Iteration
Lteration
lteration
Iteration
Figure 1: Comparison of the dynamics produced by three variants of OFTRL with different regu- larizers (negative entropy, logarithmic regularizer, and squared Euclidean norm) and OGDA in the same game A₂ defined in (2) for 5 == 10-2 The bottom row shows the duality gap achieved by the last iterates. The OFTRI variants exhibit poor performance due to their lack of forgetfulness, while OGDA converges quickly the Nash equilibrium. Since the regularizers
the first two plots are Legendre, the dynamics are equivalent to the ones produced by optimistic OMD with the respective Bregman divergences. In the plot for OMWU we observe that x' [1] can get extremely close to the boundary (e.g., in the range 1000 digits of precision. The red star, blue dot, and green square illustrate the key times Tı, T2. Ts defined in our analysis in Section 3.
e550 < x ['[ < 1). To correctly simulate the dynamics, we used
0.05
5 = 0.01
0.005
Equilibrium gap
10
10-2
10a
10a
10a
10
104
10a
10
10a
10a
10
100
10a
10a
10a
10a
Iteration
Iteration
Iteration
Figure 2: Performance of OMWU on the game As defined in eq. (2) for three choices of 5. In all plots, the learning rate was set 17 0.1. As predicted by our analysis, the length of the "flat region" between iteration Ti (red star) and T2 (blue dot) scales inversely proportionally with d.
Main Ideas. Intuitively, we trace the poor last-iterate convergence properties of OFTRL to its lack of forgetfulness. The high-level idea of our hard x 2 game instance, parametrized by > is as follows. First, it has unique Nash equilibrium at which one player is O()) close to the boundary of the simplex. We refer the first row of plots in Figure 1, where the equilibrium noted by blue dot (note that we can plot only æ x[1], v1]] for each player, since [2] = 1 x|[] and y/2] = y/2]). As can be seen, the iterates of OGDA and all three OFTRL variants initially have two-phase structure. In the first phase, they converge to the lower-right area denoted by red star in Figure 1. Then, from there all algorithms start moving towards the equilibrium. particular, y/1] increases. However, once they enter the vicinity of the equilibrium, the behavior depends on the algorithms. For OGDA, dynamics start spiraling closer and closer algorithm, the player has built up a lot of "memory" of x being better than x[2). and for this reason, [1] will stay very close for long time. During the time when x x11 is close to 1, s(1] keeps increasing since the y player receives gradients that indicates y is better than y/2]. As
equilibrium. On the other hand, for the OFTRL

---

result, the dynamics cannot "stop" near the equilibrium but start to move away from the equilibrium. The dynamics reach a point (denoted by green square) whose duality gap a constant and enter a new cycle where they move out towards the starting point of the learning process. This cycle repeats in smaller and smaller semi-ellipses that slowly converge to equilibrium. Note that the semi-ellipses correspond to the seesaw pattern in the equilibrium gap (second row of plots). OFTRL overshoots the equilibrium as it has built up a lot of "memory" of [r]] being better than x xr2] along the phase from the red star to the blue circle, and it requires many iterations to "forget" this fact. We show that as we make 8, the parameter defining the nearness to the boundary, smaller and smaller, it takes longer and longer for these semi-ellipses to get close to the equilibrium along the entire path, as illustrated in Figure 2.
Our results are related to numerical observations made in the literature on solving large-scale extensive- form games. There, algorithms based on the regret-matching" (RM+) algorithm [TTammelin et al., 2015], combined with the counterfactual regret minimization [Zinkevich et al., 2007], perform by far the best in practice. In contrast, the classical regret matching algorithm [Hart and Mas-Colell, 2000] performs much worse, in spite of similar regret guarantees. It was later discovered that RM* corresponds to OGD, while RM corresponds to FTRL [Farina et al., 2021, Flaspohler et al., 2021J. It was hypothesized that RM builds up too much negative regret at times, and thus is slow to adapt to changes in the learning dynamics related to the strategy of the other player. These numerical results and the hypothesis consistent with our theoretical findings: FTRL (and thus RM) is not able to "forget," " whereas OGD and OGDA can forget and thereby quickly adapt to changes in which actions should be played.
1.1 Related Work
The literature on last-iterate convergence of online learning methods in games vast. In this section, we will cover key contributions focusing on the case of interest for this paper: discrete-time dynamics for two-player zero-sum normal-form games.
Convergence of OGDA. Average-iterate convergence of OGDA has been studied for minimax opti- mization problems in both the unconstrained [Mokhtari al., 2020] and constrained settings [Hsieh et al., 2019]. Last-iterate convergence of OGDA in unconstrained saddle-point problems has been shown in [Daskalakis et al., 2018, Golowich al., 2020a]. In the (constrained) game setting, Wei et al. [2021], Anagnostides et al. [2022] showed best-iterate convergence to the set of Nash equilibria in any two-player zero-sum game with payoff matrix A at rate of (ppoyy d2, max:,j [A..l)/vTT) using constant learning rate, where d1 and d2 are the number of actions of the players. A stronger result was shown by Cai et al. [2022], who showed that the same rate applies to the last iterate.
Convergence of OMWU. Optimistic multiplicative weights update (also known optimistic hedge) is often regarded as the premier algorithm for learning in games. Unlike OGDA, it guarantees sublinear regret with a logarithmic dependence on the number of actions, and it is known to guarantee only polylogarithmic regret per player when used in self play even for general-sun games [Daskalakis et al., 2021]. can be applied with similar strong properties beyond normal-form games in several important combinatorial settings [Takimoto and Warmuth, 2003, Koolen et al., 2010, Farina et al., 2022]. The work by Daskalakis and Panageas [2019] established asymptotic last-iterate convergence for OMWU in games using a small learning rate under the assumption of unique Nash equilibrium. Similar asymptotic results without the unique equilibrium assumption were also given by Mertikopoulos et al. [2019], Hsieh et al. [2021]. Wei et al. [2021] were the first to provide nonasymplotic learning rates for OMWU. Specifically, they showed a linear rate of convergence in games with a unique equilibrium, albeit with a dependence on a condition number-like quantity that could be arbitrarily large given fixed d1, d2, and max,,; |. result was later extended by Lee et al. [2021] to extensive-form games. Unlike OGDA, no last-iterate convergence result for OMWU with polynomial dependence on only the natural parameters of the game (i.e., d1, d2, and max,,; [Ar,)) is known. As we show in this paper, perhaps surprisingly, this is coincidence: in general, OMWU does not exhibit last-iterate convergence rate that solely depends on these parameters, whether polynomial or not.
FTRL Vs. OMD. While the last-iterate convergence of instantiations of Optimistic Online Mirror dynamics remain
Descent has been observed before, the properties of Follow-the wew.ee-eglarizedd...eee.. mostly elusive. The present paper partly explains this vacuum: all standard instantiations of opti- mistic FTRL cannot hope to converge iterates with only polynomial dependence on the natural parameters of the game, unlike optimistic OMD. Complications in obtaining last-iterate convergence

---

results for continuous-tii time FTRL instantiations were already reported by Tlatakis-Gkargkkee al. [2020], who showed the necessity of strier Nash equilibria.
Exploising a no-regrel learner. The forgetfulness property that we identify is closely related to the concept of mean-based learning algorithms from Braverman al. [2018]. Intuitively, mean- algorithms are ones such that if the mean reward for action a is sigmificantly greater than the mean reward for action b, then the algorithm selects 6 with negligible probability. They show that MWU is Seepw-tte--erturee----e
mean-based, along with al. [2018] shows that "maanbbase algorithms are exploitable when learning to bid in first-price auctions, whereas Kumar et al. [2024] shows that OGD does not suffer from this exploitability issue.
and the Exp3 bandit algorithm. Braverman
2 Preliminaries and Problem Setup
We consider the standard setting of no-regret learning in zero-sum game A [0, 11]]dxxd Xd2, In each iteration t 2 1, the z-player chooses x' X' := Ad while the y-player chooses y e := da Then the z--laaer receives loss vector e = Ay" while the y-player receives loss vector The goal is to find or approximate a Nash equilibrium (x" (x",y") to the game such
y = - x', that x² E argminzex* maxyey x² Ay and y² argmaxyey min x Ay. The approximation error of a strategy pair (x, v) is measured by its duality gap, defined as DualityGap(z, v) maxy'yy T.T Ay' poy-mingee min x' Ay, which is always non-negative.
Popular no-regret algorithms for solving the game include the Optimistic Follow-the- Reegttta-eegl Leader (OFTRL) algorithm and the Optimistic Online Mirror Descent (OOMD) algorithm, both defined in terms of certain regularizer corresponding Bregman divergence of R is Dr(a, x²) = R(r)= R(x') - (V R(x'), x²), and the regularizer is 1-strongly convex if Dn(x, x²) 2 }11æ x' 1l2 for all I E Ad.
A - R (for some general dimension d). The
Optimistic Online Mirror Descent (OOMD) Starting from initial point (x+ y²) (8) ).) the OOMD algorithm with regularizer R and steps size v7 > 0 updates in each iteration 2 2,
V argmin " + DR(z, "}, x' argmin(mr2e f 1 DR(x,
#EX
#EX
(OOMD)
D' argmin(n eg + DR(V, )1 y¹ argmin (n ( DR(V, D')}. BEy
wEy
In particular, we call OOMD with a squared Euclidean norm regularizer, that is, R(x) 1/2 1 optimistic grudiemt-descent-asseee
(OGDA). When is the negative entropy, that is, R(x)
Ed Li=i I Iog we call the resulting OOMD algorithm optimistic multiplicative weights update (OMWU). OGDA and OMWU have been extensively studied in the literature regarding their last- iterate convergence properties in zero-sum games. Specifically, both OMWU and OGDA guarantee that (x', ,y) approaches to a Nash equilibrium as 00.
Optimistic Follow-the- wew.th----egulliied-e-eeeeee (OFTRL) Define the cumulative loss vectors D5
Eke ey and It = Ek eg-
The update rule of OFTRL with regularizer R is for each 2 1,
x² = argmin ZEX
Lh + 1 + R(x)
17
(OFTRL)
11-1 + 1 + 1 R(wy) (v, (v
y² argmiin
yEy
1)
Throughout the paper, we consider the following regularizers:
Negative entropy (R(x) = Ede 1=1 xfi] log zfi)): the resulting OFTRL algorithm coincides with OMWU defined by the OOMD framework previously.
Squared Euclidean norm (R(x) = 1 _ x((]3): note that the resulting algorithm is different from OGDA since the squared Euclidean norm is not Legendre regularizer. As we will show, the two algorithms behave very differently in terms of last-iterate convergence.
Log barrier (R(z)- Ei= log(x(i))): also call it the log regularizer.
5

---

Negative Tsallis entropy regularizers (R(x) 1- (0__((( (aD)" parameterized by 3 E (0, 1)).
1-9
The 2-dimension case We denote E IR² as x [a[1]. x²2] For d1 = finding æ' of OFTRL
reduces the following 1-dimensional optimization problem:
- + R(x)) )
x [1[1] arginn xE(0,1]
(1+
x²[2] [1]],
where we slightly abuse the notation and denote R(s) R( x for x E [0. 1J. We introduce two notations (the case for the y-player is similar): let e = [1] E [2] be the difference between the losses of the two actions, and E = Ek=1 ex be the cumulative difference between the losses of the two actions. For OFTRL, is clear that the update of x' only depends on the differences E e the step size y), and the regularizer R. For this reason, we define F.. [0, 1] as follows:
1 (() = argmin x. c (R()) ze(0,1]
(1)
1
We assume the function F,, well-defined, i.e., the above optimization problem admits a unique solution in (0, 1]. This is condition easily satisfied, for example, when the regularizer R is strongly
convex. Then the OFTRL algorithm can written as
x r²[1] F + e
x x²22]
- x² [1].
The following lemma shows that the function F, is non-increasing (we defer missing proofs in the section to Appendix A).
Lemma (Monotonicity of Fn,R). The The function F.) [0, 1] defined in (1) -ot-increasing.
We present some blanket assumptions on the regularizer, which are satisfied by all the regularizers introduced before.
Assumption 1. We assume that the regularizer R satisfies the following properties: the function Fg : + (0, 1] defined (1) is,
1. Unbiased: (0)
2. Rational: lim (E) and limg-+to (E) O.
3. Lipschitz continuous: There exists L 2 0 such that Fi, is L-Lipschitz.
Item Assumption shows that the initial strategy is the uniform distribution over the two actions, which is standard in practice. The rational assumption (item 2 in Assumption 1) is natural since otherwise, the algorithm could not even converge to a pure Nash equilibrium. The Lipschitzness (item 3 in Assumption 1) is implied when the regularizer is strongly convex over [0, 1]a (see Lemma 4), and it further implies Lipschitzness of FY,R R for any 77 as shown the following proposition.
Proposition 1. The function F,,n satisfies 1e (F/n) (F.. If Fi,n is T--lipschitz, then F,. is LLL-Lipschitz for any 0.
Slow Convergence of OFTRL: A Hard Game Instance
We give negative results the last-iterate convergence properties of OFTRL by studying its behavior on a surprisingly simple 2x2 two-player zero-sum games. The game's 's loss matrix As is parameterized by d E (0, 1)) and is defined follows:
+
Ag
(
0
3.1 Basic Properties
We summarize some useful properties of Aş the following proposition (missing proofs of this section can be found in Appendix B).

---

Proposition 2. The matrix game As satisfies:
1. As has a unique Nash equilibrium x" = -T400 I48) and y² =[21+3) [[143] 2(1+3]
1+28
2. For a strategy pair (x', y²), the loss vectors (i.e., gradients) for the two players are respec- tively:
1 + [1
( 6000"11111
= Asy' =
c= 13 x' = -=
11- -
(3)
Moreover,
1
2 e E - - 2'2 + 8]
c = 1 -,, = 1 (1+ E 1-
In particular, notice that e 2 5. It implies that if the cumulative differences between the losses of the two actions F.J large, then takes (2 iterations make Fy small (close to 0). This has important implications for non-forgetful algorithms like OFTRL that look at the whole history of losses. Since OFTRL chooses the strategy y based on Ey it could be trapped in a bad action for a long time even if the current gradients suggest that the other action is better. This is the key observation for our main negative results on the slow last-iterate convergence rates of OFTRL.
The following lemma shows that in particular region of (x, y). the duality gap is constant.
Lemma 2. Let ò, E (0, )) For any z, y E A such that xr1] 2 1 and y(1] 2 2 + the duality gap of (2. v) for game Ag (defined in (2)) satisfies DualityGap(a,, y) 2
1+8
3.2 Slow Last-Iterate Convergence
We further require the following assumption on the regularizer R (and thus the function Fi,R).
Assumption 2. Let L be the Lipschimess constant of F1, in Assumption 1. Denote constant
FI.R( )OL) There exist universal constants 8', and c3 E (0, 1 such that for any
0 < 8 8
1. For any E that satisfies Fi,R(E)= 2 I-8 we have Fi,R(
oî S0Ld
+ E) Z
1t
I+0a+0
2. For any E that satisfies Fi,)(E) 2 21145j we have Fi,
rac 120L
+ al
+ E) N 1 + C2.
Although Assumption 2 is technical, the idea is simple. Item I in Assumption 2 states that if loss
difference < already makes REE 2 T then the loss difference E' = E ( is able to make (E") greater than (E) by a margin of (6)). Item 2 in Assumption states that if E 2(1) able make (EE) greater than by constant margin c2. In Appendix C, we verify that Assumption 2 holds for the negative entropy, squared Euclidean norm, the log barrier, and the negative Tsallis entropy regularizers.
loss difference E already makes F Z I
श[+ 3 then the loss difference
Now we present the main result of the section showing that even after 2(1/8) iterations, the duality gap of the iterate output by OFTRL is still constant.
Theorem 1. Assume the regularizer R satisfies Assumption and Assumption 2. For any E (0, 8), where is constant depending only on the constants Cı and 8' defined in Assumption 2, the OFTRL dynamics on As (defined (2)) with any step size v) S 1 satisfies the following: there exists an iterution L. 2 39L6 Assumption 2.
with duality gap of at least ez, a strictly positive conslant defined in
Proof Sketch: decompose the analysis into three stages as illustrated in Figure We describe the three stages and the high-level ideas of our proof below and defer the full proof to Appendix B.2.
7

---

8
Stage
02
2
1
2(1 +
2
1
Ts
2
Stage
Stage II SC + iterations
t T1
1
Figure 3: Pictorial depiction of the three stages incurred by the OFTRL dynamics in the game As defined in (2). The point 2 denotes the unique Nash equilibrium. The times Ti and T2 are shown for concrete instantiations of OFTRL in Figure by red star and blue dot, respectively. The times T, and Th are defined in the proof of Theorem in Appendix B.2.
[1] = y [1] 2 by Assumption 1. We show that x² [1] increases Stage I [1 Ti 1]: Recall that x [1[1]
and denote Ti the first iteration that z [1] 2 1+o. During the time [1, 1]. since ['[ is always smaller than I45. we know from Proposition 2 action has larger loss than action 2 for the y-player, i.e., c = [1] e [ 2 0. Thus [1] decreases during stage I and we show that y²i [1] C1 with e₁ defined in Assumption 2.
Stage II Ti,Ta]: Recall that [1] S [T] 2(1+5) > -1. We remark that for y²[1] to increase, the loss vector must satisfy et, < However, the game matrix As guarantees that et, > - matter what the x-plaaee's strategy is (Proposition 2). Thus by the 1/-Lippchirzness of F (Proposition 1), the per-iteration increase in y'[ is most T9Lô. Therefore, we know T22 Ti 22( and the cumulative loss for the r-player decreases to ETD < ET - 22 , Recall æ [T)[1] 2 T
- -c1. We define T2 > Ti as the first iteration where
[1 71.5 As result, e < during [21, T2]
Thus T [1] 2hth [1] is much closer
Stage III [T2, Ty]: Recall that [T=[1] 2 2(148) Moreover, y [1] could keep increasing if x' 2 148 since that implies e' < 0. Now the question is how long would the x-player stay close to the boundary, i.e,
not forgetful, this happens only when E 2 E (recall x ( 2 1 But we have the end of stage II, ET s ET 22( nL5 Since the per-iteration loss is bounded by requires at least 22( (1,13) iterations cancel the cumulative loss of Q 17.55 Define T3 = T2 + 2 nT.3 ). During [3], the y-player always
x1(1 > 146" Since OFTRL-type algorithms
receives loss such that et < and we prove that in the end " 2 1/2 + 02 for some constant C2.
Conclusion: Finally, we get one iteration T3 2 9 TT. with x [1] 2 T48
1- and y 2 2 1 + C2.
Using Lemma the duality gap of (a:Ta, TT) is at least 02 > 0.
Theorem immediately implies the following (proof deferred to Appendix B.3).
Theorem 2. For optimistic FTRL with any regularizer satisfying Assumption I and Assumption
and constant steps size 1) S тŁ (L is defined in Assumption 1), there is no function f such that the corresponding learning dynamics {x', ) in two-player zero-sum games [0, 1]d]]xxx has last-iterate convergence rate of f(d,, , d2, T). More specifically, no function f can satisfy
1. DualityGap(a' ,,y²) < f(d,, T2, for all [o, 1]ds ldixda for all T 1.

---

2. limy-+oo f(d1, d) + 0.
Theorem 1 and Theorem provide impossibility results for getting a last-iterate convergence rate for OFTRL that solely depends on the bounded parameters, even in two-player zero-sum games. Moreover, they show the necessity of forgetfulness for fast last-iterate convergence in games since OGDA has a last-iterate convergence rate of O poly)d) [Cai et al., 2022, Gorbunov et al., 2022].
Extension to Higher Dimensions
In this section, extend our negative results from 2 matrix games to games with higher dimensions. We start by showing an equivalence result for a single player (say, the first player). We assume that decision maker using OFTRL with I-strongly convex (w.r.. the &2 norm) and separable regularizer R(x)) Rí (x1) + R2(22) to choose decisions. At given time time i, they see loss e E [0, 1]
Now consider the following 2n-dimensional decision problem: The player uses OFTRL using the regularizer f())) = Σ R1 (á:)) + - Rg (f.). i.e, they use R on the first half actions, and R2 on the second half. This again I-strongly convex regularizer (w.rt. the lg norm). Suppose the decision maker sees the rescaled and duplicated version of the losses lz ....., e from the 2- dimensional case: 2; = - if S n. and é na Eg if > n. The parameter a will be chosen later
based on the regularizer.
Now we wish to show that by choosing a in the right way, we get that the decisions for the 2-dimensional and 2n-dimensional OFTRL algorithms dimensional OFTRL decisions, and let
equivalent. Let x ,..., x=" be the 2- 27 be the 2n-dimensional OFTRL decisions. Then,
we want to show that Σi= # x1[1] and 2n Ei=nti of x' [2] for all L.
Lemma 3. Let the losses L ....... 2er sctissy the duplication procedure given in the preceding para- graph. Then for any time t, we have 84 =... zn and 4 #nt1
2n
Proof. Suppose not and let 2 be the corresponding solution. Then the optimal solution is such that it * ith for some i, both less than n, or both greater than n. But then, by symmetry, we have that there is more than one optimal solution to the OFTRL optimization problem at time t: the objective exactly the same we create new solution where we swap the values of a and a This is contradiction due to strong convexity.
From lemma 3, we have that the OFTRL decision problem in 2n dimensions can equivalently be written as a 2-dimensional decision problem: Since the first n entries must be the same, we can simply optimize over that one shared value, say x' [1], which we use for all n entries, and similarly use [2] for the second half of the entries. Let Dupl A + A be function that maps the two-dimensionall solution into the corresponding duplicated 2n-dimensional solution. The equivalent 2-dimensional problem is then:
}
a/ Dupl
argmin A.
π
+
6-1
+ Rí [x(x]))
" (=) (n(=[1)+=R<<>(1))
n2
+ = }
Dupl
argmin #EA²
e
d-1
R(x//m)) R(x/n)) }1
n1
11
17
na+1 + p-1
-Dupl
argmin aEA2
n
n
The next theorem shows that we can choose a for different regularizers and construct 2n x 2n loss matrices whose learning dynamics are equivalent to the learning dynamics in 2 games given in the preceding sections. We defer the proof to Appendix D.
Theorem 3. For any loss matrix A E 1j222 there exists loss matrix À E [0, 2a such that for the Fuclidean (a = 1), entropy (a = 0), Tsallis (3 E (0,1) and a -1 + 3), and log (a - regularizers, the resulting OFTRL learning dynamics are equivalent in the two games.

---

Combining Theorem I and Theorem 3, we have the following:
Corollary 1. In the same setup as Theorem 3, under Assumption and Assumption 2, there exists game matrix Ag E (0,n-apmxbb such that the OFTRI learning dynamies with any step size S AL satisfies the following: there exists an iteration t 2 3x
en with duality gap at least o2n
Since = 0 for the entropy regularizer, the same results hold more generally for games where one player has more actions than the other. particular, we can create 2n 2m game such that the resulting dynamics are equivalent to those in a 2 x 2 game. This does not work for the Euclidean and log regularizers because the rescaling factors would different for the row and column players.
Conclusion and Discussions
In this paper, we study last-iterate convergence rates of OFTRL algorithms with various popular regularizers, including the popular OMWU algorithm. Our main results show that even in simple 2 x 2 two-player zero-sum games parametrized by 8 >> 0, the lack of forgetfulness of OFTRL leads to the duality gap remaining constant even after 1/8 iterations (Theorem 1). As a corollary, we show that the last-iterate convergence rate of OFTRL must depend can be arbitrarily bad (Theorem 2). This highlights a stark contrast with OOMD algorithms: while OGDA with constant step size achieves O (TT) last-iterate convergence rate, such guarantee is impossible for OMWU or more generally OFTRL. We now discuss several interesting questions regarding the convergence guarantees of learning in games and leave them as future directions.
wreelenddependent constant that
Best-Iterate Convergence Rates While we focus on the last-iterate (i.e., QualityGa((a" ,y²))
the weaker notion of best-iterate (i.e., minke(r) DualityGap(r" (""ap("",'")) ,y")) is also of both practical and theoretical interest. By definition, we know the hest-iterate convergence rate is at least as good as the last-iterate convergence rate and could be much faster. This raises the following question:
What is the best-iterate convergence rate of OMWU/OFTRL?
To our knowledge, there are no concrete results on the best-iterate convergence rates of OMWU other OFTRL algorithms. It is thus interesting extend our negative results to the best-iterate convergence rates or develop fast best-iterate convergence rates of OMWU/OFTRL.
Dynamic Step Sizes Our negative results hold for OFTRL with fixed step sizes. We conjecture that the slow last-iterate convergence of OFTRL persists even with dynamic step sizes. In particular, believe counterexamples still work for OFTRL with decreasing step sizes. This is because decreasing the step size makes the players move even slower, and they may be trapped in the wrong direction for longer time due to the lack of forgetfulness. In Appendix E, we include numerical results for OMWU with adaptive stepsize akin to Adagrad [Duchi et al., 2011] which supports our intuition. We observe the same cycling behavior for fixed step size. While the cycle is smaller than that of fixed step sizes, the dynamics take more steps to finish each cycle. Investigating the effect of dynamic step sizes on last-iterate convergence rates an interesting future direction.
Slow Convergence due to Lack of Forgetfulness Our work shows that various OFTRL-type algorithms do not have fast last-iterate convergence rates for learning games. Our proof and hard game instance build on the intuition that these algorithms lack forgetfulness: they do not forget the past quickly. This intuition also utilized in [Panageas al., 2023]. In particular, they give an d x d potential game where the last-iterate convergence rate of the Fictitious Play algorithm, which is equivalent to the tellow-the-Leader (FTL) algorithm, suffers exponential dependence the dimension d. One natural future direction is to formalize the intuition of non coon-ooggtfulness further and give a general condition for algorithms under which they suffer slow last-iterate convergence. is also interesting to show other lower-bound results for learning in games.
10

---

Acknowledgements
We thank the anonymous reviewers for their constructive comments on improving the paper. Yang Cai was supported by the NSF Awards CCF-1942583 (CAREER) and CCF-2342642. Christian Kroer was supported by the Office of Naval Research awards N00014-22- 1-2530 and N00014-23-1-2374 and the National Science Foundation awards IIS LIS-2147361 and IIS 20--223866. Julien Grand-Clément supported by Hi! Paris and Agence Nationale de la Recherche (Grant 11- I1-LABX-0047). Haipeng Luo was supported by NSF award 193-1743 Weiqiang Zheng was supported by the NSF Awards CCF-194258 (CAREER). CCR-2342642, and Research Fellowship from the Center for Algorithms, Data, and Market Design at Yale (CADMY).
References
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. International Conference on Machine Learning, pages 536-581. PMLR. 2022.
James Bailey and Georgios Piliouras. Multiplicatiie weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 321-338, 2018.
Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg, Selling to no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 523-538, 2018.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-424 2018.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, pages 807-834. PMLR, 2019.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances neural information processing systems (NeurIPS), 2018.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and con- strained min-max optimization. 10th Innovations in Theoretical Computer Science Conference (ITCS), 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference Learning Representations (ICLR), 2018.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems (NeurIPS), 2021.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 5363 5371, 2021.
Gabriele Farina, Chung-Wad Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for 0/1-polyledral games: Bridging the gap between learning in extensive-fome and normal-form games. In International Conference on Machine Learning (ICML), pages 6337-6357, 2022.
Genevieve E Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey, Online learning with optimism and delay. In International Conference Machine Learning, pages 3363-3373, PMLR, 2021.

---

Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning multi-player games. Advances in neural information processing systems (NeurIPS), 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory (COLT), 2020b.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Advances in Neural Information Processing Systems, 2022.
Sergiu Hart and Andreu Mas-Colell A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 127-1110 2000.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
Yu-Guan Hsich, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, pages 2388-2422 PMLR, 2021.
Wouter M Koolen, Manfred K Warmuth, Jyrki Kivinen, et al. Hedging structured concepts. In COLT, pages 23-105. Citeseer, 2010.
Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. Strategically-rooust learning al- gorithms for bidding in first-price auctions. In Proceedings of the 2024 ACM Conference Economics and Computation, 2024.
Chung- Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34:14293-143486 2021.
Haipeng Luo. Lecture note Introduction to Online Learning 2022. URL holthttss//aaappee luo. net/ /tt.r//eecccccc///////// http///////..a//////ett/e//eee//
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pages 2703-2717. SIAM, 2018.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR), 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, (0)3):333--251, 2020.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo. Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, al. Nash learning from human feedback. arXiv preprint wwXiv:2312.00888 2023.
Ioannis Panageas, Nikolas Patris, Stratis Skoulakis, and Volkan Cevher. Exponential lower bounds for fictitious play in potential games. In seirth- Conference Neural Information Processing Systems, 2023. URL. /ttttts::/pppreeeeee wttp:viwwwwweeeeeeeee.e net. fnntt/ffrummiin didrum/idddtttkkkkeeeii
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(663)):990--2
2022.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 2013.
12

---

Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances Neural Information Processing Systems (NeurIPS). 2015.
Eiji Takimoto and Manfred K Warmuth. Path kernels and multiplicative updates. The Journal of Machine Learning Research, 4:773-818 818, 2003.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em em. In Twenty-fourth international joint conference on artificial intelligence, 2015.
Tim van Erven. Why FTRL is better than online mirror descent. https: https://www.cr tww.anerven..nnmmmmmmmmmm. tttp:://ww.tinvveervoo.. blog/ftrl-vs omd/, 2021. Accessed: 2024-05-22.
nn/
Emmanouil- Vasileios Vlatakis Gaaraikousaaaa,,,,ss...... Lampros Flokas, Thanasis Lianeas, Panayotis Mer- tikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. Advances in Neural Information Processing Systems, 33:1380-1333 2020.
Chen-Ye Yu Wei, Chung-Wer Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference on Learning Representations (ICLR), 2021.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20, 2007.
Contents
Introduction
1.1
Reeated Work
2 Preliminaries and Problem Setup
3 Slow Convergence of OFTRL: A Hard Game Instance
3.1 Basic Properties
3.2 Slow Ltst-Iterate Convergence
4 Extension to Higher Dimensions
5 Conclusion and Discussions
10
A Missing Proofs in Section
14
A.1 Proof of Lemma
14
A.2 Proof of Proposition
14
B Missing Proofs in Section
14
B.1 Proof of Lemma
14
B.2 Proof of Theorem
14
B.3 Proof of Theorem 2
17
Verifying Assumption for Different Regularizers
18
C.1 Negative Entropy
18
C.2 Squared Euclidean Norm Regularizer
19
13

---

C.3 Log Barrier
19
C.4 Negative Tsallis Entropy
20
Proof of Theorem 3
22
Numerical Experiments with Adaptive Stepsizes
22
A Missing Proofs in Section 2
A.1 Proof of Lemma
Proof. Let < e2. Denote Fy, ((1)) and 22 = Fg,a(e2). By definition, we have
Eσ(22 - x1) - (1(a1) R(x2)) s e (22 x1).
Since 61 < C2 we have 32 S 21-
A.2 Proof of Proposition
Proof. By definition,
{x. E x -.=+ - R(x) argmin fxr E + R(x)) (i, zE[0.1]
F argmin 2=(0.1]
The second claim on the Lipschitzness follows directly.
B Missing Proofs in Section
B.1 Proof of Lemma 2
Proof. We have
DualityGap(r,u) v) max x. Asğ BEA
min & Asy 2EA2
max (Afx)) x) 1E(1.23
min (Ays)li)
(E(1,2
1
( + 8)z(1] - - v11
[x[1) 2 I+5:
1
>> 0)
11+ 25 +
2 2 118
B.2 Proof of Theorem
Proof. Recall that minf 1 0 of
2 FI, 207 defined in Assumption 2. We fix any d < 15 6 300: 8'). Since 8 < 8', Assumption 2 holds. We will prove that there exists an it-
eration 3,L5
with duality gap c2-
Proof Plan: We decompose the analysis into three stages shown in Figure 3. Below, describe the three stages and the high-level ideas in our proof.
Stage I: Recall that x [1] = y [1] = 1 In Stage I, we show that x' [1] will increase and denote
T. > the first iteration where x1[]] 2 T+ The existence of Ti can be proved by contradiction (Claim 1). Since before the end of Stage I, [1] < I
I+3 the loss vector for the y-player satisfies e! = e [1] ey.21 2] 2 0 meaning action is worse than action 2. We will prove that finally
y [ S C1.
14

---

Stage II: Now we have that [1] I 2 c1. we denote T2 > T1 the first iteration where [ 2[1+5j > 4-Ca C1. We remark that in order to increase y [1], the loss vector must satisfy e < O. However, the game matrix As guarantees that ej 2 - no matter what the z z-player is playing. Thus by the ny y/LLLipchiizzess F (Lemma 4), the increase in y is at most n Therefore, we know T2 Ti S2 2L But during [Ti, T2], for the æ-player, we have ey
which implies its cumulative loss E < E O of..8 ). In other words, æ² [1] is very close to 1
and the cumulative loss for action is much smaller than that of action 2.
Stage III: Now we have n²² 2 2パ1+5 and that y [1] could keep increasing if x x4 2 I#3 since then the loss satisfies eg. S 0. Now the question is how long would the z-player stay close to the boundary, i.e, x² 2 1+-6 Since OFTRL-type algorithms are not forgetful, this happens only when E 2 ET (recall x [=' I But we have the end of stage II, ET S ET 22 7 ). 1 n iterations. Define T3 T2 2 (. During [T2, Ta], the y-player always receives loss such that eyy < 0 and prove that [ 2 + for some constant C2.
1
Sincee, is bounded by a constant, we know x'[1] 2 1 even after 52(
I+8
Conclusion Finally we get one iteration T's 2 52( (p()))) with -²3 2 T and y² Using Lemma 2, the duality gap of (n:T', (T) is at least C2.
2 1 2
+ Cz.
2- We define (i) T, [1] 2 2 and (ii) 7, T, to be the smallest iteration such that x (=' 2 शे.- Both T, and Ti must exist, and the reason will become clear in the following analysis. We postpone the proof of this fact in Claim 1 at the end of this paragraph.
Stage I: We know x! 2'11] -
be the smallest iteration such that
Notice from Proposition the difference el is lower bounded: et 2 - for any L. Thus Et-1 et-1 - for any 2 Since TT [1] I 7/p-Lippcch,z
2/4 we know that ET, c.. 0. As F2, is
1 S To [1] x [1] S nL ET
Lujfe
Ex
T--1|
This implies
2 2nL
Since x' ['[1] 3 for all S 5 T, - 1, we know that oy = - - -
-- 11 (1 8) [1] >
4
1-36 2 (as ā < 1T) for all 1 < TT T.-1. 1. Moreover, for all < Ti 1,,1, 1, we know that el 2 0 as x ['] I Since the difference et, is least 1/5 for all S
and remains non-negative
for all e [T,, Ti 1]. we can conclude that for all T, < S Ti
v'l1] F F + c s Fn.
and moreover
To
Fy, Fr. < F
5
1
< Fg,
(T, --12 24y
1 - -12 41.
20Lm
2 C1.
This completes the proof of Stage I, where T [1] 2 148 and y" [1] S the next stage, we prove the existence of T, and Ti.
-1. Before proceed to
Claim 1. T, and Ti exist.
Proof. It suffices to prove that Ti exists as it implies the existence of T.. Assume for the sake of
contradiction that Ti does not exist, i.e., x² [1] < I for all 2 1. By the same analysis as for Stage
I, we get [1] _ ci for all t 2 Z4I This implies eç - (1 + 8) [1] < & ci - - for
15

---

all t 2 1_
2nL Then Ex + + 00 as + +o0. As consequence, x'[]] = EEE +e +
as + +00 by item 2 in Assumption 1. But this contradicts with the assumption that x1[] < 1-1 for all 2 1. This completes the proof.
Stage 1l
We define
C1
T
E
(4)
2Lm
LLm 2
where the lower bound on T holds since
2 1. We note that T = (2 since nL s 1
GL.6
c1. Define Th Ti T. We claim that for all t E [Ti, Th 1]. y [1] = ] 2. To prove the claim, we first notice that -5 - eg S 1 for all 2 1. Then by the monotonicity and the 1/LLLiischitzness of a, (Lemma I and Lemma 4), we get for all
In Stage
have proved that 1 S
t [T1, Th 1).
1' S F n, ( 1) + nL max { Ey c/ e.-1.0}
- 2 + nb (t- - Ti + 1)6
- 2 01 + MLT8
C1
$
where, in the second-to-bee inequality, we use t - -T++15TS CL by Equation (4).
2
Now we denote T2 2 Th the smallest iteration when 1 2[1 The existence of T2 will become clear in the following analysis, and we postpone the proof to Claim the end of the discussion. Then for all & E [T,, T2 1], we have y'[1] S 1
2(1+5) which implies ex. S O. Moreover,
for all t E [T,, Ti + T 1), since y'[1] S 2 + (1 + 8)
2. we have
c = [1] [2)
1
2
1 + (1 + 8) - cI)
2
8
2
(6 )
4
Then for any Ti + T - T2, we have
x'[1] = F E +
1-1
> F E 12tttt 11
( s all E ( - -T,TT.)) T27)))
CIT
> F
+
-
4
cT'
2 F R
+
+ 2
5
where in the last inequality, we use the fact that GTT
2
oo 2 1.
20
Claim 2. T2 exists.
Proof. Assume for the sake of contradiction that T2 does not exist, i.e., y [1] 2[145] for all
t 2 Ti (since we know y' [1] < 1 9 for all t E [Ti Ti + T 1).. Then by the analysis of Stage II and Equation (5), we have xf [1] 2 4 for all t > Ti. This implies ej. < - 36 for all 448
-00 as + co. By item 2 in Assumption we get y'[1] = R + e z as t > xc. But this contradicts with the assumption that 1 (1 < 2[45 for all 2 T. This completes the proof.
t 2 Ti. As result, we have E + eb c--
16

---

Stage III Recall that we have argued in State I that F (
+ = F1.n(1(E7-1 +
-)-1))=xii
2
1 By item in Assumption 2, we have that
T45
F9.88
GT
+
ET
1 = c. - e0--1) 2 FI.
c
+ E ET + 71 11-1)
10
30Ln
Fi,
+ ny (EE 1 + 0 11-111
30L6
1 C+
(5)
1 c3 +
where the first inequality follows from the definition of T and the monotonicity of F,, F,, (Lemma 1). Now denote T3
T2 + | 2. For any T2 S t T3, know that
x² [1] = F., -
+ ++22))
= F TT--1
+ T2
(-1
-c
x
-
k=
GT
t-1
2
Fn
+
ETi
+ 8
Ti-1
Σ
+ c/
2
5
k=
GT
G
2 Fl
+
ET-- g
-1 + cg
Ti-1 +
2 +2
5
10
qT
2 F
+ ET- + 6 21-11
10
1+ C3
(by (5)
+ c3 +
Note that 1+ < 2. This implics = 11-40(0)) Moreover, we know that of 2 5 for any t. Then
odd
S
cg 2
for all T2 S t $ T3.
1+0++8
[ = Fn ETT'' + TT-1))
-
2 (LE -1
Σ
k
T3-1
-ey 1)-1))
+ e2j
Eg
+ Eg
k=1²z
030
T2)
2 Fn -1 + c
ETT21
T2-1
+ 6)
2
c30c; T
2 Fn, 1 + e
T2-1
+ 8)
(T3 -2 10
2
97 20
40
c
2 E 11 + eg
To-1
+ 8)
(T 2 3nLe
120mL
c
= =1,R(T(E 16- - E
T2-1
120L + n1)
c 2
2 Fi, TT - -
+
(n +
120L
4L.
Recall that FI + E 1))- F 1.
22 -1 + E
T2-1)
T2-
= "1] 2 21+55 By item 2 in
Assumption we have
E T-1 + e 1)
2 + 1L
8
2
+ C2 for some absolute constant
120L
2
C2 > 0. Thus, we have [T( 2 3 + C2. Recall that x [[[
2
Itc
I78. Then by Lemma
Iteat6
conclude that the duality gap of (aTs, Ta) is least C2 >
0. This completes the proof as
T3 2 T2 2 T 39Lo
B.3 Proof of Theorem 2
Proof. Assume for the sake of contradiction that there is a function that satisfies both conditions.
Then for any A E [0, 1]2x2 we have the OFTRL learning dynamics over A satisfies
17

---

1. DualityGap(r" ,y)a)) S f(2,2,T) for all T.
2. limp- (2, +0
Since limm--o f + O, we know there exists To > 0 such that for any t 2 To. Duality Gaityyy -y') 2,) cz. Now let 5 S min 3,12)) Then by Theorem 1, know there exists an iteration 2 the proof.
et 2 To such that CaplityGap(''.u 2 cz. This completes
3nL5
C Verifying Assumption 2 for Different Regularizers
Lemma 4. If the regularizer R is 1-strongly convex, then FL, is -ippschizz.
Proof. Notice that R(x) + R(1 x)) is 2-strongly convex. Thus by standard analysis (see e.g., Luo [2022, Lemma 4)) we know Fi, is -Liischiiz.
By Lemma 4, we can choose
2 for any 1-strongly convex regularizer in Assumption 1.
C.1 Negative Entropy
Lemma 5 (Assumption holds for the entropy regularizer). Consider the negative entropy regularizer R defined as R(x) = x log + (1 x) log(1 - z). Then Fi, is L -Lipschitz. We have c₁ and Assumption 2 holds with 8' 480L Fi.n( 4801
1 and
Proof. is easy verify that (x))(z) has closed-form representation
(L, 1 exp(E)
Thus T, = and
FI.R( Zoz) is universal constant. We also choose
If F1, (T, 2
1
2
1
then we have E s log(118). We note that
1+6 1+5
exp (-
(-
1
1 1+
30LS
I+ C3
1 + exp (-
d log(1/6))
1 1 03 +
30L5
Thus < 81 = 301 log +oy)]
30 log () T suffices for item in Assumption 2.
Fi Fi. 2 2(1to = 1+1428 we have E S log(1 + 26). Note that since log(1 + 2y) S 2y for
y > 0, we have
Czd
C
<
+ logg(1 + 25) <
480L
120L
240L
CsO?
# FI,R
+ E
FI,R
120L
240L
Thus item 2 in Assumption 2 holds for any 8 < 82
and Fi,n(
1
4802
960L
2407
2
Fi. 180L 1.
Combining the above, know Assumption 2 holds for the negative entropy regularizer with 8' 9606
of and C2 Fi,e( 4807 7-
of
18

---

C.2 Squared Euclidean Norm Regularizer
Lemma (Assumption holds for the Euclidean regularizer). Consider the Euclidean regularizer
R defined R(a) [2² + (1 )) We huve L = 2 and holds with 8' 480L 02 900L and C3
We also have Assumplion 20
Proof. It is easy to verify that (x))(z) has a closed-form representation
if < -1
(I)(
L- 2
if (-1,1)
0
if
Thus Fi.nt is L-Lipschitz with I, 2. Moreover,
Fi,rel 20r.
1
We choose 03
1
20
2-
Fix any E such that (i) 2 143 We have E' S
1-1 I40 < 0. We note that for any 8 <
o
302
15
F1R
+ E
2 1 =1
30LS
oi 30Z
Thus 8,
suffices for item in Assumption
Fix any such that EE, 2
We have E S 1+8 5.
The for any 8
csc
2(1+8]
2(1+5)-
2407.
we have
c3ci 120T.
ca0i
c3e 4807.
Fi,
E
Fi,
240T.
of
Thus item 2 in Assumption 2 holds for any 8 < 82
and
4807.
9601.
Combining the above, know Assumption 2 holds for the negative entropy regularizer with
= min(f,,,22]
4801. and C2 9607.
C.3 Log Barrier
Lemma (Assumption holds for the log barrier). Consider the log barrier regularizer R defined as R(x) log(x)) log(1 x). Then Assumption holds with the following choices of constants:
1. 01 = / 40012 20L >
2. C3 60L.
3. 02
Caf
Car2 210L
>
200L
4. 8' 2160T."
Proof. By setting the gradient of E R(x) to get closed-form expression of FI,R:
E +
if> 0 if F =
FF,
1
+
if E < 0.
For (0, 1), the FiR function admits an inverse function defined as
2r 1
F
2.2 T
19

---

Thus we know Bo Fi,N I46) - 1 satisfies Fi,n(Eo) I48
Moreover, we can calculate
1 c3 + )
c3
(1 (1+ cz)²
8²
Fi,
- (3)
1+ C3 8
1+ 43
C3
Cz0
Fn
5
1 + C3
ot
Thus we can choose 63
so that
60L
G
Eg
30L
C3
C3
Ep
0
C3
c30
S Eg
(since < 1/2 and 03 > 0)
8
1 1+ C3
Thus we have Fi, (Eo
2 Fi,
Eo
14c I+0++0
30L0
I+oy
We calculate Ei = Fi, (
4(646") 1426
- 86.
Then we can choose d 8'
C3
Then we
2160T
have
C
8
FLR(
+
E1)
120L
4L
cy
FiR
98)
120L
C30
2 F1,R( 240L
1
C2:
2
where C2 V
cae 210L
y2
c 210L
> 0 by the closed-form expression of Fi.8-
C.4 Negative Tsallis Entropy
For [0, 1], the negative Tsallis entropy is family of regularizers parameterized by 8 (0,1); 1):
1 x R(x)
(6)
- B
The corresponding F1, is defined as
E - x
1 1 (1 - x)
(E) argmin zE(0,1)
1- 8
1 3
For x E (0, 1), we note that Fi, has an inverse function
(T 1- -1------111
B
(1-2))-1)
Lemma 8 (Assumption 2 holds for Tsallis entropy). Consider Tsallis entropy parameterized by
e (0, 1). Then I, 2/3 and Assumption holds with the following choices of constants:
1. Ri 20L > 0.
2. 03 = 3.
3. 02 FI,R(
1 > 0. 240l
20

---

4. 8' = =mmmm((
-
caci
1-8
caci 180L J.
120LBo3
120
80
Proof. We choose C3 = 1.2 We have c1 = Fi,
is a constant.
201
We note that
Es = FI. IR
1
B
(1+8)1-0-
(1
0 8
1-g
1+ 6
1- 3
satisfies Fi, (Eo)
Similarly, we calculate
146"
+ c3
Ei = F. 1/
13 +
B
1 03 + 1-8
1 + 8)
1-8)
1-3
1 C3
B
(1
+ C3 + 0)
1-3
(1+ 8) -2
1 8
8
1 1
1-8
1-8
(1 8)
1-8
-
1-
S
1-9
Eo
+ 2
where in the first inequality we use the fact that (1 + 8)1-8 < since 8 S 1; the second inequality we use the inequality (x + 1 < x-1B
3 y1133 We note that
8 8 = 21 3)
of S
B
C3
1-8
+2
120L 1-8
30LS
1-
3
Thus for any S 81, we have for any E such that Fi, 2
1
I78
&
B
+
E
+ Eu < F.
+
< E
30L8
30LS
1-8 B
The above implies Fi,R(
2²
+ E)
2
and the first item in Assumption 2 is satisfied. Fos
1+00
301.5
We define E2
3
2 + 28
1-8
Eg = FijR
2(1 2(1+
=
1 3
(2 + 28) (2+28)
1 + 28
(1-
1-81
(2 + 28)1-8.
1 3
1 28
43
1-8)
1
1- 3
1 + 25
43
28
1-3 3
I+8
8,38
(1
(3)
where in the first inequality we use (2 + 28) 8 < 4 since 0 < 5 < and 8 E (0. 1); in the second
inequality we use the basic inequality (1 z)r= < 1 r for r, (0, 1). We define
c 2 1 3 c
82 min=
120
88
480L
21

---

Then for any 8 S 82 and E such that Fi,n|E] 2
we have
2(1+6)*
c
8
c
+
E
+ E2
120L
4L
120L
4L
C30i
c3cs
838
+
120L
480L
(1
+ 8)
czel
caci
120L
480T
4807
240L
Thus we know Fi,R(
+
8 2I. + B) 2 Fi,x(-
and item 2 in Assumption 2 is satisfied by 24nt
1207.
cze 240ł
C2 Fi,n(
0.
Combining the above, we can choose = min (81, 52} that both items in Assumption hold for 5 8.
D Proof of Theorem 3
Recall the equivalent 2-dimensional problem:
6' Dupl
argmin nee
I
8-1
" + (e[[[[[[+=-))) (2
2 na
t-1
Dupl
argmin TEA2
I,
+ R((//n)) + p111
n
n
1=1
1-
n a++1
Dupl
argmin #EA?
F + pt-1
R(w/n)
7
Euclidean regularizer: this regularizer is homogeneous of degree two. Choosing a 1, the inner minimization problem is exactly the same as the one solved by OFTRL in two dimensions.
Entropy regularizer: set 0 get equivalence:
nR(x/n Σ (og((//)))
Σ x log xfi
Σ
x1i log n
Σ
x11 log
log
Now have equivalence because the last term is constant that does not affect the argmin. Log regularizer: we set a to get equivalence, using similar logic as for entropy:
R(x/n)= Σ log(<|()/m) log n log [i].
Tsallis entropy regularizer: set -1 +
to get equivalence, using similar logic for entropy:
n R(z/n)= = = 1 --- -1
-1=1
n - 1
-
Σ 1= x11
1 1-9 3
E Numerical Experiments with Adaptive Stepsizes
In this section present numerical results when OFTRL and OOMD instantiated with adaptive stepsize [Duchi et al., 2011]: ?7t 1/v e/Ve+Ei E | l2 with some constant > We present our numerical experiments in Figure 4, where we choose e = 0.1.
22

---

Entropy (OMWU)
Log regularizer
Sq. Fuclidean norm
OGDA
1.0
1.0
1.0
1.0
0.8
0.8
0.8
0.8
0.6
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.6
0.8
1.0
0.6
1.0
0.6
0.8
1.0
0.8
[1]
x111]
[1
Equiibrium gap
10-1
10
10
10"
10-2
10-2
10
10-2
10-3
10-3
10-3
10"4
10a
10
10a
10
10
10a
10'
10a
Iteration
Iteration
lteration
Iteration
Figure 4: Comparison the dynamics produced by three variants of OFTRL with different regulariz- ers (negative entropy, logarithmic regularizer, and squared Euclidean norm) and OGDA in the same game Aş defined in (2) 8 == 10-2 and adaptive step size with 0.1. The bottom row shows the duality gap achieved by the iterates.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction match both the theoretical and experimental results of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The extension to the general m x n game does not work for the Euclidean and log regularizers because the rescaling factors would be different for the row and column players.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
23

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specing well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
See Section 2, Section and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
See Figure/ I and Python codes in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
24

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
See Python code in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
swt.miiissiiooiiioooooociicspmic for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n //ips..coom httppsscccppbbb///pppccp gewp /CodeSubmia ss Pollicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
25

---

Answer: [Yes]
Justification:
See Python code in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There is randomness in experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Our simulations were done within few hours average consumer laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
26

---

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/ httppppssspppppiiii/ccccccooo...
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics. The research con- ducted in this paper conforms with it in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
27

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
28

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "1moj1uCogz", "reviewer": "Reviewer_DNGf", "summary": "The authors, through some hard instances of games study the fundamental differences in convergence of broadly two classes of algorithms which are OOMD and OFTRL. Particular algorithms of interest include the OGDA and the OMWU algorithm respectively. They show that OFTRL (in particular OMWU) necessarily exhibits slow last-iterate convergence and this leads to it having an undesirable dependence on the underlying game.", "questions": "1) Please clarify whether Assumptions 1 and 2 are satisfied by the specific regularizers such as entropic, euclidean and log or general regularizers that are 1-strongly convex wrt to $l_2$ norm.\n2) Does the hard example still hold with vanishing step sizes?\n3) Is the high-dimensional example applicable only for the specific regularizers mentioned.", "limitations": "yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper seems to capture an important property that differentiates the likes of algorithms such as OGDA and OMWU, two extremely popular optimistic algorithms known to achieve last-iterate convergence in zero-sum games. Now this paper mounts further evidence of ``slowness\" of OWMU and that it is unavoidable to have game dependent constants appearing in the guarantees! I think this is an important finding for this area.", "weaknesses": "This is a focused study on showing certain properties of a class of algorithms such as OFTRL and OOMD. In general it is not clear if some of the results apply to every regularizer satisfying the assumptions or to the particular ones of interest such as Euclidean, Entropic etc. Beyond a few clarifications which I have asked in the next section, I do not think there are major weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review! Below, we address your questions. \n\nQ1: *Please clarify whether Assumptions 1 and 2 are satisfied by the specific regularizers such as entropic, euclidean and log or general regularizers that are 1-strongly convex wrt to $\\ell_2$ norm.*\n\nA: We clarify that we only verify Assumptions 1 and 2 for specific regularizers, but not all 1-strongly convex regularizers wrt to $\\ell_2$ norm. In this current manuscript, we verify the two assumptions for the negative entropy, Euclidean and log regularizer. We can also show that the two assumptions hold for the family of (negative) Tsallis entropy regularizers: parameterized by $0 < \\beta < 1$, $R(x) = \\frac{1 - \\sum x[i]^{\\beta}}{1-\\beta}$. Together with entropy, Euclidean, and the log regularizer, we believe our results cover every commonly-used regularizer in the online learning literature. We will add the proof for Tsallis entropy regularizers in the revised version of the paper. \n\nQ2: *Does the hard example still hold with vanishing step sizes?*\n\nA: This is a great question! Our current proof only works for fixed step sizes. In the rebuttal PDF, we provide numerical results for AdaGrad stepsize, an adaptively decreasing step size schedule. The results show that the last iterate of the decreasing step-size version exhibits qualitatively similar behavior to its constant step-size counterparts. We conjecture that our results could be extended to the case of decreasing step sizes. We will add a discussion and leave whether OFTRL with vanishing/variable step size could have a fast last-iterate convergence rate as an important future direction. \n\nQ3: *Is the high-dimensional example applicable only for the specific regularizers mentioned?*\n\nA: The reduction in the high-dimensional setting requires structures of the regularizers and might not hold for all 1-strongly convex regularizers. As shown in the current paper, the reduction works for negative entropy, Euclidean, and log regularizers. We can also prove that the reduction works for the family of Tsallis entropy regularizers (see Answer to point 1 above). We will add this result in the revised version of the paper.", "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": "", "extra_scores": {}}, {"review_id": "DGdkqzkmpF", "reviewer": "Reviewer_7DUi", "summary": "This paper shows a limitation of optimistic multiplicative weights (OMWU) with a fixed learning rate: the last-iterate convergence rate can be arbitrarily large, depending on a game-dependent constant in normal form games. This demonstrates that the current upper bounds on convergence are not loose and that there is a real barrier to this dynamic.\n\nBroader Context:\nOptimistic online learning algorithms play an important role in solving games. The average iterates of OMWU have been shown to converge in zero-sum games at a rate of 1/T, which is better than the non-optimistic counterpart. Another important algorithm in this context is the online gradient descent ascent (OGDA), which has been shown to have last-iterate convergence of O(1/sqrt{T}), where the constant hides polynomial dependence on the problem parameters. Last-iterate convergence is a desirable property in the context of games. Since OMWU is a central tool for solving games, understanding its limitations is a fundamental question.\n\nThis paper reveals an inherent limitation of OMWU (and more generally, for some algorithms within the optimistic FTRL framework), showing that OGDA might sometimes enjoy better last-iterate convergence. The main property responsible for this limitation is the \"lack of forgetfulness.\"", "questions": "Do you think using time-dependent learning rates might improve the last-iterate convergence of OMWU?\nIf so, maybe it's worth discussing it or writing it as a limitation.", "limitations": "See the above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper answers a fundamental question in the \"learning in games\" community (solving games using online learning dynamics). \nI like also the presentation of the paper. For example, the authors made an effort to explain the intuition behind the construction of the hard game.", "weaknesses": "My only criticism is the following:\nIt might be the case that OMWU can have good last-iterate convergence when using changing learning rates. These are sometimes used to avoid such an issue of forgetfulness.\n\n(But I believe that analyzing fixed learning rate is a significant contribution on its own)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments!\n\nQ: *Do you think using time-dependent learning rates might improve the last-iterate convergence of OMWU? If so, maybe it's worth discussing it or writing it as a limitation.*\n\nA: We conjecture that slow last-iterate convergence of OMWU persists for time-dependent step sizes (learning rates). In particular, we conjecture that our hard example works for decreasing step sizes. In the rebuttal PDF, we provide numerical experiment results for AadGrad stepsize, an adaptively decreasing step size schedule. The results show that the last iterate of the decreasing step-size version exhibits qualitatively similar behavior to its constant step-size counterparts. We conjecture that our results could be extended to the case of decreasing step sizes. However, a time-dependent learning rate that occasionally increases the step size or other periodic learning rate schedules might be able to address the issue of non-forgetfulness. We will discuss time-varying step sizes in the revised version of the paper. We leave the question of how time-varying step sizes affect the last-iterate convergence rates of OFTRL algorithms as an interesting and important open question.", "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": "", "extra_scores": {}}, {"review_id": "Nbx2TOFa3L", "reviewer": "Reviewer_FqEz", "summary": "The paper investigates the last-iterate convergence properties of several classes of algorithms employed in zero-sum matrix games. As a core contribution, it is shown that a large class of iteration rules can not exhibit instance-independent convergence in zero-sum games of dimension 2. The result is further generalized to larger dimensions.", "questions": "Is it possible to extract a \"forgetfulness\" property for an arbitrary learning algorithm that must imply the algorithm has slow last iterate convergence?\n\nAre there significant differences between Theorems 1 and 2 to warrant stating them separately? Upon first read, it was difficult to understand what the main difference was, and Theorem 2 seems to be a corollary of Theorem 1 looking at the proof in the appendix.", "limitations": "See weaknesses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper tackles an important problem and makes a potentially significant contribution to our understanding of learning dynamics in zero-sum matrix games.\n\nI think the results are rigorously developed, and while I did not verify the details of all the proofs, they seem to be correct.", "weaknesses": "The concept of a \"forgetful algorithm\" could be made more explicit, perhaps as a definition. It is not clear to me what property makes an algorithm forgetful by construction. An explicit definition (if it is possible at all) could greatly clarify the work.\n\nAs a possible weakness, the stated negative results apply to a particular class of algorithms (OFTRL) and potentially might be sidestepped.\n\nThe formulation of the main theorems could be clarified or perhaps simplified. For instance, theorem 2 has a rather complicated statement, which to my understanding just means either the duality gap can not go to zero (in which case it can be stated as such directly), or the duality gap can not go to zero uniformly (in which case item 1 should have a statement \"over all possible loss matrices\").\n\nI think one weakness of the paper is the presentation/organization. I found it difficult to follow the main ideas and the main contribution of the paper. For instance, the generalization to higher dimensions, while interesting, seems to be a minor contribution from a theoretical perspective, while significant space is dedicated to its proof ideas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging that we made a significant contribution to an important question and for the constructive comments on the presentation. We will incorporate your suggestions and improve the presentation in the next version of the paper. Below, we address your questions. \n\nQ1: *Is it possible to extract a \"forgetfulness\" property for an arbitrary learning algorithm that must imply the algorithm has slow last iterate convergence?*\n\nA: Our paper aims to understand the slow last-iterate convergence of OMWU and, more generally, OFTRL-type and certain Optimistic OMD-type algorithms. Our proof and hard game instances build on the intuition that these algorithms lack forgetfulness: they do not forget the past quickly and play actions that performed well in the past, even if their recent performance is bad (see also Lines 70-99 in the Introduction). We are the first to connect the intuitive idea of forgetfulness to last-iterate convergence. Even without a formal definition of “forgetfulness”, we believe that this intuitive connection with last-iterate convergence is a novel contribution.\n\nPutting the finger exactly on a formal, precise definition of forgetfulness appears to be challenging. We did try, but found it rather difficult. For example, our first attempt was to define it as any algorithm that is \"mean-based\", that is, the decision at each time depends on the past gradients solely through their mean. Such algorithms give equal weights to all past observations and are thus intuitively not forgetful. However, we quickly realized that while this covers all FTRL algorithms, it does not even cover their optimistic version (OFTRL, which is our main focus). We hope this convinces the reviewer that finding a formal and general definition for the lack of forgetfulness could be non-trivial. At any rate, the “lack of forgetfulness” is just an intuitive explanation for the phenomenon. We view our most important (and surprising) result to be the fact that all known OFTRL variants have these convergence issues. It would be interesting to come up with a formal definition that captures a broader class of algorithms, though that seems difficult and we leave it as future work.\n\n\nQ2: *Are there significant differences between Theorems 1 and 2 to warrant stating them separately? Upon first read, it was difficult to understand what the main difference was, and Theorem 2 seems to be a corollary of Theorem 1 looking at the proof in the appendix.*\n\nA: We clarify that Theorem 2 is indeed a corollary of Theorem 1. Thank you for pointing it out; we will make it clear in the next version of the paper. Theorem 1 is a more technical theorem that states the OFTRL learning dynamics have a constant duality gap even after $1/\\delta$ steps. Theorem 2 is a more high-level theorem that states OFTRL learning dynamics cannot have a last-iterate convergence rate that solely depends on the dimension and the time. Thus, game-parameter dependence is unavoidable for OFTRL algorithms, which provides a clearer comparison between OFTRL and OGDA since the latter has an $O(\\frac{\\textnormal{poly}(d_1, d_2)}{\\sqrt{T}})$ last-iterate convergence rate. In summary, while Theorem 2 is a direct corollary of Theorem 1, we state Theorem 2 separately to highlight our main contribution and the difference between OFTRL and OGDA.\n\nC1: *As a possible weakness, the stated negative results apply to a particular class of algorithms (OFTRL) and potentially might be sidestepped.*\n\nA: Although our results only hold for OFTRL, we believe they are still significant given that OFTRL is arguably one of the most studied classes of online learning algorithms and covers many standard algorithms, including the classical OMWU. We also want to emphasize that the existing positive results are even more restrictive: only OGDA and OMWU have proven concrete last-iterate convergence rates. Inspired by OMWU’s weaker convergence guarantees compared to OGDA, we demonstrate that this disadvantage is unavoidable and, in fact, applies to a broader class of OFTRL algorithms.", "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": "", "extra_scores": {}}, {"review_id": "kQLXNH8I9Z", "reviewer": "Reviewer_RnhV", "summary": "The present work studies the last iterate convergence of learning algorithms in zero sum games. Existing results have shown that although OMWU and OGDA both enjoy the $O(1/T)$ ergodic convergence rate, their best existing last iterate convergence rates exhibit a nontrivial gap. This paper constructs a particular hard example showing that such a gap is due to a fundamental limitation of the OMWU algorithm, rather than the sub-optimality of existing analysis. From this hard example, the key insight is that fast last iterate convergence requires learning algorithms to forget the past.", "questions": "Some minor comments: \n\n- In line 51-51 it is quoted from (van Erven, 2021) that FTRL is conventionally believed to be better than OMD. From the perspective of online convex optimization, I feel this is actually a bit more nuanced, as the examples I'm aware of (where FTRL beats OMD) concern time varying learning rates, which is different from the constant learning rates considered in this paper. \n\n- The wording of Theorem 2 could be improved.", "limitations": "Limitations are adequately addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper is very cool. Last iterate convergence is an important problem for learning in games, and this paper naturally motivates it by the existing theoretical and empirical gap between OMWU and ODGA. To tackle this problem, the paper then presents a particularly nontrivial analysis on the learning dynamics of Optimistic FTRL in games, despite the appeared simplicity of the constructed example. The takeaway message on the importance of forgetting is elegant, which might inspire future works on algorithm design. I also appreciate the graphical illustration on the learning dynamics, which makes the very technical proof intuitively easier to understand. Related works seem to be thoroughly discussed. \n\nFrankly speaking, the analysis in this paper is quite involved, so I only have a high level understanding of the proof while struggling on the details. However, as far as I can see, the high level intuition makes sense, and the numerical experiments are quite helpful.", "weaknesses": "This paper is already strong in my opinion, so I don't have any major complaint. One possible aspect to improve is the presentation. There are certain parts in the analysis that are particularly involved, so it might be better to write less quantitatively in the main paper, and leave those parts to the appendix. For example, Assumption 2 and the discussion right after it. I would also appreciate a further simplified proof sketch, specifically, more words and less math.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and the constructive comments on the presentation. We will incorporate your suggestions in the revised version of the paper. Specifically, we will update the flow in section 3 and make Assumption 2, the discussion, and the proof sketch more reader-friendly. Below, we answer your questions. \n\nQ1: *In line 51-51 it is quoted from (van Erven, 2021) that FTRL is conventionally believed to be better than OMD. From the perspective of online convex optimization, I feel this is actually a bit more nuanced, as the examples I'm aware of (where FTRL beats OMD) concern time varying learning rates, which is different from the constant learning rates considered in this paper.*\n\nA: Thank you for raising this point! We will add a remark for this claim in the revised paper. We also conjecture that slow last-iterate convergence rates for OFTRL algorithms persist even for time-varying learning rates. In particular, we conjecture that our hard example works for decreasing step sizes. In the rebuttal PDF, we provide numerical experiment results for AadGrad stepsize, an adaptively decreasing step size schedule. The results show that the last iterate of the decreasing step-size version exhibits qualitatively similar behavior to its constant step-size counterparts. We conjecture that our results could be extended to the case of decreasing step sizes. However, a time-dependent learning rate that occasionally increases the step size or other periodic learning rate schedules might be able to address the issue of non-forgetfulness. We will discuss time-varying step sizes in the next version of the paper. We leave the question of how time-varying step sizes affect the last-iterate convergence rates of OFTRL algorithms as an interesting and important open question. \n\nQ2: *The wording of Theorem 2 could be improved.*\n\nA: Thank you for the comment! We actually accidentally omitted the term “there is no function $f$ such that” before “... the corresponding learning dynamics” in the statement. We will improve the wording in the revised version.", "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": "", "extra_scores": {}}]

Author rebuttal:
**Discussion on Dynamic Step Sizes**: Our negative results hold for OFTRL with *fixed* step sizes. We conjecture that the slow last-iterate convergence of OFTRL persists even with *dynamic* (time-varying) step sizes. In particular, we believe our counterexamples still work for OFTRL with decreasing step sizes. This is because decreasing the step size makes the players move even slower, and they may be trapped in the wrong direction for a longer time due to the lack of forgetfulness. In the PDF, we include numerical results for OFTRL with adaptive stepsize akin to Adagrad [1], which supports our intuition. We observe that the duality gap of the last iterate exhibits qualitatively similar behavior to its fixed step size counterparts. Investigating the effect of dynamic step sizes on last-iterate convergence rates is an interesting future direction.

[1] Duchi, John, Elad Hazan, and Yoram Singer. "Adaptive subgradient methods for online learning and stochastic optimization." Journal of machine learning research. 2011

Meta-review: A clear accept paper. Identifying OMWU's inherent weakness is an interesting finding, and identifying the root cause -- don't forget quickly enough-- is a plus on top.
Decision: Accept (poster)