Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a framework for federated learning by adjusting the frequency of communication between agents and the server with an adaptive quantization scheme. Specifically, the authors combine two quantization schemes, namely, the adaptive quantization rule (AdaQuantFL) and lazily aggregated quantization (LAQ). 
strength_and_weaknesses: Weaknesses:

- My main concern is regarding the novelty of the proposed method and also, in improving the existing results. This paper seems to be significantly built on a prior work "Lazily Aggregated Quantized Gradient Innovation for Communication-Efficient Federated Learning". It is not clear how the performance of LAQ in the mentioned work is improved in theory. The authors only mention a comparison after Theorem 4.2: " Theorem 4.2 informs us that AQUILA can achieve a linear convergence rate as in LAG (Chen et al., 2018) and LAQ when certain assumptions are satisfied." I wonder what would be the motivation to use the proposed AQUILA method if it achieves the same performance for already existing LAG and LAQ methods.

- The paper considers a (not class) specific quantizer which limits the scope of the theoretical and simulation results. 

- Assumption 4.3 states that all devices’ quantization errors are constrained by the total error of the omitted devices. The justification for this assumption is presented as follows: This assumption is easy to verify when M_c≠∅ this a bounded variable will always be bounded by a part of itself multiplied by a real number. This statement is not accurate and should be: This assumption is easy to verify when M_c≠∅ this a bounded variable will always be bounded by a non-zero part of itself multiplied by a real number. So, how can we guarantee that the total error of the omitted devices is non-zero?
clarity,_quality,_novelty_and_reproducibility: The paper is marginally novel compared to the existing work on quantized federated learning in the following works:

- Jun Sun, Tianyi Chen, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Lazily aggregated quantized gradient innovation for communication-efficient federated learning. IEEE Transactions on Pattern Analysis & Machine Intelligence, pp. 1–15, 2020.

- Tianyi Chen, Georgios B Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communication-efficient distributed learning. In Proceedings of Advances in Neural Information Processing Systems, pp. 1–25, 2018.
summary_of_the_review: The paper falls short to highlight the main novelty compared to the previous works on the lazy aggregation of quantized gradients for federated learning as I detailed above. The theoretical results suggest no improvement compared to existing methods such as LAG and LAQ.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new communication efficient federated learning approach that combines adaptive quantization with lazy aggregation of gradients at each round to reduce the amount of data communicated as compared to prior work while providing comparable reduction in training loss. The approach is validated through theoretical analysis and experiments in both homogenous and heterogeneous federated learning settings.
strength_and_weaknesses: Strengths:

a) The main strength of the paper is that it combines adaptive quantization and lazy aggregation of gradients in a principled manner. Specifically, the quantization level at each round at a given node is clearly connected to the amount of new information (gradient innovation) being provided by the node instead of just depending on the loss value. 

b) The principled approach is then backed by analysis and experiments to show that it indeed reduces the amount of data being communicated while providing the same training performance in a variety of settings.

Weaknesses:

a) The main weakness according to me is that the explanation of the algorithm is currently not very clear. I have provided some comments/suggestion on improving this in the following section. 

b) While the main selling point for AQUILA is the reduction in the amount of data being communicated, the current theoretical results only show that the training converges at the same rate as standard GD. Any analytical result characterizing the expected reduction in amount of data being communicated would significantly strengthen this work. Alternately can you provide some explanation for why such an analysis is difficult?

c) Likewise, from Figure 3 (d-f) it appears that the variance in the amount of data being communicated is also significantly lower in AQUILA which is a point in its favour, especially if the network cannot handle large fluctuations in the amount of communication. Can you provide some analysis/intuition for why that may be the case?
clarity,_quality,_novelty_and_reproducibility: The overall presentation is clear but the explanation of the algorithm is quite hard to follow as some background information is missing and the explanation is spread over Section 3 of the main paper and Appendices A1, B and C. I have the following suggestion for addressing this issue:

a) Consider putting Algorithm 1 in the main paper. It is much easier to follow the explanation in Section 3 after reading Algorithm 1. If space is an issue, Figure 1 can be moved to the Appendix in my opinion.

b) Please formally define gradient innovation, with the relevant notation, instead of just explaining it in one line in the introduction. The term is used several times in Section 3, and I don't think it is a commonly known term.

b) Please provide some background or intuition behind (8) and (9). While these appear to be obtained from the quantizer in LAQ, I believe there should at least be some intuition provided for these expressions for the benefit of readers unfamiliar with LAQ.

c) Please provide some justification for (10) in the main paper by suggesting how it follows from (8) and (9). Currently it seems to appear out of nowhere unless one reads the derivation in Appendix C.

d) There is also no motivation for (11) and I still do not understand why it is a suitable criterion for device groups being skipped. Specifically, it seems to require knowledge of $\theta^{k+1}$ at all worker nodes in round $k$ but since the nodes do not have access to each other's gradients I do not see how they can calculate the threshold in (11). Please clarify.

summary_of_the_review: The paper proposes a novel principled approach for communication efficient federated learning approach that combines adaptive quantization with lazy aggregation of gradients and is backed by both theoretical analysis and experimental evaluation. However, some points need to be explained more clearly and some background information needs to be provided to make it fully accessible to readers.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a communication-efficient federated learning strategy, AQUILA, that combines lazily-aggregated quantization (LAQ) and adaptive quantization (AdaQuantFL). This strategy balances the communication frequency for each parameter and the quantization level adaptively. Experimental results show that AQUILA outperforms the baselines (including LAQ and AdaQuantFL individually) on CIFAR-10, CIFAR-100, and WikiText datasets. 
strength_and_weaknesses: The paper is well-written. Overall, I enjoyed reading the paper. Even though the main ideas and the approaches in the proofs are mainly borrowed from existing works, I think the authors did a good job in combining the methods.

