InstanT: Semi-supervised Learning with Instance-dependent Thresholds
Authors: Muyang Li
Runze Wu
Haoyu Liu
Jun Yu
Xun Yang
Bo Han
Tongliang Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: semi-supervised learning
pseudo-labeling
TL;DR: Semi-supervised learning with instance-dependent thresholds

Abstract: Semi-supervised learning (SSL) has been a fundamental challenge in machine learning for decades. The primary family of SSL algorithms, known as pseudo-labeling, involves assigning pseudo-labels to confident unlabeled instances and incorporating them into the training set. Therefore, the selection criteria of confident instances are crucial to the success of SSL. Recently, there has been growing interest in the development of SSL methods that use dynamic or adaptive thresholds. Yet, these methods typically apply the same threshold to all samples, or use class-dependent thresholds for instances belonging to a certain class, while neglecting instance-level information. In this paper, we propose the study of instance-dependent thresholds, which has the highest degree of freedom compared with existing methods. Specifically, we devise a novel instance-dependent threshold function for all unlabeled instances by utilizing their instance-level ambiguity and the instance-dependent error rates of pseudo-labels, so instances that are more likely to have incorrect pseudo-labels will have higher thresholds. Furthermore, we demonstrate that our instance-dependent threshold function provides a bounded probabilistic guarantee for the correctness of the pseudo-labels it assigns.

