# A first-order primal-dual algorithm with linesearch

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2016.

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

- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [A first-order primal-dual method with adaptivity to local smoothness](https://mlsanity.com/paper/2110.15148/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Certifying the Right to Be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning](https://mlsanity.com/paper/2512.23171/) (2025)
- [Adaptive Decentralized Composite Optimization via Three-Operator Splitting](https://mlsanity.com/paper/2602.17545/) (2026)
- [Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/2608.09022/) (2026)

## Abstract (arXiv)

The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires to update only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under standard assumptions. We also show an ergodic O(1/N) rate of convergence for our method. In case one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.