Tight last-iterate convergence rates for no-regret learning in multi-player games

We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with a constant step-size, which is no-regret, achieves a last-iterate rate of $O(1/\sqrt{T})$ with respect to the gap function in smooth monotone games. This result addresses a question of Mertikopoulos&Zhou (2018), who asked whether extra-gradient approaches (such as OG) can be applied to achieve improved guarantees in the multi-agent learning setting. The proof of our upper bound uses a new technique centered around an adaptive choice of potential function at each iteration. We also show that the $O(1/\sqrt{T})$ rate is tight for all $p$-SCLI algorithms, which includes OG as a special case. As a byproduct of our lower bound analysis we additionally present a proof of a conjecture of Arjevani et al. (2015) which is more direct than previous approaches.


Introduction
In the setting of multi-agent online learning ( [SS11,CBL06]), K players interact with each other over time. At each time step t, each player k ∈ {1, . . . , K} chooses an action z (t) k ; z (t) k may represent, for instance, the bidding strategy of an advertiser at time t. Player k then suffers a loss ℓ t (z (t) k ) that depends on both player k's action z (t) k and the actions of all other players at time t (which are absorbed into the loss function ℓ t (·)). Finally, player k receives some feedback informing them of how to improve their actions in future iterations. In this paper we study gradient-based feedback, meaning that the feedback is the vector g (t) A fundamental quantity used to measure the performance of an online learning algorithm is the regret of player k, which is the difference between the total loss of player k over T time steps and the loss of the best possible action in hindsight: formally, the regret at time T is An algorithm is said to be no-regret if its regret at time T grows sub-linearly with T for an adversarial choice of the loss functions ℓ t . If all agents playing a game follow no-regret learning algorithms to choose their actions, then it is well-known that the empirical frequency of their actions converges to a coarse correlated equilibrium (CCE) ([MV78, CBL06]). In turn, a substantial body of work (e.g., [CBL06, DP09, EDMN09, CD11, VZ13, KKDB15, BTHK15, MP17, MZ18, KBTB18]) has focused on establishing for which classes of games or learning algorithms this convergence to a CCE can be strengthened, such as to convergence to a Nash equilibrium (NE).
However, the type of convergence guaranteed in these works generally either applies only to the timeaverage of the joint action profiles, or else requires the sequence of learning rates to converge to 0. Such guarantees leave substantial room for improvement: a statement about the average of the joint action profiles a no-regret learning algorithm with constant step size? (⋆) We measure the proximity of an action profile z = (z 1 , . . . , z K ) to equilibrium in terms of the total gap function at z (Definition 3): it is defined to be the sum over all players k of the maximum decrease in cost player k could achieve by deviating from its action z k .
[LZMJ20] took initial steps toward addressing (⋆), showing that if all agents follow the online gradient descent algorithm, then for all λ-cocoercive games, the action profiles z (t) = (z (t) 1 , . . . , z (t) K ) will converge to equilibrium in terms of the total gap function at a rate of O(1/ √ T ). Moreover, linear last-iterate rates have been long known for smooth strongly-monotone games ([Tse95, GBV + 18, LS18, MOP19b, AMLJG19, ZMM + 20]), a sub-class of λ-cocoercive games. Unfortunately, even λ-cocoercive games exclude many important classes of games, such as bilinear games, which are the adaptation of matrix games to the unconstrained setting. Moreover, this shortcoming is not merely an artifact of the analysis of [LZMJ20]: it has been observed (e.g. [DISZ17, GBV + 18]) that in bilinear games, the players' actions in online gradient descent not only fail to converge, but diverge to infinity. Prior work on last-iterate convergence rates for these various subclasses of monotone games is summarized in Table 1 for the case of perfect gradient feedback; the setting for noisy feedback is summarized in Table 2 in Appendix A.4.

Our contributions
In this paper we answer (⋆) in the affirmative for all monotone games (Definition 1) satisfying a mild smoothness condition, which includes smooth λ-cocoercive games and bilinear games. Many common and well-studied classes of games, such as zero-sum polymatrix games ( [BF87,DP09,CCDP16]) and its generalization zero-sum socially-concave games ([EDMN09]) are monotone but are not in general λ-cocoercive. Hence our paper is the first to prove last-iterate convergence in the sense of (⋆) for the unconstrained version of these games as well. In more detail, we establish the following: • We show in Theorem 5 and Corollary 6 that the actions taken by learners following the optimistic gradient (OG) algorithm, which is no-regret, exhibit last-iterate convergence to a Nash equilibrium in smooth, monotone games at a rate of O(1/ √ T ) in terms of the global gap function. The proof uses a new technique which we call adaptive potential functions (Section 3.1) which may be of independent interest.
• We show in Theorem 7 that the rate O(1/ √ T ) cannot be improved for any algorithm belonging to the class of p-SCLI algorithms (Definition 5), which includes OG.
The OG algorithm is closely related to the extra-gradient (EG) algorithm ([Kor76, Nem04]), 2 which, at each time step t, assumes each player k has an oracle O k which provides them with an additional gradient at a slightly different action than the action z (t) k played at step t. Hence EG does not naturally fit into the standard setting of multi-agent learning. One could try to "force" EG into the setting of multi-agent learning by taking actions at odd-numbered time steps t to simulate the oracle O k , and using the even-numbered time steps to simulate the actions z (t) k that EG actually takes. Although this algorithm exhibits last-iterate convergence at a rate of O(1/ √ T ) in smooth monotone games when all players play according to it [GPDO20], it is straightforward to see that it is not a no-regret learning algorithm, i.e., for an adversarial loss function the regret can be linear in T (see Proposition 10 in Appendix A.3).
Nevertheless, due to the success of EG at solving monotone variational inequalities, [MZ18] asked whether similar techniques to EG could be used to speed up last-iterate convergence to Nash equilibria. Our upper bound for OG answers this question in the affirmative: various papers ([CYL + 12, RS12, RS13, HIMM19]) have observed that OG may be viewed as an approximation of EG, in which the previous iteration's gradient is used to simulate the oracle O k . Moreover, our upper bound of O(1/ √ T ) applies in many games for which the approach used in [MZ18], namely Nesterov's dual averaging ([Nes09]), either fails to converge (such as bilinear games) or only yields asymptotic rates with decreasing learning rate (such as smooth strictly monotone games). Proving last-iterate rates for OG has also been noted as an important open question in [HIMM19, Table 1]. At a technical level, the proof of our upper bound (Theorem 5) uses the proof technique in [GPDO20] for the last-iterate convergence of EG as a starting point. In particular, similar to [GPDO20], our proof proceeds by first noting that some iterate z (t * ) of OG will have gradient gap O(1/ √ T ) (see Definition 2; this is essentially a known result) and then showing that for all t ≥ t * the gradient gap only increases by at most a constant factor. The latter step is the bulk of the proof, as was the case in [GPDO20]; however, since each iterate of OG depends on the previous two iterates and gradients, the proof for OG is significantly more involved than that for EG. We refer the reader to Section 3.1 and Appendix B for further details.
The proof of our lower bound for p-SCLI algorithms, Theorem 7, reduces to a question about the spectral radius of a family of polynomials. In the course of our analysis we prove a conjecture by [ASSS15] about such polynomials; though the validity of this conjecture is implied by each of several independent results in the literature (e.g., [AS16,Nev93]), our proof is more direct than previous ones.
Lastly, we mention that our focus in this paper is on the unconstrained setting, meaning that the players' losses are defined on all of Euclidean space. We leave the constrained setting, in which the players must project their actions onto a convex constraint set, to future work.

