Optimal Fair Learning Robust to Adversarial Distribution Shift

Thank you for your thoughtful feedback and for appreciating the novelty of our results and the clarity of presentation. We recognize the importance of making the intuition in Section 1.2 as clear as possible for better readability of the rest of our paper. Acting on your suggestion, we will update our manuscript with a diagram (similar to the visualization here https://cococubed.com/images/raybox/five_shapes.pdf).

We provide a brief verbal explanation here: The hypercube represents the space of all classifiers, with each dimension corresponding to a data point. The fairness constraint is modeled as a hyperplane. The intersection of any hyperplane with the hypercube results in a bounded region whose vertices are either (i) vertices of the hypercube itself or (ii) points formed by the intersection of the hyperplane with an edge of the hypercube. In other words, all vertices of this intersection lie on the 1-skeleton (or polytope graph) of the hypercube. Accuracy can be understood as a directional objective, and the fair BOC corresponds to an extremal point in that direction on the intersection of the hyperplane and the hypercube. Since, in every direction, an extremal point must be a vertex, and all vertices lie on the 1-skeleton, it follows that the fair BOC necessarily lies on the 1-skeleton of the hypercube.

We hope that our response adequately addresses your questions, and we sincerely request your support towards a consensus for acceptance of our paper.

Thank you for your time and insightful feedback. We will cite and discuss the novel results in the papers you pointed out. However, our results are incomporable to those of the papers mentioned. Fundamentally, the underlying settings are different, and these results complement each other.

1. Comparison with [Xian & Zhao, 2024]:

Significantly, our setup assumes $P_X$ is a discrete distribution (over either a discrete or continuous domain $X$), and we will make this explicit in our revision (note that this is a standard assumption for realistic tabular datasets with features like height, income, race, etc.). On the other hand, [Xian & Zhao, 2024] implicitly assume $X$ is a continuous domain, and their results in general hold only for continuous distributions $P_X$ over $X$. See Remark 2.4 (fail cases of Assumption 2.2) in [Xian & Zhao, 2024], where the results don’t hold when the push-forward distribution $r\#P_X$ contains atoms and the randomized Fair BOC splits their mass, corresponding to the case our paper deals with, i.e., discrete distributions (See Claim 1 in our paper).

There exist many examples of discrete distributions where the optimal fair classifier must be randomized, and resorting to a deterministic classifier must necessarily come with a sharp drop in accuracy (even with the perturbation step described in Proposition 2.3 of [Xian & Zhao, 2024]); see the example in Claim 1 in our paper, where perturbing the scores/risks of each point would not do away with the need for randomization. The technical challenges in the discrete setup are very different from those in the continuous setup. For example, in most discrete distributions, the optimal fair classifier must be randomized, whereas in continuous distributions a deterministic classifier suffices under Assumption 2.2 in [Xian & Zhao, 2024]. Unlike the continuous setting, enforcing determinism in the discrete setting typically leads to non-robustness, for example in Claim 1.

We also note that the approach mentioned in Remark 2.4 of [Xian & Zhao, 2024] to handle discrete distributions, i.e., smoothing the discrete distribution and then applying the algorithm in the paper with a deterministic classifier, does not apply to discrete domains; furthermore, for continuous domains it will almost certainly lead to a drop in accuracy.

To summarize, while our submission and [Xian & Zhao, 2024] share the focus on robustness and fairness, our respective underlying frameworks are fundamentally different and complementary.

Finally, we emphasize that our robustness guarantees (Theorems 1, 2, & 3) cover adversarial distribution shifts over $X\times Z \times Y$, whereas the sensitivity analysis in Theorem 3.1 of [Xian & Zhao, 2024] covers either a shift in label distribution over $X\times Y$, or a shift in group distribution over $X \times Z$.

2. Comparison with [Chen et al., 2024]: Unlike us, they do not deal with adversarial distributions shifts, but only label distribution shifts and/or group distribution shifts. In addition, our setups are fundamentally different, theirs being the continuous case, and ours being the discrete case. Moreover, their sensitivity analysis in Theorem 2 is looser, and has an extra additive error term, unlike ours and that of [Xian & Zhao, 2024]. Besides, they do not deal with the case of perfect fairness, and require $\delta > 0$.

3. Comparison with [Chen et al., 2022]: Their result is fundamentally different, and essentially shows that the fairness of a fixed hypothesis class on two similar distributions is similar. This is essentially what we show in Claims 2/5/6, however, they only deal with label and covariate shifts, while we tackle the more general case of adversarial distribution shifts.

We hope that our response has addressed your concerns, and if so, we respectfully request you to consider increasing your rating.

Thank you for your time and insightful feedback. We respond to your comments below.

1. Real-world datasets: Our setup assumes a distribution over a discrete domain space $X$, which is a standard assumption for real-world tabular datasets (e.g., COMPAS) with features such as age, race, DoB, prior counts etc. We do not make any other assumptions on $X$. In particular, $X$ could be large, and multidimensional. The same holds for the non-robustness phenomenon is Claim 1. While experiments could be insightful, we emphasise that the focus of our paper is to establish the theoretical foundations of robust fair learning, building upon the theoretical papers of Konstantinov-Lampert (2022), and Blum et al. (2024).

2. Larger, non-degenerate example: In Claim 1, we provided a small example, independent of the sensitive attribute, just to demonstrate the phenomenon of non-robustness that occurs in optimal fair deterministic classifiers. The example can be made much larger (in fact, it can be made arbitrarily large). In addition, $X$ can also be multidimensional, and can depend on the sensitive attribute. The below example assumes $|X| = 10$, with $X$ also depending on the sensitive attribute. Consider the following distribution $P$.

$P,S(x_1, A) = (0.055, 0.9)$ | $P, S(x_1, D) = (0.045, 0.91)$ | $P, S(x_2, A) = (0.055, 0.8)$ | $P, S(x_2, D) = (0.05, 0.78)$ | $P, S(x_3, A) = (0.045, 0.73)$ | $P, S(x_3, D) = (0.045, 0.71)$ | $P, S(x_4, A) = (0.04, 0.67)$ | $P, S(x_4, D) = (0.06, 0.63)$ | $P, S(x_5, A) = (0.055, 0.53)$ | $P, S(x_5, D) = (0.05, 0.51)$ | $P, S(x_6, A) = (0.045, 0.45)$ | $P, S(x_6, D) = (0.05, 0.46)$ | $P, S(x_7, A) = (0.055, 0.33)$ | $P, S(x_7, D) = (0.06, 0.32)$ | $P, S(x_8, A) = (0.04, 0.28)$ | $P, S(x_8, D) = (0.04, 0.24)$ | $P, S(x_9, A) = (0.06, 0.17)$ | $P, S(x_9, D) = (0.055, 0.15)$ | $P,S(x_{10}, A) = (0.05, 0.09)$ | $P, S(x_{10}, D) = (0.045, 0.7)$

Consider $f$, which classifies $\{x_1,..., x_5\} \times \{A, D\}$ as $1$, and $\{x_6,...,x_{10}\} \times \{A, D\}$ as $0$. $f$ satisfies $DP$, and has accuracy much more than $0.5$. Consider the neighboring $P^′$ which differs with $P$ on $(x_5, A)$, and $(x_5, D)$, as follows.

$P', S(x_5, A) = (0.055 + \epsilon, 0.53)$ | $P', S(x_5, D) = (0.05 - \epsilon, 0.51)$,

where $\epsilon > 0$ is arbitrarily small. There are only 2 deterministic classifiers satisfying DP on $P’$, either the constant 1 classifier $f_1$, or the constant 0 classifier $f_0$, both with accuracy close to 0.5. Hence, the difference in accuracy of the deterministic DP-fair BOC on arbitrarily close $P, P^′$ is large, demonstrating non-robustness.

3. Proof length: Perhaps the proof can be shortened, we will try and simplify it to aid readability. Lemma 1 played a crucial role in simplifying the proof overall, but it can be done without Lemma 1 as well.

4. Approximate fairness: We show through the example below that the non-robustness phenomenon highlighted in Claim 1 also holds when we only require approximate fairness. In particular, this can hold in the case where sensitive group populations are highly imbalanced, for example when the mass of group $A$ is much larger than the mass of group $D$, i.e., $P(A) >> P(D)$. We define a $\delta$-approximately fair classifier as follows, “If $r$ denotes selection rate, a classifier $f$ is $\delta$-approximately DP-fair if $|r(f, A)−r(f, D)| < \delta$". We set $\delta=0.25$, and slightly modify the example in Claim 1, where we skew the probability mass towards Group $A$ (in Claim 1, the group masses are balanced). Consider a distribution P, where

$P, S(x_1, A) = (0.4, 1)$ | $P, S(x_1, D) = (0.1, 1)$ | $P, S(x_2, A) = (0.4, 0)$ | $P, S(x_2, D) = (0.1, 0)$

Consider the (deterministic) classifier $f$, with $f(x_1, A) = f(x_1, D) = 1, f (x_2, A) = f (x_2, D) = 0$. $f$ satisfies DP, and $\text{Acc}(f) = 1$. Consider the neighboring distribution $P^′$ differing only on $(x_1, D), (x_2, D)$, as follows.

$P', S(x_1, D) = (0.1 + 0.05, 1)$ | $P', S(x_2, D) = (0.1 - 0.05, 0)$

If we apply $f$ on $P’$, it does not satisfy approximate DP for any $\delta < 0.25$, even though $TV(P, P’)$ is small ($0.05$). There are only 2 deterministic classifiers satisfying approximate DP for any $\delta < 0.25$, either the constant 1 classifier $f_1$, or the constant 0 classifier $f_0$, with $\text{Acc}(f_1) = 1/2 + 0.05$, and $\text{Acc}(f_0) = 1/2 − 0.05$. Hence, the difference in accuracy of the deterministic (approximate) DP-fair BOC on closeby $P, P^′$ is almost 0.5, demonstrating non-robustness.

We will also discuss fairness regularizers based on mutual information, Pearson correlation, HGR correlation, and f-mutual information. These are relevant for broader literature review but not directly related to the problem we study.

We hope we have addressed all your concerns, and we sincerely request you to reconsider our rating.

Thank you for your insightful feedback, and for appreciating the importance of our contribution, and the clarity of presentation. We respond to your comments below.

1. Experiments: We emphasise that the focus of our paper is to advance the theoretical foundations of robust fair learning, building upon the theoretical works of Konstantinov-Lampert (2022) and Blum et al. (2024). While experiments would be valuable, we leave that as future work.

2. Randomization: It is established that on most distributions, (exact) fairness is non-trivially achievable only by randomized classifiers [Agarwal et al, Hardt et al.]. In addition, the randomization in our result is almost nil, and is the minimum amount required (only on one element). If we strictly enforce determinism, the drop in accuracy is significant, as demonstrated in Claim 1. Hence, there is a clear tradeoff between randomization and accuracy (subject to fairness), and for a tiny amount of randomness, we obtain a big jump in accuracy.

1. Moritz Hardt, Eric Price, and Nathan Srebro. Equality of Opportunity in Supervised Learning. NeurIPS 2016
2. Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A Reductions Approach to Fair Classification, ICML 2018.

We hope that our response has addressed your concerns, and if so, kindly request you to consider increasing your score, and support towards a consensus for acceptance of our paper.