Statistical Learning Theory

Contents

• Introduction and overview
• 0. Review: probability, estimation, convexity
• 1. The empirical risk minimization framework
• 2. Concentration inequalities
• 3. Vapnik-Chervonenkis dimension and Sauer’s lemma
• 4. VC generalization bounds
• 5. Rademacher complexity
• 6. Margin theory
• 7. Aggregation of estimators
• 8. Lower bounds and minimax
• 9. High dimension: sparsity and the Lasso
• 10. Research at CMAP (Lounici)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who has already seen a train/test gap and heard “overfitting” — without opening on VC dimension on line 1. Empirical first: a classifier that memorizes MNIST-like digits, a bound that explodes with class size, a large margin that “generalizes better” on a split. Only then do we name concentration, VC, Rademacher.

Why should minimizing training error predict on new data? Concentration, VC dimension, Rademacher, generalization bounds: the intuition of overfitting becomes theorems — PhD language, and a rare asset for auditing high-stakes models in industry.

What you will be able to do

• Formalize a learning problem in the empirical risk minimization (ERM) framework and identify what needs to be proved.
• Derive and use concentration inequalities (Hoeffding, Bernstein, McDiarmid) in the service of learning bounds.
• Compute the VC dimension of a function class and apply Sauer’s lemma.
• Establish and interpret a VC generalization bound — and understand what it does not say.
• Master Rademacher complexity, a finer tool than the VC dimension for modern classes.
• Exploit margin theory to explain the generalization of large-margin classifiers.
• Read and construct lower bounds and minimax results: know when a problem is genuinely hard.
• Analyze high dimension via sparsity and the Lasso (oracle inequalities) and understand the aggregation of estimators.

Official objectives and syllabus (2026-2027 catalog)

Official objectives (paraphrased from the description published on SynapseS): to provide a rigorous theoretical introduction to statistical learning, in supervised as well as unsupervised settings, with non-asymptotic methods for extracting information in a random context, using tools from probability, statistics, perturbation theory and optimization. Announced learning objectives: formulate learning problems in a rigorous mathematical framework; characterize and measure the intrinsic complexity of these problems; analyze learning errors from a theoretical angle; exploit prior knowledge to design and improve better-performing models.

The course is strongly theory-oriented, with a few R/Python practical sessions during the small classes; official assessment: in-class exams and homework assignments.

The official detailed syllabus is organized into three blocks, mapped below to our chapters.

Where this course fits in the program

Notes kept for reference: this course unit is not in the LLGA 2026–2027 lists (it is still scheduled in Period 1 for other tracks of the École, 36 h), so no LLGA module requires it. For an LLGA student it is a theoretical deepening.

The official prerequisites of the sheet — solid foundations in probability (Boole, conditional expectation, Markov, Jensen), statistics (confidence intervals, tests), linear algebra (Euclidean geometry, spectral decompositions) and analysis (Cauchy-Schwarz, Hölder), with MAP432/MAP433 recommended for the engineering cycle — correspond precisely to the foundations of the Refresher in Statistics and Machine Learning modules, whose “Generalization theory” chapter it deepens.

The course unit is shared with the engineering cycle (X), the MJH and IES masters, exchange programs and the MScT AI&AVC, IoT and TRAI tracks.

This is the research-orientation module par excellence: proving bounds “by hand” is the daily routine of a PhD student in theoretical ML (CMAP, Hi!PARIS, Inria), and doctoral schools expect familiarity with it. Downstream, it directly prepares the M2 module Privacy and Uncertainty Quantification, whose guarantees (differential privacy, uncertainty quantification) are written with the same concentration and complexity tools. The oracle inequalities of the Lasso also open onto the high-dimensional statistics encountered in several research seminars of the master’s program.

Course outline

• Review: probability, estimation, convexity: the tools of the two prerequisites, brought to the level required by the proofs of the course.
• The empirical risk minimization framework: formalizing learning as a statistical problem — the birth certificate of the course.
• Concentration inequalities: Hoeffding and its cousins, the ingredient of all the bounds that follow.
• Vapnik-Chervonenkis dimension and Sauer’s lemma: measuring the “size” of a function class.
• VC generalization bounds: the central theorem — empirical error versus true error, uniformly.
• Rademacher complexity: a data-dependent complexity measure, finer, more modern.
• Margin theory: why a large margin generalizes better, and what this says about SVMs and beyond.
• Aggregation of estimators: combining predictors with guarantees — the bridge to boosting as seen in Machine Learning.
• Lower bounds and minimax: proving that no algorithm can do better — the dark and necessary side of theory.
• High dimension: sparsity and the Lasso: learning when the dimension exceeds the number of samples, with oracle inequalities in support.
• Research at CMAP (Lounici): Karim Lounici’s research, from high-dimensional statistics to learning guarantees.

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, lecture/tutorial/lab split not published); the sheet publishes no session-by-session programme, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core theory (VC, Rademacher, margins, aggregation), 3 = advanced, proof-heavy material (minimax lower bounds, high-dimensional oracle inequalities); the level never goes down from one session to the next.

