Conformal Classification with Equalized Coverage for Adaptively Selected Groups
Authors: Yanfei Zhou
Matteo Sesia
Venue: NeurIPS 2024 poster (2024)
Keywords: Classification
Conformal Prediction
Equalized Coverage
Fairness
Primary area: fairness

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.

Conformal Classification with Equalized Coverage for Adaptively Selected Groups
Yanfei Zhou
Matteo Sesia
Department of Data Sciences and Operations
Department of Data Sciences and Operations
University of Southern California Los Angeles, California, USA yanfei zhou@marshall. usc.llllllu..eeooooooooo..oo.e.l usc. edu
University of Southern California Los Angeles, California, USA sesia@marshall. .uc.lllluuceuuuu
Abstract
This paper introduces 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 be- tween 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 simulated and real data sets.
Introduction
1.1 Uncertainty, Fairness, and Efficiency in Machine Learning
Increasingly sophisticated machine learning (ML) models, like deep neural networks, are revolution- izing decision-making in many high-stakes domains, including medical diagnostics [1], job screening [2], and recidivism prediction [3, 4). However, serious concerns related uncertainty quantification [5, 6] and algorithmic fairness fairress [7-10] underscore the need for novel methods that can provide reliable and unbiased measures of confidence, applicable any model.
Uncertainty quantification 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 a prediction, raising trust and safety concerns. A promising solution is conformal inference [12-14], which enables converting the output of any model into prediction sets with precise coverage guarantees. These sets reflect the model's confidence case-by-case basis, with smaller sets indicating higher confidence in 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 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 ensure that the prediction sets attain their coverage 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-sing 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 decision- makers 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.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 afficiency-ainee
for highly informative predictions with small set sizes-and fairness- ensuring unbiased treatment- challenging and requires novel approaches. This paper introduces 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 reasonable compromise with finite data sets, mitigating significant biases while retaining predictive power.
1.2 Background on Conformal Inference for Classification
Consider a data set comprising exchangeable (e.g., i...d) observations Z, for i D = [n] (l....,,3} sampled from an arbitrary and unknown distribution Pz. In classification, one can write Z ===X; (X;, Y.). where Y, E [4] == (1,...: L} is categorical label and X, E 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 Zn (Xn+1, Yn+1). also sampled exchangeably from P22, and whose label Yu+1 E [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 C(Xx+1) for Yu+1, guaranteeing marginal coverage at some desired level a E (0, 1):
P[Y,+1 E (((x+11) 2 1-
(1)
This probability is taken over the randomness in Yn+1 and X 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 a 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 conturr-condiiionll coverage, P(Yn-1 E Ō(x,+1) X,+1 x] >1 1 a for all x E X. This would ensure consistent coverage for all possible test features X However, it is impossible to achieve without additional assumptions, such as modeling the distribution Pz [19] or significantly restricting the feature space X' [20]. Given that such assumptions may be unrealistic in real-world settings, exact
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 Xn+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 h E [K] let M E N count the possible values of the k-th attribute. Consider a function & :::: X' x 10 + N for any subset A C [K] with |A| d elements, so that ø(x, A) is vector of length | 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 constant. If A is a singleton, e-g., A =kk for some k [K], then o(z [k}) E [M&] denotes the value of the k-th attribute; e.g., someone's 's academic degree. More generally, 6(z, (k. 13) [M x [Mi], for any distinct k, E [K], denotes the joint values of two attributes, characterizing a smaller group, such as "males with a bachelor's 's degree.".
When multiple sensitive attributes are involved, i.e., K the concept of equalized coverage introduced by [17] can be naturally extended to exhaustive equalized coverage, defined as:
P[Y E C(Xa+1) Φ ((x+1,, 2 a.
In words, this says ((x,-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- = I Mj groups characterized by a specific combination the protected attributes represented by ø(X,, [K]); see Appendix A1 for details. However, downside of this approach that the calibration subsets may be too small if M large, leading to uninformative predictions for even moderate values of K. This limitation forms the starting point of our work.
2

---

1.3 Preview of Our Contributions: Adaptive Equalized Coverage
In practice, for 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), 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 sensitive attribute ((x+1)) E {0, [1}.... {K]}, based on Xn+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 (A(Xa+1) 0) in the absence of significant biases.
Selects Bace, Race Back valid coverage on Black.
Trained model
Selects None, with marginal
Text
Calibration set
Selects Gender & Age Group Male. Age Group 2632
CP with velid coverage on Male & >65.
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 case-by-case basis.
Next, AFCP constructs a prediction set C(X++1) ) for Ya+1 that guarantees the following notion of adaptive equalized coverage at the desired level a E (0,
P(yn-1 E ((Xx+1)) ((Xx+1; A(Xx+1))) 2 aa
In words, this tells us C(X,+1) is well-calibrated for the groups defined by the selected attribute A(Xn+1). ). It is worth highlighting the key distinctions between (3) and the existing notions of cover- age reviewed above. On the one hand, if AFCP identifies significant bias, selecting A(X,+1) 0, then (3) reduces to marginal coverage (1), following the convention that 1, 0) is a constant. On the other hand, exhaustive equalized coverage (2) would correspond simultaneously selecting all possible sensitive attributes instead of only that identified by A(X,+1). To clarify the terminology, in this paper we will say that an attribute is sensitive if it may identify group affected by algorithmic bias. By contrast, a protected attribute one for which equalized coverage 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 croup-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 novel solution to address this challenge.
3

---

Marginal
AFCP
Exhaustive
(Skin cancer, Flu, Diabetes, Asthma, Stroke, Epilepsy)
|Diabetes, Flu Asthma) (Sev idendffed)
(Asthma)
Real label: Diabetes
(Skin cancer, Flu, Diabetes, Asthma, Stroke, Epllepsy)
(Asthma, Dlabetes)
[Diabetes, Stroke, Asthma) (Sex Idenoffied
Real labll: Stroke
Invalid coverage
Appraximately valid and efficient
Volid but conservative
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.
1.4 Table of Contents
Section 2 presents AFCP method, focusing the special case in which at most 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 Al 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 method efficiently and studies its computational cost. Appendix A7 describes the results of numerous additional experiments.
1.5 Related Works
Conformal inference is a very active research area, with numerous methods addressing diverse tasks, including outlier detection [21-23], classification [24 28), and regression [29-31] Overcoming the limitations of the standard marginal coverage guarantees (1) is a main interest this field.
Some works have proposed conformity scores designed seek high feature-conditiona coverage while calibrating prediction sets for marginal coverage [27, 30J. Others attempt to mitigate over- confidence while training the ML model [32, 33], and several have developed calibration methods for non-exchangeable data, accounting for possible distribution shifts [34-38]. These works are complementary ours, as we focus guaranteeing 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 elassical approach move beyond marginal coverage is label-conditional coverage, where the "protected" groups are defined not based on the features X but by the label itself, Yn+1 [42-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 identify unfairly treated groups by establishing a simultaneously valid confidence bound on group-wise disparities. In principle, their approach can integrated within the selection component 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
2.1 Automatic Attribute Selection
Given a pre-trained classifier, an independent calibration data set D, and a test point Zn+1 = (Xn+1, Xn+1) with an unknown label Yn+1. we will seleet (at most) one sensitive attribute. 1(x E {0. [1]..... {K}}, according to the following leave-one-out procedure.
For each y E [L], imagine + is equal to y, and define an augmented calibration set Dr DU [(x++11 y)}- For each E [n + 1). define also the leave-one-out set D' == D2 ((,, Y.) with y acting as placeholder for Yx+1- Then, for each E [n 1]. we construct a conformal prediction set (X,, for Y; given X; by calibrating the classifier using the data in D y, Any method can 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 Ey,, denote the binary indicator of whether Ćl (X;) fails to cover Y;:
Egg == 1(Y; $ Ć.oo Co (X:)).
After evaluating E for all i [n 1], will assess the leave-one-out miscoverage rate for the worst-off group identified by each sensitive attribute E [K] That is, we evaluate
I++ Fgy:: 1 (( (k)) m} Σ 1 {k}) = m]
6y.k = max [M(
Intuitively, by.k denotes the maximum miscoverage rate across all groups identified by the k-th attribute. Large values of 6y 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 statistical test for the null hypothesis that no algorithmic bias exists. Note that this test can be heuristic since it does not need be exact for our method rigorously guarantee (3). Therefore, we do not need to carefully consider the assumptions underlying this test. As useful heuristic, we define:
Gu = max 8y.k: RE[K]
(5)
and carry out a one-sided t-test for the null hypothesis Hu 4y S against H1 qy a.
If Ho is rejected (at any desired level, like 5%), conclude there exists a group suffering from significant algorithmic bias, and we identify the corresponding attribute through
Á(X = farg max ky
(6)
kE[R]
Otherwise, we set Á(X,+1: y) = 0, which corresponds to selecting no attribute. See Algorithm 1 for an outline of this procedure, function of the placeholder label y.
After repeating this procedure for each y E [L]. the final selected attribute A(Xnt1) is:
Á(X,,) n+ 1) = (WELL) AXNn+1,
Therefore, an attribute is selected if and only if it consistently flagged by our leave-one-out procedure for all values of the placeholder label y E [Z.. 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) construct prediction sets satisfying (3), we pause to make two remarks. First, as long as n is large enough, A(Xn+1, y) is quite stable with respect to both X and y, as each of these variables plays relatively small role in determining the leave-one-out miscoverage rates. Therefore, the selected attribute Á(Xx+1) given by (7) is also quite stable for different values of X 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 leave-one-out approach.
5

---

Algorithm Automatic attribute selection using placeholder test label.
1: Input: calibration data D; test point with features x list of K sensitive attributes;
2:
pre-trained classifier f: fixed rule for computing nonconformity scores; level (0, 1); 3: placeholder label E [L].
4: Assume Yn = y and define the augmented data set D : -D U {(Xn+1.9) 8)}.
5: for E [n++1 1] do
6: Pretend that (X,, Yi) is the test point and D' {Xx,, Y:) is the calibration set.
7: Construct a conformal prediction set Ch (X,) for Y,-
8: Evaluate the miscoverage indicator Ey.; using (4).
9: end for
10: Perform a one-sided test for Ho dy S Saw vs. H1 dy > with dy defined as in (5). Select the attribute A(X,+1:)) y) using (6) if Ho rejected, else set A(X,+1, y) 0.
12: Output: A(Xn+1; y). either a selected sensitive attribute or an empty set.
2.2 Constructing the Adaptive Prediction Sets
After evaluating A(Xn+1,3) y) by applying Algorithm I with placeholder label for Yn+1 for all y E [L], and selecting either an empty set single attribute A(Xn+1) using (7), AFCP constructs an adaptive prediction set for Ya+1 that satisfies (3) as follows.
First, it constructs a marginal conformal prediction set ("(X,+1) targeting (1), by applying the stan- dard approach reviewed in Appendix A1. Then, for each y E [L], constructs conformal prediction
set (X A( Y)) with equalized coverage for the group identified by attribute A(Xx+1 y). as if it had been fixed. This is achieved by applying the standard marginal method based on re- stricted calibration sample indexed by {i E [n] <(X; A(x,+1(nn11. v)) = ((xn+1. 6. A(Xn+1. v))}: J; see Algorithm Al in Appendix Al for further details. Therefore, note that oxX,, A(X,+1, v)) becomes equivalent to (Xn+)))) 1) if A(X,+1,))) 9) = 0. Finally, the AFCP prediction set for Yn+1 is given by:
((Xn+1) (iai)=((((Xxx) (x u u C( A(X
(8)
See Algorithm 2 for an outline of this procedure.
Note that the AFCP set 1(Xx+1) given by (8) always contains the marginal set OTI CTT( (Xn+1); this is essential prove the validity of our approach. Second, in practice the selection Å Á(X,+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 very large prediction set.
Algorithm Adaptively Fair Conformal Prediction (AFCP).
1: Input: calibration data D; test point with features X list of K sensitive attributes;
2:
pre-trained classifier f: fixed rule for computing nonconformity scores; level E (0, 1).
3: for y E [L] do
4: Select an attribute A(Xn+1, y) by applying Algorithm with placeholder label y.
5: Construct C(X A) by applying Algorithm A1 with the attribute A = A(Xx+1.3b v).
6: end for
7: Construct (X"+)))1) by applying Algorithm Al without protected attributes.
8: Output: selected attribute A(X.+1) given by (7) and prediction set C(X,.1) given by (8).
The following result, proved in Appendix A5, establishes that the prediction sets Č(X 1) output by AFCP guarantee adaptive equalized coverage (3) with respect to the adaptively selected attribute Á(X,41). 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 ((2,, {(x,, Y. are exchangeable, the prediction set ((X++1) and the selected attribute A(Xn+1) output by Algorithum 2 satisfy the adaptive equalized coverage defined in (3).

---

3 Numerical Experiments
3.1 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 the marginal benchmark, which constructs prediction sets guaranteeing (1) by applying Algorithm A1 without protected attributes. The second the exhaustive equalized benchmark, which constructs prediction sets guaranteeing (2) by applying Algorithm Al with all K sensitive attributes simultaneously protected. The third is purtial equalized benchmark that separately applies Algorithm Al with each possible protected attribute 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:
[K], and
P\Yn+1 E ((X++1) 6(X,+1, {k)) 2 1 - a, Wk E [K].
(9)
However, 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 AFCPI in our experiments.
For all methods considered, the classifier is based on a five-layer neural network with linear layers interconnected via ReLU activation function. The output layer uses softmax function estimate the conditional label probabilities. The Adam optimizer and cross-entropy loss function are used in the training process, with a learning rate set 0.0001. The loss values demonstrate convergence after 100 epochs of training. For all methods, the miscoverage target level is set at a = 0.1
3.2 Synthetic Data
We generate synthetic classification data mimic medical diagnosis task with six possible labels: Skin cancer, Diabetes, Asthma, Stroke, Flu, and Epilepsy. The available features include three sensitive attributes-ae 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 cyclically repeated as 18, 18 24, 25 40, 41 65, > 65, and Region 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 uniform distribution on [0, 1]. For simplicity, Color is denoted as Xp and the first non- non-sensitive feature as X,. Conditional on X, the label Y is generated based on a decision tree model that depends only on Xo and X1, as detailed in Appendix A7. This model is designed so that the diagnosis label for individuals with Color equal to Blue intrinsically harder to predict, mimicking the presence of algorithmic bias.
Figure 3 shows the performance of all methods as function of the total sample size, ranging from 200 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 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 large when the sample size is small.
Our AFCP method and its simpler variation, AFCPI, not only achieve valid coverage for the Blue group but do with prediction sets that, on average, not much larger than the marginal ones. AFCPI is slightly more robust than AFCP when the sample size is very small, as never fails to select sensitive attribute. This is advantageous in scenarios where we know there is 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 frequen- cies of each sensitive attribute 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.
function of sample size, within the same experiments described
7

---

Coverage Blue
Average coverage
Average size
1.0
Method
0.975
AFCP
0.8
AFCP1
0.950
Marginal
0.6
0.925
Partial
0.900
Exhaustive
200
1000
2000
200
1000
2000
1000
2000
Sample size
Figure 3: Performance of conformal prediction sets constructed by different methods on synthetic medical diagnosís data, function of the total number of training and calibration data points. Our method (AFCP) leads more informative prediction sets (smaller average size) with more effective mitigation of algorithmic bias (higher conditional coverage). The error bars indicate 2 standard errors.
often selecting attributes. However, 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.
Selects Any Attribute
Selects Region
Selects Age
Selects
1.00
0.75
Method
0.50
AFCP
AFCP1
0.25
0.00
200
500
1000
2000
200
500
1000
2000
200
1000 2000
200
1000
2000
Sample size
Figure Selection frequency of different attributes using our AFCP method and variation, AFCPI, in the experiments of Figure 3. As the sample size increases, AFCP becomes more consistent in selecting the most relevant attribute, Color.
Additional results are presented in Appendix 17.1.1. Figures A Al-A3 and Tables A2-A4 summarize the average coverage and prediction size conditional each protected attribute. Figures A4-A7 and Tables A5-A8 study the performance of an extension of our method that also provides valid coverage conditional the true label of the test point.
3.3 Nursery data
We apply AFCP and its benchmarks to the open-domain Nursery data set [49], which was derived from hierarchical decision model originally developed rank applications for nursery schools for social science studies. The data encompass 12,960 instances with eight categorical features: Parents' occupation levels), Child's 's nursery levels), Family form (4 levels), Number children (1, 2, 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- 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 the first category, rounding these perturbed labels This makes the group corresponding to the first category of Parents' occupation intrinsically more unpredictable and hence more prone to algorithmic bias. enhance the challenge of making accurate predictions for this group, it was further sampled 10% of its original size.
nearest integer.

---

Coverage for Occupation
Average coverage
Average size
1.0
1.00
Method
AFCP
0.96
3
AFCP1
Marginal
0.6
0.92
2
Partial
0.4
Exhaustive
500
1000
2000
5000
200
500
1000
2000
200
1000
5000
Sample size
Figure 5: Performance prediction sets constructed by different methods on the Nursery data, as function of the sample size. AFCP leads to more informative predictions with higher coverage conditional on the sensitive attribute, Parents' occupation (shown explicitly for level one).
Figure summarizes the performance of all approaches as function of the total number of training and calibration data points, which varies between 200 and 5000. The results are averaged over 500 randomly chosen test points and 100 repeated experiments. each experiment, 50% of the samples are randomly assigned for training and the remaining 50% for calibration. The marginal benchmark is heavily biased, leading to prediction sets with very low coverage for samples with Parents' occupation in the first category. The exhaustive benchmark is too conservative and results in very large prediction sets unless the sample size is very large. The partial benchmark performs better than the other two benchmarks, but AFCP method still outperforms it, producing smaller prediction sets with valid coverage even for the hardest-to to-predict group. See Table A9 for detailed results.
The results of additional experiments are presented in Appendix A7.122. Figures A8-A12 and Tables A 10-A14 detail average coverage and prediction set size for each sensitive attribute. Additionally. Figures A13-A18 and Tables A15-A20 report on the performance of an extended version of AFCP which also ensured valid coverage conditional on the true test label.
3.4 Additional Numerical Experiments
Figures A19-A21 and Table A21 in Appendix A7.13 summarize additional experimental results using the open-source COMPAS dataset [50]. Moreover, Appendix A7.2 demonstrates the empirical performance of our AFCP extension for outlier detection; see Figures A22-A36 and Tables A22-A34. These demonstrations involve both synthetic data and the open-domain Adult Income dataset [51]. The experiments with the real-world Adult Income data also include AFCP extension that allows for the selection multiple sensitive attributes at the same time.
3.5 Performance of AFCP with Different Sample Sizes
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 as small as 200, difficult to fit 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, 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-sampl settings.

---

3.6 Comparison between AFCP and AFCP1
Both AFCP and AFCPI outperform the benchmark approaches when applied to datasets with small sample sizes, each excelling different scenarios. AFCP is better suited situations where there is uncertainty regarding the presence of significant algorithmic bias, while AFCPI is more effective when prior knowledge suggests that at least one attribute may be biased. For example, in Figure which illustrates case where one group (Color-Bluce is consistently biased, AFCPI I 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 lack of sufficient evidence of algorithmic bias, making it reasonable calibrate the prediction sets solely for marginal coverage.
4 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, 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 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 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-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 com/FionaZ3696, Adaptively
Conf
Acknowledgements
The authors thank anonymous reviewers for helpful comments, and the Center for Advanced Research Computing at the University of Southern California for providing computing resources. M. S. and Y. Z. were partly supported by NSF grant DMS 2210637. M. S. was also partly supported by an Amazon Research Award.
10

---

References
[1] A. Jones, B. Smith, and C. Johnson. Deep learning models for medical diagnosis. Journal of Medical Imaging, 7(2):22108,, 2020.
[2] K. Brown al. Using machine learning for job application screening: A comparative analysis.
In International Conference on Artificial Intelligence in HR, pages 12-21, 2021.
[3] Jiaming Zeng, Berk Ustun, and Cynthia Rudin. Interpretable classification models for recidivism prediction. J. R. Stat. Soc. (A), (30(3):6897222. 2017.
[4] Arun K Kuchibhotla and Richard A Berk. Nested conformal prediction sets for classification with applications to probation data. Ann. Appl. Stat., 17(1):611778, 2023.
[5] Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In IEEE Conference on Computer Vision and Puttern Recognition, pages 427-436, 2015.
[6] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. Int. Conf. Mach. Learn., pages 1321-1330. PMLR, 2017.
[7] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science Conference, page 214-226. Association for Computing Machinery, 2012.
[8] Richard Zemel, Yu (Ledell) Wu, Kevin Swersky, Toniann Pitassi, and Cyntia Dwork. Learning fair representations. Int. Conf. Mach. Learn., 2013.
[9] Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Adv. Neural. Inf. Process. Syst., volume 29, 2016.
[10] Richard Berk, Arun Kumar Kuchibhotla, and Eric Tchetgen Tehetgen. Improving fairness in criminal justice algorithmic risk assessments using optimal transport and conformal prediction sets. Sociological Methods & Research, 2021.
[11] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Adv. Neural Inf. Process. Syst., 32, 2019.
[12] Harris Papadopoulos, Kostas Proedrou, Vladimir Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Eur. Conf. Mach. Learn., pages 345-356, 2002.
[13] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer, 2005.
[14] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. J. Am. Stat. Assoc., 1 (13052)):09441111 2018.
[15] Deborah Hellman. Measuring algorithmic fairness. Virginia Law Review, 106(4):81 1--8666 2020.
[16] Alexandra Chouldechova. Fair prediction with disparate impact: A study bias in recidivism prediction instruments. Big Data, 5(2):153-663, 2017.
[17] 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.
[18] Jianqing Fan, Xin Tong. Yanhui Wu, and Shunan Yao. Neyman- and equal opportunity: when efficiency meets fairness in classification. arXiv preprint arXiv:23 2023.
[19] Rina Foygel Barber, Emmanuel J Candès, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-fres conditional predictive inference. Information and Inference, 10(2):455-482
2021.
11

---

[20] Yonghoon Lee and Rina Barber. Distribution-fiet inference for regression: discrete, continuous, and in between. Adv. Neural Inf. Process. Syst., 34:7448-74 -4599, 2021.
[21] Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. Ann. Stat., 51(1):149 178, 2023.
[22] Ariane Marandon, Lihua Lei, David Mary, and Etienne Roquain. Adaptive novelty detection with false discovery rate guarantee. Ann. Stat., 52(1):157-183, 2024.
[23] Ziyi Liang, Matteo Sesia, and Wenguang Sun. Integrative conformal p-values for out-of- distribution testing with labelled outliers. J. R. Stat. Soc. (B), page qkad138, 2024.
[24] Jing Lei, James Robins, and Larry Wasserman. Distribution-FFi prediction sets. J. Am. Stat. Assoc., 108(501):288-277, 2013.
[25] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. J. Am. Stat. Assoc., 1 114(525):223255 2019.
[26] Aleksandr Podkopaev and Aaditya Ramdas. Distribution-free uncertainty quantification for classification under label shift. In Uncertainty in Artificial Intelligence, pages 144-853. PMLR, 2021.
[27] Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. Adv. Neural Inf. Process. Syst., 33, 2020.
[28] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Un- certainty sets for image classifiers using conformal prediction. In Int. Conf. Learn, Represent., 2021.
[29] Jing Lei and Larry Wasserman. Distribution-fres free prediction bands for non-parametric regression.
J. R. Stat. Soc. (B), 76(1):71-96, 2014.
[30] Yaniv Romano, Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. In Adv. Neural Inf. Process. Syst., pages 3538-3548, 2019.
[31] Matteo Sesia and Yaniv Romano. Conformal prediction using conditional histograms. Adv. Neural Inf. Process. Syst., 34, 2021.
[32] Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, and Yanfei Zhou. Training uncertainty- aware classifiers with conformalized deep learning. In Ady. Neural Inf. Process. Syst., volume 35, 2022.
[33] Ziyi Liang, Yanfei Zhou, and Matteo Sesia. Conformal inference is (almost) free for neural networks trained with early stopping. In Int. Conf. Mach. Learn., 2023.
[34] Rina Foygel Barber, Emmanuel J Candès, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. Ann. Stat., 51 2023.
[35] Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. Adv. Neural Inf. Process. Syst., 32, 2019.
[36] Isaac Gibbs and Emmanuel Candès. Conformal inference for online prediction with arbitrary distribution shifts. arXiv preprint arXiv:2208.0844 2022.
[37] Yachong Yang, Arun Kumar Kuchibhotla, and Eric Tchetgen Tchetgen. Doubly robust calibra- tion of prediction sets under covariate shift. R. Stat. Soc. (B), page qkae009, 2024.
[38] Ziyi Liang, Tianmin Xie, Xin Tong, and Matteo Sesia. Structured conformal inference for matrix completion with applications to group recommender systems. arXiv preprint arXiv:2404. 17561, 2024.
[39] Charles Lu, Andreanne Lemay, Ken Chang, Katharina Hoebel, and Jayashree Kalpathy-Craman Fair conformal predictors for applications in medical imaging. AAAI Conference on Artificial Intelligence, 11112008812666 06 2022.
12

---

[40] Fangxin Wang, Lu Cheng, Ruocheng Guo, Kay Liu, and Philip S. Yu. Equal opportunity of coverage in fair regression. Adv. Neural Inf. Process. Syst, 2023.
[41] Meichen Liu, Lei Ding, Dengdeng Yu, Wulong Liu, Linglong Kong, and Bei Jiang. Conformal- ized faimess via quantile regression. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Adv. Neural Inf. Process. Syst. 2022.
[42] Vladimir Vovk, David Lindsay, Ili Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical report, Royal Holloway, University of London, 2003. On-line Compression Modelling project.
[43] Tiffany Ding, Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Ryan Tibshirani. Class-conditional conformal prediction with many classes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
[44] Tuve Löfström, Henrik Boström, Henrik Linusson, and Ulf Johansson. Bias reduction through conditional conformal prediction. Intell. Data Anal., 19(6)1355-1375, nov 2015. ISSN 1088-467X.
[45] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid conformal prediction. In Int. Conf. Learn. Represent,, 2023.
[46] Isaac Gibbs, John J Cherian, and Emmanuel J Candès. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305.12616 2023.
[47] John Cherian and Emmanuel J. Candès. Statistical inference for fairness auditing. arXiv preprint arXiv: 2023.
[48] Ying Jin and Zhimei Ren. Confidence on the focal: Conformal prediction with selection- conditional coverage. arXiv preprint arXiv:2403.08 038668 2024.
[49] Vladislav Rajkovic. Nursery. UCI Machine Learning Repository, 1997. DOI: https:/ddo..rg/11.444////P
License: CC-BY 4.0.
[50] Jeff Larson. Surya Mattu, Lauren Kirchner, and Julia Angwin How we ana- lyzed the compas recidivism algorithm. https://wwi wwwpwppica..a.o.oooo orgg/rricler///////o/o/oo...../e how-we-a ave-analyeed--a the compas- rentiasseeiiiiismm. recidviin--llgorthhhm 2016.
[51] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: wttpoooooo/...22//////22222 License: CC-BY 4.0.
[52] Bat-Sheva Einbinder, Stephen Bates, Anastasios N Angelopoulos, Asaf Gendler, and Yaniv Romano. Conformal prediction is robust to label noise. arXiv preprint arXiv:2209.1422 2022.
[53] Ge Yan, Yaniv Romano, and Tsui- Wei Weng. Provably robust conformal prediction with improved efficiency. In The Twelfth International Conference Learning Representations, 2024. URL http::://////ttt //t::///ppnee http///pppeeeeeeee//e/e//e net htt///orrmmddB/hhhee
[54] Asaf Gendler, Wsui-Wei Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. In International Conference Learning Representattonss 2022. URL https: / //openreview. net sett/forum?ide 91111idddd..BB11P11.
[55] Shai Feldman, Bat-Sheva Einbinder, Stephen Bates, Anastasios N. Angelopoulos, Asaf Gendler, and Yaniv Romano. Conformal prediction is robust to dispersive label noise. In Harris Papadopoulos, Khuong An Nguyen, Henrik Boström, and Lars Carlsson, editors, Proceedings of the Twelfth Symposium on Conformal and Probabilistic Prediction with Applications. volume 204 of Proceedings of Machine Learning Research, pages 624-626. PMLR, 13-15 Sep 2023. URL https: htttttp://pproccedingg..oo mlr www.ppressssee.... ppress/v204/ wttp//200/eeaaa// dman23a. html.
[56] Matteo Sesia, Y. X. Rachel Wang, and Xin Tong. Adaptive conformal classification with noisy labels, 2024. URL htttps://aaatee wwwaaa.vogg....a..aa......a...ea org/ aa/////s//30 .05092.
[57] Glenn Shafer and Vladimir Vovk. A tutorial on conformal inference. J. Mach. Learn. Res., 9(3), 2008.
13

---

[58] Tuve Löfström, Henrik Boström, Henrik Linusson, and Ulf Johansson. Bias reduction through conditional conformal prediction. Intell. Data Anal. 1966):355-11355 2015.
[59] COMPAS Data Set. http////t...copppppppaaaaaa//rrp July, 2024.
Accessed:
14

---

A1 Review of Existing Conformal Classification Methods
Algorithm Al 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 the standard approach for constructing prediction sets with marginal coverage.
Algorithm A1 Conformal classification with equalized coverage for fixed protected attributes.
1: Input: calibration data D; test point with features X list of protected attributes A;
2: pre-trained classifier f: pre-defined rule for computing nonconformity scores;
3: nominal level a E (0, 1).
4: Define the calibration subset
I(Xu+1, (ix) - A))
5: for y E [T] do
6:
Compute the nonconformity scores Sy for I(X A) ((Xx+1, using f.
7: Compute the conformal p-value:
3 (Xn+1)= = I( A): S S 5" Sh
1 [X(n+1,,
8: end for
9: Construct a prediction set using C(Xn+1)= {y E [4] uz (Xn+1) 2 a).
Output: prediction set Č( ((xn+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 fixed list of protected attributes.
Algorithm A2 Conformal p-value with equalized FPR for fixed protected attributes.
Input: calibration data D; test point Zn+1: list of protected attributes A; pre-trained one-class classifier f: pre-defined rule for computing nonconformity scores; nominal level (0, 1).
2:
3:
4: Define the calibration subset
I(Zn+1, A) {i [m] p(Zz, A) ((Zn+1,
5: Compute the nonconformity scores S₁ for i E I(Z++1, A) U (2n-1) using f.
6: Compute the conformal p-value:
a( (7n+1) = 1+ ++EE E A) A): :3. 5..5 &Sut1l
1 [[
7: Output: conformal p-value úl ((Zn1)).
A2 Methodology Extension: AFCP with Multiple Selected Attributes
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 similar manner, as explained later.
A2.1 Automatic Multiple Attribute Selections
Given pre-trained classification model, an independent calibration data set with size n, and test point Zn+1 (Xn+1, Ya+1) with unknown label Y,+1, Algorithm I in Section 2.1 introduces
15

---

the AFCP component to select one sensitive attribute according to the leave-one-our procedure. Intuitively. selecting two sensitive attributes requires executing Algorithm 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 E [4]. assuming Yn+1 = Algorithm 1 is run with all K sensitive attributes for the first iteration obtain the first selected attribute Á A'(X.+1. v) {0, {1)..... {K}}. If A' y) * 0, Algorithm 1 is run again using the sensitive attributes [K] (X and can get the second selected attribute Å (X E (0, (1),..., {K}) (",,,, y). Therefore, the identified attributes for test feature X with placeholder y for the test label is the union of the two A(Xn+1, y) = A (X y) U A (X,+1.9) This procedure is outlined in Algorithm A3.
After repeating this procedure for each y E [L]. the final selected attribute A(Xn+1) is:
Á(X,+ Aeer))A((naa
(A10)
Algorithm A3 Two attributes selection using a placeholder test label.
1: Input: calibration data D; test point with features X 1; list of K sensitive attributes;
pre-trained classifier f: pre-defined rule for computing nonconformity scores; 3: nominal level a E (0, 1). placeholder label y E [T.]-
2:
4: Select the first attribute Å (X by applying Algorithm with placeholder label and sensitive attributes [K].
5: if' A (X y) # 0 then
6: Select the second attribute (² by applying Algorithm with placeholder label and sensitive attributes [K] 1 (X
7: end if
8: Output: A(Xn+1,9) v) = A' (X.+ y) U A (X which is set of an empty set, set
including one or two selected sensitive attribute(s).
A2.2 Constructing the Adaptive Prediction Sets
After selecting a subset of attributes A(X,+1) using (A10), which may empty, or include one or two attributes, AFCP constructs adaptive prediction set for Y that satisfies (3) as follows.
First, it constructs marginal conformal prediction set Ó" (Xn+1) targeting (1), by applying Algo-
rithm A1 without protected attributes. Then, for each E [T.), it constructs conformal prediction set Č(Xn+1::4 A(X A((,+1.1) y)) with equalized coverage for the group jointly identified by attributes A(Xm+198) This can be achieved by applying Algorithm A1 with protected attributes Á Á(Xn+1.8) v). Lastly, it constructs a conformal prediction set (xn(X with equalized coverage separately for each protected attribute é Uye|z] v). by applying the standard approach in Algorithm Al on the subsets indexed by {i E [n] o(X,, (0)) o(Xn+1, {{})}.
Finally, the AFCP prediction constructed using up two selected attributes is given as:
C(Xat1) (m (1n())1)) (x
{UEEUAÁ(X....)) 6 X }). (A11)
See Algorithm A4 for an outline of this AFCP extension.
Theorem A1. If ((x,, Yo are exchangeable random samples, then the conformal prediction set C(Xn+1) and the selected altributes Á(X A(Xn+1) output by Algorithm A4 satisfy the adaptive equalized coverage defined in (3).
16

---

Algorithm A4 AFCP with two selected attributes.
I: Input: calibration data D; test point with features Xn+1i list of K sensitive attributes; pre-trained classifier S: pre-defined rule for computing nonconformity scores; 3: nominal level a E (0,1) 1).
2:
4: for y E [L] do
5: Select attrributes)) A(Xn+1,3) y) by applying Algorithm A3 with placeholder label y-
6: Construct A( by applying Algorithm Al with protected attribute(s) A =
A(Xn+1,8).
7: end for
do 9: Construct (X E) by applying Algorithm A1 with protected attribute {E}.
8: for A Uye(r]
10: end for
Construct É.T (x++1) by applying Algorithm A1 without protected attributes.
12: Define the final selected attribute(s) A(Xn+1) using Equation (A10).
13: Define the final prediction set C(Xn+1) using Equation (A11).
14: Output: A(Xn+1) and C(X,+1).
A3
Methodology Extension: AFCP with Label Conditional Coverage
This section extends the AFCP method with adaptive equalized coverage that is also conditional on the true test label. We focus the main implementation of AFCP, where it can select up 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:
P E C(Xn+1)) Ya+1 = v] 1-
- o, Vy E [Z].
(A12)
Intuitively, this coverage ensures that the prediction sets constructed are valid for each group with the test label y for all possible values of y [Z]. This coverage offers 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 cabel-conditional exhaustive equalized coverage [17], defined as:
P|Y,+1 E ((Xx+1)) Yx+1 = y, 6(X,+1, [K]] 2 1 - a, Vy E [L].
(A13)
Achieving this label conditional exhaustive equalized coverage involves applying the standard conformal classification method (outlined in Algorithm Al) 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 large number of sensitive attributes or response labels are presented.
Our AFCP method strikes balance between the two approaches to achieve label-conditional adaptive equalized coverage:
P[Yn+1 E C(Xn+1)) | Yx+1 = y, ((Xx++1,(XXx2)
2 a. Vy [4],
(A14)
which guarantees that the true test label is contained within the prediction sets with high probability for the groups defined by the selected attribute Á(Xa+1) and the test label y for every y E [Z].
A3.1 Automatic Attribute Selection
Given a pre-trained classification model and an independent calibration data set with size n, for each placeholder label y E [L] for Y.+1, the AFCP method with label-conditional adaptive equalized coverage (A14) selects the sensitive attribute A(X,, (++1.3) y) by simply applying Algorithm using the label-restricted calibration data DD, (i E [n] Y, = y). After repeating this process for each
y E [L]. the final selected attribute A(X..1) 1) is again given by
Á(Xn+1) A
(A15)
17

---

A3.2 Constructing the Adaptive Prediction Sets
After selecting A(Xn+1.3) v) by applying Algorithm with placeholder label based on the label- restricted calibration data D, {i E [n] Y; y) and selecting sensitive attribute A(Xn-1).
AFCP constructs an adaptive prediction set for Yn+1 that satisfies (A14) as follows.
For each y E [T.] firstly construct conformal prediction set (Xn+1, y) by applying Al- gorithm A1 using the label-restricted calibration set Dy without considering protected attributes. Then, it constructs another conformal prediction C(X++1, A(Xn+1;y)) with equalized cov- erage for the group identified by both the selected attribute A(Xn+1, y) and label y- This can be achieved by applying Algorithm A1 based on subset of the calibration samples indexed by I(X++1,)) v) {i E Dy @(X,, A(X+1, u)) (xXn for any given placeholder label, prediction set constructed in this step satisfies the label conditional adaptive equalized coverage long as the selected variable using that placeholder label is fixed.
(,))) Lemma Al shows that,
Lemma A1. If (X,,, YO) are exchangeable and the selected attribute A(Xn+1, y) is fixed for some placeholder label y. then, the prediction set C(Xx+1, A(Xn+1xXn) v)) constructed by calibrating on I(X n+1, y) satisfies
P|Y,+1 ((XX++,,AXXxHH
Ya+1 = ((x+(X, A(X --a,
for any ū E [L].
Lastly, the final AFCP prediction set is obtained by:
((x++1) {Ug che (X 8) u uU
A(Xn+1,0))
(A16)
The procedures form AFCP prediction sets with the label-conditional adaptive equalized cover- age (A14) is summarized in Algorithm A5.
Algorithm A5 AFCP with label-conditional adaptive equalized coverage (A14).
1: Input: calibration data D; test point with features X,+1: list of K sensitive attributes;
2: pre-trained classifier f: pre-defined rule for computing nonconformity scores;
3: nominal level a E (0, 1).
4: for E [4] do
5: Define the label-restricted calibration set D, {i E [m] yy=yh
6: Select an attribute Á( A(Xn+1,y) v) by applying Algorithm with placeholder label on Dy.
7: Construct C(Xx+1, A(X by applying Algorithm Al with protected attributes
A(Xu+1, V) on Dy.
8: Construct Öd (Xn++11.)) by applying Algorithm Al on Dy.
9: end for
Define the final selected attribute Á Á(Xa+1) using Equation (A15)
11: Define the final prediction set C(X,+1) using Equation (A16).
12:
Output: A(Xn+1) and C(X++1).
Theorem A2. If (X,, 1D are exchangeable random samples, then the conformal prediction set ((xn+1) and the selected attribute Á(X,+11) output by Algorithm AS satisfy the label-conditional adaptive equalized coverage defined in (A14).
A4 Methodology Extension: AFCP for Outlier Detection
Consider a dataset D = ( containing n sample points drawn exchangeably from an unknown distribution Pz. Consider additional test point Za+1. In the outlier detection problems, our AFCP method aims to study whether Zn+1 ~ Pz by constructing a valid conformal p-value ai 77++) conditional on the group identified by the selected attribute A Á(Znt1), that is:
Plū(Zn+1) aal Φ(Zn+1, A(Zn+ S a.
(A17)
18

---

for any a E (0, Intuitively, this guarantees that, on groups defined by the selected attribute A(Zn+1), the conformal p-value is super-uniform, therefore controlling the FPR (the probability of rejecting the null hypothesis that zn+1 is an inlier when it is true) below a.
A4.1 Automatic Attribute Selection
Given pre-trained one-class classifier f. an independent calibration dataset D, and a test point Zn+1+ method selects sensitive attribute A(Zn+1) {0, {_)..... ..... } according to the following leave-one-out procedure. Sometimes, no attribute may be selected, denoted by A(Z++1) - 0.
Define an augmented calibration set D = D (Z+tZ For each i E [ni + 1], define also the lot set D := D' \ {Z,). Then, for each i [n ( 1], we compute conformal p-value (Z:) for Z using the data in DD to test if Z; is an outlier. This can be accomplished by running Algorithm A2, using D as the calibration data and 7, as the test point, and with the convention that smaller nonconformity scores suggest Z, 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 G (Zi) provides stronger evidence to reject the null hypothesis Ho,: Zi is an inlier. Let E, denote the binary indicator of whether Ho.s rejected:
E = 1 (z) S a).
(A18)
After evaluating E, for all i E [n 1). we will assess the leave-one-out FPR for the worst-off group identified by each sensitive attribute [K]. That is, we evaluate
E E. 1 [k))= mm] m]
62
max
(A19)
mE m
Σ 1 1 Z, (k)) = m]
Intuitively, 6g 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 Zn+1 is inlier. Large values of 5c 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:
i max òk; KE[K]
(A20)
and carry out a one-sided t-test for the null hypothesis Ho q S against H1 q
If Ho 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
Á(Zn+1) = {aag max ) kE(K]
(A21)
Otherwise, we set Á(Zn+1) 1) = 0, which corresponds to selecting no attribute. See Algorithm A6 for an outline of this procedure.
A4.2 Evaluating the Adaptive Conformal P-Vule
After selecting either a single attribute empty set A(Xn+z) that corresponds to 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,+1 is outlier that satisfies (A17). This can be simply achieved by applying the standard conformal method outlined in Algorithm A2 based on a restricted A
calibration sample indexed by I I(A(Zx+1)) = {i [m] o(Z,, A(Zn+1)) See Algorithm A7 for a summary of AFCP for outlier detection tasks.
Theorem A3. If (Z are exchangeable random samples, the conformal p-value ú (2n+)) and the selected attribute A(Zn+1) output by Algorithm A7 satisfy (A17).
19

---

Algorithm A6 Automatic attribute selection for outlier detection.
1: Input: calibration data D; test point Zn+1i list of K sensitive attributes;
2:
pre-trained one-class classifier f: pre-defined rule for computing nonconformity scores; 3: nominal level a E (0, 1).
4: Define the augmented data set D
(Zn+1}-
5: for E [n+ do
6: Pretend that Z, the point and 22 {2.3 is the calibration set.
7: Compute conformal p-value (Z,).
8: Evaluate the false positive indicator E, using (A18).
9: end for
Compute & using (A20).
11: Perform a one-sided test for Ho 7 S vs. H1 7
12: Select the attribute A(?m-1) using (A21) if Ho is rejected, else set A(Zn+1) = 0.
13: Output: A(Zn+1), either selected sensitive attribute empty set.
Algorithm A7 AFCP for outlier detection.
1: Input: calibration data D; test point Zn+1: list of K sensitive attributes;
2:
pre-trained one-class classifier fü pre-defined rule for computing nonconformity scores; nominal level a E (0, 1).
4: Select a sensitive attribute 1 by applying Algorithm A6.
5: Evaluate a( 11+1) by applying Algorithm A2 with protected attribute Å A(Zn+1).
6: Output: ü ((
A4.3 AFCP for Outlier Detection with Multiple Selected Attributes
AFCP for outlier detection problems can be readily extended to select sensitive attributes where J 1. This is achieved by repeatedly applying the single attribute selection procedure described in Algorithm A6 times. Each time, the algorithm selects a (possibly empty) subset of attributes
A(Zn+1)' from the list of sensitive attributes excluding the previously selected attribute A(Zn+1)* ) The final set of selected attributes is given by A(Zn+1) = A/22A(Zn+ )) outline of this procedure.
See Algorithm A8 for an
Algorithm A8 Multiple attributes selection for outlier detection.
Input: calibration data D; test point Zn list of K sensitive attributes;
2: pre-trained one-class classifier f: pre-defined rule for computing nonconformity scores;
3: nominal level E (0, 1); number of selected attributes J.
4: Denote RD = [K].
5: for E JJ do
6: Select attribute Á(Zn+1) by applying Algorithm A6 with sensitive attributes K3-1
7: Update the list of sensitive attributes K Ki-1 A(Zn+1>.
8: end for
9: Output: A(Zn+1) = U/= A(Zm+ an empty set or set of selected attributes.
After selecting a attributes A(Zn+1), which might be empty or include one more sensitive attributes, AFCP constructs an adaptive conformal p-value satisfying (A17). This can be easily achieved by applying Algorithm A2 with protected attributes Á(Zn+1). Algorithm A9 summarizes the AFCP implementation for outlier detection that allows selecting multiple protected attributes.
Theorem A4. If ( (Z,)*t nn+1 are exchangeable random samples, the conformal p-value àt (2n+1) and selected attributes A(Zn+1) output by Algorithum A9 satisfy (A17).
20

---

Algorithm A9 AFCP for outlier detection with multiple selected attributes.
I: Input: calibration data D; test point Zn+1; list of K sensitive attributes;
2: pre-trained one-class classifier f: pre-defined rule for computing nonconformity scores;
3: nominal level a E (0, 1): number of selected attributes J.
4: Select up to J sensitive attributes A(Zn+1) by applying Algorithm A8.
5: Evaluate ú( Zn+1) by applying Algorithm A2 with protected attribute A(Zn+1).
6: Output: ú 11
A5 Mathematical Proofs
Proof of Theorem I. Consider an imaginary oracle that has access to the true value Yn+1. Denote Áo (Xx+1, Y2+1) as the sensitive attribute selected by this oracle by applying Algorithm with the represent the correspond- ing output prediction set by applying Algorithm Al with the protected attribute (N Yn+1). Consider also (X.++))) ), the standard prediction set with marginal coverage (1).
true Yx+1 instead of a placeholder label. Let C* (" ( Yn-1))
The main idea of our proof is to connect the output prediction set C(X++1) and selected attribute A(Xa+1) from Algorithm to those of the imaginary oracle described above. Throughout this proof, we adopt the convention that ((Xn+1, 0) O.
To establish this connection, note that the attribute A(Xn+1) selected by Algorithm 2 either empty, Á (Xa+1) = 0, or a singleton, A(X,+1) {k} for some & E [K]. In the latter case, Á A(X++1) A A(X.+1,00 0). Vū E [Z], and thus A(Xn+1) = (X,=11 Y.+1) almost-surely. Therefore,
P[Yn+1 E ((X++1) I ((Xx+1,,((X+1)))
2 min Pf ((Xx+1) | ())++10))]
P|Y++1 E ((N+t)) ((Xn+1, Å (X Yo+i))l
min P(Yn+1 ((x++1))
(A22)
P| E ((N+41) o(Nn+1, (X Ynttill
min Plyn+1 (Xn+t)))
PY E (X Yn+1)) ((Xn+1, Áo &
where the last inequality follows from the facts that (m"(n+2) c ((Xn+1) and (X Á (Xn41, Yn+1)) C(X,41) almost-surely. Next, we only need to separately lower- bound by 1 - a the two terms on the right-hand-side of (A22).
The first part of the remaining task trivial. already well-known that P(Y E (m' 2 1 a; see 133,57,,
To complete the second part of the remaining task, note that the oracle-selected attribute Áo (Xx+11, Yn+1) ) is invariant to any permutations of the exchangeable data indexed by [n- 1]. There- fore, the data points are also exchangeable conditional on the groups defined by Á Yn+1). This means we can imagine the protected attribute (XXnti, Yn+1) is fixed, and the oracle prediction set C (Xnn+1, A (Xxx41, Yo+1)) is simply obtained by applying Algorithm Al to exchangeable data
21

---

using a fixed protected attribute. This procedure is the same as the main algorithm in [17] and has guaranteed coverage above 1 a; see Theorem in [17].
Proof of Theorem AI. Similar to the proof of Theorem 1, consider an imaginary oracle that has access to the true value of Yz+1- Denote (Xn+1, Yn+1) as the (possibly empty, one, or two) sensitive attribute(s) selected by this oracle by applying Algorithm A3 with the true Yn+1- Let (" A (X x++1)) represent the output prediction set by applying Algorithm Al with the protected attribute(s) A (Xn+1, Yn+1). Consider also ("nn()))),, the standard prediction set with marginal coverage (1), and (x the prediction set with valid coverage conditional on groups identified by fixed attribute {f]-
The key idea of our proof is again connect the practical prediction set C(X,+1) and selected protected attributes A(x,+1) of Algorithm A4 to those of the imaginary oracle described above. Throughout this proof, we adopt the convention that Φf xx+1,0) O.
To establish this connection, note that the attribute(s)) A(Xn+1) selected by applying Algorithm A3 falls into one of the three possible cases almost surely: (a) A(Xn+1) 0. (b) A(Xn+1) = ( 1n+,), and (c) 1(X,+1) A(Xa41) AX Y2+)). The last scenario happens when the oracle selects two attributes, and the A(Xx+1) contains only one of them. For clarify of the notation, we denote the last case using A(Xa+1). Therefore.
P\Y++1 E ((Xn+1)
min P(Yn41 E C(Xx+1) 6(Xn+1, 0)],
P|Y++1 ((X++1) 6(Xn+1, (X 1n-1))l,
P|Y++1 (((,t1) @(Xn11, 10011,,(((+11)) A(Xn+1)]]
min P(Y E ((X++1)),
(A23)
P|Y E ((X+1)) ((Xn+1, Á (Xx+1 Yn- 1))]
P|Y++1 E ((X+41) ((Xn+1, A A(Xn+1))]
2 min P(Yn+1 e (x"(x+))),,
P|Y++1 E (x A Pn (o()))@((()))) ('(Xnt, Yati)),,
P|Y E UseA (X p(Xn+1, ((X,,,,,(Xxxi)))) A(Xu+1))]
where the last inequality follows from the facts that (m(Xu+1) S Č(Xn-1): ("(Xn-1,'(X,, (,n41,Yn41)) S C(Xx+1), and A O C C(Xnt1)
almost-surely.
Next, we show how to separately lower-bound by a 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 lower- bounding the coverage of the third term. Because the oracle-selectdd attribute(s) (X Yn+1) are invariant to any permutation of the exchangeable data indexed by [r + 1). we can treat each of the two clements in A A (Xx+11 Yn+1) as fixed. Without loss of generality, let e and &g denote the first
22

---

and the second element respectively, A(Xn+1) = & or A(Xn+1) = l2 with probability 1. Then,
Plyn+1 E ULe (Xnt1,) () ((x,+t,
2 min P|Y E (11 (Xn+1, ((Xn11, 41),
P| E C (Xn+1, / o(Xn+1,
(A24)
min
P|Yn+1 E (X ((x+)))((xx))))))
P(Ya+1 E (Xnt1,) ( (X
min 0, a aa);
where the inequality of the last line of (A24) is proved in [17] with fixed attribute & and &a respectively, Lastly, realize that Ax (x S A A(X.11.)) (X e) S C(Xn+1) almost-surely, the proof is completed.
Proof of Theorem A2. Similar to the proof of Theorem 1, consider an imaginary oracle that has as the sensitive attribute selected by this oracle by applying Algorithm based on a subset of the calibration data indexed by Dy,4. {i [n] Y = ) Let (X ('(Xn+1, Yn+1)) represent the output prediction set by applying Algorithm A1 with the protected attribute ( Consider also ČtC (1x(xx1 Yn+1), the prediction set with label-conditional coverage obtained by running Algorithm Al using Dy without any protected attributes.
access to the true value of Yx+1. Denote (Xn+1 Yn+1)
To establish this connection between the output prediction set C(Xx+1) and the selected attribute Á(X.41) of Algorithm A5 and these of the imaginary oracle, note that the selected attribute Á(Xa+1) must be A(X,+1) = 9 or A(Xn+1) = (X,,,, 1n+1).
Therefore, for any E [Z].
P|Y,+1 E (((x+t)) Yzt1 y, (X A(Xn+1))]
2 min P(Yn+1 E ((Xx+1) Yn+1 =y ol 6(Xm=+100))
P(Y++1 E (((4+1) Ynt1= = V, A (n-1))))))))))
= min P(Yn+1 E ((Xx+1) |n+1= =);
P(Y441 E ((Xn+t) Ya41 = y, A Yn
2 min P(Yn+1 E (* Yut1) Yat1 = =y),
P(Y+41 E (X44,, Yn+1)) Yat1 = y, @(Xn+1, A (Xnn2, Ynt1ll)
(A25)
where the last inequality follows from the facts that Cte (le X S C(Xntz) and ( (X Yn+1)) S ((Xx+1) almost-
23

---

Next, we only need to separately lower-bound by 1 - a 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 P(Yn+1 Ód (Xn+1,, Yn+1) Y = y) 2 1 a; see [13, 47, 58].
Next, we prove the lower bound for the second term. Fix any y E [L]. and assume Y,+1 = First, note that the oracle-sclected attribute A"(Xx+1, Yn+1) is invariant to any permutations of the exchangeable data indexed by Dy U (Xx+1, y). Therefore, the data points are exchangeable conditional on the group identified by the oracle-selected attribute (X,,11 Yn+1). This means that we can imagine the protected attribute A'(Xn+1: Yn+1) is fixed, and the oracle prediction set C* (X Y ]) is simply obtained by applying Algorithm Al to exchangeable data using a fixed protected attribute. This procedure has guaranteed coverage above - a; see Lemma Al.
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 ((A(Zn+1)) denotes a subset of the calibration data D that has the same value of the selected attribute the test point. To prove (A17), it suffices to show that the nonconformity scores {8, : i I I(A(Zn+1)) U {Zn+1}1 } are exchangeable. Indeed, if the scores are exchangeable and almost surely distinct (which can be casily achieved by adding continuous random noises), then the rank of Sa+1 is uniformly distributed over the discrete values {1, II I(A(Zn+1)) + 1}. Consequently, the conformal p-value u ((Zu+1) constructed by Algorithm A7 follows a uniform distribution Unif(1
o 11 A(Zz+1))) [(A((2+)))I++T [Z(A(Z++1))+1 +I .]).. This implies that P(ū(Zn+1) I a
Even if the nonconformity scores are not almost surely distinet, one can still verify that the distribution of ú ū(Zn+1) is super-uniform. Combining both cases, we have P( (Z(+)) & a alo(Zn+1, A(Zn-1))) I a for any a E (0, 1).
We complete the proof by showing that the nonconformity scores {Š) : 2I) are exchangeable. Define an arbitrary permutation function applied on DU {Zn+1} and denote the permuted dataset as (D). We first run Algorithm A7 based on D to select the sensitive attribute Á( A(Zn+1). Next, assume in 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 A' 12n Essentially, A' (Zn+1)= = A(Zm+1). This is because the computation of conformal values 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 U }. This implies that the attribute selected by Algorithm A6 A(Zn+1) can be treated as fixed, and the nonconformity scores computed on the subset I(A(Zn+ U U [Zn+1 are simply reordered in the parallel world, i.c.,
(800)) : I(A(Zn+1))
oi ( 12
(Zn+1)))
where ō is the permutation obtained by restricting on U Hence, we have ($, : I(AZ.++)) (Zn _ (S'00) : : I(A [Z++1])
= T I(A u (Zn+13)).
where the equality in distribution is implied by D _ (D))
Proof of Theorem A4. This proof is the same as the proof of Theorem A3 since the multiple selected attributes Å(Zn41) are invariant to any permutation of the calibration and test data.
Proof of Lemma Al. This proof is minor extension of the proof of Theorem I in [17], with the difference that we additionally condition on the true test label.
Fix any ÿ E [L], and suppose Yo+1 = ÿ. For a placeholder label y, consider a subset of the calibration data D indexed by I(Xn+1,2) y) {i D Y 5, o(X,, A(X v)) = o(Xx+1, A(Xx+1 v))).
24

---

Since f(X,, Y= formity scores S; evaluated the subset I(X y) U {(x+11, y)} are also exchangeable.
;= are exchangeable and the protected attribute A(Xn+1, y) is fixed, the noncon-
Further, denote Q(Xn+1: as the [(1 (1- I(xxI(((n1))))) y)hh smallest value of (Si)xe 199) By the quantile lemma [13, 17, 57], for any E (0, 1),
P|Y++1 A(
Yx+1 U. (f A(Xn+1, y))]
P[ S (( Yn+1= W, ((xn11x A(
(A26)
2 a.
A6
Computational Shortcuts and Efficient Implementation
A6.1
Outlier Detection
Given a pre-trained one-class classifier, consider a calibration dataset D of size n. Let K denote number of sensitive attributes, and for each attribute k E [K]. let Mr. E N denote the count of its possible values. Denote M maxx M₁ as the maximum count across all attributes.
AFCP for outlier detection outlined in Algorithm A7 has the following computational cost.
Analysis for single test point
The cost of computing the false positive indicators for every sample in DU {Zn+1} takes Onn-log n).. Breaking into steps, for every data in DU [n+1). ( compute their nonconformity scores takes (n). Their associated conformal p-value can be computed at once by sorting all scores and keeping track of their ranks, which takes O(n log n))
Then, selecting the sensitive attributes requires On K -M).
Once the attribute is selected, the cost of applying conformal prediction conditional on the group identified by the selected attribute is (1) because the subset of the group has been found the last step.
Hence, the total cost of rumning Algorithm A7 for a single test point is O(n log + nKM)
Analysis for m test points
The cost of computing the false positive indicators for every sample in D U + h takes O(n (m + log n)). This can be derived by rewriting the conformal p-values for all j 'D U [Zu+t} } and for all t E [m] follows:
Σ
1(S < 5,)
Új
(EDU(Zn+t)
rank(S,) among (5theD + 1(5 S $;))
I+n
Computing the nonconformity scores for all samples in D U (2n+e)m U evaluating the ranks takes (n log and comparing Sx++ and 53 costs O(n m).
costs O(n + m),
Selecting the sensitive attribute costs On (mmmmmmm + M K (n + m)). Breaking in steps, for each test sample Zu+t, the worst FPR for attribute k; defined in (A20), can be rewritten as follows:
EiEDU(Z E., 16, (k) m
8t, max mE(Ma)
ΣiEDU 1[0 (k)) = m}
EieD Ee, (b((, (k)) = m) + Fe, (bb(,, (k)) = m)
mE[Ma]
EiED 1(0 (k)) =m] + 1( (1((( Zi, (k)) =m)
EiED(k.) Ext + E 1fo(Z,, (k:) m)
= max mE[Ma]
(D(km)) + 1 (2. (k)) =m)
25

---

where (kk, m) represents subset of the calibration data indexed by {i E D oZ (kt) m]. The trick we use is that the identification of subset [kk, m) does not depend on the test sample L and can be reused to calculate the FPR for every test sample ( 1 In specific,
identifying (k; m), Wk E [ m E [M&]] takes (n- M K). For each [(k: m). computing (ieD(k.m) E Vt E [m]] takes O m)) -m), and computing E (o( Z4, [k]) = m]
takes (m)) Therefore, repeating this process for all ((k, m), k E [K] m E [Mx] in total takes O(n m). Lastly, finding the maximum FPR across all attributes takes O O(m M K).
Hence, the total cost of running Algorithm A7 for m test samples is On log n + M (n/K((++pp) ()+m)).
A6.2 Multi-Class Classification
Given a pre-trained multi-class classifier, consider a calibration dataset D of size n. Let denote the total number of possible labels to predict, and let K denote the number of sensitive attributes. For each attribute & E [K]. let Mg E N denote the count of its possible values. Denote M max; Mx as the maximum count across all attributes.
AFCP for multi-class classification outlined in Algorithm 2 has the following computational cost. Analysis for a single test point
The cost of constructing prediction sets and computing miscoverage indicators within the leave-one-out procedure is O n n)).
Then, selecting the sensitive attributes requires O( 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 ((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 + KM) + MKMM
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 E DU ((xxtx y)} Vy E [L]. and VI E [m]] as follows:
1
Σ
1($ S $)))
1
(Znt()nnt)
1
(S)) among { HED + 1($ S 5Y))
1+n
For each placeholder label E [L], computing the nonconformity scores for all samples in
DU DU{(Xn y) costs (( m)) evaluating the ranks takes O(n log n)) and comparing Šy Sh+ with Sy costs ((n-m))))))))))))))))))())) -m). This process needs to be conducted for each y E [T.). therefore the total cost of this step is O(L - (n + m - n log n + num)) = O(L n- (log n + m)).
Selecting the sensitive attribute costs O(n M KLL- +--mmn+ M K). Breaking in steps, for each test sample (X u), E [4], the worst miscoverage rate for attribute k as defined in (5), can be rewritten as follows:
EIEDU(() Egs,e 16,(X,, (k}) = m)
8y, == max
mE(dde)
EIEDU(( 16,(X, (k}) = m}
EieD Eygis (8(x, (k)) = m] + Ey.e. [6 (k)) = m)
max mm(MMa)
EiED 1(0(X, (k}) = =m] + 1( (k}) = m]
EiED(km) Ey.t Ey,t, 1{x(X,, (k+ m]
mE(M,]
[D(k, - (x,;, (1+} = m
where (kk, m) represents subset of the calibration data indexed : (k))= m). The trick we use is that the identification of subset D(: m) does not depend on the test sample and the placcholder label y, therefore can be reused to calculate the miscoverage
E (Z.
26

---

rate for every test sample (xx=+,)))7 In specific, identifying (ik, m). Ak E [K] m
[M takes On M K). For each ((k, m.) computing it) p Vt E mm. Vy
L takes O (D(k, m]] m). and computing Ey,t, ( Zi {k] = m] takes (L m).
Therefore, repeating this process for all (Kk, m), [K] m [M,] and for all [L]
in total takes O n m). Lastly, finding the maximum miscoverage across all attributes takes OLL M K).
Hence, the total cost of running Algorithm 2 for m test samples is L (n+ Lm)).
A7
Additional Results from Numerical Experiments
A7.1
AFCP for Multiclass Classification
A7.111
Synthetic Data
Recall from Section 3.2 that Color is denoted Xo and the first one of the non-sensitive features as X1. The distribution of Y conditional on X modeled by a simple decision tree, where Xo and X1 the only useful predictors for Y. formulated as the following:
3:31 0,0,0)
if X-=Blue and X1 0.5,
0,,,0,333::3
Xo=Blue and .X 2 0.5,
(1,0,0,0,0,0,
Xo=Grey and ,0 X1 < 00 if Xr=rrey and
P X] =
(0.1,0,0,0.0),
1 S X1 I
(A27)
(0,0,0,0,0,1),
Xo=Grey and 5 X1 < 1.
The detailed numerical experiments results of AFCP with the adaptive equalized coverage (see Equation (3)) are presented and compared with other benchmark methods.
Table Al: Average coverage and average size of prediction for all test samples constructed by different methods as a function of the training and calibration size. All methods obtain coverage beyond 0.9, while our AFCP and AFCPI methods, along with the Marginal method, produce the smallest, thus, the most informative, prediction sets. Red numbers indicate the small size of prediction sets. See corresponding plots in Figure
Marginal
Sample size
Coverage
Size
Coverage
Size
Coverage
Size
Covemiee
Size
Coverage
Size
200
0.917
(0.002)
0.937
3,206
(0:1550
2.86]
0.967
3,624
(0:000))
5.965
(0.007)
(0.001)
0.345
0.945
1.495
(0:001)
(0.009)
(0.009)
(0.001)
(0.002)
(0.09)
2000
(0,001)
0.945
(0.007)
1.548
(0.001)
0.946
(0.007)
1,546
(0.002)
0.501
(0.007)
1.391
(0.001)
0.956
(0,008)
1,618
(0.001)
0.925
(0.008)
1.719
27

---

Coverage
Size
1.0
Method
AFCP
AFCP1
Marginal
0.8
Partial
Exhaustive
0.6
Attribute: Color
Blue
Grey
200 500
1000
2000
200
500 1000 2000
Sample size
Figure A1: Coverage and size of prediction sets constructed with different methods for groups formed by Color. For the Blue group, the Marginal method (dashed orange lines) fails to detect and correct for its undercoverage, and the Exhaustive method produces prediction sets that to be helpful. In contrast, our AFCP and AFCPI methods correct the undercoverage and maintain small prediction sets. See Table A2 for numerical details and standard errors.
conservative
Size
Method
1.00
AFCP
AFCP1
Marginal
Partial
0.95
Eshaustive
Attribute: Age Group
0.90
:65
-- 18-24
25-40
200
1000
2000
2000
41-65
Sample size
Figure A2: Coverage and size of prediction sets constructed with different methods groups formed by Age group. By design, all groups have similar performance, and none of them subject to infaimessumneerooeaage. See Table A3 for numerical details and standard errors.
Coverage
Size
Method
1.00
AFCP
AFCP1
Marginal
Partial
0.95
Attribute: Region
0.90
East
North
South
200
1000
2000
500
2000
West
Sample size
Figure A3: Coverage and size of prediction sets constructed with different methods for groups formed by Region. By design, all groups have similar performance, and none of them are subject to unfaimess/umdeeccveeaagg See Table A4 for numerical details and standard errors.
28

---

Table A2: Coverage and size of prediction sets constructed with different methods for groups formed by Color. Green numbers indicate low coverage and red numbers indicate the small size of prediction sets. See corresponding plots in Figure AI.
APCPI
Marginal
Partial
Exhaustive
Group
Sample sizze
Cowerage
Sine
Coverage
Size
Coverage
Size
Covenge
Size
Covenge
Size
Grey
Grry
200
(0.003)
0.927
(0.051)
2.936
(0,001)
0.935
(0.065)
3.015
(0.003)
0.921
(0.055)
2,862
(8.007)
0.967
(0.062)
3,457
(0.000)
0.999
(0.007)
5.961
Crry
500
(0.002)
0.941
(0.011)
1.682
(0,002)
0
(0.011)
1.682
(0.002)
0.942
(0.011)
1.683
(0.001)
0.989
(0.015)
1,941
(0.002)
0.945
(0.037)
2.917
Grey
1000
(0.001)
0.949
(0.099)
1.494
(0.0011
0.9-9
(0.009)
1.494
(0.0KE)
0.947
(0.009)
1.890
(8.00)
0.961
(0.010)
1.832
(0.002)
0.925
(0.005
1,436
Gray
2000
(0.001)
0.951
(0.007)
1.384
(0.001)
0.951
(0.007)
13844
(0 (0.001)
0.951
(0.007)
1.381
(0,001)
0.982
(0.008)
1,462
(0.002)
0914
(0.005)
1.244
Blue
Blue
200
(0.012)
0,832
(0.111)
3,723
(0.0877)
0,950
(0.108)
4 1.908
(0.012)
0.729
(0.059)
2,847
(80006
0.963
(0.1013)
5.099
(0.000)
1 1000
(0.000)
6,000
Hlue
500
(0.006)
0.916
(0.040)
3,500
(0.006)
0.917
(0.040)
3.504
(0.008)
0.515
(0.014)
1.207
(0.006)
0.917
(0.041)
3,512
(0,000)
1.000
(0.000)
5,000
Blue
1000
(0.005)
0.910
(0.0244)
3.223
(0.0155
0.910
(0.024)
3.228
(0.007)
0.484
(0.D11)
1.542
(1,005)
3,506
(0.824)
3.225
(0,000)
1.000
(0.000)
5,000
Blue
2000
(0.005)
0.906
(0.017)
3.008
0
(0.005)
(0.017)
3.008
(0.008)
0.461
(0.010)
.80
(0.005)
0.905
(0.017)
3,013
(0.001)
0.998
(0.017)
5.87%
Table A3: Coverage and size of prediction sets constructed with different methods for groups formed by Age Group. By design, all groups have similar performance, and none of them are subject to infairness/undeccovraagge See corresponding plots in Figure A2.
APCP
APCPI
Marginal
Purtil
Exthusstive
Group
Sample size
Coverage
Size
Coveruge
Size
Coverage
Size
Coverage
Size
Coverage
Size
<18
<18
200
(0.006)
0.910
(0.075)
3,098
(0.005)
0.931
(0.07%)
3.298
(0.0066
0,891
(0.056)
2,887
(0.0014)
0.961
(0.077)
3.674
(0.001)
0.999
(0.015)
5.967
<18
500
(0.003)
0.933
(0.015)
1,884
(0.003)
0.933
(0.015)
1.885
(0.003)
0.897
(0.013)
1.710
(0.003)
0.961
(0.029)
2.136
(0.004)
0.953
(0.074)
3.285
<18
1000
(0.003)
0.941
(0.010)
1.723
(0.03)
0.944
(0.010)
1.720
(0,003)
0.897
(0.000)
1.535
(0.007)
0.955
(0.014)
1884
(0.004
0.932
(0.017)
1.943
<18
2000
(0.002)
0.946
(0.011)
1,585
(0.002)
0.46
(0.011)
1.536
(0.003)
0.905
(0.009
1.434
(0.002)
0,957
(0.012)
1.653
(0.000
0.925
00.118
L.257
18-24
18-24
200
(0.005)
0.925
(0.063)
3,010
(0044)
0941
(0.053)
3.185
(0.005)
0,911
(0
2,870
(0.033)
0.970
(0.068)
3.613
(0.00)
0.999
(0.016)
5.958
18.24
500
(0.000)
0.931
(0.014)
18899
(0003)
0991
(0.014)
1.899
(0.003)
0.899
(0.012)
1.686
(0,002)
0961
(0.024)
2.091
(0.001)
0.947
(0.08-)
3.147
18:24
1000
(0.005
0.942
(0.011)
1,73
(0005)
0942
(0,011)
1,073
(0,055)
0.899
(0000)
1.504
11811
(0.014)
1815
(0003)
0.99
(0.017)
1.925
18-24
2000
(0.000)
0.445
(0.000)
1,573
(0,00))
0.45
(0.000)
1,73
(0.00%)
0.900
0000
1.401
(0.007)
1957
(0.013)
1.645
(0.001)
0.244
(0.018)
1.754
25-40
25 50
200
(0.005)
0.932
(0.057)
2,995
(0.04)
0.948
(0.059)
3.159
(0.004)
0.922
(00028)
2.868
(0.00E))
0.973
(0.064)
3.577
(0.001
0.999
(0.018)
1.965
25-40
500
(0.003)
0.924
(0.014)
18845
(0003))
0.944
(0.014)
1.845
(0,005)
0.895
(0
1.692
(0.003)
0.964
(0.032)
2.116
(0.004)
0.952
(0.090)
3.336
25-40
1000
(0.00)
0.941
(0.011)
1,646
(0005)
0.91
(1011)
1,666
(0.055)
0.896
(00010)
1.49
(0003))
0.55
(0.018)
1. 77822
(0,00)
0.94
(0.020)
1895
50
2000
(0.002)
0.945
(0.009)
1,530
(0.002)
0.955
(0.009)
1,530
(0.003)
0896
(0.008)
1.372
(0.007)
1550
(0.012)
1600
(0.003)
0.92
(0.016)
1,710
41-65
41-65
200
(0.005)
0.920
(0.057)
2,969
(0005)
0.900
(00000)
3.162
(0.005)
0.904
(0.056)
2,851
(0.001))
0.968
(0.61)
3,580
(0,000)
0.999
(0.01))
5.555
41-65
500
(0.003)
0.952
(0.015)
1.847
(0003)
0.922
(0011))
1847
(0.004)
0.908
(0011)
16688
(0.007)
0,966
(0.026)
2.047
(0.004)
0.949
(0.06))
3.138
41-65
1000
(0.002)
0.949
(0.012)
1,54
(0002)
0.949
(0012)
1,656
(0,03)
0.900
(0.00)
1.499
(0,002)
0
(0.017)
L.772
(0.004)
0.900
(0.023)
L858
41-65
2000
(0.002)
0.948
(0.009)
1,519
(0.022)
0.18
(0.007)
1.119
(0.003)
0.901
(0.008)
1,369
(0/013)
0,956
(0.010)
.500
(0.009)
0.921
(0.115)
1665
>65
265
200
(0.007)
0.900
(0.059)
3,008
(0.006)
0.923
(0.054)
3.228
(0.007)
0.880
(0.05-)
2.826
(0.005)
0.959
(0.072)
3.675
(0.000)
0.999
(0.010)
5.979
>65
500
(0.005)
0.944
(0.014)
18867
(0005))
0.944
(1.014)
1.867
(0,005)
0.904
(0002)
1.689
(0.000)
0.965
(0.020)
2.082
(0.004)
0.952
(0.084)
3.191
365
1000
(0.00))
0.946
(0.011)
1,683
(0.07)
0946
(0011)
1,603
(0.00))
0.901
(0010)
1.479
(0.001)
0,960
(0.014)
L.714
(0.004)
0.300
(0.020)
1,880
>65
2000
(0.008)
0.949
(0.010)
1,520
(0.05)
0.99
(0,010)
(0.003)
0.902
(8,00))
(0,003)
(0.012)
(0.003)
0.921
(0.016)
1,99
29

---

Table A4: Coverage and size of prediction sets constructed with different methods for groups formed by Region. By design, all groups have similar performance, and none of them are subject to unfaimess/undercoveragee See corresponding plots in Figure A3.
AFCP
AFCPI
Marginal
Partial
Exhaustive
Group
Sample
Coverage
Coverag
Cowerage
Coverage
Coverage
West
West
200
(0.005)
0.914
(0.04)
(0.00))
3,218
(0.005)
(0.057)
2,878
(0.001)
0.966
(0.001)
0.998
(0.017)
0.919
1.516
(0005)
(0.035)
(0.011)
(0.005)
(0.004)
00,021)
West
(0.00)
05277
(0.000)
(020))
(0,000
(0.08)
0
(0.09)
1.442
(0.002)
0,950
(0.01))
(0.003)
0.015
1811
East
East
200
(2008)
0.936
3.012
(0,05))
3.194
2,874
0,968
(0.062)
3.586
(0.001)
0.999
East
(0000)
(0,12)
(0.71)
Fast
0.950
(0,002)
1.508
0.929
East
2000
(0.002)
0.952
(0.009)
1,564
(0 002)
0.92
(0.00%)
1.561
(0.002)
0.908
(0.008)
1,406
(0,002)
0,959
(0.00)
1631
(0.003)
0.918
(0.015)
3.204
(0.033)
(8L000)
(00055)
(0,001)
(0,000)
0.960
0.975
(0.00)
(0.013)
(0.001)
North
(0.02)
0.957
00.011)
(0.002)
0957
(0.011)
1,683
(0.002)
0.917
(0.010)
1.489
(0.002)
0.966
(0.012)
(0,000)
0,509
(0.018)
18811
North
(0,002)
0.958
(0.009)
1,523
(0,002)
0.98
(0,009)
1.523
(0.083)
0.914
(0.008)
1333
(0.002)
0.962
(0.010)
1,572
(1,003)
0.929
(0.015)
1666
South
200
3,209
(8008)
(0.012)
(0.102)
(0.090)
South
1000
(0.003)
0.545
(0.010)
(0 003)
(0.010)
(0.083)
0.897
(0.010)
1.408
(0.007)
0.957
(0.015)
(8.001)
(0.016)
South
2000
(0,003)
0.939
(0.005)
1.501
(0.06)
0.939
(0,038)
1.501
(0.083)
0.892
(0.007)
1.345
(0.002)
0.952
(0.011)
584
(0,003)
0.922
(0.015)
1.204
30

---

Next, we provide numerical experimental results comparing AFCP with the label-conditional adaptive equalized coverage (see Equation (A14)) with other benchmark methods.
Coverage for Blue
Average coverage
Average size
1.0
1.000
Method
0.975
AFCP
0.8
AFCP1
Marginal
0.6
0.925
Partill
0.900
Exhaustive
200
500
1000
2000
200
500
1000
2000
200
500
1000
2000
Sample
Figure A4: Performance on prediction sets constructed by different methods on synthetic medical diagnosis data a function of the total number of training and calibration points. Our method (AFCP) leads to more informative sets with lower average width and higher conditional coverage on the Blue group. The error bars indicate 2 standard errors.
Table A5: Average coverage and average size of prediction sets for all test samples constructed by different methods as a function of the training and calibration size. All methods obtain coverage beyond 0.9, while AFCP and AFCP1 methods, along with the Marginal method, produce the smallest, thus, the most informative, prediction sets. Red numbers indicate the small size of prediction sets. See corresponding plots in Figure A4.
Marginal
Pantal
Eshsusiive
Sample siz0
Coverage
Size
Coverage
Size
Covergg
Size
Covenge
Size
Coverage
Size
0.925
3.552
0.922
1.846
0.996
1.000
(0.002)
(0.051)
(0.016)
(0.000)
(0.000)
(0.000)
1000
(0.002)
0.345
(0.012)
(0,001)
0.915
(0.012)
(0.002)
0.077
(0.010)
1.557
(0.001)
0.985
(0.017)
(0.000)
1-000
(0.002)
2000
(0.001)
0.947
(0.008)
578
(0.001)
0.949
(0.008)
1,585
(0.002)
0.903
(0,008)
1.415
(0.001)
0.973
(0.011)
1,000
(0.001)
0.985
(0.011)
5.104
Coverage
Size
1.0
Method
AFCP
AFCP1
Marginal
0.8
4-
Partial
Exhaustive
0.6
Attribute: Color
Blue
Gray
200
500
1000
2000
200
500
1000 2000
Sample
Figure A5; Coverage and size of prediction sets constructed with different methods for groups formed by Color. For the Blue group, the Marginal method (dashed orange lines) fails to detect and correct for its undercoverage, and the Exhaustive method produces prediction sets that too conservative to be helpful. In contrast, our AFCP and AFCP methods correct the undercoverage and maintain small prediction sets. See Table A6 for numerical details and standard errors.
31

---

Coverage
Size
Method
AFCP
AFCP1
Marginal
Partial
Exhaustive
0.950
Attribute: Age Group
0.925
<18
... >65
0.900
18-24
25-10
200
1000
2000
200
500
1000
2000
41-65
Sample size
Figure A6: Coverage and size of prediction sets constructed with different methods for groups formed by Age group. By design, all groups have similar performance, and none of them are subject to infaiines//udeeccoerrggg See Table A7 for numerical details and standard errors.
Coverage
Method
1.000
AFCP
AFCP1
0.975
Marginal
Partial
0.950
Exhaustive
0.925
A Attribute: Region
East
North
South
0.875
200
500
1000
2000
200
500
1000
2000
Sample size
Figure A7: Coverage and size of prediction sets constructed with different methods for groups formed by Region. By design, all groups have similar performance, and none of them are subject to unfainess/undercoveragee See Table A8 for numerical details and standard errors.
Table A6: Coverage and size of prediction sets constructed with different methods for groups formed by Color. Green numbers indicate low coverage and red numbers indicate the small size prediction sets. See corresponding plots in Figure A5.
AFCP
AFCP1
Marginal
Partial
Eshausivve
Group
Sample size
Coverage
Size
Coverage
Size
Coverage
Size
Coverage
Size
Coverage
Size
Grey
Grey
200
(0.003)
0.948
(0/446)
3.153
(0.000)
0.959
(01008)
5.971
(0.003)
01.446
(0.047)
3.151
(0.000
1.000
(0.000)
6,000
(0.00)
1.000
(0.000)
6,000
Grey
500
(0.002)
0.952
(0.02))
1.806
(0.007)
0.963
(0
1.700
(0.000)
0.952
(0.016)
1.843
(0.00)
0.996
(0.016)
5.252
(0.00)
1.000
(8.000)
5,000
Grey
1000
(0.001)
0.955
(0.011)
1.561
(0.001)
0.956
(0.03)
1.588
(0.000)
0.952
(0.011)
1.551
(0.00)
0.966
(0.019)
2.343
(0.000
0.59
(0.002)
5,900
Gray
(0.001)
(0.008)
(0.001)
(0.07)
(8,001)
(0.008)
(9.001)
0.97%
(0.011)
(0001)
(8.012)
Bloe
Blue
200
(0.009)
0.786
(0.07))
3.149
(0.000)
0.999
(0,005)
5.983
(0.009)
0.783
(0.049)
3.145
(0.00)
1.000
(0.000)
6,000
(0.000)
1.000
(0.000)
6,000
Rlue
500
(0.01))
0.655
(0.083)
2,813
(0.003)
0.979
(0001))
S.969
(0,008)
11533
(0.018)
1.869
(0.001)
0.999
(0.005)
3,989
(00000)
1.000
(0,000)
6,000
Blue
1000
(0.008)
0.872
4.129
(0.034)
0.964
(0058)
3.008
(0.00)
0.506
(0.013)
1.603
(0.00)
0.974
(0.054)
3.117
(0.000)
1000
(8.000)
5,000
Blue
(0.005)
(00023)
3.180
(0.012)
(0.005)
0.920
(0.000)
32

---

Table A7: Coverage and size of prediction sets constructed with different methods for groups formed by Age Group. By design, all groups have similar performance, and none of them are subject to unfairness/undeccovraagg. See corresponding plots in Figure A6.
AFCP
AFCPI
Marginal
Partial
Exhaustive
Group
Sample
Coverage
Size
Covengge
Size
Coverige
Coverage
Coverage
Stze
<18
<18
200
(0.005)
0.918
(0.046)
3.172
(0.000)
(0.008)
5.972
(0.085)
0.917
(0.048)
3.168
(0.000)
1,000
(0.000)
6.000
(0.000)
1,000
(0.000)
6,000
<18
0.346
1.893
1,990
1,64
0.984
1,000
5,981
(0.00)
0.250
1.624
1.488
0.974
1.940
0.983
5,100
(0.002)
(0.012)
(0.002)
(0.012)
(0.003)
(0.009)
(0,002)
(0.01))
(0.003)
0..01)
18:24
18-24
200
(8,00)
0.38
(0000))
(0.00)
5.71
(00044)
(3,050)
3.180
(0,000)
(0,000)
(8.000)
1,000
(0.00)
8919
1.934
1.561
0.065
0.990
5.975
(0.03)
(0.015)
(0.002)
(0.016)
(0.003)
(0.01)
00.0011
(0,000)
(0,006)
18-24
(0.000)
0.944
(0.010)
1,605
(0.002)
0.45
(0.010)
1.611
(0.003)
0.901
(0.099)
1.426
(0.002)
0.973
(0.017)
1,930
(0.001)
0.981
0.003)
5.10c
25-40
25-40
200
0.048
(0,000)
(0,005)
5.071
(0.05
(0,000)
(0,000
6000
(9,000)
1,000
(0.000)
0001
3.554
1.827
0.997
(0.002)
(0.059)
(0.07))
(0.037)
25-40
(0005)
01942
(0.015)
1.814
(0,017)
(0.003)
0.902
(0.01))
00.0011
0.981
(0,000)
1,000
(0,005)
5.985
25-40
(0,000)
0.945
(0.010)
1.556
(0 (02)
9.947
(0,009)
1.566
(0.002)
0.963
(0.000)
1 1.588
(0.000))
0.022
(0017)
1801
(0.001)
0.985
(0.027)
5.099
41-65
3.148
1.000
6000
1,000
(0.000)
(0,077)
(0.003)
(0:0000)
(0000)
(0,0000
(0.000)
0.910
1,969
(0,002)
(0,059)
(0.0001)
(0.000)
41-65
(0.003)
(.949
(0.016)
(0.002)
(0.016)
1.917
(0.003)
0.12
(0.01)
(0.001)
0.98%
(0031)
(0,000)
1,000
(0.005)
5.981
41-65
2000
(8,002)
0.947
(0.009)
1,552
(0.002)
0.949
(0,009)
1.558
(0.003)
0.902
(00009)
1.391
(0.002)
0.973
(0015)
1875
(8,002)
0.983
(0.052)
5.126
>65
0.10
1,000
500
(0008)
0.924
(0.002)
(0.059)
3,500
(0.003)
0.912
(0.017)
1.546
(0.001)
0.997
(0.000)
1,000
(0.000)
265
(0.003
0.948
(0.016)
1.839
(0.002)
0.600
(0.016)
1,930
(0.003)
0.908
(0.01
1.544
(0.001)
0.986
(0022))
26622
(0,000)
1,000
(0.004)
3.988
>65
2000
(0,002)
0.550
(0.011)
1.562
(0.022)
0.951
(0.011)
1.508
(0.003)
0.914
(0.010)
1,400
(0.002)
0.973
(0.06))
1 1668
(1,002)
(1981
(0.032)
5.082
33

---

Table A8: Coverage and size of prediction sets constructed with different methods for groups formed by Region. By design, all groups have similar performance, and none of them are subject to unfaimess/undeeroveragee See corresponding plots in Figure A7.
AFCP
AFCPI
Marginal
Partial
Eshaustive
Group
Sample
Coverage
Covenge
Civerage
Coverage
Coverage
West
West
200
0.927
(0:047)
(0.00)
0.999
(0.084)
(0.08))
3,164
(0.000)
(0.000)
(3.00))
(0.000)
(0005)
(0.003)
(0.024)
2000
(0.002)
0.926
(0.000)
(0.02)
(0.009)
(0.003)
(0.00)
(0.007)
(0.013)
1.978
(0.001)
0.933
0.022)
East
East
200
0.942
3.174
(0.00)
0.999
(0003))
0.940
3.172
1,000
(0.000)
6,000
(8,000)
1,000
(0.003)
(0002)
(0.054)
(0016)
1000
(0.002)
0.953
1,846
0.933
(0.01))
0.985
0.999
East
2000
(0.002)
0.951
(0,010)
L,588
(0.002)
0.952
(0.010)
1.595
(0.007)
0.11
(0.009)
1.400
(0.000)
0.975
(0.015)
909
(0.001)
0.983
(.031)
5.081
North
(0.00))
(1,10)
(0.003)
(01066)
(0,00))
(8,000)
0.917
1,973
5.292
(0.003)
North
1000
(0.002)
0.957
(0.015)
1,844
(0.022)
0.968
(0.015)
1.937
(0.002)
0.920
(0.01)
1.548
00.0013
0.988
(0.025)
2.686
(0,000)
1,000
(0.004)
3,986
North
2000
(0.002)
0.959
(0.010)
1.551
(0.022)
0.91
(0,010)
1.560
(0.005)
0.915
(0,009)
1.397
(0,001)
0.978
(0.014)
1885
(0.001)
0.983
(.1111)
5.107
South
South
(0.002)
(0.003)
(0.018)
(0.024)
(0.000)
South
1000
(0.063)
0.944
(0.014)
(0.002)
(0.016)
1.913
(0.003)
(0.01))
1.533
(0.001)
(0 (22))
(0.000)
1,000
(0.004)
South
2000
(0.003)
0.942
(0,009)
1,537
(0.003)
0.944
(0.009)
1.544
(0.003)
0.894
(0,008)
1.366
(0.0K2)
0.970
(0.015)
1 868
(0.001)
0.984
(0.051)
5.124
34

---

A7.1.2
Nursery Data
Table A9: Average coverage and average size of prediction sets for all test samples constructed by different methods as a function of the training and calibration size. All methods obtain coverage beyond 0.9, while our AFCP and AFCPI methods, along with the Marginal method, produce the smallest, thus, the most informative, prediction sets, Red numbers indicate the small size of prediction sets. See corresponding plots in Figure
AFCP
Marginal
Partal
Sample si20
Coverage
Size
Coverage
Size
Coverage
Size
Coverage
Sizr
Coverage
Size
200
(0.0044)
0.923
(0.0013)
(0.030)
1.918
(0:0227)
1.726
(0.002)
0.927
(8.039)
(0:0011
(0.014)
3,980
(0.014)
0.928
0.928
1.375
0.952
1.000
(0.002)
(0.002))
(0.009)
(0.009)
(0.002)
(0.000)
(00001)
2000
(0.001)
0.928
(0.006)
1.359
(0.001)
0.922
(0,006)
L,359
(0.002)
0,902
(0.005)
1.259
(0.001)
0.945
1,450
(0.000)
0.992
(0.006)
3,738
5000
(0.001)
0,916
(0.005)
1.156
(0.001)
0.916
(0.005)
1.156
(0.002)
0.501
(0.003)
1.085
(0.002)
0.928
(0,005)
1,150
(0.001)
03339
(0.007)
1.342
Coverage
Sbee
Attribute: Parents' Occupation
1.0
Occupation
Occupation
Oscupation
Method
0.6
AFCP1
Marginal
Partal
Exhoustive
200
500
2000
5000
500
1000
5000
Sample size
Figure A8: Coverage and size of prediction sets constructed with different methods for groups formed by Parents' Occupation. 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 numerical details and standard errors.
Coverage
Attibute: Children
1.00
more
Methed
AFC*
Marginal
250
500
1000
2000
5000
200 1000
500
2000
5000
Exhaustive
Sample
Figure A9: Coverage and size of prediction sets constructed with different methods for groups formed by Children. All groups have similar performance, and none of them are subject to unfair- ness/undercovverage See Table All for numerical details and standard errors.
35

---

Attributt: Finance
Conveniett
0.935
Incomenennt
0.90
Method
APCP
0.95
AFCP1
Hargnal
0.000
Exhaustivv
200
1000
2000
5000
200
300
1000
2000
5000
Sample
Figure A10: Coverage and size of prediction sets constructed with different methods for groups formed by Finance. All groups have similar performance, and none of them subject to unfair- ness/undercoverage. See Table A12 for numerical details and standard errors.
Method
1.00
AFCP
AFCP1
Margiral
Pardal
Eahaustive
Norprez
Proclenate
Sightl prob
200
500
1000
2000
5000
200
1000
2000
5000
Sample size
Figure A11: Coverage and size of prediction sets constructed with different methods for groups formed by Social. All groups have similar performance, and none of them are subject to unfair- ness/undercoveragee. See Table A13 for numerical details and standard errors.
Coverage
5be
Attribute: Health
1.00
hot-Recommenced
Recommended
M etthad
0.90
AFCP
AFCP1
Marginal
Partill
Exhaustve
Sample size
Figure A12: Coverage and size of prediction sets constructed with different methods for groups formed by Health. All groups have similar performance, and none them are subject to unfair- ness/undercoverage. See Table A14 for numerical details and standard errors.
36

---

Table A10: Coverage and size of prediction sets constructed with different methods for groups formed by Parents' Occupation. Green numbers indicate low coverage and red numbers indicate the small size of prediction sets, See corresponding plots in Figure A8.
AFCP
AFCPI
Marginal
Partal
Exhausive
Group
Sample
Coverage
Size
Coverage
Size
Coverage
Size
Coverage
Size
Coverage
Size
Occugattio 0
Occupation
200
(0.003)
0,940
(0.028)
1,692
(0.000)
0.545
(0.051)
1,751
(0.04)
0.226
(0.029)
1,685
(0.002)
0.985
(0.044)
2,420
(0.000)
1,001
(0.014)
3580
Occupation
500
(0.002)
0.933
(0.012)
1.435
(0.002)
0,933
(0.012)
1.433
(0.005)
0.911
(0.013)
1,424
(0.02)
0.961
(0.021)
1.700
(0.00)
1,000
(0.000)
4,000
Occoparion D
1000
(0.002)
0.927
(0.009)
1.315
(0.002)
0.927
(0.009)
1.315
(0.00))
0.255
(0.009)
1.314
(0.02))
0951
(0.015)
1.475
(0.000)
1.090
(0.00))
3,9%
Occupation O
2000
(0.002)
0.926
(0.007)
1.9
(0.002)
0.936
(0.07)
1.197
(0.000)
0.976
(0.006)
1.196
(0002))
0944
(0.008)
1,286
(0.001)
0.992
(0.10)
3.720
Occupation D
5000
(0.002)
0.912
(0.004)
1.010
(0.002)
0.912
(0.004)
1.010
(0.002)
0912
(0.003)
1,007
(0.002)
0.25
(0.001)
1,025
(0.002)
0.935
(0.009
1.167
Occupation I
Occupation
200
(0.022)
0.875
(0.082)
3.533
(8.00)
0.984
(0.017)
3.952
(0.013)
04488
(0,051)
1,862
(0.066)
0.988
(0.016)
3,965
(0.005)
0.993
(0.14)
3,00
Occupation
500
(0.009)
0.937
(0.041)
3.699
(0.005)
0,943
(0.0344)
3.727
(0.012)
0,11
(0.024)
1657
(0.00))
0.950
(0.027)
3.742
(0.000)
L.000
(0.000
4.000
Occupation
1000
(0.012)
0.90%
(00042)
3.505
(0.012)
0.906
(0.042)
3.305
(0.010)
0.399
(0/020)
1,561
(0.007)
0.28
(0.022))
(0,000)
1,000
(6.00)
4,000
Oecupation
2000
(0.010)
0.8945
(0.41)
3.356
(0.010)
(0
3.356
(001))
0.499
00020
1,579
(00007
0906
(0
5410
(00000
1,000
(0,000)
4.000
Occupation
5000
(0.010)
11.99
(0,038)
1,663
(0.010)
0
(0.038)
3.263
(0.012)
0,40
(0.021)
2007
(0.066)
0.00
(0.025)
1:44
(0,000)
1000
(0.000)
Occupation 2
Oscupation 2
200
(0.0044)
0.913
(0.03%)
1,810
(0.004)
0.919
(0.035)
L868
(0.004)
0.911
(0.025)
1.772
(0.03))
0.920
(0.041)
2.534
(0.001)
0,999
(0014)
3,980
Occupation 2
500
(0.0003)
0.927
(0.018)
1.577
(0.000)
0.927
(0.018)
1.577
(0.00)
0.926
(0.018)
1,566
(0.002)
0.911
(0.026)
1,906
(0.000)
1,800
(0.00)
4.000
Occupation 2
1000
(0.0077)
0.932
(0.011)
1.428
(0.002)
0.933
(0:011)
1.128
(0.00)
0991
(0.011)
1,415
(0.002)
0.956
(0.016)
1.614
(0,000)
L,000
(0.001)
3.958
Occupaticu
(0.002)
10,933
(0.007)
(0.007)
1,289
(0.007)
(0.022)
0951
(0,009)
(0.001)
(0.010)
3.226
0.923
0.921
Occupation
(0.002)
(0.005)
(0.002)
Table A11: Coverage and size of prediction sets constructed with different methods for groups formed by Children. All groups have similar performance, and none of them are subject to unfair- ness/undercovvrrge. See corresponding plots in Figure A9.
APCP
APCPI
Margical
Partial
Exhaustive
Group
Sample
Coverage
Size
Coverage
Coverage
Coverage
Size
Coverage
Size
0.504
1.966
2,004
0.884
0.968
2.633
3.980
(0.004)
10.004)
(00022)
(0:003)
(0.001)
(0:014)
1.738
1.730
0.880
2.047
(0.004)
(0:019)
(0.004)
(0.019)
(0.005)
(0.005)
(0.026)
(0.000)
1000
(0.003)
0.911
(0.014)
1,581
0.911
003))
(0.014)
1.581
(0.003)
0.884
(0.013)
1.475
(0.003)
0.940
(0.018)
1.784
(0.000)
1,000
(0.001)
3.988
1
2000
(00022)
0.910
(0.009)
1.428
10.002)
0.10
(0,009)
1.428
(0.015)
0.884
(0.09))
1.326
(0.903)
0.935
(0.012)
1.554
(0.001)
0.993
(0.014)
3.758
1
5000
(0.033
0,901
(0.009)
1.198
(0.063)
0.901
(0.009)
1.198
(0.005)
0.884
(0.006)
1.122
(0.005)
0.919
(0.009)
1,238
(0.003)
0.335
(0:016)
L
1.917
0.939
1.981
0,900
0.978
2.629
3
(0.04)
(0.052)
10.003)
(0,033)
(0.004)
(0000))
(0.002)
10.051)
(0.014)
2
(0.003)
0.933
(0:017)
1.879
(0.05))
0.34
(0.07)
1.680
(C.005)
0.905
(001))
1356
(0:302)
0.961
(0.024)
1.957
(0.000)
1,000
(0.0000
4,000
2
1000
(00003)
0,929
(0.012)
1.535
10
0929
(0.02))
1.555
(0.005)
(OOEL)
1.427
(0.302))
0.956
(0.018)
1.725
(0,000)
1,000
(0.002)
3.997
2
2000
(0.003)
0.927
(8.008)
1.387
997
0033
(0.00))
1:877
(0 (0,005)
0.890
(0.07)
1283
(0.000)
0.942
(0.010))
1.475
(0.001)
0.991
(0.015)
3.759
2
5000
(0.003)
0.911
(0.005)
1.175
(0003) (030)
(0.00))
LIRE
(0.004)
0.89
(0005))
11:0
(0.003)
0.935
(0.008)
1198
(0.000)
0.941
(0.012)
1.370
3
200
(0.04)
0.938
(0.05))
1,806
(0085)
0.500
1,883
(0.084)
0.908
(0023)
1,670
(
(0.097))
D. 0.984
(0.051)
2,544
(0,000)
1,000
(0.014)
3 3,900
3
500
(0.002)
0.945
(0:015)
1.579 1
(0002)
(0:005)
E.SK
(0:005)
6916
1
(0.002)
0.970
(0.024)
1,834
(0.000)
1,000
(0.000)
4.0030
3
1000
(00022)
0.941
1
1.451
0.11
1333
(0.0002)
0.961
(00015)
1.592
(0,000)
1,000
(0:001)
3.99%
3
2000
(00022)
0.942
(0:005)
1:324
1982
(0002)
C918
(
12:0
0.956
(0.002)
(0.010)
1.401
(0.001)
0.591
(0:015)
3:715
5000
(0.003)
0.929
(0:000)
1-128
(E000))
(0.000)
(0.005)
0914
(0000)
1056
(0:0072)
(0.008)
1:42
(0.002)
(0:012)
more
more
200
(0.004)
0.922
(0.025)
1.698
(0004)
0.944
(0/029)
1.772
(C.004)
0.894
(0.025)
1.586
(0.002)
0.979
(0.051)
2.392
(0.000)
0.999
(0.014)
3.980
THOTO
500
(00003)
0.932
(0-015)
1.902
(0003)
0033
(0.015)
1.501
(0.005)
0.902
(0.014)
1.306
(0.001))
0.962
(0.028)
1.795
(0.000)
1,000
(0:0100)
4.000
1000
1000
(0.002)
0.931
(0.010)
1.376
(0.002)
0931
(0.010)
1.376
(0.005)
0.897
(0.010)
1:266
(0.007)
0.952
(0.017)
1.319
(0.000)
1,000
(0.002)
3.995
2000
(0.002)
0.911
(0,008)
1-296
10,003)
0.31
(0,008)
1,206
(0.003)
0.907
(0.007)
1.197
(0.002)
(0.009)
1.371
(0.001)
0.901
(0:015)
1739
1.121
1.274
m00e
5000
(0.003)
(0:008)
(0.008)
(0.005)
(0.005)
(0.008)
37

---

Table A12: Coverage and size of prediction sets constructed with different methods for groups formed by Finance. All groups have similar performance, and none of them are subject to unfair- ness/undercoverrage See corresponding plots Figure A10.
AFCP
APCPI
Marginal
Partial
Exhaustive
Group
Sample size
Coverage
Coverage
Coverage
Size
Coverage
Size
Coverage
Convenient
Convenient
0.921
(0.0129)
1,873
(0.005)
0,535
1,946
(0.0014)
0.894
(0.023)
1.755
0.97%
(0.040)
2.596
0.999
(0.014)
3,980
Convenient
500
(0.002)
0.930
(0.015)
1.665
(0.002)
0.930
(0.015)
1,667
(0.005)
0.901
(0.015)
1.347
(0.007)
0.961
(0.022)
1.961
(0.000)
1,000
(0.003)
4,000
Convenient
1000
(0.002)
0.927
(0.010)
1.531
(0.002)
0.927
(0.010)
1.531
(0.002)
0.897
(0.009)
1.414
(0.902)
0.951
(0.015)
1.707
(0.000)
1,000
(0.001)
3,997
Convenient
2000
(0.002)
0.930
(0.008)
1.393
(0.002)
0.930
(0.008
1.393
(0.002)
0.905
(0.007)
1.293
(0.002)
0.947
(0.009)
1.490
(0.001)
0.992
(0.008)
3,759
Convesient
5000
(0.002)
0.917
(0.006)
1,165
(0.002)
0.977
(0.006)
1,165
(0.002)
0.906
(0.004)
1.097
(0.007)
0.932
(0 (0.006)
194
(0.002)
0,93
(0.010)
1.347
Incomvenient
Inconvenient
200
(0.004)
0.921
(0.112))
1.821
(0.005)
0.935
(0A029)
1,89
(0.0044)
0.899
(Q.027)
1,688
(0.5K1)
0,978
(0.040)
2.521
(0.001)
0.999
(0:014)
3,980
Incooveniest
500
(0.002)
0.531
(0.015)
1.582
(0.002)
0.931
(0.015)
1.583
(0.005)
0.901
(0.015)
1.462
(0.002)
0.961
(0.022)
1.857
(0.000)
1,000
(0.000)
4,080
Inconveniem
1000
(0.002)
0.920
(0.010)
1,440
(0.002)
0.929
(0.010)
1,400
(0.005)
0.902
(0.010)
1.376
(0-002)
0.951
(0.015)
601
(0,000)
1,000
(0-001)
3.997
Inconvenieus
2000
(0.002)
0.925
(0.006)
1,325
(0.002)
0,925
(0.006)
1,305
(0.002)
0.899
(0.000)
1:221
(0.002)
0.943
(0 (0.00))
L.110
(0.001)
0.991
(0.010)
3.738
Inconvenient
5000
(00002)
(0.006)
1.146
(0.002)
0.915
(9,000)
1.146
(0:002)
0.897
(0004)
1.072
(0.002)
(0.006)
1.166
(0.002)
(0.010)
1.337
Table A13: Coverage and size of prediction sets constructed with different methods for groups formed by Social. All groups have similar performance, and none of them are subject to unfair- ness/undercovvragge See corresponding plots in Figure A11.
AFCP
AFCPI
Marginal
Panial
Exhaucivv
Group
Sumple
Coverage
Coverage
Size
Coverage
Size
Coverage
Coverage
Size
Nomprob
Nomprob
200
(0.004)
8.922
(0.004)
0:933
1.964
1.775
0.976
(0.001)
0.999
(0.014)
3,980
Nonprob
500
(0:003)
0.926
(0.018)
1.655
(0.005)
0.926
(0.017)
1.657
(0.004)
0.597
(0.018)
1.538
(0.002)
0.959
(0.023)
19413
(0.000)
1.000
(0.000)
4,000
Nonprob
1000
(0.003)
6.924
(0.012)
1.509
(0.003)
0.924
(0.012)
1.509
(0.000)
0.809
(0.012)
1.406
(0.022)
0.951
(0.017)
1.604
(0000)
1,000
(0.001)
3,998
Nonprob
2000
(0.002)
0.922
(0.000)
1.360
(0.002)
0.922
(0.008)
1.360
(0.005)
0.896
(0.00K)
1.258
(0002)
0.42
(0:011)
1.456
(0.00)
0.991
(0.012)
3.740
Nouprob
5000
(0.005)
0.917
(0007)
1.164
(0.005)
0:917
(0.077)
1.164
(0.005)
05001
(0.005)
1,092
(0002)
0.977
(0:007)
1.186
(0.00)
0.38
(0.013)
1,300
Problematic
Problemane
200
(0.054)
0.937
(0.000)
1,346
(0.004)
0.949
(0.050)
1.916
(0.00))
0.913
(0.028)
1.726
(0.02)
0.981
(0.441)
2.546
(0L0B))
1.000
(0.014)
3,980
Problemaric
580
(0.092)
0.945
(0.014)
1,626
(0.002)
11:455
(0.014)
1.628
(0.00))
0.13
(0.015)
1.500
(0002)
0.67
(D/223)
18892
(0000)
1000
(0.000
4.000
Problematic
1000
(0.0033
0.941
(0.010)
1.486
(0.002)
0.941
(0.010)
1.486
(0.00))
0309
(0.009)
1,360
(0,02)
0.988
(0:014
1,630
(0000))
1.000
(0,000)
3,996
Problematic
2000
(0.002)
0.936
(0.008)
1.377
(0.002)
0.936
(0.00R)
1.337
(0.000)
0,009
(0.007)
1.238
(0.02)
0.500
(0.009)
L417
(0001)
0.93
(0.02))
3.726
Problematic
5000
(0:005)
0.916
(00006)
1:135
(0:003)
0.916
(0.066)
1.135
(0.000)
0.00
(0.004)
J,066
(0002)
0.91
(0:000)
1,060
(00022)
0.399
(0.010)
1312
Slightly proh
STightly prob
200
(0.004)
0.909
(0.027)
1,800
(0.004)
0.921
(0.029)
1.871
(0.001)
0.881
(0.026)
L.677
(0.003)
0.971
(0.064)
2,536
(0.001)
0.999
(0.014)
3,980
Slightly_pno prob
500
(0.0015)
0.920
(0.016)
1.500
(0.0005
0.920
(0.016)
1,590
(0.003)
0.891
(0.016)
1,476
(0002)
0.956
(0:026)
18893
(0000))
1.000
(0,000
4,000
Slightl_preb
1000
(0:005)
0.919
(0.01T)
1.462
(0:005)
0.919
(0.011)
1.462
(0.011)
0.891
(6:011)
L,35]
(0.02))
0.47
(8.018)
1,629
(0000)
1.000
(1001)
3.997
Slightly prob
2000
(0:012)
0.925
(8:002)
0:925
(0.008)
1.378
(8.003)
(0:086)
1,283
(0.022)
(0:0077)
(0.001)
0.93
(8011)
Slightly_prob
(0.002)
(0.002)
(0.006)
(0.005)
(0.002)
(0.007)
(0.002)
38

---

Table A14: Coverage and size of prediction sets constructed with different methods for groups formed by Health. All groups have similar performance, and none them are subject to unfair- ness/underroverage. See corresponding plots in Figure A12.
AFCP
AFCPI
Marginal
Partal
Exhaustive
Group
Sample siz0
Coverage
Size
Coverage
Size
Coverage
Size
Covenge
Size
Cowerage
Size
Rod-Recummended
Not Recommended
200
(0.003)
0.961
(0.031)
1.357
(0.003)
0.967
(0.031)
1.419
(0.003)
0.942
(0.029)
1,223
(0.01))
0.900
(0.052)
1.951
(0,000)
1.000
(0.014)
3,960
Not-Ra Rodomecommedd
300
(0.0122)
0.950
1.136
0,950
(0.008)
1.139
(8.003)
0.911
(0.817)
1,905
0971
(0.013)
1.225
1,000
4,000
Not-Rasommended
2000
(0.005)
0.935
0.922
Not- Not-Recommemddl
5000
(0.002)
(0.055)
1.033
(0.002)
(0.005)
(0.002)
0.915
00.0033
0 969
(0.02))
(0.005)
1,045
0.540
(0.099)
1.164
Priority
Priority
(0.034)
(0.013)
(0.039)
2.326
(8.004
0.909
(0.038)
0.979
(0.044)
2,087
(0000)
1000
(0.04)
Prisnity
Priocity
(0.002)
(0.15))
(0.015)
(0.022)
(0,011)
Prixiit
2000
(0.007)
(0.10)
1.384
(0.000)
(0.000)
1.384
(0,000)
(0.000)
(0.00))
0190
(0.015)
1.476
(0001)
0891
(0.11)
Prisnity
5000
(0.0013)
0.908
(0,008)
141
(0.0K))
1..00
(0.008)
1.140
(0,008)
0.806
(0.0055)
1.075
(0.03))
0934
(0,007)
1.167
(0063)
0031
(0.000)
1.330
Racammended
(0/01))
2.736
3.90
Recommended
(0.020)
2.273
1000
4.00
Recommended
1000
(0,003)
0.895
(0.014)
1.775
(0.003)
0.896
(0.014)
1.775
(0.003)
0.867
(0.014)
18622
(0,002)
0.938
(0.023)
2,053
(0.000)
1.000
(0,01)
3,998
Revommended
2000
(0.003)
0.914
(0.011)
1.646
(0,003)
1.914
(0.011)
1.646
(0.000)
0.883
(0.010)
1,339
(0.02)
0.940
(0.013)
1,800
(0.001)
0.991
(0.010)
5.700
Recommended
5000
(0.005)
0.912
(0.10)
1.293
(0.003)
0.912
(0.010)
1.293
(0,000)
0.894
(0.007)
1.213
(0,022)
0.924
(0,010)
1.324
(0.002)
0.939
(0.014)
1,532
39

---

Next, we provide numerical experimental results comparing AFCP with the label-conditional adaptive equalized coverage (see Equation (A14)) with other benchmark methods.
Coverage for Occupation
Average coverage
Average size
1.0
1.000
Method
0.9
0.975
AFCP
AFCP1
Marginal
0.7
Partil
0.6
0.900
Exhaustive
200
500
1000
2000
5000
200
500
1000
2000
5000
200
500
1000
2000
5000
Sample
Figure A13: Performance on prediction sets constructed by different methods on the nursery data as function of the total number of training and calibration points. Our method (AFCP) leads more informative sets with lower average width and higher conditional coverage on the Pretentious group. The error bars indicate 2 standard errors.
Table 15: Average coverage and average size of prediction sets for test samples constructed by different methods as function of the training and calibration size. All methods obtain coverage beyond 0.9, while our AFCP and AFCPI methods, along with the Marginal method, produce the smallest, thus, the most informative, prediction sets. Red numbers indicate the small size of prediction sets. See corresponding plots in Figure A13.
AFCP
AFCPI
Marginal
Partil
Exhausiive
Sumple
Coverage
Coverage
Size
Coverge
Covenge
Coverage
200
(0.005)
0.925
(0.029)
2.745
(0.002)
0.962
(0.017)
3.841
(0003)
0.19
(0.325)
2,575
(0.001)
0.996
(0.014)
3,970
(0.001)
0.999
(0.014)
3,980
500
(0.007)
0.924
2.934
(0.007)
0.944
(0.00K)
3.670
0.10
(0:019)
2.214
(0.001)
0.978
3.811
(0.000)
1.000
4.000
0.923
5000
(0.001)
0.915
(0.001)
0.915
(0.022)
(0.005)
1.127
(0.001)
0.935
2,553
(0.001)
0.956
Coverage
Size
Attribute: Parents' Occupation
Occupation
Occupation
0.9
Occupation
Method
AFCP
0.7
AFCP1
Partal
Exhaustive
200
500
2000
5000
500 1000
2000
5000
Sample size
Figure A14: Coverage and size of prediction sets constructed with different methods for groups formed by Parents' Occupation. For the Occupation group. the Marginal method (dashed orange lines) fails to detect and correct for its undercoverage. and the Exhaustive method produces prediction sets that too conservative to be helpful. In contrast, AFCP and AFCP1 methods correct the undercoverage and maintain small prediction sets. See Table A16 for details and standard errors.
40

