Online Locally Differentially Private Conformal Prediction via Binary Inquiries
Authors: Qiangqiang Zhang
Chenfei Gu
Xinwei Feng
Jinhan Xie
Ting Li
Venue: NeurIPS 2025 poster ()
Keywords: Conformal Prediction
Local Differential Privacy
Online Learning
Pinball Loss
Primary area: general_machine_learning

Abstract: We propose an online conformal prediction framework under local differential privacy to address the emerging challenge of privacy-preserving uncertainty quantification in streaming data environments. Our method constructs dynamic, model-free prediction sets based on randomized binary inquiries, ensuring rigorous privacy protection without requiring access to raw data. Importantly, the proposed algorithm can be conducted in a one-pass online manner, leading to high computational efficiency and minimal storage requirements with $\mathcal{O}(1)$ space complexity, making it particularly suitable for real-time applications. The proposed framework is also broadly applicable to both regression and classification tasks, adapting flexibly to diverse predictive settings. We establish theoretical guarantees for long-run coverage at a target confidence level, ensuring statistical reliability under strict privacy constraints. Extensive empirical evaluations on both simulated and real-world datasets demonstrate that the proposed method delivers accurate, stable, and privacy-preserving predictions across a range of dynamic environments.

Online Locally Differentially Private Conformal Prediction via Binary Inquiries
Qiangqiang Zhang Chenfei 2u
Xinwei Feng'
Jinhan Xie Ting Lift
Zhongtai Securities Institute for Financial Studies, Shandong University
School of Statisties and Data Science, Shanghai University of Finance and Economics
3 Yunnan Key Laboratory of Statistical Modeling and Data Analysis, Yunnan University
Abstract
We propose online conformal prediction framework under local differential pri- vacy to address the emerging challenge of preacc-preserving uncertainty quantifi- cation in streaming data environments. Our method constructs dynamic, model-free prediction sets based on randomized binary inquiries, ensuring rigorous privacy protection without requiring access raw data. Importantly, the proposed algo- rithm can be conducted a one-pass online manner, leading to high computational efficiency and minimal storage requirements with (11) space complexity, making it particularly suitable for real-time applications. The proposed framework is also broadly applicable to both regression and classification tasks, adapting flexibly to diverse predictive settings. We establish theoretical guarantees for long-run coverage at a target confidence level, ensuring statistical reliability under strict privacy constraints, Extensive empirical evaluations on both simulated and real- world datasets demonstrate that the proposed method delivers accurate, stable, and predictions across range of dynamic environments.
Introduction
Modern decision-making systems are increasingly deployed in streaming environments such as real-time bidding, health monitoring, and algorithmic trading, where data distributions evolve over time. In these dynamic settings, reliable uncertainty quantification is essential for ensuring trustwor- thy predictions and maintaining robustness under distributional shift. Conformal prediction (CP) [Vovk et al., 2005) provides powerful, distribution-fies framework for constructing prediction sets with formai finite-sample coverage guarantees. However, traditional CP methods rely on the assumption of exchangeability among calibration samples, an assumption that is often violated in online environments, where data distributions are non-stationary (e.g., due to changing user behavior during pandemic). To address the limitations posed by distributional shifts and exchangeability violations, numerous extensions to CP have been proposed (Tibshirani et al. 2019 Lei and Candès]
2021 Fannjiang et al., 2022 Barber et al. 2023 Plassier al. [0224, incorporating techniques such as weighted quantiles, adaptive calibration, and distributional adjustment.
Among the earliest attempts to bring CP into an online setting, Gibbs and Candes 202 proposed method based on online convex optimization that adaptively adjusts prediction thresholds using per- instance coverage feedback. While this approach marked an important step toward online uncertainty quantification, assumes access to true outcome labels at every time step to verify coverage, an assumption that is incompatible with privacy requirements in potentially sensitive user data such
Eqqual contribution.
Corresponding authors: Jinhan Xieejinhanxie@@muu www.eeu..n. and Ting Listingli @ mail. shufe.edu.cn>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

as patient records in healthcare or physiological signals from wearable devices. Moreover, the algorithm requires pre-specified learning rates, which may result in unstable prediction intervals that are either empty or unbounded in practice. Subsequent efforts have sought to mitigate these
limitations by proposing more stable and adaptive procedures [Zaffran et al. 2022 Angelopoulos
et al. 2023] Bhatnagar et al. 2023] MMore recent work (Podkopaev et al.) 2024 Ge et al. 2024
Angelopoulos et al. 2024] Gibbs and Candès, 2024] continues to advance online conformal prediction
methodologies to better accommodate the challenges of non-stationary, real-time data streams.
Despite these important developments, existing approaches generally lack built-in privacy protection, leaving them vulnerable to information leakage in privacy- -ensssivee applications. As demonstrated by Angelopoulos et al.] [2022), the conformal calibration step itself can leak private information unless explicitly privatized. This highlights the need for a principled framework that integrates uncertainty quantification with rigorous, end-to-end privacy guarantees. Differential Privacy (DP) [Dwork et al.) a0 one of the most widely used frameworks for privacy-preserving data analysis, provides a rigorous mathematical definition that guarantees the output of a computation does not reveal sensitive information about any individual in the dataset. Due to its strong theoretical guarantees and practical utility, DP has seen widespread adoption across a variety of domains, including healthcare, wearable sensors, and public sector services (Dankar and El Emam 2013 Li et al. 2022 Drechsler 2023) Recent research has focused extensively on the central differential privacy (CDP) model, which assumes the existence of a trusted server that can securely collect, store, and process raw user data. This framework has demonstrated effectiveness in a variety of applications, such as deep learning, federated learning, and synthetic data generation [Abadi et al. 2016 Adnan et al. 2022 Ponomareval
ct al.. 2023 Olabim et al. 2024).
Unfortunately, the aforementioned methods based on the CDP model inherently depend on the assumption of trust in the central curator, making it vulnerable to technical breaches, insider misuse, and potential privacy violations if the central server is compromised. In contrast, the local differential privacy (LDP) model eliminates the need for a trusted aggregator by requiring that each user privatize their data at the source, before any transmission to server or analyst (Kasiviswanathan et al. 2011
Duchi et al. 2018 He et al. 2023] Duchi and Ruan 2024]. Owing to its strong privacy guarantees. LDP has been widely adopted in practice by major technology companies such as Google [Erlingsson
ct al. 2014 Song et al. 202T]. Apple (Tang et al. 2017]. and Meta (Yousefpour et al., 2021]. Despite its practical importance, the literature on CP under rigorous privacy guarantees remains relatively limited, even in offline settings. For example, Angelopoulos et al. [2022) proposed a method for constructing conformal prediction sets under CDP, but their approach is limited to static calibration datasets and centralized computation. Recent efforts have attempted to extend privacy guarantees to federated and decentralized frameworks. Humbert al. (2023) applied the exponential mechanism within a federated learning paradigm to perform private quantile estimation across distributed clients. Similarly, Plassier et al.] (2023) introduced noise into gradient updates to derive private prediction sets. Although these methods effectively enforce privacy during downstream processing, they fail to address a critical vulnerability in dynamic environments: the risk of exposure at the time of data acquisition. This highlights a critical gap in the existing literature, the lack of dynamic, model- free methods for constructing prediction sets under LDP that enable real-time, decision-making.
The goal of this paper is to address the critical challenge outlined above. Specifically, we introduce an online CP framework under LDP constraints, a unified approach for distribution-free, privacy- preserving uncertainty quantification in streaming data environments. The overall flowchart of the proposed framework is illustrated in Figure I Our main contributions are summarized as follows:
algorithm that operates fully online in a single-pass, under the one-shot interaction model, where each user is inquired exactly once. The algorithm leverages locally privatized binary feedback to ensure stringent privacy guarantees without direct access to raw user data. By design, it is both computationally and memory efficient, achieving constant time and space complexity (0(1) per instance), making particularly well-suited for dynamic environments in both regression and classification tasks.
We propose a
Our framework is model-agnostic, supporting arbitrary black-box prediction models, in- cluding those trained under DP. In contrast to most existing methods, our approach provides the flexibility to construct fully end-to-end prreecypreserving pipelines when the underlying predictive model trained online is itself private.

---

