Recent advances in weakly supervised learning: New supervision paradigms, assumption relaxations, and practical solutions

# Chapter 10 Recent advances in weakly supervised learning
Source: [https://arxiv.org/html/2608.06896](https://arxiv.org/html/2608.06896)
###### Abstract

Deep learning has achieved great success in recent years thanks to the availability of high\-quality, well\-annotated training data\. However, this requirement is often not met in real\-world applications\. Weakly supervised learning aims to train an accurate model with incomplete, inexact, or inaccurate supervision\. In this chapter, we will discuss recent advances in this field, including new supervision paradigms, relaxed assumptions, and practical solutions\. First, we introduce a new weakly supervised binary classification problem called confidence\-difference classification and propose consistent approaches to solve it\. Next, we investigate complementary\-label learning, a weakly supervised multi\-class classification problem\. Our proposed approaches are based on more relaxed assumptions about the data generation process than existing consistent approaches\. Lastly, we present an evaluation framework for partial\-label learning, another popular multi\-class weakly supervised learning problem, in order to promote fair and realistic evaluation of algorithms in this field\.

\\Mainmatter

\\subchapter

New supervision paradigms, assumption relaxations, and practical solutions

### 1Introduction

In recent years, deep learning has achieved remarkable success in various real\-world applications thanks to its strong generalization capabilities\. However, this success depends heavily on the availability of large\-scale, accurately labeled training data, which is often costly or impractical to obtain in real\-world scenarios\. Weakly supervised learning offers a promising solution, allowing models to be trained with imperfect supervision while maintaining performance comparable to that of fully supervised approaches\(sugiyama2022machine\)\.

Weakly supervised learning \(WSL\) lies at the intersection of supervised and unsupervised learning\. In this chapter, we will focus primarily on weakly supervised classification, which involves constructing a binary or multi\-class classifier that assigns discrete labels to test data using only weakly supervised data\. According to the types of weak supervision, WSL can be roughly categorized into learning with incomplete, inexact, or inaccurate supervision\(zhou2018brief\)\. This chapter introduces several recent advances in weakly supervised learning, including new supervision paradigms, assumption relaxations, and practical solutions\.

Section[3](https://arxiv.org/html/2608.06896#S3)investigates a novel weakly supervised binary classification framework called*confidence\-difference classification*, which weakens the supervision requirements when leveraging soft\-label information\. While soft\-label learning has demonstrated superior performance over hard\-label approaches in various domains\(szegedy2016rethinking;yuan2023learning\), the acquisition of pointwise confidence labels for all training examples remains impractical in real\-world applications\(collins2022eliciting;shinoda2020binary;sucholutsky2023on\)\. To address this limitation, the confidence\-difference paradigm operates on unlabeled data pairs annotated only with relative confidence differences indicating the probability difference of being positive rather than absolute confidence values \(see Figure[1](https://arxiv.org/html/2608.06896#S1.F1)\)\. We introduce unbiased \(see Section[3\.3\.1](https://arxiv.org/html/2608.06896#S3.SS3.SSS1)\) and corrected risk estimators \(see Section[3\.3\.4](https://arxiv.org/html/2608.06896#S3.SS3.SSS4)\) for this problem, which have both consistency guarantees and convergence properties\. In addition, we provide theoretical analysis that quantifies how estimation errors in confidence values and class priors affect the final classifier performance \(see Section[3\.3\.3](https://arxiv.org/html/2608.06896#S3.SS3.SSS3)\)\.

Section[4](https://arxiv.org/html/2608.06896#S4)introduces a novel consistent learning approach for complementary\-label \(CL\) learning which attempts to relax the restrictive assumptions for CL learning\(wang2024learning\)\. CL learning is a multi\-class weakly supervised learning problem where training examples are annotated only with labels to which they do not belong \(see Figure[2](https://arxiv.org/html/2608.06896#S1.F2)\)\(ishida2017learning\)\. While existing consistent methods either require restrictive uniform distribution assumptions\(ishida2019complementary;feng2020learning\)or depend on ordinary\-label data to estimate transition matrices\(yu2018learning\), such conditions often fail in practical settings\(wang2025climage\)\. Our work breaks this dependency by deriving an unbiased risk estimator based on a more practical data generation assumption \(see Section[4\.3\.1](https://arxiv.org/html/2608.06896#S4.SS3.SSS1)\)\. Then, we propose a risk\-correction approach to combat overfitting problems when using deep models \(see Section[4\.3\.3](https://arxiv.org/html/2608.06896#S4.SS3.SSS3)\)\. The consistency and convergence rate of the estimation error are also established\.

Section[5](https://arxiv.org/html/2608.06896#S5)presents the first comprehensive benchmarking framework for the realistic evaluation of partial\-label \(PL\) learning\(wang2025realistic\)\. In PL learning, each training example is associated with multiple candidate labels, one of which is the ground truth \(see Figure[2](https://arxiv.org/html/2608.06896#S1.F2)\)\(cour2011learning;lv2020progressive;feng2020provably\)\. Despite significant algorithmic advances in PL learning in recent years, our analysis reveals critical gaps in current evaluation practices: First, there is an absence of principled model selection methods, despite their substantial impact on performance\(wang2025realistic\)\. Second, there are inconsistent experimental protocols that compromise fair comparisons\. These shortcomings have led to a systematic underestimation of earlier, simpler algorithms relative to more complex, recent approaches\(lv2020progressive;feng2020provably\)\. We address these limitations by providing theoretically grounded model selection criteria designed specifically for PL learning and PLENCH \(PL learning bENCHmark\), a standardized evaluation protocol \(see Section[5\.2](https://arxiv.org/html/2608.06896#S5.SS2)\)\. PLENCH provides a reproducible and fair comparison of PL learning algorithms under realistic conditions and serves as an essential testbed for future research in this field \(see Section[5\.3](https://arxiv.org/html/2608.06896#S5.SS3)\)\. We anticipate that PLENCH will lay the groundwork for the more rigorous development and evaluation of PL learning methods\.

![Refer to caption](https://arxiv.org/html/2608.06896v1/x1.png)Figure 1:Comparison of ordinary binary classification and confidence\-difference classification investigated in Section[3](https://arxiv.org/html/2608.06896#S3)\. In confidence\-difference classification, we are given unlabeled data pairs with confidence difference\. The goal is the same as that in binary classification\. Here, the color of the directional line indicates the value of the confidence difference\.![Refer to caption](https://arxiv.org/html/2608.06896v1/x2.png)Figure 2:Comparison of ordinary multi\-class classification, complementary\-label learning investigated in Section[4](https://arxiv.org/html/2608.06896#S4), and partial\-label learning investigated in Section[5](https://arxiv.org/html/2608.06896#S5)\. Complementary\-label learning and partial\-label learning are two types of weakly supervised, multi\-class classification problems involving inexact supervision\.In summary, this chapter presents several recent advances in weakly supervised learning, including new supervision paradigms \(confidence difference classification\), assumption relaxations \(selected\-completely\-at\-random CL learning\), and practical solutions \(the first PL learning benchmark\)\.

### 2Preliminaries

In this section, we introduce the basic notation and background of binary and multi\-class classification, as well as complementary\-label and partial\-label learning\.

#### 2\.1Notations

Let𝒳=ℝd\\mathcal\{X\}=\\mathbb\{R\}^\{d\}denote thedd\-dimensional feature space and𝒴\\mathcal\{Y\}denote the label space\. For binary classification, we have𝒴=\{\+1,−1\}\\mathcal\{Y\}=\\left\\\{\+1,\-1\\right\\\}\. For multi\-class classification, we have𝒴=\{1,2,…,q\}\\mathcal\{Y\}=\\left\\\{1,2,\\ldots,q\\right\\\}\. Letp​\(𝒙,y\)p\(\\bm\{x\},y\)denote the unknown joint probability density over the random variables\(𝒙,y\)∈𝒳×𝒴\(\\bm\{x\},y\)\\in\\mathcal\{X\}\\times\\mathcal\{Y\}\. An example is denoted by\(𝒙,y\)\(\\bm\{x\},y\)\. Here,𝒙∈𝒳\\bm\{x\}\\in\\mathcal\{X\}denotes an instance that characterizes the properties of this example\. Besides,y∈𝒴y\\in\\mathcal\{Y\}denotes the label of this example, which encodes the corresponding semantic information\. Letp​\(𝒙\)p\(\\bm\{x\}\)denote the marginal density of the instances\. For binary classification, letπ\+=p​\(y=\+1\)\\pi\_\{\+\}=p\(y=\+1\)andπ−=p​\(y=−1\)\\pi\_\{\-\}=p\(y=\-1\)denote the class prior probabilities for the positive and negative classes respectively\. Furthermore, letp\+​\(𝒙\)=p​\(𝒙\|y=\+1\)p\_\{\+\}\(\\bm\{x\}\)=p\(\\bm\{x\}\|y=\+1\)andp−​\(𝒙\)=p​\(𝒙\|y=−1\)p\_\{\-\}\(\\bm\{x\}\)=p\(\\bm\{x\}\|y=\-1\)denote the class\-conditional probability densities of positive and negative data respectively\. For multi\-class classification, we useπk=p​\(y=k\)\\pi\_\{k\}=p\(y=k\)to denote the class prior probability for thekk\-th class\. The goal of binary or multi\-class classification is to learn a mapping from the feature space𝒳\\mathcal\{X\}to the label space𝒴\\mathcal\{Y\}\. For binary classification, letg:𝒳→ℝg:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}denote the binary classifier to learn\. Then, we useℓ​\(g​\(𝒙\),y\)\\ell\\left\(g\(\\bm\{x\}\),y\\right\)to denote a binary loss function that characterizes the differences between the model outputg​\(𝒙\)g\(\\bm\{x\}\)and the ground\-truthyyforxx\. For multi\-class classification, let𝒇:𝒳→ℝq\\bm\{f\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}^\{q\}denote the multi\-class classifier to be learned\. Here,𝒇​\(𝒙\)=\[f1​\(𝒙\),f2​\(𝒙\),…,fq​\(𝒙\)\]\\bm\{f\}\(\\bm\{x\}\)=\\left\[f\_\{1\}\(\\bm\{x\}\),f\_\{2\}\(\\bm\{x\}\),\\ldots,f\_\{q\}\(\\bm\{x\}\)\\right\]is aqq\-dimensional vector which denotes the model output\. We usef:𝒳→𝒴f:\\mathcal\{X\}\\rightarrow\\mathcal\{Y\}to denote the label predicted by the model, which corresponds to the dimension of the maximum model output, i\.e\.,

f​\(𝒙\)=arg⁡maxk∈𝒴fk​\(𝒙\)\.f\(\\bm\{x\}\)=\\mathop\{\\arg\\max\}\_\{k\\in\\mathcal\{Y\}\}\\penalty 10000\\ f\_\{k\}\(\\bm\{x\}\)\.\(1\)Then, we useℒ​\(𝒇​\(𝒙\),y\)\\mathcal\{L\}\\left\(\\bm\{f\}\(\\bm\{x\}\),y\\right\)to denote a multi\-class loss function which characterizes the difference between the model output𝒇​\(𝒙\)\\bm\{f\}\(\\bm\{x\}\)and the ground\-truth labelyyforxx\.

#### 2\.2Ordinary Binary Classification

In ordinary binary \(OB\) classification, our goal is to learn a binary classifierg​\(𝒙\)g\(\\bm\{x\}\)which minimizes the following test error for binary classification:

R0−1OB​\(g\)=𝔼p​\(𝒙,y\)​𝕀​\(y​g​\(𝒙\)<0\),R\_\{0\\mathrm\{\-\}1\}^\{\\rm OB\}\(g\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\\mathbb\{I\}\(yg\(\\bm\{x\}\)<0\),\(2\)where𝕀\\mathbb\{I\}is an indicator function that returns11if the predicate holds; otherwise it returns0\. However, the 0\-1 loss function is non\-smooth and difficult to optimize\. Therefore, we replace the 0\-1 loss function with a classification\-calibrated loss functionℓ\\ell, and the classification risk for binary classification is defined as

ROB​\(g\)=𝔼p​\(𝒙,y\)​\[ℓ​\(g​\(𝒙\),y\)\]\.R^\{\\rm OB\}\(g\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\[\\ell\\left\(g\(\\bm\{x\}\),y\\right\)\]\.\(3\)For binary classification, a margin lossℓM\\ell^\{\\mathrm\{M\}\}is often adopted to instantiate the loss function, such as the logistic loss\. The classification risk can also be expressed as

ROB​\(g\)=𝔼p​\(𝒙,y\)​\[ℓM​\(y​g​\(𝒙\)\)\]\.R^\{\\rm OB\}\(g\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\[\\ell^\{\\mathrm\{M\}\}\\left\(yg\(\\bm\{x\}\)\\right\)\]\.\(4\)
We cannot compute the expectation in Eq\. \([3](https://arxiv.org/html/2608.06896#S2.E3)\) directly\. To cope with this problem, we typically assume that we are given a training set i\.i\.d\. sampled fromp​\(𝒙,y\)p\\left\(\\bm\{x\},y\\right\):

𝒟OB=\{\(𝒙iOB,yiOB\)\}i=1nOB∼i\.i\.d\.p​\(𝒙,y\)\.\\mathcal\{D\}^\{\\mathrm\{OB\}\}=\\left\\\{\\left\(\\bm\{x\}^\{\\mathrm\{OB\}\}\_\{i\},y^\{\\mathrm\{OB\}\}\_\{i\}\\right\)\\right\\\}\_\{i=1\}^\{n^\{\\mathrm\{OB\}\}\}\\stackrel\{\{\\scriptstyle\\text\{ i\.i\.d\. \}\}\}\{\{\\sim\}\}p\\left\(\\bm\{x\},y\\right\)\.\(5\)Then, we conduct*empirical risk minimization*by minimizing the following empirical risk:

R^OB​\(g\)=1nOB​∑i=1nOBℓ​\(g​\(𝒙iOB\),yiOB\)\.\\widehat\{R\}^\{\\mathrm\{OB\}\}\(g\)=\\frac\{1\}\{n^\{\\mathrm\{OB\}\}\}\\sum\\nolimits\_\{i=1\}^\{n^\{\\mathrm\{OB\}\}\}\\ell\\left\(g\\left\(\\bm\{x\}^\{\\mathrm\{OB\}\}\_\{i\}\\right\),y^\{\\mathrm\{OB\}\}\_\{i\}\\right\)\.\(6\)

#### 2\.3Ordinary Multi\-Class Classification

In ordinary multi\-class \(OM\) classification, our goal is to learn a multi\-class classifierf​\(𝒙\)f\(\\bm\{x\}\)which minimizes the following test error for multi\-class classification:

R0−1OM​\(f\)=𝔼p​\(𝒙,y\)​𝕀​\(f​\(𝒙\)≠y\)\.R\_\{0\\mathrm\{\-\}1\}^\{\\rm OM\}\(f\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\\mathbb\{I\}\(f\(\\bm\{x\}\)\\neq y\)\.\(7\)Similar to binary classification, we replace the 0\-1 loss function with a classification\-calibrated loss functionℒ\\mathcal\{L\}, and the classification risk for multi\-class classification is defined as

ROM​\(g\)=𝔼p​\(𝒙,y\)​\[ℒ​\(f​\(𝒙\),y\)\]\.R^\{\\rm OM\}\(g\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\[\\mathcal\{L\}\\left\(f\(\\bm\{x\}\),y\\right\)\]\.\(8\)We cannot compute the expectation in Eq\. \([8](https://arxiv.org/html/2608.06896#S2.E8)\) directly\. To cope with this problem, we typically assume that we are given a training set i\.i\.d\. sampled fromp​\(𝒙,y\)p\\left\(\\bm\{x\},y\\right\):

𝒟OM=\{\(𝒙iOM,yiOM\)\}i=1nOM∼i\.i\.d\.p​\(𝒙,y\)\.\\mathcal\{D\}^\{\\mathrm\{OM\}\}=\\left\\\{\\left\(\\bm\{x\}^\{\\mathrm\{OM\}\}\_\{i\},y^\{\\mathrm\{OM\}\}\_\{i\}\\right\)\\right\\\}\_\{i=1\}^\{n^\{\\mathrm\{OM\}\}\}\\stackrel\{\{\\scriptstyle\\text\{ i\.i\.d\. \}\}\}\{\{\\sim\}\}p\\left\(\\bm\{x\},y\\right\)\.\(9\)Then, we conduct*empirical risk minimization*by minimizing the following empirical risk for multi\-class classification:

R^OM​\(g\)=1nOM​∑i=1nOMℒ​\(f​\(𝒙iOM\),yiOM\)\.\\widehat\{R\}^\{\\mathrm\{OM\}\}\(g\)=\\frac\{1\}\{n^\{\\mathrm\{OM\}\}\}\\sum\\nolimits\_\{i=1\}^\{n^\{\\mathrm\{OM\}\}\}\\mathcal\{L\}\\left\(f\\left\(\\bm\{x\}^\{\\mathrm\{OM\}\}\_\{i\}\\right\),y^\{\\mathrm\{OM\}\}\_\{i\}\\right\)\.\(10\)

#### 2\.4Complementary\-Label Learning

In CL learning, each training example is associated with one or multiple complementary labels specifying the classes to which the example does not belong\. Let𝒟CL=\{\(𝒙iCL,Y¯iCL\)\}i=1nCL\\mathcal\{D\}^\{\\mathrm\{CL\}\}=\\left\\\{\\left\(\\bm\{x\}^\{\\mathrm\{CL\}\}\_\{i\},\\bar\{Y\}^\{\\mathrm\{CL\}\}\_\{i\}\\right\)\\right\\\}\_\{i=1\}^\{n^\{\\mathrm\{CL\}\}\}denote a CL training set sampled i\.i\.d\. from an unknown densityp​\(𝒙,Y¯\)p\(\\bm\{x\},\\bar\{Y\}\)\. Here,𝒙∈𝒳\\bm\{x\}\\in\\mathcal\{X\}is a feature vector, andY¯⊆𝒴\\bar\{Y\}\\subseteq\\mathcal\{Y\}is a CL set associated with𝒙\\bm\{x\}\. In the literature, CL learning can be categorized into single CL learning when we haveY¯=\{y¯\}\\bar\{Y\}=\\left\\\{\\bar\{y\}\\right\\\}and\|Y¯\|=1\|\\bar\{Y\}\|=1\(ishida2017learning;gao2021discriminative;liu2023consistent\), and multiple CL learning when we have1≤\|Y¯\|≤q−11\\leq\|\\bar\{Y\}\|\\leq q\-1\(feng2020learning\)\. The task of CL learning is to learn a multi\-class classifierf:𝒳→𝒴f:\\mathcal\{X\}\\rightarrow\\mathcal\{Y\}from𝒟CL\\mathcal\{D\}^\{\\mathrm\{CL\}\}\.

#### 2\.5Partial\-Label Learning

Let\(𝒙,S\)\\left\(\\bm\{x\},S\\right\)denote a PL example where𝒙∈𝒳\\bm\{x\}\\in\\mathcal\{X\}is a feature vector andS⊆𝒴S\\subseteq\\mathcal\{Y\}is a candidate label set associated with𝒙\\bm\{x\}\. The basic assumption of PLL is that the ground\-truth labelyyof𝒙\\bm\{x\}is concealed within its candidate label setSS, i\.e\.,y∈Sy\\in S\. The task of PLL is to learn a multi\-class classifierfffrom a PL training set𝒟Tr=\{\(𝒙iTr,SiTr\)\}i=1nTr\\mathcal\{D\}^\{\\rm Tr\}=\\\{\\left\(\\bm\{x\}^\{\\rm Tr\}\_\{i\},S^\{\\rm Tr\}\_\{i\}\\right\)\\\}\_\{i=1\}^\{n^\{\\rm Tr\}\}\.

### 3ConfDiff Classification

Recently, learning with*soft labels*has been shown to achieve better performance than learning with*hard labels*in terms of model generalization, calibration, and robustness\. However, collecting pointwise labeling confidence for all training examples can be challenging and time\-consuming in real\-world scenarios\. This section delves into a novel weakly supervised binary classification problem called*confidence\-difference \(ConfDiff\) classification*\(wang2023binary\)\. Instead of pointwise labeling confidence, we are given only unlabeled data pairs with confidence difference that specifies the difference in the probabilities of being positive\. We propose a risk\-consistent approach to tackle this problem and show that the estimation error bound achieves the optimal convergence rate\. We also introduce a risk\-correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven\.

#### 3\.1Motivation

Learning with soft labels has been shown to achieve better performance than learning with hard labels in the context of supervised learning\(yuan2023learning\), where each example is equipped with*pointwise labeling confidence*indicating the degree to which the labels describe the example\. The advantages have been validated in many aspects, including model generalization\(yuan2020revisiting;ishida2023is\), calibration\(muller2019does;wang2021rethinking\), and robustness\(lukasik2020does;pang2020bag\)\. For example, with the help of soft labels, knowledge distillation\(yuan2020revisiting;hinton2015distilling\)transfers knowledge from a large teacher network to a small student network\. The student network can be trained more efficiently and reliably with the soft labels generated by the teacher network\(phuong2019towards;park2019relational;gou2021knowledge\)\.

However, collecting a large number of training examples with pointwise labeling confidence may be demanding under many circumstances since it is challenging to describe the labeling confidence for each training example exactly\(collins2022eliciting;shinoda2020binary;sucholutsky2023on\)\. Different annotators may give different values of pointwise labeling confidence to the same example due to personal biases, and it has been demonstrated that skewed confidence values can harm classification performance\(shinoda2020binary\)\. Besides, giving pointwise labeling information to large\-scale datasets is also expensive, laborious, and even unrealistic in many real\-world scenarios\(wei2022learning;karimi2020deep;ratner2016data\)\. On the contrary, leveraging supervision information of pairwise comparisons may ameliorate the biases of skewed pointwise labeling confidence and save labeling costs\. Following this idea, we investigate a more practical problem setting for binary classification in this section, where we are given*unlabeled data pairs with confidence difference*indicating the difference in the probabilities of being positive\. Collecting confidence difference for training examples in pairs is much cheaper and more accessible than collecting pointwise labeling confidence for all the training examples\.

Take click\-through rate prediction in recommender systems\(zhang2019deep;jiang2022adaptive\)for example\. The combinations of users and their favorite/disliked items can be regarded as positive/negative data\. Collecting training data takes work to distinguish between positive and negative data\. Furthermore, the pointwise labeling confidence of training data may be difficult to be determined due to the extraordinarily sparse and class\-imbalance problems\(yao2021self\)\. Therefore, the collected confidence values may be biased\. However, collecting the difference in the preference between a pair of candidate items for a given user is more accessible and may alleviate the biases\. Inwang2023binary, we provided an experiment on recommender systems to illustrate it\.

Take the disease risk estimation problem for another example\. Given a person’s attributes, the goal is to predict the risk of having some disease\. When asking doctors to annotate the probabilities of having the disease for patients, it takes work to determine the exact values of the probabilities\. Furthermore, the probability values given by different doctors may differ due to their diverse backgrounds\. On the other hand, it is much easier and less biased to estimate the relative difference in the probabilities of having the disease between two patients\. Therefore, the problem of learning with confidence difference is of practical research value, but has yet to be investigated in the literature\.

#### 3\.2Problem Definition

In this subsection, the formal definition of confidence difference is given firstly\. Then, we elaborate the data generation process of ConfDiff data\.

###### Definition 1\(Confidence Difference\)\.

The confidence differencec​\(𝒙,𝒙′\)c\\left\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\\right\)between an unlabeled data pair\(𝒙,𝒙′\)\\left\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\\right\)is defined as

c​\(𝒙,𝒙′\)=p​\(y′=\+1\|𝒙′\)−p​\(y=\+1\|𝒙\)\.c\\left\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\\right\)=p\\left\(y^\{\\prime\}=\+1\|\\bm\{x\}^\{\\prime\}\\right\)\-p\\left\(y=\+1\|\\bm\{x\}\\right\)\.\(11\)

As shown in the definition above, the confidence difference denotes the difference in the class posterior probabilities between the unlabeled data pair, which can measure how confident the pairwise comparison is\. In ConfDiff classification, we are only givennnunlabeled data pairs with confidence difference𝒟CD=\{\(\(𝒙iCD,𝒙iCD′\),ci\)\}i=1n\\mathcal\{D\}^\{\\mathrm\{CD\}\}=\\left\\\{\\left\(\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\),c\_\{i\}\\right\)\\right\\\}\_\{i=1\}^\{n\}\. Here,ci=c​\(𝒙iCD,𝒙iCD′\)c\_\{i\}=c\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\)is the confidence difference for the unlabeled data pair\(𝒙iCD,𝒙iCD′\)\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\)\. Furthermore, the unlabeled data pair\(𝒙iCD,𝒙iCD′\)\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\)is assumed to be drawn from a probability densityp​\(𝒙,𝒙′\)=p​\(𝒙\)​p​\(𝒙′\)p\\left\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\\right\)=p\\left\(\\bm\{x\}\\right\)p\\left\(\\bm\{x\}^\{\\prime\}\\right\)\. This indicates that𝒙iCD\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}and𝒙iCD′\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}are two i\.i\.d\. instances sampled fromp​\(𝒙\)p\(\\bm\{x\}\)\. It is worth noting that the confidence differencecic\_\{i\}will be positive if the second instance𝒙iCD′\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}has a higher probability to be positive than the first instance𝒙iCD\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}, and will be negative otherwise\. During the data collection process, the labeler can first sample two unlabeled data independently from the marginal distributionp​\(𝒙\)p\(\\bm\{x\}\), then provide the confidence difference for them\.

#### 3\.3Methodology

In this section, we introduce our proposed approaches with theoretical guarantees\. Besides, we show the influence of an inaccurate class prior probability and noisy confidence difference theoretically\. Furthermore, we introduce a risk\-correction approach to improve the generalization performance\. Due to page limitations, detailed proofs of theorems and lemmas, as well as experimental results, can be found inwang2023binary\.

##### 3\.3\.1Unbiased Risk Estimator

In this subsection, we show that the classification risk in Eq\. \([3](https://arxiv.org/html/2608.06896#S2.E3)\) can be expressed with ConfDiff data in an equivalent way\. We rewrite the classification risk as the expectation w\.r\.t\. the densities of unlabeled data pairs of a loss function containing confidence difference\. The detailed proof can be found inwang2023binary\.

###### Theorem 1\.

The classification risk in Eq\. \([3](https://arxiv.org/html/2608.06896#S2.E3)\) can be equivalently expressed as

RCD​\(g\)=𝔼p​\(𝒙,𝒙′\)​\[12​\(ℒCD​\(𝒙,𝒙′\)\+ℒCD​\(𝒙′,𝒙\)\)\],R\_\{\\rm CD\}\(g\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\)\}\\left\[\\frac\{1\}\{2\}\\left\(\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\)\+\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\(\\bm\{x\}^\{\\prime\},\\bm\{x\}\)\\right\)\\right\],\(12\)where

ℒCD​\(𝒙,𝒙′\)=\(π\+−c​\(𝒙,𝒙′\)\)​ℓ​\(g​\(𝒙\),\+1\)\+\(π−−c​\(𝒙,𝒙′\)\)​ℓ​\(g​\(𝒙′\),−1\)\.\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\)=\\left\(\\pi\_\{\+\}\-c\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\)\\right\)\\ell\\left\(g\(\\bm\{x\}\),\+1\\right\)\+\(\\pi\_\{\-\}\-c\\left\(\\bm\{x\},\\bm\{x\}^\{\\prime\}\)\\right\)\\ell\\left\(g\(\\bm\{x\}^\{\\prime\}\),\-1\\right\)\.

Accordingly, we can derive an unbiased risk estimator for ConfDiff classification:

R^CD​\(g\)=12​n​∑i=1n\(ℒCD​\(𝒙iCD,𝒙iCD′\)\+ℒCD​\(𝒙iCD′,𝒙iCD\)\)\.\\displaystyle\\widehat\{R\}\_\{\\rm CD\}\(g\)=\\frac\{1\}\{2n\}\\sum\\nolimits\_\{i=1\}^\{n\}\\left\(\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\)\+\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}\\right\)\\right\)\.\(13\)
Actually, Eq\. \([13](https://arxiv.org/html/2608.06896#S3.E13)\) is one of the candidates of the unbiased risk estimator\. We introduce the following lemma:

###### Lemma 1\.

The following expression is also an unbiased risk estimator:

1n​∑i=1n\(α​ℒCD​\(𝒙iCD,𝒙iCD′\)\+\(1−α\)​ℒCD​\(𝒙iCD′,𝒙iCD\)\),\\frac\{1\}\{n\}\\sum\\nolimits\_\{i=1\}^\{n\}\\left\(\\alpha\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\)\+\(1\-\\alpha\)\\mathcal\{L\}\_\{\\mathrm\{CD\}\}\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}\\right\)\\right\),\(14\)whereα∈\[0,1\]\\alpha\\in\[0,1\]is an arbitrary weight\.

Then, we introduce the following theorem:

###### Theorem 2\.

The unbiased risk estimator in Eq\. \([13](https://arxiv.org/html/2608.06896#S3.E13)\) has the minimum variance among all the candidate unbiased risk estimators in the form of Eq\. \([14](https://arxiv.org/html/2608.06896#S3.E14)\) w\.r\.t\.α∈\[0,1\]\\alpha\\in\[0,1\]\.

Theorem[2](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem2)indicates the variance minimality of the proposed unbiased risk estimator in Eq\. \([13](https://arxiv.org/html/2608.06896#S3.E13)\), and we adopt this risk estimator in the following sections\.

##### 3\.3\.2Estimation Error Bound

In this subsection, we elaborate the convergence property of the proposed risk estimatorR^CD​\(g\)\\widehat\{R\}\_\{\\rm CD\}\(g\)by giving an estimation error bound\. Let𝒢=\{g:𝒳↦ℝ\}\\mathcal\{G\}=\\left\\\{g:\\mathcal\{X\}\\mapsto\\mathbb\{R\}\\right\\\}denote the model class\. It is assumed that there exists some constantC𝒢C\_\{\\mathcal\{G\}\}such thatsupg∈𝒢‖g‖∞≤C𝒢\\sup\_\{g\\in\\mathcal\{G\}\}\\\|g\\\|\_\{\\infty\}\\leq C\_\{\\mathcal\{G\}\}and some constantCℓC\_\{\\ell\}such thatsup\|z\|≤C𝒢ℓ​\(z,y\)≤Cℓ\\sup\_\{\|z\|\\leq C\_\{\\mathcal\{G\}\}\}\\ell\(z,y\)\\leq C\_\{\\ell\}\. We also assume that the binary loss functionℓ​\(z,y\)\\ell\(z,y\)is Lipschitz continuous forzzwith a Lipschitz constantLℓL\_\{\\ell\}\. Letg∗=arg⁡ming∈𝒢RB​\(g\)g^\{\*\}=\\mathop\{\\arg\\min\}\_\{g\\in\\mathcal\{G\}\}R^\{\\mathrm\{B\}\}\(g\)denote the minimizer of the classification risk in Eq\. \([3](https://arxiv.org/html/2608.06896#S2.E3)\) andg^CD=arg⁡ming∈𝒢R^CD​\(g\)\\widehat\{g\}\_\{\\rm CD\}=\\mathop\{\\arg\\min\}\_\{g\\in\\mathcal\{G\}\}\\widehat\{R\}\_\{\\rm CD\}\(g\)denote the minimizer of the unbiased risk estimator in Eq\. \([13](https://arxiv.org/html/2608.06896#S3.E13)\)\. The following theorem can be derived:

###### Theorem 3\.

For anyδ\>0\\delta\>0, the following inequality holds with probability at least1−δ1\-\\delta:

RB​\(g^CD\)−RB​\(g∗\)≤8​Lℓ​ℜn​\(𝒢\)\+4​Cℓ​ln⁡2/δ2​n,R^\{\\mathrm\{B\}\}\\left\(\\widehat\{g\}\_\{\\rm CD\}\\right\)\-R^\{\\mathrm\{B\}\}\\left\(g^\{\*\}\\right\)\\leq 8L\_\{\\ell\}\\mathfrak\{R\}\_\{n\}\(\\mathcal\{G\}\)\+4C\_\{\\ell\}\\sqrt\{\\frac\{\\ln 2/\\delta\}\{2n\}\},\(15\)whereℜn​\(𝒢\)\\mathfrak\{R\}\_\{n\}\\left\(\\mathcal\{G\}\\right\)denotes the Rademacher complexity of𝒢\\mathcal\{G\}for unlabeled data with sizenn\.

From Theorem[3](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem3), we can observe that asn→∞n\\rightarrow\\infty,RB​\(g^CD\)→RB​\(g∗\)R^\{\\mathrm\{B\}\}\\left\(\\widehat\{g\}\_\{\\rm CD\}\\right\)\\rightarrow R^\{\\mathrm\{B\}\}\\left\(g^\{\*\}\\right\)becauseℛn​\(𝒢\)→0\\mathcal\{R\}\_\{n\}\\left\(\\mathcal\{G\}\\right\)\\rightarrow 0for all parametric models with a bounded norm, such as deep neural networks trained with weight decay\(golowich2018size\)\. Furthermore, the estimation error bound converges in𝒪p​\(1/n\)\\mathcal\{O\}\_\{p\}\\left\(1/\\sqrt\{n\}\\right\), where𝒪p\\mathcal\{O\}\_\{p\}denotes the order in probability, which is the optimal parametric rate for empirical risk minimization without making additional assumptions\(mendelson2008lower\)\.

##### 3\.3\.3Robustness of Risk Estimator

In the previous subsections, it was assumed that the class prior probability is known in advance\. In addition, it was assumed that the ground\-truth confidence difference of each unlabeled data pair is accessible\. However, these assumptions can rarely be satisfied in real\-world scenarios, since the collection of confidence difference is inevitably injected with noise\. In this subsection, we theoretically analyze the influence of an inaccurate class prior probability and noisy confidence difference on the learning procedure\.

Let𝒟¯CD=\{\(\(𝒙iCD,𝒙iCD′\),c¯i\)\}i=1n\\bar\{\\mathcal\{D\}\}^\{\\mathrm\{CD\}\}=\\left\\\{\(\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\},\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\),\\bar\{c\}\_\{i\}\)\\right\\\}\_\{i=1\}^\{n\}denotennunlabeled data pairs with noisy confidence difference, wherec¯i\\bar\{c\}\_\{i\}is generated by corrupting the ground\-truth confidence differencecic\_\{i\}with noise\. Besides, letπ¯\+\\bar\{\\pi\}\_\{\+\}denote the inaccurate class prior probability accessible to the learning algorithm\. Furthermore, letR¯CD​\(g\)\\bar\{R\}\_\{\\rm CD\}\(g\)denote the empirical risk calculated based on the inaccurate class prior probability and noisy confidence difference\. Letg¯CD=arg⁡ming∈𝒢R¯CD​\(g\)\\bar\{g\}\_\{\\rm CD\}=\\mathop\{\\arg\\min\}\_\{g\\in\\mathcal\{G\}\}\\bar\{R\}\_\{\\rm CD\}\(g\)denote the minimizer ofR¯CD​\(g\)\\bar\{R\}\_\{\\rm CD\}\(g\)\. Then the following theorem gives an estimation error bound:

###### Theorem 4\.

Based on the assumptions of Theorem[3](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem3), for anyδ\>0\\delta\>0, the following inequality holds with probability at least1−δ1\-\\delta:

RB​\(g¯CD\)−RB​\(g∗\)≤\\displaystyle R^\{\\mathrm\{B\}\}\\left\(\\bar\{g\}\_\{\\rm CD\}\\right\)\-R^\{\\mathrm\{B\}\}\\left\(g^\{\*\}\\right\)\\leq16​Lℓ​ℜn​\(𝒢\)\+8​Cℓ​ln⁡2/δ2​n\\displaystyle 16L\_\{\\ell\}\\mathfrak\{R\}\_\{n\}\\left\(\\mathcal\{G\}\\right\)\+8C\_\{\\ell\}\\sqrt\{\\frac\{\\ln\{2/\\delta\}\}\{2n\}\}\+4​Cℓ​∑i=1n\|c¯i−ci\|n\+4​Cℓ​\|π¯\+−π\+\|\.\\displaystyle\+\\frac\{4C\_\{\\ell\}\\sum\\nolimits\_\{i=1\}^\{n\}\\left\|\\bar\{c\}\_\{i\}\-c\_\{i\}\\right\|\}\{n\}\+4C\_\{\\ell\}\\left\|\\bar\{\\pi\}\_\{\+\}\-\\pi\_\{\+\}\\right\|\.\(16\)

Theorem[4](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem4)indicates that the estimation error is bounded by twice the original bound in Theorem[3](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem3)with the mean absolute error of the noisy confidence difference and the inaccurate class prior probability\. Furthermore, if∑i=1n\|c¯i−ci\|\\sum\\nolimits\_\{i=1\}^\{n\}\\left\|\\bar\{c\}\_\{i\}\-c\_\{i\}\\right\|has a sublinear growth rate with high probability and the class prior probability is estimated consistently, the risk estimator can be even consistent\. This elaborates the robustness of the proposed approach\.

##### 3\.3\.4Risk\-Correction Approach

It is worth noting that the empirical risk in Eq\. \([13](https://arxiv.org/html/2608.06896#S3.E13)\) may be negative due to negative terms, which is unreasonable because of the non\-negative property of loss functions\. This phenomenon will result in severe overfitting problems when complex models are adopted\(lu2020mitigating;cao2021learning;feng2021pointwise\)\. To circumvent this difficulty, we wrap the individual loss terms in Eq\. \([13](https://arxiv.org/html/2608.06896#S3.E13)\) with*risk\-correction functions*proposed inlu2020mitigating, such as the rectified linear unit \(ReLU\) functionh​\(z\)=max⁡\(0,z\)h\(z\)=\\max\(0,z\)and the absolute value functionh​\(z\)=\|z\|h\(z\)=\|z\|\. In this way, the corrected risk estimator for ConfDiff classification can be expressed as follows:

R~CD​\(g\)=\\displaystyle\\widetilde\{R\}\_\{\\rm CD\}\(g\)=12​n​h​\(∑i=1n\(π\+−ci\)​ℓ​\(g​\(𝒙iCD\),\+1\)\)\\displaystyle\\frac\{1\}\{2n\}h\\left\(\\sum\\nolimits\_\{i=1\}^\{n\}\\left\(\\pi\_\{\+\}\-c\_\{i\}\\right\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}\\right\),\+1\\right\)\\right\)\+12​n​h​\(∑i=1n\(π−−ci\)​ℓ​\(g​\(𝒙iCD′\),−1\)\)\\displaystyle\+\\frac\{1\}\{2n\}h\\left\(\\sum\\nolimits\_\{i=1\}^\{n\}\\left\(\\pi\_\{\-\}\-c\_\{i\}\\right\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\),\-1\\right\)\\right\)\+12​n​h​\(∑i=1n\(π\+\+ci\)​ℓ​\(g​\(𝒙iCD′\),\+1\)\)\\displaystyle\+\\frac\{1\}\{2n\}h\\left\(\\sum\\nolimits\_\{i=1\}^\{n\}\\left\(\\pi\_\{\+\}\+c\_\{i\}\\right\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\),\+1\\right\)\\right\)\+12​n​h​\(∑i=1n\(π−\+ci\)​ℓ​\(g​\(𝒙iCD\),−1\)\)\.\\displaystyle\+\\frac\{1\}\{2n\}h\\left\(\\sum\\nolimits\_\{i=1\}^\{n\}\\left\(\\pi\_\{\-\}\+c\_\{i\}\\right\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}\\right\),\-1\\right\)\\right\)\.\(17\)
We assume that the risk\-correction functionh​\(z\)h\(z\)is Lipschitz continuous with Lipschitz constantLhL\_\{h\}\. For ease of notation, we introduce

