证明了私有在线学习在自适应攻击下存在根本性局限。
The Limits of Differential Privacy in Online Learning
- 区分纯差分隐私与近似差分隐私的在线学习能力边界
- 任何私有在线学习算法对几乎所有假设类都需犯无穷次错
- 适合研究隐私计算理论或在线学习的学者参考
差分隐私（DP）是一种限制算法在敏感数据上运行时隐私泄露的形式化定义，其中隐私-效用权衡是私有数据分析的核心问题。本文研究在线学习算法中差分隐私的根本极限，揭示三类约束的区别：无DP、纯DP和近似DP。首先，我们构造了一个在近似DP下可在线学习但纯DP下不可在线学习的假设类，该结果表明面对自适应对手时必须采用近似差分隐私。随后，我们证明任何私有在线学习者对于几乎所有的假设类都必须犯无限次错误。这本质上推广了先前结果，显示出私有与非私有设置之间存在显著差异——因为在无隐私要求时，只要假设类可在线学习，总能实现有限错误界。
原文摘要 · Abstract (English)
Differential privacy (DP) is a formal notion that restricts the privacy leakage of an algorithm when running on sensitive data, in which privacy-utility trade-off is one of the central problems in private data analysis. In this work, we investigate the fundamental limits of differential privacy in online learning algorithms and present evidence that separates three types of constraints: no DP, pure DP, and approximate DP. We first describe a hypothesis class that is online learnable under approximate DP but not online learnable under pure DP under the adaptive adversarial setting. This indicates that approximate DP must be adopted when dealing with adaptive adversaries. We then prove that any private online learner must make an infinite number of mistakes for almost all hypothesis classes. This essentially generalizes previous results and shows a strong separation between private and non-private settings since a finite mistake bound is always attainable (as long as the class is online learnable) when there is no privacy requirement.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。