Hybrid Local SGD for Federated Learning with Heterogeneous Communications

Yuanxiong Guo, Ying Sun, Rui Hu, Yanmin GongICLR 2022 · OpenReview

TL;DR

Hybrid Local SGD (HL-SGD) is a novel federated learning algorithm designed to break the "slow-server" bottleneck by leveraging fast device-to-device (D2D) communication. By allowing nearby devices to "gossip" and average their models locally before communicating with the central server, HL-SGD achieves up to a 5.67x speedup in training time while significantly improving accuracy on non-identical (non-IID) data distributions.

The Challenge: Communication Bottlenecks and Data Heterogeneity

Federated Learning (FL) enables thousands of edge devices—such as smartphones or IoT sensors—to collaboratively train a shared machine learning model without ever transmitting their private data to a central server. Despite its privacy benefits, FL faces two massive hurdles:

  1. The Communication Bottleneck: Sending large model updates over cellular or wide-area networks (WAN) to a distant server is notoriously slow and expensive.
  2. Data Heterogeneity (Non-IID Data): Standard "Local SGD" algorithms—where devices train independently for several steps before syncing with the server—struggle when data is non-IID. If a device only encounters one specific type of data, its local model "drifts" or overfits to that niche, severely slowing down global convergence.

While modern network infrastructures (like 5G and LANs) offer incredibly fast Device-to-Device (D2D) links, most existing FL algorithms ignore this capability. They treat every device as an isolated island that can only communicate with the "mainland" central server.

The Solution: Hybrid Local SGD (HL-SGD)

The authors propose HL-SGD, a framework that organizes devices into disjoint clusters (e.g., devices on the same floor of a building or connected to the same 5G cell tower).

The HL-SGD Workflow: 1. Global Broadcast: The central server sends the current global model to all participating devices. 2. Gossip-based Local Training: For a set number of iterations ($\tau$), each device performs a local SGD update and then gossips (averages its model) with its immediate neighbors within its cluster. This local consensus acts as an anchor, preventing the "drift" typically caused by non-IID data. 3. Device Sampling: To conserve WAN bandwidth, only a small, representative fraction of devices from each cluster upload their updated models to the central server. 4. Global Aggregation: The server averages these cluster-representative models to update the global model, and the cycle repeats.

HL-SGD is a highly generalized framework. By tuning its parameters, it can seamlessly transition into standard Local SGD, Distributed SGD, or pure Gossip SGD, allowing practitioners to strike the optimal balance between model accuracy and runtime.

Key Insights and Ideas

  • D2D as a "Free" Regularizer: The core insight of HL-SGD is that D2D communication is often orders of magnitude faster than uploading to a remote server. By utilizing this "cheap" bandwidth to synchronize locally, devices act as a collective unit, naturally mitigating the negative effects of non-IID data.
  • Runtime vs. Iterations: Most FL literature focuses heavily on minimizing communication rounds. This paper argues that runtime (actual clock time) is the more practical metric. The authors provide a rigorous runtime analysis that explicitly accounts for the differing delays of D2D versus Device-to-Server (D2S) links.
  • Consensus is Key: Theoretical analysis demonstrates that as long as clusters reach an "approximate consensus" via internal gossiping, the server only needs to hear from a handful of devices per cluster to obtain an accurate estimation of the global gradient.

Key Results

The researchers evaluated HL-SGD on two standard computer vision benchmarks: FEMNIST (a dataset of handwritten characters naturally partitioned by the writer) and CIFAR-10 (artificially partitioned to create highly skewed, heterogeneous data distributions).

As shown in the performance charts below, HL-SGD proves to be both faster and more accurate than standard Local SGD across the board.

Test Accuracy vs. Round Number and Runtime for FEMNIST and CIFAR-10
  • Massive Speedups: On the FEMNIST dataset, HL-SGD reached a target test accuracy of 75% in just 17.6% of the time required by Local SGD—translating to a 5.67x speedup in actual runtime.
  • Higher Accuracy Ceiling: After 100 communication rounds on FEMNIST, HL-SGD achieved 83.76% accuracy, outperforming Local SGD by nearly 5%. On the more complex CIFAR-10 dataset, the improvement was even more pronounced (+9.32%).
  • Robustness to Local Work: Standard Local SGD often destabilizes if devices perform too many local steps ($\tau$) between server synchronizations. HL-SGD remains remarkably stable even with large $\tau$ values because the internal cluster gossiping prevents individual models from drifting too far from the consensus.

Limitations and Future Work

While HL-SGD presents a significant leap forward for federated optimization, the authors note a few areas for future exploration:

  • Stragglers: The current theoretical model does not explicitly account for "stragglers"—devices that compute significantly slower than their neighbors—which could potentially bottleneck the gossip phase within a cluster.
  • Dynamic Topologies: The paper assumes that device clusters are disjoint and relatively static. In highly mobile environments (such as connected vehicles on a highway), clusters might change rapidly, necessitating a more dynamic network analysis.
  • Privacy Trade-offs: Although the authors note that HL-SGD is compatible with Differential Privacy and Secure Aggregation techniques, the very act of gossiping model parameters with local neighbors introduces new peer-to-peer privacy considerations that warrant further investigation.

Summary updated

Abstract

Communication is a key bottleneck in federated learning where a large number of edge devices collaboratively learn a model under the orchestration of a central server without sharing their own training data. While local SGD has been proposed to reduce the number of FL rounds and become the algorithm of choice for FL, its total communication cost is still prohibitive when each device needs to communicate with the remote server repeatedly for many times over bandwidth-limited networks. In light of both device-to-device (D2D) and device-to-server (D2S) cooperation opportunities in modern communication networks, this paper proposes a new federated optimization algorithm dubbed hybrid local SGD (HL-SGD) in FL settings where devices are grouped into a set of disjoint clusters with high D2D communication bandwidth. HL-SGD subsumes previous proposed algorithms such as local SGD and gossip SGD and enables us to strike the best balance between model accuracy and runtime. We analyze the convergence of HL-SGD in the presence of heterogeneous data for general nonconvex settings. We also perform extensive experiments and show that the use of hybrid model aggregation via D2D and D2S communications in HL-SGD can largely speed up the training time of federated learning.
BibTeX
@inproceedings{guo2022hybrid,
  author = {Yuanxiong Guo and Ying Sun and Rui Hu and Yanmin Gong},
  title = {{Hybrid Local SGD for Federated Learning with Heterogeneous Communications}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=IbWAjDv-Zqe},
}
Figure