Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper offers a dropout approach to account for different client resources. The idea is simply through pruning the network where clients fit smaller networks. The papers also offers an approach called ordered dropout where end layers are dropped rather than random neurons. 
main_review: The paper idea is interesting. Below are my main concerns: 

1) Starting from the title the paper claims this approach induces fairness. How and why ? Having clients with less computational power train smaller models does not guarantee any fairness. Perhaps it might even hurt it. The authors needs to clearly define a measure of fairness and if not prove at least test how this measure is improved. Ex: is the distribution of accuracy across clients narrowed ? 

2) The authors are encouraged to check convergence. This idea of ordered pruning can induce bias in gradients, especially if clusters are imbalanced ! Will the method still recover a meaningful solution ?

3) The idea of clustering is strange. One would expect clusters to be done based on P_{y|x} at each client or perhaps P_{y,x}. The authors instead cluster and aggregate within clients of similar capabilities. What about heterogeneity is the data distribution ? what if clients is same clients (computation wise) are very different in data distribution

4) The authors need to benchmark with more models and personalization approaches.

limitations_and_societal_impact: none
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers system heterogeneity in federated learning where different devices may have distinct processing capabilities or network bandwidth. Prior work addressed this scenario by not considering lower-end devices or scaling down models to fit all participants. In contrast, this paper proposes a novel (ordered) dropout technique to dynamically prune a shared model without sacrificing accuracy. Unlike random dropout, ordered dropout induces hierarchical pruning, allowing for efficient training via knowledge distillation. The paper empirically validates the proposed method on various federated learning benchmarks, demonstrating superior performance over the state-of-the-art.
main_review: **Originality:** The paper proposes the first method addressing system heterogeneity in federated learning. To that end, the paper develops a novel form of dropout, which leverages a hierarchical structure to ensure good performance across a wide range of device capabilities. Related work is adequately cited.

**Quality:** The submission is technically sound, and the method is empirically validated on various federated learning benchmarks. However, the code was not submitted.

