Statistical Guarantees in the Search for Less Discriminatory Algorithms
Authors: Chris Hays
Benjamin Laufer
Solon Barocas
Manish Raghavan
Venue: ICLR 2026 Poster (2026)
Keywords: fairness
anytime-valid inference
sequential decision-making
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We establish statistical guarantees for the search for less discriminatory algorithms, where model producers are required to retrain models until a fairer one is found.

Abstract: U.S. discrimination law can impose liability on firms that fail to adopt a less discriminatory alternative (LDA), defined as 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.

Published as a conference paper at ICLR 2026
STATISTICAL GUARANTEES IN THE SEARCH FOR LESS DISCRIMINATORY ALGORITHMS
Chris Hays
Ben Laufer
Solon Barocas Microsoft Research solon@microson com
Manish Raghavan MIT mragh@mit... edu
MIT
Cornell Tech
jhaysEmit.ede edu
bd156@cornel1.com edu
ABSTRACT
U.S. discrimination law can impose liability on firms that fail to adopt a less discriminatory alternative (LDA), defined 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 times encouraged proactive LDA searches, reinlorcing the expectation of good-fait effort to identify equally performant models with lower dis- parate 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 an optimal stopping problem in which developer seeks to produce ev- idence 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 attain- able 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.
INTRODUCTION
Data-driven models increasingly underpin decision making in critical domains like employ- ment, credit, and housing. While these models have been embraced for their potential to improve the quality and efficiency of such decision making, the literature on algorithmic fairness has shown that predictive models can also perpetuate exacerbate societal biases, leading to potentially unfair outcomes [Barocas et al., 2023).
Recent work argues that in such high-stakes settings, firms building data-driven decision- making systems should proactively search for "less discriminatory algorithms" (LDAs) (Black et al., 2024 Gillis et al,, 2024 Caro et al., 2024), predictive models, with equal overall performance but less disparate impact across legally protected groups These ar- guments draw on the legal doctrine that has developed over the past half century around disparate impact, which stipulates that firms may face liability if they refuse to adopt a less discriminatory alternative that could achieve their business goals as effectively as some baseline decision-making policy.
In support of their argument is the empirical finding that models optimized for accuracy can vary substantially with respect to other performance measures (like disparate impact),
II the United States, disparate impact in these sectors is typically operationalized as the differ- ence in selection rates across groups (e.g., differences in the hiring, lending, or leasing rates across racial, gender, or age groups).

---

