Error-Bounded Correction of Noisy Labels

1. Introduction

• Label noise harms model performance, especially for deep networks, while data-recalibrating methods select trustworthy individual labels but lack an explanation and guarantees to control selection quality.Overly aggressive selection can accumulate irreversible errors; overly conservative selection can slow training or leave too little clean data.Source: §1 · p. 1
• A noisy classifier’s confidence in a training label indicates its purity: low confidence suggests corruption, and the theorem quantifies a threshold separating likely corrupted from likely clean labels.The paper also reports that the theorem’s bound is empirically tight.Source: §1 · p. 2
• The proposed algorithm applies a likelihood-ratio test to a noisy classifier’s prediction and confidence threshold, correcting or retaining each label with a guaranteed success rate and high-probability recovery.The algorithm is incorporated into deep-network training and is reported to outperform state-of-the-art methods across datasets with varied noise patterns and levels.Source: §1 · p. 2

1.1. Related Work

• Prior approaches correct losses using transition matrices or model labels, or impose robustness through parameter constraints and feature-distribution assumptions, but rely on strong assumptions or may not generalize.Some approaches also lack a guarantee of learning the true label distribution or depend on trusted clean data that may be unavailable.Source: §1.1 · p. 2
• Input perturbations and regularization can improve robustness, while data-recalibrating methods select clean samples; these approaches lack control over selection quality, and theory-to-practice gaps remain.The related work also surveys theoretical results on noise-robust losses and convergence to a Bayesian optimal classifier, alongside the computational and integration limitations of KNN.Source: §1.1 · pp. 2–3

2.1. Preliminaries and Assumptions

• The analysis assumes a bounded margin around the Bayes decision boundary and feature-independent label-transition probabilities; its target is the Bayes-optimal label, not the sampled true label.The noisy conditional probability is a linear transformation of the true conditional probability.Source: §2.1 · p. 3

2.2. The Main Theorem

• If a noisy classifier f is ϵ-close to the noisy conditional probability and satisfies the theorem’s assumptions, a low-confidence observed label has a bounded probability of being correct.The bound tightens as the approximation error ϵ decreases; its threshold depends on unknown label-transition probabilities.Source: §2.2 · pp. 3–4

2.2.1. PROOF OF THEOREM 1

• The proof uses a linear-transformation lemma and the margin condition to bound the chance that a low-confidence observed label agrees with the Bayes-optimal decision; it also notes a possible high-confidence bound.The paper focuses on identifying incorrect labels for correction.Source: §2.2.1 · pp. 4–5

2.4. Empirical Validation of the Bound

• For ϵ below 0.4, the bound reaches only 0.2, while measured correctness among low-confidence labels is almost zero; estimated ϵ reaches 0.06 and 0.12 in the symmetric- and asymmetric-noise experiments.On CIFAR10, the estimated Tsybakov constants are C = 0.23 and λ = 1.04 (R² = 0.99, p-value < 1e−53); synthetic-data estimates are 0.6 and 1.3. High-confidence labels are more often correct, and the experiments report that confidence thresholding detects corrupted labels accurately.Source: Figure 1 · p. 5, §2.4 · pp. 5–6

2.3. Multiclass Setting

• Theorem 1 is extended to multiclass classification under a multiclass Tsybakov margin condition and an estimation-error constraint.The multiclass margin is the difference between the highest and second-highest true conditional class probabilities.Source: §2.3 · p. 5

3. The Algorithm: Likelihood Ratio Test for Label Correction

• LRT-Correction compares the noisy-label confidence with the classifier’s top-prediction confidence and flips the label to that prediction when their likelihood ratio is below δ.The ratio is f_ey(x)/f_mx(x), where mx is the classifier’s top prediction; otherwise the noisy label remains unchanged.Source: §3 · p. 6
• Theorem 3 bounds the probability that a flipped label equals h∗(x) by 1 − C[O(max(ϵ, ξ1))]^λ − Ψ.The bound assumes the multi-class Tsybakov condition; Ψ is the probability that the true label is neither the noisy label nor the classifier prediction.Source: §3 · p. 7
• Theorem 3 bounds the probability that a preserved label equals h∗(x) by 1 − C[O(max(ϵ, ξ))]^λ − Ψ.This bound also assumes the multi-class Tsybakov condition and accounts for the probability Ψ that the true label is neither the noisy label nor the classifier prediction.Source: §3 · p. 7

3.1. Training Deep Nets with LRT-Correction

