Dataset Fairness: Achievable Fairness On Your Data With Utility Guarantees

We thank the reviewer for their thoughtful comments on our work. Below we respond to the questions raised.

The method is highly based on an existing method, YOTO. Although it doesn't need to train multiple models, the cost of YOTO is not discussed in this paper.

We describe the computational cost of the YOTO model in extensive detail in Appendix E.1.1. including the computational resources used to train each YOTO model, the time required to train each YOTO model for each dataset, the model architecture for each dataset as well as the training details for the YOTO model. At a high-level, training one YOTO model takes roughly the same amount of time as taken by each of the separately trained models in our experiments. More specifically, on Adult and COMPAS datasets, training one YOTO model on a Tesla-V100-SXM2-32GB GPU takes roughly 5 minutes, whereas on the CelebA dataset training one YOTO model takes roughly 1.5 hours and on the Jigsaw dataset training one YOTO model takes roughly 6 hours.

The accuracy-fairness curve is algorithm-agnostic. Figure 4 shows that the estimated curve has more errors when using some particular algorithmic fairness methods. However, people tend to use some algorithmic fairness methods to train the model. In that case, the practical use of the curve is concerned.

We agree with the reviewer that the accuracy-fairness curve is algorithm-agnostic, and since our intervals are designed to align with the optimal trade-off curve, they should serve as reference for any model belonging to the model class $\mathcal{H}$ regardless of the algorithmic fairness method used to train the model. Note that in practice, any methodology whose trade-off lies above our upper confidence interval is likely to have a suboptimal trade-off, suggesting that alternative approaches may offer improved trade-offs.

What is the L_fair in equation (2)?

We provided all of the smooth relaxations $L_{\text{fair}}$ considered in our work in Appendix E (pages 23 and 25). In our experiments, we considered a number of different fairness relaxations $L_{\text{fair}}$ as considered in previous fairness literature [Bendekgey & Sudderth, 2021]. For example, given a model $h_\theta : \mathcal{X} \rightarrow \mathbb{R}$, the relaxations for demographic parity considered in our baselines are of the form: $L_{\text{fair}}(h_\theta) = |\mathbb{E}[g(h_\theta(X))\mid A = 1] - \mathbb{E}[g(h_\theta(X))\mid A = 0]|$ Where the functions $g:\mathbb{R}\rightarrow \mathbb{R}$ considered in our experiments include $g(x) = x$ (denoted as 'linear' in our results), $g(x)=\log{\sigma(x)}$ where $\sigma(x):= 1/(1+\exp{-x})$ (used for the 'separate' baseline as well as YOTO models) and $g(x)=\log{\sigma(x)}$ (denoted as 'logsig' in our results). We will also include these details in the main text in the updated version of our paper.

We hope our clarifications have addressed the reviewer's concerns, and kindly ask them to consider increasing their score.

[Bendekgey & Sudderth, 2021] Harry Bendekgey and Erik B. Sudderth. Scalable and stable surrogates for flexible classifiers with fairness constraints.

We thank the reviewer for providing comments on our work. Below we address the questions raised and try to clarify some of the misunderstandings:

The statement "For a given dataset, model class, and accuracy, the permissible range of fairness violation is x to y." in this paper is problematic. Accuracy and fairness have an inherent connection (they exhibit trade-offs) and will influence each other. So accuracy cannot be the condition for the range of fairness violation.

We consider model fairness conditional on model accuracy precisely because of the accuracy-fairness trade-off. This is also in line with the fairness-constrained accuracy maximisation formulation provided in the fairness literature [Equation (3) in Agarwal et al, 2018]. Since accuracy and fairness can be at odds with each other and exhibit trade-offs, we should not consider the fairness violation value of a model in isolation. As an example, if we do not constrain the model accuracy, the minimum demographic parity for any given model class $\mathcal{H}$ will be 0 and will be attained by a model which makes a constant prediction regardless of the input. In this case, even though the minimum attainable demographic parity is 0, the model accuracy will likely be very low. Therefore, the goal when obtaining the optimal accuracy-fairness trade-off is to minimise the model fairness violation while constraining the model accuracy. We will further clarify this in the updated version of the paper.

How to evaluate whether the confidence interval is rational or correct? This does not seem to have ground truth for this and only visually evaluating figure 4 is not enough.

Recall that the ground truth trade-off curve is defined as:

$\tau^\ast_{\text{fair}}(\psi) \coloneqq \min_{h\in \mathcal{H}} \Phi_{\text{fair}}(h)$ subject to $\text{acc} \geq \psi$.

For real-world datasets, this ground truth trade-off curve is intractable. This is because, in general, the constrained optimisation problem above is non-trivial to solve exactly. Furthermore, we only have access to a finite dataset making it impossible to obtain the exact trade-off curve in general. As a result of this, previous works in fairness literature only consider empirical accuracy-fairness trade-offs [Agarwal et al., 2018, Bendekgey & Sudderth, 2021, Zafar et al., 2015; 2017; 2019]. In this work, we construct the confidence intervals in an attempt to account for the approximation errors, and since the ground truth trade-offs are unknown, we empirically verify that the state-of-the-art methodologies lead to empirical trade-offs which are largely consistent with the obtained confidence intervals.

Apart from this, we have conducted additional experiments with synthetic data setups where the ground truth is known. The experimental results included in the Appendix E.5 of the updated manuscript show that the empirical trade-off achieved by YOTO aligns very well with the ground truth trade-off curve. Additionally, the ground truth trade-off curve is covered by all the confidence intervals constructed.

There is a strong assumption that the curve learned with YOTO is the ground truth, this is not reasonable and even wrong.

