A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games

Introduction

Gradient-based optimization methods have underpinned many of the recent successes of machine learning. The training of many models is indeed formulated as the minimization of a loss involving the data. However, a growing number of frameworks rely on optimization problems that involve multiple players and objectives. For instance, actor-critic models (Pfau and Vinyals, 2016), generative adversarial networks (GANs) (Goodfellow et al., 2014) and automatic curricula (Sukhbaatar et al., 2018) can be cast as two-player games.

Hence games are a generalization of the standard single-objective framework. The aim of the optimization is to find Nash equilibria, that is to say situations where no player can unilaterally decrease their loss. However, new issues that were not present for single-objective problems arise. The presence of rotational dynamics prevent standard algorithms such as the gradient method to converge on simple bilinear examples (Goodfellow, 2016; Balduzzi et al., 2018). Furthermore, stationary points of the gradient dynamics are not necessarily Nash equilibria (Adolphs et al., 2019; Mazumdar et al., 2019).

Some recent progress has been made by introducing new methods specifically designed with games or variational inequalities in mind. The main example are the optimistic gradient method (OG) introduced by Rakhlin and Sridharan (2013) initially for online learning, consensus optimization (CO) which adds a regularization term to the optimization problem and the extragradient method (EG) originally introduced by Korpelevich (1976). Though these news methods and the gradient method (GD) have similar performance in convex optimization, their behaviour seems to differ when applied to games: unlike gradient, they converge on the so-called bilinear example (Tseng, 1995; Gidel et al., 2019a; Mokhtari et al., 2019; Abernethy et al., 2019).

However, linear convergence results for EG and OG (a.k.a extrapolation from the past) in particular have only been proven for either strongly monotone variational inequalities problems, which include strongly convex-concave saddle point problems, or in the bilinear setting separately (Tseng, 1995; Gidel et al., 2019a; Mokhtari et al., 2019).

In this paper, we study the dynamics of such gradient-based methods and in particular GD, EG and more generally multi-step extrapolations methods for unconstrained games. Our objective is three-fold. First, taking inspiration from the analysis of GD by Gidel et al. (2019b), we aim at providing a single precise analysis of EG which covers both the bilinear and the strongly monotone settings and their intermediate cases. Second, we are interested in theoretically comparing EG to GD and general multi-step extrapolations through upper and lower bounds on convergence rates. Third, we provide a framework to extend the unifying results of spectral analysis in global guarantees and leverage it to prove tighter convergence rates for OG and CO. Our contributions can be summarized as follows:

We perform a spectral analysis of EG in §5. We derive a local rate of convergence which covers the whole range of settings between purely bilinear and strongly monotone games and which is faster than existing rates in some regimes. Our analysis also encompasses multi-step extrapolation methods and highlights the similarity between EG and the proximal point methods.

We use and extend the framework from Arjevani et al. (2016) to derive lower bounds for specific classes of algorithms. (i) We show in §4 that the previous spectral analysis of GD by Gidel et al. (2019b) is tight, confirming the difference of behaviors with EG. (ii) We prove lower bounds for $1$-Stationary Canonical Linear Iterative methods with any number of extrapolation steps in §5. As expected, this shows that increasing this number or choosing different step sizes for each does not yield significant improvements and hence EG can be considered as optimal among this class.

In §6, we derive a global convergence rate for the EG with the same unifying properties as the local analysis. We then leverage our approach to derive global convergence guarantees for OG and CO with similar unifying properies. It shows that, while these methods converges for different reasons in the convex and bilinear settings, in between they actually take advantage of the most favorable one.

Related Work

Extragradient was first introduced by Korpelevich (1976) in the context of variational inequalities. Tseng (1995) proves results which induce linear convergence rates for this method in the bilinear and strongly monotone cases. We recover both rates with our analysis. The extragradient method was generalized to arbitrary geometries by Nemirovski (2004) as the mirror-prox method. A sublinear rate of $\mathcal{O}(1/t)$ was proven for monotone variational inequalities by treating this method as an approximation of the proximal point method as we will discuss later. More recently, Mertikopoulos et al. (2019) proved that, for a broad class of saddle-point problems, its stochastic version converges almost surely to a solution.

Optimistic gradient method is slightly different from EG and can be seen as a kind of extrapolation from the past (Gidel et al., 2019a). It was initially introduced for online learning (Chiang et al., 2012; Rakhlin and Sridharan, 2013) and subsequently studied in the context of games by Daskalakis et al. (2018), who proved that this method converges on bilinear games. Gidel et al. (2019a) interpreted GANs as a variational inequality problem and derived OG as a variant of EG which avoids “wasting” a gradient. They prove a linear convergence rate for strongly monotone variational inequality problems. Treating EG and OG as perturbations of the proximal point method, Mokhtari et al. (2019) gave new but still separate derivations for the standard linear rates in the bilinear and the strongly convex-concave settings. Liang and Stokes (2019) mentioned the potential impact of the interaction between the players, but they only formally show this on bilinear examples: our results show that this conclusion extends to general nonlinear games.

Consensus optimization has been motivated by the use of gradient penalty objectives for the practical training of GANs (Gulrajani et al., 2017; Mescheder et al., 2017). It has been analysed by Abernethy et al. (2019) as a perturbation of Hamiltonian gradient descent.

We provide a unified and tighter analysis for these three algorithms leading to faster rates (cf. Tab. 1).

Lower bounds in optimization date back to Nemirovsky and Yudin (1983) and were popularized by Nesterov (2004). One issue with these results is that they are either only valid for a finite number of iterations depending on the dimension of the problem or are proven in infinite dimensional spaces. To avoid this issue, Arjevani et al. (2016) introduced a new framework called $p$-Stationary Canonical Linear Iterative algorithms ($p$-SCLI). It encompasses methods which, applied on quadratics, compute the next iterate as fixed linear transformation of the $p$ last iterates, for some fixed $p\geq 1$. We build on and extend this framework to derive lower bounds for games for 1-SCLI. Concurrenty, Ibrahim et al. (2020) extended the whole $p$-SCLI framework to games but excluded extrapolation methods. Note that sublinear lower bounds have been proven for saddle-point problems by Nemirovsky (1992); Nemirovski (2004); Chen et al. (2014); Ouyang and Xu (2018), but they are outside the scope of this paper since we focus on linear convergence bounds.

Our notation is presented in §A. The proofs can be found in the subsequent appendix sections.

Background and motivation

where the vector $(\omega^{-i})^{*}$ contains all the coordinates of $\omega^{*}$ except the $i^{th}$ one. Moreover, we say that a game is zero-sum if $\sum_{i=1}^{n}l_{i}=0$. For instance, following Mescheder et al. (2017); Gidel et al. (2019b), the standard formulation of GANs from Goodfellow et al. (2014) can be cast as a two-player zero-sum game. The Nash equilibrium corresponds to the desired situation where the generator exactly capture the data distribution, completely confusing a perfect discriminator.

associated to a $n$-player game and its Jacobian:

Gidel et al. (2019b) and Balduzzi et al. (2018) mentioned two particular classes of games, which can be seen as the two opposite ends of a spectrum. As the definitions vary, we only give the intuition for these two categories. The first one is adversarial games, where the Jacobian has eigenvalues with small real parts and large imaginary parts and the cross terms $\nabla_{\omega_{i}}\nabla_{\omega_{j}}l_{j}(\omega)$, for $i\neq j$, are dominant. Ex. 1 gives a prime example of such game that has been heavily studied: a simple bilinear game whose Jacobian is anti-symmetric and so only has imaginary eigenvalues (see Lem. 7 in App. E):

If $A$ is non-singular, there is an unique stationary point which is also the unique Nash equilibrium. The gradient method is known not to converge in such game while the proximal point and extragradient methods converge Rockafellar (1976); Tseng (1995).

Bilinear games are of particular interest to us as they are seen as models of the convergence problems that arise during the training of GANs. Indeed, Mescheder et al. (2017) showed that eigenvalues of the Jacobian of the vector field with small real parts and large imaginary parts could be at the origin of these problems. Bilinear games have pure imaginary eigenvalues and so are limiting models of this situation. Moreover, they can also be seen as a very simple type of WGAN, with the generator and the discriminator being both linear, as explained in Gidel et al. (2019a); Mescheder et al. .

