SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient¶
Authors: Lam M. Nguyen, Jie Liu, Katya Scheinberg, Martin Takáč
Published: 2017 ()
Algorithm: SARAH
arXiv: 1703.00102
Summary¶
Abstract¶
In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framework for updating stochastic gradient estimates; when comparing to SAG/SAGA, SARAH does not require a storage of past gradients. The linear convergence rate of SARAH is proven under strong convexity assumption. We also prove a linear convergence rate (in the strongly convex case) for an inner loop of SARAH, the property that SVRG does not possess. Numerical experiments demonstrate the efficiency of our algorithm.