depth separation and expressivity

Depth separation asks a sharp question: are there functions a deep network can represent compactly that any shallow network would need an absurd width to match? The answer is yes, and it gives depth a provable advantage. Some functions are cheap to build by composition but astronomically expensive to build in a single wide layer, so stacking is not just convenient but fundamentally more economical.

The classic construction is Telgarsky's. Composing a simple triangle (sawtooth) map with itself k times produces a function with two-to-the-k oscillations, which a depth-k network represents with a handful of units, while any network of depth two needs width exponential in k to approximate it. Such results are existence proofs: they exhibit specific functions where depth buys an exponential reduction in size, sharpening the universal approximation theorem, which guarantees that shallow networks can approximate any function but says nothing about how large they must be.

The crucial caveat is that expressivity is not learnability. Knowing a deep network can represent a function efficiently does not mean gradient descent will find that representation from data. Depth-separation theorems describe what is possible to represent, not what is reachable by training, and the gap between the two is large.