In classical approximation theory, we typically build complex functions by adding simple pieces together. Whether using Fourier series, splines, or polynomials, the logic is additive: if you want more detail or more "wiggles" in your approximation, you must add more basis functions. Each new parameter provides a roughly linear increase in the complexity of the resulting function.
Deep neural networks, however, operate on a fundamentally different principle: function composition. By passing the output of one layer as the input to the next, deep architectures can generate complexity that grows exponentially with the number of parameters, rather than linearly.
The Geometry of Composition
To understand why composition is so powerful, consider a simple Rectified Linear Unit (ReLU) network. A single ReLU layer creates a piecewise linear function. In a shallow network, adding more neurons simply adds more "breakpoints" where the slope of the function changes. To create a function with $N$ oscillations, a shallow network requires $O(N)$ neurons.
As Ronald A. DeVore, Guergana Petrova, and their colleagues demonstrate in Nonlinear Approximation and (Deep) ReLU Networks, depth changes this calculus. When you compose functions, you are essentially "folding" the input space. A function that folds a line in half, when composed with itself $L$ times, creates $2^L$ folds.
This mechanism allows deep networks to represent highly oscillatory patterns—what Guy Bresler and Dheeraj Nagaraj describe as "triangle waves"—using significantly fewer neurons than shallow architectures. In Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth, they prove that this exponential growth in oscillatory complexity is a "sharp" advantage: deep networks can represent functions that are impossible for shallow networks to capture efficiently.
Composition vs. Rational Complexity
The efficiency of composition isn't just an observation about ReLUs; it's a fundamental property of how hierarchical structures organize information. Matus Telgarsky explored this by comparing neural networks to rational functions (ratios of polynomials).
In Neural Networks and Rational Functions, Telgarsky shows that a deep network with a linear number of layers can represent functions that would require a rational function of exponentially high degree to approximate. This suggests that the "mental model" for a neural network should not be a high-degree polynomial, but rather a composition of low-degree parts. The depth of the network acts as a multiplier for the degree of the underlying mathematical representation.
Universal Transformations through Simple Layers
This compositional power extends beyond simple function approximation to the transformation of entire spaces. In the realm of Invertible Neural Networks (INNs), researchers like Isao Ishikawa and Takeshi Teshima have shown that even highly restricted layers can become powerful when stacked.
In Coupling-based Invertible Neural Networks Are Universal Diffeomorphism Approximators, the authors prove that affine coupling layers—which are individually quite limited in the transformations they can perform—can approximate any smooth invertible map (diffeomorphism) if the network is deep enough. The global complexity of the transformation emerges not from the sophistication of a single layer, but from the repeated application of simple, structured compositions.
Bypassing the Curse of Dimensionality
Perhaps the most significant impact of compositional efficiency is in high-dimensional spaces. Traditional methods for solving partial differential equations (PDEs) often fail as the number of dimensions increases because the number of required basis functions grows exponentially with the dimension.
E Weinan and Stephan Wojtowytsch argue in Some observations on partial differential equations in Barron and multi-layer spaces that neural networks bypass this "curse of dimensionality" by tracking complexity through tree-like compositional spaces. If a solution to a PDE can be represented as a composition of simpler functions, a deep network can find it efficiently, even in hundreds of dimensions, because the network's architecture mirrors the hierarchical structure of the problem itself.
The Stability Trade-off
While composition provides immense representational power, it is not a free lunch. Ronald A. DeVore and Guergana Petrova note in their survey Neural network approximation that the "super-convergence" rates achieved by deep networks come with a trade-off: numerical instability. The same sensitivity that allows a small change in early layers to create massive changes in the output (the "folding" effect) makes finding the absolute optimal parameters a difficult and often unstable optimization problem.
In summary, the "magic" of deep learning lies in its departure from additive approximation. By leveraging composition, deep networks transform a linear increase in depth into an exponential increase in expressive capacity, allowing them to capture the intricate, multi-scale patterns of the real world.