Introduction to Statistical Learning

Contents

• Introduction and overview
• 0. Review: conditional expectation, concentration and convexity
• 1. The typology of learning problems and the Bayes predictors
• 2. Performance criteria and inference principles
• 3. Statistical models and main algorithms
• 4. Empirical risk minimization and complexity measures
• 5. Main theorems: learnability, lower bounds and consistency
• 6. Convex risk minimization
• 7. Aggregation and ensemble methods
• 8. Scoring and bipartite ranking
• 9. Complements for self-study
• 10. 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 called fit and predict on a classifier and now wants to know why, when and how fast learning from examples works.

Empirical first: on a two-class Gaussian problem whose best achievable error is known exactly (15.87 %), the 1-nearest-neighbour rule stays near 22 % however many examples it sees. The k-nearest-neighbour rule with k = \sqrt{n} reaches 15.9 % at n = 10\,000 (code in ch. 3). Why one rule converges to the optimum and the other does not, how fast, and what to do when the optimum is out of reach are the questions of this course.

The course builds the mathematical theory of supervised learning. It defines the learning problems and their optimal predictors, the classical algorithms that approximate them, and the inequalities that say how much data they need. It then studies the two ideas behind most modern classifiers: convex surrogate losses and the aggregation of many simple predictors. It ends with scoring, where one ranks individuals instead of labelling them.

It shares tools with Convex Optimization, Theoretical Foundations of Deep Learning and Statistical Learning with Extreme Values, and prepares Kernel Methods and Sequential Learning.

What you will be able to do

• Formalize a prediction task as a learning problem: input and output spaces, loss, risk and Bayes predictor.
• Derive the Bayes classifier, the Bayes risk and the excess-risk formula, and compute them on Gaussian models.
• Choose a performance criterion (risk, cost-sensitive risk, ROC curve, AUC) and estimate it with a confidence interval.
• Explain and compare the inference principles: plug-in, empirical risk minimization, penalization, maximum likelihood and local averaging.
• Prove the mistake bound of the perceptron and the Cover–Hart inequalities, and explain the proof of Stone’s theorem for nearest neighbours.
• Compute VC dimensions and Rademacher complexities, and turn them into generalization bounds with Hoeffding’s and McDiarmid’s inequalities.
• State the fundamental theorem of statistical learning, the no-free-lunch theorem and the minimax lower bounds, and explain what each one forbids.
• Decide whether a convex surrogate loss is classification-calibrated and bound the excess classification risk by its excess surrogate risk.
• Analyse bagging, random forests, AdaBoost and exponential-weights aggregation, and prove the training-error bound of AdaBoost.
• Build and evaluate scoring functions with the ROC curve and the AUC, and bound the deviations of the empirical AUC.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com states a single objective: to present the mathematical foundations of supervised learning. It lists seven themes, announces 8 theoretical sessions and 3 practical sessions, and links to a course web page. The Université Paris-Saclay course detail gives only the type of assessment, with no programme of its own.

Every official topic is taught on this page. The extensions beyond the syllabus are the review of ch. 0, the theory of bipartite ranking in ch. 8 (an expansion of the “scoring” of the second theme), and two self-study chapters: fast rates, stability and model selection (ch. 9), and research directions (ch. 10).

Where this course fits in the programme

Official prerequisites: undergraduate courses in analysis and probability. The course also uses a little convexity; ch. 0 reviews everything that is needed.

• Refreshers — Probability and Statistics (conditional expectation, inequalities), Linear Algebra, Analysis and Optimization (convex functions, gradients) and Scientific Python (NumPy and scikit-learn, used in every code block).
• Related courses of semester 1 — Convex Optimization gives the algorithms that minimize the surrogate risks of ch. 6. Theoretical Foundations of Deep Learning applies the complexity measures of ch. 4 to neural networks. Statistical Learning with Extreme Values carries the classification bounds of ch. 4 and the ROC analysis of ch. 8 to extreme regions and anomaly detection, and Computational Statistics shares the maximum-likelihood view of ch. 2.
• Courses of semester 2 that build on it — Kernel Methods (SVMs and regularized surrogate minimization in RKHS), Sequential Learning (exponential weights and online learning, ch. 7), Reinforcement Learning, Bayesian Machine Learning, Large Random Matrices (high-dimensional classification) and Responsible Machine Learning (fairness criteria built on the performance criteria of ch. 2).

Course outline

• 0. Review — conditional expectation, Hoeffding’s inequality, the union bound and convexity.
• 1. The typology of learning problems — the statistical model of learning, the main problems, and the Bayes predictors that solve them when the distribution is known.
• 2. Performance criteria and inference principles — excess risk, consistency, cost-sensitive criteria and test-set estimation; plug-in, ERM, penalization and maximum likelihood.
• 3. Statistical models and main algorithms — linear discriminant analysis, logistic regression, the perceptron, nearest neighbours, partitions and trees, with Stone’s theorem.
• 4. Empirical risk minimization and complexity measures — finite classes, VC dimension, Sauer’s lemma, the VC inequality and Rademacher complexity.
• 5. Main theorems — the fundamental theorem of statistical learning, no free lunch, minimax lower bounds, slow rates and structural risk minimization.
• 6. Convex risk minimization — surrogate losses, calibration, comparison inequalities and the estimation error of regularized linear classifiers.
• 7. Aggregation and ensemble methods — bagging and random forests, AdaBoost and the margin, exponential weights.
• 8. Scoring and bipartite ranking — ROC curves, AUC, optimal scoring functions and empirical AUC maximization.
• 9. Complements for self-study — fast rates under margin conditions, Bernstein’s inequality, hold-out selection and algorithmic stability.
• 10. Research directions and open problems — interpolation, implicit bias, PAC-Bayes, conformal prediction, ranking and distribution shift.

Session plan

24 h in class = 11 sessions (9 × 2 h + 2 × 3 h). The volume is the official one of the Université Paris-Saclay programme table: 16 h of lectures and 8 h of tutorials. master-mva.com announces 8 theoretical sessions and 3 practical sessions; the plan below turns them into 8 lectures of 2 h and 3 practical sessions of 3 h, 2 h and 3 h. This split, and the content of each session, is a proposal.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level material. The level never goes down from one session to the next.

Self-study, outside the 24 h (about 6 h in total): ch. 9 Complements: margin conditions and fast rates, Bernstein’s inequality, hold-out selection, stability (≈ 3 h, with Ex. 7 and 15) · ch. 10 Research directions and open problems (≈ 3 h).

How to study this module

• Read ch. 0 before session 1 if Hoeffding’s inequality or conditional expectation feel distant: every bound of ch. 4–8 is built from them.
• After each lecture, redo the proofs marked as complete without looking, then do the exercises listed in the row of the session.
• Run the code of each chapter and change one parameter (sample size, k, number of rounds, regularization); the printed numbers are quoted in the text, so you can check your environment.
• The code uses NumPy, SciPy and scikit-learn on synthetic data or data generated by scikit-learn; every block runs in a few seconds on a laptop.
• Keep a one-page sheet with the main inequalities (Hoeffding, McDiarmid, the Rademacher bound, Sauer, the comparison inequality): the written exams test whether you can combine them.

0. Review: conditional expectation, concentration and convexity

Three M1 tools carry the whole course: conditional expectation defines the optimal predictors, concentration inequalities control the gap between empirical and true risks, and convexity makes risks computable. This chapter states them in the form used later.

The Probability and Statistics refresher covers the same ground at a slower pace.

Conditional expectation

Concentration of sums

For a mean of n independent variables, Chebyshev gives a deviation probability of order 1/(n t^2). Learning needs much more: an exponential decay, so that a union bound over many predictors stays small.

The union bound completes the toolkit: for any events A_1, \dots, A_N, \mathbb{P}(A_1 \cup \dots \cup A_N) \leq \sum_{j=1}^N \mathbb{P}(A_j) . With N predictors, it costs a factor N in probability, hence only \log N inside the square root.

Convexity

Two facts are used in ch. 6. An infimum of affine functions is concave. A convex function of one variable has non-decreasing one-sided derivatives.

1. The typology of learning problems and the Bayes predictors

Before any algorithm, a learning problem must be stated precisely: what is observed, what is predicted, and how errors are counted. This chapter sets the statistical framework and identifies, for each problem, the best predictor one could use if the distribution were known.

The risk of the learned predictor, R(g_n), is a random variable: it depends on the sample.

A typology

Learning problems differ by the output space, by what is predicted and by the criterion.

The first four rows are supervised: the labels are observed. The last three are unsupervised. Between them, semi-supervised learning uses a few labels and many unlabelled points.

The sampling scheme also varies. In batch learning the whole sample is given at once, as above. In online learning the pairs arrive one by one and the predictor is updated after each; ch. 7 meets this setting through exponential weights. In active learning the learner chooses which labels to query, and in reinforcement learning its actions change the data it sees.

This course is about supervised batch learning, with classification as its main example.

The Bayes classifier

The theorem says more than optimality: a classifier loses little by disagreeing with g^* where \eta is close to 1/2. This remark produces the plug-in bound of ch. 2 and the fast rates of ch. 9.

In every case the optimal predictor depends on the unknown P only through the conditional distribution of Y given X. Learning means approximating it from the sample.

The simulation below checks both formulas of Theorem 1.3 on this model.

import numpy as np
from scipy.stats import norm

rng = np.random.default_rng(0)
n, sigma = 200_000, 1.0
mu = np.array([1.0, 0.0])                       # ||mu|| = 1
y = rng.choice([-1, 1], size=n)
X = y[:, None] * mu + sigma * rng.standard_normal((n, 2))

