# Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 30 references that are in the map.
- First posted on arXiv 10 Sep 2022.

## Builds on (most cited first, 11 of 11)

- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [Level Constrained First Order Methods for Function Constrained Optimization](https://mlsanity.com/paper/2205.08011/) (2022)
- [Randomized First-Order Methods for Saddle Point Optimization](https://mlsanity.com/paper/1409.8625/) (2014)
- [Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems](https://mlsanity.com/paper/1506.04093/) (2015)

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

- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Dr. FERMI: A Stochastic Distributionally Robust Fair Empirical Risk Minimization Framework](https://mlsanity.com/paper/2309.11682/) (2023)
- [SOREL: A Stochastic Algorithm for Spectral Risks Minimization](https://mlsanity.com/paper/2407.14618/) (2024)

## Abstract (arXiv)

We investigate a primal-dual (PD) method for the saddle point problem (SPP) that uses a linear approximation of the primal function instead of the standard proximal step, resulting in a linearized PD (LPD) method. For convex-strongly concave SPP, we observe that the LPD method has a suboptimal dependence on the Lipschitz constant of the primal function. To fix this issue, we combine features of Accelerated Gradient Descent with the LPD method resulting in a single-loop Accelerated Linearized Primal-Dual (ALPD) method. ALPD method achieves the optimal gradient complexity when the SPP has a semi-linear coupling function. We also present an inexact ALPD method for SPPs with a general nonlinear coupling function that maintains the optimal gradient evaluations of the primal parts and significantly improves the gradient evaluations of the coupling term compared to the ALPD method. We verify our findings with numerical experiments.