Statistical Guarantees in the Search for Less Discriminatory Algorithms

The paper formalizes the search for less discriminatory algorithms as an optimal stopping problem, proposing an adaptive algorithm that provides high-probability upper bounds on achievable fairness gains from continued retraining. It resides in the Statistical Certification and Model Multiplicity Analysis leaf under Fairness Evaluation and Testing Methodologies, where it is currently the sole occupant. This placement reflects a relatively sparse research direction focused on formal verification of fairness properties across multiple model instantiations, contrasting with the more crowded intervention-focused branches like Fairness-Aware Training (15 papers across four leaves) and Data-Centric Bias Mitigation (4 papers across two leaves).

The taxonomy reveals that most fairness research concentrates on intervention techniques—adversarial training, reweighting strategies, and data augmentation—rather than post-hoc certification. The paper's neighboring branches include Adversarial and Automated Fairness Testing (1 paper) and Procedural and Explainability-Based Fairness Assessment (1 paper), both emphasizing empirical robustness checks rather than statistical guarantees. While Fairness-Aware Training branches develop methods to embed fairness constraints during learning, this work addresses the complementary question of certifying whether retraining efforts have sufficiently explored the model space, bridging evaluation methodologies with the retraining practices documented in adjacent intervention categories.

Among 17 candidates examined, the adaptive stopping algorithm contribution shows one refutable candidate among 10 examined, suggesting some overlap with prior work on stopping criteria or bound estimation. The formalization of LDA search as an optimal stopping problem (1 candidate examined, 0 refutable) and the distributional assumptions framework (6 candidates examined, 0 refutable) appear more distinctive within this limited search scope. The relatively small candidate pool reflects the sparse literature on statistical certification approaches compared to the broader fairness intervention landscape, though the single refutation for the stopping algorithm indicates that elements of the technical approach may have precedent in related optimization or sequential decision-making contexts.

Based on top-17 semantic matches, the work appears to occupy a genuinely underexplored niche at the intersection of model multiplicity analysis and fairness certification. The limited search scope means we cannot rule out relevant work in adjacent fields like sequential experimentation or multi-armed bandits that might inform the stopping problem formulation. The taxonomy structure suggests this certification perspective is less developed than intervention techniques, though the single sibling-less leaf position may partly reflect taxonomy granularity rather than absolute novelty.