Variance Reduced Local SGD with Lower Communication Complexity

By Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, Yifei Cheng. 2019

161 citations recorded by the source corpus.

To accelerate the training of machine learning models, distributed stochastic gradient descent (SGD) and its variants have been widely adopted, which apply multiple workers in parallel to speed up training. Among them, Local SGD has gained much attention due to its lower communication cost. Nevertheless, when the data distribution on workers is non-identical, Local SGD requires $O(T^{\frac{3}{4}} N^{\frac{3}{4}})$ communications to maintain its \emph{linear iteration speedup} property, where $T$ is the total number of iterations and $N$ is the number of workers. In this paper, we propose Variance Reduced Local SGD (VRL-SGD) to further reduce the communication complexity. Benefiting from eliminating the dependency on the gradient variance among workers, we theoretically prove that VRL-SGD achieves a \emph{linear iteration speedup} with a lower communication complexity $O(T^{\frac{1}{2}} N^{\frac{3}{2}})$ even if workers access non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impressively better than Local SGD when the data among workers are quite diverse.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “Besides, previous cross-client variance reduction methods such as variancereduced local SGD (VRLSGD) [21] and SCAFFOLD [20] are only designed for homogeneous local steps case.”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “…considered, for example with momentum (Yu et al., 2019a; Wang et al., 2019), with quantization (Reisizadeh et al., 2019; Basu et al., 2019), with adaptive stepsizes (Xie et al., 2019) and with various variance-reduction methods (Liang et al., 2019; Sharma et al., 2019; Karimireddy et al., 2019).”
On the Convergence of Local Descent Methods in Federated Learning (2019, methodology): “This bound, in case of full device participation ( K = p ), matches the convergence rate of [1], which employs an explicit variance reduction in local SGD.”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “Other variance reduced local SGD algorithms (Liang et al., 2019; Karimireddy et al., 2019; Wu et al., 2019) are not capable of achieving linear convergence.”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, methodology): “In comparison to [36] which employs an explicit variance reduction component, if we let Q(x) = x (case of no quantization), our algorithm reduces to a generalization of algorithm in [36] with distinct local and global”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, background): “In a concurrent work, (Liang et al., 2019) propose to use variance reduction to deal with client heterogeneity but still show rates slower than SGD.”
FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (2020, methodology): “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”
Stochastic Controlled Averaging for Federated Learning with Communication Compression (2023, methodology): “Substantial efforts have been made to address client heterogeneity in FL (Liang et al., 2019; Li et al., 2020b,a; Wang et al., 2020a; Zhang et al., 2021; Haddadpour et al., 2021; Yuan and Li, 2022; Alghunaim, 2023; Cheng et al., 2024), and develop other FL protocols involving variance reduction…”
Federated Learning under Arbitrary Communication Patterns (2021, background): “…also been considered, for example with momentum (Yu et al., 2019a; Wang et al., 2019b) with gradient compression (Jiang & Agrawal, 2018; Basu et al., 2019; Reisizadeh et al., 2020), with other various variance-reduction methods (Liang et al., 2019; Sharma et al., 2019; Karimireddy et al., 2019).”