# Inexact First-Order Primal-Dual Algorithms

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

## Key facts

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

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

- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization](https://mlsanity.com/paper/2112.11928/) (2021)
- [An Adaptively Inexact Method for Bilevel Learning Using Primal-Dual Style Differentiation](https://mlsanity.com/paper/2412.06436/) (2024)
- [Analysis of Total Variation Minimization for Clustered Federated Learning](https://mlsanity.com/paper/2403.06298/) (2024)
- [Structured Reinforcement Learning for Media Streaming at the Wireless Edge](https://mlsanity.com/paper/2404.07315/) (2024)
- [Why do we regularise in every iteration for imaging inverse problems?](https://mlsanity.com/paper/2411.00688/) (2024)

## Abstract (arXiv)

In this paper we investigate the convergence of a recently popular class of first-order primal-dual algorithms for saddle point problems under the presence of errors occurring in the proximal maps and gradients. We study several types of errors and show that, provided a sufficient decay of these errors, the same convergence rates as for the error-free algorithm can be established. More precisely, we prove the (optimal) O(1/N) convergence to a saddle point in finite dimensions for the class of non-smooth problems considered in this paper, and prove a O(1/N2) or even linear O(θN) convergence rate if either the primal or dual objective respectively both are strongly convex. Moreover we show that also under a slower decay of errors we can establish rates, however slower and directly depending on the decay of the errors. We demonstrate the performance and practical use of the algorithms on the example of nested algorithms and show how they can be used to split the global objective more efficiently.