Twenty units deep against a thousand wide

STATEMENT

Exhibit a function that a deep ReLU network computes with twenty hidden units and that no single hidden layer computes with fewer than a thousand and twenty-three. Build it explicitly, count its pieces, prove the shallow lower bound, and then say precisely what the example does and does not establish.

GIVEN

The triangle map on $[0, 1]$:

and its $k$-fold composition $t_k = t \circ t \circ \cdots \circ t$.

FIND

A ReLU expression for $t$; the number of linear pieces of $t_k$; the hidden units and parameters a depth-$2k$ network needs for $t_k$; and the minimum hidden units a network with a single hidden layer needs to represent it, at $k = 10$.

STRATEGY

Three separate jobs. Write $t$ with rectifiers, which is a small algebra exercise. Count the pieces of $t_k$, which is an induction. Bound the shallow network, which is the only step that needs an argument rather than a construction.

SOLUTION

Step 1 — the triangle, in two ReLU units.

$t(x) = 2\,\mathrm{ReLU}(x) - 4\,\mathrm{ReLU}\!\left(x - \tfrac12\right)$

Check both branches. For $0 \le x \le \tfrac12$ the second term vanishes and the expression is $2x$. For $x > \tfrac12$ it is $2x - 4(x - \tfrac12) = 2 - 2x$. Two hidden units, four weights and two biases in, one row of two weights out.

Step 2 — the pieces multiply. $t$ maps each of $[0,\tfrac12]$ and $[\tfrac12,1]$ onto the whole of $[0,1]$, once each. So every linear piece of $t_{k-1}$ is traversed twice by $t_k$ — once on the rising half and once on the falling half — and

$P(t_k) = 2\,P(t_{k-1}), \qquad P(t_1) = 2 \quad\Longrightarrow\quad P(t_k) = 2^k$

At $k = 10$ that is $1024$ pieces, and $1023$ breakpoints.

Step 3 — the deep cost. Stacking $k$ copies gives $2k$ hidden units. At $k = 10$: 20 hidden units, and $10 \times 7 = 70$ parameters counting every weight and bias of each block.

Step 4 — the shallow lower bound. This is the part that has to be proved rather than constructed. Let $g$ be any network on $\R$ with a single hidden layer of $n$ ReLU units:

$g(x) = \sum_{j=1}^{n} v_j\,\mathrm{ReLU}(w_j x + c_j) + v_0$

Each term is affine except at the single point $x = -c_j/w_j$ where its slope changes, so $g'$ is piecewise constant and can change value at no more than $n$ points. A function with $p$ linear pieces has $p - 1$ points where its slope changes. Hence

$p - 1 \le n, \qquad \text{so} \qquad n \ge P(t_k) - 1 = 2^k - 1$

At $k = 10$: $n \ge 1023$ hidden units, and $1023 \cdot 1 + 1023 + 1023 \cdot 1 + 1 = 3070$ parameters.

Step 5 — the comparison. $20$ units against $1023$; $70$ parameters against $3070$. The gap is $2^k$ against $2k$, so it widens without limit: at $k = 20$ the shallow network needs more than a million units to represent what twenty layers of two units represent exactly.

Check — sanity

The ReLU form agrees with the definition at three points. $t(0.25) = 0.5$, $t(0.5) = 1$, $t(0.75) = 0.5$, and the snippet prints all three. If the $-4$ were a $-2$, the third would come out as $1$ instead.

The counted pieces match the predicted $2^k$ at every $k$ tested, including $k = 10$, where the count is over $16\,384$ sample intervals. A miscount of even one piece would break the doubling.

The lower bound is tight, not merely valid. A shallow network with exactly $1023$ well-placed units can represent $t_{10}$: put one breakpoint at each of the $1023$ interior kinks and solve for the coefficients. So $1023$ is the answer, not a weak bound that a cleverer construction would beat.