<figure><img src="image_1.png" /></figure>

HAL
open science

# Marginal and training-conditional guarantees in one-shot federated conformal prediction

Pierre Humbert, Batiste Le Bars, Aurélien Bellet, Sylvain Arlot

► To cite this version:

Pierre Humbert, Batiste Le Bars, Aurélien Bellet, Sylvain Arlot. Marginal and training-conditional guarantees in one-shot federated conformal prediction. 2024. hal-04579882

HAL Id: hal-04579882

https://hal.science/hal-04579882

Preprint submitted on 18 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# Marginal and training-conditional guarantees in one-shot federated conformal prediction

Pierre Humbert, Batiste Le Bars, Aurélien Bellet, Sylvain Arlot

► To cite this version:

Pierre Humbert, Batiste Le Bars, Aurélien Bellet, Sylvain Arlot. Marginal and training-conditional guarantees in one-shot federated conformal prediction. 2024. hal-04579882

HAL Id: hal-04579882

https://hal.science/hal-04579882v1

Preprint submitted on 18 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Marginal and training-conditional guarantees in one-shot federated conformal prediction

Pierre Humbert<fnref n="1" />, Batiste Le Bars<fnref n="2" />, Aurélien Bellet<fnref n="3" /> and Sylvain Arlot<fnref n="1" />,<fnref n="4" />

**Abstract:** We study conformal prediction in the one-shot federated learning setting. The main goal is to compute marginally and training-conditionally valid prediction sets, at the server-level, in only one round of communication between the agents and the server. Using the quantile-of-quantiles family of estimators and split conformal prediction, we introduce a collection of computationally-efficient and distribution-free algorithms that satisfy the aforementioned requirements. Our approaches come from theoretical results related to order statistics and the analysis of the Beta-Beta distribution. We also prove upper bounds on the coverage of all proposed algorithms when the nonconformity scores are almost surely distinct. For algorithms with training-conditional guarantees, these bounds are of the same order of magnitude as those of the centralized case. Remarkably, this implies that the one-shot federated learning setting entails no significant loss compared to the centralized case. Our experiments confirm that our algorithms return prediction sets with coverage and length similar to those obtained in a centralized setting.

**Keywords and phrases:** conformal prediction, one-shot federated learning, prediction set, tolerance region, uncertainty quantification.

# 1. Introduction

## 1.1. Problem statement and motivation

We consider the one-shot federated learning (FL) set-prediction problem, where a set of agents connected to a central server try to compute a valid prediction set in only one round of communication, and without sharing their raw data [25].

Formally, assume that a data set $\mathcal{D}$ is distributed over $m \in \mathbb{N}^*$ agents connected to a central server. In addition, suppose that the server has an independent test point $(X, Y) \in \mathcal{X} \times \mathcal{Y}$ following the same distribution as the elements $(X_{i,j}, Y_{i,j})$ of $\mathcal{D}$ —which are assumed to be identically distributed—but whose outcome $Y$ is unobserved. The goal of the server is to compute a distribution-free valid prediction set for $Y$. One can aim at marginal validity, that is, for a given miscoverage level $\alpha \in (0, 1)$, constructing from $\mathcal{D}$ a set $\hat{C}(X)$ such that

$$ \mathbb{P}(Y \in \hat{C}(X)) \geq 1 - \alpha, \qquad (1) $$

whatever the data distribution. In addition, the set $\hat{C}(\cdot)$ must be computed in a single round of communication between the agents and the server to satisfy the one-shot constraint —a condition motivated by the fact that the number of communication rounds is often the main bottleneck in FL [27]. Note also that we want the set to be small

<footnote n="1">¹ Université Paris-Saclay, CNRS, Inria, Laboratoire de mathématiques d'Orsay, 91405, Orsay, France, e-mail: pierre.humbert@universite-paris-saclay.fr; sylvain.arlot@universite-paris-saclay.fr</footnote>

<footnote n="2">² Inria Paris - Ecole Normale Supérieure, PSL Research University, e-mail: batiste.le-bars@inria.fr</footnote>

<footnote n="3">³ PreMeDICaL project team, Inria, Univ Montpellier, France, e-mail: aurelien.bellet@inria.fr</footnote>

<footnote n="4">⁴ Institut Universitaire de France (IUF)</footnote>
# Marginal and training-conditional guarantees in one-shot federated conformal prediction

Pierre Humbert<fnref n="1" />, Batiste Le Bars<fnref n="2" />, Aurélien Bellet<fnref n="3" /> and Sylvain Arlot<fnref n="1" />,<fnref n="4" />

**Abstract:** We study conformal prediction in the one-shot federated learning setting. The main goal is to compute marginally and training-conditionally valid prediction sets, at the server-level, in only one round of communication between the agents and the server. Using the quantile-of-quantiles family of estimators and split conformal prediction, we introduce a collection of computationally-efficient and distribution-free algorithms that satisfy the aforementioned requirements. Our approaches come from theoretical results related to order statistics and the analysis of the Beta-Beta distribution. We also prove upper bounds on the coverage of all proposed algorithms when the nonconformity scores are almost surely distinct. For algorithms with training-conditional guarantees, these bounds are of the same order of magnitude as those of the centralized case. Remarkably, this implies that the one-shot federated learning setting entails no significant loss compared to the centralized case. Our experiments confirm that our algorithms return prediction sets with coverage and length similar to those obtained in a centralized setting.

**Keywords and phrases:** conformal prediction, one-shot federated learning, prediction set, tolerance region, uncertainty quantification.

# 1. Introduction

## 1.1. Problem statement and motivation

We consider the one-shot federated learning (FL) set-prediction problem, where a set of agents connected to a central server try to compute a valid prediction set in only one round of communication, and without sharing their raw data [25].

Formally, assume that a data set $\mathcal{D}$ is distributed over $m \in \mathbb{N}^*$ agents connected to a central server. In addition, suppose that the server has an independent test point $(X, Y) \in \mathcal{X} \times \mathcal{Y}$ following the same distribution as the elements $(X_{i,j}, Y_{i,j})$ of $\mathcal{D}$ —which are assumed to be identically distributed—but whose outcome $Y$ is unobserved. The goal of the server is to compute a distribution-free valid prediction set for $Y$. One can aim at marginal validity, that is, for a given miscoverage level $\alpha \in (0, 1)$, constructing from $\mathcal{D}$ a set $\hat{C}(X)$ such that

$$ \mathbb{P}(Y \in \hat{C}(X)) \geq 1 - \alpha, \qquad (1) $$

whatever the data distribution. In addition, the set $\hat{C}(\cdot)$ must be computed in a single round of communication between the agents and the server to satisfy the one-shot constraint —a condition motivated by the fact that the number of communication rounds is often the main bottleneck in FL [27]. Note also that we want the set to be small

<footnote n="1">¹ Université Paris-Saclay, CNRS, Inria, Laboratoire de mathématiques d'Orsay, 91405, Orsay, France, e-mail: pierre.humbert@universite-paris-saclay.fr; sylvain.arlot@universite-paris-saclay.fr</footnote>

<footnote n="2">² Inria Paris - Ecole Normale Supérieure, PSL Research University, e-mail: batiste.le-bars@inria.fr</footnote>

<footnote n="3">³ PreMeDICaL project team, Inria, Univ Montpellier, France, e-mail: aurelien.bellet@inria.fr</footnote>

<footnote n="4">⁴ Institut Universitaire de France (IUF)</footnote>
(for instance, with respect to the counting or the Lebesgue measure), a property called efficiency.

The probability in (1) is taken with respect to $(X, Y)$ and the data set $\mathcal{D}$. However, in practice, we only have access to one particular data set. Another quantity of interest is therefore the training-conditional miscoverage rate defined by

$$ \alpha(\mathcal{D}) := \mathbb{P}(Y \notin \hat{\mathcal{C}}(X) | \mathcal{D}), \qquad (2) $$

where the probability is now only taken with respect to the test point $(X, Y)$. Notice that $\alpha(\mathcal{D})$ is a $\sigma(\mathcal{D})$-measurable random variable and that the marginal guarantee (1) corresponds to a bound on the miscoverage rate (2) on average over all possible datasets. In other words, Eq. (1) is equivalent to a control on the expectation of the training-conditional miscoverage rate: $\mathbb{P}(Y \notin \hat{\mathcal{C}}(X)) = \mathbb{E}[\alpha(\mathcal{D})] \le \alpha$. However, the random variable $\alpha(\mathcal{D})$ can have high variance, and it is important to also control its deviation from the desired upper-bound $\alpha$ with high probability. For any $\alpha, \beta \in (0, 1)$, we are therefore also interested in constructing prediction sets with training-conditional coverage guarantees, that is, of the form

$$ \mathbb{P}(1 - \alpha(\mathcal{D}) \ge 1 - \alpha) \ge 1 - \beta. \qquad (3) $$

Prediction sets satisfying (3) are also known in the statistical literature as $(\alpha, \beta)$-tolerance regions or “Probably Approximately Correct” (PAC) predictive sets. This type of guarantee dates back to [63] and an overview can be found in [32]. More recent works on this subject include [8, 29, 47, 48, 61].

## 1.2. Related works

Our contribution takes place in the FL framework, a rather recent paradigm that allows training from decentralized data sets stored locally by multiple agents [27]. In this framework, the learning is made without exchanging raw data, making FL advantageous when data are highly sensitive and cannot be centralized for privacy or security reasons. So far, the design of FL algorithms has mainly focused on the learning step of statistical machine learning, the goal being to fit a (pointwise) predictor to decentralized data sets while minimizing the amount of communication [see e.g. 28, 37, 43]. However, quantifying the uncertainty in the prediction of these FL algorithms has not been widely studied yet.

Conformal prediction (CP) methods have become the state-of-the-art to construct marginally and conditionally valid distribution-free prediction sets [46, 54, 61, 62]. Unfortunately, one of the key steps of CP methods is the ordering of some computed scores, which is not possible in FL settings without sharing the full local data sets or performing many agent-server communication rounds. These methods are thus not well-suited to the constraints of FL in which agents process their data locally and only interact with a central server by sharing some aggregate statistics. Constructing a valid prediction set is even more difficult in the one-shot FL setting [14, 20, 36, 55, 65, 66] considered in this work, where only one round of communication between the agents and the server is allowed.

To our knowledge, [38] is the first paper considering the one-shot federated set-prediction problem with conformal prediction. Its idea is to locally calculate some quantiles of computed scores for each agent and to average them in the central server. Unfortunately, [38] does not prove that the corresponding prediction sets are valid and its method is non-robust, especially when the size of local data sets is small (see Appendix I.2 for more details). To address these issues, [25] has recently proposed a family of estimators called quantile-of-quantiles. The idea is that each agent sends to the server a local empirical quantile of its scores and the server aggregates them by computing a quantile of these
(for instance, with respect to the counting or the Lebesgue measure), a property called efficiency.

The probability in (1) is taken with respect to $(X, Y)$ and the data set $\mathcal{D}$. However, in practice, we only have access to one particular data set. Another quantity of interest is therefore the training-conditional miscoverage rate defined by

$$ \alpha(\mathcal{D}) := \mathbb{P}(Y \notin \hat{\mathcal{C}}(X) | \mathcal{D}), \qquad (2) $$

where the probability is now only taken with respect to the test point $(X, Y)$. Notice that $\alpha(\mathcal{D})$ is a $\sigma(\mathcal{D})$-measurable random variable and that the marginal guarantee (1) corresponds to a bound on the miscoverage rate (2) on average over all possible datasets. In other words, Eq. (1) is equivalent to a control on the expectation of the training-conditional miscoverage rate: $\mathbb{P}(Y \notin \hat{\mathcal{C}}(X)) = \mathbb{E}[\alpha(\mathcal{D})] \le \alpha$. However, the random variable $\alpha(\mathcal{D})$ can have high variance, and it is important to also control its deviation from the desired upper-bound $\alpha$ with high probability. For any $\alpha, \beta \in (0, 1)$, we are therefore also interested in constructing prediction sets with training-conditional coverage guarantees, that is, of the form

$$ \mathbb{P}(1 - \alpha(\mathcal{D}) \ge 1 - \alpha) \ge 1 - \beta. \qquad (3) $$

Prediction sets satisfying (3) are also known in the statistical literature as $(\alpha, \beta)$-tolerance regions or “Probably Approximately Correct” (PAC) predictive sets. This type of guarantee dates back to [63] and an overview can be found in [32]. More recent works on this subject include [8, 29, 47, 48, 61].

## 1.2. Related works

Our contribution takes place in the FL framework, a rather recent paradigm that allows training from decentralized data sets stored locally by multiple agents [27]. In this framework, the learning is made without exchanging raw data, making FL advantageous when data are highly sensitive and cannot be centralized for privacy or security reasons. So far, the design of FL algorithms has mainly focused on the learning step of statistical machine learning, the goal being to fit a (pointwise) predictor to decentralized data sets while minimizing the amount of communication [see e.g. 28, 37, 43]. However, quantifying the uncertainty in the prediction of these FL algorithms has not been widely studied yet.

Conformal prediction (CP) methods have become the state-of-the-art to construct marginally and conditionally valid distribution-free prediction sets [46, 54, 61, 62]. Unfortunately, one of the key steps of CP methods is the ordering of some computed scores, which is not possible in FL settings without sharing the full local data sets or performing many agent-server communication rounds. These methods are thus not well-suited to the constraints of FL in which agents process their data locally and only interact with a central server by sharing some aggregate statistics. Constructing a valid prediction set is even more difficult in the one-shot FL setting [14, 20, 36, 55, 65, 66] considered in this work, where only one round of communication between the agents and the server is allowed.

To our knowledge, [38] is the first paper considering the one-shot federated set-prediction problem with conformal prediction. Its idea is to locally calculate some quantiles of computed scores for each agent and to average them in the central server. Unfortunately, [38] does not prove that the corresponding prediction sets are valid and its method is non-robust, especially when the size of local data sets is small (see Appendix I.2 for more details). To address these issues, [25] has recently proposed a family of estimators called quantile-of-quantiles. The idea is that each agent sends to the server a local empirical quantile of its scores and the server aggregates them by computing a quantile of these
quantiles. Interestingly, these estimators can therefore be seen as a clever way of aggregat-
ing several quantiles calculated locally by *m* agents, who each locally use the (centralized)
split CP method (see Section 2.1 for details). Last but not least, when *m* = 1 this ap-
proach exactly recovers split CP, emphasizing that methods based on quantile-of-quantiles
estimators generalize centralized split CP to the FL setting. However, an important lim-
itation of [25] is that in order to determine which order of quantile to select for marginal
validity (1), the proposed methodology can be computationally intensive at the server
level. Moreover, the training-conditional guarantee (3) given by [25] is obtained with a
conservative procedure, leading to large prediction sets in practice. The present paper
shows how to solve these two issues.

Outside the one-shot FL setting considered here, we can also mention [39] and [50],
which focus on data-heterogeneous settings but require many communication rounds be-
tween the agents and the server. Finally, we can also mention recent works on federated
evaluation of classifiers [12], federated quantile computation [3, 49], and on uncertainty
quantification with Bayesian FL [15, 31] which, although related to our work, do not
study CP and do not obtain formal coverage guarantees.

1.3. Contributions

In this work, we consider the quantile-of-quantiles family of estimators proposed in [25]
and introduce several algorithms to find the appropriate order of quantiles so that the
marginal condition (1) or the training-conditional condition (3) are satisfied. Each of these
algorithms is computationally-efficient, distribution-free (depending only on the number
of agents and the size of their local data sets) and specially tailored to satisfy the afore-
mentioned conditions. Importantly, they come from novel theoretical results, which take
their roots in the theory of order statistics. For clarity and simplicity of reading, all the
contributions are first presented in the case where agents have the same number of data
points $n \ge 1$ (Assumption 1 in Section 2.2).

For distribution-free marginal guarantees (1), in Section 3.1:

* We prove that when $\hat{C}$ is obtained using our method, its probability of coverage $\mathrm{E}[1 - \alpha(D)] = \mathrm{P}(Y \in \hat{C}(X))$ is lower bounded by the expectation of a random variable following a particular Beta-Beta distribution [11, 40] (when the scores are almost surely distinct, these two quantities are equal). We also derive a closed-form expression for this expectation (Theorem 5), improving the one obtained in [25] and leading to Algorithm 1.

* This closed-form expression remains difficult to compute for large values of *n* and *m*, leading to a quite computationally demanding algorithm. To tackle this problem, we show that the expectation of this Beta-Beta distribution is lower and upper bounded by the quantile function of a standard Beta distribution evaluated at particular values (Proposition 8). These bounds are tight and fast to compute, which makes them interesting for practical use: they lead to Algorithm 2, which is more computationally efficient.

In Section 3.2, we build the first (to the best of our knowledge) one-shot FL algorithms
with distribution-free *training-conditional* guarantees (3). More precisely:

* We prove that $1 - \alpha(D)$ is stochastically larger (equal when the scores are a.s. distinct) than a Beta-Beta random variable (Theorem 10). We also show that the quantiles of the Beta-Beta are fast to compute, leading to an efficient algorithm that constructs training-conditionally valid prediction sets in one-shot FL (Algorithm 3).
quantiles. Interestingly, these estimators can therefore be seen as a clever way of aggregat-
ing several quantiles calculated locally by *m* agents, who each locally use the (centralized)
split CP method (see Section 2.1 for details). Last but not least, when *m* = 1 this ap-
proach exactly recovers split CP, emphasizing that methods based on quantile-of-quantiles
estimators generalize centralized split CP to the FL setting. However, an important lim-
itation of [25] is that in order to determine which order of quantile to select for marginal
validity (1), the proposed methodology can be computationally intensive at the server
level. Moreover, the training-conditional guarantee (3) given by [25] is obtained with a
conservative procedure, leading to large prediction sets in practice. The present paper
shows how to solve these two issues.

Outside the one-shot FL setting considered here, we can also mention [39] and [50],
which focus on data-heterogeneous settings but require many communication rounds be-
tween the agents and the server. Finally, we can also mention recent works on federated
evaluation of classifiers [12], federated quantile computation [3, 49], and on uncertainty
quantification with Bayesian FL [15, 31] which, although related to our work, do not
study CP and do not obtain formal coverage guarantees.

1.3. Contributions

In this work, we consider the quantile-of-quantiles family of estimators proposed in [25]
and introduce several algorithms to find the appropriate order of quantiles so that the
marginal condition (1) or the training-conditional condition (3) are satisfied. Each of these
algorithms is computationally-efficient, distribution-free (depending only on the number
of agents and the size of their local data sets) and specially tailored to satisfy the afore-
mentioned conditions. Importantly, they come from novel theoretical results, which take
their roots in the theory of order statistics. For clarity and simplicity of reading, all the
contributions are first presented in the case where agents have the same number of data
points $n \ge 1$ (Assumption 1 in Section 2.2).

For distribution-free marginal guarantees (1), in Section 3.1:

* We prove that when $\hat{C}$ is obtained using our method, its probability of coverage $\mathrm{E}[1 - \alpha(D)] = \mathrm{P}(Y \in \hat{C}(X))$ is lower bounded by the expectation of a random variable following a particular Beta-Beta distribution [11, 40] (when the scores are almost surely distinct, these two quantities are equal). We also derive a closed-form expression for this expectation (Theorem 5), improving the one obtained in [25] and leading to Algorithm 1.

* This closed-form expression remains difficult to compute for large values of *n* and *m*, leading to a quite computationally demanding algorithm. To tackle this problem, we show that the expectation of this Beta-Beta distribution is lower and upper bounded by the quantile function of a standard Beta distribution evaluated at particular values (Proposition 8). These bounds are tight and fast to compute, which makes them interesting for practical use: they lead to Algorithm 2, which is more computationally efficient.

In Section 3.2, we build the first (to the best of our knowledge) one-shot FL algorithms
with distribution-free *training-conditional* guarantees (3). More precisely:

* We prove that $1 - \alpha(D)$ is stochastically larger (equal when the scores are a.s. distinct) than a Beta-Beta random variable (Theorem 10). We also show that the quantiles of the Beta-Beta are fast to compute, leading to an efficient algorithm that constructs training-conditionally valid prediction sets in one-shot FL (Algorithm 3).
* In order to obtain an even faster algorithm, we provide a tight bound on the cumulative distribution function (cdf) of the Beta-Beta distribution (Proposition 13) which allows the automatic selection of the empirical-quantiles order that the agents should send to the server (Algorithm 4).

Importantly, our results allow to trade-off the tightness of the bounds for computational efficiency. More generally, our contributions go beyond the setting of FL, in the sense that they investigate the open question of how several split CP estimators obtained over independent data sets should be aggregated to obtain valid prediction sets.

In Section 4, we give several upper-bounds on the probability of coverage of our prediction sets. We first derive an upper-bound of order $1 - \alpha + O(m^{-1}n^{-1/2})$ for the marginal coverage of our methods from Section 3.1 (Algorithms 1–2). This result shows that our coverage is not too much above $1 - \alpha$ and strictly improves upon the work of [25], which did not provide such type of results. In the same vein, we also prove high-probability upper bounds on the training-conditional miscoverage rate obtained by the methods of Section 3.2 (Algorithms 3–4). Remarkably, these bounds are of order $1 - \alpha + O((mn)^{-1/2})$, the same order of magnitude as those of the centralized case. Hence, up to constant factors, the one-shot federated learning setting does not incur any loss.

In Section 5, we extend our theoretical results and associated methods to the more complicated setting where the agents can have different data set sizes (Theorems 19–20 and Algorithms 5–6), improving again upon the results presented in [25].

Finally, in Section 6, we empirically evaluate the performance of our algorithms on standard CP benchmarks, validating that they produce prediction sets that are computationally efficient and close to those obtained when data are centralized.

# 2. Preliminaries

## 2.1. Split Conformal Prediction

Conformal Prediction (CP) is a framework to construct prediction sets satisfying (1) without relying on any distributional assumption on the data [62]. In a centralized setting, one of the most popular methods to perform CP is the split conformal method (split CP) [46]. Since the quantile-of-quantiles procedure studied in this paper generalizes split CP, let us detail here how it is defined and recall some of the key results of previous literature. Simple and full proofs of these results are provided in Appendix I.1.

Assume that we have access to a centralized dataset $\mathcal{D}$, that we split into a learning set $\mathcal{D}^{lrn}$ and a calibration set $\mathcal{D}^{cal} = (X_i, Y_i)_{1\le i\le n_c}$, where $n_c \ge 1$ and the calibration data $(X_i, Y_i)$, $1 \le i \le n_c$, are i.i.d. and follow the same distribution as the independent test point $(X, Y)$.

First, a predictor $\hat{f}$ is built from $\mathcal{D}^{lrn}$ only, and it is used to define a nonconformity score function $s = s_{\hat{f}}: \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$, such that for every $(x, y) \in \mathcal{X} \times \mathcal{Y}$, $s_{\hat{f}}(x, y)$ measures how far the prediction $\hat{f}(x)$ is from the true output $y$. Whether we are in the regression or classification setting, many different score functions exist in the literature (see e.g. [4]). In regression, for instance, a common choice is the fitted absolute residual $s_{\hat{f}}: (x, y) \mapsto |y - \hat{f}(x)|$. In the sequel, we often write $s$ instead of $s_{\hat{f}}$ for simplicity. Furthermore, note that split CP does not assume a particular choice of score function, so throughout the paper, we keep the function $s$ abstract.

Second, we calculate the values of $s_{\hat{f}}$ taken on the calibration set $\mathcal{D}^{cal}$, called the nonconformity scores $S_i := s_{\hat{f}}(X_i, Y_i)$, $i = 1, \dots, n_c$.
* In order to obtain an even faster algorithm, we provide a tight bound on the cumulative distribution function (cdf) of the Beta-Beta distribution (Proposition 13) which allows the automatic selection of the empirical-quantiles order that the agents should send to the server (Algorithm 4).

Importantly, our results allow to trade-off the tightness of the bounds for computational efficiency. More generally, our contributions go beyond the setting of FL, in the sense that they investigate the open question of how several split CP estimators obtained over independent data sets should be aggregated to obtain valid prediction sets.

In Section 4, we give several upper-bounds on the probability of coverage of our prediction sets. We first derive an upper-bound of order $1 - \alpha + O(m^{-1}n^{-1/2})$ for the marginal coverage of our methods from Section 3.1 (Algorithms 1–2). This result shows that our coverage is not too much above $1 - \alpha$ and strictly improves upon the work of [25], which did not provide such type of results. In the same vein, we also prove high-probability upper bounds on the training-conditional miscoverage rate obtained by the methods of Section 3.2 (Algorithms 3–4). Remarkably, these bounds are of order $1 - \alpha + O((mn)^{-1/2})$, the same order of magnitude as those of the centralized case. Hence, up to constant factors, the one-shot federated learning setting does not incur any loss.

In Section 5, we extend our theoretical results and associated methods to the more complicated setting where the agents can have different data set sizes (Theorems 19–20 and Algorithms 5–6), improving again upon the results presented in [25].

Finally, in Section 6, we empirically evaluate the performance of our algorithms on standard CP benchmarks, validating that they produce prediction sets that are computationally efficient and close to those obtained when data are centralized.

# 2. Preliminaries

## 2.1. Split Conformal Prediction

Conformal Prediction (CP) is a framework to construct prediction sets satisfying (1) without relying on any distributional assumption on the data [62]. In a centralized setting, one of the most popular methods to perform CP is the split conformal method (split CP) [46]. Since the quantile-of-quantiles procedure studied in this paper generalizes split CP, let us detail here how it is defined and recall some of the key results of previous literature. Simple and full proofs of these results are provided in Appendix I.1.

