Fair Wasserstein Coresets
Authors: Zikai Xiong
Niccolo Dalmasso
Shubham Sharma
Freddy Lecue
Daniele Magazzeni
Vamsi K. Potluru
Tucker Balch
Manuela Veloso
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithmic Fairness
Nonconvex Optimization
Coresets
Primary area: fairness
TL;DR: We present Fair Wasserstein Coreset (FWC), a novel coreset approach to generate fair synthetic representative samples along with sample-level weights to be used in downstream learning tasks.

Abstract: Data distillation and coresets have emerged as popular approaches to generate a smaller representative set of samples for downstream learning tasks to handle large-scale datasets. At the same time, machine learning is being increasingly applied to decision-making processes at a societal level, making it imperative for modelers to address inherent biases towards subgroups present in the data. While current approaches focus on creating fair synthetic representative samples by optimizing local properties relative to the original samples, their impact on downstream learning processes has yet to be explored.  In this work, we present fair Wasserstein coresets ($\texttt{FWC}$), a novel coreset approach which generates fair synthetic representative samples along with sample-level weights to be used in downstream learning tasks. $\texttt{FWC}$ uses an efficient majority minimization algorithm to minimize the Wasserstein distance between the original dataset and the weighted synthetic samples while enforcing demographic parity. We show that an unconstrained version of $\texttt{FWC}$ is equivalent to Lloyd's algorithm for k-medians and k-means clustering. Experiments conducted on both synthetic and real datasets show that $\texttt{FWC}$:  (i) achieves a competitive fairness-performance tradeoff in downstream models compared to existing approaches, (ii) improves downstream fairness when added to the existing training data and (iii) can be used to reduce biases in predictions from large language models (GPT-3.5 and GPT-4).

