Scalable Stochastic Alternating Direction Method of Multipliers

Abstract

Stochastic alternating direction method of multipliers (ADMM), which visits only one sample or a mini-batch of samples each time, has recently been proved to achieve better performance than batch ADMM. However, most stochastic methods can only achieve a convergence rate $O(1/\sqrt{T})$ on general convex problems,where T is the number of iterations. Hence, these methods are not scalable with respect to convergence rate (computation cost). There exists only one stochastic method, called SA-ADMM, which can achieve convergence rate $O(1/T)$ on general convex problems. However, an extra memory is needed for SA-ADMM to store the historic gradients on all samples, and thus it is not scalable with respect to storage cost. In this paper, we propose a novel method, called scalable stochastic ADMM(SCAS-ADMM), for large-scale optimization and learning problems. Without the need to store the historic gradients, SCAS-ADMM can achieve the same convergence rate $O(1/T)$ as the best stochastic method SA-ADMM and batch ADMM on general convex problems. Experiments on graph-guided fused lasso show that SCAS-ADMM can achieve state-of-the-art performance in real applications

References in corpus (2)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Online Alternating Direction Method

Cited by in corpus (10)

• Accelerated Variance Reduced Stochastic ADMM
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Temporal Model Adaptation for Person Re-Identification
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Stochastic Variance-Reduced ADMM
• A Stochastic Variance Reduced Primal Dual Fixed Point Method For Linearly Constrained Separable Optimization
• Stochastic primal dual fixed point method for composite optimization
• Scalable Peaceman-Rachford Splitting Method with Proximal Terms
• Convergence on a symmetric accelerated stochastic ADMM with larger stepsizes