Assume that we have access to a centralized dataset $\mathcal{D}$, that we split into a learning set $\mathcal{D}^{lrn}$ and a calibration set $\mathcal{D}^{cal} = (X_i, Y_i)_{1\le i\le n_c}$, where $n_c \ge 1$ and the calibration data $(X_i, Y_i)$, $1 \le i \le n_c$, are i.i.d. and follow the same distribution as the independent test point $(X, Y)$.

First, a predictor $\hat{f}$ is built from $\mathcal{D}^{lrn}$ only, and it is used to define a nonconformity score function $s = s_{\hat{f}}: \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$, such that for every $(x, y) \in \mathcal{X} \times \mathcal{Y}$, $s_{\hat{f}}(x, y)$ measures how far the prediction $\hat{f}(x)$ is from the true output $y$. Whether we are in the regression or classification setting, many different score functions exist in the literature (see e.g. [4]). In regression, for instance, a common choice is the fitted absolute residual $s_{\hat{f}}: (x, y) \mapsto |y - \hat{f}(x)|$. In the sequel, we often write $s$ instead of $s_{\hat{f}}$ for simplicity. Furthermore, note that split CP does not assume a particular choice of score function, so throughout the paper, we keep the function $s$ abstract.

Second, we calculate the values of $s_{\hat{f}}$ taken on the calibration set $\mathcal{D}^{cal}$, called the nonconformity scores $S_i := s_{\hat{f}}(X_i, Y_i)$, $i = 1, \dots, n_c$.
Third, we compute the r-th smallest nonconformity score $S_{(r)} := \hat{Q}_{(r)}(S_{n_c}^{cal})$ for some $r \in [n_c] := \{1, \dots, n_c\}$, where $S_{n_c}^{cal} := (S_1, \dots, S_{n_c})$ and $\hat{Q}_{(\cdot)}$ is the sample quantile function defined by

$$ \forall r, N \ge 1, \forall S' \in \mathbb{R}^N, \quad \hat{Q}_{(r)}(S') := \begin{cases} S'_{(r)} & \text{if } r \le N \\ +\infty & \text{otherwise,} \end{cases} \qquad (4) $$

with $S'_{(1)} \le \dots \le S'_{(N)}$ the ordered values of $S' = (S'_1, \dots, S'_N)$. Finally, the split CP prediction set is defined, for any $x \in \mathcal{X}$, by

$$ \hat{C}_r(x) := \{ y \in \mathcal{Y} : s_{\hat{f}}(x, y) \le S_{(r)} \}. \qquad (5) $$

Following Eq. (2) in Section 1, we define the training-conditional miscoverage rate of $\hat{C}_r$ by

$$ \alpha_r(\mathcal{D}) := \mathbb{P}(Y \notin \hat{C}_r(X) | \mathcal{D}), $$

where $(X, Y)$ is a test point, independent of $\mathcal{D}$ and with the same distribution as the $(X_i, Y_i)$. We then have

$$ 1 - \alpha_r(\mathcal{D}) = \mathbb{P}(s_{\hat{f}}(X, Y) \le S_{(r)}) = F_S(S_{(r)}) $$

where $F_S$ is the common cdf of the scores $S_i$. It is well known that for every $r \in [n_c]$,

$$ \mathbb{P}(Y \in \hat{C}_r(X)) = \mathbb{E}[1 - \alpha_r(\mathcal{D})] \ge \frac{r}{n_c + 1}, $$

with equality if the scores $S_i$ are almost surely distinct [35, 62]. As a consequence, for any $\alpha \in (0, 1)$, if $(1 - \alpha)(n_c + 1) \le n_c$, taking $r = [(1 - \alpha)(n_c + 1)]$ in Eq. (5) yields a prediction set satisfying Eq. (1), and if the $S_i$ are almost surely distinct, its expected miscoverage rate is

$$ \mathbb{E}[1 - \alpha_{[(1-\alpha)(n_c+1)]}(\mathcal{D})] = \frac{[(1-\alpha)(n_c+1)]}{n_c+1} \le 1 - \alpha + \frac{1}{n_c+1}. \qquad (6) $$

Regarding training-conditional guarantees, a straightforward consequence of [61, Proposition 2b] is that

$$ \forall r \ge 1, \forall \beta \in (0, 1), \quad \mathbb{P}(1 - \alpha_r(\mathcal{D}) \ge F_{U_{(r:n_c)}}^{-1}(\beta)) \ge 1 - \beta, \qquad (7) $$

where $F_{U_{(r:n_c)}}^{-1}$ denotes the quantile function of the Beta$(r, n_c - r + 1)$ distribution. In other words, $1 - \alpha_r(\mathcal{D})$ is stochastically larger than the Beta$(r, n_c - r + 1)$ distribution. Furthermore, Eq. (7) becomes an equality if the scores $S_i$ are almost surely distinct — that is, in such a case, $\alpha_r(\mathcal{D})$ exactly follows a Beta$(r, n_c - r + 1)$ distribution. Finally, taking $r \in [n_c]$ such that $F_{U_{(r:n_c)}}^{-1}(\beta) \ge 1 - \alpha$, Eq. (7) implies that the split CP prediction set $\hat{C}_r$ satisfies Eq. (3), that is, $\hat{C}_r$ is a $(\alpha, \beta)$-tolerance region —see also Eq. (99) in Appendix I.1.2.

**Remark 1.** When $n_c$ tends to infinity, the optimal asymptotically training-conditionally valid $r$—given by Eq. (102) in Appendix I.1.2—yields a prediction set $\hat{C}_r$ with coverage between $1 - \alpha$ and $1 - \alpha + O(1/\sqrt{n_c})$ with high probability —see Eq. (103) in Appendix I.1.2 for a precise statement.
Third, we compute the r-th smallest nonconformity score $S_{(r)} := \hat{Q}_{(r)}(S_{n_c}^{cal})$ for some $r \in [n_c] := \{1, \dots, n_c\}$, where $S_{n_c}^{cal} := (S_1, \dots, S_{n_c})$ and $\hat{Q}_{(\cdot)}$ is the sample quantile function defined by

$$ \forall r, N \ge 1, \forall S' \in \mathbb{R}^N, \quad \hat{Q}_{(r)}(S') := \begin{cases} S'_{(r)} & \text{if } r \le N \\ +\infty & \text{otherwise,} \end{cases} \quad (4) $$

with $S'_{(1)} \le \dots \le S'_{(N)}$ the ordered values of $S' = (S'_1, \dots, S'_N)$. Finally, the split CP prediction set is defined, for any $x \in \mathcal{X}$, by

$$ \hat{C}_r(x) := \{ y \in \mathcal{Y} : s_{\hat{f}}(x, y) \le S_{(r)} \}. \quad (5) $$

Following Eq. (2) in Section 1, we define the training-conditional miscoverage rate of $\hat{C}_r$ by

$$ \alpha_r(\mathcal{D}) := \mathbb{P}(Y \notin \hat{C}_r(X) | \mathcal{D}), $$

where $(X, Y)$ is a test point, independent of $\mathcal{D}$ and with the same distribution as the $(X_i, Y_i)$. We then have

$$ 1 - \alpha_r(\mathcal{D}) = \mathbb{P}(s_{\hat{f}}(X, Y) \le S_{(r)}) = F_S(S_{(r)}) $$

where $F_S$ is the common cdf of the scores $S_i$. It is well known that for every $r \in [n_c]$,

$$ \mathbb{P}(Y \in \hat{C}_r(X)) = \mathbb{E}[1 - \alpha_r(\mathcal{D})] \ge \frac{r}{n_c + 1}, $$

with equality if the scores $S_i$ are almost surely distinct [35, 62]. As a consequence, for any $\alpha \in (0, 1)$, if $(1 - \alpha)(n_c + 1) \le n_c$, taking $r = [(1 - \alpha)(n_c + 1)]$ in Eq. (5) yields a prediction set satisfying Eq. (1), and if the $S_i$ are almost surely distinct, its expected miscoverage rate is

$$ \mathbb{E}[1 - \alpha_{[(1-\alpha)(n_c+1)]}(\mathcal{D})] = \frac{[(1-\alpha)(n_c+1)]}{n_c+1} \le 1 - \alpha + \frac{1}{n_c+1}. \quad (6) $$

Regarding training-conditional guarantees, a straightforward consequence of [61, Proposition 2b] is that

$$ \forall r \ge 1, \forall \beta \in (0, 1), \quad \mathbb{P}(1 - \alpha_r(\mathcal{D}) \ge F_{U_{(r:n_c)}}^{-1}(\beta)) \ge 1 - \beta, \quad (7) $$

where $F_{U_{(r:n_c)}}^{-1}$ denotes the quantile function of the Beta$(r, n_c - r + 1)$ distribution. In other words, $1 - \alpha_r(\mathcal{D})$ is stochastically larger than the Beta$(r, n_c - r + 1)$ distribution. Furthermore, Eq. (7) becomes an equality if the scores $S_i$ are almost surely distinct — that is, in such a case, $\alpha_r(\mathcal{D})$ exactly follows a Beta$(r, n_c - r + 1)$ distribution. Finally, taking $r \in [n_c]$ such that $F_{U_{(r:n_c)}}^{-1}(\beta) \ge 1 - \alpha$, Eq. (7) implies that the split CP prediction set $\hat{C}_r$ satisfies Eq. (3), that is, $\hat{C}_r$ is a $(\alpha, \beta)$-tolerance region —see also Eq. (99) in Appendix I.1.2.

**Remark 1.** When $n_c$ tends to infinity, the optimal asymptotically training-conditionally valid $r$—given by Eq. (102) in Appendix I.1.2—yields a prediction set $\hat{C}_r$ with coverage between $1 - \alpha$ and $1 - \alpha + O(1/\sqrt{n_c})$ with high probability —see Eq. (103) in Appendix I.1.2 for a precise statement.
The problem of split CP in a federated setting is that computing the quantile $S_{(r)}$ requires in general several (and often many) communications between the central server and the agents, hence it cannot be used in one-shot FL. Therefore, we consider in this paper another family of procedures (quantile-of-quantiles estimators), that we define in the next section.

Note that, although the first CP methods were the *split* and the related *full methods* [46, 62], many extensions based upon them and with similar guarantees have been proposed in the literature. Their principal novelty lies in a clever choice of the non-conformity score function *s*. In regression, [35] presents a method called locally weighted CP and provides theoretical insights for conformal inference. More recently, [54] has developed a variant of the split CP called Conformal Quantile Regression (CQR). Other recent alternatives have been proposed [19, 21, 22, 29, 45, 56]. We refer to [62], [4], and [17] for in-depth presentations of CP and to [41] for a curated list of papers related to CP.

## 2.2. Federated conformal prediction with the quantile-of-quantiles

We now present the quantile-of-quantiles family of estimators, first introduced in [25], and how it can be used to obtain valid prediction sets in a one-shot FL setting, that is, in a setting where only one round of communication between the agents and the server is allowed [20, 66] and where only aggregated statistics computed locally by the agents can be sent to the server. From now on, we assume that the decentralized data set $\mathcal{D}$ is divided into a learning set $\mathcal{D}^{lrn}$ and a calibration set $\mathcal{D}^{cal} = (X_{i,j}, Y_{i,j})_{1\le j\le m, 1\le i\le n_j}$ where $n_j \ge 1$ for every $j \in [m]$. Among calibration data, agent $j \in [m]$ has only access to $(X_{i,j}, Y_{i,j})_{1\le i\le n_j}$. We assume that $\mathcal{D}^{lrn}$ is independent from $\mathcal{D}^{cal}$, and that the calibration data $(X_{i,j}, Y_{i,j})$, $j \in [m]$, $i \in [n_j]$ are i.i.d. with the same distribution as the test point $(X, Y)$ (which is independent from $\mathcal{D}$).

We assume that a (pointwise) predictor $\hat{f}$ is learned on $\mathcal{D}^{lrn}$ only, using for instance standard FL algorithms such as FedAvg [43]. Therefore, $\hat{f}$ is independent from $\mathcal{D}^{cal}$. As in the centralized setting, $\hat{f}$ is used to define a nonconformity score function $s = s_{\hat{f}}: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ such that for every $(x, y) \in \mathcal{X} \times \mathcal{Y}$, $s_{\hat{f}}(x, y)$ measures how far the prediction $\hat{f}(x)$ is from the true output $y$. In the sequel, we only focus on the calibration of the prediction set and not on the learning part.

**Remark 2.** Note that $\hat{f}$ does not have to be a point-wise predictor, that is, a function $\mathcal{X} \to \mathcal{Y}$. For instance, like in CQR [54], we can rely on the use of a score function $s$ depending on $\hat{f} = (\hat{f}_-, \hat{f}_+)$ a pair of quantile functions $\mathcal{X} \to \mathcal{Y}$.

**Remark 3.** In the following, all probabilistic statements are valid conditionally to $\mathcal{D}^{lrn}$. This amounts to acting as if $\hat{f}$ were deterministic, since $\mathcal{D}^{lrn}$ appears only through $\hat{f}$ and $\mathcal{D}^{cal}$ is independent from $\mathcal{D}^{lrn}$.

For simplicity, from now on and until the end of Section 4, we also make the following assumption.

**Assumption 1.** Each agent $j \in [m]$ has exactly $n_j = n \ge 1$ calibration data points.

Under Assumption 1, the calibration data set size is equal to $nm$. We refer to Section 5 for the more general case where agents have data sets of calibration of different sizes $(n_j)_{1\le j\le m}$.

For calibration, the first step is to ask each agent $j \in [m]$ to compute its $n$ i.i.d. local calibration scores $S_j := (S_{1,j}, \dots, S_{n,j})$, where $S_{i,j} = s_{\hat{f}}(X_{i,j}, Y_{i,j})$ is the score associated
The problem of split CP in a federated setting is that computing the quantile $S_{(r)}$ requires in general several (and often many) communications between the central server and the agents, hence it cannot be used in one-shot FL. Therefore, we consider in this paper another family of procedures (quantile-of-quantiles estimators), that we define in the next section.

Note that, although the first CP methods were the *split* and the related *full methods* [46, 62], many extensions based upon them and with similar guarantees have been proposed in the literature. Their principal novelty lies in a clever choice of the non-conformity score function *s*. In regression, [35] presents a method called locally weighted CP and provides theoretical insights for conformal inference. More recently, [54] has developed a variant of the split CP called Conformal Quantile Regression (CQR). Other recent alternatives have been proposed [19, 21, 22, 29, 45, 56]. We refer to [62], [4], and [17] for in-depth presentations of CP and to [41] for a curated list of papers related to CP.

## 2.2. Federated conformal prediction with the quantile-of-quantiles

We now present the quantile-of-quantiles family of estimators, first introduced in [25], and how it can be used to obtain valid prediction sets in a one-shot FL setting, that is, in a setting where only one round of communication between the agents and the server is allowed [20, 66] and where only aggregated statistics computed locally by the agents can be sent to the server. From now on, we assume that the decentralized data set $\mathcal{D}$ is divided into a learning set $\mathcal{D}^{lrn}$ and a calibration set $\mathcal{D}^{cal} = (X_{i,j}, Y_{i,j})_{1\le j\le m, 1\le i\le n_j}$ where $n_j \ge 1$ for every $j \in [m]$. Among calibration data, agent $j \in [m]$ has only access to $(X_{i,j}, Y_{i,j})_{1\le i\le n_j}$. We assume that $\mathcal{D}^{lrn}$ is independent from $\mathcal{D}^{cal}$, and that the calibration data $(X_{i,j}, Y_{i,j})$, $j \in [m]$, $i \in [n_j]$ are i.i.d. with the same distribution as the test point $(X, Y)$ (which is independent from $\mathcal{D}$).

We assume that a (pointwise) predictor $\hat{f}$ is learned on $\mathcal{D}^{lrn}$ only, using for instance standard FL algorithms such as FedAvg [43]. Therefore, $\hat{f}$ is independent from $\mathcal{D}^{cal}$. As in the centralized setting, $\hat{f}$ is used to define a nonconformity score function $s = s_{\hat{f}}: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ such that for every $(x, y) \in \mathcal{X} \times \mathcal{Y}$, $s_{\hat{f}}(x, y)$ measures how far the prediction $\hat{f}(x)$ is from the true output $y$. In the sequel, we only focus on the calibration of the prediction set and not on the learning part.

**Remark 2.** Note that $\hat{f}$ does not have to be a point-wise predictor, that is, a function $\mathcal{X} \to \mathcal{Y}$. For instance, like in CQR [54], we can rely on the use of a score function $s$ depending on $\hat{f} = (\hat{f}_-, \hat{f}_+)$ a pair of quantile functions $\mathcal{X} \to \mathcal{Y}$.

**Remark 3.** In the following, all probabilistic statements are valid conditionally to $\mathcal{D}^{lrn}$. This amounts to acting as if $\hat{f}$ were deterministic, since $\mathcal{D}^{lrn}$ appears only through $\hat{f}$ and $\mathcal{D}^{cal}$ is independent from $\mathcal{D}^{lrn}$.

For simplicity, from now on and until the end of Section 4, we also make the following assumption.

**Assumption 1.** Each agent $j \in [m]$ has exactly $n_j = n \ge 1$ calibration data points.

Under Assumption 1, the calibration data set size is equal to $nm$. We refer to Section 5 for the more general case where agents have data sets of calibration of different sizes $(n_j)_{1\le j\le m}$.

For calibration, the first step is to ask each agent $j \in [m]$ to compute its $n$ i.i.d. local calibration scores $S_j := (S_{1,j}, \dots, S_{n,j})$, where $S_{i,j} = s_{\hat{f}}(X_{i,j}, Y_{i,j})$ is the score associated
to the i-th calibration data point of agent j. Then, the server and the agents jointly compute the quantile-of-quantiles (QQ) estimator, defined as follows.

**Definition 4.** (Quantile-of-quantiles [25]) For any $(\ell, k) \in [n] \times [m]$, the QQ estimator of order $(\ell, k)$ calculated on the sets of scores $(S_j)_{1 \le j \le m}$ is

$$S_{(\ell,k)} := \hat{Q}_{(k)}(\hat{Q}_{(\ell)}(S_1), \dots, \hat{Q}_{(\ell)}(S_m)), \quad (8)$$

where $\hat{Q}_{(\cdot)}(\cdot)$ is the sample quantile function defined in Eq. (4).

In other words, each agent sends to the server its $\ell$-th smallest local score, denoted by $\hat{Q}_{(\ell)}(S_j)$, and the server then computes the $k$-th smallest value of these scores, denoted by $S_{(\ell,k)}$. This strategy requires a single round of communication and thus fits the constraints of one-shot FL. Finally, for any $x \in \mathcal{X}$, we define the prediction set

$$\hat{C}_{\ell,k}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell,k)}\}, \quad (9)$$

similarly to the centralized split CP method —see Eq. (5)—, but with $S_{(r)}$ replaced by $S_{(\ell,k)}$.

The decentralized QQ prediction set can be seen as a generalization of (centralized) split CP since they coincide when $m = 1$. The crucial remaining component is a computationally efficient approach to identify a pair $(\ell, k)$ so that $\hat{C}_{\ell,k}$ defined in Eq. (9) satisfies the marginal condition (1) or the training-conditional condition (3) while being as small as possible. We investigate these points in the next sections.

## 2.3. Prediction set performance measure

A natural way to evaluate the performance of a valid prediction set $x \mapsto \hat{C}(x)$ is to measure its size $\mu(\hat{C}(x))$, where $\mu$ is some measure on $\mathcal{Y}$, for instance, the counting measure when $\mathcal{Y}$ is finite, or the Lebesgue measure when $\mathcal{Y} \subset \mathbb{R}^p$ for some $p \ge 1$. This size should be minimized, either at a given $x \in \mathcal{X}$ or on average over $x = X$. For a prediction set of the form $\hat{C}_{\ell,k}$, as defined by Eq. (9), its size depends on $\mu$, on the score function $s$, on the predictor $\hat{f}$, and on the pair $(\ell, k)$. In order to build general-purpose algorithms for choosing $(\ell, k)$, a natural strategy is thus to select, among all the pairs such that $\hat{C}_{\ell,k}$ is marginally or conditionally valid, the one which also minimizes the size $\mu(\hat{C}_{\ell,k}(x))$. By Eq. (9), this size is a nondecreasing function of $S_{(\ell,k)}$. Furthermore, we know that

$$S_{(\ell,k)} \stackrel{\text{a.s.}}{=} F_S^{-1} \circ F_S(S_{(\ell,k)}) = F_S^{-1}(1 - \alpha_{\ell,k}(\mathcal{D})), \quad (10)$$

$$\text{where} \quad 1 - \alpha_{\ell,k}(\mathcal{D}) := \mathbb{P}(Y \in \hat{C}_{\ell,k}(X) | \mathcal{D}) = F_S(S_{(\ell,k)})$$

is the coverage of $\hat{C}_{\ell,k}$, $F_S$ is the cdf of the scores $S_{i,j}$, and $F_S^{-1}$ its generalized inverse —see Eq. (35) in Appendix B.1. Hence, the size of $\hat{C}_{\ell,k}(x)$ is also a nondecreasing function of the coverage.

Therefore, the quantiles or the expectation of the coverage are good ways to measure the performance of prediction sets of the form $\hat{C}_{\ell,k}$. In the following, we will use these quantities as criteria (to be minimized) for choosing among pairs $(\ell, k)$ such that $\hat{C}_{\ell,k}$ is (marginally or training-conditionally) valid. More detailed arguments about this strategy can be found in Appendix A.
to the i-th calibration data point of agent j. Then, the server and the agents jointly compute the quantile-of-quantiles (QQ) estimator, defined as follows.

**Definition 4.** (Quantile-of-quantiles [25]) For any $(\ell, k) \in [n] \times [m]$, the QQ estimator of order $(\ell, k)$ calculated on the sets of scores $(S_j)_{1 \le j \le m}$ is

$$S_{(\ell,k)} := \hat{Q}_{(k)}(\hat{Q}_{(\ell)}(S_1), \dots, \hat{Q}_{(\ell)}(S_m)), \quad (8)$$

where $\hat{Q}_{(\cdot)}(\cdot)$ is the sample quantile function defined in Eq. (4).

In other words, each agent sends to the server its $\ell$-th smallest local score, denoted by $\hat{Q}_{(\ell)}(S_j)$, and the server then computes the $k$-th smallest value of these scores, denoted by $S_{(\ell,k)}$. This strategy requires a single round of communication and thus fits the constraints of one-shot FL. Finally, for any $x \in \mathcal{X}$, we define the prediction set

$$\hat{C}_{\ell,k}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell,k)}\}, \quad (9)$$

similarly to the centralized split CP method —see Eq. (5)—, but with $S_{(r)}$ replaced by $S_{(\ell,k)}$.

The decentralized QQ prediction set can be seen as a generalization of (centralized) split CP since they coincide when $m = 1$. The crucial remaining component is a computationally efficient approach to identify a pair $(\ell, k)$ so that $\hat{C}_{\ell,k}$ defined in Eq. (9) satisfies the marginal condition (1) or the training-conditional condition (3) while being as small as possible. We investigate these points in the next sections.

## 2.3. Prediction set performance measure

A natural way to evaluate the performance of a valid prediction set $x \mapsto \hat{C}(x)$ is to measure its size $\mu(\hat{C}(x))$, where $\mu$ is some measure on $\mathcal{Y}$, for instance, the counting measure when $\mathcal{Y}$ is finite, or the Lebesgue measure when $\mathcal{Y} \subset \mathbb{R}^p$ for some $p \ge 1$. This size should be minimized, either at a given $x \in \mathcal{X}$ or on average over $x = X$. For a prediction set of the form $\hat{C}_{\ell,k}$, as defined by Eq. (9), its size depends on $\mu$, on the score function $s$, on the predictor $\hat{f}$, and on the pair $(\ell, k)$. In order to build general-purpose algorithms for choosing $(\ell, k)$, a natural strategy is thus to select, among all the pairs such that $\hat{C}_{\ell,k}$ is marginally or conditionally valid, the one which also minimizes the size $\mu(\hat{C}_{\ell,k}(x))$. By Eq. (9), this size is a nondecreasing function of $S_{(\ell,k)}$. Furthermore, we know that

$$S_{(\ell,k)} \stackrel{\text{a.s.}}{=} F_S^{-1} \circ F_S(S_{(\ell,k)}) = F_S^{-1}(1 - \alpha_{\ell,k}(\mathcal{D})), \quad (10)$$

$$\text{where} \quad 1 - \alpha_{\ell,k}(\mathcal{D}) := \mathbb{P}(Y \in \hat{C}_{\ell,k}(X) | \mathcal{D}) = F_S(S_{(\ell,k)})$$

is the coverage of $\hat{C}_{\ell,k}$, $F_S$ is the cdf of the scores $S_{i,j}$, and $F_S^{-1}$ its generalized inverse —see Eq. (35) in Appendix B.1. Hence, the size of $\hat{C}_{\ell,k}(x)$ is also a nondecreasing function of the coverage.

Therefore, the quantiles or the expectation of the coverage are good ways to measure the performance of prediction sets of the form $\hat{C}_{\ell,k}$. In the following, we will use these quantities as criteria (to be minimized) for choosing among pairs $(\ell, k)$ such that $\hat{C}_{\ell,k}$ is (marginally or training-conditionally) valid. More detailed arguments about this strategy can be found in Appendix A.
### 3. Choice of the quantiles for coverage guarantees

We now present theoretical results together with one-shot FL algorithms which return prediction sets with marginal (Section 3.1) or training-conditional (Section 3.2) guarantees.

#### 3.1. Marginal guarantees

