Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

Introduction

The surge of recent breakthroughs in artificial intelligence (AI) has sparked significant interest in solving optimization problems that are universally considered hard. Accordingly, the need for an effective theory has two different sides: first, a deeper theoretical understanding would help demystify the reasons behind the success and/or failures of different training algorithms; second, theoretical advances can inspire effective algorithmic tweaks leading to concrete performance gains.

Deep learning has been an area of AI where theory has provided a significant boost. As a functional class, deep learning involves non-convex loss functions for which finding even local optima is NP-hard; nevertheless, elementary techniques such as gradient descent (and other first-order methods) seem to work fairly well in practice. For this class of problems, recent theoretical results have indeed provided useful insights: using tools from the theory of dynamical systems, Lee et al. (2016, 2017) and Panageas and Piliouras (2017) showed that a wide variety of first-order methods (including gradient descent and mirror descent) almost always avoid saddle points. More generally, the optimization and machine learning communities alike have dedicated significant effort in understanding the geometry of non-convex landscapes by searching for properties which could be leveraged for efficient training. For example, the well-known “strict saddle” property was shown to hold in a wide range of salient objective functions ranging from low-rank matrix factorization (Ge et al., 2016, 2017; Bhojanapalli et al., 2016) and dictionary learning (Sun et al., 2017b, a), to principal component analysis (Ge et al., 2015), phase retrieval (Sun et al., 2016), and many other models.

On the other hand, adversarial deep learning is nowhere near as well understood, especially in the case of GANs (Goodfellow et al., 2014). Despite an immense amount of recent scrutiny, our theoretical understanding cannot boast similar breakthroughs as in the case of “single-agent” deep learning. To make matters worse, GANs are notoriously hard to train and standard optimization methods often fail to converge to a reasonable solution. Because of this, a considerable corpus of work has been devoted to exploring and enhancing the stability of GANs, including techniques as diverse as the use of Wasserstein metrics (Arjovsky et al., 2017), critic gradient penalties (Gulrajani et al., 2017), different activation functions in different layers, feature matching, minibatch discrimination, etc. (Radford et al., 2015; Salimans et al., 2016).

A key observation in this context is that first-order methods may fail to converge even in toy, bilinear zero-sum games like Rock-Paper-Scissors and Matching Pennies (Piliouras and Shamma, 2014; Papadimitriou and Piliouras, 2016; Daskalakis et al., 2018; Mescheder et al., 2018; Mertikopoulos et al., 2018; Bailey and Piliouras, 2018). This is a critical failure of descent methods, but one which Daskalakis et al. (2018) showed can be overcome through “optimism”, interpreted in this context as a momentum adjustment that pushes the training process one step further along the incumbent gradient. In particular, Daskalakis et al. (2018) showed that OGD succeeds in cases where vanilla gradient descent (GD) fails (specifically, unconstrained bilinear saddle-point problems), and leveraged this theoretical result to improve the training of GANs.

A common theme in the above is that, to obtain a principled methodology for training GANs, it is beneficial to first establish improvements in a more restricted setting, and then test whether these gains carry over to more demanding learning environments. Following these theoretical breadcrumbs, we focus on a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality, a property which we call coherence. Then, motivated by the success of mirror descent (MD) methods in online/stochastic convex programming, and hoping to overcome the shortcomings of ordinary gradient descent by exploiting the problem’s geometry, we examine the convergence of MD in coherent problems. On the positive side, we show that if a problem is strictly coherent (a condition that is satisfied by all strictly monotone problems), MD converges almost surely, even in stochastic problems (Theorem 3.1). However, under null coherence (the “saturated” opposite to strict coherence), MD spirals outwards from the problem’s solutions and may cycle in perpetuity, even with perfect gradient feedback. The null coherence property covers all bilinear models, so this result generalizes and extends the recent analysis of Daskalakis et al. (2018) and Bailey and Piliouras (2018) for gradient descent and follow-the-regularized-leader (FTRL) respectively (for a schematic illustration, see Figs. 1 and 5). Thus, in and by themselves, gradient/mirror descent methods do not suffice for training convoluted, adversarial deep learning models.

To mitigate this deficiency, we introduce an extra-gradient step which allows the algorithm to look ahead and take an “optimistic” mirror step along a “future” gradient. Following Rakhlin and Sridharan (2013), this method is known as optimistic mirror descent (OMD), and was first studied under the name “mirror-prox” by Nemirovski (2004). In convex-concave problems, Nemirovski (2004) showed that the so-called “ergodic average” of the algorithm’s iterates enjoys an $\operatorname{\mathcal{O}}(1/n)$ convergence rate. In the context of GAN training, Gidel et al. (2018) further introduced a “gradient reuse” mechanism to minimize the computational overhead of back-propagation and proved convergence in stochastic convex-concave problems. However, beyond the monotone regime, averaging offers no tangible benefits because Jensen’s inequality no longer applies; as a result, moving closer to GANs requires changing both the algorithm’s output structure as well as the accompanying analysis.

Our first result in this direction is that the last iterate of OMD converges in all coherent problems, including null-coherent ones. As a special case, this generalizes and extends the results of Daskalakis et al. (2018) for OGD in bilinear problems, and also settles in the affirmative an issue left open by the authors concerning the convergence of the algorithm in nonlinear problems. In addition, under the OMD algorithm, the (Bregman) distance to a solution decreases monotonically, so each iterate is better than the previous one (Theorem 4.1). Finally, under strict coherence, we also show that OMD converges with probability $1$ in stochastic saddle-point problems (Theorem 4.3). These results suggest that a straightforward, extra-gradient add-on can lead to significant performance gains when applied to existing state-of-the-art first-order methods (such as Adam). This theoretical prediction is validated experimentally in a wide array of GAN models (including Gaussian mixture models, and the CelebA and CIFAR-10 datasets) in Section 5.

Problem setup and preliminaries

Consider a saddle-point problem of the general form

To obtain a solution of (SP), we will focus on incremental processes that exploit the individual loss/reward gradients of $f$ (assumed throughout to be at least $C^{1}$-smooth). Since the individual gradients of $f$ will play a key role in our analysis, we will encode them in a single vector as