A^​\(g\)\\displaystyle\\widehat\{A\}\(\{g\}\)=12​n​∑i=1n\(π\+−ci\)​ℓ​\(g​\(𝒙iCD\),\+1\),\\displaystyle=\\frac\{1\}\{2n\}\\sum\\nolimits\_\{i=1\}^\{n\}\(\\pi\_\{\+\}\-c\_\{i\}\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}\\right\),\+1\\right\),B^​\(g\)\\displaystyle\\widehat\{B\}\(\{g\}\)=12​n​∑i=1n\(π−−ci\)​ℓ​\(g​\(𝒙iCD′\),−1\),\\displaystyle=\\frac\{1\}\{2n\}\\sum\\nolimits\_\{i=1\}^\{n\}\(\\pi\_\{\-\}\-c\_\{i\}\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\),\-1\\right\),C^​\(g\)\\displaystyle\\widehat\{C\}\(\{g\}\)=12​n​∑i=1n\(π\+\+ci\)​ℓ​\(g​\(𝒙iCD′\),\+1\),\\displaystyle=\\frac\{1\}\{2n\}\\sum\\nolimits\_\{i=1\}^\{n\}\(\\pi\_\{\+\}\+c\_\{i\}\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}^\{\\prime\}\}\\right\),\+1\\right\),D^​\(g\)\\displaystyle\\widehat\{D\}\(\{g\}\)=12​n​∑i=1n\(π−\+ci\)​ℓ​\(g​\(𝒙iCD\),−1\)\.\\displaystyle=\\frac\{1\}\{2n\}\\sum\\nolimits\_\{i=1\}^\{n\}\(\\pi\_\{\-\}\+c\_\{i\}\)\\ell\\left\(g\\left\(\\bm\{x\}\_\{i\}^\{\\mathrm\{CD\}\}\\right\),\-1\\right\)\.\(18\)We assume that there exist positive constantsa,b,c,a,b,c,andddsuch that𝔼​\[A^​\(g\)\]≥a,𝔼​\[B^​\(g\)\]≥b,𝔼​\[C^​\(g\)\]≥c,\\mathbb\{E\}\\left\[\\widehat\{A\}\(\{g\}\)\\right\]\\geq a,\\mathbb\{E\}\\left\[\\widehat\{B\}\(\{g\}\)\\right\]\\geq b,\\mathbb\{E\}\\left\[\\widehat\{C\}\(\{g\}\)\\right\]\\geq c,and𝔼​\[D^​\(g\)\]≥d\\mathbb\{E\}\\left\[\\widehat\{D\}\(\{g\}\)\\right\]\\geq d\. Besides, letg~CD=arg⁡ming∈𝒢R~CD​\(g\)\\widetilde\{g\}\_\{\\rm CD\}=\\mathop\{\\arg\\min\}\_\{g\\in\\mathcal\{G\}\}\\widetilde\{R\}\_\{\\rm CD\}\(g\)denote the minimizer ofR~CD​\(g\)\\widetilde\{R\}\_\{\\rm CD\}\(g\)\. Then, Theorem[5](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem5)is provided to elaborate the bias and consistency ofR~CD​\(g\)\\widetilde\{R\}\_\{\\rm CD\}\(g\)\.

