Abstract
Differentially Private Stochastic Gradient Descent (DP-SGD) forms afundamental building block in many applications for learning over sensitivedata. Two standard approaches, privacy amplification by subsampling, andprivacy amplification by shuffling, permit adding lower noise in DP-SGD thanvia na\"{\i}ve schemes. A key assumption in both these approaches is that theelements in the data set can be uniformly sampled, or be uniformly permuted --constraints that may become prohibitive when the data is processed in adecentralized or distributed fashion. In this paper, we focus on conductingiterative methods like DP-SGD in the setting of federated learning (FL) whereinthe data is distributed among many devices (clients). Our main contribution isthe \emph{random check-in} distributed protocol, which crucially relies only onrandomized participation decisions made locally and independently by eachclient. It has privacy/accuracy trade-offs similar to privacy amplification bysubsampling/shuffling. However, our method does not require server-initiatedcommunication, or even knowledge of the population size. To our knowledge, thisis the first privacy amplification tailored for a distributed learningframework, and it may have broader applicability beyond FL. Along the way, weextend privacy amplification by shuffling to incorporate $(\epsilon,\delta)$-DPlocal randomizers, and exponentially improve its guarantees. In practicalregimes, this improvement allows for similar privacy and utility using datafrom an order of magnitude fewer users.