Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a framework MIME to convert centralized optimization algorithms to the federated learning setting. The key components are some control variates to reduce the effect of data distribution heterogeneity. 
Contribution:
1. A framework to convert centralized algorithms to the federated learning setting.
2. Theoretical analysis to characterize the convergence of converted algorithms
3. Experiments show MIME framework can have better performance than FedAvg.
main_review: Strengths:
1. The convergence rate of converted algorithms matches their centralized versions.
2. MimeMVR provides an improved convergence rate assuming small Hessian variance. This is an interesting theoretical result.
3. The algorithms converted by Mime show strong empirical performance.

Weaknesses:
1. Since the 'breaking the lower bound' contribution is highlighted in the title, this point may deserve more discussion. More specifically, it will be helpful to discuss some technicality on how to use the Hessian variance to improve convergence rate and why centralized algorithms cannot achieve such a rate.


--------------after rebuttal-------------
My concerns are addressed.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes MIME, a general algorithmic framework for federated learning (FL) that can adapt to (and match the performance of) arbitrary centralized algorithms like Adam, Momentum SGD, and SGD. The authors show that via the MIME framework the convergence of any centralized algorithm can be translated into the convergence of the algorithm in the FL setting. The authors also propose a momentum-based variance reduction (MVR) algorithm that the authors claim to be faster than any centralized algorithm. Finally, the authors conduct extensive numerical experiments to show that the algorithms under the MIME framework perform well on real datasets.
main_review: Overall the paper is well written with a clear presentation. The ideas presented in the paper are significantly original and of importance to the research community. However, there are a few issues with the paper, predominantly with the technical content of the paper which the authors should address. The detailed comments are listed below:

1.	Theorem I (Corollary II and III): It seems that there is a technical issue with the results presented in Theorem I which then affects the results presented in Corollaries II and III too. Please clarify the following issue. 

In the proof of Theorem I, the authors have used the fact that $\sum_k \nabla f_i(x; \zeta_{i,k}^t) = K \nabla f_i(x)$ (in Lines 873 and 877 of the supplementary material) which follows from assuming $K$ to be the number of epochs.  This implies that either $\zeta_{i,k}^t$ are sampled without replacement or $\zeta_{i,k}^t$ represents the full data, i.e., $\nabla f_i(x; \zeta_{i,k}^t) = \nabla f_i(x)$. In my understanding, this means that the stochastic gradient is not an unbiased estimate of the local gradient (or it is the full gradient). However, in Assumption (A3) this stochastic gradient is assumed to be an unbiased estimate of the local client’s gradient. The proof Theorem I (via Lemmas 7, 8) and Corollaries II and III rely on Assumption (A3) which might not hold if $\sum_k \nabla f_i(x; \zeta_{i,k}^t) = K \nabla f_i(x)$, as in my understanding Assumption (A3) and $\sum_k \nabla f_i(x; \zeta_{i,k}^t) = K \nabla f_i(x)$ both cannot be true at the same time. If my observation is correct the proofs of Theorem I and Corollaries II and III do not hold with the stated set of assumptions. Please clarify. 

2.	Assumptions: Note that the linearity of the update $\mathcal{U}(g_1 + g_2) = \mathcal{U}(g_1)  + \mathcal{U}(g_2)$ in Algorithm 1 (and Theorem I) might not hold in general unless $g_1$ and $g_2$ come from the same round of Algorithm 1. This can be seen from the fact that for adaptive algorithms like Adam updates are not linear in $g$, however, since the adaptive step is fixed at the start of the round, linearity will hold, but $g_1$ and $g_2$ must be generated within the same round. Please update the assumption accordingly.   

3.	Speed-up over centralized methods: The authors claim that MIME with MVR beats the lower bound for centralized methods, thus breaking a fundamental barrier. These claims are a bit misleading as the lower bounds corresponding to the centralized algorithms are on the computations, whereas the authors measure the total communication rounds required to reach an approximate stationary point, wherein within each round the clients compute multiple gradients. MimeMVR required total communication of $O(1/\epsilon^{3/2})$, however, it is well known that for FL problems better  $O(1/\epsilon)$ communication requirement can be achieved. 

