Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Authors: Rudrajit Das
Inderjit S Dhillon
Alessandro Epasto
Adel Javanmard
Jieming Mao
Vahab Mirrokni
Sujay Sanghavi
Peilin Zhong
Venue: ICML 2025 poster (2025)
Keywords: Retraining
Predicted Labels
Hard Labels
Label Noise
Label DP
Primary area: theory->learning_theory
TL;DR: We theoretically show that retraining a model with its predicted hard labels can improve its accuracy when the given labels are noisy, and empirically demonstrate that retraining significantly improves label DP training at no extra privacy cost.

Abstract: The performance of a model trained with noisy labels is often improved by simply *retraining* the model with its *own predicted hard labels* (i.e., $1$/$0$ labels). Yet, a detailed theoretical characterization of this phenomenon is lacking. In this paper, we theoretically analyze retraining in a linearly separable binary classification setting with randomly corrupted labels given to us and prove that retraining can improve the population accuracy obtained by initially training with the given (noisy) labels. To the best of our knowledge, this is the first such theoretical result. Retraining finds application in improving training with local label differential privacy (DP), which involves training with noisy labels. We empirically show that retraining selectively on the samples for which the predicted label matches the given label significantly improves label DP training at no extra privacy cost; we call this consensus-based retraining. For example, when training ResNet-18 on CIFAR-100 with $\epsilon=3$ label DP, we obtain more than $6$% improvement in accuracy with consensus-based retraining.

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Rudrajit Das"
Inderjit S Dhillon 23 Alessandro Epasto
Adel Javanmard Peilin Zhong'
Jieming Mao Vahab Mirrokni
Sujay Sanghavi
Abstract
discriminative model M (for classification problem) on dataset of samples and noisy label pairs {(2;, My J==
The performance of model trained with noisy labels is often improved by simply reiraining the model with its own predicted hard labels (i.c., 1/0 labels). Yet, a detailed theoretical character- ization of this phenomenon is lacking. In this paper, we theoretically analyze retraining early separable binary classification setting with randomly corrupted labels given to and prove that retraining can improve the population accu- racy obtained by initially training with the given (noisy) labels. To the best of our knowledge, this is the first such theoretical result. Retraining finds application in improving training with local label differential privacy (DP), which involves training with noisy labels. We empirically show that re- training selectively on the samples for which the predicted label matches the given label signifi- cantly improves label DP training at no extra pri- vacy cost; we call this consensus-basee retraining. For example, when training ResNet- 18 on CIFAR- 100 with label DP, we obtain more than 6% improvement in accuracy with consensus-based retraining.
Let 0, be the final learned weight/checkpoint of M and let Dj (M,,, xf) be the current checkpoint's predicted hard label for sample zy. Now, we propose to retrain M with the Ty 's in one of the following two ways:
lin-
(1) Full retraining: Retrain M with {(T), T } i.c. retrain M with the predicted labels of all the samples.
(ii) Consensus-based retraining: Define Scons == {i e nI....,n) j = Tj} to be the set of samples for which the predicted label matches the given noisy la- bel; we call this the consensus set. Retrain M with { {(x My )) jas... i.e., retrain M with the predicted la- bels of only the consensus set.
Intuitively, retraining with predicted hard labels can be bene- ficial when the underlying classes are "well-separated" In such a case, the model can potentially correctly predict the labels of many samples in the training set far away from the decision boundary which were originally incorrectly labeled and presented to it. As result, the model's accuracy (w.r.. the actual labels) on the training data can be significantly higher than the accuracy of the noisy labels presented to it. Hence, retraining with predicted labels can potentially improve the model's 's performance. This intuition is illus- trated in Figure where we consider a separable binary classification problem with noisy labels. The exact details are in Appendix A but importantly, Figures la and 1b corre- spond to versions of this problem with "large" and "small" separation, respectively. Please see the figure caption for de- tailed discussion but in summary, Figure shows us that the success of retraining depends on the degree of separation between the classes.
Introduction
We study the simple idea of retraining an already trained model with its own predicted hard labels (i.e., 1/0 labels and not the raw probabilities) when the given labels with which the model is initially trained are noisy. This is sim- ple yet effective way to boost model's performance in the presence of noisy labels. More formally, suppose we train a
Work done while Rudrajit was PhD student at the Univer- sity of Texas at Austin and student researcher at Google Re- search. Google Research "Google *University of Texas at Austin "University of Southern California. Correspondence to: Rudrajit Das <dasrudrajit@ @ crcejit@ggogll.coom goog, Alessandro Epasto <aepasto @ospasto@googge...o google.com>....... Adel Javanmard <ajavanma @ usc.edu>.
The motivation for consensus-bused retraining is that match- ing the predicted and given labels can potentially yield a smaller but much more accurate subset compared to the entire set; such a filtering effect can further improve the model's performance. As we show in Section 5 (see Tables 3 and 11), this intuition bears out in practice.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
There are plenty of ideas revolving around training a model with its own predictions, the two most common ones being

---

results show Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Given Labels
Given Labels
-2-
-1.5
1.5
Predicted Labels
Predicted Labels
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
(a) Large separation: predicted labels pretty accurate.
(b) Small separation:
predicted labels not as accurate.
Figure 1. Retraining Intuition. Samples to the right (respectively, left) of the separator (black vertical line in the middle) and colored blue (respectively, red) have actual label 1 (respectively, -1). For both classes, incorrectly labeled samples are marked by crosses (x). whereas the correctly labeled samples are marked by dots (o) of the appropriate color. The amount of label noise and the number of training samples are the same la and lb. The top and bottom plots show the joint scatter plot the training samples with the (noisy) labels given us and the labels predicted by the model after training with the given labels, respectively. Notice that in 1a, the model correctly predicts
labels of several samples that were given to with wrong label - especially, those that are far away from the separator. This is not quite the case in 1b. This difference gets reflected in the performance on the test after retraining. Specifically, in a, rerraining increases the test accuracy to 97. 97.67% from 89%. However, retraining yields no improvement in 1b. So the success of retraining depends on the inter-class separation; in particular, retraining is beneficial when the classes are well-separated.
from
self-training (Scudder, 1965; Yarowsky, 1995; Lee al., 2013) and self-distillation (Furlanello et al., 2018; Mobahi et al., 2020); we discuss these and important differences from retraining in Section 2. However, from theoretical perspective, we are not aware of any work proving that retraining a model with its predicted hard labels can be beneficial the presence of label noise in any setting. Section we derive the first theoretical result (to our knowledge) showing that full retraining with hard labels improves model accuracy.
its application especially with consensus- based filtering light-weight way improve label DP training at extra privacy cost is new to our knowledge. Second, we are not advocating consensus- cansed retraining as SOTA general-purpose algorithm for learning with noisy labels. Third, we do not view full retraining to be an algorithmic contribution; we consider it for theoretical analysis and as a baseline for consensus-basee retraining.
Our main contributions can be summarized follows:
The primary reason for our interest in retraining is that it turned out to be a simple yet effective way to improve train- ing with local' label differential privacy (DP) whose goal to safeguard the privacy of labels in supervised MI. problem by injecting label noise (see Section for a for- mal definition). Label DP is used in scenarios where only the labels are considered sensitive, e.g., advertising, recom- mendation systems, etc. (Ghazi et al., 2021). Importantly, retraining can be applied on top of any label DP training algorithum at no extra privacy cost. Our main algorithmic contribution is empirically demonstrating the efficacy of consensus based retraining in improving label DP training (Section 5). Three things worth clarifying here. First, as meta-idea, retraining is not particularly new; however,
(a) In Section 4, we consider linearly separable binary classification problem wherein the data (feature) dimension is d, and we are given randomly flipped labels with the label flipping probability being < á independently for each sample. Our main result is proving that full retraining with the predicted hard labels improves the population ac- curacy obtained by initially training with the given labels, provided that p is close enough to and the dataset size
satisfies d (1-2p)z log (1-2p)² X T2 (I-2p)z ("S" means d
d²
bounded asymptotically, ignoring constant factor multiples); see Remark 4.10 for details. In addition, that retraining becomes more beneficial as the amount of label noise (i.c., p) increases or as the degree of separation between the classes increases. To the best our knowledge, these are the first theoretical results quantifying the bene- fits of retraining with predicted hard labels in the presence
In this paper, we focus only local label DP. So throughout the paper, we will mostly omit the word "local" for conciseness.
2

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
of label noise. The analysis of retraining is particularly challenging because of the dependence of the predicted labels on the entire training set and the non-uniform/samplee dependent nature of label noise in the predicted labels; see the discussion after the statement of Theorem 4.8.
then its predicted soft labels are used train student model with the same architecture as the teacher. In contrast, we use predicted hard labels in retraining. Also, SD is usually employed with a temperature parameter (Hinton et al., 2015) to force the teacher and student models to be different; we do not have any such parameter in retraining. SD is known to ameliorate learning in the presence of noisy labels (Li et al., 2017) and this has been theoretically analyzed by Dong et al. (2019); Das & Sanghavi (2023). Dong al. (2019) propose their own SD algorithm that uses dynamically updated soft labels and provide some complicated conditions of when their algorithm can learn the correct labels in the presence of noisy labels. In contrast, we analyze retraining with fixed hard labels. Das & Sanghavi (2023) analyze the standard SD algorithm in the presence of noisy labels with fixed soft labels but their analysis in the classification setting requires some strong assumptions such access to the population, feature maps of all points in the same class having the same inner product, etc. We do not require such strong assumptions in this paper (in fact, we present sample complexity bounds).
(b) In Section 5, we show the promise of consensus- based retraining (i.e., retraining on only those samples for which the predicted label matches the given noisy label) as a simple way to improve the performance of any label DP algorithm, at no extra privacy cost. For e.g., when training ResNet-18 on CIFAR-100 with e = 3 label DP, we obtain 6.4% im- provement in accuracy with consensus-based retraining (see Table 2). The corresponding improvement for a small BERT model trained on AG News Subset (a news classification dataset) with 0.5 label DP 11.7% (see Table 10).
2 Related Work
Self-training (ST). Retraining is similar in spirit to ST (Scudder. 1965; Yarowsky. 1995; Lee et al., 2013; Sohn et al., 2020) which is the process of progressively training a model with its own predicted hard labels in the semi- supervised setting. Our focus in this work is on the fully supervised setting. This is different from ST (in the semi- supervised setting) which typically selects samples based on the model's 's confidence and hence, we call our algorithmic idea of interest retraining to distinguish it from ST. In fact, we show that our consensus- based sample selection strategy leads to better performance than confidence- baaddd sample selection in Appendix J. There is vast body of work on ST and related ideas; see Amini et al. (2022) for survey. On the theoretical side also, there are several papers showing and quantifying different kinds of benefits of ST and related ideas (Carmon et al., 2019; Raghunathan et al., 2020; Kumar et al., 2020; Chen et al., 2020; Oymak& & Guleu, 2020; Wei et al., 2020; Zhang et al., 2022). But none of these works characterize the pros/cons of ST or any related algorithum in the presence of noisy labels. In contrast, retraining can provably improve accuracy in the presence of label noise in Section 4. Empirically, ST-based ideas have been proposed to improve learning with noisy labels (Reed et al., 2014; Tanaka et al., 2018; Han et al., 2019; Nguyen et al., 2019; Li et al., 2020; Goel et al., 2022); but these works do not have rigorous theory. In the context of theory on label noise and model's confidence, Zheng et al. (2020) show that if the model's predicted score for the observed label is small, then the observed label is likely not equal to the true label. Note that the results of Zheng et al. (2020) pertain to the correctness of the observed labels, whereas our results pertain to the correctness of the predicted labels.
Label differential privacy (DP). Label DP (described in detail in Section 3) is a relaxation of full-data DP wherein the privacy of only the labels (and not the features) is safe- guarded (Chaudhuri & Hsu, 2011; I; Beimel et al., 2013; Wang & Xu, 2019; Ghazi et al., 2021; Malek Esmaeili et al., 2021; Ghazi et al., 2022; Badanidiyuru Varadaraja et al., 2023). In this work, we are not trying to propose a SOTA label DP algorithm (with an ingenious noise- injjeeinnectioon scheme); instead, advocate retraining as simple cost-processing step that can be applied top of any label DP algorithm (regardless of the noise-injection scheme) to improve its performance, at no extra privacy cost. Similar to our goal, Tang et al. (2022) apply techniques from unsupervised and semi-supervised learning to improve label DP training. In particular, one of their steps involves keeping the given noisy label of a sample only if matches a pseudo-label generated by unsupervised learning. This is similar in spirit to our consensus- based retraining scheme but crucial difference is that we do not perform any unsupervised learning; we show that matching the given noisy label to the model's own predicted label is itself pretty effective. Further, unlike our work, Tang et al. (2022) do not have any rigorous theory.
show that
3 Preliminaries
Notation. For two functions f()) and g(n), we write f(n) & (n) if there exists nig and a constant C > 0 such that for all n 2 no. f(n) S Cg(nn. For any positive integer m 2 1, we denote the set (I....,m) m} by [m]. Let e, de- note the 7t canonical vector, namely, the vector of all zeros except a one in the 4th coordinate. We denote the E norm of vector v by le.l. and the operator norm of matrix
Self-distillation (SD). Retraining also similar in principle to SD (Furlanello al., 2018; Mobahi et al., 2020), where teacher model is first trained with provided hard labels and
3

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
M by | The unit d-dimensional sphere (i.e., the set of d-dimensional vectors with unit norm) is denoted by St-1 For random variable X, its sub-gaussiag norm, denoted by
covariance matrix of the feature vector. We let y == ||
Gaussian mixture model with positive margin: Here each data point (x.y) is generated independently by first sam- pling the label y é [+1,-1) with probabilities T TT, and then generating the feature vector x E Rd as:
| is defined as |X| //2 == supge1 1/22 E [x]9) V?2
In addition, for random vector X R its sub-gaussian norm is defined as | llve s [[X, 2) lag.. We denote the CDF and complementary CDF (CCDF) of a stan- dard normal variable (i.e., distributed as N 1)) by (()) and $5 (-), respectively.
x y(1 w) >²2, where
(4.1)
uu> > is drawn from a sub- gobsssausii distribution with unit sub- sabl-aassiann norm (i.e., |u = 1).
Definition 3.1 (Label differential privacy (DP)). A ran- domized algorithm A taking as input a dataset and with range R is said to be e-labelDP if for any two datasets D and D' differing in the label of a single example and for any S S R, it holds that PP (A(D) E S) s <<(()(())
~ -0, Ia) independent of u.
Σ e Raxa is the covariance matrix in the space orthog- onal to μ.. We have E¹ = 0 and E is of rank d 1. Also, Amin > 0 and Amax are the minimum non-zero eigenvalue and the maximum eigenvalue of Σ.
Local label DP training involves injecting noise into the labels and then training with these noisy labels. The sim- plest way of injecting label noise to ensure label DP is randomized response (RR) introduced by Warner (1965). Specifically, suppose we require e-labelDP for problem with C' classes, then the distribution of the output y of RR when y is the true label is given by: P (77 - y) = er - and P 2)= c--C- for any 2 # y. Our label noise model in Section 4 (Equation (4.2)) is actually RR for 2 classes. Based on vanilla RR, more sophisticated ways to inject label noise for better performance under label DP have been pro- posed (Ghazi et al., 2021; Malek Esmaeili et al., 2021). Our empirical results in Section 5 are with RR and the method of Ghazi et al. (2021).
Note that under this data model, the projection of datapoints on the space orthogonal to ya is Gaussian. Along μ4, we have (æ,, μ1) y + u) I e and so the randomness of data along μu is due to u. Further, since u O, sign( (4) = y. Thus, I is a separator for the data w.r.t. the labels. In addition, we have a margin of at least 7 == I|Iz|lee this is because s(x.0)) (1 + u) ||elle 2 7. We will mostly refer [M] to the margin y as the "degree of separation".
We are given access to a training set T ((x,, T() ) he[nl
where for each i E [m]] Th is noisy version of the true label Yi (which we do not observe). Specifically:
4 Full Retraining in the Presence of Label Noise: Theoretical Analysis
Di
yi
with probability 1 1-p,
(4.2)
-
with probability p.
Here we will analyze full retraining (as introduced in Sec- tion 1) for linear setting with noisy labels. Since full retraining is the only kind of retraining we consider here, we will omit the word "full" subsequently this section.
for some p < 1/2, and independently for each i [m].*
4.1 Initial Training
Given the training set T ((1; ]a(]). we consider the following linear classifier model (also used in Carmon et al. (2019)):
Problem setting: We consider binary classification in a linearly separable' setting similar to the classical Gaussian mixture model. We will first describe the classical Gaussian mixture model and then describe our setting of interest, which is endowed with a positive margin.
1 - -- 12
Oo
(4.3)
This classifier's predicted label for a sample x e Rd is sign (ax, Qo)). Note that (z, 0o) -1 Σ, (Z,, x) is a
In the classical Gaussian mixture model, each data point belongs to one of two classes (1] with corresponding probabilities T., n.,. such that n, + n- 1. The feature vector RRd for data point with label y (+1,-1} is drawn independently from (V,, E), where f E RR and E é Rdxd In other words the mean of the feature vector is =/c depending on the data point's label, and Σ is the
"In the context of e-labelDP for binary classification problem with randomized response, p - -
'This is simplification to the least squares' solution (LSS) ob- tained by excluding the empirical covariance matrix's 's inverse. The LSS can be analyzed by bounding the deviation of the em- pirical covariance matrix from the population covariance matrix (which shrinks as n + oo). then adapting our current analysis to features pre-multiplied by the population covariance matrix's 's inverse, and accounting for this deviation. This would only make the math more tedious without adding any meaningful insights.
RRefer to Vershynin (2010) for other equivalent definitions. Morre specifically, there exists a linear separator that perfectly classifies the data points according to their labels.
4

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
weighted average of the noisy labels in the training set, with the weights being } ar). So it is similar to kernel methods with the inner product kernel.
1 err err(Oo) exp
n (n(1-2))
+ +
16 d
+ 2 eexp
(
12
(1 (1-22)²)
(4.7)
Our next result bounds the probability of 6, misclassifying a fixed test point æ; with respect to the randomness in the training set T.
32
The proof of Theorem 4.2 is in Appendix C.
Theorem 4.1 (Initial training). Consider x é T and let y be its true label. We have
Remark 4.3 (Tightness of error bounds). When n s Xmaxd (1-2p)9y1> 7 & (A and Amax & 1, then the lower Amin
P(sign 0o)) + v) a0(2:) == 5(1 + vn(1 22))) ( (e) |
and upper bounds for err(Oo) in Theorem 4.2 match (up to constant factors).
2
exp
and
Based on Theorem 4.2, we have the following corollary. Corollary 4.4 (Initial training's 's sample complexity). For any d > 24-4/8 + 4xepp (- 32 (1 22,)),. having number of 1/6
2/2m 2m
P(sign (azign((z,,0 0n)) * +y)+ S Ø0(2)
samples n 2 8A (1-2p)² xa ensures acc(O.) 1- In particular, when the label flipping probability satisfies p >> 2e 2e-d/5 + exp
exp 2
1
n(1 2p) 2 (x, 11)2
+ + exp
T1
(1-2p)² 2p)²
(- 32 (1 )p) then n 2 8X log logl/p d (1-2p)² 77 ensures acc acc( > >1 p. i.e., our learned classifier Og has better accuracy than the source providing noisy labels (used to learn Ob).
8
1
32
The proof of Theorem 4.1 is in Appendix B. Notice that the learned classifier 0g is more likely to be wrong the samples that are less aligned with (or closer to orthogonal 1o) the ground truth separator, i.e., fs. We can view On as a noisy label provider (a.k.a. pscudo-labeler) where the degree of label noise is non-uniform or sample-dependent unlike the original noisy source used to learn 0p. Specifically, for sample with true label y and predicted label i7 sign( (x, O,)), we have:
Remark 4.5 (Efffet of degree of separation). As the pa- rameter quantifying the degree of separation ry decreases, the error bound Theorem 4.2 increases and the sample complexity required outperform the noisy label source in Corollary 4.4 increases. This is consistent with our intuition that a classification task should become harder the degree of separation reduces; we saw this in Figure 1.
We conclude this subsection by deriving an information- theoretic lower bound on the sample complexity of any classifier to argue that 0g attains the optimal sample com- plexity with respect to d and p.
y/ with probability at least 2 1 (1) and -y with probability at most S āo (x),
7
where āo (xr) is as defined Theorem 4. We will next define the population error of a classifier as
Theorem 4.6 certoommatiinnthhoreeee lower bound on sam- ple complexity). With slight generalization of notation, let acc μ)) denote the accuracy of the classifier 0 as per Equation (4.5), when the ground truth separator is μ.. We also consider the case of D = = viz. the projection ma- trix onto the space orthogonal to p. For any classifier O learned from T == (z)) je[n]. in order to achieve inf pesa-1 acc(0; 11) 2 1-5, the condition n S2 (122))dd is necessary in our problem setting.
err( 0- : [(m.)) [P(sigu(aa (x, 0)) + v)], (4.4)
where the probability (inside the expectation) is w.r.t. the randomness in the training set used to learn ². Similarly, the population accuracy of is defined as
acc 0 := [(<e.v) [P (P(iiin(() ((sig(((, 0) -w)] err(
(4.5)
Depending on the context, our results and discussions will sometimes be presented in terms of error (lower is better) and at other times in terms of accuracy (higher is better).
It is worth mentioning that there is a similar lower bound in Gentile & Helmbold (1998) for a different classification setting. In contrast, Theorem 4.6 is tailored to our setting and moreover, the proof technique is also different and in- teresting in its own right. Specifically, for the proof of Theo- rem 4.6, we follow a standard technique in proving minimax lower bounds which is to reduce the problem of interest to an appropriate multi-war way hypothesis testing problem; this is accompanied by the application of the conditional version of Fano's inequality and some ideas from high-dimensional
Our next result bounds the error of the classifier dg Theorem 4.2 (Initial training's population error). We have
(1-E-t) ---
160(1 /n(1 2p)) 2271
err( (6)) 2
exp
2T
2 mind d
(4.6)
5

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
geometry. This proof is in Appendix D. There are also few other noteworthy lower bounds (Cai & Wei, 2021; Im & Grigas, 2023; Zhu et al., 2024) in more general settings than ours, naturally, their bounds are weaker than Theorem 4.6. We discuss these bounds in Appendix E.
on the entire training set. This dependence of the predicted labels on all the data points makes the analysis highly chal- lenging because standard techniques under independence are not applicable here." ?
The high-level proof idea for Theorem 4.8 is that for each sample By = ye(1 + ue) + Σ1/2 z1 in the training set, we carefully curate a dummy label 1%/ that does not depend on {=x ) but depends on all {ux Re[m]i see (F.3) in Ap- pendix F. We show that with high probability, the labels predicted by do on the training set (Tee)e(()) match the cor- responding dummy labels (% [e]]) We analyze the mis- classification error of 02 under this high probability "good" event with the dummy labels (77) (e[n), which more con- ducive to analysis (because they do not depend on {=*)==t), and also bound the probability of the "bad" event (i.e., 3 at least one such that Te # Tz)- We provide an outline of these steps in detail at the beginning of Appendix F.
Remark 4.7 (Minimax optimality of sample complexity). Note that the dependence of the sample complexity d and p in Corollary 4.4 matches that of the lower bound in Theorem 4.6. Thus, our sample complexity bound in Corollary 4.4 is optimal with respect to d and p.
4.2 Retraining
We first label the training set using Oo- Denote by Mi sign((z; 0o)) the predicted label for sample æ4. We then retrain using these predicted labels. Our learned classifier here is similar to the one in Section 4.1, except that the observed labels are replaced by the predicted labels. Specif- ically, our retraining classifier model is the following:
We will now provide an upper bound on the error (defined in (4.4)) of 0j.
1 - Σ T... = 72
0,
(4.8)
Theorem 4.9 (Retraining's population error). Suppose the conditions of Theorem 4.8 hold. Then, we have
0,'s predicted label for a sample x Rd is sign((æ; O,)). Our next result bounds the probability of 0 misclassifying fixed test point æ, with respect to the randomness in the training set T (similar to Theorem 4.1).
n01 22())
err(O 2xxp
64(T* +2Amaxd)
+ 2e 4/8
+ +4exp
(1 (1=)
Theorem 4.8 (Retraining). Suppose that 3/
32
(11-2p))
ndd > X .andd d 7. Consider x & T and let be its true
+
n
exp
(1
2p')
12
+ -d/16
c4nn J (4.9)
Amax label. We have
2
8X2
max
d
P(sign((x:0.)) y) S az (2), where
with of exp
[n(1-2p)>²)
40.mmc
and p' == =1(1+
B nd p.
3yy
The proof of Theorem 4.9 is in Appendix G. As expected, (4.9) is decreasing in % because the classification task be- comes easier as the degree of separation increases.
n(1 (a(1-2g')² 2 20)2 64((z, 12)2+
an (a)) == 2exp
|/:1222 l1:
Retraining vs. Initial training. We will now compare the error bounds of the initial training model 0, (4.6) from Theorem 4.2 with that of the retraining model 0 (4.9) from Theorem 4.9. Note that the dominant term in the upper bound on err err(0,) is the last term in (4.9) which has (1-2p') inside the exponent, and p' approaches p as n and d grow. In contrast, the lower bound on err (Q)) in (4.6) has (1- 22)² inside the exponent. This is the main observation that indicates retraining can improve model accuracy, and this improvement becomes increasingly significant as p - } We will now formalize this observation by providing sufficient conditions under which err( (0)) < err(On) or equivalently, acc( ①.) > (C))
+ 4 cxp
n1
(1 2p)²)
32
74 (1 (1-2 (1=2)") 11
n2
/ te -d111) ain
+ 2
exp
8A2
with of = =exp (-
"(1-2p)>²
and p' 5/= (1
3, 812 mune nd) p.
40Amax
The proof of Theorem 4.8 is in Appendix F.
Technical challenges: The proof of Theorem 4.8 is espe- cially challenging due to the following reasons:
(i) The source of the predicted labels (T.)), used by 0,,
viz., 0p is a non-uniform noisy label provider, as we dis- cussed after Theorem 4.1.
Remark 4.10 (When does retraining improve accuracy?). We consider an asymptotic regime where n, d - co. Also,
(ii) More importantly, oo depends on all the samples in the training set and hence each predicted label Th is dependent
'The analysis of Oo (Theorem 4.1) is relatively simpler because the given noisy labels (Ti)-., are independent across samples.
6

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
suppose that Amux $ 1. By comparing (4.6) with (4.9), we Aminy
(2021) specifically, Algorithm 3 with two stages. Our training set consists of 45k examples and we assume access to a validation set with clean labels consisting of 5k exam- ples which we use for deciding when to stop training, setting hyper-parameters, etc.' ? For CIFAR-10 and CIFAR-100 with three different values of e (DP parameter, see Def. 3.1), we list the test accuracies of the baseline (i.e., the method of Ghazi et al. (2021)), full RT and consensus-basee RT in Tables 1 and 2, respectively. Notice that consensus- based RT is the clear winner. Also, for the three values of in Table (CIFAR-10), the size of the consensus set (used in consensus-based RT) is ~ 31%, 55% and 76%, respectively, of the entire training set. The corresponding numbers for Table 2 (CIFAR-100) are 11, 34% and 56%, respec- tively. So for small e (high label noise), consensus-bor RT comprehensively outperforms full RT and the baseline with a small fraction of the training set. Further, in Table 3, we list the accuracies of the predicted labels and the given labels over the entire (training) dataset and the accuracy of the predicted labels (which are the same as the given labels) over the consensus set for CIFAR-10 and CIFAR-100, To summarize, the accuracy of predicted labels over the consen- sus set is significantly more than the accuracy of predicted and given labels over the entire dataset. This gives us an idea of why consensus-based RT is much better than full RT and baseline, even though the consensus set is smaller than full dataset.
obtain the following sufficient conditions. There exists absolute constant co such that if p (1 -co, 2) and
Xmmin d 7111 2p)² log
Amin d (111 2p)²
2 Xmii df
7A(1 22p)2'
then the accuracy of retraining is greater than the accuracy of initial training.
Some comments regarding Remark 4.10 are in order.
Range of n in Remark 4.10. We believe that the lower bound on n is tight w.r.t. d and p. ignoring log factors. We claim this because ?
d samples are necessary
(1-2p)²
for acc(0.) (0)0))) 1 p as per Theorem 4.6, and we can only expect the retraining classifier 02 to be better than the initial training classifier 0g if the accuracy of 0,'s predicted labels (which is used to train Q,) is more than the accuracy of the given labels = 1 - p. In contrast, the upper bound on n may be an artifact of our analysis. Having said that, the range d² of (T-2p)= & n is not very interesting because it is far more than the number of learnable parameters d.
Effect of degree of separation 7.. As increases, the minimum value of n in Remark 4.10 for which we obtain an improvement with retraining reduces. This is consistent with the high-level insight of Fig. 1, viz., retraining is more beneficial when the separation between the classes is large.
Table 1. CIFAR-10. Test set accuracies (mean +: standard devia- tion). consensus-based RT is better than full RT which is better than the baseline (initial training).
Improving Label DP Training with Retraining (RT)
Motivated by our theoretical results in Section 4 which show that retraining (abbreviated RT henceforth) can improve accuracy in the presence of label noise, we pro- pose to apply our proposals in Section 1, viz., full RT and more importantly, consensus-bast based RT to improve local label DP training because it involves training with noisy labels. Note that this can be done on top of any label DP mechanism and that too at no additional privacy cost (both the predicted labels and originally provided noisy la- bels are private). Here empirically evaluate full and consensus-basee RT on four classification datasets (avail- able on TensorFlow) trained with label DP. These include three vision datasets, namely C0, CIFAR-100, and DomainNet (Peng et al., 2019), and one language dataset, namely AG News Subset (Zhang et al., 2015). Unless oth- erwise mentioned, all our empirical results here are with the standard cross-entropy loss. All the results are averaged over three runs. We only provide important experimental details here; the other details can be found in Appendix H.
Baseline
Full RT
Consensus-base RT
57.78 + 1.13
60.07 + 0.63
63.84 =: 0.56
2
79.06 0.59
81.34 + 0.40
83.31 0.28
85.18 0.50
86.67 = 0.28
87.67 0.28
Table 2. CIFAR-100. Test set accuracies (mean + standard devia- tion). Overall, consensus- based RT is significantly better than full RT which somewhat better than the baseline (initial training).
Baseline
Full RT
Consensus- RT
23.53 + 1.01
24.42 + 1.22
29.98 1.11
4
44.53 0.81
46.99 + 0.66
51.30
0.98
5
55.75 0.36
56.98 + 0.43
59.47 0.26
One may wonder how an increase in the number of model parameters affects results because of potential overfitting to label noise. So next, we train ResNer-34 (which has
In practice, we do not need access to the validation set. Instead, it can be stored by a secure agent which returns us private version of the validation accuracy and this will not be too far off from the true validation accuracy when the validation set is large enough. We also show some results without a validation set in Appendix K.
1011000 We train a ResNet-18 18 model (from scratch) on CIFAR-10 and CIFAR- with label DP. Label DP training is done with the prior-based method of Ghazi et al.
7

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Table CIEAR-10 (top) and CIFAR-100 (bottom). Accuracies of predicted labels and given labels over the entire (training) dataset and accuracies of predicted labels over the consensus set. Note that the accuracy over the consensus set x accuracy of over the entire dataser (with both predicted and given labels). This gives us an idea of why consensus-basee RT much better than full RT and baseline, even though the consensus set is smaller than the full dataset (~ 31%, 55% and 76% of the full dataset for e 1, and 3 in the case of CIFAR-1O, and 11%, 34% and 56% of the full dataset for e 3, and in the case of CIFAR-100).
Acc. of predicted labels on full dataset
Acc. of given labels on full dataset
Acc. of predicted labels on consensus
59.30 a: 0.74
32.61 a 0.74
76.17 a: 0.15
CIFAR-10
2
81. 62622 a: 0.18
57. 11 + 0.05
92.65 + 0.22
3
89.28 0.35
76.73 a 0.12
95,94 a: 0.23
Acc. of predicted labels on full dataset
Acc. of given labels on fill dataset
Acc. of predicted labels on conseRsus set
24.90 0.92
22.35 0.41
76,09 0.85
CIFAR-100
50.85 # 0.82
46.32 # 0.34
91.59 # 1.24
5
66.51 0.02
68.09 # 0.33
94.83 + 0.15
Table CIFAR-100 w/ Nes.4t..4, Test set accuracies (mean standard deviation). Just like Table 2 (ResNet-18), consensus- based RT is the clear winner here. But the performance in case of ResNet-34 is worse than R8 due more overfitting to noise because of more parameters; this is expected.
Table 5. CIFAR-100 w/ ResNet-34: noise-robust forward correc- tion (Patrini et al., 2017) used initially (in the baseline). Test set accuracies (mean + standard deviation). We see that retraining (especially, consensus consensus-based RT) yields improvement even after noise-robust initial training, although the amount of improvement is less compared to Table (no noise-correction).
6
Baseline
Full RT
Consensus- based RT
4
37.53 a 1.58
39.33 1.37
43.87 + 1.62
Baseline
Full RT
consensus-based RT
5
51.13 + 0.69
52.33 0.38
55.43 + 0.42
4
41.80 a 0.90
42.63 + 0.58
46.53 0.76
5
53.83 # 0.83
54.43 # 0.48
56.60 0.43
nearly six times the number of parameters of ResNet--18 on CIFAR-100; the setup is exactly the same our previous ResNet- experiments. Additionally, one may wonder if retraining is useful when a label noise-robust technique is used during initial training, i.e., on top of the method of Ghazi et al. (2021). To that end, we train ResNet-34 on CIFAR-100 with (i) the popular correcior technique of forward correction (Patrini et al., 2017) applied to the first stage of Ghazi et al. (2021) (it is not clear how to apply it to the second stage), and (ii) the noise-robust symmer-- ric cross-entropy (CE) loss function of Wang et al. (2019) with a = 0.8, B = 0.2 used instead of the standard CE loss function. We show the results for ResNet-34 without any noise-robust method, forward correction used initially, and with the symmetric CE loss function in Tables 4, 5, and 6, respectively, for {4,5): 5): please see the detailed discus- sion in the captions. In summary, consensus-based RT is pretty effective even with overfitting by ResNet-34. Also, more importantly, consensus-based RT is beneficial even after noise-robust initial training.
Table 6. CIFAR-100 w/ ResNet-34: noise-robust symmetric CE loss (Wang et al., 2019) used instead of standard CE loss. Test accuracies (mean + standard deviation). We see that retraining (especially, consensus-base bassed KT) yields improvement even with a noise-robust loss function.
Baseline
Full RT
Consensus-based RT
4
37.07 2.03
38.17 # 2.03
43.20 1.77
5
53.10 0.54
53.40 + 0.33
56.13 + 0.25
that the validation set comes with clean labels. In Table 7, we show results for c = (3.4} when label DP training is done with the method of Ghazi et al. (2021) with two stages (same as the CIFAR experiments). Observe that consensus-based RT is the clear winner. Further, in Tables 8 and 9, we show the corresponding results when the noise-robust techniques of forward and buckward correction (Patrini et al., 2017) are applied to the first stage of Ghazi et al. (2021) in initial training (it is not clear how to apply forward and backward correction to the second stage). As expected, forward backward correction lead to better initial model performance (compared to no correction). The main thing note however is that consensus- RT yields significant gains even after noise-robust initial training, consistent with our earlier results.
org/ catttalog//ommmieeee....... domainnet)). This is an image classification dataset much larger than CIFAR where the images belong to one of 345 classes. Here we do linear probing (i.c., fitting a softmax layer) on top of a Re pretrained on ImageNet. We reserve 10% of the entire training set for validation and use the rest for training with label DP. Just like the CIFAR experiments, we assume
DomainNet (https: http:s/s/wwww..enssii.i.e.
taasets/catalon
*It is worth noting that for 3. consensus- RT leads similar accuracy with and without noise correction.
8

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Table Domainnett Test set accuracies (mean = standard devia- tion). Consensus-basse RT leads to very significant improvement.
Table 10, AG News Subset. Test set accuracies (mean = standard deviation). Consensus basedd RT is better than fill RT which is better than the baseline.
Baseline
Full RT
Consensus- based RT
3
23.60 = 0.92
29.23 1.03
36.30 + 0.75
Baseline
Full RT
Consensus-based RT
0.3
54.54 = 0.97
60.03 +:2 2.90
65.91
1.93
4
48.25 = 0.05
52.10 = 0.10
57.40 + 0.20
0.5
69.21 0.31
75.63 # 1.08
80.95 1.47
0.8
79.10 = 1.43
82.19 + 1.54
84.26 1.03
Table 8. DomainNet: noise-robust forward correction used ini- tially. Test set accuracies (mean standard deviation). Consensus- based RT yields significant improvement even after noise-robust initial training.
Baseline
Full RT
Consensus- bonsensus-based RT
base method to significantly improve its performance in the presence of noisy labels.
31.23 # 0.56
33.30 = 0.65
36.07 0.78
4
58.50 = 0.08
58.63 = 0.12
61.80 + 0.08
Additional empirical results in the Appendix. In Ap- pendix J, we show that consensus- based RT outperforms retraining on samples for which the model the most con- fident; this is similar to self-training's method of sample selection in the supervipe setting. In Appendix K, we show that RT is beneficial even without a validation set. Fi- nally, going beyond label DP, we show that consensus RT is beneficial in the presence of human annotation errors which can be thought of as "real" label noise in Appendix L.
noise-robust backward correction used initially. Test set accuracies (mean + standard deviation). Once again, consensus-based RT yields significant improvement even after noise-robust initial training.
Table DomainNet:
Baseline
Full RT
Consensus- baased RT
3
30.17 # 0.61
31.47 # 0.74
35.03 + 0.78
4
56.63 # 0.37
56,80 = 0.37
60.47 + 0.46
6 Conclusion
Finally, we show results on a language dataset.
In this work, we provided the first theoretical result showing retraining with predicted hard labels can provably increase model accuracy in the presence of label noise. We also showed the efficacy of consensus- based retraining (i.c., re- training on only those samples for which the predicted label matches the given label) in improving local label DP train- ing. We will conclude by discussing some limitations of our work which pave the way for future directions of work. Our theoretical results in this work focused on full retrain- ing. Because consensus-based retraining worked very well empirically, we would like to analyze it theoretically in the future. Also, our theoretical results are under the uniform label noise model. In the future, we would like to analyze retraining under non-uniform label noise models. We also hope to test our ideas on larger-scale models and datasets.
AG News Subset datasets aetaaets/catalogg /aoggg//ggaaon sgg_nwss_uubeettt This is a news article classification dataset consisting of categories world, sports, business or sci/tech. Just like the previous ex- periments, we keep 10% of the full training set for validation which we assume comes with clean labels, and use the rest for training with label DP. We use the small BERT model available in TensorFlow and the BERT English uncased preprocessor; links to both of these are in Appendix H. We pool the output of the BERT encoder, add a dropout layer with probability = 0.2, followed by a softmax layer. We fine-tune the full model. Here label DP training done with randomized response. We list the test accuracies of the baseline (i.e., randomized response), full RT and consensus- based RT in Table 10 for three different values of e. Once again, consensus- based RT is the clear winner. For the three values of 6 in Table 10, the size of the consensus set is ~ 28%, 32% and 38,, respectively, of the entire training set. So here, consensus-bused RT appreciably outperforms full RT and baseline with less than two-fifths of the entire training set. In Table 11 (Appendix I), we list the accuracies of the predicted & given labels over the full dataset and the consensus set; the observations are similar to Table 3 giving us an idea of why consensus-basee RT performs the best.
http///wwwwts.ofr.l.....oooo org/
A Acknowledgments
Adel Javanmard is supported in part by the NSF Award DMS-2311022 the Sloan fellowship in Mathematics. an Adobe Faculty Research Award, an Amazon Faculty Re- search Award, and an iORB grant from USC Marshall School of Business. Sujay Sanghavi is partially supported by NSF EnCORE Tripods (2217069) and NSF AI Insti- tute for the Foundations of Machine Learning (2019844). The authors are grateful to anonymous reviewers for their feedback on improving this paper.
So in summary, consensus paased retraining is a straightfor- ward post-processing step that can be applied on top of a

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Impact Statement
Furlanello, T., Lipton, Z., Tschannen, M., Itti, L.,, and Anandkumar, A. Born again neural networks. In Interna- tional Conference Machine Learning, pp. 1607-1616. PMLR, 2018.
This paper presents work whose goal to advance the field of machine learning. There are potential societal conse- quences of our work, none of which we feel must be specifi- cally highlighted here.
Gentile, C. and Helmbold, D. P. Improved lower bounds for learning from noisy examples: An information-theoretie approach. In Proceedings of the eleventh annual con- ference Compulational learning theory, pp. (04-115, 1998.
References
Abramowitz, M. and Stegun, I. A. Handbook of mathemat- ical functions with formulas, graphs, and mathematical tables, volume 55, US Government printing office, 1968.
Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., and Zhang, C. Deep learning with label differential privacy, Advances in neural information processing systems, 34: 27131-27145, 2021.
Amini, M.-R., Feofanov, V., Pauletto, I.., Devijver, F.,, and Maximov, Y. Self-training: A survey, arXiv preprint Stti:22202.124400 2022.
Ghazi, B., Kamath, P., Kumar, R., Leeman, E., Manurangsi, P., Varadarajan, A. V., and Zhang, C. Regression with la- bel differential privacy. arXiv preprint arX1v:2212.06074. 2022.
Badanidiyuru Varadaraja, A., Ghazi, B., Kamath, P., Ku- mar, R., Leeman, E., Manurangsi, P., Varadarajan, A. V., and Zhang. C. Optimal unbiased randomizers for regres- sion with label differential privacy. Advances in Neural Information Processing Systems, 00600266602466 2023.
Ghosh, M. Exponential tail bounds for chisquared random variables. Journal of Statistical Theory and Practice, 15 (2):35, 2021.
Ball, K. et al. An elementary introduction to modern convex geometry. Flavors of geometry, (1(158):26, 1997.
Goel, A., Jiao, Y., and Massiah, J. Pars: Pseudo-label aware robust sample selection for learning with noisy labels. arXiv preprint arXiv:2201. 0022220..0836 10836, 2022.
Beimel, A., Nissim, K., and Stemmer, U. Private learning and sanitization: Pure vs. approximate differential privacy. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 363-378. Springer, 2013.
Han, J., Luo, P., and Wang, X. Deep self- self-learning from noisy labels. In Proceedings of the IEEE/CVF international conference computer vision, pp. 5138-5147, 2019.
Cai, T. T. and Wei, H. Transfer learning for nonparametric classification. The Annals of Statistics, 4901)1100-128, 2021.
Hinton, G., Vinyals, O., Dean, J., et al. Distilling the knowledge in a neural network. arXiv preprint arXiv: ftti::/503.25555 2(7), 2015.
Carmon, Y., Raghunathan, A., Schmidt, L., Duchi, J. C., and Liang, P. S. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 32, 2019.
Im, H. and Grigas, P. Binary classification with in- stance and label dependent label noise. arXiv preprint arXiv:2306.03444 2023.
Chaudhuri, K. and Hsu, D. Sample complexity bounds for differentially private learning. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 155-186. JMLR Workshop and Conference Proceedings, 2011.
Kumar, A., Ma, T., and Liang, P. Understanding self-training for gradual domain adaptation. In International confer- ence on machine learning, pp. 5468-5479 PMLR. 2020.
Chen, Y., Wei, C., Kumar, A., and Ma, T. Self-training avoids using spurious features under domain shift. Ad- vances in Neural Information Processing Systems, 33: 21061-21071, 2020.
Lee, D.-H. al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural net- works. In Workshop challenges in representation learning, ICML, volume 3, pp. 896. Atlanta, 2013.
Das, R. and Sanghavi, S. Understanding self-distillation in the presence of label noise. In International Conference on Machine Learning, pp. 7102-7140. PMLR, 2023.
Li, J., Socher, R., and Hoi, S. C. Dividemix: Learning with noisy labels as semi-supervised learning. arXiv preprint vrXiv:2002.0739: 2020.
Dong, B., Hou, J., Lu, Y., and Zhang, Z. Distillation s early stopping? harvesting dark knowledge utilizing anisotropic information retrieval for overparameterrized neural network. arXiv preprint
Li, Y., Yang, J., Song, Y., Cao, L., Luo, J., and Li, L.-J. Learning from noisy labels with distillation. In Proceed- ings of the IEEE International Conference on Computer Vision, pp. 1910-1918, 2017.
2019.
10

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Malek Esmaeili, M., Mironov, I., Prasad, K., Shilov, I., and Tramer, F. Antipodes of label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34:6934-6944 2021.
Tang, X., Nasr, M., Mahloujifar, S., Shejwalkar, V., Song, L., Houmansadr, A., and Mittal, P. Machine learning with differentially private labels: Mechanisms and frameworks. Proceedings on Privacy Enhancing Technologies, 2022.
Mobahi, H., Farajtabar, M., and Bartlett, P. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361, 2020.
Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 101 1.3027, 2010.
Wang. D. and Xu, On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pp.
Nguyen, D. T., Mummadi, C. K., Ngo, P. N., Nguyen, T. H. P., Beggel, L., and Brox, T. Self: Learning filter noisy labels with self-ensembling. arXiv preprint arXiv: 1910,0182,, 2019.
PMLR, 2019.
Wang. Y., Ma, X., Chen, Z., Luo, Y., Yi, J., and Bailey, J. Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 322-330, 2019.
Oymak, S. and Guleu, T. C. Statistical and algorithmic insights for semi-supervised learning with self-training. arXiv preprint ar arXiv:2006. 1006, 2020.
Warner, S. L.. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63 69, 1965.
Patrini, G., Rozza, A., Krishna Menon, A., Nock, R., and
Qu, I.. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1944-1952, 2017.
Wei, C., Shen, K., Chen, Y., and Ma, T. Theoretical analysis self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622, 2020.
Peng, X., Bai, Q., Xia, X., Huang, Z., Saenko, K., and Wang, B. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference Computer Vision, pp. 1406-1415, 2019.
Wei, J., Zhu, Z., Cheng, H., Liu, T., Niu, G., and Liu, Y. Learning with noisy labels revisited: A study using real- world human annotations. In International Conference on Learning Representations, 2022.
Raghunathan, A., Xie, S. M., Yang. F., Duchi, J., and Liang, P. Understanding and mitigating the tradeoff between robustness and accuracy. In International Conference Machine Learning, pp. 7909-7919, PMLR, 2020.
Yarowsky, D. Unsupervised word sense disambiguation rivaling supervised methods. In 33rd annual meeting of the association for computational linguistics, pp. 189- 196, 1995.
Reed, S., Lee, H., Anguelov, D., Szegedy, C., Erhan, D., and Rabinovich, A. Training deep neural networks on noisy la- bels with bootstrapping. arXiv preprint arXiv: arXiv:1412.6500 1412.6596, 2014.
Zhang, S., Wang. M., Liu, S. L., Chen, P.-Y. C., and Xiong, J. How does unlabeled data improve generalization in self-training? a one-hiddenn-layr theoretical analysis. In International Conference on Learning Representations, 2022.
Scarlett, and Cevher, V. An introductory guide to fano's in- equality with applications in statistical estimation. arXiv preprint arXiv:
Zhang, X., Zhao, J., and LeCun, Y. Character-level convolu- tional networks for text classification. Advances in neural information processing systems, 28, 2015.
2019.
Scudder, H. Probability of error of some adaptive pattern- recognition machines. IEEE Transactions on Information Theory, 113)):633371, 1965.
Zheng, S., Wu, P., Goswami, A., Goswami, M., Metaxas, D.,
and Chen, C. Error-bounded correction of noisy labels. In International Conference on Machine Learning, pp. 11447-11457. PMLR, 2020.
Sohn, K., Berthelot, D., Carlini, N., Zhang. 7., Zhang, H., Raffel, C. A., Cubuk, E. D., Kurakin, A., and Li, C.-L. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances neural informa- tion processing systems, 33:596-608 608666607710 2020.
Zhu, Y., Zhang, J., Gangrade, A., and Scott, C. Label noise: Ignorance is bliss. Advances in Neural Information Processing Systems,
2024.
Tanaka, D., Ikami, D., Yamasaki, T., and Aizawa, K. Joint optimization framework for learning with noisy labels. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5552-5560, 2018.

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Appendix
Table of Contents
Appendix A: Problem Setting of Figure
Appendix B: Proof of Theorem 4.1
Appendix C: Proof Theorem 4.2
Appendix D; Proof of Theorem 4.6
Appendix E: Other Relevant Lower Bounds for Learning with Noisy Labels
Appendix F: Proof of Theorem 4.8
Appendix G: Proof of Theorem 4.9
Appendix H: Remaining Experimental Details
Appendix I: Accuracy over the Entire Dataset and over the Consensus Set in the Case of AG News Subset
Appendix J: Consensus- Baasen Retraining Does Better than Confidence- Based Retraining
Appendix K: Retraining is Beneficial Even Without a Validation Set
Appendix L: Beyond Label DP: Evaluating Retraining in the Presence Human Annotation Errors
12

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
A Problem Setting of Figure 1
The setting is exactly the same as the problem setting in Section 4 with d= 50, μt y = I ejei and p= 0.4. In the direction of μa, we have (a,, /4) y(1 + u) ||l. y(1 u)y². We consider balanced classes (i.e., 74 πT (2) and choose " ~ Unif[0,4] the uniform distribution over the interval [0. [0,4]. In Figure la, 72 0.5 (large separation) and in Figure 1b, y 0.3 (small separation). The number training samples each case is 300 and the retraining is done on the same training set on which the model is initially trained. The learned classifiers from initial training and retraining are the same as in Section 4 (i.e., Equations (4.3) and (4.8), respectively). Finally, the test accuracy of both initial training and retraining in Figure 1b is 68%.
B Proof of Theorem 4.1
We first prove the lower bound oup (2) and then the upper bound āo(z).
B.1 Lower Bound (x)
Let E, y:Dh- So & 1 with probability - and & = -1 with probability Under our data model, for each sample we can write æ; yi(1 Uz) pa 1 with 2, ~ (O, I2). Hence,
no, Σ Jæ Σ
Ea(1 u)))
Σ se[xx]
T7 M 1/121 2i.
ic|m]
xe[x]]
We also note that
P(sign((z;0o)) 0o)) + v) P(y((, 0o) 50) =P -P((2) &:11 (v=+ (xc, Σ 122 $0 ie(n]
sc|m]
Define 2 = Evern] VJ, 12, Conditioning on [[i)e[n] we have ((,On)) and so (x. 8) ~ ~NO, |
We write
= (Eie(ng Ei(1 us)
Myar, p4)
IP
&(1 (1x), (x, 00 (E, (G.
v D 12x
ic(m)
where ((1) -/2 1 e - 12 denotes the cdf of standard normal distribution.
Combining the previous two equations, we arrive at
(Eienn &1 + u: (1ya,
Pssign(xx; 0o)) 8) T
(B.1)
/n
E1/2
Eie[n] EG + u. (2 pa)1
2 E
+
7i 12 l2
E[ Eiefn] Ee + u. (2c, pa)1
n2 /1
where the expectation is with respect to {Ee. uz he(ng and the last step follows by Jensen's 's inequality and the fact that ((t) is a convex function for &.5
13

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
We next that by Bauchy-Sehward inequality,
E Σ [((((+u))
E HI[EE((1 E1(1+ (((++ 22)
Σ ([ +1 (1+
Σ E[ 1,) + [[ + u,] u,][[[1 uy] 24-
5n An(n
s v5n (5n(1- -p))
where we used that E are independent for i j, and independent from u,'s. s. In addition, [(x)] [ P(y: T.) Py: T7) = 1- 2p. Also [[u,] 1 and L s 2, since us has unit sub-gaussian norm. Hence, we get
V5(1+ vT((1 2p)) {x= plll
P(sign (arign((1e,00 0o)) y) 2 +
(B.2)
|
We next use a classical lower bound on 4. Let (t) (1968), have for any 0:
(()) (((-)). Using Equation (7.1.13) of Abramowitz & Stegun
45(1) π
t
Since + 4 1) for 0, we get:
1
1
(²(t)
exp(-t²)
(B.3)
2m
t+1 1
2v
where we used that t 1+1st +25 2 Combining (B.3) and (B.2) we get
5(1 + vn(1 - 12p))) (xx
P(sign((z;00) 0)) +u) 2
exp
2
| 12,
which completes the derivation of (oo(2) (æ).
B.2 Upper Bound (x)
We continue from (B.1), which reads
P(sign((z,00) 0o)) # +)) = E ②b (Eisjn) (i (yz.,
(B.4)
Σ E1/2
where the expectation with respect the randomness in training data, namely u; and & for i e [n.] while the test point (x, y) is fixed.
Note that under our data model, (yar 14) = (1 + u) |u|2 = =1++ since a is non-negative random variable, next define the following event:
En
Σ 2 21-)2 [c[m]
(B.5)
Recall that [[{:] 1 2p and by the Hoeffding-type inequality for sub-gaussian random variables,
(1 Σ ( [1E
(-6
12
(0(1-2p) (1 E[ue)] 2t) s 22exp
8n
14

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
(Note that [5:(1 u2 s lusllv2 2.) By choosing / n(1 2p)/2. and using the fact that uy 0 for all i we get
Σ E u.) < (nn1nn21p))))) (n(122p)/2 2exp (- 1--11 (111-1 (1-1p))
P
Hence, P(E)) s exp (-32 (2(11pp) 2p)²).
We then have
(Eien]] Si(1 + u;)) (yz))
CEi[a) 5: + (2z))
E
= ②
(1&, 1c;))
vn Σ 2
vn
Σ 12
n(1 2p) pL)
$ F
+
1
+ +P(E))
2/7
2/
n(1 2p p.)
((E)) + (P(E)
2/n Σ
n(1 2yx pe)
$
+ +P()))
2/77 Σ1/20r
where in the first inequality we used the observation that (yæx μ)) 2 0 as explained above, the definition of &g and that d a decreasing function in 2.
We next recall the tail bound of normal distribution in Equation (7.1.13) of Abramowitz & Stegun (1968):
1/2
(+) S
e
-212
for all t 2 0. where (t(t)= ((t) ((-)) is the complementary CDF of normal variables. Using this bound and the bound we derived on P(Ei) we get
(Eeem) Ci(1 us (yzr) 14)
n(1 - 22) 2 1a)2
E +
exp
+2exp
(1 2p)²
Vn /
8 8 1/
32
By invoking (B.4), we obtain the desired bound Cn (x:).
C Proof of Theorem 4.2
We will first derive the lower bound on err( Using Theorem 4.1 (and because the training set T has measure zero), we have
err( (o)) 2 [[ao(x)]
1
5(1+ + 7 2p)) 2 (xx, 1u)
E
exp
2/2
|///200 1|2
5(1 + vn(1 22)) (ar, (2),
(x, 12)2
(x. p2)
2
E exp
S 2²
p
5 5
2/2T
|
1// 2
2 1
1
(ar, 12)
2
exp (-5(1 1 VT(1 -2))
$ $12
(C.1)
2/2T
||
2
15

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
for any value of O. We next lower bound the probability the right-hand side. We have
(x,
p4)
[ + u)
P
$ v
P
SU
Σ 1
Σz Ez1e
82
(1 + u)
P
SU
Amin
P4= lez
(1 u²
P
(C.2)
|PA
where the first step holds since under our data model we have (æ, (1) u((+u) I|lelle, and 1 ==<===((tt))""" u+Σ = Ez.
given that 1/ 0. Here Pj the projection onto the orthogonal space of j.. Continuing from (C.2) we write
u)² |
S udmin
P (1+u) < ummin v d/2,
PA=111, 2 vd/22)
=P =P((1+ u) S ummin v d/2) (1Pt vd/2)
(C.3)
given that and u independent. Next note that Piz is distributed Gaussian vector in (d 1) -imeensioa space, and therefore ||P==lle, follows the chi-squared distribution with (d 1) degrees of freedom. Using the tail bound of the chi-squared distribution (see Theorem 4 of Ghosh (2021)), we get:
P (IPM2=11 < d/2) s d/16 = P ((|p)=
d/2) 2 - 1--1-1111 44/16
(C.4)
We next lower bound the other term the right-hand side of (C.3). By Markov's inequality for any non-negative random variable X, we have P(X s 2E[x]) 1/2. Also [[{1+))> 2y², since E[[u] 1 and therefore, by choosing v= 4v2y² we get
Amin v
P [11 vmmin v d/2 1/2.
(C.5)
4v2n²
Combining (C.4), (C.5), (C.3) and (C.2) with (C.1) and plugging in our choice of Amia
we arrive at
err 0o)
exp 1660 + v 2p))²
(1-6-4/16) d//66)
4
X
Let us now derive the upper bound on err er)() Using Theorem 4.1 (and because the training set T has measure zero), we have
err (0)) [x))
n11 - 2p) (ar, 21)2 E exp
+ 2exxp -2exp((200 n
(-3 (-30(1 (1
(1-p)))
(C.6)
2
2 11/20
Under our data model, x= y(1 u) + 1/22 z. Consider the probabilistic event Eg == (z | s 2dd. For every 0, have
(ax, 12)2
71 1u)
exp
|
= exp
//0/2200 ?
(1s, + 1gg)
1/7²
S exxp
P(ES),
2Xmaxd
16

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
where the inequality holds because (ze, (t) y01 u) due to which (2x, sa) 2 72 (given that is non-negative random variable) and because
Σ 12 x i2 = =>= $ Amax || s 2
2
when event & happens. Further, |=|lē, ~ xa and so using tail bounds for xa (see Theorem 3 of Ghosh (2021)), we have P(EG) se e 4/8, Putting things together, we obtain
E
exp
n/ p4)
$ exp
177"
+ t
/
22 d
Setting 77 n(1 m11-2p)) 288 and using this in (C.6), we get
err err(ou) exp
n(1 2p) 9/4
16X +e e-
+2exp +eexp
( (1-2p)))) (122p)²)
{32
D Proof of Theorem 4.6
Proof. Since are interested with dependence of sample size with respect d and p. we assume 7 |p|le 1 and = I- "hu1 the projection onto the orthogonal space of μ. Also note that without loss of generality, we can assume that our estimator 0 has unit norm, because its norm does not affect the sign of (xx 0). This way, μ and both belong to Sd-1,
We first follow a standard argument "reduce" the classification problem a multi-way hypothesis testing problem. Let p 1) be arbitrary but fixed value which
choose. We define p-packing of Sd-1 set M [MI...., p gd-1 such that (P) p&) p for 1 # k. Also define the p-packing number of Sd-1 as
M 1 sup N there exists a p-packing M of S with size M).
(D.1)
For convenience, we define the misclassification error of classifier 0 gd-1 when the ground truth separator is as err( 0::10 (1) = (c:(0; 14). As per our condition.
2 sup err( (0) $
14) 2 sup err(O 11)
(D.2)
paM
In order further lower bound the right hand side, let / be random variable uniformly distributed the hypothesis set 21. M) } and consider the case of μ pa, We also define I as the index of the element in M with maximum inner product with 0 (it does not matter how we break ties). Under our data model we have (æ, 12) y(1 u) | 12 y(1 u) and since is non-negative random variable, y sign((ar, p4))). We then have
(ar sup e max IP (iign( (xx 11)) sign (ar, (igu(( 1)) MeM
ie ic[M]
M P
sign ((, sign (zc, θ7){ =i)
M
1 p - 2
Σ P(T+ i[
(D.3)
M
E
I+P p 2
((I+1).
(D.4)
with & denoting the CDF of standard normal variable. Equation (D.3) above follows from the lemma below.
Lemma D.I. For any i [M]. we have
P (siin (sign(((x,,)))) 1))) # sign((æ, r =1) - 2/
1 1+
P(T +[]+ i/ i).
17

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Combining (D.2) and (D.4), obtain that
60
P(I+ + 1).
(D.5)
Φ 2
I+p 1-p
Next recall the set T := {(z,, Dy) je[m] and let X = [ ..... J e RRaxd and y "ai......]]] By an application of Fano's inequality, with conditioning on X (see e.g.. Section 2.3 of Scarlett & Cevher (2019)) we have
x(I 2 (1 - 50) log (p, )) 2
(D.6)
where I(;;ī{x represents the conditional mutual information between 7 and T. Using the fact that I - 7 - 7 forms Markov chain conditioned on X, and by an application of the data processing inequality we have:
I(1 s [1
(D.7)
We will now upper bound X() Let wy := (sign( (2 11)) + 1) be the 0-1 version of the actual label of æj. viz., sign( (r)) As per our setting, we have Ty 2 W, @ 23) - where 2j ~ Bernoullip)) and e denotes modulo-2 addition. Since the noise variables 2j are independent and 7, depends XI only through wy = (sign( (z),, 1), by using the tensorization property of the mutual information (see e.g.. Lemma 2, part (iii) of Scarlett & Cevher (2019)), we have
I(l:y(X) EI(witt)> S mn(lo2-Ha(p)). j=1
(D.8)
where the second inequality follows since Tj is generated by passing wy through a binary symmetric channel, which has capacity log 2 H2(p) with Hz(p) == -p pog - (1 - p) log (og(1-1) p) denoting the binary entropy function.
We next use the lemma below to further upper bound the right-hand side of (D.8).
Lemma D.2. For discrete probability distribution, consider the entropy function given by
H(P 1.P0....PPP0. PK) Σ pk log(1/pk))
We have the following bound:
k
H(p.....,Pa) log k (pi 1/k)²
1=1
Using Lemma D.2 with l we obtain log 2p) s 4(p 1/2)2 (1 - 22 which along with (D.8), (D.7) and (D.6)
gives
(1 - -2p)² + log 2 log (p)
(D.9)
1 1000
In our next lemma, we lower bound M (p,Se Sd-1).
Lemma D.3. Recall the definition of p-packing number of Sd11 given by (D.1). We have the following bound:
dp
M(p S exp
Using Lemma D.3 along with (D.9), we obtain the following lower bound on the sample complexity:
0² (1 5n)d log? n 2 2 (1 2p) with on
& 2
Ite I-p
Note that e (0, 1) can be set arbitrarily. Since our claim is on the order of n, the specific value of can be chosen based on to ensure p² 2 (1 60) is of the order of (1 - 6)). This finishes the proof Theorem 4.6.
18

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
We will now prove Lemmas D.I, D.2 and D.3.
Proof of Lemma D.1. Let consider the event 7 # i, given that 7= i. We note that if 7 7, then (0. $ V lte Otherwise, by definition of 7 we have (0, 24) (0, 11)
equivalently, the angle between 0 and by is b b cos"
I+D
Ite and therefore the angle between Mt and μ, is 26. Noting that cos(26) cos2 (b) 1 p. we would then have (PT, which is a contradiction since M forms a p-packing. We proceed by writing
2
P (1)) # sign((æ, (1x,0)))== = 2 (sign((a; 11)) # sign((æ; (0)n((200)11 =i, =
As discussed above, on the event that I i, I # i, we have 0 (0,
1te
Consider the decomposition æ
(x, p:) Pit a. We then have
(sign((æ,, (4)) sign((æ, 0)}[T x (sign((æe, pa)) ((xr, 14)0 + P Pi 0)) s $0 =1 i, +
Note that æ is data point, independent the training data T and so is independent of 0. In addition, under our data model, (x. (4,) is independent of Pi,, Hence, sign((æ; (4) (P)) x. Pi, 0) NN. ||P 0 2 Given that ||] l2 1
1 (0, 2,) = 1 - 0², In short, we can write also have | Pa. 0 2
(P)
v1- -822, Z~N(0,1).
Using this characterization, we proceed by writing
(sign((2 (z,, 11)) # sign((æ, 0) |= = i) = P sign (x, (z)))((( mz) v1 -11000+-11101000)))
(xx 14)1
PP Z s
VI - 02
0
/ 02
(8)
1- $
P
(xx, Mil1
(6)
+ P+ [E((K
2
0
P
(0)
1 P
1
2
-
2
1 1-p p
where (a) follows from the fact that 0 Ite: (b) holds due to Jensen's inequality and concavity of ++-) on the positive
values, and (c) holds because under our data model [x, u1)l E[y(1 u) || 11,]1 E[1 u]] s since |ules 2 1. This completes the proof of claim.
19

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Proof of Lemma D.2. Define 9: P: 11/k. Note that di can be negative, and we have Σ 4: = O. We write
H (p1 ...................... PP)) Σ Pi logp:
E11k q:) log(1/k+
())g(())))))) log(1 + kq:)]
2 log k
(1/k +.)
(D.10)
1=1
log k: Σ d/
i=1
log k k Σ (p= 1/1))²
Note that in Equation (D.10) we used the fact that + kg. 2 0 and log x s x 1 for all x 2 O.
This completes the proof of the lemma.
Proof of Lemma D.3. Define a p-cover of gd-1 as set of V := (Ui,.... UN) such that for any 0 e sd-1, there exists some vs such that (0, v,) 2 The p-covering number of Sd-1 is
((p inf there exists a p-cover V of 5d-1 with size N).
By a simple argument we have M(p (d Concretely, we construct a p-packing greedily by adding an element at each step which has inner product at most with all the previously selected elements, until it is no longer possible. This means that any point on 5d-1 has inner product larger than p by some the elements in the constructed set (otherwise contradicts its maximality). Hence, we have a set that both a p-cover and a p-packing of Sd-1, and by definition results in (p, Sd-1) 2 (p, Sd-1).
We next lower bound (p, 1 via volumetric argument. Let V (v1...., v; V we consider the cone around it with apex angle cos Its intersection with gd-1 defines spherical cap which we denote by C(v,,) p). Since V forms p-cover of gd-1, we have
2N) be p-cover of S For each element
Vol(5 Vol(u.N,
Σ Vol(C(u;,)))
We next use Lemma 2.2 from Ball et al. (1997) by which we have ((u.,)) Vo s e dp²12, Using this above, we get
i Ne do²112
for any p-cover Thus, we have ((p, Sd-11 2 exp( dg*) ) which completes the proof of the lemma.
E
Comparison with Other Lower Bounds for Learning with Noisy Labels
Cai & Wei (2021); Im & Grigas (2023): Zhu et al. (2024) derive some noteworthy lower bounds in much more general settings than ours; naturally, their bounds are weaker than our bound in Theorem 4.6. In the work of Cai & Wei (2021), our setting corresponds to np = 0, n2y = n. As per Theorem 3.2 of Cai & Wei (2021), the lower bound on the error is effectively" O( (ta) ) So when << d, this lower bound yields much worse sample complexity than our result in Theorem 4.6. In Im & Grigas (2023), the lower bound on the error (Theorem 2) does not reduce with so even if there are infinite samples, we cannot get zero error in the worst case. As for Zhu et al. (2024), their lower bound on the error (Theorem 1) also has a non-diminishing term depending on e. In the special case e 0 (or being small enough), there an n -12 dependence but no dependence on the dimension or a related quantity. However, the upper bound in Theorem therein does have a dependence on a VC dimension-like quantity as expected, so their lower bound is probably loose w.r.t. dimension.
PThis because / s as per Definition and aB d as per the paragraph after Remark 3 (of Cai Wei (2021)).
20

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
F
Proof of Theorem 4.8
Similar to the proof of Theorem 4.1, we want to upper bound ((y 01) < O). Plugging in 0 from (4.8) we have
yla, 01) (xx, Σ y (ar Σ sign (( 0o))
n
n
A major complication is that 0, depends on all the data points in the training set. Expanding 0, get
0o 1 T... Eiya ! n (( +1 u))) 1 E E1y1
(F.I)
n n
Thus,
Te sign(((;;))))) Oo)) sign (oe, (E (.((++,)) +112 3/1256 {iNiizi)
(F:2)
Here the outline of our proof:
For every e [n] we define the dummy label
V
sign ( 1 E1 u)) E'' (
(F.3)
Note that T/P depends only on zy, whereas Te depends on all (zi)een)
We define the event == {ve: 77 sign((x; 0o))}-
We have
P(y(x, 01) <0) P(y(x, (1)(x,00))<00 P(()) 01) < 00 s (y((( , 0,) < 0) P(E").
(F.4)
We bound each of the term on the right-hand side separately. Note that under the event E, we have
y(x, 01) =
y (x. T(e)).
We will control the probability of the RHS above being negative using concentration results on the sum of i.i.d. subgaussian random variables (with appropriate conditioning first).
Next we get into details of this proof outline. We start by bounding PPEE).
Lemma F.1. Fix & [m]. Suppose that nd 2 Define p' = (1+ 8x2 8r2 nd )p. We then have
3,
(1%- sign((æ;, 0o1)) (1 0o) <0) 5 exp
(1 (1-1200) + J
812
max
Using Lemma F.1 along with union bounding over E [n] (note that the events are dependent), we get
P(E9) < n 2
12 /)) (1- 2p')
+e +e +e-d/10) c4in.
cxp
(F.5)
812 max
where p' = (1
2 nd )p.
5X2
Noto that P(sign((m, 0,)) + v) = FFy(a,, 0.) +).
21

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Next note that under the event &, we have:
a( 01) = y (xx T((r)) 1 ΣE ysigu (mr, TE [e[m]
((0)))))) (c, wz).
(F.6
n
We define the shorthand 3:= Σ, 5: (1 u:) and condition on B. Then (F.6) will be sum of i..d subgaussian variables
T = ysign (( Bp > seweze)) x1), Le [n].
(F.7)
We continue by first characterizing its expectation.
Lemma F.2. Suppose that 082
1 and d 2 7. Then for & E [n]] we have
2Amsed
E [[T (1-2q) (yx p2) 0,
where q exp (-
9-2
207mox
Recall that xt Ve(1 ue) E1122 z5 and therefore
- [[ s T2 10 (ax, xx)) 102
=2 (ar, ye + ue) uet E 321222))lv0 ze)ll
s 44((,, wk) + 2 >1/2001e,>
where we used the assumption |wellv = and the fact that || 1/ 1
Next by using Hoeffding-type inequality for sum of sub-gaussian random variables (see e.g., Proposition 5.1 of Vershynin (2010)) we have for every t 0,
P Σn E[[T/ST] 2 2dp) s 22exp
t²
64m((z, 22)2 + Σ 12/2200
Therefore,
1 Σ [[T.B]]] 2 ΣE[T]]8] 3 To {0
3(E[T]]3])
$ 2exp
64((x; n2² + 1 |20200
n(1 29) 2yyz, 1e)2
$ 2eep
(F.8)
64((x, ((((x,,))2 + |
where the last step follows from Lemma F.2. Recall that exp
Bn2
20
Our next step is to take expectation the above with respect to 3 Σ, (i(1+ u;). Before proceeding we define the following event:
Eo = (B2
(F.9)
Note that by Hoeffding type inequality for sub-guusse gaussian random variables and given that E[G:] = 1 2p, we have
(1 E (11) )
2 $ 2cxxp
8n
By choosing t= n(1 /2) and using the fact that u, > 0 for all i, get
[ us) < <n 22)/2 2 exp
(- n (1 (1-2p)²)
32
22

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Hence,
(-22 (1 (1-
P(E)) 2 exp
We now continue by taking expectation of (F.8) with respect to
n(1 - 224)² ( 12)
P Ti < 0) 22
exp
64((2, 12)2+ + |
8
n(1 - 22))2222 2yxx, 1e)2 64((2, 14)2+ + /01/2200 1012
2E exp
(1s0 + lEG)
n(1 - 11)2
$ 2E exp
18 2P(())
(F.10)
64((x, 12) + |>>1/20011
On the event Eo we have
By
n(1 2p)
1,
2X 2mmax
4mmaxx
by our requirement in the theorem statement. Therefore,
3y2 20
(o(1-2p)))
q = exp
S exp
=
40
Since 1 1-2g2 1 22/ > 0 this implies that
n(1 - (3/x, 22)
n(1 - 22"'22 12)
E exp
1ca
S E
exp
1ca
64((x, 12
64((x, 12) | 20
ni(1 - 2244)) (xyc,, 12)2
$ eexp
64( 1u)2 11/200
Using the above bound along with the bound on P(E)) into (F.10), we arrive at
- ((1-24()2 11)a 64((xx (1)( 11)2 + Σソ
P s 2exp
+ 4expp
(1 2p)²
(F.11)
32
Invoking (F.6) and the definition of T: given by (F.7) we obtain
P(v(e, 01) < 0; 2exp
n(1 - 2 14)2 (A((x,)12 11/2 (2)
4exp
-- (1 (1-)p²²
71
2p)²
(F.12)
32
Finally we combine (F.12), (F:5) and (F.4) to get
n(1 (11-2g) 22'))2 (g/ar, 21)2
F(y(,,0) < 0) 2exp
64((x, uu)2+ / ||
4exp
n (1 2p)² 2
exp
7
(1 - 22')
+e
-/16 d/n
(F.13)
32
812
This finishes the proof Theorem 4.8.
We will now prove the intermediate lemmas and F.2.
23

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
F.1
Proof of Lemma F.1
First note that PP (Te sign(( 0o))) IP (Tg 0o) < 0).
Define غ = E (1 u.). Then using (F.1), we have
Ve (oc, (EE) 2 Eeyeze+ E Σ E(yiz.). (2 0o) n
in?
We have E (n ( and so 17 E Eiee Eiy1eis) is a zero mean Gaussian with variance (n 1) 20 E Let Fi be the o-algebra generated by (=t, Mes (Ee, uit se(n)). Note that Z;, for l, is independent of F/ and Ty is Fe-measurable. Hence,
8, (E: >
13 EcyoZE)
PP (Telar,, < = $
Vn-1 11/230
[2ee (E, Ee) Elleee
(4) ①
Vn-1 E1/2x0e llez
(xzz, Ee E 11 Eeyezze
(0)
5
exp
2
2n
(c) 1
(2te (4) E2)
(xx, 1/ 32/22e) )z)²
S
exp
exp
82 4n Σ1/200
2n /2//200 1|
1
(2e, (E, 8
||
$
2
exp
4n Σ 1/2 x ||
exp
2n
(d) 1
{2, Er)
[ 1
S
2
cxp
4n maax
|
2
exp
2n
(F.14)
Here, (a) follows by the choice of T/: (b) holds by using Equation (7.1.13) of Abramowitz & Stegun (1968):
e/2
1 12
(t(t) S
t+ 12
2
for all t 2 0. In addition (c) holds since (a + (a2 > 2 b² Also, (d) holds because under our data model we have 1/2 x, Σz, and so 1///2 t, S Amax |zele, Further, (xx,, 14)| 1y us) || 2 2 72 because uz 2 Putting these bounds together, we have
(xt, 14)
x2
2 Amax Zz |2
E1/a 6s
We proceed by taking expectation of the right-hand side of (F.14) with respect to E.. Define the shorthand 1n22 in>2.n11=112, Fix an arbitrary 2g for now (we will determine its value later) and define truncated parameter
24

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
A = min(A,A0) Ao). We have
E (
S S(E,E)]
(F.15)
= AIx()+)))
se An
| (c. ((
iej
>"
(<E[(11p)e" -d(-t)) pe (laa)) ()(m-))
se An ((1-p)-** pe Eledu] m(n-1)
se An ((--))e* 1 pet (2/2) mlu-1)
= An² (1-p+ p pe 23 22. u(n-1)
(F.16)
Here, the first and the second inequality follows from u, 2 0. The third inequality holds since u has unit sub- gaussian norm and moment-genet semeent-generating function is bounded as E[c^"] s 1²122
We next further upper bound the right-hand side of F.16 to get simpler expression. In doing that we use the following lemma (proved in Appendix F.I.I).
Lemma F.3. For t 3, have e' - -1s+tt
By choosing λo 0.2 we have 2Au + 2//2 1/2 and so 2 X2/2 1/2. Using the above lemma, we have
X2/2 (2X+ X²/2)² 22+2212 -1 15
= 2 X2/2 +4/2+443+ X+/4+ 2X3
$ 2X + 7 ( 42o + 1 21/)
$ 322 6λo)
where we used Ào s 0.2 in the last step. Next using the inequality 1 1 x S ex for O, we get
(e 2xxx88/2 1)p 1 (2 6λg 6Ao 1 12 (2+020)
By using this bound in (F.16) obtain
E[e E[e-MErE)] $ e- (2=600))))) -
(F.17)
with p/: (1+ 3Ao)p.
Using the above in (4.14) and then taking expectation with respect to 2₁ we get
Ize 122
P (Te 0o) <0)
exp (-(1 (-11-2p') 22p') exp
2
2n
11/2
1/2
)r2)) (2p(1=2)))r>))) $ E [exp (-2(1- 22p')
exp
(F.18)
2
by applying the Mauchy-Schward inequality.
Using the moment generating function of x distribution, we have
E
exp
zt 2
1
2]
2
-d/2
d/2
s 2d/n
(F.19)
m
25

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
for ri Here, the inequality (1-2)-+ 2 for x [0. 1/2].
We continue by bounding the first term on the right-hand side of (F.18). Define the event & follows:
E == {|zelles & v2d].
(F.20)
We then have
E [ex (-2(1-2p')An)
E exp ( (-2 - 22') 2n') (1e, + 1e;)]
< E exp
(-2 An² 1s, -[[,
(a)
7d
E exp
(1-22/)) 1 P(E))
4
72t
20 11 + +P(ET)
s exp
(1
(F221)
4
Note that in step (a), we used the fact that on the event ε we have X2 ( nd) and we choose λg = = (8A nd). This way, we have Ā min(A, Ao) = = (u) Also note that by our assumption in the statement of the lemma, we have do S 0.2 which the condition assumed in deriving (F.17).
We next bound P(E)). Since zς NN, Ia). =elliz has x² distribution with d-degrees of freedom. Using the tail bound of x² distribution (see Theorem of Ghosh (2021)) we have [[[ I., 2 2d)= s -d/8 and so
P(E)) s e( 2 2d) s d/8
Using the above in (F.21) we obtain
(- 72 (1- 2p') mm
E E[exp (-2(1-2p')) Xnn) exp
- 2p')
+ 1-81
(F.22)
By combining (F.22) and (F.19) with (F.18) we arrive at
72
1/2
P (a 0o) < <0)
s
cxp
(1 2p') 12
+ c///88
c//
2
412 max
d
1
12 (1-2p')
+ 4/16
cann
$
exp
2
812 max
d
which completes the proof of lemma.
F.1.1 PROOF OF LEMMA F.3
Using the Taylor series expansion of c we have:
, s P
e 1=t+ - + Σ
(F.23)
2 1-3 j!
+ - Σ 1
12
st+
(F.24)
2 2 !
+ 6- 5
2
=t+
(F.25)
2 2
2
(F224 follows by using the fact that for j 2 3 and t <
2, ti
3
7. (F:25) follows by using the fact that el 1
1+1 1 -ド- j! after plugging in t in Equation (F.23).
2
Next, using the fact that in (F225, we get:
3t
c - <tt
<t+
(F.26)
4
This completes the proof.
26

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
F.2
Proof of Lemma F.2
Under our data model we have = ye(1 + ue) ue Σ zz. Substituting for 2 in the expression of Té, we get
T3 sign ((v (1 + ue / zt, 3p EeVe =1/2z))))))) (yar, ye uz) p E
sign ye u EoVe E ze Es (yar, ve ue Σ ze),
using the fact that 1 ta= Taking expectation we get
sign ye (1+ uz) Erye |2122e11 (eelel1)) (vee, ve(1 ue)ee) [
B[
since the other term will be an odd function of zę. Letting
2o P (1 (1+ ux)
+e Ex/2zelle, <0).
we get
[[T,]3] = (1 (yx,, (1 uu+) (1 2 1i)
(F:27)
because uy> > and (yz, μ)) > 0, given the positive margin in our data model, and go 2. So what remains is to show that Qu S q 1/2.
We write
40 s (1 30?
Amax
1elle2 <0)
gy2
$
< 1|zell2z
(since de > 0)
Amax
< exp
20.mmax
9-2 1, where the last step follows from the observation that || ~ x3 and using the tail bound of x3 (Theorem
2nA
of Ghosh (2021)). So when Bn²
1 and 2 7,
2dAmmax
By² 20
Se 5--1
d/10
40 q= exp
Plugging this into (F:27) completes the proof.
G Proof of Theorem 4.9
Using Theorem 4.8 (and because the training set T has measure zero), we have err(0,) s [[[a(x)]]. Based on our data model, æ = y(1 + u) 1/22,
2. Consider the probabilistic event &g == {z: || 12 s 2d). For every > 0, we have
(ar, )2)
1)(, 12)
E
exp
= exp
(1s, + 16s)
(x. 1)2+ + ||
(xc 11)2
1/ 2z 1
117
< expp
P(E))
7 + 2X2
where the inequality holds because (x, μ1) = yy1 + x) and so (z. 1122 a (since u is a nen-negative random variable). In addition,
b 1/2 =|E213, < X2 2 |==1|², < 212
27

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
under the event Eg. Further, ||
xa and so using tail bounds for xå (see Theorem 3 of Ghosh (2021)), have P(E2) Se S--/88 Putting things together, we obtain
E exp
(ar, 12)
11(2,, 14)
2 1/
exp
74 2X max
1/7
+ te te-
62
The claim of theorem follows by setting 7)
24/)²
28

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
H Remaining Experimental Details
Here we provide the remaining details about the experiments Section 5. Our experiments were done using TensorFlow and JAX. In all the cases, we retrain starting from random initialization rather than the previous checkpoint we converged to before RT; the former worked better than the latter. We list training details for each individual dataset next.
CIFAR-10. Optimizer is SGD with momentum = 0.9, batch size 32, number of epochs in each stage of train- ing (i.c.. both stages of baseline. full RT and consensus-based RT) = 30. We use the cosine one-cycle learning rate schedule with initial learning rate = 0.1 for each stage of training. The number of epochs and initial learning rate were chosen based on the performance of the baseline method and not based on the performance of full or consensus- based RT. Standard augmentations such as random cropping, flipping and brightness/contrast change were used.
CIFAR-100. Details are the same as CIFAR-10 except that here the number of epochs in each stage of training 40 and initial learning rate 0.005.
NomainNet. Details are the same as CIFAR-10 except that here the number of epochs in each stage of training 15, initial learning rates for the first stage of the baseline in Tables 7, 8, and 9 are 1e - 3, 5e - 2, and 5e 4, respec- tively, whereas the initial learning rate for the second stage of the baseline as well as full RT and consensus based RT is 1e-3.
AG News Subset. Small BERT model link: http:s/s/www..ggggeeecco///////s
Eramewozkss/ensoorfle. BERT English uncased preprocessor link: http:::://wwww.agggl. rehub- senssorflow/bberr//raeweeerkrkt /ttteeewwwrkk//ssso/o//s low2 searrraaion/eeennnnee prtptasddppeepprrrssseeeeeeee / www.eesssoowwwoooooooooooooww
fet rect=t Optimizer is Adam with fixed learning rate le- - 5, batch size = 32, number of epochs in
each training =. 5.
Accuracy over the Entire Dataset and over the Consensus Set in the Case of AG News Subset
Here we list the accuracies of the predicted labels and the given labels over the entire dataset and the accuracy of the predicted labels (= given labels) over the consensus set for AG News Subset. Just like in Table 3, the accuracy of the predicted labels over the consensus set is significantly more than the accuracy of the predicted and given labels over the entire dataset. This explains why consensus- based RT performs the best, even though the consensus set is much smaller than the full dataset (~ 28%, 32% and 38% of the entire training set for the three values of e).
Table 11. AG News Subset. Accuracies predicted labels and given labels over entire dataset and accuracies of predicted labels (= given labels) over the consensus set. Conclusions are the same as in Table 3.
Acc. of predicted labels on full dataset
Acc. of given labels on full dataset
Acc. of predicted labels on consensus set
0.3
53.20 =: 2.82
32.52 a 2.05
61.81 a 2.66
0.5
66.78 1.31
35.5 + 0.14
76.48 0.93
0.8
79.98 0.80
42.53 + 0.13
89.59 0.43
J
Consensus-Based Retraining Does Better than Confidence-Based Retraining
Here we compare full and consensus-based RT against another strategy for retraining which we call confidence-based retraining (RT). Specifically, we propose to retrain with the predicted labels of the samples with the top 50% margin (i.e., highest predicted probability second highest predicted probability); margin is measure of the model's confidence. This idea is similar to self- training's 's method of sample selection in the sumi-super setting (Amini et al., 2022). In Tables 12 and 13, we show results for CIFAR-10 10 and CIFAR-100 (in the same setting as Section and Appendix H) with the smallest value of from Tables and 2, respectively. Notice that consensus-basee RT is clearly better than confidence-base RT.
29

---

Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Table 12. CIFAR-10. Test set accuracies (mean = standard deviation). Consensus-bused RT performs the best.
Baseline
Full RT
Consensus bansensus-based RT Confidence-bassee RT
57.78 + 1.13
60.07 0.63
63.84 0.56
62.09 0.55
Table 13. CIFAR-100. Test set accuracies (mean é standard deviation). Again, consensus-based RT performs the best.
Baseline
Full RT
Consensus baased RT
Confidence-based RT
3
23.53 + 1.01
+
29.98 + 1.11
24.99 = 1.25
K
Retraining is Beneficial Even Without a Validation Set
In all our previous experiments, we assumed access to small clean validation set. Here we show the results of training ResNet-34 on CIFAR-100 when we do not have access to a validation set and train for 100 epochs, and also compare them against the corresponding results with a validation set where we trained for 40 epochs (Table Section 5). The point of these experiments is to show that retraining can offer gains even without a validation set, which case we train for too many epochs and expect overfitting. Please see the results and discussion Table 14.
Table CIFAR-100 w/ ResNet-34 without (top) and with (bottom) validation set. Test set accuracies (mean standard deviation). Note that retraining (in particular, consensus- RT) Icads to improvement oven without a validation set. However, the performance amount improvement obtained with retraining are worse in the absence a validation set due to higher degree of overfitting. This is not surprising.
Baseline
Full RT
Consensus-based RT
4
26.03
1.75
28.33 # 1.76
30.47 1.31
Without Val. Set
5
42.50 = 1.14
44.43 # 1.27
46.27 1.72
c
Baseline
Full RT 39.33 1.37
Consensus based RT
With Val. Set
4
37.53
1.58
43.87 1.62
(Same Table 4)
5
51.13 0.69
52.33 0.38
55.43 0.42
L Beyond Label DP: Evaluating Retraining in the Presence of Human Annotation Errors
Even though empirical focus in this paper has been label DP training, retraining (RT) can be employed for general problems with label noise. Here we evaluate RT in setting with "real" label noise due to human annotation. Specifically, we focus on training ResNet-18 18 model (without label DP to be clear) on the CIFAR-1 -ONN dataset introduced by Wei et al. (2022) and available on the TensorFlow website. CIFAR-IOON is just CIFAR- labeled by humans; thus, it has real human annotation errors. The experimental setup and details are the same as CIFAR- 100 (as stated Section 5 and Appendix H); the only difference is that here we use initial learning rate 0.01.
In Table 15, list the test accuracies of the baseline which is just standard training with the given labels, full RT and consensus-based RT, respectively. Even here with human annotation errors, massensus-based RT is beneficial.
Table 15. CIFAR-IOON, Test set accuracies (mean standard deviation). So even with real human annotation errors, consensus-bused RT improves performance.
Baseline
Full RT
bossensus-based RT
55.47 + 0.18 56.88 0.35
57.68 + 0.35
30


Reviews:
[{"review_id": "AQzkNGgPl0", "reviewer": "Reviewer_nHoC", "summary": "The paper gives a theoretical treatment on when learning with predicted hard label is beneficial than learning with original noisy label.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review and great questions!\n\n**(A) Label DP setting.** We focused on this because it’s not clear how to apply existing noise-robust techniques on top of existing label DP mechanisms, while retraining is a simple post-processing step. For e.g., as mentioned in lines 365-366 right column, it’s not obvious how to apply forward correction to the second stage of Ghazi et al 2021.\n\n**(B) Form of classifier $\\hat{\\theta} =  \\sum_i y_i x_i$.** This is a simplification to the least squares’ solution (LSS) obtained by removing the empirical covariance matrix’s inverse. The way to analyze the LSS would be to bound the deviation of the empirical covariance matrix from the population covariance matrix (which shrinks as $n \\to \\infty$), then analyze with the features pre-multiplied by covariance matrix’s inverse. This would just make the math more tedious w/o adding any meaningful insights. Also, as we wrote around eq. 4.3, our classifier is similar to kernel methods with the inner product kernel & it has been used in the highly-cited work of Carmon et al 2019.\n\n**(C) Experimental setup more aligned with theory setting** \n\n1. Setting of Fig. 1 corresponds to our theory setting; see Appendix A.\n\n2. We did linear probing (LP) for CIFAR-100 with features extracted from a ResNet-50 pretrained on ImageNet. The setup is similar to our full fine-tuning (FT) experiments; we omit details here due to lack of space. Results:\n\n|$\\epsilon$|Baseline|Full RT|Consensus-based RT|\n|---|---|---|---|\n|$3$|$55.26\\pm0.19$|$60.97\\pm0.21$|$\\mathbf{63.37}\\pm0.26$|\n|$4$|$64.83\\pm0.39$|$66.67\\pm0.33$|$\\mathbf{67.83}\\pm0.37$|\n\n*So even here RT (especially, consensus RT) yields good gains*. Note that LP performs much better than full FT; this is often the case when training with noise due to less overfitting with LP.\n\n**(D) Line 197: perfect separable setting.** *Our modified GMM setting* (eq 4.1) is separable. As discussed in lines 172-176 right column, $\\theta^{*} = \\mu$ separates the data perfectly.\n\nWe’ll fix/clarify notational ambiguities. \n\n**(E) Questions for Authors** \n\n**1.** The ones in eqs. 4.3 & 4.8. Also see Appendix A.\n\n**2.** We introduced $u$ so that the margin of a data point $x$ along $\\mu$ is not the same. As explained in lines 172-175 right column, $|<x, \\mu>| = (1+u)||\\mu||^2 \\geq ||\\mu||^2$. If there is no $u$, all the points would have the same margin. We agree that from the analysis perspective, $u$ is not very important.\n\n**3.** For the binary case, see (B) above. Even in the multi-class case, something like this has been studied in reference [A] (see Section 2.2). Specifically, for $C$ classes, the labels $y_i$’s will be $C$-dimensional one-hot vectors, the ground truth $\\Theta^{\\ast}$ will be a $C \\times d$ matrix (features $x_i$’s are still $d$-dimensional, but $y_i$’s need to be defined appropriately in terms of $\\Theta^{\\ast}$ & $x_i$’s) and our predictor $\\hat{\\Theta} = \\frac{1}{n} \\sum_i y_i x_i^T$ will also be in $\\mathbb{R}^{C \\times d}$.\n\n**4.** *These lower bounds are in much more general settings than ours and so they are weaker than ours*. In [1], our setting corresponds to $n_p = 0, n_q = n$. Per Definition 2 of [1], $\\beta \\leq 1$ and as per the paragraph after Remark 3, $\\alpha \\beta \\leq d$. Now as per Thm 3.2, the lower bound on the error is effectively $n^{-O(\\frac{1+\\alpha}{d})}$. So when $\\alpha \\ll d$, this lower bound yields a much worse sample complexity than our result in Thm 4.6. In [2], the lower bound on the error (Thm 2) doesn’t reduce with $n$, so even if there are infinite samples, we can’t get 0 error in the worst case. As for [3], the lower bound on the error (Thm 1) also has a non-diminishing term depending on $\\epsilon$. In the special case of $\\epsilon = 0$ (or $\\epsilon$ being small), there is a $n^{-1/2}$ dependence but no dependence on the dimension (or a related quantity). But their upper bound in Thm 2 does have a dependence on a VC dimension-like quantity as expected, so their lower bound is probably loose w.r.t. dimension.\n\n**5.** Yes, Thm. 4.6 also applies to the retraining (RT) classifier. If you see Remark 4.10, the min. # of samples $n$ needed for RT to be better is **more than** $d/(1-2p)^2$, i.e., the lower bound of Thm. 4.6. And as discussed after Remark 4.10, this requirement on $n$ is probably tight (modulo log factors) because we can only hope the RT classifier to be better if the accuracy of the labels with which it is trained – namely, the initial model’s predicted labels – is more than $(1-p)$ (= accuracy of the noisy labels with which the initial model is trained); this requires at least $d/(1-2p)^2$ samples (per Thm. 4.6). So yes, RT can’t improve the sample complexity beyond $d/(1-2p)^2$.\n\nWe hope to have resolved your concerns and are happy to discuss further. If you’re satisfied, *we hope you will raise your score*!\n\n---\n\n[A]: \"Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View\", Thrampoulidis et al., 2020", "claims_and_evidence": "Yes, the claims were proved.", "methods_and_evaluation_criteria": "Overall makes sense to me. Though not quite sure why consider the \"label DP\" setup, seems to me a standard label noise setup suffices.", "theoretical_claims": "I've skimmed through the proofs, but have not checked the details.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The benefit of using predicted hard label is has been studied empirically, the theoretical treatment is new.", "essential_references_not_discussed": "Essential references are included.\n\n(Optional)\nthere can be some supplementary references that are related, see below.", "other_strengths_and_weaknesses": "Overall I enjoyed reading the paper. \nThe theoretical treatment of hard labels is new to me, and I think it is a good contribution to the literature.\nHave some concerns at this point, I will be happy to read the authors' comments and re-assess my review.\n\nMy biggest theoretical concerns are:\n1) The form of the classifier considered: \n$$ \\hat{\\theta} = \\frac{1}{n} \\sum_{i=1}^n y_i x_i, $$\nit does not correspond to any standard classifier.\n(At first glance, I would expect ERM or logistic regression type.)\n\nI look forward to see experimental setup that is more aligned with the theoretical setting:\n1) a data simulation that corresponds exactly to the theoretical setting, e.g., a 2-dimensional mixture of two Gaussian (and use the exact form of the classifier in theory). \n2) I think it is also possible to align CIFAR experiments with the theoretical setting, e.g., use a pretrained NN to extract the feature, then apply linear classifier on top of it (aka, \"linear probing\" in self-supervised learning). \n\nThese should provide stronger evidence to the theory.", "other_comments_or_suggestions": "1) Notation: in label noise literature, people usually use $\\tilde{y}$ to denote the noisy label, rather than $\\hat{y}$. $\\hat{y}$ is usually used to denote the predicted label by the classifier. This is a bit confusing.\n2) line 197: \"perfect separable setting\", I don't think it's separable, because Gaussian has infinite support, therefore positive and negative classes are overlapping. Do you mean \"Bayes decision boundary is linear\"?\n3) Eqn. 4.4: the notion $ P(sign(<x, \\theta>) \\neq y ) $ is overloaded, here it integrates $x$, while in Theorem 4.1, it is conditioned on $x$.", "questions_for_authors": "1) line 072, Figure 1: what's the classifier used to get the result? (linear, MLP, or the one in Eqn. 4.3/4.8?)\n2) line 217: why need \"u\"? It seems a bit redundant and does not seem to play a key role.\n3) Eqn. 4.3 & 4.8: my biggest concern, why the classifier takes the form of \n$$ \\hat{\\theta} = \\frac{1}{n} \\sum_{i=1}^n y_i x_i, $$\nit does not correspond to any standard classifier, and what's the multi-class version of it?\n\n4) Theorem 4.6 (minimax lower bound): I am aware of three (non-parametric) lower bounds in [1-3], so I would like to know the position of this lower bound in the literature.\n5) Theorem 4.6 also applies to the \"retraining classifier\" $\\theta_1$ in Eqn. 4.8, therefore, predicted hard label do not provide a gain in terms of rate/sample complexity. Then the benefit of using the hard label is only in terms of the constants?\n\n\n[1]  T Tony Cai and Hongji Wei. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 49(1):100–128, 2021.\n\n[2]  Hyungki Im and Paul Grigas. Binary classification with instance and label dependent label noise. arXiv preprint arXiv:2306.03402, 2023.\n\n[3] Yilun Zhu, Jianxin Zhang, Aditya Gangrade, and Clayton Scott. Label Noise: Ignorance Is Bliss. In Advances in Neural Information Processing Systems, 2024", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mTGG0l2joh", "reviewer": "Reviewer_hYpN", "summary": "The authors theoretically analyze retraining in a linearly separable binary classification problem and show that it can improve the model accuracy with respect to the initial training in presence of label noise. They show that retraining is particularly helpful with high levels of label noise. Then, the paper empirically shows that the proposed consensus-based retraining works better than the normal retraining.\n\n## Update after rebuttal\nAfter reading all the reviews carefully and considering the additional effort made by the authors, I decided to raise my score from 3 to 4. I think this is an excellent paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and great questions! We address your questions/concerns below.\n\n**Claims And Evidence:**\n1. We will clarify \"binary\" in the abstract. \n2. Here we simply meant a setting where we have labels for all samples - to distinguish it from the setting of self-training where we are *not* given labels for all the samples. We’ll clarify this.\n\n**Experimental Designs Or Analyses / first two weaknesses**: \n\n* Regarding comparisons with other noise-robust methods, please note that we are *not* claiming retraining is a SOTA *general-purpose* noise-robust method (see lines 100-103 left column). We are just advocating it as **straightforward post-processing step** that can be applied **on top of vanilla training or a noise-robust training method**. In case it wasn’t clear, Table 5 shows results wherein initial training (baseline) was done with forward correction applied to the method of Ghazi et al. 2021, and retraining was done on top of this. Please also see our response to your third question (under Questions For Authors) below, where we show that retraining is beneficial as a post-processing step even *when using a noise-robust loss function* instead of the usual cross-entropy loss. Moreover, it’s not straightforward to apply many existing noise-robust methods to sophisticated label DP mechanisms (such as Ghazi et al.); retraining is very easy to apply in contrast.\n\n* We didn’t release the code because at the time of submission, we didn’t obtain our organization's approval to release it. We weren't sure if code can be shared in the rebuttal because the email on rebuttal instructions didn't mention anything about code. We will release the code upon paper acceptance.\n\n**No theoretical analysis or comments for the multi-class case (Weakness 3):** Extending our analysis to the multi-class case is left for future work. Here is a starting point: in the case of $C$ classes, the labels $y_i$’s will be $C$-dimensional one-hot vectors, the ground truth $\\Theta^{\\ast}$ will be a $C \\times d$ matrix (features $x_i$’s are still $d$-dimensional vectors, but $y_i$’s need to be defined appropriately in terms of $\\Theta^{\\ast}$ and the $x_i$’s) and our predictor $\\hat{\\Theta} = \\frac{1}{n} \\sum_i y_i x_i^T$ will also be in $\\mathbb{R}^{C \\times d}$.\n\n**Questions For Authors:**\n\n**1.** Yes, memorization of noisy labels with powerful models is an issue. And if initial training is done naively, retraining may exacerbate this issue. That is why in almost all our experiments (except in Appendix J), we assume access to a clean validation set; please also see footnote 5 for the *practical version of this assumption*. This prevents the model from heavily memorizing. Moreover, as we show in Tables 3 & 7, the accuracy of the predicted (= given) labels on the consensus set is much more than the accuracy of both the predicted and given labels on the full set. This shows that regulated initial training is effective at avoiding memorization. Further, *as shown in Appendix J, even in the absence of a validation set, retraining is still beneficial but the gains are less – this is expected because the initial model’s performance is degraded due to more memorization/overfitting here*. \n\n**2.** Indeed, the benefit of retraining decreases when initial training is done for a larger number of steps. We studied this in Appendix J – here we don’t have a validation set and trained blindly for 100 epochs. Due to more overfitting here, the gains of retraining are lower than the corresponding gains with a validation set where we stopped at 40 epochs. If we train for even longer, the initial model will heavily memorize the noisy labels and this will probably render retraining ineffective.\n\n**3.** Yes, we used the cross-entropy (CE) loss; we’ll state this in the next version. Our baseline for AG News is actually randomized response (see lines 425-426 left column) to demonstrate the generality of retraining w.r.t. the baseline. Further, in Table 5, our baseline is forward correction applied to the method of Ghazi et al. 2021. So we do have results with other baselines. And based on your suggestion, we performed experiments with the *noise-robust symmetric CE loss function* proposed in [1] (1k+ citations) instead of the vanilla CE loss. In their loss (eq. 7 of [1]), we set $\\alpha=0.8$ and $\\beta=0.2$. Here are the results for CIFAR-100 w/ ResNet-34. \n\n|$\\epsilon$|Baseline|Full RT|Consensus-based RT|\n|---|---|---|---|\n|$4$|$37.07\\pm2.03$|$38.17\\pm2.03$|$\\mathbf{43.20}\\pm1.77$|\n|$5$|$53.10\\pm0.54$|$53.40\\pm0.33$|$\\mathbf{56.13}\\pm0.25$|\n\nThus, consensus RT yields meaningful gains even with the loss function of [1].\n\nWe hope to have resolved your concerns and we are happy to discuss further. If you’re satisfied with our answers, *we sincerely hope you will raise your score*!\n\n----\n\n[1]: Wang, Yisen, et al. \"Symmetric cross entropy for robust learning with noisy labels.\" ICCV 2019.", "claims_and_evidence": "The claims are almost all clear and convincing. \n- The main claim for which the clarity could be improved is the specification (especially in the abstract) that they theoretically analyze a **binary** classification problem. \n- In line 123 you claim that your work is on the fully supervised setting. Isn't the label noise scenario considered weakly-supervised?", "methods_and_evaluation_criteria": "The proposed evaluation criteria make sense for the problem considered.", "theoretical_claims": "I checked the theoretical claims superficially and they seem correct and well written.", "experimental_designs_or_analyses": "I would have preferred to see a comparison with other algorithms that perform classification with label noise, but I only see a minor result on the combination of retraining and forward correction. I think that a wider comparison would help in understanding if the contribution of this paper is mainly theoretical or if there is also a possible advancement for state-of-the-art techniques. \nI don't understand why the authors did not share the code. This arises concerns on the reproducibility of their results.", "relation_to_broader_scientific_literature": "The paper contributions are incremental, as the retraining technique is well known. However, the theoretical analysis is interesting and novel in my opinion.", "essential_references_not_discussed": "I am not aware of important related work that is not cited in the paper.", "other_strengths_and_weaknesses": "Strenghts\n- The paper is well written and even though it is theoretically heavy, it can be easily read by non-experts \n- The related work section is very useful\n- The experimental results enforces the theoretical claims\n\nWeaknesses\n- No code\n- No comparison with other techniques for classification with label noise (apart from Forward correction)\n- No theoretical analysis or comments for the multi-class classification problem", "other_comments_or_suggestions": "- in line 165 at the beginning of pp. 4 I would prefer the authors to use $\\cdot$ instead of $.$", "questions_for_authors": "- How do you relate the retraining technique with the problem of memorization of noisy samples? That is a well known problem in the noisy labels literature and I am afraid that retraining could worsen the memorization effect. Can you provide an empirical analysis of the memorization effect when using retraining? [a,b,c]\n\n- What does it happen when we increase the number of gradient steps? Does the gap between the accuracy achieved with and without retraining decrease? Is there a point in which, if we train the model for X steps, the retraining lowers the accuracy? Maybe this would be an interesting ablation study.\n\n- You use the baseline in Ghazi et al. 2021. Which objective function do you use to train your neural networks? I assume you use the cross-entropy. However, you did not study how the performance of your algorithm would change by changing baseline or objective function. This could arise questions on the general validity of retraining. Could you study the performance applying these changes? \n\n\n[a] Arpit, D., Jastrzębski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., ... & Lacoste-Julien, S. (2017, July). A closer look at memorization in deep networks. In International conference on machine learning (pp. 233-242). PMLR.\n\n[b] Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2016). Understanding deep learning requires rethinking generalization. ICLR 2017.\n\n[c]  Liu, S., Niles-Weed, J., Razavian, N., & Fernandez-Granda, C. (2020). Early-learning regularization prevents memorization of noisy labels. Advances in neural information processing systems, 33, 20331-20342.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZHObRZibvP", "reviewer": "Reviewer_JtmD", "summary": "This paper investigates the benefits of retraining a model using its own predicted hard labels in scenarios where training data contains noisy labels. \n\nThere are two strategies for retraining the model:\n\n- *Full Retraining:* The model is retrained on the entire dataset using its own predicted hard labels.\n- *Consensus-Based Retraining:* Only samples for which the model's predicted label matches the original noisy label are used for retraining.\n\nThe paper provides a rigorous theoretical analysis showing that *full retraining* with predicted hard labels can improve a model's population accuracy. In a linearly separable binary classification setting with randomly flipped labels, the authors derive error bounds and sufficient conditions when retraining is beneficial.\n\nThe authors also conduct extensive experiments on datasets such as CIFAR-10, CIFAR-100, and AG News Subset (a language dataset). The results show that both full retraining and consensus-based retraining enhance model performance, with consensus-based retraining providing the most significant improvements.\n\n## update after rebuttal\n\nThe detailed response has resolved my concerns. Thus, I raise my score after the rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and questions! We address your concerns below.\n\n**Other Strengths And Weaknesses:**\n\n**1. \"First, the theoretical analysis is…remains questionable.\"**: \n* We agree that our analysis on linear models for binary classification will not fully explain what happens in the case of non-linear models for multi-class classification, and we don’t intend to oversell the scope of our theoretical results. But we believe it is valuable as a first step; after all, *ours is the first work to analyze retraining with hard labels in any setting*. Moreover, we believe that some of our proof ideas could be useful even in the analysis of non-linear models. For instance, the proof technique of constructing dummy predicted labels that match the actual predicted labels with high probability (see lines 307-319 left column) should be useful in general, because the issue of dependence of each predicted label on the entire training set is universal regardless of the model type. \n\n* Regarding your point about complex models perfectly fitting noisy labels, we completely agree. And that is why, for such expressive models, it is important to apply (both in theory and practice) some kind of regularization when training them with noisy labels; for e.g., $\\ell_2$ regularization, early stopping, etc. Applying regularization is reasonable in scenarios such as label DP, where we already know that the labels will be noisy.\n\n**2. \"Second, although consensus-based retraining…its behavior or guarantees.\" / first bullet point under Claims And Evidence**: Agreed. We have admitted this limitation in Section 6, and plan to analyze consensus-based retraining in the future. Please note that the analysis of full retraining is itself pretty non-trivial (main technical challenges have been discussed after Thm. 4.8) and interesting in our opinion. \n\nWe do acknowledge the above two weaknesses. However, it is usually very difficult to perfectly align theoretical analysis with practical settings, and it is common to analyze simplified settings. So we believe these weaknesses **do not fundamentally undermine the significance of our work**. \n\n**3. \"Third, the effectiveness of retraining…yield significant improvements.\"** Indeed, retraining should intuitively only be beneficial when *the initial model’s predictions are more accurate than the given (noisy) labels* used to train the initial model. We have discussed/demonstrated this in several parts of the paper – Fig. 1 (see its caption), Tables 3 and 7 (these are on real data), and the comment on the range of $n$ after Remark 4.10 (specifically, regarding the lower bound on $n$). Moreover, in Appendix J & Table 10, we did an *ablation study* with and without a validation set. The initial model is naturally weaker w/o a validation set (due to overfitting); despite this, *retraining is still beneficial* but the gains are less than those with a val set. This observation is not surprising.\n\n**Second bullet point under Claims And Evidence:** As mentioned in Section 6, performing larger experiments is left for future work. While we didn’t have the time to train ImageNet from scratch now, we ran experiments on *DomainNet* dataset (available in Tensorflow) which has 345 classes & is much larger than CIFAR. We did linear probing (due to lack of time) with features extracted from a ResNet-50 pretrained on ImageNet. The setup is similar to our full fine-tuning experiments. DomainNet Results:\n\n|$\\epsilon$|Baseline|Full RT|Consensus-based RT|\n|---|---|---|---|\n|$3$|$23.60\\pm0.92$|$29.23\\pm1.03$|$\\mathbf{36.30}\\pm0.75$|\n|$4$|$48.25\\pm0.05$|$52.10\\pm0.10$|$\\mathbf{57.40}\\pm0.20$|\n\n*So even here RT (especially, consensus RT) yields large gains*.\n\n**Questions For Authors:**\n\n**1.** Please see the response to weakness **3** above (especially the last two sentences about the ablation). \n\n**2.** They *need not* be chosen based on the baseline’s performance. We did this to avoid any further hyper-parameter tuning based on retraining – to demonstrate that retraining is *not* very sensitive to hyper-parameters. If one were to optimize the hyper-parameters based on retraining’s performance as well, the gains would only increase.\n\n**3.** If randomized response (RR) is used as the baseline, then with $C$ classes and for $\\epsilon$-labelDP, each sample receives its true label $y$ w.p. $\\frac{e^{\\epsilon}}{e^{\\epsilon} + C-1}$ and some other label $y'$ w.p. $\\frac{1}{e^{\\epsilon} + C-1}$ for all $y' \\neq y$ (this has been explained in lines 177-181 left column). If the method of Ghazi et al. (2021) is used, then their first stage is RR (so the same as before), but the noise level of subsequent stages depends on the performance of the previous stage's model.\n\n**4.** Standard cross-entropy loss was used; we’ll mention this in the next version. Thanks for pointing this out!\n\nWe hope to have resolved your concerns and we're happy to discuss further. If you’re satisfied, *we sincerely hope you will raise your score*!", "claims_and_evidence": "The paper supports its main claims with a combination of rigorous theoretical analysis and extensive empirical validation.\n\nHowever, there are some aspects where the evidence is less complete:\n\n- The theoretical analysis focuses on full retraining under a uniform label noise model, while the consensus-based retraining, which empirically shows superior performance, lacks a corresponding theoretical analysis.\n- The experiments are conducted on moderate-scale datasets, so the scalability and generalizability of the approach to larger or more complex settings (e.g., experiments on the ImageNet dataset) remain to be further explored.", "methods_and_evaluation_criteria": "The proposed methods, namely full retraining and consensus-based retraining, make sense to tackle the challenges of learning with noisy labels and label differential privacy. Additionally, benchmark datasets like CIFAR-10, CIFAR-100, CIFAR-100N, and AG News Subset are well widely recognized.", "theoretical_claims": "Main theorems (Theorem 4.1, Theorem 4.2, Theorem 4.8, Theorem 4.9) are checked.", "experimental_designs_or_analyses": "The benchmark datasets are widely recognized in the community, and the experimental designs are reasonable. But some experimental settings remain unclear (see questions).", "relation_to_broader_scientific_literature": "The key contributions of the paper relate to two broader scientific literatures:\n\n- **Learning with Noisy Labels:** There is a lot of work on training models in the presence of noisy labels, which often involves robust loss functions or noise-correction techniques. The paper contributes to this literature by offering the first theoretical guarantees showing that full retraining with predicted hard labels can provably improve model accuracy under uniform label noise.\n- **Label Differential Privacy (DP):** In the context of privacy-preserving machine learning, label DP has emerged as an important concept. Prior works have proposed various noise-injection mechanisms (such as randomized response) to ensure privacy for sensitive label information. This paper shows that retraining methods (full retraining and consensus-based retraining) can enhance the model's performance without additional privacy costs.", "essential_references_not_discussed": "All essential related works are cited or discussed in the paper.", "other_strengths_and_weaknesses": "This paper investigates the benefits of retraining a model using its own predicted hard labels for label differential privacy (DP) and provides theoretical analysis. However, it exists several limitations.\n\nFirst, the theoretical analysis is confined to binary classification using linear models. Consequently, the derived results and error bounds are limited in scope and may not extend to practical scenarios where many tasks involve multiclass classification and complex nonlinear models. In real-world applications, sufficiently powerful nonlinear models can potentially memorize all the noisy labels. As a result, the model's predicted hard labels would simply replicate the noisy labels, rendering full retraining ineffective. This limitation suggests that while the theoretical contributions are valuable for understanding retraining in controlled settings, their applicability to more complex, realistic models remains questionable.\n\nSecond, although consensus-based retraining shows superior performance empirically, the paper does not provide a corresponding theoretical framework to analyze its behavior or guarantees.\n\nThird, the effectiveness of retraining is heavily dependent on the accuracy of the initial model's predictions. In scenarios where the initial model performs poorly, the retraining process might not yield significant improvements.", "other_comments_or_suggestions": "The meaning of $\\epsilon$ is not explained in the introduction, yet it appears in both the abstract and the conclusion of the introduction. Readers who are not familiar with Label Differential Privacy (DP) may be confused. It would be beneficial to provide an intuitive explanation of $\\epsilon$ in the introduction to enhance clarity and accessibility.", "questions_for_authors": "1. In scenarios where the initial model has low accuracy, how does the retraining process behave? Addressing this question could clarify the robustness of your method and whether it remains effective when the initial model is weak.\n2. Regarding the training details (Lines 1439–1440), why must the number of gradient steps and the initial learning rate be chosen based on the performance of the baseline method? Are the retraining methods particularly sensitive to these hyperparameters?\n3. What are the noise rates corresponding to different values of $\\epsilon$?\n4. The authors explicitly state that the forward correction algorithm is applied in the initial training stage for the experiments in Table 5. However, what loss function is used in the initial training stage for the experiments in Tables 1, 2, 4, and 6? Is it the standard cross-entropy loss? Clarifying this would improve the reproducibility of the reported results.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a case where author's response has resulted in two reviewers increasing their original scores so that overall paper score now is 4,4,3. The responses have addressed the concerns and the reviewers have increased the scores with the condition that the authors will include the additional results (e.g. discussions and formalizing the lower bounds and additional experimental results) in the camera ready. I recommend acceptance.
Decision: Accept (poster)