Related work
Multi-agent learning in games. In the constrained setting, many papers have studied conditions under which the action profile of no-regret learning algorithms, often variants of Follow-The-Regularized-Leader (FTRL), converges to equilibrium. However, these works all assume either a learning rate that decreases over time ([MZ18, ZMB + 17, ZMA + 18, ZMM + 17]), or else only apply to specific types of potential games ([KKDB15, KBTB18, PPP17, KPT09, CL16, BEDL06, PP14]), which significantly facilitates the analysis of last-iterate convergence. 3 Such potential games are in general incomparable with monotone games, and do not even include finitestate two-player zero sum games (i.e., matrix games). In fact, [BP18] showed that the actions of players following FTRL in two-player zero-sum matrix games diverge from interior Nash equilibria. Many other works ([HMC03, MPP17, KLP11, DFP + 10, BCM12, PP16]) establish similar non-convergence results in both discrete and continuous time for various types of monotone games, including zero-sum polymatrix games. Such non-convergence includes chaotic behavior such as Poincaré recurrence, which showcases the insufficiency of on-average convergence (which holds in such settings) and so is additional motivation for the question (⋆).

Monotone variational inequalities & OG.
The problem of finding a Nash equilibrium of a monotone game is exactly that of finding a solution to a monotone variational inequality (VI). OG was originally introduced by [Pop80], who showed that its iterates converge to solutions of monotone VIs, without proving explicit rates. 4 It is also well-known that the averaged iterate of OG converges to the solution of a monotone VI at a rate of O(1/T ) ([HIMM19, MOP19a, RS13]), which is known to be optimal ([Nem04, OX19, ASM + 20]). Recently it has been shown ([DP18, LNPW20]) that a modification of OG known as optimistic multiplicativeweights update exhibits last-iterate convergence to Nash equilibria in two-player zero-sum monotone games, but as with the unconstrained case ([MOP19a]) non-asymptotic rates are unknown. To the best of our knowledge, the only work proving last-iterate convergence rates for general smooth monotone VIs was [GPDO20], which only treated the EG algorithm, which is not no-regret. There is a vast literature on solving VIs, and we refer the reader to [FP03] for further references.

