Achievable Fairness on Your Data With Utility Guarantees

Authors: muhammad  faaiz taufiq
jean-françois  ton
yang  liu
santa  cruz
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:46:14

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.

Main paper: 
 introduction: 
 A key challenge in fairness for machine learning is to train models that minimize disparity across various sensitive groups such as race or gender [9, 35, 10] . This often comes at the cost of reduced model accuracy, a phenomenon termed accuracy-fairness trade-off [36, 32] . This trade-off can differ significantly across datasets, depending on factors such as dataset biases, imbalances etc. [1, 8, 11] .To demonstrate how these trade-offs are inherently dataset-dependent, we consider a simple example involving two distinct crime datasets. Dataset A has records from a community where crime rates are uniformly distributed across all racial groups, whereas Dataset B comes from a community where historical factors have resulted in a disproportionate crime rate among a specific racial group. Intuitively, training models which are racially agnostic is more challenging for Dataset B, due to the unequal distribution of crime rates across racial groups, and will result in a greater loss in model accuracy as compared to Dataset A. This example underscores that setting a uniform fairness 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 Figure 1 : Accuracy-fairness 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 area shows unlikely-to-be-achieved ones. (Details in Appendix F.5) dataset necessitates careful consideration of its individual characteristics and underlying biases. In this work, we advocate against the use of one-size-fits-all fairness mandates by proposing a nuanced, dataset-specific framework for quantifying acceptable range of accuracy-fairness trade-offs. To put it concretely, the question we consider is:Given a 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-fairness 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 [8, 33] to 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 to obtain a good approximation of the trade-off curve, making them computationally infeasible for large datasets or models. Secondly, these works do not account for finite-sampling errors in the obtained curve. 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.We illustrate this phenomenon in Figure 1 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 on 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) as 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 accuracy-fairness trade-off curve, supported by rigorous statistical guarantees. Our methodology not only circumvents the need to train multiple models (leading to at least a 10-fold reduction in computational cost) but is also the first to quantify the uncertainty in the estimated curve, arising from both, finite-sampling error as well as estimation error. To achieve this, our approach adopts a novel probabilistic perspective and provides guarantees that remain valid across all finite-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 1 ), or if it stems from genuine deficiencies in the fairness interventions applied (as in the blue curve).The contributions of this paper are three-fold:• We present a computationally efficient methodology for approximating the accuracy-fairness trade-off curve by training only a single model. This is achieved by adapting a technique from [15] called You-Only-Train-Once (YOTO) to the fairness setting. • To account for the approximation and finite-sampling errors, we introduce a novel technical framework to construct confidence intervals (using the trained YOTO model) which contain the optimal accuracy-fairness trade-off curve with statistical guarantees. For any accuracy threshold ψ chosen at inference time, this gives us a statistically backed range of permissible fairness violations [l(ψ), u(ψ)], allowing us to answer our previously posed question:Given a dataset, the permissible range of fairness violations corresponding to an accuracy threshold of ψ is [l(ψ), u(ψ)] for models in a given class H.• 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 our intervals are both reliable and informative. 
