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

By Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Ramaseshan Chandrasekhar, Georgios Piliouras. International Conference on Learning Representations, 2018

342 citations recorded by the source corpus.

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

Subfields: Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0ffb2d5bbbc4f2cc547569337bd20cc77c1111d7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, background): “The proof of Theorem 10 proceeds by ﬁrst using the well-known fact (Facchinei and Pang (2003); Mertikopoulos et al. (2018); Mokhtari et al. (2019a)) that for any T ∈ N , there is some t ∗ ∈ { 1 , 2 , . . . , T } so that the t ∗ th iterate z ( t ∗ ) = ( x ( t ∗ ) , y ( t ∗ ) ) obtains the upper…”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “Surprisingly, non-convergent phenomena of this kind are observed even in very simple saddle-point problems such as twodimensional, unconstrained bilinear games [4, 7, 21].”
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence (2020, methodology): “…x ∗ ) ; x ∗ − x i ≤ 0 ∀ x ∈ X More recently, algorithms developed in this framework are also applied to non-convex problems including optimizing generative adversarial networks (GANs) (Daskalakis et al. 2018; Yadav et al. 2018; Chavdarova et al. 2019; Gidel et al. 2019; Mertikopoulos et al. 2019).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “, 2018), and extragradient method (Mertikopoulos et al., 2019) have been advocated to mitigate the oscillatory behaviors around the equilibria; while Adolphs et al.”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, background): “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.”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “in developing principled training algorithms for this purpose [3, 19, 27, 29, 31, 32].”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, neutral): “[36] show almost sure convergence of SimGD-OS under strict convex-concavity (and more generally under “strict coherence”).”
Competitive Gradient Descent (2019, background): “, 2018), and optimism (Rakhlin and Sridharan, 2013; Daskalakis et al., 2017; Mertikopoulos et al., 2019) propose more sophisticated heuristics that the players could use to predict each other’s next move.”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, methodology): “We also notice that two recent works have considered algorithms for solving min-max saddle-point problems (in particular for training GAN) from the perspective of variational inequalities [31, 47].”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, methodology): “When it comes to more general ℓ p norms, [36] establishes the asymptotic convergence of the iterates of an optimistic variant of the mirror descent algorithm, but does not provide any convergence rates.”
The Unusual Effectiveness of Averaging in GAN Training (2018, methodology): “For tackling non-convergence, regularizing objective functions (Mescheder et al., 2017; Salimans et al., 2016), two time-scale techniques (Heusel et al., 2017) and extra-gradient (optimistic) methods (Daskalakis et al., 2018; Mertikopoulos et al., 2019) have been studied.”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “, 2019), extragradient (EG) (Korpelevich, 1976; Mertikopoulos et al., 2019), optimistic mirror descent (OGDA) (Daskalakis et al.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, methodology): “Recent research has focused on alternative gradient-based algorithms that have guarantees beyond the convex-concave setting [Daskalakis et al., 2017, Heusel et al., 2017, Mertikopoulos et al., 2019, Mazumdar et al., 2019].”