# Neural Networks with Small Weights and Depth-Separation Barriers

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2020.

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

- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [On the Complexity of Neural Computation in Superposition](https://mlsanity.com/paper/2409.15318/) (2024)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [The Role of Linear Layers in Nonlinear Interpolating Networks](https://mlsanity.com/paper/2202.00856/) (2022)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)
- [Depth Separation in Norm-Bounded Infinite-Width Neural Networks](https://mlsanity.com/paper/2402.08808/) (2024)
- [On Algebraic Constructions of Neural Networks with Small Weights](https://mlsanity.com/paper/2205.08032/) (2022)
- [Harvesting AI Computation at the Edge via Generic Approximation](https://mlsanity.com/paper/2606.29518/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## Abstract (arXiv)

In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths 2 and 3, and achieving results for higher depths has been an important open question. In this paper, we focus on feedforward ReLU networks, and prove fundamental barriers to proving such results beyond depth 4, by reduction to open problems and natural-proof barriers in circuit complexity. To show this, we study a seemingly unrelated problem of independent interest: Namely, whether there are polynomially-bounded functions which require super-polynomial weights in order to approximate with constant-depth neural networks. We provide a negative and constructive answer to that question, by showing that if a function can be approximated by a polynomially-sized, constant depth k network with arbitrarily large weights, it can also be approximated by a polynomially-sized, depth 3k+3 network, whose weights are polynomially bounded.