Skip to main content

Depth folds the input space

Two ReLUs fold a line in half, and a stack of such folds makes a zigzag whose pieces double with every layer, while one hidden layer gains only one piece per unit. Count linear pieces and regions, and see why the maximum grows with depth while a random network uses little of it.
DL01.2.4L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: DL01.2.3 Universal approximation

What you will be able to do
  • Show that two ReLU units compute the absolute value and explain it as a fold of the input line.
  • Prove that composing the tent map k times gives 2^k linear pieces from k layers of two units.
  • Derive the bound 1 + n + n(n - 1)/2 on the regions of a one-hidden-layer ReLU network with n units in the plane.
  • Count the linear regions of a small ReLU network from its activation patterns, and compare depths at equal parameter budgets.

The question

One hidden layer can approximate anything, so why are the networks behind image and language models dozens of layers deep? Here is a sharp version of the question: eight ReLU units, arranged as four layers of two, compute a zigzag with 16 straight pieces. How many units does a network with one hidden layer need for the same zigzag?

From the last lesson

1. In the hinge construction, what is the output weight of the unit at a knot?

Show answer

The change of slope at that knot, \({v_i = s_i - s_{i-1}}\).

2. At most how many linear pieces can one hidden layer of \(n\) ReLUs make on a line?

Show answer

\({n + 1}\): each unit adds at most one bend.

Intuition

Fold a strip of paper in half and draw on it: when you unfold it, the drawing appears twice, mirrored. A layer of ReLUs can fold its input space the same way, sending two different inputs to the same place. Whatever the later layers compute is then computed for both at once.

Fold again and every drawing appears four times; fold \(k\) times and it appears \(2^k\) times. Each fold costs one layer of two units, but it doubles the number of straight pieces.

Three panels over x from 0 to 1. Panel 1 layer, 2 units: a vermillion tent rising from 0 to 1 at x equals 0.5 and back to 0. Panel 2 layers, 4 units: two tents, a zigzag with peaks at 0.25 and 0.75. Panel 3 layers, 6 units: four tents, peaks at 1/8, 3/8, 5/8, 7/8. Under each panel the interval from 0 to 1 is drawn as a strip cut into equal cells in alternating blue tints, with the counts 2 pieces, 4 pieces and 8 pieces.
DL01.2.4-F1

Depth as folding. Each layer of two ReLUs folds \({[0, 1]}\) onto itself, so the number of straight pieces doubles with every layer, while the number of units grows by only two.

A one-hidden-layer network cannot fold. It adds its units side by side, and each unit adds one bend (DL01.2.3). So it pays one unit per piece, where depth pays two units per doubling.

Build it up

Step 1. Two units fold the line. \({\mathrm{relu}(x) + \mathrm{relu}(-x)}\) is \(x\) for positive \(x\) and \(-x\) for negative \(x\): it is \({\abs{x}}\). It sends \(x\) and \(-x\) to the same output, so it folds the number line at 0, left half onto right half.

Two panels. Left, titled Two units: the V-shaped graph of the absolute value in vermillion over x from minus 1.2 to 1.2, its left arm labelled relu of minus x and its right arm relu of x, with the formula absolute value of x equals relu of x plus relu of minus x. Right, titled Mirror points land together: a blue input line from minus 1 to 1 with dots at minus 0.8, minus 0.3, 0.3 and 0.8, and green arrows down to a vermillion output line from 0 to 1, where minus 0.8 and 0.8 both arrive at 0.8, and minus 0.3 and 0.3 both at 0.3.
DL01.2.4-F2

Two units compute the absolute value, which folds the line at 0. Mirror points land on the same output, so any later layer treats them alike.

Step 2. The tent folds \({[0, 1]}\) onto itself. The course’s running fold is

\[ t(x) = 2\,\mathrm{relu}(x) - 4\,\mathrm{relu}(x - 0.5). \]

For \({0 \le x \le 0.5}\) only the first unit is on: \({t(x) = 2x}\), rising from 0 to 1. For \({0.5 \le x \le 1}\) both are on: \({t(x) = 2x - 4(x - 0.5) = 2 - 2x}\), falling from 1 to 0. Each half of \({[0, 1]}\) is stretched onto all of \({[0, 1]}\): the interval is folded at its middle.

Step 3. Stack the folds. Feed \({t(x)}\) into another copy of \(t\). As \(x\) crosses the first half, \({t(x)}\) sweeps all of \({[0, 1]}\), so \({t(t(x))}\) makes a whole tent there; the same happens on the second half. Two tents, four pieces.

Step 4. Write it as a network. Layer 1 computes \({(\mathrm{relu}(x), \mathrm{relu}(x - 0.5))}\). Every later layer first forms \({t = 2u_1 - 4u_2}\) from the two units before it, then applies \({(\mathrm{relu}(t), \mathrm{relu}(t - 0.5))}\). Since \({t \ge 0}\) on \({[0, 1]}\), the first unit just passes \(t\) on. The output forms \({2u_1 - 4u_2}\) once more. So \(k\) folds take \(k\) hidden layers of two units, \(2k\) units in all.

The formal statement

NoteProposition: folding doubles the pieces

For \({k \ge 1}\) the \(k\)-fold composition \({t^{k} = t \circ t \circ \dots \circ t}\) is linear on each of the \(2^k\) intervals \({[j/2^k, (j + 1)/2^k]}\) and maps each of them onto \({[0, 1]}\). Neighbouring pieces have slopes \(2^k\) and \(-2^k\), so \(t^k\) has exactly \(2^k\) linear pieces. A network with \(k\) hidden layers of two ReLUs computes it.

Proof, by induction on \(k\). For \({k = 1}\), Step 2 showed it: two pieces, slopes 2 and \(-2\), each onto \({[0, 1]}\). Suppose it holds for \(k\). On one piece \(I\) of \(t^k\), the values \({u = t^k(x)}\) run once across \({[0, 1]}\), linearly, with slope \({\pm 2^k}\). Apply \(t\): while \(u\) runs over \({[0, \tfrac12]}\), \({t(u) = 2u}\) runs over \({[0, 1]}\); while \(u\) runs over \({[\tfrac12, 1]}\), \({t(u) = 2 - 2u}\) runs back over \({[0, 1]}\). So \(I\) splits at its middle into two halves of length \(2^{-(k+1)}\), each mapped linearly onto \({[0, 1]}\), with slopes \({\pm 2 \cdot 2^k = \pm 2^{k+1}}\) of opposite signs. Every piece doubles, giving \(2^{k+1}\) pieces. \(\square\)

What one hidden layer needs. A single hidden layer of \(n\) units makes at most \({n + 1}\) pieces (exercise 3 of DL01.2.3). For \(2^k\) pieces it needs

\[ n + 1 \ge 2^k, \quad \text{so} \quad n \ge 2^k - 1, \]

and the hinge construction of DL01.2.3, with a hinge at each of \({0, 1/2^k, \dots, (2^k - 1)/2^k}\), does it with \(2^k\) units (exercise 3 shows that \(2^k\) is the exact minimum). For \({k = 4}\): 8 units deep against 16 units wide. For \({k = 10}\): 20 against 1,024. Depth grows the pieces exponentially in the number of units; width grows them linearly. Telgarsky (2016) proved a strong form of this separation, and Montufar et al. (2014) the folding picture behind it.

Regions in the plane. With two inputs, each first-layer ReLU switches on one side of the line \({\vect{w}_j\T\vect{x} + b_j = 0}\). Inside each region cut out by these lines no unit switches, so the network is one linear function there. Count the regions that \(n\) lines in general position (no two parallel, no three through one point) make.

Three square panels with lines cutting them into cells in alternating blue tints, ink borders. 1 line: 2 regions. 2 lines crossing: 4 regions, with the note crosses 1 line: plus 2. 3 lines, each pair crossing inside the square at a different point: 7 regions, with the note crosses 2 lines: plus 3.
DL01.2.4-F4

Adding lines one at a time. The new line crosses every old one at a different point, is cut into one more segment than it has crossings, and each segment splits one region in two.

Add the lines one at a time. Line \(j\) meets the \({j - 1}\) earlier lines at \({j - 1}\) different points, which cut it into \(j\) segments. Each segment divides one region into two, so line \(j\) adds \(j\) regions. Starting from the one region of the empty plane,

\[ \begin{aligned} r(n) &= 1 + (1 + 2 + \dots + n) \\ &= 1 + \frac{n(n + 1)}{2} \\ &= 1 + n + \frac{n(n - 1)}{2}. \end{aligned} \]

Lines that are parallel, or that meet three at a point, cross the earlier lines at fewer distinct points, so they are cut into fewer segments and add fewer regions: general position gives the most. So one hidden layer of \(n\) ReLUs on two inputs has at most \({1 + n + n(n - 1)/2}\) linear regions, which grows like \(n^2/2\). Later layers bend their lines at the earlier ones and can fold whole groups of regions onto each other, and the maximum then grows exponentially with depth (Montufar et al., 2014; Goodfellow et al., equation 6.42).

Worked example

Push four inputs, \({0.1, 0.3, 0.7, 0.9}\), through three folds.

Four horizontal number lines from 0 to 1, one above the other: input x in blue, then after layer 1, after layer 2 and after layer 3 in vermillion. Green arrows carry each point down. Input dots at 0.1, 0.3, 0.7, 0.9. After layer 1 only two dots remain, at 0.2 and 0.6: 0.1 and 0.9 both go to 0.2, and 0.3 and 0.7 both go to 0.6. After layer 2: 0.4 and 0.8. After layer 3: 0.8 and 0.4, the arrows crossing. A note: 0.1 and 0.9 meet after one fold, and so do 0.3 and 0.7.
DL01.2.4-F3

The worked example as a trace. The first fold merges the mirror pairs, and from then on each pair travels as one point.

Layer 1. \({t(0.1) = 2 \cdot 0.1 = 0.2}\) and \({t(0.3) = 0.6}\), from the rising half. From the falling half, \({t(0.7) = 2 - 1.4 = 0.6}\) and \({t(0.9) = 2 - 1.8 = 0.2}\). The mirror pairs 0.1 and 0.9, and 0.3 and 0.7, have merged.

Layer 2. \({t(0.2) = 0.4}\) and \({t(0.6) = 2 - 1.2 = 0.8}\).

Layer 3. \({t(0.4) = 0.8}\) and \({t(0.8) = 2 - 1.6 = 0.4}\).

The same through the units, for \({x = 0.3}\). Layer 1: \({(\mathrm{relu}(0.3), \mathrm{relu}(-0.2)) = (0.3, 0)}\). Layer 2 forms \({t = 2 \cdot 0.3 - 4 \cdot 0 = 0.6}\) and outputs \({(0.6, 0.1)}\). Layer 3 forms \({t = 1.2 - 0.4 = 0.8}\) and outputs \({(0.8, 0.3)}\). The output forms \({1.6 - 1.2 = 0.4}\), matching \({t^3(0.3)}\).

Code

The folding network from scratch, with weights of shape (out, in), and its pieces counted from the changes of slope on a fine grid.

import numpy as np

def relu(z):
    return np.maximum(z, 0.0)

def folding_network(k):
    """k hidden layers of two ReLUs that compute the k-fold tent map, then a linear output."""
    layers = [(np.array([[1.0], [1.0]]), np.array([0.0, -0.5]))]
    for _ in range(k - 1):
        layers.append((np.array([[2.0, -4.0], [2.0, -4.0]]), np.array([0.0, -0.5])))
    layers.append((np.array([[2.0, -4.0]]), np.array([0.0])))
    return layers

def forward(x, layers):
    A = x[:, None]
    for l, (W, b) in enumerate(layers, start=1):
        Z = A @ W.T + b
        A = relu(Z) if l < len(layers) else Z
    return A[:, 0]

def pieces(values, n):
    slopes = np.round(np.diff(values) * n, 6)
    return 1 + int(np.count_nonzero(np.diff(slopes)))

n = 2 ** 12
x = np.arange(n + 1) / n
for k in range(1, 6):
    units = sum(W.shape[0] for W, _ in folding_network(k)[:-1])
    print(f"k = {k}: {units:2d} units in {k} layer{'s' if k > 1 else ' '}, {pieces(forward(x, folding_network(k)), n):2d} pieces")
print("t^3 at 0.1, 0.3, 0.7, 0.9:", np.round(forward(np.array([0.1, 0.3, 0.7, 0.9]), folding_network(3)), 6).tolist())
k = 1:  2 units in 1 layer ,  2 pieces
k = 2:  4 units in 2 layers,  4 pieces
k = 3:  6 units in 3 layers,  8 pieces
k = 4:  8 units in 4 layers, 16 pieces
k = 5: 10 units in 5 layers, 32 pieces
t^3 at 0.1, 0.3, 0.7, 0.9: [0.8, 0.4, 0.4, 0.8]

The one-hidden-layer network for the same zigzag needs a hinge at every bend.

def shallow_zigzag(x, k):
    """2^k ReLU units side by side: slope 2^k from 0, then a change of -/+ 2^(k+1) at each bend."""
    m = 2 ** k
    out = m * relu(x)
    for j in range(1, m):
        out = out + (-1) ** j * 2 * m * relu(x - j / m)
    return out

for k in (3, 4):
    gap = np.max(np.abs(shallow_zigzag(x, k) - forward(x, folding_network(k))))
    print(f"k = {k}: {2 ** k} units in one layer match {2 * k} units in {k} layers (gap {gap:.0e})")
k = 3: 8 units in one layer match 6 units in 3 layers (gap 0e+00)
k = 4: 16 units in one layer match 8 units in 4 layers (gap 0e+00)

Now regions in the plane. The activation pattern of an input is the list of which hidden units are on. Inside one region the pattern is fixed, and crossing a border flips a unit, so counting the distinct patterns on a fine grid counts the regions it visits. We compare three random networks with about 80 parameters each and depths 1, 2 and 3, five draws of each.

def random_layers(sizes, seed):
    rng = np.random.default_rng(seed)
    return [(rng.normal(0, np.sqrt(2 / a), (b, a)), rng.normal(0, 0.5, b)) for a, b in zip(sizes[:-1], sizes[1:])]

def count_regions(layers, lim=2.0, res=300):
    g = np.linspace(-lim, lim, res)
    A = np.array(np.meshgrid(g, g)).reshape(2, -1).T
    bits = []
    for W, b in layers[:-1]:                     # the output layer has no ReLU
        Z = A @ W.T + b
        bits.append(Z > 0)
        A = relu(Z)
    bits = np.concatenate(bits, axis=1)
    codes = bits.astype(np.int64) @ (np.int64(1) << np.arange(bits.shape[1], dtype=np.int64))
    return len(np.unique(codes))

def n_params(sizes):
    return sum(b * (a + 1) for a, b in zip(sizes[:-1], sizes[1:]))

means = {}
for sizes in ([2, 20, 1], [2, 7, 7, 1], [2, 5, 5, 5, 1]):
    counts = [count_regions(random_layers(sizes, seed)) for seed in range(5)]
    means[len(sizes) - 2] = np.mean(counts)
    print(f"depth {len(sizes) - 2}, {n_params(sizes)} parameters: regions {counts}")
