Retraining with Predicted Hard Labels Provably Increases Model Accuracy

Thanks for your review and questions! We address your concerns below.

Other Strengths And Weaknesses:

1. "First, the theoretical analysis is…remains questionable.":

• 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.

• 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.

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.

We 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.

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.

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:

So even here RT (especially, consensus RT) yields large gains.

Questions For Authors:

1. Please see the response to weakness 3 above (especially the last two sentences about the ablation).

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.

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.

4. Standard cross-entropy loss was used; we’ll mention this in the next version. Thanks for pointing this out!

We 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!

Thanks for your review and great questions! We address your questions/concerns below.

Claims And Evidence:

1. We will clarify "binary" in the abstract.
2. 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.

Experimental Designs Or Analyses / first two weaknesses:

• 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.

• 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.

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}$.

Questions For Authors:

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.

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.

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.

Thus, consensus RT yields meaningful gains even with the loss function of [1].

We 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!

[1]: Wang, Yisen, et al. "Symmetric cross entropy for robust learning with noisy labels." ICCV 2019.

Thanks for the review and great questions!

(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.

(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.

(C) Experimental setup more aligned with theory setting

1. Setting of Fig. 1 corresponds to our theory setting; see Appendix A.

2. 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:

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.

(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.

We’ll fix/clarify notational ambiguities.

(E) Questions for Authors

1. The ones in eqs. 4.3 & 4.8. Also see Appendix A.

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.

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}$.

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.

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$.

We hope to have resolved your concerns and are happy to discuss further. If you’re satisfied, we hope you will raise your score!

[A]: "Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View", Thrampoulidis et al., 2020