Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
Authors: Ioannis Anagnostides
Tuomas Sandholm
Venue: NeurIPS 2024 poster (2024)
Keywords: smoothed complexity
zero-sum games
optimistic gradient descent
linear convergence
Primary area: algorithmic_game_theory
TL;DR: We show that a certain class of first-order methods attain polynomial smoothed complexity in zero-sum games.

Abstract: Gradient-based algorithms have shown great promise in solving large (two-player) zero-sum games. However, their success has been mostly confined to the low-precision regime since the number of iterations grows polynomially in $1/\epsilon$, where $\epsilon > 0$ is the duality gap. While it has been well-documented that linear convergence---an iteration complexity scaling as $\text{log}(1/\epsilon)$---can be attained even with gradient-based algorithms, that comes at the cost of introducing a dependency on certain condition number-like quantities which can be exponentially large in the description of the game. To address this shortcoming, we examine the iteration complexity of several gradient-based algorithms in the celebrated framework of smoothed analysis, and we show that they have polynomial smoothed complexity, in that their number of iterations grows as a polynomial in the dimensions of the game, $\text{log}(1/\epsilon)$, and $1/\sigma$, where $\sigma$ measures the magnitude of the smoothing perturbation. Our result applies to optimistic gradient and extra-gradient descent/ascent, as well as a certain iterative variant of Nesterov's smoothing technique. From a technical standpoint, the proof proceeds by characterizing and performing a smoothed analysis of a certain error bound, the key ingredient driving linear convergence in zero-sum games. En route, our characterization also makes a natural connection between the convergence rate of such algorithms and perturbation-stability properties of the equilibrium, which is of interest beyond the model of smoothed complexity.

