Noisy aggregation cannot match central DP for private selection
Original title: Complexity of Differentially Private Selection via Federated APIs
A proposed Sparse Vector Technique primitive reaches central-model error with O(d log-star d) expected queries.
The paper argues that private selection built only on standard noisy aggregation inherently needs Ω(√d/ε) samples. It proposes a Sparse Vector Technique primitive with simple implementations under several trust models and an ε-differentially private selection algorithm whose additive error is O(log(dn)/ε), matching the central model when n is polynomially bounded in d. With existing shuffle-model lower bounds, the authors claim an exponential separation from shuffle and aggregation models, and apply the approach to Fp loss minimization, heavy hitters, and sparse mean estimation.
- Selection via noisy aggregation alone needs Ω(√d/ε) samples.
- The SVT algorithm’s additive error is O(log(dn)/ε).
- Expected SVT queries are O(d log-star d), called near-optimal.
- Tasks include Fp loss, heavy hitters, and sparse means.
From the original article
1 min read at arxiv.orgDifferential 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.
By Hilal Asi · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.