Statistical Learning Theory Vocabulary

Comprehensive vocabulary flashcards covering fundamental concepts, definitions, and theorems from Statistical Learning Theory.

Empirical Risk Minimization (ERM)

A learning principle that selects a hypothesis from a hypothesis class $\mathcal{H}$ that minimizes the empirical risk (training loss) over a dataset $Z$, denoted $\text{ERM}(Z) \in \arg\min_{h \in \mathcal{H}} L_Z(h)$.

Excess Error

The difference between the population risk of a learned estimator $\hat{h}_Z$ and the irreducible Bayes risk, decomposed as $L_{\mathcal{D}}(\hat{h}_Z) - L_{\text{bayes}} = (L_{\mathcal{D}}(\hat{h}_Z) - \inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h)) + (\inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h) - L_{\text{bayes}})$.

Estimation Error

The statistical error $L_{\mathcal{D}}(\hat{h}_Z) - \inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ that arises from using a finite sample-based learning algorithm $\hat{h}_Z$ rather than the optimal predictor in the hypothesis class $\mathcal{H}$.

Approximation Error

The error component $\inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h) - L_{\text{bayes}}$ that measures how well the chosen hypothesis class $\mathcal{H}$ can approximate the ideal Bayes predictor, independent of sample size $m$ or sample $Z$.

Uniform Convergence

The property that the empirical risk converges to the population risk uniformly across all hypotheses in $\mathcal{H}$, ensuring that $\sup_{h \in \mathcal{H}} [L_{\mathcal{D}}(h) - L_Z(h)] \le \varepsilon$.

Subgaussian Random Variable

A random variable $x$ with mean $\mu = \mathbb{E}[x]$ satisfying $\mathbb{E}[e^{\lambda(x-\mu)}] \le e^{\frac{1}{2}\lambda^2\sigma^2}$ for all $\lambda \in \mathbb{R}$, abbreviated $\mathcal{SG}(\sigma)$.

Hoeffding's Lemma

The result stating that if a random variable $x$ is bounded almost surely such that $\Pr(a \le x \le b) = 1$, then $x$ is subgaussian with parameter $\frac{b-a}{2}$, written $\mathcal{SG}\left(\frac{b-a}{2}\right)$.

Metric

A function $\rho : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ that satisfies four conditions for all $x, y, z \in \mathcal{X}$: (i) $\rho(x, x) = 0$; (ii) if $x \ne y$, then $\rho(x, y) > 0$; (iii) $\rho(x, y) = \rho(y, x)$; and (iv) $\rho(x, z) \le \rho(x, y) + \rho(y, z)$.

M-Lipschitz Function

A function $f : \mathcal{X} \rightarrow \mathcal{Y}$ satisfying $\rho_{\mathcal{Y}}(f(x), f(x')) \le M \rho_{\mathcal{X}}(x, x')$ for all $x, x' \in \mathcal{X}$, where the smallest such constant $M$ is the Lipschitz constant $\|f\|_{\text{Lip}}$.

$\eta$-Cover

A subset $T \subseteq U$ of a metric space such that $U \subseteq \bigcup_{t \in T} B_\eta(t)$, where the cardinality of the smallest such set $T$ is the covering number $N_{\text{cov}}^\eta(U)$.

$\eta$-Separated Set

A subset of a metric space where every pair of distinct points satisfies $\rho(u_i, u_j) > \eta$, whose maximum cardinality is denoted $N_{\text{sep}}^\eta(U)$.

Rademacher Complexity

A measure of the capacity of a set $V \subseteq \mathbb{R}^m$ to correlate with random binary noise, defined as $\text{Rad}(V) = \mathbb{E}_{R \sim \text{Unif}(\pm 1)^m} \left[\sup_{v \in V} \frac{1}{m} \sum_{i=1}^m r_i v_i\right]$.

Talagrand's Contraction Lemma

A lemma stating that if $\phi : \mathbb{R}^m \rightarrow \mathbb{R}^m$ is defined coordinatewise by $\phi(t) = (\phi_1(t_1), \dots, \phi_m(t_m))$ where each $\phi_i$ is $M$-Lipschitz, then $\text{Rad}(\phi \circ V) \le M \text{Rad}(V)$.

McDiarmid's Inequality

A concentration theorem stating that if a function $f(x_1, \dots, x_m)$ of independent variables changes by at most $c_i$ when coordinate $i$ is replaced, then $f$ is subgaussian with parameter $\frac{1}{2}\sqrt{\sum_{i=1}^m c_i^2}$.

Shattering

The condition in which a hypothesis class $\mathcal{H}$ can achieve all $2^m$ possible binary labellings on a given finite set of $m$ instances $X$, meaning $|\mathcal{H}|X| = 2^m$.

VC Dimension

The cardinality of the largest finite instance set that can be shattered by a hypothesis class $\mathcal{H}$, formally $\text{VCdim}(\mathcal{H}) = \max(\{m \ge 0 : \Gamma_{\mathcal{H}}(m) = 2^m\})$.

Growth Function

The combinatorial function $\Gamma_{\mathcal{H}}(m) = \sup_{X \in \mathcal{X}^m} |\mathcal{H}|X|$ representing the maximum number of distinct labellings a hypothesis class $\mathcal{H}$ can assign to any set of $m$ instances.

Sauer-Shelah Lemma

A combinatorial theorem establishing that if $\text{VCdim}(\mathcal{H}) \le d < \infty$, then for all $m$, $\Gamma_{\mathcal{H}}(m) \le \sum_{i=0}^d \binom{m}{i}$, which is bounded by $\left(\frac{em}{d}\right)^d$ when $m \ge d$.

Agnostic PAC Learnability

The property that an algorithm $A$ can guarantee, for all $\varepsilon, \delta \in (0, 1)$ and any distribution $\mathcal{D}$, that $\Pr(L_{\mathcal{D}}(A(Z)) > \inf_{h \in \mathcal{H}} L_{\mathcal{D}}(h) + \varepsilon) \le \delta$ given at least $m(\varepsilon, \delta)$ samples.

Realizable Distribution

A data distribution $\mathcal{D}$ under which there exists a perfect predictor in the hypothesis class achieving zero risk: $\exists h^* \in \mathcal{H}$ such that $L_{\mathcal{D}}(h^*) = 0$.

Version Space

The subset of hypotheses in $\mathcal{H}$ that remain perfectly consistent with all labeled examples observed up to time $t$, defined as $\mathcal{H}_t = \{h \in \mathcal{H} : \forall i \in [t], h(x_i) = y_i\}$.

Halving Algorithm

An online learning algorithm that predicts the majority label across all hypotheses in the active version space $\mathcal{H}_{t-1}$, guaranteeing at most $\log_2 |\mathcal{H}|$ mistakes in the realizable setting.

Littlestone Dimension

The maximum depth $d$ of a complete binary game tree of instances that can be shattered by a hypothesis class $\mathcal{H}$, denoted $\text{Ldim}(\mathcal{H})$, which characterizes online mistake bounds.

Structural Risk Minimization (SRM)

An inductive principle that decomposes $\mathcal{H} = \bigcup_{k \ge 1} \mathcal{H}_k$ into nested classes with uniform convergence bounds $\varepsilon_k$ and weights $w_k$, selecting $\hat{h} \in \arg\min_{h \in \mathcal{H}} [L_Z(h) + \varepsilon_{k_h}(m, w_{k_h}\delta)]$.

Universal Hypothesis Class

A class of functions $\mathcal{H}$ on a compact space $\mathcal{X}$ that is dense in $C(\mathcal{X})$ with respect to the supremum norm, meaning any continuous function can be approximated within arbitrary $\varepsilon > 0$.

$\beta$-Quadratic Upper Bound

A condition on a differentiable function $f$ stating that for all $w, w'$, $f(w') \le f(w) + \langle \nabla f(w), w' - w \rangle + \frac{1}{2}\beta \|w' - w\|^2$.

$\beta$-Smooth Function

A continuously differentiable function $f$ whose gradient $\nabla f$ is $\beta$-Lipschitz continuous, which implies a $\beta$-quadratic upper bound on an open convex domain.

Descent Lemma

The optimization result guaranteeing that a gradient descent step $w^+ = w - \eta \nabla f(w)$ on a function with a $\beta$-quadratic upper bound decreases the objective by at least $\eta\left(1 - \frac{1}{2}\eta\beta\right)\|\nabla f(w)\|^2$.

Implicit Regularization (Implicit Bias)

The property where an unregularized optimization algorithm implicitly converges toward a specific structured minimizer (such as minimum Euclidean norm or maximum margin) among multiple empirical minimizers.

Geometric Margin

The shortest Euclidean distance from any sample point to the decision boundary of a unit-norm linear classifier $v$, given by $\rho = \min_{i \in [m]} y_i \langle x_i, v \rangle$.

Positive Definite Kernel

A symmetric function $k : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ for which there exists a Hilbert space $\mathcal{G}$ and mapping $\phi$ such that $k(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{G}}$, or equivalently, whose kernel matrix is always positive semi-definite.

Reproducing Kernel Hilbert Space (RKHS)

A Hilbert space $\mathcal{F}$ of functions endowed with an inner product satisfying the reproducing property $f(x) = \langle f, k(x, \cdot) \rangle_{\mathcal{F}}$ for all $x \in \mathcal{X}$ and $f \in \mathcal{F}$.

Representer Theorem

A theorem stating that the minimizer of an empirical loss regularized by a nondecreasing function of the RKHS norm $\mathcal{R}(\|f\|_{\mathcal{F}})$ can always be expressed as a linear combination of kernel evaluations at the training points: $f = \sum_{i=1}^m \alpha_i \phi(x_i)$.

Uniform Stability

A stability property of an algorithm $A$ where replacing any single training example changes the expected loss on any test point by at most $\beta(m)$, formally $\sup_{S, i, z, z'} |\mathbb{E}_A \ell(A(S^{(i \leftarrow z')}), z) - \mathbb{E}_A \ell(A(S), z)| \le \beta(m)$.

Regularized Loss Minimization (RLM)

A learning algorithm that optimizes the sum of the empirical risk and a regularizer $\mathcal{R}(h)$ scaled by a hyperparameter $\lambda > 0$, defined as $\arg\min_{h \in \mathcal{H}} L_S(h) + \lambda \mathcal{R}(h)$.