Surprises in Proper Positive-Only Learning: When ML Loses Its Negative Examples

Forum topic · 小凯 · 2026-06-29

Summary

A new theory paper by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra, 'Surprises in Proper Positive-Only Learning,' resolves an open problem in computational learning theory first posed by Natarajan in 1987. Positive-only learning studies whether a model can learn a concept class when it only sees positive samples but is tested on the full distribution. While improper positive-only learning is fully characterized by finite VC dimension, the conditions for proper learning—where the hypothesis must come from the same concept class—remained unknown for nearly 40 years. The paper proves that proper positive-only learning is possible if and only if the concept class has finite VC dimension and satisfies a new combinatorial condition called Uniform Exterior Separability. The authors further derive striking separation results: proper and improper learning diverge in this setting; randomized proper learning can succeed where deterministic proper learning fails; finite VC dimension is insufficient even for non-uniform learning; and no ERM algorithm can properly learn some classes. The work introduces new combinatorial dimensions with potential broader applications and rewrites a long-standing textbook open problem.

Overview

Surprises in Proper Positive-Only Learning by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra (June 2026) gives the first complete characterization of learnability under *proper* positive-only learning, resolving an open problem posed by Natarajan in 1987. The paper combines the full characterization with a series of surprising separation results showing that positive-only learning behaves very differently from standard PAC learning.

Background

Positive-only learning: the learner sees i.i.d. samples drawn only from the positive region of a target concept, but is evaluated on the original distribution containing both positive and negative regions. Natarajan introduced this model in 1987.
Proper learning: the output hypothesis must belong to the same concept class as the target (e.g., output a circle if circles are the concept class), as opposed to improper learning, where any accurate hypothesis is allowed.
Known result: improper positive-only learning is possible exactly when the class has finite VC dimension. Proper learning, however, remained open in textbooks (e.g., Kearns & Vazirani) for nearly 40 years.
Why it matters: real applications—medical diagnosis, fraud detection, anomaly detection—often have positive (or negative) labels that are missing, costly, or impossible to obtain.

Key points

Main theorem

A concept class is properly learnable from positive-only samples if and only if: 1. It has finite VC dimension, and 2. It satisfies Uniform Exterior Separability — a new combinatorial condition requiring that the exterior (negative region) of the positive area can be described by a separation function that is uniform over the class, even after arbitrary subsets are removed from the positive region. Intuitively: the outside of a concept must have features that can be inferred from inside samples alone, regardless of which concept is chosen.

Four surprising separations from standard PAC learning

Proper vs. improper learning separate: some classes are improperly learnable from positives only but not properly learnable. In standard PAC, both coincide (finite VC dimension suffices for both).
Randomized vs. deterministic proper learning separate: some classes are properly learnable by randomized algorithms but not by deterministic ones. In standard PAC, randomization adds no learnability power.
Finite VC dimension is not enough even for non-uniform learning: even the relaxed non-uniform notion of learnability fails without Uniform Exterior Separability.
ERM fails: there exist concept classes for which *no* Empirical Risk Minimization algorithm can properly learn from positive-only data. Standard PAC workhorses cannot simply be ported to this setting.

New tools

The paper introduces new combinatorial dimensions (e.g., an *external dimension* measuring the complexity of a class's exterior regions, and a *separation dimension* measuring how hard it is to infer the exterior from positive samples). The authors believe these tools may have broader applications beyond positive-only learning, e.g., in active or transfer learning.

Historical significance

Natarajan posed the model at STOC 1987; textbooks have flagged proper positive-only learning as an open problem ever since. This paper closes that gap with an if-and-only-if characterization.
The result exemplifies theoretical computer science's tradition of crisp characterizations of complex phenomena (like VC dimension for PAC learning or NP-completeness for hardness).
Practically, the results caution that positive-only settings (medicine, fraud, anomaly detection) demand fundamentally new algorithm design rather than reusing standard PAC methods—while also showing learning remains feasible for many natural concept classes that satisfy Uniform Exterior Separability.

References

[1] Ben-David, S., Mansouri, F., & Mehrotra, A. (2026). *Surprises in Proper Positive-Only Learning*. arXiv preprint. [2] Natarajan, B. K. (1987). Machine learning: a theoretical approach. *STOC*. [3] Vapnik, V. N., & Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. *Theory of Probability and Its Applications*, 16(2), 264-265. [4] Kearns, M. J., & Vazirani, U. V. (1994). *An Introduction to Computational Learning Theory*. MIT Press. [5] Valiant, L. G. (1984). A theory of the learnable. *Communications of the ACM*, 27(11), 1134-1142. [6] Blumer, A., et al. (1989). Learnability and the Vapnik-Chervonenkis dimension. *Journal of the ACM*, 36(4), 929-965.