Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

Introduction

In classic (normal form) zero-sum games, one has to compute two probability vectors $\mathbf{x}^{*}\in\Delta_{n},\mathbf{y}^{*}\in\Delta_{m}$ $\Delta_{n}$ denotes the simplex of size $n$. that consist an equilibrium of the following problem

where $A$ is $n\times m$ real matrix (called payoff matrix). Here $\mathbf{x}^{\top}A\mathbf{y}$ represents the payment of the $\mathbf{x}$ player to the $\mathbf{y}$ player under choices of strategies by the two players and is a bilinear function.

Arguably, one of the most celebrated theorems and a founding stone in Game Theory, is the minimax theorem by Von Neumann . It states that

Soon after the appearance of the minimax theorem, research was focused on dynamics for solving min-max optimization problems by having the min and max players of (1) run a simple online learning procedure. In the online learning framework, at time $t$, each player chooses a probability distribution ($\mathbf{x}^{t},\mathbf{y}^{t}$ respectively) simultaneously depending only on the past choices of both players (i.e., $\mathbf{x}^{1},...,\mathbf{x}^{t-1},\mathbf{y}^{1},...,\mathbf{y}^{t-1}$) and experiences payoff that depends on choices $\mathbf{x}^{t},\mathbf{y}^{t}$.

An early method, proposed by Brown and analyzed by Robinson , was fictitious play. Later on, researchers discover several learning robust algorithms converging to minimax equilibrium at faster rates, see . This class of learning algorithms, are the so-called “no-regret” and include Multiplicative Weights Update method and Follow the regularized leader.

Despite the rich literature on no-regret learning, most of the known results have the feature that min-max equilibrium is shown to be attained only by the time average. This means that the trajectory of a no-regret learning method $(\mathbf{x}^{t},\mathbf{y}^{t})$ has the property that ${1\over t}\sum_{\tau\leq t}{\mathbf{x}^{\tau}}^{\top}A\mathbf{y}^{\tau}$ converges to the equilibrium of (1), as $t\rightarrow\infty$. Unfortunately that does not mean that the last iterate $(\mathbf{x}^{t},\mathbf{y}^{t})$ converges to an equilibrium, it commonly diverges or cycles. One such example is the well-known Multiplicative Weights Update Algorithm, the time average of which is known to converge to an equilibrium, but the actual trajectory cycles towards the boundary of the simplex (). This is even true for the vanilla Gradient Descent/Ascent, where one can show for even bilinear landscapes (unconstrained case) last iterate fails to converge .

2 Main Results

In this paper, we focus on the min-max optimization problem

where $f$ is a convex-concave function (convex in $\mathbf{x}$, concave in $\mathbf{y}$). We analyze the no-regret online algorithm Optimistic Multiplicative Weights Update (OMWU). OMWU is an instantiation of the Optimistic Follow the Regularized Leader (OFTRL) method with entropy as a regularizer (for both players, see Preliminaries section for the definition of OMWU).

We prove that OMWU exhibits local last iterate convergence, generalizing the result of and proving an open question of (for convex-concave games). Formally, our main theorem is stated below:

where $(\mathbf{x}^{t},\mathbf{y}^{t})$ denotes the $t$-th iterate of OMWU.

Moreover, we complement our theoretical findings with experimental analysis of the procedure. The experiments on KL-divergence indicate that the results should hold globally.

3 Structure and Technical Overview

We present the structure of the paper and a brief technical overview.

Section 2 provides necessary definitions, the explicit form of OMWU derived from OFTRL with entropy regularizer, and some existing results on dynamical systems.

Section 3 is the main technical part, i.e, the computation and spectral analysis of the Jacobian matrix of OMWU dynamics. The stability analysis, the understanding of the local behavior and the local convergence guarantees of OMWU rely on the spectral analysis of the computed Jacobian matrix. The techniques for bilinear games (as in ) are no longer valid in convex-concave games. Allow us to explain the differences from . In general, one cannot expect a trivial generalization from linear to non-linear scenarios. The properties of bilinear games are fundamentally different from that of convex-concave games, and this makes the analysis much more challenging in the latter. The key result of spectral analysis in is in a lemma (Lemma B.6) which states that a skew symmetric $A$ is skew symmetric if $A^{\top}=-A$. has imaginary eigenvalues. Skew symmetric matrices appear since in bilinear cases there are terms that are linear in $\mathbf{x}$ and linear in $\mathbf{y}$ but no higher order terms in $\mathbf{x}$ or $\mathbf{y}$. However, the skew symmetry has no place in the case of convex-concave landscapes and the Jacobian matrix of OMWU is far more complicated. One key technique to overcome the lack of skew symmetry is the use of Ky Fan inequality which states that the sequence of the eigenvalues of $\frac{1}{2}(W+W^{\top})$ majorizes the real part of the sequence of the eigenvalues of W for any square matrix W (see Lemma 3.1).

