Summary
The paper delves into the challenge of minimizing the objective, which is defined as a finite sum of smooth, and potentially non-convex, functions within a Federated Learning setting. The primary focus is addressing the significant workers-to-server communication costs arising in a centralized distributed framework, which involves one main server and multiple nodes. The authors' contributions can be summarized as:
- They present a novel formulation of the foundational SCAFFOLD algorithm, which effectively cuts uplink communication expenses by half. This lays a more straightforward foundation for integrating communication compression.
- The SCALLION algorithm is introduced, leveraging the new SCAFFOLD formulation combined with unbiased compressors.
- The SCAFCOM algorithm is developed to facilitate biased compressors in Federated Learning via local momentum. Convergence analysis for standard contractive compressors is provided.
- It is demonstrated that both SCALLION and SCAFCOM either match or surpass the communication and computation complexities of current compressed FL baselines.
- Through experiments, it's evident that SCALLION and SCAFCOM deliver performance akin to full-precision techniques, boasting compression savings exceeding 100x.
Strengths
- The writing of the paper is clear, the main claims are outlined, and the text is easily read;
- Literature review is solid and contains relevant papers on the topic;
- Proposed novel FL algorithms, SCALLION and SCAFCOM, are provably shown to be robust to heterogeneous data and partial participation and require only standard assumptions to establish first-order stationary point guarantees;
- SCALLION attains superior convergence guarantees compared to prior compressed FL methods with unbiased compression under minimal assumptions;
- Local momentum in SCAFCOM overcomes the adverse effects of biased compression. SCAFCOM improves communication complexity by a factor of 1/(1-q) over the prior art;
- Both SCALLION and SCAFCOM exhibit robustness to heterogeneous data and partial participation, unlike existing approaches;
- The paper provides a principled way to integrate communication compression into federated learning through the new SCAFFOLD formulation;
- Algorithms are simple to implement and empirically achieve significant compression savings.
Weaknesses
1) Some potentially relevant papers are missing in the references. See "Suggestions" below.
## Typos:
1) In the RELATED WORK section, instead of "TurnGrad" it should be "TernGrad".
## Suggestions:
I would recommend authors to reconsider some of the phrases that they wrote, in particular
>>Can we design FL approaches that accommodate arbitrary data heterogeneity, local updates, and partial participation, as well as support communication compression?
>>
>>In the literature, none of the existing algorithms have successfully achieved this goal, to the best of our knowledge.
To the best of my knowledge, this is true, but for the general class of non-convex loss functions. However, this is not true for strongly convex functions. There are already some works [1, 2, 3, 4] on that topic, providing a provably beneficial combination of compression, partial participation, and local updates.
[1] Grudzień, M., Malinovsky, G., & Richtárik, P. (2023). Improving Accelerated Federated Learning with Compression and Importance Sampling. _arXiv preprint arXiv:2306.03240_.
[2] Youn, Y., Kumar, B., & Abernethy, J. (2022, October). Accelerated Federated Optimization with Quantization. In _Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022)_.
[3] Condat, L., Malinovsky, G., & Richtárik, P. (2023). TAMUNA: Accelerated federated learning with local training and partial participation. _arXiv preprint arXiv:2302.09832_.
[4] Sadiev, A., Malinovsky, G., Gorbunov, E.A., Sokolov, I., Khaled, A., Burlachenko, K., & Richt'arik, P. (2022). Federated Optimization Algorithms with Random Reshuffling and Gradient Compression. _ArXiv, abs/2206.07021_.
Questions
There are several questions related to the prof of the Theorem 3:
1) (Page 25) Could authors please clarify why this inequality holds?
$$9 e^2 K^2 \eta_l^2 L^2\left(24+\frac{4(1+\omega) \alpha^2}{S}+\frac{522(1+\omega) \alpha}{N}\right) \leq \frac{\alpha(1+\omega)}{N} \leq \frac{1}{4}$$
2) Why does this property hold?
$$\| {x^0 - x^1}\|=0$$
## Conclusion
I would happily give this paper a higher grade for its theoretical contributions and reliable experiments. However, at this moment, I can not do so since the paper still contains things that need to be clarified. I am ready to reconsider my current rate during rebuttals once you respond to me on Weaknesses and Questions.
## Update after the author's rebuttal
I increased the score.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.