Chapter 5 · I.5

Problems

A chapter that uses mathematics has to teach that mathematics by making the reader compute. A chapter that only displays equations has failed, however correct the equations are.

M3Load-bearing

7/5 problems7/4 variants10/10 exercisesquota met, and enforced

The contract

5 worked problems, minimum.
4 distinct variants, and no variant more than half of them.
10 exercises, every one with a published solution.
At least one numeric problem — present.
At least one symbolic problem — present.
At least one limit or counterexample problem — present.
At least one complexity or shape problem — present.
At least one ▲▲▲ problem — present.

Numerical instantiationSymbolic derivationDimensional algebraCost accountingConstructed failureProof or impossibilityLimiting case

Problem I.5.B01

Three inputs, two regions, one network

numeric▲△△

Every value here is exact; all are printed to 4 d.p. so they line up with the reproduction snippet.

STATEMENT

Push three inputs through the same two-layer network. Report the pre-activations, the activations and the output for each, and then answer the question the numbers are really for: which of the three inputs are processed by the same affine map, and how you can tell without computing the output at all.

GIVEN

Two inputs, three hidden ReLU units, one output. Row-major throughout (Vectors, matrices and the row-major convention 0.LA.01), so a layer is applied on the right.

\mat{W}^{(1)} = \begin{bmatrix} 1 & -1 & 0.5 \\ 0.5 & 1 & -1 \end{bmatrix}, \qquad \vec{b}^{(1)} = \begin{bmatrix} -0.5 & 0.25 & 0 \end{bmatrix}

\mat{W}^{(2)} = \begin{bmatrix} 2 \\ -1 \\ 1.5 \end{bmatrix}, \qquad b^{(2)} = 0.75

The three inputs:

\vec{x}_a = \begin{bmatrix} 1 & 2 \end{bmatrix}, \qquad \vec{x}_b = \begin{bmatrix} 1.2 & 2.5 \end{bmatrix}, \qquad \vec{x}_c = \begin{bmatrix} -1 & 0 \end{bmatrix}

FIND

For each input: $\vec{z}^{(1)}$ , $\vec{a}^{(1)}$ , the activation pattern, and $\hat{y}$ . Then the effective affine map $\hat{y} = \vec{x}\vec{w} + c$ that the network applies on each pattern.

STRATEGY

Compute the pre-activations first and read the pattern off their signs, before touching the second layer. The pattern is what decides everything that follows, so getting it in hand early turns the rest into arithmetic.

SOLUTION

Step 1 — the pre-activations for $\vec{x}_a$ . This is the first half of one step of (I.5.1): each entry of $\vec{z}^{(1)}$ pairs $\vec{x}$ with one column of $\mat{W}^{(1)}$ .

z_1 = (1)(1) + (2)(0.5) - 0.5 = 1.5, \qquad z_2 = (1)(-1) + (2)(1) + 0.25 = 1.25

z_3 = (1)(0.5) + (2)(-1) + 0 = -1.5

So $\vec{z}^{(1)} = \begin{bmatrix} 1.5 & 1.25 & -1.5 \end{bmatrix}$ and the activation pattern is $110$ — units one and two on, unit three off.

Step 2 — activation and output. $\vec{a}^{(1)} = \begin{bmatrix} 1.5 & 1.25 & 0 \end{bmatrix}$ , and

$\hat{y} = (1.5)(2) + (1.25)(-1) + (0)(1.5) + 0.75 = 3 - 1.25 + 0.75 = 2.5$

Step 3 — the second input. $\vec{z}^{(1)} = \begin{bmatrix} 1.95 & 1.55 & -1.9 \end{bmatrix}$ , pattern $110$ again, and $\hat{y} = 3.9 - 1.55 + 0.75 = 3.1$ .

Step 4 — the third input. $\vec{z}^{(1)} = \begin{bmatrix} -1.5 & 1.25 & -0.5 \end{bmatrix}$ , pattern $010$ , $\vec{a}^{(1)} = \begin{bmatrix} 0 & 1.25 & 0 \end{bmatrix}$ , and $\hat{y} = -1.25 + 0.75 = -0.5$ .

Step 5 — the map each pattern selects. Write the pattern as a diagonal matrix $\mat{D}$ of ones and zeros. Then ReLU has been replaced by a fixed linear map, and the whole network collapses on that region into equation (I.5.3):

\hat{y} = \vec{x}\left(\mat{W}^{(1)}\mat{D}\,\mat{W}^{(2)}\right) + \left(\vec{b}^{(1)}\mat{D}\,\mat{W}^{(2)} + b^{(2)}\right)

For $\mat{D} = \mathrm{diag}(1,1,0)$ :

w_1 = (1)(2) + (-1)(-1) = 3, \qquad w_2 = (0.5)(2) + (1)(-1) = 0

c = (-0.5)(2) + (0.25)(-1) + 0.75 = -0.5

so on that region $\hat{y} = 3x_1 + 0\,x_2 - 0.5$ . For $\mat{D} = \mathrm{diag}(0,1,0)$ : $w_1 = 1$ , $w_2 = -1$ , $c = 0.5$ , giving $\hat{y} = x_1 - x_2 + 0.5$ .

Step 6 — the answer to the question actually asked. $\vec{x}_a$ and $\vec{x}_b$ share the pattern $110$ , so they share one affine map; $\vec{x}_c$ does not. You can tell from the signs of $\vec{z}^{(1)}$ alone, which is three inner products — the second layer never enters the decision.

Answer

input	$\vec{z}^{(1)}$	pattern	$\hat{y}$	map on that region
$\vec{x}_a$	$(1.5,\ 1.25,\ -1.5)$	$110$	$2.5$	$3x_1 + 0x_2 - 0.5$
$\vec{x}_b$	$(1.95,\ 1.55,\ -1.9)$	$110$	$3.1$	$3x_1 + 0x_2 - 0.5$
$\vec{x}_c$	$(-1.5,\ 1.25,\ -0.5)$	$010$	$-0.5$	$x_1 - x_2 + 0.5$

The first two inputs lie in one linear region and the third in another.

Check — numeric · i-5-b01-activation-pattern.py

def forward(x):
    z = [sum(x[i] * W1[i][j] for i in range(2)) + b1[j] for j in range(3)]
    a = [max(0.0, t) for t in z]
    return z, a, sum(a[j] * W2[j] for j in range(3)) + b2

Prints the three patterns $110$ , $110$ , $010$ , the outputs $2.5000$ , $3.1000$ , $-0.5000$ , and each region’s affine map — which it then evaluates directly, as a second route to the same output.

Executed in CI. The digits above are the digits it printed.

Check — sanity

The effective map reproduces the output. On the region $110$ , $3(1) + 0(2) - 0.5 = 2.5$ and $3(1.2) + 0(2.5) - 0.5 = 3.1$ . Two different inputs, one formula, the right answers. That is the content of a linear region stated as an arithmetic check.

The dead unit cannot matter. Unit three is off for $\vec{x}_a$ , so the third entry of $\mat{W}^{(2)}$ — the value $1.5$ — cannot influence $\hat{y}$ . Change it to $150$ and recompute: still $2.5$ .

The second coordinate genuinely drops out. On region $110$ the coefficient of $x_2$ is exactly zero, so moving $\vec{x}_a$ to $(1, 5)$ should not change the output as long as the pattern holds. Check the pattern first: $\vec{z}^{(1)} = (3, 4.25, -4.5)$ , still $110$ , and $\hat{y} = 6 - 4.25 + 0.75 = 2.5$ . It does not change.

Where this breaks

The whole calculation assumes the pattern is read at the given input. It is not a property of the network — it is a property of the network and the input together. A common mistake is to speak of “the dead units” of a model as though the set were fixed; unit three is off here and on for $\vec{x} = (2, 0)$ , where $z_3 = 1$ . Only a unit off for every input in the dataset is dead in the sense of I.3, and that is a much stronger and much rarer claim.

Variation

Find an input for which all three units are on, then one for which all three are off — or show that the second is impossible. I.5.X01 does exactly this by exhaustion, so try it by hand first.

Problem I.5.B02

Every region is one matrix, and its rank is the count of live units

