[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.
et al. (2021). Advances and open problems in federated learning. *Foundations and Trends® in Machine Learning* **14** 1–210.

[28] KARIMIREDDY, S. P., KALE, S., MOHRI, M., REDDI, S. J., STICH, S. U. and SURESH, A. T. (2020). SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning. In *ICML*.

[29] KIVARANOVIC, D., JOHNSON, K. D. and LEEB, H. (2020). Adaptive, distribution-free prediction intervals for deep networks. In *International Conference on Artificial Intelligence and Statistics* 4346–4356. PMLR.

[30] KOENKER, R. and BASSETT JR, G. (1978). Regression quantiles. *Econometrica*: journal of the Econometric Society 33–50.

[31] KOTELEVSKII, N., VONO, M., DURMUS, A. and MOULINES, E. (2022). Fedpop: A bayesian approach for personalised federated learning. *Advances in Neural Information Processing Systems* **35** 8687–8701.

[32] KRISHNAMOORTHY, K. and MATHEW, T. (2009). *Statistical tolerance regions: theory, applications, and computation*. John Wiley & Sons.

[33] LAHIRI, S. N. (1992). On the Bahadur-Ghosh-Kiefer representation of sample quantiles. *Statist. Probab. Lett.* **15** 163–168.

[34] LEBRUN, R. (2013). Efficient time/space algorithm to compute rectangular probabilities of multinomial, multivariate hypergeometric and multivariate Pólya distributions. *Statistics and Computing* **23** 615–623.

[35] LEI, J., G'SELL, M., RINALDO, A., TIBSHIRANI, R. J. and WASSERMAN, L. (2018). Distribution-free predictive inference for regression. *Journal of the American Statistical Association* **113** 1094–1111.

[36] LI, Q., HE, B. and SONG, D. (2021). Practical One-Shot Federated Learning for Cross-Silo Setting. In *IJCAI*.

[37] LI, T., SAHU, A. K., ZAHEER, M., SANJABI, M., TALWALKAR, A. and SMITH, V. (2020). Federated optimization in heterogeneous networks. *Proceedings of Machine Learning and Systems* **2** 429–450.

[38] LU, C. and KALPATHY-CRAMER, J. (2021). Distribution-free federated learning with conformal predictions. *arXiv preprint arXiv:2110.07661*.

[39] LU, C., YU, Y., KARIMIREDDY, S. P., JORDAN, M. and RASKAR, R. (2023). Federated Conformal Predictors for Distributed Uncertainty Quantification. In *International Conference on Machine Learning* 22942–22964. PMLR.

[40] MAKGAI, S. L. et al. (2019). From Beta to Dirichlet Frontiers, PhD thesis, University of Pretoria.

[41] MANOKHIN, V. (2022). Awesome Conformal Prediction.

[42] MARCHAL, O. and ARBEL, J. (2017). On the sub-Gaussianity of the Beta and Dirichlet distributions.

[43] McMAHAN, B., MOORE, E., RAMAGE, D., HAMPSON, S. and Y ARCAS, B. A. (2017). Communication-efficient learning of deep networks from decentralized data. In *Artificial intelligence and statistics* 1273–1282. PMLR.

[44] MEINSHAUSEN, N. and RIDGEWAY, G. (2006). Quantile regression forests. *Journal of machine learning research* **7**.

[45] NDIAYE, E. (2022). Stable conformal prediction sets. In *International Conference on Machine Learning* 16462–16479. PMLR.

[46] PAPADOPOULOS, H., PROEDROU, K., VOVK, V. and GAMMERMAN, A. (2002). Inductive confidence machines for regression. In *European Conference on Machine Learning* 345–356. Springer.

[47] PARK, S., BASTANI, O., MATNI, N. and LEE, I. (2019). PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction. In *International Conference on Learning Representations*.
et al. (2021). Advances and open problems in federated learning. *Foundations and Trends® in Machine Learning* **14** 1–210.

[28] KARIMIREDDY, S. P., KALE, S., MOHRI, M., REDDI, S. J., STICH, S. U. and SURESH, A. T. (2020). SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning. In *ICML*.

[29] KIVARANOVIC, D., JOHNSON, K. D. and LEEB, H. (2020). Adaptive, distribution-free prediction intervals for deep networks. In *International Conference on Artificial Intelligence and Statistics* 4346–4356. PMLR.

[30] KOENKER, R. and BASSETT JR, G. (1978). Regression quantiles. *Econometrica*: journal of the Econometric Society 33–50.

[31] KOTELEVSKII, N., VONO, M., DURMUS, A. and MOULINES, E. (2022). Fedpop: A bayesian approach for personalised federated learning. *Advances in Neural Information Processing Systems* **35** 8687–8701.

[32] KRISHNAMOORTHY, K. and MATHEW, T. (2009). *Statistical tolerance regions: theory, applications, and computation*. John Wiley & Sons.

[33] LAHIRI, S. N. (1992). On the Bahadur-Ghosh-Kiefer representation of sample quantiles. *Statist. Probab. Lett.* **15** 163–168.

[34] LEBRUN, R. (2013). Efficient time/space algorithm to compute rectangular probabilities of multinomial, multivariate hypergeometric and multivariate Pólya distributions. *Statistics and Computing* **23** 615–623.

[35] LEI, J., G'SELL, M., RINALDO, A., TIBSHIRANI, R. J. and WASSERMAN, L. (2018). Distribution-free predictive inference for regression. *Journal of the American Statistical Association* **113** 1094–1111.

[36] LI, Q., HE, B. and SONG, D. (2021). Practical One-Shot Federated Learning for Cross-Silo Setting. In *IJCAI*.

[37] LI, T., SAHU, A. K., ZAHEER, M., SANJABI, M., TALWALKAR, A. and SMITH, V. (2020). Federated optimization in heterogeneous networks. *Proceedings of Machine Learning and Systems* **2** 429–450.

[38] LU, C. and KALPATHY-CRAMER, J. (2021). Distribution-free federated learning with conformal predictions. *arXiv preprint arXiv:2110.07661*.

[39] LU, C., YU, Y., KARIMIREDDY, S. P., JORDAN, M. and RASKAR, R. (2023). Federated Conformal Predictors for Distributed Uncertainty Quantification. In *International Conference on Machine Learning* 22942–22964. PMLR.

[40] MAKGAI, S. L. et al. (2019). From Beta to Dirichlet Frontiers, PhD thesis, University of Pretoria.

[41] MANOKHIN, V. (2022). Awesome Conformal Prediction.

[42] MARCHAL, O. and ARBEL, J. (2017). On the sub-Gaussianity of the Beta and Dirichlet distributions.

[43] McMAHAN, B., MOORE, E., RAMAGE, D., HAMPSON, S. and Y ARCAS, B. A. (2017). Communication-efficient learning of deep networks from decentralized data. In *Artificial intelligence and statistics* 1273–1282. PMLR.

[44] MEINSHAUSEN, N. and RIDGEWAY, G. (2006). Quantile regression forests. *Journal of machine learning research* **7**.

[45] NDIAYE, E. (2022). Stable conformal prediction sets. In *International Conference on Machine Learning* 16462–16479. PMLR.

[46] PAPADOPOULOS, H., PROEDROU, K., VOVK, V. and GAMMERMAN, A. (2002). Inductive confidence machines for regression. In *European Conference on Machine Learning* 345–356. Springer.

[47] PARK, S., BASTANI, O., MATNI, N. and LEE, I. (2019). PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction. In *International Conference on Learning Representations*.
[48] PARK, S., DOBRIBAN, E., LEE, I. and BASTANI, O. (2021). PAC Prediction Sets Under Covariate Shift. In *International Conference on Learning Representations*.

[49] PILLUTLA, K., LAGUEL, Y., MALICK, J. and HARCHAOUI, Z. (2022). Differentially Private Federated Quantiles with the Distributed Discrete Gaussian Mechanism. In *International Workshop on Federated Learning: Recent Advances and New Challenges*.

[50] PLASSIER, V., MAKNI, M., RUBASHEVSKII, A., MOULINES, E. and PANOV, M. (2023). Conformal Prediction for Federated Uncertainty Quantification Under Label Shift. In *Proceedings of the 40th International Conference on Machine Learning* (A. KRAUSE, E. BRUNSKILL, K. CHO, B. ENGELHARDT, S. SABATO and J. SCARLETT, eds.). *Proceedings of Machine Learning Research* **202** 27907–27947. PMLR.

[51] RANA, P. (2013). Physicochemical properties of protein tertiary structure data set. *UCI Machine Learning Repository*.

[52] REDMOND, M. (2011). Communities and crime unnormalized data set. *UCI Machine Learning Repository*.

[53] RÉNYI, A. (1953). On the theory of order statistics. *Acta Math. Acad. Sci. Hung* **4** 48–89.

[54] ROMANO, Y., PATTERSON, E. and CANDES, E. (2019). Conformalized quantile regression. *Advances in neural information processing systems* **32**.

[55] SALEHKALEYBAR, S., SHARIF-NASSAB, A. and GOLESTANI, S. J. (2021). One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them. *Journal of Machine Learning Research* **22** 1–47.

[56] SESIA, M. and ROMANO, Y. (2021). Conformal prediction using conditional histograms. *Advances in Neural Information Processing Systems* **34** 6304–6315.

[57] SKORSKI, M. (2023). Bernstein-type bounds for beta distribution. *Modern Stochastics: Theory and Applications* **10** 211–228.

[58] TANG, W. and TANG, F. (2023). The Poisson binomial distribution—Old & new. *Statistical Science* **38** 108–119.

[59] TEMME, N. M. (1996). *Special functions: An introduction to the classical functions of mathematical physics*. John Wiley & Sons.

[60] VIRTANEN, P., GOMMERS, R., OLIPHANT, T. E., HABERLAND, M., REDDY, T., COURNAPEAU, D., BUROVSKI, E., PETERSON, P., WECKESSER, W., BRIGHT, J., VAN DER WALT, S. J., BRETT, M., WILSON, J., MILLMAN, K. J., MAYOROV, N., NELSON, A. R. J., JONES, E., KERN, R., LARSON, E., CAREY, C. J., POLAT, I., FENG, Y., MOORE, E. W., VANDERPLAS, J., LAXALDE, D., PERKTOLD, J., CIMRMAN, R., HENRIKSEN, I., QUINTERO, E. A., HARRIS, C. R., ARCHIBALD, A. M., RIBEIRO, A. H., PEDREGOSA, F., VAN MULBREGT, P. and SciPy 1.0 CONTRIBUTORS (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. *Nature Methods* **17** 261–272.

[61] VOVK, V. (2012). Conditional validity of inductive conformal predictors. In *Asian conference on machine learning* 475–490. PMLR.

[62] VOVK, V., GAMMERMAN, A. and SHAFER, G. (2005). *Algorithmic learning in a random world*. Springer Science & Business Media.

[63] WILKS, S. S. (1941). Determination of sample sizes for setting tolerance limits. *The Annals of Mathematical Statistics* **12** 91–96.

[64] YEH, I.-C. (1998). Modeling of strength of high-performance concrete using artificial neural networks. *Cement and Concrete research* **28** 1797–1808.

[65] YUROCHKIN, M., AGARWAL, M., GHOSH, S., GREENEWALD, K., HOANG, T. N. and KHAZAENI, Y. (2019). Bayesian Nonparametric Federated Learning of Neural Networks. In *ICML*.

[66] ZHANG, Y., WAINWRIGHT, M. J. and DUCHI, J. C. (2012). Communication-efficient
[48] PARK, S., DOBRIBAN, E., LEE, I. and BASTANI, O. (2021). PAC Prediction Sets Under Covariate Shift. In *International Conference on Learning Representations*.

[49] PILLUTLA, K., LAGUEL, Y., MALICK, J. and HARCHAOUI, Z. (2022). Differentially Private Federated Quantiles with the Distributed Discrete Gaussian Mechanism. In *International Workshop on Federated Learning: Recent Advances and New Challenges*.

[50] PLASSIER, V., MAKNI, M., RUBASHEVSKII, A., MOULINES, E. and PANOV, M. (2023). Conformal Prediction for Federated Uncertainty Quantification Under Label Shift. In *Proceedings of the 40th International Conference on Machine Learning* (A. KRAUSE, E. BRUNSKILL, K. CHO, B. ENGELHARDT, S. SABATO and J. SCARLETT, eds.). *Proceedings of Machine Learning Research* **202** 27907-27947. PMLR.

[51] RANA, P. (2013). Physicochemical properties of protein tertiary structure data set. *UCI Machine Learning Repository*.

[52] REDMOND, M. (2011). Communities and crime unnormalized data set. *UCI Machine Learning Repository*.

[53] RÉNYI, A. (1953). On the theory of order statistics. *Acta Math. Acad. Sci. Hung* **4** 48-89.

[54] ROMANO, Y., PATTERSON, E. and CANDES, E. (2019). Conformalized quantile regression. *Advances in neural information processing systems* **32**.

[55] SALEHKALEYBAR, S., SHARIF-NASSAB, A. and GOLESTANI, S. J. (2021). One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them. *Journal of Machine Learning Research* **22** 1-47.

[56] SESIA, M. and ROMANO, Y. (2021). Conformal prediction using conditional histograms. *Advances in Neural Information Processing Systems* **34** 6304-6315.

[57] SKORSKI, M. (2023). Bernstein-type bounds for beta distribution. *Modern Stochastics: Theory and Applications* **10** 211-228.

[58] TANG, W. and TANG, F. (2023). The Poisson binomial distribution—Old & new. *Statistical Science* **38** 108-119.

[59] TEMME, N. M. (1996). *Special functions: An introduction to the classical functions of mathematical physics*. John Wiley & Sons.

[60] VIRTANEN, P., GOMMERS, R., OLIPHANT, T. E., HABERLAND, M., REDDY, T., COURNAPEAU, D., BUROVSKI, E., PETERSON, P., WECKESSER, W., BRIGHT, J., VAN DER WALT, S. J., BRETT, M., WILSON, J., MILLMAN, K. J., MAYOROV, N., NELSON, A. R. J., JONES, E., KERN, R., LARSON, E., CAREY, C. J., POLAT, I., FENG, Y., MOORE, E. W., VANDERPLAS, J., LAXALDE, D., PERKTOLD, J., CIMRMAN, R., HENRIKSEN, I., QUINTERO, E. A., HARRIS, C. R., ARCHIBALD, A. M., RIBEIRO, A. H., PEDREGOSA, F., VAN MULBREGT, P. and SciPy 1.0 CONTRIBUTORS (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. *Nature Methods* **17** 261-272.

[61] VOVK, V. (2012). Conditional validity of inductive conformal predictors. In *Asian conference on machine learning* 475-490. PMLR.

[62] VOVK, V., GAMMERMAN, A. and SHAFER, G. (2005). *Algorithmic learning in a random world*. Springer Science & Business Media.

[63] WILKS, S. S. (1941). Determination of sample sizes for setting tolerance limits. *The Annals of Mathematical Statistics* **12** 91-96.

[64] YEH, I.-C. (1998). Modeling of strength of high-performance concrete using artificial neural networks. *Cement and Concrete research* **28** 1797-1808.

[65] YUROCHKIN, M., AGARWAL, M., GHOSH, S., GREENEWALD, K., HOANG, T. N. and KHAZAENI, Y. (2019). Bayesian Nonparametric Federated Learning of Neural Networks. In *ICML*.

[66] ZHANG, Y., WAINWRIGHT, M. J. and DUCHI, J. C. (2012). Communication-efficient
algorithms for statistical optimization. *Advances in neural information processing systems* **25**.
algorithms for statistical optimization. *Advances in neural information processing systems* **25**.
## Appendix A: Prediction set performance measure: complements

Recall that we prove in Section 2.3 that for every $(\ell, k)$, the size of $\hat{C}_{\ell,k}(x)$ is a nondecreasing function of the coverage $1 - \alpha_{\ell,k}(D)$.

As a consequence, for any $\beta \in (0, 1)$, minimizing the $(1-\beta)$-quantile of the coverage $1 - \alpha_{\ell,k}(D)$ yields a minimizer of the $(1-\beta)$-quantile of the size of $\hat{C}_{\ell,k}(x)$, simultaneously for all $x \in \mathcal{X}$. We therefore use this strategy for building the two training-conditionally-valid algorithms described in Section 3.2.

The problem is a bit more difficult when one measures the performance of a predictor set by its size on average over $D$ (even at a single $x \in \mathcal{X}$). As an illustration, let us consider regression with the fitted absolute residual score function. Then,

$$ \forall x \in \mathcal{X}, \quad \hat{C}_{\ell,k}(x) = [\hat{f}(x) - S_{(\ell,k)}, \hat{f}(x) + S_{(\ell,k)}] $$

is a prediction interval of length

$$ 2S_{(\ell,k)} = 2F_S^{-1}(1 - \alpha_{\ell,k}(D)) $$

almost surely. In this example, the size of $\hat{C}_{\ell,k}(x)$ (its length) is a nondecreasing function of the coverage $1 - \alpha_{\ell,k}(D)$, but the relationship between size and coverage is highly non-linear in general, hence the expected size $\mathbb{E}[\hat{C}_{\ell,k}(x)]$ cannot easily be linked to the expected coverage $\mathbb{E}[1 - \alpha_{\ell,k}(D)]$. Nevertheless, following what is usually done for split CP (see Section 2.1), choosing $(\ell, k)$ by minimizing $\mathbb{E}[1 - \alpha_{\ell,k}(D)]$ —or at least its value when $F_S$ is continuous, see Sections 3.1 and 2.1— is a natural choice, which is efficient according to numerical experiments.

The latter argument might seem questionable, especially when $F_S$ is not guaranteed to be continuous. Yet, the strategy we propose is reasonable for the following reasons. $S_{(\ell,k)}$ is a nondecreasing function of $(\ell, k)$ (for the lexicographic order on $\llbracket n \rrbracket \times \llbracket m \rrbracket$), hence both the expected size and the expected coverage are nondecreasing functions of $(\ell, k)$. Therefore, minimizing the value $M_{\ell,k}$ of the expected coverage $\mathbb{E}[1 - \alpha_{\ell,k}(D)]$ when $F_S$ is continuous (see Section 3.1) over the set of (marginally or conditionally) valid pairs $(\ell, k)$ yields some $(\ell, k)$ minimal for the lexicographic order in the set of valid pairs. So, even if this does not choose the optimal valid pair $(\ell, k)$, it yields a performance close to its optimal value —at least numerically. We therefore follow this strategy when building marginally-valid algorithms in Section 3.1.

## Appendix B: Key preliminary results on order statistics

In this section, we provide some known and new important results about order statistics that play a key role in our proofs. We refer to Appendix G for proofs and additional results, and to [13] for an in-depth presentation on this topic.

### B.1. Order statistics

Let us first introduce some notation. Given a real-valued random variable $Z$ with arbitrary cumulative distribution function (cdf) $F_Z$, its quantile function is defined as the generalized inverse of $F_Z$:

$$ \forall p \in (0, 1), \quad F_Z^{-1}(p) := \inf\{x \in \mathbb{R} : F_Z(x) \ge p\}. \quad (35) $$

A key property of the generalized inverse —straightforward from Eq. (35)— is that

$$ \forall p \in [0, 1], \quad F_Z \circ F_Z^{-1}(p) \ge p \quad \text{with equality if} \quad p \in \text{Im}(F_Z). \quad (36) $$
## Appendix A: Prediction set performance measure: complements

Recall that we prove in Section 2.3 that for every $(\ell, k)$, the size of $\hat{C}_{\ell,k}(x)$ is a nondecreasing function of the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$.

As a consequence, for any $\beta \in (0, 1)$, minimizing the $(1 - \beta)$-quantile of the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$ yields a minimizer of the $(1 - \beta)$-quantile of the size of $\hat{C}_{\ell,k}(x)$, simultaneously for all $x \in \mathcal{X}$. We therefore use this strategy for building the two training-conditionally-valid algorithms described in Section 3.2.

The problem is a bit more difficult when one measures the performance of a predictor set by its size on average over $\mathcal{D}$ (even at a single $x \in \mathcal{X}$). As an illustration, let us consider regression with the fitted absolute residual score function. Then,

$$ \forall x \in \mathcal{X}, \quad \hat{C}_{\ell,k}(x) = [\hat{f}(x) - S_{(\ell,k)}, \hat{f}(x) + S_{(\ell,k)}] $$

is a prediction interval of length

$$ 2S_{(\ell,k)} = 2F_S^{-1}(1 - \alpha_{\ell,k}(\mathcal{D})) $$

almost surely. In this example, the size of $\hat{C}_{\ell,k}(x)$ (its length) is a nondecreasing function of the coverage $1 - \alpha_{\ell,k}(\mathcal{D})$, but the relationship between size and coverage is highly non-linear in general, hence the expected size $\mathbb{E}[\hat{C}_{\ell,k}(x)]$ cannot easily be linked to the expected coverage $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})]$. Nevertheless, following what is usually done for split CP (see Section 2.1), choosing $(\ell, k)$ by minimizing $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})]$ —or at least its value when $F_S$ is continuous, see Sections 3.1 and 2.1— is a natural choice, which is efficient according to numerical experiments.

The latter argument might seem questionable, especially when $F_S$ is not guaranteed to be continuous. Yet, the strategy we propose is reasonable for the following reasons. $S_{(\ell,k)}$ is a nondecreasing function of $(\ell, k)$ (for the lexicographic order on $\llbracket n \rrbracket \times \llbracket m \rrbracket$), hence both the expected size and the expected coverage are nondecreasing functions of $(\ell, k)$. Therefore, minimizing the value $M_{\ell,k}$ of the expected coverage $\mathbb{E}[1 - \alpha_{\ell,k}(\mathcal{D})]$ when $F_S$ is continuous (see Section 3.1) over the set of (marginally or conditionally) valid pairs $(\ell, k)$ yields some $(\ell, k)$ minimal for the lexicographic order in the set of valid pairs. So, even if this does not choose the optimal valid pair $(\ell, k)$, it yields a performance close to its optimal value —at least numerically. We therefore follow this strategy when building marginally-valid algorithms in Section 3.1.

## Appendix B: Key preliminary results on order statistics

In this section, we provide some known and new important results about order statistics that play a key role in our proofs. We refer to Appendix G for proofs and additional results, and to [13] for an in-depth presentation on this topic.

### B.1. Order statistics

Let us first introduce some notation. Given a real-valued random variable $Z$ with arbitrary cumulative distribution function (cdf) $F_Z$, its quantile function is defined as the generalized inverse of $F_Z$:

$$ \forall p \in (0, 1), \quad F_Z^{-1}(p) := \inf\{x \in \mathbb{R} : F_Z(x) \ge p\}. \quad (35) $$

A key property of the generalized inverse —straightforward from Eq. (35)— is that

$$ \forall p \in [0, 1], \quad F_Z \circ F_Z^{-1}(p) \ge p \quad \text{with equality if} \quad p \in \text{Im}(F_Z). \quad (36) $$
In particular, when $F_Z$ is continuous, Eq. (36) is an equality for every $p \in [0, 1] = \text{Im}(F_Z)$. Given a sample $Z_1, \dots, Z_N$, we denote by $Z_{(1:N)} \le \dots \le Z_{(N:N)}$ the corresponding order statistics, so that $Z_{(i:N)} = \hat{Q}_{(i)}(Z_1, \dots, Z_N)$ for every $i \in \llbracket N \rrbracket$, using the notation defined by Eq. (4) in Section 2.1. When the sample size is clear from context, we note $Z_{(i)} := Z_{(i:N)}$.

We first recall the well-known following link between general order statistics and uniform order statistics (see e.g. [13]).

**Lemma 23.** For any $N \ge 1$, let $U_1, \dots, U_N$ be independent random variables with uniform distribution over $[0, 1]$, and $Z_1, \dots, Z_N$ be independent and identically distributed real-valued random variables with common cdf $F_Z$. For any $r \in \llbracket N \rrbracket$, let $U_{(r)} = U_{(r:N)}$ and $Z_{(r)} = Z_{(r:N)}$ respectively denote the corresponding r-th order statistics. Then, we have

$$F_Z(Z_{(r)}) \stackrel{d}{=} F_Z \circ F_Z^{-1}(U_{(r)}) \ge U_{(r)}, \quad \text{hence} \quad F_Z(Z_{(r)}) \succeq U_{(r)}, \qquad (37)$$

that is, $F_Z(Z_{(r)})$ stochastically dominates $U_{(r)}$. In particular, Eq. (37) implies that

$$\forall a \in \mathbb{R}, \quad \mathbb{P}(a \le F_Z(Z_{(r)})) \ge \mathbb{P}(a \le U_{(r)}) \quad \text{and} \quad \mathbb{E}[F_Z(Z_{(r)})] \ge \mathbb{E}[U_{(r)}]. \qquad (38)$$

Furthermore, when $F_Z$ is continuous,

$$F_Z(Z_{(r)}) \stackrel{d}{=} U_{(r)} \qquad (39)$$

both follow the Beta($r, N - r + 1$) distribution, and they have the same expectation and cdf.

Lemma 23 is proved in Appendix H.1 for completeness. It shows that concentration/deviation inequalities for order statistics can be obtained in general from results on uniform order statistics. Therefore, any result about the Beta distribution can be used to bound $F_Z(Z_{(r)})$ —hence the bounds on the coverage of (centralized) split CP in Section 2.1, for instance.

We now present non-asymptotic bounds on the quantile function of uniform order statistics, which rely on a concentration result for the Beta distribution [42, Theorem 1].

**Proposition 24.** For any integer $N \ge 1$ and $r \in \llbracket N \rrbracket$, the quantile function $F_{U_{(r:N)}}^{-1}$ of the r-th order statistics of a sample of $N$ independent standard uniform variables satisfies the following inequalities, for any $\delta > 0$:

$$F_{U_{(r:N)}}^{-1}(\delta) \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \qquad (40)$$