preliminaries: 
 Notation Throughout this paper, we consider a binary classification task, where each training sample is composed of triples, (X, A, Y ). X ∈ X denotes a vector of features, A ∈ A indicates a discrete sensitive attribute, and Y ∈ Y := {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 fairness violations Φ fair (h) ∈ [0, 1] for a classifier model h : X → Y when A = {0, 1}:Demographic Parity (DP) The DP condition states that the selection rates for all sensitive groups are equal, i.e. P(h(X) = 1 | A = a) = P(h(X) = 1) for any a ∈ A. The absolute DP violation is:Φ DP (h) := |P(h(X) = 1 | A = 1) -P(h(X) = 1 | A = 0)|.Equalized Opportunity (EOP) The EOP condition states that the true positive rates for all sensitive groups are equal, i.e. P(h(X) = 1 | A = a, Y = 1) = P(h(X) = 1 | Y = 1) for any a ∈ A. The absolute EOP violation is:Φ EOP (h) :=|P(h(X) = 1 | A = 1, Y = 1) -P(h(X) = 1 | A = 0, Y = 1)|.Next, we formalise the notion of accuracy-fairness trade-off, which is the main quantity of interest in our work. For a model class H (e.g., neural networks) and a given accuracy threshold ψ ∈ [0, 1], we define the optimal accuracy-fairness trade-off τ * fair (ψ) as, τ * fair (ψ) := min h∈H Φ fair (h) subject to acc(h) ≥ ψ.Here, Φ fair (h) and acc(h) denote the fairness violation and accuracy of h over the full data distribution. For an accuracy ψ ′ which is unattainable, we define τ * fair (ψ ′ ) = 1 and we focus on 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 τ * fair . In contrast, previous works [1, 11] impose an apriori fairness constraint during training and therefore each trained model only recovers one point on the trade-off curve corresponding to 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 as 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-fairness trade-off lies on this curve. Nevertheless, obtaining this ground-truth trade-off curve exactly is impossible within the confines of a finite-sample regime (owing to finite-sampling errors). This means that even if baseline 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 on the full data distribution.We illustrate this in Figure 1 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 compared to the red curve for accuracies in [0.62, 0.66], this apparent suboptimality is solely due to finite-sampling 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 1 , that account for such finite-sampling errors. In this case both trade-offs fall within our CIs which correctly indicates that this apparent suboptimality could stem from finite-sample variability. Conversely, a baseline's trade-off falling above our CIs (as in the blue curve in Figure 1 ) offers a confident assessment of suboptimality, as this cannot be explained away by finite-sample 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-offs alone.To achieve this, our proposed methodology adopts a two-step approach:1. Firstly, we propose loss-conditional fairness training, a computationally efficient methodology of estimating the entire trade-off curve τ * fair by training a single model, obtained by adapting the YOTO framework [15] to 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 τ * fair using the trained YOTO model. Specifically, given α ∈ (0, 1), we construct confidence intervals Γ α fair ⊆ [0, 1] which satisfy guarantees of the form:P(τ * fair (Ψ) ∈ Γ α fair ) ≥ 1 -α.Here, Γ α fair and Ψ ∈ [0, 1] are random variables obtained using a held-out calibration dataset D cal (see Section 3.2) and the probability is taken over different draws of D cal . 
methodology: 
 First, we demonstrate how our 2-step approach offers a practical and statistically sound method for estimating τ * fair (ψ). Figure 1 provides an illustration of our proposed confidence intervals (CIs) Γ α fair and shows how they can be interpreted as a range of 'permissible' values of accuracy-fairness trade-offs (the green region). Specifically, if for a classifier h 0 , the accuracy-fairness pair (acc(h 0 ), Φ fair (h 0 )) lies above the CIs Γ α fair (i.e., the pink region in Figure 1 ), then h 0 is likely to be suboptimal in terms of the fairness violation, i.e., there likely exists h ′ ∈ H with acc(h ′ ) ≥ acc(h 0 ) and Φ fair (h ′ ) ≤ Φ fair (h 0 ). On the other hand, it is unlikely for any model h ′ ∈ H to achieve a trade-off below the CIs Γ α fair (the blue region in Figure 1 ). Next, we outline how to construct such intervals.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 to solve, because the accuracy acc(h) and fairness violations Φ fair (h) are both non-smooth [1] . These constraints make it hard to use standard optimization methods that rely on gradients [25] . To get around this issue, previous works [1, 8] replace the non-smooth constrained optimisation problem with a smooth surrogate loss. Here, we consider parameterized family of classifiers H = {h θ : X → R | θ ∈ Θ} (such as neural networks) trained using the regularized loss:L λ (θ) = E[l CE (h θ (X), Y )] + λ L fair (h θ ).(2) where, l CE is the cross-entropy loss for the classifier h θ and L fair (h θ ) is a smooth relaxation of the fairness violation Φ fair [8, 29] . For example, when the fairness violation is DP, [8] considerL fair (h θ ) = E[g(h θ (X)) | A = 1] -E[g(h θ (X)) | A = 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-fairness 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 λ. 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] .As we describe above, a popular approach for approximating the accuracy-fairness trade-off τ * fair (ψ) involves training multiple models h θ * λ over a discrete grid of λ hyperparameters with the regularized loss L λ . To avoid the computational overhead of training multiple models, [15] propose 'You Only Train Once' (YOTO), a methodology of training one model h θ : X ×Λ → R, which takes λ ∈ Λ ⊆ R as an additional input using Feature-wise Linear Modulation (FiLM) [34] layers. YOTO is trained such that at inference time h θ (•, λ ′ ) recovers the classifier obtained by minimising L λ ′ in Eq. (2) .Recall that we are interested in minimising the family of losses L λ , parameterized by λ ∈ Λ (Eq. ( 2)). Instead of fixing λ, YOTO solves an optimisation problem where the parameter λ is sampled from a distribution P λ . As a result, during training the model observes many values of λ and learns to optimise the loss L λ for all of them simultaneously. At inference time, the model can be conditioned on a chosen value λ ′ and recovers the model trained to optimise L λ ′ . Hence, once adapted to our setting, the YOTO loss becomes: arg minh θ :X ×Λ→R E λ∼P λ [E[l CE (h θ (X, λ), Y )] + λ L fair (h θ (•, λ))] .Having trained a YOTO model, the trade-off curve τ * fair (ψ) 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 a single model. Although the model capacity assumption might be hard to verify in practice, our experimental section has shown that the trade-off curves estimates τ * fair (ψ) 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 τ * fair (ψ) may not align precisely with the true trade-off curve τ * fair (ψ). This discrepancy originates from two key factors. Firstly, the limited size of the training and evaluation datasets introduces errors in the estimation of τ * fair (ψ). Secondly, we opt for a computationally tractable loss function instead of the original optimization problem in Eq. ( 1). This may result in our estimation τ * fair (ψ) yielding sub-optimal trade-offs, as can be seen from Figure 1 . Therefore, to ensure that our procedure yields statistically sound inferences, we next construct confidence intervals using the YOTO model, designed to contain the true trade-off curve τ * fair (ψ) with high probability.As mentioned above, our goal here is to use our trained YOTO model to construct confidence intervals (CIs) for the optimal trade-off curve τ * fair (ψ) defined in Eq. ( 1). Specifically, we assume access to a held-out calibration dataset D cal := {(X i , A i , Y i )} i which is disjoint from the training data. Given a level α ∈ [0, 1], we construct CIs Γ α fair ⊆ [0, 1] using D cal , which provide guarantees of the form:P(τ * fair (Ψ) ∈ Γ α fair ) ≥ 1 -α.(3) Here, it is important to note that Ψ ∈ [0, 1] and Γ α fair are random variables obtained from the calibration data D cal , and the guarantee in Eq. ( 3) holds marginally over Ψ and Γ α fair . While our CIs in this section require the availability of the sensitive attributes in D cal , in Appendix D we also extend our methodology to the setting where sensitive attributes are missing. In this section, for notational convenience we useh λ (•) to denote the YOTO model h θ (•, λ) for λ ∈ Λ.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 τ * fair , involves first constructing CIs on test accuracy acc(h λ ) and fairness violation Φ fair (h λ ) for a given value of λ using D cal , denoted as C α acc (λ) and C α fair (λ) respectively satisfying, P(acc(h λ ) ∈ C α acc (λ)) ≥ 1 -α, and P(Φ fair (h λ ) ∈ C α fair (λ)) ≥ 1 -α. One way to construct these CIs involves using assumption-light concentration inequalities such as Hoeffding's inequality. To be more concrete, for the accuracy acc(h λ ): Lemma 3.1 (Hoeffding's inequality). Given a classifier h λ : X → Y, we have that,P acc(h λ ) ∈ acc(h λ ) -δ, acc(h λ ) + δ ≥ 1 -α.Here, acc(h) := (Xi,Ai,Yi)∈Dcal1(h(Xi)=Yi) |Dcal| and δ := 1 2|Dcal| log ( 2 α ).Lemma 3.1 illustrates that we can use Hoeffding's inequality to construct confidence interval C α acc (λ) = [ acc(h λ ) -δ, acc(h λ ) + δ] on acc(h λ ) such that the true acc(h λ ) will lie inside the CI with probability 1 -α. Analogously, we also construct CIs for fairness violations, Φ fair (h λ ), although 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(h λ ) and Φ fair (h λ ) for a model h λ , we next outline how to use these to derive CIs for the minimum achievable fairness τ * fair , 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.We first outline how to obtain one-sided upper confidence intervals on the optimum accuracy-fairness trade-off τ * fair (Ψ) of the form Γ α fair = [0, U λ fair ], which satisfies the probabilistic guarantee in Eq. (3). To this end, given a classifier h λ ∈ H, our methodology involves constructing one-sided lower CI on the accuracy acc(h λ ) and upper CI on the fairness violation Φ fair (h λ ). We make this concrete below: fair is an upper CI for τ * fair (L λ acc ), it follows that U λ fair is also a valid upper CI for τ * fair (ψ). 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 h λ is not trained well (and hence achieves sub-optimal accuracy-fairness trade-offs), although in such cases the CI may be conservative.Proposition 3.2. Given h λ ∈ H, let L λ acc , U λ fair ∈ [0,Having explained how to construct upper CIs on τ * fair (ψ), we next move on to the lower CIs.Obtaining lower confidence intervals on τ * fair (ψ) is more challenging than obtaining upper confidence intervals. We begin by explaining at an intuitive level why this is the case. Suppose that h λ ∈ H is such that acc(h λ ) = ψ, then since τ * fair denotes the minimum attainable fairness violation (Eq. ( 1)), we have that τ * fair (ψ) ≤ Φ fair (h λ ). Therefore, any valid upper confidence interval on Φ fair (h λ ) will also be valid for τ * fair (ψ). However, a lower bound on Φ fair (h λ ) cannot be used as a lower bound for the minimum achievable fairness τ * fair (ψ) in general. A valid lower CI for τ * fair (ψ) will therefore depend on the gap between fairness violation achieved by h λ , Φ fair (h λ ), and minimum achievable fairness violation τ * fair (ψ) (i.e., ∆(h λ ) term in Figure 2a ). We make this concrete by constructing lower CIs depending on ∆(h λ ) explicitly.Proposition 3.3. Given h λ ∈ H, let U λ acc , L λ fair ∈ [0, 1]be upper and lower CIs on acc(h λ ) and Φ fair (h λ ), i.e.λ ) ≤ U λ acc ) ≥ 1 -α/2, and P(Φ fair (h λ ) ≥ L λ fair ) ≥ 1 -α/2. Then, P τ * fair (U λ acc ) ≥ L λ fair -∆(h λ ) ≥ 1 -α, where ∆(h λ ) := Φ fair (h λ ) -τ * fair (acc(h λ )) ≥ 0.Proposition 3.3 can be used to derive lower CIs on τ * fair (ψ) at a specified accuracy level ψ, 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 ∆(h λ ) term, which is typically unknown. To circumvent this, we propose a strategy for obtaining plausible approximations for ∆(h λ ) in practice in the following section. Figure 2 : Visual illustrations for ∆(h) (Figure 2a ) and our sensitivity analysis procedure (Figure 2b ).Recall that ∆(h λ ) quantifies the difference between the fairness loss of classifier h λ and the minimum attainable fairness loss τ * fair (acc(h λ )), and is an unknown quantity in general (see Figure 2a ). Here, we propose a practical strategy for positing values for ∆(h λ ) which encode our belief on how close the fairness loss Φ fair (h λ ) is to τ * fair (acc(h λ )). This allows us 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 h λ . The main idea behind our approach is to calibrate ∆(h λ ) using additional separately trained standard models without imposing significant computational overhead.Details Our sensitivity analysis uses k additional models M := {h (1) , h (2) , . . . , h (k) } ⊆ H trained separately using the standard regularized loss L λ ′ (Eq. ( 2)) for some randomly chosen values of λ ′ . Let M 0 ⊆ M denote the models which achieve a better empirical trade-off than the YOTO model on D cal , i.e. the empirical trade-offs for models in M 0 lie below the YOTO trade-off curve (see Figure 2b ). We choose ∆(h λ ) for our YOTO model to be the maximum gap between empirical trade-offs of these separately trained models in M 0 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 a 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 as 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., ∆(h λ ) = 0), our sensitivity analysis leaves the CIs unchanged, thereby preventing unnecessary conservatism.Asymptotic analysis of ∆(h λ ) While the procedure described above provides a practical solution for obtaining plausible approximations for ∆(h λ ), we next present a theoretical result which provides reassurance that this gap should become negligible as the number of training data D tr increases. EQUATIONThen, given η ∈ (0, 1), under standard regularity assumptions, we have that with probability at least 1 -η, ∆(h) ≤ O(|D tr | -γ ), for some γ ∈ (0, 
