What is Learnable in Valiant's Theory of the Learnable?

Steve Hanneke; Anay Mehrotra; Grigoris Velegkas; Manolis Zampetakis

stat.MLMay 13, 2026

What is Learnable in Valiant's Theory of the Learnable?

Authors: Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis

Organizations: Purdue University · Stanford University · Google Research · Yale University

Abstract

Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: Which classes are learnable in it? For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that $d$ -dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a $\mathrm{poly}(d) \tilde{O}(1/ε)$ sample and $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ query algorithm, and prove that at least $Ω(d)$ samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.

Explore similar work

Sep 25, 2025cs.DS

Actively Learning Halfspaces without Synthetic Data

In the classic point location problem, one is given an arbitrary dataset

X \subset \mathbb{R}^d

n

points with query access to an unknown halfspace

f : \mathbb{R}^d \to \{0,1\}

, and the goal is to learn the label of every point in

X

. This problem is extremely well-studied and a nearly-optimal

\widetilde{O}(d \log n)

query algorithm is known due to Hopkins-Kane-Lovett-Mahajan (FOCS 2020). However, their algorithm is granted the power to query arbitrary points outside of

X

(point synthesis), and in fact without this power there is an

Ω(n)

query lower bound due to Dasgupta (NeurIPS 2004). In this work our goal is to design efficient algorithms for learning halfspaces without point synthesis. To circumvent the

Ω(n)

lower bound, we consider learning halfspaces whose normal vectors come from a set of size

D

, and show tight bounds of

Θ(D + \log n)

. As a corollary, we obtain an optimal

O(d + \log n)

query deterministic learner for axis-aligned halfspaces, closing a previous gap of

O(d \log n)

vs.

Ω(d + \log n)

. In fact, our algorithm solves the more general problem of learning a Boolean function

f

over

n

elements which is monotone under at least one of

D

provided orderings. Our technical insight is to exploit the structure in these orderings to perform a binary search in parallel rather than considering each ordering sequentially, and we believe our approach may be of broader interest. Furthermore, we use our exact learning algorithm to obtain nearly optimal algorithms for PAC-learning. We show that

O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)

queries suffice to learn

f

within error

\varepsilon

, even in a setting when

f

can be adversarially corrupted on a

c\varepsilon

-fraction of points, for a sufficiently small constant

c

. This bound is optimal up to a

\log D

factor, including in the realizable setting.

Hadley Black, Kasper Green Larsen, Arya Mazumdar +2

Optimal Sample Complexity Synthetic Data Shortest Paths

Ask PDF

Jun 26, 2026stat.ML

Surprises in Proper Positive-Only Learning

Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative regions). This model dates back to Natarajan [1987, STOC], and the characterization of improper learning is well-known -- it even appears in textbooks. The characterization of proper positive-only learning, however, has long remained open. In this work, we revisit and settle this question: a concept class is properly learnable from positive-only samples if and only if it has finite VC dimension and satisfies a new combinatorial condition, which we call uniform exterior separability. Together with several separation results, this characterization reveals a surprisingly rich landscape that differs sharply from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there are classes for which no ERM is a learner, and finite VC dimension does not suffice even for non-uniform learning. Along the way, we introduce new combinatorial dimensions that we believe can be of broader interest in learning theory.

Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1

Surprisal Voice Conversion

Ask PDF

Apr 16, 2026cs.DS

Tight Bounds for Learning Polyhedra with a Margin

We give an algorithm for PAC learning intersections of

k

halfspaces with a

ρ

margin to within error

\varepsilon

that runs in time

\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\right)

. Notably, this improves on prior work which had an exponential dependence on either

k

ρ^{-1}

and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in

k

and

ρ

in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least

ρ

from the boundary of the polyhedron, making it applicable to continuous distributions as well.

Shyamal Patel, Santosh Vempala

Polytopes Tight Bounds Optimal Sample Complexity Lower Bounds Polynomials

Ask PDF