Self-study, outside the 36 h (about 3 h in total): ch. 10 Research at CMAP (Lounici) — four papers on the Lasso, the group Lasso and aggregation (≈ 3 h).

How to study this module

• Redo each proof on scratch paper, line by line: in this module, understanding the proof is the goal — the result alone is not enough at the exam.
• Go through the review chapter without skipping it: convexity and concentration are presented there exactly at the level used in chapters 2 to 6.
• Keep the guiding thread in mind: “control the gap between empirical risk and true risk, uniformly over a class” — each chapter adds a tool for this.
• Do the exercises on computing VC dimensions and Rademacher complexities on concrete examples (thresholds, intervals, hyperplanes): they form the memory of the course.
• Reread in parallel the “Generalization theory” chapter of the Machine Learning module: you will see what was sketched there become theorems.
• If an academic career appeals to you, treat the “Research at CMAP (Lounici)” chapter as a first reading of a research paper.

0. Review: probability, estimation, convexity

The proofs of this course use the same small toolbox again and again: the union bound, the classical inequalities of probability, the vocabulary of estimation, and convexity. This review lists these tools at the level the proofs require, and proves the one that does half of the work, the union bound.

1. The empirical risk minimization framework

Concrete scene: a classifier with 10⁶ parameters, 5,000 examples — train error 0%, test 28%. The model “learns”… and memorizes. Conversely, a too-poor model stalls at 40% everywhere. This chapter formalizes the diagnosis: risk vs empirical risk, ERM, what must be proved to talk about generalization — before VC and Rademacher.

Notation. Site-wide conventions: see Notation conventions. Deviations on this page: p is the number of variables (site-wide d), because d is the VC dimension from ch. 3 on; the sample is written with capitals because it is random.

On this page R is always a risk, \mathfrak{R} the Rademacher complexity (ch. 5) and r the radius of the data (ch. 5–6).

2. Concentration inequalities

A generalization bound must say how far an empirical average can be from its expectation, with an explicit probability, for a finite sample. Concentration inequalities give exactly this, with tails that decay exponentially fast. This chapter proves Hoeffding’s inequality, states its refinements (Bernstein, McDiarmid), and bounds the expected maximum of finitely many sub-Gaussian variables — the three tools used by every later chapter.

3. Vapnik-Chervonenkis dimension and Sauer’s lemma

Hoeffding’s inequality and the union bound control finitely many predictors, but the classes used in practice — thresholds, half-planes, networks — are infinite. On N given points, however, an infinite class only produces finitely many labelings. This chapter counts them: the VC dimension measures the size of a class, and Sauer’s lemma shows that the number of labelings grows only polynomially in N.

import numpy as np
from itertools import combinations

# growth function of thresholds on R: exactly N+1 dichotomies
def threshold_growth(N):
    return N + 1        # on N sorted points, a threshold cuts after the k-th

def sauer(N, d):        # Sauer-Shelah upper bound
    return sum(len(list(combinations(range(N), k))) for k in range(d + 1))

for N in (5, 10, 20):
    print(f"N={N:3d}  thresholds: {threshold_growth(N):3d}  "
          f"Sauer(N,1)={sauer(N,1):4d}")   # equality: N+1 = 1 + N (d = 1)

4. VC generalization bounds

This chapter combines the two previous ones — concentration for each labeling, Sauer’s lemma for the number of labelings — into the central theorem of the course: with high probability, the empirical risk is close to the true risk simultaneously for every predictor of a class of finite VC dimension. Its corollary bounds the excess risk of empirical risk minimization.

5. Rademacher complexity

VC bounds depend only on a combinatorial count: they ignore the actual data and the geometry of the class, and they are far too pessimistic for linear predictors of bounded norm. Rademacher complexity measures instead how well the class can correlate with random signs on the observed sample. This chapter defines it, proves the symmetrization inequality that links it to generalization, and computes it for linear classes.

import numpy as np
rng = np.random.default_rng(5)

def linear_rademacher(X, W, B=300):
    """Monte-Carlo of the empirical Rademacher complexity of {x -> <w,x> : ||w|| <= W} (def. 5.1)."""
    n, reps = len(X), B
    sigma = rng.choice([-1.0, 1.0], size=(reps, n))
    return W * np.mean([np.linalg.norm(s @ X) for s in sigma]) / n

n, p, r, W = 400, 50, 1.0, 2.0                    # p variables: VC dimension p + 1 = 51
X = rng.normal(size=(n, p)); X /= np.linalg.norm(X, axis=1, keepdims=True)
print(f"estimated R_hat  : {linear_rademacher(X, W):.4f}")   # Jensen is nearly tight: equal up to Monte-Carlo error
print(f"bound prop.5.5   : {r*W/np.sqrt(n):.4f}")       # 0.1
print(f"VC bound dim 51  : {np.sqrt(2*(51*np.log(np.e*n/51) + np.log(2))/n):.4f}")

6. Margin theory

A linear classifier in dimension p has VC dimension p + 1, yet support vector machines generalize well in very high dimension. The explanation is the margin: a classifier that separates the data with a wide margin behaves like a member of a small class. This chapter turns this idea into a bound in which the dimension does not appear.

7. Aggregation of estimators

