A practical test for whether more model retraining can reduce bias: the authors provide an adaptive stopping rule that certifies, with high probability, when further searches for a 'less discriminatory algorithm' are unlikely to help. Applied to credit and housing datasets the method flags when additional retraining is futile, though its assurances rely on assumptions about model variability and access to demographic labels.

Main Finding

The paper formalizes the search for "less discriminatory algorithms" (LDAs) as an optimal stopping problem under model multiplicity and provides an adaptive stopping algorithm with provable, high‑probability guarantees. The algorithm outputs a certificate (an upper bound) on the marginal disparate‑impact gains attainable by further retraining; when that bound falls below a pre‑specified cost/benefit threshold, a firm can stop retraining while demonstrating that further search is unlikely to meaningfully reduce disparate impact. The method is validated on real credit and housing datasets and typically requires only a modest number of retrainings (often tens, rarely hundreds) before marginal gains become negligible.

Key Points

• Problem framing
  • Retraining with randomness (seeds, splits, hyperparameters) can produce many high‑accuracy models with varying disparate impact.
  • Firms face the practical/legal question: how long must they search to reasonably claim they tried to find an LDA?
  • Authors formalize this as an optimal stopping problem: continue sampling models while expected marginal benefit from another sample exceeds cost.
• Objective and decision rule
  • Define true utility Q(h) (e.g., selection‑rate disparity) and empirical estimate ˆQ(h) on held‑out data.
  • Given cost per retrain c and value per unit improvement b, use threshold γ = c/b. Stop when EP[Uτ − Uτ+1 | ˆUτ] ≤ γ, where Ut is the true utility of the current best empirical model.
• Algorithmic contribution
  • An adaptive stopping algorithm (Algorithm 1) that computes an anytime-valid, high‑probability upper bound on the marginal improvement attainable by further iid draws from the (unknown) model performance distribution.
  • The bound leverages anytime‑valid inference techniques and a novel, asymptotically near‑optimal sequence upper‑bounding the chance of improving upon the running best sample.
• Theoretical guarantees
  • Theorem (3.5): When the algorithm halts, with high probability the expected marginal benefit of retraining is ≤ γ.
  • The algorithm is guaranteed to halt in finite time; the paper gives a data‑independent upper bound on required retrainings as a function of γ (and confidence parameters). Stronger distributional assumptions yield tighter bounds.
• Empirical findings
  • Validated on public credit and housing datasets using standard ML methods and random retraining.
  • Observed heterogeneity across dataset/model pairs, but in all cases marginal benefits decline quickly: after ~60 retrainings marginal gains are typically in the hundredths of a percent per additional model; in several cases they are essentially negligible after fewer than 10 retrainings.
• Broader applicability
  • Method extends beyond disparate impact to any bounded loss (e.g., pure accuracy, weighted objectives), and to other search problems (hyperparameter search, sampling in redistricting), provided samples are iid (or dependence is otherwise handled).

Data & Methods

• Formal setup
  • Single fixed dataset D sampled iid from population; randomized training procedure A(D) that returns models iid conditional on D.
  • For each sample t, true utility Qt = Q(ht) and empirical utility ˆQt = ˆQ(ht; Dtest_t) (losses bounded in [0,1]).
  • Trainer repeatedly samples models h1, h2, … from A(D), tracks empirical best ˆU_t, and considers stopping after τ samples.
  • Assumes model samples are deployable (if not, rejection sampling or an accuracy threshold can be used to enforce deployability).
• Statistical methods
  • Uses anytime‑valid inference to produce sequential high‑probability upper bounds on the distributional improvement remaining given the observed empirical best.
  • Develops a novel sequence that upper‑bounds the probability that an iid draw will beat the current best; this sequence is asymptotically near‑optimal and supports adaptive stopping.
  • Analysis covers three regimes: (i) known distribution and noiseless evaluations (trivial thresholding), (ii) unknown distribution but noiseless observations, and (iii) unknown distribution with noisy empirical evaluations (finite test data)—the paper handles the realistic noisy case.
• Empirical protocol
  • Retrain multiple models by randomizing seeds/hyperparameters/algorithms; evaluate disparate impact (and other objectives) on held‑out splits.
  • Compare algorithmic stopping times to an ideal full‑information stopping time (which knows the limit distribution).
  • Report marginal improvement per retrain and stopping times across dataset/model pairs (credit and housing datasets).

Implications for AI Economics

• Operationalizing legal/regulatory expectations
  • Provides a concrete, statistically principled method for firms to certify a "good‑faith" search for LDAs: an explicit stopping rule tied to economic parameters (training cost c and benefit valuation b).
  • Regulators and courts could use the method to assess whether a firm’s search effort was reasonable or misallocated, and to set or evaluate guidance about acceptable search burdens.
• Cost–benefit framing for firm behavior
  • Embeds retraining decisions in a simple economic tradeoff (γ = c/b), enabling models of firm incentives: how changing retraining cost, valuation of fairness improvements, or legal liability affects search intensity.
  • Useful for comparative statics: e.g., reducing retraining cost (compute) or increasing b (regulatory weight on fairness) raises optimal search depth.
• Resource allocation and efficiency
  • Empirical results suggest modest search depth often suffices; firms can avoid excessive compute and labor costs by applying the stopping rule, potentially freeing resources to explore other mitigation avenues (feature collection, alternative model classes).
• Policy design and monitoring
  • Regulators could require or recommend that firms report certificates based on this method, or require disclosure of γ and confidence levels used, improving transparency and auditability.
  • The approach gives a framework to translate qualitative legal standards (reasonable/limited burden) into quantitative stopping criteria, while preserving flexibility through user‑specified assumptions.
• Limitations and risks relevant to economics
  • Assumptions matter: method relies on iid sampling from the trainer’s randomized procedure and a bounded loss; it does not directly handle dependent sampling (e.g., MCMC chains) or strategic manipulation of the procedure A to make certificates trivial.
  • Firms could game the process (e.g., choose A to understate variability) unless regulators constrain or audit A and the held‑out evaluation protocol.
  • The method provides only an upper bound on marginal gains from retraining; it does not address other dimensions of fairness (causal sources of bias, data collection choices) that may have larger welfare implications.
• Directions for economic research and policy
  • Incorporate the stopping rule into models of firm compliance under liability and enforcement regimes to predict equilibrium investments in retraining vs. other mitigation efforts.
  • Explore regulatory standards for selecting γ and confidence levels, and for auditing A and evaluation datasets to limit manipulation.
  • Extend the framework in economic models to account for strategic behavior, dependent sample procedures, multi‑objective tradeoffs, and social welfare evaluations beyond disparate impact.