Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a private and communication-efficient framework for federated learning. For communication efficiency, the authors use compression, and for privacy, the authors use local differential privacy. The authors first start with a simple algorithm that applies compression directly to DP-SGD, and expand it to the SoteriaFL framrwork, which supports a number of of local gradient estimators and the state-of-the-art shifted compression scheme. The authors back up their claims with theoretical and mathematical rigor. 
strengths_and_weaknesses: Strengths:
- The paper is well-written and it's very easy to follow
- The paper has a smooth transition from a simple algorithm that applies compression directly to DP-SGD, to a more advanced private and communication-efficient algorithm. I personally found this transition smooth and nice.
- The paper is backed by a lot of theory and it is technically sound

Weakness:
- I am not a true expert in DP papers, while I read a lot of them, but I think this paper could benefit from some numerical analysis and experiments.
questions: The only question I have from authors, is that, are the current theoretical analyses enough to back the arguments? How about some field experiments with actual devices and real measurements? Will something like that increase the confidence of the claims of the paper?


limitations: It would be nice if the authors upfront and honest discuss the limitations of the paper. I believe it adds value and increases the trust from the readers 

(disclaimer: I should mention that I did not check the correctness of the theorems and proofs)
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies FL framework that both take into account compression to reduce the communication cost, and Local Differential-Privacy. The paper first introduces a baseline method CDP-SGD, which is basically DP-SGD combined with a compression of the model updates, and compute its utility for a number of communication rounds and a (epsilon, delta) DP bound.

The paper then introduced another class of framework (SoteriaFL). The main idea of SoteriaFL is to introduce a local shift s_i at each clients, that is track across the rounds. The gradient update $g_i$ of each client is shifted by $s_i$ before being compressed and sent to the central server. The server also keep track of a global shift, and add this global shift back to the sum of the model updates received during the aggregation part of the FL algorithm. SoteriaFL can be used with various local gradient estimators. The paper consider three such gradient estimators: SGD, SVRG and SAGA. For each of them,  the paper computes the utility and the communication complexity of SoteriaFL under (epsilon,delta)-Local Differential Privacy constraints.
strengths_and_weaknesses: # Originality
The method presented in the paper seems new, and the authors made a specific effort to cite related work and explain how their work differ from existing work. In particular they point out that their CDP-SGD algorithm can subsume other previously published works when specific hyperparameter are chosen.


# Quality

The submission seems technically sound, and the mathematical proof of the claims made are provided. I did not check all the proofs of the papers (and the appendices). But the quality of the writing and the clarity of the presentation indicate a meticulous work from the authors.


# Clarity
The paper is extremely clear and well-written. I just have the following two remarks:

- Algorithm 1, line 3: $I_b$ is not defined. It is defined later at line 204, but it would be important to define it here properly. In particular, it is important for the reader to understand that this step is only a gradient estimation, and there is no local model updates made as in FedAvg.

- Algorithm2: Tjhe initialization of $s_i^{(t=0)}$ and $s^{(t=0)}$ is not specified. Could you specify it?



# Significance
Computing theoretical convergence rates and complexity bounds of newly designed FL framework is important in order to provide more theoretical foundations to the FL research fields. Therefore the line of research followed by this paper is worthy of publication. However it's significance is slightly reduced by the fact that:

- The authors do not justify when/whether the assumptions 1 and 2 are true
- There is not simulations, even on mock data, to illustrate and support there findings.
questions: - Could you elaborate more on the assumptions 1 and 2, and explain in which FL cases you think there are satisfied?

limitations: I see to main limitations of this work:

- There are no numerical experiment, even on mock data to support and illustrates the claim made by the authors. The theoretical results are $O( \cdot. )$ meaning that all the constant have disappear. Therefore it would be nice to see these results in a numerical examples in order to better understand the order of magnitudes involved.

- The authors do not put enough in context the necessity of such a framework. It would be better to have an example of a real-world FL use-case, in order to put order of magnitude in the different parameters (number of clients, dataset etc.) and show explicitly that SoteriaFL could improved real-world FL project.

I don't think that these two limitations prevent from publication, as this work is a theoretical work and the focus of the paper is on convergence/compression rate.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper presents methods for differentially-private stochastic gradient descent, bounding the communication complexity for several gradient descent methods in their framework.  
strengths_and_weaknesses: Strengths:

Appears to improve on current state-of-the-art communication complexity results.
Mathematical analysis.
Attempt to make the analysis as general as possible.  

Weaknesses:  

Essentially all theoretical for what is, at its heart, a problem for practice.  Some type of experiment showing its utility, comparing to other existing schemes, etc. seems called for.  
Analysis appears to use straightforward methods;  could be clearer about the novelty.  

Originality:  Original analysis.
Quality:  Proofs seem correct, haven't checked them in detail.
Clarity:  Adequate, some issues, examples below.
Significance:  Hard to tell  without experiments of some form.  Is this just a theoretical result?  Should people doing FL in practice care?  

Issues:  It's unclear in reading the main paper what the "databases" are and what it means for them to be "neighbors" in this context.  What exactly are the "entries" in the database, what does the "mechanism" correspond to here -- what exactly is it that is being kept "private".  (If I'm doing learning on a set of images, is an entry one of the images?  What is the mechanism acting on the image?  What are possible effects of changing out an image?)  

I have strong hesitations on this type of "theoretical" result for DP on a practical problem without any sort of experiment to see if the end-to-end product is actually worthwhile.  Asymptotics can cover up a lot.  What is the actual effect/cost of adding DP into a system on any sort of real problem?  (I have no sense from reading the paper.)  
questions: See issue above on definitions.

It really seems for your analysis you don't care about what type of compression is being used (since you're adding noise, then compressing) and just need the compressor to satisfy (2)?  If so it feels like you could streamline things -- it wasn't clear to me where "compression" was important to the results, and my impression after going over it a few times is that it really isn't, you just happen to be compressing the end vector.  (To me it's a bit strange to refer to this as a unified treatment -- it seems that compression is just a black box to you.)

See issue above on "practice".  Could you do an experiment?  Or, can you better justify why the theoretical results should be of sufficient interest?  


limitations: n/a
review_title: null

Meta-review: metareview: The paper focuses on two important challenges in federated learning: communication efficiency and privacy of the users' local data. There has been a large body of work studying each of these challenges individually, but there are not many prior works which consider both of these challenges simultaneously. The paper proposes a unified framework that enhances the communication efficiency of private federated learning with communication compression. The paper provides two types of results: (i) It theoretically analyses the case in which a compression method is applied directly to differentially-private stochastic gradient descent; Using this analysis, the authors then explain some limitations of this approach. (ii) The authors then propose a framework, called SoteriaFL, which accommodates a general family of local gradient estimators (which includes SGD, SAGA, SVRG, etc) and a shifted compression scheme (which is one of the well-known methods for compression). SoteriaFL is then analyzed theoretically and performance trade-offs in terms of privacy, utility, and communication complexity are obtained. The benefits of SoteriaFL are then shown (in terms of communication complexity and less privacy, utility loss) compared to other methods. Table I provides a good summary. 

All in all, the reviewers found the theoretical results novel and interesting. The reviewers had a number of concerns most of which were addressed by the authors response and through the discussions. I thank the authors for their responses and also for adding experimental results (which was mentioned by all the reviewers). Two of the reviewers are very positive about the paper. The third reviewer has also read the author responses and mentioned through private (email) communication that they'd be willing to increase their score if the experimental results are reasonable. All in all, based on the reviewers' feedback (and my own assessment) I think this paper provides an array of novel contributions in the field of FL. 

confidence: Certain
Decision: Accept