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

By Lam M. Nguyen, Jie Liu, Katya Scheinberg, Martin Takác. 2017

717 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Some popular examples of variance reduced algorithms are SAG (Schmidt et al., 2017), SAGA (Defazio et al., 2014), SVRG (Johnson & Zhang, 2013) and SARAH (Nguyen et al., 2017).”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “Another class of algorithms includes stochastic variation reduction techniques that include SVRG [Johnson and Zhang, 2013], SAGA [Roux et al., 2012] and their variants listed out in [Nguyen et al., 2017].”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, background): “…variance reduction framework have been developed, they can generally be characterized into one of several classes: SAGA-like [Defazio et al., 2014a], SVRG-like [Johnson and Zhang, 2013], Dual [Shalev-Shwartz and Zhang, 2013], Catalyst [Lin et al., 2015] or SARAH-like [Nguyen et al., 2017].”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “…& Zhang, 2013; Defazio et al., 2014; Qu et al., 2015; Shalev-Shwartz, 2016; Qu et al., 2016; Csiba & Richtárik, 2015; Csiba et al., 2015; Nguyen et al., 2017; Gower et al., 2018; Zhou, 2018) admit linear convergence on empirical risk minimization problems, surpassing the rate of…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “The area of single-machine optimization algorithms for finite average of functions recently saw numerous contributions, such as [163, 158, 80, 89, 45, 5, 131].”
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption (2018, background): “Recently, a class of variance reduction methods (Le Roux et al., 2012; Defazio et al., 2014; Johnson & Zhang, 2013; Nguyen et al., 2017) has been proposed in order to reduce the computational cost.”
Variance Reduced Local SGD with Lower Communication Complexity (2019, background): “Although there are many studies proposed to reduce the variance in SGD, e.g., SVRG [Johnson and Zhang, 2013], SAGA [Defazio et al., 2014], and SARAH [Nguyen et al., 2017], they could not directly deal with the gradient variance among workers in distributed optimization.”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, methodology): “The state of the art comprises i) stochastic sub-gradient methods [28], ii) variance reduced stochastic gradient methods [2, 8, 12, 15, 20], iii) coordinate methods (e.”
Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales (2019, methodology): “As an alternative to the basic SGD several variance reducing stochastic methods have been proposed recently, such as SAGA [12], SVRG [18] and SARAH [21].”
Momentum-Based Variance Reduction in Non-Convex SGD (2019, background): “The only exceptions we are aware of are SARAH [17, 18] and iSARAH [19].”
Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample (2019, methodology): “[43] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč.”
Towards closing the gap between the theory and practice of SVRG (2019, methodology): “org/lightning/ and [21] for examples where m = n.”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, background): “…method and its variance-reduced variants (e.g., SAG (Roux et al., 2012), SAGA (Defazio et al., 2014a), SVRG (Johnson and Zhang, 2013), and SARAH (Nguyen et al., 2017)) for solving (P) under strong convexity and smoothness structures usually have theoretically linear convergence rates compared…”
Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (2020, methodology): “Our methods exploit a recent biased hybrid estimators introduced in [35] as opposed to SARAH ones in [34, 43, 45].”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “Their algorithm called SREDA uses the SPIDER/SARAH technique [42, 129] to update the gradient estimators ut+1 and vt+1, i.”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “While sampling strategies such as importance sampling and mini-batching reduce the variance of the stochastic gradient, in the finite-sum case (3) a new type of variance reduction strategies has been developed over the last few years (Roux et al., 2012; Defazio et al., 2014; Johnson and Zhang, 2013;”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “Other concurrent works As the current work is carried out in its final phase, the authors became aware that an idea of resemblance was earlier presented in an algorithm named the StochAstic Recursive grAdient algoritHm (SARAH) [28, 29].”