# Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 74 references that are in the map.
- First posted on arXiv 24 Sep 2021.

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

- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [A Three-Operator Splitting Scheme and its Optimization Applications](https://mlsanity.com/paper/1504.01032/) (2015)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Proximal Algorithms in Statistics and Machine Learning](https://mlsanity.com/paper/1502.03175/) (2015)
- [Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2010.01935/) (2020)
- [Unnormalized Optimal Transport](https://mlsanity.com/paper/1902.03367/) (2019)
- [A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions](https://mlsanity.com/paper/1508.04625/) (2015)
- [An inertial forward-backward algorithm for monotone inclusions](https://mlsanity.com/paper/1403.3522/) (2014)
- [A forward-backward view of some primal-dual optimization methods in image recovery](https://mlsanity.com/paper/1406.5439/) (2014)
- [An Equivalence between the Lasso and Support Vector Machines](https://mlsanity.com/paper/1303.1152/) (2013)
- [Convex Optimization for Big Data](https://mlsanity.com/paper/1411.0972/) (2014)
- [Primal-Dual Algorithms for Non-negative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/1412.1788/) (2014)
- [Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances](https://mlsanity.com/paper/1810.00118/) (2018)
- [A Generalization of the Chambolle-Pock Algorithm to Banach Spaces with Applications to Inverse Problems](https://mlsanity.com/paper/1412.0126/) (2014)
- [Nonlinear Spectral Analysis via One-homogeneous Functionals - Overview and Future Prospects](https://mlsanity.com/paper/1510.01077/) (2015)
- [A Primal-Dual Method for Optimal Control and Trajectory Generation in High-Dimensional Systems](https://mlsanity.com/paper/1712.08226/) (2017)
- [On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems](https://mlsanity.com/paper/1303.2875/) (2013)
- [A Class of Randomized Primal-Dual Algorithms for Distributed Optimization](https://mlsanity.com/paper/1406.6404/) (2014)
- [Block-proximal methods with spatially adapted acceleration](https://mlsanity.com/paper/1609.07373/) (2016)
- [A randomized intertial primal-dual fixed point algorithm for monotone inclusions](https://mlsanity.com/paper/1611.05142/) (2016)

## Abstract (arXiv)

The linear primal-dual hybrid gradient (PDHG) method is a first-order method that splits convex optimization problems with saddle-point structure into smaller subproblems. Unlike those obtained in most splitting methods, these subproblems can generally be solved efficiently because they involve simple operations such as matrix-vector multiplications or proximal mappings that are fast to evaluate numerically. This advantage comes at the price that the linear PDHG method requires precise stepsize parameters for the problem at hand to achieve an optimal convergence rate. Unfortunately, these stepsize parameters are often prohibitively expensive to compute for large-scale optimization problems, such as those in machine learning. This issue makes the otherwise simple linear PDHG method unsuitable for such problems, and it is also shared by most first-order optimization methods as well. To address this issue, we introduce accelerated nonlinear PDHG methods that achieve an optimal convergence rate with stepsize parameters that are simple and efficient to compute. We prove rigorous convergence results, including results for strongly convex or smooth problems posed on infinite-dimensional reflexive Banach spaces. We illustrate the efficiency of our methods on ℓ1-constrained logistic regression and entropy-regularized matrix games. Our numerical experiments show that the nonlinear PDHG methods are considerably faster than competing methods.