# Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 13 Oct 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [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)
- [Maxout Networks](https://mlsanity.com/paper/1302.4389/) (2013)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [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)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Reverse-Engineering Deep ReLU Networks](https://mlsanity.com/paper/1910.00744/) (2019)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networks](https://mlsanity.com/paper/1806.01918/) (2018)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [ResNEsts and DenseNEsts: Block-based DNN Models with Improved Representation Guarantees](https://mlsanity.com/paper/2111.05496/) (2021)

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

- [Impossibility Theorems for Feature Attribution](https://mlsanity.com/paper/2212.11870/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Deep Network Approximation: Beyond ReLU to Diverse Activation Functions](https://mlsanity.com/paper/2307.06555/) (2023)
- [Don't trust your eyes: on the (un)reliability of feature visualizations](https://mlsanity.com/paper/2306.04719/) (2023)
- [Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory](https://mlsanity.com/paper/2405.05369/) (2024)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Any Deep ReLU Network is Shallow](https://mlsanity.com/paper/2306.11827/) (2023)
- [Representing Piecewise-Linear Functions by Functions with Minimal Arity](https://mlsanity.com/paper/2406.02421/) (2024)
- [Subspace Representation Learning for Sparse Linear Arrays to Localize More Sources than Sensors: A Deep Learning Methodology](https://mlsanity.com/paper/2408.16605/) (2024)
- [On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions](https://mlsanity.com/paper/2603.03084/) (2026)
- [Regional Explanations: Bridging Local and Global Variable Importance](https://mlsanity.com/paper/2604.11223/) (2026)
- [Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networks](https://mlsanity.com/paper/2605.04946/) (2026)
- [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)
- [Two-hidden-layer ReLU neural networks and finite elements](https://mlsanity.com/paper/2403.05809/) (2024)
- [A Comparative Study of Invariance-Aware Loss Functions for Deep Learning-based Gridless Direction-of-Arrival Estimation](https://mlsanity.com/paper/2503.12386/) (2025)
- [Super-fast Rates of Convergence for Neural Network Classifiers under the Hard Margin Condition](https://mlsanity.com/paper/2505.08262/) (2025)
- [Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions](https://mlsanity.com/paper/2508.09395/) (2025)
- [Cellular Learning: Scattered Data Regression in High Dimensions via Voronoi Cells](https://mlsanity.com/paper/2510.03810/) (2025)
- [On the expressivity of sparse maxout networks](https://mlsanity.com/paper/2510.14068/) (2025)
- [Sparse Bayesian Learning Algorithms Revisited: From Learning Majorizers to Structured Algorithmic Learning using Neural Networks](https://mlsanity.com/paper/2604.02513/) (2026)
- [A Rigorous, Tractable Measure of Model Complexity](https://mlsanity.com/paper/2605.21167/) (2026)
- [Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity](https://mlsanity.com/paper/2606.21687/) (2026)

## Abstract (arXiv)

A deep neural network using rectified linear units represents a continuous piecewise linear (CPWL) function and vice versa. Recent results in the literature estimated that the number of neurons needed to exactly represent any CPWL function grows exponentially with the number of pieces or exponentially in terms of the factorial of the number of distinct linear components. Moreover, such growth is amplified linearly with the input dimension. These existing results seem to indicate that the cost of representing a CPWL function is expensive. In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find a network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required to exactly represent any CPWL function is at most a quadratic function of the number of pieces. In contrast to all previous results, this upper bound is invariant to the input dimension. Besides the number of pieces, we also study the number of distinct linear components in CPWL functions. When such a number is also given, we prove that the quadratic complexity turns into bilinear, which implies a lower neural complexity because the number of distinct linear components is always not greater than the minimum number of pieces in a CPWL function. When the number of pieces is unknown, we prove that, in terms of the number of distinct linear components, the neural complexities of any CPWL function are at most polynomial growth for low-dimensional inputs and factorial growth for the worst-case scenario, which are significantly better than existing results in the literature.