Fair Wasserstein Coresets
Zikai Xiong'
Niccolò Dalmasso
Shubham Sharma
Freddy Lecue
Daniele Magazzeni!
Vamsi K. Potluru
Tucker Balch
Manuela Veloso
Abstract
Data distillation and coresets have emerged as popular approaches to generate a smaller representative set of samples for downstream learning tasks to handle large-scale datasets. At the same time, machine learning being increasingly applied to decision-making processes at societal level, making it imperative for modelers to address inherent biases towards subgroups present the data. While current approaches focus creating fair synthetic representative samples by optimizing local properties relative to the original samples, their impact on downstream learning processes has yet to be explored. In this work, we present fair Wasserstein coresets (FWC), a novel coreset approach which generates fair synthetic representative samples along with sample-lveel weights be used in downstream learning tasks. FWC uses an efficient majority minimization algorithm to minimize the Wasserstein distance between the original dataset and the weighted synthetic samples while enforcing demographic parity. We show that an unconstrained version of FWC is equívalent Lloyd's algorithm for k-medians and k-means clustering. Experiments conducted on both synthetic and real datasets show that FWC: (i) achieves competitive fairness-utility tradcoff in downstream models compared to existing approaches, (ii) improves downstream fairness when added the existing training data and (iii) can be used to reduce biases in predictions from large language models (GPT-3.5 and GPT-4).
Introduction
In the last decade, the rapid pace of technological advancement has provided the ability of collecting. storing and processing massive amounts of data from multiple sources (65) As the volume of data continues surge, it often surpasses both the available computational resources well the capacity of machine learning algorithms. In response to this limitation, dataset distillation approaches aim reduce the amount data by creating a smaller, yet representative, set of samples; see 880 40) for comprehensive reviews on the topic. Among those approaches, coresets provide a weighted subset of the original data that achieve similar performance to the original dataset in (usually) specific
machine learning task, such as clustering 26 21, Bayesian inference online learning [9] and classification [16], among others.
In tandem with these developments, the adoption of machine learning techniques has seen a surge in multiple decision-making processes that affect society large [69 81]. This proliferation of machine learning applications has highlighted the need to mitigate inherent biases in the data, as these biases can significantly impact the equity of machine learning models and their decisions (14]. Among many definitions of algorithmic fairness, demographic parity is one of the most prominently used metric
299] enforcing the distribution of outcome of machine learning model to not differ dramatically across different subgroups in the data.
'Operations Research Center, Massachusetts Institute of Technology, zikai @mit edu J.P.Morgan AT Research, {niccolo. dalmasso, shubham. x2. sharma, freddy. daniel: magazzeni, vamsi. k. potluru, tucker balch, manuela. veloso jpmchasee. com
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Current methodologies for generating smaller set of fair representative samples focus on the local
characteristics of these samples with respect the original dataset. For instance. [3]
30
24
obtain representative points by clustering while enforcing each cluster to include the same proportion
of points from each subgroup the original dataset. In another line of work, [33 44
53
72 I2
create representative points by ensuring that points in the original dataset each have at least one representative point within a given distance in the feature space. While these methods can successfully reduce clustering cost and ensure more evenly spread-out distribution of representative points in the feature space, it is unclear whether such representative samples can positively affect performance or discrimination reduction in downstream learning processes. As the induced distribution of the representative points might be far away from the original dataset distribution, downstream machine learning algorithm might lose significant performance due to this distribution shift, without necessarily reducing biases in the original data (as we also demonstrate empirically in our experiments).
Contributions In this work, we introduce Fair Wasserstein Coresets (FWC), a novel coresct ap- proach that not only generates synthetic representative samples but also assigns sample-level weights to be used in downstream learning tasks. FWC generates synthetic samples by minimizing the Wasser- stein distance between the distribution of the original datasets and that of the weighted synthetic samples, while simultaneously enforeing an empirical version of demographic parity. The Wasserstein distance is particularly suitable to this task due to its various connections with downstream learning processes and coresets generation (Section 2 Our contributions are as follows:
1. we show how the FWC optimization problem be reduced to nested minimization problem in which faimess constraints are equivalent to linear constraints (Section B);
2. we develop an efficient majority minimization algorithm [56. 39 to solve the reformulated problem (Section 4. We analyze theoretical properties of our proposed algorithm and FWC (Section (5) and show that, in the absence of fairness constraints, our algorithm reduces to an equivalent version of Lloyd's algorithm for k-means and k-medians clustering, extending its applicability beyond fairness applications (Section 6);;
3. we empirically validate the scalability and effectiveness of FWC by providing experiments on both synthetic and real datasets (Section 7 In downstream learning tasks, FWC result in competitive fairness-utility tradcoffs against current approaches, even when we enhance the fairness of existing approaches using fair pre-processing techniques, with an average disparity reduction of 53% and 18%, respectively. In addition, we show FWC can correct biases in large language models when passing coresets examples to the LLM, reducing downstream disparities by 75% with GPT-3.5 [55] by 35% with GPT-4 [. Finally, we show FWC can improve downstream faimess-- tradeoffs in downstream models when added to the training data (via data augmentation, see Appendix
Finally, we refer the reader to the Appendix for more details on the optimization problem (Section A theoretical proofs (Section B) and further experiments and details (Section C
2 Background and Related Work
Notation We indicate the original dataset samples {Z,) with Z; X,, E Z (D x X x )) C Rd, where X indicates the non-sensitive features, D indicates one or more protected attributes such as ethnicity or gender, and Y is decision outcome. In this work, we assume D and Y to be discrete features, i.c., to have a finite number of levels so that [D] < n and | < n. For example, Y might indicate a credit card approval decision based on credit history X, with D denoting sensitive demographic information. Given set of weights (0); define pz;0 the weighted distribution of dataset { { as P2:0 n delta distribution, i.e., the unit mass distribution at point I E X. Using this notation, we can express the empirical distribution of the original dataset by setting 0: = e, = for any i, i.e. n PZ:e- Em= 6z0z,- For matrix A, A denotes its transpose. For two vectors (or matrices) (u, v)
1 Σ"_ 0:62, where 8, indicates the Dirac
def. Σ; uvV, is the canonical inner product (the Frobenius dot- dot-product for matrices). We define
1 def. (I...., 1) E RT.

---

Wasserstein distance and coresets Given two probability distributions p1 and pa over metric space X. the Wasserstein distance, or optimal transport metric, quantifies the distance between the two distributions as solution of the following linear program (L.P):
We(P1.P2 P2)
min xell(pr.Pa)
c(11,
(I)
XxX
with [p1 P2) indicating the set of all joint probability distributions over the product space X' A' with marginals equal to (p1. P2) [5]. The operator c(z, y) represents the "cost" of moving probability mass from and y,, and reduces
matrix C' if the underlying metric space X' is discrete.
The Wasserstein distance has several connections with downstream learning processes and coresets. Firstly, the higher the Wasserstein distance between the weighted representative samples P2.a and the original dataset PZ:e. the higher the distribution shift, the more degradation might expect in terms of downstream learning performance [62). Secondly, the Wasserstein distance between two probability distributions can also be used to bound the deviation of functions applied to samples from such distributions. Define the following deviation:
d(P2:0 PZ:e)
def.
sup SEF
E Eamp2 f(z) - (sspp..f f())
When F is the class of L. Lipschitz-contimuuu functions with Lipschitz constant equal or less than 1, the deviation d(pz.0: P2:c) is equal to I-Wasserstein distance Wi ((22,::P:::
666 [4]. The connection
with learning processes and the downstream deviation d(p; (():x : Die) is immediate when considering Lipschitz continuous classifiers with Lipschitz constant less than 1 (such as logistic regression Lipschitz-constrained neural networks 22 For other classifiers, we note that the I-Wasserstein distance still bounds the downstream discrepancy: in Proposition 2.1 we show that the I- I-Wasserstein distance bounds the downstream discrepancy for ReLu-activated multilayer perceptrons (MLPs), which we use our experiments on real datasets (Section 7
Proposition 2.1. Let 9v gk be the class of K layer multilayer perceptrons with ReLu activations. Then, the downstream discrepancy in downstream performance of ge applied to samples from Pi& and D'y is bounded by the 1-Wasserstein distance:
d(p ((P( ((x.))))
sup
B Be (x, D1 d) T. T.
Io
gvegx
where La is the MLP Lipschitz constant upper bound defined in
775 Section 6.1, Equation (8)).
We point out that minimizing the Wasserstein distance, hence bounding the downstream performance as in Equation @2. is equivalent to the definition of a measure coresets proposed by [15]. The Wasserstein distance also connected coresets in the sense of the best discrete approximation of continuous distributions. Considering a feature space endowed with continuous distribution, minimizing the p- w--asserstten distance across all the distributions of size m topologically equivalent to identify the samples of size that provide the best Voronoi tessellation of the space in I.p sense [57 Although other definitions of coresets using Wasserstein distance have been proposed in the literature, they require either to solve the underlying optimal transport problems or the knowledge of the downstream classifier and loss function [15 82 43) FWC is agnostic to any downstream model or loss function, and uses an efficient implementation that does not actually incur in the usual high cost connected to optimal transport. By adapting the approach proposed by [77], we solve an equivalent re- re-formulated linear optimization problem, which is more computationally tractable than classic approaches such as the simplex or the interior point method (see Section
Also known statistical parity, demographic parity (DP) imposes the decision outcome and protected attributes to be independent [18]. Using a credit card approval
Demographic parity
In such cases, d(p,x. by P).) (P(Px,.b)
P & W/ (p2,g p2:c), Lemma B.I
3

---

decision example, demographic parity enforces an automatic decision process to approve similar proportion of applicants across different race demographics. DP is one of the most extensively analyzed fairness criterion; we refer the reader to [29] for review. In this work, we use the demographie parity definition by [10], which enforces the ratio between the conditional distribution of the decision outcome across each subgroups p(y| D d) and the marginal distribution of the decision outcome p(y) to be close to 1 in a given dataset. We refer to the "empirical version" of demographic parity to indicate that the conditional and marginal distributions are quantities estimated from the data. Note that the demographic parity definition we adopt enforces a condition on the weighted average of the conditional distributions across groups, which is different from more recent approach of using Wasserstein distance, and specifically Wasserstein barycenters, to enforce demographic parity 22 23 78]
3
FWC: Fair Wasserstein Coresets
Given a dataset {2,) our goal is to find a set of samples {2 and weights (0,)% such that m < n and that the Wasserstein distance between PZ:e and P2:0 is as small as possible. In addition, we use the fairness constraints proposed by [0] to control the demographic parity violation for the P2;0 distribution. Let p2.e ( (yld) indicate the conditional distribution P2:0 = y D = d).
Imposing a constraint on the demographic disparity violation then reduces to requiring the conditional distribution under the weights {0, jejm) to be close target distribution py; actoss all possible values of the protected attributes D,
(2.)(Uld) Pyr (v)
(12 (120
e, v VdED,yE)
where is parameter that determines the maximum fairness violation, and J(,,)) is the probability ratio between distributions as defined 10].
Using the notation above, our goal can then be formulated as the following optimization problem:
min Am,2Ez
Wolpz,0:77:
s.t. (p2oluld) S AdE
i-1 6, = m) Note that the optimization where Am indicates the set of valid weights {0 E ERT >
problem in (4) shares some similarities with the optimization problem in 777 in using the Wasserstein distance distance metric between distributions and using (3) to enforce demographic parity.
However, [77 only provide sample-level integer weights for the original dataset and do not generate
any new samples, while our approach provides a separate set of samples (2, /mm with associated real-valued weights (6, bm with m < n.
We now take the following steps to solve the optimization problem in (4 (i) we reduce the dimen- sionality of the feasible set by fixing V and Î priori, (ii) we formulate the fairness constraints as linear constraints, (iii) we add artificial variables to express the objective function and (iv) we simplify the optimization problem to minimizing a continuous non-convex function the {X, 1m
Step 1. Reduce the feasible set of the optimization problem As in practice all possible Y, and D; are known a priori, and there are only a limited number of them, we can avoid optimizing over them and instead manually set the proportion of each combination of ý and D. This reduces the optimization problem feasible set only over An m and n The following lemma shows that this in fact does not affect the optimization problem:
Lemma 3.1. For any m O, the best fair Wasserstein coresel formed by m duta points {2, : E [m]] no better (i.e., the optimal Wasserstein distance value is no lower) than the best fair Wasserstein coreset formed by m [)] data points {(d, X4, y)x i [mm), d E D. E V).

---

Hence, we simply set the proportions of {(D,, heem in the coresets to be similar to their respective proportions in the original dataset. The optimization problem then reduces to
min D DEAm:XEXm
(5)
J (P2oluld), Se, VdED,yE,,
s.t.
whose solutions the features in the coresct {X,]
} and the corresponding weights {0,)
Step 2. Equivalent linear constraints Following 777, the fairess constraint in Equation (3 can be expressed as 2| [D) linear constraints on the weights 0, as the disparity reduces to the following for all d D,y E
Σ
0, s -1+ (v)
Σ
0.
Σ
0. 0.2 (1 .prr(())
Σ
0.
ve(m]:D, D.
ie m.
ie[m]:D,=d
We can express these by using a 2 -row matrix A as A0 2 0.
Step 3. Reformulate the objective function by introducing artificial variables When keeping the samples X fixed, distance in the objective as a linear program with mn variables. By indicating the transportation cost matrix C(X), we define its components as follows,
follow [60] to derive equivalent formulation of the Wasserstein
c(X) def. cl2,, 2n), for i E [m], E [m]]
Note that C(X) is convex function of X when, e.g., using any L norm to define the transportation cost. Therefore, now the problem is equivalent to
min TEX"M,BEA. PERnXo
(C(8),
(6)
s.t. Pim
1,
P
0, P 0, A0 0.
Step 4. Reduce to an optimization problem of X
As from one of the constraints get 0
m P I, we further simplify problem 66 as:
min
()
s.t.
P1 m
- 1,. P> 0, AP 1, 2 0.
Let F(C), function F of C, denote the optimal objective value of the following optimization problem
min
P)
PERexm
s.t.
P1m 1,, P 2 0, APT 1, 2 0
and then problem 7 is equivalent
min F(C(X)) x
In 9 the objective is continuous but nonconvex with respect to X. Once the optimal X is solved,
then the optimal P* of the problem 7 is obtained by solving problem () with C' replaced with
C(X+). Finally, the optimal 0* follows by the equation 0* m (P*) 1,, We now provide majority minimization algorithm for solving problem (9)
5

---

Majority Minimization for Solving the Reformulated Problem
Majority minimization aims at solving nonconvex optimization problems, and refers to the process of defining a convex surrogate function that upper bounds the nonconvex objective function, so that optimizing the surrogate function improves the objective function [56] 39). As the algorithm proceeds, the surrogate function also updates accordingly, which ensures the value of the original objective function keeps decreasing. Following this framework, we define the surrogate function g(:; X*) as follows for the k-th iterate X xm
def. (C(X),PE)
(10)
in which PK is the minimizer of problem with the cost C C(
With this surrogate function, Algorithm summarizes the overall algorithm to minimize problem In each iteration of Algorithm|] [ cost matrix using the new feature vectors X We separately discuss how solve the optimization
(
line 3 is straightforward since it only involves computing the new
problems lines 4 and 5 below.
Algorithm 1 Majority Minimization for Solving (9)
Initial feature vectors X and k
2: while True do
3: C -(X**;
>> update the cost matrix updating the surrogate function (Section 4.1
C
4:
PE + optimal solution of problem (8)
5:
X arg min xEXm g X; X*);
>> updating feature vectors (Section
4.2
6:
if
,( 8t) then
7:
0% +- m. (P)) 1i;
D if algorithum has converged, compute optimal weights t return coresets and sample-level weights
8: return 8t. 0
9:
end if
10: A k: + 1;
11:
end while
4.1 Updating the Surrogate Function (Line 4)
To update the surrogate function, we need solve problem (8). which is large-scale linear program. Rather than solving the computationally prohibitive dual problem solve lower-dimensional dual problem by using a variant of the FairWASP algorithm proposed by (77). We adapt FairWASP for cases where the Lagrangian dual problems with reduced dimensior We choose FairWASP over established commercial solvers due its computational complexity being lower than other state of the art approaches such as interior interior-point or simplex method; see Lemma A.2 in Appendix A for more details.
to find the solution of (8) via applying the cutting plane methods on
4.2 Updating Feature Vectors (Line 5)
To update the feature vectors, we need obtain the minimizer of the surrogate function g( (X;8*) i.e.,
min 9(;; xexm
(11)
The above can be written the following problem:
min E sEIm] JE(m]
Σ Σ
cZi, 2,),
(12)
for P = Pt, in which each component of is nonnegative and 2, = (dz, &,, for the known fixed d, and Új. Furthermore, the matrix P is sparse, containing at most non-zeros (as when
*We show this surrogate function adequate, ie.. convex and an upper bound the original objective funetionn, Section As opposed to the scenario where n, which tackled 77

---

updating Pk for problem following m subproblems,
8 see Appendix A Moreover, problem I2
can be separated into the
min Σ X,EX se(m
dZ, P3 for E [m]
(13)
Each subproblem computes the weighted centroid of {Z, i [n), 0f under the distance function c. Therefore, (IT) suitable for parallel and distributed computing. Additionally, since the cost matrix C(X) is convex function of X, each subproblem a convex problem so gradient-bass based methods could converge to global minimizers. Furthermore, under some particular conditions, solving these small subproblems can be computationally cheap:
1. If X' is convex and cZ, def. 1 212. then the minimizer of 13 is the weighted average Eie(n) P.j X Σ
iE[n] Pij-
2. If convex and <Z, 2) def. || 2 l1, then the minimizer of 13 requires sorting the costs woirdinatewwisely and finding the median.
3. If creating new feature vectors is not permitted and X = (x;:1 E [n]], solving 13
requires finding the smallest Eiein]:P, c(Z,, (dy, X, ú,)) for X within the finite set X. The matrix P is highly sparse this operation is not computationally expensive.
5
Theoretical Guarantees
In this section we provide theoretical insights on FWC complexity, convergence behavior of Algorithm as well generalizability of FWC performance on unseen test sets.
5.1 Computational Complexity
First, we consider the FairWASP variant used in Algorithm I line 4. The initialization requires (mm)) flops and uses (n)) space for storing the cost matrix, After that, the per-iteration time and space complexities are both only On))Yl Lemma 5.1 analyzes the computational complexity of our adaptation of the FairWASP algorithm when solving problem (8).
Lemma 5.1. With efficient computation and space management, the cutting plane method has
computational complexity of
(nm + (D|ID)? log(R/e)) (R(e))
(14)
flops and (n DIID) space. Here R denotes the size of an optimal dual solution of 8 and Ō(-)
absorbs m, n, [D). | in the logarithu function.
Hence, the overall complexity of FWC is Ö(mn p log( R/c)). Note that in practice both (D) and |}] are very small compared with the coreset size m and dataset size n, so the overall complexity is almost low O(m)).
5.2 Convergence Guarantees
First, we establish that our proposed surrogate function is indeed convex and a valid upper bound. We then show Algorithm converges to first-order stationary point, within finite iterations if the minimizer of problem 11 is unique. Note that because xx;; = (C(X) Pt), the minimizer is unique whenever the cost matrix C(-) is strongly convex.
Lemma 5.2. The function X(; is convex function of X and a valid upper bound, i.e. g(X; x*) F(C(X)). This inequality holds at equality when X = **
Theorem 5.3. The objective value is monotonically decreasing, i.e., F(C(X++1) S F(C(X*)) for any 2 O. And once the algorithm stops and C(X*) is smooth at & then & is first-order stationary point of 9
Theorem 5.4. When the minimizer of 11 is unique, Algorithm Algorithm@terminnde Iterminates within finite iterations.
7

---

5.3 Generalization Guarantees
Proposition 5.5 below bounds the distance and demographic parity between the FWC samples and the true underlying distribution of the data, from which the original dataset of size n was observed. This generalizes the performance FWC unseen test sets sampled from the data generating distribution. Proposition 5.5. Let À indicate the distance between P2:0 and pze after convergence of FWC i.e. W(p2:0 PZ:e) X. Let qz be the true underlying distribution of the data supported over R2, with marginal distribution over y bounded away from zero, so that p minyey qz(y) 0. Then with probability 1 - a:
Wolp. 92) - + ((log(1/a))))))))) [= (4n
(15)
sup (p22vVl). S O (v log 2/a
(16)
np²
yE dED
In addition, in Appendix B.I we consider the task of learning using FWC samples. We show that the error in downstream learning tasks can be seen as the sum of (i) the approximation error FWC samples make with respect to the original dataset and (ii) how well Y can be learnt from X and ò from FWC samples. However, as FWC samples { {2, ) are not i.i.d., standard sample complexity results in e-g., empirical risk minimization, do not apply, highlighting the hardness in developing finite-sample learning bounds in this setting.
An Alternative View: Generalized clustering algorithm
When the faimeess constraints are absent, problem (8) reduces to:
min minpeR=xm
(C,
(17)
s.t.
P1 - P 0nxm
The minimizer P of (17 can be written in closed form. For each E [n], let Ciy: denote smallest component on the i-th row of C. Then the components of minimizer pt can be the indicator function). Hence, without fairness constraints, FWC corresponds to Lloyd's algorithm for clustering. Specifically, Lloyd's algorithm iteratively computes the centroid for each subset in the partition and subsequently re- re-partitions the input based on the closeness to these centroids 42]; these are the same operations FWC does in optimizing the surrogate function and solving problem (7). Thus, when c(x, y) is correspondingly defined as ||æ 2//1 or ||æ y1l2- FWC corresponds to Lloyd's 'ss algorithm applied k-medians k-means problems, except the centroids have fixed values for ò and Y (see Section
written as P 1 I(j = -J") (where
Comparison with k-means and k-medoids FWC and Lloyds' algorithm for k-means or k-median share similar per-iteration complexity, with the main difference in complexity due to solving problem (8). We solve this problem efficiently by utilizing variant of the FairWASP approach by [77] (Section 4.1 J. hence avoiding the usual complexity in solving optimal transport problems. As shown in Section the leading term in the runtime complexity is ((m)), which comes from calculating and storing the cost matrix C. This level of complexity is the same as those in k-means and k-medoids. In addition, from experiments also that the per-iteration complexity of FWC is roughly linear with the original dataset size n (see the runtime experiment in Section and Appendix C
Experiments
Runtime analysis We evaluate the runtime performance of FWC by creating a synthetic dataset of dimension n and features of dimension p. with the goal of creating a coreset of size (see Appendix C for details). We fix two out of the three parameters to default values (n, m. p) = (5000, 250, 25) and vary the other across suitable ranges, analyse the runtime and total number of iterations. [i top left, and Table in Appendix C.I show the runtime and number of iterations when increasing
dataset size n from 1,000 to 1,000,000, with averages and standard deviations over 10 separate runs; both the runtime and number of iterations grow proportionally to the sample size n. Figure 2 in Appendix C.T also shows that requiring a larger coreset size m implies the need of fewer iterations but longer iteration runtime, as more representatives need to be computed.

---

Real datasets results We evaluate the performance of FWC on 4 datasets widely used in the
fairness literature 19: (i) Adult M (ii) German Credit 128. (ii) Communities and Crime [64] and (iv) Drug 120 For each dataset, we consider 3 different coreset sizes m = 5%, 10%, 20% (apart from the Adult dataset, in which we select m equal to 0.5%, 1% and 2% due to the large
dataset size). We compare our approach with: (a) Fairlets and IndFair. two fair clustering
approaches by [4] and [1]. (b) K-Median Coresets, a coreset approach by (3). (c) k-means [42] and k-medoids [45 58, two classic clustering approaches and (d) Uniform Subsampling of the original dataset. For FWC, we consider three different values of the faireess violation hyper-parameters for the optimization problem in ( We compute the fairness- 2-layer multilayer perceptron (MLP) classifier with ReLu activations on the coresets created by each approach and then evaluating the classifier demographic disparity (fairesss) and AUC (utility). F shows the model with the best fairness-utility tradeoff' across the three coreset sizes m, for each approach. FWC obtains equal or better fairness-utilityy tradeoffs (smaller disparity at the same level of utility, higher utility with the same disparity, or both) across all datasets, and performance remains competitive even when using a fairness pre- pre-processing approach (3). Appendix CC2 includes more experiments and details, which highlight that: (a) FWC consistently achieves coresets that are closer in distribution the original dataset with respect to the other methods and, although not natively minimizing clustering cost, also provide competitive performance for smaller datasets (Tables and (b) when added to the training data using the data augmentation schema proposed by [68) Section 2.1] FWC generally either increase the performance or reduce the demographic disparity the downstream learning process.
tradeoff by first training
toradin Rantimee [g)
PWC Runtime Analysis (p=25, m5250)
Adult Dataset
Adul: Dataset (with Fair Pro Processing)
0.80
0.80
60
0.75
0.75
20-
1200
1000
0.65
800-
400
600
0.00
FAC le 0.313
FOR 8:500
Kieedinn Cor.
uniom Subuamping
0.60
PMC
Uniomm to
Golecke Cos
200
2e45
4ee-
66+5
8e-5
Te-4
0.55
D.64
0.06
6.68
0.15 0.32
0.55
5.62
0.63
0.00
0.05 3.66 0.07
Original Dataset Sample Size
Demagraphie Disparty
Demagraphi Daparity
Credit Dataset
Crime Dataset
Drug Dataset
0.70
0.900
0.82
0.65
0.875
0.80
0050
0.850
0.78
y 0.55
0.825
0.76
20.50
0,800
0.74
PWC 6o 2.01
PW 05
1st Far Car
Kntediin Cur
0.775
FMC to 2211
FMC te 9.311
Esd Nk: for
Keedka Cir
0.72
0.70
MIC 554)
led sir Oir
Kitelin Cer
0.35
rents HEMoemo)
Kikeer Kitesiiiee
Suburrpiig
0.725-
Nate:: (cMarrs
Kileams Reeacie
0.68
Kiltaars
Hater (eModaed
0.66
0.30
0.01
0.02 Demograshic Disperity
0.65
0,700
6.25 0.00
0.45
0.5250. $.300.550.07550
1500. 1750.200
Demographic Disprrty
Demagraphir
Figure 1: Top left: FWC runtime when changing the original dataset size n. Others: Fairness- utility tradeoff on real datasets for downstream MLP classifier, selecting the model with the best mairness-utiligg tradeoff across three different coreset sizes m, with averages taken over 10 runs. FWC consistently achieves comparable/better tradeoff as shown by the Pareto frontier (dashed red line, computed over all models and coreset sizes), even when adjusting the other coresets with a fairness pre-processing technique [33]. See text and Appendix C.2 for more details.
Using FWC to improve fairness for LLM 76 evaluate GPT-3.5 and GPT-4 for fairness on predic- tive tasks for the UCI Adult dataset in zero and few shot setting. We use similar evaluation setup and use FWC in the few shot setting as examples and evaluate the results for the gender protected attribute. Specifically, we transform the tabular data into language descriptions, and ask GPT-3.5 Turbo and GPT-4 to perform classification tasks on it. We select 200 samples to construct the test set and use a set of 16 samples found using FWC as examples. Further details on this experiment are provided in the appendix. The results are shown in [ Examples provided by FWC help reduce demographic disparity more than providing balanced few shot examples, while losing on predictive accuracy (note that the drop accuracy is similar to the drop observed in (76) and is representative of the fairness-utilee trade-off). Owing to the token limitation of LLM's, s, these representative coresets
9

---

can evidently be valuable to provide small set of samples that can help mitigate bias. When accounting for the standard deviations for demographic parity in Table FWC reduces the LLM bias when compared to zero shot prompting for GPT-4 across all runs. For GPT-3.5 Turbo, 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. Due to limited availability of computational resources (associated with querying these models), we leave a more thorough evaluation across different datasets and models to future work.
Table I: Using the same setup as in [6.,, we use GPT-3.5 Turbo and GPT-4 LLM's for fairness evaluations, with test set of 200 samples with 0.5 base parity (b, 0.5). Few Shot - FWC is used to provide sixteen examples with weights to the model as examples. Accuracy and demographic disparity (DP) are based on the resulting predictions from GPT-3.5 and GPT-4 models.
Zero Shot
Few Shot (6 0)
Few Shot (FWC)
Adult Dataset
Accuracy
DP
Accuracy
DP
Accuracy
DP
GPT Turbo
53.55 1 0.87
0.040 0.017
57.99
1,88
0.019 00015
55.02 1 1.26
0,010 0.03
GPT4
76.54 1 1.63
0.42 1 0.016
74.39 = 2.86
0.33 + 0.09
65.20 1 0.85
0.27 0.04
8
Discussion and Conclusions
We introduce FWC, a novel coreset approach that generates synthetic representative samples along with sample-level weights for downstream learning tasks. FWC minimizes the Wasserstein distance between the distribution of the original datasets and that of the weighted synthetic samples while enforcing demographic parity. We demonstrate the effectiveness and scalability of FWC through experiments conducted on both synthetic and real datasets, as well as reducing biases LLM predictions (GPT 3.5
and GPT 4). Future extensions include: (i) targeting different fairness metrics such equalized odds
27 49 as well as robustness of carness-performann
tradeoff over distribution shifts [48] 67). (ii)
exploring privacy and explainability properties of FWC [50) [5]. (iii) utilizing coresets for accelerating gradient descents algorithms and test their convergence [47 70 (iv) reformulating the optimization
framework to target deep neural network pruning [52 54 and (v) investigate applications of fair synthetic data in the financial sector [6].
Disclaimer
This paper was prepared for informational purposes by the Artificial Intelligence Research group of JPMorgan Chase & Co. and its affiliates ("JP Morgan") and is not a product of the Research Department of JP Morgan. disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document is not intended as investment research or investment advice, or recommendation. offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute solicitation under any jurisdiction to any person, if such solicitation under such jurisdiction or to such person would be unlawful.
Morgan makes no representation and warranty whatsoever and
References
[1] J. Achiam, Adler, S. Agarwal, L. Ahmad, Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, et al. Gpt-4 technical report. arXiv preprint 20330:2303.08774, 2023.
[2] C. Anil, J. Lucas, and R. Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pages 291-301. PMLR, 2019.
[3] O. Bachem, M. Lucic, and S. Lattanzi. One-shot coresets: The case of k-clustering. In International Conference on Artificial Intelligence and Statistics, pages 784-792. PMLR, 2018.
[4] A. Backurs, P. Indyk, Onak, B. Schieber, A. Vakilian, and T. Wagner. Scalable fair clustering. In International Conference on Machine Learning, pages 405-413. PMLR, 2019.
10

---

[5] S. Barocas, M. Hardt, and A. Narayanan. Fairness and Machine Learning: Limitations and Opportunities. MIT Press, 2023.
[6] G. Basso. A hitchhiker's guide to wasserstein distances. Online manuscript available at htlps:/appi. semanticscholar org/CorpusID, 51801464, 2015.
[7] B. Becker and R. Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI:
[8] D. Bertsimas and J. N. Tsitsiklis. Introduction to linear optimization, volume 6. Athena scientific Belmont, MA, 1997.
[9] Z. Borsos, M. Mutny, and A. Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in Neural Information Processing Systems, 33:14879- 2020.
[10] Calmon, D. Wei, B. Vinzamuri, Natesan Ramamurthy, and K. R. Varshney, Optimized pre-processing for discrimination prevention. Advances in Neural Information Processing Systems, 30, 2017.
[11] T. Campbell and T. Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In International Conference on Machine Learning, pages 698-706. PMLR, 2018.
[12] R. Chhaya, A. Dasgupta, J. Choudhari, and S. Shit. On coresets for fair regression and individually fair clustering. In International Conference on Artificial Intelligence and Statistics, pages 9603-9623 9625. PMLR, 2022.
[13] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30, 2017.
[14] A. Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2):1533163, 2017.
[15] S. Claici, A. Genevay, and J. Solomon. Wasserstein measure coresets. arXiv preprint arXiv:1805.07412. 2018.
[16] C. Coleman, C. Yeh, S. Mussmann, B. Mirzasoleiman, P. Bailis, P. Liang, J. Leskovec, and M. Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference on Learning Representations, 2020.
[17] A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 2266 1956.
[18) C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 214-226, 2012.
[19] A. Fabris, S. Messina, G. Silvelo, and G. A. Susto. Algorithmic faimess datasets: The story so far. Data Mining and Knowledge Discovery, 2616))2074-2152, 2022.
[20] E. Fehrman, A. K. Muhammad, E. M. Mirkes. V. Egan, and A. N. Gorban. The five factor model of personality and evaluation of drug consumption risk. In Data Science: Innovative Developments in Data Analysis and Clustering, pages 231-242. Springer, 2017.
[21] D. Feldman. Core-sets: Updated survey. Sampling Techniques for Supervised or Unsupervised Tasks, pages 23 23-44, 2020.
[22] N. Fournier and A. Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707-738, 2015.
[23] S. Gaucher, N. Schreuder, and E. Chzhen. Fair learning with wasserstein barycenters for non- decomposable performance measures. In International Conference on Artificial Intelligence and Statistics, pages 2436-2459. PMLR, 2023.

---

[24] M. Ghadiri, S. Samadi, and S. Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountabilityy and Transparency, pages 438-448, 2021.
[25] Gordaliza, Del Barrio, G. Fabrice, and J.-M. Loubes. Obtaining fairness using optimal transport theory. In International conference on machine learning, pages 2357-2362 PMLR, 2019.
[26] S. Har- Mar-Peled and S. Mazumdar. On coresets for k-means and k-median clustering. In Pro- ceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291-300, 2004.
[27] M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
[28] H. Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOI:
[29] M. Hort, Chen, J. M. Zhang, M. Harman, and F. Sarro. Bias mitigation for machine learning classifiers: A comprehensive survey. ACM J. Responsib. Comput., nov 2023.
[30] L. Huang, S. Jiang, and N. Vishnoi. Coresets for clustering with fairness constraints. Advances in Neural Information Processing Systems, 32, 2019.
[31] H. Jiang, Y. T. Lee, Z. Song, and S. C.-w. Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, pages 944-95445 993,, 2020.
[32] R. Jiang, A. Pacchiano, T. Stepleton, H. Jiang, and S. Chiappa. Wasserstein fair classification. In Uncertainty in artificial intelligence, pages 862-872. PMLR, 2020.
[33] C. Jung, S. Kannan, and N. Lutz. Service in your neighborhood: Fairness in center location. Foundations of Responsible Computing (FORC), 2020.
[34] Kamiran and T. Calders. Data preprocessing techniques for classification without discrimina- tion. Knowledge and Information Systems, 33(1):1-33, 2012.
[35] L. Kantorovitch. On the translocation of masses. Management Science, 5(1):1-4, 1958.
[36] L. G. Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathe- matics and Mathematical Physics, 20(1):53-72, 1980.
[37] Y.-g. Kim, K. Lee, and M. C. Paik. Conditional wasserstein generator. IEEE Transactions Puttern Analysis and Machine Intelligence, 2022.
[38] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint 112.v:1412.6980, 2014.
[39] K. Lange. MM optimization algorithms. SIAM, 2016.
[40] S. Lei and D. Tao. A comprehensive survey of dataset distillation. JEEE Transactions on Pattern Analysis & Machine Intelligence, 46(01):17-32, jan 2024.
[41] Y. Liu and G. Pagès. Characterization of probability distribution convergence in Wasserstein distance by L LF--quanizzation error function. Bernoulli, 26(2):1171 1204, 2020.
[42] S. Lloyd. Least squares quantization in PCM. IEEE Transactions Information Theory, 28(2):129-137 1982.
[43] N. Loo, R. Hasani, A. Amini, and D. Rus. Efficient dataset distillation using random feature approximation. Advances in Neural Information Processing Systems, 15:13877-13891, 2022.
[44] S. Mahabadi and A. Vakilian. Individual fairness for k-clustering, In International Conference on Machine Learning, pages 6586-6596. PMLR, 2020.
[45] E. Maranzana. On the location of supply points to minimize transportation costs. IBM Systems Journal, 229): 1963.
12

---

[46] B. Mirzasoleiman, J. Bilmes, and J. Leskovec. Coresets for data- training of machine learning models. In International Conference on Machine Learning, pages 6950-6966 09600666600000 PMLR, 2020.
[47] B. Mirzasoleiman, J. Bilmes, and J. Leskovec. Coresets for data- efficient training of machine learning models. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference Machine Learning. volume 119 of Proceedings of Muchine Learning Research, pages 6950-6960. PMLR, 13-18 Jul 2020.
[48] A. Mishler and N. Dalmasso. Fair when trained, unfair when deployed: Observable fairness measures are unstable in performative prediction settings. arXiv preprint arXiv:2202.05049, 2022.
[49] A. Mishler, E. H. Kennedy, and A. Chouldechova. Fairness in risk assessment instruments: Post-processing to achieve counterfactual equalized odds. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 386-400, 2021.
[50] Mohassel, M. Rosulek, and N. Trieu. Practical privacy-preserving k-means clustering. Proceedings privacy enhancing technologies, 2020.
[51] M. Moshkovitz, S. Dasgupta, C. Rashtchian, and N. Frost. Explainable k-means and k-medians clustering. In H. D. IIII and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7055-7065. PMLR, 13-18 Jul 2020.
[52] B. Mussay, M. Osadchy, V. Braverman, Zhou, and D. Feldman. Data-independent neural pruning via coresets. In International Conference on Learning Representations, 2020.
[53] M. Negahbani and D. Chakrabarty. Better algorithms for individually fair k-clustering, Advances in Neural Information Processing Systems, 34:1 13340-13351, 2021.
[54] R. Ohib, N. Gillis, N. Dalmasso, S. Shah, K. Potluru, and Plis. Explicit group sparse projection with applications to deep learning and NMF. Transactions Machine Learning Research, arXiv: arXiv:1912.03896 2022.
[55] OpenAl. Chatgpt3.5. https://cht..peeni.coom 2022.
[56] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables. SIAM, 2000.
[57] G. Pagès. Introduction to vector quantization and its applications for numerics. ESAIM: proceedings and surveys, 48:29-79, 2015.
[58] H.-S. Park and C.-H. Jun. A simple and fast algorithm for k-medoids clustering. Expert Systems with Applications, 36()):3336-331,, 2009.
[59] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, et al. Scikit-learn: Machine learning python. Journal of Machine Learning Research, 12(0ct):2825-2830) 2011.
[60] G. Peyré, M. Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355-677, 2019.
[61] V. K. Potluru, D. Borrajo, A. Coletta, N. Dalmasso, Y. El-Laham, E. Fons, M. Ghassemi, S. Gopalakrishnan, V. Gosai, F. Kreačić, et al. Synthetic data applications in finance. arXiv preprint arXiv:2401.00081, 2023.
[62] Quinonero-Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset shift in machine learning. Mit Press, 2022.
[63] Y. P. Raykov, A. Boukouvalas, F. Baig, and M. A. Little. What to do when k-means clustering fails: a simple yet principled alternative algorithm. PloS one, 110)):0162259, 2016.
[64] M. Redmond. Communities and Crime. UCI Machine Learning Repository, 2009. DOI:
http:///bo.oo//00444422CC3xx
13

---

[65] S. Sagiroglu and D. Sinanc. Big data: A review. In 2013 International Conference on Collaboration Technologies and Systems (CTS), pages 42-47. IEEE, 2013.
[66] Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):94, 2015.
[67] S. Sharma, J. Henderson, and J. Ghosh. Feamoe: fair, explainable and adaptive mixture of experts. In Proceedings of the T'hirty-Second International Joint Conference on Artificial Intelligence, IJCA 23, 2023.
[68] S. Sharma, Y. Zhang. J. M. Rios Aliaga, D. Bouneffouf, V. Muthusamy, and K. R. Varshney, Data augmentation for discrimination prevention and bias disambiguation. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 358-364, 2020.
[69] M. Sloane, F.. Moss, and R. Chowdhury. silicon valley love triangle: Hiring algorithms, pseudo-science, and the quest for auditability. Patterns, 3(2), 2022.
[70] M. Sordello, N. Dalmasso, H. He, and W. Su. Robust learning rate selection for stochas- tie optimization via splitting diagnostic. Transactions on Machine Learning Research arXiv:1910.08597.222 2024.
[71] Thickstun. Kantorovich- duality. Online manuscript available hulps://courses. cs. washington.
pdf. 2019.
[72] A. Vakilian and M. Yalciner. Improved approximation algorithms for individually fair clustering. In International Conference on Artificial Intelligence and Statistics, pages 8758-888888888 8779. PMLR, 2022.
[73] A. Vattani. K-means requires exponentially many iterations even in the plane. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 324-332, 2009.
[74] C. Villani et al. Optimal transport: Old and new, volume 338. Springer, 2009.
[75] A. Virmaux and K. Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[76] B. Wang, W. Chen, H. Pei, C. Xie, M. Kang, C. Zhang, C. Xu, Z. Xiong, Dutta, R. Schaeffer, et al. Decodingtrust: A comprehensive assessment of trustworthiness in gpt models. Thirty- seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
[77] 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):
Mar. 2024.
[78] S. Xu and T. Strohmer. Fair data representation for machine learning at the pareto frontier. Journal of Machine Learning Research, 24(331):1-63, 2023.
[79] R. Yin, Y. Liu, W. Wang, and D. Meng. Randomized sketches for clustering: Fast and optimal kernel k-means. Advances in Neural Information Processing Systems, 35:6424-6436. 2022.
[80] R. Yu, Liu, and X. Wang. Dataset distillation: comprehensive review. JEEE Transactions on Pattern Analysis & Machine Intelligence, 46(01):150-11)) 170, jan 2024.
[81] A. Zhang, L. Xing, J. Zou, and J. C. Wu. Shifting machine learning for healthcare from develop- ment to deployment and from models to data. Nature Biomedical Engineering, 6(12):1330-1345, July 2022.
[82] B. Zhao, K. R. Mopuri, and H. Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2021.
14

---

Appendix
A Details Updating the Surrogate Function (line 4 of Algorithm 1
To update the surrogate function, we need to solve problem (8) which is a huge-scale linear program with (n) constraints and ((mn) nonnegative variables. In this work, we adapt FairWASP [77] for cases where o as opposed to the scenario where showing the main idea of the algorithm, we rephrase a useful lemma for doing linear minimization on Sm,m
which was tackled by [77]. Before
def. {P PRAm P1
La, P 0}.
Lemma A.1. For the function G(C) def. maxpeS... (C, P), it is a convex fimction of C in R For e E [n], let Ciz; denote largest component on the i-th row of C, then G(C) = Σ Cis:- Define the components of p as follows:
{
0
P3 =
(18)
ifj
and then P* E arg maxpES.... (C, P) and P* aG(C).
Proof. The proof of the above lemma is equivalent with that of Lemma of 777 in the when m F n, which can be extended directly.
With this lemma, now we show how to efficiently solve problem (8) via its dual problem. Although (8) is of large scale and computationally prohibitive, is equivalent to the following saddle point problem on the Lagrangian:
min max L(P.A) del. (C,P) 1
(19)
PES AER
where h is the number of rows of A, which is at most | significantly smaller than mn; for example, for classification tasks with only two protected variables, h is no larger than 8, independent of the number of samples features. Since L(.,.) :) is bilinear, the minimax theorem guarantees that (19) is equivalent to max minpes., L(P, A). This is further equal to the dual problem:
D) It should be mentioned that h is
G(())
def.
Ayina -
max XER
max PESnm
(20)
which a.J denotes the j-th row of A. Note that the problem 20 has much fewer decision variables than that of (19) and Lemma A.1 ensures the function G(-) convex and has easily accessible function values and subgradients. Therefore, directly applying a cutting plane method has low per-iteration complexity and solves the problem (20) in linear time. We include the details on the cutting plane method in Section A.] A. below. Finally, the primal optimal solution of 8 can be easily recovered from the dual optimal solution X via solving maxpes.... (E 1n - the assumption that this problem has unique minimizer, which almost always holds in practice for the computed X and also assumed by [77]. In this way, we have shown how the problem (8) can be efficiently solved by applying a cutting plane method on its dual problem.
P). under
A.1 Details of the Cutting Plane Method for Solving 20
The cutting plane method is designed for convex problems where separation oracle can be employed [3). For any X RTm. a separation oracle operates by generating vector 9 which satisfies x g X" for all X" in the set of optimal solutions. By repeatedly applying the separation oracle to cut down the potential possible feasible set, the cutting plane method progressively narrows down the feasible solution space until it reaches convergence. The specific steps of the cutting plane algorithm are detailed in Algorithm 2 with the key distinctions among different versions this method lying in how lines 3 and 4 are implemented.
15

---

Algorithm 2 General Cutting Plane Method for (20)
1: Choose a bounded set Eg that contains optimal solution
2: for from 0 to n do
3: Choose an interior point X of Ek;
4: Compute E IR" such that
g x X for any optimal solution X+;
5: Choose the next bounded set Ek+1 2 {) E E& : g 'T>²
6:
end for
separation oracle (line 4 in Algorithm 2 can directly use the vector of subgradients, which are efficiently accessible, shown (20) is a low-dimensional convex program with subgradient oracles, there exist many well- established algorithms that can be used. Suppose that the norm of an optimal X is bounded by R. to the best of our knowledge, the cutting plane method with the best theoretical complexity is given by [II, who proposed improved cutting plane method that only needs O(hh SO +h²) log log() flops. Here SO denotes the complexity of the separation oracle. Note that here h is at most 2
For the problem 20)
mentioned in section [4] Given that have
which is far smaller than n or m. Here we restate the Corollary of [77] below for the overall time and space complexity of applying the cutting plane method in the case m # n.
Lemma A.2 (Essentially Corollary 5 of (77)). With efficient computation and space management,
the cutting plane method solves the problem 20
within
Ô (mn + 1D log( R)
(21)
flops and ((n(D|)>)) space. Here we use Ō(-) to hide m. n, [D), and ( in the logarithm function.
The above result is essentially Corollary of 777 by slightly extending the proof to the general case m # n. Finally, in terms of the implementation, we follow [77] and use the analytic center cutting plane method.
B Theoretical Proofs
This section includes the theoretical proofs for Section 2 and Section 5 We first show the Wasserstein
distance upper bounds downstream disparity for MLP networks (Proposition 1.1p. We then show (i)
the optimization problem be reduced to optimizing over the X rather than Z (Lemma 3.1 (ii)
the surrogate function is convex and a valid upper bound of the optimization objective (Lemma 5.2
(iii) our proposed algorithm converges to a first-order stationary point in X (Theorem 5.3). and (iv) our proposed algorithm terminates generalization bound for FWC performance in terms of Wasserstein distance and demographic parity
finite amount of iterations (Theorem 5.4) We also prove the
to unseen datasets coming from the same (unknown) distribution the original dataset was sampled from. Finally, we include Section to note how the downstream learning using FWC can be broken down into two terms, which highlights the challenges in analyzing its theoretical properties.
Lemma B.I. Let Z (X, (X,)) = (X Y) be two pairs of random variables with joint distributions pz and P2 and marginal distributions px, py and P and py respectively. Let TT Z2 2) indicate the set of all joint probability distributions over the product space Z x Z that admit marginal and conditional distributions over X and y. For any non-negative cost operator c:
Wo(px.P&) S Wolp.P2).
Proof. Proof of Lemma B.1 Let Xx X) indicate the set of all marginal (joint) probability distributions over the product space X' x X. For any II(Z 2) and the corresponding ge x () we have that:
16

---

J 2xz
d2, (2,
2(a,2))d(2,
(22)
2x
J xxx (lz, 2)
min (.,))
(I, = -c(px.Px)
As this is valid for any π E 11(2, 2), select:
/ c(z, (2)
π = arg min
(2)) 2x2
Then the left-hand-side of 22 equal to We(P2.P2. hence proving that We(pz.P2) 2 Wc(px.Px).
Proof. Proof of Proposition proof of the upper bound follows from the first part of the proof of the -nbbiniechhR duality [66]. this work we follow the proof by [6 711, which consider the Lagrangian form of the I-Wasserstein distance and express in the following form:
P(
sup barf(>>aa
E Ba.. Solr, d) - B(e,d) B, d)
where fig: X' - are bounded, measurable functional Lagrangian multipliers. Let I.so be the Lipschitz constant of the MI.P fe. and define the following function:
fo(x, d)
h(2,d) d)
Lio
By definition, A(x,, d) is I-Lipschitz. Again following 6 we know that for 1-Lipschitz functions the following holds:
E b, -B B(I.d))p L.o BL..dppp...,, - B(rd)) h(x, d))
= L50
(XXX))(XXX))
h(21 d1, x2, 22, (PIx.)))((..)))
M1 d2) dm (P.X.D)P((,D))
< Lso (XXD)X(XXX)
I L
[1( (x2, de) dn ((x,,)))((...)))
(XXD)x(XXX)
< (...Wi(PEx.D):PP....)) WPzz.22)
where the last inequality is due Lemma B.1
The result can be obtained by using the upper bound in (55, Section 6. which shows that I.g < L for K-layer MI.ss with ReLu activations.
Proof of Lemma 3.7 Once we generate m mD| Y data points, the feasible set of the latter Wasserstein coresct contains the feasible set of the former Wasserstein coreset.
17

---

Proof of Lemma 5.2 The convexity follows directly from the convexity of C(X), as the P 2 0 in (T)..
Before proving it is an upper bound, we show some important properties of F(C) as a function of C. Firstly, F(C) is concave on C' because of the concavity of the minimum LP's optimal objective on the objective vector. Secondly, since the feasible set of problem (8) is bounded, the optimal solution F(C" continuous with respect C. Thirdly, due the sensitivity analysis of LP ( a supergradient of F(C)) at point C' is the corresponding optimal solution P*, Here the definition of supergradients for concave functions is analogous the definition of subgradients for convex functions.
Now prove g(X; X is an upper bound of F(C(X)). Because PK is supergradient of F(C) when = -((**)
F(C)+ (P)) -) 2 F(C(())
in which the left-hand side is equal to 9(X; because F(C) (P о) and g(L; = (C(X), PŁ). Therefore, the surrogate function is an upper bound of the objective function F(C(X)). i... (X;; x 2 F(C(X)). Moreover, due to the definition in (10) g gX; X*) F(C(X)) when X =
Proof of Theorem 5.3 The monotonically decreasing part of the claim follows by:
F(C(X*++) ()) 9( k+1, x*) arg min xxx; S g(x*; F(C({*))
(23)
Here the first inequality is due to the fact that g g(;; X*) 2 F()( for any X. The final equality because g( x*) = F(C(X)) when X = Xt. Once g 8x* X²) = g(8++1; x+) and thus X E arg min xm ,(X; then X is global minimizer of the convex upper bound &+) for F(C(-)) and the upper bound ;( {*) attains the same function value with F(C(X*)). Therefore, if the surrogate function is smooth at 8*, which could be achieved if C(XF) is smooth at X*, then X is a first-order stationary point of
Proof of Theorem 5.4 Because (IT) has a unique minimizer, the second inequality in 23 holds
strictly when X x + X or equivalently (X*++1 * g((*;; X*). Once X =x then the algorithm terminates. Note that there are only finite possible optimal basic feasible solution ps that could be generated by FairWASP, as shown in Lemma A. However, before the majority minimization converges, (23 holds strictly and the corresponding Pt keeps changing. Therefore, after finite iterations, there must be a P equal to a previous Pj for j < I. When that happens,
because the surrogate functions the same and thus have the same minimizer, X x++1, and the inequalities (23 then hold at equality when i j. + 1, ,,..., f. This implies that g 983+1,, X)) g(X,, X)), so the algorithm terminates within finite iterations.
Proof of Proposition 5.5 For determining the convergence in Wasserstein distance between 22 and qz. we first use the triangle inequality:
Welp2. qz) < Wc(p2.Pz) Pz) + Wclpz, qz) = À + Wc(pz.
Note that the first term is deterministic, it the result of the optimization problem 4 For the second term, we use the result from 22 which implies that with probability a and for the
1- W-Wasserstein distance:
((W.(Pz 92) > {) S exp (-one
and so by setting the right-hand side equal to or equivalently, setting
clog(1/a)
E
n
obtain the first result.
For determining the convergence of the disparity between pz and P2(1, d) and qy we again first use the triangle inequality from the definition of the disparity J:
18

---

(P2(ydd) 9r (v)
sup dEy.dED
((22()ld),9r(1))
sup vEV,dED
or (r( [p2 (M d) - -pr(U)) (w)
+ Ipy (1) ox (v))
sup ,EYidED
qr (v())
gr
(22(udd) py (v) gr (v)
Ipy (v) qr (v)
sup dEY,dED
sup vEy
qr (v)
As the minimum of the marginal distribution of qr (y) is bounded away from zero mingey qz(y) =
p > and since by the optimization problem (4) have J(pz (yr S for all y E Vdd
D:
PD(v/d) pr pr(v) (r
(py - qr (v)
sup wEy,de
(12)))l),000000 (v)) z
sup dED
+ sup NEY
pv(
(r(
Ip (v) or(")l
sup dED
JPp (vld) PY (v))
+ sup
(y)
p
DEy
Ipy (v) uv(
sup P vEy
(v)
Note that the first term deterministic, while the second one not, as we need to account for the uncertainty of observing n i.i.d. samples {Z For the second part, we use the Dvoret- w (DKW, [17 inequality:
py (v) (v)
P
sup yey
>
S sup (1) qr (v) EP) yEy
qr (y)
< 2 2xp(( 22p²
By setting the right-hand side equal to a, or equivalently, setting
log 2) E < 2np²
we obtain the second result.
Finally, we note that the assumption the marginal distribution of gy is bounded away from zero, i.e., p >> 0, is reasonable as the outcome a discrete (usually binary) random variable, This assumption would be much more restricting in case was a continuous random variable (e.g., in regression settings).
B.1 Downstream Learning using FWC
Overall, the hardness of deriving bounds for the synthetic representatives provided by FWC can be analyzed using the following breakdown, which is adapted from (78). Consider the given dataset
Z = ((x, Y,, Di the synthetic representatives obtained using FWC å = {(X,, Y,, b and h E H (2 x y x D), the set of measurable square-integrn inttre-nttegrable function in 7,2, If we consider the downstream learning process using FWC samples over the 1,² space:
inf Erjx,D ||X n(X n(X,
then the above can be expanded in two terms, due to the property the conditional expectation being an orthogonal operator in H:
19

---

inf EYIX,D |IX - M(X, 1)13 NEW
= =Evxx, - 1113 + inf By E KEH
|EX,D DJ 1(x D)
(24)
FWC Approximation Ertor
Learning with Somples
The first term corresponds to the loss of information in approximating Y with Y via the FWC approach, and is actually independent of any downstream learning. This condition requires for the first moment (which for the binary Y case is equivalent to the joint distribution) of Y and Ý to be close as possible. Using FWC this is enforced by minimizing the Wasserstein distance. Indeed, if in definition (T) one restricts couplings that admit marginal and conditional distributions, then the conditional distributions of Y || D and Y|X, D are upper bounded in Wasserstein sense by the Wasserstein distance between the joint distribution of pz and P2 (37].
The second terms refers the training process using FWC samples Firstly, by using the equivalence in 788 the second term is equivalent to inf Byjx.D | f(X, DI3 which correspond the
finding the best L function approximate the distribution of Y. This fact implies that using FWC samples is indeed mathematically equivalent to the learning task for the original Y. However, this second term also highlights the hardness of developing learning bounds, as the FWC synthetic representatives 2 = {(x,, Y, p are not i.i.d., and hence standard bounds are not applicable.
C Experiment Details
C.1 Runtime Analysis Synthetic Dataset
As mentioned in Section 7 we generate a synthetic dataset in which one feature is strongly correlated with the protected attribute D to induce a backdoor dependency on the outcome. We consider a binary protected attribute, D e {0, 1}. which could indicate e.g., gender or race. The synthetic dataset contains two features, a feature X1 correlated with the protected attribute and a feature X2 uncorrelated with the protected attribute. For D 0, X, is uniformly distributed in [0, 10), while for D= X, = O. Instead, X₂ is 5 times a random variable from a normal distribution (o, 1). Finally, the outcome Y is binary, so Y {0. 1): Y when Y; mz + G and Y; when Y, S my + 4, where m, is the mean of ((X,); + (X2) and the noise G; comes from a normal distribution (0, 1).
This experiment visualizes the speed of our method with respect to different numbers of overall samples n, number of samples in the compressed dataset m, and the dimensionality of features p. We evaluated the performance of the algorithm under the synthetic data with different configurations of n, p, and m. In this experiment, we set compute the fair Wasserstein coreset under the ( lo-orrm distance and we use k-means
42 to initialize the starting coreset X We terminate the algorithm when X+= k The time per iteration and total iterations for varying n. p, and are shown in the Figures | (top left) [ We see that increasing the sample size of the original dataset n increases the runtime and number of iterations, while increasing the number of coresets m or dimensionality of the features reduces the overall numbers of iterations but increases each iteration's 's runtime. Additionally, for the setting of Figure D (top left), in which we vary the dataset size n, Table provides FWC average runtimes from n 500 to 1, 000, 000. We compare FWC runtimes with 500 (our lowest dataset size in the experiment) extrapolated (i) linearly, with factor of 1, (ii) linearly, with factor of 10 and (iii) quadratically. We can see that the complexity is near linear and less than quadratic with respect to the dataset size n, although the rate indeed seem to increase for at 500, 000 and above, which can be attributed to the increasing number of iterations required to achieve convergence. This akin to the phenomenon well-known for k-means, for which in larger datasets k-means might take an exponentially large number of iterations to terminate [73].
the runtime
20

---

In practice, fixed number of overall iterations is set to avoid this case: sklearn sets it to 300 feiss 23 Matlab to 100
FWC Runtime Analysis (p=25, n=5000)
FWC Runtime Analysis (m=400, n=5000)
0.6-
503
119.-
120
75-
1012
Conese Sample Size
Dimersion Featurts X
Figure Runtime analysis of FWC when varying the size of the coreset m (left) and the dimensionality of the features (right). We report averages and one standard deviation computed over 10 runs.
Table 2: Average runtimes for FWC in the same settings as Figures (top left), varying the dataset size while fixing
250 and 25, compared with the runtimes for the smallest dataset extrapolated (i) linearly, with a factor of 1, (ii) linearly, with a factor of 10 and (iii) quadratically. FWC enjoys a near linear time complexity, increasing with the largest dataset sizes; this phenomenon is shared with other clustering algorithm such as k- k-means (see text).
(seconds)
1:04000
1.Bex01
8.9e10]
0,12
10,500
1
0.95
9ow02
0.09
0.08
24,500
8.7e401
4.40001
1.99
4.4ex02
0.20
2.1ev03
0.04
48,500
3.0e
Mdle01
3.46
8.6e=02
0,35
5.4e-u
0,04
75,000
704400
1:30400
5.28
0.52
2.0e444
0.08
100,000
1.0e008
1.84000
5.79
1.Rev03
0.58
3.6404
0,08
4.5c403
18.34
8.er033
0.22
21.64
1,000,000
4.94004
1.c408
27.58
1.8ex04
C.2 Real Datasets
We consider the following four real datasets widely used in the fairness literature 19
the Adult dataset 77, which reports demographic data from the 1994 US demographic survey about ~ 49, 000 individuals. We use all the available features for classification apart from the "fnlwgt" feature, including gender the protected attribute and whether the individual salary is more than USD50, 000;
the Drug dataser 20), which contains drug usage history for 1, 885 individuals. Features X include the individual age, country of origin, education and scores various psychological test. We use the individual gender as the protected variable D. The response Y is based on whether the individual has reported have ever used the drug "cannabis" or not;
the Communities and Crime datasel [64 was put together towards the creation of a software tool for the US police department. The dataset contains economic factors for 2, 000 communities in the US, along with the proportion of violent crimes in each community. As protected attribute D, we include whether the percentage of the black population in the community is above the overall median. For the response Y, whether the violent crimes percentage level is above the mean across all communities the dataset;
binary indicator of
cluster .luster..Meane html html
KMeans
21

---

the German Credit dataset (28] reports set of 1, 000 algorithmic credit decisions from a regional bank in Germany. We use all the available features, including gender as protected attribute D and whether the credit was approved as response Y.
As perfect demographic parity achieves a value of O for the discrepancy J, so we have included demographic "dis" -parity to indicate any deviation from demographic parity. Across all experiments we compute demographic parity as the following absolute difference:
DD (b D) 1ID = - 11 0)1
(25)
for a given classifier h and a protected attribute D with two levels; the larger this difference, the larger the disparity. We also include the implementation and ayper--arameters of the methods used in the fairness-utillyy tradeoffs throughout the experiments in this paper:
For FWC we set the faimess violation hyper-parametee parameter of problem in Equation 5 to be c = [0.01, 0.05, 0.1], hence obtaining three separate FWC models, FWC (0.01), FWC (0.05) and FWC (0.1);
For Fairlet 4) we use the implementation available at the following GitHub repository: https://github.
For IndFair [12] and K-Median Coresets 3] we use the implementation avail-
able at the following GitHub repository: hattps///giituub.cmm///aseessses
For k-mmans 42 and k-medoids
45 58
use the inplementations available in the Python
package Scikit-Learn
59
All computations are run on an Ubuntu machine with 32GB of RAM and 2.50GHz Intel()) (con(R) Platinum 8259CL CPU. For all datasets, randomly split 75% of the data into training/test set, and change the split during each separate run; the training data are further separated into training and validation with 90/10 10 to compute early stopping criteria during training. The downstream classifier used is a one-layer deep multi-layer perceptron (MLP) with 20 hidden layers, ReLu activation function in the hidden layer and softmax activation function in the final layer. Unless stated otherwise, FWC uses the L to compute the distance from the original datasets in the optimization problem. For the downstream classifier, we use Adam optimizer (38 with a learning rate set to 10 33 batch size of 32, maximum number of epochs set to 500 with early stopping evaluated on the separate validation set with patience of 10 epochs and both the features X and the protected attribute D are used for training the classifier. Note that due to the size of the Adult dataset, Fairlet coresets 4 could not be run due to the RAM memory required exceeding the machine capacity (32GB). Finally, all uncertainties are reported at lo (one standard deviation) in both figures and tables. Uncertainties are computed over a set of 10 runs where the random seed for the algorithm initialization and train/test split was changed, but consistent across all methods (i.e., all methods in the first run were presented the same train/test split across each datasets).
Table 3: Wasserstein distance of the weighted coresets with respect to the original dataset, with averages and standard deviations obtained over 10 runs. In bold, coresets with the closest distance to the original dataset (i.e.. smallest Wasserstein distance) in each coreset size and dataset combination.
Weereriii Bistanre L.l
Cormett Sow i
335%
15%
2%
3%
D0%
25%
55%
10%
20%
5%
53%
20%:
326
7826)Wab)
157 4:35
3000 102
235:2:03
1.22
6.1.
1.6
172 0096
3.55 1.330
331 1354
Fadlo Meao)
1010 2114
777
33002.344
210 1442
2.102/044
200 033
4.3-1.044
4.00 100:00 D48
4:11
Ina: Far Cos
11.46 1.19
0.4
3/22 0.46
0.33 0.12
233 111
250:2/255
200 000
434-21033
331 520
4.7.2021 0.21
19.0 2 1934
14.90
1430
7.6.1.42
0.422033
3:00 1.002:011
0.80
2,0 1426
155 2:33
1.25 0.24
0.45-1.35
2030
4.5
X-Moloab 233
133
239:2042
425 2.08
0.16
315 1004
31122:111
153 0096
4.34-::00
4.55 0.26
335 022
Closeness to the original dataset and clustering performance Tables 3 and include the
numerical values (means and standard deviations computed over 10 runs) for all methods in
22

---

Table 4: Clustering cost of the coresets with respect to the original dataset, with averages and standard deviations obtained over 10 runs. bold, coresets with the smallest clustering cost (i.e., smallest sum of square distances of original dataset samples from the closest generated coreset sample) in each coreset size and dataset combination.
Chotering
Mathood
UPP)
Drag (-36))
5%
PA0 bdll
6.73
2.2
1007 0.39
1.77
261 0.99
431
0.90
444.5 0:11
170
6.54 0.41
6:330
7402 0.31
PMC
4..9
2.57
236 8.00
441 1.50
1,30 0.5
1,44
4.3.6:036
946
0.3
6.3
635
2139 1227
2:3
9.2)
243:2:0.3
410 1.25
122
0.44
4.36::0.15
6.3.3.0344
6.36
0.26
0.34::0.31
5
176.1.000
0.h6 B.11
191
0.31
4.761:0:16
190 035
1/08 11:00
1:151.0000
5.76 861
Farler (K MeMiid
1.3
540 108
500
0.90
6.37
0:35
6:0
5:90=035
8.5
0.41
7:344-044
7.09
lal. Fi: Ca
4.5 0:33
0.70 0094
1.50
0.77
0.74
=3 0.10
5:242:0.22
3:6 0.48
1.22
1.29
0:35
7.52
6:30
1:35
Lithmn Suttumpiing
1515
1:16
195.1 1667
3.38 1.44
1.54 2.31
4.8.1:0.6
1.461.0:3
5307 163)
1:34 0.33
406.1.0.5
710 0.50
K-Mrass
K-Makisb
83.83 13.96
75.10 7.22
9.15
4:3
4.0
0.5:
0:5
0,20
0.15
5 0.30
terms of Wasserstein distance from the original dataset and clustering cost, for the three core- set sizes m 15%, 10%, 20%] (apart from the Adult dataset, in which coreset sizes are set to m = 00.5% 1%, 2%] due to the large size of the original dataset). Clustering cost is computed as the sum of the squared distance of each point in the original dataset from the closest coreset representative, while the Wasserstein distance is computed solving the optimal transport between the empirical distribution of the original dataset and the one of the coresets, using the L norm as cost function. FWC consistently provides the closest distributional distance to the original dataset in Wasserstein distance, with the only exception of the Credit dataset, in which the large number of discrete features makes the optimization non-smooth in feature space, resulting in a potentially imprecise solution of Equation ( In addition, FWC, while not naturally minimizing clustering costs, seems to achieve competitive clustering costs in smaller datasets while not performing as well on larger datasets such as Adult. Finally, we note that the Wasserstein distance might not always decrease with higher coreset size, which is due to the parity violation constraint e. In other words, the coreset samples not only have to be close to the original dataset distribution but also respect the hard fairness constraint; the lower the e, the tighter this constraint is (Equation (4)). Indeed, when is the largest (e = 0.1), coresets of size 20% (or 2% for the Adult dataset, i.e., the largest) consistently has smaller Wasserstein distance to the original dataset than coresets of size 5% (0.5% for the Adult dataset, i.e., the smallest).
Fairness-utility tradeoff when using coresets for training downstream models Figure expands the results provided in Figure [ and shows all the fairness-utiltyy tradeoffs for all methods across the four datasets, both with (right column) and without (left column) using pre-processing fairness approach [34) (excluding FWC, to which no fairness modification is applied after coresets have been generated). For each method, the coreset size that achieves the best fairness-utility tradcoff' is shown (which is not necessarily the coreset with the largest size). FWC achieves a competitive hiiness-utiligg tradeoff with respect to other competing methods, when using the generated coresets to train a downstream MLP classifier model. FWC consistently reduces disparity in the downstream classification with respect other approaches, and often maintains the same utility (indicated by the AUC). For completeness, Figure also reports standard deviations for the fairness-utility tradeoff; standard deviations for the Adult and Credit datasets are large due to the MIP classifier becoming trivial (i.c.. always returning Os or 1s), which yields very low performance but has no demographic disparity (by definition, as all test samples are assigned the same outcome). Tables and 6 report the numbers shown in Figures 6 and 7 including one number to quantify the fairness-utiliy tradeoff, computed as the Euclidean distance in the Figure from the (0, 1) point (which would be a fair classifier with perfect performance). In other words, for the k-th method achieving disparity of de with uncertainty Adg and performance ag with uncertainty Aak, the tradeoff ta and associated uncertainty At, are quantified as:
de V(de tsc
(Ak - 1 +
4. V( (1
+ dz
Ale
V
Ada
Daz
(26)
t+
Finally, the average reduction in disparity was computed from Tables 5 and (6] by averaging the improvement obtained by FWC samples against all methods and across datasets. FWC result in an
23

---

average reduction in disparity of 53% and 18% for the scenario without and with fairesss pre- processing, respectively.
Table 5: Demographic disparity (Equation 25 AUC and faimiss-utilltyy tradeoff (Equation (26 of downstream MLP classifier trained using all fair coresets/clustering methods across the four real datasets. The best method across the different coresct sizes is shown, and the best performing method for each metric in each dataset is bolded. Averages and standard deviations taken over 10 runs. For the Credit dataset, K-means reaches low disparities due to the classifier being trivial, i.e.,
returning the same prediction regardless of input features.
Metbol
Dasur!
Dalan!
Dasur!
Doe Datoet
DP
DraladE 11)
DD:(1
Tralodi (1)
DD:L1
ATC
Tzaled(
DD
(TC
Tialceff (1)
FMC tr: (MB1)
4JC &
D47 41.30
1033 0.00
10:0 2: DJA
0.7 1.:1
0.5 s DA1
1133 8M8
0333 1052
16:2 EJM
I485 2 0,04
0.39 0:12
1:21 = 4.0
Pvbion 0.1)
0066-00
6.70 0.06
0:30 6-008
0.00 4-0.0
0/66 0.12
0.36 + 0.2
01164-0000 0/03
0:85 06
0.31 8/0
0.08 0:08
0:50--0.00 0.001
0:21 + 9.00
Frilitt (S-Maan)
0.01
0.3
3.00 =
0.39
0.06:::000
0.50
0.25 0.00
Parlo (K Medhidad
0:04:2:0000
0.00 0.00
0,1 009
0.14::0.10
0,30
0.33 0.14
0.:0::0000
0.76 0.05
0126 0.00
1sd. Fur: Cor
11.8 L/015
0:015
0/65
4.5 1.1
0.11
0.04
1.:0:1..000
0.:1
11.6 1:16
K MiM
012.4.008
0:09
9:009
10.0 9:007
0/06
01.5 0:05
8:91
0:16--009
0:164:0::0
0:06
0.74 0.70:0006
Unifor Schvanpiiis
0.12 0.6
0.71 0.00
0:31 0:.00
4:
0 :0.1
0.31 6:11
0.45 + 0.08
0.89 0002
0.46:
0.14::0.11
0.75 0.03
0.26--:0.0
K-Masse
0.10
0.00
044
0.00
K-Madoud
016:1.00 0UH
8.1 4.13
0.30
1.05 1:045
0.00 11507
(.40 8 1077
11:6 0.10
0300 1654
16:001: DJM
10:2:1:011
(3300 0112
(.23 4.000
Table 6: Demographic disparity (Equation (25 AUC and faimees--tiility tradeoff (Equation (26) of downstream MLP classifier trained using all fair coresets/clustering methods across the four real datasets. All methods apart from FWC have been corrected for faimess using preprocessing
fairness technique by [34. The best method across the 3 different coreset sizes is shown, and the best
performing method for each metric in each dataset is bolded. Averages and standard deviations taken
over 10 runs.
Method
Disertt A)
Daloot
Drag Dotrutt
DD
TeadodE
AUC
DD
(UC
Trakeff
DD
AUC
Tindooff (1)
PME 0.01)
B42 9:00
0.67 s 0:10
0.33 010
6/03 : 0.06
0.67 #
033 K1l
0
083 8:000
0.2 5:00
6.5 :: 9/M
0.79 0:00
6:21 : 0.6
PMCs, 0.05)
0.00
=
0.26 =0
0.00
= 0.11
0.6
0:15 004
0.22 0000
0.06
FVD ic
2:03
0.00 0.58
0.30
CAB 0.00
9122
0134 0.12
0.16 DG3
2:001
0.22 000
0.08 001
9.00
0.21 0.82
Fi Menaa)
0/02 0.00
0.50 = 068
0.40 008
0.23 4 005
0.87 0.00
0.36 0014
0.12 5:00
0:02 0.00
8.21 0:04
Parlc
0.00
0.04
Ind. Fai Use.
D45 1:035
0 4106
0.05 18:h
CJA-1100 110
0.53 D.0
1137 D0M
017.4000 0004
1695 1:042
1623.1001
IC06 0:00
0090 0.00
8:21 1.04
6.31
0::0
Unffer Sabsungling
068 0.10
0,32=
6.0 0.05
0.68 = 0.13
0,33+ 8:12
0.29 6 0:55
0.8
0.31 0:05
0:6
0.79 0 0.05
0.2 0:05
K-More
1.0m
0m 0.00
0.54 0889
(19
0.55 D01
025 D01
[LSK 8.11
0.26 1:00
0:09 1.0
0.00
8.21 (182
K-Molisis
065
0.
0130=011
0.00
068
0:39
085 0:0
0.28
0.1
041 0.00
9.22 0.03
Fairness-utility tradeoff when using coresets for data augmentation We also evaluate the per- formance of FWC in reducing the downstream demographic disparity when doing data augmentation, i..., adding the synthetic representatives to the training data when training downstream model. We use the data augmentation scheme adopted by [68] Section 2.1]. which first uses k-means on the original dataset and then sorts the synthetic representatives based on the distance of each synthetic representative to the nearest k-mean centroid with the same combination of protected attribute and outcome D and Y. We generate a set of synthetic datasets of size equal to 50% of the original dataset and look at the fairness-utille utility of a downstream model trained augmented with such synthetic representative in increments of 5% (20% and 2.5% respectively for the Adult dataset, given the large dataset size). Figures 3 and 4 show the fairness-utility tradeoff of the downstream MLP classifier when doing data augmentation, selecting the best model across various degrees of data augmentation, along with the performance of the baseline MIP classifier with no data augmentation (averages and standard deviations over 10 runs). Table 7 shows the numerical values for the downstream fairness-utie utiliiy tradcoff, including the tradeoff value computed as in Equation (26). In all datasets the data augmentation with FWC seems either increase the performance or reduce the demographic disparity. with the only exception being the Drug dataset. Upon further investigation, Figure 5 shows this effect does not appear if the protected attribute D (gender) not included in the features used to train the downstream MLP classifier. This phenomenon indicates the protected attribute provides a strong predictive effect on the outcome (whether the individual has tried cannabis or not), which might potentially be mediated by unmeasured confounders, i.e., other features regarding the recorded individuals that are not available in the Drug dataset. This would require either in-training or post-processing fairness approaches to be alleviated; see [29] for comprehensive review on different
24

---

potential approaches, Finally, as in Figure 7 the standard deviations for Adult and Credit dataset are large due the downstream model becoming trivial.
Data Augmentation Performance- Tradeoff, FWC
Credit
0.25
6423
0.042
2
8.05
0.21
0.33-
6410
0.377
Demographic Disparity
Demographi Disparity
Demographic Disparity
Demographic Disperity
Drug
0.94
3.935
0.55
0.00
0.75
0.85
5.75
3.22
8.13
0412
5.00
0.82
3.02
6ã2
0.58
Demographic Disparity
Demographic Disparity
Demagraphic Dispariy
Demographic Disparity
Bisciin Aug.)
PVC le: 0.033
FWC 0.05)
PWC Ia 0.33
Uniform Subsampting
Figure 3: Fairness-utility tradeoff of downstream MLP classifier trained using the original training set augmented with coresets representatives, following the augmentation strategy from [68]. Each point shows the best model in terms of fairness- utility tradeoff over various degrees of data augmentation, addition to the baseline model with no augmentation. Means and standard deviations taken over 10 runs, with the computed Pareto frontier indicated by the dashed red line.
Data Augmentation Cestormancc-FFiinees Tradeoff, All Methods
Adult
Crime
Credit
Drug
0.70
5,8400
0.69
0922
0.74
6.72
6.850
0923
0.36
5.8000
0518
6.65
6,6250
0.220
0122
6:30 9.155 0,540
0.4 0:445 6.44 0 Demographic Disparity
0.00
0.2e
0.30
0.12
0.38
0.00
522
6.2
Demagraphic Disparity
Demographic Disparity
Demographic Disparity
Adult
Crime
Credit
Drug
0.942
5.50
0.05
0.902
0.05
3.905
7.75
0.05
082
0.81
2.15
615 032 E14 636 Demographic Disparity
0.33
0.60
3.25
646
0.20
6.24
3,00
3.13
6.6
3.17 618 6ls 330 031
Demographic Deparity
Demographic Disparity
Demographic Disparity
Baseline (Ko Aug.
PWC In: 3.05)
Fuiree (K-eans)
Ind. Cor.
KAMedsid
PAC ta 0.501
FWC le: 0.1)
Fairet (K McMooidds
Uniform Subsamping
Figure 4: Fairness-utility tradeoff of downstream MLP classifier trained using the original training set augmented with coresets representatives, following the augmentation strategy from (68), including all methods mentioned in Section 7 Each point shows the best model in terms of fairness-utility tradeoff various degrees of data augmentation, in addition the baseline model with augmentation. Averages and standard deviations computed over 10 runs, with the top panel showing just means and the bottom panel combining both means and standard deviations, with the computed Pareto frontier indicated by the dashed red line.
25

---

Data Augmentation Performance- Tradeoff, Drug Dataset, FWC
D not used in prediction
D available during prediction
0.06
0.85
0.85
AUC
0.84
0.83
0.83
0.82
0.82
0.01
0.14
0.15
0.16
0.17
0.18
0.19
0.36
0.17
0.18
0.19
0.20
0.21
0.22
Demographic Disparity
Demographic Disparity
Baseline (No Aug.)
FWC (e: 0.01)
FWC (e: 0.05)
FWC 0.1)
Uniform Subsampling
Data augmentation faimess- tradeoff of downstream MLP classifier for the Drug dataset when the protected attribute D (gender) is either not included (left) or included (right) as feature in the learning process. As in Figure 3 the best model across various data augmentation degrees is reported, with averages and standard deviations obtained over 10 runs. FWC manages to successfully reduce the demographic disparity when gender is not used feature, but fail to do so when gender is used, indicating that gender provides strong predictive power for the outcome in question, which would require enforcing fairness either during model training or by post-processing the outputs.
Figure 5:
Table 7: Demographic disparity (Equation 25) AUC and fairness-utility tradeoff (Equation (26) of downstream MLP classifier trained via data augmentation with all fair coresets/clustering methods, across the four real datasets. The best methods across various degrees of data augmentation is shown. The best performing methods for every column is bolded, with averages and standard deviations taken over 10 runs.
Metbod
DO (2)
AUC
[D:(3
AUC
Trakedf GU)
DD
AUC (?)
Tisdoti 12)
DD.
ATC
Inaleef (3)
Bewetin Ohe Asga
000 11.5
01W
GMM 1133
02110111
00.0
(L924
0/46 1004
6.1 8J13
0,54 0.82
0.24
900
0.06
835
0.97
013
0.84
1199 1-00
0.41 668
0 9:00
0.84 6/11
0135 1:00
PRC tu 3.05)
0.142:0:
0.70 8,09
0.33 0.08
010 005
0.76 0.08
0.355:000
0.44 = 0.00
0.999 0:000
0.44 0483
021 002
0.54 0.81
0.26
0.70
Pasten Moaaoo
018 1005
0.77 17722100 11:00
1136::0000
1:44 0 0.00
11900-1-0140
0A68 003
0.19 304
0355 1001
1126 4216-10010
Tal Rii Car
0:6. 3000
0.34 0.06
0.0 004
6.78 0.14
0:23+:0.00
0.4 0.64
0.19:::0.00
0.41 6.64
8.18 8/02
0.84 6.91
0.24 9.00
Unifor Suloaspiing
0.00
0.07
0.34::00
0.19::000
0.25 0.02
K-Makes
038
300
0.06
918
0.06 1.90
0125
(L922 0:MM
0.45
0.19:::02
0.85 0.0
0125 0.10
Using FWC to correct biases in LLMs To query GPT models, test data with 200 samples is provided with base parity of 0.5 (similar to (6)) and additionally, examples are provided in the case of the few shot settings. Data is fed in as text. One of the tabular data, for example, is: "A person in 1996 has the following attributes: Age: 21.0, workelass: Private, education: Some-college, highest education level: 10.0, marital status: Never-married, occupation: Other-service, relationship: Own-child, race: White, sex: Female, capital gain: 0.0, capital loss: 0.0, hours per week: 25.0, native country: United-States".
We use the following prompts:
Zero shot: "Using the provided data, will this person from 1996 be hired at greater than 50,000 USD per year? You must only respond with the word 'yes' or 'no'. Here are examples with the correct answer."
Few shot: "Given the provided data, will this person from 1996 be hired at greater than 50,000 USD per year? You must only respond with the word 'yes' 'no". Here are examples with the correct income level for a person in 1996. Make sure you use the examples as reference", where is the number of demographically balanced samples.
Few shot (FWC): "Given the provided data, will this from 1996 be hired at greater than 50,000 USD per year? You must only respond with the word 'yes' or 'no". Here are n examples with the correct income level for person in 1996, along with weights in the
26

---

column weight. Weights are between 0 (minimumi) and 1 (maximum). The more the weight, the more important the example is. Make sure you use the examples as a reference." "
In the few shot settings, 16 examples are provided both cases due to the LLM token limitation; passing fewer examples yields similar results to the ones in Table [ For FWC, we run a separate coreset generation run (differently from other experiments in Section 7 where we selected m = 16 and ensured that the positive class (Y = 1) has equal number of male and female samples. We also note that while the results from GPT-4 for the zero shot and few shot cases are similar to what was observed by (76), the accuracies reported for the GPT-3.5 Turbo model appear be lower in our experiments, which points to a potential difference in the exact backend LLM model used for inference.
D Limitations of FWC
Coreset support and non-convex feature spaces FWC representative do not need to be within the original samples, but they do need share the same support. As shown in Section 4.2 solving line 5 in Algorithm|| I in cases 1. and 2. means the synthetic representatives could fall outside the original dataset. In case 3., the solution has be selected from the data points already existing in the original dataset (akin to k-medoids). In general. non-convex feature spaces X' might represent challenge, as representatives might be generated in zero-density regions (a simple example could be dataset distributed as a hollow circle or two moons). However, this criticism is also more generally applicable to the existing fair coresets/elustering literature, as well as the k-means algo- rithms, for which specific adjustments have been developed 663 and could be indeed extended to FWC.
Limiting the total number of iterations FWC is not of polynomial time complexity and the total number of iterations might grow faster than linear time when the dataset size is very large, as shown in the synthetic data experiment in Section C.T and Table 2 This phenomenon is shared with k-means, which is also not of polynomial time complexity and is known to potentially take an exponentially large number of iterations to terminate [73]. As mentioned in Section C.I. common practice for clustering set a fixed number of maximum iterations, after which the algorithm is stopped.
Computational bottlenecks The main complexity term for FWC is O(m)), which comes from establishing the cost matrix in the beginning of the solution of problem (8) This complexity is comparable with what occurs in Lloyd's algorithm for k-means and k-medians. This might be problematic if the cost matrix is too large be stored directly in memory. In practice, we do not actually need to store the entire matrix, as we only need to compute the largest component for each row of C for solving problem (8) (see Lemma A.I). so one could further improve the cost of storing the cost matrix. Another option would also be leverage the same approaches used for k- k-means such as, e.g., cost matrix sketching (9]. Finally, FWC would also benefit from GPU implementations akin to k-means and k-medians, which would substantially accelerate the runtime speed of FWC.
Connection between e and downstream learning In our definition of demographic parity in Equation 3 the hyper-parameter e effectively controls how different the outcome rates across sensitive feature groups D of the weighted coreset distribution P2.8 can be from the overall outcome rates in the original dataset pyr- In our experiments (Section 7. we empirically show that limiting the fairness violation in the coresets results in fairer downstream model. However, when training downstream model using FWC we induce a distribution shift between the train set and the test set, as the coresets distribution is never identical the original dataset distribution. Although we have provided some results on the generalization properties of FWC (Proposition 5.5) as well as some intuition about developing downstream learning bounds for FWC in non-i.i.d. settings (Section B.II, theoretically characterize the connection between the faimess violation parameter remains an open question. In essence, the analysis is challenging as the induced distribution shift is dependent on the biases the original dataset distribution, the coreset size m, the metric chosen for the cost matrix and, ultimately, the fairness violation parameter c. For this reason, although we have shown that restricting the fairness violation improves downstream models fairness, an explicit characterization of the downstream effects
27

---

of e, as well as other hyper- parameters, would require significant further work, beyond the scope of this paper.
Implications for other fairness measures As highlighted by [ Chapter 3], fairness notions in classification settings be categorized into notions of independence, separation, and sufficiency. Demographic parity falls in the class of the independence notion, and hence, other measures of fairness that are closely related, e-g., disparate impact, would also improve when optimizing for demographic parity. However, other notions of fairness such as separation or sufficiency may not simultaneously be satisfied [3]. As FWC targets demographic parity, cannot guarantee an improvement in these other measures. To test this, we compute the equalized odds, which falls under the notion of separation, for the downstream classifier in Section (andd check the performance of FWC compared to the other approaches. Table [ indicates the datasets in which FWC is part of the Pareto frontier for both demographic parity and equalized odds. When considering 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 in contrast to demographic parity: in Figure ] trade-off in downstream classification.
FWC sits on the Pareto frontier
across all datasets for hainess--erformantt
Table 8: Presence on the Pareto frontier for FWC across different fairesss violation hyper- parameter values (e {0.01, 0.05, 0.1)). for both demographic parity (left) and equalized odds (right) in the downstream learning settings of Section 7 As equalized odds is not an independence notion of fairness demographic parity, constraints on demographic parity do guarantee an improvement in equalized odds. resulting in FWC not performing as well for downstream performance-faiine tradcoff when using equalized odds.
Pareto Frontier, Demographic Parity
Pareto Frontier, Equalized Odds
Dataset
FWC (e = 0.01)
FWC (e 0.05)
FWC 0.1)
FWC (E = 0.01)
FWC (E 0.05)
FWC (e = 0.1)
Adult
Drug
Crime
V
Credit
E Broader Impact
Our work presents a novel approach to obtain coresets (synthetic representative samples) of a given dataset while reducing biases and disparities in subgroups of the given dataset. As other approaches in the field of algorithmic fairness, our efforts may help populations that would otherwise face disadvantages from a model or decision process. Importantly, our approach refrains from exploiting data itself; rather, it seeks to mitigate biases in data-driven decision systems. is crucial to note that our method does not claim to address all sources types of bias. In addition, while our tools enable a malicious modeler to manipulate algorithmic fairness methods to amplify disparities instead of reducing them, for instance. by reversing the fairness constraint (replacing S with 2), the unfairness a trained model can be detected by assessing over a separate test set from the original dataset.
biases inherent
28

---

Adult Dataset
Adult Dataset (with Fair Pre- Pre-Processing
0.76
0.34
0.30
0.00
0.64
0.64
frander na55
MVC 0.3
Urifrrm Sutnarshing
Parsto Troniier
Uniform Saboamsking
0.40
3.52
0.60
0.64
6.15
0:0
Demographic Disparity
Demegr aphic Disparity
Credit Dataset
Credit Dataset (with Fair Pre Processing)
-.- Pamito Trender
Falfet Heand
Unitten Schramsiing
Partts Trender
Paltet [cMendd hastol SeShakk del Ind. ful:
Unfttrm Lnttern Subramoling
HOt Iu 8:033
Fuefst Miita du!
KiPhurs KeMedilc
HMC Is: B.01)
K-Mturs:
Cas
0.32
3.9
B.M
6.55
8.66
0.67
0.200
6.555
0.00
6,05
0.05
Demographic Disparityy
Demographic Disparity
Crime Dataset
Crime Dataset (with Fair Pre-Processing)
0.20
0.20
0.66
0.66
0.66-
0.84
L 0.64
0.66-
Pusto frunder
Fudeet Maann
Unifirm Suboamsing K-hhoee KiMeeiicc
0.60
Parntz frenter
IK Pauro" To rie de gkirediss
Uniform Subsump
IVC fn 8.331
Palret Medi ds
FiNC 1.:11:0:211 0:231
Kitvent
6.05)
ic 0.25)
Fair Cor.
0.76
0.20
Demographic Disparity
Demographic Disparity
Drug Dataset
Drug Dataset (with Processing)
3.32
2.02
1.74
677
HWC 011
RAC le 051
Ins. Tai Cor
ric 16 (oMoodo
Kiizans
572
noc 001
HVC 8011
Ins. Tain Cor.
Kilbars
Medeio Cot
MWC
0173
61100
2,350
Disparity
Demographic Dispantty
Figure 6: Pairness-utility tradeoff of all methods, indicated by AUC and demographic disparity of downstream MIP classifier across all datasets (rows) and without (left column) or with (right column) fair pre-pree prepproeessing [34] (excluding FWC. to which fairness modification is applied after coresets have been generated). The Pareto frontier, indicated with dashed red-line, is computed across all models and coreset sizes. We report averages over separate train/test splits.
29

---

Adult Dataset
Adult Dataset (with Fair Pre- Pre-Processing)
0.76
0.3
0.30
0.00
0.00
0.64
HWC oe
PWC le: 0.01)
Unsimm S.barmping
Mediinn
0.64
FWC
HWC 0.11
Meanaa
Cor
Mesoo
Unilom Subsamping
0.60
300
230 comegraphic Disperity
0.40
0.60
6:6
6:3 Demegraphic Disparity
6:6
9.55
Credit Dataset
Credit Dataset (with Fair Pre Pre-Procsssigg)
0.70
0.70
0.00
0.50
0.55
Pac
K-htedan Cor
Faitet OkMledeiin))
0.45
Pac 0:1)
Uniform
0.55
05) Faifet
Farret
0.40
Fartet
KMedidds
6.10
Uniforn Subsampling
0.10
6.30
8.10
6.15
030
0.06
6.55 Demographic Disparity
3.00
0.0
3.15
Demagraphic Disparity
Crime Dataset
Crime Dataset (with Fair Pre- Pre-Processing)
0.20
0.20
0.66
0.66-
0.84
1 0.84
0.60-
0.60
0.76
Suboampine
Demographic Disparity
Demographic Disparity
Drug
Drug (with Processing)
A0CC
2.78
6.74
276
0.01
Faines
Subsompping
0.05) IS Meana)
0.79
073
Fainst Nadolaa)
Sussumpting
0.50 Derrogappicc
0.22
50e
Demographic Disparity
Figure 7: Similarly to Figure 6 we report the means and standard deviations over 10 runs of the fairness-utility tradeoff of all methods, indicated by AUC and demographic disparity of downstream MLP classifier across all datasets (rows) and without (left column) or with (right column) fair pre- processing (34] (excluding FWC, to which no fairness modification is applied after coresets have been generated).
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section 4 includes the details the majority minimization algorithm for FWC, with Section 6 showing the equivalence between the unconstrained version of FWC and Lloyd's algorithm for k-medians and k-means. Section 7 iincluess all experiments, which presented the same order as the conclusions presented in the abstract, with the synthetic data experiment first (Figures [ top left, 2 and Table 2). downstream learning and data augmentation using synthetic representatives (Figures and reducing biases in prediction from large language models (Table
and Tables
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See the Limitation section in Appendix D
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
31

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Section 5 and Appendix B for theorems and proposition statements and proof, respectively. The only exception is Proposition 2.1 which is stated in Section 2 Lemma A.I which is stated and proved in Appendix A and Lemma A.2 which proof follows directly from 777 Corollary 5] by extending to the case in which m 7 n.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4 provides the algorithm outline, with Algorithm providing the step- by-step breakdown of the algorithm. The variant of FairWASP for line 4 in Algorithm Jsee the same algorithm as (77) with m * n, while implementation details for the experiments, along with hyper- pperrpparaeetes for each methods can found in Section 7 and Appendix C Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
32

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Data openly available and details to reproduce the main experimental
results are provided in Section 7 and Appendix [ The code is not available publicly at the moment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//iips.c/ppile wttpcccppppppppeeeeeeeeeeeeeeeee wwwpee/ggiisss//eee httpa///giidee//eeeuubbiissss sonooooooc for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Implementation details are provided in Section 7 Appendix C.I for the runtime analysis with synthetic data and Appendix C.2 for the downstream learning and data augmentation experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
33

---

Justification: Yes, we provide commentary in Appendix and include la uncertainty computed over 10 runs with separate seeds in Figures (top left), (bottom row),
(bottom row). and 7nd Tables
5 6 and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: For non-LLM experiment, the computing environment is reported in Ap- pendix C Ubuntu machine with 32GB of RAM and 2.50GHz Intel(R) Xeon(R) Platinum 8259CL CPU), LLM experiments require access the OpenAI API to query GPT-3.5 and GPT-4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We include reproducibility details, data publicly available and we address the broader impact and societal implications in Section
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
34

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We address the broader impact of our method in Section H
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeetm of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Not applicable, this paper not releasing public data, image generator or pretrained language models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-uss should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
35

---

Justification:
All datasets are publicly available, and GPT-3.5 and GPT-4 were access through OpenAI API. All sources were cited the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessii thcode condsatsesss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
No new assets were introduced by this work.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or human subjects were included in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
36

---

Answer:
[NA]
Justification:
No human subjects were involved in this study.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
37


Reviews:
[{"review_id": "RMXG27sSe5", "reviewer": "Reviewer_xAdA", "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.\n\nThe authors formulate the problem as an optimization problem (4). \nThere are four steps:\n\t1. Manually set the proportion of each combination of decision (Y) and feature (D). \n\t2. Formulate linear constraints for the fairness constraint. This one borrows directly from [71].\n\t3. Formulate the Wasserstein distance optimization by using [56]\n\t4. Simply further\n\nAfter 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. \n\nSection 5 reports theoretical guarantees: running time of the algorithm, convergence guarantee for the surrogate function, and last bound the generalization guarantees. \n\nExperiments are reported in the last section:  e.g., improving fairness in LLM. \n\nOn 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. \n\nThe weaknesses (or limitation in significance) is that both crucial steps (2) and (3) are basically using prior work. The theoretical results are standard. \n\nSummarizing I feel that the paper is OK but would give a weak accept.", "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.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\nTo 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. \n  \n\n|            |   Pareto Frontier, | Demographic Parity  |   |   Pareto Frontier,  |      Equalized Odds                    |                         |\n|:----------:|:-------------------------------------:|:------------------------:|:-----------------------:|:---------------------------------:|:------------------------:|:-----------------------:|\n|   *Dataset*  |          FWC ($\\epsilon=0.01$)        |   FWC ($\\epsilon=0.05$)  |   FWC ($\\epsilon=0.1$)  |        FWC ($\\epsilon=0.01$)      |   FWC ($\\epsilon=0.05$)  |   FWC ($\\epsilon=0.1$)  |\n|    *Adult*   |              $\\checkmark$             |        $\\checkmark$      |                         |            $\\checkmark$           |                          |                         |\n|     *Drug*   |              $\\checkmark$             |        $\\checkmark$      |       $\\checkmark$      |                                   |                          |                         |\n|    *Crime*   |              $\\checkmark$             |        $\\checkmark$      |       $\\checkmark$      |                                   |                          |       $\\checkmark$      |\n|    *Credit*  |              $\\checkmark$             |                          |                         |            $\\checkmark$           |                          |       $\\checkmark$      |\n\n  \n     \nFinally, 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).\n\n\nReferences:\n- [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.\n\n- [2] Barocas, Solon, Moritz Hardt, and Arvind Narayanan. Fairness and machine learning: Limitations and opportunities. MIT press, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nRPlBTOsFW", "reviewer": "Reviewer_MJ1C", "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.", "questions": "See Weaknesses.", "limitations": "The authors included detailed limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "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)? \n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n1. 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. \n\n2. 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QgsldCNLHJ", "reviewer": "Reviewer_cAaY", "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.", "questions": "See weaknesses", "limitations": "See Weaknesses", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "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. \n\n2) 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. \n\n3) 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. \n\n2) 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?\n\n3) 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. \n\n4) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their time and comments in the review of our work; we answer each point below.\n\n1. 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:\n\n- __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);\n\n- __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);\n\n- __Connection to k-means.__ We establish a practical connection to the k-means algorithm, thereby extending FWC's applicability beyond fairness considerations (Section 6);\n\n- __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).\n\n2. 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). \n\n3. We have corrected the inconsistencies, thanks for pointing them out.\n\n4. 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. \n\nReferences:\n- [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.\n - [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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2LfzT0oyko", "reviewer": "Reviewer_4tbZ", "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.", "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?", "limitations": "Limitations are thoroughly discussed in the Appendix.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The Wasserstein problem is well-formulated with theoretical guarantees.\n- 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 |$.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful review and comments; we answer each questions below.\n\n1. 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:\n\n    $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}),$\n\n    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.\n    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.\n\n2. 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}|$. \n\n3. 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. \n\n|            |       Pareto Frontier    |                          |                         |\n|:----------:|:------------------------:|:------------------------:|:-----------------------:|\n|   *Dataset*  |   FWC ($\\epsilon=0.01$)  |   FWC ($\\epsilon=0.05$)  |   FWC ($\\epsilon=0.1$)  |\n|    *Adult*   |        $\\checkmark$      |        $\\checkmark$      |                         |\n|     *Drug*   |        $\\checkmark$      |        $\\checkmark$      |       $\\checkmark$      |\n|    *Crime*   |        $\\checkmark$      |        $\\checkmark$      |       $\\checkmark$      |\n|    *Credit*  |        $\\checkmark$      |                          |                         |\n\n\n\n4. 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. \n\nReferences:\n- [1] Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimination. Knowl. Inf. Syst., 33(1):1–33, October 2012.\n\n - [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.\n\n  - [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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank again all reviewers for their comments, detailed feedback and questions which have improved the quality of our paper. 

While we have addressed each reviewer individually, we are using the global rebuttal to upload a .pdf with the new version of Figure 1 which includes Pareto frontiers; this addresses the comment made by reviewer 4tbZ and is relevant for the discussion of demographic parity following the question by reviewer xAdA.

Meta-review: The reviewers noted that this paper formulates a relevant and interesting problem and clearly describes an approach that has sound theoretical guarantees and thorough experiments. Given the unanimous recommendation for acceptance from the four reviewers, I recommend acceptance.
Decision: Accept (poster)