Surprises in Proper Positive-Only Learning: Deep Dive
This post reviews "Surprises in Proper Positive-Only Learning" by Shai Ben-David, Farnam Mansouri, and Anay Mehrotra (June 2026), a machine learning theory paper that resolves an open problem posed by Natarajan in 1987.
| Item | Detail | |------|--------| | Title | Surprises in Proper Positive-Only Learning | | Authors | Shai Ben-David, Farnam Mansouri, Anay Mehrotra | | Area | Machine learning theory / computational learning theory | | Core contribution | First full characterization of proper Positive-Only learnability, revealing a rich landscape distinct from standard PAC learning |
The thought experiment: a recognizer that has only seen smiles
Imagine a baby raised in a room where every visitor must smile. Having never seen a frown, tears, or a neutral expression, the baby believes "a human face is a smiling face." When finally shown the outside world, how should it decide whether a non-smiling face is a face at all?
This captures Positive-Only Learning (learning from positive and unlabeled data): the learner sees only positive-class samples, yet is evaluated on the full distribution containing both classes. Proper learning additionally requires the output hypothesis to belong to the same concept class as the target (e.g., the hypothesis must be a circle if the target concepts are circular regions).
Why it matters
Negative labels are often missing, expensive, or impossible to obtain:
- Medical diagnosis: hospitals have records of diagnosed patients, but healthy people never enter the database.
- Fraud detection: confirmed fraud cases are labeled; normal transactions are overwhelmingly numerous and unlabeled.
- Anomaly detection: failures are rare and varied; only normal-operation data is abundant.
The core 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 any concept, after removing arbitrary subsets of the positive region, be uniformly describable in a way independent of the particular concept.
Geometrically: if a concept class is a family of circular regions, the condition asks whether the outside of the positive region always shares a uniform structural signature the learner can infer from positive samples alone. It is weaker than convexity but stronger than mere finite VC dimension.
Four surprising separations
Unlike standard PAC learning, where finite VC dimension essentially settles everything, positive-only proper learning exhibits a much richer landscape:
1. Proper vs. improper learning separate. Some classes are improperly learnable from positive-only data but not properly learnable. "Being able to recognize" and "being able to express the concept properly" are not the same thing here. 2. Randomized vs. deterministic proper learning separate. Some classes are properly learnable by randomized algorithms but not by deterministic ones. Randomization becomes a capability requirement, not merely a convenience. 3. Finite VC dimension is not enough even for non-uniform learning, where each target concept may have its own sample complexity. Uniform Exterior Separability is indispensable, not a bonus. 4. ERM can fail entirely. There exist classes for which no Empirical Risk Minimization algorithm properly positive-only learns, meaning standard PAC recipes cannot simply be imported.
New combinatorial tools
The paper introduces new combinatorial dimensions (e.g., an "external dimension" measuring the complexity of exterior regions, and a "separation dimension" measuring how hard it is to infer the exterior from positives). These are designed for positive-only learning but, in the authors' view, may have broader interest for other settings such as active learning, transfer learning, and meta-learning.
Historical context
Natarajan's 1987 model predated the deep learning era; what looked like a theoretical curiosity has become highly practical as positive-only and positive-unlabeled scenarios proliferate. With this result, the open-problem note in standard textbooks (e.g., Kearns & Vazirani) can be replaced by a complete characterization — a continuation of the theoretical CS tradition of crisp if-and-only-if characterizations, in the spirit of NP-completeness and the VC dimension.
Conclusion
The results are sobering — learning from half the world is much harder than standard PAC analysis suggests — but also encouraging: proper positive-only learning remains possible whenever Uniform Exterior Separability holds, and many natural concept classes do satisfy it. The deeper lesson is that the PAC framework with both labeled classes is just one special case; deviating from it exposes genuinely new structure in learnability.
References
1. Ben-David, S., Mansouri, F., & Mehrotra, A. (2026). *Surprises in Proper Positive-Only Learning*. 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. 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*. 6. Blumer, A., et al. (1989). Learnability and the Vapnik-Chervonenkis dimension. *Journal of the ACM*.