Theoretical Foundations of Deep Learning

Contents

• Introduction and overview
• 0. Review: calculus, probability and optimisation from M1
• 1. The learning problem and neural network models
• 2. The prediction as a function of the parameters; back-propagation
• 3. Landscape of the objective function
• 4. Non-convex optimisation
• 5. Robust deep learning I: stability, interpretability, Bayesian uncertainty
• 6. Robust deep learning II: Bayesian neural networks
• 7. Robust deep learning III: uncertainty in practice
• 8. Expressivity of feed-forward networks
• 9. Generalisation error of feed-forward networks
• 10. Open questions on generalisation; double descent
• 11. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with a good M1 in mathematics, computer science or physics who has already trained a network in PyTorch and wants to know which of its behaviours are theorems, which are open problems and which are folklore.

Empirical first: the same two-layer network reaches 100 % training accuracy on the scikit-learn digits whether the labels are the true ones or a random permutation of them (ch. 9). Test accuracy is 97.8 % in the first case and 8.1 % in the second. Classical capacity bounds cannot tell the two runs apart; this course builds the tools to say what can.

The course is a mathematical reading of deep learning for classification and regression. It follows a network from its definition to its training, its approximation power, its generalisation and its reliability. Each step pairs a theorem with a small experiment. The optimisation chapters extend Convex Optimization and Applications in Machine Learning; the generalisation chapters extend Introduction to Statistical Learning; the practice of networks is in Deep Learning.

What you will be able to do

• Write a feed-forward or convolutional network as a composition of maps, and prove that a ReLU network is piecewise affine in its input and piecewise polynomial in its parameters.
• Derive back-propagation, bound its cost, and explain exploding and vanishing gradients through products of Jacobians.
• Describe the critical points of the training loss of linear and wide networks, and prove the implicit bias of gradient descent towards minimum-norm solutions.
• State and use convergence results for gradient methods on non-convex functions: strict saddles, the Kurdyka–Łojasiewicz property, the Polyak–Łojasiewicz inequality.
• Prove a universal approximation theorem, and quantify approximation with Barron’s theorem, depth separation and Yarotsky’s constructions.
• Bound the generalisation error of a network with VC dimension and Rademacher complexity, and explain why such bounds are often vacuous.
• Derive the risk of minimum-norm least squares and reproduce the double-descent curve.
• Compute Bayesian posteriors, Laplace and variational approximations, and use MC dropout and ensembles to estimate predictive uncertainty.
• Measure calibration, predict failures and detect out-of-distribution inputs, with the metrics used in safety-critical applications.
• Bound the sensitivity of a network to perturbations and to individual training points.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com states that the main objective is to present the mathematical formulation of deep neural networks used for classification and regression. It announces the problems raised by these models and representative results of current research on parameter optimisation, the properties of networks, their expressivity, their complexity, and phenomena that are still unexplained, such as double descent and implicit regularisation.

It then links these results to the practice of the algorithms, with a view to robustness (uncertainty, stability). Practical sessions (TP) help students understand some properties of deep networks intuitively, implement learning algorithms on concrete problems and place the mathematical properties in their applied context.

The teaching team listed on master-mva.com is Sébastien Gerchinovitz (researcher, IRT Saint-Exupéry), François Malgouyres (professor, Institut de Mathématiques de Toulouse), Édouard Pauwels (maître de conférences, IRIT), Nicolas Thome (professor, Sorbonne Université, ISIR) and Gianni Franchi (teacher-researcher in trustworthy AI, ENSTA Paris). The Université Paris-Saclay detail states the objective as presenting representative research results on the mathematical justification of deep learning algorithms, then linking them to practice.

The table matches every official item — the “Thèmes abordés” of master-mva.com, each bullet of its ten announced sessions, and each item of the Université Paris-Saclay “Programme / plan / contenus” — with the section of these notes that teaches it.

Every official item is taught on this page. The extensions of these notes beyond the syllabus are the Polyak–Łojasiewicz analysis of over-parameterised least squares (Theorem 4.8), the influence-function experiment (5.3), and the research chapter (ch. 11, self-study), which adds the implicit bias of gradient descent on separable data (Theorem 11.1) and conformal prediction (Proposition 11.2).

Where this course fits in the programme

Official prerequisites: basic notions of analysis, statistics, machine learning and Python programming; the Université Paris-Saclay detail adds a Master 1 in mathematics with the basics of optimisation and statistical learning.

• Preparation — the refreshers Probability and Statistics (concentration, Gaussian computations), Linear Algebra, Analysis and Optimization (SVD, gradients, descent methods) and Scientific Python, NumPy and PyTorch (autograd, the labs).
• Related courses of the same semester — Deep Learning (architectures and training practice), Convex Optimization and Applications in Machine Learning, Introduction to Statistical Learning (risk bounds), Probabilistic Graphical Models and Deep Generative Models (variational inference), Computational Statistics, Optimal Transport for Machine Learning (Wasserstein GANs) and Turing Seminar: An Introduction to AGI Safety (robustness).
• Semester 2 courses that build on it — Bayesian Machine Learning, Kernel Methods for Machine Learning (neural tangent kernel), Large Random Matrices and Applications to Machine Learning (double descent), Deep Learning in Practice / Advanced Deep Learning, Responsible Machine Learning, Multimodal Explainable AI (XAI), Generative Models for Images and Learning Physical Phenomena: Metamodelling and Uncertainty Quantification.

Course outline

• Review: calculus, probability and optimisation from M1 — the chain rule, the descent lemma, concentration inequalities, Gaussian conditioning and the pseudo-inverse.
• The learning problem and neural network models — risk, Bayes predictor, risk estimation, the three errors, feed-forward and convolutional networks, the zoo, GANs, piecewise-affine predictions.
• The prediction as a function of the parameters; back-propagation — piecewise polynomials in θ, symmetries, non-convexity, non-coercivity, back-propagation, exploding and vanishing gradients.
• Landscape of the objective function — critical points, linear networks, implicit regularisation, stability of factorisations, wide networks.
• Non-convex optimisation — gradient descent on smooth functions, strict saddles, the Kurdyka–Łojasiewicz property, global convergence for over-parameterised least squares, stochastic gradient.
• Robust deep learning I — Lipschitz stability, stability to deformations, influence functions, typology of uncertainty, Bayesian linear regression (lab).
• Robust deep learning II — Laplace approximation, variational Bayes by Backprop, dropout as regularisation and as variational inference (lab).
• Robust deep learning III — metrics for regression, ensembles, evidential models, calibration, failure prediction, out-of-distribution detection (lab).
• Expressivity — universal approximation, Barron’s theorem, depth separation, super-approximation.
• Generalisation error — finite classes, Rademacher complexity, VC dimension, bounds for networks.
• Open questions; double descent — the generalisation puzzle, guarantees from a validation set, the exact risk of minimum-norm least squares.
• Research directions and open problems — implicit bias in classification, kernel and mean-field limits, benign overfitting, edge of stability, non-smooth automatic differentiation, non-vacuous bounds, conformal prediction, certified robustness, theory of GANs (self-study).

Session plan

30 h in class = 10 sessions of 3 h. The volume is the official one of the Université Paris-Saclay programme table (25 h of lectures and 5 h of labs), and master-mva.com announces the same organisation, 10 sessions of 3 h, with the labs at the end of sessions 5–7 (“cours puis TP”). The plan below follows the published order session by session; the split of each session into material and exercises is a proposal.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level results; the level never goes down.

Self-study, outside the 30 h (about 4 h in total): ch. 11 Research directions and open problems (≈ 4 h, with Ex. 18).

How to study this module

• Read ch. 0 before the first session, and redo its proofs: the descent lemma, Hoeffding’s inequality and the pseudo-inverse are used without warning later.
• After each session, do the exercises of the Practice column, then rerun the chapter’s code and change one parameter at a time.
• Every code block runs on a laptop CPU in a few seconds with NumPy, SciPy, scikit-learn and PyTorch; no data are downloaded.
• For the three labs (sessions 5–7), start from the code blocks of ch. 5, 6 and 7, which are minimal versions of the official lab subjects.
• Keep a list of the assumptions of each theorem: most of the open problems of ch. 10–11 are exactly the gaps between those assumptions and practice.

0. Review: calculus, probability and optimisation from M1

The proofs of this course use five M1 tools again and again. This chapter states them once, with the short proofs, so that later chapters can cite them by number.

1. The learning problem and neural network models

This chapter fixes the objects of the course: the risk a network must minimise, how to estimate it, and what a network computes.

1.1 Classification and regression

1.2 Risk estimation

The risk is never observed. The cleanest estimate uses data that played no role in training.

1.3 Approximation, estimation and optimisation errors

A trained network is limited by its architecture, its finite sample and its training algorithm. Each limitation has a cost.

Approximation is studied in ch. 8, estimation in ch. 9, optimisation in ch. 3 and ch. 4. Classically, enlarging \mathcal{F} lowers the first term and raises the second: the test error is U-shaped in the model size.

1.4 Feed-forward and convolutional networks

1.5 A tour of the zoo

The theorems below concern feed-forward networks; the same questions arise for the architectures used in practice.

• Recurrent networks apply the same cell along a sequence, h_t = \sigma(W h_{t-1} + U x_t + b). Back-propagation through time multiplies T Jacobians of one cell, so gradients explode or vanish (ch. 2); the LSTM of Hochreiter and Schmidhuber (1997) adds a gated additive memory.
• Transformers (Vaswani et al., 2017) replace recurrence by attention: for queries Q, keys K and values V, a head computes \mathrm{softmax}(QK^\top/\sqrt{d_k})\, V, stacked with residual connections, normalisations and feed-forward blocks.
• Representation learning reuses an intermediate layer a_\ell(x) for other tasks: auto-encoders, self-supervised and contrastive learning.
• Generative adversarial networks (GANs; Goodfellow et al., 2014) train a generator G, mapping noise to samples, against a discriminator D that separates them from data. FairGAN (Xu, Yuan, Zhang and Wu, 2018) adds a discriminator that tries to recover a protected attribute, so that the generated data carry less information about it.

For disjoint supports, \mathrm{JS}(p, q) = \log 2 whatever their distance, and the generator gets no gradient: hence the Wasserstein GAN (Arjovsky, Chintala and Bottou, 2017; see Optimal Transport for Machine Learning).

1.6 A piecewise-affine prediction as a function of the input

Depth can multiply the number of pieces (ch. 8), but random networks use little of this capacity.

import numpy as np

rng = np.random.default_rng(0)

def random_layers(widths):
    """He-initialised weights and small biases for a ReLU network."""
    return [(rng.normal(0, np.sqrt(2 / m), (m, k)), rng.normal(0, 0.5, k))
            for m, k in zip(widths[:-1], widths[1:])]

