On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchronous versions of these algorithms-a crucial requirement for modern large-scale applications-have not been studied. We bridge this gap by presenting a unifying framework for many variance reduction techniques. Subsequently, we propose an asynchronous algorithm grounded in our framework, and prove its fast convergence. An important consequence of our general approach is that it yields asynchronous versions of variance reduction algorithms such as SVRG and SAGA as a byproduct. Our method achieves near linear speedup in sparse settings common to machine learning. We demonstrate the empirical performance of our method through a concrete realization of asynchronous SVRG.
"Light" review:This work proposes a framework for linearly-convergent stochastic gradient methods that allows asynchronous computation. The paper analyzes a generalization of SVRG and SAGA, showing what speedups can be obtained.I like the statement of the general framework, and how it includes many of the previous algorithms. However, I think if you made two small modifications you could include basically all of the linearly-convergent primal methods:1. The framework doesn't seem to include SAG because the update is a bit different. In particular, SAG weighs the two $\nabla f_{i_t}$ terms by (1/n). If you added a weight to Algorithm 1 on these terms, it would allow you to include SAG. Further, adding these weight would allow you to include non-uniform sampling in the framework as in [27].2. In the update x^{t+1} = x^t - \eta(...), you could replace x^t by a weighted average of x^t and the alpha_i^t. If you do this, you could include MISO in the framework. MISO would correspond to weights of 1/n on the alpha_i^t, and all other methods place all their weight on x^t.I did not check the details, but all the results seems reasonable and plausible.The experiments are not terribly convincing in terms of utility of the method. On most datasets there only seems to be a small improvement over the locked SVRG (less than a factor of 2 in 3/4 cases). It would be interesting to see the difference if a larger number of threads were available.