• AdaCorr iteratively uses the current network’s softmax output to correct all training labels, then trains the network on the updated labels until convergence.The method alternates label correction and incremental training.Source: §3.1 · p. 7
• After burn-in, AdaCorr adds a retroactive loss to cross-entropy training to encourage consistency with the model’s prediction from a previous epoch.The burn-in stage trains on the original noisy labels using cross-entropy.Source: §3.1 · p. 7

Datasets

• The evaluation covers MNIST, CIFAR10, CIFAR100, and ModelNet40, with validation-based early stopping and test-set performance reporting.Noise is injected according to specified noise transition matrices; ModelNet40 inputs are point clouds sampled at 1,024 points per model.Source: §4 · p. 8

Baselines

• Baselines include Standard, Forward Correction, Decoupling, Coteaching, MentorNet, Forgetting, and Abstention.They respectively include standard training, noise-transition correction, two-network selection or exchange, curriculum filtering, dropout, and abstention-loss approaches.Source: §4 · p. 8

Experimental setup

• AdaCorr overall achieves the best performance across datasets under different noise settings.The experiments train all methods for 180 epochs, use RAdam, and update f_r to f once at epoch m + 40.Source: §4 · p. 8

Clothing 1M

• On Clothing 1M, AdaCorr reaches 71.47% accuracy, versus Standard at 68.94%, Forward Correction at 69.84%, and Backward Correction at 69.13%.The other listed baselines did not report results on this dataset.Source: §4 · p. 8, Table 1 · p. 8

Discussion

• On CIFAR10 with 0.4 uniform noise, AdaCorr continues correcting labels without test accuracy dropping, while Standard overfits noisy labels and test performance degrades catastrophically.The reported curves indicate that model training and label correction improve together without collapse.Source: §4 · p. 8

• Experiments across various datasets show that the method outperforms many recently proposed methods.Source: §5 · p. 8
• The paper proves theoretical guarantees for data-re-calibrating methods for noisy labels.Source: §5 · p. 8
• The proposed label-correction algorithm produces models robust to different noise patterns.Source: §5 · p. 8

Estimation of Tsybakov condition constants

• OLS estimates for the Tsybakov condition are C = 0.58 and λ = 1.27, with R2 = 0.904 and p-value < 10^-4.The estimates come from the synthetic experiment’s empirical frequency fit.Source: §1 · p. 12

Estimation of the error bound, and its tightness

• Theorem 1’s error bound is evaluated as a function of ε and plotted alongside the proportion of labels inconsistent with the Bayes-optimal rule.Figure 1(b) uses 20% noise, and Figure 1(c) shows asymmetric noise.Source: §1 · p. 12, Figure 1 · p. 13
• When f = eη, the probability that ey is correct when f(x) < ∆ is empirically zero, as shown for symmetric and asymmetric noise.This is the ε = 0 case in Figures 1(b) and 1(c).Source: §1 · p. 12, Figure 1 · p. 13

Validation of the label-correction algorithm

• With perfect f = eη, LRT-Correction produces labels very close to clean, with success limited by noise asymmetry; its Corollary 1 error bound is plotted against classifier error.Figure 3 shows the corrected labels, while Figure 2 plots the bound for symmetric and asymmetric noise settings.Source: §1 · p. 12, Figure 2 · p. 13, Figure 3 · p. 14

2. Proof of Theorem 2

• The proof assumes η(x) satisfies the multi-class Tsybakov condition for constants C, λ > 0 and t0 ∈ (0, 1].The condition is stated to hold for all t ≤ t0.Source: §2 · p. 14
• Pr [ey = h∗(x), fey(x) < ∆] equals Pr [ηey(x) ≥ηsx(x), fey(x) < ∆].Source: §2 · p. 14

3. Proof of Theorem 3

• The probability of an incorrect new label among rejected labels is at most C[O(ϵ)]^λ + Pr_{(x,y)∼D}[u_x ≠ m_x, u_x ≠ e_y]; the same bound holds among accepted labels.Source: §3 · p. 15
• The residual disagreement term Pr[ux ≠ mx, ux ≠ ey] is not handled by the algorithm and is left for future research.Source: §3 · pp. 16–17
• When eηux(x) ≥ eηsx(x) + 2ϵ, it follows that eηux(x) − ϵ ≥ eηi(x) + ϵ and fux ≥ fi(x) for all i ∈ [Nc], yielding fmx(x) = fux(x); thus the second terms in (2) and (6) are zero.Source: §3 · p. 18
• For both rejected and accepted labels, Theorem 3 bounds correction error by C[O(max(ϵ, ξ))]^λ plus Pr[ux ≠ mx, ux ≠ ey], under its stated assumptions including ξ < δ.The two bounds apply separately to rejected and accepted labels.Source: §3 · pp. 18–19