###### Theorem 5\.

Based on the assumptions of Theorem[3](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem3), the bias of the risk estimatorR~CD​\(g\)\\widetilde\{R\}\_\{\\rm CD\}\(g\)decays exponentially asn→∞n\\rightarrow\\infty:

0≤𝔼​\[R~CD​\(g\)\]−RB​\(g\)≤2​\(Lh\+1\)​Cℓ​Δ,0\\leq\\mathbb\{E\}\\left\[\\widetilde\{R\}\_\{\\rm CD\}\(g\)\\right\]\-R^\{\\mathrm\{B\}\}\(g\)\\leq 2\\left\(L\_\{h\}\+1\\right\)C\_\{\\ell\}\\Delta,\(19\)whereΔ=exp⁡\(−2​a2​n/Cℓ2\)\+exp⁡\(−2​b2​n/Cℓ2\)\+exp⁡\(−2​c2​n/Cℓ2\)\+exp⁡\(−2​d2​n/Cℓ2\)\\Delta=\\exp\{\\left\(\-2a^\{2\}n/C\_\{\\ell\}^\{2\}\\right\)\}\+\\exp\{\\left\(\-2b^\{2\}n/C\_\{\\ell\}^\{2\}\\right\)\}\+\\exp\{\\left\(\-2c^\{2\}n/C\_\{\\ell\}^\{2\}\\right\)\}\+\\exp\{\\left\(\-2d^\{2\}n/C\_\{\\ell\}^\{2\}\\right\)\}\. Furthermore, with probability at least1−δ1\-\\delta, we have

\|R~CD​\(g\)−RB​\(g\)\|≤2​Cℓ​Lh​ln⁡2/δ2​n\+2​\(Lh\+1\)​Cℓ​Δ\.\|\\widetilde\{R\}\_\{\\rm CD\}\(g\)\-R^\{\\mathrm\{B\}\}\(g\)\|\\leq 2C\_\{\\ell\}L\_\{h\}\\sqrt\{\\frac\{\\ln\{2/\\delta\}\}\{2n\}\}\+2\\left\(L\_\{h\}\+1\\right\)C\_\{\\ell\}\\Delta\.\(20\)

Theorem[5](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem5)demonstrates thatR~CD​\(g\)→RB​\(g\)\\widetilde\{R\}\_\{\\rm CD\}\(g\)\\rightarrow R^\{\\mathrm\{B\}\}\(g\)in𝒪p​\(1/n\)\\mathcal\{O\}\_\{p\}\(1/\\sqrt\{n\}\), which means thatR~CD​\(g\)\\widetilde\{R\}\_\{\\rm CD\}\(g\)is biased yet consistent\. The estimation error bound ofg~CD\\widetilde\{g\}\_\{\\rm CD\}is analyzed in Theorem[6](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem6)\.

###### Theorem 6\.

Based on the assumptions of Theorem[5](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem5), for anyδ\>0\\delta\>0, the following inequality holds with probability at least1−δ1\-\\delta:

RB​\(g~CD\)−RB​\(g∗\)≤8​Lℓ​ℜn​\(𝒢\)\+4​Cℓ​\(Lh\+1\)​ln⁡2/δ2​n\+4​\(Lh\+1\)​Cℓ​Δ\.R^\{\\mathrm\{B\}\}\\left\(\\widetilde\{g\}\_\{\\rm CD\}\\right\)\-R^\{\\mathrm\{B\}\}\\left\(g^\{\*\}\\right\)\\leq 8L\_\{\\ell\}\\mathfrak\{R\}\_\{n\}\(\\mathcal\{G\}\)\+4C\_\{\\ell\}\(L\_\{h\}\+1\)\\sqrt\{\\frac\{\\ln\{2/\\delta\}\}\{2n\}\}\+4\(L\_\{h\}\+1\)C\_\{\\ell\}\\Delta\.\(21\)

Theorem[6](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem6)elucidates that asn→∞n\\rightarrow\\infty,RB​\(g~CD\)→RB​\(g∗\)R^\{\\mathrm\{B\}\}\(\\widetilde\{g\}\_\{\\rm CD\}\)\\rightarrow R^\{\\mathrm\{B\}\}\(g^\{\*\}\), sinceℛn​\(𝒢\)→0\\mathcal\{R\}\_\{n\}\(\\mathcal\{G\}\)\\rightarrow 0for all parametric models with a bounded norm\(mohri2012foundations\)andΔ→0\\Delta\\rightarrow 0\. Furthermore, the estimation error bound converges in𝒪p​\(1/n\)\\mathcal\{O\}\_\{p\}\(1/\\sqrt\{n\}\), which is the optimal parametric rate for empirical risk minimization without additional assumptions\(mendelson2008lower\)\.

### 4Selected\-Completely\-at\-Random Complementary\-Label Learning

CL learning is a weakly supervised learning problem in which each training example is associated with one or multiple complementary labels indicating the classes to which it does not belong\. Existing consistent approaches have relied on the uniform distribution assumption to model the generation of complementary labels, or on an ordinary\-label training set to estimate the transition matrix in non\-uniform cases\. However, either condition may not be satisfied in real\-world scenarios\. In this section, we propose a novel consistent approach that does not rely on these conditions\. Inspired by the positive\-unlabeled \(PU\) learning literature, we propose an*unbiased risk estimator*based on the*Selected\-Completely\-at\-Random \(SCAR\) assumption*for CL learning\. We then introduce a*risk\-correction approach*to address overfitting problems\.

#### 4\.1Motivation

CL learning is a weakly supervised learning problem that has received a lot of attention recently\(ishida2017learning;feng2020learning;gao2021discriminative;liu2023consistent\)\. In CL learning, we are given training data associated with complementary labels that specify the classes to which the examples do not belong\. The task is to learn a multi\-class classifier that assigns correct labels to test data as in the standard supervised learning\. Collecting training data with complementary labels is much easier and cheaper than collecting ordinary\-label data\. For example, when asking workers on crowdsourcing platforms to annotate training data, we only need to randomly select a candidate label and then ask them whether the example belongs to that class or not\. Such “yes” or “no” questions are much easier to answer than asking workers to determine the ground\-truth label from a large set of candidate labels\. The benefits and effectiveness of CL learning have also been demonstrated in several machine learning problems and applications, such as domain adaptation\(zhang2021learning;han2023rethinking\), semi\-supervised learning\(chen2020negative;ma2023rethinking;deng2024boosting\), noisy\-label learning\(kim2019nlnl\), adversarial robustness\(zhou2022adversarial\), few\-shot learning\(wei2022an\), and medical image analysis\(rezaei2020recurrent\)\.

Existing research works with*consistency guarantees*have attempted to solve CL learning problems by making assumptions about the distribution of complementary labels\. The remedy started withishida2017learning, which proposed the*uniform distribution assumption*that a label other than the ground\-truth label is sampled from the uniform distribution to be the complementary label\. A subsequent work extended it to arbitrary loss functions and models\(ishida2019complementary\)based on the same distribution assumption\. Then,feng2020learningextended the problem setting to the existence of multiple complementary labels\. Recent works have proposed discriminative methods that work by modeling the posterior probabilities of complementary labels instead of the generation process\(chou2020unbiased;gao2021discriminative;liu2023consistent;lin2023reduction\)\. However, the uniform distribution assumption is still necessary to ensure the classifier consistency property\(liu2023consistent\)\.yu2018learningproposed the*biased distribution assumption*, elaborating that the generation of complementary labels follows a*transition matrix*, i\.e\., the CL distribution is determined by the true label\.

In summary, previous CL learning approaches all require either the uniform distribution assumption or the biased distribution assumption to guarantee the consistency property, to the best of our knowledge\. However, such assumptions may not be satisfied in real\-world scenarios\. On the one hand, the uniform distribution assumption is too strong, since the transition probability for different complementary labels is undifferentiated, i\.e\., the transition probability from the true label to a complementary label is constant for all labels\. Such an assumption is not realistic since the annotations may be imbalanced and biased\(wei2023class;wang2025climage\)\. On the other hand, although the biased distribution assumption is more practical, an ordinary\-label training set with*deterministic labels*, also known as*anchor points*\(liu2015classification\), is essential for estimating transition probabilities during the training phase\(yu2018learning\)\. However, the collection of ordinary\-label data with deterministic labels is often unrealistic in CL learning problems\(feng2020learning;gao2021discriminative\)\. Therefore, we are motivated to propose consistent methods that do not rely on previous strong assumptions\.

#### 4\.2Data Generation Process

Inspired by the SCAR assumption in PU learning\(elkan2008learning;coudray2023risk\), we introduce the SCAR assumption for generating complementary labels, which can be summarized as follows\.

###### Assumption 1\(Selected\-Completely\-at\-Random Assumption\)\.

