Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms

Abstract

We consider minimizing the sum of three convex functions, where the first one F is smooth, the second one is nonsmooth and proximable and the third one is the composition of a nonsmooth proximable function with a linear operator L. This template problem has many applications, for instance, in image processing and machine learning. First, we propose a new primal-dual algorithm, which we call PDDY, for this problem. It is constructed by applying Davis-Yin splitting to a monotone inclusion in a primal-dual product space, where the operators are monotone under a specific metric depending on L. We show that three existing algorithms (the two forms of the Condat-Vu algorithm and the PD3O algorithm) have the same structure, so that PDDY is the fourth missing link in this self-consistent class of primal-dual algorithms. This representation eases the convergence analysis: it allows us to derive sublinear convergence rates in general, and linear convergence results in presence of strong convexity. Moreover, within our broad and flexible analysis framework, we propose new stochastic generalizations of the algorithms, in which a variance-reduced random estimate of the gradient of F is used, instead of the true gradient. Furthermore, we obtain, as a special case of PDDY, a linearly converging algorithm for the minimization of a strongly convex function F under a linear constraint; we discuss its important application to decentralized optimization.

References in corpus (11)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Proximal Splitting Methods in Signal Processing
• On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty
• Fixed Point Strategies in Data Science
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• Collaborative Total Variation: A General Framework for Vectorial TV Models
• Convergence Rates for Projective Splitting
• Stochastic Three-Composite Convex Minimization
• Distributed Proximal Splitting Algorithms with Rates and Acceleration

Cited by in corpus (2)

• Bregman three-operator splitting methods
• Convergence Analyses of Davis-Yin Splitting via Scaled Relative Graphs II: Convex Optimization Problems