PAC Learning

Before PAC learning, "can an algorithm learn this concept" had no precise meaning — you could always get lucky or unlucky with the training sample you happened to draw. Leslie Valiant's Probably Approximately Correct (PAC) framework fixed that by asking a more honest question: how much data does it take for a learner's error to be small (approximately correct) with high confidence (probably), rather than guaranteed in every possible case?

Formally, a concept class is PAC-learnable if, for any error tolerance $\epsilon$ and failure probability $\delta$, there's a sample size $m$ — growing only polynomially as $\epsilon$ and $\delta$ shrink — after which the learner's true error is below $\epsilon$ with probability at least $1-\delta$. In words: name how wrong you're willing to be and how often you're willing to accept getting unlucky, and the theory tells you how much data buys you that guarantee.

Worked example. For a finite hypothesis class of size $H$, a standard PAC bound gives sample complexity $m \geq \frac{1}{\epsilon}\left(\ln|H| + \ln\frac{1}{\delta}\right)$. With 1,000 candidate hypotheses ($\ln 1000 \approx 6.9$), wanting 95% confidence ($\delta = 0.05$, $\ln 20 \approx 3.0$) of error below 10% ($\epsilon = 0.1$): $m \geq 10 \times (6.9 + 3.0) = 99$ examples. Tightening to 1% error instead multiplies the required sample roughly tenfold — a concrete illustration of why demanding much higher accuracy costs far more data, not just proportionally more.