PAC learning framework (probably approximately correct)

PAC formalizes the modest, honest goal of machine learning: you will not learn the truth exactly, and you cannot guarantee success every single time, but you can promise to be approximately correct with probability close to one — given enough data. The word approximately is captured by an error tolerance epsilon; probably by a confidence one minus delta. A class is PAC-learnable if some algorithm meets any target accuracy and confidence using a number of samples that grows only polynomially in one over epsilon and one over delta.

Fix an unknown distribution over inputs and an unknown target concept in a class. The learner sees m independent labeled examples and outputs a hypothesis. The class is PAC-learnable if there is an algorithm such that, for every distribution and target, with probability at least one minus delta the true error of the output is at most epsilon, whenever m exceeds a sample-complexity bound polynomial in the accuracy, the confidence, and the class's complexity. In the realizable setting the target lies in the class; the agnostic extension drops that and asks the output merely to compete with the best member.

PAC is the foundation that turned learning into a theory with provable guarantees rather than heuristics. Its central result ties learnability to VC dimension: a binary class is PAC-learnable if and only if its VC dimension is finite, and the sample complexity scales linearly with it. Computational PAC additionally demands that the algorithm run in polynomial time, which can render some statistically learnable classes computationally intractable.