mlsanityData to 7 Oct 2026

Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions

arXiv 2210.07236 ↗First posted 13 Oct 2022cs.LG cs.CC cs.NEcited by 26

Not on the map. Why?

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.

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

Builds on

22 of 55 references.

References · 22

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2015U-Net: Convolutional Networks for Biomedical Image Segmentationcited by 19,604
  4. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,267
  5. 2016Densely Connected Convolutional Networkscited by 6,691
  6. 2021Convex optimizationcited by 2,479
  7. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  8. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  9. 2016On the Expressive Power of Deep Neural Networkscited by 302
  10. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  11. 2016Benefits of depth in neural networkscited by 248
  12. 2013Maxout Networkscited by 186
10 more
  1. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  2. 2019Complexity of Linear Regions in Deep Networkscited by 166
  3. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  4. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  5. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  6. 2019Reverse-Engineering Deep ReLU Networkscited by 81
  7. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
  8. 2018A Framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networkscited by 15
  9. 2021Size and Depth Separation in Approximating Benign Functions with Neural Networkscited by 7
  10. 2021ResNEsts and DenseNEsts: Block-based DNN Models with Improved Representation Guaranteescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 6; 2025: 7; 2026: 8.

26 papers.

Sort:

  1. 2022Impossibility Theorems for Feature Attributioncited by 78
  2. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  3. 2023Deep Network Approximation: Beyond ReLU to Diverse Activation Functionscited by 33
  4. 2023Don't trust your eyes: on the (un)reliability of feature visualizationscited by 32
  5. 2024Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theorycited by 12
  6. 2024On Minimal Depth in Neural Networkscited by 11
  7. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 11
  8. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  9. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  10. 2023Any Deep ReLU Network is Shallowcited by 6
  11. 2024Representing Piecewise-Linear Functions by Functions with Minimal Aritycited by 2
  12. 2024Subspace Representation Learning for Sparse Linear Arrays to Localize More Sources than Sensors: A Deep Learning Methodologycited by 2
14 more
  1. 2026On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functionscited by 1
  2. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  3. 2026AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networkscited by 1
  4. 2026Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networkscited by 1
  5. 2024Two-hidden-layer ReLU neural networks and finite elementscited by 0
  6. 2025A Comparative Study of Invariance-Aware Loss Functions for Deep Learning-based Gridless Direction-of-Arrival Estimationcited by 0
  7. 2025Super-fast Rates of Convergence for Neural Network Classifiers under the Hard Margin Conditioncited by 0
  8. 2025Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensionscited by 0
  9. 2025Cellular Learning: Scattered Data Regression in High Dimensions via Voronoi Cellscited by 0
  10. 2025On the expressivity of sparse maxout networkscited by 0
  11. 2026Sparse Bayesian Learning Algorithms Revisited: From Learning Majorizers to Structured Algorithmic Learning using Neural Networkscited by 0
  12. 2026Regional Explanations: Bridging Local and Global Variable Importancecited by 0
  13. 2026A Rigorous, Tractable Measure of Model Complexitycited by 0
  14. 2026Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexitycited by 0