SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

By Cong Fang, Chris Junchi Li, Zhouchen Lin, T. Zhang. Neural Information Processing Systems, 2018

683 citations recorded by the source corpus.

In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order methods. For stochastic first-order method, combining SPIDER with normalized gradient descent, we propose two new algorithms, namely SPIDER-SFO and SPIDER-SFO\textsuperscript{+}, that solve non-convex stochastic optimization problems using stochastic gradients only. We provide sharp error-bound results on their convergence rates. In special, we prove that the SPIDER-SFO and SPIDER-SFO\textsuperscript{+} algorithms achieve a record-breaking gradient computation cost of $\mathcal{O}\left( \min( n^{1/2} \epsilon^{-2}, \epsilon^{-3} ) \right)$ for finding an $\epsilon$-approximate first-order and $\tilde{\mathcal{O}}\left( \min( n^{1/2} \epsilon^{-2}+\epsilon^{-2.5}, \epsilon^{-3} ) \right)$ for finding an $(\epsilon, \mathcal{O}(\epsilon^{0.5}))$-approximate second-order stationary point, respectively. In addition, we prove that SPIDER-SFO nearly matches the algorithmic lower bound for finding approximate first-order stationary points under the gradient Lipschitz assumption in the finite-sum setting. For stochastic zeroth-order method, we prove a cost of $\mathcal{O}( d \min( n^{1/2} \epsilon^{-2}, \epsilon^{-3}) )$ which outperforms all existing results.

Subfields: Artificial Intelligence, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/0572951adde832f6f84e26b5fb87da8e1d1ebca5

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

Citations in the corpus

Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations (2019, background): “The result, in general, shows that for any NN that satisfies the so-called strict saddle property (Ge et al., 2015), noisy gradient descent (NGD) can efficiently find a local minimal (Jin et al., 2017; Fang et al., 2018, 2019).”
Lower bounds for non-convex stochastic optimization (2019, positive): “This lower bound is incomparable to ours: the stochastic gradient construction in the paper [25] has unbounded variance, so it cannot imply results along the lines of Theorem 3.”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, methodology): “SPIDER has decent performance in the last two datasets.”
L ] 1 0 A pr 2 01 9 AdaGrad-Norm convergence over nonconvex landscapes AdaGrad stepsizes : sharp convergence over nonconvex landscapes , from any initialization (2019, methodology): “It is becoming common to define an ε-approximate stationary point as ‖∇F (x)‖ ≤ ε (Agarwal et al., 2017; Carmon et al., 2018, 2017a; Fang et al., 2018; Zhou et al., 2018; Allen-Zhu, 2018), but we use the convention ‖F (x)‖2 ≤ ε (Lei et al., 2017; Bottou et al., 2018) to most easily compare our…”
Momentum Improves Normalized SGD (2020, background): “Recently, these have provided provable improvements over SGD’s convergence rate, ﬁnding a point with E [ (cid:107)∇ F ( (cid:126)w ) (cid:107) ] ≤ O (1 /T 1 / 3 ) after T iterations (Fang et al., 2018; Zhou et al., 2018).”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, methodology): “It is becoming common to define an ε-approximate stationary point as ‖∇F (x)‖ ≤ ε (Agarwal et al., 2017; Carmon et al., 2018, 2017a; Fang et al., 2018; Zhou et al., 2018; Allen-Zhu, 2018), but we use the convention ‖F (x)‖ ≤ ε (Lei et al.”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “One elegant approach is variance reduction (e.g. Schmidt et al., 2017; Johnson and Zhang, 2013; Defazio et al., 2014; Bach and Moulines, 2013; Koneˇcn`y and Richt´arik, 2013; Xiao and Zhang, 2014; Gong and Ye, 2014; Fang et al., 2018; Zhou et al., 2018b).”
Variance Reduction for Matrix Games (2019, background): “A multitude of variance reduction schemes exist for finite-sum minimization [17, 26, 1, 4, 11], and their impact on complexity is well-understood [32].”
Momentum-Based Variance Reduction in Non-Convex SGD (2019, methodology): “[17, 7, 24]) do not make use of this assumption.”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “Because there are two variables x and y in our problem (2), it is not efficient to combine SGDA with SPIDER [15] or (inexact) SARAH [29, 30] directly.”
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 σ”
The Complexity of Making the Gradient Small in Stochastic Convex Optimization (2019, methodology): “For certain stochastic first-order optimization algorithms based on variance reduction (SCSG (Lei et al., 2017), SPIDER (Fang et al., 2018)), a gradient must be computed at multiple points for the same sample f(⋅; z).”
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.”
Projection-Free Adaptive Gradients for Large-Scale Optimization (2020, methodology): “…of FW to the large-scale setting of Problem (1), SVRF and SPIDER-FW integrate variance reduction based on the works of Johnson and Zhang (2013) and Fang et al. (2018) respectively, ORGFW uses a form of momentum inspired by Cutkosky and Orabona (2019), and CSFW takes advantage of the additive…”