symbolic▲▲△

Symbolic.

STATEMENT

Derive, in general, the affine map a two-layer ReLU network applies inside a single linear region. Then read two facts off the derivation: that the network is piecewise affine, and that the rank of the map on a region is bounded by the number of units switched on in it.

GIVEN

A network $\hat{\vec{y}} = \varphi(\vec{x}\mat{W}^{(1)} + \vec{b}^{(1)})\mat{W}^{(2)} + \vec{b}^{(2)}$ with $\varphi = \mathrm{ReLU}$ , $\mat{W}^{(1)} \in \R^{d_0 \times d_1}$ and $\mat{W}^{(2)} \in \R^{d_1 \times d_2}$ .

Fix an input $\vec{x}_\star$ and let $\mat{D} = \mathrm{diag}\!\left(\mathbf{1}[z^{(1)}_j > 0]\right)$ be the diagonal matrix of its activation pattern, with $k = \mathrm{tr}(\mat{D})$ units on.

FIND

The effective $\mat{W}_\star$ and $\vec{b}_\star$ with $\hat{\vec{y}} = \vec{x}\mat{W}_\star + \vec{b}_\star$ for every $\vec{x}$ in the region containing $\vec{x}_\star$ , and a bound on $\operatorname{rank}(\mat{W}_\star)$ .

STRATEGY

The one step that matters is replacing $\mathrm{ReLU}$ by $\mat{D}$ . That substitution is exact — not an approximation — precisely on the set where the pattern does not change, and everything after it is matrix algebra.

SOLUTION

Step 1 — ReLU becomes a matrix. On the region, every unit’s sign is fixed. For a unit that is on, $\mathrm{ReLU}(z) = z$ ; for one that is off, $\mathrm{ReLU}(z) = 0$ . Applying ReLU is therefore the same as multiplying on the right by $\mat{D}$ :

$\varphi(\vec{z}) = \vec{z}\mat{D} \quad \text{for every } \vec{z} \text{ in the region}$

This is an identity on that set, not a linearisation.

Step 2 — substitute and expand.

\hat{\vec{y}} = \left(\vec{x}\mat{W}^{(1)} + \vec{b}^{(1)}\right)\mat{D}\,\mat{W}^{(2)} + \vec{b}^{(2)} = \vec{x}\underbrace{\mat{W}^{(1)}\mat{D}\,\mat{W}^{(2)}}_{\mat{W}_\star} + \underbrace{\vec{b}^{(1)}\mat{D}\,\mat{W}^{(2)} + \vec{b}^{(2)}}_{\vec{b}_\star}

which is equation (I.5.3). The network is affine on the region, with a $\mat{W}_\star$ and $\vec{b}_\star$ that depend on $\mat{D}$ and on nothing else.

Step 3 — piecewise affine. The regions are indexed by the finitely many patterns $\mat{D}$ that occur. Each contributes one affine map, and the maps agree on shared boundaries because a unit crossing zero contributes zero on both sides. So the network is a continuous piecewise affine function — a statement about the whole model, obtained without any assumption about the weights.

Step 4 — the rank bound. Rank cannot exceed that of any factor, and $\operatorname{rank}(\mat{D}) = k$ :

\operatorname{rank}(\mat{W}_\star) \le \min\!\left(\operatorname{rank}\mat{W}^{(1)},\ k,\ \operatorname{rank}\mat{W}^{(2)}\right) \le \min(d_0,\ k,\ d_2)

using Rank, eigenvalues and the singular value decomposition 0.LA.04. So on a region where only $k$ units are live, the network’s output lies in a subspace of dimension at most $k$ , whatever the widths are elsewhere.

Step 5 — what that means. Width $d_1$ does not act on a single input. On any one input only the live units count, and the network behaves like a much smaller model. Width buys variety across regions, not capacity within one.

Answer

\mat{W}_\star = \mat{W}^{(1)}\mat{D}\,\mat{W}^{(2)}, \qquad \vec{b}_\star = \vec{b}^{(1)}\mat{D}\,\mat{W}^{(2)} + \vec{b}^{(2)}

exactly, on the whole region; and $\operatorname{rank}(\mat{W}_\star) \le \min(d_0, k, d_2)$ where $k$ is the number of units switched on. The network is continuous and piecewise affine, with one such map per realised activation pattern.

Check — sanity

It reproduces I.5.B01. There $d_0 = 2$ , $d_1 = 3$ , $d_2 = 1$ , $\mat{D} = \mathrm{diag}(1,1,0)$ and $k = 2$ . The formula gives $\vec{w}_\star = (3, 0)$ and $b_\star = -0.5$ , which is what the direct forward pass returned.

The rank bound is not vacuous there. $\min(2, 2, 1) = 1$ , and $\vec{w}_\star = (3,0)$ has rank 1. The bound is tight in that case.

Every ReLU disappears. If any survived, the expression would not be affine, and the substitution in Step 1 would have been wrong. Counting them is a real check: three units in, three columns of $\mat{D}$ , none left over.

Where this breaks

Two assumptions are load-bearing, and both fail for activations other than ReLU.

$\varphi$ must be piecewise linear for $\mat{D}$ to exist at all. With GELU or tanh there is no diagonal matrix of ones and zeros that reproduces the activation on any open set, so the network has no linear regions, is not piecewise affine, and none of the region-counting in I.5.B07 applies to it. What survives is a local statement — the Jacobian at a point — which is a different and weaker object.

$\varphi$ must be elementwise for $\mat{D}$ to be diagonal. Softmax is not, so the same substitution would produce a dense matrix and the rank argument would say nothing. That is I.3.X08 seen from the other side.

Variation

Extend the derivation to $L$ layers: show that on a region the network is $\vec{x}\,\mat{W}^{(1)}\mat{D}^{(1)}\mat{W}^{(2)}\mat{D}^{(2)}\cdots\mat{W}^{(L)}$ plus a bias, and state the rank bound in terms of the smallest live count across layers. Then say which single layer decides it.

Problem I.5.B03

A shape and parameter audit of a four-layer MLP

shape▲△△

Exact integer counts; memory in decimal megabytes.

STATEMENT

Audit a classifier layer by layer: the shape of every matrix, the shape of every intermediate, the parameter count of each layer and of the whole model, and the memory that model occupies in fp32. Then answer the question the audit exists to answer — where is the money.

GIVEN

An MLP with widths

$(d_0, d_1, d_2, d_3, d_4) = (784,\ 512,\ 256,\ 128,\ 10)$

Four affine layers, ReLU after the first three, no activation on the head. One example at a time, so the input is a row $\vec{x} \in \R^{1 \times 784}$ .

FIND

A table of $\mat{W}^{(\ell)}$ and $\vec{b}^{(\ell)}$ shapes, the shape of each $\vec{a}^{(\ell)}$ , per-layer and total parameter counts, the fp32 size, and the share of the total held by the first layer.

STRATEGY

Count with equation (I.5.2), one layer at a time. The two habits worth building are writing the bias into the count rather than waving it away, and checking that each layer’s output shape is the next layer’s input shape before adding anything up.

SOLUTION

Step 1 — shapes. A layer holds $\mat{W}^{(\ell)} \in \R^{d_{\ell-1} \times d_\ell}$ and $\vec{b}^{(\ell)} \in \R^{1 \times d_\ell}$ , and the row passing through is $(1 \times d_{\ell-1})(d_{\ell-1} \times d_\ell) \to (1 \times d_\ell)$ .

$\ell$	$\mat{W}^{(\ell)}$	$\vec{b}^{(\ell)}$	$\vec{a}^{(\ell)}$
1	$784 \times 512$	$1 \times 512$	$1 \times 512$
2	$512 \times 256$	$1 \times 256$	$1 \times 256$
3	$256 \times 128$	$1 \times 128$	$1 \times 128$
4	$128 \times 10$	$1 \times 10$	$1 \times 10$

Every inner dimension meets. The batch dimension is untouched throughout, which is what makes the same weights work for one example or ten thousand.

Step 2 — parameters, layer by layer. $d_{\ell-1}d_\ell + d_\ell$ :

$784 \cdot 512 + 512 = 401\,408 + 512 = 401\,920$