$$\text{and} \quad F_{U_{(r:N)}}^{-1}(1-\delta) \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}}. \qquad (41)$$

Proposition 24 is proved in Appendix H.2.

Finally, our coverage upper bounds (Theorems 16 and 17) rely on the following non-asymptotic upper bound on the increments of the quantile function $F_{U_{(\ell:n)}}^{-1}$ of the Beta($\ell, n-\ell+1$) distribution, showing that it is locally $O(n^{-1/2})$-Lipschitz.

**Theorem 25.** For any $n \ge 1$, $\ell \in \llbracket n \rrbracket$, $\varepsilon \in (0, 1)$, and $x \in (0, 1 - \varepsilon)$, we have

$$0 \le F_{U_{(\ell:n)}}^{-1}(x + \varepsilon) - F_{U_{(\ell:n)}}^{-1}(x) \le \frac{\varepsilon}{\sqrt{n+2}} \frac{\sqrt{2}}{g(\min\{x, 1 - x - \varepsilon\})}, \qquad (42)$$
In particular, when $F_Z$ is continuous, Eq. (36) is an equality for every $p \in [0, 1] = \text{Im}(F_Z)$. Given a sample $Z_1, \dots, Z_N$, we denote by $Z_{(1:N)} \le \dots \le Z_{(N:N)}$ the corresponding order statistics, so that $Z_{(i:N)} = \hat{Q}_{(i)}(Z_1, \dots, Z_N)$ for every $i \in [N]$, using the notation defined by Eq. (4) in Section 2.1. When the sample size is clear from context, we note $Z_{(i)} := Z_{(i:N)}$.

We first recall the well-known following link between general order statistics and uniform order statistics (see e.g. [13]).

**Lemma 23.** For any $N \ge 1$, let $U_1, \dots, U_N$ be independent random variables with uniform distribution over $[0, 1]$, and $Z_1, \dots, Z_N$ be independent and identically distributed real-valued random variables with common cdf $F_Z$. For any $r \in [N]$, let $U_{(r)} = U_{(r:N)}$ and $Z_{(r)} = Z_{(r:N)}$ respectively denote the corresponding r-th order statistics. Then, we have

$$F_Z(Z_{(r)}) \stackrel{d}{=} F_Z \circ F_Z^{-1}(U_{(r)}) \ge U_{(r)}, \quad \text{hence} \quad F_Z(Z_{(r)}) \succeq U_{(r)}, \quad (37)$$

that is, $F_Z(Z_{(r)})$ stochastically dominates $U_{(r)}$. In particular, Eq. (37) implies that

$$\forall a \in \mathbb{R}, \quad \mathbb{P}(a \le F_Z(Z_{(r)})) \ge \mathbb{P}(a \le U_{(r)}) \quad \text{and} \quad \mathbb{E}[F_Z(Z_{(r)})] \ge \mathbb{E}[U_{(r)}]. \quad (38)$$

Furthermore, when $F_Z$ is continuous,

$$F_Z(Z_{(r)}) \stackrel{d}{=} U_{(r)} \quad (39)$$

both follow the Beta($r, N - r + 1$) distribution, and they have the same expectation and cdf.

Lemma 23 is proved in Appendix H.1 for completeness. It shows that concentration/deviation inequalities for order statistics can be obtained in general from results on uniform order statistics. Therefore, any result about the Beta distribution can be used to bound $F_Z(Z_{(r)})$ —hence the bounds on the coverage of (centralized) split CP in Section 2.1, for instance.

We now present non-asymptotic bounds on the quantile function of uniform order statistics, which rely on a concentration result for the Beta distribution [42, Theorem 1].

**Proposition 24.** For any integer $N \ge 1$ and $r \in [N]$, the quantile function $F_{U_{(r:N)}}^{-1}$ of the r-th order statistics of a sample of $N$ independent standard uniform variables satisfies the following inequalities, for any $\delta > 0$:

$$F_{U_{(r:N)}}^{-1}(\delta) \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \quad (40)$$

$$\text{and} \quad F_{U_{(r:N)}}^{-1}(1-\delta) \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}}. \quad (41)$$

Proposition 24 is proved in Appendix H.2.

Finally, our coverage upper bounds (Theorems 16 and 17) rely on the following non-asymptotic upper bound on the increments of the quantile function $F_{U_{(\ell:n)}}^{-1}$ of the Beta($\ell, n-\ell+1$) distribution, showing that it is locally $O(n^{-1/2})$-Lipschitz.

**Theorem 25.** For any $n \ge 1$, $\ell \in [n]$, $\varepsilon \in (0, 1)$, and $x \in (0, 1 - \varepsilon)$, we have

$$0 \le F_{U_{(\ell:n)}}^{-1}(x + \varepsilon) - F_{U_{(\ell:n)}}^{-1}(x) \le \frac{\varepsilon}{\sqrt{n+2}} \frac{\sqrt{2}}{g(\min\{x, 1-x-\varepsilon\})}, \quad (42)$$
$$ 
\begin{array}{l}
\text{where } \forall t \in \left(0, \frac{1}{2}\right], \quad g(t) := \sup_{\delta \in (0, \min\{t, 1-t\})} \frac{t - \delta}{\sqrt{\log(1/\delta)}} \ge \frac{t}{2\sqrt{\log(2/t)}} \\
\text{and } \forall t \in [1/3, 1/2], \quad \frac{\sqrt{2}}{g(t)} \le 9.
\end{array}
$$

Theorem 25 is proved in Appendix H.4. To the best of our knowledge, such an upper bound has never been proved previously. It is a key result of the paper, used in the proof of our coverage upper bounds.

**Remark 26.** The upper bound in Eq. (42) is always well defined since g is defined on $(0, 1/2]$ and $\min\{x, 1-x-\varepsilon\} \le 1/2$ for every $\varepsilon \in (0, 1)$ and $x \in (0, 1-\varepsilon)$.

## B.2. Order statistics of order statistics

The federated learning methods of Section 3 are all based on the quantile-of-quantiles family of estimators (Definition 4 in Section 2.2), which are order statistics of order statistics, so we focus on them in this subsection.

Given a collection $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$ of m samples of size n, for every $j \in [m]$, we denote the order statistics of the j-th sample $(Z_{i,j})_{1 \le i \le n}$ by

$$ Z_{(1:n),j} \le Z_{(2:n),j} \le \dots \le Z_{(n:n),j}. $$

Then, for every $\ell \in [n]$, we denote the order statistics of the sample of the $\ell$-th order statistics $(Z_{(\ell:n),j})_{1 \le j \le m}$ by

$$ Z_{(\ell:n),(1:m)} \le Z_{(\ell:n),(2:m)} \le \dots \le Z_{(\ell:n),(m:m)}. $$

For every $\ell \in [n]$ and $k \in [m]$, $Z_{(\ell:n),(k:m)} := Z_{(\ell:n,k:m)}$ is the $(\ell, k)$-th order statistics of order statistics of $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$, which can also be written as follows with the notation defined by Eq. (4) in Section 2.1:

$$ Z_{(\ell:n,k:m)} = \hat{Q}_{(k)}\left(\left(\hat{Q}_{(\ell)}(Z_j)\right)_{j \in [m]}\right) $$

$$ \text{where } \forall j \in [m], \quad \mathcal{Z}_j := (Z_{i,j})_{i \in [n]} \quad \text{so that} \quad Z_{(\ell:n),j} = \hat{Q}_{(\ell)}(\mathcal{Z}_j). $$

In the following, we write $Z_{(\ell),j}$ (resp. $Z_{(\ell,k)}$) instead of $Z_{(\ell:n),j}$ (resp. $Z_{(\ell:n,k:m)}$) when the sample sizes n and m are clear from context.

Our first key result is a link with order statistics of uniform order statistics, similar to Lemma 23.

**Lemma 27.** For any n, m ≥ 1, let $(U_{i,j})_{1 \le i \le n, 1 \le j \le m}$ be independent random variables with uniform distribution over $[0, 1]$, and $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$ be independent and identically distributed real-valued random variables with common cdf $F_Z$. For every $\ell \in [n]$ and $k \in [m]$, let $U_{(\ell,k)}$ and $Z_{(\ell,k)}$ respectively denote the corresponding $(\ell, k)$-th order statistics of order statistics, as defined at the beginning of Appendix B.2. Then, we have

$$ F_Z(Z_{(\ell,k)}) \stackrel{d}{=} F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \ge U_{(\ell,k)}, \quad \text{hence} \quad F_Z(Z_{(\ell,k)}) \ge U_{(\ell,k)}, \quad (43) $$

that is, $F_Z(Z_{(\ell,k)})$ stochastically dominates $U_{(\ell,k)}$. In particular, Eq. (43) implies that

$$ \forall a \in \mathbb{R}, \quad \mathbb{P}(a \le F_Z(Z_{(\ell,k)})) \ge \mathbb{P}(a \le U_{(\ell,k)}) \quad \text{and} \quad \mathbb{E}[F_Z(Z_{(\ell,k)})] \ge \mathbb{E}[U_{(\ell,k)}]. \quad (44) $$

Furthermore, when $F_Z$ is continuous,

$$ F_Z(Z_{(\ell,k)}) \stackrel{d}{=} U_{(\ell,k)} \quad (45) $$

hence they have the same expectation and cdf.
$$ 
\begin{array}{ll}
\text{where} & \forall t \in \left(0, \frac{1}{2}\right], \quad g(t) := \sup_{\delta \in (0, \min\{t, 1-t\})} \frac{t - \delta}{\sqrt{\log(1/\delta)}} \ge \frac{t}{2\sqrt{\log(2/t)}} \\
\text{and} & \forall t \in [1/3, 1/2], \quad \frac{\sqrt{2}}{g(t)} \le 9.
\end{array}
$$

Theorem 25 is proved in Appendix H.4. To the best of our knowledge, such an upper bound has never been proved previously. It is a key result of the paper, used in the proof of our coverage upper bounds.

**Remark 26.** The upper bound in Eq. (42) is always well defined since g is defined on $(0, 1/2]$ and $\min\{x, 1-x-\varepsilon\} \le 1/2$ for every $\varepsilon \in (0, 1)$ and $x \in (0, 1-\varepsilon)$.

## B.2. Order statistics of order statistics

The federated learning methods of Section 3 are all based on the quantile-of-quantiles family of estimators (Definition 4 in Section 2.2), which are order statistics of order statistics, so we focus on them in this subsection.

Given a collection $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$ of $m$ samples of size $n$, for every $j \in [m]$, we denote the order statistics of the $j$-th sample $(Z_{i,j})_{1 \le i \le n}$ by

$$ Z_{(1:n),j} \le Z_{(2:n),j} \le \dots \le Z_{(n:n),j}. $$

Then, for every $\ell \in [n]$, we denote the order statistics of the sample of the $\ell$-th order statistics $(Z_{(\ell:n),j})_{1 \le j \le m}$ by

$$ Z_{(\ell:n),(1:m)} \le Z_{(\ell:n),(2:m)} \le \dots \le Z_{(\ell:n),(m:m)}. $$

For every $\ell \in [n]$ and $k \in [m]$, $Z_{(\ell:n),(k:m)} := Z_{(\ell:n,k:m)}$ is the $(\ell, k)$-th order statistics of order statistics of $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$, which can also be written as follows with the notation defined by Eq. (4) in Section 2.1:

$$ Z_{(\ell:n,k:m)} = \hat{Q}_{(k)}\left(\left(\hat{Q}_{(\ell)}(\mathcal{Z}_j)\right)_{j \in [m]}\right) $$

$$ \text{where } \forall j \in [m], \quad \mathcal{Z}_j := (Z_{i,j})_{i \in [n]} \quad \text{so that} \quad Z_{(\ell:n),j} = \hat{Q}_{(\ell)}(\mathcal{Z}_j). $$

In the following, we write $Z_{(\ell),j}$ (resp. $Z_{(\ell,k)}$) instead of $Z_{(\ell:n),j}$ (resp. $Z_{(\ell:n,k:m)}$) when the sample sizes $n$ and $m$ are clear from context.

Our first key result is a link with order statistics of uniform order statistics, similar to Lemma 23.

**Lemma 27.** For any $n, m \ge 1$, let $(U_{i,j})_{1 \le i \le n, 1 \le j \le m}$ be independent random variables with uniform distribution over $[0, 1]$, and $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$ be independent and identically distributed real-valued random variables with common cdf $F_Z$. For every $\ell \in [n]$ and $k \in [m]$, let $U_{(\ell,k)}$ and $Z_{(\ell,k)}$ respectively denote the corresponding $(\ell, k)$-th order statistics of order statistics, as defined at the beginning of Appendix B.2. Then, we have

$$ F_Z(Z_{(\ell,k)}) \stackrel{d}{=} F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \ge U_{(\ell,k)}, \quad \text{hence} \quad F_Z(Z_{(\ell,k)}) \ge U_{(\ell,k)}, \quad (43) $$

that is, $F_Z(Z_{(\ell,k)})$ stochastically dominates $U_{(\ell,k)}$. In particular, Eq. (43) implies that

$$ \forall a \in \mathbb{R}, \quad \mathbb{P}(a \le F_Z(Z_{(\ell,k)})) \ge \mathbb{P}(a \le U_{(\ell,k)}) \quad \text{and} \quad \mathbb{E}[F_Z(Z_{(\ell,k)})] \ge \mathbb{E}[U_{(\ell,k)}]. \quad (44) $$

Furthermore, when $F_Z$ is continuous,

$$ F_Z(Z_{(\ell,k)}) \stackrel{d}{=} U_{(\ell,k)} \quad (45) $$

hence they have the same expectation and cdf.
Lemma 27 is proved in Appendix H.5. It shows that concentration/deviation inequalities for order statistics of order statistics can be obtained in general from results on order statistics of uniform order statistics. Therefore, we now focus on the distribution of $U_{(\ell:n,k:m)}$.

By definition, $U_{(\ell:n,k:m)}$ is the k-th order statistics of a sample of m independent and identically distributed random variables following a Beta($\ell, n - \ell + 1$) distribution. This is called a Beta order statistics, and it follows a Beta-Beta distribution [2, 10, 26, 40]. The Beta-Beta distribution is difficult to analyze directly [9, 11] —as one can see from the formula of its expectation $M_{\ell,k}$ provided by Theorem 5 in Section 3.1—, so it is more convenient to first relate it to the well-known Beta distribution, as done by the next result.

**Lemma 28.** Let $n, m \ge 1$ be two integers, $k \in [m]$, $\ell \in [n]$. Let $U_{(\ell:n)}$ and $U_{(k:m)}$ be defined as in Lemma 23, and $U_{(\ell:n,k:m)} = U_{(\ell,k)}$ as in Lemma 27. Then, their cdfs satisfy

$$F_{U_{(\ell:n,k:m)}} = F_{U_{(k:m)}} \circ F_{U_{(\ell:n)}}. \qquad (46)$$

Lemma 28 is proved in Appendix H.6. Since the cdfs of $U_{(\ell:n)}$ and $U_{(k:m)}$ are known (see Lemma 23), it shows that the cdf of $U_{(\ell:n,k:m)}$ is the composition of the cdf of a Beta($k, m - k + 1$) with the cdf of a Beta($\ell, n - \ell + 1$).

# Appendix C: Proofs of Section 3.1 (marginal guarantees)

## C.1. Proof of Theorem 5

Throughout the proof, we reason conditionally to $D^{lrn}$. Since $(X_{i,j}, Y_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $(X, Y)$ are i.i.d., the associated scores $(S_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $S$ are i.i.d. Let us denote by $F_S$ their cdf (given $D^{lrn}$).

By definition of $\hat{C}_{\ell,k}(X)$, we have $\mathbb{P}(Y \in \hat{C}_{\ell,k}(X)) = \mathbb{P}(S \le S_{(\ell,k)}) = \mathbb{E}[F_S(S_{(\ell,k)})]$. Furthermore, by Eq. (44) in Lemma 27 with $Z_{i,j} = S_{i,j}$ (hence $F_Z = F_S$), we have

$$\mathbb{E}[F_S(S_{(\ell,k)})] \ge \mathbb{E}[U_{(\ell,k)}] := M_{\ell,k} \qquad (47)$$

in general, with equality when $F_S$ is continuous —or equivalently when the scores are a.s. distinct— by Eq. (45) in Lemma 27. It remains to prove the formula for $M_{\ell,k}$ announced in Theorem 5.

Recall that by definition, $U_{(\ell,k)} = U_{(\ell:n,k:m)}$ is the k-th order statistics of a sample $(U_{(\ell:n),j})_{1 \le j \le m}$ of m independent random variables with common distribution Beta($\ell, n - \ell + 1$). Therefore, its pdf is given by Eq. (64) in Appendix G.1 with $r = k$, $N = m$, $f_Z = f_{U_{(\ell,n)}}$ and $F_Z = F_{U_{(\ell,n)}}$. Using Eq. (65) with $r = \ell$ and $N = n$, we get that for every $t \in \mathbb{R}$,

$$\begin{align*}
f_{U_{(\ell,k)}}(t) &= \frac{m!}{(k-1)!(m-k)!} F_{U_{(\ell)}}(t)^{k-1} [1 - F_{U_{(\ell)}}(t)]^{m-k} f_{U_{(\ell)}}(t) \\
&= k \binom{m}{k} F_{U_{(\ell)}}(t)^{k-1} [1 - F_{U_{(\ell)}}(t)]^{m-k} f_{U_{(\ell)}}(t) \\
&= k \binom{m}{k} \left[ \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i} \right]^{k-1} \left[ 1 - \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i} \right]^{m-k} f_{U_{(\ell)}}(t) \\
&= k \binom{m}{k} \left[ \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i} \right]^{k-1} \left[ \sum_{i=0}^{\ell-1} \binom{n}{i} t^i (1-t)^{n-i} \right]^{m-k} f_{U_{(\ell)}}(t)
\end{align*}$$
Lemma 27 is proved in Appendix H.5. It shows that concentration/deviation inequalities for order statistics of order statistics can be obtained in general from results on order statistics of uniform order statistics. Therefore, we now focus on the distribution of $U_{(\ell:n,k:m)}$.

By definition, $U_{(\ell:n,k:m)}$ is the k-th order statistics of a sample of m independent and identically distributed random variables following a Beta($\ell, n - \ell + 1$) distribution. This is called a Beta order statistics, and it follows a Beta-Beta distribution [2, 10, 26, 40]. The Beta-Beta distribution is difficult to analyze directly [9, 11] —as one can see from the formula of its expectation $M_{\ell,k}$ provided by Theorem 5 in Section 3.1—, so it is more convenient to first relate it to the well-known Beta distribution, as done by the next result.

**Lemma 28.** Let $n, m \ge 1$ be two integers, $k \in [m]$, $\ell \in [n]$. Let $U_{(\ell:n)}$ and $U_{(k:m)}$ be defined as in Lemma 23, and $U_{(\ell:n,k:m)} = U_{(\ell,k)}$ as in Lemma 27. Then, their cdfs satisfy

$$F_{U_{(\ell:n,k:m)}} = F_{U_{(k:m)}} \circ F_{U_{(\ell:n)}}. \qquad (46)$$

Lemma 28 is proved in Appendix H.6. Since the cdfs of $U_{(\ell:n)}$ and $U_{(k:m)}$ are known (see Lemma 23), it shows that the cdf of $U_{(\ell:n,k:m)}$ is the composition of the cdf of a Beta($k, m - k + 1$) with the cdf of a Beta($\ell, n - \ell + 1$).

# Appendix C: Proofs of Section 3.1 (marginal guarantees)

## C.1. Proof of Theorem 5

Throughout the proof, we reason conditionally to $D^{lrn}$. Since $(X_{i,j}, Y_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $(X, Y)$ are i.i.d., the associated scores $(S_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $S$ are i.i.d. Let us denote by $F_S$ their cdf (given $D^{lrn}$).

By definition of $\hat{C}_{\ell,k}(X)$, we have $\mathbb{P}(Y \in \hat{C}_{\ell,k}(X)) = \mathbb{P}(S \le S_{(\ell,k)}) = \mathbb{E}[F_S(S_{(\ell,k)})]$. Furthermore, by Eq. (44) in Lemma 27 with $Z_{i,j} = S_{i,j}$ (hence $F_Z = F_S$), we have

$$\mathbb{E}[F_S(S_{(\ell,k)})] \ge \mathbb{E}[U_{(\ell,k)}] := M_{\ell,k} \qquad (47)$$

in general, with equality when $F_S$ is continuous —or equivalently when the scores are a.s. distinct— by Eq. (45) in Lemma 27. It remains to prove the formula for $M_{\ell,k}$ announced in Theorem 5.

Recall that by definition, $U_{(\ell,k)} = U_{(\ell:n,k:m)}$ is the k-th order statistics of a sample $(U_{(\ell:n),j})_{1 \le j \le m}$ of m independent random variables with common distribution Beta($\ell, n - \ell + 1$). Therefore, its pdf is given by Eq. (64) in Appendix G.1 with $r = k$, $N = m$, $f_Z = f_{U_{(\ell,n)}}$ and $F_Z = F_{U_{(\ell,n)}}$. Using Eq. (65) with $r = \ell$ and $N = n$, we get that for every $t \in \mathbb{R}$,

$$\begin{align*}
f_{U_{(\ell,k)}}(t) &= \frac{m!}{(k-1)!(m-k)!} F_{U_{(\ell)}}(t)^{k-1} [1 - F_{U_{(\ell)}}(t)]^{m-k} f_{U_{(\ell)}}(t) \\
&= k \binom{m}{k} F_{U_{(\ell)}}(t)^{k-1} [1 - F_{U_{(\ell)}}(t)]^{m-k} f_{U_{(\ell)}}(t) \\
&= k \binom{m}{k} \left[ \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i} \right]^{k-1} \left[ 1 - \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i} \right]^{m-k} f_{U_{(\ell)}}(t) \\
&= k \binom{m}{k} \left[ \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i} \right]^{k-1} \left[ \sum_{i=0}^{\ell-1} \binom{n}{i} t^i (1-t)^{n-i} \right]^{m-k} f_{U_{(\ell)}}(t)
\end{align*}$$
$$ \text{since} \quad 1 = \sum_{i=0}^{n} \binom{n}{i} t^i (1-t)^{n-i} = \sum_{i=0}^{\ell-1} \binom{n}{i} t^i (1-t)^{n-i} + \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i}. $$

Then, by developing the powers over the summations, we get that for every $t \in [0, 1]$,

$$ \begin{aligned} f_{U(\ell,k)}(t) &= k \binom{m}{k} \sum_{i_1=\ell}^{n} \dots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{\ell-1} \dots \sum_{i_m=0}^{\ell-1} \binom{n}{i_1} \dots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \dots \binom{n}{i_m} \\ & \quad \times t^{i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m} (1-t)^{n(m-1)-(i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m)} f_{U(\ell)}(t) \\ &= \frac{k \binom{m}{k}}{B(\ell, n-\ell+1)} \sum_{i_1=\ell}^{n} \dots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{\ell-1} \dots \sum_{i_m=0}^{\ell-1} \binom{n}{i_1} \dots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \dots \binom{n}{i_m} \\ & \quad \times t^{i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m+\ell-1} (1-t)^{n(m-1)-(i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m)+n-\ell}, \end{aligned} $$

where in the last equality we used the definition of $f_{U(\ell)}$. We now note that

$$ \begin{aligned} & \int_0^1 t \cdot t^{i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m+\ell-1} (1-t)^{n(m-1)-(i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m)+n-\ell} dt \\ &= \int_0^1 t^{i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m} (1-t)^{mn-(i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m)} dt \\ &= B(i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m+1, mn-(i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m)+1) \\ &= \left[ (mn+1) \binom{mn}{i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m} \right]^{-1}, \end{aligned} $$

since $B(b+1, a-b+1) = [(a+1)(b)]^{-1}$ for every $a, b \in \mathbb{N}$ such that $a \ge b$, here used with $a = mn$ and $b = (i_1 + \dots + i_{k-1} + \ell + i_{k+1} + \dots + i_m)$. We end the proof using the definition of the expectation (and the fact that $U_{(\ell,k)}$ is supported by $[0, 1]$):

$$ \begin{aligned} \mathbb{E}[U_{(\ell,k)}] &= \int_0^1 t \cdot f_{U_{(\ell,k)}}(t) dt \\ &= \frac{k \binom{m}{k} \sum_{i_1=\ell}^{n} \dots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{n} \dots \sum_{i_m=0}^{n} \frac{\binom{n}{i_1} \dots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \dots \binom{n}{i_m}}{\binom{mn}{i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m}}}{(mn+1)B(\ell, n-\ell+1)}. \end{aligned} $$

□

**Remark 29.** The first part of the proof of Theorem 5 —proving Eq. (11) in general, and showing that it is an equality when $F_S$ is continuous— is identical to the first part of the proof of [25, Theorem 3.2]. The second part of the proof is new: we here compute $\mathbb{E}[U_{(\ell,k)}]$ from its pdf —contrary to [25, Theorem 3.2] which uses its cdf—, which leads to a slightly simpler formula for $M_{\ell,k}$.

## C.2. Proof of Lemma 7

The argmin defining $(\ell^*, k^*)$ in Algorithm 1 is non-empty if and only if

$$ \max_{(\ell,k) \in [n] \times [m]} M_{\ell,k} \ge 1 - \alpha. $$
$$ \text{since} \quad 1 = \sum_{i=0}^{n} \binom{n}{i} t^i (1-t)^{n-i} = \sum_{i=0}^{\ell-1} \binom{n}{i} t^i (1-t)^{n-i} + \sum_{i=\ell}^{n} \binom{n}{i} t^i (1-t)^{n-i}. $$

Then, by developing the powers over the summations, we get that for every $t \in [0, 1]$,

