Fast stochastic alternating direction method of multipliers

2014 We propose a new stochastic alternating direction method of multipliers (ADMM) algorithm, which incrementally approximates the ful1 gradient in the linearized ADMM formulation. Besides having a low per-iteration complexity as existing stochastic ADMIvI algorithms, it improves the convergence rate on convex problems from O(1/√T) to O(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