---

Coverage
Size
Attrbutt: Children
1000
more
0.20
Method
AFC?
AFCF1
0900
Marginal
Partal
200
500
1000
2000
5000
202
500
1000
2000
5000
Fahoustive
Sample size
Figure A15: Coverage and size of prediction sets constructed with different methods for groups formed by Children. All groups have similar performance, and none of them are subject to unfair- ness/undercovverage See Table A17 for numerical details and standard errors.
Covrrage
Size
1.00
Attribute: Finance
Incommenient
0.9
Method
AFCP
AFCP1
Marginal
Partal
Exhoustive
200
500
1200
2000
5000
20c
500
1000
2000
5000
Sample size
Figure A16: Coverage and size of prediction sets constructed with different methods for groups formed by Finance. All groups have similar performance, and none of them are subject to unfair- ness/undercoverage. See Table A18 for numerical details and standard errors.
Coverage
Size
Method
1.00
AP
AFCP1
0.75
Marginal
Partal
Exhaustive
0.23
Attribute: Social
Norprož
0.900
Prociemate
lighty,
200
500
1000
2000
5000
200
300
10000
3000
Sample size
Figure A17: Coverage and size of prediction sets constructed with different methods for groups formed by Social. All groups have similar performance, and none of them are subject to unfair- ness/undercooverage See Table A19 for numerical details and standard errors.
Coverage
Size
Attribute: Health
1.000
Not Recommenced
Prierty
Recommended
090
M Method
0.95
AFCP1
0.000
Marginal
Partal
Sample size
Figure A18: Coverage and size of prediction sets constructed with different methods for groups formed by Health. All groups have similar performances, and none of them are subject to unfair- ness/undercovverage See Table A20 for numerical details and standard errors.
41

---

Table A16: Coverage and size of prediction sets constructed with different methods for groups formed by Parents' Occupation. Green numbers indicate low coverage and red numbers indicate the small size of prediction sets. See corresponding plots in Figure A14.
AFCP
AFCPI
Marginal
Partal
Exhausivv
Group
Sample
Coverage
Size
Coverage
Size
Coverage
Covenge
Size
Clwerage
Size
Occupatton D
Occupation
(0.004)
0.934
2.740
0.960
(0.018)
3.831
0.910
(0.001)
0.906
3,967
1,000
(0.014)
3,980
Occupation
500
(0.003)
0.921
(0.036)
2911
(0.002)
0,936
(0.011)
3.662
(0.000)
0.133
(0.022)
2.177
(0.002)
0.975
(0.008)
3,800
(0,003)
1,000
(0.000
4,000
Occupation
1000
(0.022)
0.914
(0.030)
2.937
(0.002)
0.921
(0.009)
3.502
(0003)
0.988
(0.017)
1,888
(0.022)
0.958
(0.007)
3,677
(0.083
1,000
(0,000
4,000
Oscuparion D
2000
(0.007)
0.916
(0.028)
28455
(0.002)
0.188
(0.12))
3.356
(0.000)
0910
(0.022)
1.624
(0.002)
0.455
(0.008)
3.518
(0.000)
0.995
(0000)
3.99
Oxcupation O
5000
(0.007)
0.910
(0.021)
1.679
(0.002)
0.91
(0.019)
2.681
(0,002)
0.007
(0.004)
1,000
(0.002)
0.927
(0.016)
2.768
(0.002)
0.948
(0.03)
1.877
Occupation
Occuparion
2001
(0.012)
0.739
(0.034)
2,850
(0.005)
(0.016)
3.907
(0.000)
0.692
(0.026)
2,689
(0.005)
0.995
(0.014)
3,500
(0.005)
0.995
(0.044)
3,80
Occupation
500
(0.0111
0.819
(0.086)
3,091
(0,00E)
0.971
(0,011)
3,848
(0.11)
0.630
(0.022)
2.334
(0.200)
1.000
(0.000)
4,000
(0.003)
1.000
(0.000)
0,000
Occupation
1000
(0.010)
0.844
(0.032)
3,559
(0.005)
0.947
000155
3,699
(0.00))
0.583
(0.019)
2.130
(0,000)
1.000
(0.001)
3,999
(0.0000
1,000
(0.000)
4.000
Oecupation
2000
(0.008)
0.868
(0.019)
3:257
(0.009)
0.917
(0.015)
3,166
(0.010)
0.735
(0.019)
2,054
(0.002)
0.994
(0.00))
3.952
(0,000)
1,000
(0000)
4.000
decupation I
5000
(0.0015)
0.835
(0.027)
1114
(0.007)
0.839
(0.025)
3.185
(0.009)
0.679
(0.019)
2,213
(0.004)
0.966
(0.010)
3,885
(0.0K0)
1,000
(0.000)
4.000
Occupation 2
Oscupation 2
200
(0.034)
0.933
(0.091)
2.739
(0.000)
0.962
(0.018)
3
(0.003)
0.934
(0.024)
2.569
(0.001)
0.996
(0.014)
3,973
(0.001)
0.999
(Q.01.)
3,980
Occupation 2
500
(0.0012)
0.938
(0.033)
2.547
(0.002)
0,919
(0.1122)
3.658
(0.00))
0.999
(0.017)
2.257
(0.001)
0.981
(0.011)
3.797
(0.000)
L,000
(0.000)
4.000
Cecupation 2
1000
(0.0077
0.9339
(0.028)
3.090)
(0.002)
0.944
(0.007)
3,486
(0.002)
0.228
(0.015)
2,000
(0.007)
0.70
(0.007)
5-581
(0,000)
L,800
(0.000)
4.000
Occupation 2
2000
(0.0077)
0.936
(0.026)
2.990
(0.002)
0.938
(0.010)
3.379
(0.00))
0.976
(0.019)
1,763
(0.007)
0.958
(0,008)
3.117
(0.00T)
0.997
(0,00)
3.996
Occupation
(0.002)
(0.029)
1.971
(0.002)
(0.030)
2.083
(0.002)
0.922
(0.007)
(0.002)
0.939
(0.028)
2,289
(0.002)
(0.003
3.852
Table A17: Coverage and size of prediction sets constructed with different methods for groups formed by Children. All groups have similar performance, and none of them are subject to unfair- ness/undercovvergee See corresponding plots in Figure A15.
APCP
APCPI
Marginal
Partial
Exhaustive
Group
Sample
Covenge
Size
Coverage
Size
Cawerage
Covorage
Coverage
Size
200
(0.005)
0.919
(0.051)
2.768
(0.003)
(0.017)
3.844
(0.026)
(0:001)
0.996
(0.001)
(0.014)
500
(0.005
0.916
(0,033)
2.975
(0.005)
(0.010)
3,600
(0.004)
0.900
(0.018)
2.271
(0.002)
0.975
(0.010)
(0.000)
1.000
(0.000)
4.000
1000
(0.03)
0.912
(88228
3,066
(0.055)
0.25
(0.008
3.534
(0:015)
0.895
(0.016)
2.038
(0.302)
0.961
10.008)
3.677
(0.000)
1,000
(0.000)
4,000
2000
(0002)
0.11
(0.226)
2.998
10.022)
0916
(0.012)
3,375
(0.003)
03991
(0021))
1.779
(0.000)
0.349
10.009)
3,336
(00000
0.588
(0.001)
3.97
5000
(0.03)
0.901
(0.023)
1.967
(0.003)
0.903
(0.074)
2.498
(0.005)
0.887
(0.007)
1.176
(0.002)
0.928
(0.020)
266
(0.002)
0.954
(0.005)
1,880
200
(0008)
0.933
(0.030)
2,782
(0.00:5
0.977
(0.017)
3351
(0.004)
0.927
(0.024)
2613
(0.001)
0.998
10.014)
3,972
(0.014)
3.980
2
500
(0:03)
0.927
(0.014)
2,966
(0.005)
0.946
(0,010)
3,666
(2.05)
0.915
(0,000)
2:351
(0.000)
0.960
3,824
(0.008)
(0,000)
1.000
(D.0K))
4.000
2
1000
(0.003)
0.923
(0.029)
3,052
(0.002)
0.935
(0.007)
3,536
(0.003)
0,909
(0.014)
2.015
(0.002)
0.969
(0.007)
3.675
(0,000)
1,000
(0.000)
4,000
2
2000
(0003)
0.921
(0.0200)
2.972
0.925
(0.03))
(0.01)
3.364
(0.003)
0.902
(00000)
150
(0/0001
0.949
10.007)
5.50
(0001)
0.997
(0.001)
1.996
5000
(0.05)
0.91
(0.074)
1,895
(0000))
0962
(000)
(0.023)
2:125
(0:005)
0.901
(0
1::30
(0:0002)
0.964
(0.0233
2.589
(0.022)
0.977
(0:0044
3.876
200
(0000)
0.931
(0,030)
2.721
10,033)
0.965
(0.013)
3,837
(0.004)
0.923
(0X024)
2.547
(0.0011
0.997
10.015)
3.971
(0.000)
1,000
(0.014)
3,980
3
500
(0003)
0.920
(0,035)
2.928
(0,065)
0.918
(0.010)
3.661
(0,055)
0,920
2.191
(0.220)
(0.002)
0.981
(0.009)
3,803
(0.000)
1,000
(0:000))
4.000
3
1000
(00002)
0.922
10,0299
2.976
(0,002)
0.944
(0.000)
3.497
(0.005)
0.916
(0.019)
1991
(0,0001
0.970
(0.007)
3,632
(0,000
1,000
(0:0000)
44000
2000
(0.007)
0.913
(0,027)
2.911
(0 007)
0.37
(0.01)
3.347
(0.02)
0.15
(0/2)))
1600
(0000))
0.961
(0.089)
3.477
(0.001)
0.996
(0.001)
1995
5000
(0.022
0.923
(0.024)
(0.002)
(0.022)
2,400
(0:003)
(0.007)
(0.002)
0.909
(0.021)
2,559
(0.002)
0.955
(0:004)
more
TTOT
200
(0.004)
0.916
(0.031)
2,688
(0.003)
0.957
(0.017)
3,830
(0.004)
0.910
(0/03))
2 2.509
(0-001)
0.904
(0.014)
3.967
(0.000)
0.909
(0.014)
3.980
THOT
500
(0.005)
0.902
(0.038)
2,850
(0.005)
0.943
(0.010)
3.629
(0.003)
0.903
(0.024)
2.137
(0.002)
0.978
(0.009)
3.779
(0.000)
1,000
(0:000)
4,000
1000
1000
(00005)
0.919
(0.113)
2,890
(0,085)
0931
(0,00))
3.451
(0:815)
0.898
(0X020)
1833
(0:002)
0,963
(0,008)
3.611
(0.000)
1,000
(b:000)
4,000
0.926
2,855
5:324
0.957
0.597
D000
(0.005)
(0.010)
(0.001)
0.917
1,846
2,383
D 9.907
1.003
0.938
2.550
0.956
(0.003)
(0.024)
(0.005)
(0.023)
(0.006)
(0.000)
(0.002)
(0:005)
42

---

Table A18: Coverage and size of prediction sets constructed with different methods for groups formed by Finance. All groups have similar performance, and none of them are subject to unfair- ness/undercoverrag. See corresponding plots Figure A16.
AFCP
APCPI
Marginal
Partial
Exhaustive
Group
Sample size
Coverage
Coverage
Coverage
Size
Coverage
Size
Coverage
Convenient
Convenient
0.925
(0,1500
2.753
(0.002))
0.965
(0.0014)
0.920
(0.0244)
2,587
10.014)
3.972
0.999
(0.014)
3,980
Convenient
500
(0.002)
0.927
(0.033)
2.957
(0.002)
0.948
(0.009)
3.684
(0.007)
0.913
(0.018)
2.240
(0.001)
0,980
(0.008)
3.822
(0.000)
1,000
(0.000)
4,000
Convenient
1000
(0.002)
0.923
(0.027)
3.029
(0.002)
0.934
(0.00))
3,517
(0.002)
0.905
(0.015)
1.993
(0.931)
0.965
(0.006)
3.653
(0.000)
1,000
(0.000)
4,000
Convenient
2000
(0.002)
0.927
(0.026)
2,900
(0.002)
0.931
(0.010)
3.369
(0.002)
0.909
(0.020)
1.257
(0.002)
0.958
(0.001))
3,508
(0.000)
0.997
(0,000)
3 1.995
Convesient
5000
(0.002)
0.15
(0.022)
1.90
(0.002)
0.977
(0.023)
2445
(0.007)
0.90%
(0.006)
1.143
(0.002)
0.939
(0.019)
2.614
(0.002)
0.566
(0.003)
3 8866
Incomvenient
Inconvenient
200
(0.008)
0.924
(0.1199)
2.757
(0.005)
0,961
(0.017)
3,839
(0:0055)
0.919
(Q.023)
2,564
(0.3311
0,996
(0.014)
3,969
(0.001)
0.999
(0:014)
3,980
Incooveniest
500
(0.002)
0.521
(0.055)
2.911
(0.002)
0.940
(0.009)
3,606
(0.003)
0:907
(0.021)
2.188
(0.001)
0,3776
(0 (0.008)
3,800
(0.000)
1,000
(0.090)
4,000
Inconveniem
1000
(0.002)
0.921
(0,050)
2.957
(0.002)
0.932
(0.007)
3,492
(0.005)
0.904
(0.016)
19915
(0-001)
0.966
(0.007)
1.44
(0,000)
1,000
(0-800)
4.890
Inconvenieus
2000
(0.002)
0.919
(0,026)
2,892
(0.002)
0,925
(0.011)
3.335
(0.002)
0.899
(0.020)
1.000
(0.001)
0,950
(0: (0.00)
3,483
(0.000)
0.997
(0.000)
3.995
Inconvenient
5000
(00002)
00,023)
1,879
(0.002)
0.913
(0,022)
2,409
(0:002)
0.89
(0005)
(0.002)
(0.020)
2.575
(0.001)
(0.002)
Table A19: Coverage and size of prediction sets constructed with different methods for groups formed by Social. All groups have similar performance, and none of them are subject to unfair- ness/undercovvragee See corresponding plots in Figure A17.
AFCP
AFCPI
Marginal
Panial
Exhaucivv
Group
Sumple
Coverage
Coverage
Size
Coverage
Size
Coverage
Coverage
Size
Nomprob
Nomprob
200
(0.014)
0.931
2.768
(0:003)
D:964
(0.017)
3,846
(0:025)
2.601
(0.00))
0.996
(0.001)
(0.014)
3,980
Nonprob
500
(0:003)
0.926
(0.035)
2.939
(0.003)
0.945
(0.009)
3,676
(0.003)
0.912
(0.020)
2.228
(0.001)
0.978
(0.005)
3,815
(0.000)
1.000
(0.000)
4,000
Nonprob
1000
(0.003)
6.924
(0.29))
3,016
(0.902)
0.935
(0.088)
3,515
(0.008)
0.509
(0.016)
1.980
(0.02)
0.968
(0.077)
3,558
(0000)
1,000
(0.000)
4.000
Nonprob
2000
(0.002)
0.921
(0006)
2.944
(0.002)
0.926
(0.011)
3.355
(0.002)
0.00
(0/021)
L.711
(0002)
0.51
(0.005)
3 3.50)
(0.00)
0.986
(0.00)
3.996
Nouprob
5000
(0.002)
0.915
(00044)
1904
(0.002)
0:916
(0.025)
2.437
(0.002)
0.500
(0.007)
1.157
(0002)
0.944
(0:021)
2.585
(0.022)
0957
(0.005)
3,575
Problematic
Problemane
200
(0.034)
0.924
(0,00)
2.742
(8.005)
0.963
(0.017)
3,843
(0.004)
0.922
(0/025)
2.573
(0.01)
0.997
(0.014)
3,972
(010B))
1.000
(0.014)
3,980
Problemaric
580
(0.005)
0.925
(0X034)
2.411
(0.302)
11.44
(0.099)
3.674
(0.00))
0911
(0.019)
2.213
(0002)
0.78
(0:K7T)
38800
(0000)
10000
(0,000)
4.000
Problematic
1000
(0.007)
0.923
(0.000
2.999
(0.002)
0.935
(0.007)
3.508
(0.00)
0504
(0.016)
1.954
(0,02)
0.63
(0.00)
3,644
(0000))
1.000
(0,00)
4.000
Problematic
2000
(0.002)
0.924
(0.026)
2.914
(0.002)
0.929
(0.01))
3,355
(0.000)
0.501
(0.02))
16883
(0.02)
0.53
(0.008)
3.485
(0001)
0.977
(0001)
3,996
Problematic
5000
(0:002)
0.912
(00022)
1863
(0:002)
0.914
(0.022)
2.394
(0.002)
8900
(0:005)
1,106
(0002)
0.955
(0:0100)
2.583
(00002)
0.92
(0.005)
3.871
Slightly proh
STightly prob
200
(0.004)
0.918
(0.029)
2.722
(0.003)
0.958
(0.017)
3.831
(0.000)
0.913
(0.022)
2,550
(0.001)
0.996
(0.014)
3.968
(0.001)
0.999
(0.014)
3,980
Slightly_pni prob
500
(0.0015)
0.921
(0.054)
2.921
(0.002)
0.943
(0.009)
3,662
(0.005)
0,006
(0.020)
2.201
(0002)
0.978
(0:00)
3,809
(0000))
1.000
(0,000
4,000
Slightl_preb
1000
(0:007)
0.919
(0.030)
2.566
(0:007)
0.931
(0.007)
3.492
(8.00)
0.500
(6:017)
1,929
(0001)
0.666
(0-077)
3.640
(0.00)
1.000
(0,000)
4,000
Slightly prob
2000
(8:002)
0.923
(8:002)
0:927
(0.012)
3.347
(8.000)
(0.019)
1.745
(0.02)
(0:005)
3.495
(00000)
0.99
3.997
Slightly_prob
(0.002)
1912
(0.002)
(0.023)
2.448
(0.002)
(0.006)
(0.002)
(0.019)
(0.002)
43

---

Table A20: Coverage and size of prediction sets constructed with different methods for groups formed by Health. All groups have similar performance, and none them are subject to unfair- ness/underroverage. See corresponding plots in Figure A18.
AFCP
AFCPI
Marginal
Partal
Exhaustive
Group
Sample siz0
Coverage
Size
Coverage
Size
Coverage
Size
Covenge
Size
Cowerage
Size
Rod-Recummended
Not Recommended
200
(0.005)
0.937
(0.028)
2.379
(0.025)
0.947
(0.020)
3,868
(0.005)
0.916
(0.028)
2.193
(0.01))
0.905
(0.014)
3,975
(0,000)
1.000
(0.014)
3,980
Not- Rooomecommedd
300
(0.0044
(0.01))
2.576
(0.013)
0.933
(0.005)
3.915
(8.00)
0.924
(0.033)
1.771
(0.01)
3.961
1,000
4,000
Not-Rasommended
(0.010)
2000
(0.04)
3.994
Not- Not-Recommemddl
5000
(0.002)
(0.06)
2.900
(0.002)
0.915
(0.043)
(0.000
(0.005)
0.973
(0.022)
(0.025)
3.737
(0.002)
0.539
(0.002)
33299
Priority
Priority
(0.034)
(0.08)
365
(0,077)
(0.18)
(8.04)
0.935
(0.037)
2.972
(0,00))
0.97
(0,014)
3,966
(0.00)
1000
(0.044)
Prisnity
(0.18)
Priocity
(0.005)
(0.055)
(0.09))
(0.009)
Prixiit
2000
(0.003)
(0.034)
2:709
(0.003)
(0.013)
(0.003)
(0.023)
(0,00))
(0.012)
(0.000
089
(0/00))
3596
Pricnity
5000
(0.002)
0,910
(0.026)
163
(0A0KE)
0.913
(0.027)
1.765
(0,000)
0.898
(0.005))
1OS
(0,022)
0.94
(0,028)
1,879
(0.063)
0960
(0/044)
5,831
Racammended
(0104))
0.897
3580
Recommended
3.234
2.413
3.754
1000
4.00
Recommended
1000
(0,003)
0.911
(0.02.)
3.174
(0.003)
0.925
(0.01)
3.302
(0.003)
0.850
(0.011)
2.224
(0.002)
0.963
(0.010)
3.534
(0.000)
LO000
(0,000)
4,000
Revommended
2000
(0.002)
0.920
(0.200)
2.909
(0.002)
11924
(0.06))
3.106
(0.002)
0.897
(0.015)
2.024
(0002)
0.54
(0.015)
3,316
(0.000)
0,999
(00000
3.99
Recommended
1000
(0.002)
0.916
(0.025)
1.472
(0.00E)
0.916
(00055)
1969
(0,000)
0.900
(0.010)
1.325
(0002)
0.413
(0,025)
2.164
(0.001)
0.968
(0003)
3,845
44

---

A7.1.3
COMPAS data
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 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 levels), age category (3 levels), (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-America, 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 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 the protected attribute Race function of sample size within the same experiment described in Figure A19. This plot demonstrates that both AFCP and AFCP I 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 Atrican-Americn 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 tew-tthann-aaage test accuracy.
Coverage AArricn-American
Average coverage
Average
1.0
0.99
2.8
Method
0.8
0.95
2.0
AFCP1
0.93
Marginal
1.6
Partial
0.6
0.89
1.2
Exhaustive
200
300
500
1000
200
300
500
1000
200
300
500
1000
Sample size
Figure A19: Performance of prediction sets constructed by different methods on the COMPAS data, as a function of the sample size. AFCP leads to more informative predictions with higher coverage conditional on the sensitive attribute, Race (shown for level African-Americat
Coverage for Americn
1.0
Method
0.9
AFCP
0.8
Marginal
0.6
Eshaustive
10
50
Restricted calibration sample size Figure A20: Conditional coverage for the African African-America American group using different methods on the COMPAS data, as function of the sample sizes in the restricted calibration data.
45

---

Selects
1.00
0.75
Method
AFCP
0.25
0.00
200
Sample size
Figure A21: Selection frequency of the relevant attribute Race, using our AFCP method and its variation, AFCPI, in the COMPAS experiments of Figure A19. As the sample size increases, AFCP and AFCP1 become
consistent in selecting the most relevant attribute, Race.
Table A21:
Average prediction accuracy and prediction accuracy for African-American group on the COMPAS data, as a function of the sample size.
Sample Size
Accuracy for Africun-American
Average Accuracy
200
0.355 (0.019)
0.790 (0.003)
300
0.370 (0.009)
0.813 (0.002)
0.976 (0.008)
(0.002)
1000
0.375 (0.009)
0.869 (0.002)
A7.2
AFCP for Outlier Detection
A7.2.1 Setup and Benchmarks
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, MI. 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(amarginal (7 S ax) S by applying Algorithm A2 without protected attributes. The second is the exhaustive equalized benchmark, which evaluates conformal p-values guaranteeing P( (Zn+1)
o( ((Z+1, [K])) < by applying Algorithm A2 with all K sensitive attributes simultaneously protected. The third a partial equalized benchmark that separately applies Algorithm A2 with each possible protected attribute k E [K], and then takes the maximum of all such values. This is an intuitive approach that can be easily verified to provide a coverage guarantee PP (prmiaal (Zn41)))) I a o(Zn+1, {k))) S Vk [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 BCEWithLogitLLos 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 a = 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 higher conditional FPR for groups expe- riencing unfairness, thereby maintaining the average FPR below the target threshold of 0. while simultaneously achieving a higher TPR. The results presented are averaged over 500 independent test points and 30 experiments.
A7.2.2 Synthetic Data
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 this context. The outcome labels Y have two possible values: Y 0 if the unit is properly treated and Y = 1
46

---

otherwise. In our experiment, we treat Y as an outlier and Y 0 as an inlier, with the data generation process described as:
(2: X| = (1.0) or (0, w. equal prob, if Color = Grey.
if Color = Blue,
(A28)
Figure A22 and Table A22 illustrate the performance of conformal p-values generated by various methods synthetic data, showcasing how performance varies with the number of samples in training and calibration datasets. Figures A23-A24 and Tables A23-A25 separately evaluate the False Positive Rate (FPR) and True Positive Rate (TPR) for each protected attribute. Additionally, Figure A26 explores how the severity of bias affecting groups impacts the selection frequency of our method various levels. The severity of bias controlled by the varying percentage of Blue samples, with higher levels indicating less samples and more significant biases in the Blue group.
FPR for Blue
Average FPR
Average TPR
0.12
0.8
M Method
0.3
0.09
0.6
AFCP
AFCP1
0.06
0.4
Marginal
0.1
0.2
Partal
Eshaustive
200
500
1000
2000
200
500
1000
2000
200
500
1000
2000
Sample size
Figure A22: Performance on conformal p-values constructed by different methods the synthetic data as function of the total number of training and calibration points. Our method (AFCP) leads to higher TPR and lower FPR on the Blue group. The error bars indicate 2 standard errors.
Table A22: Average FPR and TPR of conformal p-values for all test samples constructed by different methods as a function of the training and calibration size. All methods control FPR under 0.1, while AFCP and AFCP1 methods, along with the Marginal method, produce the highest TPR. Red numbers indicate high TPR. See corresponding plots in Figure A22.
AFCP
AFCPI
Marginal
Purtial
Exhoustvve
Size
200
(8.007)
0.094
(0.025)
0.642
(0.06))
0.009
(0.03))
0.544
(0/08)
0.102
(0.027)
0.649
(0003)
0.018
(0023)
0.221
(0.00)
0.000
(0,00)
0.000
500
(0.055
8.079
(0.013)
0.706
(0.005)
0.078
(0.01))
0.703
(0005)
0.085
(0.07))
0.896
(0005)
0.037
(0004)
0.519
(0002))
0.100
(0006)
0.066
1000
(0.008)
0.780
(0.005)
(0.008)
0.780
(0.005)
(0.010)
0.770
(0.014
0.664
(0.003)
(0011)
0.531
2000
(0.006)
(0.006)
(0.010
Method
0.4
AFCP1
0.3
Marginal
0.50
Partial
0.2
Exhaustive
0.25
A Attibute: Color
Blue
Gray
200
1000
2000
200
500
1000
2000
Sample size
Figure A23: Performance on conformal p-values constructed by different methods for groups formed
by Color. See Table A23 for numerical details and standard errors.
47

---

Method
0.15
0.8
AFCP
AFCP1
Marginal
0.6
0.10
Partial
Attribute: Region
East
North
0.0
South
200
1000
2000
200
1000
2000
Sample size
Figure A24: Performance on conformal p-values constructed by different methods for groups formed
by Region. See Table A25 for numerical details and standard errors.
FPR
TPR
Method
0.15
AFCP
AFCP1
Marginal
Partial
0.4
Attribute: Age Group
0.05
0.2
<18
... >65
18-24
0.00
0.0
25-40
200
500
1000
2000
200
500
1000
2000
Sample size
Figure A25: Performance on conformal p-values constructed by different methods for groups formed
by Age Group. See Table A24 for numerical details and standard errors.
Table A23: Coverage and size of prediction sets constructed with different methods for groups formed by Color. See corresponding plots Figure A23.
AFCP
APCPI
Marginal
Partial
Exhasstive
Group
Sample Size
FPR
TPR
FPR
TPR
FPR
TPR
FPR
TPR
FPR
TPR
Grey
Gray
200
(0.005)
0.085
(0.027)
0.695
(0.007)
0.073
(0.036)
0.505
(0.007)
0.077
(0,029)
0,680
(0.000)
0.020
(0.006)
0.247
(0.000)
0.000
(0.000
0,000
Grvy
500
(0.005)
0.077
(0.021)
0.767
(0.006)
0.078
(0.021)
0.766
(0.006)
0.062
(0.019)
0.734
(0.003)
0.036
(0,027)
0.567
(0.002)
0.011
(8.07)
0.074
Grey
1000
(0.005)
0.090
(0.008)
0.852
(0.005)
0.090
(0.008)
0.853
(0.004
0.069
(0.011)
0.809
(0.000)
0.045
(0.014)
0.725
(0.001)
0.058
(0.02)
0.599
Gnay
2000
(0.005)
0.887
(0.005)
0.833
(0.005)
0.087
(0.005)
0.883
(0.004)
0.071
(0.000)
0.540
(0.004)
0.022
(0.011)
0.780
(0.004)
0.07%
(0009)
0.812
Blue
Biue
200
(0.036)
0.169
(0.040)
0.190
(0.014)
0,030
(0.016)
0.029
(0003)
0.336
(0,027)
0.378
(0.000)
0.000
(0,000)
0,000
(0.000)
0,000
(0,000
0.000
Blue
500
(0,022)
10.105
(0.025)
1.132
(0,021)
IL085
(0.024)
I.112
(0,023)
0.286
(0,023)
01340
(0.012)
0.822
(0.17))
B1075
(0.000)
0.000
(8,000)
(1000
Blue
1000
(0.021)
0.079
(0.022)
0.122
(0.017)
0.062
(0.019)
0.109
(0.030)
0.336
(0.056)
0.414
(0.017)
0.059
(0.010)
0.109
(0,000)
0.000
(0,000)
0.000
Blue
2000
(0.020)
0.096
(0,020)
0.121
(0.020)
0.096
(0.020)
0.121
(00023
0.575
(0.020)
0.454
(0.017)
0.000
(0.015)
0.115
(0.000)
0.000
(0,000)
0.000
Selects Any Attribute
Selects Age Group
Selects Region
Selects Color
1.00
1.00
1.00
0.75
0.75
0.75
0.75
Method
0.50
0.25
0.25
0.25
0.25
AFCP1
0.00
0.00
0.00
5
2
5
6
S Sensitivity level
Figure A26: Selection frequencies of each protected attribute as a function of severity level of bias.
48

---

Table A24: Coverage and size of prediction sets constructed with different methods for groups formed by Age Group. See corresponding plots in Figure A25,
AFCP
AFCPI
Marginal
Pustial
Exhaustive
Gruup
Sample
TPR
TPR
TPR
TPR
TPR
West
West
(0.012)
(0,032)
0.628
(0.012)
(0.054)
0,538
(0.035)
0,689
(0.006)
(0.056)
0.187
(0.00K)
(0.000)
0,000
West
10.006)
0.086
(0.017)
0,201
(0.007)
0.084
(0.017)
0.705
(0.007)
0.097
(0.015)
0.687
(0.005)
0.043
(0.054)
0.485
(0.004)
0.008
(0.018)
0.055
West
1000
(0.008)
0.111
(0.017)
0.766
(0.008)
0.109
(0.016)
0.765
(0.010)
0.123
(0.016)
0.775
(0.007)
0.063
(0.025)
0.650
(C.007)
0.055
(0.024)
0.536
West
2000
(0.010)
0.117
(0.009)
0.805
(0.010)
0.117
(0.009)
0,805
(0.010)
0.131
(0.009)
0.817
(0.009)
0.070
(0.016)
0.718
(0.008)
0.036
(0.021)
0.698
East
0.100
0.644
0.529
0.642
0.241
0,000
(0.010)
(0,028)
(0.00))
(0.039)
(0.009))
(0.035)
(0.005)
(0.150)
(0.000)
(0.000
0.081
0.711
0.079
0,703
0.063
0.696
0.041
0,535
0.014
0,069
(0.007)
(0,020)
(0.00R)
(0.022)
(0,007)
(0,020)
(0.004)
(0.023)
(0,006)
(0.019)
East
1000
(0,007)
0.067
(0.013)
0,790
(0,08))
0.085
(0.012)
0,789
(0.007)
0.089
(C.015)
0,768
(0.006)
0,043
(0.019)
0.671
(0.006)
0.057
(0.026)
0,549
East
2000
(0.009)
0.096
(0.012)
0,794
(0,009)
0.096
(0.012)
0,796
(00088)
0.085
(0:011)
0:791
(0.007)
0.054
(0.018)
0.715
(0.008)
0,070
(0.016)
0.727
North
North
(0.008)
(0.026)
0,660
(0.00%)
(0.034)
0.582
(0,009)
00.038
(0.003)
(0.051)
0.258
(0.000)
(0,000)
North
(0.007)
0.068
(0.022)
0.717
(0.07)
0.069
(0.022)
0,716
(0.077
0.09
000054
0,031
(0.027)
0.555
(0000)
(.006)
0,074
North
1000
10.009)
0.075
(0.099)
0,789
(0,09)
0.03
(0,009)
0,789
10.085
0.065
63735
10.005)
0.030
(0.015)
DLGTE
(0.07))
(0.08))
0.533
North
2000
(0.008)
0.085
(0.009)
0816
(0.008)
0.85
(0.009)
0.816
(0.008)
0081
(0:010)
0.802
(0.006)
0.066
(0.013)
0.288
(0.006)
0.66
(0.015)
0.743
South
South
(0.010)
0.088
(0.054)
0,630
(0.009)
0.063
(0.021)
0,520
(0.010)
(0.025)
0.658
(0,003))
(0.025)
0.209
(0.010)
(0,000
0,000
South
500
(0.008)
0.081
(0.026)
0.697
(0.008)
0.070
(0.027)
0.691
(0.008)
0.081
(0.022)
0.704
(0.006)
0.033
(0.034)
0,500
(C.007)
0.004
(0.013)
0.043
South
1000
(0.008)
0,085
(0.010)
0.777
(0.00R)
0.083
(0.009)
0.777
(0.007)
0.888
(0.011)
0.768
(0.005)
0.020
(0.014)
0.661
(0.008)
0.046
(0.024)
0.502
South
2000
10.008)
0.093
(0.009)
0,803
(0.008)
0.093
10.0099
0,803
(0.008)
0.101
(0.009)
0.790
(0.007)
0.056
(0.012)
0.718
(0.011)
0.073
(0.014)
0.744
Table A25: Coverage and size of prediction sets constructed with different methods for groups formed by Region. See corresponding plots in Figure A24.
AFCP
AFCPI
Marginal
Purtial
Exhausive
Gruup
Sample Size
TPR
TPR
TPR
TPR
TPR
0.608
0,484
0.613
0.227
0,000
(0.012)
(0.052)
(0.010)
(0.037)
(0.012)
(0.031)
(0.005)
(0.059)
(0.000)
(0.000)
0.107
0,715
0.104
0,710
0,100
0.695
0,029
0.474
0.013
0,065
10.010)
(0.017)
(0.010)
(0.018)
(0.008)
(0.022)
(0.007)
(0.036)
(0.005)
(0.022)
<18
1000
(0.010)
0.181
(0.010)
0,777
(0.010)
0.096
(0.010)
0.774
(0.011)
0.105
(0.013)
0.767
(0.009)
0.051
(0.019)
0.645
(0.00)
0.044
(0.027)
0,499
<18
2000
(0.009)
0.114
(0.014)
0.806
(0.009)
0.114
(0.014)
0,806
(0.010)
0.121
(0:014)
0.806
(0.006)
0.063
(0.024)
0.689
(0.009)
0.072
(0.021)
0.693
18:24
18-24
(0.011)
0,082
(0,027)
06680
(0000)
(0.021)
0,605
(0.011)
(0.035)
0.655
(0.014)
(0.059)
0.272
(0.000)
(0.000)
0,000
18:24
18-24
1000
10.010)
(0.007)
0.099
0.069
(0.021)
(0.012)
0.791
0.750
(000))
0069
0096
(0.018)
(0.012)
0.791
0.736
(0.007)
(0.099)
0.066
0,096
(0:020
6:730
0:708
(0,004)
(0.007))
0,001
0.025
(0.032)
(0.015)
0.898
0,546
(0000)
(0112))
0860
(0.019)
(0.030)
0.541
0.089
18-24
2000
(0.067)
0.084
(1011))
0.80
(0007))
0084
(0.011)
0.00
0.079
0299 2
(00005)
0L096
(0:015)
0:231
(0000))
(0.013)
0.757
25-40
25-40
10.011)
(0.000
0,660
(0000)
(0.051)
0.575
(0.02))
(0:051)
(00655
(00000)
10000
(00000
25-40
10.006)
0.060
(00200
0.741
(0007)
0060
(0.021)
0,745
(0.067))
0,066
(60055)
63952
(0005))
0004
0.581
(
(0005))
(0.016)
0.052
25-40
1000
10,007)
0.882
(0013)
0.784
(0007)
0084
(0.015)
0.784
(0.08))
0.090
(00015)
1000K)
0.0S5
(0.01))
(00030)
0.557
25-40
2000
(0.009)
0.093
(0.01T)
0,04
(0009)
0093
(0.0113
0.04
(0.007)
0.066
0'802 2
(0
0051
0241
(0.012)
(0000)
0060
(0.013)
0.738
41-65
41-65
10,009)
0.084
(J056)
0.653
(0.08)
10,041>
0.607
(0,008)
(
10,044
(0.039)
0.244
(0000) 1
00000
(0,000)
0,000
41-65
500
(0.009)
0.074
(00225)
0,68
(O00))
0.68
(0.025)
0.679
(0,009)
0.083
(00255)
63880 1880
(0.04))
(0.051)
0.498
(0004)
(0.018)
0.074
41-65
1000
(0.00K)
0.073
(0.013)
0,798
(0.07)
0.70
(0.013)
0.798
(0.008)
0.073
(0:016)
0:771
(0,005)
0.034
(0.024)
0.867
(0.07))
GOSS
(0.031>
0.542
41-65
2000
10.008)
0.091
(0.D00)
0,800
(0.008)
0.011
(0,010)
0,810
(0,007)
O. 0.106
(0.015)
0.801
(0,007)
0,55
(0.016)
0.721
(0.008)
0.74
(0.015)
0.745
0.118
0.614
0.086
0.452
0.120
0.633
0.022
0.158
0.000
0,000
(0.015)
(0.039)
(0015))
(0.053)
(0.016)
(0.026)
(0.007)
(0.057)
(0.000)
(0,000)
>65
500
10.010)
0.086
(0.044)
0,657
(0010))
0,88
(0.035)
0.651
(0.010)
0.108
(0.024)
0.675
(0.006)
0,046
0.497
(0.056)
(0.015)
0.006
(0.019)
0.060
>65
1000
(0.0113 13
0.998
(0.015)
0.252
(0011)
0.093
(0.015)
0.754
(0.014)
0.114
(0:016)
0:759
(0.007)
0.052
(00024)
(0.006)
0.054
(0.027)
0.481
>65
2000
(0.089)
0.100
(0.013)
0.797
(0.019)
0.100
(0.013)
0.797
(0.099)
0.100
(0.012)
0.795
(0.006)
0.861
(0.0200)
0:220
(0.007)
0/070
(0.019)
0.713
49

---

A7.2.3 Adult Income Data
We apply our method to the open-domain Adult Income dataset [51], a widely utilized resource in fairness studies. In this dataset, individuals with an income exceeding $50,000 are treated as outliers, while those with income of $50,000 or less are considered inliers. All categorical variables this dataset are treated as sensitive attributes, with levels that have small sample sizes grouped together during the pre-processing stages. After pre-processing. the sensitive attributes and their associated levels are as follows: Native-country (United-States, Others); Education (Bachelors, Some- college, HS- HS-grad, Others); Work Class (Private, Non- Non-private); Marital-status (Divorced, Married-civ- spouse, Never- married, Others); Occupation (Adm-clerical, Craft-repair, Other-service, Sales, Exec- managerial, Prof- trof-specially, Others); Relationship (Own-child, Husband, Not-in-family, Unmarried, Others); Race (White, Others); and Sex (female, male).
This section evaluates and compares the performance of AFCP, AFCPI, and AFCP+, which is the AFCP implementation capable of selecting multiple protected attributes, along with other benchmark methods described in Appendix A7.2.1. All results presented in this section average over 500 test points and 30 independent experiments.
For this dataset, the groups suffering from algorithmic biases are unknown. Figure A27 evaluates the performance different methods on several groups that are observed to exhibit higher FPR using the Marginal method. In all such cases, our AFCP, AFPCI, and AFCP+ methods effectively identify and correct for the protected attributes corresponding at least one group suffering from significantly higher FPR.
Figure A28 and Table A26 present the average FPR and TPR of conformal p-values computed using different methods across all test samples. On average, all methods can control the FPR below the target level of 0.1, while AFCP methods generally achieve higher TPR.
In addition, Figures A29-A36 and Table A27-A34 separately assess the FPR and TPR of conformal p-values for each protected attribute.
Education: Bachelors
Marital Married-cw-spusse
Occupation Exec-managerial
0.20
0.20
0.20
0.15
0.15
0.15
0.35
0.05
Method
0.00
0.00
0.00
AFCP
FPR
200
500
1000
2000
200
500
1000
200
300
1000
2000
AFCP+
Relationship: Husband
Workelass: Not private
Margial
Partal
0.2
0.15
Exhaustive
0.1
0.05
200
500
1000
2000
200
500
1000
2000
Sample size
Figure A27: FPR of conformal p-values constructed with different methods for groups that observed to have significantly higher FPR when using the Marginal method. On average, our methods identify those groups and perform corrections the FPR.
50

---

Method
0.5
AFCP
0.09
0.4
AFCP1
0.3
0.06
AFCP+
0.2
Marginal
0.03
0.1
Partil
0.00
0.0
Exhaustive
200
500
1000
2000
200
500
1000
2000
Sample size
Figure A28: Average FPR and TPR of conformal p-values constructed with different methods on all test samples. All methods control FPR under the target level 0.1. Our AFCP methods can produce generally higher TPR than other methods except the Marginal one. However, as depicted in Figure A27, the Marginal method suffers from unfairness.
Table A26: Average FPR and TPR of conformal p-values constructed with different methods on all test samples. All methods control FPR under the target level 0.1. Red numbers indicate high TPR. See corresponding plots in Figure A28.
AFCP
AFCPI
AFCP+
Marginal
Puntal
Exhaustive
(0.008)
(0.04)
(0.010)
(0.09)
(0021)
(0.07)
(0.018)
(0001)
(0.022)
(0.00)
500
(0.005)
0.001
(0.019)
0.285
(0.06)
0.091
(0.022)
0.356
(0,05)
0.000
(0.024)
0.237
(0.06)
0.099
(0.08)
0.34
(0003)
0.000
(0011)
0.085
(0000)
0.00
(0.00)
0.000
0,093
0.044
(0.01)
2000
(0.004)
0.095
(0.012)
(0.004)
0.097
(0.013)
(0,005)
0.088
(0.017)
0.190
(0,005)
0.095
(00033)
0.030
0.231
(0001)
0.008
(0002)
FPR
TPR
0.20
0.5
Methad
AFCP
0.4
AFCP1
AFCP+
0.3
Marginal
0.10
Partial
0.05
Attr bute: Workclass
Private
0.00
200
200
500
2000
Sample size
Figure A29: Performance on conformal p-values constructed by different methods for groups formed by Work Class. See Table A27 for numerical details and standard errors.
FPR
TPR
Method
0.25
AFCP
0.6
<s APCP1
0.20
AFCP+
* Marginal
0.15
Partial
Exhaustive
0.10
Attribute: E Education
0.05
H5-gad
0.00
Others
200
1000
2000
200
Seme-zollege
Sample size
Figure A30: Performance on conformal p-values constructed by different methods for groups formed by Education. See Table A28 for numerical details and standard errors.
51

---

Table A27: Coverage and size of prediction sets constructed with different methods for groups formed by Work Class. See corresponding plots in Figure A29.
AFCP
AFCPI
AFCP+
Marginal
Partill
Exhaustive
Astribute: Workelass
Sumple size
HPR
11%
FPR
1P%
FPR
HRR
1P%
TPR
F2R
TPR
Not private
Not prisaee
(3.015)
0.141
(0.025)
0.248
0.067
(0.015)
0.301
(0.016)
0.133
0.238
(0.015)
0.167
(0X026)
0.306
(0.002)
0.004
0.005
(0.000)
0.000
(0,000)
0.000
Not private
(0.010)
0.154
(0.023)
0.292
(0.010)
0.148
(0.025)
0.258
(0.013)
0.125
(0.076)
0.306
(0.01))
0.174
(0.019)
0.380
(0.006)
0.037
(0.012)
0.089
(0.000
0.000
(0.000)
0.060
Not private
1000
(0.012)
0.152
(0.019)
0.303
(0.012)
0.150
(0.018)
0.202
(0.013)
0.091
(0.024)
0.175
(0.012)
0.167
(0.019)
0.451
(0.08)
0.051
(0.018)
0.169
(0.00)
0.000
(0.000)
0.060
Not private
2000
(0.009)
0.133
(0.017)
0.371
(0.009
0.134
(3.010)
0.367
(0.00)
0.061
(0.021)
0.161
(0.008
0.147
(0.014)
0.481
(0.005
0.448
(0.013)
0.278
(0.001)
0.001
(0.001)
0.001
Private
Private
(0.008)
0:062
(0,021)
0.214
(0.005)
0.038
(0.014)
0.091
(0.008)
0.057
(0.022)
0.201
(0.007)
0.067
(0.019)
0.348
(0.001)
0,002
(0.002)
0.006
(0.000)
0.000
(0.000)
0.000
Privase
500
(0.005)
0.073
(Q.021)
0.283
(0.005)
0.073
(0.022)
0.254
(00055
0.056
(0.025)
0.239
(00055
0.076
(00021)
0.324
(0.063)
0.015
(0.012)
0.083
(0.000
0.000
(0.000)
0.000
Privase
1000
(0,005)
0,075
(0.020)
0.298
(0,00))
0,073
(0.018)
0.279
(0006)
01S55
(0.026)
0.178
(0.04)
0.073
(0.011)
0.386
(0.003)
0.021
(0.012)
0.144
(0.001)
00003
(0,065)
0.012
Privato
2000
(0.004)
0.083
(0.014)
0.356
(0.004)
0.085
(0.015)
0.353
(0005)
0.066
(0.017)
0.305
(00055
0.078
(0.013)
0.468
(0.003)
0.024
(0.012)
0 0.22
(0.002)
0.10
(0.004)
0,028
Table A28: Coverage and size of prediction sets constructed with different methods for groups formed by Education. See corresponding plots in Figure A30.
AFCP
AFCPI
AFCP-
Marginal
Parial
Exhasstiive
Astribute: Education
Sumple size
FPR
TPR
FPR
TPR
FPR
TPR
FPR
TPR
FPR
TFR
FPR
TPR
Bachelors
Bachelors
(0.020)
0.138
(0.036)
0.304
(0.012)
0,048
(0.021)
0.075
(0.019)
0.125
(0.035)
0.278
(0.017)
0.186
(0.030)
0.402
(0.000)
0,300
(0.000)
0.000
(0.000)
(0.000)
0,000
Bachelors
500
(0.022)
0,181
(0.038)
0.382
(0.020)
0.163
(0.057)
0.319
(0:020)
0.155
(0.038)
0.291
(0:019)
0.200
(0.050)
0.498
(0.008)
0.031
(0.023)
0.102
(0.000)
0,000
(0.000)
0,000
Bachelors
1000
(0.021)
0,141
(0.037)
0.315
(0.019)
0.133
(0.029)
0.267
(0.021)
0.095
(0.052)
0.171
(0.016)
0.203
(0.024)
0.570
(0.013)
0.063
(0.024)
0.201
(0.000)
0.000
(0.000)
0.000
Bachelors
2000
(0.017)
0.141
(0.027)
0.10
(0.016)
0.142
(0.027)
0.209
(0.018)
0.073
(0,029)
0.192
(0.011)
0.205
(0.019)
0.645
(0.010)
0.064
(0.025)
0.315
(0.000)
0,000
(0,000)
0,000
HS-grad
grad
200
(0,005)
0.045
(0.015)
0.105
(0.005)
0,032
(0.016)
0.089
(0.006)
0.045
(0.015)
0,105
(0.005)
0,050
(0.015)
0.117
(0.001)
0,001
(0.003)
0,005
(0.000)
0,000
(0,000
0,000
IIS-gral
500
(0.005)
0.054
(0.013)
0.134
(0,006)
0,059
(0.019)
0.135
(0.006)
0,050
(0.020)
0.126
(0.005)
0,056
(0.015)
0.162
(0.000)
0,010
(0.009)
0,309
(0,000)
0,000
(0,000)
0,000
HSS grad
1000
(0.866)
0.073
(0:021)
0.225
(UAKIT
0,075
(14020)
0.219
(0.Km)
0.053
(0.018)
0.133
(0.205)
0.056
(0.013)
0.211
(0.003)
0.011
(8:00
0.061
(0.005)
0.007
(0.00))
0.005
HS-grad
2000
(0.008)
0.080
(0.018)
0.284
(0.008)
(8:019)
D:228
(0.000)
DASS
(0.012)
0.147
(0.006)
B.064
(0.015)
0,260
(0.003)
0.017
(8:005)
0.089
(0.002)
0.014
(0,011)
0.063
Others
Others
(0.014)
0,080
(0.055)
0,237
(0001))
0,060
(0:025)
0.123
(B3114)
0,078
(0.054)
0.239
(0,012)
0
(0.050)
0.257
(0.001)
0,000
(0,005)
0.007
(0,000)
0,000
(0,00)
0,000
Others
500
(0.009)
0.095
(0.024)
0.312
(0,009)
0.897
(0:025))
(0,39)
(0.029)
0.243
(0:011)
0.10S
(0,022)
0.358
(0.035)
0,012
(0.017)
0.104
(0,000)
0300
(0,000)
0,000
Others
1000
(0.0999
0.096
(0.022)
0.365
(.000)
0.094
(1-023)
0'3400
(0
0.66
(0,026)
0.224
(0-010)
0.097
(0.021)
0.400
(0,004)
0.024
(0.015)
0.184
(0000)
0.001
(0.00)
0.001
Others
2000
(0.008)
0.095
(0.022)
0.418
(0.007)
0,099
(0.022)
0:816
(0.008)
0,062
(0.028)
0.234
(0.009)
0.093
(0.015)
0.516
(0.00N)
0.021
(0.014)
0.265
(0.000
0.008
(0.002)
0.009
Some college
Some-college
200
(0:013)
0.102
(0.032)
0.223
(0.035)
0.045
(0.018)
0.091
(0.014)
0.068
(0.032)
0.188
(0.014)
D.108
(0.033)
0.235
(0.004)
0.007
(0.00m)
0.014
(8,000)
0,000
(0,000
0,000
Some college
500
(0.010)
0.097
(0.029)
0.269
(0.011))
0.093
(0:030)
0.245
(0.099)
0,062
(0.050)
0.221
(0.011)
0.096
(0.027)
0.294
(0.007)
0.027
(0.01.5)
0.081
(0.000)
0,000
(0.000)
0.000
Same colleg
1000
(0.009)
0.095
(0.022)
0.236
10,008)
0.068
(8:0221
0:222
(0,00)))
0053
(0.022)
0.130
(0.00P)
0.095
(0,025)
0.315
(0,0001
0,041
(0.013)
0.117
(0,000)
0.000
(0.00)
0.000
Some-college
2000
(0.01 1)
0.093
(0:025)
0.325
(0.011)
0,093
(0:025)
0.319
(0:006)
0.051
(0.016)
0.149
(0.009)
0.068
(0.036)
0.387
(0.006)
0.009
(0.018)
0.135
(8.001)
0.001
(0.04)
0.009
Methad
0.25
AFCP
AFCP1
0.20
0.4
AFCP
Marginal
0.15
Partal
E Exhaustive
0.10
Attribute: Manital
0.05
Divorced
Marred-cN--spose
Never-mamied
Others
200
500
1000
2000
200
500
1000
2000
Sample size
Figure A31: Performance on conformal p-values constructed by different methods for groups formed by Marital Status. See Table A29 for numerical details and standard errors.
52

---

Table A29: Coverage and size of prediction sets constructed with different methods for groups formed by Marital Status. See corresponding plots in Figure A31.
APCP
AFCPI
AHCP=
Marginal
Partial
Exhaustive
Astribute: Mariaa staues
Sample
FPR
Divorced
Divoreed
(0.010)
(0.027)
(0.014)
(0.010)
0.107
(0,01))
(0.028)
(0.001)
Divoreed
500
(0.013)
0.054
(0.058)
0.174
0.058
(0,035)
0.174
0.055
(0,029)
0.114
(0.010)
0.348
(0.050)
0.139
0.013
(3,016)
0.037
0.000
(0,000)
0.000
Divurced
1000
(0.010)
0.037
(0.035)
0.141
(0.011)
0.036
(8,033)
0.144
(0,907)
0.017
(0.027)
0.089
(0.009)
0.031
(0.032)
0.151
(0.005)
0.005
(0.020)
0.053
(0.000)
0.000
(0.000)
0.000
Divorced
2000
(0.011)
0.054
(0.039)
0.224
(0.010)
10054
(0.039)
0.224
(0.013)
0.051
(0.034)
0.105
(0.009)
0,043
(0.940)
0.199
(0.005)
0.015
(0,030)
0.114
(0.000)
0.000
(0,000)
0.000
Married-dv-sponse
Married ci-roue-
200
(0.019)
0.164
(0.021)
(0.310)
(0,020)
(0.023)
(0.020)
0.386
(0.007)
0.000
(0,000
Marrie-cix-spooee
500
(0:015)
0.162
(0.022)
0.299
(0.015)
0.158
(0.025)
0.256
(0.013)
0.127
(0.027)
0.236
(0.014)
0.198
(0.021)
0.372
(0.008)
0.037
(0.012)
0.090
(0.000)
0,000
(0.000)
0.000
Marzied spouse
1000
(0:015)
0.179
(0.018)
0,315
(0815)
0.172
(0.015)
0.297
(0.014)
0.089
(0,024)
0.182
(0.011)
0.220
(0.013)
0.644
(0.00m)
0.061
(0.014)
0.162
(0.002)
0.007
(0,002)
0.009
Marriod-ct--posse
2000
(0.015)
0.161
(0.015)
0,375
(0016))
1382
(0.00.)
0.351
(0,006)
(0.017)
0.192
(0.010)
0.215
(0.011)
0,336
(0.006)
0.05%
(0.012)
01247
(0.003)
0.022
(0.00))
0,011
married
(0.0115)
(0.016)
(0.014)
(0.016)
(0,021)
(0.000)
Never-married
500
(0:006)
0.034
(0.023)
0.15%
(0,005)
(8/022)
0.147
(0.008)
0,040
(0.022)
0.150
(0.004)
0,025
(0,020)
0.132
(0.000)
0.006
(0.010)
0,050
(0.000)
0,000
(0,000)
0.000
Never-maried
1000
(8:899)
0.043
(0.024)
0.190
(0.099)
13845
(1AE3))
0.182
(0,009
0.001
(8:25)
0.166
(0.033)
0.019
(0,019)
0.163
(0.002)
0.007
(0.014)
0,077
(0.000)
0.000
(8,000)
0.000
mariid
2000
(0.009)
0.055
(0.056)
0.307
(0.000)
(0.036)
0.309
(0.008)
0.059
(0.052)
0.275
(0.003)
0,000
(0,023)
0.221
(0.002)
0.008
(0.017)
0.129
(0.000)
0.000
(0.002)
0,002
Others
Others
200
(0.013)
0,089
(0.022)
0.175
(0.099))
(0.011)
(0.029)
(0,029)
DO0C
0,005
0:000
Others
500
(0.011)
0.108
(0.025)
0.340
S0100
(8.021)
0.225
(0.013)
0,100
(0.023)
0.205
(0.011)
0.097
(0,025)
0.250
(0.005)
0.021
(8.014)
0,063
(0.000)
0,000
(0.000)
0,000
Others
1000
(0.011)
1,080
(0.0311)
0.262
(1111
(0.022)
0.255
(0.010)
0.046
(0.036)
0.149
(0.006)
0.071
(0.027)
0.259
(0.005)
0.025
(0.025)
0.342
(0.000)
0.000
(0,000
0,000
Others
2000
(0.012)
0,093
(0.022)
0.288
(0.015)
10998
(0.022)
0.299
(0.007)
0.039
(0.029)
0.131
(0.010)
0.069
(0.024)
0.256
(0.007)
0.035
(0.020)
0.155
(0.000)
0.000
(0,000)
0,000
FPR
TPR
AFCP
AFCP1
0.20
0.6
AFCP+
Marginal
0.15
Partial
Exhaustive
0.10
Attribute: Occupation
Adm-clerical
Craft-repair
Exec-manageria
Other-sarviee
0.0
200
500
1000
2000
200
500
1000
2000
Prof-specialty
Sample size
Figure A32: Performance conformal p-values constructed by different methous for groups formed by Occupation. See Table A30 for numerical details and standard errors.
FPR
TPR
Method
AFCP
AFCP1
AFCP+
0.2
0.0
Marginal
Partial
Exhaustive
0.1
Attribute: Relationship
Hushand
Not-in-tamily
Others
0.0
0.0
Own-child
200
500
1000
2000
200
500
1000
2000
Unmarried
Sample size
Figure A33: Performance on conformal p-values constructed by different methods for groups formed by Relationship. See Table A31 for numerical details and standard errors.
53

---

Table A30: Coverage and size of prediction sets constructed with different methods for groups formed by Occupation. See corresponding plots in Figure A32.
AFCPI
AFCP+
Marginal
Partial
Exhaustive
Actribute: Occupation
Sample size
FPR
TPR
FPR
TPR
FRR
TPR
FPR
TPR
FPR
TPR
HPR
TPR
Adm-clerical
Adm-clorical
200
(0.015)
0.099
(0.027)
0.286
(0.014)
0.058
(0.032)
0.126
10.015)
0.077
(0.028)
0,183
(0.018)
0.115
(0.028)
0.289
(0.002)
0.001
(0.010)
0.010
(0.030)
0.000
(0.0800)
0,000
Adm-clerical
500
(0.014)
0.122
(0.030)
0.242
(0.014)
0.107
(0.030)
0.192
(0.015)
0.118
(0.031)
0.209
(0.015)
0.136
00.028)
0.321
(0.012)
0.037
(0.020)
0.069
(0.000)
0.000
(8. (0.000)
0.000
Adm-clerical
1000
(0.0144)
0.108
(0.027)
0.248
(0.015)
0.112
(0.025)
0.245
(0.015)
0.076
(0.022)
0.128
(0.012)
0.095
(0.025)
0.281
(0.010)
0.042
(0.022)
0.133
(0.000)
0.000
(0.000)
0.000
Admiclerical
2000
(0.0144)
0.106
(0.035)
0.322
(0.0144)
0,102
0.312
(0.011)
0,099
(0.027)
0.132
(0.012)
0.086
(0.029)
0.352
(0.007)
0.0-1
(0.027)
0.176
00.000)
0.000
(0.000)
0.000
Craft-reguir
Crai-rrppir
200
(0.017)
0.103
(0.030)
0.176
(0002))
0,500
0.073
(0.016)
10006
0.099
0.165
(00029
(0.015)
0.108
(0.029)
0.183
(0.001)
0.004
0.008
(
(0,000)
0.000
(0.000)
0.000
Craft repair
500
(0.011)
0.075
(0.023)
0.187
(0013))
0,075
(0.02
0118
C100
0.09
00100
(001))
0.097
00.025
0.230
000000 00006300
0.023
0:071
(0:014)
(0000)
0.00
(0 (0.0000
0.000
Craft-repair
1000
(0.014)
0.128
(0.027)
0.242
(00L3)
0.125
(0,028)
0228
100
0065
0111
0.136
0.278
(0.021)
00015
(0000)
10000 1
(0:0099
0.022
Crafi-repair
2000
(0.012)
0.102
(0.022)
0.270
(000))
0180
(0,022)
(0000)
0063
(0.01))
(3100))
D-346
(0.00))
(0:013)
(0.010) 1
Exte-maangerial
Excc-manigerial
200
(0.019)
0.121
(0.033)
0.248
(0.009)
0.039
(0:021)
0.079
(0007)
0,109
000033
0.257
(0.017)
0,131
(0.051)
0.279
(00001)
0.001
(0.003)
0.003
0,000
10,000
00,0000
0.000
Esee-mumigrial
500
(0.017)
0.165
(0.033)
0.362
(0.018)
0.149
(0033))
n2988 2
(
0.139
(.0044) (
0222
(0.01))
0.179
(0.025)
0.489
0.39
0.017)
D.10S
(0/000)
00.0000)
0.000
Exae-manegerial
1000
(0.016)
0.139
(0.031)
0.340
0.128
(002
(0000)
0200
0.172
(
0.317
(0.02))
(00000
0.195
0.025)
100000
0.000
0000
Exee-mamgerial
2000
(0.013)
0.115
(0.021)
0.442
5110
(
(0000))
(0.13))
(00000)
0230
(0.013)
191
0.611
(0.005)
(0:018)
0310
10.000)
(00000)
0000
(0.0000 (0.0000)
0000
Othersservice
Other-ieriic
200
(0.007)
0.026
(0.034)
0.116
(0006))
0006
(0003)
0.050
(0007))
0,025
00007)
1000
01101
(0.006)
0,025
(0.056)
0.151
(0000)
0L000
000000
000000
0.000
00:0000
Other-service
500
(0.012)
0.065
(0.05))
0.240
000
(0000))
(0006)
(0008)
0180
0.44
(
(0.055)
0.242
000000
(0.00001
0-000
Other-service
1000
(0.008)
0.039
(0.228)
0
(0008)
0.38
(0000)
0128
(00077)
0034
(.025)
000e
0,35
00000)
0.129
00.000
2012
(0000
0.000
(00000
00000
0.000
0000
Other-eevicc
2000
(0.011)
(0.042)
0.253
(
(0.042)
(0.009)
(0,025)
(0.000)
0.22 1222
(0:029)
(0.004))
(2:11))
(0.000)
(00000))
Others
Others
200
(0.012)
0.058
(0.021)
0.141
(0002))
0.059
(0.024)
0.118
(0012)
0.066
000211
0.137
(0002)
0.060
00.024)
0.151
000022
0.005
000044
0.007
000000
0,000
00,0003
0.000
Others
500
(0.099)
0.064
(0.026)
0.187
(0009))
0.69
(0,02))
0.195
10010
0,054
0316
(.025)
(0,088)
0,588
0.18
0011
(00000
10000
(0,0000
0.000
Others
Others
2000
1000
(0.008)
(0.007)
0.070
(0.018)
(0.019)
0.225
(0007)
(0.010)
0.23
0077
(0,02))
0:229
0.221
(0.016)
(0000)
0,59
0054
(0.005)
(0.017)
(0017))
0116
1190
(0.077)
0,50
(0.00K)
0062
(0111))
0:245
00.003 
0:081
00.000
(00000)
02200
0000
(0-0072
0:027
(00000
Prof-specialty
Prof-specialty
Prof-specialty
200
500
(0.024)
(0.017)
0.196
0.094
(0.032)
(0,035)
0.309
0.248
(0.01.)
(0.11))
0.129
0.40
(0024)
(0,020)
D.079
02255
(0021)
(0006))
0.11K
0.091
02255
0232
(0027)
(0.017)
0.147
0.125
(.029)
0.308
0.85
000000
(1000)
(0:000 0
1000
D-000
1000000
000000
(0/000
10000
G000
(0:0000)
D-000
00000
spociipicially
1000
(0.016)
0.122
(0.018)
0.392
(0.1)))
0.120
(0019)
0.321
10.055
0074
(0020) 1
0,159
00.018)
0.464
(0.019)
003
1000000
(00000
0000
(0-0000
0.000
Prof-specialty
2000
(0.013)
(0.024)
0.411
(0.013)
0.131
(0.026)
0:400
(0.014)
0,075
0.205
(.009))
(0.012)
0.167
0.562
(.001)>
(0.005)
(0:017)
0.262 2
(0.000)
0,000
0.000 0
(0.000)
Sales
Sales
200
(0.016)
0.110
(0,035)
0.326
(0.088)
0032
(0.022)
0.10
(0006)
0. 105
(0.03))
0.306
(0.015)
0.127
(0.025)
0.415
(00022)
0002
(0:007)
0:015
6,000
(0000))
(0.000)
0.000
Sales
500
(0.0155
0.086
(0.035)
0.346
(0.11)
0,84
0.327
(0037)
(100))
0071
(0.038)
0.285
(0.019)
0.126
0.128
0.033))
(0000)
0021
020022)
0112
(0,000)
0,000
(0.000)
0.000
Soles
1000
(0.016)
0.105
10,025)
0.382
(0.015)
0191
(0024)
0.357
1220
(0032)
(0.012)
0.128
(0.025)
0.535
(7:22))
0:211
-
0,0000
(0.0000
-
1.000
(0.000))
0.000
2000
(0.014)
(0.031)
(0.014)
(0.031)
(0. (0.009)
(0.033)
(0.011)
(0.021)
(..009)
(0.025)
0.276
(0.000)
(0.000)
FPR
TPR
0.5
Method
AFCP
0.4
AFCP1
AFCP+
0.3
Marginal
0.06
Pertial
0.2
Exhaustive
0.03
Attribute: R Race
0.1
Others
0.00
0.0
White
200
500
1000
2000
200
500
1000
2000
Sample Figure A34: Performance on conformal p-values constructed by different methods for groups formed by Race. See Table A32 for numerical details and standard errors.
54

---

Table A31: Coverage and size of prediction sets constructed with different methods for groups formed by Relationship. See corresponding plots in Figure A33.
AFCP
AFCPL
AFCP+
Marginal
Partial
Exhaustive
Actribute: Relationship
Sumple sirce
FPR
TPR
FPR
IPR
FPR
IFR
EPR
TPR
FPR
IPR
EPR
TPR
Hushand
Hushand
200
(0.021)
0.181
(0.023)
0.256
0,086
(0.013)
0.112
(0,025)
0.251
(0.019)
0.196
(0.022)
0.313
(0.04)
(0.008)
0.007
(0.000
01000
(0.000
0.000
Hushand
300
(0.014)
0.170
(0.034)
0.321
(0.016)
0.169
(0.022)
0.256
(0.014)
0.136
(0.023)
0.254
(0.016)
0.213
(0.022)
0.400
(0.088
0.040
(0.013)
0.098
(0.000)
0.000
(0.00)
0.000
Hushand
1000
(0.018)
0.191
(0.019)
0.332
(0.015)
0.153
(0.019)
0.314
(0.0155
0.097
(0.025)
0.391
10.0131
0.239
(0.01.)
0.473
(0.06))
0.066
(0.015)
0.134
(0.003)
0.088
(0.002)
0.010
Husband
2000
(0.015)
0.160
(0.016)
0.389
(0.016)
0.161
(0.016)
0.385
(0.006)
0.074
(0.018)
0.207
10.01 11
0.235
(0.011)
0.537
(0.006)
0.061
(0.013)
0.262
(0.004)
0.025
(0.003)
0.024
fammii-familyy
Not-in-farsily
(0.007)
0.057
(0.018)
0.127
(0,005)
0,055
(0.010)
0.054
(0.00)
0,053
(0.019)
0.131
(0.00%
(0.020)
0.161
(0.00))
0.001
(0.002)
0.005
(0.000)
0:000
(0.000
0.000
Not-in family
500
(0.009)
0.062
(0.030)
0.227
(0.08)
0.083
(0.018)
0.217
(0,00))
0.077
(0.019)
0.193
(0.06)
0.068
(0.019)
0.301
(0.00)
0.016
(0.009)
0.064
(0.00)
0.000
(0000)
0.000
Not-in famuly
1000
(0.009)
0.364
(0.022)
0.224
(0.009)
0.061
(0.022)
0.217
(0.099)
0.083
(0.022)
0.341
(0.05))
0.015
(0.016)
0.215
(0.00)
0.016
(0.012)
0.108
(0.000)
0.000
(0.000
0.000
Not in family
2000
(0.009)
0.080
(0.026)
0.295
(0.009)
0.081
(0.025)
0.300
(0.00)
0.000
(0.029)
0.188
(0.044)
0.033
(1005))
0.244
(0.004)
0.023
(0.012)
0.144
(0.000)
0.000
(0.00)
0.000
Others
Others
200
(0.008)
0.025
(0.013)
0.066
(0.007)
0.016
(0.010)
0.005
(0.088
0.021
(0.014)
0,061
(0.007)
0.022
(0.01
0.078
(0.000)
0.000
(0.000)
0.000
(0.000)
0.000
(0.000
0.000
Others
500
(0.312)
0.059
(0.019)
0.117
(0,009)
0.045
(0.017)
0.093
(0.000)
0.011
(0.019)
0.082
(0.012)
0.051
(00211)
0.146
(0.06)
0.012
(0.009)
0.021
(0.00))
0.000
(0.00)
0.000
Others
1000
(0.008)
0.349
(0.022)
0.172
(0.008)
0,051
(0.019)
0.154
(0.088
0.011
(0.027)
0.100
(0.05))
0.062
(00026)
0.195
(0.006)
0.017
0.089
10
(0.000)
0.000
(0.000
0.000
Others
2000
(0.015)
0.001
(0.025)
0.245
(0.015)
0.001
(0.025)
0.237
(0.009)
0.036
(0.018)
0.062
(0.015)
0.001
(0.022)
0.321
(0.008)
0.026
(0.016)
0.114
(0.000)
0.000
(0.000
0.000
Own-child
Own-child
200
(0.001)
0,008
(0.018)
0,025
(0.001)
0,010
(0.011)
0.011
(0.03))
(0.018)
0,025
(0.00))
0,010
(0.000)
0.023
(0.001)
0.001
(0.000)
0.000
(0.000)
0.000
(0.00)
0.000
Own-child
500
(0.009)
0.017
(0.040)
0.089
(0.009)
0.017
(0.012)
0.097
(0.009)
0.036
(0.04L)
0.103
(0.002)
0.005
(0.000)
0.067
(0.000)
0.000
(0.012)
0.017
(0.000)
0.000
(0.000
0.000
Own child
1000
(0.014)
0.041
(0.060)
0.214
(0.014)
0.041
(0.040)
0.200
(0.01))
0.072
(0.055)
0.167
(0.002)
0.008
(0.050)
0.158
(0.001)
0.002
(0.049)
0.117
(0.000)
0.000
(0.000
0.000
Own-child
2000
(0:012)
0.054
(0,050)
0.363
(0.012)
0,054
(0,050)
0.363
(0.011)
0.04
(0.055)
0.312
(0.003)
0.011
(0.019)
0.208
(0.002)
0.006
(0.026)
0.127
(0.000)
0.000
(0.007)
0.007
Unmarried
Unmarried
200
(0.008)
0.035
(0.025)
0.084
(0.005)
0,018
(0.011)
0.015
(0.08)
0.031
(0.024)
0.078
(0.009)
0.041
(0.029)
0.111
(0.000)
0.000
(0.000)
0.000
(0.000
0.000
(0.00)
0.000
Unmarried
500
(0.310)
0,360
(0.022)
0.112
(0.010)
0.057
(0.027)
0.102
(0.011)
0.055
(0.022)
0.302
(0.010)
0.060
(0.02.)
0.301
(0.00))
0.017
(0.013)
0.020
(0.000)
0.000
(0.000
0.000
Unmarried
1000
(0.0077
0.044
(8.054)
0.144
(0.009)
0.044
(0:035)
0.142
(0.07)
00044
(0.029)
0.009
(0.007)
0.038
((.0E1)
0.157
(0.004)
0.016
(0.023)
0.089
(0.000)
0.000
(0000)
0.000
Unmaried
2000
(0.01.0)
0,050
(0.031)
0.218
(0.012)
0.008
(0.031)
0.226
(0.008)
0:025
(0.027)
0.10K
(0.006)
0.026
(0.030)
0.159
(0.005)
0.033
(0.021)
0.000
(0.000)
0.000
(0.000
00000
Table A32: Coverage and size of prediction sets constructed with different methods for groups formed by Race. See corresponding plots in Figure A34.
AFCP
APCPI
AFCP+
Marginal
Pactial
Exhaustive
Astribute: Race
Sample
HPX
TPR
TPR
HPX
TPR
TPR
TPR
TPR
Others
Others
(0.019)
0,052
(0.029)
0.190
(0.005)
0.028
(0.018)
0.084
(0,009)
(0.027)
0.169
(0.0019
0.060
(0.028)
0.217
(0.0011
(0.034)
0.006
(0.000)
0.000
Others
(0.009)
0.074
(0.026)
0.236
(0.000)
0.070
(6.029)
0.222
(0.008)
0.061
(0.025)
0.190
(0.000)
0.082
(0.027)
0.295
(0.004)
0.019
(0.014)
0.068
(0.000)
0.000
(0.000)
0.000
Others
1000
(0.008)
0.075
(0.027)
0.266
(0.009)
0.077
(0.025)
0.254
(0.009)
0.056
(0.027)
0.167
(0.009)
0403
(0.026)
0.308
(0.005)
0.026
(0.019)
0.144
(0.0000
0.000
(0.000)
0.000
Others
2000
(0.009)
0.079
(0.027)
0.299
(0.009)
0.078
(0.028)
0.248
(0.008)
0.048
(0.027)
0.172
(0.006)
0.064
(0.025)
0.355
(0.005)
0.029
(0.022)
0.209
(0.0000
0.000
(0.000)
0.000
White
White
(0.009)
0.085
(0.021)
0.229
(0.005)
(0.011)
0.095
(0.010)
0.079
(0.022)
0.218
(0.005)
(0.020)
0.271
(0.001)
(0.002)
0.006
(0.000)
(0.000)
0.000
White
(0,005)
0.096
(0.020)
0.289
(0,006)
0.095
(6.022)
0.258
(0.006)
0.084
(0.024)
0.250
(0.006)
0.103
(0.019)
0.349
(0003)
0.021
(0.011)
0.086
(0.000)
0,000
(0.000)
0.000
White
1000
(0.006)
0.095
(0.015)
0,301
(0.005)
(0:014)
02285
(0.007)
0.065
(0.023)
0.177
(0.005)
0.099
(0.012)
0.417
(0:004)
191234
(0.013)
0.153
(0.001)
010035
(0.002)
0.505
White
2000
(0.004)
0.098
(0.015)
0. 368
(0.004)
1.00
(0.015)
D3365
(0.006)
0.860
(0.017)
0.192
(0-005)
0.101
(0.011)
0.486
(0.0015)
0.000
(B.011)
0.233
(0.001)
0.000
(0:001)
0.020
55

---

FPR
TPR
AFCP
AFCP1
0.10
AFCP+
Marginal
Partial
0.2
Exhaustive
A Attribute: Sex
Femoli
0.00
0.0
Male
200
500
1000
2000
200
500
1000
2000
Sample
Figure A35: Performance conformal p-values constructed by different methods for groups formed
by Sex. See Table A33 for numerical details and standard errors.
Table A33: Coverage and size of prediction sets constructed with different methods for groups formed by Sex. See corresponding plots in Figure A35.
AFCP
AFCPI
AFCP+
Marginal
Portial
Exhanstive
Sample size
Antribute: Sex
FFX
TPR
FFX
TPR
FFX
TPR
FFX
TPR
FFX
TPR
PPR
TPR
Female
Female
200
(0.007)
0.047
(0.015)
DJ077
(0.005)
0.031
(0.008)
0.035
(0.007)
0.045
(0.014)
0.072
(0.008)
0.057
(0:014)
0.095
(0,000)
0.001
(0.000)
0.800
(0:000)
8,000
(0,000)
0,000
Fosale
(0.807)
0.865
(0.016)
0.145
(0.007)
0.061
(0.014)
0.125
(0.808)
0.063
(6:016)
0.110
(0.005)
0.055
(0:018)
0.159
(0.033)
0.013
(0.009)
0.038
(0:000)
0.000
(0.000)
0.000
Fomole
1000
(0.017)
0.170
Female
(0.007)
(0.019)
(0.007)
(0.020)
(0.007)
(0.005)
(0.015)
(0.005)
(0.010)
(0.000)
Male
Male
200
(0.012)
0.100
(0.022)
0.252
(0.006)
D.054
(0.012)
0.105
(0.012)
D,095
(0.024)
0.239
(0.010)
0.111
(0.021)
0.257
(0,002)
0,044
(0.002)
0.007
(0.000)
0:000
0,000
(0.000)
Male
(0.007)
0.109
(0.021)
0.310
(0.008)
0.109
(0,02))
0.299
(0,000
0.090
(8.026)
0.247
(0.008)
0.126
(0000))
0.377
(0 0000
0,024
(8.012)
0.093
(0:000)
0.000
0.000
0.204
0.187
0.120
0.445
0.107
(0007))
(0,008)
(0,007)
(0001))
(0000
(0:014)
0.110
0.205
0.022
(0.010)
(0.003)
(0.0122
0.15
0.5
M ethhod
AFCP
AFCP1
0.10
AFC?+
Marginal
Partial
Exhaustive
0.05
A Atrrbute: Country
United-States
200
500
2000
2000
200
500
1000
2000
Sample size
Figure A36: Performance on conformal p-values constructed by different methods for groups formed by Country. See Table A34 for numerical details and standard errors.
56

---

Table A34: Coverage and size of prediction sets constructed with different methods for groups formed by Country. See corresponding plots in Figure A36.
AFCP
AFCP)
AFCP+
Marginal
Partial
Exhauative
Antribute: Country
Sample size
FFX
1PR
FFR
1PR
TPR
FFR
TFR
FFR
1PR
FFR
TP%
Others
Others
200
(0.017)
0.896
(0.032)
0.214
(0.013)
0.0K0
(0.018)
0.090
(0.017)
0.092
(0.032)
0.204
(0.014)
0.095
(0.030)
0.226
(0,000)
0,000
(0.004)
0.004
(8.000)
8.000
(8,000)
0,000
Otheers
500
(0:013)
0.081
(0.028)
0.185
0.073
(0.012)
(0.025)
0.155
(0:012)
0.075
(0.034)
0.147
(8:016)
0.120
(0.035)
0.319
(0.038)
0.034
0,051
(8.000)
0.000
0,000
Others
(0.012)
(0.013)
(0.050)
(0.012)
United-States
United-States
200
(0.008)
0.079
(0.0200
0.226
(0.001)
0.043
(0.010)
0.094
(0.009)
B-073
(0.021)
0.214
0-0P0
(0.007)
(0.018)
0.200
(0.001)
0.003
(0.002)
0.006
(0.000)
8.000
(0.000)
8,000
United States
500
(0.005)
0.094
(0.021)
0.093
(0.00))
(0.024)
0.264
(0.005)
0.081
(0.025)
0.097
(0.00)
(0:019)
0.346
0.019
(0.003)
(0.017)
(8.000)
0.000
0.097
0.057
0.095
0.050
57

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of this work in the Discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
58

---

All assumptions are stated in the paper and all proofs are provided in the Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The paper fully discloses the information needed to reproduce the main experimental results. Additionally, code is provided.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
59

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The paper provides open access the code needed reproduce the main perimental results, and precise information about how the open-domain data were obtained.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
cnnolicyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpp/.ccpppliiiii/mmm/tao./nttc wwtppccppcc////ccccccccccccccclt http//uudeeeeeeeee https//oooSSuuiisseeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specify all the training and test details necessary understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper reports error bars or standard deviations where appropriate, along with suitable explanations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
60

---

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 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 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 figures symmetric error bars that would yield results that are out 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.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed 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 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 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 NeurlPS Code of Ethics https :tttpp::///erre http///eurrrp.eeeee htpppbliccc.hiiiiiiiaiiaaaaiiaie
didn't make into the paper).
9. Code Of Ethics
Question:
Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal 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 the paper. However, this paper focuses on foundational research that is not tied particular application.
61

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
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)?
Question:
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 high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make 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 existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
62

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddataees has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. 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/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. 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 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
63

---

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.
64


Reviews:
[{"review_id": "bLMKy85LDq", "reviewer": "Reviewer_mW3F", "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.\n\n[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.", "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?\n\n2. How does the size of the restricted calibration sample affect the performance of the algorithm?", "limitations": "The authors discuss the limitations in the Discussion section.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The problem of conformal inference with equalized coverage is an important problem and of interest to the community.\n2. The trade-off between efficiency and equalized coverage addressed in the paper is challenging and of practical significance.\n3. Empirical evaluation demonstrates the performance improvement of AFCP over baselines.", "weaknesses": "1. The clarity of the paper can be greatly improved. Detailed comments:\n- p2 l37: \"A limitation of the current method for conformal inference with equalized coverage....\" -- what is the current method?\n- p2 l41: what do you mean by efficiency and informativeness here? Is it set size? Please make it clear and precise.\n- 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.\n- The notations are incorrect in some places and unnecessarily complex\n   - 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\n   - 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$\n- It is not clear at some places whether $A$ refers to single attribute or set\n   - Alg 2 l4-5: in line 4, $A$ refers to single attribute, in line 5 it refers to multiple (set of) attributes\n   - p6 l197: (7) returns a final selected attribute while the sentence refers to subset of attributes\n- p6 l204: minor comment, this does not hyperlink to A1\n- typos in table captions (Table A25 onwards)\n   \n2. 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.\n\n3. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and constructive feedback. We have addressed your questions and concerns point-by-point below.\n\n## Additional experiments\n\nMight you have missed some experiments described in the Appendix and mentioned in Section 3.4? We will highlight these experiments more clearly in the main text. In any case, following your suggestion, we have also conducted new experiments using the Correctional Offender Management Profiling for Alternative Sanctions (COMPAS) dataset. \n\n**Experiments in the Appendix.** In addition to using the two datasets described in the main paper (one synthetic dataset and the nursery data), we had conducted experiments using an additional synthetic dataset (Appendix A7.2.2) and a common benchmark dataset, the Adult Income Dataset (Appendix A7.2.3). The experiments with the income data also include an AFCP extension that allows for the selection of multiple sensitive attributes. This extension is referred to as the \"APCF+\" method (depicted by the green lines) and is presented in Figures A24–A33. We will better highlight these experiments in the revised paper.\n\n**New experiments with COMPAS data.** The COMPAS dataset is used for multi-class classification tasks, predicting the risk of recidivism across three categories: 'High,' 'Medium,' and 'Low.' As illustrated in the **new Figures 1-2** in the attached PDF document, these additional experiments consistently demonstrate that our AFCP method outperforms other benchmarks. Specifically, it achieves higher conditional coverage than the Marginal method and, on average, produces smaller prediction sets than the Exhaustive and Partial methods. These results are consistent with those presented in the paper and will be includes in the revised paper. Thank you!\n\n## Comparisons between AFCP and AFCP1\n\nBoth AFCP and AFCP1 outperform benchmark approaches with small sample sizes, excelling in different areas. AFCP is better suited for scenarios where there is uncertainty about the presence of significant algorithmic bias. On the other hand, AFCP1 is more effective when there is prior knowledge that at least one attribute may be biased. This distinction will be clarified in the revised paper.\n\nIn Figure 3, where one group (Color - Blue) is consistently biased, AFCP1 achieves slightly higher conditional coverage than AFCP. While AFCP shows slight undercoverage for the blue group with small sample sizes, it still performs better than the Marginal approach.\n\nAFCP's occasional inability to select a sensitive attribute with small sample sizes reflects the inherent challenges of small datasets rather than a flaw in the method. When the method does not select an attribute, it often indicates a lack of sufficient evidence of algorithmic bias, making it reasonable to calibrate the prediction sets only for marginal coverage.\n\n## Comparison Between AFCP and the Exhaustive Approach\n\nOur AFCP method offers advantages over the Exhaustive approach, especially when the sample size is small and the specific attributes indicating biased groups are not known beforehand.\n\nFor instance, in a dataset with five binary attributes where only two are significantly associated with algorithmic bias, an Exhaustive approach would have to consider all five attributes or all combinations of two attributes to ensure valid coverage. This process is inefficient. In contrast, our method can identify the two most relevant attributes in a data-driven way. It then focuses on calibrating the prediction sets within the subgroups formed by these attributes. \n\n## Impact of Calibration Sample Size\n\nWe are not completely sure about the meaning of \"restricted calibration sample\" in your question, but we will interpret it as the number of calibration samples belonging to the biased group identified by the selected attribute. Please correct us if this is not what you meant.\n\nIn general, larger sample sizes make it intrinsically easier to identify (and thereby enable mitigating) significant algorithmic biases. Conversely, if the sample size within any group is small, it is more difficult to estimate the coverage within that group. This can result in our method selecting the “wrong” sensitive attribute. However, despite this unavoidable difficulty, the experiments demonstrate that our method performs well relative to other approaches both in small-sample and in large-sample settings. \n\nIn particular, Figures 3 and 4 study the performance of our method as a function of the total number of samples in the training and calibration data. From these two plots we can see that when the sample size is as small as 200, it is challenging to select the true attribute because the data is subject to greater variability. Nevertheless, our method is able to select the “correct” attribute often enough to obtain informative prediction sets with significantly higher conditional coverage compared to the marginal approach. \n\nFigure 4 shows that, as the sample size increases, it becomes more likely for our method to select the correct sensitive attribute, as anticipated. The new COMPAS experiments we conducted following your suggestion demonstrate consistent behavior and confirm the practical advantages of our method. \n\nTo better investigate the effect of “restricted” sample size for the biased group associated with the attribute selected by our method, we counted the number of data points in the protected group for each experiment and averaged the results over 100 independent experiments. The results are plotted in the **new Figure 3** in the attached PDF document. Please let us know if this answers your question.\n\n## Clarity and Typos\nWe will fix the typos and make the clarifications you suggested. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3V5UYW8FUX", "reviewer": "Reviewer_asc2", "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.", "questions": "What is the computational complexity of the proposed method, and how does it scale with large datasets?\nAre there any optimization strategies to improve efficiency?\n\nHow stable is the attribute selection process across different sample sizes and datasets?\nCan the method handle cases where multiple sensitive attributes need to be considered simultaneously?\n\n\nCan the method be tested on more diverse and larger real-world datasets to validate its scalability and generalizability?\nHow does the method perform in scenarios with highly imbalanced datasets?\n\nHave other attribute selection procedures been considered, and how do they compare with the proposed leave-one-out approach?", "limitations": "yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses a significant and timely problem in machine learning—ensuring fairness and reliability in prediction sets. The introduction of AFCP, which dynamically adjusts for biases in a data-driven manner, is an innovative and practical contribution.\n2. The paper provides a strong theoretical basis for AFCP, clearly defining adaptive equalized coverage and offering proofs to support the validity of the method.\n3. The empirical results are robust, covering synthetic and real-world datasets. The comparisons with other benchmarks are comprehensive, demonstrating the practical benefits of AFCP in various scenarios.\n4. The method's steps, including automatic attribute selection and prediction set construction, are well-explained and logically structured.", "weaknesses": "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.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper and providing constructive feedback. Please find our responses below.\n\n## Computational Complexity Analysis \n\nAs (perhaps too) briefly mentioned in Section 1.4, Appendix A6 provides a detailed computational complexity analysis for implementing our algorithms for either a single test sample or multiple test samples. Is this the information you were looking for? We will make the reference to this analysis clearer in the camera-ready version.\n\nNotably, our AFCP methods can be efficiently implemented for multiple test samples using a shortcut. Specifically, the identification of each subgroup in the calibration set does not rely on the test sample and can be reused to calculate group-wise FPRs and miscoverage rates for different test samples. For instance, this shortcut reduces the computational complexity of the AFCP method from $\\mathcal{O}(mn\\log n + nKMm)$ to $\\mathcal{O}(n\\log n + nm + MK(n + m))$ in outlier detection settings, where $n$ is the calibration set size, $m$ is the number of test samples, $K$ is the total number of sensitive attributes, and $M$ is the maximum count of groups across all attributes.\n\n## Impact of Small Sample Sizes\n\nAlthough any attribute selection procedure may be less stable and effective with small sample sizes, we see this as an inherent challenge of small data sets rather than a flaw of our method. As mentioned in response to another comment, future work could explore the performance of our method in combination with different attribute selection procedures, as it is possible that alternative approaches may perform better in different settings, including with small sample sizes. However, the empirical performance of our AFCP method, as currently implemented, already surpasses that of other benchmark methods applied to the same data, in both large-sample and small-sample settings.\n\nFor instance, in the experiments of Figures 3 and 4, it is challenging to accurately identify the attribute associated with significant algorithmic bias when the sample size is as small as 200. However, AFCP manages to select the correct attribute frequently enough to achieve significantly higher conditional coverage compared to the Marginal method, without substantially increasing the average prediction set size. Figure 4 further illustrates this behavior, showing the selection frequency of each attribute. As the sample size increases, our method begins to consistently select the correct attribute in all instances.\n\nThese findings align with new experiments based on the COMPAS dataset, summarized in the attached one-page PDF.\n\nWe will incorporate these explanations into the revised paper to emphasize the advantages of our methods with small sample sizes. Thank you for your comment!\n\n## Simultaneous Selection of Multiple Attributes \n\nThe appendix of our paper describes variations of our AFCP method that are designed to select and protect multiple attributes simultaneously. Specifically, in Appendix A2, we describe AFCP with multiple selected attributes in the multi-class classification setting, and in Appendix A4.3, we detail AFCP with multiple selected attributes in the outlier detection setting. Appendix 7.2.3 presents experimental results when multiple attributes can be selected using the real-world Adult Income Data. We will strive to better highlight these extensions of our method in the revised paper.\n\n\n\n## Additional Experiments with Real Datasets\n\nOur proposed method is broadly applicable and can be efficiently applied for a variety of classification and outlier detection tasks. In this paper and appendices, we demonstrated its performance using two synthetic datasets and two real-world datasets. To supplement those results, in response to your feedback and the feedback of other reviewers, we have also conducted new experiments using the widely studied COMPAS dataset. The results obtained with the COMPAS dataset are summarized in the **new Figures 1-3** in the attached one-page PDF document. These additional experiments lead to conclusions that are qualitatively similar to those of the previous experiments. However, since this is a well-studied and interesting data sets, we think it may be valuable to include these new results in the revised paper.\n\nRegarding the applicability of our method to imbalanced data, please note that the new experiment on COMPAS data for recidivism prediction, for example, involve imbalanced data, with roughly 10\\% of samples having the response label \"High\", 20\\% having the label \"Medium\", and 70\\% having the label \"Low\".\n\n\n## Alternative Attribute Selection Procedures\n\nThank you for this thoughtful question. While the underlying ideas of our method are indeed flexible enough to incorporate attribute selection procedures that go beyond those considered in this paper—a strength we will emphasize more in the revision—we believe that delving into the subtle empirical trade-offs associated with different selection algorithms is beyond the scope of this paper. We hope that our work will inspire future research to explore this question further.\n\n        \n## Additional References\n\nFollowing your advice, we will include more references to recent works on robust conformal inference under distribution shift. Although these works address different problems and take different perspectives, they are sufficiently related to merit mention in Section 1.5 (Related Works). The additional page allowed in the camera-ready manuscript will enable us to briefly discuss these references without sacrificing other content. We believe this addition will provide broader context on recent trends and highlight opportunities for integrating ideas in future research. Thank you for this helpful suggestion!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "danz4UBcxI", "reviewer": "Reviewer_FDCZ", "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.", "questions": "1.\tCoverage 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.\n2.\tImpact 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": "Please refer to the weakness.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The method efficiently identifies and addresses algorithmic biases, ensuring fair treatment of sensitive groups without sacrificing informativeness. \n2. AFCP provides a practical compromise between efficient, informative predictions and algorithmic fairness by adjusting prediction sets for sensitive groups.\n3. Demonstrated effectiveness on both synthetic and real-world datasets, outperforming traditional methods in terms of both fairness and prediction informativeness.", "weaknesses": "1.\tLimitation 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.\n2.\tSample 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.\n3.\tComputational 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review, which allows us to clarify key points and address potential misunderstandings. We believe these clarifications will enhance the paper's accessibility.\n\n## Clarification on Method Aims\n\nWhile other reviewers have praised the paper for its clarity, we appreciate the opportunity to refine our explanations and address your concerns. Specifically, we would like to clarify the role of the attribute selection component in our method, and the reason why we provide formal guarantees for the coverage of the prediction sets rather than for the \"correctness\" of the selection procedure.\n\nThis paper addresses the problem of constructing prediction sets with guaranteed coverage conditional on adaptively selected sensitive attributes. As you noted, our goal is to bridge the gap between existing approaches for marginal and group-conditional conformal prediction, finding a practical balance between efficiency and fairness.\n\nTo obtain reliable inferences and approximately maximize conditional coverage, our method seeks to identify the attribute (or attributes) most likely to result in significant under-coverage under a standard (marginal) conformal inference approach. The specific selection algorithm proposed in this paper has demonstrated strong practical performance, as evidenced by our numerical experiments (see Figure 4 and the new Figure 2 in the PDF supplement accompanying this response). However, the core ideas of our method are flexible enough to accommodate different selection algorithms. In the revised manuscript, we will better highlight this flexibility.\n\nA consequence of this flexibility and \"assumption-lean\" setup is that establishing formal guarantees about the selection of the \"correct\" attribute would be challenging and somewhat limiting. It would require stronger assumptions, and it would necessitate a theoretical analysis heavily dependent on the specific implementation details of the selection algorithm. While this may be an interesting direction for further research, potentially strengthening the connection to Cherian and Candès (2023), it falls outside the scope of this paper.\n\n## Impact of Calibration Sample Size\n\nConstructing informative prediction sets with high conditional coverage is more challenging with smaller sample sizes. This is an inherent challenge, not a specific limitation of our method, and it explains why our experiments focus on comparing the performance of our method against several benchmarks across various sample sizes. These experiments demonstrate that our method consistently performs well across all sample size scenarios. For detailed results, see Figures 3–5 in the paper and the new Figures 1–3 in the PDF supplement accompanying this response.\n\nFor example, in the experiments pf Figures 3 and 4, when the sample size is as small as 200, it is inherently challenging to: (1) fit an accurate predictive model, (2) assess conditional coverage, (3) and reliably identify the sensitive attribute associated with the lowest coverage. This is reflected by the relatively large size of the prediction sets output by all methods and by the relatively large discrepancies between the nominal and empirical conditional coverage levels. Nevertheless, our method manages to frequently select the \"correct\" sensitive attribute, achieving significantly higher conditional coverage compared to the standard \"marginal\" benchmark, with only a slight increase in prediction set sizes. Further, as the sample size increases, our method becomes highly effective at identifying the attribute with the lowest conditional coverage, as illustrated in Figure 4. This allows our method to achieve high conditional coverage with relatively small prediction sets. Overall, these experiments demonstrate that our method offers distinct advantages over existing approaches in both large-sample and small-sample settings.\n\n## Applicability and Computational Cost\n\nOur proposed AFCP method is quite broadly applicable and can be efficiently implemented in many classification settings where the number of labels is not exceedingly large. Natural applications include predicting recidivism risks, determining graduation classes, and addressing binary classification problems such as spam detection and credit default risk assessment.\n\nHowever, in scenarios where the number of possible classes is extremely high, it is true that the computational cost of our method may become a limiting factor. While addressing this issue is beyond the scope of this paper, we believe that extending our method to accommodate extreme classification tasks presents valuable opportunities for future research. In the revision, we will highlight these opportunities and cite relevant works in the conformal inference literature, such as [1]. These references will provide additional context and potential inspiration for future developments.\n\nReference: [1]\"Class-Conditional Conformal Prediction with Many Classes.\" Ding et. al., NeurIPS 2023.\n\n## Clarifications on Figure 5\n\nThe behavior observed in Figure 5 can be easily explained. The horizontal axis represents the cumulative sample size, which includes both training and calibration samples. As the cumulative sample size increases, more data becomes available to train a more accurate predictive model. This increased accuracy explains why the conditional coverage for Occupation 1 improves while the average prediction set size decreases: the model becomes more precise for all individuals, including those most affected by algorithmic bias.\n\nThe main takeaway from Figure 5 is that our method consistently provides relatively informative and reliable predictive inferences compared to other conformal inference approaches, regardless of the amount of available data or the varying accuracy of the underlying machine learning model. Note that the model varies for different sample sizes but remains the same for all conformal inference methods, ensuring a fair comparison.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QNSmmUt4VC", "reviewer": "Reviewer_92Kn", "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.", "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.\n- 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": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written, with good organization, clear problem statement and easy-understanding method description.\n-  The proposed fairness notion is novel and critical for real-world application. It provides a feasible solution to migitage the tradeoff between fairness and efficiency. It is also impressing that the method works with small sample size.\n- The experiments and theorem are comphrensive and supportive of method and claims.", "weaknesses": "- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and insightful feedback.\n\n## Seeking Different Fairness Criteria\n\nThe potential for our method to be adapted based on different fairness criteria, going beyond our notion of selectively equalized coverage, is indeed both intriguing and promising. Although exploring those questions goes beyond the immediate scope of this paper, we hope that others will be inspired to improve and build upon our work in this direction. We will definitely add this suggestion in the revised manuscript. \n\n## Classification with Ordered Labels\n\nIn our current framework, we have focused on predicting categorical (unordered) labels. If the labels are ordered, an easy modification of our method would require only a small change to Equation (8). Specifically, when the target variables are ordered labels (say level 1 $<$ level 5), then $\\hat{C}(X_{n+1})$ becomes the discrete convex hull of all its components on the right-hand side in Equation 8. Because the prediction set resulting from taking unions will be a subset of the prediction set resulting from taking discrete convex hulls, the new prediction set will automatically satisfy the adaptive equalized coverage defined in Equation (3). An intriguing question, which may be investigated in future work, is whether it is possible to devise a better approach for ordinal labels. Thank you for this helpful comment. We will include this discussion in the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are grateful to the four referees for their detailed reviews and constructive suggestions. We have addressed their questions and concerns point-by-point below. In addition to providing several clarifications, which can be easily reflected in the camera-ready manuscript to enhance its accessibility and completeness, we conducted additional experiments using the COMPAS [1] dataset. The results of these experiments, which align with those already described in the paper, are summarized in the three figures contained within the attached one-page PDF file.

How we have addressed the main points raised by the reviewers:

- **Extended Empirical Evaluation:** We clarified potentially unclear aspects of our empirical evaluations and highlighted additional experiments described in the Appendices that may have been previously overlooked. We also conducted further experiments using the COMPAS dataset, a well-known benchmark for algorithmic fairness research.

- **Clarifications on the Aims and Performance of the Attribute Selection Procedure:** We provided a more detailed discussion of the attribute selection component of our method, including its performance as a function of sample size. This discussion provides additional details, which will be incorporated in the revised manuscript, and explicitly highlights aspects of the existing figures and discussions that might have been previously overlooked.

- **Deeper Comparison Between Variations of Our Method:** We elaborated further on the relative strengths of the two variations of our method, AFCP and AFCP1. Additionally, we highlighted the presence of additional extensions described in the Appendices, designed to select more than one sensitive attribute simultaneously. These extensions may have been previously overlooked by some reviewers.

-  **Clarifications on Scalability and Complexity:** We pointed out that the Appendices include a detailed discussion of the computational complexity of our method, which may have been missed by one reviewer.

- **Opportunities for Further Research:** We acknowledged and commented on several intriguing suggestions for further extensions of our method and other opportunities for follow-up research proposed by the referees. We are grateful for these ideas and look forward to including their discussion in the camera-ready version of the paper.

- **Clarifications on Notation:** We gratefully acknowledged the presence of some typos and potentially confusing notations pointed out by one reviewer. These issues will be corrected in the camera-ready version of the paper.

Reference: [1] ProPublica. (2016). Compas recidivism risk score data and analysis. Retrieved from https://github.com/propublica/compas-analysis.

Meta-review: 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.
Decision: Accept (poster)