Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a dropout based method towards communication efficient federated learning, where each client will compute the dropout probability based on the update similarity between local models. The experiments show that with fewer FLOPs than traditional federated learning algorithm, FedDrop can achieve the same accuracy.
main_review: Pros:
1. This similarity based dropout technique to reduce communication cost in FL is new, and the authors proposed novel algorithm to approach it.
2. They also did sufficient experiments to empirically validate their method.

Cons:
1. I think the writing and organization can be improved since I am not very clear about some technical details, which I will talk about below.

Questions:

1. I am confused about  $\boldsymbol{p}$ and  $\boldsymbol{p}_c$. I was wondering for $\boldsymbol{p}$, do we optimize a single $\boldsymbol{p}$ or for each client c, we compute a  $\boldsymbol{p}_c$? 

2. It seems that the constraint $g(\boldsymbol{p})$ is a combinatorial function since it contains the number of channels. How do you optimize on it?

3. For the experiments, I expect to see FedDrop can converge faster than FedAvg or SCCAFOLD in terms of the wall clock time since the main advantage of it is to reduce model size and hence speedup training.
summary_of_the_review: Overall, the idea of this paper is new, but I think this paper can be better organized to make reader easier to understand the technical details. If the authors can address my questions, I am willing to change my score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new method where local workers will drop part of their model using a shared dropout probability received from the server at each communication round. The dropout probabilities are computed by solving an optimization to promote similarity across agent's update. Compared with popular baselines in federated learning, the proposed method demonstrates better performance in terms of number of FLOPs.
main_review: The papper consists of following strengths and weaknesses

Strengths:
- The dropout mechanism is simple yet effective in deep learning. It is interesting to see how to use dropout to design new federated learning algorithm.
- Extensive numerical experiments verify the advantage of FedDrop.

Weaknesses:
- The paper lacks discussion on the convergence of the algorithm.
- The paper only shows experiments with neural network examples. I wonder how the methods perform with models that are not neural networks.
- The algorithm requires to solve an extra sub-optimization problem. The cost of solving this problem has not been well-discussed in the paper. In FL, with large number of clients, i.e. the dimension of q also grows. I am concerned about the efficiency of solving this subproblem while other baselines such as FedAvg/FedProx do not need to have this additional step.
- Keeping the algorithm in the appendix reduces the clarity of the paper.

Questions:
- As FedAvg does not work well with heterogeneous data, I wonder whether FedDrop also suffers in such setting as the update of FedDrop is very similar to FedAvg.
- Also, do we expect the same convergence guarantee as FedAvg?

Minor comment:
- There should be square in equation (6) as it is MSE not RMSE.
- In theorem 2, there should be description for the dot product, typo at \Delta \theta^n_j
summary_of_the_review: I believe the paper contain notable contribution in designing new algorithm using dropout. Numerical experiments illustrate the practical performance of the proposed algorithm However, the proposed lacks discussion on the convergence of the algorithm while other methods like FedAvg/FedProx do have guarantee. The proposed methods appear to only work directly with neural network models, there should be more discussion on other types of model.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes FedDrop and a synchronized drop-out strategy to reduce local computation during the training of FL models.
main_review: - The premise of the paper that other works actually over-emphasize communication, while local computation is as time-consuming is a bit misleading. I agree with the fact that the act of communicating information, i.e. sending the updated model parameters over the channel might not take so long. But this is not the only factor defining the time that each communication round takes in FL. There is a lot of overhead associated with each FL round: 1) select an available device (usually connected to wifi and power) 2) make sure the device does not become unavailable,... 3) collect enough updates from enough devices each with their own delays (depending on the loads, computation power...); note that here we are constrained by the slowest device. All these factors actually add a lot of overhead to each FL round. So just looking at the communication piece without seeing this bigger picture is misleading. In fact, all the methods that are compared against are targeting the reduction of the number of rounds and not communicated bits; if communicated bits were the target, the authors should have compared against methods that directly target that, e.g. by compressing the updates. 
- The theoretical results that are presented by the paper are very weak. Their statements are misleading/sloppy or wrong and lack assumptions. And to be honest the theorems should not be called that.
  - Theorem 1: This requires Assumptions 1-2 which are very strong and definitely not true for all the layers. And the result under these assumptions is trivial.
  - Theorem 3 is just obvious!
  - In Lemma 1, there is no reasonable justification to drop the Hessian term. It cannot be justified and all the approximations based on that are not valid. Note that Lemma 2 and Theorem 2 are built on top of the closeness of this approximation! Finally, although the results are presented for gradients, there is a big leap when using this in practice, where the updates are actually the accumulation of multiple steps instead of gradients.
- The algorithm is impractical and possibly not very useful in many cases:
  - No secure aggregation can be integrated into it, while many FL systems require secure aggregation.
  - The steps on adjusting the drop-out probabilities are computation/memory/communication intensive. First of all the computation there scales with the number_parameters x batch_size^2. which with large batch sizes in practice could be too much. More importantly, it will require the server to track p's for all the clients which is not possible in large-scale applications. The other alternative is that the clients keep sending the server their p's which will increase the communication as the size of p's is large. In fact, I suspect for large-scale realistic problems with many clients and a low percentage of participation per round (which are mostly absent from the experiments) this stateful situation would not necessarily lead to any benefit (as the clients' p's are updated so infrequently). I believe that is why in the case where there are 1000 clients and 1% participation the authors have had to resort to choosing the same clients for two consecutive updates; see appendix F.5. One possible issue with this is that it is not possible to make sure that the same set of clients are available for two consecutive updates due to external situations (clients may become temporarily unavailable at any point during the training). 
