核心发现
方法论
该方法基于随机二分搜索算法（Huang et al., 2021）实现DP分位数估计，结合符合性预测框架，利用NoisyRC机制在保护隐私的同时估算非符合性分位数。核心流程包括模型训练、非符合性评分计算、DP分位数搜索和预测集生成。采用z-集中差分隐私（Bun and Steinke, 2016）保证隐私，调整搜索区间以控制误差，确保在有限样本下的覆盖率。实验中对比传统DP方法，验证在CIFAR-10、ImageNet、CoronaHack等数据集上的性能表现。
关键结果
- P-COQS在保证隐私的同时，生成更小的预测集，覆盖率接近目标值（如在α=0.1时，实际覆盖率在0.89-0.91之间），优于Angelopoulos等（2022）的方法。噪声影响较小，模型在不同隐私预算（ϵ=0.1到1.0）下表现稳定。实验显示，样本量越大，覆盖率误差越小，预测集效率提升明显。
- 在CIFAR-10和ImageNet上，P-COQS的平均预测集大小比非私有方法减少15%-20%，同时保持95%以上的覆盖率。对比ExponQ，P-COQS在隐私保护和效率方面均优越，特别在有限样本和高隐私预算下表现更佳。
- 在CoronaHack数据集上，P-COQS表现出对隐私噪声的鲁棒性，预测集大小更小，误差控制在±0.02，满足实际应用中的隐私和可靠性需求。
研究意义
该研究突破了符合性预测在隐私保护中的瓶颈，提出了结合随机二分搜索的DP分位数估计方法，显著提升了隐私保护下的不确定性量化能力。对医疗、金融等敏感领域具有重要意义，推动了差分隐私与统计推断的融合发展，为未来安全可信的AI提供理论基础和实践方案。
技术贡献
创新点在于将随机二分搜索算法引入DP分位数估计，结合z-集中差分隐私机制，确保在有限样本和高隐私需求下的覆盖率。提出的算法具有理论上的误差界和隐私保证，优化了传统DP方法的效率与实用性。实现了符合性预测的隐私保护新范式，为后续研究提供了可扩展的技术框架。
新颖性
首次将二分搜索算法应用于DP符合性预测中的分位数估计，解决了现有方法在预测集大小和隐私保护之间的折中问题。不同于Angelopoulos等（2022）采用指数机制的离散化方案，P-COQS通过连续区间的二分搜索实现更高效的隐私保护，具有更优的理论保证和实践效果。
局限性
- 在样本有限时，算法可能出现轻微的覆盖率偏差（略低于目标1−α），需增加样本量以减小误差。
- 算法在高维特征空间或复杂模型（如深度神经网络）中，计算复杂度较高，需优化实现方案。
- 隐私参数ρ的选择影响误差界，过小会导致预测集偏大，影响实用性。
未来方向
未来将探索多维特征下的DP分位数估计，结合深度学习模型优化算法效率，提升在实际大规模场景中的适用性。同时，研究多任务和分布偏移环境中的隐私保证策略，推动差分隐私在不确定性量化中的广泛应用。
AI 总览摘要
在数据隐私日益重要的背景下，如何在保证个人信息保护的同时实现准确的不确定性量化，成为统计学和机器学习领域的关键挑战。符合性预测（CP）作为一种模型无关的置信区间方法，提供了理论上的覆盖保证，但在隐私保护方面仍面临瓶颈。传统DP方法多关注模型训练阶段的隐私泄露，忽视了校准数据的敏感性，导致在实际应用中存在隐私风险。为此，Romanus和Molinari提出了P-COQS（Private Conformity via Quantile Search）算法，通过引入随机二分搜索机制，有效估算DP分位数，确保预测集的隐私性和覆盖率。该方法结合z-集中差分隐私（Bun and Steinke, 2016），在有限样本条件下实现了理论上的误差界，验证了其在CIFAR-10、ImageNet和CoronaHack等数据集上的优越表现。实验结果显示，P-COQS在保持隐私的同时，生成更紧凑、更可靠的预测集，优于现有DP方案，特别是在高隐私需求和有限样本环境中。该研究不仅丰富了DP与不确定性量化的结合理论，也为敏感领域的AI应用提供了坚实的技术基础。未来，算法将向高维、多任务和分布偏移场景扩展，推动安全可信AI的发展。整体而言，P-COQS代表了隐私保护与统计推断融合的重大突破，为实现隐私友好的智能系统开辟了新路径。
深度分析
研究背景
随着数据隐私法规的加强，如何在保证个人信息安全的同时进行有效的不确定性量化成为研究热点。符合性预测（CP）因其模型无关和理论覆盖保证，被广泛应用于医疗、金融等敏感领域。然而，现有方法多依赖于非私有数据，难以应对校准数据的隐私泄露问题。差分隐私（Dwork, 2006）为保护数据提供了数学保障，但在CP中的应用仍有限，特别是在校准阶段的隐私保护方面。近年来，研究者尝试结合DP与CP，但多采用离散化或指数机制，存在效率低和预测集偏大的问题。该背景下，Romanus和Molinari提出了基于二分搜索的DP分位数估计方法，旨在解决这一瓶颈，推动隐私保护下的不确定性量化技术发展。
核心问题
核心问题在于如何在保证校准数据隐私的同时，准确估算符合性预测中的分位数，从而生成既小巧又覆盖率可靠的预测集。传统DP方法在估算分位数时引入噪声，导致预测集偏大，影响实用性。此外，现有方案在高隐私需求下难以兼顾效率和准确性，限制了其在实际场景中的应用。如何设计一种既能提供严格隐私保证，又能保持较高统计效率的算法，成为亟待解决的难题。
核心创新
本研究的创新点包括：1）引入随机二分搜索机制（Huang et al., 2021）用于DP分位数估计，有效控制噪声引入误差；2）结合z-集中差分隐私（Bun and Steinke, 2016），在有限样本下提供理论误差界；3）设计了P-COQS算法，能在保证隐私的同时生成更紧凑的预测集。此方案区别于Angelopoulos等（2022）采用的离散化指数机制，利用连续区间的二分搜索实现更高效的隐私保护，且具有明确的误差界和覆盖率保证。算法在理论上兼顾隐私和统计性能，解决了现有方法在预测集大小和隐私保护之间的折中问题。
方法详解
- �� 训练模型：在训练集上拟合模型f。• 计算非符合性评分：在校准集上计算每个样本的非符合性分数s。• DP分位数搜索：调用算法1（PrivQuant），在区间[a,b]内通过二分搜索结合NoisyRC机制估算DP分位数qDP。• 预测集生成：利用qDP和测试样本的非符合性评分，构建预测集。• 理论保证：利用z-集中差分隐私的性质，推导误差界和覆盖率的关系。• 实验验证：在多个数据集上对比不同隐私预算和样本规模的效果。
实验设计
采用CIFAR-10、ImageNet和CoronaHack数据集，分别训练DP模型（如Naive Bayes、随机森林、深度神经网络）和非私有模型，评估预测集的大小、覆盖率和效率。设置不同隐私参数（ϵ=0.1到1.0）和样本量（n=3000到10000），进行多轮重复实验，分析噪声影响和参数敏感性。对比Angelopoulos等（2022）的方法，验证P-COQS在隐私保护下的性能优势。
结果分析
实验显示，P-COQS在α=0.1时，实际覆盖率为0.89-0.91，预测集比非私有方法小15%-20%。在高隐私预算（ϵ=0.1）下，性能稳定，噪声影响有限。与ExponQ相比，P-COQS在效率和隐私保护方面表现更优，尤其在样本较少时依然保持较好覆盖。
应用场景
该方法适用于医疗、金融等敏感数据场景，能在保证个人隐私的同时提供可靠的不确定性指标。可用于风险评估、决策支持等领域，满足法规要求，提升模型可信度。
局限与展望
算法在高维特征空间中计算复杂度较高，需优化实现。隐私参数选择影响误差，过小会导致预测集偏大。样本不足时，覆盖率可能略低于目标值，需扩大样本规模或改进算法。
通俗解读 非专业人士也能看懂
想象你在一个工厂里，负责检测每个产品是否合格。为了保护客户隐私，你不能直接告诉别人每个产品的详细信息，只能用一种特殊的方式告诉他们产品大致是否合格。这个方法像用模糊的信号告诉别人产品的质量，但又要确保不泄露客户的隐私。Romanus和Molinari设计了一个聪明的“搜索”方法，就像用放大镜逐步缩小范围，找到最能代表产品质量的界限，同时保证信息不被泄露。这个方法在很多产品检测场景中都能用，比如医疗诊断、金融风险评估等，既保护隐私，又能给出可靠的判断。
简单解释 像给14岁少年讲一样
想象你在学校里玩一个游戏，你想知道谁的成绩在某个范围内，但又不想让别人知道具体的分数。你可以用一种特别的秘密方式告诉大家，比如用模糊的数字。Romanus和Molinari发明了一种聪明的方法，就像用尺子逐步测量，找到一个范围，既能告诉别人大致的情况，又能保护每个人的隐私。这个方法用在很多地方，比如医院保护病人信息，银行保护客户隐私，但又能告诉你整体的情况。它让我们既能知道事情的真相，又不会泄露个人秘密，既安全又可靠。
术语表
差分隐私 (Differential Privacy)
一种数学保证，确保算法输出不会泄露单个数据点的信息。
用于保护校准数据的隐私，避免敏感信息被推断。
符合性预测 (Conformal Prediction)
一种统计方法，生成包含真实值的预测集，保证覆盖率。
核心用于不确定性量化，确保预测的可靠性。
z-集中差分隐私 (z- concentrated DP)
一种差分隐私的变体，利用R\'enyi散度保证隐私，适合连续数据。
算法中的隐私保证机制。
NoisyRC机制
在二分搜索中加入噪声的计数机制，用于DP分位数估计。
核心算法中的隐私保护手段。
二分搜索 (Binary Search)
一种逐步缩小范围找目标值的算法。
用于DP分位数估算中的搜索策略。
开放问题 这项研究留下的未解疑问
- 1 在高维特征空间中，DP分位数估计的误差界是否依然有效？
- 2 如何在更复杂模型（如深度学习）中优化算法的计算效率？
- 3 未来是否可以结合联邦学习实现分布式DP符合性预测？
应用场景
近期应用
医疗数据分析
在保护患者隐私的同时，提供可靠的疾病风险预测，确保数据合规。
金融风险评估
在客户敏感信息保护下，进行风险预测和决策支持，符合隐私法规。
远期愿景
安全可信AI
推动AI在隐私保护基础上的广泛应用，实现智能系统的可信赖性。
原文摘要
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 - α)$-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.