Introduction to
Machine Learning

We observe $n$ independent and identically distributed (i.i.d.) pairs $(X_1,Y_1),\dots,(X_n,Y_n)$ drawn from a joint distribution $P_{X,Y}$ on $\mathcal{X}\times\{0,1\}$. The variable $X$ is called the feature vector, and $Y$ is called the label. Our goal is to construct a function $h:\mathcal{X}\to\{0,1\}$ — called a classifier — that predicts $Y$ from $X$ on new, unseen instances.

• $\mathcal{X}$instance (feature) space; any abstract set.
• $Y$binary label; $Y\in\{0,1\}$.
• $X$feature vector; takes values in $\mathcal{X}$.
• $P_{X,Y}$joint distribution of $(X,Y)$ on $\mathcal{X}\times\{0,1\}$.
• $n$sample size; number of i.i.d. observations.
• $h$classifier; a measurable function $\mathcal{X}\to\{0,1\}$.

In the supervised learning paradigm, a learner receives a training set of labeled examples and must output a prediction rule that generalises to unseen data. The protocol is defined by the following ingredients.

• $S = \{(x_i,y_i)\}_{i=1}^n$training sample; i.i.d. draws from $P_{X,Y}$.
• $\mathcal{H}$hypothesis class; a set of functions $h:\mathcal{X}\to\mathcal{Y}$.
• $\ell$loss function; measures the penalty $\ell(y',y)$ when $y'$ is predicted and $y$ is true.
• $\mathcal{A}$learning algorithm; a mapping $(\mathcal{X}\times\mathcal{Y})^n \to \mathcal{H}$ that selects a hypothesis based on the training data.
• $h_S$output hypothesis; $h_S = \mathcal{A}(S)$, used for future predictions.

This protocol encompasses binary classification when $\mathcal{Y}=\{0,1\}$ and $\ell$ is the 0‑1 loss, but it applies to any supervised learning task (regression, multi‑class classification, etc.).

The learning problem is completely specified by three fundamental objects.

• $\mathcal{X}$input (feature) space; e.g. $\mathbb{R}^d$, text documents, images.
• $\mathcal{Y}$label (output) space; for binary classification $\mathcal{Y}=\{0,1\}$.
• $P_{X,Y}$data generating distribution; a probability measure on $\mathcal{X}\times\mathcal{Y}$ that governs the random generation of feature‑label pairs. It can be factorised as $P_{X,Y} = P_X \cdot P_{Y\mid X}$, where $P_X$ is the marginal distribution of $X$ and $P_{Y\mid X}$ is the conditional distribution of $Y$ given $X$.

All data points $(X_i,Y_i)$ are assumed to be i.i.d. according to $P_{X,Y}$. The distribution $P_{X,Y}$ is unknown to the learner; only the training sample is observed.

The regression function (or posterior probability function) is the conditional expectation of the label given the features:

• $\eta(x)$probability that $Y=1$ when $X=x$; summarises all predictive information contained in the distribution $P_{X,Y}$.
• Bayes classifierthe optimal rule $h^*(x) = \mathbf{1}_{\{\eta(x) \ge 1/2\}}$; it minimises the 0‑1 risk.

Knowing $\eta$ is equivalent to knowing the data generating process for the purpose of prediction; hence many learning algorithms aim to estimate $\eta$ (or its sign) from data.

The quality of a classifier $h$ is measured by its true risk (or expected loss) under the 0‑1 loss:

• $R(h)$probability of misclassification on a fresh draw from $P_{X,Y}$.
• Bayes risk$R^* = \inf_h R(h) = R(h^*)$; the minimal achievable error, attained by the Bayes classifier.

Because $P_{X,Y}$ is unknown, $R(h)$ cannot be computed directly. The learner instead minimises an empirical risk on the training data, and we study the gap $R(h_S)-R^*$.

For a fixed input $x$, the conditional risk (or pointwise error) of a classifier $h$ is the probability of mistake given $X=x$:

Using the regression function $\eta(x)=P(Y=1\mid X=x)$, the conditional risk can be expressed explicitly:

• $R(h \mid x)$pointwise error at $x$; averaging over $X$ yields the true risk: $R(h) = \mathbb{E}_X[R(h \mid X)]$.
• pointwise Bayes rulethe decision $h^*(x)$ that minimises $R(h\mid x)$ is $h^*(x)=\mathbf{1}_{\{\eta(x)\ge 1/2\}}$.

This decomposition is central to the analysis of classification: it separates the difficulty of the problem at each point (through $\eta(x)$) from the global performance.

Using the regression function \(\eta(x)=\mathbb{P}(Y=1\mid X=x)\) from A4.4, the Bayes classifier is the decision rule that minimises the pointwise conditional risk (A4.6).

• \(h^*\)the Bayes classifier; a measurable function \(\mathcal{X}\to\{0,1\}\) that predicts the more probable label at each point.
• decision boundarythe set \(\{x:\eta(x)=1/2\}\) where ties can be broken arbitrarily; the risk does not depend on the tie‑breaking choice.

The Bayes risk is the minimum possible true risk (classification error) that any classifier can achieve. By definition,

• \(R^*\)the irreducible error inherent in the data generating distribution \(P_{X,Y}\). It is zero only when the labels are noiseless (realizable case).
• connection with \(\eta\)\(R^* = \mathbb{E}_X\!\big[\min(\eta(X),\,1-\eta(X))\big]\). This follows from the pointwise optimality of \(h^*\).

The excess risk (or regret) of a classifier \(h\) quantifies how much worse it performs compared to the optimal Bayes classifier:

Excess risk is always non‑negative, and \(E(h)=0\) exactly when \(h\) achieves the Bayes risk. It is the key quantity that learning theory bounds—we want \(E(\hat h)\) to be small with high probability after seeing a finite sample.

Proof (step‑by‑step).

1. Conditional risk expression. From A4.6, for a fixed \(x\), \(R(h\mid x) = \eta(x)\mathbf{1}_{h(x)=0} + (1-\eta(x))\mathbf{1}_{h(x)=1}\).
2. Pointwise optimality of \(h^*\). The Bayes classifier \(h^*(x)\) chooses the class with the smaller conditional error, so \(R(h^*\mid x) = \min(\eta(x),1-\eta(x))\).
3. Pointwise excess. For any \(h\), the pointwise excess risk is $$R(h\mid x)-R(h^*\mid x) = \begin{cases} (1-\eta(x))-\eta(x) = 1-2\eta(x), & \text{if } h(x)=1,\;h^*(x)=0,\\ \eta(x)-(1-\eta(x)) = 2\eta(x)-1, & \text{if } h(x)=0,\;h^*(x)=1,\\ 0, & \text{if } h(x)=h^*(x). \end{cases}$$
4. Unified form. This equals \(|2\eta(x)-1|\cdot \mathbf{1}_{h(x)\neq h^*(x)}\), because when \(h\) disagrees with \(h^*\), the difference is \(|2\eta(x)-1|\), and it is zero otherwise.
5. Integrate over \(X\). Taking expectation with respect to the marginal \(P_X\) yields the claimed identity.

Corollary 1 (Optimality of \(h^*\)). For every classifier \(h\), \(R(h) \ge R^*\). Equality holds if and only if \(h(x)=h^*(x)\) almost surely on the set where \(\eta(x)\neq 1/2\).

Corollary 2 (Noise‑weighted disagreement). The excess risk measures the disagreement between \(h\) and \(h^*\), weighted by \(|2\eta(x)-1|\)—points near the decision boundary (\(\eta(x)\approx 1/2\)) contribute less than points where one label is strongly favoured.

Corollary 3 (Excess risk as an integral). \(E(h) = \int_{\{h\neq h^*\}} |2\eta(x)-1|\,dP_X(x)\). The integral is over the region where the two classifiers disagree, and the weight \(|2\eta(x)-1|\) is the confidence margin.

The identity shows that the penalty for a wrong decision is proportional to the “confidence” of the label at that feature vector. If \(\eta(x)\) is close to \(1/2\) (high uncertainty), a mistake costs little. If \(\eta(x)\) is near \(0\) or \(1\) (high certainty), a mistake is heavily penalised.

This has a direct consequence for estimation: a learning algorithm does not need to perfectly replicate \(h^*\) everywhere; it can afford errors near the boundary where the signal is weak. The excess risk will be driven by the probability mass of the region where \(h\) disagrees with \(h^*\) and \(\eta\) is far from \(1/2\).

For a fixed classifier \(h\), define the comparison variable for a random draw \((X,Y)\):

• \(Z_h\)difference of 0‑1 losses; takes values in \(\{-1,0,1\}\).
• Expectation\(\mathbb{E}[Z_h] = R(h) - R^* = E(h)\), the excess risk.

This variable appears repeatedly in the analysis of empirical risk minimisation. Because \(\mathbb{E}[Z_h] = E(h)\), any bound on the average of i.i.d. copies of \(Z_h\) directly controls the excess risk of the empirically chosen classifier.

Given a training sample \(S = ((x_1,y_1),\dots,(x_n,y_n))\) drawn i.i.d. from \(P_{X,Y}\), the empirical risk (or training error) of a classifier \(h\) is

It is an unbiased estimator of the true risk \(R(h)\) (see A4.14) and the quantity that a learner can compute directly from the data. All learning algorithms that do not receive extra information must rely on \(\widehat{R}_n\) (or a surrogate loss) to select a hypothesis.

Proof. By linearity of expectation, \(\mathbb{E}[\widehat{R}_n(h)] = \frac{1}{n}\sum_{i=1}^n \mathbb{E}[\mathbf{1}_{h(x_i)\neq y_i}]\). Because each \((x_i,y_i)\) is drawn i.i.d. from \(P_{X,Y}\), each term equals \(\mathbb{P}(h(X)\neq Y) = R(h)\).

This unbiasedness is simple but crucial: it justifies using the empirical risk as a proxy for the true risk when the classifier is fixed in advance. However, after selecting \(h\) based on the same data (ERM), the empirical risk becomes a biased (optimistically) estimate of the true risk—leading to overfitting.

Given a hypothesis class \(\mathcal{H}\), the empirical risk minimizer (ERM) over \(\mathcal{H}\) is any classifier that minimises the training error:

When multiple hypotheses attain the minimum, any tie‑breaking rule is allowed. The ERM principle is the most basic learning strategy: pick the hypothesis that fits the observed data best, subject to the constraints of \(\mathcal{H}\). The whole of statistical learning theory is, in essence, the study of when and how well ERM works.

Consider the learner that chooses \(\mathcal{H} = \{\text{all functions } \mathcal{X}\to\{0,1\}\}\), i.e., no restriction at all. Then the ERM solution simply memorises the training labels:

This classifier has \(\widehat{R}_n(\widehat{h}_{\text{mem}}) = 0\), yet its true risk can be close to \(1/2\) on typical distributions. The learner has overfit—it fitted the noise and idiosyncrasies of the training sample rather than the underlying pattern.

Real‑world analogy. A chess amateur who memorises a few grandmaster games can perfectly replay them, but will lose against any new opponent who deviates from the memorised lines. Without understanding the principles, memorisation does not generalise.

To avoid overfitting, we must restrict the hypothesis class \(\mathcal{H}\) before seeing the data. This restriction is the inductive bias. The next sections quantify the sample size needed for ERM over a finite \(\mathcal{H}\) to avoid overfitting with high confidence.

Machine learning tasks are categorised along several independent axes. The most common distinctions are:

By Supervision Type

• Supervised LearningTraining data consist of input‑output pairs \((x_i,y_i)\). The goal is to learn a mapping that generalises to unseen inputs. Binary classification (A4.1) is the prime example.
• Unsupervised LearningOnly inputs \(x_i\) are observed; no labels. The aim is to discover structure such as clusters, densities, or low‑dimensional representations. Example: grouping customers by purchasing behaviour.
• Semi‑supervised LearningA small labelled set is combined with a large unlabelled set. The unlabelled data helps to learn the geometry of the feature space. Example: using millions of unlabelled images to improve a face detector trained on a few hundred labelled faces.
• Reinforcement LearningAn agent interacts with an environment, receiving rewards or penalties. It learns a policy (a mapping from states to actions) that maximises cumulative reward, without explicit correct outputs. Example: a robot learning to walk by trial and error.

By Data Arrival Mode

• Batch LearningThe learner receives the entire training set at once and may process it arbitrarily before outputting a predictor. All analysis in A4.1–A4.16 assumes this setting.
• Online LearningInstances arrive sequentially. At each step the learner makes a prediction, then the true label is revealed. Performance is measured by the cumulative loss over time (regret). The learner must adapt continuously without revisiting past data.

By Learner’s Agency

• Passive LearnerThe learner only observes the data that comes naturally; it cannot influence which examples are labelled or when they appear. The i.i.d. supervised setting is passive.
• Active LearnerThe learner can query an oracle (e.g., ask for the label of a specific \(x\)). The goal is to achieve high accuracy with fewer labelled examples by selecting the most informative queries.

By the Nature of the Data Source (Teacher)

• CooperativeThe data provider (teacher) selects examples specifically to help the learner, like a human tutor giving instructive exercises.
• IndifferentData are generated by a process with no intention to teach or mislead—most statistical learning theory assumes this neutral setting.
• AdversarialAn opponent deliberately crafts examples to fool the learner, as in spam filtering or intrusion detection. Online learning often models this with an adversary that may even adapt to the learner’s predictions.

The excess risk, Bayes classifier, and ERM analysis developed in A4.7–A4.16 belong to the supervised, batch, indifferent, passive paradigm—the cleanest theoretical foundation. Extensions to the other paradigms build on these core principles.

Inductive bias is the set of assumptions that a learning algorithm uses to choose a predictor from data. Without such bias, learning is impossible—every prediction on unseen instances is a blind guess. Formally, the inductive bias is captured by a hypothesis class \(\mathcal{H}\), a restricted set of functions from \(\mathcal{X}\) to \(\mathcal{Y}\) that the learner is allowed to consider.

• \(\mathcal{H} \subseteq \mathcal{Y}^{\mathcal{X}}\)the learner’s “language” of predictors; embodies prior knowledge about plausible patterns.
• Choosing \(\mathcal{H}\)commits the learner before seeing the data, just as a scientist selects a model class before performing an experiment. Data‑dependent changes to \(\mathcal{H}\) would amount to data snooping and invalidate theoretical guarantees.

Every guarantee in statistical learning theory is conditional on the choice of \(\mathcal{H}\). The size and structure of \(\mathcal{H}\) control the tradeoff between flexibility and generalisation.

Within a fixed hypothesis class \(\mathcal{H}\), the best possible predictor is the oracle (or best‑in‑class):

The approximation error measures how well \(\mathcal{H}\) can capture the true relationship:

• \(h^*_{\mathcal{H}}\)the hypothesis in \(\mathcal{H}\) with smallest true risk; the target we strive to compete with.
• \(\varepsilon_{\text{app}}\)non‑negative; equals zero if and only if the Bayes classifier \(h^*\) belongs to \(\mathcal{H}\).

If \(\mathcal{H}\) is too small, the approximation error is large—we suffer underfitting. The learner can never outperform the oracle \(h^*_{\mathcal{H}}\), no matter how much data it receives.

The estimation error measures how much worse \(\hat h\) is than the oracle \(h^*_{\mathcal{H}}\) due to the finite sample. A successful learning result shows that with high probability, \(R(\hat h) - R(h^*_{\mathcal{H}}) \le \varepsilon_{\text{est}}(n,\mathcal{H},\delta)\), where \(\varepsilon_{\text{est}}\to 0\) as \(n\to\infty\).

Total excess risk is thus bounded by \(\varepsilon_{\text{est}} + \varepsilon_{\text{app}}\). This decomposes the learning problem: approximation error depends on the expressiveness of \(\mathcal{H}\); estimation error depends on its complexity.

The realizability assumption (or noiseless case) states that the true labeling function belongs to the hypothesis class:

Under realizability, the oracle \(h^*_{\mathcal{H}}\) coincides with the Bayes classifier, and the empirical risk of the true function is zero on every sample. ERM then selects a hypothesis with zero training error. This simplification allows us to prove the cleanest sample complexity bounds and reveals the purest form of the estimation error. Realizability is, however, a strong assumption, rarely satisfied in practice; it serves as a pedagogical stepping stone toward the agnostic setting.

The theorem states that, without restricting \(\mathcal{H}\) (or equivalently, without inductive bias), every learner can be forced to fail on some distribution. Even with a large sample, the worst‑case expected error can be close to \(1/2\). Learning is impossible in the distribution‑free sense unless we confine the learner to a class \(\mathcal{H}\) with limited capacity. The proof uses a symmetrisation argument: the learner cannot distinguish between a distribution and its flipped version.

A stronger consequence of the no‑free‑lunch principle is that for any learning algorithm, there are problems where the convergence of the excess risk is arbitrarily slow. Formally, given any sequence of positive numbers \(a_n \to 0\), there exists a distribution such that

This means that no algorithm can guarantee a uniform rate of convergence over all distributions. To obtain finite‑sample guarantees with a specific rate (e.g., \(O(1/\sqrt{n})\)), we must impose structure through the hypothesis class \(\mathcal{H}\) and, often, additional assumptions on the distribution (e.g., margin, smoothness of \(\eta\)). The no‑free‑lunch theorems motivate the entire PAC learning framework: we accept that we cannot learn everything, and instead aim for guarantees that hold only when the data‑generating process is compatible with our inductive bias.

A hypothesis class \(\mathcal{H}\) is PAC learnable in the realizable setting if there exists an algorithm \(\mathcal{A}\) and a function \(m_{\mathcal{H}}(\epsilon,\delta)\) such that for any distribution \(\mathcal{D}\) over \(\mathcal{X}\) and any target function \(f\in\mathcal{H}\), when given a sample of size \(m \ge m_{\mathcal{H}}(\epsilon,\delta)\) drawn i.i.d. from \(\mathcal{D}\) and labeled by \(f\), the algorithm outputs a hypothesis \(\hat h\in\mathcal{H}\) satisfying

The smallest such \(m_{\mathcal{H}}\) is the sample complexity. For finite \(\mathcal{H}\), the bound \(m \ge \frac{\log|\mathcal{H}| + \log(1/\delta)}{\epsilon}\) (see A4.12) shows that finite classes are PAC learnable. The ERM learner witnesses the learnability. The definition extends to infinite classes via the VC dimension.

When the realizability assumption is dropped, we enter the agnostic PAC setting. A hypothesis class \(\mathcal{H}\) is agnostically PAC learnable if there exists an algorithm \(\mathcal{A}\) and a function \(m_{\mathcal{H}}(\epsilon,\delta)\) such that for any distribution \(P_{X,Y}\) over \(\mathcal{X}\times\{0,1\}\), with a sample of size \(m \ge m_{\mathcal{H}}(\epsilon,\delta)\),

Here the learner competes against the oracle \(h^*_{\mathcal{H}}\), the best predictor in \(\mathcal{H}\). The excess error is measured relative to the minimum achievable risk within the class. The sample complexity in the agnostic case typically grows as \(O(\frac{d + \log(1/\delta)}{\epsilon^2})\), where \(d\) is the VC dimension of \(\mathcal{H}\). The agnostic model is the standard framework for most practical learning problems.

The oracle inequality (A4.19) reveals a fundamental tension:

• Bias (approximation error)Decreases as \(\mathcal{H}\) becomes larger. A richer class can better approximate the Bayes classifier, potentially achieving \(\varepsilon_{\text{app}}\approx 0\).
• Complexity (estimation error)Increases with the capacity of \(\mathcal{H}\). A larger class makes it easier to overfit, requiring more samples to pin down the best hypothesis.

This is the bias–complexity tradeoff. The art of machine learning is to choose a hypothesis class that balances these two components. In practice, this is achieved via model selection, regularisation, or structural risk minimisation. The tradeoff also explains phenomena like the U‑shaped risk curve: test error first decreases as model complexity grows (reducing bias), then increases again (increasing estimation error).

The no‑free‑lunch theorems show that learning without assumptions is impossible. Different modelling philosophies impose different kinds of assumptions:

• Generative ModelsAssume a parametric or non‑parametric model for the joint distribution \(P_{X,Y}\). The learner estimates \(P_X\) and \(P_{Y\mid X}\) (or directly \(P_{X\mid Y}\) and \(P_Y\)). Because generative models make strong distributional assumptions, they can be highly sample‑efficient when the model is correct, but suffer from model misspecification. Example: Linear Discriminant Analysis assumes class‑conditional Gaussians with shared covariance.
• Discriminative ModelsDirectly model the decision boundary or the regression function \(\eta(x)\) without attempting to describe \(P_X\). They make weaker assumptions about the data distribution, usually only about the functional form of the predictor (e.g., linear classifier). This often yields better generalisation when the distributional assumptions are questionable, at the cost of potentially higher sample complexity for the same problem. Example: logistic regression, support vector machines.

The choice between generative and discriminative modelling is a concrete instance of the bias–complexity tradeoff. A generative model embodies a stronger inductive bias (specifying the full distribution), which can be beneficial if the bias is correct, or lead to large approximation error if it is wrong. A discriminative model imposes a weaker bias, often requiring more data to achieve the same accuracy, but is less sensitive to misspecification of the input distribution.

In statistical learning theory, we need to bound the difference between the true risk \(R(h)\) and the empirical risk \(\widehat{R}_n(h)\). Because the training sample is random, this difference is a random variable. Concentration inequalities provide non‑asymptotic bounds on how sharply such random quantities cluster around their expectations. They are the mathematical engine that turns an empirical observation into a finite‑sample guarantee.

Without concentration, we could only say that the empirical risk “converges” as \(n\to\infty\). With Hoeffding, Bernstein, or McDiarmid inequalities, we obtain explicit tail bounds of the form

which directly yields confidence intervals and sample complexity estimates. The entire edifice of PAC learning and uniform convergence rests on these tools.

The Chernoff (or exponential) method is the most common technique for obtaining concentration bounds. For a random variable \(X\) and \(t>0\),

By taking the infimum over \(\lambda>0\), we obtain a bound that depends on the moment generating function (MGF) of \(X\). When \(X\) is a sum of independent random variables, the MGF factorises, and the problem reduces to bounding individual MGFs.

The proof uses convexity of the exponential function to bound \(e^{\lambda X}\) by a linear interpolation, then optimises the resulting quadratic expression. This lemma is the key ingredient for Hoeffding's inequality.

This form directly implies the sample mean version (A4.30) by dividing the sum by \(n\). The bound is sub‑Gaussian with variance proxy \(\frac{(b-a)^2}{4}\) per term.

For a fixed classifier \(h\) (chosen independently of the sample), the zero‑one loss \(Z_i = \mathbf{1}_{\{h(X_i)\neq Y_i\}}\) is bounded in \([0,1]\). Applying Hoeffding's inequality with all \(a_i=0, b_i=1\) gives

Thus, with probability \(\ge 1-\delta\),

This is a \(1/\sqrt{n}\) rate confidence interval. The width shrinks polynomially, but does not exploit any problem‑specific structure (e.g., small variance).

For a finite hypothesis class \(\mathcal{H}\) with size \(|\mathcal{H}|\), we combine Hoeffding's inequality with the union bound to control all hypotheses simultaneously:

Setting the right side to \(\delta\) and solving for \(\epsilon\) yields, with probability \(\ge 1-\delta\),

This uniform bound justifies ERM: the chosen hypothesis \(\hat h_{\mathrm{erm}}\) will have true risk close to the best in \(\mathcal{H}\). This is the prototype of the PAC guarantee for finite classes.

To bound the expected maximum deviation \(\mathbb{E}[\sup_{h\in\mathcal{H}} (\widehat{R}_n(h)-R(h))]\), we can use the following: for any \(\lambda>0\),

Applied to \(X_h = \widehat{R}_n(h)-R(h)\), the MGF bound from Hoeffding's lemma yields an expected supremum bound of \(O(\sqrt{\log|\mathcal{H}|/n})\). This is a direct route to uniform convergence.

This generalises Hoeffding's inequality to functions of independent variables that are not necessarily sums, yet have limited individual influence.

A sequence of random variables \((M_n)_{n\ge 0}\) is a martingale with respect to a filtration \(\mathcal{F}_n\) if \(\mathbb{E}[|M_n|]<\infty\) and \(\mathbb{E}[M_{n+1}\mid \mathcal{F}_n] = M_n\). The martingale difference is \(D_n = M_n - M_{n-1}\), satisfying \(\mathbb{E}[D_n\mid \mathcal{F}_{n-1}]=0\).

Concentration inequalities for martingale differences allow us to handle situations where data may be dependent, as long as the conditional expectation property holds (e.g., in online learning or sequential prediction).

This is the martingale analog of Hoeffding's inequality. It is particularly useful when the bounded differences condition of McDiarmid does not hold, but a martingale structure can be exploited.

For the uniform deviation \(F(S) = \sup_{h\in\mathcal{H}} \bigl|\widehat{R}_n(h)-R(h)\bigr|\), changing one training example changes the empirical risk by at most \(1/n\). Therefore, \(F\) satisfies the bounded differences property with \(c_i = 1/n\). McDiarmid's inequality gives

This bounds the deviation of the maximal gap from its mean. The remaining challenge is to bound \(\mathbb{E}[F(S)]\) via a capacity measure such as the Rademacher complexity or the VC dimension.

Hoeffding and McDiarmid inequalities always yield a rate of \(O(1/\sqrt{n})\) regardless of the problem’s variance. This is the slow rate. For many learning problems, the true excess risk can shrink at a much faster \(O(1/n)\) rate when the noise is small (e.g., under a margin condition). To capture this, one needs inequalities that incorporate variance information, such as Bernstein's inequality or self‑bounding techniques. Merely relying on bounded differences cannot distinguish between high‑variance and low‑variance scenarios.

For a fixed classifier \(h\), the loss \(\ell = \mathbf{1}_{\{h(X)\neq Y\}}\) is a Bernoulli random variable with success probability \(R(h)\). Hence,

The worst‑case variance is \(1/4\), attained when \(R(h)=1/2\). This worst‑case bound is used by Hoeffding's inequality. When the true risk is very small (rare misclassifications), the variance is much smaller, opening the door to tighter Bernstein‑type bounds.

Recall the comparison variable \(Z_h = \mathbf{1}_{h(X)\neq Y} - \mathbf{1}_{h^*(X)\neq Y}\) (A4.12). It satisfies \(|Z_h|\le 1\) and \(\mathbb{E}[Z_h] = E(h)\). Moreover,

Under a margin condition (e.g., \(|2\eta(X)-1|\ge \tau\) on the disagreement set), the excess risk identity (A4.10) gives \(\mathbb{P}(h\neq h^*) \le \frac{1}{\tau}E(h)\). Thus, \(\operatorname{Var}(Z_h) \le c E(h)\) for some constant \(c\). This self‑bounding property is the key to proving fast rates.

It is the simplest concentration inequality and the starting point for the Chernoff method. While often too weak on its own, it is the foundation for more powerful bounds.

This inequality is ubiquitous in deriving MGF bounds, entropy bounds, and in handling expectations of maxima (e.g., \(\mathbb{E}[\max_i X_i] \ge \max_i \mathbb{E}[X_i]\)).

Unlike Hoeffding, Bernstein’s bound adapts to the variance: when \(\sigma^2\) is small, the denominator behaves like \(2\sigma^2\) and the rate is much faster than \(O(1/\sqrt{n})\). This is essential for obtaining fast excess risk bounds in classification.

• HoeffdingBest when the variance is unknown or high. Gives a sub‑Gaussian tail with rate \(O(1/\sqrt{n})\) but ignores variance. Optimal for bounded random variables with worst‑case variance \(1/4\).
• BernsteinExcels when the variance is small. Combines a sub‑Gaussian term for small deviations and a sub‑exponential term for large deviations. Leads to fast \(O(1/n)\) rates when the loss has small variance (e.g., near‑Bayes classifiers).

In learning theory, Bernstein is preferred for excess risk bounds because the variance often scales with the excess risk itself (self‑bounding).

When a random variable \(Z\) satisfies \(|Z|\le 1\) and \(\operatorname{Var}(Z)\le c\,\mathbb{E}[Z]\) (as in A4.41), Bernstein's inequality applied to i.i.d. copies \(Z_1,\dots,Z_n\) yields that with probability at least \(1-\delta\),

Solving this quadratic inequality for \(\mathbb{E}[Z]\) gives an excess risk bound of order \(O(1/n)\) (up to logarithmic factors), which is a fast rate. This technique is central to proving oracle inequalities with convergence faster than \(1/\sqrt{n}\).

This is used repeatedly to decompose expectations, for instance when bounding \(\mathbb{E}[Z_h]\) by first conditioning on \(X\) and using the pointwise optimality of \(h^*\). It also underpins the analysis of martingale differences.

Many loss functions in classification satisfy a self‑bounding relation: \(\operatorname{Var}(\ell) \le c\, \mathbb{E}[\ell]\) (up to constant factors). This occurs because a mistake is a rare event when the classifier is close to optimal. The technique then proceeds as follows:

1. Apply a Bernstein‑type inequality to the centered losses.
2. Use the self‑bounding property to replace the variance term with a multiple of the true risk (or excess risk).
3. Obtain an inequality of the form \(\mathbb{E}[Z] \le \text{empirical term} + \frac{\alpha}{n} + \beta\sqrt{\frac{\mathbb{E}[Z]}{n}}\).
4. Solve the resulting quadratic inequality to isolate \(\mathbb{E}[Z]\), yielding a bound of order \(O(1/n)\).

This approach is the main engine behind fast rates in agnostic PAC learning.

A random variable \(X\) with mean zero is sub‑Gaussian with variance proxy \(\sigma^2\) if for all \(\lambda\in\mathbb{R}\),

Hoeffding's inequality shows that any bounded zero‑mean variable is sub‑Gaussian with \(\sigma^2 = (b-a)^2/4\). Sub‑Gaussian variables exhibit Gaussian‑like tail decay, and sums of independent sub‑Gaussian variables remain sub‑Gaussian. Many concentration results (e.g., McDiarmid, Azuma–Hoeffding) are essentially sub‑Gaussian tail bounds.

Chebyshev gives a polynomial tail (\(1/t^2\)) rather than the exponential tail of Hoeffding or Bernstein. It is useful when variances are known, but in learning theory it is almost always too weak to obtain PAC guarantees of the form \(\delta = e^{-n\epsilon^2}\). It is, however, the optimal bound for distributions with finite variance but no further moment bounds.

Cramér's Theorem provides the exact exponential rate for large deviations of the sample mean of i.i.d. variables. Let \(X_1,\dots,X_n\) i.i.d. with MGF \(\psi(\lambda)=\mathbb{E}[e^{\lambda X}]\). Then for any \(a > \mathbb{E}[X]\),

where \(\Lambda^*(a) = \sup_{\lambda>0} (\lambda a - \log\psi(\lambda))\) is the Fenchel–Legendre transform (rate function).

While PAC bounds are typically finite‑sample, Cramér's theorem justifies the optimality of Chernoff‑style bounds and explains the exponential decay rates seen in Hoeffding and Bernstein inequalities. It also connects learning theory to information theory via the rate function.

We consider a finite hypothesis class \(\mathcal{H}\) consisting of \(M\) candidate classifiers:

Each \(h_j : \mathcal{X} \to \{0,1\}\) is a fixed function. The learner receives an i.i.d. sample \(S = ((X_1,Y_1),\dots,(X_n,Y_n))\) drawn from \(P_{X,Y}\). The goal is to select a hypothesis \(\hat h \in \mathcal{H}\) that minimises the true risk \(R(h)\).

The finite dictionary setting is the simplest non‑trivial model for which we can prove precise oracle inequalities and PAC guarantees. It illustrates all the essential ideas—uniform convergence, the bias–complexity tradeoff, and the role of \(\log M\)—without the technical machinery required for infinite classes.

Proof sketch. By Hoeffding’s inequality (A4.32), for any fixed \(h\in\mathcal{H}\), \(|\widehat{R}_n(h)-R(h)| \le \sqrt{\frac{\log(2/\delta)}{2n}}\) with probability \(\ge 1-\delta\). Applying the union bound over all \(M\) hypotheses gives a uniform bound:

Set this equal to \(\delta\) and solve for \(\epsilon = \sqrt{\frac{\log(2M/\delta)}{2n}}\). On the event that this uniform bound holds, for any \(h^*\in\arg\min_{h\in\mathcal{H}} R(h)\),

Adjusting constants yields the stated bound.

Proof idea. Using the log‑sum‑exp trick (A4.34) or integration of the tail bound gives an expected supremum bound of order \(\sqrt{\frac{\log M}{n}}\). This form is often more convenient for comparing the sample complexity of different classes. The expectation bound directly implies that the sample complexity grows as \(O(\frac{\log M}{\epsilon^2})\) to achieve expected excess risk \(\le \epsilon\).

Assume realizability: there exists \(h^*\in\mathcal{H}\) such that \(Y = h^*(X)\) almost surely. Then \(R(h^*)=0\), and the ERM learner selects any hypothesis with zero training error.

In this setting, a tighter bound is available than the agnostic oracle inequality. From the earlier sample complexity theorem (A4.12), we have

This is a fast rate of \(O(1/n)\) for the excess risk (up to logs). Equivalently, for a given sample size \(n\), with probability \(\ge 1-\delta\),

The difference from the agnostic bound is striking: the error shrinks as \(1/n\) rather than \(1/\sqrt{n}\), because we exploit the fact that the optimal hypothesis makes zero mistakes almost surely.

In the agnostic case (no realizability), we compete against the best hypothesis in \(\mathcal{H}\). From the uniform bound in A4.54, with probability \(\ge 1-\delta\),

To achieve excess risk \(\le \epsilon\) with confidence \(\ge 1-\delta\), it suffices to have

This is the slow rate (\(1/\sqrt{n}\)). The sample complexity grows as \(O(\log M / \epsilon^2)\). This rate is minimax‑optimal for agnostic classification without additional assumptions. The gap between the realizable and agnostic rates illustrates the price of noise in the labels.

The sample complexity depends on \(\log M\) rather than \(M\) because the concentration bounds for sums of independent variables yield exponential tails. The union bound multiplies the failure probability by \(M\), and taking the logarithm converts this into an additive \(\log M\) term.

Intuitively, each hypothesis contributes a potential overfitting event, but due to the rapid exponential decay of the tail, the total probability of any bad event grows only logarithmically with the number of hypotheses. This is a fundamental feature of empirical processes: the complexity of a finite class is measured by its log‑cardinality. Even with millions of hypotheses (\(M\approx 10^6\)), \(\log M\) is only about \(14\), so the penalty is modest. This explains why finite hypothesis classes are easily learnable.

The oracle inequality for finite \(\mathcal{H}\) relies on uniform convergence of empirical risks to true risks over the entire class:

When this holds, the ERM principle succeeds: the minimiser of the empirical risk nearly minimises the true risk. For finite \(\mathcal{H}\), uniform convergence follows from Hoeffding + union bound. For infinite classes, we need richer tools—VC dimension, Rademacher complexity—to quantify the effective size of \(\mathcal{H}\) and establish uniform convergence. The uniform convergence framework is the backbone of statistical learning theory.

Consider the problem of learning an axis‑aligned rectangle in the unit square \(\mathcal{X}=[0,1]^2\). A rectangle is defined by four parameters \(a\le b, c\le d\) in \([0,1]\), and the corresponding hypothesis is \(h(x_1,x_2) = \mathbf{1}_{[a\le x_1\le b,\,c\le x_2\le d]}\).

While the set of all rectangles is uncountably infinite, we can discretize by restricting the boundaries to lie on a uniform grid of \(k\) points in each dimension. This yields at most \(k^4\) distinct rectangles, because each of the four boundaries can take \(k\) possible values (with the monotonicity constraint \(a\le b, c\le d\) the count is roughly \(k^4/4\)).

Thus \(\mathcal{H}_{\text{grid}}\) has size \(M \le k^4\). Applying the agnostic PAC bound (A4.57), to achieve excess risk \(\epsilon\) with confidence \(1-\delta\), we need

As we refine the grid (\(k\to\infty\)), \(\log k\) grows slowly, but the discretization introduces a small approximation error—the best grid rectangle may be slightly worse than the true optimal rectangle. This illustrates the bias–complexity tradeoff in action: finer grid reduces bias but increases the log‑cardinality penalty. The VC dimension approach (later) will handle the continuous rectangle class directly, without discretization, and give a bound of \(O(\frac{d_{\text{VC}} + \log(1/\delta)}{\epsilon})\) in the realizable case, where \(d_{\text{VC}}=4\).

Exact minimisation of the empirical risk \(\widehat{R}_n(h)\) over a hypothesis class \(\mathcal{H}\) may be computationally hard. Approximate ERM (or \(\rho\)-ERM) returns any hypothesis \(\hat h\) satisfying

for a tolerance \(\rho\ge 0\). The oracle inequality (A4.54) extends gracefully: with high probability,

Thus, a small optimisation error \(\rho\) adds additively to the excess risk. This is crucial for practical algorithms (e.g., gradient descent, convex relaxations) that may not find the exact minimiser. As long as \(\rho\) is of the same order as the estimation error, the overall rate is preserved.

In binary classification, the Bayes classifier \(h^*(x) = \mathbf{1}_{\{\eta(x)\ge 1/2\}}\) depends only on the regression function \(\eta(x)=\mathbb{P}(Y=1\mid X=x)\). A plug‑in classifier first estimates \(\eta\) by \(\widehat{\eta}_n\) from data, then thresholds:

This is a semi‑parametric strategy: the model for \(\eta\) can be parametric (logistic regression) or non‑parametric (kernel smoothing, random forests). The advantage is that one can leverage powerful regression or density estimation tools, and often obtain fast rates if \(\eta\) is smooth and well separated from \(1/2\) (Tsybakov’s margin condition).

However, plug‑in methods can be sub‑optimal if the estimation error of \(\eta\) near the boundary dominates. Direct ERM over classifiers may be preferable when the goal is only classification, as it targets the decision boundary directly.

The distinction between generative and discriminative modelling (first raised in A4.26) manifests concretely in the plug‑in approach.

• Generative plug‑inEstimate the class‑conditional densities \(p(x\mid Y=y)\) and the prior \(\pi_y = \mathbb{P}(Y=y)\). Then form \(\widehat{\eta}(x) = \frac{\widehat{\pi}_1\,\widehat{p}(x\mid 1)}{\widehat{\pi}_0\,\widehat{p}(x\mid 0) + \widehat{\pi}_1\,\widehat{p}(x\mid 1)}\). This corresponds to Linear Discriminant Analysis (LDA) or Quadratic Discriminant Analysis (QDA). It uses strong parametric assumptions but is sample‑efficient when correct.
• Discriminative plug‑inDirectly model \(\eta(x)\) as \(g(\theta^\top x)\) (e.g., logistic regression). No attempt to model \(P_X\). This is more robust to misspecification of the input distribution, but may require larger sample size to achieve the same accuracy as a well‑specified generative model.

Thus, the generative–discriminative tradeoff is a choice of inductive bias: a stronger bias (full distributional model) yields better sample complexity if true, while a weaker bias (conditional model) protects against model misspecification.

The agnostic PAC bound for finite \(\mathcal{H}\) (A4.57) gives an excess risk of order \(\sqrt{\frac{\log M}{n}}\). More generally, for any class with VC dimension \(d\), the minimax rate in the agnostic case is \(\Theta\bigl(\sqrt{\frac{d}{n}}\bigr)\). This is the slow rate.

It arises because the deviation between empirical and true risk is controlled by a sub‑Gaussian tail that ignores the variance of the loss. The slow rate is unavoidable without further assumptions: there exist distributions for which any algorithm must incur excess risk at least \(c\sqrt{d/n}\).

To beat the slow rate and achieve fast rates (\(O(1/n)\)), one needs additional structure—typically, a margin condition or low noise that makes the variance of the loss small compared to its expectation (see the self‑bounding technique, A4.48).

Recall the comparison variable from A4.12: \(Z_h = \mathbf{1}_{\{h(X)\neq Y\}} - \mathbf{1}_{\{h^*(X)\neq Y\}}\). Its expectation is the excess risk \(E(h)\). The empirical excess risk can be expressed through the sample average of i.i.d. copies \(Z_{h,i}\).

For the ERM \(\hat h\), we have

because \(\hat h\) minimises the empirical 0‑1 risk. Therefore, the empirical excess risk of \(\hat h\) is non‑positive, and the true excess risk is bounded by the maximal deviation:

This reduction converts the problem of bounding the excess risk of ERM into controlling the supremum of an empirical process indexed by \(\mathcal{H}\). This is the entry point for VC theory and Rademacher complexity.

The quantity

is the maximal deviation of the empirical risk from the true risk over the class \(\mathcal{H}\). It is the central object of uniform convergence theory.

If \(\Delta_n(\mathcal{H})\) is small, then the empirical risk is a uniformly good proxy for the true risk, and ERM approximately minimises the true risk. For finite \(\mathcal{H}\), Hoeffding + union bound yields \(\Delta_n(\mathcal{H}) = O_P\bigl(\sqrt{\frac{\log|\mathcal{H}|}{n}}\bigr)\). For infinite classes, the rate depends on the VC dimension or Rademacher complexity, and the asymptotic behaviour is described by the Glivenko–Cantelli property (if \(\Delta_n(\mathcal{H})\to 0\) in probability) or the stronger Donsker property (if the process converges weakly).

All previous results generalise from the 0‑1 loss to any bounded loss function \(\ell(y',y)\). The true risk becomes

and the empirical risk is \(\widehat{R}_n(h) = \frac{1}{n}\sum_{i=1}^n \ell(h(X_i), Y_i)\). If \(\ell\) takes values in \([0,1]\), the same Hoeffding and Bernstein bounds apply.

This extension is crucial because many practical algorithms minimise surrogate losses that are convex upper bounds on the 0‑1 loss (hinge loss, logistic loss, exponential loss). The theory for bounded losses seamlessly covers these cases, though additional calibration analysis is needed to relate the surrogate risk to the 0‑1 risk.

For a bounded loss \(\ell\in[0,1]\), the functional \(F(S) = \sup_{h\in\mathcal{H}} \bigl(\widehat{R}_n(h) - R(h)\bigr)\) satisfies the bounded differences property with constant \(c_i = 1/n\). McDiarmid’s inequality (A4.35) then gives

Thus, the random oscillation of the supremum around its mean is controlled at the rate \(O(1/\sqrt{n})\), regardless of the complexity of \(\mathcal{H}\). The difficulty is entirely in bounding the mean \(\mathbb{E}[F(S)]\), which depends on the capacity of \(\mathcal{H}\)—measured by the Rademacher complexity or the VC dimension. This decomposition (concentration of the empirical process around its mean + bounding the mean) is the standard template for uniform convergence bounds.

Let \(P_n = \frac{1}{n}\sum_{i=1}^n \delta_{(X_i,Y_i)}\) be the empirical measure induced by the sample. Then the empirical risk is simply the integral under \(P_n\):

The true risk is the integral under the population measure \(P\). The uniform deviation \(\Delta_n(\mathcal{H})\) is thus

where \(\ell_h(x,y) = \ell(h(x),y)\). This perspective connects learning theory to empirical process theory in probability and statistics. The class \(\{\ell_h : h\in\mathcal{H}\}\) is a collection of functions, and its complexity (e.g., bracketing number, uniform entropy) determines the rate of the uniform central limit theorem. For 0‑1 loss, the complexity is exactly captured by the VC dimension of \(\mathcal{H}\).

Proof. From the uniform bound (A4.54), for any \(\epsilon>0\), \(\mathbb{P}\bigl(R(\hat h_n) > \min_{h\in\mathcal{H}} R(h) + \epsilon\bigr) \le 2M e^{-n\epsilon^2/2} \to 0\) as \(n\to\infty\). Thus, the excess risk converges to zero in probability. Almost‑sure convergence can also be shown via the Borel–Cantelli lemma.

This result is the simplest demonstration that learning is possible: with enough data, ERM over a finite class approaches the performance of the best available predictor. The proof relies entirely on the exponential tail bounds from Hoeffding’s inequality and the union bound.

Classical statistics often provides asymptotic results: consistency (\(\hat\theta_n\to\theta\)), asymptotic normality, and confidence intervals that hold as \(n\to\infty\). In machine learning, we demand finite‑sample (non‑asymptotic) guarantees—bounds that are valid for a fixed sample size \(n\), with explicit constants, confidence \(\delta\), and accuracy \(\epsilon\).

• Asymptotic“For large \(n\), the estimator is approximately normal.” Does not tell us whether \(n=100\) is enough.
• Finite‑sample“With probability \(\ge 1-\delta\), the excess risk is at most \(\sqrt{\frac{\log M}{n}}\).” Provides a concrete recipe for sample size and an operational confidence interval.

The PAC learning framework is inherently finite‑sample. The oracle inequalities and uniform convergence bounds we have derived are finite‑sample guarantees that hold for every \(n\), and they imply classical consistency as a simple corollary (A4.70). The advantage of the finite‑sample viewpoint is that it forces us to quantify the effect of model complexity on generalisation, rather than hiding it in an asymptotic limit.

ERM is a proper learning rule: it outputs a hypothesis from the same class \(\mathcal{H}\) used for training. Improper learning allows the learner to output a predictor that may not belong to \(\mathcal{H}\), often from a larger class \(\mathcal{H}'\). This can break computational barriers: some proper learning problems are NP‑hard, while an improper learner can achieve polynomial runtime by returning a combination of hypotheses (e.g., a voting classifier).

Moreover, improper learning can yield better sample complexity. For example, a finite class \(\mathcal{H}\) can be embedded into a convex hull; an improper learner that outputs a randomised classifier (a distribution over \(\mathcal{H}\)) may enjoy faster rates. The oracle inequality for improper learners typically replaces \(\log|\mathcal{H}|\) with the Rademacher complexity of the output class \(\mathcal{H}'\), which can be much smaller than \(\log|\mathcal{H}|\).

Thus, allowing the learner to “think outside the box” is both a computational and statistical advantage, and it underpins techniques like boosting and random forests.

A covering number \(\mathcal{N}(\mathcal{H},\rho,\epsilon)\) is the smallest number of balls of radius \(\epsilon\) (in some metric \(\rho\)) needed to cover the class \(\mathcal{H}\). For a finite hypothesis class with \(|\mathcal{H}|=M\), we can use the discrete metric \(\rho(h,h') = \mathbf{1}_{h\neq h'}\). Then, for any \(\epsilon < 1\),

since each hypothesis is isolated and requires its own ball. For \(\epsilon\ge 1\), a single ball covers everything. Thus, covering numbers for finite classes merely recapture the cardinality.

However, this perspective extends smoothly to infinite classes. By choosing a meaningful metric—for instance, the empirical \(L_1\) distance \(\frac{1}{n}\sum_{i=1}^n |h(x_i)-h'(x_i)|\)—the covering number at a small scale \(\epsilon\) can be finite even when \(\mathcal{H}\) is infinite. This is the gateway to complexity measures like metric entropy and Rademacher complexity.

Metric entropy is the logarithm of the covering number: \(\log \mathcal{N}(\mathcal{H},\rho,\epsilon)\). It quantifies the “effective size” of \(\mathcal{H}\) at resolution \(\epsilon\). In learning theory, the relevant metric is often

the empirical disagreement rate on the sample. For a finite class \(\mathcal{H}\) of size \(M\), \(\log\mathcal{N}(\mathcal{H},\rho_n,\epsilon) \le \log M\) for all \(\epsilon<1/n\) (the smallest non‑zero difference), but could be much smaller for coarser scales. For infinite classes, the growth of \(\log\mathcal{N}(\mathcal{H},\rho_n,\epsilon)\) as \(\epsilon\to 0\) determines the empirical process complexity and, ultimately, the rate of uniform convergence.

Key relationships: VC dimension \(d\) implies a bound \(\mathcal{N}(\mathcal{H},\rho_n,\epsilon) \le (C/\epsilon)^{O(d)}\), giving metric entropy of order \(d\log(1/\epsilon)\). Rademacher complexity is closely linked via Dudley’s entropy integral. Thus, metric entropy bridges the gap between simple combinatorial counts (finite \(\mathcal{H}\)) and sophisticated capacity measures for infinite classes.

Consequently:

• To achieve excess risk \(\le\epsilon\) with confidence \(1-\delta\), it suffices to have \(n \ge \frac{2\log(2M/\delta)}{\epsilon^2}\).
• The estimator is consistent: \(R(\hat h_{\mathrm{erm}})\to \min_{h\in\mathcal{H}} R(h)\) in probability as \(n\to\infty\).
• The bound depends on \(\log M\) rather than \(M\), so even very large but finite classes are efficiently learnable.
• If realizable (\(R(h^*)=0\) for some \(h^*\in\mathcal{H}\)), the rate improves to \(O(1/n)\).

This single corollary encapsulates the entire theory of learning with a finite hypothesis class and serves as the blueprint for generalisation to infinite classes via VC dimension and Rademacher complexity.

The union bound (Boole’s inequality) states that for any countable collection of events \(A_1, A_2, \dots\),

Despite its simplicity, the union bound is the single most important probabilistic tool in learning theory. It converts a guarantee for a single fixed hypothesis into a uniform guarantee over an entire hypothesis class, at the modest price of a factor \(|\mathcal{H}|\) (or \(\log|\mathcal{H}|\) after taking logarithms for exponential tail bounds).

Why it works so well in learning:

• Concentration inequalities (Hoeffding, Bernstein) provide exponentially decaying probabilities for a single bad event.
• The union bound sums these probabilities; the log of the sum becomes \(\log M\) plus a negative term in \(n\).
• Thus, the penalty for considering many hypotheses simultaneously is only logarithmic in \(M\), not linear.

Caution: The union bound is a worst‑case inequality; it does not exploit correlations between events. When hypotheses are highly similar (as in an infinite class), a naive union bound over a discretization can be too loose. More refined tools (covering numbers, chaining) are needed to replace the crude count \(M\) with a measure of intrinsic complexity. Nonetheless, for finite \(\mathcal{H}\), the union bound is the essential bridge from individual to uniform guarantees, and it lies at the heart of the PAC bounds we have proved.

The speed at which a learning algorithm can approach the Bayes risk depends critically on the noise in the labels, i.e., on how close the regression function \(\eta(x)=\mathbb{P}(Y=1\mid X=x)\) is to \(1/2\). When \(\eta(x)\) is near \(1/2\), the label is almost a fair coin toss, and even the Bayes classifier makes errors; this uncertainty hampers the estimation of the decision boundary. Conversely, when \(\eta(x)\) is well separated from \(1/2\), the label is nearly deterministic, and the learning problem is much easier.

Formally, the noise affects the variance of the comparison variable \(Z_h\) (A4.12) and thus the achievable excess risk rates. Without assumptions on noise, the minimax rate is the slow rate \(O(1/\sqrt{n})\). With stronger noise conditions, one can achieve fast rates up to \(O(1/n)\). The following sections quantify this precisely, moving from the noiseless deterministic case through Massart’s hard‑margin condition to Tsybakov’s soft‑margin condition.

The labels are noiseless if the regression function takes only the extreme values:

Equivalently, there exists a deterministic function \(f:\mathcal{X}\to\{0,1\}\) such that \(Y=f(X)\) with probability one. In this setting, the Bayes risk \(R^* = 0\), and the Bayes classifier \(h^* = f\) achieves zero error. Moreover, for any hypothesis \(h\), the comparison variable \(Z_h\) simplifies to \(\mathbf{1}_{h(X)\neq f(X)}\), whose variance is at most \(R(h)\). The realizability assumption (that \(f\in\mathcal{H}\)) is exactly the noiseless case with the optimal predictor inside the class.

This case yields the fastest possible learning rate because every misclassification carries full weight, and empirical errors are highly informative about the true structure.

Proof sketch. Since \(R(h^*)=0\), every misclassification of \(h^*\) on the sample is impossible. Hence the ERM picks a hypothesis with zero training error. The probability that a fixed bad hypothesis with \(R(h)>\epsilon\) makes zero mistakes on \(n\) i.i.d. draws is at most \((1-\epsilon)^n \le e^{-\epsilon n}\). A union bound over the at most \(M\) bad hypotheses gives failure probability \(\le M e^{-\epsilon n}\). Setting this \(\le\delta\) and solving for \(\epsilon\) yields the bound (up to constants; the precise constant factor can be optimised). Thus the excess risk is \(O(\log(M/\delta)/n)\), a fast rate compared to the agnostic \(O(\sqrt{\log M / n})\) slow rate.

This result matches the realizable PAC bound from A4.56. The key difference from the agnostic case is that the empirical risk of the target \(h^*\) is zero, which prevents the slack introduced by the approximation error and enables a tighter concentration argument.

The difference between the two rates can be understood through the variance of the zero‑one loss. For a fixed classifier \(h\), the loss indicator \(\mathbf{1}_{h(X)\neq Y}\) has variance \(R(h)(1-R(h)) \le \frac14\). In the agnostic setting, we only use this worst‑case variance bound, leading to a Hoeffding‑style concentration of order \(1/\sqrt{n}\). This is the slow rate.

In the noiseless case, the true risk of the target is zero, so the variance of the loss for the Bayes classifier is zero. More generally, as \(\hat h\) approaches zero error, its variance shrinks proportionally to its risk. This self‑bounding behaviour allows a Bernstein‑type bound that yields a rate of \(1/n\) (the fast rate).

The gap between these rates has profound practical implications: in high‑noise problems, many more samples are needed to reduce the excess risk by a factor of \(2\) compared to low‑noise problems. Identifying the prevailing noise regime is therefore an essential part of model selection and data collection.

The fast rate \(O(1/n)\) proved above relies on two ingredients: (i) the existence of a hypothesis with zero true risk, and (ii) that this hypothesis belongs to \(\mathcal{H}\). If either condition fails—i.e., the labels are noisy (\(R^*>0\)) or the Bayes classifier is not in \(\mathcal{H}\)—then even the best hypothesis in \(\mathcal{H}\) makes errors, and the variance of the loss does not vanish. Without additional structure, the slow rate \(1/\sqrt{n}\) is minimax‑optimal: for any algorithm, one can construct a distribution over \(\mathcal{X}\times\{0,1\}\) such that the excess risk is at least \(c\sqrt{\log(M)/n}\) with constant probability.

Thus, realizability alone is sufficient for fast rates, but it is a strong assumption rarely met in practice. To obtain fast rates under label noise, one must impose noise conditions that control how much probability mass lies near the decision boundary (\(\eta(x)\approx 1/2\)). The next sections develop two such conditions: Massart’s hard margin and Tsybakov’s soft margin.

This condition says that the regression function is uniformly bounded away from \(1/2\). At every point \(x\), one label is favoured by a margin of at least \(\gamma/2\). This is a hard margin assumption: there is no “twilight zone” where the label is truly ambiguous. It is the minimal noise condition that still permits fast rates in classification, because it implies a strict relationship between excess risk and the probability of disagreement with the Bayes classifier (see A4.83).

Under Massart's condition, the excess risk identity (A4.10) gives a direct lower bound. For any classifier \(h\),

Thus, the probability of disagreement between \(h\) and the Bayes classifier is at most \(E(h)/\gamma\). This is the crucial self‑bounding property: a small excess risk implies that \(h\) agrees with \(h^*\) on most of the input space.

In terms of the comparison variable \(Z_h\) (A4.12), we obtain \(\operatorname{Var}(Z_h) \le \mathbb{P}(h\neq h^*) \le E(h)/\gamma\). So the variance is bounded by a constant multiple of the excess risk itself. Plugging this into Bernstein’s inequality yields fast rates of order \(O(1/n)\).

Proof sketch. The proof uses the self‑bounding Bernstein technique (A4.46). The comparison variable \(Z_h\) satisfies \(|Z_h|\le 1\) and \(\operatorname{Var}(Z_h)\le E(h)/\gamma\). For the ERM \(\hat h\), the empirical excess risk is non‑positive by definition. Applying Bernstein’s inequality to the i.i.d. copies of \(Z_{\hat h}\) (after a symmetrization or via a uniform bound over \(\mathcal{H}\)), we obtain

Solving this quadratic inequality for \(E(\hat h)\) yields the claimed linear dependence in \(1/n\). The rate is the same \(O(1/n)\) as in the noiseless case, but slowed down by a factor \(1/\gamma\).

This condition characterises how much mass of the marginal distribution \(P_X\) lies in regions where the label is nearly a coin toss. The parameter \(\alpha\) controls the concentration of the margin near zero:

• \(\alpha = 0\) (formally, always true with \(c\ge 1\)) — no assumption beyond boundedness; the slow rate applies.
• \(\alpha \to \infty\) — the margin is strictly bounded away from zero, recovering Massart’s condition.
• Finite \(\alpha > 0\) — the mass near the boundary decays polynomially; an interpolated rate between \(1/\sqrt{n}\) and \(1/n\) is achievable.

Tsybakov's condition is the standard way to interpolate between the no‑assumption regime and the hard‑margin regime, and it yields a continuum of possible learning rates.

Proof sketch. For any threshold \(\delta>0\), decompose

Using the excess risk identity, \(E(h) \ge \delta\,\mathbb{P}(h\neq h^*, |2\eta-1|>\delta)\). The second term is bounded by \(\mathbb{P}(|2\eta-1|\le\delta) \le c\delta^\alpha\). Hence \(\mathbb{P}(h\neq h^*) \le E(h)/\delta + c\delta^\alpha\). Optimising over \(\delta\) (choosing \(\delta \propto E(h)^{1/(\alpha+1)}\)) yields the stated inequality. This inequality generalises the Massart relation (\(\alpha\to\infty\) gives \(\mathbb{P}(h\neq h^*)\le E(h)/\gamma\)).

Proof sketch. As before, we use the self‑bounding technique but now with the weaker link between variance and excess risk provided by Lemma A4.86: \(\operatorname{Var}(Z_h)\le \mathbb{P}(h\neq h^*)\le C_\alpha E(h)^{\alpha/(\alpha+1)}\). Bernstein’s inequality yields, for the ERM,

Solving this inequality for \(E(\hat h)\) gives the claimed exponent \(\frac{\alpha+1}{\alpha+2}\). The extremes match: \(\alpha\to 0\) yields \(1/\sqrt{n}\) (slow rate), \(\alpha\to\infty\) yields \(1/n\) (fast rate). This theorem elegantly unifies the learning rates under the full spectrum of noise conditions.

Thus, the Tsybakov condition serves as the central noise model in modern classification theory, bridging the gap between the worst‑case agnostic setting and the idealistic noiseless setting.

The learning rate for binary classification with a finite hypothesis class depends on the noise level captured by the Tsybakov exponent \(\alpha\):

The rate continuously improves as the noise decreases, bridging the slow rate \(1/\sqrt{n}\) and the fast rate \(1/n\). The exponent \(\frac{\alpha+1}{\alpha+2}\) grows from \(1/2\) toward \(1\) as \(\alpha\) increases. This interpolation shows that additional structural assumptions directly translate into tighter guarantees—a central theme in modern learning theory.

Consider a satellite imaging task: classifying a pixel as “water” or “land” from multispectral reflectance. In deep ocean or dense forest, the spectral signature is unambiguous—\(\eta(x)\) is near \(0\) or \(1\). Near coastlines or wetlands, the classes blend and \(\eta(x)\approx 1/2\).

Suppose the marginal distribution over pixels puts little mass on the ambiguous transitional zones. Quantitatively, assume that for small \(t\), the fraction of pixels with \(\vert 2\eta(x)-1\vert \le t\) is at most \(c t^{\alpha}\). This is the Tsybakov condition. A typical value for well‑separated terrain might be \(\alpha \approx 2\), meaning that the ambiguous region is thin. Then the learning rate becomes

substantially faster than the agnostic \(\sqrt{\log M / n}\). This explains why high‑resolution remote sensing classification can succeed with moderate training sets: the physical world often satisfies a margin condition where the class overlap is limited to narrow boundaries.

A remarkable feature of the ERM learner is that it automatically adapts to the underlying noise level—the algorithm itself does not need to know \(\alpha\) or \(\gamma\). If the data happen to satisfy a Tsybakov condition with exponent \(\alpha\), the self‑bounding Bernstein argument guarantees that the excess risk decays at the corresponding fast rate, with no change to the learning procedure.

However, the theoretical guarantee we can explicitly state without a priori knowledge of \(\alpha\) is typically the slow rate. To obtain a fully data‑dependent bound that adapts to unknown noise, one can use empirical Bernstein inequalities or local Rademacher complexities. These refined analyses yield oracle inequalities where the rate automatically improves when the Bayes risk is small or the margin is large. Thus, while ERM implicitly adapts, constructing adaptive confidence bounds requires more sophisticated tools than the plain uniform Hoeffding bound.

Talagrand’s inequality is a sharp concentration result for empirical processes. For a class \(\mathcal{F}\) of functions uniformly bounded by \(1\), it states that with high probability,

where \(\sigma^2 = \sup_{f\in\mathcal{F}} \operatorname{Var}(f(X))\). This inequality splits the deviation into a mean term (the Rademacher complexity) and a variance term.

When combined with noise conditions that force \(\sigma^2\) to be small for near‑optimal hypotheses, the variance term shrinks and the overall rate becomes faster than \(1/\sqrt{n}\). This is the modern route to proving fast rates for ERM over infinite classes, via localisation and Talagrand’s inequality. Talagrand’s result underpins many sharp oracle inequalities in the literature.

In many algorithms, we do not learn a binary classifier directly but a real‑valued function \(f:\mathcal{X}\to\mathbb{R}\), and predict via \(\operatorname{sign}(f(x))\). The margin condition relates the excess risk of the sign classifier to the excess \(\phi\)-risk (for a convex surrogate \(\phi\)).

The Tsybakov noise condition on \(\eta(x)\) can be equivalently formulated as a margin condition on the Bayes classifier’s scoring function. For any measurable \(f\), define its classification error as \(R(f) = \mathbb{P}(\operatorname{sign}(f(X))\neq Y)\). If \(f^*\) is the optimal scoring function (e.g., \(f^*(x)=2\eta(x)-1\)), then there exists a constant \(c>0\) such that

with \(\rho = \frac{\alpha}{\alpha+1}\) under Tsybakov noise. This directly parallels the disagreement lemma (A4.95) and is used to prove fast rates for SVM, boosting, and other margin‑based methods.

In the context of the comparison variable \(Z_h\), we have \(M=1\) and often \(\sigma^2 \le C\,E(h)\). When \(E(h)\) is small, the denominator is dominated by \(2\sigma^2 \approx 2C E(h)\), leading to a quadratic inequality that solves to \(E(h)=O(1/n)\). This is the formal engine of fast rates. For finite \(\mathcal{H}\), applying a union bound and solving the resulting Bernstein bound yields the explicit rates under noise conditions.

A loss function \(\ell(y',y)\) is self‑bounding if there exists a constant \(c>0\) such that for any predictor \(h\),

For the 0‑1 loss, this reduces to \(\operatorname{Var}(Z_h)\le c\,E(h)\). Under a noise condition, the constant \(c\) is \(1/\gamma\) (Massart) or \(C_\alpha E(h)^{-\frac{1}{\alpha+1}}\) (Tsybakov, after rearrangement). More generally, for any bounded loss with a unique minimiser and a curvature condition near the optimum, the excess loss is self‑bounding. This property is the key requirement for proving fast rates using Bernstein‑type inequalities.

Self‑bounding enables a “bootstrap” argument: a small empirical excess risk forces the true excess risk to be small, which in turn controls the variance, tightening the concentration even further. This virtuous cycle is the heart of local empirical process theory.

The lemma converts the noise assumption into a concrete relationship between the disagreement region (probability that \(h\) differs from the optimal rule) and the excess risk. Because the comparison variable \(Z_h\) satisfies \(|Z_h|\le\mathbf{1}_{h\neq h^*}\) and \(\mathbb{E}[Z_h]=E(h)\), the variance is bounded by the disagreement probability. This directly plugs into Bernstein’s inequality to produce the interpolated rates.

Proof outline. For any \(h\), define \(Z_h\) as before. Because \(\widehat{R}_n(\hat h)\le\widehat{R}_n(h^*)\), we have \(\frac{1}{n}\sum_{i=1}^n Z_{\hat h,i}\le 0\). Then by Bernstein's inequality and the union bound over the \(M\) hypotheses, with high probability every \(h\) satisfies

for a suitable constant \(C\) (using \(\operatorname{Var}(Z_h)\le E(h)/\gamma\)). Since the empirical excess for \(\hat h\) is non‑positive, we get \(E(\hat h)\le C\frac{\log(M/\delta)}{\gamma n}\). Tuning constants gives the clean bound. This rate is optimal up to the logarithmic factor.

Thus, under a hard margin, ERM learns at the fastest possible rate for a finite class, exactly the same as in the noiseless realizable setting up to the factor \(1/\gamma\).

All guarantees so far assume that the hypothesis class \(\mathcal{H}\) is finite. This captures many practical situations—for instance, the class of decision trees of bounded depth on a finite feature grid, or a fixed set of hand‑crafted rules. However, the most powerful learning algorithms work with infinite classes: linear classifiers in \(\mathbb{R}^d\), neural networks with real‑valued weights, kernel machines, and decision trees over continuous features. These classes contain uncountably many distinct functions, yet they generalise well in practice.

The goal of VC theory is to extend the finite‑class PAC bounds to infinite classes. The finite cardinality \(|\mathcal{H}|\) is replaced by a combinatorial measure—the VC dimension—that quantifies the effective complexity of \(\mathcal{H}\). Remarkably, a class with infinite cardinality but finite VC dimension can be learned from a finite sample, with sample complexity depending on the VC dimension rather than the (infinite) size.

Thus, VC theory provides the foundation for learning with all standard model classes and explains why many rich families of predictors do not overfit despite their vastness.

A simple way to handle an infinite class is to restrict it to a finite subset, e.g., by discretising continuous parameters (as with axis‑aligned rectangles on a grid, A4.60). If we choose a finite subclass \(\mathcal{H}_{\text{fin}}\subseteq\mathcal{H}\), then all finite‑class bounds apply directly: with probability at least \(1-\delta\),

However, this introduces an additional discretisation error: the best hypothesis in \(\mathcal{H}_{\text{fin}}\) may be worse than the best in \(\mathcal{H}\). The total error decomposes into approximation error (due to discretisation) plus estimation error (due to finite sample). The challenge is to choose the discretisation so that both errors are balanced, leading to optimal rates.

VC theory circumvents this by directly analysing the complexity of the full class \(\mathcal{H}\) via its growth function, without explicit discretisation, yielding tighter and more elegant bounds.

A set of points \(\{x_1,\dots,x_n\}\subseteq\mathcal{X}\) is shattered by \(\mathcal{H}\) if the hypotheses in \(\mathcal{H}\) can realise all \(2^n\) possible binary labelings of these points. Formally,

In other words, restricting \(\mathcal{H}\) to these \(n\) points yields the set of all \(2^n\) functions—the class is as rich as possible on that specific set. Shattering is the central combinatorial concept: a class has high capacity if it can shatter large sets. The VC dimension is the size of the largest shattered set.

For example, the class of all rectangles in \(\mathbb{R}^2\) cannot shatter a set of \(5\) points in general position (there exists a labeling pattern that no rectangle can realise), but it can shatter some set of \(4\) points, so its VC dimension is at least \(4\).

The VC dimension is an integer measuring the capacity of the class. A finite VC dimension is necessary and sufficient for uniform convergence and PAC learnability in the distribution‑free sense. Classes with \(\operatorname{VCdim}(\mathcal{H})<\infty\) are called VC classes. The VC dimension generalises the finite cardinality: for a finite class of size \(M\), we always have \(\operatorname{VCdim}(\mathcal{H})\le \log_2 M\). Conversely, an infinite class can have small VC dimension (e.g., thresholds on the line have VC dimension 1).

Consider the class of indicator functions of axis‑aligned rectangles in \(\mathbb{R}^2\):

Claim: \(\operatorname{VCdim}(\mathcal{H}_{\text{rect}}) = 4\).

Proof sketch.

• Upper bound: Given any set of 5 points, consider the “extreme” points (leftmost, rightmost, topmost, bottommost). A labelling that assigns label 1 to the four extreme points and label 0 to the remaining interior point cannot be realised by any rectangle—if a rectangle contains the four extreme points, it must contain their convex hull, and thus the interior point. Hence no set of 5 points can be shattered, so VCdim ≤ 4.
• Lower bound: The set of 4 points \(\{(0,0), (0,1), (1,0), (1,1)\}\) is shattered: for any subset, one can find a rectangle that contains exactly those points (e.g., for a single point, a tiny rectangle around it). Thus VCdim ≥ 4.

Thus the VC dimension is exactly 4, matching the number of parameters. Note, however, that the number of parameters is not a reliable measure of VC dimension—some classes with many parameters have small VC dimension, and vice‑versa (see sine functions, A4.106).

The class of indicator functions of closed intervals on \(\mathbb{R}\) is

Claim: \(\operatorname{VCdim}(\mathcal{H}_{\text{int}}) = 2\).

Proof.

• Lower bound: Two points \(x_1 < x_2\) are shattered: label patterns (1,0) can be realised by an interval covering only \(x_1\) (e.g., \([x_1, x_1]\)), (0,1) by an interval covering only \(x_2\), (1,1) by \([x_1,x_2]\), and (0,0) by an interval disjoint from both.
• Upper bound: Three distinct points \(x_1

Hence the VC dimension is 2. This is a simple example where the class is infinite yet has very small capacity, and sample complexity depends on the VC dimension 2, not on the infinite number of parameters \(a,b\).

Consider the class of homogeneous linear classifiers in \(\mathbb{R}^d\) (halfspaces through the origin):

For points in general position, this class has VC dimension \(d\). If we add a bias term (affine classifiers, thresholded at zero), the class becomes \(\{x\mapsto \operatorname{sign}(w^\top x + b)\}\) and its VC dimension is \(d+1\).

Proof for affine classifiers.

• Lower bound: The set of \(d+1\) points consisting of the origin and the \(d\) standard basis vectors in \(\mathbb{R}^d\) is shattered. (Embed in \(\mathbb{R}^{d+1}\) by appending a coordinate 1; the VC dimension of linear classifiers in \(\mathbb{R}^{d}\) is \(d+1\) by standard argument using Radon's theorem or by constructing weight vectors for each subset.) More concretely, take points \(0, e_1,\dots,e_d\). Any labeling corresponds to a separating hyperplane through some of these points.
• Upper bound: By Radon’s theorem, any set of \(d+2\) points in \(\mathbb{R}^d\) can be partitioned into two subsets whose convex hulls intersect. If a labeling assigns 1 to one subset and 0 to the other, a halfspace cannot separate them because no hyperplane can place the two subsets on opposite sides when their convex hulls intersect. Hence no set of \(d+2\) points is shattered, so VCdim ≤ d+1.

Therefore \(\operatorname{VCdim}(\mathcal{H}_{\text{affine}}) = d+1\).

The class of indicator functions of axis‑aligned rectangles (boxes) in \(\mathbb{R}^d\) is

Claim: \(\operatorname{VCdim}(\mathcal{H}_{\text{box}}) = 2d\).

Proof sketch.

• Lower bound: Choose the \(2d\) points consisting of, for each dimension \(i\), two points at the extremes, e.g., \(x_i^{(0)}\) with \(i\)-th coordinate 0 and \(x_i^{(1)}\) with \(i\)-th coordinate 1, all other coordinates 0. These \(2d\) points can be shattered: for any subset \(S\), construct a box whose \(i\)-th interval is \([0.1,0.9]\) if both types of points in dimension \(i\) are in \(S\) or neither, or a tiny interval around the coordinate needed to include exactly the desired points. This is analogous to the 2D case.
• Upper bound: Given any \(2d+1\) points, project onto each coordinate. By the pigeonhole principle and an argument similar to the 2D case, there exists a labeling that cannot be realised. A formal proof uses the fact that the class of unions of at most \(d\) intervals has VC dimension \(2d\), and the rectangle class corresponds exactly to the product of \(d\) intervals. A standard result states that product classes have VC dimension \(2d\).

Hence the VC dimension grows linearly with dimension, despite the number of parameters being \(2d\).

The class of indicator functions of all convex sets in the plane,

has infinite VC dimension.

Proof. Place \(n\) points on the unit circle. For any subset of these points, their convex hull is a polygon whose vertices are a subset of the points. By taking the convex set to be that polygon (or a slightly smoothed version), we can realise exactly that subset as the points inside the convex set. Since this works for any subset, any set of \(n\) points on the circle is shattered. As \(n\) can be arbitrarily large, \(\operatorname{VCdim}(\mathcal{H}_{\text{convex}}) = \infty\).

Thus, the class of convex sets is not PAC learnable in the distribution‑free sense; it can perfectly fit any finite sample, leading to severe overfitting. This is a striking example of an infinite VC dimension class that seems simple but is too rich to generalise.

Consider the class of binary classifiers induced by thresholding a sine wave with frequency and phase parameters:

This class is parametrized by only two real numbers (\(\omega,\phi\)), yet its VC dimension is infinite.

Proof idea. For any \(n\) distinct points \(x_1,\dots,x_n\in\mathbb{R}\), we can choose the frequency \(\omega\) large enough so that the sine wave oscillates arbitrarily fast. By adjusting \(\phi\), we can assign the sign of \(\sin(\omega x_i+\phi)\) to match any desired binary pattern—essentially, the sine function can act as a “universal” lookup table for any finite set by choosing a sufficiently high frequency. Hence any finite set can be shattered, giving infinite VC dimension.

This example shows that the number of parameters does not determine VC dimension. A class with just two real parameters can overfit arbitrarily many points. For learnability, one must restrict the frequency (e.g., via a complexity penalty) to obtain finite VC dimension.

For a hypothesis class \(\mathcal{H}\) and a positive integer \(n\), the growth function (or shatter coefficient) is defined as

It is the maximum number of distinct labelings that \(\mathcal{H}\) can generate on any set of \(n\) points. The growth function generalises the finite cardinality: for a finite class, \(\Pi_{\mathcal{H}}(n) \le |\mathcal{H}|\) for all \(n\). For infinite classes, \(\Pi_{\mathcal{H}}(n)\) may grow with \(n\), but its growth rate is controlled by the VC dimension.

Sauer–Shelah Lemma (to be proved later): If \(\operatorname{VCdim}(\mathcal{H}) = d < \infty\), then for all \(n \ge d\),

Thus, once \(n\) exceeds the VC dimension, the growth function becomes polynomial in \(n\) rather than exponential (\(2^n\)). This is the key combinatorial fact that enables uniform convergence for VC classes.

For \(n < d\), trivially \(\Pi_{\mathcal{H}}(n)\le 2^n\). The second inequality uses the well‑known binomial sum bound \(\sum_{i=0}^d \binom{n}{i} \le (en/d)^d\). This result shows that the number of distinct labelings on \(n\) points grows only polynomially in \(n\) once \(n\) exceeds the VC dimension, rather than exponentially. It is the single most important combinatorial property of VC classes and is the cornerstone of uniform convergence bounds.

The proof proceeds by induction on \(n+d\) and uses the fact that if \(\mathcal{H}\) shatters a set of size \(d+1\), then VCdim > d. For the induction step, one fixes a point, partitions \(\mathcal{H}\) into two subclasses (those that can be “cloned” with both labels on that point), and bounds the growth function recursively.

The empirical measure \(P_n = \frac{1}{n}\sum_{i=1}^n \delta_{X_i}\) places equal mass on each training point. The uniform deviation between empirical and true risk can be written as

where \(\ell_h(x)=\mathbf{1}_{h(x)\neq y}\) (or, in the realizable case, \(\mathbf{1}_{h(x)\neq f(x)}\)). For a VC class \(\mathcal{H}\) with \(\operatorname{VCdim}=d\), the growth function controls the empirical process. Specifically, the expected supremum of this difference is bounded by \(O(\sqrt{d/n})\) via symmetrization and the Sauer–Shelah lemma. This is the core of the Vapnik–Chervonenkis theory: finite VC dimension implies uniform Glivenko–Cantelli, i.e.,

and the rate is of order \(\sqrt{d/n}\). Thus, the empirical measure concentrates uniformly over the class.

This holds because any labeling of points \((x_i,y_i)\) that can be realized by functions in \(\mathcal{A}\) corresponds to a labeling of the \(x_i\) by \(\mathcal{H}\) after a flip depending on \(y_i\). Since \(y_i\) are fixed, the shattering capacity is unchanged. Consequently, all VC‑based uniform convergence bounds for the loss class directly translate to bounds on the classification risk, without any increase in complexity. This lemma justifies measuring complexity via the VC dimension of the hypothesis class itself.

Symmetrization is a technique to bound the expected supremum of an empirical process. Introduce a second independent sample \(S'=(X_1',\dots,X_n')\) drawn from the same distribution (the “ghost” sample). Then

By conditioning and using Jensen’s inequality, the expectation of the supremum over the original sample is bounded by the expectation of the supremum of the difference between two independent samples. Crucially, the right‑hand side depends only on the empirical discrepancies on \(2n\) points. Introducing Rademacher variables \(\sigma_i\in\{-1,+1\}\) independent of everything, we can further symmetrize to obtain

This is the Rademacher complexity of the loss class, which can then be bounded via the growth function and Massart's finite class lemma. Symmetrization thus converts the problem of controlling the gap between empirical and true risk into a purely combinatorial quantity over a fixed sample.

Rademacher random variables \(\sigma_1,\dots,\sigma_n\) are i.i.d. with \(\mathbb{P}(\sigma_i=+1)=\mathbb{P}(\sigma_i=-1)=1/2\), independent of the data. For a fixed sample \(S\), the empirical Rademacher complexity of a class \(\mathcal{F}\) is

Its expectation \(\mathfrak{R}_n(\mathcal{F}) = \mathbb{E}_S[\widehat{\mathfrak{R}}_n(\mathcal{F})]\) is the Rademacher complexity. It measures how well the class can fit random noise: if the class can match arbitrary sign patterns, the supremum will be large. The Rademacher complexity is directly linked to the growth function: for a class of binary functions with VC dimension \(d\), one can show \(\mathfrak{R}_n(\mathcal{F}) \le C\sqrt{d/n}\).

Rademacher complexities are one of the most flexible tools in learning theory, as they extend to real‑valued functions, unbounded losses, and can be computed or bounded for many practical model classes (e.g., neural networks, kernel machines).

Proof sketch. Using symmetrization (A4.111), the expected supremum is bounded by twice the Rademacher complexity of the loss class. For a binary function class of VC dimension \(d\), the Rademacher complexity can be bounded via Massart's finite class lemma: for any finite set of vectors in \(\{0,1\}^n\), the Rademacher average is at most \(\sqrt{2\log M / n}\) where \(M\) is the number of distinct projections. Using the Sauer–Shelah lemma, for a given sample, the number of distinct labelings is at most \((en/d)^d\). Thus the empirical Rademacher complexity is bounded by \(\sqrt{\frac{2d\log(en/d)}{n}}\), and taking expectation (with some additional handling of the logarithm) yields a bound of order \(\sqrt{d/n}\). The absolute constant \(C\) can be taken as something like \(\sqrt{2}\) plus a universal factor from the logarithm bound; specific values exist in the literature.

This follows from McDiarmid’s inequality (A4.35) because the uniform deviation satisfies the bounded differences property with constant \(1/n\). Thus, with probability at least \(1-\delta\), the deviation between its value and its expectation is at most \(\sqrt{\frac{\log(1/\delta)}{2n}}\). Adding the bound on the expectation from A4.113 yields the result. The two terms are of the same order \(O(\sqrt{d/n})\) when \(d\) dominates the log‑confidence term; in practice, the VC‑dependent term is the leading one.

Proof. Let \(h^*_{\mathcal{H}}\) be a minimiser of the true risk in \(\mathcal{H}\). Then

Applying the high‑probability VC inequality (A4.114) with a union bound adjustment (the factor 2 is absorbed into the constant) gives the stated bound. Thus, ERM over a VC class achieves excess risk of order \(O(\sqrt{d/n})\), which is minimax‑optimal for the agnostic case. This is the definitive generalisation of the finite‑class bound \(\sqrt{\log M / n}\) to the infinite setting, with \(\log M\) replaced by the VC dimension (up to logarithmic factors).

In practice, the VC dimension of \(\mathcal{H}\) may be unknown, or the learner may want to select from a hierarchy of classes \(\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots\), each with increasing capacity (e.g., polynomials of degree \(k\), neural networks with more layers). Structural Risk Minimization (SRM) is a method that automatically balances empirical fit against class complexity.

Given a sequence of hypothesis classes \(\{\mathcal{H}_k\}_{k\ge 1}\) with VC dimensions \(d_k\) (non‑decreasing), and a weighting \(w_k\) such that \(\sum_k w_k = 1\) (e.g., \(w_k = \frac{6}{\pi^2 k^2}\)), SRM selects a hypothesis \(\hat h\) from \(\bigcup_k \mathcal{H}_k\) that minimises the penalised empirical risk:

With a union bound over \(k\), one obtains an oracle inequality that simultaneously competes with the best hypothesis in each class, with a complexity penalty proportional to \(\sqrt{d_k/n}\). SRM thus provides an adaptive way to perform model selection without a priori knowledge of the right complexity. The technique is an ancestor of regularisation methods like weight decay and is closely tied to the bias–complexity tradeoff.

This theorem, due to Vapnik and Chervonenkis, crystallises the learning theory for binary classification. Finite VC dimension is both necessary and sufficient for learnability. Moreover, the sample complexity in the realizable case is \(\Theta\bigl(\frac{d + \log(1/\delta)}{\epsilon}\bigr)\) and in the agnostic case is \(\Theta\bigl(\frac{d + \log(1/\delta)}{\epsilon^2}\bigr)\). The equivalence of (2) and (3) shows that the realizable and agnostic settings are tied by the same combinatorial measure. The proof relies on the VC inequality (sufficiency) and the no‑free‑lunch argument (necessity).

Occam's razor, the principle that “simpler explanations are better,” finds a precise quantitative expression through VC theory. A hypothesis class with small VC dimension is “simple” in the sense of having limited capacity to fit random noise. The agnostic oracle inequality (A4.115) shows that the excess risk scales as \(\sqrt{\operatorname{VCdim}/n}\); thus, for a given sample size, a smaller VC dimension directly translates to a tighter bound on generalisation error.

However, a too‑simple class may suffer from high approximation error. The Structural Risk Minimization principle (A4.116) formally implements Occam's razor by adding a penalty proportional to \(\sqrt{\operatorname{VCdim}}\). The learner automatically favours simpler classes unless the data provide significant evidence that a more complex class yields a substantially better fit. This connection between combinatorial complexity and generalisation is the mathematical foundation of the bias–complexity tradeoff and justifies common practices like pruning decision trees, limiting network depth, and applying weight decay.

Proof sketch. Unlike the finite case, we cannot simply take a union bound over all hypotheses. Instead, we use the growth function and the fact that on a sample of size \(n\), the number of distinct behaviours is at most \(\Pi_{\mathcal{H}}(n) \le (e n / d)^d\). For a fixed bad hypothesis with error \(>\epsilon\), the probability it survives (makes zero mistakes on \(n\) i.i.d. draws) is \(\le (1-\epsilon)^n \le e^{-\epsilon n}\). However, we must bound the probability that some bad hypothesis in the infinite class has zero empirical error. Covering the class using the growth function on a double sample, one can show that with high probability, every hypothesis with true error \(>\epsilon\) makes at least one mistake on the training set, provided \(n\) is large enough. A classic argument (Vapnik–Chervonenkis) yields that with probability at least \(1-\delta\), the empirical error of every \(h\in\mathcal{H}\) is close to its true error, and the uniform deviation is bounded by \(O(\sqrt{d\log(n/d)/n})\). Solving for the sample size to ensure this deviation is at most \(\epsilon\) yields the claimed bound. The logarithmic dependence on \(1/\epsilon\) is characteristic of the realizable case (fast rate). More refined analysis gives the exact constant.

This theorem shows that VC classes are PAC learnable in the realizable setting with sample complexity scaling linearly in the VC dimension and only logarithmically in \(1/\epsilon\).

Proof idea. The lower bound is typically proved by constructing a distribution supported on a shattered set of size \(d\). For the realizable case, consider a uniform distribution over \(d\) points that are shattered by \(\mathcal{H}\). The true target function is chosen uniformly at random from the \(2^d\) possible labelings. An algorithm that sees only \(n\) examples cannot distinguish between the remaining possibilities, and any mistake on an unseen point contributes to the error. By a Fano or Assouad–Birgé type argument, one can show that unless \(n \ge c\, d/\epsilon\), the expected error is large. Similar arguments give the agnostic lower bound. Thus, the upper bounds from VC theory are optimal up to logarithmic factors, establishing the minimax optimality of the VC dimension as a complexity measure.

For a finite class \(\mathcal{H}\) with \(|\mathcal{H}|=M\), its VC dimension satisfies \(d \le \log_2 M\). The VC inequality (A4.114) gives a uniform bound of order \(\sqrt{d/n}\), while the direct Hoeffding+union bound gives \(\sqrt{\log M / n}\). Since \(d \le \log_2 M\), the VC bound may be slightly looser by a constant factor, but it still holds. In fact, for finite classes, the VC bound is never worse than \(\sqrt{\log_2 M / n}\) up to multiplicative constants.

More importantly, the VC theory unifies the treatment: the same inequality applies seamlessly to both finite and infinite classes. The quantity \(\log|\mathcal{H}|\) in finite class bounds is replaced by the VC dimension (times a log factor) in the infinite case. The connection is made exact through the Sauer–Shelah lemma: the growth function is polynomial in \(n\) with exponent \(d\), whereas a finite class trivially has growth function bounded by \(M\). The expected supremum of the empirical process is bounded by roughly \(\sqrt{\frac{d\log(n/d)}{n}}\), which matches the finite class bound \(\sqrt{\frac{\log M}{n}}\) up to the logarithmic factor when \(M\) is of order \(n^d\).

Thus, the VC inequality is the natural generalisation of the simple union‑bound approach, extending the concept of “effective number of hypotheses” from cardinality to combinatorial dimension.

Dudley's entropy integral provides a bound on the Rademacher complexity of a function class \(\mathcal{F}\) in terms of its metric entropy (covering numbers). Let \(\mathcal{F}\) be a class of functions from \(\mathcal{X}\) to \(\mathbb{R}\) with envelope \(1\) (i.e., \(\|f\|_\infty \le 1\)). For a sample \(x_1,\dots,x_n\), define the empirical \(L_2\) metric

Let \(\mathcal{N}(\mathcal{F}, d_n, \epsilon)\) be the covering number—the size of the smallest \(\epsilon\)-net. Then

For a VC class of binary functions, the covering number in the \(L_1\) (or \(L_2\)) metric at scale \(\epsilon\) is bounded by \((C/\epsilon)^{O(d)}\), so the entropy integral from 0 to 1 gives a factor \(\sqrt{d/n}\) (the integral of \(\sqrt{\log(1/\epsilon)}\) converges). Thus Dudley's inequality recovers the VC bound and generalises it to real‑valued classes. This is a powerful tool for analysing neural networks, kernel methods, and other infinite‑dimensional function spaces.

Chaining is a technique to bound the supremum of a stochastic process by approximating the index set at successively finer scales. Instead of a naive union bound over an \(\epsilon\)-net (which would give a suboptimal rate), chaining considers a sequence of nets \(\mathcal{N}_k\) with resolutions \(\epsilon_k = 2^{-k}\). We write any \(f\in\mathcal{F}\) as a telescoping sum of increments between successive approximations:

where \(f_k\) is the closest point in the net \(\mathcal{N}_k\). The process then decomposes into many smaller processes, and the overall supremum is bounded by summing the expected maxima at each scale. The key advantage is that each scale involves only a small number of increments, and the metric entropy at that scale controls the expected supremum.

Chaining leads to Dudley's entropy integral (A4.122) and can be refined via generic chaining (Talagrand) to yield sharp bounds involving the \(\gamma_2\) functional. For VC classes, chaining provides a more transparent proof of the uniform convergence bound and bridges the gap between the combinatorial VC argument and the empirical process viewpoint.

The VC dimension of affine halfspaces in \(\mathbb{R}^d\) is \(d+1\). The realizable sample complexity for learning a halfspace is therefore \(O\bigl(\frac{d \log(1/\epsilon) + \log(1/\delta)}{\epsilon}\bigr)\). In the agnostic setting, it is \(O\bigl(\frac{d + \log(1/\delta)}{\epsilon^2}\bigr)\).

Curse of dimensionality. If no additional structure is present, the required sample size grows linearly with the input dimension \(d\). For high‑dimensional problems (e.g., images with thousands of pixels), this suggests that learning a general halfspace is infeasible without an enormous training set. This matches the intuition that a generic linear classifier in very high dimensions can overfit.

The role of margin. In practice, linear classifiers (SVMs, logistic regression) often work well in high dimensions. This is because the data usually have a large margin. When the data are linearly separable with a margin \(\gamma > 0\), the effective capacity is much smaller—the fat‑shattering dimension scales as \(\min(d, 1/\gamma^2)\). Consequently, the sample complexity becomes \(O(1/\gamma^2 \cdot 1/\epsilon)\) rather than \(O(d/\epsilon)\). This explains why linear SVMs and other margin‑based methods can generalise well even when \(d\) is far larger than the sample size.

Implications for practice.

• Always check whether a margin exists; if not, consider dimensionality reduction or regularisation to shrink effective VC dimension.
• The bound \(d+1\) is a worst‑case; for a given distribution, the “effective” complexity can be much lower (data‑dependent VC bounds).
• For large‑margin problems, sample size requirements are dimension‑independent, a fact that drives the success of kernel methods and deep learning (via implicit biases).

VC theory provides a beautiful characterisation of learnability for binary classification, but it has limitations. It only directly handles the 0‑1 loss, leaving other important settings—regression with squared loss, classification with surrogate convex losses, and structured prediction—without a unified framework. Moreover, the VC dimension is a worst‑case combinatorial measure that can be too pessimistic for benign distributions or when the algorithm uses a large margin.

Rademacher complexity extends the theory to any bounded loss function and yields data‑dependent bounds that can adapt to the actual structure of the problem. Unlike the VC dimension, which depends only on the hypothesis class, Rademacher complexity can incorporate the training sample and the loss function, leading to tighter guarantees. It also connects seamlessly to convex optimisation and provides a direct tool for analysing kernel machines, neural networks, and boosting.

In short, Rademacher complexity is the modern language of statistical learning theory, and it underpins the analysis of most contemporary algorithms.

Let \(\mathcal{F}\) be a class of loss functions \(f : \mathcal{Z} \to [0,1]\), where \(\mathcal{Z} = \mathcal{X}\times\mathcal{Y}\). The true risk is \(R(f) = \mathbb{E}[f(Z)]\) and the empirical risk is \(\widehat{R}_n(f) = \frac{1}{n}\sum_{i=1}^n f(Z_i)\). Symmetrization bounds the expected supremum of the empirical process:

where \(\sigma_1,\dots,\sigma_n\) are independent Rademacher variables independent of the sample. The right‑hand side is (twice) the Rademacher complexity of the loss class. This symmetrization generalises the binary case (A4.111) to any bounded function class. The proof uses a ghost sample and Jensen’s inequality in the same way, with no dependence on the loss being 0‑1. Thus, the Rademacher complexity measures how well the function class can correlate with random noise—exactly the capacity that drives overfitting.

This is a data‑dependent measure: \(\widehat{\mathfrak{R}}_S(\mathcal{F})\) depends on the actual sample points. It captures the ability of \(\mathcal{F}\) to fit random signs, which is a proxy for how much the class can overfit. A class that can realise many sign patterns will have large Rademacher complexity. It can be computed or bounded for many common model classes (linear, kernel, neural networks) and is the central object in modern generalisation bounds.

Proof sketch. Apply symmetrization to bound the expected supremum, then use McDiarmid's inequality to concentrate the supremum around its expectation. The bounded differences condition holds with constant \(1/n\) because changing one \(z_i\) changes any \(f(z_i)\) by at most 1. This gives the first bound. For the second, replace \(\mathfrak{R}_n(\mathcal{F})\) with its empirical counterpart; McDiarmid again shows that the empirical Rademacher complexity concentrates around its mean, at the cost of an extra \(\sqrt{\frac{\log(1/\delta)}{2n}}\) term. These bounds are the foundation for analysing ERM and regularised algorithms: if the Rademacher complexity is small, uniform convergence holds and generalisation is guaranteed.

If all vectors are bounded in sup‑norm (i.e., \(|a_i|\le M\)), then \(\|a\|_2 \le M\sqrt{n}\), and the bound simplifies to \(M\sqrt{2\log|A|/n}\). For a finite function class with \(|f(z)|\le M\), the empirical Rademacher complexity satisfies \(\widehat{\mathfrak{R}}_S(\mathcal{F}) \le M\sqrt{2\log|\mathcal{F}|/n}\). Massart's lemma is the key technical tool that converts a cardinality into a Rademacher complexity bound. It is proved using Hoeffding's lemma and the fact that the maximum of \(M\) sub‑Gaussian random variables is bounded by \(\sqrt{2\log M}\) times the sub‑Gaussian parameter.

For a finite hypothesis class \(\mathcal{H}\) of size \(M\) and a loss function bounded in \([0,1]\), the loss class \(\mathcal{F} = \{\ell_h : h\in\mathcal{H}\}\) has \(|\mathcal{F}|\le M\). Massart's lemma immediately gives

Plugging this into the Rademacher generalisation bound (A4.128) recovers the familiar oracle inequality

up to constants and confidence terms. Thus, the Rademacher complexity framework seamlessly subsumes the finite‑class results. The advantage is that the same machinery extends to infinite classes where we can bound the Rademacher complexity via other means (e.g., via covering numbers or margin bounds).

Consider linear predictors \(\mathcal{H} = \{x \mapsto \langle w, x\rangle : \|w\|_2 \le W\}\) acting on inputs \(x\) with \(\|x\|_2 \le X\). For a loss function \(\phi\) applied to the margin, the Rademacher complexity can be bounded. For the linear function class itself (without loss), we have

This is derived by using the Cauchy–Schwarz inequality and the property \(\mathbb{E}[\|\sum \sigma_i x_i\|_2] \le \sqrt{\sum \|x_i\|_2^2}\). For the margin loss \(\ell(y \langle w, x\rangle)\) that is Lipschitz in the margin, the contraction principle (A4.132) transfers the bound to the loss class, giving a Rademacher complexity of order \(O(W X/\sqrt{n})\). This yields the standard SVM bound: the generalisation error of a large‑margin linear classifier scales as \(O(1/\sqrt{n})\) times the norm product \(WX/\sqrt{n}\), independent of the input dimension. This data‑dependent bound is far tighter than the VC dimension bound of \(O(\sqrt{d/n})\) when the margin is large.

This result, due to Ledoux and Talagrand, allows us to pass from the Rademacher complexity of the hypothesis class (e.g., linear functions) to that of the loss class (e.g., hinge loss, logistic loss) by simply multiplying by the Lipschitz constant. It is an essential tool: one first bounds the complexity of the predictor class (which is often easier) and then applies the contraction principle to obtain a bound for the actual loss. For example, the hinge loss is 1‑Lipschitz, so the Rademacher complexity of the loss class is at most that of the margin class. For the 0‑1 loss, the contraction principle does not apply directly (it is not Lipschitz), but surrogate losses provide the link.

Global Rademacher complexity gives a bound of order \(1/\sqrt{n}\), which corresponds to the slow rate. To obtain fast rates (\(O(1/n)\)) under low‑noise or margin conditions, we need a more refined analysis. Local Rademacher complexity restricts attention to a small subset of the function class: those functions with small excess risk (or small variance).

For a function class \(\mathcal{F}\) and a radius \(r>0\), define the localised class \(\mathcal{F}_r = \{f\in\mathcal{F} : \mathbb{E}[f^2] \le r\}\). The local Rademacher complexity is \(\mathfrak{R}_n(\mathcal{F}_r)\). If the variance of the loss is small for near‑optimal functions (self‑bounding), the effective class size shrinks. One can then solve a fixed‑point equation to find the critical radius \(r_n^*\) such that \(\mathfrak{R}_n(\mathcal{F}_{r_n^*}) \approx r_n^*\). This critical radius determines the excess risk rate. Under strong convexity or noise conditions, the rate becomes fast (\(1/n\)). This technique bridges Rademacher complexity and the fast‑rate results we proved for finite classes using Bernstein's inequality.

The critical radius \(r_n^*\) is the solution to the inequality \(\mathfrak{R}_n(\mathcal{F}_r) \le r\), where \(\mathcal{F}_r\) is the local class of functions with variance at most \(r\). Under a Bernstein condition (variance bounded by \(c\) times excess risk), the critical radius yields an excess risk bound of order \(r_n^*\).

For a VC class with Tsybakov noise exponent \(\alpha\), the local Rademacher complexity analysis recovers the interpolated rate \(\bigl(\frac{1}{n}\bigr)^{\frac{\alpha+1}{\alpha+2}}\). For \(\alpha\to\infty\) (Massart hard margin), the critical radius is of order \(1/n\), giving the fast rate. This approach unifies fast rates, margin conditions, and Rademacher complexity: the critical radius automatically adapts to the problem's intrinsic difficulty. Moreover, the same technique applies to linear classes, kernel methods, and neural networks, where the local Rademacher complexity can be bounded via concentration properties of the feature space.

For a reproducing kernel Hilbert space (RKHS) \(\mathcal{H}_K\) with kernel \(K\), the class of functions with bounded norm \(\mathcal{F} = \{f\in\mathcal{H}_K : \|f\|_{\mathcal{H}_K} \le B\}\) has a simple Rademacher complexity bound. Using the reproducing property and the Cauchy–Schwarz inequality, one obtains

If the kernel is bounded (e.g., Gaussian kernel with \(K(x,x)\le 1\)), this becomes \(B/\sqrt{n}\). For a bounded loss, the contraction principle then yields an excess risk bound of order \(O(B/\sqrt{n})\), independent of the dimension of the feature space. This explains the good generalisation of kernel methods like SVM: they learn in an infinite‑dimensional feature space without suffering from the curse of dimensionality, because the Rademacher complexity is controlled by the norm bound \(B\), not the ambient dimension.

Moreover, this analysis extends to neural networks in their “kernel regime” (NTK) and to deep learning via norm‑based capacity measures (e.g., path norm, spectral norm). Rademacher complexity provides a unified lens for understanding generalisation across a wide variety of model classes.

Unlike the VC dimension, which is a purely combinatorial property of the hypothesis class \(\mathcal{H}\), the Rademacher complexity depends on the training sample \(S = (z_1,\dots,z_n)\) and on the loss function. It measures how well the class can fit random noise on the actual data, making it a much finer gauge of overfitting potential.

For a fixed sample, the empirical Rademacher complexity \(\widehat{\mathfrak{R}}_S(\mathcal{F})\) can be computed exactly or bounded using geometric properties of the feature vectors. As more data arrive, the empirical measure approaches the population distribution, and the Rademacher complexity adapts: if the data lie on a low‑dimensional manifold, the complexity will be correspondingly small. This data‑dependence yields tighter, more realistic generalisation bounds than the worst‑case VC theory.

Many practical model‑selection criteria (e.g., margin bounds for SVM, norm‑based bounds for neural networks) are essentially data‑dependent upper bounds on the Rademacher complexity, providing a direct bridge from theory to algorithm design.

Symmetrization is the fundamental probabilistic step that connects the supremum of the empirical process to the Rademacher complexity. For a class \(\mathcal{F}\) of functions bounded in \([0,1]\),

This inequality replaces the unknown true risk \(R(f)\) with a second independent sample (ghost sample) and then uses Jensen’s inequality together with the fact that the difference of two i.i.d. samples has the same distribution as a Rademacher‑weighted sum. The result is a purely data‑dependent quantity—the expected maximum correlation with random signs—that controls the generalisation gap.

Symmetrization therefore transforms the problem of bounding the deviation between empirical and true risk into a problem of bounding the Rademacher complexity, a quantity that can be attacked with combinatorial, geometric, and functional‑analytic tools. It is the central bridge from empirical process theory to learning bounds.

Instead of Rademacher variables \(\sigma_i \in \{\pm 1\}\), one can use independent standard Gaussian variables \(g_i \sim \mathcal{N}(0,1)\) to define the Gaussian complexity:

Gaussian complexity is often easier to compute or bound for many classes, especially those arising from kernel methods or neural networks, because Gaussian processes have a rich theory. Moreover, the Gaussian setting connects directly to the geometry of the function class in Hilbert space.

Thanks to the similarity between the tails of Rademacher and Gaussian variables, the two complexities are equivalent up to a logarithmic factor (see A4.140). Thus, bounds on Gaussian complexity immediately transfer to Rademacher complexity, and vice‑versa, making the choice between them a matter of convenience.

In particular, for \(p=1\), \(\mathbb{E}[|\sum \sigma_i a_i|] \asymp \sqrt{\sum a_i^2}\). Khintchine's inequality shows that Rademacher sums behave like the Euclidean norm of the coefficient vector, up to universal constants. This property is crucial for bounding Rademacher complexities: it allows one to replace a supremum over the class with geometric quantities such as the width in \(L_2\).

Because Gaussian variables also satisfy a similar moment equivalence, Khintchine's inequality underpins the comparison between Rademacher and Gaussian complexities. The constants \(A_p, B_p\) are known explicitly; for instance, for \(p=2\), equality holds with \(A_2=B_2=1\).

Rademacher and Gaussian complexities are tightly related. Using a symmetrization argument and the fact that a Gaussian variable can be expressed as \(g = \mathbb{E}[\sigma] \cdot \tilde g\) (where \(\sigma\) is Rademacher independent of \(\tilde g\) which is half‑normal), one can show that for any function class \(\mathcal{F}\),

Thus, the two complexities are equivalent up to a logarithmic factor in the sample size. In many cases of interest, the logarithmic gap can be removed, and the complexities are of the exact same order. This equivalence means that the choice between Rademacher and Gaussian complexity is largely one of analytical convenience: Gaussian processes often enjoy rotational invariance (useful for kernel classes), while Rademacher variables are bounded and thus easier to handle with concentration inequalities.

In practice, bounds on the Gaussian complexity of linear and kernel classes are often derived first, then transferred to Rademacher complexity via the comparison inequality, yielding generalisation bounds for ERM with Lipschitz losses.

The contraction principle (Ledoux–Talagrand) is the fundamental tool that relates the Rademacher complexity of a loss class to that of the underlying predictor class. Let \(\phi:\mathbb{R}\to\mathbb{R}\) be a Lipschitz function with constant \(L\) and \(\phi(0)=0\). Then for any sample \(S\) and any set of real‑valued functions \(\mathcal{G}\),

This inequality holds for the empirical Rademacher complexity, and by taking expectations, for the expected Rademacher complexity as well. It allows us to separate the analysis: first bound the complexity of the predictor class (e.g., linear functions, kernel expansions, neural networks) and then multiply by the Lipschitz constant of the loss function to obtain a bound for the empirical risk minimisation problem.

Common loss functions and their Lipschitz constants:

• Hinge loss: \(\phi(t)=\max(0,1-t)\) — Lipschitz constant \(1\).
• Logistic loss: \(\phi(t)=\log(1+e^{-t})\) — Lipschitz constant \(1\).
• Exponential loss: \(\phi(t)=e^{-t}\) — not globally Lipschitz, but locally bounded analysis possible.
• Squared loss (within a bounded interval) is also Lipschitz.

Thus, for a wide range of learning algorithms, the Rademacher complexity of the loss class is at most a constant multiple of the Rademacher complexity of the hypothesis class, making the theory highly modular.

We now have a complete template for proving generalisation bounds using Rademacher complexity.

1. Symmetrization (A4.137) connects the supremum of the empirical process to the Rademacher complexity of the loss class.
2. McDiarmid's inequality concentrates the supremum around its mean, giving a high‑probability bound.
3. Contraction principle (A4.141) reduces the loss class complexity to that of the predictor class, times the Lipschitz constant of the loss.
4. Compute or bound the Rademacher complexity of the predictor class using tools like Massart's lemma (for finite classes), Khintchine's inequality (for linear classes), covering numbers and chaining (for general classes), or kernel properties.

The resulting uniform generalization bound states: with probability at least \(1-\delta\), for all \(h\) in \(\mathcal{H}\),

where \(\mathcal{F}\) is the loss class. If the Rademacher complexity decays as \(O(1/\sqrt{n})\) (the typical rate for VC classes, linear classes with bounded norms, etc.), then the excess risk of ERM is of order \(O(1/\sqrt{n})\). With local Rademacher analysis and margin or noise conditions, one can improve this to fast rates of order \(O(1/n)\).

This unified framework—from symmetrization through contraction to explicit complexity bounds—constitutes the modern core of statistical learning theory, capable of handling a vast array of models and losses with minimal assumptions beyond boundedness and i.i.d. sampling.

The empirical process indexed by a function class \(\mathcal{F}\) is the collection of random variables

where \(\widehat{R}_n(f)=\frac{1}{n}\sum_{i=1}^n f(Z_i)\) and \(R(f)=\mathbb{E}[f(Z)]\). Viewing learning through the lens of empirical process theory unifies finite‑sample and asymptotic analysis. The central objects—the supremum \(\sup_{f\in\mathcal{F}}|\mathbb{G}_n(f)|\), its expectation, and its weak limit—encode all generalisation properties of ERM and related estimators.

From this viewpoint, uniform convergence is just the statement that \(\sup_{f\in\mathcal{F}}|\mathbb{G}_n(f)|/\sqrt{n} \to 0\) in probability. Results such as Glivenko–Cantelli and Donsker theorems classify classes \(\mathcal{F}\) by the behaviour of the empirical process, directly dictating whether learning is possible and at what rate. The empirical process perspective connects learning theory to deep areas of probability theory, including concentration of measure, isoperimetry, and functional limit theorems.

A function class \(\mathcal{F}\) satisfies the Uniform Law of Large Numbers (ULLN) if

This is the minimal requirement for empirical risk minimisation to be consistent: the empirical risk must converge uniformly to the true risk so that the minimiser of the former approaches the minimiser of the latter. For binary classification with 0‑1 loss, the ULLN holds if and only if the hypothesis class has finite VC dimension. More generally, for a class of bounded functions, the ULLN is equivalent to the class being Glivenko–Cantelli.

The ULLN is the bridge from asymptotic statistics (classical consistency) to learning theory: it guarantees that with enough data, the empirical landscape accurately reflects the true risk landscape, making data‑driven model selection trustworthy.

A class \(\mathcal{F}\) of measurable functions is called a Glivenko–Cantelli class (for the distribution \(P\)) if the ULLN holds:

For a class to be Glivenko–Cantelli, it must not be too complex. Finite entropy conditions (e.g., a finite bracketing number in \(L_1(P)\)) or finite VC dimension for binary indicator functions are sufficient. The classical Glivenko–Cantelli theorem for the empirical distribution function is the prototypical example: the class of indicators \(\{(-\infty, t] : t\in\mathbb{R}\}\) is Glivenko–Cantelli. In learning theory, Glivenko–Cantelli classes are exactly those for which ERM is consistent in the sense that \(R(\hat h_n) \to \inf_{h\in\mathcal{H}} R(h)\) in probability. Thus, the study of Glivenko–Cantelli classes directly characterises the possibility of learning from data.

A class \(\mathcal{F}\) is a Donsker class if the empirical process \(\mathbb{G}_n = \sqrt{n}(\widehat{R}_n - R)\) converges weakly in the space of bounded functions \(\ell^\infty(\mathcal{F})\) to a tight Gaussian process \(\mathbb{G}\) with covariance structure \(\operatorname{Cov}(\mathbb{G}(f),\mathbb{G}(g)) = \mathbb{E}[f(Z)g(Z)] - \mathbb{E}[f(Z)]\mathbb{E}[g(Z)]\).

Donsker's theorem for classes of functions generalises the central limit theorem to infinite‑dimensional spaces. A Donsker class automatically satisfies the ULLN (Glivenko–Cantelli), but the converse is false: a class can be Glivenko–Cantelli without being Donsker. Donsker classes have finite uniform entropy integral (e.g., for VC classes the entropy integral converges), which implies a rate of concentration of order \(1/\sqrt{n}\). In learning theory, Donsker classes allow the construction of asymptotic confidence intervals for the true risk and enable the analysis of more refined properties like the asymptotic distribution of the excess risk of ERM.

The weak convergence \(\mathbb{G}_n \rightsquigarrow \mathbb{G}\) in \(\ell^\infty(\mathcal{F})\) means that for any bounded, continuous functional \(F\) on \(\ell^\infty(\mathcal{F})\), \(\mathbb{E}[F(\mathbb{G}_n)] \to \mathbb{E}[F(\mathbb{G})]\). A key sufficient condition for weak convergence is that the class \(\mathcal{F}\) is totally bounded in the \(L_2(P)\) metric and satisfies an entropy condition (e.g., \(\int_0^1 \sqrt{\log \mathcal{N}(\mathcal{F}, L_2, \epsilon)}\, d\epsilon < \infty\)).

For VC classes of indicator functions, the empirical process converges weakly to a Gaussian process. This fact underpins the validity of bootstrap and permutation tests in high‑dimensional statistics. In machine learning, it justifies the use of asymptotic approximations for the excess risk (e.g., the sampling distribution of the test error of a trained classifier). However, non‑asymptotic (finite‑sample) bounds are often preferred because the asymptotics can be unreliable for small sample sizes relative to the complexity.

The concentration of measure is the geometric principle that a well‑behaved function of many independent random variables is sharply concentrated around its mean. It underlies all non‑asymptotic bounds in learning theory. Classic examples include:

• Hoeffding's inequality (concentration of sums of bounded independent variables).
• McDiarmid's inequality (concentration of functions with bounded differences).
• Talagrand's inequality (concentration of supremum of empirical processes).

Concentration inequalities typically yield exponential tail bounds: \(\mathbb{P}(|X - \mathbb{E}[X]| \ge t) \le 2e^{-c t^2}\). This is far stronger than the polynomial tails from Chebyshev's inequality, and it is exactly what makes PAC learning possible—the confidence parameter \(\delta\) appears logarithmically, allowing high‑confidence statements with a modest cost in sample size.

The phenomenon is deeply connected to isoperimetric inequalities in high‑dimensional geometry: the majority of the mass of a high‑dimensional distribution lies in a thin shell around the mean, making large deviations exponentially rare.

Isoperimetric inequalities relate the boundary measure of a set to its volume. In the context of concentration of measure, they imply that if a set has probability at least \(1/2\), then its metric neighbourhood has probability exponentially close to 1. This is the driving mechanism behind concentration.

For product measures (e.g., i.i.d. samples), the concentration property is extremely strong: any set of product measure at least \(1/2\) is such that its \(t\)-neighbourhood (in Hamming or \(L_2\) distance) has measure at least \(1 - e^{-c t^2}\). This yields McDiarmid’s inequality and Talagrand’s inequality as corollaries. The isoperimetric approach, pioneered by Talagrand, provides a unifying perspective on concentration for empirical processes and is central to proving sharp uniform bounds for complex function classes.

This is a far‑reaching generalisation of Bernstein's inequality to the supremum of empirical processes. It incorporates both a variance term \(v\) and a sub‑exponential correction. In learning theory, Talagrand's inequality is the workhorse for proving fast rates and sharp oracle inequalities. It leads to bounds where the complexity penalty is proportional to the variance, allowing adaptive rates that improve with the noise level. The inequality was a breakthrough that revitalised empirical process theory and placed it on a firm concentration foundation.

Bousquet's inequality refines the constants in Talagrand's bound and is particularly useful in learning theory because it explicitly separates the sub‑Gaussian and sub‑exponential components. It is often the starting point for deriving local Rademacher complexity bounds and fast rates for ERM. The term \(v\) involves the supremum of the sum of squared functions, which, under a noise condition, is proportional to the excess risk itself, yielding self‑bounding and fast rates.

Klein's inequality (in the context of empirical processes) is a refined concentration bound for the supremum of an empirical process that combines the sharp variance‑dependent terms of Bousquet with a robust entropy integral approach. It states that for a class \(\mathcal{F}\) with bounded envelope,

where \(\sigma^2 = \sup_{f\in\mathcal{F}} \operatorname{Var}(f(Z))\). This inequality explicitly trades off the complexity (via covering numbers at scale \(\sigma\)) with the noise level \(\sigma\). When the variance is small, the bound becomes much smaller than the global entropy integral, leading to fast rates. Klein's inequality is a powerful tool for establishing minimax‑optimal rates for ERM under Tsybakov noise and margin conditions. It unifies the entropy integral method with the variance adaptivity pioneered by Talagrand.

A local empirical process is the empirical process restricted to a small subset of the function class, typically a ball around the optimal function or the set of functions with small variance (or small excess risk). Localisation is the key technique for proving fast rates. Instead of controlling \(\sup_{f\in\mathcal{F}} |\widehat{R}_n(f) - R(f)|\), one controls the process over \(\mathcal{F}_\delta = \{f\in\mathcal{F}: \mathbb{E}[f^2] \le \delta\}\).

The local Rademacher complexity \(\mathfrak{R}_n(\mathcal{F}_\delta)\) and the critical radius \(r_n^*\) (the solution of \(\mathfrak{R}_n(\mathcal{F}_r) \le r\)) directly determine the convergence rate. Bounds on the local empirical process using Talagrand's or Bousquet's inequality lead to an oracle inequality where the rate adapts to the unknown variance structure. This framework elegantly unifies fast rates for classification under margin conditions, regression with squared loss under low noise, and the theory of penalised estimators. Localisation is the modern cornerstone of sharp statistical learning guarantees.

All previous results assume that the training sample consists of i.i.d. draws from a fixed distribution. However, many real‑world data sources—time series, financial data, speech, and video—exhibit temporal dependence. Strong mixing (or \(\alpha\)-mixing) is a widely used condition that quantifies the decay of dependence between past and future observations.

A stationary sequence \((Z_t)_{t\in\mathbb{Z}}\) is \(\alpha\)-mixing if

where \(\mathcal{F}_a^b\) is the \(\sigma\)-algebra generated by \((Z_a,\dots,Z_b)\). The coefficients \(\alpha_k\) measure the total variation distance between the joint distribution of blocks separated by lag \(k\) and the product of their marginals. If \(\alpha_k \to 0\), the process is asymptotically independent.

Implications for learning. Under mixing conditions, concentration inequalities (such as McDiarmid's for mixing sequences, or Bernstein inequalities for \(\alpha\)-mixing processes) still hold with a penalty that depends on the mixing rate. The effective sample size is reduced, and uniform convergence bounds remain valid as long as the complexity of the hypothesis class is not too large relative to the mixing rate. Extensions of VC theory and Rademacher complexity to mixing processes exist, guaranteeing PAC‑style bounds for ergodic sources.

The central object of uniform convergence theory is the empirical process supremum

This single random variable controls the generalisation performance of all functions in the class simultaneously. Key facts:

• Finite classes: Hoeffding's inequality plus union bound yields \(\Delta_n = O_P(\sqrt{\log|\mathcal{F}| / n})\).
• VC classes: \(\Delta_n = O_P(\sqrt{\operatorname{VCdim}(\mathcal{H}) / n})\) (up to logarithmic factors).
• General bounded losses: Rademacher complexity and symmetrization give \(\mathbb{E}[\Delta_n] \le 2\mathfrak{R}_n(\mathcal{F})\); concentration via McDiarmid then yields high‑probability bounds.
• Localisation: Restricting \(\mathcal{F}\) to functions with small variance yields fast rates (Talagrand, Bousquet, Klein).

The entire edifice of statistical learning theory—from PAC bounds to oracle inequalities—is built around the control of \(\Delta_n(\mathcal{F})\). Every capacity measure (VC dimension, growth function, covering numbers, Rademacher complexity) ultimately bounds this supremum, either in expectation or with high probability.

Symmetrization is the technique that introduces an independent ghost sample \(S' = (Z_1',\dots,Z_n')\) drawn from the same distribution. The key inequality is

Because \(Z_i\) and \(Z_i'\) are i.i.d., the random variable \(\epsilon_i = \operatorname{sign}(f(Z_i) - f(Z_i'))\) is symmetric and, conditioned on the pairs, has the same distribution as a Rademacher variable. This leads to

where \(\sigma_i\) are independent Rademacher. Symmetrization thus converts the expected supremum of the deviation into the Rademacher complexity. The technique is applicable to any bounded function class and does not require independence of coordinates, only of the sample points. It is the central bridge from empirical process control to data‑dependent complexity measures and is the foundation for all Rademacher‑based generalisation bounds.

A Rademacher process is a stochastic process indexed by a function class \(\mathcal{F}\), defined by

where \(\sigma_1,\dots,\sigma_n\) are independent Rademacher variables independent of the data \(Z_1,\dots,Z_n\). The empirical Rademacher complexity \(\widehat{\mathfrak{R}}_S(\mathcal{F})\) is the expected supremum of this process (over the Rademacher randomness, conditionally on \(S\)).

The Rademacher process captures the ability of \(\mathcal{F}\) to correlate with pure noise. Its behaviour is governed by the geometry of the set \(\{(f(Z_1),\dots,f(Z_n)) : f\in\mathcal{F}\} \subset \mathbb{R}^n\). For a fixed sample, this is a finite set (if \(\mathcal{F}\) is finite) or a subset of \(\mathbb{R}^n\). The supremum of the Rademacher process can be bounded using:

• Massart's lemma for finite sets, giving a \(\sqrt{\log|\mathcal{F}|/n}\) bound.
• Dudley's entropy integral and chaining for infinite sets, bounding the process by the metric entropy of \(\mathcal{F}\) under the empirical \(L_2\) metric.
• Khintchine's inequality to relate the Rademacher process to Gaussian processes.

Thus, the Rademacher process is the explicit random object whose supremum determines the generalisation gap, and bounding it is the central technical challenge in modern learning theory.

Proof idea. The proof uses induction on the number of points, applying the following one‑dimensional inequality: for any \(a,b\in\mathbb{R}\),

When integrating over \(\sigma_i\), the convexity of the supremum and the Lipschitz property allow a sequential symmetrisation. A modern proof uses the fact that the Rademacher process can be represented as a Gaussian process after appropriate conditioning and then applies Slepian's lemma, but the original Talagrand proof is more combinatorial.

Extension to vector‑valued functions. The contraction principle also holds when \(\phi\) acts component‑wise on vector‑valued functions, with the Lipschitz constant measured in the Euclidean norm, provided the Rademacher sums are taken with vector inner products.

Importance for learning. This inequality decouples the loss function from the hypothesis class. To bound the Rademacher complexity of the loss class \(\{\ell(h(\cdot),\cdot) : h\in\mathcal{H}\}\), it suffices to verify that the loss is Lipschitz in the prediction and then bound the Rademacher complexity of the predictor class \(\mathcal{H}\). This modularity is essential for analysing SVMs, neural networks, and any algorithm using a surrogate convex loss. The contraction principle is one of the most used tools in modern generalisation bounds.

In penalised empirical risk minimisation, a complexity penalty is added to the training error to discourage overly complex hypotheses. The estimator is

where \(\Omega:\mathcal{H}\to\mathbb{R}^+\) measures the “size” of \(h\) (e.g., a norm in a linear space) and \(\lambda>0\) is a regularisation parameter. Penalised ERM encompasses ridge regression, the Lasso, support vector machines, and neural network training with weight decay. It directly implements the bias–complexity tradeoff by making it costly to use high‑capacity hypotheses. Choosing \(\lambda\) appropriately (via cross‑validation or theory) balances approximation error and estimation error.

From a theoretical standpoint, penalised ERM can be analysed using Rademacher complexity or VC dimension, and often yields oracle inequalities showing that the risk is close to the minimum achievable by any element of \(\mathcal{H}\) with controlled norm.

Structural Risk Minimisation (SRM) is a systematic procedure for model selection when a nested family of hypothesis classes \(\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots\) is given, each with increasing capacity (e.g., VC dimension \(d_k\) increasing). SRM selects a hypothesis by minimising a penalised empirical risk:

where \(w_k\) are positive weights summing to 1 (e.g., \(w_k = \frac{6}{\pi^2 k^2}\)) and \(C\) is a constant depending on the confidence \(\delta\). A union bound over the classes, together with the VC inequality for each class, yields an oracle inequality: with high probability,

SRM automatically balances the approximation error (decreasing with \(k\)) against the estimation error (increasing with \(d_k\)), without prior knowledge of the optimal complexity. It is the theoretical foundation for many practical methods like cross‑validation, information criteria, and regularisation path selection.

The Akaike Information Criterion (AIC) and the Bayesian Information Criterion (BIC) are classical model selection tools. In statistical learning theory, they can be reinterpreted as approximations to SRM penalties for particular hypothesis classes.

For a parametric class of dimension \(d\) (number of free parameters), under the log‑likelihood loss and assuming a well‑specified model, the AIC penalty is \(2d/n\) and the BIC penalty is \(d\log n / n\). From an SLT viewpoint, the VC dimension often plays the role of the parameter count, but for well‑behaved parametric classes, \(\operatorname{VCdim} \approx d\). Thus, a VC‑based penalty of \(\sqrt{d/n}\) (agnostic case) differs from the AIC/BIC penalties, which are derived from asymptotic expansions of the log‑likelihood. However, in the large‑sample limit, all consistent model selection criteria trade off bias and complexity in a similar spirit. SLT refines these by providing non‑asymptotic bounds and extending them to infinite‑dimensional spaces where parameter counting fails.

The Minimum Description Length (MDL) principle views learning as a coding problem: given a dataset, the best hypothesis is the one that leads to the shortest description (encoding) of the data. The total description length is the sum of the code length for the hypothesis (model complexity) plus the code length for the data given the hypothesis (fit).

Mathematically, if \(L(h)\) is a prefix code length for \(h\) and \(L(D|h)\) is the code length for data \(D\) given \(h\), the MDL principle selects

Under the Shannon–Kraft–McMillan inequality, \(L(h) = -\log \pi(h)\) for some probability distribution \(\pi\) over \(\mathcal{H}\) (a prior), and the term \(L(D|h)\) is essentially the negative log‑likelihood. Thus MDL is equivalent to maximum a posteriori (MAP) estimation with a prior \(\pi\). SLT connects MDL to SRM: for a finite \(\mathcal{H}\), using a uniform prior yields \(L(h) = \log|\mathcal{H}|\), which matches the \(\log|\mathcal{H}|/n\) complexity penalty. For infinite classes, MDL leads to two‑part codes where the description length depends on the VC dimension or metric entropy, again bridging coding and generalisation.

Occam’s razor—the principle that simpler explanations are preferable—finds rigorous justification in statistical learning theory. The PAC bounds and oracle inequalities all show that excess risk scales with a complexity measure (VC dimension, Rademacher complexity) divided by \(\sqrt{n}\). Thus, for a fixed amount of data, a smaller complexity class guarantees a tighter error bound. SRM and penalised ERM are the formal implementations: they explicitly penalise complexity, leading the learner to automatically favour simpler hypotheses unless the data strongly support a more complex one.

However, the razor must be applied with care: a too‑simple class can suffer high approximation error. The correct interpretation is not “always choose the simplest model,” but “choose the simplest model that explains the data sufficiently well, as measured by an appropriate complexity penalty.” The theory provides the exact form of the penalty, turning a philosophical principle into a quantitative tool.

In many machine learning algorithms, regularisation is added to the loss function to control the complexity of the learned predictor. Common examples:

• Ridge regression: \(\|w\|_2^2\) penalty, which bounds the Euclidean norm and thus the Rademacher complexity of linear classes (A4.131).
• Lasso: \(\|w\|_1\) penalty, which encourages sparsity and can yield fast rates when the true predictor is sparse.
• SVM: \(\|w\|_2^2\) penalty with hinge loss, enforcing a large margin—the effective capacity is proportional to \(1/\gamma^2\), where \(\gamma\) is the margin.
• Weight decay in neural networks: \(\ell_2\) penalty on all weights, controlling the spectral norm and hence the Rademacher complexity of the network.

From the SLT viewpoint, regularisation implicitly reduces the effective hypothesis class to those with small norm. The Rademacher complexity of the restricted class is proportional to the norm bound divided by \(\sqrt{n}\), so the penalty in the objective corresponds exactly to the complexity term in the generalisation bound. Thus, regularisation is not merely a heuristic but a principled way to enforce the bias–complexity tradeoff and guarantee good generalisation.

Algorithmic stability is a property of a learning algorithm \(\mathcal{A}\): when the training set is modified by removing or replacing a single example, the output hypothesis does not change much. A common definition is uniform stability: an algorithm has stability \(\beta\) if for any two samples \(S\) and \(S'\) differing in exactly one point,

For a stable algorithm, one can prove generalisation bounds without explicit complexity measures. A classic result: if an algorithm has uniform stability \(\beta\) (which typically scales as \(1/n\)), then with high probability,

Stability is a complementary approach to uniform convergence; it applies directly to the algorithm rather than the hypothesis class. Many regularised ERM procedures (e.g., SVM, Tikhonov regularisation) are uniformly stable with \(\beta = O(1/(\lambda n))\), where \(\lambda\) is the regularisation parameter. This connection ties regularisation to generalisation without needing VC or Rademacher arguments.

Leave‑one‑out cross‑validation (LOOCV) estimates the risk of an algorithm by repeatedly training on all but one data point and testing on the held‑out point. Its estimate is

where \(S^{-i}\) is the sample with the \(i\)-th point removed. LOOCV is nearly unbiased for the expected risk of an algorithm trained on \(n-1\) points. More importantly, for stable algorithms, the LOOCV error and the empirical error are close, and the difference between LOOCV and true risk can be bounded via stability arguments. In the SLT framework, LOOCV serves as a practical, data‑dependent model selection tool that approximates the ideal penalty in SRM when the theoretical complexity penalty is unknown or too conservative. It is a cornerstone of model selection in practice.

The PAC‑Bayes framework provides generalisation bounds for randomized classifiers. Instead of selecting a single hypothesis \(h\), the learner chooses a distribution \(\rho\) over \(\mathcal{H}\). The true risk and empirical risk of \(\rho\) are defined by averaging over \(h\):

This bound involves the KL divergence between the chosen posterior \(\rho\) and the prior \(\pi\); the more \(\rho\) deviates from \(\pi\), the larger the penalty. PAC‑Bayes bounds are remarkably tight and often lead to the optimal rates for many problems. They are especially useful for analysing ensemble methods (bagging, boosting) and for deriving margin bounds for neural networks.

The PAC‑Bayes bound requires the prior \(\pi\) to be chosen before seeing the data. Using a data‑dependent prior (e.g., one obtained from a first run of ERM) without care can invalidate the bound. However, techniques exist to make priors data‑dependent by, for example, splitting the sample into two parts: one to construct the prior, the other to apply the PAC‑Bayes bound. This yields valid, though sometimes slightly looser, guarantees.

More sophisticated methods, such as differential privacy or stability‑based arguments, allow the prior to depend on the whole dataset while preserving the validity of the bound, up to a small correction. These data‑dependent PAC‑Bayes bounds are powerful tools for analysing modern algorithms (e.g., neural networks trained with SGD) because one can choose the prior based on the weight distribution or on the training dynamics, leading to generalisation bounds that are far smaller than worst‑case VC‑dimension bounds.

A recent line of work studies generalisation through the lens of mutual information between the training data and the output hypothesis. For a randomized algorithm \(\mathcal{A}\) that takes a sample \(S\) and outputs \(W = \mathcal{A}(S)\), the expected generalisation gap can be bounded as

where \(I(S;W)\) is the mutual information between the sample and the learned parameters. If the algorithm reveals little about any individual training point (i.e., small mutual information), it generalises well. This framework unifies several earlier approaches: for ERM over a finite class, the mutual information is at most \(\log|\mathcal{H}|\); for stable algorithms, the mutual information is small. Information‑theoretic bounds have been applied to understand the generalisation of deep neural networks and the role of stochastic gradient descent, offering a new, flexible tool for modern machine learning theory.

The information‑theoretic approach to generalisation bounds the expected gap between training and test error using the mutual information between the training sample \(S\) and the algorithm’s output \(W = \mathcal{A}(S)\). For a randomized algorithm and a loss bounded in \([0,1]\), a fundamental result states

where \(I(S;W) = \operatorname{KL}(P_{S,W} \| P_S \otimes P_W)\) is the mutual information. The proof uses the Donsker–Varadhan variational representation of KL divergence and a symmetrisation argument. This inequality reveals that algorithms that reveal little information about the individual training examples (i.e., have low mutual information) generalise well. For instance, a deterministic ERM over a finite class \(\mathcal{H}\) of size \(M\) has \(I(S;\hat h) \le \log M\), yielding the classic \(\sqrt{\log M / n}\) bound. For stochastic gradient descent with Gaussian noise, the mutual information can be bounded by the sum of noise variances over iterations.

Extensions include conditioning on the hypothesis (individual sample mutual information), and connections to PAC‑Bayes via the fact that \(\operatorname{KL}(\rho\|\pi) = I(S;W)\) when \(\pi\) is the marginal distribution of \(W\). Thus, information‑theoretic bounds unify stability, PAC‑Bayes, and VC theory under a single umbrella, making them especially attractive for modern complex models where traditional capacity measures are hard to compute.

For regression with squared loss \(\ell(y',y) = (y'-y)^2\), the expected risk of a learning algorithm (averaged over training sets) decomposes into three interpretable components. Let \(\hat f_n\) be the estimator from a sample of size \(n\), and let \(f^*(x) = \mathbb{E}[Y\mid X=x]\). Then

The bias measures how far the average prediction is from the truth—typically decreasing as the model class grows. The variance measures sensitivity to the particular training sample—usually increasing with class complexity. The noise is the irreducible Bayes error. This decomposition explains the U‑shaped test error curve: as model complexity grows, bias drops quickly, variance eventually dominates, and the sum rises.

In classification, an analogous but more complex decomposition exists; for the 0‑1 loss, the bias–variance tradeoff can manifest in the interplay between the decision boundary and the randomness of the training set. The core lesson remains: the learner must balance the ability to approximate the true function against the stability of the estimates across different samples.

The bias–complexity–noise trichotomy generalises the bias–variance picture to the broader statistical learning setting. Any learning algorithm’s excess risk can be broken into three sources:

• Approximation error (bias)How well the hypothesis class \(\mathcal{H}\) can approximate the Bayes classifier or the true regression function. It is the minimum risk achievable within \(\mathcal{H}\) minus the Bayes risk. A small class has large bias; a rich class has small bias.
• Estimation error (complexity)The error due to choosing the hypothesis based on a finite sample. It depends on the capacity of \(\mathcal{H}\) (VC dimension, Rademacher complexity) and the sample size \(n\). Larger classes inflate this term.
• Irreducible noiseThe inherent randomness in the labels, captured by the Bayes risk \(R^*\). Even with infinite data, no predictor can beat this floor. It appears as the variance of \(Y\) given \(X\) or, in classification, as \(\mathbb{E}[\min(\eta(X),1-\eta(X))]\).

The total risk is the sum \(R^* + \varepsilon_{\text{app}} + \varepsilon_{\text{est}}\). Oracle inequalities (A4.19, A4.115) explicitly bound the estimation error in terms of complexity measures. The trichotomy clarifies that improving performance requires either reducing approximation error (enlarge \(\mathcal{H}\)), reducing estimation error (get more data or restrict \(\mathcal{H}\)), or accepting the noise floor. This three‑way split is the conceptual backbone of all machine learning practice.

In statistical learning theory, an oracle is a hypothetical entity that knows the true distribution \(P_{X,Y}\) and can select the best function within a given class. The oracle’s performance serves as the gold standard that a learning algorithm strives to match. The most common oracles are:

• Bayes oracle: The Bayes classifier \(h^*\), achieving risk \(R^*\). This is the absolute minimum possible risk.
• Class oracle: The best hypothesis in the chosen class \(\mathcal{H}\), i.e., \(h^*_{\mathcal{H}} \in \arg\min_{h\in\mathcal{H}} R(h)\). Its risk is \(R(h^*_{\mathcal{H}}) = R^* + \varepsilon_{\text{app}}\). The learner competes against this oracle; the goal is to achieve risk close to \(R(h^*_{\mathcal{H}})\) using only the training sample.
• Penalised oracle: In penalised ERM or SRM, the oracle may minimise a combination of risk and a penalty, e.g., \(\min_{h} [R(h) + \lambda \Omega(h)]\). The algorithm aims to achieve a comparable penalised risk.

The concept of an oracle inequality formalises this comparison: an oracle inequality (A4.19, A4.54) states that the learner’s risk is at most the oracle risk plus an excess term that vanishes as \(n\to\infty\). Thus, the learner is “almost as good” as the oracle. The existence of such guarantees—when the class is not too complex—is what makes learning theory a concrete science rather than mere heuristics.

Empirical Risk Minimisation (ERM) is the most straightforward and widely used learning principle. It is natural for several reasons:

• Direct approximation: Since we cannot compute the true risk, the empirical risk is the best available proxy. Minimising it is the most obvious surrogate for minimising the true risk. If the uniform law of large numbers holds (A4.144), ERM is consistent: the minimiser of the proxy converges to a minimiser of the true risk.
• Maximum likelihood connection: For probabilistic models with log‑loss, ERM (minimising the negative log‑likelihood) corresponds to maximum likelihood estimation (MLE). Many classical parametric methods are instances of ERM with specific losses.
• Simplicity and modularity: ERM only requires the definition of a hypothesis class and a loss function. It separates the problem into two parts: choose \(\mathcal{H}\) (inductive bias) and then solve the optimisation. This modularity is a key reason for its widespread adoption.
• Theoretical guarantees: As we have seen throughout this course, under appropriate complexity assumptions, ERM comes with finite‑sample PAC bounds and oracle inequalities. No other principle has such a complete and rigorous theoretical foundation for the binary classification problem. While alternative methods (penalised ERM, Bayesian inference, stability‑based algorithms) can improve practical performance, they are essentially refinements of the basic ERM idea, adding a penalty or a prior to control capacity.

Thus, ERM is the natural starting point for the formal study of machine learning, and its analysis illuminates the fundamental issues of generalisation, overfitting, and the need for inductive bias.

In multi‑class classification the label set is \(\mathcal{Y}=\{1,\dots,K\}\) with \(K>2\). The 0‑1 loss generalises directly: \(\ell(y',y)=\mathbf{1}_{y'\neq y}\). The Bayes classifier assigns the class with maximum posterior probability. The analogue of the VC dimension is the Natarajan dimension (or graph dimension), which reduces to the VC dimension when \(K=2\). Finite Natarajan dimension is necessary and sufficient for PAC learnability, and uniform convergence bounds involve \(\sqrt{\text{Natarajan}/n}\).

Structured prediction deals with exponentially large output spaces (e.g., sequences, trees, graphs) where the 0‑1 loss is too harsh. One defines a feature map \(\Phi(x,y)\) and learns a scoring function \(f(x,y)=\langle w,\Phi(x,y)\rangle\). Prediction is \(\arg\max_y f(x,y)\), often solved by dynamic programming or message passing. The generalisation theory relies on the structural SVM or conditional random fields, using Rademacher complexity of the scoring class and exploiting the output structure (e.g., via factor graphs) to obtain dimension‑free bounds. The key is that label dependencies reduce the effective capacity compared to a naive multi‑class view.

For regression with \(\mathcal{Y}=\mathbb{R}\), the squared loss \(\ell(y',y)=(y'-y)^2\) is the most common choice. The true risk \(R(h)=\mathbb{E}[(h(X)-Y)^2]\) is minimised by the conditional mean \(\eta(x)=\mathbb{E}[Y\mid X=x]\). The excess risk takes the clean form \(R(h)-R^* = \mathbb{E}[(h(X)-\eta(X))^2]\).

However, the squared loss is not globally Lipschitz: the derivative grows with the error size. This means the standard contraction principle (A4.132) does not directly apply to unbounded problems. To obtain generalisation bounds one must either:

• Assume the outputs and the functions are uniformly bounded (so that the loss is Lipschitz on the bounded domain), or
• Use moment conditions and extended concentration inequalities (e.g., Bernstein for unbounded variables) combined with truncation arguments.

Under boundedness, the Rademacher complexity of the squared loss class can be bounded via the Lipschitz property on the range, giving bounds similar to classification. For linear regression with \(\ell_2\) regularisation (ridge), the excess risk scales as \(O(d/n)\) in low dimensions, and a bias–variance decomposition (A4.171) cleanly separates approximation and estimation errors.

The hinge loss for binary classification with labels \(y\in\{-1,1\}\) is \(\ell(y\, f(x)) = \max(0, 1 - y f(x))\). It is a convex, 1‑Lipschitz upper bound on the 0‑1 loss. Minimising the regularised empirical hinge loss gives the Support Vector Machine (SVM):

Because the hinge loss is Lipschitz with constant 1, the contraction principle (A4.132) applies: the Rademacher complexity of the loss class is at most that of the function class \(\mathcal{H}_K\). For an RKHS with bounded kernel, the complexity is \(O(1/(\gamma\sqrt{n}))\) where \(\gamma = 1/\|f\|\) is the margin. The resulting generalisation bound is

showing that a large margin (small norm) directly improves the guarantee. This dimension‑free margin bound explains the effectiveness of SVMs in high‑dimensional spaces.

The logistic loss is \(\ell(y\, f(x)) = \log(1 + e^{-y f(x)})\) for \(y\in\{-1,1\}\). It arises from maximum likelihood in a logistic regression model where \(\mathbb{P}(Y=1\mid X=x) = \sigma(f(x))\) and \(\sigma(z)=1/(1+e^{-z})\). The loss is convex and 1‑Lipschitz, making it amenable to Rademacher bounds.

A crucial property is calibration: the logistic loss is a proper surrogate for the 0‑1 loss. For any measurable \(f\),

Thus, minimising the logistic excess risk also reduces the classification error. When combined with an \(\ell_2\) penalty (logistic ridge regression) or in an RKHS, one obtains oracle inequalities showing that the logistic estimator adapts to the noise level and can achieve fast rates under low‑noise conditions. The logistic loss is a canonical example of a convex surrogate that both enables efficient optimisation and preserves statistical optimality.

Convexity of the empirical risk (or of the regularised objective) guarantees that any local minimum is global, and that gradient‑based methods converge to the optimum at well‑understood rates. For a convex, \(L\)-smooth objective, gradient descent achieves an excess optimisation error of \(O(1/t)\); for a \(\mu\)-strongly convex function, the rate improves to linear convergence \(O(e^{-\mu t / L})\).

In statistical learning, convexity is desirable because:

• It makes the optimisation problem tractable even in high dimensions.
• Convex surrogate losses (hinge, logistic, squared hinge) provide a tight upper bound on the 0‑1 loss and are calibrated.
• The representer theorem (A4.181) often reduces an infinite‑dimensional convex problem to a finite‑dimensional one.

However, convexity is not a strict requirement: non‑convex objectives (e.g., neural networks) can also be optimised successfully in practice, but the theoretical analysis of generalisation must then rely on other properties (implicit bias, stability, margin). Convexity remains the gold standard for algorithms with provable guarantees.

A reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions \(\mathcal{H}_K\) equipped with a positive definite kernel \(K:\mathcal{X}\times\mathcal{X}\to\mathbb{R}\) satisfying \(\langle f, K(x,\cdot)\rangle_{\mathcal{H}_K} = f(x)\) for all \(f\in\mathcal{H}_K\). Kernel methods learn functions of the form \(f(x) = \sum_{i=1}^n \alpha_i K(x_i, x)\).

The Rademacher complexity of the ball \(\{f\in\mathcal{H}_K : \|f\|_{\mathcal{H}_K} \le B\}\) can be bounded by \(\frac{B}{n}\sqrt{\sum_{i=1}^n K(x_i,x_i)}\). For bounded kernels (e.g., Gaussian RBF with \(K(x,x)\le 1\)), this becomes \(O(B/\sqrt{n})\), completely independent of the (possibly infinite) feature dimension. This dimension‑free property is the statistical basis for the success of kernel SVMs, kernel ridge regression, and Gaussian processes. The kernel trick allows computing inner products implicitly without constructing feature maps, enabling flexible non‑linear learning with strong theoretical guarantees.

The proof decomposes any \(f\) into a component in the span of the kernel functions at the training points and an orthogonal part. The orthogonal part contributes nothing to the data fit term but increases the norm, so at the optimum it must vanish. The representer theorem reduces an infinite‑dimensional optimisation to a finite \(n\)-dimensional problem, making kernel methods computationally feasible. For SVMs (hinge loss), the solution is sparse (many \(\alpha_i=0\), the support vectors); for squared loss or logistic loss, the solution is typically dense.

Feed‑forward neural networks with threshold (or sigmoid) activations have finite VC dimension. For a network with \(W\) total weights (parameters) and piecewise‑polynomial activations (e.g., ReLU), the VC dimension is \(O(W \cdot L \log W)\) where \(L\) is the number of layers. For threshold gates, classical bounds give \(O(W \log W)\).

While these bounds are finite, they are typically far too large to explain the generalisation of modern overparameterized networks that have many more parameters than training examples. For example, a network with millions of weights would require millions of examples according to a naive VC bound, yet in practice such networks generalise well with much less data. This discrepancy motivated the development of norm‑based capacity measures: spectral norm, path norm, and margin‑based Rademacher complexity, which can be much smaller for networks trained with gradient descent. The VC dimension thus provides a worst‑case upper bound, but tighter data‑dependent and algorithm‑dependent bounds are needed to capture the true generalisation behaviour of deep learning.

Deep neural networks challenge the classical understanding of generalisation. Key observations include:

• Perfect fit of random labels: Overparameterized networks can achieve zero training error on randomly labelled data, yet they generalise well on correctly labelled data. This indicates that the hypothesis class is large enough to shatter any training set, so classical VC bounds give no guarantee.
• Implicit bias of SGD: Stochastic gradient descent with small learning rate and no explicit regularisation converges to solutions with low complexity (e.g., minimum \(\ell_2\) norm for linear models, low spectral norm for deep linear networks). The optimisation algorithm itself acts as a capacity control.
• Flat minima and margin: The solutions found by SGD often lie in wide basins of the loss landscape and have large margins in function space. PAC‑Bayes bounds and margin theory suggest that such solutions generalise better.

These puzzles have spurred new theoretical directions: information‑theoretic bounds, compression‑based arguments, and the study of the double descent phenomenon. The emerging picture is that generalisation in deep learning is not determined by the raw number of parameters, but by the interplay of data structure, optimisation dynamics, and the architecture’s implicit bias.

Classical bias–variance tradeoff predicts a U‑shaped test error curve as model complexity increases. The double descent phenomenon, observed in deep networks, kernel machines, and even linear models, shows a more nuanced behaviour:

• As the number of parameters increases, test error first decreases (classical regime).
• Near the interpolation threshold (where the model just fits the training data perfectly), the test error peaks.
• Beyond the interpolation threshold, as the model becomes overparameterized, the test error decreases again, often below the peak and sometimes below the initial optimal point.

This behaviour cannot be explained by classical capacity measures that blow up at the interpolation point. For linear regression with minimum‑norm least‑squares, the double descent can be rigorously analysed: the risk peaks when the number of features \(p\) equals the sample size \(n\), then drops for \(p>n\). The effect is linked to the implicit regularisation of the minimum‑norm interpolator and to the spectral properties of the feature covariance. Double descent reveals that “more parameters” can be helpful even when the model can perfectly fit noise, challenging the traditional overfitting narrative.

Interpolation refers to a model achieving exactly zero training error. In the classical underparameterized regime, interpolation leads to severe overfitting because there is a unique interpolating function that typically has poor generalisation. In the overparameterized regime, there are many interpolating solutions, and the algorithm’s choice among them determines generalisation.

For overparameterized linear regression, the minimum‑norm interpolator (obtained by gradient descent from zero initialisation) can have small test error even when the number of features far exceeds the sample size, provided the signal aligns with the high‑variance directions of the data. The phenomenon of benign overfitting characterises when this happens: essentially, the effective rank of the covariance matrix and the signal‑to‑noise ratio must satisfy certain conditions.

In deep learning, overparameterization plus implicit bias of SGD leads to solutions that interpolate the training data but also have large margins or low complexity in appropriate norms, explaining their excellent generalisation. The theory of overparameterized models has reshaped our understanding: capacity alone does not govern generalisation; the combination of model, algorithm, and data structure is what matters.

Benign overfitting occurs when a predictor fits the training data perfectly (zero empirical risk) yet still achieves near‑optimal test error. This contrasts with the classical view that interpolation leads to catastrophic overfitting. The phenomenon is possible in overparameterized regimes where many interpolating solutions exist and the learning algorithm’s implicit bias selects one with good generalisation properties.

For linear regression, the minimum‑norm interpolator has risk bounded by a decomposition involving the effective rank of the covariance matrix and the signal‑to‑noise ratio. Specifically, if the eigenvalues of the feature covariance decay appropriately and the true regression vector aligns with high‑variance directions, the excess risk can be small despite perfect fitting of noisy training labels. In neural networks, benign overfitting is facilitated by large margins and flat minima. The theory redefines “overfitting” as not necessarily harmful; the key is whether the interpolation aligns with the underlying low‑dimensional structure of the problem.

A parametric model has a fixed, finite number of parameters (e.g., linear regression, logistic regression, finite mixture models). Its capacity does not grow with the sample size. Guarantees typically involve rates like \(O(d/n)\) for excess risk under squared loss, or \(O(\sqrt{d/n})\) in the agnostic case. Parametric models are computationally efficient but vulnerable to model misspecification if the true function does not lie in the class.

A non‑parametric model allows the complexity to grow with \(n\) (e.g., histograms, kernel density estimators, smoothing splines, nearest neighbours). The hypothesis class is infinite‑dimensional, but learning is still possible because the effective complexity is controlled by a smoothness parameter or a bandwidth. Rates for non‑parametric methods are typically slower, e.g., \(O(n^{-\frac{2\beta}{2\beta+d}})\) for a Hölder‑smooth function of order \(\beta\) in \(d\) dimensions, as given by Stone’s theorem (A4.188). The distinction between parametric and non‑parametric is blurred by modern overparameterized models (neural networks) that act as adaptive non‑parametric estimators.

A learning algorithm is universally consistent if for any distribution \(P_{X,Y}\), its risk converges to the Bayes risk in probability as the sample size grows: \(R(h_n) \to R^*\) in probability. This requires the hypothesis class to be dense in the space of all functions (in a suitable sense) but with proper regularisation to avoid overfitting.

Stone’s theorem establishes that “learning is possible” in a very general sense, but uniform rates require smoothness or margin conditions. The theory of universal consistency thus delineates the boundary between the possible (consistency) and the achievable in practice (fast rates).

Statistical learning theory (SLT) and classical statistics share the goal of making inferences from data, but they differ in emphasis. Classical statistics often focuses on parametric models with a small number of parameters, using asymptotic approximations and tests for model correctness. SLT emphasises distribution‑free guarantees, finite‑sample bounds, and the analysis of algorithms that minimise empirical risk over potentially large hypothesis classes. Instead of assuming a true data‑generating model, SLT assesses performance by the excess risk compared to the best predictor in a given class, even if that class is misspecified.

Over time the boundaries have blurred: modern statistics embraces non‑parametric methods, model selection, and high‑dimensional asymptotics, while machine learning incorporates probabilistic modelling and uncertainty quantification. The intersection of the two fields—statistical learning theory—provides a coherent language to describe the generalisation ability of both classical and modern algorithms, from linear regression to deep networks.

Generalisation is the ability of a learning algorithm to perform accurately on new, previously unseen examples. In the PAC framework, this is formalised as the requirement that \(R(h_n) \le \epsilon\) with high probability after seeing \(n\) examples. All the theory developed in this sequence—VC dimension, Rademacher complexity, oracle inequalities, margin bounds, noise conditions, and stability—aims to quantify when and how fast generalisation happens.

Generalisation is not guaranteed by low training error alone; it requires an appropriate inductive bias, encoded in the hypothesis class or the learning algorithm. The no‑free‑lunch theorems (A4.21–A4.22) show that without restriction, learning is impossible. The central achievement of SLT is to identify the complexity measures that govern generalisation and to provide explicit, non‑asymptotic bounds. This transforms a philosophical puzzle into a precise mathematical discipline.

Statistical learning theory has expanded far beyond the classical VC and Rademacher frameworks. Current frontiers include:

• Deep learning theory: Understanding how overparameterized networks generalise through implicit bias, kernel regime (NTK), and feature learning.
• Distribution shift and causality: Generalisation under train‑test distribution mismatch (domain adaptation), invariant prediction, and the integration of causal reasoning.
• Large‑scale and federated learning: Generalisation with limited communication, privacy constraints, and heterogeneous data.
• Self‑supervised and foundation models: Theoretical underpinnings of pretraining on massive unlabelled data and emergent abilities.
• Robustness and fairness: Adversarial robustness, worst‑group performance, and algorithmic fairness as aspects of generalisation under different risk measures.

The tools developed in these notes—concentration inequalities, capacity measures, localisation—remain essential, but they are being adapted and extended to meet the challenges of modern machine learning. The road ahead lies at the intersection of statistics, optimisation, and information theory.

Minimising the empirical 0‑1 risk \(\widehat{R}_n(h) = \frac{1}{n}\sum_{i=1}^n \mathbf{1}_{h(x_i)\neq y_i}\) over a hypothesis class \(\mathcal{H}\) is computationally intractable for most classes of interest. Even for linear classifiers in \(\mathbb{R}^d\), the ERM problem is NP‑hard in the worst case (unless the data are linearly separable). The 0‑1 loss is non‑convex, discontinuous, and its minimisation is a combinatorial problem.

This motivates the use of convex surrogate loss functions. Instead of minimising the 0‑1 loss directly, one minimises a convex function \(\phi\) that upper‑bounds the 0‑1 loss. For instance, \(\phi(z) = \log(1+e^{-z})\) (logistic), \(\phi(z) = \max(0, 1-z)\) (hinge). These surrogate losses lead to computationally tractable optimisation (convex programs) while preserving the statistical properties: calibration ensures that a small excess surrogate risk implies a small excess 0‑1 risk. The trade‑off between computational efficiency and statistical accuracy is a central theme in modern machine learning.

Convexity is essential for efficient optimisation because any local minimum is global, and gradient‑based methods converge to the optimum. Many surrogate losses (logistic, hinge, squared hinge) are convex in the linear predictor \(w^\top x\), making regularised ERM a convex optimisation problem.

For binary classification with labels originally in \(\{0,1\}\), it is often mathematically convenient to map them to \(\{-1,+1\}\) using the spin transform:

Under this mapping, the 0‑1 loss becomes \(\mathbf{1}_{\tilde{Y} h(x) \le 0}\). A margin‑based predictor \(f(x)\) then classifies according to \(\operatorname{sign}(f(x))\), and the product \(\tilde{Y} f(x) > 0\) indicates a correct prediction. Many surrogate losses are expressed in terms of the margin \(z = y f(x)\): hinge \(\max(0,1-z)\), logistic \(\log(1+e^{-z})\), exponential \(e^{-z}\). The spin transform simplifies formulas and aligns classification with the geometric concept of halfspaces in \(\mathbb{R}^d\). It also unifies the treatment of hard classifiers (\(h:\mathcal{X}\to\{-1,+1\}\)) and real‑valued classifiers (\(f:\mathcal{X}\to\mathbb{R}\)) whose sign gives the prediction.

A hard classifier directly outputs a binary decision: \(h(x)\in\{-1,+1\}\). It is the object of interest for the 0‑1 loss. However, learning with the 0‑1 loss is computationally hard (A4.192), so one often learns a soft classifier (or scoring function) \(f:\mathcal{X}\to[-1,1]\) (or \(\mathbb{R}\)), where the sign of \(f(x)\) yields the prediction. The absolute value \(|f(x)|\) can be interpreted as a confidence or margin.

Using a soft classifier enables smooth, convex surrogate losses applied to the margin \(y f(x)\). The final decision rule is obtained by thresholding: \(h_f(x) = \operatorname{sign}(f(x))\). Generalisation bounds for soft classifiers often involve the margin \(\gamma = \min_i y_i f(x_i)\), and larger margins lead to better guarantees. The relationship between the excess surrogate risk and the excess 0‑1 risk is given by calibration theory. Thus, the soft/hard distinction separates the optimisation problem from the evaluation metric.

Common examples: hinge \(\phi(z)=\max(0,1-z)\), logistic \(\phi(z)=\log(1+e^{-z})\), exponential \(\phi(z)=e^{-z}\), squared hinge \(\phi(z)=(\max(0,1-z))^2\). These convex surrogates make empirical risk minimisation computationally tractable while providing statistical calibration guarantees: a small excess surrogate risk translates into a small excess classification risk.

With labels in \(\{-1,+1\}\) and a real‑valued predictor \(f(x)\), the margin is \(y f(x)\). To unify notation, one often works with the argument \(z = -y f(x)\). A mistake occurs when \(y f(x) \le 0\) i.e. \(z \ge 0\). The hinge loss is defined as

It satisfies \(\mathbf{1}_{z \ge 0} \le \phi(z)\) for all \(z\) (since for \(z\ge0\), \(\phi(z)\ge 1\), and for \(z<0\), \(\phi(z)=0\)). The hinge loss is convex, 1‑Lipschitz, and piecewise linear. It is the loss minimised by the Support Vector Machine (SVM) after regularisation. Because it is an upper bound on the 0‑1 loss, minimising the empirical hinge risk provides a computationally tractable surrogate for classification.

For a margin \(y f(x)\), the hinge loss is \(\max(0,\, 1 - y f(x))\). The two conventions are equivalent via the relation \(z = -y f(x)\). The function is non‑increasing for \(z \le -1\) (i.e., margin \(\ge 1\)) and increases linearly thereafter.

The exponential loss is defined as \(\phi(z) = e^{z}\) for \(z = -y f(x)\). For a correct classification with margin \(y f(x) > 0\), \(z<0\) and the loss is less than 1, decaying exponentially; for a misclassification (\(z\ge 0\)), the loss is at least 1 and grows rapidly. The exponential loss satisfies \(\mathbf{1}_{z\ge 0} \le e^z\).

It is the loss function underlying the AdaBoost algorithm: AdaBoost can be viewed as coordinate descent on the exponential loss. Although convex, the exponential loss is not Lipschitz globally, which makes it sensitive to outliers and label noise. It heavily penalises large negative margins. The exponential loss is calibrated—its population minimiser yields the Bayes classifier—but its fast growth can lead to overemphasis on misclassified examples, motivating more robust surrogates like logistic loss.

With the same parametrisation \(z = -y f(x)\), the logistic loss (in base 2) is

Using natural log, it is \(\ln(1+e^z)\); the base‑2 version simply scales by a constant. The loss is convex, smooth, and strictly decreasing for all \(z\). It satisfies \(\mathbf{1}_{z\ge 0} \le \phi(z)\) (with \(\phi(0)=1\) in base 2; in natural log it would be \(\ln 2\), so re‑scaling ensures the inequality holds at the boundary).

The logistic loss corresponds to maximum likelihood in a logistic regression model where \(\mathbb{P}(Y=+1\mid X=x) = 1/(1+e^{-f(x)})\). It is a canonical proper loss: the minimiser of the population logistic risk is exactly the log‑odds \(f^*(x) = \log\frac{\eta(x)}{1-\eta(x)}\). The logistic loss is Lipschitz (with constant 1 under suitable scaling) and well‑calibrated. It is widely used in logistic regression and neural networks.

For a soft classifier \(f:\mathcal{X}\to\mathbb{R}\) and a surrogate loss \(\phi\), the population \(\phi\)-risk is

Given a sample \(S = ((X_1,Y_1),\dots,(X_n,Y_n))\) with labels in \(\{-1,+1\}\), the empirical \(\phi\)-risk is

The minimiser of the population \(\phi\)-risk (over all measurable functions) is denoted \(f_\phi^*\). The goal of a surrogate‑loss‑based learner is to minimise the empirical \(\phi\)-risk (possibly with regularisation) to obtain \(\hat f\), and then output the hard classifier \(h_{\hat f}(x) = \operatorname{sign}(\hat f(x))\). The key question is whether a small excess \(\phi\)-risk \(R_\phi(\hat f) - R_\phi(f_\phi^*)\) guarantees a small excess classification risk \(R_{0-1}(\operatorname{sign}(\hat f)) - R^*\).

The minimiser of the population \(\phi\)-risk over all measurable functions \(f:\mathcal{X}\to\mathbb{R}\) can be found pointwise by minimising the conditional risk. For a fixed \(x\), let \(\eta(x) = \mathbb{P}(Y=+1\mid X=x)\). The conditional \(\phi\)-risk of predicting \(\alpha = f(x)\) is

Thus \(f_\phi^*(x)\) is any minimiser of \(\alpha \mapsto H_{\eta(x)}(\alpha)\). For convex, calibrated surrogates, this minimiser is unique for \(\eta(x)\neq 1/2\) and its sign matches the Bayes classifier. For the logistic loss, \(f_\phi^*(x) = \log\frac{\eta(x)}{1-\eta(x)}\). For the hinge loss, any \(\alpha\) in \([-1,1]\) is a minimiser when \(\eta(x)=1/2\), but the sign is correct. For the exponential loss, \(f_\phi^*(x) = \frac{1}{2}\log\frac{\eta(x)}{1-\eta(x)}\). In all cases, \(\operatorname{sign}(f_\phi^*(x)) = \operatorname{sign}(\eta(x)-1/2)\), so thresholding at zero yields the Bayes classifier.

For a given \(\eta\in[0,1]\), the function \(H_\eta(\alpha)\) gives the expected surrogate loss when the true conditional probability is \(\eta\) and the prediction is \(\alpha\). This function captures all information about the surrogate’s behaviour. The overall \(\phi\)-risk can be written as

Minimising \(R_\phi\) pointwise for each \(x\) is equivalent to minimising \(H_{\eta(x)}(\alpha)\) over \(\alpha\). The minimal value is \(H_{\eta(x)}^* = \inf_\alpha H_{\eta(x)}(\alpha)\). The excess \(\phi\)-risk then decomposes as \(\mathbb{E}_X[H_{\eta(X)}(f(X)) - H_{\eta(X)}^*]\). The function \(H_\eta\) is convex in \(\alpha\) (since \(\phi\) is convex) and its derivative (when \(\phi\) is smooth) is \(-\eta\,\phi'(-\alpha) + (1-\eta)\,\phi'(\alpha)\). Setting the derivative to zero yields the minimiser.

A convex surrogate \(\phi\) is Bayes consistent (or classification‑calibrated) if the minimiser \(f_\phi^*\) satisfies \(\operatorname{sign}(f_\phi^*(x)) = \operatorname{sign}(\eta(x)-1/2)\) for all \(\eta\neq 1/2\). This guarantees that the optimal surrogate‑based classifier coincides with the Bayes classifier.

For a differentiable \(\phi\), the minimiser of \(H_\eta(\alpha)\) satisfies the first‑order condition

For the minimiser to have the correct sign, we need that \(\alpha > 0\) when \(\eta > 1/2\) and \(\alpha < 0\) when \(\eta < 1/2\). This requires \(\phi'\) to be such that the ratio \(\phi'(\alpha)/\phi'(-\alpha)\) is increasing in \(\alpha\) and passes through 1 at \(\alpha=0\). For the logistic loss \(\phi(z)=\ln(1+e^z)\), \(\phi'(z)=e^z/(1+e^z)\) and \(\phi'(0)=1/2\); the condition yields \(\alpha = \ln\frac{\eta}{1-\eta}\), which indeed has the same sign as \(\eta-1/2\). The hinge loss is not differentiable at \(-1\), but its subgradient yields any \(\alpha\in[-1,1]\) for \(\eta=1/2\), and for \(\eta\neq 1/2\), the minimiser is \(\alpha = \operatorname{sign}(\eta-1/2)\) (clipped to \([-1,1]\)), still giving correct sign. The exponential loss also satisfies the sign condition.

This lemma is the central calibration result. It shows that if an algorithm achieves a small excess surrogate risk, then the resulting classifier has a small excess 0‑1 risk. The shape of \(\psi\) determines the rate: for hinge loss, \(\psi(t)=t\); for logistic and exponential, \(\psi(t) \le C\sqrt{t}\). Thus, an excess \(\phi\)-risk of \(\epsilon\) translates to an excess classification risk of at most \(\epsilon\) (fast) or \(C\sqrt{\epsilon}\). Combined with oracle inequalities on the surrogate risk, Zhang’s lemma yields the final classification bound.

The proof of Zhang’s lemma proceeds by conditioning on \(X=x\). For any \(\eta\in[0,1]\) and any \(\alpha\in\mathbb{R}\), define the excess conditional \(\phi\)-risk:

If \(\operatorname{sign}(\alpha) \neq \operatorname{sign}(\eta-1/2)\) (a classification mistake), then one can show that \(\Delta H_\eta(\alpha) \ge c > 0\) for some positive constant depending only on \(\eta\). More precisely, define

Actually, the standard proof uses the following: for any \(\alpha\) with wrong sign, \(H_\eta(\alpha) \ge H_\eta(0) \ge 1\) (for losses normalized so that \(\phi(0)=1\)). Then, by convexity of \(H_\eta\), one obtains a linear relation between the excess conditional risk and the 0‑1 mistake at that \(\eta\). Integrating over \(X\) yields the global inequality. The function \(\psi\) is essentially \(\psi(t) = \sup_{\eta} [ \mathbf{1}_{\text{wrong sign}} \text{ given } \Delta H_\eta(\alpha)\le t ]\). For hinge loss, \(\psi(t)=t\); for exponential and logistic, \(\psi(t) \le \sqrt{2t}\) (up to constants).

The calibration function \(\psi\) in Zhang’s lemma can be characterised explicitly for common losses:

• Hinge loss: \(\psi(t) = t\). This gives a perfect transfer: excess \(\phi\)-risk translates linearly to excess classification risk. This is the best possible calibration and explains why the SVM margin bound directly controls classification error.
• Logistic loss (natural base): \(\psi(t) \le \sqrt{2t}\). For the base‑2 version, constants adjust. The square‑root dependence arises because the logistic loss is smooth and has quadratic behaviour near the optimum. Consequently, an excess logistic risk of \(\epsilon\) yields an excess 0‑1 risk of at most \(\sqrt{2\epsilon}\).
• Exponential loss: \(\psi(t) \le \sqrt{2t}\) as well, similar to logistic. However, the exponential loss is more aggressive on large negative margins, which can be beneficial in boosting but detrimental under label noise.

These calibration constants are essential for converting oracle inequalities on the surrogate risk into final PAC bounds for the classifier. They also highlight the trade‑off between computational ease (hinge) and statistical efficiency under various noise regimes.

The journey from the intractable 0‑1 loss to computationally efficient algorithms can be summarised as follows:

1. ERM with 0‑1 loss is NP‑hard for linear classifiers and many other classes; the loss is non‑convex, discontinuous, and its optimisation is combinatorial.
2. Introduce a convex surrogate loss \(\phi\) that upper bounds the 0‑1 loss (after appropriate scaling) and is convex and Lipschitz (or smooth). Common choices: hinge, exponential, logistic.
3. Minimise the empirical \(\phi\)-risk (possibly with regularisation) to obtain \(\hat f\). This is a convex optimisation problem solvable in polynomial time.
4. Prove a calibration inequality (Zhang’s lemma) linking excess \(\phi\)-risk to excess classification risk: \(R_{0-1}(\operatorname{sign}(\hat f)) - R^* \le \psi(R_\phi(\hat f) - R_\phi^*)\).
5. Apply Rademacher complexity or VC bounds to control the excess \(\phi\)-risk of the regularised empirical minimiser, yielding an oracle inequality for the surrogate.
6. Combine to obtain a PAC guarantee for the final classifier.

This convex relaxation framework has been remarkably successful, underpinning SVMs, logistic regression, boosting, and many other algorithms. It illustrates a central theme of statistical learning theory: computational tractability and statistical efficiency can be achieved simultaneously through careful design of the learning objective.

Any unconstrained optimisation problem \(\min_{x} f(x)\) can be recast as a constrained problem in one extra variable using the epigraph of \(f\), defined as \(\operatorname{epi}(f) = \{(x,t) \mid f(x) \le t\}\). Then

This equivalence is trivial but powerful: if \(f\) is convex, \(\operatorname{epi}(f)\) is a convex set, and the problem becomes minimising a linear function over a convex set. This is the bridge between convex functions and convex sets, and it underpins many duality results. The optimal value is the same, and an optimal \((x^*,t^*)\) satisfies \(t^* = f(x^*)\).

Minimising a linear function over a set \(D\) is equivalent to minimising over its convex hull. Formally, for any \(D\subseteq\mathbb{R}^d\) and any vector \(c\),

Proof sketch. The inequality \(\ge\) is trivial because \(D\subseteq\operatorname{conv}(D)\). For the reverse, any point in \(\operatorname{conv}(D)\) is a convex combination \(\sum_i \theta_i x_i\) with \(x_i\in D\). Then \(c^\top(\sum \theta_i x_i) = \sum \theta_i (c^\top x_i) \ge \min_i (c^\top x_i) \ge \inf_{x\in D} c^\top x\). Hence, the minimum over the convex hull cannot be smaller than the minimum over the original set. This fact is fundamental in integer programming (LP relaxation) and in proving that hard margin SVM with hinge loss can be studied via convex analysis of the convex hull of feasible points.

Geometrically, a subgradient defines an affine function that globally underestimates \(f\) and touches it at \(x\). Subgradients exist everywhere for convex functions (see A4.211), and they are the natural generalisation of the gradient for non‑smooth convex optimisation. They are central to the analysis of SVM (hinge loss), Lasso, and other non‑smooth empirical risk minimisation problems.

Proof idea. Consider the epigraph \(\operatorname{epi}(f)\), a convex set. The point \((x,f(x))\) lies on its boundary. By the supporting hyperplane theorem, there exists a non‑zero vector \((g,-1)\) (or \((g,-\beta)\)) defining a hyperplane that supports the epigraph at \((x,f(x))\). Normalising, this yields a vector \(g\) such that for all \(y\), \(f(y) \ge f(x) + g^\top(y-x)\), which is exactly the subgradient inequality. This geometric argument shows that subgradients exist at all interior points. At boundary points, subgradients may also exist under mild conditions (e.g., the function is continuous).

These properties make convex optimisation tractable: any algorithm that finds a point where \(0\in\partial f\) (or \(\|\nabla f\|\) small) has found a global optimum. There is no danger of spurious local minima, which is a major difference from non‑convex problems.

For a differentiable function \(f\), the first‑order Taylor expansion around \(x\) gives \(f(x - \eta g) \approx f(x) - \eta \nabla f(x)^\top g\). For a fixed step size \(\eta\), the direction that minimises this linear approximation under a unit norm constraint \(\|g\|=1\) is \(g = \nabla f(x)/\|\nabla f(x)\|\). Thus, the negative gradient is the direction of steepest local decrease, justifying the gradient descent update:

This geometric intuition holds in the Euclidean norm; changing the norm yields different “steepest descent” directions (e.g., coordinate descent under \(\ell_1\) norm). In convex optimisation, gradient descent with appropriate step sizes converges to the global optimum.

Gradient descent solves \(\min_{x} f(x)\) iteratively:

Initialise x_0 arbitrarily.
For k = 0,1,2,...:
    Compute g_k = ∇f(x_k)
    Choose step size η_k > 0
    Update x_{k+1} = x_k - η_k g_k
End
    

The step size \(\eta_k\) can be fixed, decreasing, or chosen via line search. For convex \(f\) with Lipschitz gradient or Lipschitz function value (non‑smooth), precise rates are known (see A4.215). For smooth and strongly convex functions, linear convergence is achieved.

Proof. Let \(g_t\in\partial f(x_t)\). From the update and convexity:

Using \(f(x_t)-f(x^*) \le g_t^\top(x_t-x^*)\) (subgradient inequality) and \(\|g_t\|\le L\), we get

Summing from \(t=0\) to \(k-1\) and telescoping yields

With \(\eta_t = \frac{R}{L\sqrt{k}}\), we obtain \(2\frac{R}{L\sqrt{k}}\sum(f(x_t)-f(x^*)) \le R^2 + k\cdot\frac{R^2}{k} = 2R^2\). Hence \(\frac{1}{k}\sum f(x_t) - f(x^*) \le \frac{LR}{\sqrt{k}}\). Convexity gives \(f(\bar x_k)\le\frac{1}{k}\sum f(x_t)\).

Two common step size rules for subgradient descent:

• Fixed \(\eta_t = \frac{R}{L\sqrt{k}}\) for a preset total number of iterations \(k\). This gives the \(O(LR/\sqrt{k})\) guarantee but requires knowing the total iterations in advance. It is optimal for the worst case.
• Decreasing \(\eta_t = \frac{R}{L\sqrt{t}}\). This adapts automatically to running indefinitely. The analysis with telescoping sum introduces a \(\log k\) factor: \(f(\bar x_k)-f(x^*) = O(LR \frac{\log k}{\sqrt{k}})\).

The logarithmic penalty from the decreasing schedule is often acceptable, but the next section shows how to remove it by averaging only the second half of the iterates.

If we run decreasing step sizes \(\eta_t = \frac{R}{L\sqrt{t}}\) but only average the iterates from \(t=k/2\) to \(k\), the logarithmic factor disappears. The intuition is that the larger step sizes in early iterations contribute the log‑factor, while later steps are all small and stable. By discarding the first half, we get a guarantee of \(O(LR/\sqrt{k})\) without a log factor, without needing to pre‑specify the total number of iterations. The proof splits the sum and uses \(\sum_{t=k/2}^k \eta_t^2 \approx \sum \frac{1}{t} \approx O(1/k)\) with a constant, not a log, and the initial distance \(R\) still bounds the early terms. This trick makes adaptive step sizes fully competitive with the fixed horizon schedule.

Geometrically, the vector from the projection to \(x\) forms an acute angle with any other point in the set, meaning the projection is the closest point. Equivalently, \(\pi_{\mathcal{C}}(x)\) is the unique solution to \(\langle x - \pi_{\mathcal{C}}(x), z - \pi_{\mathcal{C}}(x)\rangle \le 0\). This inequality is fundamental in projected gradient descent, used to solve constrained optimisation problems \(\min_{x\in\mathcal{C}} f(x)\), and for algorithms like SVM with convex constraints.

For a closed convex set \(\mathcal{C}\subseteq\mathbb{R}^d\), the projection \(\pi_{\mathcal{C}}(x)\) is the unique point in \(\mathcal{C}\) that minimises the distance to \(x\). Uniqueness follows from the strict convexity of the Euclidean norm and the convexity of \(\mathcal{C}\).

Proof by contradiction. Suppose \(z_1\neq z_2\) both minimise \(\|x-z\|\) over \(\mathcal{C}\) and let \(r = \|x-z_1\| = \|x-z_2\|\). By convexity, \(\bar z = \frac{1}{2}(z_1+z_2)\in\mathcal{C}\). By the parallelogram law,

Thus \(\bar z\) is strictly closer to \(x\) than \(z_1\), contradicting minimality. Hence the projection is unique. This uniqueness is essential for defining projected gradient descent and for the variational inequality characterisation.

Projected gradient descent solves \(\min_{x\in\mathcal{C}} f(x)\) for a convex function \(f\) and a closed convex set \(\mathcal{C}\) by alternating a gradient step and a projection:

Initialise x_0 ∈ C.
For k = 0,1,2,...:
    Compute g_k ∈ ∂f(x_k)
    Choose step size η_k > 0
    Set y_{k+1} = x_k - η_k g_k
    Project onto C: x_{k+1} = π_C(y_{k+1})
End
    

The projection step ensures feasibility: \(x_{k+1}\in\mathcal{C}\). The analysis mirrors the unconstrained case but uses the variational inequality (A4.218) to show that the projection does not increase the distance to the optimum. PGD is the standard method for constrained convex ERM (e.g., SVM with norm constraints, Lasso with \(\ell_1\) ball).

Proof sketch. The projection step is non‑expansive: \(\|\pi_{\mathcal{C}}(y)-x^*\| \le \|y-x^*\|\). Using this and the subgradient inequality, one obtains the same recurrence as in the unconstrained case:

Telescoping the sum and averaging gives the \(O(LR/\sqrt{k})\) bound. The projection introduces no extra cost in the convergence rate; it just keeps the iterates inside the feasible set.

For SVM with hinge loss and a kernel \(K\), we learn \(f(x) = \sum_{j=1}^n \alpha_j K(x_j, x)\) by minimising over \(\alpha\) in a convex set. The objective is \(F(\alpha) = \frac{1}{n}\sum_{i=1}^n \max(0, 1 - y_i (K\alpha)_i) + \frac{\lambda}{2} \alpha^\top K \alpha\). To apply subgradient descent, we need the Lipschitz constant \(L\) of the hinge loss part with respect to \(\alpha\). The subgradient of the empirical hinge risk with respect to \(\alpha\) has norm bounded by the maximum \(\ell_2\) norm of the columns of the kernel matrix: each term contributes at most the norm of the \(i\)-th column of \(K\) (since \(|\partial \max(0,1-z)| \le 1\)). Thus, \(L = \max_i \|K_{:,i}\|_2 = \max_i \sqrt{K_{ii}} = \max_i \sqrt{K(x_i,x_i)}\). For the Gaussian kernel, \(K(x_i,x_i)=1\), so \(L=1\). The regulariser’s gradient \(2\lambda K\alpha\) adds a smooth term; the Lipschitz constant of the full objective can be bounded accordingly.

In projected subgradient descent for SVM, the feasible set is often a norm ball \(\mathcal{C} = \{\alpha : \alpha^\top K \alpha \le B^2\}\) or an \(\ell_2\) ball in feature space. The diameter \(R = \max_{\alpha,\beta\in\mathcal{C}} \|\alpha-\beta\|_2\). For the constraint \(\alpha^\top K \alpha \le B^2\), we can bound the diameter of the feasible set in \(\ell_2\): if \(\lambda_{\min}(K) > 0\), then for any \(\alpha\) in the set, \(\|\alpha\|_2 \le B/\sqrt{\lambda_{\min}(K)}\), so \(R \le 2B/\sqrt{\lambda_{\min}(K)}\). If the kernel is strictly positive definite, \(\lambda_{\min}(K)>0\); for a Gaussian kernel on distinct points, the kernel matrix has full rank but eigenvalues can be very small, making \(R\) large. Regularisation ensures a lower bound on the effective curvature. The iteration complexity \(O(LR/\sqrt{k})\) then depends on the condition number via \(\lambda_{\min}(K)\).

For a kernel derived from inner products of random features (e.g., Gaussian random projections), the kernel matrix \(K\) behaves like a Wishart matrix. Random matrix theory (Marchenko–Pastur) predicts that the eigenvalues are supported in \([\lambda_{-},\lambda_{+}]\) with \(\lambda_{-} \approx (1-\sqrt{c})^2\) where \(c = n/d\) is the aspect ratio. Thus, for a large number of random features \(d \gg n\), the smallest eigenvalue is bounded away from zero, giving a bounded diameter \(R\). Combined with \(L=1\) (for Gaussian kernel), the iteration complexity \(O(LR/\sqrt{k})\) becomes \(O(1/\sqrt{k})\) with a moderate constant. This explains why random feature approximations to kernel SVM are computationally efficient: the condition number is well‑behaved, and the subgradient method converges in a predictable number of iterations.

Boosting algorithms (e.g., AdaBoost with coordinate descent) can be cast as minimising a convex loss (exponential or logistic) over the simplex \(\Delta_N = \{\alpha\in\mathbb{R}^N : \alpha_i \ge 0, \sum \alpha_i = 1\}\), where \(N\) is the number of weak learners. The \(\ell_1\) diameter of the simplex is \(2\). However, the Lipschitz constant \(L\) with respect to \(\ell_2\) norm is large: the gradient of the loss with respect to \(\alpha\) can have norm up to \(\sqrt{N}\) (by Cauchy–Schwarz). Thus, the subgradient descent guarantee \(O(LR/\sqrt{k})\) becomes \(O(\sqrt{N/k})\), which is poor when \(N\) is large. This motivates the use of non‑Euclidean methods (mirror descent with entropy) that exploit the \(\ell_1\) geometry, where the diameter measured in \(\ell_1\) is \(2\) and the Lipschitz constant in the dual \(\ell_\infty\) norm is \(1\), giving a rate \(O(\sqrt{\log N / k})\)—exponentially better in \(N\).

Standard gradient descent is tuned to the Euclidean (\(\ell_2\)) geometry: it uses the squared Euclidean distance as a measure of progress. In many problems, the feasible set is naturally suited to a different norm—for instance, the simplex is an \(\ell_1\) ball, and the Lipschitz constant is measured in \(\ell_\infty\). Using Euclidean projections onto the simplex is possible but computationally expensive, and the resulting iteration complexity is suboptimal (large \(L\) in \(\ell_2\)). Mirror descent generalises gradient descent to arbitrary geometries by replacing the Euclidean distance with a Bregman divergence derived from a strongly convex mirror map \(\Phi\). This allows the algorithm to exploit the duality between \(\ell_1\) and \(\ell_\infty\), dramatically improving the dimension dependence from \(\sqrt{N}\) to \(\sqrt{\log N}\). Mirror descent is the foundation for the exponentiated gradient algorithm, boosting, and many online learning algorithms.

Strong convexity is the key property of the mirror map; it ensures that the Bregman divergence dominates the squared norm distance, enabling convergence proofs.

Bregman divergence is the natural notion of distance for mirror descent, replacing the squared Euclidean norm in the update step and in the convergence analysis.

Proof. Expand the left‑hand side using the definition of Bregman divergence:

A cleaner direct verification: write each term using \(\Phi\) and cancel. The identity is the generalisation of the Euclidean law of cosines to Bregman divergences. It is the key algebraic tool in the analysis of mirror descent, allowing telescoping sums with Bregman divergences in place of squared norms.

In mirror descent (A4.233), after a gradient step in the dual space, one maps back to the primal feasible set using the Bregman projection. The variational inequality for Bregman projections replaces the Euclidean one (A4.218) and is central to the convergence proof.

Consider minimising a convex function over the \(\ell_1\) ball of radius \(R\) in \(\mathbb{R}^n\). The Lipschitz constant of a typical loss gradient measured in \(\ell_\infty\) norm may be \(O(1)\), but measured in \(\ell_2\) norm it can be as large as \(\sqrt{n}\) (since \(\|g\|_2 \le \sqrt{n}\|g\|_\infty\)). Projected gradient descent using Euclidean projections onto the \(\ell_1\) ball yields an iteration complexity bound of \(O(LR/\sqrt{k}) = O(\sqrt{n}R/\sqrt{k})\), which scales poorly with dimension.

Mirror descent with the negative entropy mirror map \(\Phi(x)=\sum x_i\log x_i\) and the \(\ell_1\) norm geometry transforms the gradient into the dual \(\ell_\infty\) norm, where the Lipschitz constant remains \(O(1)\). The diameter of the simplex measured in \(\ell_1\) is \(2\), so the convergence rate becomes \(O(\sqrt{\log n / k})\)—exponentially better in \(n\). This dimension‑free improvement is the primary motivation for using non‑Euclidean methods in high‑dimensional problems such as boosting and online learning over the simplex.

Mirror descent operates in two spaces:

• The primal space \(\mathcal{X}\) where the original variables \(x\) live, equipped with a norm \(\|\cdot\|\) and a convex feasible set \(\mathcal{C}\).
• The dual space \(\mathcal{X}^*\) where gradients (subgradients) reside, equipped with the dual norm \(\|\cdot\|_*\).

The mirror map \(\Phi: \mathcal{D}\to\mathbb{R}\) (strongly convex on \(\mathcal{D}\supseteq\mathcal{C}\)) defines a one‑to‑one mapping \(\nabla\Phi: \mathcal{D}\to\mathcal{X}^*\). The gradient descent step is performed in the dual space: \(\theta_{s+1} = \nabla\Phi(x_s) - \eta g_s\), where \(g_s\in\partial f(x_s)\). Then one maps back via the inverse \((\nabla\Phi)^{-1}\) to obtain a primal point \(y_{s+1} = (\nabla\Phi)^{-1}(\theta_{s+1})\), and finally projects onto \(\mathcal{C}\) using the Bregman divergence. This decouples the non‑Euclidean geometry (captured by \(\Phi\)) from the function’s smoothness properties, allowing optimal rates in the appropriate norm.

Mirror descent solves \(\min_{x\in\mathcal{C}} f(x)\) iteratively as follows:

1. Initialise \(x_0 \in \mathcal{C}\).
2. For \(s = 0,1,2,\dots\):
   • Compute a subgradient \(g_s \in \partial f(x_s)\).
   • Dual update: \(\nabla\Phi(y_{s+1}) = \nabla\Phi(x_s) - \eta_s g_s\), where \(\eta_s>0\) is the step size.
   • Primal recovery: \(y_{s+1} = (\nabla\Phi)^{-1}(\nabla\Phi(y_{s+1}))\). (For standard \(\Phi\) this is explicit.)
   • Bregman projection: \(x_{s+1} = \arg\min_{x\in\mathcal{C}} D_\Phi(x, y_{s+1})\).

If \(\Phi\) is chosen as \(\frac{1}{2}\|x\|_2^2\), the dual update becomes \(y_{s+1} = x_s - \eta_s g_s\), and the Bregman projection is Euclidean projection, recovering projected gradient descent. For the negative entropy \(\Phi(x)=\sum x_i\log x_i\), the dual update gives a multiplicative rule, and the Bregman projection onto the simplex is simple renormalisation (A4.239).

In the convergence analysis of mirror descent, a crucial step bounds the Bregman divergence between \(x_s\) and the intermediate point \(y_{s+1}\). Using the dual update \(\nabla\Phi(y_{s+1}) = \nabla\Phi(x_s) - \eta g_s\) and the strong convexity of \(\Phi\) with respect to \(\|\cdot\|\) (coefficient \(\alpha\)), we have

Applying the definition of strong convexity \(\Phi(x_s) \ge \Phi(y_{s+1}) + \nabla\Phi(y_{s+1})^\top(x_s-y_{s+1}) + \frac{\alpha}{2}\|x_s-y_{s+1}\|^2\) and rearranging, one obtains

On the other hand, by Hölder’s inequality, \(\eta g_s^\top (x_s - y_{s+1}) \le \eta \|g_s\|_* \|x_s - y_{s+1}\|\). From the update relation \(\nabla\Phi(y_{s+1})-\nabla\Phi(x_s) = -\eta g_s\), one can also derive an upper bound on \(D_\Phi(x_s, y_{s+1})\) via the three‑point identity (A4.229), leading after algebraic manipulations to a term of the form \(a\|x_s-y_{s+1}\| - \frac{\alpha}{2}\|x_s-y_{s+1}\|^2\) which is maximised by choosing the optimal \(\|x_s-y_{s+1}\|\). The elementary inequality \(a t - \frac{\alpha}{2}t^2 \le \frac{a^2}{2\alpha}\) for any \(t\ge 0\) then gives the bound \(D_\Phi(x_s, y_{s+1}) \le \frac{\eta^2}{2\alpha}\|g_s\|_*^2\). This inequality is the key to telescoping the Bregman divergences and obtaining the convergence rate.

The mirror descent update can be written as a single proximal (or Bregman proximal) step. Starting from the dual update and the definition of Bregman projection, one can show that

Indeed, the optimality condition for this minimisation is \(\nabla\Phi(x_{s+1}) = \nabla\Phi(x_s) - \eta_s g_s + \nu\), where \(\nu\) is a normal cone term that enforces the constraint. This matches exactly the mirror descent update with the Bregman projection absorbing the constraint. This proximal formulation unifies mirror descent with other first‑order methods: it penalises moving far from \(x_s\) in the Bregman sense, while simultaneously minimising the local linear approximation of \(f\). When \(\Phi = \frac{1}{2}\|\cdot\|_2^2\), it recovers the standard proximal gradient descent update.

Choose \(\Phi(x) = \frac{1}{2}\|x\|_2^2\). Then \(\nabla\Phi(x)=x\), and the Bregman divergence is \(D_\Phi(y,x)=\frac{1}{2}\|y-x\|_2^2\). The mirror descent update:

1. Dual: \(\nabla\Phi(y_{s+1}) = \nabla\Phi(x_s) - \eta_s g_s \;\Longrightarrow\; y_{s+1} = x_s - \eta_s g_s\).
2. Primal projection: \(x_{s+1} = \arg\min_{x\in\mathcal{C}} D_\Phi(x, y_{s+1}) = \arg\min_{x\in\mathcal{C}} \frac{1}{2}\|x - y_{s+1}\|_2^2 = \pi_{\mathcal{C}}(y_{s+1})\).

Thus mirror descent coincides exactly with projected subgradient descent. The strong convexity parameter of \(\Phi\) with respect to \(\|\cdot\|_2\) is \(\alpha=1\), giving the bound \(D_\Phi(x_s,y_{s+1}) \le \frac{\eta^2}{2}\|g_s\|_2^2\), and the standard \(O(LR/\sqrt{k})\) rate follows.

For optimisation over the simplex \(\Delta_n = \{x\ge 0, \sum_i x_i=1\}\), a natural mirror map is the negative entropy: \(\Phi(x) = \sum_{i=1}^n x_i \log x_i\) (with domain \(x>0\), extended continuously to the boundary). Its gradient is \(\nabla\Phi(x) = (1+\log x_1,\dots,1+\log x_n)\), so the dual update \(\nabla\Phi(y_{s+1}) = \nabla\Phi(x_s) - \eta g_s\) becomes

Thus each coordinate is scaled multiplicatively by the exponentiated negative gradient. This is the exponentiated gradient or multiplicative weights update. The subsequent Bregman projection onto the simplex (A4.239) simply normalises: \(x_{s+1} = y_{s+1} / \|y_{s+1}\|_1\). This algorithm is central to boosting (AdaBoost), online learning (Hedge, Weighted Majority), and solving zero‑sum games.

For \(\Phi(x)=\sum_i x_i\log x_i\), the Bregman divergence is

If both \(x\) and \(y\) lie on the simplex (\(\sum_i x_i = \sum_i y_i = 1\)), the last term vanishes, and the divergence reduces to the Kullback–Leibler divergence: \(D_\Phi(y,x) = \sum_i y_i \log(y_i/x_i) = \mathrm{KL}(y\|x)\). Thus, for probability vectors, the Bregman projection with respect to negative entropy is exactly information projection: find the point in the constraint set that is closest in KL divergence. This connection to information theory makes mirror descent especially well‑suited to problems over the simplex, and the analysis relies on Pinsker’s inequality to relate KL divergence to the \(\ell_1\) norm.

For the negative entropy \(\Phi\), the Bregman projection of a positive vector \(y\) onto the simplex \(\Delta_n\) has a closed form. We solve

By introducing a Lagrange multiplier for the sum constraint, one obtains the optimality condition \(1+\log x_i - \log y_i - \lambda = 0\) for all \(i\), giving \(x_i \propto y_i\). The normalisation constraint then forces \(x_i = y_i / \sum_j y_j\). Thus, the Bregman projection onto the simplex is simply renormalisation:

This simplicity makes the negative entropy mirror map extremely computationally attractive: after the multiplicative update, a single normalisation step maintains feasibility.

This is the key geometric property that gives mirror descent with negative entropy its dimension‑independent convergence rate. The Lipschitz constant of the loss gradient measured in the dual \(\ell_\infty\) norm is often \(O(1)\) (e.g., for boosting), and the diameter of the simplex in \(\ell_1\) is \(2\). Combined with the \(1\)-strong convexity, the mirror descent bound becomes \(O(\sqrt{\log n / k})\) (the \(\log n\) arises from the dual norm of the gradient, which can be bounded by the maximum coordinate). Pinsker’s inequality thus bridges the Bregman divergence, KL divergence, and the \(\ell_1\) norm, completing the analysis.

For mirror descent with negative entropy \(\Phi(x)=\sum_{i=1}^d x_i\log x_i\) on the simplex \(\Delta_d\), the quantity \(R^2\) that bounds the initial Bregman divergence to the optimum is

The maximum of \(\Phi\) on the simplex is \(0\) (attained at any vertex, where one coordinate is \(1\) and the rest \(0\), with limit \(0\log 0 = 0\)). The minimum is achieved at the uniform distribution \(x_i = 1/d\), giving \(\Phi(1/d,\dots,1/d) = \sum_i (1/d)\log(1/d) = -\log d\). Hence

Thus, for any starting point \(x_0\in\Delta_d\) and optimum \(x^*\), we have \(D_\Phi(x^*,x_0) \le \log d\). This dimension‑dependent (but logarithmic) bound enters the mirror descent convergence rate as the complexity measure, replacing the Euclidean diameter.

Under the following conditions:

• The feasible set is the simplex \(\Delta_d\) (an \(\ell_1\) ball).
• The subgradients of the loss are bounded in \(\ell_\infty\) norm: \(\|g\|_\infty \le L\) for all \(g\in\partial f(x)\), \(x\in\Delta_d\).
• The mirror map is the negative entropy, which is \(1\)-strongly convex with respect to \(\|\cdot\|_1\) on \(\Delta_d\) (by Pinsker's inequality).

Mirror descent with step size chosen appropriately achieves, after \(k\) iterations,

The bound depends only logarithmically on the dimension \(d\), which is exponentially better than the \(O(L\sqrt{d/k})\) Euclidean bound that would result from the \(\ell_2\) Lipschitz constant blowing up to \(\sqrt{d}L\). This rate is obtained by combining the general mirror descent guarantee with \(R^2 = \log d\) and the dual norm bound \(\|g\|_* = \|g\|_\infty \le L\).

Boosting (e.g., AdaBoost) minimises a convex surrogate loss (exponential or logistic) over the simplex of size \(N\) (the number of weak learners). The gradient with respect to the weight vector \(\alpha\) has each coordinate bounded by a constant (typically \(L=1\)), so the \(\ell_\infty\) norm of the subgradient is \(O(1)\). Mirror descent with negative entropy thus yields the rate \(f(\bar\alpha_k) - f^* \le C \sqrt{\frac{\log N}{k}}\). To achieve excess risk \(\epsilon = 1/n\), we need \(k \approx \frac{\log N}{\epsilon^2} = n^2 \log N\) iterations. In contrast, projected subgradient descent with Euclidean distance would require \(k \approx N n^2\) iterations due to the \(\ell_2\) Lipschitz constant of order \(\sqrt{N}\). The exponential improvement in dimension makes mirror descent the method of choice for boosting and other large‑scale problems over the simplex.

Negative entropy is not the only choice for \(\ell_1\) geometry. The family of potentials \(\Phi(x) = \frac{1}{p}\|x\|_p^p\) for \(p>1\) is strongly convex with respect to the \(\ell_1\) norm when \(p\) is close to \(1\). Specifically, for \(p = 1 + \frac{1}{\log d}\), \(\Phi\) is strongly convex on the \(\ell_1\) ball with parameter roughly \(1/(2\log d)\). The Bregman divergence then behaves similarly to the squared \(\ell_2\) distance but adapted to the \(\ell_1\) geometry. The resulting mirror descent algorithm—called \(p\)-norm mirror descent—achieves a convergence rate of \(O(\sqrt{L^2 \log d / k})\) when the gradients are bounded in \(\ell_\infty\), matching the rate of the entropy-based method up to constants. This shows that many potential functions can be used to exploit the geometry, and the choice may be guided by computational simplicity (e.g., closed‑form Bregman projections).

In stochastic convex optimisation, the objective is an expectation over a random variable \(Z\):

where \(\ell(\cdot, z)\) is convex in \(x\) for every \(z\), and the feasible set is a closed convex set \(\mathcal{C}\). The learner does not have direct access to \(f(x)\) or its gradient; at each iteration, it draws an independent sample \(Z_t\) from \(\mathcal{D}\) and receives a subgradient \(g_t \in \partial_x \ell(x_t, Z_t)\), which is an unbiased estimate of a subgradient of \(f\): \(\mathbb{E}[g_t \mid x_t] \in \partial f(x_t)\). The goal is to generate a sequence \(x_t\) such that the expected function value \(\mathbb{E}[f(\bar x_k)]\) approaches \(\min_\mathcal{C} f(x)\). This setting encompasses empirical risk minimisation when the data distribution is the empirical distribution of a finite training set.

Many learning problems are instances of stochastic convex optimisation:

• Boosting: Minimise \(\frac{1}{n}\sum_{i=1}^n \phi(-y_i h_\alpha(x_i))\) over \(\alpha\) in the simplex. Here \(Z\) is the index \(i\) of a training example, and \(\ell(\alpha, i) = \phi(-y_i h_\alpha(x_i))\).
• Linear regression: Minimise \(\frac{1}{n}\sum_{i=1}^n (y_i - w^\top x_i)^2\) over \(w\). The loss \(\ell(w, (x_i,y_i)) = \frac{1}{2}(y_i - w^\top x_i)^2\) (or with an additional regulariser). The stochastic gradient is \(-(y_i - w^\top x_i)x_i\).
• Maximum likelihood: Minimising the negative log‑likelihood \(-\frac{1}{n}\sum_{i=1}^n \log p(x_i; \theta)\) corresponds to KL divergence minimisation between the empirical distribution and the model. Each term is \(\ell(\theta, x_i)\).

In all cases, stochastic gradient methods use one or a mini‑batch of examples per iteration, enabling scalability to large datasets.

For a finite training set of size \(n\), the empirical risk \( \frac{1}{n}\sum_{i=1}^n \ell(h(x_i), y_i) \) can be written as an expectation over a uniformly random index \(I \in \{1,\dots,n\}\):

This external randomization transforms the deterministic sum into a stochastic objective. At each iteration of stochastic gradient descent, one draws \(I_t\) uniformly and uses the subgradient of the \(I_t\)-th loss term. This provides an unbiased estimate of the full empirical gradient. The analysis of SGD then bounds the optimisation error in terms of the number of iterations, which is decoupled from \(n\). Multiple passes over the data (epochs) correspond to drawing indices with replacement, which is equivalent to the i.i.d. stochastic setting with \(\mathcal{D}\) being the empirical distribution.

In statistical learning theory, the statistical limit refers to the number of fresh training examples drawn from the population distribution required to achieve a target excess risk. This is typically a one‑pass setting: each example is used once and then discarded. In contrast, when optimising an empirical risk over a finite dataset, we often perform multiple passes (epochs) over the same data, which amounts to minimising the empirical risk to high precision. The number of computational iterations (SGD steps) can exceed the sample size \(n\). While this does not improve the statistical generalisation bound beyond the irreducible estimation error, it can reduce the optimisation error to be negligible compared to the statistical error. The theory separates these two aspects: optimisation error (how close we get to the minimiser of the empirical risk) and generalisation error (how close the empirical minimiser is to the true risk).

Stochastic Gradient Descent (SGD) solves \(\min_{x\in\mathcal{C}} f(x) = \mathbb{E}[\ell(x,Z)]\) as follows:

Initialise x_0 ∈ C.
For t = 0,1,2,...,k-1:
    Sample Z_t ~ D independent of past.
    Obtain g_t ∈ ∂_x ℓ(x_t, Z_t)   (unbiased: E[g_t | x_t] ∈ ∂f(x_t))
    Choose step size η_t > 0.
    Update x_{t+1} = π_C( x_t - η_t g_t )
End
Return x̄_k = (1/k) ∑_{t=1}^k x_t  (or last iterate with averaging)
    

The projection \(\pi_{\mathcal{C}}\) is the Euclidean projection (or a Bregman projection if using mirror descent). This algorithm applies to both population risk minimisation (when samples are drawn from the true distribution) and empirical risk minimisation (by setting \(\mathcal{D}\) to the empirical distribution and sampling with replacement).

The expectation is over the random draws \(Z_0,\dots,Z_{k-1}\). This matches the deterministic projected subgradient rate, but now the gradient is noisy; the step size must be carefully controlled to balance progress and noise variance.

Proof sketch. As in the deterministic case, for any \(x^*\in\mathcal{C}\),

Take conditional expectation \(\mathbb{E}[\cdot\mid x_t]\). By unbiasedness, \(\mathbb{E}[g_t\mid x_t] = \tilde g_t \in \partial f(x_t)\). The subgradient inequality gives \(\tilde g_t^\top(x_t - x^*) \ge f(x_t) - f(x^*)\). Also, by the variance bound, \(\mathbb{E}[\|g_t\|^2 \mid x_t] \le L^2\). Thus,

Rearrange and take total expectation:

Summing from \(t=0\) to \(k-1\) yields a telescoping bound:

By convexity, \(f(\bar x_k) \le \frac{1}{k}\sum_{t=1}^k f(x_t)\). With the choice \(\eta = \frac{R}{L\sqrt{k}}\), the right‑hand side becomes \(R^2 + k\cdot \frac{R^2}{k} = 2R^2\), so \(\mathbb{E}[f(\bar x_k)-f(x^*)] \le \frac{R^2}{2\eta k} = \frac{LR}{2\sqrt{k}}\). Adjusting constants yields the claimed \(O(LR/\sqrt{k})\) bound.

Stochastic Mirror Descent (SMD) extends mirror descent to stochastic optimisation where we only have access to an unbiased subgradient estimate \(\tilde g_s\) of \(\nabla f(x_s)\) (or a subgradient of \(\ell(\cdot, Z_s)\)). The update is identical to deterministic mirror descent but with a noisy gradient:

1. At iteration \(s\), draw an i.i.d. sample \(Z_s\) and compute \(\tilde g_s \in \partial_x \ell(x_s, Z_s)\) satisfying \(\mathbb{E}[\tilde g_s \mid x_s] \in \partial f(x_s)\).
2. Dual update: \(\nabla\Phi(y_{s+1}) = \nabla\Phi(x_s) - \eta_s \tilde g_s\).
3. Recover \(y_{s+1} = (\nabla\Phi)^{-1}(\nabla\Phi(y_{s+1}))\).
4. Bregman projection: \(x_{s+1} = \arg\min_{x\in\mathcal{C}} D_\Phi(x, y_{s+1})\).

When \(\Phi(x)=\frac{1}{2}\|x\|_2^2\), this recovers stochastic projected gradient descent. When \(\Phi(x)=\sum x_i \log x_i\), it yields exponentiated stochastic gradient. The stochastic noise is managed by averaging and appropriate step size schedules.

If the gradient variance is bounded by \(\sigma^2\) (i.e., \(\mathbb{E}[\|\tilde g_s - \mathbb{E}[\tilde g_s]\|_*^2]\le\sigma^2\)), the bound can be refined to \(O\left(\frac{LR}{\sqrt{\alpha k}} + \frac{\sigma R}{\sqrt{\alpha k}}\right)\). The rate matches the deterministic mirror descent rate up to constants, with the noise absorbed by the step size scaling.

The key step in proving SMD convergence is bounding the Bregman divergence between the primal point \(x_s\) and the intermediate dual‑mapped point \(y_{s+1}\). From the update \(\nabla\Phi(y_{s+1}) - \nabla\Phi(x_s) = -\eta \tilde g_s\) and the definition of Bregman divergence, using the three‑point identity (A4.229) with \(x=x_s\), \(y=y_{s+1}\), \(z=x_s\) (or via direct manipulation) we have

Using \(\nabla\Phi(y_{s+1}) = \nabla\Phi(x_s) - \eta \tilde g_s\), we rewrite:

Wait, this becomes circular; a standard derivation uses the strong convexity of \(\Phi\). By \(\alpha\)-strong convexity, \(\Phi(y_{s+1}) \ge \Phi(x_s) + \nabla\Phi(x_s)^\top(y_{s+1}-x_s) + \frac{\alpha}{2}\|y_{s+1}-x_s\|^2\). Hence

But \(\nabla\Phi(x_s)-\nabla\Phi(y_{s+1}) = \eta \tilde g_s\). Thus

By Hölder's inequality, \(\eta \tilde g_s^\top (x_s-y_{s+1}) \le \eta \|\tilde g_s\|_* \|x_s-y_{s+1}\| \le \frac{\eta^2}{2\alpha}\|\tilde g_s\|_*^2 + \frac{\alpha}{2}\|x_s-y_{s+1}\|^2\) (using \(ab \le \frac{a^2}{2\alpha} + \frac{\alpha}{2}b^2\)). Plugging back, the \(\frac{\alpha}{2}\|x_s-y_{s+1}\|^2\) terms cancel, yielding

This inequality bounds the progress in the dual space. Combined with a telescoping sum of Bregman divergences and the projection step (which does not increase Bregman divergence to \(x^*\)), we obtain the convergence rate.

Stochastic Coordinate Descent (SCD) exploits coordinate‑wise structure when computing a full gradient is expensive but a single coordinate gradient is cheap. For a differentiable function \(f:\mathbb{R}^d\to\mathbb{R}\), at each iteration, pick a coordinate index \(I \in \{1,\dots,d\}\) uniformly at random. The stochastic gradient is

where \(e_I\) is the \(I\)-th standard basis vector. This is an unbiased estimate of \(\nabla f(x)\): \(\mathbb{E}_I[\tilde g] = \sum_{i=1}^d \frac{1}{d} \cdot d \cdot \frac{\partial f}{\partial x_i} e_i = \nabla f(x)\). The factor \(d\) compensates for the probability \(1/d\) of selecting coordinate \(i\). The algorithm then takes a step \(x_{t+1} = x_t - \eta \tilde g\) (or with projection). SCD is especially effective when coordinate gradients are cheap (e.g., sparse data in SVMs, Lasso) and when the Lipschitz constant per coordinate is uniform.

For a convex, \(L\)-Lipschitz function with respect to \(\|\cdot\|_2\) (so coordinate‑wise Lipschitz constant \(L_i \le L\)), and a bounded feasible set of diameter \(R\), SCD with step size \(\eta = \frac{R}{L\sqrt{dk}}\) achieves

Equivalently, to achieve accuracy \(\epsilon\), \(k \approx L^2 R^2 d / \epsilon^2\) iterations are needed. This is a factor \(d\) worse in iteration count compared to full gradient descent (\(O(1/\epsilon^2)\) for stochastic). However, each SCD iteration updates only one coordinate and costs \(O(1)\) (if a coordinate gradient can be computed in \(O(1)\)), while full gradient descent costs \(O(d)\). Thus the total work to reach accuracy \(\epsilon\) is roughly \(O(d \cdot k_{\text{SCD}}) = O(d^2 / \epsilon^2)\) vs. \(O(d / \epsilon^2)\) for full gradient descent—a factor \(d\) worse. For very large \(d\) where coordinate‑wise operations are much cheaper than full gradients, SCD can be competitive. In practice, SCD shines when the data are sparse and coordinate gradients are \(O(\text{nnz}/d)\) on average.

In stochastic optimisation, the true function \(f\) is unknown (only stochastic estimates are available). Thus, one cannot directly select the best iterate based on function value (as one might with a validation set). Two common strategies for the final output are:

• Averaging \(\bar x_k = \frac{1}{k}\sum_{t=1}^k x_t\): By convexity, \(f(\bar x_k) \le \frac{1}{k}\sum_{t=1}^k f(x_t)\). This is the standard choice for both deterministic and stochastic convergence proofs, and it yields an \(O(1/\sqrt{k})\) guarantee. It requires storing all iterates or updating a running average.
• Single random iterate or final iterate: Under some conditions (e.g., strong convexity, decreasing step sizes), the last iterate also converges, but the rate may be slower. In practice, using the average or the last iterate both work; averaging is theoretically more robust because it dampens oscillations caused by noise.

For non‑convex problems, averaging is less meaningful, and one often reports the best iterate on a validation set or uses Polyak averaging (average of recent iterates). The choice of output strategy is crucial to guarantee the theoretical rate.

In online learning, data arrive in a stream, and the learner must make a prediction at each step before seeing the true label (or loss). The framework contrasts with batch learning, where a fixed training set is available upfront. Online learning models many real‑world tasks:

• Online shortest path: At each time step, a route is chosen for a vehicle; afterwards, edge weights (travel times) are revealed.
• Dynamic pricing: A seller sets a price for each arriving customer, then learns whether the customer buys.
• Sequential investment: An investor allocates wealth among assets each day, then observes returns.

The performance metric is regret: the difference between the cumulative loss of the learner and the loss of the best fixed decision in hindsight. The goal is to achieve sublinear regret \(R_n = o(n)\), meaning the average performance approaches that of the optimal fixed strategy.

Online shortest path: A graph with edges \(e\in E\). At each round \(t\), the learner chooses a path \(P_t\) from a set of allowed paths. Then a weight vector \(w_t \in [0,1]^{|E|}\) is revealed. The loss is \(\sum_{e\in P_t} w_t(e)\). The regret is measured against the best fixed path in hindsight. This can be modeled as a linear optimisation problem over a convex set: the path set is discretized, or one works in the flow polytope and uses online linear optimisation.

Dynamic pricing: Each customer has a valuation \(v_t\) drawn from an unknown distribution. The seller posts a price \(p_t\). If \(p_t \le v_t\), the sale occurs and the reward is \(p_t\); otherwise, it's 0 (or penalty). The loss (negative revenue) is \(-\text{revenue}\). The regret compares to the best fixed price. The feedback is partial (only the outcome of the chosen price). This is a bandit problem.

Sequential investment (portfolio): There are \(d\) assets. Each day \(t\), the investor chooses a distribution \(p_t \in \Delta_d\) of wealth across assets. Then a return vector \(r_t \in \mathbb{R}_+^d\) is observed. The wealth multiplies by \(p_t^\top r_t\). This is equivalent to maximising log‑wealth, which is an online convex optimisation problem with the negative logarithm of the return.

Online learning can be analysed under two different models for the data:

• Statistical (stochastic) model: The data pairs \((x_t, y_t)\) are drawn i.i.d. from a fixed distribution. In this setting, online algorithms can be converted to batch learners via online‑to‑batch conversions, and the regret is related to the generalisation error. For example, SGD is an online algorithm; its online regret bound implies a batch generalisation bound after averaging.
• Adversarial model: No distributional assumption; the sequence of losses can be chosen arbitrarily, possibly depending on the learner's past decisions (oblivious adversary) or even adaptively. This worst‑case view leads to minimax regret bounds. Algorithms like Hedge (multiplicative weights) achieve \(O(\sqrt{T \log K})\) regret against an oblivious adversary, which is optimal. The adversarial model is more robust but yields slower rates than the stochastic case (where \(O(\log T)\) regret is possible).

This distinction mirrors the difference between agnostic PAC learning (distribution‑free, worst‑case) and the realizable/low‑noise statistical setting.

In the prediction with expert advice framework, there is a set of \(K\) experts. At each round \(t\), the learner chooses a probability distribution \(p_t \in \Delta_K\) over experts (or directly an action \(a_t\)). Then a loss vector \(z_t \in [0,1]^K\) is revealed, where \(z_t(i)\) is the loss of expert \(i\) at time \(t\). The learner's loss is either the realised loss of a randomly sampled expert (expected loss \(p_t^\top z_t\)) or the loss of the convex combination itself. The cumulative regret after \(n\) rounds is

The goal is to guarantee that \(R_n\) grows sublinearly in \(n\), i.e., \(R_n = o(n)\). If the losses are convex in the action, one may consider a continuous action set \(A\) (e.g., a convex set in \(\mathbb{R}^d\)) and define regret against the best action in \(A\). This general framework unifies many online algorithms.

When the learner plays a mixed strategy \(p_t \in \Delta_K\) and incurs the expected loss \(\ell(p_t, z_t) = p_t^\top z_t\), the loss is linear in \(p_t\). This formulation allows the use of convex optimisation tools. The regret then becomes

since the minimizer of a linear function over the simplex is a vertex—one of the experts. Thus, competing against the best convex combination is equivalent to competing against the best single expert. Algorithms like Hedge (exponentiated gradient) maintain \(p_t\) and update multiplicatively: \(p_{t+1}(i) \propto p_t(i) \exp(-\eta z_t(i))\). This update is precisely online mirror descent with negative entropy over the simplex, achieving regret \(O(\sqrt{T \log K})\).

The simplest online learning strategy is Follow the Leader (FTL): at each round \(t\), play the point that would have minimised the cumulative loss on the past \(t-1\) rounds:

Because the objective is linear in \(p\), the minimiser is a vertex of the simplex, i.e., one of the \(K\) experts. FTL seems reasonable—use what has worked best so far—but it can suffer linear regret in adversarial settings. A classic counterexample: let \(K=2\) and the loss vectors alternate as \(z_1=(1,0), z_2=(0,1), z_3=(1,0), z_4=(0,1),\dots\). FTL will keep switching to the expert with zero loss on the previous round, incurring a loss of 1 every round, while the best fixed expert in hindsight has cumulative loss about \(n/2\). The regret of FTL is roughly \(n/2\), i.e., linear. This instability arises because FTL overreacts to the most recent observation. To fix this, we must add regularisation or perturbation.

The Exponential Weights (Hedge) algorithm maintains a probability distribution over \(K\) experts. Starting with uniform \(p_1 = (1/K,\dots,1/K)\), at each round \(t\):

• Play expert \(j\) with probability \(p_{t,j}\) (or play the convex combination).
• Observe loss vector \(z_t \in [0,1]^K\) (loss of each expert).
• Update weights multiplicatively: \(w_{t+1,j} = w_{t,j} \cdot \exp(-\eta z_{t,j})\), where \(\eta>0\) is a learning rate.
• Renormalise: \(p_{t+1,j} = w_{t+1,j} / \sum_{i=1}^K w_{t+1,i}\).

Equivalently, the weight of expert \(j\) at time \(t\) is \(w_{t,j} = \exp(-\eta \sum_{s=1}^{t-1} z_{s,j})\), i.e., exponential cumulative loss. The probability of selecting expert \(j\) is proportional to this weight. This algorithm is a special case of online mirror descent with negative entropy over the simplex, and it is also known as the Hedge algorithm in the context of prediction with expert advice.

Thus, the average regret per round is at most \(\sqrt{2\log K / n}\), which tends to zero, i.e., sublinear regret. The bound shows that the number of experts \(K\) only affects the regret logarithmically.

An elegant proof of the Hedge regret bound proceeds by tracking the total weight \(W_t = \sum_{j=1}^K w_{t,j}\). Initially \(W_1 = K\). After round \(t\),

Using Hoeffding's lemma (A4.29) for the random variable \(Z\) taking value \(z_{t,j}\) with probability \(p_{t,j}\), and bounded in \([0,1]\), we have

Hence \(W_{t+1} \le W_t \exp(-\eta\, p_t^\top z_t + \eta^2/8)\). Telescoping over \(t=1,\dots,n\) gives

On the other hand, for any expert \(j\), \(W_{n+1} \ge w_{n+1,j} = \exp(-\eta \sum_{t=1}^n z_{t,j})\). Combining these inequalities and taking logs yields

The constant \(\frac{1}{8}\) replaces the \(\frac{1}{2}\) from the mirror descent proof (due to the tighter Hoeffding inequality for the exponential compared to the quadratic bound from strong convexity). In practice, the difference is minor.

Follow the Perturbed Leader (FPL) overcomes the instability of FTL by adding random noise to the cumulative losses before selecting the leader. In round \(t\), the algorithm:

1. Draws a random perturbation vector \(\xi \in \mathbb{R}^K\) whose coordinates are independent uniform on \([0, 1/\eta]\). (Sometimes the distribution is chosen as Laplace or exponential for tighter analysis.)
2. Chooses the expert that minimises the perturbed cumulative loss: \(p_t = \arg\min_{j} \bigl( \sum_{s=1}^{t-1} z_{s,j} + \xi_j \bigr)\). (As a pure action; the mixed version plays one expert.)

The perturbation acts as a regulariser: it prevents the algorithm from switching too rapidly in response to a single round's loss, because an expert must beat not only the past but also the noise. FPL is a randomised algorithm; its expected regret against an oblivious adversary is bounded. The analysis uses a clever coupling argument: the cumulative loss of FPL is compared to the best fixed expert in hindsight plus the perturbation gap.

In the oblivious adversary model, the entire sequence of loss vectors \(z_1,\dots,z_n\) is chosen before the game begins, without observing the learner’s randomisation. This is a weaker adversary than the adaptive one, but it is the standard setting for FPL analysis. Because the adversary does not see the randomness, the perturbation is independent of the sequence. The expected regret is analysed by comparing the loss of FPL to that of the best expert in hindsight. For FPL with uniform perturbation, a key insight is that the expected loss of the perturbed leader is close to the expected loss of the true leader (the best expert), with an additional cost proportional to the perturbation magnitude. The analysis uses a lemma known as "Be‑the‑Leader" (A4.269) and properties of the perturbation distribution.

Proof by induction. For \(n=1\), \(p_1^*\) is arbitrary (minimiser over empty set), and the inequality holds trivially with the same argument. Assume true for \(n-1\). Then for sequence of length \(n\),

where \(p_{n-1}^*\) is the FTL optimum for the first \(n-1\) losses. Since \(p_{n-1}^*\) minimises \(\sum_{t=1}^{n-1} \ell(p, z_t)\), it is at most as good as \(p_n^*\) on those \(n-1\) losses. Hence \(\sum_{t=1}^{n-1} \ell(p_{n-1}^*, z_t) \le \sum_{t=1}^{n-1} \ell(p_n^*, z_t)\). Adding \(\ell(p_n^*, z_n)\) to both sides yields the desired inequality for \(n\). This lemma shows that if we could always use the current round's FTL (which uses past data only), its cumulative loss is at most the cumulative loss of the offline optimum—the algorithm that plays the same fixed action at every round. This is counter‑intuitive but true because the offline optimum is not tailored to the particular round. The lemma is used in the analysis of FPL to bound the expected loss of the actual FTL (which uses perturbation) relative to the offline optimum.

Proof idea (box geometry). Let \(L_t(j) = \sum_{s=1}^{t-1} z_{s,j}\) be the cumulative loss before round \(t\). FPL chooses \(j_t = \arg\min_j (L_t(j) + \xi_j)\). By the Be‑the‑Leader lemma (applied to the perturbed sequence \(\tilde z_t(j) = z_t(j) + \xi_j - \xi_j'\) where \(\xi'\) is a fresh sample?—the standard proof is more involved). A cleaner approach: the expected regret of FPL can be bounded by the sum over \(t\) of the probability that the best expert is not chosen plus the perturbation cost. Using the fact that the perturbation is uniform in a box of side \(1/\eta\), one can show that the expected number of leader changes is small. The classic bound for FPL with uniform perturbation and losses bounded by \(L=1\) is \(\mathbb{E}[R_n] \le \frac{K}{\eta} + \eta n\). Optimising \(\eta = \sqrt{K/n}\) gives \(\mathbb{E}[R_n] \le 2\sqrt{n K}\). The constant 2 may be adjusted; the original Kalai–Vempala bound is \(\mathbb{E}[R_n] \le 2\sqrt{2 n K}\) for \(L=1\) with a specific perturbation. The key geometric idea is that the perturbed leader is the minimiser of a random shifted objective; the probability that two experts swap as leader is bounded by \(\eta\) times the total variation distance, which is \(O(\eta)\). Summing over \(K\) experts yields the \(K/\eta\) term.