Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing
Ryan Rogers Department of Applied Mathematics and Computational Science, University of Pennsylvania. Email: Supported in part by a grant from the Sloan foundation and NSF grant CNS-1253345 Aaron Roth Department of Computer and Information Sciences, University of Pennsylvania. Email: Supported in part by a grant from the Sloan foundation, a Google Faculty Research Award, and NSF grants CNS-1513694 and CNS-1253345. Adam Smith Computer Science and Engineering Department, The Pennsylvania State University. Email: Supported in part by a grant from the Sloan foundation, a Google Faculty Research Award, and NSF grant IIS-1447700. Om Thakkar
Abstract
In this paper, we initiate a principled study of how the generalization properties of approximate differential privacy can be used to perform adaptive hypothesis testing, while giving statistically valid $p$ -value corrections. We do this by observing that the guarantees of algorithms with bounded approximate max-information are sufficient to correct the $p$ -values of adaptively chosen hypotheses, and then by proving that algorithms that satisfy $(\epsilon,\delta)$ -differential privacy have bounded approximate max-information when their inputs are drawn from a product distribution.
中文速览
自适应数据分析中，研究者反复用同一份数据先探索、再验证，会导致p值严重失真、虚假发现率飙升。本文证明了满足近似差分隐私（approximate differential privacy，(ε,δ)-DP）的算法，在数据来自乘积分布时，具有有界的近似最大信息量（approximate max-information），从而可以为自适应选出的假设检验提供统计上有效的p值修正函数。这一结论将此前仅对纯差分隐私（(ε,0)-DP）成立的联系推广到了实践中更常用、更高效的近似差分隐私框架，意味着在相同隐私预算下可以进行平方量级更多的自适应检验而无需放大修正因子。作者还给出了一个下界，说明近似差分隐私与最大信息量的联系本质上依赖于乘积分布假设，揭示了它与纯差分隐私在组合性质上的根本差异，为自适应假设检验的理论基础提供了更完整的刻画。
原文 arXiv:1604.03924;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1604.03924v2