📊 statistics

Statistical Guarantees in the Search for Less Discriminatory Algorithms

This paper addresses the legal requirement for firms to find less discriminatory algorithms by formalizing the search as an optimal stopping problem and proposing an adaptive algorithm that provides statistical guarantees to certify when further model retraining is unlikely to yield significant improvements in reducing disparate impact.

Original authors: Chris Hays, Ben Laufer, Solon Barocas, Manish Raghavan

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chris Hays, Ben Laufer, Solon Barocas, Manish Raghavan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Unfair Algorithm" Dilemma

Imagine you are a bank manager trying to decide who gets a loan. You use a computer program (an algorithm) to make these decisions. Recently, the law has said: "If your computer program accidentally discriminates against a specific group of people (like a certain race or gender), you are in trouble. But, if you can prove you looked for a better version of that program—one that makes the same money but treats people more fairly—and you just couldn't find one, you might be off the hook."

This is called the search for a Less Discriminatory Alternative (LDA).

The Catch:
Computer models are a bit like rolling dice. Even if you use the exact same code and the exact same data, if you run the training process twice, you might get two slightly different results. Sometimes, one version is very fair, and another is slightly less fair, even though they are both equally good at predicting who will pay back the loan.

The problem is: How many times do you have to roll the dice before you can say, "Okay, I've tried enough. I can't find a better one, so I'm stopping"?

If you stop too early, a judge might say, "You didn't try hard enough." If you keep going forever, you waste money and time. The paper asks: How do you know when you've searched enough to prove you acted in "good faith"?

The Solution: The "Smart Shopper" Algorithm

The authors propose a mathematical tool (an algorithm) that acts like a very smart, cautious shopper.

The Analogy: Shopping for the Best Deal
Imagine you are shopping for a specific item, say a toaster. You want the one that costs the least money but works just as well as the others.

You go to the first store and see a toaster for $50.
You go to the second store and see one for $48. You buy it.
You go to a third store and see one for $47. You buy that one.

But you can't visit every store in the world. At some point, you have to stop. How do you know you don't need to visit one more store just in case there's a $40 toaster hiding there?

The paper's algorithm is like a statistical compass that tells you when to stop looking. It calculates: "Based on the prices I've seen so far, the chance of finding a significantly cheaper toaster in the next store is so tiny that it's not worth the gas money to drive there."

How the Paper's Tool Works

The authors break this down into three main ideas:

1. The "Stop" Button (Optimal Stopping)
They treat the search for a fair algorithm like a game where you keep playing until the reward isn't worth the cost.

The Cost: Every time you retrain a model, it costs time and computer power.
The Reward: Every time you find a model that is slightly less discriminatory, you gain "fairness points."
The Rule: The algorithm keeps training new models as long as the expected gain in fairness is higher than the cost of training. Once the math says the next model probably won't help much, it hits the "Stop" button.

2. The "Safety Net" (Statistical Guarantees)
The authors don't just guess when to stop. They built a "safety net" (mathematical proof) that guarantees, with very high confidence (like 95% or 99%), that you haven't missed a "magic" model that would have been much better.

Think of it like a weather forecast. You can't know the future with 100% certainty, but if the forecast says there is a 99% chance of no rain, you can confidently leave your umbrella at home.
This allows a company to walk into a courtroom and say, "We stopped searching not because we gave up, but because our math proves with 99% certainty that looking further wouldn't have helped."

3. The "Real World" Test
The authors tested this on real data about credit and housing. They simulated thousands of different scenarios where they retrained models over and over.

What they found: In many cases, you don't need to search forever. After training about 60 different versions of a model, the "fairness gains" usually drop to almost zero. It's like finding that after checking 60 stores, the price of the toaster hasn't dropped below $47 anymore.
They also found that for some types of data, you might only need to check 10 models before you can safely stop.

Why This Matters

This paper gives companies a certificate of good faith.

Before this, a company might be sued and have to guess, "Did we try hard enough?" Now, they can use this tool to generate a report that says: "We trained 60 models. Our statistical guarantee shows that the chance of finding a significantly fairer model in the next 60 attempts is less than 1%. Therefore, our search was reasonable and sufficient."

It turns a vague legal argument about "trying hard enough" into a concrete, math-based decision that can be shown to a judge or regulator.

Summary in One Sentence

The paper provides a mathematical "stop sign" that tells companies exactly when they have searched enough for a fairer algorithm to prove to the law that they acted responsibly, without wasting infinite resources on a search that will never end.

Technical Summary: Statistical Guarantees in the Search for Less Discriminatory Algorithms

Problem Statement
U.S. discrimination law, particularly the doctrine of disparate impact, can impose liability on firms that fail to adopt a "less discriminatory alternative" (LDA)—a decision policy that achieves equivalent business objectives while reducing disparate impact on protected groups. Recent scholarship suggests this doctrine obligates firms to proactively search for such algorithms in high-stakes domains like employment, lending, and housing.

