SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient

In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), well as its practical variant SARAH+, as a novel approach to the finite-sum problems. Different from the vanilla SGD and other modern methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple framework for updating stochastic gradient estimates; when comparing SAG/SAGA, SARAH does not require a storage of past gradients. The linear rate of SARAH is proven under strong convexity assumption. We also a linear convergence rate (in the strongly convex case) for an inner loop SARAH, the property that SVRG does not possess. Numerical experiments the efficiency of our algorithm.