Conformal Classification with Equalized Coverage for Adaptively Selected Groups

Authors: yanfei  zhou
matteo  sesia
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 10:18:14

Abstract: This paper introduces a conformal inference method to evaluate uncertainty in classification by generating prediction sets with valid coverage conditional on adaptively chosen features. These features are carefully selected to reflect potential model limitations or biases. This can be useful to find a practical compromise between efficiency---by providing informative predictions---and algorithmic fairness---by ensuring equalized coverage for the most sensitive groups. We demonstrate the validity and effectiveness of this method on simulated and real data sets.

Main paper: 
 introduction 1.uncertainty, fairness, and efficiency in machine learning: 
 Increasingly sophisticated machine learning (ML) models, like deep neural networks, are revolutionizing decision-making in many high-stakes domains, including medical diagnostics [1] , job screening [2] , and recidivism prediction [3, 4] . However, serious concerns related to uncertainty quantification [5, 6] and algorithmic fairness [7] [8] [9] [10] underscore the need for novel methods that can provide reliable and unbiased measures of confidence, applicable to any model. Uncertainty quantification is crucial because ML models, although effective on average, can make errors while displaying overconfidence [11] . Consequently, in some situations users may lack sufficient warning about the potential unreliability of a prediction, raising trust and safety concerns. A promising solution is conformal inference [12] [13] [14] , which enables converting the output of any model into prediction sets with precise coverage guarantees. These sets reflect the model's confidence on a case-by-case basis, with smaller sets indicating higher confidence in a specific prediction.Algorithmic fairness focuses on the challenges of prediction inaccuracies that disproportionately impact specific groups, often identified by sensitive attributes like race, sex, and age. Among the many sources of algorithmic bias are training data that do not adequately represent the population's heterogeneity and a focus on maximizing average performance. However, fairness is partly subjective and lacks a universally accepted definition [15] , leading to sometimes conflicting interpretations [16] .This complexity makes conformal inference with equalized coverage [17] an appealing approach. Equalized coverage aims to ensure that the prediction sets attain their coverage not only on average for the whole population (e.g., above 90%) but also at the same level within each group of interest. While this does not necessarily imply that the prediction sets will have equal size on average across different groups-since it is possible the predictive model may be more or less accurate for different groups-it objectively communicates the possible limitations of a model. This transparency helps decisionmakers recognize when predictions may be less reliable for specific subgroups, allowing them to either avoid unnecessary actions or adopt more cautious strategies in cases of higher uncertainty, thereby minimizing the potential harm from inaccurate predictions.A limitation of the method developed in [17] for conformal inference with equalized coverage is that it does not scale well to situations involving diverse populations with multiple sensitive attributes. In such cases, it necessitates splitting the data into exponentially many subsets, significantly reducing the effective sample size and leading to less informative predictions. Balancing this trade-off [18] between efficiency-aiming for highly informative predictions with small set sizes-and fairnessensuring unbiased treatment-is challenging and requires novel approaches. This paper introduces a method to address this by providing equalized coverage conditional on carefully chosen features, informed by the model and data. While it cannot guarantee equalized coverage for all sensitive groups, it seeks a reasonable compromise with finite data sets, mitigating significant biases while retaining predictive power.Consider a data set comprising n exchangeable (e.g., i.i.d.) observations Z i for i ∈ D := [n] := {1, . . . , n}, sampled from an arbitrary and unknown distribution P Z . In classification, one can write Z i = (X i , Y i ), where Y i ∈ [L] := {1, . . . , L} is a categorical label and X i ∈ X represents the individual's features, taking values in some space X . As explained below, we will assume these features include some sensitive attributes. Further, we consider a test point Z n+1 = (X n+1 , Y n+1 ), also sampled exchangeably from P Z , and whose label Y n+1 ∈ [L] has not yet been observed.A standard goal for split conformal prediction methods is to quantify the predictive uncertainty of a given "black-box" ML model (e.g., pre-trained on an independent data set) by constructing a prediction set Ĉ(X n+1 ) for Y n+1 , guaranteeing marginal coverage at some desired level α ∈ (0, 1):EQUATIONThis probability is taken over the randomness in Y n+1 and X n+1 , as well as in the data indexed by D.Intuitively, marginal coverage means the prediction sets are expected to cover the correct outcomes for a fraction 1 -α of the population. However, this is not always satisfactory, especially if the miscoverage errors may disproportionately affect individuals characterized by well-defined features.To address these concerns, one might consider feature-conditional coverage, P[Y n+1 ∈ Ĉ(X n+1 ) | X n+1 = x] ≥ 1-α for all x ∈ X . This would ensure consistent coverage for all possible test features X n+1 . However, it is impossible to achieve without additional assumptions, such as modeling the distribution P Z [19] or significantly restricting the feature space X [20] . Given that such assumptions may be unrealistic in real-world settings, exact feature-conditional coverage is typically unachievable.Equalized coverage [17] seeks a practical middle ground between the two extremes of marginal and feature-conditional coverage, focusing on accounting for specific discrete attributes encapsulated by X n+1 . To facilitate the subsequent exposition of our method, it is useful to recall the definition of equalized coverage with the following notation.Let K denote the number of sensitive attributes, and for each k ∈ [K] let M k ∈ N count the possible values of the k-th attribute. Consider a function ϕ : X × {0, 1} K → N d for any subset A ⊆ [K] with |A| = d elements, so that ϕ(x, A) is a vector of length |A| representing the values of all attributes indexed by A for an individual with features x. In the special case where A is an empty set, ϕ returns a constant. If A is a singleton, e.g., A = {k} for some k ∈ [K], then ϕ(x, {k}) ∈ [M k ] denotes the value of the k-th attribute; e.g., someone's academic degree. More generally, ϕ(x, {k, l})∈ [M k ] × [M l ], for any distinct k, l ∈ [K],denotes the joint values of two attributes, characterizing a smaller group, such as "males with a bachelor's degree.".When multiple sensitive attributes are involved, i.e., K > 1, the concept of equalized coverage introduced by [17] can be naturally extended to exhaustive equalized coverage, defined as:EQUATIONIn words, this says Ĉ(X n+1 ) has valid coverage conditional on all K sensitive attributes. Prediction sets satisfying (2) can be obtained by applying the standard conformal calibration method separately within each of the M = K k=1 M k groups characterized by a specific combination of the protected attributes represented by ϕ(X i , [K]); see Appendix A1 for details. However, a downside of this approach is that the calibration subsets may be too small if M is large, leading to uninformative predictions for even moderate values of K. This limitation forms the starting point of our work.In practice, for a given model and data set, different groups may not exhibit the same need for rigorous equalized coverage guarantees (2) , as conformal predictions may be able to approximately achieve the desired coverage even without explicit constraints. Algorithmic bias typically affects only a minority of the population, so standard prediction sets with marginal coverage (1) may approximately satisfy (2) for most groups. Therefore, we propose Adaptively Fair Conformal Prediction (AFCP), a new method that efficiently identifies and addresses groups suffering from algorithmic bias in a data-driven way, adjusting their prediction sets to equalize coverage without sacrificing informativeness.AFCP involves two main steps. First, as sketched in Figure 1 , it carefully selects a sensitive attribute Â(X n+1 ) ∈ {∅, {1}, . . . , {K}}, based on X n+1 and the data in D. Although AFCP can be extended to select multiple attributes, we begin by focusing on this simpler version for clarity. Intuitively, AFCP searches for the attribute corresponding to the group most negatively affected by algorithmic bias. It may also opt to select no attribute ( Â(X n+1 ) = ∅) in the absence of significant biases.Figure 1 : Schematic visualization of the automatic sensitive attribute selection carried out by our Adaptively Fair Conformal Prediction (AFCP) method. This method is designed to find the attribute corresponding to the group most negatively affected by algorithmic bias, on a case-by-case basis.Next, AFCP constructs a prediction set Ĉ(X n+1 ) for Y n+1 that guarantees the following notion of adaptive equalized coverage at the desired level α ∈ (0, 1):EQUATIONIn words, this tells us Ĉ(X n+1 ) is well-calibrated for the groups defined by the selected attribute Â(X n+1 ). It is worth highlighting the key distinctions between (3) and the existing notions of coverage reviewed above. On the one hand, if AFCP identifies no significant bias, selecting Â(X n+1 ) = ∅, then (3) reduces to marginal coverage (1) , following the convention that ϕ(X n+1 , ∅) is a constant. On the other hand, exhaustive equalized coverage (2) would correspond to simultaneously selecting all possible sensitive attributes instead of only that identified by Â(X n+1 ). To clarify the terminology, in this paper we will say that an attribute is sensitive if it may identify a group affected by algorithmic bias. By contrast, a protected attribute is one for which equalized coverage is explicitly sought.Figure 2 illustrates this intuition through a simulated example. In this scenario, we generate synthetic medical diagnosis data, considering six possible diagnosis labels, and designate race, sex, and age group as potentially sensitive attributes alongside other demographic factors. Notably, the female group, identified by sex, is characterized by fewer samples and higher algorithmic bias, resulting in marginal prediction sets with low group-conditional coverage. By contrast, the model leads to no significant disparities across races and age groups in this dataset.For two example patients from the critical group, the standard marginal prediction sets fail to cover the true label. Conversely, sets calibrated for exhaustive equalized coverage are too conservative to be informative. By contrast, AFCP generates prediction sets that are both efficient and fair.Without additional sample splitting, which would be inefficient, constructing informative prediction sets that satisfy ( 3) is challenging due to potential selection bias from using the same data for attribute selection and conformal calibration. This paper presents a novel solution to address this challenge.Figure 2 : Prediction sets constructed with different methods for patients in groups negatively affected by algorithm bias. Our method (AFCP) is designed to provide informative prediction sets that are well-calibrated conditional on the automatically identified critical sensitive attribute.Section 2 presents our AFCP method, focusing on the special case in which at most one sensitive attribute may be selected. Section 3 demonstrates the empirical performance of AFCP on synthetic and real data. Section 4 discusses some limitations and suggests ideas for future work.Additional content is presented in the Appendices. Appendix A1 reviews relevant details of existing approaches. Appendices A2 and A3 present two extensions of our method, respectively enabling the selection of more than one sensitive attribute and providing valid coverage also conditional on the true test label; both extensions involve distinct technical challenges. Additionally, a variation of AFCP designed for outlier detection tasks is detailed in Appendix A4. Appendix A5 contains all mathematical proofs. Appendix A6 explains how to implement our method efficiently and studies its computational cost. Appendix A7 describes the results of numerous additional experiments.Conformal inference is a very active research area, with numerous methods addressing diverse tasks, including outlier detection [21] [22] [23] , classification [24] [25] [26] [27] [28] , and regression [29] [30] [31] . Overcoming the limitations of the standard marginal coverage guarantees (1) is a main interest in this field.Some works have proposed conformity scores designed to seek high feature-conditional coverage while calibrating prediction sets for marginal coverage [27, 30] . Others attempt to mitigate overconfidence while training the ML model [32, 33] , and several have developed calibration methods for non-exchangeable data, accounting for possible distribution shifts [34] [35] [36] [37] [38] . These works are complementary to ours, as we focus on guaranteeing a new adaptive notion of equalized coverage.In addition to [17] , several other works have considered constructing prediction sets adhering to various notions of equalized coverage and have empirically investigated the performance of conformal predictors in this regard [39] . In the context of regression, [40] and [41] proposed strategies to enhance conditional coverage given several protected attributes, but they targeted a different notion of equalized coverage designed for continuous outcomes. In classification, a classical approach to move beyond marginal coverage is label-conditional coverage, where the "protected" groups are defined not based on the features X n+1 but by the label itself, Y n+1 [42] [43] [44] . As explained in Appendix A3, the method proposed in this paper can also be extended to provide label-conditional coverage.More closely related to the notion of equalized coverage [17] are the works of [45, 46] , which differ from ours as they do not consider the automatic selection of the sensitive groups. To tackle a related challenge due to unknown biased attributes, [47] studied how to identify unfairly treated groups by establishing a simultaneously valid confidence bound on group-wise disparities. In principle, their approach can be integrated within the selection component of our method. Very recently, [48] proposed an elegant method to obtain valid conformal prediction sets for adaptively selected subsets of test cases. While their perspective aligns more closely with ours, their approach and focus differ as they study different selection rules not specifically aimed at mitigating algorithmic bias.2 Method 
