Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies how to compress the local model changes in federated learning to save uplink communication costs. In particular, the authors found (1) adaptively increasing the number of quantization levels (2) adaptively assigning different quantization levels on different clients, can effectively outperform previous static quantization schemes. They evaluated the proposed algorithm on multiple federated learning datasets.
main_review: ### Strengths
1. The proposed two adaptive quantization strategies are simple and easy to implement in practice. In the experiments, they exhibit better performance than static quantization schemes.
2. The client-level adaptive quantization scheme is new and has not appeared in literature. The idea itself makes sense and the authors proposed a theory-grounded approach to make it work.

### Weaknesses
I think the "time-adaptivity" part in the paper is a bit improper. And the authors tend to oversell their contribution. The contribution in this part is kind of trivial compared to previous works.

- In the introduction, the authors mentioned that "we observe that early training rounds can use a lower q without affecting convergence". But in fact, this observation was first made by previous literature, such as (Jhunjhunwala et al. ICASSP 2021). More generally, the intuition that one need more communication towards the end of training already appeared in two years ago in (Wang & Joshi, MLSys 2019, "Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD"). The way the authors wrote this part can make people think this paper find this idea, which is not. The authors are supposed to make it clear in introduction that "previous literature observed that.. and we further improve their algorithms by overcoming/addressing.."
- The comparison of time-adaptive quantization schemes with previous work (Jhunjhunwala et al. ICASSP 2021) is unfair. Basically, (Jhunjhunwala et al. ICASSP 2021) let all clients to participate into each round of training because they consider the full participation FL. But the algorithm itself can be easily extended to the case where we only sample few clients at each round. One can simply replace the global loss by the average loss within the current subset. Compared to this work, the authors should demonstrate (1) moving average of the loss help; (2) a step-increase strategy is better than the strategy used in (Jhunjhunwala et al. ICASSP 2021); (3) the proposed strategy converges faster than any other static quantization schemes, as predicted in Figure 2.
- Related to the above point, I feel the authors failed to demonstrate the effectiveness of the time-adaptive quantization methods. There are still many remaining questions. In their experiments, the authors do not show whether the moving average of loss help. The authors do not compare the results with previous works AdaQuantFL. The authors do not show the proposed scheme is faster than any other static quantization schemes, as predicted in Figure 2. Instead, they just fix one quantization level and report the final accuracy.
- In addition, the authors claim Pareto optimality in their experiments. I don't agree with this. Although the proposed algorithm is better, why is it the optimal one? 

summary_of_the_review: In general, I think the client-adaptive quantization part is quite interesting and novel. But the time-adaptive quantization part is incomplete. The authors fail to demonstrate the effectiveness of their proposed method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the federated learning problem with a focus on communication efficiency. The major contribution of this paper can be summarized as:

(1) Propose a time-adaptive quantization algorithm that adjusts the quantization level
as training progresses

(2) Propose a client-adaptive quantization algorithm that assigns quantization level to individual clients
main_review: Strength:

(1) A novel double quantization design

(2) Communication overhead saving is promising


Weakness

**(1)  Computational overhead in quantization**

This paper proposes a double quantization strategy for efficient FL.  While the saving in the communication overhead is promising, there is little discussion on the extra computational overhead introduced by the algorithm. For instance: i) what is the complexity of performing the time-adaptive and  client-adaptive quantization algorithm, ii) how does the overall training time being affected if we use the proposed algorithm, iii) what is the ratio between the communication time saving and the total training time

**(2)  Comparison with other communication efficient algorithms**

This paper compares with quantization baselines. How does the double quantization algorithm perform when we compare it with sketching-based FL methods?


summary_of_the_review: This paper is well-organized with a clear presentation. However,  there exist concerns regarding the efficiency of the proposed algorithm
 
The authors are strongly encouraged to address these shortcomings by:

(1) Benchmarking the total training time and the computational overhead in quantization

(2) Comparison with other  communication efficient  FL strategies such as sketching
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a communication-efficient federated learning framework named DAdaQuant. It is a quantization-based FL compression algorithm, which chooses both time-adaptive and client-adaptive quantization levels to improve the communication efficiency of FL algorithms over previous quantization works. The work provides math intuition behind choosing the client-adaptive quantization level. The authors also show solid empirical studies over FL datasets and validate the superiority of the proposed approach in communication efficiency.
main_review: The paper provides clear intuition behind the double adaptive quantization approach. The work also presents solid empirical studies by comparing with a series of baseline algorithms over multiple classical datasets. The work overall is well presented.

Major concerns and questions:
1. For Theorem 1, what is the definition of $e^{p_1\cdots p_K}_q$? How is the agent-specific quantization level $q_i$'s relates to the given quantization level $q$?
2. For Figure 4, the authors comment that for DAdaQuant, the communication cost does not scale with the number of clients. The reviewer thinks that despite per iteration the communication cost does not increase, the overall number of training rounds will increase, which causes the total communication cost to grow, especially in a data heterogeneous case. Can the author comments on this?

