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 @math . 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.
For gradient descent, a similar gap in convergence rates between the stochastic and batch algorithms is well-known @cite_15 . As noted by @cite_24 , the underlying reason is that SGD has to control the gradient's variance by gradually reducing its stepsize @math . Recently, by observing that the training set is always finite in practice, a number of variance reduction techniques have been developed that allow the use of a constant stepsize, and consequently faster convergence. In this paper, we focus on the SVRG @cite_24 , which is advantageous in that no extra space for the intermediate gradients or dual variables is needed. The algorithm proceeds in stages. At the beginning of each stage, the gradient @math is computed using a past parameter estimate @math . For each subsequent iteration @math in this stage, the approximate gradient is used, where @math is a mini-batch of size @math from @math . Note that @math is unbiased (i.e., @math ), and its (expected) variance goes to zero asymptotically.
@cite_24 @cite_15
2107438106 2105875671
Stochastic gradient descent is popular for large scale optimization but has slow convergence asymptotically due to the inherent variance. To remedy this problem, we introduce an explicit variance reduction method for stochastic gradient descent which we call stochastic variance reduced gradient (SVRG). For smooth and strongly convex functions, we prove that this method enjoys the same fast convergence rate as those of stochastic dual coordinate ascent (SDCA) and Stochastic Average Gradient (SAG). However, our analysis is significantly simpler and more intuitive. Moreover, unlike SDCA or SAG, our method does not require the storage of gradients, and thus is more easily applicable to complex problems such as some structured prediction problems and neural network learning. We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly.