Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper points out that model update frequency and update quantization level are not disjoint decisions in federated learning systems. Furthermore, it explains how to modify and combine prior work on each of the two decisions to develop a new adaptive aggregation method. 


main_review: Strengths:
1) The paper considers a relevant problem.
2) It is toward unifying the prior work.
3) Changes in the gradients seem a reasonable signal for the adaptation decisions.

Weaknesses:
1) On page 4, the paper mentions that AQUILA has a better method for setting the quantization level as, unlike AdaQuantFL, equation (7) doesn't increase the quantization level over the training process. However, doesn't the size of the gradients (i.e., $||g^k_m||$) decrease during the training process? If so, wouldn't it be better to compare the normalized gradients in eq. (7) rather than the gradients?        

2) Have the performance improvements shrunk on the CIFAR10 dataset which is a more complex dataset than MNIST? For example, look at Figure 4 subplots (d) and (f). If so, why does this happen and what is AQUILA's benefit for more complex data distributions in the real world? 
summary_of_the_review: I think this paper raises a good question about the interaction between the frequency and quality (i.e., quantization) of model updates in FL. Still, neither the intuitions nor the experiment results convince the reader much about the proposed approach. I'm marginally recommending accepting the paper mainly based on the assumptions that the problem statement is novel and the theoretical methodology is sound to my current understanding of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, authors propose the framework for federated learning that adaptively adjusts the frequency of the communication rounds and the quantization efficiency in a synergistic way.
main_review: The idea of this paper is to develop the framework fro FL that allows to ruduce communication cost.
Authors uses the following ideas as a core: 1)  the frequency of communication rounds depends on the local gradient change (Local Gradient Aggregation); 2) adaptive quantization correlates with the logic of the Lazy Gradient Aggregation - the quantization level is smaller if the local gradient difference between the current gradient and last sent one is bigger.
The combination of these two ideas allows to reduce the communication round amount in the late iterations of algorithm comparing to AdaQuantFL.

My main concern is the following: since the server updates the model with some new quantized gradients and with old ones for the machines that have decided to skip their update we save some amount of communication rounds TO the server. However, the update of the global model is a combination of quantized updates it can be quite ``dense'' and hard to send, but on every round of the algorithm server broadcast the new model to all machines that seems to be costly. May be the broadcast should be made in the same manner as the lazy aggregation procedure?

Also I have a minor comment to the notation $\theta^{\star}$ that seems to denote $f(\theta^\star}$.

According to the experimental section, I failed to follow the plots: they are quite small on A4 paper; they are not colorblind friendly and I am colorblind. However, I still have a question to the Figures representing "transmitted bits" do they assume the communication TO server  only or together with the broadcasting.




summary_of_the_review: In conclusion, I think that authors of this work made a good job. The idea of adaptation of quantization and frequency of communications is very nice; however the broadcasting procedure seems to be very time-consuming.
For me the Experimental section was impossible to follow, but I think that minor modifications of the Figures can resolve this problem.

All in all, I think that after some changes this paper can be accepted and the presented algorithm can be used in real-world FL applications.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes combining two orthogonal algorithms -- the lazily aggregated gradient(LAQ)method and adaptive quantization (AdaQuantFL)-- to reduce communication complexity in federated learning. In particular, while LAQ focuses on the frequency of gradient updates in each iteration, AdaQuantFL focuses on the adaptive allocation of bits across iterations. This paper proposes to combine both of these approaches for better communication complexity in federated learning. 

At the heart of the combining strategy is Eq. 7, which allocates the bits used in each iteration. This equation is intern based on minimizing the upper bound on the expected deviation in the path of the iterate due to gradient skipping. The authors theoretically show that such a bit allocation strategy leads to reduced communication compared to the bit allocation strategy of AdaQuantFl.


main_review: **A Strengths:**
1) Experiments validate the superiority of the proposed method over each of its individual components (LAQ, AdaQuantFL,), as well as their naive combination, and other well-known FL methods.
 
2) At a high level, the idea itself of combining two orthogonal directions in Federated learning, transmitting infrequently and compressing the updates, is very interesting. The fact that the trivial combination of these two approaches isn't as effective and one needs to intricately design the overall scheme is surprising, and something to keep in mind for future research in this area.

**B Weaknesses:**
1)  It was disappointing not to see an explicit convergence rate of the proposed method. 

2) Building on the previous point, a lack of comparison with local methods in convergence rate and experiments was disappointing. I think these comparisons are needed for a fair assessment of the paper.

3) Since this paper is mainly about combining existing ideas, there is not a lot of algorithmic novelty in the paper.

**C Presentation:**
1) The paper is well-written and easy to follow.

2) Is there any specific reason that authors choose to minimize the upper bound of the quantity on the LHS of Theorem 1. Choosing different metrics would lead to different bit allocation strategies. Why was this particular metric chosen then?
summary_of_the_review: Overall, primarily based on the experiments, I recommend the paper be accepted. However, I cannot be as confident of the paper's contribution as I would like to be because of a lack of comparison with a crucial part of the literature (B.1, B.2).
review_title: null

Meta-review: Two of the initial reviews of the paper were mildly positive (2 scores of 6), and one was very positive (score of 8). However, these reviews failed to notice some severe issues with the paper, which were detailed by the Area Chair in an Extra Review which was provided late. The severe issues include: clarity of exposition (undefined notation in many places) and theory (vacuous or meaningless theorems and assumptions). I apologize to the authors for not having had the chance to defend against this late review. However, the issues are indeed severe.
Decision: Reject