mlsanityData to 7 Oct 2026

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

arXiv 1901.08511 ↗First posted 24 Jan 2019math.OC cs.LG stat.MLcited by 142

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 142 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 33; 2022: 42; 2023: 20; 2024: 16; 2025: 14; 2026: 17.

142 papers.

Sort:

By area:

  1. 2023Nash Learning from Human Feedbackcited by 220
  2. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  3. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  4. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  5. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  6. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  7. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  8. 2024Smooth Tchebycheff Scalarization for Multi-Objective Optimizationcited by 50
  9. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  10. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  11. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  12. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
38 more
  1. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  2. 2023Multi-agent Reinforcement Learning: A Comprehensive Surveycited by 30
  3. 2022Fast Adversarial Training with Adaptive Step Sizecited by 24
  4. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  5. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  6. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  7. 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
  8. 2022Proximal Learning With Opponent-Learning Awarenesscited by 20
  9. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  10. 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
  11. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  12. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  13. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  14. 2021Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometrycited by 17
  15. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  16. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  17. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  18. 2022Generalized Optimistic Methods for Convex-Concave Saddle Point Problemscited by 15
  19. 2022Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classificationcited by 15
  20. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  21. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 14
  22. 2022An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Gamescited by 14
  23. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  24. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  25. 2022Alternating Mirror Descent for Constrained Min-Max Gamescited by 13
  26. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  27. 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
  28. 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
  29. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 12
  30. 2024On PI Controllers for Updating Lagrange Multipliers in Constrained Optimizationcited by 12
  31. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  32. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  33. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
  34. 2024Constrained Sampling with Primal-Dual Langevin Monte Carlocited by 10
  35. 2021A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problemscited by 9
  36. 2022Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithmcited by 9
  37. 2022A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learningcited by 9
  38. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9

50 most cited of 142 All 142 (JSON)