# Learning from positive and unlabeled examples -Finite size sample bounds

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 44 references that are in the map.
- First posted on arXiv 10 Jul 2025.

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

- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [Mixture Proportion Estimation via Kernel Embedding of Distributions](https://mlsanity.com/paper/1603.02501/) (2016)
- [Class-prior Estimation for Learning from Positive and Unlabeled Data](https://mlsanity.com/paper/1611.01586/) (2016)
- [Non-Negative Bregman Divergence Minimization for Deep Direct Density Ratio Estimation](https://mlsanity.com/paper/2006.06979/) (2020)
- [Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning](https://mlsanity.com/paper/1603.03130/) (2016)
- [Beyond the Selected Completely At Random Assumption for Learning from Positive and Unlabeled Data](https://mlsanity.com/paper/1809.03207/) (2018)
- [Estimating the class prior and posterior from noisy positives and unlabeled data](https://mlsanity.com/paper/1606.08561/) (2016)
- [Learning from Positive and Unlabeled Data with Arbitrary Positive Shift](https://mlsanity.com/paper/2002.10261/) (2020)
- [Instance-Dependent PU Learning by Bayesian Optimal Relabeling](https://mlsanity.com/paper/1808.02180/) (2018)

## Built on by (most cited first, 6 of 6)

- [Learning from Synthetic Data: Limitations of ERM](https://mlsanity.com/paper/2601.15468/) (2026)
- [Hitting a Moving Target: Test-Time Adaptation for AI Text Detection under Continual Distribution Shift](https://mlsanity.com/paper/2606.25152/) (2026)
- [Active learning from positive and unlabeled examples](https://mlsanity.com/paper/2602.02081/) (2026)
- [Generating Causal Temporal Interaction Graphs for Counterfactual Validation of Temporal Link Prediction](https://mlsanity.com/paper/2602.02161/) (2026)
- [Surprises in Proper Positive-Only Learning](https://mlsanity.com/paper/2606.28309/) (2026)
- [Minimax bounds for watermarked and masked recursive discrete distribution estimation](https://mlsanity.com/paper/2608.31091/) (2026)

## Abstract (arXiv)

PU (Positive Unlabeled) learning is a variant of supervised classification learning in which the only labels revealed to the learner are of positively labeled instances. PU learning arises in many real-world applications. Most existing work relies on the simplifying assumptions that the positively labeled training data is drawn from the restriction of the data generating distribution to positively labeled instances and/or that the proportion of positively labeled points (a.k.a. the class prior) is known apriori to the learner. This paper provides a theoretical analysis of the statistical complexity of PU learning under a wider range of setups. Unlike most prior work, our study does not assume that the class prior is known to the learner. We prove upper and lower bounds on the required sample sizes (of both the positively labeled and the unlabeled samples).