Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposed a differentially private training algorithm for federated learning. The target is to achieve communication reduction while keeping differential privacy during training. The proposed algorithm adds a few new components to SGD, including a privacy mechanism, a random rotation to reduce quantization error, a gradient coordinate selection mechanism to reduce communication/computation. Experiments with high \epsilon local differentially privacy guarantees are conducted. The proposed algorithm outperforms a baseline algorithm.

Overall the paper is well-organized and easy to follow. My main concern is that the paper seems incremental and the comparison with existing works is not sufficient. 

1. Out of the three components added to SGD, the random rotation scheme is from existing works and it is not the contribution of this paper. The gradient coordinate selection mechanism is just uniformly picking coordinates which quite straightforward. The main contribution seems to be the privacy mechanism which is an extension of the mechanism in Bhowmick et al., 2018 and it is not technically difficult to extend it. 

2. The experiments only compared with one baseline algorithm in literature. However, there are quite a few works on communication-efficient privacy-preserving distributed training. For example, cpSGD in Agarwal et al., 2018 is a closely related algorithm but it is not compared in experiments. If a comparison is not applicable, it is better to add more discussion on comparison with existing works to highlight the difference and contribution of this work.






review_title: A new algorithm for differentially private federated learning

final_score: rating: 3: Clear rejection
review_content: Federated learning is a distributed learning paradigm where models are learned from decentralized data sources. The paper proposes to train machine learning models with communication-efficient differentially private approaches.
I have several concerns about the work including the experimental setup.

Experimental setup:
Experiments use a privacy budget of epsilon = 400 for LeNet Models and 2000 for ResNet models. Note that differential privacy algorithms ensure that the probabilities differ by at most e^{epsilon} with high probability. This means that the probabilities can be off by  e^{400} ~ 10^170, which is higher than the number of particles in the observed universe.
The paper is very hard to accept with the current set of experimental results.

Other:
a. R_s is not defined in Section 1.2.
b. PrivQuant seems to be a very interesting algorithm, however very little intuition is provided. It would be good to describe why this algorithm is preferred over others. 
c. In Section 2.2, authors argue that one can get better results if the gradients are sparse. However note that for this to work, even the non-zero coordinates have to be relayed with differential privacy, which can add to the total privacy cost.
d. Step 14 in the algorithm: the role of r is not clear and needs to be explained more.
review_title: Federated learning with local differential privacy

final_score: rating: 6: Marginally above acceptance threshold
review_content: ==== Overview====

This paper studies a low communication algorithm for multivariate mean estimation in the federated learning setting with differentially private communication. The algorithm uses quantization and dimension subsampling (only reporting some coordinates of the vector) to lower communication and randomized rotation (essentially applying a random orthogonal matrix) to reduce quantization error. They then apply this algorithm to ERM, using it as a subroutine in SGD. They experimentally explore the behavior of their algorithm on a number of benchmark datasets. They consider how the performance changes as they vary epsilon, the discretization parameter and the number of epochs (in SGD). 

==== Comments ==

I thought PrivQuant was an interesting algorithm. I thought the use of randomized rounding was nice, although it was also used in Bhowmick et. al ’18. It wasn’t clear to me to what degree this algorithm was an extension of the algorithm in that paper, but I thought it was clever. The series of improvements made seem to all have individually appeared in the literature before (I wasn’t familiar with the random rotation but the authors indicate that this is not new to this work), but the combination of them for solving this problem seems to be unique.

The paper does a good job of placing itself in the context of prior work. I would have liked more explanation of how vqSGD compares?

The experiments are well designed. Hyper-parameter tuning is often an issue for algorithms like this and the authors clearly state how they tune hyper-parameters heuristically. They compare their algorithm to an algorithm from the literature, which has low communication via performing dimension subsampling, at a variety of epoch and privacy levels. They always outperform the other algorithm. It wasn’t clear to me if the algorithm they compare against was the current state of the art. 

The discussion of Bhowmick et. Al ’18 was bit confusing and didn’t seem very self-contained. The authors use this paper as justification for the large local epsilon values used in the experiments. They also say that they will develop algorithms that protect against inference and reconstruction attacks. This is fine, but I think the findings and caveats of Bhowmick ’18 should be discussed more explicitly if they are used to justify the statement that high local eps algorithms protect against reconstruction attacks.

This is mainly semantics but I occasionally found the granularity of the privacy confusing. PrivQuant seems to be a locally differentially private in that each data point is privatized before it is sent to a central server. However, sqSGD is not written as a purely local algorithm, instead each client holds several data points, which they aggregate into a gradient, which is then privatized. Since PrivQuant is DP, it seems like the privacy is at the client level, not the level of individual data points? Perhaps the language of multi-central DP (https://arxiv.org/pdf/2009.05401.pdf)
 would be more helpful than local DP in the cross-silo FL setting?

Just a question for the authors: do you have any intuition for what’s happening with FMNIST? It seems much more sensitive than MNIST or EMIST

==== Presentation =

It would have been nice to see the non-private performance on the Figures to compare. The non-private seems to approach around 90% in most cases, is this around the non-private error? The authors state in the “impact of communication constraints” section that their algorithm “yields competitive results”, competitive with what?

The statement of Theorem 1 was a bit confusing. Is condition (5) required for the privacy statement and the unbiased statement? Currently it reads as being required for the unbiasedness, and its not clear whether its required for privacy.

Small:
LDP is typically attributed to Dwork, McSherry, Nissim, Smith ’07 or https://arxiv.org/pdf/0803.0924.pdf.
It might have been more intuitive to just state the definition of M(v_1,v_2) in terms of the Hamming distance. 
It would be nice to have some intuition for the statement about the quantization error at the start of section 2.3 since that wasn’t obvious to me. 
At one point the authors refer to “raw perturbed gradients”, is this unquantized?
review_title: Improvement on low communication algorithm for private SGD.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies FL under local differential privacy constraints. They identify two major concerns in designing practical privacy-preserving FL algorithms: communication efficiency and highdimensional compatibility, and develop a gradient-based learning algorithm sqSGD that addresses both concerns. They improve the base algorithm in two ways: First, apply a gradient subsampling strategy that offers simultaneously better training performance and smaller communication costs. Secondly, utilize randomized rotation as a preprocessing step to reduce quantization error. 

There are also some parts need to be improved. For example, putting the related work as Section 3 is not proper. For the experiments, the epsilon is too large for privacy protection as 400 and 2000,. For this level, the privacy is not well protected. For the baseline PM, which performs well when epsilon is small. But in this paper, the comparison is only about large epsilon.

They are some typos/errors here:
After Eq(1), it needs a space before ‘M’
Different fonts for “cross-silo”
The first sentence of the last paragraph on Page 2, capitalize the first letter.
Eq(4), it should be k^* rather than k
In Algorithm 1, parameter \tau is not introduced
review_title: Review

Meta-review: This paper studies differentially private, communication-efficient training methods for federated learning. While the problem studied in this paper is well-motivated and interesting, the reviewers raised several concerns about the paper. Despite the authors' reconstruction protection explanation, the concern over large values of epsilon at the scale of 400 persists. There is not too much technical novelty since the main technique is given by prior work. 
Decision: Reject