# Empirical Bounds on Linear Regions of Deep Rectifier Networks

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

## Key facts

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

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

- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes](https://mlsanity.com/paper/2501.00200/) (2024)
- [Scaling Up Exact Neural Network Compression by ReLU Stability](https://mlsanity.com/paper/2102.07804/) (2021)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [TransNet: Transferable Neural Networks for Partial Differential Equations](https://mlsanity.com/paper/2301.11701/) (2023)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Modeling Design and Control Problems Involving Neural Network Surrogates](https://mlsanity.com/paper/2111.10489/) (2021)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [Any Deep ReLU Network is Shallow](https://mlsanity.com/paper/2306.11827/) (2023)
- [Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks](https://mlsanity.com/paper/2312.16699/) (2023)
- [Feed-Forward Neural Networks as a Mixed-Integer Program](https://mlsanity.com/paper/2402.06697/) (2024)
- [Training Thinner and Deeper Neural Networks: Jumpstart Regularization](https://mlsanity.com/paper/2201.12795/) (2022)
- [Relating Piecewise Linear Kolmogorov Arnold Networks to ReLU Networks](https://mlsanity.com/paper/2503.01702/) (2025)
- [A Computational Tropical Geometry Framework for Neural Networks](https://mlsanity.com/paper/2405.20174/) (2024)
- [Instance-wise Linearization of Neural Network for Model Interpretation](https://mlsanity.com/paper/2310.16295/) (2023)
- [Improving the Expressive Power of Deep Neural Networks through Integral Activation Transform](https://mlsanity.com/paper/2312.12578/) (2023)
- [Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regions](https://mlsanity.com/paper/2403.00860/) (2024)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [ReLU Networks as Random Functions: Their Distribution in Probability Space](https://mlsanity.com/paper/2503.22082/) (2025)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)

## Abstract (arXiv)

We can compare the expressiveness of neural networks that use rectified linear units (ReLUs) by the number of linear regions, which reflect the number of pieces of the piecewise linear functions modeled by such networks. However, enumerating these regions is prohibitive and the known analytical bounds are identical for networks with same dimensions. In this work, we approximate the number of linear regions through empirical bounds based on features of the trained network and probabilistic inference. Our first contribution is a method to sample the activation patterns defined by ReLUs using universal hash functions. This method is based on a Mixed-Integer Linear Programming (MILP) formulation of the network and an algorithm for probabilistic lower bounds of MILP solution sets that we call MIPBound, which is considerably faster than exact counting and reaches values in similar orders of magnitude. Our second contribution is a tighter activation-based bound for the maximum number of linear regions, which is particularly stronger in networks with narrow layers. Combined, these bounds yield a fast proxy for the number of linear regions of a deep neural network.