Infinitely Divisible Noise in the Low Privacy Regime

Abstract

Federated learning, in which training data is distributed among users and never shared, has emerged as a popular approach to privacy-preserving machine learning. Cryptographic techniques such as secure aggregation are used to aggregate contributions, like a model update, from all users. A robust technique for making such aggregates differentially private is to exploit infinite divisibility of the Laplace distribution, namely, that a Laplace distribution can be expressed as a sum of i.i.d. noise shares from a Gamma distribution, one share added by each user. However, Laplace noise is known to have suboptimal error in the low privacy regime for $\epsilon$-differential privacy, where $\epsilon >1$ is a large constant. In this paper we present the first infinitely divisible noise distribution for real-valued data that achieves $\epsilon$-differential privacy and has expected error that decreases exponentially with $\epsilon$.

arXiv commentTo appear at International Conference on Algorithmic Learning Theory (ALT), 2022

References in corpus (4)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
• Optimality of the Laplace Mechanism in Differential Privacy
• Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message