Fair Wasserstein Coresets

Summary

This paper introduces a new data distillation technique called Fair Wasserstein Coresets. The general idea is to create a synthetic core set along with sample weights to represent a larger dataset, by minimizing the Wasserstein distance between core set and dataset, while ensuring a fairness constraint is satisfied. The paper develops a majority minimization algorithm for this Wasserstein problem and empirically validates it on several data sets demonstrating a competitive fairness utility trade-off.

Strengths

- The Wasserstein problem is well-formulated with theoretical guarantees. - The connections with k-medoids is intuitive.

Weaknesses

- I suspect there is a potential error in Proposition 2.1, specifically pertaining to the inputs and outputs defined in these functions. Note that z consists of inputs ($d, x$) and outputs ($y$) of the NN, whereas $g_{\psi}$ is an MLP, i.e., it is a function that takes only $(d, x)$ as input. From [69 (original reference)], the MLP satisfies the Wasserstein inequality but only on the marginal distributions over p_{(x,d)} rather than over $p_{Z}$. This may be resolved if we consider not the Wasserstein distance of the MLP output, but instead the Wasserstein distance of the function $h(z) = | g_{\psi}(x,d) - y |$. - What do you mean in Lemma 3.1 that the corset is “no better than the best fair Wasserstein corset formed by $m |D||Y|$ data points”? I suspect you mean better with regard to achieving a lower Wasserstein distance, but please clarify. - The empirical analysis in Figure 1 is hard to parse. Can you measure the Pareto frontier from all of the observations and demonstrate that FWC is dominant? FWC seems Pareto efficient for Adult, Crime, and Drug, but not Credit potentially — but it is hard to see. - It is hard to understand the trade-offs between accuracy and disparity in the LLM experiments in Table 1, just by reporting these numbers. How important is it that the disparity dropped by 0.009 at a 2.97 point loss in accuracy? Again, it would be important to demonstrate some Pareto efficiency. Furthermore, the change in accuracy and disparity do not seem statistically significant based on the SD reported.

Questions

- Please clarify the potential error and comment about Proposition 2.1. If there is an error, what are the consequences with subsequent theoretical results?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are thoroughly discussed in the Appendix.

Summary

The paper gives an algorithm to generate smaller weighted synthetic dataset from real data set such that the synthetic data can enforce demographic parity when used for downstream tasks. This is achieved by solving an optimization problem of minimizing the Wasserstein distance between the two dataset distributions along with demographic parity-based fairness constraint. The authors describe how to efficiently solve this problem by reformulating it and subsequently using a majority minimization algorithm to solve the resultant nonconvex problem. They provide convergence guarantees for the algorithm and also generalization bounds for the solution. The theoretical results are supported by experiments on real and synthetic datasets.

Strengths

1) The paper for the most part is written clearly with some minor writing issues (see weaknesses). It is well structured and not too difficult to follow the high-level ideas. Both fairness and scalability are relevant issues so the paper will be of interest to the community. 2) I could not check all proofs, but the theoretical results appear sound. The connection between the unconstrained problem and Lloyd's algorithm for $k$-means is neat. 3) The authors have performed experiments on both real and synthetic datasets and compared with a number of existing methods. As such the paper is a good mix of theory and practice.

Weaknesses

1) The paper seems to borrow a lot of ideas and proof techniques from existing works like [56], [71] and others. for e.g. the reformulation, ideas to speed up the algorithm etc. As such I am not entirely sure about the novelty quotient of the work. It would be better if the authors can highlight why the modifications to techniques from existing works are non-trivial. 2) The explainability of the synthetic data will be very less. Specifically, as far as I understood, the authors are assigning the output label and sensitive attribute value to the generated data points just in same proportion as that in the original data. It is not clear to me what does this mean for the individual synthetic data points. Also do the features in the generated synthetic data correspond exactly to the features in original data? 3) I suggest the paper be proofread for minor corrections in writing: E.g.: In the contributions make the 'w' 's capitalized. On line 171 the authors say $P \geq 0$ (which I think means each entry in non-negative) while on line 258 it is $P \geq \mathbf{0}$. Maintain the consistency. 4) Should not the weight of the synthetic data sum to $n$ and not $m$ (line 141 $\Delta_m$)? Typically, we try to preserve the weight of the original data in expectation while reweighing the sampled points. Please Clarify.

Questions

See weaknesses

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

See Weaknesses

Summary

This paper proposed to extract coresets from a set of data samples using Wasserstein distance with fairness constraints. The authors formulates this problem as a minimization with linear constraints. The coreset selection is over the whole input space, not just from original data samples. The importance / weight of each coreset sample are also optimized. Extensive experiments show this method achieves better fairness-utility tradeoff, and can be applied in LLMs to reduce bias.

Strengths

The paper is nicely written and easy to follow. I appreciate the detailed steps and neat reformulations of the optimization problem. Theoretical guarantees are provided. The experiments supports the effectiveness of the proposed method very well.

Weaknesses

1. In section 4.2 (line 203), how can problem Eq.(12) be separated into subproblems as in Eq.(13), are the optimal solutions of all subproblems the same and equal to the solution to (12)? 2. In section 6 (line 259), why are the minimizers of problem (17) always has only one non-zero entry in each row? As problem (17) can be seen as a relaxed version of discrete Kantorovich problem, where we can't say anything about the sparsity of the optimal plan. Please elaborate.

Questions

See Weaknesses.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors included detailed limitations.

Summary

This paper talks about "fair Wasserstein coresets", weighted representative points generated to represent the original datasets. The goal is to meet two purposes: 1) the Wasserstein distance of the coreset and the input data set is minimized, 2) fairness in terms of demographic parity. Having a small Wasserstein distance can help to bound the downstream discrepancy for ReLu activated perceptrons. The authors formulate the problem as an optimization problem (4). There are four steps: 1. Manually set the proportion of each combination of decision (Y) and feature (D). 2. Formulate linear constraints for the fairness constraint. This one borrows directly from [71]. 3. Formulate the Wasserstein distance optimization by using [56] 4. Simply further After that, the problem is not convex. The authors use "majority minimization" [52, 38] to solve it. Specifically, one defines a convex surrogate function that upper bounds the non-convex function, and optimizes the convex function. Section 5 reports theoretical guarantees: running time of the algorithm, convergence guarantee for the surrogate function, and last bound the generalization guarantees. Experiments are reported in the last section: e.g., improving fairness in LLM. On the positive side, the problem formulation is interesting and valid, Wasserstein coreset with fairness consideration. The use of this coreset for downstream applications make sense. Thus the problem and solution have merit. Experiment are thorough. The weaknesses (or limitation in significance) is that both crucial steps (2) and (3) are basically using prior work. The theoretical results are standard. Summarizing I feel that the paper is OK but would give a weak accept.

Strengths

On the positive side, the problem formulation is interesting and valid, Wasserstein coreset with fairness consideration. The use of this coreset for downstream applications make sense. Thus the problem and solution have merit. Experiment are thorough.

Weaknesses

The weaknesses (or limitation in significance) is that both crucial steps (2) and (3) are basically using prior work. The theoretical results are standard.

Questions

I understand that there are many different notions of fairness and the authors focus on one of them, demographic parity. This is OK. One suggestion is that if the authors can provide some discussions and insights on how the results may improve other notions of fairness it will be valuable to have.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Score adjusted

Thanks for clarifying the theoretical result and updating your figures to show the Pareto frontier. The discussion in (#4) is useful and I recommend you include this discussion in your final version. I have updated my score accordingly.