Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a sketching-based federated learning algorithm to address the communication and privacy concerns in the federated learning setting. In the proposed algorithm, each client projects its local update (gradient) to a lower dimension via a sketching matrix before communicating the update to the server. The server aggregates the sketched local updates from different clients and communicates the aggregated update to the clients. The clients then de-sketch the message received from the server to update their local model. 

The paper shows that if the sketching matrix satisfies the "coordinate-wise embedding" property, then the proposed algorithm leads to provable convergence for smooth and convex objective functions. 

The paper also discusses the issue of privacy and proposes to add Gaussian noise to the sketched gradients to claim differential privacy of the resulting learning algorithm.
main_review: Strengths: 

1) The paper considers an important problem of addressing both communication cost and privacy concerns in the federated learning setting.

2) The paper makes several interesting technical contributions in the federated learning setting. In particular, the proposed sketching/de-sketching based learning algorithm is simple yet effective (as demonstrated by the analysis in the paper).

Weaknesses:

1) There is significant room for improvement in the presentation of the paper. The paper is filled with typos (see below) and many statements need to be paraphrased to effectively communicate the intended meaning. 

2) Even though the paper introduces privacy as one of the main focus points, it briefly discusses the privacy guarantee of the proposed method in Section 4.3. The authors should at least present a formal statement/results outlining the privacy guarantee. Moreover, the significance of considering two gradient vectors that differ in the single coordinate is not immediately clear. Shouldn't the authors focus on the two gradient vectors resulting from two local datasets that differ in a single data point? Please add a more detailed discussion around this.

3) In Section 4.3, the authors justify presenting the convergence results for only a noiseless setting. However, it appears that variance of the noise added to the gradient with d. How does such a large noise affect the convergence results? It would be interesting to present the results that take the presence of added noise into account.

4) The authors have provided a pretty extensive supplementary. It would be nice if the authors can connect the supplementary with the main text with more references to the supplementary. 

5) The authors discuss the issue of increased computation due to the increased number of iterations at the end of the paper. Please also consider discussing this issue earlier, e.g., in the introduction. 

6) There is scope for improving the discussion of related work. The statements like "...no work addresses both challenges simultaneously as far as we [are] concern[ed]" are not clear to the reviewer. For example, there is this prior work (https://arxiv.org/abs/1805.10559) that explores the issue of communication cost and privacy.

7) Could the authors comment on their claim that they don't increase the communication cost. As far as I can see, the authors only show that the communication cost remains the same in *order-wise sense*. Please consider modifying the relevant statements accordingly. (Some empirical results that support the authors' claims will be valuable here.)

8) The paper considers a gradient descent style algorithm where all clients participate in each round. Could the author comment on how their proposed solution should be modified for the setting where only a subset of clients participates in each round.

9) Please define $\Pi$ in Definition 4.1

10) In Section 4.2, please elaborate on "(1 \pm \epsilon) guarantee". 

11) Please consider paraphrasing the discussion in the second paragraph of Section 4.3 more precisely.  

Some examples of typos:

1) page 1, '..the amount of data to communication between...' --> '..the amount of data to be communicated between...'
2) page 1, '...is one of the most important the key...' --> please drop either 'the most important' or 'the key'
3) page 2, 'Fl' --> 'FL'
4) page 2, '...a central server update...' --> '...a central server updates...' 
5) page 2, '...three unique challenge...' -->  '...three unique challenges...'
6) page 3, '....applications in numerical linear.' --> '....applications in numerical linear algebra.' ?
7) page 4, '...we only communicates a low-dimensional sketched gradients.' --> '...we only communicate low-dimensional sketched gradients.''
8) The authors use both 'Section' and 'section'. Please consistently use one of these. 
9) page 6, '...since they intuitively, they ...' --> '...since they...'

[There are similar typos in other places. Please proofread to fix those.]

summary_of_the_review: Overall, the paper explores an interesting and timely problem. The paper presents a simple and effective scheme that has provable performance guarantees. However, there is significant room for improvement to make the contributions of the paper clear. Especially, the discussion around privacy guarantees needs to be improved. The authors also need to discuss missing prior work on communication efficiency + privacy for federated learning.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a novel federated learning framework where the client only submits a sketched gradient to the server and de-sketches the average gradient received from the server. The proposed framework can preserve the privacy of the data as well as reduce the communication cost. The paper theoretically analyzes the convergence rate and shows that the proposed method requires less communication cost than existing methods.

