On the Convergence of Local Descent Methods in Federated Learning

By Farzin Haddadpour, Mehrdad Mahdavi. 2019

316 citations recorded by the source corpus.

In federated distributed learning, the goal is to optimize a global training objective defined over distributed devices, where the data shard at each device is sampled from a possibly different distribution (a.k.a., heterogeneous or non i.i.d. data samples). In this paper, we generalize the local stochastic and full gradient descent with periodic averaging-- originally designed for homogeneous distributed optimization, to solve nonconvex optimization problems in federated learning. Although scant research is available on the effectiveness of local SGD in reducing the number of communication rounds in homogeneous setting, its convergence and communication complexity in heterogeneous setting is mostly demonstrated empirically and lacks through theoretical understating. To bridge this gap, we demonstrate that by properly analyzing the effect of unbiased gradients and sampling schema in federated setting, under mild assumptions, the implicit variance reduction feature of local distributed methods generalize to heterogeneous data shards and exhibits the best known convergence rates of homogeneous setting both in general nonconvex and under {\pl}~ condition (generalization of strong-convexity). Our theoretical results complement the recent empirical studies that demonstrate the applicability of local GD/SGD to federated learning. We also specialize the proposed local method for networked distributed optimization. To the best of our knowledge, the obtained convergence rates are the sharpest known to date on the convergence of local decant methods with periodic averaging for solving nonconvex federated optimization in both centralized and networked distributed optimization.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “The following three key elements of this update rule take different forms for different algorithms: (1)In the case of client sampling, the update rule of FedAvg (2) should hold in expectation in order to guarantee convergence [12, 13, 38, 40].”
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.”
Adaptive Personalized Federated Learning (2020, background): “Due to inherent diversity among local data shards and highly non-IID distribution of the data across clients, FedAvg is hugely sensitive to its hyperparameters, and as a result, does not beneﬁt from a favorable convergence guarantee (Haddadpour and Mahdavi, 2019; Li et al., 2020).”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, background): “, 2018) or bounded gradient diversity (Haddadpour and Mahdavi, 2019) and addressed other less challenging aspects of federated learning such as decentralized communication, nonconvexity of the objective or unbalanced data partitioning.”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “The algorithms in [HKMC19,HM19,KKM + 19,KMR19,LHY + 20,SLS + 20,YYZ19,BDKD19] work under diﬀerent heterogeneity assumptions but do not provide any robustness to malicious clients.”
Federated Learning with Buffered Asynchronous Aggregation (2021, methodology): “Most previous works analyze synchronous federated learning methods, such as the works in (Lin et al., 2018; Li et al., 2018; Reddi et al., 2020; Li et al., 2020; Stich, 2019; Yu et al., 2019b; Li et al., 2019; Haddadpour and Mahdavi, 2019; Karimireddy et al., 2020).”
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].”
FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning (2020, background): “…et al., 2020; Li et al., 2020b; Karimireddy et al., 2020; Li et al., 2020b; Liang et al., 2019; Stich, 2019; Zhao et al., 2018; Zhou & Cong, 2017; Haddadpour & Mahdavi, 2019), system robustness (Li et al., 2020a; Smith et al., 2017; Bonawitz et al., 2019), and communication cost (Koneˇcn`y et…”
Federated Learning With Quantized Global Model Updates (2020, background): “…in developing convergence guarantees for FL under various scenarios, considering iid data across the devices [11, 24–27], non-iid data [27, 14, 28, 29], participation of all the devices [30–33], or only a subset of devices at each iteration [34–36, 29, 37], and FL under limited communication…”
Personalized Federated Learning using Hypernetworks (2021, background): “…Lin et al., 2018), others tackle the more challenging heterogeneous setup in which each client is equipped with its own data distribution (Zhou & Cong, 2017; Hanzely & Richt´arik, 2020; Zhao et al., 2018; Sahu et al., 2018; Karim-ireddy et al., 2019; Haddadpour & Mahdavi, 2019; Hsu et al., 2019).”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, background): “Several analyses bound this drift by assuming bounded gradients (Wang et al., 2019; Yu et al., 2019), or view it as additional noise (Khaled et al., 2020), or assume that the client optima are (cid:15) -close (Li et al., 2018; Haddadpour & Mahdavi, 2019).”
From Local SGD to Local Fixed Point Methods for Federated Learning (2020, methodology): “Thus, local gradient descent methods have been investigated (Stich, 2019; Khaled et al., 2019; 2020; Ma et al., 2017; Haddadpour & Mahdavi, 2019).”
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 under Arbitrary Communication Patterns (2021, background): “…on synchronous local SGD with non-identical data distribution across clients wherein all clients communicate their local parameter to the server every ﬁxed ∆ rounds (Yu et al., 2019b; Haddadpour & Mahdavi, 2019; Khaled et al., 2019b;a; Wang et al., 2019c; Basu et al., 2019; Li et al., 2019b).”