Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

By Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, Viveck R. Cadambe. 2019

228 citations recorded by the source corpus.

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms. In this paper, we study local distributed SGD, where data is partitioned among computation nodes, and the computation nodes perform local updates with periodically exchanging the model among the workers to perform averaging. While local SGD is empirically shown to provide promising results, a theoretical understanding of its performance remains open. In this paper, we strengthen convergence analysis for local SGD, and show that local SGD can be far less expensive and applied far more generally than current theory suggests. Specifically, we show that for loss functions that satisfy the Polyak-Kojasiewicz condition, $O((pT)^{1/3})$ rounds of communication suffice to achieve a linear speed up, that is, an error of $O(1/pT)$, where $T$ is the total number of model updates at each worker. This is in contrast with previous work which required higher number of communication rounds, as well as was limited to strongly convex loss functions, for a similar asymptotic performance. We also develop an adaptive synchronization scheme that provides a general condition for linear speed up. Finally, we validate the theory with experimental results, running over AWS EC2 clouds and an internal GPUs cluster.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “[191] show that for PL functions, T 2/M local updates per round leads to a O(1/TKM) convergence.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “Following previous works [38, 12, 20, 15], we assume the sampling scheme guarantees that the update rule (12) hold in expectation.”
Is Local SGD Better than Minibatch SGD? (2020, background): “Haddadpour et al. (2019a) also analyze local SGD in a related setting (they assume the Polyak-ojasiewicz condition, which is implied by strong convexity).”
Adaptive Personalized Federated Learning (2020, neutral): “As we theoretically prove and empirically verify in this paper, when the data is distributed IID, we cannot beneﬁt from personalization, and it is similar to the local SGD scenario (Stich, 2018; Haddadpour et al., 2019a,b).”
On the Convergence of Local Descent Methods in Federated Learning (2019, background): “…for simplicity: , we conclude that for time period [ t c , t ] the bound in (55) reduces to In the following lemma– which is essentially proven in [8] and adopted here to support random sampling of a subset of devices in communication rounds, we show that with proper choice of learning rate this…”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “cally evolving models [14,27], which are not improvable in general [70].”
Federated Learning under Arbitrary Communication Patterns (2021, background): “…bounded gradient assumption, as achieved through different parameters in recent distributed SGD/GD literature (see, e.g., (Wang & Joshi, 2018; Khaled et al., 2019b; Haddadpour et al., 2019; Yu et al., 2019a; Li et al., 2020b; Wang et al., 2019a; Li et al., 2018)) is an interesting open problem.”
BatchCrypt: Efficient Homomorphic Encryption for Cross-Silo Federated Learning (2020, background): “Local-update SGD & Model Averaging Local-update SGD & model averaging is another common approach to reducing the communication overhead for FL [22,40], where the aggregator collects and averages model weights before propagating them back to clients.”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “The algorithms in (Basu et al., 2019; Haddadpour & Mahdavi, 2019; Haddadpour et al., 2019; Karimireddy et al., 2020; Khaled et al., 2020; Li et al., 2020; Sahu et al., 2020; Yu et al., 2019b) work under different heterogeneity assumptions but do not provide any robustness to malicious clients.”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “In this work, we focus on cross-device FL where participants are edge devices (Kairouz et al. (2019)), and in particular, aim to address the following two challenges: Challenge 1: Scalability. In large-scale cross-device FL settings, the number of clients can be in the millions, and only a small fra”