Summary
Selecting important data points privately in systems where data is spread out, like on many phones or computers, is usually less accurate than when all data is collected centrally. The authors show this in typical federated systems using noisy data summaries and prove it can’t be fixed without new tools. They introduce a new technique, based on an existing privacy method called Sparse Vector Technique, that greatly improves accuracy for these tasks. Their approach matches the accuracy of centralized methods under reasonable conditions and applies to multiple data analysis problems like finding frequent items or minimizing error in data estimates.
What this means in practice
- •For data privacy engineers: Improve accuracy in privacy-preserving selection tasks on distributed user data using the proposed Sparse Vector Technique queries.
- •For machine learning platform teams: Incorporate enhanced differentially private algorithms for federated model training tasks like feature selection and heavy-hitter identification.
A theory result. No direct application yet.
Authors
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou
Abstract
Differential privacy (DP) has become the standard for privacy-preserving data analysis, yet its practical implementation in federated or distributed settings often faces a significant utility gap compared to the central model. While existing frameworks, including local, shuffle, and secure aggregation models, offer vetted primitives, they can incur high error for important tasks such as selection. Our first contribution is to show that this is inherent in the aggregation model: any private selection algorithm relying on the standard noisy aggregation primitive requires $Ω(\sqrt{d}/\varepsilon)$ samples. To address this limitation, we propose adding a new primitive that implements a version of the Sparse Vector Technique (SVT) and argue that it has simple implementations under various trust models. We demonstrate its power by developing an $\varepsilon$-differentially private algorithm for the selection problem. For selection in dimension $d$, our algorithm achieves an additive error of $O\left(\frac{\log(dn)}{\varepsilon}\right)$, matching that of the central model when $n$ is polynomially bounded in $d$. Furthermore, we show that this can be done using a near-optimal expected number $O(d\log^*d)$ of SVT queries. Together with existing lower bounds for the shuffle model, this result establishes an exponential separation between the SVT model and shuffle or aggregation-based models. We demonstrate the model's broad applicability to diverse tasks such as $F_p$ loss minimization, heavy-hitter identification, and sparse mean estimation.