automatic attribute selection: 
 Given a pre-trained classifier, an independent calibration data set D, and a test point Z n+1 = (X n+1 , Y n+1 ) with an unknown label Y n+1 , we will select (at most) one sensitive attribute, Â(X n+1 ) ∈ {∅, {1}, . . . , {K}}, according to the following leave-one-out procedure.For each y ∈ [L], imagine Y n+1 is equal to y, and define an augmented calibration set D ′ y := D ∪ {(X n+1 , y)}. For each i ∈ [n + 1], define also the leave-one-out set D ′ y,i := D ′ y \ {(X i , Y i )}, with y acting as a placeholder for Y n+1 . Then, for each i ∈ [n + 1], we construct a conformal prediction set Ĉloo y (X i ) for Y i given X i by calibrating the classifier using the data in D ′ y,i . Any method can be applied for this purpose, although it may be helpful for concreteness to focus on employing the standard approach seeking marginal coverage (1) using the adaptive conformity scores proposed by [27] . Let E y,i denote the binary indicator of whether Ĉloo y (X i ) fails to cover Y i :EQUATIONAfter evaluating E y,i for all i ∈ [n + 1], we will assess the leave-one-out miscoverage rate for the worst-off group identified by each sensitive attribute k ∈ [K]. That is, we evaluateδ y,k := max m∈[M k ] n+1 i=1 E y,i • 1{ϕ(X i , {k}) = m} n+1 i=1 1{ϕ(X i , {k}) = m} .Intuitively, δ y,k denotes the maximum miscoverage rate across all groups identified by the k-th attribute. Large values of δ y,k suggest that the k-th attribute may be a sensitive attribute corresponding to at least one group suffering from algorithmic bias.To assess whether there is evidence of significant algorithmic bias, we can perform a statistical test for the null hypothesis that no algorithmic bias exists. Note that this test can be heuristic since it does not need to be exact for our method to rigorously guarantee (3) . Therefore, we do not need to carefully consider the assumptions underlying this test. As a useful heuristic, we define:EQUATIONand carry out a one-sided t-test for the null hypothesis H 0 : qy ≤ α against H 1 : qy > α.If H 0 is rejected (at any desired level, like 5%), we conclude there exists a group suffering from significant algorithmic bias, and we identify the corresponding attribute throughEQUATIONOtherwise, we set Â(X n+1 , y) = ∅, which corresponds to selecting no attribute. See Algorithm 1 for an outline of this procedure, as a function of the placeholder label y.After repeating this procedure for each y ∈ [L], the final selected attribute Â(X n+1 ) is:EQUATIONTherefore, an attribute is selected if and only if it is consistently flagged by our leave-one-out procedure for all values of the placeholder label y ∈ [L]. This approach minimizes the potential arbitrariness due to the use of a placeholder label and is necessary to guarantee that our method constructs prediction sets achieving (3), as discussed in the next section.Before explaining how our method utilizes the selected sensitive attribute obtained in (7) to construct prediction sets satisfying (3), we pause to make two remarks. First, as long as n is large enough, Â(X n+1 , y) is quite stable with respect to both X n+1 and y, as each of these variables plays a relatively small role in determining the leave-one-out miscoverage rates. Therefore, the selected attribute Â(X n+1 ) given by ( 7) is also quite stable for different values of X n+1 . This stability will be demonstrated empirically in Section 3. Second, despite its iterative nature, our method can be implemented efficiently; see Appendix A6. Further, if n is very large, our method could be streamlined using cross-validation instead of a leave-one-out approach.Algorithm 1 Automatic attribute selection using a placeholder test label. := D ∪ {(X n+1 , y)}. 5: for i ∈ [n + 1] do 6: Pretend that (X i , Y i ) is the test point and D ′ y \ {(X i , Y i )} is the calibration set. 7:Construct a conformal prediction set Ĉloo y (X i ) for Y i .Evaluate the miscoverage indicator E y,i using (4). 9: end for 10: Perform a one-sided test for H 0 : qy ≤ α vs. H 1 : qy > α, with qy defined as in (5) . 11: Select the attribute Â(X n+1 , y) using ( 6) if H 0 is rejected, else set Â(X n+1 , y) = ∅. 12: Output: Â(X n+1 , y), either a selected sensitive attribute or an empty set.After evaluating Â(X n+1 , y) by applying Algorithm 1 with placeholder label y for Y n+1 for all y ∈ [L], and selecting either an empty set or a single attribute Â(X n+1 ) using ( 7), AFCP constructs an adaptive prediction set for Y n+1 that satisfies (3) as follows.First, it constructs a marginal conformal prediction set Ĉm (X n+1 ) targeting (1), by applying the standard approach reviewed in Appendix A1. Then, for each y ∈ [L], it constructs a conformal prediction set Ĉ(X n+1 , Â(X n+1 , y)) with equalized coverage for the group identified by attribute Â(X n+1 , y), as if it had been fixed. This is achieved by applying the standard marginal method based on a restricted calibration sample indexed by {i ∈[n] : ϕ(X i , Â(X n+1 , y)) = ϕ(X n+1 , Â(X n+1 , y))}; see Algorithm A1 in Appendix A1 for further details. Therefore, note that ϕ(X i , Â(X n+1 , y)) becomes equivalent to Ĉm (X n+1 ) if Â(X n+1 , y) = ∅.Finally, the AFCP prediction set for Y n+1 is given by:EQUATIONSee Algorithm 2 for an outline of this procedure.Note that the AFCP set Ĉ(X n+1 ) given by ( 8) always contains the marginal set Ĉm (X n+1 ); this is essential to prove the validity of our approach. Second, in practice the selection Â(X n+1 , y) tends to be very consistent for different values of the placeholder label y, as long as the sample size n is large enough; therefore, the union in (8) will typically not lead to a very large prediction set.Algorithm 2 Adaptively Fair Conformal Prediction (AFCP). Select an attribute Â(X n+1 , y) by applying Algorithm 1 with placeholder label y.Construct Ĉ(X n+1 , A) by applying Algorithm A1 with the attribute A = Â(X n+1 , y). 6: end for 7: Construct Ĉm (X n+1 ) by applying Algorithm A1 without protected attributes. 8: Output: selected attribute Â(X n+1 ) given by (7) and prediction set Ĉ(X n+1 ) given by (8) .The following result, proved in Appendix A5, establishes that the prediction sets Ĉ(X n+1 ) output by AFCP guarantee adaptive equalized coverage (3) with respect to the adaptively selected attribute Â(X n+1 ). It is worth emphasizing this result is not straightforward and involves an innovative proof technique to address the lack of exchangeability introduced by the adaptive selection step.Theorem 1. If {(X i , Y i )} n+1i=1 are exchangeable, the prediction set Ĉ(X n+1 ) and the selected attribute Â(X n+1 ) output by Algorithm 2 satisfy the adaptive equalized coverage defined in (3). 
setup and benchmarks: 
 This section demonstrates the empirical performance of AFCP, focusing on the implementation described in Section 2, which selects at most one sensitive attribute. Our method is compared with three existing approaches, which utilize the same data, ML model, and conformity scores but produce prediction sets with different guarantees. The first is the marginal benchmark, which constructs prediction sets guaranteeing (1) by applying Algorithm A1 without protected attributes. The second is the exhaustive equalized benchmark, which constructs prediction sets guaranteeing (2) by applying Algorithm A1 with all K sensitive attributes simultaneously protected. The third is a partial equalized benchmark that separately applies Algorithm A1 with each possible protected attribute k ∈ [K], and then takes the union of all such prediction sets. This is an intuitive approach that can be easily verified to provide a coverage guarantee intermediate between ( 2) and (3), namely:EQUATIONHowever, we will see that these prediction sets are often still too conservative in practice.In addition, we apply a variation of AFCP that always selects one sensitive attribute, regardless of the outcome of the significance test. This method is denoted as AFCP1 in our experiments.For all methods considered, the classifier is based on a five-layer neural network with linear layers interconnected via a ReLU activation function. The output layer uses a softmax function to estimate the conditional label probabilities. The Adam optimizer and cross-entropy loss function are used in the training process, with a learning rate set at 0.0001. The loss values demonstrate convergence after 100 epochs of training. For all methods, the miscoverage target level is set at α = 0.1.We generate synthetic classification data to mimic a medical diagnosis task with six possible labels: Skin cancer, Diabetes, Asthma, Stroke, Flu, and Epilepsy. The available features include three sensitive attributes-Age Group, Region, and Color-and six additional non-sensitive covariates.Color is categorized as Blue or Grey, with 10% and 90% marginal frequencies, respectively. The Age Group is cyclically repeated as < 18, 18 -24, 25 -40, 41 -65, > 65, and Region is sampled from an i.i.d. multinomial distribution across {West, East, North, South} with equal probabilities. The six non-sensitive features are i.i.d. random samples from a uniform distribution on [0, 1]. For simplicity, Color is denoted as X 0 and the first non-sensitive feature as X 1 . Conditional on X, the label Y is generated based on a decision tree model that depends only on X 0 and X 1 , as detailed in Appendix A7. This model is designed so that the diagnosis label for individuals with Color equal to Blue is intrinsically harder to predict, mimicking the presence of algorithmic bias.Figure 3 shows the performance of all methods as a function of the total sample size, ranging from 200 to 2000. In each case, 50% of the samples are used for training and the remaining 50% for calibration. Results are averaged over 500 test points and 100 independent experiments.While the marginal benchmark produces the smallest prediction sets on average, it leads to significant empirical undercoverage within the Blue group. In contrast, the exhaustive benchmark, which achieves the highest coverage overall, tends to lead to overly conservative and thus uninformative prediction sets, especially for the Blue group. The partial benchmark, though less conservative than the exhaustive method, still generates prediction sets that are too large when the sample size is small.Our AFCP method and its simpler variation, AFCP1, not only achieve valid coverage for the Blue group but do so with prediction sets that, on average, are not much larger than the marginal ones. AFCP1 is slightly more robust than AFCP when the sample size is very small, as it never fails to select a sensitive attribute. This is advantageous in scenarios where we know there is a sensitive attribute worth equalizing coverage for, though this may not always be the case in practice. See Figure A1 and Table A1 for detailed results with standard errors.Figure 4 provides additional insight into our method's performance by plotting the selection frequencies of each sensitive attribute as a function of sample size, within the same experiments described in Figure 3 . These results show that our method behaves as anticipated. When the sample size and algorithmic bias are both small, AFCP shows more variability in selecting the sensitive attribute, often selecting no attributes. However, as the sample size grows and the undercoverage affecting the Blue group becomes more pronounced, AFCP consistently selects Color as the most sensitive attribute, correctly identifying the main manifestation of algorithmic bias in these data. and Tables A5-A8 study the performance of an extension of our method that also provides valid coverage conditional on the true label of the test point.We apply AFCP and its benchmarks to the open-domain Nursery data set [49] , which was derived from a hierarchical decision model originally developed to rank applications for nursery schools for social science studies. The data encompass 12,960 instances with eight categorical features: Parents' occupation (3 levels), Child's nursery (5 levels), Family form (4 levels), Number of children (1, 2, 3, or more), Housing conditions (3 levels), Financial standing (2 levels), Social conditions (3 levels), and Health status (3 levels). These features are used to predict application ranks across five categories. The variables "Parents' occupation", "Number of children", "Financial standing", "Social conditions", and "Health status" are marked as possible sensitive attributes.To prepare for model training, we executed several pre-processing steps. First, two instances labeled "recommend" were removed due to the minimal occurrence of this outcome label. Subsequently, we utilized the LabelEncoder function in the sklearn Python package to numerically encode all features and labels. To make the problem more interesting and allow control over the strength of algorithmic bias, we added independent, uniformly distributed noise to the labels of samples with Parents' occupation in the first category, rounding these perturbed labels to the nearest integer. This makes the group corresponding to the first category of Parents' occupation intrinsically more unpredictable and hence more prone to algorithmic bias. To enhance the challenge of making accurate predictions for this group, it was further down-sampled to 10% of its original size. The experiments with the real-world Adult Income data also include an AFCP extension that allows for the selection of multiple sensitive attributes at the same time.Constructing informative prediction sets that achieve high conditional coverage is inherently more challenging when dealing with smaller sample sizes. By experimenting with different sample sizes, we demonstrate that our AFCP method consistently performs well across different scenarios. For instance, in the experiments depicted in Figures 3 4 , when the sample size is as small as 200, it is difficult to fit an accurate predictive model, assess conditional coverage, and reliably identify the sensitive attribute associated with the lowest coverage. This difficulty is reflected in the relatively large sizes of the prediction sets produced by all methods and the substantial discrepancies between the nominal and empirical conditional coverage. Despite these challenges, our method often succeeds in selecting the correct sensitive attribute, achieving significantly higher conditional coverage compared to the Marginal benchmark, with only a slight increase in average prediction set size.Moreover, as the sample size increases, our method becomes highly effective at identifying the attribute associated with the lowest conditional coverage, as illustrated in Figure 4 . Consequently, our method is able 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.Both AFCP and AFCP1 outperform the benchmark approaches when applied to datasets with small sample sizes, each excelling in different scenarios. AFCP is better suited to situations where there is uncertainty regarding the presence of significant algorithmic bias, while AFCP1 is more effective when prior knowledge suggests that at least one attribute may be biased. For example, in Figure 3 , which illustrates a case where one group (Color-Blue) is consistently biased, AFCP1 achieves slightly higher conditional coverage than AFCP. While AFCP exhibits slight undercoverage for the blue group with small sample sizes, it still outperforms the Marginal approach. The occasional inability of AFCP to select a sensitive attribute in small samples reflects the inherent challenges posed by limited datasets. When the method does not select an attribute, it often signifies a lack of sufficient evidence of algorithmic bias, making it reasonable to calibrate the prediction sets solely for marginal coverage. 