def activation_patterns(x, layers):
    """Sign pattern of every hidden unit, for each input point of a 1-D grid."""
    h, pats = x[:, None], []
    for W, b in layers[:-1]:
        z = h @ W + b
        pats.append(z > 0)
        h = np.maximum(z, 0.0)
    return np.hstack(pats)

x = np.linspace(-4, 4, 40_001)
for widths in [(1, 16, 1), (1, 8, 8, 1), (1, 4, 4, 4, 4, 1)]:
    counts = []
    for trial in range(10):
        P = activation_patterns(x, random_layers(widths))
        changes = np.any(P[1:] != P[:-1], axis=1).sum()
        counts.append(changes + 1)          # affine pieces of x -> f(x)
    print(f"widths {widths}: {sum(widths[1:-1])} units, "
          f"mean pieces {np.mean(counts):.1f}, max {max(counts)}")

With 16 hidden units in each case, the mean number of pieces on [-4, 4] is 16.1 for one layer, 15.9 for two and 13.6 for four: it grows with the number of units, not exponentially with depth, as Hanin and Rolnick (2019) prove in expectation at initialisation.

2. The prediction as a function of the parameters; back-propagation

Training sees f_\theta as a function of \theta. This chapter describes its regularity and symmetries, and computes its gradient.

2.1 A piecewise-polynomial prediction in θ

For the square loss, the empirical risk is therefore piecewise polynomial of degree at most 2L in \theta: a smooth function on each piece, with kinks on the boundaries.

2.2 Basic properties of the cost function

2.3 Back-propagation

Back-propagation is reverse-mode automatic differentiation; its price is the memory needed to store every z_\ell. At a ReLU kink, PyTorch sets \sigma'(0) = 0, and the output need not be a gradient (ch. 11).

import numpy as np
import torch

rng = np.random.default_rng(0)
d, m, n = 3, 5, 4
X = rng.normal(size=(n, d)); y = rng.normal(size=n)
W1, W2, w3 = rng.normal(size=(m, d)), rng.normal(size=(m, m)), rng.normal(size=m)

z1 = X @ W1.T; a1 = np.maximum(z1, 0)          # forward pass, storing z_l and a_l
z2 = a1 @ W2.T; a2 = np.maximum(z2, 0)
f = a2 @ w3

g_f = (f - y) / n                               # backward pass, loss = mean of (f - y)^2 / 2
g_w3 = a2.T @ g_f
d2 = np.outer(g_f, w3) * (z2 > 0)               # delta_2 = sigma'(z_2) * (w3 delta_3)
g_W2 = d2.T @ a1
d1 = (d2 @ W2) * (z1 > 0)                       # delta_1 = sigma'(z_1) * (W2^T delta_2)
g_W1 = d1.T @ X

T = lambda A: torch.tensor(A, requires_grad=True)
tW1, tW2, tw3 = T(W1), T(W2), T(w3)
tf = torch.relu(torch.relu(torch.tensor(X) @ tW1.T) @ tW2.T) @ tw3
(0.5 * ((tf - torch.tensor(y)) ** 2).mean()).backward()
err = max(np.abs(g - t.grad.numpy()).max() for g, t in [(g_W1, tW1), (g_W2, tW2), (g_w3, tw3)])
print(f"max |hand-made gradient - autograd| = {err:.1e}")

The hand-made gradient agrees with PyTorch’s autograd to machine precision (2.2 \times 10^{-16}).

2.4 Exploding and vanishing gradients

A product of L random matrices typically grows or decays geometrically in L. The initialisation decides which.

import numpy as np

rng = np.random.default_rng(0)
width, L = 200, 50
for gain in [0.8, 1.0, 1.2]:
    x = rng.normal(size=width)
    Ws, h = [], x
    for _ in range(L):                                    # forward pass, He scale times gain
        W = rng.normal(0, gain * np.sqrt(2 / width), (width, width))
        Ws.append((W, W @ h > 0)); h = np.maximum(W @ h, 0)
    g = rng.normal(size=width); g /= np.linalg.norm(g)    # backward: g <- W^T (mask * g)
    for W, mask in reversed(Ws):
        g = W.T @ (mask * g)
    print(f"gain {gain}: ||grad wrt input|| after {L} layers = {np.linalg.norm(g):.2e}"
          f"  (gain^L = {gain ** L:.2e})")

After 50 layers of width 200, the back-propagated norm is 1.8 \times 10^{-5} for a gain of 0.8, 1.3 for the He scale, and 1.2 \times 10^{4} for a gain of 1.2, in line with g^{L}.

The standard remedies follow from Proposition 2.8.

• Initialisation at the critical scale: Glorot and Bengio (2010), He et al. (2015).
• Residual connections a_{\ell + 1} = a_\ell + g_\ell(a_\ell) (He et al., 2016): each Jacobian becomes I + J_{g_\ell}, close to the identity.
• Normalisation layers, gradient clipping and gated cells (LSTM).

3. Landscape of the objective function

Whether a gradient method finds a good minimum depends on the critical points of the objective. This chapter describes them for linear networks and for wide non-linear networks.

3.1 Critical points and why they matter

3.2 Linear networks: no spurious minima, implicit regularisation

Linear models also show how the algorithm selects one minimiser among many.

import numpy as np

rng = np.random.default_rng(1)
n, p = 20, 100
X, y = rng.normal(size=(n, p)), rng.normal(size=n)
step = 1 / np.linalg.norm(X, 2) ** 2
w_min_norm = np.linalg.pinv(X) @ y
P_row = np.linalg.pinv(X) @ X                           # projector on the row space of X
for name, w in [("zero init", np.zeros(p)), ("random init", rng.normal(size=p))]:
    w0 = w.copy()
    for _ in range(5000):
        w -= step * X.T @ (X @ w - y)
    print(f"{name}: residual {np.linalg.norm(X @ w - y):.1e}, "
          f"||w - w_min_norm|| = {np.linalg.norm(w - w_min_norm):.2f}, "
          f"||w - (w_min_norm + (I-P) w0)|| = {np.linalg.norm(w - w_min_norm - w0 + P_row @ w0):.1e}")

Both runs interpolate the data. From zero, the limit is the minimum-norm solution; from a random start, it is off by 8.93 in norm, exactly the component (I - P)w_0 predicted by Proposition 3.4.

For deeper linear networks the bias is subtler, and it is governed by a conserved quantity.

From a small balanced initialisation, the product follows a preconditioned flow that favours low rank (Arora, Cohen and Hazan, 2018; Gunasekar et al., 2017). Du, Hu and Lee (2018) prove the analogous conservation, unit by unit, for ReLU networks.

3.3 Stability of minimisers in structured linear networks

Minimisers are never isolated (Corollary 2.5), so stability must be measured modulo the symmetries: two sets of factors are close if they are close after rescaling. In the rank-one case this is a statement about directions.

The constant 1/\|X\|_F blows up near the origin, the saddle of Example 2.4. Malgouyres and Landsberg (official reference 7) treat products of any number of structured factors, for instance convolutional ones. Through a tensorial lifting based on the Segre embedding, they characterise when the factors are identifiable up to rescaling.

A deep analogue of the null-space property of compressed sensing then makes the error on the factors linear in the error on the product: successful training yields stable, hence interpretable, layers.

import numpy as np

rng = np.random.default_rng(1)
u, v = rng.normal(size=8), rng.normal(size=6)
for scale in [1.0, 0.1]:
    Xs = scale * np.outer(u, v)
    noisy = Xs + 0.01 * rng.normal(size=Xs.shape)
    U, s, Vt = np.linalg.svd(noisy)
    X_hat = s[0] * np.outer(U[:, 0], Vt[0])            # best rank-one approximation
    sin_u = np.sqrt(max(0.0, 1 - (U[:, 0] @ u / np.linalg.norm(u)) ** 2))
    bound = np.linalg.norm(X_hat - Xs) / np.linalg.norm(Xs)
    print(f"||X||_F = {np.linalg.norm(Xs):5.2f}: sin(angle(u_hat, u)) = {sin_u:.4f} <= bound {bound:.4f}")

With the same noise, the factor direction is recovered to \sin\angle = 0.017 when \|X\|_F = 2.15, but only to 0.125 when \|X\|_F = 0.21, each time below the bound of Proposition 3.6.

3.4 Non-linear networks: the benefit of width

Bad critical points can therefore only occur where the features lose rank. Nguyen and Hein turn this mechanism into a statement about almost all parameters.

Venturi, Bandeira and Bruna (official reference 5) show that wide enough networks of finite intrinsic dimension have no spurious valleys; Safran and Shamir (official reference 6) that over-specified networks often start in a good basin. Width is not sufficient in general: Safran and Shamir (2018) exhibit spurious local minima in two-layer ReLU networks of moderate width.

4. Non-convex optimisation

Chapter 3 described the landscape. This chapter follows the iterates of gradient methods through it: which critical points they avoid, whether they converge, and how fast.

4.1 Gradient descent on smooth functions

The theorem says nothing about which critical point is approached, nor whether the iterates converge at all. The next two sections answer these questions.

4.2 Morse functions and strict saddles

Training objectives are never Morse, since their minimisers come in continuous families (Corollary 2.5). Lee and coauthors treat one strict saddle at a time. Panageas and Piliouras (official reference 2) cover non-isolated critical points, which gives the first statement below.

import numpy as np

rng = np.random.default_rng(0)
grad = lambda z: np.stack([z[:, 0] ** 3 - z[:, 0], z[:, 1]], axis=1)
Z = rng.uniform(-2, 2, size=(10_000, 2))           # 10 000 random initialisations
for _ in range(500):
    Z = Z - 0.1 * grad(Z)
print("limits reached:", np.unique(np.round(Z, 6) + 0.0, axis=0).tolist())
z = np.array([[0.0, 1.5]])                          # start on the stable manifold {x = 0}
for _ in range(500):
    z = z - 0.1 * grad(z)
print("start (0, 1.5) ->", np.round(z, 6).tolist())

All 10 000 random starts end at (-1, 0) or (1, 0); the start (0, 1.5), on the stable manifold, ends at the saddle.

4.3 The Kurdyka–Łojasiewicz property

Bounded gradient iterates may still fail to converge: on some smooth functions they circle forever around a ring of minimisers (Absil, Mahony and Andrews, 2005). The Kurdyka–Łojasiewicz property rules this out.

The exponent gives the rate: \vartheta = 1/2 yields linear convergence, and \vartheta \in (1/2, 1) a polynomial rate. Bolte, Sabach and Teboulle (official reference 1) isolate the three ingredients of this proof — sufficient decrease, a relative error bound, KL — and apply them to proximal alternating minimisation over blocks of variables, such as the layers of a network or the factors of a matrix factorisation.

4.4 Global convergence: least squares under surjectivity, stochastic gradient

When the Jacobian of the outputs stays surjective along training, which requires over-parameterisation, the KL inequality holds globally with exponent 1/2, and gradient descent reaches a global minimum.

