On the Convergence of FedAvg on Non-IID Data
Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (	exttt{FedAvg}) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of 	exttt{FedAvg} on non-iid data and establish a convergence rate of for strongly convex and smooth problems, where is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for 	exttt{FedAvg} on non-iid data: the learning rate must decay, even if full-gradient is used; otherwise, the solution will be away from the optimal.
This paper presents convergence rates for straggler-aware averaged SGD for non-identically but independent distributed data. The paper is well-written and motivated with good discussions of the algorithm and the related works. The proof techniques involve bounding how much worse can the algorithm do because of non-identical distribution and introduction of stragglers into the standard analysis of SGD-like algorithms. The presented theory is useful, and also provides new insights such as a new sampling scheme and an inherent bias for the case of non-decaying step size. The empirical evaluation is adequate and well-presented. I think this paper is a strong contribution and should spark further discussions in the community.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
On the Convergence of FedAvg on Non-IID Data
Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (	exttt{FedAvg}) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of 	exttt{FedAvg} on non-iid data and establish a convergence rate of for strongly convex and smooth problems, where is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for 	exttt{FedAvg} on non-iid data: the learning rate must decay, even if full-gradient is used; otherwise, the solution will be away from the optimal.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



This paper presents convergence rates for straggler-aware averaged SGD for non-identically but independent distributed data. The paper is well-written and motivated with good discussions of the algorithm and the related works. The proof techniques involve bounding how much worse can the algorithm do because of non-identical distribution and introduction of stragglers into the standard analysis of SGD-like algorithms. The presented theory is useful, and also provides new insights such as a new sampling scheme and an inherent bias for the case of non-decaying step size. The empirical evaluation is adequate and well-presented. I think this paper is a strong contribution and should spark further discussions in the community.
assistant
This paper presents convergence rates for straggler-aware averaged SGD for non-identically but independent distributed data. The paper is well-written and motivated with good discussions of the algorithm and the related works. The proof techniques involve bounding how much worse can the algorithm do because of non-identical distribution and introduction of stragglers into the standard analysis of SGD-like algorithms. The presented theory is useful, and also provides new insights such as a new sampling scheme and an inherent bias for the case of non-decaying step size. The empirical evaluation is adequate and well-presented. I think this paper is a strong contribution and should spark further discussions in the community.