# Learnability with Partial Labels and Adaptive Nearest Neighbors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 16 Mar 2026.

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

- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Progressive Identification of True Labels for Partial-Label Learning](https://mlsanity.com/paper/2002.08053/) (2020)
- [Provably Consistent Partial-Label Learning](https://mlsanity.com/paper/2007.08929/) (2020)
- [Leveraged Weighted Loss for Partial Label Learning](https://mlsanity.com/paper/2106.05731/) (2021)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Progressive Purification for Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2206.00830/) (2022)
- [On the Robustness of Average Losses for Partial-Label Learning](https://mlsanity.com/paper/2106.06152/) (2021)
- [An adaptive nearest neighbor rule for classification](https://mlsanity.com/paper/1905.12717/) (2019)

## Abstract (arXiv)

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 settings in which PLL is feasible. In addition, we present PL A-kNN, an adaptive nearest-neighbors algorithm for PLL that is effective in general scenarios and enjoys strong performance guarantees. Experimental results corroborate that PL A-kNN can outperform state-of-the-art methods in general PLL scenarios.