Stochastic Variance-Reduced ADMM
This work addresses storage efficiency for large-scale optimization in machine learning, offering an incremental improvement over prior methods.
The paper tackles the high storage requirements of existing stochastic ADMM methods by integrating ADMM with SVRG, resulting in an algorithm with low storage independent of sample size and fast convergence comparable to SAG-ADMM and SDCA-ADMM, as shown in experiments where it is much faster than SCAS-ADMM and handles bigger datasets.
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.