Compressive Privatization: Sparse Distribution Estimation under Locally Differentially Privacy
Compressive Privatization: Sparse Distribution Estimation under Locally Differentially Privacy
复制标题
压缩私有化：局部差分隐私下的稀疏分布估计
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sha Ying
中科院分区：
文献类型：
--
作者：
Zhongzheng Xiong;Zengfeng Huang;Xiaojun Mao;Jian Wang;Sha Ying
研究了局部微分隐私下的离散分布估计问题。分布估计是最基本的估计问题之一，在非私有和私有环境下都得到了广泛的研究。在局部模型中，已知具有可证明的最优样本复杂度的私有机制。然而，它们只有在最坏情况下才是最优的；它们的样本复杂度与整个宇宙的大小成正比，这在实践中可能是巨大的（例如，所有IP地址）。我们表明，只要目标分布是稀疏的或近似稀疏的（例如，高度倾斜），所需的样本数量就可以显著减少。我们的新机制的样本复杂性以目标分布的稀疏性为特征，并且仅弱依赖于宇宙的大小。我们的机制同时实现了私有化和降维，并且样本复杂度只依赖于降维。然后使用压缩感知工具恢复原始分布。为了补充我们的理论结果，我们进行了实验研究，实验结果清楚地证明了我们的方法的优势，并证实了我们的理论发现。
We consider the problem of discrete distribution estimation under locally differential privacy. Distribution estimation is one of the most fundamental estimation problems, which is widely studied in both non-private and private settings. In the local model, private mechanisms with provably optimal sample complexity are known. However, they are optimal only in the worst-case sense; their sample complexity is proportional to the size of the entire universe, which could be huge in practice (e.g., all IP addresses). We show that as long as the target distribution is sparse or approximately sparse (e.g., highly skewed), the number of samples needed could be significantly reduced. The sample complexity of our new mechanism is characterized by the sparsity of the target distribution and only weakly depends on the size the universe. Our mechanism does privatization and dimensionality reduction simultaneously, and the sample complexity will only depend on the reduced dimensionality. The original distribution is then recovered using tools from compressive sensing. To complement our theoretical results, we conduct experimental studies, the results of which clearly demonstrate the advantages of our method and confirm our theoretical findings.