Differentially Private Conformal Prediction via Quantile Binary Search

• URL: http://arxiv.org/abs/2507.12497v1
• Date: Tue, 15 Jul 2025 22:08:02 GMT
• Title: Differentially Private Conformal Prediction via Quantile Binary Search
• Authors: Ogonnaya M. Romanus, Roberto Molinari,
• Abstract summary: We propose a general DP approach for Conformal Prediction (CP) that we call Private Conformity via Quantile Search (P-COQS)<n>The proposed approach adapts an existing randomized binary search algorithm for computing DP quantiles in the calibration phase of CP thereby guaranteeing privacy of the consequent prediction sets.<n>We conduct extensive experiments to examine the effects of privacy noise, sample size and significance level on the performance of our approach compared to existing alternatives.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most Differentially Private (DP) approaches focus on limiting privacy leakage from learners based on the data that they are trained on, there are fewer approaches that consider leakage when procedures involve a calibration dataset which is common in uncertainty quantification methods such as Conformal Prediction (CP). Since there is a limited amount of approaches in this direction, in this work we deliver a general DP approach for CP that we call Private Conformity via Quantile Search (P-COQS). The proposed approach adapts an existing randomized binary search algorithm for computing DP quantiles in the calibration phase of CP thereby guaranteeing privacy of the consequent prediction sets. This however comes at a price of slightly under-covering with respect to the desired $(1 - \alpha)$-level when using finite-sample calibration sets (although broad empirical results show that the P-COQS generally targets the required level in the considered cases). Confirming properties of the adapted algorithm and quantifying the approximate coverage guarantees of the consequent CP, we conduct extensive experiments to examine the effects of privacy noise, sample size and significance level on the performance of our approach compared to existing alternatives. In addition, we empirically evaluate our approach on several benchmark datasets, including CIFAR-10, ImageNet and CoronaHack. Our results suggest that the proposed method is robust to privacy noise and performs favorably with respect to the current DP alternative in terms of empirical coverage, efficiency, and informativeness. Specifically, the results indicate that P-COQS produces smaller conformal prediction sets while simultaneously targeting the desired coverage and privacy guarantees in all these experimental settings.

Related papers

• Conformal Prediction for Privacy-Preserving Machine Learning [83.88591755871734]
  Using AES-encrypted variants of the MNIST dataset, we demonstrate that Conformal Prediction methods remain effective even when applied directly in the encrypted domain.<n>Our work sets a foundation for principled uncertainty quantification in secure, privacy-aware learning systems.
  arXiv  Detail & Related papers  (2025-07-13T15:29:14Z)
• Conformal Information Pursuit for Interactively Guiding Large Language Models [64.39770942422288]
  This paper explores sequential querying strategies that aim to minimize the expected number of queries.<n>One such strategy is Information Pursuit (IP), a greedy algorithm that at each iteration selects the query that maximizes information gain or equivalently minimizes uncertainty.<n>We propose Conformal Information Pursuit (C-IP), an alternative approach to sequential information gain based on conformal prediction sets.
  arXiv  Detail & Related papers  (2025-07-04T03:55:39Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• CURATE: Scaling-up Differentially Private Causal Graph Discovery [8.471466670802817]
  Differential Privacy (DP) has been adopted to ensure user privacy in Causal Graph Discovery (CGD) We present CURATE, a DP-CGD framework with adaptive privacy budgeting. We show that CURATE achieves higher utility compared to existing DP-CGD algorithms with less privacy-leakage.
  arXiv  Detail & Related papers  (2024-09-27T18:00:38Z)
• Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency through MUltistage Sampling Technique (MUST) [3.0939420223851446]
  We propose a class of subsampling methods for privacy amplification (PA) We conduct comprehensive analyses of the PA effects and utility for several 2-stage MUST procedures. We provide the privacy loss composition analysis over repeated applications of MUST.
  arXiv  Detail & Related papers  (2023-12-20T19:38:29Z)
• Adaptive Differentially Quantized Subspace Perturbation (ADQSP): A Unified Framework for Privacy-Preserving Distributed Average Consensus [6.364764301218972]
  We propose a general approach named adaptive differentially quantized subspace (ADQSP) We show that by varying a single quantization parameter the proposed method can vary between SMPC-type performances and DP-type performances. Our results show the potential of exploiting traditional distributed signal processing tools for providing cryptographic guarantees.
  arXiv  Detail & Related papers  (2023-12-13T07:52:16Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Non-parametric Differentially Private Confidence Intervals for the Median [3.205141100055992]
  This paper proposes and evaluates several strategies to compute valid differentially private confidence intervals for the median. We also illustrate that addressing both sources of uncertainty--the error from sampling and the error from protecting the output--should be preferred over simpler approaches that incorporate the uncertainty in a sequential fashion.
  arXiv  Detail & Related papers  (2021-06-18T19:45:37Z)
• Gaussian Processes with Differential Privacy [3.934224774675743]
  We add strong privacy protection to Gaussian processes (GPs) via differential privacy (DP) We achieve this by using sparse GP methodology and publishing a private variational approximation on known inducing points. Our experiments demonstrate that given sufficient amount of data, the method can produce accurate models under strong privacy protection.
  arXiv  Detail & Related papers  (2021-06-01T13:23:16Z)
• Private Prediction Sets [72.75711776601973]
  Machine learning systems need reliable uncertainty quantification and protection of individuals' privacy. We present a framework that treats these two desiderata jointly. We evaluate the method on large-scale computer vision datasets.
  arXiv  Detail & Related papers  (2021-02-11T18:59:11Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.