Federated Learning under Arbitrary Communication Patterns

Dmitrii Avdiukhin, Shiva Prasad KasiviswanathanICML 2021 · OpenReview

Introduction

Standard Federated Learning (FL) algorithms often rely on a strict "synchronous" assumption: the central server waits for a specific set of clients to finish their local work and report back before updating the global model. In real-world scenarios, this is highly impractical. Mobile devices experience spotty network connections, varying processor speeds, and fluctuating battery levels. Forcing the entire system to wait for the slowest "straggler" severely bottlenecks efficiency.

While asynchronous algorithms exist, previous theoretical analyses suggested they were significantly worse than their synchronous counterparts. Specifically, there was a large mathematical gap regarding how much delay (staleness) the system could handle before performance degraded. This paper proves that Federated Learning doesn't need to be perfectly synchronized to be effective. The authors demonstrate that an asynchronous version of local SGD—where clients communicate with the server at arbitrary, irregular intervals—achieves the same theoretical convergence rates as synchronous versions, significantly improving previous mathematical bounds for both convex and non-convex problems.

The ASYNCCOMMSGD Algorithm

To address the synchronization bottleneck, the authors analyze an algorithm called ASYNCCOMMSGD. The process operates under three main principles:

  1. Local Updates: Every client performs local Stochastic Gradient Descent (SGD) steps on its own data independently.
  2. Arbitrary Communication: Instead of waiting for a synchronized "round" to end, clients send their updates to the server whenever they are able. The only constraint is a maximum delay ($\Delta$); every client must check in at least once every $\Delta$ iterations.
  3. Server Averaging: The server maintains a global model by averaging the latest available parameters from all $N$ clients. If a client hasn't checked in recently, the server simply uses the last version it received from them.

The "secret sauce" of their mathematical proof is the use of a Virtual Sequence. Since the actual iterates on the server and clients are messy and out-of-sync, the authors construct a theoretical "shadow" sequence representing what the model would look like if all updates were applied instantly. By proving this virtual sequence converges and showing the real iterates stay close to it, they derive much tighter bounds than previous research.

Experimental Setup

The researchers evaluated their approach using three standard computer vision benchmarks: MNIST, Fashion-MNIST, and CIFAR-10. They utilized a variety of models, ranging from simple one-layer networks to a shallow CNN and the deeper ResNet-34.

To simulate the "Non-IID" (non-identically distributed) nature of federated data, they introduced a mixing rate ($\mu$), which controls how much data from other classes a client sees versus its "assigned" primary class. A lower mixing rate means the data is more heterogeneous across clients.

Key Findings and Results

The study yields several critical insights into the viability of asynchronous federated learning:

  • Staleness is Manageable: The most surprising finding is that the "noise" introduced by stale updates (from clients who haven't communicated recently) doesn't slow down the fundamental convergence rate, provided the delay is bounded.
  • Square-Factor Improvement: Previous work suggested that the error caused by asynchrony grew very quickly as the delay $\Delta$ increased. This paper improves those bounds by a "square factor" (e.g., turning a $\Delta^4$ dependence into a $\Delta^2$), bringing the theory in line with practical engineering observations.
  • Theoretical Matching: For both strongly convex and non-convex functions, the algorithm reaches the same "statistical term" (the core speed limit of SGD) as the synchronous version. In the strongly convex case, the communication gap $\Delta$ can be as large as $O(\sqrt{T/N})$ without hurting the final accuracy.
Test Accuracy vs Total Communication across datasets and mixing rates
  • Empirical Performance: In experiments, asynchronous patterns like "Round Robin" (where clients take turns) often reached high accuracy using significantly less total communication than standard synchronous SGD.
  • Robustness to Non-IID Data: As seen in the experimental results, the algorithm performed consistently well even when clients had very different data distributions. It only showed significant degradation when the data was almost entirely disjoint ($\mu=0$). By having the server average the latest copy of every client (even stale ones), the algorithm ensures that the global model doesn't "forget" the data distributions of slower clients.

Limitations and Future Work

While the results are promising, the study has a few limitations:

  • The Bounded Gradient Assumption: Like many optimization papers, this analysis assumes that gradients don't explode (bounded second moment). Relaxing this assumption remains an interesting open problem.
  • The Hard Deadline: The proof still requires a maximum delay $\Delta$. If a client drops out forever, the current theory doesn't strictly hold because that client's unique data would be missing from the final solution.
  • Refining Heterogeneity: The authors suggest that current ways of measuring "data difference" between clients don't fully capture why some algorithms work so well even on very diverse data. Future work could involve creating better metrics for data diversity in FL.

Summary updated

Abstract

Federated Learning is a distributed learning setting where the goal is to train a centralized model with training data distributed over a large number of heterogeneous clients, each with unreliable and relatively slow network connections. A common optimization approach used in federated learning is based on the idea of local SGD: each client runs some number of SGD steps locally and then the updated local models are averaged to form the updated global model on the coordinating server. In this paper, we investigate the performance of an asynchronous version of local SGD wherein the clients can communicate with the server at arbitrary time intervals. Our main result shows that for smooth strongly convex and smooth nonconvex functions we achieve convergence rates that match the synchronous version that requires all clients to communicate simultaneously.
BibTeX
@inproceedings{avdiukhin2021federated,
  author = {Dmitrii Avdiukhin and Shiva Prasad Kasiviswanathan},
  title = {{Federated Learning under Arbitrary Communication Patterns}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=EJzvVmJLB6},
}
Figure