Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms

By Jianyu Wang, Gauri Joshi. 2018

362 citations recorded by the source corpus.

Communication-efficient SGD algorithms, which allow nodes to perform local updates and periodically synchronize local models, are highly effective in improving the speed and scalability of distributed SGD. However, a rigorous convergence analysis and comparative study of different communication-reduction strategies remains a largely open problem. This paper presents a unified framework called Cooperative SGD that subsumes existing communication-efficient SGD algorithms such as periodic-averaging, elastic-averaging and decentralized SGD. By analyzing Cooperative SGD, we provide novel convergence guarantees for existing algorithms. Moreover, this framework enables us to design new communication-efficient SGD algorithms that strike the best balance between reducing communication overhead and achieving fast error convergence with low error floor.

Subfields: Computer Vision and Pattern Recognition, Control and Systems Engineering, Optimization & Training, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “As first shown in Wang and Joshi [399], the convergence analysis of decentralized SGD can be applied to or combined with local SGD with a proper setting of the network topology matrix (mixing matrix).”
Federated Optimization in Heterogeneous Networks (2018, background): “For instance, parallel SGD and related variants (Zhang et al., 2015; Shamir et al., 2014; Reddi et al., 2016; Zhou & Cong, 2018; Stich, 2019; Wang & Joshi, 2018; Woodworth et al., 2018; Lin et al., 2020), which make local updates similar to FedAvg, have been studied in the IID setting.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, neutral): “Substituting these values back into Theorem 1, it recovers previous results of FedAvg [24, 8, 20].”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, neutral): “• 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): “Similar to existing works (Lian et al., 2017; Wang & Joshi, 2018; Li et al., 2019) our proposed method allows only decentralized communications.”
Adaptive Federated Optimization (2020, methodology): “When the client are homogeneous, FEDAVG reduces to local SGD (Zinkevich et al., 2010), which has been analyzed theoretically by many works (Stich, 2019; Yu et al., 2019; Wang and Joshi, 2018; Stich and Karimireddy, 2019).”
Personalized Federated Learning: A Meta-Learning Approach (2020, methodology): “This includes quantization and compression ideas (Reisizadeh et al., 2019; Dai et al., 2019) as well as performing multiple local updates before communicating with the master (Stich, 2018; Lin et al., 2018; Wang and Joshi, 2018).”
Is Local SGD Better than Minibatch SGD? (2020, background): “One possible formalization is the graph oracle model of Woodworth et al. (2018) which focuses on the dependence structure between different stochastic gradient computations resulting from the communication pattern.”
Distributed Fixed Point Methods with Compressed Iterates (2019, neutral): “In order to reduce it, many methods have been suggested including the use of intermittent communication and decentralization [31], as well as exchanging only compressed or quantized information between the computing units [29].”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, methodology): “, less frequent synchronization, and periodically averaging the models across the workers (Stich, 2018; Lin et al., 2018; Yu et al., 2018; Wang and Joshi, 2018; Yu et al., 2019).”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “With some ideal simplification (such as identical Dk’s or all activated nodes), the convergence of FedAvg has been analyzed by [52, 37, 41, 45].”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “[21] Jianyu Wang and Gauri Joshi.”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, methodology): “In this case, the inner optimizer is Local-SGD.”
FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, neutral): “We also recover the result in [Wang and Joshi, 2018] when there is no quatization q = 0 and we have a full device participation r = n .”
Gradient Descent with Compressed Iterates (2019, background): “Further, while there is ample work on non-local methods which communicate compressed gradients [1, 3, 11, 34, 35], including methods which perform variance-reduction to remove the variance introduced by compression [10, 23, 24], to the best of our knowledge there is little work on methods performing”
On the Convergence of FedAvg on Non-IID Data (2019, background): “The prior work [3, 41, 28, 34, 30, 31] requires the full device participation in the aggregation step of FedAvg.”