Frequency Estimation in the Shuffle Model with Almost a Single Message
This work addresses privacy-preserving data analysis for large-scale distributed systems, offering near-optimal efficiency and accuracy improvements over prior methods.
The paper tackles the frequency estimation problem in the shuffle model of differential privacy, achieving error close to central-DP accuracy with almost a single message per user, and also solves the 1-sparse vector summation problem optimally in high dimensions.
We present a protocol in the shuffle model of differential privacy (DP) for the \textit{frequency estimation} problem that achieves error $ω(1)\cdot O(\log n)$, almost matching the central-DP accuracy, with $1+o(1)$ messages per user. This exhibits a sharp transition phenomenon, as there is a lower bound of $Ω(n^{1/4})$ if each user is allowed to send only one message. Previously, such a result is only known when the domain size $B$ is $o(n)$. For a large domain, we also need an efficient method to identify the \textit{heavy hitters} (i.e., elements that are frequent enough). For this purpose, we design a shuffle-DP protocol that uses $o(1)$ messages per user and can identify all heavy hitters in time polylogarithmic in $B$. Finally, by combining our frequency estimation and the heavy hitter detection protocols, we show how to solve the $B$-dimensional \textit{1-sparse vector summation} problem in the high-dimensional setting $B=Ω(n)$, achieving the optimal central-DP MSE $\tilde O(n)$ with $1+o(1)$ messages per user. In addition to error and message number, our protocols improve in terms of message size and running time as well. They are also very easy to implement. The experimental results demonstrate order-of-magnitude improvement over prior work.