Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new algorithm called *FedLin* which, 

T.1) queries a full gradient oracle, 

T.2) de-biases the local gradients using a correction term (with the last synchronized iterate in memory) to deal with objective heterogeneity,

T.3) error corrects to deal with compression at the client and the server, and

T.4) uses a client-specific learning rate to deal with the different number of local steps on each client. 

Thus, FedLin is able to accommodate both objective and system heterogeneity along with sparse gradients and local steps. In doing so it is an early work that can deal with these multiple aspects of federated learning at once, albeit at the cost of an expensive gradient oracle. 

The paper provides the following theoretical guarantees for FedLin,

R.1) matching upper and lower bounds in the strongly convex-smooth setting without compression,

R.2) upper bounds without compression in the convex-smooth setting and the non-convex setting,

R.3) an iterate sub-optimality recursion for the strongly convex-smooth setting while using a stochastic gradient oracle,

R.4) upper bounds for client and server compression in the strongly convex-smooth setting.

See the main review for comments on these results.

main_review: I think overall the paper is clear and well-written. I have still only given it a score of 6, because there are aspects which can be improved, some of which are just presentation issues. If the following concerns can be handled, I am willing to improve my score. 

**v/s Scaffold**

The upper bounds in R.1, R.2, and R.3 are not better than Scaffold [1] but they can additionally accommodate a different number of local steps. On the other hand, Scaffold uses a stochastic oracle and accommodates partial client sampling. Both these differences are not really big though. With a step size of $1/\tau_i$, it is not surprising that FedLin can control the client drift, and it is not difficult to introduce uniform partial client sampling either. Thus if it were only for the upper bounds in R.1-R.3 (which are compression-free), the results would have been incremental to Scaffold. 

What is perhaps more interesting is the lower bound in R.1. After the Scaffold paper [1], one open question was if such a conservative client learning rate was actually necessary to compete with large mini-batch SGD (T rounds of batch size HM)? One could conjecture that it was a necessary evil to control the client drift, essentially giving us large mini-batch SGD like updates despite local steps! I.e., the obtained convergence rate can't depend on $TH$ but only $T$. This paper proves this conjecture for FedLin, giving lower bounds that depend only on $T$. This was a major limitation of Scaffold's results and analysis, and it is satisfying to see this lower bound. 

For the sake of completeness and for comparison, I would encourage the authors to also provide a similar lower bound for Scaffold, perhaps in the appendix. I expect that Scaffold's lower bound might also match its upper bound. In that case, I am not sure if the results are very exciting in the uncompressed case. Do the authors believe that proving Thm. 1-4 is technically very different from Scaffold ([1] does a good exposition of its proof technique in its appendix)? Is it fundamentally different from choosing a small enough step-size to control the client drift? If there are additional technical challenges besides this, they should be highlighted, otherwise I maintain that the techniques are incrementally different.    

**Sparsification results**

I believe these results are indeed novel. It would have been nice to have a theorem statement with both server and client level sparsification. Did the authors try this? What were the challenges in doing so? 

**Presentation** 

Based on my comments above, I think the authors should spend less space presenting and discussing Thm 1.-4 given how they are incremental over Scaffold. The paper should actually develope the lower bound in R.1 better, talk about its construction, and what it implies about other distributed algorithms like Scaffold. Perhaps Theorem 1 doesn't even need to be in the main paper, as Theorem 6. already generalizes it. It would be good to point out how the proof techniques in section 5. are different/similar to the ones in section 4, i.e., controlling the client drift? Finally, I would encourage the authors to talk a bit more about the novel proof technique developed in section 6. 

It feels a bit weird that the authors claim that all of the results can be obtained for the stochastic setting, but still don't chose to present them (even in the appendix). Why was Theorem 4. not completely worked out, along side other theorems? Having a noise term in the guarantee doesn't obfuscate the analysis or the takeaways. For instance I could go back to the Scaffold paper, and send the noise term to zero to compare the results with this paper very easily. Infact, it is important to understand if stochasticity behaves differently in presence of heterogeneity/local steps. Won't the authors be required to make more assumptions (perhaps on the stochastic gradients) to even carry out the analysis (like [2], which is a related reference that should probably be compared to as well)? It is not clear to me. Either present the stochastic results, or be upfront about the issues in doing so. In practice, it is going to be prohibitive to use a full gradient oracle, and some mini-batch version of FedLin would be used. If so how would that compare to accelerated minibatch SGD [2] ? 

