# A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2015.

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

- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Estimation of Non-Crossing Quantile Regression Process with Deep ReQU Neural Networks](https://mlsanity.com/paper/2207.10442/) (2022)
- [A primal-dual algorithm for image reconstruction with input-convex neural network regularizers](https://mlsanity.com/paper/2410.12441/) (2024)
- [Semi-Implicit Hybrid Gradient Methods with Application to Adversarial Robustness](https://mlsanity.com/paper/2202.10523/) (2022)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning](https://mlsanity.com/paper/2109.12222/) (2021)

## Abstract (arXiv)

This paper introduces a coordinate descent version of the V~u-Condat algorithm. By coordinate descent, we mean that only a subset of the coordinates of the primal and dual iterates is updated at each iteration, the other coordinates being maintained to their past value. Our method allows us to solve optimization problems with a combination of differentiable functions, constraints as well as non-separable and non-differentiable regularizers. We show that the sequences generated by our algorithm converge to a saddle point of the problem at stake, for a wider range of parameter values than previous methods. In particular, the condition on the step-sizes depends on the coordinate-wise Lipschitz constant of the differentiable function's gradient, which is a major feature allowing classical coordinate descent to perform so well when it is applicable. We then prove a sublinear rate of convergence in general and a linear rate of convergence if the objective enjoys strong convexity properties. We illustrate the performances of the algorithm on a total-variation regularized least squares regression problem and on large scale support vector machine problems.