Learning Theory1984foundational11 min read

A Theory of the Learnable

نظرية ما يمكن تعلُّمه

Valiant, L. G. — Communications of the ACM

The problem

By 1984, there was a rich theory of what computers can compute — computability and complexity theory — but no corresponding theory of what computers can learn. existed as a collection of heuristics and ad-hoc algorithms, but there was no rigorous framework to say which learning problems are tractable, how many examples are enough, or what guarantees a learning can provide. Without such a theory, there was no way to distinguish genuinely learnable concepts from ones that would require impossibly many examples or impossibly long computation.

The contribution

The PAC (Probably Approximately Correct) learning model: a mathematical framework that defines what it means for a computer to learn. A learning algorithm receives random examples labeled by an unknown target concept, and must output a that, with probability at least 1−δ, has error at most ε. Valiant proved that k-CNF formulas and certain classes are PAC-learnable in polynomial time, and established bounds that depend on the accuracy ε, the confidence δ, and the size of the . This created the first rigorous bridge between computational complexity and machine learning.

The impact

created an entirely new field: computational learning theory. It gave machine learning the same rigorous foundation that Turing and Cook gave to computation and complexity. The framework led directly to theory, boosting, and the theoretical understanding behind SVMs. Every time a modern ML paper proves a sample complexity bound or a guarantee, it is building on the language Valiant introduced.

Imagine you are studying for a driving test and you only have access to a sample of practice questions — not every possible question the exam might ask.

You can't guarantee you'll get a perfect score, but if you study enough practice questions chosen at random, you can be fairly confident that you'll mostly pass.

That's PAC learning in a nutshell: given enough random examples, a learner can probably produce a hypothesis that is approximately correct.

The question: what can a computer learn?

Before Valiant's paper, the question "can a machine learn X?" had no formal answer. There was no agreed-upon definition of what learning even meant in a computational sense.

Think about the parallel in computation theory: before Turing machines, there was no formal way to say "this problem is computable" or "this problem is not." Turing's model gave us that language. Valiant did the same for learning.

His starting point was simple but profound: learning is about generalizing from examples. You see some labeled data points, and you need to find a rule that works well not just on those examples, but on new, unseen data drawn from the same source.

The setup: concepts, examples, and hypotheses

PAC learning has four main ingredients:

Instance space — the set of all possible inputs. In Valiant's original formulation, these are Boolean vectors $x \in \{0, 1\}^n$ . Think of each bit as a : "has fur," "has wings," "can swim."

Concept class — a family $\mathcal{C}$ of Boolean functions, each mapping instances to 1. One particular function $c \in \mathcal{C}$ is the unknown target the learner is trying to discover. For example, $\mathcal{C}$ might be "all conjunctions over $n$ variables."

— a fixed but unknown probability distribution $\mathcal{D}$ over the instance space. Examples are drawn i.i.d. from $\mathcal{D}$ , and the learner's error is also measured under $\mathcal{D}$ . Crucially, the framework is distribution-free: the learner must succeed under any distribution.

Hypothesis — the function $h$ that the learner outputs. The goal is $\Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] \leq \varepsilon$ .

Open in Lab

The four ingredients of PAC learning and how they relate.

The demo wakes as you arrive…

The formal definition

Now that we have the ingredients, here is what PAC learning demands. The learner must succeed no matter which concept from $\mathcal{C}$ is the target, and no matter which distribution generates the examples. It receives labeled examples $(x, c(x))$ and must output a hypothesis $h$ such that:

With probability at least $1 - \delta$ over the random draw of examples, the hypothesis satisfies $\Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] \leq \varepsilon$ .

The learner must do this using a number of examples and computation time that are both polynomial in $1/\varepsilon$ , $1/\delta$ , and the size $n$ of each instance. If such an algorithm exists, we say $\mathcal{C}$ is PAC-learnable.

\Pr_{\text{sample} \sim \mathcal{D}^m}\!\bigl[\, \Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] \leq \varepsilon \,\bigr] \;\geq\; 1 - \delta

