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.
翻译:我们考虑将三个 convex 函数的总和最小化, 其中第一个函数是平滑的, 第二个函数是非移动和相近的, 第三个函数是线性运算符L的不移动相近函数的构成。 这个模板问题有许多应用程序, 例如图像处理和机器学习。 首先, 我们提出一个新的原始双向算法, 我们称之为 PDDDY, 用于这一问题。 这个表示法通过应用 Davis- Yin 分裂成一个单一的包含在原始- 双向产品空间的单向组合, 操作员是单向的, 根据一个取决于L的具体指标, 操作员是单向的。 我们显示, 三种现有的算法( 康达特- Vu 算法和 PD3O 算法的两种形式) 有着相同的结构, 所以 PDDDY 是这个自我一致的层次算法级算法级的第四个缺失的链接。 这个表达法, 方便了趋同分析: 它让我们得出一般的线性趋同率率率率, 和直径直径直径直径直径直的算法级的计算, 。