Preliminaries
Throughout this paper we use the following notational conventions. For a vector v ∈ R n , let v denote the Euclidean norm of v. For v ∈ R n , set B(v, R) := {z ∈ R n : v − z ≤ R}; when we wish to make the dimension explicit we write B R n (v, R). For a matrix A ∈ R n×n let A σ denote the spectral norm of A.
We let the set of K players be denoted by K := {1, 2, . . . K}. Each player k's actions z k belong to their action set, denoted Z k , where Z k ⊆ R n k is a convex subset of Euclidean space. Let Z = K k=1 Z k ⊆ R n , where n = n 1 + · · · + n K . In this paper we study the setting where the action sets are unconstrained (as in [LZMJ20]), meaning that Z k = R n k , and Z = R n , where n = n 1 + · · · + n K . The action profile is the vector z := (z 1 , . . . , z K ) ∈ Z. For any player k ∈ K, let z −k ∈ k ′ =k Z k ′ be the vector of actions of all the other players. Each player k ∈ K wishes to minimize its cost function f k : Z → R, which is assumed to be twice continuously differentiable. The tuple G := (K, (Z k ) K k=1 , (f k ) K k=1 ) is known as a continuous game. At each time step t, each player k plays an action z (t) k ; we assume the feedback to player k is given in the form of the gradient −k ) of their cost function with respect to their action z (t) k , given the actions z (t) −k of the other players at time t. We denote the concatenation of these gradients by F G (z) := (∇ z1 f 1 (z), . . . , ∇ zK f K (z)) ∈ R n . When the game G is clear, we will sometimes drop the subscript and write F : Z → R n .
Equilibria & monotone games. A Nash equilibrium in the game G is an action profile z * ∈ Z so that for each player k, it holds that for any z ′ k ∈ Z k . Throughout this paper we study monotone games: In such a case, we say also that F G is a monotone operator.
The following classical result characterizes the Nash equilibria in monotone games: In the unconstrained setting, if the game G is monotone, any Nash equilibrium z * satisfies F G (z * ) = 0. Conversely, if F G (z) = 0, then z is a Nash equilibrium.
In accordance with Proposition 1, one measure of the proximity to equilibrium of some z ∈ Z is the norm of F G (z): Definition 2 (Gradient gap function). Given a monotone game G with its associated operator F G , the gradient gap function evaluated at z is defined to be F G (z) .
It is also common ([MOP19a, Nem04]) to measure the distance from equilibrium of some z ∈ Z by adding the maximum decrease in cost that each player could achieve by deviating from their current action z k : Definition 3 (Total gap function). Given a monotone game G = (K, (Z k ) K k=1 , (f k ) K k=1 ), compact subsets Z ′ k ⊆ Z k for each k ∈ K, and a point z ∈ Z, define the total gap function at z with respect to the set . At times we will slightly abuse notation, and for F := F G , write TGap Z ′ F in place of TGap Z ′ G . As discussed in [GPDO20], it is in general impossible to obtain meaningful guarantees on the total gap function by allowing each player to deviate to an action in their entire space Z k , which necessitates defining the total gap function in Definition 3 with respect to the compact subsets Z ′ k . We discuss in Remark 4 how, in our setting, it is without loss of generality to shrink Z k so that Z k = Z ′ k for each k. Proposition 2 below shows that in monotone games, the gradient gap function upper bounds the total gap function: is a monotone game, and compact subsets Z ′ k ⊂ Z k are given, where the diameter of each Z ′ k is upper bounded by D > 0. Then For completeness, a proof of Proposition 2 is presented in Appendix A.
Special case: convex-concave min-max optimization. Since in a two-player zero-sum game G = ({1, 2}, (Z 1 , Z 2 ), (f 1 , f 2 )) we must have f 1 = −f 2 , it is straightforward to show that f 1 (z 1 , z 2 ) is convex in z 1 and concave in z 2 . Moreover, it is immediate that Nash equilibria of the game G correspond to saddle points of f 1 ; thus a special case of our setting is that of finding saddle points of convex-concave functions ([FP03]). Such saddle point problems have received much attention recently since they can be viewed as a simplified model of generative adversarial networks (e.g., [GBV + 18, DISZ17, CGFLJ19, GHP + 18, YSX + 17]).
Optimistic gradient (OG) algorithm. In the optimistic gradient (OG) algorithm, each player k performs the following update: z where g The following essentially optimal regret bound is well-known for the OG algorithm, when the actions of the other players z (t) −k (often referred to as the environment's actions) are adversarial: In Proposition 3, z * k is defined by The assumption in the proposition that z (t) k ≤ D may be satisfied in the unconstrained setting by projecting the iterates onto the region B(0, D) ⊂ R n k , for some D ≥ z * k , without changing the regret bound. The implications of this modification to (OG) are discussed further in Remark 4.

Last-iterate rates for OG via adaptive potential functions
In this section we show that in the unconstrained setting (namely, that where Z k = R n k for all k ∈ K), when all players act according to OG, their iterates exhibit last-iterate convergence to a Nash equilibrium. Our convergence result holds for games G for which the operator F G satisfies the following smoothness assumption: Assumption 4 (Smoothness). For a monotone operator F : Z → R n , assume that the following first and second-order Lipschitzness conditions hold, for some ℓ, Λ > 0: Here ∂F : Z → R n×n denotes the Jacobian of F .
By the definition of F G (·), when all players in a game G act according to (OG) with constant step size η, then the action profile z (t) takes the form The main theorem of this section, Theorem 5, shows that under the OG updates (3), the iterates converge at a rate of O(1/ √ T ) to a Nash equilibrium with respect to the gradient gap function: Theorem 5 (Last-iterate convergence of OG). Suppose G is a monotone game so that F G satisfies Assumption 4. For some Then the iterates z (T ) of OG (3) for any η ≤ min 1 150ℓ , 1 1711DΛ satisfy: By Proposition 2, we immediately get a bound on the total gap function at each time T : Corollary 6 (Total gap function for last iterate of OG). In the setting of Theorem 5, let Z ′ k := B(z We made no attempt to optimize the consants in Theorem 5 and Corollary 6, and they can almost certainly be improved.
Remark 4 (Bounded iterates). Recall from the discussion following Proposition 3 that it is necessary to project the iterates of OG onto a compact ball to achieve the no-regret property. As our guiding question (⋆) asks for last-iterate rates achieved by a no-regret algorithm, we should ensure that such projections are compatible with the guarantees in Theorem 5 and Corollary 6. For this we note that [MOP19a, Lemma 4(b)] showed that for the dynamics (3) without constraints, for all t ≥ 0, z (t) − z * ≤ 2 z (0) − z * . Therefore, as long as we make the very mild assumption of a known a priori upper bound z * ≤ D/2 (as well as z , if all players act according to (3), then the updates (3) remain unchanged if we project onto the constraint sets Z k := B(0, 3D) at each time step t. This observation also serves as motivation for the compact sets Z ′ k used in Corollary 6: the natural choice for Z ′ k is Z k itself, and by restricting Z k to be compact, this choice becomes possible.

Proof overview: adaptive potential functions
In this section we sketch the idea of the proof of Theorem 5; full details of the proof may be found in Appendix B. First we note that it follows easily from results of [HIMM19] that OG exhibits best-iterate convergence, i.e., in the setting of Theorem 5 we have, for each T > 0, min 1≤t≤T F G (z (t) ) ≤ O(1/ √ T ). 5 The main contribution of our proof is then to show the following: if we choose t * so that ) . This was the same general approach taken in [GPDO20] to prove that the extragradient (EG) algorithm has last-iterate convergence. In particular, they showed the stronger statement that F G (z (t) ) may be used as an approximate potential function in the sense that it only increases by a small amount each step: However, their approach relies crucially on the fact that for the EG algorithm, z (t+1) depends only on z (t) .
For the OG algorithm, it is possible that (6) fails to hold, even when F G (z (t) ) is replaced by the more natural choice of (F G (z (t) ), F G (z (t−1) )). 6 Instead of using F G (z (t) ) as a potential function in the sense of (6), we propose instead to track the behavior of F (t) , whereF and the matrices C (t−1) ∈ R n×n are defined recursively backwards, i.e., C (t−1) depends directly on C (t) , which depends directly on C (t+1) , and so on. For an appropriate choice of the matrices C (t) , we show that . This modification of (6) is enough to show the desired upper bound of F G (z (T ) ) ≤ O(1/ √ T ). To motivate the choice ofF (t) in (7) it is helpful to consider the simple case where F (z) = Az for some A ∈ R n×n , which was studied by [LS18]. Simple algebraic manipulations using (3) (detailed in Appendix B) show that, for the matrix C := (I+(2ηA) 2 ) 1/2 −I 2 , we haveF (t+1) = (I − ηA + C)F (t) for all t. It may be verified that we indeed have A (t) = A and C (t) = C for all t in this case, and thus (7) may be viewed as a generalization of these calculations to the nonlinear case.
Adaptive potential functions. In general, a potential function Φ(F G , z) depends on the problem instance, here taken to be F G , and an element z representing the current state of the algorithm. Many convergence analyses from optimization (e.g., [BG17,WRJ18], and references therein) have as a crucial element in their proofs a statement of the form Φ(F G , z (t+1) ) Φ(F G , z (t) ). For example, for the iterates z (t) of the EG algorithm, [GPDO20] (see (6)) used the potential function Φ(F G , z (t) ) := F G (z (t) ) .
Our approach of controlling the the norm of the vectorsF (t) defined in (7) can also be viewed as an instantion of the potential function approach: since each iterate of OG depends on the previous two iterates, the state is now given by v (t) := (z (t−1) , z (t) ). The potential function is given by Φ OG (F G , v (t) ) := F (t) , whereF ⊤ is defined in (7) and indeed only depends on v (t) once F G is fixed since v (t) determines z (t ′ ) for all t ′ ≥ t (as OG is deterministic), which in turn determine C (t−1) . However, the potential function Φ OG is quite unlike most other choices of potential functions in optimization (e.g., [BG17]) in the sense that it depends globally on F G : For any t ′ > t, a local change in adapts to the behavior of F G at iterates later on in the optimization sequence, we call it an adaptive potential function. We are not aware of any prior works using such adaptive potential functions to prove last-iterate convergence results, and we believe this technique may find additional applications.

Lower bound for convergence of p-SCLIs
The main result of this section is Theorem 7, stating that the bounds on last-iterate convergence in Theorem 5 and Corollary 6 are tight when we require the iterates z (T ) to be produced by an optimization algorithm satisfying a particular formal definition of "last-iterate convergence". Notice that that we cannot hope to prove that they are tight for all first-order algorithms, since the averaged iteratesz (T ) := 1 Theorem 2]. Similar to [GPDO20], we use p-stationary canonical linear iterative methods (p-SCLIs) to formalize the notion of "last-iterate convergence". [GPDO20] only considered the special case p = 1 to establish a similar lower bound to Theorem 7 for a family of last-iterate algorithms including the extragradient algorithm. The case p > 1 leads to new difficulties in our proof since even for p = 2 we must rule out algorithms such as Nesterov's accelerated gradient descent ([Nes75]) and Pólya's heavy-ball method ([Pol87]), a situation that did not arise for p = 1.
For simplicity, we restrict our attention to monotone operators F arising as F = F G : R n → R n for a two-player zero-sum game G (i.e., the setting of min-max optimization). For simplicity suppose that n is even and for z ∈ R n write z = (x, y) where x, y ∈ R n/2 . Define F bil n,ℓ,D to be the set of ℓ-Lipschitz operators F : R n → R n of the form F (x, y) = (∇ x f (x, y), −∇ y f (x, y)) ⊤ for some bilinear function f : R n/2 × R n/2 → R, with a unique equilibrium point z * = (x * , y * ), which satisfies z * ∈ D D := B R n/2 (0, D) × B R n/2 (0, D). The following Theorem 7 uses functions in F bil n,ℓ,D as "hard instances" to show that the O(1/ √ T ) rate of Corollary 5 cannot be improved by more than an algorithm-dependent constant factor.
Theorem 7 (Algorithm-dependent lower bound for p-SCLIs). Fix ℓ, D > 0, let A be a p-SCLI, and let z (t) denote the tth iterate of A. Then there are constants c A , T A > 0 so that the following holds: For all T ≥ T A , there is some F ∈ F bil n,ℓ,D so that for some initialization z (0) , . . . , z (−p+1) ∈ D D and T ′ ∈ {T, T + 1, . . . , T + p − 1}, it holds that TGap D2D We remark that the order of quantifiers in Theorem 7 is important: if instead we first fix a monotone operator F ∈ F bil n,ℓ,D corresponding to some bilinear function f (x, y) = x ⊤ My, then as shown in [LS18, Theorem 3], the iterates z (T ) = (x (T ) , y (T ) ) of the OG algorithm will converge at a rate of e , which eventually becomes smaller than the sublinear rate of 1/ √ T . 8 Such "instance-specific" bounds are complementary to the minimax perspective taken in this paper.
We briefly discuss the proof of Theorem 7; the full proof is deferred to Appendix C. As in prior work proving lower bounds for p-SCLIs ([ASSS15, IAGM19]), we reduce the problem of proving a lower bound on TGap DD G (z (t) ) to the problem of proving a lower bound on the supremum of the spectral norms of a family of polynomials (which depends on A). Recall that for a polynomial p(z), its spectral norm ρ(p(z)) is the maximum norm of any root. We show: Proposition 8. Suppose q(z) is a degree-p monic real polynomial such that q(1) = 0, r(z) is a polynomial of degree p − 1, and ℓ > 0. Then there is a constant C 0 > 0, depending only on q(z), r(z) and ℓ, and some µ 0 ∈ (0, ℓ), so that for any µ ∈ (0, µ 0 ), The proof of Proposition 8 uses elementary tools from complex analysis. The fact that the constant C 0 in Proposition 8 depends on q(z), r(z) leads to the fact that the constants c A , T A in Theorem 7 depend on A. Moreover, we remark that this dependence cannot be improved from Proposition 8, so removing it from Theorem 7 will require new techniques: Proposition 9 (Tightness of Proposition 8). For any constant C 0 > 0 and µ 0 ∈ (0, ℓ), there is some µ ∈ (0, µ 0 ) and polynomials q(z), r(z) so that sup ν∈[µ,ℓ] ρ(q(z) − ν · r(z)) < 1 − C 0 · µ. Moreover, the choice of the polynomials is given by The choice of polynomials q(z), r(z) in (9) are exactly the polynomials that arise in the p-SCLI analysis of Nesterov's AGD [ASSS15]; as we discuss further in Appendix C, Proposition 8 is tight, then, even for p = 2, because acceleration is possible with a 2-SCLI. As byproducts of our lower bound analysis, we additionally obtain the following: • Using Proposition 8, we show that any p-SCLI algorithm must have a rate of at least Ω A (1/T ) for smooth convex function minimization (again, with an algorithm-dependent constant). 9 This is slower than the O(1/T 2 ) error achievable with Nesterov's AGD with a time-varying learning rate.
• We give a direct proof of the following statement, which was conjectured by [ASSS15]: for polynomials q, r in the setting of Proposition 8, for any 0 . Using this statement, for the setting of Theorem 7, we give a proof of an algorithm-independent Though the algorithm-independent lower bound of Ω(ℓD 2 /T ) has already been established in the literature, even for non-stationary CLIs (e.g., [ASM + 20, Proposition 5]), we give an alternative proof from existing approaches.

Discussion
In this paper we proved tight last-iterate convergence rates for smooth monotone games when all players act according to the optimistic gradient algorithm, which is no-regret. We believe that there are many fruitful directions for future research. First, it would be interesting to obtain last-iterate rates in the case that each player's actions is constrained to the simplex and they use the optimistic multiplicative weights update (OMWU) algorithm. [DP18, LNPW20] showed that OMWU exhibits last-iterate convergence, but non-asymptotic rates remain unknown even for the case that F G (·) is linear, which includes finite-action polymatrix games. Next, it would be interesting to determine whether Theorem 5 holds if (2) is removed from Assumption 4; this problem is open even for the EG algorithm ([GPDO20]). Finally, it would be interesting to extend our results to the setting where players receive noisy gradients (i.e., the stochastic case). As for lower bounds, it would be interesting to determine whether an algorithm-independent lower bound of Ω(1/ √ T ) in the context of Theorem 7 could be proven for stationary p-SCLIs. As far as we are aware, this question is open even for convex minimization (where the rate would be Ω(1/T )).

A Additional preliminaries
A.1 Proof of Proposition 2 Proof of Proposition 2. Fix a game G, and let F = F G : Z → R n . Monoticity of F gives that for any fixed Summing the above for k ∈ K and using the definition of the total and gradient gap functions, as well as Cauch-Schwarz, gives that

A.2 Optimistic gradient algorithm
In this section we review some additional background about the optimistic gradient algorithm in the setting of no-regret learning. The starting point is online gradient descent; player k following online gradient descent produces iterates z k and the other players' actions z (t) −k at time t. Online gradient descent is a noregret algorithm (in particular, it satisfies the same regret bound as OG in Proposition 3); it is also closely related to the follow-the-regularized-leader (FTRL) ([SS11]) algorithm from online learning. 10 The optimistic gradient (OG) algorithm ([RS13, DISZ17]) is a modification of online gradient descent, for which player k performs the following update: where again g −k ) for t ≥ 0. As way of intuition behind the updates (OG), [DISZ17] observed that OG is closely related to the optimistic follow-the-regularized-leader (OFTRL) algorithm from online learning: OFTRL augments the standard FTRL update by using the gradient g (t) k at time t as a prediction for the gradient at time t + 1. When the actions z (t) −k of the other players are predictable in the sense that they do not change quickly over time, then such a prediction using g (t) k is reasonably accurate and can improve the speed of convergence to an equilibrium ([RS13]).

A.3 Linear regret for extragradient algorithm
In this section we review the definition of the extragradient (EG) algorithm, and show that if one attempts to implement it in the setting of online multi-agent learning, then it is not a no-regret algorithm. Given a monotone game G and its corresponding monotone operator F G : Z → R n and an initial point u (0) ∈ R n the EG algorithm attempts to find a Nash equilibrium z * (i.e., a point satisfying F G (z * ) = 0) by performing the updates: where Π Z (·) denotes Euclidean projection onto the convex set Z. Assuming Z contains a sufficiently large ball centered at z * , this projection step has no effect for the updates shown above when all players perform EG updates (see Remark 4); the projection is typically needed, however, for the adversarial setting that we proceed to discuss in this section (e.g., as in Proposition 3). It is easy to see that the updates (10) and (11) can be rewritten as −1) )))). Note that these updates are somewhat similar to those of OG when expressed as (23) and (24), with w (t) in (23) and (24) playing a similar role to u (t) in (10) and (11). A key difference is that the iterate u (t) is needed to update z (t) in (11), whereas this is not true for the update to z (t) in (23). Since in the standard setting of online multi-agent learning, agents can only see gradients corresponding to actions they play, in order to implement the above EG updates in this setting, we need two timesteps for every timestep of EG. In particular, the agents will play actions where v k . Unfortunately, as we show in Proposition 10 below, in the setting when the other players' actions z (t) −k are adversarial (i.e., players apart from k do not necessarily play according to EG), the algorithm for player k given by the EG updates (12) and (13) can have linear regret, i.e., is not a no-regret algorithm. Thus the EG algorithm is insufficient for answering our motivating question (⋆).
Proposition 10. There is a set Z = K k=1 Z k together with a convex, 1-Lipschitz, and 1-smooth function f 1 : Z → R so that for an adversarial choice of z (t) −k , the EG updates (12) and (13) produce a sequence v −k ) for any T > 0. Proof. We take K = 1, k = 1, n = 2, Z 1 = Z 2 = [−1, 1], and f 1 : Suppose that player 1 initializes at v It follows that for t ≥ 0 we have v 2 ) = 0 whereas the following two possible boundedness assumptions: where σ t > 0 and τ t > 0 are sequences of positive reals (typically taken to be decreasing with t). Often it is assumed that σ t is the same for all t, in which case we write σ = σ t . Noise model (Abs) is known as absolute random noise, and (Rel) is known as relative random noise [LZMJ20]. The latter is only of use in the unconstrained setting in which the goal is to find z * with F G (z * ) = 0. While we restrict Table 2 to 1st order methods, we refer the reader also to the recent work of [LBJM + 20], which provides last-iterate rates for stochastic Hamiltonian gradient descent, a 2nd order method, in "sufficiently bilinear" games.
As can be seen in Table 2, there is no work to date proving last-iterate rates for general smooth monotone games. We view the problem of extending the results of this paper and of [GPDO20] to the stochastic setting (i.e., the bottom row of Table 2) as an interesting direction for future work.  Table 1; ℓ, Λ are the Lipschitz constants of FG, ∂FG, respectively, and c > 0 is a sufficiently small absolute constant. The right-hand column contains algorithms implementable as online no-regret learning algorithms: stochastic optimistic gradient (Stoch. OG) or stochastic gradient descent (SGD). The left-hand column contains algorithms not implementable as no-regret algorithms, which includes stochastic extragradient (Stoch. EG), stochastic forward-backward (FB) splitting, double stepsize extragradient (DSEG), and stochastic variance reduced extragradient (SVRE). SVRE only applies in the finite-sum setting, which is a special case of (Abs) in which f k is a sum of m individual loss functions f k,i , and a noisy gradient is obtained as ∇f k,i for a random i ∈ [m]. Due to the stochasticity, many prior works make use of a step size ηt that decreases with t; we make note of whether this is the case ("ηt decr.") or whether the step size ηt can be constant ("ηt const."). For simplicity of presentation we assume Ω(1/t) ≤ {τt, σt} ≤ O(1) for all t ≥ 0 in all cases for which σt, τt vary with t. Reported bounds are stated for the total gap function (Definition 3); leading constants and factors depending on distance between initialization and optimum are omitted.

