A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach

By Aryan Mokhtari, Asuman E. Ozdaglar, Sarath Pattathil. 2019

380 citations recorded by the source corpus.

In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving saddle point problems. This viewpoint enables us to develop a new framework for analyzing EG and OGDA for bilinear and strongly convex-strongly concave settings. Moreover, we use the proximal point approximation interpretation to generalize the results for OGDA for a wide range of parameters.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, neutral): “…of the problem has been studied in a number of classic (Korpelevich, 1976; Nemirovski, 2004) and recent results (Mescheder et al., 2017; Ibrahim et al., 2019; Gidel et al., 2018; Daskalakis et al., 2018; Gidel et al., 2019; Mokhtari et al., 2020; Azizian et al., 2020a;b) in various settings.”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “However, linear convergence results for extragradient 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).”
Revisiting Stochastic Extragradient (2019, methodology): “…Optimistic mirror descent (OMD), first proposed by (Rakhlin and Sridharan, 2013) for convex-concave zero-sum games, has been analyzed in a number of works (Mokhtari et al., 2019; Daskalakis and Panageas, 2019; Gidel et al., 2019a) and it was applied to GAN training in (Daskalakis et al., 2018).”
When can Wasserstein GANs minimize Wasserstein Distance? (2020, background): “2 Related works Generative Adversarial Networks The works [29, 16, 25, 9, 10, 13, 21, 28, 22] considers either local convergence property of the GAN training, or the global convergence property when the objective is convex-concave However, there is no clear evidence of how the local property can be ”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, neutral): “Optimism is a simple modification to remedy the cycling behavior of simGD, which can occur even under the bilinear convex-concave setup [8, 9, 10, 36, 17, 28, 42, 50].”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “The generalized OG recursion is commonly stated as follows [25, 35]: where γ t is sometimes called the optimism rate.”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “This setting has been extensively studied and different algorithms have been developed for finding a Nash equilibrium [46, 21, 44, 29, 40, 23, 26, 43, 18, 45].”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, methodology): “We can apply extragradient algorithm for solving such problem and obtain a point ( x ′ , y ′ ) satisfying that where The required number of gradient evaluations is O ( ϵ − 2 ) [Mokhtari et al., 2019a].”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “The vast majority of this line of research focus on convex-concave setting (Kinderlehrer and Stampacchia, 1980; Nemirovski and Yudin, 1978; Nemirovski, 2004; Mokhtari et al., 2019b;a).”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, methodology): “…papers (Korpelevich, 1976; Tseng, 1995) and many recent ones (Nemirovski, 2004; Chen et al., 2014; Palaniappan and Bach, 2016; Mescheder et al., 2017; Gidel et al., 2019a,b; Daskalakis et al., 2018; Mokhtari et al., 2019; Azizian et al., 2019) suggest new methods and provide better upper bounds.”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “Lower bounds in optimization date back to Nemirovsky and Yudin (1983) and were popularized by Nesterov (2004).”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31,41,45,48] and/or obtaining last-iterate convergence guarantees [1,2,13–15,20,22,28,35,37,38,43].”