However, a central challenge arises from model multiplicity: retraining models with different random seeds or data subsets often yields predictors with comparable accuracy but materially different disparate impacts. While firms can sample multiple models to find a less discriminatory one, they cannot retrain indefinitely. The core problem is operationalizing the legal standard of "good faith": When is a search for LDAs sufficient to demonstrate that further search is unlikely to yield meaningful improvements? Current legal and regulatory guidance lacks precise criteria for determining when the marginal cost of additional search outweighs the marginal benefit in reduced discrimination.

Methodology
The authors formalize the LDA search as an optimal stopping problem. A firm trains a sequence of models $h_1, h_2, \dots$ by sampling from a randomized training procedure $\mathcal{A}$ conditional on a fixed dataset $D$ . The goal is to stop training at time $\tau$ when the expected marginal benefit of training an additional model (in terms of disparate impact reduction) falls below a cost threshold $\gamma$ (defined as the ratio of training cost to the utility of a unit improvement in disparate impact).

The framework addresses two sources of uncertainty:

Unknown Distribution: The distribution of model performance (disparate impact) is unknown.
Finite Data: The true disparate impact of a model cannot be observed directly; only an empirical estimate on a test set is available.

To solve this, the paper develops adaptive stopping algorithms that provide high-probability guarantees. The approach decomposes the expected marginal gain $g(u)$ into two components:

Improvement Probability ( $p$ ): The probability that a new sample is strictly better than the current best.
Conditional Expected Improvement (CEI, $\mu$ ): The expected magnitude of improvement given that a new sample is better.

The authors construct anytime-valid upper bounds for these quantities:

Bounding $p$ : They utilize a novel sequence upper-bounding the probability of observing a new minimum in a sequence of i.i.d. random variables (Lemma 3.2). This bound holds for all time steps $t$ simultaneously with probability $1-\delta$ .
Bounding $\mu$ : They propose several bounds based on distributional assumptions (Table 1). A universal bound ( $\bar{\mu}(u) = u$ ) requires no assumptions. Tighter bounds are derived under assumptions such as a sub-uniform left tail, an exponential left tail, or a known lower bound on disparate impact.
Finite Data Correction: To handle the gap between empirical and true disparate impact, the authors introduce an assumption of a non-decreasing selection effect (Assumption 3.4), implying that the regression-to-the-mean effect does not increase as the observed performance improves.

Key Contributions

Formalization of LDA Search: The paper formalizes the search for less discriminatory algorithms as an optimal stopping problem, providing a statistical framework to certify the sufficiency of a search.
Adaptive Stopping Algorithm (Algorithm 1): The authors present an algorithm that adaptively trains models and stops when the product of the upper-bounded improvement probability and the upper-bounded CEI falls below the cost threshold $\gamma$ .
Statistical Guarantees (Theorem 3.5): The main theoretical result provides a high-probability guarantee ( $1-\delta$ ) that when the algorithm stops, the expected marginal benefit of further training is indeed below the cost threshold. This allows firms to provide a "certificate" to courts or regulators that additional search is unlikely to help.
Data-Driven Bounds (Algorithm 2): The paper extends the framework to estimate the CEI bound from data (under Assumption 3.6), allowing for tighter bounds without pre-specifying distributional parameters, though this requires a union bound over confidence budgets.
Empirical Validation: The approach is validated on real-world credit (Adult, Folktables) and housing (HMDA) datasets using logistic regression, random forests, and gradient boosted trees.

Results

Model Multiplicity: Empirical analysis confirms significant variation in disparate impact across models trained with identical procedures but different seeds, while accuracy variation remains small. This supports the premise that retraining can yield less discriminatory models "for free" (without accuracy loss).
Stopping Performance: In experiments, the algorithm typically stops after training a relatively small number of models (often fewer than 60). Beyond this point, the marginal gains in disparate impact reduction drop to the hundredths of a percent per model.
Comparison to Ground Truth: When compared to a "full-information" regime (where the true distribution is known), the algorithm's stopping time slightly "overshoots" the optimal stopping time by tens of models on average. However, the authors note that the logarithmic scale of marginal gains means this overshoot represents a polynomial decrease in value, and the algorithm successfully identifies the point where returns diminish significantly.
Fairness-Aware Methods: The method performs comparably when applied to models trained with fairness-aware frameworks (e.g., Fairlearn) versus standard "vanilla" training.

Significance and Claims
The paper claims to provide the first statistical tools to quantify and certify the sufficiency of an LDA search under model multiplicity. By framing the search as an optimal stopping problem with high-probability bounds, the authors offer a mechanism for firms to demonstrate "good faith" efforts to regulators and courts without requiring infinite resources.

The authors are modest about the scope of their contribution, noting that:

Their procedure is one component of a broader search that includes qualitative considerations (e.g., feature selection, model assumptions).
The framework assumes a fixed cost-benefit ratio; determining these values remains a subject of ongoing legal and economic debate.
The empirical results are illustrative, based on publicly available datasets and specific model classes, and may differ in industrial settings with massive datasets and complex pipelines.
The framework can be extended to other optimal stopping problems (e.g., hyperparameter tuning, prompt engineering for LLMs), but the paper focuses specifically on the LDA context.

Ultimately, the work bridges the gap between legal doctrine requiring a search for less discriminatory alternatives and the practical limitations of machine learning development, offering a rigorous statistical method to determine when a search is "good enough."