**Experiments**

Continuing on the last issue, brings me to the (lack of) baselines in experiments. The algorithm essentially compares only to itself!

1) Why is Scaffold not present in any of the experiments and specially in the motivating figure 1? 

2) In practice people will use a stochastic oracle. Atleast some (if not all) experiments should also show a stochastic version of FedLin, along with important baselines such as accelerated minibatch SGD, Scaffold, etc. I would expect that when the local steps are the same and the heterogeneity level is low, different trade-offs will start emerging, and algorithms like  large mini-batch SGD or FedAC [3] might dominate FedLin.

**Minor Comments**

1) It would be better to present Theorem 4 for function sub-optimality, instead of recursion on iterate sub-optimality. This is good for uniformity w.r.t. the other results as well as to make the comparison with earlier work more transparent. 

# Updated Review

The authors have honestly addressed some of the limitations of their work. They have also promised to make important additions to the revised paper including experiments with other baselines and with a stochastic oracle, as well as a more detailed discussion of the baselines. I hope the authors will sincerely make these additions and will also improve upon their presentation as discussed. In light of this I am improving my score to a 7.  

**References**

[1] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International Conference on Machine Learning. PMLR, 2020.

[2] Woodworth, Blake, Kumar Kshitij Patel, and Nathan Srebro. "Minibatch vs Local SGD for Heterogeneous Distributed Learning." Advances in Neural Information Processing Systems 33 (NeurIPS 2020) (2020).

[3] Yuan, Honglin, and Tengyu Ma. "Federated Accelerated Stochastic Gradient Descent." Advances in Neural Information Processing Systems 33 (2020).
limitations_and_societal_impact: See the main review.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes an optimization method for federated learning, FedLin, that is specifically designed to ensure fast convergence even in the presence of heterogeneous data. Notably, the authors show that FedLin converges to the global optimum (or just a critical point, in the case of non-convex functions) without decaying the client learning rate. This is in contrast to methods such as FedAvg, FedProx, and FedNova, which require decaying the client loss in order to circumvent "objective mismatch", where the methods are actually optimizing an altered surrogate loss.

This work also derives lower bounds matching the convergence of FedLin on quadratics, that explain the price and cost of performing multiple local update steps. They also analyze convergence using gradient sparsification at both the client and server. Finally, the paper shows the empirical benefits of FedLin over other methods on synthetic least squares and logistic regression problems.
main_review: I think this paper is a well-written paper with a clear focal idea, and a suite of great results to back up this idea. More specifically, I really enjoy that this paper essentially shows that certain convergence-accuracy trade-offs in federated learning (that exist for methods such as FedAvg, FedProx) can actually be circumvented in certain settings. The convergence results for FedLin are impressive, and **simple**. This is actually something wish to highlight. Client heterogeneity has caused a preponderance of assumptions needed to analyze the convergence of FL methods (eg. bounded gradient dissimilarity, specific learning rate schedules, etc.). This paper does away with all of this, and simply assumes smoothness. The results have no extra "problem-dependent" terms that are shrouded in asymptotics. The fact that the authors can also incorporate sparsification relatively easily into the framework is only an additional benefit.

I also want to highlight the fact that the authors attempted to ensure that their results were as tight as possible via Section 4, something that can be challenging in federated learning. The takeaways from Theorem 5 are extremely informative, and give a succinct summary of the cost and gain of "local training steps" in federated learning. My only comment here is a question for future work: Can a similar lower bound be derived for a class of federated optimization algorithms that generalizes FedLin and other related methods (eg. SCAFFOLD, FedAvg)?

The experimental results are somewhat brief, and focus on synthetic data. I do not think this is a downside of the paper. Many works have noted that convergence failures of FedAvg can be shown in synthetic quadratic settings with just 2 clients. Moreover, this work is fundamentally a theoretical one (and a strong one at that), and I do not subscribe to the notion that all papers must offer all possible theoretical results and experimental results. I will note that even from an empirical side, the experiments that the authors do in Appendix J evincing the non-convergence of FedSplit in certain settings are also extremely valuable. One suggestion for improving these results would be to have a version of Figure 2 that compares FedLin to FedAvg, FedProx, SCAFFOLD, FedSplit, etc.

