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

Abstract

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.

arXiv comment25 pages, 3 figures

Cited by in corpus (48)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Near-Optimal Algorithms for Minimax Optimization
• Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness
• Last-iterate convergence rates for min-max optimization
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Encoding Invariances in Deep Generative Models
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Revisiting Stochastic Extragradient
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• Accelerated methods for composite non-bilinear saddle point problem
• Efficient Algorithms for Federated Saddle Point Optimization
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• $(f,\Gamma )$-Divergences: Interpolating between $f$-Divergences and Integral Probability Metrics
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Local and Global Uniform Convexity Conditions
• On Characterizing GAN Convergence Through Proximal Duality Gap
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
• On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Training Generative Adversarial Networks with Adaptive Composite Gradient
• On the exact convergence to Nash equilibrium in hypomonotone regimes under full and partial-information
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• Gradient Methods for Solving Stackelberg Games
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
• Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
• Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems
• Minimax Optimization: The Case of Convex-Submodular
• A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games