related works: 
 Many previous fairness methods in the literature, termed in-processing methods, introduce constraints or regularization terms to the optimization objective. For instance, [1, 10] impose a priori uniform constraints on model fairness at training time. However, given the data-dependent nature of accuracyfairness trade-offs, setting a uniform fairness threshold may not be suitable. Other in-processing methods [37, 24] consider information-theoretic bounds on the optimal trade-off in infinite data limit, independent of a specific model class. While these works offer valuable theoretical insights, there is no guarantee that these frontiers are attainable by models within a given model class H. We verify this empirically in Appendix F.6 by showing that, for the Adult dataset, the frontiers proposed in [24] 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.Various other regularization approaches [39, 33, 8, 14, 41, 42, 43] have also been proposed, but these often necessitate training multiple models, making them computationally intensive. Alternative strategies include learning 'fair' representations [44, 30, 31] , or re-weighting data based on sensitive attributes [18, 22] . These, however, provide limited control over accuracy-fairness trade-offs.Besides this, post-processing methods [19, 38] enforce fairness after training but can lead to other forms of unfairness such as 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 as [46, 27] involve learning a 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 a base model and subsequently applying a 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 the 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 D cal .Table 1 : Proportion of empirical trade-offs for each baseline in the three trade-off regions, aggregated across all datasets and fairness metrics (using Bernstein's CIs). 'Unlikely', 'Permissible' and 'Suboptimal' correspond to the blue, green and pink regions in Figure 1 In-processing adversary [45] 0.03 ± 0.03 0.51 ± 0.07 0.45 ± 0.07 100 min×40 logsig [8] 0.0 ± 0.0 0.66 ± 0.1 0.33 ± 0.1 100 min×40 reductions [1] 0.0 ± 0.0 0.79 ± 0.1 0.21 ± 0.1 90 min×40 linear [8] 0.01 ± 0.0 0.85 ± 0.05 0.14 ± 0.06 100 min×40 KDE-fair [12] 0.0 ± 0.0 0.97 ± 0.05 0.03 ± 0.06 85 min×40 separate 0.0 ± 0.0 0.98 ± 0.01 0.02 ± 0. To evaluate our methodology, we implement a suite of baseline algorithms including SOTA inprocessing techniques such as regularization-based approaches [8] , a SOTA kernel-density based method [12] (denoted as 'KDE-fair'), as well as the reductions method [1] . Additionally, we also compare against adversarial fairness techniques [45] and a post-processing approach (denoted as 'RTO') [2] and consider the three most prominent fairness metrics: Demographic Parity (DP), Equalized Odds (EO), and Equalized Opportunity (EOP). We provide additional details and results in Appendix F, where we also consider a synthetic setup with tractable τ * fair . The code to reproduce our experiments is provided at github.com/faaizT/DatasetFairness.Figure 3 shows the results for different datasets and fairness violations, obtained using a 10% data split as calibration dataset D cal . For each dataset, we construct 4 CIs that serve as 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, 2) Bernstein'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 accuracy-fairness trade-offs can vary significantly across the datasets. For example, achieving nearperfect fairness (i.e. Φ fair (h) ≈ 0) seems significantly easier for the Jigsaw dataset than the COMPAS dataset, even as 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 a uniform fairness threshold across datasets [as in 1] 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 -α, thereby enabling practitioners to effectively distinguish between genuine sub-optimalities and those due to finite-sample errors. Table 1 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-offs 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, it must be unlikely for any baseline to achieve a trade-off below the lower CIs. Table 1 confirms this empirically, as the proportion of models which lie below the lower CIs is negligible. In Appendix E, we also account for the uncertainty in baseline trade-offs when assessing the optimality, hence yielding more robust inferences. The results remain similar to those in Table 1 .Takeaway 3: YOTO trade-offs 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 1 ). 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-offs which have a high variance as accuracy increases (see Jigsaw results in Figure 3 , for example). This behaviour starkly contrasts the smooth variations exhibited by our YOTO-generated trade-off curves along the accuracy axis.Takeaway 4: Sensitivity analysis does not cause unnecessary conservatism. We use 2 randomly chosen separately trained models to perform our sensitivity analysis for Figure 3 . We find that 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-offs 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 C. 