main_review: Federated learning has recently become a popular framework for training machine learning models. Reducing the communication cost of federated learning is an important problem. However the contribution of this paper is incremental. First, combining sketching with federated learning has been studied by several existing papers (see comment 5). Also, the paper doesn't provide any empirical results and the theoretical part is also on the weak side. Here are the details:


1. Some notations of different sections are inconsistent. For instance, the paper uses $a$ to denote the value of coordinate-wise embedding in section 4.1, but uses $\alpha$ instead in section 5 and appendix. I suggest the authors check the notations in the paper to increase the readability of the paper.

2. The theorems in section 5 only require Assumption 3.1 holds, but I think they also require theorem 4.2 holds since their proofs use the property of the sketching matrices. In addition, I'm confused with the proof of Lemma F.6. The inequality below Eq. (18) says $E[dest_t(sk_t(h))]\leq (1+\alpha)||h||^2$. However, Thm 4.2 only tells us $E[dest_t(sk_t(h))]\leq (1+\alpha d / b_{sketch})||h||^2$. The paper should provide some explanation on why it can remove the  $d / b_{sketch}$ term?

3. I'm also confused with the proof of Corollary 5.7 and 5.9 (Thm F.8 and Thm F.10). In the last sentence of the proof of Thm F.8 says "the optimal $\alpha$ is given by O(d)." Since $\alpha$ is the value of the coordinate-wise embedding of the sketching matrix, how to let $\alpha$ be O(d)? The proof of Thm F.10 faces the same problem.

4. For Thm 5.6 and 5.8, $\eta=1/(8(1+\alpha)LK)$ is not enough to guarantee $w^T$ converge to the $w^*$ since the last term in the bounds won't decrease when the number of iteration increase. I think $\eta$ should be related with $T$ or $\epsilon$.

5. It seems that the clients use different sketching matrices for different $t$. How to guarantee that all clients use the same sketching matrix in each round without communication?

6. The following papers also adopt sketching to reduce the communication cost of federated learning. I suggest the author discuss the difference between those papers and this work.

"Communication-efficient Distributed SGD with Sketching", NeurIPS 2019. 

"FetchSGD: Communication-Efficient Federated Learning with Sketching", ICML 2020.

7. I also suggest the author perform some empirical evaluation to show the effectiveness of the proposed method.
summary_of_the_review: The paper lacks empirical results and the theoretical analysis is somewhat weak. Thus I recommend to reject the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a sketching approach to reduce the communication cost of federate learning, and prove the convergence of their proposed method for convex function. By adding gaussian noise to the gradient, it can also guarantee different privacy.
main_review: Let me first summarize the main idea of this paper. The idea is conceptually simple, it uses a JL sketch to reduce the dimension of gradient, and since this *projected* gradient has large correlations with the original gradient, one can prove the convergence. 


Strength. I found it interesting to combine sketching with federate learning. The idea is conceptually simple but no one explores it before.


Weakness. There is no experiments, and the total communication cost does not decrease.
summary_of_the_review: ---------------------------------
Post rebuttal:

I have read author's response as well as other reviewer's suggestion. I still think the paper is of value at certain aspects. But as other reviewers pointed out, I suggest the authors include a more detailed discussion on related work.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies the application of linear sketching algorithms to reduce the communication complexity in federated Learning problems. In particular, the paper proposes that the clients send a low-dimensional linear sketch of their updates to the server. Convergence rate of local SGD when deployed with such a method for aggregating the updates are discussed for various function classes. Finally, the paper also discusses a method for integrating differentially privacy guarantees in their method.
main_review: **A. Novelty in the update aggregation mechanism:**

