Minibatch vs Local SGD for Heterogeneous Distributed Learning

By Blake E. Woodworth, Kumar Kshitij Patel, Nati Srebro. 2020

228 citations recorded by the source corpus.

We analyze Local SGD (aka parallel or federated SGD) and Minibatch SGD in the heterogeneous distributed setting, where each machine has access to stochastic gradient estimates for a different, machine-specific, convex objective; the goal is to optimize w.r.t. the average objective; and machines can only communicate intermittently. We argue that, (i) Minibatch SGD (even without acceleration) dominates all existing analysis of Local SGD in this setting, (ii) accelerated Minibatch SGD is optimal when the heterogeneity is high, and (iii) present the first upper bound for Local SGD that improves over Minibatch SGD in a non-homogeneous regime.

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

Citations in the corpus

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.,…”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “To this end, the fundamentals of FL have recently been studied through the lens of the convergence analysis on local SGD [160]–[163].”