Skip to content
AI News HubLIVE
Original source2 min read

Complexity of Differentially Private Selection via Federated APIs

Summary

Researchers show that private selection built on the standard noisy aggregation primitive inherently needs Ω(√d/ε) samples, and propose a new SVT-based primitive that yields an O(log(dn)/ε) additive-error selection algorithm, establishing an exponential separation from shuffle and aggregation models.

Complexity of Differentially Private Selection via Federated APIs
Report an error

The correction channel is not available yet. You can copy the article reference below for later.

Correction instructions
Read article

content type paperpublished November 2026

Complexity of Differentially Private Selection via Federated APIs

AuthorsHilal Asi, Vitaly Feldman, Jelani Nelson†, Huy L. Nguyen‡, Kunal Talwar, Samson Zhou§

View publication

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 Ω(d/ϵ)Ω(\sqrt{d} / \epsilon)Ω(d​/ϵ) 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 εεε-differentially private algorithm for the selection problem. For selection in dimension ddd, our algorithm achieves an additive error of O(log⁡(dn)ε)O\left(\frac{\log(dn)}{\varepsilon}\right)O(εlog(dn)​), matching that of the central model when nnn is polynomially bounded in ddd. Furthermore, we show that this can be done using a near-optimal expected number O(dlog⁡∗d)O(d \log^* d)O(dlog∗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 FpF_pFp​ loss minimization, heavy-hitter identification, and sparse mean estimation.

† Anthropic; work done while at UC Berkeley

‡ Northeastern

§ Texas A&M University

Samplable Anonymous Aggregation for Private Federated Data Analytics

July 18, 2024research area Privacy, research area Tools, Platforms, Frameworks

We revisit the problem of designing scalable protocols for private statistics and private federated learning when each device holds its private data. Locally differentially private algorithms require little trust but are (provably) limited in their utility. Centrally differentially private algorithms can allow significantly better utility but require a trusted curator. This gap has led to significant interest in the design and implementation of…

Read more

Apple Privacy-Preserving Machine Learning Workshop 2022

June 29, 2022research area General

Earlier this year, Apple hosted the Privacy-Preserving Machine Learning (PPML) workshop. This virtual event brought Apple and members of the academic research communities together to discuss the state of the art in the field of privacy-preserving machine learning through a series of talks and discussions over two days.

Read more

Key points and analysis

Article intelligence

ResearchersAdvanced

Key points

  • Any private selection algorithm relying on standard noisy aggregation requires Ω(√d/ε) samples, a limitation inherent to the aggregation model.
  • A new primitive implementing a version of the Sparse Vector Technique is proposed and shown to have simple realizations under various trust models.
  • The resulting ε-differentially private selection algorithm attains O(log(dn)/ε) additive error, matching the central model when n is polynomially bounded in d, using a near-optimal expected O(d log* d) SVT queries.
  • Combined with existing shuffle-model lower bounds, this gives an exponential separation between the SVT model and shuffle or aggregation-based models, with applications to Fp loss minimization, heavy-hitter identification, and sparse mean estimation.

Highlights and analysis are generated automatically and may contain errors. Check the original source.