The other category is cooperative games, where the Jacobian has eigenvalues with large positive real parts and small imaginary parts and the diagonal terms $\nabla^{2}_{\omega_{i}}l_{i}$ are dominant. Convex minimization problems are the archetype of such games. Our hypotheses, for both the local and the global analyses, encompass these settings.

2 Methods and convergence analysis

Convergence theory of fixed-point iterations. Seeing optimization algorithms as the repeated application of some operator allows us to deduce their convergence properties from the spectrum of this operator. This point of view was presented by Polyak (1987); Bertsekas (1999) and recently used by Arjevani et al. (2016); Mescheder et al. (2017); Gidel et al. (2019b) for instance. The idea is that the iterates of a method $(\omega_{t})_{t}$ are generated by a scheme of the form:

This theorem means that to derive a local rate of convergence for a given method, one needs only to focus on the eigenvalues of $\nabla F(\omega^{*})$. Note that if the operator $F$ is linear, there exists slightly stronger results such as Thm. 10 in Appendix C.

Proximal point. For $v$ monotone (Minty, 1962; Rockafellar, 1976), the proximal point operator can be defined as $P_{\eta}(\omega)=(\operatorname*{Id}+\eta v)^{-1}(\omega)$ and therefore can be seen as an implicit scheme: $\omega_{t+1}=\omega_{t}-\eta v(\omega_{t+1})$.

Extragradient. EG was introduced by Korpelevich (1976) in the context of variational inequalities. Its update rule is

which is a contraction for $\eta>0$ small enough. From Picard’s fixed point theorem, one gets that the proximal point operator $P_{\eta}(\omega)$ can be obtained as the limit of $\varphi_{\eta,\omega}^{k}(\omega)$ when $k$ goes to infinity. What Nemirovski (2004) showed is that $\varphi_{\eta,\omega}^{2}(\omega)$, that is to say the extragradient update, is close enough to the result of the fixed point computation to be used in place of the proximal point update without affecting the sublinear convergence speed. Our analysis of multi-step extrapolation methods will encompass all the iterates $\varphi_{\eta,\omega}^{k}$ and we will show that a similar phenomenon happens for linear convergence rates.

Optimistic gradient. Originally introduced in the online learning literature (Chiang et al., 2012; Rakhlin and Sridharan, 2013) as a two-steps method, Daskalakis et al. (2018) reformulated it with only one step in the unconstrained case:

Consensus optimization. Introduced by Mescheder et al. (2017) in the context of games, consensus optimization is a second-order yet efficient method, as it only uses a Hessian-vector multiplication whose cost is the same as two gradient evaluations (Pearlmutter, 1994). We define the CO update as:

where $H(\omega)=\frac{1}{2}\|v(\omega)\|^{2}_{2}$ and $\alpha,\beta>0$ are step sizes.

3 p-SCLI framework for game optimization

In this section, we present an extension of the framework of Arjevani et al. (2016) to derive lower bounds for game optimization (also see §G). The idea of this framework is to see algorithms as the iterated application of an operator. If the vector field is linear, this transformation is linear too and so its behavior when iterated is mainly governed by its spectral radius. This way, showing a lower bound for a class of algorithms is reduced to lower bounding a class of spectral radii.

This form of the update rule is required by the consistency condition of Arjevani et al. (2016) which is necessary for the algorithm to converge to stationary points, as discussed in §G. Also note that $1$-SCLI are first-order methods that use only the last iterate to compute the next one. Accelerated methods such as accelerated gradient descent (Nesterov, 2004) or the heavy ball method (Polyak, 1964) belong in fact to the class of $2$-SCLI, which encompass methods which uses the last two iterates.

As announced above, the spectral radius of the operator gives a lower bound on the speed of convergence of the iterates of the method on affine vector fields, which is sufficient to include bilinear games, quadratics and so strongly monotone settings too.

Revisiting GD for games

In this section, our goal is to illustrate the precision of the spectral bounds and the complexity of the interactions between players in games. We first give a simplified version of the bound on the spectral radius from Gidel et al. (2019b) and show that their results also imply that this rate is tight.

Let $\omega^{*}$ be a stationary point of $v$ and denote by $\sigma^{*}$ the spectrum of $\nabla v(\omega^{*})$. If the eigenvalues of $\nabla v(\omega^{*})$ all have positive real parts, then

(Gidel et al., 2019b) For $\eta=\min_{\lambda\in\sigma^{*}}\Re(1/\lambda)$, the spectral radius of $F_{\eta}$ can be upper-bounded as

For all $\eta>0$, the spectral radius of the gradient operator $F_{\eta}$ at $\omega^{*}$ is lower bounded by

This result is stronger than what we need for a standard lower bound: using Thm. 2, this yields a lower bound on the convergence of the iterates for all games with affine vector fields.

We then consider a saddle-point problem, and under some assumptions presented below, one can interpret the spectral rate of the gradient method mentioned earlier in terms of the standard strong convexity and Lipschitz-smoothness constants. There are several cases, but one of them is of special interest to us as it demonstrates the precision of spectral bounds.

$f$ satisfies, with $\mu_{1},\mu_{2}$ and $\mu_{12}$ non-negative,

such that $\mu_{12}>2\max(L_{1}-\mu_{2},L_{2}-\mu_{1})$.

There exists a stationary point $\omega^{*}=(x^{*},y^{*})$ and at this point, $\nabla_{y}^{2}f(\omega^{*})$ and $\nabla_{x}\nabla_{y}f(\omega^{*})$ commute and $\nabla_{x}^{2}f(\omega^{*})$, $\nabla_{y}^{2}f(\omega^{*})$ and $(\nabla_{x}\nabla_{y}f(\omega^{*}))^{T}(\nabla_{x}\nabla_{y}f(\omega^{*}))$ commute.

Assumption (i) corresponds to a highly adversarial setting as the coupling (represented by the cross derivatives) is much bigger than the Hessians of each player. Assumption (ii) is a technical assumption needed to compute a precise bound on the spectral radius and holds if, for instance, the objective is separable, i.e. $f(x,y)=\sum_{i=1}^{m}f_{i}(x_{i},y_{i})$. Using these assumptions, we can upper bound the rate of Thm. 3 as follows:

Under the assumptions of Thm. 3 and Ex. 2,

What is surprising is that, in some regimes, this result induces faster local convergence rates than the existing upper-bound for EG (Tseng, 1995):

If, say, $\mu_{2}$ goes to zero, that is to say the game becomes unbalanced, the rate of EG goes to 1 while the one of Eq. 3 stays bounded by a constant which is strictly less than 1. Indeed, the rate of Cor. 1 involves the arithmetic mean of $\mu_{1}$ and $\mu_{2}$, which is roughly the maximum of them, while Eq. 4 makes only the minimum of the two appear. This adaptivity to the best strong convexity constant is not present in the standard convergence rates of the EG method. We remedy this situation with a new analysis of EG in the following section.

Spectral analysis of multi-step EG

In this section, we study the local dynamics of EG and, more generally, of extrapolation methods. Define a $k$-extrapolation method ($k$-EG) by the operator

We are essentially considering all the iterates of the fixed point computation discussed in Section 3.2. Note that $F_{1,\eta}$ is GD while $F_{2,\eta}$ is EG. We aim at studying the local behavior of these methods at stationary points of the gradient dynamics, so fix $\omega^{*}$ s.t. $v(\omega^{*})=0$ and let $\sigma^{*}=\operatorname*{Sp}\nabla v(\omega^{*})$. We compute the spectra of these operators at this point and this immediately yields the spectral radius on the proximal point operator:

The spectra of the $k$-extrapolation operator and the proximal point operator are given by:

Hence, for all $\eta>0$, the spectral radius of the operator of the proximal point method is equal to:

Again, this shows that a $k$-EG is essentially an approximation of proximal point for small step sizes as $(1+\eta\lambda)^{-1}=\sum_{j=0}^{k}(-\eta\lambda)^{j}+\mathcal{O}\left(|\eta\lambda|^{k+1}\right)$. This could suggest that increasing the number of extrapolations might yield better methods but we will actually see that $k=2$ is enough to achieve a similar rate to proximal. We then bound the spectral radius of $\nabla F_{\eta,k}(\omega^{*})$:

Let $\sigma^{*}=\operatorname*{Sp}\nabla v(\omega^{*})$. If the eigenvalues of $\nabla v(\omega^{*})$ all have non-negative real parts, the spectral radius of the $k$-extrapolation method for $k\geq 2$ satisfies:

$\forall\eta\leq\frac{1}{4^{\frac{1}{k-1}}}\frac{1}{\max_{\lambda\in\sigma^{*}}|\lambda|}$. For $\eta=(4\max_{\lambda\in\sigma^{*}}|\lambda|)^{-1}$, this can be simplified as (noting $\rho:=\rho(\nabla F_{\eta,k}(\omega^{*}))$):

The zone of convergence of extragradient as provided by this theorem is illustrated in Fig. 1.

The bound of Eq. 8 involves two terms: the first term can be seen as the strong monotonicity of the problem, which is predominant in convex minimization problems, while the second shows that even in the absence of it, this method still converges, such as in bilinear games. Furthermore, in situation in between, this bound shows that the extragradient method exploits the biggest of these quantities as they appear as a sum as illustrated by the following simple example.

Though for $\epsilon$ close to zero, the dynamics will behave as such, this is not a purely bilinear game. The associated vector field is only $\epsilon$-strongly monotone and convergence guarantees relying only on strong monotonicity would give a rate of roughly $1-\epsilon/4$. However Thm. 4 yields a convergence rate of roughly $1-1/64$ for extragradient.

Similarity to the proximal point method. First, note that the bound Eq. 7 is surprisingly close to the one of the proximal method Eq. 6. However, one can wonder why the proximal point converges with any step size — and so arbitrarily fast — while it is not the case for the $k$-EG, even as $k$ goes to infinity. The reason for this difference is that for the fixed point iterates to converge to the proximal point operator, one needs $\varphi_{\eta,\omega}$ to be a contraction and so to have $\eta$ small enough, at least $\eta<(\max_{\lambda\in\sigma^{*}}|\lambda|)^{-1}$ for local guarantees. This explains the bound on the step size for $k$-EG .

Comparison with the gradient method. We can now compare this result for EG with the convergence rate of the gradient method Thm. 3 which was shown to be tight. In general $\min_{\lambda\in\sigma^{*}}\Re(1/\lambda)\leq(\max_{\lambda\in\sigma^{*}}|\lambda|)^{-1}$ and, for adversarial games, the first term can be arbitrarily smaller than the second one. Hence, in this setting which is of special interest to us, EG has a much faster convergence speed than GD.

Recovery of known rates. If $v$ is $\mu$-strongly monotone and $L$-Lipschitz, this bound is at least as precise as the standard one $1-\mu/(4L)$ as $\mu$ lower bounds the real part of the eigenvalues of the Jacobian, and $L$ upper bounds their magnitude, as shown in Lem. 8 in §F.2. We empirically evaluate the improvement over this standard rate on synthetic examples in Appendix J. On the other hand, Thm. 4 also recovers the standard rates for the bilinear problem,Note that by exploiting the special structure of the bilinear game and the fact that $k=2$, one could derive a better constant in the rate. Moreover, our current spectral tools cannot handle the singularity which arises if the two players have a different number of parameters. We provide sharper results to handle this difficulty in Appendix I. as shown below:

Consider Ex. 1. The iterates of the $k$-extrapolation method with $k\geq 2$ converge globally to $\omega^{*}$ at a linear rate of \mathcal{O}\big{(}\big{(}1-\frac{1}{64}\frac{\sigma_{min}(A)^{2}}{{\sigma_{max}(A)^{2}}}\big{)}^{t}\big{)}.

Note that this rate is similar to the one derived by Gidel et al. (2019b) for alternating gradient descent with negative momentum. This raises the question of whether general acceleration exists for games, as we would expect the quantity playing the role of the condition number in Cor. 2 to appear without the square in the convergence rate of a method using momentum.

Finally it is also worth mentioning that the bound of Thm. 4 also displays the adaptivity discussed in §4. Hence, the bound of Thm. 4 can be arbitrarily better than the rate Eq. 4 for EG from the literature and also better than the global convergence rate we prove below.

Lower bounds for extrapolation methods. We now show that the rates we proved for EG are tight and optimal by deriving lower bounds of convergence for general extrapolation methods. As described in Section 3.3, a 1-SCLI method is parametrized by a polynomial $\mathcal{N}$. We consider the class of methods where $\mathcal{N}$ is any polynomial of degree at most $k-1$, and we will derive lower bounds for this class. This class is large enough to include all the $k^{\prime}$-extrapolation methods for $k^{\prime}\leq k$ with possibly different step sizes for each extrapolation step (see §H for more examples).

Our main result is that no method of this class can significantly beat the convergence speed of EG of Thm. 4 and Thm. 6. We proceed in two steps: for each of the two terms of these bounds, we provide an example matching it up to a factor. In $(i)$ of the following theorem, we give an example of convex optimization problem which matches the real part, or strong monotonicity, term. Note that this example is already an extension of Arjevani et al. (2016) as the authors only considered constant $\mathcal{N}$. Next, in $(ii)$, we match the other term with a bilinear game example.

Let $0<\mu,\gamma<L$. $(i)$ If $d-2\geq k\geq 3$, there exists $v\in\mathcal{V}_{d}$ with a symmetric positive Jacobian whose spectrum is in $[\mu,L]$, such that for any $\mathcal{N}$real polynomial of degree at most $k-1$, $\rho(F_{\mathcal{N}})\geq 1-\frac{4k^{3}}{\pi}\frac{\mu}{L}\,.$

$(ii)$ If ${d}/{2}-2\geq k/2\geq 3$ and $d$ is even, there exists $v\in\mathcal{V}_{d}$ $L$-Lipschitz with $\min_{\lambda\in\operatorname*{Sp}\nabla v}|\lambda|=\sigma_{min}(\nabla v)\geq\gamma$ corresponding to a bilinear game of Example 1 with $m=d/2$, such that, for any $\mathcal{N}$real polynomial of degree at most $k-1$, $\rho(F_{\mathcal{N}})\geq 1-\frac{k^{3}}{2\pi}\frac{\gamma^{2}}{L^{2}}\,.$

First, these lower bounds show that both our convergence analyses of EG are tight, by looking at them for $k=3$ for instance. Then, though these bounds become looser as $k$ grows, they still show that the potential improvements are not significant in terms of conditioning, especially compared to the change of regime between GD and EG . Hence, they still essentially match the convergence speed of EG of Thm. 4 or Thm. 6. Therefore, EG can be considered as optimal among the general class of algorithms which uses at most a fixed number of composed gradient evaluations and only the last iterate. In particular, there is no need to consider algorithms with more extrapolation steps or with different step sizes for each of them as it only yields a constant factor improvement.

Unified global proofs of convergence

We have shown in the previous section that a spectral analysis of EG yields tight and unified convergence guarantees. We now demonstrate how, combining the strong monotonicity assumption and Tseng’s error bound, global convergence guarantees with the same unifying properties might be achieved.

Tseng (1995) proved linear convergence results for EG by using the projection-type error bound Tseng (1995, Eq. 5) which, in the unconstrained case, i.e. for $v(\omega^{*})=0$, can be written as,

The author then shows that this condition holds for the bilinear game of Example 1 and that it induces a convergence rate of $1-c\sigma_{min}(A)^{2}/\sigma_{max}(A)^{2}$ for some constant $c>0$. He also shows that this condition is implied by strong monotonicity with $\gamma=\mu$. Our analysis builds on the results from Tseng (1995) and extends them to cover the whole range of games and recover the optimal rates.

To be able to interpret Tseng’s error bound Eq. 9, as a property of the Jacobian $\nabla v$, we slightly relax it to,

This condition can indeed be related to the properties of $\nabla v$ as follows:

Let $v$ be continuously differentiable and $\gamma>0$ : Eq. 10 holds if and only if $\sigma_{min}(\nabla v)\geq\gamma$.

Hence, $\gamma$ corresponds to a lower bound on the singular values of $\nabla v$. This can be seen as a weaker “strong monotonicity” as it is implied by strong monotonicity, with $\gamma=\mu$, but it also holds for a square non-singular bilinear example of Example 1 with $\gamma=\sigma_{min}(A)$.