$512 \cdot 256 + 256 = 131\,072 + 256 = 131\,328$

$256 \cdot 128 + 128 = 32\,768 + 128 = 32\,896$

$128 \cdot 10 + 10 = 1\,280 + 10 = 1\,290$

Step 3 — the total.

$N = 401\,920 + 131\,328 + 32\,896 + 1\,290 = 567\,434$

Step 4 — memory. At 4 bytes per fp32 parameter, $567\,434 \times 4 = 2\,269\,736$ bytes: $2.27$ MB, or $2.165$ MiB. Training with Adam multiplies that by roughly four, since the optimiser carries two moment estimates alongside the gradient — a point Chapter I.7 makes properly.

Step 5 — where the money is.

$\frac{401\,920}{567\,434} = 70.83\%$

The first layer holds seven parameters in ten. It is not the widest layer and it is not doing the classification; it is simply the one facing the input, and the input is 784 numbers wide. This is the general shape of the bill: an MLP pays for its interface with the data.

Answer

$\ell$	shape	parameters
1	$784 \times 512$	$401\,920$
2	$512 \times 256$	$131\,328$
3	$256 \times 128$	$32\,896$
4	$128 \times 10$	$1\,290$
	total	$\mathbf{567\,434}$

$2\,269\,736$ bytes in fp32, which is $2.27$ MB. The first layer holds $70.83\%$ of the model.

Check — sanity

The chain of shapes closes. $784 \to 512 \to 256 \to 128 \to 10$ , with each layer’s output width equal to the next layer’s input width, and the final width equal to the number of classes. A single mismatch anywhere would make the model unrunnable, so this check is free and catches most typing errors.

The biases are a rounding error, and are still counted. $512 + 256 + 128 + 10 = 906$ of $567\,434$ , or $0.16\%$ . They are cheap, which is a reason to keep them rather than a reason to omit them from the count — and I.5.X03 shows what dropping them costs.

The layer sizes fall as the widths multiply out. $401\,920 : 131\,328 : 32\,896 : 1\,290$ is close to $4 : 1.3 : 0.33 : 0.013$ , matching the products $784 \cdot 512$ , $512 \cdot 256$ , $256 \cdot 128$ , $128 \cdot 10$ . Parameters track the product of adjacent widths, exactly as (I.5.2) says.

Where this breaks

The count is a count of parameters, and parameters are only one of three things that occupy memory. Activations scale with the batch: at batch 1024 the intermediates alone are $1024 \times (512 + 256 + 128 + 10) \times 4 = 3\,710\,976$ bytes, more than the model. Optimiser state scales with the parameters. Gradients match the parameters again. Quoting a parameter count as though it were a memory requirement is the most common way to underestimate what a model needs by an order of magnitude — and the ratio is worst exactly where it matters, which is during training rather than inference.

Variation

Re-audit with widths $(784, 2048, 10)$ — a wider model with one hidden layer instead of three. Compare the totals before computing them, then check the prediction. Which is larger, and by how much?

Problem I.5.B04

Width costs a square, depth costs a line

complexity▲▲△

Exact integer counts; derived quantities to 3 d.p.

STATEMENT

Put an image into an MLP and read the bill. Count the parameters and the forward FLOPs of a wide shallow network and a narrower deep one on the same input, say where the cost sits in each, and compare both against the parameter count of a convolution doing a comparable job.

GIVEN

The input is a $224 \times 224 \times 3$ image flattened to $d_0 = 150\,528$ numbers, and the output is $1000$ classes.

Wide: one hidden layer of $4096$ units, widths $(150\,528,\ 4096,\ 1000)$ .

Deep: six hidden layers of $1024$ units, widths $(150\,528,\ 1024,\ 1024,\ 1024,\ 1024,\ 1024,\ 1024,\ 1000)$ .

Count a multiply–add as two FLOPs, and one fp32 parameter as four bytes.

FIND

For each network: total parameters, fp32 size, forward FLOPs per example, and the share of the parameters held by the input-facing matrix. Then the parameter count of a $3 \times 3$ convolution taking 3 channels to 64, against the dense layer that maps $3072$ inputs to $64$ outputs.

STRATEGY

Use (I.5.2) and keep the layers separate rather than summing early. The whole lesson lives in the ratio between layers, and a total hides it.

SOLUTION

Step 1 — the wide network.

$150\,528 \cdot 4096 + 4096 = 616\,562\,688 + 4096 = 616\,566\,784$

$4096 \cdot 1000 + 1000 = 4\,096\,000 + 1000 = 4\,097\,000$

$N_{\text{wide}} = 620\,663\,784 \quad\Rightarrow\quad 2.483 \text{ GB in fp32}$

FLOPs: $2(150\,528 \cdot 4096 + 4096 \cdot 1000) = 1\,241\,317\,376$ , or $1.241$ GFLOP for a single image.

The first matrix is $616\,566\,784 / 620\,663\,784 = 99.3\%$ of the model.

Step 2 — the deep network. The first layer is $150\,528 \cdot 1024 + 1024 = 154\,141\,696$ . The five inner layers are $5(1024 \cdot 1024 + 1024) = 5\,248\,000$ . The head is $1024 \cdot 1000 + 1000 = 1\,025\,000$ .

$N_{\text{deep}} = 160\,414\,696 \quad\Rightarrow\quad 0.642 \text{ GB}, \quad 0.321 \text{ GFLOP}$

and the first matrix is $96.1\%$ of it.

Step 3 — read the two numbers against each other. The deep network has six times the hidden layers and a quarter of the parameters. Nothing subtle happened: the wide network’s hidden width is four times larger, and it multiplies against $d_0$ , so one matrix grew fourfold. Adding five entire layers of width 1024 cost $5\,248\,000$ parameters — $3.3\%$ of that model, and less than one percent of the wide one.

This is (I.5.2) with the letters read carefully. Width enters as a product of two adjacent widths, so doubling one width doubles one matrix and doubling both quadruples it. Depth enters as a sum over $\ell$ , so adding a layer adds one term.

Step 4 — what the density is buying. A $3 \times 3$ convolution from 3 channels to 64 holds $3 \cdot 3 \cdot 3 \cdot 64 + 64 = 1792$ parameters and applies the same filter at every position. A dense layer taking a $32\times32\times3$ image ( $3072$ numbers) to 64 outputs holds $3072 \cdot 64 + 64 = 196\,672$ — $109.8$ times more, on a smaller image, to produce one vector rather than a feature map at every location.

The MLP is not paying for capacity. It is paying for the assumption that every input coordinate might interact with every unit, which for an image is false and known to be false. Chapter I.11 is the repair.

Answer

	parameters	fp32	FLOP/example	first matrix
wide, $1 \times 4096$	$620\,663\,784$	$2.483$ GB	$1.241$ G	$99.3\%$
deep, $6 \times 1024$	$160\,414\,696$	$0.642$ GB	$0.321$ G	$96.1\%$

A $3\times3$ convolution to 64 channels: $1792$ parameters, against $196\,672$ for the dense layer of the same output width — a factor of $109.8$ .

In both networks the input-facing matrix is essentially the whole model.

Check — numeric · i-5-b04-dense-cost.py

def mlp(widths):
    return sum(widths[i] * widths[i + 1] + widths[i + 1]
               for i in range(len(widths) - 1))

Prints both totals, both GB figures, both first-matrix shares, the convolution comparison, and the square law for widths $512$ , $1024$ , $2048$ .

Executed in CI. The digits above are the digits it printed.

Check — sanity

The square law is visible in one column. A hidden layer of width $512$ holds $262\,656$ parameters in its own matrix; $1024$ holds $1\,049\,600$ ; $2048$ holds $4\,196\,352$ . Each doubling of the width very nearly quadruples the count, and the small excess is the bias.

The FLOP count is twice the parameter count, minus the biases. For the wide network, $2 \times 620\,658\,688 = 1\,241\,317\,376$ . That is not a coincidence: a dense layer performs one multiply–add per weight per example, so forward FLOPs and parameters are locked together for MLPs. They come apart for convolutions, where one weight is used at every position.

