Risk and PAC Learning

A learner minimises empirical risk (average loss on training data) as a proxy for expected risk (average loss on all possible data). The gap between them is generalisation error. PAC learning formalises when this gap is small with high probability.

The idea

Expected risk R(h) = E[L(h(x), y)] measures how well hypothesis h performs on the data distribution. We cannot compute it directly, so we minimise empirical risk R̂(h) = (1/n) Σ L(h(xᵢ), yᵢ) on the sample. The difference R(h) - R̂(h) has two parts: estimation error (finite sample) and approximation error (hypothesis class).

PAC (Probably Approximately Correct) says a learner succeeds if, with probability ≥ 1 - δ, it finds a hypothesis with R(h) ≤ ε. Bounds depend on the hypothesis class complexity (VC dimension) and sample size n. More complex classes need more data to generalise.

The maths

Try it

ε (error margin): 0.100

δ (failure probability): 0.050

|H| (hypothesis class size): 100

Sample size needed

415

m ≥ ln(2|H|/δ) / (2ε²)

m ≥ ln(4000.0) / 0.0200

Need 415 samples to ensure error ≤ 0.100 with 5.0% failure probability.

Interactive demonstration of learning theory concepts

Where I used it

Easy to get wrong

Sources

COMP90051 Statistical Machine Learning (2023). PAC bounds and VC dimension.