The CL data with thekk\-th class as a complementary label are sampled completely at random from the marginal density of the data not belonging to thekk\-th class, i\.e\.,

p​\(k∈Y¯\|𝒙,k∈𝒴\\\{y\}\)=p​\(k∈Y¯\|k∈𝒴\\\{y\}\)=ck,\\displaystyle p\\left\(k\\in\\bar\{Y\}\|\\bm\{x\},k\\in\{\\mathcal\{Y\}\\backslash\\\{y\\\}\}\\right\)=p\\left\(k\\in\\bar\{Y\}\|k\\in\{\\mathcal\{Y\}\\backslash\\\{y\\\}\}\\right\)=c\_\{k\},\(22\)whereck=π¯k/\(1−πk\)c\_\{k\}=\\bar\{\\pi\}\_\{k\}/\(1\-\\pi\_\{k\}\)is a constant specifying the fraction of data with thekk\-th class as a complementary label and\(𝒙,y\)\(\\bm\{x\},y\)is sampled from the densityp​\(𝒙,y\)p\(\\bm\{x\},y\)\.

Our motivation is that complementary labels are often generated in a*class\-wise*manner\. They can be collected by answering “yes” or “no” questions given a pair of an example and a candidate label\(hu2019active;wang2021learning\)\. During an annotation round, we randomly select a candidate label and ask the annotators whether the example belongs to that class or not\. The process is repeated iteratively, so that each example may be annotated with*multiple*complementary labels\. The SCAR assumption differs from the biased distribution assumption, where only one*single*complementary label is generated by sampling only once from a multinomial distribution\. Moreover, the SCAR assumption can be generalized to non\-uniform cases by settingckc\_\{k\}to different values for different labels\. Therefore, our assumption is more practical in real\-world scenarios\.

#### 4\.3Methodology

In this section, we propose an unbiased risk estimator with the OVR strategy, followed by its theoretical analysis\. Finally, we present a risk\-correction approach to improve the generalization performance\. Due to page limitations, detailed proofs of theorems and lemmas, as well as experimental results, can be found inwang2024learning\.

##### 4\.3\.1OVR Strategy

The OVR strategy decomposes multi\-class classification into a series of binary classification problems, which is a common strategy with extensive theoretical guarantees and sound performance\(rifkin2004defense;zhang2004statistical\)\. Specifically, when considering a given class, examples that belong to the given class can be considered positive, while examples that do not belong to the given class can be considered negative\. This naturally creates multiple binary classification problems\. The OVR strategy instantiates the loss functionℒ\\mathcal\{L\}in Eq\. \([8](https://arxiv.org/html/2608.06896#S2.E8)\) with the OVR loss, i\.e\.

R​\(f1,f2,…,fq\)=𝔼p​\(𝒙,y\)​\[ℓM​\(fy​\(𝒙\)\)\+∑k∈𝒴\\\{y\}ℓM​\(−fk​\(𝒙\)\)\]\.R\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\\left\[\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{y\}\\left\(\\bm\{x\}\\right\)\\right\)\+\\sum\_\{k\\in\{\\mathcal\{Y\}\\backslash\\\{y\\\}\}\}\\ell^\{\\mathrm\{M\}\}\\left\(\-f\_\{k\}\\left\(\\bm\{x\}\\right\)\\right\)\\right\]\.\(23\)
Here,fkf\_\{k\}is a binary classifier w\.r\.t\. thekk\-th class,𝔼\\mathbb\{E\}denotes the expectation, andℓM:ℝ→ℝ\+\\ell^\{\\mathrm\{M\}\}:\\mathbb\{R\}\\rightarrow\\mathbb\{R\}\_\{\+\}is a non\-negative binary\-class loss function\. Then, the predicted label for a test instance𝒙\\bm\{x\}is determined as

f​\(𝒙\)=arg⁡maxk∈𝒴fk​\(𝒙\)\.f\(\\bm\{x\}\)=\\mathop\{\\arg\\max\}\_\{k\\in\\mathcal\{Y\}\}\\penalty 10000\\ f\_\{k\}\(\\bm\{x\}\)\.\(24\)
The goal is to find optimal classifiersf1∗,f2∗,…,fq∗f\_\{1\}^\{\*\},f\_\{2\}^\{\*\},\\ldots,f\_\{q\}^\{\*\}in a function classℱ\\mathcal\{F\}which achieve the minimum classification risk in Eq\. \([23](https://arxiv.org/html/2608.06896#S4.E23)\), i\.e\.,

\(f1∗,f2∗,…,fq∗\)=arg⁡minf1,f2,…,fq∈ℱR​\(f1,f2,…,fq\)\.\\left\(f\_\{1\}^\{\*\},f\_\{2\}^\{\*\},\\ldots,f\_\{q\}^\{\*\}\\right\)=\\mathop\{\\arg\\min\}\_\{f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\in\\mathcal\{F\}\}\\penalty 10000\\ R\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)\.\(25\)We show that the OVR risk can be rewritten using densitiesp​\(𝒙\|y¯k=1\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=1\\right\)andp​\(𝒙\|y¯k=0\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=0\\right\)as well\.

###### Theorem 7\.

When the OVR loss is used, the classification risk in Eq\. \([23](https://arxiv.org/html/2608.06896#S4.E23)\) can be equivalently expressed asR​\(f1,f2,…,fq\)=∑k=1qRk​\(fk\)R\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)=\\sum\_\{k=1\}^\{q\}R\_\{k\}\(f\_\{k\}\), where

Rk​\(fk\)=\\displaystyle R\_\{k\}\(f\_\{k\}\)=𝔼p​\(𝒙\|y¯k=1\)\[\(1−πk\)ℓM\(−fk\(𝒙\)\)\+\(π¯k\+πk−1\)\\displaystyle\\mathbb\{E\}\_\{p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=1\\right\)\}\\left\[\(1\-\\pi\_\{k\}\)\\ell^\{\\mathrm\{M\}\}\\left\(\-f\_\{k\}\(\\bm\{x\}\)\\right\)\+\\left\(\\bar\{\\pi\}\_\{k\}\+\\pi\_\{k\}\-1\\right\)\\right\.ℓM\(fk\(𝒙\)\)\]\+𝔼p​\(𝒙\|y¯k=0\)\[\(1−π¯k\)ℓM\(fk\(𝒙\)\)\]\.\\displaystyle\\left\.\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\)\\right\)\\right\]\+\\mathbb\{E\}\_\{p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=0\\right\)\}\\left\[\\left\(1\-\\bar\{\\pi\}\_\{k\}\\right\)\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\)\\right\)\\right\]\.\(26\)

Since the true densitiesp​\(𝒙\|y¯k=1\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=1\\right\)andp​\(𝒙\|y¯k=0\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=0\\right\)are not directly accessible, we approximate the risk*empirically*\. Suppose we have binary\-class datasets𝒟kN\\mathcal\{D\}^\{\\rm N\}\_\{k\}and𝒟kU\\mathcal\{D\}^\{\\rm U\}\_\{k\}sampled i\.i\.d\. fromp​\(𝒙\|y¯k=1\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=1\\right\)andp​\(𝒙\|y¯k=0\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=0\\right\), respectively\. Then, an unbiased risk estimator can be derived from these binary\-class datasets to approximate the classification risk in Theorem[7](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem7)asR^​\(f1,f2,…,fq\)=∑k=1qR^k​\(fk\)\\widehat\{R\}\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)=\\sum\_\{k=1\}^\{q\}\\widehat\{R\}\_\{k\}\(f\_\{k\}\), where

R^k​\(fk\)=\\displaystyle\\widehat\{R\}\_\{k\}\(f\_\{k\}\)=1nkN∑i=1nkN\(\(1−πk\)ℓM\(−fk\(𝒙k,iN\)\)\+\(π¯k\+πk−1\)\\displaystyle\\frac\{1\}\{n^\{\\rm N\}\_\{k\}\}\\sum\_\{i=1\}^\{n^\{\\rm N\}\_\{k\}\}\\left\(\\left\(1\-\\pi\_\{k\}\\right\)\\ell^\{\\mathrm\{M\}\}\\left\(\-f\_\{k\}\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{N\}\}\)\\right\)\+\\left\(\\bar\{\\pi\}\_\{k\}\+\\pi\_\{k\}\-1\\right\)\\right\.ℓM\(fk\(𝒙k,iN\)\)\)\+\(1−π¯k\)nkU∑i=1nkUℓM\(fk\(𝒙k,iU\)\)\.\\displaystyle\\left\.\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{N\}\}\)\\right\)\\right\)\+\\frac\{\(1\-\\bar\{\\pi\}\_\{k\}\)\}\{n^\{\\rm U\}\_\{k\}\}\\sum\_\{i=1\}^\{n^\{\\rm U\}\_\{k\}\}\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{U\}\}\)\\right\)\.\(27\)We may add regularization terms toR^​\(f1,f2,…,fq\)\\widehat\{R\}\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)when necessary\(loshchilov2019decoupled\)\. This section considers generating the binary\-class datasets𝒟kN\\mathcal\{D\}^\{\\rm N\}\_\{k\}and𝒟kU\\mathcal\{D\}^\{\\rm U\}\_\{k\}by*duplicating*instances of𝒟CL\\mathcal\{D\}^\{\\mathrm\{CL\}\}\. Specifically, if thekk\-th class is a complementary label of a training example, we regard its duplicated instance as a*negative example*sampled fromp​\(𝒙\|y¯k=1\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=1\\right\)and put the duplicated instance in𝒟kN\\mathcal\{D\}^\{\\rm N\}\_\{k\}\. If thekk\-th class is not a complementary label of a training example, we regard its duplicated instance as an*unlabeled example*sampled fromp​\(𝒙\|y¯k=0\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=0\\right\)and put the duplicated instance in𝒟kU\\mathcal\{D\}^\{\\rm U\}\_\{k\}\. In this way, we can obtainqqnegative binary\-class datasets andqqunlabeled binary\-class datasets \(k∈𝒴k\\in\\mathcal\{Y\}\):

𝒟kN\\displaystyle\\mathcal\{D\}^\{\\rm N\}\_\{k\}=\{\(𝒙k,iN,−1\)\}i=1nkN=\{\(𝒙j,−1\)\|\(𝒙j,Y¯j\)∈𝒟CL,k∈Y¯j\};\\displaystyle=\\left\\\{\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{N\}\},\-1\)\\right\\\}\_\{i=1\}^\{n^\{\\rm N\}\_\{k\}\}=\\left\\\{\(\\bm\{x\}\_\{j\},\-1\)\|\(\\bm\{x\}\_\{j\},\\bar\{Y\}\_\{j\}\)\\in\\mathcal\{D\}^\{\\mathrm\{CL\}\},k\\in\\bar\{Y\}\_\{j\}\\right\\\};\(28\)𝒟kU\\displaystyle\\mathcal\{D\}^\{\\rm U\}\_\{k\}=\{𝒙k,iU\}i=1nkU=\{𝒙j\|\(𝒙j,Y¯j\)∈𝒟CL,k∉Y¯j\}\.\\displaystyle=\\left\\\{\\bm\{x\}\_\{k,i\}^\{\\mathrm\{U\}\}\\right\\\}\_\{i=1\}^\{n^\{\\rm U\}\_\{k\}\}=\\left\\\{\\bm\{x\}\_\{j\}\|\(\\bm\{x\}\_\{j\},\\bar\{Y\}\_\{j\}\)\\in\\mathcal\{D\}^\{\\mathrm\{CL\}\},k\\notin\\bar\{Y\}\_\{j\}\\right\\\}\.\(29\)When the class priorsπk\\pi\_\{k\}are not accessible to the learning algorithm, they can be estimated by off\-the\-shelf mixture proportion estimation approaches\(scott2015rate;ramaswamy2016mixture;zhang2020unbiased;garg2021mixture;yao2022rethinking\)with𝒟kN\\mathcal\{D\}^\{\\rm N\}\_\{k\}and𝒟kU\\mathcal\{D\}^\{\\rm U\}\_\{k\}\. Notably, the*irreducibility*\(blanchard2010semi;scott2013classification\)assumption is necessary for class\-prior estimation\. However, it is still less demanding than the biased distribution assumption, which requires additional ordinary\-label training data with deterministic labels, a\.k\.a\. anchor points, to estimate the transition matrix\(yu2018learning\)\.

##### 4\.3\.2Theoretical Analysis

In this section, we present theoretical analysis of the proposed method\.

We show that the proposed risk can be calibrated to the 0\-1 loss\(zhang2004statistical\)\. LetR0−1​\(f\)=𝔼p​\(𝒙,y\)​𝕀​\(f​\(𝒙\)≠y\)R\_\{\\mathrm\{0\-1\}\}\(f\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\\mathbb\{I\}\(f\(\\bm\{x\}\)\\neq y\)denote the expected 0\-1 loss wheref​\(𝒙\)=arg⁡maxk∈𝒴fk​\(𝒙\)f\(\\bm\{x\}\)=\\mathop\{\\arg\\max\}\_\{k\\in\\mathcal\{Y\}\}\\penalty 10000\\ f\_\{k\}\(\\bm\{x\}\)andR0−1∗=minfR0−1​\(f\)R\_\{\\mathrm\{0\-1\}\}^\{\*\}=\\mathop\{\\min\}\_\{f\}\\penalty 10000\\ R\_\{\\mathrm\{0\-1\}\}\(f\)denote the Bayes error\. Besides, letR∗=minf1,f2,…,fqR​\(f1,f2,…,fq\)R^\{\*\}=\\mathop\{\\min\}\_\{f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\}\\penalty 10000\\ R\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)denote the minimum risk of the proposed risk\. Then we have the following theorem\.

