Complexity of Differentially Private Selection via Federated APIs
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou
Pairs a strong adaptive lower bound for aggregation APIs with a simple, near-optimal SVT-based remedy, giving a clear API-level separation; impact is limited by theory-only evaluation and model-specific assumptions.
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 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 , our algorithm achieves an additive error of , matching that of the central model when is polynomially bounded in . Furthermore, we show that this can be done using a near-optimal expected number 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 loss minimization, heavy-hitter identification, and sparse mean estimation.
AI Impact Assessments
(1 model)Core Contribution
The paper studies which primitives a federated or distributed DP "API" needs in order to support private selection with central-model accuracy. It makes three contributions.
1. Lower bound for aggregation APIs. Any adaptive algorithm that reaches its privacy guarantee by composing Gaussian noisy-aggregation queries needs n = Ω(√(d/ρ)) samples, i.e. Ω(√d/ε), for sparse Boolean distinguishing and hence selection. Prior lower bounds applied only to local or shuffle models, to non-interactive or one-round protocols, or to restricted settings. The proof simulates the aggregation oracle with a local nρ-zCDP protocol (distributed noise addition). It then applies a Braverman et al./Jayram cut-and-paste information-complexity argument, and it avoids the extra log d factor of the Duchi–Rogers reduction.
2. A new primitive. An SVT (AboveThreshold) API for additive queries, with a stateful stream whose privacy cost is independent of the number of "No" answers. The paper argues it is simple to implement under TEE, two-server/Prio, and MPC trust models, because the secure part is a scalar comparison and the argmax stays outside the cryptographic boundary.
3. Selection algorithms in the SVT model.
- Linear scan: optimal error but O(dn) queries.
- Geometric-budget binary search: O(log(dn)/ε) error with O(d log n) queries.
- Sampling-and-filtering: expected O(d log* n + log³ n) queries with ε-pure DP and error O(log(dn)/ε).
Together with known shuffle lower bounds, this gives an exponential separation (√d versus log d) between SVT and aggregation/shuffle models. Applications include F_p losses, heavy hitters with categories, sparse mean estimation, and MWEM synthetic data.
Methodological Rigor
The theory is largely sound and carefully built. The lower-bound reduction is clean, and the appendix proof follows an established template (Jayram's cut-and-paste inequality, a mutual-information chain rule, KL stability). The geometric budget allocation and the induction lemmas (6.4, 6.5, 6.10, 6.11) are straightforward and checkable. The privacy proofs are by basic composition, with parameters fixed in advance so that privacy holds unconditionally. Accuracy is analysed on a good event, which is standard.
Limitations of the lower bound:
The paper is purely theoretical, with no experiments. The SVT primitive's practicality (latency from sequential adaptive queries, a Θ(d) round count, TEE or MPC overhead) is argued rather than demonstrated. The log* algorithm has large constants (e.g. 776, 2^64 thresholds), so it is of theoretical interest more than a practical recipe. The O(d) adaptive rounds could be costly in federated deployments, a point the paper does not address.
Potential Impact
Timeliness & Relevance
Private federated analytics and learning are deployed at scale, and private selection (top-k, heavy hitters, histogram and marginal queries, synthetic data) is a recognised bottleneck in the federated setting. Trust models (TEE, Prio-style two-server) are increasingly in production. The paper's argument fits current trends and the ongoing open question of how to get central-DP utility without trusting a central curator.
Strengths
Weaknesses
Overall
This is a solid theory-meets-systems paper from an expert group. It is likely to be well cited in the DP and federated-analytics communities, and may influence API design. It is not a paradigm-shifting result, and its core techniques (SVT, binary search, information-complexity lower bounds) are known, but their combination and the framing are meaningfully new.
Generated Oct 30, 2026
Comparison History (0)
Pairs a strong adaptive lower bound for aggregation APIs with a simple, near-optimal SVT-based remedy, giving a clear API-level separation; impact is limited by theory-only evaluation and model-specific assumptions.