  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\"{\i}ve 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.