discussion: 
 This paper presents a practical and statistically principled method to construct informative conformal prediction sets with valid coverage conditional on adaptively selected features. This approach balances efficiency and equalized coverage, which may be particularly useful in applications involving multiple sensitive attributes. While we believe it offers substantial benefits, a potential limitation of this method is that it does not always identify the most relevant sensitive attribute, particularly when working with limited sample sizes. Nevertheless, our empirical results are quite encouraging, demonstrating that AFCP effectively mitigates significant instances of algorithmic bias when the sample size is adequate. Moreover, our method is flexible, allowing for the integration of prior knowledge about which sensitive attributes might require protection against algorithmic bias.This paper creates several opportunities for further work. Future research could focus on theoretically studying the conditions under which our method can be guaranteed to select the correct sensitive attribute with high probability. Additionally, future extensions might explore implementing different attribute selection procedures, such as those inspired by [47] -within our flexible AFCP framework to delve into the subtle trade-offs associated with different selection algorithms. Moreover, adapting our approach to accommodate different fairness criteria by adaptively adjusting the coverage rate target for each subgroup is another promising area of study. Extending our method to more efficiently handle scenarios with an extremely high number of possible classes is also worthwhile, potentially drawing inspiration from [43] . Furthermore, investigating extensions for classification tasks where the target variable is ordered could be both intriguing and practically useful. In such cases, a naive modification of our method would involve utilizing the discrete convex hull of all components instead of unions of subintervals on the right-hand side of Equation (8) . However, developing a more refined approach would be a valuable contribution for future work. Future extensions of our work could focus on adapting to distributional shifts or enhancing the robustness and efficiency of our method under adversarial attacks or contaminated data, potentially drawing connections with [52] [53] [54] [55] [56] . Finally, extending our method to accommodate regression tasks with continuous outcomes presents additional computational challenges, but potential solutions could be inspired by [33] .The numerical experiments described in this paper were carried out on a computing cluster. Individual experiments, involving 1000 calibration samples and 500 test samples, required less than 25 minutes and 5GB of memory on a single CPU. The entire project took approximately 100 hours of computing time, and did not involve preliminary or failed experiments.Software implementing the algorithms and data experiments are available online at https://github. com/FionaZ3696/Adaptively-Fair-Conformal-Prediction.Algorithm A1 outlines the standard approach for constructing conformal prediction sets with equalized coverage with respect to a fixed list of protected attributes [17] . In the special case where the list of protected attributes is empty, this method reduces to the standard approach for constructing prediction sets with marginal coverage.Algorithm A1 Conformal classification with equalized coverage for fixed protected attributes. I(X n+1 , A) = {i ∈ [n] : ϕ(X i , A) = ϕ(X n+1 , A)} . 5: for y ∈ [L] do 6:Compute the nonconformity scores Ŝy i for i ∈ I(X n+1 , A) ∪ {(X n+1 , y)} using f .Compute the conformal p-value:ûy (X n+1 ) = 1 + |i ∈ I(X n+1 , A) : Ŝy i ≤ Ŝy n+1 | 1 + |I(X n+1 , A)| .8: end for 9: Construct a prediction set using Ĉ(X n+1 ) = {y ∈ [L] : ûy (X n+1 ) ≥ α}. 10: Output: a prediction set Ĉ(X n+1 ).In the context of outlier detection, Algorithm A2 reviews the standard approach for computing conformal p-values achieving valid false positive rate (FPR) control conditional a fixed list of protected attributes.Algorithm A2 Conformal p-value with equalized FPR for fixed protected attributes.1: Input: calibration data D; test point Z n+1 ; list of protected attributes A; 2: Input: pre-trained one-class classifier f ; pre-defined rule for computing nonconformity scores; 3: Input: nominal level α ∈ (0, 1). 4: Define the calibration subsetI(Z n+1 , A) = {i ∈ [n] : ϕ(Z i , A) = ϕ(Z n+1 , A)} .5: Compute the nonconformity scores Ŝi for i ∈ I(Z n+1 , A) ∪ {Z n+1 } using f . 6: Compute the conformal p-value:û(Z n+1 ) = 1 + |i ∈ I(Z n+1 , A) : Ŝi ≤ Ŝn+1 | 1 + |I(Z n+1 , A)| .7: Output: a conformal p-value û(Z n+1 ).This section introduces an extension of AFCP that enables the selection of more than one sensitive attribute. For simplicity, we focus on the selection of up to two attributes. The methodology for selecting more than two attributes can be extended in a similar manner, as explained later.Given a pre-trained classification model, an independent calibration data set D with size n, and a test point Z n+1 = (X n+1 , Y n+1 ) with an unknown label Y n+1 , Algorithm 1 in Section 2.1 introduces the AFCP component to select one sensitive attribute according to the leave-one-out procedure. Intuitively, selecting two sensitive attributes requires executing Algorithm 1 twice. However, during the second iteration, the sensitive attribute list is restricted to exclude the most critical protected attribute selected in the first round.Specifically, for each placeholder label y ∈ [L], assuming Y n+1 = y, Algorithm 1 is run with all K sensitive attributes for the first iteration to obtain the first selected attribute Â1 (X n+1 , y) ∈ {∅, {1}, . . . , {K}}. If Â1 (X n+1 , y) ̸ = ∅, Algorithm 1 is run again using the sensitive attributes [K]\ Â1 (X n+1 , y) and one can get the second selected attribute Â2 (X n+1 , y) ∈ {∅, {1}, . . . , {K}}\ Â1 (X n+1 , y). Therefore, the identified attributes for test feature X n+1 with placeholder y for the test label is the union of the two Â(X n+1 , y) = Â1 (X n+1 , y) ∪ Â2 (X n+1 , y). This procedure is outlined in Algorithm A3.After repeating this procedure for each y ∈ [L], the final selected attribute Â(X n+1 ) is:EQUATION)Algorithm A3 Two attributes selection using a placeholder test label. Select the second attribute Â2 (X n+1 , y) by applying Algorithm 1 with placeholder label y and sensitive attributes [K] \ Â1 (X n+1 , y). 7: end if 8: Output: Â(X n+1 , y) = Â1 (X n+1 , y) ∪ Â2 (X n+1 , y), which is a set of an empty set, or a set including one or two selected sensitive attribute(s).After selecting a subset of attributes Â(X n+1 ) using (A10), which may be empty, or include one or two attributes, AFCP constructs an adaptive prediction set for Y n+1 that satisfies (3) as follows.First, it constructs a marginal conformal prediction set Ĉm (X n+1 ) targeting (1), by applying Algorithm A1 without protected attributes. Then, for each y ∈ [L], it constructs a conformal prediction set Ĉ(X n+1 , Â(X n+1 , y)) with equalized coverage for the group jointly identified by attributes Â(X n+1 , y). This can be achieved by applying Algorithm A1 with protected attributes Â(X n+1 , y).Lastly, it constructs a conformal prediction set Ĉeq (X n+1 , ℓ) with equalized coverage separately for each protected attribute ℓ ∈ ∪ y∈[L] Â(X n+1 , y), by applying the standard approach in Algorithm A1 on the subsets indexed by {i ∈ [n] : ϕ(X i , {ℓ}) = ϕ(X n+1 , {ℓ})}.Finally, the AFCP prediction set constructed using up to two selected attributes is given as:Ĉ(X n+1 ) = Ĉm (X n+1 ) ∪ ∪ L y=1 Ĉ(X n+1 , Â(X n+1 , y)) ∪ ∪ ℓ∈∪y Â(Xn+1,y)Ĉeq (X n+1 , ℓ) .See Algorithm A4 for an outline of this AFCP extension.Theorem A1. If {(X i , Y i )} n+1i=1 are exchangeable random samples, then the conformal prediction set Ĉ(X n+1 ) and the selected attributes Â(X n+1 ) output by Algorithm A4 satisfy the adaptive equalized coverage defined in (3).Algorithm A4 AFCP with two selected attributes. Select attribute(s) Â(X n+1 , y) by applying Algorithm A3 with placeholder label y.Construct Ĉ(X n+1 , A) by applying Algorithm A1 with protected attribute(s) A = Â(X n+1 , y). 7: end for 8: for ℓ ∈ ∪ y∈[L] Â(X n+1 , y) do 9:Construct Ĉeq (X n+1 , ℓ) by applying Algorithm A1 with protected attribute {ℓ}. 10: end for 11: Construct Ĉm (X n+1 ) by applying Algorithm A1 without protected attributes. 12: Define the final selected attribute(s) Â(X n+1 ) using Equation (A10). 13: Define the final prediction set Ĉ(X n+1 ) using Equation (A11). 14: Output: Â(X n+1 ) and Ĉ(X n+1 ).This section extends the AFCP method with adaptive equalized coverage that is also conditional on the true test label. We focus on the main implementation of AFCP, where it can select up to one sensitive attribute.First, the label conditional counterparts of the marginal coverage, the exhaustive equalized coverage, and the adaptive equalized coverage are defined. The label-conditional counterpart of marginal coverage is defined as:EQUATIONIntuitively, this coverage ensures that the prediction sets constructed are valid for each group with the test label y for all possible values of y ∈ [L]. This coverage offers a stronger assurance than marginal coverage in classification contexts. However, it overlooks scenarios where groups, identified by feature attributes, may suffer adverse effects from prediction biases. To address these concerns, one can aim for label-conditional exhaustive equalized coverage [17] , defined as:EQUATIONAchieving this label conditional exhaustive equalized coverage involves applying the standard conformal classification method (outlined in Algorithm A1) separately within each of the groups characterized by every possible combination of sensitive attributes and test labels. Hence, this approach can become overly conservative when a large number of sensitive attributes or response labels are presented.Our AFCP method strikes a balance between the two approaches to achieve label-conditional adaptive equalized coverage:EQUATIONwhich guarantees that the true test label is contained within the prediction sets with high probability for the groups defined by the selected attribute Â(X n+1 ) and the test label y for every y ∈ [L].Given a pre-trained classification model and an independent calibration data set D with size n, for each placeholder label y ∈ [L] for Y n+1 , the AFCP method with label-conditional adaptive equalized coverage (A14) selects the sensitive attribute Â(X n+1 , y) by simply applying Algorithm 1 using the label-restricted calibration data D y = {i ∈ [n] : Y i = y}. After repeating this process for each y ∈ [L], the final selected attribute Â(X n+1 ) is again given byÂ(X n+1 ) = ∩ y∈[L] Â(X n+1 , y). (A15)After selecting Â(X n+1 , y) by applying Algorithm 1 with placeholder label y based on the labelrestricted calibration data D y = {i ∈ [n] : Y i = y}, and selecting a sensitive attribute Â(X n+1 ), AFCP constructs an adaptive prediction set for Y n+1 that satisfies (A14) as follows.For each y ∈ [L], it firstly construct a conformal prediction set Ĉlc (X n+1 , y) by applying Algorithm A1 using the label-restricted calibration set D y without considering protected attributes. Then, it constructs another conformal prediction set Ĉ(X n+1 , Â(X n+1 , y)) with equalized coverage for the group identified by both the selected attribute Â(X n+1 , y) and label y. This can be achieved by applying Algorithm A1 based on a subset of the calibration samples indexed byI(X n+1 , y) = {i ∈ D y : ϕ(X i , Â(X n+1 , y)) = ϕ(X n+1 , Â(X n+1 , y))}.Lemma A1 shows that, for any given placeholder label, the prediction set constructed in this step satisfies the label conditional adaptive equalized coverage as long as the selected variable using that placeholder label is fixed.Lemma A1. If {(X i , Y i )} n+1i=1 are exchangeable and the selected attribute Â(X n+1 , y) is fixed for some placeholder label y, then, the prediction set Ĉ(X n+1 , Â(X n+1 , y)) constructed by calibrating on I(X n+1 , y) satisfiesP[Y n+1 ∈ Ĉ(X n+1 , Â(X n+1 , y)) | Y n+1 = ỹ, ϕ(X n+1 , Â(X n+1 , y))] ≥ 1 -α, for any ỹ ∈ [L].Lastly, the final AFCP prediction set is obtained by:EQUATIONThe procedures to form AFCP prediction sets with the label-conditional adaptive equalized coverage (A14) is summarized in Algorithm A5.Algorithm A5 AFCP with label-conditional adaptive equalized coverage (A14). Define the label-restricted calibration set D y = {i ∈ [n] : Y i = y}.Select an attribute Â(X n+1 , y) by applying Algorithm 1 with placeholder label y on D y .Construct Ĉ(X n+1 , Â(X n+1 , y)) by applying Algorithm A1 with protected attributes Â(X n+1 , y) on D y .Construct Ĉlc (X n+1 , y) by applying Algorithm A1 on D y . 9: end for 10: Define the final selected attribute Â(X n+1 ) using Equation (A15). 11: Define the final prediction set Ĉ(X n+1 ) using Equation (A16). 12: Output: Â(X n+1 ) and Ĉ(X n+1 ).Theorem A2. If {(X i , Y i )} n+1i=1 are exchangeable random samples, then the conformal prediction set Ĉ(X n+1 ) and the selected attribute Â(X n+1 ) output by Algorithm A5 satisfy the label-conditional adaptive equalized coverage defined in (A14).Consider a dataset D = {Z i } n i=1 containing n sample points drawn exchangeably from an unknown distribution P Z . Consider an additional test point Z n+1 . In the outlier detection problems, our AFCP method aims to study whether Z n+1 ∼ P Z by constructing a valid conformal p-value û(Z n+1 ) conditional on the group identified by the selected attribute Â(Z n+1 ), that is:EQUATIONfor any α ∈ (0, 1). Intuitively, this guarantees that, on groups defined by the selected attribute Â(Z n+1 ), the conformal p-value is super-uniform, therefore controlling the FPR (the probability of rejecting the null hypothesis that Z n+1 is an inlier when it is true) below α.Given a pre-trained one-class classifier f , an independent calibration dataset D, and a test point Z n+1 , our method selects a sensitive attribute Â(Z n+1 ) ∈ {∅, {1}, . . . , {K}} according to the following leave-one-out procedure. Sometimes, no attribute may be selected, as denoted by Â(Z n+1 ) = ∅.Define an augmented calibration setD ′ := D ∪ {Z n+1 }. For each i ∈ [n + 1], define also the leave-one-out set D ′ i := D ′ \ {Z i }. Then, for each i ∈ [n + 1],we compute a conformal p-value ûloo (Z i ) for Z i using the data in D ′ i to test if Z i is an outlier. This can be accomplished by running Algorithm A2, using D ′ i as the calibration data and Z i as the test point, and with the convention that smaller nonconformity scores suggest Z i is more likely to be an outlier. Any nonconformity scores can be utilized here. For concreteness, we focus on using the adaptive conformity scores proposed by [27] . Small ûloo (Z i ) provides stronger evidence to reject the null hypothesis H 0,i : Z i is an inlier. Let E i denote the binary indicator of whether H 0,i is rejected:E i := 1{û loo (Z i ) ≤ α}. (A18)After evaluating E i for all i ∈ [n + 1], we will assess the leave-one-out FPR for the worst-off group identified by each sensitive attribute k ∈ [K]. That is, we evaluateδ k := max m∈[M k ] n+1 i=1 E i • 1{ϕ(Z i , {k}) = m} n+1 i=1 1{ϕ(Z i , {k}) = m} . (A19)Intuitively, δ k denotes the maximum FPR across all groups identified by the k-th attribute, as estimated by the leave-one-out simulation carried out under the assumption that Z n+1 is an inlier. Large values of δ k suggest that the k-th attribute may be a sensitive attribute corresponding to at least one group suffering from algorithmic bias.To assess whether there is evidence of significant algorithmic bias, we can perform a statistical test for the null hypothesis that no algorithmic bias exists. We define:EQUATIONand carry out a one-sided t-test for the null hypothesis H 0 : q ≤ α against H 1 : q > α.If H 0 is rejected (at any desired level, such as 5%), we conclude there exists a group suffering from significant algorithmic bias, and we identify the corresponding attribute throughÂ(Z n+1 ) = {arg max k∈[K] δ k }. (A21)Otherwise, we set Â(Z n+1 ) = ∅, which corresponds to selecting no attribute. See Algorithm A6 for an outline of this procedure.After selecting either a single attribute or an empty set Â(X n+1 ) that corresponds to at least one group suffering from algorithmic bias, the next step of our AFCP method is to compute an adaptive conformal p-value for testing whether Z n+1 is an outlier that satisfies (A17). This can be simply achieved by applying the standard conformal method outlined in Algorithm A2 based on a restricted calibration sample indexed byI( Â(Z n+1 )) = {i ∈ [n] : ϕ(Z i , Â(Z n+1 )) = ϕ(Z n+1 , Â(Z n+1 ))},See Algorithm A7 for a summary of AFCP for outlier detection tasks.Theorem A3. If {Z i } n+1i=1 are exchangeable random samples, the conformal p-value û(Z n+1 ) and the selected attribute Â(Z n+1 ) output by Algorithm A7 satisfy (A17).Algorithm A6 Automatic attribute selection for outlier detection.1: Input: calibration data D; test point Z n+1 ; list of K sensitive attributes; 2: Input: pre-trained one-class classifier f ; pre-defined rule for computing nonconformity scores; 3: Input: nominal level α ∈ (0, 1). 4: Define the augmented data setD ′ = D ∪ {Z n+1 }. 5: for i ∈ [n + 1] do 6:Pretend that Z i is the test point and D ′ \ {Z i } is the calibration set.Compute a conformal p-value ûloo (Z i ).Evaluate the false positive indicator E i using (A18). 9: end for 10: Compute q using (A20). 11: Perform a one-sided test for H 0 : q ≤ α vs. H 1 : q > α.12: Select the attribute Â(Z n+1 ) using (A21) if H 0 is rejected, else set Â(Z n+1 ) = ∅. 13: Output: Â(Z n+1 ), either a selected sensitive attribute or an empty set.Algorithm A7 AFCP for outlier detection. AFCP for outlier detection problems can be readily extended to select J sensitive attributes where J > 1. This is achieved by repeatedly applying the single attribute selection procedure described in Algorithm A6 J times. Each time, the algorithm selects a (possibly empty) subset of attributes Â(Z n+1 ) j from the list of sensitive attributes excluding the previously selected attribute Â(Z n+1 ) j-1 .The final set of selected attributes is given by Â(Z n+1 ) = ∪ J j=1 Â(Z n+1 ) j . See Algorithm A8 for an outline of this procedure.Algorithm A8 Multiple attributes selection for outlier detection.1: Input: calibration data D; test point Z n+1 ; list of K sensitive attributes; 2: Input: pre-trained one-class classifier f ; pre-defined rule for computing nonconformity scores; 3: Input: nominal level α ∈ (0, 1); number of selected attributes J.4: Denote K 0 = [K]. 5: for j ∈ {1, . . . , J} do 6:Select an attribute Â(Z n+1 ) j by applying Algorithm A6 with sensitive attributes K j-1 .Update the list of sensitive attributesK j = K j-1 \ Â(Z n+1 ) j . 8: end for 9: Output: Â(Z n+1 ) = ∪ J j=1 Â(Z n+1) j , an empty set or a set of selected attributes.After selecting a set of attributes Â(Z n+1 ), which might be empty or include one or more sensitive attributes, AFCP constructs an adaptive conformal p-value satisfying (A17). This can be easily achieved by applying Algorithm A2 with protected attributes Â(Z n+1 ). Algorithm A9 summarizes the AFCP implementation for outlier detection that allows selecting multiple protected attributes.Theorem A4. If {Z i } n+1i=1 are exchangeable random samples, the conformal p-value û(Z n+1 ) and selected attributes Â(Z n+1 ) output by Algorithm A9 satisfy (A17).Algorithm A9 AFCP for outlier detection with multiple selected attributes.1: Input: calibration data D; test point Z n+1 ; list of K sensitive attributes; 2: Input: pre-trained one-class classifier f ; pre-defined rule for computing nonconformity scores; 3: Input: nominal level α ∈ (0, 1); number of selected attributes J. 4: Select up to J sensitive attributes Â(Z n+1 ) by applying Algorithm A8. 5: Evaluate û(Z n+1 ) by applying Algorithm A2 with protected attribute Â(Z n+1 ).6: Output: û(Z n+1 ).Proof of Theorem 1. Consider an imaginary oracle that has access to the true value of Y n+1 . Denote Âo (X n+1 , Y n+1 ) as the sensitive attribute selected by this oracle by applying Algorithm 1 with the true Y n+1 instead of a placeholder label. Let Ĉo (X n+1 , Âo (X n+1 , Y n+1 )) represent the corresponding output prediction set by applying Algorithm A1 with the protected attribute Âo (X n+1 , Y n+1 ).Consider also Ĉm (X n+1 ), the standard prediction set with marginal coverage (1) .The main idea of our proof is to connect the output prediction set Ĉ(X n+1 ) and selected attribute Â(X n+1 ) from Algorithm 2 to those of the imaginary oracle described above. Throughout this proof, we adopt the convention that ϕ(X n+1 , ∅) = 0.To establish this connection, note that the attribute Â(X n+1 ) selected by Algorithm 2 is either empty,EQUATIONwhere the last inequality follows from the facts that Ĉm (X n+1 ) ⊆ Ĉ(X n+1 ) and Ĉo (X n+1 , Âo (X n+1 , Y n+1 )) ⊆ Ĉ(X n+1 ) almost-surely. Next, we only need to separately lowerbound by 1 -α the two terms on the right-hand-side of (A22).The first part of the remaining task is trivial. It is already well-known that P(Y n+1 ∈ Ĉm (X n+1 )) ≥ 1 -α; see [13, 57] .To complete the second part of the remaining task, note that the oracle-selected attribute Âo (X n+1 , Y n+1 ) is invariant to any permutations of the exchangeable data indexed by [n + 1]. Therefore, the data points are also exchangeable conditional on the groups defined by Âo (X n+1 , Y n+1 ). This means we can imagine the protected attribute Âo (X n+1 , Y n+1 ) is fixed, and the oracle prediction set Ĉo (X n+1 , Âo (X n+1 , Y n+1 )) is simply obtained by applying Algorithm A1 to exchangeable data using a fixed protected attribute. This procedure is the same as the main algorithm in [17] and has guaranteed coverage above 1 -α; see Theorem 1 in [17] .Proof of Theorem A1. Similar to the proof of Theorem 1, consider an imaginary oracle that has access to the true value of Y n+1 . Denote Âo (X n+1 , Y n+1 ) as the (possibly empty, one, or two) sensitive attribute(s) selected by this oracle by applying Algorithm A3 with the true Y n+1 . Let Ĉo (X n+1 , Âo (X n+1 , Y n+1 )) represent the output prediction set by applying Algorithm A1 with the protected attribute(s) Âo (X n+1 , Y n+1 ). Consider also Ĉm (X n+1 ), the standard prediction set with marginal coverage (1), and Ĉeq (X n+1 , ℓ) the prediction set with valid coverage conditional on groups identified by a fixed attribute {ℓ}.The key idea of our proof is again to connect the practical prediction set Ĉ(X n+1 ) and selected protected attributes Â(X n+1 ) of Algorithm A4 to those of the imaginary oracle described above.Throughout this proof, we adopt the convention that ϕ(X n+1 , ∅) = 0.To establish this connection, note that the attribute(s) Â(X n+1 ) selected by applying Algorithm A3 falls into one of the three possible cases almost surely: (a)Â(X n+1 ) = ∅, (b) Â(X n+1 ) = Âo (X n+1 , Y n+1 ), and (c) Ȧ(X n+1 ) = Â(X n+1 ) ⊂ Âo (X n+1 , Y n+1 ).The last scenario happens when the oracle selects two attributes, and the Â(X n+1 ) contains only one of them. For clarify of the notation, we denote the last case using Ȧ(X n+1 ).Therefore,EQUATIONwhere the last inequality follows from the facts that Ĉm (X n+1 ) ⊆ Ĉ(X n+1 ), Ĉo (X n+1 , Âo (X n+1 , Y n+1 )) ⊆ Ĉ(X n+1 ), and ∪ ℓ∈ Âo (Xn+1,Yn+1) Ĉeq (X n+1 , ℓ) ⊆ Ĉ(X n+1 )almost-surely.Next, we show how to separately lower-bound by 1 -α the three terms on the right-hand-side of (A23).The lower bounds of the first and second terms have been proved in theorem 1. We will focus on lowerbounding the coverage of the third term. Because the oracle-selected attribute(s) Âo (X n+1 , Y n+1 ) are invariant to any permutation of the exchangeable data indexed by [n + 1], we can treat each of the two elements in Âo (X n+1 , Y n+1 ) as fixed. Without loss of generality, let ℓ 1 and ℓ 2 denote the first and the second element respectively, Ȧ(X n+1 ) = ℓ 1 or Ȧ(X n+1 ) = ℓ 2 with probability 1. Then,EQUATIONwhere the inequality of the last line of (A24) is proved in [17] with fixed attribute ℓ 1 and ℓ 2 respectively. Lastly, realize that∪ ℓ∈ Âo (Xn+1,Yn+1) Ĉeq (X n+1 , ℓ) ⊆ ∪ ℓ∈∪ L y=1 Â(Xn+1,y) Ĉeq (X n+1 , ℓ) ⊆ Ĉ(X n+1 )almost-surely, the proof is completed.Proof of Theorem A2. Similar to the proof of Theorem 1, consider an imaginary oracle that has access to the true value of Y n+1 . Denote Âo (X n+1 , Y n+1 ) as the sensitive attribute selected by this oracle by applying Algorithm 1 based on a subset of the calibration data indexed byD Yn+1 = {i ∈ [n] : Y i = Y n+1 }. Let Ĉo (X n+1 , Âo (X n+1 , Y n+1)) represent the output prediction set by applying Algorithm A1 with the protected attribute Âo (X n+1 , Y n+1 ). Consider also Ĉlc (X n+1 , Y n+1 ), the prediction set with label-conditional coverage obtained by running Algorithm A1 using D Yn+1 without any protected attributes.To establish this connection between the output prediction set Ĉ(X n+1 ) and the selected attribute Â(X n+1 ) of Algorithm A5 and these of the imaginary oracle, note that the selected attribute Â(X n+1 )must be Â(X n+1 ) = ∅ or Â(X n+1 ) = Âo (X n+1 , Y n+1 ).Therefore, for any y ∈ [L],EQUATIONwhere the last inequality follows from the facts that Ĉlc (X n+1 , Y n+1 ) ⊆ Ĉ(X n+1 ) andĈo (X n+1 , Âo (X n+1 , Y n+1 )) ⊆ Ĉ(X n+1 ) almost-surely.Next, we only need to separately lower-bound by 1 -α the two terms on the right-hand-side of (A25).The first part of the remaining task is trivial. It is already well-known that [13, 47, 58] .P(Y n+1 ∈ Ĉlc (X n+1 , Y n+1 ) | Y n+1 = y) ≥ 1 -α; seeNext, we prove the lower bound for the second term. Fix any y ∈ [L], and assume Y n+1 = y. First, note that the oracle-selected attribute Âo (X n+1 , Y n+1 ) is invariant to any permutations of the exchangeable data indexed by D y ∪ {X n+1 , y}. Therefore, the data points are exchangeable conditional on the group identified by the oracle-selected attribute Âo (X n+1 , Y n+1 ). This means that we can imagine the protected attribute Âo (X n+1 , Y n+1 ) is fixed, and the oracle prediction set Ĉo (X n+1 , Âo (X n+1 , Y n+1 )) is simply obtained by applying Algorithm A1 to exchangeable data using a fixed protected attribute. This procedure has guaranteed coverage above 1 -α; see Lemma A1.Proof of Theorem A3. The strategy of this proof is very standard in the conformal inference literature. We add this proof for completeness.Recall that I( Â(Z n+1 )) denotes a subset of the calibration data D that has the same value of the selected attribute as the test point. To prove (A17), it suffices to show that the nonconformity scores { Ŝi : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }}EQUATIONEven if the nonconformity scores are not almost surely distinct, one can still verify that the distribution of û(Z n+1 ) is super-uniform. Combining both cases, we haveP(û(Z n+1 ) ≤ α|ϕ(Z n+1 , Â(Z n+1 ))) ≤ α for any α ∈ (0, 1).We complete the proof by showing that the nonconformity scores { Ŝi : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }} are exchangeable. Define σ as an arbitrary permutation function applied on D ∪ {Z n+1 } and denote the permuted dataset as σ(D). We first run Algorithm A7 based on D to select the sensitive attribute Â(Z n+1 ). Next, assume in a parallel world, we repeat Algorithm A7 with the same parameters and seed settings but based on the permuted data σ(D). Denote the selected attribute in the parallel world as Â′ (Z n+1 ). Essentially, Â′ (Z n+1 ) = Â(Z n+1 ). This is because the computation of conformal pvalues and the procedure of selecting the attribute with the worst FPR in Algorithm A6 are not affected by the order of the calibration and test data. Therefore, the attribute selection process is invariant to the order of D ∪ {Z n+1 }. This implies that the attribute selected by Algorithm A6 Â(Z n+1 ) can be treated as fixed, and the nonconformity scores computed on the subset I( Â(Z n+1 )) ∪ {Z n+1 } are simply reordered in the parallel world, i.e.,{ Ŝ′ σ(i) : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }} = σ({ Ŝi : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }}),where σ is the permutation obtained by restricting σ on I( Â(Z n+1 )) ∪ {Z n+1 }. Hence, we have{ Ŝi : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }} d = { Ŝ′ σ(i) : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }} = σ({ Ŝi : i ∈ I( Â(Z n+1 )) ∪ {Z n+1 }}),where the equality in distribution is implied byD d = σ(D).Proof of Theorem A4. This proof is the same as the proof of Theorem A3 since the multiple selected attributes Â(Z n+1 ) are invariant to any permutation of the calibration and test data.Proof of Lemma A1. This proof is a minor extension of the proof of Theorem 1 in [17] , with the difference that we additionally condition on the true test label. Y i = ỹ, ϕ(X i , Â(X n+1 , y)) = ϕ(X n+1 , Â(X n+1 , y))}. Since {(X i , Y i )} n+1i=1 are exchangeable and the protected attribute Â(X n+1 , y) is fixed, the nonconformity scores Ŝi evaluated on the subset I(X n+1 , y) ∪ {(X n+1 , y)} are also exchangeable.Further, denote Q(X n+1 , y) as the ⌈(1 -α) • |1 + I(X n+1 , y)|⌉-th smallest value of { Ŝi } i∈I(Xn+1,y) . By the quantile lemma [13, 17, 57] , for any α ∈ (0, 1), AFCP for outlier detection outlined in Algorithm A7 has the following computational cost.P[Y n+1 ∈ Ĉ(X n+1 , Â(X n+1 , y)) | Y n+1 = ỹ, ϕ(X n+1 , Â(X n+1 , y))] = P[ Ŝn+1 ≤ Q(X n+1 , y) | Y n+1 = ỹ, ϕ(X n+1 , Â(X n+1 , y))] ≥ 1 -α.Analysis for a single test point • Once the attribute is selected, the cost of applying conformal prediction conditional on the group identified by the selected attribute is O(1) because the subset of the group has been found in the last step.•Hence, the total cost of running Algorithm A7 for a single test point is O(n log n + nKM ).• The cost of computing the false positive indicators for every sample inD ∪ {Z n+t } m t=1 takes O(n • (m + log n)). This can be derived by rewriting the conformal p-values for all j ∈ D ∪ {Z n+t } and for all t ∈ [m] as follows:ûj,t = 1 1 + n i∈D∪{Zn+t} 1( Ŝi ≤ Ŝj ) = 1 1 + n rank( Ŝj ) among { Ŝi } i∈D + 1( Ŝn+t ≤ Ŝj ) .Computing the nonconformity scores for all samples in D ∪ {Z n+t } m t=1 costs O(n + m), evaluating the ranks takes O(n log n), and comparing Ŝn+t andŜj costs O(n • m). • Selecting the sensitive attribute costs O(n • m + M • K • (n + m)).Breaking in steps, for each test sample Z n+t , the worst FPR for attribute k, as defined in (A20), can be rewritten as follows:δ k,t := max m∈[M k ] i∈D∪{Zn+t} E i,t • 1{ϕ(Z i , {k}) = m} i∈D∪{Zn+t} 1{ϕ(Z i , {k}) = m} = max m∈[M k ] i∈D E i,t • 1{ϕ(Z i , {k}) = m} + E t,t • 1{ϕ(Z i , {k}) = m} i∈D 1{ϕ(Z i , {k}) = m} + 1{ϕ(Z i , {k}) = m} = max m∈[M k ] i∈D(k,m) E i,t + E t,t • 1{ϕ(Z i , {k}) = m} |D(k, m)| + 1{ϕ(Z i , {k}) = m} ,where D(k, m) represents a subset of the calibration data indexed by {i ∈ D : ϕ(Z i , {k}) = m}. The trick we use is that the identification of subset D(k, m) does not depend on the test sample t and can be reused to calculate the FPR for every test sample{Z n+t } m t=1 . In specific, identifying D(k, m), ∀k ∈ [K], m ∈ [M k ] takes O(n•M •K). For each D(k, m), computing i∈D(k,m) E i,t , ∀t ∈ [m] takes O(|D(k, m)| • m), and computing E t,t 1{ϕ(Z i , {k}) = m} takes O(m). Therefore, repeating this process for all D(k, m), k ∈ [K], m ∈ [M k ] in total takes O(n • m). Lastly, finding the maximum FPR across all attributes takes O(m • M • K).Hence, the total cost of running Algorithm A7 for m test samples is O(n log n + nm + M K(n + m)).Given a pre-trained multi-class classifier, consider a calibration dataset D of size n. Let L denote the total number of possible labels to predict, and let K denote the number of sensitive attributes. For each attribute k ∈ [K], let M k ∈ N denote the count of its possible values. Denote M = max k M k as the maximum count across all attributes.AFCP for multi-class classification outlined in Algorithm 2 has the following computational cost.• The cost of constructing prediction sets and computing miscoverage indicators within the leave-one-out procedure isO(L • n • log n). • Then, selecting the sensitive attributes requires O(n • K • M + L • (n + M • K)).• Once the attribute is selected, the cost of applying conformal prediction conditional on the group identified by the selected attribute is O(1) because the subset of the group has been found in the last step.Hence, the total cost of running Algorithm 2 for a single test point is O(L(n log n + KM ) + nKM ).Analysis for m test points• The cost of computing miscoverage indicators is O(L • n • (m + log n)). This can be derived by rewriting the conformal p-values for all j ∈ D ∪ {(X n+t , y)} ∀y ∈ [L], and ∀t ∈ [m] as follows:ûy j,t = 1 1 + n i∈D∪{Zn+t} 1( Ŝy i ≤ Ŝy j ) = 1 1 + n rank( Ŝy j ) among { Ŝy i } i∈D + 1( Ŝy n+t ≤ Ŝy j ) .For each placeholder label y ∈ [L], computing the nonconformity scores for all samples in D ∪ {(X n+t , y)} m t=1 costs O(n + m), evaluating the ranks takes O(n log n), and comparing Ŝy n+t with Ŝy j costs O(n•m). This process needs to be conducted for each y∈ [L], therefore the total cost of this step is O(L • (n + m + n log n + nm)) = O(L • n • (log n + m)). • Selecting the sensitive attribute costs O(n • M • K + L • m(n + M • K). Breaking in steps, for each test sample (X n+t , y), y ∈ [L], the worst miscoverage rate for attribute k, as defined in (5) , can be rewritten as follows:δ y,k,t := max m∈[M k ] i∈D∪{(Xn+t,y)} E y,i,t • 1{ϕ(X i , {k}) = m} i∈D∪{(Xn+t,y)} 1{ϕ(X i , {k}) = m} = max m∈[M k ] i∈D E y,i,t • 1{ϕ(X i , {k}) = m} + E y,t,t • 1{ϕ(X i , {k}) = m} i∈D 1{ϕ(X i , {k}) = m} + 1{ϕ(X i , {k}) = m} = max m∈[M k ] i∈D(k,m) E y,i,t + E y,t,t • 1{ϕ(X i , {k}) = m} |D(k, m)| + 1{ϕ(X i , {k}) = m} ,where D(k, m) represents a subset of the calibration data indexed by {i ∈ D : ϕ(Z i , {k}) = m}. The trick we use is that the identification of subset D(k, m) does not depend on the test sample t and the placeholder label y, therefore can be reused to calculate the miscoverage rate for every test sample {(X n+t , y)} m t=1 . In specific, identifyingD(k, m), ∀k ∈ [K], m ∈ [M k ] takes O(n • M • K). For each D(k, m), computing i∈D(k,m) E y,i,t , ∀t ∈ [m], ∀y ∈ [L] takes O(L • |D(k, m)| • m), and computing E y,t,t 1{ϕ(Z i , {k}) = m} takes O(L • m). Therefore, repeating this process for all D(k, m), k ∈ [K], m ∈ [M k ] and for all y ∈ [L] in total takes O(L • n • m). Lastly, finding the maximum miscoverage across all attributes takes O(L • m • M • K).Hence, the total cost of running Algorithm 2 for m test samples is O(n log n+Lnm+M K(n+Lm)). Recall from Section 3.2 that Color is denoted as X 0 and the first one of the non-sensitive features as X 1 . The distribution of Y conditional on X is modeled by a simple decision tree, where X 0 and X 1 are the only useful predictors for Y , formulated as the following:P[Y | X] =                    1 3 , 1 3 , 1 3 , 0, 0, 0 , if X 0 =Blue and X 1 < 0.5, 0, 0, 0, 1 3 , 1 3 , 1 3 , if X 0 =Blue and , X 1 ≥ 0.5, (1, 0, 0, 0, 0, 0) , if X 0 =Grey and , 0 ≤ X 1 ≤ 1 6 , (0, 1, 0, 0, 0, 0) , if X 0 =Grey and , 1 6 ≤ X 1 ≤ 2 6 , . . . . . . (0, 0, 0, 0, 0, 1) , if X 0 =Grey and , 5 6 ≤ X 1 ≤ 1.(A27)The detailed numerical experiments results of AFCP with the adaptive equalized coverage (see Equation ( 3)) are presented and compared with other benchmark methods. For the Occupation 1 group, the Marginal method (dashed orange lines) fails to detect and correct for its undercoverage, and the Exhaustive method produces prediction sets that are too conservative to be helpful. In contrast, our AFCP and AFCP1 methods correct the undercoverage and maintain small prediction sets. See Table A10 For the Occupation 1 group, the Marginal method (dashed orange lines) fails to detect and correct for its undercoverage, and the Exhaustive method produces prediction sets that are too conservative to be helpful. In contrast, our AFCP and AFCP1 methods correct the undercoverage and maintain small prediction sets. See Table A16 for details and standard errors. We extend our experiments to investigate the effectiveness of AFCP using the Correctional Offender Management Profiling for Alternative Sanctions (COMPAS) dataset [50] . The COMPAS dataset is widely studied in the fairness literature for multi-class classification tasks, predicting the risk of recidivism across three categories: 'High', 'Medium', and 'Low'. Following the data preprocessing steps outlined in [59] , we exclude rows with missing or low-quality data and compute the length of stay in jail. Additionally, we merge the race groups Asian and Native American, both of which have few occurrences, into the 'Others' category. After preprocessing, the dataset comprises 6,172 instances with five categorical features: charge degree of defendants (2 levels), race (4 levels), age category (3 levels), sex (2 levels), and score category of defendants (3 levels). We regard the first four features as potentially sensitive attributes.Similar to the Nursery dataset case, we utilize the LabelEncoder function to numerically encode categorical features and outcome labels. To increase prediction difficulty and emphasize algorithmic bias, we introduce independent, uniformly distributed noise to the labels of samples identified as African-American. Additionally, we undersample the African-American group to 200 samples, while the Caucasian group contains 2,103 samples, Hispanic 509, and Others 385.Figure A19 summarizes the performance of all methods as a function of the total number of training and calibration data points, which range from 200 to 1000. Figure A20 narrows the focus by analyzing the performance relative to the number of restricted calibration data points, as defined in Section 2.2.The results are averaged over 500 randomly selected test points and 100 repeated experiments. In each experiment, 50% of the samples are randomly assigned for training and the remaining 50% for calibration. Once again, we conclude that our AFCP methods outperform the other benchmarks considered, resulting in more informative prediction sets with higher conditional coverage for the African-American subgroup.Figure A21 shows the selection frequencies of the protected attribute Race as a function of sample size within the same experiment described in Figure A19 . This plot demonstrates that both AFCP and AFCP 1 consistently select Race as the most sensitive attribute as the number of samples increases. Also, we report the prediction accuracy in Table A21 . The results confirm that the African-American group is disproportionately affected by algorithmic bias, not only in terms of uncertainty estimates but also in prediction accuracy, as they experience significantly lower-than-average test accuracy. This section demonstrates the empirical performance of our AFCP extension for outlier detection. Firstly, we focus on the implementation described in Algorithm A7, which selects at most one sensitive attribute. Similar to the multi-class classification cases, Our method is compared with three existing approaches, which utilize the same data, ML model, and conformity scores but compute conformal p-values with different guarantees. The first is the marginal benchmark, which constructs conformal p-value guaranteeing P(û marginal (Z n+1 ) ≤ α) ≤ α by applying Algorithm A2 without protected attributes. The second is the exhaustive equalized benchmark, which evaluates conformal p-values guaranteeing P(û exhaustive (Z n+1 ) ≤ α | ϕ(Z n+1 , [K])) ≤ α by applying Algorithm A2 with all K sensitive attributes simultaneously protected. The third is a partial equalized benchmark that separately applies Algorithm A2 with each possible protected attribute k ∈ [K], and then takes the maximum of all such p values. This is an intuitive approach that can be easily verified to provide a coverage guaranteeP(û partial (Z n+1 ) ≤ α | ϕ(Z n+1 , {k})) ≤ α ∀k ∈ [K].In addition, similar to the multiclass classification experiments, we consider AFCP1 -the AFCP implementation that always selects the most critical protected attribute without conducting the significance test.For all methods considered, the outlier detection model is based on a three-layer neural network, and the outputs from each layer are batch-normalized. The Adam optimizer and the BCEWithLogitsLoss loss function are used in the training process, with a learning rate set at 0.0001. The loss values demonstrate convergence after 100 epochs of training. For all methods, the miscoverage target level is set at α = 0.1. Note that the training and testing data contain both inliers and outliers, while the calibration data only contains inliers.We assess the performance of the methods based on the False Positive Rate (FPR) and the True Positive Rate (TPR). Ideally, the objective is to achieve a higher conditional FPR for groups experiencing unfairness, thereby maintaining the average FPR below the target threshold of 0.1 while simultaneously achieving a higher TPR. The results presented are averaged over 500 independent test points and 30 experiments.We employ the same data settings as in the multi-class classification example, designating Color as the sensitive attribute associated with the Blue group, which suffers from undercoverage. While Age Group and Region are also sensitive attributes, they are not subject to biases in this context. The outcome labels Y have two possible values: Y = 0 if the unit is properly treated and Y = 1 otherwise. In our experiment, we treat Y = 1 as an outlier and Y = 0 as an inlier, with the data generation process described as: • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.EQUATION 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The paper provides information on the computer resources in the Discussion section.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.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). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: This work is motivated by the need to address algorithmic bias issues, which is a topic with potentially broad impacts, as discussed in the paper. However, this paper focuses on foundational research that is not tied to a particular application.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: This paper describes foundational research and does not release new data or 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: [Yes] Justification: This paper uses open-domain data, properly crediting the license and creators. 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The new code accompanying this paper is well documented.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  


Decision: The paper concerns the problem of conformal predictions with fairness. The Authors introduces a new method that adaptively selects a sensitive attribute corresponding to the group most negatively affected by algorithmic bias. It then constructs a prediction set that ensures equalized coverage across groups defined by the selected attribute. Experiments on both simulated and real datasets are conducted to validate the proposed solution.

The reviewers are generally positive about the paper. They appreciate the proposed solution, along with its theoretical and empirical justification, and commend the clarity of the presentation. They also raised several critical comments including notational mistakes, unclear statements, areas of improvement in the empirical studies, or a limited discussion on computational complexity. During the discussion phase, the Authors successfully provided additional results and resolved the main concerns raised by the reviewers.

Reviews: review: paper_summary: paper_summary: The paper focuses on the problem of conformal inference with equalized coverage introduced in [1]. The authors propose a new method, Adaptively Fair Conformal Prediction (AFCP) that (i) adaptively selects a sensitive attribute corresponding to the group most negatively affected by algorithmic bias as evaluated by the miscoverage rate, and (ii) constructs a prediction set that satisfies equalized coverage over groups defined by the selected attribute. The authors perform experiments on synthetic and real data that demonstrate the performance of AFCP relative to methods that guarantee marginal coverage and exhaustive equalized coverage i.e., ​​valid coverage conditional on all sensitive attributes.