The deep network is cheaper in FLOPs by the same ratio as in parameters. $1.241 / 0.321 = 3.87$ against $620.7 / 160.4 = 3.87$ . It must be, by the previous check.

Where this breaks

FLOPs are not time. The wide network’s single matrix is one large, efficient multiply; the deep one’s seven matrices are seven smaller launches with a dependency between each, so the deep network can be slower despite doing a quarter of the arithmetic. Which one wins depends on the batch size, on memory bandwidth, and on whether the layers are large enough to saturate the hardware — which is I.5.X08. Ranking two architectures by FLOPs alone is a well-behaved mistake: it is wrong in a direction you can predict, but it is still wrong.

Variation

Keep the total parameter count of the wide network fixed at roughly $6.2 \times 10^8$ but spend it on a deep network of constant width. How wide can the layers be at depth 10, and what fraction of the budget does the first layer still take? The answer says something about why the first layer of an image model is never dense in practice.

Problem I.5.B05

Twenty units deep against a thousand wide

counterexample▲▲▲

Exact integer counts.

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]$ :

t(x) = \begin{cases} 2x & x \le \tfrac12 \\ 2 - 2x & x > \tfrac12\end{cases}

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.

Answer

$t(x) = 2\,\mathrm{ReLU}(x) - 4\,\mathrm{ReLU}(x - \tfrac12)$ , and $t_k$ has exactly $2^k$ linear pieces.

At $k = 10$ : the deep network uses $20$ hidden units and $70$ parameters. Any network with one hidden layer needs at least $1023$ units — a factor of $51$ — and the factor grows as $2^k / 2k$ .

Check — numeric · i-5-b05-sawtooth.py

def tooth(x):          # one triangle, written with exactly two ReLU units
    return 2.0 * relu(x) - 4.0 * relu(x - 0.5)

Counts slope changes of $t_k$ on a grid sixteen times finer than the pieces, and prints $2, 4, 8, 16, 64, 256, 1024$ for $k = 1,2,3,4,6,8,10$ — the induction of Step 2, confirmed by exhaustion rather than assumed.

Executed in CI. The digits above are the digits it printed.

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.

Where this breaks

Everything above is about representation, and it is worth being blunt about how far that is from a recommendation.

It is one function. The sawtooth was chosen because it is the extreme case. Nothing here says the functions in any application oscillate like this, and for smooth targets the depth advantage can vanish entirely.

It says nothing about training. The deep network representing $t_{10}$ has $70$ specific parameters. Gradient descent from a random start does not find them: the loss surface of a composition of ten triangle maps is close to pathological, and this is the standard demonstration that expressivity and trainability are unrelated properties.

It is one-directional. “Some functions are exponentially cheaper deep” is not “deeper is better”. The converse fails: many functions are equally cheap at either depth, and depth brings vanishing gradients (I.9), conditioning problems (I.7) and a need for normalisation (I.8) that width does not.

The honest summary is that the theorem removes an argument rather than supplying one. Nobody can any longer say a wide shallow network is as good as a deep one because both are universal approximators. I.3.T2 and this problem are about different quantities, and the second is the one that decides cost.

Variation

Modify $t$ to a three-piece map with two peaks and count the pieces of its $k$ -fold composition. Then generalise: for a map with $m$ pieces, how many hidden units does the shallow network need at depth $k$ , and what does that do to the ratio in the answer?

Problem I.5.B06

Relabelling the hidden units, and what that forbids

proof▲▲△

Symbolic, with one order-of-magnitude count.

STATEMENT

Prove that permuting a hidden layer leaves a network’s function unchanged. Count how many such relabellings a layer of width 512 admits. Then state, as consequences rather than opinions, three things that may not be done with the weights of two independently trained networks.

GIVEN

$f(\vec{x}) = \varphi(\vec{x}\mat{W}^{(1)} + \vec{b}^{(1)})\mat{W}^{(2)} + \vec{b}^{(2)}$ with $\varphi$ applied elementwise, and $\mat{P} \in \{0,1\}^{n \times n}$ a permutation matrix, where $n = d_1$ is the hidden width. Recall $\mat{P}\mat{P}^{\mathsf T} = \mat{I}$ .

FIND

A proof that the substitution $(\mat{W}^{(1)}\mat{P},\ \vec{b}^{(1)}\mat{P},\ \mat{P}^{\mathsf T}\mat{W}^{(2)})$ leaves $f$ unchanged at every input; the number of such substitutions at $n = 512$ ; and three consequences.

STRATEGY

The proof turns on one property of $\varphi$ and one of $\mat{P}$ . Identify both before writing anything: the argument is three lines once they are named, and unavailable without them.

SOLUTION

Step 1 — the property of $\varphi$ . $\varphi$ is elementwise, so applying it and then reordering the coordinates gives the same vector as reordering and then applying it. In matrix form, for any permutation $\mat{P}$ and any row $\vec{z}$ :

$\varphi(\vec{z})\mat{P} = \varphi(\vec{z}\mat{P})$

This is exactly the statement that $\varphi$ does not mix coordinates, and it is the only property of the activation the proof uses. It holds for ReLU, sigmoid, tanh and GELU alike; it fails for softmax.

Step 2 — the property of $\mat{P}$ . A permutation matrix is orthogonal: $\mat{P}\mat{P}^{\mathsf T} = \mat{I}$ . Reordering and then undoing the reorder is the identity.

Step 3 — the substitution. Write $\tilde f$ for the network with the substituted weights:

\tilde f(\vec{x}) = \varphi\!\left(\vec{x}\mat{W}^{(1)}\mat{P} + \vec{b}^{(1)}\mat{P}\right) \mat{P}^{\mathsf T}\mat{W}^{(2)} + \vec{b}^{(2)}

Factor $\mat{P}$ out of the argument, since $\vec{x}\mat{W}^{(1)}\mat{P} + \vec{b}^{(1)}\mat{P} = (\vec{x}\mat{W}^{(1)} + \vec{b}^{(1)})\mat{P}$ :

\tilde f(\vec{x}) = \varphi\!\left((\vec{x}\mat{W}^{(1)} + \vec{b}^{(1)})\mat{P}\right) \mat{P}^{\mathsf T}\mat{W}^{(2)} + \vec{b}^{(2)}

Apply Step 1 to pull $\mat{P}$ out of $\varphi$ , then Step 2 to cancel it:

= \varphi\!\left(\vec{x}\mat{W}^{(1)} + \vec{b}^{(1)}\right)\mat{P}\mat{P}^{\mathsf T}\mat{W}^{(2)} + \vec{b}^{(2)} = f(\vec{x}) \qquad \blacksquare \ \text{(I.5.6)}

At every input, to every digit. Not an approximation and not a symmetry of the loss only — a symmetry of the function.

Step 4 — how many. There are $n!$ permutation matrices of size $n$ , and they give distinct parameter vectors whenever the hidden units are distinct. At $n = 512$ :

$\log_{10}(512!) \approx 1166.5, \qquad 512! \approx 10^{1166}$

For scale, the observable universe holds on the order of $10^{80}$ atoms. The number is not large in a way that admits a comparison; it is large in the way that makes exhaustive search a category error.

And permutations are not the only symmetry. ReLU is positively homogeneous, so scaling the $j$ -th column of $\mat{W}^{(1)}$ and the $j$ -th entry of $\vec{b}^{(1)}$ by any $c > 0$ while scaling the $j$ -th row of $\mat{W}^{(2)}$ by $1/c$ is another one, and that family is continuous.

Step 5 — three consequences.

Averaging two trained networks’ weights is not averaging two models. Unit $j$ of one has no relation to unit $j$ of the other, so the mean is a network neither of them trained, and it typically performs worse than both.

A per-unit correlation between two runs measures the seed. Any such statistic is computed over an arbitrary labelling. It can be repaired — match the units first — but not ignored.

A distance in parameter space between checkpoints from different runs is uninterpretable. It is dominated by the permutation, not by any difference in behaviour. Two networks computing the identical function can sit arbitrarily far apart in weight space.

Answer