###### Theorem 8\.

Suppose the binary\-class loss functionℓM\\ell^\{\\mathrm\{M\}\}is convex, bounded below, differential, and satisfiesℓM​\(z\)≤ℓM​\(−z\)\\ell^\{\\mathrm\{M\}\}\(z\)\\leq\\ell^\{\\mathrm\{M\}\}\(\-z\)whenz\>0z\>0\. Then we have that for anyϵ1\>0\\epsilon\_\{1\}\>0, there exists anϵ2\>0\\epsilon\_\{2\}\>0such that

R​\(f1,f2,…,fq\)≤R∗\+ϵ2⇒R0−1​\(f\)≤R0−1∗\+ϵ1\.R\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)\\leq R^\{\*\}\+\\epsilon\_\{2\}\\Rightarrow R\_\{\\mathrm\{0\-1\}\}\(f\)\\leq R\_\{\\mathrm\{0\-1\}\}^\{\*\}\+\\epsilon\_\{1\}\.\(30\)

The infinite\-sample consistency elucidates that the proposed risk can be calibrated to the 0\-1 loss\. Therefore, if we minimize the proposed risk and obtain the optimal classifier, the classifier also achieves the Bayes error\.

We further elaborate the convergence property of the empirical risk estimatorR^​\(f1,f2,…,fq\)\\widehat\{R\}\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)by providing its estimation error bound\. The optimal classifiers w\.r\.t\.R^​\(f1,f2,…,fq\)\\widehat\{R\}\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)are

\(f^1,f^2,…,f^q\)=arg⁡minf1,f2,…,fq∈ℱR^​\(f1,f2,…,fq\)\.\\left\(\\widehat\{f\}\_\{1\},\\widehat\{f\}\_\{2\},\\ldots,\\widehat\{f\}\_\{q\}\\right\)=\\mathop\{\\arg\\min\}\_\{f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\in\\mathcal\{F\}\}\\penalty 10000\\ \\widehat\{R\}\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)\.\(31\)We assume that there exists some constantCℱC\_\{\\mathcal\{F\}\}such thatsupfk∈ℱ‖fk‖∞≤Cℱ\\sup\_\{f\_\{k\}\\in\\mathcal\{F\}\}\\\|f\_\{k\}\\\|\_\{\\infty\}\\leq C\_\{\\mathcal\{F\}\}and some constantCℓMC\_\{\\ell^\{\\mathrm\{M\}\}\}such thatsup\|z\|≤CℱℓM​\(z\)≤CℓM\\sup\_\{\|z\|\\leq C\_\{\\mathcal\{F\}\}\}\\ell^\{\\mathrm\{M\}\}\(z\)\\leq C\_\{\\ell^\{\\mathrm\{M\}\}\}\. We also assume that the binary\-class loss functionℓM​\(z\)\\ell^\{\\mathrm\{M\}\}\(z\)is Lipschitz continuous w\.r\.t\.zzwith a Lipschitz constantLℓML\_\{\\ell^\{\\mathrm\{M\}\}\}\.

###### Theorem 9\.

Based on the above assumptions, for anyδ\>0\\delta\>0, the following inequality holds with probability at least1−δ1\-\\delta:

R​\(f^1,f^2,…,f^q\)−R​\(f1∗,f2∗,…,fq∗\)≤\\displaystyle R\\left\(\\widehat\{f\}\_\{1\},\\widehat\{f\}\_\{2\},\\ldots,\\widehat\{f\}\_\{q\}\\right\)\-R\\left\(f\_\{1\}^\{\*\},f\_\{2\}^\{\*\},\\ldots,f\_\{q\}^\{\*\}\\right\)\\leq∑k=1q\(\(4−4π¯k\)LℓMℜnkU,pkU\(ℱ\)\+\(1−π¯k\)CℓM2​ln⁡\(2/δ\)nkU\\displaystyle\\sum\_\{k=1\}^\{q\}\\left\(\(4\-4\\bar\{\\pi\}\_\{k\}\)L\_\{\\ell^\{\\mathrm\{M\}\}\}\\mathfrak\{R\}\_\{n^\{\\rm U\}\_\{k\},p^\{\\rm U\}\_\{k\}\}\(\\mathcal\{F\}\)\+\(1\-\\bar\{\\pi\}\_\{k\}\)C\_\{\\ell^\{\\mathrm\{M\}\}\}\\sqrt\{\\frac\{2\\ln\{\\left\(2/\\delta\\right\)\}\}\{n^\{\\rm U\}\_\{k\}\}\}\\right\.\+\(8−8πk−4π¯k\)LℓMℜnkN,pkN\(ℱ\)\+\(2−2πk−π¯k\)CℓM2​ln⁡\(2/δ\)nkN\),\\displaystyle\\left\.\+\(8\-8\\pi\_\{k\}\-4\\bar\{\\pi\}\_\{k\}\)L\_\{\\ell^\{\\mathrm\{M\}\}\}\\mathfrak\{R\}\_\{n^\{\\rm N\}\_\{k\},p^\{\\rm N\}\_\{k\}\}\(\\mathcal\{F\}\)\+\(2\-2\\pi\_\{k\}\-\\bar\{\\pi\}\_\{k\}\)C\_\{\\ell^\{\\mathrm\{M\}\}\}\\sqrt\{\\frac\{2\\ln\{\\left\(2/\\delta\\right\)\}\}\{n^\{\\rm N\}\_\{k\}\}\}\\right\),\(32\)whereℜnkU,pkU​\(ℱ\)\\mathfrak\{R\}\_\{n^\{\\rm U\}\_\{k\},p^\{\\rm U\}\_\{k\}\}\(\\mathcal\{F\}\)andℜnkN,pkN​\(ℱ\)\\mathfrak\{R\}\_\{n^\{\\rm N\}\_\{k\},p^\{\\rm N\}\_\{k\}\}\(\\mathcal\{F\}\)denote the Rademacher complexity ofℱ\\mathcal\{F\}givennkUn^\{\\rm U\}\_\{k\}unlabeled data sampled fromp​\(𝐱\|y¯k=0\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=0\\right\)andnkNn^\{\\rm N\}\_\{k\}negative data sampled fromp​\(𝐱\|y¯k=1\)p\\left\(\\bm\{x\}\|\\bar\{y\}\_\{k\}=1\\right\)respectively\.

Theorem[9](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem9)elucidates an estimation error bound of our proposed risk estimator\. WhennkUn^\{\\rm U\}\_\{k\}andnkN→∞n^\{\\rm N\}\_\{k\}\\rightarrow\\infty,R​\(f^1,f^2,…,f^q\)→R​\(f1∗,f2∗,…,fq∗\)R\\left\(\\widehat\{f\}\_\{1\},\\widehat\{f\}\_\{2\},\\ldots,\\widehat\{f\}\_\{q\}\\right\)\\rightarrow R\\left\(f\_\{1\}^\{\*\},f\_\{2\}^\{\*\},\\ldots,f\_\{q\}^\{\*\}\\right\)becauseℜnkU,pkU​\(ℱ\)→0\\mathfrak\{R\}\_\{n^\{\\rm U\}\_\{k\},p^\{\\rm U\}\_\{k\}\}\(\\mathcal\{F\}\)\\rightarrow 0andℜnkN,pkN​\(ℱ\)→0\\mathfrak\{R\}\_\{n^\{\\rm N\}\_\{k\},p^\{\\rm N\}\_\{k\}\}\(\\mathcal\{F\}\)\\rightarrow 0for all parametric models with a bounded norm such as deep neural networks with weight decay\(golowich2018size\)\.

##### 4\.3\.3Risk\-Correction Approach

Although the unbiased risk estimator \(URE\) has sound theoretical properties, we have found that it can encounter several overfitting problems when using complex models such as deep neural networks\(kiryo2017positive;lu2020mitigating;cao2021learning\)\. Therefore, followinglu2020mitigating;wang2023binary, we wrap each potentially negative term with a*non\-negative risk\-correction function*g​\(z\)g\(z\), such as the absolute value functiong​\(z\)=\|z\|g\(z\)=\|z\|\. For ease of notation, we introduce

R^kP​\(fk\)=π¯k\+πk−1nkN​∑i=1nkNℓM​\(fk​\(𝒙k,iN\)\)\+1−π¯knkU​∑i=1nkUℓM​\(fk​\(𝒙k,iU\)\)\.\\widehat\{R\}^\{\\rm P\}\_\{k\}\(f\_\{k\}\)=\\frac\{\\bar\{\\pi\}\_\{k\}\+\\pi\_\{k\}\-1\}\{n^\{\\rm N\}\_\{k\}\}\\sum\_\{i=1\}^\{n^\{\\rm N\}\_\{k\}\}\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{N\}\}\)\\right\)\+\\frac\{1\-\\bar\{\\pi\}\_\{k\}\}\{n^\{\\rm U\}\_\{k\}\}\\sum\_\{i=1\}^\{n^\{\\rm U\}\_\{k\}\}\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{U\}\}\)\\right\)\.\(33\)Then, the corrected risk estimator can be written asR~​\(f1,f2,…,fq\)=∑k=1qR~k​\(fk\)\\widetilde\{R\}\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)=\\sum\_\{k=1\}^\{q\}\\widetilde\{R\}\_\{k\}\(f\_\{k\}\), where

R~k​\(fk\)=g​\(R^kP​\(fk\)\)\+1−πknkN​∑i=1nkNℓM​\(−fk​\(𝒙k,iN\)\)\.\\widetilde\{R\}\_\{k\}\(f\_\{k\}\)=g\\left\(\\widehat\{R\}^\{\\rm P\}\_\{k\}\(f\_\{k\}\)\\right\)\+\\frac\{1\-\\pi\_\{k\}\}\{n^\{\\rm N\}\_\{k\}\}\\sum\_\{i=1\}^\{n^\{\\rm N\}\_\{k\}\}\\ell^\{\\mathrm\{M\}\}\\left\(\-f\_\{k\}\(\\bm\{x\}\_\{k,i\}^\{\\mathrm\{N\}\}\)\\right\)\.\(34\)It is obvious that Eq\. \([34](https://arxiv.org/html/2608.06896#S4.E34)\) is an upper bound of Eq\. \([4\.3\.1](https://arxiv.org/html/2608.06896#S4.Ex10)\), so the bias is always present\. Next, we perform a theoretical analysis to clarify that the corrected risk estimator is*biased but consistent*\. Since𝔼​\[R^kP​\(fk\)\]=πk​𝔼p​\(𝒙\|y=k\)​ℓM​\(fk​\(𝒙\)\)\\mathbb\{E\}\\left\[\\widehat\{R\}^\{\\rm P\}\_\{k\}\(f\_\{k\}\)\\right\]=\\pi\_\{k\}\\mathbb\{E\}\_\{p\(\\bm\{x\}\|y=k\)\}\\ell^\{\\mathrm\{M\}\}\\left\(f\_\{k\}\(\\bm\{x\}\)\\right\), we assume that there exists a*positive constant*β\\betasuch that for∀k∈𝒴,𝔼​\[R^kP​\(fk\)\]≥β\\forall k\\in\\mathcal\{Y\},\\mathbb\{E\}\\left\[\\widehat\{R\}^\{\\rm P\}\_\{k\}\(f\_\{k\}\)\\right\]\\geq\\beta\. We also assume that the risk\-correction functiong​\(z\)g\(z\)is Lipschitz continuous with a Lipschitz constantLgL\_\{g\}\. Besides, we assume that there exists some constantCℜC\_\{\\mathfrak\{R\}\}such that the Rademacher complexityℜn,p​\(ℱ\)\\mathfrak\{R\}\_\{n,p\}\(\\mathcal\{F\}\)for unlabeled \(withn=nkU,p=pkUn=n^\{\\rm U\}\_\{k\},p=p^\{\\rm U\}\_\{k\}\) and negative data \(withn=nkN,p=pkNn=n^\{\\rm N\}\_\{k\},p=p^\{\\rm N\}\_\{k\}\) satisfiesℜn,p​\(ℱ\)≤Cℜ/n\\mathfrak\{R\}\_\{n,p\}\(\\mathcal\{F\}\)\\leq C\_\{\\mathfrak\{R\}\}/\\sqrt\{n\}\. This assumption holds for many models, such as fully connected neural networks and linear\-in\-parameter models with a bounded norm\(golowich2018size;lu2020mitigating\)\. We introduce\(f~1,f~2,…,f~q\)=arg⁡minf1,f2,…,fq∈ℱR~​\(f1,f2,…,fq\)\\left\(\\widetilde\{f\}\_\{1\},\\widetilde\{f\}\_\{2\},\\ldots,\\widetilde\{f\}\_\{q\}\\right\)=\\mathop\{\\arg\\min\}\_\{f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\in\\mathcal\{F\}\}\\penalty 10000\\ \\widetilde\{R\}\\left\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\\right\)andΔk=exp⁡\(−2​β2/\(\(1−πk−π¯k\)2​CℓM2/nkN\+\(1−π¯k\)2​CℓM2/nkU\)\)\\Delta\_\{k\}=\\exp\{\\left\(\-2\\beta^\{2\}/\\left\(\(1\-\\pi\_\{k\}\-\\bar\{\\pi\}\_\{k\}\)^\{2\}C\_\{\\ell^\{\\mathrm\{M\}\}\}^\{2\}/n^\{\\rm N\}\_\{k\}\+\(1\-\\bar\{\\pi\}\_\{k\}\)^\{2\}C\_\{\\ell^\{\\mathrm\{M\}\}\}^\{2\}/n^\{\\rm U\}\_\{k\}\\right\)\\right\)\}\. Then we have the following theorems\.

###### Theorem 10\.

Based on the above assumptions, the bias of the expectation of the corrected risk estimator has the following lower and upper bounds:

0\\displaystyle 0≤𝔼​\[R~​\(f1,f2,…,fq\)\]−R​\(f1,f2,…,fq\)\\displaystyle\\leq\\mathbb\{E\}\[\\widetilde\{R\}\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)\]\-R\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)≤∑k=1q\(2−2​π¯k−πk\)​\(Lg\+1\)​CℓM​Δk\.\\displaystyle\\leq\\sum\_\{k=1\}^\{q\}\\left\(2\-2\\bar\{\\pi\}\_\{k\}\-\\pi\_\{k\}\\right\)\\left\(L\_\{g\}\+1\\right\)C\_\{\\ell^\{\\mathrm\{M\}\}\}\\Delta\_\{k\}\.\(35\)Furthermore, for anyδ\>0\\delta\>0, the following inequality holds with probability at least1−δ1\-\\delta:

\|R~​\(f1,f2,…,fq\)−R​\(f1,f2,…,fq\)\|\\displaystyle\|\\widetilde\{R\}\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)\-R\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)\|≤𝒪p​\(∑k=1q\(1/nkN\+1/nkU\)\)\.\\displaystyle\\leq\\mathcal\{O\}\_\{p\}\\left\(\\sum\_\{k=1\}^\{q\}\\left\(1/\\sqrt\{n^\{\\rm N\}\_\{k\}\}\+1/\\sqrt\{n^\{\\rm U\}\_\{k\}\}\\right\)\\right\)\.\(36\)

###### Theorem 11\.

Based on the above assumptions, for anyδ\>0\\delta\>0, the following inequality holds with probability at least1−δ1\-\\delta:

R​\(f~1,f~2,…,f~q\)−R​\(f1∗,f2∗,…,fq∗\)\\displaystyle R\(\\widetilde\{f\}\_\{1\},\\widetilde\{f\}\_\{2\},\\ldots,\\widetilde\{f\}\_\{q\}\)\-R\(f\_\{1\}^\{\*\},f\_\{2\}^\{\*\},\\ldots,f\_\{q\}^\{\*\}\)≤𝒪p​\(∑k=1q\(1/nkN\+1/nkU\)\)\.\\displaystyle\\leq\\mathcal\{O\}\_\{p\}\\left\(\\sum\_\{k=1\}^\{q\}\\left\(1/\\sqrt\{n^\{\\rm N\}\_\{k\}\}\+1/\\sqrt\{n^\{\\rm U\}\_\{k\}\}\\right\)\\right\)\.\(37\)

Theorem[10](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem10)shows thatR~​\(f1,f2,…,fq\)→R​\(f1,f2,…,fq\)\\widetilde\{R\}\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)\\rightarrow R\(f\_\{1\},f\_\{2\},\\ldots,f\_\{q\}\)asnkUn^\{\\rm U\}\_\{k\}andnkN→∞n^\{\\rm N\}\_\{k\}\\rightarrow\\infty, indicating that the corrected risk estimator is biased but consistent\. An estimation error bound is also shown in Theorem[11](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem11)\. The convergence rate of the estimation error bound is still the same after employing the risk\-correction function\.

### 5Realistic Evaluation of Deep Partial\-Label Learning Algorithms

PL learning is a weakly supervised learning problem in which each example is associated with multiple candidate labels and only one is the true label\. In recent years, many deep PL learning algorithms have been developed to improve model performance\. However, we find that some early developed algorithms are often underestimated and can outperform many later algorithms with complicated designs\. In this section, we delve into the empirical perspective of PL learning and identify several critical but previously overlooked issues\. First, model selection for PL learning is non\-trivial, but has never been systematically studied\. Second, the experimental settings are highly inconsistent, making it difficult to evaluate the effectiveness of the algorithms\. Based on these findings, we proposePlench, the first PL learning bENCHmark to systematically compare state\-of\-the\-art deep PL learning algorithms\. We investigate the model selection problem for PL learning for the first time, and propose novel model selection criteria with theoretical guarantees\. Researchers can quickly and conveniently perform a comprehensive and fair evaluation and verify the effectiveness of newly developed algorithms based onPlench\. We hope thatPlenchwill facilitate standardized, fair, and practical evaluation of PL learning algorithms in the future\.

#### 5\.1Motivation

PL learning is a weakly supervised learning problem that has attracted much attention recently\(sugiyama2022machine;wang2022adaptive;tian2023partial\)\. In PL learning, each training example is associated with multiple candidate labels\(jin2002learning;cour2011learning\)\. The true label for each example is hidden in the set of candidate labels, but not accessible to the learning algorithm\. PL learning has been successfully applied to computer vision\(liu2012conditional;zeng2013learning;chen2018learning;gong2018regularization;tang2023disambiguated;wang2024learning\), natural language processing\(garrette2013learning;zhou2018weakly;ren2016afet;ren2016label\), web mining\(luo2010learning\), ecoinformatics\(briggs2012rank;wang2019partial;li2021detecting;lyu2022self\), etc\.

Among various strategies to address this problem, deep learning\-based PL learning algorithms have demonstrated satisfactory generalization performance due to the strong representation learning capabilities of deep neural networks\(lv2020progressive;wang2022pico\)\. Despite the abundance of algorithms in this area, we find that there are several fundamental and critical issues that have received less attention in the PL learning literature\. First, most PL learning algorithms select their hyperparameters by using a clean ordinary\-label validation set\(qiao2023decompositional;xu2023alim;xu2023progressive\)\. However, the original definition of PL learning does not allow the existence of an ordinary\-label dataset\(jin2002learning;cour2011learning;zhang2017disambiguation\), indicating a mismatch between the problem definitions and experimental settings in the literature\. This problem can even lead to*unfair comparisons*if some algorithms follow the classical protocol of PL learning to prohibit the use of ordinary\-label data, while some algorithms do not\. Moreover,*if we have a clean ordinary\-label dataset, why not use it for training?*In many cases, the use of clean labels is more valuable for weakly supervised learning than for ordinary supervised learning\(hendrycks2018using;yu2023delving\)\.

Second, we have found that the experimental settings used in different papers are often quite different, creating a dilemma when comparing the performance of different algorithms\. Such an obstacle can hinder objective comparisons of different algorithms, making it difficult to determine the effectiveness of a developed technique\. These problems therefore motivate us to propose a unified evaluation framework for PL learning\.

#### 5\.2Model Selection for PL Learning

We follow the original definition of PL learning to have only a single PL training set\(cour2011learning;zhang2017disambiguation\)\. Then, following a widely used validation procedure in machine learning\(raschka2018model;gulrajani2021in\), we divide a PL validation set𝒟Val=\{\(𝒙iVal,SiVal\)\}i=1nVal\\mathcal\{D\}^\{\\rm Val\}=\\\{\\left\(\\bm\{x\}^\{\\rm Val\}\_\{i\},S^\{\\rm Val\}\_\{i\}\\right\)\\\}\_\{i=1\}^\{n^\{\\rm Val\}\}from the training set for model selection\. Next, we introduce each model selection criterion in turn\. Due to page limits, detailed proofs of the theorems and propositions can be found inwang2025realistic\.

##### 5\.2\.1Covering Rate

###### Definition 2\(Covering Rate \(CR\)\)\.

The Covering Rate of a multi\-class classifier𝒇\\bm\{f\}on the PL validation set𝒟Val\\mathcal\{D\}^\{\\rm Val\}is defined as:

CR​\(𝒇\)=1nVal​∑i=1nVal𝕀​\(arg⁡maxjfj​\(𝒙iVal\)∈SiVal\)\.\{\\rm CR\}\(\\bm\{f\}\)=\\frac\{1\}\{n^\{\\rm Val\}\}\\sum\_\{i=1\}^\{n^\{\\rm Val\}\}\\mathbb\{I\}\\left\(\\mathop\{\\arg\\max\}\_\{j\}\\penalty 10000\\ f\_\{j\}\(\\bm\{x\}^\{\\rm Val\}\_\{i\}\)\\in S^\{\\rm Val\}\_\{i\}\\right\)\.\(38\)

CR indicates the fraction of validation data whose predicted label is included in its candidate label set\. It is a natural metric in PL learning, but its effectiveness may depend on the size of the candidate label sets\. When the number of partial labels of each example is equal to 1, i\.e\.,\|S\|=1\|S\|=1, PL learning is reduced to ordinary supervised learning and CR is reduced to the validation accuracy\. However, as\|S\|\|S\|increases, more false positive labels are included in the candidate label set\. In the most extreme case, when\|S\|=q\|S\|=q, PL learning is reduced to unsupervised learning and CR does not convey effective information\. Before analyzing the gap between CR and the validation accuracy, we introduce the following definition\.

###### Definition 3\(Ambiguity Degree\)\.

The Ambiguity Degreeγ\\gammais defined as

γ=sup\(𝒙,y\)∼p​\(𝒙,y\),S∼p​\(S\|𝒙,y\),y¯≠yp​\(y¯∈S\),\\gamma=\\sup\_\{\(\\bm\{x\},y\)\\sim p\(\\bm\{x\},y\),S\\sim p\(S\|\\bm\{x\},y\),\\bar\{y\}\\neq y\}p\(\\bar\{y\}\\in S\),\(39\)wherep​\(𝒙,y\)p\(\\bm\{x\},y\)is the joint distribution over𝒙\\bm\{x\}andyy\.

Ifγ<1\\gamma<1, the small ambiguity degree is satisfied and the ERM learnability for PL learning is guaranteed\(cour2011learning;liu2014learnability\)\. We also define the expected accuracy as

ACC​\(𝒇\)=𝔼p​\(𝒙,y\)​𝕀​\(arg⁡maxlfl​\(𝒙\)=y\)\.\{\\rm ACC\}\\left\(\\bm\{f\}\\right\)=\\mathbb\{E\}\_\{p\(\\bm\{x\},y\)\}\\mathbb\{I\}\(\\mathop\{\\arg\\max\}\_\{l\}\\penalty 10000\\ f\_\{l\}\\left\(\\bm\{x\}\\right\)=y\)\.\(40\)Then, we have the following proposition\.

###### Proposition 1\.

Suppose that there is a constantϵ∈\(0,1\)\\epsilon\\in\\left\(0,1\\right\)such that the expected accuracy of a classifier𝐟\\bm\{f\}satisfiesACC​\(𝐟\)≥ϵ\{\\rm ACC\}\\left\(\\bm\{f\}\\right\)\\geq\\epsilon\. Then, we have𝔼​\[CR​\(𝐟\)\]−ACC​\(𝐟\)≤\(1−ϵ\)​γ\\mathbb\{E\}\\left\[\{\\rm CR\}\(\\bm\{f\}\)\\right\]\-\{\\rm ACC\}\\left\(\\bm\{f\}\\right\)\\leq\(1\-\\epsilon\)\\gamma\.

The gap between CR and the accuracy is affected by both the accuracy and the ambiguity degree\. If the classifier is more accurate and the PL dataset is less ambiguous, the gap between the CR metric and the accuracy will be smaller\. Furthermore, we show that the minimizers of both are the same under certain conditions\.

###### Theorem 12\.

Suppose that the partial labels are generated by following the USS or the FPS with a constant flipping probability\. Then, for any two classifiers𝐟1\\bm\{f\}\_\{1\}and𝐟2\\bm\{f\}\_\{2\}that satisfy𝔼​\[CR​\(𝐟1\)\]<𝔼​\[CR​\(𝐟2\)\]\\mathbb\{E\}\\left\[\{\\rm CR\}\(\\bm\{f\}\_\{1\}\)\\right\]<\\mathbb\{E\}\\left\[\{\\rm CR\}\(\\bm\{f\}\_\{2\}\)\\right\], we haveACC​\(𝐟1\)<ACC​\(𝐟2\)\{\\rm ACC\}\\left\(\\bm\{f\}\_\{1\}\\right\)<\{\\rm ACC\}\\left\(\\bm\{f\}\_\{2\}\\right\)\.

