cpSGD: Communication-efficient and differentially-private distributed SGD
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 ⇡ d clients, the proposed method uses O(log log(nd)) bits of communication per client per coordinate and ensures constant privacy. We also improve previous analysis of the 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.
--Post rebuttal:  The authors' answered my questions satisfactorily, and I raised my score by 1 to 8. I think this is a strong paper. I look forward to reading an updated paper that improves some of the writing and presentation.  Summary: This paper seeks to combine two aspects of distributed optimization: (i) quantization to reduce the total communication cost and (ii) privacy through an application of differential privacy. The authors propose to have each of the worker nodes add noise to its gradients before sending the result to the central aggregator node.   The challenge in this case is that adding Gaussian noise, as is usual for differential privacy mechanisms, means that the resulting gradients have infinite resolution, so they cannot easily be compressed. Instead, the authors use adding a binomial RV. They analyze this particular differential privacy mechanism. Finally, since the aggregation step requires the central node to estimate the mean, the authors study the error of distributed mean estimation.  This is a heavy theory paper. As far as I know, this is the first result of this type, which could be very useful in the federated optimization setting. The results are strong and the theory is a welcome building block for future works. The paper isn't particularly written or easy to understand, with many un-interpreted expressions, but this doesn't take away from the overall contribution.   Major comments:  - This is a theory paper, so it's important to explain each of the theoretical results. The huge formula in (6) in Theorem 1 isn't very interpretable as it stands. Which one of those three terms is typically dominant? Which of the three sensitivity parameters are typically important for problems of interest? Under what conditions is the resulting epsilon not meaningful (i.e., super huge)?   - The role of the scaling term s is also a little bit unclear. It must be sufficiently small (or else the noise magnitudes could be huge, huge enough to be past the representation limit for floats), but if it's too small, the noise may not be able to be distinguishable by floats either. Is there a heuristic rule for getting the right s?  - The paper's writing is sometimes pretty rough. Please add some signposting so we know what to expect and in which section.   Minor comments:  - Line 20: it's not necessarily true that "without a central server, each client saves a global model, broadcasts the gradient to all other clients". It's fine to have each client send its gradient to a potentially small neighborhood of clients (and receive a gradient from each of them). This is the standard setting for decentralized GD and related algorithms, which don't require a complete graph for the topology. There is a whole literature that shows how the graph topology impacts convergence, etc. See Yuan, Lin, and Yin, "On the Convergence of Decentralized Gradient Descent" for a discussion.  - What's the reason why you want to use cases other than p=1/2 for the binomial mechanism?  - One of the listed improvements is that N >= 8 log (2/delta)/epsilon^2 samples is enough... where does this come out?