Is Local SGD Better than Minibatch SGD?

By Blake E. Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, Nati Srebro. 2020

290 citations recorded by the source corpus.

We study local SGD (also known as parallel SGD and federated averaging), a natural and frequently used stochastic distributed optimization method. Its theoretical foundations are currently lacking and we highlight how all existing error guarantees in the convex setting are dominated by a simple baseline, minibatch SGD. (1) For quadratic objectives we prove that local SGD strictly dominates minibatch SGD and that accelerated local SGD is minimax optimal for quadratics; (2) For general convex objectives we provide the first guarantee that at least sometimes improves over minibatch SGD; (3) We show that indeed local SGD does not dominate minibatch SGD by presenting a lower bound on the performance of local SGD that is worse than the minibatch SGD guarantee.

Subfields: Artificial Intelligence, Management Science and Operations Research, Radiology, Nuclear Medicine and Imaging, 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 Management Science and Operations Research

In Radiology, Nuclear Medicine and Imaging

In Optimization & Training

Citations in the corpus

Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “In [28], and more recently in [29, 26, 16, 37], sharper and refined analyses of the same method (sometimes called local SGD) for identical functions.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[22] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro.”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, neutral): “This variance reduction is similar in nature to work by Woodworth et al. (2020) in the homogeneous setting (σA = σc = 0), which shows an analogous improvement in convergence rates.”
Towards Understanding Biased Client Selection in Federated Learning (2022, methodology): “…of local-update SGD is analyzed in recent works (Reddi et al., 2021; Haddadpour and Mahdavi, 2019; Khaled et al., 2020; Stich and Karimireddy, 2020; Woodworth et al., 2020; Koloskova et al., 2020; Huo et al., 2020; Zhang et al., 2020; Pathak and Wainwright, 2020; Malinovsky et al., 2020; Sahu et…”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “While it is still an active research area [53], a few number of recent studies made efforts to understand the convergence of local SGD in a heterogeneous setting [12,19,20,22,24,59].”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “[13] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro.”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, background): “8 Too many local steps may degrade the quality of the final model, and how to tune s is still an open research area [106, 105, 102, 64, 108, 50].”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, background): “[23] settled the issue for the homogeneous case, showing that on the one hand, when communication is rare, Local SGD provably outperforms even accelerated Minibatch SGD, but on the other, Local SGD does not always match Minibatch SGD’s performance guarantees and in some situations is provably worse ”
Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms (2020, methodology): “…works have provided upper bounds on the convergence rate of FedAvg in the homogeneous i.i.d. setting [Yu et al., 2019, Karimireddy et al., 2019, Woodworth et al., 2020b] as well as explored various non-i.i.d. settings with diﬀerent notions of heterogeneity [Zhao et al., 2018, Sahu et al.,…”
FedSplit: An algorithmic framework for fast federated optimization (2020, methodology): “Given our results on the incorrectness of previously proposed methods and the work of Woodworth and colleagues [30] on the suboptimality on multi-step stochastic gradient methods, it is interesting to develop a precise characterization of the tradeoﬀ between the accuracy of stochastic and…”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “Many proposals aim understand and characterize conditions under which linear speed-up for distributed SGD and local SGD is achievable (Lin et al., 2018; Yu et al., 2019a; Woodworth et al., 2020; Haddadpour et al., 2019).”