Fair Wasserstein Coresets

We thank the reviewer for the careful review and comments; we answer each questions below.

1. It is indeed true that the MLP $g_\psi$ satisfies the Wasserstein inequality for $p_{(x,d)}$ rather than $p_{z}=p_{(y,x,d)}$ (with the first inequality being ultimately what we are interested in), so thanks for pointing this out. We have changed the notation to define the downstream deviation as $d(p_{(\hat{X},\hat{D});\theta}, p_{(X,D);e})$. Proposition 2.1 still holds as it can be updated as follows:

   $d(p_{(\hat{X},\hat{D});\theta}, p_{(X,D);e}) \leq L_k W_1 (p_{(\hat{X},\hat{D});\theta}, p_{(X,D);e}) \leq L_k W_1(p_{\hat{Z};\theta}, p_{Z;e}),$

   as the Wasserstein-1 distance of the joint $(X,Y,D)$ is larger than the marginal $(X,D)$, as the $L_1$ distance is the sum of the absolute values of the distances across each variables (we have added a more formal proof of this in Appendix B). In other words, the Wasserstein distance minimized by FWC still constrains the downstream learning discrepancy we are interested in. We have updated Proposition 2.1 to reflect this. Finally, note that defining $h(z) = |g_\psi(x, d) - y|$ does not work as the reverse triangle inequality $||x| - |y|| \leq |x-y|$ only holds if the expectation is inside the absolute value, so the upper bound necessary for the proof of Proposition 2.1 would not follow.

2. Thanks for the suggestion and you are totally correct. It is in the sense of achieving a lower Wasserstein distance. We have clarified it by stating that the optimal objective value (Wasserstein distance) of problem (4) is no lower than that of problem (5) with the $m$ replaced by $m|\mathcal{D}||\mathcal{Y}|$.

3. Thank you for your suggestion to improve the readability of our results. We have now updated Figure 1 to include Pareto frontiers, computed over all models and coreset sizes, which we have uploaded in the global rebuttal above. We include a table below to indicate which FWC models are included in the Pareto frontier in each dataset.

4. Thank you for the feedback. Determining the acceptable fairness-accuracy trade-off has been a discussion in the community and is eventually dependent on the application. Fairness-accuracy trade-offs have been highlighted in several works, eg., [1] and [2], and the acceptable trade-off is up to an end user and is application dependent (eg., finding lower discriminatory alternatives is mandatory in fair lending and acceptable accuracy reduction is dependent on "business necessity" [3]). Using LLM's is one of the downstream tasks considered in the paper and the experiment shows that coresets produced by FWC are able to reduce disparity in the outputs of LLM's for a classification task on average. When we observe the mean and standard deviations for demographic parity, we see that demographic parity is consistently reduced for outputs when compared to zero shot prompting for GPT-4 across all runs, showing that the coresets can help reduce disparity. For GPT-3.5, while the average disparity is reduced across runs, such consistency is indeed not observed, owing to a diverse set of outputs from the large language model. We will add this discussion to the final version of the draft.

References:

• [1] Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimination. Knowl. Inf. Syst., 33(1):1–33, October 2012.

• [2] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, pages 259–268, New York, NY, USA, 2015. ACM.

• [3] Gillis, Talia B., Vitaly Meursault, and Berk Ustun. "Operationalizing the Search for Less Discriminatory Alternatives in Fair Lending." In The 2024 ACM Conference on Fairness, Accountability, and Transparency, pp. 377-387. 2024.

We are grateful to the reviewer for their time and comments in the review of our work; we answer each point below.

1. While we acknowledge that the ideas for the reformulation and part of the complexities considerations are adapted from [1, 2] ([56, 71] in the original references) we would like to emphasize the significant contributions of this work:

• Novel algorithm. Our novel algorithm FWC represents the first fair coreset approach explicitly focusing on downstream learning, in contrast to existing methods that emphasize local properties of generated samples (Section 4);

• Theoretical claims. We support our novel algorithm FWC with theoretical claims regarding its convergence properties (Section 5.2) and generalization analysis (Section 5.3), as well as the effect on downstream learning tasks (Proposition 2.1 and Appendix B.1);

• Connection to k-means. We establish a practical connection to the k-means algorithm, thereby extending FWC's applicability beyond fairness considerations (Section 6);

• Empirical results. We demonstrate FWC's effectiveness through empirical results on synthetic data for scalability, as well as on real datasets and two LLMs for downstream classification tasks (Section 7 and Appendix C).

2. The features for the generated data are the same as the ones in the original training data, but the values of such features would be different. For instance, in Appendix C.2, in ``Using FWC to correct biases in LLM'' we include a textual example of how one of our generated coresets would look like. The value of each feature would depend on the chosen cost function $c$; in Section 4.2 we highlight the case of the $L_1$ and $L_2$ distance, as well as how to select feature values if only values existing among the training data features can be selected (akin to k-medoids).