One contention I have with the work is that it ignores a number of works that first proposed and analyzed the speed-accuracy trade-off discussed in the abstract and in Section 2. In particular, it is worth noting that works such as (Malinovsky et al., 2020; Charles and Konecny, 2020; Fallah et al, 2020, and Pathak and Wainwright, 2020) showed that various federated learning and meta-learning methods (including FedAvg, FedProx, and FOMAML) are actually optimizing surrogate objectives. (Charles and Konecny, 2021) also formalized the actual underlying trade-off (as Propositions 1 & 2 don't actually show a trade-off they simply show non-optimality of the methods). Moreover, Propositions 1 and 2 are special cases of Theorem 1 of (Charles and Konecny, 2021).

This is all to say that I think that the paper would be improved by 1) giving proper credit to the works that developed the idea of speed-accuracy trade-offs and 2) focusing on what common facets of methods such as FedProx and FedNova you are going to change in order to break that trade-off. More succinctly, breaking these trade-offs is the novel, exciting contribution of this work, not showing that the trade-offs exists.

$\\\\$

# Review Update

After reading the other reviews and the author feedback, I have kept my score as is. In particular, I think the convergence rates are still useful, if only as a benchmark against other methods (such as FedAvg) which do not converge globally, even in deterministic settings, unless parameters such as learning rate or number of steps is decayed so as to essentially degenerate to FedSGD.
limitations_and_societal_impact: The authors have some discussion of limitations of the work in Section 4. However, I would argue that the primary limitation is not addressed, and should at least be discussed. Currently, FedLin effectively requires a full participation among clients. It also requires a kind of two-stage communication process in each round, where clients train, communicate with the server, and then compute a full gradient over their data. It is worth noting that this does increase the system-level complexity of FedLin as compared to methods such as FedAvg. I do not think that contending with partial participation need be in the scope of this work (as the full participation case aligns well with cross-silo federated learning), but I do believe this limitation should be mentioned.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes and analyzes a framework for Federated optimization called FedLin. It combines client-specific local steps with (possibly) biased compression at the server and/or clients and guarantees linear convergence to the exact minimum. Algorithmic contributions are supported with lower bounds for the case of infrequent communication and carefully designed synthetic experiments on least squares and logistic regression problems, which highlight theoretical claims.
main_review: This paper is a solid piece of mainly theoretical work on the problem of linear convergence in the Federated optimization setting, and I recommend acceptance.

The paper is clearly written and well-structured. Related work is mostly adequately cited but can be complemented with the latest works on local methods with compression. I think that a much more detailed discussion is needed to compare with the briefly mentioned work [1]. I understand that it appeared quite recently, but it is essential for publication as it also suggested methods linearly converging to the exact optimum and combined with variance-reduction. It would also be helpful to include a comparison table with differences to the previous methods (e.g., with uncompressed methods like FedSplit, FedNova, SCAFFOLD, S-Local-(S)GD/SVRG from [1]) to make it easier for readers to understand the contributions.

The authors present only synthetic experiments, but they are appropriate in this case as they were carefully designed and decently support the theoretical claims. However, I recommend including real-data experiments (e.g., with LibSVM datasets) in the final version as it will help to understand the actual practical performance and limitations of the presented approach.

The main drawback of the proposed algorithm FedLin is that it requires sending uncompressed model vectors $x_{i, \tau_{i}}^{(t)}$ from workers to the server and $\overline{x}_{t+1}$ back at every communication round, which may not be efficient/possible in the federated learning setting. That is why the part on the compression seems is not very valuable from the practical side.

## Post-rebuttal
I have read other reviews and authors' answers. I found both of them very insightful and believe that the published paper will be significantly improved with the proposed suggestions in mind. To conclude, I keep my score as it is.

***

[1] E. Gorbunov, et al. “Local sgd: Unified theory and new efficient methods”. In International Conference on Artificial Intelligence and Statistics, pages 486 3556–3564. PMLR, 2021.
limitations_and_societal_impact: Limitations of the work were mostly addressed. Negative societal impact concerns are not applicable due to the theoretical nature of the paper.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers a standard distributed optimization setup in which clients periodically coordinate with a server to train a global model. The focus is on the deterministic setting, in which each worker computes full local gradients. It is first highlighted that standard algorithms for this problem do not converge to the true global minimizer without trading off speed (for example through diminishing step-sizes).

