Statistical Learning Theory
Statistical learning theory provides the mathematical framework for understanding why and when machine learning algorithms generalize from finite training data to unseen test data. This module develops the theory from first principles, covering the fundamental quantities that govern learnability.
1. The Learning Problem
Let be the input space and the output space. We observe a dataset drawn i.i.d. from an unknown distribution over . Our goal is to find a hypothesis from some hypothesis class that minimizes the true risk:
Since is unknown, we optimize the empirical risk:
The central question of statistical learning theory is: how does the gap between empirical and true risk behave?
2. Vapnik-Chervonenkis (VC) Theory
2.1 Growth Function and VC Dimension
For a hypothesis class and a set , the restriction of to is:
The growth function measures the maximum number of distinct classifications on points:
Definition (VC Dimension): The VC dimension of is the largest such that . That is, is the largest number of points that can shatter (correctly classify all possible labelings).
2.2 Computing VC Dimension
Example 1: Consider linear classifiers in : .
The VC dimension is . To see this, note that points in general position can be shattered (each of the labelings is achievable), but points cannot by Radon's theorem.
Example 2: The class of intervals on has VC dimension 2. Two points with can be shattered: labeling choose ; labeling choose ; labeling choose ; labeling choose . But three points cannot be shattered.
2.3 The VC Inequality
Theorem (VC Inequality): For any , with probability at least over the draw of , for all :
where .
This bound decomposes into:
- Estimation error: — decreases with more samples
- Complexity term: — logarithmic in
2.4 Sample Complexity
The sample complexity for PAC learning with VC dimension and error , confidence is:
This is both sufficient (if is this large, ERM with confidence produces -accurate hypotheses) and necessary (any algorithm needs at least this many samples).
3. PAC Learning Framework
3.1 Formal Definition
Definition (PAC Learning): A hypothesis class is PAC-learnable if there exists a function and an algorithm such that for every and every distribution :
The function is called the sample complexity.
3.2 Agnostic vs Realizable PAC
- Realizable: There exists with . Sample complexity: .
- Agnostic: No assumption on . Sample complexity: .
3.3 Fundamental Theorem of Statistical Learning
Theorem: For binary classification, the following are equivalent:
- is PAC-learnable
- has finite VC dimension
- is uniform convergence learnable
- is ERM-learnable
4. Rademacher Complexity
4.1 Definition
The empirical Rademacher complexity of a class with respect to a sample is:
where are i.i.d. Rademacher random variables ().
The population Rademacher complexity is:
4.2 Key Properties
Property 1 (Monotonicity): If , then .
Property 2 (Contraction): For any contraction with and :
Property 3 (Linear class): For :
4.3 Generalization Bounds via Rademacher
Theorem: For any , with probability at least :
This bound is tighter than VC bounds in many cases and captures the geometry of the function class more precisely.
5. Margin Bounds
5.1 Definition of Margin
For a classifier , the margin on a point is:
A positive margin means correct classification; larger magnitude means higher confidence.
5.2 Margin Bound
Theorem: For linear classifiers , with probability at least :
where is the -margin empirical error.
5.3 Implications for SVMs
This bound explains why support vector machines generalize well even in very high-dimensional (or infinite-dimensional) feature spaces: the margin appears in the denominator, so maximizing the margin reduces generalization error regardless of the ambient dimension.
6. PAC-Bayes Bounds
6.1 Setting
Instead of choosing a single hypothesis , consider a randomized classifier that draws from a posterior distribution over . Let be a prior distribution (chosen independently of the data).
6.2 PAC-Bayes Theorem
Theorem (McAllester, 1999): For any prior , posterior , and , with probability at least :
where is the KL divergence between the distributions.
6.3 Interpretation
- Complexity penalty: penalizes posteriors far from the prior
- Data-dependent: Both the empirical risk and complexity are measured on
- Algorithms: PAC-Bayes bounds directly motivate stochastic regularization (e.g., dropout in neural networks can be viewed through this lens)
6.4 Tightness
PAC-Bayes bounds are known to be minimax tight for certain classes (e.g., linear classifiers with Gaussian prior), meaning no other bound can be asymptotically tighter.
7. Algorithmic Stability
7.1 Definition
An algorithm is uniformly stable with parameter if for all datasets differing in one example:
7.2 Stability-Based Generalization
Theorem (Bousquet & Elisseeff, 2002): If algorithm has stability and loss bounded in , then:
7.3 Stability of Specific Algorithms
- SVMs with regularization: Stability where is the regularization parameter
- -nearest neighbors (): Stability — each point affects only its own neighborhood
- SGD with strong convexity: Stability
8. Uniform Convergence
8.1 Definition
A class satisfies uniform convergence with rate if:
8.2 VC Classes and Uniform Convergence
For VC classes with VC dimension :
8.3 Limitations
Uniform convergence is not necessary for ERM to work. There exist classes where:
- ERM succeeds (low sample complexity)
- But uniform convergence fails
This happens with "unbounded" losses or when the hypothesis class has infinite VC dimension but is still learnable (e.g., with proper structural assumptions).
9. Connections and Comparisons
| Framework | Bound Type | Strengths |
|---|---|---|
| VC Theory | Worst-case | Distribution-free, clean |
| Rademacher | Average-case | Captures geometry |
| PAC-Bayes | Algorithm-specific | Tight, practical |
| Stability | Algorithm-specific | Direct, interpretable |
10. Code: Computing VC Dimension
import numpy as np
from itertools import product
def compute_vc_dimension_linear(X, max_d=10):
"""
Compute VC dimension empirically for linear classifiers.
Args:
X: Array of shape (m, d) where m is number of points, d is dimension
max_d: Maximum dimension to test
Returns:
Estimated VC dimension
"""
m, d = X.shape
# Try subsets of increasing size
for k in range(1, min(m, max_d) + 1):
# Generate all 2^k labelings
all_shattered = True
for labels in product([-1, 1], repeat=k):
# Try to find separating hyperplane
# Using linear programming approach
y = np.array(labels)
# Check if linearly separable
# Using a simple check: solve for w such that y_i * (w^T x_i + b) > 0
try:
from scipy.optimize import linprog
# Formulate as LP
# Variables: w (d-dimensional), b (scalar), slacks
n_vars = d + 1 + k # w, b, slacks
# Objective: minimize sum of slacks
c = np.zeros(n_vars)
c[d+1:] = 1 # minimize slacks
# Constraints: y_i * (w^T x_i + b) + s_i >= 1
A = np.zeros((k, n_vars))
for i in range(k):
A[i, :d] = -y[i] * X[i]
A[i, d] = -y[i]
A[i, d+1+i] = -1
b_vec = -np.ones(k)
bounds = [(None, None)] * (d + 1) + [(0, None)] * k
result = linprog(c, A_ub=A, b_ub=b_vec, bounds=bounds)
if result.success:
continue # This labeling is achievable
else:
all_shattered = False
break
except ImportError:
# Fallback: check linear separability geometrically
from numpy.linalg import lstsq
# Augment X with bias column
X_aug = np.column_stack([X[:k], np.ones(k)])
# Solve least squares
w, residuals, rank, sv = lstsq(X_aug, y, rcond=None)
# Check if all margins are positive
margins = y * (X_aug @ w)
if np.all(margins > 1e-10):
continue
else:
all_shattered = False
break
if all_shattered:
continue # Can shatter k points, try k+1
else:
return k - 1 # Cannot shatter k points
return min(m, max_d)
def rademacher_complexity_linear(X, Lambda=1.0, n_samples=1000):
"""
Estimate Rademacher complexity for linear class with ||w|| <= Lambda.
Args:
X: Input matrix of shape (n, d)
Lambda: Radius of weight ball
n_samples: Number of Rademacher samples
Returns:
Estimated Rademacher complexity
"""
n, d = X.shape
complexities = []
for _ in range(n_samples):
# Sample Rademacher variables
sigma = np.random.choice([-1, 1], size=n)
# Compute sup over w with ||w|| <= Lambda of (1/n) sum sigma_i w^T x_i
# = (Lambda/n) ||sum sigma_i x_i||
sup_val = (Lambda / n) * np.linalg.norm(sigma @ X)
complexities.append(sup_val)
return np.mean(complexities)
def pac_bayes_bound(S, prior_mean=0, prior_var=1, delta=0.05):
"""
Compute PAC-Bayes bound for Gaussian posterior over linear classifiers.
Args:
S: Dataset of shape (n, d+1) with last column being labels
prior_mean: Mean of prior Gaussian
prior_var: Variance of prior
delta: Confidence parameter
Returns:
Tuple of (bound, empirical_risk, kl_divergence)
"""
n, d_plus_1 = S.shape
X = S[:, :-1]
y = S[:, -1]
# Compute posterior (MAP estimate for linear model)
# For simplicity, assume identity prior covariance
lam = 1.0 / prior_var
# Posterior mean and covariance
H = X.T @ X + lam * np.eye(d_plus_1)
H_inv = np.linalg.inv(H)
posterior_mean = H_inv @ (X.T @ y)
posterior_cov = H_inv
# Compute empirical risk under posterior
margins = y * (X @ posterior_mean)
emp_risk = np.mean(np.maximum(0, 1 - margins))
# KL divergence between Gaussian posterior and prior
# KL(q || p) for Gaussians
trace_term = np.trace(posterior_cov) / prior_var
mean_term = np.linalg.norm(posterior_mean - prior_mean)**2 / prior_var
kl = 0.5 * (trace_term + mean_term - d_plus_1 +
np.log(np.linalg.det(prior_var * np.eye(d_plus_1)) /
np.linalg.det(posterior_cov)))
# PAC-Bayes bound
bound = emp_risk + np.sqrt((kl + np.log(n / delta)) / (2 * (n - 1)))
return bound, emp_risk, kl
11. Minimax Theory
11.1 Minimax Risk
The minimax risk is the best achievable worst-case error:
where the infimum is over all estimators and the supremum is over all distributions .
11.2 Lower Bounds
Theorem (Fano's Inequality): For any class with and metric :
where is uniformly distributed over and is the dataset.
11.3 Minimax Optimality
An estimator is minimax optimal if:
for some constant .
Example: For Gaussian location model with :
where denotes minimum.
12. Leave-One-Out Analysis
12.1 Definition
The leave-one-out (LOO) error removes each training point in turn:
where .
12.2 Stability Connection
Theorem: If algorithm has uniform stability , then:
This provides an alternative way to estimate generalization error.
12.3 Advantages
- No need for held-out data
- Unbiased estimate of true error (for 0-1 loss)
- Detects overfitting directly
Disadvantage: Requires retrainings, computationally expensive.
13. Code: Extended Analysis
def leave_one_out_error(X, y, classifier='linear'):
"""
Compute leave-one-out error.
Args:
X: Feature matrix of shape (n, d)
y: Labels of shape (n,)
classifier: Type of classifier
Returns:
LOO error
"""
n = len(y)
errors = []
for i in range(n):
# Remove point i
X_train = np.delete(X, i, axis=0)
y_train = np.delete(y, i)
x_test = X[i]
y_test = y[i]
# Train on remaining data
if classifier == 'linear':
from sklearn.linear_model import LogisticRegression
model = LogisticRegression(max_iter=1000)
model.fit(X_train, y_train)
pred = model.predict(x_test.reshape(1, -1))[0]
elif classifier == 'knn':
from sklearn.neighbors import KNeighborsClassifier
model = KNeighborsClassifier(n_neighbors=5)
model.fit(X_train, y_train)
pred = model.predict(x_test.reshape(1, -1))[0]
errors.append(pred != y_test)
return np.mean(errors)
def compute_generalization_gap(true_risk, empirical_risk):
"""Compute generalization gap."""
return true_risk - empirical_risk
def bound_comparison(n, d, delta=0.05):
"""
Compare different generalization bounds.
Args:
n: Sample size
d: VC dimension
delta: Confidence parameter
Returns:
Dict of bound values
"""
vc_bound = np.sqrt((2 * d * np.log(2 * n / d) + 2 * np.log(2 / delta)) / n)
rademacher_bound = np.sqrt(2 * d * np.log(2 * n / d) / n) + 3 * np.sqrt(np.log(2 / delta) / (2 * n))
simpler_vc = np.sqrt(d * (np.log(2 * n / d) + 1) / n)
return {
'vc_bound': vc_bound,
'rademacher_bound': rademacher_bound,
'simpler_vc': simpler_vc,
'sample_complexity': 8 * d * np.log(2 / delta) / (vc_bound ** 2)
}
def stability_bound(n, beta, M, delta=0.05):
"""Compute stability-based generalization bound."""
return beta + (2 * n * beta + M) * np.sqrt(np.log(1 / delta) / (2 * n))
def minimax_lower_bound(d, n):
"""Compute minimax lower bound for linear classification."""
return d / n
# Demonstration
if __name__ == "__main__":
# Generate synthetic data
np.random.seed(42)
n, d = 100, 10
X = np.random.randn(n, d)
y = np.sign(X @ np.random.randn(d) + 0.5 * np.random.randn(n))
# Compare bounds
bounds = bound_comparison(n, d)
print("Generalization Bounds (n={}, d={}):".format(n, d))
for name, value in bounds.items():
print(f" {name}: {value:.4f}")
# Stability bound
beta = 0.01
M = 1.0
sb = stability_bound(n, beta, M)
print(f"\nStability Bound (beta={beta}): {sb:.4f}")
# Minimax bound
mm = minimax_lower_bound(d, n)
print(f"Minimax Lower Bound: {mm:.4f}")
# LOO error (small subset for speed)
X_small = X[:20]
y_small = y[:20]
loo = leave_one_out_error(X_small, y_small)
print(f"\nLOO Error (n=20): {loo:.4f}")
14. Summary
Statistical learning theory provides the mathematical backbone for understanding generalization. The key insights are:
- VC dimension characterizes the capacity of hypothesis classes for binary classification
- Rademacher complexity provides tighter, data-dependent bounds
- PAC-Bayes bounds are algorithm-specific and can be surprisingly tight
- Stability provides an alternative to uniform convergence for analyzing generalization
- Margin bounds explain why large-margin classifiers generalize well even in high dimensions
- Minimax theory establishes fundamental limits on what any algorithm can achieve
- Leave-one-out analysis provides practical error estimation without held-out data
These tools are not merely theoretical — they directly inform algorithm design (regularization, early stopping) and help practitioners understand when and why their models will work.
The interplay between these frameworks reveals a rich mathematical landscape:
- VC theory provides worst-case guarantees
- Rademacher complexity captures average-case behavior
- PAC-Bayes bounds bridge Bayesian and frequentist perspectives
- Stability connects to algorithmic robustness
- Minimax theory sets fundamental limits
Understanding these connections is essential for developing principled machine learning algorithms with provable guarantees.