3. We have corrected the inconsistencies, thanks for pointing them out.

4. In our work, the synthetic coresets $\hat{Z}$ lie in $\mathcal{Z}^m$. Only when $\theta\subseteq \mathbb{R}^m_+$ and $\sum_j \theta_j = m$, the empirical distribution $p_{\hat{Z};\theta}:= \frac{1}{m}\sum_{j=1}^m \theta_j \delta_{\hat{Z}_j}$ is a valid probability measure.

References:

• [1] G. Peyré, M. Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6):355–607, 2019.
• [2]Z. Xiong, N. Dalmasso, A. Mishler, V. K. Potluru, T. Balch, and M. Veloso. FairWASP: Fast and optimal fair wasserstein pre-processing. Proceedings of the AAAI Conference on Artificial Intelligence, 38(14):16120–16128, Mar. 2024.

We are grateful to the reviewer for the effort spent reading our paper and for the encouraging comments. Below are our responses to the questions raised:

1. First of all, we apologize for a typo in (13). The minimum over $\hat{X}_i \in \mathcal{X}$ in (13) should be corrected to the minimum over $\hat{X}_j \in \mathcal{X}$, replacing the subscript $i$ with $j$. We appreciate the reviewer’s attention to detail in identifying this typo. With this typo corrected, then we can observe from (12) that, for each $j\in[m]$, the variable $\hat{X}_j$ only affects the corresponding $\hat{Z}_j$, because $\hat{Z}_j = (\hat{d}_j,\hat{X}_j,\hat{y}_j)$. Different $\hat{Z}_j$ terms are independent of each other in the objective function of (12), so (12) can be decomposed into subproblems that optimize each $\hat{Z}_j$ (which is essentially $\hat{X}_j$). (12) and (13) are equivalent in the sense that they share the same optimal solutions.

2. The discrete Monge--Kantorovich (optimal transport) problem has a similar structure as (17), but is more complex. The constraint of (17) only requires that the sum of each $\underline{column}$ of $P$ equals $\frac{1}{n}$, so (17) can be easily solved by computing the smallest component of each row of $C$. An optimal solution $P$ can be a matrix where all entries of each row are zero except for the one corresponding to the smallest component of that row in $C$. In contrast, a typical optimal transport problem that is written as an LP also requires the sum of each $\underline{row}$ to equal to some given values. For this reason, optimal transport problems do not have easily computable closed-form optimal solutions. In the discrete Monge--Kantorovich problem, this pair of constraints on the sum of rows and columns essentially state that the marginals of the probability measure (the decision variable) on the product space must equal the two given probability measures.

We are thankful to the reviewer for their time and thoughtful feedback. As the reviewer has pointed out, several notions of fairness exist in the literature. Focusing on the classification setting, chapter 3 in [2] classifies these notions into independence, separation, and sufficiency. Demographic parity falls in the class of the independence notion, and hence, other measures of fairness that are closely related, eg., disparate impact, would also improve when optimizing for demographic parity. However, as highlighted in [2], other notions of fairness, such as separation may not simultaneously be satisfied. Our work is focused on demographic parity and cannot guarantee an improvement in these other measures.

To test this, we evaluated our work, which optimizes for demographic parity, on the equalized odds measure, which falls under the notion of separation. When we consider equalized odds, FWC is not a part of the Pareto frontier for the Drug dataset, and more generally, FWC performance is not as competitive. This is in contrast to demographic parity: in Figure 1, FWC sits on the Pareto frontier across all datasets for fairness-performance trade-off in downstream classification (see the addendum in the global rebuttal above for the updated version of Figure 1). We have included a table below to indicate which FWC models are part of the Pareto frontier when considering demographic parity versus equalized odds, and will add this discussion to the paper.

Finally, while we acknowledge that steps (2) and (3) are built from [1], we would like to emphasize the significant contributions of this work and especially note that: (i) our novel algorithm FWC represents the first fair coreset approach explicitly focusing on downstream learning, in contrast to existing methods that emphasize local properties of generated samples; (ii) we support FWC with theoretical claims in Propositions 2.1, Theorems 5.3, 5.4, Proposition 5.5 (as well as additional insights in Appendix B.1); (iii) we establish a practical connection to the k-means algorithm, thereby extending FWC's applicability beyond fairness considerations (Section 6); and (iv) we demonstrate FWC's effectiveness through empirical results on synthetic data for scalability, as well as on real datasets and two LLMs for downstream classification tasks (Section 7 and Appendix C).

References:

• [1] Z. Xiong, N. Dalmasso, A. Mishler, V. K. Potluru, T. Balch, and M. Veloso. FairWASP: Fast and optimal fair wasserstein pre-processing. Proceedings of the AAAI Conference on Artificial Intelligence, 38(14):16120–16128, Mar. 2024.

• [2] Barocas, Solon, Moritz Hardt, and Arvind Narayanan. Fairness and machine learning: Limitations and opportunities. MIT press, 2023.