Complexity of Differentially Private Selection via Federated APIs
AuthorsHilal Asi, Vitaly Feldman, Jelani Nelson†, Huy L. Nguyen‡, Kunal Talwar, Samson Zhou§
Complexity of Differentially Private Selection via Federated APIs
AuthorsHilal 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 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.
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…
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.