Shuffled Check-in: Privacy Amplification towards Practical Distributed Learning
Recent studies of distributed computation with formal privacy guarantees,
such as differentially private (DP) federated learning, leverage random
sampling of clients in each round (privacy amplification by subsampling) to
achieve satisfactory levels of privacy. Achieving this however requires strong
assumptions which may not hold in practice, including precise and uniform
subsampling of clients, and a highly trusted aggregator to process clients'
data. In this paper, we explore a more practical protocol, shuffled check-in,
to resolve the aforementioned issues. The protocol relies on client making
independent and random decision to participate in the computation, freeing the
requirement of server-initiated subsampling, and enabling robust modelling of
client dropouts. Moreover, a weaker trust model known as the shuffle model is
employed instead of using a trusted aggregator. To this end, we introduce new
tools to characterize the R\'enyi differential privacy (RDP) of shuffled
check-in. We show that our new techniques improve at least three times in
privacy guarantee over those using approximate DP's strong composition at
various parameter regimes. Furthermore, we provide a numerical approach to
track the privacy of generic shuffled check-in mechanism including distributed
stochastic gradient descent (SGD) with Gaussian mechanism. To the best of our
knowledge, this is also the first evaluation of Gaussian mechanism within the
local/shuffle model under the distributed setting in the literature, which can
be of independent interest.