标题： 通过分位数二分查找的差分隐私共形预测 显示英文标题

标题： Differentially Private Conformal Prediction via Quantile Binary Search

摘要： 大多数差分隐私（DP）方法侧重于限制学习者在基于其训练数据时的隐私泄露，而较少有方法考虑在涉及校准数据集的程序中可能出现的泄露，这在不确定性量化方法（如合规预测（CP））中很常见。 由于这一方向上的方法有限，我们在本工作中提出了一种通用的DP方法用于CP，我们称之为通过分位数搜索的私有合规性（P-COQS）。 所提出的方法适应了一种现有的随机二分搜索算法，用于在CP的校准阶段计算DP分位数，从而保证后续预测集的隐私性。 然而，这会带来一定的代价，即在使用有限样本校准集时，相对于所需的$(1 - \alpha)$-水平略有覆盖不足（尽管广泛的实证结果表明，P-COQS在所考虑的情况下通常能实现所需水平）。 为了验证所适应算法的性质并量化后续CP的近似覆盖保证，我们进行了大量实验，以检查隐私噪声、样本大小和显著性水平对我们的方法相对于现有替代方法性能的影响。 此外，我们在几个基准数据集上对我们的方法进行了实证评估，包括CIFAR-10、ImageNet和CoronaHack。 我们的结果表明，所提出的方法对隐私噪声具有鲁棒性，并且在经验覆盖、效率和信息性方面相对于当前的DP替代方法表现更优。 具体而言，结果表明，在所有这些实验设置中，P-COQS能够生成更小的合规预测集，同时针对所需的覆盖水平和隐私保证。 显示英文摘要

摘要： 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.