Section 4 focuses on numerical experiments to understand how the problem size and the choice of learning rate affect the performance of our algorithm. We observe that our algorithm is able to achieve global convergence invariant to the choice of learning rate, random initialization or problem size. As comparison, the latest popularized (projected) optimistic gradient descent ascent is much more sensitivity to the choice of hyperparameter. Due to space constraint, the detailed calculation of the Jacobian matrix (general form and at fixed point) of OMWU are left in Appendix.

The boldface $\mathbf{x}$ and $\mathbf{y}$ denote the vectors in $\Delta_{n}$ and $\Delta_{m}$. $\mathbf{x}^{t}$ denotes the $t$-th iterate of the dynamical system. The letter $J$ denote the Jacobian matrix. $\mathbf{I}$, $\mathbf{0}$ and $\mathbf{1}$ are preserved for the identity, zero matrix and the vector with all the entries equal to 1. The support of $\mathbf{x}$ is the set of indices of $x_{i}$ such that $x_{i}\neq 0$, denoted by $\textrm{Supp}(\mathbf{x})$. $(\mathbf{x}^{*},\mathbf{y}^{*})$ denotes the optimal solution for minimax problem. $[n]$ denote the set of integers $\{1,...,n\}$.

Preliminaries

In this section, we present some background that will be used later.

From Von Neumann’s minimax theorem, one can conclude that the problem $\min_{\mathbf{x}\in\Delta_{n}}\max_{\mathbf{y}\in\Delta}f(\mathbf{x},\mathbf{y})$ has always an equilibrium $(\mathbf{x}^{*},\mathbf{y}^{*})$ with $f(\mathbf{x}^{*},\mathbf{y}^{*})$ be unique. Moreover from KKT conditions (as long as $f$ is twice differentiable), such an equilibrium must satisfy the following ($\mathbf{x}^{*}$ is a local minimum for fixed $\mathbf{y}=\mathbf{y}^{*}$ and $\mathbf{y}^{*}$ is a local maximum for fixed $\mathbf{x}=\mathbf{x}^{*}$):

For the rest of the paper we assume no degeneracies, i.e., the last inequalities hold strictly (in the case a strategy is played with zero probability for each player). Moreover, it is easy to see that since $f$ is convex concave and twice differentiable, then $\nabla^{2}_{\mathbf{x}\mathbf{x}}f$ (part of the Hessian that involves $\mathbf{x}$ variables) is positive semi-definite and $\nabla^{2}_{\mathbf{y}\mathbf{y}}f$ (part of the Hessian that involves $\mathbf{y}$ variables) is negative semi-definite.

2 Optimistic Multiplicative Weights Update

$\eta$ is called the stepsize of the online algorithm. OFTRL is uniquely defined if $f$ is convex-concave and domains $\mathcal{X}$ and $\mathcal{Y}$ are convex. For simplex constraints and entropy regularizers, i.e., $h_{1}(\mathbf{x})=\sum_{i}x_{i}\ln x_{i},h_{2}(\mathbf{y})=\sum_{i}y_{i}\ln y_{i}$, we can solve for the explicit form of OFTRL using KKT conditions, the update rule is the Optimistic Multiplicative Weights Update (OMWU) and is described as follows:

3 Fundamentals of Dynamical Systems

We conclude Preliminaries section with some basic facts from dynamical systems.

Using KKT conditions (4), it is not hard to observe that an equilibrium point $(\mathbf{x}^{*},\mathbf{y}^{*})$ must be a fixed point of the OMWU algorithm, i.e., if $(\mathbf{x}^{t},\mathbf{y}^{t})=(\mathbf{x}^{t-1},\mathbf{y}^{t-1})=(\mathbf{x}^{*},\mathbf{y}^{*})$ then $(\mathbf{x}^{t+1},\mathbf{y}^{t+1})=(\mathbf{x}^{*},\mathbf{y}^{*})$.

