A Theoretical Approach to Characterize the Accuracy-Fairness Trade-off
  Pareto Frontier
Hua Tang Lu Cheng Ninghao Liu Mengnan Du
While the accuracy-fairness trade-off has been frequently observed in the
literature of fair machine learning, rigorous theoretical analyses have been
scarce. To demystify this long-standing challenge, this work seeks to develop a
theoretical framework by characterizing the shape of the accuracy-fairness
trade-off Pareto frontier (FairFrontier), determined by a set of all optimal
Pareto classifiers that no other classifiers can dominate. Specifically, we
first demonstrate the existence of the trade-off in real-world scenarios and
then propose four potential categories to characterize the important properties
of the accuracy-fairness Pareto frontier. For each category, we identify the
necessary conditions that lead to corresponding trade-offs. Experimental
results on synthetic data suggest insightful findings of the proposed
framework: (1) When sensitive attributes can be fully interpreted by
non-sensitive attributes, FairFrontier is mostly continuous. (2) Accuracy can
suffer a \textit{sharp} decline when over-pursuing fairness. (3) Eliminate the
trade-off via a two-step streamlined approach. The proposed research enables an
in-depth understanding of the accuracy-fairness trade-off, pushing current fair
machine-learning research to a new frontier.