First Analysis of Local GD on Heterogeneous Data

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

180 citations recorded by the source corpus.

We provide the first convergence analysis of local gradient descent for minimizing the average of smooth and convex but otherwise arbitrary functions. Problems of this form and local gradient descent as a solution method are of importance in federated learning, where each function is based on private data stored by a user on a mobile device, and the data of different users can be arbitrarily heterogeneous. We show that in a low accuracy regime, the method has the same communication complexity as gradient descent.

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

Advances and Open Problems in Federated Learning (2019, methodology): “While [370, 428, 399, 371] mainly focused on the IID case, the analysis technique can be extended to the non-IID case by adding an assumption on data dissimilarities, for example by constraining the difference between client gradients and the global gradient [266, 261, 265, 401] or the difference be”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “The local dataset sizes ni, i ∈ [1, 30] follows a power law.”
Personalized Federated Learning with Moreau Envelopes (2020, methodology): “According to Corollary 1, we are able to obtain the quadratic speedup, while most of existing FL convergence analysis of strongly convex loss functions can only achieve linear speedup [3, 6, 45].”
Adaptive Federated Optimization (2020, background): “In order to analyze FEDAVG in heterogeneous settings, many works derive convergence rates that depend on the amount of heterogeneity (Li et al., 2018; Wang et al., 2019; Khaled et al., 2019; Li et al., 2019b).”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “In a very similar vein, control variates were used to obtain linearly converging decentralized algorithms under the guise of ‘gradient-tracking’ in (Shi et al., 2015; Nedich et al., 2016) and for gradient compression as ‘compressed-diﬀerences’ in (Mishchenko et al., 2019).”
Gradient Descent with Compressed Iterates (2019, background): “For instance, until very recently [13], no convergence results were known for the simplest of all local methods—local gradient descent—in the case when the functions fi are allowed to be arbitrarily different, which is a requirement of any efficient federated learning method since data stored on dev”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, background): “Our earlier workshop paper (Khaled et al., 2019a) Assump-tion 2, however, typically does not hold for ﬁnite-sum problems where g p x, z q is a gradient of the one functions in the ﬁnite-sum.”
On the Convergence of Local Descent Methods in Federated Learning (2019, methodology): “Interestingly, our convergence analysis for both local GD and local SGD does not rely on any additional assumption which is consistent with more recent analysis in [16].”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “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”
Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning (2021, methodology): “2 RELATED WORK The federated averaging (FedAvg) algorithm was first proposed by McMahan et al. (2016) for FL as a heuristic to improve communication efficiency and data privacy.”
Decentralized Federated Averaging (2021, background): “In [14], [15], the authors prove that FedAvg needs e Oð1 Þ communication rounds to”
Client Selection and Bandwidth Allocation in Wireless Federated Learning Networks: A Long-Term Perspective (2020, background): “, [34], [35], as they do not explicitly differentiate the effects of different learning rounds.”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, background): “[10] analyzed Local Gradient Descent (σ = 0).”
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).”
A Survey on Federated Learning for Resource-Constrained IoT Devices (2021, unknown): “Each client device implements a ﬁxed number of GD steps (declares from the average model) using their local function independently in parallel [70].”
Federated Learning With Quantized Global Model Updates (2020, background): “…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 constraints [37–40].”
FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (2020, background): “Algorithm Convexity DN BG RC (T ) LC (QT ) AS FedAvg [4] μSC 0 No O ( 1/ 1/2 ) O(1/ ) O(1/ ) FedAvg [9] μSC - Yes O (1/ ) O(1/ ) O(1/ ) Coop-SGD [5] NC 0 No O(1/ ) O(1/ (2)) O(1/ (2)) MPR-SGD [3] NC - Yes O(1/ ) O(1/ (2)) O(1/ (2)) Local-GD [15] C - No O(1/ ) O(1/ (2)) O(M/ (2)) FedProx [12] NC -? N”
From Local SGD to Local Fixed Point Methods for Federated Learning (2020, methodology): “Then the assumptions in Theorem 2.6 are satisfied and our results recover known results about Local GD for heterogeneous data as particular cases (Khaled et al., 2019).”