discussion and limitations: 
 In this work, we propose a computationally efficient approach to capture the accuracy-fairness tradeoffs 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 accuracy-fairness trade-off, leveraging the computational benefits of the You-Only-Train-Once (YOTO) framework [15] . This empowers practitioners with the ability to, at 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-fairness trade-offs tailored to individual datasets.Limitations Despite the evident merits of our approach, it 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 CIs incorporate an unknown term ∆(h λ ). 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 ∆(h λ ) under weaker conditions is a promising avenue for future investigations.A.1 Confidence intervals on τ * fair Proof of Lemma 3.1. This lemma is a straightforward application of Heoffding's inequality.Proof of Proposition 3.2. Here, we prove the result for general classifiers h ∈ H. Let L h acc , U h fair be the lower and upper CIs for acc(h) and Φ fair (h) respectively,P(acc(h) ≥ L h acc ) ≥ 1 -α/2 and P(Φ fair (h) ≤ U h fair ) ≥ 1 -α/2.Then, using a straightforward application union bounds, we get thatP(acc(h) ≥ L h acc , Φ fair (h) ≤ U h fair ) ≥ 1 -P(acc(h) < L h acc ) -P(Φ fair (h) > U h fair ) ≥ 1 -α/2 -α/2 = 1 -α.Using the definition of the optimal fairness-accuracy trade-off τ * fair , we get that the eventacc(h) ≥ L h acc , Φ fair (h) ≤ U h fair implies,      min{Φ fair (h ′ ) | h ′ ∈ H, acc(h ′ ) ≥ L h acc } τ * fair (L h acc ) ≤ U h fair     .From this, it follows thatP(τ * fair (L h acc ) ≤ U h fair ) ≥ P(acc(h) ≥ L h acc , Φ fair (h) ≤ U h fair ) ≥ 1 -α.Proof of Proposition 3.3. We prove the result for general classifiers h ∈ H. Let U h acc , L h fair be the upper and lower CIs for acc(h) and Φ fair (h) respectively, P(acc(h) ≤ U h acc ) ≥ 1 -α/2 and P(Φ fair (h) ≥ L h fair ) ≥ 1 -α/2. Then, using an application of union bounds, we get thatP(acc(h) ≤ U h acc , Φ fair (h) ≥ L h fair ) ≥ 1 -P(acc(h) > U h acc ) -P(Φ fair (h) < L h fair ) ≥ 1 -α/2 -α/2 = 1 -α.Then, using the fact that ∆(h) = Φ fair (h) -τ * fair (acc(h)), we get that1 -α ≤ P(acc(h) ≤ U h acc , Φ fair (h) ≥ L h fair ) = P(acc(h) ≤ U h acc , τ * fair (acc(h)) + ∆(h) ≥ L h fair ) ≤ P(acc(h) ≤ U h acc , τ * fair (U h acc ) + ∆(h) ≥ L h fair ) ≤ P(τ * fair (U h acc ) ≥ L h fair -∆(h)), where in the second last inequality above, we use the fact that τ * fair : [0, 1] → [0, 1] is a monotonically increasing function.In this Section, we provide the formal statement for Theorem 3.4 along with the assumptions required for this result. ≤ 1/2 such that R |Dtr| (H) ≤ C |D tr | -γ .It is worth noting that Assumption A.2, which was also used in [1, Theorem 2] , holds for many classifier families with γ = 1/2, including norm-bounded linear functions, neural networks and classifier families with bounded VC dimension [21, 6] . |D tr | + 2 log (8/η) 2 |D tr | .Next, we defineh * := arg min h∈H Φ fair (h) subject to acc(h) ≥ acc(h) + ϵ.Then, we have that∆(h) =Φ fair (h) -τ * fair (acc(h)) =Φ fair (h) -τ * fair (acc(h) + ϵ) + τ * fair (acc(h) + ϵ) -τ * fair (acc(h)) =Φ fair (h) -Φ fair (h * ) + τ * fair (acc(h) + ϵ) -τ * fair (acc(h)). We know using Assumption A.1 that τ * fair (acc(h) + ϵ) -τ * fair (acc(h)) ≤ L ϵ Moreover, Φ fair (h) -Φ fair (h * ) = Φ fair (h) -Φ fair (h * ) + Φ fair (h) -Φ fair (h) + Φ fair (h * ) -Φ fair (h * ) ≤ Φ fair (h) -Φ fair (h * ) + 2 max h ′ ∈H |Φ fair (h ′ ) -Φ fair (h ′ )|.Putting the two together, we get thatEQUATIONNext, we consider the term Φ fair (h) -Φ fair (h * ). First, we observe thatacc(h * ) ≥ acc(h) + ϵ ≥ acc(h) -| acc(h) -acc(h)| + ϵ ≥ δ + ϵ -| acc(h) -acc(h)|.Next, using [1, Lemma 4] with g(X, A, Y ) = 1(h(X) = Y ), we get that with probability at least1 -η/4, we have that |acc(h) -acc(h)| ≤ 2 R |Dtr| (H) + 2 |D tr | + log (8/η) 2 |D tr | = ϵ/2.This implies that with probability at least 1 -η/4,acc(h * ) ≥ δ + ϵ/2,and hence,δ + ϵ/2 ≤ acc(h * ) ≤ acc(h * ) + |acc(h * ) -acc(h * )|.Again, using [1, Lemma 4] with g(X, A, Y ) = 1(h * (X) = Y ), we get that with probability at least 1 -η/4, we have that|acc(h * ) -acc(h * )| ≤ 2 R |Dtr| (H) + 2 |D tr | + log (8/η) 2 |D tr | = ϵ/2.Finally, putting this together using union bounds, we get that with probability at least1 -η/2, δ + ϵ/2 ≤ acc(h * ) ≤ acc(h * ) + |acc(h * ) -acc(h * )| ≤ acc(h * ) + ϵ/2,and hence, acc(h * ) ≥ δ.Using the definition of h, we have that acc(h * ) ≥ δ =⇒ Φ fair (h) ≤ Φ fair (h * ). Therefore, with probability at least 1 -η/2,EQUATIONNext, to bound the term |Φ fair (h) -Φ fair (h)| above, we consider a general formulation for the fairness violation Φ fair , also presented in [1] ,Φ fair (h) = |Φ ± fair (h)| where, Φ ± fair (h) := m j=1 E[g j (X, A, Y, h(X)) | E j ] =:Φjwhere m ≥ 1, g j are some known functions and E j are events with positive probability defined with respect to (X, A, Y ).Using this, we note that for anyh ′ ∈ H |Φ fair (h ′ ) -Φ fair (h ′ )| = |Φ ± fair (h ′ )| -| Φ ± fair (h ′ )| ≤|Φ ± fair (h ′ ) -Φ ± fair (h ′ )| = m j=1 E[g j (X, A, Y, h ′ (X)) | E j ] -E[g j (X, A, Y, h ′ (X)) | E j ] ≤ m j=1 |E[g j (X, A, Y, h ′ (X)) | E j ] -E[g j (X, A, Y, h ′ (X)) | E j ]|.Let p * j := P(E j ). Then, from [1, Lemma 6], we have that if |D tr | p * j ≥ 8 log (4 m/η), then with probability at least 1 -η/2m, we have that|E[g j (X, A, Y, h ′ (X)) | E j ] -E[g j (X, A, Y, h ′ (X)) | E j ]| ≤2 R |Dtr| p * j /2 (H) + 2 2 |D tr | p * j + log (8 m/η) |D tr | p * j = O(|D tr | -γ ).A straightforward application of the union bounds yields that if |D tr | p * j ≥ 8 log (4 m/η) for all j ∈ {1, . . . , m}, then with probability at least 1 -η/2, we have thatm j=1 |E[g j (X, A, Y, h ′ (X)) | E j ] -E[g j (X, A, Y, h ′ (X)) | E j ]| ≤ O(|D tr | -γ ).Therefore, in this case for any h ′ ∈ H, we have that with probability at least 1 -η/2,|Φ fair (h ′ ) -Φ fair (h ′ )| ≤ O(|D tr | -γ ),and therefore,EQUATIONFinally, putting Eq. ( 5), Eq. ( 6) and Eq. ( 7) together using union bounds, we get that with probability at least 1 -η, we have that∆(h) ≤ Φ fair (h) -Φ fair (h * ) + 2 max h ′ ∈H |Φ fair (h ′ ) -Φ fair (h ′ )| + Lϵ ≤ O(|D tr | -γ ).B Constructing the confidence intervals on Φ fair (h)In this section, we outline methodologies of obtaining confidence intervals for a fairness violation Φ fair . Specifically, given a model h ∈ H, with h : X → Y and α ∈ (0, 1), we outline how to find C α fair which satisfies,EQUATIONSimilar to [1] we express the fairness violation Φ fair as:Φ fair (h) = |Φ ± fair (h)| where, Φ ± fair (h) := m j=1 E[g j (X, A, Y, h(X)) | E j ] =:Φjwhere m ≥ 1, g j are some known functions and E j are events with positive probability defined with respect to (X, A, Y ). For example, when considering the demographic parity (DP), i.e.Φ fair = Φ DP , we have m = 2, with g 1 (X, A, Y, h(X)) = h(X), E 1 = {A = 1}, g 2 (X, A, Y, h(X)) = -h(X)and E 2 = {A = 0}. Moreover, as shown in [1] , 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 Φ fair (h) involves first constructing intervals C α,± fair on Φ ± fair (h) satisfying:EQUATIONOnce we have a C α,± fair , the confidence interval C α fair satisfying Eq. ( 8) can simply be constructed as:C α fair = {|x| : x ∈ C α,± fair }.In what follows, we outline two different ways of constructing the confidence intervals C α,± fair on Φ ± fair (h) satisfying Eq. ( 9).One way to obtain intervals on Φ ± fair (h) would be to separately construct confidence intervals on Φ j , denoted by C α j , which satisfies the joint guaranteeEQUATION)Given such set of confidence intervals {C α j } m j=1 which satisfy Eqn. Eq. ( 10), we can obtain the confidence intervals on Φ ± fair (h) by using the fact thatP Φ ± fair (h) ∈ m i=1 C α j ≥ 1 -α.Where, the notationm i=1 C α j denotes the set { m i=1 x i : x i ∈ C α i }.One naïve way to obtain such {C α j } m j=1 which satisfy Eq. ( 10) is to use the union bounds, i.e., if C α j are chosen such thatP(Φ j ∈ C α j ) ≥ 1 -α/m, then, we have that P ∩ m j=1 {Φ j ∈ C α j } = 1 -P(∪ m j=1 {Φ j ∈ C α j } c ) ≥ 1 - m i=1 P({Φ j ∈ C α j } c ) ≥ 1 - m i=1 (1 -(1 -α/m)) = 1 -α.Here, for an event E, we use E c to denote the complement of the event. This methodology therefore reduces the problem of finding confidence intervals on Φ ± fair (h) to finding confidence intervals on Φ j for j ∈ {1, . . . , m}. Now note that Φ j are all expectations and we can use standard methodologies to construct confidence intervals on an expectation. We explicitly outline how to do this in Section B.3.Remark The methodology outlined above provides confidence intervals with valid finite sample coverage guarantees. However, this may come at the cost of more conservative confidence intervals. One way to obtain less conservative confidence intervals while retaining the coverage guarantees would be to consider alternative ways of obtaining confidence intervals which do not require constructing the CIs separately on Φ j . We outline one such methodology in the next section.B.2 Using subsampling to construct the CIs on Φ ± fair directlyHere, we outline how we can avoid having to use union bounds when constructing the confidence intervals on Φ ± fair . Let D j denote the subset of data D cal , for which the event E j is true. In the case where the events E j are all mutually exclusive and hence D j are all disjoint subsets of data (which is true for DP, EO and EOP), we can also construct these intervals by randomly sampling without replacement datapoints (xEQUATIONi , y(j) i , h(x (j) i ))is an unbiased estimator of Φ ± fair (h). Moreover, since D j are all disjoint datasets, the datapoints (xEQUATIONi ) are all independent across different values of j, and therefore, m j=1 g j (xEQUATIONi , yi , h(x(j) i ))and ϕ i are all i.i.d. samples and unbiased estimators of Φ ± fair (h). Therefore, like in the previous section, our problem reduces to constructing CIs on an expectation term (i.e. Φ ± fair (h)), using i.i.d. unbiased samples (i.e. ϕ i ) and we can use standard methodologies to construct these intervals.Benefit of this methodology This methodology no longer requires us to separately construct confidence intervals over Φ j and combine them using union bounds (for example). Therefore, intervals obtained using this methodology may be less conservative than those obtained by separately constructing confidence intervals over Φ j .Limitation of this methodology For each subset of data D j , we can use at most l := min k≤m |D k | data points to construct the confidence intervals. Therefore, in cases where l is very small, we may end up discarding a big proportion of the calibration data which could in turn lead to loose intervals.Here, we outline some standard techniques used to construct CIs on the expectation of a random variable. These techniques can then be used to construct CIs on Φ fair (h) (using either of the two methodologies outlined above) as well as on acc(h). In this section, we restrict ourselves to constructing upper CIs. Lower CIs can be constructed analogously.Given dataset {Z i : 1 ≤ i ≤ n}, our goal in this section is to construct upper CIs on E[Z] which satisfiesP(E[Z] ≤ U α ) ≥ 1 -α.Hoeffding's inequality We can use Hoeffding's inequality to construct these intervals U α as formalised in the following result: Lemma B.1 (Hoeffding's inequality).Let Z i ∈ [0, 1], 1 ≤ i ≤ n be i.i.d. samples with mean E[Z]. Then, P E[Z] ≤ 1 n n i=1 Z i + 1 2 n log 1 α ≥ 1 -α.Bernstein's inequality Bernstein's inequality provides a powerful tool for bounding the tail probabilities of the sum of independent, bounded random variables. Specifically, for a sumn i=1 Z i comprised of n independent random variables Z i with Z i ∈ [0, B], each with a maximum variance of σ 2 , and for any t > 0, the inequality states thatP E n i=1 Z i - n i=1 Z i > t ≤ exp - t 2 2σ 2 + 2 3 tB, where B denotes an upper bound on the absolute value of each random variable. Re-arranging the above, we get thatP E[Z] < 1 n n i=1 Z i + t ≥ 1 -exp - t 2 2σ 2 + 2 3 tB.Central Limit Theorem The Central Limit Theorem (CLT) [26] serves as a cornerstone in 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 a 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 Z 1 , Z 2 , . . . , Z n as n independent and identically distributed (i.i.d.) random variables with mean µ and variance σ 2 , the sample mean Z approximates a normal distribution with mean µ and variance σ 2 /n for large n. An upper (1 -α) confidence interval for µ is thus:U α = Z + z α/2 σ √ nwhere z α/2 represents the critical value from the standard normal distribution corresponding to a cumulative probability of 1 -α.Bootstrap Confidence Intervals Bootstrapping, introduced by [17] , offers a non-parametric approach to estimate the sampling distribution of a 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 a dataset Z 1 , Z 2 , . . . , Z n , 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) is determined, yielding B bootstrap estimates. An upper (1 -α) bootstrap confidence interval for E[Z] is given by:U α = Z + (z * α -Z) with z *α denoting the α-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 as a general illustration.Recall from Proposition 3.3 that the lower confidence intervals for τ * fair include a ∆(h) term which is defined as ∆(h) := Φ fair (h) -τ * fair (acc(h)) ≥ 0. In other words, ∆(h) quantifies how 'far' the fairness loss of classifier h (i.e. Φ fair (h)) is from the minimum attainable fairness loss for classifiers with accuracy acc(h), (i.e. τ * fair (acc(h))). This quantity is unknown in general and therefore, a practical strategy of obtaining lower confidence intervals on τ * fair (ψ) may involve positing values for ∆(h) which encode our belief on how close the fairness loss Φ fair (h) is to τ * fair (acc(h)). For example, when we assume that the classifier h achieves the optimal accuracy-fairness tradeoff, i.e. Φ fair (h) = τ * fair (acc(h)) then ∆(h) = 0. However, the assumption Φ fair (h) = τ * fair (acc(h)) may not hold in general because we only have a 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 a surrogate loss which approximates the solution to the constrained minimisation problem in Eq. ( 1). This means that optimising this regularised loss is not guaranteed to yield the optimal classifier which achieves the optimal fairness τ * fair (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 h θ : X × Λ → R be the YOTO model. Our strategy for sensitivity analysis involves training multiple standard models M := {h (1) , h (2) , . . . , h (k) } ⊆ H by optimising the regularised losses for few different choices of λ.L λ (θ) = E[l CE (h θ (X), Y )] + λ L fair (h θ ).Importantly, we do not 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 * λ ∈ M ∪ {h θ (•, λ)} be such thatEQUATIONHere, Φ fair and acc denote the finite sample estimates of the fairness loss and model accuracy respectively. We treat the model h * λ as a model which attains the optimum trade-off when estimating subject to the constraint acc(h) ≥ acc(h θ (•, λ)). Specifically, we use the maximum empirical error max λ ∆(h θ (•, λ)) as a plausible surrogate value for ∆(h θ (•, λ ′ )), where∆(h θ (•, λ)) := Φ fair (h θ (•, λ)) -Φ fair (h * λ ) ≥ 0 , i.e., we posit for any λ ′ ∈ Λ ∆(h θ (•, λ ′ )) ← max λ∈Λ ∆(h θ (•, λ)) where, ∆(h θ (•, λ)) := Φ fair (h θ (•, λ)) -Φ fair (h * λ ).Next, we can use this posited value of ∆(h θ (•, λ ′ )) to construct the lower confidence interval using the following corollary of Proposition 3.3:Corollary C.1. Consider the YOTO model h θ : X × Λ → R. Given λ 0 ∈ Λ, let U h acc , L h fair ∈ [0, 1] be such that P(acc(h θ (•, λ 0 )) ≤ U h acc ) ≥ 1 -α/2 and P(Φ fair (h θ (•, λ 0 )) ≥ L h fair ) ≥ 1 -α/2.Then, we have thatP(τ * fair (U h acc ) ≥ L h fair -∆(h θ (•, λ 0 ))) ≥ 1 -α.This result shows that if the goal is to construct lower confidence intervals on τ * fair (ψ) and we obtain that ψ ≥ U h acc , then using the monotonicity of τ * fair we have that τ * fair (ψ) ≥ τ * fair (U h acc ). Therefore the interval [L h fair -∆(h θ (•, λ 0 ))), 1] serves as a lower confidence interval for τ * fair (ψ). When YOTO satisfies Pareto optimality, ∆(h θ (•, λ)) → 0 as |D cal | → ∞: Here, we show that in the case when YOTO achieves the optimal trade-off, then our sensitivity analysis leads to ∆(h θ (•, λ)) = 0 as the calibration data size increases for all λ ∈ Λ. Our arguments in 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).If for some λ ∈ Λ and h ′ ∈ H we have that, acc(h′ ) ≥ acc(h θ (•, λ)) then, Φ fair (h ′ ) ≥ Φ fair (h θ (•, λ)),In the case when YOTO satisfies this optimality property, then it is straightforward to see that ∆(h θ (•, λ)) = 0 for all λ ∈ Λ. In this case, as D cal → ∞, we get that Eq. ( 11) roughly becomesh * λ = arg min h ′ ∈M∪{h θ (•,λ)} Φ fair (h ′ ) subject to acc(h ′ ) ≥ acc(h θ (•, λ)).Here, Assumption C.2 implies that h * λ = h θ (•, λ), and therefore 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-fairness 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 λ, then the sensitivity analysis adjusts the empirical trade-off obtained using YOTO models (using the ∆(h θ (•, λ)) term defined above). If, on the other hand, we find that the YOTO model achieves a better trade-off than the separately trained models in M, then the sensitivity analysis has no effect on the lower confidence intervals as in this case ∆(h θ (•, λ)) = 0.∆(h θ (•, λ)) := Φ fair (h θ (•, λ)) -Φ fair (h * λ ) = 0.Here, we include empirical results showing how the CIs constructed change as a result of our sensitivity analysis procedure. In Figures 4 and 5 , 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 ∆(h λ ) = 0) do not cover the empirical trade-offs for the separately trained models. However, the figures show that the sensitivity analysis procedure adjusts the lower CIs in both cases so that they encapsulate the empirical trade-offs that were not captured without sensitivity analysis.Suppose that we additionally have access to a predictive model f A which predicts the sensitive attributes A using the features X. In this case, another simple strategy would be to simply impute the missing values of A, with the values Â predicted using f A . However, this will usually lead to a biased estimate of the fairness violation Φ fair (h), and hence is not very reliable unless the model f A is 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 τ * fair (ψ). Formally, we consider D cal = D ∪ D 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 ≫ n. Additionally, for both datasets, we have predictions of the sensitive attributes made by a machine-learning algorithm f A : X → A, where f A (X) ≈ A.D = {(X i , A i , Y i , f A (X i ))} n i=1 and D = {( Xi , Ỹi , f A ( Xi ))} N i=1High-level methodology Our methodology is inspired by prediction-powered inference [4] which builds confidence intervals on the expected outcome E[Y ] using data for which the true outcome Y is only available for a small proportion of the dataset. In our setting, however, it is the sensitive attribute A that is missing for the majority of the data (and not the outcome Y ).For h ∈ H, let Φ fair (h) be a fairness violation (such as DP or EO), and let Φ fair (h) be the corresponding fairness violation computed on the data distribution where A is replaced by the surrogate sensitive attribute f A (X). For example, in the case of DP violation, Φ fair (h) and Φ fair (h) denote:Φ fair (h) = |P(h(X) = 1 | A = 1) -P(h(X) = 1 | A = 0)|, Φ fair (h) = |P(h(X) = 1 | f A (X) = 1) -P(h(X) = 1 | f A (X) = 0)|.We next construct the confidence intervals on Φ fair (h) using the following steps:1. Using D, we construct intervals C ϵ (α; h) on ϵ(h) := Φ fair (h) -Φ fair (h) satisfyingEQUATIONEven though the size of D is small, we choose a methodology which yields tight intervals for ϵ(h) when f A (X i ) = A i with a high probability.2. Next, using the dataset D, we construct intervals Cf (α; h) on Φ fair (h) satisfyingEQUATIONThis interval will also be tight as the size of D, N ≫ n.Finally, using the union bound idea we combine the two confidence intervals to obtain the confidence interval for Φ fair (h) -Φ fair (h) + Φ fair (h) = Φ fair (h). We make this precise in the following result:Lemma D.1. Let C ϵ (α; h), Cf (α; h) be as defined in equations 12 and 13. Then, if we defineC α fair (h) = {x + y | x ∈ C ϵ (α; h), y ∈ Cf (α; h)}, we have that P(Φ fair (h) ∈ C α fair (h)) ≥ 1 -2α.When constructing the CIs over Φ fair (h) using imputed sensitive attributes f A (X) in step 2 above, the prediction error of f A introduces an error in the obtained CIs (denoted by ϵ(h)).Step 1 rectifies this by constructing a CI over the incurred error ϵ(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 to the case where the fairness loss under consideration is DP. As described above, the first step involves constructing intervals on ϵ(h) := Φ fair (h) -Φ fair (h) using a methodology which yields tight intervals when f A (X i ) = A i with a high probability. To this end, we use bootstrapping as described in Algorithm 1.Even though bootstrapping does not provide us with finite sample coverage guarantees, it is asymptotically exact and satisfies the property that the confidence intervals are tight when Â = A with a high probability. On the other hand, concentration inequalities (such as Hoeffding's inequality) seek to construct confidence intervals individually on Φ fair (h) and Φ fair (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 Φ fair (h) and Φ fair (h) might be in the data.To make this concrete, consider the example where f A (X) a.s.= A and hence Φ fair (h) = Φ fair (h). When using concentration inequalities to construct the 1 -α confidence intervals on Φ fair (h) and Φ fair (h), we obtain identical intervals for the two quantities, say [l, u]. Then, using union bounds we obtain that Φ fair (h) -Φ fair (h) ∈ [l -u, u -l] with probability at least 1 -2α. In this case even though Φ fair (h) -Φ fair (h) = 0, the width of the interval [l -u, u -l] does not depend on the closeness of Φ fair (h) and Φ fair (h) and therefore is not tight. Bootstrapping helps us circumvent this problem, since in this case for each resample of the data D, the finite sample estimates Φ fair (h) and Φ fair (h) will be equal. We outline the bootstrapping algorithm below. Using Algorithm 1 we construct a confidence interval C ϵ (α; h) on ϵ(h) of size 1 -α, which approximately satisfies Eq. ( 12). Next, using standard techniques we can obtain an interval Cf (α; h) on Φ fair (h) using D which satisfies Eq. (13) . Like before, the interval Cf (α; 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.1, we obtain the confidence interval on Φ fair (h).Here, we present experimental results in the setting where the sensitive attributes are missing for majority of the calibration data. Figures 7 8 9 10 11 12 show the results for different datasets and predictive models f A 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, 9 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 f A (X) ≈ A. The figures show that when the accuracy of f A is below 90%, the CIs 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 8, 10 and 12 which include the corresponding results using our methodology, show that our methodology is able to correct for the mis-calibration in CIs arising from the prediction error in f A . Even though the CIs obtained using our methodology are more conservative than those obtained by imputing the missing sensitive attributes with f A (X), they are more well-calibrated and contain the empirical trade-offs for both YOTO and separately trained model. accuracy of f A increases to 90%. In this case, the CIs with imputed sensitive attributes mostly contain empirical trade-offs. This shows that in cases where the predictive model f A has high accuracy, it may be sufficient to impute missing sensitive attributes with f A (X) when constructing the CIs.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 our confidence intervals constructed P(τ * fair (Ψ) ∈ Γ α fair ) ≥ 1 -α.This means that if the accuracy-fairness tradeoff for a given model h ′ ∈ H, (acc(h ′ ), Φ fair (h ′ )), lies above the confidence intervals Γ α fair (i.e. in the pink region in Figure 13 ), then we can confidently infer that the model h ′ achieves a suboptimal trade-off. This is because we know from the probabilistic guarantee above that the optimal trade-off (acc(h ′ ), τ * fair (acc(h ′ ))) must lie in the intervals Γ α fair with probability at least 1 -α.Here, acc(h ′ ), Φ fair (h ′ ) denote the accuracy and fairness violations for model h ′ on the full data distribution. However, in practice, we only have access to finite data and therefore can only compute the empirical values of accuracy and fairness violations which we denote by acc(h ′ ), Φ fair (h ′ ). This means that when checking if the accuracy-fairness trade-off (acc(h ′ ), Φ fair (h ′ )) lies inside the confidence intervals Γ α fair , we must account for the uncertainty in the empirical estimates acc(h ′ ), Φ fair (h ′ ). This can be achieved by constructing confidence regions C α (h ′ ) satisfyingEQUATION)Baseline's best-case accuracy-fairness trade-off If the confidence region C α (h ′ ) lies entirely above the confidence intervals Γ α fair (i.e. in the pink region in Figure 13a ), then using union bounds we can confidently conclude that with probability 1 -2α we have that the model h ′ achieves suboptimal fairness violation, i.e.Φ fair (h ′ ) ≥ τ * fair (acc(h ′ )). This allows practitioners to confidently check if a model h ′ is suboptimal in terms of its accuracyfairness trade-off. This is different from simply checking if the empirical trade-off achieved by the model ( acc(h ′ ), Φ fair (h ′ )) lies in the permissible trade-off region (green region in Figure 1 ) as it also accounts for the finite-sampling uncertainty in the tradeoff achieved by model h ′ . However, this means that the criterion for flagging a baseline model h ′ as suboptimal becomes more conservative.Next, we show how to construct confidence regions C α (h ′ ) satisfying Eq. ( 14). Lemma E.1. For a classifier h ′ ∈ H, let U h acc , L h fair be the upper and lower CIs on acc(h ′ ), Φ fair (h ′ ) respectively, P(acc(h ′ ) ≤ U h acc ) ≥ 1 -α/2, and P(Φ fair (h ′ ) ≥ L h fair ) ≥ 1 -α/2.Lemma E.2 shows that C α (h ′ ) = [L h acc , 1] × [0, U h fair ]forms the 1 -α confidence region for the accuracy-fairness trade-off (acc(h ′ ), Φ fair (h ′ )). If 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-fairness trade-off than the YOTO model. From Figure 13b it can be seen that this will occur if (L h acc , U h fair ) lies below the permissible region. Intuitively, (L h acc , U h fair ) 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 τ YOTO is still worse than the worst-case trade-off achieved by the model h ′ , leading us to the confident conclusion that h ′ achieves a better accuracy-fairness trade-off than the YOTO model. This can subsequently be used to calibrate the suboptimality gap for the YOTO model, denoted by ∆(h λ ) in Proposition 3.3.Here, we present the results with the empirical baseline trade-offs replaced by best or worst-case trade-offs as appropriate. More specifically, in Figure 14,  • if the empirical trade-off for a baseline ( acc(h ′ ), Φ fair (h ′ )) lies in the suboptimal region (as in Figure 13a ), then we plot the best-case trade-off (U h acc , L h fair ) for the baseline,• if the empirical trade-off for a baseline ( acc(h ′ ), Φ fair (h ′ )) lies in the unlikely-to-beachievable trade-off region (as in Figure 13b ), then we plot the worst-case trade-off (L h acc , U h fair ) for the baseline,• if the empirical trade-off for a baseline ( acc(h ′ ), Φ fair (h ′ )) lies in the permissible region, then we simply plot the empirical trade-off ( acc(h ′ ), Φ fair (h ′ )).Therefore, in Figure 14 if a baseline's best-case trade-off lies above the permissible trade-off region, then we can confidently conclude that the baseline achieves suboptimal accuracy-fairness tradeoff with probability 1 -2α = 90%. Similarly, a baseline's worst-case trade-off lying below the permissible trade-off region would suggest that the YOTO trade-off achieves a suboptimal trade-off and that the value of ∆(h θ ) needs to be adjusted accordingly.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-offs 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 τ * fair 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. 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) = P(h(X) = 1 | Y = y)for any a ∈ A and y ∈ {0, 1}. The absolute EO violation is defined as:Φ EO (h) :=1/2 |P(h(X) = 1 | A = 1, Y = 1) -P(h(X) = 1 | A = 0, Y = 1)| + 1/2 |P(h(X) = 1 | A = 1, Y = 0) -P(h(X) = 1 | A = 0, Y = 0)|.Next, we provide additional details regarding the YOTO model.As described in Section 3, we consider optimising regularized losses of the formL λ (θ) = E[l CE (h θ (X), Y )] + λ L fair (h θ ).When training YOTO models, instead of fixing λ, we sample the parameter λ from a distribution P λ . As a result, during training the model observes many different values of λ and learns to optimise the loss L λ for all of them simultaneously. At inference time, the model can be conditioned on a chosen parameter value λ ′ and recovers the model trained to optimise L λ ′ . The loss being minimised can thus be expressed as follows:arg minh θ :X ×Λ→R E λ∼P λ [E[l CE (h θ (X, λ), Y )] + λ L fair (h θ (•, λ))] .The fairness losses L fair considered for the YOTO model are:DP: L fair (h θ (•, λ)) = |E[σ(h θ (X, λ)) | A = 1] -E[σ(h θ (X, λ)) | A = 0]| EOP: L fair (h θ (•, λ)) = |E[σ(h θ (X, λ)) | A = 1, Y = 1] -E[σ(h θ (X, λ)) | A = 0, Y = 1]| EO: L fair (h θ (•, λ)) = |E[σ(h θ (X, λ)) | A = 1, Y = 1] -E[σ(h θ (X, λ)) | A = 0, Y = 1]| + |E[σ(h θ (X, λ)) | A = 1, Y = 0] -E[σ(h θ (X, λ)) | A = 0, Y = 0]|.Here, σ(x) := 1/(1 + e -x ) denotes the sigmoid function.In our experiments, we sample a new λ for every batch. Moreover, we use the log-uniform distribution as per [15] as the sampling distribution P λ , where the uniform distribution is U [10 -6 , 10]. To condition the network on λ parameters, we follow in the footsteps of [15] to use Feature-wise Linear Modulation (FiLM) [34] . For completeness, we include the description of the architecture next.Initially, we determine which network layers should be conditioned, which can encompass all layers or just a subset. For each chosen layer, we condition it based on the weight parameters λ. Given a layer that yields a feature map f with dimensions W × H × 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 as M σ and M µ . These MLPs produce two vectors, σ and µ, each having a dimensionality of C. The feature map is then transformed by multiplying it channel-wise with σ and subsequently adding µ. The resultant transformed feature map f ′ is given by:f ′ ijk = σ k f ijk + µ k where σ = M σ (λ) and µ = M µ (λ). Next, we provide exact architectures we used for each dataset in our experiments.Adult and COMPAS dataset Here, we use a simple logistic regression as the main model, with only the scalar logit outputs of the logistic regression being conditioned using FiLM. The MLPs M µ , 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 models takes roughly 5 minutes on a Tesla-V100-SXM2-32GB GPU.CelebA dataset For the CelebA dataset, our architecture is a 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 a kernel size of 3 × 3, and the second layer has 64 filters, also with a 3 × 3 kernel. Both convolutional layers employ a stride of 1 and are followed by a 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-layer 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 σ, 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-V100-SXM2-32GB GPU.Jigsaw dataset For the Jigsaw dataset, we employ a 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 λ parameter to modulation parameters γ and β, 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 a linear layer mapping from BERT's hidden size (768) to a scalar output. In terms of training details, our model is trained for a maximum of 10 epochs, with early stopping based on validation losses. Training this model takes roughly 6 hours on a Tesla-V100-SXM2-32GB GPU.We used four real-world datasets for our experiments.The Adult income dataset [7] includes employment data for 48,842 individuals where the task is to predict whether an individual earns more than $50k per year and includes demographic attributes such as age, race and gender. In our experiments, we consider gender as the sensitive attribute.The COMPAS recidivism data comprises collected by ProPublica [5] , 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 is 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 [20] contains online comments from various platforms, aimed at identifying and mitigating toxic behavior online. The task is to predict whether a given comment is toxic or 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.The baselines considered in our experiments include:• Regularization based approaches [8] : These methods seek to minimise fairness loss using regularized losses as shown in Section 3. We consider different regularization terms L fair (h θ ) as smooth relaxations of the fairness violation Φ fair as proposed in the literature [8] . To make this concrete, when the fairness violation under consideration is DP, we considerL fair (h θ ) = E[g(h θ (X)) | A = 1] -E[g(h θ (X)) | A = 0],with g(x) = x denoted as 'linear' in our results and g(x) = log σ(x) where σ(x) := 1/(1 + e -x ), denoted as '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.e., DP:L fair (h θ ) = |E[σ(h θ (X)) | A = 1] -E[σ(h θ (X)) | A = 0]| EOP: L fair (h θ ) = |E[σ(h θ (X)) | A = 1, Y = 1] -E[σ(h θ (X)) | A = 0, Y = 1]| EO: L fair (h θ ) = |E[σ(h θ (X)) | A = 1, Y = 1] -E[σ(h θ (X)) | A = 0, Y = 1]| + |E[σ(h θ (X)) | A = 1, Y = 0] -E[σ(h θ (X)) | A = 0, Y = 0]|.Here, σ(x) := 1/(1 + e -x ) 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 a range of λ values uniformly chosen in [0, 10] interval. • Reductions Approach [1] : 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 fairness constraints uniformly in [0, 1]. • KDE-fair [12] : This method employs a kernel density estimation trick to quantify fairness measures, capturing the degree of irrelevancy of prediction outputs to sensitive attributes. These quantified fairness measures are expressed as differentiable functions with respect to classifier model parameters, allowing the use of gradient descent to solve optimization problems that respect fairness constraints. We focus on binary classification and well-known definitions of group fairness: Demographic Parity (DP), Equalized Odds (EO) and Equalized Opportunity (EOP). • Randomized Threshold Optimizer (RTO) [2] : This scalable post-processing algorithm debiases trained models, including deep neural networks, and is proven to be near-optimal by bounding its excess Bayes risk. RTO optimizes the trade-off curve by applying adjustments to the trained model's predictions to meet constraints. In our experiments, we first train a standard classifier which is referred to 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-hoc adjustments to the base classifier for a range of fairness violation constraints.• Adversarial Approaches [45] : 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 h θ (X) generated by the main classifier h θ . 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 to 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 = 1.The training times for each baseline on the different datasets have been listed in Table 6 . In Figures 15-26 we include additional results for all datasets and fairness violations with an increasing number of calibration data D cal . It can be seen that as the number of calibration data increases, the CIs constructed become increasingly tighter. However, the asymptotic, Bernstein and bootstrap CIs are informative even when the calibration data is as little as 500 for COMPAS data (Figures 18 19 20 ) and 1000 for all other datasets. These results show that the larger the calibration data D cal , the tighter the constructed CIs are likely to be. However, even in cases where the calibration dataset is relatively small, we obtain informative CIs in most cases. show the proportion of the baselines which lie in the three trade-off regions, 'Unlikely', 'Permissible' and 'Sub-optimal' for the Bernstein's CIs, across the different datasets and fairness metrics. Overall, it can be seen that our CIs 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 1 For Figure 1 , we consider a calibration data D cal of size 2000. For the optimal model, we trained a YOTO model on the COMPAS dataset with the architecture given in F.1.1. 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 D cal 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. In Figure 27 we include the results for the Adult dataset along with the model-specific (MS) and model-agnostic (MA) FACT Pareto frontiers, obtained using the methodology in [23] . It 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 a specific model class. As a result, there is no guarantee that this Pareto frontier is achievable. This is evident from the fact that the MA FACT yields a non-informative Pareto frontier on the Adult dataset in Figure 27 , which is non-achievable in practice. The model-specific FACT trade-off curve is comparatively more realistic as it is derived using a pre-trained model. However, it is important to 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 in the given model class, as it does not provide any guarantee of 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 a logistic regression classifier as a pre-trained model for obtaining the MS FACT frontier. In real-world settings, the ground truth trade-off curve τ * fair remains intractable because we only have access to a finite dataset. In this section, we consider a synthetic data setting, where the ground truth trade-off curve can be obtained, to verify that the YOTO trade-off curves are consistent with the ground truth and that the confidence intervals obtained using our methodology contain τ * fair . Dataset Here, we consider a setup with X = R, A = {0, 1} and Y = {0, 1}. Specifically, A ∼ Bern(0.5) and we define the conditional distributions X | A = a as: X | A = a ∼ N (a,Y = Z 1(X > 0.5) + (1 -Z) 1(X ≤ 0.5),where Z ∼ Bern(0.9) and Z ⊥ ⊥ 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. Ground truth trade-off curve To obtain the ground truth trade-off curve τ * fair , we consider the family of classifiersh c (X) = 1(X > c)for c ∈ R. Next, we calculate the trade-offs achieved by this model family for a 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 τ * fair .Figure 28 shows the results for the synthetic data setup for three different fairness violations, obtained using a calibration dataset D cal of size 2000. It can be seen that for each fairness violation considered, the YOTO trade-off curve aligns very well with the ground-truth trade-off curve τ * fair . Additionally, we also consider four different confidence intervals obtained using our methodology, and Figure 28 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 CIs). Here D cal is a 10% dataset split. 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 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 1) and Preliminaries (Section 2) discuss the implications of our method for fairness decisions. We contribute to better auditing of model fairness 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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, or 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 no such risks.• Released models that have a 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 to 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 not require this, but we encourage authors to take this into account and make a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: questions: Please see Weakness.
limitations: limitations: The method requires an in-distribution calibration dataset and only applies to in-distribution tests.
paper_summary: paper_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.
strength_weakness: strength_weakness: - Data Dependency: The methodology requires separate datasets for training and calibration, which may not be feasible in situations with limited data.
- 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.
- 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.
questions: 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].
- 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?



[1] Kim, Joon Sik, Jiahao Chen, and Ameet Talwalkar. "FACT: A diagnostic for group fairness trade-offs." International Conference on Machine Learning. PMLR, 2020.

[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: limitations: Please see the questions and weaknesses above.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- Since this work is based on YOTO, YOTO should be introduced in the Preliminary section for better illustration.
- Section 3.1 should also be introduced in the Preliminary section, as it is the basic in-processing framework for fairness.
- 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.
questions: 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: limitations: The authors have adequately addressed the limitations. Since this work is mainly about fairness, I do not see any negative societal impact.

Comments: title: Official Comment by Reviewer 3zFr
comment: Thanks for the detailed response. I am satisfied with the response and will raise my score.
I am satisfied with the authors’ replies, and they have addressed my concerns and questions. After checking the replies the authors provided to other reviewers, I am happy to raise my score.