Auditing Fairness Online through Interactive Refinement
Authors: Pranav Maneriker
Codi Jay Burley
srinivasan parthasarathy
Venue: Submitted to ICLR 2023 (2023)
Keywords: fairness
metrics
verification
inference
online
monitoring

Abstract: Machine learning algorithms are increasingly being deployed for high-stakes scenarios. A sizeable proportion of currently deployed models make their decisions in a black box manner. Such decision-making procedures are susceptible to intrinsic biases, which has led to a call for accountability in deployed decision systems. In this work, we focus on user-specified accountability of decision-making processes of black box systems. Previous work has formulated this problem as run time fairness monitoring over decision functions. However, formulating appropriate specifications for situation-appropriate fairness metrics is challenging. We construct AVOIR, an automated inference-based optimization system that improves bounds for and generalizes prior work across a wide range of fairness metrics. AVOIR offers an interactive and iterative process for exploring fairness violations aligned with governance and regulatory requirements. Our bounds improve over previous probabilistic guarantees for such fairness grammars in online settings. We also construct a novel visualization mechanism that can be used to investigate the context of reported fairness violations and guide users towards meaningful and compliant fairness specifications. We then conduct case studies with fairness metrics on three different datasets and demonstrate how the visualization and improved optimization can detect fairness violations more efficiently and ameliorate the issues with faulty fairness metric design. 

Under review as a conference paper at ICLR 2023
AUDITING FAIRNESS ONLINE THROUGH INTERACTIVE REFINEMENT
Anonymous authors Paper under double-blind review
ABSTRACT
Machine learning algorithms are increasingly being deployed for high-stakes sce- narios. A sizeable proportion of currently deployed models make their decisions a black box manner. Such decision-making procedures are susceptible to intrinsic biases, which has led to a call for accountability in deployed decision systems. this work. focus on user-specified accountability of prcisionnmaking processes of black box systems. Previous work has formulated this problem as run time faireess monitoring specifications for cquuation-appoorriate fairness metrics is challenging. We con- struct AVOIR, an automated inference-based optimization system that improves bounds for and generalizes prior work across a wide range of fairness metrics. AVOIR offers an interactive and iterative process for exploring fairness violations aligned with governance and regulatory requirements. Our bounds improve over previous probabilistic guarantees for such fairness grammars online settings. We also construct novel visualization mechanism that can be used to investigate the context of reported fairness violations and guide users towards meaningful and compliant fairness specifications. We then conduct case studies with faimess metries on three different datasets and demonstrate how the visualization and im- proved optimization can detect fairness violations more efficiently and ameliorate the issues with faulty fairness metric design.
decision functions. However, formulating appropriate
INTRODUCTION
The use of advanced analytics and artificial intelligence (AI), along with its many benefits, poses im- portant threats to individuals and broader society large. Hirsch al. (020)) identify; invasion of privacy; manipulation of vulnerabilities; bias against protected classes; increased power imbalances; error; opacity and procedural unfairness; displacement of labor; pressure to conform, and intentional and harmful use as some of the key areas of concern. A core part of the solution to mitigate such risks the need to make organizations accountable and ensure that the data they leverage and the models they build and use are both inclusive of marginalized groups and resilient against societal bias. Deployed AI and analytic systems are complex multi-step processes that can produce several sources of risk at each step. At each of these stages, determining accountability in the decision mak- ing in Al processes requires a determination what cireumstances (Nissenbaum) 1996 Cooper al., 2022). A more comprehensive overview of the mechanisms that can support accountability with respect to the different stages of design of a machine learning system be found in the work of Cooper et al. (2022). We center our analy- sis on the sub problem of auditing barriers towards investigating claims surrounding mathematical guarantees of automated decision making processes. Governments across the world are wrestling with the implementation of auditing regulation and practices for increasing the accountability of de- cision processes. Recent examples include the New York City auditing requirements for Al hiring tools [Vanderford] 2022). European data regulation (GDPR 2018), accouniability bills 2019 2021 and judicial reports 2018 These societal forces have led to the emergence checklists (Mitchell et al. 2019 Sokol & Flach 2020), metrics of faimess (Verma & Rubin 2018), and recently, algo- rithms and systems that observe and audits the behavior of Al algorithms. Such ideas date back to the 1950s (Moore. 1956) but research has largely been sporadic until very recently with the widespread use of Al-based decision making giving rise to the vision of algorithmic auditing (Galdon Clavell et al. 2020). We present framework for Auditing and Verifying fairness Online through Interactive
who is accountable, for what, to whom, and under
Contextualizing wrt Nissenbaum

---

Under review as a conference paper at ICLR 2023
Concentration Bound
Monitoring System
Tree Vinultzation
Infecence
Optimization Osjectlve
Confidence ce Sots
Consitained Optimiation
Figure
Shaded nodes describe our contributions in the AVOIR framework.
Refinement (AVOIR) | AVOIR builds upon the ideas distributional probabilistic faimess guaran- tees (Albarghouthi & Vinitsky 2019 Bastani et al. 2019), generalizing them to real-world data. An overview of AVOIR is provided in Figure
1.1 PRELIMINARIES
Machine learning testing (Zhang al. 2020) is avenue that can be used to expose undesired be- havior and improve the trustworthiness of machine learning systems. Fairness criteria quantify the relationship between the outcome metric across multiple subgroups or similar individuals among the population. Formal definitions of fairness focus on observational criteria, i.e., those that can be written down as probability statement involving the joint distribution of the features, sensitive attributes, decision making function, and actual outcome. Our framework, AVOIR, supports imple- menting large range of group fairness criteria, including demographic parity (Calders al. 2009). equal opportunity (Hardt et al. 2016), disparate mistreatment (Zafar et al., 2017). and various com- binations of these criteria. As an example, suppose {0. 1] denotes the return value of binary decision function (say, candidate selection for job), and is indicator denoting whether can- didate belongs to a minority population. The 80%-rule for disparate impact (EEOC 1979 Feldman et al. 2015 is fairness criterion which states that
Pr|r = 1|s] Pr(r 1| 2 0.8
When implemented in the AVOIR DSL grammar, the above 80%-rule would be the specification E[r S==x] B[r s] >= >= 0.8. Here, the term E[r S!r]S!=s//Eip S = s] is subexpression of the specification. The smallest units involving an expectation (eg.. {[r[S!=s]) are denoted as an ele- mentary subexpressions. Our algorithm works by using adaptive concentration sets (Zhao et al.) 2016 Howard et al., 202I) to build estimates for elementary subexpressions, and then deriving the estimates for expressions that combine them. We aim to derive statistical guarantees about fairness criteria based on estimates from observed outputs. For example, let X be an observed Bernoulli r. then an assertion Φx [E[X], e, 5) over X, corresponds to an estimate satisfying
Section to intro- duce the terms.
Φx = Pr| E 5
(1)
where E[X] denotes an empirical estimate of E[ We then use assertions Φxx, byy to assert claims for expressions involving X, Y. For example, for the 80%-rule. assertions over X/Y. A specifica- tion involves either comparison of expressions with constants (eg.. X/Y > 0.8). or a combination of multiple such comparisons. Such a specification may True (T) or False (F) with some prob- ability. For given specification th. we denote the claim that P(1 F) > where å denotes the failure probability of a guarantee, Given a stream of (observations, outcomes from the decision functions), and a specified threshold probability 6, we will continue to refine the estimate for a given specification until we reach the threshold. We focus on fairness criteria that can be expressed using Bernoulli as it allows the simplification of probabilities into expectation, as Pr(r = 1] E(r]. Specifications involving variables that take more than two values can be implemented using transformations and boolean operators (examples in Appendix H.
as t/ (F,5),
2

---

Under review as a conference paper at ICLR 2023
1.2
RELATED WORK
There are a plethora of fairness criteria and subtle changes in their definition can change the im- plications on decision making (Castelnovo et al.) 202T). Practitioners need support when select- ing, designing, and guaranteeing fairness for deployed machine learning algorithms. Prior work on fairness has helped develop nuanced notions and algorithms to help train more 'fair' machine learning models. These include group fairness measures such as, inter alia, minimizing disparate impact (Calders et al., 2009, Feldman et al. 2015), maximizing the equality of opportunity (Hardt et al. (016) In contrast with group fairness notions, causal notions of fairness Kusner et al. (2017)
and individualized notions fairness Dwork et al. (2012) provide alternative statistical mechanisms
for understanding discriminatory behaviors of automated decision systems. Thomas et al. (2019)
proposed the Seldonian Framework as a generic mechanism for model users to design algorithms that help train machine learning models that can regulate them against undesirable behaviors.
We focus on the problem of detecting and diagnosing whether systems designed under any frame- work follow any prescribed regulatory constraints that supported within the grammar of AVOIR. That is, we are agnostic to the design itself; rather, we are interested in testing the adherence of mod- els to specified criteria. We use a probabilistic framework to verify this behavior. Alternative frame- works such as the AI Fairness 360 (Bellamy et al., 2019) provide mechanisms to quantify fairness uncertainty, though they are restricted pre-supported metrics. Uncertainty quantification (Ghosh) et al.] [021b]] Ginart et al. 2022) is an alternative mechanism to provides adaptive guarantees, how- ever, existing work designed for commonly used outcome metries such accuracy. FI Fl-score, etc., rather than for fairness metrics. Justicia (Ghosh et al. 202 optimizes uncertainty for fairness met- rics estimates using stochastic SAT solvers but can only be applied to a limited class of tree-based classification algorithms.
More nuanced comparison
Prior work on fairness testing is most closely related AVOIR. Fairness testing (Galhotra et al.] 2017) provides notion of causal fairness and generates tests to check the fairness of given decision-making procedure. Given a specific definition of fairness, Fairtest (Tramèr et al. 2017) and Verifair (Bastani et al. 2019) build comprehensive framework for investigating faimesss in data-driven pipelines. Fairness aware Programming (FP) (Albarghouthi & Vinitsky 2019) com- bined the two demands of machine learning testing and fairness auditing make faimess first- class concern in programming. Fairness-aware programming applies a runtime monitoring system for decision-making procedure with respect an initially stated fairness specification. The overall failure probability of an assertion is computed as the sum of failure probabilities of each constituting sub-expression (using the union bound). FP does not provide any specific mechanism for splitting
AVOIR in French means "to have" and this acronym reflects both our aspirational goal to achieve faimess in advanced analytics and AT but also reflects what is currently verifiable given a dataset, model and a faimess specification.
Frandom variable
10
10 5
(spec) ::= (ETerm) (comp-op) e (spec) (spec) (spec) V (spec)
10 8
H: 600
10-11
AH: / 600
(ETerm) ::= E E(EE)]
H:t 1000
AH: 1000
(E)
10-14
CER R (ETerm) (+,-,x, (ETerm)
0.1
0.11
0.12
0.13
0.14
0.15
8
(a) At the same concentration e, lower failure prob- ability 5 for the majority class.
(b) (E)) refers to pure expressions and (comp- op)
is any comparison operator E {>, <.
Figure 2: (Left) Failure probability of Bernoulli n.v. being concentrated around its mean for different
H = (online) Hoeffding, AH Adaptive Hoeffding. (Right) Modified Grammar for Specification.
3

---

Under review as a conference paper at ICLR 2023
uncertainty, and Verifair splits it equally across all constituent elementary subexpressions. Thus, sertion bounds for subexpressions in both FP and Verifair are split inefficiently. Proving guarantees be ameliorated by balancing it across subexpres- sions with differences in the number of observed samples. For example, consider Bernoulli r.vs X1,2 for which we derive concentration guarantees [r] - X[] 2 ai] S 6; after i; observations. 2tc². From the Hoeffding inequality, 8 2e22te We can claim tighter guarantees for X2 if t2 > t as the failure probability is lower at the same concentration e. That is, E 6 12 > 1 = 51 > 82- Varying across subexpressions to minimize the overall 8 51 + 62 allows convergence in fewer it- erations. This observation motivates us to optimize over sub-expressions and provide tighter overall concentration for compound expressions. Adaptive versions of these inequalities also have similar patterns (see Figure 2a)
for overall uncertainty across multiple groups
Clarify the con- centration.
1.3 AVOIR: KEY CONTRIBUTIONS
We summarize our contributions vis-à-vis FP and Verifair. (1) We build up AVOIR in the framework of confidence sets (Howard et al. 2021) which enables the adaptive optimization of across subexpressions. Note that FP provides examples with equal splits across two terms though it makes no specific prescription of splits. Verifair splits uncertainty equally across all elementary subexpressions. (2) The confidence sets framework allows us move away from assuming known data distribution or alternatively, fitting density estimator over the population prior to fairness testing, required in Verifair. (3) We augment the bound propagation rules to facilitate the online optimization process and allow propagation of constraints along with assertions at each iteration. (4) We build an inference engine that supports automated inference of propagation rules for wide range of metrics. In Section 3 we provide examples of inference over specifications involving over two subexpressions, which are not passible without extending the implementations provided by previous work. As a bascline, also implement bound inference rules from Verifair (denoted AVOIR-V -FF.. (5) We support interactive diagnosis of fairness specification violations using visual cues associated with convergence of subexpressions. We demonstrate the use of these cues help drive the design of specifications in Section 3.2 which show how a user may have audited their original claim and refined mathematical bounds.
New contributions section.
2
AVOIR FRAMEWORK
2.1 LANGUAGE SPECIFICATION
We describe AVOIR's s Domain Specific Language (DSL) used for specifying fairness metrics. Con- crete examples of implemented specifications in AVOIR's DSL are provided in Section 3 We focus on binary decision making functions: their outputs can be characterized by Bernoulli r.v.s. Note that for such Bernoulli r.V. X, [[ = Pr[X- 1] and hereafter, these are used interchangeably. Fairness specifications are implemented as decorators over decision functions. Consider a decision function f X > (0, 1}. where
(X)...., ,x) denotes a real-valued input vector. We use R = f(X) simplify the remainder of the definitions.
To support expressions beyond those that produce binary outputs, we use the grammar to construct Bernoulli r.v.. For example, a y-threshold based real-valued output, Ht' = (R > v) and a multi-class output, for class j. Rt' (R = j) correspond to Bernoulli r.v..
Expanded defini- tions
Expressions involving R and X; act as the arguments <B> to construct an <ETerm>, For example E| > 0 X + X2 >> a] is an elementary subexpression and an <ETerm>>
e terms represent constant real values, used, for example, as bounds for expressions. The grammar provided in Figure 2b can be then used construct various group fairness criteria. We modified the grammar from prior work to include two additional operations. First, we added a given argument to the expectation term, which allows a user to specify conditional probabilities directly, in contrast to specifying it as ratio of joint/marginal probabilities.
E(A V (B b)) E B b)
E(A, given -B=b))
4