Minor questions:
1. In section 3.5, the authors comment "We observe that Ep1...pK [Var(Qq(p))] is a useful statistic of the quantization error
because...". The reviewer does not doubt the intuition. But is there any rigorous justification for this observation?
2. Have the authors tried other orthogonal techniques combining with quantization to further improve the communication cost empirically?
summary_of_the_review: The paper is lean towards empirical studies. So the reviewer does not judge from the theoretical contribution perspective. Overall, the paper well presents the intuition and the logic of the data-adaptive quantization approach. The empirical study part is well-rounded and the results are relatively solid.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper tries to reduce the communication cost of the Federated Learning (FL) algorithms.  They introduce the doubly-adaptive quantization algorithm (DAdaQuant), which adopts two quantization techniques: 1, time-adaptive quantization; 2, client-adaptive quantization.  The empirical studies also show that DAdaQuant can improve client sever compression. 
main_review: The strengths:

1, The paper develops a new communication-efficient quantized FL, Particularly, the client-adaptive quantization is the first time to be considered for FL algorithms. 

2,  The paper has done extensive experiments to show the improvement of proposed methods. 

The weaknesses:

1,  Some math notations used in this paper miss definitions. For example, the definition of  $E_{p_1, ..., p_K}[Var(Q_q(p))]$ is missing.

2, The quantization $Q_q(p)$ used in this paper based on section 3.3 QUANTIZATION WITH FEDERATED QSGD is "$Q_q(p)$ then returns the sign of p and jpj rounded to one of the endpoints". This quantization is not an unbiased estimator of $p$, which is conflict with the claim on page 14. 

3, The paper introduces the expected variance of an accumulation of quantized parameter $E[Var(\sum Q(p))]$ as a measure of the performance of quantized FL algorithm and tries to minimize it in Thereom 1. The authors should explain more why it is a good measure.  Why not give the theoretical analysis in the following logic line: convergence guarantee -> get rounds T, given $epsilon$ -> get computational complexity and communication cost?

4, In algorithm 1, RunClient($c_k$) is missing between line 8 and line 9. 

summary_of_the_review: The paper proposes an interesting communication-efficient FL algorithm. However, the theoretical analysis is not convincing and the commonly used analyses, like communication cost via communication rounds, are missing.
review_title: null

Meta-review: Dear authors,

I apologize to the authors for insufficient discussion in the discussion period. Thanks for carefully responding to reviewers. Nevertheless, I have read the paper as well, and the situation is clear to me (even without further discussion). I will not summarize what the paper is about, but will instead mention some of the key issues.

1) The proposed idea is simple, and in fact, it has been known to me for a number of years. I did not think it was worth publishing. This on its own is not a reason for rejection, but I wanted to mention this anyway to convey the idea that I consider this work very incremental. 
2) The idea is not supported by any convergence theory. Hence, it remains a heuristic, which the authors admit. In such a case, the paper should be judged by its practical performance, novelty and efficacy of ideas, and the strength of the empirical results, rather than on the theory. However, these parts of the paper remain lacking compared to the standard one would expect from an ICLR paper. 
3) Several elements of the ideas behind this work existed in the literature already (e.g., adaptive quantization, time-varying quantization, ...). Reviewers have noticed this.
4) The authors compare to fixed / non-adaptive quantization strategies which have already been surpassed in subsequent work. Indeed, QSGD was developed 4 years ago. The quantizers of Horvath et al in the natural compression/natural dithering family have exponentially better variance for any given number of levels. This baseline, which does not use any adaptivity, should be better, I believe, to what the author propose. If not, a comparison is needed. 
5) FedAvg is not the theoretical nor practical SOTA method for the problem the authors are solving. Faster and more communication efficient methods exist. For example, method based on error feedback (e.g., the works of Stich, Koloskova and others), MARINA method (Gorbunov et al), SCAFFOLD (Karimireddy et al) and so on. All can be combined with quantization. 
6) The reviewer who assigned this paper score 8 was least confident. I did not find any comments in the review of this reviewer that would sufficiently justify the high score. The review was brief and not very informative to me as the AC. All other reviewers were inclined to reject the paper. 
7) There are issues in the mathematics - although the mathematics is simple and not the key of the paper. This needs to be thoroughly revised. Some answers were given in author response.
8) Why should expected variance be a good measure? Did you try to break this measure? That is, did you try to construct problems for which this measure would work worse than the worst case variance? 

Because of the above, and additional reasons mentioned in the reviewers, I have no other option but to reject the paper.

Area Chair
Decision: Reject