4.	The authors should include Assumption (A3) in the main text of the paper as it is important and $\sigma^2$ appears in the statements of Theorems and Corollaries. Moreover, the assumption $\mathbb{E}_i [\nabla f_i(x)]  = \nabla f(x)$ is not stated in the paper, however it is being used in the proofs.  

5.	The bounded Hessian variance and L-smooth assumptions (Assumptions (A2) and (A2*)) are strong assumptions as they are made on the stochastic samples of the local client’s data. In fact, (A2) loosely forces the data at each client to be homogeneous. Generally, for FL problems (A2) is not required and a weaker version of L-smoothness (A2*), namely, mean square smoothness is required if some sort of variance reduction is used. It seems the analysis relies on these stronger assumptions. The authors mention that Hessian similarity is crucial for federated optimization and refer to [6], however [6] considers a convex problem that is different from the non-convex problems authors tackle. Please clarify.  Moreover, the MIME framework relies on computing the full gradients of the sampled clients at each round which seems to be a stronger requirement compared to existing FL algorithms.   

6.	In the discussion of Theorem IV the authors discuss that if $\delta \approx 0$ then MimeMVR requires $O(1/\epsilon)$ communication rounds. However, the statement of Theorem IV requires $K \geq L/\delta$, which implies as $\delta \to 0$ we will have $K \to \infty$. What implication this will have on the performance of MimeMVR? 

7.	In the Appendix, the authors mention that Mime MVR does not exactly fit the MIME framework as it relies on gradient computation at two consecutive points. I think instead of just including the convergence result of the MVR in the main paper, the authors should also include the MVR algorithm in the main paper since it seems to be a non-trivial construction.   Also, in Table 5 it would be helpful if the authors can add the tracking step used by the Mime framework rather than the tracking step of the centralized algorithm. 

8.	Experiments: 
The authors have conducted sufficient experiments to validate the proposed algorithms. A few concerns are discussed next. In the Experiments section, from Figure 1 it seems that Mime and MimeLite clearly outperform the rest of the algorithms, however, in Table 1 the reported performance of Mime and MimeLite is very close to other algorithms. Why is this happening? 
Moreover, it seems that Mime and MimeLite compute more stochastic gradients per client compared to FedAvg between two communication rounds. If this is true isn’t it true that the improved performance of Mime framework is expected? 

9.	Typos and minor issues: 

$x^{\text{out}}$ in the statement of Corollary II is not defined. 

Line 832: Replace $(\mathbb{E}[X - \mathbb{E}[X]])^2$ by $\mathbb{E}[X - \mathbb{E}[X]]^2$

Line 853: The inequality is in the wrong direction. 

Expression in the statement of Lemma 4: Please use braces with the l.h.s. term to show that the sum over $i \in \mathcal{S}$ over the complete term. 

With the proofs of Theorems, Lemmas, and Corollaries the authors should explain the reasoning behind inequalities (and equalities). 

Line 974-975: Please state the tracking step for MimeAdam and MimeLiteAdam. 

The authors first use $e^t$ to denote the perturbation in the update direction of the centralized algorithm and then later in MVR for denoting the error in server momentum. Please use a different symbol for each if possible.

limitations_and_societal_impact: None noted.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a new generalized algorithmic optimization framework named MIME for adapting and analyzing the convergence of any optimization algorithm applied in centralized settings into cross-device federated learning environments. The algorithmic reduction is accomplished by decoupling the centralized optimization algorithm into optimizer (server-side) and parameter state (client-side) updates in federated settings. The convergence of the proposed adaptation is shown both theoretically and empirically over a range of challenging real-world datasets for different optimization algorithms. Interestingly, when applying the proposed federated adaptation for a specific momentum-based optimization algorithm, the adaptation is proven to be asymptotically faster than its centralized counterpart.
main_review: **Pros**
-	Interesting adaptation of any centralized optimization algorithm in federated learning settings, by decoupling the optimization problem into optimizer state (w/ complex) updates and parameter state (w/ linear) updates.
-	Proven upper bound convergence guarantees of the MIME (MIMELite) framework for different optimizers and comparison against their centralized counterpart. The upper bound convergence rate of the Momentum-based variance federated adaptation is proven to beat the lower bound of the centralized version when clients' heterogeneity is small.
-	Experiments on real-world datasets and large-scale experiment setup evaluation for EMNIST62, Shakespeare, and StackOverflow datasets.

**Cons**
-	The proposed method introduces additional communication cost in federated cross-device settings.
-	Even though the empirical evaluation is sufficient, further clarification is needed.
-	Paper structure is not necessarily coherent; some methods are introduced differently in some parts of the paper and are hard to follow.


**Discussion**

- Communication. With your proposed framework, there seems to be a lot more extra communication cost from server to clients (global model, server state, and SVRG style correction lines 140, 141) and clients to the server (updated local model weights, plus full-batch gradients). Can you propose any approaches on how this extra cost (at least on the client-end) can be mitigated? You address some part of the latter case in line 274, and in Appendix section C.3, but I think this should be introduced earlier in the text to alleviate some concerns.

- From my understanding, your analysis focus on the perspective that local batch gradient and parameter update are performed at the same client. Does the creation of the two subgroups (local batch gradient and parameter update) affect your convergence? It is clear that out of S clients, S/2 send full-batch gradients and S/2 parameter updates. Instead of creating two subgroups would a single subgroup of size S/2 lead to the same performance? My concern here is that since clients have heterogeneous distributions, considering only local batch gradients from half of the clients and parameter updates from the remaining might introduce additional noise in the state updates. Is such perspective captured in your theoretical evaluation?

- Is there a case that some of the participating clients cannot compute the full local batch gradient because of resource constraints (Line 146, Algorithm 1)? Should the subsampling method take this constraint into account?

- Experiments. Does Figure 1 show test accuracy or validation accuracy? Why do you provide the validation accuracy in Table 2, the testing accuracy would have been more informative. If this is not possible then, how were the validation datasets constructed and how was the validation accuracy computed across all clients? Moreover, showing the learning curves of the training methods presented in Table 2, based on federation round, would greatly simplify the understanding of the communication cost for each method. Finally, it would be nice to provide/plot the performance of the centralized model (e.g., as horizontal line) in Figure 1. 

- Paper structure. In Table 1 you introduce the μ-PL inequality, but in the text there is no discussion on why this convergence analysis is important, what its intricacies are (except of course in Appendix E.1) and why its analysis is not provided for ADAM and MVR – it would be better to discuss this in the text. When presenting the empirical evaluation with Momentum, it is not very clear whether you are discussing server-side or client-side momentum (additional reading is needed). Moreover, the presented momentum results are without variance (not MVR), correct? If that’s the case then what is the convergence of MVR? In addition, in Table 1 you provide convergence guarantees for SGD, Adam, and MVR, however, from the Algorithm it is not clear how the MVR or the Adam is applied since the correction term (c) seems to be always present in the MIME, which is also why MIME is different from MIMELite. Can you please elaborate more in the text to address these discrepancies? 

**Additional Related Work**

- In [1], Momentum GD is used as part of the client local step (without server-side optimization) and it is shown to provide accelerated convergence compared to vanilla SGD (FedAvg). Their approach seems to be very similar to your FedAvgMomentum training method.
- In the related work section, "Comparison to FedAvg and variants", in [2], the authors also assign more local steps to computationally fast learners in cross-silo settings and (empirically) show faster convergence.

[1] https://arxiv.org/pdf/1910.03197.pdf, [2] https://arxiv.org/pdf/2102.02849.pdf 

**Text corrections / suggestions**

