Search papers, labs, and topics across Lattice.
This paper proves that a frequency estimator with a symmetric and extremal configuration and optimized constant support size achieves maximum precision under local differential privacy (LDP). It derives a lower bound on the communication cost for such an optimal estimator, showing it can be as low as $\log_2(\frac{d(d-1)}{2}+1)$ for dictionary size $d$, and provides an algorithm to generate it. The authors also introduce a modified Count-Mean Sketch, demonstrating near-optimal performance with sufficiently large dictionary sizes, and provide practical guidelines for estimator selection based on theoretical and empirical comparisons.
Forget complex mechanisms: a simple frequency estimator with symmetric configuration and optimized support size provably achieves optimal precision under local differential privacy, slashing communication costs.
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 $\epsilon = 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.
