Back to Curriculum
Intermediate•Machine Learning
Statistical Learning Theory
VC Dimension, Rademacher complexity, generalization error bounds, and PAC learning.
Interactive Playground
Initializing Interactive Playground...
Research-Level Deep Dive & Equations
Statistical Learning Theory formalizes when and why machine learning algorithms generalize from finite training samples to unseen population distributions . Introduced by Leslie Valiant (1984), the **PAC Learning** framework defines the sample complexity of learning a hypothesis class .
•Formal PAC Learning Definition: A hypothesis class is PAC learnable if there exists an algorithm and a polynomial function such that for any target concept , any distribution , and any , given i.i.d. samples , the algorithm outputs satisfying:
where is the approximation error parameter and is the confidence failure probability.
•Expected True Risk vs Empirical Risk:
•Finite Hypothesis Class Bound: For a finite hypothesis space , applying Hoeffding's Inequality and a union bound yields the sample complexity bound:
Key Equations
PyTorch PAC Sample Complexity & Hoeffding Bound Estimatorpython
import math
import torch
def compute_pac_sample_complexity(h_size: int, epsilon: float = 0.05, delta: float = 0.01) -> int:
"""Computes minimum samples required for PAC learning finite hypothesis space H."""
n_required = (1.0 / (2 * epsilon**2)) * (math.log(h_size) + math.log(1.0 / delta))
return math.ceil(n_required)
# Example: Binary decision trees with 2^20 possible hypotheses
h_trees = 2**20
samples = compute_pac_sample_complexity(h_trees, epsilon=0.05, delta=0.01)
print(f"Required training samples for PAC guarantee: {samples:,}")Test Your Knowledge
Check whether you have mastered this concept with a quick quiz.
Was this lesson helpful?
Your feedback helps us continuously improve the curriculum and interactive visualizations.