Can Less be More? When Increasing-to-Balancing Label Noise Rates Considered Beneficial
Year: 2022

Abstract:
In this paper, we answer the question of when inserting label noise (less informative labels) can instead return us more accurate and fair models. We are primarily inspired by three observations: 1) In contrast to reducing label noise rates, increasing the noise rates is easy to implement; 2) Increasing a certain class of instances’ label noise to balance the noise rates (increasing-to-balancing) results in an easier learning problem; 3) Increasing-to-balancing improves fairness guarantees against label bias. In this paper, we first quantify the trade-offs introduced by increasing a certain group of instances’ label noise rate w.r.t. the loss of label informativeness and the lowered learning difficulties. We analytically demonstrate when such an increase is beneficial, in terms of either improved generalization power or the fairness guarantees. Then we present a method to insert label noise properly for the task of learning with noisy labels, either without or with a fairness constraint. The primary technical challenge we face is due to the fact that we would not know which data instances are suffering from higher noise, and we would not have the ground truth labels to verify any possible hypothesis. We propose a detection method that informs us which group of labels might suffer from higher noise without using ground truth labels. We formally establish the effectiveness of the proposed solution and demonstrate it with extensive experiments.

heading: 1 Introduction
text: The presence of training label noise is generally considered harmful. Typically the goal of learning with noisy labels is to improve the training by reducing the amount of noise in the training data [4, 11]. This paper discusses the feasibility of the opposite strategy and shows cases when adding label noise, leading to a scenario with less informative labels, will result in more accurate and fair models. We are primarily motivated by three observations:
Observation I: Reducing label noise is hard, but increasing it is easy. While the literature has provided us with solutions to perform data cleaning, they often require a highly customized training process. Their lack of theoretical rigor has also posed challenges when performing evaluations. On the other hand, as we will see later, increasing label noise is easy — one can always do so by randomly flipping the current noisy labels to increase it further.
Observation II: Increasing a certain class of instances’ noise rate to balance the noise rates results in an easier learning problem. When label noise is class-dependent (label class Y = +1 v.s. Y = −1), popular noise-tolerant learning algorithms typically require the knowledge of noise rates [25]. However, the learner often needs to identify the unknown noise rates by some estimation procedure [26, 27, 36]. We articulate that the mis-specification of noise rates will introduce additional learning errors, especially when the label noise is asymmetric (see Theorem 1). On the other
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
hand, although increasing the noise rate of the lower class one to balanced error rates reduces the informativeness of the training labels, it is regarded as an easier case to handle — when error rates are balanced, invoking loss correction procedures becomes unnecessary (see Lemma 2 & Theorem 3).
Observation III: Increasing-to-balancing improves fairness guarantees against label bias. When the label noise rates are group-dependent (data from young group v.s. senior group), it has been reported in the literature that imposing fairness constraints directly on the noisy labels would instead reinforce the unfairness [30]. Fixing the fairness constraints again requires the knowledge of the label noise rates. We will show that increasing and balancing noise rates allows us to directly impose fairness guarantees on the noisy training data without knowing the noise rates (Theorem 6).
This paper first quantifies the trade-offs introduced by increasing a certain group of instances’ label noise rate with respect to the loss of informative labels and the gained benefits for doing so. We analytically demonstrate when such an increase proves beneficial in terms of either improved generalization error or fairness guarantees. Then we present a method to leverage our idea of inserting label noise for the task of learning with noisy labels, either without or with a fairness constraint. The primary technical challenge we face is that we would not know which data instances are suffering from higher noise, and again we would not have the ground truth labels to verify any possible hypothesis. In response, we propose a detection method that informs us which group of labels might suffer from higher noise without using ground truth information. The core discovery is a couple of metrics that check the agreements of noisy labels among local neighbors. These two metrics can be easily estimated using noisy labels only and are shown to be sufficient to inform us of the class of labels with a higher noise rate. With this knowledge, we propose an algorithm (NOISE+) to gradually insert noise into the lower noise class of labels. Our contributions summarize as follows:
• Our paper prototypes the idea of pre-processing noisy training labels for both the constrained and unconstrained learning problems. We show the possibility of improving the training accuracy and fairness guarantees by increasing a certain class of instances’ noise rates (increasing-to-balancing).
• To enable the deployment of our idea, we propose a detection algorithm to identify the class of instances with a higher label noise rate without using any ground truth label information.
• Our solution contributes to the learning with noisy labels literature by adding another tool that is robust to noise rate (noise transition matrix) estimation errors.
All omitted proofs can be found in the Appendix. The code for reproducing the experimental results is available at https://github.com/UCSC-REAL/CanLessBeMore.

heading: 1.1 Related work
text: Our work is a contribution to the well-established literature of learning with noisy labels [11, 22, 25, 27–29, 33]. The classical solutions within the literature leveraged the knowledge of noise rates to perform loss correction [25, 27, 28], label correction [23, 27], loss reweighting [19], among many other treatments. The importance of knowing the correct noise rate parameters is clearly established. Follow-up works have provided tools for estimating the noise rates without accessing the ground truth label. These include the confident learning approach [26], anchor point [5], and more recently clustering-based ones [36]. Nonetheless, the possibility of unintended harm due to mis-specified noise rates remains. More recent works have looked into robust loss functions that would not require the knowledge of noise rate, hoping to improve the resistance to the mis-specifications [14, 21, 32, 34, 35]. Our work can be viewed as a contribution to this specific line of literature.
Our work also contributes to the understanding of fairness implications when learning with noisy labels and other imperfect information [3, 7, 10, 17, 20, 24, 30, 31]. For instance, [17] considers amending noisy sensitive attributes by appropriately re-scaling the fairness tolerance but is only restricted to class-conditional random noise. [30] proposes two noise-resistant fair classification approaches by constructing unbiased estimators with group-dependent label noise. While most of the existing works would either require the noise rates to be balanced between groups or the knowledge of the noise rates to perform noise correction [30], our work requires neither.

heading: 2 Preliminaries
text: We will consider a binary classification problem with d-dimensional feature space X ∈ Rd and label space Y ∈ {−1,+1}. (X,Y ) generate according to distribution D. Instead of accessing the clean
data, we consider the setting where the learners only have access to noisy labels Ỹ . The generation of Ỹ follows the noise transition model: e+(x) := P(Ỹ = −1|Y = +1, X = x), e−(x) := P(Ỹ = +1|Y = −1, X = x). We further assume Ỹ generates conditionally independently for different X . For now, we do not restrict how e+(x), e−(x) depend on x but to enable our analysis, later we will. Denote the noisy distribution for (X, Ỹ ) as D̃. In the second constrained learning setting, we assume that for each instance (X,Y ), we also observe a sensitive attribute Z ∈ {a, b} that defines two protected groups (e.g., senior v.s. young people) that we will later enforce fairness constraints over.
Unconstrained learning problem. In the unconstrained setting, denote the collected training data as D̃ := {(xn, ỹn)}Nn=1. The goal is to train a classifier h ∈ H that minimizes the empirical risk ED[1(h(X) 6= Y )] with only accessing D̃, where 1(·) is the 0-1 loss function. We will focus on the standard class-dependent noise rate model where e+(x) ≡ e+, e−(x) ≡ e−,∀x. We assume we have informative labels: e+, e− < 0.5. Hereby the noise rates depend only on the true label class [25], but not the specific instance x when conditional on the true label. We will operate in the challenging asymmetric error rates setting when e+ 6= e−. Fairness constrained learning problem. In the fairness constrained setting, denote the collected training data as D̃ := {(xn, ỹn, zn)}Nn=1. The goal is to train a classifier h ∈ H that maximizes the accuracy while satisfying a certain fairness constraint, measured by a fairness metric Fz(h):
min h∈H
ED[1(h(X) 6= Y )] s.t. |Fa(h)− Fb(h)| ≤ δ, (1)
wherein δ > 0 is a tolerance parameter for fairness violations. Exemplary Fa(h) includes the Equal Opportunity measure Fa(h) := P(h(X) = +1|Y = +1, Z = a) [12], the demographic parity Fa(h) := P(h(X) = +1|Z = a) [6], among others. We assume the error rates are group dependent [30]: e+(x) = e−(x) = ez, z ∈ {a, b}. Again we assume ea, eb < 0.5. Within each group, we can further assume that the noise rates are classdependent, but then we will simply apply our solution within each group (between +1/− 1 classes) and across the group. We remove this additional layer of complication to stay concise.
Notations. We define the following quantities that we will repeatedly use. We will denote by RD(h) := ED[1(h(X) 6= Y )] the true generalization error of a classifier h incurred on the clean distribution D. For a classification-calibrated loss function, we will denote its risk as R`,D(h) := ED[`(h(X), Y )]. Denote the empirical `-risk of a classifier h on dataset D as R̂`,D(h) := 1 |D| ∑ (x,y)∈D `(h(x), y).
Our solution is generically applicable to multi-class settings, which we will explain later and demonstrate with experiments. For a clear exposition of our core idea, we focus on the binary case.

heading: 3 Equalizing error rates can improve model accuracy
text: In this section, we focus on the unconstrained learning setting. We will show that while increasing one label class’ noise rate raises the generalization errors due to less informative labels, at the same time, it helps remove the training’s dependency on the noise rates (e+, e−), and therefore improves robustness to possible mis-specification of them. We will quantify such trade-off.
We would mainly demonstrate our idea by comparing to methods that explicitly use the knowledge of noise rates. For one reason, these approaches often have strong theoretical guarantees. The other reason is that the benefit of our approach of not requiring the noise rate would be clearer for this comparison. Particularly, we will use loss correction [25] as the running example. We are aware of the other recent works that do not require the noise rates. First of all, these approaches focus on improving model accuracy, but not the fairness constraints. Secondly, empirically we observe that these approaches can also benefit from our noise rate balancing procedure. We left the discussions to our experiments, where we will demonstrate using one of such losses, peer loss [21].
Loss correction. Once knowing e+, e−, there exist different ways to improve training robustness in the presence of noisy labels. We consider demonstrating our idea using the classical loss correction framework [25, 27]: denote by ẽ+, ẽ− the estimated version of e+, e−. In practice, this knowledge
can be obtained by using existing techniques [19, 26, 36]. For a given calibrated loss `, the loss correction approach defines the following loss:
˜̀(h(xn), ỹn) := (1− ẽ−sgn(ỹn)) · `(h(xn), ỹn)− ẽsgn(ỹn) · `(h(xn),−ỹn) (2)
where in above sgn is the sign function. A favorable property of ˜̀ is its unbiasedness (expectation over Ỹ |Y = y) w.r.t. `(h(x), y) when given the correct noise rate parameters e+, e−. For readers who need more background knowledge of loss correction, we reproduce details in Appendix ??. A classifier will be trained following empirical risk minimization (ERM) using ˜̀: h∗˜̀,D̃ := arg minh∈H ∑N n=1
˜̀(h(xn), ỹn). Compared to the standard loss correction, we omit the 1 − ẽ− − ẽ+ term from the denominator, which will not affect the minimizer of our ERM problem. Denote h∗`,D = arg minh∈HR`,D(h), the optimal classifier for R`,D(h), and errM := max{|ẽ+ − e+|, |ẽ− − e−|} the maximal mis-specification error. When ` is L-Lipschitz and bounded by ¯̀, let L1 := 4L,L2 := 2¯̀> 0, adapting the proof from [25] we show: Theorem 1. For any δ > 0, we have with probability at least 1− δ:
R`,D(h ∗ ˜̀,D̃ )−R`,D(h∗`,D) ≤ 1
1− e+ − e−︸ ︷︷ ︸ label informativeness
·L1 · R(H) + errM
1− e+ − e−︸ ︷︷ ︸ mis-specification
·L2 + 2 √ log 1/δ
2N , (3)
where in aboveR(H) denotes the Rademacher complexity ofH.
Clearly, e+, e− control the error due to label informativeness: a pair of e+, e− with higher sum (e+ + e−) induce larger generalization error bound. On the other hand, the potential imperfect estimates of them introduce additional error due to the mis-specification.

heading: 3.1 When does equalizing error rate improve performance?
text: Now we first provide intuitions for why increasing noise rate to balance e+ and e− might be considered helpful. Without loss of generality, suppose e+ > e−. When we increase e− to match e+ such that e = e+ = e− (later we will explain how we do so), denote by Ŷ the newly generated noisy label with e symmetric error rates for both classes. Note that e < 0.5. Denote by ŷn the generated label for example n, D̂ the distribution of (X, Ŷ ), and D̂ the dataset {(xn, ŷn)}Nn=1. We first show: Lemma 2. When e < 0.5, minimizing P(h(X) 6= Ŷ ) is equivalent with minimizing P(h(X) 6= Y ).
The above lemma says that the minimizer of P(h(X) 6= Ŷ ) is equivalent to the optimal classifier for P(h(X) 6= Y ) when the hypothesis spaceH covers the optimal h! Therefore when ` is classificationcalibrated on the noisy distribution D̂, and when the hypothesis space is sufficiently large, we know that the optimal classifier for ED̂[`(h(X), Ŷ )] will be exactly the same as the one for ED[`(h(X), Y )]. This further implies that when the error rates are symmetric, the training might not need the error rates information, and performing ERM on the noisy data:
h∗ `,D̂
:= arg min h∈H N∑ n=1 `(h(xn), ŷn) (4)
suffices to find the optimal classifier for the clean distribution, when given a sufficient amount of data. The above argument is slightly trickier when considering a finite hypothesis spaceH. Denote by −h the classifier that always flips the prediction from h. Then we prove that Theorem 3. Suppose 1) ` is symmetric s.t. `(h(x),−y) = `(−h(x), y) and 2) −h∗
`,D̂ ,−h∗`,D ∈ H:
R̂`,D̂(−h∗`,D̂) ≥ R̂`,D̂(−h ∗ `,D). Then for any δ > 0, we have with probability at least 1 − δ:
R`,D(h ∗ `,D̂ )−R`,D(h∗`,D) ≤ 11−2e · L1 · R(H) + 2 √ log 1/δ 2N .
The second condition above is simply stating that the opposite classifier of the empirically optimal one incurs a high empirical loss, and particularly higher than −h∗`,D. Intuitively, this condition is satisfied for binary classification — if one classifier performs the best on the empirical data, flipping its prediction often results in a very wrong one. Now comparing Theorem 1 and 3 we observe that equalizing noise rates increases the error due to loss of informative labels by:∣∣∣∣ 11− 2e − 11− e+ − e− ∣∣∣∣ · L1 · R(H) = |e+ − e−||1− e+ − e−| · |1− 2e+| · L1 · R(H).
On the other hand, equalizing noise rates avoids the error due to mis-specifying e+, e− by errM1−e+−e− · L2. Therefore, it is considered helpful to increase e− to e+ when errM ≥ |e+−e−|·L1·R(H)|1−2e+|·L2 . The above condition is likely to hold when the gap between noise rates |e+ − e−| is sufficiently small, and when we do not have high confidence in the estimation of e+, e− (therefore a high errM).

heading: 4 Equalizing error rates improves fairness guarantee
text: In this section, we consider the fairness constrained learning problem and show that equalizing noise rates helps improve fairness guarantee when only accessing the noisy labels. There are generally two types of fairness constraints: those that do not depend on the label and those that do. For the ones that do not, for example, demographic parity P(h(X) = +1|Z = a) = P(h(X) = +1|Z = b), the existence of noisy labels does not impose additional challenges when enforcing such constraints. For those that do, typically they are functions of true positive rates (TPR, also known as the equal opportunity measure) and false positive rates (FPR). It was shown in [30] that equalizing TPR and FPR on the noisy label leads to disparities when ea 6= eb. We will reproduce the same observations. We focus on the second type of constraints: equalizing TPR and FPR using the noisy labels.
Having noted that equalizing TPR and FPR on the noisy labels leads to unintended consequences, the literature has observed recent works on performing fairness constraint correction [30]. Similar to the loss correction approaches, such correction methods would again require the knowledge of ea, eb, which is subject to mis-specification error. Define
TPRz(h) := P(h(X) = +1|Y = +1, Z = z), FPRz(h) := P(h(X) = +1|Y = −1, Z = z) T̃PRz(h) := P(h(X) = +1|Ỹ = +1, Z = z), F̃PRz(h) := P(h(X) = +1|Ỹ = −1, Z = z)
Resampling the noisy data examples such that P(Ỹ = +1|Z = z) = P(Ỹ = −1|Z = z) = 0.5, z ∈ {a, b}, define Cz,1 := 0.5 · ez, Cz,2 := 0.5 · (1− ez), we derive the following relationship:
Lemma 4. TPRz(h), FPRz(h) relate to T̃PRz(h), F̃PRz(h) as follows:
TPRz(h) = Cz,1 · T̃PRz(h)− Cz,2 · F̃PRz(h)
ez − 0.5 , FPRz(h) = Cz,1 · F̃PRz(h)− Cz,2 · T̃PRz(h) ez − 0.5
(5) The above lemma first implies that since two groups a, b might have different Cz,1, Cz,2, equalizing T̃PR, F̃PR using the noisy labels naively is insufficient to guarantee equalization of TPR,FPR.
Unfairness due to model error. On the other hand, Lemma 4 points out a way to perform constraint correction using the knowledge of ea, eb. Denote by ẽa, ẽb (both < 0.5) the estimated copies of ea, eb that we have access to. Suppose we suffer from the following mis-specifications: errM := min{erra := |ẽa− ea|, errb := |ẽb− eb|}. Denote the corrected TPR and FPR using T̃PR and F̃PR as well as ẽa, ẽb as TPRcz(h), FPR c z(h): Define C̃z,1 := 0.5 · ẽz, C̃z,2 := 0.5 · (1− ẽz), and:
TPRcz(h) = C̃z,1 · T̃PRz(h)− C̃z,2 · F̃PRz(h)
ẽz − 0.5 , FPRcz(h) = C̃z,1 · F̃PRz(h)− C̃z,2 · T̃PRz(h) ẽz − 0.5
(6)
Theorem 5 establishes possible fairness violation due to errM, noise rates mis-specification: Theorem 5. Equalizing TPRcz(h) & FPRcz(h) for a, b leads to following possible fairness violation:
|TPRa(h)− TPRb(h)| ≥ errM · ∣∣∣∣∣ T̃PRa(h)(2ea − 1)(2ẽa − 1) − errberra T̃PRb(h)(2eb − 1)(2ẽb − 1) ∣∣∣∣∣ ,
|FPRa(h)− FPRb(h)| ≥ errM · ∣∣∣∣∣ F̃PRa(h)(2ea − 1)(2ẽa − 1) − errberra F̃PRb(h)(2eb − 1)(2ẽb − 1) ∣∣∣∣∣ .
But as a consequence of Lemma 4, we immediately know that
Theorem 6. When ea = eb, equalizing T̃PR and F̃PR suffices to equalizing the true TPR and FPR.
This is simply because equalizing ea and eb also equalizes both Cz,1 and Cz,2. Theorem 6 helps us establish a strong fairness guarantee: as long as we know the training data has balanced label noise rates across different groups, enforcing the constraints directly on the noisy data suffices to guarantee the equality between true TPR and FPR.
Our above observation points out increasing one group’s label noise to match another helps establish the fairness guarantees more easily. Consider the case ea > eb. Now suppose we are able to increase eb to match ea such that e = ea = eb. Denote by Ŷ the newly generated noisy label with e symmetric error rates for both groups, and correspondingly ŷn the newly generated training labels. Then performing fairness constrained ERM directly on D̂ := {(xn, ŷn, zn)}n:
h∗ `,D̂
:= arg min h∈H N∑ n=1 `(h(xn), ŷn) s.t. |F̂a(h)− F̂b(h)| ≤ δ, (7)
will help us equalize TPR and FPR between two groups when the number of training data is sufficiently large. In above, F̂a(h), F̂b(h) are the empirically computed fairness measures using D̂.

heading: 5 Identifying cleaner class without using ground truth label
text: With the aforementioned benefits of balancing the noise rates, the remaining technical question is to determine how does e+ or ea compare to e− or eb? Of course, when we have access to ground truth labels, we will have a rough estimate and carry on to insert label noise (e.g., by further randomly flipping the noisy labels, which we will discuss at the end of this section). In this section, we describe another approach without the need for ground truth labels. We prove its sufficiency in identifying the noisier class of labels. We demonstrate our idea using the unconstrained learning setting for detecting sgn(e+ − e−), but the idea easily generalizes to the fairness setting to detect the order of ea and eb.

heading: 5.1 Noisy label agreements
text: We first present the following definition: Definition 7 (Clusterability). We say the dataset D satisfies 2-NN clusterability if each instance x shares the same true label class with its two nearest neighbors measured by ||x− x′||2.
For the rest of the section, we will assume that D satisfies 2-NN clusterability. 2-NN was similarly introduced in a recent work [36] and has been shown to be a requirement that is mild to satisfy. Now we define the following two quantities that are central to the development of our idea. For an arbitrary instance X1 with noisy label Ỹ1, denote the noisy labels for two nearest neighbor instances of X1 as Ỹ2, Ỹ3. Define the following agreement measures:
Definition 8 (2-NN Agreements). Let Ỹ1 denote the noisy label for a randomly selected instance X1. Ỹ2, Ỹ3 are the noisy labels of X1’s 2-NN instances (measured by ||x− x′||2).
Positive Agreements PAD := P(Ỹ2 = Ỹ3 = +1|Ỹ1 = +1) (8) Negative Agreements NAD := P(Ỹ2 = Ỹ3 = −1|Ỹ1 = −1) (9)
PAD computes the likelihood of the neighbor data points “agreeing" on a positive label. NAD computes the one for the negative label. Now we will first sub-sample the noisy distribution and compute PAD,NAD:
• Step 1 Sample Ỹ such that P(Ỹ = +1) = P(Ỹ = −1) = 0.5. Denote this resampled distribution as D .
• Step 2 Compute NAD ,PAD .
Next we prove that knowing NAD ,PAD suffices to inform the order between e+, e− (sgn(e+ − e−)): Theorem 9. When e+, e− < 0.5 and D satisfies 2-NN clusterability, PAD ,NAD relate to e+, e− as follows:
PAD − NAD = 2(0.5− e+)(0.5− e−)(e− − e+). Then if PAD > NAD , we know that e+ < e−; otherwise e+ > e−. If PAD = NAD , then e+ = e−.
Estimating PAD ,NAD using D . Note that both PAD and NAD , P(Ỹ2 = Ỹ3 = +1|Ỹ1 = +1) and P(Ỹ2 = Ỹ3 = −1|Ỹ1 = −1) can be counted from the noisy data without accessing the ground truth. For instance for PAD :
• Step 1 Find all xn in D with ỹn = +1 and their 2-NN n1, n2.
• Step 2 Count #{n: ỹn=ỹn1=ỹn2=+1}#{n: ỹn=+1} . #(·) counts the number of samples that satisfy the condition.
We show pseudocode for an implementation of estimating PA in Figure ?? in Appendix ??.

heading: 5.2 Our solution: NOISE+
text: We show that randomly flipping Ỹ = y with the smaller esgn(y) by a small probability monotonically decreases the gap between noise rates |e+ − e−|. Without the loss of generality suppose e+ < e−, and we will only flip the Ỹ = +1 labels (but not flipping the ones with Ỹ = −1). We show numpy-like pseudocode for the flipping function in Figure 3, and the implementation for exclusively flipping Ỹ = −1 labels is symmetric. Denote by Ŷ as the flipped version of Ỹ : P(Ŷ = −1|Ỹ = +1) = , and ê+ := P(Ŷ = −1|Y = +1), ê− := P(Ŷ = +1|Y = −1). We have: Proposition 10. ê+ = (1− e+) · + e+, ê− = (1− ) · e−. Further, the new gap between the noise rates of the flipped label Ŷ is a monotonic function of : ê− − ê+ = e− − e+ − (1− e+ + e−) · .
Since 1− e+ + e− > 0, when is small, the above derivation shows the effectiveness in reducing the noise rate gap e− − e+ by randomly flipping the noisy labels that correspond to the class with lower noise rate. The only remaining question is how to find the optimal s.t. ê− − ê+ = 0. Calling Theorem 9, we know PAD − NAD = 2(0.5 − ê+)(0.5 − ê−)(ê− − ê+). Denote by f( ) := 0.5 · (PAD − NAD ). Easy to derive the three solutions for f( ) = 0 (setting each of the terms to 0): 1 = 1 − 0.5e− < 0, 2 =
e−−e+ 1−e++e− , 3 = 0.5−e+ 1−e+ : note that 2 = e−−e+ 1−e++e− < (e−−e+)+(1−e+−e−) (1−e++e−)+(1−e+−e−) = 1−2e+ 2(1−e+) = 3,
and 3 will lead to an uninformative state where ê+ = 0.5. Therefore 2 is our target root.
The monotonicity of f( ) from 0 to 2 motivates us to look for a proper by a binary search procedure. Suppose we have two different flipping parameters l < r. Initially the synthetic datasets induced by them are Dl and Dr, and the gaps of the counted agreements are Cl = PADl−NADl and Cr = PADr − NADr , satisfying Cl > 0 > Cr. In each iteration, we try a new flip parameter mid = ( l + r)/2, and check whether the new gap Cmid is bounded by a threshold γ. If −γ ≤ Cmid ≤ γ, we return the labels flipped by mid. Otherwise, we update the values of l and r according to the sign of Cmid: if Cmid < 0, we set r ← mid,Dr ← Dmid (reducing r); otherwise l ← mid,Dl ← Dmid (increasing l). We summarize NOISE+ in Algorithm 1. Here, we initialize r = 0.3 which empirically succeeds in varied noise settings. In case r = 0.3 fails, we can grid search a variety of values (e.g., 0.1, 0.2) satisfyingCr < 0 as the initial r to proceed our binary search algorithm. Note that Algorithm 1 assumes e+ < e−, and the implementation is symmetric for e+ > e−.
Selection of loss function. Our algorithm is particularly suitable for losses that do not require the knowledge of noise rates. Standard cross entropy (CE) would certainly be applicable. Other robust loss functions are great options too. We note a recently proposed loss, peer loss function [21], does not require the specification of noise rates:
`peer(h(xn), ỹn) := ` (h(xn), ỹn)− α · ` (h(xp1), ỹp2) .
Here, α > 0 is a hyper-parameter to control the balance of the instances for each label, p1 and p2 are uniformly and randomly selected peer samples. Peer loss is also promoted in [30] for the fairness constrained setting. We believe it is particularly suitable for our NOISE+. We will evaluate CE and peer loss in the experiment section.
Fairness constrained learning. Our above derivations and observations can be similarly applied to the fairness constrained setting. The only difference lies in that now PAD ,NAD are corresponding to the agreements within each of the two groups a, b instead of the two label class group Ỹ = +1 and Ỹ = −1. We provide details in the Appendix ?? without repeating them here.
Training. Once we have the output and noise-incremented dataset D̂ := {(xn, ŷn)}n from Algorithm 1, we will use it directly in our ERM framework for the unconstrained case as in Eqn. (4) and will use it in the fairness constrained ERM in Eqn. (7) directly too.
Extension to multi-class. As explained at the beginning, our algorithm can largely extend to the multi-class/group setting. The primary requirement of the extension is to extend the definition of PAD ,NAD to each label class/group. We defer details to Appendix ??. In the next section, we will demonstrate the effectiveness of our results with the CIFAR-10 dataset.
Algorithm 1 NOISE+: A binary search algorithm for balancing noise rates. Require: γ > 0, l = 0, r = 0.3
Resample a balanced set D from D̃; Initialize Dl = D , Dr = Flip(D , r); Estimate PADl , PADr , NADl , NADr . while PADl − NADl > γ and PADr − NADr < −γ do mid ← ( l + r)/2,Dmid ← Flip(D , mid); Estimate PADmid and NADmid ; if PADmid − NADmid < −γ then
/* mid is at the right of the root */ r ← mid,Dr ← Dmid; PADr ← PADmid , NADr ← NADmid ;
else if PADmid − NADmid > γ then /* mid is at the left of the root */ l ← mid,Dl ← Dmid; PADl ← PADmid , NADl ← NADmid ; else return D̂ = Flip(D̃, ( l + r)/2);
end if end while return unsuccessful;