$$ \begin{aligned} f_{U_{(\ell,k)}}(t) &= k \binom{m}{k} \sum_{i_1=\ell}^{n} \dots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{\ell-1} \dots \sum_{i_m=0}^{\ell-1} \binom{n}{i_1} \dots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \dots \binom{n}{i_m} \\ & \quad \times t^{i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m} (1-t)^{n(m-1)-(i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m)} f_{U_{(\ell)}}(t) \\ &= \frac{k \binom{m}{k}}{B(\ell, n-\ell+1)} \sum_{i_1=\ell}^{n} \dots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{\ell-1} \dots \sum_{i_m=0}^{\ell-1} \binom{n}{i_1} \dots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \dots \binom{n}{i_m} \\ & \quad \times t^{i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m+\ell-1} (1-t)^{n(m-1)-(i_1+\dots+i_{k-1}+i_{k+1}+\dots+i_m)+n-\ell}, \end{aligned} $$

where in the last equality we used the definition of $f_{U_{(\ell)}}$. We now note that

$$ \begin{aligned} & \int_0^1 t \cdot t^{i_1+\cdots+i_{k-1}+i_{k+1}+\cdots+i_m+\ell-1} (1-t)^{n(m-1)-(i_1+\cdots+i_{k-1}+i_{k+1}+\cdots+i_m)+n-\ell} dt \\ &= \int_0^1 t^{i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m} (1-t)^{mn-(i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m)} dt \\ &= B(i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m+1, mn-(i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m)+1) \\ &= \left[ (mn+1) \binom{mn}{i_1+\cdots+i_{k-1}+\ell+i_{k+1}+\cdots+i_m} \right]^{-1}, \end{aligned} $$

since $B(b+1, a-b+1) = [(a+1)(b)]^{-1}$ for every $a, b \in \mathbb{N}$ such that $a \ge b$, here used with $a = mn$ and $b = (i_1 + \cdots + i_{k-1} + \ell + i_{k+1} + \cdots + i_m)$. We end the proof using the definition of the expectation (and the fact that $U_{(\ell,k)}$ is supported by $[0, 1]$):

$$ \begin{aligned} \mathbb{E}[U_{(\ell,k)}] &= \int_0^1 t \cdot f_{U_{(\ell,k)}}(t) dt \\ &= \frac{k \binom{m}{k} \sum_{i_1=\ell}^{n} \dots \sum_{i_{k-1}=\ell}^{n} \sum_{i_{k+1}=0}^{n} \dots \sum_{i_m=0}^{n} \frac{\binom{n}{i_1} \dots \binom{n}{i_{k-1}} \binom{n}{i_{k+1}} \dots \binom{n}{i_m}}{\binom{mn}{i_1+\dots+i_{k-1}+\ell+i_{k+1}+\dots+i_m}}}{(mn+1)B(\ell, n-\ell+1)}. \end{aligned} $$

□

**Remark 29.** The first part of the proof of Theorem 5 —proving Eq. (11) in general, and showing that it is an equality when $F_S$ is continuous— is identical to the first part of the proof of [25, Theorem 3.2]. The second part of the proof is new: we here compute $\mathbb{E}[U_{(\ell,k)}]$ from its pdf —contrary to [25, Theorem 3.2] which uses its cdf—, which leads to a slightly simpler formula for $M_{\ell,k}$.

### C.2. Proof of Lemma 7

The argmin defining $(\ell^*, k^*)$ in Algorithm 1 is non-empty if and only if

$$ \max_{(\ell,k) \in [n] \times [m]} M_{\ell,k} \ge 1 - \alpha. $$
Since $M_{\ell,k} = \mathbb{E}[U_{(\ell:n,k:m)}]$ —see Eq. (47) in Appendix C.1—, it is a nondecreasing function of $(\ell, k)$ (for the lexicographic order), hence

$$ \max_{(\ell,k) \in [[n]] \times [[m]]} M_{\ell,k} = M_{n,m} = \mathbb{E}[U_{(n:n,m:m)}] = \mathbb{E}\left[\max_{(i,j) \in [[n]] \times [[m]]} U_{i,j}\right] $$

where the $(U_{i,j})_{(i,j) \in [[n]] \times [[m]]}$ are independent standard uniform random variables, hence

$$ M_{n,m} = \mathbb{E}[U_{(mn:mn)}] = \frac{mn}{mn+1} $$

by Eq. (69) with $r = N = mn$. Finally, we have proved that the argmin defining $(\ell^*, k^*)$ in Algorithm 1 is non-empty if and only if

$$ \frac{mn}{mn+1} = 1 - \frac{1}{mn+1} \ge 1 - \alpha, $$

which is equivalent to $mn + 1 \ge \alpha^{-1}$. $\square$

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

### C.3. Proof of Proposition 8

Recall that by Eq. (47) in Appendix C.1, $M_{\ell,k} = \mathbb{E}[U_{(\ell:n,k:m)}]$ where $U_{(\ell:n,k:m)}$ is the $k$-th order statistics of a sample $(U_{(\ell:n),j})_{1 \le j \le m}$ of $m$ independent random variables with common distribution Beta$(\ell, n - \ell + 1)$ and cdf $F_{U_{(\ell:n)}}$. Since $\ell \ge 1$ and $n - \ell + 1 \ge 1$, the function $1 - F_{U_{(\ell:n)}}$ is log-concave [5, Section 6.3 and Theorem 3] and thus [13, Equation (4.5.7)] shows that

$$ \begin{aligned} F_{U_{(\ell:n)}}(\mathbb{E}[U_{(\ell:n,k:m)}]) &= F_{U_{(\ell:n)}}\left(\mathbb{E}[\tilde{Q}_{(k)}(U_{(\ell:n),1}, \dots, U_{(\ell:n),m})]\right) \\ &\le 1 - \exp\left(-\sum_{i=0}^{k-1} \frac{1}{m-i}\right) < \frac{k}{m+1/2}, \end{aligned} \quad (48) $$

hence the upper bound of Eq. (12).

For the lower bound, we first remark that $\mathbb{E}[U_{(\ell,k)}] = 1 - \mathbb{E}[U_{(n-\ell+1,m-k+1)}]$. Indeed, defining $\tilde{U}_{i,j} = 1 - U_{i,j}$ for every $i, j \in [[n]] \times [[m]]$, on the one hand, we have $\tilde{U}_{(\ell,k)} = 1 - U_{(n-\ell+1,m-k+1)}$, and on the other hand, the fact that $(\tilde{U}_{i,j})_{i,j \in [[n]] \times [[m]]} \stackrel{d}{=} (U_{i,j})_{i,j \in [[n]] \times [[m]]}$ implies that $U_{(\ell,k)} \stackrel{d}{=} \tilde{U}_{(\ell,k)}$. So, we have proved that

$$ U_{(\ell:n,k:m)} \stackrel{d}{=} 1 - U_{((n-\ell+1):n, (m-k+1):m)} $$

hence the result by taking the expectation. Therefore, using the upper bound of Eq. (12), we get that

$$ M_{\ell,k} = 1 - M_{n-\ell+1,m-k+1} > 1 - F_{U_{(n-\ell+1:n)}}^{-1}\left(\frac{m-k+1}{m+1/2}\right) = F_{U_{(\ell:n)}}^{-1}\left(\frac{k-1/2}{m+1/2}\right) $$

since $F_{U_{(n-\ell+1:n)}}^{-1}(x) = 1 - F_{U_{(\ell:n)}}^{-1}(1 - x)$, again by a symmetry argument $(U_{(\ell:n)} \stackrel{d}{=} 1 - U_{(n-\ell+1:n)})$ [see also 59, about this property of the incomplete Beta function]. $\square$

<figure><img src="image_13.png" /></figure>
Since $M_{\ell,k} = \mathbb{E}[U_{(\ell:n,k:m)}]$ —see Eq. (47) in Appendix C.1—, it is a nondecreasing function of $(\ell, k)$ (for the lexicographic order), hence

$$ \max_{(\ell,k) \in \llbracket n \rrbracket \times \llbracket m \rrbracket} M_{\ell,k} = M_{n,m} = \mathbb{E}[U_{(n:n,m:m)}] = \mathbb{E}\left[\max_{(i,j) \in \llbracket n \rrbracket \times \llbracket m \rrbracket} U_{i,j}\right] $$

where the $(U_{i,j})_{(i,j) \in \llbracket n \rrbracket \times \llbracket m \rrbracket}$ are independent standard uniform random variables, hence

$$ M_{n,m} = \mathbb{E}[U_{(mn:mn)}] = \frac{mn}{mn+1} $$

by Eq. (69) with $r = N = mn$. Finally, we have proved that the argmin defining $(\ell^*, k^*)$ in Algorithm 1 is non-empty if and only if

$$ \frac{mn}{mn+1} = 1 - \frac{1}{mn+1} \ge 1 - \alpha, $$

which is equivalent to $mn + 1 \ge \alpha^{-1}$. $\square$

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

### C.3. Proof of Proposition 8

Recall that by Eq. (47) in Appendix C.1, $M_{\ell,k} = \mathbb{E}[U_{(\ell:n,k:m)}]$ where $U_{(\ell:n,k:m)}$ is the k-th order statistics of a sample $(U_{(\ell:n),j})_{1 \le j \le m}$ of m independent random variables with common distribution Beta$(\ell, n - \ell + 1)$ and cdf $F_{U_{(\ell:n)}}$. Since $\ell \ge 1$ and $n - \ell + 1 \ge 1$, the function $1 - F_{U_{(\ell:n)}}$ is log-concave [5, Section 6.3 and Theorem 3] and thus [13, Equation (4.5.7)] shows that

$$ \begin{aligned} F_{U_{(\ell:n)}}(\mathbb{E}[U_{(\ell:n,k:m)}]) &= F_{U_{(\ell:n)}}\left(\mathbb{E}[\tilde{Q}_{(k)}(U_{(\ell:n),1}, \dots, U_{(\ell:n),m})]\right) \\ &\le 1 - \exp\left(-\sum_{i=0}^{k-1} \frac{1}{m-i}\right) < \frac{k}{m+1/2}, \end{aligned} \quad (48) $$

hence the upper bound of Eq. (12).

For the lower bound, we first remark that $\mathbb{E}[U_{(\ell,k)}] = 1 - \mathbb{E}[U_{(n-\ell+1,m-k+1)}]$. Indeed, defining $\tilde{U}_{i,j} = 1 - U_{i,j}$ for every $i, j \in \llbracket n \rrbracket \times \llbracket m \rrbracket$, on the one hand, we have $\tilde{U}_{(\ell,k)} = 1 - U_{(n-\ell+1,m-k+1)}$, and on the other hand, the fact that $(\tilde{U}_{i,j})_{i,j \in \llbracket n \rrbracket \times \llbracket m \rrbracket} \stackrel{d}{=} (U_{i,j})_{i,j \in \llbracket n \rrbracket \times \llbracket m \rrbracket}$ implies that $U_{(\ell,k)} \stackrel{d}{=} \tilde{U}_{(\ell,k)}$. So, we have proved that

$$ U_{(\ell:n,k:m)} \stackrel{d}{=} 1 - U_{((n-\ell+1):n, (m-k+1):m)} $$

hence the result by taking the expectation. Therefore, using the upper bound of Eq. (12), we get that

$$ M_{\ell,k} = 1 - M_{n-\ell+1,m-k+1} > 1 - F_{U_{(n-\ell+1:n)}}^{-1}\left(\frac{m-k+1}{m+1/2}\right) = F_{U_{(\ell:n)}}^{-1}\left(\frac{k-1/2}{m+1/2}\right) $$

since $F_{U_{(n-\ell+1:n)}}^{-1}(x) = 1 - F_{U_{(\ell:n)}}^{-1}(1 - x)$, again by a symmetry argument ($U_{(\ell:n)} \stackrel{d}{=} 1 - U_{(n-\ell+1:n)}$) [see also 59, about this property of the incomplete Beta function]. $\square$

<figure><img src="image_13.png" /></figure>
### C.4. Proof of Lemma 9

The argmin defining $\tilde{\ell}$ in Algorithm 2 is non-empty if and only if

$$ \min_{\ell \in [n]} \tilde{k}_{m,n}(\ell, \alpha) \le m. $$

Since $F_{U_{(\ell:n)}}(1-\alpha) = \mathbb{P}(U_{(\ell:n)} \le 1 - \alpha)$, it is a nonincreasing function of $\ell$, hence, by Eq. (13),

$$ \begin{aligned} \min_{\ell \in [n]} \tilde{k}_{m,n}(\ell, \alpha) &= \tilde{k}_{m,n}(n, \alpha) = \left\lceil (m + 1/2) \cdot F_{U_{(n:n)}}(1 - \alpha) + 1/2 \right\rceil \\ &= \left\lceil (m + 1/2)(1 - \alpha)^n + 1/2 \right\rceil, \end{aligned} $$

using Eq. (65) in Appendix G.1. This directly leads to the necessary and sufficient condition (14).

Note that Eq. (14) can be rewritten

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

The function $x \in [0, +\infty) \mapsto (1+x)^{1/n}$ being concave, it is below its first-order approximation at $x=0$, so that

$$ \left(1 + \frac{1}{m - 1/2}\right)^{1/n} \le 1 + \frac{1}{n(m - 1/2)} $$

and, if $n(m - 1/2) \ge \alpha^{-1} - 1$, this upper bound is smaller than

$$ 1 + \frac{1}{\alpha^{-1} - 1} = \frac{\alpha^{-1}}{\alpha^{-1} - 1} = \frac{1}{1 - \alpha}. $$

□

## Appendix D: Proofs of Section 3.2 (training-conditional guarantees)

### D.1. Proof of Theorem 10

As previously, we make this proof conditionally to $\mathcal{D}^{lrn}$ without writing it explicitly in the following. Since $(X_{i,j}, Y_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $(X, Y)$ are i.i.d., the associated scores $(S_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $S$ are i.i.d. We denote by $F_S$ their cdf (given $\mathcal{D}^{lrn}$). Now, notice that

$$ 1 - \alpha_{\ell,k}(\mathcal{D}) := \mathbb{P}(Y \in \hat{C}_{\ell,k}(X) | \mathcal{D}) = \mathbb{P}(S \le S_{(\ell,k)} | (S_{i,j})_{1 \le i \le n, 1 \le j \le m} = F_S(S_{(\ell,k)}). $$

Therefore, applying Lemma 27 with $F_Z = F_S$, Eq. (44) with $a = F_{U_{(\ell,k)}}^{-1}(\beta)$ shows that

$$ \begin{aligned} \mathbb{P}(1 - \alpha_{\ell,k}(\mathcal{D}) \ge F_{U_{(\ell,k)}}^{-1}(\beta)) &= \mathbb{P}(F_S(S_{(\ell,k)}) \ge F_{U_{(\ell,k)}}^{-1}(\beta)) \\ &\ge \mathbb{P}(U_{(\ell,k)} \ge F_{U_{(\ell,k)}}^{-1}(\beta)) = 1 - \beta, \end{aligned} \quad (49) $$

that is, Eq. (17) holds true. The formula for $F_{U_{(\ell,k)}}^{-1}$ follows from Lemma 28. When the scores are a.s. distinct—or equivalently when $F_S$ is continuous—, Eq. (45) in Lemma 27 shows that $1 - \alpha_{\ell,k}(\mathcal{D}) \stackrel{d}{=} U_{(\ell,k)}$ hence Eq. (49) is an equality and Eq. (18) holds true. □
### C.4. Proof of Lemma 9

The argmin defining $\tilde{\ell}$ in Algorithm 2 is non-empty if and only if

$$ \min_{\ell \in [n]} \tilde{k}_{m,n}(\ell, \alpha) \le m. $$

Since $F_{U_{(\ell:n)}}(1-\alpha) = \mathbb{P}(U_{(\ell:n)} \le 1 - \alpha)$, it is a nonincreasing function of $\ell$, hence, by Eq. (13),

$$ \begin{aligned} \min_{\ell \in [n]} \tilde{k}_{m,n}(\ell, \alpha) &= \tilde{k}_{m,n}(n, \alpha) = \left[ (m + 1/2) \cdot F_{U_{(n:n)}}(1 - \alpha) + 1/2 \right] \\ &= \left[ (m + 1/2)(1 - \alpha)^n + 1/2 \right], \end{aligned} $$

using Eq. (65) in Appendix G.1. This directly leads to the necessary and sufficient condition (14).

Note that Eq. (14) can be rewritten

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

The function $x \in [0, +\infty) \mapsto (1+x)^{1/n}$ being concave, it is below its first-order approximation at $x=0$, so that

$$ \left(1 + \frac{1}{m - 1/2}\right)^{1/n} \le 1 + \frac{1}{n(m - 1/2)} $$

and, if $n(m - 1/2) \ge \alpha^{-1} - 1$, this upper bound is smaller than

$$ 1 + \frac{1}{\alpha^{-1} - 1} = \frac{\alpha^{-1}}{\alpha^{-1} - 1} = \frac{1}{1 - \alpha}. $$

□

## Appendix D: Proofs of Section 3.2 (training-conditional guarantees)

### D.1. Proof of Theorem 10

As previously, we make this proof conditionally to $\mathcal{D}^{lrn}$ without writing it explicitly in the following. Since $(X_{i,j}, Y_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $(X, Y)$ are i.i.d., the associated scores $(S_{i,j})_{1 \le i \le n, 1 \le j \le m}$, $S$ are i.i.d. We denote by $F_S$ their cdf (given $\mathcal{D}^{lrn}$). Now, notice that

$$ 1 - \alpha_{\ell,k}(\mathcal{D}) := \mathbb{P}(Y \in \hat{C}_{\ell,k}(X) | \mathcal{D}) = \mathbb{P}(S \le S_{(\ell,k)} | (S_{i,j})_{1 \le i \le n, 1 \le j \le m} = F_S(S_{(\ell,k)}). $$

Therefore, applying Lemma 27 with $F_Z = F_S$, Eq. (44) with $a = F_{U_{(\ell,k)}}^{-1}(\beta)$ shows that

$$ \begin{aligned} \mathbb{P}(1 - \alpha_{\ell,k}(\mathcal{D}) \ge F_{U_{(\ell,k)}}^{-1}(\beta)) &= \mathbb{P}(F_S(S_{(\ell,k)}) \ge F_{U_{(\ell,k)}}^{-1}(\beta)) \\ &\ge \mathbb{P}(U_{(\ell,k)} \ge F_{U_{(\ell,k)}}^{-1}(\beta)) = 1 - \beta, \end{aligned} \quad (49) $$

that is, Eq. (17) holds true. The formula for $F_{U_{(\ell,k)}}^{-1}$ follows from Lemma 28. When the scores are a.s. distinct—or equivalently when $F_S$ is continuous—, Eq. (45) in Lemma 27 shows that $1 - \alpha_{\ell,k}(\mathcal{D}) \stackrel{d}{=} U_{(\ell,k)}$ hence Eq. (49) is an equality and Eq. (18) holds true. □
## D.2. Proof of Lemma 12

The argmin defining $(\ell_c^*, k_c^*)$ in Algorithm 3 is non-empty if and only if

$$ \max_{(\ell,k) \in [n]^2 \times [m]} F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge 1 - \alpha. $$

Since $U_{(\ell:n,k:m)}$ is almost surely a nondecreasing function of $(\ell, k)$ for the lexicographic order, $F_{U_{(\ell:n,k:m)}}^{-1}(\beta)$ is a nondecreasing function of $(\ell, k)$, hence

$$ \max_{(\ell,k) \in [n]^2 \times [m]} F_{U_{(\ell:n,k:m)}}^{-1}(\beta) = F_{U_{(n:n,m:m)}}^{-1}(\beta) = F_{U_{(nm:nm)}}^{-1}(\beta) = \beta^{1/(mn)} $$

by Eq. (66) in Appendix G.1. So, $(\ell_c^*, k_c^*)$ is well defined if and only if $\beta^{1/(mn)} \ge 1 - \alpha$. The conclusion follows. □

## D.3. Proof of Proposition 13

By Eq. (46) in Lemma 28, $F_{U_{(\ell:n,k:m)}}^{-1}(\beta) = F_{U_{(\ell:n)}}^{-1} \circ F_{U_{(k:m)}}^{-1}(\beta)$. Furthermore, Eq. (40) in Proposition 24 with $N = m$, $r = k$ and $\delta = \beta$ shows that

$$ F_{U_{(k:m)}}^{-1}(\beta) \ge \frac{k}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}}. $$

This proves Eq. (21) since $F_{U_{(\ell:n)}}^{-1}$ is nondecreasing. □

## D.4. Proof of Lemma 14

The argmin defining $\tilde{\ell}^{\text{cond}}$ in Algorithm 4 is non-empty if and only if

$$ \min_{\ell \in [n]} \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta) \le m. $$

Since $F_{U_{(\ell:n)}}(1 - \alpha)$ is a nonincreasing function of $\ell$, using also Eq. (66) in Appendix G.1, we have

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

hence the argmin defining $\tilde{\ell}^{\text{cond}}$ in Algorithm 4 is non-empty if and only if

$$ (m+1) \left( (1-\alpha)^n + \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right) \le m, $$

which is equivalent to Eq. (23).

For the sufficient condition, remark that when $m \ge 2$ we have

$$ \frac{m}{m+1} \ge \frac{2}{3}. $$

If in addition

$$ m \ge \frac{9}{2} \log(1/\beta) - 2, $$

then

$$ \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \le \frac{1}{3}, \quad \text{hence} \quad \frac{m}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \ge \frac{1}{3}. $$

Finally, if we also have $n \ge \frac{\log(1/3)}{\log(1-\alpha)}$, then $(1 - \alpha)^n \le 1/3$ and we get that Eq. (23) holds true, which proves Eq. (24). □
## D.2. Proof of Lemma 12

The argmin defining $(\ell_c^*, k_c^*)$ in Algorithm 3 is non-empty if and only if

$$ \max_{(\ell,k) \in [n]^2 \times [m]} F_{U_{(\ell:n,k:m)}}^{-1}(\beta) \ge 1 - \alpha. $$

Since $U_{(\ell:n,k:m)}$ is almost surely a nondecreasing function of $(\ell, k)$ for the lexicographic order, $F_{U_{(\ell:n,k:m)}}^{-1}(\beta)$ is a nondecreasing function of $(\ell, k)$, hence

$$ \max_{(\ell,k) \in [n]^2 \times [m]} F_{U_{(\ell:n,k:m)}}^{-1}(\beta) = F_{U_{(n:n,m:m)}}^{-1}(\beta) = F_{U_{(nm:nm)}}^{-1}(\beta) = \beta^{1/(mn)} $$

by Eq. (66) in Appendix G.1. So, $(\ell_c^*, k_c^*)$ is well defined if and only if $\beta^{1/(mn)} \ge 1 - \alpha$. The conclusion follows. □

## D.3. Proof of Proposition 13

By Eq. (46) in Lemma 28, $F_{U_{(\ell:n,k:m)}}^{-1}(\beta) = F_{U_{(\ell:n)}}^{-1} \circ F_{U_{(k:m)}}^{-1}(\beta)$. Furthermore, Eq. (40) in Proposition 24 with $N = m$, $r = k$ and $\delta = \beta$ shows that

$$ F_{U_{(k:m)}}^{-1}(\beta) \ge \frac{k}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}}. $$

This proves Eq. (21) since $F_{U_{(\ell:n)}}^{-1}$ is nondecreasing. □

## D.4. Proof of Lemma 14

The argmin defining $\tilde{\ell}^{\text{cond}}$ in Algorithm 4 is non-empty if and only if

$$ \min_{\ell \in [n]} \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta) \le m. $$

Since $F_{U_{(\ell:n)}}(1 - \alpha)$ is a nonincreasing function of $\ell$, using also Eq. (66) in Appendix G.1, we have

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

hence the argmin defining $\tilde{\ell}^{\text{cond}}$ in Algorithm 4 is non-empty if and only if

$$ (m+1) \left( (1-\alpha)^n + \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right) \le m, $$

which is equivalent to Eq. (23).

For the sufficient condition, remark that when $m \ge 2$ we have

$$ \frac{m}{m+1} \ge \frac{2}{3}. $$

If in addition

$$ m \ge \frac{9}{2} \log(1/\beta) - 2, $$

then

$$ \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \le \frac{1}{3}, \quad \text{hence} \quad \frac{m}{m+1} - \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \ge \frac{1}{3}. $$

Finally, if we also have $n \ge \frac{\log(1/3)}{\log(1-\alpha)}$, then $(1 - \alpha)^n \le 1/3$ and we get that Eq. (23) holds true, which proves Eq. (24). □
# Appendix E: Proofs of Section 4 (upper bounds)

## E.1. Proof of Theorem 16

Let $\alpha \in (0, 1)$ be fixed. Let $(\ell_1, k_1) := (\ell^*, k^*)$ as defined by Algorithm 1, and $(\ell_2, k_2) := (\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))$ as defined by Algorithm 2. First, by definition of Algorithms 1–2 and by Proposition 8, we have

$$1 - \alpha \le M_{\ell_1, k_1} := \min_{(\ell, k)} \{M_{\ell, k} : M_{\ell, k} \ge 1 - \alpha\} \le M_{\ell_2, k_2} \le F_{U_{(\ell_2:n)}}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell_2, \alpha)}{m + 1/2} \right). \quad (50)$$

Second, by definition of Algorithm 2, for every $\ell \in [n]$ such that $\tilde{k}_{m,n}(\ell, \alpha) \le m$, we have

$$\begin{aligned} F_{U_{(\ell_2:n)}}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell_2, \alpha)}{m + 1/2} \right) &\le F_{U_{(\ell:n)}}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha)}{m + 1/2} \right) \\ &= F_{U_{(\ell:n)}}^{-1} \left( \frac{\left[ (m + 1/2) \cdot F_{U_{(\ell:n)}}(1 - \alpha) + 1/2 \right]}{m + 1/2} \right) \\ &\le F_{U_{(\ell:n)}}^{-1} \left( F_{U_{(\ell:n)}}(1 - \alpha) + \frac{3}{2m + 1} \right). \end{aligned} \quad (51)$$

By Theorem 25 with $x = F_{U_{(\ell:n)}}(1 - \alpha)$, hence $F_{U_{(\ell:n)}}^{-1}(x) = 1 - \alpha$, and $\varepsilon = \frac{3}{2m+1}$, we get that if $0 < F_{U_{(\ell:n)}}(1 - \alpha) < 1 - \frac{3}{2m+1}$, then

$$\begin{aligned} &F_{U_{(\ell:n)}}^{-1} \left( F_{U_{(\ell:n)}}(1-\alpha) + \frac{3}{2m+1} \right) \\ &\le 1 - \alpha + \frac{3}{(2m+1)\sqrt{n+2}} \frac{\sqrt{2}}{g(\min\{F_{U_{(\ell:n)}}(1-\alpha), 1-F_{U_{(\ell:n)}}(1-\alpha) - \frac{3}{2m+1}\})} \end{aligned} \quad (52)$$

Third, note that for every $\alpha \in (0, 1)$, by Eq. (71) in Appendix G.2 with $p = 1 - \alpha$,

$$\begin{aligned} &\sqrt{n} (U_{(\lceil(1-\alpha)n\rceil)} - (1-\alpha)) \xrightarrow[n \to +\infty]{\mathcal{L}} \mathcal{N}(0, \alpha(1-\alpha)) \\ &\text{hence} \quad F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1-\alpha) \xrightarrow[n \to +\infty]{\text{a.s.}} \frac{1}{2}. \end{aligned} \quad (53)$$

As a consequence, some $n_0(\alpha)$ exists such that, for every $n \ge n_0(\alpha)$, we have $1/3 \le F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1 - \alpha) \le 7/12$. Therefore, for every $n \ge n_0(\alpha)$ and $m \ge 18$,

$$\min \left\{ F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1-\alpha), 1 - F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1-\alpha) - \frac{3}{2m+1} \right\} \ge \frac{1}{3}$$

and by Eq. (50)–(52), we get that

$$1 - \alpha \le M_{\ell_1, k_1} \le M_{\ell_2, k_2} \le 1 - \alpha + \frac{27}{(2m+1)\sqrt{n+2}}.$$

Note that the choice of the constants 1/3 and 7/12 in the proof is arbitrary. Other choices would lead to the same result with other values for $C$, $m_0$ and $n_0(\alpha)$. For instance, $C$ can be made as close to $3\sqrt{2}/g(1/2) \le 16.1$ as desired, at the price of enlarging $m_0$ and $n_0(\alpha)$. $\square$
# Appendix E: Proofs of Section 4 (upper bounds)

## E.1. Proof of Theorem 16

Let $\alpha \in (0, 1)$ be fixed. Let $(\ell_1, k_1) := (\ell^*, k^*)$ as defined by Algorithm 1, and $(\ell_2, k_2) := (\tilde{\ell}, \tilde{k}_{m,n}(\tilde{\ell}, \alpha))$ as defined by Algorithm 2. First, by definition of Algorithms 1–2 and by Proposition 8, we have

$$1 - \alpha \le M_{\ell_1, k_1} := \min_{(\ell, k)} \{M_{\ell, k} : M_{\ell, k} \ge 1 - \alpha\} \le M_{\ell_2, k_2} \le F_{U_{(\ell_2:n)}}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell_2, \alpha)}{m + 1/2} \right). \quad (50)$$

Second, by definition of Algorithm 2, for every $\ell \in \llbracket n \rrbracket$ such that $\tilde{k}_{m,n}(\ell, \alpha) \le m$, we have

$$\begin{aligned} F_{U_{(\ell_2:n)}}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell_2, \alpha)}{m + 1/2} \right) &\le F_{U_{(\ell:n)}}^{-1} \left( \frac{\tilde{k}_{m,n}(\ell, \alpha)}{m + 1/2} \right) \\ &= F_{U_{(\ell:n)}}^{-1} \left( \frac{\left[ (m + 1/2) \cdot F_{U_{(\ell:n)}}(1 - \alpha) + 1/2 \right]}{m + 1/2} \right) \\ &\le F_{U_{(\ell:n)}}^{-1} \left( F_{U_{(\ell:n)}}(1 - \alpha) + \frac{3}{2m + 1} \right). \end{aligned} \quad (51)$$

By Theorem 25 with $x = F_{U_{(\ell:n)}}(1 - \alpha)$, hence $F_{U_{(\ell:n)}}^{-1}(x) = 1 - \alpha$, and $\varepsilon = \frac{3}{2m+1}$, we get that if $0 < F_{U_{(\ell:n)}}(1 - \alpha) < 1 - \frac{3}{2m+1}$, then

$$F_{U_{(\ell:n)}}^{-1} \left( F_{U_{(\ell:n)}}(1-\alpha) + \frac{3}{2m+1} \right) \le 1-\alpha + \frac{3}{(2m+1)\sqrt{n+2}} \frac{\sqrt{2}}{g(\min\{F_{U_{(\ell:n)}}(1-\alpha), 1-F_{U_{(\ell:n)}}(1-\alpha) - \frac{3}{2m+1}\})} \quad (52)$$

Third, note that for every $\alpha \in (0, 1)$, by Eq. (71) in Appendix G.2 with $p = 1 - \alpha$,

$$\begin{gathered} \sqrt{n} (U_{(\lceil(1-\alpha)n\rceil)} - (1-\alpha)) \xrightarrow[n \to +\infty]{\mathcal{L}} \mathcal{N}(0, \alpha(1-\alpha)) \\ \text{hence} \quad F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1-\alpha) \xrightarrow[n \to +\infty]{\text{a.s.}} \frac{1}{2}. \end{gathered} \quad (53)$$

As a consequence, some $n_0(\alpha)$ exists such that, for every $n \ge n_0(\alpha)$, we have $1/3 \le F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1 - \alpha) \le 7/12$. Therefore, for every $n \ge n_0(\alpha)$ and $m \ge 18$,

$$\min \left\{ F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1-\alpha), 1 - F_{U_{(\lceil(1-\alpha)n\rceil:n)}}(1-\alpha) - \frac{3}{2m+1} \right\} \ge \frac{1}{3}$$

and by Eq. (50)–(52), we get that

$$1 - \alpha \le M_{\ell_1, k_1} \le M_{\ell_2, k_2} \le 1 - \alpha + \frac{27}{(2m+1)\sqrt{n+2}}.$$

Note that the choice of the constants 1/3 and 7/12 in the proof is arbitrary. Other choices would lead to the same result with other values for $C$, $m_0$ and $n_0(\alpha)$. For instance, $C$ can be made as close to $3\sqrt{2}/g(1/2) \le 16.1$ as desired, at the price of enlarging $m_0$ and $n_0(\alpha)$. $\square$
## E.2. Proof of Theorem 17

The proof relies on the following lemma.

**Lemma 30.** Let $n, m \ge 1$, $\ell \in [n]$, $\alpha, \beta, \beta' \in (0, 1)$ and let $\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)$ be defined by Eq. (22). Then, some $n'_0(\alpha), m'_0(\beta, \beta') \ge 1$ exist such that, if $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, we have $\lceil n(1-\alpha) \rceil \in [n]$, $\tilde{k}_{m,n}^{\text{cond}}(\lceil n(1-\alpha) \rceil, \alpha, \beta) \in [m]$ and

$$F_{U(\lceil n(1-\alpha) \rceil:n, \tilde{k}_{m,n}^{\text{cond}}(\lceil n(1-\alpha) \rceil, \alpha, \beta):m)}^{-1}(1-\beta') \le 1-\alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}. \quad (54)$$

*Proof.* The first condition holds true when $n \ge 1/\alpha$, hence it suffices to take $n'_0(\alpha) \ge n'_{0,a}(\alpha) = 1/\alpha$. For the second condition, which can be rewritten

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

we first notice that by Eq. (53), some $n'_{0,b}(\alpha)$ exists such that, for every $n \ge n'_{0,b}(\alpha)$,

$$\frac{1}{3} \le F_{U(\lceil (1-\alpha)n \rceil:n)}(1-\alpha) \le \frac{2}{3}. \quad (55)$$

Therefore, some $m'_{0,a}(\beta)$ exists such that, if $m \ge m'_{0,a}(\beta)$ and $n \ge n'_{0,b}(\alpha)$,

$$\tilde{k}_{m,n}^{\text{cond}}(\lceil n(1-\alpha) \rceil, \alpha, \beta) \le \left[ (m+1) \left( \frac{2}{3} + \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right) \right] \le m,$$

hence the second condition holds true if $m'_{0}(\beta, \beta') \ge m'_{0,a}(\beta)$.

It remains to prove Eq. (54). For every $\ell \in [n]$, if $\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta) \in [m]$, we have

$$\begin{align*}
& F_{U(\ell:n, \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta):m)}^{-1}(1-\beta') \\
&= F_{U(\ell:n)}^{-1} \circ F_{U(\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta):m)}^{-1}(1-\beta') && \text{by Eq. (46) in Lemma 28} \\
&\le F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)}{m+1} + \sqrt{\frac{\log(1/\beta')}{2(m+2)}} \right) && \text{by Eq. (41) in Proposition 24} \\
&\le F_{U(\ell:n)}^{-1} \left( F_{U(\ell:n)}(1-\alpha) + \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(m+2)}} + \frac{1}{m+1} \right) && \text{by Eq. (22)} \\
&\le 1-\alpha + \frac{\varepsilon_m}{\sqrt{n+2}} \frac{\sqrt{2}}{g(\min\{x_n, 1-x_n - \varepsilon_m\})} && \tag{56}
\end{align*}$$

by Theorem 25 with

$$x = x_n := F_{U(\ell:n)}(1-\alpha) \quad \text{and} \quad \varepsilon = \varepsilon_m := \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(m+2)}} + \frac{1}{m+1},$$

assuming also that $x_n + \varepsilon_m < 1$. Now, taking $\ell = \lceil (1-\alpha)n \rceil$ in Eq. (56), when $m \ge m'_{0,a}(\beta)$ and $n \ge \max\{n'_{0,a}(\alpha), n'_{0,b}(\alpha)\}$, we have $\ell \in [n]$, $\tilde{k}_{m,n}^{\text{cond}}(\lceil (1-\alpha)n \rceil, \alpha, \beta) \in [m]$ and $x_n \in [1/3, 2/3]$ by Eq. (55). Since some $m'_{0,b}(\beta, \beta')$ exists such that $\varepsilon_m \le 1/12$ as soon as $m \ge m'_{0,b}(\beta, \beta')$, we get that for $m \ge \max\{m'_{0,a}(\beta), m'_{0,b}(\beta, \beta')\}$ and $n \ge$
## E.2. Proof of Theorem 17

The proof relies on the following lemma.

**Lemma 30.** Let $n, m \ge 1$, $\ell \in [n]$, $\alpha, \beta, \beta' \in (0, 1)$ and let $\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)$ be defined by Eq. (22). Then, some $n'_0(\alpha), m'_0(\beta, \beta') \ge 1$ exist such that, if $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, we have $\lceil n(1-\alpha) \rceil \in [n]$, $\tilde{k}_{m,n}^{\text{cond}}(\lceil n(1-\alpha) \rceil, \alpha, \beta) \in [m]$ and

$$F_{U(\lceil n(1-\alpha) \rceil:n, \tilde{k}_{m,n}^{\text{cond}}(\lceil n(1-\alpha) \rceil, \alpha, \beta):m)}^{-1}(1-\beta') \le 1-\alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}. \quad (54)$$

*Proof.* The first condition holds true when $n \ge 1/\alpha$, hence it suffices to take $n'_0(\alpha) \ge n'_{0,a}(\alpha) = 1/\alpha$. For the second condition, which can be rewritten

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

we first notice that by Eq. (53), some $n'_{0,b}(\alpha)$ exists such that, for every $n \ge n'_{0,b}(\alpha)$,

$$\frac{1}{3} \le F_{U(\lceil (1-\alpha)n \rceil:n)}(1-\alpha) \le \frac{2}{3}. \quad (55)$$

Therefore, some $m'_{0,a}(\beta)$ exists such that, if $m \ge m'_{0,a}(\beta)$ and $n \ge n'_{0,b}(\alpha)$,

$$\tilde{k}_{m,n}^{\text{cond}}(\lceil n(1-\alpha) \rceil, \alpha, \beta) \le \left[ (m+1) \left( \frac{2}{3} + \sqrt{\frac{\log(1/\beta)}{2(m+2)}} \right) \right] \le m,$$

hence the second condition holds true if $m'_0(\beta, \beta') \ge m'_{0,a}(\beta)$.

It remains to prove Eq. (54). For every $\ell \in [n]$, if $\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta) \in [m]$, we have

$$
\begin{align*}
& F_{U(\ell:n, \tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta):m)}^{-1}(1-\beta') \\
&= F_{U(\ell:n)}^{-1} \circ F_{U(\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta):m)}^{-1}(1-\beta') && \text{by Eq. (46) in Lemma 28} \\
&\le F_{U(\ell:n)}^{-1} \left( \frac{\tilde{k}_{m,n}^{\text{cond}}(\ell, \alpha, \beta)}{m+1} + \sqrt{\frac{\log(1/\beta')}{2(m+2)}} \right) && \text{by Eq. (41) in Proposition 24} \\
&\le F_{U(\ell:n)}^{-1} \left( F_{U(\ell:n)}(1-\alpha) + \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(m+2)}} + \frac{1}{m+1} \right) && \text{by Eq. (22)} \\
&\le 1-\alpha + \frac{\varepsilon_m}{\sqrt{n+2}} \frac{\sqrt{2}}{g(\min\{x_n, 1-x_n - \varepsilon_m\})} && \tag{56}
\end{align*}
$$

by Theorem 25 with

$$x = x_n := F_{U(\ell:n)}(1-\alpha) \quad \text{and} \quad \varepsilon = \varepsilon_m := \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(m+2)}} + \frac{1}{m+1},$$

assuming also that $x_n + \varepsilon_m < 1$. Now, taking $\ell = \lceil (1-\alpha)n \rceil$ in Eq. (56), when $m \ge m'_{0,a}(\beta)$ and $n \ge \max\{n'_{0,a}(\alpha), n'_{0,b}(\alpha)\}$, we have $\ell \in [n]$, $\tilde{k}_{m,n}^{\text{cond}}(\lceil (1-\alpha)n \rceil, \alpha, \beta) \in [m]$ and $x_n \in [1/3, 2/3]$ by Eq. (55). Since some $m'_{0,b}(\beta, \beta')$ exists such that $\varepsilon_m \le 1/12$ as soon as $m \ge m'_{0,b}(\beta, \beta')$, we get that for $m \ge \max\{m'_{0,a}(\beta), m'_{0,b}(\beta, \beta')\}$ and $n \ge$
$\max\{n'_{0,a}(\alpha), n'_{0,b}(\alpha)\}$, we have $x_n + \epsilon_m < 1$ and $\min\{x_n, 1 - x_n - \epsilon_m\} \ge 1/4$, hence Eq. (56) leads to

$$
\begin{align*}
& F_{U_{([1-\alpha)n]:n, \tilde{k}_{m,n}^{\text{cond}}([1-\alpha)n], \alpha, \beta):m}}^{-1} (1 - \beta') \\
\le & 1 - \alpha + \left( \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(m+2)}} + \frac{1}{m+1} \right) \frac{1}{\sqrt{n+2}} \frac{\sqrt{2}}{g(1/4)} \\
(\text{if } m \ge 12) & \le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}},
\end{align*}
$$

where we assume at the last line that $m \ge 12$, hence $\sqrt{m+2}/(m+1) \le 0.9949267 - 1/\sqrt{2}$, and we use that $g(1/4) \ge G(1/4, 0.0316) \ge 0.1175$ hence $0.9949267 \times \frac{\sqrt{2}}{g(1/4)} \le 11.9749 \le 12$. This ends the proof, by taking $m'_0(\beta, \beta') = \max\{m'_{0,a}(\beta), m'_{0,b}(\beta, \beta'), 12\}$ and $n'_0(\alpha) = \max\{n'_{0,a}(\alpha), n'_{0,b}(\alpha)\}$. $\square$

We can now prove Theorem 17. We actually prove a more general result, about the following generalizations of Algorithms 3 and 4, respectively, where $\beta' \in (0, 1)$ is given:

$$
(\ell_A, k_A) := \underset{(\ell,k) \in [n] \times [m]}{\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 (57)
$$

$$
\ell_B := \underset{\ell \in [n]}{\operatorname{argmin}} \left\{ F_{U_{(\ell,n,\tilde{k}_{m,n}^{\text{cond}}(\ell,\alpha,\beta):m)}}^{-1} (1-\beta') \right\} \quad \text{and} \quad k_B := \tilde{k}_{m,n}^{\text{cond}}(\ell_B, \alpha, \beta). \tag{58}
$$

**Algorithm 3 – Proof of Eq. (26)** Let us first consider the generalization of Algorithm 3 defined by Eq. (57). Let $\ell_n := \lceil n(1-\alpha) \rceil$ and $k_n := \tilde{k}_{m,n}^{\text{cond}}(\ell_n, \alpha, \beta)$. By Lemma 30, when $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, we have $\ell_n \in [n]$ and $k_n \in [m]$, hence, $F_{U_{(\ell_n:n,k_n:m)}}^{-1}(\beta) \ge 1 - \alpha$ by Proposition 13 and Eq. (22). Therefore, by definition (57) of $(\ell_A, k_A)$,

$$
\begin{align*}
F_{U_{(\ell_A:n,k_A:m)}}^{-1} (1 - \beta') &\le F_{U_{(\ell_n:n,k_n:m)}}^{-1} (1 - \beta') \\
&\le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}
\end{align*}
$$

by Eq. (54) in Lemma 30. Finally, using Eq. (18) in Theorem 10—with $\beta = 0$ and $(\ell, k) = (\ell_A, k_A)$—, we get that if the scores $S_{i,j}$, $S$ are a.s. distinct, when $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, the following inequality holds true with probability $1 - \beta'$:

$$
1 - \alpha_{\ell_A, k_A}(\mathcal{D}) \le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}. \quad (59)
$$

Eq. (26) follows by taking $\beta' = \beta$ and defining $m'_0(\beta) := m'_0(\beta, \beta)$.

**Algorithm 4 – Proof of Eq. (27)** Similarly, for the generalization of Algorithm 4 defined by Eq. (58), we get that when $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, the following inequality holds true with probability $1 - \beta'$:

$$
1 - \alpha_{\ell_B, k_B}(\mathcal{D}) \le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}. \quad (60)
$$

Eq. (27) follows by taking $\beta' = \beta$, since Eq. (55) still holds true for such a sequence $\ell_n$ by [13, Section 10.2]. $\square$
$\max\{n'_{0,a}(\alpha), n'_{0,b}(\alpha)\}$, we have $x_n + \varepsilon_m < 1$ and $\min\{x_n, 1 - x_n - \varepsilon_m\} \ge 1/4$, hence Eq. (56) leads to

$$
\begin{align*}
& F_{U_{([1-\alpha)n]:n, \tilde{k}_{m,n}^{\text{cond}}([1-\alpha)n], \alpha, \beta):m}}^{-1} (1-\beta') \\
& \le 1 - \alpha + \left( \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(m+2)}} + \frac{1}{m+1} \right) \frac{1}{\sqrt{n+2}} \frac{\sqrt{2}}{g(1/4)} \\
& \stackrel{(\text{if } m \ge 12)}{\le} 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}},
\end{align*}
$$

where we assume at the last line that $m \ge 12$, hence $\sqrt{m+2}/(m+1) \le 0.9949267 - 1/\sqrt{2}$, and we use that $g(1/4) \ge G(1/4, 0.0316) \ge 0.1175$ hence $0.9949267 \times \frac{\sqrt{2}}{g(1/4)} \le 11.9749 \le 12$. This ends the proof, by taking $m'_0(\beta, \beta') = \max\{m'_{0,a}(\beta), m'_{0,b}(\beta, \beta'), 12\}$ and $n'_0(\alpha) = \max\{n'_{0,a}(\alpha), n'_{0,b}(\alpha)\}$. $\square$

We can now prove Theorem 17. We actually prove a more general result, about the following generalizations of Algorithms 3 and 4, respectively, where $\beta' \in (0, 1)$ is given:

$$
(\ell_A, k_A) := \underset{(\ell,k) \in [n]^2 \times [m]^2}{\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 (57)
$$

$$
\ell_B := \underset{\ell \in [n]}{\operatorname{argmin}} \left\{ F_{U_{(\ell,n,\tilde{k}_{m,n}^{\text{cond}}(\ell,\alpha,\beta):m)}}^{-1} (1-\beta') \right\} \quad \text{and} \quad k_B := \tilde{k}_{m,n}^{\text{cond}}(\ell_B, \alpha, \beta). \tag{58}
$$

**Algorithm 3 – Proof of Eq. (26)** Let us first consider the generalization of Algorithm 3 defined by Eq. (57). Let $\ell_n := \lceil n(1-\alpha) \rceil$ and $k_n := \tilde{k}_{m,n}^{\text{cond}}(\ell_n, \alpha, \beta)$. By Lemma 30, when $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, we have $\ell_n \in [n]$ and $k_n \in [m]$, hence, $F_{U_{(\ell_n:n,k_n:m)}}^{-1}(\beta) \ge 1-\alpha$ by Proposition 13 and Eq. (22). Therefore, by definition (57) of $(\ell_A, k_A)$,

$$
\begin{align*}
F_{U_{(\ell_A:n,k_A:m)}}^{-1} (1 - \beta') &\le F_{U_{(\ell_n:n,k_n:m)}}^{-1} (1 - \beta') \\
&\le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}
\end{align*}
$$

by Eq. (54) in Lemma 30. Finally, using Eq. (18) in Theorem 10—with $\beta = 0$ and $(\ell, k) = (\ell_A, k_A)$—, we get that if the scores $S_{i,j}$, $S$ are a.s. distinct, when $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, the following inequality holds true with probability $1 - \beta'$:

$$
1 - \alpha_{\ell_A, k_A}(\mathcal{D}) \le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}. \quad (59)
$$

Eq. (26) follows by taking $\beta' = \beta$ and defining $m'_0(\beta) := m'_0(\beta, \beta)$.

**Algorithm 4 – Proof of Eq. (27)** Similarly, for the generalization of Algorithm 4 defined by Eq. (58), we get that when $n \ge n'_0(\alpha)$ and $m \ge m'_0(\beta, \beta')$, the following inequality holds true with probability $1 - \beta'$:

$$
1 - \alpha_{\ell_B, k_B}(\mathcal{D}) \le 1 - \alpha + \frac{12 \max\{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}, 1\}}{\sqrt{(m+2)(n+2)}}. \quad (60)
$$

Eq. (27) follows by taking $\beta' = \beta$, since Eq. (55) still holds true for such a sequence $\ell_n$ by [13, Section 10.2]. $\square$
## Appendix F: Proofs of Section 5 (different $n_j$)

Before proving Theorems 19–20, notice that the proof of Lemma 27 straightforwardly generalizes to the case of the QQ estimator $S_{(\ell_1, \dots, \ell_m, k)}$ defined by Eq. (29). So, if $(U_{i,j})_{i \in [\ell_j], j \in [m]}$ denote independent standard uniform variables, we have

$$F_S(S_{(\ell_1, \dots, \ell_m, k)}) \stackrel{d}{=} F_S \circ F_S^{-1}(U_{(\ell_1, \dots, \ell_m, k)}) \geq U_{(\ell_1, \dots, \ell_m, k)}, \quad (61)$$

with equality when $F_S$ is continuous.

### F.1. Proof of Theorem 19

First, by Eq. (61), we have

$$\begin{aligned} \mathbb{P} (Y \in \hat{\mathcal{C}}_{\ell_1, \dots, \ell_m, k}(X)) &= \mathbb{P} (S \leq S_{(\ell_1, \dots, \ell_m, k)}) \\ &= \mathbb{E}[F_S(S_{(\ell_1, \dots, \ell_m, k)})] \geq \mathbb{E}[U_{(\ell_1, \dots, \ell_m, k)}] := M_{\ell_1, \dots, \ell_m, k}. \end{aligned}$$

It remains to prove the formula for $M_{\ell_1, \dots, \ell_m, k}$. The difference with the proof of Theorem 5 is that the variables $(\hat{Q}_{(\ell_j:n_j)}(S_j))_{1 \leq j \leq m}$ are not identically distributed, so $U_{(\ell_1, \dots, \ell_m, k)}$ is the k-th order statistics of a set of independent but not identically distributed (inid) random variables. Its cdf can still be computed as follows. By [7, Equation (16)], we have, for every $t \in [0, 1]$,

$$F_{U_{(\ell_1, \dots, \ell_m, k)}}(t) = \sum_{j=k}^{m} \sum_{a \in \mathcal{P}_j} F_{U_{(\ell_{a_1}:n_1)}}(t) \cdots F_{U_{(\ell_{a_j}:n_j)}}(t) \cdot [1 - F_{U_{(\ell_{a_{j+1}}:n_{j+1})}}(t)] \cdots [1 - F_{U_{(\ell_{a_m}:n_m)}}(t)],$$

where $\mathcal{P}_j$ denotes the set of permutations $(a_1, \dots, a_m)$ of $\{1, \dots, m\}$ for which $a_1 < a_2 < \dots < a_j$ and $a_{j+1} < a_{j+2} < \dots < a_m$. Then, using Eq. (65) and (67) in Appendix G.1 and rearranging the terms, we get that for every $t \in [0, 1]$,

$$F_{U_{(\ell_1, \dots, \ell_m, k)}}(t) = \sum_{j=k}^{m} \sum_{\mathcal{P}_j} \sum_{i_1=\ell_{a_1}}^{n_{a_1}} \cdots \sum_{i_j=\ell_{a_j}}^{n_{a_j}} \sum_{i_{j+1}=0}^{\ell_{a_{j+1}}-1} \cdots \sum_{i_m=0}^{\ell_{a_m}-1} \binom{n_{a_1}}{i_1} \cdots \binom{n_{a_m}}{i_m} t^{i_1+\cdots+i_m} (1-t)^{n_1+\cdots+n_m-(i_1+\cdots+i_m)}.$$

We finally obtain the result using that

$$\begin{aligned} M_{\ell_1, \dots, \ell_m, k} &= \mathbb{E}[U_{(\ell_1, \dots, \ell_m, k)}] = \int_0^1 [1 - F_{U_{(\ell_1, \dots, \ell_m, k)}}(t)] dt \\ \text{and} \quad &\int_0^1 t^{i_1+\cdots+i_m} (1-t)^{n_1+\cdots+n_m-(i_1+\cdots+i_m)} dt \\ &= B(i_1 + \cdots + i_m + 1, n_1 + \cdots + n_m - (i_1 + \cdots + i_m) + 1) \\ &= (n_1 + \cdots + n_m + 1)^{-1} \binom{n_1 + \cdots + n_m}{i_1 + \cdots + i_m}^{-1}, \end{aligned}$$

using a property of the Beta function already used in Appendix C.1. □
Appendix F: Proofs of Section 5 (different $n_j$)

Before proving Theorems 19–20, notice that the proof of Lemma 27 straightforwardly generalizes to the case of the QQ estimator $S_{(\ell_1, \dots, \ell_m, k)}$ defined by Eq. (29). So, if $(U_{i,j})_{i \in [\ell_j], j \in [m]}$ denote independent standard uniform variables, we have

$$F_S(S_{(\ell_1, \dots, \ell_m, k)}) \stackrel{d}{=} F_S \circ F_S^{-1}(U_{(\ell_1, \dots, \ell_m, k)}) \ge U_{(\ell_1, \dots, \ell_m, k)}, \quad (61)$$

with equality when $F_S$ is continuous.

F.1. Proof of Theorem 19

First, by Eq. (61), we have

$$ \begin{aligned} \mathbb{P} (Y \in \hat{\mathcal{C}}_{\ell_1, \dots, \ell_m, k}(X)) &= \mathbb{P} (S \le S_{(\ell_1, \dots, \ell_m, k)}) \\ &= \mathbb{E}[F_S(S_{(\ell_1, \dots, \ell_m, k)})] \ge \mathbb{E}[U_{(\ell_1, \dots, \ell_m, k)}] := M_{\ell_1, \dots, \ell_m, k}. \end{aligned} $$

It remains to prove the formula for $M_{\ell_1, \dots, \ell_m, k}$. The difference with the proof of Theorem 5 is that the variables $(\hat{Q}_{(\ell_j:n_j)}(S_j))_{1 \le j \le m}$ are not identically distributed, so $U_{(\ell_1, \dots, \ell_m, k)}$ is the k-th order statistics of a set of independent but not identically distributed (inid) random variables. Its cdf can still be computed as follows. By [7, Equation (16)], we have, for every $t \in [0, 1]$,

$$ F_{U_{(\ell_1, \dots, \ell_m, k)}}(t) = \sum_{j=k}^{m} \sum_{a \in \mathcal{P}_j} F_{U_{(\ell_{a_1}:n_1)}}(t) \cdots F_{U_{(\ell_{a_j}:n_j)}}(t) \cdot [1 - F_{U_{(\ell_{a_{j+1}}:n_{j+1})}}(t)] \cdots [1 - F_{U_{(\ell_{a_m}:n_m)}}(t)], $$

where $\mathcal{P}_j$ denotes the set of permutations $(a_1, \dots, a_m)$ of $\{1, \dots, m\}$ for which $a_1 < a_2 < \dots < a_j$ and $a_{j+1} < a_{j+2} < \dots < a_m$. Then, using Eq. (65) and (67) in Appendix G.1 and rearranging the terms, we get that for every $t \in [0, 1]$,

$$ F_{U_{(\ell_1, \dots, \ell_m, k)}}(t) = \sum_{j=k}^{m} \sum_{\mathcal{P}_j} \sum_{i_1=\ell_{a_1}}^{n_{a_1}} \cdots \sum_{i_j=\ell_{a_j}}^{n_{a_j}} \sum_{i_{j+1}=0}^{\ell_{a_{j+1}}-1} \cdots \sum_{i_m=0}^{\ell_{a_m}-1} \binom{n_{a_1}}{i_1} \cdots \binom{n_{a_m}}{i_m} t^{i_1+\cdots+i_m} (1-t)^{n_1+\cdots+n_m-(i_1+\cdots+i_m)}. $$

We finally obtain the result using that

$$ \begin{aligned} M_{\ell_1, \dots, \ell_m, k} &= \mathbb{E}[U_{(\ell_1, \dots, \ell_m, k)}] = \int_0^1 [1 - F_{U_{(\ell_1, \dots, \ell_m, k)}}(t)] \mathrm{d}t \\ \text{and} \quad & \int_0^1 t^{i_1+\cdots+i_m} (1-t)^{n_1+\cdots+n_m-(i_1+\cdots+i_m)} \mathrm{d}t \\ &= B(i_1 + \cdots + i_m + 1, n_1 + \cdots + n_m - (i_1 + \cdots + i_m) + 1) \\ &= (n_1 + \cdots + n_m + 1)^{-1} \binom{n_1 + \cdots + n_m}{i_1 + \cdots + i_m}^{-1}, \end{aligned} $$

using a property of the Beta function already used in Appendix C.1. □
## F.2. Proof of Theorem 20

By the definition (30) of $\hat{C}_{\ell_1, \dots, \ell_m, k}$ and Eq. (61), we have

$$ \mathbb{P}(1 - \alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D}) \ge 1 - \alpha) = \mathbb{P}(F_S(S_{(\ell_1, \dots, \ell_m, k)}) \ge 1 - \alpha) \\ \ge \mathbb{P}(U_{(\ell_1, \dots, \ell_m, k)} \ge 1 - \alpha), \qquad (62) $$

with equality when $F_S$ is continuous. By definition of $U_{(\ell_1, \dots, \ell_m, k)} = \hat{Q}_{(\ell_j:n_j)}((U_{(\ell_j:n_j)})_{1\le j \le m})$, we have

$$ \mathbb{P}(U_{(\ell_1, \dots, \ell_m, k)} \ge 1 - \alpha) = \mathbb{P}\left(\sum_{j=1}^{m} 1_{\{U_{(\ell_j:n_j)} \le 1-\alpha\}} \le k - 1\right). $$

Furthermore, $\sum_{j=1}^{m} 1_{\{U_{(\ell_j:n_j)} \le 1-\alpha\}}$ is a sum of $m$ independent Bernoulli variables with respective parameters $p_j = \mathbb{P}(U_{(\ell_j:n_j)} \le 1 - \alpha) = F_{U_{(\ell_j:n_j)}}(1 - \alpha)$. Therefore, it follows a Poisson-Binomial distribution of parameters $(p_1, \dots, p_m)$. Using Eq. (62), we obtain Eq. (33). $\square$

# Appendix G: Classical results about order statistics distribution

We recall in this section some useful well-known results about order statistics [13]. Throughout this section, $U_1, \dots, U_N, \dots$ denote a sequence of independent standard uniform variables, and $Z_1, \dots, Z_N, \dots$ a sequence of i.i.d. random variables with common cdf $F_Z$. For any integers $1 \le r \le N$, $U_{(r:N)} = \hat{Q}_{(r)}(U_1, \dots, U_N)$ and $Z_{(r:N)} = \hat{Q}_{(r)}(Z_1, \dots, Z_N)$ denote the corresponding $r$-th order statistics.

## G.1. Exact distribution

For every $r \in [N]$, the cdf of $Z_{(r:N)}$ is given by

$$ \forall t \in \mathbb{R}, \qquad F_{Z_{(r:N)}}(t) = \sum_{i=r}^{N} \binom{N}{i} F_Z(t)^i [1 - F_Z(t)]^{N-i}. \qquad (63) $$

If we further assume that $F_Z$ is continuous with corresponding probability density function (pdf) $f_Z = F'_Z$, then, for every $r \in [N]$, the pdf of $Z_{(r:N)}$ is given by

$$ \forall t \in \mathbb{R}, \qquad f_{Z_{(r:N)}}(t) = \frac{N!}{(r-1)!(N-r)!} F_Z(t)^{r-1} [1 - F_Z(t)]^{N-r} f_Z(t). \qquad (64) $$

In the case of uniform order statistics, $U_{(r:N)}$ follows a Beta($r, N - r + 1$) distribution and its cdf $F_{U_{(r:N)}}$ and pdf $f_{U_{(r:N)}}$ are respectively given by

$$ \forall t \in [0, 1], \quad F_{U_{(r:N)}}(t) = \sum_{i=r}^{N} \binom{N}{i} t^i (1-t)^{N-i} \quad \text{and} \quad f_{U_{(r:N)}}(t) = \frac{t^{r-1}(1-t)^{N-r}}{B(r, N-r+1)} \qquad (65) $$

$$ \text{where } B: (a, b) \in (0, +\infty)^2 \mapsto \int_0^1 t^{a-1}(1-t)^{b-1}dt $$
## F.2. Proof of Theorem 20

By the definition (30) of $\hat{C}_{\ell_1, \dots, \ell_m, k}$ and Eq. (61), we have

$$ \begin{aligned} \mathbb{P}(1 - \alpha_{\ell_1, \dots, \ell_m, k}(\mathcal{D}) \ge 1 - \alpha) &= \mathbb{P}(F_S(S_{(\ell_1, \dots, \ell_m, k)}) \ge 1 - \alpha) \\ &\ge \mathbb{P}(U_{(\ell_1, \dots, \ell_m, k)} \ge 1 - \alpha), \end{aligned} \quad (62) $$

with equality when $F_S$ is continuous. By definition of $U_{(\ell_1, \dots, \ell_m, k)} = \hat{Q}_{(\ell_j:n_j)}((U_{(\ell_j:n_j)})_{1\le j \le m})$, we have

$$ \mathbb{P}(U_{(\ell_1, \dots, \ell_m, k)} \ge 1 - \alpha) = \mathbb{P}\left(\sum_{j=1}^{m} 1_{\{U_{(\ell_j:n_j)} \le 1-\alpha\}} \le k - 1\right). $$

Furthermore, $\sum_{j=1}^{m} 1_{\{U_{(\ell_j:n_j)} \le 1-\alpha\}}$ is a sum of $m$ independent Bernoulli variables with respective parameters $p_j = \mathbb{P}(U_{(\ell_j:n_j)} \le 1 - \alpha) = F_{U_{(\ell_j:n_j)}}(1 - \alpha)$. Therefore, it follows a Poisson-Binomial distribution of parameters $(p_1, \dots, p_m)$. Using Eq. (62), we obtain Eq. (33). □

# Appendix G: Classical results about order statistics distribution

We recall in this section some useful well-known results about order statistics [13]. Throughout this section, $U_1, \dots, U_N, \dots$ denote a sequence of independent standard uniform variables, and $Z_1, \dots, Z_N, \dots$ a sequence of i.i.d. random variables with common cdf $F_Z$. For any integers $1 \le r \le N$, $U_{(r:N)} = \hat{Q}_{(r)}(U_1, \dots, U_N)$ and $Z_{(r:N)} = \hat{Q}_{(r)}(Z_1, \dots, Z_N)$ denote the corresponding $r$-th order statistics.

## G.1. Exact distribution

For every $r \in \llbracket N \rrbracket$, the cdf of $Z_{(r:N)}$ is given by

$$ \forall t \in \mathbb{R}, \quad F_{Z_{(r:N)}}(t) = \sum_{i=r}^{N} \binom{N}{i} F_Z(t)^i [1 - F_Z(t)]^{N-i}. \quad (63) $$

If we further assume that $F_Z$ is continuous with corresponding probability density function (pdf) $f_Z = F'_Z$, then, for every $r \in \llbracket N \rrbracket$, the pdf of $Z_{(r:N)}$ is given by

$$ \forall t \in \mathbb{R}, \quad f_{Z_{(r:N)}}(t) = \frac{N!}{(r-1)!(N-r)!} F_Z(t)^{r-1} [1 - F_Z(t)]^{N-r} f_Z(t). \quad (64) $$

In the case of uniform order statistics, $U_{(r:N)}$ follows a Beta($r, N - r + 1$) distribution and its cdf $F_{U_{(r:N)}}$ and pdf $f_{U_{(r:N)}}$ are respectively given by

$$ \forall t \in [0, 1], \quad F_{U_{(r:N)}}(t) = \sum_{i=r}^{N} \binom{N}{i} t^i (1-t)^{N-i} \quad \text{and} \quad f_{U_{(r:N)}}(t) = \frac{t^{r-1}(1-t)^{N-r}}{B(r, N-r+1)} \quad (65) $$

$$ \text{where } B: (a, b) \in (0, +\infty)^2 \mapsto \int_0^1 t^{a-1}(1-t)^{b-1}dt $$
denotes the Beta function [59]. In particular, for every $N \ge 1$, we have

$$ \forall t \in [0, 1], \quad F_{U_{(N:N)}}(t) = t^N \quad \text{and} \quad F_{U_{(N:N)}}^{-1}(t) = t^{1/N}. \qquad (66) $$

Since $\sum_{i=0}^{N} \binom{N}{i} t^i (1-t)^{N-i} = 1$, Eq. (65) also implies that

$$ \forall t \in [0, 1], \quad 1 - F_{U_{(r:N)}}(t) = \sum_{i=0}^{r-1} \binom{N}{i} t^i (1-t)^{N-i}, \qquad (67) $$

$$ \text{hence} \quad F_{U_{(1:N)}}(t) = 1 - (1-t)^N. \qquad (68) $$

In addition, closed-form formulas are available for the expectation and variance of uniform order statistics:

$$ \mathbb{E}[U_{(r:N)}] = \frac{r}{N+1} \quad \text{and} \quad \text{Var}(U_{(r:N)}) = \frac{r(N-r+1)}{(N+1)^2(N+2)}. \qquad (69) $$

## G.2. Asymptotics

Central order statistics are known to be asymptotically normal. More precisely, following [18, 33], we have the following result.

**Theorem 31** (Asymptotic normality of central uniform order statistics [18, 33]). Let $p \in (0, 1)$, $\gamma \in \mathbb{R}$ and $(\ell_N)_{N \ge 1}$ be a sequence such that $\ell_N \in [N]$ for every $N \ge 1$ and $\ell_N = pN + \gamma\sqrt{N} + o(\sqrt{N})$ when $N \to +\infty$. Then, we have

$$ \sqrt{N}(U_{(\ell_N:N)} - p) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(\gamma, p(1-p)). \qquad (70) $$

In particular, Theorem 31 implies that

$$ \sqrt{N}(U_{([pN]:N)} - p) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(0, p(1-p)). \qquad (71) $$

By Lemma 23, Eq. (70)–(71) imply that when $F_Z$ is continuous, under the assumptions of Theorem 31,

$$ \sqrt{N}(F_Z(Z_{(\ell_N:N)} - p)) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(\gamma, p(1-p)) \qquad (72) $$

$$ \text{and} \quad \sqrt{N}(F_Z(Z_{([pN]:N)} - p)) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(0, p(1-p)). \qquad (73) $$

# Appendix H: Proofs of Appendix B

## H.1. Proof of Lemma 23

First, for every $i \in [N]$, let us define $\tilde{Z}_i := F_Z^{-1}(U_i)$, so that $\tilde{Z}_1, \dots, \tilde{Z}_N$ are independent and identically distributed, with cdf $F_Z$. Therefore, $(Z_1, \dots, Z_N) \stackrel{d}{=} (\tilde{Z}_1, \dots, \tilde{Z}_N)$, hence

$$ Z_{(r)} \stackrel{d}{=} \tilde{Z}_{(r)}. \qquad (74) $$

Second, remark that for any integers $1 \le r \le N$, any $S \in \mathbb{R}^N$ and any nondecreasing function $h: \mathbb{R} \to \mathbb{R}$, we have

$$ h(\hat{Q}_{(r)}(S)) = \hat{Q}_{(r)}(h(S)) \quad \text{where} \quad h(S) := (h(S_i))_{i \in [N]} \qquad (75) $$
denotes the Beta function [59]. In particular, for every $N \ge 1$, we have

$$ \forall t \in [0, 1], \quad F_{U_{(N:N)}}(t) = t^N \quad \text{and} \quad F_{U_{(N:N)}}^{-1}(t) = t^{1/N}. \qquad (66) $$

Since $\sum_{i=0}^{N} \binom{N}{i} t^i (1-t)^{N-i} = 1$, Eq. (65) also implies that

$$ \forall t \in [0, 1], \quad 1 - F_{U_{(r:N)}}(t) = \sum_{i=0}^{r-1} \binom{N}{i} t^i (1-t)^{N-i}, \qquad (67) $$

$$ \text{hence} \quad F_{U_{(1:N)}}(t) = 1 - (1-t)^N. \qquad (68) $$

In addition, closed-form formulas are available for the expectation and variance of uniform order statistics:

$$ \mathbb{E}[U_{(r:N)}] = \frac{r}{N+1} \quad \text{and} \quad \mathrm{Var}(U_{(r:N)}) = \frac{r(N-r+1)}{(N+1)^2(N+2)}. \qquad (69) $$

## G.2. Asymptotics

Central order statistics are known to be asymptotically normal. More precisely, following [18, 33], we have the following result.

**Theorem 31** (Asymptotic normality of central uniform order statistics [18, 33]). Let $p \in (0, 1)$, $\gamma \in \mathbb{R}$ and $(\ell_N)_{N \ge 1}$ be a sequence such that $\ell_N \in [N]$ for every $N \ge 1$ and $\ell_N = pN + \gamma\sqrt{N} + o(\sqrt{N})$ when $N \to +\infty$. Then, we have

$$ \sqrt{N}(U_{(\ell_N:N)} - p) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(\gamma, p(1-p)). \qquad (70) $$

In particular, Theorem 31 implies that

$$ \sqrt{N}(U_{([pN]:N)} - p) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(0, p(1-p)). \qquad (71) $$

By Lemma 23, Eq. (70)–(71) imply that when $F_Z$ is continuous, under the assumptions of Theorem 31,

$$ \sqrt{N}(F_Z(Z_{(\ell_N:N)} - p)) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(\gamma, p(1-p)) \qquad (72) $$

$$ \text{and} \quad \sqrt{N}(F_Z(Z_{([pN]:N)} - p)) \xrightarrow[N \to +\infty]{\mathcal{L}} \mathcal{N}(0, p(1-p)). \qquad (73) $$

# Appendix H: Proofs of Appendix B

## H.1. Proof of Lemma 23

First, for every $i \in [N]$, let us define $\tilde{Z}_i := F_Z^{-1}(U_i)$, so that $\tilde{Z}_1, \dots, \tilde{Z}_N$ are independent and identically distributed, with cdf $F_Z$. Therefore, $(Z_1, \dots, Z_N) \stackrel{d}{=} (\tilde{Z}_1, \dots, \tilde{Z}_N)$, hence

$$ Z_{(r)} \stackrel{d}{=} \tilde{Z}_{(r)}. \qquad (74) $$

Second, remark that for any integers $1 \le r \le N$, any $S \in \mathbb{R}^N$ and any nondecreasing function $h: \mathbb{R} \to \mathbb{R}$, we have

$$ h(\hat{Q}_{(r)}(S)) = \hat{Q}_{(r)}(h(S)) \quad \text{where} \quad h(S) := (h(S_i))_{i \in [N]} \qquad (75) $$
and $\hat{Q}_{(r)}$ is defined by Eq. (4) in Section 2.1.

Indeed, let $\sigma \in \mathcal{S}$ be some permutation of $\llbracket N \rrbracket$ such that $S_{\sigma(1)} \le \dots \le S_{\sigma(N)}$, hence $\hat{Q}_{(r)}(S) = S_{\sigma(r)}$. Then, $h(S_{\sigma(1)}) \le \dots \le h(S_{\sigma(N)})$ since $h$ is nondecreasing, and we get that

$$ \hat{Q}_{(r)}(h(S)) = h(S_{\sigma(r)}) = h(\hat{Q}_{(r)}(S)). $$

From Eq. (74) and (75), since $F_Z^{-1}$ is nondecreasing, we obtain that

$$ \begin{aligned} F_Z(Z_{(r)}) &\stackrel{d}{=} F_Z(\tilde{Z}_{(r)}) = F_Z(\hat{Q}_{(r)}(F_Z^{-1}(U_1, \dots, U_N))) = F_Z \circ F_Z^{-1}(\hat{Q}_{(r)}(U_1, \dots, U_N)) \\ &= F_Z \circ F_Z^{-1}(U_{(r)}). \end{aligned} $$

Using Eq. (36), this proves Eq. (37) in the general case —Eq. (38) follows directly—, and Eq. (39) when $F_Z$ is continuous. The distribution of the uniform order statistic $U_{(r)}$ is well known, see for instance [13] or Appendix G.1. $\square$

**Remark 32.** In the case of a general cdf $F_Z$, another consequence of Lemma 23 is that, for every $a, b \in \mathbb{R}$ such that $a \le b$,

$$ \mathbb{P}(U_{(r)} \le b) \le \mathbb{P}(F_Z(Z_{(r)}) \le F_Z \circ F_Z^{-1}(b)) \quad (76) $$

$$ \text{and} \quad \mathbb{P}(a \le U_{(r)} \le b) \le \mathbb{P}(a \le F_Z(Z_{(r)}) \le F_Z \circ F_Z^{-1}(b)). \quad (77) $$

*Proof.* Since $F_Z \circ F_Z^{-1}$ is nondecreasing,

$$ U_{(r)} \le b \quad \text{implies that} \quad F_Z \circ F_Z^{-1}(U_{(r)}) \le F_Z \circ F_Z^{-1}(b), \quad (78) $$

hence Eq. (76) thanks to Eq. (37). Since $F_Z \circ F_Z^{-1}(U_{(r)}) \ge U_{(r)}$ by Eq. (36), Eq. (78) also shows that

$$ a \le U_{(r)} \le b \quad \text{implies that} \quad a \le F_Z \circ F_Z^{-1}(U_{(r)}) \le F_Z \circ F_Z^{-1}(b), $$

hence Eq. (77) thanks to Eq. (37). $\square$

## H.2. Proof of Proposition 24

We start by recalling some concentration result about the Beta distribution [42, Theorem 1].

**Theorem 33** (taken from [42]). For any $a, b > 0$, the Beta distribution Beta($a, b$) is $\omega$-sub-Gaussian, with $\omega = \frac{1}{4(a+b+1)}$. This implies that, if $Z \sim \text{Beta}(a, b)$, for any $\varepsilon > 0$,

$$ \max \left\{ \mathbb{P} \left( Z \ge \frac{a}{a+b} + \varepsilon \right), \mathbb{P} \left( Z \le \frac{a}{a+b} - \varepsilon \right) \right\} \le e^{-2(a+b+1)\varepsilon^2}. $$

Note that Theorem 33 does not provide the “best” concentration inequality for the Beta distribution. Indeed, although the bound is sharp for the symmetric case $a = b$, when the Beta distribution is skewed, Theorem 33 has been improved with the Bernstein-type bound of [57]. Nevertheless, it is sufficient for our needs and yields simpler formulas.

We can now prove Proposition 24. Since $U_{(r:N)}$ follows a Beta($r, N-r+1$) distribution, Theorem 33 with $a = r, b = N-r+1$ and $\varepsilon = \sqrt{\frac{\log(1/\delta)}{2(N+2)}}$ shows that

$$ F_{U_{(r:N)}} \left( \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) = \mathbb{P} \left( U_{(r:N)} \le \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \le \delta, \quad (79) $$
and $\hat{Q}_{(r)}$ is defined by Eq. (4) in Section 2.1.

Indeed, let $\sigma \in \mathcal{S}$ be some permutation of $\llbracket N \rrbracket$ such that $S_{\sigma(1)} \le \cdots \le S_{\sigma(N)}$, hence $\hat{Q}_{(r)}(S) = S_{\sigma(r)}$. Then, $h(S_{\sigma(1)}) \le \cdots \le h(S_{\sigma(N)})$ since $h$ is nondecreasing, and we get that

$$ \hat{Q}_{(r)}(h(S)) = h(S_{\sigma(r)}) = h(\hat{Q}_{(r)}(S)). $$

From Eq. (74) and (75), since $F_Z^{-1}$ is nondecreasing, we obtain that

$$ \begin{aligned} F_Z(Z_{(r)}) &\stackrel{d}{=} F_Z(\tilde{Z}_{(r)}) = F_Z(\hat{Q}_{(r)}(F_Z^{-1}(U_1, \dots, U_N))) = F_Z \circ F_Z^{-1}(\hat{Q}_{(r)}(U_1, \dots, U_N)) \\ &= F_Z \circ F_Z^{-1}(U_{(r)}). \end{aligned} $$

Using Eq. (36), this proves Eq. (37) in the general case —Eq. (38) follows directly—, and Eq. (39) when $F_Z$ is continuous. The distribution of the uniform order statistic $U_{(r)}$ is well known, see for instance [13] or Appendix G.1. $\square$

**Remark 32.** In the case of a general cdf $F_Z$, another consequence of Lemma 23 is that, for every $a, b \in \mathbb{R}$ such that $a \le b$,

$$ \mathbb{P}(U_{(r)} \le b) \le \mathbb{P}(F_Z(Z_{(r)}) \le F_Z \circ F_Z^{-1}(b)) \quad (76) $$

$$ \text{and} \quad \mathbb{P}(a \le U_{(r)} \le b) \le \mathbb{P}(a \le F_Z(Z_{(r)}) \le F_Z \circ F_Z^{-1}(b)). \quad (77) $$

*Proof.* Since $F_Z \circ F_Z^{-1}$ is nondecreasing,

$$ U_{(r)} \le b \quad \text{implies that} \quad F_Z \circ F_Z^{-1}(U_{(r)}) \le F_Z \circ F_Z^{-1}(b), \quad (78) $$

hence Eq. (76) thanks to Eq. (37). Since $F_Z \circ F_Z^{-1}(U_{(r)}) \ge U_{(r)}$ by Eq. (36), Eq. (78) also shows that

$$ a \le U_{(r)} \le b \quad \text{implies that} \quad a \le F_Z \circ F_Z^{-1}(U_{(r)}) \le F_Z \circ F_Z^{-1}(b), $$

hence Eq. (77) thanks to Eq. (37). $\square$

## H.2. Proof of Proposition 24

We start by recalling some concentration result about the Beta distribution [42, Theorem 1].

**Theorem 33** (taken from [42]). For any $a, b > 0$, the Beta distribution Beta($a, b$) is $\omega$-sub-Gaussian, with $\omega = \frac{1}{4(a+b+1)}$. This implies that, if $Z \sim \text{Beta}(a, b)$, for any $\varepsilon > 0$,

$$ \max \left\{ \mathbb{P} \left( Z \ge \frac{a}{a+b} + \varepsilon \right), \mathbb{P} \left( Z \le \frac{a}{a+b} - \varepsilon \right) \right\} \le e^{-2(a+b+1)\varepsilon^2}. $$

Note that Theorem 33 does not provide the “best” concentration inequality for the Beta distribution. Indeed, although the bound is sharp for the symmetric case $a = b$, when the Beta distribution is skewed, Theorem 33 has been improved with the Bernstein-type bound of [57]. Nevertheless, it is sufficient for our needs and yields simpler formulas.

We can now prove Proposition 24. Since $U_{(r:N)}$ follows a Beta($r, N-r+1$) distribution, Theorem 33 with $a = r, b = N-r+1$ and $\varepsilon = \sqrt{\frac{\log(1/\delta)}{2(N+2)}}$ shows that

$$ F_{U_{(r:N)}} \left( \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) = \mathbb{P} \left( U_{(r:N)} \le \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \le \delta, \quad (79) $$
hence Eq. (40). Similarly,

$$F_{U_{(r:N)}} \left( \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) = 1 - \mathbb{P} \left( U_{(r:N)} \ge \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta \quad (80)$$

by Theorem 33, hence Eq. (41). □

### H.3. Deviation inequalities for general order statistics

The combination of Theorem 33 with Lemma 23 yields the following deviation inequalities, which are not directly useful in our study of one-shot FL CP algorithms, but can be of interest in other contexts such as the non-asymptotic analysis of (centralized) split CP —see Appendix I.1.

**Corollary 34.** For any $N \ge 1$, let $Z_1, \dots, Z_N$ be independent and identically distributed real-valued random variables with common cdf $F_Z$. Then, for any $\delta > 0$ and $r \in [N]$, the following inequality holds true:

$$\mathbb{P} \left( F_Z(Z_{(r)}) \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta. \quad (81)$$

Moreover, if $F_Z$ is continuous, we also have

$$\mathbb{P} \left( F_Z(Z_{(r)}) \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta \quad (82)$$

$$\text{and} \quad \mathbb{P} \left( \left| F_Z(Z_{(r)}) - \frac{r}{N+1} \right| \le \sqrt{\frac{\log(2/\delta)}{2(N+2)}} \right) \ge 1 - \delta. \quad (83)$$

*Proof.* By Eq. (38) in Lemma 23 with $a = \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}}$ (and using its notation), we have

$$\begin{aligned} \mathbb{P} \left( F_Z(Z_{(r)}) \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \\ \ge \mathbb{P} \left( U_{(r:N)} \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta \end{aligned} \quad (84)$$

by Eq. (79) in the proof of Proposition 24, hence Eq. (81). If we also assume that $F_Z$ is continuous, combining Eq. (39) in Lemma 23 and Eq. (80) in the proof of Proposition 24 shows that

$$\begin{aligned} \mathbb{P} \left( F_Z(Z_{(r:N)}) \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) &= \mathbb{P} \left( U_{(r:N)} \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \\ &= F_{U_{(r:N)}} \left( \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta, \end{aligned}$$

hence Eq. (82). Finally, replacing $\delta$ by $\delta/2$ in Eq. (81)–(82) implies Eq. (83) by the union bound. □
hence Eq. (40). Similarly,

$$F_{U_{(r:N)}} \left( \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) = 1 - \mathbb{P} \left( U_{(r:N)} \ge \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta \quad (80)$$

by Theorem 33, hence Eq. (41). □

### H.3. Deviation inequalities for general order statistics

The combination of Theorem 33 with Lemma 23 yields the following deviation inequalities, which are not directly useful in our study of one-shot FL CP algorithms, but can be of interest in other contexts such as the non-asymptotic analysis of (centralized) split CP —see Appendix I.1.

**Corollary 34.** For any $N \ge 1$, let $Z_1, \dots, Z_N$ be independent and identically distributed real-valued random variables with common cdf $F_Z$. Then, for any $\delta > 0$ and $r \in [N]$, the following inequality holds true:

$$\mathbb{P} \left( F_Z(Z_{(r)}) \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta. \quad (81)$$

Moreover, if $F_Z$ is continuous, we also have

$$\mathbb{P} \left( F_Z(Z_{(r)}) \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta \quad (82)$$

$$\text{and} \quad \mathbb{P} \left( \left| F_Z(Z_{(r)}) - \frac{r}{N+1} \right| \le \sqrt{\frac{\log(2/\delta)}{2(N+2)}} \right) \ge 1 - \delta. \quad (83)$$

*Proof.* By Eq. (38) in Lemma 23 with $a = \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}}$ (and using its notation), we have

$$\begin{aligned} \mathbb{P} \left( F_Z(Z_{(r)}) \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \\ \ge \mathbb{P} \left( U_{(r:N)} \ge \frac{r}{N+1} - \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta \end{aligned} \quad (84)$$

by Eq. (79) in the proof of Proposition 24, hence Eq. (81). If we also assume that $F_Z$ is continuous, combining Eq. (39) in Lemma 23 and Eq. (80) in the proof of Proposition 24 shows that

$$\begin{aligned} \mathbb{P} \left( F_Z(Z_{(r:N)}) \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) &= \mathbb{P} \left( U_{(r:N)} \le \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \\ &= F_{U_{(r:N)}} \left( \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \ge 1 - \delta, \end{aligned}$$

hence Eq. (82). Finally, replacing $\delta$ by $\delta/2$ in Eq. (81)–(82) implies Eq. (83) by the union bound. □
**Remark 35.** For a general cdf $F_Z$, instead of Eq. (82), we have

$$ \mathbb{P} \left( F_Z(Z_{(r)}) \le F_Z \circ F_Z^{-1} \left( \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \right) \ge 1 - \delta. \quad (85) $$

*Proof.* Combine Eq. (76) with $b = \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}}$ and Eq. (80). $\square$

**Remark 36.** Eq. (73) in Section G.2 shows that for any $p \in (0, 1)$, $F_Z(Z_{([pN])})$ converges towards $p$ at the rate $\sqrt{N}$. Therefore, the order of magnitude $1/\sqrt{N}$ of the deviations in Corollary 34 is optimal (at least, asymptotically).

### H.4. Proof of Theorem 25

We proceed in four steps.

**Step 1: mean value theorem.** Since $F_{U(\ell:n)}^{-1}$ is continuous on $[x, x+\varepsilon]$ and differentiable on $(x, x+\varepsilon)$ —it is even $C^\infty$ on $(0, 1)$—, by the mean-value theorem, some $c \in (x, x+\varepsilon)$ exists such that

$$ \begin{aligned} F_{U(\ell:n)}^{-1}(x+\varepsilon) - F_{U(\ell:n)}^{-1}(x) = (F_{U(\ell:n)}^{-1})'(c) \times \varepsilon &= \frac{\varepsilon}{f_{U(\ell:n)}(F_{U(\ell:n)}^{-1}(c))} \\ &\le \frac{\varepsilon}{\inf[F_{U(\ell:n)}^{-1}(x), F_{U(\ell:n)}^{-1}(x+\varepsilon)] f_{U(\ell:n)}}. \end{aligned} \quad (86) $$

Therefore, it remains to get a uniform lower bound on the density $f_{U(\ell:n)}$.

**Step 2: density lower bound with the inverse cdf $F_{U(\ell:n)}^{-1}$**. Since $f_{U(\ell:n)}$ is uni-modal [6], a straightforward proof by exhaustion (depending on the relative position of argmax $f_{U(\ell:n)}$ and $[F_{U(\ell:n)}^{-1}(x), F_{U(\ell:n)}^{-1}(x+\varepsilon)]$) shows that

$$ \inf_{[F_{U(\ell:n)}^{-1}(x), F_{U(\ell:n)}^{-1}(x+\varepsilon)]} f_{U(\ell:n)} \ge \min \left\{ \sup_{[0, F_{U(\ell:n)}^{-1}(x)]} f_{U(\ell:n)}, \sup_{[F_{U(\ell:n)}^{-1}(x+\varepsilon), 1]} f_{U(\ell:n)} \right\}. \quad (87) $$

Let us consider separately the two terms of the right-hand side of Eq. (87). On the one hand, for every $\delta \in (0, x)$,

$$ \begin{aligned} \sup_{[0, F_{U(\ell:n)}^{-1}(x)]} f_{U(\ell:n)} &\ge \frac{1}{F_{U(\ell:n)}^{-1}(x) - F_{U(\ell:n)}^{-1}(\delta)} \int_{F_{U(\ell:n)}^{-1}(\delta)}^{F_{U(\ell:n)}^{-1}(x)} f_{U(\ell:n)}(t)dt \\ &= \frac{F_{U(\ell:n)}(x) - F_{U(\ell:n)}(\delta)}{F_{U(\ell:n)}^{-1}(x) - F_{U(\ell:n)}^{-1}(\delta)} \\ &= \frac{x - \delta}{F_{U(\ell:n)}^{-1}(x) - F_{U(\ell:n)}^{-1}(\delta)}. \end{aligned} \quad (88) $$

On the other hand, similarly, for every $\delta' \in (0, 1 - x - \varepsilon)$,

$$ \begin{aligned} \sup_{[F_{U(\ell:n)}^{-1}(x+\varepsilon), 1]} f_{U(\ell:n)} &\ge \frac{1}{F_{U(\ell:n)}^{-1}(1-\delta') - F_{U(\ell:n)}^{-1}(x+\varepsilon)} \int_{F_{U(\ell:n)}^{-1}(x+\varepsilon)}^{F_{U(\ell:n)}^{-1}(1-\delta')} f_{U(\ell:n)}(t)dt \\ &= \frac{(1-\delta') - (x+\varepsilon)}{F_{U(\ell:n)}^{-1}(1-\delta') - F_{U(\ell:n)}^{-1}(x+\varepsilon)}. \end{aligned} \quad (89) $$
**Remark 35.** For a general cdf $F_Z$, instead of Eq. (82), we have

$$ \mathbb{P} \left( F_Z(Z_{(r)}) \le F_Z \circ F_Z^{-1} \left( \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}} \right) \right) \ge 1 - \delta. \quad (85) $$

*Proof.* Combine Eq. (76) with $b = \frac{r}{N+1} + \sqrt{\frac{\log(1/\delta)}{2(N+2)}}$ and Eq. (80). $\square$

**Remark 36.** Eq. (73) in Section G.2 shows that for any $p \in (0, 1)$, $F_Z(Z_{([pN])})$ converges towards $p$ at the rate $\sqrt{N}$. Therefore, the order of magnitude $1/\sqrt{N}$ of the deviations in Corollary 34 is optimal (at least, asymptotically).

### H.4. Proof of Theorem 25

We proceed in four steps.

**Step 1: mean value theorem.** Since $F_{U(\ell:n)}^{-1}$ is continuous on $[x, x+\varepsilon]$ and differentiable on $(x, x+\varepsilon)$ —it is even $C^\infty$ on $(0, 1)$—, by the mean-value theorem, some $c \in (x, x+\varepsilon)$ exists such that

$$ \begin{aligned} F_{U(\ell:n)}^{-1}(x+\varepsilon) - F_{U(\ell:n)}^{-1}(x) = (F_{U(\ell:n)}^{-1})'(c) \times \varepsilon &= \frac{\varepsilon}{f_{U(\ell:n)}(F_{U(\ell:n)}^{-1}(c))} \\ &\le \frac{\varepsilon}{\inf[F_{U(\ell:n)}^{-1}(x), F_{U(\ell:n)}^{-1}(x+\varepsilon)] f_{U(\ell:n)}}. \end{aligned} \quad (86) $$

Therefore, it remains to get a uniform lower bound on the density $f_{U(\ell:n)}$.

**Step 2: density lower bound with the inverse cdf $F_{U(\ell:n)}^{-1}$**. Since $f_{U(\ell:n)}$ is uni-modal [6], a straightforward proof by exhaustion (depending on the relative position of argmax $f_{U(\ell:n)}$ and $[F_{U(\ell:n)}^{-1}(x), F_{U(\ell:n)}^{-1}(x+\varepsilon)]$) shows that

$$ \inf_{[F_{U(\ell:n)}^{-1}(x), F_{U(\ell:n)}^{-1}(x+\varepsilon)]} f_{U(\ell:n)} \ge \min \left\{ \sup_{[0, F_{U(\ell:n)}^{-1}(x)]} f_{U(\ell:n)}, \sup_{[F_{U(\ell:n)}^{-1}(x+\varepsilon), 1]} f_{U(\ell:n)} \right\}. \quad (87) $$

Let us consider separately the two terms of the right-hand side of Eq. (87). On the one hand, for every $\delta \in (0, x)$,

$$ \begin{aligned} \sup_{[0, F_{U(\ell:n)}^{-1}(x)]} f_{U(\ell:n)} &\ge \frac{1}{F_{U(\ell:n)}^{-1}(x) - F_{U(\ell:n)}^{-1}(\delta)} \int_{F_{U(\ell:n)}^{-1}(\delta)}^{F_{U(\ell:n)}^{-1}(x)} f_{U(\ell:n)}(t)dt \\ &= \frac{F_{U(\ell:n)}(x) - F_{U(\ell:n)}(\delta)}{F_{U(\ell:n)}^{-1}(x) - F_{U(\ell:n)}^{-1}(\delta)} \\ &= \frac{x - \delta}{F_{U(\ell:n)}^{-1}(x) - F_{U(\ell:n)}^{-1}(\delta)}. \end{aligned} \quad (88) $$

On the other hand, similarly, for every $\delta' \in (0, 1 - x - \varepsilon)$,

$$ \begin{aligned} \sup_{[F_{U(\ell:n)}^{-1}(x+\varepsilon), 1]} f_{U(\ell:n)} &\ge \frac{1}{F_{U(\ell:n)}^{-1}(1-\delta') - F_{U(\ell:n)}^{-1}(x+\varepsilon)} \int_{F_{U(\ell:n)}^{-1}(x+\varepsilon)}^{F_{U(\ell:n)}^{-1}(1-\delta')} f_{U(\ell:n)}(t)dt \\ &= \frac{(1-\delta') - (x+\varepsilon)}{F_{U(\ell:n)}^{-1}(1-\delta') - F_{U(\ell:n)}^{-1}(x+\varepsilon)}. \end{aligned} \quad (89) $$
**Step 3: use of concentration results.** Given Eq. (88) and (89), it remains to show upper bounds on $F_{U_{(\ell:n)}}^{-1}(x) - F_{U_{(\ell:n)}}^{-1}(\delta)$ and $F_{U_{(\ell:n)}}^{-1}(1 - \delta') - F_{U_{(\ell:n)}}^{-1}(x + \varepsilon)$. On the one hand, by Eq. (40)–(41) in Proposition 24 with $r = \ell$ and $N = n$,

$$ \forall \delta \in (0, 1-x), \quad F_{U_{(\ell:n)}}^{-1}(x) - F_{U_{(\ell:n)}}^{-1}(\delta) \le F_{U_{(\ell:n)}}^{-1}(1-\delta) - F_{U_{(\ell:n)}}^{-1}(\delta) \le \sqrt{\frac{2\log(1/\delta)}{n+2}}. $$

Therefore, using Eq. (88), we obtain that

$$ \sup_{[0, F_{U_{(\ell:n)}}^{-1}(x)]} f_{U_{(\ell:n)}} \ge \sup_{\delta \in (0, \min\{x, 1-x\})} \left\{ \frac{x - \delta}{F_{U_{(\ell:n)}}^{-1}(x) - F_{U_{(\ell:n)}}^{-1}(\delta)} \right\} \ge g(x) \sqrt{\frac{n+2}{2}} \quad (90) $$

$$ \text{with} \quad g(x) := \sup_{\delta \in (0, \min\{x, 1-x\})} \left\{ \frac{x - \delta}{\sqrt{\log(1/\delta)}} \right\}. $$

On the other hand, similarly, for every $\delta' \in (0, x + \varepsilon)$,

$$ F_{U_{(\ell:n)}}^{-1}(1 - \delta') - F_{U_{(\ell:n)}}^{-1}(x + \varepsilon) \le F_{U_{(\ell:n)}}^{-1}(1 - \delta') - F_{U_{(\ell:n)}}^{-1}(\delta') \le \sqrt{\frac{2 \log(1/\delta')}{n+2}}. $$

Therefore, using Eq. (89), we obtain that

$$ \sup_{[F_{U_{(\ell:n)}}^{-1}(x+\varepsilon), 1]} f_{U_{(\ell:n)}} \ge \sup_{\delta' \in (0, \min\{x+\varepsilon, 1-(x+\varepsilon)\})} \left\{ \frac{(1-\delta') - (x+\varepsilon)}{F_{U_{(\ell:n)}}^{-1}(1-\delta') - F_{U_{(\ell:n)}}^{-1}(x+\varepsilon)} \right\} $$

$$ \ge \sup_{\delta' \in (0, \min\{x+\varepsilon, 1-(x+\varepsilon)\})} \left\{ \frac{1-(x+\varepsilon)-\delta'}{\sqrt{\log(1/\delta')}} \right\} \times \sqrt{\frac{n+2}{2}} \quad (91) $$

$$ = g(1 - x - \varepsilon) \sqrt{\frac{n+2}{2}}. \quad (92) $$

**Step 4: conclusion.** Combining Eq. (86), (87), (90) and (92), we obtain that

$$ F_{U_{(\ell:n)}}^{-1}(x + \varepsilon) - F_{U_{(\ell:n)}}^{-1}(x) \le \frac{\sqrt{2}}{\sqrt{n+2}} \frac{\varepsilon}{\min\{g(x), g(1-x-\varepsilon)\}}. \quad (93) $$

Now, let us rewrite the definition of $g$ as

$$ \forall t \in (0, 1), \quad g(t) := \sup_{\delta \in (0, \min\{t, 1-t\})} G(t, \delta) \quad \text{where} \quad \forall \delta > 0, \quad G(t, \delta) := \frac{t - \delta}{\sqrt{\log(1/\delta)}}. $$

Note that $t \mapsto G(t, \delta)$ is increasing whatever $\delta > 0$, so that $g$ is nondecreasing on $(0, 1/2]$. In addition, for every $t \in (0, 1/2]$, using that $t \le 1 - t$, we have $G(t, \delta) \le G(1 - t, \delta)$ for every $\delta > 0$, hence $g(t) \le g(1 - t)$. This proves that

$$ \forall t \in (0, 1), \quad g(\min\{t, 1-t\}) = \min\{g(t), g(1-t)\}, $$

hence

$$ \begin{align*} \min\{g(x), g(1-x-\varepsilon)\} &\ge \min\{g(x), g(1-x), g(x+\varepsilon), g(1-x-\varepsilon)\} \\ &= \min\{g(\min\{x, 1-x\}), g(\min\{x+\varepsilon, 1-x-\varepsilon\})\} \\ &= g(\min\{x, 1-x, x+\varepsilon, 1-x-\varepsilon\}) \quad \text{since } g \text{ is nondecreasing on } (0, 1/2] \end{align*} $$
**Step 3: use of concentration results.** Given Eq. (88) and (89), it remains to show upper bounds on $F_{U_{(\ell:n)}}^{-1}(x) - F_{U_{(\ell:n)}}^{-1}(\delta)$ and $F_{U_{(\ell:n)}}^{-1}(1 - \delta') - F_{U_{(\ell:n)}}^{-1}(x + \varepsilon)$. On the one hand, by Eq. (40)–(41) in Proposition 24 with $r = \ell$ and $N = n$,

$$ \forall \delta \in (0, 1-x), \quad F_{U_{(\ell:n)}}^{-1}(x) - F_{U_{(\ell:n)}}^{-1}(\delta) \le F_{U_{(\ell:n)}}^{-1}(1-\delta) - F_{U_{(\ell:n)}}^{-1}(\delta) \le \sqrt{\frac{2\log(1/\delta)}{n+2}}. $$

Therefore, using Eq. (88), we obtain that

$$ \sup_{[0, F_{U_{(\ell:n)}}^{-1}(x)]} f_{U_{(\ell:n)}} \ge \sup_{\delta \in (0, \min\{x, 1-x\})} \left\{ \frac{x - \delta}{F_{U_{(\ell:n)}}^{-1}(x) - F_{U_{(\ell:n)}}^{-1}(\delta)} \right\} \ge g(x) \sqrt{\frac{n+2}{2}} \quad (90) $$

$$ \text{with} \quad g(x) := \sup_{\delta \in (0, \min\{x, 1-x\})} \left\{ \frac{x - \delta}{\sqrt{\log(1/\delta)}} \right\}. $$

On the other hand, similarly, for every $\delta' \in (0, x + \varepsilon)$,

$$ F_{U_{(\ell:n)}}^{-1}(1-\delta') - F_{U_{(\ell:n)}}^{-1}(x+\varepsilon) \le F_{U_{(\ell:n)}}^{-1}(1-\delta') - F_{U_{(\ell:n)}}^{-1}(\delta') \le \sqrt{\frac{2\log(1/\delta')}{n+2}}. $$

Therefore, using Eq. (89), we obtain that

$$ \sup_{[F_{U_{(\ell:n)}}^{-1}(x+\varepsilon), 1]} f_{U_{(\ell:n)}} \ge \sup_{\delta' \in (0, \min\{x+\varepsilon, 1-(x+\varepsilon)\})} \left\{ \frac{(1-\delta') - (x+\varepsilon)}{F_{U_{(\ell:n)}}^{-1}(1-\delta') - F_{U_{(\ell:n)}}^{-1}(x+\varepsilon)} \right\} $$

$$ \ge \sup_{\delta' \in (0, \min\{x+\varepsilon, 1-(x+\varepsilon)\})} \left\{ \frac{1-(x+\varepsilon)-\delta'}{\sqrt{\log(1/\delta')}} \right\} \times \sqrt{\frac{n+2}{2}} \quad (91) $$

$$ = g(1 - x - \varepsilon) \sqrt{\frac{n+2}{2}}. \quad (92) $$

**Step 4: conclusion.** Combining Eq. (86), (87), (90) and (92), we obtain that

$$ F_{U_{(\ell:n)}}^{-1}(x+\varepsilon) - F_{U_{(\ell:n)}}^{-1}(x) \le \frac{\sqrt{2}}{\sqrt{n+2}} \frac{\varepsilon}{\min\{g(x), g(1-x-\varepsilon)\}}. \quad (93) $$

Now, let us rewrite the definition of $g$ as

$$ \forall t \in (0, 1), \quad g(t) := \sup_{\delta \in (0, \min\{t, 1-t\})} G(t, \delta) \quad \text{where} \quad \forall \delta > 0, \quad G(t, \delta) := \frac{t - \delta}{\sqrt{\log(1/\delta)}}. $$

Note that $t \mapsto G(t, \delta)$ is increasing whatever $\delta > 0$, so that $g$ is nondecreasing on $(0, 1/2]$. In addition, for every $t \in (0, 1/2]$, using that $t \le 1 - t$, we have $G(t, \delta) \le G(1 - t, \delta)$ for every $\delta > 0$, hence $g(t) \le g(1 - t)$. This proves that

$$ \forall t \in (0, 1), \quad g(\min\{t, 1-t\}) = \min\{g(t), g(1-t)\}, $$

hence

$$ \begin{align*} \min\{g(x), g(1-x-\varepsilon)\} &\ge \min\{g(x), g(1-x), g(x+\varepsilon), g(1-x-\varepsilon)\} \\ &= \min\{g(\min\{x, 1-x\}), g(\min\{x+\varepsilon, 1-x-\varepsilon\})\} \\ &= g(\min\{x, 1-x, x+\varepsilon, 1-x-\varepsilon\}) \quad \text{since } g \text{ is nondecreasing on } (0, 1/2] \end{align*} $$
$$= g(\min\{x, 1 - x - \varepsilon\}),$$

By Eq. (93), we obtain that Eq. (42) holds true.

Let us finally prove the inequalities stated about the function $g$. First, for every $t \in (0, 1/2]$, we have $t/2 \le \min\{t, 1-t\}$, hence

$$g(t) \ge G(t, t/2) = \frac{t}{2\sqrt{\log(2/t)}}.$$

Second, since $g$ is nondecreasing over $(0, 1/2]$, for every $t \in [1/3, 1/2]$,

$$g(t) \ge g\left(\frac{1}{3}\right) \ge G\left(\frac{1}{3}, 0.047\right) \ge 0.163 \ge \frac{\sqrt{2}}{9}.$$

□

### H.5. Proof of Lemma 27

We proceed similarly to the proof of Lemma 23. First, let us define $\tilde{Z}_{i,j} = F_Z^{-1}(U_{i,j})$ for every $i \in \llbracket n \rrbracket$ and $j \in \llbracket m \rrbracket$, so that $(\tilde{Z}_{i,j})_{1 \le i \le n, 1 \le j \le m}$ has the same distribution as $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$. Therefore, the corresponding order statistics of order statistics have the same distributions:

$$Z_{(\ell,k)} \stackrel{d}{=} \tilde{Z}_{(\ell,k)}. \qquad (94)$$

Second, using twice Eq. (75) in the proof of Lemma 23, since $F_Z^{-1}$ is nondecreasing, we have

$$\begin{aligned}
\tilde{Z}_{(\ell,k)} &= \hat{Q}_{(k)}\left(\left(\hat{Q}_{(\ell)}(F_Z^{-1}(U_{1,j}), \dots, F_Z^{-1}(U_{n,j}))\right)_{j \in \llbracket m \rrbracket}\right) \\
&= \hat{Q}_{(k)}\left(F_Z^{-1}\left(\hat{Q}_{(\ell)}(U_{1,j}, \dots, U_{n,j})\right)_{j \in \llbracket m \rrbracket}\right) \\
&= F_Z^{-1}\left(\hat{Q}_{(k)}\left(\left(\hat{Q}_{(\ell)}(U_{1,j}, \dots, U_{n,j})\right)_{j \in \llbracket m \rrbracket}\right)\right) = F_Z^{-1}(U_{(\ell,k)}),
\end{aligned}$$

hence Eq. (94) implies that

$$F_Z(Z_{(\ell,k)}) \stackrel{d}{=} F_Z(\tilde{Z}_{(\ell,k)}) = F_Z \circ F_Z^{-1}(U_{(\ell,k)}).$$

Using Eq. (36), this proves Eq. (43) in the general case, and Eq. (45) when $F_Z$ is continuous. □

**Remark 37.** In the case of a general cdf $F_Z$, another consequence of Lemma 27 is that, for every $a, b \in \mathbb{R}$ such that $a \le b$,

$$\mathbb{P}(U_{(\ell,k)} \le b) \le \mathbb{P}(F_Z(Z_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b)) \qquad (95)$$

$$\text{and} \quad \mathbb{P}(a \le U_{(\ell,k)} \le b) \le \mathbb{P}(a \le F_Z(Z_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b)). \qquad (96)$$

*Proof.* Since $F_Z \circ F_Z^{-1}$ is nondecreasing,

$$U_{(\ell,k)} \le b \quad \text{implies that} \quad F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b), \qquad (97)$$

hence Eq. (95) thanks to Eq. (43). Since $F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \ge U_{(\ell,k)}$ by Eq. (36), Eq. (97) also shows that

$$a \le U_{(\ell,k)} \le b \quad \text{implies that} \quad a \le F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b),$$

hence Eq. (96) thanks to Eq. (43). □
$$= g(\min\{x, 1 - x - \varepsilon\}),$$

By Eq. (93), we obtain that Eq. (42) holds true.

Let us finally prove the inequalities stated about the function $g$. First, for every $t \in (0, 1/2]$, we have $t/2 \le \min\{t, 1-t\}$, hence

$$g(t) \ge G(t, t/2) = \frac{t}{2\sqrt{\log(2/t)}}.$$

Second, since $g$ is nondecreasing over $(0, 1/2]$, for every $t \in [1/3, 1/2]$,

$$g(t) \ge g\left(\frac{1}{3}\right) \ge G\left(\frac{1}{3}, 0.047\right) \ge 0.163 \ge \frac{\sqrt{2}}{9}.$$

□

### H.5. Proof of Lemma 27

We proceed similarly to the proof of Lemma 23. First, let us define $\tilde{Z}_{i,j} = F_Z^{-1}(U_{i,j})$ for every $i \in \llbracket n \rrbracket$ and $j \in \llbracket m \rrbracket$, so that $(\tilde{Z}_{i,j})_{1 \le i \le n, 1 \le j \le m}$ has the same distribution as $(Z_{i,j})_{1 \le i \le n, 1 \le j \le m}$. Therefore, the corresponding order statistics of order statistics have the same distributions:

$$Z_{(\ell,k)} \stackrel{d}{=} \tilde{Z}_{(\ell,k)}. \qquad (94)$$

Second, using twice Eq. (75) in the proof of Lemma 23, since $F_Z^{-1}$ is nondecreasing, we have

$$\begin{aligned} \tilde{Z}_{(\ell,k)} &= \hat{Q}_{(k)}\left(\left(\hat{Q}_{(\ell)}(F_Z^{-1}(U_{1,j}), \dots, F_Z^{-1}(U_{n,j}))\right)_{j \in \llbracket m \rrbracket}\right) \\ &= \hat{Q}_{(k)}\left(F_Z^{-1}\left(\hat{Q}_{(\ell)}(U_{1,j}, \dots, U_{n,j})\right)_{j \in \llbracket m \rrbracket}\right) \\ &= F_Z^{-1}\left(\hat{Q}_{(k)}\left(\left(\hat{Q}_{(\ell)}(U_{1,j}, \dots, U_{n,j})\right)_{j \in \llbracket m \rrbracket}\right)\right) = F_Z^{-1}(U_{(\ell,k)}), \end{aligned}$$

hence Eq. (94) implies that

$$F_Z(Z_{(\ell,k)}) \stackrel{d}{=} F_Z(\tilde{Z}_{(\ell,k)}) = F_Z \circ F_Z^{-1}(U_{(\ell,k)}).$$

Using Eq. (36), this proves Eq. (43) in the general case, and Eq. (45) when $F_Z$ is continuous. □

**Remark 37.** In the case of a general cdf $F_Z$, another consequence of Lemma 27 is that, for every $a, b \in \mathbb{R}$ such that $a \le b$,

$$\mathbb{P}(U_{(\ell,k)} \le b) \le \mathbb{P}(F_Z(Z_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b)) \qquad (95)$$

$$\text{and} \quad \mathbb{P}(a \le U_{(\ell,k)} \le b) \le \mathbb{P}(a \le F_Z(Z_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b)). \qquad (96)$$

*Proof.* Since $F_Z \circ F_Z^{-1}$ is nondecreasing,

$$U_{(\ell,k)} \le b \quad \text{implies that} \quad F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b), \qquad (97)$$

hence Eq. (95) thanks to Eq. (43). Since $F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \ge U_{(\ell,k)}$ by Eq. (36), Eq. (97) also shows that

$$a \le U_{(\ell,k)} \le b \quad \text{implies that} \quad a \le F_Z \circ F_Z^{-1}(U_{(\ell,k)}) \le F_Z \circ F_Z^{-1}(b),$$

hence Eq. (96) thanks to Eq. (43). □
## H.6. Proof of Lemma 28

By Eq. (39) in Lemma 23 with $F_Z = F_{U_{(\ell:n)}}$ (which is continuous), $r = k$ and $N = m$, we have

$$F_{U_{(\ell:n)}}(Z_{(k:m)}) \stackrel{d}{=} U_{(k:m)}$$

where $Z_{(k:m)}$ is the k-th order statistics of an i.i.d. sample of m random variables distributed as $U_{(\ell:n)}$. In other words, with the notation of Lemma 27, we have $Z_{(k:m)} \stackrel{d}{=} U_{(\ell:n,k:m)}$, hence

$$F_{U_{(\ell:n)}}(U_{(\ell:n,k:m)}) \stackrel{d}{=} U_{(k:m)} \stackrel{d}{=} F_{U_{(k:m)}}^{-1}(U)$$

since $F_{U_{(k:m)}}$ is continuous (where $U$ follows the uniform distribution over $[0, 1]$). So,

$$U_{(\ell:n,k:m)} \stackrel{d}{=} F_{U_{(\ell:n)}}^{-1} \circ F_{U_{(k:m)}}^{-1}(U) = (F_{U_{(k:m)}} \circ F_{U_{(\ell:n)}})^{-1}(U)$$

has cdf $F_{U_{(k:m)}} \circ F_{U_{(\ell:n)}}$.

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

# Appendix I: Previous and additional results on related works

## I.1. Proofs of Section 2.1 (theoretical analysis of split CP)

In this section, we prove the results stated about split conformal prediction (split CP) in Section 2.1. Although these results are mostly classical, we think useful to prove them here for completeness, since these proofs are particularly simple with the notation introduced in this paper and the results of Appendix B.1.

### I.1.1. Marginal guarantees

By Lemma 23, the expected coverage of $\hat{C}_r$ is

$$\mathbb{P}(Y \in \hat{C}_r(X)) = \mathbb{E}[1 - \alpha_r(\mathcal{D})] = \mathbb{E}[F_S(S_{(r)})] \geq \mathbb{E}[U_{(r:n_c)}]$$

with equality when $F_S$ is continuous —or, equivalently, when the scores are almost surely distinct. Using Eq. (69) in Appendix G.1, we get that

$$\mathbb{P}(Y \in \hat{C}_r(X)) \geq \frac{r}{n_c + 1}$$

with equality when $F_S$ is continuous. This proves that $\hat{C}_r$ is marginally valid when $r = \lceil(1 - \alpha)(n_c + 1)\rceil$, and Eq. (6) when $F_S$ is continuous.

### I.1.2. Training-conditional guarantees

By Lemma 23,

$$\mathbb{P}(Y \in \hat{C}_r(X) | \mathcal{D}) = 1 - \alpha_r(\mathcal{D}) = F_S(S_{(r)}) \geq U_{(r:n_c)} \quad (98)$$

which follows the Beta$(r, n_c - r + 1)$ distribution, hence

$$\mathbb{P}(1 - \alpha_r(\mathcal{D}) \geq F_{U_{(r:n_c)}}^{-1}(\beta)) \geq \mathbb{P}(U_{(r:n_c)} \geq F_{U_{(r:n_c)}}^{-1}(\beta)) = 1 - F_{U_{(r:n_c)}} \circ F_{U_{(r:n_c)}}^{-1}(\beta) = 1 - \beta,$$
## H.6. Proof of Lemma 28

By Eq. (39) in Lemma 23 with $F_Z = F_{U_{(\ell:n)}}$ (which is continuous), $r = k$ and $N = m$, we have

$$F_{U_{(\ell:n)}}(Z_{(k:m)}) \stackrel{d}{=} U_{(k:m)}$$

where $Z_{(k:m)}$ is the k-th order statistics of an i.i.d. sample of m random variables distributed as $U_{(\ell:n)}$. In other words, with the notation of Lemma 27, we have $Z_{(k:m)} \stackrel{d}{=} U_{(\ell:n,k:m)}$, hence

$$F_{U_{(\ell:n)}}(U_{(\ell:n,k:m)}) \stackrel{d}{=} U_{(k:m)} \stackrel{d}{=} F_{U_{(k:m)}}^{-1}(U)$$

since $F_{U_{(k:m)}}$ is continuous (where $U$ follows the uniform distribution over $[0, 1]$). So,

$$U_{(\ell:n,k:m)} \stackrel{d}{=} F_{U_{(\ell:n)}}^{-1} \circ F_{U_{(k:m)}}^{-1}(U) = (F_{U_{(k:m)}} \circ F_{U_{(\ell:n)}})^{-1}(U)$$

has cdf $F_{U_{(k:m)}} \circ F_{U_{(\ell:n)}}$.

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

# Appendix I: Previous and additional results on related works

## I.1. Proofs of Section 2.1 (theoretical analysis of split CP)

In this section, we prove the results stated about split conformal prediction (split CP) in Section 2.1. Although these results are mostly classical, we think useful to prove them here for completeness, since these proofs are particularly simple with the notation introduced in this paper and the results of Appendix B.1.

### I.1.1. Marginal guarantees

By Lemma 23, the expected coverage of $\hat{C}_r$ is

$$\mathbb{P}(Y \in \hat{C}_r(X)) = \mathbb{E}[1 - \alpha_r(\mathcal{D})] = \mathbb{E}[F_S(S_{(r)})] \geq \mathbb{E}[U_{(r:n_c)}]$$

with equality when $F_S$ is continuous —or, equivalently, when the scores are almost surely distinct. Using Eq. (69) in Appendix G.1, we get that

$$\mathbb{P}(Y \in \hat{C}_r(X)) \geq \frac{r}{n_c + 1}$$

with equality when $F_S$ is continuous. This proves that $\hat{C}_r$ is marginally valid when $r = \lceil(1 - \alpha)(n_c + 1)\rceil$, and Eq. (6) when $F_S$ is continuous.

### I.1.2. Training-conditional guarantees

By Lemma 23,

$$\mathbb{P}(Y \in \hat{C}_r(X) | \mathcal{D}) = 1 - \alpha_r(\mathcal{D}) = F_S(S_{(r)}) \geq U_{(r:n_c)} \quad (98)$$

which follows the Beta$(r, n_c - r + 1)$ distribution, hence

$$\mathbb{P}(1 - \alpha_r(\mathcal{D}) \geq F_{U_{(r:n_c)}}^{-1}(\beta)) \geq \mathbb{P}(U_{(r:n_c)} \geq F_{U_{(r:n_c)}}^{-1}(\beta)) = 1 - F_{U_{(r:n_c)}} \circ F_{U_{(r:n_c)}}^{-1}(\beta) = 1 - \beta,$$
that for every $\beta' \in (0, 1)$, with probability at least $1 - \beta'$, the coverage $1 - \alpha_r(\mathcal{D})$ of $\hat{C}_r$ is smaller than

$$F_{U_{(r:n_c)}}^{-1}(1 - \beta') \le 1 - \alpha + \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(n_c + 2)}} + \frac{1}{n_c + 1}. \quad (105)$$

Notice that this upper bound is of order $1 - \alpha + \mathcal{O}(1/\sqrt{n_c})$ as Eq. (103), with only a slightly worse dependence on $\alpha$ and $\beta, \beta'$.

## I.2. Additional results: average of quantiles

In the one-shot FL setting, an alternative approach to quantile-of-quantiles is to use an average of quantiles, as proposed by [38]. The idea is that each agent returns its $[(n_j + 1)(1 - \alpha)]$-th smallest score, and then the central server averages these scores. Using the notation of Section 2.2, the associated prediction set is

$$\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(x) := \left\{ y \in \mathcal{Y} : s(x, y) \le \frac{1}{m} \sum_{j=1}^{m} \hat{Q}_{(\ell_j)}(S_j) \right\} \quad (106)$$

with $\ell_j = [(n_j + 1)(1 - \alpha)]$ for every $j \in [m]$. To the best of our knowledge, no coverage guarantee has ever been proved for $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$. We study this prediction set in this section, showing that its marginal coverage strongly depends on the scores distribution, so that one cannot always find some $\ell_j \in [n]$ such that the marginal coverage is larger than a given $1 - \alpha$.

### I.2.1. First remark

A first simple remark is that when each agent $j \in [m]$ has $n_j = 1$ calibration point, then one must take $\ell_j = 1$ and the marginal coverage of $\hat{C}^{\text{Avg}}$ cannot be close to 1 in general since it is equal to

$$\mathbb{E}\left[F_S\left(\frac{1}{m}\sum_{j=1}^{m} \hat{Q}_{(1)}(S_j)\right)\right] = \mathbb{E}\left[F_S\left(\frac{1}{m}\sum_{j=1}^{m} S_{1,j}\right)\right] \approx F_S(\mathbb{E}[S])$$

(at least when $m$ is large) by the law of large numbers. Therefore, $\hat{C}^{\text{Avg}}$ cannot be marginally valid for all distributions without assuming that $n_j \ge n_0(\alpha)$ for some large enough $n_0(\alpha)$, at least for a large part of the agents $j \in [m]$. The next result shows that such an assumption is not sufficient.

### I.2.2. Negative result for Bernoulli scores

We now prove that when $n_j = n$ for every $j \in [m]$, for every $\alpha \in (0, 1)$, some distribution of the scores exists such that the marginal coverage of $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ is smaller than $1 - \alpha$ whatever $\ell_j \in [m]$, for arbitrary large $m$ and $n$. Therefore, contrary to our quantile-of-quantiles prediction sets of Section 3, the $\ell_j$ cannot be chosen in such a way that $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ is a marginally-valid distribution-free prediction set, even when the data set is large enough.
that for every $\beta' \in (0, 1)$, with probability at least $1 - \beta'$, the coverage $1 - \alpha_r(\mathcal{D})$ of $\hat{C}_r$ is smaller than

$$F_{U_{(r:n_c)}}^{-1}(1 - \beta') \le 1 - \alpha + \frac{\sqrt{\log(1/\beta)} + \sqrt{\log(1/\beta')}}{\sqrt{2(n_c + 2)}} + \frac{1}{n_c + 1}. \quad (105)$$

Notice that this upper bound is of order $1 - \alpha + \mathcal{O}(1/\sqrt{n_c})$ as Eq. (103), with only a slightly worse dependence on $\alpha$ and $\beta, \beta'$.

## I.2. Additional results: average of quantiles

In the one-shot FL setting, an alternative approach to quantile-of-quantiles is to use an average of quantiles, as proposed by [38]. The idea is that each agent returns its $[(n_j + 1)(1 - \alpha)]$-th smallest score, and then the central server averages these scores. Using the notation of Section 2.2, the associated prediction set is

$$\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(x) := \left\{ y \in \mathcal{Y} : s(x, y) \le \frac{1}{m} \sum_{j=1}^{m} \hat{Q}_{(\ell_j)}(S_j) \right\} \quad (106)$$

with $\ell_j = [(n_j + 1)(1 - \alpha)]$ for every $j \in [m]$. To the best of our knowledge, no coverage guarantee has ever been proved for $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$. We study this prediction set in this section, showing that its marginal coverage strongly depends on the scores distribution, so that one cannot always find some $\ell_j \in [n]$ such that the marginal coverage is larger than a given $1 - \alpha$.

### I.2.1. First remark

A first simple remark is that when each agent $j \in [m]$ has $n_j = 1$ calibration point, then one must take $\ell_j = 1$ and the marginal coverage of $\hat{C}^{\text{Avg}}$ cannot be close to 1 in general since it is equal to

$$\mathbb{E} \left[ F_S \left( \frac{1}{m} \sum_{j=1}^{m} \hat{Q}_{(1)}(S_j) \right) \right] = \mathbb{E} \left[ F_S \left( \frac{1}{m} \sum_{j=1}^{m} S_{1,j} \right) \right] \approx F_S(\mathbb{E}[S])$$

(at least when $m$ is large) by the law of large numbers. Therefore, $\hat{C}^{\text{Avg}}$ cannot be marginally valid for all distributions without assuming that $n_j \ge n_0(\alpha)$ for some large enough $n_0(\alpha)$, at least for a large part of the agents $j \in [m]$. The next result shows that such an assumption is not sufficient.

### I.2.2. Negative result for Bernoulli scores

We now prove that when $n_j = n$ for every $j \in [m]$, for every $\alpha \in (0, 1)$, some distribution of the scores exists such that the marginal coverage of $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ is smaller than $1 - \alpha$ whatever $\ell_j \in [m]$, for arbitrary large $m$ and $n$. Therefore, contrary to our quantile-of-quantiles prediction sets of Section 3, the $\ell_j$ cannot be chosen in such a way that $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ is a marginally-valid distribution-free prediction set, even when the data set is large enough.
**Proposition 38.** In the setting of Section 2.2, with Assumption 1, for any $\ell_1, \dots, \ell_m \in [m]$, the prediction set $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ defined by Eq. (106) satisfies

$$ \mathbb{P}(Y \in \hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(X)) \le \mathbb{P}(Y \in \hat{C}_{n, \dots, n}^{\text{Avg}}(X)). \quad (107) $$

Assuming in addition that the scores $S_{i,j}$, $S$ are i.i.d. Bernoulli($p$) random variables for some $p \in [0, 1]$, for every $\ell \in [n]$, we have

$$ \mathbb{P}(Y \in \hat{C}_{\ell, \dots, \ell}^{\text{Avg}}(X)) = (1-p) + p \cdot F_{U_{(n-\ell+1:n)}}(p)^m \quad (108) $$

where $F_{U_{(n-\ell+1:n)}}$ is the cdf of the Beta($n - \ell + 1, \ell$) distribution. Therefore, for every $c \in (0, 1)$, if $m = m_n$ and $p = p_n = 1 - [\log(1/c)/m_n]^{1/n}$ are such that $\log(m_n)/n \to +\infty$ as $n \to +\infty$, we have

$$ \mathbb{P}(Y \in \hat{C}_{n, \dots, n}^{\text{Avg}}(X)) = (1 - p_n) + p_n [1 - (1 - p_n)^n]^{m_n} \xrightarrow{n \to +\infty} c. \quad (109) $$

Eq. (107)–(109) show that for any $\alpha \in (0, 1)$, when the scores follow a Bernoulli($p_n$) distribution with

$$ p_n = 1 - \left[ \frac{\log[2/(1-\alpha)]}{m_n} \right]^{1/n} \quad \text{and} \quad \log(m_n) \gg n \to +\infty $$

—for instance, when $m_n \ge n^n$, the marginal coverage of $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ is strictly smaller than $1 - \alpha$ when $n$ is large enough, whatever the $\ell_j$, $j \in [m]$. So, $\hat{C}^{\text{Avg}}$ cannot be used as a distribution-free marginally-valid prediction set.

Note that the counterexample provided by Proposition 38 relies on the non-robustness of the empirical mean of the $\hat{Q}_{(\ell_j)}(S_j)$ defining $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$: when the scores follow a Bernoulli distribution, it suffices to have one $\hat{Q}_{(\ell_j)}(S_j) \ne 1$ to make the expected coverage strictly smaller than $1 - p$, and such an “outlier” event occurs with a large probability if $m$ is large enough, even when $p$ is close to 1. This phenomenon enlightens the interest of our quantile-of-quantiles approach, which does not have such a drawback thanks to the robustness of the $k$-th empirical quantile.

*Proof of Proposition 38.* First, for every $j \in [m]$, $\hat{Q}_{(\ell_j)}(S_j)$ is a nondecreasing function of $\ell_j$, hence $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(X)$ is a nondecreasing function of $\ell_j$, which implies Eq. (107).

Second, when the scores are i.i.d. and follow a Bernoulli($p$) distribution, for any $i \in [m]$, $S_{(\ell:n),i}$ follows a Bernoulli distribution with parameter

$$ \mathbb{P}(S_{(\ell:n),i} = 1) = \sum_{k=n-\ell+1}^{n} p^k (1-p)^{n-k} \binom{n}{k} = F_{U_{(n-\ell+1:n)}}(p) $$

by Eq. (65). Therefore, we have

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(X)) &= \mathbb{P} \left( S \le \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) \\ &= \mathbb{P}(S=0) + \mathbb{P}(S=1 \text{ and } S_{(\ell:n),j}=1 \text{ for every } j \in [m]) \\ &= (1-p) + p \cdot \mathbb{P}(S_{(\ell:n),1}=1)^m = (1-p) + p \cdot F_{U_{(n-\ell+1:n)}}(p)^m, \end{aligned} $$

which proves Eq. (108).
**Proposition 38.** In the setting of Section 2.2, with Assumption 1, for any $\ell_1, \dots, \ell_m \in [m]$, the prediction set $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ defined by Eq. (106) satisfies

$$ \mathbb{P}(Y \in \hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(X)) \le \mathbb{P}(Y \in \hat{C}_{n, \dots, n}^{\text{Avg}}(X)). \quad (107) $$

Assuming in addition that the scores $S_{i,j}$, $S$ are i.i.d. Bernoulli($p$) random variables for some $p \in [0, 1]$, for every $\ell \in [n]$, we have

$$ \mathbb{P}(Y \in \hat{C}_{\ell, \dots, \ell}^{\text{Avg}}(X)) = (1-p) + p \cdot F_{U_{(n-\ell+1:n)}}(p)^m \quad (108) $$

where $F_{U_{(n-\ell+1:n)}}$ is the cdf of the Beta($n - \ell + 1, \ell$) distribution. Therefore, for every $c \in (0, 1)$, if $m = m_n$ and $p = p_n = 1 - [\log(1/c)/m_n]^{1/n}$ are such that $\log(m_n)/n \to +\infty$ as $n \to +\infty$, we have

$$ \mathbb{P}(Y \in \hat{C}_{n, \dots, n}^{\text{Avg}}(X)) = (1 - p_n) + p_n [1 - (1 - p_n)^n]^{m_n} \xrightarrow{n \to +\infty} c. \quad (109) $$

Eq. (107)–(109) show that for any $\alpha \in (0, 1)$, when the scores follow a Bernoulli($p_n$) distribution with

$$ p_n = 1 - \left[ \frac{\log[2/(1-\alpha)]}{m_n} \right]^{1/n} \quad \text{and} \quad \log(m_n) \gg n \to +\infty $$

—for instance, when $m_n \ge n^n$, the marginal coverage of $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$ is strictly smaller than $1 - \alpha$ when $n$ is large enough, whatever the $\ell_j$, $j \in [m]$. So, $\hat{C}^{\text{Avg}}$ cannot be used as a distribution-free marginally-valid prediction set.

Note that the counterexample provided by Proposition 38 relies on the non-robustness of the empirical mean of the $\hat{Q}_{(\ell_j)}(S_j)$ defining $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}$: when the scores follow a Bernoulli distribution, it suffices to have one $\hat{Q}_{(\ell_j)}(S_j) \ne 1$ to make the expected coverage strictly smaller than $1 - p$, and such an “outlier” event occurs with a large probability if $m$ is large enough, even when $p$ is close to 1. This phenomenon enlightens the interest of our quantile-of-quantiles approach, which does not have such a drawback thanks to the robustness of the $k$-th empirical quantile.

*Proof of Proposition 38.* First, for every $j \in [m]$, $\hat{Q}_{(\ell_j)}(S_j)$ is a nondecreasing function of $\ell_j$, hence $\hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(X)$ is a nondecreasing function of $\ell_j$, which implies Eq. (107).

Second, when the scores are i.i.d. and follow a Bernoulli($p$) distribution, for any $i \in [m]$, $S_{(\ell:n),i}$ follows a Bernoulli distribution with parameter

$$ \mathbb{P}(S_{(\ell:n),i} = 1) = \sum_{k=n-\ell+1}^{n} p^k (1-p)^{n-k} \binom{n}{k} = F_{U_{(n-\ell+1:n)}}(p) $$

by Eq. (65). Therefore, we have

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{\ell_1, \dots, \ell_m}^{\text{Avg}}(X)) &= \mathbb{P} \left( S \le \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) \\ &= \mathbb{P}(S=0) + \mathbb{P}(S=1 \text{ and } S_{(\ell:n),j}=1 \text{ for every } j \in [m]) \\ &= (1-p) + p \cdot \mathbb{P}(S_{(\ell:n),1}=1)^m = (1-p) + p \cdot F_{U_{(n-\ell+1:n)}}(p)^m, \end{aligned} $$

which proves Eq. (108).
Third, when $m = m_n$ is such that $\log(m_n)/n \to +\infty$ as $n \to +\infty$, we have $p_n = 1 - [\log(1/c)/m_n]^{1/n} \in (0, 1)$ for $n$ large enough, and $p_n \to 1$ and $m_n \to +\infty$ when $n \to +\infty$. So, Eq. (108) together with Eq. (68) shows that

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{n,...,n}^{\text{Avg}}(X)) &= (1-p_n) + p_n [1 - (1-p_n)^n]^{m_n} \\ &= o(1) + [1+o(1)] \left(1 - \frac{\log(1/c)}{m_n}\right)^{m_n} \\ &\xrightarrow[n \to +\infty]{} \exp(-\log(1/c)) = c. \end{aligned} $$

□

### I.2.3. Uniform scores

We now study the case of scores following a uniform distribution.

**Proposition 39.** Suppose that Assumption 1 holds true. When the scores $S_{i,j}, S$ are independent with a uniform distribution over $[a, b]$ for some $a < b$, for any $\ell \in [n]$, we have

$$ \mathbb{P}(Y \in \hat{C}_{\ell,...,\ell}^{\text{Avg}}(X)) = \frac{\ell}{n+1}. \qquad (110) $$

Proposition 39 shows that when the scores are uniform (and using this knowledge), $\hat{C}_{\ell,...,\ell}^{\text{Avg}}$ is marginally valid as soon as $\ell \ge (n+1)(1-\alpha)$, which suggests to take $\ell = [(n+1)(1-\alpha)]$. Nevertheless, the difference between the expected coverage and the nominal coverage is then equal to

$$ \frac{[(n+1)(1-\alpha)]}{n+1} - (1-\alpha) \in [0, \frac{1}{n+1}), $$

so its worst-case value $1/(n+1)$ is independent from $m$, which is not a desirable property.

*Proof.* By definition of $\hat{C}^{\text{Avg}}$, we have

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{\ell,...,\ell}^{\text{Avg}}(X)) &= \mathbb{P} \left( S \le \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) = \mathbb{E} \left[ F_S \left( \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) \right] \\ &= \mathbb{E} \left[ \frac{1}{m} \sum_{j=1}^{m} F_S(S_{(\ell:n),j}) \right] \end{aligned} $$

since $F_S(t) = (t-a)/(b-a)$ for every $t \in [a, b]$. Therefore, we get that

$$ \mathbb{P}(Y \in \hat{C}_{\ell,...,\ell}^{\text{Avg}}(X)) = \mathbb{E}[F_S(S_{(\ell:n),1})] = \mathbb{E}[U_{(\ell:n)}] = \frac{\ell}{n+1} $$

by Eq. (39) in Appendix B.1 and Eq. (69) in Appendix G.1.

□

### I.2.4. Exponential scores

We now study the case of scores following an exponential distribution.
Third, when $m = m_n$ is such that $\log(m_n)/n \to +\infty$ as $n \to +\infty$, we have $p_n = 1 - [\log(1/c)/m_n]^{1/n} \in (0, 1)$ for $n$ large enough, and $p_n \to 1$ and $m_n \to +\infty$ when $n \to +\infty$. So, Eq. (108) together with Eq. (68) shows that

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{n,...,n}^{\text{Avg}}(X)) &= (1-p_n) + p_n [1 - (1-p_n)^n]^{m_n} \\ &= o(1) + [1+o(1)] \left(1 - \frac{\log(1/c)}{m_n}\right)^{m_n} \\ &\xrightarrow[n \to +\infty]{} \exp(-\log(1/c)) = c. \end{aligned} $$

□

### I.2.3. Uniform scores

We now study the case of scores following a uniform distribution.

**Proposition 39.** Suppose that Assumption 1 holds true. When the scores $S_{i,j}, S$ are independent with a uniform distribution over $[a, b]$ for some $a < b$, for any $\ell \in [n]$, we have

$$ \mathbb{P}(Y \in \hat{C}_{\ell,...,\ell}^{\text{Avg}}(X)) = \frac{\ell}{n+1}. \qquad (110) $$

Proposition 39 shows that when the scores are uniform (and using this knowledge), $\hat{C}_{\ell,...,\ell}^{\text{Avg}}$ is marginally valid as soon as $\ell \ge (n+1)(1-\alpha)$, which suggests to take $\ell = [(n+1)(1-\alpha)]$. Nevertheless, the difference between the expected coverage and the nominal coverage is then equal to

$$ \frac{[(n+1)(1-\alpha)]}{n+1} - (1-\alpha) \in [0, \frac{1}{n+1}), $$

so its worst-case value $1/(n+1)$ is independent from $m$, which is not a desirable property.

*Proof.* By definition of $\hat{C}^{\text{Avg}}$, we have

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{\ell,...,\ell}^{\text{Avg}}(X)) &= \mathbb{P} \left( S \le \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) = \mathbb{E} \left[ F_S \left( \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) \right] \\ &= \mathbb{E} \left[ \frac{1}{m} \sum_{j=1}^{m} F_S(S_{(\ell:n),j}) \right] \end{aligned} $$

since $F_S(t) = (t-a)/(b-a)$ for every $t \in [a, b]$. Therefore, we get that

$$ \mathbb{P}(Y \in \hat{C}_{\ell,...,\ell}^{\text{Avg}}(X)) = \mathbb{E}[F_S(S_{(\ell:n),1})] = \mathbb{E}[U_{(\ell:n)}] = \frac{\ell}{n+1} $$

by Eq. (39) in Appendix B.1 and Eq. (69) in Appendix G.1.

□

### I.2.4. Exponential scores

We now study the case of scores following an exponential distribution.
**Proposition 40.** Suppose that Assumption 1 holds true. When the scores $S_{i,j}$, $S$ are independent with an exponential distribution with parameter $\lambda > 0$, for any $\ell \in [n]$, we have

$$ \mathbb{P}(Y \in \hat{\mathcal{C}}_{\ell, \dots, \ell}^{\text{Avg}}(X)) = 1 - \prod_{j=1}^{\ell} \left(1 + \frac{1}{m(n-j+1)}\right)^{-m}. \quad (111) $$

Proposition 40 shows that when the scores are exponential (and using this knowledge), it is possible to choose $\ell$ such that the expected coverage of $\hat{\mathcal{C}}_{\ell, \dots, \ell}^{\text{Avg}}$ is larger than $1 - \alpha$, provided that $m$ and $n$ are large enough. Indeed, by Eq. (111),

$$ \begin{aligned} & \max_{\ell \in [n]} \mathbb{P}(Y \in \hat{\mathcal{C}}_{\ell, \dots, \ell}^{\text{Avg}}(X)) \\ &= \mathbb{P}(Y \in \hat{\mathcal{C}}_{n, \dots, n}^{\text{Avg}}(X)) \\ &= 1 - \prod_{j=1}^{n} \left(1 + \frac{1}{m(n-j+1)}\right)^{-m} \underset{m \to +\infty}{\longrightarrow} 1 - \exp\left(-\sum_{j=1}^{n} \frac{1}{j}\right) \underset{n \to +\infty}{\longrightarrow} 1, \end{aligned} $$

where the first limit is taken for any fixed $n \ge 1$.

*Proof of Proposition 40.* A classical result about the order statistics of a sample of exponential random variables [53] shows that for any $i \in [m]$,

$$ S_{(\ell:n),i} \stackrel{d}{=} \frac{1}{\lambda} \sum_{j=1}^{\ell} \frac{E_{j,i}}{n-j+1} $$

where the $(E_{j,i})_{1 \le j \le n}$ are independent standard exponential variables. Therefore, we have

$$ \begin{aligned} \mathbb{P}(Y \in \hat{\mathcal{C}}_{\ell, \dots, \ell}^{\text{Avg}}(X)) &= \mathbb{E} \left[ F_S \left( \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) \right] \\ &= 1 - \mathbb{E} \left[ \exp \left( -\frac{\lambda}{m} \sum_{i=1}^{m} S_{(\ell:n),i} \right) \right] \\ &= 1 - \mathbb{E} \left[ \exp \left( -\frac{1}{m} \sum_{i=1}^{m} \sum_{j=1}^{\ell} \frac{E_{j,i}}{n-j+1} \right) \right] \\ &= 1 - \mathbb{E} \left[ \exp \left( -\sum_{j=1}^{\ell} \sum_{i=1}^{m} \frac{E_{j,i}}{m(n-j+1)} \right) \right] \\ &= 1 - \prod_{j=1}^{\ell} \mathbb{E} \left[ \exp \left( -\sum_{i=1}^{m} \frac{E_{j,i}}{m(n-j+1)} \right) \right] = 1 - \prod_{j=1}^{\ell} \left(1 + \frac{1}{m(n-j+1)}\right)^{-m}. \end{aligned} $$

For the last equality, since $1/(m(n-j+1))$ is positive, $E_{j,i}/[m(n-j+1)]$ follows an exponential distribution with parameter $m(n-j+1)$. Therefore, $\sum_{i=1}^{m} \frac{E_{j,i}}{m(n-j+1)}$ follows a Gamma distribution with parameter $(m, m(n-j+1))$ and the value at $-1$ of its moment generating function is equal to $(1 + \frac{1}{m(n-j+1)})^{-m}$ since $-1 < m(n-j+1)$. $\square$

# Appendix J: Additional experimental results

## J.1. Generic comparison, equal $n_j$

In this section, we provide additional results in the generic setting of Section 6.1.
**Proposition 40.** Suppose that Assumption 1 holds true. When the scores $S_{i,j}$, $S$ are independent with an exponential distribution with parameter $\lambda > 0$, for any $\ell \in [n]$, we have

$$ \mathbb{P}(Y \in \hat{C}_{\ell, \dots, \ell}^{\text{Avg}}(X)) = 1 - \prod_{j=1}^{\ell} \left(1 + \frac{1}{m(n-j+1)}\right)^{-m}. \quad (111) $$

Proposition 40 shows that when the scores are exponential (and using this knowledge), it is possible to choose $\ell$ such that the expected coverage of $\hat{C}_{\ell, \dots, \ell}^{\text{Avg}}$ is larger than $1 - \alpha$, provided that $m$ and $n$ are large enough. Indeed, by Eq. (111),

$$ \begin{aligned} & \max_{\ell \in [n]} \mathbb{P}(Y \in \hat{C}_{\ell, \dots, \ell}^{\text{Avg}}(X)) \\ &= \mathbb{P}(Y \in \hat{C}_{n, \dots, n}^{\text{Avg}}(X)) \\ &= 1 - \prod_{j=1}^{n} \left(1 + \frac{1}{m(n-j+1)}\right)^{-m} \underset{m \to +\infty}{\longrightarrow} 1 - \exp\left(-\sum_{j=1}^{n} \frac{1}{j}\right) \underset{n \to +\infty}{\longrightarrow} 1, \end{aligned} $$

where the first limit is taken for any fixed $n \ge 1$.

*Proof of Proposition 40.* A classical result about the order statistics of a sample of exponential random variables [53] shows that for any $i \in [m]$,

$$ S_{(\ell:n),i} \stackrel{d}{=} \frac{1}{\lambda} \sum_{j=1}^{\ell} \frac{E_{j,i}}{n-j+1} $$

where the $(E_{j,i})_{1 \le j \le n}$ are independent standard exponential variables. Therefore, we have

$$ \begin{aligned} \mathbb{P}(Y \in \hat{C}_{\ell, \dots, \ell}^{\text{Avg}}(X)) &= \mathbb{E} \left[ F_S \left( \frac{1}{m} \sum_{j=1}^{m} S_{(\ell:n),j} \right) \right] \\ &= 1 - \mathbb{E} \left[ \exp \left( -\frac{\lambda}{m} \sum_{i=1}^{m} S_{(\ell:n),i} \right) \right] \\ &= 1 - \mathbb{E} \left[ \exp \left( -\frac{1}{m} \sum_{i=1}^{m} \sum_{j=1}^{\ell} \frac{E_{j,i}}{n-j+1} \right) \right] \\ &= 1 - \mathbb{E} \left[ \exp \left( -\sum_{j=1}^{\ell} \sum_{i=1}^{m} \frac{E_{j,i}}{m(n-j+1)} \right) \right] \\ &= 1 - \prod_{j=1}^{\ell} \mathbb{E} \left[ \exp \left( -\sum_{i=1}^{m} \frac{E_{j,i}}{m(n-j+1)} \right) \right] = 1 - \prod_{j=1}^{\ell} \left(1 + \frac{1}{m(n-j+1)}\right)^{-m}. \end{aligned} $$

For the last equality, since $1/(m(n-j+1))$ is positive, $E_{j,i}/[m(n-j+1)]$ follows an exponential distribution with parameter $m(n-j+1)$. Therefore, $\sum_{i=1}^{m} \frac{E_{j,i}}{m(n-j+1)}$ follows a Gamma distribution with parameter $(m, m(n-j+1))$ and the value at $-1$ of its moment generating function is equal to $(1 + \frac{1}{m(n-j+1)})^{-m}$ since $-1 < m(n-j+1)$. $\square$

# Appendix J: Additional experimental results

## J.1. Generic comparison, equal $n_j$

In this section, we provide additional results in the generic setting of Section 6.1.
<figure><img src="image_15.png" /><figcaption>FIG 10. CentralM: log-log plot of ΔE as a function of m (left) or n (right). Lines show the approximation log ΔE ≈ log(c₁) – γ₁ log(m) – δ₁ log(n) with c₁, γ₁, δ₁ given by Table 1.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>FIG 11. QQM: log-log plot of ΔE as a function of m (left) or n (right). Lines show the approximation log ΔE ≈ log(c₁) – γ₁ log(m) – δ₁ log(n) with c₁, γ₁, δ₁ given by Table 1.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>FIG 12. QQM-Fast: log-log plot of ΔE as a function of m (left) or n (right). Lines show the approximation log ΔE ≈ log(c₁) – γ₁ log(m) – δ₁ log(n) with c₁, γ₁, δ₁ given by Table 1.</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>FIG 10. CentralM: log-log plot of ΔE as a function of m (left) or n (right). Lines show the approximation log ΔE ≈ log(c₁) – γ₁ log(m) – δ₁ log(n) with c₁, γ₁, δ₁ given by Table 1.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>FIG 11. QQM: log-log plot of ΔE as a function of m (left) or n (right). Lines show the approximation log ΔE ≈ log(c₁) – γ₁ log(m) – δ₁ log(n) with c₁, γ₁, δ₁ given by Table 1.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>FIG 12. QQM-Fast: log-log plot of ΔE as a function of m (left) or n (right). Lines show the approximation log ΔE ≈ log(c₁) – γ₁ log(m) – δ₁ log(n) with c₁, γ₁, δ₁ given by Table 1.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>FIG 13. CentralC: 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.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>FIG 14. QQC: 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.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>FIG 15. QQC-Fast: 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.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>FIG 13. CentralC: 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.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>FIG 14. QQC: 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.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>FIG 15. QQC-Fast: 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.</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>FIG 16. CentralC: log-log plot of $\Delta q_{1-\beta}$ as a function of m (left) or n (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ given by Table 1.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>FIG 17. QQC: log-log plot of $\Delta q_{1-\beta}$ as a function of m (left) or n (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ given by Table 1.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>FIG 18. QQC-Fast: log-log plot of $\Delta q_{1-\beta}$ as a function of m (left) or n (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ given by Table 1.</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>FIG 16. CentralC: log-log plot of $\Delta q_{1-\beta}$ as a function of m (left) or n (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ given by Table 1.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>FIG 17. QQC: log-log plot of $\Delta q_{1-\beta}$ as a function of m (left) or n (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ given by Table 1.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>FIG 18. QQC-Fast: log-log plot of $\Delta q_{1-\beta}$ as a function of m (left) or n (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ given by Table 1.</figcaption></figure>
<figure><img src="image_24.png" /><figcaption>FIG 19. Conditionally-valid algorithms: log-log plot of $\Delta q_{1-\beta}$ as a function of $m$ (left) or $n$ (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ 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>

## J.2. Generic comparison, different $n_j$

This subsection provides experimental results that complement the ones of Section 6.1.2.

### J.2.1. With random $n_j$

We start with experiments using $n_j$ (random) that are not equal. Figure 20 gives the values of the $n_j$ for $m \in \{4, 25\}$ in the experiments of Section 6.1.2. Figure 21 provides an equivalent of Figure 6 right (performance of conditionally-valid algorithms as a function of $m$) with $\Delta q_{1-\beta}$ instead of $\Delta q_{\beta}$.

<figure><img src="image_25.png" /><figcaption>FIG 20. Experiment of Section 6.1.2: values of $(n_j)_{j \in [m]}$ in increasing order. Left: $m = 4$. Right: $m = 25$.</figcaption></figure>
<figure><img src="image_24.png" /><figcaption>FIG 19. Conditionally-valid algorithms: log-log plot of $\Delta q_{1-\beta}$ as a function of $m$ (left) or $n$ (right). Lines show the approximation $\log \Delta q_{1-\beta} \approx \log(c_3) - \gamma_3 \log(m) - \delta_3 \log(n)$ with $c_3, \gamma_3, \delta_3$ 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>

## J.2. Generic comparison, different $n_j$

This subsection provides experimental results that complement the ones of Section 6.1.2.

### J.2.1. With random $n_j$

We start with experiments using $n_j$ (random) that are not equal. Figure 20 gives the values of the $n_j$ for $m \in \{4, 25\}$ in the experiments of Section 6.1.2. Figure 21 provides an equivalent of Figure 6 right (performance of conditionally-valid algorithms as a function of $m$) with $\Delta q_{1-\beta}$ instead of $\Delta q_{\beta}$.

<figure><img src="image_25.png" /><figcaption>FIG 20. Experiment of Section 6.1.2: values of $(n_j)_{j \in [m]}$ in increasing order. Left: $m = 4$. Right: $m = 25$.</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>FIG 21. Different $n_j$; log-log plot of the performance ($\Delta q_{1-\beta}$) of the conditionally-valid algorithms considered in Section 6.1.2 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$ describes 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>

### J.2.2. Algorithms 5 and 6 with $n_j = N/m$

As in Section 6.1.2, we now consider Algorithms 5 and 6 with $n_j = N/m$ for every $h \in [m]$, that we call QQM-(N/m) and QQC-(N/m). Table 4 gives the values of the coefficients of the robust log-linear regression obtained for QQM-(N/m) and QQC-(N/m) (following the exact same procedure as for QQM, QQM-Fast, QQC, and QQC-Fast, as described in Section 6.1.1). In Figure 22, we compare the performances (measured by $\Delta E$) of the marginally-valid algorithms QQM, QQM-Fast, and QQM-(N/m), as a function of either $m$ or $n := N/m$. In Figure 23, we compare the performances (measured by $\Delta q_\beta$) of the conditionally valid algorithms QQC, QQC-Fast, and QQC-(N/m), as a function of either $m$ or $n = N/m$.

<table><caption>TABLE 4</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>QQM-(N/m)</td><td>0.248</td><td>0.952</td><td>0.521</td><td>0.259</td><td>0.467</td><td>0.509</td><td>0.417</td><td>0.520</td><td>0.511</td></tr><tr><td>QQC-(N/m)</td><td>0.408</td><td>0.521</td><td>0.507</td><td>0.462</td><td>0.992</td><td>0.552</td><td>0.713</td><td>0.507</td><td>0.505</td></tr></tbody></table>

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_\beta$ or $\Delta q_{1-\beta}$, for QQM-(N/m) and QQC-(N/m), introduced in Section 6.1.2; See also text of Section 6.1.1 for details.
<figure><img src="image_26.png" /><figcaption>FIG 21. Different $n_j$; log-log plot of the performance ($\Delta q_{1-\beta}$) of the conditionally-valid algorithms considered in Section 6.1.2 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$ describes 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>

### J.2.2. Algorithms 5 and 6 with $n_j = N/m$

As in Section 6.1.2, we now consider Algorithms 5 and 6 with $n_j = N/m$ for every $h \in [m]$, that we call QQM-(N/m) and QQC-(N/m). Table 4 gives the values of the coefficients of the robust log-linear regression obtained for QQM-(N/m) and QQC-(N/m) (following the exact same procedure as for QQM, QQM-Fast, QQC, and QQC-Fast, as described in Section 6.1.1). In Figure 22, we compare the performances (measured by $\Delta E$) of the marginally-valid algorithms QQM, QQM-Fast, and QQM-(N/m), as a function of either $m$ or $n := N/m$. In Figure 23, we compare the performances (measured by $\Delta q_\beta$) of the conditionally valid algorithms QQC, QQC-Fast, and QQC-(N/m), as a function of either $m$ or $n = N/m$.

<table><caption>TABLE 4</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>QQM-(N/m)</td><td>0.248</td><td>0.952</td><td>0.521</td><td>0.259</td><td>0.467</td><td>0.509</td><td>0.417</td><td>0.520</td><td>0.511</td></tr><tr><td>QQC-(N/m)</td><td>0.408</td><td>0.521</td><td>0.507</td><td>0.462</td><td>0.992</td><td>0.552</td><td>0.713</td><td>0.507</td><td>0.505</td></tr></tbody></table>

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_\beta$ or $\Delta q_{1-\beta}$, for QQM-(N/m) and QQC-(N/m), introduced in Section 6.1.2; See also text of Section 6.1.1 for details.
<figure><img src="image_27.png" /><figcaption>FIG 22. 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) − γ log(m) − δ log(n). Plain lines and dots correspond to n = 10 (left) or m = 10 (right). Dashed lines and diamonds correspond to n = 10⁴ (left) or m = 10⁴ (right).</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>FIG 23. Conditionally-valid algorithms: log-log plot of Δqβ as a function of m (left) or n (right). Lines show the approximation log Δqβ ≈ log(c) − γ log(m) − δ log(n). Plain lines and dots correspond to n = 10 (left) or m = 10 (right). Dashed lines and diamonds correspond to n = 10⁴ (left) or m = 10⁴ (right).</figcaption></figure>

### J.3. Real data: additional results on individual data sets

In this section, we present in Figures 24 to 31 the results of the experiments of Section 6.2 on individual data sets.

<figure><img src="image_29.png" /><figcaption>FIG 24. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits. The miscoverage is α = 0.1, β = 0.2, and the calibration set is split into m = 80 disjoint subsets of equal size n = 10. The white circle represents the mean and the name of the data set is located at the top of each plot.</figcaption></figure>
<figure><img src="image_27.png" /><figcaption>FIG 22. 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) − γ log(m) − δ log(n). Plain lines and dots correspond to n = 10 (left) or m = 10 (right). Dashed lines and diamonds correspond to n = 10⁴ (left) or m = 10⁴ (right).</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>FIG 23. Conditionally-valid algorithms: log-log plot of Δqβ as a function of m (left) or n (right). Lines show the approximation log Δqβ ≈ log(c) − γ log(m) − δ log(n). Plain lines and dots correspond to n = 10 (left) or m = 10 (right). Dashed lines and diamonds correspond to n = 10⁴ (left) or m = 10⁴ (right).</figcaption></figure>

### J.3. Real data: additional results on individual data sets

In this section, we present in Figures 24 to 31 the results of the experiments of Section 6.2 on individual data sets.

<figure><img src="image_29.png" /><figcaption>FIG 24. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits. The miscoverage is α = 0.1, β = 0.2, and the calibration set is split into m = 80 disjoint subsets of equal size n = 10. The white circle represents the mean and the name of the data set is located at the top of each plot.</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>FIG 25. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits. The miscoverage is $\alpha = 0.1$, $\beta = 0.2$, and the calibration set is split into $m = 10$ disjoint subsets of equal size $n = 80$. The white circle represents the mean and the name of the data set is located at the top of each plot.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>FIG 26. Same as Figure 24 (see its caption) with $m = 80$ and $n = 10$.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>FIG 27. Same as Figure 25 (see its caption) with $m = 10$ and $n = 80$.</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>FIG 25. Coverage (left) and average length (right) of prediction intervals for 50 random learning-calibration-test splits. The miscoverage is $\alpha = 0.1$, $\beta = 0.2$, and the calibration set is split into $m = 10$ disjoint subsets of equal size $n = 80$. The white circle represents the mean and the name of the data set is located at the top of each plot.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>FIG 26. Same as Figure 24 (see its caption) with $m = 80$ and $n = 10$.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>FIG 27. Same as Figure 25 (see its caption) with $m = 10$ and $n = 80$.</figcaption></figure>
<figure><img src="image_33.png" /><figcaption>FIG 28. Same as Figure 24 (see its caption) with *m* = 80 and *n* = 10.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>FIG 29. Same as Figure 25 (see its caption) with *m* = 10 and *n* = 80.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>FIG 30. Same as Figure 24 (see its caption) with *m* = 40 and *n* = 10.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>FIG 31. Same as Figure 25 (see its caption) with *m* = 10 and *n* = 40.</figcaption></figure>
<figure><img src="image_33.png" /><figcaption>FIG 28. Same as Figure 24 (see its caption) with *m* = 80 and *n* = 10.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>FIG 29. Same as Figure 25 (see its caption) with *m* = 10 and *n* = 80.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>FIG 30. Same as Figure 24 (see its caption) with *m* = 40 and *n* = 10.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>FIG 31. Same as Figure 25 (see its caption) with *m* = 10 and *n* = 40.</figcaption></figure>