Convergence of log(1/c) for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
Ioannis Anagnostides
Tuomas Sandholm Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc. Optimized Markets, Inc. sandholm@cs, cmu edu
Carnegie Mellon University ianagnos@cs. cmu. cmu.edu
Abstract
Gradient-based algorithms have shown great promise in solving large (two-player) zero-sum games. However, their success has been mostly confined to the low- precision regime since the number of iterations grows polynomially in 1/c, where e > 0 is the duality gap. While has been well-documented that lin- ear convergence-an iteration complexity scaling as log(1/e) (g((/))-can be attained even with gradient-based algorithms, that comes the cost of introducing a depen- dency certain condition number-like quantities which can be exponentially large in the description the game.
To address this shortcoming, we examine the iteration complexity of several gradient-bar based algorithms in the celebrated framework of smoothed analysis, and we show that they have polynomial smoothed complexity, in that their number of iterations grows a polynomial in the dimensions of the game, log(L/e), and 1/0, where measures the magnitude of the smoothing perturbation. Our result applies to optimistic gradient and extra- satra-gradient descent/ascent, as well as a certain iterative variant of Nesterov's 's smoothing technique. From technical standpoint, the proof proceeds by characterizing and performing smoothed analysis of a certain error bound, the key ingredient driving linear convergence in zero-sum games. En route, our characterization also makes a natural connection between the convergence rate of such algorithms and perturbation-staee stabilltt properties of the equilibrium, which is of interest beyond the model of smoothed complexity.
Introduction
We consider the fundamental problem of computing an equilibrium strategy for (two-player) zero-sum game
min max (xx Ay), #EA" YEAm
where Ad+1_ (x 12d+1 x T 14+1 1} represents the d-dimensional probability simplex and Rexm the payoff matrix of the game. Tracing all the way back to Von Neumann's celebrated minimax theorem [von Neumann, 1928], zero-sum games played pivotal role in the carly development of game theory [von Neumann and Morgenstern, 1947] and the crystallization of linear programming duality [Dantzig, 1951]. Indeed, in light of the equivalence between zero-sum games and linear programming [Adler, 2013, von Stengel, 2023, Brooks and Reny, 2023], many central optimization problems be cast (1).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

State of the art algorithms for solving zero-sum games can be coarsely classified based on the desired accuracy of a feasible solution (x. y). measured in terms of the duality gap
(2 y) == max (x. Ay') min (a', Ayy). V'EA"
(2)
x'EA"
In the so-called low-precision regime, where one is content with a crude solution (o", yy) such that ((x=", "²)====== > O, the best available algorithms typically revolve around the framework of regret minimization, both in practice [Farina et al., 2021, Brown and Sandholm, 2019, Zinkevich et al., 2007, Tang et al., 2023] and in theory [Carmon et al., 2020, 2019, 2024, Grigoriadis and Khachiyan, 1995, Clarkson et al., 2012, Alacaoglu and Malitsky, 2022]-in conjunction with other techniques to speed up the per-iteration complexity, such variance reduction, data structure design, and sparsification [Zhang and Sandholm, 2020, Farina and Sandholm, 2022]. Such algorithms have been central to landmark results in practical computation of equilibrium strategies even in enormous games [Brown and Sandholm, 2018, Bowling et al., 2015, Moravěík et al., 2017, Perolat et al., 2022].
The high-precision regime, where e < poly(nem) has turned out to be more elusive, with current LP-based techniques struggling to scale favorably in large instances. This deficiency can be in part attributed to the relatively high per-iteration complexity of LP-based approaches, such as interior- point methods or the ellipsoid algorithm, as well as their intense memory requirements. promising antidote is to instead rely on iterative tradient-based methods that have minimal per-iteration cost. Indeed, in a line of work pioneered by Tseng [1995], it is by known well-documented that linear convergence- an iteration complexity scaling only as (1e( ( been achieved even with such methods [Tseng, 1995, Gilpin et al., 2012, Wei et al., 2021, Applegate et al., 2023, Fercoq, 2023]. There is, however, major caveat to those results: the number of iterations no longer grows polynomially with the dimensions of the game n and m, but instead depends on certain condition number-like quantities that could be exponentially large in the description of the problem; it is thus unclear how to interpret those results from a computational standpoint.
To address those shortcomings, in this paper we work in the celebrated framework of smoothed analysis pioneered by Spielman and Teng [2004]. Namely, our goal is to characterize the iteration complexity of certain gradient-baser algorithms in zero-sum games when the payoff matrix A is subjected to small but random perturbations, as formally introduced below.
Definition 1.1 (Zero-sum games under Gaussian perturbations). Let A E [-1,1]=xm, We assume that the payoff matrix is given by A ;= A + G, where each entry of G is an independent (univariate) Gaussian random variable with zero mean and variance x² < 1.
Randomness here is only injected into the payoff matrix and not the set of constraints (that is, the probability simplex), which the natural model: after applying the perturbation, the problem should still be zero-sum game in the form of (1). Under this model, we investigate the convergence of the following gradient-ber based algorithms.' (Their formal description is given later in Appendix B.)
1. optimistic gradient descent/ascent (OGDA) [Popov, 1980];
2. optimistic multiplicative weights update (OMWU) [Syrgkanis et al., 2015, Chiang et al., 2012, Rakhlin and Sridharan, 2013];
3. extra-gradient descent/ascent (EGDA) (Korpelevich, 1976]; and [Gilpin et al., 2012,
4. iterative variant of Nesterov's ' smoothing technique ( (IterSmooth th)
Nesterov, 2005].
Smoothed complexity allows interpolating between worst-case analysis- whenn the variance of the noise o² is negligible- and average-case maalysis-whee the noise dominates over the underlying input. An average-case analysis is often unreliable since-as as Edelman [1993] convincingly argued a fully random matrix does not necessarily capture typical instances encountered in practice. Spielman and Teng [2004] put forward the framework of smoothed analysis as an attempt to explain the performance of algorithms in realistic scenarios; to understand how brittle worst-case instances really are. They famously proved that the simplex algorithm, under a certain pivoting rule, enjoys polynomial smoothed complexity, meaning that its running time is bounded by some polynomial in the
'The vanilla gradient descent/ascent algorithm does not even converge (in a last-iterate sense) zero-sum games (e.g. I [Mertikopoulos et al., 2018J.. which is why our analysis revolves around certain variants thereof. It is worth noting that regret minimization techniques provide guarantees concerning the average iterates, a distinction blurred in our introduction.
2

---

size of the input and 1/a. Smoothed analysis is by now well-accepied algorithmic framework with a tremendous impact in the analysis of algorithms. We also argue that it is particularly mell-motivtted from a game-theoretic perspective: there is often misspecification or noise when modeling game, so smoothed analysis offers a compelling way of bypassing pathological instances that are perhaps artificial in the first place.
Nevertheless, we are not aware of any prior work operating in the smoothed complexity model per Definition 1.1 in the context of zero-sum games. To clarify this point, it is important to stress here that although zero-sum games can be immediately reduced to linear programs, that reduction is less clear in the smoothed complexity model. In particular, one set of constraints in the induced linear program takes the form Ay S vl,, b. where 1, IR" is the all-ones vector, According to the usual model of smoothed complexity in the context of linear programs, randomness has to be injected into both A and b, but that clearly disturbs the validity of the equivalence. More broadly, reductions in the smoothed complexity model are quite delicate [Bläser and Manthey, 2015]; as further example, even reductions involving solely linear transformations can break in the smoothed complexity model since independence a crucial assumption in this framework-is not guaranteed to carry over. Relatedly, one interesting direction arising from the work of Spielman and Teng [2003] is to perform smoothed analysis in linear programs which are guaranteed to be feasible and bounded, no matter the perturbation; zero-sum games under Definition 1.1 constitute such a class. Besides the point above, different algorithms designed for the same problem can have entirely different properties, not least in terms of their smoothed complexity. The class of algorithms we consider in this paper is quite distinet from the ones shown to have polynomial smoothed complexity in the context of linear programs (described further in Appendix A). In many ways, gradient-basee methods are simpler and more natural, which partly justifies their tremendous practical use. As result, understanding their smoothed complexity is an important question.
1.1
Our results
Our main contribution is to show that, with the exception of OMWU, the other gradient- based algorithms mentioned above (Items 3 and 4) have polynomial smoothed complexity with high probability that is to say, with probability at least poly(rmm
Theorem 1.2. With high probability over the randomness of A E Raxm (Definition 1.1), OGDA, EGDA and Imor th converge to an e-equilibrium after poly(n, m, 1/o) log(1/e) iterations.
The main takeaway of this result is that, modulo pathological instances, certain gradient-based algorithms are reliable solvers in zero-sum games even in the high-precision regime. Similarly to earlier endeavors in the context of linear programs [Spielman and Teng, 2004, Blum and Dunagan, 2002], dependency of poly(1/a) the class of interior-poin pornnt methods whose running time grows as log(1/0
/ (as in Theorem 1.2) is what we should expect; the one exception
but those algorithms are (weakly) polynomial even in the worst case. We further remark that the polynomial dependency on 7 and m in Theorem 1.2 can almost certainly be improved, and we made no effort to optimize it.
Regarding OMWU, which is not covered by Theorem 1.2, we also obtain a significant improvement in the iteration complexity compared to the worst-case analysis of Wei et al. [2021], but our bound is still not polynomial. As we explain further in Appendix C.3, the main difficulty pertaining to OMWU is that the analysis of Wei et al. [2021] gives (at best) an exponential bound no matter the geomelry of the problem. With that mind, our result is essentially the best one could hope for without refining the worst-case analysis of OMWU, which not within our scope here. We anticipate that our characterization herein will prove useful in conjunction with future developments in the worst-case complexity of OMWU, as well as in the analysis of other iterative methods.
The error bound The central ingredient that enables gradient- gradient-based algorithms to exhibit linear convergence is certain error bound, given below as Definition 1.3. For compactness in our notation, we let X' := A and y = n.. We then let x := v). Z = X x V, and Z = X x y", where X* and yr represent the (convex) set of equilibria for Player and Player y. respectively.
Definition 1.3 (Error bound). Let ((2) denote the duality gap as introduced in (2). We say that the zero-sum game (1) satisfies an error bound with modulus R E B if
Vz E Z. (xx) 2 x||= 11z- 1I2-(=))1
(3)
3

---

Above, IIg. (-) denotes the (Euclidean) projection operator, the set of games with a unique equilibrium has measure one, so we can safely replace 1I (z) by the unique equilibrium x" z". has been known at least since the work of Tseng [1995] that affine variational inequalities indeed satisfy (3). Nevertheless, it should come to no surprise that, even in 3 x 3 games, R can be arbitrarily small (Proposition 3.1), which in turn means that, linear convergence notwithstanding, the number of iterations prescribed by an analysis revolving around (3) can be arbitrarily large. In fact, with the exception of OMWU, which is to be discussed further below, Definition 1.3 suffices to establish linear convergence (essentially) based on existing results, Our main result pertaining to Definition 1.3 is that the modulus is likely to be polynomial in the smoothed complexity model:
Theorem 1.4. With high probability over the randomness of A (Definition 1.1), the error bound per Definition 1.3 is satisfied for any sufficiently small k Z poly(a, 1/ (n(m))
To establish this result, the first step lower bound k in terms of certain natural geometric features of the problem (Theorem 3.6), which is discussed further in Section 3.1. Establishing Theorem 1.4 then reduces to analyzing each of those quantities under Definition 1.1. It turns out that bounding those quantities also suffices for characterizing OMWU, whose existing analysis due to Wei et al. [2021] involves some further ingredients besides the eπrоr bound of Definition 1.3.
Further implications Our characterization of the error bound given in Theorem 3.6 has some further important implications. First, a well-know vexing issue regarding computing equilibria even in zero-sum games is that solution with small duality gap can still be relatively far from the equilibrium in the geometric sense, a phenomenon further exacerbated in multi-player games [Etessami and Yannakakis, 2007]. Therefore, results providing guarantees in terms of the duality gap are not particularly informative when comes to computing strategies close to the equilibrium in a geometric sense. At the same time, there are ample reasons why the latter guarantee is more appealing [Etessami and Yannakakis, 2007]. Theorem 1.4 implies that such concerns can be alleviated in the smoothed complexity model:
Corollary 1.5. With high probability over the randomness of A (Definition 1.1), any point 2 E Z with (z2) < satisfies ||= 2" S poly (,, 1/o).
Beyond smoothed analysis, Theorem 3.6 applies to any non-degenerate game (Definition 3.2), and can be thereby used to parameterize the rate of convergence of gradient-based algorithms based on natural and interpretable game-theoretic quantities of the underlying game, which has eluded prior work. In particular, make a natural connection between the complexity of gradient- based algorithms and perturbation stability properties of the equilibrium. In light of misspecificattios which often present in temee-thcoretic modeling, focusing on games with perturbation-stabl equilibria is moll-motivated and has already received ample of interest in prior work [Balcan and Braverman, 2017, Awasthi et al., 2010]; more broadly, perturbation stability is common assumption in the analysis of algorithms beyond the worst-case model [Makarychey and Makarychev, 2021]. There are different natural ways of defining perturbation-stable games; here, we assume that any perturbation with magnitude below 8 >> O, in that || A' Alla S 8, maintains the support of the equilibrium and the nondeegenyyacy of the game; we call such games 5-support-stable (Definition 4.1). In this context, we show the following result.
Corollary 1.6. For any 8-support-stan stable zero-sum game, OGDA, EGDA and IterSmooth converge to an e-equilibrium after poly(n, m, 1/6) log(1/c) iterations.
That is, games in which 8 is not too close to O are more amenable to gradient- based algorithms, which is quite natural connection. Corollary 1.6 is shown by relating each of the quantities involved in Theorem 3.6 parameter ê defined above.
2
Notation
Before we proceed with our technical content, we first take the opportunity to streamline our notation; further background smoothed analysis and description of the algorithms referred to earlier (Items 1 to 4) is given later in Appendix B, as it is not important for the purpose of the main body.
*Definition 1.3 also readily establishes linear convergence for other compelling primal-dual algorithms, as shown recently by Applegate et al. [2023]; in that paper, the error bound was referred to as "sharpness," a terminology employed in other papers well (e.g., [Zarifis et al., 2024]).

---

We use boldface letters, such as y. b, to represent vectors in Euclidean space. For vector R", we access its ith coordinate via a subscript, namely z;. Superscripts (together with parantheses) are typically reserved for the (discrete) time index. We denote by ||z]|| the Fuclidean norm, | -i== at the foe norm by || = m&x sign (zg], and the & norm by ||||| == Ex=1e | For x, E R", we let dist(ar, (2r, æ²) = || æ'Il- span(-) represents the linear space spanned by given set of vectors. For a E R and subset B C [m]. we denote by EB E IR the subvector of a induced by B. We let 1, E Rh be the all-ones vector of dimension n; we will typically omit the subscript when it is clear from the context. For vectors a E R" and y E R", we write (ær y) E Rn+" to denote their concatenation. Throughout this paper, we use æ and y to denote the strategy of Player and Player y, respectively.
To represent matrices, we use boldface capital letter, such as A, Q. will sometimes be convenient to use A E Rem to represent vectorization of A Raxm, We overload notation by letting || || be the spectral norm of A. For a matrix A E RR* and subsets B C [m], S [m], we denote by AB,N E B the submatrix of A induced by B and N. Ai, and A, represent the ith row and jth column of A, respectively. The singular values of matrix M E Rdxd are denoted by a (M) 2 (M) 2 ... 2 dd( 2 0 (not to be confused with our notation for the variance r²). To be more explicit, we may also use max (M) = 0i (M( and mii (M) = oM(M
3 Smoothed analysis of the error bound
In this section, we perform smoothed analysis of the error bound as introduced earlier in Defini- tion 1.3-in (two-player) zero-sum games. is first instructive to point out why smoothed analysis is useful in the first place: the modulus & can be arbitrarily close to 0 even when n = m = 3 (that is, 3 x games); this is detrimental as the iteration complexity of algorithms such as OGDA grows as a polynomial in 1/K.
Proposition 3.1. There exists a 3 x 3 zero-sum game such that k. per Definition 1.3 is arbitrarily close to O.
In proof, it is enough to consider the ill-conditioned diagonal matrix
0
0
A =
27
0
(4)
0 1
where 0 < 7 < 1. The (unique) equilibrium of (4) reads x² y" 3+27 (2,1,2 3 Now, considering x = (1,0, 0) and y = (0, 0, 1). for the duality gap we have (ax, y) = 7, while the distance of (x: y) from the optimal solution (x", yy" is at least 3 In turn, by Definition 1.3, this
3427"
means that x < 2%y So, Proposition 3.1 follows by taking 7 + 0.3
Proposition 3.1 exposes one type of pathology that can decelerate basedd algorithms, which evidently related to the poor spectral properties the payoff matrix. This intuition quite helpful when equilibria are fully supported as is the case in (u)-but has to be significantly refined more broadly, as we formalize in the sequel.
To sidestep such pathological examples, we thus turn to the smoothed analysis framework of Defini- tion 1.I.
3.1 Overview
The most natural approach to analyze the error bound in the smoothed complexity model is to rely on an existing (worst-case) analysis proving that a positive exists, and then attempt to refine that analysis. Yet, at least based on such prior results we are aware of, that turns out to be challenging. As an example, let consider the recent analysis of Wei al. [2021]. As we explain in more detail in Appendix C.3, Wei et al. [2021] relate the modulus x of the error bound to the (inverse of the) norm of a solution to a certain feasible linear program; the existence of a legitimate k > then follows readily from feasibility. Now, this reduction seems quite promising: Renegar [1994] has shown that the
'If we want to specify the game with (finite) number of L bits, Proposition 3.1 tells us that the modulus be exponentially small in L.
5

---

norm of a solution to linear program can be bounded in terms of its condition number- the distance infeasibility in our case, and Dunagan al. [2011] later proved that the condition number of linear programs is polynomial in the smoothed complexity model. Nevertheless, there are some difficulties materializing that argument. First, the induced linear program involves terms depending on both the payoff matrix and the geometry of the constraints (the probability simplex in our case). Consequently, the analysis of Dunagan et al. [2011] I] does not carry over since randomness is only injected into the payoff' matrix. The second and more important obstacle is that the induced linear program depends on the optimal solution, which in turn depends on the randomness of the payoff matrix; this significantly entangles the underlying distribution. As there exponentially many possible configurations, cannot afford to argue about each one separately and then apply the union bound. This difficulty is in fact known to be the crux in performing smoothed analysis [Spielman and Teng, 2004].*
To address those challenges, we provide a new characterization of the error bound in terms of some natural quantities of the underlying game (Theorem 3.6), which in some sense capture the difficulty of the problem. We are then able to use a technique due to Spielman and Teng [2004], exposed in Section 3.3, to bound the probability that each of the involved quantities is close to 0 (Propositions 3.8 to 3.10), even though the underlying distribution is quite convoluted. The resulting analysis follows the one given by Spielman and Teng [2003] in the context of termination of linear programs, but still has to account for a number of structural differences.
In what follows, we structure our argument as follows. First, in Section 3.2, we relate the modulus to some natural quantities capturing key geometric features of the problem. Section 3.3 then proceed by analyzing those quantities in the smoothed analysis framework.
3.2 Characterization of the error bound
Our first goal is characterize the error bound in terms of certain natural quantities, which will then enable us to provide polynomial error bounds in the smoothed complexity model. Our only assumption here that the zero-sum game is degeneeeee,,,, in the sense of Definition 3.2 below; this can always be met with the addition of an arbitrarily small amount of noise (Lemma C.I). As such, our characterization here has an interest beyond the smoothed analysis framework, casting the error bound in terms of more interpretable game-the quantities; for example, concrete implication is given in Section
Let us denote by e the value of game (1), that is,
f min max (ar, Ay) max min (ar, Ay), yEy øE
#E yEy
which is consequence of the minimax theorem [von Neumann, 1928]. We are now ready to state the formal definition of a non-degenerate game.
Definition 3.2 (Non-degenerate game). A zero-sum game described with payoff matrix A and value v is said to be non-degenerate if it admits unique equilibrium (x* yy") E Z, and x² and y² make tight exactly of the inequalities fa; 2 O]se(m] (xxAA.,) S v])e(m] and m of the inequalities (y) 2 JE) U ((y, A..) 2 v) ve]]) respectively.
In the sequel, we will make constant use of the fact that the set of degenerate games has measure zero under the law induced by Definition 1.1 (Lemma C.I).
In this context, we let B(x*) == (i E [x] x; > 0} denote the support of x (corresponding to
Player 2),, and similarly N(y²) = [j [m] y > 0} for the support of Player y. The striet complementarity theorem [Ye, 2011] tells us that B indexes exactly the set of tight inequalities (1y, Ai,) 2 v)ve(n). and symmetrically, N indexes exactly the set of tight inequalities {(x, A S "hjejm]- In particular, this implies that B |N| with probability 1. It will also be convenient to define B = [n] \ B and N = [m] NN
Now, at a high level, one can split solving zero-sum game into two subproblems: i) identifying the support of the equilibrium, and ii) solving the induced linear system specify the exact probabilities
*This not concern in the unconstrained setting, where X = R² and y = R" in which polynomial smoothed complexity follows readily from existing results relating the convergence of OGDA or EGDA to the condition number of the payoff matrix A (e.g., [Mokhtari et al., 2020, Li et al., 2023, Azizian et al., 2020]). which in turn well-known to be polynomial in the smoothed complexity model [Spielman and Teng, 2004].

---

within the support. It will be helpful to have that viewpoint in mind in the upcoming analysis, and in particular in the proof of Theorem 3.6. Roughly speaking. thinking of as measure of the problem's difficulty, we will relate to i) the difficulty of identifying the support of the equilibrium, and ii) the difficulty of solving the induced linear system. To be clear, those two subproblems are only helpful for the purpose of the analysis, and they are certainty intertwined when using algorithms such as OGDA.
Staying on the latter task, we will make use of a certain transformation so as eliminate one of the redundant variables. Namely, for any ØB E A(B) and ÿN E A(N), let us select a fixed pair of coordinates (i. B x N (for example, the ones with the smallest index). Using the fact that (āg. 1) = 1 and (yN 1) = 1, we can eliminate 2; and y by writing
AB. (2. Q7) (z) c) (ū. +
(5)
where ãेe E Ro D E EY (for B = { and Ñ = N \ {i}) coincide with Ey and UN on 20
all coordinates in B and N, respectively. and B,N = T(Q", b, c, d) for (non-singular) linear transformation T (BBN))(BM), (We spell out the exact definition of TT later in Appendix C.I, as it is not important for our purposes here; it follows by simply writing क; = (.. 1) and D 1 (ū. 1).) The point of transformation (5) is that, by eliminating one of the redundant variables, there is a convenient characterization of the equilibrium (Claim C.3); namely, Qy" = c and Q x= b.
We are now ready to introduce the key quantities upon which our characterization relies on. It turns out that those are analogous to the ones considered by Spielman and Teng [2003] in the context of analyzing the termination linear programs; this is not coincidental, as our analysis was especially targeted to do
Definition 3.3. Let A be the payoff matrix of non-degenerate game, (x* yy) E Z the unique equilibrium, and B S [m], C [m] the support of x and y² respectively. We introduce the following quantities.
1. (r((A) = min (x;;) and (A) = minseN( (U));
2. (A)( je (ar A (,J))) and (D(A) min (( vkx) v); and
3. (A) = miny dist Q span Q )) and YD (A) = min, dist Qt... span Qg-1.)).
where we use the shorthand notation B - ii B (i) (N -j = N (i)), and Q = Q(A) is defined in (5).
(Above, we adopt the convention that if a minimization problem is with respect to an empty set, the minimum is to be evaluated as 1.)
Item 3 above will enable us to control the norm of solutions to any linear system induced by Q, as we explain in the sequel. Our proof will actually rely on a slightly different matrix, which we call Q: the lemma below relates the geometry of Q to Q, and reassures us that the condition number of Q cannot be far from that of Q long - -E N y3 2 (A) (by Item 1) is not too close to 0. (A symmetric statement holds when focusing on Player y.)
Lemma 3.4. Let e = Qğ* = EEEE 3 Qu.f, and suppose that Q E B is such that its jth column is equal to Q.:j c. Then,
N -
min dist( Q.,j span Q R,))) 14 jeN
min (u..j span(S (pan(Q -y))-
v3
jeN
Next, we recall a fairly standard bound relating the magnitude of a solution to a linear system क = Mp with the smallest singular value of a full-rank matrix M.
Lemma 3.5. Let M E Raxd be full-rank matrix. For any क E Rd there is p E Rd with |p|| <
(M) ||]|| such that
ã == Mp Σ P.M.
7

---

Moreover, to connect Lemma 3.5 with (A), we observe that the smallest singular value can also be lower bounded in terms of the smallest distance of a column from the linear space spanned by the rest of the columns- which now matches the expression of Item 3 we saw earlier. In particular, we will make use of the so-called negative second moment identity [Tao et al., 2010] (Proposition C.4), which implies that
mmin Q)= 2
min dist (Q.j. span Q (pan(Q. N-)) (6)
EjEN dist
"Q.,, Q N,,))
I
JEÑ
Proposition C.4 also implies that 7D (A)
(A), and will suffice to lower bound 7/p
V
in the sequel. We are now ready to proceed with the main result of this subsection. Below, we use the notation "Z" to suppress lower-order terms and absolute constants.
Theorem 3.6. Let A be a non-degenerate payoff matrix, and suppose that (ap(A), an A)), are as in Definition 3.3. Then, the error bound (Defini- tion 1.3) is satisfied for any sufficiently small modulus
(Bp(A), (A)) and (yp(A),nD
1
K z so min(n, m)s
min (OAT(A))))((A))(())))))))))
is enough to explain how to lower bound x > such that maxy (x, Ay') - 2 K| x Ix (x]]] x||æ x=1l for any
X. In nutshell, our argument is divided based the magnitude À == || which can be thought of as a measure of closeness from the support of the equilibrium. When À < 1, which means that is still far from the support of the equilibrium, ma Ay') - is governed by 3p (A)) In the contrary case, our basic strategy revolves around showing that the error bound can be treated in the unconstrained case, which would then relate the modulus k to the smallest singular value of the underlying matrix (essentially by Lemma 3.5)-and subsequently to (P)) due to (6). Indeed, this turns out to be possible by working with matrix Q. as defined earlier in Lemma 3.4. We defer the precise argument to Appendix C.I.
3.3 Smoothed analysis
Having established Theorem 3.6, our next step show that each of the quantities introduced in Def- inition 3.3 is unlikely to be too close to O in the smoothed complexity model, which would then im- ply Theorem 1.4. The main difficulty lies in the fact that each configuration that may arise depends on the support of the equilibrium, which in turn depends on the underlying randomization of A, thereby significantly complicating the underlying distribution. Further, one cannot afford to argue about each configuration separately and then apply the union bound as there are too many possible configurations. To tackle this challenge, we follow the approach put forward by Spielman and Teng [2003].
In particular, given that all quantities of interest in Theorem 3.6 depend on the support of the equilibrium, it is natural to proceed by partitioning the probability space over all possible supports, and then bound the worst possible toc--hht is, the one maximizing the probability we want to minimize. In doing so. the challenge is that one has condition on the cquílibrium having a given support (formally justified by Proposition C.5). To argue about the induced probability density function upon such conditioning, is convenient perform change of variables from A to a new set of variables that now contains the equilibrium (x", .y") (Lemma C.6). The basic idea here is that since the event we condition on concerns the equilibrium, is helpful to have that equilibrium being part of our set of variables. The induced probability density function is now quite complicated, but can still be analyzed using the following lemma.
Lemma 3.7 (Spielman and Teng, 2003). Let p be the probubility density function of a random variable X. If there exist 8 > 0 and e E (0, 1] such that
p(t)) p(t)
0 05ig/56
2 c,
(7)
then
P < e X 2 0
<
e c
8

---

In words, random variables whose density is smooth in the sense of (7) are unlikely to be too close to O. Gaussian random variables certainly have that property (Lemma C.8), but is not confined to the Gaussian law; the analysis of Spielman and Teng [2003] and subsequently our result-is not tailored to the Gaussian case.
We are now ready to state our main results in the smoothed complexity model; the proofs are deferred to Appendix C.2. We commence with (p(A), which the easiest to analyze. In particular, the following result is a consequence of an anti-concentration bound with respect to a conditional Gaussian random variable (Lemma C.7).
Proposition 3.8. Let (r(A) be defined as in Item 2. For any 6 2 0,
5| S e emin(n, m)² (r(A)) P À
r²
The analysis of (A) is more challenging, and makes crucial use of Lemma 3.7. As we alluded to earlier, key step is to change variables from A B.N (Q, b, c, -)-i accordance with (5)-and then to (Q, xx", y²" based on Qý* c, Q X- b. It is important to note that Q longer contains independent random variables even though AB.N is (by Definition 1.1); this stems from the presence still overcome this issue of redundant variable in z'g (since (a'g. 1) 1). Nevertheless,
using Lemma 3.7, leading to the following bound.
Proposition 3.9. Let (P) be defined as in Item 3. For any 0.
4e min (n, m)
P A
(p)A S
4max |Q 20| +3
r²
Similar reasoning, albeit with some further complications, provides a bound for ap(A), which is given below.
Proposition 3.10. Let (A)(A) be defined as in Item 1. For any 2 O,
Se2 min(n, m)
F A
ap (A) S 1 + +12
Armed with Propositions 3.8 to 3.10 and Theorem 3.6, we can establish Theorem 1.2 by suitably leveraging existing results, as we formalize in Appendix C.3.
4 Parameterized results for perturbation-stable games
Another important implication of our characterization in Theorem 3.6 is that it enables connecting the convergence rate of gradient-based based algorithms to natural and interpretable game-theoretic quantities. In particular, here we highlight connection with perturbation-stae sense.
games, in the following formal
Definition 4.1 (Perturbation-staale games). Let A be the payoff matrix of non-degenerate game. We say that the game is 6-support-stable, with 6 > 0, for any A' with ||A A'll < 5 it holds that A' is non-degenerate game whose equilibrium has the same support A.
Perhaps the simplest example of support-stable game with favorable parameter > 0 arises when A is the 2 x 2 identity matrix. Indeed, as long as the perturbation parameter ô remains below a certain absolute constant, the perturbed game still admits a unique full-support equilibrium. To see this, suppose for the sake of contradiction that the perturbed game has an equilibrium such that Player 2 plays one of the two actions with probability 1. Player y would then obtain a utility of at least 1 - O()). But the value of the original game was 1/2, which in turn implies that the value of the perturbed game is 1/2 + (6); for a sufficiently small this leads to a contradiction. Similar reasoning applies with respect to Player y. (The previous argument carries over more broadly to diagonally dominant 2 x 2 payoff matrices.)
As we have highlighted already, games with perturbation-stale equilibria-all under different notions of stability-hat have already received attention in the literature [Balcan and Braverman, 2017, Awasthi et al., 2010] (cf. Cohen [1986]), and are part of a broader trend in the analysis of algorithms beyond the worst case (for further background, we refer to the excellent book edited by Roughgarden [2.21]). Our goal here is to make the following natural connection.

---

Theorem 4.2. Any S-support-stable game (per Definition 4.1) satisfies the ervor bound for any sufficiently small modulus
R 2 poly () n '''""
By virtue of our discussion in Appendix C.3, Theorem 4.2 immediately implies Corollary 1.6. Indeed, we observe that all parameters involved in Theorem 3.6 can be lower bounded in terms of the stability parameter of Definition 4.1, 1, as we formalize Appendix C.4.
Conclusions and future research
In conclusion, we performed the first smoothed analysis with respect to a number of well-studied gradient-based algorithms in zero-sum games. In particular, we showed that OGDA, EGDA and IterSmooth all enjoy polynomial smoothed complexity, meaning that their iteration complexity grows polynomial in the dimensions of the game, 1/o, and log(1/e); for OMWU, our analysis reveals a significant improvement over the worst-case bound due to Wei et al. [2021], but still remains superpolynomial. We also made connection between the rate of convergence of the above algorithms and natural perturbation stabbilit property of the equilibrium, which is interesting beyond the model of smoothed complexity.
number of interesting avenues for future research remain open. First, is it the case that DMWU has polynomial smoothed complexity or is there an inherent separation with the other algorithms we stud- ied? Answering this question the positive would necessitate significantly improving the worst-case analysis of OMWU due to Wei et al. [2021] (ef. Cai et al. [2024] for a recent development concerning the last-iterate convergence of OMWU). Beyond OMWU, our results could also prove useful for establishing polynomial bounds for other natural dynamics in the smoothed analysis framework. Moreover, characterization the error bound in Theorem 3.6 assumes that the game is non-degenen non-degenerate. This is an innocuous assumption in the smoothed complexity model, as it holds with probability 1, but nevertheless it would be interesting to generalize it to any game. Doing so could shed some light into whether Theorem 4.2 holds with respect other, perhaps more natural notions of perturbation stability beyond Definition 4.1. would also be interesting to investigate other models of smoothed complexity that account for dependencies between the entries of the payoff matrix [Bhaskara et al., 2024]. Moreover, our focus has been on zero-sum games under simplex constraints, but we suspect that more general positive results should be attainable under polyhedral constraint sets; perhaps the most notable such candidate is the class of extensive-form games |Romanovskii, 1962, von Stengel, 1996]. Even beyond (two-player) zero-sum games, Theorem 1.2 could apply to (multi- (multi-player) polyma- trix zero-sum games [Cai et al., 2016]. It is less clear whether the model of smoothed complexity can be informative when it comes convergence to coarse correlated equilibria in multi multi-player games.
Acknowledgments
We are grateful to the anonymous reviewers NeurIPS for their helpful feedback. The first author is indebted to Ioannis Panageas for many insightful discussions. This material is based on work supported by the Vannevar Bush Faculty Fellowship ONR Foundation grants R1-2312342 and RI-1901403, ARO award INF22100066 and NIH award A2401085001.
National Science
References
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, and Atsushi Iwasaki. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. In International Confer- ence on Artificial Intelligence and Statistics (AISTATS), 2023.
Iln Adler. The equivalence of linear programs and zero-sum games. Int. J. Game Theory, 42(1): 165-177, 2013.
Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction variational inequality methods. In Conference on Learning Theory (COLT), 2022.
10

---

Kimon Antonakopoulos, Elena Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra- gradient methods for min-max optimization and games. In International Conference on Learning Representations (ICIRR) 2021.
David L. Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming. 201 (1):133-184, 2023.
Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, and Santosh S. Vempala. On nash-equilibria of approximation-stable games. In International Symposium on Afgorithmic Game Theory (SAGT), 2010.
Waiss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statisties (2020), Proceedings of Machine Learning Research, 2020.
Maria-Florina Balcan and Mark Braverman. Nash equilibria in perturbation-stal -table games. Theory Comput., 13(1): 1-31, 2017.
Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, and Aravindan Vijayaraghavan. New tools for smoothed analysis: Least singular value bounds for random matrices with dependent entries. In Proceedings of the Annual Symposium Theory of Computing (STOC), 2024.
Markus Bläser and Bodo Manthey. Smoothed complexity theory. ACM Trans. Comput. Theory, 7(2): 6:1-6:21, 2015.
Avrim Blum and John Dunagan. Smoothed analysis of the perceptron algorithm for linear program- ming. Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), 2002.
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, and Aviad Rubinstein. Smoothed complexity of 2-player nash equilibria. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2020.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218):145-11) 2015.
Benjamin Brooks and Philip J. Reny. canonical game-75 years in the making-showing the equivalence of matrix games and linear programming. Economic Theory Bulletin, 2023.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: top professionals. Science, 359(6374):418-42222 2018.
Libratus beats
Noam Brown and Tuomas Sandholm. Solving imperfect-infonte information games via discounted regret minimization. In Conference on Artificial Intelligence (AAAT), 2019.
Luciana S. Buriol, Marcus Ritt, Félix Carvalho Rodrigues, and Guido Schäfer. On the smoothed price of anarchy of the traffic assignment problem. In Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), 2011.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos H. Papadimitriou. Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2): 648-655, 2016.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Yang Cai. Gabricle Farina, Julien Grand- -Clémennééent, Christian Kroer, Chung-Wer Lee, Haipeng Luo, and Weiqiang Zheng, Fast last-iterate convergence learning in games requires forgetful algorithms. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2019.

---

Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Coordinate methods for matrix games. In Proceedings of the Annual Symposium Foundations of Computer Science (FOCS), 2020.
Yair Carmon, Arun Jambulapati, Yujaa Jin, and Aaron Sidford. A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.
Xi Chen, Xiaotie Deng, and Shang- Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 2009.
Xi Chen, Chenghao Guo, Emmanouil- Xinzhi Zhang. Smoothed complexity local max-cut and binary max-esp. Proceedings of the Annual Symposium Theory of Computing (STOC), 2020.
Eimaanuil-Vasileios Vasileios Vlatakis Vlatakis-Gkarage Gkaragkounis, Mihalis Yannakakis, and
Xi Chen, Chenghao Guo, Himmanouil-Vasiled Smoothed complexity of SWAP in local graph partitioning, Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2024.
VlatakisGGkaragken and Mihalis Yannakakis.
Chao-Kai Chiang, Tianbao Yang. Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory (COLT), 2012.
Miranda Christ and Mihalis Yannakakis. The smoothed complexity of policy iteration for markov decision processes. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2023.
Kenneth L. Clarkson, Elad Hazan, and David Woodruff. Sublinear optimization for machine learning. Journal of the ACM, 59(5):23:1-23:49) 2012.
Joel E. Cohen. Perturbation theory of completely mixed matrix games. Linear Algebra and its Applications, 79:153-161 1986.
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Hedging under uncertainty: Regret minimization meets exponentially fast convergence. In International Symposium on Algorithmic Game Theory (SAGT), 2017.
Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM, 68(1):3:1-3:39 2021.
Leonardo Cunha, Gauthier Gidel, Fabian Pedregosa, Damien Scieur, and Courtney Paquette. Only tails matter: Average-case universality and robustness in the convex regime. In International Conference on Machine Learning (ICML), 2022.
George Dantzig. A proof of the equivalence of the programming problem and the game problem. In Tjalling Koopmans, editor, Activity Analysis of Production and Allocation, pages 330-335. John Wiley & Sons, 1951.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Innovations in Theoretical Computer Science Conference (ITCS), 2019.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Games and Economic Behavior, 92:327-348, 2015.
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, and Abhishek Shetty. Smooth nash cquilibria: Algorithms and complexity. In Innovations in Theoretical Computer (ITCS), 2024.
Asen L Dontchev and R Tyrrell Rockafellar. Implicit functions and solution mappings: A view from variational analysis, volume 616. Springer, 2009.
John Dunagan, Daniel A. Spielman, and Shang- Teng. Smoothed analysis of condition numbers and complexity implications for linear programming. Mathematical Programming, 126(2)3315- 350. 2011.
12

---

Alan Edelman. Eigenvalue roulette and random test matrices. Linear Algebra for Large Scale and Real-Time Applications, pages 365-368, 1993.
Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points (extended abstract). In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2007.
Gabriele Farina and Tuomas Sandholm. Fast payoff matrix sparsification techniques for structured extensive-form games. In Conference on Artificial Intelligence (AAAI), 2022.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Conference on Artificial Intelligence (AAAI); 2021.
Olivier Fercoq. Quadratic error bound of the smoothed gap and the restarted averaged primal-dum hybrid gradient, 2023.
Nicola Gatti, Marco Rocco, and Tuomas Sandholm. Strong Nash equilibrium is in smoothed P. In Conference on Artificial Intelligence (AAAI), 2013, Late-breaking paper track.
Yiannis Giannakopoulos. abs/2306.106000 2023.
smoothed FPTAS for equilibria congestion games. CoRR,
Yiannis Giannakopoulos, Alexander Grosz, and Themistoklis Melissourgos. On the smoothed complexity of combinatorial local search. CoRR, 0tts/2211.075444 2022.
Angeliki Giannou, Emmanouil- Vasileios Vlatakis- SaaaakiinGaarakkuniis, and Panayotis Mertikopoulos, On the rate of convergence of regularized learning in games: From bandits and uncertainty optimism and beyond. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
Andrew Gilpin, Javier Peña, and Tuomas Sandholm. First-order algorithm with (ln(1//e) conver- gence for e-equilibrium in two-person zero-sum games. Mathematical Programming, 133(1-2): 279-298, 2012.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS). 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman E. 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. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Michael D. Grigoriadis and Leonid G. Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2):53-58, 1995.
Nika Haghtalab, Michael I. Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. In Proceedings of the Anmual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Nika Haghtalab, Michael I. Jordan, and Eric Zhao. A unifying perspective on multi-calibration: Unleashing game dynamics for multi-objective learning. Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2023.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra- orrdietr methods. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
Sophie Huiberts, Yin Tat Lee, and Xinzhi Zhang. Upper and lower bounds on the smoothed complexity of the simplex method. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2023.
13

---

Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Chung- Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive- games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
Chris Junchi Li, Huizhuo Yuan, Gauthier Gidel, Quanquan Gu, and Michael I. Jordan. Nesterov meets optimism: Rate-optimal separable minimax optimization. In International Conference on Machine Learning (ICML), 2023.
Pouria Mahdavinia, Yuyang Deng, Haochuan Li, and Mehrdad Mahdavi. Tight analysis of extra- gradient and optimistic gradient methods for nonconvex minimax problems. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Arna Maiti, Kevin G. Jamieson, and Lillian J. Ratliff. Instance-dependent sample complexity bounds for zero-sum matrix games. In International Conference Artificial Intelligence and Statistics (AISTATS), 2023.
Konstantin Makarychev and Yury Makarychev. Perturbation Resilience, page 95-119. Cambridge University Press, 2021.
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), 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 E. Ozdaglar, and Sarath Pattathil. A unified analysis of extra- aitra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-511 2017.
Yurii Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103, 2005.
Courtney Paquette, Bart van Merriënboer, Elliot Paquette, and Fabian Pedregosa. Halting time is predictable for large models: A universality property and average-case analysis. Found. Comput. Math., 23(2):597-673, 2023.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eccles, Mark Rowland, Mare Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre. Nathalie Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623)9900999, 2022.
L.D. Popov. A modification to the Arrow-Huwiie method for search of saddle-points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):855-88)) 8888, 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019 2013.
James Renegar. Incorporating condition measures into the complexity theory of linear programming. SIAM Jourmal on Optimization, 5(3):506-524, 1995.
Jarnes Renegar Some perturbation theory for linear programming. Mathematical Programming, 65: 73-91, 1994.
14

---

Ralph Tyrell Rockafellar. Convex Analysis. Princeton university press, 2015.
I. Romanovskii. Reduction of a game with complete memory to matrix game. Soviet Mathematics, 3, 1962.
Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In Irit Dinur, editor, Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2016.
Damien Scieur and Fabian Pedregosa. Universal average-case optimality of polyak momentum. In International Conference on Machine Learning (ICML), 2020.
Zhuoqing Song, Jason Lee, and Zhuoran Yang. Can we find nash equilibria at a linear rate in markov games? In International Conference on Learning Representations (ICLR), 2023.
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algorithms. Math. Program.. 97(1-2):375 404, 2003.
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385-463, 2004.
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms practice. Commun. ACM, 52(10):76-84, 2009.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, 2015.
Xiaohang Tang, Le Cong Dinh, Stephen Marcus McAleer, and Yaodong Yang. Regret-minimizing double oracle for extensive-form games. In International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, 2023.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Society, 2023.
Terence Tao, Van Vu, and Manjunath Krishnapur. Random matrices: Universality of ESDs and the circular law. The Annals of Probahility, 38(5):2023 -065, 2010.
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1):237-252, 1995.
Eric van Damme. Stability and perfection of Nash equilibria, volume 339. Springer, 1991.
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song. and Di Wang. Minimum cost flows, mdps, and l fjregrression in nearly linear time for dense instances. In Proceedings of the Anmual Symposium on Theory of Computing (STOC), 2021.
Daniil Vankov, Angelia Nedić, and Lalitha Sankar. Last iterate convergence of popov method for non-monotone stochastic variational inequalities, 2023.
John von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295-320. 1928.
John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1947.
Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-246, 1996.
Bernhard von Stengel. Zero-sum games and linear programming duality. Mathematics of Operations Research, 2023.
Chen-Yo Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. International Conference on Learning Representations (ICLR), 2021.
15

---

Yinyu Ye. Interior point algorithms: theory and analysis. John Wiley & Sons, 2011.
Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning single- index models via alignment sharpness. In International Conference on Machine Learning (ICML), 2024.
Brian Hu Zhang and Tuomas Sandholm. Sparsified linear programming for zero-sum equilibrium finding. In International Conference on Machine Learning (ICML), 2020.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2007.
16

---

A Further related work
Besides the pioneering work of Spielman and Teng [2004], which revolved around the simplex algorithm, other prominent algorithms for solving linear programs have also been investigated through the lens of smoothed complexity. Blum and Dunagan [2002] showed that perceptron, a popular algorithm in machine learning, also enjoys polynomial smoothed complexity (with high probability) for solving linear programming feasibility problems, which can also capture general linear programs via binary search procedure. Further, Dunagan et al. [201 1] performed smoothed analysis of interior-point methods by relying on an earlier characterization due to Renegar [1995].
Beyond linear programming and (two- (two-player) zero-sum games, there has been a considerable interest in understanding the smoothed complexity of Nash equilibria in general-sum games, but the outlook that has emerged from this endeavor is rather bleak [Chen et al., 2009, Boodaghians et al., 2020, Rubinstein, 2016]. On a more positive note, Daskalakis et al. [2024] recently considered a more permissive solution concept they refer to as smooth Nash equilibrium; the basic idea of their relaxation is that instead of considering best-response deviations, they restrict to deviations that do not assign too much probability mass on any pure strategy, controlled by a certain parameter. For certain regime of that parameter, they obtained positive results, bypassing the intractability of the usual Nash equilibrium. Considering smooth Nash equilibria could also be fruitful in the context of zero-sum games. In particular, we surmise that, if one is content with convergence to smooth Nash equilibria, the error bound could exhibit more favorable properties. Smoothed analysis has also been applied to more structured classes of games, such as congestion or potential games [Giannakopoulos, 2023, Giannakopoulos et al., 2022, Chen et al., 2020]. as well as other important problems in game theory [Gatti et al., 2013, Buriol et al., 201 1]. Other notable developments in a broader context were covered in an older survey by Spielman and Teng [2009]; for more recent developments, we point to, for example, Christ and Yannakakis [2023], Chen et al. [2024], Huiberts et al. [2023], and the many references therein.
Average-case analysis has also been a popular topic in the optimization literature [Cunha et al., 2022, Paquette et al., 2023, Scieur and Pedregosa, 2020], and so it is worth relating our results to that line of work. In particular, let us focus on the recent work of Cunha et al. [2022]. First, that paper targets a certain class of convex quadratic problems, whereas we examine zero-sum games. They also operate under different perturbation model, deriving a parametrization based on the concentration of the eigenvalues of a certain matrix. Further, without strong convexity, Cunha et al. [2022] establish complexity scaling with poly(1/c), while here we target the log(1/c) regime. We finally remark that the techniques employed are also quite different. In particular, Cunha et al. [2022, Problem 2.1] posit that the optimal solution does not depend on the underlying randomization. In contrast, as we have already highlighted, the fact that the equilibrium is a function of the randomization constitutes the main technical crux in our setting. At the same time, Cunha et al. [2022] encountered several challenges not present in our setting, so overall those results are complementary.
Beyond smoothed complexity, understanding the last-iterate convergence of gradient- gradeent-based methods such as OGDA and EGDA has received tremendous interest in the literature; e.g., [Golowich et al., 2020a, Cai et al., 2022, Gorbunov et al., 2022, Vankov et al., 2023, Golowich et al., 2020b, Mahdavinia et al., 2022, Antonakopoulos et al., 2021, Mertikopoulos et al., 2019, Abe et al., 2023]. It worth noting that linear convergence has also been documented for the more challenging class of extensive- games [Lee et al., 2021], as well as Markov games [Song et al., 2023]. Nevertheless, there are lower bounds precluding linear convergence beyond affine variational inequalities [Golowich et al., 2020a, Wei et al., 2021]. We also refer to the works of Cohen et al. [2017] and Giannou et al. [2021] for further characterizations of the convergence rate of no-regret dynamics in multi-player games.
Contrary to the above line of work, which focuses on last-iterate convergence, the most common approach to solving zero-sum games revolves around regret minimization whereby optimality guar- antees concern the average strategies. Learning in such settings has been popular research topic as it captures many central problems; two notable recent applications are learning from multiple distributions [Haghtalab et al., 2022] and at least three limitations of the no-regret framework worth highlighting here. The first one, which has been stressed extensively already, that the number of iterations must grow at least as 1)1 when one insists on taking (uniform) averages [Daskalakis et al., 2015]. The second and more nuanced caveat that the no-regret framework does not provide instance-based guarantees based on natural same-theorcee parameters of the problem (see, for example, the discussion of Maiti
[Haghtalab et al., 2023]. Yet, there are
17

---

et al. [2023]). Building on earlier work [Wei et al., 2021, Tseng, 1995], some of our results here attempt to address this shortcoming by coming up with more interpretable parameterization of the iteration complexity of algorithms such as OCDA. The final limitation is that, convergence to the set of equílibria notwithstanding, no-regret guarantees provide no information regarding properties of the equilibrium reached. Although not an issue in non-degenerate zero-sum games, equilibrium selection still remains a central problem. Earlier results [Wei et al., 2021, Tseng, 1995] provide an interesting characterization for the last iterate of OGDA and EGDA by showing that the limit point is the projection of the initial point to the set of equilibria.
Finally, it is worth pointing out the best available theoretical guarantees for solving zero-sum games. Assuming that each entry of has absolute value bounded by 1, (1) can be solved in minnnn,mm/// m33/22 [van den Brand al., 2021]. Here, w the exponent of matrix multiplication and Ô suppresses polylogarithmic factors n and m. The complexity we obtain for algorithms such as OGDA is not competitive even though we work in the more benign smoothed complexity model; we reiterate that we did not attempt to optimize the polynomial factors in terms of n. and m, and those can almost certainly be improved. On the other hand, there are two main aspects in which algorithms such as OGDA are more appealing in terms of their scalability: the per-iteration complexity and the memory requirements. An algorithm such as OGDA requires a single matrix-vector product in each iteration, which can be implemented in linear time for sparse matrices, and has limited memory footprint. In contrast, implementing interior-point methods in large games can be prohibitive.
(mmax(n, m²)") [Cohen al., 2021] or Ö(nm min(n,
B Preliminaries
In this section, we introduce some further background on smoothed complexity and define the algorithms cited earlier (Items I to 4).
Further notation For a random variable X, we denote by E[X] its expectation and by V[X] its variance, under the assumption that both are finite. For sequence of random variables X Xa
and scalars 0r,, ,a E R. linearity of expectation yields that E[a; + +................... +axXa = 0: E[
a, [Xa] Assuming independence, it also holds that V/a,X, + + a. = (a,)"v[X,,
... + (aa) P [x]]. We will also use the fact that a linear combination of independent Gaussian random variables is also Gaussian. More broadly, linear combinations can be understood through convolution the space of probability density functions, which means that smoothness (in the sense of Lemma C.7) is preserved in certain regime.
B.1 Smoothed complexity
To fully specify Definition 1.1, we first recall that a (univariate) Gaussian random variable with zero mean and variance o² admits probability density function of the form
12
p::
exp
2T
20
The law of such a Gaussian random variable will be denoted by NNO,, In the original work of Spielman and Teng [2004], smoothed complexity was defined the expected running time (or some other cost function) of some algorithm over the perturbed input. More precisely, let A be an algorithm whose inputs can be expressed vectors in Rdd, and let (I) be the running time of algorithm A on input I Rd.. Then, the smoothed complexity of A is
Ca o) = max Bgg-N((...
(T + |[][])].
IER*
As pointed out by Spielman and Teng [2003], one does not need to limit smoothed analysis to measure the expected running time, and high probability guarantees are also quite natural; see, for example, the smoothed analysis of the perceptron algorithm due to Blum and Dunagan [2002]. Our main result also provides a guarantee with high probability: it not clear whether the expected running time can also be bounded by (nly(n, m, 1/0), which is left for future work.
B.2 Algorithms
Next, we specify the algorithms we consider in this work.
18

---

Optimistic gradient descent/ascent Originally proposed by Popov [1980], optimistic gradient descent/ascent (OGDA) and variants thereof [Hsieh al., 2019] has been recently revived in the online learning literature commencing from the pioneering works of Rakhlin and Sridharan [2013] and Chiang et al. [2012]. If we denote for compactness F(z) = (Ay,-A a:), OGDA can be expressed as follows for & E N(= (1,2.....))
}).
(+)) (1 (==-11( - == -1z -FF((())
(OGDA)
Here, 17 > is the learning rale; (1) denotes the (Euclidean) projection operator set 2 Xx); and 20) = 2(1) E 2 is the initialization. That is. players simultaneously update their strategies through optimistic gradient steps. Given that X and y are probability simplexes, each projection can be computed exactly in nearly linear time. The key reference point for OGDA in affine variational inequalities is the work of Wei et al. [2021] who established linear convergence using the notion of metric subregularity (Definition C.9), which is strongly related to Definition 1.3; we discuss their approach later in Appendix C.3.
Optimistic multiplicative weights update Deriving from the same class of online learning al- gorithms as OGDA, optimistic multiplicative weights (OMWU) is the incarnation of optimistic mirror descent with an entropic regularizer, namely
x1)) x x (1-1) exp (-2n + (t-)(
(OMWU)
(0)) x (1 o exp A (1-11) 7 (2(()-))
for E N Above, o denotes the component-wise product; the exponential mapping exp(-) is also to be applied -omponent-wise; and x-11) = (0) == 1n. i 1m). Daskalakis and Panageas [2019]
first proved that OMWU exhibits asymptotic (last-iterate) convergence, and Wei al. [2021] later established linear convergence.
Remark B.I. It is important to note here that the exponential map of OMWU can produce iterates with an arbitrarily large number of bits. Nevertheless, it hard to show that the analysis of Wei et al. [2021] carries over when the iterates are truncated up to a certain length of the most significant bits, and so we will not dwell further on this issue here.
Extra-gradien descent/ascent to OGDA, namely
The extra-gradient method of Korpelevich [1976] is quite similar
2(0) -=(2(())(((()) (1+1) = (z((00)) - - (F(((
(EGDA)
for t E N. Unlike DGDA, one caveat is that it requires two gradient evaluations per each iteration t. EGDA is also less suited to use in an online environment: it requires more feedback than what is provided in the online learning setting. and in fact, even legitimate variants of EGDA can still incur substantial regret [Golowich et al., 2020a]. Tseng [1995] first established that EGDA exhibits linear convergence for problems such as (1), discussed further in Appendix C.3.
Iterative smoothing This is a refinement of Nesterov's ' classical smoothing technique [Nesterov, 2005] due to Gilpin al. [2012]. Let us first recall the vanilla version of Nesterov, which we refer to Smoothing(( A, z 2(0),))
1. Initialize 1) Dz
and (0)) = z00), where Dz is the & diameter of Z.
2. For t = 0, 1,
(a) (t)
2 2(1
142 (1)
(b) 241
I
(++1) = arg min =E2
(VF,(u(()) -- () + ||2 (t)) 12
27
'OMWU is oftentimes expressed via the (optimistic) mirror descent viewpoint, but the form we provide here is easily seen to be equivalent.
19

---

where (z) == max - -2) - - - and L is a suitable matrix
norm.
(c) ((((+1) < return.
(d)
g((+1) arg min
Σ
r++ +1 2
I (VF,(u - -
|| 210112
ZEZ
2n
In this context, IterSmooth(A, A, (0), p,,)) simple refinement of Smoothing, which nonetheless attains linear convergence [Gilpin et al., 2012].
1. Let e = ())
2. For t = 0,1,...
(a) ((+11) (0
p
(b) ((+1) Smoothing(A) A, 20) ((+1)).. e((t))
(c) If 1(2(t+)) < c, return.
C Omitted proofs
We dedicate this section to the proof' omitted earlier from the main body,
C.1 Proofs from Section 3.2
We first point out that degenerates games have measure zero (ef. Spielman and Teng [2003, Proposition 5.1
Lemma C.1. For Gaussian distributed payoff matrix A per Definition 1.1, the game is degenerate (Definition 3.2) with probubility (almost surely).
Indeed, the set of games with a non unique equilibrium has measure zero [van Damme, 1991, Theorem 3.5. Regarding the characterization in terms of the number of tight inequalities of the corresponding (primal and dual) linear programs, gathered in Definition 3.2, note that if + 1 of the inequalities were tight at æ², that would induce a feasible linear system of n equalities (by eliminating v) in n variables (by eliminating one of the redundant variables); such degeneracies have measure zero, and there are only finitely many possible such degeneracies, leading to Lemma C.I. As a result, in the smoothed complexity model, we safely assume that the game is non-degenerate.
Now, as we alluded to earlier, establishing Definition 1.3 reduces to showing that for any points E X' and E V.
max x Ay') 2 x|| - xx (x)] x||æ x=1|, V
(8)
min (x' Ay) xlly 1yy (2)) = =kly - y²1l x'E
(9)
(Definition 1.3 then indeed follows from the obvious fact || æ=1| b1 yn || 2 Accordingly, our proof of Theorem 3.6 below will focus on lower bounding k. so that (8) holds, and (9) can then be treated similarly.
|| 2 ||)
Before we proceed, us make some observations regarding transformation (5) we saw earlier. First, one can understand the transformation A A T(Q², d) through the equations
d= Aijii by -Aiy + Aijic Cr = Ar + A.j; Qu = Ar A.y - Ar + A (10)
for all (i',j") E N. N. This can easily be derived from (5) by using the fact that Zp @2, and UN = (g. 1- From (10), we see that there is permutation of the rows T that is upper triangular, with every entry being either 1 or -1. This implies that (T) abuse of notation, we will write T., (as opposed to T(i)).) to access the (i.j) row of T, so that
x)
1. With slight
Ai.j TT.j, (Q', b, d)). From (10), we also see that Tı, contains at most 4 non-zero entries. In turn, this implies that ||Ta S 2 and || S 4. We gather the above observations in the claim below, which will be used in the sequel.
20

---

Claim C.2. For the (linear) transformation T E ((BBN)(BM)) given in (10), it holds that det(T)) Further; ||, S 2 and [T,ill S for all (i.j) B x N.
The point of transformation (5) is that, we claimed earlier, the spectral properties of matrix Q (as opposed to A.N, which a natural candidate) suffice to capture the difficulty of addressing the second subproblem identified in Section 3.2. In addition, there is straightforward but convenient characterization of the equilibrium (x", yy in terms of the transformed game (5), as stated below.
Claim C.3. It holds that Qÿ* and Q x= = b.
Proof. It is clear that the vector Qÿ must have the same value in every coordinate since "" fully supported and a best response (by assumption). If that entry was positive, then 3= would not be a best response since Player z could profit from removing all the probability mass (which is possible since Lieñ x > 0). If there was negative entry, Player z would profit from increasing its probability mass (which is possible since ΣiEB ag < 1). Similar reasoning yields Q T x= = b. D
Having made the above observations, we next prove some lemmas claimed earlier in Section 3.2 which will be used for the proof of Theorem 3.6. First, give the proof of Lemma 3.4.
Lemma 3.4. Let C QÚ' EjEN N Dj Q. and suppose that Q E BBB is such that its jth column is equal to Q.. Then,
N
min dist Q.. span N..N-3)) 1+ jeN
min dist QQ... span( (pan(Q..n -j)) JEN
Σ5eN yj
Proof. Let N 3 j arg JNN span span(Q., (Q.,N-g)) By definition, there is p E R-N-5' and
r E N with ||||| = such that
Q JEÑ-j'
Σ
Q (1--g))) 0 = Σ JEÑ-ド
p,(Q..s - tc..
where c = min jeN dist Q.,,, span( s.an. Q-,) Rearranging, we have
Qui' 1 y + yj
Σ Pj + Σ Qui -13 - Pj + V JEÑ
Σ Pj" = =r.
(11)
JEÑ-j'
J"EN
1-E Vj Now, let us suppose that all coefficients above are such that 1bb/1 S 1-E +I
for all
j E N. Then, ΣjeN Φ5 = =| since ΣSEN H54 S EjEN 10 S </.V,, where for convenience
we used the notation ΣjEÑ o, = =|Ele' - -lÑle' S EJEN O3 S |51e'. Thus, by definition
of Φj.
1 Σ 3
Σ 1p
ps = -1-- Σ 3 ps)
= =
JEN
JEÑ-J
JEN
Since 0 < 1- ΣjEň Vj. we have
<1-EseN
Σ Pj
=1
1 Σ
Eje y3
JEÑ-j"
Thus,
N
0j = U3 + 3
Σ
Pj p== 11 c
Σ xEN y
JEÑ-j'
21

---

I-EiEN since é' - 1-E V The last displayed inequality contradicts our earlier assumption that 10y1 <.' As result, we conclude that at least one coefficient Φj has an absolute value at least e'. Dividing (11) by that coefficient, we get
min dist Qu,. span SppanQQ.a0 QNNN- jEN
E S c
1+
IN|
min dist (ist span span NN,))
EJEÑ N Vj
jEN
This completes the proof.
We continue with the proof of Lemma 3.5.
Lemma 3.5. Let M E Raxd be full-rank matrix. For any t Rd there is p Rd with
|p|| S min [ such that
d I == Mp Σ P.M. j=1
Proof. Let M UEVT be singular value decomposition (SVD) of Q, where U and V orthonormal. Then, given that Q is invertible (by assumption),
VΣ VU-UU T
where E di mix)). (Here, max and minn are the maximum and minimum singular values of M, respectively.) Thus, |ppl < | | fact that the spectral norm of any orthonormal matrix is and the spectral norm of any diagonal matrix its maximum entry in asbolute value.
||||||||||||| S (Q) | where we used the
We next state the negative second moment identity that connects the smallest singular values in terms of certain geometrie property of the matrix (namely, Item 3) (see also [Tao, 2023] for further background).
Proposition C.4 (Negative second moment identity [Tao al., 2010). Let M E Rdxd be invertible matrix. Then,
d
Σ (M)
(12)
dist (M, H r.))
dist (M. H
r=1
where H_ == span M, -, 1.31 M M..).
One can readily prove this identity by equivalently expressing the negative second moment ((MM)))M--)) either Σ (M-1) Σ o, (M) Σ |M leading to the first identity in (12). The second one follows from the fact that the singular values of T coincide with the singular values of M.
We now ready prove Theorem 3.6, restated below.
Theorem 3.6. Let A be a non-degenerate payoff matrix, and suppose that (ap(A), a (Ap(A), (A)) and (xp(A),nD((
are as in Desinition 3.3. Then, the error bound (Defini-
tion 1.3) is satisfied for any sufficiently small modulus
1
min ((aD(A)) (AP())
A* | min(n, m)3
Proof. We lower bound 6 so that (8) holds; bound (9) will then be treated in a symmetric fashion, and Definition 1.3 will follow.
Let us fix any point æ E X. We can write x as AT + (1 A)@ g for some E [o, 1] such that TB E A' and all coordinates of 7 in are zero, and G E X' and all coordinates of क in are zero. For notational convenience, we define
P(A) = 2 0 mmin
Q I+ ap(A)
(13)
We consider the following two cases.
22

---

Case I:
1f xzg. it follows that x x* (since À = 1), AP(A)]|eB - 2 4 411
and the conclusion trivially follows. We can thus assume that RB + z/B. In this case, follows that B o 0, and we proceed as follows.
max ( Ay) - - 2 À mmxx r'EY
TB ABJ) + (1 A) (1E A AB,) -0)
(14)
JEN
À Amxx ( FB A AB.) 2(1 - A)||A'lloo
(15)
JEN
where (14) follows from the definition == Xã B + (1 A} h and the fact that (0' ABJ) for all j E N; and (15) uses definition of ||A'||
[| to lower bound the second term in (14). Continuing
from (15), we can use the transformation defined (5) to get
max xBB. AB) = max Ø x Q c)2 JEN
(16)
JEN
where, with an abuse of notation, the convention above is that Q., 0 jf N. For convenience, let us define Xj == (a. x Q., e) for all j E N. Our goal is to lower bound maxjeN Xj- To that end, first observe that, by the fact that Qy (Claim C.3),
t x² Qú
Σ リイ
x Q (w ..
JEN
Σ
3í ( x¹, Q.. c) 1 11-E
Dj
( x. -c)
JEN
JEN
In other words,
Σ yラン;
JEN
which in turn implies that
Σ JEN
max(0, Σ yj max(0, =- Σ yj min(0,
JEN
JEN
2 -ap (A)
min m0),),,)),
(17)
JEN
where made use of the obvious identity t max(0, t) + min(0, for all t e R, as well as the definition of (A) (Item 1). We let E R N be the (unique) solution to the linear system
Qp Σ (Q., c)ps,
JeÑ
and p, = 0 for j E N \.. By Lemma 3.5, we know that ||p|| S (amin (Q)) a+1l Then we have
Σ
XIP Σ
X,p; Exp,
5- v. E c)p,
| 1111
(18)
JEN
JEN
JEN
Moreover,
Σ XiPj
Σ Pj m0 Xi) + Σ
Pj min(O, Xi)
JEN
JEN
JEN
< Σ max(0. p,) max(0, X²)
(0, p,) min X²)
(19)
JEN
JEN
< ||p||
max(0, X;) - -lpp1 Σ
min(0,
(20)
JEN
JEN
||||10
1+ aD(A)
max(0. (0, X²)
(21)
JEN
1+ aD(A)
IN
max Xa =
(22)
mmin(1) (Q)
JEN
23

---

where (19) follows from the fact that p; max(0, X²) I max(0. Pj) max(0, Xj) (by nonnegativity of
max(0, X2)) and pj min(0. X2) I min P;) min(0, (0, Xj) (by nonpositivity of min(0. X, )) (20) uses
that min Pj) 2- |pl 2 - -pll,o. which gives min(0, P;) min(O, Xi) I - -I|plioc min(O, X;);
(21) follows from (17); and (22) uses the bound ||D|| I (amin (Q)) || ==1l (Lemma 3.5).
Combining (18) and (22),
1 N
(I+ aD(A)
max DB D. AB.) JEN
2
min Q
a x
(23)
2| min (Q) (1+
1
| x |l,
(24)
(nD(
where (23) uses the definition of Xy and the assumption that ā + xx (equivalently, zi * TB). and (24) follows from the bound
[B FHlll S
|BB TBl11 S
Σ <EB
x
Σ(x;
(z.
x²)
2 2- B 11
iEB
Returning (15), we have
1
1
-1
max xx, Ag') v 2 A ''E)
2 B min Q
1+ aD (A)
[ -B:ll 2((1 AA)ll''
(P 2B2 -2(1 \)[| ">]lA'lloo oloo:
(25)
where the equality above follows from the definition of P(A) in (13). Next, we bound
|| x 2²1
|| = + (1 1)
l|
|| 233) -
21 (1 1) 1
< 21211
2 (11 1>
(26)
- 2x - w/y 3 - ,)²
(27)
where (26) uses triangle incquality with respect to || || along with the incquality (t1 + t2)
2t + 262, and (27) uses that | |I @ S 1. Since we are assuming that (P [B - JB
4(1 )) A |ox. (27) in turn implies that
P(A)
|| xx 112
2X
1
+
X2
[ ==/
|
P(A)
x2
2+
| 1311²
(28)
||
Combining (25) and (28) with the assumption that XP(A)] 2311 4(1 - 1l
m Ayy) v P(A)](BB 2
y'Ey
2 P(A) 2+ ( ||A
P(A)
))
2)
1--x"" x01| 2 x(A)]l= x=1|- |
2
It is easy to see that P(A)/|IA') is upper bounded by an absolute constant, and so we have
1
B min Q (1+ aD(A)
max Av - P(A)|E=
x=1
| - x=11
vey
2|N
1
(aD(A))?p(A))(I> = x-1l.
(aD(A))
B
Above, the last bound uses the fact that
1
min dist(QQ.., span
span Q ( Ny))
Puin
B
JEN
min dist Q.,j span( (- [B|3/2 7p( (A)on(A) jEÑ
BB//22
where the first inequality uses (6), while the second one is consequence of Lemma 3.4.
24

---

Case II: AP(A)] - r'lll < 4(1 - All.. This case can only arise when B * 0 (for
otherwise X 1). Then, we bound
max (2r, Ay') (x, Ay") v
y'EY
2 A( - TB. A A.NUN)) + -)((@))))))))))))))) B. A A.N -b))
2 (1 (A),
(29)
by definition of (A) (Item 2) and the fact that (āg FB, A B.,NDN) = c(0B 23 1) = 0.
Moreover, by (27) together with the assumption that AP(A) (|) FiBll <4 - >)]lA* oo.
x - x01' 11. 32
[10))120] P(A) )
(1- 1)2 + 4) ^)
32
||A2||00
)
2
+3 +3 (1 - 1)2.
P(A)
Combining with (29) yields
||A'
2
-2
max( x Ay') - 2 r'cy
32
+3
BD(A)] x=1l
P(A)
P(A)
3D (p(AA]la - x''l
A A I1
1
1
| B (O0(A)))(()))((()) x"11.
C.2 Proofs from Section 3.3
We continue with the proofs from Section 3.3. As we have noted already, given that all quantities of interest in Definition 3.3 depend on the support of the equilibrium, it is natural proceed by partitioning the probability space over all possible such configurations. To do so, we will use the following simple fact [Spielman and Teng, 2003, Proposition 8.
Proposition C.5 (Spielman and Teng, 2003). Let X and Y be random variables distributed accordi to an integrable density function. For any event E(X,Y) Y),
111 max P () = y] =: max P ()(EXXX y
In our application, we want to condition on the event that B is the support of x and N is the support of y² For convenience, we let Type (A) denote the indicator random variable representing whether B and N indeed index the positive coordinates of the equilibrium; that is, Type (A) = 1 {i E [n]] : x (A) 0} A N (j [m] (A) > 0}}. Unlike general linear programs, which can be infeasible or unbounded, the linear program induced by a zero-sum game is guaranteed to be primal and dual feasible, matter the perturbation (under Definition 1.1). We will thus only have to condition on events in which B and N are both nonempty. To be able to control the probability density function upon conditioning on Type (Ap) it will be convenient to perform certain change of variables, which is descrihed next.
Change of variables Let us denote by A B,N the entries of A excluding those in AB,N. We first perform a change of variables from A B,N, AB,N to A B,N Q c, b, d, which uses the linear transformation T associated with (5). With this new set of variables at hand, we can conveniently express Qğ c and Q x = b (Claim C.3). Accordingly, we next perform a change of variables from A R.N. Q, b, d to A p Q. x=' y", When performing those change of variables one has to account for the transformed probability density function. This can be understood as follows. The probability of an event EAA) can be expressed as
/ E(A))A(A)dA.
The integral above can be cast in terms of new set of variables B by computing the corresponding Jacobian, assuming that is non-singular. We will make use this fact in the sequel. The following lemma gathers some of the above observations regarding the change of variables.
25

---

Lemma C.6 (Change of variables). Let ((A) be any event that depends on the randommess of A. Then,
P[E(A)) S max (A) B,N A
Type (A)l
A
max
P
((A)) A 2 and A N. S v1].
B,N
A A Mar.-aaaaap 3/100
Indeed, the first inequality above a consequence of Proposition C.5. The equality then follows from noting that, when
C - Qú
Q "0, -= (i" Qy") AB,NY" = vl, A W. - =v,,
the event By (A) can be equivalently expressed A B 2 v1 and AT N,B
2 vl.
We first bound the probability that (A( == min, jE ( (z'g. A B.J)) is close to O; the proof for 3D (A) is then symmetric. The key ingredient is the following anti-concentration lemma pertaining conditional Gaussian distribution [Spielman and Teng, 2003, Lemma 8.3].
Lemma C.7 (Spielman and Teng, 2003). Let be a Gaussian random variable of variance a² and mean of absolute value at most 1. For 2 0, T 2 1 and t ST. T,
ET <ir+3) g2
Stysttelg 2
Proposition 3.8. Let (p(A) ) be defined as Item 2. For any 2 0,
e S
emin (n, m)² o²
P 3p(A) S 1
Proof. By Lemma C.6, it suffices to bound
max B,N A Q. [Bp(A)= S é' AB,NUN 2 v1 and A N S v1].
P
By Proposition C.5, it suffices to prove that for all B, N, A B.N. A B.N. Q, y", satisfying A UN 2 vl,
P
ABJ)
(0g, AB.) 20
(30)
Ag,
P
10
B
BJ) scl N (x AB.)) 2 0
(31)
An
jEN
P
(x
ABJ) <6' 10 (x ABS) 20
(32)
ABa
JEN
Σ
Plg, E
(33)
JEN
where in (30) the distribution of A B.N after conditioning A B.N. Q, x², y", v remains the same, which is a consequence of independence per Definition 1.1; (31) is an application of the union bound; (32) uses the fact that the events {v (atg. AB,) Z O]EEN are pairwise indepen- dent; and (33) defines gj = - (x) ABJ). which is a Gaussian random variable with expectation [E[g,]] & max |At and variance V(g;]] = Eie ( dependence). In particular, by Cauchy-Schward Vig,l N max(1, /e///[/,)) have
= o² Eien (x;) (by in- 1 02 Further, by Lemma C.7 (for B
max c/. E 19
max(41Elo, (1:E (MD) [g.
P Pig; < é' - -o]
[g
min(n, (n, m) max ((). E(g,11)
min(mmm.
26

---

for any e' 2 0 and j N, where we note that we applied Lemma C.7 for gj/ [ || (since the absolute value of the mean has to be at most 1), which has variance Vlg, /lg,1/(0 / g,) ) So, setting c((l]] + 1
9, - |o| maxie Aisl v 9j 2 gj
P
S P 95
9
S 00 +
91 2 -
|
min(n, m)
(34)
Now, when min(n.m) > the proposition is vacuously true, while in the contrary case the claim follows from (34) and (33).
Next, proceed with the bound (A) The key ingredient is the observation that random variable with a slowly changing density function cannot be too concentrated on any any interval (Lemma 3.7 due to Spielman and Teng [2003, Lemma 8.2]; restate it below for convenience). Gaus- sian random variables have this property, as pointed out by Spielman and Teng [2003, Lemma 8.1J.
Lemma C.8 (Spielman and Teng, 2003). Let μ be the probability density function of a Gaussian random variable in R of variance o² centered at point of norm at most 1. If dist(r, r') I e then
u(r')
2 E -(1
(u(r
Lemma 3.7 (Spielman and Teng, 2003). Let p be the probability density function of random variable X. If there exist 8 >> 0 and e (0, 1] such that
p(l') p(t)
0SiSiS66
2 c,
(7)
then
P[X S X X 0
c5
Proposition 3.9. Let YPA) be defined as in Item 3. For any 2 0.
4e min(nn m)3
7p(A) < A
P
1mxx |Q A0 11 +3 Sc
σ²
Proof. Let uA (A) be the probability density function of A, which, by independence (Definition 1.1), can be expressed as [Lejm],jejm] PA.,, where HA.,, is Gaussian random variable. We first perform a change of variables from A.N, AB,N to A Q b, c, d, in accordance with (5); this can be understood through the (non-singular; Claim C.2) linear transformation A T(Q', b, c, d). To express the density in the new variables, we first note that the Jacobian of the change of variables (T) = 1 (Claim C.2), and so the density on Q b, c, d can be expressed as MAB.N (T(Q", b, c, d)) (AAAA,,AAAE
Next, perform a change of variables from B. Q b, c, to A B,N: Q y", according to the transformations Qý* = Q Ø = b; and v = d- (w) Qύ*). It easy to see that the Jacobian of the change of variables
0(A B.N Q b, c.
B.N. Q x², y (
det (a(b)bbbaa) c.d)
a(.
)
det
det (
So, the density on A.N: Q T ÿ reads
PAB.N (T(Q', Q Qū + (6" Q.'))) (A (A (A d
By Lemma C.6, it suffices to upper bound
max B.N
IP Ag R ,
(ir A)
S A A,NUV 2 el and A NB S v1].
27

---

Further, by Proposition C.5, it is in turn enough to bound (A))x(A) I for all B, N (for the non-trivial case where B, N 0), A B,N. T., y", such that A N v1 and A AT N, BB S vl,
where the induced distribution on Q is
MA (T(Q', Q x Qÿ o We will prove that for any N and N-
det (Q)
4e minin,,
P Qu
dist(Q span (,,) Q 4/0l + 4 N, +3
I r²
(35)
,0,00
and then apply a union bound over j N. Having fixed Q N, we can express Q., as q + iq
where IR B 3 qll E span N., and R 3 qt is the unit vector orthogonal to span Q --))) Then, [4| = dist(Q..j. span Q N-y)) and det = (C(Q.,N-)) where C(Q N-y) does not depend on Qu (this can be obtained by expressing the determinant using the formula for parallelepipeds). By symmetry, we can prove (35) by bounding the probability that t at most e given that
least
0. We can thus focus proving
4e mininn, (4|gg ol 4|01 4|| N- 1la + +3)
max all Elsppa Q
Plt S E e S Se
(36)
o²
and then (35) follows from the fact that ||Q.,]| || Now, the induced distribution on is proportional to
p(t) = II PA., ((T))),)()))
(x
for rt defined as
(q tgttt.. Q
N-
( q
Q. NNNN + tqt),
j
. (5 qll +tq+)).
v
We now want to apply Lemma 3.7. To that end, have
((s(t) (t))) ||T,, (1), (tr(t')]
S <4(t 1)) (# (ot.gg))) - ("" 1))
(37)
16( 1')
(38)
where (37) follows from |TT, < 2 (Claim C.2), and (38) follows from the fact that llq 1|, 15 || $ Morcover, again by Claim C.2,
(Ti (() ||T [ <4(1g_ + |o| + ||Q NNN -yll + ().
o² Let 0 0 5 1 for 5 (4]|g [+4|]|+4] ; |
Lemma C.8 then implies that
PA.., (Ta 2 1Zl|N..
PA., (TTij (t))
Thus,
p(t')
PA ( Ti (t')))
(KJ)EBx HAs, ((Tiy Th. (t)) 2 -e
II
p(t)
We conclude that (36) can be obtained from Lemma 3.7, and the theorem follows.
Finally, we bound the probability that ap(AA (Item 1) close to 0: a can be bounded in similar fashion.
28

---

Proposition 3.10. Let (p((A) be defined as in Item 1. For any 2 0.
me mimmm,nnn))))) m)
P ap(A) S 15 + 1)2 Sc
Proof. By Lemma C.6, suffices to bound
max
P B.N A Qu "y,0
(a)(A) Se A,NUN 2 and A I
N. N.B*B S v1l,
where we recall that the induced probability density function on A B,N Q x., y² v reads
MAn,N (T(Q',Q x. Qy" u=" Qy" A (A (A (A B det (Q)²
We consider the non-trivial case where B, * 0. We will perform a further change of variables. Namely, let a A, for i B B. We map A B,N to A B.N
A
A - la T a, so that
A T B now proportional
B I v1 can be equivalently expressed as AN.a cl The induced density function
PAB,N (T(Q', Q x. Qy" U (x" Q7 (a))))a) (A + 1a )r(+),
where v(.) does not depend on ãt and a. By Proposition C.5, it is enough to show that for any B, N, A N.N. A B.N. A B.N. Q y", satisfying A B.NY' 2 vl,
ap a*.
A N. B
s1 a
max
( 1)2, AA B. (51AA) Blo + lu/+ 4))
8e mn min(n, r²
where the induced distribution on Øt* and a is proportional to
AA (T(Q', Q क", Qū
(Ø Qÿ" (M)a))a (A B.N + la
(39)
We see that ~* independent of a and {a, {a)} JeN are pairwise independent. Thus, conditioning on the event A N. N. <vl the induced distribution on Ø* is proportional to
PA ( F(Q's Øt Qy
1 Qū ()) II
(A 5*) S a,}.
JEN
We can proceed by showing that for any fixed E and T B-1'
A AN. Su a
max((I + 1)2, A BN
A5
B.N 1loo + +10| 4))
86 Se"mminnnn,
d²
and then applying the union bound over all E B. Having fixed 3 the induced density on 2 say p(t), proportional pI(t): Pz(t), where
(t) == PAA,, (T(Q',
`") + ((Q.... T")) -. + QQ., Qū', u ( QB
and
(2( II Pa B AA,
A u 1 a,l.
JEN
We will first apply Lemma 3.7 to bound p1 (tt))/p1(t) for 0 < < < < and a sufficiently small 5. We define
(t) = (Q', Q A- B- +
+1Q Q7 +
Q "") + t QQ V")),
29

---

so that (t( Il B PA.,, (TTg,, Tz.j (t,)(t)).. Then, we have
(Tey ((y(t) Ti, - 4 + Q'Il
where we used Claim C.2, Further,
- (t + Q) b0
and Lemma C.8 implies that for 8 S "/
PA., ( (T Ti. (t)))
+f Iew و وااا ااا+
2
PA.y ((Taj) i.j. Pig (t)))
As result, for d
x² 8|8 | o1 Tz Q1| [0=++++++]]]] +1))
pt(t') (1(()
(A ((T (i.s(()))
II
PA (TTy (()(1)) 2 _e_
(x,))
Next, we focus on lower bounding p2 p2(()/p22)) From (39), it is not hard to see that aj is Gaussian random variable with expectation [B|a]]| S + ||A B.N lllo and variance V[a,] 2 min(n.m)
d²
Also,
P2(t')
II
P.
1.j
,t' v a,l
Pt(
P. a,
A B i.j B
tt u a,l
JEN
II P.
B-ij'
B
B
Aigl' Su aj (A B-ig B_1) Aist S -aj]
JEN
By Lemma C.7 (for (2) A B
+ |o| 1)/(1 + A ))
B.N
Pa, AA
A 1 ve
AA B-i 3 A.tt Su
> 1 min(n, m) B A B / 8 + |0| + 1)
min(n.m)) R.. ( R. 14)
Thus, for 8 5- 20m min(n.m)]] A ~l (5) 111
Pay [(A B-ir' 2
F + Aigl' 50- aj (A B 36
A Ai - 21 2m
which in turn implies that
P2(t')
)
1 -e_
(2(1)
2m
We conclude that p(l') of 8.
- and the proof follows from Lemma 3.7 by lower bounding the value
(())
Armed with Propositions 3.8 to 3.10, Theorem 1.4 can be obtained from Theorem 3.6, in conjunction with a union bound and the fact that ||A*||> S poly(n, m) with high probability (by Gaussian concentration).
C.3 Proof of Theorem 1.2
Having established Theorem 1.4, here we explain how existing results imply Theorem 1.2. We first focus on OGDA. We also take the opportunity to explain in more detail how Wei et al. [2021] established Definition 1.3, which was sketched earlier in Section 3.1. Our treatment of the rest of the algorithms will be more brief.
30

---

Metric subregularity A central ingredient in the approach of Wei et al. [2021] is what they refer to as saddle-poing metric subregularity, stated below as Definition C.9. For the sake of generality, we give the definition for general objective function f X 3 9 (ar, y) f(x. y), assumed to be continuously differentiable; (1) corresponds to the bilinear case fxz y) (x. Ay). We use again the notation Fzz) == (V (ar, y), - -V, f y)), where IR= 9 == (z. y). We also let L E R be
a Lipschitz continuity parameter for F with respect to || |l. so that [[)()) - F(''Ill = L|| z'I; in the context of (1), one can always take L == |||]]
Definition C.9 (Metric subregularity for saddle-poin problems [Wei et al., 2021]). A saddle-point problem satisfies metric subregularity if there exists problem -eppedeed parameter n' E Ryo such
that for any z E Z and zt == 11 (z),
(F(z), z²) kl|1=
sup #'EZ
==1
(40)
2 z'11
The nomenclature of Definition C.9 can be justified by the fact that (40) is equivalent a common type of metric subregularity [Wei et al., 2021, Appendix F]; for more background, we refer to Dontchey and Rockafellar [2009]. We further remark that Wei et al. [2021] introduced (40) in more general form by allowing an exponent 3 E Rz0 in the right-hand side, but that additional flexibility is not relevant for our purposes.
Now, there an obvious connection between Definition 1.3 and Definition C.9 in bilinear problems with bounded domain; namely, we have
(F(z), 2 z²)
1 (2),
sup z'ez
2 2'11
2
where we used the fact that (F(=), =) = 0 and > 21|| < Dz 2. So, Definition 1.3 with respect
to parameter implies Definition C.9 with parameter K" == k/2.
Linear convergence of OGDA Under metric subregularity. in the sense of Definition C.9, Wei et al. [2021] were able to establish that OGDA converges to the set Z* at a linear rate:
Theorem C.10 (Wei et al., 2021), Consider a saddle-point problem (1) satisfying metric subregularity with respect to some k' E RR For any S 1 the iterates 8L'
of OGDA satisfy
dist(= (9, ,0,2" 1²) S (1+
(1e)()))))
-1/2
dist(3(),
(41)
81
As result, Theorem C010 implies that OGDA guarantees dist(2 2*) S f so long as
log (822
t 2 2
(42)
log + 324||A77
(x')²
In conjunction with Theorem 3.6 and Propositions 3.8 to 3.10, this immediately implics that OGDA has polynomial smoothed complexity with high probability, as claimed earlier in Theorem 1.2.
Before we proceed, is instructive to explain how Wei [2021] treated the error bound in bilinear problems where X' and y are polyhedral sets. As we explained earlier, it is enough to show that for any x E X' and y E V,
max x yEy Ay - v 2 x|| 11x- (x)]
V min x z
Ay 2 k| y
Hy (y))l-
We focus on the first inequality, which is with respect to Player x. We let X' = e S b, Vi E [Lz]], where la denotes the number of vertices of X. We also let o, Ayy, where y denotes the jth vertex of ); for simplicity, we will denote by k, E N the number of vertices of y We consider a fixed x X \ X and x² xx (x:)
Wei et al. [2021] impose (40) only for points Z Z", which is easily to be equivalent.
31

---

It is easy to see that the set of optimal strategies for Player z, X= = fx E d' maxyey Ay) S u.) can be expressed as
X = E R. c.. - b, o v(iJ) E [ee] [by]]
Indeed, any point y E V convex combination of the vertices of V/ and the converse direction is
also obvious. A feasibility constraint E [cx] is said to be tight if c x² = b;; similarly, an optimality constraint j E [ky] is tight if oJ x² v. We let - (x=) C [ez] be the set of tight feasibility constraints and Ky k²(x') C [ky] be the set of tight optimality constraints. We can assume without any loss that La, Kg o O. It is well-known (e.g., [Rockafellar, 2015]) that the normal cone of X at xt with respect to X can be expressed as
No.
En pictt + Σg gjo, V(p.q) E R/ R ieTi
jek,
Wei et al. [2021] also define Ma
C Naw as
N fccT Vi E Lz)
Now, the main parameter of interest that relates to Definition 1.3 in the analysis of Wei et al. [2021] stems from the following quantity.
Definition C.11. We let C E R>0 be defined as the infimum over (0, oo) so that
Ep.c: P.c.+ +
E00000pp.0 ph. S SC 2 Ma. n Boo
(43)
TE
JER,
where 8, C Rn is the set points with &oo norm upper bounded by
By definition of MM' it is evident that there always exists finite problem-dependent parameter C' E Ryo such that Definition C.I1 is satisfied. It is then not hard to show that
max x T Ay-yy- - 2 K yEy
- [xx(x"))
Assuming that the number of vertices is polynomial in the dimensions. this shows that Definition C.11 essentially captures the complexity satisfying Definition 1.3. As we explained earlier in Section 3.1, the constraint matrix of the linear program induced by Definition C.11 depends both on the payoff matrix A as well as the set of constraints. is thus unclear how to use existing results the model of smoothed complexity [Dunagan et al., 2011] 1] to bound C. The second and more important challenge revolves around the fact that Definition C. depends solely on the tight constraints the optimal solution, which in turn depends the randomness of A. Under our characterization, the latter challenge was addressed earlier in Section 3.3.
Continuing for OMWU, we again rely on the analysis of Wei et al. [2021], which relates the rate of convergence of OMWU to three quantities. The first one [Wei et al., 2021, Definition 3] is similar to Definition C.9, but with the difference that the maximization is now constrained to be over points whose support is subset of the support of the equilibrium; namely.
x==x"AAy)
K2g
min max =EX'(="> BEV* ()))
(44)
x
where V*())= = ty E AT supp(y) C supp(y")) A symmetric definition is to be considered with respect to Player y. To connect this to (8), we note that, when y E ())),, (a", Ay) = v. We thus left to lower bound max, (x. Ay) v in terms of || x= 1/2, but under the constraint that E (2). An inspection of our proof of Theorem 3.6 (and in particular the proof of (8)) reveals that its conclusion holds even when the maximization is subject to the above constraint, and
analysis
"In fact, by virtue of Carathéodory's theorem, one can refine Definition C.11 that this holds even when the number vertices is exponential in the dimensions. Namely, point e Mar n B.x can written as the conical combination of at most n of the vectors describing the cone in (43), thereby maintaining feasibility. This observation can be used to refine the (worst-cas case) analysis of Wei et al. [2021] to, for example, extensive-form games wherein the number of vertices is typically exponential in the dimensions.
32

---

immediately lower bounds (44) as well. The second quantity introduced by Wei et al. [2021, Definition 2] corresponds exactly Item 2, which was bounded in Proposition 3.8. The third quantity [Wei et al., 2021, Definition 4] is where the exponential overhead is introduced. Namely, the iteration complexity of OMWU in their analysis depends on exp (min(ar A), ()(())))) where we recall the definition in Item 1. Unfortunately, for any game, it holds that (A( & 1/n and aD(A) I 1/m, and so even if the geometry of the problem is favorable, the obtained bound is exponential. (The reason the above quantity crucial in their analysis is because it lower bounds the probability of playing any action through the trajectory of OMWU.) Nevertheless, using Proposition 3. 3.10, our analysis provides instead a bound of exp(poly(n, m, 1/a)) with high probability, which is still a major improvement the worst-case bound of Wei al. [2021], which be doubly exponential in the number of bits L describing the came-one can easily make sure that a (A) R 1/2 (Proposition 3.1).
Next, for EGDA, Tseng [1995] established linear convergence under the error bound
dist(2, =²) S +|| ITz(= r)((2))]
for some > 0 and suitable > 0 [Tseng, 1995, Corollary 3.3]. It is easy to make the following connection.
Lemma C.12. holds that ((2) z ||| 11 nf(())]]
Proof. Indeed, by the first-order optimality condition for the optimization problem associated with
z' = llz (=)))) = arg min 2'62
{||=' (z=nfF(=)][ = h(z')}
we get (2 z', vh(z') for any 2 E Z, equivalently, minge -3- z', n)((2) o.
Observing that mingez F())) = (z) and bounding
(2
2 - z z' z/|l| 2 2'11 ズ - D2ll - 2'1l -212 -I1 - nf(()))]
leads to the claim.
can thus be shown that Definition 1.3 again sufficient to dictate the rate of convergence of EGDA.
Finally, for IterSmooth, Gilpin et al. [2012] introduced a "condition measure" of the payoff matrix A, which in fact corresponds precisely Definition 1.3. Thus, Theorem 1.2 with respect to IterSmooth follows readily from [Gilpin et al., 2012, Theorem 2].
C.4 Proof of Theorem 4.2
Finally, we conclude with the proof Theorem 4.2, which restated below.
Theorem 4.2. Any d-support-stale stable game (per Definition 4.1) satisfies the ervor bound for any sufficiently small modulus
e 2 poly (_
Proof of Theorem 4.2. We treat each parameter separately.
Let start from 3p(A) (Item 2). We let j' arg min (#), Ang)), where assume that N * 0. We consider a perturbed matrix A' such that
[Ais Br(A) if B,j= otherwise.
A/
A
*More specifically, the proof Wei et al. [2021, Theorem 3] upper bounds the Kullback-Leibler divergence (L(=("),z") exp (min(ar(A), (A), ap(()) Thus, guarantee KL(z(1), x²) < using the analysis of Wei et al.
quantity that is at least large (1+ 1 where C2 s
[2021] one needs at least log(1/e)/log (1 15,2Ca iterations. When C2 & 1. this grows with 1/C₂ 2 exp (min(ar(( (ain(ar(A),auu aD)))
33

---

Then, the game described by A' cannot be non- non-degenerate with the same support as A. Indeed, in the contrary case would follow that the (unique) equilibrium (T yiy) remains the same since A B.N = A B.N. But then, v ( A B.J") セー (mrg. A B.J' ( = 0, by definition of j' and (A)), which is a contradiction. Further, | All Bp()). In turn, this implies that å v (p()). Similar reasoning yields that (A()).
Continuing for Yip (A) (Item 3). assume that B, + V. We let UEVT be singular value decomposition (SVD) of Q. Then, a perturbation to Q of the form Udiag(0, 0.... mmin (Q)) leads a singular matrix Q'. which cannot be the if the perturbed game is non-degenerate with the same support. This perturbation can be cast in terms of B/ through transformation II in (5). This lower bounds o min Q) in terms of 6, and Proposition C.4 can in turn lower bound (r(() in terms of minn (Q).
Finally, we treat (A(A) (Item 1). The non-trivial case is again when B, + 0. Let i' E arg min If B, we define
ifi=',
R i 3
..
a
otherwise.
We know that Q perturbed game was non-degenerate with the same support, it would follow that (x', .) is the unique equilibrium, which is contradiction since Ep 0. Further, the norm of the perturbation |66 b'll is upper bounded in terms of a pP)) which can be again expressed in terms of A,N through transformation (5). Similarly, if i' of B, we define
-- TT We then consider the perturbed vector b' Q Ø'. If the
B
x
(P(())
B
and we consider the perturbed vector 6' =Q V'. If the perturbed game was non-degenerate with the same support, it would follow that (ø', is the unique equilibrium, which is a con- tradiction since Eien z Σie + a = The norm of the perturbation is again upper bounded in terms of (A).. Overall, we have shown that ó < ap(A) (ooyy (n, m). Similar reasoning applies with respect to aD(A), (A). This completes the proof.
34

---

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: All claims made in the abstract and introduction are proven in Appendices C.I to C.4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be 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 to 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]
Justification:
All limitations and assumptions are stated in Section 1.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
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-specification, asymptotic approximations only holding locally). The authors should reflect 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 few datasets or with 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
35

---

Justification:
The full set of assumptions and proofs are given in Appendices C.I C.1 to C.4.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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 of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
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 a 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 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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 architccture 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 reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
36

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
Sadiidde/CodSuumiise wwwssssssllllooooooooooooooooooo icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //iips.co.. wttpccccpppccceeeeecec.eccccccct cuubiicgguides httpa///ggiieee/eeeuuuubiiiiiiii
/CodeSubmieeeeee wwwissssiiniioiiieeeeee oniooicy))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If 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 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?
Answer: [NA]
Justification: [NA]
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: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support 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 a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
37

---

It is OK to report 1-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 enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpeerrppp..cppppp.cc/ctiiiaaaa
Answer: [Yes]
Justification: The contribution of the paper is theoretical, and conforms in every respect with the NeurlPS Code of Ethics.
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., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: The contribution of the paper is theoretical, and we do not foresee any societal impact.
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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
38

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
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 usage guidelines or restrictions to access the model or implementing safety filters.
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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does 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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of 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.
39

---

If this information is not available online, the authors are encouraged to reach out to 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: [NA]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as 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 to anonymize your assets (if applicable). You can 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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
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 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does 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 NeurlPS 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.
40


Reviews:
[{"review_id": "N3TtphfF3l", "reviewer": "Reviewer_L1q2", "summary": "The authors apply the smoothed analysis framework predominantly studied by (Spielman and Teng'04) to some common sequential algorithms for learning the Nash equilibria in zero-sum bimatrix games. To this end, they look at EGDA, OGDA, OMWU and IterSmooth. They look at these algorithms that have known last-iterate convergence properties, albeit with game dependent constants or do not have linear rates in the worst case. Their main techniques are to show important constants and condition numbers have polynomial dependence on the game dimensions and the noise parameter.", "questions": "Can the authors comment if the smoothed analysis could give insights going beyond bimatrix games, such as the performance of the algorithms studied in this paper but for convex-concave settings or for low-rank bimatrix non-zero sum games?\n\nMinor:\nTypo in page 8, line 395 ...of the error bond->...bound.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is one way to understand the average case performance of some common algorithms for solving bimatrix games. Their results instill some sense of confidence in these algorithms as their average case performance is polynomial in the dimensions and has a linear last-iterate behavior, except OMWU, which perhaps indicates some intrinsic intractability with respect to the best obtainable constants still being game dependent!", "weaknesses": "1) I think the authors could perhaps provide more justification for using smoothed analysis in this context. In the standard sense, it is about understanding perturbation of worst case instances (for simplex). For games, often we do not clearly know the worst case game matrices for certain algorithms.\n\n2) Some assumptions related to perturbations of the A matrix, that is in definition 4.1 could be restrictive, in that the support of the equilibrium doesn't change. Can the authors comment on whether this can be relaxed to a certain extent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and service.\n\n*Can the authors comment if the smoothed analysis could give insights going beyond bimatrix games, such as the performance of the algorithms studied in this paper but for convex-concave settings or for low-rank bimatrix non-zero sum games?*\n\nThis is an interesting question. Beyond (two-player) matrix games, perhaps the most natural next step would concern polymatrix zero-sum games, for which we suspect that similar results should apply. For general convex-concave games, it is not clear to us how one should even define the perturbed instance, unless the underlying function is more structured. When it comes to nonzero-sum bimatrix games, even under a low-rank constraint computing Nash equilibria is hard (unless the rank is 1), and so iterative algorithms instead converge in a time-average sense to a so-called coarse correlated equilibrium (CCE). It is unclear whether the framework of smoothed complexity can lead to meaningful improvements when it comes to convergence to CCE. On the other hand, it seems plausible that our results can be extended to rank-1 games. \n\n*Some assumptions related to perturbations of the A matrix, that is in definition 4.1 could be restrictive, in that the support of the equilibrium doesn't change. Can the authors comment on whether this can be relaxed to a certain extent?*\n\nThere are other natural notions of perturbation stability one could consider in the context of Section 4; for example, that the equilibrium of the perturbed game must be $\\delta$-close to the equilibrium of the original game. It is not clear whether a result such as Theorem 4.2 applies to that notion, but we believe this is an interesting question for future work. One technical challenge we should point out here is that our characterization of Theorem 3.6 does not handle multiplicity of equilibria, which appears to be relevant for other notions of perturbation stability.\n\n*I think the authors could perhaps provide more justification for using smoothed analysis in this context.*\n\nBesides the usual justification for performing smoothed analysis in the context of linear programming and optimization, which applies to zero-sum games as well, we believe that in game-theoretic problems smoothed complexity is even more relevant since there is often noise/imprecision when specifying the players’ utilities. This puts into question some worst-case pathological examples, such as the one specified in Proposition 3.1. Those are the type of examples for which algorithms such as OGD perform poorly in practice.\n\nFinally, we thank the reviewer for spotting the typo.", "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": "9Ps3j8yTrf", "reviewer": "Reviewer_uKXc", "summary": "This paper studies smoothed analysis of gradient-based algorithms for computing equilibria in zero-sum games. In general, regret minimization can be used to compute an $\\epsilon$-equilibrium in a number of iterations polynomial in $1/\\epsilon$. If inverse polynomial or better precision in $\\epsilon$ is desired, this iteration count becomes prohibitively large. In this case LP solvers based on interior point methods can be used, which have iteration counts of $\\log(1/\\epsilon)$, but high per-iteration complexity and memory requirements. This paper shows that several standard gradient-based algorithms converge to an $\\epsilon$-approximate equilibrium in a number of iterations polynomial in $\\log(1/\\epsilon)$ in the setting of smoothed analysis. In particular the runtime also depends polynomially on $1/\\sigma$, where $\\sigma$ is the variance of the smoothing noise.\n\nThe general approach taken in this paper is to prove that, for a smoothed zero-sum game, the duality gap of a pair of strategies is with high probability at most polynomially (in the size of the game  $nm$ and the noise variance $\\sigma$) smaller than the $\\ell_2$ distance to the equilibrium strategy pair. Existing analysis of several standard gradient descent methods then imply convergence to an $\\epsilon$-equilibrium in time polynomial in $nm,1/\\sigma,\\log(1/\\epsilon)$.", "questions": "Could you clarify precisely how gradient based methods in the smoothed setting improve over, say interior point methods which also achieve $\\log(1/\\epsilon)$ iteration complexity? Probably you can claim lower space requirements, but is there anything else to say?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides, to my knowledge, the first theoretical justification for using gradient-based methods as equilibrium solvers in zero sum games in the high-precision regime, i.e. where $\\epsilon$ is inverse polynomial in the size of the game.\n2. The approach via smoothed analysis is quite generic: it revolves around structural properties of the game relating distance to the equilibrium and the duality gap. This structural property appears in the analysis of several gradient-based algorithms, and so the results can be applied to directly obtain $\\log(1/\\epsilon)$ convergence to $\\epsilon$-equilibria.", "weaknesses": "The paper relies heavily on techniques for smoothed analysis of linear programming developed by Spielman and Teng. This is in some sense to be expected due to the strong connections between zero-sum games and linear-programming. As the authors point out, the smoothed analysis of gradient-based methods is well-known in the unconstrained min-max setting, and the main problem is that for zero-sum games the strategies must be constrained to be probability distributions.\n\n\nClarity:\n\nLine 260: The introduction of $Q$, $d$, and $c$ here as implicitly defined by equation (5) was not very illuminating. Going to the appendix to see the full definition eventually resolves this, but this part could be better written.\n\nLine 774 and 776:  Refs to Definition 3.1 should probably be refs to Theorem 3.6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and service.\n\nWe also thank the reviewer for pointing out the issues with clarity. We will make sure to incorporate the suggestions in the revision.\n\n*Could you clarify precisely how gradient based methods in the smoothed setting improve over, say interior point methods which also achieve $\\log(1/\\epsilon)$ iteration complexity? Probably you can claim lower space requirements, but is there anything else to say?*\n\nThe two main aspects on which gradient-based algorithms, such as OGD, are more appealing than interior-point methods are the per-iteration complexity and the memory requirements. An algorithm such as OGD requires a single matrix-vector product per iteration; this is nearly linear for sparse matrices, and can be even smaller when the game-matrix is more structured (for example, low-rank). The memory requirements of OGD are also minimal, as the reviewer points out. On the other hand, interior-point methods require solving a linear system in each iteration, which can be prohibitive in large games. In those regards gradient-based algorithms are more compelling.", "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": "adASLrLdc9", "reviewer": "Reviewer_La2m", "summary": "This paper performs a smoothed analysis for zero-sum games. Existing convergence rate guaratees of gradient-based algorithms often depend on condition number-like quantities which can be exponential in dimension. This paper shows that for the average case or smoothed case (as opposed to worst-case) the error condition constant can be polynomial in dimension. This validates practically observed success of gradient-based algorithms to solve zero-sum games.\n\nThe paper also discusses the relation between $\\delta$-stable games and error-bound condition constant.", "questions": "See Weakness section.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strength of the paper is Theorem 1.4 which shows that, in the smoothed case, the error-bound coefficient is polynomial in problem dimensions. This deals with an important problem and bridges the gap between theoretical rates and success of gradient-based algorithms in real life to solve zero-sum games. \n\nThe paper is easy to read.", "weaknesses": "1. The paper lacks adequate comparison with existing literature. There has been considerable research on smoothed analysis of optimization problems (see [1] for example). Since standard (worst-case) analysis of gradient-based algorithms like OGDA, EGDA, etc. to solve (1) is quite similar to analysis of gradient-based algorithms to solve constrained convex optimization problem, I expect the novelty required to deal with the smoothed version of (1) should be pretty similar to the established techniques to deal with smoothed analysis of constrained convex optimization problem. If this is not true, I request you to provide a detailed discussion delineating the two scenarios and highlighting the novelties required in this paper on top of smoothed analysis of convex minimization problems.\n\n2. Convergence in terms of euclidean distance instead of duality gap should be less emphasized as contribution/novelty as these type of results are already known for gradient-based algorithms. \n\nMinor Suggestions:\n\n3. The paper abstract and possibly title should be reflective of the fact that Theorem 1.4 is the main message of the paper (instead of convergence rates) as all the other results of the paper readily follows from Theorem 1.4. \n\n4. An example where the the constant $\\kappa$ depends exponentially on $m,n$ could be helpful. \n\nReason for my score: Theorem 1.4 seems to be the main contribution - the proof of which mostly requires change of variables and well-known concentration results for Gaussian random variables. This result by itself, although a very nice result, seems a little inadequate for a NeurIPS level paper. But I am on the fence here and I may change my score depending on answer to the first question under Weakness section.  \n\n[1]Cunha, Leonardo, Gauthier Gidel, Fabian Pedregosa, Damien Scieur, and Courtney Paquette. \"Only tails matter: Average-case universality and robustness in the convex regime.\" In International Conference on Machine Learning, pp. 4474-4491. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and service.\n\n*The paper lacks adequate comparison with existing literature. There has been considerable research on smoothed analysis of optimization problems (see [1] for example).*\n\nWe will make sure to cite and discuss [1] (and some of the references therein) in the revised version. There are many crucial differences between our results and [1]. \n\n- First, [1] focuses on certain convex quadratic problems while we examine zero-sum games. \n- The perturbation model between our paper and [1] are also different, as the latter has an average-case flavor (parameterized by the concentration of eigenvalues of a certain matrix) while we work in the usual smoothed complexity model of Spielman and Teng. \n- Our main result establishes an iteration complexity scaling with $\\log(1/\\epsilon)$, while [1] obtains a complexity polynomial in $1/\\epsilon$ (unless there is strong convexity, which is not the case in our problem). \n- Moreover, the algorithms considered in [1] are distinct from ours, although they are also gradient-based, and the techniques are also very different. In particular, [1] assumes (see Problem 2.1 in that paper) that the underlying randomization is independent of the optimal solution. On the other hand, as we stress throughout our paper, the fact that in our setting the equilibrium depends on the randomization is the main technical challenge.\n\nOverall, the technical challenges we faced are very different from the ones in [1], and we believe that the papers are generally orthogonal. We will include the above discussion in the revision.\n\n\n*Convergence in terms of euclidean distance instead of duality gap should be less emphasized as contribution/novelty as these type of results are already known for gradient-based algorithms*\n\nThe contribution/novelty of our results in terms of Euclidean distance is that they provide the first polynomial bounds in the smoothed complexity model. Many results in terms of Euclidean distance were known, as the reviewer points out and as we highlight throughout the paper, but they had to rely on exponentially large constants. We believe that this improvement–which is obtained in conjunction with those known results–is worth highlighting as an important contribution.\n\n\n*​​The paper abstract and possibly title should be reflective of the fact that Theorem 1.4 is the main message of the paper (instead of convergence rates) as all the other results of the paper readily follows from Theorem 1.4.*\n\nWe will expand the abstract to reflect the fact that Theorem 1.4 is the main technical contribution. \n\n*An example where the constant $\\kappa$ depends exponentially on $m, n$ could be helpful.*\n\nStarting from the $3 \\times 3$ example of Proposition 3.1, one can make $\\kappa$ to be inversely exponential in $m, n$ by suitable selecting $\\gamma = \\gamma(n, m)$ (and filling the rest of the matrix according to the identity matrix).", "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": "kZtbsb5ydk", "reviewer": "Reviewer_NLN1", "summary": "The paper is concerned with studying the convergence of some state-of-the-art gradient-based algorithms for solving zero-sum games. For these algorithms, it is known that in the worst case, the number of their iterations grows polynomially in 1/e, where e is the error bound.\n\nThe paper shows that for many of the aforementioned algorithms, their smoothed complexity is polynomial in the sense that their number of iterations grows polynomially in log(1/e).", "questions": "No questions.", "limitations": "No limitations found.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies state-of-art algorithms that have significant important in ML applications.\n2. The paper provides meaningful justifications as to why some of the gradient-based algorithms for zero-sum games perform well in practice.", "weaknesses": "No noted weaknesses. This seems to be a very solid paper that's very relevant to the scope of NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and service.", "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": "WRGxGYxZv1", "reviewer": "Reviewer_RDh1", "summary": "The paper provides smoothed analysis results four gradient-based algorithms for two-player zeros-sum games: OGDA, OMWU, EGDA and IterSmooth. The considered setting assumes that the payoff matrix is injected by noise where each element of the noise matrix is i.i.d. Gaussian $\\mathcal{N}(0, \\sigma^2)$. In this setting, the linear convergence rate $O(\\log(1/\\epsilon))$ of three algorithms OGDA, EGDA and IterSmooth are proved to hold with probability $1- \\frac{1}{mn}$, where $m$ and $n$ are dimensions of the action space of the two players. The proofs rely on a key insight that with high probability over the randomness of the noise, the payoff matrix (and hence the game) satisfies a particular error bound that gives rise to the $\\log(1/\\epsilon)$ convergence rate.", "questions": "1. In the presentation of section 3.2, the matrix $Q$ (and subsequently $\\tilde{x}$ and $\\tilde{y}$)  is defined based on a particular pair of indexes $(i, j) \\in B \\times N$. Are all subsequent claims hold for all $(i, j)$?\n\n2. Is there a reason for the missing proof of claim C.2?", "limitations": "The work is of mathematical nature and has no societal impact.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper offers novel techniques to analyze the reliability of existing gradient-based algorithms. These new techniques sidestep the difficulty on condition numbers-like quantity in previous analyses, and instead focus on the geometric characteristics of (the equilibrium of) the game. This seems highly interesting and significant.", "weaknesses": "I find the writing hard to understand. Theorems, lemmas and technical results are often discussed before they are explained and/or formally defined.  In particular, the definition of the matrix $Q$ in Equation (5) is quite confusing as it is not worded as a definition at all. The vector $b, c$ and value $d$ also seem to come out of no where.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and service.\n\n*In the presentation of section 3.2, the matrix $Q$ is defined based on a particular pair of indexes $(i,j) \\in B \\times N$. Are all subsequent claims hold for all $(i,j)$?*\n\nMatrix $Q$ is indeed defined with respect to a certain pair $(i,j) \\in B \\times N$, and all subsequent claims hold for any such $(i, j)$.\n\n*Is there a reason for the missing proof of claim C.2?*\n\nThe proof of Claim C.2 is in the paragraph just before Claim C.2. We are happy to transfer the proof after the claim if the reviewer believes the current version can cause confusion.\n\n*The definition of the matrix $Q$  in Equation (5) is quite confusing as it is not worded as a definition at all. The vector $b, c$ and value $d$ also seem to come out of no where.*\n\nThose quantities are defined in Eq. (10) of the appendix. Their exact definition is not important for the purpose of the main body, but we will make sure to include Eq. (10) in the main body of the revision as we see how the current version can cause some confusion.\n\nLet us know if we can further make the writing easier to understand.", "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:

Meta-review: This paper studies the smoothed analysis of gradient-based algorithms for computing equilibria in bilinear two-player zero-sum games over simplexes in a high-precision regime. The existing algorithms covered in this paper have known last-iterate worst-case convergence rate but might suffer from an undesirable dependency on the dimension of the matrix, as discussed via a toy example from Proposition 3.1 in this paper.

Motivated by this issue, the paper studies the smoothed analysis of some gradient-based algorithms for computing equilibria in zero-sum games and shows that their complexity depends on a polynomial in the dimension, $\log(1/\epsilon)$, and $1/\sigma$, where $\sigma$ measures the magnitude of the smoothing perturbation. 

This paper received unanimous support, has gone through the discussions, and is hence recommended for acceptance.

In the camera-ready version, it would be more illuminating if some proof-of-concept experimental results (e.g., using the toy example from Proposition 3.1) could be included to support the theoretical results.
Decision: Accept (poster)