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

Abstract

This paper introduces a coordinate descent version of the Vũ-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.

32 pages

References in corpus (6)

• Pathwise coordinate optimization
• Convex Optimization for Big Data
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• A Three-Operator Splitting Scheme and its Optimization Applications
• Randomized Primal-Dual Proximal Block Coordinate Updates
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

Cited by in corpus (15)

• Coordinate Friendly Structures, Algorithms and Applications
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Block-proximal methods with spatially adapted acceleration
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Deep Quantile Regression: Mitigating the Curse of Dimensionality Through Composition
• Primal-dual block-proximal splitting for a class of non-convex problems
• Dual Extrapolation for Sparse Generalized Linear Models
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Iterative regularization for convex regularizers
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• Coordinate Linear Variance Reduction for Generalized Linear Programming
• Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization
• A generic coordinate descent solver for nonsmooth convex optimization
• Coordinate-Update Algorithms can Efficiently Detect Infeasible Optimization Problems
• Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications