VC Dimension, Rademacher complexity, generalization error bounds, and PAC learning.
For a small example, one learner chooses a threshold; another memorizes every label. Both can fit a tiny sample, but the larger class needs more evidence to justify its flexibility.
Validation error stops improving while training error falls. Vary dataset size and capacity, identify variance, and choose whether more data or stronger regularization is plausible.
Initializing Interactive Playground...
Predict how one control changes the Statistical Learning Theory result.
The starter deliberately follows a tempting but flawed assumption: Quoting a bound without its assumptions
Check: Your saved hypothesis predicts a direction, the experiment tests it, and the result changes or supports your explanation.
Explanations after each answer · 80% to pass · Statistical Learning Theory
Chapter 1 of 5 · Core
A learning algorithm sees a finite sample but is judged on new examples. Let S contain N independent examples from one fixed distribution D, and let the loss lie in [0,1]. Population risk R(h) is expected loss under D; empirical risk is the average loss on S. This distinction matters because selecting a model using its training error makes that error an optimistic estimate.
In realizable binary classification, assume some hypothesis in H labels the population without error. PAC learning asks for an algorithm that, with probability at least 1 − δ over the training sample, returns a hypothesis with population error at most ε. The guarantee must hold for every allowed distribution and target. Sample complexity specifies how many examples suffice. Computational efficiency is an additional requirement; a statistical guarantee alone does not supply an efficient algorithm.
In the agnostic case, perfect prediction need not exist. The target becomes risk at most ε above the infimum risk within H. Neither definition is simply a bound on the difference between training and population error: that difference is a generalization gap, which can help prove a learning guarantee.
For a fixed hypothesis and bounded independent losses, Hoeffding's inequality bounds the probability of an absolute gap larger than a by 2 exp(−2Na²). Taking a union bound over a finite, pre-specified H gives a simultaneous statement for every hypothesis, including one selected using S. Solving 2|H| exp(−2Na²) ≤ δ yields N ≥ log(2|H|/δ)/(2a²).
If an empirical risk minimizer has empirical risk no larger than any comparator, apply the gap bound twice: once to the selected hypothesis, once to the best comparator. Its excess population risk is then at most 2a. Set a = ε/2 to obtain an agnostic excess-risk guarantee. Do not relabel the gap tolerance a as excess error ε without this factor.
For a consistent learner in the realizable finite-class case, a different argument is sharper. A hypothesis with error greater than ε survives N independent examples with probability at most (1−ε)^N ≤ exp(−Nε). A union bound gives N ≥ log(|H|/δ)/ε. This is a sufficient bound under those assumptions, not the minimum dataset size for every real task.
For |H| = 100, δ = 0.05, and a gap tolerance of 0.1, the two-sided Hoeffding bound needs 415 samples after rounding upward. To guarantee agnostic excess error 0.1 by this argument, use gap tolerance 0.05 and obtain 1,659. For realizable consistent classification with error tolerance 0.1, the other bound gives 77. Different answers reflect different assumptions and guarantees, not contradictory arithmetic.
The i.i.d. assumption fails when duplicates cross the split, patients occur in both sets, or future information leaks backward. A larger row count does not repair those failures. Define the deployment unit and split by that unit before invoking a statistical bound.
Key equations
import math
def gap_bound_size(hypotheses, gap, delta):
if hypotheses < 1 or not 0 < gap < 1 or not 0 < delta < 1:
raise ValueError("Invalid class size, gap, or failure probability")
return math.ceil(math.log(2 * hypotheses / delta) / (2 * gap**2))
assert gap_bound_size(100, 0.1, 0.05) == 415
assert gap_bound_size(100, 0.05, 0.05) == 1659
print("Gap 0.1:", gap_bound_size(100, 0.1, 0.05))
print("Agnostic excess risk 0.1:", gap_bound_size(100, 0.05, 0.05))
print("Realizable consistent error 0.1:", math.ceil(math.log(100 / 0.05) / 0.1))The Bias-Variance Tradeoff
StatQuest
Relate model flexibility to underfitting, overfitting, and generalization on unseen data.
Primary sources and free technical reading for Statistical Learning Theory.