and, following standard conventions, we will treat $g(x)$ as an element of $\mathcal{Y}\equiv\mathcal{V}^{\ast}$, the dual of the ambient space $\mathcal{V}\equiv\mathcal{V}_{1}\times\mathcal{V}_{2}$, assumed to be endowed with the product norm $\lVert x\rVert^{2}=\lVert x_{1}\rVert^{2}+\lVert x_{2}\rVert^{2}$.

Most of the literature on saddle-point problems has focused on the monotone case, i.e., when $f$ is convex-concave. In such problems, it is well known that solutions of (SP) can be characterized equivalently as solutions of the associated (Minty) variational inequality:

Importantly, this equivalence extends well beyond the realm of monotone problems: it trivially includes all bilinear problems ($f(x_{1},x_{2})=x_{1}^{\top}Mx_{2}$), quasi-convex-concave objectives (where Sion’s minmax theorem applies), etc. For a concrete non-monotone example, consider the problem

The only saddle-point of $f$ is $x^{\ast}=(0,0)$: it is easy to check that $x^{\ast}$ is also the unique solution of the corresponding problem (VI), despite the fact that $f$ is not even (quasi-)monotone.To see this, simply note that $f(x_{1},x_{2})$ is multi-modal in $x_{2}$ for certain values of $x_{1}$. This shows that the equivalence between (SP) and (VI) encompasses a wide range of phenomena that are innately incompatible with convexity/monotonicity, even in the lowest possible dimension; for an in-depth discussion of the links between (SP) and (VI), we refer the reader to Facchinei and Pang (2003).

Motivated by this equivalence, we introduce below the notion of coherence:

We say that (SP) is coherent if every saddle-point of $f$ is a solution of the associated variational inequality problem (VI) and vice versa. If (VI) holds as a strict inequality whenever $x$ is not a saddle-point of $f$, (SP) will be called strictly coherent; by contrast, if (VI) holds as an equality for all $x\in\mathcal{X}$, we will say that (SP) is null-coherent.

The notion of coherence will play a central part in our considerations, so a few remarks are in order. First, to the best of our knowledge, its first antecedent is a gradient condition examined by Bottou (1998) in the context of nonlinear programming; we borrow the term “coherence” from the more recent paper of Zhou et al. (2017) (who actually used the term to describe strict coherence). We should also note that it is possible to relax the equivalence between (SP) and (VI) by positing that only some of the solutions of (SP) can be harvested from (VI). Our analysis still goes through in this case but, to keep things simple, we do not pursue this relaxation here.

Finally, regarding the distinction between coherence and strict coherence, we show in Appendix A that (SP) is strictly coherent when $f$ is strictly convex-concave. At the other end of the spectrum, typical examples of problems that are null-coherent are bilinear objectives with an interior solution: for instance, $f(x_{1},x_{2})=x_{1}x_{2}$ with $x_{1},x_{2}\in$ has $\langle g(x),x\rangle=x_{1}x_{2}-x_{2}x_{1}=0$ for all $x_{1},x_{2}\in$, so it is null-coherent. Finally, neither strict, nor null coherence imply a unique solution to (SP), a property which is particularly relevant for GANs.

Mirror descent

Motivated by its prolific success in convex programming, our starting point will be the well-known mirror descent (MD) method of Nemirovski and Yudin (1983), suitably adapted to our saddle-point context; for a survey, see Hazan (2012) and Bubeck (2015).

for all $x,x^{\prime}\in\mathcal{X}$ and all $t\in$. In terms of smoothness (and in a slight abuse of notation), we also assume that the subdifferential of $h$ admits a continuous selection, i.e., a continuous function $\nabla h\colon\operatorname{dom}\partial h\to\mathcal{Y}$ such that $\nabla h(x)\in\partial h(x)$ for all $x\in\operatorname{dom}\partial h$.Recall here that the subdifferential of $h$ at $x\in\mathcal{X}$ is defined as $\partial h(x)\equiv\{y\in\mathcal{Y}:h(x^{\prime})\geq h(x)+\langle y,x^{\prime}-x\rangle\;\text{for all}\;x\in\mathcal{V}\},$ with the standard convention $h(x)=\infty$ for all $x\in\mathcal{V}\setminus\mathcal{X}$. Then, following Bregman (1967), $h$ generates a pseudo-distance on $\mathcal{X}$ via the relation

This pseudo-distance is known as the Bregman divergence. As we show in Appendix B, we have $D(p,x)\geq\frac{1}{2}K\lVert x-p\rVert^{2}$, so the convergence of a sequence $X_{n}$ to some target point $p$ can be verified by showing that $D(p,X_{n})\to 0$. On the other hand, $D(p,x)$ typically fais to be symmetric and/or satisfy the triangle inequality, so it is not a true distance function per se. Moreover, the level sets of $D(p,x)$ may fail to form a neighborhood basis of $p$, so the convergence of $X_{n}$ to $p$ does not necessarily imply that $D(p,X_{n})\to 0$; we provide an example of this behavior in Appendix B. For technical reasons, it will be convenient to assume that such phenomena do not occur, i.e., that $D(p,X_{n})\to 0$ whenever $X_{n}\to p$. This mild regularity condition is known in the literature as “Bregman reciprocity” (Chen and Teboulle, 1993; Kiwiel, 1997), and it will be our standing assumption in what follows (note also that it holds trivially for both Examples 3.1 and 3.2 below).

Now, as with standard Euclidean distances, the Bregman divergence generates an associated prox-mapping defined as

In analogy with the Euclidean case (discussed below), the prox-mapping (3.3) produces a feasible point $x^{+}=P_{x}(y)$ by starting from $x\in\operatorname{dom}\partial h$ and taking a step along a dual (gradient-like) vector $y\in\mathcal{Y}$. In this way, we obtain the mirror descent (MD) algorithm

where $\gamma_{n}$ is a variable step-size sequence and $\hat{g}_{n}$ is the calculated value of the gradient vector $g(X_{n})$ at the $n$-th stage of the algorithm (for a pseudocode implementation, see Algorithm 1).

