Module 1 · Reading 1.2 · read before S02: From Linear Models to MLPs

The PDF posted in Canvas is the assigned version of this reading. It is built from this page, so the text is identical; anything here marked as deep reading is optional and is not in the PDF.

You already know linear models: weighted sums, a threshold or a sigmoid on top, trained to separate classes or fit a line. This section is about the two-step move that turns them into neural networks (insert a nonlinearity, then stack) and about why each step is necessary. Skip the nonlinearity and a ten-layer network collapses into the linear model you started with. Skip the stacking and you keep the perceptron’s blind spots. Together they produce the multilayer perceptron (MLP), the architecture underneath everything else in this course: CNNs are MLPs with shared weights, and in a standard Transformer block with a 4x-expanded feed-forward sublayer, the MLP holds roughly two-thirds of the block’s non-embedding parameters.

We build up in historical order (perceptron, activation functions, hidden layers) because the history is a sequence of failures that each next idea repaired, and you will hit miniature versions of the same failures in your own training runs.

How to read this

The perceptron and its learning rule

Frank Rosenblatt’s perceptron (1958) is a linear classifier with labels \(y\) in \(\{-1, +1\}\):

\[\hat{y} = \operatorname{sign}(\mathbf{w}^\top \mathbf{x} + b)\]

Its learning rule is startlingly simple. Visit the training examples one at a time; when the model classifies one wrong (or lands exactly on the boundary), add \(y_i\, \mathbf{x}_i\) to the weights and \(y_i\) to the bias; otherwise do nothing. Each update tilts the decision boundary toward the misclassified point. The perceptron convergence theorem, proved in the early 1960s, guarantees that if any linear boundary separates the data with some margin, this procedure finds a separating boundary after finitely many mistakes — one of the first learning guarantees ever proved.

The theorem’s standard form (usually credited to Albert Novikoff’s 1962 proof) is worth knowing because of what controls the bound: if every example lies within radius \(R\) of the origin and some separator classifies everything correctly with margin at least \(\gamma\) (that is, no point comes closer than \(\gamma\) to the boundary), then the total number of mistakes ever made is at most \((R/\gamma)^2\). Nothing in the bound mentions the number of examples or the dimension: only the geometry. Wide margins mean fast learning; barely-separable data can force enormous mistake counts even in two dimensions. That “margin” quantity went on to have a distinguished later career: maximizing it is exactly the idea behind support vector machines, the method that outcompeted neural networks through the 1990s.

The guarantee has a sharp edge, though: if no separating line exists, the rule never settles. It cycles forever, permanently oscillating between wrong answers. Here is both behaviors in one script: a separable two-blob dataset, and the four XOR points from section 1.1:

import numpy as np

np.random.seed(0)

def train_perceptron(X, y, epochs=50):
    """Rosenblatt's rule: on each mistake, add y_i * x_i to the weights.

    y must be in {-1, +1}. Returns mistakes made in each epoch.
    """
    w = np.zeros(X.shape[1])
    b = 0.0
    history = []
    for epoch in range(epochs):
        mistakes = 0
        for xi, yi in zip(X, y):
            if yi * (w @ xi + b) <= 0:      # wrong side (or on) the boundary
                w += yi * xi
                b += yi
                mistakes += 1
        history.append(mistakes)
        if mistakes == 0:
            break
    return w, b, history

# Dataset 1: linearly separable — two blobs with a gap between them
X_sep = np.vstack([np.random.randn(50, 2) + [2, 2],
                   np.random.randn(50, 2) + [-2, -2]])
y_sep = np.array([1] * 50 + [-1] * 50)

# Dataset 2: XOR — four points no line can split correctly
X_xor = np.array([[1, 1], [-1, -1], [1, -1], [-1, 1]], dtype=float)
y_xor = np.array([-1, -1, 1, 1])

w, b, hist = train_perceptron(X_sep, y_sep)
print(f"separable data: mistakes per epoch = {hist}")
print(f"separable data: converged after {len(hist)} epochs, w = {w}, b = {b}")

w, b, hist = train_perceptron(X_xor, y_xor, epochs=1000)
print(f"XOR data: ran {len(hist)} epochs, mistakes in the last 5 epochs = {hist[-5:]}")

Running this prints:

separable data: mistakes per epoch = [2, 0]
separable data: converged after 2 epochs, w = [3.6008164  3.06362926], b = 0.0
XOR data: ran 1000 epochs, mistakes in the last 5 epochs = [4, 4, 4, 4, 4]

On the separable blobs, two mistakes total and done. On XOR, after a thousand epochs the perceptron is still misclassifying all four points every pass — not because training is too short, but because the thing it is searching for does not exist. Minsky and Papert’s 1969 book Perceptrons made this class of limitation rigorous, and the field’s momentum stalled with it.

Historical note. Minsky and Papert’s analysis targeted single-layer perceptrons, and researchers at the time knew that multilayer networks were more expressive — the problem was that Rosenblatt’s mistake-driven rule gives no way to assign credit to hidden units, whose “correct” outputs nobody knows. The missing ingredient was not the architecture but a training algorithm for it. That gap stood for roughly seventeen years, until backpropagation’s popularization in 1986, which is why this course spends two full sessions on it (the S04 and S05 readings).

People. Frank Rosenblatt was not a computer scientist — he was a psychologist at the Cornell Aeronautical Laboratory, and he saw the perceptron as a model of biological learning as much as a computing device. He and Minsky had debated the potential of neural networks publicly for years. Rosenblatt died in a boating accident in 1971, two years after Perceptrons appeared, and did not live to see the vindication of the multilayer networks he had already been experimenting with.

Adaline and the delta rule: learning as descent

The perceptron was not the only learning machine of its era, and its closest sibling turned out to be the more prophetic one. In 1960, Bernard Widrow and his student Marcian “Ted” Hoff at Stanford built Adaline (adaptive linear neuron), presented in a paper titled “Adaptive Switching Circuits.” Architecturally it is almost the same model — a weighted sum with a threshold on top. The difference is entirely in how it learns. Rosenblatt’s rule reacts to classification mistakes and does nothing otherwise. The Widrow–Hoff rule, also called the delta rule or least mean squares (LMS), instead measures the squared error between the pre-threshold weighted sum and the target, and adjusts every weight a little bit in proportion to how much it would reduce that error, on every example, mistake or not.

Said in modern vocabulary: Adaline is trained by stochastic gradient descent on a differentiable loss. That is precisely the recipe that section 1.3 presents as the foundation of all of deep learning — proposed in 1960, twenty-six years before backpropagation made it work for hidden layers. The delta rule also escaped the perceptron’s cycling pathology: on non-separable data it does not oscillate forever but settles toward the least-bad linear fit, because it is descending a well-defined loss surface rather than chasing mistakes. LMS itself became one of the most deployed algorithms in engineering history, as the core of adaptive filters in echo cancellation and signal processing: decades of quiet industrial service while its intellectual descendants waited for their moment.

People. Ted Hoff’s later career is a reminder of how small this world was: after the Adaline work at Stanford, he joined a young company called Intel, where he became one of the inventors of the first commercial microprocessor, the Intel 4004 (1971). One of the people behind the learning rule that grew into deep learning’s optimizer also helped create the hardware lineage that would eventually train it. Widrow remained at Stanford and continued working on adaptive signal processing for the rest of his career.

The conceptual gap between the two 1960-era rules (fix mistakes versus descend a loss) is worth sitting with, because the loss-descent view won completely. Every optimizer in this course, from plain SGD to AdamW, is the delta rule’s descendant; the perceptron rule survives mainly as a theorem in learning theory courses.

Why stacking linear layers is not enough

The obvious fix for limited capacity is to compose models: feed the output of one linear layer into another. But composition of linear maps is linear. If \(h = W_1 x + b_1\) and \(\hat{y} = W_2 h + b_2\), then

\[\hat{y} = (W_2 W_1)\, x + (W_2 b_1 + b_2)\]

which is a single linear layer with weight matrix \(W_2 W_1\). Stack a hundred linear layers and the resulting function is still a line; the XOR failure survives intact. Depth does nothing until you insert something nonlinear between the layers.

The algebra above is a two-layer argument; it is worth watching the claim hold for a ten-layer stack, with the collapse computed explicitly:

import numpy as np

np.random.seed(0)

