Convergence on a symmetric accelerated stochastic ADMM with larger stepsizes
Convergence on a symmetric accelerated stochastic ADMM with larger stepsizes
复制标题
DOI：
10.4208/csiam-am.so-2021-0021
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Jianchao Bai;Deren Han;Hao Sun;Hongchao Zhang
中科院分区：
文献类型：
--
作者：
Jianchao Bai;Deren Han;Hao Sun;Hongchao Zhang
本文提出了一种求解线性约束可分离凸优化问题的对称加速随机交替方向乘子法（SAS-ADMM）。目标函数是一个可能非光滑的凸函数与许多光滑凸函数的平均函数之和。我们提出的算法结合了ADMM的思想和加速随机梯度方法的技术，可能与方差减少来解决光滑子问题。SAS-ADMM的一个主要特点是它的对偶变量在分离的原始变量的每次更新之后对称地更新，与标准的确定性或随机ADMM相比，这使得对偶变量的收敛区域更大、更灵活。证明了该随机优化算法具有遍历期望收敛性和O（1/T）的收敛速度，其中T为外迭代次数。我们的初步实验表明，该算法是非常有效的解决可分离优化问题的大数据应用。最后，在附录中讨论了算法的3块扩展及其加速随机增广拉格朗日方法的变体。
In this paper, we develop a symmetric accelerated stochastic Alternating Direction Method of Multipliers (SAS-ADMM) for solving separable convex optimization problems with linear constraints. The objective function is the sum of a possibly nonsmooth convex function and an average function of many smooth convex functions. Our proposed algorithm combines both ideas of ADMM and the techniques of accelerated stochastic gradient methods possibly with variance reduction to solve the smooth subproblem. One main feature of SAS-ADMM is that its dual variable is symmetrically updated after each update of the separated primal variable, which would allow a more flexible and larger convergence region of the dual variable compared with that of standard deter-ministic or stochastic ADMM. This new stochastic optimization algorithm is shown to have ergodic converge in expectation with O(1/T) convergence rate, where T is the number of outer iterations. Our preliminary experiments indicate the proposed algorithm is very effective for solving separable optimization problems from big-data applications. Finally, 3-block extensions of the algorithm and its variant of an accelerated stochastic augmented Lagrangian method are discussed in the appendix.