The PAC guarantee — Over at least a (1−δ) fraction of random training sets of size m, the learner's hypothesis h has error ≤ ε on new data from the same distribution.

Open in Lab

Drag ε and δ to see how the PAC guarantee changes.

The demo wakes as you arrive…

Sample complexity: how many examples are enough?

The most natural question is: how many examples $m$ does the learner need? Valiant showed that for a finite concept class $\mathcal{C}$ , the answer is:

If you draw at least $m \geq \frac{1}{\varepsilon}\bigl(\ln|\mathcal{C}| + \ln\frac{1}{\delta}\bigr)$ examples, then any hypothesis consistent with all the examples is PAC-correct.

The intuition is a process of elimination. Each random example has a chance of at least $ε$ of ruling out any "bad" hypothesis — one whose error exceeds $ε$ . After $m$ examples, the probability that any specific bad hypothesis survives all of them is at most $(1-ε)^m \leq e^{-εm}$ . By a union bound over all $|\mathcal{C}|$ possible concepts, the probability that any bad hypothesis survives is at most $|\mathcal{C}| \cdot e^{-εm}$ . Setting this ≤ $δ$ and solving for $m$ gives the bound above.

m \;\geq\; \frac{1}{\varepsilon}\!\left(\ln|\mathcal{C}| + \ln\frac{1}{\delta}\right)

Sample complexity for a finite concept class — m examples suffice to PAC-learn — logarithmic in the concept class size, inverse in ε and δ. Larger concept classes need more examples, but only logarithmically more.

Open in Lab

Adjust the concept class size, ε, and δ to see how sample complexity changes.

The demo wakes as you arrive…

The key idea: elimination by random evidence

The deepest insight in Valiant's proof is that random examples are surprisingly powerful. You do not need cleverly chosen examples or adversarial queries. Plain random samples, drawn from whatever distribution nature provides, are enough.

Imagine the concept class as a room full of suspects. Each random example is like a witness who points and says, "that suspect is not the one." Any suspect whose predictions contradict a witness is eliminated. After enough witnesses, only suspects whose behavior closely matches the real culprit remain. The ones still standing may not be identical to the target, but they are approximately correct — they agree on all but an $\varepsilon$ -fraction of the population.

Open in Lab

Watch bad hypotheses get eliminated one by one as random examples arrive.

The demo wakes as you arrive…

What Valiant proved learnable

Valiant did not just define the framework — he used it to prove concrete results. He showed that several natural Boolean function classes are efficiently PAC-learnable:

k-CNF formulas — conjunctive normal form with at most $k$ literals per clause. These are learnable in polynomial time. The algorithm is simple: start with the most general hypothesis and eliminate clauses that contradict positive examples.

k-DNF formulas — disjunctive normal form with at most $k$ literals per term. Also PAC-learnable, though the algorithm works differently.

$\mu$ -expressions — Boolean formulas where each variable appears at most once. These have bounded complexity that makes efficient learning possible.

These results established the first positive examples of efficient learnability, giving the field concrete problems to study and extend.

Open in Lab

Toggle between k-CNF and k-DNF to see how the learning algorithm eliminates inconsistent hypotheses.

The demo wakes as you arrive…

Computational complexity meets learning

One of the most important aspects of PAC learning is its insistence on computational efficiency. It is not enough to show that a concept class can be learned with finitely many examples — the learner must also run in polynomial time.

This creates a fascinating split. Some concept classes are information-theoretically learnable — you can prove a finite sample complexity bound exists — but computationally hard to learn. Learning them would require time that grows exponentially with $n$ .

Valiant himself noted this distinction: a class might be learnable in the statistical sense (finite samples suffice) but intractable in the computational sense (no polynomial-time algorithm exists, assuming standard complexity-theoretic conjectures). This connection between learning and computational complexity became one of the most studied themes in the field.

Distribution-free: the strength of making no assumptions

One of the boldest design choices in PAC learning is the distribution-free requirement. The learner must succeed under any distribution $\mathcal{D}$ . It cannot assume that data is uniformly distributed, or Gaussian, or follows any particular pattern.

