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

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