# Why Do Local Methods Solve Nonconvex Problems?

arXiv: https://arxiv.org/abs/2103.13462 · HTML: https://mlsanity.com/paper/2103.13462/

## Key facts

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

## Builds on (most cited first, 30 of 46)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks](https://mlsanity.com/paper/1907.04595/) (2019)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Shape Matters: Understanding the Implicit Bias of the Noise Covariance](https://mlsanity.com/paper/2006.08680/) (2020)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)

## Built on by (most cited first, 8 of 8)

- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Continuously Discovering Novel Strategies via Reward-Switching Policy Optimization](https://mlsanity.com/paper/2204.02246/) (2022)
- [Efficient automatic design of robots](https://mlsanity.com/paper/2306.03263/) (2023)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Self-learn to Explain Siamese Networks Robustly](https://mlsanity.com/paper/2109.07371/) (2021)
- [Iteratively Learn Diverse Strategies with State Distance Information](https://mlsanity.com/paper/2310.14509/) (2023)
- [Diverse Policy Optimization for Structured Action Space](https://mlsanity.com/paper/2302.11917/) (2023)

## 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.