[1] Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2020.
strength_weakness: strength_weakness: 1. The clarity of the paper can be greatly improved. Detailed comments:
- p2 l37: "A limitation of the current method for conformal inference with equalized coverage...." -- what is the current method?
- p2 l41: what do you mean by efficiency and informativeness here? Is it set size? Please make it clear and precise.
- Section 1.1: Overall, it is hard to understand the motivation from this section. It would be helpful to rewrite this a bit e.g. l32-36: it is not clear how this conveys the rationale for conformal inference with equalized coverage different from rationale for conformal inference more generally.
- The notations are incorrect in some places and unnecessarily complex
   - p2 l71-72: $\phi$ is defined as mapping to $\mathbb{N}$ whereas the next line says it results in vector of length $|A|$. I believe it should be defined more generally
   - p2 l77-84: The notion of equalized coverage in [17] is defined as: $\mathbb{P}(Y_{n+1} \in C(X_{n+1}, A_{n+1}) | A_{n+1} = a) \geq 1 - \alpha$. It is not clear how this is extended to multiple (possibly overlapping) groups defined by $K$ sensitive attributes using $\phi$
- It is not clear at some places whether $A$ refers to single attribute or set
   - Alg 2 l4-5: in line 4, $A$ refers to single attribute, in line 5 it refers to multiple (set of) attributes
   - p6 l197: (7) returns a final selected attribute while the sentence refers to subset of attributes