Thus, the FedLin algorithm, which converges linearly to the true minimizer, is introduced to get the best of both worlds. Several theorems covering various settings (strongly convex, convex, non-convex, stochastic) are given, and show that FedLin matches the communication complexity of parallel GD, regardless of the number of local steps used. Then, a matching lower bound is given for FedLin to show that the strongly convex convergence result is tight.  

Then, several gradient sparsification schemes are investigated (at the server and at the workers), which show that server-side sparsification is far less impactful than client-side sparsification. The impact of gradient sparsification is evaluated experimentally in Section 7. 
main_review: The fact that standard FL algorithms do not converge to the true minimizer is good to recall, but it's quite well-known so maybe too much space is spent on this. Otherwise, the algorithm is quite natural, and achieves its objective of providing linear convergence to the true minimizer in the deterministic setting. This being said, I have two major concerns, that I develop below. 

1) Convergence rates: 
I have very mixed feelings about Theorems 1-4 and the beginning of Section 4.1. It is nice to know that we can do local steps, but they do not seem to improve anything in this deterministic setting. Indeed, taking only one local step each time is enough. The step-size is divided by the number of local steps, and so workers end up doing a step of the same size as if they were only doing one step, with a similar result apparently. This only increases the computational cost, with no benefits.

I believe that it would be great to highlight at least one setting in which this is not the case. Something like "it cannot be better in the general setting but in some cases you really gain things", because after reading Section 4 I don't see why I would use FedLin over parallel GD. It seems like FedLin was proposed and analyzed for the sake of performing local steps, instead of actually bringing something to the table. 

Besides, there is a matching lower bound, but it is only matching for the FedLin algorithm so it does not imply that other algorithms of this kind cannot do better. I know it is hard to use a general lower bound because it would require acceleration to match it, but if you consider the lower bound from [A], you obtain that you need at least $O(\sqrt{\kappa})$ communications to solve the problem (adapt the proof, or argue that you consider a graph of diameter 1 so time $\tau \sqrt{\kappa}$, which means $\sqrt{\kappa}$ communications). "Translated" into a non-accelerated algorithm, this means that any algorithms requires time at least $\kappa$ communications, and so clearly there is no hope to beat parallel-GD in this setting without further assumptions (e.g., on the local functions to allow for more parallelism). This kind of reasoning seems more convincing to me than Theorem 5 since it is not restricted to FedLin. 


2) Compression: 
Why compress the gradients but not the parameters? They are the same dimension, and so it seems that the complicated compression scheme can only gain a factor 2 in general since full dimensional parameters will need to be sent anyway. Besides, both the server and the workers need to send full parameters so there is no upstream/downstream argument to be made on this part either. I have a hard time convincing myself of the interest of the compression scheme since it seems to affect only half of the actual communications. 

[A] Scaman, Kevin, et al. "Optimal algorithms for smooth and strongly convex distributed optimization in networks." international conference on machine learning. PMLR, 2017.


=====================================

After the response and discussing with the other reviewers, I recognize that this paper advances the understanding of FL algorithms and thus raised my score accordingly. 
limitations_and_societal_impact: No foreseeable societal impact.
review_title: null

Meta-review: This paper introduces the FedLin algorithm (which could be seen as an adaptation of FedSVRG) for cross-silo federated learning (without client sampling) and derives rigorous complexity guarantees. 

The reviewers commended the theoretical results, in particular the simple convergence proof of FedLin, and corresponding (algorithm specific) lower bound. 
Partial communication compression was studied as additional contribution. Yet, this aspect was assessed more critically by the reviewers, as  compression of the parameters is not supported.

The reviewers are of the opinion that their concerns were adequately addressed by the author's response (and that the promised changes by the authors will be implemented in the final version).

Additionally, I strongly encourage the authors to also include:
- a discussion of the relation to 'FedSVRG' [[Konecny et al, Federated Optimization: Distributed Machine Learning for On-Device Intelligence, 2016]](https://arxiv.org/pdf/1610.02527.pdf) and possibly additional literature related to 'federated SVRG' variants. In this regard, the claims on novelty should be phrased more carefully. (In particular also more carefully than in the author's response, as e.g. the mentioned algorithmic differences seem quite small and partially irrelevant (i.e. omitting a discussion of heterogenity for an algorithm that does not depend on heterogenity does not seem to be a limitation, etc.).
- a discussion of the 'client sampling' aspect would be appreciated. The limitation of FedLin to do a pass over all clients (and requiring twice as much communication as FedAvg) seems quite limiting in practice.
Decision: Accept (Poster)