# Apple — Complexity of Differentially Private Selection via Federated APIs

- Company: Apple (apple.com)
- Announced: 2026-11-10
- Category: research-paper
- Coverage: not counted
- Announcement: yes
- Group: announcements
- Source: https://machinelearning.apple.com/research/differentially-private-selection
- Record: https://forck.live/items/38795-complexity-of-differentially-private-selection-via-federated-apis
- Subject: Machine Learning Research

Apple researchers show that private selection under standard noisy aggregation primitives inherently needs Ω(√d/ε) samples, then propose a new Sparse Vector Technique primitive to close the gap. The paper argues the limitation is inherent to the aggregation model rather than an artifact of particular algorithms. Adding an SVT primitive yields an ε-differentially private selection algorithm with additive error O(log(dn)/ε), matching the central model when n is polynomially bounded in d. The authors say the algorithm uses a near-optimal expected O(d log* d) SVT queries and that, with existing shuffle-model lower bounds, this establishes an exponential separation between the SVT model and shuffle or aggregation-based models. They also demonstrate the model's applicability to F_p loss minimization, heavy-hitter identification and sparse mean estimation.

## Evidence

Verbatim from https://machinelearning.apple.com/research/differentially-private-selection:

> Authors Hilal Asi, Vitaly Feldman, Jelani Nelson†, Huy L. Nguyen‡, Kunal Talwar, Samson Zhou§
> 
> 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) 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.

---

Record: https://forck.live/items/38795-complexity-of-differentially-private-selection-via-federated-apis
Catalogue: https://forck.live/llms.txt
Current issue: https://forck.live/feed.md
