PAC Learning

A computer program is shown a thousand photos, each labeled with whether a cat is in it or not. Afterwards, it should decide for itself on new, never-before-seen photos. The crucial question is: how many examples are needed before you can trust the result? PAC learning is a theory that gives a precise mathematical answer to exactly that. The abbreviation stands for “probably approximately correct.” Both qualifications are deliberate: the program is allowed to make occasional mistakes, and in rare unlucky cases, the entire result may even turn out poor.

Why two pinches of uncertainty are allowed

A perfect guarantee would be nice, but it’s impossible. The examples are chosen at random. With very small probability, you might end up with a thousand photos in which, by pure chance, every cat happens to be sitting on a red sofa. Then the program learns the wrong rule, without anyone having made a mistake. No method can do anything about such bad luck.

That’s why PAC learning works with two dials. One describes how many errors the finished program is allowed to make in operation, say at most five percent. The other describes how often the learning process is allowed to go completely wrong, say in one out of a hundred runs. Both values can be chosen freely and made arbitrarily small. The price for this is more training examples.

The practical value lies in inverting this calculation. Instead of guessing how much data to collect, a number can be computed. That was new in the 1980s. Computer scientist Leslie Valiant received the 2010 Turing Award, computer science’s most important prize, for this idea.

The math behind the number of examples

Before learning begins, you fix which kinds of rules are even under consideration. This set is called the hypothesis space. For a simple model, that might be all straight dividing lines between two clusters of points. For a large neural network, the space is astronomically larger. The learning procedure searches within it for the rule that best fits the examples seen.

The decisive quantity is how flexible this space is. Experts measure this with the VC dimension, named after the mathematicians Vapnik and Chervonenkis. It roughly indicates how many points the model could still cleanly separate under any arbitrary split. The higher this value, the more examples are needed. The theory provides a formula for this: the number of examples grows roughly proportional to the VC dimension and inversely proportional to the allowed error rate.

Behind this lies an intuitive tension. A very rigid model needs few examples but cannot represent many relationships at all. A very flexible model can represent almost anything, but tends to simply memorize the training data. This memorization is called overfitting. PAC learning was the first to make the relationship between flexibility and data requirements measurable.

What remains of this in today’s models

The formulas can hardly be applied directly to large language models. The computed example counts turn out absurdly high there, far higher than what actually suffices in practice. A common misconception is therefore that PAC learning has been disproven. What’s true is: the theory provides a guarantee for the worst possible case, and real data is almost never that malicious.

Nevertheless, this way of thinking still shapes the field today. The principle of never evaluating models on the same data they were trained on originates from this corner. Statements like “more training data helps, but with diminishing returns” are also an everyday rendering of the PAC formulas.

You’ll mainly encounter the term in machine learning lectures and research papers. It rarely appears in product announcements. But anyone reading reports about data volumes, generalization, or overfitting is indirectly reading about PAC learning as well.