Non-convex Finite-Sum Optimization Via SCSG Methods

By Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan. 2017

257 citations recorded by the source corpus.

We develop a class of algorithms, as variants of the stochastically controlled stochastic gradient (SCSG) methods (Lei and Jordan, 2016), for the smooth non-convex finite-sum optimization problem. Assuming the smoothness of each component, the complexity of SCSG to reach a stationary point with $\mathbb{E} \|\nabla f(x)\|^{2}\le \epsilon$ is $O\left (\min\{\epsilon^{-5/3}, \epsilon^{-1}n^{2/3}\}\right)$, which strictly outperforms the stochastic gradient descent. Moreover, SCSG is never worse than the state-of-the-art methods based on variance reduction and it significantly outperforms them when the target accuracy is low. A similar acceleration is also achieved when the functions satisfy the Polyak-Lojasiewicz condition. Empirical experiments demonstrate that SCSG outperforms stochastic gradient methods on training multi-layers neural networks in terms of both training and validation loss.

Subfields: Artificial Intelligence, Computational Mechanics

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

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, neutral): “ee Theorem 1) SGD3 sc (SGD + recursive regularization) O " 2 log 3 (see Theorem 3) online nonconvex ( -nonconvex) SGD (naive) O " 4 (folklore, see e.g. [3, 17]) SCSG O " 10 = 3 (see [21]) SGD4 O " 2 + " 4 (see Theorem 4) Natasha1 :5 O " 3 + 1 = 3 " 10 = 3 (see [3”
fPINNs: Fractional Physics-Informed Neural Networks (2018, methodology): “On the other hand, we will investigate other available optimization algorithms such as in references [67, 68] in order to expedite finding better local minima.”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, methodology): “Several papers have show encouraging results when using SVRG variants on small MNIST training problems [Johnson and Zhang, 2013, Lei et al., 2017].”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “ERM) problems such as Lasso, SVM, Logistic Regression, fall into this category (see Section 1.3). Ecient stochastic methods for Problem (1.1) have also inspired stochastic algorithms for neural nets [5, 29, 34] as well as SVD, PCA, and CCA [7, 9, 26]. We summarize the history of stochastic gradient ”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, neutral): “, 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 results to those from Ghadimi and Lan (2013); Li and Orabona (2019).”
Not All Samples Are Created Equal: Deep Learning with Importance Sampling (2018, methodology): “The algorithms we considered were SVRG (Johnson & Zhang, 2013), accelerated SVRG with Katyusha momentum (Allen-Zhu, 2017) and, the most suitable for Deep Learning, SCSG (Lei et al., 2017) which in practice is a mini-batch version of SVRG. SAGA (De-fazio et al., 2014) was not considered due to the pr”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, methodology): “However, as discussed in [20, 27], the method called SPIDER in [8, 12] does not practically perform well due to small step-size and its dependence on the reciprocal of the estimator’s norm.”
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization (2018, methodology): “In addition to NAG and HB methods, stochastic variance reduced gradient (SVRG) methods integrate SGD with GD to acquire a hybrid descent direction of reduced variance (Johnson & Zhang, 2013; Reddi et al., 2016; Lei et al., 2017).”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “1 This update can be also seen in a way that outer loop size is generated by geometric distribution similar to [14, 15].”
An Energy Approach to the Solution of Partial Differential Equations in Computational Mechanics via Machine Learning: Concepts, Implementation and Applications (2019, background): “we end up facing a non-convex finite-sum optimization problem [15]: min p ∑”
Neon2: Finding Local Minima via First-Order Oracles (2017, methodology): “ the epoch length to B b , and replaced r fi (xt )i e ) with 1 jS 0 j P i2 S 0 r fi (xt ) r fi e for some S 0 that is a random subset of [ n ] with cardinality jS 0j = b. 12 We remark that Lei et al. [19] only showed that an epoch runs in an expectation of O (B ) stochastic gradients. We assume it i”
Distributed Stochastic Optimization via Adaptive SGD (2018, methodology): “This is an important aspect of the algorithm: even prior analyses that meet the same time, space and communication costs [9, 12, 13] require the user to input the smoothness parameter to tune a learning rate.”
How To Make the Gradients Small Stochastically (2018, unknown): “For instance, to find a point x with ‖∇f(x)‖ ≤ ε, the state-of-the-art stochastic method converges in T ∝ ε−10/3 iterations [12], or T ∝ ε−3.”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “For illustrations, let us compare the sampling efficiency among SGD, SCSG and Spider-SFO in their special cases.”
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “PL condition is particularly suited for analyzing overparameterized problems and has been utilized by several recent papers (Bassily et al., 2018; Karimi et al., 2016; Lei et al., 2017; Ma et al., 2017; Vaswani et al., 2018).”
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).”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “In the ofﬂine method SCSG , Lei et al. [30] carefully performed updates so that all “ﬁrst-order errors” cancel out.”