Auditing Fairness by Betting
Authors: Ben Chugg
Santiago Cortes-Gomez
Bryan Wilder
Aaditya Ramdas
Venue: NeurIPS 2023 spotlight (2023)
Keywords: fairness
auditing
sequential analysis
martingales
testing by betting
TL;DR: We provide efficient methods to sequentially audit the fairness of models which handle continuous monitoring of data, randomized data collection policies, and distribution shift.

Abstract: We provide practical, efficient, and nonparametric methods for auditing the fairness of deployed classification and regression models. Whereas previous work relies on a fixed-sample size, our methods are sequential and allow for the continuous monitoring of incoming data, making them highly amenable to tracking the fairness of real-world systems. We also allow the data to be collected by a  probabilistic policy as opposed to sampled uniformly from the population. This enables auditing to be conducted on data gathered for another purpose. Moreover, this policy may change over time and different policies may be used on different subpopulations. Finally, our methods can handle distribution shift resulting from either changes to the model or changes in the underlying population. Our approach is based on recent progress in anytime-valid inference and game-theoretic statistics---the ``testing by betting'' framework in particular. These connections ensure that our methods are interpretable, fast, and easy to implement. We demonstrate the efficacy of our approach on three benchmark fairness datasets.

Auditing Fairness by Betting
Ben Chugg', Santiago Cortes-Gomez', Bryan Wilder', Aaditya Ramdas 1.2 Departments of Machine Learning' and Statistics? Carnegie Mellon University
(benchugg, acortesg, bwilder, aramdas] @cmm. edu
Abstract
We provide practical, efficient, and nonparametric methods for auditing the fairess of deployed classification and regression models. Whereas previous work relies on a tixelsample size, our methods are sequential and allow for the continuous monitoring of incoming data, making them highly amenable tracking the fairness of real-world systems. We also allow the data to be collected by probabilistic policy as opposed sampled uniformly from the population. This enables auditing to be conducted on data gathered for another purpose. Moreover, this policy may change over time and different policies may be used on different subpopulations. Finally, our methods can handle distribution shift resulting from either changes the model or changes the underlying population. Our approach based on recent progress in mytime-valid inference and game theee-thcoeetic statistics the "testing by betting" framework in particular. These connections ensure that our methods are interpretable, fast, and easy to implement. We demonstrate the efficacy of approach on three benchmark fairness datasets.
1 Introduction
As algorithmic decision-making continues to increase in prevalence across both the private and public sectors [1, 2], there has been an increasing push scrutinize the fairness of these systems. This has lead to an explosion of interest in so-called "algorithmic fairness", and a significant body of work has focused on both defining faimesss and training models fair ways (e.g.. [3-5]). However, preventing and redressing harms in real systems also requires the ability to audit models in order to assess their impact; such algorithmic audits are increasing area of focus for researchers and practitioners [6-9]. Auditing may begin during model development [10]. but as model behavior often changes over time throughout real-world deployment in response to distribution shift or model updates [1 1, 12], it is often necessary to repeatedly audit the performance of algorithmic systems over time [8, 13]. Detecting whether deployed models continue to meet various fairesss criteria is of paramount importance to deciding whether an automated maaisinnnmaiingg system continues act reliably and whether intervention is necessary.
In this work, we consider the perspective of an auditor or auditing agency tasked with determining if model deployed "in the wild" is fair or not. Data concerning the system's decisions are gathered over time (perhaps with the purpose of testing faimness but perhaps for another purpose) and our goal determine if there is sufficient evidence conclude that the system unfair. If system is in fact unfair, we want to determine so as early as possible, both in order to avert harms to users and because auditing may require expensive investment to collect or label samples [8, 13]. Following
the recent work of Taskesen et al. [14] and Si et al. [15], natural statistical framework for thinking about this problem is hypothesis testing. Informally, consider the null and alternative hypotheses, Ho and H,, defined respectively
Ho the model is fair, H1 the model is unfair.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Unfortunately, traditional hypothesis testing requires stringent assumptions on the data; a fixed number of iid data points, for example. Such assumptions are unrealistic our setting. We should, for instance, be able to continually test a system
we receive more information, i.e., perform sequential hypothesis testing. Moreover, we would like to be able stop collecting additional samples at arbitrary data-dependent stopping times if we have sufficient evidence against the null. This is not allowed in traditional statistical frameworks, where it is known as "peeking" or "p-hacking."
To overcome these challenges, we take advantage of recent progress in safe, anytime-valid inference (SAVI) to construct sequential procedures for determining whether an existing crcision-making system is fair. SAVI is part of sequential analysis, a branch of statistics concerned as the name suggests- with analyzing data sequentially while maintaining statistical validity. This subfield traces its origins back to Wald, Lai, Robbins, and several others beginning in the 1940s [16-20]. More recently, the power of sequential analysis to enable inference under continuous monitoring of data and data-dependent stopping rules (hence safe and anytime-valid) has led to an explosion of work in the area [21-23]. A further exciting development has been the connection between such methods and so-called "game-theoretic probability" [24, 25] which is consistent with modern measure theoretic probability' but provides an alternative foundation based on repeated games. Importantly for our purposes, this renders many of the tools of SAVI interpretable as well as statistically powerful. We refer the interested reader to the recent survey by Ramdas et al. [27] for further detail on the relationship between sequential analysis. SAVI, and thenrette statistics.
Contributions. We develop tools to sequentially audit both classifiers and regressors. In particular:
1. We formulate the problem of auditing the fairness of classification and regression models in terms of sequential hypothesis testing. The focus on sequential testing distinct from other work, and highlights various desiderata that are important in practice- speciiicalllcilllll......... (i) being able to continuously monitor the data and (ii) a focus on rejecting the null as early as possible (i.e., reducing the number of costly samples needed to detect unfaireess).
2. Next, we design nonparametrie sequential hypothesis tests which hold under various defini- tions of group fairness. We treat auditing as sequential two-sample testing and adapt the recent work of Shekhar and Ramdas [28] on two- two-sample testing by betting to the fairness setting. We also provide novel bounds on the expected stopping time of our tests under the alternative, and demonstrate how to handle distribution drift (due to either model changes or changes in the underlying population). time-varying data collection policies, and composite nulls which more accurately reflect practical demands.
3. Finally, we demonstrate the real world applicability of our methods on three datasets: credit default data, US census data, and insurance data. We show that our method is robust to distribution shift resulting from model retraining and to various randomized data-collection policies whose densities deviate significantly from the underlying population. All code is publicly available at https: //t///ggttttb//// com/ commbbhugg//// auditing- fagg-fairnes...
In order to provide a preview of our methodology, we suggest the following thought experiment. Imagine a fictitious better who is skeptical that a machine learning system is fair. She sets up an iterated game wherein she bets on the results of the audit as it is conducted. Her bets are structured such that, if the system is unfair, her expected payoff will be large. Conversely, if the system is fair, her expected payoff is small. Thus, if her wealth increases over time, it evidence that the system is unfair. Our sequential test thus rejects the null if her wealth crosses some predetermined threshold. Of course, the trick is to design her bets in such a way the above conditions are satisfied, and that under the alternative, her wealth grows as quickly as possible. Mathematically, the above is made rigorous via nonnegative martinglasss and results concerning their behavior over time [29, 30].
Additional Related Work. This work sits at the intersection of several fields. On the fairesss side, the closest work to ours is that of Taskesen et al. [14] and Si et al. [15], both of which study fairness through the lens of (fixed-time) hypothesis testing, based on a batch of n iid observations. Given iid data Z₁ ~ p. they formulate the null as Ho p E 9, where G is the set of all "fair" distributions and derive a test statistic based on projecting the empirical distribution onto G (minimizing a Wasserstein distance). They work with classifiers only. On the more technical side, we view our work as
There are some subtleties to this remark. but they are outside the scope of this work. However, as an example of how the insights of game- theerrheoe statistics can be applied to modern probability, we highlight the recent work of Waudby- Smith and Ramdas [26] which draws inspiration from Shafer and Vovk [25].

---

