Probably Approximately Correct (PAC) learning: with probability ≥ 1−δ, find a hypothesis with error ≤ ε, using polynomially many examples and computation.
100
0.10
0.90
50
PAC Bound: m ≥ (1/ε)(ln(|H|/δ)) for finite H, or m ≥ (1/ε)(d·ln(1/ε) + ln(1/δ)) for VC dimension d. Concept class: Circles centered at origin (1D parameter: radius). The algorithm sees labeled points (+inside, −outside) and must find a circle with small error. Consistent learner: The smallest consistent circle is optimal for this class — it minimizes false positives while never making false negatives.