Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies federated learning with quantization. The problem setting is very standard, including both iid and non-iid cases. This work proposes a new algorithm, called lossy FL, to save the communication costs, especially from the broadcasting direction. To my understanding, the algorithm is new but still very similar to double-squeeze (Tang 2019). The presentation of the paper is generally good. However, there are several major issues regarding the quality and significance of this work.

1. The convergence analysis is based on the assumption that the problem is strongly convex. But from the motivation of this work and numerical results, the problems would be nonconvex. The current analysis is restrictive.

2. There is no analytic result of quantifying the upper bound of \tau, which is one of the key differences between federated learning and distributed training. There are already many works there.

3. The comparison with double-squeeze is definitely not fair, since the aggregation rule of the double-squeeze did not consider the \tau step local update.

4. The numerical results are very limited, where the CNN network is very small. There is no need to perform quantization for this neural net. Also, MNIST and CIFAR-10 are all small datasets. I don’t know why there were 40 devices used. To show the advantage of federated learning, the speed up in terms of the training time should be compared and plotted.

review_title: Comments for Federated Learning with Quantized Global Model Updates

final_score: rating: 5: Marginally below acceptance threshold
review_content: In the setting of Federated Learning, the authors propose to quantize both (1) the model send from PS to devices, and (2) the update from device to PS. Although the idea of model-broadcast-compression has appeared in previous work, the authors improve upon previous works in that (1) the authors propose to compress-and-send model updates instead of the model itself, which have smaller variance and peak-to-average ratio and therefore have more effective quantization compression, and (2) do not require pre-processing like linear transformation. The authors further show the effectiveness of their proposed algorithm, LFL, by offering a convergence analysis under appropriate conditions, and offering thorough experimental evaluations.

Pros:
+ The authors show convergence results under the strong-convex and smooth condition, making this work more theoretically-grounded than previous related work.


Cons:
+ I am not convinced that sending updates instead of sending models is a valuable idea.
Sending updates instead of sending models is definitely not a new idea in the quantization optimization community, but mostly from device to PS direction, and not the other way around. I believe there are some challenges or tradeoffs to do the PS-to-device directions, but the authors did not sufficiently address this in the paper. For example, two trade-offs that I would expect are, (1) now devices have more computation responsibility, but they are usually weak in computation and sensitive in power consumption, (2) we are essentially quantizing the updates twice (once from devices to PS, and once from PS to devices). This double quantization will inevitably lead to larger quantization variance, and therefore slower convergence of the model, especially when we are close to the end of the learning.


+ The contribution is not clearly highlighted in the theory nor in the simulation.
The authors mention that "in Tang et al. (2019) the PS broadcasts quantized global model ... Instead, we propose broadcasting the global model update ... We remark that the global model update has less variability/variance and peak-to-average ratio than the global model..."
The authors indicate that, claimed improvements come from the fact that the model update has a smaller variance/peak-to-average ratio than the model.
I believe that this intuition is important in terms of differentiating this work among all model-broadcast-compression works.
Hence I would expect the authors to conduct corresponding experiments, and corresponding highlights in the analysis, showing that the variance/peak-to-average ratio of model updates are indeed $c$ times smaller than the model itself, and the gain (e.g. reduction of communication cost, reduction of computation iteration) is proportional to $c$.

+ The authors mention that "(some devices might not be able to participate all learning iterates) ... Our algorithm can easily be adapted to such scenarios by sending the global model, rather than the model update".
I would recommend the authors conduct another set of experiments, maybe in the future, to take random devices join/drop-out into consideration. 
There should be a join/drop-out probability thresholding, below which LFL is more efficient than the previous work, and above which LFL is less effective.
This would complete the picture of the 'scope' of LFL.

+ The contribution section is way too lengthy. Probably move the second paragraph to the related work section.

+ What is the architecture the authors used to conduct the experiments? And how the communication cost is evaluated?

review_title: Good but not good enough

final_score: rating: 5: Marginally below acceptance threshold
review_content: In the paper, authors propose a novel quantization algorithm to reduce the communication cost between server and clients in federated learning, where the communication are limited and unstable. In their method, both the global model and
the local model updates are quantized before being transmitted. The authors also analyze the convergence of the proposed algorithm under certain conditions and execute federated simulations to evaluate it. Results show that the proposed algorithm converge as fast as the lossless broadcasting with no accuracy degradation. 

The following are my concerns: 
1) In practice, it is not guaranteed that devices don't change in a certain amount of federated rounds. The proposed algorithm requires that the local devices have a good estimate of the global model, which is not true in real life. In this case, the server needs to send the global model to new devices. Since the target of the paper is to reduce the communication cost, the authors should perform experiments and investigate the effect of new participated devices. What is the upper bound of the new participated devices when this algorithm works better than other compared algorithms?

2) It is better to show the convergence regarding the computational time and communication time.  

3) There have multiple tasks more difficult than EMNIST and CIFAR10 in Tensorflow Federated, e.g. Stackoverflow.  MNIST and CIFAR10 is a little bit weak to prove the effectiveness of the proposed algorithm. 

review_title: More investigations are required for the applications of the algorithm in practical Federated Learning

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
This paper suggests a lossy federated learning (LFL) algorithm where the PS broadcasts a quantized version of the global model to devices. This approach helps reduce the communication cost of federated learning and is in particular useful when the communication bandwidth is limited. Associated convergence analysis is given to present the effect of lossy broadcasting on the performance of federated learning. From experimental results, it is shown that the proposed algorithm with (q_1, q_2) = (2, 2) shows almost the same performance as the lossless schemes while enjoying a considerably reduced amount of communication bits.

Reasons for score:
I vote for accepting. I totally agree with the importance and timeliness of this topic. My main concern is about the justification of the assumption and I hope that the authors can address this in the rebuttal.

Concerns:
- It would be better to explain the practical motivation behind the assumption that the devices transmit the lossless local updates to the PS focusing on lossy broadcasting only. For me, it is not clear how this assumption reflects the practical scenarios.
If the bandwidth of the communication channel between a device and the PS is limited by the amount that only can be achieved by quantization, can't we even do the iterations because the bandwidth required for device-PS communication exceeds the bandwidth limit for this channel?

- For Figure 1, it would be better if some reasons could be presented that the performances of LGM and LTGM tend to change differently over iteration for non-iid and iid data. I think this would help to understand the strength of the proposed method.



review_title: Nice work but concerns about the assumption

Meta-review: Although the reviewers acknowledge some contributions of the paper, it has some limitations on both theoretical results and numerical experiments. It is still unclear about the effectiveness of the proposed method. The authors should consider the following issues for the future submission: 

1) The justification of $\tau$ is not clear in federated learning with respect to communication efficiency (please see Reviewer 1’s comments).

2) The bounded stochastic gradient assumption is not applicable in the strongly convex case. This issue has been discussed clearly in [Nguyen et. al, “SGD and Hogwild! Convergence Without the Bounded Gradients Assumption”, ICML 2018]. Therefore, the constant G in Section 3.2. would damage the complexity bound since it could be arbitrarily large. 

3) Although the goal is to illustrate the benefits of the proposed quantization approach, the numerical experiments and the theoretical contributions are limited. The theoretical results are incremental from the existing optimization theory (both strongly convex and non-convex). Moreover, network architecture and data sets are not enough to justify the efficiency of the method. 

Decision: Reject