---

Under review as a conference paper at ICLR 2023
which is used represent B[A[B b), simplifying expressions used for group fairess specifica- tion. Additionally, we add binary comparison operators <, >; ==, =, which further simplifies the process of writing specifications.
2.2 PROPAGATING BOUNDS
Generating the bounds for specification requires propagating guarantees from elementary subex- pressions. Assuming that observed values for each <E> correspond to an underlying random vari- able X, a probabilistic guarantee dx consists of an empirical estimate E[X], concentration bound xx, and a failure probability 6x, such that Pr[[E[X]= E[x]] 2 ex] & 8x We refer to expressions fairesss specification will typically consist of mul-
of this form elementary subexpressions. tiple such elementary expressions, denoted as compound expressions. For compound expressions, we must infer the implied guarantees that can be provided, with corresponding constraints. Each inference rule corresponds to derivation in the DSL grammar. Inference rules have preconditions and postconditions that follow the general expression
express
Ufrlr (0.
where e denotes claim for subexpression, for a <spec>, E and are the mean and concen- tration terms associated with a subexpression claim, C' denotes a constraint. For example, consider starting with the assumptions
Updated the lan- guage to show the assumptions
(E [E[X), Ex, 6x), Y (E[Y), sy, ey, 5y). Then we have
[ + E
[ + B(y])| [E[X] E[X] + (B E|Y)
- [ - E [ + [ [
Sx + EY
ie., we can derive X + Y [E[X + Ex + &r,, 6x + 8y). Some derivations also lead to rules that require constraints. For instance, assume X (B[X),ex (x,,xxx,x) B[X] > Then
have Pr[X < [[ EX] - 5 If we add the constraint that E[X] EX c, have Pr[X < c 1 -, 8, thus,
X (x
v
(T,8x)
under the constraint [ [
x 2 c}
The full set of inference rules required for the DSL is provided in the appendix (Figure) 5). The im- plementation in AVOIR follows these rules but can be extended to other rule inference templates that support the DSL. We note that these rules extend the ones implemented by VeriFair (VF BBstani et al. 2019) with constraints that enable the optimizations required in AVOIR (see Appendix A
2.3
OPTIMIZING BOUNDS
2.3.1
AVOIR ALGORITHM
The pseudocode for optimization procedure in AVOIR described in the appendix (Algo- rithm []. The input to the algorithm is the reporting threshold probability A and specification db. We then infer a symbolic optimization problem is inferred corresponding to the failure probabili- ties and constraints derived from concentration bounds. At each step, the ORSERVE (X) function is called with new observation of every elementary subexpression and observed output. The running updated. The final optimization problem OPT corresponding
mean and counts of observations to each specification is a nonlinear constrained optimization problem. We use the COIN-OR im- plementation of IPOPT (Wächter & Biegler 2006), accessed though the Pyomo (Hart et 201T) interface to solve this problem at each step. If a solution is successfully found for OPT, the algo- rithm terminates, with the estimate for the specification having reached the required threshold. If no solution is found, the estimates continue to be updated with d; A for each elementary subexpres- sion. The main intuition behind the algorithm to create a confidence sequence corresponding to
Veerifair
5

---

Under review as a conference paper at ICLR 2023
the estimates at each time step. The OPT corresponding to specification:
min
==1
(2)
s.t. 9h (01 m: E E[XI]. E(X,.)) S EN
8 1
where ge and Ex are the functions/hounds derived using the transformations carried out through the DSL inference rules (further details in Appendix A.2).
Definition 1. For 8 E (0, (1 - 6) confidence sequence is a sequence of confidence sets, usually intervals (CI,) say (I,, R.) S IR satisfying uniform convergence guarantee. After observing the tth unit, we calculate updated confidence set CI, for unknown quantity of interest Og with the coverage property Pr(vt 2 1, 1,0,: : 0g Cl:) 2 1-8 (Howwad et 2021).
In this paper, we focus on the mean of r.v.s E[X] that constitute estimates for elementary subex- pressions as the quantities of interest. We use adaptive concentration inequalities to construct these confidence sequences. Any adaptive concentration inequality that can be applied to arv. X {0, such that
Px| - E| 2 E(t, 8
(3)
can be used in AVOIR. Here, [X] denotes the empirical estimate of [[ after the 8th observa- tion. For the purpose of comparison with previous work (eg., VF), we use the Adaptive Hoeffding Inequality (Zhao et al. 2016),, which will be referred to as AIN hereafter.
Theorem 1. The sequence of estimates generated by AVOIR form confidence set.
The proof follows from the fact that AVOIR always estimates using a failure probability higher than that which is provided by AIN, and hence applying a union bound ensures that the estimates are confidence set. The full proof is provided in Appendix C
Corollary 1.1. The estimates for the overall specification vp form a confidence sequence converging xp (b, A), F).
Proof. We initialize the main specification with the required failure probability A. The termina- tion condition requires E9; 5; S A. From Theorem we can infer that the confidence sequence corresponding to the termination achieves the required threshold A, and therefore, is valid.
2.3.2 IMPROVEMENTS OVER BASELINE
In all prior work (Alarghoothhi et al. 2017 Albarghouthi & Vinitsky 2019 Bastani et al. 2019), d; for each elementary subexpressions is set to A/n, where the number such term in the specifica- tion. This simplification is carried out using the assumption AB == 5, = V, for all elementary subexpressions. As we do not make this assumption, we can prove the following key theorem.
Introduce A,
We define the specification stopping time T for confidence sequence as the smallest time such that, given a threshold A and specification v. we can terminate any inference algorithm to claim that Pr[vt 2 1, 1/2 T 2 A, where viT is the estimate of vp at time T.
Definition 2.
Theorem 2. Given a threshold probability A for a specification b. let the stopping time for AVOIR be T and stopping time with the As assumption be T Then T S T
See Appendix for the proof.
Consider a Bernoulli r.v R corresponding to the output of a binary decision function, with being indicator of class membership. Let X V and Y -s be r.vs corresponding to positive decision for the majority and minority classes, respectively. Suppose we aim estimate gi X
Concrete Example
ET
We demonstrate the improvements possible using our approach by instantiating this example with data. Suppose we want the upper bound of the failure probability A 0.1 for the specification. Consider set of observations such that [[ 0.8, nx 1550 and Eyy] 0.5, ny 310.

---

Under review as a conference paper at ICLR 2023
-10-2
AVOIR-08 AVOIVVI
6x - by
6x + by S 0.1
Ex +ey 0.2
6
13
yy
1.2
1.1-
3.5
4.5
5
5.5
6x
-10-2
1.0
2000 2500 3000 3500
(a) No solution exists with additional constraint As ōx = dy A/2 common assumption in prior work.
(b) Bounds for first half of a gender-fairnes speci- fication generated by AVOIR-OB and AVOIR-VE
Figure 3: (Left) AVOIR finds solution for a theoretical scenario with 6x + +oy S under constraint dataset, the vertical lines show the step
Ex εy S er (Right) For RateMyProfs, which the methods can provide a guarantee of failure for the upper bounds with A <= 0.05.
Figure 3a shows that no solution is feasible for the optimization problem with Ag. However, AVOIR find solution. For the optimal solution, 82 R 2.356, which aligns with our intuition from section 1.2 about allocating higher failure probability to terms with the majority of observations. The optimization problem inferred by AVOIR:
min 8x 5y
4x
6x + By S B[X]
E er
(4)
0 s 6x 1
2.4 VISUALIZATION FOR INTERACTIVE REFINEMENT
Using our specification framework as a backend, we built an interactive application for analysis and refinement of specifications provided in our grammar. Specifically, fairness specifications can be naturally parsed into a tree because of the structure of the grammar. Each node of the tree represents some sub-expression in the syntax tree of the overall specification. These nodes allow user of AVOIR to interactively audit and tune the specification definition. To create the visualization, we use Vega (Satyanarayan et al. 2015), a declarative JSON-based visualization grammar. We log the estimates during runs of AVOIR and then output the grammar in a tabular JSON-form that contains a row for each grammar element and its associated evaluations. This tabular data is used by our Vega specification to produce the visualizations. By selecting one of the nodes in the syntax tree, user can see plot of the evaluation values associated with the selected grammar element. This allows for comparison of multiple grammar elements. The ability to analyze and compare these evaluation values provides context surrounding specification violations, and assists the user in interacting with and deciding how refine specification We provide detailed example of how these interactions can help AVOIR users choose an appropriate fairness metric in Section
3 CASE STUDIES
The following text describes two real-world scenarios for AVOIR. We implement Verifair inference rules in the AVOIR (denoted as AVOIR- (VOIR-VF) framework, which allows us to sidestep the assumptions of having known data generating distribution, making it more efficient than Verifair. We denote AVOIR-OB as the implementation which also utilizes the constraints and optimization framework. An important case study the COMPAS dataset can be found in Appendix G
Explaining AVOIR-V VF
7

---

Under review as a conference paper at ICLR 2023
3.1 RATE MY PROFS
In this section, provide detailed black-box machine learning model (ML) based case study a real-world dataset. In this case study, we use the rate my professors (RMP) dataset released by Keymanesh al. (202T). This dataset includes professor names and reviews for them written by students in their classes, ratings, and certain self-reported attributes of the reviewer. Ratings are provided on five-point scale (I-5 stars). We use the preprocessing described in Keymanesh et al. (202T) to infer the gender attribute for the professors. This dataset is divided into an 80-20 split (train-test). We then train SERT-based transformer modellDevlin et al. (2019) on the training split. We use the implementation from the simpletransformers" package. The loss function chosen is the mean-squared error from the true ratings. On the test set, we track a gender-fairness specification in the model outputs:
package.
(E[r > 3 gender F] H[r > gender M < 1.2) (E[r > 3 gender M)] / E[r > 3 gender F] > 0.8)
We the failure probability A 0.05. OPT is after each batch (5 items/batch). Figure 3b shows that AVOIR-OE can provide a guarantee in 2.5% fewer iterations than AVOIR-VE Note also that the OB guarantee provided tries optimize for the failure probability while staying under the required threshold, remaining closer to the required threshold in subsequent steps.
3.2 ADULT INCOME
In this case study we the Adult income dataset (Kohavi, 1996) which has been used frequently in prior fairness-related work. The historical dataset labels individuals from the 1994 census as having high-income (>> 50, 000 year) not (S 50, 000 year). In this case study, we look a column of data as a black-box measurement (internally, we use a materialized view, details Appendix [...
US Federal laws mandate against start our analysis with is a group fairness property that monitors the difference of the proportions of individuals with recorded as male that have a high income to females that have high income should be less than 0.5. In addition, we ensure that the difference between individuals with race marked as white and those without should have difference of less than 0.5. The associated specifi- cation is given below, where h is an indicator for whether an individual is high-income is the binary classification output our model:
and based discrimination. Thus, the specification
(E[h
scx=M] - E/h scx=F] < 0.5) &
[E[h
race=W] - E[h race!=W] < 0.5)
In this example, we set the failure threshold probability A = 0.15
When run with this specification, the generated materialized view cannot achieve the required bound. We can then use our iterative refinement visualization tool to analyze different components of the specification. A developer would first interact with the left subtree of the specification. Due to paucity of space. this visualization is presented in Appendix G.2 The plot for the corresponding data shown Figure showws that guarantees cannot converge under the threshold with the given number of data samples. The developer can now choose to either reduce the guarantee (i.c. reduce d) or increase the threshold. Next, analyzing the right subtree, the race group fairness term can be guaranteed to be under the threshold (Figure (b).. Using this information, the developer can make an intelligent decision to increase the threshold on the group fairness for term for sex. Suppose they increase it to 0.55 and rerun the analysis. OB is able provide guarantee at this threshold within 870 steps, whereas VF can provide at 960 steps, demonstrating a relative improvement of about 10.35%. Additionally, the optimal 5 split across the terms are (0.135, 0.36 10*) which is far from the equal split allocated by VF. The reason for this split is because increasing the threshold for the first time provides the optimizer with additional legroom better distribute the failure probabilities between the two terms.
"htps//simplcrranfommrs.aai 'OB Optimized Bounds
8

---

Under review as a conference paper at ICLR 2023
1.00
1.00
0.75
0.75
0.50
[[N(s-)--ihjsmi]] <85
Kblraww) [(bjrt
0.25
0.25
0.00
-0.25
-0.25
-0.50
-0.50
-0.75
-0.75
-1.00
200
400
600
8b0
1000
Osservad
Csservad
(b) Group fairness for race (difference ratio of high income earners) in right subtree for initial specifica- tion.
(a) Group faimess for Difference in ratio of high income earners subtree for initial specification.
Figure 4: (Left) Red dotted lines the upper bound of the value cannot be guaranteed to be under the threshold at the specified failure probability. (Right) Guarantee possible with given data.
DISCUSSION & FUTURE WORK
The case studies presented in the previous section demonstrate the ability of our tools to provide vital context when deciding how to refine model fairesss specification. Although this contex- tual information makes decisions easier, is not always clear how one should alter specification in light of violation and its relevant context. To assist in these decisions, we currently examining ways work to suggest edits that are likely to achieve the desired intent of developer. Using our vi- sual analysis tool for refinement, we can gather edits from developers and then use that data to learn iterative changes to the syntax tree of the specification. In addition to improving the usability of our tools for making fairness specification refinements, we also envision more scalable framework. Our case studies look at single model with respect to a single dataset. However, real-world de- ployment of machine learning often contain many clients with models and datasets that may evolve and drift over time. We take it as future work to study the efficient monitoring of machine learning distributed context, enabling horizontal scala-
Non stationary data future work
behavior with respect fairness specification bility. We believe techniques such as decoupling the observation of data and the reporting results from monitoring of the results are promising and can lead the desired scalability.
CONCLUSION
We present the AVOIR framework for easily defining and monitoring fairness specifications online and aids in the interactive refinement of specifications. AVOIR is easy to integrate within modern database systems but can also serve as a standalone system evaluating whether black box machine learning models are meeting specific fairness criteria specific datasets (including both structured and unstructured data) as described in our case studies. AVOIR extends the grammar from Fairness Aware Programming Allarghouthh & Vinitsky (209)) with operations that enhance expressiveness. In addition we derive probabilistic guarantees that improve the confidence with which specification violations are reported. To assist in refinement of specifications, we develop interactive visual analysis application within AVOIR. Through case studies, we demonstrate that AVOIR can provide users with insights that contribute directly refinement decisions. Our framework builds the foun- dation for further improvements to the fairness specification, auditing and verification workflow. We plan to extend this work to provide intelligent specification refinement suggestions support distributed machine learning settings. We also plan explore the use of AVOIR for fair ranking problems and tailored database integration.

---

Under review as a conference paper at ICLR 2023
6 REPRODUCIBILITY
To enhance the reprodueibility of our work. on the theoretical side, all proofs (with the necessary assumptions) are provided in the appendix. Specifically, proofs for the inference engine are in Ap- pendix A and proofs for the correctness of bounds are provided in Appendix C Theorem 2 which shows how AVOIR improves over prior work is proved in Appendix [ To reproduce the results of the case studies in the paper, each case study is encapsulated inside a Jupyter notebook. These notebooks are attached along with the source code for AVOIR. In addition, all datasets used for generating results for the case studies are also attached in the submitted supplementary documen- tation. Finally, the model weights used for the RateMyProfs study for exact reproduction are pro- vided in a dropbox folder hosted at httptt:s/////ttt www. dropbox. com/ httm:shh/noo4ssswkw33.... AABthgLMa ATA.AM/.....AAAA333111
REFERENCES
Aws Albarghouthi and Samuel Vinitsky. Fairness-aware programming. In Proceedings of the Con- ference on Fairness, Accountability, and Transparency, pp. 21 211-219, 2019.
Aws Albarghouthi, Loris D'Antoni, Samuel Drews, and Aditya V Nori. Fairsquare: probabilis- tic verification of program fairness. Proceedings of the ACM on Programming Languages, (00PSLA):1-30, 2017.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In Ethics of Data and Analytics, pp. 254 264. Auerbach Publications, 2016.
Abolfazl Asudeh, H. V. Jagadish, Julia Stoyanovich, and Gautam Das. Designing fair ranking schemes. In Peter A. Bonez, Stefan Manegold, Anastasia Ailamaki, Amol Deshpande, and Tim Kraska (eds.), Proceedings of the 2019 International Conference on Management of Data, SIG- .OOD Conference 2019, Amsterdam, The Netherlands, June 30 July 5, 2019, pp. 1259-1276. ACM, 2019.
Osbert Bastani, Xin Zhang, and Anmando Solar-Lezama. Probabilistic verification of fairness prop- erties via concentration. Proceedings of the ACM on Programming Languages, 3(0OPSLA): 1-27, 2019.
R. K. E. Bellamy, K. Dey, M. Hind, S. C. Hoffman, S. Houde, Kannan, Lohia, J. Martino, S. Mehta, A. Mojsilović, S. Nagar, K. Natesan Ramamurthy, J. Richards, D. Saha, P. Sattigeri, M. Singh, K. R. Varshney, and Y. Zhang. Ai fairness 360: An extensible toolkit for detecting and mitigating algorithmic bias. IBM Journal of Research and Development, 63(4/5):4:1-4:155 2019. doi: 2411://RD..2219.9922
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18.
IEEE, 2009.
Alessandro Castelnovo, Riccardo Crupi, Greta Greco, and Daniele Regoli. The 7oo of fairness metrics in machine learning. arXiv preprint arXiv:2106.00467, 2021.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias recidivism prediction instruments. Big data, 5(2):153-163, 2017.
US Congress. Hr 223 2231-algoiithmic accountability act of 2019, 2019.
A Feder Cooper, Emanuel Moss, Benjamin Laufer, and Helen Nissenbaum. Accountability in an algorithmic society: relationality, responsibility, and robustness in machine learning. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 864-876, 2022.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18633/v//N19-11 1423. URL https:
7/acl anchlantholooo ogy. www.hhollly..ogg////1/g///// 9-
10

---

Under review as a conference paper at ICLR 2023
William Dieterich, Christina Mendoza, and Tim Brennan. Compas risk scales; Demonstrating curacy equity and predictive parity, Northpointe Inc, 7(4), 2016.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214-224,22 2012.
The U.S. EEOC. Uniform guidelines on employee selection procedures. March 1979.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 259-268, 2015.
Avi Feller, Emma Pierson, Sam Corbett-Davies and Sharad Goel. computer program used for bail and sentencing decisions was labeled biased against blacks. it's actually not that clear. The Washington Post, 17, 2016.
Gemma Galdon Clavell, Mariano Martín Zamorano, Carlos Castillo, Oliver Smith, and Aleksan- dar Matic. Auditing Algorithms: On Lessons Learned and the Risks of Data Minimization, pp- 265-271. Association for Computing Machinery. 2020.
Sainyam Galhotra, Yuriy Brun, and Alexandra Meliou. Fairness testing: testing software for discrim- ination. In Proceedings of the 2017 11th Joint meeting on foundations of software engineering, pp. 498-510, 2017.
Bishwamittra Ghosh, Debabrota Basu, and Kuldeep S Meel. Justicia: stochastic sat approach to formally verify fairness. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 7554-7563, 2021a.
Soumya Ghosh, Q Vera Liao, Karthikeyan Natesan Ramamurthy, Jiri Navratil, Prasanna Sattigeri, Kush Varshney, and Yunfeng Zhang. Uncertainty quantification 360: A holistic toolkit for quantifying and communicating the uncertainty of ai. arXiv preprint 2:Xiv:2106.014 2021b.
Tony Ginart, Martin Jinye Zhang, and James Zou, Midemon: Deployment monitoring for machine learning systems. In International Conference on Artificial Intelligence and Statistics, pp. 3962- 3997. PMLR, 2022.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in neural information processing systems, 29, 2016.
William E Hart, Jean-Paul Watson, and David L Woodruff. Pyomo: modeling and solving mathe- matical programs in python. Mathematical Programming Computation, 3(3):219-600, 2011.
Dennis Hirsch, Tim Bartley, Arvind Chandrasekaran, Srinivasan Parthasarathy, Piers Turner, Devon Norris, Keir Lamont, and Christina Drummond. Corporate data ethics: Data governance transfor- mations for the age of advanced analytics and ai (final report). In Appeared at the Privacy Law Scholars Conference (also available as SSRN Abstract: 3828239), 2020.
Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonpara- metric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055-100 2021.
B Justice Srikrishna. A free and fair digital economy: Protecting privacy, empowering indians, 2018.
Moniba Keymanesh, Tanya Berger- Bolfer-Wolf, Micha Elsner, and Srinivasan Parthasarathy. Fairness- aware summarization for justified decision-making. arXiv preprint arXiv:2107.06243 2021.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent Trade-Offs in the Fair De-
termination of Risk Scores. In Christos H. Papadimitriou (ed.), 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs). pp.
Dagstuhl, Germany, 2017. Schloss Migstuhl-Leibnic http://arggp..ooauo.oooeooooo//s
Zentrum fuer Informatik. ISBN 978-3-95977-029-33
doi: 10.42300LIP http:://roppn http:/dooss....s.uhuoooo http:/stwwhhddddou/ueeeeeeeeee wtw.te
URL

---

Under review as a conference paper at ICLR 2023
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A Recision-tree hybrid. In Kdd, volume 96, pp. 202-207, 1996.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
Margaret Mitchell, Simone Wu, Andrew Zaldivar, Parker Barnes, Luey Vasserman, Hutchinson, Elena Spitzer, Inioluwa Deborah Raji, and Timnit Gebru. Model cards for model reporting. In Proceedings of the conference on fairness, accountabilityy and transparency, pp. 220-229, 2019.
E.F. Moore. Gedlanknn-xperriments on sequential machines. Automata Studies, Princeton University Press, 129-153, 1956.
Fatemeh Nargesian, Abolfazl Asudeh, and H. V. Jagadish. Tailoring data source distributions for fairness-aware data integration. Proc. VLDB Endow, 14(11):51192532, 2021.
Helen Nissenbaum. Accountability in a computerized society. Science and engineering ethics, 2(1):
25-42, 1996.
Central Digital 2021.
Office URL
and
Data.
Algorithmic transparency standard,
Nov
aloosttindd- /tcps::/www/ gov. ut//governmeen//coleec......
European Parliament. 2018 reform of eu data protection rules. European Commission, 2018.
Arvind Satyanarayan, Ryan Russell, Jane Hoffswell, and Jeffrey Heer. Reactive vega: streaming dataflow architecture for declarative interactive visualization. IEEE trunsactions visualization and computer gruphics, (2(1):659-66 668, 2015.
Kacper Sokol and Peter Flach. Explainability fact sheets: framework for systematic assessment of explainable approaches. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 56 2020.
Chenkai Sun, Abolfazl Asudeh, H. V. Jagadish, Bill Howe, and Julia Stoyanovich. Mithralabel: Flexible dataset nutritional labels for responsible data science. In Wenwu Zhu, Dacheng Tao, Xueqi Cheng, Peng Cui, Elke A. Rundensteiner, David Carmel, Qi He, and Jeffrey Xu Yu (eds.), Proceedings of the 28th ACM International Conference on Information and Knowledge Manage- ment, CIKM 2019, Beijing. China, November 3-7, 2019, pp. 2893-2896. ACM, 2019.
Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere. Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468):999- 1004, 2019.
Florian Tramèr, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, Jean-Pierre Hubaux, Mathias Humbert, Ari Jucls, and Huang Lin. Fairtest: Discovering unwarranted associations in data- driven applications. In 20/7 IEEE European Symposium on Security and Privacy (EuroS P), pp- 401-416, 2017. doi: 10. 109/EuroSP..007..299
Richard tainty.
prompts uncer- URL https://wwwt ws wtt.c//mtaatttee/c/ccc new yorks landmark aaikk--iii bias- law prompts annerttainty
Vanderford.
New york's
landmark ai bias law
WSJ. 2022.
Sahil Verma and Julia Rubin. Fairness definitions explained. 2018 ieeelacm international work- shop on software fairness (fairware), pp. 1-7. IEEE, 2018.
Andreas Wächter and Lorenz T Biegler. On the implementation of an interior-poin filter line- search algorithm for large-scale nonlinear programming. Mathematical programming, 106(1); l): 25-57, 2006.
Anne L Washington. How to argue with an algorithm: Lessons from the compas propuulic debate. Colo. Tech. IJ, 17:131, 2018.
12

---

Under review as a conference paper at ICLR 2023
Ke Yang, Julia Stoyanovich, Abolfazl Asudeh, Bill Howe, H. V. Jagadish, and Gerome Miklau. A nutritional label for rankings. In Gautam Das. Christopher M. Jermaine, and Philip A. Bernstein (eds.). Proceedings of the 2018 International Conference Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pp. 1773-1776. ACM, 2018.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp- 962-970. PMLR, 2017.
Jie M. Zhang, Mark Harman, Lei Ma, and Yang Liu, Machine learning testing: Survey, landscapes and horizons. IEEE Transactions Software Engineering, pp. 1-1, 2020. doi: 10. 109/TSE. 2019.2962027.
Shengjia Zhao, Enze Zhou, Ashish Sabharwal, and Stefano Ermon. Adaptive concentration inequal- ities for sequential decision problems. Advances in Neural Information Processing Systems, 29, 2016.
A INFERENCE RULES
In Figure 5 provide of rules that be used determining the constraints and guarantees associated with specification. We represent
XOY: (E,,, = Pr ( O E - E 2 e) < 5
where ④ represents a binary operator. Constraints are represented in curly brackets ()-
The proof of correctness for each inference rule starts from the assumptions above the horizontal line and derives the assertions below. These proofs use ideas similar to those Bastani et al. (2019). We reproduce the proofs in Appendix A. here for completeness. Note that the assertions the base case (elementary subexpressions) can be arrived at by applying the Adaptive Hoeffding INequality, (AIN).
AIN
A.1 INFERENCE RULES WITH CONSTRAINTS
In Section 2.2 we provided the proofs for X KYYYA X c. In the following provide the proofs for the remainder of the inference rules.
Product Starting with øx = x (E ex, ex, 6x), Φx Y Ely 5y). First, from union bound, both of these hold true with probability least 1 8x 5y. Then,
[[
X
X
+ E [
X
+
E
X
X
X
+
We have
E[
B[XY] [[ ]|
(as X, Bernoulli)
|
- E[X]B[]]]
[ E Y - E[Y) + EY
E[X))
< E[X]I - + [ - E(XI)
+
Ey)sx
E Ey |||]| + EXEY
Therefore, X x V: E[ + + EY +v)
13

---

Under review as a conference paper at ICLR 2023
X: (E[X), Ex 5x): Y sy,
X Y [E[X] + B + Ey, 8x + 5y)
X [E Ex 5x Y E SY, 5y)
X
[E BY ExEY
E[ [[]]Ex: 8x + ox)
X: (E,s,) 8) -
x KE,EE,, E)
(Inverse)
(Inverse Constr.)
X-1: E
X-1: E
B(E-e) =j 8) ,1B =}
E(E-s)
X (E, EEEE> (True)
X: E, E, 6) E+ (False)
+ = X >c:::0 (T,88
+ x (F,6)
X: (E,
(True Constr.)
== X > c: (T, 8), {E -
X EE,
(False Constr.)
b= X < c: (T, {E + < c)
e1 (BI, 81),)).8 1/2 (B2, 52)
Vi (BI, 81), 2/2 (B2, 62)
(and)
(or)
1 A 4/2 (BB, A B2, 81 + 82)
1 V 2/2 (B) V B2, 81 + 82) 1 (B1, 51), CC }k), 12 : (B2, 62), {C21 (c2
constr.)
1/ 2/2 (B1 A B2, 81 +2)) (C11, 1k: Cm.
1 (B. 1. ) (C11...,, 1k) th2 (B22, 82)
(or constr.)
1 V 1/2 (8B, B2, 81 + 82), (CI (C21....2m)
Figure 5: Inference rules used to guarantees for expressions. The inference rules for each compound expression build on the union bound, triangle inequality, and structural induction approach described by Bastani et 2019).
14

---

Under review as a conference paper at ICLR 2023
Inverse/Inverse constr. Assume X (E, and E- - 0. Instead, in the constrained case, start with only the prior assumption i.e., X (E. c, 8) Then,
| = E [
X + X
E X
X [
S ex
i.c., [[[]]| Ex + [[X]]. Also,
E[x] E[X]
[X[]] - [[
E X [
|X
X
IE [XX 5x
where the last step follows from the previous derivation and if [[[]] Ex > O. The latter condition enforces that the sign of the incquality does not change. VF adds this as precondition; we add it as a post-constraint.
Boolean Operators Starting from 1 (b,, 51), 1/2 (b2, 02), can apply the union bound for 1 A 4/2, 1 V 4h2 to derive the rules for and/or. Similarly, constraints follow the semantics specified by the rules they also follow from the union bound.
A.2 INFERRED OPTIMIZATION PROBLEM
For given overall specification vh, suppose (Ei, i E (1......) represents the concentration bounds associated with each constituent elementary subexpression. Using the aforementioned infer- ence rules, we can derive the overall 8T Σ 8,, along with a set of (say) K constraints
gk En, E 11).
E(X,) I EK
where
E = -
E[X,)]]]
denotes the maximum allowed margin for the thth inequality subexpression (i.e. having form <ETerm> <comp-op> c). The objective is minimize the overall failure probability é7. The overall optimization problem can then be formulated as shown 2 having n optimization variables and 2n K constraints (bounds inputs required acceptable upper bound of failure probability A. If the solution to the optimization problem 67 = Σ; 6, I A, then the optimization can conclude with the required confidence in the proved guarantee. At this point, the developer may choose to terminate AVOIR. However, using Corollary 4.1 they may continue to run and refine the estimates.
ó; provide the 2n constraints). A developer using AVOIR
B CONCENTRATION BOUNDS
The adaptive Hoeffding inequality (Zhao et al. 2016 Bastani al. 2019).
Theorem 3. Given a Bernoulli random variable x with distribution Px. Let (X, e i..d samples of X. Let
E = Σ X
Let 'T be a random variable on NU (00} such that Pr(T < 00) 1, and let
log (logı.1 t ++ 1) log (24/5)
e(5,t) t) =
t
15

---

Under review as a conference paper at ICLR 2023
Then, for any d E R., we have
Pr Pr| E[X] S
c(6, 7) 2 1
Theorem provides mechanism for choosing the stopping time using arbitrary methods for fixed 5. Note that in general, any adaptive concentration inequality suffices; we use the Hoeffding inequal- ity that does depend on the empirical variance but is frequently used in scenarios dealing with bounded r.v.. However, we use confidence intervals to visualize the evolution of sub-expressions (and overall specification) over the sequence of observations. For doing so, we require an additional result
Proposition 1, Lemma 1) Let S. Ei= X be random walk Theorem 4. (Zhao et al. 2016 from i..dd random vartables X1...... X₂ ~ D. For any 5 > 0,
Pr[ST 2 f(T) S
for any stopping time T if and only if
Pr[En, St 2 f(t)] 8
Corollary 4.1. For any > O,
Pr Pr|E [[X]]][[]] S <(6, T)
for any stopping time T if and only if
Pr Vt. [X[] - [[X]| S c(0, t 2 8
Proof. Follows directly from applying Theorem to Theorem
Intuitively, Theorem holds since we can choose adversarial stopping rule for T that terminates as soon as the boundary for e(,, 1) is crossed (Zhao et al. 2016). Thus, when we establish a bound with stopping rule, as long as the underlying distribution remains unchanged, the bound will hold prior to and after the stopping rule is enforced. Theorem 1.1 implies that once we choose an optimal bound for each subexpression, we can extend the bounds derived using Theorem 3 following observations with the guarantees for the subexpressions still holding true.
C CONFIDENCE SEQUENCES
In this section, we show that the estimates generated from AVOIR form a confidence set (Theo- [e. First, we assume the existence of concentration sequenee for the mean of each elementary subexpression (eg., Theorem 3 can provide one). That is, need function et,, such that
Pr|vt 2 1, [X] E[X] s ett, 6x)1 2 8x-
(5)
For convenience of exposition, we denote such adaptive inequality functions AIN. For any AIN to be usable with AVOIR, we require s(t, 8) to be monotonically non-increasing in ó and n. We expect this be the case for most AIN, since increasing the number of observations of increasing the failure threshold should allow for additional concentration around the mean. For example, the adaptive Hoeffding inequality (Theorem 3) follows this assumption. Second, we assume that, except in degenerate cases, AVOIR terminates (see corollary 4.2 for termination criteria). We now prove Theorem
Proof. First, will prove that the estimates for elementary subexpressions are confidence quence. Following this, using the inference rules from Appendix [A] we will show that the estimates for every compound expression also confidence sequance.
16

---

Under review as a conference paper at ICLR 2023
Elementary subexpressions XI,...,Xp: At stopping time Tetet
Consider specification e consisting of elementary subexpressions
o == X;
(6)
be the stopping time estimates. Then, from the termination criterion, a solution to the optimization problem OPT exists, i.e.
A
Σ 8x;
The sequence of bounds claimed by AVOIR
(E(A,t), t< T, (E(8x, T2T
Ex, (t)
(8)
From equation and the optimization constraint 8; E [0, we have A 2 8x,- From the non-
decreasing behavior AIN
<(A,1) S (.)..
(9)
Now
Pr[vt 2 - ex.
=1 Pr 2 E E[X,] (t)
= =1-P Pr
U E [X|] > (t)
121
T-1
= -1-P Pr
B|X,]| Ex, (x) U U
[X. Ex, (0)
1=1
12T
(associativity of U)
T-1 U
= 1 Pr
U
-[x] -[x]] e(5x..))
t=1
12T
(From
= =1 Pr
U t=1
E [ - E[x,]I > t)
E[X.]| E (6xx, U
U 12T
E X1] - E[X,]| e(xx,.
(Using
T-1
= 1 Pr
[E - B[X,]| e t]]} U U
[E[X] - E[X]]] > e(6x,,
(=1
(21
(Rearranging)
2 1- Pr
( - E[X,]] e(xx,
(21
Pr Et 2 [X[
E[X,]| e(5x,;
2 1 8x,
where the last step follows from the definition of the adaptive concentration bound used. Thus, ex; (t) defines ox, confidence sequence for TE(X.).
17

---

Under review as a conference paper at ICLR 2023
Compound subexpressions Consider non-specification compound <ETerm> Cj consisting of elementary subexpressions with indices Cj = f2. jast) as the decision r.v.,, ie, ....:,......JJ!!!
Xj, ..... j jus- Note that Cj is multiset the same expression could occur multiple times within Cj. At stopping time TT
ob, (IE &c,,)
(10)
where [T] ec, are the corresponding values computed through the inference rules, In general, we denote by
E, (t), (t) INFER(
(11)
the values inferred at time step t, where INFER denotes the inference rules. Now,
Pr 2 1, [[C, E[C,]| sc,
M
< Pr
U 2, 1 Li=1
(From
<
Pr
31 2 1, ~xxx
(union bound)
iEC;
Σ
Pr
31 1, [ E, [x 8xx; (1)
(definition of o'x,,
iEC
8x,,
(elementary subexpressions)
iEC,
S 6c,, Therefore EC, (t) defines 1 dc, confidence sequence for B[C,]
(applying 11 for t = 7)
A similar proof can be constructed for any <spec>, Consider any specification th.. Let
w (br. (4), der (1))
(12)
where (t)(t) (t) S F} the inferred value and ò (t) corresponds the confidence for the corresponding to the index multiset B = {[ki,... kD } ]. Denote by, as the true value of the, and 6%r the inferred threshold at stopping time T. From INFER, we have
assertion at time Let the elementary subexpressions involved be ,,, Xxp
(t()), 8 (t) INFER( Xx, .....
(13)
We have
Pr 2 1, by & by (T)
Pr
3t > 1, X
(From L
[==1
Pr
31 1, xx
(union bound)
icB,
Σ Pr
3t > 1, - Sxn, (8)
(definition of d'x
iEB,
8XL1
(elementary subexpressions)
iEB,
S0x Thus, byz (t) a 8o, confidence sequence for byz
(applying |] for T)
D OPTIMALITY
Proof. Under As. at the stopping time T 8,
A/n, with
Σ 5 = A.
18

---

Under review as a conference paper at ICLR 2023
As 6," propagated using INFER (without constraint rules), we know that they must satisfy the
constraints of the optimization problem 2
At time T+ AVOIR would find solution o7 such that
minimizes Σ 6,
Σ
A
Thus, AVOIR would terminate at step T+, but may find feasible solution at an earlier step, i.c. T Tt.
Corollary 4.2. Under mild conditions, AVOIR terminates finite steps with an assertion over the required specification.
Proof. We know that the stopping time T < T the stopping time for AVOIR. Thus, AVOIR would terminate whenever Verifiar can. For completeness, we provide the conditions under which Verifair terminates. Note that E IR corresponds to a constant threshold involved in specification, also presented in the grammar and bound proagation rules.
Clarified
For every subexpression Cj occurring in the specification such that it is involved in the inverse or inverse constr. rules (i.c., [[Ca] E[CA] + 0, C2 +
For every subexpression C. such that it occurs True/False type inequality (such as C₁- c), E|CA] # Ck #c
E IMPLEMENTATION
We built a python library to create specifications that can be implemented as a decorator over de- cision functions. The front end interactive application was implemented using stream and the visualizations were built in Vega Satyanarayan et al. (2015). Each term the DSL implemented through corresponding python class. New input/output observations are monitored to update all the terms in a specification. Inference for evaluating the value and bounds carried out via operator overloading in these classes. In line with previous work (Albarghouthi et al. 2017) Bastani al.) 2019 A Albarghouthi & Vinitsky/ (219)) on distributional verification, we use rejection sampling for conditional probability estimation.
E.1
VISUAL ANALYSIS
Using specification framework a backend, we built an interactive application for analysis and refinement of specifications provided in our grammar. Given a user provided machine learning model. dataset, and specification the application simulates stream of observations to the provided model. Following the simulation, a visualization provided that represents the specification as a syntax tree where each node of the tree corresponds the visualization.
element of grammar. Figure shows
Note that for each observation made by machine learning model, the specification is evaluated to check for violations. Each grammar element that makes up the specification evaluated as well, and thus each grammar element is associated with the value it evaluates for given observation. For specifications <spec>, there is a boolean value associated with each observation, whereas an expectation term, <ETerm>, associated with a real value. By selecting one of the nodes in the syntax tree, user can see plot of the evaluation values associated with the selected grammar el- ement. We call these plots evaluation plots and two can be observed time each with shared scales along the horizontal axis which denotes observations over time. This allows for comparison
'hups///treammlit.o//
19

---

Under review as a conference paper at ICLR 2023
Algorithm AVOIR Algorithm
Input: A, v
A, Specification A
Output: T, time step when the value of can be guaranteed with probability
1: for X,
do
2:
9x, = A
> Set initial value Vi Sum of observations
3: Sx. = 0
4: nxx; =0 0
b Number of observations
5: end for
6: T' O
b Time step
7: Initialize OPT.
Initialize Optimization Problem (Fig. 5
8: procedure OBSERVE(X)
9: for X; do
10:
Sx. = Sx. +
nx; = nxx; +1
E[X,]= = Sx,/nx.
13:
Initialize dx, symbolic variable
14:
Assign e(6x,, nxx)) symbolic variable
15:
end for
16:
Propagate 5x, using the inference rules
17:
Initialize constraints 9R in OPT: using the computed values
18:
87 Sol ve ( (T
19:
if O7 S A then
20:
dx,
87 X.
return T. T end if
22:
T T= +
24:
end procedure
of multiple grammar elements. The ubility to analyze and compare these evaluation values provides context surrounding specification violations, and assists the user in deciding how to refine a speci- fication. The case studies in section 3 demonstrate the usefulness of the context provided by these visualizations.
F AVOIR IN DATABASE SETTING
In the database literature researchers Nargesian et al. (2021), have explored an approach to tailoring data integration strategies to ensure that the data set used for analysis has an appropriate represen- tation of relevant (demographic) groups and it meets desired distribution requirements. The authors describe how to acquire such data in an approximate cost-optimal manner for several realistic set- tings. This work is orthogonal to work and yet AVOIR can potentially integrate with the authors approach to examine if fairness criteria are being met during the integration process. In other studies on fairness researchers Yang al. (2018); Asudeh et al. (2019); Sun et al. (2019), have considered the problem of personalized fair ranking functions and discuss approaches to determine if a proposed ranking function satisfies a set of desired fairness criteria and, if does not, suggest modifications that do. AVOIR attempts to solve a more general purpose problem (not limited to any particular fairness criteria) and is agnostic to the specific model (treats it as a blackbox). While have not examined the performance of AVOIR for fair ranking problems, it is something we plan to examine the future.
To demonstrate how AVOIR can be integrated within database system we use panda dataframes simulate the application of AVOIR in the database setting. Specifically, we wrap pandas dataframes with a python 'Database' class, and provide query mechanism create materialized views. Queries are provided in the form of python functions that take a dataframe as input and output corresponding dataframe. The corresponding view thus generated can be updated with in- scrtion/update/ddlletinn of data. The specification is added as a decorator inside the refresh function,
httpss///aaddssyyyaaa.ooo
20

---

Under review as a conference paper at ICLR 2023
high, rcome
Ejjighinncmm tee_Nale T--EPihh.nne noome neee_emmale
(nnegti Mew Snsgtuinoomm Farrate 1]
high income
Prrphirrcomee teoo Pamale
sox, Fomole
(ET EEPig, 13x6.8) (EMigh 1).iggt......ooooooo Eluihhincoom
race, Write
Incohm race, rase_Vitte Eipippinssm Jnooma mon, nouLWhe
(etrmn I noc Vhita 1]- Enrphiincome bace, nait_ = 0.51
highh income
EPigh, iocom
Figure Tree of initial specification before refinement in the adult income dataset.
allowing AVOIR to track specifications in database setting. Note that this tie-in with pandas is only for ease of implementation; the inference engine and optimization can be extended to any database engine.
G ADDITIONAL CASE STUDIES
G.1 MATERIALIZED VIEWS
A materialized view is constructed by querying the dataset to select for employees of the federal govermment. We simulate the materialized view using a panda dataframe wrapped python class to monitor updates and run AVOIR for any monitored specification.
G.2 INTERACTION THROUGH VEGA
Figure 6 shows a subtree of the specification visualized through Vega. A developer analyzing this spec can click on the top pink node to see the evolution of the sex faimesss part of the specification and superimpose the threshold. The threshold is set to be evaluated with every 5 new data points added to the materialized view. Clicking on the corresponding element in the right subtree, the developer see Figure 4b
G.3 COMPAS RISK ASSESSMENT VIA MATERIALIZED VIEWS
The Correctional Offender Management Profiling for Alternative Sanctions (COMPAS) recidivism risk score data is a popular dataset for assessing machine bias of commercial tools used to assess a criminal defendant's likelihood to re-offend. The data is based recidivism (re-offending) scores derived from a software released by Northpointe and widely used across the United States for making sentencing decisions. In 2016, (nggwin al. (2016) released article and associated analysis code critiquing machine bias associated with race present in the COMPAS risk scores for a set of arrested individuals in Broward County, Florida over period of two years. The analysis concluded that there were significant differences in the risk assessments of African-American American and Caucasian individuals. Northpointe pushed back in report (Dieterich et al.) (0166) strongly rejecting the claims made by the ProPublica article; instead, they claimed that Angwin et al. (2016) made several statistical and
hhtps:/ppanasspyddaaaoogg
21

---

Under review as a conference paper at ICLR 2023
E[briskreeidd- (=C) Ebbris/reciiddd (=AA
Efresdoofiriic & r-c) / dieecd-ooiiia d-jinikkkkkkkkoooo 1-AA)
1.0 20.3
280
Via
(a) (ProPublica) COMPAS, "Sample A" False Positive Rate Bias specification required to above the 10% = 0.9 threshold converges to value that can be guaranteed to be under the required threshold.
Dbserved
(b) (Northpointe) "Sample analysis by Northpointe using False Discovery Rate that op- posed the ProPublica reports.
Figure 7: COMPAS dataset case study.
technical errors in the report. In this case study, we use AVOIR to study the claims made by the two aforementioned reports. First, start with the data released by ProPublica and load it into a pannds-- simulated DB. We then create a materialized view that corresponds to the preprocessing steps used in the publicly available ProPublica analysis notebook We look "Sample A" (Dieterich al. 2016), where the analysis of the "not low" risk assessments using a logistic regression model reveals high coefficient associated with the factor associated with race being African-Ameriea In terms of fairness metric, this corresponds to false positive rate (FPR) balance (predictive equality) (Verma metrics. The associated specification in AVOIR grammar would be
Rubin 2018)
E[hrisk E[hrisk race=Caucasian & recid=0) < 1.1
rac==African-Ammrrian recid=0]
Where hrisk k is an indicator for high risk assessments made by the black-box COMPAS tool as defined by (Angwin et al. at. (2016), recid i indicator for re-offending within years of first arrest, and 10%-rule is used as the threshold. We choose a failure threshold probability of A 0.1, with the optimization run after every batch of 5 samples. AVOIR finds that when the decisions are made in sequential, online fashion, the assertion for violation of the specification cannot be made with the required failure guarantee.
By analyzing the components using the visualization tool, optimize since the lower FPR in the denominator (FPR for Caucasian individuals) increasing the overall variance and limiting the ability to optimize for guarantees. We follow this analysis by using the reciprocal specification, i.e.,
glean that AVOIR is unable to
E[hrisk
race=Caucasian & recid=0] / E[hrisk race=African-American & recid=0] 0.9
find that indeed, the specification violated with a confidence of over 1 A 0.9 proba- bility, and AVOIR can detect this violation within about half the number of available assessments (3350 steps) when run in an online setting. Figure 7a demonstrates the progression of the tracked expectation term. Thus, if deployed with the corrected specification, AVOIR would be able to alert Northpointe of violation/potentiall--biee
decision making tool.
The Northpointe report (Dieterich et al. 2016) makes several claims about the shortcomings of this analysis, but one of the primary claims is that Angwin al. (2016) used an analysis based on "Model
22

---

Under review as a conference paper at ICLR 2023
Metric Name
Detinition
DSL
|
Dwark et al. 2012
Prusscivve Fariyy
Pı(Y 1i - [B
houldechova
gqeal Upsartunity
Pr = =, 1 BBl-:
Hardt 2016
Equaiized O0ds
Prid= = 1.6 P 1p =;
Hardt et 2016
0
Table 1: Examples of supported metrics.
Errors" rather than "Target Population Errors". In Fairness metric terms, this refers to the difference between a False Positive Rate (FPR) balance vs False Discovery Rate (FDR) balance, i.e. balancing for predictive parity over predictive equality. In probabilistic terms, the difference amounts to com- paring P(Y 1 0,g g 2) (FPR) vs P(Y 0 g 1,2) (FDR), where y refers to the decision made by the algorithm, Y refers to the true value, and = 1, 2 reflects group mem- bership (Verma & Rubin (2018). This analysis run on the dataset subset dubbed "Sample B". To test their hypothesis, we run reproduce the corresponding preprocessing steps and run both versions (numerator and denominator being Caucasian) versions the corresponding specification under the same setup as earlier. We find that despite the point estimate being within the required threshold, neither version can guaranteed with the required confidence with the given data. Due to paucity of space, we describe only one of the two variants with the corresponding figure (Figure 7b
E[ r E(recid=0 race=African-Ammrrian & hrisk] >> 0.9
race=Caucasian & hrisk] /
We note that the Northpointe report (Dieterich et al., 2016) does not provide confidence intervals for their claim either. Further, even though the report does not release associated code, the point estimates of the False Discovery Rates (FDRs) match those present in the report which increases our confidence in AVOIR-based analysis.
The back and forth exchange has been the subject of much discussion in both academic and journal- istic publications (Feller et al.) 2016 Washington 2018). Seminal work by Kleinberg al. (2017) proved the impossibility of simultancously guaranteeing certain combinations of fairness metrics. While AVOIR cannot solve this problem, usage can help provide explicit guarantees on defined metrics. The specification grammar also provides simple mechanism for independent replication of claims. We conclude this case study by noting that AVOIR lends itself successful analysis that is not possible with the Verifair implementation available online.
H SUPPORTED METRICS
We provide non-exhaustive list of statistical group-based fairness criteria and show an exact/ap- proximate equivalent in the AVOIR DSL in Table [ Verma & Rubin (2018):
We use the following notation, adapted from
G: Protected sensitive attribute. For demonstration purposes, will use the values and f to denote majority and minorty classes.
X: Features describing each individual
Y: True label for X
S: Probability Pr|Y XX G] predicted for certain class
d: Predicted decision for X, usually derived from
A threshold to test the specification. For ratios based approximations, this would be number + for some small e > 0. For difference based approxiamtions, this number would be some small > 0. When multiple terms present, to denote the 7th threshold.
New section
23

---

Under review as a conference paper at ICLR 2023
We assume that the decision function f tracked by AVOIR signature that takes X, G, Y as input and produces or d as output. Note that in their python implementation. = would be replaced by and by the given keyword.
24


Reviews:
[{"review_id": "Op082ldrU2", "reviewer": "Reviewer_Gatp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper improves on previous methods for automated fairness auditing. Their main contributions are improving the concentration bounds, extending the language to specify fairness metrics, and creating a visualization tool. \n\n- For complex fairness metrics/expressions, the authors propose to distribute error rates unequally by solving an optimization problem. These can reduce the number of samples required to verify the conditions. \n- Building on prior work, the authors provide an automated way to specify and track the fairness metrics. \n- They also create a visualization tool for practitioners to visualize which sub-expressions are violated. ", "summary_of_the_review": "These works heavily build on prior work, and the novelty is unclear. The main novelty in this work is improving the number of samples required to audit fairness,  which seems to be limited. Moreover, the paper is hard to parse and unclear in many places. Thus, I suggest rejection. ", "strength_and_weaknesses": "Strengths:\n- The observation that different (sub-)expressions usually have different power (N) is interesting, and the empirical benefits from improving concentration bounds are significant. \n- Authors create an automated system leveraging existing tools, which can be helpful in practical settings. \n\nWeaknesses: \n- The paper is unclear at many points and hard to parse:\n\t- The definition and difference b/w different terms, such as spec, expression, claim, etc., needs to be clarified. It would be good to explain all these with concrete examples in one place, in a preliminary or background section.\n\t- The example in sec 3.2 is unclear. How does X: ..., Y: ... translate to  X \\pm Y. \n\t- Some figures do not have legends and labels, making the results hard to interpret. \n- Corollary 4.2 is unclear. What is c? Moreover, it appears that the algorithm would not stop/cannot detect if the specification is \"almost surely\" violated in a limited number of samples, i.e., if Alg 1, line 18 has no solution, it would keep running. So if the expectation converges to some other value than what is specified, i.e., fairness constraints are not satisfied, it won't terminate or throw an error. \n- No human/practitioner study is done to assess the usability of the visualization & auditing tool.  \n\nQuestions & other minor errors: \n- Fig 3b, 4a, 4b : What are x and y axis, legends in 4a 4b?\n- The fairness specification in sec 4.1 has a typo?\n- What does the heading adaptive optimization mean in Table 1?\n- Why do authors use $\\delta_i=\\delta_j$, when prior works have used $\\Delta/n (as also mentioned in the paper)$? How do the results change with $\\Delta/n$\n\nTypos: \n - stochaistic -> stochastic (Sec 1, second last para)\n- \"choose an a suitable\" -> choose a suitable (sec 1, last para)\n- Sec 3.1, first para \"We then infer a symbolic optimization problem is inferred corresponding\"\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Jcr1cAL9HUm", "reviewer": "Reviewer_Guzx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper presents AVOIR, a fairness audit framework that allows the generation of fairness probabilistic guarantees for any models and fairness metrics. AVOIR also uses a tree-based visualization to help users better the fairness specification.", "summary_of_the_review": "The paper needs improvement in its presentation and clear justification of the novelty. ", "strength_and_weaknesses": "Strengths:\n1. The paper studies the fairness audition problem, which is of high importance.\n\n2. AVOIR system is easy to integrate with the existing ML system with arbitrary fairness metrics.\n\n\nWeaknesses\n\n1. The paper’s presentation needs significant improvements to allow readers outside the fairness audition area to understand. While reading the paper, I had a hard time understanding the technical details of the proposed algorithm and the experimental results. This area contains a lot of background information from software testing, and a lot of the paper’s results are based on Albarghouthi & Vinitsky (2019). Besides, the paper does not provide a background information section or related work section, making it more difficult to understand the technical details.\n\n2. The Novelty needs to be clarified. In table 1, compared to all other works, the only advantage of the system is visual refinement (e.g., tree visualization). In this regard, the contribution is not that significant. Besides, I found that the framework proposed in the paper is similar to Albarghouthi & Vinitsky (2019). According to Table 1, AVIOR shows advantages over Albarghouthi & Vinitsky (2019) regarding Adaptive Optimization and Visual Refinement. However, adaptive optimization has been integrated into Ginart et al. (2022) and Ghosh et al. (2021a). If visual refinement is only the improvement over the previous work, then the contributions are incremental.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ImpFR0BELpO", "reviewer": "Reviewer_nDjC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper designs a DSL for specifying/verifying probabilistic guarantees for Bernouilli rv-related fairness metrics in online settings. The authors claim that their approach improves over prior work in terms of having more efficient optimization.", "summary_of_the_review": "The paper contains some interesting ideas, but it is not written very clearly and has some issues with precision that make it difficult to fully evaluate both the scope and correctness of the contributions, as well as to fairly evaluate why this work is a substantial improvement over prior work. It is possible that the main issue is lack of clarity in the writing. If that is the case, then a deep re-write would resolve most of my concerns. However, I do not think that is the limit of the problems. As noted above in weaknesses, I think the paper needs deeper empirical investigation/demonstration to really benefit 1) the contribution 2) support of the theoretical claims of better efficiency 3) comparison to prior work. Unfortunately, as the paper stands, I do not think it is of high enough quality to be accepted to a top-tier conference. The ideas are interesting and the paper seems to have the potential to pass this bar, but needs reworking in order to do so.", "strength_and_weaknesses": "Strengths:\n\n1. The problem the authors have set out to solve is an important one. Having good tools for identifying runtime fairness violations in deployed systems is an important goal. \n\n2. The authors acknowledge that this, however, is not enough. There needs to be a way to interact with / effectively debug violations to improve the power of auditing tools.\n\n3. The authors also make the contribution that this can be done efficiently (at least, more efficiently than prior work).\n\nWeaknesses:\n\n1. Unfortunately, due to lack of specificity / a preliminaries section that adequately specifies the setup, it is not entirely clear what exactly the extent of the contribution is.  For example, 2.1 needs to be more precise. It would be useful to specify a set of fairness criteria that are in scope, rather than speaking generally about fairness criteria. Work on Rawlsian social welfare does not seem to be in scope for this work, yet is arguably in scope in terms of the generality of how fairness criteria are written about in 2.1. This makes 2.1 (strictly speaking) incorrect. A dedicated preliminaries section would help fix this. \n\n2. More precision in the math terms would also be helpful. For example (1) should define (above or below) what the types are for the symbols being used. What is r? Should we consider s to be applicable only to binary settings, or to multi-group fairness settings? Is the example fairness criterion something that the paper actually will use? If not, why is it there? If the definitions that are in scope are those from Verma and Rubin, can (briefly) a set of such definitions be described rigorously, with an example metric related to that set?\n\n3. I think the authors need to explain more as to why this work provides a significant improvement over Bastani, et al. Notably, in Table 1, the improvement of AVOIR seems to be visual refinement. But is that actually enough of an improvement / a contribution to make this paper novel? It's not entirely clear, as presented. A dedicated related work section (as opposed to peppering some related work into the intro, and some in section 2) would be useful, and them some comparison in terms of evaluation (to verify the claim of improved efficiency) would be useful here. Moreover, if visual refinement is to be evaluated as a significant contribution, this should be featured more heavily in the paper. There is not a single example of this in the main paper, and the one in the Appendix is not adequately explored/ explained to justify its utility.\n\n4. 2.3.2 seems to contradict the claim about operating on Bernoulli r.v.'s. \"Arbitrary\" suggests that any metric could be used, but this is not true. This feels like a contradiction from a lack of precision.\n\n5. I do not understand figure 3b. What does it mean to have Avoir-Verifiair? Verifair is talked about like a prior work baseline, but this suggests some combination? (ultimately, this became a bit clearer at the beginning of Section 4, but I lost the thread here and had to work to find it again, and I'm not sure I completely did). \n\n6. What exactly is being interactively tuned? This is said at a high level and not entirely made precise, in my opinion. I had hoped to see perhaps one long empirical example of online refinement. Perhaps one in which distribution shift is induced, so that we can see how the system catches it quickly in relation to prior work (this would support the theoretical claims being made). Without one, it is not clear what the benefit of this system is (and this matters a lot, since there is a claim about runtime improvement).\n\nNits, suggestions (I believe the following would improve the paper, but they do not impact my score):\n\n1a. The claims in the abstract and intro concerning accountability do not seem correct to me. The link between audits and accountability has been explored in various works, none of which are cited here. Importantly, this link is not a given (as it seems to be suggested here). Audits are not necessarily constitutive of accountability. The concrete takeaway here, for this framing to work effectively, is to defer to those that have studied this problem in depth, rather than claiming this as a given without substantiating it. For an example on the complicated relationship between accountability and auditing, I would read sections of and cite Helen Nissenbaum's update to her classic paper that was at FAccT last year, \"Accountability in an Algorithmic Society\" https://dl.acm.org/doi/abs/10.1145/3531146.3533150\n\n1b. Related to the above, the paper makes claims in the introduction about the challenges of accountability for ML, and has a paragraph that talks about a subset of problems with ML that make it special/difficult in unique ways. These claims, as written, are not adequately substantiated. Again, many others study this as a problem in itself. It is worth deferring to this work via citations, and then highlighting the two examples given in the intro as the ones that are relevant to this paper. Again, see paper example in 1a (and associated related work citations in that paper).\n\n2. Many typos. Please proofread. One example, \"stochaistic\" (mispelling) in intro, second to last paragraph.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2rbYgVa9j5", "reviewer": "Reviewer_1wit", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work introduces a framework/interface that allows users to (1) define fairness-based rate constraints/metrics, and (2) monitor these metrics / work to refine the initial constraint definitions (if necessary). The work also provides case studies showcasing the framework. \n\n1. Define fairness-based rate constraints/metrics. The grammar used in the framework is based on the one used in Fairness Aware Programming with the addition of two extensions: direct specification of conditional statements, and the addition of some binary operators. Moreover, probabilistic guarantees based on union bound and interval algebra are provided that provide tighter confidence bounds on statistical metrics of interest. \n\n2. Monitor these metrics / work to refine initial constraint defns. The framework includes a way for users to see a visual of the statistical metrics that may be in violation of fairness. A case study is shown that details how this information can help users choose an appropriate fairness metric. ", "summary_of_the_review": "I recommend rejection pending clarifications from the authors. \n\nWork related to the broader subject of high probability fairness guarantees seems to be missing from the text. As such, it is hard to determine how similar some of the key contributions are to prior work, and therefore hard to determine the novelty of the work. These contributions also seem to be the most substantial (e.g., the additions to the grammar and the visualization proposed are contributions but more minor in scope). \n\n\n\n", "strength_and_weaknesses": "Strengths \n- Many sections of the work are well-written, including the introduction and some proofs in the appendices (A and B). The examples provided throughout the text help build intuition, e.g., Figure 2. \n- The bound propagation and optimization techniques seem useful, especially for problem settings in which high probability fairness guarantees are necessary. \n- The visualization techniques proposed offer additional guidance to users that interested in determining the specific fairness metric for the application at hand. \n\nWeaknesses \n- Missing related work on techniques with probabilistic fairness guarantees. The only related work in this space mentioned is AVOIR, but there are numerous other techniques in fair ML that propose probabilistic fairness guarantees. For example, the Seldonian framework ('Preventing undesirable behavior of intelligent machines'; Thomas 2019) is a family of algorithms that provides high confidence fairness guarantees; and 'Offline contextual bandits with high pr guarantees' (Metevier 2019) introduces a framework that uses interval arithmetic & the union bound to produce tight(er) bounds on statistical metrics of interest. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2-ou3Mjcxvc", "reviewer": "Reviewer_Uuem", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper investigates the problem of auditing fairness automatically, online, and in a black-box manner. It proposes AVOIR to address this problem for multiple fairness metrics. It claims to optimize the previously used adaptive Hoeffding inequality to decrease the sample complexity. AVOIR also comes along a visualisation and computation schema to compute and communicate the fairness violation. The paper also presents case studies on real-life datasets to justify its usefulness.", "summary_of_the_review": "The paper addresses an interesting and timely problem of auditing fairness automatically, online, and in a black-box manner. Though the paper spends a lot of effort to compare with the related work, it does not concretely state its contributions (specifically sec 2.3.1 is poorly written). I think that the paper should be rewritten and polished to explicate the contributions with concrete mathematical statements. Otherwise, it is presently hard to evaluate the methodology now.", "strength_and_weaknesses": "Strength\n- The paper addresses an interesting problem of auditing fairness automatically, online, and in a black-box manner. This extends the previous fairness auditors by one or more extents.\n- The paper presents an extensive summary of the related works and points the gaps where they can be improved.\n- The paper performs elaborate case studies and develop a tool to visualise the results.\n\n\nWeakness and questions:\n- The paper suffers from poor readability. The core contribution is not properly stated. More focus has been paid to contrasting the work with existing literature while failing to convey a coherent story.\n- It is not clear why the number of iterations is less for the proposed framework than the existing work, VeriFair.\n- In Sec 2.2, what is F?\n- Section 2.3.1 is written very poorly. There is no concrete mathematical statement to follow. What do you mean by sub-expression? What do you mean by Bernoulli random variables X_{1, 2}? What is the implication of the subscripts {1, 2}? What is the definition of failure probability?\n- Can you elaborate on this statement: \"We can claim stronger guarantees for X 2 if t 2 > t 1 as the failure probability is lower at the same concentration\"?\n- In Sec 3.3.2, while no solution is feasible for the optimization problem with A_\\delta, AVOIR finds a solution. What is the reasoning? What is A_\\delta here?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject