Communication trade-offs for synchronized distributed SGD with large step size

By Kumar Kshitij Patel, Aymeric Dieuleveut. 2019

27 citations recorded by the source corpus.

Synchronous mini-batch SGD is state-of-the-art for large-scale distributed machine learning. However, in practice, its convergence is bottlenecked by slow communication rounds between worker nodes. A natural solution to reduce communication is to use the \emph{`local-SGD'} model in which the workers train their model independently and synchronize every once in a while. This algorithm improves the computation-communication trade-off but its convergence is not understood very well. We propose a non-asymptotic error analysis, which enables comparison to \emph{one-shot averaging} i.e., a single communication round among independent workers, and \emph{mini-batch averaging} i.e., communicating at every step. We also provide adaptive lower bounds on the communication frequency for large step-sizes ($ t^{-\alpha} $, $ \alpha\in (1/2 , 1 ) $) and show that \emph{Local-SGD} reduces communication by a factor of $O\Big(\frac{\sqrt{T}}{P^{3/2}}\Big)$, with $T$ the total number of gradients and $P$ machines.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Optimization & Training, ML Systems & Hardware

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 Electrical and Electronic Engineering

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “The convergence analysis of local-update SGD methods is an active current area of research [370, 271, 428, 399, 334, 318, 233].”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “[26] Kumar Kshitij Patel and Aymeric Dieuleveut.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “Re-markably, for instance for local SGD (Zinkevich et al., 2010; Stich, 2019b; Patel & Dieuleveut, 2019) we show improved rates for the convex and strongly-convex case and recover the best known rates for the non-convex case under weaker assumptions than assumed in prior work (highlighted in Table…”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “Stich (2018) and, more recently Stich and Karimireddy (2019) and Patel and Dieuleveut (2019), gave a sharper analysis of the same method, under the name of local SGD, also for identical functions.”
Don't Use Large Mini-Batches, Use Local SGD (2018, neutral): “[41] have also given similar results for quadratic functions and strongly convex functions, comparing local SGD with mini-batch SGD and one-shot averaging.”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “Analyses have been developed for strongly convex (Patel and Dieuleveut, 2019; Stich, 2019b) and non-convex (Yu et al.”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, methodology): “(cid:74) (cid:75) In machine learning framework, this is for example valid for both least squares regression and logistic regression [27].”
FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correction (2022, background): “The works in [10,13] show that FedAvg reaches asymptotic convergence for homogeneous clients.”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “Stich (2018) and, more recently Stich & Karimireddy (2019); Patel & Dieuleveut (2019); Khaled et al. (2020), gave a sharper analysis of the same method, under the name of local SGD, also for identical functions.”