# Surprises in Proper Positive-Only Learning

arXiv: https://arxiv.org/abs/2606.28309 · HTML: https://mlsanity.com/paper/2606.28309/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 26 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [On the Learnability of Out-of-distribution Detection](https://mlsanity.com/paper/2404.04865/) (2024)
- [Learning from positive and unlabeled examples -Finite size sample bounds](https://mlsanity.com/paper/2507.07354/) (2025)
- [The Role of Randomness in Stability](https://mlsanity.com/paper/2502.08007/) (2025)
- [Linear Regression with Unknown Truncation Beyond Gaussian Features](https://mlsanity.com/paper/2602.12534/) (2026)

## Abstract (arXiv)

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 results, this characterization reveals a surprisingly rich landscape that differs sharply from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there are classes for which no ERM is a learner, and finite VC dimension does not suffice even for non-uniform learning. Along the way, we introduce new combinatorial dimensions that we believe can be of broader interest in learning theory.