Why can a deep narrow network match a shallow wide one using far fewer parameters?
answer
- two knobs, not the same knob
- composition, not just more units
- layer k reuses layer k-1's features
- one kink per shallow unit
- linear pieces double with each layer
basics
~20 sDepth composes. Each layer reuses every feature the layer below it built, so complexity compounds with depth, while a shallow net must build each feature independently from the raw input. For some functions that costs exponentially more units.
solid answer
~50 sWidth and depth both add parameters, but they buy different things. In a shallow net every hidden unit sees only the raw input, so each feature is built from scratch and capacity grows roughly one unit at a time. In a deep net layer k operates on the features layer k-1 produced, so feature complexity compounds through composition. The textbook demonstration is the sawtooth: composing the hat map `g(x) = 2x` below `0.5` and `2 - 2x` above with itself k times gives a function with `2^k` linear pieces, and a depth-k stack with a couple of units per layer computes it. A one-hidden-layer ReLU net over a scalar input adds at most one kink per unit, so it needs about `2^k` units for the same function. Linear in depth versus exponential in width — that is a depth-separation result.
code
python · 15 linesin_dim, out_dim = 256, 10
def mlp_params(widths):
dims = [in_dim] + widths + [out_dim]
return sum(dims[i] * dims[i + 1] + dims[i + 1] for i in range(len(dims) - 1))
deep = mlp_params([256] * 10)
print("deep, 10 hidden layers of 256:", deep) # 660490
w = 1
while mlp_params([w + 1]) <= deep:
w += 1
print("widest single hidden layer on that budget:", w) # 2473
print("one hidden layer of 100000 units costs:", mlp_params([100000])) # 26700010go deeper
Recall that depth and width are two different ways to grow a network, and that stacking layers lets later layers build on earlier features instead of starting from the raw input each time.
Be ready to explain composition concretely and count parameters out loud: fan-in plus fan-out per added wide unit, versus a fixed fan-in repeated per layer. Knowing the sawtooth piece-counting argument is a strong answer here.
Show that you treat the separation as a representation result only, and pair it with the caveats you have actually hit: saturating returns from depth, bottleneck layers destroying information, and optimization being the real constraint.
Own the framing that capacity is not a scalar. Two architectures at the same parameter budget define different hypothesis classes, and the design question is which class plausibly contains your target given the data and the compute you can spend.
## The two knobs A feedforward network can grow in two directions: more units in a layer (width) or more layers (depth). Both raise the parameter count, but at a **fixed budget** they are not interchangeable, and interviewers use this leaf to check whether you understand why. ## First, the arithmetic Between a layer of size `a` and a layer of size `b`, a fully connected map costs `a*b` weights plus `b` biases. Take a 256-dimensional input and 10 outputs. A trunk of 10 hidden layers of width 256 costs `10 * (256*256 + 256) + (256*10 + 10) = 660,490` parameters. Spend the same budget on a single hidden layer and each added unit costs 256 incoming weights, 1 bias and 10 outgoing weights — 267 parameters — so the budget buys only about 2,473 units. A single hidden layer of 100,000 units would cost about 26.7 million parameters, roughly forty times the deep trunk. That already says something: width charges you full fan-in plus full fan-out for every unit you add, while depth reuses the same modest fan-in over and over. ## The real reason is composition The arithmetic is a symptom; composition is the cause. In a one-hidden-layer network every unit is a function of the **raw input coordinates**. If the target depends on some intermediate concept, every unit that needs that concept must rediscover it from scratch, in parallel. In a deep network layer k is a function of the features layer k-1 already produced, so a feature built once is reused by everything above it. Complexity can therefore **multiply** layer by layer instead of **adding** unit by unit. ## A concrete separation Define the hat map on `[0,1]`: `g(x) = 2x` for `x <= 0.5` and `g(x) = 2 - 2x` above. Two ReLU units implement `g` exactly. Composing `g` with itself k times gives a sawtooth with `2^k` linear pieces, and a depth-k network with a handful of units per layer computes it with O(k) parameters. Now count what a shallow net can express. With a scalar input, a one-hidden-layer ReLU network is `sum_i a_i * relu(w_i * x + b_i) + c`; each unit contributes at most one breakpoint, at `x = -b_i / w_i`. So a width-m shallow network is piecewise linear with **at most m+1 pieces**. To reproduce a depth-k sawtooth it needs `m >= 2^k - 1` units. Linear in depth, exponential in width. Analogous statements are classical in Boolean circuit complexity, where parity is the standard example of a function that constant-depth circuits need exponential size to compute. ## What the separation does and does not claim It is a statement about **representation**: there exists a function depth expresses cheaply and width cannot. It does not claim your target function is of that kind, that gradient descent will actually find the deep solution, or that stacking layers always improves a real model. Expressivity is necessary, not sufficient. Whether a deep stack is *trainable* is a separate concern with its own machinery, and it is not what this question is testing. ## Capacity and the hypothesis class A hypothesis class is the set of functions an architecture can realise as its weights vary. Depth and width at a matched budget carve out **different** classes; neither is a subset of the other in general. So "more capacity" is not a single number you can read off the parameter count — two models with 660,490 parameters each can contain very different function sets, and the useful question is which class contains something close to your target. ## Depth is not free capacity A deeper stack only contains everything the shallower one does if each added layer can pass its input through unchanged. A layer narrower than the information it must carry is a **bottleneck**: put a width-2 layer in the middle of a deep trunk and no later layer can recover what it destroyed. The honest claim is therefore *depth at a sensible width*, not depth at any width. Empirically, the gains from depth also saturate — the tenth layer typically buys much less than the third. ## What to say in an interview Say composition and reuse, back it with the sawtooth counting argument, quote the parameter arithmetic to show width is charged per unit at full fan-in and fan-out, and then volunteer the caveat: this is a representation result, real gains still depend on optimization and on the data.
- Does adding another layer always enlarge what a network can represent?Only if the added layer can pass its input through, at least approximately. A plain layer that is wide enough can come close to an identity map, so the deeper class roughly contains the shallower one. A layer narrower than the information it must carry is a bottleneck instead, and it removes functions the shallower network had. Depth enlarges the class only when width keeps up.
- If depth is so parameter-efficient, why not just keep stacking layers?Because expressivity is not trainability or throughput. A deep stack is harder to optimize, its forward pass is sequential so latency grows with depth, and empirical gains saturate — each extra layer buys less than the one before. The separation result guarantees that some functions favour depth, not that your function does.
- Why does depth stop helping if you remove the nonlinearity between layers?Because a composition of linear maps is itself a single linear map. Ten stacked linear layers collapse to one matrix product, so the hypothesis class is exactly that of a one-layer linear model regardless of depth. Depth only compounds expressivity when a nonlinearity sits between the layers; the extra parameters otherwise just re-parameterise the same function.
A shallow net is a workshop where every worker builds a whole product from raw stock. A deep net is an assembly line where each station reuses the part the station before it made.
saying these in an interview costs you the question
- Says depth is just a way of having more parameters
- Claims a wide enough single layer makes depth pointless in practice
- Treats capacity as a single number read off the parameter count
- Thinks the depth-separation result proves deeper always wins on real data
- Believes stacking layers without a nonlinearity still adds expressivity