An inexact accelerated stochastic ADMM for separable convex optimization
An inexact accelerated stochastic ADMM for separable convex optimization
复制标题
DOI：
10.1007/s10589-021-00338-8
复制
发表时间：
2020-10
影响因子：
2.2
通讯作者：
Jianchao Bai;W. Hager;Hongchao Zhang
中科院分区：
文献类型：
--
作者：
Jianchao Bai;W. Hager;Hongchao Zhang
针对线性约束结构可分凸优化问题，提出了一种非精确加速随机交替方向乘子法（AS-ADMM）格式。目标函数是一个可能非光滑的凸函数和一个光滑函数的总和，光滑函数是许多分量凸函数的平均值。具有这种结构的问题经常出现在机器学习和数据挖掘应用中。AS-ADMM结合了ADMM和随机梯度方法的思想，使用方差缩减技术。其中一个ADMM子问题采用线性化技术，而类似的线性化可以引入其他子问题。对于一个特定的算法参数的选择，它表明，目标误差和约束违反是相对于外部迭代的次数sk。在强凸性假设下，期望误差线性收敛到零。还讨论了AS-ADMM的线性化变体和增量采样策略。随机和确定性ADMM算法的数值实验表明，AS-ADMM可以特别有效的大数据应用中出现的结构化优化。
An inexact accelerated stochastic Alternating Direction Method of Multipliers (AS-ADMM) scheme is developed for solving structured separable convex optimization problems with linear constraints. The objective function is the sum of a possibly nonsmooth convex function and a smooth function which is an average of many component convex functions. Problems having this structure often arise in machine learning and data mining applications. AS-ADMM combines the ideas of both ADMM and the stochastic gradient methods using variance reduction techniques. One of the ADMM subproblems employs a linearization technique while a similar linearization could be introduced for the other subproblem. For a specified choice of the algorithm parameters, it is shown that the objective error and the constraint violation arerelative to the number of outer iterationsk. Under a strong convexity assumption, the expected iterate error converges to zero linearly. A linearized variant of AS-ADMM and incremental sampling strategies are also discussed. Numerical experiments with both stochastic and deterministic ADMM algorithms show that AS-ADMM can be particularly effective for structured optimization arising in big data applications.