# Depth Separation in Norm-Bounded Infinite-Width Neural Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 49 references that are in the map.
- First posted on arXiv 13 Feb 2024.

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

- [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)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Geometry of Optimization and Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1705.03071/) (2017)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [The power of deeper networks for expressing natural functions](https://mlsanity.com/paper/1705.05502/) (2017)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Penalising the biases in norm regularisation enforces sparsity](https://mlsanity.com/paper/2303.01353/) (2023)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)

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

- [Spectral complexity of deep neural networks](https://mlsanity.com/paper/2405.09541/) (2024)
- [When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective](https://mlsanity.com/paper/2503.11272/) (2025)
- [Consideration Circuits: Depth Separation and Universality Beyond a Single Softmax](https://mlsanity.com/paper/2610.04143/) (2026)

## Abstract (arXiv)

We study depth separation in infinite-width neural networks, where complexity is controlled by the overall squared ℓ2-norm of the weights (sum of squares of all weights in the network). Whereas previous depth separation results focused on separation in terms of width, such results do not give insight into whether depth determines if it is possible to learn a network that generalizes well even when the network width is unbounded. Here, we study separation in terms of the sample complexity required for learnability. Specifically, we show that there are functions that are learnable with sample complexity polynomial in the input dimension by norm-controlled depth-3 ReLU networks, yet are not learnable with sub-exponential sample complexity by norm-controlled depth-2 ReLU networks (with any value for the norm). We also show that a similar statement in the reverse direction is not possible: any function learnable with polynomial sample complexity by a norm-controlled depth-2 ReLU network with infinite width is also learnable with polynomial sample complexity by a norm-controlled depth-3 ReLU network.