Positive-Unlabeled Learning with Extreme Scarcity of Labeled Positives

Yuanchao Dai, Ximing Li, Wei Wang, Changchun Li, Gang Niu, Masashi Sugiyama
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:22509-22527, 2026.

Abstract

Positive-Unlabeled (PU) learning is a weakly-supervised paradigm that trains a binary classifier from labeled positive and unlabeled instances. In PU risk estimation, the empirical risk consists of an unlabeled term and a positive term. In this paper, we observe that when labeled positives are scarce, the risk deviation is dominated by the generalization bound of the positive term, which is composed of a complexity term governed by Rademacher complexity and a concentration term governed by the uniform range bound, leading to estimator instability. Based on this observation, we theoretically derive the sufficient sample threshold, defined as the smallest number of labeled positives required to achieve a target excess risk with high probability, and reveal its explicit dependence on both components. Inspired by this insight, we propose ScalePU, which incorporates variance regularization to induce a restricted sub-hypothesis space with reduced Rademacher complexity, and geometric regularization to encourage compact clustering of positive samples with a tighter effective range. Theoretical analysis demonstrates that both mechanisms effectively lower the threshold through improvements to different components of the bound. Experiments on eight benchmark datasets validate the effectiveness of ScalePU, with significant improvements under extreme label scarcity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-dai26f, title = {Positive-Unlabeled Learning with Extreme Scarcity of Labeled Positives}, author = {Dai, Yuanchao and Li, Ximing and Wang, Wei and Li, Changchun and Niu, Gang and Sugiyama, Masashi}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {22509--22527}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/dai26f/dai26f.pdf}, url = {https://proceedings.mlr.press/v306/dai26f.html}, abstract = {Positive-Unlabeled (PU) learning is a weakly-supervised paradigm that trains a binary classifier from labeled positive and unlabeled instances. In PU risk estimation, the empirical risk consists of an unlabeled term and a positive term. In this paper, we observe that when labeled positives are scarce, the risk deviation is dominated by the generalization bound of the positive term, which is composed of a complexity term governed by Rademacher complexity and a concentration term governed by the uniform range bound, leading to estimator instability. Based on this observation, we theoretically derive the sufficient sample threshold, defined as the smallest number of labeled positives required to achieve a target excess risk with high probability, and reveal its explicit dependence on both components. Inspired by this insight, we propose ScalePU, which incorporates variance regularization to induce a restricted sub-hypothesis space with reduced Rademacher complexity, and geometric regularization to encourage compact clustering of positive samples with a tighter effective range. Theoretical analysis demonstrates that both mechanisms effectively lower the threshold through improvements to different components of the bound. Experiments on eight benchmark datasets validate the effectiveness of ScalePU, with significant improvements under extreme label scarcity.} }
Endnote
%0 Conference Paper %T Positive-Unlabeled Learning with Extreme Scarcity of Labeled Positives %A Yuanchao Dai %A Ximing Li %A Wei Wang %A Changchun Li %A Gang Niu %A Masashi Sugiyama %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-dai26f %I PMLR %P 22509--22527 %U https://proceedings.mlr.press/v306/dai26f.html %V 306 %X Positive-Unlabeled (PU) learning is a weakly-supervised paradigm that trains a binary classifier from labeled positive and unlabeled instances. In PU risk estimation, the empirical risk consists of an unlabeled term and a positive term. In this paper, we observe that when labeled positives are scarce, the risk deviation is dominated by the generalization bound of the positive term, which is composed of a complexity term governed by Rademacher complexity and a concentration term governed by the uniform range bound, leading to estimator instability. Based on this observation, we theoretically derive the sufficient sample threshold, defined as the smallest number of labeled positives required to achieve a target excess risk with high probability, and reveal its explicit dependence on both components. Inspired by this insight, we propose ScalePU, which incorporates variance regularization to induce a restricted sub-hypothesis space with reduced Rademacher complexity, and geometric regularization to encourage compact clustering of positive samples with a tighter effective range. Theoretical analysis demonstrates that both mechanisms effectively lower the threshold through improvements to different components of the bound. Experiments on eight benchmark datasets validate the effectiveness of ScalePU, with significant improvements under extreme label scarcity.
APA
Dai, Y., Li, X., Wang, W., Li, C., Niu, G. & Sugiyama, M.. (2026). Positive-Unlabeled Learning with Extreme Scarcity of Labeled Positives. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:22509-22527 Available from https://proceedings.mlr.press/v306/dai26f.html.

Related Material