Communication Efficient Decentralized Training with Multiple Local Updates

By Xiang Li, Wenhao Yang, Shusen Wang, Zhihua Zhang. 2019

56 citations recorded by the source corpus.

Decentralized optimization has been demonstrated to be very useful in machine learning. This work studies the communication-efficiency issue in decentralized optimization. We analyze the Periodic Decentralized Stochastic Gradient Descent (PD-SGD) algorithm, a straightforward combination of federated averaging and decentralized SGD. For the setting of for non-convex objective and non-identically distributed data, we prove that PD-SGD converges to a critical point. In particular, the number of local SGDs trades off communication and local computation. From an algorithmic perspective, we analyze a novel version of PD-SGD, which alternates between multiple local updates and multiple decentralized SGDs. We also show that when we periodically shrink the length of local updates, this generalized PD-SGD can better balance the communication-convergence trade-off both theoretically and empirically.

Subfields: Aerospace Engineering, Computational Mechanics, Electrical and Electronic Engineering, 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 Aerospace Engineering

In Computational Mechanics

In Electrical and Electronic Engineering

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”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “…SGD (Wang & Joshi, 2018) which considers only the IID data case ( f i = f j ) with local updates and a ﬁxed mixing matrix W , and the recently proposed • periodic decentralized SGD (Li et al., 2019) that allows for multiple local update and multiple mixing steps (for ﬁxed W ) in a periodic manner.”
On the Convergence of Local Descent Methods in Federated Learning (2019, background): “Comparison to past work In context of decentralized algorithms, the concurrent work [21] proposed a variant of local SGD that alternatives between multiple local updates and multiple communication steps and shows that under additional assumption of 1 p ∑p j=1 ‖∇fj(w)−∇f(w)‖ ≤ κf (i.”
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).”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “In Assumption 2, κ quantiﬁes the bounded deviation between the local loss functions F r , r ∈ [ R ] and the global loss function F ; see also [YJY19,LYWZ19], where this assumption has been used in heterogeneous data settings in decentralized SGD without Byzantine clients.”
Federated Learning Over Wireless Networks: Convergence Analysis and Resource Allocation (2019, methodology): “Using the data generation method similar to that in [39], in which users’ random samples and weights are drawn from N (0, 1) and 5% of the labels are flipped uniformly at random, we can control the value of ρ by changing λ.”
Federated Mutual Learning (2020, background): “Many theoretical works are also made for FederatedAveraging focusing on convergence analysis and relaxing the assumptions in the Non-IID setting[9, 10, 11].”