heading: 6 Experiments
text: In order to verify the power of our increasing-to-balancing method, we conduct extensive experiments on both unconstrained learning and constrained learning settings. The datasets include: the UCI Adult Income dataset [9], the Compas recidivism dataset [2], Fairface [15] face attribute dataset, and CIFAR 10 [16] dataset. We defer more dataset details to Appendix ??.

heading: 6.1 Unconstrained learning
text: Setup. For the unconstrained learning, we implement a one-layer perceptron for binary classification on Adult, Compas, and Fairface datasets. We flip the true labels on training set according to a set of asymmetric noise rates, train the models on the corrupted labels, and evaluate the accuracy on test set with clean labels. The baseline methods we compare include: surrogate loss [25] with mis-specified noise rates (Mis. SL) and estimated noise rates (Est. SL) respectively, vanilla cross entropy (CE), and peer loss functions [21] (Peer). For Mis. SL, we randomly generate the noise parameters but ensure that the trace is equal to that of the true noise transition matrix. For Est. SL, we estimate the noise rates by adopting the confident learning procedure [26]. We note that the training of peer loss functions does not require the knowledge of noise rates, and follow their instructions to tune the hyper-parameters through cross-validation. For the same corrupted training labels, we deploy our increasing-to-balancing procedure, and evaluate the performance of cross entropy and peer loss functions again. We set the threshold γ used in Algorithm 1 as 0.1% on Adult and Fairface datasets, and loose it to 1% on Compas due to its much smaller data size. We repeat all the methods 5 runs with different random seeds and report the mean and standard deviation.
Results. We show the experimental results in Table 1. We observe that our increasing-to-balancing method significantly improves the accuracy of the vanilla cross entropy on the majority of noise settings. It is notable that the cross entropy with increasing-to-balancing has a comparable performance with Est. SL, when the noise is relatively small. When the noise rates are large (e.g. 0.2 and 0.4), we observe a significant degradation for cross entropy, but increasing-to-balancing still boosts the accuracy. Moreover, we find that peer loss after increasing-to-balancing is more robust to noise, and dominantly achieve the highest accuracy.
Multi-class extension. We test NOISE+ in the multi-class setting by balancing the noise rates class by class. We evaluate the compared methods on MNIST [18] and CIFAR-10 [16] with more sophisticated noise transition matrices. Considering that both datasets have 10 classes, we adopt the following procedure to generate the 10× 10 noise transition matrix: (1) manually set the diagonal elements at least 0.4; (2) permute the diagonal elements to increase the randomness; (3) fill out the non-diagonal elements randomly and ensure the sum of each column is 1. An MLP model is trained from scratch on MNIST dataset, while a pre-trained vision transformer [8] is used to extract visual features on CIFAR-10 dataset. As shown in Table 2, we observe that when the noise gap is 0.1 and 0.2, CE and Peer with NOISE+ outperforms the pure CE and Peer, respectively. When the noise gap is 0.3, balancing cannot compensate for the performance drop due to increased noise.
Experiments on Clothing1M. Clothing1M is a large-scale dataset collected from online shopping websites, comprising of 1 million training images of clothes with realistic noisy and 10,000 test data
with clean labels. For a fair comparison, we adopted the same setting as described in [27] and trained a ResNet-50 [13] classifier. Table 3 compares our methods with some other baselines, including loss correction [27] and Co-Teaching [11]. Without a careful tuning of training parameters, vanilla CE with NOISE+reached 70.37% test accuracy. In comparison, standard CE achieves 68.94%, loss correction achieves 69.84%, and Co-Teaching is 70.15%.

