Machine-Learning Theory

Before 1984, machine learning had accumulated many algorithms that seemed to work well empirically but almost no formal account of what "learning" even guaranteed, or how much data a given problem actually required. Leslie Valiant's paper "A Theory of the Learnable" addressed this gap by proposing a precise computational framework: a learner has access to an EXAMPLES source that draws instances at random from some unknown probability distribution and labels them according to an unknown target concept, and the learner's job is to output, in polynomial time, a hypothesis that is correct on almost all future examples from that same distribution, with high probability over the randomness of the training sample. Valiant called a hypothesis "probably" correct because the learner only needs to succeed with probability at least a chosen confidence level, not with certainty, and "approximately" correct because the hypothesis only needs to be right on all but a small chosen fraction of future examples, not perfectly — together giving the framework its name, probably approximately correct, or PAC, learning.

A concept class is PAC-learnable if there is an algorithm that, for any target concept in the class, any data distribution, and any chosen error tolerance and confidence level, can produce a suitable hypothesis using a number of training examples and amount of computation that grows only polynomially as the tolerance and confidence demands tighten. Valiant demonstrated that several nontrivial concept classes, including k-CNF formulas and monotone DNF formulas, are learnable in this strict sense, which mattered because it showed the framework was not vacuous — some genuinely useful classes of concepts admit a mathematically guaranteed learning procedure with a bounded sample requirement, not just an empirically plausible one. These particular classes were chosen because they are expressive enough to represent nontrivial Boolean functions while still admitting an efficient consistent-hypothesis-finding procedure, illustrating that the tension between expressiveness and efficient learnability is a real constraint the framework forces into the open rather than a merely theoretical worry.

The most immediately useful consequence of PAC theory for a practitioner is a sample complexity bound: for a finite hypothesis class of size |H|, if the true target concept is exactly representable in that class (the realizable case), then a learning algorithm that returns any hypothesis perfectly consistent with a training sample of size at least m ≥ (1/ε)(ln|H| + ln(1/δ)) is guaranteed, with probability at least 1 − δ, to have true error at most ε on future data. This single formula converts two abstract tolerances — how wrong you are willing to risk being, and how often you are willing to risk being that wrong — into a concrete number of labeled examples, and it reveals that sample requirements grow only logarithmically in the size of the hypothesis class, which is why enormous hypothesis classes can still be learnable from surprisingly modest data, provided that class remains finite in the strict sense the bound requires.

The sample complexity bound for finite hypothesis classes is elegant but useless for the hypothesis classes most machine learning actually uses, such as linear classifiers or neural networks, whose parameters are real-valued and whose class is therefore infinite — |H| is simply not a finite number to plug into a formula. The tool that resolves this was developed earlier and independently by Vladimir Vapnik and Alexey Chervonenkis, whose 1971 paper established conditions under which the empirical frequency of events observed in a random sample converges uniformly to their true probabilities across an entire class of events at once, rather than for one event at a time. This uniform convergence result is what a learning algorithm actually needs: not just that error on the training sample is a good estimate of error on the true distribution for one fixed hypothesis, but that this holds simultaneously for every hypothesis the algorithm might select, since the algorithm chooses its hypothesis after seeing the data.

The relevant measure of an infinite hypothesis class's effective size is now called its VC dimension: the largest number of points that some configuration of the class can shatter, meaning the class contains a hypothesis realizing every possible way of labeling those points as positive or negative. For linear classifiers in the plane, three points in general position can be shattered — every one of the eight possible ways to label three non-collinear points as positive or negative can be achieved by some line — but four points cannot be shattered by any line, because a configuration such as four points labeled alternately in an X-shaped, or XOR-like, pattern cannot be separated by a single straight line no matter how the line is drawn. The VC dimension of linear classifiers in the plane is therefore exactly three, a finite number despite the hypothesis class itself containing infinitely many distinct lines.

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth showed how to plug VC dimension into a sample complexity bound in place of ln|H|, giving results of the same qualitative shape but applicable to infinite classes: roughly, a sample of size on the order of (d/ε) log(1/ε) plus (1/ε) log(1/δ), where d is the VC dimension, suffices for PAC learnability in the realizable case. The deep result underlying both bounds — for finite classes and for classes measured by VC dimension — is the same: finite capacity of a hypothesis class, however that capacity is measured, is what makes generalization from a finite sample to the entire distribution mathematically possible at all. Without some such bound on capacity, a hypothesis class could always contain a member that fits any given training sample perfectly by memorization alone, regardless of how much data was collected, which is precisely the scenario PAC theory and VC dimension are constructed to rule out.

PAC theory and VC dimension explain how much data is needed for a fixed hypothesis class to generalize, but they say nothing about how to choose the class in the first place — too restrictive a class and no hypothesis in it fits the true relationship well no matter how much data arrives; too flexible a class and the model fits noise in the particular training sample rather than the underlying pattern. Stuart Geman, Elie Bienenstock, and René Doursat gave this trade-off its now-standard decomposition for squared-error prediction: the expected squared error of a learned predictor on a new point can be decomposed into three non-negative terms — the irreducible noise inherent in the problem, a bias term measuring how far the average prediction across many hypothetical training sets diverges from the true value, and a variance term measuring how much the prediction itself fluctuates across those different training sets.

Bias and variance move in opposite directions as model flexibility changes, which is why the trade-off is often visualized as a U-shaped curve for total expected error against model complexity. An overly simple model — one that cannot represent the true relationship even with unlimited data — has high bias because it is systematically wrong in a consistent direction, but low variance because that consistent wrongness does not depend much on which particular training sample was drawn. An overly flexible model has the reverse problem: it can, in principle, represent the true relationship, giving it low bias, but because it has enough capacity to fit incidental noise in any given training sample, its predictions swing substantially from one training set to another, giving it high variance. Geman, Bienenstock, and Doursat framed this specifically as a dilemma rather than a solvable equation because, for a fixed amount of training data, reducing one term generally increases the other, and the practitioner's real task is to find the complexity level that minimizes their sum, not to eliminate either one.

This framing connects directly back to sample complexity: the finite-VC-dimension bounds show that adding more training data narrows the gap between training error and true error for a fixed hypothesis class, which is exactly the mechanism that lets a practitioner tolerate a higher-variance, higher-capacity model class as data grows, since more data can substitute for lower flexibility in controlling variance. Understanding the bias–variance decomposition is therefore not a separate topic from PAC learning and VC dimension but the practical, quantitative face of the same underlying question — how a finite sample constrains what any learning algorithm can honestly claim to have learned about a distribution it has only partially observed. Neither theory tells a practitioner the single correct model complexity for a specific dataset in advance; both instead explain why searching for that complexity empirically, through techniques like cross-validation, is a mathematically well-motivated exercise rather than a purely trial-and-error one.