Apple Machine Learning Research
·
指纹编码与几何相遇：私密查询发布和自适应数据分析的改进下界
💡
原文英文，约400词，阅读约需2分钟。
📝
内容提要
指纹编码是证明差分隐私下界的重要工具，适用于低准确度问题。本文提出了一种通用框架，证明了特定查询集下的下界，并展示了准确算法与差分隐私算法所需的样本复杂度，改进了已有结果。
🎯
关键要点
- 指纹编码是证明差分隐私下界的重要工具，适用于低准确度问题。
- 本文提出了一种通用框架，用于证明特定查询集下的下界。
- 该框架展示了准确算法与差分隐私算法所需的样本复杂度。
- 对于任意自适应计数查询，准确算法需要Ω(log |X| ⋅ log Q / α^3)样本。
- 该结果改进了之前已知的下界，证明了基于差分隐私的方法在此问题上是最优的。
- 对于(ε, δ)-差分隐私算法，回答计数查询的样本复杂度需要Ω(d log(1/δ) log Q / (ε α^2))。
- 该框架直接证明了这一下界，并改进了之前的结果。
- 本文还表征了在近似差分隐私下回答随机0-1查询的样本复杂度，提供了新的上下界。
➡️
