Online Differentially Private Conformal Prediction for Uncertainty Quantification

Thank you for your valuable suggestions. We address each point below.

• Privacy Guarantees of Theorem 4.4. Our core contribution is Algorithm 2's online private quantile construction, which enables Algorithm 1 to generate online private prediction sets via DP's post-processing property. While we focused theoretical analysis on Algorithm 2's privacy guarantees (which automatically extend to Algorithm 1), we will explicitly state Algorithm 1's privacy guarantees in Theorem 4.4.

  • Theorem 4.4 (Revised). Algorithm 1 satisfies $\max_{1 \leq j \leq t} \epsilon_j$-DP, $(\max_{1 \leq j \leq t} \epsilon_j, \max_{1 \leq j \leq t} \delta_j)$-DP, or $\max_{1 \leq j \leq t} \mu_j$-GDP, depending on the mechanism used, where $t \geq 1$.
  • In line with composition-based privacy intuition, the privacy-utility trade-off is governed by $\max_t \mu_t$. Our additional experiments with time-varying $\mu_t$ in Table 3 and Figure 5 through the link shows that long-run performance depends on the maximum privacy parameter.

• Definition 3.1 applying to an online setting. While Definition 3.1 provides a general DP framework, our method specifically enforces LDP at each step by controlling plausible deniability for any two individual values- a special case of Definition 3.1. Unlike global DP, which requires a trusted curator, LDP operates at the individual level: users randomize their data locally before sharing, ensuring protection even from the data collector. We will formally define LDP in the revision for clarity.

• Comparison with a private baseline. To the best of our knowledge, our work is the first to construct online DP conformal prediction sets in the streaming setting. To provide a meaningful baseline, we compare our method with the Private Prediction Sets method proposed by Angelopoulos et al. (2021), an approach for constructing prediction sets under DP in the offline setting with access to the full calibration dataset. It cannot handle streaming data or distribution shifts, especially changepoints, due to its static model. Table 1 shows that while Private Prediction Sets achieve slightly higher coverage, our method (ODPCP) yields narrower prediction intervals, especially under strong privacy constraints. This demonstrates that ODPCP offers a favorable privacy–efficiency trade-off in the online setting.

• Contributions and Relation to the literature. Our work tackles the critical yet underexplored challenge of private uncertainty quantification in streaming environments. We will add the following comment in the revision.

  • Unlike existing private conformal methods—such as the offline approach of Angelopoulos et al. (2021) or the federated solution of Plassier et al. (2023)—our method is specifically designed for online applications, advancing both privacy-preserving prediction and real-time uncertainty quantification.
  • The core technical innovation addresses a fundamental tension: maintaining valid coverage under privacy constraints while processing data in a single pass. Unlike batch methods, our privatized quantile estimation must balance noise injection with statistical efficiency without future data access. We provide theoretical guarantees of long-run nominal coverage despite these constraints.

• Nonconformity score at time step $t$: In Algorithm 1, nonconformity scores $S_t$ are computed and used in a strict one-pass manner to ensure streaming compatibility. At each time step $t$, the score $S_t = \mathcal{S}(X_t, Y_t)$ is computed for the current observation $(X_t, Y_t)$ and used once at $t+1$ to update the private quantile estimate $\hat{q}_{t+1}^{1-\alpha}$ via Algorithm 2. For instance, $S_1$ (initialized arbitrarily) updates $\hat{q}_2^{1-\alpha}$, while $S_2$ updates $\hat{q}_3^{1-\alpha}$, and so forth. Crucially, each $S_t$ is discarded immediately after use, avoiding storage of historical scores and guaranteeing memory-efficient operation in online settings. This design allows streaming without accessing past observations.

• An example of privately trained models. Our framework is model-agnostic, and it provides online private prediction sets regardless of whether the base model was trained with DP-SGD or standard SGD. This intentional decoupling focuses privacy guarantees on the conformalization step. We have included empirical comparisons (Figures 7-8, 12-13 in the Appendix) showing stable coverage rates across both training approaches and wider intervals with DP-SGD models, reflecting their inherent prediction uncertainty (via higher $S_t$ scores). These findings confirm our method's robustness to the base model's privacy status.

