FairPATE: Exposing the Pareto Frontier of Fairness, Privacy, Accuracy, and Coverage

• W3 Abstaining from prediction for fairness reasons The introduction justifies this as "if a decision cannot be made without violating a pre-specified fairness metric, then the model can refuse to answer at which point the decision can be relegated to a human judge". If I have understood this correctly, this is a flawed argument...

  • We think there has been a misunderstanding regarding a) purpose of the reject option for fairness, and b) the inference-time nature of the IPP algorithm that implements it. What the reject-option enables is for a human (e.g. a trained judge) to take over the decision making in case of a fairness constraint violation. The presumption here is that a trained judge is better placed to make impactful decisions than the algorithm. Therefore, the human judge can choose to accept violations of the fairness constraint on a case-by-case basis. We do not believe the human judge should be placed under the same constraints as the algorithm given the vast difference in training, experience and accountability faced by the human judge versus the algorithm.

• Consider the situation where there are group of data points from the majority group, on which if the algorithm predicts correctly the fairness will be violated and hence the algorithm abstains

  • Please note that IPP is an inference-time algorithm. It is incorrect to say that the "algorithm predicts correctly that the fairness will be violated" because there is no prediction involved in this process. For instance, using Demographic Parity, the fairness metric requires that the rates of acceptance be similar for different subgroups. Since IPP is releasing decisions, it can keep an exact record of the decisions released (this is what $m(z,k)$ counter keeps in Algorithm 1). Therefore, the rates calculated based on this record is exact and so are the detected violations that would prompt the algorithm to reject a certain query.

• Intuitively, it appears that any problem can be made fair this way by simply refusing to predict on certain majority groups thereby artificially boosting the fairness of the algorithm. The correct fairness solution should aim to improve performance on the minority group instead.

  • Our standard fairness metric does not require a notion of majority vs. minority. At any given decision point, our algorithm (IPP) bounds the worst-case fairness violations experienced by any subpopulation. Furthermore, the reject-option is not a silver bullet; as it comes with a trade-off with coverage (1-rejection rate). Therefore the more rejections translate more work for the human judge. It is, therefore, in the best interest of deployer of the upstream algorithm (FairPATE or DP-FERMI, or any other fairness-aware) algorithm to minimize fairness violations at training-time; because an unfair algorithm will increase the work that human judges would need to do— eliminating the need for the fair algorithm in the first place.

• W4  Unfair Comparisons Fair-PATE and Loewy et. al's algorithm do not work under the same restrictions of differential privacy. Specifically, Fair-PATE uses public unlabelled data and Loewy et. al doesn't and we know that (even a small amount of) public data can severely help in improving accuracy of DP models (perhaps fairness too). Hence, it appears to me that Loewy et. al. uses a significantly stricter notion of privacy and achieves nearly comparable result and in some cases even better (for tabular datasets, there are no comparison on vision datasets with Loewy et. al.).

  • We wish to clarify and disentangle two issues that the reviewer points out: a) access to public data, b) access to additional data. All of our baselines experiments are conducted using the exact data splits of Lowy et al. 2023. This means that we do not use any additional training data compared to our baselines. Instead, we use the training data available to us and partition it into public and private. Consistent with the original PATE framework, we do not use the labels of the public dataset; instead we train teacher models on the private partition and label the public points under privacy and fairness constraints. In Figure 1.a, a DP-SGD method like Lowy et al. 2023 replaces the shaded Private Model. Therefore, we respectfully disagree with the reviewer's assessment that the comparisons are not fair data-wise. As a matter of fact, in our experiments, DP-Fermi receives additional information compared to FairPATE (namely, the labels of the public data partition).

We thank the reviewer for their feedback. Below we address each point raised in "Weaknesses" section.

• Several examples of underperformance Several examples also show that FairPATE performs significantly worse than competitor. Examples include Demographic Parity for Adult dataset and UTK Face ().

  • For the concerns about significance, please see our General Response.

  • We have noted clearly in the main paper that for the Adult dataset, under Demographic Parity DP-Fermi performs better than FairPATE for smaller epsilon values (Figure 10). However that trend is not consistent over different datasets (on UTKFace, FairPATE does better for lower epsilons and can even go lower in terms of achievable classification error—see Figure 6). We provide a discussion on the cause of these performance differentials in response to Reviewer XkhF.

