# Statistical Guarantees in the Search for Less Discriminatory Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 30 Dec 2025.

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

- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [Fairlearn: Assessing and Improving Fairness of AI Systems](https://mlsanity.com/paper/2303.16626/) (2023)
- [Optimal Inference After Model Selection](https://mlsanity.com/paper/1410.2597/) (2014)
- [Characterizing Fairness Over the Set of Good Models Under Selective Labels](https://mlsanity.com/paper/2101.00352/) (2021)
- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [Empirical observation of negligible fairness-accuracy trade-offs in machine learning for public policy](https://mlsanity.com/paper/2012.02972/) (2020)
- [Arbitrariness and Social Prediction: The Confounding Role of Variance in Fair Classification](https://mlsanity.com/paper/2301.11562/) (2023)
- [Recombination: A family of Markov chains for redistricting](https://mlsanity.com/paper/1911.05725/) (2019)
- [Be Intentional About Fairness!: Fairness, Size, and Multiplicity in the Rashomon Set](https://mlsanity.com/paper/2501.15634/) (2025)
- [Descending Price Optimally Coordinates Search](https://mlsanity.com/paper/1603.07682/) (2016)
- [Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans](https://mlsanity.com/paper/2008.06131/) (2020)
- [What Constitutes a Less Discriminatory Algorithm?](https://mlsanity.com/paper/2412.18138/) (2024)
- [Recent Developments in Pandora's Box Problem: Variants and Applications](https://mlsanity.com/paper/2308.12242/) (2023)
- [The Statistical Fairness-Accuracy Frontier](https://mlsanity.com/paper/2508.17622/) (2025)
- [Audits Under Resource, Data, and Access Constraints: Scaling Laws For Less Discriminatory Alternatives](https://mlsanity.com/paper/2509.05627/) (2025)

## Abstract (arXiv)

U.S. discrimination law can impose liability on firms that fail to adopt a less discriminatory alternative (LDA): a decision policy that achieves the same business objectives while reducing disparate impact on legally protected groups. Recent scholarship argues that this doctrine has direct implications for algorithmic decision-making in high-stakes domains such as employment, lending, and housing, potentially obligating firms to search for "less discriminatory algorithms" (Black et al., 2024). Regulators have at times encouraged proactive LDA searches, reinforcing the expectation of a good-faith effort to identify equally performant models with lower disparate impact. Model multiplicity makes such searches plausible: retraining with different random seeds can yield models with comparable predictive performance but materially different disparate impacts. Yet firms cannot retrain indefinitely, raising a central question: when is the search sufficient to demonstrate good faith? We formalize LDA search under multiplicity as an optimal stopping problem in which a developer seeks to produce evidence that further search is unlikely to yield meaningful improvements. Our main contribution is an adaptive stopping algorithm that provides a high-probability upper bound on the best disparate-impact gains attainable through continued retraining, enabling developers to certify (e.g., to a court) that additional search is unlikely to help. We also show how stronger distributional assumptions over the model space can yield tighter bounds, and we validate the approach on real-world credit and housing datasets.