The substitution leaves $f$ unchanged because $\varphi$ commutes with permutations and $\mat{P}\mat{P}^{\mathsf T} = \mat{I}$ ; the two facts are the whole proof. A hidden layer of width $n$ therefore admits at least $n!$ parameter vectors realising each function, which at $n = 512$ exceeds $10^{1166}$ .

Consequently, across independently trained networks: weight averaging, per-unit correlation and parameter-space distance are all meaningless until the units are matched.

Check — sanity

Check it at $n = 2$ by hand. Swap the two hidden units: exchange the columns of $\mat{W}^{(1)}$ and the entries of $\vec{b}^{(1)}$ , and exchange the rows of $\mat{W}^{(2)}$ . The output is a sum of two terms, and a sum does not care in which order it is written. The general proof is that observation with the bookkeeping done.

The proof uses one property of $\varphi$ , and it is worth naming exactly. Step 1 needs $\varphi(\vec{z})\mat{P} = \varphi(\vec{z}\mat{P})$ — equivariance to permutation. Being elementwise is sufficient for that but not necessary: softmax mixes coordinates and is still permutation-equivariant, so the argument covers it. What would break the proof is an activation that treats its coordinates asymmetrically, such as one applying a different function to each. That is why the property to check is equivariance, not elementwiseness.

The count is sane. $\log_{10}(2!) = 0.30$ , $\log_{10}(8!) = 4.6$ , $\log_{10}(512!) = 1166.5$ by Stirling. The growth is faster than exponential, which is why width makes the redundancy worse rather than better.

Where this breaks

The symmetry constrains what comparisons mean; it does not say the comparisons cannot be made. Git Re-Basin is the constructive version: find the permutation aligning one network to the other, apply it, and only then interpolate. When the alignment is right, the interpolated network can match its endpoints; when it is skipped, the same interpolation collapses. The symmetry did not go away, it was paid for.

Nor does the result say anything about a single run. Comparing a checkpoint with its own earlier state is fine, because no relabelling occurred between them. The failure is specific to comparing across independent initialisations, which is exactly the comparison people most want to make.

Variation

Count the symmetries of a two-hidden-layer network of widths $(n_1, n_2)$ . Then decide whether the positive-rescaling family survives if the activation is GELU instead of ReLU, and say which property of ReLU that family depended on.

Problem I.5.B07

How many pieces a budget buys, and where you put them

limit▲▲△

Exact integer counts.

STATEMENT

Take a fixed number of ReLU units in the plane and count the linear regions two arrangements of them can reach. Establish the growth rate in each case, evaluate both at the same budget, and state the limit that the comparison is really about.

GIVEN

Input dimension $d = 2$ . The two bounds of the chapter:

R_1(n, d) \;\le\; \sum_{i=0}^{d}\binom{n}{i} \tag{I.5.4}

for one hidden layer of $n$ units, and

R_L(n, d) \;\ge\; \left\lfloor \tfrac{n}{d} \right\rfloor^{\,d(L-1)} \sum_{j=0}^{d}\binom{n}{j} \tag{I.5.5}

for $L$ hidden layers of $n$ units each, valid when $n \ge d$ .

FIND

The closed form of (I.5.4) at $d = 2$ and its growth rate in $n$ ; the region counts for thirty units as $1 \times 30$ and as $3 \times 10$ ; the same for sixty units at three depths; and the asymptotic statement the table is evidence for.

STRATEGY

Evaluate before generalising. The closed form at $d = 2$ is three terms, the numbers are small enough to check by hand, and the growth rate is then visible rather than asserted.

SOLUTION

Step 1 — one hidden layer in the plane.

$\sum_{i=0}^{2}\binom{n}{i} = 1 + n + \frac{n(n-1)}{2}$

so $R_1 = \Theta(n^2)$ . Two units give 4 regions, three give 7, ten give 56, one hundred give 5051. Doubling the width roughly quadruples the pieces: growth is polynomial of degree $d$ , and in the plane that degree is two.

Step 2 — the same thirty units, two ways. One layer of thirty:

$1 + 30 + \frac{30 \cdot 29}{2} = 1 + 30 + 435 = 466$

Three layers of ten, using (I.5.5) with $\lfloor 10/2 \rfloor = 5$ :

$5^{\,2 \cdot 2} \cdot \left(1 + 10 + 45\right) = 625 \cdot 56 = 35\,000$

A factor of $75.1$ , at the same unit count and very nearly the same parameter count.

Step 3 — sixty units, three ways.

arrangement	regions
$1$ layer $\times\ 60$	at most $1\,831$
$2$ layers $\times\ 30$	at least $104\,850$
$6$ layers $\times\ 10$	at least $546\,875\,000$

The last is not a larger network. It is the same sixty units, stacked.

Step 4 — the limit the table is about. Read the two bounds as functions of the budget. Hold depth fixed and grow width: $R_1 = \Theta(n^d)$ , polynomial. Hold width fixed and grow depth: the exponent $d(L-1)$ carries $L$ , so $R_L = \Omega\!\left(c^{\,L}\right)$ with $c = \lfloor n/d\rfloor^{d}$ , exponential.

$\lim_{L \to \infty} \frac{R_L(n, d)}{R_1(nL, d)} = \infty$

for any fixed $n > d$ : spending a growing budget on depth outruns spending it on width, eventually and then permanently. That is the precise sense of “depth multiplies what width adds”, and it is a statement about a limit rather than about any particular architecture.

Answer

At $d = 2$ , one hidden layer of $n$ units reaches at most $1 + n + n(n-1)/2$ regions, which is $\Theta(n^2)$ .

Thirty units: $466$ as one layer, at least $35\,000$ as three layers of ten — a factor of $75.1$ . Sixty units: $1\,831$ , $104\,850$ , $546\,875\,000$ at depths $1$ , $2$ and $6$ .

Width buys regions polynomially and depth buys them exponentially, so the ratio diverges as the budget grows.

Check — numeric · i-5-b07-region-counts.py

def shallow(n, d):                       # Zaslavsky 1975, one hidden layer
    return sum(comb(n, i) for i in range(d + 1))

