# Complexity of One-Dimensional ReLU DNNs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 18 references that are in the map.
- First posted on arXiv 8 Dec 2025.

## Builds on (most cited first, 11 of 11)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [RadiX-Net: Structured Sparse Matrices for Deep Neural Networks](https://mlsanity.com/paper/1905.00416/) (2019)
- [Testing RadiX-Nets: Advances in Viable Sparse Topologies](https://mlsanity.com/paper/2311.03609/) (2023)

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

- [Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulas](https://mlsanity.com/paper/2609.32695/) (2026)

## Abstract (arXiv)

We study the expressivity of one-dimensional (1D) ReLU deep neural networks through the lens of their linear regions. For randomly initialized, fully connected 1D ReLU networks (He scaling with nonzero bias) in the infinite-width limit, we prove that the expected number of linear regions grows as sumi = 1L ni + mathopoleft(sumi = 1Lniright) + 1, where nℓ denotes the number of neurons in the ℓ-th hidden layer. We also propose a function-adaptive notion of sparsity that compares the expected regions used by the network to the minimal number needed to approximate a target within a fixed tolerance.