# When Expressivity Meets Trainability: Fewer than n Neurons Can Work

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

## 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 (most cited first, 30 of 61)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights](https://mlsanity.com/paper/1702.03044/) (2017)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Topology and Geometry of Half-Rectified Network Optimization](https://mlsanity.com/paper/1611.01540/) (2016)
- [Why does deep and cheap learning work so well?](https://mlsanity.com/paper/1608.08225/) (2016)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)

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

- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [NTK-SAP: Improving neural network pruning by aligning training dynamics](https://mlsanity.com/paper/2304.02840/) (2023)
- [Memory capacity of two layer neural networks with smooth activations](https://mlsanity.com/paper/2308.02001/) (2023)
- [Memorization With Neural Nets: Going Beyond the Worst Case](https://mlsanity.com/paper/2310.00327/) (2023)
- [Global L2 minimization at uniform exponential rate via geometrically adapted gradient descent in Deep Learning](https://mlsanity.com/paper/2311.15487/) (2023)
- [pTNAS: Progressive Neural Architecture Search for Tabular Data](https://mlsanity.com/paper/2403.10318/) (2024)
- [Representation and Regression Problems in Neural Networks: Relaxation, Generalization, and Numerics](https://mlsanity.com/paper/2412.01619/) (2024)
- [Architecture independent generalization bounds for overparametrized deep ReLU networks](https://mlsanity.com/paper/2504.05695/) (2025)

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