In this section, we present two strategies for choosing a pair $(\ell, k)$ ensuring that $\hat{C}_{\ell,k}(x)$, defined by Eq. (9), is a marginally valid prediction set, that is, satisfies (1) for a given $\alpha \in (0, 1)$. Following Section 2.3, in order to get the best possible prediction set, our strategy is to take $(\ell, k)$ such that the marginal coverage

$$ \mathbb{P}(Y \in \hat{C}_{\ell,k}(X)) = \mathbb{P}(s_{\hat{f}}(X, Y) \le S_{(\ell,k)}) $$

is above $1 - \alpha$ while being as small as possible.

Our first algorithm is based on the following theorem, which simplifies the formula given in [25, Theorem 3.2].

**Theorem 5.** In the setting of Section 2.2, with Assumption 1, for any $(\ell, k) \in [n] \times [m]$, the set $\hat{C}_{\ell,k}$ defined by Eq. (9) satisfies

$$ \mathbb{P}(Y \in \hat{C}_{\ell,k}(X)) \ge M_{\ell,k} \qquad (11) $$

where

$$ M_{\ell,k} := \frac{k \binom{m}{k} \sum_{i_1=\ell}^{n} \cdots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{n} \cdots \sum_{i_m=0}^{n} \frac{\binom{n}{i_1} \cdots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \cdots \binom{n}{i_m}}{\binom{mn}{i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m}}}{(mn+1)\mathrm{B}(\ell, n-\ell+1)} $$

and

$$ B : (a, b) \in (0, +\infty)^2 \mapsto \int_0^1 t^{a-1}(1-t)^{b-1}dt $$

denotes the Beta function [59]. Moreover, when the associated scores $(S_{i,j})_{1 \le j \le m, 1 \le i \le n}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (11) is an equality.

Theorem 5 is proved in Appendix C.1. It shows that we can lower bound the probability of coverage of the quantile-of-quantiles prediction set by a distribution-free quantity $M_{\ell,k}$, which depends only on $m, n, \ell$ and $k$. Furthermore, the lower bound is sharp as it becomes an equality when the scores have a continuous cdf. This is for instance the case with the fitted absolute residual if the noise distribution given $X$ is almost surely atomless.

Theorem 5 suggests the following algorithm for the selection of $\ell$ and $k$, which we call QQM (QQ stands for Quantile-of-Quantiles and M for Marginal).<fnref n="1" />

**Algorithm 1 (QQM).** Given $\alpha \in (0, 1)$,

$$ \text{compute } (\ell^*, k^*) = \underset{(\ell,k) \in [n] \times [m]}{\operatorname{argmin}} \{M_{\ell,k} : M_{\ell,k} \ge 1 - \alpha\}, $$

$$ \text{and output } \hat{C}_{\ell^*, k^*}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell^*, k^*)}\}. $$

<footnote n="1">¹QQM is a slight modification of the algorithm FedCP-QQ proposed in [25]. More specifically, Eq. (11) is simpler and easier to compute than the corresponding formula for $M_{\ell,k}$ in [25].</footnote>
### 3. Choice of the quantiles for coverage guarantees

We now present theoretical results together with one-shot FL algorithms which return prediction sets with marginal (Section 3.1) or training-conditional (Section 3.2) guarantees.

#### 3.1. Marginal guarantees

In this section, we present two strategies for choosing a pair $(\ell, k)$ ensuring that $\hat{C}_{\ell,k}(x)$, defined by Eq. (9), is a marginally valid prediction set, that is, satisfies (1) for a given $\alpha \in (0, 1)$. Following Section 2.3, in order to get the best possible prediction set, our strategy is to take $(\ell, k)$ such that the marginal coverage

$$ \mathbb{P}(Y \in \hat{C}_{\ell,k}(X)) = \mathbb{P}(s_{\hat{f}}(X, Y) \le S_{(\ell,k)}) $$

is above $1 - \alpha$ while being as small as possible.

Our first algorithm is based on the following theorem, which simplifies the formula given in [25, Theorem 3.2].

**Theorem 5.** In the setting of Section 2.2, with Assumption 1, for any $(\ell, k) \in [n] \times [m]$, the set $\hat{C}_{\ell,k}$ defined by Eq. (9) satisfies

$$ \mathbb{P}(Y \in \hat{C}_{\ell,k}(X)) \ge M_{\ell,k} \quad (11) $$

where

$$ M_{\ell,k} := \frac{k \binom{m}{k} \sum_{i_1=\ell}^{n} \cdots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{n} \cdots \sum_{i_m=0}^{n} \frac{\binom{n}{i_1} \cdots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \cdots \binom{n}{i_m}}{\binom{mn}{i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m}}}{(mn+1)\mathrm{B}(\ell, n-\ell+1)} $$

and

$$ B : (a, b) \in (0, +\infty)^2 \mapsto \int_0^1 t^{a-1}(1-t)^{b-1}dt $$

denotes the Beta function [59]. Moreover, when the associated scores $(S_{i,j})_{1 \le j \le m, 1 \le i \le n}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (11) is an equality.

Theorem 5 is proved in Appendix C.1. It shows that we can lower bound the probability of coverage of the quantile-of-quantiles prediction set by a distribution-free quantity $M_{\ell,k}$, which depends only on $m, n, \ell$ and $k$. Furthermore, the lower bound is sharp as it becomes an equality when the scores have a continuous cdf. This is for instance the case with the fitted absolute residual if the noise distribution given $X$ is almost surely atomless.

Theorem 5 suggests the following algorithm for the selection of $\ell$ and $k$, which we call QQM (QQ stands for Quantile-of-Quantiles and M for Marginal).<fnref n="1" />

**Algorithm 1 (QQM).** Given $\alpha \in (0, 1)$,

$$ \text{compute } (\ell^*, k^*) = \underset{(\ell,k) \in [n] \times [m]}{\operatorname{argmin}} \{M_{\ell,k} : M_{\ell,k} \ge 1 - \alpha\}, $$

$$ \text{and output } \hat{C}_{\ell^*, k^*}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell^*, k^*)}\}. $$

<footnote n="1">¹QQM is a slight modification of the algorithm FedCP-QQ proposed in [25]. More specifically, Eq. (11) is simpler and easier to compute than the corresponding formula for $M_{\ell,k}$ in [25].</footnote>
**Remark 6.** By convention, when the argmin defining ($\ell^*, k^*$) in Algorithm 1 is empty, we define $\hat{C}_{\ell^*, k^*}(x) = \mathcal{Y}$. A similar convention is used in all of our algorithms.

The minimization step of Algorithm 1 comes from the fact that all pairs $(\ell, k)$ such that $M_{\ell,k} \ge 1 - \alpha$ ensure the marginal coverage, by Theorem 5, but we need to select one specific pair. For the prediction set to be as small as possible, following Section 2.3, we should minimize the coverage. In Algorithm 1, we minimize $M_{\ell,k}$ since it is equal to the expected coverage when the scores cdf is continuous.

By Theorem 5, the set $\hat{C}_{\ell^*, k^*}$ is marginally valid. It is also nontrivial when $mn$ is large enough, according to the following lemma.

**Lemma 7.** The argmin defining ($\ell^*, k^*$) in Algorithm 1 is non-empty —hence $\hat{C}_{\ell^*, k^*}$ is nontrivial— if and only if $mn \ge \alpha^{-1} - 1$.

This lemma is proved in Appendix C.2. Remarkably, the necessary and sufficient condition in Lemma 7 depends on the calibration samples sizes only through the total number $mn$ of calibration data points, hence it is the same for the centralized case (with one agent holding $mn$ calibration data points) and for the one-shot FL case (with $m \ge 2$ agents, each having access to $n$ calibration data points).

A critical limitation of QQM is that computing ($\ell^*, k^*$), and even a single $M_{\ell,k}$, is costly when $m \times n$ is large, preventing the approach to scale to a large number of data points or agents. For example, based on techniques from [34], [25] describes an algorithm that can be used to compute a single $M_{\ell,k}$ with a worst-case complexity of $\mathcal{O}(m^4 n \log(n))$. Although this complexity could be slightly improved using more advanced ideas from [34], the overall complexity of Algorithm 1 would still remain too high for very large data sets (e.g., when the number of agents $m$ is large). Our second strategy enables us to find a valid pair $(\ell, k)$ much faster. It is based on sharp upper and lower bounds over $M_{\ell,k}$ that can be computed efficiently.

**Proposition 8.** Let $n, m \ge 1$ be two integers, $(\ell, k) \in [[n]] \times [[m]]$, and $M_{\ell,k}$ be defined in Theorem 5. Then,

$$F_{U(\ell:n)}^{-1} \left( \frac{k-1/2}{m+1/2} \right) < M_{\ell,k} < F_{U(\ell:n)}^{-1} \left( \frac{k}{m+1/2} \right), \quad (12)$$

where $F_{U(\ell:n)}^{-1}$ is the quantile function of the $\text{Beta}(\ell, n - \ell + 1)$ distribution [59].

Proposition 8 is proved in Appendix C.3. By combining Proposition 8 and Theorem 5, if a pair $(\ell, k)$ is such that the left-hand side of Eq. (12) is greater or equal to $1 - \alpha$, then the associated prediction set $\hat{C}_{\ell,k}$ is marginally valid. As a consequence, for any $\ell \in [[n]]$ and $\alpha \in (0, 1)$, if we set

$$k = \tilde{k}_{m,n}(\ell, \alpha) := \lceil (m + 1/2) \cdot F_{U(\ell:n)}(1 - \alpha) + 1/2 \rceil, \quad (13)$$

then $1 - \alpha \le F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha) - 1/2}{m + 1/2} \right) \le M_{\ell, \tilde{k}_{m,n}(\ell, \alpha)} \le \mathbb{P}(Y \in \hat{C}_{\ell, \tilde{k}_{m,n}(\ell, \alpha)}(X)),$

provided that $\tilde{k}_{m,n}(\ell, \alpha) \in [[m]]$. Therefore, choosing the associated pair $(\ell, \tilde{k}_{m,n}(\ell, \alpha))$ leads to a marginally-valid prediction set. Following our idea to minimize $M_{\ell,k}$ among marginally-valid pairs $(\ell, k)$ in Algorithm 1, it is here natural to choose $\ell$ by minimizing the upper-bound $F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha)}{m + 1/2} \right)$ provided by Proposition 8, which leads to Algorithm 2 below.
**Remark 6.** By convention, when the argmin defining ($\ell^*, k^*$) in Algorithm 1 is empty, we define $\hat{C}_{\ell^*, k^*}(x) = \mathcal{Y}$. A similar convention is used in all of our algorithms.

The minimization step of Algorithm 1 comes from the fact that all pairs $(\ell, k)$ such that $M_{\ell,k} \ge 1 - \alpha$ ensure the marginal coverage, by Theorem 5, but we need to select one specific pair. For the prediction set to be as small as possible, following Section 2.3, we should minimize the coverage. In Algorithm 1, we minimize $M_{\ell,k}$ since it is equal to the expected coverage when the scores cdf is continuous.

By Theorem 5, the set $\hat{C}_{\ell^*, k^*}$ is marginally valid. It is also nontrivial when $mn$ is large enough, according to the following lemma.

**Lemma 7.** The argmin defining ($\ell^*, k^*$) in Algorithm 1 is non-empty —hence $\hat{C}_{\ell^*, k^*}$ is nontrivial— if and only if $mn \ge \alpha^{-1} - 1$.

This lemma is proved in Appendix C.2. Remarkably, the necessary and sufficient condition in Lemma 7 depends on the calibration samples sizes only through the total number $mn$ of calibration data points, hence it is the same for the centralized case (with one agent holding $mn$ calibration data points) and for the one-shot FL case (with $m \ge 2$ agents, each having access to $n$ calibration data points).

A critical limitation of QQM is that computing ($\ell^*, k^*$), and even a single $M_{\ell,k}$, is costly when $m \times n$ is large, preventing the approach to scale to a large number of data points or agents. For example, based on techniques from [34], [25] describes an algorithm that can be used to compute a single $M_{\ell,k}$ with a worst-case complexity of $\mathcal{O}(m^4 n \log(n))$. Although this complexity could be slightly improved using more advanced ideas from [34], the overall complexity of Algorithm 1 would still remain too high for very large data sets (e.g., when the number of agents $m$ is large). Our second strategy enables us to find a valid pair $(\ell, k)$ much faster. It is based on sharp upper and lower bounds over $M_{\ell,k}$ that can be computed efficiently.

**Proposition 8.** Let $n, m \ge 1$ be two integers, $(\ell, k) \in [[n]] \times [[m]]$, and $M_{\ell,k}$ be defined in Theorem 5. Then,

$$F_{U(\ell:n)}^{-1} \left( \frac{k - 1/2}{m + 1/2} \right) < M_{\ell,k} < F_{U(\ell:n)}^{-1} \left( \frac{k}{m + 1/2} \right), \quad (12)$$

where $F_{U(\ell:n)}^{-1}$ is the quantile function of the Beta($\ell, n - \ell + 1$) distribution [59].

Proposition 8 is proved in Appendix C.3. By combining Proposition 8 and Theorem 5, if a pair $(\ell, k)$ is such that the left-hand side of Eq. (12) is greater or equal to $1 - \alpha$, then the associated prediction set $\hat{C}_{\ell,k}$ is marginally valid. As a consequence, for any $\ell \in [[n]]$ and $\alpha \in (0, 1)$, if we set

$$k = \tilde{k}_{m,n}(\ell, \alpha) := \lceil (m + 1/2) \cdot F_{U(\ell:n)}(1 - \alpha) + 1/2 \rceil, \quad (13)$$

then $1 - \alpha \le F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha) - 1/2}{m + 1/2} \right) \le M_{\ell, \tilde{k}_{m,n}(\ell, \alpha)} \le \mathbb{P}(Y \in \hat{C}_{\ell, \tilde{k}_{m,n}(\ell, \alpha)}(X)),$

provided that $\tilde{k}_{m,n}(\ell, \alpha) \in [[m]]$. Therefore, choosing the associated pair $(\ell, \tilde{k}_{m,n}(\ell, \alpha))$ leads to a marginally-valid prediction set. Following our idea to minimize $M_{\ell,k}$ among marginally-valid pairs $(\ell, k)$ in Algorithm 1, it is here natural to choose $\ell$ by minimizing the upper-bound $F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha)}{m + 1/2} \right)$ provided by Proposition 8, which leads to Algorithm 2 below.
**Algorithm 2 (QQM-Fast).** Given $\alpha \in (0, 1)$,

$$ \text{compute} \quad \tilde{\ell} = \underset{\ell \in \llbracket n \rrbracket \text{ s.t. } \tilde{k}_{m,n}(\ell, \alpha) \in \llbracket m \rrbracket}{\operatorname{argmin}} \quad \left\{ F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha)}{m + 1/2} \right) \right\} \quad \text{and} \quad \tilde{k}_{m,n}(\tilde{\ell}, \alpha), $$
$$ \text{where } \tilde{k}_{m,n}(\ell, \alpha) \text{ is defined by Eq. (13),} $$

$$ \text{and output} \quad \hat{C}_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))}\}. $$

By construction, following the arguments detailed after Proposition 8, the set $\hat{C}_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)}$ is marginally valid. It is also nontrivial when $mn$ is large enough, according to the next lemma.

**Lemma 9.** The argmin defining $\tilde{\ell}$ in Algorithm 2 is non-empty —hence $\hat{C}_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)}$ is nontrivial— if and only if

$$ (1 - \alpha)^n \le \frac{m - 1/2}{m + 1/2}. \quad (14) $$

In particular, condition (14) holds true if $n(m - 1/2) \ge \alpha^{-1} - 1$.

Lemma 9 is proved in Appendix C.4. In addition, QQM-Fast is computationally efficient. Indeed, the functions $F_{U(\ell:n)}$ and $F_{U(\ell:n)}^{-1}$ are fast to evaluate even when $n$ is large (it takes a few milliseconds for $n = 10^6$). Furthermore, the minimization step in Algorithm 2 requires at most $n$ evaluations, and the complexity of Algorithm 2 is almost not impacted by the value of $m$. For example, on a standard personal machine (Intel i5 with 4 CPU at 2.50GHz), with $m = n = 10^6$, QQM-Fast takes a few seconds to return the valid pair $(\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))$ using the SciPy implementation [60] of the cdf $F_{U(\ell:n)}$ and the quantile function $F_{U(\ell:n)}^{-1}$ of the Beta distribution, whereas QQM can take several hours.

While the two methods presented above ensure that the marginal coverage at level $1 - \alpha$ is satisfied whatever the data distribution, one may wonder how much above $1 - \alpha$ it can be. This question is answered in detail in Section 4.1.

## 3.2. Training-conditional guarantees

In this section, we present two algorithms for choosing $(\ell, k)$ such that the quantile-of-quantiles prediction set $\hat{C}_{\ell,k}(x)$ defined by Eq. (9) is a distribution-free training-conditionally valid prediction set, that is, satisfies Eq. (3). In other words, the goal is to select $\ell$ and $k$ such that the miscoverage random variable

$$ \alpha_{\ell,k}(\mathcal{D}) = \mathbb{P}(Y \notin \hat{C}_{\ell,k}(X) | \mathcal{D}) \quad (15) $$

is smaller than $\alpha \in (0, 1)$ with probability at least $1 - \beta \in (0, 1)$, that is,

$$ \mathbb{P}(\mathbb{P}(Y \in \hat{C}_{\ell,k}(X) | \mathcal{D}) \ge 1 - \alpha) = \mathbb{P}(1 - \alpha_{\ell,k}(\mathcal{D}) \ge 1 - \alpha) \ge 1 - \beta. \quad (16) $$

Our first algorithm is based on the following theorem.

**Theorem 10.** In the setting of Section 2.2, with Assumption 1, for any $(\ell, k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket$ and any $\beta \in (0, 1)$, the miscoverage random variable $\alpha_{\ell,k}(\mathcal{D})$ defined by Eq. (15) satisfies

$$ \mathbb{P}(1 - \alpha_{\ell,k}(\mathcal{D}) \ge F_{U(\ell:n,k:m)}^{-1}(\beta)) \ge 1 - \beta, \quad (17) $$

where $F_{U(\ell:n,k:m)}^{-1} := F_{U(\ell:n)}^{-1} \circ F_{U(\ell:k)}^{-1}$ and for every $1 \le r \le N$, $F_{U(r:N)}^{-1}$ is the quantile function of the Beta(r, N - r + 1) distribution.
**Algorithm 2 (QQM-Fast).** Given $\alpha \in (0, 1)$,

$$ \text{compute} \quad \tilde{\ell} = \underset{\ell \in \llbracket n \rrbracket \text{ s.t. } \tilde{k}_{m,n}(\ell, \alpha) \in \llbracket m \rrbracket}{\operatorname{argmin}} \quad \left\{ F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha)}{m + 1/2} \right) \right\} \quad \text{and} \quad \tilde{k}_{m,n}(\tilde{\ell}, \alpha), $$
$$ \text{where } \tilde{k}_{m,n}(\ell, \alpha) \text{ is defined by Eq. (13),} $$

$$ \text{and output} \quad \hat{C}_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))}\}. $$

By construction, following the arguments detailed after Proposition 8, the set $\hat{C}_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)}$ is marginally valid. It is also nontrivial when $mn$ is large enough, according to the next lemma.

**Lemma 9.** The argmin defining $\tilde{\ell}$ in Algorithm 2 is non-empty —hence $\hat{C}_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)}$ is nontrivial— if and only if

$$ (1 - \alpha)^n \le \frac{m - 1/2}{m + 1/2}. \qquad (14) $$

In particular, condition (14) holds true if $n(m - 1/2) \ge \alpha^{-1} - 1$.

Lemma 9 is proved in Appendix C.4. In addition, QQM-Fast is computationally efficient. Indeed, the functions $F_{U(\ell:n)}$ and $F_{U(\ell:n)}^{-1}$ are fast to evaluate even when $n$ is large (it takes a few milliseconds for $n = 10^6$). Furthermore, the minimization step in Algorithm 2 requires at most $n$ evaluations, and the complexity of Algorithm 2 is almost not impacted by the value of $m$. For example, on a standard personal machine (Intel i5 with 4 CPU at 2.50GHz), with $m = n = 10^6$, QQM-Fast takes a few seconds to return the valid pair $(\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))$ using the SciPy implementation [60] of the cdf $F_{U(\ell:n)}$ and the quantile function $F_{U(\ell:n)}^{-1}$ of the Beta distribution, whereas QQM can take several hours.

While the two methods presented above ensure that the marginal coverage at level $1 - \alpha$ is satisfied whatever the data distribution, one may wonder how much above $1 - \alpha$ it can be. This question is answered in detail in Section 4.1.

## 3.2. Training-conditional guarantees

In this section, we present two algorithms for choosing $(\ell, k)$ such that the quantile-of-quantiles prediction set $\hat{C}_{\ell,k}(x)$ defined by Eq. (9) is a distribution-free training-conditionally valid prediction set, that is, satisfies Eq. (3). In other words, the goal is to select $\ell$ and $k$ such that the miscoverage random variable

$$ \alpha_{\ell,k}(\mathcal{D}) = \mathbb{P}(Y \notin \hat{C}_{\ell,k}(X) | \mathcal{D}) \qquad (15) $$

is smaller than $\alpha \in (0, 1)$ with probability at least $1 - \beta \in (0, 1)$, that is,

$$ \mathbb{P}(\mathbb{P}(Y \in \hat{C}_{\ell,k}(X) | \mathcal{D}) \ge 1 - \alpha) = \mathbb{P}(1 - \alpha_{\ell,k}(\mathcal{D}) \ge 1 - \alpha) \ge 1 - \beta. \qquad (16) $$

Our first algorithm is based on the following theorem.

