mlsanityData to 14 Oct 2026

Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling

arXiv 2112.15199 ↗First posted 30 Dec 2021math.OC cs.LGcited by 16

Not on the map. Why?

Abstract (arXiv)

In this paper we study the convex-concave saddle-point problem minx maxy f(x) + yT A x - g(y), where f(x) and g(y) are smooth and convex functions. We propose an Accelerated Primal-Dual Gradient Method (APDG) for solving this problem, achieving (i) an optimal linear convergence rate in the strongly-convex-strongly-concave regime, matching the lower complexity bound (Zhang et al., 2021), and (ii) an accelerated linear convergence rate in the case when only one of the functions f(x) and g(y) is strongly convex or even none of them are. Finally, we obtain a linearly convergent algorithm for the general smooth and convex-concave saddle point problem minx maxy F(x,y) without the requirement of strong convexity or strong concavity.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 24 of its 48 references that are in the map. First posted on arXiv 30 Dec 2021.

Builds on

24 of 48 references.

References · 24

  1. 2017Training GANs with Optimismcited by 217
  2. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 150
  3. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  4. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  5. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  6. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  7. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  8. 2018Negative Momentum for Improved Game Dynamicscited by 60
  9. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  10. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  11. 2019Revisiting Stochastic Extragradientcited by 35
  12. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
12 more
  1. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 31
  2. 2018Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexitycited by 29
  3. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  4. 2020Multi-consensus Decentralized Accelerated Gradient Descentcited by 20
  5. 2020Accelerating Smooth Games by Manipulating Spectral Shapescited by 18
  6. 2020Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Accelerationcited by 18
  7. 2016Sketching for Large-Scale Learning of Mixture Modelscited by 14
  8. 2017Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithmscited by 8
  9. 2021An Optimal Algorithm for Strongly Convex Minimization under Affine Constraintscited by 8
  10. 2017DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimizationcited by 7
  11. 2020IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Methodcited by 6
  12. 2021DIPPA: An improved Method for Bilinear Saddle Point Problemscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 10; 2023: 1; 2024: 2; 2025: 1; 2026: 2.

16 papers.

Sort:

By area:

  1. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  2. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  3. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  4. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  5. 2022DADAO: Decoupled Accelerated Decentralized Asynchronous Optimizationcited by 8
  6. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  7. 2024Accelerated Preference Optimization for Large Language Model Alignmentcited by 5
  8. 2025Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimizationcited by 5
  9. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  10. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  11. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  12. 2022Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problemscited by 3
4 more
  1. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  2. 2026Learning to Optimize by Differentiable Programmingcited by 1
  3. 2024Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approachcited by 0
  4. 2026Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimizationcited by 0