eta = 1 / (1 + np.exp(-2 * X @ mu / sigma**2))  # P(Y = +1 | X = x)
g_star = np.where(eta > 0.5, 1, -1)             # Bayes classifier
print("error of g* on the sample :", round(np.mean(g_star != y), 4))
print("Phi(-||mu||/sigma)        :", round(norm.cdf(-1.0), 4))
print("mean of min(eta, 1 - eta) :", round(np.mean(np.minimum(eta, 1 - eta)), 4))

The three printed values are 0.1599, 0.1587 and 0.1589. No classifier, however clever, can do better than 15.87 % on this problem.

2. Performance criteria and inference principles

A learning rule is judged by its risk, but that risk is random and the distribution is unknown. This chapter defines what a good rule is, how its performance is measured on data, and the principles from which rules are built.

What a good rule is

Consistency is asymptotic. A non-asymptotic guarantee is a statement of the form: with probability at least 1 - \delta over the sample, R(g_n) - R^* \leq \varepsilon(n, \delta) . The function \varepsilon gives the rate; ch. 4–5 compute it for many rules.

Criteria beyond the error probability

The error probability treats both kinds of mistakes alike. In medicine or fraud detection they do not cost the same. Write \mathrm{FPR}(g) = \mathbb{P}(g(X) = 1 \mid Y = -1) for the false positive rate and \mathrm{TPR}(g) = \mathbb{P}(g(X) = 1 \mid Y = 1) for the true positive rate, also called recall or sensitivity.

For c \in (0, 1), the cost-sensitive risk charges c for a false positive and 1 - c for a false negative: R_c(g) = \mathbb{E}\big[\, c\, \mathbb{1}\{Y = -1,\, g(X) = 1\} + (1 - c)\, \mathbb{1}\{Y = 1,\, g(X) = -1\} \big] .

With p = \mathbb{P}(Y = 1) and c = p, the cost-sensitive risk is proportional to the balanced error (\mathrm{FPR} + 1 - \mathrm{TPR})/2. Changing c moves the threshold on \eta; the ROC curve of ch. 8 records all the thresholds at once.

Measuring performance on data

The training error \hat R_n(g_n), computed on the sample used for learning, is optimistic: g_n was chosen to fit those points. Bounding that optimism is the purpose of ch. 4.

V-fold cross-validation splits the sample into V blocks, trains on V - 1 of them, tests on the last, and averages over the V choices. It estimates the risk of the rule trained on n(V-1)/V points; the folds are dependent, so Proposition 2.3 does not apply to it directly.

Inference principles

A rule has to turn the sample into a predictor. Four principles cover most algorithms.

Plug-in. Estimate \eta by some \hat\eta_n, then threshold: g_n(x) = +1 if \hat\eta_n(x) > 1/2.

A rate for estimating \eta in L^2 thus gives a rate for classification. The converse fails: classifying well only needs \hat\eta on the right side of 1/2.

Empirical risk minimization (ERM). Fix a class \mathcal{G} of classifiers and choose \hat g_n \in \arg\min_{g \in \mathcal{G}} \hat R_n(g), \qquad \hat R_n(g) = \frac{1}{n} \sum_{i=1}^n \mathbb{1}\{g(X_i) \neq Y_i\} .

A richer class lowers the approximation error and raises the estimation error. This trade-off is the central tension of the course.

Penalization. Let the data choose the richness of the class.

Maximum likelihood. If one posits a model \{p_\theta(y \mid x)\} for the conditional law of Y, the conditional maximum-likelihood estimator maximizes \sum_i \log p_\theta(Y_i \mid X_i).

Local averaging is a fifth, nonparametric route: it estimates \eta(x) by averaging the labels of the sample points near x, then plugs in. It is the subject of the second half of ch. 3.

3. Statistical models and main algorithms

The classical classification algorithms each implement one of the principles of ch. 2. This chapter presents them by family, with one main theorem per family: a closed form for discriminant analysis, a mistake bound for the perceptron, and universal consistency for nearest neighbours.

Discriminant analysis

LDA plugs in the class frequencies, the class means and the pooled empirical covariance. With different covariances, the quadratic terms remain and the boundary becomes a quadric (QDA). Example 1.5 is the case \mu_\pm = \pm \mu and \Sigma = \sigma^2 I, where w = 2\mu / \sigma^2 and b = 0.

Linear discriminative models

Newton’s method (iteratively reweighted least squares) or a gradient method solves it. On linearly separable data the infimum is not attained, since the loss decreases along any separating direction; a penalty \lambda \|\theta\|^2 restores a minimizer.

The perceptron (Rosenblatt, 1958) is the oldest learning algorithm. It starts from w_0 = 0 and runs through the examples; whenever Y_i \langle w, X_i \rangle \leq 0, it updates w \leftarrow w + Y_i X_i.

The bound does not involve the dimension: the margin, not the number of parameters, measures the difficulty. Margins return in ch. 6 and in the analysis of boosting in ch. 7.

Local averaging

The choice k = \sqrt{n} meets both conditions; k = 1 does not. The next result says what happens to the 1-NN rule.

Partitions and trees

Trees are readable and handle mixed features, but small changes of the sample change the splits: they have high variance. The ensembles of ch. 7 exploit exactly this.

Two more families complete the picture. Support vector machines minimize a regularized hinge loss over linear functions or a reproducing kernel Hilbert space; ch. 6 analyses them, and Kernel Methods develops them. Neural networks x \mapsto \sum_j a_j\, \sigma(w_j^\top x + b_j) are trained with the same surrogate losses; Deep Learning and Theoretical Foundations of Deep Learning study them.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

rng = np.random.default_rng(1)
mu = np.array([1.0, 0.0])
def sample(n):
    y = rng.choice([-1, 1], size=n)
    return y[:, None] * mu + rng.standard_normal((n, 2)), y

Xte, yte = sample(20_000)
eta = 1 / (1 + np.exp(-2 * Xte @ mu))
print("Bayes risk  ~", round(np.mean(np.minimum(eta, 1 - eta)), 4))
print("Cover-Hart  ~", round(np.mean(2 * eta * (1 - eta)), 4))
for n in [100, 1_000, 10_000]:
    X, y = sample(n)
    for k in [1, int(np.sqrt(n))]:
        err = 1 - KNeighborsClassifier(n_neighbors=k).fit(X, y).score(Xte, yte)
        print(f"n = {n:6d}   k = {k:3d}   test error = {err:.4f}")

The 1-NN error stays at 0.219–0.227, around the Cover–Hart limit 0.225. With k = \sqrt{n} the error falls from 0.191 to 0.162, then to 0.159: Stone’s theorem at work.

4. Empirical risk minimization and complexity measures

By Proposition 2.5, the estimation error of ERM is at most twice the uniform deviation \sup_{\mathcal{G}} |\hat R_n - R|. This chapter bounds that supremum: first for finite classes, then through two complexity measures, the VC dimension and the Rademacher complexity.

Finite classes

For N = 10^6 rules, n = 10\,000 examples and \delta = 0.05, the uniform deviation is at most \sqrt{17.50 / 20\,000} = 0.030. A million candidates cost only a logarithm.

Without noise the rate is 1/n instead of 1/\sqrt{n}: in the example above, 0.0017 instead of 0.03. Chapter 9 explains the intermediate regimes.

Growth function and VC dimension

Most useful classes are infinite, but on n points they produce finitely many labellings.

The growth function is thus either 2^n for all n or bounded by a polynomial of degree V: there is nothing in between.

The error vectors (\mathbb{1}\{g(X_i) \neq Y_i\})_i are in one-to-one correspondence with the traces of \mathcal{G}, which is why S_{\mathcal{G}} appears. With Lemma 4.6 the deviation is of order \sqrt{V \log n / n}, for every distribution.

Rademacher complexity

The VC dimension ignores the distribution and handles only binary functions. Linear functions with a bounded norm in high dimension have a large VC dimension, yet margins suggest that they are easy to learn. A data-dependent measure handles both issues.

It measures how well the class can correlate with pure noise. A class that fits every sign pattern has complexity close to its range; a single function has complexity 0.

For half-planes in \mathbb{R}^2 (V = 3), \delta = 0.05 and n = 10\,000, the bound is 0.175; at n = 100\,000 it is 0.061. The constants are pessimistic, but the shape \sqrt{V/n} is right: ch. 5 shows it cannot be improved beyond the logarithm.

The dimension does not appear, only the norms. Chapter 6 combines this with surrogate losses.

import numpy as np

rng = np.random.default_rng(2)
n, d, B, reps = 200, 5, 1.0, 2000
X = rng.standard_normal((n, d))
X /= np.linalg.norm(X, axis=1, keepdims=True)    # ||x_i|| = 1
sig = rng.choice([-1, 1], size=(reps, n))         # Rademacher signs

# linear class {x -> <w, x> : ||w|| <= B}: the sup equals (B/n) ||sum_i sigma_i x_i||
lin = B * np.linalg.norm(sig @ X, axis=1).mean() / n
print(f"linear     : {lin:.4f}   bound B/sqrt(n) = {B / np.sqrt(n):.4f}")

# thresholds x -> 1{x > t}: on sorted points, the n + 1 patterns 0...0 1...1
patterns = np.tril(np.ones((n + 1, n)), k=-1)[:, ::-1]
thr = (sig @ patterns.T).max(axis=1).mean() / n
print(f"thresholds : {thr:.4f}   Massart sqrt(2 log(n+1)/n) = {np.sqrt(2 * np.log(n + 1) / n):.4f}")