# Ten linear layers, no activations, random weights
sizes = [4, 16, 16, 16, 16, 16, 16, 16, 16, 16, 3]
Ws = [0.5 * np.random.randn(a, b) for a, b in zip(sizes[:-1], sizes[1:])]
bs = [0.1 * np.random.randn(b) for b in sizes[1:]]

def deep_linear(X):
    h = X
    for W, b in zip(Ws, bs):
        h = h @ W + b
    return h

# Collapse the whole stack into a single (W_eff, b_eff) by composing the maps
W_eff = np.eye(sizes[0])
b_eff = np.zeros(sizes[0])
for W, b in zip(Ws, bs):
    W_eff = W_eff @ W
    b_eff = b_eff @ W + b

X = np.random.randn(100, 4)
out_deep = deep_linear(X)
out_flat = X @ W_eff + b_eff
print(f"10-layer output shape: {out_deep.shape}, single-layer W_eff shape: {W_eff.shape}")
print(f"max |difference| between 10 layers and 1 layer: {np.max(np.abs(out_deep - out_flat)):.2e}")

total_params = sum(W.size + b.size for W, b in zip(Ws, bs))
print(f"parameters in the stack: {total_params}, in the collapsed layer: {W_eff.size + b_eff.size}")

Running this prints:

10-layer output shape: (100, 3), single-layer W_eff shape: (4, 3)
max |difference| between 10 layers and 1 layer: 1.14e-12
parameters in the stack: 2307, in the collapsed layer: 15

Ten layers, 2,307 parameters — and a 15-parameter linear map reproduces every output to within floating-point noise (1e-12). The 2,292 extra parameters buy exactly nothing: the stack cannot represent a single function that the one layer cannot. This is also a practical bug you will someday write: forget the activation between two nn.Linear layers in PyTorch and the model silently degrades to this collapsed form, trains without error messages, and performs like logistic regression. Nothing in the framework warns you, because nothing is wrong: the model is just linear.

That something-nonlinear is the activation function: an elementwise nonlinear function applied to each hidden unit’s pre-activation \(z = \mathbf{w}^\top \mathbf{x} + b\). With activations, the network

\[h = f(W_1 x + b_1), \qquad \hat{y} = W_2 h + b_2\]

is no longer collapsible, and its expressive power grows with width and depth rather than staying stuck at “a line.”

Activation functions: sigmoid, tanh, ReLU

Three activations carry most of the field’s history.

Sigmoid, \(\operatorname{sigmoid}(z) = 1/(1 + e^{-z})\), squashes its input into \((0, 1)\). It is smooth and interpretable as a probability, which makes it the standard output unit for binary classification to this day. As a hidden activation it dominated the 1980s and 1990s, partly by analogy to neuron firing rates.

Tanh, \(\tanh(z)\), is a rescaled sigmoid with range \((-1, 1)\). Being zero-centered, it generally trains a bit better than sigmoid in hidden layers and largely displaced it there.

ReLU (rectified linear unit), \(\operatorname{relu}(z) = \max(0, z)\), is not even differentiable at zero, and it discards all information about how negative its input is. It also became the default hidden activation of the deep learning era. Rectifying units have a long prehistory in neuroscience-inspired models, but their takeover of mainstream deep learning came around 2010–2011, through work by Nair and Hinton and by Glorot, Bordes, and Bengio showing that deep rectifier networks train faster and often better than their sigmoid/tanh counterparts. AlexNet (2012) used ReLU and credited it with a large training speedup, and the field followed.

Why does such a crude function win? Look at the derivatives. Backpropagation multiplies one local derivative per layer along the path from the loss to a weight, so what matters for deep networks is how these derivatives behave, especially far from zero, where units saturate:

import numpy as np

np.random.seed(0)

def sigmoid(z): return 1 / (1 + np.exp(-z))

def d_sigmoid(z): s = sigmoid(z); return s * (1 - s)

def d_tanh(z): return 1 - np.tanh(z) ** 2

def d_relu(z): return np.asarray(z > 0, dtype=float)

print("z      d_sigmoid  d_tanh   d_relu")
for z in [0.0, 2.0, 5.0, 10.0]:
    print(f"{z:>4.1f}   {d_sigmoid(z):8.4f}  {d_tanh(z):7.4f}  {d_relu(z):6.1f}")

# What saturation does to a deep chain of gradients: multiply 20 layer-local
# derivatives together, using typical pre-activation values ~N(0, 1.5^2)
z = 1.5 * np.random.randn(20)
print(f"\nproduct of 20 sigmoid derivatives: {np.prod(d_sigmoid(z)):.2e}")
print(f"product of 20 tanh derivatives:    {np.prod(d_tanh(z)):.2e}")
print(f"product of 20 relu derivatives:    {np.prod(d_relu(z)):.2e}")

Running this prints:

z      d_sigmoid  d_tanh   d_relu
 0.0     0.2500   1.0000     0.0
 2.0     0.1050   0.0707     1.0
 5.0     0.0066   0.0002     1.0
10.0     0.0000   0.0000     1.0

product of 20 sigmoid derivatives: 5.77e-17
product of 20 tanh derivatives:    3.41e-13
product of 20 relu derivatives:    0.00e+00

The table tells the story of the vanishing gradient. Sigmoid’s derivative never exceeds 0.25 and dies exponentially fast away from zero; multiply twenty such factors and the product is around 1e-17. Tanh is better but still saturates. Along an active positive path, ReLU’s local activation derivative is exactly 1, so that factor alone does not shrink the gradient; weight matrices and inactive paths still determine the end-to-end gradient through a deep network.

The third line of the product experiment shows ReLU’s price: its derivative for negative inputs is exactly 0, so this particular single chain (where about half the twenty values are negative) is blocked completely. In a real network each weight sits on many paths through many units, so gradient still flows as long as some paths are active; but a unit whose pre-activation is negative for every training input learns nothing at all. Such dead ReLUs are a real failure mode, usually caused by too-large learning rates or bad initialization, and they motivate variants like leaky ReLU and GELU that leave a small slope on the negative side. (At \(z = 0\) exactly, ReLU has no derivative; implementations pick a convention, and ours uses 0; the choice does not matter in practice, as section 1.4 discusses.)

One distinction to keep firm: everything above concerns hidden activations. At the output, choose the representation and loss together. Binary and multiclass classification are usually implemented as raw logits passed to a numerically fused cross-entropy loss; sigmoid or softmax is then applied when probabilities are needed. APIs that explicitly expect probabilities are also valid, provided the convention is matched. Unbounded regression usually ends in no activation at all, while bounded or positive targets may justify a task-specific transform. A recurring mistake is a ReLU at the end of an unbounded regression network, which then cannot predict negative values. Saturation in an explicit probability output need not kill learning when it is paired with a stable fused loss; mismatching the output convention and loss will.

Watching gradients vanish in a real network

The 20-factor product above is a caricature — one path, hand-picked pre-activation scale. The honest version of the experiment is to build an actual deep network, run a real forward and backward pass, and measure how large the gradient is at each depth. Here is a 12-layer MLP under three different hidden activations, using PyTorch’s autograd (which section 1.4 demystifies) and its default initialization:

import torch
import torch.nn as nn

torch.manual_seed(0)

def make_net(act, depth=12, width=64):
    layers = [nn.Linear(2, width), act()]
    for _ in range(depth - 2):
        layers += [nn.Linear(width, width), act()]
    layers += [nn.Linear(width, 1)]
    return nn.Sequential(*layers)

X = torch.randn(256, 2)
y = torch.randn(256, 1)

print("gradient norm of the weight matrix at each depth (12 linear layers):")
print(f"{'':>9} {'layer 1':>9} {'layer 4':>9} {'layer 8':>9} {'layer 12':>9}   ratio 1/12")
for name, act in [("sigmoid", nn.Sigmoid), ("tanh", nn.Tanh), ("relu", nn.ReLU)]:
    torch.manual_seed(0)
    net = make_net(act)
    loss = ((net(X) - y) ** 2).mean()
    loss.backward()
    linears = [m for m in net if isinstance(m, nn.Linear)]
    g = [linears[i].weight.grad.norm().item() for i in (0, 3, 7, 11)]
    print(f"{name:>8}: {g[0]:9.2e} {g[1]:9.2e} {g[2]:9.2e} {g[3]:9.2e}   {g[0] / g[3]:.1e}")

Running this prints:

gradient norm of the weight matrix at each depth (12 linear layers):
            layer 1   layer 4   layer 8  layer 12   ratio 1/12
 sigmoid:  3.21e-11  1.22e-07  2.69e-04  5.92e-01   5.4e-11
    tanh:  1.19e-04  4.25e-04  1.53e-03  1.17e-02   1.0e-02
    relu:  9.15e-06  5.32e-05  1.45e-03  4.74e-02   1.9e-04

Read each row from right to left — from the output layer back toward the input, the direction gradient actually flows. The sigmoid network is the catastrophe the theory predicts: the first layer’s gradient is ten billion times smaller than the last layer’s. Under gradient descent, layer 12 learns at full speed while layer 1 is effectively frozen; the network is deep on paper and shallow in practice. This is not an exotic failure: it is what training deep sigmoid networks in 1990 was actually like, and it is a large part of why “deep” did not work for twenty years.

Two honest observations complicate the clean story. First, tanh survives respectably here (ratio 1e-2): its derivative reaches 1.0 at zero, and at this depth with small inputs it has not yet saturated; tanh networks of moderate depth were genuinely trainable in the 1990s, which is why LeNet-era networks used tanh-like units. Second, even the ReLU network’s gradients shrink noticeably (ratio 1.9e-4) — because passing gradient through undiminished requires not just a good activation but weight matrices that neither shrink nor amplify signals on average. That is a property of initialization, and PyTorch’s defaults are not tuned for a 12-layer sigmoid-or-otherwise stack. Getting this right, and what “right” means, is the business of section 1.7, where this exact experiment reappears with variance-matched initializations. The activation function is necessary, not sufficient.

Hidden layers and what they compute

An MLP with one hidden layer computes \(\hat{y} = W_2\, f(W_1 x + b_1) + b_2\). A useful way to read this: each hidden unit \(j\) is itself a little linear classifier \(f(\mathbf{w}_j^\top \mathbf{x} + b_j)\), carving the input space with its own hyperplane; the output layer is a linear model over those \(H\) carvings. The hidden layer re-represents the input as “which side of each of these \(H\) learned boundaries are you on, and by how much” — and in that representation, problems like XOR become linearly separable (you saw this happen in section 1.1, where a width-8 hidden layer took XOR accuracy from 52% to 100%).

For XOR concretely, two hidden ReLU units suffice: one unit that activates for “both inputs high,” one for “both inputs low,” and an output that fires when neither is active. The network learns conjunctions, then combines them — a tiny instance of the compositional story from section 1.1.

With ReLU activations there is an even more concrete geometric picture: every function a ReLU MLP computes is piecewise linear — flat facets joined at creases, one crease direction contributed per hidden unit. More units, more creases, finer approximation. That intuition suggests a network can approximate any reasonable function if it is wide enough, which is in fact a theorem.

Stacking a second hidden layer changes the geometry in kind, not just in degree. The second layer’s units draw their hyperplanes in the representation produced by the first layer — and a straight boundary in that learned space maps back to a bent, folded boundary in the input space. Each layer of depth lets the network fold the input space before the next layer cuts it, so a cut made once can count many times. This folding picture is worth carrying forward: it is the intuitive content of the depth-separation results in Going deeper, and it previews why the deep networks of later chapters build their features stage by stage (edges into textures into parts into objects) rather than all at once in one enormous layer.

Universal approximation, informally — and why it is not enough

The universal approximation theorem, proved independently in 1989 by George Cybenko (for sigmoid activations) and by Hornik, Stinchcombe, and White (for broad classes of activations), says informally: a feedforward network with one hidden layer can approximate any continuous function on a bounded region to any desired accuracy, provided the hidden layer may be as wide as needed.

Rather than prove it, we can watch it happen. Take a wiggly 1-D target function and approximate it with one hidden layer of ReLU units whose “kinks” are spread across the interval; fit only the output layer by least squares, and double the width repeatedly:

import numpy as np

np.random.seed(0)

# Target: a wiggly 1-D function on [0, 1]
x = np.linspace(0, 1, 500)
target = np.sin(2 * np.pi * x) + 0.5 * np.sin(6 * np.pi * x)

