LLGA · Course notes

Deep Learning

APM_52183_EP · Year 1 · Period 2

Contents

Introduction and overview

Module Deep Learning — official title (SynapseS 2026-2027 catalog): “Apprentissage profond de la théorie à la pratique”
Code APM_52183_EP
Team and volume Instructor (“Responsable” on the 2026–2027 sheet and on the track page): Boris Bonev · instructional engineering team: P. Bianchi, C. Bonet, B. Bonev · 36 h in person · 4.5 ECTS (MScT degrees; 5 ECTS engineering curriculum and exchange programs) · the foundations and practice of deep learning — PyTorch pipeline, automatic differentiation, optimization, CNNs, RNNs, transformers for text, robustness, deep reinforcement learning, generative models — together with a cost reading of them: counting FLOPs and bytes, parallelizing training, compressing inference, and knowing the lower bounds that say what cannot be done better.
Period Fall semester — period 2 (X-3A-P2): from 04/01/2027 to 19/03/2027 · X3A MA3 slot · min./max. enrollment 1/80 (occurrence: –/85)
Language French, English
Assessment Numerical grade out of 20 (literal conversion / American grade); “validation by project” stated for the engineering degree and the exchange programmes; resit allowed (max of the two grades); course unit earned if final grade ≥ 10. Modalities specific to the LLGA track: not displayed (its section of the sheet is empty) · prerequisites stated on the sheet (engineering degree and exchange programmes): basics in machine learning, coding in Python.
Status in the program P2 option — Choose 1AI-systems route (DL-once option) Course unit listed in the official LLGA 1 – S2 2026-2027 track, in the Period 2 “Choose 1” group: the Period 2 way to satisfy the rule “Deep Learning required once, in P1 or P2”.

Audience: a student with the sheet’s prerequisites — basics of machine learning and Python — who wants to learn deep learning together with its costs: the FLOPs, memory and communication of a training run or of a served model. Empirical first: each topic starts from a failure seen in practice — an out-of-memory error on a 7B model caused by a poor sharding choice, a speedup of only 1.2× despite 8 GPUs (Amdahl’s law) — and only then names the tools that explain it: complexity bounds, data, tensor and pipeline parallelism, quantization.

The module covers the P1 foundations in cost-oriented form, then adds what the lower bounds allow and how real GPUs behave.

What you will be able to do

Official objectives and syllabus (2026-2027 catalog)

Officially, the APM_52183_EP course unit offers an in-depth presentation of the practical and theoretical aspects of deep learning: on the one hand the mastery of Python / PyTorch implementation (implementation, debugging, visualization), on the other the analysis of foundations (automatic differentiation, universality results, non-convex optimization, equivariant models).

The stated objective is twofold: give an overview of the deep learning landscape and of its applications, in traditional fields and in new ones, and make students able to train by themselves a deep network of several million parameters, with PyTorch.

Prerequisites stated on the sheet (for the engineering degree and the exchange programmes): basics in Machine Learning and coding in Python.

The sheet lists a nine-item programme, in the order below; every item, and every theoretical topic of the description, is mapped to the section that teaches it.

Element of the official description / syllabus Section of this module
1. Introduction and presentation of the field ch. 0 — the field, its tasks and architectures (landscape); the building blocks of modern networks (from MLP to transformer block).
2. Training pipeline in PyTorch ch. 0 — the training pipeline: dataset, loader, model, loss, optimizer, a ResNet-18 (11.2 M parameters) on CIFAR-10, debugging and visualization checks.
3. Optimization for deep learning ch. 0 — optimization: SGD with momentum, Adam and AdamW (definition 0.9), initialization (prop. 0.7), learning rate, warmup, clipping, convergence rates (theorem 0.10, prop. 0.11).
4. Image analysis ch. 0 — output size and receptive field; ch. 1 — convolutional networks: definition 1.7, translation equivariance (prop. 1.8), cost (example 1.9); exercise 8.
5. Regression and classification of sequential data ch. 1 — recurrent networks: definition 1.12, vanishing gradients (prop. 1.13), LSTM (example 1.14).
6. Text generation (Transformers) ch. 0 — attention, positions, tokens, causal mask (definition 0.12 to 0.14); ch. 1 — text generation: teacher forcing, perplexity, decoding (definition 1.15, example 1.16); ch. 5 (KV cache, decode).
7. Stability and robustness ch. 7.1 — Lipschitz bounds and certified radius (prop. 7.2), adversarial examples and adversarial training (example 7.3), distribution shift.
8. Deep reinforcement learning ch. 7.2 — MDP, Bellman equation, DQN and policy gradient (definition 7.4, theorem 7.5, recalled from the RL course where they are proved), read through their cost: rollouts, variance per FLOP, replay memory; example 7.6, exercise 10.
9. Generative models ch. 7.3 — VAE and ELBO (definition 7.7, prop. 7.8), GAN (prop. 7.9), diffusion (definition 7.10, example 7.11), its Gaussian reverse step, ancestral sampler and ELBO (prop. 7.12, definition 7.13, prop. 7.14); exercise 9.
Automatic differentiation (description) ch. 0 — automatic differentiation: forward and reverse modes (definition 0.4), cheap gradient principle (prop. 0.5).
Universality results (description) ch. 0 — universal approximation (theorem 0.1, admitted) and an explicit ReLU construction (prop. 0.2, proved).
Non-convex optimization (description) ch. 0 — SGD on a non-convex objective (theorem 0.10, proved), and what is observed beyond the guarantee.
Equivariant models (description) ch. 1 — equivariant models: definition 1.10, permutation-equivariant layers (prop. 1.11).
Training a network of several million parameters ch. 0 — the ResNet-18 script; ch. 1–6 count what larger runs cost.

Complement to the official syllabus Chapters 1 to 6 also develop a “cost and systems” angle (FLOPs and memory counting, data/tensor/pipeline parallelism, collective communications, checkpointing and ZeRO, efficient inference, roofline) and chapter 8 the lower bounds of distributed optimization; neither appears as such in the official syllabus. They are this module’s complement, taught in class after the official themes they rely on.

Where this course fits in the program

One of the six options of the Period 2 “Choose 1” group, and the second way to satisfy the track rule “Deep Learning required once, in P1 or P2”: a student who did not take Deep Learning in Period 1 takes this course instead, as the AI-systems route of the home page does. It therefore assumes no earlier deep learning course.

Official prerequisites (stated for the engineering degree and the exchange programmes): basics in Machine Learning and coding in Python. In this programme they are covered by Machine Learning (Period 1) and by chapters 2–6 of the off-curriculum Refresher on neural networks. Chapter 0 builds everything else, from the training pipeline to the transformer block, before the cost chapters.

The other options of the same group (Optimization for AI, Multimodal Generative AI, …) cannot be taken alongside this course: the page cites their notes only as optional reading. It runs in parallel with the mandatory Reinforcement Learning, Graph ML and NLP courses, to which sections 7.2 and 7.3 and chapter 0 link.

Downstream, the module directly prepares ML Ops and LLM Engineering Principles (M2), where these cost accounts become deployment decisions, and Advanced Topics in Large Language Models (M2), whose large-scale analyses build on the same scaling laws and budgets.

Course outline

Session plan

36 h in class = 12 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet (36 h in person).

The sheet lists a nine-item programme without dates; the plan below follows its order — items 1–3 in sessions 1–3, items 4–6 in sessions 3–5, items 7–9 in sessions 9–11 — and interleaves this module’s systems chapters where they rely on the material just taught. The split into sessions is our proposal.

Level 1 = foundations (pipeline, autodiff, building blocks, first counts), 2 = core architectures, systems and methods, 3 = proof-heavy theory; the level never goes down from one session to the next.

Session Hours Level Content Practice
1 3 h 1 ch. 0 The field and its tasks, universal approximation (official 1); the PyTorch training pipeline (official 2) lab: the ResNet-18 script, initial-loss and one-batch checks
2 3 h 1 ch. 0 Automatic differentiation; optimization for deep learning: initialization, learning rate, Adam and AdamW, rates for non-convex and convex problems (official 3) Example 0.6 in PyTorch; learning-rate range test
3 3 h 1 ch. 0 From MLP to transformer block: convolution sizes, attention and the \sqrt{d_k} scaling, positions, BPE, pre-LN block, causal mask, LoRA (1.5 h); ch. 1 Units, cost of a linear layer and of a transformer block, the 6ND rule (1.5 h) the block of ch. 0 in PyTorch; Ex. 1
4 3 h 2 ch. 1 Training memory, the GPU memory hierarchy, scaling laws; convolutional networks and translation equivariance (official 4) lab: counting a ResNet stage; Ex. 8
5 3 h 2 ch. 1 Equivariant models; recurrent networks and LSTMs (official 5); text generation with transformers, decoding (official 6) lab: temperature and nucleus sampling on a small model
6 3 h 2 ch. 2 Data, tensor and pipeline parallelism; the decision tree Ex. 2
7 3 h 2 ch. 3 All-reduce: ring and tree, overlap; ch. 4 Checkpointing, ZeRO, mixed precision Ex. 5, 6
8 3 h 2 ch. 5 The memory wall, prefill and decode, compression, speculative decoding; ch. 6 Roofline, Amdahl, the budget of a 7B LLM Ex. 3, 4, 7
9 3 h 2 ch. 7.1 Stability and robustness: Lipschitz bounds, adversarial examples, distribution shift (official 7) lab: FGSM on the CIFAR-10 model of session 1
10 3 h 2 ch. 7.2 Deep reinforcement learning, recalled from the RL course and read through its cost (official 8, 1.5 h); ch. 7.3 VAE and GAN (official 9, 1.5 h) Example 7.6; REINFORCE with a baseline on a small control task (Ex. 10)
11 3 h 2 ch. 7.3 Diffusion: forward process, Gaussian reverse step, ancestral sampler, the noise loss as a reweighted ELBO (official 9) lab: a DDPM on 2-D data (Ex. 9)
12 3 h 3 ch. 8 Decentralized optimization, gossip, lower bounds and optimal algorithms, the finite-sum regime Example 8.2 by hand; talks of Ex. 11 (Megatron, ZeRO or FlashAttention, with a measured DP scaling)

Self-study, outside the 36 h (about 3 h in total): ch. 9 Research readings — the papers behind the lower bounds, and the Lipschitz regularity of networks (≈ 3 h).

How to study this module

Independent note The LLMs that structure the M2 of the master’s program are first and foremost objects of cost: counting them, parallelizing them and compressing them is the condition for deploying them. This module provides this language of budgets, common to the systems courses and the M2 LLM courses — and directly marketable in careers in large-scale ML engineering as in research on distributed learning.

0. Foundations: the field, the PyTorch pipeline, autodiff, optimization and the transformer block

This chapter lays the foundation that the rest of the module relies on, assuming only the sheet’s prerequisites: basics of machine learning and Python. It covers the first three themes of the official syllabus — the field and its tasks (with the universal approximation theorem), the training pipeline in PyTorch, and optimization for deep learning, with automatic differentiation in between — and ends by building the transformer block from the multilayer perceptron.

Readers who want backpropagation worked by hand on tiny networks first can use chapters 2–6 of the off-curriculum Refresher on neural networks.

The pedagogical contract of the P2 variant This variant teaches the same official foundations as the P1 course, and asks of each one “how much does it cost, and how far can one go?”. Three questions organize everything:

  • (Q1) count — predict the FLOPs and memory of a training run before launching it (ch. 1, 6);
  • (Q2) parallelize — decompose the compute time over several machines, and know what theory forbids (ch. 2–4, then the limits proved in ch. 8);
  • (Q3) compress — reduce the inference cost at nearly equal quality (ch. 5).

The lower bounds of ch. 8 come from the distributed-optimization literature (the papers of ch. 9): this module is the place in the master’s program where one proves lower bounds, not just algorithms.

The field: tasks, architectures and what a network can represent

Deep networks are the default tool for vision and language, and are spreading to the sciences. The official syllabus follows the main families of tasks; the table says where each one is treated here.

Task Data Typical architecture Section
image analysis pixel grids convolutional network (CNN) ch. 1, CNNs
regression / classification of sequences time series, audio, sensors recurrent network (RNN, LSTM) ch. 1, RNNs
text generation token sequences causal transformer ch. 1, text generation, ch. 5
sequential decisions interactions with a system deep reinforcement learning section 7.2
generating new data images, text, molecules VAE, GAN, diffusion section 7.3

Why should a network be able to represent the function that solves such a task? The classical answer is the universal approximation theorem.

Theorem 0.1 — Universal approximation (Cybenko 1989; Hornik 1991; Leshno, Lin, Pinkus & Schocken 1993) Let \sigma\colon \mathbb{R} \to \mathbb{R} be continuous and not a polynomial.

For every continuous function f on a compact set K \subset \mathbb{R}^d and every \varepsilon > 0, there exist a width N and parameters a_j, b_j \in \mathbb{R}, w_j \in \mathbb{R}^d such that the one-hidden-layer network g(x) = \sum_{j=1}^{N} a_j\,\sigma(w_j^\top x + b_j) satisfies \sup_{x \in K}|f(x) - g(x)| \leq \varepsilon .

Proposition 0.2 — An explicit ReLU construction in one dimension (proved) Let f be L-Lipschitz on [0, 1] and n \geq 1. With the knots x_k = k/n and the slopes s_k = n\big(f(x_{k+1}) - f(x_k)\big), the network g(x) = f(0) + s_0\,\mathrm{ReLU}(x) + \sum_{k=1}^{n-1}(s_k - s_{k-1})\,\mathrm{ReLU}(x - x_k) has n hidden units and satisfies \sup_{[0,1]}|f - g| \leq L/n .

Proof. On [x_k, x_{k+1}] exactly the units with knots x_0, \dots, x_k are active, so g is affine there with slope s_0 + (s_1 - s_0) + \dots + (s_k - s_{k-1}) = s_k .

Since g(0) = f(0), induction on k gives g(x_k) = f(x_k) at every knot: g is the piecewise linear interpolant of f.

For x \in [x_k, x_{k+1}], g(x) = \lambda f(x_k) + (1 - \lambda) f(x_{k+1}) for some \lambda \in [0, 1], hence |f(x) - g(x)| \leq \lambda|f(x) - f(x_k)| + (1-\lambda)|f(x) - f(x_{k+1})| \leq L/n , because both distances to the knots are at most 1/n. ∎

What the theorem does not say It guarantees existence, not efficiency nor learnability. The grid construction above needs about (L/\varepsilon)^d units in dimension d, an exponential cost; depth changes this picture, since some functions computed by deep narrow networks require exponentially many units with one hidden layer (Telgarsky 2016). Nor does it say that gradient descent will find the approximating weights: that is the question of the optimization section below.

Theorem 0.1 is admitted here. The P1 Deep Learning notes (ch. 1.2) sketch Cybenko’s proof for a sigmoidal \sigma; the general non-polynomial case of Leshno et al. (1993), which covers ReLU, needs more analysis; proposition 0.2 proves the one-dimensional ReLU case.

The training pipeline in PyTorch

Every training script, from a small classifier to a large language model, is built from the same five objects: a dataset (indexable, returning one example and its label), a data loader (batching, shuffling, parallel loading), a model (an nn.Module whose parameters are registered automatically), a loss, and an optimizer that updates the parameters from their gradients. The loop alternates a training phase (forward pass, loss, backward pass, update) and an evaluation phase without gradients.

The script below trains a ResNet-18 — about 11.2 million parameters, the order of size the official objectives ask students to master — on CIFAR-10.

import torch, torch.nn as nn
from torch.utils.data import DataLoader
import torchvision, torchvision.transforms as T

device = "cuda" if torch.cuda.is_available() else "cpu"
norm = T.Normalize((0.49, 0.48, 0.45), (0.25, 0.24, 0.26))
train = torchvision.datasets.CIFAR10("data", train=True, download=True,
    transform=T.Compose([T.RandomCrop(32, padding=4), T.RandomHorizontalFlip(), T.ToTensor(), norm]))
