# Metric-Fair Classifier Derandomization

arXiv: https://arxiv.org/abs/2206.07826 · HTML: https://mlsanity.com/paper/2206.07826/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 15 Jun 2022.

## Builds on (most cited first, 16 of 16)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [Average Individual Fairness: Algorithms, Generalization and Experiments](https://mlsanity.com/paper/1905.10607/) (2019)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [The Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (2020)
- [Randomization matters. How to defend against strong adversarial attacks](https://mlsanity.com/paper/2002.11565/) (2020)
- [Theoretical evidence for adversarial robustness through randomization](https://mlsanity.com/paper/1902.01148/) (2019)
- [Probably Approximately Metric-Fair Learning](https://mlsanity.com/paper/1803.03242/) (2018)
- [Optimum Statistical Estimation with Strategic Data Sources](https://mlsanity.com/paper/1408.2539/) (2014)
- [Beyond Locality-Sensitive Hashing](https://mlsanity.com/paper/1306.1547/) (2013)
- [Strategyproof Linear Regression in High Dimensions](https://mlsanity.com/paper/1805.10693/) (2018)
- [On Fairness, Diversity and Randomness in Algorithmic Decision Making](https://mlsanity.com/paper/1706.10208/) (2017)
- [Linear Classifiers that Encourage Constructive Adaptation](https://mlsanity.com/paper/2011.00355/) (2020)

## Built on by (most cited first, 2 of 2)

- [Weak Proxies are Sufficient and Preferable for Fairness with Missing Sensitive Attributes](https://mlsanity.com/paper/2210.03175/) (2022)
- [Responsible AI (RAI) Games and Ensembles](https://mlsanity.com/paper/2310.18832/) (2023)

## Abstract (arXiv)

We study the problem of classifier derandomization in machine learning: given a stochastic binary classifier f: X → [0,1], sample a deterministic classifier hatf: X → 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, hatf 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 α-metric fair according to a metric d with a locality-sensitive hash (LSH) family, then our derandomized hatf is, with high probability, O(α)-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.