Surjectivity of J needs at least as many parameters as data points (p \ge N). For a wide two-layer network, \mu is bounded below at initialisation and the Jacobian barely moves during training, the lazy regime of ch. 11.

import torch

torch.set_num_threads(1)                            # tiny model: one thread is fastest
torch.manual_seed(0)
N, d, m = 20, 20, 2000
X = torch.randn(N, d); X = X / X.norm(dim=1, keepdim=True)
y = torch.randn(N)

def outputs(theta):                                 # f(x) = a^T relu(W x) / sqrt(m)
    W, a = theta[: m * d].view(m, d), theta[m * d:]
    return torch.relu(X @ W.T) @ a / m ** 0.5

def spectrum(theta):                                # extreme eigenvalues of J J^T
    J = torch.autograd.functional.jacobian(outputs, theta.detach())
    e = torch.linalg.eigvalsh(J @ J.T)
    return e[0].item(), e[-1].item()

theta = torch.randn(m * d + m, requires_grad=True)
mu, lam = spectrum(theta)
lr = 0.2                                            # below 1 / lambda_max
opt, losses = torch.optim.SGD([theta], lr=lr), []
for t in range(201):
    loss = 0.5 * ((outputs(theta) - y) ** 2).sum()
    losses.append(loss.item())
    opt.zero_grad(); loss.backward(); opt.step()
print(f"at init: mu = {mu:.3f}, lambda_max = {lam:.2f}; after training: mu = {spectrum(theta)[0]:.3f}")
print("loss at steps 0, 50, 100, 200:", [f"{losses[k]:.1e}" for k in (0, 50, 100, 200)])
print(f"guaranteed rate 1 - lr*mu = {1 - lr * mu:.3f}; "
      f"observed rate per step = {(losses[200] / losses[100]) ** 0.01:.3f}")

With 2 000 hidden units and 20 data points, \mu = 0.274 at initialisation and 0.271 after training. The loss falls from 15 to 3.9 \times 10^{-10} in 200 steps, at an observed rate of 0.900 per step, faster than the guaranteed 0.945.

ReLU networks are not smooth, but they are definable. For such locally Lipschitz functions, Davis, Drusvyatskiy, Kakade and Lee (official reference 24) prove that the stochastic subgradient method with decreasing steps has, almost surely, only Clarke-critical limit points, under a boundedness assumption.

5. Robust deep learning I: stability, interpretability, Bayesian uncertainty

A network deployed in a hospital or a car must be accurate, but also predictable. A small change of the input should not flip the decision, and the network should signal when it does not know. This chapter introduces both sides of decision robustness: stability and uncertainty.

5.1 Decision robustness for critical systems

In medical diagnosis or autonomous driving, errors have asymmetric and sometimes irreversible costs. A deployed model must then answer three questions besides “what is the prediction?”.

• Is the decision stable under small perturbations of the input (5.1–5.2)?
• Which training data does it rest on (5.3)?
• How uncertain is it, and is the input of the kind seen in training (5.4, ch. 6, ch. 7)?

5.2 Stability to deformations

Images of the same object differ by small deformations more than by additive noise.

• Scattering networks (Bruna and Mallat, 2013; the theory is in Mallat, 2012) cascade wavelet transforms and complex moduli, then average at a scale 2^J. They are invariant to translations small compared with 2^J and Lipschitz-stable to deformations, with a bound that vanishes with the amplitude of \tau relative to 2^J and with the sizes of \nabla\tau and of the Hessian of \tau.
• Convolutional kernel representations (Bietti and Mairal, 2017) satisfy similar bounds. Pooling and patch sizes trade invariance against discriminative power, and the stability of a learned model is controlled by its norm in the associated reproducing kernel Hilbert space.

5.3 Influence functions: which training points drive a prediction?

This classical tool of robust statistics (Cook and Weisberg, 1982) explains a prediction by the training points that support it. It also finds mislabelled examples and crafts training-set attacks. For networks, H is not invertible, and Koh and Liang use a damping term and Hessian-vector products.

import numpy as np

rng = np.random.default_rng(0)
n, d, lam = 200, 5, 1e-2
X = rng.normal(size=(n, d)); w_true = rng.normal(size=d)
y = (rng.uniform(size=n) < 1 / (1 + np.exp(-X @ w_true))).astype(float)
x_test, y_test = rng.normal(size=d), 1.0

def fit(X, y, iters=30):                     # Newton's method on the L2-regularised log-loss
    w = np.zeros(d)
    for _ in range(iters):
        p = 1 / (1 + np.exp(-X @ w))
        g = X.T @ (p - y) / len(y) + lam * w
        H = (X.T * (p * (1 - p))) @ X / len(y) + lam * np.eye(d)
        w -= np.linalg.solve(H, g)
    return w, H

def test_loss(w):
    p = 1 / (1 + np.exp(-x_test @ w))
    return -np.log(p if y_test == 1 else 1 - p)

w_hat, H = fit(X, y)
p_t = 1 / (1 + np.exp(-x_test @ w_hat))
g_test = (p_t - y_test) * x_test
predicted, actual = [], []
for i in range(n):
    p_i = 1 / (1 + np.exp(-X[i] @ w_hat))
    g_i = (p_i - y[i]) * X[i] + lam * w_hat          # gradient of the i-th summand
    predicted.append(g_test @ np.linalg.solve(H, g_i) / n)   # removing z_i: eps = -1/n
    w_loo, _ = fit(np.delete(X, i, 0), np.delete(y, i))
    actual.append(test_loss(w_loo) - test_loss(w_hat))
predicted, actual = np.array(predicted), np.array(actual)
print(f"correlation(influence prediction, leave-one-out) = {np.corrcoef(predicted, actual)[0, 1]:.4f}")
top = np.argsort(-np.abs(actual))[:3]
print("three most influential points (predicted, actual):",
      [(int(i), round(float(predicted[i]), 4), round(float(actual[i]), 4)) for i in top])

On this L2-regularised logistic regression, the influence formula and 200 refits by leave-one-out agree with correlation 0.9998. For the most influential point, it predicts a test-loss change of 0.161, against 0.169 measured.

5.4 Decision uncertainty and Bayesian models

The model is linear in w but not in x: with polynomial features, Gaussian bumps or random features, it performs non-linear regression. The first lab fits it on simulated data with a gap.

import numpy as np

rng = np.random.default_rng(0)
x = np.concatenate([rng.uniform(-2, 0, 30), rng.uniform(1, 2, 15)])   # gap on (0, 1)
beta = 25.0                                          # noise precision (sigma = 0.2)
y = np.sin(2 * x) + rng.normal(0, beta ** -0.5, x.size)

centres = np.linspace(-3, 3, 25)                     # explicit embedding: Gaussian bumps
phi = lambda t: np.exp(-(np.subtract.outer(t, centres) ** 2) / (2 * 0.4 ** 2))

alpha = 1.0                                          # prior w ~ N(0, alpha^{-1} I)
Phi = phi(x)
S_N = np.linalg.inv(alpha * np.eye(centres.size) + beta * Phi.T @ Phi)
m_N = beta * S_N @ Phi.T @ y

for t in [-1.0, 0.5, 1.5, 3.0]:
    f = phi(np.array([t]))[0]
    mean, var = f @ m_N, 1 / beta + f @ S_N @ f      # predictive mean and variance
    print(f"x = {t:4.1f}: mean {mean:+.2f} (truth {np.sin(2 * t):+.2f}), "
          f"predictive std {np.sqrt(var):.2f} (noise std {beta ** -0.5:.2f})")

Where data are dense (x = -1 and x = 1.5), the predictive standard deviation is 0.22 and 0.21, barely above the noise level 0.20. It rises to 0.59 in the gap and to 1.31 outside the data, at x = 3: the epistemic term does its job.

6. Robust deep learning II: Bayesian neural networks

For a network, the posterior is neither Gaussian nor computable. This chapter presents the three approximations used in practice — Laplace, variational and Monte Carlo dropout — first on logistic regression, where they can be checked.

6.1 The Laplace approximation

The approximation pulls the probability towards 1/2 where s_a^2 is large, without changing the predicted class.

import numpy as np

rng = np.random.default_rng(0)
n = 100                                               # two Gaussian classes in the plane
X = np.vstack([rng.normal([-1, 0], 0.7, (n, 2)), rng.normal([1, 0], 0.7, (n, 2))])
y = np.r_[np.zeros(n), np.ones(n)]
Phi = np.c_[np.ones(2 * n), X]                        # features (1, x1, x2)
alpha = 1.0                                           # prior w ~ N(0, alpha^{-1} I)
sigmoid = lambda a: 1 / (1 + np.exp(-a))

w = np.zeros(3)                                       # MAP by Newton's method
for _ in range(25):
    p = sigmoid(Phi @ w)
    H = (Phi.T * (p * (1 - p))) @ Phi + alpha * np.eye(3)
    w -= np.linalg.solve(H, Phi.T @ (p - y) + alpha * w)
S = np.linalg.inv(H)                                  # Laplace: q(w) = N(w_MAP, H^{-1})

for x in [np.array([0.5, 0.0]), np.array([0.5, 8.0]), np.array([6.0, 8.0])]:
    f = np.r_[1.0, x]
    mu_a, s2_a = f @ w, f @ S @ f
    probit = sigmoid(mu_a / np.sqrt(1 + np.pi * s2_a / 8))
    mc = sigmoid(rng.multivariate_normal(w, S, 20_000) @ f).mean()
    print(f"x = ({x[0]:.1f}, {x[1]:.1f}): MAP {sigmoid(mu_a):.3f} | Laplace, probit {probit:.3f} | "
          f"Laplace, Monte Carlo {mc:.3f} | var(a) = {s2_a:.2f}")

Near the data, at the point (0.5, 0), the MAP gives 0.869 and the Laplace predictive 0.864. Far along the uninformative direction, at (0.5, 8), the activation variance is 6.8, and the Laplace predictive moves from 0.345 to 0.417, towards 1/2. The probit formula and a Monte Carlo average over q agree within 0.004.

For networks, Laplace is applied to the last layer or with Kronecker-factored Hessians (Ritter, Botev and Barber, 2018; Daxberger et al., 2021).

6.2 Variational inference and Bayes by Backprop

6.3 Dropout: a regulariser and a variational approximation

Dropout (Srivastava et al., 2014) multiplies each unit by an independent Bernoulli mask \delta \sim \mathcal{B}(q), divided by the keep probability q, during training. On a linear model, its effect is an explicit penalty.

Dropout is thus a ridge penalty weighted by the energy of each feature; Wager, Wang and Liang (2013) extend this reading to generalised linear models. Its Bayesian reading is due to Gal and Ghahramani.

The second lab implements a LinearVariational layer and compares it with MC dropout on a one-dimensional regression with a gap.

import torch
import torch.nn as nn

torch.set_num_threads(1)                              # tiny model: one thread is fastest
torch.manual_seed(0)
x = torch.cat([torch.empty(40).uniform_(-3, -1), torch.empty(40).uniform_(1, 3)])[:, None]
y = torch.sin(x) + 0.1 * torch.randn_like(x)          # gap in the data around 0

class LinearVariational(nn.Module):
    """Mean-field Gaussian q(W) = N(mu, softplus(rho)^2), prior N(0, 1) (Bayes by Backprop)."""
    def __init__(self, n_in, n_out):
        super().__init__()
        self.mu = nn.Parameter(0.3 * torch.randn(n_out, n_in + 1))
        self.rho = nn.Parameter(torch.full((n_out, n_in + 1), -4.0))
    def forward(self, h):
        sigma = nn.functional.softplus(self.rho)
        W = self.mu + sigma * torch.randn_like(sigma)          # reparameterisation trick
        self.kl = (0.5 * (sigma ** 2 + self.mu ** 2 - 1) - torch.log(sigma)).sum()
        return nn.functional.linear(h, W[:, :-1], W[:, -1])

def train(model, loss_fn, steps=1000):
    opt = torch.optim.Adam(model.parameters(), lr=1e-2)
    for _ in range(steps):
        opt.zero_grad(); loss_fn(model).backward(); opt.step()

bnn = nn.Sequential(LinearVariational(1, 32), nn.Tanh(), LinearVariational(32, 1))
def neg_elbo(model, noise_sd=0.1):                    # -ELBO = expected NLL + KL
    nll = ((model(x) - y) ** 2).sum() / (2 * noise_sd ** 2)
    return nll + sum(layer.kl for layer in model if isinstance(layer, LinearVariational))
train(bnn, neg_elbo)

mcd = nn.Sequential(nn.Linear(1, 32), nn.Tanh(), nn.Dropout(0.1), nn.Linear(32, 1))
opt_loss = lambda model: ((model(x) - y) ** 2).mean() + 1e-4 * sum((p ** 2).sum() for p in model.parameters())
train(mcd, opt_loss)                                  # dropout + weight decay

grid = torch.tensor([[-2.0], [0.0], [2.0], [5.0]])
with torch.no_grad():
    mcd.train()                                       # keep dropout active at test time
    for name, model in [("Bayes by Backprop", bnn), ("MC dropout", mcd)]:
        draws = torch.stack([model(grid) for _ in range(500)]).squeeze(-1)
        err = (draws.mean(0) - torch.sin(grid.squeeze())).abs()
        print(f"{name:17s} |error| / std at x = -2, 0, 2, 5:",
              "  ".join(f"{e:.2f}/{s:.2f}" for e, s in zip(err.tolist(), draws.std(0).tolist())))

Inside the data, both methods are honest: at x = -2 and x = 2, the error is at most the standard deviation. At x = 5, far outside, the error reaches 0.62 (Bayes by Backprop) and 1.20 (MC dropout), against standard deviations of 0.12 and 0.15. Both approximations under-estimate epistemic uncertainty away from the data; Exercise 12 studies the role of the prior and of the noise level.

7. Robust deep learning III: uncertainty in practice

Uncertainties must be checked against data. This chapter gives the metrics and the practical tools.

7.1 Metrics for regression

A network with two outputs (\mu, s), trained on the NLL, therefore learns the aleatoric variance (Gneiting and Raftery, 2007, for the theory of proper scores). Calibrating the intervals afterwards is studied by Kuleshov, Fenner and Ermon (2018).

7.2 Ensembles and evidential models

Deep ensembles (Lakshminarayanan, Pritzel and Blundell, 2017) train M networks from different random initialisations, independently. The disagreement between members is a strong epistemic signal, and ensembles are among the most reliable methods under distribution shift (Ovadia et al., 2019).

7.3 Calibration

Guo, Pleiss, Sun and Weinberger (official reference 19) observe that modern deep networks are overconfident. Their temperature scaling divides the logits by a single scalar T, fitted by minimising the NLL on a validation set.

7.4 Failure prediction

ConfidNet (Corbière et al., official reference 20) exploits this: an auxiliary network, fed with the features of the classifier, is trained to regress the TCP on the training set. At test time its output ranks the predictions by reliability, and it detects failures better than the MCP.

7.5 Out-of-distribution detection

ODIN (Liang, Li and Srikant, official reference 21) takes the maximum softmax probability at a high temperature T, typically 1000, on an input moved by a small signed-gradient step that increases the score — more so for in-distribution inputs. The temperature has a first-order explanation.

The third lab runs these tools on the scikit-learn digits: a network is trained on the digits 0–4, and the digits 5–9 play the role of out-of-distribution inputs.

import numpy as np
import torch
import torch.nn as nn
from sklearn.datasets import load_digits
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split

torch.set_num_threads(1)                              # tiny model: one thread is fastest
torch.manual_seed(0)
X, y = load_digits(return_X_y=True)
X = torch.tensor(X / 16.0, dtype=torch.float32); y = torch.tensor(y)
inn = y < 5                                           # in-distribution: digits 0-4
X_ood = X[~inn]                                       # out-of-distribution: digits 5-9
X_tr, X_te, y_tr, y_te = train_test_split(X[inn], y[inn], test_size=0.5, random_state=0)
X_val, y_val, X_te, y_te = X_te[:200], y_te[:200], X_te[200:], y_te[200:]

def make_net():
    net = nn.Sequential(nn.Linear(64, 128), nn.ReLU(), nn.Linear(128, 5))
    opt = torch.optim.Adam(net.parameters(), lr=1e-2)
    for _ in range(300):                              # full-batch training, deliberately long
        opt.zero_grad(); nn.functional.cross_entropy(net(X_tr), y_tr).backward(); opt.step()
    return net

def ece(probs, labels, bins=10):
    conf, pred = probs.max(1)
    edges, total = torch.linspace(0, 1, bins + 1), 0.0
    for lo, hi in zip(edges[:-1], edges[1:]):
        b = (conf > lo) & (conf <= hi)
        if b.any():
            total += b.float().mean() * abs((pred[b] == labels[b]).float().mean() - conf[b].mean())
    return float(total)

net = make_net()
with torch.no_grad():
    logits_val, logits_te = net(X_val), net(X_te)
T = torch.ones(1, requires_grad=True)                 # temperature scaling on the validation set
opt = torch.optim.LBFGS([T], lr=0.1, max_iter=200)
def closure():
    opt.zero_grad(); l = nn.functional.cross_entropy(logits_val / T, y_val); l.backward(); return l
opt.step(closure)
p1, pT = logits_te.softmax(1), (logits_te / T.detach()).softmax(1)
acc = (p1.argmax(1) == y_te).float().mean()
print(f"accuracy {acc:.3f}; ECE {ece(p1, y_te):.3f} -> {ece(pT, y_te):.3f} after T = {T.item():.2f}")

wrong = (p1.argmax(1) != y_te).numpy()
print(f"failure prediction AUROC with MSP: {roc_auc_score(wrong, -p1.max(1).values.numpy()):.3f}")

def odin_score(x, temp=1000.0, eps=0.002):          # ODIN: temperature + input perturbation
    x = x.clone().requires_grad_(True)
    out = net(x) / temp
    nn.functional.cross_entropy(out, out.argmax(1)).backward()
    with torch.no_grad():
        return (net(x - eps * x.grad.sign()) / temp).softmax(1).max(1).values

labels = np.r_[np.zeros(len(X_te)), np.ones(len(X_ood))]    # 1 = out-of-distribution
with torch.no_grad():
    msp = torch.cat([net(X_te), net(X_ood)]).softmax(1).max(1).values
odin = torch.cat([odin_score(X_te), odin_score(X_ood)])
ens = torch.stack([m(torch.cat([X_te, X_ood])).softmax(1) for m in [net] + [make_net() for _ in range(4)]]).mean(0)
for name, s in [("MSP", msp), ("ODIN", odin), ("ensemble of 5", ens.detach().max(1).values)]:
    print(f"OOD detection AUROC, {name:13s}: {roc_auc_score(labels, -s.numpy()):.3f}")

The network reaches 99.2 % test accuracy. Temperature scaling finds T = 1.53, a sign of overconfidence, and lowers the ECE from 0.007 to 0.004. The MCP ranks errors with an AUROC of 0.994, a fragile figure since the 251 test digits contain only two errors. For OOD detection, the AUROC is 0.945 with the maximum softmax probability, 0.959 with ODIN and 0.947 with an ensemble of five networks. Exercise 14 adds a ConfidNet head.

8. Expressivity of feed-forward networks

Which functions can a network represent, and at what size? Shallow networks are universal; size and depth decide the cost.

8.1 Universal approximation

For ReLU, a complete proof only uses tools from ch. 0 and ch. 1.

Universality says nothing about size, which may grow exponentially with the dimension; Barron exhibits a class where it does not.

8.2 A quantitative result in L2: Barron’s theorem

The dimension enters only through C_f. Barron also shows that n fixed basis functions cannot beat order (1/n)^{2/d} uniformly over the class: adapting the units to f defeats the curse of dimensionality.

8.3 Depth separation

The construction is due to Telgarsky (2016). Eldan and Shamir (official reference 9) prove a high-dimensional analogue: a radial function on \mathbb{R}^d is computed by a network with two hidden layers of width polynomial in d, but no network with one hidden layer approximates it to better than a constant unless its width is exponential in d.

import numpy as np

relu = lambda t: np.maximum(t, 0.0)
tent = lambda t: 2 * relu(t) - 4 * relu(t - 0.5)      # g: one hidden layer of width 2

x = np.linspace(0, 1, 2 ** 12 + 1)
k = 8
h = x.copy()
for _ in range(k):                                    # depth-k, width-2 network: g o ... o g
    h = tent(h)

# Best continuous piecewise-affine fit with p uniform pieces (least squares on hat functions).
for p in [16, 63, 255, 256]:
    knots = np.linspace(0, 1, p + 1)
    hats = np.array([np.interp(x, knots, np.eye(p + 1)[j]) for j in range(p + 1)]).T
    f = hats @ np.linalg.lstsq(hats, h, rcond=None)[0]
    print(f"p = {p:3d} pieces: L1 error {np.trapezoid(np.abs(f - h), x):.4f}"
          f"  (Theorem 8.8 guarantees >= 1/16 = 0.0625 when p <= {2 ** (k - 2) - 1})")

# Yarotsky's approximation of x^2: f_m(x) = x - sum_s g_s(x) / 4^s.
for m in [1, 2, 4, 6]:
    g, f_m = x.copy(), x.copy()
    for s in range(1, m + 1):
        g = tent(g)
        f_m -= g / 4 ** s
    print(f"m = {m}: sup |f_m(x) - x^2| = {np.abs(f_m - x ** 2).max():.2e}"
          f"  (bound 2^(-2m-2) = {2.0 ** (-2 * m - 2):.2e})")

