What Valiant Actually Defined: Revisiting the Original Theory of the Learnable

For nearly four decades, Leslie Valiant's 1984 paper "A Theory of the Learnable" has been cited as the origin of the Probably Approximately Correct (PAC) framework. Generations of students have learned the PAC model and quietly assumed it was the model Valiant wrote down. It was not. The paper "What is Learnable in Valiant's Theory of the Learnable?" by Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, and Manolis Zampetakis returns to the source and shows that the model Valiant actually defined differs from PAC learning in three structural ways, and that these differences change which classes are learnable, not merely how efficiently they can be learned.

This is a subtle and worthwhile correction to the historical record, but the paper goes much further than historiography. It gives a clean characterization of learnability in Valiant's original model, and it demonstrates a rare phenomenon: a setting where the addition of membership queries expands the set of learnable concept classes rather than just reducing the sample or time complexity.

The Three Asymmetries of Valiant's Model

To appreciate the result, it helps to be precise about how Valiant's original model differs from the PAC model that inherited its name. A learner in Valiant's model:

• Sees only positive examples. The training distribution $D$ is supported entirely on the positive region of the target $h^\star$, meaning $\text{supp}(D) \subseteq \text{supp}(h^\star)$. The learner never observes a labeled negative example from the data stream.
• Must produce a one-sided hypothesis. The output $h$ must satisfy $\text{supp}(h) \subseteq \text{supp}(h^\star)$, that is, zero false positives. It is permitted to miss up to an $\varepsilon$ fraction of the positive distribution, but it may never assert positivity where the target is negative.
• May issue membership queries. The learner can ask the oracle "is $h^\star(x) = 1$?" for any point $x$ in the domain, including points it would never see in the positive sample stream.

In the canonical Boolean hypercube setting, $H = (H_1, H_2, \ldots)$ where each $H_d$ is a class of Boolean functions on ${0,1}^d$, learnability requires the number of examples and queries to be $\text{poly}(d, 1/\varepsilon, 1/\delta)$. The polynomial dependence on the ambient dimension $d$ is essential, because the domain ${0,1}^d$ is finite and one could trivially memorize any target with $2^d$ queries. The model is therefore genuinely about generalization, not enumeration.

The combination of positive-only data and a one-sided guarantee is what makes the model interesting. Without queries, the learner faces a hard problem: it observes points it knows are positive, but it has no direct information about where the boundary of $h^\star$ lies. It can only safely predict positive on regions it can certify as inside the target. Membership queries give it a way to probe outward from observed positives and certify additional structure.

The Characterization: Adaptive Query-Compression

The central result is a clean equivalence. A concept class over a finite domain is learnable in Valiant's model if and only if every realizable positive sample admits a polynomial-size adaptive query-compression scheme. This holds for every finite domain, and in particular for Valiant's original Boolean-hypercube setting where the polynomial must be in $d$.

This deserves unpacking because it modifies one of the most elegant ideas in learning theory. Classical sample compression schemes, introduced by Littlestone and Warmuth and later shown by Moran and Yehudayoff and others to be tightly connected to PAC learnability, work as follows: from any labeled sample consistent with some target, you can select a small subset of examples (the compression set) from which a reconstruction function recovers a hypothesis consistent with the full sample. The size of the compression set, if bounded independently of the sample size, characterizes learnability up to logarithmic factors. Compression is non-interactive: the compression set is a static certificate.

The new notion replaces the static certificate with an interactive one. Instead of selecting a subset of the observed sample, the compression scheme certifies a positive sample through a short adaptive interaction with the membership oracle. The learner asks a polynomial number of queries, each potentially chosen based on earlier answers, and uses the transcript to certify that its hypothesis introduces no false positives while covering the observed sample. The authors call this a query-compression scheme, and they prove that polynomial-size adaptive query-compression is both necessary and sufficient for learnability.

The proof has several moving parts that are independently interesting:

• A boosting argument specific to Valiant's model, showing that weak learners can be amplified while preserving the zero-false-positive constraint.
• A reduction establishing uniform success over all potential targets, which is needed because the one-sided guarantee must hold against an adversarially chosen $h^\star$.
• Both directions of the equivalence: learnability implies query-based compression, and query-based compression implies learnability.
• A VC-dimension lower bound that pins down the sample complexity within polynomial factors.

The result is that the sample complexity of learning in Valiant's model is controlled, up to polynomial factors, by the size of the smallest adaptive query-compression scheme. This is a satisfying parallel to the PAC story, with interaction substituted for static selection.

Strictly Sandwiched, and the Halfspace Example

The most conceptually striking consequence is that learnability in Valiant's model is strictly sandwiched between two neighbors:

1. PAC learnability (the strongest, since it has two-sided data and two-sided error tolerance),
2. Valiant's model with queries,
3. The query-free positive-only variant studied by Natarajan (STOC 1987), Shvaytser (1990), and Kivinen (1995).

The strictness in both directions is the point. There exist classes that are PAC learnable but not learnable in Valiant's model, and there exist classes learnable in Valiant's model but not learnable without queries. The latter inclusion being strict is the unusual part. In most of learning theory, membership queries are a convenience: they can lower sample complexity or speed up computation, but the family of learnable classes typically does not change. Here it does.

The cleanest illustration is halfspaces over $\mathbb{R}^d$. The authors prove that halfspaces are not learnable in the query-free positive-only model for any $d \geq 2$, yet they become learnable once membership queries are allowed. Concretely, they give an algorithm using

$$\text{poly}(d) \cdot e^{O((\log 1/\delta)/\varepsilon)} \text{ samples and } \text{poly}(d) \cdot \text{polylog}(1/\varepsilon\delta) \text{ queries},$$

and they show a matching $\Omega(d)$ lower bound on samples or queries. To the best of the authors' knowledge, this is the first algorithm to learn halfspaces in Valiant's model without assuming finite bit-complexity. Prior work could only handle bounded-precision halfspaces, which collapses the problem to learning a finite class and sidesteps the genuine geometric difficulty.

My Take

What I find most valuable here is the demonstration that interaction can be a certification primitive rather than just an efficiency primitive. The classical compression-learnability correspondence is about what can be summarized; the new query-compression notion is about what can be verified through dialogue. This is a meaningfully different intuition, and I suspect it has applications beyond Valiant's specific model.

Consider the analogy to interactive proofs. Static compression is to query-compression roughly as NP is to interactive verification: in both cases, allowing an adaptive exchange with an oracle certifies things a static witness cannot. The halfspace result makes this concrete. A positive sample of points inside a halfspace gives you a convex hull, but it tells you nothing about the orientation of the separating hyperplane far from the data. Queries let you binary-search toward the boundary and certify safe extensions. Without that interaction, the geometry simply does not constrain the false-positive region enough.

I would also flag what the result implies about the historical mislabeling. Calling Valiant's model "PAC" obscured a genuinely distinct and harder learning problem. The one-sided, positive-only setting is closer to many realistic situations than symmetric PAC learning: anomaly detection, learning from positive-unlabeled data, and safety-critical classification where false positives carry asymmetric cost all have this flavor. A theory that characterizes exactly when zero-false-positive learning is feasible is directly relevant to those settings.

The honest limitations are clear from the paper itself. The exact characterization holds for finite domains. For arbitrary domains, the authors do not obtain an exact characterization; their techniques generalize enough to prove the strict sandwich but not to pin down learnability completely. The halfspace algorithm also carries an $e^{O((\log 1/\delta)/\varepsilon)}$ sample dependence, which is far from the polynomial-in-$1/\varepsilon$ behavior we expect from clean PAC results. Whether this exponential dependence is necessary or an artifact of the technique is an open question.

Conclusion

The paper recovers a model that was hiding in plain sight for forty years and gives it the characterization it deserves. The adaptive query-compression notion is a genuine addition to the toolkit connecting compression and learnability, and the halfspace result is a rare clean example where membership queries change the learnable, not just the efficient. The open questions are inviting: an exact characterization over general domains, the true sample complexity of halfspaces in this model, and whether query-compression schemes have an analogue of the deep VC-to-compression bounds known for PAC learning. More broadly, I would like to see whether interaction-as-certification clarifies other settings where one-sided guarantees matter. If it does, this revisiting of Valiant's original definition will have repaid the attention many times over.