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

arXiv: https://arxiv.org/abs/2112.15199 · HTML: https://mlsanity.com/paper/2112.15199/

## 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 (most cited first, 24 of 24)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [Accelerating Smooth Games by Manipulating Spectral Shapes](https://mlsanity.com/paper/2001.00602/) (2020)
- [Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration](https://mlsanity.com/paper/2011.06572/) (2020)
- [Sketching for Large-Scale Learning of Mixture Models](https://mlsanity.com/paper/1606.02838/) (2016)
- [Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms](https://mlsanity.com/paper/1703.02624/) (2017)
- [An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints](https://mlsanity.com/paper/2102.11079/) (2021)
- [DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization](https://mlsanity.com/paper/1710.05080/) (2017)
- [IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method](https://mlsanity.com/paper/2006.06733/) (2020)
- [DIPPA: An improved Method for Bilinear Saddle Point Problems](https://mlsanity.com/paper/2103.08270/) (2021)

## Built on by (most cited first, 16 of 16)

- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Accelerated Preference Optimization for Large Language Model Alignment](https://mlsanity.com/paper/2410.06293/) (2024)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)
- [Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization](https://mlsanity.com/paper/2206.08573/) (2022)
- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems](https://mlsanity.com/paper/2209.04604/) (2022)
- [Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization](https://mlsanity.com/paper/2210.17550/) (2022)
- [Learning to Optimize by Differentiable Programming](https://mlsanity.com/paper/2601.16510/) (2026)
- [Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach](https://mlsanity.com/paper/2410.14592/) (2024)
- [Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization](https://mlsanity.com/paper/2609.20327/) (2026)

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