Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms
  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.
