Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces the idea of progressive training of deep networks for federated learning, where only some layer blocks are trained initially and the remaining blocks are progressively added, in order to reduce both local computation cost and communication cost in the early stages (as there are fewer weights). The authors provide a convergence proof of this approach, showing the same asymptotic convergence rate as plain training.
Numerical experiments are conducted in EMNIST, CIFAR-10/100 and BraTS, split either in an IID or non-IID fashion and representing either a cross-device or cross-silo setting. Numerical experiments show a highly architecture-dependent reduction in the computation cost in the centralised setting. In the federated setting, communication gains significant communication gains are also achieved. Finally, the authors show that progressive training is compatible with other compression methods, increasing the gain in communication cost.
main_review: # Novelty & Significance:

- The idea of progressive training is not new, and the authors cite in particular Karras et al 2018. Given the importance of the topic in the paper, I would have appreciated a paragraph devoted to it in the related work section.
- Theoretical results follow a previous proof structure but seem to bring some novelty. Their significance is not that big insofar as the paper is concerned with deep learning, for which convergence rates do not play a huge role (in particular, the learning rate schedule is chosen independently of the rate derived). Further, the final result is that the convergence is at worst twice slower than the baseline, which is a simple consequence of the choice of spending at least half of the training budget on the full network.
- The experimental results show that the idea can bring some computational and communication savings, in a variety of contexts (cross-device/silo), and is compatible with other approaches.
    - Re computational gains, the benefits seem highly dependent on the architecture (cf fig 3), which reduces its significance.
    - The proposed approach seems only to bring very modest gains with respect to a « random » approach where one would train random sub-networks (cf Table 5). This reduces the significance of the results.

# Writing & Clarity:
- The paper is well written and the main idea is way conveyed.
- However, notations could be simplified (e.g. page 4 the notation $x_{t, E_s^c}$ is introduced but never used) to facilitate understanding
- I would suggest using a log range for the compression factor axis on figs 6a and 6b.

Here are a few minor typos:
- Page 4, paragraph training of progressive model, there is a typo for $T_S$, I think the correct value should be $T (S+1) / 2S$
- Circular notations for the theoretical analysis (end of page 4) for $s = \min(S, t/T_s)$
- End of sec 4.5, missing « is » easy to implement
- Proof of lemma 2, page 13, the first update equation is probably missing a $\gamma_t$ before $g_t^s$ 

# Quality & Correctness:

## Theoretical results:

- I did not check the details of the proof of Theorem 1.
- Regarding the results, the choice of learning step $\alpha_t$ seems to be hardly usable in practice, as it relies on the knowledge of both the full gradient and the gradient of the sub-network.

## Empirical results

Computation reduction;
- I am not sure to completely understand the metric used in the x-axis of Fig 2, in terms of unit used. Is it the total number of FLOP (i.e. the number of floating point operations over time integrated along time)? 
- Why isn’t BraTS reported as well for the computation cost reduction benchmark?

Communication reduction:

- Which architecture is used for the results reported in Fig 4 and 5 for the classification tasks? Additional results are reported in Appendix for varying architectures, but it would be nice to precise it in the main text
- For multiple experiments, the authors average results over 3 seeds, which is a good effort towards reproducibility. Would it be possible to perform 5 runs in order to get stds ? Otherwise, to have access to the individual values?
- There are some instabilities at each step transition (cf Fig 5), and I suspect that warm-up seems to play some role here. The paper is silent about this aspect there were no ablation studies or investigation on this particular ingredient. I would have appreciated a focus on this part rather than e.g.
summary_of_the_review: This paper introduces an existing scheme into the federated setting, and provides an experimental proof of the gains it brings in terms of local computations and communication. Despite some minor issues which can be fixed, I think this paper could be accepted.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors adopt the progressive training technique to accelerate the training process federated learning. The authors also establish the convergence rate of the proposed algorithm. Extensive experiments demonstrate the efficacy of the proposed algorithm.  
main_review: It is an interesting work on accelerating the training process of federated learning.  The reviewer still has several concerns about the current submission:
(1) It seems that the main benefit of progressive training for federated learning comes from the early stage during training.  Hence, we recommend the authors do more ablation studies on the hyperparameter $S$. 
(2) For different stages,  how do the authors set the hyperparameters, such as learning rate.  Since in different stages, the depth of subnetworks is differents,  the hyperparameter tuning techniques may highly influence the training speed and final performance.
(3) Theorem 1 provides the convergence of the proposed ProgFed.  However, the convergence results do not indicate the benefit of progressive training for federated learning. 
(4)  The experiments should be strengthened.  The main optimizer in ProgFed is fedavg.  The authors should incorporate the proposed ProgFed with several other types of local opitmizers, such as fedprox, scaffold, etc., to further show progressive training can be a versatile and strong technique for accelerating federated learning. 
summary_of_the_review: see the comment above.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The issue that this work attempts to solve is that of computation and communication efficiency in federated learning. This is realised via ProgFed, a method that progressively trains neural network blocks of layers in $S$ “stages”. For the first $S - 1$ stages only a subset of layers is selected to be optimised, with the help of an optional (depending on the architecture) additional head to provide the training signal (which is discarded after that particular stage is finished). At the last stage, the authors propose to fine-tune the entire architecture in an end-to-end manner. Due to the specific nature of this form of training, the first $S-1$ stages of training require less compute (due to not needing to perform the forward / backward passes on the layers not selected) and also less communication (as the clients and server only need to communicate the specific set of layers that is optimised). The authors prove that such a training procedure converges in a rate similar to the one of standard end-to-end training and demonstrate in extensive experiments the benefits of ProgFed. As an extra bonus, the authors also show that ProgFed is more amenable to compression / quantization of the federated messages, thus showing that the benefits of these, more traditional, approaches are additive to the ones of ProgFed.
main_review: This submission is good; the paper is well-written, the idea is simple and seems to work well in practice. Furthermore, the experimental evaluation is thorough and considers multiple datasets and architectures. There is also a nice bonus that the proposed method is orthogonal to more traditional approaches that target communication cost reduction. For this reason, I am leaning towards recommending acceptance.

Having said that, there are some things that I would like some input from the authors:
- It seems that currently you throw away the auxiliary heads obtained during the progressive training phase. This seems like a waste; why not reuse these heads for inference? For example, one could argue about some “voting” between the heads or even “early exiting” of datapoints if an early head is confident enough about the prediction (this would reduce the computational complexity at inference time as well).  Does the performance of each head become worse after the end-to-end fine-tuning?
- While the provided proof is welcome, unless I am missing something, it seems to be in the centralised setting. Can it be extended to the federated setting? As the main motivation of this work is the federated setting, it makes more sense to prove convergence in such scenarios. 
- In the experiments you report the mean after three experiment runs. Why not show the standard deviation / error as well? This will allow one to better judge the significance of the results. Currently it is a bit unclear.
- In Figure 2 it is weird that the end-to-end training has a bit of instability that is not present in progressive training. Could you elaborate on why this is the case? Furthermore, at Figure 5 ProgFed seems to have quite some aggressive dips in performance (I guess when switching stages). This is especially pronounced at CIFAR 10. Could the authors expand upon this and whether such instabilities can be hindering in practice?
- Do you have any indication or intuition as to why progressive training helps with quantization / compression?
- For section 4.5; does the “Layerwise” strategy use only one head, i.e., the one at the end? If yes, why not use a separate head (i.e, such as ProgFed)? How does Layerwise + end-to-end fine-tuning perform compared to ProgFed? Furthermore, the difference between ProgFed and “Random is small”, so some standard error indication would help.  Finally, the “Random” strategy is missing from Figure 8 and it would be great if you could elaborate on what is the extra memory that “Random” needs.

As for other minor things:
- The plots such as the one at Figure 3 are kind of confusing and not very clear. I would suggest that the authors convert them to bar plots (such as the ones they have in the appendix) instead. 
- There is a reference that is listed twice (the “Sparsified SGD with memory”)
- “Layerwise” referred to as “Laywise”

summary_of_the_review: Good submission with a simple idea that seems to work well in practice. Extensive evaluation and nice compatibility with more traditional compression and quantization. There are some points that I would like some input from the authors which, if turned out positive, would strengthen this work further. For this reason, I am leaning towards acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces "ProgFed", which is an algorithm designed for federated learning scenarios. 

ProgFed applies the idea of progressive training. Instead of training the neural network from end to end, it first trains the shallow layers, and then gradually train the deep layers, hoping that: 1) training the shallow layers first will learn some simple and meaningful features which will help training the deep layers, 2) and thus reduces the communication cost for the federated learning applications. Besides, the ProgFed algorithm also applies the local steps (Local-SGD or FedAvg) in order to decrease the communication cost during the model training. The ProgFed algorithm works not only for the feed-forward neural nets but also the U-nets, which consist of an encoder and a decoder.

For the theoretical part, the authors show that ProgFed has similar convergence results compared with SGD.

For the empirical (experimental) part, the authors use experiments trying to show the superiority of ProgFed over other existed federated learning methods, e.g. the trivial end-to-end training procedure, the communication compression methods (e.g. quantization)
main_review: Please see "Summary Of The Paper" for the overview of the paper.

The paper introduces "ProgFed", which is an algorithm designed for federated learning scenarios. The authors use theoretical and empirical results trying the show the superiority of ProgFed over other federated learning methods when applying to neural networks. However, I think that there are several weaknesses in this paper.

1. The first weakness (major weakness) comes from the  "algorithm" part. If I understand correctly, the novelty of ProgFed is applying the progressive training technique into the federated learning setting. However, progressive training is an existed method trying to speed up the neural network training in the single machine setting. In the single machine case, it is easy to apply progressive training techniques with different optimizers, e.g. RMSProp, ADAM, SGD, or other optimization algorithms. In the federated learning setting, it is also natural to apply progressive training with other federated optimization algorithms, e.g. local methods like FedAvg (Local-SGD), SCAFFOLD, FedPAGE, or compression schemes like quantization, Sign-SGD, etc. For ProgFed,  if I understand correctly, it just applies the progressive training technique with the Local-SGD algorithm. Thus the first weakness comes from the algorithmic novelty perspective.

2. The second weakness (major weakness) comes from the model and the theoretical analysis. The data heterogeneity is the most important aspect that differentiates federated optimization from distributed optimization. If the data on different clients are not iid, then the gradients on different clients are not the same. In ProgFed algorithm (Algorithm 1) Line 16, the algorithm uses local update $x_{c,j+1}^s = x_{c,j}^s - \eta g_c^s(x_{c,j}^s)$ for stage $s$, client $c$, local step $j$. Here, $\nabla f_c(\cdot)$ should be different in the federated learning setting. However, in the assumption part and the proofs, I do not see any assumptions to control the data heterogeneity (like $(G,B)$-BGD). Based on the fact that FedAvg and Local-SGD need assumptions like $(G,B)$-BGD to guarantee the convergence, I believe that either the model does not consider data heterogeneity (which is a main drawback for the federated learning applications), or the proof needs to modify in order to support data heterogeneity.

3. The third weakness (minor weakness) comes from the empirical part. For the experiments, the authors compare ProgFed with very straightforward optimization (end-to-end) and several compression schemes. However, as I stated previously, ProgFed actually consists of two modules, progressive training and Local-SGD, which behave at a different level. Directly comparing ProgFed with end-to-end training does not show the effectiveness of ProgFed, I suggest the authors add more experiments, such as ProgFed vs Progressive training + simple SGD, to demonstrate the effectiveness of local-steps with the existence of progressive training, or ProgFed vs Progressive training + quantization, to demonstrate whether the progressive training combines better with local steps methods or compression methods, or ProgFed VS Local-SGD, to show the power of progressive training. Besides, I think the data split for different datasets can be moved to the main content.

Please point out if my understanding is wrong, and I will consider raising my score if my concerns and questions are addressed or answered. 
summary_of_the_review: In summary, I have the following concerns:

1. The proposed ProgFed algorithm seems a little bit incremental, since it seems like an "A+B" method where A is progressive training technique and B is FedAvg (local-SGD).
2. For the model or the theoretical analysis, either the model does not consider data heterogeneity or the theoretical analysis needs to be modified.
3. (minor concern) ProgFed is a combination of two techniques, and comparing with compression schemes like quantization is not very fair.
review_title: null

Meta-review: As pointed out by some reviewers, the proposed method basically puts progressive training in the federated context. The theoretical analysis only concerns the centralized or non-federated setting and thus give no insight or guidelines for progressive training in federated learning. The main advantage of saving communication mainly comes from the simple observation that less parameters are computed and communicated during each round before the full end-to-end stage. However, this may cause extra overhead in hyper-parameter tuning including number of stage, learning rate schedules and stage-wise warmup. Despite its potential effectiveness in practice, the current version of the paper falls short of the acceptance bar due to the weakness in novelty and relevant theory for federated learning.
Decision: Reject