Stochastic Variance-Reduced ADMM

Abstract

The alternating direction method of multipliers (ADMM) is a powerful optimization solver in machine learning. Recently, stochastic ADMM has been integrated with variance reduction methods for stochastic gradient, leading to SAG-ADMM and SDCA-ADMM that have fast convergence rates and low iteration complexities. However, their space requirements can still be high. In this paper, we propose an integration of ADMM with the method of stochastic variance reduced gradient (SVRG). Unlike another recent integration attempt called SCAS-ADMM, the proposed algorithm retains the fast convergence benefits of SAG-ADMM and SDCA-ADMM, but is more advantageous in that its storage requirement is very low, even independent of the sample size $n$. We also extend the proposed method for nonconvex problems, and obtain a convergence rate of $O(1/T)$. Experimental results demonstrate that it is as fast as SAG-ADMM and SDCA-ADMM, much faster than SCAS-ADMM, and can be used on much bigger data sets.

References in corpus (6)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A General Analysis of the Convergence of ADMM
• Online Alternating Direction Method
• Scalable Stochastic Alternating Direction Method of Multipliers

Cited by in corpus (2)

• Stochastic Primal-Dual Proximal ExtraGradient Descent for Compositely Regularized Optimization
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization