Why Depth Helps
Depth separations and compositional functions.
A ReLU network of width 2 and depth 20 computes a sawtooth with over a million linear pieces. A network with one hidden layer needs more than a hundred thousand units just to stay within a constant error of it. For some functions depth buys exponential expressive power. This lesson counts linear regions, proves a Telgarsky-style separation, states Eldan and Shamir's high-dimensional one, builds exponentially accurate approximations of from sawtooths, and then asks what these theorems do not say about trained networks.
What you’ll learn
- Bound the number of linear pieces of a ReLU network, and state Zaslavsky's count for one hidden layer and the Montúfar et al. lower bound for deep networks.
- Prove that sawtooths computed by deep width-2 networks cannot be approximated by shallow networks of sub-exponential size.
- State Eldan and Shamir's separation between two and three layers in high dimension, and explain its Fourier intuition.
- Derive Yarotsky's approximation of with error at depth , and explain the depth advantage for compositional functions.
Counting linear pieces
A ReLU network computes a continuous piecewise-affine function. One measure of its complexity is the number of linear regions, the maximal connected sets on which it is affine. In one input dimension the regions are intervals, and they can be counted layer by layer.
Let be a partition of into intervals on which every unit of layer is affine (). On each interval, a unit of layer applies ReLU to an affine function, which crosses zero at most once, adding at most one breakpoint:
The output is affine in the last layer, so it is affine on every interval of . For a budget of units, the AM–GM inequality bounds the product:
With one hidden layer, units give at most pieces. Spread over layers, the same units allow exponentially many in , and compositions of zigzag maps come close to the bound.
In input dimensions, one hidden layer of ReLUs cuts by hyperplanes into at most regions (Zaslavsky's count for arrangements in general position): polynomial in for fixed . Deep networks fold the input space repeatedly. Montúfar, Pascanu, Cho and Bengio (2014) constructed networks with inputs and hidden layers of width that have at least regions. For two inputs and three layers of 8 ReLUs that is regions, against at most 301 for one layer of the same 24 units.
One hidden layer of 24 ReLUs acts on two-dimensional inputs. At most how many linear regions can the network have?
- 25
- 301
- 9,472
Show the answer
B. 301
24 lines in general position cut the plane into regions. The count is polynomial in the width, while depth can multiply regions layer by layer.
Telgarsky’s separation
The tent map is one hidden layer of width 2:
maps each half of onto all of , so composing with it splits every piece of the inner function in two. compositions, a network of depth and width 2, give a sawtooth that alternates between 0 and 1 on a grid of spacing :
Cut where . Apart from two half-length pieces at the ends, this leaves intervals of length ; on each, has one sign, alternating between neighbors, and is a triangle of height :
On each affine piece of the set is an interval, so switches at most times. Discard the at most intervals containing a switch. The rest fall into at most runs of consecutive intervals on which the indicator is constant while the sign of alternates, so in a run of intervals at least have on the wrong side of :
Where is on the wrong side, , so each wrong-side interval contributes at least its triangle:
A network with hidden layers of width at most has at most pieces. Staying within error of therefore requires
A width-2, depth-20 ReLU network computes . By the bound above, how many units must a network with one hidden layer have to stay within error of it?
- About 40, the same as the deep network
- About 400
- More than 100,000
- More than
Show the answer
C. More than 100,000
One hidden layer of units has at most pieces, and the bound needs , so . The deep network uses 40 ReLUs, two per layer.
Telgarsky (2016) proved the general version: for every , some functions computed by networks with layers and nodes per layer cannot be approximated by networks with layers unless those have nodes. The result covers "semi-algebraic" gates, including ReLU, maximum and piecewise polynomials, and also boosted decision trees.
High dimension and compositional functions
The intuition is spectral. A one-hidden-layer network is a sum of ridge functions , and the Fourier transform of a ridge function lives on the line through the origin in direction . So the spectrum of a width- network sits on lines. Eldan and Shamir choose so that multiplying by its density smears each line into a thin tube, and a radial target whose spectral mass spreads over a high-frequency spherical shell; tubes cover an exponentially small fraction of that shell unless is exponential in . Two hidden layers escape: the first approximates as a sum of univariate functions, the second applies a univariate function of the result.
With , the sawtooth of tent maps, the following function is the piecewise-linear interpolant of at the points (each subtracted sawtooth bends the previous interpolant at the new midpoints):
Linear interpolation of a function with second derivative 2 on a grid of spacing errs by at most :
The sawtooths are produced one after another by a ReLU network of constant width and depth , so accuracy costs units. One hidden layer needs , since pieces cannot fit better than about . Products come from squares, then polynomials and Taylor expansions: Yarotsky approximates the unit ball of the Sobolev space to accuracy with depth and weights.
Depth also helps when the target itself is a composition. If of variables is a binary tree of functions of two variables, each with derivatives, a deep network mirroring the tree approximates it to accuracy with units, while generic shallow networks need (Mhaskar & Poggio, 2016; Poggio et al., 2017). Depth that matches the target's structure removes the curse of dimensionality. That natural signals are hierarchical in this sense is a hypothesis, not a theorem, and it is what connects the result to practice.
What the separations do not show
Four caveats keep the theorems in proportion. Worst-case targets: separations use functions built for the purpose, sawtooths and radial oscillations; whether real targets need depth in the same way is an empirical question. Typical behavior: trained networks realize far less than their maximal region counts. Learnability: a function a deep network can represent may still be hard to learn; parities of many bits are representable by small networks, yet gradient-based training fails on them (Shalev-Shwartz, Shamir & Shammah, 2017). Optimization: very deep networks became trainable only through normalization, residual connections and careful initialization, so depth's practical benefits mix expressivity, optimization and inductive bias.
Key takeaways
- ReLU networks are piecewise affine. In one dimension, widths allow at most pieces; one hidden layer of units cuts into at most regions, while deep networks can have exponentially many in depth (Montúfar et al.).
- The tent map composed times gives pieces at width 2; any approximant within error needs at least pieces, so one hidden layer needs exponentially many units (Telgarsky).
- Eldan and Shamir: an approximately radial function needs exponential width with one hidden layer but polynomial width with two, because ridge functions' spectra lie on lines.
- Subtracting scaled sawtooths interpolates with error at depth , giving -size approximations of products and smooth functions; compositional targets escape the curse of dimensionality with matching depth.
- Separations are worst-case existence results: typical networks realize far fewer regions, representable functions can be hard to learn, and proofs beyond depth 4 face circuit-complexity barriers.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A ReLU network on has three hidden layers of width 4. At most how many affine pieces can its output have?
- 13
- 64
- 125
- 4,096
Show the answer
C. 125
. With the same 12 units in one layer the bound would be 13.
Why does composing a function with the tent map double its number of affine pieces on ?
- has two ReLU units, and each adds one piece
- Composition always doubles the number of pieces
- is affine on each half of and maps each half onto all of , so every piece of the inner sawtooth is split in two
- The tent map doubles the input's frequency in the Fourier domain
Show the answer
C. is affine on each half of and maps each half onto all of , so every piece of the inner sawtooth is split in two
Applying after : each piece of runs from 0 to 1 or back, and crosses once, where folds it. So each piece becomes two.
Yarotsky's approximates on with error . What is the smallest that guarantees error at most ?
- 3
- 9
- 20
- 1,000
Show the answer
B. 9
gives , while gives . Depth grows like , whereas one hidden layer would need hundreds of pieces.
Which statement do depth-separation theorems justify?
- Deeper networks always generalize better than shallow ones
- Every function is computed more efficiently by a deep network
- Trained deep networks realize exponentially many linear regions
- Some functions computed by small deep networks cannot be approximated by shallow networks without exponentially many units
Show the answer
D. Some functions computed by small deep networks cannot be approximated by shallow networks without exponentially many units
Separations are existence statements about specific functions (sawtooths, radial oscillations). They say nothing about generalization, about all functions, or about what training produces.
Further reading
- M. Telgarsky, "Benefits of depth in neural networks," Conference on Learning Theory (COLT) (2016).
- R. Eldan & O. Shamir, "The power of depth for feedforward neural networks," Conference on Learning Theory (COLT) (2016).
- G. Montúfar, R. Pascanu, K. Cho & Y. Bengio, "On the number of linear regions of deep neural networks," NeurIPS (2014).
- D. Yarotsky, "Error bounds for approximations with deep ReLU networks," Neural Networks 94, 103–114 (2017).
- T. Poggio, H. Mhaskar, L. Rosasco, B. Miranda & Q. Liao, "Why and when can deep—but not shallow—networks avoid the curse of dimensionality: A review," International Journal of Automation and Computing 14, 503–519 (2017).