Achievable Fairness on Your Data With Utility Guarantees
Authors: Muhammad Faaiz Taufiq
Jean-Francois Ton
Yang Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: fairness
dataset
accuracy-fairness trade-off
uncertainty quantification
Primary area: fairness
TL;DR: We provide a methodology for reliably characterising the fairness properties of datasets.

Abstract: In machine learning fairness, training models that minimize disparity across different sensitive groups often leads to diminished accuracy, a phenomenon known as the fairness-accuracy trade-off. The severity of this trade-off inherently depends on dataset characteristics such as dataset imbalances or biases and therefore, using a uniform fairness requirement across diverse datasets remains questionable. To address this, we present a computationally efficient approach to approximate the fairness-accuracy trade-off curve tailored to individual datasets, backed by rigorous statistical guarantees. By utilizing the You-Only-Train-Once (YOTO) framework, our approach mitigates the computational burden of having to train multiple models when approximating the trade-off curve. Crucially, we introduce a novel methodology for quantifying uncertainty in our estimates, thereby providing practitioners with a robust framework for auditing model fairness while avoiding false conclusions due to estimation errors. Our experiments spanning tabular (e.g., Adult), image (CelebA), and language (Jigsaw) datasets underscore that our approach not only reliably quantifies the optimum achievable trade-offs across various data modalities but also helps detect suboptimality in SOTA fairness methods.