Assume that $w$ is a differentiable function and the Jacobian of the update rule $w$ at a fixed point $\mathbf{z}^{*}$ has spectral radius less than one. It holds that there exists a neighborhood $U$ around $\mathbf{z}^{*}$ such that for all $\mathbf{z}^{0}\in U$, the dynamics $\mathbf{z}^{t+1}=w(\mathbf{z}^{t})$ converges to $\mathbf{z}^{*}$, i.e. $\lim_{n\rightarrow\infty}w^{n}(\mathbf{z}^{0})=\mathbf{z}^{*}$ $w^{n}$ denotes the composition of $w$ with itself $n$ times.. $w$ is called a contraction mapping in $U$.

Note that we will make use of Proposition 2.5 to prove our Theorem 1.1 (by proving that the Jacobian of the update rule of OMWU has spectral radius less than one).

Last iterate convergence of OMWU

In this section, we prove that OMWU converges pointwise (exhibits last iterate convergence) if the initializations $(\mathbf{x}^{0},\mathbf{y}^{0}),(\mathbf{x}^{1},\mathbf{y}^{1})$ belong in a neighborhood $U$ of the equilibrium $(\mathbf{x}^{*},\mathbf{y}^{*})$.

We first express OMWU algorithm as a dynamical system so that we can use Proposition 2.5. The idea (similar to ) is to lift the space to consist of four components $(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w}$, in such a way we can include the history (current and previous step, see Section 2.2 for the equations). First, we provide the update rule $g:\Delta_{n}\times\Delta_{m}\times\Delta_{n}\times\Delta_{m}\to\Delta_{n}\times\Delta_{m}\times\Delta_{n}\times\Delta_{m}$ of the lifted dynamical system and is given by

where $g_{i}=g_{i}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})$ for $i\in$ are defined as follows:

Then the dynamical system of OMWU can be written in compact form as

In what follows, we will perform spectral analysis on the Jacobian of the function $g$, computed at the fixed point $(\mathbf{x}^{*},\mathbf{y}^{*})$. Since $g$ has been lifted, the fixed point we analyze is $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ (see Remark 2.4). By showing that the spectral radius is less than one, our Theorem 1.1 follows by Proposition 2.5. The computations of the Jacobian of $g$ are deferred to the supplementary material.

2 Spectral Analysis

Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be the equilibrium of min-max problem (2). Assume $i\notin\textrm{Supp}(\mathbf{x}^{*})$, i.e., $x_{i}^{*}=0$ then (see equations at the supplementary material, section A)

