论文标题
根据本地隐私和通信约束估算稀疏离散分布
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
论文作者
论文摘要
我们考虑在当地差异隐私（LDP）和通信约束下估算稀疏离散分布的问题。我们表征了在LDP约束下稀疏估计的样本复杂性，最高为恒定因素，并且在通信约束下的样本复杂性达到对数因子。我们在最不发达国家下的上限是基于Hadamard响应，这是一种私人硬币方案，每个用户只需要一点点通信。在沟通限制下，我们提出了基于随机哈希功能的公共硬币计划。我们紧密的下限是基于最近提出的卡平方收缩方法。
We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints, we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on the recently proposed method of chi squared contractions.
