Improving Frequency Estimation under Local Differential Privacy
This work addresses the challenge of balancing privacy and utility in data aggregation for users who distrust aggregators, representing a strong specific gain in the field.
The paper tackled the problem of frequency estimation under Local Differential Privacy by improving the tradeoff bounds between privacy and utility using information-theoretical methods, achieving new bounds that are attainable for binary inputs and leading to estimators that outperform state-of-the-art methods in experiments.
Local Differential Privacy protocols are stochastic protocols used in data aggregation when individual users do not trust the data aggregator with their private data. In such protocols there is a fundamental tradeoff between user privacy and aggregator utility. In the setting of frequency estimation, established bounds on this tradeoff are either nonquantitative, or far from what is known to be attainable. In this paper, we use information-theoretical methods to significantly improve established bounds. We also show that the new bounds are attainable for binary inputs. Furthermore, our methods lead to improved frequency estimators, which we experimentally show to outperform state-of-the-art methods.