mlsanityData to 14 Oct 2026

When Expressivity Meets Trainability: Fewer than n Neurons Can Work

arXiv 2210.12001 ↗First posted 21 Oct 2022cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Modern neural networks are often quite wide, causing large memory and computation costs. It is thus of great interest to train a narrower network. However, training narrow neural nets remains a challenging task. We ask two theoretical questions: Can narrow networks have as strong expressivity as wide ones? If so, does the loss function exhibit a benign optimization landscape? In this work, we provide partially affirmative answers to both questions for 1-hidden-layer networks with fewer than n (sample size) neurons when the activation is smooth. First, we prove that as long as the width m ≥ 2n/d (where d is the input dimension), its expressivity is strong, i.e., there exists at least one global minimizer with zero training loss. Second, we identify a nice local region with no local-min or saddle points. Nevertheless, it is not clear whether gradient descent can stay in this nice region. Third, we consider a constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point is a nearly global minimizer. It is expected that projected gradient methods converge to KKT points under mild technical conditions, but we leave the rigorous convergence analysis to future work. Thorough numerical results show that projected gradient methods on this constrained formulation significantly outperform SGD for training narrow neural nets.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 61 of its 81 references that are in the map. First posted on arXiv 21 Oct 2022.

Builds on

61 of 81 references.

References · 61

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2014ImageNet Large Scale Visual Recognition Challengecited by 8,498
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  5. 2016Wide Residual Networkscited by 3,070
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  7. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,329
  8. 2018Robustness May Be at Odds with Accuracycited by 880
  9. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  10. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  11. 2018On Lazy Training in Differentiable Programmingcited by 675
  12. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
38 more
  1. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  2. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  3. 2016Benefits of depth in neural networkscited by 250
  4. 2016Deep Learning without Poor Local Minimacited by 234
  5. 2017Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weightscited by 217
  6. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  7. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  8. 2019Complexity of Linear Regions in Deep Networkscited by 167
  9. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  10. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  11. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  12. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  13. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  14. 2016Topology and Geometry of Half-Rectified Network Optimizationcited by 102
  15. 2016Why does deep and cheap learning work so well?cited by 100
  16. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 88
  17. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  18. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  19. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 78
  20. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  21. 2017Deep linear neural networks with arbitrary loss: All local minima are globalcited by 65
  22. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
  23. 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
  24. 2020Perturbing Across the Feature Hierarchy to Improve Standard and Strict Blackbox Attack Transferabilitycited by 57
  25. 2020The Global Landscape of Neural Networks: An Overviewcited by 57
  26. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  27. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  28. 2018On the loss landscape of a class of deep neural networks with no bad local valleyscited by 38
  29. 2017The power of deeper networks for expressing natural functionscited by 35
  30. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  31. 2016Diverse Neural Network Learns True Target Functionscited by 33
  32. 2016No bad local minima: Data independent training error guarantees for multilayer neural networkscited by 30
  33. 2017Depth Creates No Bad Local Minimacited by 29
  34. 2018Small nonlinearities in activation functions create bad local minima in neural networkscited by 28
  35. 2018Understanding the Loss Surface of Neural Networks for Binary Classificationcited by 27
  36. 2019Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problemscited by 24
  37. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  38. 2018Spurious Valleys in Two-layer Neural Network Optimization Landscapescited by 21

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 5; 2024: 2; 2025: 1.

8 papers.

  1. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 40
  2. 2023NTK-SAP: Improving neural network pruning by aligning training dynamicscited by 30
  3. 2023Memory capacity of two layer neural networks with smooth activationscited by 5
  4. 2023Memorization With Neural Nets: Going Beyond the Worst Casecited by 2
  5. 2023Global L2 minimization at uniform exponential rate via geometrically adapted gradient descent in Deep Learningcited by 2
  6. 2024pTNAS: Progressive Neural Architecture Search for Tabular Datacited by 2
  7. 2024Representation and Regression Problems in Neural Networks: Relaxation, Generalization, and Numericscited by 2
  8. 2025Architecture independent generalization bounds for overparametrized deep ReLU networkscited by 0