Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients

Abstract

Federated learning (FL) is a new machine learning framework which trains a joint model across a large amount of decentralized computing devices. Existing methods, e.g., Federated Averaging (FedAvg), are able to provide an optimization guarantee by synchronously training the joint model, but usually suffer from stragglers, i.e., IoT devices with low computing power or communication bandwidth, especially on heterogeneous optimization problems. To mitigate the influence of stragglers, this paper presents a novel FL algorithm, namely Hybrid Federated Learning (HFL), to achieve a learning balance in efficiency and effectiveness. It consists of two major components: synchronous kernel and asynchronous updater. Unlike traditional synchronous FL methods, our HFL introduces the asynchronous updater which actively pulls unsynchronized and delayed local weights from stragglers. An adaptive approximation method, Adaptive Delayed-SGD (AD-SGD), is proposed to merge the delayed local updates into the joint model. The theoretical analysis of HFL shows that the convergence rate of the proposed algorithm is $\mathcal{O}(\frac{1}{t+\tau })$ for both convex and non-convex optimization problems.

References in corpus (19)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Recurrent Neural Network Regularization
• Federated Learning with Non-IID Data
• Federated Learning for Mobile Keyboard Prediction
• On the Convergence of FedAvg on Non-IID Data
• The Loss Surfaces of Multilayer Networks
• Applied Federated Learning: Improving Google Keyboard Query Suggestions
• Federated Optimization in Heterogeneous Networks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• Distributed Random Projection Algorithm for Convex Optimization
• Local Model Poisoning Attacks to Byzantine-Robust Federated Learning
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• A Little Is Enough: Circumventing Defenses For Distributed Learning
• A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates

Cited by in corpus (2)

• FedLGA: Towards System-Heterogeneity of Federated Learning via Local Gradient Approximation
• Federated Learning with Buffered Asynchronous Aggregation