  Achieving the Bayes optimal binary classification rule subject to group
fairness constraints is known to be reducible, in some cases, to learning a
group-wise thresholding rule over the Bayes regressor. In this paper, we extend
this result by proving that, in a broader setting, the Bayes optimal fair
learning rule remains a group-wise thresholding rule over the Bayes regressor
but with a (possible) randomization at the thresholds. This provides a stronger
justification to the post-processing approach in fair classification, in which
(1) a predictor is learned first, after which (2) its output is adjusted to
remove bias. We show how the post-processing rule in this two-stage approach
can be learned quite efficiently by solving an unconstrained optimization
problem. The proposed algorithm can be applied to any black-box machine
learning model, such as deep neural networks, random forests and support vector
machines. In addition, it can accommodate many fairness criteria that have been
previously proposed in the literature, such as equalized odds and statistical
parity. We prove that the algorithm is Bayes consistent and motivate it,
furthermore, via an impossibility result that quantifies the tradeoff between
accuracy and fairness across multiple demographic groups. Finally, we conclude
by validating the algorithm on the Adult benchmark dataset.
