Strict Optimality of Frequency Estimation Under Local Differential Privacy
This work provides a theoretically optimal solution for frequency estimation in privacy-preserving data analysis, which is incremental as it builds on existing LDP methods to establish strict optimality and practical guidelines.
The paper tackles the problem of achieving maximum precision in frequency estimation under local differential privacy by proving that a symmetric and extremal configuration estimator with optimized support size is strictly optimal, and it demonstrates that the communication cost can be as low as log₂(d(d-1)/2 + 1) for dictionary size d, with empirical results matching theoretical predictions.
This paper establishes the strict optimality in precision for frequency estimation under local differential privacy (LDP). We prove that a frequency estimator with a symmetric and extremal configuration, and a constant support size equal to an optimized value, is sufficient to achieve maximum precision. Furthermore, we derive that the communication cost of such an optimal estimator can be as low as $\log_2(\frac{d(d-1)}{2}+1)$, where $d$ denotes the dictionary size, and propose an algorithm to generate this optimal estimator. In addition, we introduce a modified Count-Mean Sketch and demonstrate that it is practically indistinguishable from theoretical optimality with a sufficiently large dictionary size (e.g., $d=100$ for a privacy factor of $ε= 1$). We compare existing methods with our proposed optimal estimator to provide selection guidelines for practical deployment. Finally, the performance of these estimators is evaluated experimentally, showing that the empirical results are consistent with our theoretical derivations.