As announced, we will combine this assumption with the strong monotonicity to derive unified global convergence guarantees. Before that, note that this quantities can be related to the spectrum of $\operatorname*{Sp}\nabla v(\omega^{*})$ as follows – see Lem. 8 in Section F.1,

Hence, theses global quantities are less precise than the spectral ones used in Thm. 4, so the following global results will be less precise than the previous ones.

2 Global analysis EG and OG

We can now state our global convergence result for EG:

As for Thm. 4, this result not only recovers both the bilinear and the strongly monotone case, but shows that EG actually gets the best of both world when in between. Furthermore this rate is surprisingly similar to the result of Thm. 4 though less precise, as discussed.

Combining our new proof technique and the analysis provided by Gidel et al. (2019a), we can derive a similar convergence rate for the optimistic gradient method.

Under the same assumptions as in Thm. 6, for $\eta\leq(4L)^{-1}$, the iterates $(\omega_{t})_{t}$ of (OG) converge linearly to $\omega^{*}$ as, for all $t\geq 0$,

Interpretation of the condition numbers. As in the previous section, this rate of convergence for EG is similar to the rate of the proximal point method for a small enough step size, as shown by Prop. 1 in §F.2. Moreover, the proof of the latter gives insight into the two quantities appearing in the rate of Thm. 6. Indeed, the convergence result for the proximal point method is obtained by bounding the singular values of $\nabla P_{\eta}$, and so we compute,We dropped the dependence on $\omega$ for compactness.

where $\mathcal{H}(\nabla v):=\frac{\nabla v+\nabla v^{T}}{2}\,.$ This explains the quantities ${L}/{\mu}$ and ${L^{2}}/{\gamma^{2}}$ appear in the convergence rate, as the first corresponds to the condition number of $\mathcal{H}(\nabla v)$ and the second to the condition number of $\nabla v\nabla v^{T}$. Thus, the proximal point method uses information from both matrices to converge, and so does EG, explaining why it takes advantage of the best conditioning.

3 Global analysis of consensus optimization

In this section, we give a unified proof of CO. A global convergence rate for this method was proven by Abernethy et al. (2019). However it used a perturbation analysis of HGD. The drawbacks are that it required that the CO update be sufficiently close to the one of HGD and could not take advantage of strong monotonicity. Here, we combine the monotonicity $\mu$ with the lower bound on the singular value $\gamma$.

As this scheme uses second-orderW.r.t. the losses. information, we need to replace the Lipschitz hypothesis with one that also controls the variations of the Jacobian of $v$: we use $L_{H}^{2}$, the Lispchitz smoothness of $H$. See Abernethy et al. (2019) for how it might be instantiated.

This result shows that CO has the same unifying properties as EG, though the dependence on $\mu$ is worse.

This result also encompasses the rate of HGD (Abernethy et al., 2019, Lem. 4.7). The dependance in $\mu$ is on par with the standard rate for the gradient method (see Nesterov and Scrimali (2006, Eq. 2.12) for instance). However, this can be improved using a sharper assumption, as discussed in Remark 1 in Section F.3, and so our result is not optimal in this regard.

Conclusion

In this paper, we studied the dynamics of EG, both locally and globally and extended our global guarantees to other promising methods such as OG and CO. Our analysis is tight for EG and unified as they cover the whole spectrum of games from bilinear to purely cooperative settings. They show that in between, these methods enjoy the best of both worlds. We confirm that, unlike in convex minimization, the behaviors of EG and GD differ significantly. The other lower bounds show that EG can be considered as optimal among first-order methods that use only the last iterate.

Finally, as mentioned in §5, the rate of alternating gradient descent with negative momentum from Gidel et al. (2019b) on the bilinear example essentially matches the rate of EG in Cor. 2. Thus the question of an acceleration for adversarial games similar to the one in the convex case using Polyak (Polyak, 1964) or Nesterov’s (Nesterov, 2004) momentum remains open.

This research was partially supported by the Canada CIFAR AI Chair Program, the Canada Excellence Research Chair in “Data Science for Realtime Decision-making”, by the NSERC Discovery Grants RGPIN-2017-06936 and RGPIN-2019-06512, the FRQNT new researcher program 2019-NC-257943, by a Borealis AI fellowship, a Google Focused Research award and a startup grant by IVADO. Simon Lacoste-Julien is a CIFAR Associate Fellow in the Learning in Machines & Brains program. The authors would like to thank Adam Ibrahim for helpful discussions, especially on lower bounds.

Bibliography

Appendix A Notation

Appendix B Interpretation of spectral quantities in a two-player zero-sum game

In this appendix section, we are interested in interpreting spectral bounds in terms of the usual strong convexity and Lipschitz continuity constants in a two-player zero-sum game:

with $f$ is two times continuously differentiable.

where $\mu_{1},\mu_{2}$ and $\mu_{12}$ are non-negative constants. Let $\omega^{*}=(x^{*},y^{*})$ be a stationary point. To ease the presentation, let,

Now, more precisely, we are interested in lower bounding $\Re(\lambda)$ and $|\lambda|$ and upper bounding $|\lambda|$ for $\lambda\in\operatorname*{Sp}\nabla v(\omega^{*})$.

In this subsection we focus on the square and commutative case as formalized by the following assumptions:

The following holds: (i) $p=m=\frac{d}{2}$; (ii) $S_{2}$and $A^{T}$ commute; (iii) $S_{1}$, $S_{2}$ and $AA^{T}$ commute.

Denote by $|\mu|$ and $|L|$ the determinants of theses matrices, and by $\operatorname*{Tr}\mu$ and $\operatorname*{Tr}L$ their traces.

In this case we get an exact characterization of the spectrum $\nabla v(\omega^{*})$, which we denote by $\sigma^{*}=\operatorname*{Sp}\nabla v(\omega^{*})$:

Under Assumption 1, $\lambda\in sigma^{*}$ if and only if there exists some $i\leq d$ such that $\lambda$ is a root of

We compute the characteristic polynomial of $\nabla v(\omega^{*})$ using that $S_{2}$ and $A^{T}$ commute, using the formula for the determinant of a block matrix, which can be found in Zhang (2005, Section 0.3) for instance.

Under Assumption 1, we have the following results on the eigenvalues of $\nabla v(\omega^{*})$.

For $i\leq m$, if $(\alpha_{i}-\beta_{i})^{2}<4\sigma^{2}_{i}$, the roots of $P_{i}$ satisfy:

For $i\leq m$, if $(\alpha_{i}-\beta_{i})^{2}\geq 4\sigma^{2}_{i}$, the roots of $P_{i}$ are real non-negative and satisfy :

where $L_{max}=\max(L_{1},L_{2},L_{12})$.

Assume that $(\alpha_{i}-\beta_{i})^{2}<4\sigma^{2}_{i}$, i.e. the discriminant of the polynomial $P_{i}$ of Lem. 3 is negative. Consider $\lambda$ a root of $P_{i}$. Then $\Re\lambda=\frac{\alpha_{i}+\beta_{i}}{2}$ and $|\lambda|^{2}=\alpha_{i}\beta_{i}+\sigma^{2}_{i}$. Hence $\Re\lambda\geq\frac{1}{2}\operatorname*{Tr}\mu$ and $\det\mu\leq|\lambda|^{2}\leq\det L$.

Assume that $(\alpha_{i}-\beta_{i})^{2}\geq 4\sigma^{2}_{i}$, i.e. the discriminant of the polynomial $P_{i}$ of Lem. 3 is non-negative. This implies that $\Delta=\left(\operatorname*{Tr}L\right)^{2}-4\det\mu\geq 0$.

Denote by $\lambda_{+}$ and $\lambda_{-}$ the two real roots of $P_{i}$. Then

As $x\mapsto x-\sqrt{x^{2}-4\det\mu}$ is decreasing on its domain, the minimum is reached at $\operatorname*{Tr}L$ and is $\frac{\operatorname*{Tr}L-\sqrt{\Delta}}{2}\geq 0$. However this lower bound is quite loose when $A=0$. So note that

These assertions are immediate corollaries of the two previous ones.