For concreteness, two widely used examples of prox-mappings are as follows:

When $\mathcal{X}$ is endowed with the $L^{2}$ norm $\lVert\cdot\rVert_{2}$, the archetypal prox-function is the (square of the) norm itself, i.e., $h(x)=\frac{1}{2}\lVert x\rVert_{2}^{2}$. In that case, $D(p,x)=\frac{1}{2}\lVert x-p\rVert^{2}$ and the induced prox-mapping is

with $\operatorname{\Pi}(x)=\operatorname*{arg\,min}_{x^{\prime}\in\mathcal{X}}\lVert x^{\prime}-x\rVert^{2}$ denoting the ordinary Euclidean projection onto $\mathcal{X}$.

The update rule $x\leftarrow P_{x}(y)$ is known in the literature as the multiplicative weights (MW) algorithm (Arora et al., 2012), and is one of the centerpieces for learning in zero-sum games (Freund and Schapire, 1999; Mertikopoulos et al., 2018; Daskalakis et al., 2018), adversarial bandits (Auer et al., 1995), etc.

Regarding the gradient input sequence $\hat{g}_{n}$ of (MD), we assume that it is obtained by querying a first-order oracle which outputs an estimate of $g(X_{n})$ when called at $X_{n}$. This oracle could be either perfect, returning $\hat{g}_{n}=g(X_{n})$ for all $n$, or imperfect, providing noisy gradient estimations.The reason for this is that, depending on the application at hand, gradients might be difficult to compute directly e.g., because they require huge amounts of data, the calculation of an unknown expectation, etc. By that token, we will make the following blanket assumptions for the gradient feedback sequence $\hat{g}_{n}$:

When (SP) is convex-concave, it is customary to take as the output of (MD) the so-called ergodic average

or some other average of the sequence $X_{n}$ where the objective is sampled. The reason for this is that convexity guarantees – via Jensen’s inequality and gradient monotonicity – that a regret-based analysis of (MD) can lead to explicit rates for the convergence of $\bar{X}_{n}$ to the solution set of (SP) (Nemirovski, 2004; Nesterov, 2007). Beyond convex-concave problems however, this is no longer the case: averaging provides no tangible benefits in a non-monotone setting, so we need to examine the convergence properties of the generating sequence $X_{n}$ of (MD) directly. With all this in mind, our main result for (MD) may be stated is as follows:

Suppose that (MD) is run with a gradient oracle satisfying (3.6) and a variable step-size sequence $\gamma_{n}$ such that $\sum_{n=1}^{\infty}\gamma_{n}=\infty$. Then:

If $f$ is strictly coherent and $\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$, $X_{n}$ converges (a.s.) to a solution of (SP).

This result establishes an important dichotomy between strict and null coherence: in strictly coherent problems, $X_{n}$ is attracted to the solution set of (SP); in null-coherent problems, $X_{n}$ drifts away and cycles without converging. In particular, this dichotomy leads to the following immediate corollaries:

Suppose that $f$ is strictly convex-concave. Then, with assumptions as above, $X_{n}$ converges (a.s.) to the (necessarily unique) solution of (SP).

Suppose that $f$ is bilinear and admits an interior saddle-point $x^{\ast}\in\mathcal{X}^{\circ}$. If $X_{1}\neq x^{\ast}$ and (MD) is run with exact gradient input ($\sigma=0$), we have $\lim_{n\to\infty}D(x^{\ast},X_{n})>0$.

Since bilinear models include all finite two-player, zero-sum games, Corollary 3.3 encapsulates both the non-convergence results of Daskalakis et al. (2018) and Bailey and Piliouras (2018) for gradient descent and FTRL respectively (for a more comprehensive formulation, see Proposition C.3 in Appendix C). This failure of (MD) is due to the fact that, witout a mitigating mechanism in place, a “blind” first-order step could overshoot and lead to an outwards spiral, even with a vanishing step-size. This phenomenon becomes even more pronounced in GANs where it can lead to mode collapse and/or cycles between different modes. The next two sections address precisely these issues.

Optimistic mirror descent

In convex-concave problems, taking an average of the algorithm’s generated samples as in (3.7) may resolve cycling phenomena by inducing an auxiliary sequence that gravitates towards the “center of mass” of the driving sequence $X_{n}$ (which orbits interior solutions). However, this technique cannot be employed in non-monotone problems because Jensen’s inequality does not hold there. In view of this, we replace averaging with an optimistic “extra-gradient” step which uses the obtained information to “amortize” the next prox step (possibly outside the convex hull of generated states). The seed of this “extra-gradient” idea dates back to Korpelevich (1976) and Nemirovski (2004), and has since found wide applications in optimization theory and beyond – for a survey, see Bubeck (2015) and references therein.

In a nutshell, given a state $x$, the extra-gradient method first generates an intermediate, “waiting” state $\hat{x}=P_{x}(-\gamma g(x))$ by taking a prox step as usual. However, instead of continuing from $\hat{x}$, the method samples $g(\hat{x})$ and goes back to the original state $x$ in order to generate a new state $x^{+}=P_{x}(-\gamma g(\hat{x}))$. Based on this heuristic, we obtain the optimistic mirror descent (OMD) algorithm

where, in obvious notation, $\hat{g}_{n}$ and $\hat{g}_{n+1/2}$ represent gradient oracle queries at the incumbent and intermediate states $X_{n}$ and $X_{n+1/2}$ respectively (for a pseudocode implementation, see Algorithm 2).

In his original analysis, Nemirovski (2004) considered the ergodic average (3.7) of the algorithm’s iterates and established an $\operatorname{\mathcal{O}}(1/n)$ convergence rate in monotone problems. However, as we explained above, even though this kind of averaging is helpful in convex-concave problems, it does not provide any tangible benefits beyond this class: in more general problems, $X_{n}$ appears to be the most natural solution candidate. Our first result below justifies this choice in the class of coherent problems:

Suppose that (SP) is coherent and $g$ is $L$-Lipschitz continuous. If (OMD) is run with exact gradient input ($\sigma=0$) and $\gamma_{n}$ such that $0<\inf_{n}\gamma_{n}\leq\sup_{n}\gamma_{n}<K/L,$ the sequence $X_{n}$ converges monotonically to a solution $x^{\ast}$ of (SP), i.e., $D(x^{\ast},X_{n})$ decreases monotonically to .

Suppose that $f$ is bilinear. If (OMD) is run with assumptions as above, the sequence $X_{n}$ converges monotonically to a solution of (SP).

Theorem 4.1 includes as a special case the analysis of Facchinei and Pang (2003, Theorem 12.1.11) for optimistic gradient descent and, in turn, the corresponding asymptotic result of Daskalakis et al. (2018) for bilinear saddle-point problems. As in the case of Daskalakis et al. (2018), Theorem 4.1 shows that optimism (i.e., the extra-gradient add-on) plays a crucial role in stabilizing (MD): not only does (OMD) converge in problems where (MD) provably fails (e.g., in zero-sum finite games), but this convergence is, in fact, monotonic. In other words, at each iteration, (OMD) comes closer to a solution of (SP), whereas (MD) may spiral outwards, towards higher and higher values of the Bregman divergence, ultimately converging to a limit cycle. This phenomenon can be seen very clearly in Fig. 1, and also in the detailed analysis we provide in Appendix C.

Of course, except for very special cases, the monotonic convergence of $X_{n}$ cannot hold when the gradient input to (OMD) is imperfect: a single “bad” sample of $\hat{g}_{n}$ would suffice to throw $X_{n}$ off-track. In this case, we have:

Suppose that (SP) is strictly coherent and (OMD) is run with a gradient oracle satisfying (3.6) and a variable step-size sequence $\gamma_{n}$ such that $\sum_{n=1}^{\infty}\gamma_{n}=\infty$ and $\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$. Then, with probability $1$, $X_{n}$ converges to a solution of (SP).

It is worth noting here that the step-size policy in Theorem 4.3 is different than that of Theorem 4.1. This is due to a) the lack of randomness (which obviates the summability requirement $\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$ in Theorem 4.1); and b) the lack of Lipschitz continuity assumption (which, in the case of Theorem 4.1 guarantees monotonic decrease at each step, provided the step-size is not too big). Importantly, the maximum allowable step-size is also controlled by the strong convexity modulus of $h$, suggesting that the choice of distance-generating function can be fine-tuned further to allow for more aggressive step-size policies – a key benefit of mirror descent methods.

Experimental results

For the experimental validation of our theoretical results, we began by evaluating the extra-gradient add-on in a highly multi-modal mixture of $16$ Gaussians arranged in a $4\times 4$ grid as in Metz et al. (2017). The generator and discriminator have $6$ fully connected layers with $384$ neurons and Relu activations (plus an additional layer for data space projection), and the generator generates $2$-dimensional vectors. The output after {4000, 8000, 12000, 16000, 20000} iterations is shown in Fig. 2. The networks were trained with RMSprop (Tieleman and Hinton, 2012) and Adam (Kingma and Ba, 2014), and the results are compared to the corresponding extra-gradient variant (for an explicit pseudocode representation in the case of Adam, see Daskalakis et al. (2018) and Appendix E). Learning rates and hyperparameters were chosen by an inspection of grid search results so as to enable a fair comparison between each method and its look-ahead version. Overall, the different optimization strategies without look-ahead exhibit mode collapse or oscillations throughout the training period (we ran all models for at least $20000$ iterations in order to evaluate the hopping behavior of the generator). In all cases, the extra-gradient add-on performs consistently better in learning the multi-modal distribution and greatly reduces occurrences of oscillatory behavior.

In our experiments with Gaussian mixture models, the most promising training method was Adam with an extra-gradient step (a concrete pseudocode implementation is provided in Appendix E). Motivated by this, we trained a Wasserstein-GAN on the CelebA and CIFAR-10 datasets using Adam, both with and without an extra-gradient step. The architecture employed was a standard DCGAN; hyperparameters and network architecture details may be found in Appendix E. Subsequently, to quantify the gains of the extra-gradient step, we employed the widely used inception score and Fréchet distance metrics, for which we report the results in Fig. 3. Under both metrics, the extra-gradient add-on provides consistently higher scores after an initial warm-up period (and is considerably more stable). For visualization purposes, we also present in Fig. 4 an ensemble of samples generated at the end of the training period. Overall, the generated samples provide accurate feature representation and low distortion (especially in CelebA).

Conclusions

Our results suggest that the implementation of an optimistic, extra-gradient step is a flexible add-on that can be easily attached to a wide variety of GAN training methods (RMSProp, Adam, SGA, etc.), and provides noticeable gains in performance and stability. From a theoretical standpoint, the dichotomy between strict and null coherence provides a justification of why this is so: optimism eliminates cycles and, in so doing, stabilizes the method. We find this property particularly appealing because it paves the way to a local analysis with provable convergence guarantees in multi-modal settings; we intend to examine this question in future work.

Appendix A Coherent saddle-point problems

We begin our discussion with some basic results on coherence:

If $f$ is convex-concave, (SP) is coherent. In addition, if $f$ is strictly convex-concave, (SP) is strictly coherent.

Let $x^{\ast}$ be a solution point of (SP). Since $f$ is convex-concave, first-order optimality gives

Combining the two, we readily obtain the (Stampacchia) variational inequality

In addition to the above, the fact that $f$ is convex-concave also implies that $g(x)$ is monotone in the sense that

for all $x,x^{\prime}\in\mathcal{X}$ Bauschke and Combettes (2017). Thus, setting $x^{\prime}\leftarrow x^{\ast}$ in (A.3) and invoking (A.2), we get

To establish the converse implication, focus for concreteness on the minimizer, and note that (VI) implies that

Now, if we fix some $x_{1}\in\mathcal{X}_{1}$ and consider the function $\phi(t)=f(x^{\ast}_{1}+t(x_{1}-x^{\ast}_{1}),x^{\ast}_{2})$, the inequality (A.5) yields