test = torchvision.datasets.CIFAR10("data", train=False, download=True,
    transform=T.Compose([T.ToTensor(), norm]))
train_dl = DataLoader(train, batch_size=128, shuffle=True, num_workers=4)
test_dl = DataLoader(test, batch_size=512)

model = torchvision.models.resnet18(num_classes=10).to(device)
print(sum(p.numel() for p in model.parameters()))        # 11,181,642
epochs = 30
opt = torch.optim.SGD(model.parameters(), lr=0.1, momentum=0.9, weight_decay=5e-4)
sched = torch.optim.lr_scheduler.OneCycleLR(opt, max_lr=0.1, total_steps=epochs * len(train_dl))
loss_fn = nn.CrossEntropyLoss()

for epoch in range(epochs):
    model.train()
    for x, y in train_dl:
        x, y = x.to(device), y.to(device)
        loss = loss_fn(model(x), y)
        opt.zero_grad(set_to_none=True)
        loss.backward()                 # reverse-mode automatic differentiation
        opt.step(); sched.step()
    model.eval(); correct = 0
    with torch.no_grad():               # no graph is stored during evaluation
        for x, y in test_dl:
            correct += (model(x.to(device)).argmax(1).cpu() == y).sum().item()
    print(f"epoch {epoch}: last train loss {loss.item():.3f}, test acc {correct / len(test):.3f}")

Debugging and visualization: the checks that catch most bugs

  1. Initial loss: with K balanced classes and a freshly initialized network, the cross-entropy should be close to \ln K (\ln 10 \approx 2.30 here); a very different value points to a bug in the labels, the loss or the initialization.
  2. Overfit one batch: training on a single batch of 32 examples must drive the loss near 0; if it does not, the model, the loss or the optimizer is wrong, independently of any data issue.
  3. Look at the inputs after augmentation and normalization, by displaying a few images with their labels.
  4. Monitor the training and validation curves, the learning rate and the gradient norm per layer (TensorBoard or an equivalent tool): a gradient norm that explodes precedes a divergence, a validation curve that rises while the training curve falls is overfitting.
  5. Fix the seeds and save checkpoints, so that a run can be reproduced and resumed.

Example 0.3 — The first two numbers to compute before training For the script above:

  1. the initial loss should read about 2.30;
  2. the training state in fp32 holds the weights (11.2 \times 10^6 \times 4 bytes \approx 45 MB), their gradients (45 MB) and the momentum buffer of SGD (45 MB): about 134 MB, to which the activations of the current batch are added (they grow linearly with the batch size and with the image resolution).

With Adam in mixed precision, definition 1.4 below gives 16 bytes per parameter, about 179 MB.

The same accounting, applied to a model with 7 billion parameters, is what ch. 1 and ch. 4 turn into sharding decisions.

Automatic differentiation: what loss.backward() computes

A network is a program made of elementary operations. Automatic differentiation computes the exact derivatives of such a program — not a finite-difference approximation, and not a symbolic formula — by applying the chain rule operation by operation.

Definition 0.4 — Evaluation trace, forward and reverse modes The program computes intermediate values v_1, \dots, v_m, each by an elementary operation of earlier ones, v_i = \phi_i(v_j : j \in \mathrm{pa}(i)), the inputs being the first values and the output y the last.

Forward mode propagates tangents \dot v_i = \sum_{j \in \mathrm{pa}(i)} \frac{\partial \phi_i}{\partial v_j}\,\dot v_j alongside the evaluation: one pass gives the derivative along one input direction.

Reverse mode first evaluates and stores the trace, then propagates adjoints backwards, \bar v_j = \sum_{i : j \in \mathrm{pa}(i)} \bar v_i\,\frac{\partial \phi_i}{\partial v_j} starting from \bar y = 1: one backward pass gives the derivative of the output with respect to all inputs.

Backpropagation is reverse mode applied to the loss.

Proposition 0.5 — The cheap gradient principle (Baur–Strassen 1983; Griewank) For a scalar function of p parameters computed by a program of elementary operations, reverse mode returns the whole gradient at a cost bounded by a small constant times the cost of one evaluation, independently of p; forward mode would need p passes.

The reason is local: each elementary operation with k arguments contributes k partial derivatives, used once in the backward sweep, which is of the same order as evaluating it.

The price is memory: all the intermediate values must be stored until the backward pass, which is why activations dominate the training memory (def. 1.4) and why checkpointing (ch. 4) trades recomputation for memory.

For a dense network the constant is about 2: \text{backward} \approx 4ND \quad \text{against} \quad \text{forward} \approx 2ND \ \text{FLOPs (theorem 1.3)}.

Example 0.6 — One forward and one backward pass by hand Take f(x_1, x_2) = x_1 x_2 + \sin x_1 at (x_1, x_2) = (\pi, 2).

  1. Forward trace: v_1 = \pi, \quad v_2 = 2, \quad v_3 = v_1 v_2 = 2\pi, \quad v_4 = \sin v_1 = 0, \quad v_5 = v_3 + v_4 = 2\pi .
  2. Backward sweep from \bar v_5 = 1: \bar v_3 = \bar v_4 = 1; then \bar v_2 = \bar v_3\, v_1 = \pi \quad\text{and}\quad \bar v_1 = \bar v_3\, v_2 + \bar v_4 \cos v_1 = 2 - 1 = 1 .

Hence \nabla f(\pi, 2) = (1, \pi), which matches the formulas \partial_1 f = x_2 + \cos x_1 and \partial_2 f = x_1.

In PyTorch, x = torch.tensor([math.pi, 2.0], requires_grad=True); (x[0]*x[1] + torch.sin(x[0])).backward() leaves exactly (1, \pi) in x.grad.

Optimization for deep learning

Training minimizes the empirical risk F(\theta) = \frac1n\sum_i \ell(h_\theta(x_i), y_i), which is non-convex as soon as there is a hidden layer.

Two algorithms do almost all the work. The first is SGD with momentum, where g_k is the mini-batch gradient at step k: m_{k+1} = \beta m_k + g_k, \qquad \theta_{k+1} = \theta_k - \eta\, m_{k+1}. The second is Adam/AdamW (definition 0.9 below), which divides each coordinate of the step by a running estimate of the gradient’s magnitude. Three facts specific to deep networks decide whether they work: initialization, the learning rate, and clipping.

Proposition 0.7 — Initialization that preserves the signal (He et al. 2015, proved) Consider a layer z = W x with W \in \mathbb{R}^{m \times n} whose entries are independent, centred, of variance s^2, independent of the input x = \mathrm{ReLU}(u), where the coordinates of u are centred, symmetric and identically distributed. Then

Key result — variance propagation through a ReLU layer \mathrm{Var}(z_i) = \frac{n s^2}{2}\,\mathrm{Var}(u_j).

The choice s^2 = 2/n (He initialization) keeps the variance of the pre-activations constant from layer to layer; a smaller s^2 makes it vanish geometrically with depth, a larger one makes it explode.

Proof. z_i = \sum_{j=1}^{n} W_{ij} x_j is a sum of n independent centred terms, so \mathrm{Var}(z_i) = \sum_j \mathbb{E}[W_{ij}^2]\,\mathbb{E}[x_j^2] = n s^2\, \mathbb{E}[x_j^2].

Since u_j is symmetric, \mathrm{ReLU}(u_j)^2 equals u_j^2 on half of the distribution and 0 on the other half, so \mathbb{E}[x_j^2] = \tfrac12\mathbb{E}[u_j^2] = \tfrac12\mathrm{Var}(u_j). ∎

Example 0.8 — The learning rate that diverges On f(\theta) = \tfrac{L}{2}\theta^2, gradient descent gives \theta_{k+1} = (1 - \eta L)\theta_k: it converges if and only if \eta < 2/L .

For a network, the role of the curvature L is played by the largest eigenvalue of the Hessian of the loss (the sharpness), which is unknown and changes during training.

Hence the practical recipe: find the largest learning rate that does not diverge on a short run, use a fraction of it, start with a warmup (a linear ramp over the first percent of the steps, while the early curvature is high and Adam’s moment estimates are poor), then decay it (cosine or steps).

Gradient clipping, g \mapsto g\min(1, c/\|g\|), caps the damage of a rare large gradient.

Definition 0.9 — Adam and AdamW (Kingma & Ba 2015; Loshchilov & Hutter 2019) Adam keeps two states per parameter, started at m_0 = v_0 = 0.

Its hyperparameters are the learning rate \eta, the decay rates \beta_1, \beta_2 (defaults 0.9 and 0.999), a small \varepsilon and the weight decay \lambda. At each step k \geq 1, coordinate by coordinate: m_k = \beta_1 m_{k-1} + (1-\beta_1)\, g_k, \qquad v_k = \beta_2 v_{k-1} + (1-\beta_2)\, g_k^2, \hat m_k = \frac{m_k}{1-\beta_1^k}, \qquad \hat v_k = \frac{v_k}{1-\beta_2^k}, \qquad \theta_k = \theta_{k-1} - \eta\Big(\frac{\hat m_k}{\sqrt{\hat v_k} + \varepsilon} + \lambda\,\theta_{k-1}\Big).

The bias corrections undo the start from zero.

AdamW applies the decay \lambda\theta outside the adaptive ratio, as written. Plain Adam with “L2 regularization” adds \lambda\theta to g_k instead: the decay is then divided by \sqrt{\hat v_k}, and the weights with large gradients are barely regularized.

The two states m, v are the 8 bytes per parameter of the training-memory table of ch. 1 (definition 1.4).

Theorem 0.10 — SGD on a non-convex objective (Ghadimi & Lan 2013, proved) Let F be L-smooth (its gradient is L-Lipschitz) and bounded below by F^\star, and let \Delta = F(\theta_0) - F^\star.

Assume the stochastic gradients g_k are unbiased with variance at most \sigma^2. SGD with the constant step \eta = \min\Big(\frac1L,\ \sqrt{\frac{2\Delta}{L\sigma^2 K}}\Big) satisfies, after K steps, \frac{1}{K}\sum_{k=0}^{K-1} \mathbb{E}\,\|\nabla F(\theta_k)\|^2 \;\leq\; \frac{4L\Delta}{K} + 2\sigma\sqrt{\frac{2L\Delta}{K}}.

The guarantee is a small gradient on average: a near-stationary point, at the rate O(1/\sqrt K) with gradient noise and O(1/K) without.

Proof. The descent lemma of L-smooth functions, with \eta \leq 1/L and the variance bound \mathbb{E}\|g_k\|^2 \leq \|\nabla F(\theta_k)\|^2 + \sigma^2 , gives \mathbb{E}\,F(\theta_{k+1}) \leq \mathbb{E}\,F(\theta_k) - \frac{\eta}{2}\,\mathbb{E}\|\nabla F(\theta_k)\|^2 + \frac{L\eta^2\sigma^2}{2}.

Summing over k < K and using F \geq F^\star: \frac1K\sum_{k<K}\mathbb{E}\|\nabla F(\theta_k)\|^2 \leq \frac{2\Delta}{\eta K} + L\eta\sigma^2 .

If \eta is the square root, both terms equal \sigma\sqrt{2L\Delta/K}. If \eta = 1/L, then \sigma^2 \leq 2L\Delta/K and the sum is at most 4L\Delta/K. ∎

Proposition 0.11 — Gradient descent versus Nesterov acceleration (Nesterov 1983, 2004; stated) Let f be L-smooth and \mu-strongly convex, with condition number \kappa = L/\mu.

  • Gradient descent with step 1/L needs O(\kappa\ln(1/\varepsilon)) gradient evaluations to reach accuracy \varepsilon (theorem 0.5 of the Machine Learning course, proved there for quadratics, next to the convex SGD rate).
  • Nesterov’s accelerated gradient needs only O(\sqrt{\kappa}\ln(1/\varepsilon)): y_k = x_k + \frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\,(x_k - x_{k-1}), \qquad x_{k+1} = y_k - \frac1L\nabla f(y_k).
  • No method that only combines gradients does better on all such functions (Nesterov 2004, ch. 2).

For \kappa = 10^4: about 10^4\ln(1/\varepsilon) steps against 100\ln(1/\varepsilon). Chapter 8 meets the same \sqrt\kappa in distributed training, multiplied by a network factor.

Non-convex optimization: what is guaranteed, what is observed The guarantee is modest: with a step tuned to the horizon, SGD reaches points whose average squared gradient norm is O(1/\sqrt{K}) after K steps (theorem 0.10) — stationary points, not minima.

What is observed is much better, for three reasons studied in research:

  • in high dimension, most critical points with a high loss are saddle points rather than poor local minima (Dauphin et al. 2014), and the noise of SGD helps to escape them (Ge et al. 2015);
  • overparameterized networks have many connected near-global minima;
  • normalization layers and residual connections (next section) keep the landscape well conditioned along the trajectory.

From MLP to transformer block

The cost chapters count convolutional networks and transformers. This section builds both from the multilayer perceptron, so that the module needs no earlier deep learning course.

Shapes follow the site convention. A linear layer is h = Wx + b with W \in \mathbb{R}^{d_\mathrm{out} \times d_\mathrm{in}} (the weight of nn.Linear). A sequence of n tokens of width d is a matrix X \in \mathbb{R}^{n \times d}, one token per row.

Convolution: output size and receptive field. A convolutional layer replaces the dense matrix by a small k \times k filter slid over the image; ch. 1 writes it out (definition 1.7) and counts its cost. With padding p and stride s, an input of side H gives an output of side H' = \Big\lfloor \frac{H + 2p - k}{s} \Big\rfloor + 1 .

For a 32-pixel input, a 3×3 filter and padding 1, the output keeps side 32 with stride 1 (the “same” padding of the ResNet-18 above) and halves to 16 with stride 2.

Each output of a stack of L such layers with stride 1 sees a patch of side 1 + L(k-1) of the input, its receptive field: it grows linearly with depth, and faster with strides or pooling.

Attention. In a convolution each position mixes a fixed neighbourhood; in attention each token decides, from the data, which other tokens to read.

Definition 0.12 — Scaled dot-product and multi-head attention (Vaswani et al. 2017) One attention head projects the tokens into queries, keys and values, Q = XW_Q, \qquad K = XW_K, \qquad V = XW_V, \qquad W_Q, W_K, W_V \in \mathbb{R}^{d \times d_k}, and returns \mathrm{Att}(Q, K, V) = \mathrm{softmax}\Big(\frac{QK^\top}{\sqrt{d_k}}\Big)V , the softmax acting on each row. Row i of the output is an average of the value vectors, weighted by how well query i matches each key.

Multi-head attention runs h heads with d_k = d/h in parallel, concatenates their outputs into an n \times d matrix and multiplies it by W_O \in \mathbb{R}^{d \times d}.

Proposition 0.13 — Why divide by \sqrt{d_k} (proved) Let the coordinates of a query q and a key k be independent, centred and of variance 1.

Then the score q^\top k has mean 0 and variance d_k, and the scaled score q^\top k/\sqrt{d_k} has variance 1, whatever the head width.

Proof. q^\top k = \sum_{j=1}^{d_k} q_j k_j is a sum of d_k independent centred terms, each of variance \mathbb{E}[q_j^2 k_j^2] = \mathbb{E}[q_j^2]\,\mathbb{E}[k_j^2] = 1 . ∎

Without the scaling, at d_k = 64 the scores have standard deviation 8. A softmax of such spread-out scores is nearly one-hot, and its Jacobian \mathrm{diag}(p) - pp^\top is then nearly zero: gradients stop flowing through the head. The scaling plays the role that He initialization (prop. 0.7) plays for linear layers.

Positions. Attention alone ignores order: permuting the rows of X permutes the rows of the output in the same way (permutation equivariance, the symmetry studied in ch. 1, definition 1.10). Order is injected by adding a position vector p_i to the embedding of token i:

Recent LLMs rotate the queries and keys instead of adding vectors (RoPE, see the Large Language Models course).

Tokens: byte-pair encoding in five lines (Sennrich et al. 2016).

  1. Start from single bytes.
  2. Count the adjacent pairs of symbols in a training corpus.
  3. Merge the most frequent pair into a new symbol, and record the merge.
  4. Repeat until the vocabulary reaches its target size (50\,257 tokens for GPT-2).
  5. Encode new text by replaying the merges in order.

Frequent words become one token, rare words split into pieces, and no word is ever out of vocabulary. Variants and their trade-offs: Text Mining and NLP, ch. 1.

Definition 0.14 — Pre-LN transformer block with causal mask With \mathrm{LN} the layer normalization of each token (zero mean, unit variance, then a learned scale and shift), a block maps X to H = X + \mathrm{MHA}\big(\mathrm{LN}(X)\big), \qquad Y = H + \mathrm{MLP}\big(\mathrm{LN}(H)\big), where \mathrm{MLP}(u) = W_2\,\mathrm{GELU}(W_1 u) acts on each token, with W_1 \in \mathbb{R}^{4d \times d} and W_2 \in \mathbb{R}^{d \times 4d}.

For generation, token i may only read tokens j \leq i. The causal mask M, with M_{ij} = 0 if j \leq i and -\infty otherwise, is added before the softmax: \mathrm{softmax}\Big(\frac{QK^\top}{\sqrt{d_k}} + M\Big)V .

Row i of the output then depends on x_1, \dots, x_i only.

Residual connections make each sublayer a correction to the identity. The gradient reaches the first layers through the sums, without crossing every block’s Jacobian, so the product of prop. 1.13 (the vanishing gradient of recurrent networks) never forms.

Pre-LN (normalizing before each sublayer, from GPT-2 on) keeps that identity path clean; the original post-LN design needed a long warmup to train at all (Xiong et al. 2020).

The block below is a complete, runnable version; ch. 1 counts its parameters (12d^2 plus biases) and its FLOPs.

import torch, torch.nn as nn

