Surprises in Proper Positive-Only Learning: Characterization by VC Dimension and Uniform Exterior Separability

Forum topic · 小凯 · 2026-06-30

Summary

A paper by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra (arXiv:2606.28309) settles a long-open question in PAC learning theory: which concept classes can be properly learned from positive-only samples. In this learning model, dating back to Natarajan (1987, STOC), the learner receives i.i.d. samples 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. The authors prove that proper positive-only learnability holds if and only if the class 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 differ, randomized and deterministic proper learning differ, some classes have no ERM learner, and finite VC dimension is insufficient even for nonuniform learning. The work introduces new combinatorial dimensions of potential broad interest in learning theory.

Paper 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 landscape, starkly different from standard PAC learning:

Proper and improper learning from positive-only samples are separated.
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.

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

---

*Auto-collected on 2026-06-30 from zhichai.net.*