Risk-Consistent Multiclass Learning from Random Label-Subset Membership Queries

• URL: http://arxiv.org/abs/2605.07413v1
• Date: Fri, 08 May 2026 08:05:02 GMT
• Title: Risk-Consistent Multiclass Learning from Random Label-Subset Membership Queries
• Abstract summary: This paper proposes a multiclass learn ing framework under random label-subset queries.<n>We derive an unbiased estimator of the target risk under the empirical risk minimization (ERM) framework.<n>To address negative empirical risk and the associated overfitting problem, we introduce corrected risk estimators based on non-negative and absolute-value corrections.
• Score: 23.692455958661668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Obtaining accurate class labels is often costly or unreliable, and may also be limited by privacy or other practical conditions. Compared with asking an annotator to provide the exact class, it is often easier to ask whether the true label belongs to a certain label subset. This query-response form defines a distinct weak-supervision mechanism: weak supervision information is generated through feedback on a label subset. Although weakly supervised learning has studied many learning frameworks, most existing work starts from established weak label objects. A systematic characterization is still lacking for weakly supervised learning generated directly by such query response observations. This paper proposes a multiclass learn ing framework under random label-subset queries. We model the data-generating distribution of query-response observations and derive an unbiased estimator of the target risk under the empirical risk minimization (ERM) framework. To address negative empirical risk and the associated overfitting problem, we introduce corrected risk estimators based on non-negative and absolute-value corrections. Theoretical analysis establishes a conditional generalization and excess-risk bound for the unbiased estimator, and a bias-and-consistency result for the corrected risk estimator. Experiments under the matched random-query mechanism demonstrate the feasibility of direct query-response learning and the stabilization effect of risk correction.

Related papers

• Large Classification-Risk-Optional Label Acquisition [0.0]
  We study how a limited labeling budget should be allocated to minimize multiclass zero-one classification risk.<n>We develop a two-stage adaptive procedure that attains the oracle leading-risk criterion under regularity conditions.
  arXiv  Detail & Related papers  (2026-09-06T23:31:55Z)
• A Unified and Stable Risk Minimization Framework for Weakly Supervised Learning with Theoretical Guarantees [33.15955234458642]
  Weakly supervised learning has emerged as a practical alternative to fully supervised learning when complete and accurate labels are costly or infeasible to acquire.<n>We propose a principled, unified framework that bypasses such post-hoc adjustments by formulating a stable surrogate risk grounded in the structure of weakly supervised data.
  arXiv  Detail & Related papers  (2025-11-28T00:57:04Z)
• Learning from M-Tuple Dominant Positive and Unlabeled Data [9.568395664931504]
  This paper proposes a generalized learning framework emphMDPU to better align with real-world application scenarios.<n>We derive an unbiased risk estimator that satisfies risk consistency based on the empirical risk minimization (ERM) method.<n>To mitigate the inevitable overfitting issue during training, a risk correction method is introduced, leading to the development of a corrected risk estimator.
  arXiv  Detail & Related papers  (2025-05-25T13:20:11Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• An Unbiased Risk Estimator for Partial Label Learning with Augmented Classes [46.663081214928226]
  We propose an unbiased risk estimator with theoretical guarantees for PLLAC. We provide a theoretical analysis of the estimation error bound of PLLAC. Experiments on benchmark, UCI and real-world datasets demonstrate the effectiveness of the proposed approach.
  arXiv  Detail & Related papers  (2024-09-29T07:36:16Z)
• Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical [66.57396042747706]
  Complementary-label learning is a weakly supervised learning problem. We propose a consistent approach that does not rely on the uniform distribution assumption. We find that complementary-label learning can be expressed as a set of negative-unlabeled binary classification problems.
  arXiv  Detail & Related papers  (2023-11-27T02:59:17Z)
• Can Class-Priors Help Single-Positive Multi-Label Learning? [40.312419865957224]
  Single-positive multi-label learning (SPMLL) is a typical weakly supervised multi-label learning problem. Class-priors estimator is introduced, which could estimate the class-priors that are theoretically guaranteed to converge to the ground-truth class-priors. Based on the estimated class-priors, an unbiased risk estimator for classification is derived, and the corresponding risk minimizer could be guaranteed to approximately converge to the optimal risk minimizer on fully supervised data.
  arXiv  Detail & Related papers  (2023-09-25T05:45:57Z)
• Learning from Multiple Unlabeled Datasets with Partial Risk Regularization [80.54710259664698]
  In this paper, we aim to learn an accurate classifier without any class labels. We first derive an unbiased estimator of the classification risk that can be estimated from the given unlabeled sets. We then find that the classifier obtained as such tends to cause overfitting as its empirical risks go negative during training. Experiments demonstrate that our method effectively mitigates overfitting and outperforms state-of-the-art methods for learning from multiple unlabeled sets.
  arXiv  Detail & Related papers  (2022-07-04T16:22:44Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

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.