Algorithms for bounding contribution for histogram estimation under user-level privacy
This work addresses privacy-preserving data analysis for scenarios with varying user data quantities, offering practical solutions to reduce noise and data loss, though it is incremental in improving existing bounding strategies.
The paper tackles the problem of histogram estimation under user-level differential privacy in heterogeneous data scenarios, where noise injection is proportional to maximum user contributions, by proposing algorithms to choose optimal user contribution bounds that achieve two-approximation for bounded domains and logarithmic-approximation for unbounded domains without distribution assumptions, with experiments validating effectiveness.
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.