Learnability with Partial Labels and Adaptive Nearest Neighbors

• URL: http://arxiv.org/abs/2603.15781v2
• Date: Fri, 20 Mar 2026 10:35:01 GMT
• Title: Learnability with Partial Labels and Adaptive Nearest Neighbors
• Abstract summary: We mathematically characterize the settings in which is feasible for learning with partial labels.<n>We present PL A-$k$NN, an adaptive nearest-neighbors algorithm for learning with partial labels.
• Score: 13.304461869104344
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Tuning the Right Foundation Models is What you Need for Partial Label Learning [55.61644150441799]
  Partial label learning seeks to train generalizable classifiers from datasets with inexact supervision.<n>In this work, we empirically conduct evaluations of 11 foundation models across 13 approaches on 8 benchmark datasets under 3 scenarios.<n>Our findings reveal that current approaches tend to achieve significant performance gains when using foundation models, 2) exhibit remarkably similar performance to each other, 3) maintain stable performance across varying ambiguity levels, while 4) are susceptible to foundation model selection and adaptation strategies.
  arXiv  Detail & Related papers  (2025-06-05T13:37:33Z)
• Realistic Evaluation of Deep Partial-Label Learning Algorithms [94.79036193414058]
  Partial-label learning (PLL) is a weakly supervised learning problem in which each example is associated with multiple candidate labels and only one is the true label.<n>In recent years, many deep algorithms have been developed to improve model performance.<n>Some early developed algorithms are often underestimated and can outperform many later algorithms with complicated designs.
  arXiv  Detail & Related papers  (2025-02-14T14:22:16Z)
• Appeal: Allow Mislabeled Samples the Chance to be Rectified in Partial Label Learning [55.4510979153023]
  In partial label learning (PLL), each instance is associated with a set of candidate labels among which only one is ground-truth. To help these mislabeled samples "appeal," we propose the first appeal-based framework.
  arXiv  Detail & Related papers  (2023-12-18T09:09:52Z)
• Complementary Classifier Induced Partial Label Learning [54.61668156386079]
  In partial label learning (PLL), each training sample is associated with a set of candidate labels, among which only one is valid. In disambiguation, the existing works usually do not fully investigate the effectiveness of the non-candidate label set. In this paper, we use the non-candidate labels to induce a complementary classifier, which naturally forms an adversarial relationship against the traditional classifier.
  arXiv  Detail & Related papers  (2023-05-17T02:13:23Z)
• ALIM: Adjusting Label Importance Mechanism for Noisy Partial Label Learning [46.53885746394252]
  Noisy partial label learning is an important branch of weakly supervised learning. Most of the existing works attempt to detect noisy samples and estimate the ground-truth label for each noisy sample. We propose a novel framework for noisy with theoretical guarantees, called Adjusting Labeling Mechanism (ALIM)'' It aims to reduce the negative impact of detection errors by trading off the initial candidate set and model outputs.
  arXiv  Detail & Related papers  (2023-01-28T03:42:53Z)
• Progressive Purification for Instance-Dependent Partial Label Learning [37.65717805892473]
  Partial label learning (PLL) aims to train multiclass classifiers from the examples each annotated with a set of candidate labels where a fixed but unknown candidate label is correct. The candidate labels are always instance-dependent in practice and there is no theoretical guarantee that the model trained on the instance-dependent examples can converge to an ideal one. In this paper, a theoretically grounded and practically effective approach named POP, i.e. PrOgressive Purification, is proposed. Specifically, POP updates the learning model and purifies each candidate label set progressively in every epoch.
  arXiv  Detail & Related papers  (2022-06-02T02:07:12Z)
• Few-Shot Partial-Label Learning [25.609766770479265]
  Partial-label learning (PLL) generally focuses on inducing a noise-tolerant multi-class by training on overly-annotated samples. Existing few-shot learning algorithms assume precise labels of the support set; as such, irrelevant labels may seriously mislead the meta-learner. In this paper, we introduce an approach called FsPLL (Few-shot image learning)
  arXiv  Detail & Related papers  (2021-06-02T07:03:54Z)
• Provably Consistent Partial-Label Learning [120.4734093544867]
  Partial-label learning (PLL) is a multi-class classification problem, where each training example is associated with a set of candidate labels. In this paper, we propose the first generation model of candidate label sets, and develop two novel methods that are guaranteed to be consistent. Experiments on benchmark and real-world datasets validate the effectiveness of the proposed generation model and two methods.
  arXiv  Detail & Related papers  (2020-07-17T12:19:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.