- When averaging the local objective functions in (1), why isn't the local function weighted by the number of local samples $n_m$? 

- Page 4, first line: quantification -> quantization.
clarity,_quality,_novelty_and_reproducibility: The paper is well written. The authors share experimental details and the code to reproduce the results. 
summary_of_the_review: Please see my comments above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a new adaptive quantization strategy (and aggregation criteria), AQUILA, by adaptively determining the quantization bits per round per client in lazily aggreagated federated learning. The quantization level $b^*$ is chosen based on the $l_\infty$ and $l_2$ norm of the difference between the current gradient and the previous quantized gradient. Convergence rates in non-convex and PL condition are provided. Experiments are conducted to show the advantages of the proposed method.
strength_and_weaknesses: Pros:
1. The topic of federated learning (FL) is important and interesting to NeurIPS community.
2. The paper provides both theoretical and empirical results.
3. The writing and presentation, though can still be improved, is in general clear.

Cons:
1. (i) The motivation is not very strong. While alternating the number of bits $b$ across training rounds might be effective, it is not guaranteed to always bring benefits (reduced communication). Specifically, in formula (10) when choosing $b^*$, it seems that the number of bits largely relies on the largest entry of the vector ($l_\infty$ norm). What if the vector only has a few 'outliers'? This strategy would use a large $b$ to compromise those outliers. A more practical and possibly better strategy might be sending those large coordinates in full-precision, and quantize others using low bits. This may use much less communication than the proposed strategy. In my understanding, (10) basically says that if the largest magnitude of the vector is big, we use more bits. This does not look very exciting and promising to me.

(ii) From Figure 2 and Figure 3, we see that the communication across training rounds of AQUILA is almost constant (a flat line). Then why not simply using a fixed number of bits? I think a figure with the evolution of the $b^*$ for the clients might help.

(iii) The communication criteria (11) looks more like a byproduct for the convenience of proof (e.g., Lemma A.1). Could you please provide more intuition on it and its difference with (6)? Besides, I have two questions regarding (11). First, how do you know $\theta^{k+1}$ at time $k$? Second, are both $\gamma$ and $\beta$ free hyperparameters? If so, the algorithm becomes much harder to tune which is also a potential drawback.

2. The convergence analysis considers full gradient without noise, which is less practical since people use SGD in most applications. On page 6, the authors wrote 'we could still prove the correctness of Corollary 4.1 in this special condition without any extra assumptions'. Then why is Assumption 4.3 needed? 

3. Indeed, Assumption 4.3 seems a little bit strange. In (13), is the $\gamma$ the same as that in (11)? Also, you can assume a very large $\gamma$ for this condition to hold. However, I do not see this $\gamma$ appearing in later theoretical results. So how does this assumption affect the analysis?

4. The experiments uses $M=24$ clients which is rather small for FL. Also, there is no ablation study on the impact of $\gamma$ and $\beta$. Thus we do not know how robust this algorithm is to different choices of the hyperparameters. I think the authors should also compare with strategies with fixed-bit quantization like the popular QSGD method. This could help justify the importance of adaptive quantization and strengthen the motivation. Currently, given the above concerns, I think the motivation is not very strong.
clarity,_quality,_novelty_and_reproducibility: Please see above.
summary_of_the_review: I feel that the motivation of this paper is not very strong. I have some concerns about the design of the new adaptive quantization strategy. The theoretical analysis needs some seemingly meaningless assumption and does not consider stochastic gradients which is less practical. The experiments lacks ablation study and comparison with important methods. Thus, I think the paper is below the high bar of ICLR in its current version.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents an approach, AQUILA, to reduce communication overhead in federated learning (FL) by combining adaptive quantization (adapting the bit-rate) and lazily-aggregated gradients. The paper provides a theoretical convergence guarantees and an experimental evaluation illustrating the potential communication reduction achieved with AQUILA.

**Strengths:** We acknowledge and appreciate that there is some algorithmic novelty in the work, although it involves combining many ideas that have previously appeared in the literature. We also appreciate the experiments that were done to compare to previous work, including experiments added during the rebuttal period

**Weaknesses:** There are two main weaknesses of this work:
1. Because the theory focuses on deterministic gradients (the extension to handle stochastic gradients is not at all obvious) and largely combines existing proof techniques, this creates a significant gap between theory and practice, and there wasn't enough theoretical support on its own to justify accepting the paper; this effectively raises the bar on expectations for the experimental evidence.
2. Although the experiments include comparisons with many other methods in the literature and show promising performance, they don't help illustrate or understand why AQUILA performs better than previous approaches. For example, in Fig 2, we see that transmitted bits / epoch is relatively flat throughout training (with few exceptions), leading to the question of whether a simpler method like LAQ could perform nearly as well if it was tuned better.

In addition, the paper could be strengthened by improving clarity of presentation. One concrete suggestion is to clarify the description of the algorithm based on the reviewers' feedback. Another suggestion is to directly acknowledge the limitation of focusing the analysis on the deterministic setting (for example, in Section 6) and point this out as an important direction for future work. (To be clear, we understand that analyzing AQUILA with stochastic gradients would require substantial additional work and did not expect that for this submission.)
justification_for_why_not_higher_score: If the theory covered the case that was actually run in experiments (with stochastic gradients), then the paper would be stronger, but this seems like a major challenge. Without this, the primary contribution is the experiments, and these don't sufficiently help justify or explain why the proposed approach performs better than previous approaches. The reviewers weren't comfortable recommending acceptance (and I agree) without this.
Decision: Reject