FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling

Cheng Chen, Ziyi Chen, Yi Zhou, Bhavya Kailkhura

Abstract

We develop FedCluster—a novel federated learning framework with improved optimization efficiency, and investigate its theoretical convergence properties. The FedCluster groups the devices into multiple clusters that perform federated learning cyclically in each learning round. Therefore, each learning round of FedCluster consists of multiple cycles of meta-update that boost the overall convergence. In nonconvex optimization, we show that FedCluster with the devices implementing the local stochastic gradient descent (SGD) algorithm achieves a faster convergence rate than the conventional federated averaging (FedAvg) algorithm in the presence of device-level data heterogeneity. We conduct experiments on deep learning applications and demonstrate that FedCluster converges significantly faster than the conventional federated learning under diverse levels of device-level data heterogeneity for a variety of local optimizers.

Introduction

Standard Federated Learning, particularly the widely used Federated Averaging (FedAvg) algorithm, faces significant efficiency hurdles. The primary bottlenecks are infrequent global updates and severe data heterogeneity (non-IID data) among devices. In FedAvg, the server waits for a subset of devices to complete local training before performing a single global update per round. This approach fails to fully exploit the potential for optimization progress within a single communication cycle. Furthermore, "client drift" caused by heterogeneous data distributions across devices can lead to unstable or slow convergence.

FedCluster addresses these issues by introducing a "cluster-cycling" mechanism that increases the frequency of global updates without increasing the communication overhead for individual devices.

The FedCluster Framework

The core innovation of FedCluster is the organization of participating devices into $M$ distinct clusters. Instead of the parallel update scheme used in standard FL, FedCluster employs a sequential "relay" fashion within each learning round.

Comparison of standard Federated Learning (left) and the proposed FedCluster framework (right).

In each round:

  • Sequential Execution: Clusters perform FL tasks one after another. Cluster 1 downloads the initial global model, trains locally, and uploads updates. The server then produces an intermediate global model.
  • Cycle Progression: Cluster 2 downloads this updated model to begin its own training phase. This process continues until all $M$ clusters have contributed.
  • Resource Efficiency: Despite the sequential nature at the cluster level, each individual device still only performs one download and one upload per round, maintaining the same resource footprint as FedAvg.

This framework is highly flexible, acting as a "meta-framework" that can incorporate various local optimizers such as SGD, Adam, or FedProx.

Theoretical and Practical Advantages

FedCluster offers two major advantages:

  • Convergence Speedup: Theoretically, for non-convex optimization, FedCluster achieves a convergence rate of $O(1/\sqrt{TME})$, effectively providing a $\sqrt{M}$ speedup over FedAvg's $O(1/\sqrt{TE})$ in terms of learning rounds.
  • Mitigating Heterogeneity: By grouping devices, the framework operates on cluster-level data heterogeneity, which is mathematically guaranteed to be lower than the device-level heterogeneity that hampers FedAvg. The grouping effectively "smooths" the noise from individual non-IID datasets.

Experimental Evaluation

The researchers evaluated FedCluster using standard benchmarks like CIFAR-10 and MNIST with AlexNet architectures. They simulated 1,000 devices and varied data heterogeneity using a ratio $\rho_{device}$, where higher values indicate more extreme non-IID distributions.

Test accuracy on CIFAR-10 using AlexNet, comparing FedCluster and FedAvg under different levels of data heterogeneity.

Key results include:

  • Superior Performance: FedCluster consistently reached higher accuracy levels faster than FedAvg, especially in high-heterogeneity scenarios ($\rho = 0.9$).
  • Optimizer Robustness: The benefits of FedCluster were observed across multiple local optimizers, including Momentum and FedProx.
  • Scalability: Increasing the number of clusters ($M$) generally improved convergence, though practical limits exist based on the total time allocated for a single learning round.

Conclusion

FedCluster represents a significant step forward in making federated learning more efficient for real-world, heterogeneous edge environments. By simply reordering updates into sequential clusters, it achieves faster convergence and better handling of non-IID data without increasing device-level communication costs. Future work may explore asynchronous updates to mitigate straggler effects and more sophisticated clustering strategies based on network topology or data distribution.

Summary updated

Abstract

We develop FedCluster--a novel federated learning framework with improved optimization efficiency, and investigate its theoretical convergence properties. The FedCluster groups the devices into multiple clusters that perform federated learning cyclically in each learning round. Therefore, each learning round of FedCluster consists of multiple cycles of meta-update that boost the overall convergence. In nonconvex optimization, we show that FedCluster with the devices implementing the local {stochastic gradient descent (SGD)} algorithm achieves a faster convergence rate than the conventional {federated averaging (FedAvg)} algorithm in the presence of device-level data heterogeneity. We conduct experiments on deep learning applications and demonstrate that FedCluster converges significantly faster than the conventional federated learning under diverse levels of device-level data heterogeneity for a variety of local optimizers.
BibTeX
@inproceedings{chen2020fedcluster,
  author = {Cheng Chen and Ziyi Chen and Yi Zhou and Bhavya Kailkhura},
  title = {{FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling}},
  booktitle = {Accepted by IEEE International Conference on Big Data},
  year = {2020},
  url = {https://openreview.net/forum?id=hK6YV9LoXH},
}
Figure