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

Source: [A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems](<https://www.sota2.com/research/paper/68fa57711e209131ce9a54b6>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T14:43:29.035Z

Authors: Erfan Yazdandoost Hamedani, Necdet Serhat Aybat

Published: 2018-03-04T18:43:13.000Z

## Abstract

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 $\\nabla\_x\\Phi(\\cdot,y)$ is Lipschitz for any fixed $y$, and $\\nabla\_y\\Phi(\\cdot,\\cdot)$ 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(\\bar{x}\_k,y)-\\mathcal L(x,\\bar{y}\_k)$ for the ergodic sequence $\\{\\bar{x}\_k,\\bar{y}\_k\\}$. In particular, we show $\\mathcal O(1/k)$ rate when the problem is merely convex in $x$. Furthermore, assuming $\\Phi(x,\\cdot)$ is linear for each fixed $x$ and $f$ is strongly convex, we obtain the ergodic convergence rate of $\\mathcal O(1/k^2)$ -- 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Personalized PageRank on econ-beaflw](<https://www.sota2.com/research/sota/personalized-pagerank-on-econ-beaflw.md>): Personalized PageRank; econ-beaflw; Execution Time: 72.28.

- [Personalized PageRank on bio-CE-HT](<https://www.sota2.com/research/sota/personalized-pagerank-on-bio-ce-ht.md>): Personalized PageRank; bio-CE-HT; Execution Time: 187.15.

- [Personalized PageRank on bio-CE-LC](<https://www.sota2.com/research/sota/personalized-pagerank-on-bio-ce-lc.md>): Personalized PageRank; bio-CE-LC; Execution Time: 2.58.

- [Personalized PageRank on DD242](<https://www.sota2.com/research/sota/personalized-pagerank-on-dd242.md>): Personalized PageRank; DD242; Execution Time: 43.29.

- [Personalized PageRank on DD68](<https://www.sota2.com/research/sota/personalized-pagerank-on-dd68.md>): Personalized PageRank; DD68; Time: 36.55.

- [Personalized PageRank on peking-1](<https://www.sota2.com/research/sota/personalized-pagerank-on-peking-1.md>): Personalized PageRank; peking-1; Execution Time: 122.37.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1803.01401>)

[PDF](<https://arxiv.org/pdf/1803.01401.pdf>)