Paper deep dive
Efficient Federated Conformal Prediction with Group-Conditional Guarantees
Haifeng Wen, Osvaldo Simeone, Hong Xing
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 3/22/2026, 5:06:14 AM
Summary
The paper introduces Group-Conditional Federated Conformal Prediction (GC-FCP), a novel protocol for federated learning that provides group-conditional coverage guarantees. By utilizing group-stratified T-Digest coresets, GC-FCP enables efficient, privacy-preserving calibration across heterogeneous clients with overlapping data groups, significantly reducing communication and computational overhead compared to centralized baselines.
Entities (5)
Relation Signals (3)
GC-FCP → provides → Group-conditional coverage
confidence 100% · GC-FCP, a novel protocol that provides group-conditional coverage guarantees.
GC-FCP → utilizes → T-Digest
confidence 100% · GC-FCP, an efficient federated protocol that accelerates communication and computation by compressing group-stratified calibration scores into mergeable T-Digest coresets.
GC-FCP → extends → CondCP
confidence 95% · we propose a communication- and computation-efficient federated extension of CondCP
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Deploying trustworthy AI systems requires principled uncertainty quantification. Conformal prediction (CP) is a widely used framework for constructing prediction sets with distribution-free coverage guarantees. In many practical settings, including healthcare, finance, and mobile sensing, the calibration data required for CP are distributed across multiple clients, each with its own local data distribution. In this federated setting, data can often be partitioned into, potentially overlapping, groups, which may reflect client-specific strata or cross-cutting attributes such as demographic or semantic categories. We propose group-conditional federated conformal prediction (GC-FCP), a novel protocol that provides group-conditional coverage guarantees. GC-FCP constructs mergeable, group-stratified coresets from local calibration scores, enabling clients to communicate compact weighted summaries that support efficient aggregation and calibration at the server. Experiments on synthetic and real-world datasets validate the performance of GC-FCP compared to centralized calibration baselines.
Tags
Links
- Source: https://arxiv.org/abs/2603.14198v2
- Canonical: https://arxiv.org/abs/2603.14198v2
Trouble viewing inline? Open PDF directly →
Full Text
81,046 characters extracted from source content.
Expand or collapse full text
Efficient Federated Conformal Prediction with Group-Conditional Guarantees Haifeng Wen IoT Thrust The Hong Kong University of Science and Technology (Guangzhou) Guangzhou, China Osvaldo Simeone Institute for Intelligent Networked Systems (INSI) Northeastern University London London, UK Hong Xing IoT Thrust The Hong Kong University of Science and Technology (Guangzhou) Guangzhou, China Department of ECE The Hong Kong University of Science and Technology HK SAR Abstract Deploying trustworthy AI systems requires principled uncertainty quantification. Conformal prediction (CP) is a widely used framework for constructing prediction sets with distribution-free coverage guarantees. In many practical settings, including healthcare, finance, and mobile sensing, the calibration data required for CP are distributed across multiple clients, each with its own local data distribution. In this federated setting, data can often be partitioned into, potentially overlapping, groups, which may reflect client-specific strata or cross-cutting attributes such as demographic or semantic categories. We propose group-conditional federated conformal prediction (GC-FCP), a novel protocol that provides group-conditional coverage guarantees. GC-FCP constructs mergeable, group-stratified coresets from local calibration scores, enabling clients to communicate compact weighted summaries that support efficient aggregation and calibration at the server. Experiments on synthetic and real-world datasets validate the performance of GC-FCP compared to centralized calibration baselines. 1 Introduction Figure 1: Left: In a federated system with heterogeneous clients, each client k holds local calibration data kD_k and communicates over a bandwidth-limited channel to a central server. The server aggregates these summaries to perform conformal calibration (CP) and outputs a set-valued predictor (⋅∣)C(· ). Right: GC-FCP targets group-conditional coverage for potentially overlapping groups =G1,G2,G3G=\G_1,G_2,G_3\, ensuring the inequality ℙ(Y∈(X∣)∣X∈G)≥1−αP(Y (X ) X∈ G)≥ 1-α for all groups G∈G , whereas methods that only guarantee marginal coverage ℙ(Y∈(X∣))≥1−αP(Y (X ))≥ 1-α, such as FCP [lu2023federated], may still under-cover within specific groups. Deploying trustworthy AI systems critically depends on uncertainty quantification to enable reliability control at deployment time. Given a pretrained model, conformal prediction (CP) post-processes the model’s outputs to construct prediction sets with finite-sample, distribution-free coverage guarantees. The calibration of the prediction set is carried out offline by leveraging held-out calibration data [vovk2005algorithmic, angelopoulos2021gentle, barber2021jackknifeplus, simeone2025uncertainty]. In many practical deployments, however, calibration data are inherently distributed and subject to privacy constraints, so that each client must retain its data on-site, e.g., hospitals, banks, or Internet-of-Things devices [mcmahan2017communication]. Federated conformal prediction (FCP) [lu2023federated] addresses the outlined distributed setting with the goal of preserving marginal coverage with respect to a distribution obtained by mixing local data distributions. Pursuing a similar marginal coverage guarantee, humbert2023one and humbert2024marginal proposed one-shot FCP schemes based on a quantile-of-quantiles estimator. Beyond calibration targeting the mixture distribution, FCP-Pro [li2025fcp] and personalized FCP [min2025personalized] address the heterogeneity of local data distributions by training additional models during the calibration process, providing marginal coverage on local distributions or on the distribution of a new client. To address robustness, kang2024certifiably studied Byzantine clients that may report arbitrary statistics. Considering more general connectivity constraints underlying communications, decentralized calibration via message passing over arbitrary graphs was proposed by [wen2025distributed], and distributed remote calibration protocols were studied in [zhu2025conformal] for wireless sensor networks. The state of the art on federated calibration summarized above did not target group-conditional coverage guarantees. In federated settings, data can often be partitioned into, potentially overlapping, groups, which may reflect client-specific strata or cross-cutting attributes such as demographic or semantic categories (see Fig. 1). For centralized settings, Mondrian CP [vovk2003mondrian] addresses group-conditional coverage over disjoint groups of covariates, while CondCP [gibbs2023conformal] allows for overlapping groups by reframing conditional coverage as simultaneous coverage over a class of covariate shifts. Kandinsky CP [pmlr-v267-bairaktari25a] extended Mondrian CP and CondCP to groups that depend on both covariates and labels. Other related research directions for centralized scenarios include localized coverage guarantees [guan2023localized]; learning improved conformity scores to reduce conditional miscoverage [xie2024boosted]; as well as analyses of sample-conditional validity for split conformal methods [duchi2025sample]. All this prior art on group-conditional CP has focused on centralized settings. To address this knowledge gap, in this paper, we propose a communication- and computation-efficient federated extension of CondCP [gibbs2023conformal], namely group-conditional federated conformal prediction (GC-FCP), which enables efficient server-side prediction-set construction by communicating only compact summaries sketched from group-stratified local calibration scores, while preserving the information needed for group-conditional calibration. Unlike FedCF [srinivasan2025fedcf], GC-FCP does not treat different groups separately, seeking simultaneous coverage across all groups. The main contributions are summarized as follows: • We first propose centralized GC-FCP, an extension of CondCP [gibbs2023conformal] that achieves group-conditional coverage guarantees under the mixture of the local data distribution. • We develop GC-FCP, an efficient federated protocol that accelerates communication and computation by compressing group-stratified calibration scores into mergeable T-Digest [dunning2019computing] coresets. • We establish group-conditional coverage bounds for GC-FCP, making explicit how the coreset compression level affects the achieved coverage. • We validate the proposed methods on synthetic and real-world benchmarks, demonstrating that GC-FCP attains group-conditional reliability while substantially reducing computational overhead. 2 Problem Setting As illustrated in Fig. 1, we study a federated calibration setting that follows reference [lu2023federated]. Accordingly, we consider a network consisting of K clients that communicate with a central server. In this setup, each client k∈1,…,K≜[K]k∈\1,…,K\ [K] has access to a local calibration dataset k=(Xi,k,Yi,k)i=1nk,D_k= \(X_i,k,Y_i,k) \_i=1^n_k, with data points (Xi,k,Yi,k)(X_i,k,Y_i,k) drawn i.i.d. from a client-specific distribution PkP_k over ×X×Y. We define a global calibration dataset as the union =⋃k=1Kk,D= _k=1^KD_k, with n=∑k=1Knkn= _k=1^Kn_k. As in [lu2023federated], the goal is to calibrate a shared pre-trained model f:↦f:X through communication with the central server. Calibration is evaluated on test data (Xn+1,Yn+1)(X_n+1,Y_n+1) drawn from the mixture P=∑k=1KπkPk,P= _k=1^K _kP_k, (1) for some arbitrary and known mixture weights πk≥0 _k≥ 0 with ∑k=1Kπk=1 _k=1^K _k=1. In practice, the weights πkk=1K\ _k\_k=1^K dictate the relative relevance of the data of each client k for the calibration of model f. Calibration aims at obtaining a set predictor (⋅∣):→2.C(· ):X→ 2^Y. (2) using the distributed calibration data via clients-to-server communication. Prior work [lu2023federated] imposed the constraint that the prediction set (2) satisfies the marginal coverage condition ℙ(Yn+1∈(Xn+1∣))≥1−αP(Y_n+1 (X_n+1 ))≥ 1-α (3) with respect to the mixture distribution (1). In contrast, as explained next, we impose a more flexible conditional coverage condition based on grouping. Let ⊆2G 2^X be a finite collection of groups in the covariate space X and ⋃G∈= _G =X. Importantly, the groups are generally overlapping, i.e., there exist groups Gi,Gj∈G_i,G_j such that Gi⋂Gj≠∅G_i G_j≠ (see Fig. 1). Groups may or may not represent client-specific partitions. In fact, some groups G may correspond to data categories that are more representative of the distribution PkP_k of a given client k. However, it may also be that groups refer to categories that apply equally across all clients. We consider the set G to be arbitrary and given. Given a target mis-coverage level α∈(0,1)α∈(0,1), calibration aims to construct set prediction (⋅∣)C(· ) such that, for every group G∈G , the following group-conditional coverage requirement holds: ℙ(Yn+1∈(Xn+1∣)|Xn+1∈G)≥1−α,P (Y_n+1 (X_n+1 )\, |\,X_n+1∈ G )≥ 1-α, (4) where the probability in (4) is taken over the calibration data in D and the test data (Xn+1,Yn+1)(X_n+1,Y_n+1). For condition (4) to be meaningful, we assume that all groups G∈G satisfy the inequality ℙ(Xn+1∈G)>0P(X_n+1∈ G)>0 under the mixture distribution (1). Note that this does not require that the inequality ℙk(X∈G)>0P_k(X∈ G)>0 holds for every client k. Rather, it only requires that at least one component with probability πk>0 _k>0 places positive mass on the group G. If the groups G were disjoint, the conditional coverage requirement (4) could be obtained by combining FCP [lu2023federated] and Mondrian CP [vovk2003mondrian]. Accordingly, one applies the FCP protocol separately for each group G∈G . However, ensuring the conditions (4) become difficult when groups overlap, and we address this challenge in this paper. 3 Preliminaries To start, consider, for reference, a centralized split-conformal setting in which a server has access to i.i.d. calibration data (Xi,Yi)i=1n\(X_i,Y_i)\_i=1^n and a test covariate Xn+1X_n+1. In this section, we review CondCP [gibbs2023conformal], which addresses the problem of satisfying the constraints (4) in such a centralized setting. Let s:×↦ℝs:X×Y be a score function derived from a predictive model f, and define the calibration scores Si=s(Xi,Yi)S_i=s(X_i,Y_i) with i=1,…,ni=1,…,n. Furthermore, let ℓα(θ,S) _α(θ,S) denote the pinball loss at level 1−α1-α: ℓα(θ,S)=(1−α)(S−θ),S≥θ,α(θ−S),S<θ. _α(θ,S)= cases(1-α)(S-θ),&S≥θ,\\ α(θ-S),&S<θ. cases (5) Given the set of groups G (possibly overlapping), define the group-membership map Φ:→0,1|| :X→\0,1\^|G| as Φ(x)=(x∈G)G∈0,1||, (x)= (1\x∈ G\ )_G ∈\0,1\^|G|, (6) which encodes membership of element x∈x belonging to each group of G as a binary indicator vector (where true=11\true\=1 and false=01\false\=0). Then, CondCP defines the set of functions ℱ=x↦β⊤Φ(x):β∈ℝ||,F_G= \x β (x):β ^|G| \, (7) which corresponds to arbitrary linear combinations for the group indicators. Specifically, for any input test score S∈ℝS , CondCP solves the augmented quantile regression problem: g^S=argming∈ℱ1n+1∑i=1nℓα(g(Xi),Si)+1n+1ℓα(g(Xn+1),S). g_S= _g _G\ \ 1n+1 _i=1^n _α (g(X_i),S_i ) .\\ .+ 1n+1 _α (g(X_n+1),S ) \. (8) Note that the solution g^S g_S is a function in class (7). By the properties of the pinball loss, the solution g^S g_S represents a covariate (Xn+1X_n+1)-dependent version of the (1−α)(1-α)-empirical quantile of the augmented calibration scores Sii=1n∪S\S_i\_i=1^n∪\S\ [gibbs2023conformal]. The prediction set is then defined as the set of all labels y∈y whose score s(Xn+1,y)s(X_n+1,y) is no larger than the corresponding empirical quantile g^s(Xn+1,y)(Xn+1) g_s(X_n+1,y)(X_n+1), i.e., (Xn+1∣)=y∈:s(Xn+1,y)≤g^s(Xn+1,y)(Xn+1).C(X_n+1 )\\ = \y :s(X_n+1,y)≤ g_\,s(X_n+1,y)(X_n+1) \. (9) The prediction set (9) is constructed by addressing an equivalent formulation of the convex problem (8) via dual methods (see Appendix D for details). Under the assumption of i.i.d. calibration and test data, the set (Xn+1∣)C(X_n+1 ) in (9) satisfies group-conditional coverage (4). Communication overhead: Solving problem (8) at the server would require collecting all calibration scores and their group-membership features, yielding a communication overhead (n)O(n). Computational overhead: Solving problem (8) requires computational complexity of order (n3/2||2)O(n^3/2|G|^2) using standard convex problem solvers [renegar1988newton, nesterov1994interior]. Table 1: Communication load and computational complexity. Method Comm. Comp. CondCP & Centralized GC-FCP (n)O(n) (n3/2||2)O (n^3/2|G|^2 ) GC-FCP (Kδ)O(Kδ) (δ3/2||2)O (δ^3/2|G|^2 ) 4 Group-Conditional Federated Conformal Prediction (GC-FCP) This section introduces group-conditional federated conformal prediction (GC-FCP), a federated calibration procedure designed to achieve group-conditional coverage (4) over a prescribed, generally overlapping, collection of groups G under any mixture distribution (1). In GC-FCP, each client computes calibration scores locally and communicates to the server only a compact, group-stratified summary, while the server efficiently constructs the CP set for each test point without accessing raw client-level calibration scores. 4.1 Federated Augmented Quantile Regression To start, consider an ideal setting in which the entire calibration dataset D, which includes the datasets kD_k from all clients k∈[K]k∈[K], is available at the central server. Assume also no computational limitations at the server. Even in this simplified setup, as explained in the previous section, CondCP would fail to guarantee the conditional coverage requirements (4), since the data points in dataset D are not i.i.d. with respect to the mixture distribution (1). We address this challenge in this section by proposing centralized GC-FCP, a centralized calibration scheme that guarantees the desired condition (4). As in Section 3, let s:×↦ℝs:X×Y be a score function derived from the shared predictive model f. We denote the calibration scores at client k as Si,k=s(Xi,k,Yi,k)S_i,k=s(X_i,k,Y_i,k) with i∈1,…,nk\ i∈\1,…,n_k\ and k∈[K]k∈[K]. Furthermore, given a test point (Xn+1,Yn+1)∼P(X_n+1,Y_n+1) , we denote its score by Sn+1=s(Xn+1,Yn+1)S_n+1=s(X_n+1,Y_n+1). For a test covariate Xn+1X_n+1 and an input score value S∈ℝS , centralized GC-FCP solves the following federated augmented quantile regression estimator as a generalization of the CondCP problem (8): g^S=argming∈ℱ∑k=1Kπknk+1(∑i=1nkℓα(g(Xi,k),Si,k)+ℓα(g(Xn+1),S)), g_S= g _G *argmin _k=1^K _kn_k+1 ( _i=1^n_k _α(g(X_i,k),S_i,k)\\ + _α(g(X_n+1),S) ), (10) where the function set ℱF_G is defined in (7). The objective in problem (10) incorporates the scores of all K clients, with each k-th term weighted by the factor πk/(nk+1) _k/(n_k+1), thus matching the structure of the target mixture distribution (1). Using this definition, centralized GC-FCP obtains the prediction set as in (9). Theorem 4.1 (Group-conditional coverage for centralized GC-FCP). For every group G∈G , the set (9) with the empirical quantile (10) produced by centralized GC-FCP satisfies the conditional coverage condition (4). Proof: See Appendix A.1. As summarized in Table 1, the centralized GC-FCP shares the same communication and computational overheads as CondCP. 4.2 Group-Conditional Federated Conformal Prediction The previous subsection focused on a centralized version of GC-FCP, which solves problem (10) using the calibration scores pooled from all clients. To mitigate the communication and computational overhead associated with this approach, we now introduce GC-FCP, a novel distributed protocol that replaces the full calibration dataset with small group-stratified coresets. As summarized in Table 1, this protocol reduces the communication load and enables a more efficient server-side optimization (whenever n≫δn δ). GC-FCP starts by applying a coreset construction based on T-Digest [dunning2019computing], which is a sketching algorithm for computing approximations of quantiles, and is elaborated in the sequel. The sketches produced by T-Digest are then used to solve the optimization problem (10) at the central server. While T-Digest was also used by FCP [lu2023federated], GC-FCP must additionally account for the structure of the groups in the set G, producing stratified structures (see Fig. 2). 4.2.1 T-Digest Let (Ri,wi)i=1ℓ\(R_i,w_i)\_i=1 be weighted real-valued samples with Ri∈ℝR_i and weights wi>0w_i>0, and define the total weight as W=∑i=1ℓwiW= _i=1 w_i. The associated weighted empirical cumulative distribution function (CDF) is F(t)=1W∑i=1ℓwi 1Ri≤t,F(t)= 1W _i=1 w_i\,1\R_i≤ t\, with generalized empirical quantile function Q(u)=inft:F(t)≥uQ(u)= \t:F(t)≥ u\ for u∈[0,1]u∈[0,1]. T-Digest: A T-Digest [dunning2019computing] produces an ordered collection of m<ℓm< clusters ℛc⊆1,…,ℓR_c \1,…, \, i.e., if c1<c2c_1<c_2, Ri≤RjR_i≤ R_j for any i∈ℛc1i _c_1 and j∈ℛc2j _c_2. Cluster ℛcR_c is described by a cluster representative R¯c R_c and an aggregate weight WcW_c. Each cluster ℛcR_c includes a subset of samples Rii=1ℓ\R_i\_i=1 with total weight Wc=∑i∈ℛcwi,W_c= _i _cw_i, and the weighted cluster means R¯c=1Wc∑i∈ℛcwiRi. R_c= 1W_c _i _cw_iR_i. In summary, T-Digest returns the weights and the cluster means as =(R¯c,Wc)c=1m. TD= \( R_c,W_c) \_c=1^m. (11) It is worth noting that T-Digest enforces the ordering R¯1≤R¯2≤⋯≤R¯m R_1≤ R_2≤…≤ R_m, producing ordered cluster means. To this end, it orders the original set Rii=1ℓ\R_i\_i=1 such that we have R1≤R2≤⋯≤RℓR_1≤ R_2≤…≤ R_ . Clusters are then constructed greedily as follows. To elaborate, let Vc=∑i=1cWiV_c= _i=1^cW_i with V0=0V_0=0, and define the empirical left and right quantile boundaries of cluster c∈1,…,mc∈\1,…,m\ as qcL=Vc−1W and qcR=VcW.q_c^L= V_c-1W\ and \ q_c^R= V_cW. (12) Samples R1,R2,…,RℓR_1,R_2,…,R_ are aggregated in an increasing order into the current cluster ℛcR_c as long as adding the next sample preserves the constraint r(qcR)−r(qcL)≤1,c=1,…,m.r (q_c^R )-r (q_c^L )≤ 1, c=1,…,m. (13) with scale function r(q)=δ2πarcsin(2q−1).r(q)= δ2π (2q-1). (14) for some parameter δ>0δ>0 that controls the level of compression. Intuitively, the condition (13) enforces finer resolution near the tails of the empirical distribution of the scalars Rii=1ℓ\R_i\_i=1 , while permitting larger clusters near the median. By this construction, the number of retained clusters scales as m=Θ(δ)m= (δ) [dunning2019computing]. From the digest =(R¯c,Wc)c=1m TD= \( R_c,W_c) \_c=1^m, the approximate quantile function for u∈[0,1]u∈[0,1] is given by Q^(u)=inft:F^(t)≥u, Q(u)= \t: F(t)≥ u\, (15) where F^(t)=1W∑c=1mWc 1R¯c≤t. F(t)\ =\ 1W _c=1^mW_c\,1\ R_c≤ t\. (16) is an estimate of the empirical CDF F(t)F(t). The quality of this estimate will be analyzed in Section 5. Merging T-Digests: A key property of T-Digest is that digests can be merged and then re-compressed such that the number of retained clusters remains Θ(δ) (δ) [dunning2019computing]. Let (j)=(R¯c(j),Wc(j))c=1mj TD^(j)=\( R^(j)_c,W^(j)_c)\_c=1^m_j be digests obtained from disjoint datasets indexed by j=1,…,Jj=1,…,J. To merge them, one applies the same procedure discussed above to the pooled samples ⋃j=1J(j) _j=1^J TD^(j). We denote the merged digest as Merge((1),…,(J))Merge( TD^(1),…, TD^(J)). 4.2.2 GC-FCP Figure 2: Illustration of the atom partitions applied by GC-FCP. Given the set of overlapping groups =G1,G2,G3G=\G_1,G_2,G_3\, the resulting 77 non-empty atoms =A1,…,A7A=\A_1,…,A_7\ are shown on the right, together with the corresponding group-membership vector (6). In order to address the group-conditional constraint (4), GC-FCP first stratifies the data at the clients into disjoint atoms based on unique group membership patterns. Independent T-Digests are then constructed per atom, and used at the server as coresets to approximate the solution of the quantile regression problem (10). Atoms construction: As illustrated in Fig. 2, GC-FCP first partitions the input domain X into a collection =AA∈A=\A\_A of atoms, which are defined as ⋃A∈A= _A A=X and A⋂A′=∅A A = , for any pair A,A′∈A,A . The collection A corresponds to the smallest-cardinality partition of the set X such that all the sets G can be recovered via union operations on its atoms. Formally, for each subset of groups, ⊆S , define A()=(⋂G∈G)⋂(⋂G∈∖Gc)A(S)= ( _G G ) ( _G G^c ) (17) as the intersection of all groups in subset S and the complement of all groups not in subset S. The construction =A()⊆A=\A(S)\_S yields the collection of atoms [kallenberg2002foundations]. By construction, each atom A corresponds to all points x∈x with the same membership vector Φ(x) (x). Accordingly, for any x∈Ax∈ A, we can write ΦA=Φ(x) _A= (x). An example is illustrated in Fig. 2. Local-score partition and digest: We now partition the set of local scores at client k∈[K]k∈[K] into |||A| subsets k,AD_k,A, one per atom A as k,A=s(X,Y):X∈A,(X,Y)∈k.D_k,A= \s(X,Y):X∈ A,\ (X,Y) _k \. (18) Each client k∈[K]k∈[K], for each atom A, builds a separate digest k,A TD_k,A using the scores k,AD_k,A and equal weights w=πk/(nk+1)w= _k/(n_k+1). Following Section 4.2, the resulting digest k,A TD_k,A consists of a set of means and weights with mk,A=Θ(δ)m_k,A= (δ) clusters k,A=(S¯k,A,c,Wk,A,c)c=1mk,A, TD_k,A= \ ( S_k,A,c,\,W_k,A,c ) \_c=1^m_k,A, (19) where S¯k,A,c=1Wk,A,c∑i∈k,A,cπknk+1Si S_k,A,c= 1W_k,A,c _i _k,A,c _kn_k+1S_i is the weighted mean of the scores in cluster k,A,cS_k,A,c, and Wk,A,c=|k,A,c|πknk+1W_k,A,c=|S_k,A,c| _kn_k+1 is the aggregated weight. Next, client k∈[K]k∈[K] transmits the digest k,A TD_k,A along with all A∈A to the server. For each atom A∈A , the server merges the received digests k,Ak=1K\ TD_k,A\_k=1^K to obtain a global digest A TD_A =Merge(1,A,…,K,A) =Merge ( TD_1,A,…, TD_K,A ) (20) =(S¯A,c,WA,c)c=1mA, = \ ( S_A,c,\,W_A,c ) \_c=1^m_A, with mA=Θ(δ)m_A= (δ) clusters, where Merge(⋅)Merge(·) denotes the merge operation on k,Ak=1K\ TD_k,A\_k=1^K. As a result, the union over the digests of all atoms yields the final coreset: ~=(A,S¯,W):(S¯,W)∈A,A∈ D= \ (A, S,W ): ( S,\,W )∈ TD_A,\ A \ (21) with size |~|=Θ(||δ)| D|= (|A|δ). Note that each entry (A,S¯,W)(A, S,W) of the coreset includes the identifier of the atom A, the mean score S¯ S, and the corresponding weight W. Set construction: Given a test score S, GC-FCP solves problem (10) using the coreset ~ D instead of the original pooled data D, i.e., β~(S)=argminβ∈ℝ||∑(A,S¯,W)∈~Wℓα(β⊤ΦA,S¯)+(∑k=1Kπknk+1)ℓα(β⊤Φ(Xn+1),S). β(S)= β ^|G| *argmin _(A, S,W)∈ DW\, _α (β _A,\, S )\\ + ( _k=1^K _kn_k+1 ) _α (β (X_n+1),\,S ). (22) Finally, the prediction set is constructed as (Xn+1∣~)=y∈:s(Xn+1,y)≤g~s(Xn+1,y)(Xn+1).C(X_n+1 D)\\ = \y :s(X_n+1,y)≤ g_s(X_n+1,y)(X_n+1) \. (23) where g~S(x)=β~(S)⊤Φ(x) g_S(x)= β(S) (x). The proposed GC-FCP is summarized in Algorithm 1. Communication overhead: Solving problem (22) at the server requires collecting all digests k,A\ TD_k,A\, yielding a total communication load of GC-FCP of order (Kδ)O(Kδ), instead of the overhead of order (n)O(n) of CondCP and centralized GC-FCP. Computational overhead: Solving the dual of problem (22) requires computational complexity of order (|~|3/2||2)=(δ3/2||2)O(| D|^3/2|G|^2)=O(δ^3/2|G|^2) by standard convex problem solvers [renegar1988newton, nesterov1994interior], instead of the order (n3/2||2)O(n^3/2|G|^2) of CondCP and centralized GC-FCP. Algorithm 1 GC-FCP Input: Clients’ calibration sets kk=1K\D_k\_k=1^K; groups G; score s(⋅,⋅)s(·,·); mis-coverage level α; mixture weights πk _k; T-Digest compression parameter δ. ⊳ Client side (in parallel): for device k∈1,…,Kk∈\1,…,K\ do Construct T-Digest k,A TD_k,A for each atom A∈A using k,AD_k,A. Transmit T-Digests k,AA∈\ TD_k,A\_A to the central server. end for ⊳ Server side: Merge k,Ak∈[K]\ TD_k,A\_k∈[K] for each atom A∈A via (20). Solve (22) and compute the prediction set (23). Output: (⋅∣~)C(· D) 5 Coverage Guarantees of GC-FCP The key property of GC-FCP is its ability to provide group-conditional coverage guarantees (4) for the prediction set. Deriving finite-sample group-conditional guarantees for GC-FCP is technically challenging, since one must simultaneously account for the non-exchangeability of the samples in the coreset and for the approximation error introduced by sketching via the local digest. To this end, we first analyze the quantile estimation accuracy of T-Digest, and then provide a group-conditional coverage bound for GC-FCP. 5.1 Quantile Accuracy of T-Digest We start by deriving a relationship between the compression parameter δ used in the scale function (14) by T-Digest for compression, which dictates the number of clusters m=Θ(δ)m= (δ), and the accuracy of the approximate quantile (15). Lemma 5.1 (Uniform bound of T-Digest). Defining as F(t)F(t) the true CDF of original samples, the CDF estimate (16) produced by T-Digest satisfies the uniform accuracy bound supt∈ℝ|F(t)−F^(t)|≤sin(πδ)≤πδ. _t |F(t)- F(t) |≤ ( πδ )≤ πδ. (24) Moreover, for all u∈[0,1]u∈[0,1], the quantile estimate 16 satisfies the inequality |F(Q^(u))−u|≤π/δ.|F( Q(u))-u|≤π / . -1.2ptδ. Proof. See Appendix B.1. ∎ 5.2 Group-Conditional Coverage Guarantees of GC-FCP Based on properties of T-Digest presented in Lemma 5.1, we can now prove the group-conditional coverage guarantees of GC-FCP. Theorem 5.1 (Group-conditional coverage guarantees for GC-FCP). For each group G∈G , the prediction set (Xn+1∣~)C(X_n+1 D) produced by GC-FCP satisfies the inequality ℙ(Yn+1∈(Xn+1∣~)∣Xn+1∈G)≥1−α−πδ.P(Y_n+1 (X_n+1 D) X_n+1∈ G)≥ 1-α- πδ. (25) Proof: See Appendix B.2. While Theorem 5.1 assumes that problems (22) are solved exactly, the next result accounts for suboptimality induced by numerically solving problem (22). An upper bound of the group-conditional coverage of GC-FCP can be found in Appendix C. 6 Experiments We evaluate GC-FCP on (i) a synthetic regression benchmark [romano2019cqr]; (i) CIFAR-10 image classification [krizhevsky2009learning]; and (i) PathMNIST medical image classification [medmnistv2]. Across all experiments, we compare the proposed scheme, GC-FCP, to the following benchmarks: (i) vanilla centralized CP, which provides the marginal guarantee (3); (i) FedCP [lu2023federated], which also satisfies (3); (i) centralized CondCP [gibbs2023conformal]; and (iv) centralized GC-FCP, which is described in Section 4.1. CondCP and centralized GC-FCP are only evaluated on the small-scale synthetic dataset and CIFAR-10 due to their prohibitive computational complexity (see Table 1). Further comparisons with FedCF [srinivasan2025fedcf] and personalized FCP [min2025personalized] can be found in Appendix E.2. For each group G∈G , we estimate group-conditional coverage on a test set T as cov^(G)=1/|G|∑(x,y)∈Gy∈(x∣), cov(G)=1 / . -1.2pt|T_G| _(x,y) _G1 \y (x ) \, where G=(x,y)∈:x∈GT_G=\(x,y) :x∈ G\, and report the empirical coverage cov^(G) cov(G) for all groups G∈G . For classification, we also report the average prediction set size (1/||)∑(x,y)∈|(x∣)|(1/|T|) _(x,y) |C(x )|. Computational complexity is evaluated by the average wall-clock time required for each method to construct a prediction set on the same platform. 6.1 Synthetic Regression Figure 3: Visualization of prediction sets for the synthetic regression task for (a) centralized CP and FedCP [lu2023federated], as well as for (b) centralized CondCP, centralized GC-FCP, and GC-FCP. (c) Per-group miscoverage rate. For the synthetic regression task, we consider K=4K=4 clients with heterogeneous covariate distributions PX,kP_X,k given by truncated normal distributions on the interval [0,5][0,5] with mean μk=0.5+4(k−1)K−1 _k=0.5+ 4(k-1)K-1 and variance σk=0.5+0.1(k−1) _k=0.5+0.1(k-1). Following [romano2020classification], we generate responses as Yk∼Pois(sin2(X)+0.1)+0.03Xϵ1+25U<0.01ϵ2+(0,0.01k2),Y_k ( ^2(X)+0.1)+0.03X _1\\ +251\U<0.01\ _2+N(0,0.01k^2), (26) with independent variables ϵ1,ϵ2∼(0,1) _1, _2 (0,1) and U∼Unif([0,1])U ([0,1]). We train a centralized linear regression model f(⋅)f(·) on a separate training dataset generated in the same way, and use the score s(x,y)=|y−f(x)|s(x,y)=|y-f(x)|. Groups are given by overlapping intervals =[0,2],[1,3],[2,4],[3,5]G=\[0,2],[1,3],[2,4],[3,5]\. The miscoverage level α is set to α=0.1α=0.1. Other parameters are summarized in Table 3 in Appendix E.1. Fig. 3 (a)-(b) visualizes representative prediction sets, while Fig. 3 reports the mis-coverage rate across the four overlapping interval groups. Centralized CP and FedCP apply a single global threshold and therefore exhibit uneven group-wise miscoverage rates. In particular, some groups are under-covered (mis-coverage above α), reflecting shifts in the conditional score distribution across covariate regions. In contrast, CondCP, centralized GC-FCP, and GC-FCP yield substantially more uniform group-wise mis-coverage near the target level α across all groups (Fig. 3(c)) by adapting the threshold over the covariate space (Fig. 3(b)). 6.2 CIFAR-10 Experiments Table 2: Coverage, set size, and computational load comparisons on CIFAR-10 [krizhevsky2009learning]. Methods Marginal coverage Coverage (set size) Comp. speedup G1G_1 G2G_2 G3G_3 G4G_4 Centralized CP 0.901 0.879 ↓ (0.91) 0.855 ↓ (0.90) 0.906 (0.93) 0.936 (0.95) N/A Centralized CondCP 0.903 0.901 (0.96) 0.901 (0.98) 0.902 (0.94) 0.901 (0.91) 1× Centralized GC-FCP 0.906 0.903 (0.96) 0.903 (0.99) 0.905 (0.94) 0.905 (0.92) 1.01× FedCP 0.902 0.880 ↓ (0.92) 0.856 ↓ (0.90) 0.906 (0.93) 0.936 (0.95) N/A GC-FCP (δ=25δ=25) 0.911 0.896 ↓ (0.95) 0.887 ↓ (0.96) 0.919 (0.95) 0.931 (0.95) 34.36× GC-FCP (δ=250δ=250) 0.906 0.903 (0.96) 0.902 (0.98) 0.905 (0.94) 0.906 (0.92) 19.73× GC-FCP (δ=2500δ=2500) 0.906 0.903 (0.96) 0.903 (0.99) 0.905 (0.94) 0.905 (0.92) 3.96× We now adopt a pre-trained ResNet56 model f(⋅)f(·) for the CIFAR-10 image classification task with score function s(x,y)=1−[f(x)]ys(x,y)=1-[f(x)]_y, where y denotes the y-th entry of the softmax result [sadinle2019least]. We consider K=5K=5 clients with a non-i.i.d. label partition, so that each client holds 10/K10/K disjoint classes. We set uniform mixture weights πk=1/K _k=1/K, and total calibration size n=∑knk=5000n= _kn_k=5000. Groups are defined by overlapping predicted label classes y^(x)=argmaxy[f(x)]y y(x)= _y[f(x)]_y: G1=x:y^(x)∈0,1,2,3,G2=x:y^(x)∈2,3,4,5,G3=x:y^(x)∈4,5,6,7,and G4=x:y^(x)∈6,7,8,9.G_1=\x: y(x)∈\0,1,2,3\\,G_2=\x: y(x)∈\2,3,4,5\\,G_3=\x: y(x)∈\4,5,6,7\\,and G_4=\x: y(x)∈\6,7,8,9\\. We set the miscoverage level α=0.1α=0.1 and use a pre-trained ResNet56 to serve the model f(⋅)f(·) to construct the score function s(x,y)=1−[f(x)]ys(x,y)=1-[f(x)]_y [sadinle2019least]. The report results represent the average after 5050 Monte Carlo simulations, each with 50005000 test points. Table 2 reports marginal coverage, group-conditional coverage (with average set size in brackets), and computational speedup (“Comp. speedup”), with the latter being normalized with respect to the complexity of centralized CondCP. Centralized CP and FedCP attain the same marginal coverage near 0.90.9, but their group-conditional coverage varies substantially across groups (e.g., below 0.90.9 for groups G1G_1 and G2G_2), indicating that marginal calibration does not control errors uniformly across overlapping groups. Centralized CondCP and centralized GC-FCP achieve near-uniform group-conditional coverage across all groups, matching the intended behavior of augmented quantile calibration under grouping conditions. GC-FCP closely tracks the centralized group-conditional performance while substantially improving computational efficiency. The computational gains are pronounced: depending on δ, GC-FCP yields from 3.96×3.96× to 34.36×34.36× per-test-point speedup relative to centralized CondCP, illustrating the accuracy–efficiency trade-off governed by the digest compression parameter. The value of the compression parameter affects coverage. For instance, with aggressive compression (δ=25δ=25), some groups are slightly under-covered (e.g., G2G_2), in a manner consistent with Theorem 5.1. 6.3 Medical dataset experiments Finally, we evaluate GC-FCP on PathMNIST from MedMNIST (9 tissue classes) with images resized to 3×28×283× 28× 28 [medmnistv2]. We consider K=5K=5 clients, each holding samples from 22 disjoint classes, except the last client holds 11 class. We train a centralized CNN f(⋅)f(·) on the training split. We randomly shuffle the mixture validation and test data, split it into calibration and conformal test datasets equally, and allocate calibration samples to clients as in the CIFAR-10 experiments. Groups are defined by predicted-label classes: G1=x:y^(x)∈0,1,2,G2=x:y^(x)∈1,2,3,G3=x:y^(x)∈2,3,4,G4=x:y^(x)∈3,4,5,G5=x:y^(x)∈4,5,6,7,8.G_1=\x: y(x)∈\0,1,2\\,G_2=\x: y(x)∈\1,2,3\\,G_3=\x: y(x)∈\2,3,4\\,G_4=\x: y(x)∈\3,4,5\\,G_5=\x: y(x)∈\4,5,6,7,8\\. Other parameters remain the same as CIFAR-10 experiments. Table 4 in Appendix E.1 shows that Centralized CP and FedCP achieve marginal coverage near 0.90.9, but can deviate noticeably at the group level (e.g., lower coverage on G3G_3). GC-FCP with moderate compression (δ=250δ=250 or δ=2500δ=2500) attains group-conditional coverage close to the target for all groups, while maintaining small average set sizes (near one label on average). In contrast, overly aggressive compression (δ=25δ=25) degrades calibration. Overall, these results corroborate that GC-FCP achieves group-conditional reliability in heterogeneous federated classification tasks, with accuracy controlled by the digest compression parameter δ. 7 Conclusion We have introduced Group-Conditional Federated Conformal Prediction (GC-FCP), a principled framework for constructing prediction sets with group-conditional guarantees in heterogeneous federated settings. GC-FCP leverages T-Digest to compress stratified calibration scores into a small mergeable coreset. Under mild assumptions, we established group-conditional coverage guarantees for GC-FCP, and empirical results on synthetic regression and image classification benchmarks corroborated these findings while demonstrating substantial computational speedups. Future work includes extending the framework to richer conditional structures beyond finite group families, as well as investigating robustness to more complex settings such as decentralized calibration [wen2025distributed], adversarial behavior [kang2024certifiably], and online CP [angelopoulos2024online, gasparin2024conformal]. References Efficient Federated Conformal Prediction with Group-Conditional Guarantees (Supplementary Material) Appendix A Proof of Section 4 A.1 Proof of Theorem 4.1 Proof. First assume there are no ties, i.e., Si,k≠g^Sn+1(Xi,k)S_i,k≠ g_S_n+1(X_i,k) for all i∈[nk],k∈[K]i∈[n_k],\,k∈[K], and Sn+1≠g^Sn+1(Xn+1)S_n+1≠ g_S_n+1(X_n+1). The tie case is handled at the end of the proof. Recall that g(x)=β⊤Φ(x)g(x)=β (x) with β∈ℝ||β ^|G| and Φ(⋅) (·) defined in (6), then the optimal function g^Sn+1(⋅) g_S_n+1(·) solved by (10) reduces to a real-value vector given by β∗=argminβ∈ℝ||∑k=1K(πknk+1∑i=1nk+1ℓα(∑G∈βGXi,k∈G,Si,k)),β^*= β ^|G| * *argmin _k=1^K ( _kn_k+1 _i=1^n_k+1 _α ( _G _G1\X_i,k∈ G\,S_i,k ) ), (27) where we denote Snk+1,k=Sn+1S_n_k+1,k=S_n+1 for simplicity. Under the no-ties assumption, the first-order optimality condition implies that for every group G∈G , ∑k=1Kπknk+1∑i=1nk+1(Xi,k∈G(Si,k<θi,k∗−(1−α)))=0,∀G∈ _k=1^K _kn_k+1 _i=1^n_k+1 (1\X_i,k∈ G\ (1\S_i,k< _i,k^*\-(1-α) ) )=0, ∀ G (28) where θi,k∗=∑G∈βG∗Xi,k∈G _i,k^*= _G β^*_G1\X_i,k∈ G\. Let EkE_k be the event that (Xn+1,Yn+1)(X_n+1,Y_n+1) is drawn from PkP_k. Conditioned on EkE_k, the (nk+1)(n_k+1) scores Si,ki=1nk+1\S_i,k\_i=1^n_k+1 are exchangeable. Let ℰE be the event that, for every k∈[K]k∈[K], there exists a permutation σk _k such that (Sσk(1),k,…,Sσk(nk+1),k)=(s1,k,…,snk+1,k), (S_ _k(1),k,…,S_ _k(n_k+1),k )= (s_1,k,…,s_n_k+1,k ), (40) where (s1,k,…,snk+1,k)(s_1,k,…,s_n_k+1,k) denotes the realized values of (S1,k,…,Snk+1,k)(S_1,k,…,S_n_k+1,k). Then, we have, for all G∈G , ℙ(Yn+1∈(Xn+1∣)∣Xn+1∈G,ℰ) (Y_n+1 (X_n+1 ) X_n+1∈ G,E) (29) =ℙ(Sn+1≤θn+1∗,Xn+1∈G∣ℰ)ℙ(Xn+1∈G∣ℰ) = P(S_n+1≤θ^*_n+1,X_n+1∈ G )P(X_n+1∈ G ) =∑k=1Kπkℙ(Sn+1≤θn+1∗,Xn+1∈G∣ℰ,ℰk)∑k=1Kπkℙ(Xn+1∈G∣ℰ,ℰk) = _k=1^K _kP(S_n+1≤θ^*_n+1,X_n+1∈ G ,E_k) _k=1^K _kP(X_n+1∈ G ,E_k) =(a)∑k=1Kπknk+1∑i=1nk+1Si,k≤θi,k∗Xi,k∈G∑k=1Kπknk+1∑i=1nk+1Xi,k∈G (a)= _k=1^K _kn_k+1 _i=1^n_k+11\S_i,k≤θ^*_i,k\1\X_i,k∈ G\ _k=1^K _kn_k+1 _i=1^n_k+11\X_i,k∈ G\ =(b)(1−α)∑k=1Kπknk+1∑i=1nk+1Xi,k∈G∑k=1Kπknk+1∑i=1nk+1Xi,k∈G (b)= (1-α) _k=1^K _kn_k+1 _i=1^n_k+11\X_i,k∈ G\ _k=1^K _kn_k+1 _i=1^n_k+11\X_i,k∈ G\ =1−α, =1-α, where (a)(a) follows exchangeability on client k under the event EkE_k and (b)(b) follows the first-order condition. This result implies marginal coverage under G=G=X. If the assumption Si≠g^S(Xi)S_i≠ g_S(X_i) does not hold, we have ℙ(Yn+1∈(Xn+1∣)∣Xn+1∈G,ℰ)≥1−α.P(Y_n+1 (X_n+1 ) X_n+1∈ G,E)≥ 1-α. The proof technique is similar to [gibbs2023conformal] and Appendix B.2 and is omitted here. By the tower rule, we obtain the desired result. ∎ Appendix B Proofs for Section 5 B.1 Results on T-Digest This section provides additional results on T-Digest and proves Lemma 5.1. To begin, we state the following fact that holds in our digest construction described in Section 4.2. B.1.1 Important Lemmas Lemma B.1 (CDF error controlled by maximal cluster mass). Let (Ri,wi)i=1ℓ\(R_i,w_i)\_i=1 be weighted samples with total weight W and empirical CDF F. Let =(R¯c,Wc)c=1m TD=\( R_c,W_c)\_c=1^m be a digest with induced CDF F^(t)=1W∑c=1mWc 1R¯c≤t F(t)\ =\ 1W _c=1^mW_c\,1\ R_c≤ t\. Define the maximal normalized cluster mass ρmax=max1≤c≤mWcW. _ \ =\ _1≤ c≤ m W_cW. (30) Then, supt∈ℝ|F(t)−F^(t)|≤ρmax. _t |F(t)- F(t) |≤ _ . (31) Proof. Let ℛcc=1m\R_c\_c=1^m be the partition for the digest defined in Section 4.2, and define Lc=mini∈ℛcRiL_c= _i _cR_i and Uc=maxi∈ℛcRiU_c= _i _cR_i. Fix t∈ℝt and consider any cluster c. If t<Lct<L_c, then cluster c contributes zero to both F(t)F(t) and F^(t) F(t). If t≥Uct≥ U_c, cluster c contributes Wc/W_c/W to both F(t)F(t) and F^(t) F(t). If t∈[Lc,Uc)t∈[L_c,U_c), discrepancy arises from the cluster c only because maxi∈ℛcRi≤mini∈ℛc′Ri _i _cR_i≤ _i _c R_i for any c′>c >c, which yields |F(t)−F^(t)|≤WcW. |F(t)- F(t) |≤ W_cW. (32) Therefore, the above sum is bounded by ρmax _ . Taking the supremum over t completes the proof. ∎ Lemma B.2 (Arcsine scale implies ρmax≤sin(π/δ) _ ≤ (π/δ)). Suppose the digest is constructed with the scale r(q)=δ2πarcsin(2q−1)r(q)= δ2π (2q-1) under the condition of (13). Then ρmax=max1≤c≤mWcW≤sin(πδ)≤πδ. _ = _1≤ c≤ m W_cW≤ ( πδ )≤ πδ. (33) Proof. For each cluster c, let its empirical left/right quantile boundaries be qcL=Vc−1/Wq_c^L=V_c-1/W and qcR=Vc/Wq_c^R=V_c/W, where Vc=∑i=1cWiV_c= _i=1^cW_i (with V0=0V_0=0). Then qcR−qcL=Wc/Wq_c^R-q_c^L=W_c/W. The well-formedness constraint gives r(qcR)−r(qcL)≤1⟺arcsin(2qcR−1)−arcsin(2qcL−1)≤2πδ.r(q_c^R)-r(q_c^L)≤ 1 (2q_c^R-1)- (2q_c^L-1)≤ 2πδ. (34) Let uL=2qcL−1u_L=2q_c^L-1 and uR=2qcR−1u_R=2q_c^R-1, so that uL,uR∈[−1,1]u_L,u_R∈[-1,1] and qcR−qcL=(uR−uL)/2q_c^R-q_c^L=(u_R-u_L)/2. Under the constraint arcsin(uR)−arcsin(uL)≤2π/δ (u_R)- (u_L)≤ 2π/δ, the difference uR−uLu_R-u_L is maximized by taking symmetry around zero: arcsin(uR)=π/δ (u_R)=π/δ and arcsin(uL)=−π/δ (u_L)=-π/δ, hence uR=sin(π/δ)u_R= (π/δ) and uL=−sin(π/δ)u_L=- (π/δ). Therefore uR−uL≤2sin(πδ)⟹qcR−qcL=uR−uL2≤sin(πδ),u_R-u_L≤ 2 ( πδ ) q_c^R-q_c^L= u_R-u_L2≤ ( πδ ), (35) which is exactly Wc/W≤sin(π/δ)W_c/W≤ (π/δ). Taking the maximum over c yields the claim. ∎ Lemma B.3 (From ‖F−F^‖∞\|F- F\|_∞ to rank-accurate quantiles). Let F,F^F, F be CDFs on ℝR and define the generalized quantile function Q^(u)=inft:F^(t)≥u Q(u)= \t: F(t)≥ u\. If supt∈ℝ|F(t)−F^(t)|≤ϵ _t |F(t)- F(t)|≤ε, then for all u∈[0,1]u∈[0,1], F(Q^(u))∈[u−ϵ,u+ϵ].F( Q(u))\ ∈\ [u-ε,\ u+ε]. (36) In particular, when F is an empirical CDF with total weight W, Q^(u) Q(u) has empirical rank within (u±ϵ)W(u±ε)W. Proof. Fix u∈[0,1]u∈[0,1] and let t⋆=Q^(u)t = Q(u). By definition, F^(t⋆)≥u F(t )≥ u and for any t<t⋆t<t , F^(t)<u F(t)<u. Using supt|F(t)−F^(t)|≤ϵ _t|F(t)- F(t)|≤ε gives F(t⋆)≥F^(t⋆)−ϵ≥u−ϵF(t )≥ F(t )-ε≥ u-ε. For the upper bound, for any η>0η>0 we have F^(t⋆−η)<u F(t -η)<u, hence F(t⋆−η)≤F^(t⋆−η)+ϵ<u+ϵF(t -η)≤ F(t -η)+ε<u+ε. Letting η→0η→ 0 and using right-continuity of F yields F(t⋆)≤u+ϵF(t )≤ u+ε. ∎ B.1.2 Proof of Lemma 5.1 Proof. By Lemma B.1, supt|F(t)−F^(t)|≤ρmax. _t|F(t)- F(t)|≤ _ . (37) By Lemma B.2, ρmax≤sin(π/δ) _ ≤ (π/δ), hence supt|F(t)−F^(t)|≤sin(π/δ)=:ϵ _t|F(t)- F(t)|≤ (π/δ)=:ε. The bound sin(π/δ)≤π/δ (π/δ)≤π/δ yields the second inequality. Finally, Lemma B.3 implies that Q Q is ϵε-accurate in the quantile/rank sense. ∎ B.2 Proof of Theorem 5.1 We begin with the following corollary that controls the error of T-Digest for each atom. Corollary B.1 (Atom-wise sketch accuracy). Let pAp_A be its weighted empirical CDF and let p^A p_A be the step-CDF induced by the merged digest A TD_A. Then, under the arcsine scale (14), supt∈ℝ|pA(t)−p^A(t)|≤ϵ=πδ. _t |p_A(t)- p_A(t) |\ ≤\ ε\ =\ πδ. (38) Equivalently, the quantile query induced by A TD_A is ϵε-accurate in the sense of Section 4.3. Proof. This is a direct application of Lemma 5.1 to the weighted sample set AD_A. ∎ Step 1: First-order condition. The subgradient of (22) on β β with respect to β is given by ∑A∈∑c=1mAWA,cvA,cΦA+wtestvtestΦ(Xn+1)|vA,c=αif S¯A,c<β^TΦA,−(1−α)if S¯A,c>β^TΦA,tA,cif S¯A,c=β^TΦA,vtest=αif S<β^TΦ(Xn+1),−(1−α)if S>β^TΦ(Xn+1),ttestif S=β^TΦ(Xn+1), \ _A _c=1^m_AW_A,cv_A,c _A+w_testv_test (X_n+1) | .\\ .v_A,c= casesα&if S_A,c< β^T _A,\\ -(1-α)&if S_A,c> β^T _A,\\ t_A,c&if S_A,c= β^T _A cases,v_test= casesα&if S< β^T (X_n+1),\\ -(1-α)&if S> β^T (X_n+1),\\ t_test&if S= β^T (X_n+1) cases \, (39) where wtest=∑k=1Kλkw_test= _k=1^K _k with λk=πk/(nk+1) _k= _k/(n_k+1) and tA,c,ttest∈[α−1,α]t_A,c,t_test∈[α-1,α]. The first-order condition for optimality implies that for each group G∈G , there exist tA,c∈[α−1,α]t_A,c∈[α-1,α] (for clusters with ties) and ttest∈[α−1,α]t_test∈[α-1,α] (if the test point has a tie) such that ∑A:A⊆G∑c=1mAWA,cvA,c+wtestvtestXn+1∈G=0, _A:A G _c=1^m_AW_A,cv_A,c+w_testv_test1\X_n+1∈ G\=0, where the vA,cv_A,c and vtestv_test are as defined above. Step 2: Empirical CDF and T-Digest approximate. The atoms A\A\ partition X disjointly, with membership vectors ΦA _A. The true empirical CDF per atom is pA(t)=WA−1∑i:Xi∈Aλk(i)Si≤t,p_A(t)=W_A^-1 _i:X_i∈ A _k(i)1\S_i≤ t\, where WA=∑i:Xi∈Aλk(i)W_A= _i:X_i∈ A _k(i), λk(i)=πk(i)/(nk(i)+1) _k(i)= _k(i)/(n_k(i)+1), and k(i)k(i) is the index of the client that the sample XiX_i belongs to, for i∈[n]i∈[n]. The coreset per atom yields p^A(t)=WA−1∑c=1mAWA,cS¯A,c≤t, p_A(t)=W_A^-1 _c=1^m_AW_A,c1\ S_A,c≤ t\, with supt|pA(t)−p^A(t)|≤ϵ _t|p_A(t)- p_A(t)|≤ε by Corollary B.1. Step 3: Coverage. With (Xn+1,Yn+1)∼∑k=1KπkPk(X_n+1,Y_n+1) _k=1^K _kP_k, as in the proof of FCP [lu2023federated], let EkE_k be the event that (Xn+1,Yn+1)(X_n+1,Y_n+1) is drawn from PkP_k. For each k∈[K]k∈[K], let Πnk+1 _n_k+1 denote the set of all permutations of 1,…,nk+1\1,…,n_k+1\, and define the event ℰ=∀k∈[K],∃σk∈Πnk+1s.t.(Sσk(1),k,…,Sσk(nk+1),k)=(s1,k,…,snk+1,k),E= \∀ k∈[K],\,∃ _k∈ _n_k+1\ s.t.\ (S_ _k(1),k,…,S_ _k(n_k+1),k )= (s_1,k,…,s_n_k+1,k ) \, (40) where (s1,k,…,snk+1,k)(s_1,k,…,s_n_k+1,k) denotes the realized values of (S1,k,…,Snk+1,k)(S_1,k,…,S_n_k+1,k). Then, we have, for all G∈G , ℙ(Yn+1∈(Xn+1∣~)∣Xn+1∈G,ℰ)=Ek[ℙ(Sn+1≤β^Sn+1TΦ(Xn+1)∣Xn+1∈G,ℰ,Ek)]=ND,P(Y_n+1 (X_n+1 D) X_n+1∈ G,E)=E_E_k [P(S_n+1≤ β_S_n+1^T (X_n+1) X_n+1∈ G,E,E_k) ]= ND, where N N =∑A:A⊆GWApA(θ^A)+wtestSn+1≤θ^n+1Xn+1∈G, = _A:A GW_Ap_A( θ_A)+w_test1\S_n+1≤ θ_n+1\1\X_n+1∈ G\, D D =∑A:A⊆GWA+wtestXn+1∈G = _A:A GW_A+w_test1\X_n+1∈ G\ with θ^A=β^Sn+1TΦA θ_A= β_S_n+1^T _A and θ^n+1=β^Sn+1TΦ(Xn+1) θ_n+1= β_S_n+1^T (X_n+1) Analogously, define the GC-FCP approximate numerator and denominator as N^=∑A:A⊆GWAp^A(θ^A)+wtestSn+1≤θ^n+1Xn+1∈G,D^=D. N= _A:A GW_A p_A( θ_A)+w_test1\S_n+1≤ θ_n+1\1\X_n+1∈ G\, D=D. By Corollary B.1, we have N≥∑A:A⊆GWA(p^A(θ^A)−ϵ)+wtestSn+1≤θ^n+1Xn+1∈G=N^−ϵ∑A:A⊆GWA.N≥ _A:A GW_A( p_A( θ_A)-ε)+w_test1\S_n+1≤ θ_n+1\1\X_n+1∈ G\= N-ε _A:A GW_A. By the first-order condition, for the component corresponding to G, there exist tA,c,ttest∈[α−1,α]t_A,c,t_test∈[α-1,α] such that α∑A:A⊆G∑c:S¯A,c<θ^AWA,c−(1−α)∑A:A⊆G∑c:S¯A,c>θ^AWA,c+∑A:A⊆G∑c:S¯A,c=θ^AWA,ctA,c+wtestvtestXn+1∈G=0 α _A:A G _c: S_A,c< θ_AW_A,c-(1-α) _A:A G _c: S_A,c> θ_AW_A,c+ _A:A G _c: S_A,c= θ_AW_A,ct_A,c+w_testv_test1\X_n+1∈ G\=0 ⟹ ∑A:A⊆G∑c=1mAWA,cS¯A,c<θ^A+wtestSn+1<θ^n+1Xn+1∈G+(1−α)0=(1−α)D−, _A:A G _c=1^m_AW_A,c1 \ S_A,c< θ_A \+w_test1 \S_n+1< θ_n+1 \1\X_n+1∈ G\+(1-α)T_0=(1-α)D-T, where 0=∑A:A⊆G∑c=1mAWA,cS¯A,c=θ^A+wtestSn+1=θ^n+1Xn+1∈GT_0= _A:A G _c=1^m_AW_A,c1 \ S_A,c= θ_A \+w_test1 \S_n+1= θ_n+1 \1\X_n+1∈ G\ =∑A:A⊆G∑c=1mAWA,ctA,cS¯A,c=θ^A+wtestttestSn+1=θ^n+1Xn+1∈G.T= _A:A G _c=1^m_AW_A,ct_A,c1 \ S_A,c= θ_A \+w_testt_test1\S_n+1= θ_n+1\1\X_n+1∈ G\. By the definition of p^A(t) p_A(t) and N N, we have N^−α0=(1−α)D− N- _0=(1-α)D-T Because tA,c,ttest∈[α−1,α]t_A,c,t_test∈[α-1,α], α0−≥0, _0-T≥ 0, yielding N^≥(1−α)D. N≥(1-α)D. This yields P(Yn+1∈(Xn+1∣~)∣Xn+1∈G,ℰ) (Y_n+1 (X_n+1 D) X_n+1∈ G,E) =ND = ND ≥N^−ϵ∑A:A⊆GWAD ≥ N-ε _A:A GW_AD ≥(1−α)D−ϵ∑A:A⊆GWAD ≥ (1-α)D-ε _A:A GW_AD ≥1−α−ϵ, ≥ 1-α-ε, where the last inequality is due to ∑A:A⊆GWA<D _A:A GW_A<D. Taking expectation on both sides w.r.t. ℰE yields the desired result. Appendix C Group-Conditional Coverage Upper bound of GC-FCP Theorem C.1 (Upper bound coverage in the case of perfect quantile regression). Assume that the conditional score distribution S∣XS X is continuous and fix any confidence level η∈(0,1)η∈(0,1). Then, with probability at least 1−η/21-η/2 over the calibration data, for every group G∈G , GC-FCP satisfies ℙ(Yn+1∈(Xn+1∣~)∣Xn+1∈G)≤1−α+πδ+ΔG,P(Y_n+1 (X_n+1 D) X_n+1∈ G)\\ ≤ 1-α+ πδ+ _G, (41) where the additive term ΔG=||maxπδ,∑k=1Kπknk+1∑k[πknknk+1(pk,G−log(2K/η)2nk)], _G=|G| \ πδ,\, _k=1^K _kn_k+1 \ _k [ _kn_kn_k+1 (p_k,G- (2K/η)2n_k ) ], (42) with pk,G=PX,k(X∈G)p_k,G=P_X,k(X∈ G) being the probability that a covariate X drawn from client k belongs to group G. Proof: See Appendix C.1. Theorem C.1 shows that GC-FCP cannot be arbitrarily conservative. The group-wise coverage lies in a narrow band around 1−α1-α, with band width controlled explicitly by the additive term ΔG _G, which consists of the mis-coverage gap ϵε, calibration sizes nkn_k, and the mixture-weighted group mass pk,Gp_k,G. For instance, when the mixture-weighted group mass ∑kπkpk,G _k _kp_k,G is small, the denominator shrinks, and ΔG _G grows, which suggests that an efficient prediction set for low-support groups requires more calibration samples. C.1 Proof of Theorem C.1 For any G∈G , where ||=d|G|=d, we begin with P(Yn+1∈(Xn+1∣~)∣Xn+1∈G,ℰ)=ND≤N^+ϵ∑A:A⊆GWAD≤N^D+ϵ (Y_n+1 (X_n+1 D) X_n+1∈ G,E)= ND≤ N+ε _A:A GW_AD≤ ND+ε Record that tA,c,ttest∈[α−1,α]t_A,c,t_test∈[α-1,α], which yields ≥(α−1)0,N^=(1−α)D−+α0⟹N^≤(1−α)D+0T≥(α-1)T_0, N=(1-α)D-T+ _0\\ N≤(1-α)D+T_0 Hence, P(Yn+1∈(Xn+1∣~)∣Xn+1∈G,ℰ)≤1−α+ϵ+0DP(Y_n+1 (X_n+1 D) X_n+1∈ G,E)≤ 1-α+ε+ T_0D Now our target is to upper bound 0=∑A:A⊆G∑c=1mAWA,cS¯A,c=θ^A+wtestSn+1=θ^n+1Xn+1∈GT_0= _A:A G _c=1^m_AW_A,c1 \ S_A,c= θ_A \+w_test1 \S_n+1= θ_n+1 \1\X_n+1∈ G\ under the assumption that the distribution of S∣XS X is continuous. To bound this term, we first simplify the notation by relabeling the pseudo-points with the test point with i=1,…,m,m+1i=1,…,m,m+1, where m=∑A∈mA=(δ||)m= _A m_A=O(δ|A|) is the total number of clusters and S¯m+1=Sn+1 S_m+1=S_n+1. Claim 1. Under the conditions of Theorem C.1, with probability 1, we have ∑A:A⊆G∑c=1mAS¯A,c=θ^A+Sn+1=θ^n+1≤d. _A:A G _c=1^m_A1 \ S_A,c= θ_A \+1 \S_n+1= θ_n+1 \≤ d. Proof. See Appendix C.2 ∎ By Claim 1, with probability 1, we have 0D≤d⋅maxmaxA,c:A⊆G,c∈[mA]WA,c,wtestXn+1∈G∑A:A⊆GWA+wtestXn+1∈G T_0D≤ d· \ _A,c:A G,c∈[m_A]W_A,c\ ,\ w_test1\X_n+1∈ G\ \ _A:A GW_A+w_test1\X_n+1∈ G\ Next, we bound RHS using the properties of T-Digest. Record that wtest=∑k=1Kλk=∑k=1Kπknk+1w_test= _k=1^K _k= _k=1^K _kn_k+1. Claim 2. Assume that GC-FCP uses the scale function r(q)=δ2πarcsin(2q−1)r(q)= δ2π (2q-1) for q∈[0,1]q∈[0,1], where q is the normalized cumulative weight, i.e., quantile. Then, we have maxA,cWA,c≤WAsin(πδ)≤sin(πδ)≤πδ. _A,cW_A,c≤ W_A ( πδ )≤ ( πδ )≤ πδ. Proof. This is a direct result of Lemma B.2 and WA≤1W_A≤ 1. ∎ Claim 3. Assume that the mixture weights πk>0 _k>0, with pk,G=PX,k(X∈G)>0p_k,G=P_X,k(X∈ G)>0, for any η>0η>0, with probability larger than 1−η/21-η/2, we have ∑A:A⊆GWA≥∑kπknknk+1(pk,G−log(2K/η)2nk). _A:A GW_A≥ _k _kn_kn_k+1 (p_k,G- (2K/η)2n_k ). (43) Proof. See Appendix C.3. ∎ Combining Claims 1, 2, and 3, we have 0D≤dmaxπδ,∑k=1Kπknk+1∑kπknknk+1(pk,G−log(2K/η)2nk) T_0D≤ d \ πδ, _k=1^K _kn_k+1 \ _k _kn_kn_k+1 (p_k,G- (2K/η)2n_k ) Record that P(Yn+1∈(Xn+1∣~)∣Xn+1∈G,ℰ)≤1−α+ϵ+0D,P(Y_n+1 (X_n+1 D) X_n+1∈ G,E)≤ 1-α+ε+ T_0D, combing the bound of 0/DT_0/D and taking expectation over ℰE yield the desired result. C.2 Proof of Claim 1 Proof. Let ℒL denote the set of all pseudo-points, consisting of the clusters across all atoms and the test point. Specifically, ℒ=(A,c):A∈,c∈[mA]∪testL=\(A,c):A ,c∈[m_A]\∪\test\, with |ℒ|=m+1|L|=m+1, where m=∑A∈mA=(δ||)m= _A m_A=O(δ|A|) is the total number of clusters at merged T-Digests. For each l∈ℒl , define the feature Ψl=ΦA _l= _A if l=(A,c)l=(A,c) is a cluster in atom A, or Ψl=Φ(Xn+1) _l= (X_n+1) if l=testl=test, and the score Tl=S¯A,cT_l= S_A,c if l=(A,c)l=(A,c), or Tl=Sn+1T_l=S_n+1 if l=testl=test. The optimizer β^Sn+1 β_S_n+1 is the solution to the weighted quantile regression problem (22) with S=Sn+1S=S_n+1. A tie at pseudo-point l occurs if Tl=β^Sn+1TΨlT_l= β_S_n+1^T _l. Let aug=Xi,ki∈[nk],k∈[K]∪Xn+1D^aug=\X_i,k\_i∈[n_k],k∈[K]∪\X_n+1\. As in [gibbs2023conformal], we calculate the probability P(∑l∈ℒTl=β^STΨl>d∣aug)P ( _l 1 \T_l= β_S^T _l \>d ^aug ) The event ∑l∈ℒTl=β^STΨl>d \ _l 1 \T_l= β_S^T _l \>d \ implies that there exists a subset ℐ⊆ℒI with |ℐ|=d+1|I|=d+1 such that Tl=β^STΨlT_l= β_S^T _l for all l∈ℐl . Therefore, P(∑l∈ℒTl=β^STΨl>d∣aug)≤∑ℐ⊆ℒ,|ℐ|=d+1ℙ(∃β∈ℝd s.t. Tl=βTΨl∀l∈ℐ|aug)P ( _l 1 \T_l= β_S^T _l \>d ^aug )≤ _I ,\,|I|=d+1P (∃β ^d s.t. T_l=β^T _l\ ∀ l \ |\ D^aug ) For a fixed ℐI, the event is that the vector (Tl)l∈ℐ∈span(ΨlT)l∈ℐ(T_l)_l \( _l^T)_l \, where span(ΨlT)l∈ℐspan\( _l^T)_l \ is the image of the map β↦(ΨlTβ)l∈ℐβ ( _l^Tβ)_l , which is a linear subspace of ℝd+1R^d+1 with dimension at most d. Under the continuity assumption, the conditional distribution of (Si,k)i,k∪Sn+1(S_i,k)_i,k∪\S_n+1\ given the X’s is absolutely continuous with respect to Lebesgue measure on ℝn+1R^n+1. The mapping from the original scores Si,kS_i,k (and Sn+1S_n+1) to the coreset scores Tll∈ℒ\T_l\_l is piecewise affine. For each atom A, the score space ℝnAR^n_A is partitioned into finitely many open cones ℛπR_π indexed by permutations π∈nAπ _n_A, where ℛπ=∈ℝnA:sπ(1)<⋯<sπ(nA)R_π=\s ^n_A:s_π(1)<…<s_π(n_A)\, where boundaries have measure zero. Within each ℛπR_π, the sorted scores (π)s^(π) determine fixed quantile positions qlq_l based on permuted weights, leading to fixed cluster assignments via the deterministic T-Digest merge rules. Thus, each S¯A,c S_A,c is an affine function of (π)s^(π) (weighted average over fixed indices), and hence affine in s. The full map to (Tl)l∈ℐ(T_l)_l is therefore piecewise affine across atoms and the test score, preserving measure-zero sets under the continuous distribution of S∣XS X. Since the subspace has Lebesgue measure zero in ℝd+1R^d+1, its pre-image under the affine map also has measure zero. For a fixed ℐI, we have P(∃β∈ℝd s.t. Tl=βTΨl∀l∈ℐ|aug)=0.P (∃β ^d s.t. T_l=β^T _l\ ∀ l \ |\ D^aug )=0. Since there are at most (m+1d+1) m+1d+1 many such ℐI, the union bound yields P(∑l∈ℒTl=β^STΨl>d∣aug)=0P ( _l 1 \T_l= β_S^T _l \>d ^aug )=0 Because ∑A:A⊆G∑c=1mAS¯A,c=θ^A+Sn+1=θ^n+1>d⊆∑l∈ℒTl=β^STΨl>d, \ _A:A G _c=1^m_A1 \ S_A,c= θ_A \+1 \S_n+1= θ_n+1 \>d \ \ _l 1 \T_l= β_S^T _l \>d \, we have P(∑A:A⊆G∑c=1mAS¯A,c=θ^A+Sn+1=θ^n+1>d∣aug)≤ℙ(∑l∈ℒTl=β^STΨl>d∣aug)=0.P ( _A:A G _c=1^m_A1 \ S_A,c= θ_A \+1 \S_n+1= θ_n+1 \>d ^aug )\\ ( _l 1 \T_l= β_S^T _l \>d ^aug )=0. Marginalizing augD^aug yields the desired result. ∎ C.3 Proof of Claim 3 Proof. The calibration weight in G is ∑A:A⊆GWA=∑kλk⋅#i:Xi,k∈G _A:A GW_A= _k _k·\#\i:X_i,k∈ G\, where λk=πk/(nk+1) _k= _k/(n_k+1). Let Zk=#i:Xi,k∈GZ_k=\#\i:X_i,k∈ G\, then ∑A:A⊆GWA=∑kλkZk _A:A GW_A= _k _kZ_k, and Zk∼Bin(nk,pk,G), with pk,G=PX,k(X∈G)Z_k (n_k,p_k,G), with p_k,G=P_X,k(X∈ G) and the expected weight is E[∑A:A⊆GWA]=∑kλknkpk,G=∑kπknknk+1pk,G.E [ _A:A GW_A ]= _k _kn_kp_k,G= _k _kn_kn_k+1p_k,G. By Hoeffding’s inequality, for each k, P(Zk≤nkpk,G−tk)≤exp(−2tk2nk),P (Z_k≤ n_kp_k,G-t_k )≤ ( -2t_k^2n_k ), for tk>0t_k>0. Set tk=(nk/2)log(2K/η)t_k= (n_k/2) (2K/η) with any η>0η>0, we have P(Zk≤nkpk,G−tk)≤η2K.P(Z_k≤ n_kp_k,G-t_k)≤ η2K. By union bound over k, with probability larger than 1−η/21-η/2, ∑kλkZk≥∑kλk(nkpk,G−tk)=∑kπknknk+1(pk,G−log(2K/η)2nk). _k _kZ_k≥ _k _k(n_kp_k,G-t_k)= _k _kn_kn_k+1 (p_k,G- (2K/η)2n_k ). We have, with probability larger than 1−η/21-η/2, ∑A:A⊆GWA=∑kλkZk≥∑kπknknk+1(pk,G−log(2K/η)2nk). _A:A GW_A= _k _kZ_k≥ _k _kn_kn_k+1 (p_k,G- (2K/η)2n_k ). ∎ Appendix D Dual construction for (9) under the objective (10) Reformulate the primal: Let λk=πk/(nk+1) _k= _k/(n_k+1). The primal objective of (10) is rewritten as: ∑k=1Kλk∑i=1nkℓα(g(Xi,k),Si,k)+(∑k=1Kλk)ℓα(g(Xn+1),S). _k=1^K _k _i=1^n_k _α(g(X_i,k),S_i,k)+ ( _k=1^K _k ) _α(g(X_n+1),S). The pinball loss is given by ℓα(u,s)=(1−α)(s−u)++α(u−s)+, _α(u,s)=(1-α)(s-u)_++α(u-s)_+, where (a)+=maxa,0(a)_+= \a,0\. To reformulate the primal problem (10), we first introduce the following claim to rewrite the pinball loss as an optimization problem. Claim 4 (Pinball Loss Reformulation). Fix any scalar residual r=s−ur=s-u. Consider the following problem minp,q≥0(1−α)p+αqs.t.r=p−q. _p,q≥ 0\ (1-α)p+α q .t. r=p-q. (44) Then, the optimal value of (44) equals ℓα(u,s) _α(u,s). Proof. Since r=p−qr=p-q, we have p=r+qp=r+q. Together with p≥0p≥ 0 and q≥0q≥ 0, feasible pairs satisfy q≥max−r,0=(−r)+q≥ \-r,0\=(-r)_+ and then p=r+q≥0p=r+q≥ 0. Substitute p=r+qp=r+q into the objective: (1−α)p+αq=(1−α)(r+q)+αq=(1−α)r+q.(1-α)p+α q=(1-α)(r+q)+α q=(1-α)r+q. Thus, minimizing over feasible q is equivalent to minq≥(−r)+(1−α)r+q, _q≥(-r)_+\ (1-α)r+q, whose minimum is attained at q∗=(−r)+q^*=(-r)_+, giving value (1−α)r+(−r)+.(1-α)r+(-r)_+. If r≥0r≥ 0, then (−r)+=0(-r)_+=0, so the value is (1−α)r=(1−α)(s−u)(1-α)r=(1-α)(s-u). If r<0r<0, then (−r)+=−r(-r)_+=-r, so the value is (1−α)r−r=−αr=α(u−s)(1-α)r-r=-α r=α(u-s). Therefore, the optimal value is exactly (1−α)(s−u)++α(u−s)+=ℓα(u,s).(1-α)(s-u)_++α(u-s)_+= _α(u,s). ∎ By Claim 4, we introduce auxiliary pi,k,qi,k≥0p_i,k,q_i,k≥ 0 for each calibration point (i,k)(i,k) and pktest,qktest≥0p_k^test,q_k^test≥ 0 for each virtual test copy per client k and rewrite the problem (10) as (P0):ming∈ℱ,p,q (P0): _g _G,p,q ∑k=1K∑i=1nkλk((1−α)pi,k+αqi,k)+∑k=1Kλk((1−α)pktest+αqktest), _k=1^K _i=1^n_k _k ((1-α)p_i,k+α q_i,k )+ _k=1^K _k ((1-α)p_k^test+α q_k^test ), (45) s.t. Si,k−g(Xi,k)=pi,k−qi,k,S−g(Xn+1)=pktest−qktest,∀i∈[nk],∀k∈[K] S_i,k-g(X_i,k)=p_i,k-q_i,k,S-g(X_n+1)=p_k^test-q_k^test, ∀ i∈[n_k], 10000\ ∀ k∈[K] pi,k,qi,k,pktest,qktest≥0,∀i∈[nk],∀k∈[K] p_i,k,q_i,k,p_k^test,q_k^test≥ 0, ∀ i∈[n_k], 10000\ ∀ k∈[K] Dual problem: Introduce dual variables ηi,k _i,k for calibration constraints and ηktest _k^test for each test copy. Using standard calculations, the dual problem is given by the following linear programming (LP) problem: (P1):maxηi,k,ηktest (P1): _\ _i,k\,\η^test_k\ 10000\ 10000\ ∑k=1K∑i=1nkηi,kSi,k+S∑k=1Kηktest _k=1^K _i=1^n_k _i,kS_i,k 10000\ + 10000\ S _k=1^Kη^test_k (46) s.t. −λkα≤ηi,k≤λk(1−α),∀i∈[nk],∀k∈[K], - _kα≤ _i,k≤ _k(1-α), ∀ i∈[n_k], 10000\ ∀ k∈[K], (47) −λkα≤ηktest≤λk(1−α),∀k∈[K], - _kα≤ _k^test≤ _k(1-α), ∀ k∈[K], (48) ∑k=1K∑i=1nkηi,kΦ(Xi,k)+∑k=1KηktestΦ(Xn+1)=0. _k=1^K _i=1^n_k _i,k (X_i,k) 10000\ + 10000\ _k=1^K _k^test (X_n+1)=0. (49) where Φ(x)=(x∈G)G∈0,1|| (x)= (1\x∈ G\ )_G ∈\0,1\^|G|. The last constraint is to enforce the linearity of g(x)=βTΦ(x)g(x)=β^T (x), which arises mathematically from the stationary condition with respect to the primal weights β. Set construction via KKT conditions: In [gibbs2023conformal, Section 4], the conformal prediction set is constructed using the dual solution ηS _S (for input score S) and KKT conditions. The optimal g^S(Xn+1) g_S(X_n+1) satisfies: ηSn+1=1−α _S^n+1=1-α if S>g^S(Xn+1)S> g_S(X_n+1), ηSn+1=−α _S^n+1=-α if S<g^S(Xn+1)S< g_S(X_n+1), and ηSn+1∈[−α,1−α] _S^n+1∈[-α,1-α] if S=g^S(Xn+1)S= g_S(X_n+1). Similarly, let ηStest=∑k=1Kηk,Stest _S^test= _k=1^K _k,S^test be the sum of dual variables over test copies (since the test is duplicated). The set is: C^dual(Xn+1)=y:ηs(Xn+1,y)test≤(∑k=1Kλk)(1−α), C_dual(X_n+1)= \y: _s(X_n+1,y)^test≤ ( _k=1^K _k )(1-α) \, using the weighted upper bound. Binary search: We compute C^dual(Xn+1) C_dual(X_n+1) using the following two-step procedure. First, using Algorithm 1 of [gibbs2023conformal], we binary search for the largest value of S∗S^* such that ηS∗n+1<1−α _S^*^n+1<1-α. Second, we output all y such that s(Xn+1,y)≤S∗s(X_n+1,y)≤ S^* [gibbs2023conformal, Theorem 4]. Appendix E Additional Experimental Results E.1 Experimental Settings and Results of Section 6 Other parameters for the synthetic regression can be found in Table 3. Table 3: Experimental setup for synthetic regression. Parameter Value T-Digest parameter δ δ=250δ=250 Local calibration sizes nkn_k n1=1000n_1=1000, nk=333n_k=333 for k>1k>1 Mixture weights πk _k πk=1/K _k=1/K for all k Miscoverage level α α=0.1α=0.1 Model f(⋅)f(·) linear regression Score s(x,y)s(x,y) |y−f(x)||y-f(x)| Test points ntestn_test 200200 Monte Carlo runs 100100 The experimental results of PathMNIST are summarized in Table 4. Table 4: Coverage and set size comparisons on PathMNIST [medmnistv2]. Methods Marginal coverage Coverage (set size) G1G_1 G2G_2 G3G_3 G4G_4 G5G_5 Centralized CP 0.901 0.888 ↓ (1.00) 0.885 ↓ (1.00) 0.879 ↓ (1.00) 0.935 (1.00) 0.895 ↓ (1.00) FedCP 0.905 0.892 ↓ (1.01) 0.889 ↓ (1.01) 0.883 ↓ (1.02) 0.937 (1.01) 0.900 (1.02) GC-FCP (δ=25δ=25) 0.876 ↓ 0.891 ↓ (1.12) 0.890 ↓ (1.14) 0.880 ↓ (1.15) 0.895 ↓ (1.07) 0.853 ↓ (1.01) GC-FCP (δ=250δ=250) 0.908 0.913 (1.07) 0.910 (1.08) 0.911 (1.11) 0.911 (0.98) 0.898 ↓ (1.03) GC-FCP (δ=2500δ=2500) 0.909 0.913 (1.07) 0.910 (1.08) 0.910 (1.11) 0.912 (0.98) 0.900 (1.03) Figure 4 reports the empirical group-wise coverage and the average set size over confidence level α on CIFAR-10. Vanilla CP achieves competitive marginal coverage but exhibits group-wise miscalibration under non-i.i.d. client partitions. GC-FCP reduces these discrepancies, pushing group-wise coverage closer to the target across G∈G . This improvement comes with a moderate increase in set size, reflecting the standard trade-off when enforcing conditional validity over overlapping groups. Figure 5 reports the empirical group-wise coverage and the average set size over confidence level α on PathMNIST. As expected, vanilla CP exhibits nonuniform conditional coverage across groups and different values of α. GC-FCP improves stability across groups while keeping prediction sets competitive, highlighting its practical value in privacy-constrained settings. (a) Average coverage over different groups. (b) Average set size over different groups. Figure 4: Average coverage and set size versus coverage level 1−α1-α with vanilla CP and the proposed GC-FCP on CIFAR-10. (a) Average coverage over different groups. (b) Average set size over different groups. Figure 5: Average coverage and set size versus coverage level 1−α1-α with vanilla CP and the proposed GC-FCP on PathMNIST. E.2 Comparison with Personalized FCP and FedCF In this section, we compare the proposed GC-FCP with personalized FCP [min2025personalized] and FedCF [srinivasan2025fedcf] on CIFAR-10 [krizhevsky2009learning] using a fixed pretrained ResNet-56 classifier pθ(⋅∣x)p_θ(· x) and the standard classification nonconformity score S(x,y)=1−pθ(y∣x)S(x,y)=1-p_θ(y x). We split the CIFAR-10 test set uniformly at random into a calibration pool and an evaluation pool independently in each Monte Carlo repetition. The calibration pool is partitioned into K=5K=5 source clients by a disjoint partition of the true labels: each sample (x,y)(x,y) is assigned to client k if y belongs to the corresponding label subset as in Sec. 6.2, yielding client-specific calibration sets kk=1K\D_k\_k=1^K. In addition, we construct a synthetic (K+1)(K+1)-th target client by sampling 20002000 samples with replacement from the same calibration pool. All test points are drawn from the synthetic target client in the same way. FedCF [srinivasan2025fedcf] and GC-FCP calibrate using the calibration data from the K source clients together with the synthetic target calibration client, whereas personalized FCP [min2025personalized] leverages the source-client data to train additional distribution-estimation models and calibrates for the target client accordingly. For grouping, we consider the model confidence X(x)=maxc∈0,…,9pθ(c∣x)X(x)= _c∈\0,…,9\p_θ(c x) and define an overlapping family of confidence-based groups =G1,…,G4G=\G_1,…,G_4\ on the restricted confidence range [0.5,1][0.5,1]. Let 0.5=a0<a1<a2<a3<a4=10.5=a_0<a_1<a_2<a_3<a_4=1 be equally spaced breakpoints and define G1=x:X(x)∈[a0,a2),G2=x:X(x)∈[a1,a3),G3=x:X(x)∈[a2,a4),G4=x:X(x)∈[a3,a4],G_1=\x:\,X(x)∈[a_0,a_2)\,\ G_2=\x:\,X(x)∈[a_1,a_3)\,\ G_3=\x:\,X(x)∈[a_2,a_4)\,\ G_4=\x:\,X(x)∈[a_3,a_4]\, so that a point may belong to multiple groups when its confidence lies in an overlap interval. Finally, since FedCF [srinivasan2025fedcf] and personalized FCP [min2025personalized] are not designed to enforce simultaneous validity over overlapping G, we enforce a single set-valued predictor by resolving overlaps with a fixed random tie-breaking rule: when a test point lies in multiple groups, we randomly select one eligible group and construct the prediction set using the corresponding group-specific calibration. The report results represent the average after 100 Monte Carlo simulations, each with 20002000 test points drawn from the target client. Table 5 shows that GC-FCP achieves coverage across all overlapping groups. In contrast, personalized FCP and FedCF exhibit under-coverage for some groups despite providing marginal coverage, because both methods are group-wise procedures that treat each group independently and thus only admit guarantees when groups form a disjoint partition, which breaks under overlap. Consequently, the inability of these baselines to coordinate calibration across overlapping groups results in systematic group-conditional violations, whereas GC-FCP’s joint optimization over the overlapping family preserves group-conditional validity. Table 5: Coverage comparisons on CIFAR-10 [krizhevsky2009learning]. Methods Marginal coverage Coverage G1G_1 G2G_2 G3G_3 G4G_4 Personalized FCP 0.898 0.893 ↓ 0.890 ↓ 0.626 ↓ 0.913 FedCF 0.898 0.801 ↓ 0.824 ↓ 0.792 ↓ 0.905 GC-FCP (δ=250δ=250) 0.899 0.922 0.930 0.925 0.901