A Generic Framework for Conformal Fairness

We thank the reviewer for taking the time to review our paper. We further appreciate the reviewer’s positive comments regarding the manuscript's writing.

[W1] Conformal Fairness metrics need to be well-discussed in methodology. Specifically, Theorem 3.4 states that "the coverage difference for Predictive Parity is satisfied". In Table 1, the definition of Predictive Parity relies on a conformal prediction, $\mathcal{C}$, but the specific mapping/quantification is not discussed in the theorem statement

We are happy to clarify Theorem 3.4’s statement, especially in the last sentence regarding “the coverage difference for Predictive Parity is satisfied”. The use of “coverage difference” is a bit misleading since the prediction set is the conditional of the probability for Predictive Parity. We are balancing an adapted PPV between groups by minimizing the difference. We will clean up the language in Theorem 3.4 in the updated manuscript.

[W2] Suppose there is a conformal prediction in Theorem 3.4, how good is it, i.e. what shall the value of $\alpha$ be, as in Equation 1

The choice of $\alpha$ may not be in the hands of the practitioner but instead defined by regulatory frameworks within the domain you’re focused on (e.g. 80% rule is $\alpha = 0.8$ for Disparate Impact). This is similar to standard conformal prediction, where you have an $\alpha$ miscoverage that you want to be within.

We thank the reviewer for taking the time to review our paper.

[W1] Need to elaborate on design choices.
[Q1] Why choose inverse quantile for miscoverage level? Explain a bit more about the intuitions behind Lemmas 3.1 and 3.2.

We are happy to elaborate on our design choices in the methodology section. Below, we’ve provided some motivation for the particular queries the reviewer asked about.

Choice of Inverse Quantile: To achieve a $1 - \alpha$ coverage level (or equivalently an $\alpha$ miscoverage level), prediction sets are constructed using the $(1 - \alpha)$ quantile of the calibration scores as an upper threshold for when to include class labels. Formally, $\mathbb{P}(y_{n + 1} \in \mathcal{C}(x_{n + 1})) = \mathbb{P}(s(x_{n + 1}, y_{n + 1})\leq \hat{q}(\alpha)) = Q^{-1}(\hat{q}(\alpha), \lbrace s(x_i, y_i)\rbrace_{i = 1,}^{n})$, where $Q^{-1}$ is the inverse quantile function. Varying the miscoverage can be done by varying the threshold used to be higher or lower than $\hat{q}(\alpha)$.

Lemma 3.1 Motivation and Intuition: The fairness metrics considered in this work are evaluated on a subpopulation (e.g. for members of a particular group or particular true label). The purpose of Lemma 3.1 is to assert the bounds in CP hold when we consider a subset of the calibration set, which intuitively makes sense due to exchangeability.

Lemma 3.2 Motivation and Intuition: Lemma 3.2 is to derive the miscoverage level when given a particular threshold using the calibration scores. This workflow is the opposite of conformal prediction, where you are given a miscoverage level and need to determine the threshold (i.e. $\hat{q}(\alpha)$) that achieves it. The intuition for the inequality comes from exchangeability between the calibration and test scores.

We thank the reviewer for engaging in a discussion about our work. We are happy to answer any further questions the reviewer may have.

[Q1] Minor Concerns: RAPS has superseded APS. Also, need some baselines with other conditional conformal prediction methods.

The CF Framework is agnostic to the particular non-conformity scoring function and can easily work with RAPS as it does APS, TPS, CF-GNN, DAPS, etc. In Figure E14 in "Rebuttal Additional Results.pdf" in the supplemental material, we show some results for efficiency and fairness violations for varying values of $c$ with the ACSIncome dataset with RAPS alongside the APS results from the manuscript. We observe that the CF framework improves the fairness compared to the baseline RAPS predictor similarly to the APS results.

For comparison with other conditional CP methods, see the results shared for [W3] where we adapt the BatchGCP algorithm for the ACS datasets.

We plan to include these additional results in an appendix in the updated manuscript.

[W3] Missed an established line of work on group-conditional fairness guarantees; these works study the enforcement of coverage guarantees (usually of both upper and lower bounds) on rich classes of subpopulations given by possibly arbitrarily overlapping groups.

We thank the reviewer for highlighting this line of work and will include these references to better elucidate the developments that lead up to our work.

While these works study group-conditional coverage guarantees, they omit discussions of class conditionality, which is incorporated in the standard (and our conformal) definitions of common fairness metrics. Class-conditional coverage goes beyond group-conditional coverage and is more interpretable than group-conditional coverage in certain settings, as discussed in [2] which we cite in our work.

Below we discuss each of the papers the reviewer shared and how it differs and relates to our work. We pick the only work (C. Jung et al.) among these that can act as a baseline – for the group-conditional-only fairness metrics – and compare our proposed method.

• R. Barber et al: The limits of distribution-free conditional predictive inference [IMA 2020]:
  This work provides a thorough theoretical analysis of conditional conformal prediction and characterizations for when conditional coverage guarantees hold. Our work with the adapted conformal fairness metrics is an instantiation of the characterizations of the theoretical results presented.

• C. Jung et al: Batch Multivalid Conformal Prediction [ICLR 2023], O. Bastani et al: Practical adversarial multivalid conformal prediction [NeurIPS 2022]:
  These works aim to achieve multivalid conformal guarantees which require (1) group-conditional and (2) threshold-calibrated coverage guarantees. Though our work and these two works involve group-conditional coverage, these works are orthogonal because they focus on additionally achieving threshold-calibrated coverage whereas we consider additionally achieving class-conditional coverage for metrics like Equal Opportunity and Predictive Equality. These methods do not provide applicable guarantees for balancing the coverage of each positive label between groups.
  
  O. Bastani et al. conducted experiments for sequential prediction tasks – a distinct task from what we are considering.
  
  C. Jung et al. only conducted experiments for regression-based tasks; however, we were able to use their BatchGCP algorithm (and code) to provide another baseline to compare our method. Using the ACSIncome dataset and the XGBoost model that we trained for our results, we use their BatchGCP algorithm to construct a threshold function and evaluate the fairness disparity and efficiencies compared to our group-conditional baseline and our CF Framework. Since BatchGCP only optimizes for group-conditional coverage, we present the results for Demographic Parity (see Figure E12 in "Rebuttal Additonal Results.pdf" in the supplemental material) and Disparate Impact (see Table E6 in "Rebuttal Additonal Results.pdf" in the supplemental material) – two fairness metrics that only condition on group information. The results show that our framework can control for the group conditional coverage disparity between groups unlike Base APS and BatchGCP. To dissect the poor performance of BatchGCP, we plot the per-group coverages in Figure E13 in "Rebuttal Additonal Results.pdf" in the supplemental material and observe that certain groups are significantly undercovered (i.e., groups 4, 5, and 7).

• Z. Deng et al: Happymap: A generalized multi-calibration method [ITCS 2023]:
  This work introduces a generalization for multi-calibration and how it relates to algorithmic fairness for conformal prediction; however, the applications are limited to Equalized Coverage for Regression tasks and don’t present any experiments (synthetic or real) to compare against.

• I. Gibbs et al: Conformal Prediction with Conditional Guarantees [2023]:
  This work considers a wide array of problems that interpolate between marginal and conditional coverage by considering conditional coverage as a class of covariate shifts. This work generalizes some of the notions presented in C. Jung et al. regarding group conditional coverages; however, it relies on the i.i.d. assumption throughout its theory. This assumption limits the work’s applicability to non-i.i.d spaces (e.g. graphs) which our framework applies as seen with our experiments on real-world graph datasets.

[1] Anastasios Nikolas Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, Tal Schuster, “Conformal Risk Control”, The Twelfth International Conference on Learning Representations (2024)

[2] Tiffany Ding, Anastasios N. Angelopoulos, Stephen Bates, Michael I. Jordan, and Ryan J. Tibshirani. Class-conditional conformal prediction with many classes. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23

[W2] The theoretical/methodological side does not offer strong novel contributions; for the most part, it simply wraps class-conditional and group-conditional conformal methodology into fairness-specific terminology

We note that novelty is certainly in the eye of the beholder and that while our framework builds upon the ideas of conditional conformal methodologies, the simplicity of the framework does not necessarily take away from the novelty. Additionally, our framework differentiates itself from the existing literature in a few different aspects:

1. Group Information at Inference: Existing works in group conditional prediction require knowledge of the group information at inference time. This can be a limiting factor as the group information can be purposefully withheld to de-bias certain processes or in an online setting, where data is coming in a real-time or streaming manner as mentioned in Lines 238-241. In these settings, even if group information is absent, the CF framework still provides group-conditional coverage. We will elaborate on this point in the updated manuscript as we clean up the writing in response to [W1].