A1. The idea of using random matrices to reduce communication complexity in federated learning is not new at all. See, for instance, the following papers (which the authors seem to be oblivious to):

   i) Suresh, A. T., Felix, X. Y., Kumar, S., & McMahan, H. B. (2017, July). Distributed mean estimation with limited communication. In International Conference on Machine Learning (pp. 3329-3337).

   ii) Mayekar, P., & Tyagi, H. (2020, June). RATQ: A universal fixed-length quantizer for stochastic optimization. In International Conference on Artificial Intelligence and Statistics (pp. 1399-1409).

   iii) Chen, W. N., Kairouz, P., & Özgür, A. (2020). Breaking the communication-privacy-accuracy trilemma. In advances in Neural Information Processing Systems (pp. 3312--3324).

  iv) Agarwal, N., Suresh, A. T., Yu, F., Kumar, S., & Mcmahan, H. B. (2018). cpSGD: Communication-efficient and differentially-private distributed SGD. arXiv preprint arXiv:1805.10559.

The lack of comparison of the author's proposed scheme with any of these papers is astonishing and is definitely warranted for a fair understanding of the authors' contribution. 

A2. From my understanding of the papers mentioned above, there is nothing that the authors propose in their aggregating algorithm(Section 4) that wasn't already known. 

     a. For instance, both i, ii, highlight, and crucially use the fact that when the updates are processed using certain random matrices, the coordinates of the processed vector have small absolute values; a property amenable for efficient vector quantization. The authors of this paper, too, point out a similar property in Definition 4.1.

      b. Similarly using $R^T$ to "de-sketch" the sketched update has also been highlighted in these papers.
  

A3.  I don't see the point behind definition 4.1, since the authors don't seem to exploit this property to build better communication protocols. In particular, since convergence guarantees seem to rely on only the second moment bound in T 4.2, something as unsophisticated as uniformly sampling $b_{sketch}$ coordinates would (and scaling appropriately and setting other coordinates to $0$) would give the same guarantees as sophisticated sketches (precisely the same as in T 4.2). What is the point of these sophisticated sketches then? This does not come out in the paper at all. 

As I pointed out in A2., properties similar to Definition 4.1 have been highlighted by many papers since 2017. The rationale behind highlighting such properties in these papers was to further exploit such properties for efficient vector quantization.  It is pointless to use these sketches, without exploiting them to build efficient vector quantizers.


 **B. Presentation and clarity**

B.1 The authors can significantly improve the presentation and the clarity of this paper. The paper has many ambiguities and typos in its current form, and, frankly, it is far from being ready for publication.

B.2 In  a 43 page research paper whose main goal is to reduce the communication complexity of federated learning, it is astonishing that not a single line is used to describe the overall quantization procedure.

 Perhaps the author meant to use the default 32 bit (64 bit) precision to transmit each scalar. Even this is important to state explicitly. Of course, if this is indeed the case, then what is the point of using sophisticated sketches (See point A.3 for more details).

B.3 The parameter $\alpha$ is never defined. This parameter crucially shows up in convergence results. ( After going through the proofs, I could understand this was the variance blowup parameter. Nonetheless, it should have been highlighted in the first place.)

B.4 It is only in the discussion section that the authors point out that their convergence results build upon the work of Khaled 19. In my opinion, this should be explicitly stated in Section 5 and highlighted, where the convergence results are presented. 

B.5 There are several inconsequential typos and grammatical mistakes throughout the paper. Thorough proofreading of the paper should be able to fix this.

B.6 It is disappointing that there are no labels to identify the parts in the appendix as proofs of the results presented in the main paper. Given the lack of such labels, the appendix section is extremely difficult to navigate through.
summary_of_the_review: GIven the lack of novelty in the paper's main algorithm (A.2), the lack of comparison with other published works using similar approaches (A.1, B.4), the fact that authors themselves show a lack of understanding of the motivation behind using sketches (A.3), and multiple presentation issues (B.1 - B.6), I  recommend the paper be rejected.
review_title: null

Meta-review: The paper studies federated learning with various sketching techniques used for communication. 

The main concerns from the reviewers are: 

1) the presentation can be improved; 

2) the novelty and related work section is not satisfactory since there have been papers on sketched federated learning; 

3) there is no numerical study to validate the efficacy of the method. 

I suggest the authors to take into consideration the feedback from the reviewers in the revision of the paper.
Decision: Reject