Differentially Private Assouad, Fano, and Le Cam
Jayadev Acharya Cornell University Research supported by NSF 1815893, NSF 1657471, and NSF 1846300 (CAREER). Ziteng Sun∗ Cornell University Huanyu Zhang∗ Cornell University
Abstract
Le Cam’s method, Fano’s inequality, and Assouad’s lemma are three widely used techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under central differential privacy. Our results are simple, easy to apply and we use them to establish sample complexity bounds in several estimation tasks.
中文速览
在统计估计中，证明样本复杂度下界通常依赖Le Cam方法、Fano不等式和Assouad引理这三大经典工具，但当数据需要满足差分隐私（differential privacy, DP）保护时，这些工具并不能直接使用。本文为这三种方法各自建立了差分隐私版本，核心技术思路是：利用分布之间的耦合（coupling）所诱导的期望Hamming距离来刻画隐私约束带来的额外代价——两个分布越"接近"（期望Hamming距离越小），隐私机制就越难区分它们，从而需要更多样本。将这套新工具应用于多个具体估计任务后，作者证明了离散分布在全变差距离和$\ell_2$距离下的最优样本复杂度，并为乘积分布、高斯混合分布等更复杂的分布族给出了至多差对数因子的紧下界。这项工作不仅填补了隐私统计推断理论中的基础空白，还为未来证明私有算法的最优性提供了一套系统、易用的通用框架。
原文 arXiv:2004.06830;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2004.06830v3