# Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 45 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 15 of 15)

- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [An Accelerated Linearized Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1401.6607/) (2014)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Accelerated gradient sliding for structured convex optimization](https://mlsanity.com/paper/1609.04905/) (2016)
- [A first-order primal-dual method with adaptivity to local smoothness](https://mlsanity.com/paper/2110.15148/) (2021)
- [Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures](https://mlsanity.com/paper/1811.08937/) (2018)
- [Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization](https://mlsanity.com/paper/2101.00143/) (2021)
- [On a Unified and Simplified Proof for the Ergodic Convergence Rates of PPM, PDHG and ADMM](https://mlsanity.com/paper/2305.02165/) (2023)
- [Golden ratio primal-dual algorithm with linesearch](https://mlsanity.com/paper/2105.07108/) (2021)

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

- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)

## Abstract (arXiv)

Line search procedures are often employed in primal-dual methods for bilinear saddle point problems, especially when the norm of the linear operator is large or difficult to compute. In this paper, we demonstrate that line search is unnecessary by introducing a novel primal-dual method, the auto-conditioned primal-dual hybrid gradient (AC-PDHG) method, which achieves optimal complexity for solving bilinear saddle point problems. AC-PDHG is fully adaptive to the linear operator, using only past iterates to estimate its norm. We further tailor AC-PDHG to solve linearly constrained problems, providing convergence guarantees for both the optimality gap and constraint violation. Moreover, we explore an important class of linearly constrained problems where both the objective and constraints decompose into two parts. By incorporating the design principles of AC-PDHG into the preconditioned alternating direction method of multipliers (ADMM), we propose the auto-conditioned alternating direction method of multipliers (AC-ADMM), which guarantees convergence based solely on one part of the constraint matrix and fully adapts to it, eliminating the need for line search. Finally, we extend both AC-PDHG and AC-ADMM to solve bilinear problems with an additional smooth term. By integrating these methods with a novel acceleration scheme, we attain optimal iteration complexities under the single-oracle setting.