def fit_relu_net(width):
    """One hidden layer of `width` ReLU units with random slopes and evenly
    spaced 'kinks'; only the output layer is fit (by least squares)."""
    kinks = np.linspace(0, 1, width, endpoint=False)          # where each ReLU bends
    H = np.maximum(0.0, x[:, None] - kinks[None, :])          # (500, width) hidden features
    H = np.hstack([H, np.ones((len(x), 1))])                  # bias column
    coef, *_ = np.linalg.lstsq(H, target)
    return H @ coef

for width in [2, 4, 8, 16, 32, 64]:
    pred = fit_relu_net(width)
    print(f"width {width:>3}: max |error| = {np.max(np.abs(pred - target)):.4f}")

Running this prints:

width   2: max |error| = 1.1074
width   4: max |error| = 0.6698
width   8: max |error| = 0.2268
width  16: max |error| = 0.0567
width  32: max |error| = 0.0148
width  64: max |error| = 0.0038

Each doubling of width cuts the worst-case error by roughly a factor of four once the network has enough kinks to see the target’s wiggles (0.0567 to 0.0148 to 0.0038). That factor is no accident: a ReLU network with evenly spaced kinks is a piecewise-linear approximator, and piecewise-linear approximation of a smooth curve has error shrinking with the square of the segment count. The demonstration matches the theorem’s promise (any accuracy you name, some width delivers) while exposing what the theorem leaves out: you pay for every digit of accuracy with more units, and for less tidy targets (high-frequency, high-dimensional) the required width can grow at ruinous rates.

That points at the three honest caveats. First, universal approximation is an existence statement — good weights exist, but the theorem says nothing about whether gradient descent finds them. Second, it says nothing about generalization: a wide-enough network can also fit noise perfectly. Third, one wide-enough layer can be exponentially wasteful: there are functions that a deep network expresses with polynomially many units but that provably require exponentially many in any single hidden layer. Depth buys efficiency of representation, not raw possibility; that is the modern answer to “why deep and not just wide?”

The width cost also explodes with input dimension, and the arithmetic is sobering. Our 1-D experiment needed roughly one kink per resolved wiggle. A generic function of \(d\) inputs, resolved to 10 distinct values per axis, has on the order of \(10^d\) regions to get right: at \(d = 2\) that is a hundred units (fine); at \(d = 20\) it is \(10^{20}\) (impossible), and 20 is a small input dimension by deep learning standards (a 28×28 grayscale image has 784). This is the curse of dimensionality, and it explains why “wide enough exists” is cold comfort. Real high-dimensional data escapes the curse only because it is not generic — natural images, audio, and text concentrate near much lower-dimensional structure, and compositional models can exploit that structure with far fewer units than the worst case demands. Deep learning’s empirical success is, in part, a bet that real data has this exploitable structure. The bet usually pays; the theorem never promised it would.

Pitfall. The universal approximation theorem is the most misquoted result in deep learning. It does not say “a neural network can learn anything,” and citing it as a reason your model will work is a category error: your model’s failure modes are optimization and generalization, and the theorem addresses neither. When you want to argue a network can fit your data, the useful check is empirical: overfit a small subset. Ten minutes of experiment beats a theorem that was never about training.

Going deeper

The claim that depth is exponentially more efficient than width has a family of precise theorems behind it, and one of them fits in twenty lines of NumPy. Consider the tent map: the function on \([0, 1]\) that rises linearly from 0 to 1 over the left half and falls back to 0 over the right half. It is exactly representable with two ReLU units: tent(x) = 2*relu(x) - 4*relu(x - 0.5). Now compose it with itself. Each composition folds the interval in half, doubling the number of oscillations: two applications give 4 linear pieces, three give 8, and \(k\) applications give \(2^k\) pieces while using only \(2k\) ReLU units arranged in \(k\) layers:

import numpy as np

np.random.seed(0)

def tent(x):
    """The tent map on [0, 1] -- exactly two ReLU units: 2*relu(x) - 4*relu(x - 0.5)."""
    return 2 * np.maximum(0.0, x) - 4 * np.maximum(0.0, x - 0.5)