• Misleading regarding diversity of experiments In the introduction, the paper sells itself regarding performing a wide range of experiments but results on nearly half of these datasets are hidden away in the appendix without any mention in the main text and without comparisons. Experiments on CheXpert, CelebA, FairFace, and Retired-Adults are not available in the main text and it is very hard to interpret the results presented for this in the appendix. In fact, there areno results of FAIR-PATE on CheXpert in the paper

  • The CheXpert results were already present in the paper (in the last figure of the appendix) but was unfortunately mislabeled. We apologize for the error. The figure's label has been corrected in the updated manuscript.

  • We currently have results of FairPATE on CheXpert, CelebA and FairFace in Section H in the appendix. Unfortunately given the space constraints we cannot add all the aforementioned results in the main text.

• Please show comparison on these for demographic parity and equalized odds (similar to Figure 2,3 with comparison to Loewe et. al.'s algorithm) on these four datasets. In addition, there are results in the literature that run DP algorithms on CelebA and CheXpert. Comparisons should be made to them to show what is the sacrifice being made compared to state-of-the-art.

  • DP-FERMI is an expensive algorithm to run. On CelebA, it requires 33 hours to train one model for 200 epochs as specified in the paper without parameter tuning on an NVIDIA A100; while the model has at least 4 hyper-parameters to tune. Nevertheless, we are currently in the process on running DP-FERMI on CelebA, and we will report the results as we acquire them in the coming days.

• W2 Wrong Conclusion from Theorem 2 I did not go through the detail of Theorem 1 but I assume it is correct and follows from Group privacy arguments. However, the sentence above Theorem 1 (Point C2) claims that the result proves that " pre-processing ... will necesarrily degrade the guarantee of the .... private learning mechanism". How ever this is not what the Theorem shows. The theorem only proves a privacy guarantee of   $M \odot P_{\mathrm{pre}}$ not that this is the tightest privacy guarantee possible for the composed mechanism. Am I missing something ?

  • We are not sure we follow the reviewer's comments here. Does the reviewer take issue with the phrasing of the claim " pre-processing ... will necesarrily degrade the guarantee of the .... private learning mechanism"?

  • If yes, then we apologize for the confusion. We can adjust the claim as

    pre-processing ... will necessarily degrade the guarantee of the .... composed preprocessor and private learning mechanism

  • Of course, the private learning algorithm does not degrade on its own; but via the inclusion of a fairness pre-processor, we have shown that the joint fair and private mechanism will have degraded privacy guarantee which is always an upper bound on the privacy leakage

  • We are also unsure of what the reviewer mean by the "tightest privacy guarantee possible for the composed mechanism." Do they mean that another $\mathcal{P}_\text{pre}$ could possibly reduce the privacy cost? If yes, then given that the pre-processor is simply ensuring the fairness definition holds (via a filter that class balances the dataset conditioned on the sensitive attribute) can the reviewer recommend another pre-processor?

• Motivation. I understand that there are several works showing that privacy incurs a sacrifice in fairness. However, one possible approach to this problem is simply improving the accuracy and perhaps the resultant accuracy also leads to high fairness. In fact Berrada et. al. (2023) makes this argument with some experiments in their paper. I did not see an argument in this paper why this approach is not expected to solve all problems. Why should there be a trade-off between privacy and fairness ? Is it known in the literature and are there theoretical studies arguing about the necessity of a trade-off ?

  • Berrada et al. 2023 only consider unfairness with respect to loss disparity. This particular fairness metric is inherently a measure of the generalization of the model. That is, if a model is well generalized, then it is also well-generalized for different subpopulations of the data; therefore, it is only natural that it would exhibit lower loss disparity. As a result Berrada et al. 2023 do not consider (or rather, need to consider) an unfairness mitigation step. Our results (and that of Lowy et al. 2023 and others) show that for other group fairness metrics, this is not the case. That is, fairness and accuracy do not align so well all the time.

  • In terms of theoretical results Cummings et al. 2019 provide an the impossibility result for DP learning and exact fairness; while also demonstrating a positive result for the case of approximate fairness (our settings). More recently, Mangold et al. 2023 have showed that "the fairness (and accuracy) costs induced by privacy in differentially private classification vanishes at a $O(\sqrt{p}/n)$ rate, where n is the number of training records, and p the number of parameters." This is achieved through a proof of pointwise Lipschitz smoothness of group fairness metrics with respect to the model where the pointwise Lipschitz constant explicitly depends on the confidence margin of the model, and may be different for each sensitive group. Therefore, in the presence of minority groups in the data, we can expect a non-zero gap between private and non-private models.

• Missing baselines. Why is there no comparison with the algorithm of Zhang et. al. (2021), Kulynuych et. al. (2022) and Berrada et. al. (2023) ? They are mentioned in one or two sentences at the very end of the paper but without any comprehensive empirical comparison.

  • Kulynych et. al 2021 does not account for the privacy leakage of its importance sampling step therefore a fair comparison with methods such as ours or Lowy et al. 2023 is not possible

  • Berrada et al. 2023 only considers loss parity, and has no unfairness mitigation for two of our gorup fairness metrics (see our previous answer for more details)

  • Zhang et al. 2021 implement early stopping to save on privacy budget; however, they do not measure the privacy leakage of their early stopping criterion therefore the privacy loss reported is underestimated

• What is FairDP-SGD ? It doesn't seem to have been defined anywhere ? Is it an existing work ? Where is FAIR-PATE's result on CheXpert ?

  • This is an error on our part. The figure in the appendix was mislabelled. We apologize for the confusion. The figure's label has been corrected in the updated manuscript.

We once again thank the reviewer for their detailed feedback and kindly ask them to consider raising their score if we have addressed their concerns successfully. We are happy to answer further questions.

We kindly note that in the following, where appropriate, we have grouped the reviewer's questions together:

• I can't judge what is the impact of IPP (the rejection step added at inference time) on the overall results. Can you provide some ablation study showing how the framework performs on various datasets with different majority/minority distributions with and without IPP?

• How does the framework work in case of some distribution shift? This is especially important in the context of my question above.

  • We have run additional experiments on FairPATE+IPP and have added the results Section E.2 in the appendix of the updated manuscript. We observe that under class-imbalance for every percentage of coverage degradation, the fairness-privacy curve improves consistently. For the balanced case, we observe that the disparity levels are much higher. This is because random (non-stratified) sampling is not conducive to demographic parity. IPP's overall behavior is similar as before but the curves are much closer to each other and the rejection rates are higher due to high disparity levels of the initial models caused by random sampling.

• For the other datasets reported in the appendix the trends shown reverts, e.g., DP-Fermi produces better tradeoffs than FairPATE. Can you discuss why? What feature of the dataset makes this possible?

  • We thank the reviewer for the insightful question. Adult is a label-imbalanced dataset and we believe this is the reason its results stand out. Let us elaborate on this point: FairPATE achieves better fairness by pre-processing (a sample-level mitigation). As a result, if the dataset is imbalanced; especially if it is conditionally imbalanced, that is $\mathbb{P}[Y = 1 \mid Z = 0] - \mathbb{P}[Y = 1 \mid Z = 1] > \gamma,$ then fairness of a model trained on such data would also be bounded from below: $\mathbb{P}[\hat{Y} = 1 \mid Z = 0] - \mathbb{P}[\hat{Y} = 1 \mid Z = 1] > \alpha > 0.$ This follows from Shamsabadi et al. 2023 Theorem 1, if we assume that the ground truth labels $Y$ are coming from a data oracle and the predicted labels $\hat{Y}$ are from the "surrogate model". Since the oracle model is not fair; then the actual model trained on those will similarly not be fair (in the demographic parity sense).

  • DP-FERMI on the other hand has a model-level mitigation with a fairness regularization term scaled with $\lambda \in \mathbb{R}^+$ . For a large enough $\lambda$ , DP-FERMI can close the fairness gap on a particular dataset. However, this comes at a cost to generalization. Prior works in algorithmic fairness have noted this trade-off under the notion of "stability" and "generalization of fairness" (see for instance, Huang and Vishnoi 2020). We note that in Section D in the appendix, we also present a weight-space mechanism (namely, model fair-tuning) and show it to be similarly effective in reducing the residual fairness gap of a FairPATE student model.

• Fig. 2 and 3 use orange colors for two different algorithms (Tran et al (Fig 2) and Jagielski et al. (Fig 3)). The authors should report all algorithms in all figures or justify their absence.

  • We have regenerated and replaced Figure 3 to ensure distinct colors. We apologize for the confusion.
  • As to the reason why Figure 3 does not include Tran 21 et al, we have already made an explicit note in the empirical section that we report the same baseline results as reported by Lowy et al. 2023 (in 2nd line of SOTA Baseline Comparisons) including that of Tran et al 2021.

• Why Tran et and Jagielski et al. are not reported for the UTK-dataset experiment?

  • Both methods are evaluated on tabular data and are not suitable for deep learning models. In particular, Lowy et al. 2023 report that they have attempted this to no avail:

    We observed that the baselines were very unstable while training and mostly gave degenerate results(predicting a single output irrespective of the input). By contrast, our method was able to obtain stable and meaningful tradeoff curves.

    Given that DP-FERMI reports better fairness-accuracy trade-offs at every privacy level compared to these baselines; we found it sufficient to test FairPATE against the new state-of-the-art (DP-FERMI); and report the other baselines for which we had reported data.

Minor comments:

• A lot of the cited papers have appeared in conferences. But the authors cite their arxiv version. I suggest to update the references accordingly.
  • We thank the reviewer for their careful reading of the paper. We have replaced the arxiv papers with conference counterparts.

We once again thank the reviewer for their detailed feedback and kindly ask them to consider raising their score if we have addressed their concerns successfully. We are happy to answer further questions.

We thank the reviewer for their feedback. Below we address each point raised in "Weaknesses" section.

• Fairness is "enforced" by adding parity constraint within the aggregator which acts as a rejection sampling step on the basis of fairness. The general idea was proposed in several other works in the past, including the ones cited by the authors and against which the authors compare. It is thus difficult to understand what is new in the proposed framework. An explicit mention would help.
  • The reviewer is correct that our work enforces fairness on the level of sample selection. However, this is done within a differentially private learning setup. The only prior work that we are aware of that has a sampling step for fairness within a private-learning setup is Kulynych et. al 2021 but importantly that work does not consider the privacy cost of the fairness importance sampling it performs while our work does.
  • We have added an extended related works section in Section I in the appendix with a more detailed comparison to Kulynych et. al 2021.
• A discussion on when to use the proposed framework in contrast to other frameworks is absent (see also my questions below).
  • We have addressed the reviewer's concern. Please see our General Response.
• The experimental analysis should be improved. Some figures are misleading, e.g., same colors used for different algorithms (see questions below).
  • We have re-generated the figures in question (3 and 4) and updated the manuscript accordingly.

We thank the reviewer for their feedback. Below we address each point raised in "Weaknesses" section. We kindly note that in the following, we have grouped the reviewer's comments that addressed a common concern:

• The implications of rejecting for fairness are not considered. Rejection for privacy has implications in terms of privacy budget and likewise rejections for fairness come with implications and ignoring them might be responsible for the observed gains on the Pareto frontier. Consider the noted rejection example: ...

  • Our understanding of the reviewer's remark here is that in a human-in-the-loop setting, the mistakes of the human would ultimately be mistakes of the end-to-end system; and therefore, measuring the efficacy of the system should consider the human error as well. While we agree with the reviewer, we believe that measuring the end-to-end error of the human-in-the-loop system should be the topic of a future study.

  • We have added the following to our discussion in Section 7:

    We note that in a human-in-the-loop system, the mistakes of the human would ultimately be mistakes of the end-to-end system; and therefore, measuring the efficacy of the system should consider the human error as well. We have shown that FairPATE and IPP enable such applications but whether such a system is the appropriate choice for a given application is out of the scope of the current study.

• In arguments for intervention points, assumptions are made which preclude solutions. They assume the intervention need to be made independent of other mechanisms in PATE. That is, they cannot consider information internal to decision making that is not described by Figure 1 like individual teacher outputs. This leaves the possibility that some fairness methods might be able to integrated with PATE in a closer manner than the options described. One example is that they might include the teacher outputs instead of operating on the overall predicted class like Algorithm 1 assumes presently. C3 in particular suggests that some interventions will not account for privacy budget correctly due to special circumstances and suggests at Point 4, they can be budgeting can be handled correctly. Nothing is stopping a design from refunding privacy budget if a query is rejected subsequently to an intervention point.

  • Regarding the suggested alternative scheme, we would like to to ensure that we understand the premise correctly: is the reviewer suggesting that we run PATE, accept and reject queries according to standard PATE analysis, and then apply the fairness intervention and reject possibly some more queries; and come back to give back some of the privacy budget?

  • If the answer is yes, then we note that standard PATE privacy analysis in Papernot et al. 2016 (summarized in Section B in the appendix) is based on the probability of answering a certain query. To recoup the "unused" privacy budget one needs to find the difference between the privacy budget if the sample would have been answered and the privacy budget if the sample wouldn't have been answered. Note that the this is exactly what FairPATE already performs. Therefore, the suggested scheme is functionally equivalent to FairPATE but presents additional complexity.

• Results in the Pareto frontier show small improvements, no improvements, and in some cases worse results than prior baselines.

• Suggestion: Include more experimental samples in the results to make sure the statistical validity of any improvement claims is good. This may require larger datasets. Related, the experiments show error bars but how they are derived is not explained.

  • We have included more results in the revised manuscript. Please see our responses to Reviewers XkhF and p5Rv.

• Comparisons against methods in which rejection due to fairness is not an option may not be fair.

• Suggestion: either integrate suggestion regarding accounting for rejection above, or incorporate some form of rejection (or simulate it) in the existing methods being compared to. It may be that the best methodology is not FairPATE but some existing baselines if adjusted to include fairness rejection option.

  • The reviewer is correct that the IPP algorithm is an inference-time algorithm, therefore, its use is not limited to a FairPATE model.
  • We have run additional experiments on other models with the IPP; and included the results in Section E.1 in the appendix. We find that FairPATE with IPP outperforms baselines (with IPP) in most regions fairness-privacy settings in both accuracy and coverage. See Figure 11 for a 2d Pareto surface, or Figure 12 for a corresponding 3d plot which showcases the accuracy performance improvements better.

• Question A: Is reasonable to ignore downstream decisions from queries rejected due to fairness (i.e. contrary to my suggestion in the weaknesses above)?

  • We believe the alternative algorithm suggested is functionally similar to FairPATE. Please see our answer above.

• Question B: C1 makes a point that adding privacy after fairness may break fairness. What about in expectation? Were one to view the demographic statistics defining fairness measures in expectations, wouldn't they remain fair?

  • The aforementioned fairness constraints are rate constraints which are in and of themselves expected values. If the constraints remain effective post DP noising; it means that we have retained at least group membership information. This is inconsistent with the standard neighboring relationship that our standard privacy definition adopts (i.e., one-sample difference between two datasets) therefore it is a weaker privacy notion. We conjecture that this weaker privacy notion would be closer to the DP w.r.t. sensitive attributes (which defines the group membership), but that it is possibly even weaker because prior theoretical work with DP w.r.t. sensitive attributes (namely, Mozannar et al. 2020) have already shown that a second post-processing step is necessary to ensure the fairness constraint is satisfied post DP-noising.

• Question C: Theorem 1 makes a statement about a pre-processor inducing privacy parameter degradation but FairPATE (or PATE) appears to fit the definition of a pre-processor. If the point of the Theorem is to argue against pre-processors, isn't it also arguing against PATE/FairPATE? Unrelated, what is "ordering defined over the input space X" and why is it necessary?

  • Theorem 1 does not apply to FairPATE because it does not pre-process the training data as described in theorem 1. FairPATE is a pre-processor from the point of view of the student which only sees public queries. An algorithm that pre-processes the teacher data would indeed fit Theorem 1 because it sees private sensitive data (this is intervention point 1 in Figure 1.a).

  • The assumption on the ordering is a technicality that simplifies the the proof. In practice, one can almost always assume such an ordering exists. An example of such ordering would be to order images based on their pixel values in some specified order of height, width and channel starting by checking the first pixel, then the second pixel, and so on.

We once again thank the reviewer for their detailed feedback and kindly ask them to consider raising their score if we have addressed their concerns successfully. We are happy to answer further questions.

Smaller things:

• Rejection rate is not shown in any experiments. One could view a misclassification as a rejection, however. Please include rejection rates or view them as misclassifications in the results.

  • We do report coverage which is 1-rejection rate for the results that use the IPP. See Figure 5 where coverage is marked by the color; similarly the Pareto frontiers in the appendix all include coverage encoded in color.

• The distribution whose fairness need to be protected is left to be guessed by the reader. For privacy, it is more clear that it is the private data that is sensitive and thus privacy budgeting is done when accessing that private data as opposed to the public data. For fairness, the impact on individuals in the private dataset seems to be non-existent as the decisions for them are never made, released, or implemented in some downstream outcome. I presume, then, it is the fairness needs to be respected on the public data.

• Algorithm 1 and several points throughout the work hint at this. However, there is also the consideration of intervention points 1,2,3 which seem odd as they points seen before any individual for whom fairness is considered is seen. That is, fairness about public individuals cannot be made there, independent of any other issues such as privacy budgeting. Further, Theorem 1 discusses a demographic parity pre-processor which achieves demographic parity on private data which I presume is irrelevant.

• The statement "PATE relies on unlabeled public data, which lacks the ground truth labels Y" is a bit confusing unless one has already understood that fairness is with respect to public data. PATE also relies on private labeled data to create the teachers.

  • A fairness intervention and a privacy intervention have different goals w.r.t. the data distribution they target. In private learning, the goal is to protect the privacy of the sensitive training data only. In fair learning, the end goal is to ensure the algorithmic decisions (at inference-time) are fair. Within the context of FairPATE; from a private learning perspective, PATE (and FairPATE by extension) protect private teacher data (see Figure 1.a) and not the public unlabeld data. From a fair learning perspective, a FairPATE model is just like any other fairness-aware model is trained such that it achieves fairness on training data, with the expectation that that behavior generalizes to inference-time. These are standard assumptions which is why we have refrained from repeating them.

Smallest things:

• Double "violations" near "violations of demographic disparity violations".
• The statement "DP that only protects privacy of a given sensitive feature" might be mischaracterizing DP. It is not focused on features or even data but rather the impact of individuals on visible results.
  • We thank the reviewer for their keen eye. We have fixed the typo and revised the sentence to

    ..DP that only protects privacy of individuals with respect to particular sensitive features...

Thank you for the clarifications.

• With regards to:

  "From a fair learning perspective, a FairPATE model is just like any other fairness-aware model is trained such that it achieves fairness on training data, with the expectation that that behavior generalizes to inference-time. These are standard assumptions which is why we have refrained from repeating them."

  Some discussion there is warranted despite "standard assumptions". FairPATE (Algorithm 2 and Algorithm 1) enforces fairness on the inference-time instances and I don't think this requires an assumption of being distributed similarly to training-time data. The approach does not resemble fairness-aware model training but rather an inference-time enforcement mechanism. The approach's DP protection of inference-time instances is only coincidental and not the goal while fairness w.r.t training-time instances is irrelevant as it is in any fairness training procedure (decisions for training instances have already been made in the past as indicated by their label). Is it accurate to say that "FairPATE addresses inference data fairness and training data privacy"?

• With regards to discussions about comparisons against baselines that do not have the option to "reject due to fairness violation"; I don't see a suggestion of solution for this work and given how close the results already were, my concerns regarding this fairness and results are not addressed enough to warrant an upgrade in score large enough to the next threshold value.

Dear Authors,

Thanks for the response. Just to clarify when you say

'''Finally, all PATE-based frameworks assume access to an unlabeled public dataset on which privacy accounting does not take place. This is akin to pre-training DP-SGD models on public data before any privacy accounting occurs—although this requires labels while PATE-based models do not.'''

Do you mean PATE uses the same kind of data, but without labels, as DP-SGD normally uses for pre-training ?

From my understanding, the most popular examples of DP-SGD using pre-training is ImageNet pre-trained for private fine-tuning on CIFAR or JFT pre-training for fine-tuning on ImageNet and similar for NLP tasks.

Is your public data from a very different distribution compared to the test set ? That's not the impression I got from reading the draft.