Metric-Fair Classifier Derandomization
  We study the problem of \emph{classifier derandomization} in machine
learning: given a stochastic binary classifier $f: X \to [0,1]$, sample a
deterministic classifier $\hat{f}: X \to \{0,1\}$ that approximates the output
of $f$ in aggregate over any data distribution. Recent work revealed how to
efficiently derandomize a stochastic classifier with strong output
approximation guarantees, but at the cost of individual fairness -- that is, if
$f$ treated similar inputs similarly, $\hat{f}$ did not. In this paper, we
initiate a systematic study of classifier derandomization with metric fairness
guarantees. We show that the prior derandomization approach is almost maximally
metric-unfair, and that a simple ``random threshold'' derandomization achieves
optimal fairness preservation but with weaker output approximation. We then
devise a derandomization procedure that provides an appealing tradeoff between
these two: if $f$ is $\alpha$-metric fair according to a metric $d$ with a
locality-sensitive hash (LSH) family, then our derandomized $\hat{f}$ is, with
high probability, $O(\alpha)$-metric fair and a close approximation of $f$. We
also prove generic results applicable to all (fair and unfair) classifier
derandomization procedures, including a bias-variance decomposition and
reductions between various notions of metric fairness.