- p6 l204: minor comment, this does not hyperlink to A1
- typos in table captions (Table A25 onwards)
   
2. Insufficient empirical evaluation: While the paper includes detailed analysis on the two selected datasets, both these setups are fairly synthetic. Also, the Nursery data seems to be from 1997; the paper lacks evaluation on any recent and common benchmark datasets in literature. The paper also seems to lack experiments that demonstrate coverage and efficiency performance in the presence of multiple sensitive attributes.

3. The AFCP1 variation of AFCP seems to outperform AFCP in all cases -- when the sample size is small, we still see undercoverage for the Blue group using AFCP (Fig 3) and AFCP1 is more robust by selecting at least one attribute. While the paper mentions this, what would be the advantage of using AFCP? Is there any procedure to select variations for different data regimes?
questions: questions: 1. The main text discusses the AFCP algorithm where at most one sensitive attribute may be selected. If we want equalized coverage over multiple attributes, won’t using AFCP result in similar challenges as exhaustive equalized coverage?

2. How does the size of the restricted calibration sample affect the performance of the algorithm?
limitations: limitations: The authors discuss the limitations in the Discussion section.
paper_summary: paper_summary: The paper presents a novel conformal inference method aimed at generating prediction sets with valid coverage, conditional on adaptively chosen features. This method is intended to address the dual concerns of efficiency and algorithmic fairness by ensuring equalized coverage for the most sensitive groups, thus providing informative predictions while maintaining fairness. The proposed approach, termed Adaptively Fair Conformal Prediction (AFCP), is validated on both simulated and real datasets.
strength_weakness: strength_weakness: 1. While the paper acknowledges the scalability issues associated with current methods for conformal inference with equalized coverage, it does not provide a detailed analysis of the computational complexity of the proposed method. A deeper exploration of scalability, particularly for large-scale datasets, would strengthen the paper.
2. The method's reliance on leave-one-out procedures for attribute selection could be computationally intensive and potentially unstable with small sample sizes. More discussion on the stability and robustness of the attribute selection process, along with empirical evidence, would be beneficial.
3. The literature review, while covering relevant works, could be more exhaustive. Incorporating additional recent studies on robust conformal inference and handling distributional shifts would provide a broader context and highlight the novelty of the proposed approach.
questions: questions: What is the computational complexity of the proposed method, and how does it scale with large datasets?
Are there any optimization strategies to improve efficiency?

