Privacy Amplification via Random Check-Ins

  • 2020-07-30 16:26:38
  • Borja Balle, Peter Kairouz, H. Brendan McMahan, Om Thakkar, Abhradeep Thakurta
  • 0

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.

 

Quick Read (beta)

loading the full paper ...