x = np.linspace(0.0, 1.0, 100001)
f = x.copy()
for depth in range(1, 11):
    f = tent(f)                                  # compose one more layer
    slopes = np.sign(np.diff(f))                 # slope sign on each tiny interval
    pieces = 1 + int(np.sum(slopes[1:] != slopes[:-1]))
    if depth in (1, 2, 3, 5, 8, 10):
        print(f"depth {depth:>2} ({2 * depth:>2} ReLU units total): {pieces:>5} linear pieces")

Running this prints:

depth  1 ( 2 ReLU units total):     2 linear pieces
depth  2 ( 4 ReLU units total):     4 linear pieces
depth  3 ( 6 ReLU units total):     8 linear pieces
depth  5 (10 ReLU units total):    32 linear pieces
depth  8 (16 ReLU units total):   256 linear pieces
depth 10 (20 ReLU units total):  1024 linear pieces

Twenty units in ten layers produce a function with 1,024 linear pieces. Now recall from the width experiment that a one-hidden-layer ReLU network contributes one kink per unit: representing a function with 1,024 pieces in a single hidden layer needs on the order of a thousand units (fifty times more), and every additional layer of depth doubles the gap. Depth lets the network reuse computation: each layer folds the space, and later layers operate on all the folds at once. Width can only add creases one at a time.

This demonstration is the intuition behind a cluster of real theorems. Telgarsky (COLT 2016) proved the sawtooth construction into a general separation: there are functions computable by deep networks with few units per layer such that any shallow network approximating them needs exponentially many units. Eldan and Shamir (COLT 2016) showed a separation of striking sharpness — a natural function on \(\mathbb{R}^d\) expressible by a small 3-layer network that no 2-layer network can approximate without width exponential in the dimension \(d\); even one extra layer can be exponentially valuable. Earlier, Montufar, Pascanu, Cho, and Bengio (NeurIPS 2014) counted linear regions directly, showing the number of regions a ReLU network can carve grows exponentially with depth but only polynomially with width. Together these results turn “deep is efficient” from folklore into mathematics, with the standard caveat that they concern representation; whether gradient descent finds these efficient deep solutions is a separate and still partly open question.

A caution before you conclude “always maximize depth”: the separation theorems say deep representations exist, not that they are reachable. The tent-map weights above were constructed by hand; asking gradient descent to discover a 50-layer folding from data runs directly into the vanishing-gradient measurements earlier in this section, and very deep plain MLPs are notoriously hard to train. The architectures that made real depth practical (normalization layers and, above all, the residual connections of section 2.2) are engineering answers to exactly this gap between what depth can represent and what optimization can find. In practice, depth is chosen by validation performance under a compute budget, not by expressivity theorems.

On the activation side, the modern frontier has moved past ReLU without abandoning its lesson. GELU (Gaussian error linear unit, proposed by Hendrycks and Gimpel in 2016) smoothly gates inputs by their magnitude: it approaches the identity for large positive inputs and approaches zero for large negative inputs, with a smooth transition through zero. BERT and GPT-2 used GELU, while many newer language models use gated SiLU/SwiGLU feed-forward layers instead. Leaky ReLU handles dead units more directly with a fixed small negative slope. None of these choices changes the section’s core logic (they are all inexpensive nonlinearities with usable derivatives), and in practice the difference between reasonable choices is usually smaller than the difference between a suitable one and a saturating one. A safe default is ReLU for a plain MLP and the activation specified by the architecture you are reproducing.

Common pitfalls

  • Symptom: your “deep” network performs exactly like logistic regression. Cause: missing activation functions — stacked linear layers collapse into one, as the ten-layer experiment shows. Fix: check that a nonlinearity sits between every pair of linear layers; in PyTorch, print the model and look.
  • Symptom: training loss decreases at first, then a growing fraction of hidden units output zero for every input, and learning stalls. Cause: dead ReLUs — units pushed into the always-negative regime by large updates. Fix: lower the learning rate, use sensible initialization (section 1.7), or switch to leaky ReLU/GELU.
  • Symptom: a deep sigmoid/tanh network trains its last layers but the early layers barely move. Cause: vanishing gradients — products of sub-1 saturation derivatives, as in our 12-layer measurement (a 5e-11 front-to-back ratio). Fix: ReLU-family activations, careful initialization, and (later in the course) normalization layers and residual connections.
  • Symptom: perceptron-style training never converges no matter the number of epochs. Cause: the data is not linearly separable; the convergence theorem’s precondition fails. Fix: add features or hidden layers, or switch to a loss-based method (logistic regression) that at least converges to the best available linear model.