We need the following lemma to be able to interpret Thm. 6 in the context of Example 2, whose assumptions imply Assumption 1.

Under Assumption 1, the singular values of $\nabla v(\omega^{*})$ can be lower bounded as:

In particular, if $\mu_{12}>2\max(L_{1}-\mu_{2},L_{2}-\mu_{1})$, this becomes

To prove this we compute the eigenvalues of $(\nabla v(\omega^{*}))^{T}\nabla v(\omega^{*})$. We have that,

As in the proof of Lem. 3, as Assumption 1 implies that $A^{T}S_{1}-S_{2}A^{T}$ and $A^{T}A+S_{2}^{2}$ commute,

Let $Q_{i}(X)=(XI-\alpha_{i}^{2}-\sigma_{i}^{2})(XI-\beta_{i}^{2}-\sigma_{i}^{2})-(\alpha_{i}-\beta_{i})^{2}\sigma_{i}^{2}$. Its discriminant is

The smallest is $\lambda_{i-}$ which can be lower bounded by

Appendix C Complement for Section 3

The convergence result of Thm. 1 can be strengthened if the Jacobian is constant as shown below. A proof of this classical result in linear algebra can be found in Arjevani et al. (2016) for instance.

Appendix D Convergence results of §4

* In this subsection, we quickly show how to obtain $(i)$ of Thm. 3 from Theorem 2 of Gidel et al. (2019b), whose part which interests us now is the following:

If the eigenvalues of $\nabla v(\omega^{*})$ all have positive real parts, then for $\eta=\Re(1/\lambda_{1})$ one has

where $\delta=\min_{1\leq j\leq m}|\lambda_{j}|^{2}(2\Re(1/\lambda_{j})-\Re(1/\lambda_{1}))$ and $\operatorname*{Sp}\nabla v(\omega^{*})=\{\lambda_{1},\dots,\lambda_{m}\}$ sorted such that $0<\Re(1/\lambda_{1})\leq\Re(1/\lambda_{2})\leq\dots\leq\Re(1/\lambda_{m})$.

By definition of the order on the eigenvalues,

To prove the second part of Thm. 3, we rely on a different part of Gidel et al. (2019b, Theorem 2) which we recall below:

The best step-size $\eta^{*}$, that is to say the solution of the optimization problem

Note that the hypotheses stated in §4 correspond to the assumptions of §B.1. Moreover, with the notations of this subsection, one has that $4\sigma_{i}^{2}\geq 4\mu_{12}^{2}$ and $\max(L_{1},L_{2})^{2}\geq(\alpha_{i}-\beta_{i})^{2}$. Hence the condition $2\mu_{12}\geq\max(L_{1},L_{2})$ implies that all the eigenvalues of $\nabla v(\omega^{*})$ satisfy the case $(a)$ of Thm. 9. Then, using Thm. 3,

Appendix E Spectral analysis of §5

Assuming that the eigenvalues of $\nabla v(\omega^{*})$ all have non-negative real parts, the proximal point operator $P_{\eta}$ is continuously differentiable in a neighborhood of $\omega^{*}$ . Moreover, the spectra of the $k$-extrapolation operator and the proximal point operator are given by:

Hence, for all $\eta>0$, the spectral radius of the operator of the proximal point method is equal to:

To prove the result about the $k$-extrapolation operator, we first show the following lemma, which will be used again later.

Recall that we defined $\varphi_{\eta,\omega}:z\mapsto\omega-\eta v(z)$. We drop the dependence on $\eta$ in $\varphi_{\eta,\omega}$ for compactness.

The Jacobians of $\varphi_{\omega}^{k}(z)$ with respect to $z$ and $\omega$ can be written as

For $k=1$, $\varphi_{\omega}(z)=\omega-\eta v(z)$ and the result holds.

Assume this result holds for $k\geq 0$. Then,

For the derivative with respect to $\omega$, we use the chain rule:

In the proof of Lem. 1 and later we will use the spectral mapping theorem, which we state below for reference:

See for instance Lax (2007, Theorem 4, p. 66 ) for a proof.

First we compute $\nabla F_{\eta,k}(\omega^{*})$. As $\omega^{*}$ is a stationary point, it is a fixed point of the extrapolation operators, i.e. $\varphi_{\omega^{*}}^{j}(\omega^{*})=\omega^{*}$ for all $j\geq 0$. Then, by the chain rule,

Hence $\nabla F_{\eta,k}(\omega^{*})$ is a polynomial in $\nabla v(\omega^{*})$. Using the spectral mapping theorem (Thm. 11), one gets that

For the proximal point operator, first let us prove that it is differentiable in a neighborhood of $\omega^{*}$. First notice that,

If the eigenvalues of $\nabla v(\omega^{*})$ all have non-negative real parts, this spectrum does not contain zero. Hence $\omega\mapsto\omega+\eta v(\omega)$ is continuously differentiable and has a non-singular differential at $\omega^{*}$. By the inverse function theorem (see for instance Rudin (1976)), $\omega\mapsto\omega+\eta v(\omega)$ is invertible in a neighborhood of $\omega^{*}$ and its inverse, which is $P_{\eta}$, is continuously differentiable there. Moreover,

Recall that the eigenvalues of a non-singular matrix are exactly the inverses of the eigenvalues of its inverse. Hence,

where the last equality follows from the spectral mapping theorem applied to $I_{d}+\eta\nabla v(\omega^{*})$. Now, the bound on the spectral radius of the proximal point operator is immediate. Indeed, its spectral radius is:

Let $L=\max_{\lambda\in\sigma^{*}}|\lambda|$ and $\eta=\frac{\tau}{L}$ for some $\tau>0$. For $\lambda\in\sigma^{*}$,

Now we focus on lower bounding the terms in between the parentheses. By definition of $\eta$, we have $\eta^{k-1}\frac{|\Re(\lambda^{k+1})|}{|\lambda|^{2}}\leq\tau^{k-1}$ and $\eta^{2(k-1)}|\lambda|^{2(k-1)}\leq\tau^{2(k-1)}$. Hence

Notice that if $k=1$, i.e. for the gradient method, we cannot control this quantity. However, for $k\geq 2$, if $\tau\leq(\frac{1}{4})^{\frac{1}{k-1}}$, one gets that

which yields the first assertion of the theorem. For the second one, take $\eta=\frac{1}{4L}$, i.e. the maximum step-size authorized for extragradient, and one gets that

* First we need to compute the eigenvalues of $\nabla v$.

Assumption 1 of Section B.1 holds so we can apply Lem. 3 which yields the result.

The Jacobian is constant here and has following the form:

Hence $\min_{\lambda\in\operatorname*{Sp}\nabla v}|\lambda|^{2}=\sigma_{min}(A)^{2}$ and $\max_{\lambda\in\operatorname*{Sp}\nabla v}|\lambda|^{2}=\sigma_{max}(A)^{2}$. Using Thm. 4, we have that,

Finally, Thm. 10 implies that the iterates of the $k$-extrapolation converge globally at the desired rate. ∎

Under the assumptions of Cor. 1, the spectral radius of the n-extrapolation method operator is bounded by

This is a direct consequence of Thm. 4 and Thm. 9, as the latter gives that for any $\lambda\in\operatorname*{Sp}\nabla v(\omega^{*})$,

Appendix F Global convergence proofs

In this section, $\|.\|$ denotes the Euclidean norm.

* Let us recall Eq. 10 here for simplicity:

The proof of this lemma is an immediate consequence of a global inverse theorem from Hadamard (1906); Levy (1920). Let us recall its statement here:

A proof of this theorem can be found in Rheinboldt (1969, Theorem 3.11). We now proceed to prove the lemma.

Hence $\|\nabla v^{-1}(v(\omega))\|=(\sigma_{min}(\nabla v(\omega)))^{-1}\leq\gamma^{-1}$.

Taking the limit when $t$ goes to gives that $\gamma\leq\|\nabla v(\omega)u\|$. As it holds for all $u$ such that $\|u\|=1$ this implies that $\gamma\leq\sigma_{min}(\nabla v)$. ∎

With the next lemma, we relate the quantities appearing in Thm. 6 to the spectrum of $\nabla v$. Note that the first part of the proof is standard — it can be found in Facchinei and Pang (2003, Prop. 2.3.2) for instance — and we include it only for completeness.