- Lines 100, 107: Notation D is a bit misleading when referring to clients (most of the time denotes dataset), would another notation (e.g., C) be more appropriate?
- Line 119: please add eq. or equation 1
- Line 130: change table 4 reference to table 5
- Line 133: while … while fragmentation
- Table 1: Why is MimeLiteSGD equivalent to FedSGD? Did you refer to FedAvg? FedSGD is different from FedAvg [3], similarly in Appendix section C.5 Line 759.
- Line 204: epsilon(ε) refers to accuracy or error? In your analysis, it refers to error
- Line 221: which increases to increase
- Line 259: Appendix D does not refer to proof sketch, change to B
- Line 285: Appendix B does not refer to the experimental setup, change to C
- Please be consistent with the Mime or MIME naming (see sections 4 and 5).
- Please align subfigures in Figure 1.
- Line 331: Statement slightly contradicts your empirical evaluation, which is also shown in Table 2 – MIME does not always outperform MIMELite.


[3] https://arxiv.org/pdf/1602.05629.pdf 



**POST AUTHORS RESPONSE COMMENT:**
I read carefully the response of the authors to my points and the points raised by the other reviewers. My primary concern is the additional communication cost introduced by the framework in cross-device federated settings. In their follow-up answer, the authors propose an approach to reduce this cost through sampling and indicated (in another response) that the lower bound analysis of the communication complexity remains an open question. I would like to see this question and others raised during the reviewing process as part of the paper's discussion/future work section since it can help readers to further investigate these open problems. My score remains unchanged.


limitations_and_societal_impact: The work does not seem to have any limitations or potentially negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies cross-device federated learning setting where the number of clients is very large and most of the clients participate in only one round of communication. Because of this low client participation per round, it is hard to have any client state/memory. State is usually helpful in traditional federated learning setting (eg: in SCAFFOLD) in estimating client heterogeneity, which can then be used to correct for the bias of the client. To mitigate this, the authors propose two meta-algorithms: MIME and MIMELITE, to adaptive a general class of centralized algorithms to this cross-device setting. MIME uses variance reduction at the client (like SCAFFOLD) and MIMELITE does not.

The paper analyzes the effect of these meta-algorithms for three standard centralized (server-only) deep learning optimization methods: SGD, Adam, MomentumVarianceReduction (MVR). However, reviewer could not find the pseduo-code for the MVR in the paper. For SGD, and Adam authors show that MIME modification performs at least as good as their centralized base algorithms for nonconvex problems. For MVR, authors prove that the server-level momentum of MIME helps beat the performance of centralized baselines under low-heterogeneity.
main_review: Contributions are original and their quality seems solid, but it is hard to verify it due to lack of clarity (see below). Improving clarity could better convince the readers of the claims. Although it is not clear if the contributions are consistently useful in practice (see below), these analysis and the experiments could be impact for future research and practice. Reviewer is willing to reconsider the score if the clarity and empirical quality can be improved.

-Strengths
1. If the base centralized algorithms use a momentum, MIME and MIMELITE uses an unbiased estimator of the server-level momentum. These algorithms communicate this momentum to the participating clients at the beginning of each round, and the clients use it to correct their bias when taking gradient descent steps. Note that clients do not update the momentum for their whole round to maintain the lack of bias of the momentum.

2. It it shown that for SGD and Adam, MIME matches the performance of the corresponding centralized (without local gradient steps) base algorithm. Whereas, MIMELITE is slightly worse and it could match centralized performance under certain conditions.

3. For MVR algorithm, MIME is shown to perform much better than centralized algorithm when the client Hessian heterogeneity is smaller than the smoothness of the global loss. This seems to be first such result for smooth non-quadratic setting proving the benefit of federated algorithm over centralized methods. However it was hard to verify this claim as MVR algorithm is not given.

4. Authors report (small scale single-run) ablation study on 2 layer MLP with base SGD+momentum algorithm, to show that MIME & MIMELITE perform better than FedAvg in cross-device setting. It is shown that momentum helps MIMEs however it doesn’t affect FedAvg.

5. Reviewer appreciates that authors also report both positive and negative results they get on large-scale datasets. However, from the given single runs it is is not clear if their meta-algorithms are consistently better than baselines. One way or the other, it would be useful to know.



