# Bias Detection via Maximum Subgroup Discrepancy

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 68 references that are in the map.
- First posted on arXiv 4 Feb 2025.

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

- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [Learning De-biased Representations with Biased Representations](https://mlsanity.com/paper/1910.02806/) (2019)
- [One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques](https://mlsanity.com/paper/1909.03012/) (2019)
- [An Intersectional Definition of Fairness](https://mlsanity.com/paper/1807.08362/) (2018)
- [An Empirical Study of Rich Subgroup Fairness for Machine Learning](https://mlsanity.com/paper/1808.08166/) (2018)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges](https://mlsanity.com/paper/2305.06969/) (2023)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Generalized Linear Rule Models](https://mlsanity.com/paper/1906.01761/) (2019)
- [Mitigating Dataset Bias by Using Per-sample Gradient](https://mlsanity.com/paper/2205.15704/) (2022)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Amortized Projection Optimization for Sliced Wasserstein Generative Models](https://mlsanity.com/paper/2203.13417/) (2022)
- [Identifying Significant Predictive Bias in Classifiers](https://mlsanity.com/paper/1611.08292/) (2016)
- [Learning Optimized Or's of And's](https://mlsanity.com/paper/1511.02210/) (2015)
- [On Approximating Total Variation Distance](https://mlsanity.com/paper/2206.07209/) (2022)
- [Sample Complexity of Probability Divergences under Group Symmetry](https://mlsanity.com/paper/2302.01915/) (2023)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [Progress in Mathematical Programming Solvers from 2001 to 2020](https://mlsanity.com/paper/2206.09787/) (2022)
- [A simple polynomial-time approximation algorithm for the total variation distance between two product distributions](https://mlsanity.com/paper/2208.00740/) (2022)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Computability of Optimizers](https://mlsanity.com/paper/2301.06148/) (2023)
- [Interpretable Differencing of Machine Learning Models](https://mlsanity.com/paper/2306.06473/) (2023)

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

- [Intersectional Fairness via Mixed-Integer Optimization](https://mlsanity.com/paper/2601.19595/) (2026)
- [humancompatible.detect: a Python Toolkit for Detecting Bias in AI Models](https://mlsanity.com/paper/2509.24340/) (2025)

## Abstract (arXiv)

Bias evaluation is fundamental to trustworthy AI, both in terms of checking data quality and in terms of checking the outputs of AI systems. In testing data quality, for example, one may study the distance of a given dataset, viewed as a distribution, to a given ground-truth reference dataset. However, classical metrics, such as the Total Variation and the Wasserstein distances, are known to have high sample complexities and, therefore, may fail to provide a meaningful distinction in many practical scenarios. In this paper, we propose a new notion of distance, the Maximum Subgroup Discrepancy (MSD). In this metric, two distributions are close if, roughly, discrepancies are low for all feature subgroups. While the number of subgroups may be exponential, we show that the sample complexity is linear in the number of features, thus making it feasible for practical applications. Moreover, we provide a practical algorithm for evaluating the distance based on Mixed-integer optimization (MIO). We also note that the proposed distance is easily interpretable, thus providing clearer paths to fixing the biases once they have been identified. Finally, we describe a natural general bias detection framework, termed MSDD distances, and show that MSD aligns well with this framework. We empirically evaluate MSD by comparing it with other metrics and by demonstrating the above properties of MSD on real-world datasets.