Stochastic Game class
Not implementable as no-regret Implementable as no-regret µ-strongly monotone  In this section we prove Theorem 5. In Section B.1 we show that OG exhibits best-iterate convergence, which is a simple consequence of prior work. In Section B.1 we begin to work towards the main contribution of this work, namely showing that best-iterate convergence implies last iterate convergence, treating the special case of linear monotone operators F (z) = Az. In Section B.3 we introduce the adaptive potential function for the case of general smooth monotone operators F , and finally in Section B.4, using this choice of adaptive potential function, we prove Theorem 5. Some minor lemmas used throughout the proof are deferred to Section B.5.

B.1 Best-iterate convergence
Throughout this section, fix a monotone game G satisfying Assumption 4, and write F = F G , so that F is a monotone operator (Definition 1). Recall that the OG algorithm with constant step size η > 0 is given by: In Lemma 11 we observe that some iterate z (t * ) of OG has small gradient gap.
In the remainder of this section we present our main technical contribution in the context of Theorem 5, showing that for a fixed T , the last iterate z (T ) does not have gradient gap F (z (T ) ) much larger than min 1≤t≤T max 0≤s≤2 F (z (t+s) ) .

B.2 Warm-up: different perspective on the linear case
Before treating the case where F is a general smooth monotone operator, we first explain our proof technique for the case that F (z) = Az for some matrix A ∈ R n×n . This case is covered by [LS18, Theorem 3] 11 ; the discussion here can be viewed as an alternative perspective on this prior work.
Assume that F (z) = Az for some A ∈ R n×n throughout this section. Let z (t) be the iterates of OG, and define Thus the updates of OG can be written as The extra-gradient (EG) algorithm is the same as the updates (19) where the square root of I + (2ηA) 2 may be defined via the power series It is easy to check that C is well-defined as long as η ≤ O(1/ℓ) ≤ O(1/ A σ ), and that CA = AC. Also note that C satisfies Finally setw (t) = w (t) + Cz (t−1) , so thatw (t) corresponds (under the PEG interpretation of OG) to the iterates w (t) of EG, plus an "adjustment" term, Cz (t) , which is O((ηA) 2 ). Though this adjustment term is small, it is crucial in the following calculation:w Since C, A commute, the above implies that F (w (t+1) ) = (I − ηA + C)F (w (t) ). Monotonicity of F implies that for η = O(1/ℓ), we have I − ηA + C σ ≤ 1. It then follows that F (w (t+1) ) ≤ F (w (t) ) , which establishes that the last iterate is the best iterate.