**Theorem 10.** In the setting of Section 2.2, with Assumption 1, for any $(\ell, k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket$ and any $\beta \in (0, 1)$, the miscoverage random variable $\alpha_{\ell,k}(\mathcal{D})$ defined by Eq. (15) satisfies

$$ \mathbb{P}(1 - \alpha_{\ell,k}(\mathcal{D}) \ge F_{U(\ell:n,k:m)}^{-1}(\beta)) \ge 1 - \beta, \qquad (17) $$

where $F_{U(\ell:n,k:m)}^{-1} := F_{U(\ell:n)}^{-1} \circ F_{U(\ell:k)}^{-1}$ and for every $1 \le r \le N$, $F_{U(r:N)}^{-1}$ is the quantile function of the Beta(r, N - r + 1) distribution.
Moreover, when the associated scores $(S_{i,j})_{1 \le i \le n, 1 \le j \le m}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (17) is an equality and, for any $\beta' \in (0, 1)$ such that $\beta \le 1 - \beta'$,

$$ \mathbb{P}(F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \le 1 - \alpha_{\ell,k}(\mathcal{D}) \le F_{U_{(\ell:n,k:m)}}^{-1}(1 - \beta') = 1 - \beta - \beta'). \quad (18) $$

The interval $[F_{U_{(\ell:n,k:m)}}^{-1}(\beta), F_{U_{(\ell:n,k:m)}}^{-1}(1 - \beta')]$ is thus a two-sided fluctuation interval for the coverage random variable $1 - \alpha_{\ell,k}(\mathcal{D})$.

Theorem 10 is proved in Appendix D.1. Eq. (17) is sharp since it becomes an equality when the scores are a.s. distinct. It can be seen as a generalization of Eq. (7) to the case of the quantile-of-quantiles estimator. Theorem 10 is based on the fact that if $U_{(\ell:n,k:m)}$ is a random variable with cdf $F_{U_{(\ell:n,k:m)}}$, then $1 - \alpha_{\ell,k}(\mathcal{D})$ stochastically dominates $U_{(\ell:n,k:m)}$ in general, and they have the same distribution when the scores are a.s. distinct by Lemma 27 in Appendix B.2 (which also implies that Theorem 5 holds true with $M_{\ell,k} = \mathbb{E}[U_{(\ell:n,k:m)}]$).

**Remark 11.** The distribution associated to $F_{U_{(\ell:n,k:m)}}$ is a particular case of the Beta-Beta distribution [11, 40]. It can also be seen as the cdf of the k-th order statistics of a sample of m independent Beta($\ell, n - \ell + 1$) random variables [9, 26].

Theorem 10 suggests the following algorithm to select $\ell$ and $k$ for training-conditional validity, which we call QQC (QQ stands for Quantile-of-Quantiles and C for Conditional).

**Algorithm 3 (QQC).** Given $\alpha \in (0, 1)$ and $\beta \in (0, 1)$,

$$ \text{compute } (\ell_c^*, k_c^*) = \underset{(\ell,k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket}{\operatorname{argmin}} \left\{ F_{U_{(\ell:n,k:m)}}^{-1}(1-\beta) : F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge 1 - \alpha \right\} \quad (19) $$

$$ \text{and output } \hat{C}_{\ell_c^*, k_c^*}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell_c^*, k_c^*)}\}. $$

By construction and Theorem 10, the set $\hat{C}_{\ell_c^*, k_c^*}$ satisfies the training-conditional condition (16). It is also nontrivial when $mn$ is large enough, according to the following lemma.

**Lemma 12.** The argmin defining $(\ell_c^*, k_c^*)$ in Algorithm 3 is non-empty —hence $\hat{C}_{\ell_c^*, k_c^*}$ is nontrivial— if and only if

$$ mn \ge \frac{\log(\beta)}{\log(1-\alpha)}. \quad (20) $$

Lemma 12 is proved in Appendix D.2. Furthermore, as long as $m$ and $n$ are not too large, Algorithm 3 is computationally efficient since $F_{U_{(\ell:n)}}^{-1}$ and $F_{U_{(k:m)}}^{-1}$ can be computed quickly (see the comments below Algorithm 2 in Section 3.1).

Note that any pair $(\ell, k)$ satisfying the condition $F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge 1 - \alpha$ leads to a conditionally valid prediction set. As a selection criterion among these pairs $(\ell, k)$, following Section 2.3, we minimize $F_{U_{(\ell:n,k:m)}}^{-1}(1 - \beta)$ which, according to Eq. (18) in Theorem 10, is equal to the $(1 - \beta)$-quantile of the distribution of $1 - \alpha_{\ell,k}(\mathcal{D})$ when the scores are a.s. distinct.

QQC may require to evaluate $F_{U_{(\ell:n,k:m)}}^{-1}$ for many pairs $(\ell, k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket$, which can be too costly when $n$ and $m$ are large. In the sequel, we propose a simpler sufficient condition for Eq. (16) to be satisfied, leading to a faster algorithm. It is based on the following lower bound on the quantile function $F_{U_{(\ell:n,k:m)}}^{-1}$.

**Proposition 13.** Let $n, m \ge 1$ be two integers, $k \in \llbracket m \rrbracket$, $\ell \in \llbracket n \rrbracket$, and $F_{U_{(\ell:n,k:m)}}^{-1}$ be defined as in Theorem 10. For any $\beta \in (0, 1)$, we have

$$ F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge F_{U_{(\ell:n)}}^{-1} \left( \frac{k}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right). \quad (21) $$
Moreover, when the associated scores $(S_{i,j})_{1 \le i \le n, 1 \le j \le m}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (17) is an equality and, for any $\beta' \in (0, 1)$ such that $\beta \le 1 - \beta'$,

$$ \mathbb{P}(F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \le 1 - \alpha_{\ell,k}(\mathcal{D}) \le F_{U_{(\ell:n,k:m)}}^{-1}(1 - \beta') = 1 - \beta - \beta'). \quad (18) $$

The interval $[F_{U_{(\ell:n,k:m)}}^{-1}(\beta), F_{U_{(\ell:n,k:m)}}^{-1}(1 - \beta')]$ is thus a two-sided fluctuation interval for the coverage random variable $1 - \alpha_{\ell,k}(\mathcal{D})$.

Theorem 10 is proved in Appendix D.1. Eq. (17) is sharp since it becomes an equality when the scores are a.s. distinct. It can be seen as a generalization of Eq. (7) to the case of the quantile-of-quantiles estimator. Theorem 10 is based on the fact that if $U_{(\ell:n,k:m)}$ is a random variable with cdf $F_{U_{(\ell:n,k:m)}}$, then $1 - \alpha_{\ell,k}(\mathcal{D})$ stochastically dominates $U_{(\ell:n,k:m)}$ in general, and they have the same distribution when the scores are a.s. distinct by Lemma 27 in Appendix B.2 (which also implies that Theorem 5 holds true with $M_{\ell,k} = \mathbb{E}[U_{(\ell:n,k:m)}]$).

**Remark 11.** The distribution associated to $F_{U_{(\ell:n,k:m)}}$ is a particular case of the Beta-Beta distribution [11, 40]. It can also be seen as the cdf of the k-th order statistics of a sample of m independent Beta($\ell, n - \ell + 1$) random variables [9, 26].

Theorem 10 suggests the following algorithm to select $\ell$ and $k$ for training-conditional validity, which we call QQC (QQ stands for Quantile-of-Quantiles and C for Conditional).

**Algorithm 3 (QQC).** Given $\alpha \in (0, 1)$ and $\beta \in (0, 1)$,

$$ \text{compute } (\ell_c^*, k_c^*) = \underset{(\ell,k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket}{\operatorname{argmin}} \left\{ F_{U_{(\ell:n,k:m)}}^{-1}(1-\beta) : F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge 1 - \alpha \right\} \quad (19) $$

$$ \text{and output } \hat{C}_{\ell_c^*, k_c^*}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell_c^*, k_c^*)}\}. $$

By construction and Theorem 10, the set $\hat{C}_{\ell_c^*, k_c^*}$ satisfies the training-conditional condition (16). It is also nontrivial when $mn$ is large enough, according to the following lemma.

**Lemma 12.** The argmin defining $(\ell_c^*, k_c^*)$ in Algorithm 3 is non-empty —hence $\hat{C}_{\ell_c^*, k_c^*}$ is nontrivial— if and only if

$$ mn \ge \frac{\log(\beta)}{\log(1-\alpha)}. \quad (20) $$

Lemma 12 is proved in Appendix D.2. Furthermore, as long as $m$ and $n$ are not too large, Algorithm 3 is computationally efficient since $F_{U_{(\ell:n)}}^{-1}$ and $F_{U_{(k:m)}}^{-1}$ can be computed quickly (see the comments below Algorithm 2 in Section 3.1).

Note that any pair $(\ell, k)$ satisfying the condition $F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge 1 - \alpha$ leads to a conditionally valid prediction set. As a selection criterion among these pairs $(\ell, k)$, following Section 2.3, we minimize $F_{U_{(\ell:n,k:m)}}^{-1}(1 - \beta)$ which, according to Eq. (18) in Theorem 10, is equal to the $(1 - \beta)$-quantile of the distribution of $1 - \alpha_{\ell,k}(\mathcal{D})$ when the scores are a.s. distinct.

QQC may require to evaluate $F_{U_{(\ell:n,k:m)}}^{-1}$ for many pairs $(\ell, k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket$, which can be too costly when $n$ and $m$ are large. In the sequel, we propose a simpler sufficient condition for Eq. (16) to be satisfied, leading to a faster algorithm. It is based on the following lower bound on the quantile function $F_{U_{(\ell:n,k:m)}}^{-1}$.

**Proposition 13.** Let $n, m \ge 1$ be two integers, $k \in \llbracket m \rrbracket$, $\ell \in \llbracket n \rrbracket$, and $F_{U_{(\ell:n,k:m)}}^{-1}$ be defined as in Theorem 10. For any $\beta \in (0, 1)$, we have

$$ F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge F_{U_{(\ell:n)}}^{-1} \left( \frac{k}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right). \quad (21) $$
Proposition 13 is proved in Appendix D.3. From this result, we see that for any $\ell \in \llbracket n \rrbracket$, taking (if possible)

$$k = \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta) := \left[ (m+1) \left( F_{U(\ell:n)}(1-\alpha) + \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right) \right] \quad (22)$$

implies that $F_{U(\ell:n, \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta):m)}^{-1}(\beta) \ge 1 - \alpha$ and by Theorem 10, $\hat{C}_{\ell, \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)}$ satisfies the training-conditional condition (16). Choosing $\ell$ similarly to Algorithm 3 leads to the following algorithm.

**Algorithm 4 (QQC-Fast).** Given $\alpha \in (0, 1)$ and $\beta \in (0, 1)$,

$$\text{compute} \quad \tilde{\ell}^{\text{cond}} = \underset{\ell \in \llbracket n \rrbracket}{\operatorname{argmin}} \quad \left\{ F_{U(\ell:n, \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta):m)}^{-1}(1-\beta) \right\}$$

and $\tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)$, where $\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)$ is defined by Eq. (22).

$$\text{Output} \quad \hat{C}_{\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)}(x) = \{ y \in \mathcal{Y} : s(x, y) \le S_{(\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta))} \}.$$

By construction, following the arguments detailed after Proposition 13, the set $\hat{C}_{\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)}$ satisfies the training-conditional condition (16). It is also nontrivial when $mn$ is large enough, as shown by the following lemma.

**Lemma 14.** The argmin defining $\tilde{\ell}^{\text{cond}}$ in Algorithm 4 is non-empty —hence the set $\hat{C}_{\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)}$ is nontrivial— if and only if

$$\frac{m}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \ge (1-\alpha)^n. \quad (23)$$

For instance, it holds true when

$$n \ge \frac{\log(1/3)}{\log(1-\alpha)} \quad \text{and} \quad m \ge \max \left\{ 2, \frac{9}{2} \log(1/\beta) - 2 \right\}. \quad (24)$$

Lemma 14 is proved in Appendix D.4. In addition, Algorithm 4 is computationally efficient. Indeed, $F_{U(\ell:n, k:m)}^{-1} := F_{U(\ell:n)}^{-1} \circ F_{U(k:m)}^{-1}$ by Theorem 10, so Algorithm 4 requires at most $n$ evaluations of the functions $F_{U(\ell:n)}$, $F_{U(\ell:n)}^{-1}$ and $F_{U(k:m)}^{-1}$, which are fast to evaluate even when $n, m$ are large as explained below Algorithm 2.

**Remark 15.** Note that the computational complexities of all proposed algorithms have two parts: (i) the choice of a valid pair $(\ell, k)$, and (ii) the computation of $S_{(\ell,k)}$ given the data and $(\ell, k)$. The second part is not an issue since $\hat{f}$ is supposed to be given and the score functions usually can be computed fastly. So, all the complexities discussed throughout Section 3 are about the first part, which can be reused across multiple data sets, score functions, or predictors $\hat{f}$, as long as $m$ (the number of agents) and $n$ (the size of local data sets) remain fixed.

## 4. Upper bounds on the coverage

In the previous section, we focused on the problem of choosing $\ell$ and $k$ such that $1 - \alpha_{\ell,k}(\mathcal{D})$ is above $1 - \alpha$, either in expectation (Section 3.1), or with high probability (Section 3.2). In the present section, we raise the natural and important question of upper-bounding
Proposition 13 is proved in Appendix D.3. From this result, we see that for any $\ell \in \llbracket n \rrbracket$, taking (if possible)

$$k = \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta) := \left[ (m+1) \left( F_{U_{(\ell:n)}(1-\alpha)} + \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right) \right] \quad (22)$$

implies that $F_{U_{(\ell:n),\tilde{k}_{m,n}^{\text{cond}}(\ell,\alpha,\beta):m}}^{-1}(\beta) \ge 1 - \alpha$ and by Theorem 10, $\hat{C}_{\ell,\tilde{k}_{m,n}^{\text{cond}}(\ell,\alpha,\beta)}$ satisfies the training-conditional condition (16). Choosing $\ell$ similarly to Algorithm 3 leads to the following algorithm.

**Algorithm 4 (QQC-Fast).** Given $\alpha \in (0, 1)$ and $\beta \in (0, 1)$,

$$\text{compute} \quad \tilde{\ell}^{\text{cond}} = \underset{\ell \in \llbracket n \rrbracket}{\operatorname{argmin}} \quad \left\{ F_{U_{(\ell:n),\tilde{k}_{m,n}^{\text{cond}}(\ell,\alpha,\beta):m}}^{-1} (1-\beta) \right\}$$

and $\tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)$, where $\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)$ is defined by Eq. (22).

$$\text{Output} \quad \hat{C}_{\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)}(x) = \{ y \in \mathcal{Y} : s(x, y) \le S_{(\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta))} \}.$$

By construction, following the arguments detailed after Proposition 13, the set $\hat{C}_{\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)}$ satisfies the training-conditional condition (16). It is also nontrivial when $mn$ is large enough, as shown by the following lemma.

**Lemma 14.** The argmin defining $\tilde{\ell}^{\text{cond}}$ in Algorithm 4 is non-empty —hence the set $\hat{C}_{\tilde{\ell}^{\text{cond}}, \tilde{k}_{m,n}^{\text{cond}}(\tilde{\ell}^{\text{cond}}, \alpha, \beta)}$ is nontrivial— if and only if

$$\frac{m}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \ge (1-\alpha)^n. \quad (23)$$

For instance, it holds true when

$$n \ge \frac{\log(1/3)}{\log(1-\alpha)} \quad \text{and} \quad m \ge \max \left\{ 2, \frac{9}{2} \log(1/\beta) - 2 \right\}. \quad (24)$$

Lemma 14 is proved in Appendix D.4. In addition, Algorithm 4 is computationally efficient. Indeed, $F_{U_{(\ell:n,k:m)}}^{-1} := F_{U_{(\ell:n)}}^{-1} \circ F_{U_{(k:m)}}^{-1}$ by Theorem 10, so Algorithm 4 requires at most $n$ evaluations of the functions $F_{U_{(\ell:n)}}, F_{U_{(\ell:n)}}^{-1}$ and $F_{U_{(k:m)}}^{-1}$, which are fast to evaluate even when $n, m$ are large as explained below Algorithm 2.

**Remark 15.** Note that the computational complexities of all proposed algorithms have two parts: (i) the choice of a valid pair $(\ell, k)$, and (ii) the computation of $S_{(\ell,k)}$ given the data and $(\ell, k)$. The second part is not an issue since $\hat{f}$ is supposed to be given and the score functions usually can be computed fastly. So, all the complexities discussed throughout Section 3 are about the first part, which can be reused across multiple data sets, score functions, or predictors $\hat{f}$, as long as $m$ (the number of agents) and $n$ (the size of local data sets) remain fixed.

## 4. Upper bounds on the coverage

In the previous section, we focused on the problem of choosing $\ell$ and $k$ such that $1 - \alpha_{\ell,k}(\mathcal{D})$ is above $1 - \alpha$, either in expectation (Section 3.1), or with high probability (Section 3.2). In the present section, we raise the natural and important question of upper-bounding
$1 - \alpha_{\ell,k}(\mathcal{D})$ in expectation or with high-probability, as a function of $k, \ell, m$, and $n$. In particular, when the coverage is guaranteed to be larger than $1 - \alpha$, it is interesting to evaluate how far from $1 - \alpha$ it can be, in order to quantify the quality of the corresponding algorithms.

## 4.1. Marginal coverage upper bounds

In this section, we provide an upper bound on the expectation of the coverage $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})]$ obtained by Algorithms 1–2 of Section 3.1. Recall that, by Theorem 5, when the scores are a.s. distinct, $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})] = \mathbb{P}(Y \in \hat{\mathcal{C}}_{\ell,k}(X)) = M_{\ell,k}$. Hence, in that case it is sufficient to upper-bound $M_{\ell,k}$, as done by the following result.

**Theorem 16.** Given $\alpha \in (0, 1)$, let $(\ell^*, k^*)$ and $(\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))$ be the pairs respectively returned by Algorithms 1 and 2 of Section 3.1, where $\tilde{k}_{m,n}(\ell, \alpha)$ is defined by Eq. (13). Then, some $n_0(\alpha), m_0 \ge 1$ exist such that, if $n \ge n_0(\alpha)$ and $m \ge m_0$, we have

$$1 - \alpha \le M_{\ell^*,k^*} \le M_{\tilde{\ell},\tilde{k}_{m,n}(\tilde{\ell},\alpha)} \le 1 - \alpha + \frac{C}{(2m+1)\sqrt{n+2}}, \quad (25)$$

where $C$ denotes a numerical constant (for instance, the result holds true with $m_0 = 18$ and $C = 27$).

Theorem 16 is proved in Appendix E.1. Combined with Theorem 5, it shows that, if the scores are a.s. distinct, and when $m, n$ are sufficiently large, Algorithms 1 and 2 return prediction sets with marginal coverage between $1 - \alpha$ and $1 - \alpha + \mathcal{O}(n^{-1/2}m^{-1})$. In particular, their marginal coverages tend to $1 - \alpha$ when either $n$ or $m$ tends to infinity, a result that was not obtained previously for any one-shot FL marginally-valid prediction set [25].

Note that we do not exactly recover the upper bound $1 - \alpha + 1/(mn)$ obtained in the centralized case when there are $mn$ calibration points —Eq. (6) in Section 2.1. For Algorithm 1, following [25] we conjecture the stronger result $M_{\ell^*,k^*} \le 1 - \alpha + \mathcal{O}(1/mn)$. While our experiments in Section 6.1 corroborate this, proving it would require a different analysis that we leave for future work. For Algorithm 2, the results of Section 6.1.1 suggest that Eq. (25) is tight (up to the value of $C$).

## 4.2. Training-conditional coverage upper bounds

We now provide high-probability upper bounds on the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$ obtained by Algorithms 3–4 of Section 3.2.

**Theorem 17.** Let $\alpha \in (0, 1)$ and $\beta \in (0, 1)$ be given. Recall that the pairs $(\ell_c^*, k_c^*)$ and $(\tilde{\ell}_{cond}^*, \tilde{k}_{m,n}^{cond}(\tilde{\ell}_{cond}, \alpha, \beta))$ respectively denote the pairs $(\ell, k)$ chosen by Algorithms 3 and 4. In the setting of Section 2.2, with Assumption 1, assuming in addition that the scores $S_{i,j}, S$ are a.s. distinct, some $n'_0(\alpha), m'_0(\beta) \ge 1$ exist such that, for any $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta)$,

$$\mathbb{P} \left( 1 - \alpha_{\ell_c^*, k_c^*}(\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - \beta \quad (26)$$

$$\text{and} \quad \mathbb{P} \left( 1 - \alpha_{\tilde{\ell}_{cond}^*, \tilde{k}_{m,n}^{cond}(\tilde{\ell}_{cond}, \alpha, \beta)}(\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - \beta, \quad (27)$$

with $\Delta(\beta) = 12 \max\{2\sqrt{\log(1/\beta)}, 1\}$.
$1 - \alpha_{\ell,k}(\mathcal{D})$ in expectation or with high-probability, as a function of $k, \ell, m$, and $n$. In particular, when the coverage is guaranteed to be larger than $1 - \alpha$, it is interesting to evaluate how far from $1 - \alpha$ it can be, in order to quantify the quality of the corresponding algorithms.

## 4.1. Marginal coverage upper bounds

In this section, we provide an upper bound on the expectation of the coverage $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})]$ obtained by Algorithms 1–2 of Section 3.1. Recall that, by Theorem 5, when the scores are a.s. distinct, $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})] = \mathbb{P}(Y \in \hat{\mathcal{C}}_{\ell,k}(X)) = M_{\ell,k}$. Hence, in that case it is sufficient to upper-bound $M_{\ell,k}$, as done by the following result.

**Theorem 16.** Given $\alpha \in (0, 1)$, let $(\ell^*, k^*)$ and $(\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))$ be the pairs respectively returned by Algorithms 1 and 2 of Section 3.1, where $\tilde{k}_{m,n}(\ell, \alpha)$ is defined by Eq. (13). Then, some $n_0(\alpha), m_0 \ge 1$ exist such that, if $n \ge n_0(\alpha)$ and $m \ge m_0$, we have

$$1 - \alpha \le M_{\ell^*, k^*} \le M_{\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha)} \le 1 - \alpha + \frac{C}{(2m+1)\sqrt{n+2}}, \quad (25)$$

where $C$ denotes a numerical constant (for instance, the result holds true with $m_0 = 18$ and $C = 27$).

Theorem 16 is proved in Appendix E.1. Combined with Theorem 5, it shows that, if the scores are a.s. distinct, and when $m, n$ are sufficiently large, Algorithms 1 and 2 return prediction sets with marginal coverage between $1 - \alpha$ and $1 - \alpha + \mathcal{O}(n^{-1/2}m^{-1})$. In particular, their marginal coverages tend to $1 - \alpha$ when either $n$ or $m$ tends to infinity, a result that was not obtained previously for any one-shot FL marginally-valid prediction set [25].

Note that we do not exactly recover the upper bound $1 - \alpha + 1/(mn)$ obtained in the centralized case when there are $mn$ calibration points —Eq. (6) in Section 2.1. For Algorithm 1, following [25] we conjecture the stronger result $M_{\ell^*, k^*} \le 1 - \alpha + \mathcal{O}(1/mn)$. While our experiments in Section 6.1 corroborate this, proving it would require a different analysis that we leave for future work. For Algorithm 2, the results of Section 6.1.1 suggest that Eq. (25) is tight (up to the value of $C$).

## 4.2. Training-conditional coverage upper bounds

We now provide high-probability upper bounds on the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$ obtained by Algorithms 3–4 of Section 3.2.

**Theorem 17.** Let $\alpha \in (0, 1)$ and $\beta \in (0, 1)$ be given. Recall that the pairs $(\ell_c^*, k_c^*)$ and $(\tilde{\ell}_{cond}^*, \tilde{k}_{m,n}^{cond}(\tilde{\ell}_{cond}, \alpha, \beta))$ respectively denote the pairs $(\ell, k)$ chosen by Algorithms 3 and 4. In the setting of Section 2.2, with Assumption 1, assuming in addition that the scores $S_{i,j}, S$ are a.s. distinct, some $n'_0(\alpha), m'_0(\beta) \ge 1$ exist such that, for any $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta)$,

$$\mathbb{P} \left( 1 - \alpha_{\ell_c^*, k_c^*}(\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - \beta \quad (26)$$

$$\text{and} \quad \mathbb{P} \left( 1 - \alpha_{\tilde{\ell}_{cond}^*, \tilde{k}_{m,n}^{cond}(\tilde{\ell}_{cond}, \alpha, \beta)}(\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - \beta, \quad (27)$$

with $\Delta(\beta) = 12 \max\{2\sqrt{\log(1/\beta)}, 1\}$.
Theorem 17 is proved in Appendix E.2. Remarkably, the bounds are of the form $1-\alpha+\mathcal{O}(1/\sqrt{mn})$, exactly as for split CP in the centralized case (see Remark 1 in Section 2.1). Therefore, up to constants, using one-shot FL training-conditionally valid prediction sets —also known as $(\alpha, \beta)$-tolerance regions— such as Algorithms 3 and 4 incurs no loss compared to a centralized algorithm such as split CP [61].

A consequence of Theorem 17 is that, under the same assumptions, for any $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta)$,

$$ \mathbb{P} \left( 1 - \alpha \le 1 - \alpha_{\ell_c^*, k_c^*} (\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - 2\beta \quad (28) $$

(by Theorem 10 and the union bound), and a similar results holds true for the output of Algorithm 4. This shows that the deviations of the coverage are (at most) of order $(mn)^{-1/2}$, as for split CP in the centralized case [61, Proposition 2a]. The proof of this theorem, and by extension Eq. (28), rely on the fact that

$$ [F_{U_{(\ell:n,k:m)}^{-1}}(\beta), F_{U_{(\ell:n,k:m)}^{-1}}(1-\beta)] \subseteq \left[ 1-\alpha, 1-\alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right] $$

when the pair $(\ell, k)$ is chosen by our algorithms. Then, thanks to Eq. (18) in Theorem 10, we know that, with probability $1-2\beta$, the coverage random variable $1-\alpha_{\ell,k}(\mathcal{D})$ belongs to the first interval, which concludes the proof. This means that, when $(\ell, k)$ is the pair chosen by either Algorithm 3 or Algorithm 4, we have that $[F_{U_{(\ell:n,k:m)}^{-1}}(\beta), F_{U_{(\ell:n,k:m)}^{-1}}(1-\beta)]$ contains $1-\alpha_{\ell,k}(\mathcal{D})$ with probability $1-2\beta$, and that both $F_{U_{(\ell:n,k:m)}^{-1}}(\beta)$ and $F_{U_{(\ell:n,k:m)}^{-1}}(1-\beta)$ tend to $1-\alpha$ at a rate of at least $(mn)^{-1/2}$. According to the numerical experiments of Section 6.1, this rate $(mn)^{-1/2}$ seems exact (that is, not improvable in worst-case) when $(\ell, k)$ is chosen by Algorithm 4.

**Remark 18.** The proof of Theorem 17 also shows that

$$ \mathbb{P} \left( 1 - \alpha_{\ell_n, \tilde{k}_{m,n}^{\text{cond}}(\ell_n, \alpha, \beta)} (\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - \beta $$

for $\ell_n = \lceil n(1-\alpha) \rceil$. This inequality could be used to build prediction sets with a smaller computational complexity than Algorithm 4, at the price of being slightly more conservative. By Theorem 31 in Appendix G.2, the proof can also be generalized to any sequence $(\ell_n)_{n \ge 1}$ such that $\ell_n \in \llbracket n \rrbracket$ for every $n$ and $\ell_n = n(1-\alpha) + o(\sqrt{n})$ as $n \to +\infty$.

## 5. Generalization to different $n_j$

In the previous sections, for simplicity, we assume that all agents have the same number $n$ of (calibration) data points. Let us now consider the general case, that is, the setting described in Section 2.2 without Assumption 1. Since the $m$ agents have data sets of possibly different sizes $n_1, \dots, n_m$, one needs to adapt the order of the local quantile to each agent. Given $(\ell_1, \dots, \ell_m) \in \llbracket n_1 \rrbracket \times \dots \times \llbracket n_m \rrbracket$, the QQ estimator (Definition 4) is now defined by

$$ S_{(\ell_1, \dots, \ell_m, k)} := \hat{Q}_{(k:m)} \left( \hat{Q}_{(\ell_1:n_1)}(S_1), \dots, \hat{Q}_{(\ell_m:n_m)}(S_m) \right), \quad (29) $$

where $S_j = (S_{i,j})_{1 \le i \le n_j}$ denotes the set of local scores computed by the $j$-th agent. In words, each agent $j \in \llbracket m \rrbracket$ now sends to the server its $\ell_j$-th smallest score and the server
Theorem 17 is proved in Appendix E.2. Remarkably, the bounds are of the form $1 - \alpha + O(1/\sqrt{mn})$, exactly as for split CP in the centralized case (see Remark 1 in Section 2.1). Therefore, up to constants, using one-shot FL training-conditionally valid prediction sets —also known as $(\alpha, \beta)$-tolerance regions— such as Algorithms 3 and 4 incurs no loss compared to a centralized algorithm such as split CP [61].

A consequence of Theorem 17 is that, under the same assumptions, for any $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta)$,

$$ \mathbb{P} \left( 1 - \alpha \le 1 - \alpha_{\ell_c^*, k_c^*} (\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - 2\beta \quad (28) $$

(by Theorem 10 and the union bound), and a similar results holds true for the output of Algorithm 4. This shows that the deviations of the coverage are (at most) of order $(mn)^{-1/2}$, as for split CP in the centralized case [61, Proposition 2a]. The proof of this theorem, and by extension Eq. (28), rely on the fact that

$$ [F_{U(\ell:n,k:m)}^{-1}(\beta), F_{U(\ell:n,k:m)}^{-1}(1-\beta)] \subseteq \left[ 1-\alpha, 1-\alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right] $$

when the pair $(\ell, k)$ is chosen by our algorithms. Then, thanks to Eq. (18) in Theorem 10, we know that, with probability $1 - 2\beta$, the coverage random variable $1 - \alpha_{\ell,k}(\mathcal{D})$ belongs to the first interval, which concludes the proof. This means that, when $(\ell, k)$ is the pair chosen by either Algorithm 3 or Algorithm 4, we have that $[F_{U(\ell:n,k:m)}^{-1}(\beta), F_{U(\ell:n,k:m)}^{-1}(1-\beta)]$ contains $1 - \alpha_{\ell,k}(\mathcal{D})$ with probability $1 - 2\beta$, and that both $F_{U(\ell:n,k:m)}^{-1}(\beta)$ and $F_{U(\ell:n,k:m)}^{-1}(1-\beta)$ tend to $1 - \alpha$ at a rate of at least $(mn)^{-1/2}$. According to the numerical experiments of Section 6.1, this rate $(mn)^{-1/2}$ seems exact (that is, not improvable in worst-case) when $(\ell, k)$ is chosen by Algorithm 4.

**Remark 18.** The proof of Theorem 17 also shows that

$$ \mathbb{P} \left( 1 - \alpha_{\ell_n, \tilde{k}_{m,n}^{\text{cond}}(\ell_n, \alpha, \beta)} (\mathcal{D}) \le 1 - \alpha + \frac{\Delta(\beta)}{\sqrt{(m+2)(n+2)}} \right) \ge 1 - \beta $$

for $\ell_n = \lceil n(1 - \alpha) \rceil$. This inequality could be used to build prediction sets with a smaller computational complexity than Algorithm 4, at the price of being slightly more conservative. By Theorem 31 in Appendix G.2, the proof can also be generalized to any sequence $(\ell_n)_{n \ge 1}$ such that $\ell_n \in \llbracket n \rrbracket$ for every $n$ and $\ell_n = n(1 - \alpha) + o(\sqrt{n})$ as $n \to +\infty$.

## 5. Generalization to different $n_j$

In the previous sections, for simplicity, we assume that all agents have the same number $n$ of (calibration) data points. Let us now consider the general case, that is, the setting described in Section 2.2 without Assumption 1. Since the $m$ agents have data sets of possibly different sizes $n_1, \dots, n_m$, one needs to adapt the order of the local quantile to each agent. Given $(\ell_1, \dots, \ell_m) \in \llbracket n_1 \rrbracket \times \dots \times \llbracket n_m \rrbracket$, the QQ estimator (Definition 4) is now defined by

$$ S_{(\ell_1, \dots, \ell_m, k)} := \hat{Q}_{(k:m)} \left( \hat{Q}_{(\ell_1:n_1)}(S_1), \dots, \hat{Q}_{(\ell_m:n_m)}(S_m) \right), \quad (29) $$

where $S_j = (S_{i,j})_{1 \le i \le n_j}$ denotes the set of local scores computed by the $j$-th agent. In words, each agent $j \in \llbracket m \rrbracket$ now sends to the server its $\ell_j$-th smallest score and the server
computes the k-th smallest value of these values. The associated prediction set is, for any $x \in \mathcal{X}$,

$$ \hat{C}_{\ell_1, \dots, \ell_m, k}(x) := \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell_1, \dots, \ell_m, k)}\}, \quad (30) $$

and its miscoverage rate is denoted by

$$ \alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D}) := \mathbb{P}(Y \notin \hat{C}_{\ell_1, \dots, \ell_m, k}(X) | \mathcal{D}). \quad (31) $$

When the $n_j$ are different, the difficulty is that the random variables $(\hat{Q}_{(\ell_j:n_j)}(S_j))_{1 \le j \le m}$ in the right-hand side of Eq. (29) are not identically distributed as they are computed on data sets of different sizes. Hence, in this setting, the counterpart of Theorem 5 of Section 3.1 (marginal guarantee) is as follows.

**Theorem 19.** In the setting of Section 2.2, without Assumption 1, for any $(\ell_1, \dots, \ell_m, k) \in [[n_1]] \times \dots \times [[n_m]] \times [[m]]$, the set $\hat{C}_{\ell_1, \dots, \ell_m, k}$ defined by Eq. (30) satisfies

$$ \mathbb{P}(Y \in \hat{C}_{\ell_1, \dots, \ell_m, k}(X)) \ge M_{\ell_1, \dots, \ell_m, k} \quad (32) $$

with

$$ M_{\ell_1, \dots, \ell_m, k} = 1 - \frac{1}{1 + \sum_{j=1}^{m} n_j} \sum_{j=k}^{m} \sum_{a \in \mathcal{P}_j} \sum_{i_1 = \ell_{a_1}}^{n_{a_1}} \dots \sum_{i_j = \ell_{a_j}}^{n_{a_j}} \sum_{j_{j+1}=0}^{\ell_{a_{j+1}}-1} \dots \sum_{i_m=0}^{\ell_{a_m}-1} \frac{\binom{n_{a_1}}{i_1} \dots \binom{n_{a_m}}{i_m}}{\binom{n_1+\dots+n_m}{i_1+\dots+i_m}}, $$

where $\mathcal{P}_j$ denotes the set of permutations $a = (a_1, \dots, a_m)$ of $\{1, \dots, m\}$ such that $a_1 < a_2 < \dots < a_j$ and $a_{j+1} < a_{j+2} < \dots < a_m$. Moreover, when the associated scores $(S_{i,j})_{1 \le j \le m, 1 \le i \le n_j}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (32) is an equality.

Theorem 19 is proved in Appendix F.1. Furthermore, the miscoverage rate defined by Eq. (31) can be controlled with high probability thanks to the following result, which generalizes Theorem 10 in Section 3.2.

**Theorem 20.** In the setting of Section 2.2, without Assumption 1, for any $(\ell_1, \dots, \ell_m, k) \in [[n_1]] \times \dots \times [[n_m]] \times [[m]]$, and any $\alpha \in (0, 1)$, the miscoverage random variable $\alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D})$ defined by Eq. (31) satisfies

$$ \mathbb{P}(1 - \alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D}) \ge 1 - \alpha) \ge \text{PB}(k - 1; (F_{U(\ell_j:n_j)}(1 - \alpha))_{1 \le j \le m}), \quad (33) $$

where $F_{U(\ell_j:n_j)}$ denotes the cdf of the Beta$(\ell_j, n_j - \ell_j + 1)$ distribution and for every $t \in \mathbb{R}$ and $u \in [0, 1]^m$, $\text{PB}(\cdot; u)$ denotes the cdf of a Poisson-Binomial (PB) random variable with parameter $u^2$. Moreover, when the associated scores $(S_{i,j})_{1 \le j \le m, 1 \le i \le n_j}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (33) is an equality.

Theorem 20 is proved in Appendix F.2. Theorem 19 and Theorem 20 imply that (i) if $M_{\ell_1, \dots, \ell_m, k} \ge 1 - \alpha$, then $\hat{C}_{\ell_1, \dots, \ell_m, k}$ is a marginally valid prediction set, and (ii) given $\beta \in (0, 1)$ if $\text{PB}(k - 1; (F_{U(\ell_j:n_j)}(1 - \alpha))_{1 \le j \le m}) \ge 1 - \beta$, then $\hat{C}_{\ell_1, \dots, \ell_m, k}$ is an $(\alpha, \beta)$-tolerance region, that is, a training-conditionally valid prediction set. It remains to select $(\ell_1, \dots, \ell_m, k)$, among those satisfying the desired condition. Applying directly the strategy of Algorithms 1 or 3, although theoretically possible, can be computationally untractable since the $\ell_j$ can be different, hence a parameter set of cardinality $m \cdot n^m$.

<footnote n="2">²Recall that the PB distribution with parameter $u \in [0, 1]^m$ is the distribution of $Z_1 + \dots + Z_m$ where the random variables $Z_j$ are independent and respectively follow the Bernoulli($u_j$) distribution. It therefore generalizes the Binomial($m, p$) distribution, which corresponds to the case where $u_1 = \dots = u_m = p$. More details can be found in [58].</footnote>
computes the k-th smallest value of these values. The associated prediction set is, for any $x \in \mathcal{X}$,

$$ \hat{C}_{\ell_1, \dots, \ell_m, k}(x) := \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell_1, \dots, \ell_m, k)}\}, \quad (30) $$

and its miscoverage rate is denoted by

$$ \alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D}) := \mathbb{P}(Y \notin \hat{C}_{\ell_1, \dots, \ell_m, k}(X) | \mathcal{D}). \quad (31) $$

When the $n_j$ are different, the difficulty is that the random variables $(\hat{Q}_{(\ell_j:n_j)}(S_j))_{1 \le j \le m}$ in the right-hand side of Eq. (29) are not identically distributed as they are computed on data sets of different sizes. Hence, in this setting, the counterpart of Theorem 5 of Section 3.1 (marginal guarantee) is as follows.

**Theorem 19.** In the setting of Section 2.2, without Assumption 1, for any $(\ell_1, \dots, \ell_m, k) \in [[n_1]] \times \dots \times [[n_m]] \times [[m]]$, the set $\hat{C}_{\ell_1, \dots, \ell_m, k}$ defined by Eq. (30) satisfies

$$ \mathbb{P}(Y \in \hat{C}_{\ell_1, \dots, \ell_m, k}(X)) \ge M_{\ell_1, \dots, \ell_m, k} \quad (32) $$

with

$$ M_{\ell_1, \dots, \ell_m, k} = 1 - \frac{1}{1 + \sum_{j=1}^{m} n_j} \sum_{j=k}^{m} \sum_{a \in \mathcal{P}_j} \sum_{i_1=\ell_{a_1}}^{n_{a_1}} \dots \sum_{i_j=\ell_{a_j}}^{n_{a_j}} \sum_{j_{j+1}=0}^{\ell_{a_{j+1}}-1} \dots \sum_{i_m=0}^{\ell_{a_m}-1} \frac{\binom{n_{a_1}}{i_1} \dots \binom{n_{a_m}}{i_m}}{\binom{n_1+\dots+n_m}{i_1+\dots+i_m}}, $$

where $\mathcal{P}_j$ denotes the set of permutations $a = (a_1, \dots, a_m)$ of $\{1, \dots, m\}$ such that $a_1 < a_2 < \dots < a_j$ and $a_{j+1} < a_{j+2} < \dots < a_m$. Moreover, when the associated scores $(S_{i,j})_{1 \le j \le m, 1 \le i \le n_j}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (32) is an equality.

Theorem 19 is proved in Appendix F.1. Furthermore, the miscoverage rate defined by Eq. (31) can be controlled with high probability thanks to the following result, which generalizes Theorem 10 in Section 3.2.

**Theorem 20.** In the setting of Section 2.2, without Assumption 1, for any $(\ell_1, \dots, \ell_m, k) \in [[n_1]] \times \dots \times [[n_m]] \times [[m]]$, and any $\alpha \in (0, 1)$, the miscoverage random variable $\alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D})$ defined by Eq. (31) satisfies

$$ \mathbb{P}(1 - \alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D}) \ge 1 - \alpha) \ge \text{PB}(k - 1; (F_{U(\ell_j:n_j)}(1 - \alpha))_{1 \le j \le m}), \quad (33) $$

where $F_{U(\ell_j:n_j)}$ denotes the cdf of the Beta$(\ell_j, n_j - \ell_j + 1)$ distribution and for every $t \in \mathbb{R}$ and $u \in [0, 1]^m$, $\text{PB}(\cdot; u)$ denotes the cdf of a Poisson-Binomial (PB) random variable with parameter $u^2$. Moreover, when the associated scores $(S_{i,j})_{1 \le j \le m, 1 \le i \le n_j}$ and $S := s(X, Y)$ are almost surely distinct, Eq. (33) is an equality.

Theorem 20 is proved in Appendix F.2. Theorem 19 and Theorem 20 imply that (i) if $M_{\ell_1, \dots, \ell_m, k} \ge 1 - \alpha$, then $\hat{C}_{\ell_1, \dots, \ell_m, k}$ is a marginally valid prediction set, and (ii) given $\beta \in (0, 1)$ if $\text{PB}(k - 1; (F_{U(\ell_j:n_j)}(1 - \alpha))_{1 \le j \le m}) \ge 1 - \beta$, then $\hat{C}_{\ell_1, \dots, \ell_m, k}$ is an $(\alpha, \beta)$-tolerance region, that is, a training-conditionally valid prediction set. It remains to select $(\ell_1, \dots, \ell_m, k)$, among those satisfying the desired condition. Applying directly the strategy of Algorithms 1 or 3, although theoretically possible, can be computationally untractable since the $\ell_j$ can be different, hence a parameter set of cardinality $m \cdot n^m$.

<footnote n="2">²Recall that the PB distribution with parameter $u \in [0, 1]^m$ is the distribution of $Z_1 + \dots + Z_m$ where the random variables $Z_j$ are independent and respectively follow the Bernoulli($u_j$) distribution. It therefore generalizes the Binomial($m, p$) distribution, which corresponds to the case where $u_1 = \dots = u_m = p$. More details can be found in [58].</footnote>
Therefore, we propose to fix $\ell_j = \lceil(1 - \alpha)(n_j + 1)\rceil$ for all $j \in \llbracket m \rrbracket$, similarly to the classical (centralized) split CP methodology. Then, we only need to select $k \in \llbracket m \rrbracket$, thereby reducing significantly the computational complexity.<fnref n="3" /> Following the principles described in Section 2.3 for choosing $k$, Theorems 19–20 lead to the two following algorithms.

**Algorithm 5 (QQM-n<sub>j</sub> [25]).** Given $\alpha \in (0, 1)$,

$$
\begin{align*}
\text{compute} \quad & \ell_j^* = \lceil (1-\alpha)(n_j+1) \rceil \quad \text{for every } j \in \llbracket m \rrbracket \\
\text{and} \quad & k^*(\ell_{1\dots m}^*) = \arg \min_{k \in \llbracket m \rrbracket} \{ M_{\ell_1^*, \dots, \ell_m^*, k} : M_{\ell_1^*, \dots, \ell_m^*, k} \ge 1 - \alpha \}. \\
\text{Output} \quad & \hat{C}_{\ell_1^*, \dots, \ell_m^*, k^*(\ell_{1\dots m}^*)}(x) = \{ y \in \mathcal{Y} : s(x, y) \le S_{(\ell_1^*, \dots, \ell_m^*, k^*(\ell_{1\dots m}^*))} \} .
\end{align*}
$$

**Algorithm 6 (QQC-n<sub>j</sub> ).** Given $\alpha \in (0, 1)$ and $\beta \in (0, 1)$,

$$
\begin{align*}
\text{compute} \quad & \ell_j^* = \lceil (1-\alpha)(n_j+1) \rceil \quad \text{for every } j \in \llbracket m \rrbracket \\
\text{and} \quad & k_c^*(\ell_{1\dots m}^*) = \operatorname*{argmin}_{k \in \mathcal{K}} \left\{ \operatorname{PB}\left(k-1; (F_{U(\ell_j^*; n_j)}(1-\alpha))_{1\le j \le m}\right) \right\}, \\
\text{where} \quad & \mathcal{K} := \left\{ k \in \llbracket m \rrbracket : \operatorname{PB}\left(k-1; (F_{U(\ell_j^*; n_j)}(1-\alpha))_{1\le j \le m}\right) \ge 1-\beta \right\}. \\
\text{Output} \quad & \hat{C}_{\ell_1^*, \dots, \ell_m^*, k_c^*(\ell_{1\dots m}^*)}(x) = \{ y \in \mathcal{Y} : s(x, y) \le S_{(\ell_1^*, \dots, \ell_m^*, k_c^*(\ell_{1\dots m}^*))} \} .
\end{align*}
$$

For reasons detailed below Theorem 20, Algorithm 5 yields a distribution-free marginally valid prediction set, and Algorithm 6 yields a distribution-free training-conditionally valid prediction set. The exact computation of $M_{\ell_1, \dots, \ell_m, k}$ can be done in the same way as that of $M_{\ell, k}$ (see details in [25, Appendix A.2.]). Furthermore, because $M_{\ell_1, \dots, \ell_m, k} = \mathbb{E}[Z]$ where $Z$ has cdf $\text{PB}(k-1; (F_{U(\ell_j; n_j)}(1-\alpha))_{1 \le j \le m})$, another possibility is to numerically integrate this Poisson-Binomial cdf to approximate the expectation. There exist many algorithms to compute the Poisson-Binomial cdf of Eq. (33) efficiently, see for instance [23]. Moreover, precise approximations of it can be obtained when $m$ is large. We refer to the recent review of [58] on the Poisson-Binomial distribution for more details.

**Remark 21 (Other variants of Algorithms 5–6).** Following the comments below Theorem 20, Algorithm 5 (resp. Algorithm 6) remains marginally (resp. training-conditionally) valid with any other choice for the $\ell_j^*$, leading to many possible variants. Let us detail three of them. First, in Algorithm 6, one can replace $\ell_j^*$ by the value of $r_c$ defined by Eq. (34) when $|\mathcal{D}^{cal}| = n_j$, which corresponds to training-conditionally valid splitCP applied to the data of agent j alone. Second, when the argmin defining $k^*$ or $k_c^*$ is empty, it is possible to increase the $\ell_j^*$ (for instance, by adding 1 to each of them) until the argmin becomes nonempty (which happens for large enough $\ell_j^*$ if and only if Eq. (20) in Lemma 12) holds true. Third, when $m$ is small, one can consider small sets $\mathcal{L}_j^*$ of candidate values for $\ell_j^*$, and replace the argmin in Algorithms 5–6 by an argmin over $(k, \ell_1^*, \dots, \ell_m^*) \in \mathcal{K} \times \mathcal{L}_1^* \times \dots \times \mathcal{L}_m^*$, which yields a tractable algorithm provided this set remains small. While our Theorems 19–20 prove coverage lower bounds for each of these variants, we leave their detailed study for future work.

**Remark 22.** If we set $n_1 = \dots = n_m = n$ and $\ell_1 = \dots = \ell_m = \ell \in \llbracket n \rrbracket$ in Eq. (32), respectively in Eq. (33), we exactly recover the results obtained in Theorem 5 of Section 3.1 (marginal guarantee), resp. in Theorem 10 of Section 3.2 (conditional

<footnote n="3">³This strategy can also be used when $n_j = n$ (Section 3) at the cost of being less accurate than searching for all values of $\ell$ and $k$. See also Section 6.1.2 and Remark 18 in Appendix E.2.</footnote>
Therefore, we propose to fix $\ell_j = \lceil(1 - \alpha)(n_j + 1)\rceil$ for all $j \in \llbracket m \rrbracket$, similarly to the classical (centralized) split CP methodology. Then, we only need to select $k \in \llbracket m \rrbracket$, thereby reducing significantly the computational complexity.<fnref n="3" /> Following the principles described in Section 2.3 for choosing $k$, Theorems 19–20 lead to the two following algorithms.

**Algorithm 5 (QQM-n<sub>j</sub> [25]).** Given $\alpha \in (0, 1)$,

$$
\begin{align*}
\text{compute } \ell_j^* &= \lceil(1 - \alpha)(n_j + 1)\rceil \quad \text{for every } j \in \llbracket m \rrbracket \\
\text{and } k^*(\ell_{1...m}^*) &= \arg \min_{k \in \llbracket m \rrbracket} \left\{ M_{\ell_1^*, \dots, \ell_m^*, k} : M_{\ell_1^*, \dots, \ell_m^*, k} \ge 1 - \alpha \right\}. \\
\text{Output } \hat{C}_{\ell_1^*, \dots, \ell_m^*, k^*(\ell_{1...m}^*)}(x) &= \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell_1^*, \dots, \ell_m^*, k^*(\ell_{1...m}^*))}\}.
\end{align*}
$$

**Algorithm 6 (QQC-n<sub>j</sub> ).** Given $\alpha \in (0, 1)$ and $\beta \in (0, 1)$,

$$
\begin{align*}
\text{compute } \ell_j^* &= \lceil(1 - \alpha)(n_j + 1)\rceil \quad \text{for every } j \in \llbracket m \rrbracket \\
\text{and } k_c^*(\ell_{1...m}^*) &= \underset{k \in \mathcal{K}}{\operatorname{argmin}} \left\{ \operatorname{PB}\left(k - 1; (F_{U(\ell_j^* : n_j)}(1 - \alpha))_{1 \le j \le m}\right) \right\}, \\
\text{where } \mathcal{K} &:= \left\{ k \in \llbracket m \rrbracket : \operatorname{PB}\left(k - 1; (F_{U(\ell_j^* : n_j)}(1 - \alpha))_{1 \le j \le m}\right) \ge 1 - \beta \right\}. \\
\text{Output } \hat{C}_{\ell_1^*, \dots, \ell_m^*, k_c^*(\ell_{1...m}^*)}(x) = \{y \in \mathcal{Y} : s(x, y) \le S_{(\ell_1^*, \dots, \ell_m^*, k_c^*(\ell_{1...m}^*))}\}.
\end{align*}
$$

For reasons detailed below Theorem 20, Algorithm 5 yields a distribution-free marginally valid prediction set, and Algorithm 6 yields a distribution-free training-conditionally valid prediction set. The exact computation of $M_{\ell_1, \dots, \ell_m, k}$ can be done in the same way as that of $M_{\ell, k}$ (see details in [25, Appendix A.2.]). Furthermore, because $M_{\ell_1, \dots, \ell_m, k} = \mathbb{E}[Z]$ where $Z$ has cdf $\text{PB}(k-1; (F_{U(\ell_j^* : n_j)}(1-\alpha))_{1 \le j \le m})$, another possibility is to numerically integrate this Poisson-Binomial cdf to approximate the expectation. There exist many algorithms to compute the Poisson-Binomial cdf of Eq. (33) efficiently, see for instance [23]. Moreover, precise approximations of it can be obtained when $m$ is large. We refer to the recent review of [58] on the Poisson-Binomial distribution for more details.

**Remark 21 (Other variants of Algorithms 5–6).** Following the comments below Theorem 20, Algorithm 5 (resp. Algorithm 6) remains marginally (resp. training-conditionally) valid with any other choice for the $\ell_j^*$, leading to many possible variants. Let us detail three of them. First, in Algorithm 6, one can replace $\ell_j^*$ by the value of $r_c$ defined by Eq. (34) when $|\mathcal{D}^{cal}| = n_j$, which corresponds to training-conditionally valid splitCP applied to the data of agent j alone. Second, when the argmin defining $k^*$ or $k_c^*$ is empty, it is possible to increase the $\ell_j^*$ (for instance, by adding 1 to each of them) until the argmin becomes nonempty (which happens for large enough $\ell_j^*$ if and only if Eq. (20) in Lemma 12) holds true. Third, when $m$ is small, one can consider small sets $\mathcal{L}_j^*$ of candidate values for $\ell_j^*$, and replace the argmin in Algorithms 5–6 by an argmin over $(k, \ell_1^*, \dots, \ell_m^*) \in \mathcal{K} \times \mathcal{L}_1^* \times \dots \times \mathcal{L}_m^*$, which yields a tractable algorithm provided this set remains small. While our Theorems 19–20 prove coverage lower bounds for each of these variants, we leave their detailed study for future work.

**Remark 22.** If we set $n_1 = \dots = n_m = n$ and $\ell_1 = \dots = \ell_m = \ell \in \llbracket n \rrbracket$ in Eq. (32), respectively in Eq. (33), we exactly recover the results obtained in Theorem 5 of Section 3.1 (marginal guarantee), resp. in Theorem 10 of Section 3.2 (conditional

<footnote n="3">³This strategy can also be used when $n_j = n$ (Section 3) at the cost of being less accurate than searching for all values of $\ell$ and $k$. See also Section 6.1.2 and Remark 18 in Appendix E.2.</footnote>
guarantee). Indeed, the summation over permutations $a \in P_j$ in Theorem 19 then becomes the $\binom{m}{k}$ of Theorem 5, after rearranging the terms. For Theorem 20, the parameters of the Poisson-Binomial ($F_{U(\ell_j:n_j)}(1-\alpha)_{1\le j \le m}$ are then equal, hence we get the Binomial($m; F_{U(\ell:n)}(1-\alpha)$) distribution. This leads to Theorem 10 with $\beta = F_{U(\ell:n,k:m)}(1-\alpha)) = F_{U(\ell_{k:m})} \circ F_{U(\ell:n)}(1-\alpha))$ since $F_{\text{Binomial}(m,p)}(k-1) = 1 - F_{U(\ell_{k:m})}(p)$, here used with $p = F_{U(\ell:n)}(1-\alpha)$.

# 6. Numerical experiments

In this section, we first study the behavior of our algorithms in a generic setting and then evaluate them on real datasets. The code of our experiments is publicly available.<fnref n="4" /> In the experiments, we compare the performance of the following conformal-based prediction-set algorithms:

* Algorithms 1–4, respectively called QQM, QQM-Fast, QQC and QQC-Fast (when the $n_j$ are equal);

* Algorithms 5–6, respectively called QQM-$n_j$ and QQC-$n_j$ (when the $n_j$ may be different);

* CentralM: split conformal prediction $\hat{C}_r$ (as defined in Section 2.1) on the full (centralized) calibration data set $\mathcal{D}^{cal}$, with $r = \lceil(1-\alpha)(|\mathcal{D}^{cal}| + 1)\rceil$ so that it is marginally valid; in other words, CentralM is the centralized version of QQM and they coincide when $m=1$;

* CentralC: split conformal prediction $\hat{C}_r$ on the full (centralized) calibration data set $\mathcal{D}^{cal}$ with

$$r = r_c := \min\{\tilde{r} \in \llbracket |\mathcal{D}^{cal}| \rrbracket : F_{U(\tilde{r}:|\mathcal{D}^{cal}|)}^{-1}(\beta) \ge 1 - \alpha\}, \quad (34)$$

so that it is conditionally valid, by Eq. (7) in Section 2.1; in other words, CentralC is the centralized version of QQC and they coincide when $m=1$;

* FedCP-Avg: federated approach proposed by [38], which averages the $m$ quantiles of order $\lceil(n_j+1)(1-\alpha)\rceil$ sent by the agents, hence the prediction set

$$\hat{C}_{\text{FedCP-Avg}}(x) := \left\{ y \in \mathcal{Y} : s(x, y) \le \frac{1}{m} \sum_{j=1}^{m} \hat{Q}_{\lceil(n_j+1)(1-\alpha)\rceil}(S_j) \right\}.$$

All our experiments are done with $\alpha = 0.1$ and $\beta = 0.2$.

As explained in Section 2.3, we compare the performance of these methods either through the length of the prediction sets they produce (in Section 6.2, where these are intervals) or their coverage, which should both be as small as possible while keeping the associated set valid. Note that it is fair to compare split CP (CentralM and CentralC), FedCP-Avg and our quantile-of-quantiles prediction sets (Algorithms 1–6) through their coverages since they all are of the form $\{y \in \mathcal{Y} : s(x, y) \le \bar{S}\}$ for some random variable $\bar{S}$.

## 6.1. Generic comparison.

In this section, we compare numerically the performance (measured by their coverages) of our algorithms and their centralized counterparts (CentralM and CentralC). This comparison is made under the mild assumption that $F_S$ is continuous, which implies that the cdf of the training-conditional coverage distribution of each algorithm is known and,

<footnote n="4">⁴https://github.com/pierreHmbt/One-shot-FCP</footnote>
guarantee). Indeed, the summation over permutations $a \in P_j$ in Theorem 19 then becomes the $\binom{m}{k}$ of Theorem 5, after rearranging the terms. For Theorem 20, the parameters of the Poisson-Binomial ($F_{U(\ell_j:n_j)}(1-\alpha)_{1\le j\le m}$ are then equal, hence we get the Binomial($m; F_{U(\ell:n)}(1-\alpha)$) distribution. This leads to Theorem 10 with $\beta = F_{U(\ell:n,k:m)}(1-\alpha)) = F_{U_{(k:m)}}(1-\alpha)$ since $F_{\text{Binomial}(m,p)}(k-1) = 1 - F_{U_{(k:m)}}(p)$, here used with $p = F_{U(\ell:n)}(1-\alpha)$.

# 6. Numerical experiments

In this section, we first study the behavior of our algorithms in a generic setting and then evaluate them on real datasets. The code of our experiments is publicly available.<fnref n="4" /> In the experiments, we compare the performance of the following conformal-based prediction-set algorithms:

* Algorithms 1–4, respectively called QQM, QQM-Fast, QQC and QQC-Fast (when the $n_j$ are equal);

* Algorithms 5–6, respectively called QQM-$n_j$ and QQC-$n_j$ (when the $n_j$ may be different);

* CentralM: split conformal prediction $\hat{C}_r$ (as defined in Section 2.1) on the full (centralized) calibration data set $\mathcal{D}^{cal}$, with $r = \lceil(1-\alpha)(|\mathcal{D}^{cal}| + 1)\rceil$ so that it is marginally valid; in other words, CentralM is the centralized version of QQM and they coincide when $m=1$;

* CentralC: split conformal prediction $\hat{C}_r$ on the full (centralized) calibration data set $\mathcal{D}^{cal}$ with

$$r = r_c := \min\{\tilde{r} \in \llbracket |\mathcal{D}^{cal}| \rrbracket : F_{U(\tilde{r}:|\mathcal{D}^{cal}|)}^{-1}(\beta) \ge 1 - \alpha\}, \quad (34)$$

so that it is conditionally valid, by Eq. (7) in Section 2.1; in other words, CentralC is the centralized version of QQC and they coincide when $m=1$;

* FedCP-Avg: federated approach proposed by [38], which averages the $m$ quantiles of order $\lceil(n_j+1)(1-\alpha)\rceil$ sent by the agents, hence the prediction set

$$\hat{C}_{\text{FedCP-Avg}}(x) := \left\{ y \in \mathcal{Y} : s(x, y) \le \frac{1}{m} \sum_{j=1}^{m} \hat{Q}_{\lceil(n_j+1)(1-\alpha)\rceil}(S_j) \right\}.$$

All our experiments are done with $\alpha = 0.1$ and $\beta = 0.2$.

As explained in Section 2.3, we compare the performance of these methods either through the length of the prediction sets they produce (in Section 6.2, where these are intervals) or their coverage, which should both be as small as possible while keeping the associated set valid. Note that it is fair to compare split CP (CentralM and CentralC), FedCP-Avg and our quantile-of-quantiles prediction sets (Algorithms 1–6) through their coverages since they all are of the form $\{y \in \mathcal{Y} : s(x, y) \le \bar{S}\}$ for some random variable $\bar{S}$.

## 6.1. Generic comparison.

In this section, we compare numerically the performance (measured by their coverages) of our algorithms and their centralized counterparts (CentralM and CentralC). This comparison is made under the mild assumption that $F_S$ is continuous, which implies that the cdf of the training-conditional coverage distribution of each algorithm is known and,

<footnote n="4">⁴https://github.com/pierreHmbt/One-shot-FCP</footnote>
more importantly, universal – see Eq. (7) and the discussion below for centralized algo-
rithms, Theorem 10 for federated algorithms with equal $n_j$ and Theorem 20 for federated
algorithms with general $n_j$. We also have closed-form formulas for the expected coverage
when $F_S$ is continuous, by Eq. (6) for centralized algorithms, and by Theorems 5 and 19
for our federated algorithms. Under this *generic setting*, we thus consider simultaneously
all learning problems, data distributions, predictors $\hat{f}$ and score functions $s$ such that the
scores cdf $F_S$ is continuous.

Throughout this subsection, for each algorithm considered, denoting by $1 - \alpha(\mathcal{D})$ its (random) coverage, we are interested in $F_{1-\alpha(\mathcal{D})}$ the coverage cdf, $\Delta\mathbb{E} := \mathbb{E}[1 - \alpha(\mathcal{D})] - (1 - \alpha)$ the difference between the expected coverage and the nominal coverage $(1 - \alpha)$, and, for several values of $\zeta \in (0, 1)$, $\Delta q_{\zeta} := F_{1-\alpha(\mathcal{D})}^{-1}(\zeta) - (1 - \alpha)$ the difference between the $\zeta$-quantile of the coverage and the nominal coverage.

6.1.1. Equal $n_j$

We first compare QQM, QQM-Fast, QQC, QQC-Fast, CentralM and CentralC under Assumption 1, that is, when each agent $j \in [m]$ has the same number $n_j = n$ of calibration data points. In Section 4, we prove that $\Delta\mathbb{E} = \mathcal{O}(m^{-1}n^{-1/2})$ for our marginally valid federated prediction sets (Theorem 16) and that $\Delta q_{1-\beta} = \mathcal{O}(m^{-1/2}n^{-1/2})$ for our training-conditionally valid federated prediction sets (Theorem 17). But these only are *upper bounds*, and we would like to know whether they match the true order of magnitude of their coverages —at least in worst case, since one can for instance get $\Delta\mathbb{E} = 0$ for QQM by choosing $\alpha = 1 - M_{\ell,k}$ for some $(\ell, k) \in [n] \times [m]$, or for CentralM by choosing $\alpha \in \{\frac{r}{n_c+1} : r \in [n_c+1]\}$. Furthermore, knowing the true (worst-case) order of magnitude of the coverage of each algorithm is crucial to determine when one of the federated prediction sets we propose should be preferred to another, and for knowing precisely what may be lost by considering the one-shot FL setting instead of the centralized setting.

**Methods.** In order to answer these questions, for each algorithm considered, we evaluate below the rates of convergence towards zero of $\Delta\mathbb{E}$, $\Delta q_\beta$ and $\Delta q_{1-\beta}$ as $m$ and $n$ increase. The choice of the quantile orders $\beta$ and $(1-\beta)$ comes from the fact that (i) the conditional validity is equivalent to $\Delta q_\beta \ge 0$, so for prediction sets satisfying this condition, knowing how tight is this inequality in worst case is meaningful, and (ii) since $\beta = 0.2$, the $\beta$ and $(1-\beta)$-quantiles of the coverage are the bounds of an interval containing “typical values” of the coverage. In particular, by definition, the coverage $1-\alpha(\mathcal{D})$ is below $(1-\alpha) + \Delta q_{1-\beta}$ with probability $1-\beta = 80\%$.

We consider values of (m, n) in the grid {[10<sup>i/3</sup>] : i ∈ [9]}<sup>2</sup>. For each pair (m, n) and each algorithm, we compute ΔE, Δq<sub>β</sub> and Δq<sub>1-β</sub>. Then, for each algorithm, using empirical risk minimization with the Huber loss [24], we robustly fit the log-linear regression model log y = log(c) − γ log(m) − δ log(n) + ε, where ε is some residual term, c > 0 and γ, δ, n ∈ R are the model parameters, and y is either ΔE, Δq<sub>β</sub> or Δq<sub>1-β</sub>. Note that by construction, ΔE ≥ 0 for marginally-valid algorithms, and Δq<sub>1-β</sub> ≥ Δq<sub>β</sub> ≥ 0 for conditionally-valid algorithms. The estimated values of c, γ, δ for each algorithm and each quantity of interest are reported in Table 1. Plots showing the values of ΔE, Δq<sub>β</sub>, Δq<sub>1-β</sub> (together with their log-linear model approximation) are provided in Figures 1 and 3, and in Appendix J.1.

In order to compare the performance of the algorithms more closely, we also plot in
Figures 2 and 4 the full cdfs of the coverage distribution for two specific pairs (m, n),
(200, 20) and (20, 200), and report the corresponding expectations, standard-deviations
(computed by numerically integrating the cdfs), and $\zeta$-quantiles for $\zeta \in \{\beta, 1 - \beta\}$ in
Table 2.
more importantly, universal – see Eq. (7) and the discussion below for centralized algo-
rithms, Theorem 10 for federated algorithms with equal $n_j$ and Theorem 20 for federated
algorithms with general $n_j$. We also have closed-form formulas for the expected coverage
when $F_S$ is continuous, by Eq. (6) for centralized algorithms, and by Theorems 5 and 19
for our federated algorithms. Under this *generic setting*, we thus consider simultaneously
all learning problems, data distributions, predictors $\hat{f}$ and score functions $s$ such that the
scores cdf $F_S$ is continuous.

Throughout this subsection, for each algorithm considered, denoting by $1 - \alpha(\mathcal{D})$ its (random) coverage, we are interested in $F_{1-\alpha(\mathcal{D})}$ the coverage cdf, $\Delta\mathbb{E} := \mathbb{E}[1 - \alpha(\mathcal{D})] - (1 - \alpha)$ the difference between the expected coverage and the nominal coverage $(1 - \alpha)$, and, for several values of $\zeta \in (0, 1)$, $\Delta q_{\zeta} := F_{1-\alpha(\mathcal{D})}^{-1}(\zeta) - (1 - \alpha)$ the difference between the $\zeta$-quantile of the coverage and the nominal coverage.

6.1.1. Equal $n_j$

We first compare QQM, QQM-Fast, QQC, QQC-Fast, CentralM and CentralC under Assumption 1, that is, when each agent $j \in [m]$ has the same number $n_j = n$ of calibration data points. In Section 4, we prove that $\Delta\mathbb{E} = \mathcal{O}(m^{-1}n^{-1/2})$ for our marginally valid federated prediction sets (Theorem 16) and that $\Delta q_{1-\beta} = \mathcal{O}(m^{-1/2}n^{-1/2})$ for our training-conditionally valid federated prediction sets (Theorem 17). But these only are upper bounds, and we would like to know whether they match the true order of magnitude of their coverages —at least in worst case, since one can for instance get $\Delta\mathbb{E} = 0$ for QQM by choosing $\alpha = 1 - M_{\ell,k}$ for some $(\ell, k) \in [n] \times [m]$, or for CentralM by choosing $\alpha \in \{\frac{r}{n_c+1} : r \in [n_c+1]\}$. Furthermore, knowing the true (worst-case) order of magnitude of the coverage of each algorithm is crucial to determine when one of the federated prediction sets we propose should be preferred to another, and for knowing precisely what may be lost by considering the one-shot FL setting instead of the centralized setting.

**Methods.** In order to answer these questions, for each algorithm considered, we evaluate below the rates of convergence towards zero of $\Delta\mathbb{E}$, $\Delta q_\beta$ and $\Delta q_{1-\beta}$ as $m$ and $n$ increase. The choice of the quantile orders $\beta$ and $(1-\beta)$ comes from the fact that (i) the conditional validity is equivalent to $\Delta q_\beta \ge 0$, so for prediction sets satisfying this condition, knowing how tight is this inequality in worst case is meaningful, and (ii) since $\beta = 0.2$, the $\beta$ and $(1-\beta)$-quantiles of the coverage are the bounds of an interval containing “typical values” of the coverage. In particular, by definition, the coverage $1-\alpha(\mathcal{D})$ is below $(1-\alpha) + \Delta q_{1-\beta}$ with probability $1-\beta = 80\%$.

We consider values of $(m, n)$ in the grid $\{\lceil 10^{i/3} \rceil : i \in [9]\}^2$. For each pair $(m, n)$ and each algorithm, we compute $\Delta\mathbb{E}$, $\Delta q_\beta$ and $\Delta q_{1-\beta}$. Then, for each algorithm, using empirical risk minimization with the Huber loss [24], we robustly fit the log-linear regression model $\log y = \log(c) - \gamma \log(m) - \delta \log(n) + \varepsilon$, where $\varepsilon$ is some residual term, $c > 0$ and $\gamma, \delta \in \mathbb{R}$ are the model parameters, and $y$ is either $\Delta\mathbb{E}$, $\Delta q_\beta$ or $\Delta q_{1-\beta}$. Note that by construction, $\Delta\mathbb{E} \ge 0$ for marginally-valid algorithms, and $\Delta q_{1-\beta} \ge \Delta q_\beta \ge 0$ for conditionally-valid algorithms. The estimated values of $c, \gamma, \delta$ for each algorithm and each quantity of interest are reported in Table 1. Plots showing the values of $\Delta\mathbb{E}, \Delta q_\beta, \Delta q_{1-\beta}$ (together with their log-linear model approximation) are provided in Figures 1 and 3, and in Appendix J.1.

In order to compare the performance of the algorithms more closely, we also plot in
Figures 2 and 4 the full cdfs of the coverage distribution for two specific pairs $(m, n)$,
(200, 20) and (20, 200), and report the corresponding expectations, standard-deviations
(computed by numerically integrating the cdfs), and $\zeta$-quantiles for $\zeta \in \{\beta, 1 - \beta\}$ in
Table 2.
<table><caption>TABLE 1
Estimated parameters of the log-linear model $log y = log(c_i) - \gamma_i log(m) - \delta_i log(n)$ where y is either $ΔE$, $Δq_β$ or $Δq_{1-β}$, for the six algorithms compared in Section 6.1.1; see text for details.</caption><thead><tr><th rowspan="2">Method</th><th colspan="3">ΔE ≈ c<sub>1</sub>m<sup>-γ<sub>1</sub></sup>n<sup>-δ<sub>1</sub></sup></th><th colspan="3">Δq<sub>β</sub> ≈ c<sub>2</sub>m<sup>-γ<sub>2</sub></sup>n<sup>-δ<sub>2</sub></sup></th><th colspan="3">Δq<sub>1-β</sub> ≈ c<sub>3</sub>m<sup>-γ<sub>3</sub></sup>n<sup>-δ<sub>3</sub></sup></th></tr><tr><th>c<sub>1</sub></th><th>γ<sub>1</sub></th><th>δ<sub>1</sub></th><th>c<sub>2</sub></th><th>γ<sub>2</sub></th><th>δ<sub>2</sub></th><th>c<sub>3</sub></th><th>γ<sub>3</sub></th><th>δ<sub>3</sub></th></tr></thead><tbody><tr><td>CentralM</td><td>0.502</td><td>0.999</td><td>0.999</td><td>0.235</td><td>0.498</td><td>0.498</td><td>0.269</td><td>0.501</td><td>0.501</td></tr><tr><td>QQM</td><td>0.924</td><td>1.026</td><td>1.019</td><td>0.463</td><td>0.492</td><td>0.487</td><td>0.522</td><td>0.501</td><td>0.495</td></tr><tr><td>QQM-Fast</td><td>0.336</td><td>1.001</td><td>0.582</td><td>0.227</td><td>0.483</td><td>0.499</td><td>0.400</td><td>0.512</td><td>0.504</td></tr><tr><td>CentralC</td><td>0.257</td><td>0.501</td><td>0.501</td><td>0.590</td><td>1.014</td><td>1.014</td><td>0.504</td><td>0.499</td><td>0.499</td></tr><tr><td>QQC</td><td>0.341</td><td>0.507</td><td>0.502</td><td>0.508</td><td>0.910</td><td>0.847</td><td>0.637</td><td>0.502</td><td>0.497</td></tr><tr><td>QQC-Fast</td><td>0.676</td><td>0.498</td><td>0.501</td><td>0.400</td><td>0.503</td><td>0.509</td><td>0.958</td><td>0.496</td><td>0.498</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>FIG 1. Marginally-valid algorithms: log-log plot of $ΔE$ as a function of $m$ (left) or $n$ (right). Lines show the approximation $log ΔE ≈ log(c_1) - \gamma_1 log(m) - \delta_1 log(n)$ with $c_1, \gamma_1, \delta_1$ given by Table 1. Plain lines and dots correspond to $n = 10$ (left) or $m = 10$ (right). Dashed lines and diamonds correspond to $n = 10^4$ (left) or $m = 10^4$ (right).</figcaption></figure>

**Marginally-valid algorithms.** For QQM and CentralM, according to Table 1, $ΔE$ decrease to zero at the same rate, close to $m^{-1}n^{-1}$, with only a multiplicative constant ≈ 2 in favour of CentralM. Overall, the difference between expected coverages of QQM and CentralM is small, as shown by Figure 1. In comparison, QQM-Fast shows a worse performance with $ΔE$ decreasing to zero at a rate close to $m^{-1}n^{-1/2}$ (Table 1). This leads to a significant gap between the performances of QQM-Fast and the two other ones as shown by Figure 1. For $(m, n) \in \{(200, 20), (20, 200)\}$, the coverage cdfs of the three algorithms have similar shapes (Figure 2) apart from a shift corresponding to already mentioned differences between expectations, and a slightly larger standard-deviation for federated algorithms compared to CentralM (see also Table 2). The $(1 - \beta)$-quantile of the coverage is also slightly larger for the federated algorithms compared to CentralM, even if they all are of the same order of magnitude $(1 - \alpha) + O(m^{-1/2}n^{-1/2})$ at first order (see Tables 1 and 2).

Note also that Table 1 suggests that our theoretical expected coverage upper bound (Theorem 16) $(1 - \alpha) + O(m^{-1}n^{-1/2})$ provides the correct worst-case order of magnitude for QQM-Fast (even if the estimated exponent for $n$ is $\delta_1 = 0.58$ instead of exactly $1/2$), and supports our conjecture that it could be improved to $(1 - \alpha) + O(m^{-1}n^{-1})$ for QQM.

Overall, these numerical results show that among one-shot FL prediction sets, QQM should be preferred to QQM-Fast as long as its computational complexity remains tractable (keeping in mind Remark 15 about the computational complexity of our federated algorithms). Then, using QQM yields a mild loss compared to CentralM, with a one-shot FL algorithm. Note however that the expected coverage of QQM-Fast also converges to $1 - \alpha$ when $mn$ tends to infinity, as proved by Theorem 16 and illustrated in this section, so when $m$ or $n$ is too large so that one must use QQM-Fast, the loss in terms of
<table><caption>TABLE 1
Estimated parameters of the log-linear model $log y = log(c_i) - \gamma_i log(m) - \delta_i log(n)$ where y is either $\Delta E$, $\Delta q_β$ or $\Delta q_{1-β}$, for the six algorithms compared in Section 6.1.1; see text for details.</caption><thead><tr><th rowspan="2">Method</th><th colspan="3">ΔE ≈ c<sub>1</sub>m<sup>-γ<sub>1</sub></sup>n<sup>-δ<sub>1</sub></sup></th><th colspan="3">Δq<sub>β</sub> ≈ c<sub>2</sub>m<sup>-γ<sub>2</sub></sup>n<sup>-δ<sub>2</sub></sup></th><th colspan="3">Δq<sub>1-β</sub> ≈ c<sub>3</sub>m<sup>-γ<sub>3</sub></sup>n<sup>-δ<sub>3</sub></sup></th></tr><tr><th>c<sub>1</sub></th><th>γ<sub>1</sub></th><th>δ<sub>1</sub></th><th>c<sub>2</sub></th><th>γ<sub>2</sub></th><th>δ<sub>2</sub></th><th>c<sub>3</sub></th><th>γ<sub>3</sub></th><th>δ<sub>3</sub></th></tr></thead><tbody><tr><td>CentralM</td><td>0.502</td><td>0.999</td><td>0.999</td><td>0.235</td><td>0.498</td><td>0.498</td><td>0.269</td><td>0.501</td><td>0.501</td></tr><tr><td>QQM</td><td>0.924</td><td>1.026</td><td>1.019</td><td>0.463</td><td>0.492</td><td>0.487</td><td>0.522</td><td>0.501</td><td>0.495</td></tr><tr><td>QQM-Fast</td><td>0.336</td><td>1.001</td><td>0.582</td><td>0.227</td><td>0.483</td><td>0.499</td><td>0.400</td><td>0.512</td><td>0.504</td></tr><tr><td>CentralC</td><td>0.257</td><td>0.501</td><td>0.501</td><td>0.590</td><td>1.014</td><td>1.014</td><td>0.504</td><td>0.499</td><td>0.499</td></tr><tr><td>QQC</td><td>0.341</td><td>0.507</td><td>0.502</td><td>0.508</td><td>0.910</td><td>0.847</td><td>0.637</td><td>0.502</td><td>0.497</td></tr><tr><td>QQC-Fast</td><td>0.676</td><td>0.498</td><td>0.501</td><td>0.400</td><td>0.503</td><td>0.509</td><td>0.958</td><td>0.496</td><td>0.498</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>FIG 1. Marginally-valid algorithms: log-log plot of $\Delta E$ as a function of $m$ (left) or $n$ (right). Lines show the approximation $log \Delta E \approx \log(c_1) - \gamma_1 \log(m) - \delta_1 \log(n)$ with $c_1, \gamma_1, \delta_1$ given by Table 1. Plain lines and dots correspond to $n = 10$ (left) or $m = 10$ (right). Dashed lines and diamonds correspond to $n = 10^4$ (left) or $m = 10^4$ (right).</figcaption></figure>

**Marginally-valid algorithms.** For QQM and CentralM, according to Table 1, $\Delta E$ decrease to zero at the same rate, close to $m^{-1}n^{-1}$, with only a multiplicative constant $\approx 2$ in favour of CentralM. Overall, the difference between expected coverages of QQM and CentralM is small, as shown by Figure 1. In comparison, QQM-Fast shows a worse performance with $\Delta E$ decreasing to zero at a rate close to $m^{-1}n^{-1/2}$ (Table 1). This leads to a significant gap between the performances of QQM-Fast and the two other ones as shown by Figure 1. For $(m, n) \in \{(200, 20), (20, 200)\}$, the coverage cdfs of the three algorithms have similar shapes (Figure 2) apart from a shift corresponding to already mentioned differences between expectations, and a slightly larger standard-deviation for federated algorithms compared to CentralM (see also Table 2). The $(1 - \beta)$-quantile of the coverage is also slightly larger for the federated algorithms compared to CentralM, even if they all are of the same order of magnitude $(1 - \alpha) + O(m^{-1/2}n^{-1/2})$ at first order (see Tables 1 and 2).

Note also that Table 1 suggests that our theoretical expected coverage upper bound (Theorem 16) $(1 - \alpha) + O(m^{-1}n^{-1/2})$ provides the correct worst-case order of magnitude for QQM-Fast (even if the estimated exponent for $n$ is $\delta_1 = 0.58$ instead of exactly $1/2$), and supports our conjecture that it could be improved to $(1 - \alpha) + O(m^{-1}n^{-1})$ for QQM.

Overall, these numerical results show that among one-shot FL prediction sets, QQM should be preferred to QQM-Fast as long as its computational complexity remains tractable (keeping in mind Remark 15 about the computational complexity of our federated algorithms). Then, using QQM yields a mild loss compared to CentralM, with a one-shot FL algorithm. Note however that the expected coverage of QQM-Fast also converges to $1 - \alpha$ when $mn$ tends to infinity, as proved by Theorem 16 and illustrated in this section, so when $m$ or $n$ is too large so that one must use QQM-Fast, the loss in terms of
<figure><img src="image_4.png" /><figcaption>FIG 2. Marginally-valid algorithms: cdf of the coverage $1 - \alpha(D)$. The mean of each distribution is shown by a dot and the quantiles of order $\beta$ and $1 - \beta$ by crosses. Left: $(m, n) = (200, 20)$. Right: $(m, n) = (20, 200)$. See Table 2 for additional information.</figcaption></figure>

<table><caption>TABLE 2
Expectation, standard-deviation, $\beta$-quantile and $(1 - \beta)$-quantile of the coverage $1 - \alpha(D)$ of the algorithms compared in Section 6.1.1 (equal $n_j$).</caption><thead><tr><th rowspan="2">Method</th><th colspan="4">(m, n) = (200, 20)</th><th colspan="4">(m, n) = (20, 200)</th></tr><tr><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th></tr></thead><tbody><tr><td>CentralM</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td></tr><tr><td>QQM</td><td>0.90004</td><td>0.00604</td><td>0.89500</td><td>0.90515</td><td>0.90012</td><td>0.00603</td><td>0.89510</td><td>0.90522</td></tr><tr><td>QQM-Fast</td><td>0.90084</td><td>0.00577</td><td>0.89601</td><td>0.90572</td><td>0.90070</td><td>0.00585</td><td>0.89580</td><td>0.90563</td></tr><tr><td>CentralC</td><td>0.90402</td><td>0.00466</td><td>0.90013</td><td>0.90796</td><td>0.90402</td><td>0.00466</td><td>0.90013</td><td>0.90796</td></tr><tr><td>QQC</td><td>0.90524</td><td>0.00569</td><td>0.90048</td><td>0.91004</td><td>0.90526</td><td>0.00589</td><td>0.90036</td><td>0.91025</td></tr><tr><td>QQC-Fast</td><td>0.91084</td><td>0.00558</td><td>0.90618</td><td>0.91556</td><td>0.91046</td><td>0.00560</td><td>0.90579</td><td>0.91519</td></tr></tbody></table>

expected coverage remain very small; for instance, when $m = 200$, the expected coverage of QQM-Fast is 0.90084 while the one of QQM is 0.90004 (Table 2).

**Conditionally-valid algorithms.** The $(1 - \beta)$-quantiles of the coverages of the three conditionally-valid algorithms are of the same order of magnitude $1 - \alpha + O(m^{-1/2}n^{-1/2})$, with constants within a factor 2 in front of the remainder term (Table 1, where the estimated $\gamma_3, \delta_3$ all are very close to $1/2$; see also Figure 19 in Appendix J.1). This matches our theoretical upper bound (Theorem 10), suggesting its tightness. Bigger differences appear when considering the $\beta$-quantiles of the coverage, which seem to be of order $1 - \alpha + O(m^{-1}n^{-1})$ for CentralC and QQC (with $\gamma_2, \delta_2$ slightly smaller than 1 for QQC), while it is clearly larger, of order $1 - \alpha + O(m^{-1/2}n^{-1/2})$, for QQC-Fast, according to Table 1 and Figure 3. A good summary of what happens here may be found in Figure 4: CentralC and QQC tightly adjust the $\beta$-quantile of the coverage (which is the one that must be above $1 - \alpha$), better than QQC-Fast.

Overall, as expected, the computationally more efficient method QQC-Fast is also a bit more conservative than the other two methods, which would suggest to use QQC (in a one-shot FL context) if one has enough computational power, leading to only a small loss compared to the centralized case. Note finally that all three training-conditionally valid algorithms also are marginally valid in the settings considered by Figure 4, since the expectations of their coverages are larger than their $\beta$-quantiles (which is not surprising since $\beta = 0.2 < 1/2$ and the medians here are close to the expectations).
<figure><img src="image_4.png" /><figcaption>FIG 2. Marginally-valid algorithms: cdf of the coverage $1 - \alpha(D)$. The mean of each distribution is shown by a dot and the quantiles of order $\beta$ and $1 - \beta$ by crosses. Left: $(m, n) = (200, 20)$. Right: $(m, n) = (20, 200)$. See Table 2 for additional information.</figcaption></figure>

<table><caption>TABLE 2
Expectation, standard-deviation, $\beta$-quantile and $(1 - \beta)$-quantile of the coverage $1 - \alpha(D)$ of the algorithms compared in Section 6.1.1 (equal $n_j$).</caption><thead><tr><th rowspan="2">Method</th><th colspan="4">(m, n) = (200, 20)</th><th colspan="4">(m, n) = (20, 200)</th></tr><tr><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th></tr></thead><tbody><tr><td>CentralM</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td></tr><tr><td>QQM</td><td>0.90004</td><td>0.00604</td><td>0.89500</td><td>0.90515</td><td>0.90012</td><td>0.00603</td><td>0.89510</td><td>0.90522</td></tr><tr><td>QQM-Fast</td><td>0.90084</td><td>0.00577</td><td>0.89601</td><td>0.90572</td><td>0.90070</td><td>0.00585</td><td>0.89580</td><td>0.90563</td></tr><tr><td>CentralC</td><td>0.90402</td><td>0.00466</td><td>0.90013</td><td>0.90796</td><td>0.90402</td><td>0.00466</td><td>0.90013</td><td>0.90796</td></tr><tr><td>QQC</td><td>0.90524</td><td>0.00569</td><td>0.90048</td><td>0.91004</td><td>0.90526</td><td>0.00589</td><td>0.90036</td><td>0.91025</td></tr><tr><td>QQC-Fast</td><td>0.91084</td><td>0.00558</td><td>0.90618</td><td>0.91556</td><td>0.91046</td><td>0.00560</td><td>0.90579</td><td>0.91519</td></tr></tbody></table>

expected coverage remain very small; for instance, when $m = 200$, the expected coverage of QQM-Fast is 0.90084 while the one of QQM is 0.90004 (Table 2).

**Conditionally-valid algorithms.** The $(1 - \beta)$-quantiles of the coverages of the three conditionally-valid algorithms are of the same order of magnitude $1 - \alpha + O(m^{-1/2}n^{-1/2})$, with constants within a factor 2 in front of the remainder term (Table 1, where the estimated $\gamma_3, \delta_3$ all are very close to $1/2$; see also Figure 19 in Appendix J.1). This matches our theoretical upper bound (Theorem 10), suggesting its tightness. Bigger differences appear when considering the $\beta$-quantiles of the coverage, which seem to be of order $1 - \alpha + O(m^{-1}n^{-1})$ for CentralC and QQC (with $\gamma_2, \delta_2$ slightly smaller than 1 for QQC), while it is clearly larger, of order $1 - \alpha + O(m^{-1/2}n^{-1/2})$, for QQC-Fast, according to Table 1 and Figure 3. A good summary of what happens here may be found in Figure 4: CentralC and QQC tightly adjust the $\beta$-quantile of the coverage (which is the one that must be above $1 - \alpha$), better than QQC-Fast.

Overall, as expected, the computationally more efficient method QQC-Fast is also a bit more conservative than the other two methods, which would suggest to use QQC (in a one-shot FL context) if one has enough computational power, leading to only a small loss compared to the centralized case. Note finally that all three training-conditionally valid algorithms also are marginally valid in the settings considered by Figure 4, since the expectations of their coverages are larger than their $\beta$-quantiles (which is not surprising since $\beta = 0.2 < 1/2$ and the medians here are close to the expectations).
<figure><img src="image_5.png" /><figcaption>FIG 3. Conditionally-valid algorithms: log-log plot of $\Delta q_{\beta}$ as a function of $m$ (left) or $n$ (right). Lines show the approximation $\log \Delta q_{\beta} \approx \log(c_2) - \gamma_2 \log(m) - \delta_2 \log(n)$ with $c_2, \gamma_2, \delta_2$ given by Table 1. Plain lines and dots correspond to $n = 10$ (left) or $m = 10$ (right). Dashed lines and diamonds correspond to $n = 10^4$ (left) or $m = 10^4$ (right).</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIG 4. Conditionally-valid algorithms: cdf of the coverage $1 - \alpha(D)$. The mean of each distribution is shown by a dot and the quantiles of order $\beta$ and $1 - \beta$ by crosses. Left: $(m, n) = (200, 20)$. Right: $(m, n) = (20, 200)$. See Table 2 for additional information.</figcaption></figure>

### 6.1.2. Different $n_j$

We now study the case where the $n_j$ are different, so that only QQM-$n_j$ and QQC-$n_j$ are available in the one-shot FL case.

**Methods.** We consider several settings with a total of $N = 4000$ calibration points distributed across $m$ agents, where $m$ divides $N$. For each value of $m$ considered, the values of $(n_1, \dots, n_m)$ are chosen (once for all) randomly, according to a multinomial distribution with parameters $N$ and $(1/m, \dots, 1/m)$; in other words, each of the $N$ calibration points is uniformly assigned among the $m$ agents, independently. Figure 20 in Appendix J.2.1 provides the exact values of the $n_j$ for $m = 4$ and $m = 25$.

In addition to QQM-$n_j$ and QQC-$n_j$, which are the only ones able to deal with agents having different number of data points in a one shot FL setting, we also consider several other algorithms for comparison:

* Centralized algorithms (CentralM and CentralC);

* Algorithms 5–6 with data split equally into $m$ agents (hence having each $n_j = N/m$ points), that we call QQM-(N/m) and QQC-(N/m), respectively;

* QQM and QQC, with data split equally into $m$ agents, as in Section 6.1.1.

For each of these algorithms, we report the values of the expectation, standard-deviation
<figure><img src="image_5.png" /><figcaption>FIG 3. Conditionally-valid algorithms: log-log plot of $\Delta q_{\beta}$ as a function of $m$ (left) or $n$ (right). Lines show the approximation $\log \Delta q_{\beta} \approx \log(c_2) - \gamma_2 \log(m) - \delta_2 \log(n)$ with $c_2, \gamma_2, \delta_2$ given by Table 1. Plain lines and dots correspond to $n = 10$ (left) or $m = 10$ (right). Dashed lines and diamonds correspond to $n = 10^4$ (left) or $m = 10^4$ (right).</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIG 4. Conditionally-valid algorithms: cdf of the coverage $1 - \alpha(D)$. The mean of each distribution is shown by a dot and the quantiles of order $\beta$ and $1 - \beta$ by crosses. Left: $(m, n) = (200, 20)$. Right: $(m, n) = (20, 200)$. See Table 2 for additional information.</figcaption></figure>

### 6.1.2. Different $n_j$

We now study the case where the $n_j$ are different, so that only QQM-$n_j$ and QQC-$n_j$ are available in the one-shot FL case.

**Methods.** We consider several settings with a total of $N = 4000$ calibration points distributed across $m$ agents, where $m$ divides $N$. For each value of $m$ considered, the values of $(n_1, \dots, n_m)$ are chosen (once for all) randomly, according to a multinomial distribution with parameters $N$ and $(1/m, \dots, 1/m)$; in other words, each of the $N$ calibration points is uniformly assigned among the $m$ agents, independently. Figure 20 in Appendix J.2.1 provides the exact values of the $n_j$ for $m = 4$ and $m = 25$.

In addition to QQM-$n_j$ and QQC-$n_j$, which are the only ones able to deal with agents having different number of data points in a one shot FL setting, we also consider several other algorithms for comparison:

* Centralized algorithms (CentralM and CentralC);

* Algorithms 5–6 with data split equally into $m$ agents (hence having each $n_j = N/m$ points), that we call QQM-(N/m) and QQC-(N/m), respectively;

* QQM and QQC, with data split equally into $m$ agents, as in Section 6.1.1.

For each of these algorithms, we report the values of the expectation, standard-deviation
and $\zeta$-quantile for $\zeta \in \{\beta, 1 - \beta\}$ of their coverages when $m \in \{4, 25\}$ in Table 3, and we plot the cdfs of their coverages when $m = 25$ in Figure 5. Since specific values of $m$ can be misleading (as explained at the beginning of Section 6.1.1), we report $\Delta E$ (respectively, $\Delta q_{\beta}$) as a function of $m$ for marginally-valid (respectively, conditionally-valid) algorithms in Figure 6; for completeness, the values of $\Delta q_{1-\beta}$ for conditionally-valid algorithms are plotted in Figure 21 of Appendix J.2.1. Note that the values $m \in \{4, 25\}$ in Table 3 and $m = 25$ in Figure 5 have been chosen because they are typical of the worst-case performance of most algorithms, according to Figure 6.

<table><caption>TABLE 3</caption><thead><tr><th rowspan="2">Method</th><th colspan="4">(m, N) = (4, 4000)</th><th colspan="4">(m, N) = (25, 4000)</th></tr><tr><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th></tr></thead><tbody><tr><td>CentralM</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td></tr><tr><td>QQM</td><td>0.90009</td><td>0.005659</td><td>0.89535</td><td>0.90485</td><td>0.90017</td><td>0.00706</td><td>0.89435</td><td>0.90617</td></tr><tr><td>QQM-(N/m)</td><td>0.90305</td><td>0.00558</td><td>0.89838</td><td>0.90775</td><td>0.90217</td><td>0.00581</td><td>0.89731</td><td>0.90709</td></tr><tr><td>QQM-n<sub>j</sub></td><td>0.90335</td><td>0.00558</td><td>0.89869</td><td>0.90804</td><td>0.90238</td><td>0.00583</td><td>0.89755</td><td>0.90733</td></tr><tr><td>CentralC</td><td>0.90402</td><td>0.00465</td><td>0.90012</td><td>0.90796</td><td>0.90402</td><td>0.00465</td><td>0.90012</td><td>0.90796</td></tr><tr><td>QQC</td><td>0.90503</td><td>0.00553</td><td>0.90040</td><td>0.90968</td><td>0.90549</td><td>0.00581</td><td>0.90062</td><td>0.91039</td></tr><tr><td>QQC-(N/m)</td><td>0.90969</td><td>0.00622</td><td>0.90444</td><td>0.91487</td><td>0.90679</td><td>0.00569</td><td>0.90203</td><td>0.91160</td></tr><tr><td>QQC-n<sub>j</sub></td><td>0.90997</td><td>0.00620</td><td>0.90474</td><td>0.91512</td><td>0.90698</td><td>0.00567</td><td>0.90222</td><td>0.91177</td></tr></tbody></table>

Different $n_j$: Expectation, standard-deviation, $\beta$-quantile and $(1 - \beta)$-quantile of the coverage $1 - \alpha(D)$ of the eight algorithms listed at the beginning of Section 6.1.2.

<figure><img src="image_7.png" /><figcaption>FIG 5. Different $n_j$: cdf of the coverage $1 - \alpha(D)$ of the algorithms considered in Section 6.1.2 with $N = \sum_{j=1}^{m} n_j = 4000$ data points distributed among $m = 25$ agents. The mean of each distribution is shown by a dot and the quantiles of order $\beta$ and $1 - \beta$ by crosses. See Table 3 for additional information. Left: marginally-valid algorithms: CentralM, QQM with $n_j = N/m$ for all $j$, QQM-(N/m) (that is, Algorithm 5 with $n_j = N/m$ for all $j$) and QQM-n$_j$. Right: conditionally-valid algorithms: CentralC, QQC with $n_j = N/m$ for all $j$, QQC-(N/m) (that is, Algorithm 6 with $n_j = N/m$ for all $j$) and QQC-n$_j$.</figcaption></figure>
and $\zeta$-quantile for $\zeta \in \{\beta, 1 - \beta\}$ of their coverages when $m \in \{4, 25\}$ in Table 3, and we plot the cdfs of their coverages when $m = 25$ in Figure 5. Since specific values of $m$ can be misleading (as explained at the beginning of Section 6.1.1), we report $\Delta E$ (respectively, $\Delta q_{\beta}$) as a function of $m$ for marginally-valid (respectively, conditionally-valid) algorithms in Figure 6; for completeness, the values of $\Delta q_{1-\beta}$ for conditionally-valid algorithms are plotted in Figure 21 of Appendix J.2.1. Note that the values $m \in \{4, 25\}$ in Table 3 and $m = 25$ in Figure 5 have been chosen because they are typical of the worst-case performance of most algorithms, according to Figure 6.

<table><caption>TABLE 3</caption><thead><tr><th rowspan="2">Method</th><th colspan="4">(m, N) = (4, 4000)</th><th colspan="4">(m, N) = (25, 4000)</th></tr><tr><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th><th>E[·]</th><th>Std</th><th>q<sub>β</sub></th><th>q<sub>1-β</sub></th></tr></thead><tbody><tr><td>CentralM</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td><td>0.90002</td><td>0.00474</td><td>0.89605</td><td>0.90403</td></tr><tr><td>QQM</td><td>0.90009</td><td>0.005659</td><td>0.89535</td><td>0.90485</td><td>0.90017</td><td>0.00706</td><td>0.89435</td><td>0.90617</td></tr><tr><td>QQM-(N/m)</td><td>0.90305</td><td>0.00558</td><td>0.89838</td><td>0.90775</td><td>0.90217</td><td>0.00581</td><td>0.89731</td><td>0.90709</td></tr><tr><td>QQM-n<sub>j</sub></td><td>0.90335</td><td>0.00558</td><td>0.89869</td><td>0.90804</td><td>0.90238</td><td>0.00583</td><td>0.89755</td><td>0.90733</td></tr><tr><td>CentralC</td><td>0.90402</td><td>0.00465</td><td>0.90012</td><td>0.90796</td><td>0.90402</td><td>0.00465</td><td>0.90012</td><td>0.90796</td></tr><tr><td>QQC</td><td>0.90503</td><td>0.00553</td><td>0.90040</td><td>0.90968</td><td>0.90549</td><td>0.00581</td><td>0.90062</td><td>0.91039</td></tr><tr><td>QQC-(N/m)</td><td>0.90969</td><td>0.00622</td><td>0.90444</td><td>0.91487</td><td>0.90679</td><td>0.00569</td><td>0.90203</td><td>0.91160</td></tr><tr><td>QQC-n<sub>j</sub></td><td>0.90997</td><td>0.00620</td><td>0.90474</td><td>0.91512</td><td>0.90698</td><td>0.00567</td><td>0.90222</td><td>0.91177</td></tr></tbody></table>

Different $n_j$: Expectation, standard-deviation, $\beta$-quantile and $(1 - \beta)$-quantile of the coverage $1 - \alpha(D)$ of the eight algorithms listed at the beginning of Section 6.1.2.

<figure><img src="image_7.png" /><figcaption>FIG 5. Different $n_j$: cdf of the coverage $1 - \alpha(D)$ of the algorithms considered in Section 6.1.2 with $N = \sum_{j=1}^{m} n_j = 4000$ data points distributed among $m = 25$ agents. The mean of each distribution is shown by a dot and the quantiles of order $\beta$ and $1 - \beta$ by crosses. See Table 3 for additional information. Left: marginally-valid algorithms: CentralM, QQM with $n_j = N/m$ for all $j$, QQM-(N/m) (that is, Algorithm 5 with $n_j = N/m$ for all $j$) and QQM-n$_j$. Right: conditionally-valid algorithms: CentralC, QQC with $n_j = N/m$ for all $j$, QQC-(N/m) (that is, Algorithm 6 with $n_j = N/m$ for all $j$) and QQC-n$_j$.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>FIG 6. Different $n_j$: log-log plot of the performance (left: $\Delta E$; right: $\Delta q_\beta$) of the algorithms considered in Section 6.1.2 (left: marginally-valid algorithms; right: conditionally-valid algorithms) as a function of the number of agents $m$. The total number of data points $N = \sum_{j=1}^m n_j = 4000$ is fixed and $m$ varies within the set of divisors of $N$. The values when $m = 1, 2$ for QQC-(N/m) and QQC-$n_j$ are missing because there is no $k$ such that the resulting sets are conditionally valid.</figcaption></figure>

**Comparison to centralized algorithms and to federated algorithms with $n_j = n$.**
Let us start with marginally-valid algorithms, that is, the ones appearing in the top half of Table 3 and on the left of Figures 5–6. The typical ordering of their performance (for instance measured by their expected coverages) is not surprising: first CentralM, then QQM (with a small loss compared to CentralM, as already studied in Section 6.1.1), and finally QQM-(N/m) and QQM-$n_j$, with similar performances (and a larger loss compared to CentralM). In addition to the increase of expected coverage, the quantiles also increases slightly, with the same ordering. Nevertheless, QQM-$n_j$ has a reasonably good performance, with an expected coverage below $1 - \alpha + 0.005$.

One possible reason explaining the fact that QQM-$n_j$ is more conservative than the federated algorithms we propose for the case of equal $n_j$ (with the same overall sample size) can be the suboptimality of the choice $\ell_j^* = \lceil (1-\alpha)(n_j+1) \rceil$ made for computational reasons. Indeed, we see on Table 3 and Figures 5–6 that QQM-(N/m) and QQM-$n_j$ have similar performances and are not as good as QQM or CentralM.

Similar comments can be made about conditionally-valid algorithms, that is, the ones appearing in the bottom half of Table 3 and on the right of Figures 5–6, whose performance should primarily be measured by the $\beta$ and $(1-\beta)$-quantiles of their coverages.

**Impact of the number of agents $m$.** Let us now consider when the number of agents $m$ vary while the total number of samples $N$ is fixed. Once again, let us start with marginally-valid algorithms. First, notice that when $m = 1$ and $m = N$, the four algorithms considered choose the same pair $(\ell, k)$ by definition, hence they have the same performance. Then, putting aside the value $m = 1$, Figure 6 shows that the performance of both QQM-(N/m) and QQM-$n_j$ generally improve when $m$ increases, while the one of QQM is approximately constant. The fact that distributing the data across more agents can yield a better performance may seem surprising, but it can easily be explained. Indeed, as shown by Table 4 and Figure 22 in Appendix J.2.2, for QQM-(N/m), when both $m$ and $n := N/m$ vary, $\Delta E$ is approximately proportional to $m^{-1}(N/m)^{-1/2} = m^{-1/2}N^{-1/2}$. So, in the experiment of Figure 6, where $N$ is fixed, $\Delta E$ is approximately proportional to $m^{-1/2}$, hence it decreases when $m$ increases. In addition, we propose the following intuition for explaining the behaviors of both QQM-$n_j$ and QQM-(N/m): when $m$ increases, the algorithm has more options for $k \in \lceil m \rceil$ (while each $\ell_j$ remains fixed equal to $\ell_j^*$), allowing to adjust more precisely the coverage (in worst case), hence a
<figure><img src="image_8.png" /><figcaption>FIG 6. Different $n_j$: log-log plot of the performance (left: $\Delta E$; right: $\Delta q_\beta$) of the algorithms considered in Section 6.1.2 (left: marginally-valid algorithms; right: conditionally-valid algorithms) as a function of the number of agents $m$. The total number of data points $N = \sum_{j=1}^m n_j = 4000$ is fixed and $m$ varies within the set of divisors of $N$. The values when $m = 1, 2$ for QQC-(N/m) and QQC-$n_j$ are missing because there is no $k$ such that the resulting sets are conditionally valid.</figcaption></figure>

**Comparison to centralized algorithms and to federated algorithms with $n_j = n$.**
Let us start with marginally-valid algorithms, that is, the ones appearing in the top half of Table 3 and on the left of Figures 5–6. The typical ordering of their performance (for instance measured by their expected coverages) is not surprising: first CentralM, then QQM (with a small loss compared to CentralM, as already studied in Section 6.1.1), and finally QQM-(N/m) and QQM-$n_j$, with similar performances (and a larger loss compared to CentralM). In addition to the increase of expected coverage, the quantiles also increases slightly, with the same ordering. Nevertheless, QQM-$n_j$ has a reasonably good performance, with an expected coverage below $1 - \alpha + 0.005$.

One possible reason explaining the fact that QQM-$n_j$ is more conservative than the federated algorithms we propose for the case of equal $n_j$ (with the same overall sample size) can be the suboptimality of the choice $\ell_j^* = \lceil (1-\alpha)(n_j+1) \rceil$ made for computational reasons. Indeed, we see on Table 3 and Figures 5–6 that QQM-(N/m) and QQM-$n_j$ have similar performances and are not as good as QQM or CentralM.

Similar comments can be made about conditionally-valid algorithms, that is, the ones appearing in the bottom half of Table 3 and on the right of Figures 5–6, whose performance should primarily be measured by the $\beta$ and $(1-\beta)$-quantiles of their coverages.

**Impact of the number of agents $m$.** Let us now consider when the number of agents $m$ vary while the total number of samples $N$ is fixed. Once again, let us start with marginally-valid algorithms. First, notice that when $m = 1$ and $m = N$, the four algorithms considered choose the same pair $(\ell, k)$ by definition, hence they have the same performance. Then, putting aside the value $m = 1$, Figure 6 shows that the performance of both QQM-(N/m) and QQM-$n_j$ generally improve when $m$ increases, while the one of QQM is approximately constant. The fact that distributing the data across more agents can yield a better performance may seem surprising, but it can easily be explained. Indeed, as shown by Table 4 and Figure 22 in Appendix J.2.2, for QQM-(N/m), when both $m$ and $n := N/m$ vary, $\Delta E$ is approximately proportional to $m^{-1}(N/m)^{-1/2} = m^{-1/2}N^{-1/2}$. So, in the experiment of Figure 6, where $N$ is fixed, $\Delta E$ is approximately proportional to $m^{-1/2}$, hence it decreases when $m$ increases. In addition, we propose the following intuition for explaining the behaviors of both QQM-$n_j$ and QQM-(N/m): when $m$ increases, the algorithm has more options for $k \in \lceil m \rceil$ (while each $\ell_j$ remains fixed equal to $\ell_j^*$), allowing to adjust more precisely the coverage (in worst case), hence a
better performance. The fact that QQM behaves differently (with $\Delta E$ roughly constant when $m$ varies) should not be surprising, since the number of candidate values for $(\ell, k)$ is equal to $N = nm$ (hence it remains constant), and Table 1 shows that for QQM, $\Delta E$ is approximately proportional to $(mn)^{-1} = N^{-1}$.

For conditionally-valid algorithms, Figure 6 shows a similar behavior for $\Delta q_\beta$ (decreasing function of $m$ for QQC-$n_j$ and QQC-$\langle N/m \rangle$, roughly constant for QQC), for which we propose the same intuitive explanation (see also Table 4 and Figure 23 in Appendix J.2.2). Note however that QQC-$n_j$ and QQC-$\langle N/m \rangle$ do not coincide with QQC and CentralC when $m=1$ because of the choice made for $\ell_j$ in Algorithm 6, which prevents to find a value of $k$ satisfying the training-conditional guarantee. Other choices would be possible (see Remark 21 in Section 5).

**Conclusion.** Our one-shot FL algorithms dealing with non-equal $n_j$ provide prediction sets only slightly more conservative than their centralized counterparts, while being computationally tractable, hence they seem effective for performing CP in one-shot FL with different $n_j$. Note that the values of $m$ for which QQM-$n_j$ and QQC-$n_j$ are the most conservative are the small values $m \ge 2$, which precisely are the ones for which QQM-$n_j$ and QQC-$n_j$ could be improved (while remaining tractable) by choosing among a few values of $\ell_j$ for every $j \in \llbracket m \rrbracket$ (see Remark 21).

## 6.2. Real data

In this section, we evaluate the performance of each algorithm (in terms of coverage and length of the returned prediction sets) on five public-domain regression data sets also considered in [54] and [56]: physicochemical properties of protein tertiary structure (bio) [51], bike sharing (bike) [16], communities and crimes (community) [52], Tennessee's student teacher achievement ratio (star) [1], and concrete compressive strength (concrete) [64].

### 6.2.1. Setup

For each experiment, we split the full data set into three parts: a learning set (40%), a calibration set (40%), and a test set (20%). To simulate a FL scenario, we also split the calibration set in $m$ disjoint subsets of equal size $n$. We consider scenarios where either $m > n$ or $m < n$, with $\max\{m/n, n/m\} \in \{4, 8\}$ depending on the data set; the exact values of $(m, n)$ for each data set are given in Appendix J.3. All features are then standardized to have zero mean and unit variance. For each algorithm, we compute the empirical coverage obtained on the test set and the average length of the prediction set over the test set. These two metrics are collected over 50 different learning-calibration-test random splits.

Prediction sets are constructed using the Conformalized Quantile Regression method (CQR) [54], a popular variant of split CP directly compatible with our approach, following Remark 2 in Section 2.2. In CQR, $\hat{f}$ is $(\hat{f}_{\alpha/2}, \hat{f}_{1-\alpha/2})$ where $\hat{f}_{\delta}$ is a quantile regressor of order $\delta$ [30] and $s(x, y) = \max(\hat{f}_{\alpha/2}(x) - y, y - \hat{f}_{1-\alpha/2}(x))$, so that the prediction set $\{y \in \mathbb{R} : s(x, y) \le \hat{q}\} = [\hat{f}_{\alpha/2}(x)-\hat{q}, \hat{f}_{1-\alpha/2}(x)+\hat{q}]$ has a size adaptive to heteroscedasticity. In the following experiments $\hat{f}_{\alpha/2}$ and $\hat{f}_{1-\alpha/2}$ are quantile regression forests [44] built from the learning set only. The number of trees in the forest is set to 1000, the two parameters controlling the coverage rate on the learning data are tuned using cross-validation (within the learning set), and the remaining hyperparameters are set as done in [54].
better performance. The fact that QQM behaves differently (with $\Delta E$ roughly constant when $m$ varies) should not be surprising, since the number of candidate values for $(\ell, k)$ is equal to $N = nm$ (hence it remains constant), and Table 1 shows that for QQM, $\Delta E$ is approximately proportional to $(mn)^{-1} = N^{-1}$.

For conditionally-valid algorithms, Figure 6 shows a similar behavior for $\Delta q_\beta$ (decreasing function of $m$ for QQC-$n_j$ and QQC-$\langle N/m \rangle$, roughly constant for QQC), for which we propose the same intuitive explanation (see also Table 4 and Figure 23 in Appendix J.2.2). Note however that QQC-$n_j$ and QQC-$\langle N/m \rangle$ do not coincide with QQC and CentralC when $m=1$ because of the choice made for $\ell_j$ in Algorithm 6, which prevents to find a value of $k$ satisfying the training-conditional guarantee. Other choices would be possible (see Remark 21 in Section 5).

**Conclusion.** Our one-shot FL algorithms dealing with non-equal $n_j$ provide prediction sets only slightly more conservative than their centralized counterparts, while being computationally tractable, hence they seem effective for performing CP in one-shot FL with different $n_j$. Note that the values of $m$ for which QQM-$n_j$ and QQC-$n_j$ are the most conservative are the small values $m \ge 2$, which precisely are the ones for which QQM-$n_j$ and QQC-$n_j$ could be improved (while remaining tractable) by choosing among a few values of $\ell_j$ for every $j \in \llbracket m \rrbracket$ (see Remark 21).

## 6.2. Real data

In this section, we evaluate the performance of each algorithm (in terms of coverage and length of the returned prediction sets) on five public-domain regression data sets also considered in [54] and [56]: physicochemical properties of protein tertiary structure (bio) [51], bike sharing (bike) [16], communities and crimes (community) [52], Tennessee's student teacher achievement ratio (star) [1], and concrete compressive strength (concrete) [64].

### 6.2.1. Setup

For each experiment, we split the full data set into three parts: a learning set (40%), a calibration set (40%), and a test set (20%). To simulate a FL scenario, we also split the calibration set in $m$ disjoint subsets of equal size $n$. We consider scenarios where either $m > n$ or $m < n$, with $\max\{m/n, n/m\} \in \{4, 8\}$ depending on the data set; the exact values of $(m, n)$ for each data set are given in Appendix J.3. All features are then standardized to have zero mean and unit variance. For each algorithm, we compute the empirical coverage obtained on the test set and the average length of the prediction set over the test set. These two metrics are collected over 50 different learning-calibration-test random splits.

Prediction sets are constructed using the Conformalized Quantile Regression method (CQR) [54], a popular variant of split CP directly compatible with our approach, following Remark 2 in Section 2.2. In CQR, $\hat{f}$ is $(\hat{f}_{\alpha/2}, \hat{f}_{1-\alpha/2})$ where $\hat{f}_{\delta}$ is a quantile regressor of order $\delta$ [30] and $s(x, y) = \max(\hat{f}_{\alpha/2}(x) - y, y - \hat{f}_{1-\alpha/2}(x))$, so that the prediction set $\{y \in \mathbb{R} : s(x, y) \le \hat{q}\} = [\hat{f}_{\alpha/2}(x)-\hat{q}, \hat{f}_{1-\alpha/2}(x)+\hat{q}]$ has a size adaptive to heteroscedasticity. In the following experiments $\hat{f}_{\alpha/2}$ and $\hat{f}_{1-\alpha/2}$ are quantile regression forests [44] built from the learning set only. The number of trees in the forest is set to 1000, the two parameters controlling the coverage rate on the learning data are tuned using cross-validation (within the learning set), and the remaining hyperparameters are set as done in [54].
<figure><img src="image_9.png" /><figcaption>FIG 7. Empirical coverages of prediction intervals ($\alpha = 0.1$) constructed by various methods, aggregated across all data sets. Our methods are shown in bold font. See the beginning of Section 6.2.2 for details. Left: $m > n$. Right: $m < n$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIG 8. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits of the bike data set. The miscoverage is $\alpha = 0.1$, $\beta = 0.2$, and the calibration set is split into $m = 40$ disjoint subsets of equal size $n = 10$. See the beginning of Section 6.2.2 for details.</figcaption></figure>

## 6.2.2. Results

Figure 7 displays the boxes of the empirical coverages obtained by each method over all the data sets and all the 50 different data splits (one point represents the empirical coverage obtained on one random split of one data set). Figures 8 and 9 show the empirical coverages as well as the lengths of the intervals obtained on the bike data set. All the results on other individual data sets are provided in Appendix J.3. For each box, the white circle indicates the mean, the left-end of the box corresponds to the empirical quantile of order $\beta = 0.2$ and the right-end to the empirical quantile of order $1 - \beta = 0.8$.

**Marginally-valid algorithms.** First, on average, CentralM, QQM and QQM-Fast all return intervals with coverage greater than $1 - \alpha = 0.9$ (the nominal coverage), without being too far from it. Importantly, our two one-shot FL methods return prediction sets with coverage and length close to those returned by split CP (CentralM). So, there is only a small loss when using our one-shot FL algorithms (whose coverage/length are slightly larger in terms of both expectation and dispersion). It is interesting to note that the results obtained with our two FL methods are quite similar, with slightly better results for QQM notably when $m > n$ (left panel of Figure 7). As QQM-Fast is much faster, it is a good alternative to QQM and can be preferred in real applications. Note finally that for marginal algorithms, the results for $m > n$ and $m < n$ are comparable.
<figure><img src="image_9.png" /><figcaption>FIG 7. Empirical coverages of prediction intervals ($\alpha = 0.1$) constructed by various methods, aggregated across all data sets. Our methods are shown in bold font. See the beginning of Section 6.2.2 for details. Left: $m > n$. Right: $m < n$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIG 8. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits of the bike data set. The miscoverage is $\alpha = 0.1$, $\beta = 0.2$, and the calibration set is split into $m = 40$ disjoint subsets of equal size $n = 10$. See the beginning of Section 6.2.2 for details.</figcaption></figure>

## 6.2.2. Results

Figure 7 displays the boxes of the empirical coverages obtained by each method over all the data sets and all the 50 different data splits (one point represents the empirical coverage obtained on one random split of one data set). Figures 8 and 9 show the empirical coverages as well as the lengths of the intervals obtained on the bike data set. All the results on other individual data sets are provided in Appendix J.3. For each box, the white circle indicates the mean, the left-end of the box corresponds to the empirical quantile of order $\beta = 0.2$ and the right-end to the empirical quantile of order $1 - \beta = 0.8$.

**Marginally-valid algorithms.** First, on average, CentralM, QQM and QQM-Fast all return intervals with coverage greater than $1 - \alpha = 0.9$ (the nominal coverage), without being too far from it. Importantly, our two one-shot FL methods return prediction sets with coverage and length close to those returned by split CP (CentralM). So, there is only a small loss when using our one-shot FL algorithms (whose coverage/length are slightly larger in terms of both expectation and dispersion). It is interesting to note that the results obtained with our two FL methods are quite similar, with slightly better results for QQM notably when $m > n$ (left panel of Figure 7). As QQM-Fast is much faster, it is a good alternative to QQM and can be preferred in real applications. Note finally that for marginal algorithms, the results for $m > n$ and $m < n$ are comparable.
<figure><img src="image_11.png" /><figcaption>FIG 9. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits of the bike data set. The miscoverage is $\alpha = 0.1$, $\beta = 0.2$, and the calibration set is split into $m = 10$ disjoint subsets of equal size $n = 40$. See the beginning of Section 6.2.2 for details.</figcaption></figure>

**Conditionally-valid algorithms.** The comparison between the three training conditionally valid algorithms on Figures 7–9 is similar to the comparison made above between the three marginally-valid algorithms. The main difference is the loss of using our fast one-shot FL algorithm QQC-Fast instead of QQC is larger than for our marginally-valid one-shot FL algorithms. Therefore, our advice here is to use QQC as long as it is computationally tractable, that is, when the total number *mn* of calibration data points is not huge —since its complexity might be proportional to *mn*.

Note that on Figures 7–9, the empirical $\beta$-quantile of the coverage of some training-conditionally-valid algorithms is slightly smaller than $1 - \alpha$. This apparent contradiction with the theoretical guarantees about these algorithms is due to the fact that the coverages reported in these experiments are only estimations obtained from finite test sets (200 points for the bike dataset, for instance).

Finally, as in Section 6.1, we can notice that the (empirical) marginal coverages of training-conditional algorithms are higher than those of the marginal algorithms.

**FedCP-Avg.** First, in our experiments, FedCP-Avg appears to be marginally valid for each data set, and training-conditionally valid at a confidence level $\beta$ for all data sets except bike, community and star (each time when $m < n$). So, even without general theoretical guarantees (and even some counterexamples, see Appendix I.2), it here turns out to be valid in most cases (but not all, which is an issue). Second, FedCP-Avg is much more conservative than all competing algorithms in most data sets, and the few cases where it is less conservative than training-conditional algorithms precisely are the cases where FedCP-Avg is not training-conditionally valid. Therefore, FedCP-Avg appears to be clearly worse than our one-shot FL algorithms in all our experiments, a fact which is also supported by the few theoretical results presented in Appendix I.2.

**Conclusion.** Overall, these experiments support the fact that our one-shot FL methods are well-suited for building prediction sets in a federated setting, with only a mild loss compared to the centralized case.
<figure><img src="image_11.png" /><figcaption>FIG 9. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits of the bike data set. The miscoverage is $\alpha = 0.1$, $\beta = 0.2$, and the calibration set is split into $m = 10$ disjoint subsets of equal size $n = 40$. See the beginning of Section 6.2.2 for details.</figcaption></figure>

**Conditionally-valid algorithms.** The comparison between the three training conditionally valid algorithms on Figures 7–9 is similar to the comparison made above between the three marginally-valid algorithms. The main difference is the loss of using our fast one-shot FL algorithm QQC-Fast instead of QQC is larger than for our marginally-valid one-shot FL algorithms. Therefore, our advice here is to use QQC as long as it is computationally tractable, that is, when the total number *mn* of calibration data points is not huge —since its complexity might be proportional to *mn*.

Note that on Figures 7–9, the empirical $\beta$-quantile of the coverage of some training-conditionally-valid algorithms is slightly smaller than $1 - \alpha$. This apparent contradiction with the theoretical guarantees about these algorithms is due to the fact that the coverages reported in these experiments are only estimations obtained from finite test sets (200 points for the bike dataset, for instance).

Finally, as in Section 6.1, we can notice that the (empirical) marginal coverages of training-conditional algorithms are higher than those of the marginal algorithms.

**FedCP-Avg.** First, in our experiments, FedCP-Avg appears to be marginally valid for each data set, and training-conditionally valid at a confidence level $\beta$ for all data sets except bike, community and star (each time when $m < n$). So, even without general theoretical guarantees (and even some counterexamples, see Appendix I.2), it here turns out to be valid in most cases (but not all, which is an issue). Second, FedCP-Avg is much more conservative than all competing algorithms in most data sets, and the few cases where it is less conservative than training-conditional algorithms precisely are the cases where FedCP-Avg is not training-conditionally valid. Therefore, FedCP-Avg appears to be clearly worse than our one-shot FL algorithms in all our experiments, a fact which is also supported by the few theoretical results presented in Appendix I.2.

**Conclusion.** Overall, these experiments support the fact that our one-shot FL methods are well-suited for building prediction sets in a federated setting, with only a mild loss compared to the centralized case.
## 7. Discussion

All prediction sets proposed in this paper are of the form $\hat{C}_{\bar{l}, \bar{k}}$ —as defined by Eq. (9)— with

$$ (\bar{l}, \bar{k}) \in \underset{(\ell, k) \in \mathcal{E}}{\operatorname{argmin}} \{\operatorname{crit}(\ell, k)\}, $$

where $\mathcal{E} \subset [n] \times [m]$ is a set of marginally (resp. training-conditionally) valid pairs, and $\operatorname{crit}(\ell, k)$ is an upper bound on the expectation (resp. some quantile) of the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$ when the scores cdf is continuous. Note that we adopt here Assumption 1 to maintain notation simplicity, but the comments made in this paragraph also apply to Algorithms 5–6 in Section 5. The selection criteria ($\operatorname{crit}$) used in Algorithms 1–6 come from arguments presented in Section 2.3 (and Appendix A), and they are validated by the theoretical and numerical results obtained in Sections 4 and 6. Yet, other choices are possible, leading to numerous variants of our algorithms. For instance, one could modify Algorithms 3–4 by taking

$$ \operatorname{crit}(\ell, k) = F_{U_{(\ell,n,k:m)}}^{-1}(1 - \beta') $$

with any $\beta' \in (0, 1)$ —instead of fixing $\beta' = \beta$—, leading to the algorithms respectively defined by Eq. (57) and (58) in Appendix E.2. Remarkably, theoretical coverage upper bounds similar to Theorem 17 can also be obtained for these variants, as proved by Eq. (59) and (60) in Appendix E.2. One could also use this criterion for selecting among marginally-valid pairs $(\ell, k)$, or use $\operatorname{crit}(\ell, k) = M_{\ell,k}$ for selecting among training-conditionally-valid pairs $(\ell, k)$. The function $\operatorname{crit}$ can also be chosen by the user —for instance, with a specific application in mind—, together with a set $\mathcal{E}$ chosen among those used by our Algorithms 1–6, and the resulting prediction set would satisfy the corresponding distribution-free coverage lower bounds proved in this paper.

This work brings many possible future research directions. It would be interesting to investigate how our quantile-of-quantiles estimators can be adapted to the heterogeneous case, that is, when agents have data following different distributions. This could potentially extend the approaches of [39] and [50] to the one-shot setting. Another interesting line of research would be to propose and study differentially private versions of our algorithms. On a more theoretical aspect, it would be interesting to control the deviations of the coverage of marginal prediction sets built in Section 3.1, and conversely to control the expected coverage of the training-conditional prediction sets of Section 3.2. Finally, our paper focuses on the calibration step, making it particularly suited for split-based conformal methods. It would be interesting to study how our FL approach could be extended to full conformal prediction, and to the more general framework of nested conformal prediction [21].

## References

[1] ACHILLES, C. M., BAIN, H. P., BELLOTT, F., BOYD-ZAHARIAS, J., FINN, J., FOLGER, J., JOHNSTON, J. and WORD, E. (2008). Tennessee's student teacher achievement ratio (STAR) project. *Harvard Dataverse* 1 2008.

[2] AL-HUSSAINI, E. K. (2012). Composition of cumulative distribution functions. *Journal of Statistical Theory and Applications* ISSN 1538 7887.

[3] ANDREW, G., THAKKAR, O., MCMAHAN, B. and RAMASWAMY, S. (2021). Differentially private learning with adaptive clipping. *Advances in Neural Information Processing Systems* 34 17455–17466.
## 7. Discussion

All prediction sets proposed in this paper are of the form $\hat{C}_{\bar{l}, \bar{k}}$ —as defined by Eq. (9)— with

$$ (\bar{l}, \bar{k}) \in \underset{(\ell, k) \in \mathcal{E}}{\operatorname{argmin}} \{\operatorname{crit}(\ell, k)\}, $$

where $\mathcal{E} \subset [n] \times [m]$ is a set of marginally (resp. training-conditionally) valid pairs, and $\operatorname{crit}(\ell, k)$ is an upper bound on the expectation (resp. some quantile) of the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$ when the scores cdf is continuous. Note that we adopt here Assumption 1 to maintain notation simplicity, but the comments made in this paragraph also apply to Algorithms 5–6 in Section 5. The selection criteria ($\operatorname{crit}$) used in Algorithms 1–6 come from arguments presented in Section 2.3 (and Appendix A), and they are validated by the theoretical and numerical results obtained in Sections 4 and 6. Yet, other choices are possible, leading to numerous variants of our algorithms. For instance, one could modify Algorithms 3–4 by taking

$$ \operatorname{crit}(\ell, k) = F_{U_{(\ell,n,k:m)}}^{-1}(1 - \beta') $$

with any $\beta' \in (0,1)$ —instead of fixing $\beta' = \beta$—, leading to the algorithms respectively defined by Eq. (57) and (58) in Appendix E.2. Remarkably, theoretical coverage upper bounds similar to Theorem 17 can also be obtained for these variants, as proved by Eq. (59) and (60) in Appendix E.2. One could also use this criterion for selecting among marginally-valid pairs $(\ell, k)$, or use $\operatorname{crit}(\ell, k) = M_{\ell,k}$ for selecting among training-conditionally-valid pairs $(\ell, k)$. The function $\operatorname{crit}$ can also be chosen by the user —for instance, with a specific application in mind—, together with a set $\mathcal{E}$ chosen among those used by our Algorithms 1–6, and the resulting prediction set would satisfy the corresponding distribution-free coverage lower bounds proved in this paper.

This work brings many possible future research directions. It would be interesting to investigate how our quantile-of-quantiles estimators can be adapted to the heterogeneous case, that is, when agents have data following different distributions. This could potentially extend the approaches of [39] and [50] to the one-shot setting. Another interesting line of research would be to propose and study differentially private versions of our algorithms. On a more theoretical aspect, it would be interesting to control the deviations of the coverage of marginal prediction sets built in Section 3.1, and conversely to control the expected coverage of the training-conditional prediction sets of Section 3.2. Finally, our paper focuses on the calibration step, making it particularly suited for split-based conformal methods. It would be interesting to study how our FL approach could be extended to full conformal prediction, and to the more general framework of nested conformal prediction [21].

## References

[1] ACHILLES, C. M., BAIN, H. P., BELLOTT, F., BOYD-ZAHARIAS, J., FINN, J., FOLGER, J., JOHNSTON, J. and WORD, E. (2008). Tennessee's student teacher achievement ratio (STAR) project. *Harvard Dataverse* 1 2008.

[2] AL-HUSSAINI, E. K. (2012). Composition of cumulative distribution functions. *Journal of Statistical Theory and Applications* ISSN 1538 7887.

[3] ANDREW, G., THAKKAR, O., MCMAHAN, B. and RAMASWAMY, S. (2021). Differentially private learning with adaptive clipping. *Advances in Neural Information Processing Systems* 34 17455–17466.
[4] ANGELOPOULOS, A. N. and BATES, S. (2023). Conformal prediction: A gentle introduction. *Foundations and Trends in Machine Learning* **16** 494–591.

[5] BAGNOLI, M. and BERGSTROM, T. (2005). Log-concave probability and its applications. *Econom. Theory* **26** 445–469.

[6] BAGNOLI, M. and BERGSTROM, T. C. (1989). Log-concave probability and its applications.

[7] BALAKRISHNAN, N. (2007). Permanents, order statistics, outliers, and robustness. *Revista matemática complutense* **20** 7–107.

[8] BIAN, M. and BARBER, R. F. (2023). Training-conditional coverage for distribution-free predictive inference. *Electronic Journal of Statistics* **17** 2044–2066.

[9] CASTELLARES, F., LEMONTE, A. J. and SANTOS, M. A. (2021). A note on explicit expressions for moments of order statistics. *Spanish journal of statistics* **3** 45–53.

[10] CONNOR, S. B. and FEWSTER, C. J. (2022). Integrals of incomplete beta functions, with applications to order statistics, random walks and string enumeration. *Brazilian Journal of Probability and Statistics* **36** 185–198.

[11] CORDEIRO, G. M. (2013). A simple formula based on quantiles for the moments of beta generalized distributions. *Journal of Statistical Computation and Simulation* **83** 1932–1943.

[12] CORMODE, G. and MARKOV, I. L. (2023). Federated Calibration and Evaluation of Binary Classifiers. *Proceedings of the VLDB Endowment* **16** 3253–3265.

[13] DAVID, H. A. and NAGARAJA, H. N. (2004). *Order statistics*. John Wiley & Sons.

[14] DENNIS, D. K., LI, T. and SMITH, V. (2021). Heterogeneity for the Win: One-Shot Federated Clustering. In *ICML*.

[15] EL MEKKAOUI, K., MESQUITA, D., BLOMSTEDT, P. and KASKI, S. (2021). Federated stochastic gradient Langevin dynamics. In *Uncertainty in Artificial Intelligence* 1703–1712. PMLR.

[16] FANAEE-T, H. and GAMA, J. (2013). Event labeling combining ensemble detectors and background knowledge. *Progress in Artificial Intelligence* 1–15.

[17] FONTANA, M., ZENI, G. and VANTINI, S. (2023). Conformal prediction: a unified review of theory and new challenges. *Bernoulli* **29** 1–23.

[18] GHOSH, J. K. (1971). A new proof of the Bahadur representation of quantiles and an application. *Ann. Math. Statist.* **42** 1957–1961.

[19] GUAN, L. (2023). Localized conformal prediction: A generalized inference framework for conformal prediction. *Biometrika* **110** 33–50.

[20] GUHA, N., TALWALKAR, A. and SMITH, V. (2019). One-shot federated learning. *arXiv preprint arXiv:1902.1175*.

[21] GUPTA, C., KUCHIBHOTLA, A. K. and RAMDAS, A. (2022). Nested conformal prediction and quantile out-of-bag ensemble methods. *Pattern Recognition* **127** 108496.

[22] HAN, X., TANG, Z., GHOSH, J. and LIU, Q. (2022). Split localized conformal prediction. *arXiv preprint arXiv:2206.13092*.

[23] HONG, Y. (2013). On computing the distribution function for the Poisson binomial distribution. *Computational Statistics & Data Analysis* **59** 41–51.

[24] HUBER, P. J. (1992). Robust estimation of a location parameter. In *Breakthroughs in statistics: Methodology and distribution* 492–518. Springer.

[25] HUMBERT, P., LE BARS, B., BELLET, A. and ARLOT, S. (2023). One-Shot Federated Conformal Prediction. In *International Conference on Machine Learning* 14153–14177. PMLR.

[26] JONES, M. C. (2004). Families of distributions arising from distributions of order statistics. *Test* **13** 1–43.

[27] KAIROUZ, P., MCMAHAN, H. B., AVENT, B., BELLET, A., BENNIS, M., BHAGOJI, A. N., BONAWITZ, K., CHARLES, Z., CORMODE, G., CUMMINGS, R.