Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition
By Rong Ge, Furong Huang, Chi Jin, Yang Yuan. 2015
1,144 citations recorded by the source corpus.
We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization. Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.
Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics, Optimization & Training, Mathematical Optimization
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
- Yoshua Bengio
- Tengyu Ma
- Ruslan Salakhutdinov
- Michael I. Jordan
- Jason D. Lee
- Percy Liang
- Sergey Levine
- Quoc V. Le
In Computational Mathematics
- Jason D. Lee
- Yuanzhi Li
- Anima Anandkumar
- Kfir Yehuda Levy
- Rong Ge
- Sham M. Kakade
- Simon Shaolei Du
- Michael I. Jordan
In Computational Mechanics
- Zeyuan Allen-Zhu
- Peter Richtárik
- Jason D. Lee
- Michael I. Jordan
- Francis R. Bach
- Nati Srebro
- Jakub Konecný
- Tengyu Ma
In Optimization & Training
- Jason D. Lee
- Zeyuan Allen-Zhu
- Peter Richtárik
- Tengyu Ma
- Yuanzhi Li
- Ohad Shamir
- Jakub Konecný
- Francis R. Bach
In Mathematical Optimization
- Zeyuan Allen-Zhu
- Prateek Jain
- Jason D. Lee
- Peter Richtárik
- Michael I. Jordan
- Sham M. Kakade
- Francis R. Bach
- Yuanzhi Li
Citations in the corpus
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, neutral): “5), where previously SGD variants only achieve Õ(ε−4) [6, 14, 30].”
- Deep Learning without Poor Local Minima (2016, methodology): “Thus, Theorem 2.3 and Corollary 2.4 suggest that for 1-hidden layer networks, training can be done in polynomial time with a second order method or even with a modified stochastic gradient decent method, as discussed in (Ge et al. , 2015).”
- BatchEnsemble: An Alternative Approach to Efficient Ensemble and Lifelong Learning (2020, background): “…of the deep neural networks, combined with the fact that there is a wide variety of local minima solutions in high dimensional optimization problem (Ge et al., 2015; Kawaguchi, 2016; Wen et al., 2019), results in the following observation: deep neural networks trained with different random seeds…”
- Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “…tuning: There are two benefits: (1) the policies found in the perturbed game may not remain an equilibrium in the original game, so fine-tuning ensures convergence; (2) in practice, fine-tuning could further help escape a suboptimal mode via the noise in PG (Ge et al., 2015; Kleinberg et al., 2018).”
- An Alternative View: When Does SGD Escape Local Minima? (2018, background): “For example, it is proved that noise helps to escape saddle points [7, 16], gives better generalization [9, 23], and also guarantees polynomial hitting time of good local minima under some assumptions [29].”
- A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “Several papers ( e.g. Ge et al. (2015); Lee et al. (2016)) have shown that (given certain smoothness properties) it suffices for critical points to meet the following two conditions: (i) no poor local minima — every local minimum is close in its objective value to a global minimum; and (ii) strict…”
- Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “In general, if the objective is strict-saddle [11], SGD could escape all saddle points.”
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “The hope is to leverage recent advance in first-order algorithms (Ge et al., 2015; Lee et al., 2016; Jin et al., 2017) which showed that if the landscape satisfies (1) all local minima are global and (2) all saddle points are strict (i.”
- Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, methodology): “Algorithms that provably work in this setting include cubic regularization [36], trust region methods [16], approximate cubic regularization schemes [3], [12], [13], randomly initialized and perturbed (stochastic) gradients [17], [22], [22], [29], [30].”
- Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “For this function class, researchers have shown (perturbed) gradient descent (Jin et al., 2017; Ge et al., 2015; Lee et al., 2016; Du et al., 2017a) can find a global minimum.”
- Few-Shot Learning via Learning the Representation, Provably (2020, background): “Therefore, randomly initialized gradient descent or perturbed gradient descent are guaranteed to converge to a global minimum of (16) in polynomial-time (Ge et al., 2015, Lee et al., 2016, Jin et al., 2017).”
- Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “4 Therefore, recent methods for showing global convergence of gradient-based optimizers on non-convex objectives (Lee et al., 2016; Ge et al., 2015) cannot be used in our case, because they assume all saddles are strict 5 and the objective function is continuously differentiable everywhere.”
- Learning Deep ResNet Blocks Sequentially using Boosting Theory (2017, background): “Furthermore, the entire training still relies on the unstable end-to-end back-propagation which are susceptible to suboptimal solutions (Ge et al. , 2015) in deep networks.”
- Hessian-based Analysis of Large Batch Training and Robustness to Adversaries (2018, background): “[12] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan.”
- Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, background): “SGD and noise: Noise is often added in SGD to improve its behavior around saddle points for non-convex losses, see Lee et al. (2016); Anandkumar and Ge (2016); Ge et al. (2015).”