🤖 machine learning

Fair Conformal Classification via Learning Representation-Based Groups

This paper proposes a fair conformal classification framework that guarantees conditional coverage on adaptively identified subgroups through nonlinear feature combinations, effectively addressing algorithmic biases to produce trustworthy and informative prediction sets.

Original authors: Senrong Xu, Yanke Zhou, Yuhao Tan, Zenan Li, Yuan Yao, Taolue Chen, Feng Xu, Xiaoxing Ma

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Senrong Xu, Yanke Zhou, Yuhao Tan, Zenan Li, Yuan Yao, Taolue Chen, Feng Xu, Xiaoxing Ma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart AI doctor. It's great at diagnosing patients on average, but if you look closely, it sometimes makes confident, wrong guesses for specific types of people—like young women from a certain region or older men with a specific job history. This is "algorithmic bias."

Now, imagine you want to add a safety net to this doctor. You want the AI to say, "I'm not 100% sure, so here is a list of possible diagnoses," rather than just picking one. This is called Conformal Prediction. It's like a weather forecast that says, "There's a 90% chance of rain," guaranteeing that if you check 100 days, it will actually rain on 90 of them.

The Problem:
The standard safety net works well for the "average" person. But if the AI is biased, the safety net might fail for those specific groups it doesn't understand well. It might say, "I'm 90% sure it's rain," but for the biased group, it's actually only 50% sure. The paper calls this a failure of fairness.

The Old Solution (and why it's clunky):
Previous methods tried to fix this by checking every possible combination of traits (e.g., "Is it a Black woman?" "Is it a Black man?" "Is it a White woman?").

The Analogy: Imagine trying to find a specific needle in a haystack by checking every single straw one by one.
The Flaw: There are too many combinations. Also, some biases are tricky. Maybe the AI only fails on "White Women OR Black Men" (a weird mix). Old methods, which look at traits one by one, can't easily spot this complex pattern. They are like a flashlight that only shines in a straight line; they miss the shadows in the corners.

The New Solution: FAREG (Fair Conformal Prediction for Representation-based Groups)
The authors propose a new method called FAREG. Here is how it works, using simple metaphors:

1. The "Translator" (The Encoder-Decoder)

Instead of looking at the raw data (like "Age: 25, Gender: Female"), FAREG uses a Translator.

The Metaphor: Imagine the AI is trying to understand a foreign language. The raw data is the foreign text. The Translator (a neural network) converts this text into a "secret code" (a latent representation) that captures the essence of the person, including complex relationships between traits that a human might miss.
Why it helps: This secret code can easily spot that "White Women" and "Black Men" share a hidden similarity that causes the AI to stumble, even though they look very different on the surface. It's like realizing that two people from different countries both speak a rare dialect, making them a specific group to watch out for.

2. The "Fairness Detective"

Once the data is translated into this secret code, FAREG acts as a detective.

The Metaphor: The detective looks at the secret code to find the "trouble spots." It asks: "Which groups of people are getting the worst safety nets?"
The Action: It doesn't just guess; it learns. It finds the specific groups where the AI is unfair and creates a special, larger safety net just for them. If the AI is shaky for a specific group, the system says, "Okay, for this group, we will give a bigger list of possibilities to be safe."

3. The "Safety Net Builder"

Finally, the system builds the prediction set.

The Metaphor: It's like a tailor making a custom suit. For the general population, it makes a standard suit (a small list of predictions). But for the groups the detective found to be "unfairly treated," it sews in extra fabric (a larger list of predictions) to ensure they are covered just as well as everyone else.
The Result: Everyone gets a 90% guarantee of being correct. The "average" person gets a small, efficient list. The "unfairly treated" group gets a slightly larger list, but they are no longer left behind.

4. The "New Ruler" (WSC+)

The paper also introduces a new way to measure fairness, called WSC+.

The Metaphor: Old rulers were straight sticks. They could only measure simple, straight-line biases. The new ruler (WSC+) is flexible and bendy. It can measure complex, curved, or twisted biases (like the "White Women OR Black Men" example).
Why it matters: It proves that the new method is actually finding the hidden unfairness that the old straight rulers missed.

Summary of Results

The authors tested this on fake data (simulating mental health diagnoses) and real-world data (like nursery school applications).

The Outcome: FAREG successfully found the hidden, complex groups that were being treated unfairly.
The Trade-off: It managed to fix the fairness without making the prediction lists so huge that they become useless. It kept the lists "compact" (informative) while ensuring everyone got a fair shot at being correct.

In a nutshell:
FAREG is a smart system that translates complex human data into a secret code to find hidden groups of people who are being treated unfairly by AI. It then customizes the AI's safety net for those specific groups, ensuring that the AI is reliable for everyone, not just the average person.

Technical Summary: Fair Conformal Classification via Learning Representation-Based Groups

1. Problem Statement

Conformal Prediction (CP) provides statistically rigorous marginal coverage guarantees for machine learning models, ensuring that the true label falls within a predicted set with a user-specified probability (e.g., $1-\alpha$ ). However, standard CP methods only guarantee coverage on average across the entire population. This marginal guarantee fails to account for algorithmic biases, where specific subgroups (defined by sensitive features like race or gender) may suffer disproportionately poor coverage.

While "equalized coverage" methods attempt to ensure valid coverage across predefined groups, they face significant limitations:

Expressiveness: Existing methods (e.g., Romano et al., 2020a) typically define groups based on single features. They struggle to capture complex, non-linear interactions between features (e.g., the subgroup defined by "White Female OR Black Male" in an Exclusive OR relationship).
Scalability and Efficiency: Exhaustively searching for all plausible subgroups is computationally infeasible. Previous adaptive approaches (e.g., Zhou & Sesia, 2024) rely on greedy selection of discrete features or Naïve Bayes assumptions, which limits their ability to handle continuous features and non-linear group definitions.

The core challenge is to develop a conformal inference framework that adaptively identifies unfairly treated subgroups defined by complex, non-linear feature combinations while maintaining computational efficiency and producing compact, informative prediction sets.

2. Methodology: FAREG

The authors propose FAREG (Fair Conformal Prediction for Representation-based Groups), a learning-based framework that adaptively identifies bias-affected groups and adjusts prediction sets to achieve adaptive equalized coverage.

2.1 Learning Representation-Based Groups

Instead of extracting groups directly from raw input features $X$ , FAREG encodes $X$ into a latent representation $Z$ via a mapping $Z = f(X)$ . The method employs a Deep Variational Information Bottleneck (Deep VIB) architecture to learn a group membership indicator $S$ (where $S=1$ indicates membership in an unfairly treated group $\hat{G}$ ) based on $Z$ .

The optimization objective maximizes the mutual information between the latent representation $Z$ and both the group membership $S$ and the input $X$ , while minimizing the mutual information between $Z$ and individual sample identities $i$ to ensure privacy and generalization. The loss function is formulated as:
$\mathcal{L} = \mathcal{L}_{CC} + \mathcal{L}_{MSE} - \beta \mathcal{L}_{KL}$
Where:

$\mathcal{L}_{CC}$ : Empirical conditional coverage loss, minimized to identify groups with poor coverage.
$\mathcal{L}_{MSE}$ : Reconstruction loss (Mean Squared Error) ensuring $Z$ retains sufficient information to reconstruct $X$ , thereby maintaining interpretability.
$\mathcal{L}_{KL}$ : Kullback-Leibler divergence term compressing $Z$ to a standard normal distribution.

The group selection is constrained by a minimum group size proportion $\delta$ . The authors utilize Projected Gradient Descent (PGD) to optimize the decoder parameters, projecting the predicted group membership probabilities back onto the feasible set to satisfy the size constraint.

2.2 Constructing Adaptive Prediction Sets

Once the unfair groups are identified, FAREG constructs the final prediction set $C(X_{N+1})$ for a test instance:

A standard conformal prediction set $C_m(X_{N+1}, D)$ is constructed using the full calibration set.
The model samples $T$ vectors $s_t$ from the learned joint Bernoulli distribution, each defining a specific group $\hat{G}_{s_t}$ .
Separate conformal sets are constructed for each sampled group.
The final prediction set is the union of the standard set and all group-specific sets:
$C(X_{N+1}) = C_m(X_{N+1}, D) \cup \bigcup_{t=1}^{T} C_m(X_{N+1}, \hat{G}_{s_t})$

2.3 Enhanced Evaluation Metric: WSC+

To evaluate the effectiveness of identifying non-linear unfair groups, the authors introduce WSC+, a non-linear extension of the Weighted Slab Coverage (WSC) metric. While traditional WSC evaluates coverage over linear slabs ( $a \leq v^T X \leq b$ ), WSC+ evaluates coverage over arbitrary non-linear functions $\pi(X)$ (specifically quadratic functions in the experiments). This allows for a more precise assessment of whether the conformal procedure covers groups defined by complex feature interactions.

3. Key Contributions

FAREG Framework: A novel conformal prediction method that uses an encoder-decoder architecture to adaptively identify subgroups with poor coverage defined by non-linear feature combinations, overcoming the limitations of linear or single-feature group definitions.
WSC+ Metric: A new non-linear conditional coverage metric designed to better capture and evaluate the performance of conformal procedures on complex, unfairly treated subgroups.
Theoretical Guarantees: The paper proves that FAREG achieves adaptive equalized coverage (Eq. 1) over the selected group set, provided the data is exchangeable. Theoretical analysis via VC-dimension suggests FAREG's candidate group space is a superset of that of previous adaptive methods (like AFCP), offering stronger expressiveness.
Efficiency: The method maintains time complexity comparable to standard conformal prediction ( $O(N+M)$ ), significantly outperforming the $O(N \log N + NM)$ complexity of the state-of-the-art AFCP method.

4. Experimental Results

The authors evaluated FAREG on both synthetic and real-world datasets (Nursery, ACSIncome).

Synthetic Data (Mental Illness Diagnosis Scenario):
- Coverage: FAREG was the only method to consistently achieve valid conditional coverage (≥0.9) on the target subgroup defined by an Exclusive NOR (XNOR) relationship between features, whereas baselines (Marginal, Partial, AFCP1, AFCP2) failed to maintain this coverage or required significantly larger sample sizes.
- Efficiency: FAREG maintained competitive average prediction set sizes, avoiding the excessive set sizes observed in AFCP2 when it attempted to cover the target group.
- Feature Selection: FAREG successfully identified the relevant non-linear feature combinations (X[0] and X[1]) with higher frequency than baselines as sample size increased.
- Runtime: FAREG demonstrated significantly lower time costs compared to AFCP, with training time scaling linearly with sample size.
Real-World Data (Nursery and ACSIncome):
- On the Nursery dataset, FAREG consistently outperformed all baselines in Group Coverage and WSC+ metrics while maintaining valid marginal coverage.
- On the ACSIncome dataset, FAREG achieved valid conditional coverage (0.9) and competitive efficiency compared to AFCP2.
Metric Validation: Experiments confirmed that WSC+ identifies groups with worse coverage than the linear WSC metric, validating its utility in detecting non-linear biases.

5. Significance and Claims

The paper claims that FAREG provides a practical pathway toward trustworthy machine learning by balancing the trade-off between the efficiency of conformal prediction (small set sizes) and the demands of algorithmic fairness (equalized coverage).

Expressiveness: By learning latent representations, FAREG captures complex algorithmic biases that linear methods or single-feature approaches miss.
Interpretability: Despite using latent representations, the encoder-decoder structure allows for the reconstruction of input features, mitigating the "black box" concern and demonstrating that the learned groups reflect meaningful feature interactions (e.g., XNOR relationships).
Robustness: The framework offers a flexible approach that can be adapted to different fairness notions without requiring pre-defined group structures.

The authors acknowledge a limitation: the enhanced expressivity of representation-based groups may partially sacrifice the direct interpretability of groups defined on manifest features, though they argue the reconstruction capability compensates for this. The work positions itself as an advancement over existing adaptive fair conformal methods by addressing the expressiveness gap in group identification.