A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

By Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, Sebastian U. Stich. 2020

652 citations recorded by the source corpus.

Decentralized stochastic optimization methods have gained a lot of attention recently, mainly because of their cheap per iteration cost, data locality, and their communication-efficiency. In this paper we introduce a unified convergence analysis that covers a large variety of decentralized SGD methods which so far have required different intuitions, have different applications, and which have been developed separately in various communities. Our algorithmic framework covers local SGD updates and synchronous and pairwise gossip updates on adaptive network topology. We derive universal convergence rates for smooth (convex and non-convex) problems and the rates interpolate between the heterogeneous (non-identically distributed data) and iid-data settings, recovering linear convergence rates in many special cases, for instance for over-parametrized models. Our proofs rely on weak assumptions (typically improving over prior work in several aspects) and recover (and improve) the best known complexity results for a host of important scenarios, such as for instance coorperative SGD and federated averaging (local SGD).

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel and Zhang, 2021, Loizou et al., 2020, 2021].”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “We speculate that similar ideas to the ones presented in this work can be used for the development of efﬁcient decentralized methods (Assran et al., 2019; Koloskova et al., 2020) for solving problem (3).”
Privacy Amplification by Decentralization (2020, background): “cal analysis of (non-private) decentralized algorithms [37, 51, 35, 45, 40], owing to its simplicity and good empirical performance.”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “Their analysis was extended to heterogeneous clients in [36, 40, 15, 16, 18].”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “This analysis was further expanded to the non-IID data partition and client sampling cases by [11–18, 23, 24].”
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].”
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].”
Federated Learning With Quantized Global Model Updates (2020, background): “There have also been eﬀorts 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…”
Towards Understanding Biased Client Selection in Federated Learning (2022, neutral): “…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 al., 2020) and methods to…”
A Superquantile Approach to Federated Learning with Heterogeneous Devices (2021, methodology): “The proof uses a result on communication rounds of FedAvg from [15]. where ∆ 0 = ( F θ,ν ( w 0 ) − F ,ν ) /ε 0 + 1 , and big O ( · ) includes constants and polylog factors.”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, background): “[12] also prove a lower bound, but specifically for 1-strongly convex objectives, which obscures the important role of the strong convexity parameter.”
Towards Out-Of-Distribution Generalization: A Survey (2021, background): “Various assumptions [82, 118, 128, 148] are made in regard to data heterogeneity to guarantee the performance of FL models, which is assessed as the expected utility across all clients.”
Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies (2020, background): “[14] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich.”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “decentralized averaging is an effective way to reduce the number of communication rounds among devices [147], [148].”
Private Weighted Random Walk Stochastic Gradient Descent (2020, neutral): “For convex problems, the convergence rate is O(1/ √ k) [41], where k is the algorithm round in which |E | communication links are activated and O(N) computations are performed.”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “We note that Assumption 4 can be seen as a replacement for Assumption 5 which is commonly used in the literature [4, 13, 29].”
Federated Multi-Task Learning under a Mixture of Distributions (2021, background): “For these reasons, they have attracted significant interest recently in the machine learning community [41, 63, 42, 62, 3, 51, 46, 31].”