  A trade-off between accuracy and fairness is almost taken as a given in the
existing literature on fairness in machine learning. Yet, it is not preordained
that accuracy should decrease with increased fairness. Novel to this work, we
examine fair classification through the lens of mismatched hypothesis testing:
trying to find a classifier that distinguishes between two ideal distributions
when given two mismatched distributions that are biased. Using Chernoff
information, a tool in information theory, we theoretically demonstrate that,
contrary to popular belief, there always exist ideal distributions such that
optimal fairness and accuracy (with respect to the ideal distributions) are
achieved simultaneously: there is no trade-off. Moreover, the same classifier
yields the lack of a trade-off with respect to ideal distributions while
yielding a trade-off when accuracy is measured with respect to the given
(possibly biased) dataset. To complement our main result, we formulate an
optimization to find ideal distributions and derive fundamental limits to
explain why a trade-off exists on the given biased dataset. We also derive
conditions under which active data collection can alleviate the
fairness-accuracy trade-off in the real world. Our results lead us to contend
that it is problematic to measure accuracy with respect to data that reflects
bias, and instead, we should be considering accuracy with respect to ideal,
unbiased data.
