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

Cheng Chen, Ziyi Chen, Yi Zhou, Bhavya Kailkhura

TL;DR

This paper introduces FedCluster, a novel federated learning framework that significantly accelerates convergence by organizing devices into clusters and cycling through them for updates within each learning round. This "cluster-cycling" approach leads to faster convergence, especially in the presence of heterogeneous data, outperforming traditional federated averaging (FedAvg).

What Problem Does This Paper Address?

Federated learning (FL) enables distributed model training across numerous devices without centralizing raw data, preserving privacy. However, a major bottleneck is the slow convergence of algorithms like FedAvg, primarily due to device-level data heterogeneity (non-IID data). Existing methods like FedProx or variance reduction techniques offer improvements but often still suffer from infrequent global model updates per round. The paper aims to address this by proposing a framework that allows for more frequent global model updates within the same resource constraints, thereby boosting optimization efficiency and convergence speed, particularly in challenging non-convex optimization scenarios.

Methods

The core innovation is the FedCluster framework. Instead of activating all participating devices in a round for a single global update, FedCluster first groups devices into multiple clusters. Within a single learning round, these clusters are then activated sequentially in a cyclic manner. This means that a learning round now consists of multiple "cycles," where each cycle involves a subset of devices from one cluster performing local training and contributing to a global model update.

Key aspects of the method include:

  • Cluster-Cycling: The central idea is to perform federated learning in multiple stages within a single round, with each stage focusing on a different cluster. This allows for more frequent model updates to the global model.
  • Generality: FedCluster is designed to be a general framework. It can accommodate any existing federated learning algorithm (e.g., FedAvg, FedProx) within its clusters.
  • Theoretical Analysis: The authors provide theoretical convergence guarantees for FedCluster with local SGD in non-convex optimization. They show that FedCluster achieves a faster convergence rate of $O(1/\sqrt{TME})$ compared to FedAvg's $O(1/\sqrt{T})$, where $T$ is the number of rounds, $M$ is the number of clusters, and $E$ is the number of local epochs. Crucially, FedCluster's convergence depends on cluster-level data heterogeneity ($H_{cluster}$), which is shown to be less than or equal to device-level heterogeneity ($H_{device}$), thus making it more robust to data variations.
  • Clustering Strategies: The paper suggests various ways to form clusters, including random uniform, timezone-based, and availability-based clustering, allowing flexibility based on the application scenario.

Datasets

The experiments were conducted on two standard deep learning datasets:

  • CIFAR-10: A widely used dataset for image classification.
  • MNIST: A dataset of handwritten digits, also common for benchmarking.

The authors simulated 1000 devices, each with 500 data samples, and introduced varying levels of device-level data heterogeneity by assigning a "major class" to subsets of devices and sampling the remaining data from other classes.

Key Insights and Ideas

  • More frequent updates = faster convergence: The core insight is that by breaking down a single learning round into multiple "mini-rounds" (cycles) across clusters, the global model is updated more frequently. This leads to significantly faster convergence, especially when data is heterogeneous.
  • Cluster-level heterogeneity matters more: The theoretical analysis reveals that FedCluster's convergence is primarily influenced by the heterogeneity between clusters, not just the heterogeneity within each device. This is a key advantage, as it allows for more effective learning even when individual devices have very different data distributions.
  • Flexibility is key: FedCluster isn't tied to a specific local optimizer. Its ability to integrate existing FL algorithms makes it a versatile framework for improving performance across various scenarios.
  • Trade-offs in clustering: The number of clusters ($M$) and the clustering strategy itself impact convergence. More clusters can lead to faster convergence (as per theory), but practical limitations on the number of cycles per round exist.

Key Results

  • Faster Convergence: Experiments consistently show FedCluster converging significantly faster than FedAvg on both CIFAR-10 and MNIST datasets, across various levels of device-level data heterogeneity. This holds true for train loss and test accuracy.
  • Robustness to Heterogeneity: FedCluster demonstrates superior performance compared to FedAvg when device-level data heterogeneity is high.
  • Optimizer Agnostic: FedCluster shows significant improvements over FedAvg when using different local optimizers like SGD-momentum, Adam, and FedProx.
  • Impact of Cluster Number: Increasing the number of clusters generally leads to faster convergence for FedCluster, aligning with theoretical predictions.
  • Theoretical Guarantees: The paper provides theoretical convergence rates for non-convex optimization, showing FedCluster's $O(1/\sqrt{TME})$ rate is superior to FedAvg's $O(1/\sqrt{T})$.

Limitations and Future Work

  • Clustering Strategy: While the paper proposes several clustering approaches, the optimal strategy for different scenarios is not definitively determined and remains an area for future exploration. The impact of the clustering approach on performance is noted as an interesting avenue.
  • Practical Implementation: The authors express hope that FedCluster can be implemented in practical systems to demonstrate its benefits.
  • Random Cyclic Order: The impact of the random cyclic order of cluster activation on performance is also highlighted as a future research direction.
  • Resource Constraints: While FedCluster adheres to the stated resource constraints (two communications and a fixed number of local updates per device per round), the paper focuses on theoretical analysis under full participation and simplified assumptions. Further analysis under partial participation and more complex communication patterns could be explored.

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 (Fe-dAvg) 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},
}

Loading related content...

Figure