- The experimental results are not convincing and I do not think the gains are significant enough.
  - The method is only tailored and only tested on CNNs while many FL problems do not use them. This has made the experimental section less convincing as there are many usual FL benchmarks that are absent.
  - Flops are not easy to estimate and most of the reported results are in terms of FLOPS. While even the authors' estimates of actual FLOPS savings show that the theoretical numbers used for FLOPS (as the x-axis in many figures) could be as much as 1.5x worse; see table 9.
  - There are only a few plots comparing the rounds, while that is important. In fact, there is actually only one plot (Fig 18) that compares FedDrop with another method FedAvg over the number of rounds. And in that plot, it is clear that FedDrop cannot achieve the final accuracy of FedAvg with low r (which is the setting that has gains based on other plots). And in order to achieve similar final performances to FedAvg, FedDrop has to run with r=0.75 or higher which does not seem to result in any significant gain (in other metrics).
  - I noticed that the results that show a significant gain for FedDrop, e.g. Fig 4, actually use very low E; compare Fig 4 to Fig 8, where E=8. Note that large E is essential in getting good results in FL. Also, this is very unfair to other methods as their only tool in reducing the communication rounds is local computation; while FedDrop is additionally using r! Based on this I do not believe the authors have done a fair comparison. It is worth noting that in many of the plots it seems that running the other algorithms for a longer time could also result in better results than FedDrop (e.g. see Fig 15); Interestingly, even in this case Fig 16 shows a large gap in favor of FedDrop which is due to the use of low E as well! Unfortunately, I do not think the authors use good criteria to stop the algorithms (e.g. when they have converged).

======= After Rebuttal =======

I do not think the authors' response addressed my concerns.
- Around the theoretical results: my original comment was around the fact that just stating some theoretical results with assumptions that are not realistic or verified does not add to the paper's value. Moreover, the results in Theorem 3 are obvious. And the term Theorem is reserved for significant contributions and does not apply here. Also, the authors did not provide any meaningful justification for the approximation in Lemma 1 (and the divergence from theory where there are multiple local steps).
- For the theoretical results: As other reviewers have also mentioned, the empirical results are quite weak. And as I mentioned in my original review they are not fair (not running the algorithms for long enough, not allowing larger E for other methods, ...). Unfortunately, the authors did not properly address these issues in their rebuttal. Please refer to my original review for detailed issues regarding the empirical results in the paper.
summary_of_the_review: Based on the above comments, I do not believe this paper passes the acceptance threshold. I encourage the authors to address the points around: motivation, practicality, and rigorous experimental comparisons with other works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a new method of coordinated, per client and weight dropout for federated learning. The intuition behind the method is to increase the dropout probability (probability of having a weight set to zero) for weights where different clients often have opposite parity gradients (as when those gradients are summed together are likely to cancel each other out). The authors show that doing this can reduce the computational cost on clients of FL by up to 3x.  
main_review: Strengths
- The paper tackles the problem of computational cost to the clients, which is relatively understudied compared to the communication costs. 
- The technique does not make any simplifying assumptions and is applicable to real world FL use cases. 

Weaknesses
- The method proposed comes with increased communication costs to the client. While the authors show that they can favourably trade communication costs for computational costs, generally practitioners are more concerned with communication costs, as these can impose real costs on the users (such as using up limited wifi resources), whereas computational costs are largely in training time which are 'paid' by the server. 
- The results here are very specific to computer vision. Would similar results be possible for other problems such as NLP?
- The log graphs in figure 5 are odd and challenging to read, with different spacing applied to the x and y axis. 
- In figure 5.c how is FedDrop able to achieve lower communication costs than FedAvg?
- The results in table 1 are a little difficult to interpret. If I understand them correctly, they indicate the computational cost of different method to reach a given accuracy, under the constraint that they keep below a certain communication budget. If this is correct, it would be much more valuable to the reader to record the actual communication costs of each method as well as their computational costs. Simply saying that all methods stayed below some budget may be hiding important information about the additional communication costs of FedDrop. 
- Empirical results appear quite weak, with a 10x - 100x increase in the communication costs resulting in less than a 10x reduction in computation costs. 
summary_of_the_review: While reducing client computational costs is an important task in FL, the method proposed in the paper comes at a very high communication costs, which makes it unlikely to be practically useful while communication costs are still the primary concern in FL.
review_title: null

Meta-review: The paper introduces drop-out probabilities which are adaptive to the similarity of model parameters between clients.
The reviewers liked the idea, however missed several aspects, such as a convergence analysis or at least discussion, as well as an analysis of additional cost of the adaptive step, and finally several concerns on the strength of the experimental setup and benchmarks.

Unfortunately consensus among the reviewers is that it remains below the bar even after the discussion phase.

We hope the detailed feedback helps to strengthen the paper for a future occasion.
Decision: Reject