# On the Power of Randomization in Fair Classification and Representation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 41 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [The Variational Fair Autoencoder](https://mlsanity.com/paper/1511.00830/) (2015)
- [Flexibly Fair Representation Learning by Disentanglement](https://mlsanity.com/paper/1906.02589/) (2019)
- [Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees](https://mlsanity.com/paper/1806.06055/) (2018)
- [Inherent Tradeoffs in Learning Fair Representations](https://mlsanity.com/paper/1906.08386/) (2019)
- [Fair Generative Modeling via Weak Supervision](https://mlsanity.com/paper/1910.12008/) (2019)
- [Fair Regression with Wasserstein Barycenters](https://mlsanity.com/paper/2006.07286/) (2020)
- [Learning Certified Individually Fair Representations](https://mlsanity.com/paper/2002.10312/) (2020)
- [Post-processing for Individual Fairness](https://mlsanity.com/paper/2110.13796/) (2021)
- [Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification](https://mlsanity.com/paper/1906.05082/) (2019)
- [Metric-Free Individual Fairness in Online Learning](https://mlsanity.com/paper/2002.05474/) (2020)
- [Bayes-Optimal Classifiers under Group Fairness](https://mlsanity.com/paper/2202.09724/) (2022)
- [Learning Fair Representations for Kernel Models](https://mlsanity.com/paper/1906.11813/) (2019)
- [Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability](https://mlsanity.com/paper/1809.04578/) (2018)

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

- [A Critical Review of Predominant Bias in Neural Networks](https://mlsanity.com/paper/2502.11031/) (2025)

## Abstract (arXiv)

Fair classification and fair representation learning are two important problems in supervised and unsupervised fair machine learning, respectively. Fair classification asks for a classifier that maximizes accuracy on a given data distribution subject to fairness constraints. Fair representation maps a given data distribution over the original feature space to a distribution over a new representation space such that all classifiers over the representation satisfy fairness. In this paper, we examine the power of randomization in both these problems to minimize the loss of accuracy that results when we impose fairness constraints. Previous work on fair classification has characterized the optimal fair classifiers on a given data distribution that maximize accuracy subject to fairness constraints, e.g., Demographic Parity (DP), Equal Opportunity (EO), and Predictive Equality (PE). We refine these characterizations to demonstrate when the optimal randomized fair classifiers can surpass their deterministic counterparts in accuracy. We also show how the optimal randomized fair classifier that we characterize can be obtained as a solution to a convex optimization problem. Recent work has provided techniques to construct fair representations for a given data distribution such that any classifier over this representation satisfies DP. However, the classifiers on these fair representations either come with no or weak accuracy guarantees when compared to the optimal fair classifier on the original data distribution. Extending our ideas for randomized fair classification, we improve on these works, and construct DP-fair, EO-fair, and PE-fair representations that have provably optimal accuracy and suffer no accuracy loss compared to the optimal DP-fair, EO-fair, and PE-fair classifiers respectively on the original data distribution.