for all $t\in$. This implies that $\phi$ is nondecreasing, so $f(x_{1},x^{\ast}_{2})=\phi(1)\geq\phi(0)=f(x^{\ast}_{1},x^{\ast}_{2})$. The maximizing component follows similarly, showing that $x^{\ast}$ is a solution of (SP) and, in turn, establishing that (SP) is coherent.

For the strict part of the claim, the same line of reasoning shows that if $\langle g(x),x-x^{\ast}\rangle=0$ for some $x$ that is not a saddle-point of $f$, the function $\phi(t)$ defined above must be constant on $$, indicating in turn that$f$ cannot be strictly convex-concave, a contradiction. ∎

We proceed to show that the solution set of a coherent saddle-point problem is closed (we will need this regularity result in the convergence analysis of Appendix C):

Let $\mathcal{X}^{\ast}$ denote the solution set of (SP). If (SP) is coherent, $\mathcal{X}^{\ast}$ is closed.

Let $x^{\ast}_{n}$, $n=1,2,\dotsc$, be a sequence of solutions of (SP) converging to some limit point $x^{\ast}\in\mathcal{X}$. To show that $\mathcal{X}^{\ast}$ is closed, it suffices to show that $x^{\ast}\in\mathcal{X}$.

Indeed, given that (SP) is coherent, every solution thereof satisfies (VI), so we have $\langle g(x),x-x^{\ast}_{n}\rangle\geq 0$ for all $x\in\mathcal{X}$. With $x^{\ast}_{n}\to x^{\ast}$ as $n\to\infty$, it follows that

i.e., $x^{\ast}$ satisfies (VI). By coherence, this implies that $x^{\ast}$ is a solution of (SP), as claimed. ∎

Appendix B Properties of the Bregman divergence

In this appendix, we provide some auxiliary results and estimates that are used throughout the convergence analysis of Appendix C. Some of the results we present here (or close variants thereof) are not new (see e.g., Nemirovski et al., 2009; Juditsky et al., 2011). However, the hypotheses used to obtain them vary wildly in the literature, so we provide all the necessary details for completeness.

with $\nabla h(x)$ denoting a continuous selection of $\partial h(x)$. The induced prox-mapping is then given by

By standard results in convex analysis (Rockafellar, 1970, Chap. 26), $h^{\ast}$ is differentiable on $\mathcal{Y}$ and its gradient satisfies the identity

For notational convenience, we will also write

and we will refer to $Q\colon\mathcal{Y}\to\mathcal{X}$ as the mirror map generated by $h$. All these notions are related as follows:

Let $h$ be a distance-generating function on $\mathcal{X}$. Then, for all $x\in\operatorname{dom}\partial h$, $y\in\mathcal{Y}$, we have:

Finally, if $x=Q(y)$ and $p\in\mathcal{X}$, we have

By (B.6b), we have $\partial h(x^{+})\neq\varnothing$, i.e., $x^{+}\in\operatorname{dom}\partial h$. As a result, the update rule $x\leftarrow P_{x}(y)$ is well-posed, i.e., it can be iterated in perpetuity.

For (B.6a), note that $x$ solves (B.3) if and only if $y-\partial h(x)\ni 0$, i.e., if and only if $y\in\partial h(x)$. Similarly, comparing (B) with (B.3), it follows that $x^{+}$ solves (B) if and only if $\nabla h(x)+y\in\partial h(x^{+})$, i.e., if and only if $x^{+}=Q(\nabla h(x)+y)$.

For (B.7), by a simple continuity argument, it suffices to show that the inequality holds for interior $p\in\mathcal{X}^{\circ}$. To establish this, let

Since $h$ is strongly convex and $y\in\partial h(x)$ by (B.6a), it follows that $\phi(t)\geq 0$ with equality if and only if $t=0$. Since $\psi(t)=\langle\nabla h(x+t(p-x))-y,p-x\rangle$ is a continuous selection of subgradients of $\phi$ and both $\phi$ and $\psi$ are continuous on $$, it follows that$\phi$is continuously differentiable with$\phi^{\prime}=\psi$on$$. Hence, with$\phi$convex and$\phi(t)\geq 0=\phi(0)$for all$t\in$, we conclude that$\phi^{\prime}(0)=\langle\nabla h(x)-y,p-x\rangle\geq 0$, which proves our assertion. ∎

We continue with some basic bounds on the Bregman divergence before and after a prox step. The basic ingredient for these bounds is a generalization of the (Euclidean) law of cosines which is known in the literature as the “three-point identity” (Chen and Teboulle, 1993):

Let $h$ be a distance-generating function on $\mathcal{X}$. Then, for all $p\in\mathcal{X}$ and all $x,x^{\prime}\in\operatorname{dom}\partial h$, we have

Our claim then follows by adding the last two lines and subtracting the first. ∎

With this identity at hand, we have the following series of upper and lower bounds:

Let $h$ be a $K$-strongly convex distance-generating function on $\mathcal{X}$, fix some $p\in\mathcal{X}$, and let $x^{+}=P_{x}(y)$ for $x\in\operatorname{dom}\partial h$, $y\in\mathcal{Y}$. We then have:

so (B.11a) follows by gathering all terms involving $h$ and recalling the definition of $D(p,x)$. ∎

By the three-point identity (B.9), we readily obtain

where, in the last step, we used (B.7) and the fact that $x^{+}=P_{x}(y)$, so $\nabla h(x)+y\in\partial h(x^{+})$. The above is just (B.11b), so the first part of our proof is complete.

Therefore, by Young’s inequality (Rockafellar, 1970), we get

with the last step following from Lemma B.1 applied to $x$ in place of $p$. ∎

which admits $p$ as a solution for all $c\geq 0$ (so $p$ belongs to the closure of $L_{c}(p)$ even though $D(p,p)=0$ by definition). As a result, under this distance-generating function, it is possible to have $X_{n}\to p$ even when $\liminf_{n\to\infty}D(p,X_{n})>0$ (simply take a sequence $X_{n}$ that converges to $p$ while remaining on the same level set of $D$). As we discussed in the main body of the paper, such pathologies are discarded by the Bregman reciprocity condition