InstanT: Semi-supervised Learning with Instance-dependent Thresholds
Muyang Li", Runze Wu', Haoyu Liu?, Jun Yu², Xun Yang", Bo Han', Tongliang Liu"
"Sydney Center, The University Sydney: 'FUXI AI Lab, NetEase; University of Science and Technology of China; "Hong Kong Baptist University
Abstract
Semi-supervised learning (SSL. has been a fundamental challenge in machine learn- ing for decades. The primary family of SSL algorithms, known as pseudo-labeling. involves assigning pseudo-labels to confident unlabeled instances and incorporating them into the training set. Therefore, the selection criteria of confident instances are crucial to the success of SSL. Recently, there has been growing interest in the development of SSL methods that use dynamic or adaptive thresholds. Yet, these class-dependent
methods typically apply the same threshold to all samples, thresholds for instances belonging to certain class, while neglecting instance- thresholds,
information. In this paper, propose the study of instance-dependee which has the highest degree of freedom compared with existing methods. Specifi- cally, devise novel cestance-dependee instances by utilizing their instance-level ambiguity and the instance-dependen error rates of pseudo-labels, so instances that are more likely have incorrect pseudo-labels will have higher thresholds. Furthermore, we demonstrate that our instance-dependent threshold function provides bounded probabilistic guarantee for the correctness of the pscudo-labels assigns. Our implementation is available at hhttps://githii cww tttht//llbbbbbb 2ttp://22222NNuee12e
threshold funetion for all unlabeled
1 Introduction
In recent years, machine learning algorithms trained on abundant accurately labeled data have demonstrated unparalleled performance across different domains. However, in practice, it is often financially infeasible to collect reliable labels for all samples in large-scale datasets. A more practical solution select subset of the data and use expert annotations to assign labels them 39]. This scenario, where the majority of the data is unlabeled and only portion has reliable labels, is known as semi-supervised learning (SSL). SSL, our aim is usually to learn a classifier that has comparable performance the one trained in fully supervised manner. To achieve this, the majority of existing approaches adopt a training strategy named pseudo-labeling. More specifically, a model will be trained on small set of labeled data first, and this model will then be applied to the larger unlabeled set to assign predicted pseudo-labels to them. If the model's confidence in an instance exceeds a certain threshold, then this instance along with its predicted pseudo-label will be added to the training set for this iteration. Thus by itcratively expanding the training set, if the expanded instances are indeed assigned with correct labels, then the classification error will be gradually reduced [43]
However, since the model is bound to make mistakes, the newly added training samples are not always assigned with correct labels, which generates label noise (5) 46 44). Under the influence of label noise, the model will gradually over-fits fits to noisy supervision, hence accumulating generalization error. Since the model makes predictions based on instance features, it is usually assumed that for
"Corresonnennce to Tongliang Liu (tongliang.liu liu arngliinn..lu@xyddee...... eed.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Uniform l'hreshold
Class-dpenndent Threshold
Instance-dependdem Threshold
7(2s)
r(0)
T(m))
Figure 1: Illustration on the differences between uniform thresholds, class-dependent thresholds, and destance-deeendent thresholds in SSL. The black solid lines are the decision boundaries generated by the classifier, and the colored dashed lines are the confidence thresholds, the colored square, triangle, and circle represent the unlabeled instances with their predicted class. We can observe that uniform threshold does not depend on any factors, class-dependent thresholds only depend on the predicted pseudo-label, and instance- destacee-dependet thresholds depend on the features of unlabeled instances.
"hard" examples, the classifier is more likely to give incorrect predictions to them 55 making the label noise pattern instance-dependent
45 55).
Consequently, selecting an appropriate confidence threshold for pseudo-label assignment becomes a key factor that determines the performances of SSL methods. For predictions that more likely to have incorrect labels, we want to assign higher thresholds to avoid selecting them prematurely. And for predictions that are more likely to be correct, we want to assign lower thresholds to encourage adding them to the training set at an earlier stage. Conventionally, such a threshold is usually determined by empirical experience in ad-hoc manner, where only few of the existing works threshold selection. Recently, increasing research focused 48 [44], where such confidence threshold is conditional on some external factors, such as the current training progress. Notably, the vast majority of those methods consider single threshold for all instances and overlook their instance-level information, such as the instance-level label noise rate. As illustrated in Figure [ the instance-dependent threshold is the most flexible among existing threshold types.
consider the theoretical implication on the investigation of dynamic adaptive thresholds p 17 41
Motivated by this challenge, in this paper, we propose a new SSL algorithm named Instance- dependent Thresholding (InstanT). Since the learned model is subject to the influence of instance- dependent label error, we aim to quantify and reduce such error by estimating an instance mnstance-dependett confidence threshold function based on the potential label noise level and instance ambiguity (clean class posterior). In addition, we can derive a lower- bounrebonnded probability, for samples that satisfy the thresholds will be assigned to a correct label. From our main theorem, we show that as the training progresses, this probability lower-bound will asymptotically increase towards one, hence guaranteeing the pseudo-label quality for instances that satisfies our proposed thresholds.
We summarize our contributions as follows: (1) We propose an SSL algorithm named Instan which assigns thresholds to individual unlabeled samples based on the gestance-dependerd label noise level and prediction confidence. (2) We prove InstanT has a bounded probability to be correct, which vouch for the reliability of the lseulo-labels it assigns with theoretical guarantee. (3) To the best of our knowledge, this is the first attempt to estimate the instance instance-dependent thresholds in SSL, which has the highest degree of freedom compared with existing methods. (4) Through extensive experiments, we show that our proposed method is able to surpass state-of-the-art (SOTA) SSL methods across multiple commonly used benchmark datasets.
Related work. As we mentioned, some existing works have already been considered improve lseudo-labeling by leveraging "dynamic" or "adaptive" thresholds. More specifically, Dash [48 considers a monotonically decreasing dynamic threshold, based on the intuition that as training progresses, the model at later stage will provide more reliable predictions than at early stages. Flex- Match 54
further introduced class-dependent learning status addition to the dynamic threshold. Adsh 17 employs adaptive threshold under class imbalanced scenario by optimizing the number of labuls per class. As for adaptive thresholds, AdaMatch [9] considers using a pre-defined threshold factor multiplied by the averaged top-1 prediction confidence, making it adaptive to the

---

model's current confidence level. FreeMatch [4 considers combination of adaptive global and local thresholds, which combines the training progress and class-specific information.
In addition to the aforementioned more recent methods, most of the classical methods use pre-defined fixed thresholds, which remain constant throughout the entire training process [
18
19
29 36]
Such thresholds are usually set to be high enough to prevent the occurrence of incorrect pscudd-
labels. Notably, other approaches such as reweighting [TO] 22], distribution alignment 200 31 42).
contrastive learning 24 49), consistency regularization
were also employed to improve SSL.
Preliminaries
2.1 Notation and Problem Setting
We consider the general setting from SSL, namely, we have small group of labeled instances X; := {I1 ...., In. with their corresponding labels Y := fy/..... yn And there is an unlabeled with their latent labels Yu = (Wn+1,.... Vn+mm usually, we have m >> >> n. Furthermore, we assume that the labeled instances and unlabeled instances are independent and identically distributed (i.i.d), i.e. X (x,, Y, == (Y, Yr.Y.. E E..
instance group X, := (In+11:-...
We term the model trained with clean and pseudo-labels as f. parameterized by 0. Since fo is bound make mistakes, its generated pseudo-label Y, will contain label errors. Hence the softmax predictions of fe are actually approximating the noisy class posterior. We fix the notation for the real noisy class posterior as PX) at t-th iteration, whereas our approximated noise class posterior is |( which can be obtained from the softmax predictions of the model fo at t-th iteration.
As the clean label for the unlabeled set is unknown, we instead wish to recover the Bayes optimal label for all the unlabeled instances, which is the label class that maximizes the clean class posterior (50 [66] The Bayes optimal label is generated by the hypothesis that minimizes the risk within the hypothesis space, i.e. the Bayes optimal classifier, which we denote as h". And we can denote the Bayes optimal label for as h" (x).
2.2 Instance-dependent Label Noise in SSL
As mentioned in the previous section, label noise is inevitable challenge in SSL. Moreover, since P(Ý X) is dependent X, we say the label noise is instance-deeenndet 12 45 we have x x) T(x) transition matrix, which models the generation of label noise. P(Y X = x)) represents the latent
Concretely,
x)
35 where T(x,) is the instance-dependent
clean class posterior for unlabeled samples. We can define the ij-th entry of T(x)) as:
(z) p(Ý = j| = x;
(1)
which means the ij-th entry of (()) models the probability that æ with clean label = i will be predicted = j.
2.3 Tsybakov Margin Condition
We assume our learned classifier satisfies Tsybakov Margin Condition [38]. which essentially re- strained the level of complexities of the classification problem by assuming the data are separable enough. a commonly used assumption for various Machine Learning problems (2 56 in-
cluding SSL [48]. Without the loss of generality, we will directly present the multi-class Tsybakov Margin Condition (2. 56), whereas the binary case will be provided in the Appendix B
Assumption (Multi-class Tsybakov Margin Condition). For some finite constant C, a > 0, and 5u (0, 1), the Tsybakov Margin Condition holds if vo E (0, do), have
P[P(Y = >|X = x) P(Y = $ X = x) s 5] < C8..
Where P(Y = 7|X æ) and P(Y X ær) are the largest and second-largest clean class posterior probability for
3

---

2.4 Quality-Quantity Trade-off in SSL
To understand the choice of pseudo-label thresholds in SSL, is essential to consider the trade-ofi off between the quality and the quantity of the pseudo-labels [1]. Typically, higher threshold is presumed yield superior label quality, as it assigns pseudo-labels solely to instances where the classifier exhibits high level of confidence. Conversely, elevating the threshold diminishes the quantity of pseudo-labels, as leads to the exclusion of instances where the classifier lacks sufficient confidence. Hence causing the dilemma of quality- trade-off.
One possible approach to address the quantity-quality trade-off in SSL is to apply dynamic threshold, which is dependent on the training progress. This is because the evaluation metric for confident samples is usually not stationary throughout the training process of neural networks. As the model's predicted probability is subject to the level of over- over-fitting [66 30), designing thresholding function that is dependent on the training process is crucial to the success of SSL algorithms 9 41 Intuitively, in the early stage of the training process, where the model has just started to fitting, the threshold should not be set too high to filter out too many samples, and as the model has already well-fitted to the training data, the threshold should be elevated to combat falsely confident instances caused by confirmation bias
3 Instance-dependent thresholds A theoretical perspective
In this section, we focus on answering the specific research question: For SSL, can we derive instance-dependent pseudo-label assignment thresholds with theoretical guarantees?
The answer to this question is affirmative. We will present our main theorem and the proof to show that for samples that satisfy our instance-dependent threshold function, their likelihood of being correct is bowerebounded.
3.1 Lower-bound Probability of Correctness
For a classifier trained with sufficient accurately labeled data, its prediction will be made if P(Y = >| = x) > P(Y =| æ). However, under the existence of label errors, the fidelity of the classifier can no longer be guaranteed. Recently, Zheng et al. [56] showed that the classifier influenced by the label noise can still have a bounded error rate. We show that in SSL tasks, where the label noise is pestance-dependen we can establish lower-bound probability for the predictions to be correct through similar derivations.
Recall Assumption D we have y := arg max, P(Y = -iX- = æn), == arg max P(Y
i|X- Iu), k arg max; P( i|X I..) = du. And let eg be the estimation error between
our estimated noisy class posterior P() and true noisy class posterior P(Y]X). We can then formulate our main theorem:
Theorem 1. Assume estimated noisy class posterior P(FIX) satisfies Assumption with C,
do E (0, 1), and < 60 mjn Tú ((,(())) we have:
P =[== hi (aw),, p(L k|X = xx) 2 [(xw)) 1 1
(2)
where 7 (xx)) is the instance-dependent threshold function:
Yl
T(xu) T PPY = =||X-
xu) + (TY =||X v.))
The proof of Theorem I is provided in Appendix C Theorem I substantiates that, as our model over-fits to the label error (as eg decreases), and the transition matrix can be successfully estimated, the probability bower-bound of the assigned pseudo-labels are correct will increase asymptotically. This guarantees the quality of the pseudo-labels r(*.) assigned. Note that, r(xu) requires the clean class posterior of unlabeled instances, which can provably inferred upon the successful estimation of T T(x) and the noisy class posterior [26] 32]
To gain deeper understanding of Theorems T we will try to intuitively understands the outputs of
T(x.). Our aim is to examine the behavior of 7 ((x in relation to the unlabeled sample vu, which

---

Classifier
Classifier
P(P = xx)
(2,)) )
P( x
x1)
fo(x)
000001
folæ)
000.402
7 (2x))
X1
Yi
L(0')
(0.(0.6)
Y:
0..0..011
0.70220.
X (x)
0.30600
X
for(2)
0.40.501
0.
0..02..666
T(mm))
T(z.)
Noise Transition Estimator
Noise Transition Estimator
Figure 2: Overview of InstanT.. Left: training process of transition matrix estimator for For labeled instance 3t, whose label is 2, the classifier fo will first generate noisy class posterior. Then, we want the second row of the transition matrix to approximate the noisy class posterior by minimizing L(O') from Equation Right: The inference process of (a..)) When calculating r@x.), Tu will be simultaneously passed to the classifier and transition matrix estimator. Since the predicted class label from the model that minimizes the forward loss (Fquation (), we will use the first column from our estimated transition matrix to modulate threshold based on Theorem
has predetermined clean class posterior. If we observe an increase in the sum of column in the transition matrix, it will result in corresponding increase in the threshold r(ru). This implies that when zu is highly likely be assigned with an incorrect pseudo-label, r(xx) will assign higher threshold in order to prevent its premature inclusion of (æx. Due] in the training set. Conversely, when zu is less likely to be assigned with a incorrect pseudo-label, r(x.) will assign a lower threshold to encourage adding {æ Du } to the training set.
3.2 Identification of Instance-dependent Transition Matrix in SSL
Theorem builds upon the assumption that T(x) can be successfully identified. Yet, the identification of T(x) has been long-standing issue in the field of label noise learning. Fortunately, in SSL, we argue that T(x) can be provably identified under mild conditions. We will first justify argument from theoretical perspective based on the Theorems from Liu et al. (27). Subsequently, we will also propose the empirical methods for estimating T (xx) from an intuitively understandable aspect in the following section.
We will start by defining the identifiability, we use Ω to represent an observation space and use O to represent general parametric space. Then, for distribution with parameter 0', such that o' e θ, model Pg on Q can be defined [0). We further define its identifiability as:
Definition (Identifiabilitty. Parameter 6' is said to be identifiable if Py + Po", 4A #
P(Y = x)), i.e., Pe. is a distribution defined by the transition probability and clean class posterior. To determine the identifiability of T(x),, we also need to define the term informative noisy labels. Specifically, we have:
In our case, 0'(x) P(YXX
Definition 2 (Informative noisy labels). For a given sample (x, y), its noisy label gJ is said to be informative if cank(T((x.)) = YY).
Then, we can make the following theorem:
Theorem 2. With i.i (x, y): pairs, three informative noisy labels 9: are sufficient and necessary for the identification T
The Theorem is based on Kruskal's Identifiability Theorem, the proof is provided in the Appendix D From Theorem 2 and Definition 2 we can conclude thar, in SSL, if we have more than three
labeled samples per class, transition matrix T (ax:) identifiable, more discussions on this can also be
found in Appendix D
5

---

InstanT: Instance-dependent thresholds for pseudo-label assignment
4.1 Instance-dependent Threshold Estimation
While Theorem ! provides a theoretical guarantee for the correctness of T (xxu), as discussed in section 2.4 SSL algorithms can benefit from non-constant thresholds 41 Here we define the dynamic threshold at iteration / from the relative confidence threshold (RT) in AdaMatch [9]
n
Rit
P( = [I.
max
xi)e 3,
n
where is the number of labeled samples, and is fixed discount factor. Subsequently, present the instance-depee denendent threshold function at iteration t:
r(xu). min 1, (a s|X Tule
Σ iigll
Tr P(Y i|X xu)e + Ket
(5)
Note that this estimation process requires the clean class posterior, which can be estimated or approximated using a transition matrix via importance re-weighting [26] [6] or loss correction
[32 [5), details will be introduced in the following section. We also remark here that less strict
desteneeddepeneent version the threshold function can be used with the class-dependent transition
matrix [32 46 [22, which can lead to better empirical results under certain cases, it is also important
to note that even under deas-deenndent transition matrix, the threshold function is still instance- dependent, the noise class posterior are instance-dependent.
4.2 Modelling Instance-dependent Label Noise
Now we will introduce piratical method for estimating T(x) in SSL. Our approach involves approximating the label noise transition pattern using a Deep Neural Network. As we recall from Equation T(x) can be described a mapping function T' X + R|*XX|), since we already know that, in general cases, Txx)) is identifiable in SSL, we only need to find the correct mapping function. In addition, since we have clean label Yi for Xt, and we also have the noisy pseudo-labels Ý, for Xi, this enables to directly fit a model to approximate T(æ). Therefore, we want our transition matrix estimator, parameterized by 6 to approximate the label noise transition process at every iteration t:
(x1) P( j|M = i, x);0 = P(Ý j| i, x: T(x).
(6)
The above approximation holds since label noise is assumed to be i.id, therefore both labeled and unlabeled samples share the same noise transition process. As we estimate the noisy class posterior for labeled samples,
therefore collect distribution D = YY, P( Observing Equation 6 we can design following objective for 6' minimize:
=1))
LD((')
Σ de log( ((x)).
Where zt is the one-hot vector for the label of labeled samples, thus yı f(()) is equivalent finding the class-conditional noise class posterior P(ý: = j|Yi = i, X, æ2; ). 9r is the one-hot noisy pseudo-label of æ1, minimizing (. will result fm 0' approximate ((x). As shown in Figure
2 fg will be trained in parallel to the main classifier and updated in every epoch.
Notably, the estimator for the transition matrix InstanT not constrained to one specific method,
there has been a wide versatile of 7 estimator in the field of label noise learning 25 45 51, we have incorporated some of them into the implementation of Instan', indicating the good extensibility of InstanT.

---

4.3
Distribution Alignment
When the prediction of the classifier becomes imbalanced, Distribution Aligmment (DA) is used modulate the prediction so that the poorly predicted class will not be overlooked completely This is achieved by estimating the prior of the pseudo-label p(ý) during training, and setting a clean class prior P(Y). which usually assumed to be uniformly distributed. The distribution alignment process can be described as P(Y = _ = σu) = Norm( = j = Tu P( j P(Y =j)). where Norm is total-sum scaling. Therefore, if the distribution of Y severely imbalanced, DA will force the prediction for the minority class to be scaled up, and the prediction for the over-populated class to be scaled down.
20 42
4.4 Loss Correction
While the classifier trained with incorrect pseudo-labels is subject to the influence of noisy supervision,
in order satisfy Theorem 1 the estimated softmax predictions from fo must approximate the clean class posterior [56]. As we have already demonstrated that the transition matrix can be identified in standard SSL setting, in this part, will show how infer clean class posterior from noisy predictions and transition matrix, by utilizing forward correction [32]. Specifically, let lg be proper composite loss
33 (e.g. softmax cross-entropy loss), forward correction is defined as:
fo(x))) = T( ( f
(8)
where to is an invertible link function. It has been proven that minimizing the forward loss with an accurately estimated transition matrix equivalent to minimizing the loss defined over clean latent pseudo-labels 32]. Therefore, minimizing E will let the softmax prediction of classifier fo approximate the clean class posterior.
4.5 Training with Consistency Regularization Loss
Lastly, we provide an overview of the training objective of InstanT. We employ the widely adopted consistency regularization loss [6 47,, which assumes well-learned and robust model should generate consistent predictions for random perturbations of given instance. Previous methods have commonly employed augmentation techniques introduce perturbations. The training loss of classifier fo consists of two parts: supervised loss LD, (0) and unsupervised loss (0). LD, (0) is calculated by the labeled samples, specifically, we have:
n Evn, fo((a)))
LD. (0)
where is the number of labeled samples, yı is the one-hot label for æn, and W is weak augmentation function [36 47], and is the cross-entropy loss function. Unsupervised loss Lp,, (f) is calculated by the unlabeled samples X, and their predicted laeudo-labels Y,, which can be defined as:
(0) Σ 1(p(8 = k|X W(xw)) > T (w))):) (fn (o((ew))))
(10)
where m is the number of unlabeled instances, 9., is the one-hot pseudo-label for wu. and S is strong augmentation function 7 15). I is indicator function that filters unlabeled instances using 7 (a.).. Combining the supervised and unsupervised loss, we then have the overall training objective:
(o) (0) ALp, (0),
(11)
where À is used to control the influence of the unsupervised loss.
7

---

Table 1: Top-1 accuracy with pre-traines trainedddd ViT. The best performance bold and the second best performance is underlined. All results are averaged with three random seeds {0,1,2) and reported with 95% confidence interval.
Datasct Label
CIFAR-I0
CIFAR-100
STL-10
40
250
200
400
2500
100
37.65291
88.21
95,42:04
63.34
73.13=0.
84.28
30. 647
57.16142
23.44
MT
64.57+44
87.15
95.25+05
59.50
69.42=0.9
82.91
42.72=74
66.80+34
77.71
MixMatch
65,04+26
97.16209
97.95=01
60.36
72.26=:0.1
83.84
10.68=11
27.58:162
61.85+1113
VAT
60.07=663
93.33+t6.
97.67=02
75.33=004
83.42+00.4
20.57=44
18=7.
80.94
UDA
78.76136
97.92102
97.96.uu1
49.116
25.85
83.81102
48.37
79.67
89 89.46.110
FixMatch
66.50=15.1
97. 27.
97.95a01
65 41.
75.52=0011
83.98
40.13
77.72
88.41
FlexMatch
70.54190
97.78
97.88.nn
63. 63.761aM
74.01 2.0.5
83.72.a03
60.63:112
78. 17
89. 24.53
Dash
74.35+45
96.63220
97.90+003
63.33-104
74.54=0.2
84.01
41.06244
78.03=33
89.56:220
AdaMatch
85. 35.15
97.94
97.92201
73.61
78.59:004
84,49.16.1
68.17
83,50
89.25
Instan'T
17
97.93+01
98.08=a1
74.17
78.80
84.28+0.5
69.39:744
85,09:28
89.35
5
Experiments
5.1
Experiment Setup
We use three benchmark datasets for evaluating the performances of InstanT,, they are: CIFAR- 10. CIFAR-100 [21], and STL--10 [13]. CIFAR-10 has 10 classes and 6,000 samples per class. CIFAR- 100 has 100 classes and 600 samples per class. STL--10 has 10 classes and 500 labeled samples per class, 100,000 unlabeled instances in total. For each dataset, samples to create different levels of difficulty. Following recently more challenging settings 41], where the labeled samples could be extremely limited, we set the number of labeled samples per class on CIFAR-10 as {1, 4, 25), for CIFAR-100, we set as {2, 4, 25,, for STL-10, we set as {1,4, 10).
set varying numbers of labeled
To ensure fair comparison between our method and all baselines, and to allow simple reproduction of our experimental results, we implemented InstanT and conducted all experiments within USB (Unified SSL Benchmark) framework [40]. To improve the training efficiency, e.g. faster convergence, we use pre-trained ViT as the backbone model for all baselines with the same hyper-parameters in part I. We use A (28 as the default optimizer, where the learning rate is set 5e 4 for CIFAR-10/100, le - 4 for STL-10 40 The total training iterations K are set as 204,800 for all datasets. The training batch size is as for all datasets. For more comprehensive evaluation of our proposed method, we also conduct experiments with Wide ResNet [53 trained from scratch, the 54 these results are summarized
detailed settings are aligned with existing works 77 9 36 47
48
in part II. We select a range of popular baseline methods to evaluate against Instan'T, which includes
Pseudo-Label (PL) (23], MeanTeacher (MT) (37). VAT [29). MixMatch (8), UDA (47). FixMatch
[36]. Dash 4 FlexMatch [54] and AdaMatch 19]. More comprchensive setting details, including
full details of hhper--prammnnn parameters, can be found in Appendix A
5.2
Main results
Part I. Our main results will be divided into two parts: part and part II. For training efficiency, we will use a pre-trained Vision Transformer as the backbone model in part I, enabling us to compare a more diverse collection of baselines over broader range of benchmark settings. In Part II, we will select baselines with better performance from Part and train them from scratch for more comprehensive evaluation.
Table 2: Running time on STL-10
Method
s/epoch
FixMatch AdaMatch Instan'T
30.1
30.1
Experimental results from part are summarized in Table 0 where we can observe that, overall, Instan'T achieves the best performances in most of the settings. More specifically, in the setting where label amount is extremely limited, Instan'T exhibits the most significant improvement over all datasets, including an average 2. 17% increase accuracy on CIFAR- 10 (10) over SOTA. While the identifiability of the transition matrix cannot be guaranteed with extremely limited labels, this could be remedied by including highly confident instances and their pseudo-labels to the labeled set and using them to better estimate the transition matrix. However, the number of labeled samples increases, the
31.1
Runninn time is tested on NVIDIA RTX 4090 GPUs.
8

---

Table 3: T accuracy with WRN-28. The best performance bold and the second best performance is underlined. All results are averaged with three random seeds (0.1,2) and reported with a 95% confidence interval.
Datasct
CIFAR-10
CIFAR-100
# Label
40
250
4000
400
2500
10000
UDA
91.60++1
94.44_0.3
95.55=00.
40.60=18
64.79
72.13+02
FixMatch
91.45++17
94.87=0.1
95.51
43.08
65.63
71.65
FlexMatch
94.53+104
94.85=0.1
95.62=0011
4..
66.11+0.4
72.48:02
Dash
84.67-44
94.78=n3
95.54=001
45.26=26
65.51+aa1
72.10=03
AdaMatch
94.64400
94.76=01
95.46=0.1
52.02
66.36+477
72.32402
I
94.83
94.72=0.2
95.57
53
67.09
72.30+0.
dominance of Instan'T becomes less pronounced. We hypothesize that this can be attributed to the classifier fo performing better with more labeled samples, resulting in fewer label errors. Since Instan'T primarily aims to increase the threshold for instances likely have noisy pseudo-labels, the impact of Instan'T becomes less significant in the presence of reduced label noise. Moreover, comparing the performance gap between InstanT and its closest counterpart, AdaMatch, becomes apparent that InstanTT consistently outperforms AdaMatch in nearly all cases. This observation underscores the non-trivial improvement and contribution brought forth by InstanT.
Part II. In this part, we will present the experiment results of part II, which are summarized Table 3 Specifically, we will compare Instan I against other popular baseline methods on CIFAR-I0/100 trained from scratch. For all methods, we use WRN-28-2 as default backbone model, trained with 2 iterations. We use SGD as the default optimizer, with momentum set as 0.9, initial learning rate as 0.03 and cosine learning rate scheduler.
Observing from experiment results, we summarize similar patterns the results from part I. Overall, Instan'T brings most significant performance increases when the number of labeled samples are limited, e.g., when there is only 4 labeled samples per-class. Notably, for CIFAR- (400), Instan'T exhibits an increase in accuracy for nearly 2%, which can be view as a significant improvement SOTA baseline. While on other cases such as CIFAR-10 (250) and CIFAR-100 (10000), InstanT outperformed by other baseline methods, we emphasize that no single baseline consistently outperforms InstanT in all cases.
Another question of interest is whether InstanT will be as efficient as other methods in training time. While learning transition matrix estimator does sacrifice time and space complexity some extent, we show that Instan'T can still maintain high efficiency. As shown in Table compared with FixMatch and AdaMatch, InstanT almost does not introduce further significant computational burden.
To gain better understanding of the key differences between Instan'T and existing methods, we now focus on the visualizations of Instan'T compared to representative baselines. Specifically, we will display the classification accuracy, unlabeled sample utilization ratio, and pseudo-label accuracy of
Instan Free [41), AdaMatch [9]. and FixMatch (36) in Figure These models trained
from scratch on CIFAR-100 with 400 labeled samples, following commonly used settings [36 41).
Examining the classification accuracy in Figure 3(a) we observe that while InstanT does not converge as rapidly as FreeMatch. it ultimately achieves superior accuracy the later stages of training. This attributed to Instan'iss 's ability to find a better balance between the quantity and quality of pseudo-labels.
As depicted in Figure 36b (bb and B(c] although InstanT utilizes fewer unlabeled samples compared to FreeMatch, it demonstrates sig significantly improved accuracy on pseudo-labels. On the other hand, AdaMatch exhibits similar pseudo-label accuracy Instan'T but utilizes a smaller proportion of unlabeled instances. The key distinction lies in the instance- dependeet threshold function employed by Instan',, which allows us to set a lower Ke for InstanT compared to AdaMatch, as InstanT mitigates the negative impact by increasing the instance-dependent thresholds for instances more prone to label noise, whereas AdaMatch will incorporate too many instances with incorrect pseudo-labels.
5.3 Ablation study

---

0.5
0.8
0.7
Preude tabel Ac
0.4
0.6-
ACC.
Instant FreeMatch
Uniobated
0.4
InstanT
Reeeaatch
0.4
0.3
InstanT
FraaMatch
0.2
0.2
AdaMatch
FiMMatch
FadMatch
0.1
100k
200k
300k
400k 500k
0.0
100k
400k 500k
0.1
100k
200c
300k
4D0k
500K
Traininng iter.
Triining Iter.
Training Iter.
(a) Top-1 Accuracy
(b) Utilization ratio
(c) Pscudo-label Accuracy
Figure 3: Results from InstanTT and selected baselines, trained from scratch CIFAR-100(400),
Table 4: Ablation study on STL-10(40).
In this section, we will be verifying the effects of each component of InstanT,, specifically, we will focus on eval- uating the parts that we adapted from existing works, and determine how many performance improvements are tributed to our instance-dependent thresholds. Results of this ablation study are summarized Table 4 where all experiments averaged over three random seeds and ran on STL-10((0) using the setting part I. First, we observe that Instan T-I removed both Distribution Alignment (DA) and relative thresholds (RT), which makes equivalent to adding T( top of the fixed threshold of FixMatch. Notably, this also brings significant improvement over FixMatch for over 2%, which further verifies the effectiveness of our proposed Setance-dependent thresholds. Simply removing RT DA will also cause performance drop, which is aligned with the results from AdaMatch 9
Method
RT
DA
Acc.
FixMatch
X
77.72.1.4
AdaMatch
83,50=4.2 /
79.92 V
InstanT-I
X
X
Instan'-I11
81.49 X
Instan InstanT
X
J
82.97
J
85.09
Conclusion
In this paper, we introduce novel approach to thresholding techniques in SSL called instance- dependent confidence threshold. This approach offers the highest level of flexibility among existing methods, providing significant potential for further advancements. We then present Instan'T, theoret- ically guided method designed under the concept of instance-dependen threshold. Instan'T assigns unique confidence thresholds to each unlabeled instance, considering their individual likelihood of having incorrect labels. Additionally, demonstrate that proposed method ensures bounded probability of assigning correct pseudo-labels, characteristic rarely offered by existing SSL ap- proaches. Through extensive experiments, demonstrate the competitive performance of Instan'T when compared to SOTA baselines.
Acknowledgement
Tongliang Liu is partially supported by the following Australian Research Council projects: FT220100318, DP220102121, LP220100527, LP220200949, and IC190100031. Muyang Li, Runze Wu and Haoyu Liu are supported by NetEase Youling Crowdsoureing Platform. This research was undertaken with the assistance of resources from the National Computational Infrastructure (NCI Australia), an NCRIS enabled capability supported by the Australian Government. The authors acknowledge the technical assistance provided by the Sydney Informatics Hub, Core Research Facility of the University of Sydney.
10

---

References
[1] Abulikemu Abuduweili, Xingjian Li, Humphrey Shi, Cheng-Zhong Xu, and Dejing Dou. Adaptive consistency regularization for semi-supervised transfer learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6923-6932, 2021.
[2] Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In International Conference on Machine Learning, pages 1220-1223 PMLR, 2013.
[3] Elizabeth Allman, Catherine Matias, and John Rhodes. Identifiability of parameters in latent structure models with many observed variables. 2009.
[4] Eric Arazo, Diego Ortego, Paul Albert, Noel O'Connor, and Kevin McGuinness. Pseudo- labeling and confirmation bias in deep semi-supervised learning. In 2020 International Joint Conference on Neural Networks (IJCNN, pages 1-8. IEEE, 2020.
[5] Yingbin Bai, Erkun Yang, Bo Han, Yanhua Yang, Jiatong Li, Yinian Mao, Gang Niu, and Tongliang Liu. Understanding and improving early stopping for learning with noisy labels. Advances in Neural Information Processing Systems, 34:24392- 24403, 2021.
[6] Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31, 2018
[7] David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel. Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring. arXiv preprint arXiv: /91 1.09785, 2019.
[8] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach semi-supervised learning. Advances neural information processing systems, 32, 2019.
[9] David Berthelot, Rebecca Roclofs, Kihyuk Sohn, Nicholas Carlini, and Alex Kurakin. Adamatch: A unified approach to semi-supervised learning and domain adaptation. arXiv preprint arXiv:2106.0477 046.04 2021.
[10] H Chen, R Tao, Yue Fan, Y Wang. M Savvides, J Wang, B Raj. X Xie, and Bernt Schiele. Softmatch: Addressing the quantity-quality tradeoff in semi-supervised learning. In Eleventh International Conference Learning Representations. OpenReview. net, 2023.
[11] Pengfei Chen, Junjie Ye, Guangyong Chen, Jingwei Zhao, and Pheng-Ann Heng. Beyond class-conditional assumption: A primary attempt to combat instance-dependent label noise. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11442-11450, 2021.
[12] Jiacheng Cheng, Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance and label-dependent label noise. In International Conference Machine Learnin, pages 1789-1799 PMLR, 2020.
[13] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 215-223. JMLR Workshop and Conference Proceedings. 2011.
[14] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pages 702-703, 2020.
[15] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint
111017080.5555 2017.
[16] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. calibration of modern neural networks. In International conference machine learning, pages 1321-1330. PMLR, 2017.

---

[17] Lan-Zhe Guo and Yu-Feng Li. hasssimbalancee semi-supervised learning with adaptive thresholding. In International Conference on Machine Learning. pages 8082-8094, PMLR, 2022.
[18] Zhuo Huang, Chao Xue, Bo Han, Jian Yang, and Chen Gong. Universal semi-supervised learning. Advances in Neural Information Processing Systems, 34:2671 14 26722,,,-26725, 2021.
[19] Zhuo Huang, Jian Yang, and Chen Gong. They are not completely useless: Towards recycling transferable unlabeled data for class-mismatched semi-supervised learning. IEEE Transactions on Multimedia, 2022.
[20] Jaehyung Kim, Youngbum Hur, Sejun Park, Eunho Yang. Sung Ju Hwang, and Jinwoo Shin. Dis- tribution aligning refinery of pseudo-label for imbalanced semi-supervised learning. Advances in neural information processing systems, 33:14567-14579 2020.
[21] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[22] Zhengfeng Lai, Chao Wang, Henrry Gunawan, Sen-Ching S Cheung, and Chen-Nee Chuah. Smoothed adaptive weighting for imbalanced semi- semi-supervised learning: Improve reliability against unknown distribution data. In International Conference on Machine Learning, pages 11828-1 109--1184 1843. PMLR, 2022.
[23] Dong- Hyuu Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, page 896, 2013.
[24] Doyup Lee, Sungwoong Kim, Ildoo Kim, Yeongjac Cheon, Minsu Cho, and Wook-Shin Han. Contrastive regularization for semi-super learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 3911-39200 2022.
[25] Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end label-noise learning without anchor points. In International conference on machine learning, pages
PMLR, 2021.
[26] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on pattern analysis and machine intelligence, 38(3):447-461, 2015.
[27] Yang Liu. Identifiability of label noise transition matrix. arXiv preprint arXiv:2202.02016. 2022.
[28] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 17X1v:1711.05101, 2017.
[29] Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii Virtual adversarial training: a regularization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 1979 2018
[30] Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip Torr, and Puneet Dokania. Calibrating deep neural networks using focal loss. Advances in Neural Information Processing Systems, 33:15288-15299 2020.
[31] Youngtaek Oh, Dong-Jin Kim, and In So Kweon. Daso: Distribution semantics- pseudo-label for imbalanced semi-supervised learning. In Proceedings of the IEEF/CV Conference Computer Vision and Pattern Recognition, pages 9786-9796, 2022.
[32] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE conference computer vision and pattern recognition. pages 1944-1952, 2017.
[33] Mark D Reid and Robert C Williamson. Composite binary losses. The Journal of Machine Learning Research, 1:2387-24422, 2010.
[34] Kuniaki Saito, Donghyun Kim, and Kate Saenko. Openmatch: Open-set consistency regulariza- tion for semi-supervised learning with outliers. arXiv preprint arXiv:2105.14111 2021.
12

---

[35] Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. In Conference on learning theory, pages 489-511. PMLR, 2013.
[36] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raf- fel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi- supervised learning with consistency and confidence. Advances in neural information processing systems, 33:596 608, 2020.
[37] Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged con- sistency targets improve semi-supervised deep learning results. Advances in neural information processing systems, 30, 2017.
[38] Alexander Tsybakov. Optimal aggregation of classifiers in statistical learning, The Annals of Statistics, 32((): 2004.
[39] Xudong Wang, Long Lian, and Stella X Yu. Unsupervised selective labeling for more effective semi-supervised learning. In Computer Eision-ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXX. pages 427-445. Springer, 2022.
[40] Yidong Wang, Hao Chen, Yue Fan, Wang Sun, Ran Tao, Wenxin Hou, Renjie Wang, Linyi Yang. Zhi Zhou, Lhe Guo, et al. Usb: A unified semi-supervised learning benchmark for classification. Advances in Neural Information Processing Systems, 35:3938-3966 2022.
[41] Yidong Wang, Hao Chen, Qiang Heng, Wenxin Hou, Marios Savvides, Takahiro Shinozaki, Bhiksha Raj, Zhen Wu, and Jindong Wang. Freematch: Self-adaptive thresholding for semi- supervised learning. arXiv preprint arXiv:2205.07244 072466 2022.
[42] Chen Wei, Kihyuk Sohn, Clayton Mellina, Alan Yuille, and Fan Yang. Crest: A class- rebalancing self-training framework for imbalanced semi remi-supervised learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 10857-10866, 2021.
[43] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations.
[44] Songhua Wu, Xiaobo Xia, Tongliang Liu, Bo Han, Mingming Gong, Nannan Wang, Haifeng Liu, and Gang Niu. Class2simi: A noise reduction perspective on learning with noisy labels. In International Conference on Machine Learning, pages 11285-11295. PMLR, 2021.
[45] Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. Advances in Neural Information Processing Systems, 33:7597-7610, 2020.
[46] Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? Advances in neural information processing systems, 32, 2019.
[47] Qizhe Xie, Zihang Dai, Eduard Hovy, Minh- Mhnh-Thang Luong, and Quoc Le. Unsupervised data augmentation for consistency training. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 6256 6266666688676 2020.
[48] Yi Xu, Lei Shang, Jinxing Ye, Qi Qian, Yu-Feng Li, Baigui Sun, Hao Li, and Rong Jin. Dash: Semi-supervised learning with dynamic thresholding. In International Conference on Machine Learning, pages 1 11525-11555 1536. PMLR, 2021.
[49] Fan Yang. Kai Wu, Shuyi Zhang, Guannan Jiang, Yong Liu, Feng Zheng, Wei Zhang, Chengjie Wang, and Long Zeng. Class-aware contrastive semi-supervised learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14421-14430. 2022.
[50] Shuo Yang, Erkun Yang, Bo Han, Yang Liu, Min Xu, Gang Niu, and Tongliang Liu, Estimating despancedeeeendent bayes-label transition matrix using deep neural network. International Conference Machine Learning, pages 25302-25312. PMLR, 2022.
13

---

[51] Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual t: Reducing estimation error for transition matrix label-noise learning. Advances in neural information processing systems, 33:7260-7271, 2020.
[52] LIN Yong, Renjie Pi, Weizhong Zhang, Xiaobo Xia, Jiahui Gao, Xiao Zhou, Tongliang Liu, and Bo Han. A holistic view of label noise transition matrix in deep learning and beyond. In The Eleventh International Conference on Learning Representations. 2022.
[53] Sergey Zagoruyko and Nikos Komodakis. 1605. 2016.
Wide residual networks. arXiv preprint
[54] Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 34:18408-1848 18419, 2021.
[55] Yikai Zhang, Songzhu Zheng, Pengxiang Wu, Mayank Goswami, and Chao Chen. Learning with feature-dependent label noise: A progressive approach. In Ninth International Conference on Learning Representations, volume 9, 2021.
[56] Songzhu Zheng, Pengxiang Wu, Aman Goswami, Mayank Goswami, Dimitris Metaxas, and Chao Chen. Error-boundet correction of noisy labels. International Conference on Machine Learning, pages 11447-1 1457. PMLR, 2020.
14

---

A Comprehensive settings
For all methods, we apply temperature scaling for probability calibration by default, and the scaling factor is set 0.5, For FixMatch, Dash, FlexMatch and AdaMatch, is set 0.95. For UDA, is set as 0.8, temperature scaling factor is set as 0.4, according to the recommendation of the original paper. For Dash, y is set 1.27, C' is set 1.0001, p is 0.05, warm-up iteration is set as 5120 iterations. For Instan'T, base T is set as 0.9 by default.
B Tsybakov Margin Condition (Binary)
We present the binary case of Tsybakov Margin Condition here. can be defined as:
Assumption 2 (Binary Tsybakov Margin Condition). For some finite constant C, a 0, and 50 (0. 2. the Tsybakov Margin Condition holds 16 E (0, 80), we have
1 P P[M = m))
2 s C8
Through similar derivations, we can provide our main theorem in binary case:
Theorem 3. Assume estimated noisy class posterior P()1X) satisfies Assumption 2 with C, >> 0, 5n E (0, 1. and eg < 60 -To, we have:
P p k= (au,,, P( k|X xu) 2 r(zn)) 1- C[0ea))))
(12)
where 7 (Ix) is the instance-dependent threshold function under binary case:
YI
7 T(wx) Ta. = =|XX = aw + Σ
(aw() =i|X = vw).
(13)
C Proof of Theorem 1
Definition 3. For multi-class classification, the relationship between noisy class posterior P( and clean class posterior P(Y can be concluded as:
Y
p( = = =)) Σ =
= =i xxxx x).
(14)
Proof of Theorem 1
For simplicity, we will denote the clean class posterior P(Y = k| = x) as тΙ (z). noise class
posterior P(ý = X = ar) as 7/ (w), estimated noise class posterior P(L = k X = ax) as î (z)).
Proof.
P [k h² h²(xx) (x() 2 T(Zu)] = - P [K- h2 (~xx)) (x( < T(xx))
1 - P |m (x 2 no( 1 (xw) < T((Ew)
15

---

Based on Definition we can substitute mi (aa) with E Ti, (aa and since ll ig Tol S Eo (e-close); we can continue with:
$ 1 - P
(T 2 (x E Tú (2 < T(xu)) + Ea
T(xiu) Eipk Ti, (ar ( +
1 P
Mc (Tu) 2 (x(( mc (2())))
Th (I
17/ ( S ()((a))) T((x)
Ligh Ti (2x
c0
1 P
(
(x
1 (T S (TFu)) (a(u)))
60
Te,
Note that, since 60 S to min Te. (Io)), the Multi-class Tsybakov Condition can be applied here:
os mc(m)) (o(( < Tk, (xw)
60
S
60
Tk (w
Which gives us:
- P 0 0 (T (TOu Te,N
C0
Co (zu)
> -1-0 C
Hence proved [ h² (xn). (Ixn) 2 T(En)] C10(Ee)1"
D Proof of Theorem 2
In this section, provide the proof from Liu al. for the necessary and sufficient condition of the identification of instance-dependent transition matrix T(x). First, we provide the Kruskal's Identifiability Theorem (or Kruskal rank Theorem):
Theorem 4. The parameters M, i 1, .... ... are identifiable, up label permutation, if
p
(M.) 2
(15)
Proof. Then we follow the proof from Liu al. to first prove the sufficiency. Since we cannot observe the true label for unlabeled instances X,, we denote them as hidden variable Z for simplicity. P(Z i) is the prior for the latent label.
Each Y i, Vi ..., p corresponds the observation O, YY| is the cardinality of the pseudo-label space. Without loss of generality, we will fix the number of classes as three during the analysis.
Each y; corresponds to an observation matrix M,:
Mijj k| P(O, Z = 5) P( k/Y j, x))
Therefore, by definition of M1, M2, and T(x), they all equal to T(x): M, i 1,2, When T(x) has full rank, we know immediately that all rows in Mj, M2, M3 are independent. Therefore, the Kruskal ranks satisfy
(M1 (M2) = (Mg) = |
Checking the condition in Theorem
4 we easily verify
(M1) + (M2) + (Ma) = 3/ 2 2 +2
Where Theorem proves the sufficiency for three labeled samples per-class is sufficient for the identification of (x)
16

---

Subsequently, Liu er al. also provides the proof for necessity, without the loss of generality, the analysis for this part will be conducted in binary case only. More specifically, the label error generation in SSL can be described by binary transition matrix:
1 e (z) e+ (z)
(= 1 (a)
T(x:)
In order to prove necessity, we must show that less than three informative labels per-class will not give us unique solution for Tx)). If we were given two unlabeled instances with their pscudo-label Yi and Yg. Specifically, with unlabeled instance and pseudo-label pairs, conclude the following probabilities can derive all potential probabilities we can possibly get from them:
Posterior: P( +1|X)
Positive Consensus: P( = +
Negative Consensus: p() Y -
This is because other probability distributions are able to be derived from these three quantities:
P( -
P( =+
P(ý +1,8, 82 = - -| = P(- = +1|
= +1|x), P(K -1,82 = = P(Y: +1|x) P( = =+
But P(2: +1[X) P(" +)), since noisy labels are i.i.d. The above three quantities led to
three equations that depend on e This gives us the following system of equations:
P( = +1 = P(Y = +1) +1- = +1)) e
P( Y/2 = +1 = P(Y = +1) (1- P(Y = +1)) -
P( Y2 = - P(Y=+1)) (1- +1)) e_)
Where:
P( = Y2 = +1(X)
=P(ý = Y2 = +1, +1
+ 8 +1, -
=P( = Ý/ - -PY = ++|
+ P(Y = =
P(Y -|X)
=P(Y (1- P(Y +1)) .2
Given Y, P1 8g are conditional independent, which gives us:
P(ý = Y22 +1 +1,
P(ý = +1|Y +1,,X) = +1//Y = +1,X)
P(R: = Y, = +1 -1,
P(): = +1/Y -1,x) - -1
Conversely, for P(ý P - the derivation can follow similar procedure. We can now assert that C4, e_ are not identifiable. Where simple counter example can show that two sets of unique e_, e__ both satisfies above derivation:
P(Y +1) = 0.7, e+ = 0.2, e = 0.2
P(Y = +1) = 0.8, e4 0.242, e = 0.07
Which proves that two informative noisy labels are insufficient to identify T(xu).
17


Reviews:
[{"review_id": "YketsEa9LE", "reviewer": "Reviewer_1e9N", "summary": "- Assumption for instance-dependent threshold setting and theoretical proof based on it\n- Transition matrix modeling (estimator design) to reduce label error through instance-dependent threshold function\n- This paper shows good performance on various datasets (CIFAR10, 100, STL-10)", "questions": "1) The running time in Table 2 was 1s lower than Fix and AdaMatch. Do you have the result in terms of the amount of calculations and the number of parameters?\n2) If the reason for applying Distribution Alignment in InstanT-II in Table 3 is to eliminate class imbance, what is the reason why performance improves when DA is applied in ablation study? (The experimental environment in the paper appears to be a situation with low imbalance using the same number of labeled data for each class).\n3) Usually SSL papers show error rates of CIFAR10/100. How does the error rate come out?\n4) What about the results on larger sized images (e.g. ImageNet)?\n5) Papers on instance dependent pseudo-labeling already exist. Is there any difference from that? For example, the paper SimMatch: Semi-supervised Learning with Similarity Matching (2022 CVPR) also uses instance dependent similarity. This paper theoretically proves the validity of using instance-level threshold, but is there any excellence or novelty compared to the similarity method used in the above paper?\n6) The results of the comparative papers presented in the proposed paper and the results of the papers below are different. Is it an accurate comparison? Is there a reason why the second paper below is not included in the result table?\n- SimMatch: Semi-supervised Learning with Similarity Matching (2022 CVPR) \n- SOFTMATCH: ADDRESSING THE QUANTITY-QUALITY TRADE-OFF IN SEMI-SUPERVISED LEARNING (2023 ICLR)\n7) Please also respond to the weaknesses pointed out.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) A new approach in SSL called instance-dependent threshold setting\n2) Solid theoretical proof\n3) Excellent performance, especially in environments with little labeled data", "weaknesses": "1) Transition matrix modeling for threshold calculation for each instance is required (complexity is expected to increase).\n2) There is no consideration for class imbalance, which is mainly dealt with in SSL. If there is a class imbalance problem, it may not be a good idea to set different thresholds for each instance.\n3) Comparative papers (FlexMatch, Dash, AdaMatch, etc.) are papers published before 2022. Comparisons with recent papers have not been made. In addition, AdaMatch, which is mainly compared, is a paper dealing with domain adaptation issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 1e9N, we are grateful for your comprehensive review and the substantial range of questions you have raised.\n\n> **W1: Computational complexity**\n\nAs suggested in Table 2 of our paper, InstanT brings a minimal increase in terms of training time. Here we present you with more run-time analysis from other datasets, all speeds are measured with Nvidia RTX 4090 GPUs.\n\nPre-trained results with ViT:\n\n| Methods | CIFAR-10 | CIFAR-100 |\n| ------ | ------ | ------ |\n| FixMatch | 104.4 | 100.9 | \n| AdaMatch | 104.6 | 101.4 | \n| InstanT | 106.7 | 104.2 | \n\nTable 1-1: Seconds per-epoch during the training of each method.\n\nOverall, while the complexity of InstanT indeed increases, the training speed is not significantly impaired compared with other baseline methods. More importantly, we believe that the code can be further optimized and reduce the run-time.\n\n> **W2: Performance of InstanT when there exists class-imbalance**\n\nThank you for posing this concern when there exists class imbalance, InstanT is still expected to maintain a robust performance. We will address this from two perspectives: (1) Theoretical capabilities of InstanT with motivating examples; (2) Empirical performance of InstanT under imbalanced scenarios.\n\n - In the presence of class imbalance, this disparity typically manifests in the class posterior (prediction); InstanT is sensitive to the distribution and can leverage the labeled samples to probe such imbalanced class posterior, and attain an estimation to account for the probability of being misclassified. \n\n - Lastly, to fully address your concern, we also conducted comprehensive experiments on class-imbalance cases to empirically verify the performance of InstanT. All results are trained with Wide-ResNet-28-2 for $2^{18}$ iteration, following commonly used settings [4,5], we fix all methods with random seed {0}, imbalance ratio $\\gamma$ = {50,100,150}\n\n| Methods | $\\gamma$=50 | $\\gamma$=100  | $\\gamma$=150 |\n| ------ | ------ | ------ | ------ |\n| Dash | 0.7828 | 0.7077 | 0.6572 |\n| FlexMatch | 0.7977 | 0.7069 | 0.6433 |\n| AdaMatch | 0.7937 | 0.7278 | 0.6571 |\n| FreeMatch | 0.7971 | 0.7208 | 0.6354 |\n| InstanT | **0.7993** | **0.7346** | **0.6797** |\n\nTable 1-2: CIFAR-10, $N_1$=500, $M_1$=4000.\n\n| Methods | $\\gamma$=50 | $\\gamma$=100  | $\\gamma$=150 |\n| ------ | ------ | ------ | ------ |\n| Dash | 0.8118 | 0.7528 | 0.6940 |\n| FlexMatch | 0.8117 | 0.7445 | 0.6947 |\n| AdaMatch | 0.8198 | 0.7496 | 0.6969 |\n| FreeMatch | 0.8196 | 0.7543 | 0.7001 |\n| InstanT | **0.8216** | **0.7602** | **0.7116** |\n\nTable 1-3: CIFAR-10, $N_1$=1500, $M_1$=3000. \n\nThe above results verified our justification, under class-imbalanced scenarios, the instance-dependent threshold still exhibited outstanding performances compared with other baseline methods. As the class-imbalance ratio increases, we can observe a more significant advantage of InstanT. This corroborates our hypothesis - when classes are highly imbalanced, InstanT can indeed filter out substantial label errors and maintain a much more robust performance.\n\n> **W3: Lack of comparsion with recent methods & AdaMatch as a domain adapation method**\n\nDue to character limit, please find our response to this question at the General Response 1 at the top. \n\nIt's correct that AdaMatch can be used for Domain Adaptation (DA), but it's a SSL method as well. Due to the inherent similarity, DA is usually considered a highly relevant topic to SSL. That's why AdaMatch is named \"A Unified Approach to Semi-Supervised Learning and Domain Adaptation\".\n\n> **Q1: Number of operations and number of parameters**\n\nDue to the character limit, please find our response to this question in the general response section above.\n\n> **Q2: Purpose of Distribution Alignment in class-balance case**\n\nDistribution Alignment is not only useful when the initial labeled set is imbalanced. A more common issue in SSL is the self-generative class-imbalance, meaning during the process of psudeo-labeling, the error of classifiers will acculumate and eventually leading to the domainace of certain psudeo-label class. Distribution alignemnt is therefore employed to modulate the predictions made by the classifier and alleviates the issue of imbalanced pseudo-labels.\n\n> **Q3: Results in error rates**\n\nThe error rate is simply 1 - classification accuracy. \n\n> **Q4: Results on ImageNet**\n\nDue to the character limit, please find our response to this question at the General Response 2 at the top. \n\n> **Q5: Differences between SimMatch.**\n\n**SimMatch did not introduce instance-dependent threshold, it applies a fixed threshold to all samples.** It's core contribution lies in an enhanced form of consistency regularization, considering instance-level similarity. SimMatch essentially refines the application of consistency regularization to prevent overfitting. Whereas InstanT focus on devising a novel thresholding approach aimed at enhancing the filtration of label errors more efficiently. \n\n> **Q6: Reported results are different from the original papers, lack of coparsion with SoftMatch**\n\nThanks for the suggestion, we have added the comparsions with SoftMatch in the Table 0-1 an 0-2 of the General Response. \n\nThe discrepancy between the results from Table 1 and the original papers is because we have adapted a new trending setting in SSL [3], where we use pre-trained ViT as backbone instead of WRN training from scratch. This new setting is more computationally efficient, and all baseline methods have been tuned to their favorable hyper-parameters free from bias [3].\n\nWe also included results under conventional settings, those results can be found in the Appendix, as well as Table 0-1 from General Response 1. Where you will find that the results are overall consistent with the results reported in other papers.\n\nDue to character limits, please find the reference list at the end of General Response. "}, {"review_id": "k9SZZiYCuu", "reviewer": "Reviewer_zzrr", "summary": "This paper proposes a semi-supervised method with instance-dependent thresholds (InstanT), which can assign different thresholds to individual unlabeled data based on the instance-dependent label noise level and prediction confidence. Also, this paper provides a theoretical analysis of the proposed InstanT. Extensive experiments have shown the effectiveness of the proposed method.", "questions": "Please refer to the Weaknesses. ", "limitations": "The limitations of this paper should be discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper proposes an Instance-dependent Thresholding strategy for semi-supervised learning. Also, the proposed method can vouch for the reliability of pseudo-labels it assigns with a theoretical guarantee. \n\n2. This paper is easy to read and well organized.\n\n3. The experimental results and the proof of  Theorems in this paper seem to be solid.\n", "weaknesses": "1. This paper is devoted to addressing the SSL problem with dynamic thresholding. However, there is a lack of some SOTA methods to be compared with the proposed method. For example, \n[1] Guo et al., Class-imbalanced semi-supervised learning with adaptive thresholding, ICML, 2022. \n[2] Yang et al., Class-aware contrastive semi-supervised learning, CVPR, 2022.\n[3] Wang et al., Freematch: Self-adaptive thresholding for semi-supervised learning, ICLR, 2023. \n[4] Chen et al., Softmatch: Addressing the quantity-quality trade-off in semi-supervised learning, ICLR, 2023.\n\n2. Most previous SSL methods have reported their performance on both datasets: SVHN and ImageNet. It is therefore suggested that the authors supplement some experiments to evaluate the generalization performance of the proposed method. \n\n3. It is suggested to omit some symbols whose meanings have been explained in the previous context, so as to increase the brevity of this paper.\n\n4. The proposed method is motivated by the learning with noisy labels. Therefore, it is necessary to review some related methods to give readers a whole picture. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your invaluable feedbacks and suggestions, all of which will significantly contribute to the enhancement of our work. Please find our response addressing your concerns:\n\n>  W1: Lack of comparsion with SOTA (FreeMatch, SoftMatch etc.)\n\nThank you for raising this question, we have conducted comprehensive evaluations against the two most recent SOTA methods - FreeMatch [1] and SoftMatch [2], as you suggested.\n\nFirst, we present the results under conventional settings [1,2], where all results are trained from scratch with WRN28-2, we fix all methods with random seed \"0\".\n\n| Methods | CIFAR-10(10) | CIFAR-10(40) | CIFAR-10(250) | CIFAR-100(400) | CIFAR-100(2500) |\n| ------ | ------ | ------ | ------ | ------ | ------ |\n| SoftMatch | 0.7557 | 0.9464 | 0.9517 | 0.5057 | 0.6622 |\n| FreeMatch | 0.9193 | **0.9512** | 0.9506 | 0.4920 | 0.6659 |\n| InstanT | **0.9250** | 0.9510 | **0.9525** | **0.5217** | **0.6709** |\n\nTable 2-1\n\nUnder conventional settings, we can observe that InstanT showcases strong performance against SOTA baselines, especially on the most challenging cases,e.g. CIFAR-10(10) and CIFAR-100(400), indicating when there exist large label errors, InstanT can more effectively filter them out. \n\nWe also present the results with pre-trained ViT, settings are aligned with Table 1 from our paper.\n\n| Methods | CIFAR-10(10) | CIFAR-10(40) | CIFAR-10(250) |  CIFAR-100(200) | CIFAR-100(400) | STL-10(10) | STL-10(40) |\n| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |\n| SoftMatch | 0.8003±0.09 | 0.9795±0.01 | 0.9814±0.00 | 0.7057±0.01 | 0.7821±0.01 | 0.6510±0.09 | 0.8370±0.04 |\n| FreeMatch | 0.7721±0.05 | **0.9811±0.00** | **0.9819±0.00** |  **0.7629±0.02** | **0.7938±0.00** |  0.6230±0.14 | 0.8496±0.03 |\n| InstanT | **0.8732±0.10** | 0.9793±0.00 | 0.9808±0.01 | 0.7417±0.00 | 0.7880±0.00 | **0.6939±0.07** | **0.8509±0.03** |\n\nTable 2-2\n\nFrom Table 2-2, we can observe that, while InstanT obtained the best results in 3 out of 7 cases, it's average improvement is much more significant than FreeMatch, and for cases where its performance is worse, the gaps are relatively marginal.\n\n> **W2: Lack of results on SVHN and ImageNet.**\n\nThank you for raising this concern, we have added more experiments on ImageNet-100, with 100 labeled samples per-class, to evaluate our method against selected SOTA baselines. All results are obtained using  a ResNet-50 trained for 500,000 iterations, with random seed {0}.\n\n| Methods | Top-1 Acc. | F-1 Score |\n| ------ | ------ | ------ | \n| FixMatch | 0.6624 | 0.6559 |\n| AdaMatch | 0.6860 | 0.6822 |\n| FreeMatch | 0.6578 | 0.6529 |\n| InstanT | **0.6994** | **0.6972** |\n\nTable 2-3\n\nAs we can observe from Table 2-3, InstanT shows strong generalization capability and scalability on large benchmarks such as ImageNet-100, surpassing a range of SOTA baseline methods. \n\nAs for the SVHN dataset, since it is considered a \"simpler\" case, running InstanT on SVHN cannot effectively differentiate it from other methods. Therefore, given limited time and computational resources, we forfeit to display the results here. Alternatively, if the reviewer still deems it necessary, we could also showcase these results during the rolling discussion phase.\n\n > **W3: Omit previously defined symbols.**\n\nWe thank the reviewer for posing this feedback. Indeed, for brevity, we will avoid over-defining symbols in the official version of our paper.\n\n> **W4: Lack of review for label noise papers.**\n\nHere we will give a concise overview of the relevant label noise learning papers, a more comprehensive review will be added to the main paper at a later stage.\n\nThe most relevant line of work is the modeling of label noise. The pioneering work introduced the concept of learning with class-dependent label noise, which has been widely recognized [3,4,5]. Noteworthy strategies in this area include anchor-point estimation [6], end-to-end estimation [7], mixture proportion estimation [3], etc.\n\nMeanwhile, another line of research has concentrated on tackling instance-dependent label noise [8], which reflects a more realistic scenario. In this regard, notable works include the part-dependent anchor-points [9] and modeling through DNNs [10].\n\nOnce again, we would like to thank the reviewer for spending your valuable time reviewing our paper, and we welcome any new questions & suggestions the reviewer might have after rebuttal.\n\n - [1] Wang, Yidong, et al. \"Freematch: Self-adaptive thresholding for semi-supervised learning.\" arXiv preprint arXiv:2205.07246 (2022).\n - [2] Chen, Hao, et al. \"Softmatch: Addressing the quantity-quality trade-off in semi-supervised learning.\" arXiv preprint arXiv:2301.10921 (2023).\n - [3] Scott, Clayton, Gilles Blanchard, and Gregory Handy. \"Classification with asymmetric label noise: Consistency and maximal denoising.\" Conference on learning theory. PMLR, 2013.\n - [4] Natarajan, Nagarajan, et al. \"Learning with noisy labels.\" Advances in neural information processing systems 26 (2013).\n - [5] Patrini, Giorgio, et al. \"Making deep neural networks robust to label noise: A loss correction approach.\" Proceedings of the IEEE conference on computer vision and pattern recognition. 2017.\n - [6] Liu, Tongliang, and Dacheng Tao. \"Classification with noisy labels by importance reweighting.\" IEEE Transactions on pattern analysis and machine intelligence 38.3 (2015): 447-461.\n - [7] Li, Xuefeng, et al. \"Provably end-to-end label-noise learning without anchor points.\" International conference on machine learning. PMLR, 2021.\n - [8] Cheng, Jiacheng, et al. \"Learning with bounded instance and label-dependent label noise.\" International conference on machine learning. PMLR, 2020.\n - [9] Xia, Xiaobo, et al. \"Part-dependent label noise: Towards instance-dependent label noise.\" Advances in Neural Information Processing Systems 33 (2020): 7597-7610.\n - [10] Yang, Shuo, et al. \"Estimating instance-dependent label-noise transition matrix using dnns.\" (2021)."}, {"review_id": "0Gucnn2Sgq", "reviewer": "Reviewer_Cia8", "summary": "This paper presents a new approach for selecting confident examples called InstanT, which uses instance-dependent thresholds for assigning pseudo-labels to unlabeled data. Unlike existing methods that apply the same threshold to all samples, InstanT considers the instance-level ambiguity and error rates of pseudo-labels, assigning higher thresholds to instances more likely to have incorrect pseudo-labels. The paper demonstrates that this approach provides a probabilistic guarantee for the correctness of the assigned pseudo-labels. This innovative method may offer a new perspective on SSL.", "questions": "1.What might be the potential drawbacks or limitations of this method? How could these impact its applicability or performance in certain scenarios or with certain types of data?\n\n2.The experimental evaluation of the method is based on only three datasets. Could the authors explain their choice of datasets and how representative these datasets are of the types of data the method would encounter in real-world applications? Would the performance of the method vary significantly if tested on other datasets? \n\n3.The authors may need to clarify the relationship between the Quality-Quantity Trade-off and the effective dynamic value. How do these two factors interact within the context of their proposed method?\n\n4.The paper discusses the balance between the quality and quantity of pseudo-labels. Could the authors provide some intuition of how this balance can be achieved in practice?\n\n5.This paper is highly related to the problem of learning with instance-dependent label noise. To clearly demonstrate the effectiveness, can authors provide a comparison with methods for handling instance-dependent label noise?", "limitations": "The main paper seems to lack a comprehensive discussion on the limitations of the proposed method. It would be beneficial for the authors to conduct a thorough review of their method to identify any potential limitations. I suggest including a separate section in the main paper dedicated to discussing these limitations, which would provide a more balanced and complete perspective of the proposed method.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper finds a significant and challenging problem in semi-supervised learning (SSL) that has not been adequately tackled by existing methods. Traditional SSL methods typically use a single loss threshold to select confident examples, implicitly assuming that examples with the same loss have the same likelihood of pseudo-label correctness. However, this assumption does not always hold, as there can be hard but confident examples that have larger loss values but correct pseudo-labels. \n\n2.The innovation of this paper is noteworthy. This paper innovatively proposes to estimate the probability of examples being incorrect and applies instance-dependent thresholds based on these estimates. This approach is more nuanced and potentially more effective as it takes into account the individual characteristics of each example. It is the first to propose the estimation of instance-dependent thresholds in SSL. This novel approach represents could open up new avenues for research in the field. \n\n3.The authors also provide sufficient theoretical analysis about their proposed method. They present a theorem that shows that for samples that satisfy their instance-dependent threshold function, the likelihood of the pseudo-labels being correct is lower-bounded. This provides a solid foundation for the proposed method and helps to convince readers of its assumption and correctness.", "weaknesses": "1.Certain aspects of the paper could benefit from further explanation and clarification. Specifically, the relationship between the Quality-Quantity Trade-off and the effective dynamic value is not clearly articulated in the main body of the paper. These are key components of the proposed method, and their interaction could significantly impact the performance of the method.\n\n2.The paper does not sufficiently discuss the limitations of the proposed method. Every method has its limitations and potential drawbacks, and a thorough discussion of these is crucial for a balanced and comprehensive presentation of the work. \n\n3.The empirical improvement of the proposed method is marginal when the amount of labeled data increases. This suggests that the method's performance may not scale well with larger labeled datasets.\n\n4.The experimental evaluation of the method is based on only three datasets. This limited number of datasets may not provide a comprehensive evaluation of the method's performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging our contributions and posing a wide range of valuable questions & suggestions, all of which have been very inspiring to us. We sincerely hope that our response can address your questions and concerns:\n\n> **W1 & Q3: Relationship between Quality-Quantity trade-off and efficitive dynamic thresholds.**\n\nWe apologize for the lack of clarity in our main paper, and you're absolutely correct; this concept holds significant importance. Let's begin by considering the correlation between dynamic thresholds and the quality-quantity trade-off. Dynamic thresholds have now emerged as the primary solution for quality-quantity trade-off. In the initial training stages, an excessively high fixed threshold leads to an excessive filtration of samples, thereby compromising quantity. Conversely, during the later training stages, a fixed threshold set too low fails to effectively filter any samples, thereby compromising quality.\n\nIn addition, to better understand and set restraint on the dynamic threshold, we define an \"effective dynamic threshold\" (Assumption 2), whose left-hand side can be viewed as the gain of the quality of the pseudo-label after introducing $\\kappa$, and the right-hand side can be view as the loss of the quantity of the pseudo-label after introducing $\\kappa$. So we're assuming that, with an effective dynamic threshold, we expect the increase in the quality of the pseudo-label must at least match the loss of the quantity of the pseudo-label. \n\n> **W2 & Q1: Didn't discuss the limition of InstanT & When InstanT could fail.**\n\nThank you for this constructive suggestion, here we will discuss some of the potential limitations of InstanT, and we will include them in the official version of our paper. \n\n - When there is minimal label error generated by the classifier, InstanT has no significant differences with other SSL methods. The instance-dependent thresholds generated by InstanT becomes trivial simply and reduce to $\\kappa$.\n - InstanT is subjective to the influence of transition matrix estimation, if, for some reason, the estimation of the transition matrix is extremely poor, this could potentially hinder the thresholding of InstanT.\n\nTherefore, InstanT could potentially obtain no significant improvements on simpler datasets and with abundant labeled sets, for instance, on the SVHN dataset, or on the CIFAR-10 dataset with abundant labeled samples. \n\n> **W3: Performance of InstanT on larger labeled datasets.**\n\nThank you for raising this concern, this has been a commonly mentioned issue. We would like to point out that, since learning on larger labeled datasets is relatively easy, the performance limit on larger labeled datasets has almost been fully exploited, and converged towards the fully-supervised results. This means the performance gap will almost always be marginal on larger labeled datasets, similar results are verified in recent SSL papers as well [1,2]. \n\n> **W4 & Q2: Number of datasets is limited.**\n\nThank you for the suggestion, the datasets we selected are the most commonly used benchmarks in SSL with an adequate level of challengingness, all of which are widely acknowledged datasets to simulate real-world problems. In addition, to fully address your concern, we also conduct experiments on ImageNet-100, with 100 labeled samples per class, to evaluate our method. All results are obtained from a ResNet-50 train from scratch for 500,000 iterations on ImageNet-100 using random seed {0}.\n\n| Methods | Top-1 Accuracy | F-1 Score |\n| ------ | ------ | ------ | \n| FixMatch | 0.6624 | 0.6559 |\n| AdaMatch | 0.6860 | 0.6822 |\n| FreeMatch | 0.6578 | 0.6529 |\n| InstanT | **0.6994** | **0.6972** |\n\nTable 3-1\n\nAs suggested in Table 3-1, InstanT also showcases strong performances on large-scale real-world datasets such as ImageNet. \n\n> **Q4: Intuition on how InstanT better balances between quantity-quality trade-off.**\n\nBasically, existing methods attempt to find a better balance between quantity and quality trade-offs by assigning dynamic thresholds that are dependent on the training progress. InstanT further improves this concept by utilizing the simple intuition that \"some unlabeled samples are more likely to have incorrect pseudo-labels than others\". Once we can determine the probability of which sample is more likely to have an incorrect pseudo-label, InstanT will adjust its label assignment threshold based on such likelihood, hence increasing the threshold level for samples with a larger noisy probability.\n\n> **Q5: Comparsion on methods handling instance-dependent label noise.**\n\nHere we will try to implement PTD [3] to test its performance in SSL. Our implementation strategy is for PTD to leverage labeled samples as anchor points to learn the transition matrix. We also apply two different settings for a fair comparison, where PTD will adapt fixed and dynamic thresholds to choose pseudo-label (noisy label) respectively. The version where PTD uses a dynamic threshold will be referred to as PTD(DT). Since PTD requires the number of anchor points to be larger than $C\\times M$, where $C$ is the number of classes and $M$ is the number of parts (hyper-para), labels per class must be larger, hence we only evaluate on CIFAR-10(250). \n\n| Methods | CIFAR-10(250) |\n| ------ | ------ |\n| PTD | 0.9723±0.04 | \n| PTD(DT) | 0.9711±0.01 | \n| InstanT | **0.9808±0.00** |\n\nFrom the results, we can observe that PTD also achieves good results, but cannot be used for cases when the number of labels per class is limited. The main difference between PTD(DT) and InstanT is their thresholding method, the better performance of InstanT further verifies the effectiveness of the instance-dependent thresholds.\n\nFull reference info will be omit due to character limit\n\n[1] Freematch: Self-adaptive thresholding for semi-supervised learning\n\n[2] Softmatch: Addressing the quantity-quality trade-off in semi-supervised learning\n\n[3] Part-dependent label noise: Towards instance-dependent label noise"}, {"review_id": "wlypd6uqL2", "reviewer": "Reviewer_kWe6", "summary": "This paper focuses on semi-supervised learning (SSL) and proposes the study of instance-dependent thresholds to make incorrect pseudo-labels have higher thresholds.", "questions": "As mentioned in the part of weaknesses, the authors may make a mistake in Theorem 2, which makes that the paper is not convincing. The theoretical analysis part of the paper should be considered more seriously.\nThe dynamic threshold is determined by the transition matrix T(x). But in practice it is impossible to estimate it without any bias. The bias may influence on the final result. Is it possible to provide an error bound in the analysis?\n", "limitations": "No", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper studies an important problem in SSL, and tries to propose a dynamic and adaptive threshold to guarantee the pseudo-label quality for instances. Also, it gives a theoretical analysis on estimating the threshold. The experiments are sufficient and the results surpasses SOTA. In the results, it is obvious to see that the algorithm has a considerable improvement in Top-1 accuracy. The ablation study shows that every part of this algorithm is useful.", "weaknesses": "Theorem 2 is proved with Bayes rule with Assumption 2. But if the dynamic value k_t > 0, Theorem 2 does not hold. It is incorrect P(X>=a+b)>=P(X>=a) for any b>0. I think there may be some mistakes in Assumption 2 and Theorem 2. The theorems and analyses based on Assumption 2 may be wrong.\nIn section 4.1 the authors do not give any theoretical reasons for the definition of k_t and \\tau(x_u). Whether k_t satisfies Assumption 2 or not? \nIn Equation 8, the authors use an approximation \\hat{T}(x) to estimate T(x). But the analysis is based on the real value of T(x). If the label noise is large or the number of samples is not enough, the error between the real value of T(x) and the approximation \\hat{T}(x) cannot be ignored. Some analysis should be provided here.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully going over our proof and pose challenges to them, we strongly agree that the theoritical part of the paper should be rigorous, and believe that your questions and suggestions will further refine our paper.\n\n > **W1: Proof regarding to Theorem 2.**\n\nFor simplicity, let's denote event $k=h^{*}(\\bf{x_u})$ as event A, $\\hat{P}(\\hat{Y}=k|X=\\bf{x_u}) \\geq \\tau$ as event B, $\\hat{P}(\\hat{Y}=k|X=\\bf{x_u}) \\geq \\tau + \\kappa$ as event C, without the loss of generality, iteration $t$ will be omitted.\n\nFirst of all, you're correct, for any $\\kappa \\geq 0$, $P(B) \\geq P(C)$ holds. However, the relationship between the joint proability of $P(A,B)$ and $P(A,C)$ are not known, since event A,B,C are not independent. Therefore, we must first decompose them into conditional probabilities and making assumptions on their relationship (Assumption 2).\n\nTo understand Assumption 2 with a concrete example, consider this SSL dataset with total of 1000 unlabeled samples. With a non-dynamic fixed threshold $\\tau$, the prediction confidence of all unlabeled samples surpass this threshold, P(B) = 1, only 500 of samples are assigned with correct thresholds, P(A|B) = 0.5. If we increase the threshold with some non-zero constant $\\kappa$, now only 600 samples surpass this threshold, and among them, there is still 500 samples assigned with correct threshold, P(C) = 0.6, P(A|C) = 5/6. Note P(A,B) = 0.5, and P(A,C) = 0.5 as well, which satisfies Assumption 2.\n\nNevertheless, we are also putting Assumption 2 under the microscope, examining its rigor and necessity, it's possible that we might need to modify Assumption 2 and make more rigorous justifications. \n\n> **W2: Does $\\kappa_t$ in section 4.1 satisfies Assumption 2?**\n\nThanks for pointing this question out. $\\kappa_t$ is assumed to satisfy Assumption 2 throughout the paper, we will explicitly clarify this point in the final version of the paper.\n\n> **W3: Didn't account the estimation error of $T(x)$**\n\nThank you for this highly constructive suggestion. We have improved our proof and including the estimation error of $T(x)$. Our improved proof can be found in the submitted pdf file in the genral response at the top. \n\nAs for the estimation error bound of $T(x)$, it has been extensively studied and is been continuously improved, recent paper indicting even with a small number of samples, the estimation error can still be managed to reduce to a small level. Lastly, and more importantly, emprical results on challenging cases (where the estimation error of $T(x)$ is larger), still suggests our method can obtain a more robust performance than SOTA baselines. \n\nFurthermore, we wish to underscore our central contribution, which lies in the introduction and estimation of instance-level label errors. This forms the foundation for deriving instance-dependent thresholds in SSL. We view our work as an initial exploration into the possibility of instance-dependent thresholds in SSL.\n\nOnce again, we would like to express our appreciation to the reviewer for carefully checking our proof and results. We welcome any new questions & suggestions you might still holds after the rebuttal."}, {"review_id": "zbiMCYAiH4", "reviewer": "Reviewer_4nX9", "summary": "This paper introduces a new thresholding methodology for Semi-Suervised Learning. This paper proposes InstanT, which uses an instance-dependent threshold for each unlabeled data (Fig1). This algorithm shows the improvement on multiple semi-supervised benchmark datasets.", "questions": "Please see the weaknesses.", "limitations": "Please see the weaknesses.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Pros. \n- This paper is well-written and easy to follow.\n- This paper is well-motivated (Fig 1).\n- This paper proposes InstanT, and it is very well derived.\n- This paper shows extensive experiments (Especially it seems to train all other semi-supervised learning baselines using ViT models) and shows the effectiveness of this method.", "weaknesses": "Cons.\n- (Minor) This paper uses a pre-trained ViT model. In pre-training, I think the classes in Cifar10/Cifar100 could be the subset of the pre-training dataset. If These classes are already trained, they could be already well clustered and easy to train with a very small labeled dataset. (It also shows the performance improvement in the original training setting in the Appendix)\n\n- (Minor) It would be great if it reports the supervised learning results (full labeled dataset)\n\n- (Major) This paper evaluates their algorithm in very small datasets (Cifar10/Cifar100/STL-10). Therefore, I don't know how it robustly works in large datasets such as ImageNet. Nowadays, most of the papers evaluate their algorithms on ImageNet. (In this case, it seems to train the model from scratch. (not using pre-trained ViT model)  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging our contributions. We are grateful for your constructive feedbacks and positive remarks about our work. We hope we can address you questions and concerns:\n\n> **W1: Are the classes from CIFAR10/100 a subset of pre-trained dataset?**\n\nThank you for this very insightful concern, the pre-trained dataset is ImageNet-1k, and there indeed are some class overlaps between CIFAR-100 and ImageNet-1k. However, we would like to raise several points proving our results are indeed convincing:\n\n - the distribution of features are still notably different (different reslution level, different feature space) between CIFAR and ImageNet;\n\n - even though the pre-trained ViT might have some prior knowledge to CIFAR10/100, this does not harm using pre-trained ViT as the backbone model. Because all the baseline methods are running on the same backbone, and the fact that InstanT can still obtain better performances showcase its improvement is valid and non-trivial; \n\n - lastly, as you mentioned, we can also observe performance improvements on train-from-scratch cases in the Appendix. We also supplement you with some our newest results comparing with newly added baselines when train from scratch:\n\n| Methods | CIFAR-10(10) | CIFAR-10(40) | CIFAR-10(250) | CIFAR-100(400) | CIFAR-100(2500) |\n| ------ | ------ | ------ | ------ | ------ | ------ |\n| SoftMatch | 0.7557 | 0.9464 | 0.9517 | 0.5057 | 0.6622 |\n| FreeMatch | 0.9193 | **0.9512** | 0.9506 | 0.4920 | 0.6659 |\n| InstanT | **0.9250** | 0.9510 | **0.9525** | **0.5217** | **0.6709** |\n\nTable 5-1\n\nBased on the above justifications, we hope you find our evaluations to be sensible and our improvements are significant.\n\n> **W2: Did not include fully-supervised results.**\n\nThank you for this valuable suggestion, we have supplement the sully-supervised results and will update them into our paper, we also present them here to address your concern:\n\npre-trained ViT results, settings are aligned with Table 1 of the paper.\n\n| CIFAR-10 | CIFAR-100 | STL-10 |\n| ------ | ------ | ------ |\n| 0.991 ±0.00 | 0.9152 ±0.00 | 0.8100 ±0.03 |\n\nTable 5-2\n\nWe can observe that STL-10 exhibts results that are worse than SSL baselines, this is bacause unlike CIFAR datasets, the vast majority of STL-10 do not come with groun-truth labels, so fully-supervised models trained on STL-10 can only access to a small proportion of labels. \n\n**> W3: Did not include large-scale datasets.**\n\nPer your suggestion, we have implemented experiments on ImageNet-100. And, as you have pointed out, we did not use pre-trained ViT, since that will be ill-posed. Results are trained form scratch with a ResNet-50 for 500,000 iterations on ImageNet-100 using random seed {0}.\n\n| Methods | Top-1 Accuracy | F-1 Score |\n| ------ | ------ | ------ | \n| FixMatch | 0.6624 | 0.6559 |\n| AdaMatch | 0.6860 | 0.6822 |\n| FreeMatch | 0.6578 | 0.6529 |\n| InstanT | **0.6994** | **0.6972** |\n\nTable 5-3\n\nFrom Table 5-3, we can observe that InstanT maintains a robust performance on real-world large-scale datasets, surpassing several SOTA baselines. We will supplement the more comprehensive results of this experiment with the main paper. \n\nOnce again, we would like to thank the reviewer for your positive remarks and spending your valuable time reviewing our paper, we welcome any new questions & suggestions the reviewer might have after rebuttal.\n"}]

Author rebuttal:
Dear reviewers, please find our general responses to some of the commonly asked questions, due to character limits in some of the individual rebuttal, we kindly refer you to see our response here:

> **GA1: Comparsions with more recent baselines**

We have included the comparsions with two recent baselines, FreeMatch (ICLR'23) and SoftMatch (ICLR'23). First, we present the results under conventional settings [1,2], where all results are trained from the scratch with WRN28-2, we fix all methods with random seed "0".

| Methods | CIFAR-10(10) | CIFAR-10(40) | CIFAR-10(250) | CIFAR-100(400) | CIFAR-100(2500) |
| ------ | ------ | ------ | ------ | ------ | ------ |
| SoftMatch | 0.7557 | 0.9464 | 0.9517 | 0.5057 | 0.6622 |
| FreeMatch | 0.9193 | **0.9512** | 0.9506 | 0.4920 | 0.6659 |
| InstanT | **0.9250** | 0.9510 | **0.9525** | **0.5217** | **0.6709** |

Table 0-1

Under conventional settings, we can observe that InstanT showcases strong performance against SOTA baselines, especially on hard cases (e.g. CIFAR-10(10) and CIFAR-100(400)), indicating when there exists large label errors, InstanT can more efficitively filter them out. 

We also present the results from pre-trained ViT, settings are aligned with Table 1 from our paper.

pre-trained results
| Methods | CIFAR-10(10) | CIFAR-10(40) | CIFAR-10(250) |  CIFAR-100(200) | CIFAR-100(400) | STL-10(10) | STL-10(40) |
| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
| SoftMatch | 0.8003±0.09 | 0.9795±0.01 | 0.9814±0.00 | 0.7057±0.01 | 0.7821±0.01 | 0.6510±0.09 | 0.8370±0.04 |
| FreeMatch | 0.7721±0.05 | **0.9811±0.00** | **0.9819±0.00** |  **0.7629±0.02** | **0.7938±0.00** | 0.6230±0.14 | 0.8496±0.03 |
| InstanT | **0.8732±0.10** | 0.9793±0.00 | 0.9808±0.01 | 0.7417±0.00 | 0.7880±0.00 | **0.6939±0.07** | **0.8509±0.03** |

Table 0-2

From Table 0-2, it is evident that eventhough InstanT only achieved the highest scores in 3 out of 7 cases, its average enhancement is considerably more pronounced than that of FreeMatch. Furthermore, in situations where InstanT's performance shows a decline, the gaps are relatively marginal.

> **GA2: Experiments on large-scale datasets (ImageNet)**

We have added the experiments on ImageNet-100, with 100 labeled samples per-class, to evaluate our method against selected baseline methods. All results are obtained with a ResNet-50 trained for 500,000 iterations, with random seed {0}.

| Methods | Top-1 Accuracy | F-1 Score |
| ------ | ------ | ------ | 
| FixMatch | 0.6624 | 0.6559 |
| AdaMatch | 0.6860 | 0.6822 |
| FreeMatch | 0.6578 | 0.6529 |
| InstanT | **0.6994** | **0.6972** |

Table 0-3

As we can observe from Table 0-3, InstanT showcases strong performances on large-scale real-world datasets as well.

References:

- [1] Freematch: Self-adaptive thresholding for semi-supervised learning
- [2] Softmatch: Addressing the quantity-quality trade-off in semi-supervised learning
- [3] Usb: A unified semi-supervised learning benchmark for classification
- [4] Class-imbalanced semi-supervised learning with adaptive thresholding
- [5] Crest: A class-rebalancing self-training framework for imbalanced semi-supervised learning

Meta-review: This work investigates the instance-dependent thresholds for semi-supervised learning. It is conducted in a principled manner and the experimental study demonstrates its potential. Reviewers raised a number of issues on this work. The authors provided feedback and this helped to address the concerns. After the author-reviewer discussion phase, all scores converge to leaning to accept this work. AC also read the submission, review and response and discussed this work with SAC. In conclusion, this work has its value and significance in addressing the instance-dependent thresholding issue by taking a theoretical perspective. The overall quality of this work meets the requirement of this conference. Acceptance is therefore recommended. Meanwhile, this work needs to adequately consider the review comments when preparing the final version of this submission. In particular, this work shall improve the clarity at multiple places, especially those related to theoretical analysis, and more rigorously present Assumption 2.
Decision: Accept (poster)