B.3 Setting up the adaptive potential function
We next extend the argument of the previous section to the smooth convex-concave case, which will allow us to prove Theorem 5 in its full generality. Recall the PEG formulation of OG introduced in the previous section: where again z (t) denote the iterates of OG (15). As discussed in Section 3.1, the adaptive potential function is given by F (t) , wherẽ for some matrices C (t) ∈ R n×n , −1 ≤ t ≤ T , to be chosen later. Then: where (Recall that ∂F (·) denotes the Jacobian of F .) We state the following lemma for later use: Proof. For all z ∈ R n , monotonicity of F gives that ∂F (z) + ∂F (z) ⊤ is PSD, which means that so are A (t) + (A (t) ) ⊤ , B (t) + (B (t) ) ⊤ . Similarly, (1) gives that for all z ∈ R n , ∂F (z) σ ≤ ℓ, from which we get A (t) σ ≤ ℓ, B (t) σ ≤ ℓ by the triangle inequality. The remaining three inequalities are an immediate consequence of the triangle inequality and the fact that ∂F is Λ-Lipschitz (Assumption 4). Now define the following n × n matrices: Moreover, for a positive semidefinite (PSD) matrix S ∈ R n×n and a vector v ∈ R n , write v 2 S := v ⊤ Sv, so that for a matrix M ∈ R n×n and a vector v ∈ R n , we have Then by (26), Next we define C (T ) = 0 and for −1 ≤ t < T , 12 Notice that the definition of C (t−1) in (28) depends on C (t) , which depends on C (t+1) , and so on. By (27) and (25), it follows that Our goal from here on is two-fold: (1) to prove an upper bound on I − ηA (t) + C (t) σ , which will ensure, by (30), that F (t+1) F (t) , and (2) to ensure that F (t) is an (approximate) upper bound on F (z (t) ) for all t, so that in particular upper bounding F (T ) suffices to upper bound F (z (T ) ) . These tasks will be performed in the following section; we first make a few remarks on the choice of C (t−1) in (28): Remark 6 (Specialization to the linear case & experiments). In the case that the monotone operator F is linear, i.e., F (z) = Az, it is straightforward to check that the matrices C (t−1) as defined in (28) are all equal to the matrix C defined in (21) and A (t) = B (t) = A for all t. A special case of a linear operator F is that corresponding to a two-player zero-sum matrix game, i.e., where the payoffs of the players given actions x, y, are ±x ⊤ My. In experiments we conducted for random instances of such matrix games, we observe that the adaptive potential functionF (t) closely tracks F (z (t) ), and both are monotonically decreasing with t. It seems that any "interesting" behavior whereby F (z (t) ) grows by (say) a constant factor over the course of one or more iterations, but whereF (t) grows only by much less, must occur for more complicated monotone operators (if at all). We leave a detailed experimental evaluation of such possibilities to future work.
Remark 7 (Alternative choice of C (t) ). It is not necessary to choose C (t−1) as in (28). Indeed, in light of the fact that it is the spectral norms I − ηA (t−1) + C (t−1) σ that control the increase in F (t−1) to F (t) , it is natural to try to set The reason for the constraint * defined in (32) is to ensure that F (t+1) 2 ≤ F (t) 2 (M (t) ) ⊤ M (t) (so that (29) is replaced with an inequality). The reason for the constraint C σ ≤ 1/10 is to ensure that F (z (T ) ) ≤ O F (T ) . Though the asymptotic rate of O(1/ √ T ) established by the choice of C (t−1) in (28) is tight in light of Theorem 7, it is possible that a choice of C (t−1) as in (31) could lead to an improvement in the absolute constant. We leave an exploration of this possibility to future work.

