Differentially Private Conformal Prediction via Quantile Binary Search
Authors: Ogonnaya Michael Romanus
Roberto Molinari
Venue: Accepted by TMLR ()

Abstract: Differentially Private (DP) approaches have been widely explored and implemented for a broad variety of tasks delivering corresponding privacy guarantees in these settings. While most of these DP approaches focus on limiting privacy leakage from training data, there are fewer approaches that consider leakage when procedures involve \textit{calibration data} which is common in uncertainty quantification through Conformal Prediction (CP). Since there is a limited amount of approaches in this direction, in this work we deliver a general DP approach for CP that we call Private Conformity via Quantile Search (P-COQS). The proposed approach adapts an existing randomized binary search algorithm for computing DP quantiles in the calibration phase of CP thereby guaranteeing privacy of the consequent prediction sets. This however comes at a price of marginally under-covering with respect to the desired $(1 - \alpha)$-level when using finite-sample calibration sets (although broad empirical results show that the P-COQS generally targets the required level in the considered cases). Confirming properties of the adapted algorithm and quantifying the approximate coverage guarantees of the consequent CP, we conduct extensive experiments to examine the effects of privacy noise, sample size and significance level on the performance of P-COQS compared to existing alternatives. In addition, we empirically evaluate our approach on several benchmark datasets, including CIFAR-10, ImageNet and CoronaHack. Our results suggest that the proposed method is robust to privacy noise and performs favorably with respect to the current DP alternative in terms of \textit{empirical coverage}, \textit{efficiency}, and \textit{informativeness}. Specifically, the results indicate that P-COQS produces smaller conformal prediction sets while simultaneously targeting the desired coverage and privacy guarantees in all these experimental settings.

Published in Transactions Machine Learning Research (02/2026)
Differentially Private Conformal Prediction via Quantile Binary Search
Ogonnaya M. Romanus
romanusogonnaay com
Department of Mothematics and Statistics
Auburn University
Roberto Molinari
robmol@narilhannarr.ccmm edu
Department of Mathematics and Statistics Auburn University
Reviewed OpenReview: https: // o/ppr//veeeeee.e..mm net/ forum? id= IX7tNOuc.J
Abstract
Differentially Private (DP) approaches have been widely explored and implemented for broad variety of tasks delivering corresponding privacy guarantees in these settings. While most of these DP approaches focus on limiiing privacy leakage from training data, there are fewer approaches that consider Icakage when procedures involve calibration data which common in uncertainty quantification through Conformal Prediction (CP). Since there is a limited amount of approaches this direction, in this work we deliver general DP approach for CP that we call Pri- vate Conformity via Quantile Search (P-COQS). The proposed approach adapts existing randomized binary search algorithm for computing DP quantiles in the calibration phase of CP thereby guarantccing privacy of the consequent prediction sets. This however comes at a price of marginally under-covering with respect lo the desired (1 - a) level when using finite-sample calibration sets (although broad empirical results show that the P-COQS generally targets the roquired level in the considered cases). Confirming properties of the adapted algorithm and quan- tifying the approximate coverage guarantees of the consequent. CP, conduct extensive experiments to examine the effects of privacy noise, sample size and sig- nificance level on the performance of P-COQS compared to existing alternatives. In addition, we empirically evaluate our approach on several benchmark datasets, including CIFAR-10, ImageNet and CoronaHack. Our results suggest that the pro- posed hot is robust to privacy noise and performs favorably with respect to the current DP alternative in terms of empirical coverage, efficiency, and informative- ness. Specifically, the results indicate that P-COQS produces smaller conformal prediction sets while simultaneously targeting the desired coverage and privacy guarantees in all these experimenial settings.

---

Published in Transactions Machine Learning Research (02/2026)
1 Introduction
In high-stakes domains such as health care, criminal justice and financial risk assessment (among others) machine learning models are increasingly being used to guide decision-making processes. These approaches are commonly built to produce single-point predictions without quantifying un- certainty, which could lead to overconfident and unreliable outcomes with negative consequences for the following decisions. Many techniques have been proposed to address the need for reliable uncertainty quantification, including (but not limited to) Bayesian neural networks, ensemble meth- al. 2017 Osband et al. 2016 Gal & Ghahramani] 2016 Kendall & G 2017). While these methods can offer meaningful uncertainty estimates, they often rely on strong modeling assumptions, are computationally intensive, or lack rigorous coverage guarantecs (especially under model misspocifi- cation or when applied oul-of-distributtion) Conformal Prediction (CP) addresses various of these limitations by generating prediction sels, that is, subsets of the response space y that, under the assumption of exchangeability, are guaranteed to contain the true response with a user-specified probability 1- aa where a E (0. These sets provide a reliable and model-agnostic framework for uncertainty quantification, making them increasingly attractive in safely-critical applical ions (see
ods, and dropout- based approximations (sec c.g. Blundell ct al.] 2015 Lakshminarayanan
e.g. [Uddin & Lofstrom 2023 Astigarraga et al. 2025 Tuwani & Beam 2023 Olsson et al. 2022
While conformal methods require independent and identically distributed (iid) data for exact guar- antees, recent extensions have begun to explore how to adapt them to distribution shift settings with approximate validity (see e.g. Tibssirani et al., 2019 2024
Gibbs & Candès 2021 Jonkers et al..
However, while CP provides statistical reliability, its reliance calibration data introduces privacy risks since any publicly released statistic based on these data could be exploited by adversary. Morcover, when training models on data that collect individual-level information, these models lend to preserve individual-specifie information, and some of them, such as deep neural net net works, are known to memorize training examples (Fredrikson et al. 2015 Carlini et al.] 2021), enabling adversaries to extract sensitive information via model inversion (Fredrikson ct al.) 2015) or mem-
bership inference attacks (Shokri et al., 2017). This poses a signilicant challenge also in regulated domains (e-g., under GDPR, HIPAA, or CCPA), where models must not leak information about individuals in the training calibration sets. To address these issues, Differential Privacy (DP) (Dwork] 2006) has emerged as one of the main frameworks for privacy-preservinn machine-learning, ensuring (with high probability) that model outputs do not reveal whether any individual's data was included in the training set. However, existing DP frameworks focus primarily on protecting the training phase, leaving the calibration phase (and thus the CP step) vulnerable to privacy breaches. Given this issue, there are nevertheless very few existing approaches that ensure that CP procedures can provide DP guarantecs while maintaining reasonable performance in terms of uncertainty quantification metrics and computational efficiency (see Angelopoulos et al. 2022 Hence, this work aims to further contribute to the goal of uncertainty quantification under privacy constraints by adapting an existing DP quantile selection approach based on binary search (Huang ct al., 2021 and using it as a subroutine to deliver CP sets that guarantec privacy. We confirm the iheoretical ical properties of the resulting CP procedure and highlight its favorable experimental performance compared to the few existing alternatives, both in terms of uncertainty quantification and computational efficiency.
2

---

Published in Transactions Machine Learning Research (02/2026)
2
Related Work
The idea. behind CP was first described in Vovk et al. (2005) followed by different papers that developed its theory and applications (see Vovk (2015). Vovk (2002), Vovk al. (2017) Vovk & Petej (2022), and the references therein). Based on these, considerable attention has been paid in recent years to adapt CP to different settings and deliver additional applied and theoretical results (see Angelopoulos & Bates
2021 for recent detailed review). Despite these different research outputs, little attention has been devoted to guaranteeing privacy for the calibration data through protection of the derived non- non-conformity scores used to deliver the prediction sets for uncertainty quantification. To the best of the authors' knowledge, the only existing work related to the central DP approach we present in this paper is that of Angelopoulos et al. (2022) where they privatize the CP procedure by discretizing the non-conformity scores inlo bins and applying the exponential mechanism (MeSherry & Talwar (007)) to select DP quantile which is then used to form the prediction sets, More specifically, to maintain coverage guarantees under c-DP, the target quantile is adjusted (inflated) to account for added noise. This ensures both privacy (via DP) and valid coverage, albeit with potentially larger prediction sets due to the privacy-utility trade-off. A possible practical limitation of this proposed approach lies in the choice of the optimal number of bins, as well as a hyperparameter that needs to be tuned minimize the inflated quantile to achieve the smallest possible prediction set. Although procedures have been determined to compute these in an optimal manner, they can potentially increase the time complexity of this method. In recent years there have been few other CP approaches proposed in the set setting of federated learning (Humberl) et al. 2023) and local DP (Penso et al. 2025 however, these do not fit in the central DP framework of this paper.
3 Preliminaries
3.1 Conformal Prediction
To define the framework of the proposed method, let us consider n exchangeable data points {(x,, Y1), .... (X,, with X; E X being a d-dimensional input vector and Y; E y being the larget variable. Using the basic splil CP (Papadopoulos et al. 2002 Lei al.] 2015 we partition these points into training set with Ptrain observations (to fit model of choice Terain observations to quantify prediction uncertainty (as-
f) and calibration set with Peaa suming test data is taken from another sample). If we let I = of the ibservations, then we can define Teal C I as the index set of observations in the calibration set. Assuming that we have trained a model ff on the training set, the goal of CP is to compute non-conformitty scores 8; = s(,,, J) f) measure the discrepancy between the model's prediction and the true target value such that lower scores suggest. better agreement, that is, better predictions from the trained model f. Therefore we now have a set of non-conformity scores S = {81...., } on which a E (0, 1) being the significance level which represents the amount of errors (in percentage) that the model is allowed to make. We denote this quantile as g and let its dependence on the significance level a be implicit. Once the scores are computed, we can therefore sort them in incrcasing ordor (that is, {it S ... S H/)aal)) and estimate this quantile by selecting the score in the y.th position where we define
represent the index set
for each calibration point (X,, Vi E Teat. These scores
can obtain a-quantiles with
[[1 -a)(aalal + 1)1, with [e] representing the smallest integer greater than x, loading to I 8[r]- Suppose that we now have new test data point X the resulting prediction
3

---

Published in Transactions Machine Learning Research (02/2026)
set for the target Yest defined as:
C(Xust)) {y EY: 8 Y, s 1)
Under the assumption of exchangeability of the data points, this set guarantees the coverage prob- ability P(Ytest E C(Xtest)) 2 1- a, where the probability is taken over the n + 1 data points (X,, Vi),..., (Xn, Yn), (Xest, Ytest)- For further details and extensions we refer the reader to An- gelopoulos & Bates (2021).
3.2 Differential Privacy
Differential Privacy (DP) currently represents one of the main frameworks for privacy protection with mathematically provable guarantees. More in detail, a randomized mechanism M is said to be (c, 5)-DP if, for all neighboring datasets D and D' (that is, datasets with Hamming distance ADD = 1) and for all mcasurable subsets Q of the output space, we have that
P[M(D) E Q S <'P( E Q 5.
There are many variations of this framework, including Gaussian Differential Privacy which benefits from a series of nice additional properties compared to the above (c, 6)-DP (Dwork 2006 Dong et al. 2022). For the purpose of this work, rely specific version of DP defined below.
Definition ZonneConneetreted Differential Privacy, Bun & Steinke (0166). For p > 0, a ron- domized mechanism M satisfies (p, 00- Coneeeeccneeeeeeeed Differential Privacy (sCDP) if for all neighboring datasets D and D and for all 1 > 1, the Rényi divergence D of order n satisfies:
D,(M(D))M((') sm.
Unlike (e,8)-DP, p-zCDP is tight under sequential composition without the need for the advanced composition theorem, which may consume extra privacy budget. Nevertheless, there is direct relationship between the (e, d)P framework and the zCDP framework: indeed. if .M satisfies P zCDP, then for 8 0, M satisfies (c, 6)-DP with e p 2/plog(1/8) (see Near & Abuah 2021 ). Hence, the latter implies the former. In particular, randomized mechanism M satisfies (c, DP if and only satisfics c-CDPP Bun & Steinke 2016).
4 P-COQS: Private Conformity via Quantile Search
As highlighted in Angelopoulos et al. (0022) the release of the non-conformity score quantile O or of the prediction sets based on this quantile can compromise the privacy of individuals in the calibration set. Therefore, solution to this problem is to directly release DP quantile its corresponding prediction sets, which would also preserve DP based on the privatized quantile. While the existing alternative in Angelopoulos et al. (2022) employs the exponential mechanism to sample a DP quantile, this work relies on direct adaptation of the DP binary search algorithm presented in Huang et al. (2021). More spocifically, the latter algorithm releases a DP quantile by employing a noisy count function (denoted as NoisyRC) within a binary search procedure run on a sequence of ordered integers. particular, the function NoisyRC([a, b), returns a noisy count of g E Ja, b), where G is set containing ordered integers that are considered sensitive and hence must
4

---

Published in Transactions Machine Learning Research (02/2026)
be accessed privately (see Huang et al., 2021). However, since in this work our sequences are not integers (given that the non-conformity scores continuous), we adapt this DP quantile selection approach in straightforward manner and, for completeness, reproduce their adapted approach in Algorithm 1 with some modification to suit our application.
Algorithm 1 Adapted PrivQuant Algorithm of Huang et al. (2021)
Require: Non-conformity scores S = {si,.... .:.....: Sneal:
significance level (0, 1), lower and upper bounds for non-conformity scores [a, b), A > (small positive value, default A = 10-10), privacy
parameter p
Ensure: DP quantile q DP
1: Fix r= = [(1 (neal + 1)] and N [log2 (4-1/a)]
2: Initializo: left a, right t b, i
3: while i < do
4: mid + right
5: c + NoisyRC([a, mid], S)
6: if c o then
7:
left mid
8:
else
9: right mid
10: end if
11:
i i+1
12: end while
13 return g DP
right
2
Broadly speaking, Algorithm perffrrs a binary search over the interval b] (often corresponding to [0. 1] in the case of classification lasks) by iteratively narrowing the search space to localize the quantile of interest while preserving privacy through a randomized counting mechanism. More specifically, at each itcration, the algorithm evaluates a midpoint and calls the function NoisyRC, which returns a DP count of the number of non-conformily scores (in S) less than or equal to the midpoint. This count guides the search by indicating whether the true quantile lies to the left or right of the midpoint. The process continues until it reaches iteration N which the maximum number of iterations allowed to ensure p-zCDP, Indeed, stated further on, the DP noise used for the function NoisyRC needs to be scaled to the number of iterations in Algorithm | Since we would ideally want the algorithm to terminate when the interval length is smaller than a small value A (i.e. right- - left < A), the fixed number of iterations N needed to reach this point is such that 0-0/22 < A (since the interval is divided by two after each iteration) which, solving for N, gives us
N [log [/]]]
With this representing the exact number of iterations to guarantee the required condition, Algorithm I returns the midpoint as the private quantile estimate DP
Remark 1. As for all DP settings, the choice of the bounds [a, b) have to either be made a-priori (before seeing the data) or also have to be determined through DP approaches. For classification problems, the bounds for non-conformitty scores are naturally defined (in general) on the [0, 1| space. In regression settings however, non-conformity scores such as absolute or squared residuals are unbounded, and thus a finite range (a, b) must be imposed. A common and privacy-safe choice is to
5

---

Published in Transactions Machine Learning Research (02/2026)
fiz a= and truncate scores obove robust upper bound estimated through differentialiy private procedure with small additional privacy budget Pb. In the latter the total privacy cost then becomes Ptotal p Pb- In practice, using conservative public bound privately estimated high quantile yields similar utility while preserving the formal PtPt guarantee.
the DP conformal prediction Once this quantile is obtained, following the definition in Section 3.1 set is simply given by:
CDP (X test.) = { EY 8 Y, S pr)
(1)
We refer to the above procedure as Private Conformity via Quantile Search (P-COQS) which therefore built on the adaptation described in Algorithm and the consequent use of the resulting The entire P-COQS procedure is summarized Algorithm
DP quantile pPP equation 1
Algorithm 2 P-COQS
Require: Training data Dirain {(X,, (X Y meram )}, calibration data Deal {(X1, Yı). ...., (Xnexi Yeaa) }. test point Xtest, significance level a (0, 1), bounds [a, b], res- olution A > O, privacy parameter
Ensure: DP prediction set CDP
1: Train model on Dirain to obtain
2: Compute conforrnyyy scores =
from Deal using
3: Run Algorithm 1 to obtain qDP
4: Define
(Y E 3: s(Xrest ř, s DPJ
3: return CDP
Let us now focus on the properties P-COQS and, for completeness, we start by studying the error bound and DP properties of Amgorithm [ which directly follow from the properties the PrivQuant algorithm in Huang et al. (2021). Indeed, while the latter algorithm tailored search over positive integers, as mentioned earlier, and any set of bounds (a, b] on the real line. Let us therefore discuss (confirm) the DP properties of this adaptation and, to do so, let us first define the noisy count function as
I the latter to any ordered data type
NoisyRC((a, mid], S) = ca n (a, mid)) +W (0, [1og2(--//))
(2)
2p
where p > is the privacy parameter under zCDP, with the sensitivity scaled to the maximum (considering that count query l--snnitivityy is 1), and card number of itcrations N for Algorithm | denotes the cardinality of set. Let now denole u b-a/a and let represent the standard normal CDF. Moreover, let M(A) max, # { 8; E (t,++A) represent the maximum number of calibration scores inside A-interval. Then, adapting directly from Huang et al. (022]) h, the
following proposition holds.
Proposition 1. Algorillm 7 using equation is p-cCDP and, with probabilily at least 1 -B, relurns a quantile whose rank error is bounded by
[1)
2 (/log2(1) ([0gg(1)])
I r- + M(A), where
log
P
6

---

Published in Transactions Machine Learning Research (02/2026)
Proof. Since the sensitivity of the range query card(S n [a, mid)) is 1, adding Gaussian noise O., N 2016), after N calls the whole algorithm satisfies p-xCDP. Now, let W ~ o0 with o² N/(2p)- Then the error between the true count and its noisy version is distributed as W. For one call we have that
2p guarantees p/N-xDDP per call, where N = [log((u)] By composition (Bun & Steinke
Pr( > -*) S 2e 2 - ((20))
Applying a union bound over N calls we consequently have
Pr Pr(3i: [. 7*) S 22Ne-r" To ensure this probability is at most B, it suffices that
T" 2 ov 2 log
Finally, since the algorithm stops with an interval of length at most A, the true count can vary by at most ((A) within this interval so, substituting x² = N/(pp) and N = [logg(u)], the final rank error is at most 5" + (().
Remark 2. If the score distribution admits a density bounded by L on [a, b), then we have that [[M(A)] S LA Neal- Consequently, choosing A c/Teca implies that B[M(A)) I eL,, so that the dominant term in the rank error becomes T* Hence, smaller A increases (and thuss T"), while larger A increnses M(A). Consequently, A should balance the trade-off between the DP-noise component (r" (Iog(I/Ai) and the discretization component (M( Aneal in expectation). However, in contrast to other possible DP quantile approaches which use histograms (and therefore require careful tuning of global bin width), the choice of A here is considerably simpler. Indeed, A only controls the numerical resolution of the binary search and does not define a partition of the score space. As a result, any A in the regime x c//ecal leads to similar behavior, making the tuning of A substontially easier than selecting an "optimal" " bin size in histogram- baasd approaches.
[log2((b aa/
Remark 3. With respect to the DP noise error term T", an equivalent (but slightly sharper) for- mulation avoids the wnion bound and uses the Gaussian quantile. In that case,
T" -= (1
[w)] 2p
T (11
0 2[logg(w)1
2N
Remark 4. Noling that [log2 w/ S logg u + 1, we have that
logz u + 1
2(log2 1)
log u plog 2
log (ogloou+O(1)) O(1))
log
Therefore, with p, B ftaed, as u + oo (L.e. as + 0) we have that
(V log u log log u
7" =
which matches the polylogarithmic order in Huang et al. 2021 (near-optimal up to constants).
7

---

Published in Transactions Machine Learning Research (02/2026)
Remark 5. A natural question whether empirical membershiip-ttference attacks (MLAs) can be used to validate pricacy leakage from releasing DP quantile. Since P-COQS relies the adapted PriuQuant mechanism in Algorithm 1 which satisfies p-zCDP and therefore inherits explicit (E,6)-DP guarantees, the worst-case success probability of any MTA is already upper-bounded by the theoretical DP conversion bounds (Yeom et al., 2015). Thus, MIAs canmot reveal leakage beyond what the DP guarantee already certifies. Nevertheless, MIAs can serve as an empirical diagnostic to confirm that the observed atlack advantage is consistent with the theoretical bound, and therefore may be useful in high-risk practical deployments. This investigation is however left for future work.
Appendix E provides some empirical results on the rank errors of Algorithm based on the settings presented later in Section 5.1 Following the above, and for sake of completeness, we also provide the computational complexity of this algorithm.
Proposition 2. Algorillom runs in
o 0( Neal log b -
)=))
time and requires ((1) memory beyond the storage of the non-conformity scores.
Proposition is a direct consequence of the binary search routine over [a, bJ that stops once the interval length is at most A. Knowing that the number itcrations is N [ogg((b (2bb()()AA]]) at every iteration the algorithum makes a single call to NoisyRC([a, mid], S), which computes a range count over the Real calibration scores and adds Gaussian noise. With the scores stored in a simple array, this range count is a linear-time operation, so each iteration costs @(nea); and the total running time is NV = O(rcat log((b a)/ In addition, apart from the stored scores, the algorithm keeps only constant number of scalar variables (e.g., left, right, mid), so the auxiliary memory usage is (L)). Considering this computational complexity, since A is extremely small in practice (c.g., 10 10)1 the number of iterations is commonly around 30-40, making P-COQS computationally negligible compared to training ff or its DP counterpart.
Having studied the rank error the DP binary search subroutine and its computational complexity, we are now able to quantify what exlent the rank associated with the private quantile pP from Algorithm differs from the non-private rank in the calibration data. Based on this, we know that obtaining a p-zCDP quantile ensures that Algorithm preserves the desired privacy level. Moreover, Proposition allows us to explicitly define the DP noise error term T' with high probability (at least 1 1- 9), w which generally dominates ((A) since A is small. We will see that this information can be used and is indeed helpful when determining the coverage guarantees of P-COQS in Algorithm 2 which are stated in Theorem For this purpose, we also define Stest = s(Xtost, Y,
Theorem 1 (Coverage Guarantoc). Let (S1, Stants Stest) be an ezchangeable sequence of non- conformily scores. With probability at least 1 (over the DP noise in Algorillm 7. the P-COQS prediction set CDP (Xr(X)s)t) satisfies:
S (( E CDP (Xtee))) 51-a- a ++1
neat
neca +
If ties are not randomized, the same guarantee holds with the lower bound replaced by 1- r+1
nart1
Proof. Recalling that 7= -* ++++M(1) where 7" is the DP noise term from Proposition I and M (A) is the discrotization term, we have that Algorithm 1 outputs private quantile q DP with rank
8

---

Published in Transactions Machine Learning Research (02/2026)
error T, i.e. 8(r-T) I qPP I S(r+T) By the exchangeability condition of the non-conformity scores, the rank of Steet = s(Xuest. f) among ($1...., S Swest) is uniformly distributed over (1....,Reaal + 1]. Thus, recalling that r = [(1 aneaaall + 1)] and that
E C (Xross)ss)
Stest S q DP
we consequently have:
7 T
S (Stost pPPP)= 2
r T+T Teal
+
where:
L [[1 a)) + 1)] -T
T
2 -1-0
and
nral +
neal +
U (1 a ()) (Real + 1)] +
a-))(noal + 1) 1
T+1
Meal +
Neal +
Oeal +
Therefore this allows us to conclude that
7
1 Neal +
P (Yes
CDP (Xrest) 5 +
Plaa +
Remark 6. Theorem 1 is a marginal coverage result: it holds under exchangeability of ($1,..., Snear Stest) and does not imply slice-wise (e.g., class-conditional or group-conditiona) cov- erage, nor robustness under covariate shift. Extending P-COQS to Mondrian or other conditional conformal frameworks, or studying its behavior under distribution shift, is an interesting direction for future work but beyond the scope of this paper.
Although Theorem does not ensure the coverage probability (1-a), as opposed the method in Angelopoulos et al. (2022) that preserves this standard CP guarantee, it establishes approximate coverage bound with error term of order O(T/nea). While this indeed implies an error margin for the actual coverage, it nevertheless also provides an upper bound to the coverage guarantee which allows to understand how conservative and how efficient the resulting prediction sets can be (see e.g. Lei et al., 2018 Li et al.) 2025). More in detail, this error depends not only on the size of the calibration set but also on the width of the interval [a, b) and the privacy level p under zCDP. Specifically, as shown in Proposition D the coverage error increases with the length of the interval and decreases with the privacy budget. Therefore, achieving accurate coverage requires sufficiently large calibration set when the parameters of the error bound are fixed. Nevertheless, all the experimental results in Section indicate that P-COQS is able to achieve coverage comparable to the non-private conformal prediction method, despite this weaker theoretical guarantee.
Remark 7. As highlighted by Huang et al. (2021), the quantile method adapted in Algorithm is nearly optimal, implying that our results are suboptimal (polylogarithmic) in terms of CP guarantees. Nevertheless, using the bounds in Proposition 4 delivers a practical way to determine the true differentially privale coverage guaranlee with high probability (i.e. 3) without having to inflate the coverage to mitigate the impact of privacy noise (which can negatively impact the informativeness of the CP sets). For erample, suppose that are dealing with classification task where the
9

---

Published in Transactions Machine Learning Research (02/2026)
non-confornity scores lie in the interval [0, 1]. Then by faring the other parometers A and p (e.g.,
A 10-10 and p 0.1) and assuming min..j [s; sj < A (for all i, E (1...., Reat :....., }) and i + j),
following Proposition | the true probability of DP coverage of P-COQS is at least
0.0183
and at most 1 a + 0.0186 guaranteed with probability at least 0.99 (if choosing 8 0.01) and calibration size cl 3000.
Following the above discussion, a straightforward adaptation of the significance level in Algorithm 2 can allow to guarantee the a coverage (with probability at least - -B) as stated in the corollary below.
Corollary 1. Let
a" = max max{0, 0, a Teat +
Then, if we run Algorithm 2 with a in place of a, with probability at least 1 - 3 we have that
P (Yess E CD 2 1 11-00
If ties are not randomized, the same guarantee holds with a max (0,
T+1 noat
The proof of this corollary is direct consequence of the bounds in Theorem I and is therefore omilled. As a result, similarly to Angelopoulos et al. (2022), could also correct P-COQS to achieve the required coverage, although this would be achieved only with high probability 1 1 8-8a as opposed to Angellopoulos et al. (2022) where this coverage is fully guaranteed. More in detail though, the correction in Corollary [ depends on the total rank-crror bound T = T' + (4) where the discretization component M(A) is not directly observable since it depends on the calibration scores. Nevertheless, one can work with a deterministic or probabilistic upper bound on (A) without compromising privacy. For instance, following Remark 2 if the score distribution admits bounded density L on (a, b), then with high probability we have [A)] < L. A Peall and conservative choice such as M() = I. A Teat can be used to adjust a". Alternatively, if no distributional assumption is made, an auxiliary DP histogram over the A-grid can provide private estimate of M(A) at negligible additional privacy cost. This makes the resulting coverage slightly more conservative while still ensuring the nominal
a guarantee with high probability 1 - 3. However, in the following sections we do not make use of this correction since, as shown across all the experimental results, the empirical performance of P-COQS does not appear to be significantly affected by the original approximate guarantee stated in Theorem
5 Experiments
In this section, we evaluate the proposed P- P-COQS under the same experimental setting as An- extend this evaluation with controlled simulation periments. Specifically; we compare P-COQS with the method introduced by Angelopoulos el. al. (2022) (henceforth referred to as EXPONQ) and to an additional benchmark represented by a DP histogram (CDF construction) approach to estimate a private quantile as an alternative subrou- Line for CP (Wasserman & Zhou 20100: we refer to this approach as HISTLAP. Although the properties of the HISTLAP approach have not been formally investigated within a CP framework,
gelopoulos et al. (2022] |
Additionally,
'The code reproduce the experiments this section and R package implementation of P-COQS be found at lhttpe://githu. wwwpseaCmeeeeeeeeee. GSXCC-Groupppcoee
10

---

Published in Transactions Machine Learning Research (02/2026)
it is nevertheless a reasonable alternative to compare to the considered EXPONQ and P-COQS approaches. This being said, we investigate scenarios where the CP approaches employ either non- private models (f) DP models (fPP). For differentially private models, we train Naïve Bayes and Random Forest models using TBM's Diffprivlib library in Python ensuring pure c-DP guar- antees. For deep neural networks, we adopt the same methodology as Angelopoulos et al. (0022) utilizing the Opacus library to obtain (c, (C models. For DP conformal prediction methods, we leverage the equivalence between e-DP and (e, O)-CDP established in Lemma 3.2 of Bun & Steinke (2016) where, among others, we have that c-DP implics (2/2)-2CDP. This allows us to analyze the CP approaches under either privacy framework while maintaining similar privacy guarantees. We specifically examine how these methods behave under varying privacy parameters (e) and different sample sizes. Consistent with the experimental design of Angelloppsss et al. (2022), we restrict our investigation to classification tasks. The non-conformity measure we used is given by the hinge loss function:
=1 -1 f(x))
where f(x)y represents the predicted probability of the model for the true class We evaluate the performance of CP methods using the metrics of coverage, efficiency and informativeness. Therefore, if a CP approach performs well, we expect (i) the coverage to be close to - a, (ii) the efficiency be close to from below. When
to be close to from above, and (iii) the informativeness comparing to the benchmark datasets considered in Angelopoulos et al. 20022 we employ their same experimental and parameters settings.
Remark 8. When comparing P-COQS to the alternative benchmark HISTLAP (as well as to the eristing EXPONQ), a first aspect that must be underlined that, in practice, they all require bounds on the non-conformitty scores (i.e. [a, However, as opposed to P-COQS, the HISTLAP ap- prouch (like EXPONQ) requires the specificution of the number of bins B which must balance the discretization bias (O(1/B)) against the privacy noise term (O(v p/c/(c)))))))) and therefore needs to be optimized based on the somple size neat and the privacy budget ECp. In contrast, as pointed out in Remark 2 P-COQS only involves the parameter A, whose effect on the privacy term is logarithmic (T" x VTog((b- - a)) Hence, A can be set very small (e.g., 10-10 or 1 o//oaat with- out signiffccnttly affecting privacy noise, avoiding the need for tuning of an "optimal" discretization scale (see Proposition 7 Indeed, eristing theoretical results for DP quantile estimation through
privatized histograms (e.g. Wasserman & Zhou, 2010 Pilbutla et al. 2022. Lalanne et al. 2023)
provide erplicit ervor bounds, typically of order O (meats) 2/3) for the privacy-induced component of the error (after optimally choosing the number of bins B), together with discretization and sampling terms of orders 1/B and noad -1/2 respectively- In contrast, the privacy contrilution of Algorithm 1 based the noisy range count (NodsyRC) decays (1/(Beat/P)) under zCDP composition (with A x c/Tlaat), up to logarithmie factors. Relating the two privacy measures through the standard conversion [Bun & Steinke, 20166), Algorithm [ scales asymptotically faster in neat than that of the DP histogram approach. Nevertheless, the total quantile error in both fromeworks is ultimately dominated by the common sampling term O(1/ /eal), so the advantage is most relevant in small samples and/or orr small privacy budgels.
PDP implementations based IBM's Diffprivlib: http:///ltttuuubbeeeeeeeoeoellll
modele. modele..talfcce wtw.ee.ttttcclaaaaiiaaiioooom models
11

---

Published in Transactions Machine Learning Research (02/2026)
5.1 Simulated Data
We first consider a simple low-dimensional binary classification problem with eight features. The feature matrix for class 1 is sampled from Gaussian N (H,, E1), with #r [0.8..... ..... 0.8]* R and Σ = 1-7 E _ while class 2 follows [H,,, Σ²) with μ2 = [--1..... -1] and Σg = 1. where II denotes the identity matrix. This setting delivers reasonable overlap between the two classes and implies a slightly non-linear decision boundary due to the small difference in the covariance matrices. The generated data is class- balanced, with 60% used for the training set, 24% for the calibration set, and 16% reserved for evaluating CP performance. As for the models, we consider the two classifiers mentioned carlier: Naïve Bayes (NB) and Random Forest (RF) (we will see applications with deep neural works in Section 5.2 In particular, in this section we will focus on CP performance when employing the DP versions of these models (i.e. fDP), whereas the results using the non-DP models/ ff can be found in the appendix. This being said, we evaluate coverage, efficiency, and informativeness with a fixed privacy budget c;= repeat experimental runs I = 1, 000 times in each setting (unless otherwise specified). Moreover, when varying one of the parameters to study the sensitivity of the methods, the other parameters 10, 000 (total
= 2 when privatizing the models and
are fixed at: ECP = 1 (privacy budget for CP, corresponding to (fCr/a)-ZCDP)); sample size to be split); a 0.1 (significance level for coverage). For the proposed P-COQS we use the default value for A in Algorithm [ (i.e. A = 10-19) and in Appendix D we provide an ablation study with varying levels of A highlighting how the P-COQS performance appears to be stable for any reasonably small value of A. For the HISTLAP approach, since there is no standard rule to choose the number of bins in a DP setting, we pre-evaluated a grid of values in [20, 100) and chose to fix the number of bins to B 50 which gave the best overall results and can be considered reasonable in practice since Real = 2, 400 (implying that each bin contains the order of tens of observations). For clarity of presentation, here we only discuss the results for the RF classifier, while we provide the same results for the NB classifier in Appendices and
5.1.1 Effect of CP Privacy Budget (ECP)
We examine the sensitivity of P-COQS, EXPONQ and HISTLAP to variations in the CP privacy parameter ECP, using a private RF model while maintaining fixed sample size of n 10, 000. For the DP model (that achieves 79% accuracy), the results in Table 1 indicate that P-COQS and HISTLAP show significantly lower sensitivity to ECP compared to EXPONQ, while comparing favor- ably to it over the different evaluation metrics across the considered privacy budgets. In particular, for smaller values of cCP, the P-COQS appears to perform better than HISTLAP as discussed earlier in Remark S Comparable results are observed for the private NB model (see Table 7 in Appendix | where the P-COQS and HISTLAP have a more aligned behavior (while still outper- forming EXPONQ), with P-COQS having slight advantage for the smallest privacy budget. The same conclusions can be drawn when using the non-DP variants of the NB and RF models reported in Table 3 and Table 12 respectively where, as expected, efficiency and informativeness results are slightly better for all approaches.
5.1.2 Effect of Sample Size (n:)
We investigate the impact of sample size on the performance of the CP methods considered here. For each sample size, the sample split as mentioned at the start of this section (i.e. 60% training, 24% calibration and 16% test). We recall that we discuss the results with the DP version of RF (sec
12

---

Published in Transactions Machine Learning Research (02/2020)
1CP
Cowerage
Ellicimaay
Inforandivesoo
EXPONQ
HETTLAP
P-ODQS
EXPONQ
HESTLAP
P-COQS
ExPONQ
HISTLAP
P-COQS
0.1
1,0000 1 0.0002
0.5263 1 0.0196
0,5008 1 0.0112
1,9970
0.0087
1.3582 1 0.0826
1,2066 1 0.0689
0,0000 1, 0.0087
0,6418
0.0826
0.735
0.0089
0.5
0.5075
0.1122
0.9645
0.11008
0,8022 0.0111
1.5621
0.2776
1.2706 0.0427
1.2580
0,4379
0.7244
00422
0,7450
1.0
0.5242
0.0122
0.5023 0.0106
0,8077 0.100T
1,3499
0.0335
1.2579
0.0420
1,2505 0.0428
0,6541
00533
0.7321
00420
0.7455
1.5
0.9171
0.0010
05015 1 0.0100
0 0,008811 1 0.010
1.3185
0.0865
1.2558 0.0211
1,2835 1. 0.0455
0.6817 1. 00485
0.7342
00421
0.7467
0.0188
3.0
0.5006
1: 0.0112
0.5008 1: 0.0.11
0 0.5076 1 0.0106
1,2921
6.0471
1.2653 E: 0.0418
1 1,2532 1: 0.048]
0.7059 1 0.047]
0.7567
0.418
0.7468
0.04:1
5.0
0.5058 0.0022
0.509 + 0.00101
0.5075 0.0101
1.2601 0.0505
1.2610 + 0.0417
1,2529 + 0.045
0.7180 0.0605
0.7381
00417
0.7471
0.0135
0.5031 +00029
1.2736 0.0525
1,2513 0.0400
1,2531
0.7387
0.7469 0.0440
Table 1: Average effect of CP privacy budget ECP on conformal prediction with DP Random Forest
model. The numbers are metric averages over 1, 000 runs (per method and privacy budget) with variance bounds.
Appendix C.2 for the result of the non-DP model f) and also recall Chat, as in other experiments, the privacy budget for the models is fixed at E, = 2. The results in Table 2 show that in general P-COQS over-covers less than the DP alternatives in smaller sample sizes and hence converges more quickly towards the correct I-c a coverage, with consequent advantages over the DP alternatives in terms of efficiency and informativeness. In Appendices A.2 and B.2 the results for the NB classifier show that both the HISTLAP and P-COQS under-cover for the smallest sample size (i.e. 100) while EXPONQ over-covers. Nevertheless, it can be observed that the P-COQS under-covering appears to be solved already starting from n = 200, as is the case for HISTLAP which however has a more inconsistent behavior as the sample size increases, under-covering in various occasions for moderate sample sizes.
Coneaage
Elliciancy
Informativcuse
EXPONQ
HESTLAP
P-00QS
EXpUNt)
HusTLAP
P-COQS
EXPONQ
HaSTLAP
P-CCKS
100
0.9079 1 0.0142
0,9570 1 0.0158
0.5894 1 0,1000
1,997 1: 0.046
1.9872 1 0.0236
1,900 1 0.1630
0,0022 1 0.0045
0,0027 1 0.0200
0.0596 1 0,1660
200
0.9003 0.0000
0,0637 1: 0.0252
0.9651 1: 0.006
1,0000 0.078
19895 1 1.00070
1,885 0.1100
0.010 0.0098
0.0105
0.0379
0.0617 0.01100
0.0019
0.9620
0.113 +0055-
00009
1.0499 0.166
0.1601
0.1666
0.9800 0.0011
0.9307 0.0817
0.5095 =00001
1.9977 + 0.0100
166282 0.1888
0/0223
0.0:10
0
0.4652
2000
0.9976
0.0065
0,3066
:: 0.0232
0.5063
=: 0.0228
1.9678 e: 0.036
1.4645 = 0.0013
1.4:900 4: 0.0834
0.022
: 0.0078
0.5456 =: 000931
0.5810 4: 0.0845
6000
0.9467 0.0255
0.9611
+ 0.0155
0.5010
0.00
1,9064 + 0. 1988
1:3016-1 + 0.0578
1,2915
+ 0.0527
0.1096
0. 1986
0.0964
+ 0.0678
0.7065 0.0527
10000
0.22
+ 0.0125
0,9022 0.0101
0.8077 0.0107
1.3150 + 0.0536
1.3677 + 0.0017
1,2535 + 0.0438
0.6411 + 0.0055
0.7323 0.0417
0.7663 + 0.0138
Table 2: Average effect of sample size on private conformal prediction with DP Random Forest
model. The numbers are metric averages over 1, 000 runs (per method and sample size) and in parentheses the corresponding variance of the metrics.
5.1.3 Effect of Significance Level (a:)
We examine the performance across varying values (fixing n = 10, 000, es 2, and ECP 1). As seen in Table 3 P-COQS and HISTLAP appear to better target the required coverage level on average compared to EXPONQ. With respect to the other metrics, the results indicate that P-COQS generally performs better than EXPONQ and is comparable the HISTLAP approach. Appendix B.3 provides similar conclusions the DP NB model.
5.1.4 Computational Efficiency
We compare the runtime of the considered methods (including the non-DP CP which we refer to as "Standard") under two settings which considered the non-DP and DP versions of each model (i.e. f and fDP respectively). Confirming the model privacy budget to be c, = 2, conformal privacy budget
13

---

Published in Transactions Machine Learning Research (02/2020)
Coverage
Elliciency
Informativence
EXPONQ
HISTLAP
r-COQS
ExPONQ
T1sTLAP
P-COgS
ExpoNQ
IDsLLA
P-COOS
0.01
1,000 (0.00ke)
0,9921 (0.0127)
0.5004 (0.0038)
1.9070
(0,00S7]
1,788 (00855)
1.7007 (0.0483)
0.0030
(0.087)
0.2161
(0,053)
0.233
(0.0653)
(0.0121)
0.9456
1,8588 (31)
(0.0433)
(0:0438)
0.151
0.5325
(0
0.30
0,9242 (0.0123)
0.0022 (0.0100)
0.8977 (0.0107)
1.3458 (000553)
1,9677 (000085)
1,2535 (0.0433)
0.6641 (0,055))
0.7323 (0040))
0.7465 (00435)
Table 3: Average effect of a on private conformal prediction using DP Random Forest model. The numbers metric averages over 1,000 runs (per method and significance level), with variances in pesentheses.
<CP = 1, lotal sample size n 10, 000 and significance level a 0.1, we record the average runtime over 1,000 runs. Table 4 highlights the considerable computational gain that P-COQS delivers with respect to EXPONQ while remaining comparable (or often better) across all performance metries considered above (similar conclusions hold for the NB model in Appendix B.4h. It must. be underlined that, mentioned in Section 2 the increased computational time for EXPONQ is mainly due to the optimization subroutine needed to choose the optimal number of bins and the quantile-inflation hyperparameter to achieve the smallest possible prediction set. This being said, we can observe that the HISTLAP approach the most computationally efficient among the DP procedures while preserving similar performance P-COQS: this is due the fact that no optimal bin-width search procedure run (as is the case for EXPONQ) whereas P-COQS does not strictly require tuning of A and therefore loses some computational efficiency with respect to HISTLAP simply due to the binary-search. Even so, the computational difference can be considered almost negligible between P-COQS and HISTLAP since they have computational times in the order of milliseconds.
Coverage
Efficiency
Informativeness
Model Accuracy
Ave. time (secs)
f + Standard
0.9025 + 0.0099
1.2222 + 0.0224
0.7778 + 0.0224
0.8125 + 0.0093
0.0001 + 0.0001
f EXPONQ
0.9229 + 0.0120
1.2939 + 0.0406
0.7061 = 0.0406
0.8125 0.0093
0.7522 + 0.0075
f + HISTLAP
0.9024 + 0.0101
1,2220 + 0.0228
0.7780 0.0228
0.8125 + 0.0093
0.0002 + 0.0001
f f+ P-COQS
0.9025 + 0.0098
1.2223 + 0.0221
0.7777 = 0.0221
0.8125 + 0.0093
0.0076 + 0.0001
fDP + Standard
0.8965 + 0.0129
1.2507 + 0.0573
0.7493 = 0.0573
0.7941 + 0.0173
0.0001 + 0.0001
jDP ExPONQ
0.9242 0.0123
1.3459 + 0.0555
0.6541 0.0555
0.7941 + 0.0173
0.7570 + 0.0078
for + HISTLAP
0.9024 + 0.0103
1.2682 + 0.0416
0.7318 + 0.0416
0.7941 + 0.0173
0.0002 + 0.0001
for + P-COQS
0.8977 + 0.0106
1.2533 + 0.0438
0.7467 + 0.0438
0.7941 + 0.0173
0.0076 + 0.0001
Table 4: Average computational time of Standard, EXPONQ, HISTLAP and P-COQS combined with non-DP and DP versions of the RF classifier.
5.2 Datasets
In this section, we take the same settings as in Angelopoulos et al. (022) and study the perfor- mance of P-COQS when applied to three benchmark datasets: CIFAR-10 (Krizhevsky et al. 2009)
ImageNet (Deng et al. 2009) and CoronaHack (Pérez et al., 2020). We compare the performance of P-COQS with the non-DP CP approach (Standard) and with EXPONQ proposed by AAgelopoulos jtt al. (2022), and follow the same experimental setup as in the latter. Unless otherwise stated, the significance level is fixed at 0.1, CP privacy budget at cCp = (corresponding to (c0r/2)-
14

---

Published in Transactions Machine Learning Research (02/2026)
zCDP) and, when used, the DP models are trained to achieve (e,6)-DP using the Opacus library with (c 8 and 8 = 10-
5.2.1 CIFAR-10 Benchmark Analysis
We first evaluate P-COQS the CIFAR-10 dataset, comparing its performance EXPONQ under different privacy settings. Following Angelopoulos et al. (2022] we consider two scenarios for model training: (i) one where a non-DP model used (f) and (ii) one where DP model used (fDP). Both DP and non-DP models share the same convolutional neural network architecture. The DP model achieved an accuracy of 60% compared to 77% for the non-DP model. The evaluation is based on 1, 000 random splits of the CIFAR-10 validation set, each of size = 5, 000. Figure [ displays the empirical coverage and prediction set sizes across these settings. Our findings suggest that P-COQS generally produces smaller prediction sets (Figure [b], while achieving empirical coverage levels that are comparable to those of the standard (non-privatod CP baseline (Figure [ab, except for the case where a DP model is used where P-COQS appears to slightly undercover with respect to the standard CP baseline. On the other hand, compared to P-COQS, by inflating the quantile EXPONQ guarantees the coverage level but tends to have larger prediction sets for this reason. In the latter case, for all methods it can be seen that prodiction sets are larger when using a DP model (as expected).
Non-DP Model
Model
Non-DP Model
DP Model
0.94
Aug. Prodletion San Sba
32
Caverage
0.92
0.9
28
1.5
0.88
1.4 Standard
ExpoaQ P-COQS
Expos P.COQS
Expon[
P-COQS
ExponQ P-COOS
(a) Coverage
(b) Avg. Prediction Set Size
Figure/ 1: Results of Standard, EXPONQ and P-COQS methods applied to the CIFAR-10 dataset. (a) Boxplots with coverage distributions of the three methods under the non-DP model (Ieft) and DP model (right) scenarios; (b) Boxplots with distributions of average set. sizes of the three methods under the non-DP model (left) and DP model (right) scenarios. Red dots represent respective average metric.
5.2.2 Scale Evaluation ImageNet
We apply both considered private CP methods to the ImageNet dataset using pre-trained (non- DP) ResNet-152 model. We evaluated the performance of P-COQS and EXPONQ under varying values of the conformal privacy budget ECP. The evaluation uses = 30, 000 samples for calibration and 20, 000 samples for validation. For each budget value ECP, performance metrics are computed over 100 random splits of the ImageNet validation set, following the procedure in Angelopoulos
15

---

Published in Transactions Machine Learning Research (02/2020)
et al. (2022). As shown in Figure P-COQS appears to slightly under-cover but this does not appear be significant based the 95% confidence intervals (red vertical whiskers in the plots) and remains stable in performance across the different values of ECP, whereas EXPONQ appears to significantly over-cover for the small budgets (see Figure 2a With this in mind, P-COQS also appears to be stable with respect to prediction set sizes while EXPONQ approaches these sizes only as ECP increases (as highlighted also in the simulation results in Section 5.1.
0.93
22
0.92
Avg. Prodiccion Set Simo
0.91
Coverag
0.9
1.9
0.89
0.88
1.7
0.87
10 ExponQ
Ior-coqs
10 Expon
I1r-coqs
(a) Coverage
(b) Avg. Prediction Set Size
Figure2 2: Results of EXPONQ and P-COQS methods applied to the ImageNet dataset. (a) Median coverage (bar height), mean coverage (red dots) and 95% confidence intervals for coverage (red vertical whiskers) for each method under different privacy budgets (red-dashed horizontal line is the target coverage); (b) Average prediction set sizes (average set sizes in 100 splits): median (bar height), mean (red dots) and 95% confidence intervals (red vertical whiskers) for each method under different privacy budgets c.
5.2.3 Medical Imaging Analysis with CoronaHack Dataset
Finally, we evaluate both methods on the CoronaHack dataset, a publicly available chest X-ray dataset comprising 5, 908 images categorized into three classes: normal, viral pneumonia (primarily COVID-19), and bacterial pneumonia. We fine-tuned the final layer ResNet-18 model over 14 epochs using 4, 408 training samples, under both DP and non-DP settings. The DP model achieved 64% accuracy compared to 70% for the non-DP model. CP was calibrated on 000 samples and validated on 500 samples, across 1, 000 random splits of the data. Figure 3 presents the results for different configurations of the DP and non-DP models. While EXPONQ tends to produce overly conservative prediction sets, P-COQS appears to better target the nominal coverage level of 0.9 (see Figure 3a). Moreover, looking at the prediction set sizes, the distribution of the P-COQS appears to deliver roughly similar set sizes to the non-private CP approach since the proportions sets of specific sizes (1, 2 or on the x-axis) are very close each other (see Figure 3bp. Also in this case EXPONQ produces larger sets (i.e. higher proportions for sets of size or 3), where again the sizes tend to increase overall when using the DP model.
16

---

Published in Transactions Machine Learning Research (02/2020)
Non-DP Model
DP Model
Model
Model
1
Cavarage
Proporton
0.4
0.9
11.2
Standed Expont) P-0DQS
Standard EeporQ P-000S
DaStandurd
InExpond
BEP-COQS
(a) Coverage
(b) Distribution Prediction Set Sizes
Figure Results of Standard, EXPONQ and P-COQS methods applied to the CoronaHack dataset. (a) Boxplots with coverage distributions of the three methods under the non-DP model (left) and DP model (right)) scenarios; (b) Distribution of prediction set sizes where the y-axis represents the empirical proportion of sets of size 1, 2 or 3 (represented on the x-axis) for each method: median proportion (bar height), mean proportion (red dots) and 95% confidence intervals (red vertical whiskers) for each method under the non-DP model (left) and DP model (right) scenarios.
6 Discussion
The proposed P-COQS provides computationally efficient DP alternative to existing privacy- preserving CP approaches. It does so by adapting an existing DP quantile method and trading off some thcoretical guarantees on the lower bound for the coverage probability, while however guaranteeing quantifiable lower and upper error bounds for this probability. In this way, it is possible to determine (tight) error bounds which can then be used to assess the true minimum coverage level with high probability. Despite this thcorctical trade-off, which however remains small (if not negligible) in common settings, the P-COQS shows an empirical performance over different metrics that is in line with standard non-private CP, indicating that it targets the correct. coverage level in all settings while delivering more precise CP sets compared to the existing DP alternative (that we denoted as EXPONQ). The theoretical trade-off of the P-COQS can be observed mainly in settings with small sample sizes and/or privacy budgets in which the variability of P- COQS metrics is indeed larger compared to EXPONQ. However, the latter approach also makes a trade-off by generally over-covering with respect to the required coverage level in smaller samples and for small privacy budgets. As consequence, the latter tends to deliver less efficient and informative prediction sets in these settings and appears to only approach those of P-COQS for larger privacy budgets and/or sample sizes. In general, considering these different trade-offs and without claiming the existence of better approach, the proposed P-COQS appears to provide a valid mrivacy-preserving (and computationally efficient) CP approach also based on its generally good performance compared to EXPONQ in the diffcrent experimental settings considcred. While both EXPONQ and P-COQS can be applied within different forms of CP (e.g. full CP), future work will aim refine the theoretical coverage bounds of P-COQS in order to achieve the minimal (1 a coverage guarantecs, without overly compromising the efficiency and informativeness of the
17

---

Published in Transactions Machine Learning Research (02/2026)
prediction sets nor the computational efficiency of the method, particularly when the calibration sample size and/or privacy budget are small.
Acknowledgments
This work has been supported by the U.S. National Science Foundation under Grant No. SES- 2150615. The authors would also like greatly thank Aleksandra Slavkovié and Jordan Awan for their extremely helpful comments and feedback.
18

---

Published in Transactions Machine Learning Research (02/2026)
References
Anastasios N Angelopoulos and Stephen Bates. gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Tijana Zrnic, and Michael 1 Jordan. Private prediction scts. Harvard Data Science Review, 4(2), 2022.
Mario Astigarraga, Andrés Sánchez-Ruiz, and Gonzalo Colmenarejo. Conformal prediction-based machine learning in cheminformatics: Current applications and new challenges. Artificial Intel- ligence the Life Sciences, pp. 100127, 2025.
Charles Blundell, Julien Cornebise, Koray Kavukeuoglu, and Daan Wierstra. Weight uncertainty in neural networks. In International Conference Machine Learning, pp. 1613-1622. PMLR, 2015.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pp. 335-658. Springer, 2016.
Voss,, Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX security symposium (USENIX Security 21), pp. 2650, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenct: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-24882 255. Teee, 2009.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series (Statistical Methodology), 84(1):3-37, 2022.
Cynthia Dwork. Differcntial privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures, In Proceedings of the 22nd ACM SIGSAC confer- ence on computer and communications security, pp. 1922-1333, 2015.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pp. 1050-1059. PMLR, 2016.
Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift. arXiv preprint arXiv:2106.000 001000110000000000 70, 2021.
Ziyue Huang, Yuting Liang, and Ke Yi. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems, 34:25993 260044, 2021.
Pierre Humbert, Batiste Le Bars, Aurélien Bellet, and Sylvain Arlot. One-shot federated conformal prediction. In International Conference on Machine Learning, pp. 14153-141777 PMLR, 2023.
19

---

Published in Transactions Machine Learning Research (02/2026)
Jef Jonkers, Glemn Van Wallendael, Lue Duchateau, and Sofie Van Hoecke. Conformal predictive systems under covariate shift. In Proceedings of the Thirteenth Symposium Conformal and Probabilistic Prediction with Applications, pp. 406-423. PMLR, 2024.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? In Advonces in Neural Information Processing Systems, pp. 5574-5584 2017.
Alex Krizhevsky, Gooffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, pp. (402-6413, 2017.
Benjamin Lalanne, Aurélien Garivier, and Rémi Gribonval. Differentially private quantiles via histogram density estimation. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Jing Lei, Alessandro Rinaldo, and Larry Wasserman. A conformal prediction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 74:29-43, 43, 2015.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113(523): 2018.
Miao Li, Michael Klamkin, Mathieu Tanneau, Reza Zandchshahvar, and Pascal Van Hentenryck. Conformal prediction with upper and lower bound models. arXiv preprint arXiv:2503.04: 04001, 2025.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium Foundations of Computer Science (FOCS 07), pp. 143103. IEFE, 2007.
Joseph P Near and Chiké Abuah. Programming differential privacy. URL: https://uem, 2021.
Henrik Olsson, Kimmo Kartasalo, Nita Mulliqi, Marco Capuccini, Pekka Ruusuvuori, Hemamali Samaratunga, Brett Delahunt, Cecilia Lindskog, Emiel AM Janssen, Anders Blilie, et al. Estimat- ing diagnostic uncertainty in artificial intelligence assisted pathology using conformal prediction. Nature communications, 13(1):7761, 2022.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in Newral Information Processing Systems, pp. 4026 4034, 2016.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Machine learning: ECML 2002: 13th European conference on machine learning Helsinki, Finland, August 19 19-23, 2002 proceedings 13, pp.
Springer, 2002.
Coby Penso, Bar Mahpud, Jacob Goldberger, and Or Sheffet. diction under local differential privacy. arXiv preprint arXio:2505.1577 157211 2025.
conformal pre-
Juan Caballero Pérez, José Manuel Caballero Contreras, Carlos de Blas Pérez, and Felipe Leza Alvarez. Databiology lab coronahack: Collection of public covid-19 data. bioRwiv, pp. 2020 10, 2020.
20

---

Published in Transactions Machine Learning Research (02/2026)
Krishna Pillutla, Yassine Laguel, Zaid Harchaoui, and Yoram Low. Bounded-space differentially private quantiles via flat histograms. In NeurIPS Federated Learning Workshop, 2022.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inferenco at- lacks against machine learning models. In 2017 IEEE symposium on securily and privacy (SP), pp. 3 3-18. IEEE, 2017.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel J Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. arXiv preprint arX4::1044.000 2019.
Rudraksh Tuwani and Andrew Beam. Safe and reliable transport of prediction models to new healthcare settings without the need to collect new labeled data. medRriv, 2023.
Nasir Uddin and Tuwe Lofstrom. Applications of conformal regression on real-world industrial use cases using crepes and mapie. In Conformal and Probabilistic Prediction with Applications, pp. 147-165. PMLR, 2023.
Vladimir Vovk. On-line confidence machines are well-calibrated. The 43rd Annual IEEE Sym- posium on Foundations of Computer Science, 2002. Proceedings., pp. 187-196. TEFE, 2002.
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74: 9-28, 2015.
Vladimir Vovk and Ivan Petej. Venn-abers predictors. arXiv preprint arXio:1211.0033 2012.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world,
volume Springer, 2005.
Vladimir Vovk, Jieli Shen, Valery Manokhin, and Min-ge Xie. Nonparametric predictive distribu- tions based on conformal prediction. In Conformal and probabilistic prediction and applications, pp. 82-102. PMLR, 2017.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 175(489):375-389, 2010.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk machine learn- ing: Analyzing the connection to overfitting. In 2018 IEEE 31st computer securily foundations symposium (CSF), pp. 268 282. IEEE, 2018.
21

---

Published in Transactions Machine Learning Research (02/2026)
A Simulation Results With Non-DP Naive Bayes Model
The parameter settings as in the non-DP NB model and the model's accuracy is 83%.
A.1
Effect of CP Privacy Budget (ECP)
'CP
Coverage
Dffecency
Informatommess
EXPONS
HESTLA
P-CDQS
EXPONQ
HESTLAP
P-COQS
ExPoNQ
HiSTLAP
P-COOS
0.1
0.5999
0.0004
0.5095 1 0.0199
0.9005 1 0.00190
19618 6.028)
1,005 0,0599
1,811 1. 0.0629
0,0322
0.0289
0.7985
0.089
0,8187
-00629
05
0.000
1.0
0.0116
0.5002 0.0100
0.5005
1,2500
0.099)
1,1779
0.0905
1.1788 0.0205
0.7481
0.0800
0.822
0.2205
0.8212
010006
1.6
0.9154
+ 0.0108
0.5012 + 0.00521
0.5066 + 0.0000
1.2264 + 0.0267
1.1776+ + 0.0202
1.1789 +: 0.0201
0.7746 0.2267
0.8224
00202
0.8211
8.0201
300 (.508]
à: 0.0097
0.5012 5: 0.1003
0.5085 0.0059
1,2019 0.0214
11777 +: 0.0197
1.1789
:: 0.0230
0.7981
0/2213
118223 = 00197
0,8211
5.
0.5051 0.0099
0.5002
0.9085
0.024
0.0166
1.1788
0,8075
0.196
0.0200
0.009
1.1857 0.018
0.0197
0.0201
0,8145
0,8223 00197
0.0001
Table 5: Average effect of CP privacy budget CCP conformal prediction with non-DP Naäve Bayes model. The numbers are metric averages over 1000 runs (per method and privacy budget) and the corresponding variance bounds of the metries.
A.2 Effect of Sample Size (n)
Sumplee
Coverag
Ellicwsy
Informniivmmo
EXPoNQ
HistLAP
P-D0QS
EXPoNQ
HisTTap
P-CDQS
ExprvQ
HisTL.P
P-CDQS
1:00
0.9794 + D7451
039332 + 010775
0.9001 + 0.170
1.730) 0.2179
1.4931 + 0.101
1.2771 + 0.2735
0.2200 0.21
0.5600 + 0. 0.191
0.7226+0022
230
0.5800 = 0.0207
048957
0.0507
0.8965 + 0.0888
1.7801
0.3658
1.315 0.1469
1.2802 + +.2.349
0.3030 = 0.1658
0.2447 + 1:60
0,7108 0.2251
0,9086 0.0059
0.3156
1:2780 0.122
0.3481 0.3156
0,7708 0.11352
0.98%
0.0129
0.9011
0.0230
0.9031
0.0227
1,6272
0.348
1.1932 0.0500
1,1905
0.5728
0.3483
0.800550.0050
6000
0.5082 2 0.0180
0.9002 0.0128
0,0009 1. 0.0127
1.3149
0,0795
1.1782 1: 0.0279
1.1801 0.0222
0.885 0.0793
0.8218 1: 0.0270
0,8199 0.0283
10:00
0.9227 = 0.01
0.9002 L 0.0101
0.0005 i: 0.0101
1,2009
0.009
1.1778 à 0.020
1,1788 8: 0.0206
0.740 0.000)
0.222 :: 0.0377
0.8212 2: 0.0206
Table 6: Average effect of sample size on DP CP ( (ECP = 1) with non-DP Naäve Bayes model. The numbers are metric averages over 1000 runs (per method and sample size) and the corresponding variance bounds of the metries.
22

---

Published in Transactions Machine Learning Research (02/2026)
B Simulation Results With DP Naive Bayes Model
The parameter settings are as in the DP R. model and the model's accuracy 75%.
B.1 Effect of CP Privacy Budget (ECP)
Coverage
Ellicimny
Informativmmne
EXPONQ
HISTLAP
P. COCQ
ExpoNQ
HEsTLA
P. cogs
EspoNQ
HistLAP
P. P.COSS
01)
1,0000 + 0.002
0.8855 + 0.0162
0.5090
0.0197
1.9895 + 0.009)
1.5054 + 0.0555
1.5981 + 0.0077
0.0005
0.0050
0.0346
0.0555
0.0018 0.0677
0.5
0.8955
0.5890 0.0101
1.5692
0.4308
0.041
1.0
0.0116
0.0008
0,8019 0.0300
1.8841 0.0457
1.3970
0.0025
0.5359
0.0457
0,0000
00016
0,0055 B0026
1.5
0.9148 2: 0.0104
0,8955 1 0.10197
0,2099 1 0.0099
1,4553 à: 0.0385
1,3970 1: 0.0016
1,3885 4: 0.0021
0.5447 2: 00085
[L8000
2: 00016
0,6015 = 80021
3.0
0.5075
1 0.0098
0.8095 1 0.0099
0,8099 1 0.0057
1,4272 1 0.0357
1 1 0.0014
1 1,3885
1 0.002)
0,5728 1. 0.0337
0,0028
06014
0,6015
0.0020
5.
0.5655
018095
0,8019 0,0097
1,4161 0.0225
0.0015
0.5840
0,6014 0.0200
1011
0.0096
0.5003 0.0057
1,4033
0.0015
1,387 0.0021
0,5927 0.021
0,8029 0.0015
0,0013 0.021
Table 7: Average effect of CP privacy budget ECP conformal prediction with DP Naïve Bayes model and Ef 2. The numbers are metric averages over 1000 runs (per method and privacy budget) and the corresponding variance bounds of the metrics.
B.2 Effect of Sample Size (n)
Sumpiee
Comerage
Fffieeeyy
Informstvveees
ExPONQ
P-COQS
ExpoNQ
HisLLPr
P-CDQS
ExposQ
RiseAr
P-CDQS
0.9791
0.0447
0.807
0.1297
0,7981 0.1661
1,9266 0.3180
1.4537 0.0144
0.0734 0.3199
= 0
0.90/4
0.0188
09943
0.0800
0.0235 i: 0.0630
1.9895
0.087
18852 0:1355
1.7918 1.1191
0.0104
0.0087
0.1458 + 1:35
0:116
5:00
0.5000
0/074
0.9088
0.0:58
0.0085 + +.00517
1.989)
0.2271
16111 + +0.1082
1.0175 0.1366
0.0120 0.0274
0.3830 + 1052
+.1355
1000
0.5094
= 0.0034
08805
0.0028
0,326) = 0.0566
1.9863 = 0.0147
1,500 + 0.1066
1.737 + 0.11674
0.0037
0.0147
0.1100 + 1960
0.1554
0.906
0.0150
0.8887
0.0210
0.0012:1..022
1
0.007
1323 0.0638
1.5313::: 0.0069
0.0677 0,153:
0.4777 0.0688
0.0987
0.0000
0.31
0.3707 0.1906
10000
0.9217 0.0116
0.899 0.0008 0.8389 = 0.0000
1,4841 0.0457
1,3953 0.0321
1.5985 :: 0.0326
0.5150 0.0457
0.0321
0.0015
Table 8: Average effect of sample size DP CP (cep 1) with DP Naive Bayes model (cr 2).
The numbers are metric averages over 1000 runs (per method and sample size) and the correspond- ing variance bounds of the metrics.
B.3 Effect of Significance Level (a)
48
Covaragg
Ellicisncy IlstLA
Infornativemsse
EXPONQ
HisTLAr
P' COQS
ExPONQ
P' COQS
ExpONQ
IDscLA
P. coQS
0.01
1,0000 (0,0002)
0,9822 (0.0047)
0.9985 (0.0050)
1,9998
(0.0020)
1.8228 (0.0136)
1,0824 (0.0582)
0.0005 (00000)
0.1772
(0.0138)
0.0176 (0.0562)
(0,0088)
(0.0072)
L,7599
(0.0357]
(0.0380)
0.2421
(0.000:
0:3671 (0/057))
(0.030)
0.10
0.0217 (000116) 0,9000 (0.0006)
0.8008 (0.0100)
1.4841 (0.0457)
1,0022 (0.0314)
1.3065 (0.0336)
0.5159 (0.0457)
0.5878 (000144)
0.6015 (0.0326)
Table Average effect of a on DP CP (ECP 1) with DP Naäve Bayes model (e, 2). The numbers are metric averages over 1000 runs (per method and value) and the corrosponding variance bounds of the metrics.
23

---

Published in Transactions Machine Learning Research (02/2026)
B.4 Average CP computational time with DP and non-DP models
Coverage
Efficiency
Informativeness
Model Accuracy
Ave. time (secs)
f + Standard
0.9025 + 0.0099
1.2222 + 0.0224
0.7778 + 0.0224
0.8125 + 0.0093
0.0001 + 0.0001
f EXPONQ
0.9229 0.0120
1.2939 + 0.0406
0.7061 0.0406
0.8125 0.0093
0.7522 + 0.0075
f + HISTLAP
0.9021 0.0101
1.2220 + 0.0228
0.7780 0.0228
0.8125 0.0093
0.0002 + 0.0001
f+ P- COCS
0.9025 + O. 0098
1.2223 + 0.0224
0.7777 = 0.0224
0.8125 + 0.0093
0.0076 = 0.0001
J0P + Standard
0.8965 + 0.0129
1.2507 + 0.0573
0.7493 = 0.0573
0.7941 + 0.0173
0.0001 + 0.0001
JDP EXPONQ
0.9242 0.0123
1.3459 0.0555
0.6541 0.0555
0.7941 0.0173
0.7570 + 0.0078
fDP HISTLAP
0.W024 + 0.0103
1.2682 + 0.0416
0.7318 + 0.0416
0.7941 + 0.0173
0.0002 + 0.0001
fDP + P-COQS
0.8977 + 0.0106
1.2533 + 0.0438
0.7467 = 0.0138
0.7941 + 0.0173
0.0076 + 0.0001
Table 10: Average computational time of Standard, EXPONQ, HISTLAP and P-COQS and com- bined with non-DP and DP versions of the Naïve Bayes classifier. The numbers are metric averages over 1000 runs (per setting) and in parentheses is the corresponding variance of the metrics.
B.5 Effect of Model Privacy Budget (E/)
Coverage
Effilency
Informativcaess
ExpexQ
HiSTI.AP
P-C00S
EXPoNQ
Haset.w
P-C0QS
ExpOTQ
Hieri.ar
P-COQS
0.1
0.9218 (0.01 15)
0.5001
(0.0088)
0.8035 (0.0102)
1,6580 (0.0355)
1.5895
(0.0226)
1.5007 (0.0238)
0.3820 (0.0355)
0.4105 (0.0296)
0.4063 (0.0258)
(0.0034)
(0.0996)
(0.0389)
1.4616 (000259)
1.4530
(0.0259)
(0.0264)
0.9405 (0.0308)
0.5301 (0.0534)
0.8812 (0.0108)
1.7647 (0.1443)
1.4575 (0.0753)
1.5208 (0.1717)
0.2353 (0. 1413;
0.5425 (0.0753)
0.0792 (0.1717)
0.9217 (0.01 16)
0.5065 (0.0036)
0.8009 (0.0100)
1.841 (0.0457)
1.3971 (000117)
1.3985 (0.0526)
0.5159 (0.0457)
0.6028 (0.0317)
0.6015 (0.0326)
0.9224 (0.0117)
5058 (0.0138)
0,5000 (0.0080)
1,2784 (0.0372)
1,2035 (0.0217)
1.3035 (0.0218)
0.7216 (0.0672)
0.7974 (0.0217)
0.7965 (0.0218)
(0.0110)
(0.0039)
(0.0088)
(0.0007)
(0.0266)
(0.0205)
Table 11: Average effect of model privacy budget ey DP CP (ECP 1) with DP Naïve Bayes model. The numbers are metric averages over 1000 runs (per method and privacy budget) and the corresponding variance bounds of the metrics.
24

---

Published in Transactions Machine Learning Research (02/2026)
C Simulation Results With Non-DP Random Forest Model
The parameter settings described in Section 5.1 and the accuracy of the model is 81 %..
C.1
Effect of Privacy Budget (tCP)
TCP
Coverage
Effeiency
Informatommess
EXPONS
HuSTLAP
P-CDQS
EXPONQ
HESTLAP
P-COQS
ExPoNQ
HiSTLAP
P-COOS
0,1
0.5908
0.0004
0.9125 1 0.0191
0.9027 1 0.00195
13885 6.012)
1,250
0.0025
1.2265 1. 0.0893
0.0114
0.0125
0.7401
0.0225
0.7731
00.005
05
1.2219
0.5005.t:000
1.0
0.025 0.0101
0.0024
+.00000
1,2839 0.0800
1.2219 0.0225
0.0061++ +00405
0.7776
00231
0.022
1.5
0.9155
+ 0.0106
0.5025 + 0.0100
0.5025 + 0.0008
1,3609 + 0.0296
1.22118 + 0.0227
1,2228 + 0.0221
0.7341 = 00235
0.7782
00227
0.7777
0.024
300
015083
2: 0.009
0.5922 2: 0.11100
0.5025
1.2411 0.0236
1,2214
0.0224
1,2220 4: 0.0222
0.7589
0/023
U.7780
= 002224
0,7776
0.2222
5.0
0.5057
0.5623 0.00P9
0.3025
0.0058
1,2024 0.0225
1,2216 0.0244
1.2227
0.7676
0.7784
0.0255
0.0099
0.0222
0,7730
0.7784
0.024
Table 12: Average effect of CP privacy budget cCp conformal prediction with non-DP Random Forest model. The numbers are metric averages over 1000 runs (per method and privacy budget) and in parentheses is the corresponding variance of the metrics.
C.2 Effect of Sample Size (n)
Ellicinnyy
Informativmmmes
FXPOXQ
HistLAP
P-C00S
EXPONI
HisTL.P
P-C0QS
EXPONQ
Hasrl.a
P-CCK3
100
0.9892 0,3022
0JITT 1: 0.0451
0.8015 2: 011122
1,8588 1: 0.1716
1.7618 1 0,1902
1.4777 à: 0.3024
0.3342 :: 0.1715
0.2382 2: 0.1932
0.5222
1133024
0.9951
0,0183
0,8655 1 0.0427
0.9129 100005
0.1908
16228. 1.0.828
1.4559
0.2047
0.3075
0,3712
0.5441
1.0.247
0.039)
050041
0.5752-1:0.10
0.9887
0.0036
0.9175
0.020)
0.908
0.0840
1,9520
0.0577
1315 0.0859
1,2737
0.0099
0.0677
0.8900
0.0830
0.7263
0.0029
2000
0.9863
0.0126
0.3085 + 0.0228
0.5055
0.0023
1,7402 +: 0.1492
1,2600 + 0.0395
1,2512 0.0007
0.2508 + 0.1492
0.7400
0.0506
0.7488
0.0007
6100
0.9893 0.0081
0,3028 :: 0.0127
0.5025 0.0125
1.3745
0.0996
1 1.2274 0.0007
1.2276 0.030)
D.6255 0.0886
0.7726 0.0807
0.7725 0.0000
0,0120
0.9024 0.0099
1,2219
0,7777
0.7781 11,0255
Table 13: Average effect of sample size on DP CP (ECP = 1) with non-DP Random Forest model.
The numbers are metric averages over 1000 runs (per method and sample size) and in parentheses is the corresponding variance of the metrics.
25

---

Published in Transactions Machine Learning Research (02/2026)
D Ablation Study A
In this appendix we provide brief ablation study understand the sensitivity of Algorithm | to the choice of A. Using range for A between 10 to 10 and the same simulation settings in Section 5.1 the results are presented in Table 14 bclow.
A
Coverage
Efficiency
Informativeness
Accuracy
10 10-20
0.9219 (0.0109)
1.4856 (0.0534)
0.5144 (0.0534)
0.7479 (0.0125)
10 x 10-15
0.9219 (0.0109)
1.4856 (0.0534)
0.5144 (0.0534)
0.7479 (0.0125)
Naive Bayes
x 10-10
0.9219 (0.0109)
1.4856 (0.0534)
0.5144 (0.0534)
0.7479 (0.0125)
10 10
0.9219
(0.0109)
1.4856 (0.0534)
0.5144 (0.0534)
0.7479 (0.0125)
10 x 10
1.0000 (0.0000)
2.0000
(0.0000)
0.0000 (0.0000)
0.7479 (0.0125)
10 x 10
0.8979
(0.0105)
1.2542
(0.0436)
0.7458
(0.0436)
0.7941 (0.0173)
10 x 10 10-15 15
0.8979
(0.0105)
1.2542
(0.0436)
0.7458 (0.0436)
0.7941 (0.0173)
Random Forest
10 10-10
0.8979
(0.0105)
1.2542
(0.0436)
0.7458 (0.0436)
0.7941 (0.0173)
10 x 10-5
0.8979
(0.0105)
1.2542
(0.0436)
0.7458 (0.0436)
0.7941 (0.0173)
x 10-1
0.8983 (0.0106) 1.2554 (0.0447)
0.7446 (0.0447) 0.7941 (0.0173)
Table 14: Average effect of parameter A on P-COQS with DP Naive Bayes and Random Forest
models (ty 2 and ecp = 1). The numbers are metric averages over 1000 runs and in parentheses are the corresponding variance of the metrics.
We observe that the performance of P-COQS remains unchanged for all reasonably small values of A while it changes only for the value A = 10-1; this is not surprising since the range for the non-conformity scores is [0, 1], meaning that we accept to stop Algorithm | when the difference between scores smaller than 0.1 (one tenth of the possible space) which is unreasonable practice.
26

---

Published in Transactions Machine Learning Research (02/2026)
E Absolute Rank Error
In this section present results based the simulation settings in Section 5.1 with 10, and E 2. Table 15 and Table 16 present the average absolute rank errors (over H 1, 4,000 runs) over different privacy budgets (CPP) of the different private DP quantile approaches considered for Naive Bayes and Random Forest models respectively. In line with the results of Section 5.1 we observe that HISTLAP and P-COQS have the lowest errors over the different settings, with P-COQS showing generally better performance for smaller privacy budgets.
Table 15: Rank Errors for Naive Bayes (Private and Non-private)
cep
Method
Rank Error
EXPONQ
LAPIIST
P-COQS
0.1
Non-private
0.3372 (0.0154)
0.0372 (0.0277)
0.0316 (0.0251)
Private
0.1460 (0.0217)
0.0231 (0.0189)
0.0293 (0.0235)
0.5
Non- Privariv
0.1199 (0.0512)
0.0084
(0.0066)
0.0067 (0.0056)
Private
0.0813 (0.0222)
0.0053 (0.00413
0.0067 (0.0055)
1.0
Privativ
0.0574 (0.0230)
0.0044
(0.0035)
0.0040 (0.0031)
Private
0.0468 (0.0160)
0.0030 (0.0023)
0.0010 (0.0032)
1.5
Nou-private
0.0350 (0.0150)
0.0032 (0.0025)
0.0034 (0.0026)
Private
0.0326 (0.0117)
0.0023 (0.0018)
0.0033 (0.0025)
3.0
Nou-private
0.0194 (0.0078)
0.0020 (0.0016)
0.0028 (0.0019)
Private
0.0174 (0.0067)
0.0017 (0.0013)
0.0027 (0.0018)
Non-private
0.0118 (0.0050)
0.0016
(0.0013)
0.0026
(0.0017)
Private
0.0109 (0.0045)
0.0015 (0.0012)
0.0026 (0.0016)
Noi-private
0.0061 (0.0030)
0.0014 (0.0012)
0.0026 (0.0016)
Private
0.0057 (0.0028)
0.0015 (0.0012)
0.0026 (0.0015)
Table 16: Rank Errors for Random Forest (Private and Non- Non-private)
ECP
Method
Rank Error
EXPONQ
LAPHist
P-COQS
0.1
Non-private
0.3615 (0.0139)
0.0812 (0.0253)
0.0237 (0.0211)
Private
0.3209 (0.0502)
0.0182 (0.0133)
0.0079 (0.0056)
0.5
Non-private
0.1078 (0. (5.0580)
0.0074
(0. (0.0054)
0.0052 (0.0060)
Private
0.0871 (0.1125)
0.0033 (0.0024)
0.0037 (0.0021)
1.0
Non-private
0.0467
(0.0204)
0.0053
(0.0033)
0.0028 (0.0045)
Private
0.0149 (0.0079)
0.0023 (0.0017)
0.0034 (0.0018)
1.5
Non-private
0.0305 (0.0129)
0.0048
(0.0032)
0.0019 (0.0038)
Private
0.0099 (0.0053)
0.0021 (0.0015)
0.0032 (0.0016)
3.0
Non-private
0.0160 (0.0073)
0.0045
(0.0029)
0.0009
(0.0028)
Private
0.0045 (0.0043)
0.0020 (0.0013)
0.0031 (0.0014)
5.0
Nou-private
0.0103 (0.0064)
0.0044 (0.0028)
0.0006
(0.0022)
Private
0.0019 (0.0032)
0.0020 (0.0013)
0.0031 (0.0013)
10.0
Non-private
0.0014 (0.0052)
0.0044 (0.0028)
0.0003
(0.0017)
Private
0.0008 (0.0023)
0.0019 (0.0013)
0.0090
(0.0013)
27


Reviews:
[{"review_id": "pz1FmXXoBA", "reviewer": "Reviewer_QF3c", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- The authors initially describe the challenges of deploying conformal prediction (CP) as a truly private solution for generating distribution-free samples, noting the possibility of a privacy-leaking calibration step. \n- Note that CP is often used in high-sensitivity fields where, along with privacy guarantees where high levels of actual coverage (not via just simply data distribution) are necessary.\n- The authors mention that the calibration step in CP can leak information since the quantile of calibration non-conformity scores depends on the underlying individual's data.\n- The paper notes that existing exponential methods are not sufficient due to the high cost of binning, tuning, and possibly inflated quantiles, leading to larger-than-required prediction sets.\n- The authors then propose P-COQS, which enables a differentially private binary search for identifying the quantile on individual conformal scores with better accuracy than existing methods. \n- Errors due to DP are quantified both theoretically and via experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes, the core claims of the paper can be categorized as per the following, \n\nFirst, the theoretical bounds, as recognized by the privacy bound for Algorithm 1 (this is by definition), rank error probabilistic bound from Proposition 1 (ensuring probabilistic accuracy), and the subsequent coverage guarantee in Theorem 1, are responsible for ensuring privacy-accuracy guarantees.\n\nSecond, the empirical results show a better coverage than existing SOTA methods for the low-$\\epsilon$ regime.\n\nHowever, the following are some limitations that need to be addressed in this work, \n1. The authors describe the lower and upper bounds of the scores $(a, b)$. How are these readily available? And are they fully disclosed or only disclosed under DP? Otherwise, the value of $q$ might leak information.\n2. Is it possible to compare the method to other possible alternatives? Like DP histogram releases, the release of quantile under already privatized data / privatized model, other uncertainty techniques that might work with DP?\n3. Possibility to explore membership inference attack-based verification for quantile releases that can strengthen empirical results?\n4. How does the method work for continuous targets, such as in the case of regression?", "audience_yn": "Yes", "audience_explanation": "The work focuses on differentially private metric generation to generate distribution-free prediction samples. Statistical findings can be useful in systems with limited data with high levels of privatization.", "requested_changes": "Overall, the paper is well-written and mostly justifies its claims. However, I have identified 4 important limitations of the work above that can be addressed for significant improvements.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8GVtsIZwJx", "reviewer": "Reviewer_7vqy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces P-COQS, a differentially private conformal prediction method that releases a DP quantile of calibration nonconformity scores via a fixed-depth binary search over a *known score range* [a,b] (e.g., the observed min/max of calibration scores or user-specified bounds) with resolution delta, using a noisy range count (NoisyRC) at each step; noise is calibrated so the search satisfies $\\rho$‑zCDP. The theory provides a high-probability rank‑error bound for the privatized quantile and, under exchangeability, an approximate coverage band for the resulting conformal sets around the nominal $(1 − \\alpha)$. Experiments on simulations and three vision benchmarks (CIFAR‑10, ImageNet, CoronaHack), with both non‑DP and DP base models, report near‑nominal coverage, smaller prediction sets than ExponQ, and orders‑of‑magnitude faster runtime.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Overall, the paper’s claims are substantiated for the most part, with several focused gaps that could be addressed.\n\n**(C1) Claim (Sec. 4):** *The paper proposes a private quantile mechanism for continuous scores via binary search (P-COQS).*  \n**Evidence:** Algorithm 1 adapts a private quantile search to real-valued scores by searching over an interval ([a,b]) at resolution ($\\delta$) for a fixed number of steps ($N=\\lceil\\log_2((b-a)/\\delta)\\rceil$). Each step calls a noisy range count to estimate (#$\\{s\\le \\text{mid}\\}$) with Gaussian noise; the final midpoint is the DP quantile ($q_{\\mathrm{DP}}$). Algorithm 2 forms the conformal set using ($q_{\\mathrm{DP}}$).\n\n**(C2) Theoretical claim (Sec. 3.2–4):** *The DP quantile search satisfies rho‑zCDP and induces a high‑probability rank‑error tau, which together yield an approximate coverage band for the resulting DP conformal sets.*  \n**Evidence:** Gaussian noise per range‑count query is scaled to the fixed iteration budget $N$, so each call uses $\\rho/N$ and the search composes additively to $\\rho$‑zCDP. With probability at least $1−\\beta$, the privatized quantile’s rank deviates from the non‑private rank by at most $\\tau$ (explicit tail bound provided). Under exchangeability, this rank‑error window implies the coverage band, and the text discusses deterministic tie handling.\n\n**(C3) Claim (Sec. 5):** *Across benchmarks, P-COQS attains near-nominal coverage, is more stable across privacy budgets and dataset regimes, and is substantially faster than ExponQ.*   \n**Evidence:** Section 5 (simulations and CIFAR-10, ImageNet, CoronaHack) reports near-target coverage with smaller, more stable prediction sets than ExponQ, and orders-of-magnitude runtime speedups (e.g., $\\approx$0.007 s vs $\\approx$0.75 s in the NB setting), supporting the central empirical claim.\n\n## Claims that are undersubstantiated\n\n**(U1) Exact claim:** *P-COQS achieves favorable efficiency at comparable coverage across settings.*   \n**Provided:** Head-to-head comparisons with ExponQ on simulations and three benchmarks show smaller set sizes for P-COQS at near-nominal coverage; CIFAR-10 also includes a non-private CP baseline (“Standard”).  \n**Undersubstantiated & why it's required:** Comparisons are limited to ExponQ as the DP-quantile baseline. Alternative DP quantile estimators (e.g., smooth-sensitivity quantiles; histogram + Laplace / DP-CDF; direct DP-quantile mechanisms) are not included. Adding one such baseline would demonstrate that the efficiency advantage is not specific to ExponQ’s inflation strategy, improving external validity of the claim. _(Representative references provided in the References section.)_\n\n**(U2) Exact claim:** *The continuous-score adaptation (grid ($[a,b],\\delta$)) is robust in practice.*   \n**Provided:** Theory specifies iteration budget ($N=\\lceil\\log_2((b-a)/\\delta)\\rceil$) and a rank-error bound that scales with ($u=(b-a)/\\delta$).  \n**Undersubstantiated & why it's required:** No ablation shows sensitivity of coverage/set size to bounds ([a,b]) or resolution ($\\delta$). Since the error term depends on ($u$), empirical plots vs ($[a,b],\\delta$) (and observed ($\\tau$) percentiles) are needed to establish practical robustness and to guide practitioners in choosing these knobs.\n\n**(U3) Exact claim:** *The approximate coverage band is adequate in practice.*   \n**Provided:** A two-sided coverage band ($1-\\alpha\\pm O((\\tau+1)/(n_{\\mathrm{cal}}+1))$) with discussion of ties and approximation sources.  \n**Undersubstantiated & why it's required:** The magnitude of ($\\tau$) under realistic settings is not reported (e.g., empirical distribution of rank error across runs). Reporting ($\\tau$) percentiles alongside coverage would quantify the tightness of the band and clarify when small calibration sizes materially affect coverage.\n\n--- \n# References \n[1] Nissim, K., Raskhodnikova, S., & Smith, A. (2007). Smooth sensitivity and sampling in private data analysis. STOC ’07.   \n[2] Bun, M., Nissim, K., Stemmer, U., & Steinke, T. (2019). Private algorithms for smooth sensitivity and mean estimation. NeurIPS.   \n[3] Wasserman, L., & Zhou, S. (2010). A statistical framework for differential privacy. JASA, 105(489), 375–389. (DP histograms/DP-CDF; quantiles via CDF.)  \n[4] Li, C., Hay, M., Miklau, G., & Wang, Y. (2015). Differentially private histogram publication for dynamic datasets. VLDB J.   \n[5] Kaplan, H., Mansour, Y., & Stemmer, U. (2022). Differentially Private Approximate Quantiles. ICML 2022.", "audience_yn": "Yes", "audience_explanation": "I believe TMLR's audience would be interested in the paper as it provides \n\n- **Privacy-aware uncertainty quantification:** A simple, composable mechanism that privatizes the conformal quantile with clear zCDP accounting.\n    \n- **Applied ML in sensitive domains:** The runtime advantage and smaller sets at comparable coverage are attractive for clinical and large-scale vision deployments.\n    \n- **Theory–practice bridge:** An explicit rank-error to coverage band mapping that can be budgeted alongside DP-SGD training privacy.", "requested_changes": "The following changes will help substantiate all the claims made and make the paper read better.\n\n- **[Definite] Adding one DP-quantile baseline beyond ExponQ.** Including a smooth-sensitivity or histogram + Laplace / DP-CDF quantile to show that P-COQS’s efficiency gains are not baseline-specific. _(See References in Section above.)_\n    \n- **[Definite] Ablating ($[a,b]$), ($\\delta$), and ($\\beta$).** Reporting coverage and mean set size vs these knobs and include empirical percentiles of rank error ($\\tau$) to operationalize the theory and guide practice.\n\n- **[Minor if not modify the claim] Slice-wise / shift robustness.** Adding a small Mondrian (per-class) analysis or a covariate-shift stress test to assess coverage beyond the marginal guarantee.\n    \n- **[Optional] Reporting CP-step privacy also in (($\\varepsilon,\\delta$)).** Providing the standard zCDP to DP conversion so the CP privacy budget can be compared with DP-SGD training budgets.\n        \n- **[Optional] Clarifying implementation details.** Stating the tie-handling rule used in experiments (deterministic “($\\le$)” vs randomized), and make Algorithm-1 midpoint/return lines explicit for readability.\n    \n- **[Optional] CIFAR-10 reminder.** In Sec. 5.2.1, including a one-line reminder that “Standard” refers to non-private split CP on the same splits, for quick orientation.", "broader_impact_concerns": "No", "additional_comments": "The review has been modified after the rebuttal to reflect that the under-substantiated claims have now been addressed.", "extra_scores": {}, "extra_text": {}}, {"review_id": "vOM5WwEhVx", "reviewer": "Reviewer_j1Zh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a general Differentially Private approach for Conformity Prediction via Quantile Search (P-COQS), which adapts an existing randomized binary search algorithm for computing DP quantiles. \n\nGiven a dataset, authors spilt it into a training dataset and a calibration dataset. Firstly, trained a model via training dataset, then compute an evaluation score for each data in the calibration dataset to evaluate the model (a lower score means this model more correctly predict this data). Finally, given a test data, it output a subset of the predictions, and this subset of candidates have lower evaluation scores.\n\n\n1.\tThe “exchangeable” in this paper is confusing.\nIn the preliminary, authors say training data and calibrate data are exchangeable\nHowever, in the proof of algorithm, authors treat calibrate data and training data are exchangeable. From the proof of Algorithm 1 and the second to the last sentence of Section 3.1, “Under the assumption of exchangeability of the data points, this set guarantees the coverage probability P(Ytest ∈ C(Xtest)) ≥ 1−α, where the probability is taken over the n + 1 data points (X1,Y1),...,(Xn,Yn),(Xtest,Ytest).”\n\n2.\tThe research problem in this paper is less of meanings. Based on their analyses, there is no privacy issue of calibrate data here.\nAuthors consider calibrating dataset and the test data are exchangeable, actually, they treat them as IID, this is impossible. As the trainer could not get to know the test data, otherwise, he/she can just use this test data to train the model. \n\nEven trying to fix and construct the application scenario, there are still some contradiction. From their algorithm, we can infer that, there should be 3 participators in the scenario. A has the training dataset and train the model, B has the test data, C (as a third party) evaluate the model (from A) to B. Note that, A and C could not be the same person as A could not know the test data. B and C could not be the same person as C should treat the test data privately. Then, there is also a contradiction. If C helps B to test the model, and B give C the data information, then there is no privacy issue.\n\n3.\tTo output a subset of predictions, this in not useful. It is expected to output one exact prediction.", "claims_and_evidence_yn": "No", "claims_explanation": "The research setting in preliminary is not consistent with the proof. For a test data should not be exchangeable with a calibrate data, so the proof theorem is not correct.", "audience_yn": "No", "audience_explanation": "This paper (this version) is not suitable to TMLR.", "requested_changes": "1.\tClarify the research question. \n2.\tThe coverage guarantees are approximate, it do not guarantee exact (1-α)coverage; instead there is an error τ. Although the paper describes this as “controllable,” its quantitative analysis of that term under typical practical parameter ranges (e.g. n_cal,ρ,b−a) is weak, leaving readers unable to judge when the error may become unacceptable.\n3.\tThe experiments of the manuscript were mainly compared with ExponQ (Angelopoulos et al., 2022), which is the appropriate preferred baseline, but other controls can also be supplemented to show the advantages and disadvantages more comprehensively.\n4.\tThe article claims that P-COQS is significantly superior to ExponQ in computation (the average time difference is given in Table 4), but lacks an analysis of the algorithm complexity.\n5.\tThe symbols in the text are not clearly indicated, for example, \\delta.\n6.\tIt is recommended to list both ρ (zCDP) and the converted (ε,δ) in the main text table, so that readers can visually assess the privacy intensity.\n7.\tThe description at the beginning of the experiment section is too lengthy. It is suggested to polish the sentences to make them easier to read.\n8.\tIn Theorem 1, Y_test should be Y", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)