For k = 8, least-squares fits with 16 or 63 uniform pieces do no better than the constant 1/2, with an L^1 error of 0.25; 255 pieces still leave 0.171, and only 256 pieces fit exactly.

8.4 Super-approximation by deep networks

The code confirms the bound for m = 1, 2, 4, 6. Since xy = ((x + y)^2 - x^2 - y^2)/2, products, polynomials and local Taylor expansions follow at a logarithmic extra cost.

9. Generalisation error of feed-forward networks

The estimation error of Proposition 1.5 is controlled by the uniform deviation between risk and empirical risk over the class. This chapter bounds it for binary classification, in general and then for networks. The loss takes values in [0, 1].

9.1 Risk bounds and Rademacher complexity

Talagrand’s contraction lemma transfers such bounds to losses: if \phi is \rho-Lipschitz, composing a class with \phi multiplies its Rademacher complexity by at most \rho.

9.2 VC dimension

9.3 Complexity of feed-forward networks

For a network with W = 10^6 weights and L = 10 layers, WL\log W \approx 1.4 \times 10^8, against n = 5 \times 10^4 training images: Corollary 9.7 is vacuous. Norm-based bounds do not count parameters.

With a margin loss and the contraction lemma, such bounds become margin bounds: the test error is bounded by the fraction of training points of margin below \gamma, plus a complexity term divided by \gamma\sqrt{n} (Bartlett, Foster and Telgarsky, 2017, with spectral norms).

import numpy as np
import torch
import torch.nn as nn
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split

rng = np.random.default_rng(0)

# 1) Empirical Rademacher complexity of {x -> <w, x> : ||w|| <= M}: closed form vs bound.
n, d, M = 200, 50, 1.0
X = rng.normal(size=(n, d)) / np.sqrt(d)                      # ||x_i|| close to 1
sigma = rng.choice([-1.0, 1.0], size=(5000, n))
rad = M * np.linalg.norm(sigma @ X, axis=1).mean() / n         # sup_w <w, sum sigma_i x_i> / n
B = np.linalg.norm(X, axis=1).max()
print(f"empirical Rademacher complexity {rad:.4f} <= M B / sqrt(n) = {M * B / np.sqrt(n):.4f}")

# 2) Same network, true labels vs random labels (Zhang et al., 2017, on a small scale).
torch.set_num_threads(1)                                      # tiny model: one thread is fastest
Xd, yd = load_digits(return_X_y=True)
Xd = torch.tensor(Xd / 16.0, dtype=torch.float32)
for name, labels in [("true labels", yd), ("random labels", rng.permutation(yd))]:
    torch.manual_seed(0)
    X_tr, X_te, y_tr, y_te = train_test_split(Xd, torch.tensor(labels), test_size=0.3, random_state=0)
    net = nn.Sequential(nn.Linear(64, 256), nn.ReLU(), nn.Linear(256, 10))
    opt = torch.optim.Adam(net.parameters(), lr=1e-2)
    for _ in range(400):                                       # full batch, no regularisation
        opt.zero_grad(); nn.functional.cross_entropy(net(X_tr), y_tr).backward(); opt.step()
    acc = lambda A, b: (net(A).argmax(1) == b).float().mean().item()
    print(f"{name:13s}: train accuracy {acc(X_tr, y_tr):.3f}, test accuracy {acc(X_te, y_te):.3f}")

The Monte Carlo complexity, 0.070, sits below the bound 0.088 of Proposition 9.4. The same network and algorithm fit true and random labels perfectly, with test accuracies of 97.8 % and 8.1 %. A bound that depends only on the class must hold for both runs, so it cannot be smaller than the random-label gap; norms, margins and the algorithm must enter (Exercise 16).

10. Open questions on generalisation; double descent

Chapter 9 ends on a paradox. This chapter surveys what is known about it, then computes exactly the risk of the simplest interpolating model, which already displays double descent.

10.1 A tour of open questions

Kawaguchi, Kaelbling and Bengio (official reference 11) organise the debate around a few points.

• The random-label experiment of Zhang et al. (2017) shows that generalisation depends on the pair formed by the data and the algorithm, not on the class alone.
• Uniform bounds over the class are vacuous. Data-dependent bounds (norms, margins, PAC-Bayes: Dziugaite and Roy, 2017) and algorithm-dependent bounds are partial answers.
• Explaining generalisation and guaranteeing it are different questions. A held-out set already gives a non-vacuous guarantee, as below.
• The algorithm selects one interpolant among many (Proposition 3.4); which one, and why it generalises, is the question of implicit regularisation.

10.2 Double descent

Belkin, Hsu, Ma and Mandal (official reference 29) observed, on random features and on networks, that the test risk plotted against the number p of parameters is U-shaped for p < n, peaks near the interpolation threshold p = n, then decreases again. Nakkiran et al. (2020) report the same curve for deep networks. Linear regression already shows it.

Let x \sim \mathcal{N}(0, I_p) and y = x^\top \beta + \varepsilon, with noise \varepsilon \sim \mathcal{N}(0, \sigma^2) and \|\beta\| = r. From n samples, let \hat\beta = X^+ y.

This is least squares when p < n, and the minimum-norm interpolant reached by gradient descent from zero when p > n (Proposition 3.4). The excess risk is \|\hat\beta - \beta\|^2.

import numpy as np

rng = np.random.default_rng(0)
n, sigma, r = 100, 0.5, 1.0                       # samples, noise level, signal norm ||beta||

def exact_risk(p):                                # Gaussian design, min-norm least squares
    if p < n - 1:
        return sigma ** 2 * p / (n - p - 1)
    if p > n + 1:
        return r ** 2 * (1 - n / p) + sigma ** 2 * n / (p - n - 1)
    return np.inf

for p in [10, 50, 90, 98, 102, 110, 200, 400, 1000]:
    risks = []
    for _ in range(200):
        beta = rng.normal(size=p); beta *= r / np.linalg.norm(beta)
        X = rng.normal(size=(n, p))
        y = X @ beta + sigma * rng.normal(size=n)
        beta_hat = np.linalg.pinv(X) @ y          # min-norm interpolator when p > n
        risks.append(np.sum((beta_hat - beta) ** 2))   # excess risk for isotropic x
    print(f"p/n = {p / n:5.2f}: simulated excess risk {np.mean(risks):6.3f}, "
          f"formula {exact_risk(p):6.3f}")

With 100 samples, noise level 0.5 and signal norm 1, simulation and formula agree away from the threshold: 0.255 at p/n = 0.5, 0.753 at p/n = 2, 0.928 at p/n = 10. The minimum over p > n is at p = 2n, as Corollary 10.3 predicts for a signal twice as strong as the noise.

Near p = n both explode: the formula gives 24.5 and 25.0 at p = 98 and p = 102, and the simulated mean, about 20, is noisy because the risk has heavy tails. The link with random-matrix spectra is developed in Large Random Matrices and Applications to Machine Learning.

11. Research directions and open problems

This chapter is for self-study. It surveys directions in which the questions of the course are still open, with entry points into the literature. It uses ch. 3, 4, 9 and 10, and Exercise 18 goes with it.

11.1 Implicit bias in classification

Proposition 3.4 showed that gradient descent selects the minimum-norm interpolant in least squares. In classification, the selected solution is a maximum-margin one.

Training long after the training error reaches zero thus keeps increasing the margin, which the margin bounds of ch. 9 reward. Lyu and Li (2020) extend the picture to homogeneous networks, such as ReLU networks without biases: gradient flow converges in direction to a KKT point of a margin-maximisation problem. Whether this point generalises, and how the architecture shapes the implicit norm, are open questions.

11.2 Infinite-width limits: lazy training and mean field

Two scalings of wide networks lead to two different theories.

• Neural tangent kernel. With the 1/\sqrt{m} scaling of the code of ch. 4, the matrix J J^\top of Theorem 4.8 converges, as the width grows, to the Gram matrix of a fixed kernel, the neural tangent kernel of Jacot, Gabriel and Hongler (2018). Training then behaves like kernel regression, and Du, Zhai, Póczos and Singh (2019) prove global convergence of gradient descent for wide two-layer networks.
• Lazy training. Chizat, Oyallon and Bach (2019) show that this regime is generic: any model enters it when the scaling makes the parameters move little. The network then behaves as its linearisation and learns no new features, which often hurts performance in practice.
• Mean field. With a 1/m scaling, the empirical distribution of the neurons of a two-layer network follows a Wasserstein gradient flow (Mei, Montanari and Nguyen, 2018; Chizat and Bach, 2018). In this regime features are learned; Chizat and Bach prove that, under conditions on the activation and the initial support, the limit, when it exists, is a global minimiser.

Open problems include quantitative rates for the mean-field dynamics, extensions to deep networks, and a theory of the intermediate regimes in which practical networks operate.

11.3 Benign overfitting

Theorem 10.2 shows interpolation with a bounded risk, but not consistency. Bartlett, Long, Lugosi and Tsigler (2020) characterise the covariances of Gaussian features for which the minimum-norm interpolant is consistent. The noise must be absorbed by many directions of small variance, a condition expressed through two effective ranks of the covariance. Extending such characterisations beyond linear and kernel models is open.

11.4 The edge of stability

The descent lemma (Proposition 0.2) needs a step below 2/L. Cohen, Kaur, Li, Kolter and Talwalkar (2021) observe that full-batch gradient descent on networks behaves otherwise. The largest eigenvalue of the Hessian rises until it reaches 2/\eta, then hovers there, while the loss keeps decreasing non-monotonically. Explaining this self-stabilisation, and its effect on the solutions found, is an active topic.

11.5 Non-smooth automatic differentiation

At the kinks of ReLU, back-propagation applies the chain rule to objects that are not derivatives. Work by Bolte and Pauwels (2021) shows that its output is an element of a conservative set-valued field. For definable functions (Proposition 4.6), conservative fields coincide with the gradient almost everywhere. Stochastic gradient methods driven by them converge to points that are critical for the field, which justifies the practice of training ReLU networks with automatic differentiation.

11.6 Non-vacuous bounds and the role of the algorithm

Dziugaite and Roy (2017) optimise a PAC-Bayes bound for a stochastic network trained on MNIST and obtain a non-vacuous guarantee. Arora, Ge, Neyshabur and Zhang (2018) derive bounds from the compressibility of trained networks. Hardt, Recht and Singer (2016) bound the generalisation error of stochastic gradient descent through its algorithmic stability. No bound is yet known to predict reliably which of two practical architectures generalises better.

11.7 Uncertainty with guarantees

The approximate posteriors of ch. 6 come without guarantees. Conformal prediction provides a guarantee that holds for any model, at the price of exchangeability (Vovk, Gammerman and Shafer, 2005; Angelopoulos and Bates, 2023).

import numpy as np
from sklearn.datasets import load_diabetes
from sklearn.linear_model import Ridge