The linear class gives 0.067 against the bound 0.071: Proposition 4.13 is nearly tight. For thresholds the estimate is 0.055, while Massart’s lemma gives 0.230. The n + 1 patterns are strongly correlated, and the union bound inside Lemma 4.11 ignores it; chaining arguments remove the logarithm.

5. Main theorems: learnability, lower bounds and consistency

Chapter 4 showed that a finite VC dimension is enough for ERM to learn. This chapter shows that it is also necessary, that the rate \sqrt{V/n} cannot be improved, that no rule learns every distribution at a fixed rate, and how growing classes yield universally consistent rules.

No free lunch

No rule learns every problem from a sample that has not seen most of the domain: prior knowledge, encoded by a class or by assumptions on P, is unavoidable.

The fundamental theorem

Lower bounds

So ERM over a VC class is optimal up to a logarithm. The lower bounds hold over all distributions in a fixed class; without a class, the situation is worse.

Stone’s theorem gives consistency for every distribution; Theorem 5.6 says that no rate can hold for every distribution. Rates require assumptions: the Bayes classifier in a VC class, smoothness of \eta, or the margin conditions of ch. 9.

Consistency with growing classes

Histograms on a grid whose mesh shrinks, linear combinations of a growing number of stumps, and networks with a growing number of units all fit this scheme. The theorem requires knowing how fast to grow the class; penalization lets the data decide.

The rule does as well as if an oracle had told it the best class, up to the penalty. Making the penalty data-dependent, for instance with \hat{\mathfrak{R}}_n, is the idea of Rademacher penalization (Koltchinskii, 2001).

6. Convex risk minimization

ERM with the 0–1 loss is computationally hard: even approximating, within some constant factor, the largest number of sample points that a half-space classifies correctly is NP-hard (Ben-David, Eiron and Long, 2003). Most practical classifiers instead minimize a convex surrogate of the margin y f(x). This chapter asks when this still leads to the Bayes classifier, and how fast.

Calibration

Conditioning on X = x reduces the question to a single number \alpha = f(x).

Calibration means that the pointwise minimizer of the surrogate always has the sign of the Bayes classifier.

The hinge, logistic, exponential and square losses have \varphi'(0) = -1, -\frac12, -1, -2: all are calibrated. The perceptron loss \max(0, -u) is not (Exercise 11).

Comparison inequalities

The minimizers tell another story. The logistic minimizer recovers \eta through the sigmoid, so logistic regression estimates probabilities; the hinge minimizer keeps only the sign, so SVM outputs are not probabilities.

Estimation error

Combining Theorems 6.4 and 6.7, the excess classification risk is at most \psi^{-1} of the estimation error plus the approximation error \inf_{\mathcal{F}_B} R_\varphi - R_\varphi^*. Over a rich class — a reproducing kernel Hilbert space with a universal kernel, or combinations of base classifiers — with a radius B_n growing slowly, both terms vanish. This is how the consistency of SVMs (Steinwart, 2005) and of regularized boosting (Lugosi and Vayatis, 2004) is proved.

Minimizing the empirical \varphi-risk is a convex problem; Convex Optimization covers the algorithms.

import numpy as np
from scipy.stats import norm
from sklearn.linear_model import LogisticRegression
from sklearn.svm import LinearSVC

rng = np.random.default_rng(3)
mu = np.array([1.0, 0.5])                    # Bayes risk = Phi(-||mu||)
def sample(n):
    y = rng.choice([-1, 1], size=n)
    return y[:, None] * mu + rng.standard_normal((n, 2)), y
X, y = sample(500)
Xte, yte = sample(50_000)

Z = np.c_[X, np.ones(len(X))] * y[:, None]   # rows y_i (x_i, 1)
w = np.zeros(3)
for _ in range(2000):                        # gradient descent on mean exp(-y f(x))
    w += 0.1 * (Z * np.exp(-Z @ w)[:, None]).mean(axis=0)
f_exp = np.c_[Xte, np.ones(len(Xte))] @ w

print(f"Bayes risk   {norm.cdf(-np.linalg.norm(mu)):.4f}")
print(f"logistic     {1 - LogisticRegression(C=1e4).fit(X, y).score(Xte, yte):.4f}")
svm = LinearSVC(C=1.0, loss='hinge', random_state=0)   # the default loss is the squared hinge
print(f"hinge (SVM)  {1 - svm.fit(X, y).score(Xte, yte):.4f}")
print(f"exponential  {np.mean(np.sign(f_exp) != yte):.4f}")

The test errors are 0.1345, 0.1362 and 0.1347: all three surrogates land within 0.005 of the Bayes risk. Here the Bayes classifier is linear, so the approximation error vanishes and calibration does the rest.

7. Aggregation and ensemble methods

Instead of choosing one predictor, one can combine many. Averaging independent-looking predictors reduces variance (bagging, random forests); reweighting the data reduces bias (boosting); exponential weights combine a finite family almost as well as its best member.

Bagging and random forests

Bagging (Breiman, 1996) draws B bootstrap samples, each made of n draws with replacement from D_n, trains the same base rule on each, and averages the outputs (regression) or takes a majority vote (classification).

Averaging leaves the bias unchanged and removes only the uncorrelated part of the variance: as B \to \infty, the term \rho s^2 remains. Decorrelating the base predictors is therefore the point.

The same holds for votes. If 25 classifiers erred independently with probability 0.3, Hoeffding’s inequality would bound the error of the majority by e^{-2 \cdot 25 \cdot 0.2^2} = 0.135, and the exact binomial tail is 0.017. Independence never holds exactly, and Proposition 7.1 measures what correlation costs.

from sklearn.datasets import make_classification
from sklearn.ensemble import BaggingClassifier, RandomForestClassifier
from sklearn.tree import DecisionTreeClassifier

X, y = make_classification(n_samples=1000, n_features=10, n_informative=5,
                           flip_y=0.05, random_state=0)
Xtr, ytr, Xte, yte = X[:500], y[:500], X[500:], y[500:]
models = {
    "one deep tree": DecisionTreeClassifier(random_state=0),
    "bagging, 200 trees": BaggingClassifier(DecisionTreeClassifier(), n_estimators=200,
                                            oob_score=True, random_state=0),
    "random forest, 200 trees": RandomForestClassifier(n_estimators=200, oob_score=True,
                                                       random_state=0),
}
for name, m in models.items():
    m.fit(Xtr, ytr)
    oob = f"   out-of-bag {1 - m.oob_score_:.3f}" if hasattr(m, "oob_score_") else ""
    print(f"{name:25s} test error {1 - m.score(Xte, yte):.3f}{oob}")

One tree has a test error of 0.120, bagging 0.084 and the forest 0.068; the out-of-bag estimates (0.070 and 0.064) are close to the test errors.

Boosting

Misclassified points gain weight, so each new base classifier concentrates on the examples its predecessors got wrong.

If every base classifier beats chance by \gamma > 0, the training error is at most e^{-2\gamma^2 T}, hence 0 after T > \log(n)/(2\gamma^2) rounds.

AdaBoost is thus coordinate descent on the exponential surrogate of ch. 6, over linear combinations of base classifiers. Gradient boosting (Friedman, 2001) replaces the exponential loss by any differentiable loss.

The code below runs AdaBoost with decision stumps x \mapsto s\, \mathrm{sign}(x_j - t), written from scratch.

import numpy as np
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=1000, n_features=10, n_informative=5,
                           flip_y=0.05, random_state=0)
y = 2 * y - 1
Xtr, ytr, Xte, yte = X[:500], y[:500], X[500:], y[500:]

def stump(X, y, w):
    """Best rule s * sign(x_j - t) for the weights w (summing to 1)."""
    Wneg, best = w[y == -1].sum(), (np.inf,)
    for j in range(X.shape[1]):
        o = np.argsort(X[:, j])
        err = Wneg + np.r_[0, np.cumsum((w * y)[o])]   # error of "+1 iff x_j > t"
        for s, e in ((1, err), (-1, 1 - err)):
            k = np.argmin(e)
            if e[k] < best[0]:
                best = (e[k], j, X[o[k - 1], j] if k > 0 else -np.inf, s)
    return best

w, Ftr, Fte, bound = np.full(500, 1 / 500), np.zeros(500), np.zeros(500), 1.0
for t in range(1, 201):
    eps, j, thr, s = stump(Xtr, ytr, w)
    alpha = 0.5 * np.log((1 - eps) / eps)
    h_tr, h_te = s * np.where(Xtr[:, j] > thr, 1, -1), s * np.where(Xte[:, j] > thr, 1, -1)
    Ftr, Fte = Ftr + alpha * h_tr, Fte + alpha * h_te
    w = w * np.exp(-alpha * ytr * h_tr); w /= w.sum()
    bound *= 2 * np.sqrt(eps * (1 - eps))
    if t in (1, 10, 50, 200):
        print(f"T = {t:3d}  train {np.mean(np.sign(Ftr) != ytr):.3f}  "
              f"bound {bound:.3f}  test {np.mean(np.sign(Fte) != yte):.3f}")

After 1, 10, 50 and 200 rounds the training error is 0.128, 0.086, 0.054 and 0.010, below the bound of Theorem 7.4 (0.668, 0.429, 0.266, 0.108). The test error falls from 0.124 to 0.096 at 50 rounds and stays near 0.10 afterwards.

Margins

Boosting often keeps improving its test error after the training error has reached 0 (Schapire, Freund, Bartlett and Lee, 1998). The explanation is the margin: normalized by \sum_t \alpha_t, the output F_T lies in the convex hull of \mathcal{H}, and further rounds increase the margins Y_i F_T(X_i).

