Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work theoretically studies the heterogeneous cross-silo federated optimization problem. Previously,  Mishchenko et al. [2022] had shown that SCAFFOLD with randomized number of local steps (which they call Prox-Skip / ScaffNew) enjoyed an accelerated communication complexity, proving improvement due to local steps. 

This paper extends their framework to employ variance reduction and compressed communication at the client level, while maintaining the accelerated communication complexity. They also propose an hierarchical federated model where clients are attached to always-available hubs for which their algorithms are particularly well suited.
strengths_and_weaknesses: # Strengths

1. The approach is well motivated and forms a natural line of inquiry - combining communication compression + variance reduction with ProxSkip. 
2. The results obtained by the authors, though not surprising in the light of ProxSkip, are significant and technically involved. It is a result of synthesizing several state of the art analysis techniques, and recover most of them as state of the art.
3. I also enjoyed the motivation of the local variance reduction via the hub model and can see it being useful.

# Weaknesses

Most of the weaknesses stem from poor writing (see questions section for detailed feedback) - i) section 4 is very terse and not elaborated well , and ii) the limitations of the method and comparison with prior work is not well carried out.
The most impactful aspect of this paper might be the new hierarchical FL model proposed. But unfortunately, there is almost no discussion on its unique aspects, optimality etc.
questions: # Suggestions for improvement

1. Section 4 is way too terse and hard to comprehend. The setting of the hub model and the algorithm description should be separated (perhaps with pseudo-code). I had to work hard to reconstruct what was being conveyed. E.g. of confusions: why is the global gradient a concatenation of estimators in eq (12)? control vector y_t is used before it is defined (in fact it is never properly defined or initialized) etc.
2. It is also unclear how Theorem 9 relates to Theorem 5?  Why can we not use VR and CC directly in Section 3 with Thm. 5? Thms 6 and 8 are definitely direct corollaries of Thm 5 and it would be clearer if stated as such.
3. More time should be spent explaining the results in Corollaries 1 and 2 - what is $\omega$ and how should we think about it? why does it scale as $\omega / M$ and is the optimal scaling? The latter relies on the independence of the compression randomness, which is not stated. Overall, I think the paper would greatly benefit from moving some of the exposition in Section 2 to the Appendix and instead expanding on the results in Sections 3 and 4, with greater discussion about the implications of the theoretical rates.
3. The result for the setting with C > 0 is not optimal since there is no speed-up wrt to number of clients. The optimal rate likely scales as C/M (as SCAFFOLD obtains).
4. Also, while client and data sampling are discussed in detail in Sec 1.2, their effect on ProxSkip-VR is never discussed.
5. It should be made clear that all the discussion in the paper is for cross-silo FL and does not apply to cross-device FL.
6. Nitpick (feel free to ignore): the colors used in the text (e.g. in math symbols like W and E in Thm 5, and algorithm names) made it visually busy, confusing and harder to read for me. I would suggest using such colors sparsely in text - more as a shorthand (e.g. red is always error terms) rather than for emphasis or drawing attention. 
limitations: The limitations of the method are not adequately discussed. The questions section above goes into detail.

Note: I am willing to raise my score on an assurance from the authors that the writing and presentation will be improved. The results are otherwise technically sound and interesting.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a new variance reduced variant to ProxSkip, called ProxSkip-VR, for federated learning. It possesses a combination of preferable techniques in federated learning including data sampling, client sampling and local training. The variance reduced estimator is general and covers numerous existing estimators. Linear convergence is proved for the strongly convex objective. More importantly, the paper take a closer look on the cost of training FL methods by incorporating local training cost and communication cost whereas most existing FL methods only consider communication cost in convergence results. Numerical experiments on regularized logistic regression is presented to illustrate the performance of ProxSkip-VR compared to existing methods.
strengths_and_weaknesses: Strengths:
- The paper is well-written. I can see the history of FL methods evolving over different generations.
- ProxSkip-VR possesses several important properties for an FL method: client sampling, data sampling, and variance reduced local update step.
- The paper proposes a new architecture for FL which contains hubs between server and workers. This architecture is reasonable and it represents many real-world applications.
- Convergence results are provided which cover different type of gradient estimators.
- The evaluation considers the total cost which consists of communication cost and local training cost which has not been considered in existing works. This also help show the advantage of using variance reduced estimator in local training.

Cocerns:
- Table 1 summarizes results of ProxSkip-VR w.r.t. existing works. It shows that communication complexity of ProxSkip-VR is better than GD but it does not explicitly discuss how it is better and the reader needs to go back and check the other paper to learn about this comparison.
- I do not see how the control vector $y_t$ is chosen in the proof of ProxSkip-VR (Theorem 5). I wonder if $y_t$ is chosen the same as in (11).

Minor comments:
- The experiments has a non-zero value for the penalty parameter $\lambda$ for $\{x\}^2$ regularizer but the code appears to set it to 0. I am not sure if the code precisely reflect the setting of the experiments described in the paper.
questions: - ProxSkip-VR assumes that the stochastic gradient $g_t$ is unbiased. Can the theory be generalized to biased estimators to cover this type of gradient estimators?
- Does the proof of ProxSkip-VR in Appendix C hold for any choice of $y_t$ or it has to be a certain choice so that $g_t$ satisfies Assumption  4?
limitations: With the definition of $r$ in (4), I think assumption 3 is not needed.
I hope to see more discussion on how to select $y_t$ in the main text.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigates applications of the variance-reduced technique in Federated Learning and proposed a new algorithm based on **ProxSkip** in [Mishchenko et al. 2022]. The method constructed by the authors can be substantially faster in terms of the *total training time* than ProxSkip in theory and practice in the regime when local computation is sufficiently expensive. The authors also corroborate their theoretical results through experiments.
strengths_and_weaknesses: **Strengths**
1. The proposed method **ProxSkip-VR** enjoys a lower communication complexity than gradient descent.

2. This paper proposed a new FL architecture, where ProxSkip-VR can be substantially faster in terms of the *total training time* than ProxSkip.

3. The authors corroborate their theoretical results with carefully engineered proof-of-concept experiments.

**Weaknesses**

1. The algorithm can be impractical since we can not control the communication timestamp.

2.  Attributing to combine L-SVRG [Hofmann et al., 2015, Kovalev et al., 2020a] and DIANA [Mishchenko et al., 2019] techniques, the improvement over ProxSkip is natural. Hence the novelty is limitted.
questions: 1. Table 1 says the communication complexity of **FedLin** is worse than GD. But the communication complexity of FedLin is also reduced by a factor of $H$ compared with GD, where $H$ is the number of local updates (see the discussion below Eq. (9) of [Mitra et al., 2021]). Therefore, the communication complexity of FedLin can also attain $O(\sqrt{L/\mu}\log(1/\epsilon))$ by setting $H = \sqrt{L/\mu}$.

2. In [Mitra et al., 2021], the authors show that FedLin converges much faster than SCAFFOLD in experiments of the linear model. However, the performance of FedLin in Section 5 is worse than SCAFFOLD and Local SGD, which is unreasonable since FedLin has a *linear convergence rate*. And I don't think the difference between logistic regression and linear regression is the reason. So I doubt the results in Section 5, could you explain the reason?
limitations: This paper identifies 5 distinct generations of LT methods and classifies ProxSkip and ProxSkip-VR in Generation 5: Accelerated Age, but I don't think the full-gradient and variance-reduced methods are practical and popular in FL. Considering large-scale machine learning models, stochastic gradient descent (and its variants) with the *constant batch size* is a prevalent training scheme. So the summarization in this paper may be less appropriate.

Considering existing works [Mitra et al., 2021] and [Mishchenko et al. 2022], the contribution and novelty are limited. More importantly, the experiment results are not convincing.
review_title: null

Meta-review: metareview: The paper proposes a new optimization algorithm for distributed learning with applications to federated learning. The results are interesting and I recommend acceptance. This paper benefited considerably during the author rebuttal phase and I strongly urge the authors to incorporate all the reviewer suggestions and the author clarifications in the final version of the paper. 
confidence: Certain
Decision: Accept