# On the Number of Linear Functions Composing Deep Neural Network: Towards a Refined Definition of Neural Networks Complexity

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

## Key facts

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

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [One step closer to unbiased aleatoric uncertainty estimation](https://mlsanity.com/paper/2312.10469/) (2023)
- [Explanations Go Linear: Post-hoc Explainability for Tabular Data with Interpretable Meta-Encoding](https://mlsanity.com/paper/2504.20667/) (2025)
- [Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulas](https://mlsanity.com/paper/2609.32695/) (2026)

## Abstract (arXiv)

The classical approach to measure the expressive power of deep neural networks with piecewise linear activations is based on counting their maximum number of linear regions. This complexity measure is quite relevant to understand general properties of the expressivity of neural networks such as the benefit of depth over width. Nevertheless, it appears limited when it comes to comparing the expressivity of different network architectures. This lack becomes particularly prominent when considering permutation-invariant networks, due to the symmetrical redundancy among the linear regions. To tackle this, we propose a refined definition of piecewise linear function complexity: instead of counting the number of linear regions directly, we first introduce an equivalence relation among the linear functions composing a piecewise linear function and then count those linear functions relative to that equivalence relation. Our new complexity measure can clearly distinguish between the two aforementioned models, is consistent with the classical measure, and increases exponentially with depth.