The number of rounds does not appear: only the margin distribution and the complexity of the base class do. Lugosi and Vayatis (2004) combine such bounds with the comparison inequality of ch. 6 to prove that regularized boosting is Bayes-risk consistent.

Exponential weights

Take M fixed predictors f_j (trained on a separate sample, or given as experts), and a loss in [0, 1] that is convex in the prediction. Pairs arrive one at a time, and L_{t-1,j} denotes the cumulative loss of f_j before round t. The exponentially weighted average predicts p_t = \sum_{j=1}^M w_{t,j}\, f_j(x_t), \qquad w_{t,j} \propto e^{-\eta L_{t-1, j}} .

On independent data, averaging the successive aggregates turns this into a batch guarantee of order \sqrt{\log M / n} (Cesa-Bianchi, Conconi and Gentile, 2004); for exp-concave losses, mirror averaging reaches \log M / n (Juditsky, Rigollet and Tsybakov, 2008). Stacking (Wolpert, 1992) learns the weights by cross-validation instead. Sequential Learning develops the online side.

8. Scoring and bipartite ranking

In credit scoring, medical triage or document retrieval, one must order individuals by their chance of being positive rather than label them. The criterion becomes a curve, and the optimal rules are the increasing transforms of \eta.

A random score has AUC 1/2; a score that puts every positive above every negative has AUC 1.

Scoring thus asks for the order induced by \eta: less than estimating \eta, more than classifying at a single threshold.