This condition comes into play at the very last part of the proofs of Theorems 3.1 and 4.1; other than that, we will not need it in the rest of our analysis.

Finally, for the analysis of the OMD algorithm, we will need to relate prox steps taken along different directions:

Let $h$ be a $K$-strongly convex distance-generating function on $\mathcal{X}$ and fix some $p\in\mathcal{X}$, $x\in\operatorname{dom}\partial h$. Then:

For all $y_{1},y_{2}\in\mathcal{Y}$, we have:

In addition, letting $x^{+}_{1}=P_{x}(y_{1})$ and $x^{+}_{2}=P_{x}(y_{2})$, we have:

We begin with the proof of the Lipschitz property of $P_{x}$. Indeed, for all $p\in\mathcal{X}$, (B.7) gives

Therefore, setting $p\leftarrow x^{+}_{2}$ in (B.23a), $p\leftarrow x^{+}_{1}$ in (B.23b) and rearranging, we obtain

By the strong convexity of $h$, we also have

For the second part of our claim, the bound (B.11b) of Proposition B.3 applied to $x^{+}_{2}=P_{x}(y_{2})$ readily gives

thus proving (B.22a). To complete our proof, note that (B.11b) with $p\leftarrow x^{+}_{2}$ gives

where we used Young’s inequality and (B.11a) in the second inequality. The bound (B.22b) then follows by substituting (B) in (B). ∎

Appendix C Convergence analysis of mirror descent

We begin by recalling the definition of the mirror descent algorithm. With notation as in the previous section, the algorithm is defined via the recursive scheme

where $\gamma_{n}$ is a variable step-size sequence and $\hat{g}_{n}$ is the calculated value of the gradient vector $g(X_{n})$ at the $n$-th stage of the algorithm. As we discussed in the main body of the paper, the gradient input sequence $\hat{g}_{n}$ of (MD) is assumed to satisfy the standard oracle assumptions

where $\mathcal{F}_{n}$ represents the history (natural filtration) of the generating sequence $X_{n}$ up to stage $n$ (inclusive).

With this preliminaries at hand, our convergence proof for (MD) under strict coherence will hinge on the following results:

Suppose that (SP) is strictly coherent and (MD) is run with a gradient oracle satisfying (3.6) and a step-size $\gamma_{n}$ such that $\sum_{n=1}^{\infty}\gamma_{n}=\infty$ and $\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$. Then, with probability $1$, there exists a (possibly random) solution $x^{\ast}$ of (SP) such that $\liminf_{n\to\infty}D(x^{\ast},X_{n})=0$.

Proposition C.1 can be seen as a “dichotomy” result: it shows that the Bregman divergence is an asymptotic constant of motion, so (MD) either converges to a saddle-point $x^{\ast}$ (if $D(x^{\ast})=0$) or to some nonzero level set of the Bregman divergence (with respect to $x^{\ast}$). In this way, Proposition C.1 rules out more complicated chaotic or aperiodic behaviors that may arise in general – for instance, as in the analysis of Palaiopanos et al. (2017) for the long-run behavior of the multiplicative weights algorithm in two-player games. However, unless this limit value can be somehow predicted (or estimated) in advance, this result cannot be easily applied. This is the main role of Proposition C.2: it shows that (MD) admits a subsequence converging to a solution of (SP) so, by (B.20), the limit of $D(x^{\ast},X_{n})$ must be zero.

With all this at hand, our first step is to prove Proposition C.1:

Let $D_{n}=D(x^{\ast},X_{n})$ for some solution $x^{\ast}$ of (SP). Then, by Proposition B.3, we have

where, in the last line, we set $\xi_{n+1}=-\langle U_{n+1},X_{n}-x^{\ast}\rangle$ and we invoked the assumption that (SP) is coherent. Thus, conditioning on $\mathcal{F}_{n}$ and taking expectations, we get

where we used the oracle assumptions (3.6) and the fact that $X_{n}$ is $\mathcal{F}_{n}$-measurable (by definition).

Now, letting $R_{n}=D_{n}+(2K)^{-1}G^{2}\sum_{k=n}^{\infty}\gamma_{k}^{2}$, the estimate (C) gives

i.e., $R_{n}$ is an $\mathcal{F}_{n}$-adapted supermartingale. Since $\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$, it follows that

We now turn to the proof of existence of a convergent subsequence of (MD) under strict coherence (Proposition C.2):

We begin with the technical observation that the solution set $\mathcal{X}^{\ast}$ of (SP) is closed – and hence, compact (cf. Lemma A.2 in Appendix A). Clearly, if $\mathcal{X}^{\ast}=\mathcal{X}$, there is nothing to show; hence, without loss of generality, we may assume in what follows that $\mathcal{X}^{\ast}\neq\mathcal{X}$.

Assume now ad absurdum that, with positive probability, the sequence $X_{n}$ generated by (MD) admits no limit points in $\mathcal{X}^{\ast}$. Conditioning on this event, and given that $\mathcal{X}^{\ast}$ is compact, there exists a (nonempty) compact set $\mathcal{C}\subset\mathcal{X}$ such that $\mathcal{C}\cap\mathcal{X}^{\ast}=\varnothing$ and $X_{n}\in\mathcal{C}$ for all sufficiently large $n$. Moreover, given that (SP) is strictly coherent, we have $\langle g(x),x-x^{\ast}\rangle>0$ whenever $x\in\mathcal{C}$ and $x^{\ast}\in\mathcal{X}^{\ast}$. Therefore, by the continuity of $g$ and the compactness of $\mathcal{X}^{\ast}$ and $\mathcal{C}$, there exists some $a>0$ such that

To proceed, fix some $x^{\ast}\in\mathcal{X}^{\ast}$ and let $D_{n}=D(x^{\ast},X_{n})$. Then, telescoping (C) yields the estimate

where, as in the proof of Proposition C.1, we set $\xi_{n+1}=\langle U_{n+1},X_{n}-x^{\ast}\rangle$. Subsequently, letting $\tau_{n}=\sum_{k=1}^{n}\gamma_{k}$ and using (C.5), we obtain

