  Recent years have seen a surge of machine learning approaches aimed at
reducing disparities in model outputs across different subgroups. In many
settings, training data may be used in multiple downstream applications by
different users, which means it may be most effective to intervene on the
training data itself. In this work, we present FairWASP, a novel pre-processing
approach designed to reduce disparities in classification datasets without
modifying the original data. FairWASP returns sample-level weights such that
the reweighted dataset minimizes the Wasserstein distance to the original
dataset while satisfying (an empirical version of) demographic parity, a
popular fairness criterion. We show theoretically that integer weights are
optimal, which means our method can be equivalently understood as duplicating
or eliminating samples. FairWASP can therefore be used to construct datasets
which can be fed into any classification method, not just methods which accept
sample weights. Our work is based on reformulating the pre-processing task as a
large-scale mixed-integer program (MIP), for which we propose a highly
efficient algorithm based on the cutting plane method. Experiments demonstrate
that our proposed optimization algorithm significantly outperforms
state-of-the-art commercial solvers in solving both the MIP and its linear
program relaxation. Further experiments highlight the competitive performance
of FairWASP in reducing disparities while preserving accuracy in downstream
classification settings.
