Owing to their connection with generative adversarial networks (GANs), saddle-point problems have recently attracted considerable interest in machine learning and beyond. By necessity, most theoretical guarantees revolve around convex-concave (or even linear) problems; however, making theoretical inroads towards efficient GAN training depends crucially on moving beyond this classic framework. To make piecemeal progress along these lines, we analyze the behavior of mirror descent (MD) in a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality – a property which we call coherence. We first show that ordinary, “vanilla” MD converges under a strict version of this condition, but not otherwise; in particular, it may fail to converge even in bilinear models with a unique solution. We then show that this deficiency is mitigated by optimism: by taking an “extra-gradient” step, optimistic mirror descent (OMD) converges in all coherent problems. Our analysis generalizes and extends the results of Daskalakis et al. [2018] for optimistic gradient descent (OGD) in bilinear problems, and makes concrete headway for provable convergence beyond convex-concave games. We also provide stochastic analogues of these results, and we validate our analysis by numerical experiments in a wide array of GAN models (including Gaussian mixture models, and the CelebA and CIFAR-10 datasets). The surge of recent breakthroughs in deep learning 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 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. For instance, using tools from the theory of dynamical systems, BID28 BID29 and Panageas & 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 non-convex landscapes by searching for properties which could be leveraged for efficient training. As an example, the "strict saddle" property was shown to hold in a wide range of salient objective functions ranging from low-rank matrix factorization BID8 BID20 and dictionary learning [Sun et al., 2017a,b] , to principal component analysis BID19 , and many other models.On the other hand, adversarial deep learning is nowhere near as well understood, especially in the case of generative adversarial networks (GANs) BID22 . Despite an immense amount of recent scrutiny, our theoretical understanding cannot boast similar breakthroughs as in "single-agent" deep learning. 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 , critic gradient penalties BID23 , feature matching, minibatch discrimination, etc. [Radford et al., 2016; Salimans et al., 2016] .Even before the advent of GANs, work on adaptive dynamics in general bilinear zero-sum games (e.g. Rock-Paper-Scissors) established that they lead to persistent, chaotic, recurrent (i.e. cycle-like) behavior [Sato et al., 2002; Piliouras & Shamma, 2014; Piliouras et al., 2014] . Recently , simple specific instances of cycle-like behavior in bilinear games have been revisited mainly through the lens of GANs BID15 Mescheder et al., 2018; Papadimitriou & Piliouras, 2018] . Two important recent results have established unified pictures about the behavior of continuous and discrete-time first order methods in bilinear games: First, established that continuous-time descent methods in zero-sum games (e.g., gradient descent, follow-the-regularized-leader and the like) are Poincaré recurrent, returning arbitrarily closely to their initial conditions infinitely many times. Second, BID4 examined the discrete-time analogues (gradient descent, multiplicative weights and follow-the-regularized-leader) showing that orbits spiral slowly outwards. These recurrent systems have formal connections to Hamiltonian dynamics and do not behave in a gradient-like fashion BID6 ; BID5 . This is a critical failure of descent methods, but one which BID15 showed can be overcome through "optimism", interpreted in this context as an "extra-gradient" step that pushes the training process further along the incumbent gradient -as a result, optimistic gradient descent (OGD) succeeds in cases where vanilla gradient descent (GD) fails (specifically, unconstrained bilinear saddle-point problems).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 are related to those of a naturally associated variational inequality, a property which we call coherence. Then, hoping to overcome the shortcomings of ordinary descent methods 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 satisfied by all strictly convex-concave 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. The null coherence property covers all bilinear models, so this result encompasses fully the analysis of BID4 for GD and follow-the-regularized-leader (FTRL) in general bilinear zero-sum games within our coherence framework. Thus, in and by themselves, gradient/mirror descent methods do not suffice for training convoluted, adversarial deep learning models.To mitigate this deficiency, we consider the addition of an extra-gradient step which looks ahead and takes an additional step along a "future" gradient. This technique was first introduced by BID27 and subsequently gained great popularity as the basis of the mirror-prox algorithm of Nemirovski [2004] which achieves an optimal O(1/n) convergence rate in Lipschitz monotone variational inequalities (see also Nesterov, 2007 , for a primal-dual variant of the method and BID25 , for an extension to stochastic variational inequalities and saddle-point problems).In the learning literature, the extra-gradient technique (or, sometimes, a variant thereof) is often referred to as optimistic mirror descent (OMD) [Rakhlin & Sridharan, 2013] and its effectiveness in GAN training was recently examined by BID15 and Yadav et al. [2018] (the latter involving a damping mechanism for only one of the players). More recently, BID21 considered a variant method which incorporates a mechanism that "extrapolates from the past" in order to circumvent the need for a second oracle call in the extra-gradient step. Specifically, BID21 showed that the extra-gradient algorithm with gradient reuse converges a) geometrically in strongly monotone, deterministic variational inequalities; and b) ergodically in general stochastic variational inequalities , achieving in that case an oracle complexity bound that is √ 13/7/2 ≈ 68% of a bound previously established by BID25 for the mirror-prox algorithm.However, beyond convex-concave problems, averaging offers no tangible benefits because there is no way to relate the value of the ergodic average to the value of the iterates. As a result, moving closer to GAN training requires changing both the algorithm's output as well as the accompanying analysis. With this as our guiding principle, we first show 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 Noor et al. [2011] for OGD in pseudo-monotone problems, and also settles in the affirmative an open question of BID15 concerning the convergence of the last iterate of OGD in nonlinear problems. Going beyond deterministic problems, we also show that OMD converges with probability 1 even in stochastic saddle-point problems that are strictly coherent. These results complement the existing literature on the topic by showing that a cheap extra-gradient add-on can lead to significant performance gains when applied to state-of-the-art methods (such as Adam). We validate this prediction for a wide array of standard GAN models in Section 5. 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, and beyond zero-sum games; we intend to examine this question in future work.
We show how the inclusion of an extra-gradient step in first-order GAN training methods can improve stability and lead to improved convergence results.
{"src": "scitldr-AIC_train", "paper_id": "Bkg8jjC9KQ"}