rng = np.random.default_rng(0)
X, y = load_diabetes(return_X_y=True)                 # 442 patients, bundled with scikit-learn
alpha, covered, widths = 0.1, [], []
for trial in range(1000):                             # random splits: train / calibration / test
    idx = rng.permutation(len(y))
    tr, cal, te = idx[:200], idx[200:321], idx[321:]
    model = Ridge(alpha=1.0).fit(X[tr], y[tr])
    scores = np.abs(y[cal] - model.predict(X[cal]))   # conformity scores on the calibration set
    n = len(cal)
    q = np.sort(scores)[int(np.ceil((n + 1) * (1 - alpha))) - 1]
    pred = model.predict(X[te])
    covered.append(np.mean(np.abs(y[te] - pred) <= q))
    widths.append(2 * q)
print(f"target coverage {1 - alpha:.2f}; empirical coverage {np.mean(covered):.3f} "
      f"(sd over splits {np.std(covered):.3f}); mean interval width {np.mean(widths):.0f}")

Over 1000 random splits of the diabetes data, the empirical coverage is 0.901 for a target of 0.90. The guarantee is marginal, averaged over the data. Foygel Barber, Candès, Ramdas and Tibshirani (2021) show that exact conditional coverage, given X = x, is impossible without further assumptions; approximate conditional guarantees and conformal methods under distribution shift are active topics.

For adversarial robustness, randomised smoothing gives certificates. Cohen, Rosenfeld and Kolter (2019) classify x by the most likely output of a base classifier under Gaussian noise \mathcal{N}(0, \sigma^2 I), and certify the decision in a Euclidean ball whose radius is proportional to \sigma.

11.8 Theory of generative adversarial networks

Proposition 1.9 assumes an optimal discriminator over all functions. With discriminators restricted to a class of networks, Arora, Ge, Liang, Ma and Zhang (2017) show that the training objective can be small while the generator has a support far too small to represent the data. Generalisation of generative models, and the equilibria of the GAN game, remain only partly understood. The diffusion models that replaced GANs in many applications are treated in Stochastic Calculus in Machine Learning and Generative Models for Images.

11.9 Explaining predictions by input attributions

Influence functions (Theorem 5.5) explain a prediction by training points. Saliency maps explain it by input coordinates, through the gradient of the class score with respect to the input (Simonyan, Vedaldi and Zisserman, 2014), or its integral along a path from a baseline, integrated gradients (Sundararajan, Taly and Yan, 2017). Whether such attributions are faithful to the computation of the network is debated; these methods are developed in Multimodal Explainable AI.

11.10 A short list of open problems

1. Explain why stochastic gradient descent on over-parameterised networks finds solutions that generalise, outside the lazy and linear regimes.
2. Give quantitative global convergence results for deep networks of realistic width, from standard initialisations.
3. Find generalisation bounds that are non-vacuous and predict the ranking of architectures and training choices.
4. Obtain uncertainty estimates for deep networks that remain calibrated, conditionally on the input, under distribution shift.
5. Decide whether gradient methods can find the efficient deep approximants of ch. 8, which are typically not found from random initialisations.

Exercises

1. ★ Size of a test set. How many test examples guarantee, with probability 95 %, that the test error of a fixed classifier is within 1 % of its risk (Proposition 1.3)? Within 0.1 %?

   Solution: we need \sqrt{\log(2/\delta)/(2m)} \le \varepsilon, that is m \ge \log(40)/(2\varepsilon^2). For 1 %, this gives m \ge 3.689 / (2 \times 10^{-4}) \approx 18\,445 .

   For 0.1 %, multiply by 100: about 1.84 million examples.

2. ★ Pieces of a small network. Let f(x) = \sigma(x) - 2\sigma(x - 1) + \sigma(x - 2) with the ReLU \sigma. Draw f, count its affine pieces and compare with Proposition 1.11.

   Solution: the kinks are at 0, 1 and 2, with slope jumps +1, -2, +1, so the slopes are 0, 1, -1, 0. The function is a hat supported on [0, 2], with peak 1 at x = 1. It has 4 pieces, the maximum m + 1 for m = 3 units.

3. ★ Back-propagation by hand. Let f(x) = w_2\, \sigma(w_1 x + b_1) with w_1 = 2, b_1 = -1, w_2 = 3, one example (x, y) = (1, 1) and the loss \frac12 (f - y)^2. Run Algorithm 2.6 and check one derivative by finite differences.

   Solution: forward, z_1 = 1, a_1 = 1, f = 3. Backward, \delta_2 = f - y = 2, so \partial/\partial w_2 = \delta_2 a_1 = 2.

   Then \delta_1 = \sigma'(z_1)\, w_2\, \delta_2 = 6, so \partial/\partial w_1 = \delta_1 x = 6 and \partial/\partial b_1 = 6. Check: replacing w_1 by 2 + h gives the loss \frac12 (2 + 3h)^2, whose derivative at 0 is 6.

4. ★ Initialisation for leaky ReLU. Let \sigma(t) = \max(t, at) with 0 \le a < 1. For a symmetric z, show that the second moment of \sigma(z) is (1 + a^2)/2 times that of the input, and find the weight variance s^2/n that preserves the second moment (Proposition 2.9).

   Solution: split according to the sign of z. The positive part contributes \mathbb{E}[z^2 \mathbb{1}_{z > 0}], the negative part a^2 times the same quantity by symmetry, and each is half of \mathbb{E}[z^2]. The recursion becomes q_{\ell+1} = s^2 (1 + a^2) q_\ell / 2, so s^2 = \frac{2}{1 + a^2} .

5. ★ Bayesian linear regression in one dimension. Model y = wx + \varepsilon with \beta = 4 (noise standard deviation 0.5), prior w \sim \mathcal{N}(0, 1), and data x = (1, 2), y = (1, 3). Compute the posterior and the predictive distribution at x = 3, and split its variance (Theorem 5.8).

   Solution: S_N^{-1} = 1 + 4 \times (1 + 4) = 21 and m_N = 4 \times (1 + 6)/21 = 4/3. At x = 3, the predictive mean is 4 and the variance is \frac14 + \frac{9}{21} \approx 0.25 + 0.43 = 0.68 .

   The epistemic part already exceeds the aleatoric one at x = 3, outside the data.

6. ★ Calibration by hand. Six predictions have confidences 0.95, 0.9, 0.9, 0.6, 0.55, 0.5 and are correct, respectively, yes, yes, no, yes, no, no. Compute the ECE with the bins [0.5, 0.75] and (0.75, 1], and say what temperature scaling with T > 1 changes.

   Solution: the high bin has mean confidence 0.917 and accuracy 0.667; the low bin, 0.55 and 0.333. Hence \mathrm{ECE} = \tfrac12 \times 0.25 + \tfrac12 \times 0.217 \approx 0.208 .

   The model is overconfident in both bins. A temperature T > 1 lowers all confidences; the accuracy, 3/6, is unchanged (Proposition 7.5).

7. ★★ The scalar network, again. For F(a, b) = (ab - 1)^2, compute the Hessian at (1, 1) and show that it is singular; explain the singular direction; is F a Morse function? For G(a, b, c) = (abc - 1)^2, show that the Hessian vanishes at the origin.

   Solution: the Hessian is 2\begin{pmatrix} b^2 & 2ab - 1 \\ 2ab - 1 & a^2 \end{pmatrix}, equal at (1, 1) to twice the all-ones matrix, with eigenvalues 4 and 0. The null direction (1, -1) is tangent to the rescaling orbit (c, 1/c) at c = 1.

   The critical points are degenerate, so F is not Morse. For G, write G = 1 - 2abc + (abc)^2: its lowest-order non-constant term is cubic, so all second derivatives vanish at 0 — a degenerate saddle, outside the scope of Theorem 4.3.

8. ★★ Counting pieces. Prove Proposition 8.7 in detail. Deduce that a one-hidden-layer ReLU network computing the sawtooth g^k exactly needs at least 2^k - 1 units, and that a network of depth L and width w computing it needs (2w)^L \ge 2^k.

   Hints and expected result: if two piecewise-affine functions have N_1 and N_2 pieces, their sum has at most N_1 + N_2 - 1 pieces (union of breakpoints). The ReLU of a function with N pieces has at most 2N pieces. Induct on the layers. The sawtooth has 2^k pieces with distinct slopes on adjacent pieces, so no fewer pieces can represent it.

9. ★★ Balancedness in depth. For W = W_L \cdots W_1 and the gradient flow of \mathcal{L}(W) in the factors, show that W_{j+1}^\top W_{j+1} - W_j W_j^\top is conserved for every j (generalising Proposition 3.5).

   Solution: let A_j = W_L \cdots W_{j+1} and B_j = W_{j-1} \cdots W_1, so that the flow is \dot W_j = -A_j^\top \nabla B_j^\top. Using A_j = A_{j+1} W_{j+1} and B_{j+1} = W_j B_j, both derivatives equal -A_j^\top \nabla B_{j+1}^\top - B_{j+1} \nabla^\top A_j .

10. ★★ A Polyak–Łojasiewicz region. For F(a, b) = \frac12 (ab - 1)^2, show that \|\nabla F\|^2 = 2F\,(a^2 + b^2). Deduce linear convergence of gradient descent on any region a^2 + b^2 \ge c that contains the iterates, and discuss a start near the saddle.

    Solution: \nabla F = (ab - 1)(b, a), hence the identity, and the PL inequality with constant c on the region. Theorem 4.8 gives a rate 1 - \eta c.

    From a small balanced start a_0 = b_0 = t_0, the iterates stay balanced and t grows like t_0 (1 + \eta)^k. Leaving the saddle region takes about \log(1/t_0)/\eta steps: the PL constant degenerates near the saddle.

11. ★★ The dropout penalty. Two features take the values (1, 1, 1, 1) and (1, 0, 0, 0) on four examples, and the keep probability is q = 0.5. Write the penalty of Proposition 6.6 and compare it with ridge. What happens with standardised features?

    Solution: the penalty is \frac{1 - q}{q}(4 w_1^2 + w_2^2) = 4w_1^2 + w_2^2: the rare feature is penalised four times less per unit weight than with an isotropic ridge of the same strength on w_1. If every feature satisfies \sum_i x_{ij}^2 = n, dropout is exactly ridge with \lambda = n(1 - q)/q.

12. ★★ Bayes by Backprop against MC dropout (Python). In the second code block of ch. 6, use a prior \mathcal{N}(0, s_0^2) with s_0 \in \{0.1, 1, 3\}, then dropout rates 0.1 and 0.5. Report the ratio error/standard deviation at x = 0 and x = 5.

    Hints and expected result: the KL term becomes \sum_j \Big(\log\frac{s_0}{\sigma_j} + \frac{\sigma_j^2 + \mu_j^2}{2 s_0^2} - \frac12\Big).

    In our runs, the ratio at x = 5 stays between 5 and 9 for every prior and both dropout rates: neither approximation is calibrated far from the data.

    Widening the prior from 0.1 to 1 roughly doubles the spread of Bayes by Backprop in the gap (x = 0), but leaves it unchanged at x = 5. A dropout rate of 0.5 raises the spread at x = 5 only from 0.15 to 0.19. One reason is that the tanh units saturate far from the data, so the spread there comes from the output layer alone.

13. ★★ The ODIN perturbation. Prove Proposition 7.9. Then let u = \nabla_x \log S(x; T) and show that the ODIN step \tilde x = x + \varepsilon\, \mathrm{sign}(u) increases \log S, at first order, by \varepsilon \|u\|_1.

    Solution: the first part is the expansion e^{-v} = 1 - v + O(v^2) in each term of the denominator. For the second, a first-order Taylor expansion gives \log S(\tilde x) \approx \log S(x) + \varepsilon \langle u, \mathrm{sign}(u)\rangle = \log S(x) + \varepsilon \|u\|_1 .

    Liang et al. observe larger gradient norms on in-distribution inputs, which therefore gain more.

14. ★★ A ConfidNet head on the digits (Python). In the lab of ch. 7, freeze the classifier and train a small network on its hidden features to regress the true class probability, with the square loss. Compare its failure-prediction AUROC with that of the maximum class probability.

    Hints and expected result: training errors are almost absent, so the TCP targets are close to 1 on the training set; train the head on the validation half instead. The lab’s test set holds only two errors among 251 digits, so the AUROC of both criteria is close to 1 and the comparison is meaningless. A harder task separates them, for instance with 20 % of the training labels flipped, or with the classifier trained for only a few steps. Report bootstrap intervals.

15. ★★★ The Barron constant of a Gaussian. For f(x) = \exp(-\|x\|^2/2) on \mathbb{R}^d, compute C_f (Definition 8.3). Deduce how many units Theorem 8.5 needs for an L^2 error \varepsilon on the unit ball, and compare with a grid of piecewise-affine interpolation. Which functions have an infinite Barron constant?

    Hints and expected result: \hat f is the standard Gaussian density, so C_f = \mathbb{E}\|G\| for G \sim \mathcal{N}(0, I_d), close to \sqrt d. Theorem 8.5 then needs about 4d/\varepsilon^2 units.

    A grid with error of order h^2 needs about \varepsilon^{-d/2} cells. Functions with kinks, such as |x_1|, have no integrable first Fourier moment.

16. ★★★ Is the random-label network more complex? (Python). In the experiment of ch. 9, compute for both trained networks the product of the Frobenius norms of the weight matrices, the minimum normalised margin on the training set, and the bound of Theorem 9.9 combined with a margin loss.

    Hints and expected result: the network trained on random labels has larger norms and smaller margins, so its norm-based bound is larger. In our runs, the product of Frobenius norms is about 9 times larger, and the bound 30 to 70 times larger, depending on the margin level used. Both bounds may still exceed 1: discuss what this says about the tightness of Theorem 9.9.

17. ★★★ Double descent with random ReLU features (Python). Draw n = 100 inputs x \sim \mathcal{N}(0, I_{10}), a unit vector \beta, and responses y = \sigma(\beta^\top x) + 0.2\,\varepsilon.

    Fit them by minimum-norm least squares on p random features \sigma(w_j^\top x)/\sqrt p, with w_j \sim \mathcal{N}(0, I_{10}/10), for p from 10 to 3000.

    Plot the test error against p, as a median over 20 draws of the features, then add a small ridge penalty. Finally, repeat with a scalar input x \in [0, 1].

    Hints and expected result: in our runs over three seeds, the test error has a first minimum between p = 25 and p = 50 (0.12 to 0.15). It peaks at p = n = 100 (10 to 45), then decreases again for p \gg n, to 0.06–0.13 at p = 3000, below the first minimum, as in Belkin et al. (2019).

    A ridge penalty equal to 10^{-2} times the squared norm of the coefficients removes the peak, as the formulas of Hastie et al. (2022) predict. With a scalar input there is no second descent: the limiting kernel is smooth, and its interpolant of noisy points oscillates more and more as p grows.

18. ★★★ Lazy training (Python, self-study). Rerun the second code block of ch. 4 with widths m \in \{100, 1000, 10\,000\}. Measure the relative distance \|\theta_K - \theta_0\| / \|\theta_0\| and the change of \lambda_{\min}(JJ^\top), then repeat with the mean-field scaling 1/m and a step multiplied by m.

    Hints and expected result: in the 1/\sqrt m scaling, the relative distance decreases like m^{-1/2} and \lambda_{\min} barely moves: the network behaves like its linearisation (section 11.2). In the mean-field scaling, the neurons move by a quantity of order one, and features are learned.

Projects and assessment

The official assessment differs between the two sources. On master-mva.com it is labs (TP) 30 % and an exam 70 %. In the Université Paris-Saclay detail it is a final exam (90 %) and a take-home assignment with an algorithm implementation (10 %), with a resit exam whose grade replaces the previous ones. The solo subjects below are sized like an extended lab report or take-home implementation; the group subjects are for students who want to go further; the exam proposal matches the final exam.

Solo projects

1. [Solo · ≈ 20 h] Paper study: temperature scaling (Guo, Pleiss, Sun and Weinberger, 2017). Question: does miscalibration grow with capacity, and does one temperature fix it? Train multilayer perceptrons and a small CNN of increasing width and depth, with and without weight decay, on the scikit-learn digits and on Fashion-MNIST (public, via torchvision).
   • Deliverables: code, a 4–6 page report with reliability diagrams, a 10-minute talk.
   • Success criterion: reproduce the trend “ECE grows with capacity”, and a lower ECE after temperature scaling at unchanged accuracy.
   • Chapters used: ch. 6, 7. Evaluated with the rubric below.
2. [Solo · ≈ 20 h] Depth separation in practice. Question: can gradient descent find the efficient deep representation of the sawtooth? Train shallow and deep ReLU networks with Adam to fit g^k for k = 4, \dots, 8, and record the parameters needed to reach an L^1 error of 1/16.
   • Deliverables: code, a 4–6 page report with a figure “parameters against k” for both families, a 10-minute talk.
   • Success criterion: the figure, compared with Theorem 8.8 and Proposition 8.7, and a discussion of what random initialisations find.
   • Chapters used: ch. 1, 2, 8. Evaluated with the rubric below.
3. [Solo · ≈ 20 h] Implicit regularisation in matrix factorisation (Gunasekar et al., 2017). Question: does gradient descent on W = UU^\top from a small initialisation find low-rank solutions of matrix sensing? Use synthetic low-rank matrices and random Gaussian measurements; compare with nuclear-norm minimisation by proximal gradient.
   • Deliverables: code, a 4–6 page report, a 10-minute talk.
   • Success criterion: recovery error and effective rank as functions of the initialisation scale, with Proposition 3.5 used to explain the trend.
   • Chapters used: ch. 3, 4. Evaluated with the rubric below.

Group projects

1. [Group of 2–3 · ≈ 30 h each] Paper study: double descent (Belkin, Hsu, Ma and Mandal, 2019). Question: when does the test risk peak at the interpolation threshold, and what removes the peak?
   • Member A: theory — Theorem 10.2, the asymptotics of Hastie et al. (2022) with ridge and in a misspecified model, checked by simulation.
   • Member B: random Fourier features on a 10 000-image subset of MNIST (public, via torchvision), reproducing the curve of the paper.
   • Member C: width sweep of a two-layer network with label noise, after Nakkiran et al. (2020).
   • Deliverables: one repository, a 6–8 page report, a 15-minute talk. Success: a peak at the threshold, and agreement with theory in the linear case within Monte Carlo error. Chapters 3, 9, 10.
2. [Group of 2–3 · ≈ 30 h each] An uncertainty benchmark. Question: which approximation of ch. 6–ch. 7 gives the most reliable uncertainties, and at what cost?
   • Methods, one or two per member: last-layer Laplace, Bayes by Backprop, MC dropout, deep ensembles, an evidential classifier; one shared evaluation harness.
   • Data: digits 0–4 against 5–9 and Fashion-MNIST against MNIST for OOD detection; the scikit-learn diabetes data for regression.
   • Metrics: NLL, ECE, failure and OOD AUROC, coverage and sharpness, all over 5 seeds.
   • Deliverables: code, a 6–8 page report with one summary table, a 15-minute talk. Success: complete table with error bars and a check of Proposition 7.3. Chapters 5–7.
3. [Group of 2–3 · ≈ 30 h each] Landscape and convergence of small networks. Question: do the assumptions of Theorems 3.7, 4.3, 4.7 and 4.8 hold along real training runs?
   • Member A: fraction of runs reaching zero loss on N random points, as a function of width, with \lambda_{\min}(JJ^\top) tracked along training.
   • Member B: finite length of the iterates and an estimate of the Łojasiewicz exponent near the limits.
   • Member C: failure cases — narrow ReLU networks, dead units, degenerate saddles.
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: each figure tied to a theorem whose assumptions are checked numerically. Chapters 3, 4.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, four exercises (a proposal, not the official exam).

1. Question (4 points). State the decomposition of the excess risk into approximation, estimation and optimisation errors, and prove the bound on the estimation error. Explain in a few lines why double descent contradicts the classical picture, using Proposition 3.4 and Theorem 10.2.

   Expected: Proposition 1.5 with its three-term proof (2 points); interpolation and the selection of the minimum-norm interpolant, the explosion at p = n and the second descent (2 points).

2. Question (5 points). Bayesian linear regression with y = wx + \varepsilon, noise precision 1 and the prior w \sim \mathcal{N}(0, 1), on the data x = (1, -1, 2), y = (2, -1, 3). Compute the posterior, then the predictive mean and variance at the inputs 0 and 3, and split each variance into aleatoric and epistemic parts.

   Expected: S_N^{-1} = 7 and m_N = 9/7 (2 points). At x = 0, mean 0 and variance 1, all aleatoric; at x = 3, mean 27/7 \approx 3.86 and variance 1 + 9/7 \approx 2.29 (2 points). Interpretation (1 point).

3. Question (5 points). Let F(\theta) = \frac12\|G(\theta) - y\|^2 with \lambda_{\min}(JJ^\top) \ge \mu and a \beta-Lipschitz gradient. Prove that gradient descent with step 1/\beta converges linearly to zero loss, and explain why the assumption needs at least as many parameters as data points.

   Expected: the PL inequality from \nabla F = J^\top r (2 points); the descent lemma and the rate 1 - \mu/\beta (2 points); the rank of J is at most p (1 point).

4. Question (6 points). Expressivity on the line. (a) Show that a one-hidden-layer ReLU network with m units has at most m + 1 affine pieces. (b) Show that the tent map composed with itself is a sawtooth with 4 pieces. (c) Prove that every continuous piecewise-affine function with at most 2^{k-2} - 1 pieces is at L^1 distance at least 1/16 from g^k.

   Expected: kinks of each unit (2 points); composition on each half-interval (1 point); the pairing argument of Theorem 8.8 (3 points).