In practice one rarely has a single model: one has a list of candidates — several hyperparameters, several model families — and must choose among them or combine them with the same data. This chapter shows how to combine M candidates so that the result is almost as good as the best of them, at a price of order \sqrt{\log M/n}, and reads cross-validation in this light.

import numpy as np
rng = np.random.default_rng(8)

n, M = 400, 12
x = rng.uniform(-2, 2, n); y = np.sin(2*x) + 0.3*rng.standard_normal(n)
target = lambda z: np.sin(2*z)

# split: the dictionary is fitted on the first half and the weights use the second half,
# so that the f_j are fixed functions for the losses of Thm 7.3
x1, y1, x2, y2 = x[:n//2], y[:n//2], x[n//2:], y[n//2:]
coefs = [np.polyfit(x1, y1, d) for d in range(1, M+1)]
dictionary = [lambda z, c=c: np.polyval(c, z) for c in coefs]
losses = np.array([np.mean((f(x2) - y2)**2) for f in dictionary])   # held-out empirical risk

eta, m = 2.0, len(x2)
pi = np.exp(-eta*m*(losses - losses.min())); pi /= pi.sum()
agg = lambda z: sum(w*f(z) for w, f in zip(pi, dictionary))

z = np.linspace(-2, 2, 400)
risk = lambda f: np.mean((f(z) - target(z))**2)                     # distance to the target
risks = np.array([risk(f) for f in dictionary])
j_hat = int(np.argmin(losses))
print(f"oracle: degree {np.argmin(risks)+1}, risk {risks.min():.4f}")
print(f"held-out selection: degree {j_hat+1}, risk {risks[j_hat]:.4f}")
print(f"exponential aggregate: risk {risk(agg):.4f}")
print("weights by degree:", np.round(pi, 2))

On this draw the weights put almost 90 % of their mass on degrees 5 to 7. The aggregate (risk 0.0059) does slightly better than the degree selected on the held-out half (degree 7, 0.0064) and even than the best single degree (degree 6, 0.0062): a convex combination can beat every member of the dictionary. Without the split, the training losses decrease with the degree, so the weights grow with it and favour the most complex polynomials.

8. Lower bounds and minimax

The previous chapters give upper bounds: some algorithm reaches a given rate. To know whether a better algorithm could exist, one needs lower bounds that hold for every estimator. This chapter introduces the minimax risk and Le Cam’s two-point method, and uses them to show that the 1/\sqrt n rates of the course cannot be improved in general.

9. High dimension: sparsity and the Lasso

When the number of variables p exceeds the number of observations n, least squares is not even defined; learning remains possible if only a few variables matter. This chapter studies the Lasso, which exploits such sparsity, and proves that it predicts almost as well as if the relevant variables were known in advance, at the price of a factor \log p.

import numpy as np
from sklearn.linear_model import Lasso, LassoCV
rng = np.random.default_rng(20)

n, p, s, sigma = 100, 1000, 5, 1.0
X = rng.normal(size=(n, p))
X *= np.sqrt(n) / np.linalg.norm(X, axis=0)        # columns with ||X_j||^2 / n = 1 (def. 9.1)
beta = np.zeros(p); beta[:s] = rng.choice([-1, 1], s) * 1.5
y = X @ beta + sigma * rng.standard_normal(n)

lam_theo = 2*sigma*np.sqrt(2*np.log(2*p)/n)        # prop. 9.2
# sklearn minimizes (1/(2n))||y - Xb||^2 + alpha ||b||_1, the objective of def. 9.1: alpha = lambda
lasso = Lasso(alpha=lam_theo, fit_intercept=False).fit(X, y)
support = np.flatnonzero(lasso.coef_)
err_theo = np.linalg.norm(X @ (lasso.coef_ - beta))**2 / n
print(f"theoretical lambda {lam_theo:.3f}  support {support} (true [0 1 2 3 4])"
      f"  prediction error {err_theo:.3f}")

grid = np.geomspace(1e-2, 1, 60)                   # empirical calibration (ch. 7)
cv = LassoCV(cv=5, alphas=grid, fit_intercept=False).fit(X, y)
err = np.linalg.norm(X @ (cv.coef_ - beta))**2 / n
print(f"CV lambda {cv.alpha_:.3f}  support size {np.count_nonzero(cv.coef_)}"
      f"  prediction error {err:.3f}  (oracle s/n = {s/n:.3f})")

On this draw, the theoretical \lambda = 0.78 recovers exactly the five true variables but shrinks each coefficient by about \lambda, so its prediction error is 3.6. The cross-validated \lambda = 0.27 keeps 15 variables and predicts far better (0.46), against s/n = 0.05 for the oracle that knows the support: the theoretical value is conservative, it guards against false positives and pays for it in shrinkage.

10. Research at CMAP (Lounici)

This self-study chapter presents four papers of the course coordinator that extend chapters 7 and 9: sup-norm rates and support recovery for the Lasso, the group Lasso, and aggregation by exponential weights.

Exercises

1. ★ Sample size (Hoeffding). A fixed classifier has a 0-1 loss. How many examples to guarantee |\hat R_n - R| \leq 0.02 with probability 0.99? And if the same guarantee is wanted simultaneously for M = 100 classifiers?

   Solution. For one classifier, n \geq \log(2/\delta)/(2\varepsilon^2) = \log 200/0.0008 = 5.298/0.0008 \approx 6623. For M classifiers, union bound: replace \delta by \delta/M = 10^{-4}: n \geq \log(2\times10^4)/0.0008 = 9.903/0.0008 \approx 12\,379 — the price of “simultaneous” is a factor \log M, not M.

2. ★ VC dimension of intervals. Show that the class of intervals \{x \mapsto \mathbf{1}_{x \in [a,b]}\} on \mathbb{R} has \mathrm{VC} = 2.

   Solution. Two points x_1 < x_2 are shattered: the four labelings are obtained with [a,b] avoiding everything, containing only x_1, only x_2, or both.

   Three points x_1 < x_2 < x_3: the labeling \{x_1, x_3\} without x_2 is impossible (an interval containing the extremes contains the middle): no shattering, \mathrm{VC} = 2. (Bonus question: unions of k intervals → 2k, by the same parity argument on the components.)

3. ★ Sauer in small dimensions. Verify s(N,2) = 1 + N + N(N-1)/2 and compute s(10,2); show that the class of thresholds (Example 1.4, VC dimension 1) achieves exactly N+1 = s(N,1) dichotomies and the class of intervals (exercise 2, VC dimension 2) exactly s(N,2), so that the Sauer bound is attained by both.

   Solution. \sum_{k\leq2}\binom{N}{k} = 1 + N + N(N-1)/2; s(10,2) = 1 + 10 + 45 = 56.

   Thresholds produce N+1 dichotomies on N sorted points (cut after the k-th point, k = 0, \dots, N), which is s(N,1) = 1 + N.

   Intervals realize the empty set and the N(N+1)/2 blocks of consecutive points \{x_i, \dots, x_j\}, i \leq j: 1 + N(N+1)/2 = 1 + N + N(N-1)/2 = s(N,2), that is 56 for N = 10. The bound cannot be improved in general.

4. ★★ Symmetrization to complete (Prop. 5.2). Redo the proof and justify: (a) the use of Jensen to swap \sup and \mathbb{E}_{S'}; (b) the legality of introducing the signs \sigma_i; (c) the final sub-additivity.

   Solution.

   • (a) For each fixed S, \sup_f \mathbb{E}_{S'}[g_f] \leq \mathbb{E}_{S'}[\sup_f g_f]: for every f_0, the pointwise inequality g_{f_0} \leq \sup_f g_f passes to the expectation, and one then takes the supremum over f_0 on the left.
   • (b) Conditionally on (X_i, X'_i), the quantity \sigma_i(f(X'_i) - f(X_i)) has the same distribution as f(X'_i) - f(X_i) because \sigma_i is symmetric and independent — one may therefore insert \sigma_i without changing the distribution of the supremum.
   • (c) \sup_f (A_f + B_f) \leq \sup_f A_f + \sup_f B_f for any choice of decomposition, applied to A_f = \frac1n\sum\sigma_if(X'_i), B_f = -\frac1n\sum\sigma_if(X_i); since -\sigma has the same law as \sigma, the two suprema have the same expectation, which gives the factor 2.

5. ★★ Rademacher of constants (exact computation). Compute \hat{\mathfrak{R}}_S(\{x \mapsto c : c \in [0,1]\}) and its equivalent as n \to \infty.

   Solution. With \Sigma = \sum_i\sigma_i: \sup_{c \in [0,1]} \frac1n|c\,\Sigma| = \frac1n |\Sigma|, so \hat{\mathfrak{R}}_S = \frac1n\mathbb{E}|\Sigma|. By the CLT (Probability Theory for ML module, chapter 2), \Sigma/\sqrt n is approximately standard Gaussian and \mathbb{E}|\Sigma| \sim \sqrt{2n/\pi}, hence \hat{\mathfrak{R}}_S \sim \sqrt{\frac{2}{\pi n}} \approx \frac{0.798}{\sqrt n}. (Without the absolute value in Definition 5.1, the convention of Lemma 5.4 and of some textbooks, the supremum is \frac1n\max(\Sigma, 0), whose expectation \hat{\mathfrak{R}}^{\circ}_S is half as large, \approx 0.399/\sqrt n.) Even a “one-dimensional” class has nonzero complexity, of order exactly 1/\sqrt n.

6. ★★ Le Cam for the Bernoulli mean (quadratic loss). Show that the quadratic minimax risk for estimating p from n Bernoulli draws satisfies \mathcal{M}_n \geq 1/(64n). Hint. Two parameters p_{1,2} = 1/2 \pm s, quadratic loss, separation \Delta = 2s; test A = \{|\hat p - p_1| \leq s\} and bound the binomial KL.

   On A^c: (\hat p - p_1)^2 \geq s^2 contributes s^2\,\mathbb{P}_1(A^c); on A: |\hat p - p_2| \geq s contributes s^2\,\mathbb{P}_2(A). Summing then averaging over the two problems: \mathcal{M}_n \geq \frac{s^2}{2}\big(\mathbb{P}_1(A^c) + \mathbb{P}_2(A)\big) \geq \frac{s^2}{2}(1-\delta).

   KL of the product distributions: n\,\mathrm{KL}(\mathrm{Bern}(p_1)\|\mathrm{Bern}(p_2)) \approx n \times \frac{(2s)^2}{2p(1-p)} = 8ns^2 (to first order at p = 1/2). Taking s = 1/(4\sqrt n): \mathrm{KL} \approx 1/2, Pinsker gives \delta \leq 1/2, hence \mathcal{M}_n \geq \frac{s^2}{4} = \frac{1}{64n} — the 1/n order is what matters; the empirical mean achieves p(1-p)/n \leq 1/(4n): the parametric rate is optimal.

7. ★★ Restricted eigenvalues under orthonormal design. Take n = p and an orthonormal design, X^\top X = n I (normalized columns).

   • (a) Show that the RE condition (Def. 9.3) holds with \kappa = 1.
   • (b) Show that the Lasso reduces to soft-thresholding of the correlations z = X^\top Y/n = \beta^\star + z^\star, that is \hat\beta_j = \mathrm{sign}(z_j)(|z_j| - \lambda)_+.
   • (c) On the event \{|z^\star_j| \leq \lambda/2\ \forall j\} of Prop. 9.2, show that for every j |\hat\beta_j - \beta^\star_j| \leq \min\big(|\beta^\star_j|,\ 3\lambda/2\big). Deduce \|\hat\beta - \beta^\star\|_2^2 \leq \sum_{j \in S} \min\big((\beta^\star_j)^2,\ \tfrac94\lambda^2\big) \leq \tfrac94\, s\lambda^2, and comment on the (s\log p)/n rate.

   Solution (sketch).

   • (a) \|Xh\|^2/n = \|h\|_2^2 \geq \|h_S\|_2^2 (the cone restricts nothing).
   • (b) Since X^\top X = nI, the objective equals \frac12\|z - b\|_2^2 + \lambda\|b\|_1 up to a constant. It separates coordinate by coordinate into \frac12(z_j - b_j)^2 + \lambda|b_j|, whose minimizer is the soft-thresholding. With Y = X\beta^\star + \varepsilon, one gets z = \beta^\star + z^\star.
   • (c) Fix j and write \theta = \beta^\star_j and \xi = z^\star_j, so that z_j = \theta + \xi with |\xi| \leq \lambda/2.
   • Case |z_j| \leq \lambda: then \hat\beta_j = 0 and the error is |\theta| \leq |z_j| + |\xi| \leq 3\lambda/2.
   • Case |z_j| > \lambda: then |\theta| \geq |z_j| - |\xi| > \lambda/2 \geq |\xi|, so z_j has the sign of \theta, and the soft-thresholding gives \hat\beta_j - \theta = \xi - \lambda\,\mathrm{sign}(\theta), \qquad |\hat\beta_j - \theta| \leq 3\lambda/2. Moreover 0 < |\hat\beta_j| \leq |\theta| - \lambda/2: the estimate lies between 0 and \theta, so the error is also at most |\theta|.
   • Off the support, \theta = 0 gives |z_j| = |\xi| < \lambda, hence \hat\beta_j = 0: no false positive on the event.

   Summing the squares over S gives the bound. With \lambda = 2\sigma\sqrt{2\log(2p)/n}, \|\hat\beta - \beta^\star\|_2^2 \leq \frac94\, s\lambda^2 = 18\,\frac{\sigma^2 s\log(2p)}{n}. This is the rate of Theorem 9.4 with \kappa = 1 and a better constant (18 instead of 72). The factor \log(2p) is the price of not knowing S; least squares on the true support would give \sigma^2 s/n.

   The factor 9/4 cannot be dropped: with \beta^\star_j = 10 and z^\star_j = -\lambda/2, the error on that coordinate is exactly 3\lambda/2, more than \lambda.

8. ★★ Convex aggregation (Thm 7.3(i)) to prove step by step. Redo the four steps (convexity, exponential weights, uniformization, assembly) and write each inequality with its exact constants; where does the proof use (i) the uniform prior, (ii) the convexity of the loss, (iii) independence? Hint. Follow the proof of the theorem; for the uniformization step, write the Hoeffding bound for each j, take \delta/(2M) and sum.

   • (i) The uniform prior is used in the exponential-weights step, through H(\pi) \leq \log M: the bound depends only on \log M, the number of candidates; a non-uniform prior \rho would replace \log M by \log(1/\rho_{j^\star}) for the best candidate j^\star.
   • (ii) Convexity allows R(\tilde f) \leq \sum_j\pi_j R(f_j); without convexity, one would be limited to selection (MS).
   • (iii) Independence between the observations is used exactly in Hoeffding; it is also what makes \hat R_n(f_j) computable and concentrated — the same role as everywhere in the course since Prop. 1.2.

Projects and assessment

The official assessment is “in-class exams and homework assignments”, graded out of 20 with a resit (SynapseS 2026–2027 sheet, quoted in the fiche above). The unit is not in the LLGA lists, so the sheet gives it no LLGA weight or ECTS. Everything below is a proposal: solo subjects sized as homework assignments, group subjects as a term project, and a mock in-class exam. Every subject exercises objective O1 (machine-learning foundations, here their theory); the benchmark subject also exercises O3 (evaluating LLMs) and O8 (trustworthy claims about models), and the last group subject O4 (graphs).

Solo projects

1. [Solo · ≈ 20 h] How vacuous are generalization bounds? Question: at realistic sample sizes, how far are the bounds of chapters 4–6 from the gaps one measures, and which term makes each of them vacuous?
   • On two classes of MNIST (digits 3 and 5; LeCun, Bottou, Bengio and Haffner, 1998), train a linear SVM and a one-hidden-layer MLP for n from 500 to 10,000, and measure the train–test gap (ch. 1).
   • Evaluate the VC bound (Thm 4.1), the Rademacher oracle bound with a Monte Carlo estimate of the empirical complexity (Thm 5.3 and the code of ch. 5, for the SVM’s norm-bounded class) and, for the SVM, the margin bound (Thm 6.2, or Cor. 6.3 when the data are separated), each with its stated constants; the SVM’s norm and margin are measured on the data, so use the grid version of the note “Data-dependent margin” (ch. 6); reproduce the table of Example 4.3 (ch. 4–6).
   • Add the random-label run of Zhang, Bengio, Hardt, Recht and Vinyals (2017): at small n both models fit random labels, the VC bound and the Rademacher complexity of the class ignore the labels, and only the margin bound tells the two runs apart.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Success: every bound is plotted against the measured gap for at least four values of n, and the report names the dominating term of each bound and the sample size at which it drops below 1.
2. [Solo · ≈ 20 h] Certifying benchmark scores with concentration. Question: how many test items are needed to rank M models, or M prompt variants of one LLM, with confidence 1 - \delta? This is the “Hoeffding versus Bernstein” lab of session 3, carried to the model comparisons of Large Language Models, 9.6 and Machine Learning, 4.9.
   • Derive simultaneous intervals for M accuracies and for the paired differences, with Hoeffding (Thm 2.3), Bernstein (Thm 2.5), the empirical Bernstein bound of Maurer and Pontil (2009) and a union bound (Prop. 0.1). Paired differences vanish on most items, so the variance-sensitive bounds should win there (ch. 0, 2).
   • Check the coverage of each interval on 10^4 simulated benchmarks. Then apply them to per-item results on the 14,042 test questions of MMLU (Hendrycks and coauthors, 2021), from the archived per-sample files of the first Hugging Face Open LLM Leaderboard (2023–2024) or from your own runs of a small open model.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Success: every interval covers at least 1 - \delta in simulation, and the report gives the number of items each inequality needs to separate two models 2 points apart, compared with McNemar’s test of LLM 9.6.
3. [Solo · ≈ 15 h] Minimax lower bounds: a written homework with a numerical check. The classical evaluation of the course, in the format of its homework assignments. Question: do the upper bounds of the course meet the lower bounds of chapter 8?
   • Prove Le Cam lower bounds for the Gaussian and Bernoulli means under quadratic loss (Example 8.3, Ex. 6) with explicit constants, then Assouad’s bound for a VC class (Thm 8.4) in full (ch. 8).
   • Simulate the excess risk of the empirical mean and of ERM on the hypercube distributions of Thm 8.4, with \Delta = c\sqrt{d/n}, for n from 10^2 to 10^5 (ch. 4, 8).
   • Deliverables: a 4–6 page typeset proof and one notebook. Success: complete proofs with constants, and a plot where the ratio of the measured risk to the lower bound stays within a constant factor over the whole range of n.

Group projects

1. [Group of 3 · ≈ 30 h each] Paper study: exponential weights against cross-validation, and sparse PAC-Bayesian aggregation (Alquier and Lounici, 2011). Question: when does aggregating M models beat selecting one by cross-validation, and does the price follow \log M/n? The paper is paper 4 of chapter 10.
   • Member 1: a dictionary of M heterogeneous regressors (polynomials, nearest neighbours, random forests, kernel ridge) fitted on one half of the California housing data (Pace and Barry, 1997; fetch_california_housing in scikit-learn), exponential weights (Def. 7.2) on the other half, and the oracle excess risk against M and n, compared with Thm 7.3 (ch. 7).
   • Member 2: K-fold cross-validation and the one-standard-error rule (Prop. 7.4) under the same budget, and the cost of fitting the dictionary and the weights on the same data, the flaw that the split of the ch. 7 code avoids (ch. 7).
   • Member 3: the sparse prior of the paper on a simulated linear model with p > n, computed by Markov chain Monte Carlo as in the paper, against the Lasso with theoretical and cross-validated \lambda (ch. 9, 10).
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: excess-risk curves with intervals over 10 seeds, a measured price of aggregation compared with \log M/n and \sqrt{\log M/n}, and one claim of the paper reproduced or refuted.
2. [Group of 3 · ≈ 30 h each] Lasso in high dimension: phase transitions and the calibration of \lambda. Question: where does the Lasso recover the support, and how far is the rate of Thm 9.4 from the measured error?
   • Member 1: simulated sparse regression over a grid of (n, p, s), with columns normalized as in Def. 9.1; the theoretical \lambda (Prop. 9.2) against the cross-validated one and the Dantzig selector of Candès and Tao (2007), solved as a linear program with scipy.optimize.linprog (ch. 9).
   • Member 2: exact support recovery against n/(2s\log(p-s)), to reproduce the sharp threshold of Wainwright (2009) for Gaussian designs, and the sup-norm error against the \sigma\sqrt{\log p/n} rate of Lounici (2008) (ch. 9, 10).
   • Member 3: an optimistic estimate of the RE constant \kappa of Def. 9.3, as the smallest ratio \|Xh\|^2/(n\|h_S\|^2) over sampled directions of the cone, and a log–log check of the s\log p/n rate (ch. 9).
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: the phase diagram shows the transition near n = 2s\log(p-s), and the measured prediction error stays below the bound of Thm 9.4 with the estimated \kappa.
3. [Group of 3 · ≈ 30 h each] Paper study: margin and norm bounds for neural networks and graph neural networks (Bartlett, Foster and Telgarsky, 2017). Question: do norm-based bounds, unlike parameter counts, track the generalization of an MLP and of a graph network? The subject prepares Graph ML and extends Deep Learning (Period 2), 7.1.
   • Member 1: MLPs on CIFAR-10 (Krizhevsky, 2009), with true and random labels; the spectral complexity of the paper divided by the margin, against the measured gap (ch. 5, 6).
   • Member 2: a graph convolutional network (Kipf and Welling, 2017) for graph classification on PROTEINS from TUDataset (Morris and coauthors, 2020), with the PAC-Bayesian bound of Liao, Urtasun and Zemel (2021) for graph neural networks.
   • Member 3: the shared protocol (several widths and sample sizes, 3 seeds) and the rank correlation between each measure and the gap, as in Jiang and coauthors (2020), with the parameter count as a VC-style baseline (ch. 4).
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: a table of rank correlations with intervals over seeds, and a justified answer on which measure tracks the gap for each model.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet and a basic scientific calculator allowed (question 2 needs logarithms and square roots), no other device, four questions. The sheet announces in-class exams but displays no format.

1. Question (4 points). Write the decomposition of the excess risk R(\hat h) - R^\star of ERM into approximation and estimation errors. Using Prop. 1.2 and the VC inequality, explain why ERM over a class of finite VC dimension is consistent relative to the class but not universally consistent, and how a sieve of classes repairs it.

   Expected: the decomposition of chapter 1, with R^\star the Bayes risk. The estimation error is at most 2\sup_h |R(h) - \hat R_n(h)| (Prop. 1.2), hence at most 2\varepsilon_n(\delta) on the event of the VC inequality, of order \sqrt{d/n} up to a logarithm, for every distribution (Cor. 4.2). The approximation error of a fixed class does not depend on the sample size. Classes of growing VC dimension d_n, with d_n\log n/n \to 0 and a union that approximates every Bayes rule, give universal consistency.

2. Question (5 points). (a) How many test examples guarantee |\hat R_n(h) - R(h)| \leq 0.05 with probability 0.95 for one fixed classifier, and simultaneously for 50 classifiers? (b) Orthonormal design, z = X^\top Y/n = (1.2, -0.3, 0.5) and \lambda = 0.4: compute the Lasso of Def. 9.1. (c) Evaluate the margin bound of Cor. 6.3 for (r, \gamma, n, \delta) = (1, 0.2, 10^4, 0.05).

   Expected: (a) n \geq \log(40)/(2 \times 0.05^2) \approx 738 for one classifier; the union bound replaces \delta by \delta/50 and gives n \geq \log(2000)/0.005 \approx 1521, about twice as many, not fifty times (Example 2.4, Ex. 1). (b) Soft-thresholding at \lambda (Ex. 7): \hat\beta = (0.8, 0, 0.1). (c) With Prop. 5.5, \frac{2r}{\gamma\sqrt n} + 3\sqrt{\frac{\log(2/\delta)}{2n}} \approx 0.10 + 0.04 = 0.14.

3. Question (5 points). Let X_1, \dots, X_M be centered and sub-Gaussian with parameter \sigma, not necessarily independent. Prove that \mathbb{E}\max_j X_j \leq \sigma\sqrt{2\log M}. Deduce that a class of M functions with values in [-1, 1] has an empirical Rademacher complexity (Def. 5.1) of at most \sqrt{2\log(2M)/n}.

   Expected: Jensen on the logarithm, \max_j e^{\lambda X_j} \leq \sum_j e^{\lambda X_j}, the sub-Gaussian bound, then \lambda = \sqrt{2\log M}/\sigma (Prop. 2.6).

   For a fixed sample, each of the 2M variables \pm\frac1n\sum_i \sigma_i f(X_i) is sub-Gaussian with parameter 1/\sqrt n, because \mathbb{E}e^{t\sigma_i a} = \cosh(ta) \leq e^{t^2a^2/2}. The absolute value of Def. 5.1 is the maximum over these 2M variables.

4. Question (6 points). Observations X_1, \dots, X_n are i.i.d. \mathcal{N}(\theta, \sigma^2) with \sigma known. With Le Cam’s two-point method (Thm 8.2, adapted to the quadratic loss) and Pinsker’s inequality, prove that the minimax quadratic risk satisfies \mathcal{M}_n \geq \sigma^2/(16n). Compare with the risk of the empirical mean.

   Expected:

   • Take the means 0 and 2s, and the event that \hat\theta is within s of 0. On this event the loss under the second mean is at least s^2 (triangle inequality); off it, the loss under the first mean exceeds s^2.
   • Averaging the two risks, the maximal risk is at least \frac{s^2}{2}(1 - \mathrm{TV}), where TV is the total variation between the two product laws (proof of Thm 8.2).
   • The KL of the products is n(2s)^2/(2\sigma^2) = 2ns^2/\sigma^2. With s = \sigma/(2\sqrt n) it equals 1/2, and Pinsker gives \mathrm{TV} \leq 1/2.
   • Hence \mathcal{M}_n \geq s^2/4 = \sigma^2/(16n). The empirical mean has risk \sigma^2/n: it is minimax up to the factor 16.

Grading rubric (proposal)

References

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014 — free pdf (authors’ website): chapters 3-6 (PAC, VC, no free lunch), 26 (Rademacher, margin); the backbone of ch. 1-6.
• V. Vapnik, Statistical Learning Theory, Wiley, 1998 — the historical source: ERM, VC dimension, generalization bounds (ch. 1, 3, 4).
• S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013 — chapter 2 (Hoeffding, Bernstein, maximal inequalities for sub-Gaussian variables), chapter 6 (the entropy method and the bounded differences inequality of McDiarmid); the foundation of ch. 2.
• M. J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge University Press, 2019 — ch. 2 (sub-Gaussians), ch. 4 (uniform laws, Rademacher complexity, VC classes), ch. 5 (metric entropy, Dudley’s chaining), ch. 7 (sparse linear models, the Lasso), ch. 8 (PCA in high dimension, the unsupervised block II), ch. 15 (minimax lower bounds, Le Cam/Fano); direct extensions of ch. 2, 5, 8 and 9.
• M. Mohri, A. Rostamizadeh, A. Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press, 2018 — Rademacher and margin bounds in textbook form (ch. 3-5; Lemma 5.7 is Lemma 5.4 here, Theorems 5.8 and 5.9 are used in ch. 6).
• L. Devroye, L. Györfi, G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996 — the classic reference on VC: Theorem 12.5 (full VC inequality, sketch of ch. 4).
• A. B. Tsybakov, Introduction to Nonparametric Estimation, Springer, 2009 — chapter 2: Le Cam, Fano, Assouad, minimax lower bounds (ch. 8).
• M. Ledoux, M. Talagrand, Probability in Banach Spaces: Isoperimetry and Processes, Springer, 1991 — the contraction lemma (Theorem 4.12, absolute-value version with constant 2L) and the theory of empirical processes (ch. 5).
• R. Meir, T. Zhang, “Generalization error bounds for Bayesian mixture algorithms”, Journal of Machine Learning Research 4, 2003 — JMLR page: Theorem 7, the contraction without absolute value and without \varphi(0) = 0 (Lemma 5.4).
• V. Koltchinskii, D. Panchenko, “Empirical margin distributions and bounding the generalization error of combined classifiers”, Annals of Statistics 30(1), 2002 — arXiv:math/0405343: Theorem 2, margin bounds uniform over the margin (the data-dependent margin note of ch. 6).
• P. Bickel, Y. Ritov, A. Tsybakov, “Simultaneous analysis of Lasso and Dantzig selector”, Annals of Statistics 37(4), 2009 — arXiv:0801.1095: the restricted eigenvalue condition (Def. 9.3) and the full oracle inequalities of which Theorem 9.4 is the skeleton.
• P. Bühlmann, S. van de Geer, Statistics for High-Dimensional Data: Methods, Theory and Applications, Springer, 2011 — compatibility conditions, oracle inequalities for the Lasso (ch. 6-7).
• T. Hastie, R. Tibshirani, M. Wainwright, Statistical Learning with Sparsity: The Lasso and Generalizations, CRC Press, 2015 — free pdf (authors’ website): the “applied” companion reading of ch. 9.
• K. Lounici, Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators, Electronic Journal of Statistics 2, 2008 — ch. 10, paper 1.
• K. Lounici, M. Pontil, S. van de Geer, A. B. Tsybakov, Oracle inequalities and optimal inference under group sparsity, Annals of Statistics 39(4), 2011 — ch. 10, paper 2.
• K. Lounici, “Generalized mirror averaging and D-convex aggregation”, Mathematical Methods of Statistics 16(3), 2007 — ch. 10, paper 3.
• P. Alquier, K. Lounici, “PAC-Bayesian bounds for sparse regression estimation with exponential weights”, Electronic Journal of Statistics 5, 2011 — HAL version — ch. 10, paper 4.
• N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006 — the sequential framework of exponential weights (ch. 7), sources of the “progression” inequalities.