Maximizing the AUC is therefore a classification problem on pairs, for the pairwise rule \mathrm{sign}(s(x) - s(x')).

Empirical AUC maximization

The empirical ranking risk minimizer therefore has excess ranking risk of order \sqrt{V \log n / n}, as in classification. This argument is the one of Clémençon, Lugosi and Vayatis (2008), who also obtain faster rates under low-noise conditions by Hoeffding’s decomposition of U-statistics.

Pairwise surrogates. As in ch. 6, the indicator of a misordered pair is replaced by a convex loss of the score difference. RankBoost (Freund, Iyer, Schapire and Singer, 2003) minimizes, over linear combinations F of base scores, the pairwise exponential risk \frac{1}{n_+ n_-} \sum_{i : Y_i = 1} \sum_{j : Y_j = -1} \exp\big(-(F(X_i) - F(X_j))\big) . It runs the rounds of Definition 7.3 with the weights placed on the n_+ n_- positive–negative pairs instead of the points. Ranking SVMs use the hinge loss on the same pairs.

Univariate surrogates. The minimizer \log(\eta/(1 - \eta)) of the logistic risk (Example 6.5) is strictly increasing in \eta, so by Theorem 8.3 it is an optimal score. The hinge minimizer \mathrm{sign}(2\eta - 1) collapses the order and is not.

TreeRank (Clémençon and Vayatis, 2009) builds a piecewise-linear approximation of the optimal ROC curve by recursive partitioning. Each cell C is one segment of the curve, of horizontal length \alpha(C) = P_-(C) and vertical length \beta(C) = P_+(C). Splitting C into a part C' ranked first and the rest adds a vertex, and the AUC gains the area of a triangle: \tfrac12 \big( \alpha(C)\, \beta(C') - \beta(C)\, \alpha(C') \big) . Maximizing the empirical version of this gain over C' \subset C is a cost-sensitive classification problem inside C (Proposition 2.2).

import numpy as np
from scipy.stats import norm, rankdata
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import roc_auc_score

rng = np.random.default_rng(4)
mu = np.array([1.0, 0.0])
def sample(n):
    y = rng.choice([-1, 1], size=n)
    return y[:, None] * mu + rng.standard_normal((n, 2)), y

def auc(s, y):
    """Empirical AUC through the Mann-Whitney rank formula (mid-ranks for ties)."""
    r, n1, n0 = rankdata(s), (y == 1).sum(), (y == -1).sum()
    return (r[y == 1].sum() - n1 * (n1 + 1) / 2) / (n1 * n0)

X, y = sample(300)
Xte, yte = sample(20_000)
s_lr = LogisticRegression().fit(X, y).decision_function(Xte)
print("theory Phi(sqrt 2)   :", round(norm.cdf(np.sqrt(2)), 4))
print("oracle score mu'x    :", round(auc(Xte @ mu, yte), 4))
print("logistic regression  :", round(auc(s_lr, yte), 4), round(roc_auc_score(yte, s_lr), 4))
print("useless coordinate   :", round(auc(Xte[:, 1], yte), 4))

The oracle score reaches 0.9218 and logistic regression trained on 300 points 0.9217, with the rank formula and scikit-learn agreeing; the useless coordinate gives 0.503, the AUC of chance.

9. Complements for self-study

This chapter extends the in-class material in three directions: rates faster than 1/\sqrt{n} when the labels are not too noisy (a complement to ch. 4–5), the selection of a rule on held-out data (ch. 2), and algorithmic stability, a route to generalization that avoids complexity measures (ch. 4 and 6).

Margin conditions and fast rates

The \sqrt{V/n} lower bound of Theorem 5.5 is built from distributions with \eta close to 1/2 on a large set. Excluding them gives faster rates.

The difference of losses \mathbb{1}\{g(X) \neq Y\} - \mathbb{1}\{g^*(X) \neq Y\} is non-zero only on A. Its variance is therefore at most \mathbb{P}(A): a classifier with small excess risk has a small-variance excess loss. Bernstein’s inequality turns small variances into fast rates.

Without the condition, Proposition 4.1 gives \sqrt{\log N / n}. Under the margin condition with exponent \alpha, the same argument with localization gives the intermediate rate (\log N / n)^{(1+\alpha)/(2+\alpha)} (Tsybakov, 2004), and local Rademacher complexities extend it to infinite classes (Bartlett, Bousquet and Mendelson, 2005).

Selecting a rule on held-out data

Choosing k for nearest neighbours, the depth of a tree or the regularization of an SVM among M values thus costs \sqrt{\log M / m}. Cross-validation averages several splits to reduce the variance of the selection; its theory is surveyed by Arlot and Celisse (2010).

Algorithmic stability

Complexity measures look at the whole class. Stability looks only at the rule: how much does the output change when one example changes?

Regularized ERM is stable. With a convex loss \varphi that is L-Lipschitz, inputs of norm at most \rho and the penalty \lambda \|w\|^2, it is stable with \beta = 2L^2\rho^2/(\lambda n) in the averaged sense used by Shalev-Shwartz and Ben-David (2014, ch. 13), which suffices for Proposition 9.7. The trade-off reappears: a large \lambda makes the rule stable but biased. Stability also explains why stochastic gradient descent with few passes generalizes (Hardt, Recht and Singer, 2016).

10. Research directions and open problems

This chapter, for self-study, surveys questions on which the theory of the previous chapters is being extended. It cites only the main references; the papers themselves give the precise statements.

Interpolation and benign overfitting

Zhang, Bengio, Hardt, Recht and Vinyals (2017) observed that deep networks trained by gradient descent fit random labels perfectly, yet generalize on real labels. For such interpolating predictors, the uniform bounds of ch. 4 are vacuous, and Nagarajan and Kolter (2019) argue that two-sided uniform convergence may be unable to explain this behaviour at all.

Belkin, Hsu, Ma and Mandal (2019) documented the double descent curve: the test error can decrease again beyond the interpolation threshold. Bartlett, Long, Lugosi and Tsigler (2020) characterized when the minimum-norm interpolant in linear regression is consistent, through effective ranks of the covariance. A sharp theory for classification with general features remains open.

Implicit bias of optimization

Soudry, Hoffer, Nacson, Gunasekar and Srebro (2018) proved that gradient descent on the logistic loss over separable data converges in direction to the hard-margin SVM solution. The optimization algorithm, not an explicit penalty, selects the predictor, and the margin theory of ch. 7 applies to it. Lyu and Li (2020) extended the result to homogeneous neural networks. Which implicit biases arise for other architectures and algorithms, and what they imply for generalization, is an active question.

PAC-Bayes and data-dependent bounds

PAC-Bayesian bounds (McAllester, 1999; Catoni, 2007) control the risk of a randomized predictor by the Kullback–Leibler divergence between a data-dependent posterior and a fixed prior. Dziugaite and Roy (2017) optimized such a bound to obtain the first non-vacuous guarantee for a stochastic deep network on MNIST. Alquier (2024) surveys the field. Tight bounds for the deterministic networks used in practice are still missing.

Distribution-free uncertainty

Conformal prediction (Vovk, Gammerman and Shafer, 2005) turns any predictor into prediction sets with exact finite-sample coverage under exchangeability; the split version is analysed by Lei, G’Sell, Rinaldo, Tibshirani and Wasserman (2018). Angelopoulos and Bates (2023) give an introduction. Conditional coverage, which is impossible in full generality, and coverage under distribution shift are open directions.

Ranking, scoring and U-statistics

Clémençon and Vayatis (2007) studied the problem of ranking only the best instances, where the criterion focuses on the beginning of the ROC curve. Empirical risks over all pairs cost O(n^2); Clémençon, Colin and Bellet (2016) showed that incomplete U-statistics built on a few random pairs keep the statistical rates. Consistent surrogates for partial-AUC criteria and for multipartite ranking are only partly understood.

Distribution shift and fairness

Ben-David, Blitzer, Crammer, Kulesza, Pereira and Vaughan (2010) bounded the risk on a target domain by the source risk plus a divergence between the domains. Hardt, Price and Srebro (2016) defined equality of opportunity, a constraint on the true positive rates of ch. 2 across groups, and showed how to enforce it by post-processing a score. Responsible Machine Learning develops these questions.

Theory of random forests

Biau, Devroye and Lugosi (2008) proved the consistency of simplified random forests, and Scornet, Biau and Vert (2015) the consistency of Breiman’s forests in additive regression models. Wager and Athey (2018) built confidence intervals for forest-based estimates of treatment effects. The consistency of Breiman’s original algorithm for general distributions is still open.

Questions to explore

• Can a margin-based bound (Theorem 7.7) predict the test error of a trained boosting model or network within a factor of two, on real data?
• For which surrogate losses is the minimizer of the empirical risk, on separable data, an optimal scoring function in the sense of Theorem 8.3?
• How do the fast rates of ch. 9 combine with interpolation: can an interpolating classifier achieve them?
• What is the sample complexity of learning a classifier that satisfies a fairness constraint at a given tolerance?
• Can stability arguments (ch. 9) replace uniform convergence for rules such as random forests or gradient boosting?

Exercises

Levels: ★ apply the course, ★★ combine results or prove a short statement, ★★★ open-ended or research-flavoured. Exercises 6, 14 and 17 are computational.

1. ★ A Bayes classifier with costs. The input takes three values a, b, c with the following probabilities and regression function:

   x	a	b	c
   \mathbb{P}(X = x)	0.5	0.3	0.2
   \eta(x)	0.9	0.4	0.1

   Find the Bayes classifier and the Bayes risk, and the excess risk of the constant classifier +1. Then find the classifier that minimizes the cost-sensitive risk with cost 0.3 for a false positive.

   Solution: g^*(a) = +1 and g^*(b) = g^*(c) = -1, so R^* = 0.5 \times 0.1 + 0.3 \times 0.4 + 0.2 \times 0.1 = 0.19 .

   The constant +1 has risk \mathbb{P}(Y = -1) = 0.41. Theorem 1.3 gives the same excess, 0.3 \times 0.2 + 0.2 \times 0.8 = 0.22.

   With cost 0.3, Proposition 2.2 predicts +1 where \eta > 0.3, that is at a and b. Its cost-sensitive risk is 0.015 + 0.054 + 0.014 = 0.083, against 0.113 for g^*.

2. ★ Bayes risk of Gaussian classes. In Example 1.5 with \sigma = 1, compute R^* for \|\mu\| = 1.5.

   Then take all coordinates of \mu \in \mathbb{R}^d equal to m = 0.2. Compute R^* for d = 25 and d = 100, and explain the result.

   Solution: R^* = \Phi(-1.5) = 0.0668. With \|\mu\| = m\sqrt{d}, the risk is \Phi(-1) = 0.1587 for d = 25 and \Phi(-2) = 0.0228 for d = 100.

   Many weakly informative independent features add up, provided the classifier weights them correctly. LDA (Proposition 3.1) has to estimate d coordinates of w to do so, which is where estimation error enters.

3. ★ How many test points? How large must a test sample be for the test error to be within \pm 0.01 of the risk with probability 0.95? Compare with Chebyshev’s inequality.

   Solution: by Proposition 2.3, m \geq \log(40) / (2 \times 10^{-4}) = 18\,444; for \pm 0.02, 4611 points suffice.

   Chebyshev with \mathrm{Var} \leq 1/4 requires 1/(4 m \varepsilon^2) \leq 0.05, that is m \geq 50\,000. The exponential tail of Hoeffding’s inequality is worth a factor 2.7 here, and much more at smaller \delta.

4. ★ VC dimensions. Compute the VC dimension of (a) axis-parallel rectangles in \mathbb{R}^2 (label +1 inside), and (b) unions of two intervals on the line.

   Solution: (a) V = 4. Four points in a diamond, (\pm 1, 0) and (0, \pm 1), are shattered. Among any five points, keep a leftmost, a rightmost, a lowest and a highest one; the smallest rectangle containing them contains the fifth, so the labelling with the fifth point negative and the others positive is impossible.

   2. V = 4. On sorted points, a union of two intervals realizes exactly the labellings with at most two blocks of +1. All labellings of four points have at most two such blocks, while (+, -, +, -, +) has three.

5. ★ Two \psi-transforms. Derive H and \psi for the square loss and the exponential loss (Example 6.5). For an excess exponential risk of 0.005, bound the excess classification risk exactly and with \psi(\theta) \geq \theta^2/2.

   Solution: for the square loss, C_\eta(\alpha) is minimized at \alpha = 2\eta - 1, so H(\eta) = 4\eta(1 - \eta) and \psi(\theta) = 1 - (1 - \theta^2) = \theta^2.

   For the exponential loss, the minimizer is \frac12 \log(\eta/(1-\eta)), so H(\eta) = 2\sqrt{\eta(1-\eta)} and \psi(\theta) = 1 - \sqrt{1 - \theta^2}.

   Solving 1 - \sqrt{1 - \theta^2} \leq 0.005 gives \theta \leq \sqrt{1 - 0.995^2} = 0.0999. The quadratic bound gives \sqrt{0.01} = 0.1: almost the same.

6. ★ Choosing k, in Python. Rerun the code of Example 3.8 with n = 2000 and k \in \{1, 3, 15, 45, 200, 1000, 1999\}. Explain both ends, and check the Cover–Hart bound.

   Hints and expected result: replace the loop of Example 3.8 by the following.

   import numpy as np
   from sklearn.neighbors import KNeighborsClassifier
   
   rng = np.random.default_rng(1)
   mu = np.array([1.0, 0.0])
   def sample(n):
       y = rng.choice([-1, 1], size=n)
       return y[:, None] * mu + rng.standard_normal((n, 2)), y
   
   X, y = sample(2000)
   Xte, yte = sample(20_000)
   for k in [1, 3, 15, 45, 200, 1000, 1999]:
       err = 1 - KNeighborsClassifier(n_neighbors=k).fit(X, y).score(Xte, yte)
       print(f"k = {k:4d}   test error = {err:.4f}")

   The errors are 0.223, 0.193, 0.170, 0.163, 0.158, 0.158 and 0.504. Small k has high variance, and k = 1 sits at the Cover–Hart limit 0.225, below 2R^*(1 - R^*) = 0.267.

   Large k still works here because the Bayes boundary is a line through the centre of the data, so even half of the sample is a good neighbourhood. At k = n - 1 the rule votes over the whole sample: it is a constant classifier with error 0.5.

7. ★★ A sharper plug-in inequality. Show that the plug-in classifier satisfies R(\hat g) - R^* \leq 2\, \mathbb{E}\big[\,|\hat\eta(X) - \eta(X)|\; \mathbb{1}\{\hat g(X) \neq g^*(X)\}\big] . Deduce that under Massart’s condition |2\eta - 1| \geq h, R(\hat g) - R^* \leq \frac{4}{h}\, \mathbb{E}\big[(\hat\eta(X) - \eta(X))^2\big] .

   Solution: the first bound is the proof of Proposition 2.4 before dropping the indicator.

   Where \hat g \neq g^*, the estimate is on the other side of 1/2, so |\hat\eta - \eta| \geq |\eta - 1/2| \geq h/2. Hence \mathbb{1}\{\hat g \neq g^*\} \leq 2|\hat\eta - \eta| / h, and inserting this gives the result.

   The classification rate is now the square of the L^2 rate for \eta, instead of its square root.

8. ★★ The perceptron bound is tight. Run the perceptron on the points e_1, \dots, e_d of \mathbb{R}^d with arbitrary labels. Count its mistakes and compare with Theorem 3.3.

   Solution: the unit vector w^* = \frac{1}{\sqrt d} \sum_j y_j e_j separates the data with margin \gamma = 1/\sqrt{d}, and \rho = 1, so the bound is (\rho/\gamma)^2 = d.

   In the first pass, w is a combination of the earlier, orthogonal e_j, so \langle w, e_i \rangle = 0 and each example triggers an update: d mistakes. After the pass, w = \sum_j y_j e_j classifies everything correctly, and the bound is attained.

9. ★★ Rademacher complexity by hand. On two points x_1 < x_2, compute \hat{\mathfrak{R}}_2 for the thresholds x \mapsto \mathbb{1}\{x > t\} and for all functions with values in \{0, 1\}. Compare with Lemma 4.11.

   Solution: the threshold patterns are (0,0), (0,1) and (1,1).

   Consider the four sign vectors (+,+), (+,-), (-,+) and (-,-) in turn. The maxima of \sigma_1 a_1 + \sigma_2 a_2 over the patterns are 2, 0, 1 and 0.

   Their mean is 3/4, and dividing by n = 2 gives 0.375.

   With all four patterns, the maximum is (\sigma_1)_+ + (\sigma_2)_+, of mean 1, so \hat{\mathfrak{R}}_2 = 0.5. Massart’s lemma gives \sqrt{2}\, \sqrt{2 \log 3} / 2 = 1.05 for the thresholds: correct but vacuous, since the class has range 1.

10. ★★ Sauer’s lemma is tight. Show that on an infinite set, the class of indicators of the subsets with at most V elements has VC dimension V and growth function exactly \sum_{i \leq V} \binom{n}{i}.

    Solution: on n distinct points, the traces are the subsets of at most V of these points: there are \sum_{i \leq V} \binom{n}{i} of them. A set of V points is shattered, since all its subsets are allowed; a set of V + 1 points is not, since the full set is missing.

11. ★★ The perceptron loss is not calibrated. For \varphi(u) = \max(0, -u), compute C_\eta, H and H^-, and conclude. Then show that the squared hinge loss \max(0, 1 - u)^2 is calibrated and compute its \psi-transform.

    Solution: the conditional risk is piecewise linear, C_\eta(\alpha) = (1 - \eta)\, \alpha \ \text{ for } \alpha \geq 0, \qquad C_\eta(\alpha) = \eta\, |\alpha| \ \text{ for } \alpha \leq 0 .

    Its minimum is at \alpha = 0 for every \eta, so H = H^- = 0. The loss is not calibrated, in line with Theorem 6.3, since \varphi is not differentiable at 0.

    The constant f = 0 minimizes the risk, and the perceptron works only through its algorithm and separability.

    The squared hinge has \varphi'(0) = -2: calibrated. On [-1, 1] it coincides with the square loss, whose minimizer 2\eta - 1 lies there, so \psi(\theta) = \theta^2.

12. ★★ AdaBoost forgets its last choice. Show that under the new weights w_{t+1}, the base classifier h_t has weighted error exactly 1/2. What does this imply for h_{t+1}?

    Solution: the weight of the examples misclassified by h_t becomes \frac{\varepsilon_t\, e^{\alpha_t}}{Z_t} = \frac{\varepsilon_t \sqrt{(1 - \varepsilon_t)/\varepsilon_t}}{2\sqrt{\varepsilon_t (1 - \varepsilon_t)}} = \frac12 . So h_t is no better than chance under the new weights, and AdaBoost never selects the same classifier twice in a row.

13. ★★ AUC by hand. Three positives have scores 0.9, 0.7, 0.4 and three negatives 0.8, 0.3, 0.2. Compute the empirical AUC by counting pairs, by the rank formula, and as the area under the empirical ROC curve. Compute the empirical ranking risk L_n and relate it to the AUC.

    Solution: the score 0.9 beats the three negatives, 0.7 beats two and 0.4 beats two, so \widehat{\mathrm{AUC}} = 7/9 = 0.778.

    The positive ranks among the six scores are 6, 4 and 3, so the rank formula gives (13 - 6)/9 = 7/9. The ROC curve goes through (0, 1/3), (1/3, 1/3), (1/3, 1) and (1, 1), with area 1/9 + 2/3 = 7/9.

    Two unordered pairs are misordered, hence 4 of the 30 ordered pairs, and L_n = 0.133. The 18 ordered pairs with different labels make up 0.6 of all pairs, and 0.6 \times 2/9 = 0.133: the empirical analogue of Proposition 8.4.

14. ★★ Exponential weights, in Python. Simulate 50 experts with Bernoulli losses of means drawn in [0.3, 0.5] over T = 5000 rounds. Compare the regret of exponential weights with the bound of Theorem 7.8 and with the uniform average; then vary \eta.

    Hints and expected result:

    import numpy as np
    
    rng = np.random.default_rng(5)
    T, M = 5000, 50
    q = rng.uniform(0.3, 0.5, size=M)                  # mean loss of each expert
    L = (rng.uniform(size=(T, M)) < q).astype(float)   # losses in {0, 1}
    eta = np.sqrt(8 * np.log(M) / T)
    
    cum, total = np.zeros(M), 0.0
    for t in range(T):
        w = np.exp(-eta * (cum - cum.min()))           # shift for numerical stability
        total += (w / w.sum()) @ L[t]
        cum += L[t]
    print(f"exponential weights regret {total - cum.min():6.1f}")
    print(f"uniform average regret     {L.mean(axis=1).sum() - cum.min():6.1f}")
    print(f"bound sqrt(T log M / 2)    {np.sqrt(T * np.log(M) / 2):6.1f}")

    The regret is 72.9, below the bound 98.9, while the uniform average loses 487.4. A much smaller \eta behaves like the uniform average: 231.5 at a tenth of the tuned value.

    A much larger \eta approaches follow-the-leader, which does even better here: 58.1 at ten times the tuned value, 55.3 at a hundred times. With independent losses the leader rarely changes. The tuning of Theorem 7.8 is a worst-case choice: on losses that alternate between two experts, follow-the-leader errs at every round and its regret grows linearly in T.

15. ★★★ Fast rates under the margin condition. Let \mathcal{G} be finite and contain g^*, and assume the margin condition with exponent \alpha. Adapt the proof of Theorem 9.4 to show that, with probability at least 1 - \delta, R(\hat g_n) - R^* \leq C \Big(\frac{\log(N/\delta)}{n}\Big)^{(1+\alpha)/(2+\alpha)} , for a constant C depending on the margin constant and \alpha.

    Hints and expected result: by Proposition 9.2 the variance of the excess loss is at most c\, \Delta^\kappa, with \kappa = \alpha/(1 + \alpha). Bernstein’s inequality and the ERM property give \Delta \leq \sqrt{\frac{2 c\, \Delta^\kappa L}{n}} + \frac{4L}{3n} . If the first term dominates, \Delta^{1 - \kappa/2} \lesssim \sqrt{L/n}, so \Delta \lesssim (L/n)^{1/(2 - \kappa)}, and 1/(2 - \kappa) = (1 + \alpha)/(2 + \alpha).

    Otherwise \Delta \lesssim L/n, which is smaller. The exponent goes from 1/2 (\alpha = 0) to 1 (\alpha \to \infty).

16. ★★★ A lower bound with one point. The input is a single point, and \eta = \frac12 + \varepsilon under P_+, \eta = \frac12 - \varepsilon under P_-. Show that every rule has, under one of the two, an expected excess risk of at least \varepsilon\, \big(1 - \mathrm{TV}(P_+^n, P_-^n)\big) . Using Pinsker’s inequality, deduce a lower bound of order 1/\sqrt{n}.

    Hints and expected result: predicting the wrong label costs |2\eta - 1| = 2\varepsilon. The sum of the probabilities of a wrong prediction under the two laws is at least 1 - \mathrm{TV}, which gives the first claim.

    For \varepsilon \leq 1/4, the divergence between the two sample laws satisfies \mathrm{KL}(P_+^n \,\|\, P_-^n) = 2n\varepsilon \log\frac{1 + 2\varepsilon}{1 - 2\varepsilon} \leq 16 n \varepsilon^2 . With \varepsilon = 1/(8\sqrt{n}), it is at most 1/4, so \mathrm{TV} \leq \sqrt{1/8} = 0.354, and the excess risk is at least 0.08/\sqrt{n}. On V shattered points, the same argument gives the \sqrt{V/n} of Theorem 5.5.

17. ★★★ When a linear score cannot rank. On the concentric circles of scikit-learn, compare the AUC of a linear logistic score, of a random-forest score and of minus the radius. Relate the results to Theorem 8.3, then study the effect of the forest’s leaf size and of the training size.

    Hints and expected result:

    import numpy as np
    from sklearn.datasets import make_circles
    from sklearn.ensemble import RandomForestClassifier
    from sklearn.linear_model import LogisticRegression
    from sklearn.metrics import roc_auc_score
    
    X, y = make_circles(n_samples=4000, noise=0.2, factor=0.5, random_state=0)
    Xtr, ytr, Xte, yte = X[:1000], y[:1000], X[1000:], y[1000:]
    lin = LogisticRegression().fit(Xtr, ytr).decision_function(Xte)
    rf = RandomForestClassifier(n_estimators=300, min_samples_leaf=10, random_state=0)
    rf_s = rf.fit(Xtr, ytr).predict_proba(Xte)[:, 1]
    print("linear logistic score AUC:", round(roc_auc_score(yte, lin), 4))
    print("random forest score AUC  :", round(roc_auc_score(yte, rf_s), 4))
    print("minus the radius AUC     :", round(roc_auc_score(yte, -np.linalg.norm(Xte, axis=1)), 4))

    The AUCs are 0.492, 0.953 and 0.962. Here \eta is a decreasing function of the radius, so minus the radius is (nearly) an optimal score, while no linear score orders the points like \eta.

    The logistic population minimizer is optimal only within a model that contains an increasing transform of \eta. Studying how fast the forest’s AUC approaches the optimum, and comparing with a pairwise objective or TreeRank, is an open-ended project.

Projects and assessment

The official assessment, on master-mva.com, has two written parts: a partial exam (Part 1), which is mandatory, and a final exam (Part 2). A re-take, by written exam or by project, is proposed only to students who attended both parts. No weights are displayed. The Université Paris-Saclay course detail describes the assessment as “Evaluation Continue non Intégrale”.

The written exam below is a proposal in the spirit of both exams: Part 1 would cover ch. 0–4 and Part 2 the whole course. The solo subjects are sized for the re-take project or for personal study. The group subjects follow the MVA tradition of reproducing a research paper and presenting it orally.

Solo projects

1. [Solo · ≈ 20 h] Calibration and comparison inequalities, measured. How tight is the comparison inequality of Theorem 6.4 for actual learning rules? A paper study of Bartlett, Jordan and McAuliffe (2006), with Zhang (2004).
   • Implement: on a two-dimensional model with a known regression function (two Gaussian classes with unequal covariances), minimize the empirical hinge, logistic, exponential and square risks over linear and quadratic features, for n from 100 to 10 000.
   • Measure: the excess classification risk and the excess surrogate risk, both by Monte Carlo, using the known \eta and R_\varphi^* = \mathbb{E}\, H(\eta(X)).
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 1, 6.
   • Success criterion: the inequality holds on every run; the report plots both sides of it against n and explains when they are far apart.
2. [Solo · ≈ 20 h] Stone’s theorem, proved and tested. Write a complete proof of the universal consistency of the k-NN rule, then test its limits. A paper study of Stone (1977) and Cover and Hart (1967), following the proofs of Devroye, Györfi and Lugosi (1996).
   • Prove: the variance and bias steps of Theorem 3.5, Stone’s lemma with an explicit constant, and the limit of Proposition 3.6.
   • Test: the excess risk against n for k = 1, k = \sqrt{n} and a hold-out choice of k (Proposition 9.5), in dimensions 2, 10 and 50, on Gaussian classes with a known Bayes risk.
   • Deliverables: a 6–8 page note with the proof, code, 10-minute talk. Chapters: ch. 2, 3, 5, 9.
   • Success criterion: a proof without gaps, and a figure showing how the convergence slows down as the dimension grows.
3. [Solo · ≈ 20 h] How loose are generalization bounds? Compute the bounds of ch. 4, 6 and 7 for a linear SVM and for boosted stumps on real data, and compare them with test errors. A paper study of Bartlett and Mendelson (2002).
   • Data: the breast-cancer data set bundled with scikit-learn (569 points, 30 features, standardized on each training part), over 20 random train–test splits.
   • Compute: the VC bound (Corollary 4.12), the margin bound for linear classifiers (Theorem 4.10 with the ramp loss, Lemma 6.6 and Proposition 4.13) and the margin bound for boosting (Theorem 7.7), with empirical Rademacher complexities estimated by Monte Carlo.
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 4, 6, 7.
   • Success criterion: a table of bounds against test errors, the margin \gamma that minimizes each bound, and an explanation of which term makes a bound vacuous when it is.

Group projects

1. [Group of 2–3 · ≈ 30 h each] Boosting the margin, reproduced. Does the test error of AdaBoost keep falling after the training error reaches zero, and do margins explain it? A paper study of Schapire, Freund, Bartlett and Lee (1998), with the counterpoint of Breiman (1999).
   • Implement: AdaBoost with stumps and with depth-3 trees, written from scratch and checked against scikit-learn; the normalized margins Y_i F_T(X_i) / \sum_t \alpha_t at T = 5, 100 and 1000; Breiman’s arc-gv, which maximizes the minimum margin.
   • Data: the simulated data of make_hastie_10_2 in scikit-learn (Example 10.2 of Hastie, Tibshirani and Friedman, 2009) and the breast-cancer data set.
   • Split: member A writes the boosting code; B the margin distributions and the bound of Theorem 7.7; C, in a group of three, arc-gv and the comparison.
   • Deliverables: code, 8–10 page joint report, 20-minute talk. Chapters: ch. 6, 7.
   • Success criterion: the cumulative margin distributions of the 1998 paper, reproduced qualitatively, and Breiman’s observation that a larger minimum margin need not lower the test error.
2. [Group of 2–3 · ≈ 30 h each] Bipartite ranking: TreeRank against surrogate minimization. Which method gets closest to the optimal ROC curve: a logistic plug-in score, pairwise RankBoost, or TreeRank? A paper study of Clémençon and Vayatis (2009), with Clémençon, Lugosi and Vayatis (2008).
   • Data: synthetic models with a known \eta, hence a known optimal ROC curve (Theorem 8.3): Gaussian classes with unequal covariances, and the circles of Exercise 17.
   • Implement: TreeRank with cost-sensitive tree splits (Proposition 2.2); RankBoost on an incomplete U-statistic built from random pairs; logistic regression on polynomial features.
   • Split: member A writes TreeRank; B RankBoost and the incomplete U-statistics; C, in a group of three, the evaluation: ROC curves, the sup-distance to the optimal curve, and bootstrap intervals for the AUC.
   • Deliverables: code, 8–10 page joint report, 20-minute talk. Chapters: ch. 2, 7, 8.
   • Success criterion: each method’s AUC within 0.01 of the optimum at n = 5000, or an explanation of why it cannot get there.
3. [Group of 2 · ≈ 25 h each] Structural risk minimization against cross-validation. Do the penalties of ch. 5 select a classifier as well as cross-validation does? A paper study of Koltchinskii (2001), with the survey of Arlot and Celisse (2010).
   • Model: histogram classifiers on regular grids of m \times m cells in [0, 1]^2, for m = 1, \dots, 30, on synthetic data with a known \eta of varying smoothness.
   • Split: member A computes the VC penalty of Proposition 5.8 and the Rademacher penalty; member B implements hold-out and V-fold selection, and the oracle choice computed from the true risk.
   • Deliverables: code, 8-page joint report, 20-minute talk. Chapters: ch. 2, 4, 5, 9.
   • Success criterion: the ratio of the excess risk of each selected classifier to that of the oracle, reported over 50 samples for n from 200 to 20 000, and the oracle inequality of Proposition 5.8 checked on every sample.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, no calculator needed beyond logarithms and square roots; four independent questions. This format is a proposal: the official pages do not describe it.

1. Question (5 points). Let \eta(x) = \mathbb{P}(Y = 1 \mid X = x) in binary classification with labels \pm 1. Define the Bayes classifier g^* and prove that every classifier g satisfies R(g) - R^* = \mathbb{E}\big[\,|2\eta(X) - 1|\; \mathbb{1}\{g(X) \neq g^*(X)\}\big] . Deduce that a plug-in classifier built from \hat\eta has excess risk at most 2\, \mathbb{E}|\hat\eta(X) - \eta(X)|.

   Expected: the conditional error of g at x, compared with that of g^* (Theorem 1.3); then the observation that \eta and \hat\eta lie on different sides of 1/2 wherever the classifiers disagree (Proposition 2.4).

2. Question (6 points). Let \mathcal{G} be the indicators of intervals [a, b] on the real line. (a) Compute its growth function and its VC dimension. (b) Bound the excess risk of the ERM with Corollary 4.12 for n = 10\,000 and \delta = 0.05. (c) Restrict the endpoints to the grid \{k/100\} and apply Proposition 4.1 instead. Comment.

   Expected: (a) S(n) = n(n+1)/2 + 1 and V = 2 (Example 4.4). (b) 0.123 + 0.027 = 0.151. (c) The class has 5151 + 1 = 5152 classifiers, so the bound is \sqrt{2 \log(2N/\delta)/n} = 0.049. The finite bound is three times smaller, but it ignores the approximation error that the grid adds.

3. Question (5 points). Let \varphi be convex, differentiable at 0, with \varphi'(0) < 0. Prove that \varphi is classification-calibrated. For the hinge loss, compute H and the \psi-transform, and deduce a bound on the excess classification risk of \mathrm{sign}\, f.

   Expected: the proof of Theorem 6.3 (tangent at 0 below C_\eta, so H^- = \varphi(0) > H). For the hinge loss, H(\eta) = 1 - |2\eta - 1| and \psi(\theta) = \theta (Example 6.5). By Theorem 6.4, the excess classification risk is at most the excess hinge risk.

4. Question (4 points). Prove that the training error of AdaBoost after T rounds is at most \prod_t 2\sqrt{\varepsilon_t(1 - \varepsilon_t)}. If every weighted error is at most 0.4 and n = 1000, after how many rounds is the training error guaranteed to be zero?

   Expected: the three steps of Theorem 7.4. With \gamma = 0.1, the training error is a multiple of 1/n, so it is zero once the bound is below 10^{-3}.

   The bound e^{-2\gamma^2 T} gives T \geq 346; the exact product 0.96^{T/2} gives T \geq 339.

Total: 5 + 6 + 5 + 4 = 20 points.

Grading rubric (proposal)

References

Official references (master-mva.com, 2026–2027)

• M. Mohri, A. Rostamizadeh, A. Talwalkar, Foundations of Machine Learning, MIT Press, 2012 (2nd ed. 2018).
• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014.
• The course web page linked from master-mva.com: http://nvayatis.perso.math.cnrs.fr/ISLcourse.html.

Textbooks and surveys

• L. Devroye, L. Györfi, G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996 — ch. 1–5, 9.
• V. N. Vapnik, Statistical Learning Theory, Wiley, 1998 — ch. 4–5.
• T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, 2nd ed., Springer, 2009 — ch. 3, 7.
• S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013 — ch. 0, 4, 9.
• O. Bousquet, S. Boucheron, G. Lugosi, “Introduction to statistical learning theory”, in Advanced Lectures on Machine Learning, Lecture Notes in Artificial Intelligence 3176, Springer, 169–207, 2004.
• S. Boucheron, O. Bousquet, G. Lugosi, “Theory of classification: a survey of some recent advances”, ESAIM: Probability and Statistics 9, 323–375, 2005.
• M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 1999 — ch. 4–5.
• M. Ledoux, M. Talagrand, Probability in Banach Spaces, Springer, 1991 — contraction (ch. 6).
• I. Steinwart, A. Christmann, Support Vector Machines, Springer, 2008 — ch. 6.
• L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone, Classification and Regression Trees, Wadsworth, 1984 — ch. 3.
• R. E. Schapire, Y. Freund, Boosting: Foundations and Algorithms, MIT Press, 2012 — ch. 7.
• N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006 — ch. 7.
• A. B. Tsybakov, Introduction to Nonparametric Estimation, Springer, 2009 — ch. 5, 9.

Concentration, complexity and learnability (ch. 0, 4, 5)

• W. Hoeffding, “Probability inequalities for sums of bounded random variables”, Journal of the American Statistical Association 58(301), 13–30, 1963.
• C. McDiarmid, “On the method of bounded differences”, in Surveys in Combinatorics 1989, London Mathematical Society Lecture Note Series 141, Cambridge University Press, 148–188, 1989.
• V. N. Vapnik, A. Ya. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities”, Theory of Probability and Its Applications 16(2), 264–280, 1971.
• N. Sauer, “On the density of families of sets”, Journal of Combinatorial Theory, Series A 13(1), 145–147, 1972.
• S. Shelah, “A combinatorial problem; stability and order for models and theories in infinitary languages”, Pacific Journal of Mathematics 41(1), 247–261, 1972.
• P. Massart, “Some applications of concentration inequalities to statistics”, Annales de la Faculté des Sciences de Toulouse 9(2), 245–303, 2000.
• P. L. Bartlett, S. Mendelson, “Rademacher and Gaussian complexities: risk bounds and structural results”, Journal of Machine Learning Research 3, 463–482, 2002.
• V. Koltchinskii, “Rademacher penalties and structural risk minimization”, IEEE Transactions on Information Theory 47(5), 1902–1914, 2001.
• L. G. Valiant, “A theory of the learnable”, Communications of the ACM 27(11), 1134–1142, 1984.
• D. Haussler, “Decision theoretic generalizations of the PAC model for neural net and other learning applications”, Information and Computation 100(1), 78–150, 1992.
• A. Blumer, A. Ehrenfeucht, D. Haussler, M. K. Warmuth, “Learnability and the Vapnik–Chervonenkis dimension”, Journal of the ACM 36(4), 929–965, 1989.
• A. Ehrenfeucht, D. Haussler, M. Kearns, L. Valiant, “A general lower bound on the number of examples needed for learning”, Information and Computation 82(3), 247–261, 1989.
• L. Devroye, “Any discrimination rule can have an arbitrarily bad probability of error for finite sample size”, IEEE Transactions on Pattern Analysis and Machine Intelligence 4(2), 154–157, 1982.

Classical algorithms (ch. 3)

• F. Rosenblatt, “The perceptron: a probabilistic model for information storage and organization in the brain”, Psychological Review 65(6), 386–408, 1958.
• A. B. J. Novikoff, “On convergence proofs on perceptrons”, in Proceedings of the Symposium on the Mathematical Theory of Automata, vol. 12, Polytechnic Institute of Brooklyn, 615–622, 1962.
• T. M. Cover, P. E. Hart, “Nearest neighbor pattern classification”, IEEE Transactions on Information Theory 13(1), 21–27, 1967.
• C. J. Stone, “Consistent nonparametric regression”, Annals of Statistics 5(4), 595–620, 1977.
• C. Cortes, V. Vapnik, “Support-vector networks”, Machine Learning 20(3), 273–297, 1995.

Convex surrogates (ch. 6)

• T. Zhang, “Statistical behavior and consistency of classification methods based on convex risk minimization”, Annals of Statistics 32(1), 56–85, 2004.
• P. L. Bartlett, M. I. Jordan, J. D. McAuliffe, “Convexity, classification, and risk bounds”, Journal of the American Statistical Association 101(473), 138–156, 2006.
• G. Lugosi, N. Vayatis, “On the Bayes-risk consistency of regularized boosting methods”, Annals of Statistics 32(1), 30–55, 2004.
• I. Steinwart, “Consistency of support vector machines and other regularized kernel classifiers”, IEEE Transactions on Information Theory 51(1), 128–142, 2005.
• S. Ben-David, N. Eiron, P. M. Long, “On the difficulty of approximately maximizing agreements”, Journal of Computer and System Sciences 66(3), 496–514, 2003.

Aggregation and ensembles (ch. 7)

• L. Breiman, “Bagging predictors”, Machine Learning 24(2), 123–140, 1996.
• L. Breiman, “Random forests”, Machine Learning 45(1), 5–32, 2001.
• Y. Freund, R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting”, Journal of Computer and System Sciences 55(1), 119–139, 1997.
• R. E. Schapire, Y. Freund, P. Bartlett, W. S. Lee, “Boosting the margin: a new explanation for the effectiveness of voting methods”, Annals of Statistics 26(5), 1651–1686, 1998.
• L. Breiman, “Prediction games and arcing algorithms”, Neural Computation 11(7), 1493–1517, 1999.
• J. Friedman, T. Hastie, R. Tibshirani, “Additive logistic regression: a statistical view of boosting”, Annals of Statistics 28(2), 337–407, 2000.
• J. H. Friedman, “Greedy function approximation: a gradient boosting machine”, Annals of Statistics 29(5), 1189–1232, 2001.
• V. Koltchinskii, D. Panchenko, “Empirical margin distributions and bounding the generalization error of combined classifiers”, Annals of Statistics 30(1), 1–50, 2002.
• D. H. Wolpert, “Stacked generalization”, Neural Networks 5(2), 241–259, 1992.
• N. Cesa-Bianchi, A. Conconi, C. Gentile, “On the generalization ability of on-line learning algorithms”, IEEE Transactions on Information Theory 50(9), 2050–2057, 2004.
• A. Juditsky, P. Rigollet, A. B. Tsybakov, “Learning by mirror averaging”, Annals of Statistics 36(5), 2183–2206, 2008.

Scoring and ranking (ch. 8)

• J. Neyman, E. S. Pearson, “On the problem of the most efficient tests of statistical hypotheses”, Philosophical Transactions of the Royal Society A 231, 289–337, 1933.
• W. Hoeffding, “A class of statistics with asymptotically normal distribution”, Annals of Mathematical Statistics 19(3), 293–325, 1948.
• J. A. Hanley, B. J. McNeil, “The meaning and use of the area under a receiver operating characteristic (ROC) curve”, Radiology 143(1), 29–36, 1982.
• T. Fawcett, “An introduction to ROC analysis”, Pattern Recognition Letters 27(8), 861–874, 2006.
• Y. Freund, R. Iyer, R. E. Schapire, Y. Singer, “An efficient boosting algorithm for combining preferences”, Journal of Machine Learning Research 4, 933–969, 2003.
• S. Clémençon, N. Vayatis, “Ranking the best instances”, Journal of Machine Learning Research 8, 2671–2699, 2007.
• S. Clémençon, G. Lugosi, N. Vayatis, “Ranking and empirical minimization of U-statistics”, Annals of Statistics 36(2), 844–874, 2008.
• S. Clémençon, N. Vayatis, “Tree-based ranking methods”, IEEE Transactions on Information Theory 55(9), 4316–4336, 2009.
• S. Clémençon, I. Colin, A. Bellet, “Scaling-up empirical risk minimization: optimization of incomplete U-statistics”, Journal of Machine Learning Research 17(76), 1–36, 2016.

Fast rates, model selection and stability (ch. 9)

• E. Mammen, A. B. Tsybakov, “Smooth discrimination analysis”, Annals of Statistics 27(6), 1808–1829, 1999.
• A. B. Tsybakov, “Optimal aggregation of classifiers in statistical learning”, Annals of Statistics 32(1), 135–166, 2004.
• P. Massart, É. Nédélec, “Risk bounds for statistical learning”, Annals of Statistics 34(5), 2326–2366, 2006.
• P. L. Bartlett, O. Bousquet, S. Mendelson, “Local Rademacher complexities”, Annals of Statistics 33(4), 1497–1537, 2005.
• S. Arlot, A. Celisse, “A survey of cross-validation procedures for model selection”, Statistics Surveys 4, 40–79, 2010.
• O. Bousquet, A. Elisseeff, “Stability and generalization”, Journal of Machine Learning Research 2, 499–526, 2002.
• M. Hardt, B. Recht, Y. Singer, “Train faster, generalize better: stability of stochastic gradient descent”, in Proceedings of the 33rd International Conference on Machine Learning, PMLR 48, 1225–1234, 2016.

Research directions (ch. 10)

• C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, “Understanding deep learning requires rethinking generalization”, International Conference on Learning Representations, 2017.
• V. Nagarajan, J. Z. Kolter, “Uniform convergence may be unable to explain generalization in deep learning”, Advances in Neural Information Processing Systems 32, 2019.
• 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.
• 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.
• 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.
• K. Lyu, J. Li, “Gradient descent maximizes the margin of homogeneous neural networks”, International Conference on Learning Representations, 2020.
• D. A. McAllester, “PAC-Bayesian model averaging”, in Proceedings of the 12th Annual Conference on Computational Learning Theory, ACM, 164–170, 1999.
• O. Catoni, PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, IMS Lecture Notes Monograph Series 56, 2007.
• G. K. Dziugaite, D. M. Roy, “Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data”, in Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, 2017.
• P. Alquier, “User-friendly introduction to PAC-Bayes bounds”, Foundations and Trends in Machine Learning 17(2), 174–303, 2024.
• V. Vovk, A. Gammerman, G. Shafer, Algorithmic Learning in a Random World, Springer, 2005.
• J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, L. Wasserman, “Distribution-free predictive inference for regression”, Journal of the American Statistical Association 113(523), 1094–1111, 2018.
• A. N. Angelopoulos, S. Bates, “Conformal prediction: a gentle introduction”, Foundations and Trends in Machine Learning 16(4), 494–591, 2023.
• S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, J. W. Vaughan, “A theory of learning from different domains”, Machine Learning 79(1–2), 151–175, 2010.
• M. Hardt, E. Price, N. Srebro, “Equality of opportunity in supervised learning”, Advances in Neural Information Processing Systems 29, 2016.
• G. Biau, L. Devroye, G. Lugosi, “Consistency of random forests and other averaging classifiers”, Journal of Machine Learning Research 9, 2015–2033, 2008.
• E. Scornet, G. Biau, J.-P. Vert, “Consistency of random forests”, Annals of Statistics 43(4), 1716–1741, 2015.
• S. Wager, S. Athey, “Estimation and inference of heterogeneous treatment effects using random forests”, Journal of the American Statistical Association 113(523), 1228–1242, 2018.