Try it yourself

  1. Modify the perceptron script to record the weight vector after each epoch on the XOR data. Does it cycle through a repeating sequence? How long is the cycle?
  2. Hand-construct a 2-hidden-unit ReLU network that computes XOR on the four points \((\pm 1, \pm 1)\) (choose W1, b1, w2, b2 yourself, no training), and verify it in NumPy.
  3. In the width experiment, replace the ReLU features with tanh((x - kinks) * 10) features. How does max error scale with width now? What happens with the multiplier at 1 instead of 10?
  4. Continue the width experiment to widths 128, 256, and 512 (increase the sample grid to 5000 points so the measurement stays honest). Does the factor-of-four-per-doubling trend continue? At what width does float64 arithmetic start to matter?
  5. In the gradient-norm experiment, increase depth from 12 to 24 and rerun. Which activation’s front-layer gradient degrades fastest? Then replace nn.ReLU with nn.GELU and compare.
  6. Implement the delta rule (gradient descent on squared error of the pre-threshold sum) for the XOR points, and confirm that unlike the perceptron rule it converges — to weights near zero. Explain why “converges to the least-bad linear fit” and “solves the problem” are different claims.

Further reading

  • Cybenko, “Approximation by superpositions of a sigmoidal function,” Mathematics of Control, Signals and Systems, 1989 — the original universal approximation result for sigmoid networks. springer.com
  • Hornik, Stinchcombe & White, “Multilayer feedforward networks are universal approximators,” Neural Networks, 1989 — the companion result extending universal approximation to general activations. sciencedirect.com
  • Glorot, Bordes & Bengio, “Deep Sparse Rectifier Neural Networks,” AISTATS 2011 — the empirical case that made ReLU the deep learning default. proceedings.mlr.press
  • Nair & Hinton, “Rectified Linear Units Improve Restricted Boltzmann Machines,” ICML 2010 — rectified units’ first modern mainstream appearance. cs.toronto.edu
  • Telgarsky, “Benefits of depth in neural networks,” COLT 2016 — the sawtooth depth-separation theorem behind our tent-map experiment. proceedings.mlr.press
  • Eldan & Shamir, “The Power of Depth for Feedforward Neural Networks,” COLT 2016 — one extra layer can be exponentially more valuable than any amount of width. arxiv.org/abs/1512.03965
  • Montufar, Pascanu, Cho & Bengio, “On the Number of Linear Regions of Deep Neural Networks,” NeurIPS 2014 — counting the regions ReLU networks carve, and how depth multiplies them. arxiv.org/abs/1402.1869
  • Hendrycks & Gimpel, “Gaussian Error Linear Units (GELUs),” 2016 — the smooth ReLU relative that Transformers adopted. arxiv.org/abs/1606.08415
  • Dive into Deep Learning, Chapter 5 (Multilayer Perceptrons) — the same material with runnable PyTorch notebooks. d2l.ai

Before class you should be able to

  • State what the perceptron convergence theorem guarantees, which geometric quantities control the bound, and what happens on non-separable data.
  • Explain why a stack of linear layers collapses into a single linear map, and recognize the missing-activation bug in a model definition.
  • Compare the derivatives of sigmoid, tanh, and ReLU, and explain vanishing gradients as a product of per-layer factors.
  • Describe dead ReLUs — cause, symptom, and the standard fixes.
  • Distinguish hidden activations (a design choice) from output activations (dictated by the task and its loss).
  • Say what the universal approximation theorem does and does not promise (existence of weights, not trainability or generalization).
  • Explain, via the folding picture, why depth can be exponentially more efficient than width.

Connects to

  • This session is covered by Quiz 1 (Module 1: S01–S08), given at S09.
  • This is the conceptual setup for 1.3 (S03), which replaces the mistake-driven rule with loss minimization (the move Adaline made first), and for 1.4 (S04–S05), which finally trains the hidden layers.
  • You will implement forward and backward passes for a scalar engine in HW1, and the Try it yourself exercises below extend the same pattern to a layer.

← S01 · Why Deep Learning Works Now · All readings · S03 · Losses and Gradient Descent →