Introduction

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.

Learn From Samples

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">The dashed box is the hidden <b>true concept</b>. The learner sees only the
sampled points (<span class="g">inside</span> = yes, <span class="x">outside</span> = no) and
guesses the tightest box — the <span class="b">learned</span> rectangle.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// PAC learning of an axis-aligned rectangle. The true concept is a hidden
// rectangle; the learner outputs the tightest box around the positive samples.
// Generalization error = area(true) - area(learned)
const PAD = 14, W = 272;
const TRUE = { x0: 0.22, y0: 0.28, x1: 0.74, y1: 0.78 }; // normalized
const sx = u => PAD + u * W, sy = v => PAD + (1 - v) * W;
function inTrue(p) { return p.x >= TRUE.x0 && p.x <= TRUE.x1 && p.y >= TRUE.y0 && p.y <= TRUE.y1; }
let pts = [];

function sample(n) {
  pts = [];
  for (let i = 0; i < n; i++) { const p = { x: Math.random(), y: Math.random() }; p.pos = inTrue(p); pts.push(p); }
}

function learned() {
  const P = pts.filter(p => p.pos);
  if (!P.length) return null;
  return { x0: Math.min(...P.map(p => p.x)), y0: Math.min(...P.map(p => p.y)), x1: Math.max(...P.map(p => p.x)), y1: Math.max(...P.map(p => p.y)) };
}
function area(r) { return r ? (r.x1 - r.x0) * (r.y1 - r.y0) : 0; }

function render() {
  const L = learned();
  let s = '';
  s += rect('true', TRUE);
  if (L) s += rect('learned', L);
  pts.forEach(p => { s += '<circle class="' + (p.pos ? 'pos' : 'neg') + '" cx="' + sx(p.x).toFixed(1) + '" cy="' + sy(p.y).toFixed(1) + '" r="3.5"/>'; });
  document.getElementById('plot').innerHTML = s;
  // generalization error = P(misclassified) = area(true) - area(learned)
  const err = Math.max(0, area(TRUE) - area(L));
  const e = document.getElementById('err');
  e.innerHTML = fmt('Generalization error: <span style="color:%v%">%v2%%</span> of new points misclassified.', { v: err < 0.03 ? '#0a7d33' : err < 0.1 ? '#b9770e' : '#c0392b', v2: (err * 100).toFixed(1) });
}
function rect(cls, r) { return '<rect class="' + cls + '" x="' + sx(r.x0).toFixed(1) + '" y="' + sy(r.y1).toFixed(1) + '" width="' + ((r.x1 - r.x0) * W).toFixed(1) + '" height="' + ((r.y1 - r.y0) * W).toFixed(1) + '"/>'; }

function update() { const n = +document.getElementById('n').value; document.getElementById('nval').textContent = n; sample(n); render(); }
document.getElementById('n').addEventListener('input', update);
document.getElementById('resample').addEventListener('click', update);
update();
Result
Console

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.

The Hard Part

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pac-learning/Content licensed under CC BY-NC 4.0.