Theorem[12](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem12)shows that when partial labels are generated by using the USS or the FPS with a constant flipping probability, the classifier that minimizes the expectation of CR will also minimize the expected accuracy\. Therefore, the CR metric will serve as a*consistent*model selection criterion for PL learning under certain data distribution assumptions\. However, this conclusion may not hold when partial labels are not generated by either strategy\.

##### 5\.2\.2Approximated Accuracy

Next, we introduce the definition of the Approximated Accuracy metric\.

###### Definition 4\(Approximated Accuracy \(AA\)\)\.

The Approximated Accuracy of a multi\-class classifier𝒇\\bm\{f\}on the PL validation set𝒟Val\\mathcal\{D\}^\{\\rm Val\}is defined as:

AA​\(𝒇\)=1nVal​∑i=1nVal∑j∈SiValfj​\(𝒙iVal\)∑k∈SiValfk​\(𝒙iVal\)​𝕀​\(arg⁡maxlfl​\(𝒙iVal\)=j\)\.\\mathrm\{AA\}\(\\bm\{f\}\)=\\frac\{1\}\{n^\{\\rm Val\}\}\\sum\_\{i=1\}^\{n^\{\\rm Val\}\}\\sum\_\{j\\in S^\{\\rm Val\}\_\{i\}\}\\frac\{f\_\{j\}\(\\bm\{x\}^\{\\rm Val\}\_\{i\}\)\}\{\\sum\_\{k\\in S^\{\\rm Val\}\_\{i\}\}f\_\{k\}\(\\bm\{x\}^\{\\rm Val\}\_\{i\}\)\}\\mathbb\{I\}\\left\(\\mathop\{\\arg\\max\}\_\{l\}\\penalty 10000\\ f\_\{l\}\(\\bm\{x\}^\{\\rm Val\}\_\{i\}\)=j\\right\)\.\(41\)

Then, we have the following theorem\.

###### Theorem 13\.

Suppose there is a functionC:𝒳×2𝒴↦ℝC:\\mathcal\{X\}\\bigtimes 2^\{\\mathcal\{Y\}\}\\mapsto\\mathbb\{R\}such that the conditionp​\(S\|𝐱,y\)=C​\(𝐱,S\)​𝕀​\(y∈S\)p\(S\|\\bm\{x\},y\)=C\(\\bm\{x\},S\)\\mathbb\{I\}\\left\(y\\in S\\right\)holds for PL data\. Suppose further that the multi\-class classifier𝐟​\(𝐱\)\\bm\{f\}\(\\bm\{x\}\)is consistent withp​\(y\|𝐱\)p\(y\|\\bm\{x\}\)\. Then, under mild conditionsAA​\(𝐟\)\\mathrm\{AA\}\(\\bm\{f\}\)is statistically consistent with the expected accuracy, i\.e\.,𝔼​\[AA​\(𝐟\)\]=ACC​\(𝐟\)\\mathbb\{E\}\\left\[\{\\rm AA\}\(\\bm\{f\}\)\\right\]=\{\\rm ACC\}\\left\(\\bm\{f\}\\right\)\.

The introduction of AA is inspired by data\-generation\-based strategies for PL learning\(wu2023learning\)\. Theorem[13](https://arxiv.org/html/2608.06896#chapter10.Thmtheorem13)illustrates that AA can be a consistent metric w\.r\.t\. the expected classification accuracy on test data under certain assumptions\. In particular, the data distribution assumption can hold for a wide range of types of partial labels\(liu2012conditional;wu2023learning\)\. However, there are two factors that may affect its effectiveness\. First, it may not be suitable for certain algorithms\(wen2021leveraged\)where the loss function is not*strictly proper*\(gneiting2007strictly;charoenphakdee2021on\)and its modeling output is not calibrated to the posterior probabilities\. Second, it requires that the modeling output to be accurate, which may not be satisfied in the early stages of training\.

##### 5\.2\.3Oracle Accuracy

Finally, we present the definition of the Oracle Accuracy metric\.

###### Definition 5\(Oracle Accuracy \(OA\)\)\.

The Oracle Accuracy of a multi\-class classifier𝒇\\bm\{f\}on a PL validation set𝒟Val\\mathcal\{D\}^\{\\rm Val\}is defined as

OA​\(𝒇\)=1nVal​∑i=1nVal𝕀​\(arg⁡maxlfl​\(𝒙iVal\)=yiVal\),\\mathrm\{OA\}\(\\bm\{f\}\)=\\frac\{1\}\{n^\{\\rm Val\}\}\\sum\_\{i=1\}^\{n^\{\\rm Val\}\}\\mathbb\{I\}\\left\(\\mathop\{\\arg\\max\}\_\{l\}\\penalty 10000\\ f\_\{l\}\(\\bm\{x\}^\{\\rm Val\}\_\{i\}\)=y^\{\\rm Val\}\_\{i\}\\right\),\(42\)whereyiValy^\{\\rm Val\}\_\{i\}is the underlying true label of𝒙iVal\\bm\{x\}^\{\\rm Val\}\_\{i\}\.

The OA metric is natural if we have access to true labels in supervised learning\. However, such a condition is not realistic in real problems of PL learning\. In fact, the availability of true labels contradicts the original motivation of PL learning, which is to reduce labeling costs at the expense of true label ignorance\. Inspired bygulrajani2021in, we restrict the use of true labels by allowing only one query \(the last checkpoint\) for each hyperparameter configuration\. This means that we do not allow early stopping when using the OA metric\. We try to compensate for the unrealistic access to true labels by restricting the model selection space\. We also include the results of OA with early stopping \(ES\), which can be considered as an upper bound of the model selection performance, for reference\. Actually, OA with ES may be the most common model selection criterion for PL learning papers\.

#### 5\.3PLENCH

In this section, we introduce the benchmark algorithms, datasets, and settings\. Due to page limits, the detailed benchmark results can be found inwang2025realistic\.

##### 5\.3\.1Benchmark Algorithms

We have divided the benchmark algorithms into four main groups\.

We considered deep PL learning algorithms that used simple loss functions or disambiguation strategies without strong regularization techniques as vanilla deep PL learning algorithms\. Identification\-based strategies included PRODEN\(lv2020progressive\), CAVL\(zhang20222exploiting\), and POP\(xu2023progressive\)\. Note that RC\(feng2020provably\)is in the same form as PRODEN, so we only included PRODEN here to avoid repetitive comparisons\. The averaging\-based strategies included ABS\-MAE\(lv2024on\)and ABS\-GCE\(lv2024on\), which showed favorable performance among the losses in the family\. The data\-generation\-based strategies included EXP\(feng2020learning\), MCL\-GCE\(feng2020learning\), MCL\-MSE\(feng2020learning\), CC\(feng2020provably\), LWS\(wen2021leveraged\), and IDGP\(qiao2023decompositional\)\. Also, LOG\(feng2020learning\)is analogous to CC, so we only included CC here\.

CL learning is a special case of PL learning with only one label excluded from each candidate label set of training examples, i\.e\.,\|S\|=q−1\|S\|=q\-1\(wang2025climage\)\. If we consider each label outside the candidate label set as a complementary label, it is possible to apply CL learning algorithms to solve PL learning problems as well\(feng2020learning\)\. Therefore, we included several vanilla CL learning algorithms with simple loss functions inPlench\. The vanilla CL learning algorithms included PC\(ishida2017learning\), Forward\(yu2018learning\), NN\(ishida2019complementary\), GA\(ishida2019complementary\), SCL\-EXP\(chou2020unbiased\), SCL\-NL\(chou2020unbiased\), L\-W\(gao2021discriminative\), and OP\-W\(liu2023consistent\)\.

We considered PL learning algorithms that employ strong representation learning or regularization techniques to be holistic PL learning algorithms\. We used five algorithms, including VALEN\(xu2021instance\), PiCO\(wang2022pico\), ABLE\(xia2022ambiguity\), CRDPL learning\(wu2022revisiting\), and DIRK\(wu2024distilling\)\.

We also included three noisy PL learning algorithms that explicitly considered tailored strategies to handle the cases where the true label might be outside the candidate label set\. The deep noisy PL learning algorithms included FREDIS\(qiao2023fredis\), ALIM\(xu2023alim\), and PiCO\+\(wang2024picoplus\)\.

##### 5\.3\.2Benchmark Datasets

To comprehensively evaluate the model performance of all algorithms, we included eleven real\-world PL learning benchmark datasets, including nine widely used tabular datasets and two image datasets that we collected\. The tabular datasets included Lost\(cour2011learning\), Soccer Player\(zeng2013learning\), and Yahoo\! News\(guillaumin2010multiple\)for the automatic face naming task, MSRCv2\(liu2012conditional\)for the object classification task, Mirflickr\(huiskes2008mir\)for the web image classification task, Birdsong\(briggs2012rank\)for the bird song classification task, Malagasy\(garrette2013learning\), Italian\(johan2009converting\), and English\(zhou2018weakly\)for the POS tagging task\.

For face age estimation, we considered ten crowdsourced labels of age numbers along with the true label as partial labels for a given human face\. For automatic face naming, we considered the names in the corresponding captions or subtitles as partial labels for a face cropped from an image\. For object classification, we considered object classes as partial labels for a segmentation part in an image\. For web image classification, we considered tags on a web page as partial labels for a given image\. For bird song classification, we considered bird species appearing in a ten\-second bird song fragment as partial labels for the singing syllables of the fragment\. For POS tagging, we considered all possible POS tags as partial labels for a given word with its contexts\.

##### 5\.3\.3Benchmark Settings

In this section, we mainly investigate the hyperparameter tuning problem in the context of model selection\. For tabular datasets, we first divided a test set from the entire dataset\. Since the datasets were not explicitly divided into training and validation parts, we manually divided them into a PL training set𝒟Tr\\mathcal\{D\}^\{\\rm Tr\}and a PL validation set𝒟Val\\mathcal\{D\}^\{\\rm Val\}\. Then, we trained a model with𝒟Tr\\mathcal\{D\}^\{\\rm Tr\}and evaluated its validation performance on𝒟Val\\mathcal\{D\}^\{\\rm Val\}with the model selection criteria proposed in Section[5\.2](https://arxiv.org/html/2608.06896#S5.SS2)as well as its test performance on the test set𝒟Te\\mathcal\{D\}^\{\\rm Te\}with ordinary labels\. We then selected the checkpoint with the best validation performance and returned the corresponding test accuracy as the final result\. We randomly selected a set of hyperparameter configurations from a given pool for a given data split and recorded the mean accuracy as well as the standard deviations for the best performance with different dataset splits\. We used ResNet\(he2016deep\)and DenseNet\(huang2017densely\)for image datasets and a multilayer perceptron \(MLP\) with a hidden layer width of 500 equipped with the ReLU\(nair2010rectified\)activation function for tabular datasets\.

All the algorithms were implemented in PyTorch\(paszke2019pytorch\)and all experiments were conducted with a single NVIDIA Tesla V100 GPU\. We used the Adam optimizer\(kingma2015adam\)\. We ran 60,000 iterations for the image datasets, 20,000 iterations for the Soccer Player, Italian, Yahoo\! News, and English datasets, and 10,000 iterations for the other datasets\. We recorded the performance on validation and test sets per 1,000 iterations\. We used three random data splits for PLCIFAR10 and five random data splits for tabular datasets\. For each data split, we selected 20 random hyperparameter configurations from a given pool\.

### 6Conclusion

In this chapter, we presented several recent advances in weakly supervised learning, including new supervision paradigms, assumption relaxations, and practical solutions\. First, we delved into a novel weakly supervised learning setting in which only unlabeled data pairs with confidence difference were provided\. To solve this problem, we derived an unbiased risk estimator to perform empirical risk minimization\. We established an estimation error bound to demonstrate that the optimal parametric convergence rate can be attained\. Additionally, we introduced a risk correction approach to address overfitting issues\. Second, we made the first attempt at consistent complementary\-label learning that does not rely on the uniform distribution assumption or an ordinary\-label training set to estimate the transition matrix in non\-uniform cases\. Based on a more practical distribution assumption, we proposed a consistent approach with theoretical guarantees\. Third, we proposed the first benchmark for performance evaluation of state\-of\-the\-art deep PLL algorithms\. We introduced new model selection criteria to address the lack of criteria for selecting models in PLL\. In the future, it is promising to investigate the integration of foundation models\(li2026weakly\), evaluation issues of other WSL problems\(wang2026accessible\), and consistent approaches for more WSL problems\(ma2026;wang2026rethinking\)\.

### Acknowledgment

The authors would like to thank the following individuals for their contributions to the conference papers included in this chapter: Lei Feng, Yuchen Jiang, Min\-Ling Zhang, Takashi Ishida, Yu\-Jie Zhang, Dong\-Dong Wu, and Jindong Wang\. WW was supported by the SGU MEXT Scholarship, by the Junior Research Associate \(JRA\) program of RIKEN, and by Microsoft Research Asia\. MS was supported by JST ASPIRE Grant Number JPMJAP2405\.

\\Backmatter

### References

## References