Tighter Theory for Local SGD on Identical and Heterogeneous Data

By Ahmed Khaled, Konstantin Mishchenko, Peter Richtárik. 2019

489 citations recorded by the source corpus.

We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug $H=1$, where $H$ is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training, Federated & Distributed Learning

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 Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “[16] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[16] A Khaled, K Mishchenko, and P Richtárik.”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, background): “• In the homogeneous setting, if Θ = Θ1:K , and γ = η, then LocalUpdate is equivalent to Local SGD with K local steps.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “, 2016; 2017) and has recently attracted the attention of the theoretical community in the seek of the best convergence rates (Stich, 2019b; Wang & Joshi, 2018; Yu et al., 2019; Basu et al., 2019; Patel & Dieuleveut, 2019; Stich & Karimireddy, 2019; Li et al., 2019; Khaled et al., 2020).”
Personalized Federated Learning: A Meta-Learning Approach (2020, background): “…paper, there are several works that study statistical heterogeneity of users’ data points in FL (Zhao et al., 2018; Sahu et al., 2018; Karimireddy et al., 2019; Haddadpour and Mahdavi, 2019; Khaled et al., 2019; Li et al., 2019), but they do not attempt to ﬁnd a personalized solution for each user.”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “In Lemma 5, we improve this bound toO(η2tKσ 2) which allows for our improved guarantee.3 Our approach resembles that of Khaled et al. (2019), which we became aware of in the process of preparing this manuscript, however our analysis is more refined.”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, background): “Several recent works show significant accuracy loss for FederatedAveraging over non-IID data, and some propose algorithms to improve FederatedAveraging over non-IID data (Zhao et al., 2018; Li et al., 2019; Shoham et al., 2019; Karimireddy et al., 2019; Liang et al., 2019; Li et al., 2020a; Wang et ”
Natural Compression for Distributed Deep Learning (2019, background): “, 2010) or once every few iterations (Stich, 2018; Khaled et al., 2020)).”
Federated Learning of a Mixture of Global and Local Models (2020, background): “In its most simple form, when one does not employ partial participation, model compression, or stochastic approximation, FedAvg reduces to Local Gradient Descent (LGD) (Khaled et al., 2019, 2020), which is an extension of GD performing more than a single gradient step on each device before aggregati”
Towards Understanding Biased Client Selection in Federated Learning (2022, methodology): “The eﬀect of data heterogeneity on the convergence 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…”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “cally evolving models [14,27], which are not improvable in general [70].”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “[161] that local SGD can achieve the convergence rate of O(1/√MT ) under both IID and nonIID data.”
Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach (2020, background): “More related to our paper, there are several works that study statistical heterogeneity of users’ data points in FL [18–23], but they do not attempt to ﬁnd a personalized solution for each user.”
Fine-tuning Global Model via Data-Free Knowledge Distillation for Non-IID Federated Learning (2022, background): “It has been verified that the vanilla FL algorithm, FedAvg [30], leads to drifted local models and forgets the global knowledge catastrophically in this scenario, which further induces degraded performance and slow convergence [14, 19, 21].”
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.”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “While it has shown success in certain applications, its performance on heterogeneous data is still an active area of research (Li et al., 2018; Yu et al., 2019; Li et al., 2019b; Haddadpour & Mahdavi, 2019; Khaled et al., 2020).”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “[11] A Khaled, K Mishchenko, and P Richtárik.”