How Much Data to Learn?

A child sees a few dogs and soon recognizes dogs she's never met. A spam filter sees some labeled emails and starts catching new spam. In both cases, a rule is being learned from examples — and then applied to unseen cases. The deep question is: how many examples does that take, and when is it even possible?

Memorizing the examples is no answer: it nails the training cases and fails on everything new — the classic trap of overfitting. Real learning means generalizing: capturing the underlying rule, not the specific samples.

PAC learning — Probably Approximately Correct, introduced by Leslie Valiant in 1984 — is the theory that makes this precise. It asks for a hypothesis that is, with high probability, approximately correct on future data, and studies how many samples and how much computation that requires. It's the mathematical backbone of machine learning — and it draws a sharp line between what can be learned efficiently and what can't.

Try it. There's a hidden true concept — a rectangle: points inside it are "yes," outside are "no." The learner only sees a handful of labeled samples and guesses the tightest rectangle consistent with them. Slide the number of samples up and down.

<p class="hint">{{hint}}</p>
<svg id="plot" viewBox="0 0 300 240" class="plot"></svg>
<label class="slab">{{training_samples}} <b id="nval">12</b>
  <input id="n" type="range" min="2" max="300" value="12" />
</label>
<div id="err" class="err"></div>
<button id="resample" type="button" class="ghost">{{resample}}</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint .g { color: #0a7d33; font-weight: 700; } .hint .x { color: #888; font-weight: 700; } .hint .b { color: #457b9d; font-weight: 700; }
.plot { width: 100%; max-width: 360px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.true { fill: rgba(42,157,143,.07); stroke: #2a9d8f; stroke-width: 2; stroke-dasharray: 5 4; }
.learned { fill: rgba(69,123,157,.12); stroke: #457b9d; stroke-width: 2; }
.pos { fill: #0a7d33; } .neg { fill: #b9bfc6; }
.slab { display: block; font: 600 14px system-ui; color: #1d3557; margin: .8rem 0 .4rem; }
.slab input { width: 100%; margin-top: .3rem; accent-color: #457b9d; }
.err { font-weight: 800; font-size: 1.05rem; margin: .3rem 0 .7rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

With few samples the learned rectangle is too small — lots of future points get misclassified (high generalization error). Add more, and it hugs the true concept, error shrinking toward zero. That curve — error falling as samples grow — is PAC learning, made visible.

PAC learning turns "can we learn this?" into precise mathematics:

• Sample complexity. How many examples you need scales with the VC dimension — a measure of how flexible the hypothesis class is. More flexibility means more samples to pin down the right rule and avoid overfitting.
• The generalization guarantee. With enough samples, any consistent hypothesis is, with high probability, approximately correct on future data. That's a real theorem, not a hope.
• Some classes are easy. Rectangles, intervals, linear separators and many natural concepts are efficiently PAC-learnable — polynomial samples and time.
• Some are provably hard. Certain concept classes (e.g. small circuits, some Boolean formulas) cannot be learned efficiently unless cryptography breaks — learning them would let you break codes believed secure. Learnability and hardness are deeply linked.
• The deep-learning puzzle. Modern networks have astronomical VC dimension, so classic theory predicts they should overfit — yet they generalize. Reconciling PAC theory with deep learning's success is a major open research front.

So PAC learning is where complexity theory meets statistics: it tells you not just whether a problem is computable, but whether it's learnable — and at what cost in data.

PAC theory is the quiet foundation under applied machine learning:

• Generalization guarantees: bounds on how well a model trained on n examples will do on new data.
• How much data to collect: sample-complexity results guide dataset sizing.
• Model selection and regularization: VC dimension explains why simpler models often generalize better.
• Trustworthy AI: provable guarantees matter in medicine, finance and safety-critical systems.
• Boosting and ensemble methods: born directly from PAC-learning theory (weak vs strong learnability).

Even when practitioners don't cite it, PAC learning is the reason "train on data, hope it generalizes" rests on solid ground rather than wishful thinking.

PAC learning answers a question that sounds philosophical and turns out to be mathematical: when can experience be turned into reliable knowledge? Memorizing isn't learning; generalizing is — and PAC theory pins down exactly how many examples that demands, and proves that with enough of them, success isn't luck but a guarantee.

It also draws a humbling boundary: some concepts are no more learnable than secret codes are breakable. Learnability has its own landscape of easy and hard, mirroring the rest of this site. And its biggest open question is wonderfully current — why does deep learning generalize when the theory says it shouldn't? The answer is still being written, in the gap between what we can prove and what we can build.