a continuation and application of the testing by betting framework [21] and more specifically of nonparametric two sample testing by betting [28]. We will deploy similar "betting strategies" (to be defined later) as [28]. but provide novel analyses which are particular to our setting, and consider several extensions. Relatedly, but slightly further removed from our setting, Duan et al. [31] also employ game-theoretic ideas to construct interactive rank tests. The idea of auditing system to verify its veracity extends well beyond the domain of algorithmic faireess. Statistical procedures have been developed, for instance, to audit election results [32] and recently several SAVI inspired methods have been developed for several such scenarios [33, 34]. More broadly and outside the scope of this paper, betting techniques have been deployed with great success in optimization, online learning, and statistics [35-38, 26].
2 Preliminaries
Consider feature space X' and model 9 X + [0. 1]. Depending on the application, (p(x) might be a risk score for an individual with covariates v, a classification decision, or the probability that some action is taken. Each E X' is associated with some "sensitive attribute" A = A. E {0, I,.... J} (indicating, e.g., the result of a private health test, whether they went to college, their income strata, etc). We will often refer to A as group membership. The classifier may or may not observe A. For the sake of exposition, we will assume that A E {0, 13, i., there are two groups. However, our methods extend straightforwardly to more than two groups. The details are provided in Appendix B. Before formally stating the problem, let us discuss the notion of fairness we will employ in this work.
Fairness. We focus on the concept of "group" faireess. Roughly speaking, this involves ensuring that groups of individuals sharing various attributes are treated similarly. There have been multiple notions of group fairness proposed in the literature. We introduce the following generalized notion of group fairness, which can be instantiated to recapture various others.
Definition 1. Let (5, X, (o...). denote family of conditions on the attributes A, covari- ates X, and outcomes Y. We say a predictive model yp X + [0, 1] is fair with respect to {&) } and a distribution p over X' if, for all j E [J], Ex~o (p(( (X) X, Y)] = Ex
(O.....J)
X, Y)].
As was mentioned above, unless otherwise stated we will assume that there are only two conditions Eo. E1. For our purposes, the important feature of Definition is that it posits the equality of means. Indeed, letting μ4a E (xx=ol(sX)((s alternative as H₃ orr # μ1. Different choices of conditions Ey lead to various faimess notions in the literature. For instance, if oo is a classification model, then:
for b E {0, }} we can write our null as Ho 1o = lu and
1. Taking En = (A = 0, Y = 1} and E = (A = Y, =1 1} results in equality of opportunity
[39]. Predictive equality [40] is similar, corresponding switching Y = 1 with Y 0.
2. Taking Eo = {A = 0), & = {A- = 1} results in statistical parity [41]]
3. Taking ε = {A== = j. j,{( for some projection mapping É X + F C X onto "legimitate factors" results in conditional statistical parity [42, 41].
Problem Formulation. We consider an auditor who is receiving two streams of predictions 2o (p(XF))eET and Z = (+(())))eT) where X obeys condition &. (i.c., is drawn from some distribution over Xl..). For brevity, we will let y x(X)), b E {0, 1]. The index sets To, Ti C N }oo denote the times at which the predictions are received. We let the index differ between groups it may not be feasible to receive prediction from each group each timestep. We refer to this entire process as an audit of the model 4
For b E f0. 1}. let [&[ To n [t] be the set of times at which we receive predictions from group b up until time The auditor is tasked with constructing a sequential hypothesis test & (Ø. ) where o. = or ((U 2 U (ULeT, 2,)) (0, 1} is a function of all predictions received until time l. We interpret Φi = 1 as "reject Ho", and de as "fail to reject Ho." Once we reject the null, we stop gathering data. That is, our stopping time is 7 arg infe 1}. We say that e is level-a sequential test if
sup P( = < a, or equivalently PEH.
sup P(r < 50)
(1)
PeHo
In words, the test should have small false positive rate (type error) simultaneously across all time steps. (Note that fixed-time level-a test would simply drop the quantifier 3t > and concern
3

---

itself with some fixed time t n.) We also wish to design tests with high power. Formally, we say that o has asymptotic power 1 3 if su P(vt 2 1: : o. 0) I 5, or equivalently suppeH, P(r = oo) S B. That is, in all worlds in which the alternative is true, we fail to reject with probability at most /3 (type error). Typically the type-ll error 3 = Br decreases with the sample size n. In this work we will develop asymptotic power one tests, meaning that 3,, + 0 as n -> oc.
Martingales and filtrations. Our techniques rely on the machinery of nonnegative (aatinamas and results concerning their behavior over time. We introduce some of the technicalities here. A (forward) filtration F = (Fi))20 an increasing sequence of o o-fields Fr C Fi+1- Throughout this paper, we will consider the "canonical filtration" F, o very usefully) be thought of as all the information known at time t. We say that a stochastic process S = (S)) is adapted to (F.) if St is F,, measurable for all t 2 1. and predictable if S, is Fi-1 measurable for all 2 1. A P-martingale is an adapted stochastic process M = (M1)221 such that [i] Mf for all f 2 1. If the equality is replaced with S. then M is P-supermartingale particularly useful result in sequential analysis is Ville's 's inequality [29]. which states that if M is a nonnegative P-supermartingale, then for all a > O, P(3t 2 0 M. 1/a) S [Mo]. We will also employ the following randomized improvement to Ville's 's inequality [43, Corollary 4.1.1]: For M as above and any F-stopping time P(3 T M, 2 1/ax or M, 2 U/a) S where U is
Ze) which can heuristically (but
uniform random variable on [0, 1] which is independent of M and T.
3 Methods
We begin by introducing the methodology in the setting where the predictions are received uniformly at random from the population. We will then progressively generalize the setting: Sections 3.2 and 3.3 will enable time-varying data collection policies, Section 3.4 will allow the means μ and fn to change with time, and Section 3.5 will consider composite nulls of the form IMo p1l S
To case the presentation, let us make the assumption that we receive an audit from both groups each timestep, so that To Ti = N. This is without loss of generality; one can simply wait until multiple audits from each group are available. However, Appendix provides a more detailed discussion on how to modify our framework and theorems if this condition is unmet.
3.1 Testing by betting
Returning to the intuition for a moment, recall the fictitious bettor discussed in the introduction. She attempts to prove that the system is unfair by betting on the results of the audits before they revealed. If the system is unfair, then the average difference between P and Y; (i.e., the model's 's outputs across different groups) will be non-zero. The skeptic's 's bets are therefore structured such that if μ = EY + EÝ; = Mi, then her expected wealth will increase over time, More formally, at time the skeptic designs payoff function S. : R x R + Rz0 which is F, measurable and Ey (S, (²:0 [r-1] < 1 if P E Ho (i.e, 44n = 11).. Next, the skeptic receives the model predictions Y (XX)) and Y = ((())). We assume the skeptic starts with wealth of Ko = At each time L, she reinvests all her wealth KG-1 on the outcome and her payoff is KG = SP. P.1) KG-1 = IT S,77, P.!).. We call (KG))20 the skeptic's 's wealth process. The wealth process
under the null, due the constraint function. Thus, by Ville's inequality, the probability that Kc, ever exceeds 1/a is at most a when the model is fair. The skeptic's goal, as it were, is design payoff functions such that the wealth process grows quickly under the alternative, and thus rejection occurs sooner rather than later.
supermartingale starting
the payoff
Inspired by common idea in game thee-theoretic statistics (cf. [21, 26-281), let us consider the following payoff function:
S. S (()))))) = 1+ (9. -Ý,).
(2)
where A, is predictable and lies in [-1, 1] to ensure that (P.. P.)) 2 0. Note that for P E Ho- [p[Ka]Fi-1] = 1 Ep(1++>(8 Rejecting when K., > 1/a thus gives to valid level-a sequential test as described above. We will select d using Online Newton Step (ONS) [44, 45], which ensures exponential growth of the wealth process under the alternative. Figure illustrates the behavior of the wealth process under various hypotheses when using ONS to choose d As the difference between the means A |Po #1l
- - 1=
K,- so (KG) is a nonnegative P P-martingale.

---

Algorithm Testing group fairness by betting
Growth of ih process
150
Input: (0,
Ko +
100
for = 1,2,..,, do
Wea th
T may nol be known in advance
Perhaps receive audits 9 and Y.!
50
Construct payoff St (e.g. (2), (16), or (7)) Update K2 + S If Kf; 2 1/a then stop and reject the null end for if the null has not been rejected then
0-
50
150
250
300
Time
Draw U ~ Unif(0, 1), reject if K,, U/a
0.1.1
1/a
end if
4=0
Figure 1: Left: Description of main algorithm. Right: The wealth process (K2) under different conditions on the means. Observations follow a Bernoulli distribution for a given mean. As A == |n0 fia increases, the wealth grows more quickly. If test rejects, the procedure ends, hence the plateauing of the blue and purple lines. For A = 0, the wealth fluctuates around and the test never rejects. Shaded regions indicated the standard deviation after 100 trials.
increases, the wealth grows more quickly which leads to faster rejection of the null. To define ONS, let 9r = Y Y and initialize \ = For 2 1, recursively define
d (2-2213)
2 In(3) 1 E - 11/2) v -1/22, where
2--1
9i A.gi
The machinery just introduced sufficient to define a level-a sequential test. However, we add a final ingredient to increase the power of this procedure. Motivated by the randomized Ville's inequality mentioned in Section 2, we introduce one final step: If we stop the procedure at some stopping time but have not yet rejected the null (because, for instance, our budget K,, 2 U/a, where U uniform on [0, and drawn independently from everything observed so far. We emphasize that the final step only be performed once. Thus, if it is possible that more data will be collected in the future, we advise waiting. We summarize the process in Algorithm 1.
out), can check if
The following proposition gives bound on the expected stopping time of this sequential test under the alternative. We note that Shekhar and Ramdas [28] also provide a bound on the expected stopping time of multivariate betting-style sequential test. However, due to the generality of their setting, their result defined in terms quantities which are difficult to analyze. We thus provide a more direct analysis specific the difference of univariate means. The proof may be found in Appendix C.I.
Proposition 1. Algorithm with input (0, 1) and betting strategy (2) is level-ax sequential test with asymptotic power one. Moreover, letting A = |Po [41), under the alternative the expected stopping time obeys
1
E
S
log
(4)
AZa
is possible to demonstrate a lower bound of [[r] 2 / where a² = -E[(Po
p1 [28, Prop. 2]. Since 2² 2 1 in the worst case, our result is optimal up to a factor of log(1/A?).
3.2 Time-varying data collection policies
Here we extend the setting to allow for -ine-dependent data collection policies. This is motivated by the fact that organizations are often collecting data for various purposes and must therefore evaluate fairness on data which is not necessarily representative of the population at large. We also allow the data collection policies to differ by group. Mathematically, for b (0. 1} let x+(()) =x(-EE) denote the randomized policies which determine the probability with which a set of covariates are
5

---

selected from the population. Let p" be the density of ((.. Following standard propensity weighting techniques [46, 47], introduce the weighted estimates
wx(x) p
(5)
mi (x(
We may write simply w/ when x is understood from context. The policy n. (and hence the weight w/) need not be deterministic, only Ft-1 measurable (so it can be considered deterministic quantity at time 1). This motivated by various practical applications of sequential decision-making, in which the policy used to collect data often changes over time in response to either learning policy [48, 49]. In many applications, o. a function of a select few covariates only instance, income, education level, or career. In some settings is reasonable assume knowledge of pe (by means of a census, for instance). However, this is not always the case. Section 3.3 will therefore discuss strategies which do not require precise knowledge of the density. We will assume that for all x, t and b, (x) < co. In this case, (5) enables an unbiased estimate of f4 = Ex,((())) when X, is sampled according to x
E Ex-a; ( = J ((z))) (lo)a)())) Sx ((x)p) 1ab-
(6)
Our payoff function is similar to the previous section, but reweights the samples by w/([= w/( (XP)).
and then adds a corrective factor to ensure that the payoff is nonnegative:
St S F!) = 1+ (P, - Y/!W!), where L; == min ess inf
1
(7)
bE(0,1) ZE (x)(z)
and de is once again selected via ONS. Multiplication by L, is required to ensure that the values L, (Y,Ww wg Y/lw!) lie in [-1, 1] in order be compatible with ONS. Here "ess inf" is the essential infimum, which is the infimum over events with nonzero measure. For most practical applications one can simply replace this with minimum. For such strategy, we obtain the following guarantee.
Proposition 2. Algorithm I with input E (0, 1) and betting strategy (7) is a level-a sequential test with asymptotic power one. Moreover, suppose that 0 < Linf := inf L, and let k = A and A = | Hnl. Then, treating log-log factors as constant, under the alternative the expected stopping time obeys
E[
log
(8)
R2
k²aa
Thus we see that we pay the price of allowing randomized data collection policies by factor of roughly 1/Tnnt- Note that the payoff function (7) does not require knowledge of Linf Indeed, this strategy remains valid even if Timf = 0 as long as T., is nonzero for each f. It is only the analysis that requires Lint to be finite and known. The proof of Proposition 2 is provided in Appendix C.2.
3.3 Time-varying policies for unknown densities
A reasonable objection the discussion in the previous section is that the densities pe may not always be known. In this case we cannot compute the propensity weights in (5). Here we provide an alternative payoff function which uses an estimate of the density, p". We assume we know upper and lower bounds on the multiplicative error of our estimate: 8una 2 max, sup,, (p' (x)( (x))p((x)), and gmin < min, inf (7 (x:) (x)) We assume that gmin > O.
Let @f be the propensity weights at time t using the estimated density, i.e., (z(2) (z)/ Notice that Ex==, (X))(()))xXXXX)
fx ((x))" (x))dr Sx (z)) (x) S
gmax Hb. Similarly, E Ex-: (3 the payoff function
8mmn pb. Recall that G x(xx)). Consider
Po Jmax
#f 8min
S 874) ) 1 A,B.
where B, is F.-1 measurable. Then
Bag Y.
E 10 181
ESS. = 1 A,B,
< + A, - v1).
Juax
8min

