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. This paper addresses two critical bottlenecks: model personalization and synchronization latency. We propose a quadratic penalty-based formulation for efficient learning of personalized local models and a hierarchical asynchronous cloud architecture to mitigate latency issues. We devise a tailored block coordinate descent-based computation scheme (FedBCD) and characterize its theoretical convergence. Experimental results demonstrate faster convergence for personalized models compared to state-of-the-art methods.

Introduction

Federated Learning (FL) typically aims to train a single "global model" across decentralized edge devices without sharing raw data. However, current approaches like FedAvg face two major challenges:

  1. Model Personalization: Diverse user habits and non-i.i.d. data distributions make a single global model suboptimal for individual users, often resulting in a "jack of all trades, master of none."
  2. Synchronization Latency: Traditional "Sync-cloud" models wait for all devices to finish local training before aggregation. Because edge devices have heterogeneous computing power and intermittent connectivity, "stragglers" frequently stall the entire training process.

The FedBCD Framework

We introduce the Federated Block Coordinate Descent (FedBCD) scheme to address these challenges simultaneously through a hierarchical approach.

Quadratic Penalty Formulation

Instead of forcing local models ($x_i$) to be identical to the global model ($z$), FedBCD employs a soft constraint via a quadratic penalty term: $\frac{\gamma_i}{2} \|x_i - z_n\|^2$. This acts as an "anchor," encouraging local models to stay near the global model's collective knowledge while providing the freedom to specialize on local data distributions.

Hierarchical Async-cloud Architecture

We propose moving away from a monolithic cloud server to a cluster of servers connected via a multi-agent graph. Communication is structured in two layers:

  • Edge-to-Cloud: Master-slave communication between devices and their assigned cloud servers.
  • Cloud-to-Cloud: Multi-agent consensus between servers within the cloud.
Comparison of the traditional Sync-cloud architecture (a) and the proposed hierarchical Async-cloud architecture (b).

Communication Protocols and Latency

The asynchronous protocol allows cloud servers to enter the aggregation phase as soon as a subset of devices responds, rather than waiting for all participants. This "first-come, first-served" approach significantly reduces idle time caused by stragglers.

Communication timelines for synchronous (a) vs. asynchronous (b) protocols, highlighting the reduction in idle time for the coordinator and servers.

We also provide a practical variant, FedBCD-I, which allows edge devices to perform local training "offline" and sync the penalty term only when re-connected, further improving utility in real-world scenarios with intermittent connectivity.

Results and Discussion

We prove that FedBCD achieves a sublinear convergence rate of $O(1/\sqrt{T})$ for non-convex problems, matching existing decentralized algorithms while offering better practical latency. Analysis shows that latency gains from the asynchronous protocol scale with the number of cloud servers, particularly when device updates are intermittent.

Experiments on MNIST and CIFAR-10 benchmarks with simulated data heterogeneity demonstrate:

  • Superior Personalization: FedBCD consistently achieves higher personalized test accuracy than FedAvg and FedProx.
  • Wall-clock Speedup: The asynchronous protocol reaches target accuracy levels significantly faster in actual runtime.
  • Global Stability: Despite allowing local models to deviate, the resulting global model remains competitive with traditional consensus-based methods.

Conclusion

FedBCD effectively balances the trade-off between global model consistency and local personalization while mitigating the impact of stragglers through an asynchronous hierarchical architecture. This dual-pronged approach offers a robust solution for large-scale federated learning deployments where device heterogeneity and user diversity are prevalent.

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