This is both a strength and a constraint. It is strong because a PAC-learnable class is truly robust: the guarantee holds regardless of the data source. It is constraining because it makes many problems harder than they would be under specific distributional assumptions.

Think of it as a worst-case guarantee: just as computational complexity asks "does this algorithm work for all inputs?", PAC learning asks "does this learner work for all distributions?"

The bridge to VC dimension

Valiant's sample complexity bound depends on $\ln|\mathcal{C}|$ , the logarithm of the concept class size. This works beautifully for finite classes, but what about infinite concept classes like "all linear classifiers in $\mathbb{R}^n$ "?

The answer came from connecting PAC learning to the Vapnik-Chervonenkis dimension — a measure of the "effective complexity" of a hypothesis class. Blumer, Ehrenfeucht, Haussler, and Warmuth (1989) proved the fundamental theorem: a concept class is PAC-learnable if and only if it has finite VC dimension.

This result unified Valiant's computational framework with statistical learning theory, creating a single characterization of learnability that remains central to the field today.

The idea in code

PAC learning a conjunction — the elimination algorithmpython

Simplified to show the idea — not the real implementation.

import random
import math

def pac_learn_conjunction(n, examples):
    """Learn a conjunction over n Boolean variables from labeled examples.

    Strategy: start with ALL 2n possible literals (x1, ¬x1, x2, ¬x2, ...),
    then eliminate any literal that contradicts a positive example.
    Whatever survives is guaranteed to be a valid (conservative) hypothesis.
    """
    # Start with every possible literal as a candidate
    literals = set(range(2 * n))  # even index = xi, odd = ¬xi

    for x, label in examples:
        if label == 1:  # positive example
            for i in range(n):
                if x[i] == 1:
                    literals.discard(2 * i + 1)  # drop ¬xi
                else:
                    literals.discard(2 * i)      # drop xi

    def hypothesis(x):
        for lit in literals:
            var = lit // 2
            is_negated = lit % 2 == 1
            val = 1 - x[var] if is_negated else x[var]
            if val == 0:
                return 0
        return 1

    return hypothesis

# How many examples do we need?
def sample_bound(n, epsilon, delta):
    concept_class_size = 3**n  # each variable: present, negated, or absent
    return int(math.ceil((1/epsilon) * (math.log(concept_class_size) + math.log(1/delta))))

Why it changed everything

1984
PAC Learning (this paper)
Valiant defines PAC learning in "A Theory of the Learnable," creating computational learning theory.
1989
VC Dimension Characterization
Blumer et al. prove that a class is PAC-learnable if and only if its VC dimension is finite — unifying PAC with statistical learning theory.
1989
Computational Hardness of Learning
Kearns and Valiant show that some concept classes are statistically learnable but computationally intractable under cryptographic assumptions.
1990
Weak Learnability = Strong Learnability
Schapire proves that weak and strong PAC learnability are equivalent, paving the way for boosting algorithms like AdaBoost.
1995
Support Vector Machines
SVMs combine VC theory with kernel methods, bringing PAC-inspired theory to practical large-margin classifiers.
2010
PAC-Bayes & Modern Generalization
PAC-Bayes bounds extend Valiant's framework to Bayesian and deep learning settings, providing tighter generalization guarantees for modern models.

Boosting grew directly from a question PAC learning raised: if you can learn just slightly better than random guessing (a ), can you combine many weak learners into an arbitrarily accurate one? Schapire proved yes, and followed. Every gradient boosting library today traces its lineage to this PAC learning question.

CitationValiant, L. G.. A Theory of the Learnable. Communications of the ACM, 1984.

Terms in this paper

PAC Learningالتعلم الصحيح تقريبياً باحتمال
Concept Classفئة المفاهيم
Hypothesisفرضية
Sample Complexityتعقيد العينة
Distribution-Free Learningالتعلم الحُرّ التوزيع
Boolean Functionدالة بولية
Generalizationالتعميم
Supervised Learningالتعلم الـمُوجّه (المصحوب ببيانات مرجعية)
VC Dimensionبُعد VC