class Block(nn.Module):                      # pre-LN transformer block, causal
    def __init__(self, d=768, h=12):
        super().__init__()
        self.h, self.ln1, self.ln2 = h, nn.LayerNorm(d), nn.LayerNorm(d)
        self.qkv, self.proj = nn.Linear(d, 3 * d), nn.Linear(d, d)
        self.mlp = nn.Sequential(nn.Linear(d, 4 * d), nn.GELU(), nn.Linear(4 * d, d))

    def forward(self, x):                     # x: (batch, n, d)
        b, n, d = x.shape
        q, k, v = self.qkv(self.ln1(x)).view(b, n, 3, self.h, d // self.h).permute(2, 0, 3, 1, 4)
        mask = torch.ones(n, n, dtype=torch.bool, device=x.device).tril()
        att = (q @ k.transpose(-2, -1)) / (d // self.h) ** 0.5      # (b, h, n, n) scores
        att = att.masked_fill(~mask, float("-inf")).softmax(-1)
        x = x + self.proj((att @ v).transpose(1, 2).reshape(b, n, d))
        return x + self.mlp(self.ln2(x))

print(sum(p.numel() for p in Block().parameters()))   # 7,087,872 = 12 d^2 + 13 d

LoRA in five lines (Hu et al. 2022). Fine-tuning all the weights costs the full 16 bytes per parameter of ch. 1 (definition 1.4). LoRA freezes each pretrained matrix W_0, of size d_\mathrm{out} \times d_\mathrm{in}, and learns a low-rank correction: W = W_0 + BA, \qquad B \in \mathbb{R}^{d_\mathrm{out} \times r}, \quad A \in \mathbb{R}^{r \times d_\mathrm{in}}, \quad r \ll \min(d_\mathrm{in}, d_\mathrm{out}) .

B starts at zero, so training starts from the pretrained model. Only r(d_\mathrm{in} + d_\mathrm{out}) parameters per matrix receive gradients and Adam states. After training, BA is added into W_0, so inference costs nothing extra.

For d_\mathrm{in} = d_\mathrm{out} = 4096 and r = 8: 65\,536 trainable parameters instead of 16.8 M per matrix, 256 times fewer.

1. Counting: FLOPs, memory, scaling laws

A GPU budget is easily burned because nobody counted the FLOPs and the bytes before launching the job. This chapter teaches the module’s first skill, exact counting: predicting the compute and the memory of a training run from the architecture alone.

What breaks Three confusions cost the most: mixing up a FLOP count and a FLOP/s throughput, forgetting that memory bandwidth (not compute) often sets the speed, and adding GPUs without checking what Amdahl’s law allows.

The point of counting by hand: An engineer who can estimate the FLOPs of a training run by hand saves GPU-days — and catches configuration errors before they explode.

Definition 1.1 — Units: FLOP, FLOPs, FLOP/s A FLOP (floating-point operation) = one elementary operation (+, ×); we count a multiply-add a \cdot b + c as 2 FLOPs (the module’s convention, aligned with the systems literature); FLOP/s = throughput.

An A100 GPU: ≈ 19.5 TFLOP/s fp32, 312 TFLOP/s tensor-core bf16; an H100: ≈ 1000 TFLOP/s bf16 (sparse modes excluded).

The MFU (model FLOPs utilization) = achieved FLOP/s ÷ peak FLOP/s: 35–50% is a good LLM training run; the rest is lost to memory, communication and subtasks (ch. 6).

Proposition 1.2 — Cost of a linear layer and a transformer (proved)

  • (i) A matrix-matrix product A \in \mathbb{R}^{m \times n} by B \in \mathbb{R}^{n \times p} costs 2mnp FLOPs.
  • (ii) A linear layer d_\mathrm{in} \to d_\mathrm{out} applied to n tokens costs 2\,n\,d_\mathrm{in}d_\mathrm{out} FLOPs and has d_\mathrm{in}d_\mathrm{out} parameters — that is, 2 FLOPs per parameter and per token.
  • (iii) Transformer block of width d, over a sequence of n tokens:
    • QKVO 4 \times 2d^2 = 8d^2,
    • scores QK^\top and product with V: 2 \times 2n^2 d,
    • MLP (width 4d): 2 \times 2 \times 4d^2 = 16d^2
    — that is, per token: 24d^2 + 4nd \ \text{FLOPs}.

Proof.

  • (i) Each of the mp entries of C=AB is a dot product of length n (n multiplications + n−1 additions ≈ 2n FLOPs).

  • (ii) special case with m=n tokens, p = d_\mathrm{out}.

  • (iii) apply (ii) to each projection; for QK^\top (an n \times d by d \times n matrix): 2n^2 d, likewise for (\cdot)V (n \times n by n \times d).

    MLP = two layers d \to 4d then 4d \to d.

    Divide the total by n tokens to express it per token: QKV projections (3 \times 2d^2) + output (2d^2) = 8d^2, quadratic part of attention 4nd, MLP 16d^2. ∎

Theorem 1.3 — The rule C \approx 6\,N\,D (proved) Pre-training a model with N parameters (dense transformer) on D tokens costs

Key result — the training-compute rule C \;\approx\; 6\,N\,D \;\;\text{FLOPs} \qquad (\text{forward} \approx 2ND,\; \text{backward} \approx 4ND).

Proof. Forward pass: the model is a composition of linear layers and negligible operations (normalizations, softmax: O(nd) or O(n^2) without a d^2 factor); each parameter is used exactly once per token, at 2 FLOPs each (prop. 1.2 ii) — hence 2ND.

Backward pass: for each layer, the gradient is computed by

  • (a) applying the transpose of the weight to the upstream gradient (2ND) and
  • (b) multiplying the upstream gradient by the local input to form the weight gradient (2ND)

— that is 2 \times 2ND. Total 6ND.

Experience (profiling of large training runs) confirms within ±10%, the gap coming from (shared) embeddings, the vocabulary and the heads. ∎

Definition 1.4 — Training memory, line by line (Adam, mixed precision) For N parameters:

Tensor Precision Bytes/parameter
weights (bf16/fp16) 2 bytes 2
gradients (bf16) 2 2
Adam states m, v (fp32) 4 + 4 8
fp32 master weights (stability) 4 4
total states 16
activations (depend on n, d, number of layers) — see ch. 4 2 about 34\,d per token and per layer

The activation line follows Korthikanti et al. (2022): a transformer layer keeps about 34\,d bytes per token in bf16, plus a term that grows with the context length when the attention scores are stored.

Order of magnitude to remember: 16 bytes per parameter of states + activations. A 7B model with Adam: 7\times10^9 \times 16 ≈ 112 GB — before any activation: a single 80 GB GPU is not enough (ch. 4 and 6).

The GPU memory hierarchy, in one box A GPU computes in its streaming multiprocessors, each with registers and a small on-chip SRAM: 192 KB per multiprocessor on an A100, about 20 MB in all, read at roughly 19 TB/s. Behind them sit a 40 MB L2 cache and the HBM, the “GPU memory” of nvidia-smi: 80 GB at about 2 TB/s (figures of Dao et al. 2022).

Beyond the card, NVLink joins the GPUs of a node (600 GB/s per A100), InfiniBand joins nodes (about 25 GB/s per link) and PCIe reaches the host memory (about 32 GB/s). Each step down is several to tens of times slower, and much larger. Every count of this module — the 16 bytes per parameter, the KV cache, the all-reduce, the roofline of ch. 6 — asks at which level the bytes live and how often they cross a boundary.

Scaling laws: from Kaplan to Chinchilla (the budget as a primary dimension) Kaplan et al. 2020: over decades, the loss follows power laws in the number of parameters N and of tokens D, combined into the joint fit L(N, D) = \Big[\Big(\frac{N_c}{N}\Big)^{\alpha_N/\alpha_D} + \frac{D_c}{D}\Big]^{\alpha_D} — first reading: enlarging the model helps more than enlarging the data.

Hoffmann et al. 2022 (Chinchilla): with the compute budget C = 6ND fixed, the optimum is reached for D \approx 20 N — the models of the Kaplan era were undertrained; GPT-3 (300B tokens for 175B parameters) was “too big” for its data, and Chinchilla — 70B parameters on 1.4T tokens (example 1.6), trained with the budget of the 280B Gopher — outperforms both.

Method lesson for this module: the budget C is not a side constraint, it is the axis along which one designs the model.

(The M2 LLMs module, ch. 3, revisits these laws in detail; the “energy” angle is in the Optimization and Responsible AI for Sustainability module, ch. 6.)

Example 1.5 — Counting GPT-2 small by hand GPT-2 small has 12 blocks of width d = 768, a context of n = 1024 tokens and a vocabulary of 50\,257 tokens.

  1. Parameters. A block holds 4d^2 (attention projections) + 8d^2 (MLP) = 12d^2 \approx 7.1M parameters, so the 12 blocks hold about 85M.

    The token embeddings add 50\,257 \times 768 \approx 38.6M, which gives the announced 124M once position embeddings and biases are included.

  2. FLOPs per token, forward. By prop. 1.2, a block costs 24d^2 + 4nd \approx 14.2\text{M} + 3.1\text{M} \approx 17.3\text{M FLOPs}, i.e. about 208M for the 12 blocks; the output layer (logits over the vocabulary) adds 2 \times 768 \times 50\,257 \approx 77M.

The attention term 4nd equals 24d^2 when n = 6d: below a context of about 4\,600 tokens for this width, the matrix products dominate and the rule “2 FLOPs per parameter and per token” is accurate; for long contexts, the quadratic term takes over.

Example 1.6 — Sizing a model from a compute budget with the Chinchilla rule With a budget of C = 10^{23} FLOPs and the ratio D \approx 20N, the rule C = 6ND becomes C = 120\,N^2, so N = \sqrt{C/120} \approx 2.9 \times 10^{10} \ \text{parameters} \quad\text{and}\quad D \approx 5.8 \times 10^{11} \ \text{tokens}: a model of about 29B parameters trained on about 580B tokens.

As a check, Chinchilla itself (70B parameters, 1.4T tokens) corresponds to 6 \times 7 \times 10^{10} \times 1.4 \times 10^{12} \approx 5.9 \times 10^{23} \ \text{FLOPs}, with D/N = 20.

Halving the budget divides N and D by \sqrt 2 each, not N alone by two.

def flops_transformer(N_params, D_tokens, fwd_ratio=2.0, bwd_ratio=4.0):
    return (fwd_ratio + bwd_ratio) * N_params * D_tokens

C = flops_transformer(6.7e9, 1e12)                  # LLaMA-7B ~ 6.7B params, 1T tokens
print(f"{C:.2e} FLOPs")                              # 4.02e22
peak, mfu = 312e12, 0.45                             # A100 bf16, 45% MFU
hours = C / (peak * mfu) / 3600
print(f"{hours:,.0f} GPU-hours")                     # ~80,000 -- see ch. 6 and Touvron et al. 2023

Image analysis: convolutional networks

Images are large (a 224 \times 224 colour image has 150\,528 values) and their content does not depend on where an object sits. Convolutional networks exploit both facts: each output looks only at a small neighbourhood (locality), and the same filter is applied at every position (weight sharing).

Definition 1.7 — Convolutional layer For an input X \in \mathbb{R}^{c_\mathrm{in} \times H \times W} and a kernel K \in \mathbb{R}^{c_\mathrm{out} \times c_\mathrm{in} \times k \times k}, the layer computes (stride 1, zero padding) Y_{o,i,j} = b_o + \sum_{c=1}^{c_\mathrm{in}}\sum_{u,v=0}^{k-1} K_{o,c,u,v}\, X_{c,\,i+u,\,j+v}.

It has c_\mathrm{out}c_\mathrm{in}k^2 + c_\mathrm{out} parameters and costs 2\,H'W'\,c_\mathrm{out}c_\mathrm{in}k^2 FLOPs for an H' \times W' output — prop. 1.2 (ii) with H'W' positions playing the role of tokens.

A network stacks such layers with non-linearities and downsampling (stride or pooling); classification ends with a global average pooling and a linear layer, detection predicts boxes and classes at many positions, segmentation predicts a label per pixel with an encoder-decoder (U-Net).

Proposition 1.8 — Convolution commutes with translations (proved) Let (\tau_t X)_{c,i,j} = X_{c,\,i - t_1,\,j - t_2} translate an image by t = (t_1, t_2) (on an infinite grid, or away from the borders). Then \mathrm{conv}(\tau_t X) = \tau_t\,\mathrm{conv}(X): the layer is translation-equivariant, and a global pooling after it makes the network translation-invariant.

Proof. \mathrm{conv}(\tau_t X)_{o,i,j} = b_o + \sum_{c,u,v} K_{o,c,u,v}\, X_{c,\,i - t_1 + u,\,j - t_2 + v} = \mathrm{conv}(X)_{o,\,i - t_1,\,j - t_2} = \big(\tau_t\,\mathrm{conv}(X)\big)_{o,i,j}, since the same kernel is used at every position.

Pointwise non-linearities commute with translations too, so the whole stack is equivariant; a global average sums over all positions and forgets the shift. ∎

Example 1.9 — What weight sharing saves A 3 \times 3 convolution from 64 to 64 channels on a 56 \times 56 map (a ResNet stage) has 64 \times 64 \times 9 = 36\,864 weights and costs 2 \times 56^2 \times 64 \times 64 \times 9 \approx 0.23 \ \text{GFLOPs}.

A dense layer between the same input and output, each of size 64 \times 56^2 = 200\,704, would have 200\,704^2 \approx 4 \times 10^{10} weights: locality and sharing divide the parameter count by about 10^6.

The compute, on the other hand, stays large, because the small kernel is applied at every one of the 3\,136 positions: CNNs are compute-bound, which is why they map well onto GPUs (ch. 6).

The same count for a vision transformer (Dosovitskiy et al. 2021). ViT-B/16 cuts a 224 \times 224 image into 196 patches of 16 \times 16 pixels, plus one class token: n = 197 tokens of width d = 768, through 12 blocks. By prop. 1.2 (iii), one image costs 12 \times 197 \times (24d^2 + 4nd) \approx 3.5 \times 10^{10} \ \text{FLOPs} in the forward pass, about 35 GFLOPs — the “17.5 GFLOPs” of vision papers, which count a multiply-add once.

Equivariant models

Proposition 1.8 is one instance of a general design principle: when the task is unchanged by a group of transformations of the input, build that symmetry into the architecture instead of learning it from augmented data.

Definition 1.10 — Equivariance and invariance Let a group G act on the inputs by x \mapsto \rho_\mathrm{in}(g)x and on the outputs by y \mapsto \rho_\mathrm{out}(g)y. A map f is G-equivariant if f(\rho_\mathrm{in}(g)x) = \rho_\mathrm{out}(g)f(x) \quad \text{for all } g \in G \text{ and all } x, and G-invariant if f(\rho_\mathrm{in}(g)x) = f(x).

Examples: translations of an image and convolutional networks; permutations of the elements of a set and DeepSets, graph neural networks or self-attention without positional encoding; rotations of the plane and group-equivariant CNNs (Cohen & Welling 2016); rotations of the sphere and spherical models used for weather and climate, such as the spherical Fourier neural operators of Bonev et al. (2023).

Proposition 1.11 — Permutation-equivariant linear layers (Zaheer et al. 2017, proved) A linear map W\colon \mathbb{R}^n \to \mathbb{R}^n satisfies WP = PW for every permutation matrix P if and only if W = a I + b\,\mathbf{1}\mathbf{1}^\top for two scalars a, b. An equivariant layer on sets of n scalars therefore has 2 parameters instead of n^2, whatever n.

Proof. WP = PW for the permutation \pi means W_{\pi(i)\pi(j)} = W_{ij} for all i, j.

Any index i can be sent to any i' by a permutation, so all diagonal entries are equal, to a + b say.

Any ordered pair of distinct indices (i, j) can be sent to any other such pair (i', j'), so all off-diagonal entries are equal, to b. Hence W = aI + b\mathbf{1}\mathbf{1}^\top.

Conversely IP = PI and \mathbf{1}\mathbf{1}^\top P = \mathbf{1}\mathbf{1}^\top = P\mathbf{1}\mathbf{1}^\top, because every row and column of P sums to 1. ∎

The layer x \mapsto ax + b(\mathbf{1}^\top x)\mathbf{1} processes each element (ax_i) and adds a summary of the whole set (b\sum_j x_j): it is the skeleton of DeepSets and of message passing on graphs. Built-in symmetry gives the right behaviour on every input, not only on those seen with augmentation, and it saves parameters and data.

Sequential data: recurrent networks

Time series, audio and sensor streams have a variable length and an order. A recurrent network reads them one step at a time and carries a state that summarizes the past; it can output a single prediction for the whole sequence (classification) or one prediction per step (regression, forecasting).

Definition 1.12 — Recurrent network and backpropagation through time With input x_t \in \mathbb{R}^{d_\mathrm{in}} and state h_t \in \mathbb{R}^d: h_t = \tanh(W h_{t-1} + U x_t + b), \qquad \hat y_t = V h_t, \qquad t = 1, \dots, n.

The same parameters (W, U, b, V) are used at every step. Training unrolls the recursion into a deep network of depth n, the sequence length, and applies backpropagation to it (backpropagation through time).

Each step costs about 2(d^2 + d\,d_\mathrm{in}) FLOPs, but step t needs h_{t-1}: the n steps cannot be computed in parallel, unlike the n positions of a transformer (prop. 1.2).

Proposition 1.13 — Vanishing and exploding gradients (proved) With a_s = W h_{s-1} + U x_s + b, \frac{\partial h_n}{\partial h_t} = \prod_{s=t+1}^{n} \mathrm{diag}\big(\tanh'(a_s)\big)\,W, \qquad \Big\|\frac{\partial h_n}{\partial h_t}\Big\| \leq \|W\|^{n-t}.

If \|W\| < 1, the influence of step t on the loss at step n decays exponentially with the gap n - t; if W has an eigenvalue of modulus larger than 1 and the units stay in their linear regime, it can grow exponentially.

Proof. The chain rule gives \partial h_s/\partial h_{s-1} = \mathrm{diag}(\tanh'(a_s))\,W, and the Jacobians multiply along the chain h_t \to h_{t+1} \to \dots \to h_n. The norm of a product is at most the product of the norms, and \|\mathrm{diag}(\tanh'(a_s))\| \leq 1 since 0 < \tanh' \leq 1. ∎

Example 1.14 — Fifty steps of memory, and the LSTM fix With \|W\| = 0.9, a dependency 50 steps back is weighted by at most 0.9^{50} \approx 0.005 : the network cannot learn it.

The LSTM (Hochreiter & Schmidhuber 1997) adds a cell state updated additively, c_t = f_t \odot c_{t-1} + i_t \odot \tilde c_t , where the gates f_t, i_t \in (0,1)^d are computed from x_t and h_{t-1}. Along this direct path, \partial c_t/\partial c_{t-1} = \mathrm{diag}(f_t): when the forget gate stays close to 1, the gradient crosses many steps almost intact, and the network learns how long to remember.

Exploding gradients are handled separately, by gradient clipping. The GRU is a lighter variant with two gates.

Text generation with transformers

A language model assigns a probability to every sequence of tokens and generates text by sampling from it one token at a time. The transformer of prop. 1.2 becomes a generator through two changes: a causal mask, and a decoding rule.

Definition 1.15 — Causal language model, teacher forcing, perplexity The model factorizes p_\theta(x_1, \dots, x_n) = \prod_{t=1}^{n} p_\theta(x_t \mid x_{<t}).

In each attention layer the scores q_t^\top k_j with j > t are set to -\infty before the softmax (causal mask), so that position t only sees the past.

Training minimizes the cross-entropy -\frac1n\sum_t \log p_\theta(x_t \mid x_{<t}) on real text, with the true previous tokens as inputs (teacher forcing): a single forward pass produces the n predictions in parallel, which is what makes transformers much faster to train than RNNs.

The perplexity \exp\big(-\frac1n\sum_t\log p_\theta(x_t \mid x_{<t})\big) is the effective number of choices per token; a uniform model over a vocabulary \mathcal{V} has perplexity |\mathcal{V}|.

Example 1.16 — Decoding: temperature, top-k, nucleus At each step the model outputs logits z and the next token is drawn from \mathrm{softmax}(z/T). For three candidate tokens with logits (2, 1, 0):

  • at T = 1 the probabilities are (0.665, 0.245, 0.090);
  • at T = 0.5 they become (0.867, 0.117, 0.016), sharper;
  • at T = 2, (0.506, 0.307, 0.186), flatter.

T \to 0 is greedy decoding (always the most likely token), which tends to produce repetitive text.

Top-k sampling keeps only the k most likely tokens.

Nucleus (top-p) sampling keeps the smallest set whose probabilities sum to at least p, e.g. p = 0.9 keeps the first two tokens here at T = 1 (0.665 + 0.245 = 0.91), renormalized (Holtzman et al. 2020).

Generating each new token costs one forward pass for the new position only, provided the keys and values of the past are kept: this is the KV cache whose size governs inference in ch. 5 (def. 5.1).

2. Parallelism: data, tensor, pipeline

This chapter answers a practical question: how to split one training run over many GPUs. There are three axes, often combined (the “3D parallelism” of large systems); for each, we give the principle, the decomposition of the time per step and the communication cost.

Definition 2.1 — Data parallelism (DP) Each GPU holds a complete copy of the model, processes a different mini-batch (B/P examples), then the gradients are averaged by an all-reduce (ch. 3).

Time per step (batch size B, forward+backward time \tau_\mathrm{calc}(B), gradient of size S bytes): T_\mathrm{DP} \;=\; \underbrace{\tau_\mathrm{calc}(B/P)}_{\text{compute, divided by } P} \;+\; \underbrace{2\,(P-1)\,\alpha + \tfrac{2(P-1)}{P}\tfrac{S}{b}}_{\text{ring all-reduce (theorem 3.2)}}.

Strong scalability (at fixed B): the compute term shrinks, the communication term grows — the balance point defines the effective batch size; hence increasing B with the step (LARS, You et al. 2017).

This is the default mode of PyTorch DDP.

Definition 2.2 — Tensor parallelism (TP — Megatron, Shoeybi et al. 2019) One splits the matrices of the model. For the MLP block Y = \sigma(XW_1)\,W_2, the matrix W_1 is split by columns and W_2 by rows.

GPU i holds W_1^{[i]} and W_2^{[i]}, computes \sigma(XW_1^{[i]}) without any communication (the nonlinearity acts entry by entry, so column blocks stay independent), then the partial product \sigma(XW_1^{[i]})\,W_2^{[i]}; a single all-reduce sums the partial products into Y = \sum_i \sigma(XW_1^{[i]})\,W_2^{[i]}.

This column-then-row split costs one all-reduce in the forward pass and one in the backward pass per block; attention is split per head in the same way.

TP lives on the fastest links (intra-node NVLink): every layer pays a communication — this is the “mandatory high bandwidth” parallelism.

Theorem 2.3 — Pipeline parallelism: the bubble (proved) p stages (consecutive layers on each GPU), m micro-batches, each micro-batch costs \tau per stage. Under “1F1B” scheduling (one forward pass, one backward pass, staggered), the total time is T_\mathrm{pipe} \;=\; (m + p - 1)\,\tau, \qquad \eta \;=\; \frac{m}{m + p - 1} \;\xrightarrow[m \to \infty]{}\; 1, where \eta is the efficiency; the “bubble” (stage idle time) accounts for \frac{p-1}{m+p-1} of the total.

Proof.

  • Fill-up: the first micro-batch crosses the p stages in p\,\tau (stage j starts at j\tau); afterwards each following micro-batch exits every \tau units (the stages work staggered): the m-th exits at (p + m - 1)\tau .
  • Ideal work (without bubble): each stage processes m micro-batches, i.e. m\tau busy; efficiency is the ratio m\tau / (m+p-1)\tau.
  • Idle time: each stage stays idle for (p-1)\tau in total (fill-up and drain combined), i.e. a fraction (p-1)/(m+p-1) of the total time. ∎
Mode What is split Communication Required hardware Typical use
DP (2.1) the batch 1 gradient all-reduce per step decent inter-node network (InfiniBand) default, up to hundreds of GPUs
TP (2.2) the matrices all-reduce at every layer (forward+backward) intra-node NVLink (8 GPUs) very wide models (≥ 30B), or huge width
PP (2.3) the layers point-to-point activations between stages any network, bubble to amortize depth; combined with DP/TP (“3D”)
ZeRO (ch. 4) the states (optimizer, gradients, weights) like DP (all-reduce) + on-the-fly gathers same as DP replacing TP when memory, not compute, is the blocker

Example 2.4 — When does the gradient all-reduce start to hurt? Train a 1B-parameter model with data parallelism, bf16 gradients (S = 2 GB) and a global batch of 0.5M tokens per step. By theorem 1.3, a step costs 6 \times 10^9 \times 5 \times 10^5 = 3 \times 10^{15} \ \text{FLOPs}.

  • One node, P = 8 GPUs on NVLink (say b = 100 GB/s per GPU for the collective): at 312 TFLOP/s and 45\% MFU, compute takes 3 \times 10^{15}/(8 \times 1.4 \times 10^{14}) \approx 2.7 \ \text{s}, while the bandwidth term of the ring all-reduce is \frac{2 \times 7}{8} \times \frac{2}{100} \approx 0.035 s: about 1\% of the step.
  • Sixty-four GPUs over a slower inter-node network (b = 25 GB/s): compute drops to 0.33 s, while communication grows to \frac{2 \times 63}{64} \times \frac{2}{25} \approx 0.16 \ \text{s}, almost half of the compute.

Without overlapping communication and computation (ch. 3), the scaling from 8 to 64 GPUs would deliver a speedup of about 5.5 instead of 8.

Choosing: the practitioner’s decision tree

  1. Does the model fit on one GPU with activations? → DP, end of story.
  2. The Adam states do not fit → ZeRO-2/3 (ch. 4), not TP: less communication.
  3. The weights alone do not fit (2N bytes > memory) → TP intra-node (8 NVLink GPUs) + PP inter-node + DP on top; tune m ≥ 4p to keep the bubble under 20% (theorem 2.3).
  4. Always measure the MFU (ch. 1): below 35%, the hierarchy is poorly chosen.

3. Communication: all-reduce and friends

This chapter studies the operation that connects the workers. The real bottleneck of distributed training is rarely compute: it is the exchange of gradients. One collective operation must be known in depth — the all-reduce — and two ways of implementing it, one that saves bandwidth and one that saves latency.

Definition 3.1 — All-reduce P machines each hold a vector g_i of S bytes; all must receive \bar g = \frac1P\sum_i g_i (the gradient average in DP). Homogeneous network: latency \alpha per message, bandwidth b bytes/s.

Theorem 3.2 — Ring all-reduce: bandwidth-optimal (proved) Arranging the P machines in a ring and cutting the vector into P chunks of S/P bytes, the all-reduce proceeds in two phases (reduce-scatter then all-gather) of P-1 steps each:

Key result — cost of the ring all-reduce T_\mathrm{ring} \;=\; 2\,(P-1)\,\alpha \;+\; \frac{2(P-1)}{P}\cdot\frac{S}{b} \;\xrightarrow[P \to \infty]{}\; 2\alpha P + \frac{2S}{b}.

The bandwidth term becomes independent of P: each machine sends 2S(P-1)/P < 2S bytes in total, whatever the number of machines.

This is optimal: Patarasuk and Yuan (2009) show that any all-reduce algorithm must make some machine send at least 2S(P-1)/P bytes.

Proof. Reduce-scatter. At step t, machine i sends a chunk (already partially summed) to i+1 and receives from i-1 a different chunk which it adds to its own.

After P-1 steps, machine i holds the complete sum of chunk i — each machine has sent (P-1)\cdot S/P bytes.

All-gather. Same round in broadcast direction: the complete sums circulate, (P-1)\cdot S/P bytes sent per machine.

Total per machine: 2(P-1)S/P bytes at rate b, that is 2(P-1)S/(Pb) — and the critical path is indeed the sequence of 2(P-1) steps of latency \alpha. ∎

Proposition 3.3 — Tree all-reduce: latency-optimal In a binary tree: reduction in \log_2 P steps then broadcast in \log_2 P steps, but each step transmits the entire vector: T_\mathrm{tree} = 2\log_2 P\,(\alpha + S/b).

For small S (short gradients, many small tensors): the tree wins (latency); for large S (LLM gradients): the ring wins (bandwidth). Real libraries (NCCL) choose dynamically — and compose partial rings over the actual topology (intra NVLink, inter IB).

Example 3.4 — Ring or tree, in numbers Take P = 64 machines, a latency \alpha = 2\,\mus and a bandwidth b = 25 GB/s.

  • For a small message, S = 64 KB (S/b \approx 2.6\,\mus): the ring costs 2 \times 63 \times 2 + \frac{2 \times 63}{64} \times 2.6 \approx 257\,\mu\text{s}, dominated by its 126 latencies, while the tree costs 2 \times 6 \times (2 + 2.6) \approx 55\,\mus: the tree is almost five times faster.
  • For a full gradient, S = 1 GB (S/b = 40 ms): the ring costs about 0.25 ms + 78.8 ms \approx 79 ms, while the tree costs 12 \times 40 \approx 480 ms: the ring is six times faster.

This is why gradients are grouped into large buckets before being reduced: a few large ring all-reduces are much cheaper than many small ones.

Three wars against the communication term: overlap, bucketing, compression

  • Overlap: while the GPU computes layer k+1, the gradient of layer k is already on the network (async by buckets); provided T_\mathrm{comm} \leq T_\mathrm{calc}, communication disappears from the critical path — the raison d’être of PyTorch DDP’s “bucketing”.
  • Gradient compression: quantizing the gradients (8 bits, even 1 bit) before exchange divides S by 2–16; error feedback (compensating the quantization error at the next step) preserves convergence — at the price of a delicate variance/theory trade-off (see the Emerging ML module, ch. 2–3 for the federated case, where communication is the limiting factor).
  • Locality: reducing the number of communications (local steps, gossip) is exactly the strategy dictated by the bound of ch. 8: fewer rounds, but more steps — the optimum of Scaman et al. is a precise point on this frontier.

4. Memory efficiency: checkpointing, ZeRO, mixed precision

The 16 bytes per parameter of ch. 1 and the activations rarely fit on one GPU. This chapter presents three ways of trading a little computation or communication for a lot of memory: recomputing activations, partitioning the training states, and storing numbers on fewer bits.

Theorem 4.1 — Activation checkpointing: O(\sqrt{L}) memory (proved) A network of depth L, activations a bytes per layer (per token/batch):

  • (i) without precautions, the backward pass requires M_\mathrm{full} = L\,a bytes of activations;
  • (ii) by storing only the inputs of a partition into \sqrt{L} segments of \sqrt{L} layers and recomputing each segment during the backward pass (gradient checkpointing, Chen et al. 2016): M_\mathrm{ckpt} \;\approx\; 2\sqrt{L}\,a \;+\; O(a), \qquad \text{additional cost} \approx +\tfrac{1}{3}\ \text{of time (one extra forward pass per segment).}

Proof. Memory. We store \sqrt L boundary activations; during the backward pass of a segment, we replay its local forward: at most \sqrt L simultaneous activations inside the segment (which can itself be recursively checkpointed: the memory/time trade-off can be tuned over the whole range [a, La], see the \sqrt{L} “compass”). Total \sqrt L + \sqrt L = 2\sqrt L live activations.

Time. Each layer is recomputed exactly once more in the forward direction: the forward pass accounts for 1/3 of the total cost (theorem 1.3: 2ND vs 6ND), hence about +33%. ∎

Definition 4.2 — ZeRO (Rajbhandari et al. 2020): partitioning the states Instead of replicating the training states on every GPU (classical DP: 16N bytes per GPU), ZeRO partitions them:

Stage What is partitioned Memory/GPU (states) Communication
ZeRO-1 Adam states (m, v, masters): 12N 4N + 12N/P = DP
ZeRO-2 + gradients (2N) 2N + 14N/P = DP
ZeRO-3 + weights (2N) 16N/P ≈ 1.5 × DP (on-the-fly gathers)

Example: a 7B model on 8 GPUs. ZeRO-3 brings its 16 \times 7 = 112 GB of states down to 112/8 = 14 \ \text{GB per GPU} — the model becomes trainable on a single node, without TP or pipeline bubble (ch. 2); DeepSpeed/FSDP implement exactly this continuum.

Mixed precision: the “free” compression Computing in bf16 (2 bytes) instead of fp32 (4): half the memory and (on tensor cores) 2–8× the throughput; fp32 is kept for accumulators and master weights (long sums and small updates; historical fp16 additionally required loss scaling, Micikevicius et al. 2018).

Theorem 1.3 remains valid: we count FLOPs, precision changes the price of a FLOP. Integer quantization (int8/int4) only serves inference — ch. 5; its error analysis is proved in the notes of the Optimization and Responsible AI for Sustainability course (prop. 3.3, second part): \text{error} \leq \sum_\ell \frac{\Delta_\ell}{2}\prod_{m>\ell}\mathrm{Lip}_m .

Example 4.3 — Why the master weights stay in fp32 The bf16 format keeps the 8 exponent bits of fp32 — the same range, up to about 3.4 \times 10^{38} — but only 7 mantissa bits, i.e. two to three significant decimal digits; fp16 has 10 mantissa bits but only 5 exponent bits, hence a maximum of 65\,504 and the need for loss scaling.

Near 1, consecutive bf16 numbers are 2^{-7} \approx 0.0078 apart. An Adam update of 10^{-4} applied to a weight equal to 1 is therefore rounded away: 1 + 10^{-4} is stored as 1, and a training run in pure bf16 would simply stop learning for that weight.

Keeping an fp32 copy of the weights (spacing 2^{-23} \approx 1.2 \times 10^{-7} near 1) lets these small updates accumulate; the bf16 copy is only used for the matrix products.

Common mistakes with training memory

  1. Budgeting the activations for the global batch: they scale with the micro-batch processed at once by each GPU, which is why gradient accumulation (several micro-batches before one optimizer step) fits large batches in small memories.
  2. Treating ZeRO-3 as free: every forward and backward pass gathers the weights on the fly, and the ZeRO paper puts its communication volume at about 1.5 times that of plain data parallelism — acceptable on NVLink, painful on a slow network.
  3. Reading the “allocated” memory of the profiler as the peak: temporary buffers of the collectives and allocator fragmentation add to it, so a plan that fills 100\% of the memory on paper will fail; keep a margin.

5. Efficient inference

At scale (millions of requests), inference dominates the total cost: it deserves its own tools. Four levers, from the simplest to the deepest.

Definition 5.1 — The memory-bandwidth wall of autoregressive inference Generating one token requires rereading all the weights (2N bytes in bf16) and the KV cache — the keys/values of past layers, to be kept for attention: \text{KV cache} \;=\; 2\;(\text{K and V})\times n_\mathrm{layers}\times n_\mathrm{ctx}\times d_\mathrm{model}\times 2\ \text{bytes} \;=\; 4\,n_\mathrm{layers}\,n_\mathrm{ctx}\,d_\mathrm{model}\ \text{bytes (bf16)}.

For 7B (32 layers, d = 4096, context 2048): 4 \times 32 \times 2048 \times 4096 \approx 1.1 \ \text{GB} — more than some believe, and growing with the context.

Peak throughput (one GPU, memory bandwidth B_\mathrm{mem}): \text{tokens/s} \;\lesssim\; \frac{B_\mathrm{mem}}{2N\ \text{bytes}} \qquad (\text{e.g. } 2\,\text{TB/s} \div 14\,\text{GB} \approx 140\ \text{tok/s}).

This ceiling — and not FLOPs — governs token-by-token generation (ch. 6, roofline); batching fills the compute units without moving the wall.

Proposition 5.2 — PTQ/QAT quantization, pruning, distillation (compact map)

Lever Idea Memory/speed effect Ref. / cross-reference
int8/int4 PTQ round the trained weights, calibration only 2–8× memory, up to 4× CPU/latency Jacob et al. 2018; error bounds: Responsible AI module, ch. 3
QAT simulate rounding during training (STE) int8 nearly lossless, int4 on large models Jacob et al. 2018
Structured pruning remove whole heads/channels/layers effective speedup (unlike unstructured) Han et al. 2016
Distillation student trained on the teacher’s logits softened by a temperature T 10–50× fewer parameters at similar quality on a narrow target task (the range of the Responsible AI notes, ch. 3); less on broad benchmarks: DistilBERT keeps 97 % of BERT’s GLUE score with 40 % fewer parameters Hinton et al. 2015; Sanh et al. 2019; Responsible AI notes, ch. 3 (full lab)
Speculative decoding small model proposes, large model verifies in parallel — same distribution in theory 2–3× tokens/s without loss Leviathan et al. 2023
IO-aware attention rewrite attention for the GPU memory hierarchy (tiling, kernel fusion) 2–4× training/inference on long contexts, O(n) memory Dao et al. 2022 (FlashAttention); memory hierarchy in ch. 1, roofline reading in ch. 6; see also the P1 Deep Learning notes, ch. 6.3

Prefill and decode: two regimes in one request Serving a request has two phases.

The prefill processes the whole prompt at once: all its tokens go through each weight matrix together, the arithmetic intensity is high and the phase is compute-bound, like training.

The decode then produces the answer one token at a time and is memory-bound (def. 5.1). A benchmark that reports a single “tokens per second” mixes the two and says little; report the time to first token (prefill) and the time per output token (decode) separately.

Memory also scales with concurrency: with the KV cache of def. 5.1, 32 simultaneous sequences of 2\,048 tokens on the 7B model need about 32 \times 1.1 \approx 35 GB of cache in addition to the 13.4 GB of weights — the KV cache, not the model, is what limits the batch size of an inference server.

Example 5.3 — How many tokens does speculative decoding buy? A small draft model proposes \gamma tokens; the large model checks them all in one parallel pass and accepts each one, in order, with probability \alpha (the rejection rule of Leviathan et al. keeps the output distribution exactly that of the large model). Under the simplifying assumption that acceptances are independent, the expected number of tokens produced per pass of the large model is \mathbb{E}[\text{tokens}] = 1 + \alpha + \alpha^2 + \cdots + \alpha^{\gamma} = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}, since the j-th proposed token is kept only if the j-1 previous ones were, and the pass always yields one token from the large model at the first rejection (or after the last acceptance).

With \alpha = 0.8 and \gamma = 4: (1 - 0.8^5)/0.2 \approx 3.4 \ \text{tokens per pass}.

Because generation is memory-bound (def. 5.1), checking four tokens costs almost the same time as generating one, so the speedup approaches 3.4 minus the cost of the draft model — consistent with the 2–3\times of the table.

Example 5.4 — Comparing honestly: the module’s protocol Any compression claim is verified in four columns:

  1. quality metric (perplexity/accuracy — not “it feels better”);
  2. latency at p50 and p99 (tail latency pays for cache misses);
  3. throughput (aggregate tokens/s);
  4. energy per request (J/request — Optimization and Responsible AI for Sustainability module, ch. 6).

An improvement on three columns with the fourth constant is a result; on a single one, it is a communication angle.

6. Real systems: roofline, GPU, and the complete budget of a 7B LLM

This chapter confronts the counts of the previous chapters with real hardware. It explains why a GPU rarely reaches its peak throughput, bounds the speedup of any parallelization, and ends with the complete budget of a 7B model.

Definition 6.1 — Roofline model (why a “312 TFLOP/s” GPU delivers 45%) An operation has an arithmetic intensity I = \mathrm{FLOPs}/\mathrm{bytes\ read+written}. The achievable throughput is

Key result — the roofline P_\mathrm{achievable} \;=\; \min\big(P_\mathrm{peak},\; B_\mathrm{mem}\cdot I\big)

with P_\mathrm{peak} the compute throughput and B_\mathrm{mem} the memory bandwidth.

A huge GEMM (large I): compute-bound; an activation, a normalization, a tokenizer, token-by-token generation (low I): memory-bound — increasing the GPU’s FLOP/s changes nothing there.

The 35–50% MFU of LLM training largely reflects the time spent in memory-bound operations and in communication; FlashAttention (prop. 5.2) wins by reducing bytes, not FLOPs — a pure roofline move.

Example 6.2 — Reading the roofline of an A100 With P_\mathrm{peak} = 312 TFLOP/s and B_\mathrm{mem} = 2 TB/s, the two regimes meet at the ridge point I^\star = 312/2 = 156 \ \text{FLOP per byte}.

A product of two n \times n matrices in bf16 performs 2n^3 FLOPs and moves at least 3 \times 2n^2 bytes, so I = n/3: it is compute-bound as soon as n \gtrsim 470.

Generating one token with batch size 1 multiplies each weight matrix by a single vector: 2 FLOPs per weight read, i.e. I \approx 1 FLOP per byte in bf16, and the achievable throughput is B_\mathrm{mem} \cdot I \approx 2 TFLOP/s — less than 1\% of the peak.

With a batch of B sequences, each weight read serves B tokens and I \approx B: decoding becomes compute-bound only around B \approx 150, which is why inference servers batch requests aggressively.

Proposition 6.3 — Amdahl’s law (proved) — the ceiling of all parallelism If a fraction s of the work is sequential (inevitably so), the speedup on P processors is capped: A(P) \;=\; \frac{1}{s + (1-s)/P} \;\leq\; \frac{1}{s}.

Proof. Sequential time T_1 = T_s + T_p with s = T_s/T_1. On P processors, the parallel part divides at best by P: T_P = T_s + T_p/P, hence A(P) = T_1/T_P = 1/(s + (1-s)/P), increasing in P and bounded above by 1/s. ∎

Example 6.4 — Complete case study: training a “7B” LLM (end-to-end computation) Assumptions (close to Touvron et al. 2023): N = 6.7\times10^9 parameters, D = 10^{12} tokens, A100-80GB bf16 (312 TFLOP/s peak, 2 TB/s HBM, 400 W), one node = 8 GPUs + NVLink.

Question Computation Result
Total FLOPs 6ND = 6 \times 6.7\times10^9 \times 10^{12} 4.0\times10^{22} FLOPs
GPU-hours (45% MFU) 4\times10^{22} / (312\times10^{12}\times0.45) / 3600 ≈ 79,000 GPU·h — the paper announces 82,432: the 6ND rule is accurate to ±5%
States memory 16\,N = 16 \times 6.7\times10^9 107 GB > 80 GB: ZeRO-2/3 or TP required (ch. 2, 4)
Activations (checkpointing, batch 4×2048 tokens) \approx 2\sqrt{32}\times(\text{layer act.}) a few GB/GPU: checkpointing (th. 4.1) makes the batch viable
Time on 256 GPUs (32 nodes) 79,000/256 h ≈ 13 days — hence the vital importance of MFU (half the time = 6 days saved)
GPU-only energy 79,000 h × 0.4 kW (+ PUE, see the Responsible AI module, ch. 6) ≈ 32 MWh before PUE; emissions by region: 1.6 t (FR) to ~15 t (world average)
fp16 inference weights 2N = 13.4 GB; KV cache 2048 ctx ≈ 1.1 GB (def. 5.1) fits on 1 80 GB GPU; throughput ≈ 140–150 tok/s (memory wall)

This table — reused in exercise 7 — is the module’s typical deliverable: a quantified budget, every line traceable to a theorem of the course (1.3, 4.1, 5.1, 6.1), and an engineer’s conclusion (where to invest the next euro: MFU? memory? quantization?).

The system’s keyboard: what to know about a GPU Memory hierarchy (registers → SRAM ~20 MB → HBM ~80 GB → NVLink → IB, the box of ch. 1); each level ~10× slower.

Winning kernels are those that maximize locality (tiling, fusion — FlashAttention again); “tensor cores” do bf16 GEMMs in 16×16×16 blocks — hence the importance of dimensions that are multiples of powers of 2, and why padding genuinely wastes.

For the ML engineer: profile before optimizing (nsight, PyTorch profiler), look at the roofline’s “memory bound” line, and remember that the best code optimizer is a better algorithm (ch. 5).

7. Stability, robustness, reinforcement learning and generative models

The previous chapters trained networks for supervised tasks and counted what that costs. This chapter covers the last three themes of the official syllabus: how stable a trained network is under small changes of its input, how deep networks learn to act from rewards instead of labels, and how they learn to generate new data. Each section gives the founding objects and one result proved in full; the specialised modules of the programme go further.

7.1. Stability and robustness

Stability has two meanings. Training stability — signals that neither vanish nor explode through depth or time — was treated with initialization (prop. 0.7), the recurrent case (prop. 1.13), normalization, residual connections and clipping. Robustness asks whether the trained model keeps its prediction when the input is perturbed: by an adversary who chooses a tiny worst-case perturbation, or by a shift between training and deployment data.

Definition 7.1 — Lipschitz constant, adversarial example A map f is L-Lipschitz (for a norm \|\cdot\|) if \|f(x) - f(x')\| \leq L\|x - x'\| \quad \text{for all } x, x'; the smallest such L is \mathrm{Lip}(f).

An adversarial example for a classifier at x is a point x + \delta with \|\delta\| \leq \epsilon (an imperceptible budget, e.g. \epsilon = 8/255 per pixel in \ell_\infty) that receives a different prediction.

Proposition 7.2 — Lipschitz bound of a network, certified radius (proved)

  • (i) For f = f_L \circ \dots \circ f_1 with f_l(x) = \sigma(W_l x + b_l) and \sigma 1-Lipschitz (ReLU, tanh), \mathrm{Lip}_2(f) \leq \prod_{l=1}^{L}\|W_l\|_2, the product of the spectral norms.
  • (ii) If a binary classifier predicts \mathrm{sign}\,f(x) with f L-Lipschitz in \ell_2, every perturbation with \|\delta\|_2 < |f(x)|/L leaves the prediction unchanged.

Proof.

  • (i) We have \|f_l(x) - f_l(x')\| \leq \|W_l x - W_l x'\| \leq \|W_l\|_2\,\|x - x'\|, since \sigma is 1-Lipschitz coordinate-wise; Lipschitz constants multiply under composition.
  • (ii) |f(x + \delta) - f(x)| \leq L\|\delta\|_2 < |f(x)|, so f(x + \delta) has the sign of f(x). ∎

The product bound is easy but often loose by orders of magnitude, and computing the exact Lipschitz constant of a deep network is NP-hard (Virmaux & Scaman 2018, ch. 9). Certified defences therefore constrain the norms during training (spectral normalization, orthogonal layers) so that the radius of (ii) becomes meaningful.

Example 7.3 — Why high dimension makes adversarial examples easy (Goodfellow et al. 2015) For a linear score f(x) = w^\top x and an \ell_\infty budget \epsilon, the worst perturbation is \delta = -\epsilon\,\mathrm{sign}(w)\,\mathrm{sign}(f(x)), which moves the score by \epsilon\|w\|_1.

On a 32 \times 32 colour image (d = 3\,072) with weights of size |w_i| \approx 0.01 and \epsilon = 8/255 \approx 0.031, the shift is about 0.031 \times 3\,072 \times 0.01 \approx 0.95 : a change of 3\% of the range on each pixel, invisible to the eye, moves the score by about 1, enough to flip any prediction whose margin is smaller.

Networks are piecewise linear, so the same attack works on them with w replaced by the input gradient: the fast gradient sign method takes \delta = \epsilon\,\mathrm{sign}\big(\nabla_x \ell(h_\theta(x), y)\big).

Adversarial training (Madry et al. 2018) solves \min_\theta \mathbb{E}\max_{\|\delta\|_\infty \leq \epsilon}\ell(h_\theta(x + \delta), y), approximating the inner maximum by a few projected gradient steps — a minimax problem, like the GAN game of section 7.3 — at a cost of several forward-backward passes per training step.

Distribution shift The second robustness question needs no adversary: deployment data differ from training data (another hospital, another camera, corruptions such as blur or noise). The honest protocol evaluates on held-out shifted sets, not only on an i.i.d. test split, and reports the drop. Data augmentation, pre-training on broad data and the equivariances of ch. 1 are the usual levers; none removes the drop entirely.

7.2. Deep reinforcement learning

In reinforcement learning no label says what the right output is: an agent acts, the environment answers with a new state and a reward, and the goal is to maximize the accumulated reward. Deep networks enter as function approximators for values or policies over large state spaces (pixels, board positions, text).

The mandatory Reinforcement Learning and Autonomous Agents course of the same period proves the founding results. This section states them, then reads them through the module’s question: what does deep RL cost?

Recall — proved in the RL course (ch. 1, theorem 5.1, algorithm 6.1)

  • Definition 7.4 — MDP and Bellman equation (RL, ch. 1). An MDP (\mathcal{S}, \mathcal{A}, P, r, \gamma) has transition probabilities P(s' \mid s, a), rewards r(s, a) and a discount \gamma \in [0, 1). A policy \pi(a \mid s) generates trajectories \tau of states and actions, with return G(\tau) = \sum_{t \geq 0} \gamma^t r(s_t, a_t). The optimal action value satisfies the Bellman optimality equation Q^\star(s, a) = r(s, a) + \gamma\,\mathbb{E}_{s' \sim P(\cdot \mid s, a)}\max_{a'}Q^\star(s', a'), and acting greedily with respect to Q^\star is optimal.
  • Deep Q-networks (Mnih et al. 2015; RL, algorithm 6.1) fit a network Q_\theta by minimizing, over transitions (s, a, r, s') drawn from a replay buffer, \big(r + \gamma\max_{a'}Q_{\theta^-}(s', a') - Q_\theta(s, a)\big)^2 , where the target network \theta^- is a copy of \theta refreshed every few thousand steps.
  • Theorem 7.5 — Policy gradient (REINFORCE, Williams 1992; RL, theorem 5.1). For a differentiable policy \pi_\theta, trajectories of H steps (the return G(\tau) then sums over t < H) and J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[G(\tau)], for any constant baseline b, \nabla J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\Big[\big(G(\tau) - b\big)\sum_{t=0}^{H-1}\nabla_\theta\log\pi_\theta(a_t \mid s_t)\Big]. The dynamics are neither known nor differentiated: only \log \pi_\theta is (the log-derivative trick).

What deep RL costs. Three quantities separate it from supervised training.

Example 7.6 — Policy gradient on a two-armed bandit One state, two actions; action 1 gives reward 1, action 0 gives 0; the policy plays action 1 with probability \pi_\theta(1) = \sigma(\theta), the logistic function.

Then J(\theta) = \sigma(\theta) \quad\text{and}\quad J'(\theta) = \sigma(\theta)(1 - \sigma(\theta)).

  • Without baseline. The REINFORCE estimator is r\cdot\partial_\theta\log\pi_\theta(a): it equals 1 - \sigma(\theta) when action 1 is drawn (probability \sigma(\theta)) and 0 otherwise, so its mean is \sigma(\theta)(1 - \sigma(\theta)), as the theorem says.

  • With the baseline b = \tfrac12, the estimator becomes \tfrac12(1 - \sigma(\theta)) for action 1 and \tfrac12\sigma(\theta) for action 0, since \partial_\theta\log(1 - \sigma(\theta)) = -\sigma(\theta) : same mean.

    At \theta = 0 it takes the constant value \tfrac14, whereas without baseline it takes the values \tfrac12 and 0 — the baseline removed all the variance at that point.

In rollouts: at \theta = 0 the estimator without baseline has standard deviation \tfrac14, equal to its mean, so about 100 rollouts are needed for a 10\,\% relative error, against a single one with the baseline. The same gradient costs a hundred times fewer environment steps and forward passes.

Actor-critic methods and PPO, used to fine-tune language models from human feedback, learn such baselines with a value network (RL course, ch. 5).

7.3. Generative models

A generative model learns a distribution p_\theta close to the data distribution p_\mathrm{data}, in order to sample new images, sounds or molecules. Autoregressive models were met in ch. 1 (text generation); the three other families below differ by how they make training tractable.

Definition 7.7 — Variational autoencoder (Kingma & Welling 2014) A latent variable z \sim p(z) = \mathcal{N}(0, I) and a decoder p_\theta(x \mid z) define p_\theta(x) = \int p_\theta(x \mid z)p(z)\,dz, an intractable integral.

An encoder q_\phi(z \mid x) = \mathcal{N}\big(\mu_\phi(x), \mathrm{diag}\,\sigma_\phi^2(x)\big) approximates the posterior, and training maximizes the evidence lower bound \mathrm{ELBO}(x) = \mathbb{E}_{q_\phi(z \mid x)}\big[\log p_\theta(x \mid z)\big] - \mathrm{KL}\big(q_\phi(z \mid x)\,\|\,p(z)\big), a reconstruction term minus a regularization towards the prior.

Gradients with respect to \phi go through the sampling by the reparameterization z = \mu_\phi(x) + \sigma_\phi(x) \odot \varepsilon, \varepsilon \sim \mathcal{N}(0, I).

Proposition 7.8 — The ELBO is a lower bound, with an explicit gap (proved)

Key result — the ELBO gap \log p_\theta(x) = \mathrm{ELBO}(x) + \mathrm{KL}\big(q_\phi(z \mid x)\,\|\,p_\theta(z \mid x)\big) \geq \mathrm{ELBO}(x).

Proof. By Bayes, p_\theta(z \mid x) = p_\theta(x \mid z)p(z)/p_\theta(x), so for every z: \log p_\theta(x) = \log p_\theta(x \mid z) + \log p(z) - \log p_\theta(z \mid x).

Add and subtract \log q_\phi(z \mid x) and take the expectation over z \sim q_\phi(\cdot \mid x): \log p_\theta(x) = \mathbb{E}_q[\log p_\theta(x \mid z)] - \mathbb{E}_q\big[\log\frac{q_\phi(z \mid x)}{p(z)}\big] + \mathbb{E}_q\big[\log\frac{q_\phi(z \mid x)}{p_\theta(z \mid x)}\big].

The first two terms form the ELBO, the third is a KL divergence, which is non-negative. ∎

Proposition 7.9 — The optimal GAN discriminator (Goodfellow et al. 2014, proved) A GAN trains a generator G (pushing noise z to samples of density p_g) against a discriminator D(x) \in (0, 1) in the game \min_G\max_D\ \mathbb{E}_{p_\mathrm{data}}\log D(x) + \mathbb{E}_{p_g}\log(1 - D(x)).

For a fixed generator, the best discriminator is D^\star(x) = \frac{p_\mathrm{data}(x)}{p_\mathrm{data}(x) + p_g(x)}, and the value of the game becomes 2\,\mathrm{JS}(p_\mathrm{data}\,\|\,p_g) - \log 4: the generator minimizes the Jensen–Shannon divergence, which is zero exactly when p_g = p_\mathrm{data}.

Proof. The objective is \int\big(p_\mathrm{data}(x)\log D(x) + p_g(x)\log(1 - D(x))\big)dx, maximized pointwise.

For a, b > 0, y \mapsto a\log y + b\log(1 - y) is concave on (0, 1) with derivative a/y - b/(1 - y), which vanishes at y = a/(a + b): this gives D^\star.

With m = (p_\mathrm{data} + p_g)/2, the value is \mathbb{E}_{p_\mathrm{data}}\log\frac{p_\mathrm{data}}{2m} + \mathbb{E}_{p_g}\log\frac{p_g}{2m} = \mathrm{KL}(p_\mathrm{data}\|m) + \mathrm{KL}(p_g\|m) - 2\log 2 = 2\,\mathrm{JS}(p_\mathrm{data}\|p_g) - \log 4. ∎

Definition 7.10 — Denoising diffusion (Ho, Jain & Abbeel 2020) A fixed forward process adds Gaussian noise in T_\mathrm{diff} small steps, with variances \beta_t and \alpha_t = 1 - \beta_t (time t = 0 is the data): x_t = \sqrt{\alpha_t}\,x_{t-1} + \sqrt{\beta_t}\,\varepsilon_t ; it has the closed form x_t = \sqrt{\bar\alpha_t}\,x_0 + \sqrt{1 - \bar\alpha_t}\,\varepsilon with \bar\alpha_t = \prod_{s \leq t}\alpha_s and \varepsilon \sim \mathcal{N}(0, I).

A network \varepsilon_\theta(x_t, t) is trained to recover the noise, by minimizing \mathbb{E}_{x_0, t, \varepsilon}\big\|\varepsilon - \varepsilon_\theta\big(\sqrt{\bar\alpha_t}x_0 + \sqrt{1 - \bar\alpha_t}\,\varepsilon,\ t\big)\big\|^2 — a plain regression, with t drawn uniformly.

Sampling starts from pure noise and removes the predicted noise step by step (definition 7.13).

Example 7.11 — How fast the forward process destroys an image, and what sampling costs With a constant \beta_t = 0.02, after 100 steps \bar\alpha = 0.98^{100} \approx 0.133 : the image survives with coefficient \sqrt{0.133} \approx 0.36 under noise of standard deviation \sqrt{0.867} \approx 0.93.

With the schedule of Ho et al. (T_\mathrm{diff} = 1\,000, \beta_t increasing linearly from 10^{-4} to 0.02), \sum_t\beta_t \approx 10 and the last coefficient is \bar\alpha_{T_\mathrm{diff}} \approx e^{-10} \approx 4 \times 10^{-5} : the last state is pure noise to excellent accuracy, which justifies starting the sampler from \mathcal{N}(0, I).

The cost side, in the language of this module: a GAN generates a sample in one forward pass, a diffusion model in up to 1\,000 passes of its network (tens with modern samplers), and an autoregressive model in one pass per token — numbers that decide the inference budgets of ch. 5.

Training only regresses noise; generating needs the reverse of each forward step. The reverse step is intractable in general, but it becomes a Gaussian once the clean data point is known.

Proposition 7.12 — The reverse step given the data is Gaussian (proved) For t \geq 2, q(x_{t-1} \mid x_t, x_0) = \mathcal{N}\big(\tilde\mu_t(x_t, x_0),\ \tilde\beta_t I\big), \qquad \tilde\beta_t = \frac{1 - \bar\alpha_{t-1}}{1 - \bar\alpha_t}\,\beta_t , \tilde\mu_t(x_t, x_0) = \frac{\sqrt{\bar\alpha_{t-1}}\,\beta_t}{1 - \bar\alpha_t}\,x_0 + \frac{\sqrt{\alpha_t}\,(1 - \bar\alpha_{t-1})}{1 - \bar\alpha_t}\,x_t .

Writing x_0 through the noise \varepsilon of the closed form, x_0 = \big(x_t - \sqrt{1 - \bar\alpha_t}\,\varepsilon\big)/\sqrt{\bar\alpha_t}, the mean becomes \tilde\mu_t = \frac{1}{\sqrt{\alpha_t}}\Big(x_t - \frac{\beta_t}{\sqrt{1 - \bar\alpha_t}}\,\varepsilon\Big).

Proof. By Bayes, and since the forward process is Markov, q(x_{t-1} \mid x_t, x_0) \propto q(x_t \mid x_{t-1})\, q(x_{t-1} \mid x_0), a product of two Gaussians in x_{t-1}: \mathcal{N}\big(x_t;\ \sqrt{\alpha_t}\,x_{t-1},\ \beta_t I\big) \quad\text{and}\quad \mathcal{N}\big(x_{t-1};\ \sqrt{\bar\alpha_{t-1}}\,x_0,\ (1 - \bar\alpha_{t-1}) I\big).

The exponent is quadratic in x_{t-1}, so the posterior is Gaussian. Its precision is the sum of the two precisions; since \alpha_t(1 - \bar\alpha_{t-1}) + \beta_t equals 1 - \bar\alpha_t, \frac{\alpha_t}{\beta_t} + \frac{1}{1 - \bar\alpha_{t-1}} = \frac{1 - \bar\alpha_t}{\beta_t\,(1 - \bar\alpha_{t-1})} = \frac{1}{\tilde\beta_t}.

Its mean is \tilde\beta_t times the sum of the precision-weighted centres, \tilde\beta_t\Big(\frac{\sqrt{\alpha_t}}{\beta_t}\,x_t + \frac{\sqrt{\bar\alpha_{t-1}}}{1 - \bar\alpha_{t-1}}\,x_0\Big) = \tilde\mu_t(x_t, x_0).

Substituting x_0 and using \bar\alpha_t = \alpha_t\bar\alpha_{t-1} gives the second form. ∎

Definition 7.13 — Ancestral sampler (DDPM) The learned reverse step replaces the unknown noise by its prediction: p_\theta(x_{t-1} \mid x_t) = \mathcal{N}\big(\mu_\theta(x_t, t),\ \sigma_t^2 I\big), \qquad \mu_\theta(x_t, t) = \frac{1}{\sqrt{\alpha_t}}\Big(x_t - \frac{\beta_t}{\sqrt{1 - \bar\alpha_t}}\,\varepsilon_\theta(x_t, t)\Big), with \sigma_t^2 = \beta_t or \tilde\beta_t (Ho et al. found both work).

Sampling draws x_{T_\mathrm{diff}} \sim \mathcal{N}(0, I), then for t = T_\mathrm{diff}, \dots, 1 sets x_{t-1} = \mu_\theta(x_t, t) + \sigma_t z, \qquad z \sim \mathcal{N}(0, I), with z = 0 at the last step. One sample costs T_\mathrm{diff} forward passes of \varepsilon_\theta.

Proposition 7.14 — The noise loss is a reweighted ELBO (Ho et al. 2020, proved) Take the latents x_1, \dots, x_{T_\mathrm{diff}}, the encoder q of the forward process and the decoder p_\theta of definition 7.13 (a Gaussian of mean \mu_\theta(x_1, 1) at the last step). The ELBO of prop. 7.8 then satisfies -\mathrm{ELBO}(x_0) = \sum_{t=1}^{T_\mathrm{diff}} w_t\,\mathbb{E}_{\varepsilon}\big\|\varepsilon - \varepsilon_\theta(x_t, t)\big\|^2 + C, \qquad w_t = \frac{\beta_t^2}{2\sigma_t^2\,\alpha_t\,(1 - \bar\alpha_t)}, where x_t is built from x_0 and \varepsilon by the closed form of definition 7.10, and C does not depend on \theta.

The loss of definition 7.10 drops the weights w_t. Since w_t is largest for small t, where denoising is easy, dropping it moves the effort to the noisier steps, and Ho et al. found that it gives better samples.

Proof. The ELBO with these latents splits into one term per step (Ho et al. 2020, eq. 5): -\mathrm{ELBO}(x_0) = \mathbb{E}_q\Big[\mathrm{KL}\big(q(x_{T_\mathrm{diff}} \mid x_0)\,\|\,p(x_{T_\mathrm{diff}})\big) + \sum_{t \geq 2}\mathrm{KL}\big(q(x_{t-1} \mid x_t, x_0)\,\|\,p_\theta(x_{t-1} \mid x_t)\big) - \log p_\theta(x_0 \mid x_1)\Big].

  • The first term has no parameter.
  • For t \geq 2, both laws are Gaussian with fixed variances (prop. 7.12), so the KL equals \|\tilde\mu_t - \mu_\theta\|^2/(2\sigma_t^2) plus a constant. Subtracting the two \varepsilon-forms of the means, \tilde\mu_t - \mu_\theta = \frac{\beta_t}{\sqrt{\alpha_t(1 - \bar\alpha_t)}}\,\big(\varepsilon_\theta(x_t, t) - \varepsilon\big), which gives w_t.
  • For t = 1, \bar\alpha_1 = \alpha_1 and 1 - \bar\alpha_1 = \beta_1, so x_0 - \mu_\theta(x_1, 1) = \sqrt{\beta_1/\alpha_1}\,(\varepsilon_\theta - \varepsilon); the Gaussian log-likelihood gives the weight \beta_1/(2\sigma_1^2\alpha_1), which is w_1. ∎
Family Training signal Exact likelihood Sampling cost Typical weakness
autoregressive next-token cross-entropy yes one pass per token slow sequential sampling
VAE ELBO lower bound one pass blurry samples
GAN adversarial game no one pass unstable training, mode collapse
diffusion noise regression bound (variational) tens to 1\,000 passes slow sampling

Diffusion returns in the mandatory Graph Machine Learning course, whose section 9.5 makes it discrete to generate graphs. The notes of Multimodal Generative AI develop latent diffusion and text-to-image models; that course is a sibling of this one in the same “Choose 1” group, so it is read as notes, not taken alongside.

8. Theoretical complexity of training

The previous chapters made each training step faster with more GPUs; this chapter asks whether there is a limit to what parallelism can buy. The answer is yes, and it is provable: for distributed optimization over a network, lower bounds say how many computation and communication rounds any algorithm needs. This chapter is the most theoretical of the module, and its lower bound is the central result of the papers read in ch. 9.

Definition 8.1 — Decentralized distributed optimization over a graph P machines, each with its own convex function f_i, connected by a graph G (each machine talks only to its neighbors); common goal: \min_x\; f(x) = \frac{1}{P}\sum_{i=1}^{P} f_i(x). The execution time counts two currencies: the number of local iterations (compute: gradient steps, whose number grows with the condition number — proposition 0.11) and the communication rounds (one gossip round = mixing the vectors between neighbors).

The gossip matrix W is symmetric and doubly stochastic, with W_{ij} > 0 only between neighbours.

Its largest eigenvalue is 1 (consensus vectors). The quality of the network is summarized by |\lambda_2(W)| \in [0, 1), the second largest modulus of an eigenvalue of W, or equivalently by the spectral gap \delta_W = 1 - |\lambda_2(W)| .

The disagreement between machines shrinks like (1 - \delta_W)^t after t gossip rounds — the smaller the gap, the slower the network reaches consensus.

Scaman et al. (ch. 9) write \gamma for a normalized eigengap of their gossip matrix, the ratio of its smallest non-zero to its largest eigenvalue: it plays the role of \delta_W here (small means poorly connected), not of |\lambda_2(W)|.

Example 8.2 — The spectral gap of a ring and of a complete graph On a ring of P machines where each one averages its value with its two neighbours, W = \tfrac13(I + S + S^{-1}) with S the cyclic shift.

The eigenvalues of W are \tfrac13\big(1 + 2\cos(2\pi k/P)\big), k = 0, \dots, P-1; the largest is 1 (consensus) and the second largest gives \delta_W = \tfrac43\sin^2(\pi/P) \approx \frac{4\pi^2}{3P^2}.

For P = 64, \delta_W \approx 3.2 \times 10^{-3} and 1/\sqrt{\delta_W} \approx 18: information needs a number of rounds proportional to P to cross the ring.

On a complete graph with W = \tfrac1P \mathbf{1}\mathbf{1}^\top, one round averages everything: \lambda_2(W) = 0, so \delta_W = 1 and 1/\sqrt{\delta_W} = 1. The topology alone changes the communication factor by more than an order of magnitude.

Theorem 8.3 — Lower bounds and optimality (Scaman, Bach, Bubeck, Lee, Massoulié, ICML 2017; statement) For f = \frac1P \sum f_i \mu-strongly convex and L-smooth (\kappa = L/\mu), every distributed algorithm (in the sense of def. 8.1) requires, to reach precision \varepsilon, a time

Key result — the compute × communication lower bound T \;=\; \Omega\!\Big(\sqrt{\kappa}\,\Big(1 + \frac{\tau}{\sqrt{\delta_W}}\Big)\ln\frac{1}{\varepsilon}\Big),

where a local gradient computation takes one unit of time and a communication round takes \tau units.

This order is attained, up to replacing the global condition number by the local ones of the f_i, by accelerated gradient ascent on the dual problem (Nesterov’s scheme, proposition 0.11) combined with Chebyshev accelerated gossip — replacing W by a well-chosen polynomial in W that flattens its spectrum, the same trick that accelerates gradients, applied to the graph (the MSDA algorithm).

When communication dominates (\tau large), the time is essentially \tau\sqrt{\kappa/\delta_W}\,\ln(1/\varepsilon): the product of the two obstacles.

The JMLR 2019 journal version (ch. 9) extends the analysis to the other classical convex settings — smooth or not, strongly convex or not. For non-smooth objectives, the network only affects a second-order term of the error.

Proof. Sketch of the lower bound (the “adversary” argument). One constructs a family of “local” quadratics at each node, whose solution x^\star depends on spread-out information.

For machine i to learn what machine j knew, the information must travel along the graph, and the mixing of the graph imposes \Omega(1/\sqrt{\delta_W}) communication rounds (each plain gossip round multiplies the imbalance by only 1 - \delta_W; acceleration reaches the square root, not better).

Independently, even sequentially, a quadratic with condition number \kappa requires \Omega(\sqrt\kappa) gradient accesses (Nesterov’s bound, proposition 0.11).

The construction crosses the two obstacles into a quadratic on the product graph × condition number: no algorithm can beat the product of the two bounds. ∎

Reading: the two regimes, and why they structure practice

Regime Condition Dominant time Practical equivalent
sequential (compute) fast network, gap close to 1 (NVLink, \delta_W \approx 0.9) \sqrt{\kappa}: Nesterov reigns a single node, 8 tightly linked GPUs
parallel (communication) slow network, \delta_W \to 0 (Ethernet, large clusters) \sqrt{\kappa/\delta_W}: the network caps everything multi-datacenter, federated (see the Emerging ML module, ch. 2–3)

Engineering consequence: adding machines does not reduce the time below the communication floor. This is the exact analogue of Amdahl’s law (ch. 6) for optimization: the “sequential” part is no longer a program but the geometry of the network. All of ch. 3 (all-reduce, compression, overlap) is a war against this 1/\sqrt{\delta_W}.

Proposition 8.4 — What parallelism can buy: the “finite sum” regime The bound of theorem 8.3 concerns the time to reach an \varepsilon-optimal point when the data are partitioned (each f_i is opaque). If instead all machines can evaluate the same function (replicated data), parallelism reduces the variance of SGD (mini-batching divides the \sigma^2 of theorem 0.10 by the batch size) — but the optimal statistical rate bounds the gain (Dieuleveut et al.; developed in ch. 11 of the Optimization for AI notes, a sibling option read as notes only). In short: parallelism speeds up compute, never (or marginally) the statistical complexity — a distinction that commercial announcements like to forget.

9. Research readings: lower bounds and Lipschitz regularity

Who wrote these papers (2026-2027 catalog): the APM_52183_EP course unit “Apprentissage profond de la théorie à la pratique” is led by Boris Bonev (“Responsable” on the 2026–2027 sheet and on the track page), with P. Bianchi, C. Bonet and B. Bonev on the instructional engineering team.

The works presented below are those of Kevin Scaman (previously MSR–INRIA) and co-authors, the lower-bound results underlying chapter 8 and the Lipschitz analysis behind section 7.1: they are cited as classic references of the field, not as the works of the official team.

Three papers to know:

Optimality of distributed optimization (the heart of ch. 8)

  • K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, L. Massoulié, Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks, ICML 2017 — the paper establishing the lower bound of theorem 8.3 and the optimal algorithm (Nesterov × Chebyshev gossip): the optimal time depends on the product condition number × topology. This is the first complete characterization of the compute/communication trade-off over networks.
  • K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, L. Massoulié, Optimal Convergence Rates for Convex Distributed Optimization in Networks, JMLR 2019 — the journal version, extended to the other classical convex settings (smooth or not, strongly convex or not), with matching upper and lower bounds in the decentralized case: the two regimes of chapter 8 are characterized there optimally.

Complexity of neural networks: Lipschitz regularity

  • A. Virmaux, K. Scaman, Lipschitz regularity of deep neural networks: analysis and efficient estimation, NeurIPS 2018 — proving that computing exactly the Lipschitz constant of a deep network is NP-hard, and designing the estimator (SeqLip, layer-wise power iteration) that became standard.

    The link with this module: the quantization-error propagation bound quoted in the mixed-precision note of ch. 4 (proved in the Responsible AI notes, prop. 3.3) involves precisely these \mathrm{Lip}_m constants — and the paper says how far one can (not) compute them; on the robustness side, the Lipschitz constant is the certificate of adversarial guarantees (see the M2 Security and Robustness module, ch. 5).

Reading thread L1: read the ICML 2017 focusing on (i) the construction of the lower bound (theorem 8.3 above); L2: re-prove the pipeline bubble (2.3) on paper; L3: profile a mini distributed training run (exercise 11) and empirically verify the ring all-reduce formula 3.2. This is the theory → system → measurement chain that defines this module.

Exercises

  1. ★ Counting. Prove the “per token” formula 24d^2 + 4nd of a transformer block (prop. 1.2), then verify theorem 1.3 on a GPT-2 small (N \approx 124M, 12 blocks, d = 768): compute C for D = 3B tokens and compare with a torch.profiler (or flops-profiler) profile within ±10%. Expected solution: 6ND \approx 6 \times 1.24\times10^{8} \times 3\times10^{9} \approx 2.2\times10^{18} \ \text{FLOPs}, about 4.4 A100-hours at 45\,\% MFU.

  2. ★ Pipeline bubble. Re-prove theorem 2.3 (draw the 1F1B Gantt chart for p=4, m=8). Then: what minimal m for an efficiency ≥ 90% with p = 16 stages? Solution: m/(m+15) \geq 0.9 \Rightarrow m \geq 135.

  3. ★ Inference memory wall. (a) Recover the KV cache formula (def. 5.1) for a model with grouped-query attention (GQA: g head groups instead of h) — what saving?

    (b) Compute the peak throughput of a 13B fp16 on an A100 (2 TB/s) and on a 1 TB/s GPU.

    (c) Show that, as far as the weights are concerned, int8 doubles this ceiling and int4 quadruples it, and explain why batching raises the aggregate throughput but not this per-sequence ceiling.

    Solution: (a) factor g/h; (b) ≈ 77 then 38 tok/s; (c) the weights go from 2N bytes to N (int8) and N/2 (int4): the ceiling is multiplied by 2 and 4, up to the KV cache, which stays in bf16.

  4. ★ Roofline. A kernel reads X \in \mathbb{R}^{m \times n} and w \in \mathbb{R}^n and computes Xw (2mn FLOPs, (mn + n + m)\times4 bytes).

    (a) Intensity I(m) as m \to \infty (at fixed n=4096)?

    (b) On an A100 (312 TFLOP/s, 2 TB/s), for which m is the GEMV memory-bound?

    (c) Deduce why autoregressive decoding is memory-bound and what batching changes there (hint: I grows with batch size — but not the wall per token).

  5. ★★ All-reduce. Prove theorem 3.2 on the reduce-scatter (induction on the steps).

    Then plot T_\mathrm{ring} and T_\mathrm{tree} (prop. 3.3) for S = 1 GB, \alpha = 2\,\mu s, b = 25 GB/s, P = 2 \dots 512 on a log scale. Crossover? Which mode for a bf16 LLM-13B gradient?

    Partial solution: the ring wins as soon as S/P \gg \alpha b.

  6. ★★ Checkpointing. A model with 30 blocks, activations 1.2 GB per block, 15 GB of memory available for activations.

    (a) Verify that storing all the activations does not fit.

    (b) Apply theorem 4.1: how many segments, what memory, what time overhead?

    (c) Show that with a single level of checkpoints and k segments the memory is about (k + L/k)\,a, hence never below 2\sqrt{L}\,a; explain how recursive checkpointing goes below this floor at the price of more recomputation (Chen et al. 2016 reach O(\log L) memory for O(L \log L) computation).

    Solution: (a) 36 GB > 15 GB; (b) 5 or 6 segments, (5 + 6) \times 1.2 \approx 13.2 GB, about +\tfrac13 of time.

  7. ★★ Complete budget (the capstone lab). Take up the table 6.4 with N = 13B, D = 300B tokens (a “Chinchilla-lite” budget: comment on the D/N ratio), on 64 H100 GPUs (≈ 990 TFLOP/s bf16, 40% MFU, 700 W). Compute: FLOPs, GPU-hours, calendar time, states memory (ZeRO-3 over 8 nodes?), energy, FR/world emissions. Conclude with three sentences of architecture recommendation.

    Partial answers: 2.3\times10^{22} FLOPs; ≈ 16,500 GPU·h; ≈ 11 days; 208 GB of states → ZeRO mandatory.

  8. ★★ Receptive field and translation equivariance. (a) Show that a stack of L convolutions with kernel k and stride 1 has a receptive field of side 1 + L(k-1). Compare the weights of three stacked 3 × 3 layers with those of one 7 × 7 layer, with c channels in and out and no bias.

    (b) With circular padding, show that the layer of definition 1.7 commutes exactly with a cyclic shift (torch.roll), and check it numerically.

    (c) Show that a stride-2 convolution is equivariant to shifts by an even number of pixels — a shift by 2 of the input shifts the output by 1 — but not to a shift by 1. Check both numerically.

    Solution: (a) each layer widens the patch by k - 1, so three 3 × 3 layers see 7 × 7 pixels with 27c^2 weights instead of 49c^2. (b) the proof of prop. 1.8 holds verbatim with indices taken modulo the image size.

    1. The stride-2 output at (i, j) is the stride-1 output at (2i, 2j): an even shift 2t moves it by t; an odd shift falls between the samples, and no shift of the output reproduces it.
  9. ★★ A DDPM sampler on 2-D data. (a) For Gaussian data x_0 \sim \mathcal{N}(0, s^2 I), show that the best noise predictor at step t (the minimizer of the loss of definition 7.10) is \varepsilon^\star(x_t, t) = \frac{\sqrt{1 - \bar\alpha_t}}{\bar\alpha_t s^2 + 1 - \bar\alpha_t}\,x_t .

    (b) Implement the ancestral sampler of definition 7.13 with \varepsilon^\star, 100 steps, \beta_t linear from 0.001 to 0.2 and \sigma_t^2 = \beta_t. From 100 000 noise draws, compare the standard deviation of the samples with s, for s = 0.5 and s = 2.

    (c) With the schedule of (b), train an MLP \varepsilon_\theta(x_t, t) (three hidden layers of 128 units, input (x_t, t/T_\mathrm{diff})) on scikit-learn’s make_moons (noise 0.05, standardized), then sample 2\,000 points and compare them with the data.

    Solution: (a) the minimizer is the conditional mean \mathbb{E}[\varepsilon \mid x_t]. The pair (\varepsilon, x_t) is Gaussian, with covariance \sqrt{1 - \bar\alpha_t} and \mathrm{Var}\,x_t = \bar\alpha_t s^2 + 1 - \bar\alpha_t.

    1. About 0.51 and 1.98 (0.47 and 1.94 with \sigma_t^2 = \tilde\beta_t): each reverse mean is exact for Gaussian data, its variance only approximately.

    2. 4 000 Adam steps with batches of 512 (seconds on a CPU) put about 99 % of the samples within 0.3 of a data point.

  10. ★★ REINFORCE with a baseline: variance and cost. (a) In the bandit of example 7.6, write \sigma = \sigma(\theta) and show that the estimator with a constant baseline b has variance \sigma(1-\sigma)\big[(1-\sigma)(1-b)^2 + \sigma b^2 - \sigma(1-\sigma)\big].

    (b) Deduce the variance-optimal baseline. At \sigma = 0.9, compare no baseline, b = 0.9 (the mean reward J(\theta)) and the optimum, and convert each variance into the number of rollouts needed for a 10\,\% relative error.

    (c) Implement REINFORCE on Gymnasium’s CartPole-v1 with a policy 4 \to 64 \to 2, without baseline and with a learned value baseline b(s_t) (allowed by the RL course, ch. 5). With 8 vectorized environments, report environment steps per second, and the environment steps and policy FLOPs needed to reach an average return of 475, over 5 seeds.

    Solution: (a) the estimator equals (1-b)(1-\sigma) with probability \sigma and b\sigma with probability 1-\sigma; its mean is \sigma(1-\sigma).

    1. The optimum b^\star = 1 - \sigma makes the estimator constant, with variance 0. At \sigma = 0.9 the variance is 0.0009 without baseline (about 11 rollouts), 0.0576 with b = 0.9 (about 711 rollouts) and 0 with b^\star (one rollout). The mean reward is not the variance-optimal baseline: here it multiplies the cost by 64.
  11. ★★★ Paper + measurement. Choose: Megatron (TP), ZeRO, or FlashAttention.

    (a) Summarize the mechanism in 10 lines with the module’s formulas.

    (b) Measure an effect on a small real setup (2 GPUs suffice): DP scaling 1→2→4 on a model that fits in memory (verify the \frac{2(P-1)}{P}\frac{S}{b} term of theorem 3.2 with torch.distributed and a barrier-timer).

    (c) Present in 10 minutes: key figure, one reproduced number, one limitation.

    Grid: accuracy of the quoted formulas, honesty of the measurement (error bars!), relevance of the chosen limitation.

Projects and assessment

Official assessment. The fiche above quotes the SynapseS 2026–2027 sheet: a numerical grade out of 20, “validation by project” stated for the engineering degree and the exchange programmes, a resit allowed (the better of the two grades is kept), and the course unit earned at 10/20. The modalities specific to the LLGA track are not displayed: that section of the sheet is empty. Everything below is our proposal, built to fit a validation by project: subjects, a written exam and a rubric.

The projects exercise the master objectives O1 (deep learning foundations), O3 (large language models, through their training and serving budgets) and O7 (hands-on practice: profiling, distributed training, serving), and O2 (generative modelling) through the diffusion sampler of section 7.3. Their measured numbers are meant to fill the compute-budget line of the charter of the end-of-year projects.

Solo projects

  1. [Solo · ≈ 25 h] Count, then measure: 6ND, memory and the roofline on GPT-2 small. Question: how close do the counts of ch. 1 come to a profiler on a real model, and why do they miss where they miss?
    • Implement: a FLOP and memory counter from prop. 1.2, theorem 1.3 and definition 1.4; profile the forward and backward passes of the Hugging Face gpt2 checkpoint (124 M parameters, Radford et al. 2019) and its generation with torch.profiler; place the main kernels on the roofline of definition 6.1.
    • Data and hardware: WikiText-103 sequences of 1 024 tokens; one free Colab or Kaggle T4 GPU.
    • Deliverables: code, a 4-page report with a predicted-versus-measured table (FLOPs, activation memory, MFU, KV-cache growth), a 10-minute talk.
    • Chapters: ch. 1, 5, 6.
    • Success: FLOPs within ±10 %, KV cache within ±5 %, every larger gap explained.
  2. [Solo · ≈ 25 h] Paper study: Lipschitz regularity and certified robustness (Virmaux & Scaman 2018). Question: how loose is the product of spectral norms of prop. 7.2, and what does a tighter Lipschitz estimate buy?
    • Implement: train the ResNet-18 of ch. 0 on CIFAR-10 three ways — standard, PGD adversarial training (Madry et al. 2018), spectral normalization (Miyato et al. 2018). For each, compute the product bound, a layer-wise power-iteration estimate in the spirit of the paper’s SeqLip, the certified radius of prop. 7.2 (ii) extended to ten classes through the margin, and the FGSM and PGD accuracy at budget 8/255.
    • Data and hardware: CIFAR-10, and CIFAR-10-C (Hendrycks & Dietterich 2019) for the distribution shift of section 7.1; one free T4 GPU, with reduced epochs.
    • Deliverables: code, a 4–6 page report that also counts the cost of each training with theorem 1.3, a 10-minute talk.
    • Chapters: ch. 0, 7.1, 9.
    • Success: a table of three trainings by five metrics with error bars over three seeds, and the gap between bound and estimate explained.
  3. [Solo · ≈ 20 h] Variance per FLOP: REINFORCE at laptop scale. It connects this course to Reinforcement Learning and Autonomous Agents (theorem 5.1, ch. 6). Question: how much compute do a baseline, a batch of trajectories and vectorized environments save to reach a given return?
    • Implement: exercise 10 (c) extended — REINFORCE without baseline, with a learned value baseline, and the PPO of the RL course; vary the number of vectorized environments (1 to 64) and of trajectories per update.
    • Data and hardware: Gymnasium CartPole-v1 and LunarLander-v3; a laptop CPU.
    • Deliverables: code, a 4-page report, a 10-minute talk.
    • Chapters: ch. 1 (counting), 6 (batching), 7.2.
    • Success: environment steps and policy FLOPs to the threshold (475 on CartPole, 200 on LunarLander) with intervals over five seeds, and a measured gradient variance that follows the trend of example 7.6.

Group projects

  1. [Group of 3 · ≈ 30 h each] From DDP to ZeRO-3: measuring the all-reduce term and Amdahl’s ceiling. Question: does the ring formula of theorem 3.2 predict the step time of real data-parallel training, and when does sharding pay?
    • Implement: train GPT-2 small (or the ResNet-18 of ch. 0) with DDP, ZeRO-1 (PyTorch’s ZeroRedundancyOptimizer), ZeRO-2 (FSDP’s SHARD_GRAD_OP or DeepSpeed) and FSDP full sharding (Zhao et al. 2023), on 1 and 2 GPUs (Kaggle’s free 2 × T4), and on 2 to 8 CPU processes with the gloo backend for the communication fit.
    • Measure: step time with error bars; the bandwidth term of theorem 3.2, fitted from all-reduce micro-benchmarks; the gain of overlap and of the bucket size; an Amdahl serial fraction (prop. 6.3); memory per GPU against definition 4.2.
    • Split: member A, DDP and the all-reduce benchmarks; member B, ZeRO-1, ZeRO-2 and FSDP memory; member C, the fits, Amdahl and the decision tree.
    • Deliverables: code, a 6-page report, the decision tree of ch. 2 annotated with the group’s own numbers, a 15-minute talk.
    • Chapters: ch. 2, 3, 4, 6; extends exercise 11.
    • Success: a fitted bandwidth within a factor 2 of the nominal link, and memory per GPU within 10 % of definition 4.2 plus the measured activations.
  2. [Group of 3 · ≈ 30 h each] Serving a small LLM under a budget: quantization, speculative decoding, batching. It connects this course to Large Language Models (ch. 6) and ML Ops and LLM Engineering (ch. 3). Question: which combination of levers gives the best quality–latency–throughput–energy trade-off on one free GPU?
    • Implement: serve Qwen2.5-1.5B-Instruct with Hugging Face transformers, separating time to first token (prefill) from time per output token (decode); int8 and 4-bit weights (bitsandbytes: LLM.int8() of Dettmers et al. 2022, NF4 of Dettmers et al. 2023); speculative decoding with Qwen2.5-0.5B-Instruct as draft model; static batches of 1 to 32 requests.
    • Measure: the acceptance rate against example 5.3, and the four columns of example 5.4 — perplexity on WikiText-2 and accuracy on 500 HellaSwag questions, p50 and p99 latency, tokens per second, energy from nvidia-smi power readings.
    • Split: member A, quantization; member B, speculative decoding; member C, batching, the measurement harness and energy.
    • Deliverables: code, a 6-page report, a 15-minute talk built on the four-column table.
    • Chapters: ch. 5, 6.
    • Success: at least five configurations measured on all four columns, and the speedup predicted from the measured acceptance rate within 20 % of the observed one.
  3. [Group of 4 · ≈ 30 h each] Paper study: a Chinchilla sweep at small scale (Hoffmann et al. 2022). Question: does the compute-optimal ratio of ch. 1, about 20 tokens per parameter, hold for tiny language models trained on simple text?
    • Implement: a family of causal transformers built from the block of ch. 0, from 1 to 60 M parameters, so that each budget’s optimum (about 3, 9 and 20 M at 20 tokens per parameter) is bracketed. At three budgets of about 10^{15}, 10^{16} and 5 \times 10^{16} FLOPs (counted as 6ND), train five or six models of different sizes each; fit the IsoFLOP minima and the law L(N, D) = E + A/N^\alpha + B/D^\beta.
    • Data and hardware: TinyStories (Eldan & Li 2023); one or two free T4 GPUs, about 4 \times 10^{17} FLOPs and 10 GPU-hours in all.
    • Split: member A, data and tokenizer; member B, model family and training loop; member C, the sweep and the fits; member D, evaluation and sampling.
    • Deliverables: code, a 6-page report with perplexities and samples under temperature and nucleus sampling (example 1.16), a 15-minute talk.
    • Chapters: ch. 0, 1, 6.
    • Success: the optimal size and ratio at each budget with bootstrap intervals, compared honestly with the Chinchilla ratio.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet and a non-programmable calculator allowed; four questions on 20 points — a course question, a computation and two short proofs.

  1. Question (4 points). Course. Explain why generating tokens one at a time with batch size 1 is memory-bound, while the prefill of a long prompt is compute-bound. Give the arithmetic intensity of each phase in FLOPs per byte (bf16 weights), and say what batching, the KV cache and int8 weights change.

    Expected: decode multiplies each weight matrix by one vector, 2 FLOPs per 2-byte weight, so the intensity is about 1, far below the A100 ridge of 156 (example 6.2): tokens per second are capped by bandwidth over weight bytes (definition 5.1). Prefill reuses each weight for the n prompt tokens, an intensity of about n, compute-bound beyond about 150 tokens.

    Batching B sequences multiplies the decode intensity by B. The KV cache avoids recomputing the past but adds bytes read per token. Int8 halves the weight bytes and doubles the memory-bound ceiling.

  2. Question (6 points). Computation. A dense transformer with 3 B parameters is trained on 60 B tokens on 32 A100 GPUs (312 TFLOP/s bf16 peak, 40 % MFU), with Adam in mixed precision. (a) Total FLOPs and the ratio of tokens to parameters. (b) GPU-hours and calendar days. (c) Training-state memory, in total and per GPU with ZeRO-3. (d) With a global batch of one million tokens and bf16 gradients: the bandwidth term of the ring all-reduce at 25 GB/s, against the compute time of one step.

    Expected: (a) 6ND = 1.08 \times 10^{21} FLOPs, 20 tokens per parameter (Chinchilla-optimal). (b) 1.08 \times 10^{21} / (1.25 \times 10^{14}) FLOP/s ≈ 8.7 million GPU-seconds ≈ 2 400 GPU-hours, about 75 h or 3.1 days on 32 GPUs. (c) 16 bytes per parameter: 48 GB in total, 1.5 GB per GPU.

    1. The gradient weighs 6 GB, so the bandwidth term is 2 \times \tfrac{31}{32} \times 6/25 \approx 0.47 s; one step computes 1.8 \times 10^{16} FLOPs in about 4.5 s. Communication is about 10 % of compute, and overlap (ch. 3) hides it.
  3. Question (5 points). Short proof: checkpointing. A network of L layers keeps a bytes of activations per layer. (a) With one level of checkpoints, one every L/k layers, show that the peak activation memory of the backward pass is about (k + L/k)\,a, minimal at k = \sqrt L, where it equals 2\sqrt L\,a. (b) Show that the extra computation is one forward pass, about a third of a training step (theorem 1.3).

    Expected: (a) the k boundary activations stay stored, and the backward pass of a segment recomputes its L/k layers and holds them together. The sum k + L/k is minimal where its derivative 1 - L/k^2 vanishes.

    1. Each layer is recomputed once in the forward direction: 2ND extra FLOPs out of 6ND, that is +1/3.
  4. Question (5 points). Short proof: diffusion. For the forward process of definition 7.10, show that q(x_{t-1} \mid x_t, x_0) is Gaussian and compute its variance. Then explain in two sentences why the sampler of definition 7.13 still needs a network, given this closed form.

    Expected: by Bayes and the Markov property, the posterior is proportional to a product of two Gaussians in x_{t-1}, of precisions \alpha_t/\beta_t and 1/(1 - \bar\alpha_{t-1}). The precisions add, and since \alpha_t(1 - \bar\alpha_{t-1}) + \beta_t equals 1 - \bar\alpha_t, \tilde\beta_t = \frac{1 - \bar\alpha_{t-1}}{1 - \bar\alpha_t}\,\beta_t .

    The mean depends on x_0, unknown when sampling; the network predicts the noise, hence x_0, from x_t (prop. 7.12, second form).

Grading rubric (proposal)

Criterion Weight What earns the marks
Correct counts and derivations 30 % every predicted number (FLOPs, bytes, communication, variance) traced to a result of the course, with its units
Measurement quality 25 % error bars over repeated runs or seeds, warm-up excluded, hardware and software versions stated, a controlled baseline
Analysis of the gaps 20 % predicted and measured values side by side; each gap above 10 % explained or flagged as open
Code and reproducibility 10 % one command reruns every table and figure; fixed seeds; public data only
Report and talk 15 % the four-column protocol of example 5.4 where relevant, honest limitations, a clear engineering recommendation

References