Online Locally Differentially Private Conformal Prediction via Binary Inquiries

Chenfei Gu (Shanghai University of Finance and Economics) · Qiangqiang Zhang (Shandong University) · Ting Li (Shanghai University of Finance and Economics) · Jinhan Xie (Yunnan University) · Xinwei Feng (Shandong University)

classification tasks computational efficiency local differential privacylong-run coverageminimal storage requirementsmodel-free prediction setsone-pass online manneronline conformal prediction privacy protectionrandomized binary inquiriesregression tasks space complexitystatistical reliabilitystreaming data uncertainty quantification

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.