Furthermore, by the properties of the singular values,

Now, taking the real and imaginary part yields:

Taking the squared norm and developing the right-hand sides yields

Finally, apply Eq. 111 for $u=X$ and $u=Y$:

As $Z\neq 0$, $\|X\|^{2}+\|Y\|^{2}>0$ and this yields $\gamma\leq|\lambda|\leq L$. To get the inequality concerning $\gamma$, multiply on the left the first line of Eq. 113 by $X^{T}$ and the second one by $Y^{T}$:

Again, summing these two lines and using Eq. 111 yields:

As $Z\neq 0$, $\|X\|^{2}+\|Y\|^{2}>0$ and so $\mu\leq\Re(\lambda)$. ∎

F.2 Proofs of §6: extragradient, optimistic and proximal point methods

We now prove a slightly more detailed version of Thm. 6.

For $\eta=(4L)^{-1}$, this can be simplified as: $\|\omega_{t}-\omega^{*}\|_{2}^{2}\leq\left(1-\frac{1}{4}\left(\frac{\mu}{L}+\frac{1}{16}\frac{\gamma^{2}}{L^{2}}\right)\right)^{t}\|\omega_{0}-\omega^{*}\|_{2}^{2}$.

The proof is inspired from the ones of Gidel et al. (2019a); Tseng (1995).

We will use the following well-known identity. It can be found in Gidel et al. (2019a) for instance but we state it for reference.

First note that as $\gamma>0$, by Thm. 12, $v$ has a stationary point $\omega^{*}$ and it is unique.

Then, rearranging and using that $v(\omega^{*})=0$ yields that,

where the first term is lower bounded using strong monotonicity and the second one using Cauchy-Schwarz’s inequality. Using in addition the fact that $v$ is Lipschitz continuous we obtain:

where the last inequality comes from Young’s inequality. Using this inequality in Eq. 125 yields:

Now we lower bound $\|\omega_{1}-\omega^{*}\|$ using $\|\omega_{0}-\omega^{*}\|$. Indeed, from Young’s inequality we obtain

Note that if $\eta\leq\frac{1}{4L}$, as $\mu\leq L$, $\eta^{2}L^{2}+2\eta\mu-1\leq-\frac{7}{16}$. Therefore, with $c=\frac{7}{16}$,

Finally, using $(iii)$ and Lem. 2, we obtain:

Under the assumptions of Thm. 6, the iterates of the proximal point method method $(\omega_{t})_{t}$ with $\eta>0$ converge linearly to $\omega^{*}$ the unique stationary point of $v$,

The singular values $\nabla P_{\eta}(\omega_{0})$ are the eigenvalues of $(\nabla P_{\eta}(\omega_{0}))^{T}(\nabla P_{\eta}(\omega_{0}))$. The latter is equal to:

Finally, multiply this equation on the left by $X^{T}$:

Hence, as $X\neq 0$, we have proven that,

Hence, as $P_{\eta}(\omega^{*})=\omega^{*}$, taking $\omega^{\prime}=\omega^{*}$ gives the desired global convergence rate. ∎

Now let us prove the result Thm. 7 regarding Optimistic method. \thmglobalconvergenceoptimistic*

For the beginning of this proof we follow the proof of Gidel et al. (2019a, Theorem 1) using their notation:

Note that, with this notation, summing the two upates steps, we recover (OG)

Let us now recall Gidel et al. (2019a, Equation 88) for a constant step-size $\eta_{t}=\eta$,

we refer the reader to the proof of Gidel et al. (2019a, Theorem 1) for the details on how to get to this equation. Thus with $\eta\leq(4L)^{-1}$, using the update rule $\omega_{t}^{\prime}=\omega_{t}-\eta v(\omega^{\prime}_{t-1})$, we get,

where for the last inequality we used that $\sigma_{\min}(\nabla v)\geq\gamma$ and Lemma 2. Using Young’s inequality, the update rule and the Lipchitzness of $v$, we get that,

Thus combining (152), (153) and (156), we get with a constant step-size $\eta\leq(4L)^{-1}$,

In order to get the theorem statement we need a rate on $\omega_{t}^{\prime}$. We first unroll this geometric decrease and notice that

to get (using the fact that $\omega^{\prime}_{0}=\omega^{\prime}_{-1}$),

With $\eta\leq(4L)^{-1}$ we can use the fact that $\max(\mu,\gamma)\leq L$ to get,

leading to the statement of the theorem. Finally, for $\eta=(4L)^{-1}$ that can be simplified into,

F.3 Proof of Section 6.3: consensus optimization

where $H$ is the squared norm of $v$. We prove a more detailed version Thm. 8.

and $\beta\leq(2L_{H})^{-1}$, the iterates of CO defined by Eq. CO satisfy,

As $H$ is $L_{H}^{2}$ Lipschitz smooth, we have,

Then, replacing $\omega_{t+1}-\omega_{t}$ by its expression and using Young’s inequality,

Note that, crucially, $\nabla H(\omega_{t})=\nabla v(\omega_{t})^{T}v(\omega_{t})$. Using the first part of Lem. 8 to introduce $\mu$ and assuming $\beta\leq(2L_{H}^{2})^{-1}$,

Finally, using Lem. 8 to introduce $\gamma$,

Now, note that Eq. 169 is a second-order polynomial condition on $\alpha$, so we can compute the biggest $\alpha$ which satisfies this condition. This yields,

where in the second line we defined $\beta=(2L_{H}^{2})^{-1}$. Then the rate becomes,

where we use Young’s inequality: $\sqrt{2}\sqrt{a+b}\geq\sqrt{a}+\sqrt{b}$. Noting that $\frac{1}{2}(1+\frac{1}{\sqrt{2}})\geq 1$ yields the result. ∎

A common convergence result for the gradient method for variational inequalities problem – see Nesterov and Scrimali (2006) for instance – is that the iterates convergence as $O\left(\left(1-\frac{\mu^{2}}{L^{2}}\right)^{t}\right)$ where $\mu$ is the monotonicty constant of $v$ and $L$ its Lipschitz constant. However, this rate is not optimal, and also not satisfying as it does not recover the convergence rate of the gradient method for strongly convex optimization. One way to remedy this situation is to use the co-coercivity or inverse strong monotonicity assumption:

Appendix G The p-SCLI framework for game optimization

The approach we use to prove our lower bounds comes from Arjevani et al. (2016). Though their whole framework was developed for convex optimization, a careful reading of their proof shows that most of their results carry on to games, at least those in their first three sections. However, we work only in the restricted setting of $1$-SCLI and so we actually rely on a very small subset of their results, more exactly two of them.

$F_{\mathcal{N}}$ is affine so it can be written as $F_{N}(\omega)=\nabla F_{\mathcal{N}}\omega+F_{\mathcal{N}}(0)$.

However, they show in Arjevani et al. (2016, Thm. 5) that, for a method to converge to a stationary point of $v$, at least for convex problems, that is to say symmetric positive semi-definite $\nabla v$, $\mathcal{C}$ and $\mathcal{N}$ need to satisfy:

If $\mathcal{C}$ and $\mathcal{N}$ are polynomials, this equality for all symmetric positive semi-definite $\nabla v$ implies the equality on all matrices. Injecting this result in Eq. 175 yields the definition of 1-SCLI we used.

Appendix H Proofs of lower bounds

The class of methods we consider, that is to say the methods whose coefficient mappings $\mathcal{N}$ are any polynomial of degree at most $k-1$, is very general. It includes:

the $k^{\prime}$-extrapolation methods $F_{k^{\prime},\eta}$ for $k^{\prime}\leq k$ as defined by Eq. 5.

extrapolation methods with different step sizes for each extrapolation:

cyclic Richardson iterations (Opfer and Schober, 1984): methods whose update is composed of successive gradient steps with possibly different step sizes for each

and any combination of these with at most $k$ composed gradient evaluations.

The lemma below shows how $k$-extrapolation algorithms fit into the definition of $1$-SCLI:

For a $k$-extrapolation method, $\mathcal{N}(\nabla v)=-\eta\sum_{j=0}^{k-1}(-\eta\nabla v)^{k}$.