Therefore, by the law of large numbers for martingale difference sequences (Hall and Heyde, 1980, Theorem 2.18), we conclude that $\tau_{n}^{-1}\sum_{k=1}^{n}\gamma_{k}\xi_{k+1}$ converges to with probability $1$.

Finally, for the last term of (C.6), let $S_{n+1}=\sum_{k=1}^{n}\gamma_{k}^{2}\lVert\hat{g}_{k}\rVert_{\ast}^{2}$. Since $\hat{g}_{k}$ is $\mathcal{F}_{n}$-measurable for all $k=1,2,\dotsc,n-1$, we have

i.e., $S_{n}$ is a submartingale with respect to $\mathcal{F}_{n}$. Furthermore, by the law of total expectation, we also have

Applying all of the above, the estimate (C.6) gives $D_{n+1}\leq D_{1}-a\tau_{n}/2$ for sufficiently large $n$, so $D(x^{\ast},X_{n})\to-\infty$, a contradiction. Going back to our original assumption, this shows that, with probability $1$, at least one of the limit points of $X_{n}$ must lie in $\mathcal{X}^{\ast}$, as claimed. ∎

With all this at hand, we are finally in a position to prove our main result for (MD):

Proposition C.2 shows that, with probability $1$, there exists a (possibly random) solution $x^{\ast}$ of (SP) such that $\liminf_{n\to\infty}\lVert X_{n}-x^{\ast}\rVert=0$ and, hence, $\liminf_{n\to\infty}D(x^{\ast},X_{n})=0$ (by Bregman reciprocity). Since $\lim_{n\to\infty}D(x^{\ast},X_{n})$ exists with probability $1$ (by Proposition C.1), it follows that $\lim_{n\to\infty}D(x^{\ast},X_{n})=\liminf_{n\to\infty}D(x^{\ast},X_{n})=0,$ i.e., $X_{n}$ converges to $x^{\ast}$. ∎

We proceed with the negative result hinted at in the main body of the paper, namely the failure of (MD) to converge under null coherence:

The evolution of the Bregman divergence under (MD) satisfies the identity

where, in the last line, we used the null coherence assumption $\langle g(x),x-x^{\ast}\rangle=0$ for all $x\in\mathcal{X}$. Since $D(X_{n},X_{n+1})\geq 0$, taking expecations above shows that $D(x^{\ast},X_{n})$ is nondecreasing, as claimed. ∎

With Theorem 3.1 at hand, the proof of Corollary 3.2 is an immediate consequence of the fact that strictly convex-concave problems satisfy strict coherence (Proposition A.1). As for Corollary 3.3, we provide below a more general result for two-player, zero-sum finite games.

Then, writing $\Gamma\equiv\Gamma(\mathcal{A}_{1},\mathcal{A}_{2},M)$ for the resulting game, we have:

Let $\Gamma$ be a two-player zero-sum game with an interior Nash equilibrium $x^{\ast}$. If $X_{1}\neq x^{\ast}$ and (MD) is run with exact gradient input ($\sigma^{2}=0$), we have $\lim_{n\to\infty}D(x^{\ast},X_{n})>0$. If, in addition, $\sum_{n=1}^{\infty}\gamma_{n}^{2}<\infty$, $\lim_{n\to\infty}D(x^{\ast},X_{n})$ is finite.

Note that non-convergence does not require any summability assumptions on $\gamma_{n}$.

In words, Proposition C.3 states that (MD) does not converge in finite zero-sum games with a unique interior equilibrium and exact gradient input: instead, $X_{n}$ cycles at positive Bregman distance from the game’s Nash equilibrium. Heuristically, the reason for this behavior is that, for small $\gamma\to 0$, the incremental step $V_{\gamma}(x)=P_{x}(-\gamma g(x))-x$ of (MD) is essentially tangent to the level set of $D(x^{\ast},\cdot)$ that passes through $x$.This observation was also the starting point of Mertikopoulos et al. (2018) who showed that FTRL in continuous time exhibits a similar cycling behavior in zero-sum games with an interior equilibrium. For finite $\gamma>0$, things are even worse because $V_{\gamma}(x)$ points noticeably away from $x$, i.e., towards higher level sets of $D$. As a result, the “best-case scenario” for (MD) is to orbit $x^{\ast}$ (when $\gamma\to 0$); in practice, for finite $\gamma$, the algorithm takes small outward steps throughout its runtime, eventually converging to some limit cycle farther away from $x^{\ast}$.

We make this intuition precise below (for a schematic illustration, see also Fig. 1 above):

Write $v_{1}(x)=-Mx_{2}$ and $v_{2}(x)=x_{1}^{\top}M$ for the players’ payoff vectors under the mixed strategy profile $x=(x_{1},x_{2})$. By construction, we have $g(x)=-(v_{1}(x),v_{2}(x))$. Furthermore, since $x^{\ast}$ is an interior equilibrium of $f$, elementary game-theoretic considerations show that $v_{1}(x^{\ast})$ and $v_{2}(x^{\ast})$ are both proportional to the constant vector of ones. We thus get

where, in the last line, we used the fact that $x^{\ast}$ is interior. This shows that $f$ satisfies null coherence, so our claim follows from Theorem 3.1(b).

For our second claim, arguing as above and using (B.11c), we get

with $G=\max_{x_{1}\in\mathcal{X}_{1},x_{2}\in\mathcal{X}_{2}}\lVert(-Mx_{2},x_{1}^{\top}M)\rVert_{\ast}$. Telescoping this last bound yields

so $D(x^{\ast},X_{n})$ is also bounded from above. Therefore, with $D(x^{\ast},X_{n})$ nondecreasing, bounded from above and $D(x^{\ast},X_{1})>0$, it follows that $\lim_{n\to\infty}D(x^{\ast},X_{n})>0$, as claimed. ∎

Appendix D Convergence analysis of optimistic mirror descent

We now turn to the optimistic mirror descent (OMD) algorithm, as defined by the recursion

