Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD

By Jianyu Wang, Gauri Joshi. 2018

256 citations recorded by the source corpus.

Large-scale machine learning training, in particular distributed stochastic gradient descent, needs to be robust to inherent system variability such as node straggling and random communication delays. This work considers a distributed training framework where each worker node is allowed to perform local model updates and the resulting models are averaged periodically. We analyze the true speed of error convergence with respect to wall-clock time (instead of the number of iterations), and analyze how it is affected by the frequency of averaging. The main contribution is the design of AdaComm, an adaptive communication strategy that starts with infrequent averaging to save communication delay and improve convergence speed, and then increases the communication frequency in order to achieve a low error floor. Rigorous experiments on training deep neural networks show that AdaComm can take $3 \times$ less time than fully synchronous SGD, and still reach the same final training loss.

Subfields: Artificial Intelligence, 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 Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “Given a model for wall clock time, our analysis can be readily extended to further fine-tune the communication-computation complexity of [37].”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “A similar phenomena is also observed by an independent work [43], which finds that faster initial drop of global loss will result higher final error floor.”
Improving Federated Learning Personalization via Model Agnostic Meta Learning (2019, background): “Consequently, the recommendations that in order to stabilize the convergence, one might decrease the number of local epochs or the local learning rate (McMahan et al., 2017; Wang & Joshi, 2018), are in some scenarios misguided.”
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”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, methodology): “Thus, MATCHA belongs to the class of local-update SGD methods recently studied in [22, 27, 28].”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “…first time that a distributed momentum SGD method for non-convex stochastic optimization is proven to possess the same linear speedup property (with communication reduction) as distributed SGD (without momentum) in (Lian et al., 2017; Yu et al., 2018; Wang & Joshi, 2018a; Jiang & Agrawal, 2018).”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “5 We directly compare to the reported values of [53], as some missing descriptions and hyperparameters prevented us from reproducing the results ourselves.”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Parallel SGD and related variants, which make local updates similar to FedAvg , have been analyzed in the I.I.D. setting [68, 93, 104, 108, 120, 121, 122, 125, 136, 140].”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “time considerations is studied in [25] for the datacenter setting.”
ATP: In-network Aggregation for Multi-tenant Learning (2021, background): “(2) reducing network traffic – using large batch size to reduce the communication frequency [11, 29, 38]; using quantization [57] or reducing redundancy in SGD [45] to reduce bytes sent over the network; optimizing mixture of local-global aggregation to adapt to network change at runtime [21, 64].”
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].”
Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD (2020, background): “As observed in experiments [14], a larger number of local updates τ requires less communication but typically leads to a higher error at convergence.”
Model Pruning Enables Efficient Federated Learning on Edge Devices (2019, methodology): “To improve the communication efficiency of FL, methods for optimizing the communication frequency were studied [25]–[27].”
Communication-Efficient Edge AI: Algorithms and Systems (2020, background): “…via over-the-air computation [21], [84], [85], [86] • Aggregation frequency control with limited bandwidth and computation resources [87], [88], [89] • Data reshufﬂing via index coding and pliable index coding for improving training performance [90], [91], [92] • Straggler mitigation via coded…”
BatchCrypt: Efficient Homomorphic Encryption for Cross-Silo Federated Learning (2020, background): “So the existing theories and optimizations including ﬂexible synchronization [24,34,62] and local update SGD [22,35,56] naturally apply.”
A Crowdsourcing Framework for On-Device Federated Learning (2019, methodology): “In the recent work [27], the authors designed a robust method which applies the proposed periodicaveraging SGD (PASGD) technique to prevent communication delay in the distributed SGD setting.”