Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 x2x^2 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 x2x^2 with error 2−2m−22^{-2m-2} at depth O(m)\order{m}, 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.

DerivationProof
  1. ∣Pi∣ ≤ ∣Pi−1∣+mi ∣Pi−1∣=(mi+1) ∣Pi−1∣\abs{P_i}\ \le\ \abs{P_{i-1}}+m_i\,\abs{P_{i-1}}=(m_i+1)\,\abs{P_{i-1}}

    Let Pi−1P_{i-1} be a partition of R\R into intervals on which every unit of layer i−1i-1 is affine (P0={R}P_0=\{\R\}). On each interval, a unit of layer ii applies ReLU to an affine function, which crosses zero at most once, adding at most one breakpoint:

  2. #pieces ≤ ∏i=1ℓ(mi+1) ≤ (Nℓ+1)ℓ\#\text{pieces}\ \le\ \prod_{i=1}^\ell(m_i+1)\ \le\ \Big(\frac N\ell+1\Big)^{\ell}

    The output is affine in the last layer, so it is affine on every interval of PℓP_\ell. For a budget of N=∑imiN=\sum_im_i units, the AM–GM inequality bounds the product:

  3. ℓ=1: N+1versusℓ layers: up to (Nℓ+1)ℓ\ell=1:\ N+1\qquad\text{versus}\qquad\ell\text{ layers}:\ \text{up to }\Big(\frac N\ell+1\Big)^{\ell}

    With one hidden layer, NN units give at most N+1N+1 pieces. Spread over ℓ\ell layers, the same units allow exponentially many in ℓ\ell, and compositions of zigzag maps come close to the bound.

