Distributed Conformal Prediction via Message Passing
Authors: Haifeng Wen
Hong Xing
Osvaldo Simeone
Venue: ICML 2025 poster (2025)
Keywords: Conformal prediction
Distributed optimization
Primary area: theory->probabilistic_methods
TL;DR: We propose two message-passing-based approaches for achieving reliable inference in a fully decentralized setting via conformal prediction.

Abstract: Post-hoc calibration of pre-trained models is critical for ensuring reliable inference, especially in safety-critical domains such as healthcare. Conformal Prediction (CP) offers a robust post-hoc calibration framework, providing distribution-free statistical coverage guarantees for prediction sets by leveraging held-out datasets. In this work, we address a decentralized setting where each device has limited calibration data and can communicate only with its neighbors over an arbitrary graph topology. We propose two message-passing-based approaches for achieving reliable inference via CP: quantile-based distributed conformal prediction (Q-DCP) and histogram-based distributed conformal prediction (H-DCP). Q-DCP employs distributed quantile regression enhanced with tailored smoothing and regularization terms to accelerate convergence, while H-DCP uses a consensus-based histogram estimation approach. Through extensive experiments, we investigate the trade-offs between hyperparameter tuning requirements, communication overhead, coverage guarantees, and prediction set sizes across different network topologies. The code of our work is released on: https://github.com/HaifengWen/Distributed-Conformal-Prediction.

Distributed Conformal Prediction via Message Passing
Haifeng Wen*
Hong Xing* 12
Osvaldo Simeone"
Abstract
to ensure reliable inference and decision-making in safety- critical domains such healthcare (Kompa et al., 2021), engineering (Cohen et al., 2023) and large language models (LLMs) (Ji et al., 2023; Huang et al., 2025). Conformal prediction (CP) is a model-agnostic post-hoe calibration framework that provides distribution- free statistical cover- age guarantees. This is done by augmenting an AI model's decisions with prediction sets evaluated on the basis of held- out data (Vovk et al., 2005; Angelopoulos al., 2024b).
Post-hoc calibration of pre-trained models is critical for ensuring reliable inference, especially in safety-critical domains such as healthcare. Conformal Prediction (CP) offers robust post-hoe calibration framework, providing distribution-ffee statistical coverage guarantees for prediction sets by leveraging held-out datasets. In this work, we address a decentralized setting where each device has limited calibration data and can communicate only with its neighbors over an arbitrary graph topology. We propose two message-passinne passing-based approaches for achiev- ing reliable inference via CP: quantile-based distributed conformal prediction (Q-DCP) and histogram-based distributed conformal prediction (H-DCP). Q-DCP employs distributed quantile regression enhanced with tailored smoothing and regularization terms to accelerate conver- gence, while H-DCP uses consensus-based histogram estimation approach. Through exten- sive experiments, investigate the trade-off's between hyperparameter tuning requirements, communication overhead, coverage guarantees, and prediction set sizes across different network topologies. The code of our work released on: https::/ http::://githtte cwm hww/eaaiee//aaaaaaaaacaaaae Distribouted--ooffooll------
CP uses held-out calibration data to infer statistical infor- mation about the distribution of the errors made by the pre-trained AI model. Based on this analysis, CP associates to each decision of the AI model a prediction set that in- cludes all the outputs that are consistent with the inferred error statistics. Specifically, CP calculates a quantile of per- formance scores attained by the pre-trained model on the calibration data (Vovk et al., 2005; Lei et al., 2018; 8; Barber et al., 2021). The prediction set provably meets marginal coverage guarantees for a user-defined target. Accordingly, the correct output is included in the prediction set with high probability with respect to the distribution of calibration and test data.
In light of its simplicity and of its strong theoretical prop- erties, CP has been recently developed in several direc- tions, including to address more general risk functions (An- gelopoulos et al., 2024c), to provide localized statistical guarantees (Gibbs et al., 2025), to operate via an online feedback- based mechanism (Gibbs & Candes, 2021), and incorporate Bayesian inference mechanisms (Clarté & Zdeborová, 2024). Furthermore, it has been applied in safety-critical areas such medical diagnostics (Lu et al., 2022) and LLMs (Quach et al., 2024; Mohri & Hashimoto, 2024).
1. Introduction
1.1. Context and Motivation
The post-hoe calibration of pre-trained artificial intelligence (AI) models has become increasingly important means
As mentioned, CP requires access to a data set of calibration data points. However, in practice, a decision maker may not have sufficient calibration data stored locally. This is important issue, since the size of the prediction set de- pends on the number of available calibration data points, and thus a small calibration data set would yield uninfor- mative prediction sets (Zecchin et al., 2024). However, calibration data may be available in a decentralized fash- ion across multiple devices (Xu et al., 2023). Examples include diagnostic healthcare models at different hospitals,
"Equal contribution 'IoT Thrust, The Hong Kong Univer- sity of Science and Technology (Guangzhou), Guangzhou, China 'Department of ECE, The Hong Kong University of Science and Technology, HK SAR DDeparteent of Engineering, King's College London, London, U.K.. Correspondence to: Hong Xing <hongx- ing hust.hk>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Distributed Conformal Prediction via Message Passing
Q-DCP
Distributed pinball loss minimication g(y)
P(Yust E C(Krest (D)) 1
Prodiction set C( (D)
(leopard. tiger, cat)
(1-z)-th quantile
Updare 10
via ADMM
H-DCP
al
Averaging consensus
Lest
(a)
(b)
Figure 1. (a) This work studies a decentralized inference setting in which multiple devices share the same pre trained model, and each device has local calibration data set. (b) Given a common imput, the devices aim at producing prediction set that includes the true label with a user-defined probability 1 a. (c) We propose two message-passing schemes for conformal prediction (CP): Quantile-based distributed CP (Q-DCP) addresses the decentralized optimization of the pinball, or quantile, loss over calibration scores; while histogram-based distributed CP (H-DCP) targets the consensus-based estimate of the histogram of the calibration scores.
Internet-of-Things (IoT) systems, and autonomous vehicle networks. In many of these scenarios, the distributed de- vices are privacy-conscious, preventing direct exchange of the local calibration data sets.
at producing a prediction set that includes the true label with user-defined probability.
This paper proposes two distributed CP (DCP) approaches: quantile-based DCP (Q-DCP) and histogram-based DCP (H-DCP), Q-DCP employs distributed quantile regression enhanced with tailored smoothing and regularization terms to accelerate convergence via message passing, while H- DCP uses consensus-
With this motivation, prior art has studied settings in which multiple data-holding devices are connected to the decision- making device via capacity-limited links in a star topology (Humbert et al., 2023; Lu et al., 2023; Plassier et al., 2023; Zhu et al., 2024), which is widely adopted for federated learning (McMahan et al., 2017; Kairouz et al., 2021). In these systems, the central device collects information from the devices to estimate the relevant global quantile of the calibration data distributed across the devices. In particular, in (Humbert et al., 2023), the global quantile estimated via a caaetiiie-oo-uunntileeee approach, which the devices transmit their local quantiles the central server and the quantile of the received quantiles is calculated at the central server side. In (Zhu et al., 2024), the central server estimates the average of the local histograms of quantized calibration scores and then estimates the global quantile based on the average histogram.
histogram estimation approach inspired by (Zhu et al., 2024).
Specifically, the main contributions of this work are as fol- lows:
1. We introduce Q-DCP, message-passing CP proto- col based on quantile regression. Q-DCP addresses a decentralized quantile regression problem by means of the alternating direction method of multipliers (ADMM) (Boyd et al., 2011) with tailored smooth- ing and regularization to accelerate the convergence speed. Q-DCP guarantees marginal coverage as cen- tralized CP, long as hyperparameters related the network topology and to the initialization are properly selected.
1.2. Main Contributions
2.
We also introduce H-DCP, a decentralized CP protocol that attains hyperparameter-free coverage guarantees. H-DCP estimates the global histogram of quantized local scores via a consensus algorithm.
The star topology assumed in the prior art does not reflect many important scenarios of interest in which communi- cation is inherently local, being limited to the neighbors of each device. As illustrated in Fig. ((a), this paper stud- ies CP in fully decentralized architecture in which the data-holding devices can only communicate via message passing on a connectivity graph. In this setting, all devices are decision-makers that have access to limited local cal- ibration data and share a common pre-trained model. As shown in Fig. 1(b), given a common input, the devices aim
Experiments explore the trade-offs between hyperpa- rameter tuning requirements, communication overhead, coverage guarantees, and prediction set sizes for Q- DCP and H-DCP across different network topologies. While H-DCP requires a larger communication load than Q-DCP, its coverage guarantees are not tied to hyperparameter selection.
2

---

Distributed Conformal Prediction via Message Passing
1.3. Notations
minimizes the inefficiency while satisfying the constraint
(2).
We use lower-case letter x denote scalars; upper-case letter X to denote random variables; bold lower-case letter to denote vectors; bold upper-case letter X to denote matrices; script letter X' to denote sets. We denote ||>||| as the 12-norm of vector æ; [[-} as the indicator function; | = V Ga as the G-norm of a vector æ with positive semidefinite matrix G; o Fmax (X) and muin (X)) as the largest singular value and the smallest non-zero singular value of a matrix X, respectively; and (X) to denote the i-th largest eigenvalue of a matrix X.
As shown in Fig. ((a), in order to produce the prediction set (( (D), devices can communicate over a connectiv- ity graph. The connectivity graph g(V. E) is undirected, with V denoting the set of devices with [ = K and
& S {(i.j) E V x Vii * j} denoting the set of edges with |8| E. The connectivity of the graph is character- ized by the 2E K incidence matrix A = [A]. A2 with submatrices AI, E REXK Denoting the index corresponding to an edge (i. E g E f1....,,1 |8 }. the (q. f)-th entry of matrix A and the (q.j)-th entry of matrix Ag equal if (i. is an edge in graph g(V, E), i.e., (i. E E, and they equal zero otherwise. Each device can only communicate with its set of neighbors, denoted as M {j E Vi k) E), under communication con- straints to be specified in Sec. 4.
2. Problem Description
We study network of K devices in which each device k has access to a local calibration data set Dr- = {(Xi,A, R. } ne with data points (Xi,s,, Yi,k) drawn i...d. from a distribution PR. We define the global data set the union U D)- D and n = Σ fi as the total number of data points. Using the local data sets {D&] and message-passing- based communication, the devices aim to collaboratively calibrate the decision of shared pre-trained model f X' | y.
3. Background
3.1. Split Conformal Prediction
Split CP provides a general framework for the design of post-hoe calibration strategies satisfying the coverage re- quirement (2) in centralized settings. CP constructs the pre- diction set C(-ID) based on a calibration data set D. This is done by evaluating quantile, dependent on the largest mis- coverage level a, of the scores assigned by the pre-trained model f to the calibration data points in set D.
To elaborate, assume that a test input Xtest is available at all devices. This may represent, e.g., a common observation in sensor network or a user query distributed to multiple servers. Given a target coverage level (1 - a) for a E [O, 1]. the goal of the system is to determine set-valued func- tion C(-ID) X + 2 with marginal coverage guarantees. Specifically, following (Lu et al., 2023), given test data point (X Yıe)), drawn from the mixture distribution
To elaborate, define as s(x, y) a negatively oriented score derived from model f. such as the absolute error s(x, y) ly f(x) for regression or the log-loss s(x, y) - log fz( for classification. Write as S, s(X,, Yi) the score assigned by the model f to the i-th calibration data point (X,, Yt) in the data set D. The prediction set is evaluated by including all the labels y E y with a score no larger than a fraction, approximately 1-a, of the calibration scores {S Specifically, CP produces the set
P
wpP Pk
(L)
for some weight wa 2 0 and Ek=1 Wk= 1, we impose the
coverage requirement
P(Yesu E C(XieulD)) 2 a.
This condition requires that the test label Yust belongs to the prediction set C(Xtes test (D) with probability at least 1 a. The probability in (2) is evaluated over the calibration data
C(XID) = {v e s(X,)) S (1(1)) + 1/n): (S))..)
(4)
in D and the test data (Xiest, Yrea). As in (Lu et al., 2023), we will specifically concentrate on the choice
where Q(7; (8.) is the I smallest value of the set {S.) which is set the score threshold.
Wk X T4k + 1,
(3)
in which the weight w/e for each device le is proportional to the size of the local data set Dr.
The empirical 7-quantile Q(T: (S:) in (4) can be ob- tained by solving the following quantile regression problem (Koenker & Bassett Jr, 1978)
The average size of the output of C(-ID), referred to as the inefficiency, is defined as the expectation EX (D), where the average is evaluated over Xlest and on the distri- bution of the data D. Ideally, the prediction set C(X ((Xusa) (D)
Q(7: (S:))))) = arg min (s ((S.)E))
(5)
RER
3

---

Distributed Conformal Prediction via Message Passing
where py (, (-1())))=)) is the pinball loss function defined as
uates the histogram vector Ps: = [1 k2 ........... PM. R& of the scores. The vectors Pę- with k: = 1,2,... K, synchronously transmitted to the centralized server on an additive multi-access channel, and the server estimates the average histogram p- = 1 Ex= Ps. based on the received K
(s ((
a
(6)
ReLU(S: - + (1
ReLU(s- ,
signal. The empirical (1 - a') qqqaaniillle of all the scores is then estimated from the estimated average histogram p for some optimized value a'. Under the non-i..dd setting described in Sec. 2, WFCP can guarantee the coverage con- dition (2).
with (x)U(x)= = max(x, 0).
3.2. Distributed Conformal Prediction on Star Topology
The calculation of the empirical quantile in the prediction set (4) requires full knowledge of the scores of all calibration data points in set D. When the data points are distributed and communication-constaaiiee de- vices as in the setting under study in this paper, evaluating the empirical quantile is not possible unless communica- tion is enabled. Prior work has studied federated setting in which all devices are connected to a centralized server (Humbert et al., 2023; Lu et al., 2023; Plassier et al., 2023; Zhu et al., 2024; 2025; Kang et al., 2024). For reference, we briefly introduce FedCP-QQ (Humbert et al., 2023), FCP (Lu et al., 2023) and WFCP (Zhu et al., 2024) next.
4. Quantile-based Distributed CP
In this section, we present the first fully decentralized proto- col proposed in this work, which referred to as quantile- based distributed CP (Q-DCP).
across privacy-
4.1. Decentralized Quantile Regression via ADMM
Q-DCP addresses the quantile regression problem (5) the fully decentralized setting described in Sec. 2 using ADMM (Boyd et al., 2011). This strategy obtains approximation of the empirical quantile Q((1 a1 + K K/n); (S: ) with a controlled error, which requires a single scalar broad- cast to the neighbors of each device at each optimization iteration. As will be discussed, on the flip side, Q-DCP requires careful hyperparameter tuning in order to satisfy the coverage condition (2). The alternative strategy pro- posed in the next section alleviates such requirements on hyperparameter tuning at the cost of larger per-iteration communication cost.
Denote {St.k s(X,,e, H the scores evaluated using the shared model I on the local data set Dj for device k. In FedCP-QQ (Humbert et al., 2023), each device k first calculates the empirical (1 - a')- quantile of its local scores, which is transmitted to the cen- tralized server for some probability a'. After collecting K local quantiles, the central server calculates the empirical (1 - -uaamtile of the received quantiles, thus obtaining quantile-of -u-unttilss............. By optimizing the probabilities a' and B3 the prediction set (4) is constructed using quantile- of-quantiles as the threshold. This approach satisfies the coverage condition (2) if the data sets Dj are i.idd across devices.
FedCP-QQ:
Formally, in Q-DCP, the K devices collaboratively solve the quantile regression problem
K Σ ((1-)(1+4)) (s (S(,))))
Minimize sER
(7)
FCP: While FedCP-QQ assumes i.i.d. data sets across devices, FCP (Lu et al., 2023) adopts the model described in Sec. 2 allowing data points from different local data sets to be drawn from different distributions {Px 1 while the test data point (Xtes, Yeea) is drawn from a mixture P P= 1 w&Pk of the local distributions. In FCP, the central server collects the local scores from the K devices, and then calculates the empirical (1 (1-a)(1- + k/n)-quantile This value is used as the threshold to construct prediction set C(X[D) in (4). FCP satisfies coverage condition (2) by choosing the weight wx to be proportional ngg + i.c.,
where target coverage (1 a) + K/n) follows FCP (Lu et al., 2023) (see previous section). The objective function (7) is convex, but it is not smooth or strongly convex. For such an objective function, direct application of ADMM would exhibit a sub-linear convergence rate, causing a large optimality gap when the number of communication rounds is limited (He & Yuan, 2012).
To ensure a linear convergence rate, we propose to re- place the ReLU operation in (6) with the smooth function ((x) = x + (1/k) log(1 + e <-**), where smaller x leads to greater smoothness at the cost of larger approximation error. In practice, the function (zz) coincides with RcLU(x) as lim g(w) = ReLU(z) (Chen & Mangasarian, 1996). Furthermore, to guarantee strong convexity, we add a regu-
Wk 12 + 1.
WFCP: Unlike FedCP-QQ and FCP, which communicate quantiles between devices and server, Zhu et al. (2024) pro- posed to exchange information about the local histograms of the quantized scores. Specifically, the scores { nh are first quantized to M levels by each device k which then eval-
4

---

Distributed Conformal Prediction via Message Passing
larization term the pinball loss function (6) as
distributed averaging algorithm (Xiao & Boyd, 2004) to obtain the average s(7) = 1/K E $k
(T) with negligible
n
(8 ((S)))))
7
Σ g(S: 8)
error.
i=1
(8)
Finally, the prediction set constructed
+ 7 Σ ā(s S:) + (s -00)2
CO-DEP (X()) = {u E y 8 S sD-DC),
(13)
2
with
where / > 0 and So are hyperparameters. The modified pinball loss function (- (S is L-smooth and μ- strongly convex, with L (nx)/4 + Using the smooth
8 S-DCP = 5()) + Q-DCP
(14)
where CDDCP is upper bound on the error |s()) of the quantile estimate g(() to be derived in the next subsection.
and strongly convex loss in (8), the decentralized optimiza- tion of quantile regression in (7) is modified as
The proposed Q-DCP is summarized in Algorithm 1.
Minimize .EB
Σ Mu-axu44 (8 (S
Algorithm 1 Q-DCP
Input: ADMM parameters e > 0 and b > 1, number of iterations T, incidence matrix A, smoothness parame- ter L and regularization parameters (μi, 80, eo). coverage level 1 a, and score s(..-) Initialize s()) z 20) ( and t
Note that the (unique) solution of problem (9), denoted by s*, generally different from the optimal solution s" of problem (7), unless x tends to infinity and μ is set zero.
Q-DCP adopts ADMM to address problem (9), obtaining the formulation
ADMM (Boyd et al., 2011):
while t T do
Update s(++1) by solving
K
Minimize CER",EER=
f(s) = Σ P( P(1-a)(1+ K) (sk (5
Vi( ( A X (0) + +cA (As(t++)))) Bz( 0
k=1
Subject to As + Bz 0,
((+1) (cB - (cAs(++1) + (
(10) where A 22Ex is the incidence matrix defined in See. 2, B I- -I]] E 2EE and an auxiliary variable imposing the consensus constraint on neighboring devices, corresponding index of edge (i
(1+1) x + ((+1)) + (Bz(1+))
t ++t+1
end while Prediction set construction: for device & E V do
i.e., 8; 2g and 8j 2g if (i.5) E with q being the
Run distributed averaging (Xiao & Boyd, 2004) to obtain g(T) K Σ 8 (T)
4.2. Description of Q-DCP
Calculate e ( and En using (17) and (16), respectively,
Following ADMM (Boyd et al., 2011), Q-DCP solves prob- lem (10) by considering the augmented Lagrangian
and set QDDCP = ((7) + (7)) + 2
end for
Output: CO-DCP = f2 E y: s.sssss. v) s 50-DP)
T. 2, A) f(s) (2. As B2) + c
I As B2ll2
(11)
where X E 222E, is the Lagrange multiplier associated with the 2E equality constraints in (10), and c > is a hyperpa- rameter. The updates of the local estimated quantiles 8, the consensus variables z and the dual variables À at iteration t ++1 are given by (Boyd al., 2011)
4.3. Theoretical Guarantees
In this section, we first derive the e QDDCP upper bound on the estimation error of Q-DCP used in constructing the prediction set (13). Then we prove that Q-DCP attains the coverage guarantee (2).
s (f+1) = argmin (s, 2 (1) A (1)),
(12a)
By the triangle inequality, the estimation error |s(T) s*1 can be upper bounded
BERK
(1+1) argmin T. (t+1), ,,,
(12b)
zEkE
(T()) s < ( 5-1 1s" - -s
(15)
X (1+1) = (1) + As (1+1) + (x((+)))
(12c)
where the first term accounts for the convergence error for problem (10), while the second term quantifies the bias caused by the use of the smooth and strongly convex ap- proximation (8).
After T iterations, ADMM produces the quantile estimate (T) for each device V. Then, the devices run the fast
5

---

Distributed Conformal Prediction via Message Passing
The bias term can be bounded as follows. We start with the following assumption.
as of the parameter ö in (17), which depends on the connec- tivity properties of the graph through the incidence matrix A. In this section, we present an alternative fully decentral- ized protocol, referred to as histogram bistogram-bused DCP (H-DCP), which provides rigorous coverage guarantees without the need for hyperparameter tuning as in Q-DCP, but at the cost of larger communication overhead.
Assumption 4.1. The regularization parameter 8p and the optimal solution s" in (5) differ by at most en 2 0, i.c.,
|80 - 5*1 S 60-
Proposition 4.2. Under Assumption 4.1, the bias |s - s*1
upper bounded as
In H-DCP, devices exchange histograms of quantized cal- ibration scores in manner similar to WFCP (Zhu et al., 2024). As result of a consensus algorithm, the devices evaluate the average histogram in order to yield an es- timate of the mixture distribution P in (1) with weights (3). From this estimate, a suitable bound is derived on the (1 (1-a)(1 + K/n)-quantiin -quantile of the distribution P to evaluate the prediction set of the form (4).
2n log(2) + + E0.
1s - 11--815 1
(16)
Proof:
See supplementary material (see Appendix A.1). D
Next, the convergence error (5(T) s*| is bounded by lever-
aging on existing results on the convergence of ADMM.
Proposition 4.3 (Theorem 1, Shi et al., 2014). The conver- gence error s B(T) 3*1 is upper bounded as
5.1. Description of H-DCP
T-1
start, in H-DCP, all devices apply a uniform scalar quan- tizer, r(+) [o, 1] + {1/M, 2/...... .I. with step size 1/M, to all the local calibration scores under the following assumption.
1
(3(T) - 8-1 1
11u(0)
- -ulla (17)
Kp
1
1+8
(T)
where the parameter 8 >> is defined as
Assumption 5.1. The score function s(-.) :) is bounded, i.c. without loss of generality, 0 S s(; S
8 == mmmin ( ((b 1 -)/ / (bo muxe (M+)
(18)
/// ((c/4)o max (M+ + (b/c) T min (M (M)))
The quantizer is formally defined as
with any b M-
A
A M. A + AT Moreover, (
1 [0,
and G = cI
Og
T(s)
M
m
M
m
OF (I/c)
m
for m 22....,
M
M
M
E E containing the first E entries of the vector X (0), and we also write as u²
((x(0)T,("" (T with X (0)
(19) With this quantizer, each device & E V evaluates the local histogram P;: = -p. ,PM.,l' ,PM,]* associated with the lo- cal quantized scores (S..,))) with Em=1 Pm,k- 1. Accordingly, this vector includes the entries
[(=*)T, (A TTT the 2Ex x vector collecting of the optimal primal solution z" and the optimal Lagrange multipliers X of problem (10).
The upper bound (17) depends on the initial error, quantified by the distance uu u² ll. and by the connectivity of the graph. In fact, a larger connectivity is reflected by a larger ratio amin ( (M -)/ max (M+) (Fiedler, 1973), and thus larger parameter d in (17).
1 n6
= m [T(()))= Σ TIA
Pm.k
M
(20)
with Pm, representing the fraction of the quantized scores associated with the m-th quantization level device i E V. The sum
Using the obtained bounds (16) and (17) in (15), we obtain the following main result on the performance for Q-DCP.
Theorem 4.4 (Coverage Guarantee for Q-DCP). The pre- diction set CD-DCP (-ID) in (13) produced by Q-DCP satisfies the coverage condition (2) with weights selected as in (3).
K
mk >
((Si))=
m) M (21)
Pm
n&Pm
n
n
corresponds to the fraction of quantized scores equal to m/M in the set of quantized scores for the global data set D. defining the global histogram vector [pi..... PM).
Proof: See supplementary material (see Appendix A.2) O
5. Histogram-based Distributed CP
In H-DCP, the devices aim at estimating the global score histogram p in (21) in order to obtain an estimate of the -1-00 (1 + K/n)-quantile of the quantized calibration
As demonstrated by Theorem 4.4, Q-DCP requires knowl-
edge of a parameter 60 satisfying Assumption 4.1, as well
6

---

Distributed Conformal Prediction via Message Passing
scores, i.e.,
Algorithm 2 H-DCP
Consensus parameters 1) and matrix W. number of iterations T, quantization level M, coverage level 1 a, and score s(:;-)
Input:
Ma M
Q ((1 a) (1+ (K+KK)n)))))) K/n);;nn (T(
1
arg min m=
Σ 1 a) (1 K
(22)
Each device & E V calculates the local histogram Ps via (20)
M
Initialize m/&
(0) ((Kn)//n)ps and
By the design of the quantizer (19), this quantile provides
Consensus:
an upper bound on the (1 (1 + ( //uanilueeile of the unquantized calibration score.
while t < T do
for device k E /o (t)
zy (f+1) = 2 + 17 - (1 -xk)
To estimate the sum (21), the devices apply consensus with matrix W E R-K satisfying W WT, W1 1 with entries
end for
1 W 1s and || IW- 1Kl/K|la
t t t+1 end while Prediction set construction: for device k E do
Wi. W 0 if (k.j) E and [W]&J 0 oth- erwise. Following the fast distributed averaging algorithm (Xiao & Boyd, 2004), each device & E V updates the local vector E. by linear consensus step
Calculate e JI-DCP via (26) Calculate m H-DCP via (25) a,k
K
end for
(1+1) 4 3k
(1)
+
We (a kk )
(23)
Output: For all E V, construct Ck CHLDDP (LIDDCP)) via (24)
j=1
(0)
where we define the initialization z ((Kn))/)pp such that p 1/K k= Lg. and E (0, 1] is the update rate.
3
where e p= 1-1 is the spectral gap of the consensus
>
matrix W, the prediction sets C# (--DCP(.ID) in (24) produced by H-DCP for all k V satisfy the coverage condition (2)
by choosing weights as in (3).
Finally, H-DCP constructs the prediction set at device as
H-DCP
Proof:
See supplementary material (see Appendix A.3). O
C-DDCP C (H-DCP(XD)-- yEy. ((s(X,)))
a.
(24)
M
Theorem 5.2 shows that H-DCP only requires knowledge of the spectral gap 2. which can be efficiently estimated in fully decentralized manner (Muniraju et al., 2020). The flip side is that, while Q-DCP requires the exchange a single real number at each iteration, H-DCP has a communication overhead M times larger, requiring the exchange of an M- dimensional real vector.
where
m
M a.k
H-DCP
arg min
Σ
iik
(T)
1=1
(25)
1 K
2 a1
+ H-DCP
6. Experimental Results
and H-DCP is parameter to be determined below to give upper bound on the error |==] pll for the local estimate (T) of the global vector p at device & E V after T global 4
In this section, we report experimental results on the pro- posed decentralized CP protocols, Q-DCP and H-DCP, us- ing the conventional centralized CP benchmark. We first study Q-DCP and H-DCP separately, and then provide comparison between Q-DCP and H-DCP function of the communication load. Throughout, we evaluate the performance in terms of coverage and average set size, also known as inefficiency (Vovk et al., 2005), for different net- work topologies.
communication rounds. Note that if (1 a1 + K/n) +
ICP > 1, we set IIDCP = M.
The proposed H-DCP summarized in Algorithm
5.2. Theoretical Guarantee
In this subsection, we provide the main result on the cover- age guarantee H-DCP through the following theorem. Theorem 5.2 (Coverage Guarantee for H-DCP). Setting
6.1. Setting
As in Lu et al. (2023), we first train a shared model f(-) using the C0 training data set to generate the score function s-.,)). Calibration data, obtained from the Cif test data, distributed non-i.i.d manner among K
H-DCP
K KV2K (1 TT)
T
max [n KEV
}
K
1
n
(26)

---

Distributed Conformal Prediction via Message Passing
20 devices by assigning unique classes each device. Specifically, device receives nı data points corresponding to 0-4, device 2 receives n2 data points from classes 5- 9, and so on. We set 7 = 50 for all devices k E V. Using the shared model f()). the score function defined as s(2, y) = - [ where [f(]] is the confidence assigned by the model to label y (Sadinle al., 2019).
1.0
100
CP
Normalizer set size
Q-BCC
chain
cycle
Coverage
-0-1
slut
0.2
10-3
0.0
0.5
We extract the calibration data from the Cifar 100 test data by sampling uniformly at random (without replacement), and average results are shown over 10 random generations of the calibration data. The set size is normalized to the overall number of classes, i.e., 100.
Figure 2. Coverage and normalized set size versus coverage level
for CP and Q-DCP when Assumption 4.1 is satisfied (T' 1500 and 6o = 0.1). The shaded error bars correspond to intervals covering 95% of the realized values.
1.0
10"
CP
6.2. Results for Q-DCP
Normalin alized set size
DCP
The hyperparameters for the Q-DCP loss (8) are chosen as follows. We set A = 2000 for the smooth function g(-) as suggested by Nkansah et al. (2021), and we choose μ 2000. Moreover, unless noted otherwise, in (8), we set so be the average the local score quantiles, which can be evaluated via preliminary consensus step. Note that the need to choose suitable value for so is related to the general problem of hyperparameter-tuning Sec. 4.3. This aspect will be further elaborated below by studying the impact the selection of hyperparameter cu in (16).
Coverage
10-1
10-2
0.0
0.5 a
1-a
Figure 3. Coverage and normalized set size versus coverage level a for CP and Q-DCP when Assumption 4.1 is not satisfied (T = 1500, 10 and = 8 20cx.
for Q-DCP discussed in
standard form with entries Wey = a for all edges (k, j) E E, Wi = Wi for all devices E V, and Wkj 0 otherwise, where being the Laplacian of the connectivity graph (Xiao & Boyd, 2004). As illustrated in Fig. 4, unlike Q-DCP, H- DCP guarantees the coverage level - a without the need for hyperparameter tuning. Results on the convergence of H-DCP can be found the supplementary material (see Appendix B.2).
The impact of the coverage level 1 a on Q-DCP is studied in Fig. 2 for T 1500 and Eg 0.1. while results convergence can be found in the supplementary material (see Appendix B.2.). We specifically consider the chain, cycle, star, torus, and complete graph, which are listed in order of increasing connectivity. Validating Theorem 4.4, the figure shows that Q-DCP provides coverage guarantees, with more conservative prediction obtained over graphs with lower connectivity. In particular, with a complete graph, the assumed T' 1500 iterations are seen to be sufficient to obtain the same set size as centralized CP.
2/(A) (L) + AK-
with L
1.0
10"
CP
Normal Iood set size
DCP
0.8
As detailed in Theorem 4.4, Q-DCP requires a carefully selected hyperparameter 6o. satisfying Assumption 4.1, in
Coverage
0.6
10-1
complete
order to meet coverage guarantees. To verify this point,
Fig. shows coverage and size as function of for the pair (Sg = 8 20a, co 10-4), for which Assumption 4.1 is not satisfied. The figure confirms that Q-DCP can fail to yield coverage rates larger than 1 - for some topologies. This is particularly evident for graphs with stronger connectivity, which yield faster rate of error compounding across the iterations.
0.0
0.7
0.5
1-a
1 1-
Figure 4. Coverage and normalized set size versus coverage level a for CP and H-DCP (T' 150).
6.4. Comparing Q-DCP and H-DCP
6.3. Results for H-DCP
Finally, we conduct experiments to compare the two pro- posed approaches in terms of the trade-offs among commu- nication overhead, coverage guarantees, and prediction set sizes. In order to enable a fair comparison, we evaluate the performance of both Q-DCP and H-DCP under the same
For H-DCP, unless noted otherwise, we set the consensus rate to 17 1, and the number of quantization levels to M 1000. We choose the consensus matrix W in the
8

---

Distributed Conformal Prediction via Message Passing
10
10a
CP
7. Conclusion
Normalizen set size
Q-PCP
H-DCP
Coverage
0.9
fioati
flont32
This work has addressed the post-hoc calibration of pre- trained models in fully decentralized settings via conformal prediction (CP). We have proposed two message-passingg based approaches, ceantile-based distributed CP (Q-DCP) and histogram-based distributed CP (H-DCP), that achieve reliable inference with marginal coverage guarantees. Q- DCP leverages distributed quantile regression with smooth- ing and regularization to enhance convergence, while H- DCP applies consensus-based histogram estimation. Our extensive experiments demonstrated the effectiveness of both methods in balancing communication overhead, cov- erage guarantees, and prediction set sizes across various network topologies. Specifically, Q-DCP was observed to have lower communication requirements, while being sen- sitive to hyperparameter tuning. In contrast, H-DCP offers robust coverage guarantees the cost of larger communi- cation load.
hyp. sctting
flont64
0.8
10-1
setting
hyp setting? 2
0.7
byp. setting?
10 10
10a
10?
Commun. load (bit)
Commun. load (bit)
Figure.5 5. Coverage and normalized set size versus the total per- device communication load (torus graph with a 0.1, and Q-DCP with hyperparameter setting given by (eg = 0.1, so being the average the local score quantile) and hyperparameter setting given by (ee = 10_², = -0)).
total communication load per device. The communication load is evaluated in bits as T - C. where T is the number of iterations and C' denotes the number of bits communicated by one device per iteration. The per-iteration communica- tion load C is evaluated for the two schemes as detailed next.
Future work may investigate extension to asynchronous net- work (Wei & Ozdaglar, 2013; Tian al., 2020), to localized risk guarantees (Gibbs et al., 2025; Zecchin & Simeone, 2024) and to online CP (Zhang et al., 2024; Angelopoulos et al., 2024a).
For H-DCP, we fix the number of quantization levels to M = 1000, so that each histogram vector contains M = 1000 numbers. Each of these numbers is represented using a floating point format with / ε {16, 32, 64) bits. Over- all. the per-iteration per-device communication load of H- DCP is C Mf. For Q-DCP, we also represent each estimated quantile $% using a floating point format with T {16,32, 64) bits, yielding a communication load equal to C-C
Acknowledgements
The work of H. Xing was supported by the Guangdong Ba- sic and Applied Basic Research Foundation under Grant 0025A1515010122 by the Guangdong Provincial Key Lab of Integrated Communication, Sensing and Com- putation for Ubiquitous Internet of Things under Grant 2023B 10331212010007 and by the Guangzhou Municipal Sci- ence and Technology Project under Grants 2024A04J4527 and 2024A03J0623.. The work of O. Simeone sup- ported by the European Union's Horizon Europe project CENTRIC (101096379), by an Open Fellowship of the EPSRC (EP/W024100//), and by the EPSRC project (EP/X011852/1).
Fig. 5 show the coverage and set size versus the total per- device communication load, TC, for both Q-DCP and H- DCP on the torus graph using different values of the numer- ical precision f. The choice of the torus graph is motivated by the fact that the spectral gap of the torus graph with 20 devices is moderate, providing an intermediate setting between a complete graph and a cycle graph. For Q-DCP, consider two choices of hyperparameters, one, in Fig. 2, satisfying Assumption 4.1, and one, chosen as in Fig. 3, not satisfying this assumption.
Impact Statement
This paper presents work whose goal is to advance the field of conformal prediction and reliable machine learn- ing. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
As seen in Fig. 5, with well-selected hyperparameters, Q- DCP provides more efficient prediction sets, while also meeting the coverage requirement 1 a = 0.9. An ex- ception is given by the case numerical precision of the inputs prevents Q-DCP from ob- taining a high-quality solution for equation (12a). However, with poorly selected hyperparameters, Q-DCP can yield a violation of the coverage requirements even at a high pre- cision f. In contrast, H-DCP maintains the coverage level 1 a across all considered communication loads.
16, in which the reduced
References
Angelopoulos, A. N., Barber, R., and Bates, S. Online conformal prediction with decaying step sizes. In Pro- ceedings of the 4|st International Conference on Machine Learning, volume 235, pp. 1616-1630, Jul. 2024a.

---

Distributed Conformal Prediction via Message Passing
Angelopoulos, A. N., Barber, R. F., and Bates, S. Theoreti- cal foundations of conformal prediction. arXiv preprint arXiv:2411.11822 2024b.
Ji, Z., Lee, N., Frieske, R., Yu, T., Su, D., Xu, Y., Ishii, E., Bang, Y. J., Madotto, A., and Fung, P. Survey of halluci- nation in natural language generation. ACM Computing Surveys, 55(12): 2023.
Angelopoulos, A. N., Bates, S., Fisch, A., Lei, L.., and Schuster, T. Conformal risk control. In The Twelfth International Conference on Learning Representations, Vienna, Austria, May 2024c.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M. Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and trends@ in machine learning. 14(1 (((12):1-210 2021.
Barber, R. F., Candes, E. J., Ramdas, A., and Tibshirani, J. Predictive inference with the jackknife+. The Annals of Statistics, 4986-7777 2021.
Kang, M., Lin, Z., Sun, J., Xiao, C., and Li, B. Certifiably Byzantine- robust federated conformal prediction. In Pro- ceedings of the 4|st International Conference on Machine Learning, volume 235, pp. 20022-23057 Jul. 2024.
Boyd, S., Parikh, N., Chu, E.,, Peleato, B., Eckstein, J., et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning. 3(1):1-122, 2011.
Koenker, R. and Bassett Jr, G. Regression quantiles. ECoRO- metrica: journal of the Econometric Society, pp. 33-50, 1978.
Chen, C. and Mangasarian, O. L. A class of smoothing functions for nonlinear and mixed complementarity prob- lems. Computational Optimization and Applications, 5 (2):97-138, 1996.
Kompa, B., Snock, J., and Beam, A. L. Second opinion needed: communicating uncertainty in medical machine learning, NPJ Digital Medicine, 4(1):4, 2021.
Clarté, L. and Zdeborová, L. Building conformal predic- tion intervals with approximate message passing. arXiv preprint arXiv:2410. 16493, 2024.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution-free predictive inference for regression. Journal of the American Statistical Associa- tion, 113(523):1094 1111, 2018.
Cohen, K. M., Park, S., Simeone, O., and Shitz, S. S. Calibrating Al models for wireless communications via conformal prediction. IEEE Transactions on Machine Learning in Communications and Networking, 1:296- 312, 2023.
Lu, C., LLmaa,m A., Chang, K., Höbel, K., and Kalpathy- Cramer, Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 2022.
Fiedler, M. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298-305, 1973.
Lu, C., Yu, Y., Karimireddy, S. P., Jordan, M.. and Raskar, R. Federated conformal predictors for distributed uncer- tainty quantification. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202, pp. 22942-22964, Jul. 2023.
Gibbs, I. and Candes, E. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1666: 111016666222 2021.
Gibbs, I., Cherian, J., and Candès, E. J. Conformal pre-
diction with conditional guarantees. Journal of the Royal Statistical Society Series B: Statistical Methodology. pp. qkaf008, 2025.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effiieee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
He, B. and Yuan, X. On the O(1/n) convergence of the Rachford alternating direction method. SIAM Journal on Numerical Analysis, 50(2):700-775 -009000770000000 2012.
Douglas-Rachford
Mohri, C. and Hashimoto, T. Language models with con- formal factuality guarantees. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 36009-3604777 Jul. 2024.
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q. Peng, W., Feng, X., Qin, B., et al. A survey hallucination in large language models: Principles, taxon- omy, challenges, and open questions. ACM Transactions on Information Systems, 43(2):1 2025.
Muniraju, G., Tepedelenlioglu, C., and Spanias, A. Con- sensus based distributed spectral radius estimation. IEEE Signal Processing Letters, 27: 1741099-1049 2020.
Humbert, P., Le Bars, B., Bellet, A., and Arlot, S. One- shot federated conformal prediction. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 14153-1417,, Jul. 2023.
Nkansah, H., Benyah, F., and Amankwah, H. Smoothing approximations for least squares minimization with L1- norm regularization functional. International Journal of Analysis and Applications, 19(2):264 2279,, 2021.
10

---

Distributed Conformal Prediction via Message Passing
Plassier, V., Makni, M., Rubashevski,, A., Moulines, E., and Panov, M. Conformal prediction for federated uncertainty quantification under label shift. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 27907-27947, Jul. 2023.
prediction. IEEE Transactions on Signal Processing, 72: 1235-1250, 2024.
Zhu, M., Zecchin, M., Park, S., Guo, C., Feng. C., Popovski, P., and Simeone, O. Conformal distributed remote infer- ence in sensor networks under reliability and communica- tion constraints. IEEE Transactions on Signal Processing, 73:1488-1500 2025.
Quach, V., Fisch, A., Schuster, T., Yala, A., Sohn, J. H., Jaakkola, T. S., and Barzilay, R. Conformal language modeling. In The Twelfth International Conference on Learning Representations, Vienna, Austria, May 2024.
Sadinle, M., Lei, J., and Wasserman, L. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(52)):223- 234, 2019.
Shi, W., Ling, Q. Yuan, K., Wu, G., and Yin, W. On the linear convergence of the ADMM in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7):1750-1761 2014.
Tian, Y., Sun, Y., and Scutari, G. Achieving linear conver- gence in distributed asynchronous multiagent optimiza- tion. IEEE Transactions Automatic Control, 65(12):
5264-5279, 2020.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in random world, volume 29. Springer, 2005.
Wei, E. and Ozdaglar, A. On the O(1=k) convergence of asynchronous distributed alternating direction method of multipliers. In 2013 IEEE Global Conference Signal and Information Processing, pp. 551-554, 2013.
Xiao, I.. and Boyd, S. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Xu, M., Wu, Y., Cai, D., Li, X., and Wang, Federated fine- tuning of billion-sized language models across mobile devices. arXiv preprini arXiv:2308. 13894, 2023.
Zecchin, M. and Simeone, O. Localized adaptive risk con- trol. In The Thirty-eighth Annual Conference Neu- ral Information Processing Systems, Vancouver, Canada, Dec. 2024.
Zecchin, M., Park, S., Simeone, O., and Hellström, F. Gen- eralization and informativeness of conformal prediction. In 2024 IEEE International Symposium on Information Theory, pp. 244-249. IEFF, 2024.
Zhang, Y., Park, S., and Simeone, O. Bayesian optimiza- tion with formal safety guarantees via online conformal prediction. IEEE Journal of Selected Topics in Signal Processing, 2024.
Zhu, M., Zecchin, M., Park, S., Guo, C., Feng, C., and Simeone, O. Federated inference with reliable uncer- tainty quantification over wireless channels via conformal

---

Distributed Conformal Prediction via Message Passing
A. Proofs of Main Results
A.1. Proof of Proposition 4.2
For simplicity, in this proof, we use the notations (s) = (s(( and (s(())) By definition, we set
s' = arg mRR Ps(s) and 3* = arg min,eR (s(s), where 3 = (1-a)(++K/m) First, by S ā(x) mmaxxxxax...- (2. 0) S log2
we have
(s(s) - PP(s)
= 3 Σ (Ō(S: - s) - m -8,0) + (1 - BB)
Σ
(ā(s - S:) mmx(s - S). + 11 (s so)
2
(27)
1=1
1=1
n3 log 2
μ (s -80)²
Ri
and (a(s) ps(s) 2 (s - s0)². By p-strong convexity and (s*) = 0, we have
~a(s") - pa($*) 2 (8" - -8
(28)
We next bound the term (s()*) ) (3*) as follows:
مs(s") ~²(8*) p3(5*) D3(5") ps(s") ps(s*)
n nlog? 2
(s" s0)² + pp(s" =3(
n log 2 K
+ " (s" 3 Pp( Po(
(29)
n mogg? 2
(s" sp)
1 (3" s0)
2
(6) n log 2
1 2
+
2 C0>
K
where (a) is due to pa(s*) S ps($*) by the definition s", and (b) is by Assumption 4.1. Finally, we have
2 (0a(s")- - P=((*)) < 2n + 6
(s' -5) 1
(30)
This yields the desired result.
A.2. Proof of Theorem 4.4
We have (5(T) s51 S (5(T) + 13 -s1 (T) + co. yielding
g(T) - E0 S S 5(F) + (T) (T) t
(31)
Then, for a data point (X, Y) drawn from P in (1), we have
(y e (X-DDC(X(D)) P ((xXX)) Y) (T) ( + t0) 2 Y) S $**).
(32)
Since s" is the empirical (1 - a1 + have P (s(X, Y) x*) 2 ax which implies the desired result.
(4) and by [Theorem 4.3, Lu et al., 2023] with wy o ny we
A.3. Proof of Theorem 5.2
Define the spectral gap o = A2 W Then, the typical result of the consensus convergence in Xiao & Boyd (2004) yields the inequality
Σ kEV
|
pl s (1 - n0)2
(33)
kev
12

---

Distributed Conformal Prediction via Message Passing
In other words, the consensus error decays exponentially.
(T) Let the histogram error as 6 = k x. To simplify the notation, we denote Ma,k = a,k
H.DCP c = cH-DCP, Si,k
( Y(,)) as the i-th quantized score on device k; and S (aa),) as the quantized score of the test point.
By definition of &s we have
2 (1- a) + K
Ma.k = min
m E
[M]
te
1=1
min
m E [M]
Σ
+ C,k
2 (1 - a)(1 +
(34)
==1
a)( + K ) + Σ i,k
min
E m
[M]
Σ
2 (1
1=1
Following the technique in (Lu et al., 2023), let wk
n and define the event F. as k
E = E V, (1), (2) STa (ma(ttt))..) = ($1, 82,60 sm.+1
(35)
where {81, 11, are the order statistics of the scores. For each device k. we also define be (7) = 1(Six S /- By the definition of mars Mf
(2") 1-th smallest score in U (5, leading to ma. is the [[1 a) + K) + me Em* Ci,
m
ma,k
bk
(1 an + K) +
(36)
M
A=
Then, we have
P (SSea
Stes I
Ma.k
FF.
=
Σ k=
Wk P
(Sues
S
Ma.k
(S..t....,
Stea are exchangeable, F)
M
M
K
by( Ma.k)
min
1,
Wik
T1 + 1
(37)
(n + K) + me Eie ii
min
1,
n K
(T)
n6 ni Σ i,k
min
1.1
n K
We next bound the RHS. Using min(x, y} y + --
we have
2
P. (Sest 5
Ma.k M
[E
0
+
1 ITE
Σ
Ma.k (T))
1=1 Eik
1
ne
12 Σ Mark (T)
i=1
a
2
+ K
2
n - K
(T)
ne
1
1=
2
K
K
TEE
2
nc
n
Max
(T)
n²
mark
(T)
2
2
n +
n1
K
n +
K
i,k
+
in
+
K)2
i
(38)
13

---

Distributed Conformal Prediction via Message Passing
2
Next, we bound the term
Ei=1"
1,k
as
ma.k
M S M
Σ
S Ma,k
Σ
(e (0
(e ( S M
(39)
where the first inequality follows from Jensen's inequality. This directly implies
Σ a
(T) E,
Σ
iill
Ma.k
(T)
VMIe ( Furthermore, by the convergence of consensus (33), we have
||e
1 < Σ l (T) 1
S (1-
2T
1 - pll & K(1 - no)
2T
max REV
1
-pl?.
(40)
KEV
KEV
The last term x
pll can be bounded as, for any E V,
2 K
o (0)
-112
2
1
2< x,,1
(| 112 + -11x;112)
(41)
K
j=1
j=1
To bound | we first recall that 2t
Kng Pk. where Pk = [PI, ,.M. with Pm, = 1/nx Ee T(T(S
PMM,K]
=
m/M}. 0 S Pm, I 1 and 1 PD: 1. Then, we have
K2n n2
K2n
M
K2n
M
n2n
||00211
1
112
n
(pm.k)
n
Pm.
n2
(42)
m=1
m=1
Thus,
le (T) 12
2 (1
m2) 27
1 K
(43)
n22
To simplify the notation, we define the constant
A ny nVM M
2K3(1 no) 27
n2)22
1 K
K
n
K
j=1
(44)
K V 2K (1 T00)
K n2
max KEV
7
n2 + K
K 1=1
Combining the above bounds, we have
P (Sest <
Ma.k M
E
2 1
1
a
NE
A 1 ( 2/ (
ThE
2A
a
TEE
+
(45)
2
+
K
2
Tt + K
+ K
Let the RHS of (45) equal to 1 a. yielding
n2 K A.
=
(46)
Finally, the coverage guarantee of H-DCP follows
P (Yieu CH-DCP (Xuel = P (See S
Ma.k = Eg [P
iS S
Mark
2 1 - aa E
(47)
M
M
B. Additional Experimental Results
B.1. Comparing with SOTA on star topology
In the special case of a star topology. the communication cost of Q-DCP coincides with FCP, while H-DCP reduces to WFCP. Experimental results with = 0.1, comparing Q-DCP and H-DCP with FCP (Lu et al., 2023), FedCP-QQ (Humbert et al., 2023), and WFCP (Zhu et al., 2024), can be found in Table These results show that the proposed protocols have comparable performance as the state of the art in terms of coverage and set size in the special case of a star topology. However, in contrast to existing schemes, H-DCP and Q-DCP apply to any network topology.
14

---

Distributed Conformal Prediction via Message Passing
Table Coverage and size for Q-DCP, H-DCP, FCP, WFCP, and FedCP-QQ under CIFAR100
topology with 0.1.
Q-DCP
H-DCP(WFCP)
FCP
FedCP-QQ
Coverage (:sstd)
0.913 + 0.01
0
0.918 + 0.01
0.996 + 0.003
Set Size (#bttd)
11.35 + 0.89
12.16 1.47
11.98 + 0.99
45.32 + 7.22
B.2. Convergence Results for Q-DCP and H-DCP
Setting Eo 0.1, Fig. 6 shows the coverage and set size versus the number of ADMM iterations I'' for centralized CP and for Q-DCP on different graphs. We specifically consider the complete graph, torus, star, cycle, and chain, which are listed in order of decreasing connectivity. While coverage is guaranteed for any number of iterations T, Q-DCP is seen to require more rounds to achieve efficient prediction sets on graphs with weaker connectivity levels. Furthermore, Q-DCP achieves performance comparable to CP on all graphs at convergence.
1.00
100
Normalized set: size
Q-DCP
0.98
complete torus
Coverage
0.96
star eycle
0.94
0.92
0.90
10-1
102
10a
10
102
103
10
ADMM Iterations (7)
ADMM Iterations (7)
Figure 6. Coverage and normalized set size versus the number of ADMM iterations for CP and Q-DCP (a = 0.1 and 6g = 0.1).
Fig. 7 shows coverage and set size performance versus the number of consensus iterations for H-DCP on different graphs Graphs with lower connectivity are observed require more consensus iterations give efficient prediction as in the case of Q-DCP presented in Fig. 6.
1.00
10"
Normalized set size
H-DCP
0.98
complete
Coverage
torus
0.96
star
cycle
chain
0.94
0.92
0.90
10-1
10
102
10a
10 Consensus Iterations (I)
10
1
Consensus Iterations
(I)
Figure 7, Coverage and normalized set size versus iterations T for CP and H-DCP (a = 0.1),
B.3. Scalability and sensitivity of Q-DCP and H-DCP for network size
To validate the proposed method on a larger network, we considered network with K 100 devices, each of which includes data from a distinet class setting T 3000 for both H-DCP and Q-DCP (with 0.5), experimental results can be found in Fig. 8 and Fig. 9. These results demonstrate that the proposed schemes are scalable to larger networks.
To evaluate the sensitivity of the performance of to the choice of Ep. we have evaluated coverage and set size for Q-DCP on Erdös-Rény: Rényi graphs with an increasing number of devices K, in which each edge is included in the graph with fixed probability 0.5. The 100 classes CIFAR100 are divided (almost) equally among the devices (without replacement). Other parameters are the same as Sec. For a 0.1 and T 3000, experimental result can found Fig. 10 with
15

---

Distributed Conformal Prediction via Message Passing
1.0
100
CP
Normalizen sel: size
Q-DCP
0.8
chaan cycle
Coverage
0.6
star torus
complete
0.4
10"2
0.2
10^3
0.0
0.3
0.5
0.1
0.3
0.5
0.7
0.9
1-a
1-a
Figure 8, Coverage and normalized set size versus coverage level 1 satisfied 100).
for CP and Q-DCP under CIFAR100 when Assumption 4.1
1.0
Normalizer lized set. size
H-DCP
chain
cycle
Coverage
10
star
complete
10-2
10-3
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7 0.9
1
1-a
Figure Coverage and normalized set size versus coverage level for CP and H-DCD under CIFARIOO (K 1000.
co and Fig. 11 with cp 0.1. The level of connectivity increases with as the average spectral gap increases from 0.44 to 0.68. As result, fixing T, the set size decrease the level of connectivity increases. This observation is robust with respect to the choice of hyperparameter ég. However, verified by these results, the optimal choice of eg depends on the size of the network. In practice, for 1, Assumption 4.1 is satisfied for all values of K between 20 and 80, and thus Proposition 4.3 guarantees convergence to the target coverage probability 1 = 0.9 when T is large enough. This is not the case for cg = 0.1, in which case Assumption 4.1 violated as grows larger.
0.40
0.98
ormalizzd set size
0.35
CP
Q DCP
Coverage
0.96
0.30
0.94
0.25
0.20
0.92
0.15
0.90
0.10
20
40
80
40
80
Number of Devices
Number of Devices
Figure 10. Coverage and normalized size versus number of devices K for CP and Q-DCP under CIFAR100 Erdös Rényi graph
with connect probability 0.5 (a 0.1,T 3000, é = 1).
B.4. Ablation studies for Q-DCP
Fig. 12 to 14 show the effects of different choices of the smoothness parameter λ and the regularization parameter μ the coverage guarantee and set size for the torus graph, respectively. Fig. 12 shows that small will lead to an inefficient prediction set due to the inaccurate approximation of ReLU, while large kappa will lead to a slow convergence speed of the ADMM yielding an inefficient prediction set as well. Fig. 13 demonstrates that a small j causes a low ADMM convergence rate making the prediction set conservative. Fig. 14 shows that under the poor choices of su and 6g as in Fig. 3, in which Assumption does not satisfied. One can observe that small y gives the satisfaction of the coverage condition, while large
16

---

Distributed Conformal Prediction via Message Passing
Normalized aiized set size
0.35
0.96
0.30
DCP
Coverage
0.94
0.25
0.92
0.20
0.90
0.15
20
40
60
80
20
40
60
80
Number of Devices
Number of Devices
Figure Coverage and normalized set size versus numher devices K for CP and Q-DCP under CIPAR1O0 on Frdós-Rényí graph with connect probability 0.5 (a 0.1,7
3000, 0.1).
1.00
109
Normalized set size
0.98
Coverage
0.96
0.94
0.92
0.90
10-1
10
10a
10
10
Figure 12. Coverage and set size versus é for Q-DCP. (Torus graph with 1000, a = 0.1, sp
and cp = 0.1)
leads to the solution of ADMM nearly same as so. yielding the violation of the coverage condition.
B.5. Ablation study for H-DCP
Fig. 15 shows the coverage and set size versus quantization level M for H-DCP different graphs. One can observe that under limited consensus iterations, increasing the quantization level A/ can make the estimated quantiles more accurate thus potentially providing more efficient prediction sets. On the flip side, it will lead to larger error bound of the consensus and may violate the efficiency of the prediction on graphs with poor connectivity.
B.6. Experimental results on PathMNIST
PathMNIST includes 9 classes and 107, 180 data samples in total (89, 996 for training. 10, 004 for validation, 7, 180 for test). Medical datasets involve private and sensitive information, which are usually distributed over siloed medical centers, making a decentralized implementation practically relevant.
To this end, we trained small-resnetl4 as the shared model, and we considered setting with 8 devices. Seven the devices have data from only one class, while the last device stores data for the remaining two classes. For Q-DCP, the number of ADMM communication rounds was set T 8000, and the number of consensus iterations and the quantization level for H-DCP were set T' 80 and M 100. This way, both Q-DCP and H-DCP are subject to the same communication costs (in bits). Other settings remain the same as in Sec. 6. Results on coverage and normalized set size versus coverage level for Q-DCP and H-DCP, can be found in Fig. 16 and Fig. 17, respectively. These experimental results confirm the efficiency of the proposed methods for applications of interest.
17

---

Distributed Conformal Prediction via Message Passing
1.00 *AMH
109
34995
Normalized size
Coverage
0.96
0.94
0.92
0.90
10-1
10a
10
10a
10a
Figure 13. Coverage set size versus μ for Q-DCP. (Torus graph with 1000, a 0.1, 80
and co 0.1)
1.00 944649
109
Normalizze set. size
0.95
Coverage
0.90
0.85
10-1
0.80
10a
10P
103
10a
Figure 14. Coverage set size versus / for Q-DCP. (Torus graph with
1000, a 0.1, mingey Q((1 - a)(1 +
K K/n); (Sca (11)) and co 10-4)
1.00
10
Normalized set size
0.98
CP
Coverage
0.96
chain cycle
0.94
torus
0.92
complete
10a
104
10a
10*
Quantization Level (M)
Quantization Level (Mr)
Figure 15. Coverage and set size versus quantization level M for H-DCP. (T = 150 and = 0.1)
1.0
Normalized set size
109
Q-DCP
0.8
cycle
Coverage
0.6
toras complete
10-1
0.4
0.2
0.0
10
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
1-a
1
Figure 16. Coverage and normalized size versus coverage level for CP and Q-DCP under PathMNIST.
18

---

Distributed Conformal Prediction via Message Passing
1.0
Normalized set size
H-DCP
0.8
cycle
Coverage
0.6
star
complete
10-2
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
1
1
Figure 17. Coverage and normalized set size versus coverage level for and H-DCP under PathMNNST.
19


Reviews:
[{"review_id": "HLDrEJfiO1", "reviewer": "Reviewer_6Gbu", "summary": "This paper addresses the challenge of conformal prediction in decentralized settings where multiple devices have limited calibration data and can only communicate with neighboring devices over arbitrary graph topologies. The authors propose two methods for distributed conformal prediction: Quantile-based Distributed Conformal Prediction (Q-DCP) and Histogram-based Distributed Conformal Prediction (H-DCP). Q-DCP employs distributed quantile regression enhanced with smoothing and regularization terms to accelerate convergence, solving the problem via ADMM. H-DCP uses a consensus-based histogram estimation approach, obtaining the global histogram of quantized calibration scores. Both methods provide theoretical coverage guarantees, with H-DCP offering hyperparameter-free guarantees at the cost of higher communication overhead.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > The experiments are limited to a single dataset (Cifar100). Including additional datasets...\n\n   Following your advice, we have evaluated the proposed scheme on a healthcare dataset, namely [PathMNIST](https://medmnist.com/). PathMNIST includes $9$ classes and 107,180 data samples in total. \n\n   We considered a setting with $K=8$ devices. Seven of the devices have data from only one class, while the last device stores data for the remaining two classes. For Q-DCP, we set $T=8000$, and for H-DCP, we set $T=80$ and $M=100$. This way, both Q-DCP and H-DCP are subject to the same communication costs (in bits). Other settings remain the same as in the paper. Experimental results, which can be found  [here](https://anonymous.4open.science/r/ICML_Rebuttal-AE74/Rebuttal_figures_and_tables.pdf) in Figures 1 and 2, confirm the efficiency of the proposed methods for applications of interest.\n\n2. > Could the algorithms be adapted to handle asynchronous updates or device dropouts?\n\n   Leveraging existing literature on decentralized optimization and consensus, Q-DCP and H-DCP could indeed be extended to the above settings\n\n   - Q-DCP: Q-DCP is based on the ADMM protocol. An asynchronous version of ADMM was studied in [R1] for distributed convex optimization problems over a large-scale network with arbitrary topology. This approach may be applicable to the pinball loss minimization problem (7), yielding a generally slower convergence than with synchronous communications [Theorem 3.2, R1]. A setting with time-varying graphs, modeling communication outages, was studied in [R3] via first-order methods, which may also be applicable to problem (7).\n   - H-DCP: Asynchronous consensus algorithms with linear convergence rate were studied in [R2]. These may be leveraged to extend H-DCP to asynchronous settings. Furthermore, consensus protocols have also been widely studied for time-varying graphs [R4].\n\n   [R1] E. Wei and A. Ozdaglar, \"On the $\\mathcal{O}(1/k)$ Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers,\" *2013 IEEE GlobalSIP*, 2013.\n\n   [R2] Y. Tian, Y. Sun and G. Scutari, \"Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization,\" in *IEEE Trans. Autom. Control*., vol. 65, no. 12, pp. 5264-5279, Dec. 2020.\n\n   [R3] A. Nedić and A. Olshevsky, \"Distributed Optimization Over Time-Varying Directed Graphs,\" in *IEEE Trans. Autom. Control*., vol. 60, no. 3, pp. 601-615, March 2015.\n\n   [R4] F. Xiao and L. Wang, “Asynchronous Consensus in Continuous-Time Multi-Agent Systems With Switching Topology and Time-Varying Delays,” *IEEE Trans. Autom. Control*., vol. 53, no. 8, pp. 1804–1816, Sep. 2008.\n\n3. > the initialization of both methods appears to require some coordination...\n\n   In experiments, we choose the consensus matrix $\\boldsymbol W$ in the standard form (See the first paragraph of Section 6.3). For this case, the eigenvalues of the Laplacian matrix $L$ can be obtained efficiently in a fully decentralized manner. See page 7 lines 340-348 (left) and reference [R5]. No other initialization settings for Q-DCP or H-DCP are required by coordination.\n\n   [R5] P. Di Lorenzo and S. Barbarossa, \"Distributed Estimation and Control of Algebraic Connectivity Over Random Graphs,\" in *IEEE Trans. Signal Process*., vol. 62, no. 21, pp. 5615-5628, Nov.1, 2014.\n\n4. > How would the approaches need to be modified for scenarios where devices have different locally trained models...\n\n   If the devices hold different local models, collaborative inference would have to be based on a different class of protocols. As an example, each device $k$ could first construct a local CP set $\\mathcal{C}_k$ using the local model and data. Then, the CP sets could be aggregated via communications, which is a non-trivial problem that has been studied in [R6] and their later work using majority vote strategies. A fully decentralized implementation of these protocols in an arbitrary topology is an open problem. It is also important to note that these types of protocols would generally yield less efficient prediction sets when applied to settings in which agents share the same model [Theorem 2.8, R6].\n\n   [R6] Gasparin, Matteo, and Aaditya Ramdas. \"Merging uncertainty sets via majority vote.\" *arXiv:2401.09379*, 2024.\n\n5. > Could the Q-DCP approach be extended to provide localized or conditional coverage guarantees...\n\n   Following [R7], the localized coverage condition could be equivalently stated as Eq. (2.3) in [R7]. Accordingly, [R7] suggests approximating the localized coverage condition by solving the generalized optimization problem (2.4) in [R7]. It may be possible to generalize Q-DCP to address this problem, rather than problem (7) in our submission, in a decentralized way. Ensuring localized coverage opens up interesting research directions for future extensions of our work.\n\n   [R7] Gibbs I, Cherian JJ, Candès EJ. Conformal prediction with conditional guarantees. *arXiv:2305.12616*. 2023.", "claims_and_evidence": "The claims made in the paper are well-supported by theoretical analysis and empirical evidence. The theoretical results (Theorems 4.4 and 5.2) provide formal coverage guarantees for both proposed methods, with clear derivations and reasonable assumptions. The experimental results confirm these guarantees and illustrate the performance trade-offs across different network topologies, sample sizes, and hyperparameter settings. The comparison between Q-DCP and H-DCP regarding communication overhead versus hyperparameter sensitivity is particularly well-substantiated.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem. The authors use standard metrics in conformal prediction (coverage rate and prediction set size/inefficiency) to evaluate performance. The experimental setup using Cifar100 data distributed in a non-i.i.d. manner across devices is reasonable for demonstrating the methods' effectiveness. The comparison across different network topologies (chain, cycle, star, torus, and complete graph) provides insights into how connectivity affects performance.", "theoretical_claims": "The theoretical claims in the paper appear sound. The paper provides detailed proofs for the main theorems (Theorems 4.4 and 5.2) in the appendix, establishing coverage guarantees for both Q-DCP and H-DCP. The proofs build on established results in distributed optimization and consensus algorithms, adapting them to the conformal prediction setting. The coverage guarantee for Q-DCP requires assumptions about parameter initialization that are carefully stated and verified in experiments.", "experimental_designs_or_analyses": "The experimental design is comprehensive and appropriate. The authors evaluate their methods on Cifar100 data distributed across 20 devices in a non-i.i.d. manner, with each device assigned 5 unique classes. The evaluation covers various network topologies, hyperparameter settings, and communication budgets. The experiments verify theoretical results and provide practical insights on trade-offs between methods. The ablation studies effectively demonstrate the impact of key hyperparameters on performance.", "relation_to_broader_scientific_literature": "The paper extends previous work on federated conformal prediction (e.g., FedCP-QQ, FCP, WFCP) which primarily addressed star topologies, to the more challenging case of arbitrary graph topologies. It integrates ideas from distributed optimization (ADMM), consensus algorithms, and conformal prediction. The work contributes to the growing literature on reliable and uncertainty-aware distributed machine learning, with connections to federated learning and distributed statistical estimation.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths：\n1. The paper presents a novel and theoretically sound approach to distributed conformal prediction that extends beyond the star topology assumed in prior work.\n2. The authors provide strong theoretical guarantees with clear conditions under which they hold, along with empirical validation.\nThe comparative analysis between Q-DCP and H-DCP offers valuable insights into the trade-offs between communication efficiency and hyperparameter sensitivity.\n3. The experimental evaluation is thorough, covering various network topologies, hyperparameter settings, and demonstrating convergence properties.\n\n\nWeaknesses：\n1. The experiments are limited to a single dataset (Cifar100). Including additional datasets, particularly those from domains mentioned as motivating applications (healthcare, IoT, autonomous vehicles), would strengthen the empirical evaluation.\n2. The practical implementation details for large-scale distributed systems are somewhat limited. More discussion on handling device failures, communication delays, or asynchronous updates would enhance practicality.\n3. While the methods address device-to-device communication, the initialization of both methods appears to require some coordination (e.g., for H-DCP, setting the consensus matrix W), which could be challenging in fully decentralized settings.\n4. The study focuses on the post-hoc calibration of a shared pre-trained model, but does not explore scenarios where devices have different local models, which would be relevant for many real-world applications.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. How would the proposed methods perform if devices have heterogeneous computational capabilities or experience intermittent connectivity? Could the algorithms be adapted to handle asynchronous updates or device dropouts?\n2. The current work assumes all devices share the same pre-trained model. How would the approaches need to be modified for scenarios where devices have different locally trained models, as might be the case in federated learning settings?\n3. Could the Q-DCP approach be extended to provide localized or conditional coverage guarantees rather than just marginal coverage? This would be valuable for handling distribution shifts between devices.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mBeytorsyx", "reviewer": "Reviewer_7tEz", "summary": "The paper introduces two novel algorithms for distributed conformal prediction in decentralized networks. The Q-DCP employs ADMM to solve a distributed quantile regression problem with a smoothed pinball loss $ \\tilde{\\rho}\\_\\gamma(s)$ (incorporating a smoothing function $ \\tilde{g}(x)$ and regularization term $ \\frac{\\mu}{2}(s-s\\_0)^2$). After $T$ iterations, the device compute an average quantile estimate  $\\bar{s}(T)$ and the authors derive an error bound $\\epsilon\\_{Q-DCP}$ such that $|\\bar{s}(T) - s^*| \\leq \\epsilon\\_{Q-DCP}$, ensuring the prediction set satisfies the coverage guarantee (Thm 4.4). The second one (or H-DCP) leverages a consensus-based histogram estimation approach. Each device quantizes its calibration scores into $M$ levels and exchanges these histogram vectors with its neighbors, allowing them to compute an average global histogram. From this, a quantile is estimated, and Theorem 5.2 guarantees that with error bound $\\epsilon\\_{H-DCP}$ linked to the consensus convergence, the resulting prediction set meets the desired coverage $P(Y \\in C(X|D)) \\geq 1-\\alpha$.\n\n\n***\n\n I appreciate the author's efforts to address my concerns. Based on the explanation and promised final revisions I increased my rating to 3", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > The largest network tested has only 20 devices...\n\n   To validate the proposed method on a larger network, we considered a network with $100$ devices, each of which collects data from a distinct class, setting $T=3000$ for both H-DCP and Q-DCP (with $\\epsilon=0.5$). The experiment results, which can be found [here](https://anonymous.4open.science/r/ICML_Rebuttal-AE74/Rebuttal_figures_and_tables.pdf) in Figures 3 and 4, demonstrate that the proposed schemes are scalable to larger networks.\n\n2. > The paper presents mean results but does not report confidence intervals...\n\n   Thank you for suggesting adding error bar in the figures. You may find, e.g.,  Fig. 2 in the original draft, with an error bar of 95%-interval added [here](https://anonymous.4open.science/r/ICML_Rebuttal-AE74/Rebuttal_figures_and_tables.pdf) (See Figure 5).\n\n3. > No comparison with other SOTA decentralized uncertainty quantification methods...\n   >\n   > How does Q-DCP compare against recent federated conformal prediction...\n\n   To the best of our knowledge, all previous distributed CP schemes applied only to the federated setting with a parameter server. Only when focusing on the special case of a star topology can we then compare the performance of the proposed protocols to the existing ones we are aware of, namely FedCP-QQ (Humbert et al., 2023), FCP (Lu et al., 2023) and WFCP (Zhu et al. (2024b)).\n\n   In this special case, the communication cost of Q-DCP coincides with FCP, while H-DCP reduces to WFCP. Experimental result with $\\alpha=0.1$ can be found [here](https://anonymous.4open.science/r/ICML_Rebuttal-AE74/Rebuttal_figures_and_tables.pdf) in Table 1. These results, obtained at convenience, show that the proposed protocols have comparable performance to the existing state of the art in terms of coverage and set size in a star topology. However, in contrast to existing schemes, H-DCP and Q-DCP apply to arbitrary network topology.\n\n4. > The application of message passing algorithms in optimization is not novel, such as prior work [1].\n\n   Please note that this interesting prior work [1] focuses on a fully centralized setting. This is fundamentally different from our decentralized setup. Accordingly, \"message passing\" in [1] refers to AMP, a Bayesian inference approach, while \"message passing\" in our work refers to gossip-style averaging consensus among distributed agents.\n\n5. > The presentation of this paper fails to handle mathematical complexity effectively.... \n   >\n   > the authors sometimes introduce notation without prior explanation...\n\n   We believe that our designs are formally well-motivated, and are validated by our theory.\n\n   - For Q-DCP: As discussed in line 194-202 (right), the smooth function $\\tilde{g}(\\cdot)$ and the regularization term in Eq. (8) aims for strong convexity, so as to ensure the linear convergence rate of ADMM, which has been theoretically verified in Proposition 4.3.\n\n   - For H-DCP: As discussed in lines 292-300 (left), the calibration score is quantized so as to support linear average consensus on the local histograms of the scores. As theoretically proved in Theorem 2, this ensures linear convergence and guarantees coverage.\n\n   The notation $Z_i$ in (8) was a typo, and it should be $S_i$. The notation $E$ refers to the number of edges $E=|\\mathcal{E}|$.\n\n6. > I think integrating the pseudocode... \n   >\n   > before equation (31), do you mean...\n\n   For the equation before Eq. (31), yes, you are correct. We would be happy to fit algorithm tables in the main text.\n\n7. > Does your Q-DCP’s hyperparameter sensitivity worsen as the e.g., network grows?\n\n   The key hyperparameter to be selected in Q-DCP is $\\epsilon_0$. To evaluate the sensitivity of the performance to the choice of $\\epsilon_0$, we have evaluated Q-DCP on Erdős–Rényi graphs with an increasing number of devices $K$, in which each edge is included in the graph with a probability of 0.5. The 100 classes of CIFAR100 are uniformly at random (w/o replacement) divided among the $K$ devices. Other parameters are the same as the draft.\n\n   For $\\alpha=0.1$ and $T=3000$, experimental results can found [here](https://anonymous.4open.science/r/ICML_Rebuttal-AE74/Rebuttal_figures_and_tables.pdf) in Figure 6 with $\\epsilon_0=1$ and in Figure 7 with $\\epsilon_0=0.1$. The average spectral gap increases with $K$ from 0.44 to 0.68. As a result, by fixing $T$, the set size decreases with the level of connectivity. This observation is robust against the choice of $\\epsilon_0$. However, as verified by these results, the optimal choice of $\\epsilon_0$ does depend on the size of network. In practice, for $\\epsilon_0=1$, Assumption 4.1 is satisfied for all values of $K$ between $20$ and $80$, and thus convergence to the target coverage probability $1-\\alpha=0.9$ is guaranteed when $T$ is large enough (see Proposition 4.3). This is not the case for $\\epsilon_0=0.1$, when Assumption 4.1 is violated as $K$ grows larger.", "claims_and_evidence": "they are generally convincing", "methods_and_evaluation_criteria": "While CIFAR-100 is a widely used benchmark, this paper does not test its methods in real-world distributed settings or more diverse datasets.", "theoretical_claims": "I didn't check the proofs line-by-line but they appear correct. The convergence error of ADMM, the bias from the smoothing approximation, etc, are just standard route in optimization analysis.", "experimental_designs_or_analyses": "-  the largest network tested has only 20 devices, which is very small for real-world decentralized applications\n\n- The paper presents mean results but does not report confidence intervals or variance across multiple runs, which make it unclear whether observed differences are statistically significant or just noise. No comparison with other SOTA decentralized uncertainty quantification methods, such as federated conformal prediction or Bayesian approaches.", "relation_to_broader_scientific_literature": "This work builds upon existing work in split conformal prediction, while also incorporating ideas from decentralized/federated optimization and message passing.", "essential_references_not_discussed": "The application of message passing algorithms in optimization is not novel, such as prior work [1].\n\n[1] Clarté, Lucas, and Lenka Zdeborová. \"Building Conformal Prediction Intervals with Approximate Message Passing.\" arXiv:2410.16493", "other_strengths_and_weaknesses": "- While H-DCP somehow removes hyperparameter sensitivity, it suffers from a significantly higher communication cost per iteration due to the need for transmitting full histograms.\n\n- The presentation of this paper fails to handle mathematical complexity effectively. While the problem formulation is reasonable to me, many of the introduced techniques appear somewhat ad hoc and lack a compelling motivation. Furthermore, the authors sometimes introduce notation without prior explanation, like $Z_i$ in (8), $E$ in line 230,231, etc", "other_comments_or_suggestions": "- I think integrating the pseudocode from the appendix into the main body could improve readability and help readers grasp the key ideas more effectively\n\n- before equation (31), do you mean $\\left|\\bar{s}^{(T)}-\\hat{s}^*\\right|+\\left|\\hat{s}^*-s^*\\right| \\leq \\epsilon^{(T)}+\\tilde{\\epsilon}_0$?\n\n- equation (35), $E$ is already used\n\n- equation (37),  the first line uses different probabilistic notation", "questions_for_authors": "- How does Q-DCP compare against recent federated conformal prediction approaches like [a,b] in terms of accuracy, communication cost, and robustness?\n\n[a] Lu, Charles, et al. \"Federated conformal predictors for distributed uncertainty quantification.\" International Conference on Machine Learning, 2023.\n\n[b] Plassier, Vincent, et al. \"Conformal prediction for federated uncertainty quantification under label shift.\" International Conference on Machine Learning, 2023.\n\n\n- Does your Q-DCP’s hyperparameter sensitivity worsen as the e.g., network grows?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wTIAAN0Eiq", "reviewer": "Reviewer_wc5C", "summary": "This paper proposes a distributed way of achieving conformal prediction intervals. It extends the current literature by looking at graphs other than a star graph, and by looking at histogram summaries in addition to quantiles.\n\n\"## update after rebuttal: I have changed my recommendation to accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > The benchmarking seems ok; a standard Cifar data set is used. It could be interesting to also look at synthetic examples.\n\n   Please refer to the rebuttal of Reviewer 6Gbu for details on experiments on a different data set.\n\n2. > It is not clear how one can validate Assumption 4.1, that is, how one would find $\\epsilon_0$ which is non-trivial. The assumption seems to be key though.\n\n   Indeed, as indicated in our paper, the difficulty in setting hyperparameter $\\epsilon_0$ is one of the key motivations for introducing H-DCP, which does not require hyperparameter tuning. Please refer to page 6 lines 281-291(left) for further discussion on this point.\n\n3. > The study is a comparison but perhaps more can be said. From Figures 2-4 it seems that all methods fail on the chain graph, in that they give prediction intervals which are far too large. What is the spectral gap for this graph? Is there an explanation? If one would want to apply any of the proposed algorithms, how could one check that they work well, are there guidelines?\n\n   The spectral gap of the chain graph is as low as $0.0123$, which is significantly smaller than other topologies. For example, the spectral gap of the star topology is $0.095$. As a result, as formalized by Proposition 4.3 and Theorem 5.2, the convergence in terms of communication rounds is decided by the spectral gap, which is thus slower for chain graphs.  It is indeed the results in Proposition 4.3 and Theorem 5.2 provide insightful guidelines about how various factors have an impact on the CP guarantee.\n\n4. > There could have been a mention of federated learning more generally.\n\n   We would be happy to add further reference on federated learning.\n\n5. > The figures are very difficult to read; there are star and torus?\n\n   We will increase the marker sizes of in the revised version.\n\n6. > What if the devices share both quantiles and histograms, could the method be improved?\n\n   This is an interesting question. Combining advantages of both schemes, one could indeed apply H-DCP first to obtain an estimate of true global quantile, which is then used as prior information in the ADMM problem solved by Q-DCP. This can help mitigating the reliance of Q-DCP on the choice of hyperparameter $s_0$.\n\n7. > If instead of sharing quantiles or histograms, the devices would share their CP intervals, would there be any mileage in that?\n\n   Sharing and merging their CP intervals is generally less efficient than computing a single set using all distributed data [R1, R2]. For example, supposing that we have $K$ prediction sets $\\\\{\\mathcal{C}\\_k\\\\}\\_{k\\in[K]}$ and merge them using majority vote as $\\mathcal{C}^M:=\\left\\\\{y\\in\\mathcal{Y}:1/K\\sum\\_{k=1}^K\\mathbb{1}\\\\{y\\in\\mathcal{C}\\_k\\\\}>\\tau\\right\\\\}$ for some $\\tau \\in [0,1)$. Then, by Theorem 2.1 in [R2], the majority vote procedure gives $1-\\alpha/(1-\\tau)$ coverage guarantee instead of $1-\\alpha$ (see also Theorem 2.8 in [R2]).\n\n   [R1] M. Gasparin and A. Ramdas, “Conformal online model aggregation,” May 02, 2024, *arXiv*: arXiv:2403.15527.\n\n   [R2] Gasparin, M. and Ramdas, A. (2024). Merging uncertainty sets via majority vote. arXiv preprint arXiv:2401.09379.\n\n8. > Why do you need i.i.d. data for each device? Usually exchangeable scores suffice...\n\n   We consider i.i.d. in the text to simplify the presentation. But indeed this assumption could be relaxed to exchangeability as done in [Assumption 4.1, Lu et al., 2023]. \n\n9. > In the experiments how is the inefficiency determined when the distribution of the data is not available?\n\n   We indeed do not have access to the distribution in the experiments. Therefore, the inefficiency defined as $\\mathbb{E}|\\mathcal{C}(X\\_{\\text{test}}|\\mathcal{D})|$ is estimated using test data by $$1/|\\mathcal{D}\\_{\\text{test}}|\\sum\\_{X\\_{\\text{test}}\\in \\mathcal{D}\\_{\\text{test}}}|\\mathcal{C}(X\\_{\\text{test}}|\\mathcal{D})|$$ in experiments.\n\n10. > Why did you choose the torus graph for Figure 5 and not one of the other graphs?\n\n    This choice is motivated by the fact that the spectral gap of torus graph with $20$ devices is in a moderate regime, providing a balanced setting between a complete graph and a cycle graph in terms of the spectral gap, which significantly affects the prediction performance in line with Theorem 5.2.", "claims_and_evidence": "The theoretical claims are clear and the proofs are plausible.", "methods_and_evaluation_criteria": "The benchmarking seems ok; a standard Cifar data set is used. It could be interesting to also look at synthetic examples.", "theoretical_claims": "The proofs seem ok.\n\nIt is not clear how one can validate Assumption 4.1, that is, how one would find epsilon_0 which is non-trivial. The assumption seems to be key though.", "experimental_designs_or_analyses": "The study is a comparison but perhaps more can be said. From Figures 2-4 it seems that all methods fail on the chain graph, in that they give prediction intervals which are far too large. What is the spectral gap for this graph? Is there an explanation? If one would want to apply any of the proposed algorithms, how could one check that they work well, are there guidelines?", "relation_to_broader_scientific_literature": "There could have been a mention of federated learning more generally.", "essential_references_not_discussed": "None come to mind.", "other_strengths_and_weaknesses": "The figures are very difficult to read; there are star and torus?", "other_comments_or_suggestions": "It would be good to mention split conformal prediction already in the introduction.\nIt would be good to detail the choice of W already in 5.1.\nWhat if the devices share both quantiles and histograms, could the method be improved? \nIf instead of sharing quantiles or histograms, the devices would share their CP intervals, would there be any mileage in that?", "questions_for_authors": "Why do you need i.i.d. data for each device? Usually exchangeable scores suffice (an assumption which can again be weakened, see work by Rina Foygel Barber et al) \n\nIn the experiments how is the inefficiency determined when the distribution of the data is not available? \n\nWhy did you choose the torus graph for Figure 5 and not one of the other graphs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TfeXwYlIYT", "reviewer": "Reviewer_iKT1", "summary": "This work studies CP in a decentralised inference setting, where multiple devices share the same pre-trained model, and each device has a local calibration data set (motivated by e.g. privacy constraints). Given a common input, the devices aim at producing a prediction set that includes the true label of the test data with probability $1 − \\alpha$. Two message-passing schemes are proposed for this Distributed CP (DCP) problem.\n\nWhile the star graph topology was considered in prior works, this paper considers graphs where each node communicates only with its neighbours over an arbitrary graph topology.\n\n-- update after rebuttal --\n\nThis is a well-written paper with solid theoretical contributions, so I maintain my evaluation. However, I continue to have reservations regarding the use of the terminology 'message passing' in the title. I would appreciate if the authors could address my questions listed under 'Other Strengths And Weaknesses' and 'Other Comments Or Suggestions' sections, not just those under the 'Questions For Authors' section.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we are happy to consider your valuable suggestions in **Other Strengths And Weaknesses** and **Other Comments Or Suggestions**. For the other questions, please find the point-to-point response below.\n\n1. > Do you require the calibration data to be iid across devices?\n\n   Please see our reply to comment 8 of Reviewer wc5C.\n\n2. > My understanding is that the constraint in (10) enforces the communication constraint based on the graph topology, is this correct?\n\n   Yes, this is correct. In practice, the constraint in the problem (10) is equivalent to $s_i=z_{ij},s_j=z_{ij},$ for all $(i,j)\\in \\mathcal{E}$, where, $s_i$'s is the local copy of the shared optimization variable $s$ at device $i$, and $z_{ij}$ is an auxiliary variable imposing the desired consensus constraint between neighboring devices $i$ and $j$.\n\n3. > line 175, right column: does hyperparameter tuning refer to tuning $\\mu$ and $\\kappa$?\n\n   Yes, this is correct.", "claims_and_evidence": "This paper is of high quality in terms of presentation and novelty. The theoretical claims are explained clearly and supported by proofs. I've gone through the proofs for Q-DCP and they seem correct.\n\nThe experimental results are also comprehensive and compelling.", "methods_and_evaluation_criteria": "Yes, the numerical experiments are rigorously designed. The proposed DCP methods are compared against the centralised CP as the benchmark, with graphs with different levels of connectivity.", "theoretical_claims": "I've gone through the proofs for Q-DCP and they seem correct. The proofs are well written.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "This paper ties together quite a few interesting ideas with relevance extending beyond CP to optimisation theory, distributed computing, federated learning, and privacy.\n\nA notable example is found in Q-DCP, where the authors transform the original objective (7) into a smooth, strongly-convex surrogate loss for accelerated convergence. This approach parallels the seminal adaptive regularisation technique from Bartlett, Hazan, and Rakhlin (2007), demonstrating how the paper builds upon established theoretical foundations while advancing them in new domains", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Title: A more precise and compelling title would better reflect the flexibility and novelty of the proposed DCP methods, and attract the intended readers. I’m not sure whether “message passing” is the best key word to use here because i) the main novelty is that arbitrary graph topologies are allowed instead of just simple star topologies, and ii) H-DCP doesn’t really use message passing?", "other_comments_or_suggestions": "- It might be beneficial to update the paragraph just above (23). Explain that the local vector $x_k$ represents the local estimate at device k of the global vector p. Add one sentence explaining why the update rule (23) is enforcing consensus among the devices and is therefore called the “linear consensus step”.\n\n- line 346: nitpick: did you want to compare 1 real number vs M real numbers as the communication overhead? If so, it’s perhaps more accurate to say M-dim real vector instead of M-dim histogram vector.", "questions_for_authors": "1. Do you require the calibration data to be iid across devices? \n\n2. My understanding is that the constraint in (10) enforces the communication constraint based on the graph topology, is this correct? Could you elaborate?\n\n3. line 175, right column: does “hyperparameter tuning” refer to tuning $\\mu$ and $\\kappa$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces two novel methods, Q-DCP and H-DCP, for distributed conformal prediction in decentralized settings with graph-based communication. The work is a significant extension of prior conformal prediction research, which focused primarily on star graphs, by addressing arbitrary graph topologies. The theoretical guarantees, including coverage bounds and convergence proofs, are rigorous and well-substantiated. The authors also provide experimental results to support their claims, exploring the trade-offs between the two methods in terms of communication cost, hyperparameter sensitivity, and efficiency under various graph structures.

The authors’ rebuttal meaningfully strengthens the submission. They addressed concerns about dataset limitations by adding experiments on PathMNIST, a healthcare dataset, and expanded the scale to 100 devices, demonstrating scalability and applicability to diverse real-world scenarios. They clarified key assumptions, such as the choice of the hyperparameter ε₀, and explained how H-DCP mitigates sensitivity to hyperparameter tuning. Additionally, they provided detailed insights into the impact of spectral gap on chain graph performance, offering a clear explanation for the observed inefficiencies.

While the paper still has some limitations, such as the lack of a direct comparison with other state-of-the-art methods in distributed uncertainty quantification and limited exploration of asynchronous communication or device heterogeneity, the rebuttal addresses these issues to a reasonable extent. The authors explained that no direct competitors exist for arbitrary graph topologies and highlighted how their methods subsume existing approaches in specific cases, such as star graphs. They also suggested feasible extensions to asynchronous settings and scenarios with locally trained models, providing valuable directions for future work.

In conclusion, this paper makes a substantial contribution to the field of distributed conformal prediction, offering strong theoretical and experimental support for its claims. The authors’ thoughtful responses and the additional experiments presented in the rebuttal further strengthen the paper. While some areas remain open for exploration, such as real-world deployment and performance on specific graph types, the overall quality and relevance of the work justify its acceptance.
Decision: Accept (poster)