print("most a 20-unit layer can make:", 1 + 20 + 20 * 19 // 2)
depth 1, 81 parameters: regions [141, 159, 169, 166, 176]
depth 2, 85 parameters: regions [53, 102, 79, 78, 48]
depth 3, 81 parameters: regions [27, 68, 76, 98, 43]
most a 20-unit layer can make: 211
Three square panels, each the square from minus 2 to 2 in both inputs cut into linear regions with ink borders and alternating blue tints. Depth 1, 2-20-1, 81 parameters: 141 regions cut by 20 straight lines. Depth 2, 2-7-7-1, 85 parameters: 53 regions, some borders bending where they meet first-layer lines. Depth 3, 2-5-5-5-1, 81 parameters: 27 regions, large cells with a few bent borders.
DL01.2.4-F5

The linear regions of one random network of each depth, about 80 parameters each. The deeper networks have bent borders, but fewer regions: a random draw is far from the maximum that depth makes possible.

The result surprises at first. With the same budget, the random deeper networks have fewer regions, about 160, 70 and 60 on average. The maximum grows exponentially with depth, but a randomly drawn network gets nowhere near it: Hanin and Rolnick (2019) showed that at initialisation the average count is at most about the total number of units raised to the input dimension, a bound that does not depend on the depth, and found it close to the truth in experiments. Depth gives the capacity to fold; the weights must be chosen, or learned, to use it.

Explore

DL01.2-X1

Hinges and folds

On the left, drag the knots (or pick one and use its sliders) to build a one-hidden-layer ReLU network that follows \({\sin 2\pi x}\); add knots and watch the largest error fall. On the right, raise the depth and compare the pieces of the folding network with those of a one-layer network that has the same number of units.

A static picture in place of the interactive: the tent map composed once, twice and three times on the interval from 0 to 1, making 2, 4 and 8 straight pieces from 2, 4 and 6 ReLU units, with the pieces shown as strips of alternating tints.

Try to bring the error below 0.1 with as few knots as you can, then press the button that puts the knots on the curve and compare. On the right, find the first depth at which the one-layer network with the same units falls behind, and how far behind it is at depth 6.

Pitfalls

Two panels over x from 0 to 1, each with the dashed 8-piece zigzag of three folds. Left, marked with a cross and titled 6 units, 1 layer: 6 pieces: a vermillion network that follows the first six pieces and then runs straight down out of the picture after x equals 0.75, with the note no hinges left after 6/8. Right, marked with a tick and titled 6 units, 3 layers: 8 pieces: the vermillion folding network on top of the zigzag all the way.
DL01.2.4-F6

Wrong beside right. With six units, one layer runs out of hinges after six pieces; three layers of two fold the interval three times and make all eight.

“Units are units: it does not matter how they are arranged.”

Six ReLUs side by side make at most seven pieces on a line; six ReLUs in three layers of two make eight, and the gap grows exponentially. The arrangement decides how the bends combine: side by side they add, in a chain they multiply.

“Deeper networks always have more linear regions.”

They can have exponentially more, for well-chosen weights. A random deep network typically has about as many as a shallow one with the same number of units, and in the code above it had fewer than a shallow one with the same parameter budget. Quoting the maximum as if it were typical overstates what depth does for a given network.

“More regions mean a better model.”

Regions measure what a network can draw, not whether it draws the right thing. A zigzag with a million pieces is useless for data without such a pattern, and it overfits wildly. Depth helps when the target has repeated or compositional structure that folding can reuse, which is often the case with images and language. Expressivity in full is DL10.1.

Check yourself

Recall

1. Which two units compute \({\abs{x}}\), and why is that a fold?

Show answer

\({\mathrm{relu}(x) + \mathrm{relu}(-x)}\). It sends \(x\) and \(-x\) to the same value, so the left half of the line lands on the right half.

2. How many linear pieces does the \(k\)-fold tent map have, and how many units does the folding network use?

Show answer

\(2^k\) pieces from \(2k\) units, in \(k\) hidden layers of two.

3. How many units does one hidden layer need to make the same \(2^k\) pieces?

Show answer

At least \({2^k - 1}\) by counting pieces, and exactly \(2^k\) in fact.

4. At most how many regions do \(n\) lines in general position make in the plane?

Show answer

\({1 + n + n(n - 1)/2}\): line \(j\) adds \(j\) regions.

5. How do we count the linear regions of a ReLU network in code?

Show answer

Record which hidden units are on at every point of a fine grid and count the distinct patterns.

Exercises

1. ★ Compute \({t(x)}\), \({t^2(x)}\) and \({t^3(x)}\) for \({x = 0.15}\). Which other input in \({[0, 1]}\) has the same \({t(x)}\)?

Show solution

\({t(0.15) = 0.3}\), \({t(0.3) = 0.6}\) and \({t(0.6) = 2 - 1.2 = 0.8}\). The mirror point \({1 - 0.15 = 0.85}\) has \({t(0.85) = 2 - 1.7 = 0.3}\) too, so it follows the same path from layer 1 on.

2. ★★ A one-hidden-layer ReLU network has two inputs and 5 hidden units. What is the largest number of linear regions it can have? Check your answer by adding the lines one at a time.

Show solution

\({1 + 5 + 5 \cdot 4/2 = 16}\). One at a time: the plane starts as 1 region, and the lines add 1, 2, 3, 4 and 5 regions, giving \({1 + 15 = 16}\).

3. ★★★ Show that a one-hidden-layer network with only \({2^k - 1}\) ReLU units cannot equal \(t^k\) on \({[0, 1]}\), for any \({k \ge 1}\).

Show solution

\(t^k\) has \({2^k - 1}\) bends inside \({(0, 1)}\), and each unit bends at most once, so every unit must bend at a different one of them. Write unit \(i\) as \({v_i\,\mathrm{relu}(w_i x + b_i)}\), with \({w_i \ne 0}\).

Going left to right, a unit with \({w_i > 0}\) switches on at its bend and changes the slope by \({\Delta_i = v_i w_i}\). A unit with \({w_i < 0}\) switches off there and changes it by \({\Delta_i = -v_i w_i}\).

Left of every bend only the units with \({w_i < 0}\) are on, so the first slope is the sum of \({v_i w_i = -\Delta_i}\) over those units.

The slope of \(t^k\) changes by \({\pm 2^{k+1}}\) at every bend, so every \(\Delta_i\) is a multiple of \(2^{k+1}\), and so is the first slope. But the first slope of \(t^k\) is \(2^k\), which is not a multiple of \(2^{k+1}\). So \({2^k - 1}\) units are too few, and with the construction in the lesson, \(2^k\) is the exact minimum.

Summary card

Width adds bends; depth folds and multiplies them.

The anchor figure again: the tent map composed once, twice and three times on the interval from 0 to 1, with 2, 4 and 8 straight pieces from 2, 4 and 6 units.
DL01.2.4-F1

Each layer doubles the pieces.

  • Fold. \({\abs{x} = \mathrm{relu}(x) + \mathrm{relu}(-x)}\); the tent \(t(x) = {2\,\mathrm{relu}(x)} - {4\,\mathrm{relu}(x - 0.5)}\) folds \({[0, 1]}\).
  • Depth. \(t^k\) has \(2^k\) pieces from \(2k\) units; one hidden layer needs \(2^k\) units.
  • Regions. \(n\) lines in general position make \({1 + n + n(n - 1)/2}\) regions.
  • Typical, not maximal. Random deep networks use little of the exponential maximum.

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Simon J. D. Prince, Understanding Deep Learning, MIT Press, free PDF. Section 4.1 composes two shallow networks and describes the first as folding the input space back onto itself (figure 4.3); section 4.2 shows that the composition is a deep network; section 4.5 compares shallow and deep networks by their linear regions. The notes to chapter 3 give Zaslavsky’s (1975) bound on the regions made by hyperplanes, which for two inputs is the formula derived here; the notes to chapter 4 summarise Telgarsky (2016).
  • Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, section 6.4.1. Figure 6.5 explains the advantage of depth with absolute-value units that fold the input space, after Montufar et al. (2014), and equation 6.42 gives their bound on the linear regions of a deep rectifier network, exponential in the depth.
  • Guido Montúfar, Razvan Pascanu, Kyunghyun Cho and Yoshua Bengio, On the number of linear regions of deep neural networks, arXiv 1402.1869 (2014). Deep networks map portions of each layer’s input space to the same output and so re-use pieces of computation exponentially often in their depth.
  • Matus Telgarsky, Benefits of depth in neural networks, COLT 2016. Networks with order \(k^3\) layers of constant width that networks with order \(k\) layers cannot approximate unless they have exponentially many, order \(2^k\), nodes. Its Lemma 3.10 uses exactly this lesson’s tent map (with one more ReLU around it, which changes nothing on \({[0, 1]}\)), and Lemma 3.8 shows that composing two such triangle maps multiplies their numbers of rising and falling pieces.
  • Boris Hanin and David Rolnick, Deep ReLU networks have surprisingly few activation patterns, NeurIPS 2019. At initialisation the average number of activation patterns is bounded by the total number of neurons raised to the input dimension, independent of depth, and stays near that bound during training.

Next. DL01.3 Activation functions looks beyond the ReLU: what other bends are on offer, and what each does to training. The theory of expressivity continues in DL10.1.

This lesson unlocks

DL01.3 Activation functions DL10.1 Expressivity and depth (planned)

Your progress is saved in this browser only. No account, no tracking.
Back to top