heading: 6.2 Constrained learning
text: Setup. We conduct experiments with equal odds constraints [12] on Adult, Compas, and Fairface datasets. We add heterogeneous noise, i.e., uneven noise rates for different group memberships but symmetric for different classes, into training labels but keep test labels clean. We stress-test the performance of the naïve logistic regression (LR) and group-weighted peer loss (GPL) [30] with and without our increasing-to-balancing program.1 We note that GPL degrades to peer loss when noise rates are homogeneous across protected groups [30], and directly apply peer loss after balancing. For a fair comparison, we use logistic regression as the base classifier for all the methods. We use the reductions approach [1] to solve the constrained optimization.
Results. We report the accuracy and fairness violation for ea = 0.2 and eb = 0.4 in Table 4 and defer more noise settings to Appendix ??. We make the following observations: (1) All the methods retain a comparable accuracy. We conjecture that this benefits from the symmetric noise rates between positive and negative classes. (2) After balancing, both naïve LR and Peer significantly mitigate the fairness violations on Adult and Fairface datasets as a result of equalized noise rates across groups. (3) Peer loss generally has a lower fairness violation than naïve LR. This implies its capability of recovering unbiased classifiers. (4) We find out that the performance of LR with increasing-to-balancing is less profitable on Compas dataset because of uninformative features (only 10-dimensional features), and more robust on Fairface dataset with rich image information.

