mlsanityData to 7 Oct 2026

Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

arXiv 1503.02101 ↗First posted 6 Mar 2015cs.LG math.OC stat.MLcited by 241

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 241 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Mar 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 64; 2022: 52; 2023: 36; 2024: 28; 2025: 30; 2026: 30.

241 papers.

Sort:

By area:

  1. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 226
  2. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  3. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  4. 2022On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Featurescited by 97
  5. 2022Robust Training under Label Noise by Over-parameterizationcited by 93
  6. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  7. 2024β-DPO: Direct Preference Optimization with Dynamic βcited by 89
  8. 2021An Unconstrained Layer-Peeled Perspective on Neural Collapsecited by 87
  9. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  10. 2022Are All Losses Created Equal: A Neural Collapse Perspectivecited by 78
  11. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  12. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
38 more
  1. 2021Stochastic Training is Not Necessary for Generalizationcited by 63
  2. 2022The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minimacited by 51
  3. 2022Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifoldcited by 50
  4. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  5. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  6. 2021Deep Ensembling with No Overhead for either Training or Testing: The All-Round Blessings of Dynamic Sparsitycited by 44
  7. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 43
  8. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 42
  9. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  10. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  11. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  12. 2025Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation Is Wastefulcited by 36
  13. 2021Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomizationcited by 35
  14. 2021Taxonomizing local versus global structure in neural network loss landscapescited by 34
  15. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  16. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  17. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  18. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
  19. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  20. 2022Escaping Saddle Points for Effective Generalization on Class-Imbalanced Datacited by 28
  21. 2022Implicit Full Waveform Inversion with Deep Neural Representationcited by 26
  22. 2021Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysiscited by 25
  23. 2021Overparameterization of deep ResNet: zero loss and mean-field analysiscited by 24
  24. 2021The loss landscape of deep linear neural networks: a second-order analysiscited by 24
  25. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  26. 2023An SDE for Modeling SAM: Theory and Insightscited by 22
  27. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  28. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  29. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  30. 2021The dilemma of quantum neural networkscited by 20
  31. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  32. 2024A Unified and General Framework for Continual Learningcited by 19
  33. 2025LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)cited by 19
  34. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  35. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  36. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  37. 2022BEINIT: Avoiding Barren Plateaus in Variational Quantum Algorithmscited by 15
  38. 2021Lazy OCO: Online Convex Optimization on a Switching Budgetcited by 14

50 most cited of 241 All 241 (JSON)