2022/06/07 by Yuhan Liu, Liu, Yuhan, Ananda Theertha Suresh +7 · 1 citation
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2206.03008
openalex publication_date 2022/06/07 · openalex created_date 2022/06/13 · openalex updated_date 2026/07/28
We study the problem of histogram estimation under user-level differential privacy, where the goal is to preserve the privacy of all entries of any single user. We consider the heterogeneous scenario where the quantity of data can be different for each user. In this scenario, the amount of noise injected into the histogram to obtain differential privacy is proportional to the maximum user contribution, which can be amplified by few outliers. One approach to circumvent this would be to bound (or limit) the contribution of each user to the histogram. However, if users are limited to small contributions, a significant amount of data will be discarded. In this work, we propose algorithms to choose the best user contribution bound for histogram estimation under both bounded and unbounded domain settings. When the size of the domain is bounded, we propose a user contribution bounding strategy that almost achieves a two-approximation with respect to the best contribution bound in hindsight. For unbounded domain histogram estimation, we propose an algorithm that is logarithmic-approximation with respect to the best contribution bound in hindsight. This result holds without any distribution assumptions on the data. Experiments on both real and synthetic datasets verify our theoretical findings and demonstrate the effectiveness of our algorithms. We also show that clipping bias introduced by bounding user contribution may be reduced under mild distribution assumptions, which can be of independent interest.