We wish to clarify that our work does not make the assumption that the curve learned with YOTO is the ground truth, and every theoretical result presented in our paper remains valid regardless of whether the YOTO trade-off curve is optimal or not. More specifically, as we mention in Section 3.2.1, the upper confidence intervals on $\tau^\ast_{\text{fair}}$ do not depend on how close the YOTO trade-off curve is to the ground truth optimum curve. In contrast, the lower confidence intervals presented in Proposition 3.4 depend on the gap between the YOTO achieved trade-off curve and the ground-truth trade-off curve (denoted by $\Delta(h)$). While this gap, $\Delta(h)$, is an unknown quantity in general, we propose sensitivity analysis techniques to posit plausible values for $\Delta(h)$ in practice in Appendix C.

This strong but possibly wrong assumption is only mentioned in "In other words, 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." (Page 4). I strongly recommend treating this seriously.

The statement above does not refer to the optimality of the YOTO trade-off. Instead, the statement provides an intuitive, informal explanation of (Dosovitskiy & Djolonga, 2020, Proposition 1) and implies that under large enough model capacity, the trade-off curves obtained using YOTO should align with the trade-off curves obtained by training models separately (which may or may not be the same as optimal ground-truth trade-off curve). We will further clarify this in the updated version of our paper, by possibly including the formal result provided in (Dosovitskiy & Djolonga, 2020, Proposition 1) for completeness.

I thank the authors for their response and am sorry for the late response. The authors' response addresses part of my concerns. But

1. The new explanation that "the lower confidence intervals presented in Proposition 3.4 depend on the gap between the YOTO achieved trade-off curve and the ground-truth trade-off curve" is essentially making a strong assumption that the YOTO should be good enough, although not group truth. I do not think this point is reasonable and grounded.
2. The evaluation based on such small tabular data is not convincing to me, without new results presented.

Based on the above and my original comments, I would maintain my original score.

(I also added the above comments in the original review.)

We would like to thank the reviewer for taking the time to review our work. There seem to be some misunderstandings regarding our methodology which we seek to clarify below.

Motivation. Can the authors elaborate on the motivation for using a universe fairness requirement across datasets? What are the advantages of doing this?

We would like to emphasise that, in this work, we argue against the use of a universal fairness requirement across datasets because the accuracy-fairness trade-off is highly dependent on the characteristics of the dataset. Therefore, previous works such as [Agarwal et al., 2018 ] which use a uniform fairness requirement (such as requiring the Demographic Parity to be $\leq 0.1$ regardless of the dataset) may have varying implications for the achievable model accuracy across the different datasets. Our proposed methodology instead allows practitioners to quantify the complete accuracy-fairness tradeoff curve which may be used to obtain the range of permissible fairness violations at any given level of model accuracy chosen at inference time and does not require imposing any restrictions on model fairness or accuracy apriori at training time. We will further clarify this distinction in the next version of our paper.

Technique novelty. This paper introduces a computationally efficient method for estimating the trade-off. However, from my understanding, the efficiency part directly adopts YOTO framework and the confidence interval estimation only involves trivial bounds.

There are a number of important technically novel aspects regarding both, the construction of confidence intervals and the application of the YOTO framework in our methodology, which we believe will be of interest to the ML fairness community:

1. Firstly, we would like to emphasise that our method of constructing the confidence intervals on the trade-off curve $\tau^\ast_{\text{fair}}$ does not simply rely on trivial bounds. While standard methods like Hoeffding's inequality can be used directly to obtain confidence intervals on model accuracy, the same is not true for fairness violation metrics like Demographic Parity, Equalised Odds and Equalized Opportunity which involve multiple (conditional) expectation terms. While a naive application of union bounds can be used to construct confidence intervals on these fairness violation metrics, these bounds are known to be highly conservative and are often non-informative. Therefore, in order to construct informative confidence intervals on fairness violations, we propose a subsampling procedure in Appendix B.2 which provides a novel methodology of constructing valid confidence intervals on fairness violation metrics by subsampling calibration data. We will include a discussion of this approach in the main text of our paper.
2. Secondly, our confidence intervals not only incorporate finite sample uncertainty from finite calibration data, but also account for the possible sub-optimality in the fairness trade-offs achieved by $h$. Specifically, to incorporate the latter, we formally consider the gap between the optimal accuracy-fairness trade-off $\tau^\ast_{\text{fair}}$ and the trade-off achieved by a model $h$, denoted by $\Delta(h)$ in Figure 2 in the main text. Part of our methodology for obtaining the lower confidence interval involves quantifying this gap $\Delta(h)$. While this gap $\Delta(h)$ is intractable in general, we propose a sensitivity analysis methodology to posit plausible value for $\Delta(h)$ in practice (in Appendix C). In contrast to the previous works in fairness literature [Agarwal et al., 2018, Bendekgey & Sudderth, 2021, Zafar et al., 2015; 2017; 2019], to the best of our knowledge, our work is the first to consider uncertainty arising from both, finite datasets used to evaluate accuracy and fairness metrics as well as the possible sub-optimality in the fairness trade-offs achieved by $h$.
3. Thirdly, we also propose a novel methodology for constructing informative confidence intervals in the setting where the sensitive attributes $A$ are accessible only for a small subset of the calibration dataset. This methodology effectively combines data with actual and predicted sensitive attributes to derive tighter and more accurate CIs, even when the majority of $A$ values are absent.
4. Finally, while YOTO has previously been applied in areas like multi-task learning [Lin et al. 2020], our work provides a novel application of the YOTO framework to fairness literature and offers practitioners the capability to, at inference time, specify desired accuracy levels and promptly receive corresponding admissible fairness violation ranges.