Conformal Classification with Equalized Coverage for Adaptively Selected Groups

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.

Strengths

- The paper is well written, with good organization, clear problem statement and easy-understanding method description. - 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. - 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. - Though a little out of scope, this paper would be better to provide performance evaluation with presence of distribution shift, especially label shift and shift in protected attributes.

Questions

- Would your method preserve satisfy more rigorous fairness (Q1) with better design? I think this may be related with union of sub-intervals. Adaptively adjust the coverage rate of subgroup may help. - Also, the union of sub-intervals may make less sense in some real-world applications. Say, in some data, the target variables are some categorical and also ordered labels, say level 1~5. Predicting a sample to be either level 1 or 5 is confusing. Have this phenomenon be considered and addressed in your paper?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes

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.

Strengths

1. The method efficiently identifies and addresses algorithmic biases, ensuring fair treatment of sensitive groups without sacrificing informativeness. 2. AFCP provides a practical compromise between efficient, informative predictions and algorithmic fairness by adjusting prediction sets for sensitive groups. 3. Demonstrated effectiveness on both synthetic and real-world datasets, outperforming traditional methods in terms of both fairness and prediction informativeness.

Weaknesses

1. Limitation on Sensitive Attribute Selection: The current method may not always identify the most relevant sensitive attribute, especially with limited sample sizes or overlapping biases. The ‘Automatic Attribute Selection’ section is somewhat challenging to follow. For instance, in Equation 6, it seems that only the argmax element is included in the set, and the algorithm does not seem to provide a sensitive attribute with formal guarantees. Since much of the paper’s contribution hinges on this algorithm, the lack of clarity in its description makes it hard to be convinced of its effectiveness. 2. Sample Size Sensitivity: AFCP’s performance can be constrained by the sample size. Smaller sample sizes may result in less reliable attribute selection and less informative prediction sets. In practical datasets, sample sizes tend to be small when many features are selected. The Sensitive Attribute Selection algorithm may lead to a large label set, resulting in too few samples to accurately determine the thresholds. 3. Computational Complexity: With a large label set, such as in ImageNet which has 1000 labels, this method involves complex procedures for attribute selection and prediction set construction. This complexity may make the method computationally intensive.

Questions

1. Coverage for Occupation 1 in Figure 5: The coverage for Occupation 1 in Figure 5 shows a significant increase in the Marginal method when the sample size increases from 2000 to 5000. This rapid increase is puzzling, particularly since the average size of the prediction set also decreases in this interval. Could you clarify why this behavior occurs? It seems counterintuitive, as one would generally expect a consistent relationship between coverage and prediction set size. 2. Impact of Calibration Set Size on Sensitive Attribute Selection and Final Prediction Set: How do you think the calibration set size influences the algorithm for Sensitive Attribute Selection and the final prediction set? Specifically:

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Please refer to the weakness.

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.

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. 2. The paper provides a strong theoretical basis for AFCP, clearly defining adaptive equalized coverage and offering proofs to support the validity of the method. 3. 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. 4. 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. 2. The method's reliance on leave-one-out procedures for attribute selection could be computationally intensive and potentially unstable with small sample sizes. More discussion on the stability and robustness of the attribute selection process, along with empirical evidence, would be beneficial. 3. The literature review, while covering relevant works, could be more exhaustive. Incorporating additional recent studies on robust conformal inference and handling distributional shifts would provide a broader context and highlight the novelty of the proposed approach.

Questions

What is the computational complexity of the proposed method, and how does it scale with large datasets? Are there any optimization strategies to improve efficiency? How stable is the attribute selection process across different sample sizes and datasets? Can the method handle cases where multiple sensitive attributes need to be considered simultaneously? Can the method be tested on more diverse and larger real-world datasets to validate its scalability and generalizability? How does the method perform in scenarios with highly imbalanced datasets? Have other attribute selection procedures been considered, and how do they compare with the proposed leave-one-out approach?

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

yes

Summary

The paper focuses on the problem of conformal inference with equalized coverage introduced in [1]. The authors propose a new method, Adaptively Fair Conformal Prediction (AFCP) that (i) adaptively selects a sensitive attribute corresponding to the group most negatively affected by algorithmic bias as evaluated by the miscoverage rate, and (ii) constructs a prediction set that satisfies equalized coverage over groups defined by the selected attribute. The authors perform experiments on synthetic and real data that demonstrate the performance of AFCP relative to methods that guarantee marginal coverage and exhaustive equalized coverage i.e., ​​valid coverage conditional on all sensitive attributes. [1] Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2020.

Strengths

1. The problem of conformal inference with equalized coverage is an important problem and of interest to the community. 2. The trade-off between efficiency and equalized coverage addressed in the paper is challenging and of practical significance. 3. Empirical evaluation demonstrates the performance improvement of AFCP over baselines.

Weaknesses

1. The clarity of the paper can be greatly improved. Detailed comments: - p2 l37: "A limitation of the current method for conformal inference with equalized coverage...." -- what is the current method? - p2 l41: what do you mean by efficiency and informativeness here? Is it set size? Please make it clear and precise. - Section 1.1: Overall, it is hard to understand the motivation from this section. It would be helpful to rewrite this a bit e.g. l32-36: it is not clear how this conveys the rationale for conformal inference with equalized coverage different from rationale for conformal inference more generally. - The notations are incorrect in some places and unnecessarily complex - p2 l71-72: $\phi$ is defined as mapping to $\mathbb{N}$ whereas the next line says it results in vector of length $|A|$. I believe it should be defined more generally - p2 l77-84: The notion of equalized coverage in [17] is defined as: $\mathbb{P}(Y_{n+1} \in C(X_{n+1}, A_{n+1}) | A_{n+1} = a) \geq 1 - \alpha$. It is not clear how this is extended to multiple (possibly overlapping) groups defined by $K$ sensitive attributes using $\phi$ - It is not clear at some places whether $A$ refers to single attribute or set - Alg 2 l4-5: in line 4, $A$ refers to single attribute, in line 5 it refers to multiple (set of) attributes - p6 l197: (7) returns a final selected attribute while the sentence refers to subset of attributes - p6 l204: minor comment, this does not hyperlink to A1 - typos in table captions (Table A25 onwards) 2. Insufficient empirical evaluation: While the paper includes detailed analysis on the two selected datasets, both these setups are fairly synthetic. Also, the Nursery data seems to be from 1997; the paper lacks evaluation on any recent and common benchmark datasets in literature. The paper also seems to lack experiments that demonstrate coverage and efficiency performance in the presence of multiple sensitive attributes. 3. The AFCP1 variation of AFCP seems to outperform AFCP in all cases -- when the sample size is small, we still see undercoverage for the Blue group using AFCP (Fig 3) and AFCP1 is more robust by selecting at least one attribute. While the paper mentions this, what would be the advantage of using AFCP? Is there any procedure to select variations for different data regimes?

Questions

1. The main text discusses the AFCP algorithm where at most one sensitive attribute may be selected. If we want equalized coverage over multiple attributes, won’t using AFCP result in similar challenges as exhaustive equalized coverage? 2. How does the size of the restricted calibration sample affect the performance of the algorithm?

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

3

Limitations

The authors discuss the limitations in the Discussion section.

Author-Reviewer Discussion Phase

Dear Authors and Reviewers! Thank you for your reviews, rebuttal, additional comments, questions and responses! We have the last two days of the discussion phase! Please use this time as efficiently as possible :) Thank you, NeurIPS 2024 Area Chair