Surprises in Proper Positive-Only Learning: A Full Characterization

Forum topic · 小凯 · 2026-06-30

Summary

This paper by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra (arXiv:2606.28309) settles a long-open question in learning theory: when is a concept class properly learnable from positive-only samples? In this PAC-learning variant, 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 that places mass on both positive and negative regions. While improper learning from positive-only samples is well characterized (and appears in textbooks), proper learning was not. The authors prove that a class is properly learnable from positive-only samples if and only if it has finite VC dimension and satisfies a new combinatorial condition they call uniform exterior separability. The characterization yields surprising separations from standard PAC learning: proper and improper learning differ, randomized and deterministic proper learning differ, some classes have no ERM learner, and finite VC dimension does not even suffice for nonuniform learning. The paper also introduces new combinatorial dimensions of independent interest.

Overview

Field: Machine Learning (Learning Theory) Authors: Shai Ben-David, Farnam Mansouri, Anay Mehrotra Published: 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.

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.

Key Findings

Together with several separation results, this characterization reveals a surprisingly rich picture, starkly contrasting with standard PAC learning:

Proper vs. improper learning are separated — access to only positive samples makes proper learning strictly harder.
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 in this setting.

Along the way, the paper introduces new combinatorial dimensions, which the authors believe may find broader interest in learning theory.

--- *Source: arXiv:2606.28309*