How stable is the attribute selection process across different sample sizes and datasets?
Can the method handle cases where multiple sensitive attributes need to be considered simultaneously?


Can the method be tested on more diverse and larger real-world datasets to validate its scalability and generalizability?
How does the method perform in scenarios with highly imbalanced datasets?

Have other attribute selection procedures been considered, and how do they compare with the proposed leave-one-out approach?
limitations: limitations: yes
paper_summary: paper_summary: The paper introduces a conformal inference method to assess uncertainty in classification by generating prediction sets with valid coverage, conditional on adaptively chosen features. These features are selected to address model limitations or biases, balancing efficiency and fairness by ensuring equalized coverage for sensitive groups. The paper demonstrates this method's validity and effectiveness on both simulated and real datasets.
strength_weakness: strength_weakness: 1.	Limitation on Sensitive Attribute Selection: The current method may not always identify the most relevant sensitive attribute, especially with limited sample sizes or overlapping biases. The ‘Automatic Attribute Selection’ section is somewhat challenging to follow. For instance, in Equation 6, it seems that only the argmax element is included in the set, and the algorithm does not seem to provide a sensitive attribute with formal guarantees. Since much of the paper’s contribution hinges on this algorithm, the lack of clarity in its description makes it hard to be convinced of its effectiveness.
2.	Sample Size Sensitivity: AFCP’s performance can be constrained by the sample size. Smaller sample sizes may result in less reliable attribute selection and less informative prediction sets. In practical datasets, sample sizes tend to be small when many features are selected. The Sensitive Attribute Selection algorithm may lead to a large label set, resulting in too few samples to accurately determine the thresholds.
3.	Computational Complexity: With a large label set, such as in ImageNet which has 1000 labels, this method involves complex procedures for attribute selection and prediction set construction. This complexity may make the method computationally intensive.
questions: questions: 1.	Coverage for Occupation 1 in Figure 5: The coverage for Occupation 1 in Figure 5 shows a significant increase in the Marginal method when the sample size increases from 2000 to 5000. This rapid increase is puzzling, particularly since the average size of the prediction set also decreases in this interval. Could you clarify why this behavior occurs? It seems counterintuitive, as one would generally expect a consistent relationship between coverage and prediction set size.
2.	Impact of Calibration Set Size on Sensitive Attribute Selection and Final Prediction Set: How do you think the calibration set size influences the algorithm for Sensitive Attribute Selection and the final prediction set? Specifically:
limitations: limitations: Please refer to the weakness.
paper_summary: paper_summary: This paper presents a conformal inference method to assess uncertainty in classification by generating prediction sets with valid coverage based on adaptively chosen features. Falling between marginal and strictly conditional coverage, the features in the proposed method are adaptively selected to address potential model limitations or biases, balancing the need for informative predictions with ensuring algorithmic fairness.
strength_weakness: strength_weakness: - It seems that *adaptive equalized coverage* requires each group to surpass a given coverage rate. Desirably like RAPS, the coverage rate should be the same at desired level to guarantee exact demographic parity.
- Though a little out of scope, this paper would be better to provide performance evaluation with presence of distribution shift, especially label shift and shift in protected attributes.
questions: questions: - Would your method preserve satisfy more rigorous fairness (Q1) with better design? I think this may be related with union of sub-intervals. Adaptively adjust the coverage rate of subgroup may help.
- Also, the union of sub-intervals may make less sense in some real-world applications. Say, in some data, the target variables are some categorical and also ordered labels, say level 1~5. Predicting a sample to be either level 1 or 5  is confusing. Have this phenomenon be considered and addressed in your paper?
limitations: limitations: Yes

Comments: title: Author-Reviewer Discussion Phase
comment: Thank you! We will include additional details on the COMPAS data analysis in the revised version of the paper, in support of the three new figures, including accuracy metrics. Please let us know if there is anything else that we should clarify at this point. (In the previous message we didn't realize there's still time until August 13th to discuss, if needed).
Dear Authors and Reviewers!

Thank you for your reviews, rebuttal, additional comments, questions and responses! 

We have the last two days of the discussion phase! Please use this time as efficiently as possible :) 

Thank you,

NeurIPS 2024 Area Chair
Thank you for the explanation and clarification. I acknowledge the comparison between methods as I did in my previous comment. I am also not raising questions on the associated guarantees of conformal prediction, but it would be helpful to add accuracy metrics in the future versions to highlight whether this classification setting is challenging to begin with, and how the prediction sets provide more helpful information. 

In the light of the current discussion, I am willing to raise my score to 5.
Thank you for acknowledging our response. We’re pleased to see that our initial reply addressed your previous questions and concerns. 

We also appreciate your follow-up question about the COMPAS data analysis, though it’s unfortunate that it arrived so close to the deadline, particularly since the meaning of this question is not entirely clear to us.

A 3-class classification problem is a reasonable and informative setting for comparing the performance of different conformal prediction methods. In this case, it shows that our method achieves the desired 90% coverage with prediction sets that are relatively small, averaging below 1.5 in size. It's important to emphasize this is an interesting result, which is not trivial at all to achieve in a 3-class context. In any case, what matters the most here is the comparison between the performances of different conformal prediction methods, which clearly shows the advantages of our approach.

In general, an average prediction set size of 1.5 suggests high confidence (prediction sets of size of 1) in the majority of cases, and less informative predictions sets (sizes 2 and 3) only in a minority of cases where the model may be less accurate. Achieving this type of separation between confident and unconfident predictions is precisely what conformal prediction (and, more broadly, uncertainty quantification in machine learning) generally aims to do.
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)
I thank the authors for the detailed response. I maintain my positive score of weak accept.
Thank you for the thorough response, I raise my rating to 5.