A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Probably Approximately Correct (PAC) learning, introduced by Leslie Valiant in 1984, formalizes what it means for a learning algorithm to succeed. A concept class is PAC-learnable if there exists an algorithm that, for any target concept in the class and any distribution over inputs, produces a hypothesis with error at most epsilon with probability at least 1 - delta, using a number of samples polynomial in 1/epsilon, 1/delta, and the representation size. This framework transforms the informal question "can we learn this?" into a precise mathematical statement about sample efficiency and computational feasibility.
Before the PAC framework, machine learning lacked a rigorous answer to a basic question: when can we say an algorithm has "learned" a concept? Empirical success on a test set is encouraging but proves nothing about future performance or worst-case behavior. Leslie Valiant's 1984 framework answered this by defining learning in terms of two tolerances — an accuracy parameter epsilon and a confidence parameter delta — and requiring that the algorithm's resource usage (both samples and computation) scale polynomially with the difficulty of the guarantee.
The formal setup works as follows. There is an unknown target concept c (a function mapping inputs to {0, 1}) drawn from a known concept class C, and an unknown distribution D over the input space. The learner receives m training examples drawn i.i.d. from D, each labeled by c. The learner must output a hypothesis h such that the probability of h disagreeing with c on a fresh random example from D is at most epsilon, and this guarantee must hold with probability at least 1 - delta over the random draw of the training set. A concept class C is PAC-learnable if there exists an algorithm and a function m(epsilon, delta) polynomial in 1/epsilon and 1/delta such that for every c in C and every D, drawing m(epsilon, delta) examples suffices.
The distribution-free requirement is crucial and often misunderstood. The same algorithm must work regardless of how inputs are distributed — it cannot assume data is Gaussian, uniform, or structured in any particular way. This makes PAC guarantees robust but conservative: real data often has exploitable structure, so PAC bounds can be pessimistic for benign distributions. The computational requirement is equally important: the algorithm must run in polynomial time, connecting learning theory directly to complexity theory. Some concept classes are "information-theoretically" learnable (enough samples exist) but not "computationally" learnable (no known polynomial-time algorithm can find the right hypothesis).
The PAC framework serves as the foundation for most of learning theory. The sample complexity bounds it produces — typically involving the VC dimension or other complexity measures of the hypothesis class — tell you how many examples are necessary and sufficient for learning. It also provides a clean separation between learnable and unlearnable concept classes: some classes (conjunctions, decision lists) are efficiently PAC-learnable, while others (general Boolean functions, certain cryptographic concepts) are provably not under standard complexity assumptions. This framework gives you the language and tools to ask precise questions about learnability, and every subsequent topic in this course builds on or extends the PAC model.