---

1.0
0.75
Mo(()
Mi((1
0.50
0.5
0.25
Wea th
100
100
0
100
200
300
400
0 100
200
300
400
Time
Time
Figure 2: Two illustrations of our sequential test adapting to distribution shift. In both settings, the observations time are Bernoulli with bias determined by the respective mean at that time. Shaded areas in the bottom plots represent the standard deviation across 100 trials. Left: For the first 100 time steps, have (t()) ju1 (1) 0.3. At time 100, 14 (t) begins to smoothly slope upward. Right: Here we assume that both means are non-stationary and non-smooth. Both are sinusoidal with Gaussian noise but (t) drifts slowly upwards over time.
Under the null, (40 - μ1 O. implying that [[ < 1. We select B, so that St is nonnegative (thus ensuring that the capital process is nonnegative supermartingale) and is compatible with ONS. The following condition on B, suffices: B, < gunn min; inf, (23) (xr))= Note that we know the true densities then
take g 8min and recover (7).
3.4 Handling distribution shift
Until this point we' 'e assumed that the means μl remain constant over time. A deployed model, however, is susceptible to distribution shift due to changes in the underlying population, changes the model (retraining, active learning, etc), or both. Here we demonstrate that our framework handles both kinds of drift. In fact, need not modify strategy (we still deploy Algorithm 1), but we must reformulate our null and alternative hypotheses and our analysis will change. Before introducing the mathematical formalities, two cases of distribution shift and the response of our sequential test to each. The left panel is case of "smooth" drift in which case (t) /41 (t) equal for some number of timesteps after which Jn (t) begins to drift upward. The right panel exemplifies a situation in which both means change each timestep (the weekly prevalence of disease in population, for instance), but 141 (t) has marked drift upward over time. In both cases, the wealth process is sensitive to the drift and grows over time.
draw the reader's attention to Figure 2 which illustrates
To handle changes in the underlying population we let denote the population distribution over X at time t. Likewise, to handle changes to the model, we let pp: : X' + [0. 1] be the model at time t. In order to define our hypotheses, let A := (t) 44 (t)] where μu (t) Ex~p. (xx(()))eeeee))))))) Fe-1), b e {0, 1}. Then, we write the null and alternative hypothesis as
Ho A, = 0 1I 1, 37 S.t. A 0 A T.
(10)
Of course, Ho and H1 do not cover the space of possibilities. In particular, neither contains the event that (t) * (t) for some finite interval t E [a. b) and are otherwise equal. However, we believe (10) strikes desirable balance between analytical tractability and practical utility; defining H, such that we will reject the null for each finite window (a, b] places too extreme burden on the growth of the wealth process. Moreover, as illustrated by Figure 2, if A, > for large enough window, then our sequential tests will reject the null.
If are working with randomized data collection policies per Section 3.2, then one should change the definition of the weights in Equation (5) to incorporate the time-varying distribution pt. That is, wf (z) p (z) (z). Otherwise, all procedures detailed in the previous sections remain the same, and we can provide the following guarantee on their performance.
Proposition 3. Algorithm 1 with input E (0, 1) and betting strutegies (2) and (7) is level-o sequential test for problem (10). It has power one under the alternative if Aint == inf A, where n is some time at which drift begins. Moreover, under the alternative the expected stopping
7

---

Credit Default Dataset
No correction (M1)
With correction (M2)
Type-I error (M1)
0.5
6.6
FPR (under Ha)
A = 200
0,00
Desiee
f 500
6.1
1000
1.2-
0,02
0.2-
0000
0,001
0.0
500
10GD
5500
1000)
2000
0.00
01.05
Rejection time (under Hi)
Rejection time (under H:]
Permutation test (MI)
Permutation test (M2)
X
Betting
Figure 3: Comparisons of false positives rates (FPRs) and stopping times on credit loan data and US census data. The left two columns plot under Hi versus the FPR as is varied from 0.1 to 0.01. The FPR grossly inflated when under method MI, as illustrated the first and third columns. Betting is a Pareto improvement over the permutation tests.
time obeys
E B n
log
(11)
A inf
2
Furthermore, if the data are gathered by randomized policies &. and Lint >> 0 for Line as in Proposition 2, then the expected stopping time follows by replacing Dint in (14) with Aint Lint-
Let us make two remarks about this result. First, the condition Amt > 0 ensures that, after some point, the means fo (t( and μr (t) remain separated. they diverge only later reconverge, there is no guarantee that the test will reject (though. in practice, it will if they are separated for sufficiently long). Second, the reader may have guessed that the expected stopping time under drift beginning at However, it is priori feasible that
time n follows from Propositions 1 and 2 after simply adding the reliance of ONS on past predictions would result in slower convergence under distribution shift. Proposition 3 verifies that this is not the case, and that the rate is the same up to constants.
3.5 Composite Nulls
In practice, it may be unreasonable require that the means between two groups precisely zero. Instead, we may only be interested in detecting differences greater than e for some & 1. In this case we may write the null and alternative
Ho | - Hil S e vs H1 140 - Hil >
(12)
To formulate our test, introduce Hi : Ho > and H μ4 is false, then the alternative H, is true. Our approach will therefore entail testing both H. vs Hi and H6 vs H" Let of denote the sequential test for the former, and &f for the latter. The test given by o, = max oR) (i.e., rejecting Ho if either Ho or H is rejected) is then a test for
pairs of auxiliary hypotheses: H6 140 #4 S
S vs H" #n
> e. Observe that if either H or H
(12). Came-theoretically, this can be interpreted splitting our initial capital in half and playing two games simultaneously. To test Hi and H' consider the two payoff functions
Q₂
= 1 p;)==
A8 ? c), and (YO Y!) = + Xe 8.0 -)--
(13)
A, | H then both Q and RG are nonnegative. We thus select X, ONS as usual. The wealth processes (KC) and (KRR) defined by Qe and Rd (i.e., K. nlse PPP P,!) and KRft -lige (Y,,, P!i) are then nonnegative supermartingales under HQ and Hğ respectively. We reject Ho if either KCf 2 2/a or X 2/a which results in overall level-a sequential test. Proposition 4. Algorithm I with input a/2 (0. 1) with betting strategy Q₁ (resp., R&) is a level-a/2 sequential test for H' vs Hi (resp.. H" vs H Rejecting Ho if either H', or H" is rejected results in level-a sequential test with asymptotic power one for problem (12). Let A |o M1 Then, under the alternative the expected stopping time 7 obeys
1
E [[T] (A 6)
log a(A - e)²
(14)
8

---

Distribution Shift, Census Data
No correction (M1)
With correction (M2)
k 250
FPR (under Hoi
k 500
0.10
0.5
k 1000
Betting
Permutation test (MI)
0.05
Permutation test (M2)
0.0
0.00
200
400
600
800
1000
2000
Rejection time (under H1)
Rejection time [under H4)
Figure 4: Response of the tests distribution shift the census data. We fair model for 400 timesteps, after which we switch to an unfair model with A R 1.0. The leftmost plot uses permutation tests under M1, resulting in inflated type-I error. Values are plotted ranges from 0.01 0.1.
We note that under the alternative, < A, so < - A. Proposition states that the expected stopping time depends on the interplay of Á and and will increase as they approach each other. This is intuitive. For a fixed A one would expect that the problem becomes harder as e A.
4 Experiments
Here we provide several sets of experiments to demonstrate the benefits of our sequential test compared to fixed-time tests.² First we need to consider how fixed-time tests might be applied in practice to deal with sequential settings. We consider two such methods.
N, wait until we have collected audits, then perform the test. If the test does not reject, collect another k audits and repeat. We emphasize that if one does not adjust the significance level over time, then this not a valid level-a test. However, may be used unwittingly in practice, so we study it one baseline.
M1. For some prespecified
M2. We batch and test the same way as above, but we apply Bonferroni-like correction in order to ensure it is level a. More precisely, for the jth-batch, j 2 1, we set the significance level to a/22. The union bound then ensures that the FPR is at most a over all batches.
We run experiments on three real world datasets: a credit default dataset [50], US census data [51] and health insurance data [52]. All can be made violate equality of opportunity if trained with naive models; we provide the details in Appendix D. Suffice it to say here that the absolute difference in means, A, is 0.03 for the credit default dataset, R 1.1 for the census data, and z 0.06 for the insurance data. We employ various distinct models to test our methods, from forest-based models to logistic regression. We use permutation test as our baseline fixed-time test because of its ubiquity in practice, exact type-I error control under exchangcability. and minimax optimality in various scenarios [53].
Figure 3 compares the results of Algorithm (betting strategy (2)) with the permutation test baselines MI and M2. The left two columns plot the empirical false positive rate (FPR) against the stopping time under the alternative. Values concentrated in the lower left corner are therefore preferable. We plot values for each test is varied from 0.01 to 0.1. The betting test typically Pareto-dominates the (stopping time, FPR) values achievable by the baselines. In a small number of cases, M1 (baseline without Bonferroni correction) achieves a faster stopping time; however, this is only possible with very high FPR (> 0.5). This inflated FPR is verified by the final column, which shows that MI does respect the desired type-I error rate. This encourages the use of the Bonferroni-style correction of M2. However, doing so results in an overly conservative test which is slower to reject than betting, as seen in the center column of Figure Betting, meanwhile. respects the desired FPR over all a, and almost always has the fastest stopping time at any given FPR. We note that while it may appear that the permutation tests improve as k gets larger, this trend does not hold for large k. Indeed, is
We reffrain from comparing our betting-styl style sequential tests to other sequential tests; we refer the reader to [28] for such comparisons. Instead, our goal in this section is to persuade the fairness community that sequential tests are superior tools to fixed-time tests for auditing deployed systems.

---

Various Data Collection Policies, Insurance Dataset
0.10
Population
Relative. probability
FPR under Hu
0.05
200
0.2
0.00
0.U
NE
NW
SE
SW
2500
5000 7500 100000
Region
Rejection time under 17,
Figure 5: Illustration of our betting method when using various data collection strategies, Ti, 22. and T3. which were based on each individual's region (NE, NW, SE, SW). Operationally, я, samples an individual by first sampling region with the given probability, and then sampling individual uniformly at random from that region. We compare results against our method with data sampled uniformly from the population (red crosses), and to permutation tests (M2), also with uniformly sampled data. Even with randomized policies, we continue to outperform permutation tests.
also the minimum rejection time for the permutation test. Increasing & to 1,500 on the credit default dataset, for instance, would result in vertical line at 1, 500.
The robustness of betting to distribution shift is illustrated by Figure Here we use fair model for the first 400 timesteps. after which we switch to a random forest classifier which is unfair (A z 1.1). The rejection time for all tests suffers accordingly, but betting remains Pareto improvement over the permutation tests using M2. As before, using MI results in an enormous FPR. Interestingly, we see that M2 also results FPR higher than 0.1 (the maximum value of a:) nontrivial percentage the time. Indeed, under distribution shift, the the permutation test using M2 is no longer level-a since the data are not exchangeable, Betting, on the other hand, maintains its coverage guarantee.
Finally, Figure 5 illustrates the performance of various algorithms when audits are not conducted on predictions received uniformly at random from the population (discussed Section 3.2). Instead, predictions were received based on an individual's 's region. We test three distinct strategies, T1, T2 and 33, each of which deviates from the population distribution varying degrees (LHS of Figure 5). As expected, the rejection time of our strategy suffers compared to when the predictions are received uniformly from the population (denoted by the red crosses). The desired level-a guarantee still met, however, and betting continues to outperform permutation tests in all cases.
5
Summary
We have argued that practitioners in the field of algorithmic fairness should consider adopting sequential hypothesis tests in lieu fixed-time tests. The former enjoy two desirable properties absent in the latter: (i) the ability to continually monitor incoming data, and (ii) the ability to reject at data-dependent stopping times. Both (i) and (ii) are useful for high-stakes and/or time- sensitive applications in which fixing the budget beforehand and waiting for more data to arrive may be unsatisfactory, such as auditing the fairness of healthcare models [54] or resource allocation strategies during a public health crisis [55, 56]. We provided a sequential test with asymptotic power one for group fairness (Algorithm 1) inspired by the paradigm game-theoretic probability and statistics [25, 21, 28]. It is fast, easy to implement, and can handle marying data collection policies, distribution shift, and composite nulls, all which are common in practice. We also provided bounds on the expected stopping time of the test. We hope that the simplicity of our methods combined with their strong theoretical guarantees prove useful for practitioners the field.
Limitations and societal impact. Auditing is complex socio- nocio-technical problem which involves range of questions: choosing appropriate audit targets, gaining access data, ensuring the credibility and independence of external auditors, creating accountability based on audit results, and more [57]. Indeed, poorly designed audits may certify that a system is "fair" while masking harder to verify issues such as data provenance. Our work addresses only one portion of the overall auditing task: providing statistically sound methods for the sequential testing of a specific criteria. This complementary to, and does not substitute for, careful overall design of auditing framework.
10

---

Acknowledgements. We thank Jing Yu Koh and Shubhanshu Shekhar for helpful conversations. We also thank the anonymous referees for helpful feedback which improved the paper. BC and AR acknowledge support from NSF grants IIS-2229881 and DMS-2310718 BC was supported in part by the NSERC PGS D program, grant no. 567944. BW and SCG were supported in part by the A12050 program at Schmidt Futures, grant no, G-22-64474.
References
[1] Shira Mitchell, Eric Potash, Solon Barocas, Alexander D' Amour, and Kristian Lum. Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application, 8:141-163, 2021.
[2] Peter Henderson, Ben Chugg, Brandon Anderson, and Daniel Ho. Beyond ads: Sequential decision-making algorithms in law and public policy. In Proceedings of the 2022 Symposium on Computer Science and Law, pages 87-100, 2022.
[3] Deborah Hellman. Measuring algorithmic fairness. Virginia Law Review, 106(4):811-86) 2020.
[4] Jon Kleinberg, Jens Ludwig. Sendhil Mullainathan, and Ashesh Rambachan. Algorithmic fairness. In AEA papers and proceedings, volume 108, pages 22-27, 2018.
[5] Allison Woodruff, Sarah E Fox, Steven Schinde- and Jeffrey Warshaw. A qualitative exploration of perceptions of algorithmic faimess. In Proceedings of the 2018 CHI conference on human factors factors in computing systems, pages 1-14, 2018.
[6] Inioluwa Deborah Raji and Joy Buolamwini. Actionable auditing: Investigating the impact of publicly naming biased performance results of commercial Al products. In Proceedings the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 429-435, 2019.
[7] Jack Bandy. Problematic machine behavior: A systematic literature review of algorithm audits. Proceedings of the ACM on human-compute interaction, 5:1-34, 2021.
[8] Danaë Metaxa, Joon Sung Park, Ronald E. Robertson, Karrie Karahalios, Christo Wilson, Jeff Hancock, and Christian Sandvig. Auditing algorithms: Understanding algorithmic systems from the outside in. Foundations and Trends in Human-Computer Interaction, 14(4):272-344 2021.
[9] Briana Vecchione, Karen Levy, and Solon Barocas. Algorithmic auditing and social justice: Lessons from the history of audit studies. In Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1-9. 2021.
[10] Inioluwa Deborah Raji, Andrew Smart, Rebecca N. White, Margaret Mitchell, Timnit Gebru, Ben Hutchinson, Jamila Smuth-Loud, Daniel Theron, and Parker Barnes. Closing the AI accountability gap: Defining end-to-end framework for internal algorithmic auditing. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 33-44, 2020.
[11] John R Zech, Marcus A Badgeley, Manway Liu, Anthony Costa, Joseph Titano, and Eric Karl Oermann. Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: cross-sectional study. PLoS medicine, 15(1 (xeee6633) 2018.
[12] Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. Proceedings of the European conference on computer vision (ECCV), pages 456-473, 2018.
[13] Xiaoxuan Liu, Ben Glocker, Melissa M McCradden, Marzych Ghassemi. Alastair K Denniston. and Lauren Oakden-Rayner. The medical algorithmic audit. The Lancet Digital Health, 2022.
[14] Bahar Taskesen, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. A statistical test for probabilistie fairness. In Proceedings of the 2021 ACM Conference on Fairness, Accountability; and Transparency, pages 648-665, 2021. 1

---

[15] Nian Si, Karthyek Murthy, Jose Blanchet, and Viet Anh Nguyen. Testing group faimess via optimal transport projections. In International Conference on Machine Learning, pages 9649-9659, PMLR, 2021. 1,2
[16] Abraham Wald. Sequential analysis. John Wiley and Sons, 1947. 2
[17] Abraham Wald and Jacob Wolfowitz. Optimum character of the sequential probability ratio test. The Annals of Mathematical Statistics, pages 326-339, 1948.
[18] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[19] Donald A Darling and Herbert Robbins. Confidence sequences for mean, variance, and median. Proceedings of the National Academy of Sciences, 58(1):66-688 1967.
[20] Tze Leung Lai. On confidence sequences. The Annals of Statistics, pages 263-280, 1976. 2
[21] Glenn Shafer. Testing by betting: A strategy for statistical and scientific communication. Journal of the Royal Statistical Sociery: Series A (Statistics in Society), with discussion, 184(2): 407-431, 2021. 2, 4, 10
[22] Aaditya Ramdas, Johannes Ruf, Martin Larsson, and Wouter Koolen. Admissible anytime-valid sequential inference must rely on nonnegative martingales. arXiv preprint wwXiv:2009.03167 2020.
[23] Peter Grünwald, Rianne de Heide, and Wouter M Koolen. Safe testing. Journal of the Royal Statistical Society, Series (Methodological) forthcoming with discussion, 2023.
[24] Glenn Shafer and Vladimir Vovk. Probability and finance: It's only game!, volume 491. John Wiley & Sons, 2005. 2
[25] Glenn Shafer and Vladimir Vovk. Game-theoretic foundations for probability and finance, volume 455. John Wiley & Sons, 2019. 2, 10
[26] Ian Waudby-Smitt and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society, Series B (Methoddological), forthooming with discussion, 2023. 2. 3, 4
[27] Aaditya Ramdas, Peter Grünwald, Vladimir Vovk, and Glenn Shafer. Game-theoretic statistics and safe anytime-valid inference. Statistical Science, 2023. 2
[28] Shubhanshu Shekhar and Aaditya Ramdas. Nonparametric two-sample testing by betting. IEEE Transactions on Information Theory, 2023. 2, 3, 4, 9, 10
[29] Jean Ville. Étude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):224 1939.
4
[30] Johannes Ruf, Martin Larsson, Wouter M Koolen, and Aaditya Ramdas. A composite general- ization Ville's martingale theorem. Electronic Journal of Probability (forthcoming). 2023.
2
[31] Boyan Duan, Aaditya Ramdas, and Larry Wasserman. Interactive rank testing by betting, In Conference on Causal Learning and Reasoning, pages 201-235. PMLR, 2022. 3
[32] Philip B Stark. Conservative statistical post-election audits. The Annals of applied statistics, 2 (2),550-581, 2008. 3
[33] Ian Waudhy-Smith, Philip B Stark, and Aaditya Ramdas. RiLACS: Risk limiting audits via confidence sequences. In Electronic Voting: 6th International Joint Conference, E-Vote-ID 2021, Proceedings 6, pages 124-139, Springer, 2021. 3
[34] Shubhanshu Shekhar, Ziyu Xu, Zach Lipton, Pierre J. Liang, and Aaditya Ramdas. Risk- limiting financial audits via weighted sampling without replacement. Uncertainty in Artificial Intelligence ( (UAI), 2023.
12

---

[35] Francesco Orabona and Dávid Pál. Coin betting and parameter- free online learning. Advances in Neural Information Processing Systems, 29, 2016.
[36] Kwang-Sung Jun and Francesco Orabona. Parameter-free online convex optimization with sub-exponential noise. In Conference on Learning Theory, pages 1802-1823. PMLR, 2019.
[37] Keyi Chen, John Langford, and Francesco Orabona. Better parameter-free stochastic optimiza- tion with ODE updates for coin-betting. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 6239 6247, 2022.
[38] Ian Waudby-Smin Smith,, Lili Wu, Aaditya Ramdas, Nikos Karampatziakis, and Paul Mineiro. Anytime-vee valid off-policy inference for contextual bandits. ACM/IMS Journal of Data Sci- ence, 2023. 3
[39] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016. 3, 21
[40] Sam Corbett-Dave Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost fairness. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data mining, pages 797-806, 2017. 3
[41] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-222 2012.
[42] Faisal Kamiran, Indré Žliobaité, and Toon Calders. Quantifying explainable discrimination and removing illegal discrimination in automated decision making. Knowledge and information systems, 35:613- 11661,4,,,,, 2013. 3
[43] Aaditya Ramdas and Tudor Manole. Randomized and exchangeable improvements of Markov's, Chebyshev's ' and Chernoff's inequalities. arXiv preprint arXiv:2304.02611 2023, 4, 16
[44] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in Banach spaces. In Conference On Learning Theory, pages 1493-1529, PMLR, 2018. 16
[45] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-199)) 2007.
[46] Daniel G Horvitz and Donovan Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260)::63-6855, 1952.
[47] RD Narain, On sampling without replacement with varying probabilities. Journal of the Indian Society of Agricultural Statistics, 3(2):169-175, 1951. 6
[48] Peter Henderson, Ben Chugg, Brandon Anderson, Kristen Altenburger, Alex Turk, John Guyton, Jacob Goldin, and Daniel E Ho. Integrating reward maximization and population estimation: Sequential decision-making for Internal Revenue Service audit selection. AAAI Conference on Artificial Intelligence, 2023.
[49] Ben Chugg, Peter Henderson, Jacob Goldin, and Daniel E Ho. Entropy regularization for population estimation. AAAI Conference Artificial Intelligence, 2023. 6
[50] I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2): 1473-2480 2009.
[51] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine leamnin. Advances in Neural Information Processing Systems, 34, 2021. 9, 21
[52] Brett Lantz. Machine learning with R: expert techniques for predictive modeling. Packt Publishing Limited, 2019, 21
13

---

[53] Ilmun Kim, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimality of permutation tests. The Annals of Statisties, 50(1):225-251, 2022. 9
[54] Muhammad Aurangzeb Ahmad, Arpit Patel, Carly Eckert, Vikas Kumar, and Ankur Terede- sai. Fairness in machine learning for healthcare. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3529-3530, 2020. 10
[55] Douglas B White and Derek C Angus. proposed lottery system to allocate searce COVID-19 medications: promoting faimess and generating knowledge. Jama, 324 330, 2020. 10
[56] Ben Chugg, Lisa Lu, Derek Ouyang, Benjamin Anderson, Raymond Ha, Alexis D' Agostino, Anandi Sujeer, Sarah L Rudman, Analilia Garcia, and Daniel E Ho. Evaluation of allocation schemes of COVID-19 testing resources in community-based door-to-door testing program. In JAMA health forum, volume 2, pages 2212260-e212220 American Medical Association, 2021. 10
[57] Inioluwa Deborah Raji, Peggy Xu, Colleen Honigsberg, and Daniel Ho. Outsider oversight: Designing third party audit ecosystem for Al governance. In Proceedings of the 2022 AAAI/ACM Conference on Al, Ethics, and Society, pages 557-571, 2022. 10
[58] Nick Harvey. A second course in randomized algorithms. 2022. 17
14

---

A Testing in batches
Of course, it is the rare application in which we can expect to receive audit from each group each timestep. We can modify the strategy in Section 3 to handle different arrival times by simply waiting to bet until we have new audits from each group. If multiple audits from the other group have accumulated during that period, we bet with their average. More formally, define
N [b(t] n (n:n max(()))(())), and G
1
Σ JENY
(15)
where we recall that Toll] To n [4] is the set of times at which we receive audits from group b up until time t. In words, NV is simply all timesteps for which we receive an audit from group b without receiving an audit from the other group. From here, we can define a payoff function as
S = 1 (G - G)), if Nf * 0 and N2 * 0, 1,
(16)
otherwise.
If S, = then K,2 = 1, so this can be interpreted as abstaining from betting at time L. This occurs when we have no new audits from one group (N₂- = 0 for some b). Note that No and Nł are both
non-empty, then one of them contains only t. Thus, in this case, GP - G. E ( G G. 9. As in Section we choose A using ONS, but we use gt = G Gt in its definition. The expected stopping time of the test defined by (16) follows as a corollary from Proposition 1 after correcting for the number of timesteps during which non-trivial bets were placed. More specifically, the stopping- time in Proposition is with reference to the number of times we actually bet, i.e., with respect to the times {t: N. # 0, N2 + 0). The same remark holds for other propositions throughout this paper and, as such, we will state these propositions under the assumption that To = Ti = N.
Finally, let us emphasize that the above discussion is still assuming an online data gathering procedure. If we are a nonsequential setting (i.e., all the data has already been gathered), then we may simulate a sequential setting by simply revealing the outcomes one at time. Thus, all of our procedures hold for fixed-time hypothesis testing as well.
B Auditing multiple groups
Here we consider the case when there more than two groups. Suppose we have J + I groups {0, l.....,J... J.. In accordance with Definition I, the null and alternative become
Ho : (p) = (X)))) Vi, E (0, (o.
(17)
H, : ji,j E JO such that (x)x( # (x((())
(18)
As before, let μ4 Ex(o(X)),,,, i {0. (O......J) J}. One could derive sequential test by applying Algorithm to each pair of means and μıj. Game-theoretically, this can be interpreted as splitting your initial wealth among multiple games and playing each simultaneously. If you grow rich enough in any one game, you reject the null. Of course, one needs to adjust the significance level to account for the number of games being played, thus reducing the (nonasymptotic) power of the test.
Of course, it is not necessary to test each mean against all others. We need only test whether Ms = 1bb+1 for all 6 E {o....,Jl J). That is, we can play J games instead of (( games. In order to ensure this constitutes a level-a test, we reject when the wealth process of any game is at least J/a. For any single game, this occurs with probability a/ under the null. Therefore, the union bound then ensures that the type-I error of this procedure is bounded by a. Moreover, the asymptotic power remains one since, if μ4 # Mj for some i then jo * 14++1 for some b. The guarantees we've we've provided on Algorithm ensure that the wealth process for this particular game will eventually grow larger than a/a and test will reject. We summarize this discussion with the following proposition, which is the equivalent of Proposition for auditing multiple groups
Proposition 5. Let a E 1). Consider running Algorithmm on groups b,b + 1, for b E [0.1.....JJ - 1} in parallel with input parameter a.J. This constitutes a level-a sequential test for (17) with aymptotic power one against (18). we receive an audit from each group at each timestep, then the expected stopping time T of this procedure obeys
1
E[T]
S
min
log
(19)
be J-1 1146
116411
[eb - 1b41
15

---

The expected stopping time follows from Proposition I after correcting for the significance level and the difference between the means. We take the minimum over all because the procedure rejects as soon as any of the wealth processes grow too large. Equivalent versions of Propositions 2 and 3 for multiple groups can obtained similarly.
Let us end by remarking that similar ideas may be applied to test other notions of group fairness which posit the equivalence of multiple means. This is the case of equalized odds, for instance. As above we simply imagine playing multiple games simultaneously, each testing for the equivalence of one pair of means.
C Omitted proofs
C.1 Proof of Proposition 1
We break the proof into three components.
Level-a sequential test. Combining the discussion at the beginning of Section 3 with Ville's inequality demonstrates why our procedure constitutes level-a sequential test. However, let us prove formally here for completeness. Let P E Hg and note that Ep y y = -xx))
M4 μ11 0. Therefore, using the fact that de is predictable (i.e., F -measurable)
- 2 KL A.PPPP -P,1) = KK
Ep [p/K]]FF-1] = Ep
so (Kx):21 a P-martingale, with initial value 1. Moreover, nonegative since |dl S 1/2 for all I by definition of ONS. Thus, Ville's inequality implies P(3l 2 1: K,, 2 1/a)) a, meaning that rejecting 1/a yields level-a sequential test. Finally, as discussed in the main paper, the last lines of Algorithm 1 are justified by the randomized Ville's 's incquality of Ramdas and Manole [43], which states that, for all stopping times n,
P S n: 2 1/a or K,, U/a) Sa, a,
where U ~ Unif(0, 1) is independent of everything else.
Asymptotic power Next, let us demonstrate that Algorithm has asymptotic power one. That is, for P E H,, P(r < c0) = 1. It suffices to show that P(r 5o) 0. To see this, define
90 P!. S.
ys.
V
1=1
2=1
We have the following guarantee on the wealth process, which can be translated from results concerning ONS from Cutkosky and Orabona [44, Theorem
S?
1
S2 St
K₁ 2
exp 4(V; + [S
exp
1
(20)
V
Since (7= o0} (T 1 for all > 1, have P(7 = oe) lim inf, P(7 > () <
lim inf P(K, < 1/a), where the final inequality is by definition of the algorithm. Using the second inequality of (20).
S St
8 log(t/a) S. t
8 llg(t//)
P(K, < 1/0) < P
<
1/a
<
t
By the SLLN, Sz/t converges μ40 Wy * 0 almost surely. On the other hand, 8 8log(1/a)/ 0. Thus, if we let A, be the event that exp(St /8t) < t/a, we see that ((A.) almost surely. Hence, by the dominated convergence theorem,
/ [(A))dP=
P(T = oo) < limmin inf P(A,) = lim inf 10000
iim 1(A)ddP = 0. 10000
10000
This completes the argument.
16

---

Expected stopping time. Last, let us show the desired bound on the expected stopping time. Fix P E H1. Let be the stopping time of the test. Since it nonnegative, we have
B| Σ P(T>
P(log < log((/a))
= P(E.)
for F. flog Kr (og(1/a)) Note that the second equality is by definition of the algorithm. Employing the first inequality of (20) yields
Eg C {S
4(V + [Sc))log(L/a) log
St 4
V1 + Σ laa1) (l0g(1/a) 1og(1/v3)
To analyze the probability of this event, we first develop upper bounds We = Eige løs| and V.- We begin with W, Since W; the sum independent random variables in [0, 1]. we apply the multiplicative Chernoff bound (e.g., [58]) to obtain
P(W: (1 + &))()))
Setting the right hand side equal to 1/t² and solving for d gives ō /6 logtt/EW, Thus, with probability 1 - 1/t?, we have
W. S EW; [.] t lt 2t vt 2 17,
(21)
where we ve used that E E = Eis [[ S since [gi| S 1. Following nearly identical process for Vi, we have that with probability 1 - 1/t².
we've
V < [V] + v 6E [V. logt & + / log/ s 21, 2 17,
(22)
where again that | 2 < |g:| < 1. Let H, (V < 21 ( 21). Then,
E c { (6f log(2
{ 4v t log (2t/a)
We now argue that [S,] unlikely to be so small. Indeed, since S, the sum of independent random variables in 1-1. 1). applying a Chernoff bound for the third time gives P([S, ESA 2 u) < 2 2exp(-u" (u/ w//t)///) /t). So, with probability 11/22, by the reverse triangle inequality,
||
|ES S JSt ESS. S / Vog 213
implying that,
|S 2 ES,
Vt 2t 2 14 2t log 2t.
This final quantity is at least D for all t by the law of total probability,
162 A
81
log(
). Now, combining what we've 'v done thus far,
A
P(E,) P(E, n H.) + H H < P( < D) + P(H;) 3/t2,
and so, for large enough such that (21), (22), and S 1) all hold, that is
162
T 2
log
a
have
E
Σ
P(E.) ST
Σ <T
3
2 2
1z
E1
12
This completes the proof.
17

---

C.2 Proof of Proposition 2
The proof is similar to that of Proposition 1, so we highlight only the differences.
The wealth process remains martingale due to the IPW weights (5). Indeed, since X and L, are Ft-1 measurable, under the null we have
F II NL (fW7)) Ft-1
-1 ALE. P(tfl) K1 +1++ XeLo HI)) K,
Moreover, as described in the text, multiplication by L, ensures that K, is nonnegative, since
|L, |/, 10/10000( w - La P (x))) L. (x))
I Liw)(X) (X.) L (x:) 1
since
L S (xP)
for each b by definition. Therefore, (K2))21 is nonnegative martingale and, as before, Ville's inequality implies that rejecting at 1/a gives level-o sequential test.
The asymptotic power follows by replacing 9r. in Appendix C.I with
hr = L. P wt).
Under the alternative, he has non-zero expected value, so identical arguments apply.
Regarding, the expected stopping time, we again argue about h instead of g.. Since [hy| S (see above), the bounds on V, and We remain they are in the proof of Proposition The bound on [E[[]]] is where the proof departs that in Appendix C.I. In this case we have
[[ S + W P:
[[-1] S Le 11).
Therefore.
B|S.] BEB B[S 1 Le(Ro m1) [| (mO 11 [E[L.).
Induction thus yields
[E[S.]|
(Po (1)
E[L:]
A
E[L.] 2 AtLint-
From here, we may replace A in the proof in Appendix C.I with Aiitt and the arithmetic remains the same. This yields the desired result.
C.3 Proof of Proposition 3
Again, the proof mirrors that of Proposition 1 so we highlight only the differences.
First let us ensure that Algorithm yields level-a sequential test. As before, it suffices to demonstrate that the wealth process a nonnegative martingale. The time-varying means do not change this fact from before:
KI E
II
(1 + 0, - F. KG AEPP P( KC--,,
-8)))))))
since. under the null, E| Fl Po = μi = Elp(()](
F- Nonnegativity once again follows from the ONS strategy.
Asymptotic power follows an identical argument as in Appendix C.I, so we focus on expected stopping time. The event E, remains the same as in Appendix C.I. We again apply Chernoff bound
18

---

to We (the values remain independent, even though they are not necessarily identically distributed), and obtain
W, S RW, + WG log < 2/,
for 1. 2 17 with probability 1 1 1/12, since again, led S 1 for each i. Similarly, EV, < 2/ with probability 1/12 for 2 17. Let the shift begin time n, and set A infeza (po(L) (1) Then [ES; 2 (1 n) A. As above, we want to find / such that
Vol 212 2 D. Rearranging and simplifying this final inequality, we see that it suffices for t to satisfy
S 2 ESA log 212 (L n)
n z /log(2t/aa.
(23)
We claim this holds for all
108
108
& 2 n max
n1
log
A
a
To this, suppose first that where
108 log
4 108 a
B
A
Then, at t. = 2n, the right hand side of (23) is
6
2n log(2n/a) S n,
A
where the final inequality holds for all 2 B, which assumed. Now suppose that B, that (23) should hold for 2 n + B. Since the left hand side of (23) grows faster than the right hand side, it suffices to show that it holds at t + B. To this end, write
t (2t/a))
(n + 8) log(2n/a + 23/a)
28 28
A
72
108
4 108 log
4 108
log
log
A
A
A
a
72
108
4 108 Aaa
[4 108
log
log
+ log log
A
Aaa
A
108
[ 108
log
3,
A
where the final inequality uses the (loose) bound log log(z) < log?
C.4 Proof of Proposition 4
First let us note that (K:?) are indeed nonnegative supermartingales. Under the null H/. we have Eng 1
PH e,
Emg Q R F = 1 AEn D2P - - c)
Moreover, for inequality,
1 | Q: The argument is similar for R.. Therefore, by Ville's
P 2 2/0) S a/2, and P(I 2: 1: 2 2/or) S a/2.
so the union bound gives P( > 1 K2 > 2/a or K2 > 2/a) < a. This implies that the proposed test, which involves rejecting if max KB) 2 2/a is a level-a sequential test.
19

---

Now, note that ONS restricts X to be in [-1/2.1/2], which is a subset of - We can therefore use similar ONS analysis as above, without needing to modify the guarantees to account for the range of A. Recall from Section C.I the definitions gr. St, and V,. Because Q₁ and RG have an extra term, we need to modily these terms for this new setting, Define
S
Σ(E 0f c);
V
Σ gi c)P
The guarantee given by (20) translates, this setting,
1 K2 2 Vi
exp { 14(V (S
(S))²
where we've simply replaced S, and V2 by S and V The same guarantee holds for K2 (there yi is replaced with -9i but makes no difference).
Results for asymptotic power (for both X- and K:(²) follow from similar arguments in Section C.I but replacing St and Vú with Si and V/. Therefore, let us turn our attention to expected stopping time. We will consider the expected stopping time of the test based on K.? Since identical arguments hold for K.P, one need only multiply the result by to get the overall expected stopping time.
Following what was done previous proofs, write E[r] = E P(E:), where E, = (log K, log(1/a)) We have
E, c ((S)) < (1))/=+())(((((//////))
log(1/V()))
((()))² <4 4 (V, + 162 +1. + Le) (log(1 (o/(()a)/// - log(1/V()))
C <(18)8 (5:) <4 1/ +/+tt
Σ ist
Iil + tc
(log(1/a)- - log(1/V())
Here we've used that V/ < V. 1e2 and | < |S + As in Section C.I, we have W. Eisele lail S 2/ and V/2 S 21 with probability 22 for all 2 17. Let H, be the event that both V S 21 and W. & 21. Note that by the reverse triangle inequality, | 2 | tc. Therefore,
E4 n H. C (|S)) < (16t + + +00++ (c²))]
C [[S]] < / + (()++((((+)))((00/))+++-0= +c22)
C [[St] < le + (e
log (21 + ()2)))
C [|Sa] < le + //8((log(1/)++
where we've used that < 1. With probability 1 1/1 1/2,
21 log(2 The minimum
I T such that IA
log(3))) is the order of / 21 log 21) le + 18(((o l3)(31))
1
T A 6)2
log
a(A - -)²2
Therefore,
E F Σ P(R) ST
Σ (P H.) + P(H)) ST
Σ ST.
3
12
GST
G>T
Note that this is under the alternative, so A and A A
D Simulation Details
Code recreate plots and run the simulations is available at https: htttps://githbb.... com combbcuggg/ auditing
teatttinn-aiiinssss fairness. Here we provide more extensive details each figure.
20

---

Figure 1. Given A, we generate the two means Ao and μr as 0.5 A/2 and - A/2. We take ((X) be distributed as Ber(Hs). (Thus, this simulates scenario for which we witness the classifcation decisions, not e.g., risk score.) We set a 0.01, so we reject when the wealth process is at least 100. We receive a pair of observations each timestep. Fach experiment was run 100 times to generate the plotted standard deviation around the mean of each wealth process.
As above, we take the distribution of model observations spr (px(( (x) to be (er()u(()) For the left hand side of Figure 2 take no (4) jn (1) 0.3 for / = ,,.., 99. At 100, we add logistic curve to 141. particular, we let
Figure2 2.
0.5
Pi (t) 0.3
t 2 100.
1 exp (250 - t)/25)
We keep (t( at 0.3 for all t. For the right hand side of Figure 2, we let both μlr and po be noisy sine functions with different wavelengths. We let
(t( sin(t/40)
+ +.4 6
for all t, where et ~ (0, 0.01). Mcanwhile,
in (1) = sin(t/20) + 0.4 + 1000
t
+ c
10
where, again, of ~ 7(0,0.01) The mean (t) thus has a constant upward drift over time. As before, assume receive pair of observations at each timestep and we take 0.01. We generate the means once, but run the sequential test 100 times order to plot the standard deviation around the mean of the wealth process.
Figures and 4. For a given sequential test and given value of a, we run (i) the test under the null hypothesis (i.e., with a fair model; we describe how we generated a fair model below), and (ii) the test under the alternative. Repeating 300 times and taking the average gives the FPR and average rejection time for this value of a. This procedure how the leftmost two columns of Figure were constructed. The final column then simply plots the FPR versus the value of a..
We used vanilla random forest for both the credit default dataset and the US census data. For the credit default dataset, the model does not satisfy equality of opportunity [39] when Y indicates whether an individual has defaulted on their loan, and A indicates whether not they have any university-lever education. One can imagine loans being given or withheld on the basis of whether they are predicted to be returned; we might wish that this prediction does hinge on educational attainment. For the census data, the model does not satisfy equality of opportunity when A indicates whether an individual has an optical issues, and Y indicates whether they are covered by public insurance. Admittedly, this example is somewhat less normative than the other. It is unclear whether we should expect perfect equality of opportunity in this context. However, we emphasize that our experiments are for illustrative purposes only. They are not meant as comments on the actual fairness or unfairness of these datasets. We interface with the census data by means the folktables package [51].
For the credit default dataset and random forest classifier, we have A |mo - مn 0.034. We have A = 0.09 for the census data. To construct the fair model (in order to test the null), we add A to the model predictions of the group with the lower mean. Thus, the distributions of predictions are different but the means are identical.
Figure follows similar experimental logic, but begin with fair model (i.e., group predictions with the same mean, generated as above), and then switch to the unfair random forest classifier at time 400.
Figure 5. We use US health insurance data [52], which is synthetic data generated based on US census information. We train a logistic regression model to predict the risk of non-repayment based on 11 covariates which include age, BMI, gender, region, and whether the individual is a smoker. We find that the predicted risks are different among males (0.235) and females (0.174), so we use as gender and use equality of opportunity
notion of group fairness.
21

---

We construct three data collection policies, T1, 22, and т3. which are probability distributions over four regions: NE, SE. NW, SW. Data-collection works by first sampling a region with the probability prescribed by Ti, and then sampling an individual in that region uniformly at random. We defined the three strategies as follows:
# (NE) 0.1, गi (NW) 0.2, Ti (SE), 0.3, mi (SW) 0.4,
T2 (NE) = 0.05, 22 (NWW = 0.15, (SE), 0.25, #2(SW) = 0.55,
33 (N) 0.05, (NW) 0.1, (S(E)) 0.15, ms(SW) 0.7.
We also ran our-betting based method with data sampled uniformly for the population, which served the comparison point. Of course, is expected from Proposition and 2, data sampled uniformly from the population yields better results. We also compared to permutation tests run on data sampled uniformly from the population. These were implemented as described above and we do not belabor the details here.
22


Reviews:
[{"review_id": "vkiLEYycJX", "reviewer": "Reviewer_am4v", "summary": "This paper clarifies the issue of fairness auditing, wherein an auditor verifies the fairness of a system through sequential interaction with it. The goal is to develop a methodology that facilitates anytime-valid tests of system fairness. Essentially, this involves devising a sequence of test statistics for the null hypothesis (i.e., the system is fair), enabling the auditor to conduct statistical tests using these statistics at any given stopping time. To achieve this, the authors design a payoff for the invalidity of observed information against the null hypothesis. A sufficiently high value of this payoff can safely lead to the rejection of the null hypothesis. Both theoretical and experimental analyses of the proposed method substantiate the efficacy of this sequential fairness testing approach.", "questions": "The existence of group-wise streams may not be feasible in practice. In a typical scenario, an auditor might receive a sequence of i.i.d. data drawn from a composite distribution that combines the group-wise distributions. Therefore, it would be more beneficial to illustrate the application in a situation where a single, mixed stream is present.", "limitations": "There are no specific limitations or potential negative social impacts that need to be addressed in relation to this paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a well-written and fascinating paper. Recently, the problem of fairness auditing has garnered attention, driven by societal demands for fair systems incorporating machine learning techniques. Sequential testing of fairness has become an essential tool for such audits. This paper delivers a robust technical solution for sequential fairness testing, offering impressive theoretical and empirical analyses of its performance.\n\nThe principal technical innovation is the reduction of the fairness auditing problem into a two-sample testing problem. This transformation facilitates the application of the established and theoretically sound methodology of anytime-valid two-sample testing.\n\nThe empirical experiments conducted in this paper effectively illustrate the potential for achieving higher power with fewer interactions, all while controlling the Type-I error in comparison to the permutation test. This evidence underscores the practicality of the proposed method.", "weaknesses": "A notable weakness is the limited innovation in methodology. The construction of the testing algorithm is merely an application of the anytime-valid two-sample testing developed by Shekhar and Ramdas. Additionally, even though Shekhar and Ramdas did not account for adjustments to time-varying data collection and distributional shifts, such an extension might be relatively straightforward.\n\nIn the context of time-varying data collection, the authors make the assumption that the density of the covariate distribution is readily accessible. This assumption, however, isn't practically feasible. Therefore, it would be advantageous to address the limitations of this assumption more thoroughly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind words on the paper.\n\nRegarding time-varying data collection, we agree that the density, $\\rho_t$, will not always be known. However, we had in mind situations in which knowing the density is feasible.  Consider, for instance, algorithms deployed across a database of users (e.g., social media, e-commerce). Precise population characteristics might be known by virtue of the fact that users must sign up for the application and provide various information. Another example comes from considering data-collection policies which use demographic features, income bracket, or general socioeconomic indicators. In this case the population level quantities may be known via state and federal statistics. \n\nThat being said, we recognize that the reviewer is correct and that we may not always have access to the density. We have therefore added an ``extensions\" section which discusses how our method can be amended when only an estimate of the density is available, in addition to bounds on its multiplicative error. The idea is straightforward: we reweight the terms $\\omega_t^b\\hat{Y}_t^b$ in the payoff function by these bounds. The resulting process can be shown to be a *super*martingale (as opposed to a martingale), and therefore results in a more conservative test in practice. The mathematical guarantees, however, still hold.   We thank the reviewer for raising this interesting question. \n\nFinally, we also agree with the reviewer regarding group wise streams. Section 3.2 in the submitted paper discusses how to reformulate our methods to handle a single stream of data. The idea is to wait to bet until there are new predictions available for both groups.\nIf multiple predictions for one group have accrued in the interim, we then bet with their average. \n"}, {"review_id": "Ay8ldCqAnQ", "reviewer": "Reviewer_sAy5", "summary": "This work proposes an approach based on recent results of super-martingales to detect when a certain predictor is demographically unfair. Studying different formulations of group fairness (such as equal opportunity, demographic parity, etc), the authors frame the problem as that of sequential hypothesis test, where a null corresponding to equalized metrics across groups. The problem is then to reject the null, if the alternative is true, as soon as possible while controlling for type-1 error. Because this is set up as a sequential hypothesis test, this implies strong conditions on the probability of false positive (i.e. for any future time). Relying on the idea of “betting”, the authors then design a pay-off function that allows the “payoff” to be a super-martingale under the null (and remain controlled), whereas the payoff grows exponentially under the alternative. While the authors derive their methodology a a “basic”/standard, they further comment on how the same approach can be minimally modified to accommodate for data collected at different rates from different demographic groups, with different data-collection policies (not iid), and under “distribution shifts”. They finally showcase their method in a couple of real world datasets, comparing with relatively simple alternative.", "questions": "1. A potentially trivial question is how to employ the same ideas to not only equal opportunity but also to equalized odds (which requires not only equal TPR but also FPRs to be the same). Is it true that in this case one can simply generalize the null hypothesis as one where both rates being the same, and the results would naturally follow? A footnote on this might be useful.\n\n2. While their approach seems to work quite nicely in practice, I wonder about the tightness of Proposition 1 (and its corollaries that follow). What are the typical constants associated with this bound? Moreover, do the authors think it would be possible to obtain a lower bound on $\\mathbb E[\\tau]$ as a function of $\\Delta$?\n\n3. As far as I understand, the experiments section did not showcase their results on being able to incorporate different data-collection policies (Sec 3.2). Could the authors comment on why this is the case? Even if the data they used involved static policies, could they simulate different policies a posteriori to showcase their results?", "limitations": "The results all hinge on the auditing process being conducted properly. The paper realizes this and appropriately mentions it in the limitations section.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The studied problem is quite important and timely, given the increasing use of predictive algorithms in society.\n- The proposed solution is relatively simple and elegant, provably correct, and seems effective in practice.\n- This paper is beautifully written, and it was a pleasure to read.\n- The experiment results are very nice and easy to understand", "weaknesses": "- The experiment results do not seem to address the time-varying data collection policies setting. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their enthusiasm regarding the work! To address the main weakness, we have added experiments for various data collection policies. We discuss the details in point 3 below, and respond to the other questions in order: \n\n\n1. We can handle equalized odds by playing two games simultaneously: One would check whether the TPRs are the same and the other whether the FPRs are the same. We thank the reviewer for raising this point; we will make sure to add a remark about it. \n2. The asymptotic notation in Proposition 1 is hiding a constant of 81. However, we did not attempt to optimize the constant; doing so could perhaps shave off a factor of 2 or more. It is also possible, using information-theoretic arguments, to get a lower bound over all sequential tests of the form $\\mathbb{E}[\\tau]\\gtrsim\\log(1/\\alpha)/\\Delta^2$. We will add a discussion of this fact to the text.  Notice that, up to constants, our upper bound is off of this lower bound by a log-factor. An interesting open question is whether this log-factor difference between upper and lower bounds can be removed, either through a tighter lower bound (perhaps specific to our test), or a tighter upper bound. \n3. Section 4 now includes several experiments that employ various data collection policies. We also use a new dataset (an insurance dataset) and a different model (logit) in order to further test our methods in new settings. We test three different data collection policies, all based on the location of the individual, which is one of NE, NW, SE, SW. In the original dataset, individuals are roughly evenly split among these locations. We test three policies, each of which places successively more weight on the SW region. We refer the reviewer to the attached pdf for figures of the results. Overall, we see that the method continues to perform well under all three policies, though it requires more steps to reject (as suggested by comparing Proposition 1 and 2). \n"}, {"review_id": "0w2k1jwBPV", "reviewer": "Reviewer_T7v6", "summary": "This work introduces practical and efficient methods for auditing the fairness of deployed classification and regression models. The methods are sequential, allowing for continuous monitoring of incoming data, and can handle distribution shifts resulting from changes in the model or the underlying population. The approach is based on recent advancements in anytime-valid inference and game-theoretic statistics. The methods are demonstrated to be effective through experiments on benchmark fairness datasets.", "questions": "I would like to discuss a thought experiment regarding a fair model that exhibits some degree of non-determinism. In this scenario, the model generally produces fair outputs for a given instance, but with a certain probability (e.g. 10%) the same instance would have an unfair output. My intention in raising this thought is to gain insights into the robustness and reliability of your framework. I am curious to understand whether such non-deterministic behavior would impact or challenge the effectiveness of your proposed framework.", "limitations": "I acknowledge that cost considerations and reaching a sufficient amount of evidence to make a decision are factors that may lead to the discontinuation of data collection. However, it is crucial to recognize that the fairness of a deployed system can evolve over time, necessitating continuous evaluation to ensure ongoing fairness. In addition, the emergence of regulatory frameworks like the AI Act in the EU emphasizes the importance of continuous evaluation, as it may become a legal requirement. These factors highlight the need for continuous monitoring and evaluation to address fairness concerns and comply with legal obligations. So even if the null is rejected at some other time in the future this could not be seen any more. How does the framework could handle this? Is this a limitation?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality:\n\nThe concept of developing a system that can continuously monitor and track the fairness of deployed real-world systems in a sequential evaluation context is a novel contribution. The idea of extending fairness evaluation beyond the development phase is an innovative approach.\n\nQuality:\n\nThe paper demonstrates a high level of quality, with well-founded theoretical reasoning and rigorous analysis. The authors present a solid theoretical foundation that supports their proposed methods.\n\nClarity:\n\nThe paper is written in a clear and understandable manner. The research problem is effectively formulated, and the theoretical foundations are explained comprehensively. The clarity of the paper contributes to its accessibility and readability.\n\nSignificance:\n\nEnsuring fairness in systems goes beyond the initial testing phase and requires continuous monitoring of deployed models. The significance of the paper lies in its contribution to the field by providing a way to quantify and evaluate the fairness of deployed models. This capability is becoming increasingly important as the need for ongoing monitoring and accountability in real-world systems grows. The paper's focus on continuous fairness monitoring and its impact on the research community make it a valuable contribution to the field.\n\n", "weaknesses": "It would greatly enhance the paper's findings to include more than two datasets for result verification. Additionally, since only one model (Random Forest) was trained on the dataset, it would be intriguing to explore the effects of different fairness methods, such as in-processing, post-processing, and preprocessing approaches, by testing multiple models. By incorporating these suggestions, the paper's results would become more robust and comprehensive, providing a more thorough understanding of the proposed methods and their performance across various datasets and models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for posing several thoughtful questions.\n\nRegarding the weaknesses, Section 4 now includes several new experiments that employ various data collection policies on a new dataset (an insurance dataset) and with a new model (logit).  We test three different data collection policies, all based on the location of the individual, which is one of NE, NW, SE, SW. In the original dataset, individuals are roughly evenly split among these locations. We test three policies, each of which places successively more weight on the SW region. We refer the reviewer to the attached pdf for figures of the results. Overall, we see that the method continues to perform well under all three policies, though it requires more steps to reject than if the streams are representative of the population. This is as suggested by comparing Proposition 1 and 2).  \n\nRegarding the reviewer's question: yes, our method allows for potentially random behavior in the model. Note that our method tests standard definitions of group fairness, which require that the expected performance of the model (on some metric) is equal between groups. According to these definitions, a model which is fair 90\\% of the time and unfair 10\\% of the time is ``unfair\": the 10\\% unfair behavior means that the average performance is no longer identical between groups. Our method uses samples of (features, labels, predictions) to test whether the expected performances are equal, and the distribution of these samples can include any internal randomness of the model as well as the distribution over features and labels. \n\nRegarding limitations: Suppose the null is initially rejected at time $t_1$. If the system changes substantially in response to this original audit, then we may simply begin a new auditing process afresh (if the system did not change, we may unsurprisingly simply reject the same null again). However, some sort of correction is required to perform multiple audits. For instance, we might run the second audit with $\\alpha/2$, the third with $\\alpha/4$, and so on in order to ensure level-$2\\alpha$ across all audits. Even better, we might consider running an online false discovery rate controlling procedure (several of these have been suggested in the recent ML and Statistics literatures, we will point to them in our paper)."}, {"review_id": "tNGCYQA6cS", "reviewer": "Reviewer_YGbH", "summary": "The paper proposes a safe anytime-valid inference (SAVI) testing procedure to audit the potential unfairness of a classifier or regression model. The paper posits group-conditioned fairness as a test of equality of means under some finite set of conditions, this definition includes several common fairness notions such as equality of odds and equality of opportunity. In this setting, the authors propose a technique allows for sequential testing of equality of means that can accommodate repeated testing, finite or infinite testing time horizons, batched testing, and importance weighted testing. The authors also provide expected stopping times for their testing procedure.", "questions": "See weaknesses above. ", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well written and structured. All the necessary information to understand the paper's contributions is provided within the main text. Several practical considerations (time horizon, batched testing, importance weighting) are clearly outlined and addressed. The method itself is extremely simple to implement.", "weaknesses": "Overall the paper is very solid. The main weakness I see is that there is no immediate way of extending these ideas to settings where equality of means may be too strict of a definition, and instead one would want to test that the absolute difference of means falls below some epsilon value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interest in the paper! \n\nWe agree that exact equality of means may be too precise a condition in practice (though we note that most other group fairness papers work with these definitions). It is in fact possible to handle a null of the form $H_0: |\\mu_1-\\mu_0|<\\epsilon$. The idea is to use two supermartingales, one to detect if $\\mu_1\\geq \\mu_0 +\\epsilon$ and one to detect if $\\mu_0\\geq \\mu_1 + \\epsilon$. We can then examine the maximum of these two processes over time, rejecting the null if either one exceeds $1/\\alpha$. Unfortunately, we were unable to discuss this in the submitted paper due to space constraints but, if the paper is accepted, we plan on using the additional page to explain this idea in more detail. "}]

Author rebuttal:
Thanks to all reviewers for their thoughtful questions and comments! 

Meta-review: All reviewers agreed that the paper should be accepted, with some reviewers describing the paper as "fascinating", "simple and elegant", "important and timely" and "a pleasure to read". Some improvements that the reviewers would like to see are a clarification of the relationship of this work to Shekhar and Ramdas, and an extension of the hypothesis test to handle a null in which the means are not exactly equal.
Decision: Accept (spotlight)