FedCF: Fair Federated Conformal Prediction

## Abstract

Abstract Conformal Prediction (CP) is a widely used technique for quantifying uncertainty in machine learning models. In its standard form, CP offers probabilistic guarantees on the coverage of the true label, but it is agnostic to sensitive attributes in the dataset. Several recent works have sought to incorporate fairness into CP by ensuring conditional coverage guarantees across different subgroups. One such method is Conformal Fairness (CF). In this work, we extend the CF framework to the Federated Learning setting and discuss how we can audit a federated model for fairness by analyzing the fairness-related gaps for different demographic groups. We empirically validate our framework by conducting experiments on several datasets spanning multiple domains, fully leveraging the exchangeability assumption. {NoHyper} † † ∗ Equal Contribution, † \dagger This work was done while the author was a student at The Ohio State University.

## 1 Introduction

Ensuring model fairness is a critical thrust of trustworthy machine learning (ML). ML models, when not calibrated for fairness, are prone to developing biases at each stage of an ML pipeline, as reflected by their predictions Mehrabi et al. (2021). We define bias as disparate performance (i.e., accuracy for classification) between different sub-populations. In the data collection phase, measurement bias may occur due to disproportionate data collection on sub-populations, while representation bias manifests from a lack of training data on specific strata. During training, these biases are inductively learned by the model–leading to incorrect predictions in safety-critical tasks. These models are also susceptible to algorithmic bias, resulting from regularization and optimization techniques during model training, which incorrectly generalize for marginalized groups. To mitigate these risks, many ML models must adhere to regulations placed by local governing bodies (Hirsch et al., 2023). Towards model compliance, Komala et al. (2024); Agrawal et al. (2024); Jones et al. (2025) have proposed approaches to enhance model fairness in varying tasks, including federated graph learning and representation learning.

Developing robust ML frameworks with mathematically rigorous guarantees is also essential for building actionable, trustworthy ML models for safety-critical tasks. In this frontier, researchers have increasingly explored Conformal Prediction (CP)–an uncertainty quantification (UQ) technique that only assumes statistical exchangeability–to develop trustworthy ML models (Vovk et al., 2005). Unlike traditional point-wise prediction in ML, CP guarantees that the correct outcome will be in a prediction set with a user-specified property. Practitioners have adopted CP due to its model-free assumption and post-hoc application (Cherian & Bronner, 2020). Additionally, users can apply CP to structured data (such as graphs), which cannot be used with traditional IID-based methods (Maneriker et al., 2025). However, vanilla CP is not calibrated for fairness and can be inherently unfair Cresswell et al. (2025).

Several approaches have been proposed at the intersection of fairness and CP–each catering to different tasks and notions of fairness. Romano et al. (2020a) developed a CP approach for the regression setting to ensure equalized coverage across protected groups. Lu et al. (2022) considers equalized coverage in a classification task for medical imaging.
Zhou & Sesia (2024) extends Romano et al. (2020a) and provides an algorithm adaptive to sensitive groups to increase the predictive power of the CP sets when several sensitive attributes are present, and focuses on the classification task.
Lastly, Vadlamani et al. (2025) provides a framework to ensure fair coverage of positive outcomes, without requiring protected attributes at inference time, unlike prior work.
Orthogonally, CP has been used to enhance the fairness of other tasks. To mitigate bias in LLM-based recommender systems, Fayyazi et al. (2025) explores iteratively using fairness-aware CP.

While there are several approaches to integrating fairness into CP, these methods are not considered when the training data is decentralized (i.e., available only to clients) and the ML model is stored on a centralized server. Extending these CP methods to the federated learning (FL) setting is essential because tasks that benefit from fair uncertainty quantification (such as those in healthcare and finance) also often have privacy considerations, making it infeasible to keep data on a centralized server. Thus, we extend the work of Vadlamani et al. (2025) using recent literature in Federated CP (Lu et al., 2023).

Key Contributions: We extend the Conformal Fairness (CF) framework (Vadlamani et al., 2025) to the FL setting while maintaining the theoretical fairness guarantees provided by CF.

We first discuss how to bound conditional coverage according to a user-specified fairness notion when data is decentralized. To facilitate this, we provide a sufficient set of terms that a client can compute using local data, how the server should aggregate these terms to bound the conditional coverage, and theoretically prove the validity of our approach.

Next, we consider the client-server communication overhead and its tradeoff with preserving data privacy. Specifically, we propose two term-aggregation approaches, with one having less communication overhead and the other being more privacy-preserving of client data. We also revise the original CF algorithm to reduce the number of communication rounds required to construct a fair conformal predictor.

Lastly, we evaluate FedCF on several datasets, including tabular, graph, and image datasets, and for multiple popular fairness metrics, and observe that FedCF can control for a particular coverage gap level while maintaining the original CP coverage guarantee.

## 2 Background

### 2.1 Conformal Prediction

Conformal Prediction (CP) (Vovk et al., 2005) is a widely used framework for quantifying predictive uncertainty in ML. CP provides rigorous statistical guarantees without imposing assumptions on the model, requiring only that the data are exchangeable–a broader condition than IID and compatible with non-IID or structured settings (e.g., graphs).

We focus on split (inductive) CP in the classification setting. Let $\bm{x}_{i}\in{\mathcal{X}}={\mathbb{R}}^{d}$ and $y_{i}\in{\mathcal{Y}}=\{0,\dots,C-1\}$ denote features and labels. Given a calibration dataset, $\mathcal{D}_{\mathrm{calib}}=\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}$, our goal is to construct a set-valued predictor ${\mathcal{C}}$ such that, for an exchangeable test point $(\bm{x}_{\text{test}},y_{\text{test}})$,

$$ $\textstyle 1-\alpha\leq\Pr[y_{\text{test}}\in{\mathcal{C}}({\bm{x}}_{\text{test}})]\leq 1-\alpha+\frac{1}{\lvert\mathcal{D}_{\mathrm{calib}}\rvert},$ (1) $$

where $1-\alpha\in(0,1)$ is the target coverage level. We refer to Equation [1](https://arxiv.org/html/2509.22907v1#S2.E1) as the coverage guarantee. Concretely, given a non-conformity score $s:{\mathcal{X}}\times{\mathcal{Y}}\to{\mathbb{R}}$, define the conformal quantile as

$$ $\textstyle\hat{q}(\alpha)=\text{Quantile}(\frac{\lceil(n+1)(1-\alpha)\rceil}{n};\{s(\bm{x}_{i},y_{i})\}_{i=1}^{n}).$ $$

The resulting prediction set ${\mathcal{C}}_{\hat{q}(\alpha)}(\bm{x}_{\text{test}})=\{y\in{\mathcal{Y}}:s(\bm{x}_{\text{test}},y)\leq\hat{q}(\alpha)\,\}$ satisfies the guarantee in [1](https://arxiv.org/html/2509.22907v1#S2.E1).

Evaluating CP: Two standard metrics are used: (1) Coverage, the estimated test-time probability, $\Pr[y_{\text{test}}\in{\mathcal{C}}_{\hat{q}(\alpha)}(\bm{x}_{\text{test}})]$; and (2) Efficiency, the average prediction set size, $\lvert{\mathcal{C}}_{\hat{q}(\alpha)}(\bm{x}_{\text{test}})\rvert$. These are typically in tension as achieving a higher desired coverage often necessitates larger sets.

### 2.2 Federated Learning

A key contributor to developing strong deep learning models is providing a large amount of quality training data (Kaplan et al., 2020). However, in certain domains, such as healthcare and finance, collecting large amounts of data may be prohibitive due to privacy concerns. Federated learning (FL) is a framework for collaborative learning that keeps training data decentralized and private. Given $K$ clients that will participate in training, each client has its own training data that it wants to keep private. The goal is to optimize a global loss function, $L$, that is the weighted average of local risk functions, $\ell_{k}$. Formally, FL finds weights $\theta^{*}$ s.t.
$\theta^{*}=\text{argmin}_{\theta}\{L(\theta)=\sum_{k=1}^{K}w_{k}\cdot\mathbb{E}_{(x^{(k)},y^{(k)})\sim P_{k}}[\ell_{k}(\theta;x^{(k)},y^{(k)})]\},$
where $P_{k}$ is client $k$’s local distribution and ${\bm{w}}\in\Delta^{k}$ are weights (Lu et al., 2023).

### 2.3 Federated Conformal Prediction (FCP)

Setting:
In FL, the development and calibration datasets are partitioned over
$K$ clients. Meaning, each client $k\in\{1,\dots,K\}={\mathcal{K}}$ retains a private calibration set
$\mathcal{D}_{\mathrm{calib}}^{(k)}=\{({\bm{x}}^{(k)}_{i},y^{(k)}_{i})\}_{i=1}^{n_{k}}$ drawn from an unknown local
distribution $P_{k}$. The goal is to still construct a prediction set function ${\mathcal{C}}$ such that for any test point $({\bm{x}}_{\text{test}},y_{\text{test}})\sim Q_{\text{test}}$, where $Q_{\mathrm{test}}=\sum_{k=1}^{K}\gamma_{k}P_{k}$ is the mixutre distribution with weights
$\gamma_{k}\propto(n_{k}+1)$ (Lu et al., 2023), Equation [1](https://arxiv.org/html/2509.22907v1#S2.E1) is satisfied. This is done while respecting the communication and privacy constraints of FL.

Partial exchangeability and the FCP algorithm.
Lu et al. (2023) introduce *partial exchangeability*: within each client, the multiset
$\{s({\bm{x}}^{(k)}_{1},y^{(k)}_{1}),\dots,s({\bm{x}}^{(k)}_{n_{k}},y^{(k)}_{n_{k}}),s({\bm{x}}_{\mathrm{test}},y_{\mathrm{test}})\}$
is exchangeable with probability $\gamma_{k}$.
Under this assumption, the FCP method aggregates all non-conformity scores, orders them, and
selects the $(1-\alpha)(N+K)$-th statistic as follows

$$ $\hat{q}(\alpha)=\text{Quantile}(\frac{\lceil(N+K)(1-\alpha)\rceil}{N};\{({\bm{x}}^{(k)}_{i},y^{(k)}_{i})\}_{k,i})$ $$

where $N=\sum_{k=1}^{K}n_{k}$. The prediction set $C_{\alpha}({\bm{x}})=\{y:S({\bm{x}},y)\leq\hat{q}_{\alpha}\}$ then
satisfies

$$ $\textstyle 1-\alpha\;\leq\;\Pr[y_{\mathrm{test}}\in C_{\alpha}({\bm{x}}_{\mathrm{test}})]\;\leq\;1-\alpha+\frac{K}{N+K}.$ (2) $$

Communication-efficient quantile sketches.
To preserve privacy, instead of transmitting all $N$ scores to the server, each client can send a mergeable sketch (e.g., using T-Digest (Dunning, 2021) or DDSketch (Masson et al., 2019)). Doing so will loosen the guarantee given in Equation [2](https://arxiv.org/html/2509.22907v1#S2.E2).

### 2.4 Conformal Fairness

While CP provides marginal coverage guarantees, it is agnostic to sensitive attributes within the data. So different groups can receive systematically different coverages. The *Conformal Fairness (CF)* framework (Vadlamani et al., 2025) formalizes the notion of fairness for prediction sets by considering the disparity in *conditional* coverage between sensitive groups, all while retaining the validity based on the CP exchangeability. At a high level, CF adapts group-fairness notions (e.g., Demographic Parity and Equal Opportunity) to the set-valued outputs of CP and then tunes a score threshold to satisfy a user-specified “closeness” criterion ,
$c$, on inter-group disparities. Using the exchangeability assumption, CF can be applied to non-IID/structured data.

From point predictions to set-based fairness.
Let ${\mathcal{C}}_{\lambda}({\bm{x}})=\{y\in{\mathcal{Y}}:\,s({\bm{x}},y)\leq\lambda\}$ denote the CP prediction set at score threshold $\lambda$.
CF adapts classical group-fairness metrics by replacing point-prediction events (i.e., $\tilde{y}=\hat{Y}$) with set-membership events (i.e., $\tilde{y}\in{\mathcal{C}}_{\lambda}(X)$) and evaluating disparities across groups $\mathcal{G}$ and, when appropriate, advantaged labels ${\mathcal{Y}}^{+}$. For example, a set-based Demographic Parity-style constraint can be written as,

$$ $\textstyle\left|\Pr\!\big[\tilde{y}\in{\mathcal{C}}_{\lambda}(X)\mid X\in g_{a}\big]-\Pr\!\big[\tilde{y}\in{\mathcal{C}}_{\lambda}(X)\mid X\in g_{b}\big]\right|\;\leq\;c\quad\forall\,g_{a},g_{b}\in\mathcal{G},\ \tilde{y}\in{\mathcal{Y}}^{+},$ $$

with analogous set-based forms for other common group-fairness metrics.

Conditional coverage as the fairness control knob.
To evaluate a chosen fairness notion, CF filters the calibration data to the relevant subpopulation (e.g., a group or a group-and-label slice) via a filter function, $F_{m}$, and uses conditional coverage estimates under that filter. It then searches a threshold space $\Lambda$ to identify $\lambda_{\mathrm{opt}}$ that satisfies the closeness criterion across groups (and labels, if required) while maintaining CP validity. A key technical ingredient is that CP coverage holds when labels are fixed to a particular $\tilde{y}$, which underpins group- and class-conditional control in CF.

Guarantees and trade-offs.
CF provides a theoretically grounded procedure to bound fairness disparities (as defined above) without sacrificing CP’s finite-sample coverage guarantees, which is empirically backed by CF reducing fairness violations across several metrics and remains effective with multiple sensitive attributes (intersectional groups). In practice, satisfying stricter fairness closeness $c$ increases the average prediction set size, reflecting the fairness–efficiency trade-off.

Practical advantages.
Unlike many conditional-CP baselines that require group membership at inference time or are model-specific, CF’s set-based metrics and thresholding procedure do not require protected attributes at test time and apply across different non-conformity scores and data modalities, making it compatible with downstream deployment constraints.

## 3 FedCF Theory and Methodology

In this section, we begin by establishing the theoretical and methodological foundations. We first redefine the concept of the coverage gap ([3.1](https://arxiv.org/html/2509.22907v1#S3.SS1)) and introduce a descent-based reformulation of the CF Framework ([3.2](https://arxiv.org/html/2509.22907v1#S3.SS2)), both within the federated setting. Following this, we present the Federated Conformal Fairness (FedCF) Framework.

### 3.1 FedCF: Extending Coverage Gap to the Federated Setting

Let $F_{M}$ be a filter function for some fairness metric. Then, we define the fairness-specific coverage level for positive label $\tilde{y}\in{\mathcal{Y}}^{+}$ in group $g\in{\mathcal{G}}$ as
$\Pr[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda\mid F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]$.
In the federated setting, since the data is decentralized, we cannot directly estimate this quantity. To address this, we rewrite the quantity–using notation in Table [1](https://arxiv.org/html/2509.22907v1#S3.T1)–as,

$$ $\displaystyle\textstyle\Pr$ $\displaystyle[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda\mid F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]=\sum\limits_{k=1}^{K}\Big(\underbrace{\Pr[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda\mid F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,E_{k}]}_{\text{ \hbox to8.75pt{\vbox to8.75pt{\pgfpicture\makeatletter\hbox{\enskip\lower-4.37431pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.17432pt}{0.0pt}\pgfsys@curveto{4.17432pt}{2.30544pt}{2.30544pt}{4.17432pt}{0.0pt}{4.17432pt}\pgfsys@curveto{-2.30544pt}{4.17432pt}{-4.17432pt}{2.30544pt}{-4.17432pt}{0.0pt}\pgfsys@curveto{-4.17432pt}{-2.30544pt}{-2.30544pt}{-4.17432pt}{0.0pt}{-4.17432pt}\pgfsys@curveto{2.30544pt}{-4.17432pt}{4.17432pt}{-2.30544pt}{4.17432pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.44446pt}{-2.39166pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{I}} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} } \pgfsys@invoke{ }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}}}}$ $\displaystyle\textstyle\qquad\cdot\underbrace{\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1\mid E_{k}]}_{\text{ \hbox to10.89pt{\vbox to10.89pt{\pgfpicture\makeatletter\hbox{\quad\lower-5.44658pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.24658pt}{0.0pt}\pgfsys@curveto{5.24658pt}{2.89764pt}{2.89764pt}{5.24658pt}{0.0pt}{5.24658pt}\pgfsys@curveto{-2.89764pt}{5.24658pt}{-5.24658pt}{2.89764pt}{-5.24658pt}{0.0pt}\pgfsys@curveto{-5.24658pt}{-2.89764pt}{-2.89764pt}{-5.24658pt}{0.0pt}{-5.24658pt}\pgfsys@curveto{2.89764pt}{-5.24658pt}{5.24658pt}{-2.89764pt}{5.24658pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.99655pt}{-2.39166pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{II}} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} } \pgfsys@invoke{ }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}}}}\cdot\underbrace{\Pr[E_{k}]}_{\text{ \hbox to13.37pt{\vbox to13.37pt{\pgfpicture\makeatletter\hbox{\quad\lower-6.68608pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.48608pt}{0.0pt}\pgfsys@curveto{6.48608pt}{3.5822pt}{3.5822pt}{6.48608pt}{0.0pt}{6.48608pt}\pgfsys@curveto{-3.5822pt}{6.48608pt}{-6.48608pt}{3.5822pt}{-6.48608pt}{0.0pt}\pgfsys@curveto{-6.48608pt}{-3.5822pt}{-3.5822pt}{-6.48608pt}{0.0pt}{-6.48608pt}\pgfsys@curveto{3.5822pt}{-6.48608pt}{6.48608pt}{-3.5822pt}{6.48608pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.54866pt}{-2.39166pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{III}} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} } \pgfsys@invoke{ }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}}}}\Big)\cdot\Big(\underbrace{\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]}_{\text{ \hbox to13.13pt{\vbox to13.13pt{\pgfpicture\makeatletter\hbox{\quad\lower-6.56548pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.36548pt}{0.0pt}\pgfsys@curveto{6.36548pt}{3.5156pt}{3.5156pt}{6.36548pt}{0.0pt}{6.36548pt}\pgfsys@curveto{-3.5156pt}{6.36548pt}{-6.36548pt}{3.5156pt}{-6.36548pt}{0.0pt}\pgfsys@curveto{-6.36548pt}{-3.5156pt}{-3.5156pt}{-6.36548pt}{0.0pt}{-6.36548pt}\pgfsys@curveto{3.5156pt}{-6.36548pt}{6.36548pt}{-3.5156pt}{6.36548pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.39586pt}{-2.39166pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{IV}} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} } \pgfsys@invoke{ }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}}}}\Big)^{-1}.$ (3) $$

