Stochastic Recursive Gradient Algorithm for Nonconvex Optimization

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

100 citations recorded by the source corpus.

In this paper, we study and analyze the mini-batch version of StochAstic Recursive grAdient algoritHm (SARAH), a method employing the stochastic recursive gradient, for solving empirical loss minimization for the case of nonconvex losses. We provide a sublinear convergence rate (to stationary points) for general nonconvex functions and a linear convergence rate for gradient dominated functions, both of which have some advantages compared to other modern stochastic gradient algorithms for nonconvex losses.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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

Citations in the corpus

SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “− One could use an update similar to that of SARAH (Nguyen et al., 2017) and continuously perform local updates to c i instead of keeping it ﬁxed.”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, methodology): “VR methods were recently extended to work with (non-strongly) convex losses [13], and more recently also to non-convex losses [29, 28, 2, 23], in all cases leading to best current rates for (1) in a given function class.”
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].”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “Thus SCAFFOLD can be seen as an extension of variance reduction techniques for federated learning, and one could similarly extend SARAH (Nguyen et al., 2017), SPIDER (Fang et al., 2018), etc. Note that standard SGD with client sampling is provably slower and converges at a sublinear rate even with σ”
Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales (2019, methodology): “In particular, we show that the expected number of iterations required to achieve ‖∇f(x)‖ ≤ is bounded by O( −2/(2p − 1)), which is an improvement on the result in [14] and a similar one to those in [25, 22], in terms of dependence on , but such that, in principal, it never requires computation of t”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, background): “Other researchers have also made signiﬁcant progress in this direction, including [2, 3, 4, 8, 12, 16, 17, 18, 22, 27, 30].”
On the Acceleration of L-BFGS with Second-Order Information and Stochastic Batches (2018, unknown): “Numerous work has focused on the choice of g k such as SAG/SAGA [30, 7], MISO/FINITO [17, 8], SDCA [32], SVRG/S2GD [11, 13], SARAH [23, 24].”
Momentum-Based Variance Reduction in Non-Convex SGD (2019, background): “The only exceptions we are aware of are SARAH [17, 18] and iSARAH [19].”