Convergence on a Symmetric Accelerated Stochastic ADMM with Larger Stepsizes (CSIAM Transactions on Applied Mathematics, 2022)
In this paper, we develop a symmetric accelerated stochastic AlternatingDirection Method of Multipliers (SAS-ADMM) for solving separable convex optimization problems with linear constraints. The objective function is the sum of a possiblynonsmooth convex function and an average function of many smooth convex functions. Our proposed algorithm combines both ideas of ADMM and the techniques ofaccelerated stochastic gradient methods possibly with variance reduction to solve thesmooth 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 withthat of standard deterministic or stochastic ADMM. This new stochastic optimizationalgorithm is shown to have ergodic converge in expectation with $\mathcal{O}(1/T)$ convergencerate, where $T$ denotes the number of outer iterations. Our preliminary experimentsindicate the proposed algorithm is very effective for solving separable optimizationproblems from big-data applications. Finally, 3-block extensions of the algorithm andits variant of an accelerated stochastic augmented Lagrangian method are discussed inthe appendix.
Keywords: Convex optimization; stochastic ADMM; symmetric ADMM; larger stepsize; proximal mapping; complexity.