On Group Sufficiency Under Label Bias

Thank you for the insightful review and constructive feedback!

W1: Dependence on transition probabilities. The claim in line 126 that the method requires only noisy labels seems overstated, as the transition probabilities are also needed.

We note that we do experiment with using Confident Learning [1] to estimate the transition matrix only from noisy data, though this generally results in worse performance than using the true transition matrix. We emphasize that as better transition matrix estimates are developed, our method will improve in this setting as well. We will clarify the claim in L126 to reflect this.

W2: Entropy term and conditioning.

Q1: My first question concerns the entropy term in Equation (4). Specifically, the entropy H(Y | F(X)) is not conditioned on the sensitive attribute G, so the use of T_{g_i} is a bit confusing to me. In line 1052, where the definition of mutual information appears to differ from the one presented in line 202 of the main text. Could you clarify this discrepancy?

In our class-attribute-conditioned noise model (Assumption 3.1), the backward correction always involves $T_g$ because noise depends on $(Y, G)$, which leads to $\\mathbb{E}_{\\tilde Y \\mid Y = y,\\, G = g} [(T_g^{-1})\_{\\tilde{Y},\\cdot}] = e\_y^{\\top}$. Using the marginal matrix $T$ would result in a biased estimator, as it does not correspond to the actual probability of corruption for that sample.

After this backwards correction, $−\\log \\pi(Y \\mid f(X))$ is independent of $G$. Thus, the two definitions on L1052 and L202 are equivalent. We will modify L1050 to the following to make it more explicit:

$\\mathbb{E}\_{\\tilde Y \\mid G, Y=y}[(-T_G^{-1}\\log\pi(\\cdot\\mid s))\_{\\tilde Y}] = -\\log\\pi( y\\mid s)$.

Q2: Regarding the "Noise Types," I would like to ask why the authors add noise only to one specific sensitive group. Performing additional experiments with the same level of noise applied to different groups seems straightforward and would provide a more comprehensive evaluation.

We add noise only to one specific group as it is the worst-case scenario. Because the entire disparity is concentrated in one group, the resulting sufficiency gap is maximal for a fixed average noise rate. Further, if both groups were noisy, as one group's noise matrix approaches the other, training a naive calibrated classifier with respect to noisy labels is sufficient to remove the sufficiency gap as shown in Corollary 4.1.1, and thus the problem becomes trivial.

We appreciate the suggestion to add noise solely to the other protected group. In our current experiments, the noisy group was selected largely for historical reasons, and we did not experiment with noising the other group due to computational considerations. We expect our method to perform similarly with noise in the other group, and will verify this in a future revision.

[1] Confident Learning: Estimating Uncertainty in Dataset Labels. JAIR.

Dear Authors, thank you for your detailed response.

Your response seems satisfactory; I still do not understand how, in the backward correction, you are allowed to use $T_g$ instead of $T$, as the definition of entropy does not depend on $g_i$.

While it's true that the true entropy

$H(Y \\mid f(X)) = \\mathbb{E}\_{X, Y}[-\\log p_Y(Y \\mid f(X))]$

does not explicitly depend on $G$, the estimator we construct for this quantity does. This is because we only observe $\tilde{Y}$ and not $Y$, and given Assumption 3.1, we need $T_g$ to invert the noise generating process to "recover" $Y$. By using $T_g$ in the estimator, we achieve unbiasedness as is shown above. One could instead use $T$ in the estimator, but it would be biased. We will make this distinction clearer in the revision. Please let us know if this addresses your concerns!

Dear Authors, thank you for your detailed reply.

I understand your point and will increase my score. I believe the paper would benefit from a more detailed explanation, as the result currently appears counterintuitive.

Additionally, regarding the experimental section, I would suggest presenting results with different noise levels (beyond 0.6 and 0.7) and comparing the performance using the true versus the estimated transition matrix for both CMI-REG and SUF-REG in the main part of the paper. This would offer a clearer picture of the method’s effectiveness.

Thank you for the insightful review and constructive feedback!

The value of the novel methods proposed in this paper would have been greatly enhanced if the authors would have used a different method to compare their method against. Fairret is an example of a method that can function for predictive parity (the simplification of sufficiency when dealing with binary classification) and also works as an added loss term. These types of method would allow the authors to show that their specific focus on label bias is warranted as this cannot by done by traditional methods not assuming this level of label bias.

The paper would also improve if the authors could provide results comparing their method with other methods, however I can see how this would fall out of the scope of the rebuttal. While I appreciate it if the authors would do this, I do not expect it.

We have added a multicalibration baseline from [1] following a suggestion from Reviewer xUeM. Specifically, we pre-process the data using the $T_g^{-1}$ matrix, learn an ERM model, then apply Algorithm 1 from [1] for multicalibration, using the single attribute to define $\mathcal{C}$.

We present results for AUROC and Sufficiency Gap below, using the same setting as Table 2 of the main paper. We include only the Forward loss for our methods for brevity. We find that sufficiency gaps for this baseline remain substantially higher and AUROC is also significantly worse.

The paper uses the adult dataset, while still popular in the research area of fairness in AI, it has been shown that this dataset should not be used anymore for showing the capabilities of methods (Fabris et al., Algorithmic Fairness Datasets: the Story so Far).

We agree with the issues with the adult dataset, and have included it here solely due to its popularity in other fairness literature. However, we have actually also conducted experiments on the ACS Income dataset from [2], which has been proposed as a drop-in replacement for adult which addresses some of its issues (age, arbitrary threshold, outdated feature encodings).

The paper contains datasets with both simulated and real noise with regards to the labels. This is already commendable but the authors could have also used the dataset of Lenders and Calders (Real-life Performance of Fairness Interventions-Introducing A New Benchmarking Dataset for Fair ML) which provides a dataset with these biased and unbiased labels on a dataset where biases are more inherently present. The dataset however is very small.

Thank you for pointing out this dataset! We have conducted an experiment on it, using the biased human labels from the ranking strategy as observed labels, and the eight categorical features from the Kaggle version of the dataset.

Due to small sample size (n=856), and the fact that even the oracle (training on clean labels) has quite high Sufficiency Gap, we expect the gain of our method in this setting to be limited. However, we do find that (1) in all cases, applying CMI-Reg reduces the sufficiency gap relative to the base loss, and (2) applying CMI-Reg does not significantly change overall AUROC when the confidence intervals are taken into account.

The interpretability of figure 2 could be improved; the plots are very small and the legend is not very easy to understand without reading the entire paper.

If the camera-ready allows for an additional page then I would ask the authors to increase the size of the plots in Figure 2.

Thank you for these suggestions! We will make these changes for the next revision if additional space is available.

[1] Multicalibration: Calibration for the (Computationally-Identifiable) Masses. ICML 2018.

[2] Retiring Adult: New Datasets for Fair Machine Learning. NeurIPS 2021.

Thank you for the insightful review and constructive feedback!

The proposed method has some dominance over others. However, a case where the method can shine out and establish clear dominance is when the transition matrix is estimated and the Brier score itself is noisy.

In the noisiest of settings where you can only estimate Brier scores and transition matrices with noisy data (perhaps with the help of Clusterability or some anchor points), will the proposed CMI-REG show a lot of significant improvement?

Thank you for the suggestion! We note that the setting where we only have estimated transition matrices, as well as no clean examples for model selection, is the most difficult setting for our problem. We have provided results for this setting below. We observe that across the 24 combinations of losses and datasets, CMI-REG achieves lower or equal sufficiency gap than the base loss in 20 such combinations.

Further, expecting our regularizer to improve every single base loss is a lofty goal, as some losses may have optimization landscapes that naturally work better with our regularizer. Instead, looking at the best achievable sufficiency gap for each dataset, we find that CMI-REG achieves the lowest sufficiency gap across all four datasets.

I am also skeptical of the finite sample estimator of the CMI regularizer.

Can the authors comment on the convergence of the proposed mutual information estimators with finite samples?

We will add the following proposition to the paper, characterizing the finite sample convergence of the MI estimator.

Proposition: Let $\\hat{I}\_n$ be the CMI estimator defined in Eq (7), estimated with IID samples $(x\_i, g\_i, \\tilde{y}\_i)_{i=1}^{n}$.

Under Assumptions 3.1 and 3.2, and that $\forall x_i \in \mathcal{B}: h_{\\phi}(f_{\\theta}(x_i)) = \\mathbb{P}(Y \\mid f_{\\theta}(x_i))$ and $h_{\psi}(f_{\theta}(x_i)) = \\mathbb{P}(Y \\mid f_{\\theta}(x_i), g_i)$, we have that, with probability $1 - \\delta$,

$|\\hat{I}\_n - I(Y; G \\mid f(X))| \leq \sqrt{\frac{k \log (2/\delta)}{n}} = O(\frac{1}{\sqrt{n}})$,

where $k$ is a constant that depends only on $K$ and $|G|$.

Further, combining this with Proposition 5.1, we have that

$Suf_g(f) \\leq \\sqrt{\\frac{2}{K}} (\\hat{I}_n + O(\\frac{1}{\\sqrt{n}}))^{1/2}$.

We will include the full proof in the appendix in the revision, but it involves (1) showing the Lipschitzness of the mutual information in the total variation distance, (2) applying the Bretagnolle–Huber’s inequality on the two $P_{Y,G}$ distributions, and (3) plugging (2) into (1).

Thank you for the insightful review and constructive feedback!

W1. Lack of meaningful baselines. Here is my suggested baseline: Since the transition matrices are given to CMI-REG, why not transform the noisy data using the transition matrices $T^g$ and $T$ as a pre-processing step and then use any standard multicalibration algorithm?

Thank you for the suggestion! There are two primary issues with the proposed baseline. First, the inverse of the transition matrix $(T^g)^{-1}$ is in general not row-stochastic, and may contain values outside of $[0, 1]$. Thus, it cannot not be directly used in a pre-processing step to transform the observed labels into unbiased true labels. Second, applying multicalibration during test-time requires knowledge of the group attributes during inference. None of our methods or baselines require this assumption.

Regardless, we have adapted the proposed baseline to our setup in the following way:

• We apply a softmax to each row of $(T^g)^{-1}$ so it is row stochastic.
• We randomly flip observed labels according to this matrix, and then train an ERM model on this processed data.
• We apply Algorithm 1 from [1] for multicalibration, specifically using the implementation from [2], using the single attribute to define $\mathcal{C}$.
• We vary all hyperparameters (including $\alpha$ and $\lambda$) using a random search, and select the optimal model using the same setting as Table 2 of the paper.

We present results for AUROC and Sufficiency Gap below. We include only the Forward loss for our regularizers for brevity. We find that sufficiency gaps for this baseline remain substantially higher and AUROC is often worse.

W2. Novelty and contribution are not clear. Methodically, the paper's approach can be summarized as adding a calibration regularizer with corrections to prediction rates due to noise, which is completely specified via transition matrices. Unfortunately, the experiments do not convince me otherwise, either due to small relative improvements, many of which fall within error margins.

We argue that our contributions extend beyond simply combining noise-robust losses with a heuristic regularizer. First, we propose and formalize this particular problem, which, to our knowledge, has not been studied in prior work. Second, we theoretically characterize this problem, showing necessary & sufficient conditions showing that label bias, even when classifiers are calibrated on noisy labels, inevitably induces a sufficiency gap on the true labels (Theorem 4.1 and Corollary. 4.1.1). Third, though our experimental gains are modest, they do seem to be consistent, and statistically significant in many cases.

W3. Uneven presentation. As an example, I was very surprised to find SUF-REG being presented in the experimental section (Line 254) in 2 lines with minimal details. Similarly, backward and forward corrections in Lines 206 and 208 are presented with only a reference and no details.

Due to space issues, we were not able to describe SUF-REG thoroughly in the main paper and had to relegate it to the appendix. We focused primarily on CMI-REG because it performed marginally better, and because the techniques used in CMI-REG (e.g. linear heads for posterior estimation) are common across the two methods. The backward correction used in L206 and L208 are applications of a well-known result from prior work [3], and so we did not describe it in detail. We will provide more exposition to this in the revision.

W4. Empirical results are not very convincing. Looking at Figure 2, I cannot confirm that CMI-REG and SUF-REG indeed Pareto dominate in every case. Also, overall, the Pareto fronts are rather sparse.

We note that expecting our regularizer to improve every single base loss is a lofty goal that may not be realistic, as some losses may have optimization landscapes that naturally work better with our regularizer. We note that overall, either CMI-REG or SUF-REG achieves the lowest sufficiency gap in 8/10 experimental settings (Tables 3 and 4 in the appendix).

Regarding the sparsity of the Pareto plots, we emphasize that all methods were given the same budget of 20 hyperparameter from a random search, from a fairly wide range grid shown in Appendix B.3. The reason why some Pareto curves collapse to a single point is because there is no observed trade-off between fairness and performance in those cases. In general, such a trade-off may not exist, e.g. the group Bayes optimal score with respect to true labels has maximum performance and zero sufficiency gap.

Q1. On page 7, I think the transition matrix for Eq. (4) should probably be $T^{-1}$, not $(T_g)^{-1}$. No? Same for Eq. 6 and onwards, as none of these probability estimates have a conditioning on group.

In our class-attribute-conditioned noise model (Assumption 3.1), the backward correction always involves $T_g$ because noise depends on $(Y, G)$, which leads to $\\mathbb{E}_{\\tilde Y \\mid Y = y,\\, G = g} [(T_g^{-1})\_{\\tilde{Y},\\cdot}] = e\_y^{\\top}$. Using the marginal matrix $T$ would result in a biased estimator, as it does not correspond to the actual probability of corruption for that sample.

On the latter note, I find that lack of any discussion or reference to the (now) vast literature of multi-calibration is a miss.

Q2. Please discuss multi-calibration.

We will add a paragraph on multicalibration to the related works in Section 2.2, and add the above experiment with the multicalibration baseline to the main paper. Please let us know if this is satisfactory!

As also stated in the paper's limitation section (thanks for making this very clear), the assumption that we have the transition matrices as inputs to the algorithm is a rather strong one that limits the applicability of the algorithm as it is. I think the paper would have benefited greatly from an estimation step using a small, clean dataset (for example).

Thank you for the suggestion! We note that we do experiment with using Confident Learning [4] to estimate the transition matrix (only from noisy data), though this generally results in worse performance than using the true transition matrix. We emphasize that as better transition matrix estimations methods are developed, our method will improve in this setting as well.

If we were instead given $n$ iid samples with labels for whether they are mislabeled or not as the reviewer suggests, we could then use the empirical estimator for each element of $T$. We have theoretically characterized the behavior of this estimator, and its impact on sufficiency gap estimates, in Appendix A.5.

[1] Multicalibration: Calibration for the (Computationally-Identifiable) Masses. ICML 2018.

[2] When is Multicalibration Post-Processing Necessary? NeurIPS 2024.

[3] Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach. CVPR 2017.

[4] Confident Learning: Estimating Uncertainty in Dataset Labels. JAIR.