Conformal Classification with Equalized Coverage for Adaptively Selected Groups

Thank you for your careful review and insightful feedback.

Seeking Different Fairness Criteria

The potential for our method to be adapted based on different fairness criteria, going beyond our notion of selectively equalized coverage, is indeed both intriguing and promising. Although exploring those questions goes beyond the immediate scope of this paper, we hope that others will be inspired to improve and build upon our work in this direction. We will definitely add this suggestion in the revised manuscript.

Classification with Ordered Labels

In our current framework, we have focused on predicting categorical (unordered) labels. If the labels are ordered, an easy modification of our method would require only a small change to Equation (8). Specifically, when the target variables are ordered labels (say level 1 $<$ level 5), then $\hat{C}(X_{n+1})$ becomes the discrete convex hull of all its components on the right-hand side in Equation 8. Because the prediction set resulting from taking unions will be a subset of the prediction set resulting from taking discrete convex hulls, the new prediction set will automatically satisfy the adaptive equalized coverage defined in Equation (3). An intriguing question, which may be investigated in future work, is whether it is possible to devise a better approach for ordinal labels. Thank you for this helpful comment. We will include this discussion in the revised paper.

Thank you for your detailed review, which allows us to clarify key points and address potential misunderstandings. We believe these clarifications will enhance the paper's accessibility.

Clarification on Method Aims

While other reviewers have praised the paper for its clarity, we appreciate the opportunity to refine our explanations and address your concerns. Specifically, we would like to clarify the role of the attribute selection component in our method, and the reason why we provide formal guarantees for the coverage of the prediction sets rather than for the "correctness" of the selection procedure.

This paper addresses the problem of constructing prediction sets with guaranteed coverage conditional on adaptively selected sensitive attributes. As you noted, our goal is to bridge the gap between existing approaches for marginal and group-conditional conformal prediction, finding a practical balance between efficiency and fairness.

To obtain reliable inferences and approximately maximize conditional coverage, our method seeks to identify the attribute (or attributes) most likely to result in significant under-coverage under a standard (marginal) conformal inference approach. The specific selection algorithm proposed in this paper has demonstrated strong practical performance, as evidenced by our numerical experiments (see Figure 4 and the new Figure 2 in the PDF supplement accompanying this response). However, the core ideas of our method are flexible enough to accommodate different selection algorithms. In the revised manuscript, we will better highlight this flexibility.

A consequence of this flexibility and "assumption-lean" setup is that establishing formal guarantees about the selection of the "correct" attribute would be challenging and somewhat limiting. It would require stronger assumptions, and it would necessitate a theoretical analysis heavily dependent on the specific implementation details of the selection algorithm. While this may be an interesting direction for further research, potentially strengthening the connection to Cherian and Candès (2023), it falls outside the scope of this paper.

Impact of Calibration Sample Size

Constructing informative prediction sets with high conditional coverage is more challenging with smaller sample sizes. This is an inherent challenge, not a specific limitation of our method, and it explains why our experiments focus on comparing the performance of our method against several benchmarks across various sample sizes. These experiments demonstrate that our method consistently performs well across all sample size scenarios. For detailed results, see Figures 3–5 in the paper and the new Figures 1–3 in the PDF supplement accompanying this response.

For example, in the experiments pf Figures 3 and 4, when the sample size is as small as 200, it is inherently challenging to: (1) fit an accurate predictive model, (2) assess conditional coverage, (3) and reliably identify the sensitive attribute associated with the lowest coverage. This is reflected by the relatively large size of the prediction sets output by all methods and by the relatively large discrepancies between the nominal and empirical conditional coverage levels. Nevertheless, our method manages to frequently select the "correct" sensitive attribute, achieving significantly higher conditional coverage compared to the standard "marginal" benchmark, with only a slight increase in prediction set sizes. Further, as the sample size increases, our method becomes highly effective at identifying the attribute with the lowest conditional coverage, as illustrated in Figure 4. This allows our method to achieve high conditional coverage with relatively small prediction sets. Overall, these experiments demonstrate that our method offers distinct advantages over existing approaches in both large-sample and small-sample settings.

Applicability and Computational Cost

Our proposed AFCP method is quite broadly applicable and can be efficiently implemented in many classification settings where the number of labels is not exceedingly large. Natural applications include predicting recidivism risks, determining graduation classes, and addressing binary classification problems such as spam detection and credit default risk assessment.

However, in scenarios where the number of possible classes is extremely high, it is true that the computational cost of our method may become a limiting factor. While addressing this issue is beyond the scope of this paper, we believe that extending our method to accommodate extreme classification tasks presents valuable opportunities for future research. In the revision, we will highlight these opportunities and cite relevant works in the conformal inference literature, such as [1]. These references will provide additional context and potential inspiration for future developments.

Reference: [1]"Class-Conditional Conformal Prediction with Many Classes." Ding et. al., NeurIPS 2023.

Clarifications on Figure 5

The behavior observed in Figure 5 can be easily explained. The horizontal axis represents the cumulative sample size, which includes both training and calibration samples. As the cumulative sample size increases, more data becomes available to train a more accurate predictive model. This increased accuracy explains why the conditional coverage for Occupation 1 improves while the average prediction set size decreases: the model becomes more precise for all individuals, including those most affected by algorithmic bias.

The main takeaway from Figure 5 is that our method consistently provides relatively informative and reliable predictive inferences compared to other conformal inference approaches, regardless of the amount of available data or the varying accuracy of the underlying machine learning model. Note that the model varies for different sample sizes but remains the same for all conformal inference methods, ensuring a fair comparison.

Thank you for your detailed review and constructive feedback. We have addressed your questions and concerns point-by-point below.

Additional experiments

Might you have missed some experiments described in the Appendix and mentioned in Section 3.4? We will highlight these experiments more clearly in the main text. In any case, following your suggestion, we have also conducted new experiments using the Correctional Offender Management Profiling for Alternative Sanctions (COMPAS) dataset.

Experiments in the Appendix. In addition to using the two datasets described in the main paper (one synthetic dataset and the nursery data), we had conducted experiments using an additional synthetic dataset (Appendix A7.2.2) and a common benchmark dataset, the Adult Income Dataset (Appendix A7.2.3). The experiments with the income data also include an AFCP extension that allows for the selection of multiple sensitive attributes. This extension is referred to as the "APCF+" method (depicted by the green lines) and is presented in Figures A24–A33. We will better highlight these experiments in the revised paper.

New experiments with COMPAS data. The COMPAS dataset is used for multi-class classification tasks, predicting the risk of recidivism across three categories: 'High,' 'Medium,' and 'Low.' As illustrated in the new Figures 1-2 in the attached PDF document, these additional experiments consistently demonstrate that our AFCP method outperforms other benchmarks. Specifically, it achieves higher conditional coverage than the Marginal method and, on average, produces smaller prediction sets than the Exhaustive and Partial methods. These results are consistent with those presented in the paper and will be includes in the revised paper. Thank you!

Comparisons between AFCP and AFCP1

Both AFCP and AFCP1 outperform benchmark approaches with small sample sizes, excelling in different areas. AFCP is better suited for scenarios where there is uncertainty about the presence of significant algorithmic bias. On the other hand, AFCP1 is more effective when there is prior knowledge that at least one attribute may be biased. This distinction will be clarified in the revised paper.

In Figure 3, where one group (Color - Blue) is consistently biased, AFCP1 achieves slightly higher conditional coverage than AFCP. While AFCP shows slight undercoverage for the blue group with small sample sizes, it still performs better than the Marginal approach.

AFCP's occasional inability to select a sensitive attribute with small sample sizes reflects the inherent challenges of small datasets rather than a flaw in the method. When the method does not select an attribute, it often indicates a lack of sufficient evidence of algorithmic bias, making it reasonable to calibrate the prediction sets only for marginal coverage.

Comparison Between AFCP and the Exhaustive Approach

Our AFCP method offers advantages over the Exhaustive approach, especially when the sample size is small and the specific attributes indicating biased groups are not known beforehand.

For instance, in a dataset with five binary attributes where only two are significantly associated with algorithmic bias, an Exhaustive approach would have to consider all five attributes or all combinations of two attributes to ensure valid coverage. This process is inefficient. In contrast, our method can identify the two most relevant attributes in a data-driven way. It then focuses on calibrating the prediction sets within the subgroups formed by these attributes.

Impact of Calibration Sample Size

We are not completely sure about the meaning of "restricted calibration sample" in your question, but we will interpret it as the number of calibration samples belonging to the biased group identified by the selected attribute. Please correct us if this is not what you meant.

In general, larger sample sizes make it intrinsically easier to identify (and thereby enable mitigating) significant algorithmic biases. Conversely, if the sample size within any group is small, it is more difficult to estimate the coverage within that group. This can result in our method selecting the “wrong” sensitive attribute. However, despite this unavoidable difficulty, the experiments demonstrate that our method performs well relative to other approaches both in small-sample and in large-sample settings.

In particular, Figures 3 and 4 study the performance of our method as a function of the total number of samples in the training and calibration data. From these two plots we can see that when the sample size is as small as 200, it is challenging to select the true attribute because the data is subject to greater variability. Nevertheless, our method is able to select the “correct” attribute often enough to obtain informative prediction sets with significantly higher conditional coverage compared to the marginal approach.

Figure 4 shows that, as the sample size increases, it becomes more likely for our method to select the correct sensitive attribute, as anticipated. The new COMPAS experiments we conducted following your suggestion demonstrate consistent behavior and confirm the practical advantages of our method.

To better investigate the effect of “restricted” sample size for the biased group associated with the attribute selected by our method, we counted the number of data points in the protected group for each experiment and averaged the results over 100 independent experiments. The results are plotted in the new Figure 3 in the attached PDF document. Please let us know if this answers your question.

Clarity and Typos

We will fix the typos and make the clarifications you suggested. Thank you!

I thank the authors for the detailed response. I will list some comments and questions I have below:

1. Thank you for the additional experiments. Feel free to correct me if I'm missing something, but it seems the COMPAS dataset has three classes. I am not sure if this is a good setup to study coverage -- e.g. average size is <=2 in Fig 1. How informative would coverage be in this case compared to accuracy? That said, I acknowledge the results.

2. "restricted calibration sample" is referred from the paper (e.g., l203)

Thank you for your time and effort in reviewing our paper and providing constructive feedback. Please find our responses below.

Computational Complexity Analysis

As (perhaps too) briefly mentioned in Section 1.4, Appendix A6 provides a detailed computational complexity analysis for implementing our algorithms for either a single test sample or multiple test samples. Is this the information you were looking for? We will make the reference to this analysis clearer in the camera-ready version.

Notably, our AFCP methods can be efficiently implemented for multiple test samples using a shortcut. Specifically, the identification of each subgroup in the calibration set does not rely on the test sample and can be reused to calculate group-wise FPRs and miscoverage rates for different test samples. For instance, this shortcut reduces the computational complexity of the AFCP method from $\mathcal{O}(mn\log n + nKMm)$ to $\mathcal{O}(n\log n + nm + MK(n + m))$ in outlier detection settings, where $n$ is the calibration set size, $m$ is the number of test samples, $K$ is the total number of sensitive attributes, and $M$ is the maximum count of groups across all attributes.

Impact of Small Sample Sizes

Although any attribute selection procedure may be less stable and effective with small sample sizes, we see this as an inherent challenge of small data sets rather than a flaw of our method. As mentioned in response to another comment, future work could explore the performance of our method in combination with different attribute selection procedures, as it is possible that alternative approaches may perform better in different settings, including with small sample sizes. However, the empirical performance of our AFCP method, as currently implemented, already surpasses that of other benchmark methods applied to the same data, in both large-sample and small-sample settings.

For instance, in the experiments of Figures 3 and 4, it is challenging to accurately identify the attribute associated with significant algorithmic bias when the sample size is as small as 200. However, AFCP manages to select the correct attribute frequently enough to achieve significantly higher conditional coverage compared to the Marginal method, without substantially increasing the average prediction set size. Figure 4 further illustrates this behavior, showing the selection frequency of each attribute. As the sample size increases, our method begins to consistently select the correct attribute in all instances.

These findings align with new experiments based on the COMPAS dataset, summarized in the attached one-page PDF.

We will incorporate these explanations into the revised paper to emphasize the advantages of our methods with small sample sizes. Thank you for your comment!

Simultaneous Selection of Multiple Attributes

The appendix of our paper describes variations of our AFCP method that are designed to select and protect multiple attributes simultaneously. Specifically, in Appendix A2, we describe AFCP with multiple selected attributes in the multi-class classification setting, and in Appendix A4.3, we detail AFCP with multiple selected attributes in the outlier detection setting. Appendix 7.2.3 presents experimental results when multiple attributes can be selected using the real-world Adult Income Data. We will strive to better highlight these extensions of our method in the revised paper.

Additional Experiments with Real Datasets

Our proposed method is broadly applicable and can be efficiently applied for a variety of classification and outlier detection tasks. In this paper and appendices, we demonstrated its performance using two synthetic datasets and two real-world datasets. To supplement those results, in response to your feedback and the feedback of other reviewers, we have also conducted new experiments using the widely studied COMPAS dataset. The results obtained with the COMPAS dataset are summarized in the new Figures 1-3 in the attached one-page PDF document. These additional experiments lead to conclusions that are qualitatively similar to those of the previous experiments. However, since this is a well-studied and interesting data sets, we think it may be valuable to include these new results in the revised paper.

Regarding the applicability of our method to imbalanced data, please note that the new experiment on COMPAS data for recidivism prediction, for example, involve imbalanced data, with roughly 10% of samples having the response label "High", 20% having the label "Medium", and 70% having the label "Low".

Alternative Attribute Selection Procedures

Thank you for this thoughtful question. While the underlying ideas of our method are indeed flexible enough to incorporate attribute selection procedures that go beyond those considered in this paper—a strength we will emphasize more in the revision—we believe that delving into the subtle empirical trade-offs associated with different selection algorithms is beyond the scope of this paper. We hope that our work will inspire future research to explore this question further.

Additional References

Following your advice, we will include more references to recent works on robust conformal inference under distribution shift. Although these works address different problems and take different perspectives, they are sufficiently related to merit mention in Section 1.5 (Related Works). The additional page allowed in the camera-ready manuscript will enable us to briefly discuss these references without sacrificing other content. We believe this addition will provide broader context on recent trends and highlight opportunities for integrating ideas in future research. Thank you for this helpful suggestion!