arXiv preprint ·
Complexity of Differentially Private Selection via Federated APIs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Cryptography & Security
Get the few papers worth your time in Cryptography & Security every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.