# A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2018.

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

- [A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems](https://mlsanity.com/paper/2106.06075/) (2021)
- [Convex-Concave Min-Max Stackelberg Games](https://mlsanity.com/paper/2110.05192/) (2021)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Robust No-Regret Learning in Min-Max Stackelberg Games](https://mlsanity.com/paper/2203.14126/) (2022)
- [Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems](https://mlsanity.com/paper/2212.07844/) (2022)
- [A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization](https://mlsanity.com/paper/2112.11928/) (2021)
- [STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games](https://mlsanity.com/paper/2210.09769/) (2022)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees](https://mlsanity.com/paper/2408.12505/) (2024)

## Abstract (arXiv)

In this paper, we propose a primal-dual algorithm with a novel momentum term using the partial gradients of the coupling function that can be viewed as a generalization of the method proposed by Chambolle and Pock in 2016 to solve saddle point problems defined by a convex-concave function mathcal L(x,y)=f(x)+Phi(x,y)-h(y) with a general coupling term Phi(x,y) that is not assumed to be bilinear. Assuming nablaxPhi(·,y) is Lipschitz for any fixed y, and nablayPhi(·,·) is Lipschitz, we show that the iterate sequence converges to a saddle point; and for any (x,y), we derive error bounds in terms of mathcal L(barxk,y)-mathcal L(x,baryk) for the ergodic sequence barxk,baryk. In particular, we show mathcal O(1/k) rate when the problem is merely convex in x. Furthermore, assuming Phi(x,·) is linear for each fixed x and f is strongly convex, we obtain the ergodic convergence rate of mathcal O(1/k2) -- we are not aware of another single-loop method in the related literature achieving the same rate when Phi is not bilinear. Finally, we propose a backtracking technique which does not require the knowledge of Lipschitz constants while ensuring the same convergence results. We also consider convex optimization problems with nonlinear functional constraints and we show that using the backtracking scheme, the optimal convergence rate can be achieved even when the dual domain is unbounded. We tested our method against other state-of-the-art first-order algorithms and interior-point methods for solving quadratically constrained quadratic problems with synthetic data, the kernel matrix learning, and regression with fairness constraints arising in machine learning.