B.4 Proof of Theorem 5
In this section we prove Theorem 5 using the definition ofF (t) in (25), where C (t−1) is defined in (28). We begin with a few definitions: for positive semidefinie matrices S, T, write S T if T − S is positive semidefinite (this is known as the Loewner ordering). We also define To understand the definition of the matrices D (t) in (33), note that, in light of the equality for a square matrix X for which I − X is invertible, we have, for t ≤ T , Thus, to upper bound I − A (t−1) + C (t−1) , it will suffice to use the below lemma, which generalizes [GPDO20, Lemma 12] and can be used to give an upper bound on the spectral norm of I − ηA (t−1) + η 2 A (t) B (t) + D (t) for each t: Lemma 13. Suppose A 1 , A 2 , B, D ∈ R n×n are matrices and K, L 0 , L 1 , L 2 , δ > 0 so that: It follows that I − A 1 + A 2 B + D σ ≤ 1 + (K + 400) δ 2 .
Proof of Lemma 13. We wish to show that /2, so that R 1 , R 2 , S are positive semidefinite and J 1 , J 2 , K are anti-symmetric.

Lemma 15 uses backwards induction (on t) to establish bounds on the matrices C (t) .
Lemma 15 (Backwards induction lemma). Suppose that there is some L 0 > 0 so that for all t ≤ T , we have max{η A (t) σ , η B (t) σ } ≤ L 0 ≤ 1/200 and ηℓ ≤ 2/3. Then: 2. The matrices C (t) are well-defined, i.e., I − ηA (t) + C (t) is invertible for each t ∈ [T ], and the spectral norm of its inverse is bounded above by √ 2.
4. For all t < T , it holds that for J 1 = 8L 2 0 and J 2 = 30L 2 0 η 2 (ηΛ) 2 . Proof. The proof proceeds by backwards induction on t. The base case t = T clearly holds since C (T ) = 0. As for the inductive step, suppose that items 1 through 4 hold at time step t, for some t ≤ T . Then by (28) and L 0 ≤ √ 2−1 2 , establishing item 1 at time t − 1.
Next we establish items 4 and 5 at time t − 1. First, we have where the final inequality uses ηℓ ≤ 2/3.
Lemma 16. Suppose that the pre-conditions of Lemma 15 (namely, those in its first sentence) hold. Then for each t ∈ [T ], we have and Proof. By Lemma 17, for any ǫ > 0, Also, for any ǫ > 0, where (63)  Choosing ǫ = 3L 0 and using the definition of D (t) in (33), it follows from the above displays that which establishes (61).
Finally we are ready to prove Theorem 5; for convenience we restate it here.
• We calculate that holds as long as L 0 ≤ 1/150.
The conclusion of Theorem 5 is an immediate conclusion of item 2 at time T , since 4δ ≤ 5δ 0 = 60D η √ T .