def deep(n, d, L):                       # Montufar et al. 2014, L hidden layers
    return (n // d) ** (d * (L - 1)) * shallow(n, d)

Prints the shallow table for $n = 1 \ldots 100$ , the thirty-unit comparison with its ratio, and the three sixty-unit arrangements.

Executed in CI. The digits above are the digits it printed.

Check — sanity

Small cases are checkable by drawing. One line cuts the plane into 2; two crossing lines into 4; three lines in general position into 7. The formula gives $2, 4, 7$ . A fourth line meets the other three in three points and so adds four regions, giving 11 — which is what $1 + 4 + 6$ says.

The deep bound reduces to the shallow one at $L = 1$ . The exponent $d(L-1)$ becomes zero, the factor becomes 1, and (I.5.5) collapses to (I.5.4). A bound that did not do this would be inconsistent.

The bounds point in the directions they should. (I.5.4) is an upper bound and (I.5.5) a lower one, so the comparison in Step 2 is between the best the shallow network could do and the worst the deep construction achieves. The factor of 75 is therefore a conservative statement of the gap, which is the only direction in which such a comparison is worth anything.

Where this breaks

Region counts measure how finely a network can chop its input space, and that is not what anyone wants from a model. Three limits, in increasing order of how often they are forgotten.

The counts are extremal. A trained network realises far fewer regions than its architecture allows, and the ones it realises cluster near the data rather than spreading evenly.

Pieces are not accuracy. A target needing few pieces can still be approximated badly, and a network with many regions may spend nearly all of them where no data lies.

The bound assumes $n \ge d$ . A layer narrower than the input is not governed by region counting at all but by rank: it has already discarded a subspace, and no depth after it recovers what was lost. That failure is I.5.X04, and its general form is the minimal-width theorem I.5.T4.

Variation

Fix a budget of 120 units in the plane and tabulate (I.5.5) at $L = 1, 2, 4, 12, 20, 30, 60$ with $n = 120/L$ . The maximum is not at the largest $L$ . Find where it is, and explain what the $\lfloor n/d \rfloor$ term does to the bound once the layers get narrow.

Exercises

Every one has a published solution. A hidden solution is a solution; a missing one is an abandonment.

I.5.X02The same budget, two shapesshape▲△△

Audit two classifiers on the same task: widths $(784, 512, 256, 128, 10)$ from I.5.B03, and widths $(784, 2048, 10)$ . Give the parameter count of each, say which is larger and by how much, and then answer the question that matters — which layer would you shrink first, in each.

Hint

Use (I.5.2) and keep the layers separate. Predict the answer before computing; the deep model has three times the layers.

Solution

The deep model. From I.5.B03: $401\,920 + 131\,328 + 32\,896 + 1\,290 = 567\,434$ .

The wide model.

$784 \cdot 2048 + 2048 = 1\,605\,632 + 2048 = 1\,607\,680$

$2048 \cdot 10 + 10 = 20\,490$

$N = 1\,628\,170$

The wide model is $2.87$ times larger with a third of the layers. The prediction most people make is the opposite one, and the reason it fails is that depth appears in (I.5.2) as a sum while width appears as a product. Three extra layers add three terms; one width of $2048$ instead of $512$ multiplies the largest term by four.

Which layer to shrink. In both, the first. It holds $70.83\%$ of the deep model and $98.7\%$ of the wide one, and in neither case is that because the layer is doing more work — it is because it faces $784$ inputs.

The lesson generalises. For any MLP on wide input, the parameter count is approximately $d_0 d_1$ , and every other decision is noise against it. This is why an image model does not begin with a dense layer, why a language model’s embedding table is discussed separately from its blocks, and why quoting depth as a proxy for size is unreliable.

I.5.X03What the bias buys, in one sentence and one counterexamplesymbolic▲△△

Show that a bias-free MLP with any depth, any widths and ReLU activations maps the origin to the origin, whatever its weights. Then say what that costs, and whether the standard repair — appending a constant $1$ to the input — recovers everything a full set of biases would.

Hint

Evaluate the network at $\vec{x} = \vec{0}$ layer by layer. ReLU has one property here that sigmoid does not.

Solution

The origin is pinned. With $\vec{b}^{(\ell)} = \vec{0}$ everywhere, $\vec{0}\mat{W}^{(1)} = \vec{0}$ , and $\mathrm{ReLU}(\vec{0}) = \vec{0}$ . The same at the next layer, and the next. By induction $f(\vec{0}) = \vec{0}$ for every choice of weights and every depth.

What that costs. The network cannot represent any function with $f(\vec{0}) \ne \vec{0}$ — which includes most regression targets and every classifier whose decision boundary does not pass through the origin. The restriction is on the function class, so no amount of training removes it. It is the same failure the perceptron’s bias fixes in I.2, arriving once per layer instead of once.

The absorption trick, and its limit. Append a constant $1$ to the input and add a row to $\mat{W}^{(1)}$ : that row is the first layer’s bias, exactly. So the first layer loses nothing. The later layers are a different matter. Their input is $\mathrm{ReLU}(\cdot)$ , which has no constant coordinate to multiply — unless a hidden unit is arranged to be always on, which costs a unit and constrains its weights. Absorption is exact at the input and approximate after it, and the difference is why frameworks keep a separate bias per layer rather than one augmented column.

What it costs to keep them. In the model of I.5.B03, $512 + 256 + 128 + 10 = 906$ parameters of $567\,434$ : $0.16\%$ . The biases are the cheapest expressivity in the model, which is the whole argument for having them.

Where the argument reverses. Biases are dropped in real architectures — the projections inside a transformer block often omit them — but never for the reason above. There the layer is followed by a normalisation that has its own learned shift, so the bias would be redundant rather than unaffordable. Dropping a parameter because something else supplies it is a different decision from dropping it to save memory, and only the first one is sound.

I.5.X01Seven of the eight patternsnumeric▲▲△

Three hidden units admit eight activation patterns on paper. Using the network of I.5.B01, determine how many of the eight actually occur for some input in the plane, name the one that does not, and prove by hand that it cannot.

Hint

Each unit is on where one linear inequality holds. “All three off” is three inequalities at once — add two of them together and see what they force.

Solution

Seven of eight occur. A scan of the plane at a spacing of $0.005$ finds witnesses for $001$ , $010$ , $011$ , $100$ , $101$ , $110$ and $111$ , and never finds $000$ .

Why seven is the number to expect. Three units draw three lines. In general position, three lines cut the plane into $\binom{3}{0} + \binom{3}{1} + \binom{3}{2} = 1 + 3 + 3 = 7$ regions (I.5.4). One region per pattern, so exactly one of the eight sign vectors is unrealised. The count is not an accident of these particular weights; it is the arrangement bound, met exactly.

Which one, and why. Suppose all three units were off at some $\vec{x}$ :

$z_1 = x_1 + 0.5x_2 - 0.5 \le 0, \quad z_2 = -x_1 + x_2 + 0.25 \le 0, \quad z_3 = 0.5x_1 - x_2 \le 0$

Add the second and third:

$z_2 + z_3 = -0.5x_1 + 0.25 \le 0 \quad\Longrightarrow\quad x_1 \ge 0.5$

From the third alone, $x_2 \ge 0.5x_1 \ge 0.25$ . Substituting both into the first:

$z_1 = x_1 + 0.5x_2 - 0.5 \ \ge\ 0.5 + 0.5(0.25) - 0.5 = 0.125 > 0$

which contradicts $z_1 \le 0$ . The pattern $000$ is impossible.

What the impossibility means. There is no input this network maps to zero through its hidden layer, so the constant $b^{(2)} = 0.75$ is never the whole output. More generally, the set of realisable patterns is a property of the weights, and it is smaller than $2^{n}$ for every network with $n > d$ : at $n = 10$ units in the plane, $56$ of $1024$ patterns occur, or $5.5\%$ . Counting units and exponentiating badly overstates what a layer can do — which is the content of I.5.T1 stated as a fraction.

I.5.X04A narrow layer discards a subspace, permanentlycounterexample▲▲△

An MLP has $d_0 = 10$ and $d_1 = 3$ . Exhibit two distinct inputs that every network of this shape maps to the same output, whatever the later widths, the later depth, or the training. Then say why this is not an optimisation failure and what the general statement is.

Hint

The first layer is a map $\R^{10} \to \R^{3}$ . What is the dimension of its null space, and what does the rest of the network ever see?

Solution

The construction. $\mat{W}^{(1)} \in \R^{10 \times 3}$ has rank at most 3, so by rank–nullity (Rank, eigenvalues and the singular value decomposition 0.LA.04) its null space $\{\vec{v} : \vec{v}\mat{W}^{(1)} = \vec{0}\}$ has dimension at least $7$ .

Pick any non-zero $\vec{v}$ in it and any $\vec{x}$ . Then

(\vec{x} + \vec{v})\mat{W}^{(1)} + \vec{b}^{(1)} = \vec{x}\mat{W}^{(1)} + \vec{v}\mat{W}^{(1)} + \vec{b}^{(1)} = \vec{x}\mat{W}^{(1)} + \vec{b}^{(1)}

The two inputs produce identical pre-activations — the same three numbers, bit for bit. Everything after the first layer is a function of those three numbers, so $f(\vec{x}) = f(\vec{x} + \vec{v})$ for every subsequent architecture and every setting of its parameters.

A concrete pair. Let the first three rows of $\mat{W}^{(1)}$ be the standard basis of $\R^3$ and the remaining seven be zero. Then $\vec{v} = (0,0,0,1,0,0,0,0,0,0)$ is in the null space, and

$\vec{x} = (1,1,1,0,0,0,0,0,0,0), \qquad \vec{x} + \vec{v} = (1,1,1,1,0,0,0,0,0,0)$

are indistinguishable to the network. Coordinate 4 does not exist as far as the model is concerned.

Why this is not an optimisation failure. No gradient signal can separate the two, because the loss is a function of the output and the outputs are equal. The gradient with respect to every parameter is identical for both. There is nothing for training to fix: a learning rate, a schedule, a longer run and a better initialisation all leave it exactly where it was. The failure is in the architecture, and it is a theorem about matrix rank rather than an empirical difficulty.

The general statement. A layer narrower than its input has already lost a subspace, and no depth after it recovers what was discarded. I.5.T4 is the sharp form: for input dimension $d$ , ReLU networks whose hidden widths are all at most $d$ express a very limited class even in the infinite-depth limit, and width $d + 1$ is exactly the threshold at which universal approximation returns.

Where the same fact is useful. A deliberate bottleneck is how an autoencoder works (I.12): the discarding is the point, and the design question becomes which subspace is discarded rather than whether one is. The difference between a bottleneck and a bug is entirely whether it was chosen.

I.5.X05The bound is reached only in general positionlimit▲▲△

The chapter assumes a layer’s hyperplanes are in general position. Test the assumption: for three ReLU units in the plane, count the regions when the three lines are in general position, when all three are parallel, and when all three meet at a point. Then give weights realising the parallel case and say what a network in that state has lost.

Hint

Draw them. Then check each count against $\binom{3}{0} + \binom{3}{1} + \binom{3}{2}$ .

Solution

General position: 7. Three lines, no two parallel, no three concurrent. Each new line crosses all the previous ones, so line 1 adds 1 region to the plane’s 1, line 2 adds 2, line 3 adds 3: $1 + 1 + 2 + 3 = 7$ . This is the bound (I.5.4) at $n = 3$ , $d = 2$ , and it is attained.

Three parallel lines: 4. Parallel lines cut the plane into strips, and $n$ of them give $n + 1$ strips. Three give 4, against a bound of 7. The arrangement has lost $43\%$ of the regions its width could have bought.

Three concurrent lines: 6. Lines through a common point divide the plane into $2n$ sectors. Three give 6 — one short of the bound, because the three pairwise intersections have collapsed into one.

Weights realising the parallel case. Any $\mat{W}^{(1)}$ whose columns are proportional:

\mat{W}^{(1)} = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{bmatrix}, \qquad \vec{b}^{(1)} = \begin{bmatrix} 0 & -1 & -2 \end{bmatrix}

Every unit’s boundary is a line of slope $-1$ ; only the offsets differ. Note that $\operatorname{rank}(\mat{W}^{(1)}) = 1$ , which is the algebraic statement of the same collapse.

What the network has lost. Three units, four regions — the expressive power of two units in general position, at the parameter cost of three. Worse, the pre-activations are now three scaled copies of a single number $x_1 + x_2$ , so the layer has reduced a two-dimensional input to one dimension and the second coordinate is no longer separable from the first. The failure of I.5.X04 has arrived through degeneracy rather than through narrowness.

Why this matters and why it usually does not. Random initialisation puts the columns in general position with probability one, so a fresh network starts at the bound. Training can move it away — weight decay pulls columns toward each other and dead units remove hyperplanes outright — so the effective region count of a trained network is an empirical quantity, below the bound and sometimes far below. The bound describes what the architecture permits, and I.5.T1’s caution about attainability is exactly this exercise.

I.5.X06Inside a region the gradient is one matrix productgradient▲▲△

For the network of I.5.B01 at $\vec{x} = (1, 2)$ , compute $\partial \hat{y} / \partial \vec{x}$ in closed form from (I.5.3), confirm it against a central difference, and then compute the gradient reaching each column of $\mat{W}^{(1)}$ . Explain the third column’s value.

Hint

On a region the network is $\vec{x}\mat{W}_\star + b_\star$ , so the gradient in $\vec{x}$ is $\mat{W}_\star$ itself (The derivative of a linear map 0.MC.04). For the weight gradients, differentiate the same expression with $\mat{D}$ held fixed.

Solution

Closed form. The pattern at $(1,2)$ is $110$ , so $\mat{D} = \mathrm{diag}(1,1,0)$ and

\frac{\partial \hat{y}}{\partial \vec{x}} = \mat{W}_\star = \mat{W}^{(1)}\mat{D}\,\mat{W}^{(2)} = \begin{bmatrix} 3.0000 & 0.0000 \end{bmatrix}

Central difference. With $h = 10^{-6}$ , the snippet returns $(+3.0000,\ +0.0000)$ . The two agree, which is the point of computing both.

Gradients into $\mat{W}^{(1)}$ . Differentiating $\hat{y} = \sum_j \mathrm{ReLU}(z_j)W^{(2)}_j + b^{(2)}$ with respect to $W^{(1)}_{ij}$ , at fixed pattern:

$\frac{\partial \hat{y}}{\partial W^{(1)}_{ij}} = x_i\,D_{jj}\,W^{(2)}_j$

At $i = 1$ : unit 1 gives $(1)(1)(2) = +2.0000$ , unit 2 gives $(1)(1)(-1) = -1.0000$ , unit 3 gives $(1)(0)(1.5) = +0.0000$ . The snippet’s finite differences return the same three numbers.

Why the third is zero. $D_{33} = 0$ : unit 3 is off at this input, so $\hat{y}$ does not depend on its incoming weights at this input, and the derivative is exactly zero rather than small. Perturbing $W^{(1)}_{13}$ by $10^{-6}$ changes nothing, because the ReLU absorbs it.

Two consequences worth separating.

Locally, this is how backpropagation will look. Chapter I.6 derives it properly, and the shape of the answer — a product of the layer matrices with a diagonal mask between them — is already visible here.

This is not a dead unit. Unit 3 receives no gradient from this example. It receives plenty from $(2, 0)$ , where $z_3 = 1$ . A unit is dead only when the pattern is zero for every example in the dataset (I.3), and a single zero gradient is evidence of nothing.

Where the closed form stops being exact. $\mat{W}_\star$ is the gradient inside the region. On the boundary, where some $z_j = 0$ , ReLU has no derivative and frameworks pick a subgradient by convention — the same kink discussed in I.2.X09. The set where this matters has measure zero, but a finite-difference check that straddles a boundary will disagree with the closed form, and that disagreement is real rather than numerical.

I.5.X07An MLP cannot tell an image from the same pixels shuffledproof▲▲△

Fix a permutation $\pi$ of the input coordinates, applied to every example in a dataset. Prove that the MLP function class is unchanged: for every network $f$ there is a network $f_\pi$ of identical shape with $f_\pi(\pi(\vec{x})) = f(\vec{x})$ for all $\vec{x}$ . Then say what that implies about the first assumption of this chapter, and design the experiment that measures it.

Hint

A permutation of coordinates is a matrix. Ask what happens to $\mat{W}^{(1)}$ alone — no other layer needs to change.

Solution

The proof. Let $\mat{P}_\pi$ be the permutation matrix with $\pi(\vec{x}) = \vec{x}\mat{P}_\pi$ . Given $f$ with first weight matrix $\mat{W}^{(1)}$ , define $f_\pi$ by replacing it with $\mat{P}_\pi^{\mathsf T}\mat{W}^{(1)}$ and leaving every other parameter alone. Then

\pi(\vec{x})\left(\mat{P}_\pi^{\mathsf T}\mat{W}^{(1)}\right) + \vec{b}^{(1)} = \vec{x}\mat{P}_\pi\mat{P}_\pi^{\mathsf T}\mat{W}^{(1)} + \vec{b}^{(1)} = \vec{x}\mat{W}^{(1)} + \vec{b}^{(1)}

The first pre-activation is identical, so every later layer sees identical input and $f_\pi(\pi(\vec{x})) = f(\vec{x})$ . The map $f \mapsto f_\pi$ is a bijection of the class onto itself, so the two classes are the same class, relabelled. $\blacksquare$

What it implies. The architecture has no notion of which input coordinates are near each other. Shuffle every image in a dataset with one fixed permutation and the MLP’s best achievable loss is unchanged, its optimal parameters are a rearrangement of the originals, and its learning curve is the same up to the randomness of initialisation. Spatial structure is information the MLP is constructed not to use.

The experiment. Fix one permutation $\pi$ of the $784$ pixel positions. Train the same MLP twice: on the original images, and on $\pi$ -shuffled images. Then train a small CNN on both. Report four curves.

The prediction the proof licenses is sharp: the MLP’s two curves coincide within seed noise, and the CNN’s do not — the CNN’s shuffled run should be markedly worse. The gap between the CNN’s two curves is the locality prior, measured in the units of the task rather than argued for.

Why this is the right way to state an assumption. The chapter could have said the MLP “ignores spatial structure”, which is vague enough to be unfalsifiable. Stated as invariance under a fixed permutation, it becomes a theorem with a two-line proof and an experiment that would refute it if it were false. Book III returns to this as the laboratory task for Chapter III.1, and the same measurement is what motivates convolution in I.11.

One thing the proof does not say. It concerns a fixed permutation applied to every example. Permuting each example differently destroys the dataset for every architecture, MLP included, because the labels no longer correspond to a consistent function of the input. The invariance is over the choice of coordinate ordering, not over shuffling as an operation.

I.5.X08A dense layer is memory-bound until the batch is largecomplexity▲▲△

For a single dense layer of shape $1024 \times 1024$ in fp32, derive the arithmetic intensity — FLOPs performed per byte of memory moved — as a function of the batch size $B$ . Tabulate it for $B$ from 1 to 1024, and say what the numbers imply about running an MLP one example at a time.

Hint

Count the traffic honestly: the weights are read once per batch, the inputs and outputs scale with $B$ . Then take the limit in $B$ .

Solution

The two counts. A batch of $B$ rows through $\mat{W} \in \R^{d \times d}$ performs $B d^2$ multiply–adds, or $2Bd^2$ FLOPs. The bytes moved, at 4 bytes each, are the weights once plus the input and output rows:

\text{bytes} = 4\left(d^2 + Bd + Bd\right), \qquad \text{intensity}(B) = \frac{2Bd^2}{4\left(d^2 + 2Bd\right)}

The table, at $d = 1024$ :

$B$	FLOP/byte	weights as a share of traffic
1	$0.499$	$99.8\%$
2	$0.996$
8	$3.938$
32	$15.059$	$94.1\%$
128	$51.200$
256	$85.333$	$66.7\%$
1024	$170.667$

The limit. Divide through by $B$ :

$\lim_{B \to \infty} \text{intensity}(B) = \frac{2d^2}{8d} = \frac{d}{4} = 256$

so the intensity rises towards $d/4$ and never passes it. Small $B$ is the regime where the denominator is dominated by $d^2$ , and the intensity is approximately $B/2$ .

What it implies. At $B = 1$ the layer performs one multiply–add per weight and does half a FLOP per byte moved. Accelerators reach their peak arithmetic rate only above roughly $100$ FLOP/byte, so a batch of one leaves the machine idle by more than two orders of magnitude: the time is spent reading weights, not multiplying. The layer is memory-bound, and making the matrix bigger does not help, since the weights grow as fast as the arithmetic.

Three consequences.

Batching is not only a statistical decision. I.4 discusses the batch as a variance choice; this is the other axis, and at $B = 1$ the hardware cost is paid whatever the statistics say.

FLOPs are a poor proxy for time. Two models with the same FLOP count differ by a factor of hundreds if one runs at $B = 1$ and the other at $B = 256$ . I.5.B04’s caution has its arithmetic here.

Single-example inference is the hard case. Serving one request at a time is exactly the memory-bound regime, which is why inference systems batch requests across users, and why the same problem returns for the KV cache in Book IV.

I.5.X09Ten thousand parameters, spent two waysnumeric▲▲△

Input dimension 2, one output, a budget of $10\,000$ parameters. Find the widest single hidden layer that fits, and the widest three hidden layers of equal width that fit. Compare the linear regions each can reach, and then state carefully what the comparison does and does not license.

Hint

Write the parameter count as a function of $w$ in each case — one is linear in $w$ , the other quadratic — and solve. Then apply (I.5.4) and (I.5.5).

Solution

One hidden layer. Parameters $2w + w + w + 1 = 4w + 1 \le 10\,000$ gives $w \le 2499.75$ , so $w = 2499$ and $N = 9997$ .

Three hidden layers of width $w$ .

$2w + w + 2\left(w^2 + w\right) + w + 1 = 2w^2 + 6w + 1 \le 10\,000$

$w \le \frac{-6 + \sqrt{36 + 4 \cdot 2 \cdot 9999}}{4} = \frac{-6 + \sqrt{80\,028}}{4} \approx 69.22$

so $w = 69$ and $N = 9937$ . The quadratic term is what costs the width: the same money buys $2499$ units in one layer or $207$ units in three.

Regions. By (I.5.4), the shallow network reaches at most

$1 + 2499 + \frac{2499 \cdot 2498}{2} = 3\,123\,751$

By (I.5.5) with $\lfloor 69/2 \rfloor = 34$ , the deep one reaches at least

$34^{4} \cdot \left(1 + 69 + \frac{69 \cdot 68}{2}\right) = 1\,336\,336 \cdot 2416 = 3\,228\,587\,776$

A factor of $1034$ , with a tenth of the units and the same budget. And the comparison is conservative in both directions: an upper bound for the shallow network against a lower bound for the deep one.

What this licenses. For a target that genuinely needs many linear pieces, depth is the cheaper way to buy them, and the gap is large enough that no constant factor closes it.

What it does not license. Four things, and the last is the one that decides practice.

Regions are not accuracy. Neither network is being fitted to anything here. The comparison is of what the architectures can express.

The deep bound is a construction. A trained network of that shape realises far fewer regions, and its regions concentrate near the data.

The shallow bound is attainable but not free. Reaching $3.1$ million regions requires $2499$ hyperplanes in general position, which random initialisation provides and training may spoil (I.5.X05).

Trainability was not in the comparison at all. A three-layer network of width $69$ is easy to train; the same argument at depth 50 would give a far larger region count and a network that does not train without residual connections and normalisation. The budget calculation says where the expressivity is; it does not say where the optimum of the whole design problem is.

I.5.X10Capacity is chosen before the data, and both limits say solimit▲▲▲

The third assumption of this chapter is that width is fixed before training and is the same for every example. Examine what it costs by taking two limits: depth to infinity at width $\le d_0$ , and width to infinity at depth 2. Say what each limit gives and what neither gives, and then state precisely what an MLP cannot do that a conditional architecture can.

Hint

The first limit is I.5.T4; the second is I.3.T2. Ask in each case what is being held fixed and what the theorem is silent about.

Solution

Limit one: depth to infinity, width at most $d_0$ . Nothing arrives. Hanin and Sellke show the minimal width for uniform approximation of continuous functions on a compact subset of $\R^{d_0}$ is exactly $d_0 + 1$ ; at width $d_0$ the class stays limited however deep the network is. Depth does not substitute for width below the threshold, and I.5.X04 is the elementary reason — a narrow first layer has already discarded a subspace.

Above the threshold the situation reverses completely: width $d_0 + 1$ suffices, with depth doing all the work. So width is not a smooth resource. It has a hard floor, and above the floor it trades against depth.

Limit two: width to infinity, depth 2. Universality arrives, and nothing else. One hidden layer with a non-polynomial activation approximates any continuous function on a compact set (I.3.T2), with no bound on the number of units, no claim that gradient descent finds them, and no statement about behaviour off the compact set.

What neither limit gives. Both are statements about a network whose shape was chosen in advance. In each, the capacity is a number written down before any data arrived, and the theorem describes what that number permits. Neither says anything about whether the capacity is well spent, and neither can, because spending is a property of training.

What an MLP cannot do. On any single input, the live units are at most $d_1$ , and by I.5.B02 the map applied has rank at most the number of live units. So the arithmetic performed on an easy input and on a hard one costs the same and has the same ceiling. The network can vary which units fire — that is the activation pattern, and it is the only per-input adaptivity an MLP has — but never how many are available. There is no mechanism by which a harder example recruits more capacity.

The architectures that break the assumption. A mixture of experts routes each input to a subset of a much larger parameter pool, so total capacity and per-input cost come apart: the model is large and the computation per token is not. Early-exit networks stop at a shallower layer for easy inputs. Both are answers to precisely the assumption examined here, and both pay for it — with a routing decision that must itself be learned, and a load-balancing problem that does not exist for a dense layer.

The honest summary. Fixed capacity is what makes an MLP simple enough to analyse: every count in this chapter, from (I.5.2) to (I.5.5), assumes it. It is also the first assumption real systems abandon once the parameter count matters more than the analysis does.