with $X_{1}$ initialized arbitrarily in $\operatorname{dom}\partial h$, and $\hat{g}_{n}$, $\hat{g}_{n+1/2}$ representing gradient oracle queries at the incumbent and intermediate states $X_{n}$ and $X_{n+1/2}$ respectively.

The heavy lifting for our analysis is provided by Proposition B.4, which leads to the following crucial lemma:

Suppose that (SP) is coherent and $g$ is $L$-Lipschitz continuous. With notation as above and exact gradient input ($\sigma=0$), we have

Substituting $x\leftarrow X_{n}$, $y_{1}\leftarrow-\gamma_{n}g(X_{n})$, and $y_{2}\leftarrow-\gamma_{n}g(X_{n+1/2})$ in Proposition B.4, we obtain the estimate:

where, in the last line, we used the fact that $x^{\ast}$ is a solution of (SP)/(VI), and that $g$ is $L$-Lipschitz. ∎

We are now finally in a position to prove Theorem 4.1 (reproduced below for convenience):

Suppose that (SP) is coherent and $g$ is $L$-Lipschitz continuous. If (OMD) is run with exact gradient input and a step-size sequence $\gamma_{n}$ such that

the sequence $X_{n}$ converges monotonically to a solution $x^{\ast}$ of (SP), i.e., $D(x^{\ast},X_{n})$ is non-increasing and converges to .

Let $x^{\ast}$ be a solution of (SP). Then, by the stated assumptions for $\gamma_{n}$, Lemma D.1 yields

where $\alpha\in(0,1)$ is such that $\gamma_{n}^{2}<\alpha K/L$ for all $n$ (that such an $\alpha$ exists is a consequence of the assumption that $\sup_{n}\gamma_{n}<K/L$). This shows that $D(x^{\ast},X_{n})$ is non-decreasing for every solution $x^{\ast}$ of (SP).

With $\sup_{n}\gamma_{n}<K/L$, the above estimate readily yields $\sum_{n=1}^{\infty}\lVert X_{n+1/2}-X_{n}\rVert^{2}<\infty$, which in turn implies that $\lVert X_{n+1/2}-X_{n}\rVert\to 0$ as $n\to\infty$.

By the compactness of $\mathcal{X}$, we further infer that $X_{n}$ admits an accumulation point $\hat{x}$, i.e., there exists a subsequence $n_{k}$ such that $X_{n_{k}}\to\hat{x}$ as $k\to\infty$. Since $\lVert X_{n_{k}+1/2}-X_{n_{k}}\rVert\to 0$, this also implies that $X_{n_{k}+1/2}$ converges to $\hat{x}$ as $k\to\infty$. Further, by passing to a subsequence if necessary, we may also assume without loss of generality that $\gamma_{n_{k}}$ converges to some limit value $\gamma>0$. Then, by the Lipschitz continuity of the prox-mapping (cf. Proposition B.4), we readily obtain

i.e., $\hat{x}$ is a solution of (VI) – and, hence, (SP). Since $D(\hat{x},X_{n})$ is nonincreasing and $\liminf_{n\to\infty}D(\hat{x},X_{n})=0$ (by the Bregman reciprocity requirement), we conclude that $\liminf_{n\to\infty}D(\hat{x},X_{n})=0$, i.e., $X_{n}$ converges to $\hat{x}$. Since $\hat{x}$ is a solution of (SP), our proof is complete. ∎

Our last result concerns the convergence of (OMD) in strictly coherent problems with a stochastic gradient oracle:

which is obtained from the two-point estimate (B.22b) by substituting $x\leftarrow x^{\ast}$, $x_{1}\leftarrow X_{n}$, $y_{1}\leftarrow\hat{g}_{n}$, $x^{+}_{1}\leftarrow X_{n+1/2}=P_{X_{n}}(-\gamma_{n}\hat{g}_{n})$, $y_{2}\leftarrow\hat{g}_{n+1/2}$, and $x^{+}_{2}\leftarrow X_{n}=P_{X_{n}}(-\gamma_{n}\hat{g}_{n+1/2})$. Then, working as in the proof of Proposition C.1, we obtain the following estimate for the sequence $D_{n}=D(x^{\ast},X_{n})$:

Then, following the same steps as in the proof of Proposition C.1, it follows that $D_{n}$ converges to some limit value $D_{\infty}$.

Each term in the above bound can be controlled in the same way as the corresponding terms in (C.6). Thus, repeating the steps in the proof of Proposition C.2, it follows that there exists a subsequence of $X_{n+1/2}$ (and hence also of $X_{n}$) which converges to $x^{\ast}$.

Our claim then follows by combining the two intermediate results above in the same way as in the proof of Theorem 3.1(a); to avoid needless repetition, we omit the details. ∎

Appendix E Experimental results

For most of our experiments, the method that seemed to generate the best results was Adam and its optimistic version (Daskalakis et al., 2018); for a pseudocode iplementation, see LABEL:alg:extra_Adam below. We also noticed empirically that it was more efficient to use two different sets of moment estimates $(m_{t},v_{t})$ and $(m_{t}^{\prime},v_{t}^{\prime})$ for the first and the second gradient steps. We used this algorithm for our experiments with both GMMs and the CelebA/CIFAR-10 datasets.

E.2. Experiments with standards datasets

In this section we present the results of our image experiments using OMD training techniques. Inception and FID scores obtained by our model during training were reported in Fig. 3: as can be seen there, the extra-gradient add-on improves the performance of GAN training and efficiently stabilizes the model; without the extra-gradient step, performance tends to drop noticeably after approximately $100k$ steps.

For ease of comparison, we provide below a collection of samples generated by Adam and optimistic Adam in the CelebA and CIFAR-10 datasets. Especially in the case of CelebA, the generated samples are consistently more representative and faithful to the target data distribution.

For the reproducibility of our experiments, we provide Table 1 and Table 2 the network architectures and the hyperparameters of the GANs that we used. The architecture employed is a standard DCGAN architecture with a $5$-layer generator with batchnorm, and an $8$-layer discriminator. The generated samples were 32$\times$32$\times$3 RGB images.

References