cpSGD: Communication-efficient and differentially-private distributed SGD

By Naman Agarwal, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, H. Brendan McMahan. 2018

548 citations recorded by the source corpus.

Distributed stochastic gradient descent is an important subroutine in distributed learning. A setting of particular interest is when the clients are mobile devices, where two important concerns are communication efficiency and the privacy of the clients. Several recent works have focused on reducing the communication cost or introducing privacy guarantees, but none of the proposed communication efficient methods are known to be privacy preserving and none of the known privacy mechanisms are known to be communication efficient. To this end, we study algorithms that achieve both communication efficiency and differential privacy. For $d$ variables and $n \approx d$ clients, the proposed method uses $O(\log \log(nd))$ bits of communication per client per coordinate and ensures constant privacy. We also extend and improve previous analysis of the \emph{Binomial mechanism} showing that it achieves nearly the same utility as the Gaussian mechanism, while requiring fewer representation bits, which can be of independent interest.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, Federated & Distributed Learning, 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 Computer Networks and Communications

In Optimization & Training

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “There is some work on adding discrete noise [13], but there is no notion whether such methods are optimal.”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, background): “The closest work to ours is cpSGD (Agarwal et al., 2018), which also serves as an inspiration for much of our work. cpSGD uses a distributed version of the binomial mechanism (Dwork et al., 2006a) to achieve distributed DP.”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “To analyze the convergence rate of Algorithm 3, the next lemma(which originates from [59] but we use a version adapted from [18]) builds the connection between distributed SGD and mean estimation.”
Personalized Federated Learning: A Meta-Learning Approach (2020, background): “Several works have studied the problem of preserving privacy in federated learning (Duchi et al., 2014; McMahan et al., 2017b; Agarwal et al., 2018; Zhu et al., 2019).”
Secure Federated Submodel Learning (2019, methodology): “only suffices for the recommendation models used in Alibaba but also can easily degenerate to a widely used vector-based representation [18], [30], by setting the number of columns d to 1.”
Federated Evaluation of On-device Personalization (2019, background): “, 2017) and differential privacy (McMahan et al., 2018; Agarwal et al., 2018; Abadi et al., 2016b).”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “…with a dependency graph (Woodworth et al., 2018b), devising eﬃcient distributed optimization methods beneﬁting from diﬀerential privacy guarantees (Agarwal et al., 2018), stochastic optimization solutions for the agnostic formulation (Mohri et al., 2019), and incorporating cryptographic…”
Differentially Private Meta-Learning (2019, methodology): “Agarwal et al. (2018) also consider what is effectively a local DP guarantee but leverages SMC to reduce the amount of randomization needed per task-owner.”
AdaCliP: Adaptive Clipping for Private SGD (2019, background): “Even though noisy SGD usually provides global differential privacy, recent works have shown that they can be combined with cryptographic homomorphic encryption techniques to provide stronger privacy guarantees [30, 31].”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “Some extension of communication efficient distributed learning, such as differentially private optimization (Agarwal et al., 2018), optimization on manifolds (Saparbayeva et al.”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Current works that aim to improve the privacy of federated learning typically build upon previous classical cryptographic protocols such as SMC [10, 42] and differential privacy [3, 8, 41, 76].”