If $v$ has a stationary point $\omega^{*}$, evaluating at $\omega^{*}$ yields

Using that $v(\omega^{*})=0$ and so $(\nabla v)\omega^{*}=-v(0)$, one gets that

which yields the result for affine vector fields with a stationary point. In particular it holds for vector fields such that $\nabla v$ is non-singular. As the previous equality is continuous in $\nabla v$, by density of non-singular matrices, the result holds for all affine vector fields.

* To ease the presentation of the proof of the theorem, we rely on several lemmas. We first prove $(i)$ and $(ii)$ will follow as a consequence.

Recall the definition of $F_{\mathcal{N}}$, which is affine by assumption,

Then $\nabla F_{\mathcal{N}}=I_{d}+\mathcal{N}(\nabla v)\nabla v$. As $\mathcal{N}$is a polynomial, by the spectral mapping theorem (Thm. 11),

The right-hand side of Eq. 186 can be written as a constrained optimization problem as follows:

By weak duality, see Boyd and Vandenberghe (2004) for instance, we can lower bound the value of this problem by the value of its dual. So let us write the Lagrangian of this problem:

The Lagrangian is convex and quadratic so its minimum with respect to $t,a_{0},\dots,a_{k-1},z_{1},\dots,z_{m}$ is characterized by the first order condition. Moreover, if there is no solution to the first order condition, its minimum is $-\infty$ (see for instance Boyd and Vandenberghe (2004, Example 4.5)).

One has that, for any $1\leq j\leq m$ and $0\leq l\leq k-1$,

Setting these quantities to zero yields the following dual problem:

Taking $\nu_{j}\xi_{j}=\chi_{j}$ yields the result:

The next lemma concerns Vandermonde matrices and Lagrange polynomials.

Let $\lambda_{1},\dots,\lambda_{d}$ be distinct reals. Denote the Vandermonde matrix by

where $L_{1},L_{2},\dots,L_{d}$ are the Lagrange interpolation polynomials associated to $\lambda_{1},\dots,\lambda_{d}$ and $L_{j}=\sum_{l=0}^{d-1}L_{j}^{(l)}X^{l}$ for $1\leq j\leq d$.

A proof of this result can be found at Atkinson (1989, Theorem 3.1).

The next lemma is the last one before we finally prove the theorem. Recall that in Thm. 5 we assume that $k+1\leq d$.

Assume that $\operatorname*{Sp}\nabla v=\{\lambda_{1},\dots,\lambda_{k+1}\}$ where $\lambda_{1},\dots,\lambda_{k+1}$ are distinct non-zero reals. Then the problem of Eq. 186 is lower bounded by

where $L_{1},\dots,L_{k}$ are the Lagrange interpolation polynomials associated to $\lambda_{1},\dots,\lambda_{k}$.

To prove this lemma, we start from the result of Lem. 13 and we provide feasible $(\nu_{j})_{j}$ and $(\xi_{j})_{j}$. First, any feasible $(\nu_{j})_{j}$ and $(\xi_{j})_{j}$ must satisfy the $k$ constraints involving the powers of the eigenvalues, which can be rewritten as:

Using the previous lemma yields, for $1\leq j\leq k$,

Hence the problem can be rewritten only in terms of the $(\nu_{j})_{j}$ and $\xi_{k+1}$. Let $c_{j}=\frac{\lambda_{k+1}}{\lambda_{j}}L_{j}(\lambda_{k+1})$. The objective becomes:

Choosing $\xi_{k+1}=\frac{1-\sum_{j=1}^{k}c_{j}}{1+\sum_{j=0}^{k}\frac{\nu_{k+1}}{\nu_{j}}c_{j}^{2}}$ to maximize this quadratic yields:

Finally take $\nu_{j}=\frac{|c_{j}|}{1+\sum_{j=1}^{k}|c_{j}|}$ for $j\leq k$ and $\nu_{k+1}=\frac{1}{1+\sum_{j=1}^{k}|c_{j}|}$which satisfy the hypotheses of the problem of Lem. 13. With the feasible $(\nu_{j})_{j}$ and $(\xi_{j})_{j}$ defined this way, the value of the objective is

To prove the theorem, we build on the result of Lem. 15. We have to choose $\lambda_{1},\dots,\lambda_{k+1}\in[\mu,L]$ positive distinct such that Eq. 199 is big. One could try to distribute the eigenvalues uniformly across the interval but this leads to a lower bound which decreases exponentially in $k$. To make things a bit better, we use Chebyshev points of the second kind studied by Salzer (1971). However we will actually refer to the more recent presentation of Berrut and Trefethen (2004).

For now, assume that $k$ is even and so $k\geq 4$. We will only use that $d-1\geq k$ (and not that $d-2\geq k$). Define, for $1\leq j\leq k$, $\lambda_{j}=\frac{\mu+L}{2}-\frac{L-\mu}{2}\cos{\frac{j-1}{k-1}\pi}$. Using the barycentric formula of Berrut and Trefethen (2004, Eq. 4.2), the polynomial which interpolates $f_{1},\dots,f_{k}$ at the points $\lambda_{1},\dots,\lambda_{k}$ can be written as:

Define $Z(X)=\sum_{j=1}^{k}\frac{w_{j}}{X-\lambda_{j}}$.

Now, $\sum_{j=1}^{k}\frac{\lambda_{k+1}}{\lambda_{j}}L_{j}(\lambda_{k+1})$ can be seen as the polynomial interpolating $\frac{\lambda_{k+1}}{\lambda_{1}},\dots,\frac{\lambda_{k+1}}{\lambda_{k}}$ at the points $\lambda_{1},\dots,\lambda_{j}$ evaluated at $\lambda_{k+1}$. Hence, using the barycentric formula,

Similarly, $\sum_{j=1}^{k}|\frac{\lambda_{k+1}}{\lambda_{j}}L_{j}(\lambda_{k+1})|$ can be seen as the polynomial interpolating $|\frac{\lambda_{k+1}}{\lambda_{1}}|\operatorname*{sign}(L_{1}(\lambda_{k+1})),\dots,|\frac{\lambda_{k+1}}{\lambda_{k}}|\operatorname*{sign}(L_{k}(\lambda_{k+1}))$ at the points $\lambda_{1},\dots,\lambda_{j}$ evaluated at $\lambda_{k+1}$. However, from Berrut and Trefethen (2004, Section 3),

and by Berrut and Trefethen (2004, Eq. 4.1),

Therefore, using the barycentric formula again,

Now take any $\lambda_{k+1}$ such that $\lambda_{1}<\lambda_{k+1}<\lambda_{2}$. Then, from Eq. 210, $\operatorname*{sign}Z(\lambda_{k+1})=(-1)^{k+1}=-1$ as we assume that $k$ is even. By definition of the coefficients $w_{j}$, $\operatorname*{sign}\frac{w_{1}}{\lambda_{k+1}-\lambda_{1}}=+1$. Hence $1+\operatorname*{sign}Z(\lambda_{k+1})\operatorname*{sign}\frac{w_{1}}{\lambda_{k+1}-\lambda_{1}}=0$. Similarly, $\operatorname*{sign}\frac{w_{2}}{\lambda_{k+1}-\lambda_{2}}=+1$ and so $1+\operatorname*{sign}Z(\lambda_{k+1})\operatorname*{sign}\frac{w_{2}}{\lambda_{k+1}-\lambda_{2}}=0$ tooWe could do without this, but it is free and gives slightly better constants..

As the quantity inside the parentheses of Eq. 215 is non-negative, we can focus on lower bounding it. Using the considerations on signs we get:

where we used that, for $j\geq 3$, $\left|\frac{1}{\lambda_{k+1}-\lambda_{j}}\right|\frac{\lambda_{k+1}}{\lambda_{j}}\leq\left|\frac{1}{\lambda_{k+1}-\lambda_{3}}\right|\frac{\lambda_{k+1}}{\lambda_{3}}$ as $\lambda_{1}<\lambda_{k+1}<\lambda_{2}<\lambda_{3}<\dots<\lambda_{k}$. Now, recalling that $\lambda_{1}=\mu$, and using that $\lambda_{1}<\lambda_{k+1}<\lambda_{2}<\lambda_{3}$ for the inequality,