Achievable Fairness on Your Data With Utility Guarantees
Muhammad Faaiz Taufiq" ByteDance Research
Jean-François Ton
ByteDance Research
faaiz. tww.figgyyeeedcnceccooo com
jeanfrancoss@yyteddeecccom
Yang Liu
University of California Santa Cruz yangl iangliuSucsc.edu
Abstract
In machine learning fairness, training models that minimize disparity across differ- ent sensitive groups often leads diminished accuracy, phenomenon known the fairness-accuracy trade-off. The severity of this trade-off inherently depends dataset characteristics such dataset imbalances biases and therefore, using a uniform fairness requirement across diverse datasets remains questionable. To address this, we present computationally efficient approach approximate the laimess--cccuaat trade-off curve tailored to individual datasets, backed by rigorous statistical guarantees. By utilizing the Cou-Only-Train- Once (YOTO) framework, our approach mitigates the computational burden of having to train multiple models when approximating the trade-off curve. Crucially, we introduce a novel methodol- ogy for quantifying uncertainty in our estimates, thereby providing practitioners with robust framework for auditing model fairness while avoiding false conclu- sions due to estimation errors. Our experiments spanning tabular (e.g., Adult), image (CelebA), and language (Jigsaw) datasets underscore that our approach not only reliably quantifies the optimum achievable trade-offs across various data modalities but also helps detect suboptimality in SOTA fairness methods.
Introduction
key challenge in fairesss for machine learning is train models that minimize disparity across
various sensitive groups such as race or gender [ 35 10. This often comes at the cost of reduced model accuracy, phenomenon termed accuracy fairness trade-off 36 32) This trade-off differ significantly across datasets, depending on factors such as dataset biases, imbalances etc. [
faiuresy-fairness
To demonstrate how these trade-off's are inherently dataset-dependent, we consider simple example involving two distinct crime datasets. Dataset A has records from a community where crime rates uniformly distributed across all racial groups, whereas Dataset B comes from community where historical factors have resulted in a disproportionate crime rate among specific racial group. Intuitively, training models which racially agnostic is more challenging for Dataset B, due the unequal distribution of crime rates across racial groups, and will result in a greater loss in model accuracy compared to Dataset A.
This example underscores that setting a uniform faimess requirement across diverse datasets (such as requiring the fairness violation metric to be below 10% for both datasets), while also adhering to essential accuracy benchmarks is impractical. Therefore, choosing fairness guidelines for any
Coorrsponniing authors: faaiz, taufig@bytedance. com and jaunfrancodsebyyteddeec.co
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Empir optimally
Empir trade-off using optimally modal evaluated spll
Impirial pa trade-off using suboptimally traind model
Permisibble tradealff region (Our mithod!
Suboptimal accuracyffaimess trade-off
0,08
Dem Partyy
0.07
0.06
0.06
0.04
Uniikely to achievable
0.62
0.63
0.66
0.65
Accuracy
0.36
0.58
0.00
0,62
0.64
0.56
Accuracy
Accuracy-fairees trade-offs for COMPAS dataset (on held-out data). The black and red curves are obtained using the same optimally trained model evaluated on different splits. The blue curve is obtained using a suboptimally trained model. The green area depicts the range of permissible fairness violations for each accuracy, pink area shows suboptimal accuracy-fairness trade-offs, and blue shows miiikel--t-bbeaccheee ones. (Details in Appendix F.5)
Figure 1:
dataset necessitates careful consideration of its individual characteristics and underlying biases. In this work, we advocate against the use of one-size- fil fairness mandates by proposing a nuanced, dataset-speeific framework for quantifying acceptable range of accuracy- sauuacyyfaireess trade-offs. To put concretely, the question we consider is:
Given dataset, what is the range of permissible fairness violations corresponding to each accuracy threshold for models in a given class H.?
This question can be addressed by considering the optimum accuracy-fairess trade-off, which shows the minimum fairness violation achievable for each level of accuracy. Unfortunately, this curve is typically unavailable and hence, various optimization techniques have been proposed to approximate this curve, ranging from regularization R 33
adversarial learning 45 40)
However, approximating the trade-off curve using these aforementioned methods has some serious limitations. Firstly, these methods require retraining hundreds if not thousands of models obtain good approximation of the trade-off curve, making them computationally infeasible for large datasets models. Secondly, these works do not account for finite-sampling This is problematic since the empirical trade-off evaluated over a finite dataset may not match the exact trade-off over the full data distribution.
in the obtained curve.
We illustrate this phenomenon Figure where the black and red trade-off curves are obtained using the same model but evaluated over two different test data draws. Here, relying solely the estimated curves without accounting for the uncertainty could lead us to make the incorrect conclusion that the methodology used to obtain the black trade-off curve is sub-optimal (compared to the red curve) it achieves a higher fairness violation for accuracies in the range (0.62, 0.66). However, this discrepancy arises solely due to finite-sampling errors.
In this paper, we address these challenges by introducing a computationally efficient method of approximating the optimal eecuracy-fairnes, trade-off curve, supported by rigorous statistical guar- antees. Our methodology not only circumvents the need to train multiple models (leading to at least 10-fold reduction in computational cost) but is also the first to quantify the uncertainty in the estimated curve, arising from both, amite-sampling error as well as estimation error. To achieve this, approach adopts novel probabilistic perspective and provides guarantees that remain valid across all sample draws. This also allows practitioners to distinguish if an apparent suboptimality in a baseline could be explained by finite-sampling errors (as in the black curve in Figure []. or if stems from genuine deficiencies in the fairesss interventions applied (as in the blue curve).
The contributions of this paper are three-fold:

---

We present computationally efficient methodology for approximating the recuracy-faimeet trade-off curve by training only a single model. This is achieved by adapting a technique from 15 called You-Only-TTrain-nne Trann-Onnen--e (YOTO) to the fairness setting.
To account for the approximation and snite-sampligg errors, we introduce a novel technical framework to construct confidence intervals (using the trained YOTO model) which contain the optimal sacuracy-fairnest trade-off curve with statistical guarantees. For any accuracy threshold d chosen at inference time, this gives statistically backed range of permissible fairness violations [[()), u(t)), allowing us to answer our previously posed question:
Given dataset, the permissible range of fairness violations corresponding threshold of vo is [[()), u[ for models in a given class H.
accuracy
Lastly, we showcase the vast applicability of our method empirically across various data modalities including tabular, image and text datasets. We evaluate our framework on a suite of SOTA fairness methods and show that intervals are both reliable and informative.
2 Preliminaries
Notation Throughout this paper, we consider binary classification task, where each training sample is composed of triples. (X, A. Y). X E X' denotes a vector of features, A E A indicates a discrete sensitive attribute, and Y E 3 == {0, 1 represents a label. To make this more concrete, if we take loan default prediction as the classification task, X represents individuals' features such as their income level and loan amount; A represents their racial identity; and Y represents their loan default status. Having established the notation, for completeness, we provide some commonly used fairesss violations P (h) E [0, 1] for classifier model h X + y' when A = {0,
Demographic Parity (DP) The DP condition states that the selection rates for all sensitive groups are equal, i.e. P()(X) = 1 A a) ((M(X) 1) for any a E A. The absolute DP violation is: DP (h) [Ph = 1 A 1) (P(()
A 0)|-
Equalized Opportunity (EOP) The EOP condition states that the true positive rates for all sensitive groups are equal, i.e. ((((X) = 1 A = a, Y = P({(X) = Y = 1) for any a E A. The absolute EOP violation is:
POO (h) : |=)((((X)
1,Y = 1) PP) = A 0, 1))-
2.1 Problem setup
Next, we formalise the notion of accurucy-fairness trade-off, which is the main quantity of interest in our work. For model class H (e.g., neural networks) and given accuracy threshold ai E [0, we define the optimal eccuracy-fairness trade-off Thar (v) as,
Tuir (v)
min (fain()) subject to acc(h) 2 tb
(I)
hEH
Here, P and (h) denote the fairness violation and accuracy of h over the full data distribution. For an accuracy 4/' which is unattainable, we define Tha (3/) 1 and we focus models H trained using gradient-based methods. Crucially, our goal is not to estimate the trade-off at a fixed accuracy level, but instead to reliably and efficiently estimate the entire trade-off curve Thi In contrast, previous works [ impose an apriori fairness constraint during training and therefore each trained model only recovers one point on the trade-off curve corresponding this pre-specified constraint.
If available, this trade-off curve would allow practitioners to characterise exactly how, for a given dataset, the minimum fairness violation varies model accuracy increases. This not only provides a principled way of selecting data-specific fairness requirements, but also serves as a tool to audit if a model meets acceptable fairness standards by checking if its accuracy- -airness trade-off lies on this curve. Nevertheless, obtaining this ground- trade-off curve exactly is impossible within the confines of a finite-samin sample regime (owing A's empirical trade-off evaluated on a finite dataset is suboptimal compared to the empirical trade-off of baseline B, this does not necessarily imply suboptimality the full data distribution.
errors). This means that even if baseline
We illustrate this in Figure T where both red and black trade-off curves are obtained using the same model but evaluated on different test data splits. Here, even though the black curve appears suboptimal
3

---

compared to the red curve for accuracies in [0.62, 0.66], this apparent suboptimality is solely due to samil-g errors (since the discrepancy between the two curves arises only due to different evaluation datasets). If we rely only on comparing empirical trade-offs, we would incorrectly flag the methodology used to obtain the black curve as suboptimal.
To address this, we construct confidence intervals (CIs), shown as the green region in Figure | that account for such sinite-sampling errors. In this case both trade-off's fall within our Cls which correctly indicates that this apparent suboptimality could stem from finite-sample variability. Conversely, baseline's is trade-off falling above our CIs (as in the blue curve in Figure I offers confident assessment of suboptimality, as this cannot be explained away by samile variability. Therefore, our CIs equip practitioners with a robust auditing tool. They can confidently identify suboptimal baselines while avoiding false conclusions caused by considering empirical trade-off's alone.
High-level road map To achieve this, our proposed methodology adopts a two-step approach:
1. Firstly, we propose pass-conditional fairness training. a computationally efficient method- ology of estimating the entire trade-off curve fair by training a single model, obtained by adapting the YOTO framework
[1] the fairness setting.
2. Secondly, to account for the approximation and finite-sampling errors in our estimates, we introduce a novel methodology of constructing confidence intervals on the trade-off curve Thir using the trained YOTO model. Specifically, given E (0, 1), we construct confidence intervals no S [0, 1] which satisfy guarantees of the form:
P(T E T
fair 1-ox. ox.
Here, D and v E [0. 1] are random variables obtained using held-out calibration dataset
Deal (see Section B.2) and the probability taken over different draws of Deal-
3 Methodology
First, we demonstrate how 2-step approach offers a practical and statistically sound method for es- timating Fair (v)). Figure F provides an illustration of our proposed confidence intervals (CIs) I and shows how they can be interpreted as range of 'permissible' values of recuracy-faireet trade-offs (the green region). Specifically, if for a classifier /g. the accuracy-fairness pair (acc(ho), P (ho)) lies above the CIs fair (i.e., the pink region in Figure D. then ho is likely to be suboptimal in terms of the fairness violation, i.e., there likely exists h' с H with acc(h') 2 acc(ho) and
Pisir (h') S (ho)) On the other hand, it is unlikely for any model h' e H to achieve trade-off below the CIs I'm (the blue region in Figure D. Next, we outline how to construct such intervals.
3.1 Step 1: Efficient estimation of trade-off curve
The first step of constructing the intervals is to approximate the trade-off curve by recasting the problem into a constrained optimization objective. The optimization problem formulated in Eq, 1 is however, often too complex solve, because the accuracy acc(h) and fairness violations P (h) are both non-smooth (1 These constraints make it hard to use standard optimization methods that rely on gradients 225. To get around this issue, previous works g replace the non-smooth constrained optimisation problem with smooth surrogate loss. Here, we consider parameterized family of classifiers H. (ho X + R E Q (such as neural networks) trained using the regularized loss:
(0) Eloce(he (X), Y)] + X Chai(
(2)
where, ICE is the cross-entropy loss for the classifier le and Ctair is a smooth relaxation of the g 29 For example, when the fairness violation is DP, (8] consider
fairness violation Prair
L (ho) = Elg(ho(X)) A = 1| - Elg(ho(X))
0).
for different choices of g(x), including the identity and sigmoid functions. We include more examples
of such regularizers in Appendix F.3 The parameter À in L, modulates the accuracy-fairned trade-off
with lower values of À favouring higher accuracy over reduced fairness violation.
Now that we defined the optimization objective, obtaining the trade-off curve becomes straightforward by simply optimizing multiple models over a grid of regularization parameters X. However, training multiple models can be computationally expensive, especially when this involves large-scale models (e.g. neural networks). To circumvent this computational challenge, we introduce loss-conditional fairness training obtained by adapting the YOTO framework proposed by [15.

---

3.1.1 Loss-conditional fairness training
As we descrihe above, a popular approach for approximating the accuracy-fairness trade-off Tfir (1)) involves training multiple models hig over a discrete grid of À hyperparameters with the regularized loss Lx. To avoid the computational overhead of training multiple models, [15] propose 'You Only Train Once' (YOTO), a methodology of training one model ha X' x A + R. which takes À E A C I as an additional input using Feature-wise Linear Modulation (FiLM) 34 layers. YOTO trained such that at inference time ha(,; X) recovers the classifier obtained by minimising Lx in Eq.
Recall that are interested in minimising the family of losses Lx. parameterized by À A (Eq. (2). Instead of fixing X, YOTO solves an optimisation problem where the parameter À is sampled from distribution Px- As a result, during training the model observes many values of À and learns to optimise the loss Lx for all of them simultaneously. At inference time, the model can be conditioned on chosen value X' and recovers the model trained to optimise Lx-- Hence, once adapted to our setting, the YOTO loss becomes:
arg min Ex-P, [Bller(ho(X, A), X (hoii((o( XA--R
Having trained a YOTO model, the trade-off curve Thir (1b) can be approximated by simply plugging in different values of À at inference time and thus avoiding additional training. From a theoretical point of view, [15] Proposition 1] proves that under the assumption of large enough model capacity, training the loss-conditional YOTO model performs as well as the separately trained models while only requiring single model. Although the model capacity assumption might be hard verify in
practice, our experimental section has shown that the trade-off curves estimates Tair (v)) obtained using YOTO are consistent with the ones obtained using separately trained models.
It should be noted, as is common in optimization problems, that the estimated trade-off curve T (hir(() may not align precisely with the true trade-off curve (v)) This discrepancy originates from two key factors. Firstly, the limited size of the training and evaluation datasets introduces errors in the
estimation of Thar (1b). Secondly, we opt for a computationally tractable loss function instead of
the original optimization problem in Eq. (1. This may result in our estimation Thir (v) yielding sub-optimal trade-offs, as can be seen from Figure I Therefore, to ensure that our procedure yields statistically sound inferences, we next construct confddece intervals using the YOTO model, designed to contain the true trade-off curve Thir (vb) with high probability.
3.2 Step 2: Constructing confidence intervals
As mentioned above, our goal here is to use our trained YOTO model to construct confidence intervals (CIs) for the optimal trade-off curve Thir ( defined in Eq. (T). Specifically, we assume access to a held-out calibration dataset Deat == {(X,. Y.)3 which is disjoint from the training data. Given a level a E [0, 1], we construct CIs r S [0, 1] using Deat. which provide guarantees of the form:
PT ) E fair) 1-a.
Here, it is important to note that V E [0. 1] and 1 are random variables obtained from the calibration data Deat. and the guarantee in Eq. (3) holds marginally over V/ and Tuir. While our CIs in this section require the availability of the sensitive attributes in Deal, in Appendix D we also extend our methodology to the setting where sensitive attributes are missing. In this section, for notational convenience we use (-(-) to denote the YOTO model ho( A) for X E A.
The uncertainty in our trade-off estimate arises, in part, from the uncertainty in the accuracy and fairness violations of our trained model. Therefore, our methodology of constructing CIs on Thir involves first constructing CIs on test accuracy ace(hx) and fairness violation (ha) for given value of À using Deat. denoted as C& (A) and Cp (A) respectively satisfying,
(hacc(lx)) E Ch (A)) 11-a, a, and IP(Prair(hs) E CA)) 21-@0 a.
One way to construct these CIs involves using assumption-ligee concentration inequalities such as Hoeffding's 's inequality. To be more concrete, for the accuracy acc ahx(h
Lemma 3.1 (Hoeffding's 's inequality). Given classifier hy : -> V/ we have that,
IP (aco(hx) (aco(tx)= ô, acc(his) + 8 0)) 2 a.
Here, acc(h)= E(x,AA,))DD..
1(h(x.==Y) and == = 2/Daa log (2). Daal
5

---

Lemma 3.1 illustrates that we can use Hoeffding's inequality to construct confidence interval
Coce (A)
(acc(/x)) - 6, acc(hx) + 6] on acc(hx) such that the true acc(hx) will lie inside the CI with probability 1 a. Analogously, also construct CIs for faimesss violations, (par(hx), al- though this is subject to additional nuanced challenges, which we address using a novel sub-sampling based methodology in Appendix B Once we have CIs over acc(hx) and P (hx) for a model hx, we next outline how to use these to derive CIs for the minimum achievable fairness Tfirr satisfying Eq. (3). We proceed by explaining how to construct the upper and lower CIs separately, as the latter requires additional considerations regarding the trade-off achieved by YOTO.
3.2.1 Upper confidence intervals
We first outline how to obtain one-sided upper confidence intervals on the optimum accuracy-fairness trade-off Thir! (V) of the form fair = [0, U which satisfies the probabilistic guarantee in Eq. (3). To this end, given a classifier h E H. our methodology involves constructing one- siees lower CI on the accuracy ace(hx, and upper CI on the fairness violation P (hx). We make this concrete below:
Proposition 3.2. Given h2 E H. let I Pair (hx). i.e.
UA fair E [0, 1]
be lower and upper CIs on acc and
P ((ac((hx) 2 Lgce) 21-a/2, a/2, and P(Prac S Uldte) 2 1 a/22.
Then, IP (Tran (Lice) I
U Fair 2 a
Proposition 3.2 shows that for any model hx, the upper CI on model fairness, U provides valid upper CI for the trade-off value at _ i.e. Thin (L This can be used construct upper CIs on Thar (1b) for a given accuracy level 1b. To understand how this can be achieved, we first find À E A such that the lower CI on the accuracy of model hx, Lice. satisfies L 2 v. Then, since by definition Tair is monotonically increasing function, we know that Thar (I2cc) 2 Tair (v)). Since Proposition 3.2 tells us that U/ is an upper CI for Thir (Lare), ), it follows that U is also a valid upper CI for Tair (+)
Intuitively, Proposition 3.2 provides the 'worst-case' optimal trade-off, accounting for finite-sample uncertainty. It is important to note that this result does not rely on any assumptions regarding the optimality of the trained classifiers. This means that the upper CIs will remain valid even if the YOTO classifier hy is not trained well (and hence achieves sub-optimal accuracy- fairness trade-offs), although in such cases the CI may be conservative.
Having explained how construct upper CIs on ( we next move on the lower Cls.
3.2.2 Lower confidence intervals
Obtaining lower confidence intervals Thar (v) is more challenging than obtaining upper confidence intervals. We begin by explaining at an intuitive level why this is the case.
Suppose that hΛ E H is such that aco(hx) = sb. then since Thar denotes the minimum attainable
fairness violation (Eq. (L), we have that Tair (bb) (ha) Therefore, any valid upper confidence
interval on (fxx)(1)) will also be valid for Fair (v)) However, lower bound on Ptair(hx) cannot be
used as a lower bound for the minimum achievable fairness (v)) in general. A valid lower CI
for Tair (1²) will therefore depend on the gap between fairness violation achieved by h,, (hx).
and minimum achievable fairness violation Tha (vb) (i.e., (hhx) term in Figure 2ap. We make this concrete by constructing lower Cls depending on (hax) explicitly.
Proposition 3.3. Given hy E H. let U A E [0. 1] be upper and lower CIs on acc(hx) and P (hx). i.e.
P(aco(hx) -
2 0//2, and PP(Praic 2 [ 2 0./2.
acc
Then, TP (Tinn (UA) acc 2
Fair A (ha)) 21 a, where A(hx) = (1a) - The (hx)))))) 2 0.
Proposition 3.3 can be used to derive lower CIs on Tia (v) at a specified accuracy level z!. using a methodology analogous to that described in Section 3.2.1 Intuitively, this result provides the "best-case" optimal trade-off, accounting for finite-sample uncertainty. However, unlike the upper CI, the lower CI includes the (1,x) term, which typically unknown. To circumvent this, we propose a strategy for obtaining plausible approximations for A(hx) in practice in the following section.

---

1.0
Optimel tradeoff Fig
Faimes Violation,
0.8
Trode-off achieved by model h
(acc)h)) aualit
0.8
Cls before sensitivity analysis
bg
Cls after sensitivity analysis
Faimes: Viel
Separately trained models
0.6
Optimum achievable
Shift lower by 4 b
0.4
Feasible trade off region
0.4
A2
0.2
0.2
Unachievable abble trade-off region
0.00
0.2
0.4
0.5
0.8
1.
8.0
Accuracy
Accuracy
(a) Visual representation of the difference between the (h) Sensitivity analysis shifts lower CIs below by a con- optimal and model achieved trade-offs.
stant amount whereas upper CIs remain unchanged.
Figure 2: Visual illustrations for (h)) (Figure 2a and our sensitivity analysis procedure (Figure 2b
3.2.3 Sensitivity analysis for Ahhx)
Recall that (hxx) quantifies the difference between the fairness loss of classifier 4x and the minimum attainable fairness loss Fair (acc()x)), and is an unknown quantity in general (see Figure 2ap. Here, we propose a practical strategy for positing values for A(hx) which encode our belief on how close the fairness loss Prair (hx) is to Tiur (acc(hx)). This allows to construct CIs which not only incorporate finite-sampling uncertainty from calibration data, but also account for the possible sub-optimality in the trade-offs achieved by hx The main idea behind our approach is to calibrate (h)x) using additional separately trained standard models without imposing significant computational overhead.
Details Our sensitivity analysis uses i additional models . (4 (22), (k) } S H trained separately using the standard regularized loss Lx (Eq. (2) for some randomly chosen values of X. Let Ma S .M denote the models which achieve better empirical trade-off than the YOTO model on Deat. i.e. the empirical trade-offs for models in Mo lie below the YOTO trade-off curve (see Figure 2b). We choose ((hx) for our YOTO model to be the maximum gap between empirical trade-offs of these separately trained models in Mo and the YOTO model. It can be seen from Proposition 3.3 that, in practice, this will result in a downward shift in the lower CI until all the separately trained models in M lie above the lower CI. As result, our methodology yields increasingly conservative lower CIs as the number of additional models M increases.
Even though the procedure above requires training additional models M, it does not impose the same computational overhead training models over the full range of À values. We show empirically in Section 5 that in practice 2 models are usually sufficient to obtain informative and reliable intervals. Additionally, we also show that when YOTO achieves the optimal trade-off (i.e., ((hx) 0), our sensitivity analysis leaves the CIs unchanged, thereby preventing unnecessary conservatism.
Asymptotic analysis of (hhx) While the procedure described above provides practical solution for obtaining plausible approximations for A (h₂)), we next present a theoretical result which provides reassurance that this gap should become negligible as the number of training data Djr increases.
Theorem 3.4. Let P (ha))))) on training data Du and let
(h'), acc(h") denote the faimess violation and accuracy for h' E H evaluated
== arg min P (h²) subject to acc(h') 2 6. WEH
Then, given 1) (0, 1), under standard regularity assumptions, we have that with probability least 1- (h) < Ō((Dul "")"""").ffo for some y E 1/2] where Ö(-) suppresses dependence on log (1/n).
shows that as the training data size (Dul increases, the error term A(hx) will become negligible with high probability for any model hy which minimises the empirical training loss in Eq. In this case, ((h,) should not have a significant impact on the lower Cls in Proposition and the Cls will reflect the uncertainty in Tiai arising mostly due to finite calibration data. We also verify this empirically Appendix F.7 It is worth noting that Theorem 3.4 relies on the same assumptions used in Theorem 2 in [1. which have been provided in Appendix A.2
Theorem 3.4
3.3
7

---

hoeffdings Cls
bernstein Cis
-
YDTO (Durs)
KDE-fair
linear
reductions
asymptotic Cis
bootstrap Cls
separate
logsig
RTO
adversary
Adult dataset
COMPAS dataset
CelebA dataset
Jigsaw dataset
3153
2125
2100
0109
3313
2353
0323
0.32
3.59
0.04
210
0.54
620
0.00
010
0.05
0.02
602
D.1
6.78
6G
0.:0
06.33
0.50
Figure 3: Results four real-world datasets where Deai is 10% data split. Here, 0.05 and use M = 2 separately trained models for sensitivity analysis.
4 Related works
Many previous fairness methods in the literature, termed in-processing methods, introduce constraints or regularization terms the optimization objective. For instance, [[] impose priori uniform constraints on model fairness at training time. However, given the data-dependent nature of accuracy- fairness trade-offs, setting uniform fairness threshold may not be suitable. Other in-processing methods [37 (24] consider information-theoredd
bounds on the optimal trade-off in infinite data limit, independent of specific model class. While these works offer valuable theoretical insights, there is no guarantee that these frontiers are attainable by models within given model class H. We verify this empirically in Appendix by showing that, for the Adult dataset, the frontiers proposed in [2 are not achieved by any SOTA method we considered. In contrast, our method provides guarantees on the achievable trade-off curve within realistic constraints of model class and data availability.
41 42 43 have also been proposed, but these often necessitate training multiple models, making them computationally intensive. Alternative strategies include learning 'fair' representations [4 30 31 or re-weighting data based on sensitive attributes 18 These, however, provide limited control over accuracy- -firness trade-offs.
Various other regularization approaches (39 33, 8, 14
Besides this, post- pessesrocesiin methods [19 38 enforce fairness after training but can lead to other forms of unfairness such disparate treatment of similar individuals [16). Moreover, many post-hoc approaches such as [3] 2 still require solving different optimisation problems for different fairness thresholds. Other methods such [46] 27 involve learning post-hoc module in addition to the
base classifier. As a result, the computational cost of training the YOTO model is similar to (and in many cases lower than) the combined cost of training base model and subsequently applying post-processing intervention to this pre-trained classifier. We confirm this empirically in Section
5 Experiments
In this section, we empirically validate our methodology of constructing confidence intervals on fairness trade-off curve, across diverse datasets with neural networks as model class H. These datasets range from tabular (Adult and COMPAS to image-based (CelebA), and natural language processing datasets (Jigsaw). Recall that our approach involves two steps: initial estimation of the trade-off via the YOTO model, followed by the construction of CIs using calibration data Deal-

---

Table Proportion of empirical trade-offs for each baseline in the three trade-off regions, aggregated across all datasets and fairness metrics (using Bernstein's 's Cls). 'Unlikely', 'Permissible" and 'Sub- optimal' correspond to the blue, green and pink regions in Figure [igure[[espectivellee The last column shows the rough average training time per model across experiments no. of models per experiment.
Category
Baseline
Unlikely
Permissible
Sub-optimal
Training time
adversary
+
0.51 0.07
0.45 0.07
x 100 min 40
logsig 8
0.0 1 0.0
0.66 0.1
0.33 1: 0.1
reductions
0.0 +: 0.0
0.79 = 0.1
0.21 + 0.1
90 min 40
In-processing
lincar
0.01 + 0.0
0,5 0.05
0.14 1144=00 0.06
100 min x 40
KDE-fair
12
0.0 + 0.0
0.97 = 0.05
0.03 = 0.06
85 min x 40
sepuratee
0.0
0.98 0.01
0.02
100 min
YOTO (Ours)
0.0 +: 0.0
1.0 0.0
0.0 0.0
105 min X
RTO
0.0 0.0
0.65 0.2
0.35 0.05
95 min (training base classifier)
Post-processing
10min 40 (post-hoc optimisations)
To evaluate our methodology, implement suite of baseline algorithms including SOTA in- processing techniques such as regularization-based approaches [8], SOTA kernel-density based method [12] (denoted as 'KDE-fair") ) as well as the reductions method [. Additionally, we also compare against adversarial fairness techniques [45] and a post-proesssing approach (denoted as 'RTO') 22 and consider the three most prominent fairness metries: Demographic Parity (DP), Equalized Odds (EO), and Equalized Opportunity (EOP). We provide additional details and results in Appendix F where we also consider synthetic setup with tractable Tair The code to reproduce our experiments is provided at Batluu..com/faaii//DDa htto///aiii/DDttteeaaaaanee
5.1 Results
Figure shows the results for different datasets and fairness violations, obtained using a 10% data split as calibration dataset Deat- For each dataset, we construct CIs that serve the upper and lower bounds on the optimal accuracy-fairness trade-off curve. These intervals are computed at a 95% confidence level using various methodologies, including 1) Hoeffding's. s. 2) Bernstein's 's inequalities which both offer finite sample guarantees as well as, 3) bootstrapping [17]. and 4) asymptotic intervals based on the Central Limit Theorem 26 which are valid asymptotically. There are 4 key takeaways:
Takeaway 1: Trade-off curves are data dependent. The results in Figure 3 confirm that the fairmess trade-offs can vary significantly across the datasets. For example, achieving near- perfect fairness (i.e. (h) = 0) seems sigmificantly easier for the Jigsaw dataset than the COMPAS dataset, even the accuracy increases. Likewise, for Adult and COMPAS, the DP increases gradually with increasing accuracy, whereas for CelebA, the increase is sharp once the accuracy increases above 90%. Therefore, using uniform fairness threshold across datasets [as in I may be too restrictive, and our methodology provides more dataset-specific insights about the entire trade-off curve instead.
Takeaway 2: Our CIs are both reliable and informative. Recall that, any trade-off which lies above our upper CIs is guaranteed to be sub-optimal with probability 1 a, thereby enabling practitioners to effectively distinguish between genuine sub-optimalities and those due to inite-sample errors. Table [ lists the proportion of sub-optimal empirical trade-offs for each baseline and provides a principled comparison of the baselines. For example, the adversarial, RTO and logsig baselines have a significantly higher proportion of sub-optimal trade-off's than the KDE-fair and separate baselines.
On the other hand, the validity of our lower CIs depends on the optimality of our YOTO model and the lower CIs may be too tight if YOTO is sub-optimal. Therefore, for the lower CIs to be reliable, must be unlikely for any bascline to achieve trade-off below the lower Cls. Table confirms this empirically, as the proportion of models which lie below the lower CIs is negligible. In Appendix we also account for the uncertainty in baseline trade-off's when assessing the optimality, hence yielding more robust inferences. The results remain similar to those in Table []
Takeaway 3: YOTO trade-off's are consistent with SOTA. We observe that the YOTO trade-offs align well with most of the SOTA baselines considered while reducing the computational cost by approximately 40-fold (see the final column of Table T).. In some cases, YOTO even achieves a better trade-off than the baselines considered. See, e-g., the Jigsaw dataset results (especially for EOP) Moreover, we observe that the baselines yield empirical trade-off's which have high variance as

---

accuracy increases (see Jigsaw results in Figure 3 for example). This behaviour starkly contrasts the smooth variations exhibited by our KOTO-genenann trade-off curves along the accuracy axis.
Takeaway 4: Sensitivity analysis does not cause unnecessary conservatism. We use randomly chosen separately trained models to perform this only causes a shift in lower CIs for 2 out of the 12 trade-off' curves presented (i.e. for DP and EO trade-offss on the Adult dataset), leaving the rest of the CIs unchanged. Therefore, in practice sensitivity analysis does not impose significant computational overhead, and only changes the CIs when YOTO achieves a suboptimal trade-off. Additional results have been included in Appendix
sensitivity analysis for Figure [ We find that
6 Discussion and Limitations
In this work, we propose a computationally efficient approach to capture the aceuracy-fairness trade- offs inherent to individual datasets, backed by sound statistical guarantees. Our proposed methodology enables a nuanced and dataset-specific understanding of the accuracy-fairness trade-offs. It does so by obtaining confidence intervals on the fccuracy-fairness trade-off, leveraging the computational benefits of the Saa--OnllT--i-----
(YOTO) framework [15]. This empowers practitioners with the ability to, inference time, specify desired accuracy levels and promptly receive corresponding permissible fairness ranges. By eliminating the need for repetitive model training. we significantly streamline the process of obtaining accuracy-fairmet trade-ofi tailored to individual datasets.
Limitations Despite the evident merits of our approach, also has some limitations. Firstly, our methodology requires distinct datasets for training and calibration, posing difficulties when data is limited. Under such constraints, the YOTO model might not capture the optimal accuracy-fairness trade-off, and moreover, the resulting confidence intervals could be overly conservative. Secondly, our lower Cls incorporate an unknown term (1hx). While we propose sensitivity analysis for approximating this term and prove that it is asymptotically negligible under certain mild assumptions in Section 3.2.3 a more exhaustive understanding remains an open question. Exploring informative upper bounds for ((hx) under weaker conditions is promising avenue for future investigations.
Acknowledgments
We would like express our gratitude to Sahra Ghalebikesabi for her valuable feedback earlier draft of this paper. We also thank the anonymous reviewers for their thoughtful and constructive comments, which enhanced the clarity and rigor of our final submission.
References
[1] A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. Wallach. reductions approach to fair classification. 03 2018.
[2] I. M. Alabdulmohsin and M. Lucic. A near-optimal algorithm for debiasing trained machine learning models. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 8072-8084. Curran Associates, Inc., 2021.
[3] W. Alghamdi, H. Hsu, H. Jeong. H. Wang, P. W. Michalak, S. Asoodeh, and F. P. Calmon. Beyond adult and compas: Fairness in multi-class prediction, 2022.
[4] A. N. Angelopoulos, S. Bates, Fannjiang, M. I. Jordan, and T. Zrnce. Prediction-powerel inference, 2023.
[5] J. Angwin, J. Larson, S. Mattu, and L. Kirchner. Machine bias, 2016.
[6] L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. In D. Helmbold and B. Williamson, editors, Computational Learning Theory, pages 224-240, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
[7] B. Becker and R. Kohavi. Adult. http://tbo.ooy/00444422XXX
UCI Machine Learning Repository, 1996. DOI:
10

---

[8] H. Bendekgey and E. B. Sudderth. Scalable and stable surrogates for flexible classifiers with fairness constraints. In A. Beygelzimer, Dauphin. P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[9] S. Caton and C. Haas. Fairness in machine learning; A survey. CoRR, abs/2010.04053. 2020.
[10] L. E. Celis, L. Huang, V. Keswani, and N. K. Vishnoi. Classification with fairness constraints: A meta-algorithm with provable guarantees. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT '19, page 319-328, New York, NY, USA, 2019. Association for Computing Machinery.
[11] L. E. Celis, L. Huang, V. Keswani, and N. K. Vishnoi. Fair classification with noisy protected attributes: A framework with provable guarantees. In M. Meila and T. Zhang, editors, Proceed- ings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1349-12 1369-1361. PMLR, 18-24 Jul 2021.
[12] J. Cho, G. Hwang, and C. Suh. A fair classifier using kernel density estimation. In H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15088-15099, Curran Associates, Inc., 2020.
[13] J. Devlin, M. Chang, K. Lee, and K. Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, 810.04800, 2018.
[14] M. Donini, I.. Oneto, S. Ben-David, J. S. Shawe-Taylor, and M. Pontil. Empirical risk min- imization under fairness constraints. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. -esachia,chi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[15] A. Dosovitskiy and J. Djolonga. You only train once: Loss-conditional training of deep networks. In International Conference on Learning Representations, 2020.
[16] EEOC. Uniform guidelines employee selection procedures, 1979.
[17] B. Efron. Bootstrap methods: Another look the jackknife. The Annals of Statistics, 7(1):1-26.
1979.
[18] A. Grover, J. Song, A. Agarwal, K. Tran, A. Kapoor, E. Horvitz, and S. Ermon. Bias Correction of Learned Generative Models Using Likelihood FeeeioooddFFeeeee Importance Weighting. Curran Associates Inc., Red Hook, NY, USA, 2019.
[19] M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 3323 3331, Red Hook, NY, USA, 2016. Curran Associates Inc.
[20] Jigsaw and Google. Unintended bias in toxicity classification, 2019.
[21] M. Kakade, Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds. and regularization. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008
[22] F. Kamiran and T. Calders. Data pre-processing techniques for classification without discrimi- nation. Knowledge and Information Systems, 33, 10 2011.
[23] J. S. Kim, J. Chen, and A. Talwalkar. Fact: A diagnostic for group fairness trade-offs. CoRR, abs/2004.03424 2020.
[24] S. Kim, J. Chen, and A. Talwalkar. Model-agnostic characterization of faimness trade-offs. CoRR, abs/2004.03424, 2020.
[25] D. P. Kingma and Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
[26] L. Le Cam. The central limit theorem around 1935. Statistical Science, 1(1):78-11, 1986.

---

[27] E. Z. Liu, B. Haghgoo, A. S. Chen, A. Raghunathan, P. W. Koh, S. Sagawa, P. Liang, and C. Finn. Just train twice: Improving group robustness without training group information. CoRR, abs/2107.09044, 2021.
[28] Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[29] M. Lohaus, M. Perrot, and U. V. Luxburg. Too relaxed to be fair. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6360-6360 PMLR, 13-18 Jul 2020.
[30] C. Louizos, K. Swersky, Y. Li, M. Welling, and R. Zemel. The variational fair autoencoder, 2017.
[31] K. Lum and J. Johndrow. A statistical framework for fair predictive algorithms, 2016.
[32] N. Martinez, M. Bertran, and G. Sapiro. Minimax pareto fairness: multi objective perspective. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 13-18 Jul 2020.
PMLR,
[33] M. Olfat and Y. Mintz. Flexible regularization approaches for faimess in deep learning, In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3389-3394, 2020.
[34] E. Perez, F. Strub, H. de Vries, V. Dumoulin, and A. C. Courville, Film: Visual reasoning with general conditioning layer. CoRR, abs/ 709907787,, 2017.
[35] B. Ustun, Y. Liu, and D. Parkes. Fairesss without harm: Decoupled classifiers with preference guarantees. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages -373-6382. PMLR, 09-15 Jun 2019.
[36] A. Valdivia, J. Sánchez-Monedero, and J. Casillas. How fair can we go in machine learning? assessing the boundaries of accuracy and faimess. International Journal of Intelligent Systems, 1614):1619-163,, 2021.
[37] H. Wang. L. He, R. Gao, and F. Calmon. Aleatoric and epistemic discrimination: Fundamental limits of fairness interventions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[38] D. Wei, K. N. Ramamurthy, and F. Calmon. Optimized score transformation for fair classifica- tion. In Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1673-1683. PMLR, 26-28 Aug 2020.
[39] Wei and M. Niethammer. The fairnes- pareto front. Statistical Analysis and Data Mining: The ASA Data Science Journal, 15(3):287-302 2022.
[40] J. Yang, A. A. S. Soltan, D. W. Eyre, Y. Yang, and D. A. Clifton. An adversarial training framework for mitigating algorithmic biases clinical machine learning. npj Digital Medicine, 6:55, 2023.
[41] M. Zafar, I. Valera, M. Rodriguez, and K. P. Gummadi. Fairness constraints: A mechanism for fair classification. 07 2015.
[42] M. B. Zafar, I. Valera, M. Gomez Rodriguez, and K. P. Gummadi. Fairnsss beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th International Conference on World Wide Web, WWW '17, page 1171-1180, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee.
[43] M. B. Zafar, I. Valera, M. GodezzRodrrguez,, and K. P. Gummadi. Fairness constraints: A flexible approach for fair classification. Journal of Machine Learning Research, 20(75):1-42, 2019.
12

---

[44] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork. Learning fair representations. In Dasgupta and D. McAllester, editors, Proceedings of the 30th International Conference on Machine Learning. volume 28 of Proceedings of Machine Learning Research, pages 325-333, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[45] B. H. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES '18, page 335-340, New York, NY, USA, 2018, Association for Computing Machinery.
[46] A. Tifrea, P. Lahoti, B. Packer, Y. Halpern, A. Beirami, and E, Prost. Frappé: A group fairness framework for post-processing everything, 2024.
13

---

A Proofs
A.1 Confidence intervals on Thair
Proof of Lemma 3.1 This lemma is straightforward application of Heoflding's inequality,
Proof of Proposition 3.2 Here, we prove the result for general classifiers h H. Let T Uh be the lower and upper Cls for acc(h) and (thir()) respectively,
(h(ccc(h) > T Thec 2 - a/2 and (P(Prair S U 2 1 oz/2.
Then, using straightforward application union bounds, get that
P(acc(h) 2 Lace P (h) S U
2 1 - (lacc(h) < Lac)) PP (h) > Unite
2 1 - 0/2 a.2 2
Using the definition of the optimal fairness-accuracy trade-off Tiar we get that the event
(acc(h) 2 L'cce (h) S fair
implies,
min PPai lh' H. acc(h') I } S Uh
fair
The (hke)
From this, follows that
PP (Lice)
U
PP(acc(h)
L
Praie (h) Uh OK.
Proof of Proposition 3.3 We prove the result for general classifiers h H. Let Uh Miir be the upper and lower Cls for acc(h) and P (h) respectively,
Paaco(h) S U ž a/2 and P( 2 Lb 2 1 a/2.
Then, using an application of union bounds, we get that
P(ace(h) I U Paai 2 I
2 1 P(acc(h) > U Praie (1) < D
2 1 a/2 a/2
Then, using the fact that A(h) P (h) Trar (acc(h)), get that
a & P(aco(h) < U P (h) 2 D
= P(acce()) I U Thii (aco(h)) + A(h) 2 D
< (hacc(h) I Ub Thair (Uhh + A(h) 2 L
< P( (Ulhe) 2 L A(h)).
where in the second last inequality above, the fact that Tair [0, [0, 1] is monotonically increasing function.
A.2 Asymptotic convergence of (hh)
this Section, we provide the formal statement for Theorem 3.4 along with the assumptions required for this result.
Assumption A.I. The is L-Lipschitz.
Assumption A.2. Let Ryp, (?() denote the Rademacher complexity of the classifier family H. where |Dzz is the number of training examples. We assume that there exists C 2 0 and > S 1/2 such that R Da (H) C [
It is worth noting that Assumption A.2 which was also used in [ Theorem 2]. holds for many classifier families with 7 = 1/2, including norm-bounded linear functions, neural networks and classifier families with bounded VC dimension (21 6).
14

---

Theorem A.3. Let (h))))(), acc(h)) denote the fairness violation and accuracy metrics for model N evaluated on training data Dv and define
== arg min R'CH
P (h') subject to acc(h') 2 6.
Then, under Assumptions A.1 and
A.2
we have that with probability at least 7/. A(h) z
O((Dul-)), where (-) suppresses polynomial dependence on log (1/1)-
Proof of Theorem
A.3 Let
log (8/n)
c= (R) +
+
Dpr
2 Dul
Next, we define
h" arg min P (h)
subject to acc(h) 2 acc(h) +
Then, we have that
(hh) = tair (h)
Fair (acc((t))
+
Pair (h)
Tair (acc(h) + E) + Thar T'ar (ace(h) + + - (aco((()
= Pair (h) - purre (h²) + Thai (a)c + - Thir (acc(h)).
We know using Assumption A. that
Thir (acc(h) + Tair (acc(h)) S Le
Moreover,
P fair (h) Paair (h²) = Paii (h)
Prair (hi) + P (h) - Prair (1i) + P (h*)
Pair (h'*)
2 fair (h)
Praie (h*) + 2 max (Paii((') - Praie (h!)l-
MEW
Putting the two together, we get that
(hh) < (h)i P (1i*) )
max [ (h') Drair (h()) + Le. WEH
(5)
Next, consider the term (h) & (h*). First, observe that
acc(h") acc(h) + acc(h) |aco(h) acc(h)) + 8 |acc(h) acc(h)).
Next, using [1] Lemma 4] with g(X, A, = L(h(X) = Y), get that with probability at least 1 1/4, we have that
2
log (8/n) e/2.
(aco(h) acc(h)) S 2
v DDr
2 Drrl
This implies that with probability at least 1 - n//4,
acc(h²) 2 5 + e/2,
and hence,
8 8 acc(h") < acc(h") |acc(h") acc(h")) )--
Again, using IT Lemma 4] with g(X, A,Y) 11:" (X) Y), we get that with probability least 1//4, we have that
2
log (8/n) Daal
lace(h") -ace(ht))5277
5 2 (H)
e/2.
V(Du
15

---

Finally, putting this together using union bounds, we get that with probability at least 1/2.
+ e/2 S acc(h") S acc(h*) + lace(h") - acc(h*)) S acc(li") + e/22,
and hence,
acc(l+* 2
Using the definition of h, we have that acc(h²) probability at least 1 - n/22,
Prair (h) (fair(ht) Therefore, with
P (h) Prair (aii)())))
s O.
Next, to bound the term Paair (h) Pair (h) above, consider general formulation for the fairness violation fairr also presented in [T]
fair (h) = [ Fair (h) where,
Fair = Σ (l Eg]
where m 2 94 are some known functions and & are events with positive probability defined with respect to (X, Y).
Using this, note that for any h' 7L
Prair (ha) Faii (h())
1 fair (h')1 - 1 Fur (n')l
2 L (h')
((ii((())) (h')l
Elg, (X, A, A,Y, Eg] - El,,(XX,
[X, (X, E (X, A,Y,, E
Let pj P(E)). Then, from Lemma 6], we have that if (Dul p3 2 llog (4m/n). then with probability least n/2m, we have that
2
log (8 (8m/n)
(X,,, E,1 - Elg (Y 8,1l $2 R p2lp:/2)/2(()) +
+
(Pul
[Dulp]
-((Pa 77)
A straightforward application of the union bounds yields that if |Drl 2 8 (4m/n) for all
j E (1,...,m), m.) then with probability least 7/2, we have that
m
Σ (l,, 1&) Elg, |&|] Ō((
Therefore, in this case for any h E H. we have that with probability at least - 11/2,
[Paii (h') Praie (h)) ((Pull
and therefore,
2 max MEH
P (N') D (h') < O(PPI
(7)
Finally, putting Eq. [5.. Eq. (6) and Eq. together using union bounds, get that with probability at least 1 17, we have that
A (hh) < Pmai (h)
Driir (I*)) + 2 max (h(') & (h'') + Le S Ō((Dal
KEE
16

---

B Constructing the confidence intervals on Prair (h)
In this section, we outline methodologies of obtaining confidence intervals for faimess violation fair- Specifically, given model H. with x y and Cla which satisfies,
(0, 1), we outline how to find
Pr (h) Clar 2 a.
(8)
Similar to we express the fairness violation Piiir as:
Pair (h) = [ fair (/)]
where,
D Fair
(1) = Σ
A &&y]
where > 1, 9ú some known functions and E events with positive probability defined with
respect to (X, A, Y). For example, when considering the demographic parity (DP), i.e. Piair Qp have
2, with gi (X, A, (X)))) (x)), & {A 1). 92 (X; A, (X)(X)) (X) and & = A = 0}. Moreover, as shown in [. the commonly used fairness metrics like Equalized Odds (EO) and Equalized Opportunity (EOP) can also be expressed in similar forms.
Our methodology of constructing CIs on P (h) involves first constructing intervals C & fair satisfying:
(h)
P fair (h)
Fair
a.
Once we have a Co.+ the confidence interval Ofai satisfying Eq. ( can simply be constructed as:
C.a
{ [|2]
x E C.
In what follows, we outline different ways of constructing the confidence intervals Fair on a (h) satisfying Eq. (9.
B.1 Separately constructing CIs on 4
One way to obtain intervals on + (ii,, would be to separately construct confidence intervals on +,, denoted by Cý, which satisfies the joint guarantee
IP (nj=n ( Cf1)) 2 a.
(10)
Given such set of confidence intervals {CH y which satisfy Eqn. Eq. (10 we can obtain the confidence intervals on t (h) by using the fact that
P
④ (h)
C5
2 1
Where, the notation Σm === {C9 1y=
E C.). }. One naïve way to obtain such which satisfy Eq. 110 is to use the union bounds, i.e., if Cj are chosen such that
m C denotes the set (Σ
PP Cf) > 1 1- a/mm
then, have that
P (n m
{ E 1
P(U 18, C999
2 Σ P([ 0939)
21 (1- a/mm)
Here, for an event ε, we use E to denote the complement of the event. This methodology therefore reduces the problem of finding confidence intervals on ( to finding confidence intervals on +; for (1,..., m). Now note that 6 are all expectations and we can use standard methodologies to construct confidence intervals
expectation. We explicitly outline how do this in Section B.3
17

---

Remark The methodology outlined above provides confidence intervals with valid finite sample cov- erage guarantees. However, this may come the cost of more conservative confidence intervals. One way to obtain less conservative confidence intervals while retaining the coverage guarantees would be consider alternative ways of obtaining confidence intervals which do require constructing the Cls separately on $ We outline one such methodology in the next section.
B.2
Using subsampling to construct the CIs T directly
Here, we outline how we can avoid having to use union bounds when constructing the confidence intervals on a Let D, denote the subset of data Deal, for which the event & is true. the case where the events &j are all mutually exclusive and hence Dj are all disjoint subsets of data (which true for DP, EO and EOP), we can also construct these intervals by randomly sampling without
replacement datapoints (Ir (1) Vi
( from D, for I I == minasm [Dxl- We use the fact that
!
(h)
(5(2 M. m(()
is an unbiased estimator of D (4). Moreover, since Dj are all disjoint datasets, the datapoints (x(2) af)) (y())) are all independent across different values of j. and therefore, m
Σラ=1 03 (2(2)) af :/s h(xx
1 (1) (1) (2))) are i.i.d. In other words.
Tai (h)
Σ db where,
= Σ (5( o ve M M(
and o; are all i.idd samples and unbiased estimators of 4 fair (h). Therefore, like in the previous section, our problem reduces constructing CIs on an expectation term (i.e. " (h)), using i.i.d. unbiased samples (i.e. @z) and we can use standard methodologies to construct these intervals.
Benefit of this methodology This methodology dence intervals over 3 and combine them using union bounds (for example). Therefore, intervals obtained using this methodology may be less conservative than those obtained by separately con- structing confidence intervals over D
longer requires to separately construct confi-
Limitation of this methodology For each subset of data Dj. data points to construct the confidence intervals. Therefore, in cases where is very small, we may end up discarding big proportion of the calibration data which could in turn lead loose intervals.
at most == min [Dy]
B.3 Constructing CIs on expectations
Here, we outline some standard techniques used to construct CIs on the expectation of a random variable. These techniques can then be used construct CIs ( (using either of the two methodologies outlined above) as well as on acc(h). In this section, we restrict ourselves to construct- ing upper Cls. Lower CIs can be constructed analogously.
Given dataset (Z: issis n). our goal this section to construct upper CIs on E[Z] which satisfies
P < U 2 1 a.
Hoeffding's 's inequality We can use Hoeffding's 's inequality to construct these intervals U as for- malised in the following result:
Lemma B.1 (Hoeffding's 's inequality). Let Z, [0. 1). 1 i be i.i.d. samples with mean E[Z]. Then,
1 <
1
P
Z
E
2, f=1
log 2n
2 21-a.
Bernstein's inequality Bernstein's 's inequality provides powerful tool for bounding the tail prob- abilitics of the sum of independent, bounded random variables. Specifically, for sum En= Z;
18

---

comprised of n independent random variables Z; with Zi E [0, B), each with a maximum variance of and for any t 0, the inequality states that
12
IP
E
Σ
7
4 2
S exp
20 + tBB
where B denotes upper bound on the absolute value of each random variable. Re-arranging the above, we get that
t² 20 + 31
E
Σ Zi + +t))
2 exe
7
This allows to construct upper CIs on [
Central Limit Theorem The Central Limit Theorem (CLT) 26 serves as a cornerstone statistics for constructing confidence intervals around sample means, particularly when the sample size is substantial. The theorem posits that, for a sufficiently large sample size, the distribution of the sample mean will closely resemble normal (Gaussian) distribution, irrespective of the original population's distribution. This Gaussian nature of the sample mean empowers us to form confidence intervals for the population mean using the normal distribution's characteristics.
Given 11 Zz..... Zn as n independent and identically distributed (i.i.d)) random variables with mean μ and variance of, the sample mean Z approximates normal distribution with mean μ and variance o²/n /n for large n. An upper (1 - a) confidence interval for p is thus:
U 2 + 2a/2 Vn
where 2n/2 represents the critical value from the standard normal distribution corresponding to cumulative probability of a.
Bootstrap Confidence Intervals Bootstrapping, introduced by [7 offers a non- parametric ap- proach estimate the sampling distribution statistic. The method involves repeatedly drawing samples (with replacement) from the observed data and recalculating the statistic for each resample. The resulting empirical distribution of the statistic across bootstrap samples forms the basis for confidence interval construction.
Given dataset Z1, Zz...., Zn. one can produce B bootstrap samples by selecting n observations with replacement from the original data. For each of these samples, the statistic of interest (for instance, the mean) determined, yielding B bootstrap estimates. An upper (1 ax) bootstrap confidence interval for [E] is given by:
U = 2 -2)
with =; denoting the a-quantile of the bootstrap estimates. It's worth noting that there exist multiple methods to compute bootstrap confidence intervals, including the basic, percentile, and bias-corrected approaches, and the method described above serves general illustration.
C
Sensitivity analysis for Ahh)
Recall from Proposition 3.3 that the lower confidence intervals for The include A(h) term which is defined as
(hh) (Pair(()) Tia (acc(h)) 2 0.
In other words, A(h) quantifies how 'far' the fairness loss of classifier h (i.c. Ptai(hh) is from the minimum attainable fairness loss for classifiers with accuracy acc(h), (i.e. T (acc(h))) This quantity is unknown in general and therefore, practical strategy of obtaining lower confidence intervals on The (e))
(vb) may involve positing values for A(h) which encode our belief on how close the faimess loss Prai (h) is to Tha (a.c(h)). For example, when assume that the classifier h achieves tradeoff, i.e. (har = T (ace(h)) then A (hh) =
the optimal
However, the assumption (h) Thir (acc(h)) may not hold in general because we only have finite training dataset and consequently the empirical loss minimisation may not yield the optima to the true expected loss. Moreover, the regularised loss used in training h is surrogate loss which
19

---

approximates the solution to the constrained minimisation problem in Eq. (T. This means that optimising this regularised loss not guaranteed to yield the optimal classifier which achieves the optimal fairness Tfir (acc(h)). Therefore, to incorporate any belief on the sub-optimality of the classifier h, we may consider conducting sensitivity analyses to plausibly quantify (h)).
Let he X' x A + R be the YOTO model. Our strategy for sensitivity analysis involves training multiple standard models .M == (h()) h(9),.... ,...,,,... ,, S H by optimising the regularised losses for few different choices of X.
(0) - El/cE (ho (X), Y)] + (tair(pp)
Importantly, we do require covering the full range of À values when training separate models M. and our methodology remains valid even when M is a single model. Next, let h E M U (ho(,, A)} be such that
h = mig Praie (h') subject to acc(h') 2 acc(ho(:; A)). W (hMo((h(-AA)
(11)
Here, Prair and acc denote the finite sample estimates of the faimeess loss and model accuracy respectively. We treat the model 1i, as a model which attains the optimum trade-off when estimating subject to the constraint acc(h) 2 acc(he(:,))). Specifically, we use the maxi- mum empirical error max A (haa( ((), A)) as plausible surrogate value for A(ho(, where A(ho(,, A)) = Paai (ho(-; A)) Plai (h5)) 2 0, i.e., we posit for any X E
A(ho(, max [hho(: A)) PEλ
where,
Í(ho(: = (ho(:, A)) Prai (hī))
Next, we can use this posited value of A ((ho(: X')) to construct the lower confidence interval using the following corollary of Proposition 3.3
Corollary C.1. Consider the YOTO model hg X A - R. Given A A, let Uh be such that
L.k E [0, 1]
P(aco(ho(,.2pn (o)) S Uth 2 a/2 and PP (ho((, 2 L A 2 a/2.
Then, we have that P (T (U L Ahhol, Ao))) 2 1-a.
This result shows that if the goal is to construct lower confidence intervals Thir (v)) and obtain that vb 2 U then using the monotonicity of Thir have that Thar (v)) 2 Thir (U Therefore the
interval [ A (oo(()))))) 1] serves as a lower confidence interval for Tair (16).
When YOTO satisfies Pareto optimality, ((ho(:,)) -> O as [Deil + oo: Here, we show that in the case when YOTO achieves the optimal trade-off, then our sensitivity analysis leads to
A(ha( (;, A)) = as the calibration data size increases for all X E A. Our arguments this section are not formal, however, this idea can be formalised without any significant difficulty.
First, the concept of Pareto optimality (defined below) formalises the idea that YOTO achieves the optimal trade-off:
Assumption C.2 (Pareto optimality).
for some e and h e H we have that, ace(h') 2 acc(ho(:, then, Prai((h)) 2 Praie A)),
In the case when YOTO satisfies this optimality property, then it is straightforward to see that (ho A)) for all A. In this case, as Deal - oo, we get that Eq. (11) roughly becomes
hg
arg min WeMc((a(sA))
P (11)) subject to acc(h') 2 acc(ho(;, A)).
Here, Assumption C.2 implies that hī = ho( A), and therefore
Â (lho (-, ()) = Drair (hg (1, A)) P (ht) = 0.
20

---

hoeffdings Cls
bernstein Cls
YOTO (Ours)
KDE-fair logsig
linear RTO
reductions
asymptotic Cls
bootstrap Cls
separate
adversary
0.20
0.20
0.20
Equateed Coc0
0.15
Equalzed Colo
0.35
coes
0.15
0.00
0.00
0.05
0.00
74
0.76
0.78
0.80
0.52
0.84
0.00
0.74
0.76
0.78
0.80
0.22
0.84
0.74
0.75
0.76
0.80
0.82
0.54
Accuracy
Accuracy
Accuracy
(a) No sensitivity analysis
(b) MM
2
(c) M =
Figure 4: CIs with and without sensitivity analysis for Adult dataset for EO violation.
Domogragnc Petty
Demographte Panty
Demoggaaphe Punty
0.80
0.80
0.82
0.88
0.84
Accurrcyy
(a) No sensitivity analysis
(b) |M| =
(c) [M]
Figure 5: CIs with and without sensitivity analysis for Adult dataset for DP violation.
0.10
0.10
0.10
Exuuleed Dals
0.08
0.06
0.06
0.02
0.02
0.00
0.00
0.00
0.00
6.50
0.55
0.60
0.65
0.70
0.50
0.55
0.60
0.65
0.70
0.50
0.55
0.60
0.65
0.70
Accuracy
Accurasy
Accuracy
(a) No sensitivity analysis
(b) |M] =
(c) [M =
Figure 6: CIs with and without sensitivity analysis for COMPAS dataset for EO violation. Here, sensitivity analysis has no effect on the constructed Cls as the YOTO model achieves a better empirical trade-off than the separately trained models.
Intuition behind our sensitivity analysis procedure Intuitively, the high-level idea behind our sensitivity analysis is that it checks if we train models separately for fixed values of (i.e. models in M), how much better do these separately trained models perform in terms of the accuracy-fairnes trade-offs as compared to our YOTO model. If we find that the separately trained models achieve a better trade-off than the YOTO model for specific values of X, then the sensitivity analysis adjusts the empirical trade-off obtained using YOTO models (using the Á (ho A)) term defined above). If, on the other hand, we find that the YOTO model achieves better trade-ofi off than the separately trained models in M, then the sensitivity analysis has no effect on the lower confidence intervals as this case &
=0.
C.1 Experimental results
Here, we include empirical results showing how the CIs constructed change result of our sensitivity analysis procedure. In Figures and we include examples of CIs where the empirical trade-off obtained using YOTO is sub-optimal. In these cases, the lower CIs obtained without sensitivity analysis (i.e. when we assume A ((hx) 0) do not cover empirical trade-offs for separately trained models. However, the figures show that the sensitivity analysis procedure adjusts the lower Cls in both cases so that they encapsulate the empirical trade-offs that were not captured without sensitivity analysis.
21

---

Recall that M represents the set of additional separately trained models used for the sensitivity analysis. can be seen from Figures thht in both cases our sensitivity analysis performs well with as little as two models (i.e. [M 2), which shows that our sensitivity analysis does not come at a high computational cost.
Tables 2 and contain results corresponding to these figures and show the proportion of trade-off's which lie in the three trade-off' regions shown in Figure[] with and without sensitivity analysis. It can be seen that in both tables, when |M] = 2, the proportion of trade-offss which lie below the lower CIs (blue region in Figure 1 is negligible.
Additionally, in Figure 6 we also consider an example where YOTO achieves a better empirical trade-off than most other baselines considered, and therefore there is no need for sensitivity analysis. (and Table show that sensitivity analysis has no effect on the CIs constructed since in this case sensitivity analysis gives us (-ho(-, A)) = O for À E A. This shows that in cases where sensitivity analysis is not needed (for example, if YOTO achieves optimal empirical trade-off), our sensitivity analysis procedure does not make the CIs more conservative.
In this case, Figure O
Table 2: Results for the Adult dataset and EO fairness violation with and without sensitivity analysis: Proportion of empirical trade-offss for each baseline which lie in the three trade-off regions (using Bootstrap Cls).
Baseline
Sub-ogtimal
Unlikely (I
Permissible ([M)
Unlikely (IA4)
Permissille [MM) 2)
Uniikely (IMI
Permissible ((M)
KDE
0.00
0:85
0.00
RTO
0.60
0.00
0.40
0.00
0.40
0.00
0.40
udvensary
0.54
0.00
0.36
0.00
0.36
0.00
0.36
linerr
0,60
0.00
0.40
0.00
0.40
0.00
0.40
logsig
0.35
0.65
0.65
reductions
0.93
0.00
0.07
0.00
0.07
0.00
0.07
separate
0.00
0.51
0:16
0.00
1.00
0.00
1.00
Table Results for the Adult dataset and DP fairness violation with and without sensitivity analysis: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions (using Bootstrap Cls).
Baseline
Sub optimal
Unlikely (I.M) = 0)
Permissible (IMM) = 0)
Unlikely (I 2)
Permissible (MM) = 2)
Unlikely (IM) = 5)
Permissible ((MM = 51
KDE-Gar
0.03
0.10
0:87
0.00
0.97
0.00
0.97
RTO
0.67
0.00
0:31
0.00
0.33
0.00
0,33
adversary
0.91
0.09
0.00
0.00
0.09
Tinesr
0
0.33
0.27
0.00
0.60
0.00
0.60
logsip
0.75
0.05
0:23
0.00
0.27
0.00
0.27
reductions
0,87
0.00
0.13
0.00
0.13
0.00
0,13
sepurate
0.03
0.71
0.00
Table 4: Results for the COMPAS dataset and EO fairness violation with and without sensitivity analysis: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions (using Bootstrap CIs).
Baseline
Sub-optimal
Uniiiklly (IM) 0)
Parmissible (IM)
Unlikely (LM)
Permissible ([M) 2)
Unlikely (IM)
Permissible (IMM
KDE fair
0,00
0.00
1.00
0.00
1.00
0.00
1.00
RTO
0.15
0.85
0.00
0.00
0.85
adversary
0.00
0.00
1.00
0.00
1.00
0.00
1.00
Tinere
0.21
0.00
0.79
0.00
0.79
0.00
0.79
logsig
0.55
0.45
0.00
0.45
roductions
0.70
0.00
0.20
0.70
separate
0.03
0.50
0.17
0.80
0.17
0.80
0.17
D Scarce sensitive attributes
Our methodology of obtaining confidence intervals on P assumes access to the sensitive attributes for all data points in the held-out dataset D. However, in practice, we may only have access to A for a small proportion of the data in D. In this case, naïve strategy would involve constructing confidence intervals using only the data for which A is available. However, since such data is scarce, the confidence intervals constructed are very loose.
22

---

Suppose that we additionally have access to predictive model fA which predicts the sensitive attributes A using the features X. In this case, another simple strategy would be simply impute the missing values of A, with the values Å predicted using fA- However, this will usually lead to a biased estimate of the fairesss violation Paarr (f),, and hence is not very reliable unless the model fA highly accurate, In this section, we show how to get the best of both worlds, i.e. how to utilise the data with missing sensitive attributes to obtain tighter and more accurate confidence intervals on (b)).
Formally, we consider Dent = DUD where D denotes a data subset of size n that contains sensitive attributes (i.e. we observe A) and D denotes the data subset of size N for which we do not observe the sensitive attributes A, and N >> 11 Additionally, for both datasets, we have predictions of the sensitive attributes made by a machine-learning algorithm FA + A. where fx(X) = A. Concretely we have that = ((X,, A, Y,, fa(,))) T and D = [(X,, Y,, (x(
High-level methodology Our methodology is inspired by prediction prediction-powered powered inference f which builds confidence intervals on the expected outcome [E[]] using data for which the true outcome Y only available for a small proportion of the dataset. In our setting, however, it is the sensitive attribute that missing for the majority the data (and not the outcome Y).
For E H. let Paair (h) be a fairness violation (such as DP or EO), and let Prai be the corresponding fairness violation computed on the data distribution where A is replaced by the surrogate sensitive attribute fA(X). For example, in the case of DP violation, Prai(h) and Ptair (h) denote:
Paiir (h) [P()(X) = 1 A 1) (P((X) = 1 A 0)},
Prair (h) (P()X) 1 fx() 1) (( fx(X) O)}.
We next construct the confidence intervals on (tai(() using the following steps:
1. Using D, construct intervals h) c(h) = P (h) D (h) satisfying
P(c(h) E C. h)) 2 a.
(12)
Even though the size of D is small, choose methodology which yields tight intervals for e(h) when fX,, = A, with a high probability.
2. Next, using the dataset D, we construct intervals Či(a; h) (m) satisfying
P(P (h) E C((a;)) 2 1 - a.
(13)
This interval will also be tight as the size of DD N > n.
Finally, using the union bound idea we combine the two confidence intervals obtain the confidence interval for Pfair(h) - Pfair(h) + (h)r = (tai We make this precise in the following result:
Lemma D.I. Ler C.(on)), h)), Ör(a; h) be as defined in equations 12 and 13 Then, if we define Ch (h) {x + + Ce(a;h), h)(a;)),, we have that
PPPriiir E (h)(
2a.
When constructing the CIs over Prai (h) using imputed sensitive attributes f((X) step above, the prediction error of f. introduces an error in the obtained CIs (denoted by <(h)). Step rectifies this by constructing a CI over the incurred error c(h), and therefore combining the two allows us to obtain intervals which utilise all of the available data while ensuring that the constructed CIs are well-calibrated.
Example: Demographic parity Having defined our high-level methodology above, we concretely demonstrate how this can be applied the case where the faireess loss under consideration is DP. As described above, the first step involves constructing intervals on e(h) = (h) e (h) using a methodology which yields tight intervals when fx(X) = A; with a high probability. To this end, we use bootstrapping as described in Algorithm
Even though bootstrapping does not provide with finite sample coverage guarantees, it is asymptot- ically exact and satisfies the property that the confidence intervals are tight when A = A with high
23

---

probability. On the other hand, concentration inequalities (such as Hoeffding's 's inequality) seek to construct confidence intervals individually (h) and (h) and subsequently combine them through union bounds argument, for example. In doing so, these methods do not account for how close the values of 2 Pair (h) and P (h) might be in the data.
To make this concrete, consider the example where fa(X) = A and hence Prai(()) Paair (h). When using concentration inequalities to construct the a confidence intervals on taar (h) and Praie (h), we obtain identical intervals for the two quantities, say [2. u]. Then, using union bounds we obtain that (P)i Itair (h) [1 u, u -1] with probability least 1 2o. In this even though Prair (h) pame = O, the width of the interval [ - u, u - I] does not depend on the closeness of rair (h) and (h) and therefore is not tight. Bootstrapping helps circumvent this problem, since
this case for each resample the data D. the finite sample estimates Paair and (rair(h) will be equal. We outline the bootstrapping algorithm below.
Algorithm Bootstrapping for estimating <(h) = Paiie (h) pair (h)
Require: Dataset D. number of bootstrap samples B, significance level a Ensure: confidence interval for e(h)
Initialize empty array for i B do
Draw bootstrap sample DD' of size |D] with replacement from 'D
Compute (h) and (h) on D
Compute the difference (h) = P (h) Prair(h)
Append e(h) to Vb
end for
Compute the a/2 and - a/2 quantiles of ys. denoted as and Return: Confidence interval C, (a; h) [1, u]
c(h) of size - which obtain an interval Ci(a; h) on Prai (h) using D which satisfies Eq. 11 Like before, the interval Ci(a; h) is likely to be tight as we use D to construct it, which is significantly larger than D. Finally, combining the two as shown in Lemma D.I obtain the confidence interval (air (h).
Using Algorithm
construct confidence interval Ce(a: h)
approximately satisfies Eq. (12). Next, using standard techniques
D.1 Experimental results
Here, we present experimental results in the setting where the sensitive attributes are missing for majority of the calibration data. Figures 7 show the results for different datasets and predictive models fA with varying accuracies. Here, the empirical fairness violation values for both YOTO and separately trained models are evaluated using the true sensitive attributes over the entire calibration data.
CIs with imputed sensitive attributes are mis-calibrated Figures 7 and 11 show results for Adult, COMPAS and CelebA datasets, where the CIs are computed by imputing the missing sensitive attributes with the predicted sensitive attributes [X( A. The figures show that when the accuracy of /A is below 90%, the Cls are highly miscalibrated as they do not entirely contain the empirical trade-offs for both YOTO and separately trained models.
Our methodology corrects for the mis-calibration In contrast, Figures 10 and 12 which include the corresponding results using our methodology, show that our methodology is able to correct for the mis-calibration CIs arising from the prediction error in fA- Even though the CIs obtained using methodology are more conservative than those obtained by imputing the missing sensitive attributes with fA (X), they are more well-calibrated and contain the empirical trade-offs for both YOTO and separately trained model.
Imputing missing sensitive attributes may work when SA has high accuracy Finally, Figures 7c 9c and IIc show that the CIs with imputed sensitive attributes relatively better calibrated as the

---

hoeffdings
asymptotic
baotstrap
(Ours)
separate
Demegraphe Peett
Denegraphe Parity
Denegegec Gomegraeee
0.10
0.10
0.10
0.05
0.05
0.05
0.00
(a) (fc 50%
(fc(ff) 70%
(c) acc(fa) 90%
Figure 7: Cls obtained by imputing missing senstive attributes using fA for Adult dataset. Here 50 and 2500.
Demograpas Pupty
Demographe Danby
Demogragnic
0.10
0.10
0.10
0.05
0.05
0.05
0.00
Accurety
Accurecy
(a) afc(fa) 50%
(b) acc(ff)) 70%
(c) acc(fa) 90%
Figure 8: Cls were obtained using our methodology for the Adult dataset. Here m = 50 and N 2500.
Demopaatte Party
0.15
Demogranhc Partt
Demographi therty
0.35
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.58
0.64
0.66
0.00
0.60
0.64
0.58
0.68
0.50
0.68 0.58
0.50 0.62
0.64
0.66
Accuracyy
Accuracy
Accuracy
(a) afc(ff) 50%
(b) acc(fx) 70%
(c) acc(fa) 90%
Figure 9: Cls obtained by imputing missing senstive attributes using LA for COMPAS dataset. Here 50 and N 2000.
0.150
Dempgraphe Fartyy
0.15
Gemographic 1ult
Demogrraphe Phetty
0.15
0.100
0.10
0.10
0.05
0.050
0.05
0.00
0.56
055
0.50 0.62
964
0.66
0.68
0.000
0.5
0.58
0.60
0.62
0.54
0.66
0.68
0.00
0.56
0.58
0.80
0.62
0.64
0.56
0.66
Accuracy
Accuracy
Accuracy
(a) acc(fA) 50%
(b) acc( 70%
(c) acc(SA) = 90%
Figure 10: CIs obtained using our methodology for COMPAS dataset. Here n 50 and N 2000.
accuracy of fA increases to 90%. this case, the CIs with imputed sensitive attributes mostly contain empirical trade-offs. This shows that in cases where the predictive model fA has high accuracy, may be sufficient to impute missing sensitive attributes with fX(X when constructing the Cls.
E Accounting for the uncertainty in baseline trade-offs
In this section, we extend our methodology to also account for uncertainty in the baseline trade-offs when assessing the optimality of different baselines. Recall that confidence intervals constructed
25

---

hoeffdings
asymptotic
bernstein
baotstrap
(Ours)
separate
0.150
Deee Demeggappee Paitly
Demodnap
0.100
0.075
0.075
0.075
0.050
6.050
0.050
0.025
0.025
0.025
0.000
6.000
0.000
(a) (fx) 50%
acc
70%
(c) acc 90%
Figure 11: Cls obtained by imputing missing senstive attributes using fA for CelebA dataset. Here 50 and 2500.
0.150
0.150
0,150
Demoggrent seeggeeeeiie Weeyy
0.100
0.075
0.075
0.075
0.050
0.059
0.050
0.025
6.025
0.025
0.000
0.000
0.000
Accuracy
Accuracy
Accurary
(a) acc(fa) 50%
(b) acc(fa) 70%
(c) acc(fa) 90%
Figure 12: Cls obtained using our methodology for CelebA dataset. Here n 50 and N = 2500.
on Tair satisfy the guarantee
P( (V)
E
Pa fair
a.
This means that if the accuracy-fairness tradeoff for given model h/ H. (acc(h'), Ptai((")). lies above the confidence intervals th (i.e. in the pink region in Figure 13). then we can confidently infer that the model h' achieves suboptimal trade-off. This is because we know from the probabilistic guarantee above that the optimal trade-off (acc(h'), T (acc(h")) must lie in the intervals T with probability least 1 a.
Here, acc(h"), ( (h') denote the accuracy and fairness violations for model on the full data distribution. However, in practice, only have access finite data and therefore can only compute empirical values accuracy and fairness violations which we denote by aco(N'), (h)) This means that when checking if the accuracy-faiis feirres--airness trade-off (acc(h"), P (h')) lies inside the confi- dence intervals fair we must account for the uncertainty in the empirical estimates aco(h') P (h'). This can be achieved by constructing confidence regions C (h') satisfying
1ev
PP(acceh'), P (h')) E C CO (h)) 2 a.
(14)
Baseline's best-case aciiracy-fairness trade-off If the confidence region (*(h') lies entirely above the confidence intervals a (i.e. in the pink region in Figure 13a), then using union bounds we can confidently conclude that with probability 2a we have that the model h achieves suboptimal fairness violation, i.c.
P (K) 2 Than (acc(h')
This allows practitioners to confidently check if model is suboptimal terms of its accuracy- fairness trade-off. This is different from simply checking if the empirical trade-off off achieved by the model (hcc(h)), (h")) lies in the permissible trade-off region (green region in Figure 1 it also accounts for the finite-samplig uncertainty the tradeoff achieved by model M. However, this conservative.
means that the criterion for flagging baseline model h/ as suboptimal becomes
Next, we show how to construct confidence regions C (t() satisfying Eq. (4).
Lemma E.1. For a classifier h' H, let Uh Lh be the upper and lower CIs on acc(h'), (h') respectively,
P(acc(h') < Uhh 21 2-a22 and ((Drir(h)) 2 Ihh)) 2 1 a/2.
26

---

Supoptimal accuracy-faimess trade-off Permissible trade-off region
Unlikely to be achievable trade-off Confidence region for (acc)A), (pwr)))
0.6
0.6-
0.4
04
0.00
%
Accuracy
Accurery
(a) Here, (U ( represents the best-case accuracy-faiin fairness trade-off achieved by h. If the confidence region lies entirely in the sub- optimal region, we can confidently conclude that achieves a suboptimal tradc-off.
(b) Here, (T Uhar) represents the worst- accuracy faimesss trade-off achieved by the confidence region lies entirely in the 'unlikely' region, we can conclude that achieves better tradc-off than YOTO.
Figure 13: Confidence region (*(h) for the accuracy-fairnes trade-off achieved by h.
Then, P(((ccc(h', Praie (h')) E [0, Uz x [L 1)) 2 a.
Lemma E. shows that (OO)) = [0, U x [T 1] forms the - a confidence region for the Securacy-airness trade-off (acc(h'), (fair (k)). We illustrate this in Figure 13a If this confidence region lies entirely above the permissible region (i.e. in the pink region in Figure 13 we can confidently conclude that the model h achieves suboptimal accuracy-fairnet fairness trade-off. From Figure 13a it can be seen that this will occur if (U L lies above the permissible region.
Intuitively, (Uh aces ) can be seen as an optimistic best-case accuracy-fairnet trade-off achieved by the model h., since at this point in the confidence region ("hh') the accuracy is maximised and fairness violation is minimised. Therefore this best-case trade-off lies above the permissible region, then this intuitively indicates that the worst-case optimal trade-off Thi is still better than the best-case trade-off achieved by the model h', leading us to the confident conclusion that h achieves suboptimal accuracy-faiie fairness trade-off.
Baseline's worst-case accuracy-fairness trade-off Conversely, if confidence region C* (h') lies entirely below the confidence intervals ro (i.e. in the blue region in Figure 13), then using union bounds we can confidently conclude that with probability 2a we have that the model / achieves better trade-off than the YOTO model he(;, A). Formally, this means that
YOTO (acc((() 2 Prai((h)).
where
YOTO = min P (ho A)) subject to acc(ho(:; 2 6.
XEA
This would indicate that the YOTO model does not achieve the optimal trade-off and can be used to further calibrate the A(hx) values when constructing the lower confidence interval using Proposition 3.3 Again, this different from simply checking if the empirical trade-off achieved by the model tobb--eceeee (acc (h'), Prii (h')) lies in the unlikely-to- to-eeey-t--b--eeeeeee achieved trade-off region (blue region in Figure 13 as it also accounts for the finite-sampling uncertainty the tradeoff achieved by model ht.
Next, we show to construct such confidence region (aa using an approach analogous to the one outlined above:
Lemma E.2. For a classifier h/ H. let Likes Uh be the lower and upper CIs on acc(h"), P (h') respectively,
P(aco(h')= 2 Lise) 2 a/2, and ((Prai((h)) I Ufine) 2 a/2.
Then, PP((acc(h'), Daair (ht)) [L 1] x 10, U (
27

---

Table The table shows the proportion of models whose best-case trade-off (U L lies in the suboptimal region, models whose worst-case trade-off (Lice. Lin) lies the unlikely region and models whose confidence regions C* overlaps with the permissible trade-off region. The table reports average across all experiments.
BASELINE
UNLIKELY
PERMISSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
1.010.0
0.0:0.0
RTO
0.0
0.77 10.05
0,23# 0.04
ADVERSARY
0.0
0.79 +0.1
0.2+0.08
LINEAR
0.08=0.05
0.81+0.06
0.11=0.05
LOGSIG
0.71 =0.02
0.25+0.1
REDUCTIONS
0.0.0.00
0.82.00.09
0.18 10.08
SEPARATE 0.03
0.951 0.08
0.02 10.03
Lemma E.2 shows that (I)) = [L 1] 10, fair] forms the 1 - confidence region for the accuracy- trade-off (ace(N'), Pfar
U
this confidence region lies entirely below the permissible region (i.e. in the blue region in Figure 13), we can confidently conclude that the model h' achieves a better accuracy- farrncsss trade-off than the YOTO model. From Figure 13b it can be seen that this will occur if (L U lies below the permissible region.
Intuitively, (Lisg Uhir) can be seen as a conservative worst-case accuracy-fairness trade-off achieved by the model h'. Therefore if this worst-case trade-off lies below the permissible region, then this intuitively indicates that the best-case YOTO trade-off 7 ~YOTO is still worse than the worst-case trade-off achieved by the model h', leading us the confident conclusion that h' achieves better accuracy-faire fairness trade-off than the YOTO model. This can subsequently be used to calibrate the suboptimality gap for the YOTO model, denoted by A(hx) Proposition 3.3
E.1 Experimental results
Here, we present the results with the empirical baseline tradc-off's replaced by best or worst-case trade-offs as appropriate. More specifically, Figure
if the empirical trade-off for baseline (aco(h'), (r'ie(h()) lies in the suboptimal region (as in Figure 13a). then we plot the best-case trade-off (Ule L for the baseline,
if the empirical trade-off for a baseline (aco(h'), (r") lies in the unlikely-to-be achievable trade-off region (as in Figure 13b). then we plot the worst-case trade-off (I Uh for the baseline,
if the empirical trade-off for a baseline (h'), (h")) lies in the permissible region, then we simply plot the empirical trade-off (aco(h'), Prai (h))).
Therefore, in Figure [4 if baseline's 's best-case trade-off lies above the permissible trade-off region, then we can confidently conclude that the baseline achieves suboptimal accuracy-fairnes trade- off with probability permissible trade-off region would suggest that the YOTO trade-off achieves suboptimal trade-off and that the value of A (hhs) needs to be adjusted accordingly.
2a 90%. Similarly, a baseline's worst-case trade-off lying below
Table 5 shows the proportion of best-case trade-offs which lie above the permissible trade-off region and the proportion of worst-case trade-off's which lie below the permissible region. Firstly, the table shows that the proportion of worst-case trade-offs which lie in the 'unlikely' region is negligible, empirically confirming that our confidence intervals on optimal trade-off Thi are indeed valid. Secondly, we can see that there are a considerable proportion of baselines whose best-case trade-off lies above the permissible region, highlighting that our methodology remains effective in flagging suboptimalities in SOTA baselines even when we account for the possible uncertainty in baseline trade-offs. This shows that our methodology yields CIs which are not only reliable but also informative.
28

---

hoeffdings Cls
bernstein Cis
YDTO (Durs)
KDE-fair
linear
reductions
asymptotic Cis
bootstrap Cls
separate
logsig
RTO
adversary
Adult dataset
COMPAS dataset
CelebA dataset
Jigsaw dataset
3153
2123
2100
0109
3315
2353
0323
3.9
0.04
210
0.53
620
0.32
1.00
010
0005
3.02
002
0.1
1.78
1.00
6G
01:00
23
06.33
0.30
Figure 14: Results with the empirical baseline trade-off's replaced by best-case and worst-case trade- off's for baselines lying above and below the permissible region respectively. Here, Deal is 10% data split and 0.05.
F Experimental details and additional results
In this section, we provide greater details regarding our experimental setup and models used. We first begin by defining the Equalized Odds metric which has been used in our experiments, along with DP and EOP.
Equalized Odds (EO): EO condition states that, both the true positive rates and false positive rates for all sensitive groups are equal, i.e. P(h(X)= = 1 A a, Y y) ((((X) 1 Y y) for any E A and E {0, 1}. The absolute EO violation is defined as:
(h) = (X(() = A 1, = P((()) = 1 A= 0, 1)1
+ 1/2 (X) = A 1, = 0) (P)( = 0, 0)-
Next, we provide additional details regarding the YOTO model.
F1 Practical details regarding YOTO model
As described in Section 3 we consider optimising regularized losses of the form
(0) = ()) Y)] + À (he))
When training YOTO models, instead of fixing X, we sample the parameter À from distribution Px- As result, during training the model observes many different values of À and learns optimise the loss L) for all of them simultaneously. At inference time, the model can be conditioned on a chosen parameter value X' and recovers the model trained optimise Lx. The loss being minimised can thus be expressed as follows:
arg min Ex-P, [B]|en(ho(X, A), Y)] A (hol:, he:X A-
The fairness losses Lear considered for the YOTO model are:
DP: (raie(ho (:, 2)) [Elo(ha(X, A)) A = 1] (lo(hel(X, A)) A O]
EOP: Crar ()) [Bo
= - B
A= =
A 0, =
EO:
(har(ho A)) = [E( -|
|Boo(h A)) 1 (X, 4= A=
29

---

Here, a(x) = 1/(+1 denotes the sigmoid function.
sample new for every batch. Moreover, we the log-uniform distribution as per [15] as the sampling distribution Px. where the uniform distribution is U(10- 10). To condition the network on À parameters, we follow in the footsteps of [1]] to use Feature-wise Linear Modulation (FiLM) [34] For completeness, we include the description of the architecture next.
In our experiments,
Initially, we determine which network layers should be conditioned, which can encompass all layers or just subset. For each chosen layer, we condition it based on the weight parameters A. Given layer that yields feature map f with dimensions W x H x C, where W and H denote the spatial dimensions and C' stands for the channels, we introduce the parameter vector À to two distinct multi-layer perceptrons (MLPs), denoted and 14, each having a dimensionality of C. The feature map is then transformed by multiplying chasnel-wise with and subsequently adding μr. The resultant transformed feature map f' is given by:
Ms and Mp. These MLPs produce two vectors,
fiy oxfuk + M where a = (A) and == (A))
Next, we provide exact architectures we used for each dataset in our experiments.
F.11 YOTO Architectures
Adult and COMPAS dataset Here, we use simple logistic regression as the main model, with only the scalar logit outputs of the logistic regression being conditioned using FiLM. The MLPs Mn. M, both have two hidden layers, each of size 4, and ReLU activations. We train the model for maximum of 1000 epochs, with early stopping based on validation losses. Training these simple GPU.
models takes roughly 5 minutes on a
CelebA dataset For the CelebA dataset, architecture is convolutional neural network (ConvNet) integrated with the FiLM (Feature-wise Linear Modulation) mechanism. The network starts with two convolutional layers: the first layer has 32 filters with kernel size of 3 x and the second layer has 64 filters, also with a 3 x 3 kernel. Both convolutional layers employ a stride of I and are followed by max-pooling layer that reduces each dimension by half.
The feature maps from the convolutional layers are flattened and passed through a series of fully connected (MLP) layers. Specifically, the first layer maps the features to 64 dimensions, and the subsequent layers maintain this size until the final layer, which outputs a scalar value. The activation function used in these layers is ReLU,
To condition the network on the parameter using FiLM, we design two multi-layes perceptrons (MLPs), M₁, and M.. Both MLPs take the À parameter as input and have 4 hidden layers. Each of these hidden layers is of size 256. These MLPs produce the modulation parameters μ and a, which are used to perform feature-wise linear modulation on the outputs of the main MLP layers. The final output of the network is passed through a sigmoid activation function to produce the model's prediction. We train the model for a maximum of 1000 epochs, with early stopping based on validation losses. Training this model takes roughly 1.5 hours on a Tesla V 100-0X02-326G3 GPU.
Jigsaw dataset For the Jigsaw dataset, we employ neural network model built upon the BERT architecture 13] integrated with the Feature-wise Linear Modulation (FiLM) mechanism. We utilize the representation corresponding to the [CLS] token, which carries aggregate information about the entire sequence. To condition the BERT's output on the À parameter using FiLM, we design two linear layers, which map the X parameter to modulation parameters y and }3 both of dimension equal to BERT's hidden size of 768. These modulation parameters are then used to perform feature-wise linear modulation on the [CLS] representation. The modulated representation is passed through a classification head, which consists of linear layer mapping from BERT's hidden size (768) to scalar output. In terms of training details, our model is trained for maximum of 10 epochs, with early stopping based on validation losses. Training this model takes roughly 6 hours on a 1000-0000020000 GPU.
F.2
Datasets
We used four real-world datasets for our experiments.
Adult dataset The Adult income dataset 77) includes employment data for 48,842 individuals where the task is to predict whether individual carns more than $50k per year and includes demographic
30

---

attributes such as age, race and gender. In our experiments, we consider gender as the sensitive attribute.
COMPAS dataset The COMPAS recidivism data comprises collected by ProPublica [ includes information for 6172 defendants from Broward County, Florida. This information comprises 52 features including defendants' criminal history and demographic attributes, and the task is to predict recidivism for defendants. The sensitive attribute in this dataset is the defendants' race where A 1 represents 'African American' and A = 0 corresponds to all other races.
CelebA dataset The CelebA dataset [28 consists of 202.599 celebrity images annotated with 40 attribute labels. In our task, the objective is to predict whether an individual in the image smiling, The dataset comprises features in the form of image pixels and additional attributes such as hairstyle, eyeglasses, and more. The sensitive attribute for our experiments is gender.
Jigsaw Toxicity Classification dataset The Jigsaw Toxicity Classification dataset (0) contains online comments from various platforms, aimed identifying and mitigating toxic behavior online. The task is to predict whether given comment is toxic not. The dataset includes features such as the text of the comment and certain metadata such as the gender or race to which each comment relates. In our experiments, the sensitive attribute is the gender to which the comment refers, and we only filter the comments which refer to exactly one of 'male' or 'female' gender. This leaves us with 107,106 distinct comments.
F.3 Baselines
The baselines considered in our experiments include:
Regularization based approaches [8] These methods seek to minimise fairness loss using
regularized losses as shown Section 3 We consider different regularization terms Cair (hg) smooth relaxations of the fairness violation Drair proposed in the literature [8] To make this concrete, when the fairness violation under consideration is DP, we consider
Lairr (hg) ([(((h(X)) A 1] Elg(h+(X)) A= 0).
with g(x) = denoted as 'linear' in our results and g(x)) = log a (x) where (xr) = 1/(1 + *)) denoted 'logsig' in our results. In addition to these methods, we also consider separately trained models with the same regularization term as the YOTO models, i.c..
DP: Luir = [B(o(h(())) A- B[o(ho(X)) A= OJl
HOP: frar (ho) = (ho (X)) A=
E| (ho (X)) | A 0, 1] + E (he (X)) 4 1, = ((o(hs(X))
1, =,
EO:
(ho) = (hoo (X) A- - - X)) A = 0,Y = 1]]
= O]|-
Here, (z)) 1/(1 + - denotes the sigmoid function. We denote these models as "separate" in our experimental results as they are the separately trained counterparts to the YOTO model. For each relaxation, we train models for range of X values uniformly chosen in j0, 10 interval.
This method transforms the fairness problem into a sequence of cost-sensitive classification problems. Like the regularization approaches this requires multiple models to be trained. Here, to try and reproduce the trade-off curves, we train the reductions approach with a range of different faimess constraints uniformly in [0, 1].
Reductions Approach 1
This method employs kernel density estimation trick to quantify fairness measures, capturing the degree of irrelevancy of prediction outputs to sensitive attributes. These quantified fairness measures expressed differentiable functions with respect to classifier model parameters, allowing the use of gradient descent to solve optimization problems that respect faimess constraints. We focus binary classification and well-known definitions of group fairness: Demographic Parity (DP), Equalized Odds (EO) and Equalized Opportunity (EOP).
KDi-fair [12]
This scalable post-processing algorithm debiases trained models, including deep neural networks, and proven to near-optimal by bounding its excess Bayes risk. RTO optimizes the trade-off curve by applying adjustments
Randomized Threshold Optimizer (RTO) 2
31

---

to the trained model's predictions to meet fairesss constraints. In our experiments, we first train standard classifier which is referred as the base classifier. Next. we use the RTO algorithm to apply adjustments to the trained model's prediction to meet fairness constraints. To reproduce the trade-off curves, we apply post-hoe adjustments to the base classifier for a range of fairness violation constraints.
These methods utilize an adversarial training paradigm where an additional model, termed the adversary, is introduced during training. The primary objective of this adversary is to predict the sensitive attribute A using the predictions ha (x) generated by the main classifier hg. The training process involves an adversarial game between the primary classifier and the adversary, striving to achieve equilibrium. This adversarial dynamic ensures that the primary classifier's predictions are difficult use for determining the sensitive attribute A, thereby minimizing unfair biases associated with A. Specifically, for DP constraints, the adversary takes the logit outputs of the classifier as the input and predicts A. In contrast for EO and EOP constraints, the adversary also takes the true label Y as the input. For EOP constraint, the adversary is only trained on data with Y ==L. L.
Adversarial Approaches [45
The training times for each baseline on the different datasets have been listed in Table 6
Table 6: Approximate training times per model for different baselines across various datasets.
Adult
COMPAS
CelebA
Jigsaw
adversary
min
min
90 min
310 min
linear/Ingsi//sepaatt
min
min
min
310 min
KDE-fair
min
min
60 min
280 min
reductions
min
2 min
70 min
290 min
YOTO
4 min
min
90 min
320 min
RTO (base classifier training)
3 min
3 min
70 min
310 min
RTO (Post-hoc optimisation per fairness constraint)
min
min
10 min
30 min
F.4 Additional results
In Figures| 15 26 we include additional results for all datasets and fairness violations with an increasing number of calibration data D It can be seen that the number of calibration data increases, the CIs constructed become increasingly tighter. However, the asymptotic, Bernstein and bootstrap CIs informative even when the calibration data is little as 500 for COMPAS data (Figures 18 20 and 1000 for all other datasets. These results show that the larger the calibration data Deat. the tighter the constructed Cls are likely be. However, even in cases where the calibration dataset is relatively small, we obtain informative CIs in most cases.
Tables 7 18 show the proportion of the baselines which lie in the three trade-off regions, 'Unlikely', 'Permissible' and 'Sub-optimal" for the Bernstein's 's CIs, across the different datasets and fairness metrics. Overall, it can be seen that our Cls are reliable since the proportion of trade-offs which lie below our CIs is small. On the other hand, the tables show that our CIs can detect a significant number of sub-optimalities in our baselines, showing that our intervals are informative.
F.5 Additional details for Figure
For Figure [ we consider a calibration data Den of size 2000. For the optimal model, we trained a YOTO model on the COMPAS dataset with the architecture given in F.1.I We train the model for a maximum of 1000 epochs, with early stopping based on validation losses. Once trained, we obtained the red and black curves by first splitting Deai randomly into two subsets, and evaluating the trade-offs on each split separately. On the other hand, for the sub-optimal model, we use another YOTO model with the same architecture but stop the training after 20 epochs. This results in the trained model achieving a sub-optimal trade-off as shown in the figure. We evaluated this trade-off curve on the entire calibration data.
32

---

hoeffdings Cls
bernstein Cls
YOTO (Ours)
KDE-fair logsig
linear RTO
reductions adversary
asymptotic Cls
bootstrap Cls
separate
0.20
0.20
0.20
Demogro Potto
Demegnatte Beety
0.15
0.15
0.15
0.10
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
0.76
0.78
0.80
0.62
0.84
0.86
0.76
0.78
0.80
0.82
0.84
0.88
0.76
0.78
0.80
0.52
0.84
0.08
Accuracy
Accuracy
Accuracy
(a) Daall 1000
(b) (Dai
5000
(c) DDail
10, 000
Figure 15: Demographic Parity results for Adult dataset
Equatesd Oeporueity
Equalzed Ogpotueity
Eouelzed Deporuuity
0.15
8.15
0.15
6.10
6.10
0.10
0.05
0.05
0.05
3.74
0.26
8.80
0.76
0.80
0.50
Accuracy
Accurasy
(a) [Dail 1000
(b) [Dai 5000
(c) (Dall
10, 000
Figure 16: Equalized Opportunity results for Adult dataset
0.20
6.20
0.20
0.15
Eqalted GHB
0.15
Equatred Crock
0.15
Equateed
0.10
0.00
74
0.76
0.78
0.80
0.82
0.84
0.00
0.74
0.76
0.78
0.80
0.82
0.84
0.00
0.74
0.76
0.78
0.80
0.82
0.84
Accuracy
Accuracy
Accuracy
(a) (Deal = 1000
(b) |Dail = 5000
(c) DDail
10, 000
Figure 17: Equalized Odds results for Adult dataset
Table Proportion of empirical trade-offs for each baseline which lie the three trade-off regions, for the COMPAS dataset and DP (using Bernstein's 's Cls). Here Deai is a 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
1.0
0.0
RTO
0.0
0.67
0.33
ADVERSARY
0.15
0.85
0.0
LINEAR
0.0
0.82
0.18
LOGSIG
0.05
0.2
0.75
REDUCTIONS
0.0
0.83
0.17
SEPARATE
0.0
1.0
0.0
F.6 Experimental results with FACT Frontiers
MA FACT and MS FACT yield conservative Pareto Frontiers. In Figure 27 we include the results for the Adult dataset along with the model-specific (MS) and model-agnoste (MA) FACT Pareto frontiers, obtained using the methodology [23]. can be seen that both Pareto frontiers, MS FACT and MA FACT are overly conservative, with the MA FACT being completely non-informative on the Adult dataset. The model-agnostic FACT trade-off considers the best-case trade-off for any given dataset and does not depend on specific model class. As result, there is no guarantee that this Pareto frontier achievable. This evident from the fact that the MA FACT yields non-informative Pareto frontier the Adult dataset in Figure 27 which is non-achievable in practice.
33

---

hoeffdings Cls
bernstein Cls
YOTO (Ours)
KDE-fair logsig
linear RTO
reductions
asymptotic Cls
bootstrap Cls
separate
adversary
0.15
0.15
0.15
Demogrppi Porty
Demegrane Perty
Demugraph Berty
0.10
0.10
0.10
0.05
0.05
0.03
0.00
0.50
0.55
0.60 Accuracy
0.65
0.20
0.00
0.50
0.55
0.60
0.65
0.70
0.00
6.50
0.55
0.60
0.85
0.70
Accuracy
Accuracy
(a) [Dail = 500
(b) Daai
1000
(c) [Dail = 5000
Figure 18: Demographic Parity results for COMPAS dataset
Orpettunts
0.06
0.06
0.06
0.04
0.04
0.04
0.02
0.00
0.02
0.00
0.60
6.30
0.60 Accunacy
0.50
0.55
0.50
0.55
Accunary
Accunecy
(a) [Deail 500
(b) (Dail 1000
(c) [Deal 5000
Figure 19: Equalized Opportunity results for COMPAS dataset
0.10
0.10
0.10
0.06
0.06
Exuuledd
0.06
0.02
0.02
0.00
0.00
0.50
0.55
0.60
0.65
0.70
0.50
0.55
0.60
0.65
0.70
0.50
0.55
0.60
0.65
0.70
Accuracy
Accurasy
Accuracy
(a) (Dail = 500
(b) Daall = 1000
(c) DDail = 5000
Figure 20: Equalized Odds results for COMPAS dataset
Table Proportion of empirical trade-offs for each baseline which lie the three trade-off regions, for the COMPAS dataset and EOP (using Bernstein's Cls). Here Deal is 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
0.99
0.01
RTO
0.0
0.96
0.04
ADVERSARY
0.0
1.0
0.0
LINEAR
0.0
1.0
0.0
LOGSIG
0.01
0.36
0.62
REDUCTIONS
0.03
0.77
0.2
SEPARATE
0.0
1.0
0.0
The model-specifee FACT trade-off curve is comparatively more realistic as it is derived using pre-trained model. However, it is important note that the trade-off for this pre-trained model may not lie on the obtained MS FACT frontier. In fact, MS FACT may still not be achievable by any model the given model class, as it does not provide any guarantee being achievable either. This can be seen from Figure 27 which shows that the MS-FACT frontier is not achieved by any of the SOTA baselines under consideration. In these experiments, we used logistic regression classifier as pre-trained model for obtaining the MS FACT frontier.
34

---

hoeffdings Cls
bernstein Cls
YOTO (Ours)
KDE-fair
linear
reductions
asymptotic Cls
bootstrap Cls
separate
logsig
RTO
adversary
0.150
6.150
0.150
Demegr-pphe Pwrtoy
0.125
0.125
0..12
Demegnapis
0.100
0.100
0.000
0.025
0.025
0.025
0.000
0.7
0.8
0.9
0.000
0.5
6.6
0.7
0.5
0.9
0.000
0.5
0.6
0.7
0.8
0.9
Accuracy
Accuracy
Accuracy
(a) Daal 1000
(b) Daai 5000
(c) Daal
10, 000
Figure 21: Demographic Parity results for CelebA dataset
Diggrfuutt int
aalled Drpertunly
0.05
0.05
0.05
0.03
0.05
0.03
0.02
0.02
0.00
20.01
0.001
0.00
0.00
0.00
0.88
0.91
0.92
Accuracy
Accuracy
Accurasy
(a) [Deal] 1000
(b) (aail 5000
(c) Paal
10, 000
Figure 22: Equalized Opportunity results for CelebA dataset
0.10
0.10
0.10
0.08
Equatted CAdes
0.08
Equatred Crlck
0.08
Equattes
0.06
0.06
0.06
0.5
0.6
0.7
0.8
0.3
0.5
0.6
0.7
0.8
0.5
0.00
0.5
0.6
0.7
0.8
0.9
Accuracy
Accuracy
Accuracy
(a) [Deal 1000
(b) DDail 5000
(c) DDail 10,
000
Figure 23: Equalized Odds results for CelebA dataset
Table 9: Proportion of empirical trade-off's for each baseline which lie in the three trade-off regions, the COMPAS dataset and BO (using Bernstein's Cls). Here Deal a 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
1.0
0.0
RTO
0.0
0.89
0.11
ADVERSARY
0.0
1.0
0.0
LINEAR
0.0
0.76
0.24
LOGSIG
0.0
0.45
0.55
REDUCTIONS
0.0
0.7
0.3
SEPARATE
0.1
0.87
0.03
E.7 Synthetic data experiments
real-world settings, the ground truth trade-off curve Tiair remains intractable because we only have access to finite dataset. In this section, we consider synthetic data setting, where the ground truth trade-off curve can be obtained, to verify that the YOTO trade-off eurves are consistent with the ground truth and that the confidence intervals obtained using methodology contain Thar
Dataset Here, we consider a setup with X A ~ Berm(0.5) and we define the conditional distributions X A as:
A {0, 1} and y {0, 1}. Specifically,
X == a~
35

---

hoeffdings Cls
bernstein Cls
YOTO (Ours)
KDE-fair logsig
linear
reductions
asymptotic Cls
bootstrap Cls
separate
RTO
adversary
0.05
0.05
0.05
0.04
20.04
0.04
0.03
pemogaa
0.02
0.55
0.60
0.65 Accuracyy
0.70
0.25
0.55
0.60
0.65 Accuracy
0.70
0.75
0.55
0.60
0.65
0.70
0.75
Accuracy
(a) Daal 1000
(b) (aai
5000
(c) Daal
10, 000
Figure 24: Demographic Parity results for Jigsaw dataset
Eqaiioo opportat
0.00
Eqalland Orgartuntyy
20.00
Equilbed Drgerfunky
00.06
0.04
0.04
0.04
0.02
0.02
0.02
0.00
0.00
0.00
0.55
0.50
0.50
Accuraty
Accuraty
Accuracy
(a) [Deal] 1000
(b) Daall 5000
(c) (Daal
10, 000
Figure 25: Equalized Opportunity results for Jigsaw dataset
0.08
6.06
0.08
Equatted 060s
Equatred Cets
Equatred Cales
0.04
0.04
0.04
0.02
0.50
0.55
0.60
0:65
0.70
0.75
0.50
0.55
0.60
0.65
0.70
0.75
0.50
0:55
0.60
0.65
0.70
0.75
Accursty
Accuracy
Accuracy
(a) (Dail 1000
(b) Daall
5000
(c) D
10, 000
Figure 26: Equalized Odds results for Jigsaw dataset
Table 10: Proportion of empirical trade-off's for each baseline which lie in the three trade-off regions, for the Adult dataset and DP (using Bernstein's Cls). Here D 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
1.0
0.0
RTO
0.0
0.33
0.67
ADVERSARY
0.0
0,0
1.0
LINEAR
0.13
0.47
0.4
LOGSIG
0.0
0,27
0.73
REDUCTIONS
0.0
0.13
0.87
SEPARATE
0.03
0.95
0.02
Moreover, we define the labels Y as follows:
Y = Z 1(X > 0.5) + (1- L(X < 0.5).
where Z ~ Bern( and Z IL X. Here, Z introduces some 'noise' to the labels Y and means that perfect accuracy is not achievable by linear classifiers. If perfect accuracy was achievable, the optimal values for Equalized Odds and Equalized Opportunity would be 0 (and would be achieved by the perfect classifier). therefore our use of 'noisy' labels Y ensures that the ground truth trade-off curves will be non-trivial.
YOTO model training Using the data generating mechanism, we generate 5000 training datapoints, which we use train the YOTO model. The YOTO model for this dataset comprises of a simple
36

---

Table 11: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions, for the Adult dataset and EOP (using Bernstein's 's Cls). Here Dent is a 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.07
0.89
0.04
RTO
0.0
0.5
0.5
ADVERSARY
0.0
0,36
0.64
LINEAR
0.0
0.5
0.5
LOGSIG
0.0
0.09
0.91
REDUCTIONS
0.0
0.17
0.83
SEPARATE
0.02
0.95
0.03
Table 12: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions, for the Adult dataset and EO (using Bernstein's 's Cls). Here Deal is 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL.
KDE-FAIR
0.0
1.0
0.0
RTO
0.0
0.4
0.6
ADVERSARY
0.0
0,36
0.64
LINEAR
0.0
0.4
0.6
LOGSIG
0.0
0.65
0.35
REDUCTIONS
0.0
0.1
0.9
SEPARATE
0.0
1.0
0.0
hoeffdings Cls
bootstrap Cls
logsig linear reductions
adversary
RTO
asymptotic Cls
YOTO (Ours)
MA FACT
MS FACT
bernstein Cls
separate
Equalted O Oportuatty wty
(aalleed 049%
0.85 Accuracy
Accuracy
Acturacy
Figure 27: Results on the Adult dataset with FACT frontiers (pre-sensitivity analysis, i.c. A(ha) = 0).
Here, (Deal 2000 and 0.05.
logistic regression as the main model, with only the scalar logit outputs of the logistic regression being conditioned using FiLM. The MLPs My, M, both have two hidden layers, each of size 4, and ReLU activations. We train the model for a maximum of 1000 epochs, with early stopping based on validation losses. Training these simple model only requires one CPU and takes roughly minutes.
Ground truth trade-off curve To obtain the ground truth trade-off curve Thir we consider the family of classifiers
=(x))_(XX >
for c IR. Next, we calculate the trade-offss achieved by this model family for fine grid of c values between -3 and 3, using a dataset of size 500,000 obtained using the data-generating mechanism described above. The large dataset size ensures that the finite sample errors in accuracy and fairness violation values are negligible. This allows us to reliably plot the trade-off curve Thir-
E.7.1 Results
shows the results for the synthetic data setup for three different fairesss violations, obtained using calibration dataset Deal of size 2000. It can be seen that for each fairness violation considered, YOTO trade-off curve aligns very well with the ground-truth trade-off curve The Additionally, also consider four different confidence intervals obtained using methodology, and Figure 28
37

---

be intuitively Table 13: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions, for the CelebA dataset and DP (using Bernstein's s Cls). Here Daal is 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
1.0
0.0
RTO
0.0
0.56
0.44
ADVERSARY
0.0
0.18
0.82
LINEAR
0.0
0.88
0.12
LOGSIG
0.05
0.95
0.0
SEPARATE
0.0
1.0
Table 14: Proportion of empirical trade-off's for each baseline which lie in the three trade-off regions, for the CelebA dataset and EOP (using Bernstein's 's Cls). Here Deal is 10% dataset split.
UNLIKELY
PLAUSIBLE
KDE-FAIR
0.0
0.91
0.09
RTO
0.0
0.45
0.55
ADVERSARY
0.0
0.27
0.73
LINEAR
0.15
0.82
0.03
LOGSIG
0.0
0.73
0.27
SEPARATE
0.0
1.0
0.0
shows that each of the four confidence intervals considered contain the ground-truth trade-off curve. This empirically verifies the validity of our confidence intervals in this synthetic setting.
Additionally, in Figure 29 plot how the worst-case values for ((h) change (relative to the optimal trade-off ) as the number of training data Drr increases. Here, we use h2 as a short- hand notation ((bx))
for the YOTO model ha A) and the quantity the y-axis, maxxeλ TH ()cc(fx))
thought of as the worst-case error percentage between YOTO trade-off and the optimal trade-off. The figure empirically verifies result in Theorem 3.4 by showing that as the number of training data increases, the error term declines across all fairness metrics.
hoeffdings Cls
asymptotic Cls
bernstein Cls
bootstrap Cls -
YOTO (Ours)
GT tradeoff
Eounttedd Orportunty
70.80
0.80
Equaliee Dats
0.80
0.60
0.60
0.60
0.40
0.40
0.40
0.20
0.00
0.00
0.00
Accurwcy
Arcunacy
Accurary
Figure 28: Results for the synthetic dataset with ground truth trade-off curves Tair"
38

---

Table 15: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions, for the CelebA dataset and EO (using Bernstein's 's Cls). Here Paal is a 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL.
KDE-FAIR
0.0
1.0
0.0
RTO
0.0
0.71
0.29
ADVERSARY
0.0
0.27
0.73
LINEAR
0.0
0.97
0.03
LOGSIG
0.0
0.73
0.27
SEPARATE
0.0
1.0
0.0
Table 16: Proportion of empirical trade-offs for each baseline which lie in the three trade-off regions, for the Jigsaw dataset and DP (using Bernstein's 's Cls). Here Deat is 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
0.92
0.08
RTO
0.0
0.5
ADVERSARY
0.0
0.09
0.91
LINEAR
0.0
0.76
0.24
LOGSIG
0.0
0.4
0.6
SEPARATE
0.0
0.88
0.12
0.10
DP
EOP
0.08
EO
T (accib]l
max Alh))
0.06
0.04
0.02
0.00
0
2500
5000
7500
10000 12500 15000 17500 20000 Drdl
Plot showing how A(h) decreases (relative to the ground truth trade-off value Tair (ace(h)) as the training data size [Pu] increases. Here, we plot worst (i.e. largest) value of ((hx)/ Tin (aco(hx)) achieved by our YOTO model over grid of values in [0, 5].
Figure 29:
Table 17: Proportion of empirical trade-off's for each baseline which lie in the three trade-off regions, for the Jigsaw dataset and EOP (using Bernstein's Cls). Here Daai is 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
0.83
0.17
RTO
0.0
0.62
0.38
ADVERSARY
0.06
0.94
0.0
LINEAR
0.14
0.59
0.27
LOGSIG
0.0
0.29
0.71
SEPARATE
0.0
0.47
0.53
39

---

Table 18: Proportion of empirical trade-off's for each baseline which lie in the three trade-off regions, for the Jigsaw dataset and EO (using Bernstein's 's Cls). Here Deal is a 10% dataset split.
UNLIKELY
PLAUSIBLE
SUB-OPTIMAL
KDE-FAIR
0.0
0.75
0.25
RTO
0.0
0.57
0.43
ADVERSARY
0.0
1.0
0.0
LINEAR
0.0
0.73
0.27
LOGSIG
0.0
0.4
0.6
SEPARATE
0.0
0.87
0.13
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section 3 includes the theoretical results and Section includes the experimen- tal results claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section includes a discussion of the limitations our methodology.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- lant role in developing norms that preserve the integrity of the community, Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
41

---

Justification:
Appendix A contains all proofs and assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Appendix F contains comprehensive practical details needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
42

---

Answer: [Yes]
Justification: Our code has been made open source, and link to our code has been included in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (httpss//nips.cc/pbblee
guides/CodeSubmissionnnP
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https Stwpabbbieguuidesoooeeebbnneeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 5 and Appendix FrcenddxxFiincuuce include the training and test details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Table in Section 5 report the standard errors in our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
43

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Fiincluess information the compute resources used.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have tried to be transparent regarding our methodology, and theoretical and practical details to reproduce and use our method in practice.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The Introduction (Section and Preliminaries (Section discuss the implica- tions of our method for fairness decisions. We contribute to better auditing of model faimess standards and are unaware of the negative social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: We use open-source data to train models. We do not release trained models (only the code used to train the models).
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperssitheode. setersswthhcdd.ccc/aaaaatttt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have included details of our code and models in our submission.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "VRKI0rEvB0", "reviewer": "Reviewer_3zFr", "summary": "This paper proposes a computationally efficient method to estimate the accuracy-fairness trade-off curve with the statistical guarantee given the dataset and model class. Specifically, it first adopts an existing method, You-Only-Train-Once (YOTO), to get the trade-off curve and then proposes a systematic way to obtain the confidence intervals for fairness and accuracy.", "questions": "Please see Weakness.", "limitations": "The method requires an in-distribution calibration dataset and only applies to in-distribution tests.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The research problem on the fairness-accuracy tradeoff is fundamental and practical. There is rarely literature that touches on this problem.\n2. Considering the finite sample error, the confidence interval is essential for tradeoff investigation. This paper proposes a systematic way to investigate this problem.\n3. The paper is well-written and easy to follow.", "weaknesses": "1. The research focus, the fairness-accuracy tradeoff, is computationally expensive since the auditing process usually involves multiple model training. Even though the author adopts a computation-efficient YOTO framework to tackle this issue. However, the main contribution on the efficiency side is mainly from existing work. I suggest the authors highlight the values of statistical guarantee. For example, given the statistical guarantee, can the authors provide a more comprehensive evaluation or any insights for model training? Otherwise, the audience may have a \"so what\" question in mind.\n2. I understand the general clue for deriving confidence intervals for the fairness and accuracy side, but I am still confused about how the authors estimate confidence intervals in practice, especially for sensitivity $\\Delta(h_{\\lambda})$. (1) How do you estimate or justify $\\Delta(h_{\\lambda})$ without know Pareto optimality? It seems to be counter-intuitive. (2) Do you consider Pareto optimality only for specific model classes? I am curious about \"When YOTO satisfies Pareto optimality\" (Line 693). If the main conclusion only holds under specific model classes, it would be better to highlight such condition. (3) I suspect the analysis is rigorous. For example, for Hoeffding’s inequality in Line 215, $\\tilde{acc}$ should be the expectation of $acc$. However, $\\tilde{acc}$ is the accuracy of $h_{\\lambda}$ on $D_{cal}$, which is a realization (not mean) of ACC variable.\n3. I notice that there is a similar literature at https://openreview.net/forum?id=dSbbZwCTQI, which also trains once with flexible tradeoffs. The main idea of YODO is to ``line'' in the weight space that connects the accuracy-optimum and fairness-optimum points using a single model, which is different from YOTO manner. It would be better to highlight the difference and why the authors chose YOTO instead of YODO.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful review and for highlighting the strengths of our work, including its motivation and presentation. Below we address some of the questions raised.\n> [...] given the statistical guarantee, can the authors provide a more comprehensive evaluation or any insights for model training? [...]\n\nOur confidence intervals (CIs) are designed to equip practitioners with an auditing tool to assess fairness trade-offs for different model classes and datasets. \n\nIf for a classifier $h_0$, the accuracy-fairness trade-off lies above our proposed upper CIs (i.e. in the pink region in Figure 1), then with probability $1-\\alpha$ the classifier $h_0$ achieves a sub-optimal trade-off (i.e., there exists another classifier $h' \\in \\mathcal{H}$ with $acc(h') \\geq acc(h_0)$ and $\\Phi_{fair}(h') \\leq \\Phi_{fair}(h_0)$).\nIn this case, one should explore alternative fairness methodologies and model architectures until the model achieves a trade-off in the \"permissible trade-off region\" (green area in Figure 1). In this way, our CIs can also guide algorithm development, as researchers can use the permissible region of trade-offs identified by our CIs as a target during the design of improved algorithms.\n\nIt is worth emphasising that unlike prior works which only consider the empirical accuracy-fairness trade-offs, our CI-based methodology is the first to avoid false conclusions arising from finite-sampling errors, thereby offering more reliable insights in realistic data-limited scenarios, as we demonstrate empirically in Figure 1.\n\n> How do you estimate or justify $\\Delta(h_\\lambda)$ without known Pareto optimality?\n\nFirst, we recall that $\\Delta(h_\\lambda)$ (defined in Figure 2a) intuitively denotes the gap between the trade-off achieved by YOTO and the optimal achievable trade-off $\\tau^*_{fair}$, and is an unknown quantity in general. Therefore, for practical purposes, we use sensitivity analysis to posit 'plausible' values for this quantity.\nThe high-level idea behind our procedure is to calibrate the value of $\\Delta(h_\\lambda)$ using some additional models trained separately using standard methods with varying fairness constraints.\n\n**Sensitivity analysis**\nExplicitly, our sensitivity analysis approach is as follows: First, aside from our YOTO model, our sensitivity analysis procedure uses $k$ additional models $\\mathcal{M} :=$ { $h_1, ..., h_k$ } trained separately using standard regularized loss (in Eqn. (2) of our paper).\n\nLet $\\mathcal{M_0} \\subseteq \\mathcal{M}$ be the models which achieve a better empirical trade-off than our YOTO model (see Figure 2b in our main text). We choose $\\Delta(h_\\lambda)$ for our YOTO model to be the maximum gap between the empirical trade-offs of these models in $\\mathcal{M}_0$ and the YOTO model. In practice, this shifts our lower CIs downward until all the trade-offs for models in $\\mathcal{M}$ lie above our lower CIs.\n\n**Intuition**\nIf we assume that training models separately for each fairness constraint recovers the optimal trade-off curve, then we could in principle obtain this optimal curve by training many different models, although at a significant computational cost. Our approach instead offers a compromise between the optimality of trade-offs and computational cost, as we instead train a few models with fairness regularization parameters $\\lambda$ sampled uniformly and use these to posit plausible values for $\\Delta(h_\\lambda)$. (In our experiments, we found that using 2 separately trained models for sensitivity analysis was sufficient.) \n\n> Do you consider Pareto optimality only for specific model classes?\n\nOur methodology remains valid for any model class $\\mathcal{H}$ which can be optimised using gradient-based methods. In this setting, the models in $\\mathcal{H}$ can be trained using a YOTO-style architecture and hence our methodology remains applicable. While we mention this in Section 2.1 (lines 108-109), we will highlight this further in the updated manuscript. \n\n> [...] for Hoeffding’s inequality in Line 215, $\\tilde{acc}$ should be the expectation of $acc$ [...]\n\nWe wish to clarify that  $\\widetilde{acc(h_\\lambda)}$ is indeed a random variable. Formally,  \n    $$\n\\widetilde{acc(h_\\lambda)} := \\sum_{(X_i, Y_i) \\in D_{cal}} \\frac{1(h_\\lambda(X_i) = Y_i)}{|D_{cal}|}.\n    $$\n    Then, Hoeffding's inequality shows that with probability at least $1-\\alpha$ we have that\n    $$\n    |\\widetilde{acc(h_\\lambda)} - \\mathbb{E}[\\widetilde{acc(h_\\lambda)}] | \\leq \\sqrt{\\log{(2/\\alpha)}/(2|D_{cal}|)}. \n    $$\n    Then, Lemma 3.1 follows from the fact that $acc(h_\\lambda) = \\mathbb{E}[\\widetilde{acc(h_\\lambda)}]$.\n\nWe will clarify this further in the final version. \n\n> [...] It would be better to highlight the difference and why the authors chose YOTO instead of YODO\n\nFirstly, we thank the reviewer for pointing us to this manuscript. The YODO architecture comprises two sets of parameters, each corresponding to accuracy and fairness optimisation respectively. \nThis means that, for a given size of the main model, the YODO architecture will require the optimisation of twice as many parameters as the standard model.\n\nIn contrast, the YOTO architecture does not split the weights but instead uses the FiLM layers to dynamically adapt the hidden layers of the models depending on the fairness regularization parameter $\\lambda$.\nConsequently, YOTO only adds a relatively small number of additional parameters as it only involves two additional MLPs which can be significantly smaller than the main model. (See Appendix F.1 for more details on model architectures.) As a result, training YOTO can be computationally cheaper, especially in cases where the main model is very large. \nFor completeness, we will include a comprehensive discussion of this comparison in the final version of our paper.\n\nWe hope that we were able to address all the reviewer's questions and hope that the reviewer would consider increasing their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7F6mGzeB3q", "reviewer": "Reviewer_NxJb", "summary": "Considering inherent accuracy-fairness trade-off in real-world scenarios with data imbalance and bias, imposing strict fairness constraint could be impractical. To address this, the paper introduces an efficient method to contextualize and accurately estimating fairness-accuracy trade-off curve for each dataset. The proposed YOTO ease redundant model training to realize the trade-off curves. Also, the paper presents a method to quantify the confidence of the estimate.", "questions": "- Can I understand the trade-off curve estimated by proposed method similar to Pareto Frontier with CIs inherent in dataset when model design is specified? If so, I think it would be worth mentioning related thresholding post-processing methods [1,2].\n- I think we can easily interpret points reside in upper-left are suboptimal in Figure 3. However, how can we interpret the ones reside in lower-right region? Does this mean the proposed trade-off estimate and corresponding CI is not accurate?\n\n\n\n[1] Kim, Joon Sik, Jiahao Chen, and Ameet Talwalkar. \"FACT: A diagnostic for group fairness trade-offs.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Jang, Taeuk, Pengyi Shi, and Xiaoqian Wang. \"Group-aware threshold adaptation for fair classification.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 6. 2022.", "limitations": "Please see the questions and weaknesses above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clarity of the writing: The paper is easy to follow and well-motivated.\n- Novel Approach: The paper introduces a novel method to approximate the fairness-accuracy trade-off curve efficiently, which is a significant improvement over traditional methods requiring multiple model trainings.\n- Computational Efficiency: By leveraging the YOTO framework, the proposed method reduces the computational burden, making it feasible for large datasets and complex models.\n- Practical Utility: The framework provides a practical tool for auditing model fairness, offering a principled way to select data-specific fairness requirements and assess compliance.", "weaknesses": "- Data Dependency: The methodology requires separate datasets for training and calibration, which may not be feasible in situations with limited data.\n- Assumptions for Statistical Guarantees: The statistical guarantees rely on assumptions that may not hold in all practical scenarios, potentially limiting the generalizability of the results.\n- Objective Formulation Dependency: The trend (scattered points) of YOTO and corresponding CIs are specifically designed for relaxed fairness metric rather than explicit fairness notion, which may make the boundary inaccurate. In other words, trade-off curve and CIs can be sensitive to fairness loss formulation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for acknowledging the novelty and practical utility of our approach and the clarity of our writing. We respond to the questions raised below.\n\n> Assumptions for Statistical Guarantees: The statistical guarantees rely on assumptions that may not hold in all practical scenarios, potentially limiting the generalizability of the results.\n\nWe would like to clarify that while Theorem 3.4 relies on regularity assumptions, our statistical guarantee in Proposition 3.2 does not require any additional assumptions beyond the exchangeability of data. \nIn specific, Proposition 3.2 provides the 'worst-case' optimal trade-off, accounting for finite-sample uncertainty and the upper CIs obtained remain valid even if the YOTO classifier $h_\\lambda$ is not trained well (and hence achieves sub-optimal accuracy-fairness trade-off), although in such cases the CI may be conservative.\nThis means that any trade-off which lies above the upper CIs is guaranteed to be suboptimal with probability $1-\\alpha$ without any additional assumptions.\n\n> Objective Formulation Dependency: [...] trade-off curves and CIs can be sensitive to fairness loss formulation\n\nWhile the trade-offs and CIs obtained may be sensitive to the fairness loss formulation, it is important to emphasise that our coverage guarantees in Propositions 3.2 and 3.3 are independent of the fairness loss formulations. \nSpecifically, our upper CIs obtained in Proposition 3.2 remain valid regardless of the fairness loss used. \nSimilarly, for the lower CIs, our sensitivity analysis should adjust the lower CIs to account for any sub-optimalities in the estimated trade-off curve arising from our choice of fairness loss in practice.\n\nThis is also evident from our experimental results in Section 5 where we consider baselines with various fairness loss formulations, and show that the obtained trade-offs are overall consistent with our CIs.\n\n> Can I understand the trade-off curve estimated by proposed method similar to Pareto Frontier with CIs inherent in dataset when model design is specified? If so, I think it would be worth mentioning related thresholding post-processing methods [1,2].\n\nWe thank the reviewer for their question. It is important to clarify the distinct goals of our work and those in [1,2]. Our focus in this work is on reliably approximating the optimal accuracy-fairness trade-offs achievable within a specific model class, $\\mathcal{H}$, using the finite data available. To achieve this, we construct CIs with probabilistic guarantees of the form $\\mathbb{P}(\\tau^*_{fair}(\\Psi) \\in \\Gamma^\\alpha) \\geq 1-\\alpha$. \n\nThis is in contrast to [1, 2] which provide upper bounds on the best achievable accuracy-fairness trade-off when infinite data is available. While these works offer valuable theoretical insights, there is no guarantee regarding whether this upper bound is achievable by the model class under consideration, given available data. In fact, we consider the FACT Pareto frontiers proposed in [1] in Appendix F.6, where we show empirically that these Pareto frontiers are highly conservative and are not achieved by any of the SOTA baselines we considered. We will further highlight these distinctions in our updated manuscript.\n\n> I think we can easily interpret points reside in upper-left are suboptimal in Figure 3. However, how can we interpret the ones reside in lower-right region? Does this mean the proposed trade-off estimate and corresponding CI is not accurate?\n\nOur confidence intervals (CIs) quantify the range of most likely trade-offs achievable for a given finite dataset and model class. \nIn particular, our CIs only offer coverage of at least $1-\\alpha$. \nThis means that if a baseline's trade-off falls below the CIs (i.e. in the blue region in Figure 1) then this would suggest that the model achieves an exceptionally good accuracy-fairness trade-off, although in practice this will rarely occur (i.e. with a probability of at most $\\alpha$). \nThis is also consistent with our experimental results, where we consider \n$\\alpha = 0.05$. Our results in Table 1 verify that less than 5\\% of the SOTA baseline trade-offs fall below our lower CIs, as promised by Proposition 3.3.\n\nWe hope that the above has addressed the questions raised by the reviewer adequately and that the reviewer will consider raising their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uZZHApJrS3", "reviewer": "Reviewer_Vp4R", "summary": "This paper addresses a significant limitation in the fairness literature, which is the use of uniform fairness requirements across diverse datasets. It proposes the YOTO framework to approximate the fairness-accuracy trade-off and reduce computational costs while existing methods typically require multiple models for training.", "questions": "In Lemma 3.1, $\\delta$ specifies the relationship between the confidence interval and the data size of the held-out set. Is there any requirement for the size of the held-out calibration dataset to guarantee an effective measure for the confidence intervals?", "limitations": "The authors have adequately addressed the limitations. Since this work is mainly about fairness, I do not see any negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality: This paper discusses the problems associated with using uniform fairness metrics across diverse datasets and provides a framework for choosing fairness guidelines based on the characteristics of individual datasets. While this issue has been addressed in the fairness literature, this paper proposes a new framework to tackle it. Unlike previous work that recovers a single point on the trade-off curve corresponding to pre-specified fairness constraints during the training procedure, this method estimates the entire trade-off curve.\n\n- Quality and Clarity: The paper is well-constructed and is easy-to-follow. The motivation and research question are clearly stated. The theoretical analysis is solid. The experiment is conducted across three different practical applications (tabular data, image, and text), which is rigorous.\n\n- Significance: This paper proposes a novel framework to approximate the accuracy-fairness trade-off curve, which is an important and efficient evaluation paradigm for providing fairness guidelines in practice. The method has a practical advantage, allowing decision-makers to observe the minimum fairness violation that a particular dataset could have as the model accuracy increases.", "weaknesses": "- The content in lines 121-126 that illustrates the suboptimal problem, as shown in Figure 1, is highly similar to the content in lines 61-66. This content should be summarized to make it more concise.\n- Since this work is based on YOTO, YOTO should be introduced in the Preliminary section for better illustration.\n- Section 3.1 should also be introduced in the Preliminary section, as it is the basic in-processing framework for fairness.\n- There is a lack of dataset and experiment setup descriptions, including data size, sensitive attributes chosen, held-out set size, and train-test split ratio.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's recognition of the quality and originality of our work. We clarify the questions raised below.\n\n> The content in lines 121-126 that illustrates the suboptimal problem, as shown in Figure 1, is highly similar to the content in lines 61-66. This content should be summarized to make it more concise [...]\nSince this work is based on YOTO, YOTO should be introduced in the Preliminary section for better illustration [...]\nSection 3.1 should also be introduced in the Preliminary section, as it is the basic in-processing framework for fairness [...]\n\nWe thank the reviewer for their suggestions regarding the structure of our write-up and will make the proposed modifications to the final version of our paper. \n\n> There is a lack of dataset and experiment setup descriptions, including data size, sensitive attributes chosen, held-out set size, and train-test split ratio.\n\nDue to space constraints, we have included comprehensive details about our experimental setup in Appendix F of our paper. This includes dataset details (including dataset sizes), sensitive attributes chosen, model architectures used for both, our YOTO model and the baselines, and training details (such as the number of epochs, compute resources used, methodology of early stopping and fairness losses). For completeness, we will also include the key details in the final version of our main text. \n\n> In Lemma 3.1, $\\delta$ specifies the relationship between the confidence interval and the data size of the held-out set. Is there any requirement for the size of the held-out calibration dataset to guarantee an effective measure for the confidence intervals?\n\nIn general, Hoeffding's inequality provides finite-sample guarantees which remain valid regardless of the size of the calibration dataset. However, if the calibration dataset size is low, the CIs obtained might be more conservative (and hence less informative). \nThe width of the CIs decreases as the calibration dataset size increases, thereby leading to more informative confidence intervals. In fact, it can be seen from Lemma 3.1 that the width of the CIs on $acc(h_\\lambda)$ is $\\mathcal{O}(1/\\sqrt{|D_{cal}|})$. \n\nTo investigate how the calibration dataset size impacts the informativeness of our CIs in practice, we have conducted comprehensive ablation studies across different datasets in Appendix F.4. Our empirical results show that while the informativeness of the CIs for a given calibration dataset size depends on the fairness metric and dataset under consideration, we observe that in many cases the CIs obtained are informative when the size of calibration dataset is at least 1000. \n\nWe hope the above addressed the concerns raised by the reviewer and that the reviewer will consider increasing their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors introduce a new method to estimate the fairness-accuracy tradeoff (and the uncertainty over this tradeoff) in a single training run. This method involves adapting the previously proposed YOTO framework to compute suitable confidence intervals over the dataset at hand. The reviewers were excited by the novelty of the proposed approach and the potential for more sample efficient fair learning.
Decision: Accept (poster)