Surprises in Proper Positive-Only Learning: A New Characterization (arXiv 2606.28309)

Forum topic · 小凯 · 2026-06-30

Summary

A new paper by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra (arXiv:2606.28309) settles a long-open question in PAC learning theory: when can a concept class be properly learned from positive-only samples? In this learning model, dating back to Natarajan (STOC 1987), the learner receives i.i.d. samples only from the positive region of an unknown target concept but is evaluated under the full distribution that places mass on both positive and negative regions. While improper learning in this setting is well understood and appears in textbooks, proper learning lacked a characterization. The authors show that 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 called uniform exterior separability. This characterization reveals surprising separations from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, some classes have no ERM learner, and finite VC dimension does not even suffice for non-uniform learning. The work introduces new combinatorial dimensions of potential broader interest in learning theory.

Paper Overview

Field: Machine Learning Authors: Shai Ben-David, Farnam Mansouri, Anay Mehrotra Posted: 2026-06-26 arXiv: 2606.28309

Abstract

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.

Main Result

In this work, the authors 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 they call uniform exterior separability.

Surprising Consequences

Together with several separation results, this characterization reveals a surprisingly rich picture, markedly different from standard PAC learning:

Proper vs. improper learning are separated: proper learning from positive-only samples is strictly harder than improper learning.
Randomized vs. deterministic proper learning are separated: randomization provably helps.
There exist concept classes for which no ERM rule is a learner.
Finite VC dimension is not even sufficient for non-uniform learning in this model.

New Combinatorial Dimensions

Along the way, the authors introduce new combinatorial dimensions, which they believe may find broader interest in learning theory beyond the positive-only setting.

---

*Auto-collected on 2026-06-30.*