A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory
Not on the map. Why?
Abstract (arXiv)
We consider the problem of exact computation of the maximum function over d real inputs using ReLU neural networks. We prove a depth hierarchy, wherein width Omegabig(d^1+frac12k-2-1big) is necessary to represent the maximum for any depth 3≤ k≤ log2(log2(d)). This is the first unconditional super-linear lower bound for this fundamental operator at depths k≥3, and it holds even if the depth scales with d. Our proof technique is based on a combinatorial argument and associates the non-differentiable ridges of the maximum with cliques in a graph induced by the first hidden layer of the computing network, utilizing Tur'an's theorem from extremal graph theory to show that a sufficiently narrow network cannot capture the non-linearities of the maximum. This suggests that despite its simple nature, the maximum function possesses an inherent complexity that stems from the geometric structure of its non-differentiable hyperplanes, and provides a novel approach for proving lower bounds for deep neural networks.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 23 of its 32 references that are in the map. First posted on arXiv 4 Jan 2026.
Builds on
23 of 32 references.
References · 23
- 2016Error bounds for approximations with deep ReLU networkscited by 574
- 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
- 2016Benefits of depth in neural networkscited by 250
- 2015The Power of Depth for Feedforward Neural Networkscited by 183
- 2019Complexity of Linear Regions in Deep Networkscited by 167
- 2016Why Deep Neural Networks for Function Approximation?cited by 82
- 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
- 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
- 2017Depth Separation for Neural Networkscited by 46
- 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
- 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
- 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
11 more
- 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 21
- 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
- 2021Depth separation beyond radial functionscited by 18
- 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
- 2021Optimization-Based Separations for Neural Networkscited by 17
- 2023How Many Neurons Does it Take to Approximate the Maximum?cited by 12
- 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 12
- 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
- 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
- 2022The Theoretical Expressiveness of Maxpoolingcited by 4
- 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
Built on by
Citing papers per year: 2026: 3.
3 papers.