A fundamental tenet of deep learning is that deep networks are more expressive than shallow ones. While the Universal Approximation Theorem guarantees that a network with a single hidden layer can approximate any continuous function to arbitrary precision, it says nothing about efficiency. In practice, achieving that approximation with a shallow network might require an impossibly large number of neurons.
To understand why depth is so uniquely powerful, researchers study the exact representational limits of Rectified Linear Unit (ReLU) networks. By analyzing simple, fundamental functions—such as computing the maximum of several numbers—through the lenses of polyhedral geometry, combinatorics, and dynamical systems, recent work has established hard lower bounds on network depth. These results reveal that depth is not just a optimization convenience, but a strict geometric requirement.
The Geometry of ReLU Composition
To understand why depth provides an advantage over width, we must look at how ReLU layers transform space. A single ReLU neuron splits the input space with a flat hyperplane, activating on one side and remaining flat on the other. A single layer of these neurons partitions the input space into a collection of convex polyhedral regions, inside each of which the network's output is purely linear.
When we stack layers, we compose these piecewise linear functions. Instead of merely adding more hyperplanes, composition allows the network to repeatedly "fold" the input space. As shown by Raman Arora et al. in "Understanding Deep Neural Networks with Rectified Linear Units", this process can be analyzed using the geometry of zonotopes. The authors demonstrated that deep networks achieve a super-exponential reduction in the number of neurons required to represent certain functions compared to shallow architectures. Each additional layer takes the polyhedral subdivisions of the previous layer and slices them again, compounding the geometric complexity at a rate that width alone cannot match.
The Logarithmic Barrier of the Maximum Function
To prove exactly how much depth is required for specific tasks, researchers frequently use a deceptively simple benchmark: the maximum function, $F(x_1, \dots, x_d) = \max\{x_1, \dots, x_d\}$.
Intuitively, computing the maximum of $d$ variables requires a hierarchical selection process. Think of it like a tournament bracket: you compare pairs of numbers, pass the winners to the next round, and repeat. This hierarchical structure naturally implies a tree-like depth that scales logarithmically with the number of inputs ($\log_2 d$).
In "Benefits of Max Pooling in Neural Networks: Theoretical and Experimental Evidence", Kyle Matoba et al. formalized this intuition. They showed that replicating or approximating a maximum operation (such as max pooling) requires a minimum depth proportional to $\log_2 d$. If a network is shallower than this limit, it incurs a persistent approximation error that cannot be resolved by making the layers wider.
Representing this function exactly without error introduces even stricter constraints. Christoph Hertrich et al. explored these boundaries in "Towards Lower Bounds on the Depth of ReLU Neural Networks", proving that certain multi-variable max functions cannot be represented by architectures with only two hidden layers, unless the network relies on highly unstable internal non-differentiable points that perfectly cancel each other out.
Discrete Geometry and Weight Constraints
The mathematical arguments become even more rigid—and the lower bounds more absolute—when we consider the constraints of real-world hardware. Computers do not operate with infinite-precision real numbers; they use discrete formats like integers or rational fractions.
When a ReLU network is restricted to integer weights, its representational space transitions from continuous polyhedra to discrete lattice polytopes. In "Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes", Christian Alexander Haase et al. revealed that the expressive capacity of an integer-weighted network is fundamentally limited by how many times it can alternate between two geometric operations: Minkowski sums and convex hull operations.
Continuous Input Space ──> [Layer 1: Minkowski/Convex Hull] ──> Lattice Polytope (Even Volume Parity)
│
(Next Layer)
▼
Lattice Polytope (Odd Volume Parity)
The authors introduced a combinatorial invariant to track this complexity: the parity of the normalized volumes of the polytope's faces. Each layer acts as a geometric transformer that can alter this parity. Because shallow networks are restricted to producing polytopes with even normalized volumes for certain dimensions, they are structurally blocked from representing functions whose geometry demands odd normalized volumes. Using this tool, the authors proved a hard lower bound: computing the maximum of $n$ inputs with integer weights requires at least $\lceil \log_2 n \rceil$ hidden layers, regardless of whether the layers are infinitely wide.
Moving from integers to rational weights (decimals and binary fractions) makes proving lower bounds significantly harder because fractions allow for highly flexible geometric scaling. However, in "On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth", Gennadiy Averkov et al. successfully extended these principles. By analyzing the geometric expansion of polytopes across successive layers, they confirmed that even with rational weights, a network's depth must grow logarithmically with the number of inputs to exactly represent the maximum function.
Architectural Bottlenecks and Hyperplane Arrangements
The specific structural rules imposed on a network's architecture can also create geometric bottlenecks that force a requirement for depth.
One example is when a network's internal decision boundaries are restricted to specific geometric patterns. In "Depth-Bounds for Neural Networks via the Braid Arrangement", Moritz Leo Grillo et al. studied "braid-conforming" ReLU networks, where internal breakpoints are restricted to specific hyperplane arrangements. Under this geometric constraint, they proved that the depth required to compute the maximum of $d$ inputs scales at a doubly-logarithmic rate ($\Omega(\log \log d)$), demonstrating that even simple functions have non-trivial depth requirements when their internal geometry is restricted.
An even more dramatic bottleneck appears when we enforce structural constraints like monotonicity or convexity. Input Convex Neural Networks (ICNNs) are designed so that the output is a convex function of the inputs, which is useful for optimization guarantees. However, Egor Bakaev et al. showed in "On the Depth of Monotone ReLU Neural Networks and ICNNs" that this constraint comes with a massive expressivity tax.
The authors linked the depth required by a constrained network to the geometric complexity of the target function's Newton Polytope. Functions with complex boundary-to-volume ratios act as structural bottlenecks. For an ICNN to represent the simple maximum function, its depth must scale linearly with the number of inputs, rather than logarithmically. This exposes a massive expressivity gap where a shallow, unconstrained network can easily outperform a much deeper, constrained one.
The Dynamical Systems View: Chaos and Iteration
A final, intuitive way to understand the necessity of depth is to view neural network composition as a discrete dynamical system. Instead of looking at static polyhedral shapes, we can look at what happens when a function is repeatedly iterated.
In "Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem", Clayton Hendrick Sanford et al. analyzed network expressivity through the lens of "chaotic itineraries." When you stack layers, you are effectively iterating a piecewise linear map. This iteration can quickly generate chaotic behavior, creating functions that oscillate rapidly and possess complex periodic trajectories.
The authors proved that shallow networks face a fundamental representation limit here: they cannot efficiently capture these chaotic itineraries. No matter how wide you make a single hidden layer, its approximation error for these deeply iterated functions cannot be driven below a constant threshold. The rapid, cascading oscillations generated naturally by depth are structurally unachievable by a single flat layer, proving that depth is fundamentally irreplaceable when representing complex, highly recurrent data patterns.
Key Foundational Work
Towards Lower Bounds on the Depth of ReLU Neural Networks (2021) — contributed 1 concept elements to this direction.
Understanding Deep Neural Networks with Rectified Linear Units (2018) — contributed 1 concept elements to this direction.