by definition of the interpolation points. Now, for $k\geq 4$, the sinus is non-negative on $[\frac{\pi}{k-1},\frac{2\pi}{k-1}]$ and reaches its minimum at $\frac{\pi}{k-1}$. Hence,

as $0\geq\frac{\pi}{k-1}\geq\frac{\pi}{2}$. Putting everything together yields,

which yields the desired result by the definition of the problem of Eq. 186.

Now, we tackle the case $k$ odd, with $k\geq 3$ and $d-1\geq k+1$. Note that if $\mathcal{N}$ is a real polynomial of degree at most $k-1$, it is also a polynomial of degree at most $(k+1)-1$. Applying the result above yields that there exists $v\in\mathcal{V}_{d}$ with the desired properties such that,

Hence, $(i)$ holds for any $d-2\geq k\geq 3$. ∎

Then, $(ii)$ is essentially a corollary of $(i)$.

For a square zero-sum two player game, the Jacobian of the vector field can be written as,

Moreover, by computing $\nabla v^{T}\nabla v$ and using that $\operatorname*{Sp}AA^{T}=\operatorname*{Sp}A^{T}A$, one gets that $\min_{\lambda\in\operatorname*{Sp}\nabla v}|\lambda|=\sigma_{min}(\nabla v)=\sigma_{min}(A)\geq\gamma$ and $\sigma_{max}(\nabla v)=\sigma_{max}(A)\leq L$. ∎

Interestingly, the examples we end up using have a spectrum similar to the one of the matrix Nesterov uses in the proofs of his lower bounds in Nesterov (2004). The choice of the spectrum of the Jacobian of the vector field was indeed the choice of interpolation points. Following Salzer (1971); Berrut and Trefethen (2004) we used points distributed across the interval as a cosinus as it minimizes oscillations near the edge of the interval. Therefore, this links the hardness Nesterov’s examples to the well-conditioning of families of interpolation points.

Appendix I Handling singularity

The following theorem is a way to use spectral techniques to obtain geometric convergence rates even if the Jacobian of the vector field at the stationary point is singular. We only need to ensure that the vector field is locally null along these directions of singularity.

The following theorem is actually a combination of the proof of Nagarajan and Kolter (2017, Thm. A.4), which only proves asymptotic statibility in continuous time with no concern for the rate, and the classic Thm. 1.

Let $\rho^{*}=\rho(\nabla_{\theta}(\operatorname*{Id}+h_{\theta})(0,0))$ and define the iterates $(\theta_{t},\varphi_{t})_{t}$ by

Then, if $\rho^{*}<1$, for all $\epsilon>0$, there exists a neighborhood of $(0,0)$ such that for any initial point in this neighborhood, the distance of the iterates $(\theta_{t},\varphi_{t})_{t}$ to a stationary point of $h$ decreases as $\mathcal{O}((\rho^{*}+\epsilon)^{t})$ . If $v$ is linear, this is satisfied with the whole space as a neighborhood for all $\epsilon>0$.

The following proof is inspired from the ones of Nagarajan and Kolter (2017, Thm. 4) and Gidel et al. (2019b, Thm. 1).

We first show that, for all $\eta>0$ there exists $\tau\geq\delta>0$ such that,

The interesting thing here is that we are completely getting rid of the dependence on $\varphi$, both in the linearization and in the bound.

Let $\varphi\in B_{p}(0,\tau)$. Then, using that $h(0,\varphi)=0$, the Taylor development of $h(\theta,\varphi)$ w.r.t. to $\theta$ yields:

Hence, for $\theta\in B(0,\frac{\eta}{2c})$, we get that:

Concerning the other term, by continuity, $\nabla_{\theta}h(0,\varphi)-\nabla_{\theta}h(0,0)$ goes to zero as $\varphi$ goes to zero. Hence, there exists $\delta>0$, $\delta\leq\min(\tau,\frac{\eta}{2c})$ such that for any $\varphi\in B_{p}(0,\delta)$, $\|(\nabla_{\theta}h(0,\varphi)-\nabla_{\theta}h(0,0))\theta\|\leq\frac{\eta}{2}\|\theta\|$. Combining the two bounds yields the desired result.

We now apply the previous result with $\eta=\epsilon/2$. We first examine what this means for $(\theta_{t+1},\varphi_{t+1})$ when $(\theta_{t},\varphi_{t})$ is in $B_{m+p}((0,0),\delta)$. However, the neighborhood $B_{m+p}((0,0),\delta)$ is not necessarily stable, so we will again restrict it afterwards. See the proof (Nagarajan and Kolter, 2017, Thm. 4) for a more detailed discussion on this. Assume for now that $(\theta_{t},\varphi_{t})\in B_{m+p}((0,0),\delta)$. Then,

Consider now the other coordinate $\varphi_{t+1}$, still under the assumption that $(\theta_{t},\varphi_{t})\in B_{m+p}((0,0),\delta)$. Then,

Assume $(\theta_{0},\varphi_{0})\in V$. By construction, $(\theta_{0},\varphi_{0})\in B_{m+p}((0,0),\delta)$. Now assume that $(\theta_{0},\varphi_{0}),(\theta_{1},\varphi_{1}),\dots,(\theta_{t},\varphi_{t})$ are in $B_{m+p}((0,0),\delta)$ for some $t\geq 0$. By what has been proven above, first, $\|\theta_{t+1}\|\leq(\rho^{*}+\epsilon)^{t+1}\|\theta_{0}\|\leq\|\theta_{0}\|$. Then,

Hence, putting the two coordinates together,

by definition of $V$. Hence, $(\theta_{t+1},\varphi_{t+1})\in B_{m+p}((0,0),\delta)$ which concludes the induction and the proof.

By a linear base change, we get the more practical corollary:

Then, for all $\epsilon>0$, for any $\omega_{0}$ in a neighborhood of $\omega^{*}$, the distance of the iterates $(\omega_{t})^{t}$ to fixed points of $F$ decreases in $\mathcal{O}((\rho^{*}+\epsilon)^{t})$.

Moreover, if $F$ is linear, we can take this neighborhood to be the whole space and $\epsilon=0$.

We consider the spaces $\operatorname*{Ker}(\nabla F(\omega^{*})-\lambda I_{d})^{m_{\lambda}}$, $\lambda\in\operatorname*{Sp}\nabla F(\omega^{*})$ where $m_{\lambda}$ denotes the multiplicity of the eigenvalue $\lambda$ as root of the characteristic polynomial of $\nabla F(\omega^{*})$. Then, we have,

In general the condition $\operatorname*{Ker}(\nabla F(\omega^{*})-I_{d})^{2}=\operatorname*{Ker}(\nabla F(\omega^{*})-I_{d})$ will be equivalent to $\operatorname*{Ker}\nabla v(\omega^{*})^{2}=\operatorname*{Ker}\nabla v(\omega^{*})$ where $v$ is the game vector field. We keep this remark informal but we prove this for extragradient below as an example. Indeed, as seen with $1-SCLI$ in Section 3.3 with Eq. 2, $\nabla F(\omega^{*})$ is of the form $\operatorname*{Id}+\mathcal{N}(\nabla v(\omega^{*}))\nabla v(\omega^{*})$ where $\mathcal{N}$ is a polynomial. Hence, $(\nabla F(\omega^{*})-I_{d})^{j}=\mathcal{N}(\nabla v(\omega^{*}))^{j}\nabla v(\omega^{*})^{j}$. Moreover, in practice, $\mathcal{N}(\nabla v(\omega^{*}))$ will be chosen — e.g. by the choice of the step-size — to be non-singular. Hence, $\operatorname*{Ker}(\nabla F(\omega^{*})-I_{d})^{j}=\operatorname*{Ker}\nabla v(\omega^{*})^{j}$ and so $\operatorname*{Ker}(\nabla F(\omega^{*})-I_{d})^{2}=\operatorname*{Ker}(\nabla F(\omega^{*})-I_{d})$ will be equivalent to $\operatorname*{Ker}\nabla v(\omega^{*})^{2}=\operatorname*{Ker}\nabla v(\omega^{*})$.

We now prove a lemma concerning extragradient which as a first step before apply Cor. 4. We could have proven this result for $k$-extrapolation methods but we focus on extragradient for simplicity.