Federated Block Coordinate Descent Scheme for Learning Global and Personalized Models

Ruiyuan Wu, Anna Scaglione, Hoi-To Wai, Nurullah Karakoç, Kari Hreinsson, Wing-Kin Ma

Abstract

In federated learning, models are learned from users’ data that are held private in their edge devices, by aggregating them in the service provider’s “cloud” to obtain a global model. Such global model is of great commercial value in, e.g., improving the customers’ experience. In this paper we focus on two possible areas of improvement of the state of the art. First, we take the difference between user habits into account and propose a quadratic penalty-based formulation, for efficient learning of the global model that allows to personalize local models. Second, we address the latency issue associated with the heterogeneous training time on edge devices, by exploiting a hierarchical structure modeling communication not only between the cloud and edge devices, but also within the cloud. Specifically, we devise a tailored block coordinate descent-based computation scheme, accompanied with communication protocols for both the synchronous and asynchronous cloud settings. We characterize the theoretical convergence rate of the algorithm, and provide a variant that performs empirically better. We also prove that the asynchronous protocol, inspired by multi-agent consensus technique, has the potential for large gains in latency compared to a synchronous setting when the edge-device updates are intermittent. Finally, experimental results are provided that corroborate not only the theory, but also show that the system leads to faster convergence for personalized models on the edge devices, compared to the state of the art.

Introduction

Standard Federated Learning (FL) typically aims to train a single "one-size-fits-all" global model. However, two major hurdles persist: data heterogeneity (non-i.i.d. data) and system latency. Users have different habits, meaning a single global model may fail to perform optimally for any specific individual. Furthermore, most FL protocols are synchronous; if a few edge devices are slow (the "straggler" problem), the entire global update process stalls. This paper introduces FedBCD, a framework that balances model personalization with communication efficiency.

Methods: The FedBCD Framework

The authors propose the Federated Block Coordinate Descent (FedBCD) scheme, which relies on two core innovations:

1. Quadratic Penalty for Personalization

Instead of forcing every local model $x_i$ to be identical to the global model $z$, FedBCD introduces a penalty term $\frac{\gamma_i}{2} \|x_i - z\|^2$. This formulation allows local models to deviate based on local data while staying anchored to the aggregated "wisdom of the crowd."

2. Hierarchical and Asynchronous Cloud Architecture

The framework moves away from a monolithic cloud toward a cluster of servers. This hierarchical structure allows for more flexible communication patterns between edge devices and the cloud infrastructure.

Hierarchical communication architecture showing the transition from a single cloud entity to a distributed cloud-server model that communicates with edge devices.

To combat latency, the authors developed an Async-cloud protocol. Unlike synchronous systems that wait for all participants, the asynchronous version triggers aggregation as soon as a subset of servers are ready. This is inspired by multi-agent consensus techniques, allowing the global model to progress even when some edge-device updates are intermittent.

Comparison of the Sync-cloud and Async-cloud protocols, illustrating how the asynchronous approach overlaps update and aggregation phases to reduce idle time.

Experimental Results

The researchers evaluated FedBCD using MNIST and CIFAR-10 benchmarks under non-i.i.d. conditions.

  • Superior Personalization: In MNIST tests with low data diversity, FedBCD achieved personalized test accuracy approaching 90-100%, significantly outperforming FedAvg and FedProx (70-80%), which enforce strict model consensus.
  • Wall-Clock Speedups: The asynchronous protocol showed massive gains in runtime. For CIFAR-10, the Async version reached high accuracy levels much faster than the Sync version, effectively mitigating the straggler problem.
  • Global Stability: Despite allowing local deviations, the global model performance remained competitive with state-of-the-art methods, proving that personalization does not necessitate a sacrifice in collective model quality.

Conclusion and Future Work

FedBCD successfully addresses the dual challenges of personalization and latency in federated learning. By decoupling local training from rigid global synchronization, the system achieves faster convergence and better local performance. Future research may focus on reducing dependency on a central coordinator, moving toward fully decentralized "serverless" federated environments.

Summary updated

Abstract

In federated learning, models are learned from users’ data that are held private in their edge devices, by aggregating them in the service provider’s “cloud” to obtain a global model. Such global model is of great commercial value in, e.g., improving the customers’ experience. In this paper we focus on two possible areas of improvement of the state of the art. First, we take the difference between user habits into account and propose a quadratic penalty-based formulation, for efficient learning of the global model that allows to personalize local models. Second, we address the latency issue associated with the heterogeneous training time on edge devices, by exploiting a hierarchical structure modeling communication not only between the cloud and edge devices, but also within the cloud. Specifically, we devise a tailored block coordinate descent-based computation scheme, accompanied with communication protocols for both the synchronous and asynchronous cloud settings. We characterize the theoretical convergence rate of the algorithm, and provide a variant that performs empirically better. We also prove that the asynchronous protocol, inspired by multi-agent consensus technique, has the potential for large gains in latency compared to a synchronous setting when the edge-device updates are intermittent. Finally, experimental results are provided that corroborate not only the theory, but also show that the system leads to faster convergence for personalized models on the edge devices, compared to the state of the art.
BibTeX
@inproceedings{wu2021federated,
  author = {Ruiyuan Wu and Anna Scaglione and Hoi-To Wai and Nurullah Karakoç and Kari Hreinsson and Wing-Kin Ma},
  title = {{Federated Block Coordinate Descent Scheme for Learning Global and Personalized Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=Gx2lQK_XG9f},
}
Figure