-Comments
1. Although there are only some subtle differences between original FedAvg/SCAFFOLD and MIME-SGD/MIMELITE-SGD, latter gets a much better rate nonconvex in cross-device setting. Can the authors provide more discussion on this difference and intuition behind this improvement?

2. App A: Over-all App A is confusing. 
a. Fig 1: It is not clear which algorithm is FedAvg. I think authors use FedAvg both for some meta-algorithm (not given) and standard FedAvg.
b. What is “server-momentum” in App A and mentioned everywhere else? Can the authors please define it? Why is it called “momentum” and not some kind of pseudo “gradient” for FedAvg? 

3. App B is confusing. It could be written more clearly. For example,
line 649: where is the convex case in Theorem IV? It is hard to understand the section due to the sudden analogy with convex case.

4. Table 1 and Appendix: Can the authors please add the reference for optimal statistical rate?

5. Where are the full pseudo codes of MVR & MIME-MVR algorithm given? Cannot verify the result without the algorithm. It is not given in Table 5. There is not MVR algorithm in [14].

6. Why are there no simulations of MVR and its MIME variants?

7. Table1:
a. Why is FedAvg rate not given?
b. What is FedSGD? Same for FedSGD, FedSGDm, and FedAdam in the Appendix. 

8. What is the FedAvg meta algorithm used in the experiments? It is confusing to use FedAvg to refer to the original FedAvg and the some other meta algorithm from [45]. 

9. Table 2: It is not clear why authors are confident that numbers will hold the same over multiple runs. As this is an paper on optimization methods, it is appropriate give the numbers over multiple runs and give their standard errors. Most of the numbers are very close to each other, so it is not conclusive that Mime or Mimelite are useful for large datasets, except for Stackoverflow with Adam. 

10. Are authors using “SGDm” and “Momentum” interchangeably?

11. Why does the theory (SGD,MVR) and expts (Adagrad,SGD+momentum) use different base algorithms? I was expecting to the see the experiment with MVR for different levels of heterogeneity.

12. Ablation study: it is not clear why MIME{Adam,Adagrad} is not compared with Fed{Adam,Adagrad} which are much more practical base algorithm. [https://openreview.net/forum?id=LkFG3lB13U5]

13. Although MIME predominantly can only match the centralized rates, but authors claim they may outperform centralized methods in practice (mismatch of theory and practice). Why is this the case?

14. Why is there no discussion of MIME on convex problems?


-Other Comments
1. line 890: $\pm$ is not a standard notation for adding and subtracting. Missing brackets for argument inside $\mathcal{U}$
2. line 677: uses i both outside and inside sum
3. line. 323: “”App ??”
4. When saying that “MimeMVR is the first algorithm which beat centralized rates”, are the authors claiming this for general nonconvex setting or is this applicable to convex problems too? Authors may want to be explicit about this for non-expert readers.
5. Algo 1: From lines 140-141 and 146-147 it is not clear how c & s are calculated. Authors could mention the direction of communication when calculating and sending c.
6. line 325: Why is sparsity of gradients useful?

—After author response—
\
I keep my score the same as I am still confused about some parts of the paper. I highly encourage authors to improve the clarity in the next revision.

—__After after__ author response—
\
With their latest response, authors have clarified most of my initial concerns. Unfortunately, I am still keeping my scores the same because now I am not sure if empirical results are directly validating the theoretical results.
limitations_and_societal_impact: Authors could improve the discussion on limitations of their methods. Authors could mention some open questions arising from their study. For example, authors could discuss why MIME predominantly can only match the centralized rates, but they may outperform centralized methods in practice (mismatch of theory and practice). Authors could also mention why or why not MIME can help in convex setting.
review_title: null

Meta-review: Most of the concerns of the reviewers were addressed during the rebuttal period and the reviewers unanimously believe that the paper is above the acceptance threshold as the theoretical results are novel. Please revise the paper according to the reviewer's comments to clarify the confusions. In addition, please address the following concern which was raised by the reviewers in the discussion period:

-- All plots are for test accuracy/error. Please include the optimization error convergence rate plots to have a better connection with the rest of the paper. 
Decision: Accept (Poster)