Privacy Amplification via Random Check-Ins

By Borja Balle, Peter Kairouz, H. Brendan McMahan, Om Thakkar, Abhradeep Thakurta. 2020

81 citations recorded by the source corpus.

Differentially Private Stochastic Gradient Descent (DP-SGD) forms a fundamental building block in many applications for learning over sensitive data. Two standard approaches, privacy amplification by subsampling, and privacy amplification by shuffling, permit adding lower noise in DP-SGD than via na\"ive schemes. A key assumption in both these approaches is that the elements in the data set can be uniformly sampled, or be uniformly permuted -- constraints that may become prohibitive when the data is processed in a decentralized or distributed fashion. In this paper, we focus on conducting iterative methods like DP-SGD in the setting of federated learning (FL) wherein the data is distributed among many devices (clients). Our main contribution is the \emph{random check-in} distributed protocol, which crucially relies only on randomized participation decisions made locally and independently by each client. It has privacy/accuracy trade-offs similar to privacy amplification by subsampling/shuffling. However, our method does not require server-initiated communication, or even knowledge of the population size. To our knowledge, this is the first privacy amplification tailored for a distributed learning framework, and it may have broader applicability beyond FL. Along the way, we extend privacy amplification by shuffling to incorporate $(\epsilon,\delta)$-DP local randomizers, and exponentially improve its guarantees. In practical regimes, this improvement allows for similar privacy and utility using data from an order of magnitude fewer users.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “[5] Borja Balle, Peter Kairouz, Brendan McMahan, Om Dipakbhai Thakkar, and Abhradeep Thakurta.”
Privacy Amplification by Decentralization (2020, background): “For instance, if we assume that the availability of a user at each time step follows the same Bernoulli distribution for every user, we can still build a random walk with the desired distribution, similarly to what is done in another context by Balle et al. (2020).”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “Amplification by subsampling, as one of the key techniques for achieving strong privacy guarantees, is very challenging in current cross-device federated learning systems (Balle et al., 2020).”