# Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures

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

## Key facts

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

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

- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization](https://mlsanity.com/paper/2209.01850/) (2022)
- [Clustered Federated Learning based on Nonconvex Pairwise Fusion](https://mlsanity.com/paper/2211.04218/) (2022)
- [Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers](https://mlsanity.com/paper/2410.01979/) (2024)
- [BALPA: A Balanced Primal-Dual Algorithm for Nonsmooth Optimization with Application to Distributed Optimization](https://mlsanity.com/paper/2212.02835/) (2022)
- [Rectify and Align GPS Points to Parking Spots via Rank-1 Constraint](https://mlsanity.com/paper/2510.13439/) (2025)

## Abstract (arXiv)

Primal-Dual Hybrid Gradient (PDHG) and Alternating Direction Method of Multipliers (ADMM) are two widely-used first-order optimization methods. They reduce a difficult problem to simple subproblems, so they are easy to implement and have many applications. As first-order methods, however, they are sensitive to problem conditions and can struggle to reach the desired accuracy. To improve their performance, researchers have proposed techniques such as diagonal preconditioning and inexact subproblems. This paper realizes additional speedup about one order of magnitude. Specifically, we choose non-diagonal preconditioners that are much more effective than diagonal ones. Because of this, we lose closed-form solutions to some subproblems, but we found simple procedures to replace them such as a few proximal-gradient iterations or a few epochs of proximal block-coordinate descent, which are in closed forms. We show global convergence while fixing the number of those steps in every outer iteration. Therefore, our method is reliable and straightforward. Our method opens the choices of preconditioners and maintains both low per-iteration cost and global convergence. Consequently, on several typical applications of primal-dual first-order methods, we obtain 4-95× speedup over the existing state-of-the-art.