Fast Stochastic Alternating Direction Method of Multipliers
This work addresses the need for faster optimization in large-scale machine learning problems, offering an incremental improvement over existing stochastic ADMM methods.
The paper tackles the problem of slow convergence in stochastic ADMM algorithms by proposing a new method that approximates the full gradient incrementally, achieving an improved convergence rate from O(1/√T) to O(1/T) on convex problems, with experiments showing it is significantly faster than state-of-the-art algorithms.
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.