heading: 7 Concluding Remarks
text: This paper elaborates the possibility of improving the training model accuracy and fairness guarantees by increasing a certain class of instances’ noise rates. Our idea is based on several observations that increasing-to-balance label noise rates can yield an easier learning problem that is robust to mis-specified noise rate parameters. The above robustness helps us improve generalization power as well as fairness guarantees. To deploy our idea, we propose a detection algorithm to identify the class of instances with a higher label noise rate, without using any ground truth label information.
Our noise rate balancing solution is primarily a data pre-processing procedure and is compatible with most existing learning with noisy label solutions. Our experiment result using peer loss is one such example. Empirically we do observe that many other solutions may also enjoy the benefits of balancing the noise rates. We believe this data pre-processing technique has the potential to find applications in other learning tasks when balancing label noise or bias is desired.
1We did not repeat testing surrogate loss as it is reported in [30] that GPL appears to be a better and more robust solution. Also we focus on correcting fairness constraints in this section, both SL and GPL would use the same constraint corrections.

heading: Acknowledgments
text: This work is partially supported by the National Science Foundation (NSF) under grant IIS-2007951 and the NSF FAI program in collaboration with Amazon under grant IIS-2040800. The authors would like to thank Jiaheng Wei and Zhaowei Zhu for their prompt discussion and help on the experimental setup for the Clothing1M dataset.