From a theoretical perspective, provide rigorous analysis of the algorithm''s 's LDP guarantees and show that these extend the entire prediction pipeline when the pre-trained model is also DP, thereby achieving full end-to-end privacy protection. In addition, we establish that the algorithm achieves long-run coverage guarantees at the nominal target level, regardless of the underlying predictive model.
Binary Inquiry
Randomiiedd Response
One-yy-onc
A
Produce Forecuat
Aggregate
Update Private Quanale for Nest Rousad
Ulee
Compute
Moncanformity (Locally
Ouspur
Figure 1: The server processes users sequentially in one-by-on manner. Each user locally computes their own conformity score. Using the private quantile estimate from the previous round, the server constructs prediction set for the current user and issues binary inquiry. Upon receiving the user's randomized response, the server updates the private quantile estimate accordingly and proceeds to the next user in the sequence.
Preliminaries
2.1 Differential privacy
In this subsection, we review the basic concepts and some useful properties of CDP and LDP. Definition 2.1 (CDP, Dwork et al. (2066]), ). Let X be the sample space for individual data, randomized algorithm M: X > R is (c,8)- CDDP D if and only if for every pair of adjacent datasets X, X' C X" and for any measurable event E C R, the inequality below holds:
Px(M(X) E E) S e Pr(MM(X)) E EE)+ +
When 5 = 0, then M is called pure e-D..
This definition enforces privacy at the output level and assumes the existence of trusted curator with access the raw dataset. While such an assumption simplifies algorithm design, does not eliminate the need for trust or mitigate the risks of internal data exposure. To address this limitation, LDP given as follows, which shifts the privacy mechanism to the user side, requiring that data be randomized before collection, thereby removing the need for any trusted data aggregator. The formal definition of LDP is given below.
Definition 2.2 (LDP, Xiong et al. (2020]. A randomized algorithm M X - R satisfies (e, 8)-LDP if and only if. for any pair of input individual values x, E X, and for every measurable event E C R, we have
(x) E S PP(M)(()')) +8.
When 6 = 0, this reduces to pure e-LDP.
LDP ensures privacy at the individual level by requiring each user randomize their data locally before sending it to the data collector. LDP supports different interaction models depending on how users communicate with the server. In this paper, adopt the one-shot interactive LDP setting [Cheu et al. 2019 Liu et al. 2023). wherein each user applies local randomizer exactly once and transmits privatized feedback to the server. This design substantially reduces communication overhead while providing rigorous privacy protection. Specifically, our algorithm assumes that each user is inquired only once, and the server updates its internal state solely based on the privatized responses it receives.
We now proceed to present several key properties of L.P that characterize how privacy guarantees preserved under sequences of operations.

---

Lemma 2.3. [Xiong et al. 2020
Sequential Composition: Suppose mechanisms (M1y..., M,} satisfy 4-LDP, respectively, and are sequentially applied to the private data. Then, the combined mechanism formed by (M1,...,Me, Mn) in some order satisfies (Σi=1 G.)-DPP
Parallel Composition: Suppose n. mechanisms {M M satisfy 4,LDP for i = 1. n. respectively, and are computed on a disjoint subset of the private data. Then, mechanism formed by (M1 (D.).. M, Mn(),)) satisfies max(e;)-LDPP
Postprocessing Property: If mechanism M1 satisfies c-LDP, then for any mechanism M2. even if M2 does not satisfy LDP, the composition My)Mi(-) also satisfies e-LDP.
2.2 Problem formulation
In this paper, we consider an online learning framework in which data arrive sequentially as {(X,, (i))e,,, with X, E X
Rdd and Y, y R. Classical online CP [Gibbs and Candes)
2021] Angellopoos et al. 2023 Gibbs and Candes 2024 Podkopaev et al. 2024] assumes the exis-
tence of a bounded non- non-conformity score function S. X [0, DJ at each time t, where the score S, = SX,,, Yt) quantifies the discrepancy between the model's prediction and the observed outcome.
A common example in regression task is the absolute residual score, Sx(X, Y2) Y (X,),,
where ft X' + E is the predictive model trained in an online manner. The primary goal is to construct a prediction set C₁ at each time such that the long-run empirical coverage converges to a pre-specified nominal level 1 - a. Formally, we aim to satisfy:
1 T T (y (Mee((x))) (1 (1-a)
T _ T
lim T-000
ax) 0.
where the prediction set is given by: C = { E y: S. S ge and the threshold q. is iteratively updated via q++1 qe ne (1(, & (X,)) - a), with n. denoting the step size. This update rule is interpreted as an online (sub)gradient descent algorithm on the quantile pinball loss:
++1 = q:
S.)
with (g, = (14g S.) (1- S.)
While these methods achieve distribution-fii coverage guarantees, they typically require access to accurate feedback indicating whether the true outcome Yú lies within the prediction set C. In privacy- sensitive settings, this feedback can inadvertently disclose personal confidential information, and users may be unwilling or unable to provide truthful responses. Additionally, the underlying predictive model fe may itself be vulnerable to privacy attacks. This limitation highlights the need for a privacy-pree peeeec--reeeiingg online CP framework that mitigates information leakage while maintaining reliable online calibration.
3 Algorithm and main results
In this section, we systematically present our method for constructing online privacy-preserving CP sets using binary inquiries. As outlined in ( each subgradient ( S;) is purely determined by the binary indicator variable representing whether the non-conformity score St is less than or equal to the current quantile estimate q- This inherent binary structure enables to implement local randomization mechanism via randomized response, which directly supports LDP constraints. Motivated by this, we carefully design the binary inquiry presented to the user to adjust the stochastic gradient descent process via subgradient without violating privacy conditions. This leads to a modified update rule in which the deterministic subgradient replaced with privatized binary response, drawn from a locally randomized mechanism. Specifically, upon receiving the privatized binary feedback L LRBR(S,, qt, r), as defined in Algorithm truthful response, the subgradient is updated according to:
|
where r (0, 1] is the probability of
(r(1 a) + 0.5(1 -r)), if gt - (r(1 a) + 0.5(1 r)), otherwise

---

This formulation modulates the strength of privacy protection in the update step according to the response rate r: a smaller value of r corresponds stronger privacy protection, as it increases the amount of randomization in the binary feedback mechanism. Notably, in the special case where r == 1, the mechanism reduces to the non-DP setting, and the update St degenerates to the standard subgradient 1 (t)..))). recovering the standard deterministic subgradient update without any privacy protection [Podkopaey et al. 2024]. The complete procedure is summarized in Algorithm
Algorithm 1: Locally Randomized Binary Response (LRBR)
1 Input: local nonconformity score S. private quantile g, response rate r Bernoulli(r)
3 t ~ Bernoulli(0.5)
if 1 then
return 1 (1>5)
else
L
return v
In Algorithm| D generating the random bit e prior to the conditional branch may appear redundant; however, this design is intentional to prevent side-channel attacks, such as inferring the true value based on variations in response timing [Coppens et al.) 2009 Lawson 2009
To enable private, adaptive quantile estimation in an online setting. we adopt coin betting-based online convex optimization framework [Orabona and Pal. 2016 Cutkosky and Orabona 2018
Podkopaev al. 2024]. This parameter-free ffreee and robust method reformulates the learning process as a repeated betting game framework, providing regret guarantees even in adversarial environments. Within this framework, gambler sequentially bets fraction X E [-1, 1] of their current wealth W on an outcome G. E [-1, 1]. which may be adversarially chosen as in [Orabona and Pal 2016). Starting from initial endowment Wo >> O, the cumulative wealth evolves according to: W. Wo + EL A -- To adaptively adjust X based sequential feedback, we use the Baaievsky-Trrffmmo (KT) estimator [Krichevsky and Trofimov 1981). which sets: X = Eizl ct/t. To integrate this with our privatized quantile estiattio, ge is the privatized subgradient in equation (3). The signed bet w. := A,W,-1 1 is then interpreted as the current privatized estimate of the (1 a -quantile, denoted as qt- This feedback is used to update the coin betting procedure at each step. The resulting design enables the algorithm to adaptively refine its quantile estimate based on privatized, binary feedback while maintaining rigorous LDP guarantees. We summarize the proposed procedure for the regression task in Algorithm 2 extension to classification tasks is presented in Section 4
define the feedback as Ce == -9t. where
The corresponding
In our framework, the predicted value Y, will be transmitted to the curator in order to construct the prediction interval Ć = [Y, q. go]. As such intervals inherently disclose the quantile threshold 4. inquiring the user based on this value does not introduce additional privacy risk. Importantly, 9: is updated via the above proposed mechanism that satisfies LDP, thereby ensuring rigorous individual- level privacy protection, even when 4 is externally observable. Specifically. ge is estimated via binary inquiries, which provide several practical advantages. Each inquiry conveys only a single bit of information, substantially reducing communication overhead and improving transmission efficiency. In contrast to open-ended inquiries, binary inquiries are more intuitive and cognitively accessible, thereby enhancing user comprehension and response fidelity [Brown et al. [996). Beyond communication efficiency, our framework facilitates fully online computation, eliminating the need to store or re-access historical data. As result, it significantly reduces memory and computational demands, making our method particularly well-suited for streaming applications [Lee al. 2022).
In online learning, regret quantifies the cumulative difference between the learner's performance and that of fixed comparator. Formally, let {g. (e) denote the sequence of decisions made by the algorithm. The regret with respect to a fixed comparator q² E R is given by:
Rr(a")
Σ
- (((a")
We provide the regret bound as follows in Corollary 3.1
5

---

Algorithm 2: Binary Private Online Conformal Prediction
Input: Data stream {(x,, V,) (21: Response rate ry E (0, 1); Miscoverage level a E (0, 1);
Initialize Wo = 1, X1 = 0, =
for == 1....... do
// Train a predictive model fe(-) Predict Y, + fi()));
// Generate conformal prediction interval
Output: the private prediction interval: Č₁ := [Y, g:: Y, + qr];
// Compute nonconformity score (kept locally) Nonconformity score: S, = 1Y; Ytl:
// Preparing updated rule for next round Inquiry LRBR response: L <- LRBR(S,, qt, rt); i then
9r. 1 (rr - a) 0.5(1 T:));
else
L 9t
(ri a) + 0.5(1 r)));
Update: We t Wi-1 9196
10
Update: Ac+1 & F+I 4IG
Update: 9++1 +- \
Corollary 3.1. Let f4: S K denote the sequence of decisions produced by the proposed algorithm. Under the coin betting framework with the KT potential, the cumulative regret with respect any fixed comparator q" E IR satisfies the following bound:
R7 (4')
Σ 4(a)) -
TV
where C is a universal constant, and denotes the base of the natural logarithm.
3.1 establishes a sublinear cumulative regret bound within the coin betting framework. Specifically, the regret bound of order O(VT In T) ensures that the cumulative loss incurred by the algorithm relative to any fixed comparator q" grows sublinearly over time. Consequently, the average per-round regret asymptotically converges to zero T + co.
Corollary
Theorem 3.2. Algorithm 7 is an (e, randommiee with e log + (1++)\(1-r))
Proof. With probability r, the user returns a truthful binary response indicating whether S < y:: otherwise, a fair coin is flipped. This randomized mechanism masks the true response, and the privacy level e determined by the worst-case distinguishability between outputs for different true answers. A full derivation is deferred to Appendix
Theorem 3.3. Algorithm 2 satisfies maxx 0)-LDDP
0)-LDP, where t 2 1.
Proof. By parallel composition and the post-processing property, the guarantee holds. A detailed argument deferred to Appendix C.3
Theorems 3.2 and 3.3 establish that the proposed algorithms satisfy rigorous LDP guarantees. The
proposed algorithms ensure that individual-level privacy is preserved every iteration, without the need to store or re-access raw data, thereby enabling both privacy protection and memory efficiency in streaming environments.
Although our algorithm satisfies LDP at the user level, an adversary could still exploit vulnerabilities the underlying predictive model to infer sensitive information. To address this concern, we establish rigorous form of privacy protection: when the predictive model is dynamically trained under LDP constraints, our framework also ensures end-to-end privacy guarantees across the entire prediction pipeline.

---

Theorem 3,4. Suppose the predictive model satisfies (maxigışt E,, maxisist 6,)-LDP. The entire pipeline, mapping private individual data to the final prediction interval Č₁ inherits LDP guarantees. Then, Algorithm 2 ensures (maxisjsoly) + Ez). maxisis: 6,)-LDP, where t t 1.
Proof. By additionally applying the sequential composition property, the theorem follows. complete proof is deferred to Appendix C.4
The
IT
We illustrate this process in Figure 13 which empirically validates the consistency between simulation results and the theoretical guarantee established in TheoremB.4
Theorem 3.5. Let the target miscoverage level a E (0, 1/2) be fixed, and let (0, 1] denote the probability of a truthful response. Suppose that the non-conformity scores are bounded, such that a finite constant. Then, the proposed procedure
S. E 10, DJ for all t 1, ..., where D described in Algorithm 2 satisfies the following long-run coverage guarantee:
1 (I(r (1- 0.
lim T-000
(4)
T
Proof. Although each feedback bit randomized, its expectation coincides with the true subgradient:
Elgl = r- (I{S, < 9.} - -a)).
Hence, the update rule drives a toward the (1 a) quantile in expectation. By boundedness of the scores and stability of the coin-betting update, the prediction sets converge to the desired long-run coverage. A complete derivation is provided in Appendix C.5
Theorem 3.5 jestablishes that the proposed method achieves valid long-run coverage guarantees that are independent of the underlying predictive model, regardless of whether the model is dynamically trained with or without privacy constraints. However, because q: is defined as the (1 a -quantile of the non-conformity scores, models trained under LDP often exhibit decreased predictive accuracy due to the injected noise. This typically results in larger non-conformity scores and consequently wider prediction intervals. To illustrate this effect, include representative experiment using the privately trained predictive (Pdel(PTM) from Abadi et al. (016). dynamically trained under LDP constraints; see Figure 12
4 Extension to classification tasks
In this section, we extend our framework from regression to multi-class classification problems, where the response variable takes values in finite label set V. Unlike regression, where prediction intervals are centered around scalar estimates, classification requires constructing prediction sets containing likely class labels. This shift necessitates adapting both the definition of non-conformity scores and the structure of the prediction region. Given probabilistic classifier f RRd [0, |) we define the non-conformity score for a candidate label y E y as
Sy(X, y) = - (X)),
where (X) denotes the predicted probability assigned to class y. typically computed via softmax over the model's logits. Intuitively, this score captures the model's uncertainty about the correctness of label y: smaller scores correspond to more confident predictions. At each time step I, the prediction set is constructed by including all labels whose non-conformity scores fall below a dynamic quantile threshold:
i (X,) tu E y Sy(X,, v) g.).
The threshold 9t. analogous to the conformal quantile used in the regression setting, is updated sequentially based on privatized binary feedback. To ensure privacy, we adopt the same binary inquiry strategy in Section 3 Specificallyy, the non-conformity score for the true label, S = S (X,, Y:). is compared against the current threshold and the result of this comparison is encoded as binary signal, which is privatized using a local binary randomized mechanism. The privatized feedback is then used to compute a subgradient dt (as defined in Equation (3). and the sign-reversed quantity G: : - is passed to the coin-betting algorithm to update d an efficient and privacy-preserving manner. The complete procedure for the classification task is summarized in Algorithm
7

---

Table 1: Coverages and widths for the proposed method, DPCP and DIACI in Example 5.1 in parentheses denote standard deviations for coverage (x10 3) and for width (x10 10
Numbers
Method
no-privacy
0.5 Width
Coverage
Width
Coverage
Width
Coverage
Width
Coverage
Case A
Proposed 0.890 (0.03) 3.43 (0.30) 0.889 (0.30) 3.42 (0.40) 0.875 (1.00) 3.36 (1.20) 0.853 (2.10) 3.28 (2.70)
DPCP 0.900 (0.51)
8.29 (1.02) 0.904 (0.52) 8.40 (1.07) 0.911 (0.61) 8.60 (1.48) 0.922 (0:90) 8.95 (2.96)
DIACI 0.897 (0.09) 3.47 (0.30)
Case B
Proposed 0.890 (0:05) 4.46 (0.96)
0.889 (0.26) 4.44 (1.30)
0.874 (0.90)
4.22 (2.91)
0.850 (1.82)
3.83 (5.06)
DPCP
0.900 (0.54) 9.00 (1.45) 0.904 (0.53) 9.14 (1.56)
0.911 (0.00)
9.40 (2.19)
0.923 (0.93)
9.89 (4.55)
DtACI
0.899 (0.07) 4.76 (1.02)
Case C
Proposed 0.890 (0.03) 3.26 (0.30)
0.889 (0.27) 3.26 (0.37)
0.875 (1.06)
3.21 (1.03)
0.852 (1.92) 3.11 (1.89)
DPCP 0.900 (0.50) 4.43 (0.63) 0.904 (0.51) 4.49 (0.60) 0.911 (0.6)) 4.60 (0.8)) 0.920 (1.01) 4.80 (1.99)
DIACI
0.899 (0.m) 3.34 (0:27)
Case D
Proposed 0.890 (0:03) 3.26 (0.31)
0.889 (0.22) 3.26 (0.36)
0.875 (1.02) 3.21 (1.02) 0.853 (1.90) 3.11 (2.10)
DPCP 0,900 (0.53) 3.29 (0.41) 0.904 (0.53) 3.33 (0.42) 0,911 (0.62) 3.40 (0.58) 0.922 (0.97) 3.53 (1.19)
DIACI 0.899 (0.08) 3.34 (0.29)
5
Experiments
We evaluate the finite-sample performance of the proposed estimator by comparing it with two baselines: DPCP (Angelopoulos et al. [022]. an offline private conformal method, and DtACI [Gibbs) and Candès 2024). . an online adaptive method using expert aggregation. For ease of interpretation. the privacy parameter is set to 0.5, 1, 2, with the corresponding values of r provided in Table 4 We define the miscoverage level as a 0.1.
Example 5.1 (Regression on Synthetic Data). In this example, we evaluate the proposed method on the regression task using synthetic data. We generate data similar to Barber et al., 2023) via It ~ (O, Is) and y/: = x, 3t + e for = 1,.... 10,000, where 3g E R and e, is from a normal distribution and independent of rą. We consider four cases. (A) Abrupt shifts with homoskedastic errors; (B) Abrupt shifts with heteroskedastic errors; (C) Smooth shifts with homoskedastic
errors; (D) No shifts with homoskedastic errors The sample size is set to 10,000. Long-run coverage and interval width are evaluated over these data points and averaged across 200 simulation runs. See Appendix B.T for data generation.
Table [ rrports coverage and interval width for both methods across four cases at the 90% confidence level. In drifting environments that are closer to real-world data streams, the proposed method achieves slightly lower but comparable coverage to DPCP, while producing substantially narrower intervals. Specifically, DPCP's widths more than double in Cases A and B and increase by over 40% in Case C. This is expected, as DPCP operates in a fixed-sample offline setting and constructs conservative intervals without adapting to distributional shifts. In contrast, our online method updates intervals in real time, allowing for more efficient and adaptive inference. In the static setting without distributional shifts, as in Case D, DPCP's higher coverage becomes more favorable. For DtACI, which is designed for online settings without privacy constraints, we compare it under the no- privacy scenario. The proposed method again yields shorter intervals while maintaining comparable performance, with slightly lower coverage.
We compare the computational efficiency of the three methods. Table shows that DtACI, with six experts, requires approximately 100 times more computation time due to its complex update rules, and DPCP requires approximately 10 times.
The left panel of Figure 2 shows instant coverage, instant width, long-run coverage, and long-run width for DIACI with initialization values on E {0.1. 0.9). and for the proposed method under varying privacy levels. DPCP is omitted as it is an offline method. All methods exhibit coverage oscillations around the target level of a, with noticeable drops change points but rapid recovery
8

---

thereafter. Lower values result in slightly larger fluctuations. Initially, smaller values lead to lower long-run coverage. but all methods eventually converge to the target level. similar pattern is observed for instant width and long-run width. The results also show that DrACI is sensitive to initialization and requires each expert to adjust predictions based on interval coverage, leading to frequent feedback requests. As the number of experts increases, this can cause user fatigue and raise privacy concerns, limiting its use in privacy-sensitive settings. In contrast, the right panel of Figure 2 shows that the proposed method is robust to initialization, demonstrating consistent performance across different settings. Results for Case Figure Case C in Figure and Case Figure of the Appendix exhibit similar patterns.
Table 2: Computational time (in seconds) of the proposed method, DPCP and DIACI.
Method
T=5000
T=10000
T=15000
T=20000
T=25000
DIACI
3.46
7.03
11.17
14.84
19.34
DPCP
0.931
1.003
1.077
1.234
1.378
Proposed
0.037
0.069
0.100
0.133
0.167
Instant Coverage/ Width
Long-run Coverage Width
Instant Coverage Width
Long-run Coverage Width
6.
0.7
0.0
0.5
0.5
6.0
6.0
5.5
Time
Time
6993
10000
10000
Time
Time
Figure 2: Results for Case A in Example 5.1 Left panels: comparison of methods by instant coverage, instant width, long-run coverage, and long-run width. Right panels: impact of initialization settings (Wo, A1) for the proposed method with c 3.
Example 5.2 (Classification on synthetic data). We also conduct a classification study using synthetic data, encompassing three distribution shift scenarios plus one no shift environment. The findings are generally similar to those in the regression setting. To save space, we relegate the detailed results to Appendix B.2
Example 5.3 (Regression on Real Data). We use the ELEC2 dataset Harries et al. 1999 As shown in Figure TT of the Appendix, lower values lead to slightly larger fluctuations coverage. Nevertheless, the long-run coverage stabilizes around - a within the first quarter of the data stream for all methods. Similar patterns are observed in the width and long-run width. Further details are provided in Appendix [B.3]
Example 5.4 (Classification Real Data). We assess the classification performance of our method using the real WISDM dataset [Kwapisz et al. 2011]. benchmark for smartphone- recognition. We focus on two representative users User 10 and User 14 who completed and 4 activity types, respectively, forming two independent tasks. For each task, we construct time- indexed data stream and implement the model f, using XGBoost. Rolling coverage is calculated using a sliding window 200 points to capture short-term fluctuations, while long-run coverage reflects the cumulative average over all time steps. Set size (Angelopoulos et al. 2022 indicates the
activity
number classes included the prediction set, representing model uncertainty. Lower values at given coverage level indicate better performance.

---

Figure 3 shows the results for both users under varying privacy settings of DtACI and the proposed method. Patterns are generally consistent with the simulation studies. With stronger privacy (c (c>+) 1), rolling coverage shows increased variability due to amplified noise. Long-run coverage initially decreases but gradually converges to the target level. For set size, lower e values slightly increase the occurrence of larger sets, indicating increased uncertainty. However, small and medium-sized sets remain dominant overall. DIACI is also sensitive to the initial setting of a1, initially deviating more but ultimately aligning with the non-private and low-noise settings.
User 14 Set Size Distribution
10000
Rolling Coverage
Long-run Coverage
14000
Covvrrage
10006
Count
10000
5006
8000
User 14
4000
2000
Time
Time
Method
Rolling Coverage
Long-run Coverage
User 10- Size Distribution
User Coveradd
10000
5000
Re
Count
6006
5000 20000 15000 20000 25000 38000
5000 10000 15000 20000 25000 30000
Proposediton-priiee
Prepisedl:=2)
DIACHo;
Proposedi:- 1)
Method
Figure 3: Evaluation of method performance terms of coverage and set size for User 14 (top), and User 10 (bottom).
6 Conclusion and Limitations
This paper proposes a novel and practical framework for online conformal prediction under LDP. By combining randomized binary feedback with coin-betting update scheme, the method enables one-pass, model-free prediction set construction with formal privacy guarantees. It supports both regression and classification, and operates efficiently in streaming settings with constant memory. Despite its strengths, several limitations remain. First, Theorem 3.5 provides only asymptotic coverage guarantees; deriving non-asymptotic bounds under LDP is an important direction for future work. Second, our approach employs standard nonconformity scores, which are broadly applicable but may yield conservative prediction sets. Incorporating ideas from recent methods such CP- Gen [Bai et al. 2022]. which learn data-adaptive scores via constrained ERM, could lead to more efficient prediction sets while preserving valid coverage. Another promising direction is to extend our framework to multivariate private online conformal prediction, building on recent advances such [Xu al., 2024] and (Braun et al., 2025 Such extensions would broaden the applicability of private online conformal prediction to digh-dimensional and structured data streams.
Acknowledgements
We sincerely thank the reviewers, ACs, SACs, and PCs for their time, constructive feedback, and thoughtful discussions. Qiangqiang Zhang and Xinwei Feng were supported by the National Key R&D Program of China (No. YAA 1008701) and the National Natural Science Foundation of China (Grant Nos. 12371148, 12326603, and 1243 1017).. Chenfei Gu's research was supported by the Fundamental Research Funds for the Central Universities (No. CXJJ-2024-448), Jinhan Xie's tie's research was partially supported by the National Key R&D Program of China (10002)YFA003700)) and the National Natural Science Foundation of China (No. 12501388). Ting Li's research was partially supported by the National Natural Science Foundation of China (No. 12571304), the Shanghai Pujiang Programme (No. 24PJC030), CCF- DiDi GAIA Collaborative Research Funds and the Program for Innovative Research Team of Shanghai University of Finance and Economies.
10

---

References
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
Mohammed Adnan, Shivam Kalra, Jesse C Cresswell, Graham W TTylor, and Hamid R Tizhoosh. Federated learning and differential privacy for medical image analysis. Scientific reports, 12(1): 1953, 2022.
Anastasios Angelopoulos, Emmanuel Candes, and Ryan Tibshirani. Conformal pid control for time series prediction. In Advances in Neural Information Processing Systems, volume 36, pages 23047-23074, 2023.
Anastasios Nikolas Angelopoulos, Stephen Bates, Tijana Zrnie, and Michael I Jordan. Private prediction sets. Harvard Data Science Review, 4(2), 2022.
Anastasios Nikolas Angelopoulos, Rina Barber, and Stephen Bates. Online conformal prediction with decaying step sizes. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 1616-1630. PMLR, 21-27 Jul 2024.
Yu Bai, Song Mei, Huan Wang, Yingbo Zhou, and Caiming Xiong. Efficient and differentiable conformal prediction with general function classes. arXiv preprint arXiv: 1091, 2022.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 86--855,,,85, 2023.
Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved online conformal prediction via strongly adaptive online learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 2337-2363. PMLR, 23-29 Jul 2023.
Sacha Braun, Eugène Berta, Michael Jordan, and Francis Bach. Multivariate conformal prediction via conformalized gaussian scoring. arXiv preprint 20Xv:25507.20411 2025.
Thomas C Brown, Patricia A Champ, Richard C Bishop, and Daniel W McCollum. Which response format reveals the truth about donations to a public good? Land Economics, pages 152-166, 1996.
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Advances in CrUROOlgy-EUROCKYYP 2019: 38th Annual International Conference the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part 38, pages 375-403 Springer, 2019.
Bart Coppens, Ingrid Verbawwhede, Koen De Bosschere, and Bjor De Sutter. Practical mitigations for timing-bace based side-channel attacks on modern x86 processors. In 2009 30th IEEE symposium security and privacy, pages 45-60. IEEE, 2009.
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Proceedings of the 3/st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1493-1529, PMLR, 06-09 Jul 2018.
Fida Kamal Dankar and Khaled El Emam. Practicing differential privacy in health care: A review. Trans. Data Priv., 6(1):35-6) 2013.
Jörg Drechsler. Differential privacy for government agencies- are we there yet? Journal of the American Statistical Association, 118(541)761--73, 2023.
John C Duchi and Feng Ruan. The right complexity measure in locally private estimation: is not the fisher information. The Annals of Statistics, 52(1):1-51, 2024.
John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally
private estimation. Journal of the American Statistical Association, 113(521):182-200 2018.

---

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances crypology-EUROCRYPP EUROCRYPT 2006: 24th annual international conference on the theory and applications of cryptographic techniques, st. Petersburg, Russia, May 28-June 1, 2006. proceedings 25, pages 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. pages 265-284, Springer, 2006b.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
Clara Fannjiang, Stephen Bates, Anastasios N Angelopoulos, Jennifer Listgarten, and Michael I Jordan. Conformal prediction under feedback covariate shift for biomolecular design. Proceedings of the National Academy of Sciences, 119(43): 19, 2022.
Haosen Ge, Hamsa Bastani, and Osbert Bastani. Stochastic online conformal prediction with semi-bandit feedback. arXiv preprint arXiv:2455.13268, 2024.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. In Advances in Neural Information Processing Systems, volume 34, pages 1660-1672, 2021.
Isaac Gibbs and Emmanuel J Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1 2024.
M. Harries, University of New South Wales. School of Computer Science, and Engineering. Splice-2 Comparative Evaluation: Electricity Pricing. PANDORA electronic collection. University of New South Wales, School of Computer Science and Engineering, 1999.
Zaobo He, Lintao Wang, and Zhipeng Cai. Clustered federated learning with adaptive local differential privacy on heterogeneous iot data. JEEE Internet of Things Journal. 11(1):137-146, 2023.
Pierre Humbert, Batiste Le Bars, Aurélien Bellet, and Sylvain Arlot. One-shot federated conformal prediction. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Reseurch, pages 14153-14177. PMLR, 23-29 Jul 2023.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-82) 826, 2011.
Raphail Krichevsky and Victor Trofimov. The performance of universal encoding. IEEE Transactions on Information Theory, 27(2) 1981
Jennifer R Kwapisz, Gary M Weiss, and Samuel Moore. Activity recognition using cell phone accelerometers. ACM SigKDD Explorations Newsletter. 12(2):74-82, 2011.
Nate Lawson. Side-channel attacks on cryptographic software. IEEE Security & Privacy, 7(6) 68, 2009.
Sokbae Lee, Yuan Liao, Myung Hwan Sco, and Youngki Shin. Fast and robust online inference with stochastic gradient descent via random scaling. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7381-7389, 2022.
Lihua Lei and Emmanuel J Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(5):91 1--98,, 2021.
Zhangbing Li, Baichuan Wang. Jinsheng Li, Yi Hua, and Shaobo Zhang, Local differential privacy protection for wearable device data. Plos one, 17())cc0272766 2022.
Yi Liu, Qirui Hu, Lei Ding, and Linglong Kong. Online local differential private quantile inference In Proceedings of the 40th International Conference on Machine Learning. via volume 202 of Proceedings of Machine Learning Research, pages 21698-21714, PMLR, 23-29
Jul 2023.
12

---

Merumu Olabim, Amir Greenfield, and Arjun Barlow. A differential privacy-based approach for mitigating data theft in ransomware attacks. Authorea Preprints, 2024.
Francesco Orabona and David Pal. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, volume 29, 2016.
Vincent Plassier, Mehdi Makni, Aleksandr Rubashevskii, Eric Moulines, and Maxim Panov. Confor- mal prediction for federated uncertainty quantification under label shift. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 27907-27947. PMLR, 23-29 Jul 2023.
Vincent Plassier, Nikita Kotelevskii, Aleksandr Rubashevskii, Fedor Noskov, Maksim Velikanov, Alexander Fishkov, Samuel Horvath, Martin Takac, Eric Moulines, and Maxim Panov. Efficient conformal prediction under data heterogeneity. In Proceedings of The 27th International Confer- ence on Artificial Intelligence and Statisties, volume 238 of Proceedings of Machine Learning Research, pages 4879 4987..87..00 PMLR, 02-04 May 2024.
Aleksandr Podkopaev, Dong Xu, and Kuang-Chil Lee. Adaptive conformal inference by betting, In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 40886-40907. PMLR, 21-27 Jul 2024.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence 2023.
Research,
Shuang Song. Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2638-2644 PMLR, 13-15 Apr 2021.
Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Privacy loss in apple's implementation of differential privacy macos 10.12. arXiv preprint 17Xiv:1709.02753, 2017.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. In Advances in Neural Information Processing Systems, volume 32, 2019.
V. Vovk, A. Gammerman, and G. Shafer. Algorithmic Learning in Random World. Springer US, 2005. ISBN 9780387001524.
Xingxing Xiong, Shubo Liu, Dan Li, Zhaohui Cai, and Xiaoguang Niu. A comprehensive survey on local differential privacy. Security and Communication Networks, 2020(1):8829533) 2020.
Chen Xu, Hanyang Jiang, and Yao Xie. Conformal prediction for multi-dimensional time series by ellipsoidal sets. Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 55076-55099, PMLR, 21-27 Jul 2024.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao et al. Opacus: User-friendly differential privacy library pytorch. arXiv preprint arXiv:2109.122 109.9229.. 2021.
Margaux Zaffran, Olivier Feron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 25866. PMLR, 17-23 Jul 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer:[Yes]
Justification: The abstract and introduction clearly state the main claims, including the development of online LDP-based conformal prediction framework (Section and its extension to classification tasks (Section 4p. Section 3] introduces the proposed method within regression setting, providing theoretical guarantees for privacy, regret, and long-run coverage, with complete proofs in the Appendix. Experimental validation in Section further supports these claims, with additional results included in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the proposed framework are discussed in Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Theoretical results, including privacy guarantees, regret analysis, and long-rum coverage, are presented in Section 3 with complete assumptions stated. Detailed proof' are provided the Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental procedures, including data sources (WISDM, Elec2), data preprocessing steps, and evaluation metrics, are fully detailed in Section SectionSJandd Appendix [B.l B.2 and B.3, Algorithmic procedures and parameter configurations are clearly specified in A Algorithms and ensuring comprehensive reproducibility of reported results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
The authors should provide scripts to reproduce all experimental results for the new reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The implementation code and detailed instructions for reproducing the experi- mental results will be provided the Supplemental Material submitted alongside the paper. The datasets used (WISDM [ (waaiss et al. [011], Elec2 (Harries et al. [999]) are publicly accessible and cell-documented in the eited references, making them easy locate and access.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//mips.ccppubic//uui http://dddde/deSSSubbbiiiii Sat////ooSSSSeiaaeeeeeeee httpeeeseeeeeeeeeeeeeieieoool.oa
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All training and testing details are fully specified in Section 5 and Appendix B.1 B.2 and B.3] Detailed parameter settings and experimental procedures are also provided in the supplemental material to ensure reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
16

---

Answer: [Yes]
Justification: The statistical significance of the experimental results is assessed through coverage rates (1 (r) and interval widths, as shown in multiple figures (e.g., Figures 2 The 0.9 coverage line clearly marked to illustrate the target coverage level. Additionally, Tables I and 3 provide comprehensive comparisons of coverage rates and interval lengths across different methods.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments were conducted laptop equipped with 16GB RAM and an AMD Ryzen 9 7940HX processor with Radeon Graphics. The runtime comparison between the proposed method and DtACI is provided in Table 2 ensuring consistent hardware configuration for fair comparison and reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research strictly adheres to the NeurIPS Code of Ethics, as the study is based on publicly available datasets (WISDM [Kwapisz et al. 2011], Elec2 (Harries et al., 1999)) and does not involve any sensitive or personally identifialle information. All data
usage and analysis are conducted in compliance with data usage guidelines and ethical standards.
17

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[Yes]
Justification: Both potential positive and negative societal impacts of the proposed method are discussed in Section
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The study does not release any new datasets, models, or assets that pose potential risks for misuse. All experiments are conducted using publicly available datasets without sensitive or potentially harmful content.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
18

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have properly mentioned and cited all assets used in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's ' creators.
New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper proposes new algorithm for online private conformal predic- tion, but no new assets such as datasets, models, or code repositories are released. All experimental implementations are based existing publicly available datasets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This study does not involve crowdsourcing or research with human subjects, as all experiments were conducted using synthetic data and publicly available datasets without human participation.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
19

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer:[Na
Justification: This study does not involve human subjects crowdsourcing data collection, and therefore no IRB approval or equivalent ethical review was required.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
The core methods and experimental framework of this research do not involve the use of Large Language Models (LLMss). The proposed methodology based solely on online LDP mechanisms and adaptive quantile updates, without utilizing L.MMs as components any theoretical or empirical development.
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy http:p//eerrrrpsscc///////eeeeep for what should or should be described.
20

---

Appendix
A Algorithm for classification under binary private online conformal prediction
Algorithm 3: Binary Private Online Conformal Prediction (Classification)
Input:
Data stream {(X,, Yi) Response rate E (0, 1); Miscoverage level a E (0, 1); Initialize Wo À 0, q1 =
for f = =, 1,2..... do
// Train predictive model fe(-)
Compute probability vector: (x,) < (X),, where px(,), = (X,), ............)).......
// Generate conformal prediction set
Output: the private prediction set: I'r(X.) {y E E 1 Py,((X)) s ac):
// Calculate nonconformity score (kept locally) Nonconformity score: S, = 1 (X,); // Preparing updated rule for next round Inquiry LRBR response: L < LRBR(S, rx); if then
1 (r:(1 - a) 0.5(1 rt));
else
9t - (ri(1 a) + 0.5(1 r:));
// Update wealth and quantile estimate Update: W. Wi-1 9:9 10
Update: det1 F+I ) 9
11
Update: g++1 +- A Wr;
B Additional Results
B.1 Regression Setting
Data generation regression. Similar to Barber al. [0233] we generate data via x ~ N(0 Is) and yr = x 9. + et for = ...... 10,000, where 3, T and e, is Gaussian noise. We consider the following four scenarios:
(1) Abrupt regime shifts. We define three fixed coefficient vectors:
g01) = (1,2,1,0,0), 3 = (0, -,, 1, -2
-), g(3) = (0, 0, 1,2,
and assign 3: = 3(0 for three consecutive segments of t. Under this setting, we consider two noise variants: Case (A) uses homoskedastic noise E, ~ NO 1), and Case (B) uses heteroskedastic noise
= . T with 7/2 ~ (N 1).
(2) Smooth concept drift. We let Be evolve linearly time:
t 1
B, (1 - -aa)) + aggends
1'
where Bxtatt 21, 1, 0) and 3und (0,0, 1). The noise is homoskedastic with e, AO, 1), denoted as Case (C).
(3) Fixed environment. We keep the coefficient vector fixed throughout the whole stream:
3 (1,2,1,0,0), Vt= 1, 10,000,
21

---

with homoskedastic noise ~ (0, 1). This is denoted as Case (D).
Figures 4 present the simulation results for Case B and Case C, respectively. The general character- istics of the proposed method are consistent with those observed in Case A, though some differences arise due to the distinct data generation settings. In Case B, the heteroskedastic noise structure leads to more pronounced fluctuations and wider intervals compared to Case A. Conversely, in Case C and Case D, the absence of abrupt regime shifts results in relatively stable coverage and interval width throughout the data stream.
Instant Coverage Width
Long-run Coverage Width
1.0
Coverage
0.8
0.7
0.6
0.5
Interval Length Case B
8.0
6.0
4.0
2.0
DEACHO, 0.1)
DEACHe; 0.9)
Proposed(Non-pprvaatt)
Proposed(e= 3) Proposed(e
Proposed(e= 0.5)
Figure 4:
Simulation results for regression in Case B, comparing different methods in terms of instant coverage, instant width, long coverage, and long-run width. The results are averaged over 200 runs, excluding the first 200 data points.
Instant Coverage Width
Long-run Coverage Width
1.0
Covarage
0.8
0.7
0.6
0.5
Case C
Interval Length
5.0
4.0
3.0
2.0
2000
8000
10000
2000
4000
8000
10000
Time
Time
DeACH 0.1)
DeACHl, 0.9)
ProposediNoonprivatte
Proposed(s 3)
Proposed(s -1)
Proposedtr 0.5)
Simulation results for regression in Case C, comparing different methods in terms of instant coverage, instant width, long-run coverage, and long-run width. The results are averaged over 200 runs, excluding the first 200 data points.
Figure
B.2 Classification Setting
Data generation for classification. We evaluate our method under four scenarios, each generating data stream ((I,, [ where 2, (0, 0, 1p) and ye {O...., K 1} is drawn from the softmax
22

---

Instant Coverage Width
Long-run Coverage / Width
1.0
0.9
0.7
0.6
0.5
Interval Case D
0.4
5.0
4.0
3.0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10090
Time
Time
DeACH 0.1)
0.9)
Propesed(Non-privatt))
Proposed[:- -3
Proposed(c
Propesed(c- 0.5)
Simulation results for regression in Case D, comparing different methods in terms of instant coverage, instant width, long- coverage, and long-run width. The results are averaged over 200 runs, excluding the first 200 data points.
Figure 6:
model:
exp((8!)) r4)) Σj= exp(18( xzi)
Ply xx)
For each scenario, the coefficient vectors
(hth evolve linearly over time as:
8(h (1 3 (r.((k)
1
O2
1-1
Smooth Drift (Case 1) In this setting, we consider K classes and p 3 features. Classes and drift symmetrically along the first feature, while class 2 remains fixed. The coefficient vectors defined as follows:
( start = [ 0,0, O), 3:00 [1, 01, B = 0, 3 =
8(2) [0, 0, 1].
Amplified Drift (Case 2) This setting is a variant of the Smooth Drift scenario but with doubled drift magnitude. The number of classes and features remains the same (K 3,P = 3). The coefficient vectors are defined as:
3 start | 0,0],
((0) end
02,0,0,,
e 02,0,0, 3 = 1,
8
[0, 2].
Class Emergence (Case 3) This setting introduces class that gradually emerges by activating a specific feature, while the other classes remain fixed. Here, we consider K = 4 classes and = features. The coefficient vectors defined as:
3
2, 0,
((1) 2,,0,000,0) g(3) = [0,0,0.0.4]. end
B [0, 2,0.0)
g(3) start
0.0.0.0.0)
No Drift (Case 4) 3):
As a control setting, we consider no drift: all classes remain fixed (K = 3. =
8 = 8.5h [1,0,0, 8 = (0,0,
Figure shows the coverage and set size of the prediction sets for the outcome labels. For a fixed coverage level, smaller set size indicates higher efficiency. The observed patterns align closely with those in the regression setting. DIACI, initialization particularly sensitive. When the initial a set equal to the target miscoverage level a 0.1. the initial prediction sets are relatively large and
23

---

Table 3: Coverages and set sizes for the proposed method DPCP and DIACI in Example 5.2
Numbers in parentheses denote standard deviations for coverage (x10-2) 22) and for width ( (x10*
Method
no-privacy
c 0.5
Coverage
size
Coverage
size
Coverage
size
Coverage
size
Case
Proposed 0.890 (0.02) 2.17 (0.16) 0.889 (0.24) 2.17 (0.20) 0,875 (1.05) 2.16 (0.55) 0.854 (2.09) 2.11 (1.02)
DPCP 0.900 (0.42)
2.19 (0.14) 0.902 (0.41) 2.20 (0.15 0.905 (0.44)
2.22 (0.17) 0.911 (0:53) 2.25 (0:24)
DtACI 0.901 (0.08) 2.20 (0.15)
Case
Proposed 0.890 (0.03) 1.69 (0.16) 0.889 (0.25) 1.69 (0.22)
0.875 (1.04)
1.70 (0.62)
0.853 (2.03)
1.67 (1.16)
DPCP 0.901 (0.42)
1.72 (0.16)
0.902 (0.42)
1.73 (.16)
0.906 (0.44)
1.74 (0.18)
0.911 (0.52)
1.77 (0.23)
DtACI 0.901 (0:08)
1.73 (0.16)
Case 3
Proposed 0.890 (0.02) 1.71 (0.19)
0.889 (0.23)
1.72 (0.25)
0.875 (1.04)
1.77 (0.94)
0.852 (1.86)
1.75 (1.62)
DPCP 0.900 (0.42) 1.74 (0.19) 0.901 (0.42) 1.75 (0.19) 0.905 (0.45)
1.78 (0.22)
0.910 (0.54)
1.81 (0.32)
DIACI
0.900 (0.08) 1.75 (0.19)
Case
Proposed 0.890 (0.02) 1.92 (0.17)
0.889 (0.23)
1.92 (0.22)
0.875 (0.97)
1.92 (0.60)
0.855 (1.95) 1.89 (1.13)
DPCP 0,901 (0.43)
1.95 (0.18) 0.903 (0.49) 1.96 (0.19) 0,906 (0.48) 1.98 (0.23) 0.912 (0.61) 2.01 (0.32)
DIACI
0.901 (0.08) 1.96 (0.16)
maintain coverage around 0.9 throughout. In contrast, when 01 = 0.9, the smaller initial sets result in lower initial coverage. For the proposed method, coverage fluctuates around 1 a. with slightly larger fluctuations under smaller e values. For long-run coverage, smaller values initially result in lower coverage and set size due the added noise from randomized responses. Nevertheless, all methods eventually converge to the nominal coverage level. Given the data configuration, where
the coefficient vectors 2(0) and ((()) initially move closer together and then diverge, the set size first increases and then decreases.
Figures 8 and present the results for Case 2 and Case 3, respectively. In terms of instant coverage and long-run coverage, the patterns across Cases 1, 2, and 3 are generally consistent. Regarding set size and long-run set size, the trend in Case 2 is similar to that in Case 1, with set size initially increasing and then decreasing due to class overlap during the drift process. In contrast, Case exhibits a consistently decreasing trend in set size, gradually stabilizing over time the class distributions remain more separable, allowing the prediction sets to contract and stabilize. Figure [0 shows the results for Case 4. Under the No Drift scenario, compared with Case 1, the set sizes of all three methods decrease and their coverage remains stable overall, which is as expected. As summarized in Table the results
similar to those in the regression setting: DPCP achieves higher coverage at the cost of larger set sizes. However, we emphasize that DPCP is an offline method and cannot be deployed in an online environment.
B.3 Elec2
For the purpose of evaluating the proposed method, we utilize the Elec2 dataset, which provides comprehensive record of electricity demand New South Wales, Australia [Harries et al.) 1999]. J. The dataset, compiled by the University of New South Wales, is well-suited for forecasting applications and has been widely employed in prior studies for time-serics prediction tasks. We employ AR(3) to serve as the base forecasting model and aim to construct confidence intervals for the electricity demand. Rolling coverage refers to the short-term coverage calculation over a sliding window of recent data points, capturing immediate fluctuations and reflecting the model's localized response to data variability. In contrast, long-run coverage accumulates coverage over the entire data stream, providing comprehensive view of overall performance stability.
As shown in Figure II rolling coverage and long-run coverage are generally stable, with coverage oscillating around the target level of 1 - a and no noticeable drops. In the proposed method, higher privacy protection (e = 1) results in slightly increased fluctuations in rolling coverage, while the long-run coverage is initially lower but quickly converges to match other settings.
24

---

Instant Coverage Set Size
Long-run Coverage Set Size
1.0
0.9
Coverase
0.8
0.7
0.6
0.5
Case 1
0.4
2.1
Size
1.8
1.5
1.2
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Time
Time
DtACI(a; = 0.1)
DtACI(; 0.9)
Proposed(Non-prrivae)) Proposed(e = 0.5)
Proposed(:=3)
Proposed(e=
Figure 7: Simulation results for classification in Case comparing different methods in terms of instant coverage, instant set size, long-run coverage, and long-run set size. Results are averaged over 200 runs; the first 200 points are excluded.
Instant Coverage Set Size
Long-run Coverage Set Size
1.0
0.9
Goveraa
0.8
0.7
0.6
0.5
Case 2
0.4
1.8
Size
1.5
1.2
0.9
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Time
Time
DtACI(a; = 0.1)
DtACI(a; 0.9)
Proposed(Non--private) Proposed(e = 0.5)
Proposed(:= =3
Proposed(e=1]
Figure 8: Simulation results for classification in Case 2, comparing different methods in terms of instant coverage, instant set size, long-run coverage, and long-run set size. Results are averaged over 200 runs; the first 200 points are excluded.
Regarding width, all methods exhibit fluctuations, capturing inherent data variability. Long-run width, however, remains relatively stable, gradually decreasing over time, suggesting that the algorithm becomes more stable accumulates more calibration data.
B.4 Comparison of PTMs and Non-Private Models
In this section, we investigate the impact of model privatization on interval width and coverage by comparing privately trained models and non-private models under Case A; see Figure [2] While long-run coverage remains unaffected, privately trained models typically exhibit lower predictive accuracy than non-private models, leading to higher non-conformity scores S, and consequently wider prediction intervals.
25

---

Instant Coverage Set Size
Long-run Coverage Set Size
1.0
0.9
Coverase
0.8
0.7
0.6
0.5
Size Case 3
0.4
2.0
1.8
1.6
1.4
1.2
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Time
Time
DtACI(a; = 0.1)
DtACI(;; =099)
Proposed(Non-prrivae)) Proposed(e = 0.5)
Proposed(:=
Proposed(:=
Figure 9: Simulation results for classification in Case comparing different methods in terms of instant coverage, instant set size, long-run coverage, and long-run set size. Results are averaged over 200 runs; the first 200 points are excluded.
Instant Coverage Set Size
Long-run Coverage Set Size
0.9
0.8
0.7
0.6
Case 4
0.4
2.0
1.8
1.4
1.2
1.0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Time
Time
DEACI(;; 0.1)
DIACK(a,=099)
Provist
Proposed(E 3)
Proposed(c-
Proposed(c
Figure 10: Simulation results for classification Case 4, comparing different methods terms of instant coverage, instant set size, long-run coverage, and long-run set size. Results are averaged over 200 runs; the first 200 points are excluded.
B.5 Simulation of privacy allocation under parallel composition
We further investigate the impact of varying privacy budgets. The results in Figure 13 obtained under Case A, are consistent with the theoretical guarantees established in Theorems 3.3 and 3.4 Specifically, we observe that the performance under randomly drawn
[0.5,3] is similar to that under the fixed value 3. This expected because the theoretical privacy bound depends on max, E,, which, in the random case, is very likely to be close to the upper bound of 3.
26

---

Rolling Coverage Width
Long-run Coverage Width
1.0
0.9
Coverage
0.7
0.6
0.5
Elec2
0.4
0.12
0.10
Set Size
0.06
10000
20000
30000
40000
10000
20000
30000
40000
Time
Time
DEACI(a - 0.1)
DEACI(a 0.9)
Proposed(Non--priatte) Proposed(c-1)
Proposed(: -
Proposed(c 2)
Figure 11: Results for the Elec2 dataset, comparing different methods in terms of rolling cover- age/width and long-run coverage/width. The rolling metrics are computed using a sliding window of size 200, and the first 200 data points are excluded.
Instant Coverage Width
Long-run Coverage Width
0.9
0.8
Coverage
0.6
0.5
Interval Length
20
0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Time
Time
Non-private PTM, Non-private
Proposedic 2)
Proposed(:
Proposed[PTM, =
Proposed(PTM c=
Comparison of instant coverage, instant interval width, long-run coverage, and long-run width between privately-trained models (PTMs) and non-private models in Case A. The results averaged over 200 runs. The first 200 data points are excluded to mitigate initialization effects.
Figure 12:
C Proof
C.1 Proof of Corollary 3.1
The stated regret bound is derived by applying the Krichevsky Drochevsk-TTroimmo (KT) potential within the coin betting framework. In our setting, the LRBR mechanism produces privatized feedback signals coin betting framework
Se that are uniformly bounded magnitude, i.e., [9al < 1. Crucially, does not require the feedback signals to be exact subgradients; it only necessitates boundedness. Therefore, the general regret bound established in Orabona and Pal (016) remains applicable, and directly implies the result stated in Corollary 3.1
27

---

Instant Coverage Width
Long-run Coverage Width
0.9
Coverage
0.8
0.5
0.5
Interval Length
10
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
Time
Time
Proposedic 3)
Propesed(::(0o...3].
Proposed(: 0.5)
Proposed(PTM, c=
Proposed(PTM, (U.5 31)
Proposed(PTM, c=0.3)
Simulation results in Case A, illustrating the impact of varying privacy budgets (6z) under both private and non-private settings. The four panels compare instant coverage, instant width, long-run coverage, and long-run width, demonstrating how privacy parameters affect the predictive intervals over time. These results provide empirical support for the theoretical guarantees stated in Theorems 3.3 and3.4
Figure 13:
C.2 Proof of Theorem 3.2
Algorithm I inneestiates the relationship between the inquiry value and the user's binary response,
controlled by the response rate r. Let the true label defined T(q > 5) E {0, 1}. where the non-conformity score. Due to local randomization, the output does not necessarily match the ground truth. The conditional probability of outputting "I" given that the truth is "1"
1 ++
Pr(Output
Truth
2
which occurs either when the user responds deterministically with 1 (with probability r), or when the individual is randomized (u = 0) and v = 1 (with probability (1 r)) Similarly, the probability of outputting "I" given that the truth is "0" is
Pr[Output Truth = 0]
2
which corresponds to the randomized case where u and v
This yields the following likelihood ratio:
Pr Pr(Output Truth =
(1+ 1
Pr Output Truth 0]
(1 - -r)/2 1-
and symmetrically,
Pr[Output Truth = 0] 1+
Pr[Output Truth = -1]
We have completed the proof of this theorem.
C.3 Proof of Theorem 3.
At the first iteration, Algorithm 2 is inquired via Algorithm T [using response rate 71, which induces an (c1. 0) local randomizer. By the post-processing property in Lemma [.33 the output of the first iteration in Algorithm remainss (e1, 0)-LP. At second iteration, the algorithm takes as input the privatized outputs from the first iteration, along with new response obtained using rate r2, which corresponds to an (F2, O)llocal randomizer. Since the responses originate from disjoint individuals and each individual is inquired only once, the parallel composition in Lemma 2.3 ensures that the
28

---

second iteration satisfies (maxfe1, <2). O)-LDP. Using the same argument repeatedly, we conclude that after iterations, the entire Algorithm (max Ej, O)-LDP, as each iteration involves a disjoint individual and only post-processed privatized outputs are used. We have completed the proof of this theorem.
C.4 Proof of Theorem
Notice that the first iteration is required to train predictive model that satisfies (#1. d1)-LDP and is simultaneously inquired using Algorithm|| [ with response rate r1, inducing an (c1 0)-loaal randomizer. By the post-processing property and sequential composition stated in Lemma 2.3 the output of the first iteration Algorithm preserves (c1 +1. (151511)-1a d1)-LDP. Using the same arguments Theorem 3.3 after / iterations, the entire procedure remains (maxigjşe($) +e)), maxisss 6 via post-pree processocss,ng sequential composition, and parallel composition in Lemma 2.3 The proof of this theorem is completed.
the proof of
C.5 Proof of Theorem 3.5
To simplify the notation, we define the constant c as
c= c=) +
-r).
(5)
Step The feedback term di is defined as
1 1 L =1 cc
9t. =
if L = 0
The LRBR mechanism generates L via the sampling steps u ~ Bernoulli(r) and v ~ (em5 Thus, the probabilities for L 1 and L 0 are given by
P(L 1) I(q 5e} (1 r) 0.5,
P(L =) 0) = 1 PPL 1).
The expectation of the feedback term is [g = PPL +)+ (-c)- = 0) which expands to El9.] r 1lq > St} + 0.5(1 r) Substituting the definition of from the expression
simplifies to
E [gg
(I St} a))
The cumulative sum of expectations over T steps is therefore Σt E[gd] Σn r (1(4: > Sr} - (1 a)) Rewriting the above using the coverage indicator L(Y; E Ce = l(g: > St). we obtain
T
T
Σ Eigd = Σ (Ixx (
Since >> is constant, our objective reduces proving
Σ fx e Ct - (1 a)
lim T-x00
0,
which is equivalent to establishing
T
lim T-+00
Elge] 0.
Step 2.
We assume that the nonconformity scores satisfy S, E [0, D) for all t = 1,2.3.... (a).
Suppose that for some t 2 1, the predicted radius q: exceeds the upper bound D, i.e. gr D. Given that de = Å Wr-1 and the wealth is nonnegative (W,-1
0), it follows that x 0.
The probability that = is 0.5(1 + r) > 0.5. When L = 1, we have 9r = -11-33 which implies W, W1-111 Xege) < W and d4+1 #+1 2+1 9t At. Consequently,
at+1 W, < g. indicating reduction in the predicted radius. The mechanism introduces
29

---

persistent downward tendeney when > D, and the radius eventually returns to the admissible range. This prevents unbounded growth.
(b). Suppose that for some f 2 1, we have gi 2 0 but 4+1 < 0. This implies that there must exist
some & such that 4++ > 0. Indeed, since at 0, it follows that d 2 0, while a++1 < 0 implies
Ae+1 < 0. Hence,
1
0> A411
[+1 d 1+1
which gives 9r > Given that St+1 0, the probability that 0 0.5(1++)) > 0.5, and when L = O, we have G++1 - < 0. Consequently,
++1
t d
2 + At+1 ++2 9t+1 2
(9) + 9(+1).
++2 ++2
When a < 0.5, we have 91 Ut-1 =1 2c < O. which implies X 0. Therefore, there exists
some k 2 2 such that λc+* > 0, and hence q+** > This shows that temporary excursions into the negative region corrected by the update rule, ensuring that the radius remains nonnegative in the long run. Next, consider the update rule:
Σ Di=1 98
9++1
9:9:
1+1
EE Di
t-1
1-1 1
Σ 9r t+ 1
9t
9ilk
gilb
+ g:qt
t+1
t t+1
1=1
1-1
t
9:9 + 9.9t Σ
Qt
9t + 9t
9i
t +
1
++1
so the increment is
1
1++
Qr 9t +
9:9 + 9r
91
++1
According to Orabona and Pal 2016
Podkopaev et al.
2024], we have the bound
DI
U:gi
$
Σ
S DL 11
1=1
1=1
so the absolute increment satisfies:
1
1 2e1 < t+
(D
(D
1( DI) < 2D +1.
Combining this with 9ı = 0 E [0, DJ and the analysis in (a) and (b), we conclude that [9:| S 3D + 1, ie., the update sequence is uniformly bounded.
Step 3. We begin by asserting the following statement:
Σ - as T + co.
(6)
We proceed by contradiction. Suppose the above does not hold. That is, there exists constant 0
such that
T'
VT, 37 T
gb
Ze.
According to the KT framework, the update of g++1 depends on the cumulative feedback up to time 6,
[c+1| = |de+1 We|
91
We.
1
30

---

we have already shown the For some index T", we can lower bound the update as
T"
T's T +
|gT++1|
gi
WT 2
Wr.
T +
We now invoke the KT framework's lower bound on the wealth process W Orabona and Pal 2016
(
(1(12)
W. 2
1
exp
( Σ 91
KVi
4
Substituting into the previous inequality yields
T 4T 2 T +1 KVT
T
4 =
exp
This implies that for any T, there exists T > such that the above inequality holds. Since the exponential term exp T's² grows exponentially T" oc, it follows that the sequence |9T becomes unbounded T 20. This contradicts the assumption that |gT is bounded. Thus, the initial assumption false, and the convergence stated is established.
Step 4. We now prove that
T
1
Σ
[g]]
T
T-000
t=1
by invoking the Dominated Convergence Theorem (DCT). From result
6
Ar
9t
0.
T-000
By construction, 9. (1- (1-c,-0 -c). hence
ldel s M = max [ cl. |c] 1
|Ar| 1
V7 1. 1.
Choose the constant random variable Y = 1. Since E[ xc, and gives the domination |Ar| $ Y. Combining (6) and 7 with DCT yields
lim E[Ar] E lim Ar] [[0] 0.
Since the sum in Ar is finite, expectation and summation commute:E[Ar] = ΣT E[go). It then follows that
Bigd
+ 0, as T + co.
[=1
Since the absolute value is applied to the cumulative sum rather than each individual term, we obtain
T
1
E[gd]
+ 0, as T + 20.
T
Thus, the convergence of the expected feedback sequence establishes the desired convergence of the coverage error as
T
lim T-+00
Σ I
e - (1- a) =
T
This completes the proof.
31

---

D Conversion table
Table 4: Conversion table between and
0.00
0.5
1.10
0.05
0.10
0.55
1.24
0.1
0.20
0.6
1.39
0.15
0.30
0.65
1.55
0.2
0,40
0.7
1.73
0.25
0.51
0.75
1.95
0.3
0.62
0.8
2.20
0.35
0.73
0.85
2.51
0,4
0.85
0.9
2.94
0.45
0.97
0.95
3.66
32


Reviews:
[{"review_id": "8I6mUqsHXA", "reviewer": "Reviewer_nEbK", "summary": "The paper studies the problem of local-DP (LDP) streaming bit information for conformal prediction (getting value within an interval with % probability guarantees). The paper:\n- propose the new algorithm using the known coin betting technique + randomized coin (for DP)\n- show the regret and experiments for this new algorithm", "questions": "1. DPCP is offline / central DP method. Will this be an apple-to-apple comparison? I feel a setting where distribution is not shifted (i.e. learning the confidence quickly) should be added because it's offline? \n2. In the baseline for non-private you used DtACI. Can you explain why not Podkopaev et al?\n3. Can you comment how your paper compares to Penso et al. 2025 – “Privacy-Preserving Conformal Prediction under Local DP.” and Zhang et al. 2025 – “Online Differentially Private Conformal Prediction for Uncertainty Quantification.” ?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "(+) new settings of online (one-pass) + local DP + one-bit\n(+) complete theory\n(+) many datasets tried\n(-) Analysis is mostly off-the-shelf: applying the same known technique to a slightly different algorithm. The novelty is more on settings it applies to rather than advancing any theory or new ideas to work elsewhere.\n(-) Unclear / possibly missing comparison in experiment results I want to ask, see below.", "was_revised": true, "final_justification": "Overall I see slight weakening of acceptance due to worse performance with distribution doesn't shift, as I suspected. However, there are still theoretical and ideation contributions that I think the paper can still be accepted.\n\nThe comment on multi dimensional by Reviewer yJev is also not a big concern to me.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Novelty, Originality, and Theoretical Contributions.** Classical online CP methods (e.g., Gibbs & Candès, 2021; Angelopoulos et al., 2023; Gibbs & Candès, 2024; Podkopaev et al., 2024) rely on true label feedback to adjust prediction intervals via pinball loss minimization: $q_{t+1} = q_t - \\eta_t \\cdot g_t,$ where $g_t \\in \\partial \\ell_{1-\\alpha}(q_t, S_t)$ is a subgradient of the loss.\n                    \n  - The subgradient is given by:\n\n    - If $q_t \\ne S_t$, then\n      $$\\partial \\ell_{1-\\alpha}(q_t, S_t) = \\mathbb{I}\\\\{S_t \\leq q_t\\\\} - (1 - \\alpha)$$\n    - If $q_t = S_t$, then\n      $$\\partial \\ell_{1-\\alpha}(q_t, S_t) \\in [\\alpha - 1, \\alpha]$$\n\n  - In contrast, we propose a novel approach that replaces true feedback with randomized response, enabling privacy-preserving one-bit feedback without revealing true inclusion status—an idea not explored in prior online CP work. Our privacy-aware update mimics subgradient behavior:\n\n    - If $L = 1$, \n      $$ g_t = 1 - \\left( r (1 - \\alpha) + 0.5 (1 - r) \\right). $$  \n    - Otherwise,  \n      $$ g_t = - \\left( r (1 - \\alpha) + 0.5 (1 - r) \\right). $$\n\n  - This update ensures convergence to the target quantile while preserving user privacy. While inspired by coin-betting methods, our consideration randomized response mechanism is novel, offering a simple, efficient, and privacy-compliant CP solution.\n  - Additionally, we make several theoretical contributions for privacy-preserving online CP:\n     - Our method inherits regret guarantees from the coin-betting framework using a privacy-aware update rule $g_t \\in [-1, 1]$, enabled by binary randomized response. However, achieving these guarantees is not trivial: additive-noise methods (e.g., Zhang et al., 2025) cannot ensure similar guarantees.\n     - We establish formal LDP guarantees in the fully online setting.\n     - The update rule satisfies: $\\mathbb{E}[g_t] = r \\cdot (\\mathbb{I}\\\\{ S_t \\le q_t \\\\} - (1 - \\alpha)),$ which mirrors the subgradient of the pinball loss. This structure allows us to prove asymptotic coverage guarantees despite the presence of privacy noise.\n\n  - Thus, our contribution lies not only in adapting existing frameworks, but also in designing a new privacy-aware online CP algorithm for both classification and regression, with formal privacy and coverage guarantees.\n\n- **Clarification on the Comparison in Experiment Results.** We agree that DPCP (Angelopoulos et al., 2022) is an offline, central DP method and not tailored for streaming scenarios. However, we included it as a baseline to benchmark our method against existing privacy-preserving conformal predictors.\n\n   - Our experiments already span six simulation settings (with varying drift levels in both regression and classification) and two real-world datasets, providing broad evaluation under realistic online conditions.\n\n   - To address the suggestion of including a stationary setting, we conducted an additional experiment with a fixed coefficient vector ($\\beta = (1, 2, 1, 0, 0)$) and no drift. Results are shown below. As expected, DPCP achieves slightly higher coverage and wider intervals. These results confirm that our method remains competitive even in stationary, offline-like settings.\n\n**Table: Proposed vs DPCP. Std values in parentheses (coverage std ×10⁻², width std ×10⁻¹)**\n\n|   | $\\epsilon=3$ | $\\epsilon=3$   | $\\epsilon=1$ | $\\epsilon=1$         | $\\epsilon=0.5$  | $\\epsilon=0.5$    |\n|----------|------------------------|---------------|------------------------|---------------|--------------------------|---------------|\n| Method   |  Coverage | Width | Coverage | Width  |  Coverage | Width   |\n| Proposed | 0.889 (0.3)           | 3.09 (0.4)         | 0.875 (1.0)            | 3.04 (1.0)         | 0.852 (1.9)              | 2.93 (1.8)           |\n| DPCP     | 0.904 (0.5)           | 3.33 (0.4)         | 0.911 (0.6)            | 3.40 (0.6)         | 0.922 (1.0)              | 3.53 (1.2)           |\n\n\n- **Clarification on Not Using Podkopaev et al. [2024] as Non-private Baseline** \n   - We chose DtACI as the non-private baseline because it is a well-established, widely cited method (published in JMLR, cited over 120 times), known for its stability, practicality, and reproducibility, making it a strong benchmark.\n\n   - We also carefully considered the connection to Podkopaev et al. [2024]. In fact, as explicitly noted in lines 161–164 of our paper: \n\n      > “Notably, in the special case where $r = 1$, the mechanism reduces to the non-DP setting, and the update $g_t$ degenerates to the standard subgradient $\\partial \\ell_{1-\\alpha}(q_t, S_t)$, recovering the standard deterministic subgradient update without any privacy protection [Podkopaev et al., 2024].”\n\n   - Thus, the “non-private” curve in our experiments effectively coincides with the update structure proposed in Podkopaev et al. [2024], as it corresponds to the same subgradient-driven quantile estimation procedure under $r = 1$, i.e., without privatization. We will clarify this connection in the experimental section to avoid confusion and to highlight that our private method remains competitive even under local DP constraints.\n\n- **Comparison to Penso et al. (2025)**\n\n  - Penso et al. (2025) proposed two LDP-based CP methods: one perturbs labels using $k$-ary randomized response, and the other uses privatized conformity scores via binary indicators—both offering finite-sample coverage without accessing true labels.\n\n  - While valuable, their framework is offline, requiring a fixed calibration set and disjoint batches across multiple rounds (Algorithms 1–3). In contrast, our method is fully online, operating in a streaming setting with single-pass, $O(1)$ memory updates (Algorithm 2), making it highly efficient and scalable.\n\n  - Moreover, their approach is tailored to classification and depends on the number of labels $k$, while our method is task-agnostic, supporting both classification and regression without dependence on label cardinality.\n\n- **Comparison to Zhang et al. (2025)**\n\n  - Zhang et al. (2025) proposed an online differentially private conformal prediction (ODPCP) method using additive noise (e.g., Laplace or Gaussian) with a fixed truncation constant $c$ to ensure update stability. While effective, their approach requires careful sensitivity tuning and additional hyperparameters, complicating practical deployment.\n\n  - In contrast, our method employs randomized response to achieve LDP with only a single privacy parameter $\\epsilon$, eliminating the need for extra tuning. It integrates naturally into the coin-betting framework, preserving theoretical guarantees such as bounded regret.\n\n  - Moreover, randomized response mechanisms make more efficient use of the privacy budget than additive-noise approaches, which may lead to excessive noise and degraded utility under strong privacy (Balle et al., 2018; Liu et al., 2022).\n\n  - We have conducted additional simulation studies and present a direct comparison between our method and ODPCP under various privacy levels in the following table.\n\n     - As shown, our method outperforms ODPCP under strong privacy ($\\epsilon = 0.5$), offering tighter and more stable intervals. This aligns with Figure 15 in Zhang et al. (2025), which highlights ODPCP’s instability at low privacy budgets.\n\n    - In summary, we view our method as a simplification and refinement of Zhang et al. (2025), offering a more elegant, hyperparameter-free, and empirically robust framework for private online conformal prediction.\n\n   **Table: Coverages and widths for the proposed method and ODPCP**  \n    *Std values in parentheses (coverage std ×10⁻², width std ×10⁻¹).*\n\n|  |   | $\\epsilon=3$ | $\\epsilon=3$   | $\\epsilon=1$ | $\\epsilon=1$         | $\\epsilon=0.5$  | $\\epsilon=0.5$    |\n|------|----------|------------------------|---------------|------------------------|---------------|--------------------------|---------------|\n| Case | Method   |  Coverage | Width | Coverage | Width  |  Coverage | Width   |\n| A    | Proposed | 0.889 (0.2)            | 3.25 (0.4)    | 0.875 (1.0)            | 3.16 (1.1)    | 0.853 (2.0)              | 3.11 (2.5)    |\n| A    | ODPCP    | 0.888 (0.5)            | 3.26 (0.6)    | 0.868 (1.4)            | 3.94 (10.0)   | 0.864 (2.6)              | 7.42 (54.0)   |\n| B    | Proposed | 0.889 (0.3)            | 4.16 (1.2)    | 0.874 (0.9)            | 3.94 (2.5)    | 0.851 (1.8)              | 3.60 (4.3)    |\n| B    | ODPCP    | 0.888 (0.5)            | 4.20 (1.6)    | 0.869 (1.3)            | 4.72 (11.0)   | 0.865 (2.4)              | 8.59 (54.0)   |\n| C    | Proposed | 0.889 (0.3)            | 3.10 (0.4)    | 0.875 (1.1)            | 3.04 (1.0)    | 0.852 (1.9)              | 2.95 (1.8)    |\n| C    | ODPCP    | 0.888 (0.5)            | 3.13 (0.6)    | 0.869 (1.4)            | 3.61 (23.0)   | 0.867 (2.7)              | 6.65 (30.0)   |\n\n**References**\n\nAngelopoulos et al. (2022). *Private prediction sets*. _Harvard Data Sci. Rev._, 4(2).\n\nAngelopoulos et al. (2023). *Conformal PID control for time series prediction*. _NeurIPS_, 23047–23074.\n\nBalle et al. (2018). *Privacy amplification by subsampling: Tight analyses via couplings and divergences*. _NeurIPS_.\n\nGibbs & Candès (2021). *Adaptive conformal inference under distribution shift*. _NeurIPS_ , 1660–1672.\n\nGibbs & Candès (2024). *Conformal inference for online prediction with arbitrary distribution shifts*. _JMLR_, 25(162):1–36.\n\nLiu et al. (2022). *Identification, amplification and measurement: A bridge to Gaussian differential privacy*. _NeurIPS_ , 11410–11422.\n\nOrabona & Pál (2016). *Coin betting and parameter-free online learning*. _NeurIPS_ .\n\nPodkopaev et al. (2024). *Adaptive conformal inference by betting*. arXiv preprint arXiv:2412.19318."}, {"review_id": "5X9CaWjkHJ", "reviewer": "Reviewer_RLiw", "summary": "This paper introduces an online conformal prediction (CP) method that produces locally differentially private quantiles. Based on randomized binary inquiries, the method is computationally efficient and enables to dynamically construct distribution-free prediction sets that maintain privacy. Furthermore, the authors demonstrate that the long-run empirical coverage (eq. 1) converges to a pre-specified nominal level $1−\\alpha$ and that the cumulative regret is controlled (Corollary 3.1). Finally, on several experiments, they illustrate the efficiency of their method.", "questions": "1\\ In Algorithm 2, the value of $r_t$​ depends on time. What is a practical application where we would want to modify the degree of privacy over time?\n    \n2\\ What is the purpose of Section 4, \"Extension to Classification Tasks\"? It seems to be just a modification of the score function.\n\n3\\ In the experiments, Table 1 shows that coverages of the sets returned by the proposed method are lower than 0.9, even if the number of points is huge (10,000). Is there an explanation for this?\n\n4\\ Furthermore, in Table 1, we see that when $\\epsilon$ increases, the coverage decreases for the proposed method, which is the opposite of what is observed for DPCP and seems more natural. Can you elaborate on this?\n\n5\\ Do you think it could be possible to see the impact of the privacy in the regret bound in Corollary 3.1?\n\n6\\ (Minor) When there is no privacy, is DPCP exactly equal to the standard split method?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1\\ The paper is very well-written and easy to follow.  Furthermore, the problem is well-motivated.\n\n2\\ The method is well-explained, clever, and simple in a positive manner.\n\n3\\ The subject is of particular interest to the CP community.\n\n###  Weaknesses\n\nOverall, to me, there are not many drawbacks to this paper. However, here are a few:\n\n1\\ The bound on the regret in Corollary 3.1 does not depend on $r_t$ (the privacy).\n\n2\\ The tables in the experiments do not include standard deviations.\n    \n3\\ In line 271, it is stated that \"The proposed method achieves slightly lower but comparable coverage to DPCP, while producing substantially narrower intervals.\" This is an interesting remark, but to properly compare the sets, they should be compared when they have the same size or coverage.\n    \n4\\ There is no \"Conclusion and Limitations\" section.\n\nTypos: Line 98: \"of of\"", "was_revised": true, "final_justification": "In my opinion, this is a good article. After the rebuttal I keep my score.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn. \n\n- **Standard deviations in the experiment.**  We have added a table reporting the standard deviations of coverage and prediction interval width, which will be included in the revised version.\n> **Table: Standard deviations of coverage (×10⁻²) and prediction interval width (×10⁻¹).**\n\n|       |         | no-privacy | no-privacy |   ε = 3   |  ε = 3    |   ε = 1   |  ε = 1    | ε = 0.5  |  ε = 0.5   |\n|-------|---------|------------|------------|-----------|-----------|-----------|-----------|----------|-----------|\n| Case  | Method  | Coverage   | Width      | Coverage  | Width     | Coverage  | Width     | Coverage | Width     |\n| A     | Proposed| 0.890 (0.03) | 3.25 (0.3) | 0.889 (0.2) | 3.25 (0.4) | 0.875 (1.0) | 3.16 (1.1) | 0.853 (2.0) | 3.11 (2.5) |\n|       | DPCP    | 0.900 (0.5)  | 8.30 (1.0) | 0.904 (0.5) | 8.41 (1.1) | 0.911 (0.6) | 8.61 (1.5) | 0.922 (0.9) | 8.95 (3.0) |\n|       | DtACI   | 0.897 (0.08) | 3.42 (0.3) | *         | *         | *         | *         | *        | *         |\n| B     | Proposed| 0.890 (0.04) | 4.18 (0.9) | 0.889 (0.3) | 4.16 (1.2) | 0.874 (0.9) | 3.94 (2.5) | 0.851 (1.8) | 3.60 (4.3) |\n|       | DPCP    | 0.899 (0.5)  | 8.99 (1.4) | 0.903 (0.5) | 9.12 (1.6) | 0.910 (0.6) | 9.37 (2.2) | 0.921 (0.9) | 9.81 (3.9) |\n|       | DtACI   | 0.899 (0.07) | 4.82 (1.0) | *         | *         | *         | *         | *        | *         |\n| C     | Proposed| 0.890 (0.03) | 3.10 (0.3) | 0.889 (0.3) | 3.10 (0.4) | 0.875 (1.1) | 3.04 (1.0) | 0.852 (1.9) | 2.95 (1.8) |\n|       | DPCP    | 0.900 (0.5)  | 4.43 (0.6) | 0.904 (0.5) | 4.50 (0.6) | 0.912 (0.6) | 4.61 (0.9) | 0.923 (0.9) | 4.81 (1.8) |\n|       | DtACI   | 0.899 (0.08) | 3.34 (0.3) | *         | *         | *         | *         | *        | *         |\n\n- **Comparisons with the same size or coverage.**\n  - In our experiments, all methods are evaluated under a fixed nominal level $ \\alpha = 0.1 $ to reflect real-world deployment scenarios.\n  - We agree that aligning empirical coverage offers a fairer comparison. Following your suggestion, we adjusted the $\\alpha$ for our method to match DPCP’s empirical coverage under each privacy level. The resulting interval widths are reported below.\n  - The results show that our method produces narrower intervals while matching the empirical coverage of DPCP.\n\n> **Table: Coverages and widths for the proposed method and DPCP (coverage-matched comparison, coverage Std × 10⁻², width Std × 10⁻¹).**\n|       |         |   ε = 3   |  ε = 3    |   ε = 1   |  ε = 1    | ε = 0.5  |  ε = 0.5   |\n|-------|---------|-----------|-----------|-----------|-----------|----------|-----------|\n| Case  | Method  | Coverage  | Width     | Coverage  | Width     | Coverage | Width     |\n| A     | Proposed | 0.904 (0.2) | 3.44 (0.4) | 0.911 (1.0) | 3.69 (1.9) | 0.922 (1.9) | 4.54 (13) |\n|      | DPCP     |  0.904 (0.5) | 8.41 (1.1) | 0.911 (0.6) | 8.61 (1.5) | 0.922 (0.9) | 8.95 (3.0) |\n| B     | Proposed |  0.903 (0.3) | 4.68 (1.4) | 0.910 (0.9) | 5.34 (4.5) | 0.921 (1.8) | 7.08 (18) |\n|      | DPCP     |  0.903 (0.5) | 9.12 (1.6) | 0.910 (0.6) | 9.37 (2.2) | 0.921 (0.9) | 9.81 (3.9) |\n| C     | Proposed |  0.904 (0.3) | 3.28 (0.4) | 0.912 (1.1) | 3.51 (1.6) | 0.923 (1.8) | 4.10 (6.4) |\n|      | DPCP     |  0.904 (0.5) | 4.50 (0.6) | 0.912 (0.6) | 4.61 (0.9) | 0.923 (0.9) | 4.81 (1.8) |\n\n- **Conclusion section.** In the revised version, we will include the following section including conclusions and limitations of this paper.\n   - This paper proposes a novel and practical framework for online conformal prediction under LDP. By combining randomized binary feedback with a coin-betting update scheme, the method enables one-pass, model-free prediction set construction with formal privacy guarantees. It supports both regression and classification, operates efficiently in streaming settings with constant memory. Despite its strengths, several limitations remain. First, Theorem 3.5 provides only asymptotic coverage guarantees; deriving non-asymptotic bounds under LDP is an important direction for future work. Second, we use standard nonconformity scores, which are broadly applicable but may yield conservative sets; exploring data-adaptive scores could improve efficiency. \n\n\n- **Clarification on $r_t$**. The mechanism is not inherently time-dependent; rather, each time step typically represents a new user in the online setting, with $r_t$ reflecting that user's individual privacy preference. In practice, users may differ in their desired level of privacy—privacy-conscious users may choose a smaller $r_t$, introducing more noise, while others may opt for a larger $r_t$ to allow more informative updates. This flexibility makes the algorithm suitable for real-world scenarios with heterogeneous privacy preferences.\n\n- **Purpose of Section 4**. While Section 4 changes the nonconformity score, this is not a mere technical detail—it illustrates the framework’s applicability to both regression and classification. Unlike contemporaneous work (e.g., Penso et al., 2025), which focuses solely on classification, our method is model- and task-agnostic, applicable to any setting with a scalar nonconformity score. Section 4 demonstrates how the same core algorithm (Algorithm 2) extends to classification with minimal adjustments, reinforcing our claim of task generality and supporting clarity and reproducibility.\n\n\n- **Coverages are lower than 0.9**. This behavior is consistent with prior findings. Podkopaev et al. (2024) reported similar long-run coverage (~88\\%) for their coin-betting conformal predictor even without privacy, and considered the small gap a minor practical issue. In our case, stronger privacy (i.e., smaller $\\epsilon$) introduces more randomness via randomized response, which weakens the update signal and slows convergence—especially in early rounds—leading to temporary undercoverage in finite samples. Nonetheless, as shown in Figures 2, 3, and S.6, coverage steadily improves with more data and approaches the nominal 90\\%, confirming asymptotic consistency. Even under strong privacy (e.g., $\\epsilon = 0.5$), the method maintains ~85\\% coverage, demonstrating solid practical performance.\n\n- **Why does our coverage drop as $ \\epsilon $ decreases (opposite DPCP, more intuitive)**. This is an excellent comment.\n  - DPCP is an offline method that privatizes calibration scores using the exponential mechanism (Angelopoulos et al., 2022). Specifically, their Equation (3):\n  $$\n\\tilde{q} = \\frac{(n+1)(1-\\alpha)}{n(1-\\gamma\\alpha)} + \\frac{2}{\\epsilon n}\\log\\left(\\frac{m}{\\gamma\\alpha}\\right)\n $$\n    shows that the privatized quantile $\\tilde{q}$ increases as $\\epsilon$ decreases. This inflates prediction thresholds, yielding wider, more conservative sets to preserve coverage—explaining DPCP's increasing coverage under stronger privacy.\n\n  - In contrast, our fully online method uses privatized binary feedback to update the quantile estimate. Lower $\\epsilon$ reduces the response rate (e.g., $\\epsilon = 0.5$ when  $r = 0.25$), increasing noise and slowing learning. This leads to slight undercoverage early on, but Figures 2 and 3 show that coverage stabilizes over time, especially after initial rounds—common in streaming scenarios.\n\n  - In summary, the coverage gap reflects early-stage randomness under privacy constraints and does not undermine the method’s strong long-term performance.\n\n- **Regret bound with respect to $r_t$ in Corollary 3.1**\n  - The regret bound in Corollary 3.1 is directly derived from the coin-betting framework of Orabona & Pál (2016) (see Page 7, Corollary 5), which guarantees bounded regret as long as the feedback signal $g_t \\in [-1, 1]$ remains bounded.\n\n   - From a theoretical standpoint, the influence of the privacy parameter $r$ is absorbed into the worst-case analysis inherent to coin-betting. To explicitly reflect the effect of $r$ in the regret bound would require substantial modifications to the original analysis (see Appendix F, Pages 19–22), which is nontrivial and beyond the current scope. Nevertheless, we agree that this is an interesting direction for future theoretical work.\n\n- **When there is no privacy, is DPCP exactly equal to the standard split method?**. You are right.  As the privacy budget $\\epsilon \\to \\infty$ and $\\gamma \\to 0$, the privatized quantile $\\tilde{q}$ in Equation (3) of Angelopoulos et al. (2022) converges to the standard split conformal quantile. This is explicitly noted in their paper, confirming that DPCP reduces to the standard split conformal method when privacy constraints are removed. Since DPCP builds on the split method with an added privacy mechanism, the two are equivalent in the non-private setting.\n\n- **Typos and Formatting**. We will correct the typo in Line 98 (“of of”) and perform a thorough pass over the manuscript to ensure all grammatical and formatting issues are addressed in the final version.\n\n**References**\n\nAngelopoulos, A., Bates, S., Zrnic, T., & Jordan, M. I. (2022). *Private prediction sets*. Harvard Data Science Review, 4(2).\n\nPodkopaev, A., Xu, D., & Lee, K. (2024). *Adaptive conformal inference by betting*. arXiv preprint arXiv:2412.19318.\n\nOrabona, F. and Pál, D. (2016). *Coin betting and parameter-free online learning*. In _Advances in Neural Information Processing Systems_, 29.\n\nPenso, C., Mahpud, B., Goldberger, J., and Sheffet, O. (2025). *Privacy-preserving conformal prediction under local differential privacy*. arXiv preprint arXiv:2505.15721."}, {"review_id": "yc9nJo8fbk", "reviewer": "Reviewer_yJev", "summary": "The authors introduce an online conformal prediction framework with local differential privacy in streaming data. Their method uses randomized binary queries and generates model-free prediction sets. The framework applies to regression and classification tasks with theoretical guarantees. Experimental validation on synthetic and real-world datasets confirms the method's accuracy.", "questions": "1. Does the framework apply only to one-dimensional problems? Equation 2 references gradients while quantiles operate in one dimension. Similarly, Algorithm 2 (line 10) describes a \"gradient update\" that appears to be a derivative update.\n\n2. How do alternative methods perform under local differential privacy constraints? What are their respective performance and utility trade-offs?\n\n3. What specific utility advantages does the proposed method offer over existing approaches?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper demonstrates good writing quality and presents an intriguing local online framework for privacy-preserving settings. However, the framework appears constrained to one-dimensional learning problems due to its reliance on quantiles $(q_t)$. \n\nThe evaluation would benefit from broader comparisons with existing methods beyond the binary inquiry approach. The theoretical contribution could be strengthened by more clearly articulating the specific theoretical challenges addressed and demonstrating why this solution outperforms alternatives. Given the one-dimensional nature of the problem, gradient descent may not be the most appropriate benchmark, comparison with Newton methods would be more relevant.", "was_revised": true, "final_justification": "The authors provide sufficient arguments in their answer, my initial concern is solved.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Does the framework apply only to one-dimensional problems**. This is an excellent comment.\n   - Our current framework is indeed tailored for one-dimensional output tasks (e.g., scalar regression or classification), where the quantile threshold $q_t$ directly defines prediction intervals or sets.\n\n    - The main contribution lies in developing a fully online, locally differentially private CP method that requires only a single-bit privatized feedback via randomized response. To our knowledge, the first such framework for one-pass conformal prediction with binary LDP feedback.\n\n   - While multivariate outputs were not our original focus, we consider a promising way to extend to multivariate outputs. Specifically, for multivariate responses $Y_t \\in \\mathbb{R}^p$, we define a scalar nonconformity score using an ellipsoidal projection:\n     $$ \\hat{e}(Y) = (Y - \\hat{f}(X_t) - \\bar{\\varepsilon})^T \\hat{\\Sigma}^{-1} (Y - \\hat{f}(X_t) - \\bar{\\varepsilon}),$$\n     where $\\hat{\\Sigma} $ is a low-rank approximation of the residual covariance matrix based on residuals\n    $ \\hat{\\varepsilon}_t = Y_t - \\hat{f}(X_t) \\in \\mathbb{R}^p.$ \n   This score can be used in our privacy-preserving framework to learn the privacy quantile $\\hat{Q}_t(1 - \\alpha)$, forming an ellipsoidal prediction region:\n\n     $$ \\hat{C}_{t-1}(X_t, \\alpha) = \\left\\\\{ Y : \\hat{e}(Y) \\leq \\hat{Q}_t(1 - \\alpha) \\right\\\\}. $$\n\n   - This extension is aligned with prior work (e.g. Xu et al., 2024 and Braun et al., 2025) who use Mahalanobis-type distances for multivariate conformity, demonstrating the flexibility of our framework beyond the univariate case.\n\n- **Comparison with Newton methods**\n\n   - Classic online cp methods (e.g., Angelopoulos et al., 2023; Podkopaev et al., 2024) often formulate quantile estimation as online optimization of the pinball loss:\n\n     $$\\ell\\_{1-\\alpha}(q, S_t) = (\\mathbb{I}\\\\{q \\geq S_t\\\\} - (1 - \\alpha))(q - S_t),$$\n     \n     which is convex but non-smooth and admits only subgradients.\n\n   - Our approach adopts a coin-betting strategy that is parameter-free, step size-free, and single-pass, making it well-suited for streaming and LDP settings. Unlike gradient-based methods, it does not rely on smoothness or differentiability.\n\n  - In contrast, Newton methods require twice-differentiable loss functions. Since the pinball loss is non-differentiable at $q = S_t$, Newton-style updates are inapplicable in this context.\n\n- **Clarification on Equation 2 and the \"gradient update\" in Algorithm 2**. We have revised the terminology for clarity and consistency with standard conventions in online convex optimization for non-smooth problems:\n  - In Algorithm 2 (line 10), we now refer to the update simply as an update, rather than a “gradient update.”\n  - In Equation (2), we clarify that the update is based on a subgradient of the pinball loss.\n  - The symbol has been corrected from $\\nabla \\ell_{1-\\alpha}$ to $\\partial \\ell_{1-\\alpha}$ to accurately reflect the use of a subgradient (not a gradient), given the non-differentiability of the pinball loss at $q = S_t$.\n\n- **Broader comparison and justification of the update mechanism**. Existing privacy-preserving CP methods are limited in number and mostly focus on the offline setting. We compare our method against two recent and representative approaches:\n   - Penso et al. (2025) proposed two offline methods: one perturbs labels via $k$-ary randomized response, the other perturbs conformity scores using binary randomized queries. Both achieve finite-sample coverage without ground-truth labels but require disjoint calibration batches and fixed datasets, limiting applicability in streaming settings. In contrast, our method supports fully online prediction with $O(1)$ memory and single-pass quantile updates. Moreover, our model-agnostic framework accommodates both regression and classification, unlike their classification-specific approach dependent on the label space size $k$.\n\n  - Zhang et al. (2025) introduced ODPCP, which adds noise to subgradients and applies truncation. This method requires hyperparameter tuning and sensitivity calibration. By contrast, our approach employs parameter-free binary randomized response (aside from $\\epsilon$), integrates seamlessly with coin betting, and enjoys bounded regret guarantees. Prior work (e.g., Balle et al., 2018; Liu et al., 2022) shows that randomized response more efficiently utilizes the privacy budget compared to additive noise.\n\n   - We also conduct simulation studies comparing our method with ODPCP across various privacy levels. As shown, our method yields tighter and more stable intervals than ODPCP, consistent with the instability reported in Zhang et al. (2025, Fig. 15) for low privacy budgets. \n\n**Table: Proposed method vs ODPCP**  \n(Std devs: coverage ×10⁻², width ×10⁻¹)\n|  |   | $\\epsilon=3$ | $\\epsilon=3$   | $\\epsilon=1$ | $\\epsilon=1$         | $\\epsilon=0.5$  | $\\epsilon=0.5$    |\n|------|----------|------------------------|---------------|------------------------|---------------|--------------------------|---------------|\n| Case | Method   |  Cov. | Width | Cov. | Width  |  Cov. | Width   |\n| A    | Proposed | 0.889 (0.2)            | 3.25 (0.4)    | 0.875 (1.0)            | 3.16 (1.1)    | 0.853 (2.0)              | 3.11 (2.5)    |\n|    | ODPCP    | 0.888 (0.5)            | 3.26 (0.6)    | 0.868 (1.4)            | 3.94 (10.0)   | 0.864 (2.6)              | 7.42 (54.0)   |\n| B    | Proposed | 0.889 (0.3)            | 4.16 (1.2)    | 0.874 (0.9)            | 3.94 (2.5)    | 0.851 (1.8)              | 3.60 (4.3)    |\n|     | ODPCP    | 0.888 (0.5)            | 4.20 (1.6)    | 0.869 (1.3)            | 4.72 (11.0)   | 0.865 (2.4)              | 8.59 (54.0)   |\n| C    | Proposed | 0.889 (0.3)            | 3.10 (0.4)    | 0.875 (1.1)            | 3.04 (1.0)    | 0.852 (1.9)              | 2.95 (1.8)    |\n|     | ODPCP    | 0.888 (0.5)            | 3.13 (0.6)    | 0.869 (1.4)            | 3.61 (23.0)   | 0.867 (2.7)              | 6.65 (30.0)   |\n\n- **Theoretical Contributions.** We highlight the following theoretical contributions:\n   - Our method inherits regret guarantees from the coin-betting framework by using a privacy-aware update rule $g_t \\in [-1,1]$, enabled by binary randomized response. In contrast, additive-noise methods (e.g., Zhang et al., 2025) cannot ensure bounded updates and thus lack similar guarantees.\n  - We establish formal LDP guarantees in the fully online setting, addressing a gap in the literature where most theoretical results focus on offline calibration.\n  - The update rule satisfies: $\\mathbb{E}[g_t] = r \\cdot (\\mathbb{I}\\\\{ S_t \\le q_t \\\\} - (1 - \\alpha)),$ which mirrors the subgradient of the pinball loss. This structure allows us to prove asymptotic coverage guarantees despite the presence of privacy noise.\n\n- **Utility trade-offs and coverage behavior.** Privacy constraints inherently affect coverage performance. In offline methods (e.g., Angelopoulos et al., 2022; Penso et al., 2025), stronger privacy (smaller $\\epsilon$) typically leads to over-coverage and wider intervals due to conservative calibration. For example, Theorem 2 in Angelopoulos et al. (2022) shows that:\n\n  $$ \\tilde{q} = \\frac{(n+1)(1-\\alpha)}{n(1-\\gamma \\alpha)} + \\frac{2}{\\epsilon n} \\log \\left( \\frac{m}{\\gamma \\alpha} \\right), $$\n\n  where the second term increases as $\\epsilon$ decreases, inflating $\\tilde{q}$ and widening the prediction interval.\n\n   In contrast, online methods (e.g., Zhang et al., 2025; ours) tend to exhibit under-coverage, especially in early rounds. This is because privacy noise, additive in ODPCP or randomized in our approach, dampens the update signal, slowing the convergence of quantile estimates.\n\n- **Advantages of the proposed method.** Our method offers several key advantages over existing LDP-based conformal prediction approaches:\n  - Efficiency: It supports single-pass updates with constant memory, unlike offline methods (e.g., Angelopoulos et al., 2022; Penso et al., 2025) that require fixed calibration sets and multiple passes, making it well-suited for streaming settings.\n\n  - Parameter-free: In contrast to additive-noise methods (e.g., Zhang et al., 2025) that require sensitivity tuning, our method only depends on the privacy budget $\\epsilon$, simplifying implementation and improving robustness.\n\n  - Empirical strength: As shown in Table 1 and Figure 2, our method achieves strong coverage with tighter intervals even under strong privacy $\\epsilon = 0.5$, balancing privacy and utility.\n\n  - Generality: Unlike classification-specific approaches (e.g., Penso et al., 2025), our framework is model-agnostic and applicable to both regression and classification tasks.\n\n**References**\n\nAngelopoulos et al., 2023. *Conformal PID control for time series prediction*. _NeurIPS_.\n\nAngelopoulos et al., 2022. *Private prediction sets*. _Harvard Data Science Review_.\n\nBalle et al., 2018. *Privacy amplification by subsampling: Tight analyses via couplings and divergences*. _NeurIPS_.\n\nBraun et al., 2025. *Multivariate conformal prediction via conformalized Gaussian scoring*. arXiv.\n\nLiu et al., 2022. *Identification, amplification and measurement: A bridge to Gaussian differential privacy*. _NeurIPS_.\n\nOrabona and Pál, 2016. *Coin betting and parameter-free online learning*. _NeurIPS_.\n\nPenso et al., 2025. *Privacy-preserving conformal prediction under local differential privacy*. arXiv.\n\nPodkopaev et al., 2024. *Adaptive conformal inference by betting*. arXiv.\n\nXu et al., 2024. *Conformal prediction for multi-dimensional time series by ellipsoidal sets*. arXiv.\n\nZhang et al., 2025. *Online differentially private conformal prediction for uncertainty quantification*. _ICML_."}, {"review_id": "aOzIXu9mF3", "reviewer": "Reviewer_Cdgt", "summary": "This paper propose an online conformal prediction procedure under local differential privacy. Theoretical guarantee and experiments results are provided to demonstrate the proformance of the proposed method.", "questions": "1. In line 151, interprete the statement about \"This  binary structure naturally aligns with 152 a local randomization mechanism, which is crucial for satisfying LDP constraints\".\n2. In line 175, why can $\\omega_t$ be interpreted as an estimate of the $(1 - \\alpha)$-quantile? Could you provide a more intuitive explanation of lines 9–11 in Algorithm 2?\n3. Is there a trade-off between privacy constraints and prediction coverage? Why does DtACI produce wider intervals compared to the proposed method and DPCP?\n4. Theorem 3.5 presents an asymptotic long-run coverage guarantee. Is it possible to provide a more explicit bound to better understand the convergence rate?\n5. Regarding the experimental results, the proposed method consistently exhibits undercoverage in Table 1 and Figure 2. How can this result be explained?\n\n------------------\n\nI have updated the score.", "limitations": "Yes, limitations are discussed in Appendix B.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper proposes an intuitive way to address the  challenge of privacy-preserving uncertainty quantification in online scenario. The problem is interesting, and the motivation is well-supported through relevant literature and illustrative examples.\n\nWeaknesses:\n- The intuitive idea behind Algorithm 2 could be illustrated more clearly.", "was_revised": true, "final_justification": "My questions have been satisfactorily addressed, and I have updated the score accordingly.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Clarification on the Intuition Behind Algorithm 2**\n\n   - Our algorithm can be viewed as a private and adaptive betting game against streaming data. Imagine a gambler estimating a target quantile (e.g., the 90th percentile) using only privatized yes/no feedback, without access to true values.\n\n  - Despite this uncertainty, the gambler adapts intelligently—tracking her \"wealth,\" betting on the quantile's location, and adjusting based on noisy signals. This builds on the coin-betting framework of Orabona & Pál (2016), a parameter-free online learning method with regret guarantees. In their setup, a fraction $\\lambda_t \\in [-1, 1]$ of wealth $W_{t-1}$ is bet on an outcome $c_t \\in [-1, 1]$, updating via:\n\n    $$ W_t = W\\_{t-1} + \\lambda_t W\\_{t-1} \\cdot c_t. $$\n\n    In our setting, \n       - Each round, a new nonconformity score $ S_t $ is generated.\n       - The learner compares $ S_t $ with the current quantile estimate $ q_t $ and receives privatized binary feedback via randomized response.\n       - This yields a privatized signal $ g_t $, approximating the subgradient of the pinball loss. We set $ c_t = -g_t $ to match the coin-betting formulation.\n\n  - Algorithm 2 then proceeds as follows:\n      - **Line 9:** Updates wealth $ W_t = W\\_{t-1} - q_t \\cdot g_t $.\n      - **Line 10:** Computes the adaptive betting fraction $ \\lambda\\_{t+1} $ using the KT betting strategy (Krichevsky and Trofimov, 1981), where $\\lambda_{t+1} = \\frac{\\sum_{i=1}^{t} g_i}{t+1} = \\frac{t}{t+1} \\lambda_t - \\frac{1}{t+1} g_t$.\n      - **Line 11:** Updates the next quantile estimate via $ q\\_{t+1} = \\lambda\\_{t+1} W_t $.\n\n  - This yields an LDP-compliant, one-bit adaptive quantile estimator with bounded regret. The coin-betting process is detailed in lines 170–178, and we will enhance the intuition further in the revised text for clarity.\n  - Our approach follows the standard method in Orabona & Pál (2016) (Algorithm 1). Given the theoretical nature of this work, the algorithm itself may not be as intuitive, but this is an inherent aspect of its theoretical framework.\n\n- **Clarification on line 151**. The statement refers to the fact that our update signal is derived from the key term in the subgradient of the pinball loss: $ \\mathbb{I}\\\\{S_t \\le q_t\\\\} - (1 - \\alpha), $ which depends only on whether the nonconformity score $S_t$ is less than or equal to the current estimate $q_t$. This binary structure naturally enables the use of the classical randomized response mechanism to satisfy LDP. \n   - Instead of collecting exact values, we issue a yes/no query (\"Is $S_t \\le q_t$?\") and perturb the yes/no answer using randomized response. Since this mechanism is inherently binary, it integrates seamlessly into our algorithm without modification. The update remains efficient, private, and fully compatible with the coin-betting framework. \n   - To improve clarity, we revised line 151 as follows: \"This inherent binary structure enables us to implement a local randomization mechanism via randomized response, which directly supports LDP constraints.\"\n\n- **Clarification on  $w_t$  and explanation of Algorithm 2 lines 9–11**. Our algorithm follows the standard coin-betting framework [Orabona & Pál, 2016], where a learner bets a fraction $\\lambda_t \\in [-1, 1]$ of current wealth $W_{t-1}$ on an outcome $c_t \\in [-1, 1]$, yielding a signed bet $w_t = \\lambda_t W_{t-1}$. This serves as a parameter-free estimate of the target quantity. In [Podkopaev et al., 2024], $c_t = -g_t$, where $g_t$ corresponds to the subgradient of the pinball loss:\n\n  - If $q_t \\ne S_t$, then  \n  $$\n  \\partial \\ell_{1-\\alpha}(q_t, S_t) = \\mathbb{I}\\\\{S_t \\leq q_t\\\\} - (1 - \\alpha)\n  $$\n\n  - If $q_t = S_t$, then  \n  $$\n  \\partial \\ell_{1-\\alpha}(q_t, S_t) \\in [\\alpha - 1, \\alpha]\n  $$\n\n   This subgradient structure enables coin-betting to estimate the target quantile. Coin-betting implements a parameter-free      online optimization method with provable regret bounds. When applied to the pinball loss subgradient—whose expectation vanishes at the $(1 - \\alpha)$-quantile—it naturally drives $w_t$ toward this quantile, yielding a consistent estimate without learning rate tuning.\n\n  - In our setting, we introduce a privatized version of $g_t$ via randomized response, carefully designed to satisfy:\n\n    $$ \\mathbb{E}[g_t] = r \\cdot (\\mathbb{I}\\\\{ S_t \\le q_t \\\\} - (1 - \\alpha)), $$\n\n    which mirrors the (scaled) pinball subgradient, ensuring consistency with the key term in the loss subgradient. This preserves the alignment with quantile estimation while enabling local differential privacy. For this reason, we interpret $w_t$ as a private approximation of the $(1 - \\alpha)$-quantile.\n\n  - Lines 9–11 of Algorithm 2 implement the classic coin-betting update loop, adapted to our privacy-aware setting:\n     - **Line 9** updates wealth $W_t$ based on the privatized signal $g_t$ and prediction $q_t$, reflecting gain or loss from the “bet.”\n     - **Line 10** uses the KT betting strategy to update $\\lambda\\_{t+1}$, acting as a running average of feedback.\n     - **Line 11** computes $q\\_{t+1} = \\lambda\\_{t+1} W_t$, which becomes the next quantile estimate.\n\n  - This loop provides an adaptive, parameter-free quantile estimator that is simple, efficient, and LDP-compliant. We elaborate further on its coin-betting interpretation in lines 170–178 of the paper.\n\n- **On the trade-off between privacy constraints and prediction coverage**\n\n  - There is an inherent trade-off between privacy and prediction coverage: stronger privacy (i.e., smaller $\\epsilon$) adds more noise, weakening the feedback signal and slowing convergence. This can lead to temporary undercoverage in early rounds, particularly in finite-sample settings (e.g., $n = 10{,}000$).\n\n   - This effect arises from the randomness introduced by the randomized response mechanism. However, as shown in Figures 2 and 3, coverage improves over time and steadily approaches the nominal level (e.g., 90%) across all privacy levels. In larger samples (e.g., Figure S.6), coverage is already close to nominal, confirming asymptotic consistency.\n\n  - In summary, while early undercoverage may occur due to privacy noise, our method achieves stable long-run coverage, demonstrating robustness even under strong LDP constraints.\n\n- **Clarification on wider intervals of DtACI.** As shown in Table 1, DtACI yields intervals that are slightly wider than ours but still much narrower than DPCP, with a slightly higher coverage. A similar pattern is seen in classification (Table S.1):\n\n  - Regarding DtACI, it produces slightly wider intervals (by ~0.03–0.04), but also provides ~0.01 higher coverage—an intuitive result of the coverage-size trade-off. The difference reflects the core design distinction: DtACI adaptively adjusts the miscoverage level $ \\alpha_t $ using expert weighting, while our method directly estimates the $ (1 - \\alpha) $ quantile through a parameter-free coin-betting update. Our method is feedback-efficient and tuning-free. In contrast, DtACI involves expert initialization and step size tuning, leading to more conservative calibration. These small differences reflect each method’s structure and trade-offs.\n\n\n\n\n\n**Table: Coverages and sizes for three classification cases under the proposed method and DtACI**\n|    | Case 1  | Case 1 | Case 2  | Case 2 | Case 3 | Case 3 |\n|----------|-------------|------|-------------|------|-------------|------|\n| Method   | Coverage | Size | Coverage | Size | Coverage | Size |\n| Proposed | 0.890       | 2.17 | 0.890       | 1.69 | 0.890       | 1.71 |\n| DtACI    | 0.900       | 2.20 | 0.901       | 1.73 | 0.900       | 1.75 |\n\n    \n\n- **Convergence Rate**. As noted in Appendix B, deriving non-asymptotic convergence bounds under LDP is an important but challenging open problem. While our current analysis focuses on asymptotic guarantees, we plan to explore finite-sample bounds in future work. That said, empirical results already show finite-sample performance even under strong privacy budgets (e.g., $\\epsilon = 0.5$), with average coverage around 0.85 over 10,000 time steps, demonstrating the method's practical robustness.\n\n- **Undercoverage in Table 1 and Figure 2:**\n \n  - We acknowledge the slight undercoverage observed in Table 1 and Figure 2. A similar trend was reported by Podkopaev et al. (2024), who observed ~88% long-run coverage using a coin-betting-based conformal predictor and considered the gap minor in practice. In our case, this undercoverage likely stems from early-round noise introduced by privatized feedback under strong privacy settings.\n\n  - This reflects a well-known trade-off: stronger privacy (smaller $\\epsilon$) increases noise via randomized response, weakening update signals, slowing convergence, and causing temporary undercoverage in finite samples (e.g., $n = 10{,}000$).\n\n  - However, this effect is transient. As shown in Figures 2 and 3, coverage steadily improves and converges toward the nominal level across all privacy levels. Larger-sample results (Figure S.6) show near-complete convergence, confirming asymptotic consistency.\n\n  - In summary, while early-stage undercoverage may occur, long-run coverage remains reliable—even under strong privacy (e.g., $\\epsilon = 0.5$), the method achieves 85% coverage, demonstrating practical robustness.\n\n**References**\n\nOrabona, F. and Pál, D. (2016). *Coin betting and parameter-free online learning*. In _Advances in Neural Information Processing Systems_, 29.\n\nPodkopaev, A., Xu, D., and Lee, K. (2024). *Adaptive conformal inference by betting*. arXiv preprint arXiv:2412.19318.\n\nKrichevsky, R. and Trofimov, V. (1981). *The performance of universal encoding*. IEEE Trans. Inf. Theory, 27(2):199–207."}, {"review_id": "SmCNlGikVp", "reviewer": "Reviewer_H3RF", "summary": "This paper studies the problem of privacy protection of online conformal prediction or uncertainty quantification. In the continuous streaming setting, this work proposes a method to make reliable predictions while maintaining privacy of every user by using randomized response (local DP) to answer the question. The algorithm runs in one-pass and has low space complexity and high computational complexity. The method is then applied to both regression and classification tasks. The proposed method is also model agnostic. The paper also gives theoretical guarantees as well as empirical evaluations of the method to demonstrate its feasibility.", "questions": "I have no questions.", "limitations": "The authors did address the limitations of the work in the appendix. This would be better in the main text of the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper quality is pretty good, it provides a good introduction to the topic and a clear problem description. The work studies an important problem of privacy in the online setting. To my knowledge, there is no work prior to this which studies this particular setup. Privacy is an important concern in the live decision-making systems. I believe the work is significant and original, despite the simplicity of the methods used.\n\nWeaknesses:\nThe proofs are all in the appendix, which is a downside of the work. I propose that some intuition of the proofs are added to the main text of the paper to have completeness. The experiments could be better explained. Also, the figures should say what the y-axis is representing.", "was_revised": true, "final_justification": "The authors addressed my concerns adequately.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Intuition of the Proofs**. This is an excellent comment.  We now summarize the key ideas behind our main theoretical results and will include the following in the revised version.\n\n   - **3.1. Corollary 3.1 (Regret Bound)**. The proof leverages the KT-based (Krichevsky and Trofimov, 1981) coin-betting framework, where regret remains sublinear as long as the privatized updates $g_t$ are bounded in $[-1, 1]$ (Orabona and Pál, 2016)—a condition satisfied by our randomized response mechanism.\n\n   - **3.2. Theorem 3.2 (Privacy Guarantee)**. With probability $r$, the user returns a truthful binary response indicating whether $S_t \\le q_t$; otherwise, a fair coin is flipped. This randomized mechanism masks the true response, and the privacy level $\\epsilon$ quantifies the worst-case distinguishability between outputs for different true answers.\n\n   - **3.3–3.4. Theorems 3.3 and 3.4 (LDP Guarantees)**. Theorem 3.3 shows our algorithm satisfies $(\\max_{1 \\leq j \\leq t} \\epsilon_j, 0)$-LDP since each user contributes only once through a local randomizer. Privacy is preserved via parallel composition, and only post-processed private outputs are used. \n\n       Theorem 3.4 extends this to the full pipeline: if the predictive model is trained under $(\\varepsilon_j, \\delta_j)$-LDP, then combining it with our querying mechanism yields per-round privacy of $(\\epsilon_j + \\varepsilon_j, \\delta_j)$.\n\n  - **3.5. Theorem 3.5 (Asymptotic Coverage).** Although each feedback bit is noisy, its expectation aligns with the true subgradient:\n    $$\\mathbb{E}[g_t] = r \\cdot (\\mathbb{I}\\\\{S_t \\le q_t\\\\} - (1 - \\alpha)).$$\n\n    Thus, in expectation, the updates move $q_t$ toward the target $(1 - \\alpha)$ quantile. Over time, this leads to convergence of the prediction sets to the desired long-run coverage, even under strong privacy noise.\n\n- **More explanation on the experiments.**  We agree that clearer exposition would improve the interpretability of our results. While the experiments demonstrate strong performance across different privacy levels and task types (regression/classification; synthetic/real), we will revise the experimental section to enhance clarity by:\n\n  - Clarifying axis labels in all figures (e.g., y-axis denotes empirical coverage or interval width over time);\n  - Making the figure captions more descriptive;\n  - Adding brief summaries to highlight key trends observed in each figure.\n  - For example, we observe that stronger privacy (smaller $\\epsilon$) leads to slightly lower empirical coverage in early rounds due to weaker update signals $g_t$, which slows the convergence of $q_t$. As shown in Figures 2 and 3, this undercoverage diminishes over time, and coverage steadily approaches the nominal level (e.g., 90%), highlighting the method’s asymptotic robustness.\n\n- **The y-axis.** We will explicitly label all y-axes in the figures. Depending on the context, the y-axis will be marked as either \"Coverage\" or \"Prediction Interval Width/Set Size\", and figure captions will be updated accordingly to improve clarity and interpretability.\n\n- **Conclusion and Limitations.** We have moved the discussion of limitations, previously placed in Appendix B due to space constraints, into the main text for completeness. The following section will appear at the end of the main body.\n  - This paper proposes a novel and practical framework for online conformal prediction under LDP. By combining randomized binary feedback with a coin-betting update scheme, the method enables one-pass, model-free prediction set construction with formal privacy guarantees. It supports both regression and classification, operates efficiently in streaming settings with constant memory. Despite its strengths, several limitations remain. First, Theorem 3.5 provides only asymptotic coverage guarantees; deriving non-asymptotic bounds under LDP is an important direction for future work. Second, we use standard nonconformity scores, which are broadly applicable but may yield conservative sets; exploring data-adaptive scores could improve efficiency.\n\n**References**\n\nOrabona, F. and Pál, D. (2016). *Coin betting and parameter-free online learning*. In _Advances in Neural Information Processing Systems_, 29.\n\nKrichevsky, R. and Trofimov, V. (1981). *The performance of universal encoding*. IEEE Trans. Inf. Theory, 27(2):199–207."}]

Author rebuttal:

Meta-review: ## Metareview

This paper studies online conformal prediction under local differential privacy (LDP). The setting is that, at each time step $t$, we receive an example $X_t$ and would like to output a set $\hat{C}_t(X_t)$ such that the label $Y_t$ is contained (i.e. "covered") in this set; we aim for a high coverage while still ensuring that the set $\hat{C}_t(X_t)$ is of small size. As usual, here we receive $Y_t$ after the prediction and we thus can update our prediction for the next rounds accordingly. In conformal prediction, the set $\hat{C}_t(X_t)$ is not arbitrary but is based on computing some score $S_t(X_t, y)$ and then keep only $y$ whose score is at most a certain threshold $q_t$. To achieve a certain coverage $1 - \alpha$, we wish to set the threshold to be the $(1 - \alpha)$-quantile. The privacy protection considered in this paper is for $(X_t, Y_t)$. The LDP model means that the algorithm immediately privatize each $(X_t, Y_t)$ and that there is no need for the curator.

The main insight in this paper is that the gradient update for $q_t$ only uses a single bit of information: whether $Y_t$ is contained in the predicted set $\hat{C}_t(X_t)$. Therefore, by applying the classic binary randomized response (and then debiasing the update to the threshold), such an algorithm can be made LDP. By subtlety combining this with online convex optimization, this gives regret guarantees for the algorithm. Finally, the authors also perform experiments; the algorithm empirically outperforms known DP conformal algorithm of Angelopoulos et al. (2022), which works in an even more relaxed model of central DP that allows a trusted curator, and is quite competitive against non-private algorithm of Gibbs and Candes (2024).

## Strengthes

- Apart from a (likely) parallel work of Zhang et al. (ICML 2025), this is the first paper that considers conformal prediction under LDP, which is a natural setting. The paper also obtains compelling initial results in the model.

- The proposed algorithm is simple and likely to be practical.

- The experimental results suggest good empirical performance, e.g. even against well-known a non-private method of Gibbs and Candes (2024).

## Weaknesses

- From LDP perspective, the use of (binary) randomized response and debiased gradient is ubiquitous in literature and is not novel, although they are still novel in the context of DP online conformal prediction.

- There are some recent papers on the topic, such as Penso et al. and Zhang et al. (ICML 2025), that are not cited or discussed in the paper. This is addressed in the rebuttal to reviewer nEbK. (Note that these papers are likely parallel contribution and might have been available online only very close to or even after the NeurIPS submission deadline.)

## Recommendation

This paper studies a new privacy-preserving model for conformal prediction and propose an algorithm that has good theoretical and empirical performance. This is thus a solid starting point that can lead to future research in this direction.
Decision: Accept (poster)