Accelerated Variance Reduction Stochastic ADMM for Large-Scale Machine Learning

Recently, many stochastic variance reduced alternating direction methods of multipliers (ADMMs) (e.g., SAG-ADMM and SVRG-ADMM) have made exciting progress such as linear convergence rate for strongly convex (SC) problems. However, their best-known convergence rate for non-strongly convex (non-SC) problems is
$\mathcal {O}(1/T)$
as opposed to
$\mathcal {O}(1/T^2)$
of accelerated deterministic algorithms, where
$T$
is the number of iterations. Thus, there remains a gap in the convergence rates of existing stochastic ADMM and deterministic algorithms. To bridge this gap, we introduce a new momentum acceleration trick into stochastic variance reduced ADMM, and propose a novel accelerated SVRG-ADMM method (called ASVRG-ADMM) for the machine learning problems with the constraint
$Ax + By = c$
. Then we design a linearized proximal update rule and a simple proximal one for the two classes of ADMM-style problems with
$B = \tau I$
and
$B\ne \tau I$
, respectively, where
$I$
is an identity matrix and
$\tau$
is an arbitrary bounded constant. Note that our linearized proximal update rule can avoid solving sub-problems iteratively. Moreover, we prove that ASVRG-ADMM converges linearly for SC problems. In particular, ASVRG-ADMM improves the convergence rate from
$\mathcal {O}(1/T)$
to
$\mathcal {O}(1/T^2)$
for non-SC problems. Finally, we apply ASVRG-ADMM to various machine learning problems, e.g., graph-guided fused Lasso, graph-guided logistic regression, graph-guided SVM, generalized graph-guided fused Lasso and multi-task learning, and show that ASVRG-ADMM consistently converges faster than the state-of-the-art methods.