Review summaries:
This submission studies the paradigm of injecting label-noise from the perspective of fairness and robustness. The motivation stems from the fact that balancing the label proportions yields an easier learning problem and improves fairness guarantees. The submission derives a bound between the corrected loss with label noise and the population risk, which through the use of standard concentration inequalities, involves the Rademacher complexity. In order to fix one, they propose a method that detects the right choice of labels that suffer from noise, which then is turned into an algorithm for robust and fair label correction.

This paper explores ways to improve the generalization performance and fairness guarantees, by increasing a certain class of instances' label noise to balance the rates between different classes. Theorem suggests that when the gap between noise rates is small and when we don't have high confidence in estimating the noise rates, it may be beneficial to increase noise rates. The paper further proposes a method to insert label noise without knowing the ground truth training labels. Experiments show that the rate balancing procedure can be beneficial to increase test performance.

In this work, the authors aim to show that adding label noise in some cases could be beneficial to the test performance and fairness of models. Firstly, they find that increasing-to-balancing can result in an easier learning problem and improves fairness guarantees against label bias. Then they propose a method by inserting label noise to the group of labels with lower noise rates. To estimate the noise rates of various groups, the authors propose a detection method by checking the agreements of noisy labels among local neighbors. Experiments are conducted on three tiny datasets and CIFAR-10 dataset across different levels of noise rates to verify the effectiveness of the proposed algorithm. 

This paper considers classification in the case of noisy training data, where one subset of points suffers from higher label noise then the complementary subset. This paper claims that by increasing the label noise rate on the less noisy subset, it is possible to obtain more accurate models since the learning problem is easier.   Additionally, in the context of fairness, increasing the noise rate of the advantaged group improves fairness guarantees in the sense that when we are fair on the noisy data, we are also fair on the clean data.   Lastly, this paper contributes a method to detect which subset suffers from higher noise rates (and how much more is suffers) without access to the ground truth.