**Table 1: Important notation used for coverage gap calculation.**
| Notation | Definition | Notation | Definition |
| --- | --- | --- | --- |
| $n_{k}$ | $\lvert\mathcal{D}_{\mathrm{calib}}^{(k)}\rvert$ | $\mathcal{D}_{\mathrm{calib}}^{(k)}$ | Client $k$’s calibration dataset. |
| $n_{k}^{(g,\tilde{y})}$ | $\lvert{\mathcal{S}}_{k}^{(g,\tilde{y})}\rvert$ | ${\mathcal{S}}_{k}^{(g,\tilde{y})}$ | $\{\textstyle({\bm{x}}_{i},y_{i})\in\mathcal{D}_{\mathrm{calib}}^{(k)}\mid F_{M}({\bm{x}}_{i},y_{i},g,\tilde{y})=1\}$ |
| $\gamma_{k}$ | $\Pr[E_{k}]$ | $E_{k}$ | The event $\bm{x}_{\text{test}}$ is exchangeable with $\mathcal{D}_{\mathrm{calib}}^{(k)}$. |
| $\pi^{(g,\tilde{y})}$ | Point estimate<br>for Term IV<br>in Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3). | $L^{(g,\tilde{y})},U^{(g,\tilde{y})}$ | Bounds for Term IV in Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3). |
|  | $\alpha_{k}^{(g,\tilde{y});\lambda}$ | $\sum\limits_{({\bm{x}}_{i},_)\in{\mathcal{S}}_{k}^{(g,\tilde{y})}}\bm{1}[s({\bm{x}}_{i},\tilde{y})\leq\lambda]$ |  |

With this reformulation, we can estimate different terms individually—either locally on each client or globally on the server. The following theorem presents two types of fairness-specific conditional coverage estimates: (1) interval bounds and (2) point estimates. The estimates for the individual terms are provided in Lemmas [B.1](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem1), [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2), and [B.3](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem3) in Appendix [B](https://arxiv.org/html/2509.22907v1#A2). For clarity, Table [1](https://arxiv.org/html/2509.22907v1#S3.T1) summarizes the primary notation used in our main theorem. A full notations table can be found in Appendix [A](https://arxiv.org/html/2509.22907v1#A1).

###### Theorem 3.1 .

The fairness-specific coverage level (Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3)) can be bounded as

$$ $\textstyle L_{\text{cov}}(\lambda,F_{M},g,\tilde{y})\leq\Pr[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]\leq U_{\text{cov}}(\lambda,F_{M},g,\tilde{y}),$ $$

where

$$ $\displaystyle\textstyle L_{\text{cov}}(\lambda,F_{M},g,\tilde{y})=\sum\limits_{k=1}^{K}\frac{\gamma_{k}\alpha_{k}^{(g,\tilde{y});\lambda}n_{k}^{(g,\tilde{y})}}{(n_{k}^{(g,\tilde{y})}+1)(n_{k}+1)U^{(g,\tilde{y})}}\text{ and }U_{\text{cov}}(\lambda,F_{M},g,\tilde{y})=\sum\limits_{k=1}^{K}\frac{\gamma_{k}(\alpha_{k}^{(g,\tilde{y});\lambda}+1)}{(n_{k}+1)L^{(g,\tilde{y})}}.$ (4) $$

If the data is IID, using MLE estimates for each term, we get the following estimate for the fairness-specific coverage level

$$ $\Pi_{\text{cov}}=\Pr[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]=\sum\limits_{k=1}^{K}\frac{\gamma_{k}\alpha_{k}^{(g,\tilde{y});\lambda}}{n_{k}\pi^{(g,\tilde{y})}}.$ (5) $$

Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1) gives us bounds for the coverage level, which we can convert into bounds for the coverage gap between groups for fairness evaluation. The interval bounds provide finite sample guarantees that are typically seen in the CP literature, at the cost of being a more conservative estimate. Conversely, point estimates provide tight coverage estimates, but assume IID data, and may violate those guarantees.

###### Theorem 3.1 .

### 3.2 FedCF: Revisiting the Conformal Fairness Algorithm

Figure: Algorithm 1 Descent-Based CF Optimization

One drawback of the original Conformal Fairness algorithm is that it creates a sampled, discretized search space and iterates to find the minimal $\lambda$ satisfying the fairness specification. This process requires computing the coverage gap every iteration and for each positive label, which becomes even more inefficient in the federated setting, where coverage gap computation requires client-server communication.

Algorithm [1](https://arxiv.org/html/2509.22907v1#alg1) describes the core descent-based CF algorithm.
(^1^11We omit the iteration over the positive labels for brevity and present just the core optimization.)
The algorithm takes as input the calibration set for each client, $\big\{\mathcal{D}_{\mathrm{calib}}^{(k)}\big\}_{k\in{\mathcal{K}}}$, the set of (positive) labels, the set of sensitive groups, ${\mathcal{G}}$, a closeness criterion, $c$, and a filtering function, $F_{M}$. Additionally, we initialize a threshold, $\lambda_{0}$, as the $\hat{q}$ value given by the FCP algorithm (Lu et al., 2023), to ensure $1-\alpha$ coverage is still satisfied.

For a given threshold $\lambda_{t}$, we can compute the coverage gap $cg_{t}$ and evaluate whether it adheres to our fairness constraint. FedCF solves,
$\lambda_{opt}=\min_{\lambda\in\Lambda}\lambda,\text{ subject to }cg_{t}-c\leq 0.$
We solve this using a framework analogous to Gradient Descent (GD) with Momentum (Polyak, 1964). Let $\eta$ and $\mu$ be the initial learning rate and momentum constant, respectively. The update rule for $\lambda_{t}$ is,

$$ $\textstyle\lambda_{t+1}=\lambda_{t}+\eta_{t}\cdot b_{t+1}=\lambda_{t}+\eta\cdot(1/2)^{p_{t}}\cdot b_{t+1},$ $$

where $b_{t+1}=\mu\cdot b_{t}+(cg_{t}-c)$ is the modified step size, $p_{t}=\max\{\lceil\log_{2}(\frac{\eta}{\Delta\lambda})\rceil,0\}$ is the number of halves to make to update $\lambda_{t}$ by $\Delta\lambda=(\lambda_{opt}-\lambda_{t})\bm{1}_{[b_{t+1}\geq 0]}+(\lambda_{0}-\lambda_{t})\bm{1}_{[b_{t+1}<0]}$.

We do not stop immediately once a satisfactory $\lambda$ is found; instead, we continue exploring to check whether a smaller $\lambda$ exists. This algorithm directly applies to the federated setting, with one important consideration: the computation of the coverage gap in Line [4](https://arxiv.org/html/2509.22907v1#alg1.l4).

### 3.3 FedCF: the end-to-end Federated Conformal Fairness framework

Having established the sufficient terms to compute the fairness-specific coverage gap, we now present the FedCF framework. We discuss FedCF in the context of the interval-bounds estimates from Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1), noting the discussion also applies to the point-estimate case by setting $L_{\text{cov}}=U_{\text{cov}}=\Pi_{\text{cov}}$. The fairness-specific coverage gap is given by,

$$ $\displaystyle\textstyle\text{cg}(\lambda,F_{M},\tilde{y},\mathcal{G})$ $\displaystyle:=\max\limits_{g_{a}\in\mathcal{G}}\{U_{\text{cov}}(\lambda,F_{M},g_{a},\tilde{y})\}-\min\limits_{g_{b}\in\mathcal{G}}\{L_{\text{cov}}(\lambda,F_{M},g_{b},\tilde{y})\}$ (6) $\displaystyle=\max\limits_{g_{a},g_{b}\in\mathcal{G}}\{U_{\text{cov}}(\lambda,F_{M},g_{a},\tilde{y})-L_{\text{cov}}(\lambda,F_{M},g_{b},\tilde{y})\}.$ (7) $$

While equations [6](https://arxiv.org/html/2509.22907v1#S3.E6) and [7](https://arxiv.org/html/2509.22907v1#S3.E7) are mathematically equivalent, their formulations lead to two different communication and aggregation strategies demonstrating the tradeoff between communication overhead and privacy. We present the communication efficient protocol in the main paper and the enhanced privacy protocol in Appendix [D](https://arxiv.org/html/2509.22907v1#A4). In Appendix [D](https://arxiv.org/html/2509.22907v1#A4), we also present a hybrid protocol, where clients select whether to use the communication efficient or enhanced privacy protocol.
We include FedCF extensions concerning differential privacy in Appendix [F](https://arxiv.org/html/2509.22907v1#A6).

Note that $U_{\text{cov}}$ and $L_{\text{cov}}$ depend on $L^{(g,\tilde{y})}$ and $U^{(g,\tilde{y})}$, respectively. Since these quantities are also computed in a federated manner on the server, we compute them prior to computing the coverage gap for any particular $\lambda$(^2^22The algorithm for computing the prior is similar to that of the coverage gap, so we omit it here).
Given that these priors are available on the server, we can compute the fairness-specific coverage gap. From Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1), each client computes and sends two values for each $(g,\tilde{y})\in{\mathcal{G}}\times{\mathcal{Y}}^{+}$ pair: $\frac{\alpha_{k}^{(g,\tilde{y});\lambda}\cdot n_{k}^{(g,\tilde{y})}}{(n_{k}^{(g,\tilde{y})}+1)\cdot(n_{k}+1)}$ and $\frac{\alpha_{k}^{(g,\tilde{y});\lambda}+1}{n_{k}+1}$. Once the server receives these pairs from each client, it proceeds to aggregate these quantities to derive $L_{\text{cov}}$ and $U_{\text{cov}}$ for each $(g,\tilde{y})$. $U_{\text{cov}}$ is limited 1 to reconcile $\Pr[\,\cdot\,]\leq 1$ for any event. The final coverage gap is determined as per Equation [6](https://arxiv.org/html/2509.22907v1#S3.E6). Algorithms [2](https://arxiv.org/html/2509.22907v1#alg2) and [3](https://arxiv.org/html/2509.22907v1#alg3) describe the federated coverage gap algorithm.

##### Communication Complexity and Privacy Implications.

Each client is responsible for sending messages of size totaling ${\mathcal{O}}(2\cdot\lvert{\mathcal{G}}\rvert\lvert{\mathcal{Y}}^{+}\rvert)$ to the server per server round. While this is linear in terms of the number of $(g,\tilde{y})$ pairs, we note that with enough $\lambda$s, the server can learn the distribution of $\Pr[s(\bm{x}_{\text{test}},\tilde{y})\leq\lambda\mid F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,E_{k}]$.

Figure: Algorithm 2 Server-side Aggregation for Coverage Gap

## 4 Experiments

### 4.1 Setup.

##### Datasets.

We evaluate the FedCF framework on four multi-class datasets in different domains: (1, 2) ACSIncome and ACSEducation (Ding et al., 2021), (3) Pokec-{n, z} (Takac & Zabovsky, 2012), (4) Fitzpatrick Groh et al. (2021). These datasets were not originally for FL, so we partitioned them to form our clients. For the ACS datasets, we use state and territory data to partition the information into clients. We consider six different partitioning schemes, based on common regional definitions in the U.S., which result in 4 (small), 8 (large), and 51 (all) clients. We also consider equivalent schemes for just the continental U.S.. For Pokec-{n, z}, each graph is treated as a separate client, as they originate from distinct partitions of the larger Pokec social network. Finally, for Fitzpatrick, since there is no predetermined partitioning scheme, we use a Dirichlet partitioner (Yurochkin et al., 2019) with concentration parameter of $0.5$ to split $\mathcal{D}_{\mathrm{train}}/\mathcal{D}_{\mathrm{valid}}/\mathcal{D}_{\mathrm{calib}}$ for $K\in\{2,4,8\}$ clients. We use a $30\%/20\%/25\%/25\%$ stratified split for the full $\mathcal{D}_{\mathrm{train}}/\mathcal{D}_{\mathrm{valid}}/\mathcal{D}_{\mathrm{calib}}/\mathcal{D}_{\mathrm{test}}$.

##### Base Models.

For the ACS datasets, we use XGBoost (Chen & Guestrin, 2016). For Pokec-{n,z}, we use GraphSAGE (Hamilton et al., 2017) with GCN aggregation. For Fitzpatrick, we use ResNet-18 (He et al., 2016). Each of these models is trained using FedAvg (McMahan et al., 2017).

##### Baseline.

We construct a federated fairness-agnostic conformal predictor targeting a coverage level of $1-\alpha=0.9$ using FCP Lu et al. (2023) with T-Digest Dunning (2021). For the non-conformity score, we adopt APS (Romano et al., 2020b) and RAPS (Angelopoulos et al., 2022) for all datasets, as well as DAPS (H. Zargarbashi et al., 2023), a graph-specific method, for Pokec-{n,z}. We then assess fairness using $\lambda=\hat{q}(\alpha)$ for three popular group-fairness metrics, reformulated in Table [2](https://arxiv.org/html/2509.22907v1#S4.T2)–Demographic Parity, Equal Opportunity, and Predictive Equality.

**Table 2: Formulations for Conformal Fairness Metrics.**
| Metric | Definition |
| --- | --- |
| Demographic (or Statistical) Parity | $\lvert\Pr[\tilde{y}\in\mathcal{C}_{\lambda}(X)~\Big|~X\in g_{a}]-\Pr[\tilde{y}\in\mathcal{C}_{\lambda}(X)~\Big|~X\in g_{b}]\rvert<c,~\forall g_{a},g_{b}\in\mathcal{G},~\forall\tilde{y}\in\mathcal{Y}^{+}$ |
| Equal Opportunity | $\lvert\Pr[\tilde{y}\in\mathcal{C}_{\lambda}(X)~\Big|~Y=\tilde{y},X\in g_{a}]-\Pr[\tilde{y}\in\mathcal{C}_{\lambda}(X)~\Big|~Y=\tilde{y},X\in g_{b}]\rvert<c,~\forall g_{a},g_{b}\in\mathcal{G},~\forall\tilde{y}\in\mathcal{Y}^{+}$ |
| Predictive Equality | $\lvert\Pr[\tilde{y}\in\mathcal{C}_{\lambda}(X)~\Big|~Y\neq\tilde{y},X\in g_{a}]-\Pr[\tilde{y}\in\mathcal{C}_{\lambda}(X)~\Big|~Y\neq\tilde{y},X\in g_{b}]\rvert<c,~\forall g_{a},g_{b}\in\mathcal{G},~\forall\tilde{y}\in\mathcal{Y}^{+}$ |

##### Evaluation Metrics:

We report two key metrics: (1) efficiency, and (2) worst-case fairness disparity. The latter captures the largest difference in conditional coverage across groups, under the chosen fairness metric. For example, under Demographic Parity, we report:

$$ $\max_{\tilde{y}\in{\mathcal{Y}}^{+}}\max\limits_{g_{a},g_{b}\in\mathcal{G}}\lvert\Pr\!\big[\tilde{y}\in{\mathcal{C}}_{\lambda}({\bm{x}}_{test})\mid{\bm{x}}_{test}\in g_{a}\big]-\Pr\!\big[\tilde{y}\in{\mathcal{C}}_{\lambda}({\bm{x}}_{test})\mid{\bm{x}}_{test}\in g_{b}\big]\rvert.$ (8) $$

More details on the experimental setup can be found in Appendix [C](https://arxiv.org/html/2509.22907v1#A3).

### 4.2 Results

In each figure, we use a solid line to represent the average efficiency of the base federated conformal predictors across different thresholds and a dashed line to represent the corresponding average worst-case fairness disparity. The bar plot shows the efficiency and worst-case fairness disparity using FedCF, while the dots indicate the desired fairness disparity. We report the average base performance for clarity and readability. In all experiments, FedCF achieves an actual fairness disparity within the specified closeness criterion, $c$, which may not be the case with the base federated conformal predictor.

##### Preserves Key Characteristics of CF.

Two important characteristics of the CF framework are that it is (1) agnostic to the specific non-conformity score function and (2) supports intersectional fairness. We demonstrate that our FedCF framework preserves these two characteristics via the Pokec-{n, z} dataset. Pokec-{n, z} each have two sensitive attributes: region and gender. In addition to considering each attribute individually, we can treat each pair of attributes as distinct and apply FedCF. Furthermore, Pokec-{n, z} is a graph dataset. Recently, several developments have been made in graph CP research on non-conformity scores that utilize the graph structure. In addition to two standard CP methods–APS and RAPS–we also provide results using DAPS. Figure [1](https://arxiv.org/html/2509.22907v1#S4.F1) shows how the FedCF framework can achieve the desired fairness criterion with minimal cost to efficiency for different non-conformity scores and when considering multiple groups.

Figure: Figure 1: Pokec-{n, z} using both sensitive attributes. The top plots present the efficiency results, while the bottom plots are for the fairness disparities for (a) APS, (b) DAPS, and (c) RAPS. In all cases, FedCF achieves the desired closeness criteria better than the base federated conformal predictors.
Refer to caption: x1.png

##### Robust Performance with Different Numbers of Clients.

An important trade-off in trustworthy FL is between predictive utility and maintaining fairness/privacy guarantees for each of its clients, which becomes increasingly challenging as the number of clients increases (Wen et al., 2023). To demonstrate how our framework can adapt to a varying number of clients, we use a Dirichlet partitioner with the Fitzpatrick dataset to evaluate performance with $K\in\{2,4,8\}$ clients in addition to a centralized setup with a single client. We see in Table [3](https://arxiv.org/html/2509.22907v1#S4.T3) that as the number of clients increases, the baseline performance worsens, but the FedCF framework can still control for the necessary closeness criterion. We omit Equal Opportunity for Fitzpatrick as it is not meaningful in the context of this dataset, which aims to predict a skin condition, and the sensitive attribute is the skin type. People with certain skin types are known to be more likely to develop certain skin conditions, so the true positive rates of a classifier will typically not equalize, resulting in a degenerate (meaningless) solution. Finally, Fitzpatrick is a relatively small dataset with fewer than 17K points. Splitting the dataset into different splits and clients will result in a small number of points per $(g,\tilde{y})$ pair, making the interval bounds from Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1) quite large.

**Table 3: Fitzpatrick using RAPS. Each entry is of the form, efficiency/fairness disparity. We bold the lower fairness disparity value for each comparison. This table contains the results for $K\in\{1,2,4,8\}$ clients. We observe that FedCF consistently matches or outperforms the base federated conformal predictor and is below the desired closeness criterion, $c$.**
|  | 1 client | 2 clients | 4 clients | 8 clients |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Metric | Base | Ours | Base | Ours | Base | Ours | Base | Ours |
| Dem_Parity | 2.356 / 0.151 | 3.647 / 0.103 | 2.565 / 0.163 | 4.149 / 0.153 | 2.844 / 0.293 | 4.684 / 0.099 | 3.502 / 0.166 | 5.214 / 0.089 |
| Pred_Eq | 2.356 / 0.111 | 3.647 / 0.109 | 2.543 / 0.177 | 4.140 / 0.177 | 2.837 / 0.287 | 4.564 / 0.102 | 3.502 / 0.171 | 5.293 / 0.083 |

##### Efficiency vs Fairness Trade-Off.

To make FedCF an actionable framework, it is essential to understand the utility trade-off when imposing fairness constraints. Using the interval-based approach to estimate the fairness-specific coverage gap gives a finite-sample guarantee for controlling fairness gaps. However, sometimes imposing fairness may result in a severe cost to utility. For example, a degenerate conformal predictor (one with near-full efficiency) is “fair,” but completely impractical for use. By relaxing the theoretical guarantees, we can improve the efficiency by considering a tighter estimate for the coverage gap, using point estimates through MLE. Figure [2](https://arxiv.org/html/2509.22907v1#S4.F2) compares the efficiency and fairness disparities when using the interval bounds vs the point estimate on the ACSEducation dataset. We observe that with the interval bounds, we always get within the closeness criterion, but the efficiencies are quite high. Alternatively, using point estimates may exceed the desired closeness criterion, but be more fair than the baseline and not sacrifice as much efficiency.

Figure: Figure 2: ACSEducation using RAPS. The left two plots are the efficiency plots for (a) using the interval bounds and (b) using the MLE estimate. Similarly, the two right (c) using the interval bounds and (d) using the MLE estimate. We observe that with the MLE estimates, FedCF achieves lower efficiency at the cost of a higher worst-case fairness disparity. Both the interval bounds and MLE estimates outperform the base federated conformal predictor in controlling for fairness disparity.
Refer to caption: x3.png

## 5 Discussion

##### On Data Heterogeneity.

In a practical federated setting, the data distribution will vary between clients–resulting in data heterogeneity across the FL system, which can affect performance at inference time (Wen et al., 2023). To address these concerns, we evaluate FedCF on varying partitioning schemes.
For Fitzpatrick, we use a probabilistic partitioning scheme to ensure the data is distributed in a particular manner. For the ACS and Pokec-{n, z} datasets, the partitioning is naturally induced by state and region information in the datasets.

##### On Data Requirements.

A major limitation of CP is that to achieve a desired coverage rate, practically, you require a large enough calibration dataset such that the interval width for the CP guarantee is tight enough. This is exacerbated in the CF and FedCF framework as it requires sufficient calibration data for each group-positive label pair (for each client). If we consider intersectional fairness, the multiplicative increase in the number of groups further increases the data requirements.

##### On Interval Bounds.

We provide two ways of estimating the fairness-specific coverage level with intervals and point estimates, but we can choose different intervals by considering the following. Suppose the event $s({\bm{x}}_{test},y_{test})\leq\lambda$ (conditioned on $F_{M}$) is a Bernoulli random trial of some unknown probability $p$. We want to estimate $p$ as that is our fairness-specific coverage level. If we also treat the calibration scores as Bernoulli trials (by exchangeability), we can estimate $p$ using a Binomial Proportion Confidence Interval. Several results provide tighter or looser bounds (Wallis, 2013), which can be used to get better efficiency vs. fairness trade-offs.

## 6 Conclusion

In this work, we extended the Conformal Fairness framework to a federated setting, introducing the novel and comprehensive FedCF framework. We reformulated the CF framework to use a descent-based approach to make it more efficient for FL applications. Additionally, we developed theoretically grounded protocols to enable coverage gap calculations in a federated manner. The FedCF framework offers clients a choice of participation protocols, including communication efficient and enhanced privacy options. We conducted experiments on various non-conformity scores and datasets– including graph data where we leverage the exchangeability assumption from CP.

##### Extensibility and Future Work

An important application of FedCF is that it can be used to audit federated conformal predictors for fairness (discussed in Appendix [G](https://arxiv.org/html/2509.22907v1#A7)). In the future, we will explore how FedCF can be extended to split learning (Gupta & Raskar, 2018).
Unlike federated Learning, which trains full models locally and aggregates updates, split learning divides the model across clients and server, sharing only partial computations (enhanced privacy, reduced compute).

## References

- Agrawal et al. (2024)
Nimesh Agrawal, Anuj Kumar Sirohi, Sandeep Kumar, et al.
No prejudice! fair federated graph neural networks for personalized recommendation.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pp. 10775–10783, 2024.
- Angelopoulos et al. (2022)
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I. Jordan.
Uncertainty sets for image classifiers using conformal prediction, 2022.
URL [https://arxiv.org/abs/2009.14193](https://arxiv.org/abs/2009.14193).
- Beutel et al. (2020)
Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Marques, Yan Gao, Lorenzo Sani, Hei Li Kwing, Titouan Parcollet, Pedro PB de Gusmão, and Nicholas D Lane.
Flower: A friendly federated learning research framework.
*arXiv preprint arXiv:2007.14390*, 2020.
- Chen & Guestrin (2016)
Tianqi Chen and Carlos Guestrin.
Xgboost: A scalable tree boosting system.
In *Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, KDD ’16, pp. 785–794, New York, NY, USA, 2016. Association for Computing Machinery.
ISBN 9781450342322.
doi: 10.1145/2939672.2939785.
URL [https://doi.org/10.1145/2939672.2939785](https://doi.org/10.1145/2939672.2939785).
- Cherian & Bronner (2020)
John Cherian and Lenny Bronner.
How the washington post estimates outstanding votes for the 2020 presidential election.
*Retrieved September*, 13:2023, 2020.
- Cresswell et al. (2025)
Jesse C Cresswell, Bhargava Kumar, Yi Sui, and Mouloud Belbahri.
Conformal prediction sets can cause disparate impact.
In *The Thirteenth International Conference on Learning Representations*, 2025.
- Ding et al. (2021)
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt.
Retiring adult: New datasets for fair machine learning.
*Advances in neural information processing systems*, 34:6478–6490, 2021.
- Dong et al. (2022)
Jinshuo Dong, Aaron Roth, and Weijie J Su.
Gaussian differential privacy.
*Journal of the Royal Statistical Society Series B: Statistical Methodology*, 84(1):3–37, 2022.
- Dunning (2021)
Ted Dunning.
The t-digest: Efficient estimates of distributions.
*Software Impacts*, 7:100049, 2021.
ISSN 2665-9638.
doi: https://doi.org/10.1016/j.simpa.2020.100049.
URL [https://www.sciencedirect.com/science/article/pii/S2665963820300403](https://www.sciencedirect.com/science/article/pii/S2665963820300403).
- Dwork (2006)
Cynthia Dwork.
Differential privacy.
In *International colloquium on automata, languages, and programming*, pp. 1–12. Springer, 2006.
- Dwork et al. (2014)
Cynthia Dwork, Aaron Roth, et al.
The algorithmic foundations of differential privacy.
*Foundations and trends® in theoretical computer science*, 9(3–4):211–407, 2014.
- Erlingsson et al. (2019)
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.
Amplification by shuffling: From local to central differential privacy via anonymity.
In *Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 2468–2479. SIAM, 2019.
- European Parliament and Council of the European Union (2024)
European Parliament and Council of the European Union.
Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 laying down harmonised rules on artificial intelligence (Artificial Intelligence Act) and amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 2018/858, (EU) 2018/1139 and (EU) 2019/2144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2019/882.
Official Journal of the European Union, 2024.
URL [https://eur-lex.europa.eu/eli/reg/2024/1689/oj/eng](https://eur-lex.europa.eu/eli/reg/2024/1689/oj/eng).
- Fayyazi et al. (2025)
Arya Fayyazi, Mehdi Kamal, and Massoud Pedram.
Facter: Fairness-aware conformal thresholding and prompt engineering for enabling fair llm-based recommender systems.
In *Forty-second International Conference on Machine Learning*, 2025.
- Groh et al. (2021)
Matthew Groh, Caleb Harris, Luis Soenksen, Felix Lau, Rachel Han, Aerin Kim, Arash Koochek, and Omar Badri.
Evaluating deep neural networks trained on clinical images in dermatology with the fitzpatrick 17k dataset.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 1820–1828, 2021.
- Gupta & Raskar (2018)
Otkrist Gupta and Ramesh Raskar.
Distributed learning of deep neural network over multiple agents.
*Journal of Network and Computer Applications*, 116:1–8, 2018.
ISSN 1084-8045.
doi: https://doi.org/10.1016/j.jnca.2018.05.003.
URL [https://www.sciencedirect.com/science/article/pii/S1084804518301590](https://www.sciencedirect.com/science/article/pii/S1084804518301590).
- H. Zargarbashi et al. (2023)
Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski.
Conformal prediction sets for graph neural networks.
In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), *Proceedings of the 40th International Conference on Machine Learning*, volume 202 of *Proceedings of Machine Learning Research*, pp. 12292–12318. PMLR, 23–29 Jul 2023.
URL [https://proceedings.mlr.press/v202/h-zargarbashi23a.html](https://proceedings.mlr.press/v202/h-zargarbashi23a.html).
- Hamilton et al. (2017)
William L. Hamilton, Rex Ying, and Jure Leskovec.
Inductive representation learning on large graphs.
*CoRR*, abs/1706.02216, 2017.
URL [http://arxiv.org/abs/1706.02216](http://arxiv.org/abs/1706.02216).
- He et al. (2016)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.
Deep residual learning for image recognition.
In *2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 770–778, 2016.
doi: 10.1109/CVPR.2016.90.
- Hirsch et al. (2023)
Dennis Hirsch, Timothy Bartley, Aravind Chandrasekaran, Davon Norris, Srinivasan Parthasarathy, and Piers Norris Turner.
*Business Data Ethics: Emerging Models for Governing AI and Advanced Analytics*.
Springer Nature, 2023.
- Jones et al. (2025)
Charles Jones, Fabio De Sousa Ribeiro, Mélanie Roschewitz, Daniel C Castro, and Ben Glocker.
Rethinking fair representation learning for performance-sensitive tasks.
In *The Thirteenth International Conference on Learning Representations*, 2025.
- Kaplan et al. (2020)
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.
Scaling laws for neural language models.
*CoRR*, abs/2001.08361, 2020.
URL [https://arxiv.org/abs/2001.08361](https://arxiv.org/abs/2001.08361).
- Komala et al. (2024)
CR Komala, Ashok Kumar, N Hema, S Nagarani, Ajay Singh Yadav, M Rajendiran, R Srinivasan, and V Vijayan.
Fair-automl: Enhancing fairness in machine learning predictions through automated machine learning and bias mitigation techniques.
In *AIP Conference Proceedings*, volume 3193, pp. 020005. AIP Publishing LLC, 2024.
- Lu et al. (2022)
Charles Lu, Andréanne Lemay, Ken Chang, Katharina Höbel, and Jayashree Kalpathy-Cramer.
Fair conformal predictors for applications in medical imaging.
*Proceedings of the AAAI Conference on Artificial Intelligence*, 36(11):12008–12016, Jun. 2022.
doi: 10.1609/aaai.v36i11.21459.
URL [https://ojs.aaai.org/index.php/AAAI/article/view/21459](https://ojs.aaai.org/index.php/AAAI/article/view/21459).
- Lu et al. (2023)
Charles Lu, Yaodong Yu, Sai Praneeth Karimireddy, Michael Jordan, and Ramesh Raskar.
Federated conformal predictors for distributed uncertainty quantification.
In *International Conference on Machine Learning*, pp. 22942–22964. PMLR, 2023.
- Maneriker et al. (2023)
Pranav Maneriker, Codi Burley, and Srinivasan Parthasarathy.
Online fairness auditing through iterative refinement.
In *Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining*, KDD ’23, pp. 1665–1676, New York, NY, USA, 2023. Association for Computing Machinery.
ISBN 9798400701030.
doi: 10.1145/3580305.3599454.
URL [https://doi.org/10.1145/3580305.3599454](https://doi.org/10.1145/3580305.3599454).
- Maneriker et al. (2025)
Pranav Maneriker, Aditya T Vadlamani, Anutam Srinivasan, Yuntian He, Ali Payani, et al.
Conformal prediction: A theoretical note and benchmarking transductive node classification in graphs.
*Transactions on Machine Learning Research*, May 2025.
- Masson et al. (2019)
Charles Masson, Jee E. Rim, and Homin K. Lee.
Ddsketch: a fast and fully-mergeable quantile sketch with relative-error guarantees.
*Proc. VLDB Endow.*, 12(12):2195–2205, August 2019.
ISSN 2150-8097.
doi: 10.14778/3352063.3352135.
URL [https://doi.org/10.14778/3352063.3352135](https://doi.org/10.14778/3352063.3352135).
- McMahan et al. (2017)
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.
Communication-Efficient Learning of Deep Networks from Decentralized Data.
In Aarti Singh and Jerry Zhu (eds.), *Proceedings of the 20th International Conference on Artificial Intelligence and Statistics*, volume 54 of *Proceedings of Machine Learning Research*, pp. 1273–1282. PMLR, 20–22 Apr 2017.
URL [https://proceedings.mlr.press/v54/mcmahan17a.html](https://proceedings.mlr.press/v54/mcmahan17a.html).
- Mehrabi et al. (2021)
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.
A survey on bias and fairness in machine learning.
*ACM computing surveys (CSUR)*, 54(6):1–35, 2021.
- New York City Council (2021)
New York City Council.
Local law 4 of 2021: Fair chance act, 7 2021.
URL [https://www.nyc.gov/site/cchr/law/fair-chance-act.page](https://www.nyc.gov/site/cchr/law/fair-chance-act.page).
- New York City Council (2023)
New York City Council.
Local law 144 of 2021: Prohibiting automated employment decision tools.
*New York City Register*, 7 2023.
URL [https://www.nyc.gov/site/dca/about/automated-employment-decision-tools.page](https://www.nyc.gov/site/dca/about/automated-employment-decision-tools.page).
- Polyak (1964)
B.T. Polyak.
Some methods of speeding up the convergence of iteration methods.
*USSR Computational Mathematics and Mathematical Physics*, 4(5):1–17, 1964.
ISSN 0041-5553.
doi: https://doi.org/10.1016/0041-5553(64)90137-5.
URL [https://www.sciencedirect.com/science/article/pii/0041555364901375](https://www.sciencedirect.com/science/article/pii/0041555364901375).
- Romano et al. (2020a)
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès.
With malice toward none: Assessing uncertainty via equalized coverage.
*Harvard Data Science Review*, 2020a.
- Romano et al. (2020b)
Yaniv Romano, Matteo Sesia, and Emmanuel Candes.
Classification with valid and adaptive coverage.
*Advances in neural information processing systems*, 33:3581–3591, 2020b.
- Takac & Zabovsky (2012)
Lubos Takac and Michal Zabovsky.
Data analysis in public social networks.
In *International scientific conference and international workshop present day trends of innovations*, volume 1, 2012.
- U.S. Equal Employment Opportunity Commission (1979)
U.S. Equal Employment Opportunity Commission.
Questions and answers to clarify and provide a common interpretation of the uniform guidelines on employee selection procedures.
*Federal Register*, 44(43), 1979.
URL [https://www.eeoc.gov/laws/guidance/questions-and-answers-clarify-and-provide-common-interpretation-uniform-guidelines](https://www.eeoc.gov/laws/guidance/questions-and-answers-clarify-and-provide-common-interpretation-uniform-guidelines).
- Vadlamani et al. (2025)
Aditya T. Vadlamani, Anutam Srinivasan, Pranav Maneriker, Ali Payani, and Srinivasan Parthasarathy.
A generic framework for conformal fairness.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=xiQNfYl33p](https://openreview.net/forum?id=xiQNfYl33p).
- Vovk et al. (2005)
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer.
*Algorithmic learning in a random world*, volume 29.
Springer, 2005.
- Wallis (2013)
Sean Wallis.
Binomial confidence intervals and contingency tests: Mathematical fundamentals and the evaluation of alternative methods.
*Journal of Quantitative Linguistics*, 20(3):178–208, 2013.
doi: 10.1080/09296174.2013.799918.
URL [https://doi.org/10.1080/09296174.2013.799918](https://doi.org/10.1080/09296174.2013.799918).
- Wen et al. (2023)
Jie Wen, Zhixia Zhang, Yang Lan, Zhihua Cui, Jianghui Cai, and Wensheng Zhang.
A survey on federated learning: challenges and applications.
*International journal of machine learning and cybernetics*, 14(2):513–535, 2023.
- Yurochkin et al. (2019)
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Trong Nghia Hoang, and Yasaman Khazaeni.
Bayesian nonparametric federated learning of neural networks, 2019.
URL [https://arxiv.org/abs/1905.12022](https://arxiv.org/abs/1905.12022).
- Zhou & Sesia (2024)
Yanfei Zhou and Matteo Sesia.
Conformal classification with equalized coverage for adaptively selected groups.
*Advances in Neural Information Processing Systems*, 37:108760–108823, 2024.

## Appendix A Notation Table

**Table 4: Common notation used in FedCF.**
| Notation | Defintion |
| --- | --- |
| ${\mathcal{G}}$ | The set of all demographic groups. |
| ${\mathcal{Y}},{\mathcal{Y}}^{+}$ | The set of labels and positive/advantaged labels, respectively. |
| $g\text{ and }\tilde{y}$ | The group $g\in\mathcal{G}$ and $\tilde{y}\in\mathcal{Y}^{+}$ under consideration. |
| $F_{M}$ | Filter function for fairness metric $M$. |
| $c$ | Closeness criterion for a fairness specification. |
| $\lambda$ | Threshold used for constructing test prediction sets. |
| ${\mathcal{K}}$ | The set of clients, $\{1,\dots,K\}$. |
| $\mathcal{D}_{\mathrm{train}}^{(k)}/\mathcal{D}_{\mathrm{valid}}^{(k)}/\mathcal{D}_{\mathrm{calib}}^{(k)}$ | Client $k$’s train/validation/calibration dataset. |
| $n_{k}$ and $N$ | $|\mathcal{D}_{\mathrm{calib}}^{(k)}|$ and $\sum\limits_{k=1}^{K}n_{k}$, respectively. |
| ${\mathcal{S}}_{k}^{(g,\tilde{y})}$ and $n_{k}^{(g,\tilde{y})}$ | $\{({\bm{x}}_{i},y_{i})\in\mathcal{D}_{\mathrm{calib}}^{(k)}\mid F_{M}({\bm{x}}_{i},y_{i},g,\tilde{y})=1\}$ and $\lvert{\mathcal{S}}_{k}^{(g,\tilde{y})}\rvert$ |
| $\alpha_{k}^{(g,\tilde{y});\lambda}$ | $\sum\limits_{({\bm{x}}_{i},_)\in{\mathcal{S}}_{k}^{(g,\tilde{y})}}\bm{1}[s({\bm{x}}_{i},\tilde{y})\leq\lambda]$ |
| $E_{k}$ and $\gamma_{k}$ | The event $\bm{x}_{\text{test}}$ is exchangeable with data from client $k$ and $\Pr[E_{k}]$. |
| $L^{(g,\tilde{y})},U^{(g,\tilde{y})}$ | Bounds for prior (term IV). |
| $\pi^{(g,\tilde{y})}$ | Point estimate for prior (term IV). |
| $L_{\text{cov}},U_{\text{cov}}$ | Bounds for fairness-specific coverage level. |
| $\Pi_{\text{cov}}$ | Point estimate for fairness-specific coverage level. |

## Appendix B Proofs

### B.1 Proof of Theorem 3.1

Recall, since the data is distributed across clients in the federated setting, we reformulated the fairness-specific coverage level as Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3). In doing so, the computation of the coverage level is split between the clients and the server. We present bounds and point estimates for each of the terms in Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3) across Lemmas [B.1](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem1), [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2), and [B.3](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem3), leading to a proof of Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1).

#### B.1.1 Client-Side Estimates

Since each client operates independently with its own dataset, we can derive interval bounds for terms I and II. For the point estimates approach, we use maximum likelihood estimators (MLEs) for each term, providing the tightest estimates.

###### Lemma B.1 .

For each client $k$, group $g$, positive label $\tilde{y}$, and threshold $\lambda$, we get the following interval bounds:

$$ $\textstyle\frac{\alpha_{k}^{(g,\tilde{y});\lambda}}{n_{k}^{(g,\tilde{y})}+1}\leq\Pr[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,E_{k}]\leq\frac{\alpha_{k}^{(g,\tilde{y});\lambda}+1}{n_{k}^{(g,\tilde{y})}+1}$ (9) $$

If the data are IID, then we can use an MLE point estimate, given by the following:

$$ $\textstyle\Pr[s({\bm{x}}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,E_{k}]=\frac{\alpha_{k}^{(g,\tilde{y});\lambda}}{n_{k}^{(g,\tilde{y})}}$ (10) $$

The proof of Lemma [B.1](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem1) is as follows:

###### Proof.

We first observe that,

$$ $\displaystyle\Pr[s(\bm{x}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,~E_{k}]$ $\displaystyle=\underset{\bm{x}_{\text{test}}\sim{P}_{k}}{\Pr}[s(\bm{x}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1],$ $$

since exchangeability with the elements in $k$ is true iff $\bm{x}_{\text{test}}$ is sampled from $k$’s local distribution, $P_{k}$. The interval bounds follow from the conditional coverage guarantees given in CF (Vadlamani et al., 2025).

For the point estimate, we can model the event that the predicted score $s({\bm{x}}_{test},\tilde{y})$ falls below $\lambda$ as a Bernoulli random variable with success probability $p$. We can treat the $n_{k}^{(g,\tilde{y})}$ calibration points as individual Bernoulli trials, to then construct a maximum likelihood estimate (MLE) for $p$, which will be $\hat{p}=\frac{\alpha_{k}^{(g,\tilde{y});\lambda}}{n_{k}^{(g,\tilde{y})}}$.
∎

Lemma [B.1](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem1) bounds the fair-conditional coverage for a particular group-label pair for the test covariate $(\bm{x}_{\text{test}},y_{\text{test}})$. We next bound the coverage of the test covariate satisfying the Fairness Metric ($F_{M}$), conditioned on the test point being exchangeable with data from client $k$ using Lemma [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2), and provide the proof below.

###### Lemma B.1 .

###### Proof.

#### B.1.2 Server-Side Estimates

Terms III and IV require a global view of the clients’ data, so they are handled on the server.

For term III, we follow the setup by Lu et al. (2023), where given $n_{k}=\lvert\mathcal{D}_{\mathrm{calib}}^{(k)}\rvert$, $\gamma_{k}\coloneqq\Pr[E_{k}]\propto n_{k}+1$ and $\sum\limits_{k=1}^{K}\gamma_{k}=1$. Finally, for term IV, we have that

$$ $\textstyle\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]=\sum\limits_{k=1}^{K}\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1\mid E_{k}]\cdot\Pr[E_{k}].$ $$

Using Lemma [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2), we can get an interval-bound and point-estimate as shown in the following lemma.

###### Lemma B.2 .

For each client $k$, group $g$, and positive label $\tilde{y}$, we get the following interval bounds:

$$ $\textstyle\frac{n_{k}^{(g,\tilde{y})}}{n_{k}+1}\leq\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1\mid E_{k}]\leq\frac{n_{k}^{(g,\tilde{y})}+1}{n_{k}+1}$ (11) $$

If the data are IID, then we can use an MLE point estimate, given by the following:

$$ $\textstyle\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1\mid E_{k}]=\frac{n_{k}^{(g,\tilde{y})}}{n_{k}}$ (12) $$

###### Proof.

To demonstrate the finite sample guarantee, we note that $F_{M}({\bm{x}},y,g,\tilde{y})=1$ for all $({\bm{x}},y)\in\mathcal{D}_{\mathrm{calib}}^{(k)}$ are all exchangeable Bernoulli trials. Observe that conditioning on $E_{k}$ implies ${\mathcal{D}_{\mathrm{calib}}}_{+}^{(k)}\coloneqq\mathcal{D}_{\mathrm{calib}}^{(k)}\cup\{\bm{x}_{\text{test}}\}$ is an exchangeable sequence of length $n_{k}+1$. Treating this as a finite ’bag’ of covariates, we have

$$ $\forall_{({\bm{x}},y)\in{\mathcal{D}_{\mathrm{calib}}}_{+}^{(k)}},~~\Pr[F_{M}(\bm{x},y,g,\tilde{y})=1~|~E_{k}]=\frac{\sum_{(\bm{x}_{i},y_{i})\in{\mathcal{D}_{\mathrm{calib}}}_{+}^{(k)}}F_{M}(\bm{x_{i}},y_{i},g,\tilde{y})}{n_{k}+1}.$ $$

In other words, we have defined the probability of randomly selecting a covariate with $F_{M}({\bm{x}},y,g,\tilde{y})=1$. Since this applies to all points we know,

$$ $\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1~|~E_{k}]=\frac{\sum\limits_{(\bm{x}_{i},y_{i})\in{\mathcal{D}_{\mathrm{calib}}}_{+}^{(k)}}F_{M}(\bm{x}_{i},y_{i},g,\tilde{y})}{n_{k}+1}.$ (13) $$

Since we implicitly condition on $F_{M}(\bm{x},y,g,\tilde{y}),~~\forall(\bm{x},y)\in k$ (effectively making them deterministic), we can calculate the following bounds [13](https://arxiv.org/html/2509.22907v1#A2.E13),

$$ $\displaystyle\frac{\underset{(\bm{x}_{i},y_{i})\in\mathcal{D}_{\mathrm{calib}}^{(k)}}{\sum}F_{M}(\bm{x_{i}},y_{i},g,\tilde{y})}{n_{k}+1}\leq\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1~|~E_{k}]$ $\displaystyle~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\leq\frac{\underset{(\bm{x}_{i},y_{i})\in\mathcal{D}_{\mathrm{calib}}^{(k)}}{\sum}F_{M}(\bm{x_{i}},y_{i},g,\tilde{y})+1}{n_{k}+1},$ (14) $$

where the $+1$ term comes from the unknown value of $F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})$. Substituting the sums with $n_{k}^{(g,\tilde{y})}$, proves the interval bounds.

For the point estimate, the event that $F_{M}=1$ can be modeled as a Bernoulli random variable with success probability $p$. We can use the full $n_{k}$ calibration points as $n_{k}$ Bernoulli trials to construct an MLE for $p$, which will be $\hat{p}=\frac{n_{k}^{(g,\tilde{y})}}{n_{k}}$.
∎

Lastly, we use Lemma [B.3](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem3), to bound $\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]$. The proof of Lemma [B.3](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem3) leverages the result of Lemma [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2).

###### Lemma B.3 .

For each client $k$, group $g$, and positive label $\tilde{y}$, we get the following interval bounds:

$$ $\textstyle L^{(g,\tilde{y})}=\sum\limits_{k=1}^{K}\gamma_{k}\frac{n_{k}^{(g,\tilde{y})}}{n_{k}+1}\leq\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]\leq\sum\limits_{k=1}^{K}\gamma_{k}\frac{n_{k}^{(g,\tilde{y})}+1}{n_{k}+1}=U^{(g,\tilde{y})}.$ (15) $$

If the data are IID, then we can use an MLE point estimate, given by the following:

$$ $\textstyle\Pr[F_{M}({\bm{x}}_{\text{test}},y_{\text{test}},g,\tilde{y})=1]=\sum\limits_{k=1}^{K}\gamma_{k}\frac{n_{k}^{(g,\tilde{y})}}{n_{k}}=\pi^{(g,\tilde{y})}.$ (16) $$

###### Proof.

To achieve this result, we first use the law of total probability to separate $\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})]$ into terms known by the server and the client:

$$ $\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})]=\sum_{k=1}^{K}\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1~|~E_{k}]\cdot\Pr[E_{k}]$ (17) $$

Then, substituting the bounds for term II (see Lemma [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2)), and $\gamma_{k}=\Pr[E_{k}]$ from term IV into Equation [17](https://arxiv.org/html/2509.22907v1#A2.E17), we complete the proof.
∎

Having proved the Lemmas, we can move on to proving,
See [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1)

###### Proof.

Substituting the bounds for terms I, II, and IV which were established via Lemmas [B.1](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem1), [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2), [B.3](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem3) respectively and the defintion of III into Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3) completes the proof.
∎

On closer inspection, we observe that Terms I and II can be combined and bound together.

###### Lemma B.4 .

Using the defintions of $\alpha_{k}^{(g,\tilde{y});\lambda}$ and $n_{k}+1$ we have,

$$ $\displaystyle\frac{\alpha_{k}^{(g,\tilde{y});\lambda}}{n_{k}+1}\leq\Pr[s(\bm{x}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,~\bm{x}_{\text{test}}\overset{\text{exc.}}{\sim}k]$ $\displaystyle~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\cdot\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1~|~\bm{x}_{\text{test}}\overset{\text{exc.}}{\sim}k]\leq\frac{\alpha_{k}^{(g,\tilde{y});\lambda}+1}{n_{k}+1}.$ (18) $$

###### Proof.

First, observe that,

$$ $\displaystyle{\Pr[s(\bm{x}_{\text{test}},\tilde{y})\leq\lambda~|~F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1,~E_{k}]\cdot\Pr[F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1~|~E_{k}]}$ $\displaystyle=\Pr[s(\bm{x}_{\text{test}},\tilde{y})\leq\lambda,~F_{M}(\bm{x}_{\text{test}},y_{\text{test}},g,\tilde{y})=1~|~E_{k}]$ $$

Then consider the following Bernoulli random variables (R.V) $\bm{1}[s(\bm{x},y)\leq\lambda]\cdot F_{M}(\bm{x},y,g,\tilde{y})$ for all $(\bm{x},y)\in k\cup\{(\bm{x}_{\text{test}},y_{\text{test}})\}$ which form an exchangeable sequence (using the assumption $\bm{x}_{\text{test}}\overset{\text{exc.}}{\sim}k$). Additionally, observe $\alpha_{k}^{(g,\tilde{y});\lambda}=\sum_{(\bm{x}_{i},y_{i})\in k}\bm{1}[s(\bm{x},y)\leq\lambda]\cdot F_{M}(\bm{x},y,g,\tilde{y})$ is an equivalent definition of $\alpha_{k}^{(g,\tilde{y});\lambda}$. The rest of the proof follows from the proof of Lemma [B.2](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem2) by using $\bm{1}[s(\bm{x},y)\leq\lambda]\cdot F_{M}(\bm{x},y,g,\tilde{y})$ as the Bernoulli R.V instead of $F_{M}(\bm{x},y,g,\tilde{y})$ and $\alpha_{k}^{(g,\tilde{y});\lambda}$ in place of $n_{k}^{(g,\tilde{y})}$.
∎

Using the above result, we can tighten the lower-bound of Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1).

###### Corollary B.1 .

Swapping terms I and II with the combined term in Lemma [B.4](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem4), the lower bound in Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1) can be simplified and tightened to

$$ $L_{\text{cov}}(\lambda,F_{M},g,\tilde{y})=\sum_{k=1}^{K}\frac{\gamma_{k}\alpha_{k}^{(g,\tilde{y});\lambda}}{(n_{k}+1)U^{(g,\tilde{y})}}$ (19) $$

###### Proof.

Instead of substituting terms I and II into Equation [3](https://arxiv.org/html/2509.22907v1#S3.E3) as in the proof of Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1), we can instead use Lemma [B.4](https://arxiv.org/html/2509.22907v1#A2.Thmtheorem4) to update the bounds. Observe that the upper bound remains the same as Theorem [3.1](https://arxiv.org/html/2509.22907v1#S3.Thmtheorem1) while the lower bound becomes tighter.
∎

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Proof.

###### Lemma B.4 .

###### Proof.

###### Corollary B.1 .

###### Proof.

## Appendix C Additional Experiment Details

### C.1 Datasets

We present a summary of common dataset statistics in Table [5](https://arxiv.org/html/2509.22907v1#A3.T5) and go into more details on each dataset in the following sections.

**Table 5: Dataset Statistics. T refers to Tabular, G refers to Graph, and V refers to vision. ^∗ACS datasets have six (6) groups if using the continental split schemes (see Section [C.2](https://arxiv.org/html/2509.22907v1#A3.SS2)). ˆ Number of inputs after removing those with unknown group information**
| Name | Type | Size | # Labeled | # Groups | # Classes |
| --- | --- | --- | --- | --- | --- |
| ACSIncome | T | $1,664,500$ | ALL | race$(9)^{*}$ | $4$ |
| ACSEducation | T | $1,664,500$ | ALL | race$(9)^{*}$ | $6$ |
| Fitzpatrick | V | $16,012$ˆ | ALL | skin type$(6)$ | $9$ |
| Name | Type | $(|{\mathcal{V}}|,|{\mathcal{E}}|)$ | # Labeled | # Groups | # Classes |
| Pokec-{n, z} | G | $(133,138,~1,458,258)$ | $17,594$ | region$(2)$, gender$(2)$ | $4$ |

### C.2 Folktables Datasets

In the fairness space, the American Community Services (ACS) datasets from the Folktables library are a widely used set of tabular data (Ding et al., 2021). The data is taken across the 51 U.S. states and territories. For our federated setup and each dataset below, we consider the following 6 partitioning schemes:

- (1.)
All: We consider each U.S. state and territory to be its own client
- (2.)
Large: We follow the U.S. Census Bureau’s division of the U.S. into the Northeast, the Midwest, the South, and the West
- (3.)
Small: We follow the Bureau of Economic Analysis’s division of the U.S. into New England, the Mideast, the Great Lakes, the Plains, the Southeast, the Southwest, the Rocky Mountain, and the Far West.
- (4-6.)
Continental All, Continental Large, Continental Small: The same as 1 to 3, but we only consider the continental U.S.–removing Alaska, Hawaii, and Puerto Rico.

All Folktable datasets have a race attribute. When we partition the data using all the states and territories, we use the full version of race, which has 9 groups. However, when partitioning just with continental U.S., we combine some demographic groups–primarily those from Alaska, Hawaii, and Puerto Rico–into the appropriate ‘Other’ categories, resulting in a total of 6 groups.

##### ACSIncome:

We used the standard ACSIncome dataset from Folktables; however, we divided the targets into four classes by evenly splitting the income into 4 brackets. The sensitive attribute in this case is race, resulting in either $9$ or $6$ groups.

##### ACSEducation:

This is a custom dataset. We used the ACSTravelTime data and selected Education Level as the target. The education level was divided into $6$ groups: {did not complete high school, has a high school diploma, has a GED, started an undergrad program, completed an undergrad program, and completed graduate or professional school}. ACSEducation also uses race as a sensitive attribute.

### C.3 Non-Tabular Datasets

##### Pokec-{n,z}:

The Pokec-{n, z} dataset (Takac & Zabovsky, 2012) is a social network graph dataset collected from Pokec, a popular social network in Slovakia. Since several rows in the dataset are missing features, two commonly used subgraphs are the Pokec-z and Pokec-n datasets. The graphs have four labels corresponding to the fieldwork and two sensitive attributes: gender ($2$ groups) and region ($2$ groups). Our experiments consider each attribute individually as well as intersectional fairness by creating an attribute with $4$ groups. For our federated setup, we use each subgraph as a single client, resulting in $2$ clients.

##### Fitzpatrick:

The Fitzpatrick dataset (Groh et al., 2021) contains clinical images classified based on the depicted skin condition. There are several levels of granularity regarding the skin condition label. We use a version with 9 skin conditions: {inflammatory, malignant epidermal, genodermatoses, benign dermal, benign epidermal, malignant melanoma, benign melanocyte, malignant cutaneous lymphoma, malignant dermal}. There are 6 demographic groups based on the Fitzpatrick skin type. For our federated setup, we use a Dirichlet partitioner to split the data into $K\in\{2,4,8\}$ clients.

### C.4 Hyperparameters and Implementation

To promote reproducibility, the source code for FedCF is provided in the supplementary material, along with the configuration files containing the hyperparameters used.

The project was written using the Flower AI Federated Learning framework (Beutel et al., 2020) for both base model training and the FedCF framework.

### C.5 Non-Conformity Scores

##### Adaptive Prediction Sets (APS)

The most popular CP method for classification problems is APS (Romano et al., 2020b). The scoring function first sorts the softmax logits in descending order and accumulates the class probabilities until the correct class is included. For tighter prediction sets, randomization is introduced through a uniform random variable.

Formally, let $\hat{\pi}$ be a trained classification model with softmaxed output. If $\hat{\pi}({\bm{x}})_{(1)}\geq\hat{\pi}({\bm{x}})_{(2)}\geq\dots\geq\hat{\pi}({\bm{x}})_{(K-1)}$, $u\sim U(0,1)$, and $r_{y}$ is the rank of the correct label, then

$$ $s({\bm{x}},y)=[\sum_{i=1}^{r_{y}}\hat{\pi}({\bm{x}})_{(i)}]-u\hat{\pi}({\bm{x}})_{y}.$ $$

APS has two major drawbacks that have led to it being surpassed by other methods in recent CP literature. First, APS tends to produce large (less efficient) prediction sets. Second, it does not account for structure in its formulation. To address these issues, alternatives like RAPS and DAPS have emerged(^3^33RAPS and DAPS have hyperparameters typically tuned on separate held-out data, but we fix them a priori to preserve data for calibration and evaluation as well as to be consistent with what prior federated conformal prediction works have done.).

##### Regularized Adaptive Prediction Sets (RAPS)

Angelopoulos et al. (2022) introduces a regularization approach for APS. Given the same setup and notation as APS, define $o({\bm{x}},y)=\lvert\{c\in\mathcal{Y}:\hat{\pi}({\bm{x}})_{y}\geq\hat{\pi}({\bm{x}})_{c}\}\rvert$. Then,

$$ $s({\bm{x}},y)=[\sum_{i=1}^{r_{y}}\hat{\pi}({\bm{x}})_{(i)}]-u\hat{\pi}({\bm{x}})_{y}+\nu\cdot\max\{(o({\bm{x}},y)-k_{reg}),0\},$ $$

where $\nu$ and $k_{reg}\geq 0$ are regularization hyperparameters.

##### Diffusion Adaptive Prediction Sets (DAPS)

Graphs are rich with neighborhood information, with nodes often exhibiting homophily. This suggests that the non-conformity scores of connected nodes are likely to be related. To leverage this insight, DAPS H. Zargarbashi et al. (2023) incorporates a one-step diffusion update on the non-conformity scores. Formally, if $s({\bm{x}},y)$ is a point-wise score function (e.g., APS), then the diffusion step yields a new score function

$$ $\hat{s}({\bm{x}},y)=(1-\delta)s({\bm{x}},y)+\frac{\delta}{|{\mathcal{N}}_{\bm{x}}|}\sum\limits_{{\bm{u}}\in{\mathcal{N}}_{\bm{x}}}s({\bm{u}},y),$ $$

where $\delta\in[0,1]$ is a diffusion hyperparamter and ${\mathcal{N}}_{\bm{x}}$ is the $1$-hop neighborhood of ${\bm{x}}$.

## Appendix D FedCF with Enhanced Privacy

Preserving data privacy is a fundamental pillar of FL mechanisms, as they typically interact with sensitive client data. In this vein, we formulate an enhanced privacy version of FedCF.

### D.1 Enhanced Privacy

To better preserve privacy (compared to the communication efficient approach), we can offload more of the computation to the client-side, making it harder for the server-side to reverse-engineer or infer distributional information from the sent quantities. Expanding Equation [7](https://arxiv.org/html/2509.22907v1#S3.E7), we get

$$ $\displaystyle U_{\text{cov}}(\lambda,F_{m},g_{a},\tilde{y})-L_{\text{cov}}(\lambda,F_{m},g_{b}.\tilde{y})$ $\displaystyle=\sum\limits_{k=1}^{K}\gamma_{k}\underbrace{\{\frac{(\alpha_{k}^{(g_{a},\tilde{y});\lambda}+1)}{(n_{k}+1)L^{(g_{a},\tilde{y})}}-\frac{\alpha_{k}^{(g_{b},\tilde{y});\lambda}n_{k}^{(g_{b},\tilde{y})}}{(n_{k}^{(g_{b},\tilde{y})}+1)(n_{k}+1)U^{(g_{b},\tilde{y})}}\}}_{\text{Returned by the Client}}.$ (20) $$

In this formulation, the client sends back the summand for each group, positive label pair, making the space complexity of the client’s message ${\mathcal{O}}\big(\lvert{\mathcal{G}}\rvert^{2}\lvert{\mathcal{Y}}^{+}\rvert\big)$–quadratic with respect to the number of groups and linear with respect to positive labels.

The data privacy improves with this approach compared to the communication efficient version, since the data sent to the server is the difference of client-level summary statistics, which obfuscates individual distribution information from the server. However, unlike the communication efficient approach, the upper-coverage term ($U_{\text{cov}}$) is not separable from the aggregated sum, thus preventing us from enforcing $U_{\text{cov}}<1$. In limited data settings, this results in more conservative coverage gap estimates, which increases the prediction set size when using the enhanced privacy approach.

We provide a side-by-side comparison of the communication efficient and enhanced privacy version of computing the federated coverage gap in Figure [3](https://arxiv.org/html/2509.22907v1#A5.F3) in Appendix [E](https://arxiv.org/html/2509.22907v1#A5).

### D.2 Hybrid

In real-world scenarios, clients often have varying privacy and communication requirements. For example, clients in resource-constrained areas may not have the network bandwidth to send the necessary packets to the centralized server. In our proposed hybrid approach, a client may elect to be communication efficient, without preventing the remaining clients from using the enhanced privacy protocol. We present the full server-side algorithm, which combines the communication efficient, enhanced privacy, and hybrid protocols for the federated coverage gap, in Algorithm [6](https://arxiv.org/html/2509.22907v1#alg6) in Appendix [E](https://arxiv.org/html/2509.22907v1#A5).

### D.3 Empirical Comparison

We conduct two experiments using the Fitzpatrick dataset and $8$ clients, as well as the larger ACSIncome dataset with the continental_all partition scheme–$48$ clients–to test the communication efficient, enhanced privacy, and hybrid protocols. For the hybrid protocol, we randomly assign half the clients to each protocol. From Table [6](https://arxiv.org/html/2509.22907v1#A4.T6), we observe that all configurations control the fairness disparity within the closeness criterion; however, if all clients agree upon the communication efficient protocol, FedCF achieves a better efficiency with a slightly worse fairness disparity, albeit still within the closeness criterion. Though with more data, we observe that the efficiency gaps are smaller as seen in Table [7](https://arxiv.org/html/2509.22907v1#A4.T7).

**Table 6: Fitzpatrick, $\bm{8}$ clients, APS. Each entry is of the form, efficiency/fairness disparity. We bold the lower fairness disparity value for each comparison. We observe that the communication efficient approach produces the most efficient prediction sets, while having a similar or higher fairness disparity. The enhanced privacy approach and hybrid approach have similar performance (w.r.t efficiency and fairness disparity), with minor differences stemming from the stochasticity of FedCF, as they default to the same coverage-gap aggregation protocol (see Algorithm [6](https://arxiv.org/html/2509.22907v1#alg6)). All methods improve upon the baseline fairness disparity and control for the closeness criterion.**
| Metric | $c=0.1$ | $c=0.15$ | $c=0.2$ |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Base | Ours | Base | Ours | Base | Ours |  |
| Dem_Parity | 3.671 / 0.136 | 7.041 / 0.047 | 3.671 / 0.136 | 4.978 / 0.101 | 3.672 / 0.136 | 3.940 / 0.111 |
| Pred_Eq | 3.676 / 0.134 | 7.042 / 0.047 | 3.675 / 0.134 | 4.765 / 0.094 | 3.672 / 0.134 | 3.8803 / 0.106 |

**Table 7: ACSIncome, Continental All, RAPS. Each entry is of the form, efficiency/fairness disparity. We observe that with sufficient data, each protocol performs at a similar efficiency, and they all decrease the baseline fairness disparity and control it within the closeness criterion. Our fairness disparity values are bolded.**
| Metric | $c=0.1$ | $c=0.15$ | $c=0.2$ |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Base | Ours | Base | Ours | Base | Ours |  |
| Dem_Parity | 2.609 / 0.148 | 3.037 / 0.086 | 2.610 / 0.148 | 2.634 / 0.138 | 2.613 / 0.148 | 2.613 / 0.148 |
| Pred_Eq | 2.607 / 0.160 | 3.294 / 0.063 | 2.610 / 0.161 | 2.661 / 0.138 | 2.609 / 0.161 | 2.609 / 0.161 |

With these empirical results, note that under the hybrid setting, clients that optimize for communication efficiency still benefit from the fact that they can operate over a limited bandwidth network connection. The required bandwidth for a particular client undergoes a factor of $\approx\frac{|\mathcal{G}|}{2}$ reduction–i.e. $\mathcal{O}(|\mathcal{G}^{2}||\mathcal{Y}^{+})\to\mathcal{O}(2\cdot|\mathcal{G}||\mathcal{Y}^{+})$, when a client selects the communication efficient protocol while ensuring the remaining clients benefit from the enhanced privacy protocol. For Fitzpatrick, this results in the communication overhead (in bytes) being reduced by a factor of three.
($|\mathcal{G}|/2=3$, for Fitzpatrick). For the ACS datasets using the small, large, or all client assignments, this reduction corresponds to $|\mathcal{G}|/2=4.5$

## Appendix E Algorithms

Figure: Algorithm 4 More Communication Efficient Client-Side Computation for Coverage Gap

Figure: Algorithm 6 Full Server-side Aggregation for Coverage Gap

## Appendix F Differential Privacy in FedCF

FedCF can also be extended to formally consider $(\epsilon,\delta)$-differential privacy (DP), a mathematically rigorous framework for data privacy (Dwork, 2006), where $\delta$ is the probability that $\epsilon$-DP is violated. We can embed DP within our framework via client shuffling and additive noise approaches. Client shuffling is a global DP approach that is performed after the client sends data. Before the server receives the data, it goes through a trusted, centralized shuffler to anonymize which client has sent what data (Erlingsson et al., 2019). Our framework can accommodate client shuffling due to its parallelism with client-side computation and its additive aggregation approach.

For additive noise, we propose augmenting the values each client sends back with Gaussian noise(Dwork et al., 2014; Dong et al., 2022), such that a client returns,

$$ $h={\frac{(\alpha_{k}^{(g_{a},\tilde{y});\lambda}+1)}{(n_{k}+1)L^{(g_{a},\tilde{y})}}-\frac{\alpha_{k}^{(g_{b},\tilde{y});\lambda}n_{k}^{(g_{b},\tilde{y})}}{(n_{k}^{(g_{b},\tilde{y})}+1)(n_{k}+1)U^{(g_{b},\tilde{y})}}}+X,$ (21) $$

where $X$ is a Gaussian random variable (R.V). For the communication efficient approach, one would add a Gaussian R.V. to the upper coverage and lower coverage terms returned by the client. To ensure $(\epsilon,\delta)$-DP, we make $X\sim\mathcal{N}\bigg(0,\frac{2\ln(1.25/\delta)(\Delta g)^{2}}{\epsilon^{2}}\bigg)$, where $\Delta h$ is the sensitivty of $h$–or how much $h$ can change if one of the points in the client’s dataset changes. For FedCF, $h$ can be affected by data changes in the covariates (or non-conformity scores), labels, and group memberships.

### F.1 Example: Differential Privacy Bounds for Enhanced Privacy Protocol

Observe using the enhanced privacy approach, $\Delta h\leq\frac{1}{n_{k}}\big(\frac{1}{L^{(g_{a},\tilde{y})}}+\frac{1}{U^{(g_{b},\tilde{y})}}\big)$. For the communication efficient approach $\Delta h\leq\frac{1}{n_{k}L^{(g_{a},\tilde{y})}}$ for the upper coverage term and $\Delta h\leq\frac{1}{n_{k}U^{(g_{b},\tilde{y})}}$ for the lower coverage term. The server will know the sensitivity used by each client and their choice of $\epsilon$ and $\delta$.

To demonstrate how the server can estimate the coverage gap, we will consider an example using the enhanced privacy approach. The result from server aggregation is,

$$ $\displaystyle\text{cov_gap_est}(\lambda,F_{m},g_{a},g_{b},\tilde{y})$ $\displaystyle~~~=\sum\limits_{k=1}^{K}\gamma_{k}\underbrace{\{\frac{(\alpha_{k}^{(g_{a},\tilde{y});\lambda}+1)}{(n_{k}+1)L^{(g_{a},\tilde{y})}}-\frac{\alpha_{k}^{(g_{b},\tilde{y});\lambda}n_{k}^{(g_{b},\tilde{y})}}{(n_{k}^{(g_{b},\tilde{y})}+1)(n_{k}+1)U^{(g_{b},\tilde{y})}}+X_{k}^{(g_{a},g_{b},\tilde{y})}\}}_{\text{Returned by the Client}},$ (22) $$

where $X_{k}^{(g_{a},g_{b},\tilde{y})}\sim\mathcal{N}(0,{\sigma^{2}}_{k;(g_{a},g_{b},\tilde{y})})$ such that ${\sigma^{2}}_{k;(g_{a},g_{b},\tilde{y})}$ provides $(\epsilon_{k},\delta_{k})$-DP for the client. Then observe,

$$ $\displaystyle\text{cov_gap_est}(\lambda,F_{m},g_{a},g_{b},\tilde{y})$ $\displaystyle~~~~~~~~~~=\underbrace{\sum\limits_{k=1}^{K}\gamma_{k}\{\frac{(\alpha_{k}^{(g_{a},\tilde{y});\lambda}+1)}{(n_{k}+1)L^{(g_{a},\tilde{y})}}-\frac{\alpha_{k}^{(g_{b},\tilde{y});\lambda}n_{k}^{(g_{b},\tilde{y})}}{(n_{k}^{(g_{b},\tilde{y})}+1)(n_{k}+1)U^{(g_{b},\tilde{y})}}\}}_{\text{true coverage gap}}+\underbrace{\sum\limits_{k=1}^{K}\gamma_{k}X_{k}^{(g_{a},g_{b},\tilde{y})}}_{\text{Guassian R.V}}$ (23) $\displaystyle~~~~~~~~~~=\text{cov_gap}(\lambda,F_{m},g_{a},g_{b},\tilde{y})+X,~~X\sim\mathcal{N}\bigg(0,\sum\limits_{k=1}^{K}\gamma_{k}^{2}{\sigma^{2}}_{k;(g_{a},g_{b},\tilde{y})}\bigg)$ (24) $$

Using a prespecified probability $\beta$ we can accept or reject the statement $\text{cov_gap_est}(\lambda,F_{m},g_{a},g_{b},\tilde{y})\leq c$. In other words, we can check whether,

$$ $\displaystyle\text{cov_gap}(\lambda,F_{m},g_{a},g_{b},\tilde{y})+X\leq c\implies X\leq c-\text{cov_gap}(\lambda,F_{m},g_{a},g_{b},\tilde{y})$ $\displaystyle\implies\boxed{\underbrace{\frac{X}{\sqrt{\sum\limits_{k=1}^{K}\gamma_{k}X_{k}^{(g_{a},g_{b},\tilde{y})}}}}_{\text{Standard Normal RV}}\leq\frac{c-\text{cov_gap}(\lambda,F_{m},g_{a},g_{b},\tilde{y})}{\sqrt{\sum\limits_{k=1}^{K}\gamma_{k}X_{k}^{(g_{a},g_{b},\tilde{y})}}}}.$ $$

Then, if $\Phi(\frac{c-\text{cov_gap}(\lambda,F_{m},g_{a},g_{b},\tilde{y})}{\sqrt{\sum\limits_{k=1}^{K}\gamma_{k}X_{k}^{(g_{a},g_{b},\tilde{y})}}})>\beta$, where $\Phi$ is the CDF of the standard normal distribution, we can accept the coverage gap as being less than $c$. In other words, with probability $\beta$, the closeness criterion is satisfied with $\lambda$.

While using Gaussian noise results in a PAC-style guarantee, one could instead add strictly positive noise via an exponential mechanism Dwork et al. (2014), where the noise $X\sim\text{exp}(\frac{\epsilon}{2\Delta h})$ is selected to satisfy $\epsilon$-DP, i.e., $(\epsilon,0)$-DP. This would result in an overestimate of the actual coverage gap. If the overestimate satisfies the closeness criterion, then the server would assert that the exact coverage gap also satisfies the closeness criterion–thus restoring the strict (non-PAC) guarantee in FedCF.

## Appendix G FedCF for Auditing

Auditing tools are vital for regulatory bodies to ensure ML models comply with fairness and safety standards (Maneriker et al., 2023). In this regard, we present how FedCF can be used to determine if a federated conformal predictor is fair according to the regulator’s specification of fairness and closeness criterion, $c$ (U.S. Equal Employment Opportunity Commission, 1979; New York City Council, 2021; 2023; European Parliament and Council of the European Union, 2024).

To assess compliance, FedCF can use the global threshold ($\lambda$) values used by the previously trained conformal-predictor and provide it to each client. Then, the client should send the sufficient values calculated via Algorithm [4](https://arxiv.org/html/2509.22907v1#alg4) (or Algorithm [5](https://arxiv.org/html/2509.22907v1#alg5)) to compute the federated coverage gap. The server would aggregate these values using Algorithm [6](https://arxiv.org/html/2509.22907v1#alg6). If the calculated coverage gap is below $c$, then the server can assert that the conformal predictor is fair.

Our auditing approach does not require all clients to provide data for auditing. As discussed in Section [3.1](https://arxiv.org/html/2509.22907v1#S3.SS1), our guarantees hold assuming that the test-point, $(\bm{x}_{\text{test}},y_{\text{test}})\sim\sum_{k=1}^{K}\gamma_{k}P_{k}$, is sampled from a mixture of client distributions where $\gamma_{k}$ is the probability the test point is sampled from $P_{k}$, or equivilantly is exchangeable with data from client $k$. Thus, if a subset of clients used to train the original federated conformal predictor provides auditing data, then the audit guarantees will hold assuming that $(\bm{x}_{\text{test}},y_{\text{test}})$ are sampled from a mixture consisting of the subset of clients used for auditing. This result allows clients to independently decide if they would like to submit data for auditing.

The auditing tool provided by FedCF can also be used to ascertain the marginal fairness with respect to each client. Using the auditing procedure described above with data from one client, FedCF can determine if the global, federated conformal predictor maintains fairness with respect to data from a single client. If the computed coverage gap is less than $c$, then the fairness guarantees hold with regard to $(\bm{x}_{\text{test}},y_{\text{test}})\sim P_{k}$, i.e., the client’s marginal distribution.

## Appendix H More Results

Here, we provide additional results for the ACS and Pokec-{n,z} datasets. Recall, in each figure, we use a solid line to represent the average efficiency of the base federated conformal predictors across different thresholds and a dashed line to represent the corresponding average worst-case fairness disparity. The bar plot shows the efficiency and worst-case fairness disparity using FedCF, while the dots indicate the desired fairness disparity. We report the average base performance for clarity and readability

### H.1 Impact of Data Heterogeneity on ACSEducation: US vs Continental US

Figure: (a) Communication Efficient.
Refer to caption: x5.png

Figure: (a) Communication Efficient.
Refer to caption: x9.png

Figure: (a) Communication Efficient.
Refer to caption: x13.png

Figure: (a) Communication Efficient.
Refer to caption: x17.png

### H.2 Impact of different sensitive attributes for Pokec-{n,z}

Figure: (a) Communication Efficient.
Refer to caption: x21.png

Figure: (a) Communication Efficient.
Refer to caption: x25.png

Figure: (a) Communication Efficient.
Refer to caption: x29.png

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. How does the method handle data heterogeneity in realistic federated environments where the exchangeability assumption may not hold?
 
2. Can you provide a detailed analysis of communication costs and scalability when the number of clients and sensitive attributes increases significantly?
 
3. How does FedCF compare against other existing federated fairness approaches in terms of both fairness guarantees and computational efficiency?
soundness: 2
strengths: 1. Fair federated learning is an important and timely research direction given the increasing deployment of ML systems in sensitive domains.
 
2. The experimental results preliminarily demonstrate that the proposed method can control fairness disparities within specified bounds.
summary: The paper introduces FedCF, a framework that brings conformal fairness into federated learning by using coverage decomposition along with two communication protocols. Its main contribution is in adapting and integrating existing conformal-fairness methods for use in federated settings, while offering relatively limited novel algorithmic advances.
weaknesses: 1. The work primarily combines existing methods without substantial algorithmic innovation. While the extension of conformal fairness to federated settings is reasonable, the approach is relatively straightforward and lacks deeper theoretical understanding.
 
2. The experimental setup is quite far from a realistic federated setting. Since the datasets are split artificially rather than coming from natural sources, the evaluation may fail to reflect the true data heterogeneity that is central to federated learning.
 
3. The exchangeability assumption across clients creates tension with federated learning principles. Since federated learning is specifically designed to handle heterogeneous, non-IID data distributions, this assumption potentially undermines the method's applicability in practice.
 
4. Communication costs scale unfavorably with the number of sensitive attributes, particularly for the privacy-preserving variant. This scalability concern may limit practical deployment in settings with multiple fairness considerations.
 
5. The evaluation lacks comparison with alternative federated fairness approaches, making it difficult to assess relative performance. Additionally, the efficiency degradation observed with fairness constraints, especially using interval bounds, triggers concerns about practical utility.

---

confidence: 3
contribution: 3
initial_rating: 4
presentation: 3
questions: See Weaknesses
soundness: 3
strengths: 1. Overall, the paper is easy to read, and the idea is clear.

2. The evaluation of the models is reasonable, and the choice of experiments is diverse (but see Weaknesses).
summary: In this paper, the authors introduce the Federated Conformal Fairness (FedCF) approach, which extends the Conformal Fairness framework to a federated setting. The paper introduces two communication protocols that allow for a balance between communication overhead and privacy.
Authors conduct experiments on data from different domains, namely tabular, graph, and image tasks, and demonstrate that FedCF can control fairness disparities with acceptable trade-offs in set size.
weaknesses: Some of the points below are not necessary weaknesses, but rather questions that I did not understand during review. Can the authors kindly address them?

1. In experiments, only datasets with a relatively small number of clients are used (at most 51 [line 313]). In practice, however, there could be millions of clients. Even if the performance of the proposed framework is reasonable for the moderate number of clients, it could potentially degrade with K. I think an experiment on a dataset with a large number of clients (e.g., Stack Overflow) can resolve this issue.

2. Another practical challenge for federated learning is partial participation, when clients can be unresponsive from one communication round to another. However, the algorithm appears not to consider this situation. Will this situation create any challenges for the framework? Could this lead to bias?

3. As an additional limitation of experiments, datasets were partitioned to create clients rather than collected in a native FL way. Therefore, the evaluation lacks real-world heterogeneity.

4. This is rather a question. Currently, the approach tunes a single global $\ lambda$ for all clients, which may be inefficient given the real-world heterogeneity among clients. Can one incorporate multiple thresholds (per client or per group of clients) into the framework?

5. In practice, new clients can join the distributed system with their new local datasets. How can the FedCF adopt them?

---

confidence: 5
contribution: 2
initial_rating: 4
presentation: 3
questions: - Descent-based CF optimization, descent or ascent? You are from a very small $\lambda_0$? and $b_{t+1}$ should be positive. Then Lines 10 and 14 is a gradient ascent with momentum.
- Line 8 of Algorithm 1, do you need to return $\lambda_{opt}$ here? If not, $\Delta \lambda$ may be negative. Are there some typos in Line 11 of Algorithm 1 to ensure $\Delta \lambda$ not to be negative.
- I did not understand the dots or dotted line in Figure 1.
- The efficiency is bad compared with baseline.
soundness: 2
strengths: - The authors introduce a descent-based conformal fairness optimization to solve fair federated learning problems. 
- The authors provide a criterion to update learning rate in algorithm.
- The writing is good.
summary: This paper explore fair federated learning by conformal prediction, which is an extension of conformal fairness to the federated learning. They audit a federated model for fairness by analyzing the fairness-related gaps for different demographic groups. Numerical experiments is rich.
weaknesses: - There may be some mistakes in the core algorithm--descent based CF optimization (see questions).
- Numerical results are not good enough and the efficiency (the average prediction set size is large).
- This paper is an intersection of conformal federated learning and conformal  fairness algorithms?

---

confidence: 4
contribution: 2
initial_rating: 2
presentation: 2
questions: Questions:

1)	How tight is the bound in Thm 3.1 (experimental or theoretical)?

2)	How does model performance decrease with reducing fairness disparity?  How does this achieved performance compare to what is optimally achievable either in a centralized or federated setting? 

3)	While this paper focuses on its extension of the CF framework in [1], I was also curious about how it differed from the Federated Conformal Prediction framework in [2]?  

Additional Remarks:

1)	I thought the writing was a bit disorganized, since I felt I had to hunt through the paper to understand how FedCF enforces fairness across the clients.  The paper might benefit from some reorganization in the introduction and background sections in a way that builds up more systematically to the FedCF algorithm.

2)	The paper needs to address the model performance lost when the clients use the prediction set threshold determined by the server.   

3)	The predict set threshold is used by all clients.  I think it might be useful to examine whether the set thresholds should be client specific.  I suspect this can be one way of recovering model performance lost by having all clients use the same threshold.

References:

[1] Vadlamani, et al. “A generic framework for conformal fairness”, ICLR 2025

[2] Lu, et al., ”Federated conformal predictors for distributed uncertainty quantification”, ICML 2023
soundness: 3
strengths: + The proposed extension of conformal fairness to the federated setting is interesting and timely.  

+ Use of gradient search for coverage parameter, lambda, is an improvement over what was done in the original CF paper [1].
summary: This paper extends the Conformal Fairness (CF) framework [1] to federated learning (FL).  The paper suggests the framework provides a way to “audit” the fairness of FL models.  The extension relies on bounding the coverage of the conformal prediction set as a sum of statistics generated by the clients.  The server does a gradient search for the parameter, lambda, (size of the prediction set) that minimizes the squared error between the model’s coverage gap and a desired closeness level (c).  This threshold is then used by all clients in making their predictions.  The FedCF extension is evaluated on 4 datasets using APS, DAPS, and RPAS conformity measures.  Experimental results verify that FedCF can tradeoff fairness disparity against prediction set size in a manner that is plausible for use in auditing the fairness of FL models.
weaknesses: -	The bound on the coverage gap in Thm 3.1 is essential for the paper’s federated extension, but there are no results (experimental or theoretical) estimating how tight the bound is.  One would always expect the bounds obtained in a distributed setting to be worse than those that could be obtained using all the available information.  It is important to know how much one loses in estimating the coverage gap in this manner.

-	The paper is missing any meaningful discussion of model performance.  Based on my reading of the paper, FedCF is a post-processing approach to achieving fairness in FL in which all clients send statistics to the server from which the coverage threshold, lambda, is selected and that threshold is then used by all clients.  Essentially, we achieve fairness by assigning positive outcomes to less qualified individuals, until the target for fairness disparity has been achieved.  This comes at a cost of reducing the model’s performance (accuracy, f-score, whatever) on the entire population.  So the paper’s results and the “audit” are of limited value if one can’t assess how much performance is lost in achieving the fairness objective.   Moreover, it should be possible to estimate what the “optimal” performance would be for a given lambda.  It would be good to see how FedCF performance fairs with respect to this optimal cost.


Decision: Reject