In dd input dimensions, one hidden layer of nn ReLUs cuts Rd\R^d by nn hyperplanes into at most ∑j=0d(nj)\sum_{j=0}^d\binom nj regions (Zaslavsky's count for arrangements in general position): polynomial in nn for fixed dd. Deep networks fold the input space repeatedly. Montúfar, Pascanu, Cho and Bengio (2014) constructed networks with dd inputs and LL hidden layers of width n≥dn\ge d that have at least (∏i=1L−1⌊n/d⌋d)∑j=0d(nj)\big(\prod_{i=1}^{L-1}\lfloor n/d\rfloor^d\big)\sum_{j=0}^d\binom nj regions. For two inputs and three layers of 8 ReLUs that is 162×37=9,47216^2\times37=9{,}472 regions, against at most 301 for one layer of the same 24 units.

Check your understanding

One hidden layer of 24 ReLUs acts on two-dimensional inputs. At most how many linear regions can the network have?

  1. 25
  2. 301
  3. 2242^{24}
  4. 9,472
Show the answer

B. 301

24 lines in general position cut the plane into (240)+(241)+(242)=1+24+276=301\binom{24}0+\binom{24}1+\binom{24}2=1+24+276=301 regions. The count is polynomial in the width, while depth can multiply regions layer by layer.

Telgarsky’s separation

DerivationThe sawtooth
  1. Δ(x)=2 ReLU(x)−4 ReLU(x−12)={2x0≤x≤122−2x12≤x≤1\Delta(x)=2\,\mathrm{ReLU}(x)-4\,\mathrm{ReLU}\big(x-\tfrac12\big)=\begin{cases}2x&0\le x\le\frac12\\2-2x&\frac12\le x\le1\end{cases}

    The tent map is one hidden layer of width 2:

  2. sL=Δ∘⋯∘Δ⏟L,sL(j/2L)=j mod 2,2L affine piecess_L=\underbrace{\Delta\circ\cdots\circ\Delta}_{L},\qquad s_L\big(j/2^L\big)=j\bmod2,\qquad2^L\ \text{affine pieces}

    Δ\Delta maps each half of [0,1][0,1] onto all of [0,1][0,1], so composing with it splits every piece of the inner function in two. LL compositions, a network of depth LL and width 2, give a sawtooth that alternates between 0 and 1 on a grid of spacing 2−L2^{-L}:

DerivationProof
  1. M=2L−1,∫I∣sL−12∣ dx=h4=2−L−2M=2^L-1,\qquad\int_I\big|s_L-\tfrac12\big|\,dx=\frac h4=2^{-L-2}

    Cut [0,1][0,1] where sL=12s_L=\tfrac12. Apart from two half-length pieces at the ends, this leaves M=2L−1M=2^L-1 intervals of length h=2−Lh=2^{-L}; on each, sL−12s_L-\tfrac12 has one sign, alternating between neighbors, and ∣sL−12∣\abs{s_L-\tfrac12} is a triangle of height 12\tfrac12:

  2. #{wrong-side intervals} ≥ (M−2N)−(2N+1)2=2L−1−2N−1\#\{\text{wrong-side intervals}\}\ \ge\ \frac{(M-2N)-(2N+1)}{2}=2^{L-1}-2N-1

    On each affine piece of gg the set {g≥12}\{g\ge\tfrac12\} is an interval, so 1[g≥12]\mathbf 1[g\ge\tfrac12] switches at most 2N2N times. Discard the at most 2N2N intervals containing a switch. The rest fall into at most 2N+12N+1 runs of consecutive intervals on which the indicator is constant while the sign of sL−12s_L-\tfrac12 alternates, so in a run of rr intervals at least ⌊r/2⌋\lfloor r/2\rfloor have gg on the wrong side of 12\tfrac12:

  3. ∫01∣sL−g∣ dx ≥ 2−L−2(2L−1−2N−1)=18−2N+12L+2\int_0^1\abs{s_L-g}\,dx\ \ge\ 2^{-L-2}\big(2^{L-1}-2N-1\big)=\frac18-\frac{2N+1}{2^{L+2}}

    Where gg is on the wrong side, ∣sL−g∣≥∣sL−12∣\abs{s_L-g}\ge\abs{s_L-\tfrac12}, so each wrong-side interval contributes at least its triangle:

  4. (m+1)ℓ ≥ 2L−3⟹m ≥ 2(L−3)/ℓ−1(ℓ=1: m≥2L−3−1)(m+1)^\ell\ \ge\ 2^{L-3}\quad\Longrightarrow\quad m\ \ge\ 2^{(L-3)/\ell}-1\qquad\big(\ell=1:\ m\ge2^{L-3}-1\big)

    A network with ℓ\ell hidden layers of width at most mm has at most (m+1)ℓ(m+1)^\ell pieces. Staying within L1L^1 error 116\tfrac1{16} of sLs_L therefore requires

Check your understanding

A width-2, depth-20 ReLU network computes s20s_{20}. By the bound above, how many units must a network with one hidden layer have to stay within L1L^1 error 116\tfrac1{16} of it?

  1. About 40, the same as the deep network
  2. About 400
  3. More than 100,000
  4. More than 101210^{12}
Show the answer

C. More than 100,000

One hidden layer of mm units has at most m+1m+1 pieces, and the bound needs m+1≥217m+1\ge2^{17}, so m≥131,071m\ge131{,}071. The deep network uses 40 ReLUs, two per layer.

Telgarsky (2016) proved the general version: for every kk, some functions computed by networks with Θ(k3)\Theta(k^3) layers and Θ(1)\Theta(1) nodes per layer cannot be approximated by networks with O(k)\order{k} layers unless those have Ω(2k)\Omega(2^k) 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 σ(wk⋅x+bk)\sigma(\mathbf w_k\cdot\mathbf x+b_k), and the Fourier transform of a ridge function lives on the line through the origin in direction wk\mathbf w_k. So the spectrum of a width-nn network sits on nn lines. Eldan and Shamir choose μ\mu 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; nn tubes cover an exponentially small fraction of that shell unless nn is exponential in dd. Two hidden layers escape: the first approximates ∥x∥2=∑ixi2\norm{\mathbf x}^2=\sum_ix_i^2 as a sum of univariate functions, the second applies a univariate function of the result.

DerivationSquaring with depth (Yarotsky, 2017)
  1. fm(x)=x−∑s=1mgs(x)22sf_m(x)=x-\sum_{s=1}^m\frac{g_s(x)}{2^{2s}}

    With gs=Δ∘sg_s=\Delta^{\circ s}, the sawtooth of ss tent maps, the following function is the piecewise-linear interpolant of x2x^2 at the 2m+12^m+1 points j/2mj/2^m (each subtracted sawtooth bends the previous interpolant at the new midpoints):

  2. max⁡x∈[0,1]∣x2−fm(x)∣=(2−m)24=2−2m−2\max_{x\in[0,1]}\big|x^2-f_m(x)\big|=\frac{(2^{-m})^2}{4}=2^{-2m-2}

    Linear interpolation of a function with second derivative 2 on a grid of spacing hh errs by at most 2h2/8=h2/42h^2/8=h^2/4:

  3. xy=12((x+y)2−x2−y2)xy=\tfrac12\big((x+y)^2-x^2-y^2\big)

    The sawtooths are produced one after another by a ReLU network of constant width and depth O(m)\order{m}, so accuracy ε\varepsilon costs O(log⁡(1/ε))\order{\log(1/\varepsilon)} units. One hidden layer needs Θ(ε−1/2)\Theta(\varepsilon^{-1/2}), since NN pieces cannot fit x2x^2 better than about 1/(8N2)1/(8N^2). Products come from squares, then polynomials and Taylor expansions: Yarotsky approximates the unit ball of the Sobolev space Wn,∞([0,1]d)W^{n,\infty}([0,1]^d) to accuracy ε\varepsilon with depth O(ln⁡(1/ε))\order{\ln(1/\varepsilon)} and O(ε−d/nln⁡(1/ε))\order{\varepsilon^{-d/n}\ln(1/\varepsilon)} weights.

Depth also helps when the target itself is a composition. If ff of dd variables is a binary tree of functions of two variables, each with mm derivatives, a deep network mirroring the tree approximates it to accuracy ε\varepsilon with O((d−1) ε−2/m)\order{(d-1)\,\varepsilon^{-2/m}} units, while generic shallow networks need O(ε−d/m)\order{\varepsilon^{-d/m}} (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 m1,…,mℓm_1,\dots,m_\ell allow at most ∏i(mi+1)\prod_i(m_i+1) pieces; one hidden layer of nn units cuts Rd\R^d into at most ∑j≤d(nj)\sum_{j\le d}\binom nj regions, while deep networks can have exponentially many in depth (Montúfar et al.).
  • The tent map Δ(x)=2 ReLU(x)−4 ReLU(x−12)\Delta(x)=2\,\mathrm{ReLU}(x)-4\,\mathrm{ReLU}(x-\tfrac12) composed LL times gives 2L2^L pieces at width 2; any approximant within L1L^1 error 116\tfrac1{16} needs at least 2L−32^{L-3} 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 x2x^2 with error 2−2m−22^{-2m-2} at depth O(m)\order{m}, giving O(log⁡(1/ε))\order{\log(1/\varepsilon)}-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.

Question 1

A ReLU network on R\R has three hidden layers of width 4. At most how many affine pieces can its output have?

  1. 13
  2. 64
  3. 125
  4. 4,096
Show the answer

C. 125

∏i(mi+1)=53=125\prod_i(m_i+1)=5^3=125. With the same 12 units in one layer the bound would be 13.

Question 2

Why does composing a function with the tent map Δ\Delta double its number of affine pieces on [0,1][0,1]?

  1. Δ\Delta has two ReLU units, and each adds one piece
  2. Composition always doubles the number of pieces
  3. Δ\Delta is affine on each half of [0,1][0,1] and maps each half onto all of [0,1][0,1], so every piece of the inner sawtooth is split in two
  4. The tent map doubles the input's frequency in the Fourier domain
Show the answer

C. Δ\Delta is affine on each half of [0,1][0,1] and maps each half onto all of [0,1][0,1], so every piece of the inner sawtooth is split in two

Applying Δ\Delta after sL−1s_{L-1}: each piece of sL−1s_{L-1} runs from 0 to 1 or back, and crosses 12\tfrac12 once, where Δ\Delta folds it. So each piece becomes two.

Question 3

Yarotsky's fmf_m approximates x2x^2 on [0,1][0,1] with error 2−2m−22^{-2m-2}. What is the smallest mm that guarantees error at most 10−610^{-6}?

  1. 3
  2. 9
  3. 20
  4. 1,000
Show the answer

B. 9

m=9m=9 gives 2−20≈9.5×10−72^{-20}\approx9.5\times10^{-7}, while m=8m=8 gives 2−18≈3.8×10−62^{-18}\approx3.8\times10^{-6}. Depth grows like log⁡(1/ε)\log(1/\varepsilon), whereas one hidden layer would need hundreds of pieces.

Question 4

Which statement do depth-separation theorems justify?

  1. Deeper networks always generalize better than shallow ones
  2. Every function is computed more efficiently by a deep network
  3. Trained deep networks realize exponentially many linear regions
  4. 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).