Fast Stochastic Alternating Direction Method of Multipliers

Abstract

In this paper, we propose a new stochastic alternating direction method of multipliers (ADMM) algorithm, which incrementally approximates the full gradient in the linearized ADMM formulation. Besides having a low per-iteration complexity as existing stochastic ADMM algorithms, the proposed algorithm improves the convergence rate on convex problems from $O(\frac{1}{\sqrt{T}})$ to $O(\frac{1}{T})$, where $T$ is the number of iterations. This matches the convergence rate of the batch ADMM algorithm, but without the need to visit all the samples in each iteration. Experiments on the graph-guided fused lasso demonstrate that the new algorithm is significantly faster than state-of-the-art stochastic and batch ADMM algorithms.

References in corpus (1)

• Online Alternating Direction Method

Cited by in corpus (9)

• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Convolutional Dictionary Learning: Acceleration and Convergence
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Image Super-Resolution via RL-CSC: When Residual Learning Meets Convolutional Sparse Coding
• Scalable Plug-and-Play ADMM with Convergence Guarantees
• Stochastic Modified Equations for Continuous Limit of Stochastic ADMM
• Random constraint sampling and duality for convex optimization
• Distributed Machine Learning for Predictive Analytics in Mobile Edge Computing Based IoT Environments