B.5 Helpful lemmas
Lemma 17 (Young's inequality). For square matrices X, Y, we have, for any ǫ > 0, Applying the previous lemma to the cross terms in the quantity XX ⊤ when using the decomposition X = Y + (X − Y), we obtain the following.
Lemma 18. For square matrices X, Y, we have, for any ǫ > 0, In particular, choosing ǫ = 1 gives Lemma 19 is an immediate corollary of the two lemmas above: Lemma 19. For square matrices X, Y, we have Lemma 20. For square matrices X, Y such that Y σ ≤ M , we have Proof. For any v, we have YXv 2 ≤ M 2 Xv 2 .

C Proofs for Section 4
In this section we prove Theorem 7, and as byproducts of our analysis additionally prove the results mentioned at the end of Section 4. Recall from Section 4 that F bil n,ℓ,D is defined to be the set of ℓ-Lipschitz operators F : R n → R n of the form for which A is of full rank and −A −1 b ∈ D D := B R n/2 (0, D) × B R n/2 (0, D). Note that each F ∈ F bil n,ℓ,D can be written as the min-max gradient operator F (x, y) = (∇ x f (x, y) ⊤ , −∇ y f (x, y) ⊤ ) ⊤ corresponding to the function We next note that when F ∈ F bil n,ℓ,D , the p-SCLI updates of Definition 5 can be rewritten as follows: Observation 22. Suppose that A is a p-SCLI. Then there are constants α j , β j , γ, δ ∈ R, 0 ≤ j ≤ p − 1, depending only on A, so that for an instance F of the form F (z) = Az + b, and an arbitrary set of p initialization poitns z (0) , . . . , z (−p+1) ∈ R n , the iterates z (t) of A satisfy for t ≥ 1 and C j (A) = α j A + β j I n for 0 ≤ j ≤ p − 1 and N(A) = γA + δI n .
In the case of OG with a constant step size η, for F (z) = Az + b, we may rewrite (15) as All lower bounds we prove in this section will apply more generally to any iterative algorithm A whose updates are of the form (78) when restricted to instances F (z) = Az + b.
The remainder of this section is organized as follows. In Section C.1, we prove Theorem 7. In Section C.2 we prove Proposition 8, which is used in the proof of Theorem 7, and Proposition 9, showing that Proposition 8 is tight in a certain sense. In Section C.3 we prove a conjecture of [ASSS15], which is similar in spirit to Proposition 8 and leads to an algorithm-independent version of Theorem 7 (with a weaker quantitative bound). Finally, in Section C.4, we discuss another byproduct of our analysis, namely a lower bound for p-SCLIs for convex function minimization.
C.1 p-SCLI lower bounds for the class F bil n,ℓ,D Notation. For a square matrix A, let ρ(A) be its spectral radius, i.e., the maximum magnitude of an eigenvalue of A. For matrices A 1 ∈ R n1×m1 , A 2 ∈ R n2×m2 , let A 1 ⊗ A 2 ∈ R (n1n2)×(m1m2) be the tensor product (also known as Kronecker product) of A 1 , A 2 .
We will need the following standard lemma: Lemma 23. For a square matrix C and all k ∈ N, we have C k σ ≥ ρ(C) k .
Next we prove Theorem 7, restated below for convenience.
Theorem 7 (restated). Fix ℓ, D > 0, let A be a p-SCLI 14 , and let z (t) denote the tth iterate of A. Then there are constants c A , T A > 0 so that the following holds: For all T ≥ T A , there is some F ∈ F bil n,ℓ,D so that for some initialization z (0) , . . . , z (−p+1) ∈ D D and some T ′ ∈ {T, T + 1, . . . , T + p − 1}, it holds that TGap D2D Proof of Theorem 7. Take F (z) = Az + b, where A, b are of the form shown in (76), with M = ν · I for some ν ∈ (0, ℓ]. Notice that A therefore depends on the choice of ν (which will be specified later), but for simplicity of notation we do not explicitly write this dependence. The outline of the proof is to first eliminate some corner cases in which the iterates of A do not converge and then reduce the statement of Theorem 7 to that of Proposition 8. There are a few different ways to carry out this reduction: we follow the linear algebraic approach of [ASSS15], but an approach of a different flavor using elementary ideas from complex analysis is given in [Nev93, Section 3.7].
Since F ∈ F bil n,ℓ,D , we have that the equilibrium z * = (x * , y * ) ∈ D D satisfies B R n/2 (x * , D)×B R n/2 (y * , D) ⊂ D 2D . Then, from [GPDO20, Eq. (22)], it follows that TGap D2D F (z) ≥ D F (z) for any z ∈ R n . Therefore, to prove Theorem 7 it suffices to show the lower bound F (z (T ′ ) ) ≥ cAℓD √ T . We consider the dynamics of the iterates of A for various choices of z (0) , . . . , z (−p+1) ∈ D D . To do so, we define the block matrices: and the block vectors Then the updates of A as in (78) can be written in the following form, for F (z) = Az + b: Hence Recall that Observation 22 gives us C j (A) = α j · A + β j · I n , and N(A) = γ · A + δ · I n , for some real numbers α j , β j , γ, δ where 0 ≤ j ≤ p − 1.
We now consider several cases: is not invertible for some choice of ν ∈ (0, ℓ] (which determines A as explained above). First suppose that C(A) − I np is not invertible. Note that the row-space of C(A) − I np contains the row-space of the following matrix: If C 0 (A) + · · · + C p−1 (A) − I n is full-rank, then the row-space ofC additionally contains the row-space of I n 0 · · · 0 ∈ R n×np , and thusC, and so C(A)−I would be full-rank. Thus C 0 (A)+· · ·+C p−1 (A)−I n is not full-rank. But we can write: But since M is a nonzero multiple of the identity matrix, if the above matrix is not full-rank, it must be identically 0, i.e., p−1 j=0 C j (A) = I n . Hence p−1 j=0 β j = 1, p−1 j=0 α j = 0. Thus, for any choice of the matrix A ∈ R n×n , if we choose b = 0 (so that F (z) = Az), and if z (0) = · · · = z (−p+1) = z for some z ∈ R n , it holds that for all t ≥ 1, the iterates z (t) of Z satisfy z (t) = z. We now choose M = ℓ · I n/2 and z = z (0) = D/ n/2 · 1 ∈ R n , so that z (0) − A −1 b = z (0) ∈ D D . Then for all t ≥ 0, Similarly, if N(A) is not invertible for some choice of ν ∈ (0, ℓ], then by choice of A we must have that γ = δ = 0, i.e., N(A) = 0 for all choices of ν. Thus, choosing w (0) = 0 and b = D/ n/2 · 1 ∈ D D , and so for all t ≥ 0, F (z (t) ) = F (z (0) ) = b = √ 2D. Thus in this case we get the lower bound for T ≥ T A := ℓ 2 .
p−1 j=0 β j = 1. This case contains the case in which the iterates z (t) of the p-SCLI converge to the true solution −A −1 b for all A, b, and is thus the main nontrivial case (in particular, it is the case in which we use Proposition 8).

C.2 Proof of Propositions 8 and 9
In this section we prove Propositions 8 and 9.
We remark also that the case k ≥ 3 can be dealt with directly, without appealing to Theorem 25: again let w 0 = b(µ), so that (85) holds. Then there exists some kth root u 0 ∈ ∆ of w 0 so that a ′ (0) · u 0 = re iθ for some θ ∈ [−π/3, π/3] and r > 0. Then for sufficiently small u 0 (which can be made arbitrarily small by taking µ ↓ 0).
The polynomials in (86) are closely related to Nesterov's accelerated gradient descent (AGD); we discuss this connection further in Remark 8.
We are not aware of any reference in the literature directly claiming to prove the statement of Conjecture 24. However, we will show two distinct proofs of Conjecture 24: the first is an indirect proof showing how Conjecture 24 may be derived indirectly as a consequence of prior works ([Nev93, AS16]), and the second is a direct proof using basic principles from complex analysis.
Before continuing, we introduce some further notation.
Notation. For a polynomial s(z), write ρ(s) to be the spectral radius of s, i.e., ρ(s) = max{|z| : s(z) = 0} is the maximum magnitude of a root of s. LetĈ = C ∪ {∞} denote the Riemann sphere. For z ∈ C, r > 0, let D(z, r) := {w ∈ C : |w − z| < r} denote the (open) disk of radius r centered at z. Set ∆ = D(0, 1) and H := {z ∈ C : ℑ(z) > 0} to be the upper half-plane (here ℑ(z) denotes the imaginary part of z). We refer the reader to [Ahl79] for further background on complex analysis.
(We use Lemma 26 in (92).) Let S t denote the set of polynomials s t with complex coefficients of degree at most t such that s t (0) = 1. (Note in particular that the polynomials p t defined above belong to S t for each t.) It follows from Theorem 3.6.3, and Example 3. |s t (ν)| 1/t = ℓ/µ − 1 ℓ/µ + 1 .
(In more detail, the quantity on the left-hand-side of (93), which is called the optimal reduction factor of the region [µ, ℓ] in [Nev93] and denoted by η [µ,ℓ] therein, is shown in [Nev93, Theorem 3.6.3] to be equal to e −G(0) , where G : C − [µ, ℓ] → R is the Green's function for the region C − [µ, ℓ]. Then [Nev93, Example 3.8.3] explicitly computes the Green's function and shows that e −G(0) is the quantity on the right-hand-side of (93)).
The desired conclusion follows by taking ǫ ↓ 0, thus completing the proof of Theorem 25. We remark that an alternative approach to establishing (93) without appealing to the heavy machinery of Green's functions is to use [AS16, Lemma 2] directly, which shows that The approach to proving Conjecture 24 described above is unsatisfying in that it first passes a statement about polynomials (namely, Conjecture 24) to a statement about matrices (namely, about lim inf t sup ν∈[µ,ℓ] C(ν) t 1/t σ ), relying on a nontrivial uniform version of Gelfand's formula ([Koz09]), before passing back to a statement about polynomials and using either [AS16] or [Nev93] to establish (93). It is natural to wonder whether there is a direct proof of Conjecture 24 which operates on the polynomials q(z), r(z) directly, without bounding the optimal reduction factor in (93) and constructing the matrices C(ν). We next give such a direct proof of Conjecture 24, which follows from basic facts from complex analysis.
The conclusion of Proposition 29 is known even for non-stationary p-CLIs and without the superfluous 1/ √ p factor (e.g., it follows from Proposition 5 in [ASM + 20]), but our proof is new since it involves Theorem 25, which does not seem to have been previously known in the literature. We are hopeful that Theorem Define, for each t ≥ 0, . . .
We will choose S = ν · I n , for some ν ∈ (0, ℓ] to be chosen later. Thus f (x) − f (x * ) = 1 2ν Sx + b 2 . Next we proceed exactly as in the proof of Theorem 7, with S taking the role of A there. In particular, we define C(S) exactly as in (79), where C j (S) = α j · A + β j · I n , N(S) = γ · S + δ · I n , where α j , β j , γ, δ ∈ R are the constants associated with the p-SCLI A. Cases 1, 2, and 3a of the proof (namely, the ones in which the algorithm does not converge) proceed in exactly the same way and we omit the details.
Remark 8. As in Theorem 7, the lower bound in Proposition 30 involves an algorithm-dependent constant c A due to the reliance on Proposition 8. We remark that the iterates x (t) of gradient descent satisfy f (x (t) ) − f (x * ) ≤ O(ℓD 2 /T ) for any ℓ-smooth convex function f , so Proposition 8 is tight up to the algorithm-dependent constant c A . Nesterov's AGD improves the rate of gradient descent to O(ℓD 2 /T 2 ), but is non-stationary (i.e., requires a changing step size). The polynomials in Proposition 9 (i.e., (9)) showing the necessity of an algorithm-dependent constant in Proposition 8 correspond under the reduction outlined in the proof of Proposition 30 to running Nesterov's AGD with a fixed learning rate. We do not know if such an algorithm (for an appropriate choice of the arbitrary but fixed learning rate) can lead to an arbitrarily large constant factor speedup over the rate O(ℓD 2 /T ) of gradient descent. We believe this is an interesting direction for future work.