# On the Local Complexity of Linear Regions in Deep ReLU Networks

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 66 references that are in the map.
- First posted on arXiv 24 Dec 2024.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [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)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [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)
- [How to Start Training: The Effect of Initialization and Architecture](https://mlsanity.com/paper/1803.01719/) (2018)
- [Trainability and Accuracy of Neural Networks: An Interacting Particle System Approach](https://mlsanity.com/paper/1805.00915/) (2018)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Gradient Descent Quantizes ReLU Network Features](https://mlsanity.com/paper/1803.08367/) (2018)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [Gradient Dynamics of Shallow Univariate ReLU Networks](https://mlsanity.com/paper/1906.07842/) (2019)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (2022)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [Your diffusion model secretly knows the dimension of the data manifold](https://mlsanity.com/paper/2212.12611/) (2022)

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

- [Time to Spike? Understanding the Representational Power of Spiking Neural Networks in Discrete Time](https://mlsanity.com/paper/2505.18023/) (2025)
- [Constraining the outputs of ReLU neural networks](https://mlsanity.com/paper/2508.03867/) (2025)
- [AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks](https://mlsanity.com/paper/2605.06218/) (2026)
- [Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks](https://mlsanity.com/paper/2605.06300/) (2026)
- [Generalization in Nonlinear Least Squares via Learned Feature Geometry](https://mlsanity.com/paper/2606.08799/) (2026)
- [ReLU Networks as Random Functions: Their Distribution in Probability Space](https://mlsanity.com/paper/2503.22082/) (2025)
- [Geometric Decoupling: Diagnosing the Structural Instability of Latent](https://mlsanity.com/paper/2604.18804/) (2026)
- [Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity](https://mlsanity.com/paper/2606.21687/) (2026)
- [Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulas](https://mlsanity.com/paper/2609.32695/) (2026)

## Abstract (arXiv)

We define the local complexity of a neural network with continuous piecewise linear activations as a measure of the density of linear regions over an input data distribution. We show theoretically that ReLU networks that learn low-dimensional feature representations have a lower local complexity. This allows us to connect recent empirical observations on feature learning at the level of the weight matrices with concrete properties of the learned functions. In particular, we show that the local complexity serves as an upper bound on the total variation of the function over the input data distribution and thus that feature learning can be related to adversarial robustness. Lastly, we consider how optimization drives ReLU networks towards solutions with lower local complexity. Overall, this work contributes a theoretical framework towards relating geometric properties of ReLU networks to different aspects of learning such as feature learning and representation cost.