The DOI matches its Crossref record.
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
Open accessAbstract
In this paper, we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the numbers of observations are fewer than the number of parameters in the model. We show that with the quadratic activations, the optimization landscape of training, such shallow neural networks, has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions, we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Larger models are 'easy' to optimize as local methods, such as SGD, converge to global minima of the training risk in over-parametrized regimes.
“There is a growing understanding that larger models are 'easy' to optimize as local methods, such as SGD, converge to global minima of the training risk in over-parametrized regimes (e.g., [36]).”
From Reconciling modern machine-learning practice and the classical bias–variance trade-off (2019) · cites this paper as [36]
Section 2.1 and Remark 2.6 support global convergence of local methods in over-parameterized shallow networks, but under specific conditions: quadratic activations for the landscape result, or suitably initialized gradient descent with Gaussian inputs for the convergence result. The Related Work section cites empirical SGD results, but the paper does not establish the citing sentence’s broader claim that SGD converges to global training-risk minima across over-parameterized larger models. (LLM, conf=0.85)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 56
- 10.1109/IJCNN.1991.155333 · DOI
- polyak, 1963, Gradient methods for minimizing functionals, Zhurnal Wychislitelnoy Matematiki i Matematicheskoy Fiziki, 3, 643
- livni, 2014, On the computational efficiency of training neural networks, Proc Adv Neural Inf Process Syst, 855
- li, 2017, Convergence analysis of two-layer neural networks with relu activation
- li, 2017, Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
- levy, 2016, The power of normalization Faster evasion of saddle points
- nguyen, 2017, The loss surface of deep and wide neural networks
- 10.1007/s10107-006-0706-8 · DOI
- 10.1109/TASL.2011.2109382 · DOI
- mei, 2016, The landscape of empirical risk for non-convex losses
- ledoux, 2005, The Concentration of Measure Phenomenon, 89, 10.1090/surv/089 · DOI
- 10.1109/MSP.2017.2671158 · DOI
- lee, 2016, Gradient descent only converges to minimizers, Proc Conf Learn Theory, 1246
- 10.1007/s00365-010-9117-4 · DOI
- adamczak, 2015, A note on the Hanson–Wright inequality for random vectors with dependencies, Electron Commun Probab, 20, 1, 10.1214/ECP.v20-3829 · DOI
- hazan, 2015, Beyond convexity: Stochastic quasi-convex optimization, Proc Adv Neural Inf Process Syst, 1594
- jin, 2017, How to escape saddle points efficiently
- janzamin, 2015, Beating the perils of non-convexity Guaranteed training of neural networks using tensor methods
- kalai, 2009, The isotron algorithm: High-dimensional isotonic regression, Proc Conf Learning Theory (COLT)
- kakade, 2011, Efficient learning of generalized linear and single index models with isotonic regression, Proc Adv Neural Inf Process Syst, 927
- krizhevsky, 2012, ImageNet classification with deep convolutional neural networks, Proc Adv Neural Inf Process Syst, 1097
- kawaguchi, 2016, Deep learning without poor local minima, Proc Adv Neural Inf Process Syst, 586
- vershynin, 2010, Introduction to the Non-Asymptotic Analysis of Random Matrices
- 10.1088/0305-4470/30/17/002 · DOI
- zhong, 2017, Recovery guarantees for one-hidden-layer neural networks
- zhang, 2016, $\ell_{1}$ -regularized neural networks are improperly learnable in polynomial time, Proc Int Conf Mach Learn, 993
- zhang, 2017, Convergence results for neural networks via electrodynamics
- zhang, 2016, Understanding deep learning requires rethinking generalization
- xie, 2016, Diverse neural network learns true target functions
- wiatowski, 2017, Energy propagation in deep convolutional neural networks
- brutzkus, 2017, Globally optimal gradient descent for a ConvNet with Gaussian inputs
- 10.1109/TIT.2015.2399924 · DOI
- 10.1103/PhysRevE.52.4225 · DOI
- carmon, 2016, Gradient descent efficiently finds the cubic-regularized non-convex newton step
- carmon, 2016, Accelerated methods for non-convex optimization
- choromanska, 2015, The loss surfaces of multilayer networks, Proc AISTATS, 192
- 10.1145/1390156.1390177 · DOI · Paper page
- 10.1007/s10107-016-1026-2 · DOI
- ge, 2015, Escaping from saddle points—Online stochastic gradient for tensor decomposition, Proc 28th Conf Learn Theory, 797
- goel, 2016, Reliably learning the ReLU in polynomial time
- haeffele, 2015, Global optimality in tensor factorization deep learning and beyond
- 10.1017/CBO9780511801334 · DOI
- agarwal, 2016, Finding approximate local minima faster than gradient descent
- bartlett, 2017, Spectrally-normalized margin bounds for neural networks
- 10.1007/BF00993164 · DOI
- blum, 1989, Training a 3-node neural network is NP-complete, Proc Adv Neural Inf Process Syst, 494
- 10.1088/0305-4470/29/16/005 · DOI
- tian, 2017, An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis, Proc Int Conf Mach Learn (ICML), 1
- bölcskei, 2017, Optimal approximation with sparsely connected deep neural networks
- soudry, 2016, No bad local minima Data independent training error guarantees for multilayer neural networks
- soltanolkotabi, 2017, Structured signal recovery from quadratic measurements Breaking sample complexity barriers via nonconvex optimization
- telgarsky, 2016, Benefits of depth in neural networks
- soudry, 2017, Exponentially vanishing sub-optimal local minima in multilayer neural networks
- 10.1137/100806126 · DOI
- safran, 2017, Spurious local minima are common in two-layer ReLU neural networks
- soltanolkotabi, 2017, Learning ReLUs via gradient descent
Cited by
Sorted by citations
Reconciling modern machine-learning practice and the classical bias–variance trade-off
Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1903070116 · Cited by 1,595
The Computational Limits of Deep Learning
Thompson, N. C., Greenewald, K., Lee, K., & Manso, G. F. (2020) · arXiv · doi:10.48550/arxiv.2007.05558 · Cited by 538
Liu, C.-Y., Kuo, E.-J., Abraham Lin, C.-H., Gemsun Young, J., Chang, Y.-J., Hsieh, M.-H., & Goan, H.-S. (2025) · Quantum Machine Intelligence · doi:10.1007/s42484-025-00305-0 · Cited by 40
Metadata
- Authors
- Soltanolkotabi, M., Javanmard, A., & Lee, J. D.
- Affiliations
- University of Southern California (US)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2019-02
- Volume
- 65
- Issue
- 2
- Pages
- 742-769
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2739160792
- Cited by
- 356
- References
- 0
- Citations by year
- 2026: 15 · 2025: 24 · 2024: 20 · 2023: 21 · 2022: 48 · 2021: 50 · 2020: 66 · 2019: 61
- FWCI
- 26.38
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Simons Institute for the Theory of Computing
- Air Force Office of Scientific Research (FA9550-18-1-0078)
- National Science Foundation (#1813877)
- Northrop Grumman
- Google Faculty Research Award
- University of Southern California
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- overparameterized neural networks, shallow neural networks, optimization landscape, global optimality, local search, gradient descent convergence, linear convergence, initialization, Gaussian input
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
