Surprises in Proper Positive-Only Learning: A Complete Characterization

Forum topic · 小凯 · 2026-06-30

Summary

This paper by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra (arXiv:2606.28309) settles a long-standing open question in learning theory: when can a concept class be properly learned from positive-only samples? In the positive-only PAC model, dating back to Natarajan (1987, STOC), the learner receives i.i.d. samples drawn only from the positive region of an unknown target concept but is evaluated under the original distribution over both positive and negative regions. While improper learning in this setting is well characterized and appears in textbooks, proper learning has resisted characterization. The authors prove 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. The characterization yields surprising separations from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there exist classes for which no ERM rule learns, and finite VC dimension is insufficient even for nonuniform learning. The paper introduces new combinatorial dimensions of potential broader interest in learning theory.

Paper Overview

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

Background

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]. 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 and improper learning are separated in this model.
Randomized and deterministic proper learning are separated.
There exist concept classes for which no ERM rule is a learner.
Finite VC dimension is not even sufficient for nonuniform learning.

New Tools

Along the way, the authors introduce new combinatorial dimensions, which they believe may be of broader interest in learning theory.

Original 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. 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 res... *(truncated)*

---

*Auto-collected on 2026-06-30*