Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
复制标题
估计本地隐私和通信约束下的稀疏离散分布
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ziteng Sun
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Yuhan Liu;Ziteng Sun
我们考虑的任务估计稀疏离散分布下的局部差分隐私和通信约束。在局部隐私约束下，我们提出了一个样本最优的私人硬币方案，每个用户只发送一个比特的消息。对于通信约束，我们提出了一个基于随机散列函数的公共硬币方案，我们证明了它在对数因子下是最优的。我们的结果表明，样本复杂度仅与环境维度呈对数关系，因此在稀疏性假设下显着提高了样本复杂度。我们的下限是基于最近提出的卡方收缩方法。
We consider the task of estimating sparse discrete distributions under local differential privacy and communication constraints. Under local privacy constraints, we present a sample-optimal private-coin scheme that only sends a one-bit message per user. For communication constraints, we present a public-coin scheme based on random hashing functions, which we prove is optimal up to logarithmic factors. Our results show that the sample complexity only depends logarithmically on the ambient dimension, thus providing significant improvement in sample complexity under sparsity assumptions. Our lower bounds are based on a recently proposed chi-squared contraction method.
登录
查看更多内容
通过 Fisher 信息得出通信约束下学习分布的下限
影响因子：
6
作者：
Leighton Pate Barnes;Yanjun Han;Ayfer Ozgur
通讯作者：
Ayfer Ozgur
影响因子：
2.5
作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi
通讯作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi
影响因子：
2.5
作者：
Wang, Di;Xu, Jinhui
通讯作者：
Xu, Jinhui
本地差异隐私下的 Fisher 信息
DOI：
10.1109/jsait.2020.3039461
发表时间：
2020
期刊：
IEEE Journal on Selected Areas in Information Theory
影响因子：
--
作者：
Barnes, Leighton Pate;Chen, Wei-Ning;Ozgur, Ayfer
通讯作者：
Ozgur, Ayfer