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

Introduction

However, the type of convergence guaranteed in these works generally either applies only to the time-average 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 fails to capture the game dynamics over time ([MPP17]), and both types of guarantees use newly acquired information with decreasing weight, which, as remarked by [LZMJ20], is very unnatural from an economic perspective. In fact, even in the adversarial setting, standard no-regret algorithms such as FTRL ([SS11]) need to be applied with decreasing step-size in order to achieve sublinear regret. Therefore, the following question is of particular interest ([MZ18, LZMJ20, MPP17, DISZ17]):

We measure the proximity of an action profile $\mathbf{z}=(\mathbf{z}_{1},\ldots,\mathbf{z}_{K})$ to equilibrium in terms of the total gap function at $\mathbf{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 $\mathbf{z}_{k}$. [LZMJ20] took initial steps toward addressing ( ⋆ ‣ 1), showing that if all agents follow the online gradient descent algorithm, then for all $\lambda$-cocoercive games, the action profiles $\mathbf{z}^{(t)}=(\mathbf{z}^{(t)}_{1},\ldots,\mathbf{z}^{(t)}_{K})$ will converge to equilibrium in terms of the total gap function at a rate of $O(1/\sqrt{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 $\lambda$-cocoercive games. Unfortunately, even $\lambda$-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.

In this paper we answer ( ⋆ ‣ 1) in the affirmative for all monotone games (Definition 1) satisfying a mild smoothness condition, which includes smooth $\lambda$-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 $\lambda$-cocoercive. Hence our paper is the first to prove last-iterate convergence in the sense of ( ⋆ ‣ 1) 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/\sqrt{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/\sqrt{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]), EG is also known as mirror-prox, which specifically refers to its generalization to general Bregman divergences. which, at each time step $t$, assumes each player $k$ has an oracle $\mathcal{O}_{k}$ which provides them with an additional gradient at a slightly different action than the action $\mathbf{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 $\mathcal{O}_{k}$, and using the even-numbered time steps to simulate the actions $\mathbf{z}^{(t)}_{k}$ that EG actually takes. Although this algorithm exhibits last-iterate convergence at a rate of $O(1/\sqrt{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 $\mathcal{O}_{k}$. Moreover, our upper bound of $O(1/\sqrt{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 $\mathbf{z}^{(t^{*})}$ of OG will have gradient gap $O(1/\sqrt{T})$ (see Definition 2; this is essentially a known result) and then showing that for all $t\geq 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.

2 Related work

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. In potential games, there is a canonical choice of potential function whose local minima are equivalent to being at a Nash equilibrium. The lack of existence of a natural potential function in general monotone games is a significant challenge in establishing last-iterate convergence.

Such potential games are in general incomparable with monotone games, and do not even include finite-state 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 ( ⋆ ‣ 1).

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. Technically, the result of [Pop80] only applies to two-player zero-sum monotone games (i.e., finding the saddle point of a convex-concave function). The proof readily extends to general monotone VIs ([HIMM19]). 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 multiplicative-weights 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

A Nash equilibrium in the game $\mathcal{G}$ is an action profile $\mathbf{z}^{*}\in\mathcal{Z}$ so that for each player $k$, it holds that $f_{k}(\mathbf{z}^{*}_{k},\mathbf{z}_{-k}^{*})\leq f_{k}(\mathbf{z}_{k}^{\prime},\mathbf{z}_{-k}^{*})$ for any $\mathbf{z}_{k}^{\prime}\in\mathcal{Z}_{k}$. Throughout this paper we study monotone games:

The game $\mathcal{G}=(\mathcal{K},(\mathcal{Z}_{k})_{k=1}^{K},(f_{k})_{k=1}^{K})$ is monotone if for all $\mathbf{z},\mathbf{z}^{\prime}\in\mathcal{Z}$, it holds that $\langle F_{\mathcal{G}}(\mathbf{z}^{\prime})-F_{\mathcal{G}}(\mathbf{z}),\mathbf{z}^{\prime}-\mathbf{z}\rangle\geq 0$. In such a case, we say also that $F_{\mathcal{G}}$ is a monotone operator.

The following classical result characterizes the Nash equilibria in monotone games:

In the unconstrained setting, if the game $\mathcal{G}$ is monotone, any Nash equilibrium $\mathbf{z}^{*}$ satisfies $F_{\mathcal{G}}(\mathbf{z}^{*})={\mathbf{0}}$. Conversely, if $F_{\mathcal{G}}(\mathbf{z})={\mathbf{0}}$, then $\mathbf{z}$ is a Nash equilibrium.

In accordance with Proposition 1, one measure of the proximity to equilibrium of some $\mathbf{z}\in\mathcal{Z}$ is the norm of $F_{\mathcal{G}}(\mathbf{z})$:

Given a monotone game $\mathcal{G}$ with its associated operator $F_{\mathcal{G}}$, the gradient gap function evaluated at $\mathbf{z}$ is defined to be $\|F_{\mathcal{G}}(\mathbf{z})\|$.

It is also common ([MOP19a, Nem04]) to measure the distance from equilibrium of some $\mathbf{z}\in\mathcal{Z}$ by adding the maximum decrease in cost that each player could achieve by deviating from their current action $\mathbf{z}_{k}$:

Given a monotone game $\mathcal{G}=(\mathcal{K},(\mathcal{Z}_{k})_{k=1}^{K},(f_{k})_{k=1}^{K})$, compact subsets $\mathcal{Z}_{k}^{\prime}\subseteq\mathcal{Z}_{k}$ for each $k\in\mathcal{K}$, and a point $\mathbf{z}\in\mathcal{Z}$, define the total gap function at $\mathbf{z}$ with respect to the set $\mathcal{Z}^{\prime}:=\prod_{k=1}^{K}\mathcal{Z}_{k}^{\prime}$ by $\Gap_{\mathcal{G}}^{\mathcal{Z}^{\prime}}(\mathbf{z}):=\sum_{k=1}^{K}\left(f_{k}(\mathbf{z})-\min_{\mathbf{z}_{k}^{\prime}\in\mathcal{Z}_{k}^{\prime}}f_{k}(\mathbf{z}_{k}^{\prime},\mathbf{z}_{-k})\right).$ At times we will slightly abuse notation, and for $F:=F_{\mathcal{G}}$, write $\Gap_{F}^{\mathcal{Z}^{\prime}}$ in place of $\Gap_{\mathcal{G}}^{\mathcal{Z}^{\prime}}$.

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 $\mathcal{Z}_{k}$, which necessitates defining the total gap function in Definition 3 with respect to the compact subsets $\mathcal{Z}_{k}^{\prime}$. We discuss in Remark 4 how, in our setting, it is without loss of generality to shrink $\mathcal{Z}_{k}$ so that $\mathcal{Z}_{k}=\mathcal{Z}_{k}^{\prime}$ for each $k$. Proposition 2 below shows that in monotone games, the gradient gap function upper bounds the total gap function:

Suppose $\mathcal{G}=(\mathcal{K},(\mathcal{Z}_{k})_{k=1}^{K},(f_{k})_{k=1}^{K})$ is a monotone game, and compact subsets $\mathcal{Z}_{k}^{\prime}\subset\mathcal{Z}_{k}$ are given, where the diameter of each $\mathcal{Z}_{k}^{\prime}$ 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 $\mathcal{G}=(\{1,2\},(\mathcal{Z}_{1},\mathcal{Z}_{2}),(f_{1},f_{2}))$ we must have $f_{1}=-f_{2}$, it is straightforward to show that $f_{1}(\mathbf{z}_{1},\mathbf{z}_{2})$ is convex in $\mathbf{z}_{1}$ and concave in $\mathbf{z}_{2}$. Moreover, it is immediate that Nash equilibria of the game $\mathcal{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:

where $\mathbf{g}^{(t)}_{k}=\nabla_{\mathbf{z}_{k}}f_{k}(\mathbf{z}^{(t)}_{k},\mathbf{z}^{(t)}_{-k})$ for $t\geq 0$. The following essentially optimal regret bound is well-known for the OG algorithm, when the actions of the other players $\mathbf{z}^{(t)}_{-k}$ (often referred to as the environment’s actions) are adversarial:

Assume that for all $\mathbf{z}_{-k}$ the function $\mathbf{z}_{k}\mapsto f_{k}(\mathbf{z}_{k},\mathbf{z}_{-k})$ is convex. Then the regret of OG with learning rate $\eta_{t}=O(D/L\sqrt{t})$ is $O(DL\sqrt{T})$, where $L=\max_{t}\|\mathbf{g}^{(t)}_{k}\|$ and $D=\max\{\|\mathbf{z}_{k}^{*}\|,\max_{t}\|\mathbf{z}^{(t)}_{k}\|\}$.

Last-iterate rates for OG via adaptive potential functions

Condition (1) is entirely standard in the setting of solving monotone variational inequalities ([Nem04]); condition (2) is also very mild, being made for essentially all second-order methods (e.g., [ALW19, Nes06]).

By the definition of $F_{\mathcal{G}}(\cdot)$, when all players in a game $\mathcal{G}$ act according to (OG) with constant step size $\eta$, then the action profile $\mathbf{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/\sqrt{T})$ to a Nash equilibrium with respect to the gradient gap function:

By Proposition 2, we immediately get a bound on the total gap function at each time $T$:

In the setting of Theorem 5, let $\mathcal{Z}_{k}^{\prime}:=\mathcal{B}(\mathbf{z}_{k}^{(0)},3D)$ for each $k\in\mathcal{K}$. Then, with $\mathcal{Z}^{\prime}=\prod_{k\in\mathcal{K}}\mathcal{Z}_{k}^{\prime}$,

We made no attempt to optimize the consants in Theorem 5 and Corollary 6, and they can almost certainly be improved.

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 ( ⋆ ‣ 1) 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\geq 0$, $\|\mathbf{z}^{(t)}-\mathbf{z}^{*}\|\leq 2\|\mathbf{z}^{(0)}-\mathbf{z}^{*}\|$. Therefore, as long as we make the very mild assumption of a known a priori upper bound $\|\mathbf{z}^{*}\|\leq D/2$ (as well as $\|\mathbf{z}^{(-1)}_{k}\|\leq D/2$, $\|\mathbf{z}^{(0)}_{k}\|\leq D/2$), if all players act according to (3), then the updates (3) remain unchanged if we project onto the constraint sets $\mathcal{Z}_{k}:=\mathcal{B}({\mathbf{0}},3D)$ at each time step $t$. This observation also serves as motivation for the compact sets $\mathcal{Z}_{k}^{\prime}$ used in Corollary 6: the natural choice for $\mathcal{Z}_{k}^{\prime}$ is $\mathcal{Z}_{k}$ itself, and by restricting $\mathcal{Z}_{k}$ to be compact, this choice becomes possible.

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\leq t\leq T}\|F_{\mathcal{G}}(\mathbf{z}^{(t)})\|\leq O(1/\sqrt{T})$. In this discussion we view $\eta,D$ as constants. The main contribution of our proof is then to show the following: if we choose $t^{*}$ so that $\|F_{\mathcal{G}}(\mathbf{z}^{(t^{*})})\|\leq O(1/\sqrt{T})$, then for all $t^{\prime}\geq t^{*}$, we have $\|F_{\mathcal{G}}(\mathbf{z}^{(t^{\prime})})\|\leq O(1)\cdot\|F_{\mathcal{G}}(\mathbf{z}^{(t^{*})})\|$. 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_{\mathcal{G}}(\mathbf{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, $\mathbf{z}^{(t+1)}$ depends only on $\mathbf{z}^{(t)}$. For the OG algorithm, it is possible that (6) fails to hold, even when $F_{\mathcal{G}}(\mathbf{z}^{(t)})$ is replaced by the more natural choice of $(F_{\mathcal{G}}(\mathbf{z}^{(t)}),F_{\mathcal{G}}(\mathbf{z}^{(t-1)}))$. For a trivial example, suppose that $n=1$, $F_{\mathcal{G}}(\mathbf{z})=\mathbf{z}$, $\mathbf{z}^{(t^{\prime})}=\delta>0$, and $\mathbf{z}^{(t^{\prime}-1)}=0$. Then $\|(F_{\mathcal{G}}(\mathbf{z}^{(t^{\prime})}),F_{\mathcal{G}}(\mathbf{z}^{(t^{\prime}-1)}))\|=\delta$ but $\|(F_{\mathcal{G}}(\mathbf{z}^{(t^{\prime}+1)}),F_{\mathcal{G}}(\mathbf{z}^{(t^{\prime})}))\|>\delta\sqrt{2-4\eta}$.

In general, a potential function $\Phi(F_{\mathcal{G}},\mathbf{z})$ depends on the problem instance, here taken to be $F_{\mathcal{G}}$, and an element $\mathbf{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 $\Phi(F_{\mathcal{G}},\mathbf{z}^{(t+1)})\lesssim\Phi(F_{\mathcal{G}},\mathbf{z}^{(t)})$. For example, for the iterates $\mathbf{z}^{(t)}$ of the EG algorithm, [GPDO20] (see (6)) used the potential function $\Phi(F_{\mathcal{G}},\mathbf{z}^{(t)}):=\|F_{\mathcal{G}}(\mathbf{z}^{(t)})\|$.

Lower bound for convergence of pp-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 $\mathbf{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 iterates $\bar{\mathbf{z}}^{(T)}:=\frac{1}{T}\sum_{t=1}^{T}\mathbf{z}^{(t)}$ of OG satisfy $\Gap_{\mathcal{G}}^{\mathcal{Z}^{\prime}}(\bar{\mathbf{z}}^{(T)})\leq O\left(\frac{D^{2}}{\eta T}\right)$ [MOP19a, 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$.

From (3) it is evident that OG with constant step size $\eta$ is a 2-SCLI with $\beta_{1}=1,\beta_{0}=0,\alpha_{1}=-2\eta,\alpha_{0}=\eta$. Many standard algorithms for convex function minimization, including gradient descent, Nesterov’s accelerated gradient descent (AGD), and Pólya’s Heavy Ball method, are of the form (8) as well. We additionally remark that several variants of SCLIs (and their non-stationary counterpart, CLIs) have been considered in recent papers proving lower bounds for min-max optimization ([AMLJG19, IAGM19, ASM+20]).

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 $\Gap_{\mathcal{G}}^{\mathcal{D}_{D}}(\mathbf{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 $\mathcal{A}$). Recall that for a polynomial $p(z)$, its spectral norm $\rho(p(z))$ is the maximum norm of any root. We show:

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_{\mathcal{A}},T_{\mathcal{A}}$ in Theorem 7 depend on $\mathcal{A}$. Moreover, we remark that this dependence cannot be improved from Proposition 8, so removing it from Theorem 7 will require new techniques:

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 $\Omega_{\mathcal{A}}(1/T)$ for smooth convex function minimization (again, with an algorithm-dependent constant). [AS16] claimed to prove a similar lower bound for stationary algorithms in the setting of smooth convex function minimization; however, as we discuss in Appendix C, their results only apply to the strongly convex case, where they show a linear lower bound. This is slower than the $O(1/T^{2})$ error achievable with Nesterov’s AGD with a time-varying learning rate.

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_{\mathcal{G}}(\cdot)$ 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 $\Omega(1/\sqrt{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 $\Omega(1/T)$).

Acknowledgements

We thank Yossi Arjevani for a helpful conversation.

References

Appendix A Additional preliminaries

Since $f_{k}$ is continuously differentiable, [Nes75, Theorem 2.1.3] gives that $f_{k}$ is convex. Thus

Summing the above for $k\in\mathcal{K}$ and using the definition of the total and gradient gap functions, as well as Cauch-Schwarz, gives that $\Gap_{\mathcal{G}}^{\mathcal{Z}^{\prime}}(\mathbf{z})\leq D\cdot\sum_{k=1}^{K}\|\nabla_{\mathbf{z}_{k}}f_{k}(\mathbf{z})\|\leq D\sqrt{K}\|F(\mathbf{z})\|$. ∎

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 $\mathbf{z}^{(t)}_{k}\in\mathcal{Z}_{k}$ defined by $\mathbf{z}^{(t+1)}_{k}=\mathbf{z}^{(t)}_{k}-\eta_{t}\mathbf{g}^{(t)}_{k}$, where $\mathbf{g}^{(t)}_{k}=\nabla_{\mathbf{z}_{k}}f_{k}(\mathbf{z}^{(t)}_{k},\mathbf{z}^{(t)}_{-k})$ is player $k$’s gradient given its action $\mathbf{z}^{(t)}_{k}$ and the other players’ actions $\mathbf{z}^{(t)}_{-k}$ at time $t$. Online gradient descent is a no-regret 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. In particular, they are equivalent in the unconstrained setting when the learning rate $\eta_{t}$ is constant.

The optimistic gradient (OG) algorithm ([RS13, DISZ17]) is a modification of online gradient descent, for which player $k$ performs the following update:

where again $\mathbf{g}^{(t)}_{k}=\nabla_{\mathbf{z}_{k}}f_{k}(\mathbf{z}^{(t)}_{k},\mathbf{z}^{(t)}_{-k})$ for $t\geq 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 $\mathbf{g}^{(t)}_{k}$ at time $t$ as a prediction for the gradient at time $t+1$. When the actions $\mathbf{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 $\mathbf{g}^{(t)}_{k}$ is reasonably accurate and can improve the speed of convergence to an equilibrium ([RS13]).

A.3 Linear regret for extragradient algorithm

where $\Pi_{\mathcal{Z}}(\cdot)$ denotes Euclidean projection onto the convex set $\mathcal{Z}$. Assuming $\mathcal{Z}$ contains a sufficiently large ball centered at $\mathbf{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 $\mathbf{u}^{(t)}=\Pi_{\mathcal{Z}}(\mathbf{u}^{(t-1)}-\eta F_{\mathcal{G}}(\Pi_{\mathcal{Z}}(\mathbf{u}^{(t-1)}-\eta F_{\mathcal{G}}(\mathbf{u}^{(t-1)}))))$. Note that these updates are somewhat similar to those of OG when expressed as (23) and (24), with $\mathbf{w}^{(t)}$ in (23) and (24) playing a similar role to $\mathbf{u}^{(t)}$ in (10) and (11). A key difference is that the iterate $\mathbf{u}^{(t)}$ is needed to update $\mathbf{z}^{(t)}$ in (11), whereas this is not true for the update to $\mathbf{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 $\mathbf{v}^{(t)}$, $t\geq 0$, where $\mathbf{v}^{(2t)}=\mathbf{u}^{(t)}$ and $\mathbf{v}^{(2t+1)}=\mathbf{z}^{(t)}$ for all $t\geq 0$. Recalling that $F_{\mathcal{G}}(\mathbf{z})=(\nabla_{\mathbf{z}_{1}}f_{1}(\mathbf{z}),\ldots,\nabla_{\mathbf{z}_{K}}f_{K}(\mathbf{z}))$, this means that player $k\in[K]$ performs the updates

where $\mathbf{v}^{(0)}_{k}=\mathbf{u}^{(0)}_{k}$. Unfortunately, as we show in Proposition 10 below, in the setting when the other players’ actions $\mathbf{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 ( ⋆ ‣ 1).

Suppose that player 1 initializes at $\mathbf{v}^{(0)}_{1}=0$. Then for all $t\geq 0$, we have

It follows that for $t\geq 0$ we have $\mathbf{v}_{1}^{(2t)}=0$ and $\mathbf{v}_{1}^{(2t+1)}=\max\{-\eta,-1\}$. Hence for any $T\geq 0$ we have $\sum_{t=0}^{T-1}f_{1}(\mathbf{v}_{1}^{(t)},\mathbf{v}_{2}^{(t)})=0$ whereas

(with the optimal point $\mathbf{v}_{1}$ being $\mathbf{v}_{1}^{*}=-1$) so the regret is $\lceil T/2\rceil$. ∎

A.4 Prior work on last-iterate rates for noisy feedback

In this section we present Table 2, which exhibits existing last-iterate convergence rates for gradient-based learning algorithms in the case of noisy gradient feedback (i.e., it is an analogue of Table 1 for noisy feedback, leading to stochastic algorithms). We briefly review the setting of noisy feedback: at each time step $t$, each player $k$ plays an action $\mathbf{z}_{k}^{(t)}$, and receives the feedback

where $\mathcal{F}=(\mathcal{F}^{(t)})_{t\geq 0}$ is the filtration given by the sequence of $\sigma$-algebras $\mathcal{F}^{(t)}:=\sigma(\mathbf{z}^{(0)},\mathbf{z}^{(1)},\ldots,\mathbf{z}^{(t)})$ generated by $\mathbf{z}^{(0)},\ldots,\mathbf{z}^{(t)}$. Additionally, it is required that the variance of $\xi_{k}^{(t)}$ be bounded; we focus on the following two possible boundedness assumptions:

where $\sigma_{t}>0$ and $\tau_{t}>0$ are sequences of positive reals (typically taken to be decreasing with $t$). Often it is assumed that $\sigma_{t}$ is the same for all $t$, in which case we write $\sigma=\sigma_{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 $\mathbf{z}^{*}$ with $F_{\mathcal{G}}(\mathbf{z}^{*})={\mathbf{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.

Appendix B Proofs for Section 3

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(\mathbf{z})=\mathbf{A}\mathbf{z}$. 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.

Throughout this section, fix a monotone game $\mathcal{G}$ satisfying Assumption 4, and write $F=F_{\mathcal{G}}$, so that $F$ is a monotone operator (Definition 1). Recall that the OG algorithm with constant step size $\eta>0$ is given by:

In Lemma 11 we observe that some iterate $\mathbf{z}^{(t^{*})}$ of OG has small gradient gap.

More generally, we have, for any $S\geq 0$ with $S<T/3$,

Choosing $\mathbf{z}=\mathbf{z}^{*}$, using that $\langle F(\mathbf{z}^{(t)}),\mathbf{z}^{(t)}-\mathbf{z}^{*}\rangle\geq 0$, and applying Young’s inequality gives that for $t\geq 1$,

Summing the above equation for $1\leq t\leq T-1$ gives

The desired result (16) follows by substituting $T+1$ for $T$.

To obtain (17), we break $\{0,1,\ldots,T-2\}$ into $\lfloor(T-1)/S\rfloor$ windows of $S$ consecutive time steps each. Then there must be some $t\in\{0,\ldots,T-2-(S-1)\}$ so that

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 $\mathbf{z}^{(T)}$ does not have gradient gap $\|F(\mathbf{z}^{(T)})\|$ much larger than $\min_{1\leq t\leq T}\max_{0\leq s\leq 2}\|F(\mathbf{z}^{(t+s)})\|$.

B.2 Warm-up: different perspective on the linear case

The extra-gradient (EG) algorithm is the same as the updates (19), (20), except that in (19), $F(\mathbf{z}^{(t-1)})$ is replaced with $F(\mathbf{w}_{t})$. As such, OG in this context is often referred to as past extragradient (PEG) [HIMM19]. Many other works have also made use of this interpretation of OG, e.g., [RS12, RS13, Pop80].

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 $\mathbf{z}^{(t)}$ denote the iterates of OG (15).

(Recall that $\partial F(\cdot)$ denotes the Jacobian of $F$.) We state the following lemma for later use:

The remaining three inequalities are an immediate consequence of the triangle inequality and the fact that $\partial F$ is $\Lambda$-Lipschitz (Assumption 4). ∎

Now define the following $n\times n$ matrices:

Next we define $\mathbf{C}^{(T)}={\mathbf{0}}$ and for $-1\leq t<T$, The invertibility of $\mathbf{M}^{(t)}$, and thus the well-definedness of $\mathbf{C}^{(t-1)}$, is established in Lemma 15.

Notice that the definition of $\mathbf{C}^{(t-1)}$ in (28) depends on $\mathbf{C}^{(t)}$, which depends on $\mathbf{C}^{(t+1)}$, and so on. By (27) and (25), it follows that

B.4 Proof of Theorem 5

To understand the definition of the matrices $\mathbf{D}^{(t)}$ in (33), note that, in light of the equality

for a square matrix $\mathbf{X}$ for which $I-\mathbf{X}$ is invertible, we have, for $t\leq T$,

Thus, to upper bound $\|I-\mathbf{A}^{(t-1)}+\mathbf{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-\eta\mathbf{A}^{(t-1)}+\eta^{2}\mathbf{A}^{(t)}\mathbf{B}^{(t)}+\mathbf{D}^{(t)}$ for each $t$:

$\mathbf{A}_{1}+\mathbf{A}_{2}^{\top}$, $\mathbf{A}_{2}+\mathbf{A}_{2}^{\top}$, and $\mathbf{B}+\mathbf{B}^{\top}$ are PSD;

$\|\mathbf{A}_{1}\|_{\sigma},\|\mathbf{A}_{2}\|_{\sigma},\|\mathbf{B}\|_{\sigma}\leq L_{0}\leq 1/106$;

$\mathbf{D}+\mathbf{D}^{\top}\preceq L_{1}\cdot\left(\mathbf{B}^{\top}\mathbf{B}+\mathbf{A}_{1}\mathbf{A}_{1}^{\top}\right)+K\delta^{2}\cdot I$.

$\mathbf{D}^{\top}\mathbf{D}\preceq L_{2}\cdot\mathbf{B}^{\top}\mathbf{B}$.

$10L_{0}+\frac{4L_{2}}{L_{0}^{2}}+5L_{1}\leq 24/50$.

For any two matrices $\mathbf{X},\mathbf{Y}\in\{\mathbf{A}_{1},\mathbf{A}_{2},\mathbf{B}\}$, $\|\mathbf{X}-\mathbf{Y}\|_{\sigma}\leq\delta$.

For $i\in\{1,2\}$, let us write $\mathbf{J}_{i}=(\mathbf{A}_{i}-\mathbf{A}_{i}^{\top})/2,\mathbf{R}_{i}=(\mathbf{A}_{i}+\mathbf{A}_{i}^{\top})/2$, and $\mathbf{K}=(\mathbf{B}-\mathbf{B}^{\top})/2,\mathbf{S}=(\mathbf{B}+\mathbf{B}^{\top})/2$, so that $\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{S}$ are positive semidefinite and $\mathbf{J}_{1},\mathbf{J}_{2},\mathbf{K}$ are anti-symmetric.

Next we will show (in (42) below) that the sum of all terms in (36) apart from the first four are preceded by a constant (depending on $L_{0},L_{1}$) times $\mathbf{B}^{\top}\mathbf{B}$ in the Loewner ordering. To show this we begin as follows: for any $\epsilon,\epsilon_{1}>0$, we have:

Note in particular that (37), (38), and (39) imply that

and choosing $\epsilon=L_{0}\leq 1$ (whereas $\epsilon_{1}$ is left as a free parameter to be specified below) gives

where the last line results from the choice $\epsilon=L_{0}^{2},\epsilon_{1}=L_{0}$.

By (40) and (41) we have, for any $\epsilon_{1}>0$,

Next, for any $\epsilon>0$, it holds that

By (43) and (44), for any $\mu,\nu\in(0,1)$ and $\epsilon>0$ with $2\nu+10\epsilon+\mu\cdot(2+2\epsilon)\leq 1$,

where (B.4) follows from Lemma 17, (46) follows from Lemma 18 and $\nu+5\epsilon\leq 1$, (47) follows from $2\nu+10\epsilon+\mu\cdot(2+2\epsilon)\leq 1$, (48) follows from $\|\mathbf{J}_{2}-\mathbf{K}\|_{\sigma}\leq\delta$ as well as Lemma 18, and (49) follows from Lemma 20 together with $\|\mathbf{R}_{1}^{1/2}\|_{\sigma}\leq\sqrt{L_{0}}$.

By (42) and (49), by choosing $\epsilon_{1}=1/100,\epsilon=1/20$, $\nu=5L_{0}+\epsilon_{1}+\frac{2L_{2}}{L_{0}^{2}}+L_{1}$, and $\mu=L_{1}$, which satisfy

it holds that for the above choices of $\epsilon,\epsilon_{1}$,

The next several lemmas ensure that the matrices $\mathbf{D}^{(t)}$ satisfy the conditions of the matrix $\mathbf{D}$ of Lemma 13. First, Lemma 14 shows that $\|F(\mathbf{z}^{(t)})\|$ only grows by a constant factor over the course of a constant number of time steps.

for each $s\geq 1$, and so if $\delta_{s}:=\max\{\|F(\mathbf{z}^{(t+s-1)})\|,\|F(\mathbf{z}^{(t+s-2)})\|\}$, the triangle inequality gives

Lemma 15 uses backwards induction (on $t$) to establish bounds on the matrices $\mathbf{C}^{(t)}$.

$\|\mathbf{C}^{(t)}\|_{\sigma}\leq 2L_{0}^{2}$ for each $t\in[T]$.

The matrices $\mathbf{C}^{(t)}$ are well-defined, i.e., $I-\eta\mathbf{A}^{(t)}+\mathbf{C}^{(t)}$ is invertible for each $t\in[T]$, and the spectral norm of its inverse is bounded above by $\sqrt{2}$.

$\|\eta\mathbf{A}^{(t)}-\mathbf{C}^{(t)}\|_{\sigma}\leq 2L_{0}$ and $\|I-\eta\mathbf{A}^{(t)}+\mathbf{C}^{(t)}\|_{\sigma}\leq 1+2L_{0}$ for each $t\in[T]$.

Let $\delta^{(t)}:=\max\{\|F(\mathbf{z}^{(t)})\|,\|F(\mathbf{z}^{(t-1)})\|\}$ for all $t\leq T$. For $t<T$, it holds that

for $J_{1}=8L_{0}^{2}$ and $J_{2}=30L_{0}^{2}\eta^{2}(\eta\Lambda)^{2}$.

The proof proceeds by backwards induction on $t$. The base case $t=T$ clearly holds since $\mathbf{C}^{(T)}=0$. As for the inductive step, suppose that items 1 through 4 hold at time step $t$, for some $t\leq T$. Then by (28) and $L_{0}\leq\frac{\sqrt{2}-1}{2}$,

Next, note that $\|\eta\mathbf{A}^{(t-1)}-\mathbf{C}^{(t-1)}\|\leq L_{0}+2L_{0}^{2}\leq 2L_{0}$. Thus, by Equation (5.8.2) of [HJ12] and $L_{0}\leq\frac{1}{2}-\frac{1}{2\sqrt{2}}$, it follows that

which establishes item 2 at time $t-1$. It is also immediate that $\|I-\eta\mathbf{A}^{(t-1)}+\mathbf{C}^{(t-1)}\|_{\sigma}\leq 1+2L_{0}$, establishing item 3 at time $t-1$.

Next we establish items 4 and 5 at time $t-1$. First, we have

Next, by definition of $\mathbf{C}^{(t-1)}$ in (28),

(52) is by Lemma 21 with $\mathbf{X}=\eta\mathbf{A}^{(t)}-\mathbf{C}^{(t)}$;

(53) uses Lemma 17 and item 3 at time $t$;

(54) follows from $L_{0}\leq\frac{1-\sqrt{2/3}}{2}$;

(55) follows from the inductive hypothesis that item 5 holds at time $t$;

Inequalities (51) through (54) establish item 4 at time $t-1$. In order for item 5 to hold at time $t-1$, we need that

By choosing $J_{1}=8L_{0}^{2}$ we satisfy (59) since $L_{0}<\sqrt{1/24}$. By choosing $J_{2}=30L_{0}^{2}\eta^{2}(\eta\Lambda)^{2}$ we satisfy (60) since

Suppose that the pre-conditions of Lemma 15 (namely, those in its first sentence) hold. Then for each $t\in[T]$, we have

where (63) uses Lemma 17, (64) uses item 3 of Lemma 15 and Lemma 20, and (65) uses item 4 of Lemma 15.

Choosing $\epsilon=3L_{0}$ and using the definition of $\mathbf{D}^{(t)}$ in (33), it follows from the above displays that

Finally we are ready to prove Theorem 5; for convenience we restate it here.

By Lemma 11 with $S=3$, we have that for some $t^{*}\in\{0,1,2,\ldots,T\}$,

Write $\delta:=\delta_{0}(1+2L_{0})$. By (30), we have that for any $t\in\{t^{*},\ldots,T\}$,

We will prove by forwards induction (contrast with Lemma 15) that for each $t\in\{t^{*}-1,\ldots,T\}$, the following hold:

$\max\{\|F(\mathbf{z}^{(t)})\|,\|F(\mathbf{z}^{(t-1)})\|\}\leq 4\delta$.

$\|I-\eta\mathbf{A}^{(t)}+\mathbf{C}^{(t)}\|_{\sigma}^{2}\leq 1+10025\Lambda_{0}^{2}\eta^{2}\delta^{2}$ if $t\geq t^{*}$.

where the last inequality holds since $8L_{0}^{2}+4L_{0}\leq 2$.

We proceed to the proof of item 1 at time $t$. By Lemma 12, we have that

For $\mathbf{X}\in\{\eta\mathbf{A}^{(t)},\eta\mathbf{A}^{(t+1)},\eta\mathbf{B}^{(t+1)}\}$, $\mathbf{X}+\mathbf{X}^{\top}$ is PSD by Lemma 12.

We may bound $\mathbf{D}^{(t+1)}+(\mathbf{D}^{(t+1)})^{\top}$ as follows:

where (73) follows from Lemma 16, (74) follows from item 5 of Lemma 15 and item 2 of the current induction at time $t$, and (75) follows from Lemma 18 and (70). This shows that in our application of Lemma 13 we may take $L_{1}=12L_{0}$. Moreover, as we will take the parameter $\delta$ in Lemma 13 to be $5\Lambda_{0}\eta\delta$ (see below items), we may take $K=14L_{0}$ (since $14\cdot(5\Lambda_{0}\eta\delta)^{2}\geq 310\delta^{2}\eta^{2}\Lambda_{0}^{2}$).

so we may take $L_{2}=60L_{0}^{4}$ in our application of Lemma 13.

By (70), (71), and (72), we may take the parameter $\delta$ in Lemma 13 to be equal to $5\Lambda_{0}\eta\delta$ since $\max\{8\Lambda_{0}L_{0}\delta,4\delta\Lambda_{0}+12\delta\Lambda_{0}L_{0},4\delta\Lambda_{0}+20\delta\Lambda_{0}L_{0}\}\leq 5\Lambda_{0}\delta$.

which establishes that item 3 holds at time $t$.

Finally we show that item 1 holds at time $t$. To do so, we use (69) and the fact that $\delta^{2}\leq\frac{146D^{2}}{\eta^{2}T}$ to conclude that

where $K_{0}=10025\cdot 146$ and the last inequality holds as long as $K_{0}\Lambda_{0}^{2}D^{2}=K_{0}\eta^{2}\Lambda^{2}D^{2}\leq 1/2$, i.e., $\eta\leq\frac{1}{\sqrt{2K_{0}}\cdot\Lambda D}$; in particular, it suffices to take $\eta\leq\frac{1}{1711\cdot\Lambda D}$. This verifies that item 1 holds at time $t$, completing the inductive step.

The conclusion of Theorem 5 is an immediate conclusion of item 2 at time $T$, since $4\delta\leq 5\delta_{0}=\frac{60D}{\eta\sqrt{T}}$. ∎

B.5 Helpful lemmas

For square matrices $\mathbf{X},\mathbf{Y}$, we have, for any $\epsilon>0$,

Applying the previous lemma to the cross terms in the quantity $\mathbf{X}\mathbf{X}^{\top}$ when using the decomposition $\mathbf{X}=\mathbf{Y}+(\mathbf{X}-\mathbf{Y})$, we obtain the following.

For square matrices $\mathbf{X},\mathbf{Y}$, we have, for any $\epsilon>0$,

In particular, choosing $\epsilon=1$ gives

Lemma 19 is an immediate corollary of the two lemmas above:

For square matrices $\mathbf{X},\mathbf{Y}$, we have

For square matrices $\mathbf{X},\mathbf{Y}$ such that $\|\mathbf{Y}\|_{\sigma}\leq M$, we have

For any square matrix $\mathbf{X}$ so that $\|\mathbf{X}\|_{\sigma}<1$, we have

Using the equality (34), we have that for any $\epsilon>0$,

Choosing $\epsilon=\frac{1-\|\mathbf{X}\|_{\sigma}}{\|\mathbf{X}\|_{\sigma}}$ gives the desired conclusion. ∎

Appendix 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.

for $t\geq 1$ and $\mathbf{C}_{j}(\mathbf{A})=\alpha_{j}\mathbf{A}+\beta_{j}I_{n}$ for $0\leq j\leq p-1$ and $\mathbf{N}(\mathbf{A})=\gamma\mathbf{A}+\delta I_{n}$.

In the case of OG with a constant step size $\eta$, for $F(\mathbf{z})=\mathbf{A}\mathbf{z}+\mathbf{b}$, we may rewrite (15) as

so we have $\mathbf{C}_{0}(\mathbf{A})=I_{n}-2\eta\mathbf{A},\mathbf{C}_{1}(\mathbf{A})=\eta\mathbf{A},\mathbf{N}(\mathbf{A})=-\eta I_{n}$.

All lower bounds we prove in this section will apply more generally to any iterative algorithm $\mathcal{A}$ whose updates are of the form (78) when restricted to instances $F(\mathbf{z})=\mathbf{A}\mathbf{z}+\mathbf{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.

We will need the following standard lemma:

Next we prove Theorem 7, restated below for convenience.

We consider the dynamics of the iterates of $\mathcal{A}$ for various choices of $\mathbf{z}^{(0)},\ldots,\mathbf{z}^{(-p+1)}\in\mathcal{D}_{D}$. To do so, we define the block matrices:

Then the updates of $\mathcal{A}$ as in (78) can be written in the following form, for $F(\mathbf{z})=\mathbf{A}\mathbf{z}+\mathbf{b}$:

Recall that Observation 22 gives us $\mathbf{C}_{j}(\mathbf{A})=\alpha_{j}\cdot\mathbf{A}+\beta_{j}\cdot I_{n}$, and $\mathbf{N}(\mathbf{A})=\gamma\cdot\mathbf{A}+\delta\cdot I_{n}$, for some real numbers $\alpha_{j},\beta_{j},\gamma,\delta$ where $0\leq j\leq p-1$.

But since $\mathbf{M}$ is a nonzero multiple of the identity matrix, if the above matrix is not full-rank, it must be identically 0, i.e., $\sum_{j=0}^{p-1}\mathbf{C}_{j}(\mathbf{A})=I_{n}$. Hence $\sum_{j=0}^{p-1}\beta_{j}=1,\sum_{j=0}^{p-1}\alpha_{j}=0$.

Case 3. $\rho(\mathbf{C}(\mathbf{A}))<1$; in this case we have

Note that $\mathbf{U}^{\top}(\mathbf{C}(\mathbf{A})-I_{np})^{-1}\mathbf{U}$ is the lower $n\times n$-submatrix of the matrix $(\mathbf{C}(\mathbf{A})-I_{np})^{-1}$, and therefore it must be the inverse of the Schur complement of the upper $(p-1)n\times(p-1)n$-submatrix of $\mathbf{C}(\mathbf{A})-I_{np}$. Thus $\mathbf{U}^{\top}(\mathbf{C}(\mathbf{A})-I_{np})^{-1}\mathbf{U}$ is invertible, and since $\mathbf{N}(\mathbf{A})$ is as well, we may define $\mathbf{B}(\mathbf{A}):=-\left(\mathbf{U}^{\top}(\mathbf{C}(\mathbf{A})-I_{np})^{-1}\mathbf{U}\mathbf{N}(\mathbf{A})\right)^{-1}$. Hence $\mathbf{U}^{\top}(\mathbf{C}(\mathbf{A})-I_{np})^{-1}\mathbf{U}=-\mathbf{B}(\mathbf{A})^{-1}\mathbf{N}(\mathbf{A})^{-1}$. As shown in [ASSS15, Eqs. (68) – (70)], this implies that $\sum_{j=0}^{p-1}\mathbf{C}_{j}(\mathbf{A})=I_{n}+\mathbf{N}(\mathbf{A})\mathbf{B}(\mathbf{A})$, which can be written as:

It then follows from (81) and the fact that $\mathbf{N}(\mathbf{A}),\mathbf{C}(\mathbf{A})$ commute with $\mathbf{A}$ that

Case 3b. $\sum_{j=0}^{p-1}\beta_{j}=1$. This case contains the case in which the iterates $\mathbf{z}^{(t)}$ of the $p$-SCLI converge to the true solution $-\mathbf{A}^{-1}\mathbf{b}$ for all $\mathbf{A},\mathbf{b}$, and is thus the main nontrivial case (in particular, it is the case in which we use Proposition 8).

By the formula for the determinant of a tensor product of matrices,

C.2 Proof of Propositions 8 and 9

In this section we prove Propositions 8 and 9.

By Cauchy’s integral formula, there is a positive constant $A_{0}$, depending only on the function $R(\cdot)$, so that for $w\in\Delta$, we have that

By choosing $\mu_{0}>0$ to be sufficiently small, we may ensure that $[0,\mu_{0}]\subset V$. Now fix any $\mu\in(0,\mu_{0})$. We consider several cases:

Case 1. $k=1$. Let $w_{0}=b(\mu)$, so that

for some constant $A_{1}>0$. We have that $R(a(w_{0}))=\mu$ by definition of $a(z)$. Moreover,

Case 2. $k=2$. Again let $w_{0}=b(\mu)$, so that (85) holds. Let $u_{0}\in\Delta$ be a square root of $w_{0}$, i.e., $u_{0}^{2}=(-u_{0})^{2}=w_{0}$. Then $R(a(u_{0}))=R(a(-u_{0}))=\mu$. It must be the case that either $a^{\prime}(0)\cdot u_{0}$ or $-a^{\prime}(0)\cdot u_{0}$ has a non-negative real part; suppose without loss of generality that it is $a^{\prime}(0)\cdot u_{0}$ (if not, then replace $u_{0}$ with $-u_{0}$). Then

We remark also that the case $k\geq 3$ can be dealt with directly, without appealing to Theorem 25: again let $w_{0}=b(\mu)$, so that (85) holds. Then there exists some $k$th root $u_{0}\in\Delta$ of $w_{0}$ so that $a^{\prime}(0)\cdot u_{0}=re^{i\theta}$ for some $\theta\in[-\pi/3,\pi/3]$ and $r>0$. Then

for sufficiently small $u_{0}$ (which can be made arbitrarily small by taking $\mu\downarrow 0$). ∎

The proof of this proposition involves similar calculations as were done in [ASSS15, Section 5.2], but we spell them out in detail for completeness.

The polynomials in (86) are closely related to Nesterov’s accelerated gradient descent (AGD); we discuss this connection further in Remark 8.

C.3 Proof of a conjecture of [ASSS15]

In this section we prove the following conjecture:

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.

Notice that the opposite direction of the inequality in (91) holds trivially, and thus we have equality. Notice also that the first equality in (91) follows by Gelfand’s formula.

(We use Lemma 26 in (92).) Let $\mathcal{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 $\mathcal{S}_{t}$ for each $t$.) It follows from Theorem 3.6.3, and Example 3.8.3 of [Nev93] that

Combining (89), (92), and (93), we see that

The desired conclusion follows by taking $\epsilon\downarrow 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

For completeness we prove Lemma 27 below; we first complete the proof of Theorem 25 assuming Lemma 27.

where to derive (94) we used that $R(\infty)=\infty$ since $q(z)$ is monic of degree $p$ and $r(z)$ is of degree $p-1$, and to derive (95) we used that $R(1)=0$ since $q(1)=0$ by assumption.

Next we recall the Schwarz lemma from elementary complex analysis:

A holomorphic function $f:\Delta\rightarrow\Delta$ with $f(0)=0$ satisfies $|f(z)|\leq|z|$ for all $z\in\Delta$.

Since $H:\Delta\rightarrow\Delta$ is holomorphic, satisfies $H(0)=0$ (by (94)), (95) together with Lemma 28 gives us that

where the choice of the branch of the square root will be explained below. In particular, $G$ is obtained as the composition of maps $G=G_{5}\circ G_{4}\circ G_{3}\circ G_{2}\circ G_{1}$, where $G_{1},\ldots,G_{5}$ are defined by:

The conclusion of Proposition 29 is known even for non-stationary $p$-CLIs and without the superfluous $1/\sqrt{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 25 may have further consequences for proving lower bounds for optimization algorithms, such as in the stochastic setting.

C.4 Byproduct: Lower bound for convex function minimization

In this section we prove an (algorithm-dependent) lower bound of $\Omega(1/T)$ on the rate of convergence for $p$-SCLIs for convex function minimization. This statement was claimed to be proven by [AS16, Corollary 1], but in fact their results only give a linear lower bound for the strongly convex case (and not the sublinear bound of $\Omega(1/T)$ we obtain here): in particular, Corollary 1 of [AS16] is a corollary of Theorem 2 of [AS16], which should be adjusted to state that the error after $T$ iterations cannot be upper bounded by $O\left(\left(1-(\mu/L)^{\alpha}\right)^{T}\right)$, for any $\alpha<1$. In particular, this modified version can be established by only using functions for which the condition number $L/\mu$ is a constant. In more detail, one runs into the following issue when using the machinery of [AS16] to attempt to prove that the iteration complexity of a $p$-SCLI cannot be $O(\kappa^{\alpha}\ln(1/\epsilon))$ for any $\alpha<1$: at the end of the proof of [AS16, Theorem 2], Lemma 4 of [AS16] is used to conclude the existence of some $\eta\in(L/2,L)$ satisfying a certain inequality. However, $L/\eta$ represents the condition number $\kappa$ of the problem, and so choosing $\eta\in(L/2,L)$ forces the condition number $\kappa$ of the function to be a constant. This weaker version of [AS16, Theorem 2] does not imply [AS16, Corollary 1].

By replacing $T$ with $T+p-1$ and decreasing $c_{\mathcal{A}}$, the conclusion of Proposition 30 follows. ∎