**Clarity:** The paper is clearly written and well organized. However, the section heading margins have been substantially decreased. I am not sure whether this is grounds for rejection (according to the [NeurIPS 2021 Style Files](https://media.neurips.cc/Conferences/NeurIPS2021/Styles/neurips_2021.pdf)), but it significantly reduces readability and should be changed.

**Significance:** Unlike prior work, which does not consider system heterogeneity or resorts to suboptimal approaches such as dropping lower-end devices or downscaling the shared model, the proposed method embraces heterogeneity. Consequently, the proposed technique is simple yet elegant and provides a practical solution to a relevant problem in federated learning.

**Questions**

- How do ordered dropout and knowledge distillation ordered dropout compare in terms of running time? Knowledge distillation might be significantly more expensive since it always evaluates the largest possible model.
- How do you achieve good accuracy with $\alpha = 1$ where the loss consists entirely of the KL divergence term?
- What do $U$ and $V$ correspond to in Theorem 1? After reading the proof, I assume that they denote the network layers, but the reader should not have to guess.
- How do you evaluate federated dropout or extended federated dropout on devices with low capabilities? While random dropout prunes neurons during training, these neurons are all present at inference time.
limitations_and_societal_impact: The paper fails to discuss potential negative societal impacts within the page limit (as required by the [NeurIPS blog](https://neuripsconf.medium.com/introducing-the-neurips-2021-paper-checklist-3220d6df500b)).
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposed a scheme for training deep models in the setup of federated learning, where updates to different nested submodels can be trained at different clients with different hardware capabilities.

(+) I appreciate solid grounding in practical motivation with potential significant practical value, and I would love to see further works in this direction.

(-) I feel execution on these ideas is not good enough, especially in terms of matching empirical baselines. 
main_review: ### Presentation

Overall, the paper reads well, clearly describes relation to prior work, and its contributions. I only have minor comments and suggestions for improvement.

One detail in presentation I found confusing is in Sec 1-3 is whether the target impact of this work is on training or deployment for inference. In some way both, but I think these two points are somewhat confusingly entangled and may be worth explicitly separating as two distinct values delivered.

In Fig 2, I find the visualization misleading. The two diagrams for p=0.2 are networks functionally equivalent with respect to permutation of activations. I believe the crucial feature of proposed approach is the relation in line 113, and should be promoted in the narrative. I see it as the main originality / novelty, and while the idea may seem simple, I think it is very important.

Lines 81-83 I don't get the comment about computational benefits. No matter how random neurons are sampled, in the setup you have, you can still represent the model forwards / backward pass using dense matrix multiplies of smaller size. 

Sec 3.1, the focus on layers when explaining the idea seems confusing to me, as it primarily impacts how adjacent layers interact. Moreover, the presentation seems to apply only to something that would fit into tf.keras.Sequential, but really is more general. 

Sec 3.3 feels quite disruptive in the overall flow. I would either move it completely to appendix, leaving just a brief shoutout, or include more details about what this actually means. U, V are for instance not even defined, and I can't really understand what you try to say without looking at the appendix.

In Alg 1, server already makes a decision about what submodel to send to a client ( p_{max}^i ). If that is already the case, why not also include the sampling in the server's decision and save some communication? [I now see this would not quite work for KD variant]. Perhaps look up how could the story be improve with PIR here [your 31, Sec 4.2.1].

Eq (2) - I think this is a problem only if you are aggregating the updated models. If you instead aggregate the model updates (difference between initial and updated model), this would not be a problem (?) Similarly, paragraph in line 201+ seems not relevant afterwards (?)



Fig 4/5 have overlap in the same data (FjORD w/ KD) but different color. That is confusing.

### Experimental evaluation

Major problem I see is lack of focus on recovering solid baseline model quality.

In Fig 3. I would like to see additional baseline, which should make a strong case for the OD idea and highlight why line 113 is important. That is, take the SM p=1.0 model, and create random submodels from it for smaller p values. I would expect the model quality to be below the OD line. **Could you please include this in response?**

For CIFAR 10 dataset partitioning, I would like to see something else than uniform split. See perhaps "Reddi et al, Adaptive Federated Optimization" for ideas. But even then, I would be looking more at the other two datasets.

Somewhere, I would in more detail explain how to apply the idea to RNNs, I think that is not at all intuitive.

The major problem I see is in Fig 4/5. The accuracies are significantly below baselines (omitted from these figures). Baselines presented in Fig 2 in this paper (!) and also other works, for instance in mentioned "Reddi et al., Adaptive Federated Optimization". I see this as a significant problem for this work which is focused primarily on the practical side of things. 

If you are able to almost match the baselines for p=1.0, and have this additional message that submodels are readily available, that would be a very strong message to me. As is, it appears as collection of regimes that do not quite work, yet.

### Ideas for improvement

I would mainly focus on narrowing the gap from existing baselines.

I like the messaging around device heterogeneity. What is completely missing, is that the device hardware is likely going to correlate with the data available to it. I think if you took a richer dataset, maybe stackoverflow which contains lot more information based on which to partition the data, you could create a setup when comparing full model trained on a single cluster, and FjORD trained model on two (or all) clusters. There is a chance that creating really strong contribution would be easier with such larger / richer dataset, than it is with the simple datasets used in the current submission.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper develops new techniques for tackling system heterogeneity (i.e., diversity in the processing capabilities and network bandwidth of clients) in federated learning. The paper highlights the practical issue of system heterogeneity in federated learning that is often ignored in many papers. All the reviewers agree that the paper has interesting ideas and solves an important problem, and are in favor of accepting the paper. Along with data heterogeneity, systematic study of system heterogeneity can potentially have significant practical value and can be of interest to a wider audience. I recommend acceptance of the paper. I suggest the authors address the concerns of the reviewers in the final revision.
Decision: Accept (Spotlight)