and all other partial derivatives of $g_{1,i}$ are zero, thus $\frac{e^{-\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{n}x^{*}_{t}e^{-\eta\frac{\partial f}{\partial x_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}$ is an eigenvalue of the Jacobian computed at $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$. This is true because the row of the Jacobian that corresponds to $g_{1,i}$ has zeros everywhere but the diagonal entry. Moreover because of the degeneracy assumption of KKT conditions (see Remark 2.2), it holds that

Similarly, it holds for $j\notin\textrm{Supp}(\mathbf{y}^{*})$ that

(again by Remark 2.2) and all other partial derivatives of $g_{2,j}$ are zero, therefore $\frac{e^{\eta\frac{\partial f}{\partial y_{j}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{m}y^{*}_{t}e^{\eta\frac{\partial f}{\partial y_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}$ is an eigenvalue of the Jacobian computed at $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$.

We focus on the submatrix of the Jacobian of $g$ computed at $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ that corresponds to the non-zero probabilities of $\mathbf{x}^{*}$ and $\mathbf{y}^{*}$. We denote $D_{\mathbf{x}^{*}}$ to be the diagonal matrix of size $\left|\text{Supp}(\mathbf{x}^{*})\right|\times\left|\text{Supp}(\mathbf{x}^{*})\right|$ that has on the diagonal the nonzero entries of $\mathbf{x}^{*}$ and similarly we define $D_{\mathbf{y}^{*}}$ of size $\left|\text{Supp}(\mathbf{y}^{*})\right|\times\left|\text{Supp}(\mathbf{y}^{*})\right|$. For convenience, let us denote $k_{x}:=\left|\text{Supp}(\mathbf{x}^{*})\right|$ and $k_{y}:=\left|\text{Supp}(\mathbf{y}^{*})\right|$. The Jacobian submatrix is the following

The characteristic polynomial of $J_{\text{new}}$ is obtained by finding $\det(J_{\text{new}}-\lambda\mathbf{I})$. One can perform row/column operations on $J_{\text{new}}$ to calculate this determinant, which gives us the following relation:

where $q(\lambda)$ is the characteristic polynomial of the following matrix

and $B_{11},B_{12},A_{12},A_{21}$ are the aforementioned sub-matrices. Notice that $J_{\text{small}}$ can be written as

Notice here that $H$ is the Hessian matrix evaluated at the fixed point $(\mathbf{x}^{*},\mathbf{y}^{*})$, and is the appropriate sub-matrix restricted to the support of $\left|\text{Supp}(\mathbf{y}^{*})\right|$ and $\left|\text{Supp}(\mathbf{x}^{*})\right|$. Although, the Hessian matrix is symmetric, we would like to work with the following representation of $J_{\text{small}}$:

Let us denote any non-zero eigenvalue of $J_{\text{small}}$ by $\epsilon$ which may be a complex number. Thus $\epsilon$ is where $q(\cdot)$ vanishes and hence the eigenvalue of $J_{\text{new}}$ must satisfy the relation

We are to now show that the magnitude of any eigenvalue of $J_{\text{new}}$ is strictly less than 1, i.e, $\left|\lambda\right|<1$. Trivially, $\lambda=\frac{1}{2}$ satisfies the above condition. Thus we need to show that the magnitude of $\lambda$ where $q(\cdot)$ vanishes is strictly less than 1. The remainder of the proof proceeds by showing the following two lemmas:

Let $\lambda$ be an eigenvalue of matrix $J_{\text{small}}$. It holds that $\textrm{Re}(\lambda)\leq 0$.

Assume that $\lambda\neq 0$. All the non-zero eigenvalues of matrix $J_{\text{small}}$ coincide with the eigenvalues of the matrix

is positive semi-definite. Moreover, we use KyFan inequalities which state that the sequence (in decreasing order) of the eigenvalues of $\frac{1}{2}(W+W^{\top})$ majorizes the real part of the sequence of the eigenvalues of $W$ for any square matrix $W$ (see , page 4). We conclude that for any eigenvalue $\lambda$ of $R$, it holds that $\textrm{Re}(\lambda)$ is at most the maximum eigenvalue of $\frac{1}{2}(R+R^{\top})$. Observe now that

by the convex-concave assumption on $f$ it follows that the matrix above is negative semi-definite (see Remark 2.2) and so is $R+R^{\top}$. We conclude that the maximum eigenvalue of $R+R^{\top}$ is non-positive. Therefore any eigenvalue of $R$ has real part non-positive and the same is true for $J_{\textrm{small}}$. ∎

If $\epsilon$ is a non-zero eigenvalue of $J_{\text{small}}$ then, $\textrm{Re}(\epsilon)\leq 0$ and $\left|\epsilon\right|\downarrow 0$ as the stepsize $\eta\to 0$.

We first can see that $\eta$ which is the learning rate multiplies any eigenvalue and we may assume that whilst $\eta$ is positive, it may be chosen to be sufficiently small and hence the magnitude of any eigenvalue $\left|\epsilon\right|\downarrow 0$.

The equation $\epsilon=\frac{\lambda(\lambda-1)}{2\lambda-1}$ determines two complex roots for each fixed $\epsilon$, say $\lambda_{1}$ and $\lambda_{2}$. The relation between $\left|\epsilon\right|$, $\left|\lambda_{1}\right|$ and $|\lambda_{2}|$ is illustrated in Figure 2, where the $x$-axis is taken to be $\propto\exp(1/\left|\epsilon\right|)$. Specifically we choose $\epsilon=-1/\log(x)+1/\log(x)\sqrt{-1}$ that satisfies $|\epsilon|\downarrow 0$ as $x\rightarrow\infty$ (The $x$-axis of Figure 2 takes $x$ from 3 to 103).

Let $\lambda=x+\sqrt{-1}y$ and $\epsilon=a+\sqrt{-1}b$. The relation $\frac{\lambda(\lambda-1)}{2\lambda-1}=\epsilon$ gives two equations based on the equality of real and imaginary parts as follows,

Notice that the above equations can be transformed to the following forms:

For each $\epsilon=a+\sqrt{-1}b$, there exist two pairs of points $(x_{1},y_{1})$ and $(x_{2},y_{2})$ that are the intersections of the above two hyperbola, illustrated in Figure 4. Recall the condition that $a<0$. As $\left|\epsilon\right|\rightarrow 0$, the hyperbola can be obtained from the translation by $(\frac{2a+1}{2},b)$ of the hyperbola

where the translated symmetric center is close to $(\frac{1}{2},0)$ since $(a,b)$ is close to $(0,0)$. So the two intersections of the above hyperbola, $(x_{1},y_{1})$ and $(x_{2},y_{2})$, satisfy the property that $x_{1}^{2}+y_{1}^{2}$ is small and $x_{2}>\frac{1}{2}$ since the two intersections are on two sides of the axis $x=\frac{2a+1}{2}$, as showed in Figure 3.

and then the condition $a<0$ gives the inequality

where only the case $x>\frac{1}{2}$ is considered since if the intersection whose $x$-component satisfying $x<\frac{1}{2}$ has the property that $x^{2}+y^{2}$ is small and then less than 1, Figure 4. Thus to prove that $\left|\lambda\right|<1$, it suffices to assume $x>\frac{1}{2}$. It is obvious that $x^{2}-x+y^{2}=(x-\frac{1}{2})^{2}+y^{2}-\frac{1}{4}<0$ implies that $x^{2}+y^{2}<1$. The proof completes. ∎

Experiments

In this section, we conduct empirical studies to verify the theoretical results of our paper. We primarily target to understand two factors that influence the convergence speed of OMWU: the problem size and the learning rate. We also compare our algorithm with Optimistic Gradient Descent Ascent (OGDA) with projection, and demonstrate our superiority against it.

We start with a simple bilinear min-max game:

To understand how learning rate affects the speed of convergence, we conduct similar experiments on Eqn. (14) and plot the $l_{1}$ error with different step sizes in Figure 5(a)-(c). For this experiment the matrix size is fixed as $n=100$. We also include a comparison with the Optimistic Gradient Descent Ascent. Notice the original proposal was for unconstrained problems and we use projection in each step in order to constrain the iterates to stay inside the simplex. For the setting we considered, we observe a larger learning rate effectively speeds up our learning process, and our algorithm is relatively more stable to the choice of step-size. In comparison, OGDA is quite sensitive to the choice of step-size. As shown in Figure 5(b), a larger step-size makes the algorithm diverge, while a smaller step-size will make very little progress. Furthermore, we also choose to perform our algorithm over a convex-concave but not bilinear function $f(\mathbf{x},\mathbf{y})=x_{1}^{2}-y_{1}^{2}+2x_{1}y_{1}$, where $\mathbf{x},\mathbf{y}\in\Delta_{2}$ and $x_{1}$ and $y_{1}$ are the first coefficients of $\mathbf{x}$ and $\mathbf{y}$. With this low dimensional function, we could visually show the convergence procedure as in Figure 5(b), where each arrow indicates an OMWU step. This figure demonstrates that at least in this case, a larger step size usually makes sure a bigger progress towards the optimal solution.

Finally we show how the KL divergence $D_{KL}((\mathbf{x}^{*},\mathbf{y}^{*})\parallel(\mathbf{x}^{t},\mathbf{y}^{t}))$ decreases under different circumstances. Figure 6 again considers the bilinear problem (Eqn.(14)) with multiple dimensions $n$ and a simple convex-concave function $f(\mathbf{x},\mathbf{y})=x_{1}^{2}-y_{1}^{2}+2x_{1}y_{1}$ with different learning rate. We note that in all circumstances we consider, we observe that OMWU is very stable, and achieves global convergence invariant to the problem size, random initialization, and learning rate.

Conclusion

In this paper we analyze the last iterate behavior of a no-regret learning algorithm called Optimistic Multiplicative Weights Update for convex-concave landscapes. We prove that OMWU exhibits last iterate convergence in a neighborhood of the fixed point of OMWU algorithm, generalizing previous results that showed last iterate convergence for bilinear functions. The experiments explores how the problem size and the choice of learning rate affect the performance of our algorithm. We find that OMWU achieves global convergence and less sensitive to the choice of hyperparameter, compared to projected optimistic gradient descent ascent.

References

Appendix A Equations of the Jacobian of OMWU

In this section, we compute the equations of the Jacobian at the fixed point $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{z}^{*},\mathbf{w}^{*})$. The fact that $(\mathbf{x}^{*},\mathbf{y}^{*})=(\mathbf{z}^{*},\mathbf{w}^{*})$ and $(\mathbf{z},\mathbf{w})$ takes the position of $(\mathbf{x},\mathbf{y})$ in computing partial derivatives gives the following equations.

Appendix C Jacobian matrix at (𝐱∗,𝐲∗,𝐳∗,𝐰∗)(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{z}^{*},\mathbf{w}^{*})

By acting on the tangent space of each simplex, we observe that $D_{\mathbf{x}^{*}}\mathbf{1}\mathbf{1}^{\top}\mathbf{v}=0$ for $\sum_{k}v_{k}=0$, so each eigenvalue of matrix $J$ is an eigenvalue of the following matrix

The characteristic polynomial of $J_{\text{new}}$ is $\det(J_{new}-\lambda I)$ that can be computed as the determinant of the following matrix: