针对敏感数据差异,提出自适应选择机制提升隐私保护下的选优效果。
Private Selection with Heterogeneous Sensitivities
- 根据得分与敏感度相关性动态选择隐私机制
- 新方法在极端场景下优于经典算法,避免随机选择风险
- 改进版GEM增强鲁棒性,适合高敏感度差异场景
差分隐私选择问题涉及从有限候选集中选出高分项,每项评分依赖敏感数据。传统方法如报告噪声最大值(RNM)假设所有候选项敏感度相同,但现实中常存在差异。虽广义指数机制(GEM)可利用敏感度差异,但其表现不稳定,甚至可能劣于随机选择。本文研究得分分布与敏感度分布对隐私选择的影响,发现总存在利用敏感度异质性的机制优于RNM,但无单一机制始终最优。为此,提出基于得分与敏感度相关性的决策准则,并设计改进版GEM,在原机制表现差时仍保持良好性能。结合该准则的自适应机制在极化设置下显著超越GEM和修改版GEM。
原文摘要 · Abstract (English)
Differentially private (DP) selection involves choosing a high-scoring candidate from a finite candidate pool, where each score depends on a sensitive dataset. This problem arises naturally in a variety of contexts including model selection, hypothesis testing, and within many DP algorithms. Classical methods, such as Report Noisy Max (RNM), assume all candidates' scores are equally sensitive to changes in a single individual's data, but this often isn't the case. To address this, algorithms like the Generalised Exponential Mechanism (GEM) leverage variability in candidate sensitivities. However, we observe that while these algorithms can outperform RNM in some situations, they may underperform in others - they can even perform worse than random selection. In this work, we explore how the distribution of scores and sensitivities impacts DP selection mechanisms. In all settings we study, we find that there exists a mechanism that utilises heterogeneity in the candidate sensitivities that outperforms standard mechanisms like RNM. However, no single mechanism uniformly outperforms RNM. We propose using the correlation between the scores and sensitivities as the basis for deciding which DP selection mechanism to use. Further, we design a slight variant of GEM, modified GEM that generally performs well whenever GEM performs poorly. Relying on the correlation heuristic we propose combined GEM, which adaptively chooses between GEM and modified GEM and outperforms both in polarised settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。