Learnability with Partial Labels and Adaptive Nearest Neighbors

Nicolás A. Errandonea, Santiago Mazuelas, Jose A. Lozano, Sanjoy Dasgupta
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3439-3447, 2026.

Abstract

Prior work on partial labels learning (PLL) has shown that learning is possible even when each instance is associated with a bag of labels, rather than a single accurate but costly label. However, the necessary conditions for learning with partial labels remain unclear, and existing PLL methods are effective only in specific scenarios. In this work, we mathematically characterize the scenarios in which PLL is feasible. In addition, we present PL A-$k$NN, an adaptive nearest-neighbors algorithm for PLL that is effective in general scenarios and enjoys strong performance guarantees. Experimental results corroborate that PL A-$k$NN can outperform state-of-the-art methods in general PLL scenarios

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-errandonea26a, title = { Learnability with Partial Labels and Adaptive Nearest Neighbors }, author = {Errandonea, Nicol{\'a}s A. and Mazuelas, Santiago and Lozano, Jose A. and Dasgupta, Sanjoy}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3439--3447}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/errandonea26a/errandonea26a.pdf}, url = {https://proceedings.mlr.press/v300/errandonea26a.html}, abstract = { Prior work on partial labels learning (PLL) has shown that learning is possible even when each instance is associated with a bag of labels, rather than a single accurate but costly label. However, the necessary conditions for learning with partial labels remain unclear, and existing PLL methods are effective only in specific scenarios. In this work, we mathematically characterize the scenarios in which PLL is feasible. In addition, we present PL A-$k$NN, an adaptive nearest-neighbors algorithm for PLL that is effective in general scenarios and enjoys strong performance guarantees. Experimental results corroborate that PL A-$k$NN can outperform state-of-the-art methods in general PLL scenarios } }
Endnote
%0 Conference Paper %T Learnability with Partial Labels and Adaptive Nearest Neighbors %A Nicolás A. Errandonea %A Santiago Mazuelas %A Jose A. Lozano %A Sanjoy Dasgupta %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-errandonea26a %I PMLR %P 3439--3447 %U https://proceedings.mlr.press/v300/errandonea26a.html %V 300 %X Prior work on partial labels learning (PLL) has shown that learning is possible even when each instance is associated with a bag of labels, rather than a single accurate but costly label. However, the necessary conditions for learning with partial labels remain unclear, and existing PLL methods are effective only in specific scenarios. In this work, we mathematically characterize the scenarios in which PLL is feasible. In addition, we present PL A-$k$NN, an adaptive nearest-neighbors algorithm for PLL that is effective in general scenarios and enjoys strong performance guarantees. Experimental results corroborate that PL A-$k$NN can outperform state-of-the-art methods in general PLL scenarios
APA
Errandonea, N.A., Mazuelas, S., Lozano, J.A. & Dasgupta, S.. (2026). Learnability with Partial Labels and Adaptive Nearest Neighbors . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3439-3447 Available from https://proceedings.mlr.press/v300/errandonea26a.html.

Related Material