Learnability with Partial Labels and Adaptive Nearest Neighbors

Nicolas A. Errandonea; Santiago Mazuelas; Jose A. Lozano; Sanjoy Dasgupta

stat.MLMar 16, 2026

Learnability with Partial Labels and Adaptive Nearest Neighbors

Authors: Nicolas A. Errandonea, Santiago Mazuelas, Jose A. Lozano, Sanjoy Dasgupta

Organizations: Basque Center for Applied Mathematics, Bilbao, Spain · Ikerbasque, Basque Foundation for Science · University of the Basque Country, Spain · University of California San Diego, USA

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 settings 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.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of the error rates of PL A- $k$ NN and state-of-the-art methods for Fashion-MNIST and MSCRv2 under an increasing noise rate. The results show that PL A- $k$ NN consistently outperforms existing approaches across a wide range of noise levels. See Appendix D for the comparison in MNIST CIFAR10 and MirFlickr.

Panel of Figure 2 — Figure 2: Comparison of the error rates of PL A- $k$ NN and state-of-the-art methods for Fashion-MNIST and MSRCv2 under an increasing noise rate. The results show that PL A- $k$ NN outperforms $10$ -NN and A- $k$ NN across a wide range of noise levels, while having comparable performance to the best $k$ NN. See Appendix D for the comparison in MNIST CIFAR10 and MirFlickr.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Comparison of the error rates of PL A- $k$ NN and state-of-the-art methods for MNIST, CIFAR-10, and MirFlickr under an increasing noise rate. The results show that PL A- $k$ NN outperforms existing approaches across a wide range of noise levels.

Panel of Figure 4 — Figure 4: Comparison of the error rates of PL A- $k$ NN and $k$ NN benchmarks for MNIST, CIFAR-10, and MirFlickr under an increasing noise rate. The results show that PL A- $k$ NN outperforms $10$ -NN and A- $k$ NN across a wide range of noise levels, while having comparable performance to the best $k$ -NN.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 578 papers

Rethinking Learning from Label Proportions via Moment Matching
Oct 15, 2026Tianhao Ma, Wei Wang, Yivan Zhang +4Weakly Supervised Learning
The University of Tokyo · RIKEN AIP
Learning from Label Proportions with Dual-proportion Constraints
Mar 22, 2026Tianhao Ma, Ximing Li, Changchun Li +1Weakly Supervised Learning
The University of Tokyo, Japan · College of Computer Science and Technology, Jilin University, China · Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, China +1
Calibrated Disambiguation for Partial Multi-label Learning
Oct 13, 2026Zhuoming Li, Yuheng Jia, Mi Yu +1Multi-Label Classification Noisy-Label Learning
School of Computer Science and Engineering, Southeast University · China Telecom Cloud Computing Corporation, Beijing 100088, China

Oct 15, 2026J/K move · Enter open · S save

Rethinking Learning from Label Proportions via Moment Matching

Tianhao Ma, Wei Wang, Yivan Zhang, Dong-Dong Wu+3

The University of Tokyo · RIKEN AIP

Weakly Supervised Learning

Open paper AskPDF arXiv

Learning from label proportions (LLP) is a weakly supervised setting where training data are grouped into bags with only bag-level label proportions observed, and the goal is to learn a classifier that predicts labels for individual instances. Recently, a large body of methods has emerged; however, most of them rely on the assumption that instance-label pairs are sampled i.i.d. and randomly assembled into bags, an assumption often violated in real-world scenarios. Our experimental results indicate that these methods perform suboptimally under non-random settings. In this work, we adopt a more realistic assumption: bags are sampled i.i.d., and instance labels are conditionally independent given the instances. Under this setting, we show that the label counts follow a Poisson multinomial distribution. Motivated by this observation, we propose LLP via moment matching (LLP-MM), a simple yet effective approach which leverages multi-order factorial moments as training objectives, encouraging the classifier predictions to match these moments and thereby more fully exploit the underlying statistical structure of the data. Extensive experiments on benchmark datasets under various bag construction strategies demonstrate the effectiveness of our approach while maintaining high computational efficiency. Our code is available at https://github.com/TianhaoMa5/LLP-MM.

Abstract

Statistical Learning Theory

Explore similar work

Rethinking Learning from Label Proportions via Moment Matching

Learning from Label Proportions with Dual-proportion Constraints

Calibrated Disambiguation for Partial Multi-label Learning