mlsanityData to 7 Oct 2026

Why Do Local Methods Solve Nonconvex Problems?

arXiv 2103.13462 ↗First posted 24 Mar 2021cs.LG cs.DS math.OCcited by 8

Not on the map. Why?

Abstract (arXiv)

Non-convex optimization is ubiquitous in modern machine learning. Researchers devise non-convex objective functions and optimize them using off-the-shelf optimizers such as stochastic gradient descent and its variants, which leverage the local geometry and update iteratively. Even though solving non-convex functions is NP-hard in the worst case, the optimization quality in practice is often not an issue -- optimizers are largely believed to find approximate global minima. Researchers hypothesize a unified explanation for this intriguing phenomenon: most of the local minima of the practically-used objectives are approximately global minima. We rigorously formalize it for concrete instances of machine learning problems.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 46 of its 63 references that are in the map. First posted on arXiv 24 Mar 2021.

Builds on

46 of 63 references.

References · 46

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  7. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  8. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  9. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  10. 2017Implicit Regularization in Matrix Factorizationcited by 318
  11. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  12. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
34 more
  1. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  2. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  3. 2016Deep Learning without Poor Local Minimacited by 233
  4. 2019Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networkscited by 162
  5. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  6. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  7. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  8. 2016Identity Matters in Deep Learningcited by 107
  9. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  10. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  11. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  12. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  13. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  14. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  15. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  16. 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
  17. 2019Implicit Regularization for Optimal Sparse Recoverycited by 78
  18. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 75
  19. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  20. 2016Global rates of convergence for nonconvex optimization on manifoldscited by 61
  21. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  22. 2016The non-convex Burer-Monteiro approach works on smooth semidefinite programscited by 44
  23. 2016No bad local minima: Data independent training error guarantees for multilayer neural networkscited by 29
  24. 2015When Are Nonconvex Problems Not Scary?cited by 27
  25. 2016Gradient Descent Converges to Minimizerscited by 25
  26. 2015Global Optimality in Tensor Factorization, Deep Learning, and Beyondcited by 22
  27. 2013Gradient methods for convex minimization: better rates under weaker conditionscited by 21
  28. 2017On the Optimization Landscape of Tensor Decompositionscited by 21
  29. 2015On the Quality of the Initial Basin in Overspecified Neural Networkscited by 20
  30. 2016Accelerated Methods for Non-Convex Optimizationcited by 20
  31. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  32. 2016On the low-rank approach for semidefinite programs arising in synchronization and community detectioncited by 17
  33. 2013Provable Bounds for Learning Some Deep Representationscited by 14
  34. 2016Finding Approximate Local Minima Faster than Gradient Descentcited by 8

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 2; 2023: 4.

8 papers.

  1. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  2. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  3. 2022Continuously Discovering Novel Strategies via Reward-Switching Policy Optimizationcited by 23
  4. 2023Efficient automatic design of robotscited by 11
  5. 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
  6. 2021Self-learn to Explain Siamese Networks Robustlycited by 5
  7. 2023Iteratively Learn Diverse Strategies with State Distance Informationcited by 3
  8. 2023Diverse Policy Optimization for Structured Action Spacecited by 1