• Presentation. We will add missing algorithm input parameters and fix typos, ambiguous expressions, and formatting issues(see Table 2 in the link).

Thank you for your valuable suggestions. We address each point below.

• Definition of μ-GDP. We will revise the paper to include a formal definition of μ-GDP(Dong et al., 2022).

• Clarification of Line 150. We will revise Line 150 to include the private quantile online update rule and clarify its connection to the private subgradient used in the quantile update. Specifically, the private subgradient is computed as:

The quantile estimate is then updated via:

This enables adaptive updates of $\hat{q}_{t+1}^{1 - \alpha}$ via real-time feedback $\hat{g}_t$, while preserving privacy. The update is learning-rate-free and matches Algorithm 2.

• Clarification of Line 191. We will clarify the connection to Algorithm 2's update rules in the revision, which govern our online quantile adjustment via:

  • Update of internal ``wealth'': $W_t = \max\lbrace W_{t-1} - \hat{g}_t \cdot \hat{q}_t^{1 - \alpha} \, c \rbrace$.
  • Update of running average: $\lambda_{t+1} = \frac{t}{t+1} \lambda_t - \frac{1}{t+1} \hat{g}_t$.
  • Quantile update: $\hat{q}^{1 - \alpha} _ {t+1} = \lambda_{t+1} \cdot W_t$
  • These update rules, derived from coin-betting potentials, enable adaptive, learning-rate-free quantile updates.

• Figure readability. Updated figures will appear in the main paper for improved clarity. See Figure 1 for the revised version.

• Clarification of Line 596. We will add the following comments to support these claims. The Kelly-inspired wealth process $W_t$ demonstrates stable long-term growth and can diverge to infinity under mild conditions, even in adversarial settings [Orabona and Pál, 2016]. Consequently, beyond some time $T$, the lower bound $c$ becomes inactive, leaving updates entirely driven by adaptive coin-betting dynamics [Cutkosky and Orabona, 2019].

• Hyperparameters adjustment in line 191. We adapt coin betting [Cutkosky and Orabona, 2018] to more complex online private conformal prediction problems by using noise-perturbed subgradients and introducing a transient lower bound $c$. This yields learning-rate-free updates supporting one-pass processing, DP guarantees, and adaptive calibration.

• Static and dynamic regrets. Our work focuses on coverage guarantees under DP, not regret. While conformal prediction evaluates performance through coverage and interval size, investigating regret-based metrics for private conformal prediction remains an interesting direction for future work.

• Clarifications of Section 5. You are right! Section 5 extends our method to conformal quantile regression (CQR), using quantile regression-derived scores to create prediction sets robust to heteroscedastic and heavy-tailed data.

• Comparisons with ACI or AtACI. Our work is specifically aimed at private conformal prediction methods for online settings, where existing approaches (ACI, DtACI) lack privacy guarantees. While direct comparison with non-private methods is limited by differing objectives, we benchmark against: (1) Original online baselines (quantifying privacy-utility tradeoffs) and (2) Offline DP-CP [Angelopoulos et al., 2021]. As Table 1 shows, our method achieves comparable coverage with 30-50% narrower prediction sets, demonstrating superior online efficiency under privacy constraints.

• Explanations on cases in the synthetic section. Due to space constraints, we omitted detailed justifications but will add them using the extra page. Our synthetic cases evaluate methods across (i) covariate dependence, (ii) noise structure, and (iii) temporal dynamics. Setting 1 examines static environments (fixed coefficients), while Setting 2 tests dynamic scenarios with changepoints, ensuring comprehensive evaluation under practical conditions.

• Initialization of $W_0$, $\lambda_1$. We conduct sensitivity analysis to initialization parameters $W_0$ and $\lambda_1$​ by taking multiple values. Figure 2 shows stable coverage across configurations, demonstrating algorithm robustness to starting values.

• CP interval for Figure 4. We'll add CP intervals. Please refer to the updated Figure 3.

• $\mu=0$.We use $\mu=0$ to denote the no-noise case and will revise this notation for clarity.

• Notations. We will correct all typos, formatting issues, and ambiguous expressions.

Thank you for your valuable suggestions. We address each point below

• Finite sample converge rates. Theorem 4.5 shows that ODPCP achieves the desired long-run coverage. Although it does not provide explicit finite-sample convergence rates, our empirical results indicate rapid convergence in practice, with strong coverage even in early rounds, making the method well-suited for real-world streaming applications. We agree that formal convergence bounds would be valuable and highlight this as an important direction for future work.

• LDP. Although our paper briefly mentioned local differential privacy (LDP), we acknowledge the need for a more formal definition. We will add the following definition of $(\varepsilon, \delta)$-LDP and its implications.

  • (Xiong et al., 2020) A randomized algorithm $A: \mathcal{X} \rightarrow \mathcal{R}$ satisfies $(\varepsilon, \delta)$-LDP if and only if any pair of input individual values $x, x' \in \mathcal{X}$, for every measurable event $E \subseteq \mathcal{R}$:

When $\delta = 0$, this reduces to pure LDP.

• Unlike global differential privacy that requires a trusted curator, LDP enforces privacy at the individual level—each user randomizes their data locally before sharing it, providing protection against the data collector itself.

• Experiments. We strengthen our experimental results with additional analyses from multiple perspectives, which we will include in the final version using the extra page.

  • Classification tasks. We evaluate ODPCP on activity classification using the PAMAP2 dataset, categorizing activities into three classes (resting, light, vigorous) based on heart rate and sensor data. An XGBoost model provides predictions, with ODPCP generating private prediction sets at each time step $t$. Figure 4 (available anonymously here) shows ODPCP’s broad applicability to discrete prediction problems, maintaining strong empirical coverage and adaptive behavior under privacy constraints.
  • Reproducing results using random seeds. While Setting 1 used fixed random seeds for reproducibility, the similarity between Cases 1-2 reflects their analogous data-generating processes and our method's robustness. Additional experiments in Table 4 confirm this stability, showing nearly identical results without seed fixing.
  • Privacy budget allocation. Our framework supports time-varying privacy parameters $\mu_t$, enabling adaptive privacy control for each individual. Consistent with privacy composition, the overall privacy-utility trade-off is typically governed by $\max_t \mu_t$. We evaluated privacy budget allocation’s impact through two complementary experiments.
    • (1) In Table 3 campares random-budget setting $\mu_t \sim \text{Uniform}(0.5, 2.0)$ with fixed $\mu = 2.0$ across all synthetic cases. The coverage results are consistently close, demonstrating that random allocation preserves long-run performance.
    • (2) Figure 5 demonstrates ODPCP's empirical stability across sample sizes (10k–100k) under dynamic per-step privacy allocations.

• Generalization to other data types. Our method is model-agnostic. ODPCP's key innovation is Algorithm 2's private quantile update, which operates independently of model architecture or data type. This enables ODPCP to be applied to high-dimensional data (sensor streams, text, images) with some appropriate predictive model.

  • Computational Efficiency. The quantile update is lightweight and efficient, with computational costs dominated by the base model $\hat{f}_t(\cdot)$.
  • privacy–coverage trade-offs. They are determined by the base model's prediction quality, while our update maintains computational stability across diverse tasks.

• Comparisons with online methods. Our work is specifically focused on online private conformal prediction methods for streaming settings, where existing approaches (ACI, DtACI) lack rigorous privacy guarantees. Direct comparisons are limited by differing objectives.

  • We supplemented our experiments with a comparison against an offline private method—Private Prediction Sets (DPCP; Angelopoulos et al., 2021). As shown in Table 1, both methods achieve similar coverage. However, ODPCP produces significantly narrower prediction sets, highlighting its efficiency in the online setting with privacy.

• Notation issues. We will enhance the paper's clarity through explicit notation definitions, and full consistency review.