Published as a conference paper at ICLR 2026
euen if the trmnnigg procedure used is eonctly the same (Marx et al. 2020: D' A'mour et al 2022: Rudin et all. 2024 Black et al, 2022). This is because training processes are almost always stochastic; the subset of data used to train a model, the batch ordering in stochastic gradient descent, the set of features included as inputs, and any number of other aspects of training algorithm are random. A firm might thus hope to sample large set of models with comparable predictive performance and select the one with minimal disparate impact.
Scholars, advocates, and regulators have argued that firms are well-positioned to searcch for IDAs because they oversee model training (Black et al,, 2024 LinRegLaby 2023; Blower, 2023). They have further argued that firms ought to take certain minimal steps to perform such searches, given that reductions in discrimination are a.t.aarreeetiia sometimes achievable "for free" (i.e., without sacrificing accuracy) (Islam et al. 2021; Rodolfa et al, 2021).
Others have been skeptical of the promise of LDAs, questioning whether they can really yield meaningful reductions in disparate impact and raising concerns_ahooe ahout the lengths to which firm must go to demonstrate good-faith effort (Pace, 2023; Scherer et al,, 2019). At the heart of this skepticism is the sense that a search for LDAs could potentially go on forever, given that additional searching might uncover an even less discriminatory alternative than what has been discovered already. Many modern machine learning optimization problems it is often unreasonable to identify the
involve rich function classes and are non-convex, set of global optima_ (animaaTnnnn (Tn_someeeeeeeattstttteeeeaeaelt some simpler machine learning methods or settings, however, this may be possible (Gillis et al., 2024)-) As one financial services blog put it: "no constraints or limits on this search have been proposed
and it is unclear how resource, time, and effort are expected in searching for these potential LDAs" (Pace, 2022). In this paper, we develop a framework for formalizing the concept of a sufficient search for less discriminatory algorithms in the model development process and a procedure for establishing that a firm has performed sufficintt search.
Our contributions. We develop statistical tools to quantify the value of an LDA search under model multiplicity. We formalize LDA scarch as an optimal stopping problem, wherein a firm wants to continue training models as long as the marginal gain from doing so (in disparate impact reduction) is sufficiently large. This is a natural way to model the search process: the firm will not know about the models it may train until it actually trains them; thus, they should sequentially train new models until the returns from doing so are no longer worth the model training costs. Our primary contribution is an opti stopping algorithm (Algorithm 1D and theorem (Theorem 3.5) to quantify and bound the value of continuing search for I.DAs. Our theorem provides a high-probability upper bound on the marginal value of training additional models, allowing a firm to stop an LDA search when its value is sufficiently low. Thus, our methods also provide a certificate of the limited benefits to continued search, allowing the firm to demonstrate to a third party (e.g., a court or internal compliance team) that it has conducted reasonable search. Our framework allows for the firm to impose knowledge about data and model distributions in order to furt her refine our algorithm's 's guarantees. Under stronge assumptions, we establish correspondingly stronger upper bounds on the marginal value of training additional models.
At a technical level, our algorithm establishes general high-probability guarantees for marginal returns of additional samples when sampling from an unknown distribution. We draw on recent results on anytime-valid inference, which allow us to adaptively stop train- ing models while maintaining statistical validity. In particular, we develop a novel and asymptotically near-optimal sequence upper-boundn bounding the probability of improving upon a running best sample drawn iid from any distribution, which may be of independent interest.
We also evaluate our algorithm empirically on a number of publicly available datasets related to credit and housing. We randomly retrain models across standard machine learning meth- ods and measure the stopping time of our algorithm against the optimal full-information stopping time. We find significant heterogeneity in the full-information marginal returns to retraining, and in the performance of the algorithm relative to this idealized benchmark. In all of our experiments, training small number of models models, the marginal gains in performance drop into the hundredths of a percent per new model; in several, the marginal gains were extremely small after less than 10 models trained.
enough: after about 60
2

---

Published as a conference paper at ICLR 2026
Our proposed procedure is just one piece of larger and more complex set of steps that firm might take to search for a less discriminatory algorithm. In real cases, debates about the existence of less discriminatory algorithm might cover a swath of both quantitative and qualitative copsiderations about the reasonableness of model assumptions, variables used, and so forth (Black et al. 2024).
Related work. Our work is motivated by a literalure on less Iiscriminators algorit hins, model multiplicity and lairness/accuat Lradeoffs (Black et al 2024: 2022:
Coston al 2021: Rodolfa el aly 2021 Laufer et al. 2025 Gillis et al, 2024; Cen el al. 2025; Mallah
al, 2025 Rudin al,, 2024: Dai al., 2025). This literature surfaces the idea that there
may be many highly accurate models, and that retraining models may yield predictors with
different properties, especially with respect fairness. Our work addresses an important
and unanswered question in this arca: How do we certify the sufficiency of search for a particulor model retraining process?
Our Tramework is closely related to a long literalure in economics and computer science (De Grood 2004 Beyhaghi and Cai, 2024; Lippman and McCall, 1976 Bikhchandani and Sharma, 1996). for which there are many classic applications beyond model retrainigg Our modelis is similar to the classic Pandora's Box problem (Weitzman, 1978; Kleinberg et al, 2016; BByhaghi and Cai, 2024), in which the preiiioon-maer pays cost to sample from known distribution. However, our work is different in that we assume minimal knowledge of the distributions. Also, rather than trying to maximize total utility of scarch, we seek a high-probability guarantee on the marginal returns of drawing another sample.
SETTING AND MODEL
At high level, we study the problem of learning predictive machine learning model from finite dataset. The firm's utility for predictor is determined by its average performance on loss function over the population distribution. In the search for LDAs, the loss function might be the difference in selection rates of protected group versus that of reference group.
The firm seeks to take advantage of model multiplicity to reduce this loss by sampling multiple high performing models and selecting the least discriminatory among them (i.e., the one that minimizes disparate impact). Our target is to design procedure which determines when a sufficient search has been conducted during the re-training process.
We assume the model trainer pre-specifies (1) cost for sampling an additional model by repeating a randomized training procedure and (2) a utility for a unit improvement to disparate impact. The ratio of these quantities specifies a target threshold for determining whether the marginal benefit, of retraining models is worth the cost: if the expected benefit from training new model is above the threshold, the model trainer should do so, and if it is below the threshold, the trainer should terminate the retraining procedure and deploy the best model seen so far. In the remainder of this section, we formalize this setting and define notation.
Data and utility. We will assume the existence of an unknown population distribution D from which the firm has sampled an iid dataset D of size consisting of labeled data pairs (x, X x y. The firm will deploy a predictor determines outcomes (like offers of employment, credit, or housing), y will be binary, where 1 is the positive outcome. The firm's utility will be defined as
X y. In cases where the predictor
Q(h) A E(z,y)~D [((h(x), v.z]
for l given and im(Q) S J0, B If the goal is to reduce disparity in selection rates with respect to a group indicator g(x)= E (0, 1} as in the search for LDAs, E would be written
Thii is without loss of generality: any bounded loss function can be rescaled so the loss is on 1]. Our proposed methods therefore work for loss functions beyond disparate impact; for example, firm could minimize a weighted combination of disparate impact and error rate instead of disparate impact alone.
3

---

Published as a conference paper at ICLR 2026
as (a. ((19(((1) 0) Then, the expected selection rate disparity of 0J B(h(X) (X) = 11, i.e. the
1)) (()
which is a/P(g(z) 0) if
g(x) - 0 and -a/P(g(z) = if gf) = the model would be given by (=((h==[[((() [[((() 9(X) difference between the selection rate for the reference group and the selection rate for the protected group. The loss is bounded in [0, 1] if the selection rate for the protected group (X for which g(X)= = 1) is never greater than that for the reference group (X for which g(X) = 0). This is reasonable because discrimination against the protected group is not a concern if their selection rate is higher than the reference group. 3 However, our results are not solely relevant to l as the selection rate disparity: our results hold for any outcome space }' and loss function l as long as the range of Q is bounded in [0,
The model trainer cannot observe their true utility. Instead, we will assume they have access to a finite sample of data on which they will evaluate their model. The empirical performance will be defined for a fixed dataset S, as
Q1;;5) _ S
Σ iES
Model distribution. The model trainer will have a randomized training procedure AA that takes in dataset D and returns model h. There are no assumptions on the procedure A(D), except that it is fixed in advance and returns a model iid conditional on the data D.
While we assume the model trainer has fixed dataset D, do not necessarily assume that all models are trained on the same training sample. Instead, the data may be partitioned into subsets Dirain and Diest, where h A(D) depends only on the training subset D and not on the remaining data Dest D Dtrainn, Additionally, AA is not restricted to produce models from any particular model class or setting of hyperparameters- does not need to be a standard model training process for a fixed model class. For example, A might. first randomly decide between multiple algorithms (which themselves might. be randomized), like random forests or neural networks. Alternately, A might sample from given distribution over hyperparameters.
We will analyze the setting in which model trainer trains a sequence of models h1, h2,.... by sampling iid, conditional on D, from A(D). Let Dirain Diraia.... be the sequence of training splits and Dfrst Diest ,... .... be the sequence of test splits. (Recall Dirain U Diest D for all f, so train and test splits for different steps t will have shared data.) For brevity, we will write the true and empirical loss of the 1-th model as
Q - Q(he), and Q - Q(e; D.
We will denote by P the distribution of the infinite sequence Q1. Q..... (When just considering the first entries of this sequence, we will imagine throwing the rest away so as to not introduce new notation.) We will denote by P the distribution of the infinite sequence Q1, ...... similar to P. and assume that P and P are defined on the same space. All distributions and probabilities throughout this work are taken conditional on D, since imagine there is one fixed dataset used for training and evaluation. Note that P and P are supported on (a subset of) [0, 1] since Qr, Q, [0, 1] by assumption. Also, note that {Qr) are tid, conditional on D. Let Po be the marginal distribution of any Qt- Similarly, (Q:) are iid conditional on D and we will denote the marginal distribution of any Q by Po. Finally, let PP be the joint probability distribution over the pairs (Q1, Qi)... and let Fo be the marginal distribution over any (Qr, Qt).
We will analyze the model with the best performance on the test split, after the trainer concludes training. Formally, for given i, let be the model with the lowest empirical disparate impact up to the t-th model: i = arg min Q, We will analyze the case where, after the model trainer trains models, they select and deploy hi, The true and empirical
'If selection rate disparity is a concern for both groups (L.e. both groups are protected), this loss could alternately represent the absolute value of the difference between selection rates between groups.
4

---

Published as a conference paper at ICLR 2026
disparate impact of the selected model after training & models will be denoted
Ug - Qio
and
Ü, 2 Q...
In the context of an LDA search, we assume the models sampled from A(D) are all de- ployable, in the sense that a sample from A(D) meets the business needs of the firm. this is not true for some model training process, rejection sampling can be used to continue retraining until a deployable one is found. In practice, this may be accomplished by, for example, sctting an accuracy threshold and letting A(D) be samples from the model train- ing distribution, conditional on sufficient accuracy. H This approach setting an accuracy threshold and searching for model with lower disparate impact reflects the fact that the legal framework focuses on search for alternatives among procedures that meet business needs. In other settings, beyond the LDA framework, could encode some fairness-accuracy trade-off via weighted combination of different objectives.
Certifying a sufficient search. For given cost of training a single model and utility for a unit improvement to disparate impact b, the model trainer is justified in terminating search after training r models if b Br,lU, U++1 Ü+] S c, i.e., the expected marginal benefit of training an additional model, given the observed best model so far, does not outweigh the cost. Equivalently, we will write
Ep!U, Ut+1
(1)
where we define - c/b. Our definition requires the model trainer to continue sampling models as long as the expected benefits outweigh the cost. But our information is limited in two ways: First, we do not know P. Second, we can only observe noisy estimates of Qe due to our finite data sample. Thus, we can only hope to upper bound the left-hand expression of Equation (1), with high probability over т, given this uncertainty.
Finally, we nole that, while our guarantee wrilten in terms of the marginal benefits of training a single additions model, our results hold for the marginal benefit of training & 2 additional models. This is because the marginal benefits of retraining are monotonically non- increasing in each additional model, while the costs remain linear. Thus, in our framework, there exists some k > 0 for which training & more models is worth the marginal cost, training one more model is worth the marginal cost.
3 ADAPTIVE STOPPING FOR REPEATED MODEL RETRAINING
Our main theoretical contribution is an adaptive algorithm (Algorithm D and accompanying theoretical result (Theorem 3.5). The algorithm gives a procedure for training models until stopping condition is met. The theorem establishes that, when the algorithu halts, the marginal benefits of retraining can be concluded to be no longer worth the costs. We also establish that the algorithm always halts at some finite time that depends on fy and gives data-ined inttiindeeeedennt upper bound on the number of models that need to be trained.
Our plan for the section is follows. To build intuition, in Sections 3.1 and 3.2, start with analysos of simpler settings. In Section 3.1. the distribution of model performance is known, and observations of performance are observed exactly if they were evaluated on infinite data (i.e., Q. Q. for all f). In this regime, the stopping problem trivial and can be described by a threshold on draws from the model peformance distribution. Next, in Section 3.2. we relax the first condition and do not assume full knowledge of the model performance distribution. We outline how different conditions on the model performance distribution yield different bounds, and our method allows decision-makers to input assumptions suitable to their context. Then, in Section 3.3. we handle the additional uncertainty from evaluations on finite data. To do so, we introduce a natural assumption on
"In other settings, might represent accuracy itself, in which case the search would be for more accurate models. However, our motivation for this work is clarifying the debate around LDAs. The model multiplicity literature argues that models optimized for accuracy will similar accuracy but perhaps differences in other properties (Black al. 2022: Rodolfa et al. 2021
5

---

Published as a conference paper at ICLR 2026
the relationship between observed and true model performance. In Appendix C consider the case in which estimation a property of the model loss distribution can be leveraged to produce tighter bounds marginal benefits of model retraining. All proofs are deferred to Appendix
3.1 THE FULL-INFORMATION REGIME
We first consider the simplest case, when both the distribution P is known and the popu- lation values of Q are exactly observed. For any 4, note that Ug - U++1 = (U, Q(+1) I I1U Qc+1]. Thus, if the performance of the best model so far u, the expected marginal gain of a new sample is
g(u) A Equpo 1(u - I Q.]
Observe that is weakly monotonically increasing, and g(0) = 0. Therefore, there is some threshold up at which the marginal gain drops below 7. Define this threshold follows:
up - sup {u: g(u) 57).
.E(0.)]
Thus, our stopping time satisfics the desired guarantce Equation ( if and only if
Ep, UU, U++1 u g(U+) S + U, Sup
(3)
This immediately yields a stopping condition: compute -p and sample until a value less than up. observed. The stopping time т in this case geometrically distributed, since each sample is less than up with probability Po(up 2 Ur+1), and so the expected stopping time is 1/Polup 2 U++1).
3.2 THE INFINITE- DATA REGIME
Without knowledge of P, the developer cannot compute up. We next consider the case where P unknown, but we can perfectly observe_ Q: for all t. Because of our uncertainty about P, cannot always guarantec Equation (1) for finite that the sequence {Q.).m observed so far have been abnormally large (i.c., an especially unlucky sequence), so that the expected marginal gain of a new sample is greater than 7. The best we can do is ensure that it holds with high probability, over the randomness of (Q:) That is, for a pre-specified 8 E (0, 1), we want
there is always a chance
P(Ep, [U+ U U.] S 7) P(o(U>) S 21)
(4)
where the expectation is over U/+1 marginally and the probability is over all / jointly. Our goal thus provide an anytime-val valid upper bound on {g(U)) That is, suppose we had sequence {U))), such that
E s(U)) > g. <
Then, suffices to stop sampling 7 such that g. (U+) S y, since this immediately provides a high-probability bound on g(+)).
We have thus roduced our stopping problem maintaining an anytime-valid upper bound for g(U,). Our next step is to actually construct such a bound. To do so, we decompose g(-) into two terms: One which captures the probability of observing a strictly better sample, and another which captures the expected improvement conditional on observing strictly better sample. Observe
g(u) EQ-Eo uul Polu =Q =)= p(u)p(u).
where we define, for draw of Q lid from Po, p(u) Ep, lu Q Q] and p(u) & Polu> Q) We will call μ the conditional expected improvement (CET) and p the improvement probability. It suffices to upper bound cach of these separately and then combine them.
SThis concept is closely related to to.that.of of the meon residual life of random variable, for which there is rich literature. See, e.g., Hall and Wellnen (2020).

---

Published as a conference paper at ICLR 2026
Bounding μ.. We first formalize our goal for bounds μ. We will then provide explicit bounds under a variety potential assumptions on the distribution. The definition is written for generic distribution P since we will reuse this definition later in the finite-data case.
Definition 3.1 (ū-Bounded CEI for P). f [0, + [0, 1] is CEI bound for distribution
P if
EQup (u Q Q p(u)
for all u e [0, 1], almost surely.
We can use the fact that P is supported on [0, 1] almost surely to derive an immediate bound satisfying Definition 3.1: Equp/u Q u > Q] I u, since Q 2 0. Thus, f juniversal (u) -
satisfies Definition 3.1, making it valid upper bound for μr.
This bound is quite conservative, since it bounds expected improvement by maximum possible improvement. In Appendix B. we provide series of assumption Pa under which we can derive tigher bounds j satisfying Definition 3.1.
Bounding p. Having provided bounds for μ, we next turn the problem of bounding p. The following lemma yields a general anytime-valid high probability upper bound for the probability of observing new minimum in sequence of iid random variables. We state the lemma for a general sequence of random variables because it may be of independent interest. Informally, the lemma establishes sequence Pt, depending on confidence budget a, such that with probability at least 1 far among sequence of iid random variables. The bound is anylime-valid valid because it holds for all time steps rather than traditional bound, which would hold for some t fixed in advance. An asymptotically near-optimal (but more complex) sequence can be found in Theorem E.
is greater than the minimum value seen so
Lemma 3.2. Let {x,];- be a sequence of iid random variables distributed according law Po- Let A Pp be their joint distribution. Let Y, the minimum of these variables up to time t, i.e., Ye mingee Xs. For any a (0, define an upper bound
1 ---e-he -1/a
ift
p.())=
(1-1) +1)+++
1/(-11
otherwise.
Then, the probability over Po that X141 is less than Y, at any time is bounded by Pr(a) with probability 1 over P. Formally,
P(BtEN: Po(X++1 Y, Y, > pr(o)) aa
We note that the high probability bound is conditional on Y,, reflecting the fact that stopping procedure may depend on the minimum seen so far. This stands in contrast with an unconditional bound, which could not depend the data seen far and would not be relevant to a Drcisiionmmken deciding whether to stop at time t or not, having seen the data up to time t. Lemma 3.2 yields immediate anytime-valid upper bound on {r(U.)):
P(tteN: p(U)) > p.())) S
(5)
Combining bounds. Our algorithm simply combines our bounds on f and p to maintain an anytime-valid upper bound on the marginal gain, given by ju(U)) (e()). Formally, our algorithm simply terminates at the first t such that P. (U(U)) P- (6) < y. Moreover, 7 is guaranteed to be finite because (+(()) < for all f, and lim (.) 0. A data-indepenndent upper bound on the maximum possible number models trained by our algorithm can thus be directly computed from 8 and y by finding the smallest such that pr(0) 7. We state the algorithm for a generic distribution P given as input, rather than Po, since we will reuse this algorithm in the finite-data regime.

---

Published as a conference paper at ICLR 2026
Algorithm 1 LDA Search with Adaptive Stopping
input:
An unknown model performance distribution P from which to draw iid samples. Stopping threshold y and failure probability
Optional: An almost-sure expected conditional improvement bound z satisfying Defini- lion 3.1 If not provided, use ja puniversal (u) = u.
1: for 1,2,... do
2: Draw new sample X
iid
P.
3: Define Pt in Lemma
3.2
4: Define Y = minggt X
5: if p(Y;) Pc(5) < then
6: return Y;
7: end if
8: end for
We now state the formal statistical guarantee for our infinite data setting, It is a special case of more general theorem we prove, Theorem D.1
Proposition 3.3. For all 7,
8 > 0, Algorithm run with Po, y. and any p that satisfies Definition 3.1 for Po as input terminates at stopping time t E N such that
P(EplU, - U U-] < 7) 2-
Next, we generalize to the case where we have finite data.
3.3 THE FINITE-DATA REGIME
we observe only finite data, we cannot perfectly observe each Qr; instead, we observe Q-- As before, we will seek to maintain anytime-valid upper bound on the marginal gain. We must take care to define the marginal gain appropriately in particular, our goal is to bound the expected marginal gain with respect to the true disparate impact (Qi), given observations of empirical disparate impact (Q:). Formally, our goal is to show that, at stopping time т,
E - Ur+1 Ú+)57-
where the expectation is also conditional on D. To do this, need to establish relation between the measurement error U, - at different points on the left tail of Po. We provide a natural assumption on the relationship between these quantities: the selection effect or prtression-tttth-meenn effect is, in expectation, non-decreasing in t. The assumption that regression-tee to- tee-tteeeeeeee is at least constant is henpuentlyssupposee in the large literature. on aactuustingaaaallle for or estimating these effects (Stein atl 1956 James _tlallll al, 1961 Sorepson and Kennedy, 1984; Andrews et al., 2024: Zrnic and Fithian 2024: Fithian et al, 2014). Intuitively, this assumption holds for Sub-Gaussian left tails where the selection effect should be linear in the gap between Úr and Ü.+1 and even for sub-exponential left tails whore there should be constant regression to the mcan in the gap between Ú, and Ūz+1- This assumption would not hold if some measurable set of values of Ù, indicate that the model has low disparate impact, while models with Ü.+1 < U, have relatively high disparate impact.
Assumption 3.4 (Non-decreasing selection effect). It holds for all t that
Ep!U, - Ú. Üt] Ep[U++1 - Ú2+1 Üt).
Under Assumption 3.4 we can apply Algorithm I on the sequence {ū,};= exactly the same as to how we applied it to {U,) in the infinite data case. This additional assumption is sufficient for the following theorem to hold, using only a minor modification to the argument applied in the infinite data case.
8

---

Published as a conference paper at ICLR 2026
Theorem 3.5. Under Assumption 3.4 for all 2 > and 8 0, Algorithm M run with P = Po, 7,6 and any j that satisfies Definition 3.1 for Po terminates at time T N such that
P(ErUU, U741 U 1
(6)
In Appendix + we extend our results to analyze the case which the mean residual life can be estimated from data, under an additional assumption on the distribution Po.
EMPIRICAL ANALYSIS
In this section, we evaluate our method on several datasets and machine leaanig Jearning.methootee The datasets we use are Adult (Becker and Kohavi, 1996), Folktables (Ding et alj. 2021). and HMDA (CFPB, 2017). The methods we use are logistic regression, random forests and gradient boosted trees. In Appendix A we also evaluate how well our approach composes with fairness-aware machine learning methods like Fairlearn Weerts et al, (2023). To eval- uate our algorithm, we would wouldideally compare its performance against the full-infornation regime discussed in Section 3.1, where we perfectly observe the marginal benefit of sampling new model. This is in general not possible, since we know neither the true data distribution nor the true distribution of model disparate impacts, Instead, we treat the finite dataset as a "population distribution" and subsample to produce training and testing datasels Full details of our data cleaning and feature feature/outcome /outcome selection are available in Appendix A and in our code at betps://githin conn///nc/orrrrrreoeoo.oeococc wwwnchiishaass/leea..
com/
A precondition for there to be any benefit to model retraining is variation in disparate impact. In Figure 3 we show there is significant variation disparate impact among models: on several datasets and methods, there is about 20% spread between the highest and lowest disparate impact observed. Having established the variation in disparate impact, we next evaluate Algorithm I. To do this, we track (1) the true marginal benefit of continued search (as computed from our "population distribution"), and (2) the upper bound given by the algorithm. For a fixed 7, we are primarily interested in algorithm's 's stopping time particularly as it compares to the time at which the true, full-information marginal gain drops below 7.
The results of running the algorithm many times for each Po are visualized in Figure Iterations of the algorithm are on the horizontal axis and the marginal gain from resam- pling (using a logarithmic scale) is on the vertical axis. The pink line is our upper bound (()))p:()) for 8 = 0.05, setting p(Ú.)) = Úū; we place no assumptions on the distribution Po. The brown line the ground truth g(,). The shaded colored regions for each line show standard deviations over multiple runs of the dataset resampling, model training and algorithm.
For any Amm would stop when the pink line drops below the horizontal line at 7. Given full distributional information, a model trainer should stop the retraining process once the brown line drops below the horizontal line at 7. Thus, for any fixed the average number of iterations that the algorithm trained models past the stopping time given full information is the horizontal distance between the brown and pink lines. Empirically, Algorithm I performs well in the sense that it. "overshoots" the correct stopping time by tens of models in general, though it appears to perform worse for logistic regression on all datasets and all methods on HMDA. Further assumptions (i.e., A1 A2 A3) will likely yield tighter bounds. We note that each vertical axis is on logarithmic scale.
We also implemented Algorithm in the same setting. The corresponding visualization of the results is displayed in Figure and discussed in Appendix A Finally, we repeat our our analysis implementing a popular fair machine learning framework Fairlearn (Weerts al, 2023). We display the results in Figure and discuss these in Appendix A.
9

---

Published as a conference paper at ICLR 2026
Upper board (R10)-M68)
Full Infon (s:
Aeat
Fobtablo
HMEA
Lagas Dlpaada
fooet
Morginal Gare
Guller Searnd
Figure 1: Algorithm run on several datasets and models. Panel rows are ML methods and panel columns are datasets. In each panel, the horizontal axis is the iteration of the algorithm and the vertical axis is marginal gain. The pink line our estimated upper bound natz (. (0.05) and the brown line is the full-information marginal gain. For any % ! would stop when the pink line crosses the horizontal line at 7. Note that the vertical axis is on a logarithmic scale, so a shallow downward sloping line reflects polynomial decrease in the displayed quantity.
Algorithm
DISCUSSION
Although recent work has proposed that firms should take steps to proactively search for less discriminatory algorithms, there are a number of open questions regarding both the gains be expected from an LDA search and the resources required conduct one. In this paper we take one step towards developing the tooling firms would need to conduct search. We put forward method that allows firms to adaptively sample models that come from a particular loss distribution. Our algorithm adaptively bounds the marginal gains of a continued search, allowing a firm to terminate the search when the gains are small and provide evidence that their search was sufficient.
We take as given the developer's cost of training models relative to their value of reducing disparate impact. While determining how firm might determine this cost is beyond the scope this work, is the subject of ongoing debate (Pace,, 2022: Black et al., 2024). Case law suggests that courts may reject less discriminatory alternatives that impose too great cost on defendants, but that they are also willing to endorse alternatives that are far from costless Black et al (2024). Our framework help contribute to this debate in at least two ways. First, because we provide anytime-valid bounds, we do not require that a firm pre-specify cost. Instead, model developers and compliance leams can iteratively develop models, consider the incremental gains, run separate experiments, and adaptively decide how to value those gains relative to development costs. Second, given a search conducted by a firm, our framework allows us to "back out" high-probabilin upper bound on the firm's estimated cost implied by their decision to stop the search. That is, by observing sequence of models sampled by a developer, we can draw conclusions about their implicit value for reducing disparate impact from their decision to terminate a search, and thereby facilitate more informed debate about the reasonableness of the search.
number of future directions related to this setting are open, especially related to adaptive searches, where the performance of previous models influences the distribution of the next models trained. Additionally, applying our general framework to other settings beyond the search for LDAs is fruitful direction for future work.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Andrews, T., Kitagawa, T., and McCloskey, A. (2024). Inference on Winners. The Quarterly Journal of Economies, (39(5))305-33) 358.
Barocas, S., Hardt, M., and Narayanan, A. (2023). Fairness and Machine Learning: Limi- tations and Opportunáties, MIT press.
Becker, B. and Kohavi, R. (1996). Adult. UCI Machine Learning Repository. DOL: https://bbi.org/ http://oiior/100.445.3333 10.24433/C5XX2222
Beyhaghi, H. and Cai, L. (2024). Recent Developments in Pandora's Box Problem: Variants and Applications. ACM SIGecom Erchanges, 21(1):20-34
Bikhchandani, S. and Sharma, S. (1996). Optimal Search with Learning. Journal of Eco- nomic Dynamics and Control, 20(1-3):335 359.
Black, E., Koepke, J. L.,, Kim, P. T., Barocas, S., and Hsu, M. (2024). Less Discriminatory Algorithms. Geo. LJ, 113:53.
Black, E., Raghavan, M., and Barocas, S. (2022). Model Multiplicity: Opportunities, Con- cerns, and Solutions. In Proceedings of the 2022 ACM Conference Fairness, Account- ability, and Trunsparency, pages 550-863
Blower, B. (2023). CFPB Puts Lenders & FinTeecss On Notice: Their Models Must Search For Less Discriminatory Alternatives Or Face Fair Lending Non- Non-Compliance Risk. Section: Views.
Caro, S., Gillis, T. B., and Nelson, S. (2024). Modernizing Fair Lending, University of Chicago, Becker Friedman Institute for Economics Working Paper, (2024-18).
Cen, S. H., Goyal, S., Javed, Z., Karthik, A., Liang, P., and Ho, D. E. (2025). Audits Under Resource, Data, and Access Constraints: Scaling Laws For Loss Discriminatory Alternatives. In Proceedings of the 39th Conference on Neural Information Processing Systems. arXiv:2509.0560 [es].
CFPB (2017). Home Mortgage Disclosure Act Data. United States Government.
Cooper, A. F., Lee, K., Choksi, M. 7., Barocas, S., De Sa, C., Grimmelmann, J., Kleinberg, J., Sen, S., and Zhang, B. (2024). Arbitrariness and Social Prediction: The Confounding Role of Variance in Fair Classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 22004-22013
Coston, A., Rambachan, A., and Chouldechova, A. (2021). Characterizing Fairness Over the Set of Good Models Under Selective Labels. In Proceedings of the 38th International Conference on Machine Learning, pages 2144 2155. PMLR.
Dai, G., Ravishankar, P., Yuan, R., Black, E., and Neill, D. B. (2025). Be Intentional About Fairness!: Fairness, Size, and Multiplicity in the Rashomon Set. In Proceedings of the 5th ACM Conference on Equity and Access in Algorithums, Mechanisms, and Optimization, EAAMO '25, page 42 73, New York, NY, USA. Association for Computing Machinery.
D' D'Amour, A., Heller, K., Moldovan, D., Adlam, B., Alipanahi, B., Beutel, A., Chen, C.,, Deaton, J., Fisenstein, J., Hoffman, M. D., et al. (2022). Underspecification Presents Challenges for Credibility in Modern Machine Learning. Journal of Machine Learning Research, 23(226):1-6 61.
DeGroot, M. H. (2004). Oplimal Slopping, pages 324 324-384. John Wiley & Sons, Ltd.
Ding, F., Hardt, M., Miller, J., and Schmidt,, L. (2021). Retiring Adult: New Datasets for Fair Machine Learning. Advances in Neural Information Processing Systems, 34.
Fallah, A., Jordan, M. I., and Ulichncy, A. S. (2025). The Statistical Fairness-Accuracy Frontier. In NeurIPS 2025 Workshop: Reliable ML from Unreliable Data.
11

---

Published as a conference paper at ICLR 2026
FinRegLab (2023). Machine Learning Explainability & Fairness: Insights from Consumer Lending. Empirical white paper, FinRegLab. Updated July 2023.
FinRegLab (2025). Advancing the Credit Ecosystem: Machine Learning & Cash Flow Data in Consumer Underwriting. Empirical white paper, FinRegLab.
Fithian, W., Sun, D., and Taylor, J. (2014). Optimal Inference after Model Selection. arXiv preprint 14Xiv:1400 10.222977
Gillis, T. B., Meursault, V., and Ustun, B. (2024). Operationalizing the Search for Less Discriminatory Alternatives in Fair Lending. In The 2024 ACM Conference on Fairness, Accountability, and Transporency, pages 377-387, Rio de Janeiro Brazil. ACM.
Hall, W. J. and Wellner, J. A. (2020). Estimation of Mean Residual Life. In Almudevar, A., Oakes, D., and Hall, J., editors, Statistical Modeling for Biological Systems, pages 169 189. Springer International Publishing, Cham.
Islam, R., Pan, S., and Foulds, R. (2021). Can We Obtain Fairness For Free? In Proceedings of the 2021 AAAT/ACM Conference on AI, Ethics, and Sociely, pages 586 596, Virtual Event USA. ACM.
James, W., Stein, C., et al. (1961). Estimation with Quadratic Loss. In Proceedings of the 4th Berkeley Symposium Mathematical Statistics and Probability, volume 1, pages 361-379. University of California Press.
Kleinberg, R., Waggoner, B., and Weyl, E. G. (2016). Descending Price Optimally Coordi- nates Search. In Proceedings of the 2016 ACM Conference on Economics and Computa- tion, EC '16, page 23- 23-24, New York, NY, USA. Association for Computing Machinery.
Laufer, B., Raghavan, M., and Barocas, S. (2025). What constitutes a less discriminatory algorithm? In Proceedings of the 2025 Symposium on Computer Science and Law, pages 136-151.
Lippman, S. A. and McCall, J. (1976). The Economics of Job Search: A Survey. Economic Inquiry, 14(2):155 189.
Marx, C., Calmon, F., and Ustun, B. (2020). Predictive Multiplicity in Classification, In Proceedings of the 37th International Conference on Machine Learning, pages 6765-6774. PMLR.
Pace, R. (2022). Six Unanswered Fair Lending Questions Hindering Al Credit Model Adoption.
Lix-unanswered-fair -ed lending-guestions
Pace, R. (2023). Fool's Gold 2: Is There Really Low-Cost Accuracy-Pairness Trade-off?
The Al LendScape Blog.
Robbins, H. (1970). Statistical Methods Related to the Law of the Iterated Logarithm. The Annals of Mathemalical Statistics, (5):133377-144 1409.
Robbins, H. and Siegmund, D. (1972). On the Law of the Iterated Logarithm for Maxima and Minima. Proc. Sirth Berkely Sympostum Mathematical Statistics and Probability, 3:51-70.
Rodolfa, K. T., Lamba, H., and Ghani, R. (2021). Empirical Observation of Negligible Fairness Accuracy Trade-offs in Machine Learning for Public Policy. Nature Machine Intelligence, 3(10):896-90)
Rudin, C., Zhong, C., Semenova, L.., Seltzer, M., Parr, R., Liu, J., Katta, S., Donnelly, J., Chen, H., and Boner, Z. (2024). Position: Amazing Things Come From Having Many Good Models. In Proceedings of the 41tt International Conference Machine Learning, pages 42783-42795.
12

---

Published as a conference paper at ICLR 2026
Scherer, M. U., King, A. G., and Mrkonich, M. J. (2019). Applying Old Rules to New Tools: Employment Discrimination Law the Age Algorithms. SCL Rev., 71:449.
Shorack, G. R. (2000). Probability for Statisticians. Springer.
Sorensen, D. and Kemnedy, B. (1984). Estimation of Response to Selection using Least- squares and Mixed Model Methodology. Journal of Animal Science, 5865):1097-1106.
Stein, C. el al. (1956). Inadmissibility of the Usual Estimator for the Mean of Multivariale Normal Distribution. In Proceedings of the Third Berkeley Symposium Mathematical Statistics and Probability, volume 1, pages 197-206.
Waudby-Smithh I. and Ramdas, A. (2024). Estimating Means of Bounded Random Variables by Betting. Journal of the Royal Slatistical Sociely Series B: Slatistical Melhodology, 86(1):1-27.
Weerts, H., Dudik, M., Edgar, R., Jalali, A., Lutz, R., and Madaio, M. (2023). Fairlearm: Assessing and Improving Fairness AT Systems.
Weitzman, M. (1978). Optimal Search for the Best Alternative, volume 78, Department of Energy.
Zrnic, T. and Fithian, W. (2024). A Flexible Defense Against the Winner's Curse. arXi::241..18669 [stat].
13


Reviews:
[{"review_id": "9vb7uZfPKs", "reviewer": "Reviewer_bHC9", "summary": "The paper proposes a statistical criterion to determine when to stop training (sampling) models on a finite dataset while trying to minimize a quantity of interest. The main statistical guarantee is that the algorithm will stop at a point where training an additional model will unlikely lead to an improvement. The paper focuses mainly on fairness metrics, but the approach is in theory applicable to any quantity of interest that is averaged over the test set e.g. model performance.", "questions": "In Equation 1, shouldn't the expectation be $\\mathbb{E}\\_{\\mathbb{P}\\_0\\times \\mathbb{P}\\_0}[U\\_{\\tau} - U\\_{\\tau+1} | \\widehat{U}\\_{\\tau}]$? This is because $\\mathbb{P}_0$ is the marginal distribution of a single pair $(\\widehat{U}, U)$, while in Equation 1 involves two pairs $(\\widehat{U}\\_{\\tau}, U\\_{\\tau})$ and $(\\widehat{U}\\_{\\tau + 1}, U\\_{\\tau+1})$? I assume that $U\\_{\\tau}$ remains a random variable when we condition on $\\widehat{U}\\_{\\tau}$?\n\nThe theorems bound the expected improvement resulting from training **one** additional model. But let's assume that I can train $B$ models in parallel with no additional costs. How easy would it be to extend the theorems to bound the expected improvement from training $B$ additional models? Would it be as simple as applying a union bound? Maybe it is possible to do better than that, since the union bound will become artificially loose at $B$ increases?\n\nThe datasets used in the experiments are quite large. Would the approach provide a good coverage on smaller datasets e.g. COMPAS?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very easy to follow, despite containing a lot of theory. To accomplish this, the manuscript starts from an ideal scenario :known population risk $Q$ and known marginal distribution of said risk $P_0$. Then each assumption is subsequently relaxed. First, acknowledging that $P_0$ is unknown means that we must find an upper bound on expected improvement that holds with high probability. Further relaxing our knowledge of $Q$ to that of its empirical counterpart $\\widehat{Q}$ is then explained to derive the final form of the algorithm. Structuring the paper this way is very pedagogical and helps the reader understand each step of the derivation.\n\nThe algorithm is well motivated based on Theorem 3.5. \n\nThe correctness of the algorithm is demonstrated empirically on three datasets and model types.", "weaknesses": "## Extending Experiments\n\nWhile the presented experiments highlight that the algorithm is correct (the upper bounds holds with probability at least 95% in general), they could be extended to highlight interesting trade-offs and other applications beyond fairness.\n\nFor instance, the appendix presents Algorithm 2 as an alternative that uses of subset of the trained models to estimate the upper bound in conditional expected improvement $\\overline{\\mu}$. However, the tightness of this algorithm is not compared empirically with Algorithm 1. There might be interesting trade-offs between algorithms 1 and 2 in terms of number of model trainings required for the bounds to go below $\\gamma$. Algorithm 2 has a tighter $\\overline{\\mu}$ but it requires separate samples to first compute the quantile $C$ and the bound $\\overline{p}_t(\\delta/3)$ is looser because of the union bound. Consequently, it would be pertinent to add Algorithm 2 to Figure 1.\n\nAnother way the experiments could be extended is to apply Algorithm 1 to another use-case. For example, I think it is perfectly applicable to hyperparameter optimization via random search. Applying Algorithm 1 to find the hyperparameters of the Random Forests and MLP used in the experiments would highlight the versatility of the method. To avoid diluting the main message of the paper (which is about less discriminative alternatives), these additional experiments could be placed in a dedicated appendix.\n\n\n## More details on Assumption 3.4\n\nAssumption 3.4 is the key to replace population risk $Q$ with the empirical risk $\\widehat{Q}$ in the algorithm. While this assumption is motivated by citing the existing literature, it would be better to assess whether it holds in the experiments. This should be doable since the experiments are designed so that population distributions are known. \n\nFigure 4 shows that mis-coverage is higher for more expressive models (RFs and MLPs). It would be interesting to see if assumption 3.4 is indeed less likely to hold for these models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bmL60DIWd6", "reviewer": "Reviewer_evA5", "summary": "The paper formalizes the search for less discriminatory algorithms (LDAs) as an optimal stopping problem grounded in the context of model multiplicity and fairness-aware model selection. It proposes an adaptive stopping algorithm (Algorithm 1) that provides a high-probability upper bound on the marginal benefit of retraining models, effectively giving a statistical “certificate” for when a firm can reasonably stop searching for fairer models. The theoretical framework integrates ideas from anytime-valid inference and optimal stopping theory, establishing guarantees that the expected marginal gain from retraining is below a user-specified threshold. Empirical evaluations on three fairness-sensitive datasets (Adult, Folktables, HMDA) and multiple model classes (logistic regression, random forests, neural networks) demonstrate the method’s ability to approximate the optimal stopping point with reasonable accuracy. The discussion highlights implications for algorithmic fairness compliance, proposing the approach as a tool to certify “good-faith” searches for LDAs in high-stakes domains.", "questions": "1. How sensitive is the stopping time to violations of Assumption 3.4 (non-decreasing selection effect)? Would the algorithm’s guarantees degrade gracefully under mild violations?\n\n2. Could the method be extended to handle adaptive retraining (where the next model’s training depends on previous outcomes), which is common in fairness optimization pipelines?\n\n3. How should practitioners select or validate the threshold γ in regulatory or organizational contexts?\n\n4. Would the method still provide valid guarantees if retraining involved data reweighting or feature modification, rather than randomness in initialization or batch ordering?\n\n5. How does the choice of fairness metric influence the stopping behavior and the empirical coverage rates?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- Theoretical novelty: The framing of LDA search as an optimal stopping problem is original and mathematically sound. The derivation of anytime-valid upper bounds for marginal gains extends prior work in statistical inference and stopping theory.\n\n- Practical relevance: The work connects theoretical constructs to regulatory and compliance debates in algorithmic fairness, addressing a pressing question of how firms can demonstrate sufficient fairness efforts.\n\n- Methodological rigor: The paper clearly delineates three regimes (full-information, infinite-data, finite-data) and progressively builds the theoretical results with appropriate assumptions and proofs.\n\n- Statistical guarantees: The introduction of an adaptive, distribution-agnostic stopping rule that provides high-probability bounds strengthens the method’s interpretability and generality.\n\n- Empirical validation: The experimental section, while modest, is well aligned with the theoretical claims. The algorithm’s overshoot relative to the full-information optimum provides empirical evidence for its reliability.", "weaknesses": "- Limited empirical scope: The empirical evaluation, though methodologically correct, uses small-scale settings with standard datasets. There is limited evidence of robustness in larger or more complex model retraining pipelines.\n\n- Assumption strength: Several theoretical results depend on distributional assumptions that may not hold in realistic ML training scenarios with non-iid retraining or adaptive hyperparameter tuning.\n\n- Connection to fairness metrics: While the framework generalizes beyond disparate impact, the empirical focus remains narrow. It does not analyze whether the stopping rule’s behavior changes under alternative fairness definitions (e.g., equal opportunity, demographic parity).\n\n- Practical deployment considerations: The paper lacks discussion of computational cost, reproducibility challenges, and real-world compliance integration.\n\n- Clarity of exposition: The writing is dense in the theoretical sections (e.g., Section 3) and could better motivate the intuition behind the derived bounds for a mixed audience of ML and applied fairness researchers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DOc80wbH5L", "reviewer": "Reviewer_gjyJ", "summary": "The paper formalizes the practice of retraining to find less discriminatory algorithms (LDAs), models with comparable utility but reduced disparate impact, by casting it as an optimal-stopping problem. Given model multiplicity, the authors define a decision rule: stop retraining once the expected marginal improvement in disparity from training one more model falls below a cost/benefit threshold. \nThey provide an adaptive stopping algorithm with anytime-valid, high-probability upper bounds on the marginal improvement, so that when the algorithm halts, one can certify that continued search is unlikely to pay off. Empirical studies are conducted to validate the method.", "questions": "Please see the weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Turning “good-faith LDA search” into an auditable optimal-stopping problem with an explicit threshold $\\gamma$ is a nice formulation. The adaptive rule provides high-probability upper bounds on the marginal gain from one more retrain, enabling a certificate that a search was “sufficient” at the data-dependent stopping time. The paper motivates the problem clearly, is well-written, and easy to follow.", "weaknesses": "1. **Bounding $\\mu$ in Section 3.2.**  \n   The paper presents several upper bounds on \\( \\mu(u) \\) under different assumptions on the underlying density. It is not immediately clear how conservative these bounds are in practice. Could the authors comment on the **tightness** of these bounds (e.g., instances where they are known to be sharp vs. loose), and perhaps provide empirical or theoretical comparisons across the proposed choices?\n\n2. **Online learning formulation (infinite-data regime).**  \n   Consider the infinite-data setting where we observe i.i.d. $Q_t$ exactly but $P$ is unknown. Can we estimate $u_p^\\star$ in a data-driven way at each round? For example, at round $t$ define $$ \\hat g(u) = \\frac{1}{t}\\sum_{j=1}^t (u - Q_j){1}\\{u>Q_j\\},$$\n   and set $\\hat u_p = \\sup_{u\\in[0,1]} \\hat g(u) \\le \\gamma$. One could update $hat g$ each round (or every few rounds) and stop when $U_\\tau \\le \\hat u_p$. Would this constitute a **valid** approach within your framework, and under what conditions (if any) would it inherit your guarantees?\n\n3. **Assumption 3.4.**  \n   The intuition for Assumption 3.4 is not fully clear, particularly why it should hold for **any** $P$ and **any** $\\hat P$? What is meant precisely by “regression to the mean is at least constant”? A more natural route might be to index the assumption by **sample size**, yielding an explicit bound between $P$ and $\\hat P$ that vanishes as $n \\to \\infty$. Could the authors either (i) give **verifiable sufficient conditions** ensuring Assumption 3.4 under common validation-reuse protocols, or (ii) reformulate it in a sample-size–dependent way that makes its asymptotic validity transparent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FLxcUsUwWo", "reviewer": "Reviewer_TPVF", "summary": "This paper seeks to give anytime-valid bounds on the expected marginal utility of randomly training an additional model in search of a Least Discriminatory Algorithm. The paper is organized in three levels of generality -- first, the authors tackle the full-information regime where the distribution and the population utilities are known. Then, the authors generalize their results, with high probability and under various assumptions, to unknown model sampling distributions. Finally, the authors generalize the results to finite data with an additional assumption that the 'selection effect' (the measurement error conditioned on the current empirical disparate impact) does not decrease with additional training runs.", "questions": "1. How would a model developer determine which of the assumptions would be suitable for their data? How could they defend that choice to a judge or regulator?\n\n2. The bounds on the ground truth in the experiment are very wide -- is it plausible to run the same experiment on a synthetic distribution with a known ground truth?\n\n3. At the end of section 4, you state that, \"Empirically, Algorithm 1 performs well in the sense that it \"overshoots\"... by tens of models...\" How can I see this relationship from the plots? Is this by drawing a horizontal line from each point on the brown curve to the right until it touches the pink curve? \n\n4. Techniques exist in the literature to find a diverse set of models of a particular model class without randomized re-training. Some examples include the Rashomon set of decision trees, a sampling of the Rashomon set of XGBoost models, and a sampling of the Rashomon set using dropout in neural networks. What makes your approach desirable over these methods, which are more likely to directly find an LDA instead of randomly training and hoping for one?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper has a clear and precise motivation and framing of results. \n\n2. The paper's organization as a gradual movement towards generality, with some additional thoroughly explained assumptions, made the paper very easy to read and understand.\n\n3. I do not have the expertise to know whether the proposed bounds on the probability of sampling a new minimum value of a random variable are significant, but to this reviewer they are interesting and potentially useful.\n\n4. I am convinced that the proposed bounding approach and algorithm can be useful to firms seeking to meet regulatory requirements (which may not yet exist) around finding LDAs, supposing that their training procedures are capable of finding satisfactory models.", "weaknesses": "1. Relating to strength #4, I am unconvinced that knowledge that a firm satisfied a strong bound using the provided approaches would actually certify anything of value to a regulator or a court. It is entirely plausible that a firm could have an algorithm A that either is not sufficiently random, or is biased in some way (neither necessarily intentionally), so as to yield models which are very discriminatory, even when a non-discriminatory model may exist. Using the above approach could inadvertently allow a firm to certify that they had sufficiently searched for LDAs when in fact they hadn't.\n\n2. Although the additional assumptions in the theorems are well-described, I am not left with a sense of whether or not they are plausible in real data distributions. \n\n3. Relating to weakness #2, I think that additional experiments including the tightened bounds using assumptions A1-A3 would be useful to the paper. As it stands, it is difficult to determine how much those additional assumptions help beyond allowing smaller values of $\\bar{\\mu}$ in the algorithm.\n\n4. I think the experiments would benefit from many more iterations than the 60 plotted. Also, the starting values of both bounds at iteration 0 seem very small -- is there really such tiny expected marginal utility in training another model, even after only training a single model?\n\n5. This is neither a weakness nor a strength, so I am putting it last. The framing of the paper as a search for LDAs does not capture the full generality of the results. As the authors suggest, the results apply to any loss function and to any repeated (randomized) model fitting procedure. The search for LDAs is one potential application of these methods, but I feel that this could have been emphasized adjacent to other potential applications instead of as the main thrust of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)