2. Balancing miscoverage for all groups and all labels: Existing literature aims to minimize group conditional miscoverage, i.e., for all groups, $g$, $\mathbb{P}(y_{n + 1}\not\in \mathcal{C}(x_{n + 1})|x_{n + 1}\in g)\leq \alpha$ for some $\alpha$. What our framework does differently than the existing literature, is formulate fairness as the pairwise miscoverage disparity across groups. Additionally, we account for conditioning on advantaged labels, similar to fairness metrics like Equal Opportunity and Predictive Equality, in the disparity measurement, which is essential for evaluating certain notions of fairness. For example, metrics like Equal Opportunity require expressions of the form $\mathbb{P}(y_{n + 1}\not\in \mathcal{C}(x_{n + 1})|x_{n + 1}\in g, \mathbf{y_{n + 1} = y^+})$, which would not fit into the existing group-conditional CP literature.

   To balance the miscoverages between groups, we use the inverse quantile to determine the miscoverage for a given threshold. The inverse quantile operation is unique in this context and is not similarly utilized in the existing literature including the literature the reviewer shared. This operation is performed for all the subpopulations (i.e. based on group membership and true label). Coupled with the bounds given by Lemma 3.1 and 3.2, we can find an appropriate threshold where the fairness disparity requirement and the standard coverage guarantees are met.

3. Predictive Parity (Conditioning on prediction set): Unlike the other fairness metrics considered, Predictive Parity involves conditioning on the predicted label (or existence in the prediction set for conformal fairness). We provide Theorem 3.4, which discusses when the standard notion of Predictive Parity can be balanced. We also present a proxy for Predictive Parity where a solution that satisfies an arbitrarily small disparity constraint (i.e. arbitrarily small values of $c$) always exists.

We thank the reviewer for taking the time to review our paper.

[W1] The main weakness and bottleneck at this point is the writing of the manuscript In particular, the writing of Section 3, which introduces the objectives, the general algorithm, and the analysis. Lots of key notions and terms, both on the fairness side and on the conformal side, are not properly and unambiguously introduced and/or are discussed in arbitrary order.

We understand the reviewer’s concerns about the clarity and organization of the manuscript and agree that the introduction of key notions and terms and the flow of the material can be improved. We clarify the specific notions/terms the reviewer mentioned below:

Fairness:

• Groups: We define groups as subpopulations of the dataset attributed to some protected attribute (e.g. race, gender).

• Filters/Filter function: Each fairness metric is evaluated on a subpopulation based on the group information and true class label. The “filter function” abstracts the different subpopulations in the algorithm so that inverse quantiles and scores are computed on the correct subpopulations. For a concrete example, see Section 3.3. Input.

• Fairness → Conformal Fairness: We adapt the fairness definitions for our conformal framework, by replacing predicted label equality ($\cdot = \hat{Y}$) with existence in the prediction set $\cdot \in\mathcal{C}_{\lambda}(X)$. This sort of conversion is also done in the literature [1].

Conformal Prediction:

• Interval Widths: Our setting, like most CP works, deals with finite-sample miscoverage guarantees, which state that the miscoverage is in the interval $(\alpha - \frac{1}{n + 1}, \alpha]$. The interval width is $\frac{1}{n + 1}$.

• Label Miscoverages: Our framework aims to balance the gaps in miscoverages between sensitive groups for all advantaged/positive labels (e.g., is_approved for loan approval task). Thus, we compute the miscoverage for each group and each positive label using the inverse quantile and save the results.

Dear Reviewer ST3N,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concerns and whether you will keep or modify your assessment on this submission?

Thanks,

Area Chair

We thank the reviewer for engaging in a discussion about our work, for their constructive comments, and for updating their scores. We will iterate and improve the presentation while addressing specific suggestions (e.g., the closeness criterion discussion). We also thank the reviewer for acknowledging our work's usefulness for conference attendees interested in the union/intersection of conformal prediction and ML fairness. We are happy to answer any further questions the reviewer may have.

[W3] Lack of comparison with all existing fairness-aware methods limits benchmarking. Adding baselines would clarify the framework's effectiveness.
[Q2] Why were existing fairness-aware methods not used as baselines for comparison?

Our paper is focused on making a fair version of conformal prediction, thus we compare it to standard conformal prediction methodologies (e.g., APS and TPS). Our framework can utilize other CP methods (e.g. RAPS, CF-GNN, DAPS, etc.) and directly improve on those in terms of fairness. For an additional non-conformity score method, we include results with RAPS in Figure E14 in "Rebuttal Additional Results.pdf" in the supplemental material.

Going beyond simply using group conditional coverage directly, which is currently our baseline, there hasn’t been much work in the fairness + conformal prediction space. As mentioned in our Discussion section, existing works at the intersection of fairness and conformal prediction for comparison are limited. Three recent works we mentioned are cited (Wang et al., 2024), (Lu et al., 2022), and (Liu et al., 2022).

Wang et al. introduce the notion of Equal Opportunity of Coverage – a conformal notion of Equal Opportunity. This work is an instantiation of our work specifically for Equal Opportunity. Our work generalizes to several popular fairness and user-defined metrics, like our Predictive Parity Proxy, which could not be considered in Wang et al.

Lu et al. focus on a particular application of skin lesion classification for medical testing. Furthermore, their proposed method – GAPS/GRAPS – requires group information at inference time, which our method does not and is not always viable in online settings. Liu et al. focus on fairness for quantile regression and tailor their framework for Demographic Parity. Furthermore, their proposed method requires group information at inference time, which our method does not and is not always viable in online settings.

Addressing Reviewer ST3N’s comments about having another baseline related to the recent group-conditional CP literature, we compare against BatchGCP [5] as a baseline to demonstrate the CF framework’s efficacy in balancing miscoverage across groups for all labels. The comparison is done for Disparate Impact and Demographic Parity as they both only require group conditioning. The results are presented in Table E6 and Figure E12 in "Rebuttal Additional Results.pdf" in the supplemental material.

We plan to include these additional results in an appendix in the updated manuscript.


[5] C. Jung et al: Batch Multivalid Conformal Prediction [ICLR 2023]

We thank the reviewer for taking the time to review our paper.

[W1] Lacking detailed discussion of the fairness-efficiency trade-off. Quantifying acceptable efficiency losses when fairness is improved would make the results more actionable for practitioners balancing both aspects

Figures 1 and 2 in the main paper depict the fairness-efficiency trade-off at a high level, but as is common when discussing utility-fairness relationships in the literature [1, 2], improving fairness comes at the cost of utility (i.e., efficiency). The particular requirements for fairness and efficiency losses may not be in the hands of the practitioner but set by regulatory frameworks that exist in the domain you’re focused on (e.g. 80% Rule for Disparate Impact).

[Q1] How does the framework handle scalability with multiple sensitive attributes, especially computationally?

Currently, the framework is implemented serially and thus scales with the number of sensitive groups; however, the framework is embarrassingly parallel with respect to the $\Lambda$ search space (Line 2 in Algorithm 1) and with the inverse quantile computations for each (sensitive group, label) pair (Lines 9-14 in Algorithm 1). Thus, distributed frameworks (e.g., Ray) can be integrated to utilize multiple cores. Parallelizing Lines 9-14 can alleviate the effect of the number of sensitive attributes for framework scalability.

[W2] The extension of the exchangeability assumption to real-world data may not always hold. Adding empirical evidence or discussion on when this assumption is valid in practice would make the claims more robust
[Q3] How practical is the exchangeability assumption for real-world graph data? Any empirical evidence?

In this work, we consider the transductive setting for node classification which, in the existing conformal prediction on graphs literature, there is a theorem that states that the exchangeability assumptions hold between the calibration and test nodes in the transductive setting [3, 4]. We don’t make any claims about the inductive setting, where additional assumptions are required and exchangeability may not be achieved.


[1] Yingqiang Ge, Xiaoting Zhao, Lucia Yu, Saurabh Paul, Diane Hu, Chu-Cheng Hsieh, and Yongfeng Zhang. 2022. Toward Pareto Efficient Fairness-Utility Trade-off in Recommendation through Reinforcement Learning. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining (WSDM '22).

[2] S. Dehdashtian, B. Sadeghi and V. N. Boddeti, "Utility-Fairness Trade-Offs and how to Find Them," 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)

[3] Huang, Kexin, Ying Jin, Emmanuel Candes, and Jure Leskovec. "Uncertainty quantification over graph with conformalized graph neural networks." Advances in Neural Information Processing Systems 36 (2024).

[4] Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 12292–12318. PMLR, 23–29 Jul 2023.