LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning

By Tianyi Chen, Georgios B. Giannakis, Tao Sun, Wotao Yin. 2018

329 citations recorded by the source corpus.

This paper presents a new class of gradient methods for distributed machine learning that adaptively skip the gradient calculations to learn with reduced communication and computation. Simple rules are designed to detect slowly-varying gradients and, therefore, trigger the reuse of outdated gradients. The resultant gradient-based algorithms are termed Lazily Aggregated Gradient --- justifying our acronym LAG used henceforth. Theoretically, the merits of this contribution are: i) the convergence rate is the same as batch gradient descent in strongly-convex, convex, and nonconvex smooth cases; and, ii) if the distributed datasets are heterogeneous (quantified by certain measurable constants), the communication rounds needed to achieve a targeted accuracy are reduced thanks to the adaptive reuse of lagged gradients. Numerical experiments on both synthetic and real data corroborate a significant communication reduction compared to alternatives.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “The synthetic data tests linear regression with increasing smoothness constants and logistic regression with uniform smoothness constants (Chen et al., 2018).”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “To further reduce the communication overhead, one promising direction is to compress the variables that are sent between diﬀerent workers [Chen et al., 2018, Wang et al., 2018].”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “There have been massive amount of work in the context of algorithms [37, 33, 36, 5, 26] and systems [16, 43, 9] that improve the communication efficiency of synchronous distributed SGD in a fully-connected network.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “A Lazily Aggregated Gradient (LAG) strategy is studied to reduce the communication cost for Gradient Descent based distributed learning (Chen et al., 2018).”
Wireless Network Intelligence at the Edge (2018, background): “, sparsification [192], opportunistic uploading based on gradient magnitudes [193], and adaptively adjusting the communication intervals [31], [194].”
Scheduling Policies for Federated Learning in Wireless Networks (2019, methodology): “From an algorithmic perspective, the idea is to reduce the overhead in the update uploading phase to make the model training communication efficient, where typical methods range from reducing the communication bandwidth by only updating the UEs with significant training improvement [12], compressing”
FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (2020, background): “A number of recent works such as Lazily Aggregated Gradient (LAG) [23] and COLA [24] have been proposed to occasionally skip message exchanges among the agents to save communication.”
Distillation-Based Semi-Supervised Federated Learning for Communication-Efficient Collaborative Training With Non-IID Private Data (2020, methodology): “Another stream of research proposed themodel compression to reduce the communication cost required for the model parameter exchanges, which can be performed via several strategies, such as low-rank representation [17], model parameter quantization [17], [18], [19], neural network pruning [20], updat”
Asynchronous Online Federated Learning for Edge Devices with Non-IID Data (2019, methodology): “These methods are costly due to a synchronization [7] step (shown in Figure 1), where the server needs to wait for all local updates before aggregation.”
Over-the-Air Machine Learning at the Wireless Edge (2019, methodology): “Numerous studies have focused on communication-efficient DSGD schemes, where three main approaches are employed; namely, quantization [1]–[3], sparsification [4], [6], [7], and local updates [8], [9].”
Decentralized Federated Averaging (2021, methodology): “Compared with existing works on FedAvg [1], [8], [9], [10], [11], this paper uses a decentralized framework to enhance the robustness of FL to node failures and privacy”
Convergence Time Optimization for Federated Learning Over Wireless Networks (2020, methodology): “However, the LAG algorithm in [16] is a deterministic user selection scheme [16] in which some users may not get an opportunity to send their local FL models to the BS thus increasing the training loss.”
RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets (2018, unknown): “Other related work in this context includes (Yin et al. 2018b) that targets escaping saddle points of nonconvex optimization problems under Byzantine attacks, and (Chen et al. 2018a) that leverages a gradient-coding based algorithm for robust learning.”
Distributed Learning in Wireless Networks: Recent Progress and Future Challenges (2021, methodology): “accelerate learning [59], [76], [77], or compressing updates by exploiting their sparsity using the techniques outlined in Subsection II-D1.”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, methodology): “Lazily aggregated quantized gradient method (LAQ) is one example that combines the gradient update quantization with temporal sparsification, in a way that the number of links is sparsified based on the temporal gradient update difference, and the gradient update difference is adaptively adjusted fo”