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