Grading rubric (proposal)

References

Official references (master-mva.com course page, numbered as there; the text calls them “official reference N”):

1. J. Bolte, S. Sabach, M. Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1–2), 2014 (pages listed as “59-594” on the official page).
2. I. Panageas, G. Piliouras. Gradient descent only converges to minimizers: non-isolated critical points and invariant regions. ITCS, 2017.
3. J. D. Lee, M. Simchowitz, M. I. Jordan, B. Recht. Gradient descent only converges to minimizers. COLT, 2016.
4. P. Baldi, K. Hornik. Neural networks and principal component analysis: learning from examples without local minima. Neural Networks, 2(1):53–58, 1989.
5. L. Venturi, A. S. Bandeira, J. Bruna. Neural networks with finite intrinsic dimension have no spurious valleys. arXiv, February 2018.
6. I. Safran, O. Shamir. On the quality of the initial basin in overspecified neural networks. ICML, pages 774–782, 2016.
7. F. Malgouyres, J. Landsberg. Multilinear compressed sensing: application to deep linear networks. arXiv, 2017.
8. A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945 (dated 1994 on the official page; volume 39 is the 1993 volume).
9. R. Eldan, O. Shamir. The power of depth for feedforward neural networks. 29th Annual Conference on Learning Theory, PMLR 49:907–940, 2016.
10. N. Golowich, A. Rakhlin, O. Shamir. Size-independent sample complexity of neural networks. Proceedings of COLT 2018, 297–299, 2018.
11. K. Kawaguchi, L. P. Kaelbling, Y. Bengio. Generalization in deep learning. In Mathematical Aspects of Deep Learning, pages 112–148, Cambridge University Press, 2022.
12. J. Bruna, S. Mallat. Invariant scattering convolution networks. IEEE TPAMI, 35(8):1872–1886, 2013.
13. A. Bietti, J. Mairal. Group invariance and stability to deformations of deep convolutional representations. NIPS, 2017.
14. P. W. Koh, P. Liang. Understanding black-box predictions via influence functions. ICML, 2017.
15. C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
16. K. P. Murphy. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012.
17. C. Blundell, J. Cornebise, K. Kavukcuoglu, D. Wierstra. Weight uncertainty in neural networks. ICML, 2015.
18. Y. Gal, Z. Ghahramani. Dropout as a Bayesian approximation: representing model uncertainty in deep learning. ICML, 2016.
19. C. Guo, G. Pleiss, Y. Sun, K. Q. Weinberger. On calibration of modern neural networks. ICML, 2017.
20. C. Corbière, N. Thome, A. Saporta, T.-H. Vu, M. Cord, P. Pérez. Confidence estimation via auxiliary models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
21. S. Liang, Y. Li, R. Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. ICLR, 2018.
22. K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de l’Institut Fourier, 48(3):769–783, 1998.
23. J. Bolte, A. Daniilidis, A. Lewis, M. Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2):556–572, 2007.
24. D. Davis, D. Drusvyatskiy, S. Kakade, J. D. Lee. Stochastic subgradient method converges on tame functions. arXiv:1804.07795, 2018.
25. Q. Nguyen, M. Hein. The loss surface of deep and wide neural networks. arXiv:1704.08045, 2017.
26. G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:303–314, 1989.
27. D. Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. Proceedings of COLT 2018, 639–649, 2018.
28. P. L. Bartlett, N. Harvey, C. Liaw, A. Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1–17, 2019.
29. M. Belkin, D. Hsu, S. Ma, S. Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849–15854, 2019.
30. T. Hastie, A. Montanari, S. Rosset, R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50:949–986, 2022.

Textbooks

• F. Bach. Learning Theory from First Principles. MIT Press, 2024.
• S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016.
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
• L. van den Dries. Tame Topology and O-minimal Structures. London Mathematical Society Lecture Note Series 248, Cambridge University Press, 1998.
• V. Vovk, A. Gammerman, G. Shafer. Algorithmic Learning in a Random World. Springer, 2005.
• R. D. Cook, S. Weisberg. Residuals and Influence in Regression. Chapman and Hall, 1982.

Networks, optimisation and landscape

• P.-A. Absil, R. Mahony, B. Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, 16(2):531–547, 2005.
• S. Arora, N. Cohen, E. Hazan. On the optimization of deep networks: implicit acceleration by overparameterization. ICML, 2018.
• H. Attouch, J. Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116:5–16, 2009.
• J. Bolte, E. Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188:19–51, 2021.
• J. Cohen, S. Kaur, Y. Li, J. Z. Kolter, A. Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. ICLR, 2021.
• S. S. Du, W. Hu, J. D. Lee. Algorithmic regularization in learning deep homogeneous models: layers are automatically balanced. NeurIPS, 2018.
• S. Ghadimi, G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
• X. Glorot, Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. AISTATS, 2010.
• S. Gunasekar, B. Woodworth, S. Bhojanapalli, B. Neyshabur, N. Srebro. Implicit regularization in matrix factorization. NIPS, 2017.
• K. He, X. Zhang, S. Ren, J. Sun. Delving deep into rectifiers: surpassing human-level performance on ImageNet classification. ICCV, 2015.
• K. He, X. Zhang, S. Ren, J. Sun. Deep residual learning for image recognition. CVPR, 2016.
• S. Hochreiter, J. Schmidhuber. Long short-term memory. Neural Computation, 9(8):1735–1780, 1997.
• H. Karimi, J. Nutini, M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition. ECML PKDD, 2016.
• S. Łojasiewicz. Une propriété topologique des sous-ensembles analytiques réels. Les Équations aux Dérivées Partielles, Éditions du CNRS, 87–89, 1963.
• K. Lyu, J. Li. Gradient descent maximizes the margin of homogeneous neural networks. ICLR, 2020.
• I. Safran, O. Shamir. Spurious local minima are common in two-layer ReLU neural networks. ICML, 2018.
• D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, N. Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1–57, 2018.
• A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin. Attention is all you need. NIPS, 2017.
• A. J. Wilkie. Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. Journal of the American Mathematical Society, 9(4):1051–1094, 1996.

Approximation, generalisation and infinite width

• S. Arora, R. Ge, B. Neyshabur, Y. Zhang. Stronger generalization bounds for deep nets via a compression approach. ICML, 2018.
• P. L. Bartlett, D. J. Foster, M. Telgarsky. Spectrally-normalized margin bounds for neural networks. NIPS, 2017.
• P. L. Bartlett, P. M. Long, G. Lugosi, A. Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063–30070, 2020.
• L. Chizat, F. Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. NeurIPS, 2018.
• L. Chizat, E. Oyallon, F. Bach. On lazy training in differentiable programming. NeurIPS, 2019.
• S. S. Du, X. Zhai, B. Póczos, A. Singh. Gradient descent provably optimizes over-parameterized neural networks. ICLR, 2019.
• G. K. Dziugaite, D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. UAI, 2017.
• B. Hanin, D. Rolnick. Complexity of linear regions in deep networks. ICML, 2019.
• M. Hardt, B. Recht, Y. Singer. Train faster, generalize better: stability of stochastic gradient descent. ICML, 2016.
• A. Jacot, F. Gabriel, C. Hongler. Neural tangent kernel: convergence and generalization in neural networks. NeurIPS, 2018.
• M. Leshno, V. Ya. Lin, A. Pinkus, S. Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861–867, 1993.
• S. Mei, A. Montanari, P.-M. Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665–E7671, 2018.
• P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, I. Sutskever. Deep double descent: where bigger models and more data hurt. ICLR, 2020.
• B. Neyshabur, R. Tomioka, N. Srebro. Norm-based capacity control in neural networks. COLT, 2015.
• M. Telgarsky. Benefits of depth in neural networks. COLT, PMLR 49, 2016.
• D. Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103–114, 2017.
• C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.

Robustness, uncertainty and generative models

• A. Amini, W. Schwarting, A. Soleimany, D. Rus. Deep evidential regression. NeurIPS, 2020.
• A. N. Angelopoulos, S. Bates. Conformal prediction: a gentle introduction. Foundations and Trends in Machine Learning, 16(4):494–591, 2023.
• M. Arjovsky, S. Chintala, L. Bottou. Wasserstein generative adversarial networks. ICML, 2017.
• S. Arora, R. Ge, Y. Liang, T. Ma, Y. Zhang. Generalization and equilibrium in generative adversarial nets (GANs). ICML, 2017.
• J. Cohen, E. Rosenfeld, J. Z. Kolter. Certified adversarial robustness via randomized smoothing. ICML, 2019.
• E. Daxberger, A. Kristiadi, A. Immer, R. Eschenhagen, M. Bauer, P. Hennig. Laplace Redux — effortless Bayesian deep learning. NeurIPS, 2021.
• R. Foygel Barber, E. J. Candès, A. Ramdas, R. J. Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455–482, 2021.
• T. Gneiting, A. E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359–378, 2007.
• I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio. Generative adversarial nets. NIPS, 2014.
• I. Goodfellow, J. Shlens, C. Szegedy. Explaining and harnessing adversarial examples. ICLR, 2015.
• D. Hendrycks, K. Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. ICLR, 2017.
• D. P. Kingma, M. Welling. Auto-encoding variational Bayes. ICLR, 2014.
• V. Kuleshov, N. Fenner, S. Ermon. Accurate uncertainties for deep learning using calibrated regression. ICML, 2018.
• B. Lakshminarayanan, A. Pritzel, C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. NIPS, 2017.
• D. J. C. MacKay. The evidence framework applied to classification networks. Neural Computation, 4(5):720–736, 1992.
• S. Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331–1398, 2012.
• M. P. Naeini, G. Cooper, M. Hauskrecht. Obtaining well calibrated probabilities using Bayesian binning. AAAI, 2015.
• Y. Ovadia, E. Fertig, J. Ren, Z. Nado, D. Sculley, S. Nowozin, J. Dillon, B. Lakshminarayanan, J. Snoek. Can you trust your model’s uncertainty? Evaluating predictive uncertainty under dataset shift. NeurIPS, 2019.
• H. Ritter, A. Botev, D. Barber. A scalable Laplace approximation for neural networks. ICLR, 2018.
• M. Sensoy, L. Kaplan, M. Kandemir. Evidential deep learning to quantify classification uncertainty. NeurIPS, 2018.
• K. Simonyan, A. Vedaldi, A. Zisserman. Deep inside convolutional networks: visualising image classification models and saliency maps. ICLR Workshop, 2014.
• N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, R. Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56):1929–1958, 2014.
• M. Sundararajan, A. Taly, Q. Yan. Axiomatic attribution for deep networks. ICML, 2017.
• S. Wager, S. Wang, P. Liang. Dropout training as adaptive regularization. NIPS, 2013.
• D. Xu, S. Yuan, L. Zhang, X. Wu. FairGAN: fairness-aware generative adversarial networks. IEEE International Conference on Big Data, 2018.