Gradual Federated Learning with Simulated Annealing

Luong Trung Nguyen, Junhan Kim, Byonghyo ShimIEEE TSP 2021 · DOI · OpenReview

Abstract

Federated averaging (FedAvg) is a popular federated learning (FL) technique that updates the global model by averaging local models and then transmits the updated global model to devices for their local model update. One main limitation of FedAvg is that the average-based global model is not necessarily better than local models in the early stage of the training process so that FedAvg might diverge in realistic scenarios, especially when the data is non-identically distributed across devices and the number of data samples varies significantly from device to device. In this paper, we propose a new FL technique based on simulated annealing. The key idea of the proposed technique, henceforth referred to as simulated annealing-based FL (SAFL), is to allow a device to choose its local model when the global model is immature. Specifically, by exploiting the simulated annealing strategy, we make each device choose its local model with high probability in early iterations when the global model is immature. From extensive numerical experiments using various benchmark datasets, we demonstrate that SAFL outperforms the conventional FedAvg technique in terms of the convergence speed and the classification accuracy.

Introduction

Standard Federated Learning (FL), specifically the ubiquitous Federated Averaging (FedAvg) algorithm, relies on a central server to aggregate local model updates from distributed devices to create a superior global model. As shown in Figure 1, this process involves distributing a common model, performing local training, and then averaging these updates at the server.

The standard Federated Averaging (FedAvg) process: (1) distributing the common model, (2) local training, and (3) global model update via averaging.

However, this "collaboration first" approach has a significant drawback. In the early stages of training, or when data is highly heterogeneous (non-IID) across devices, the averaged global model can actually be inferior to a device's locally trained model. Forcing a device to adopt an "immature" global model can lead to training divergence, overfitting to the global average, and poor final accuracy. Essentially, collaboration can do more harm than good if the participants aren't "ready" yet.

Simulated Annealing-based Federated Learning (SAFL)

To address these limitations, we propose SAFL, which draws inspiration from Simulated Annealing (SA)—a probabilistic optimization technique used to find global minima in complex landscapes.

Probabilistic Model Selection

Instead of blindly accepting the global model, each device in SAFL chooses between its locally updated model and the global feedback. This choice is governed by a probability $p = \exp(-t/L)$, where $t$ is the iteration and $L$ is a control parameter.

The concept of simulated annealing applied to the cost function. SAFL uses a probabilistic update to avoid local minimum traps by allowing local autonomy in early stages.

In early iterations (high "temperature"), devices have a high probability of sticking with their local updates. As training progresses and the system "cools," they rely more heavily on the global server feedback. This gradual transition ensures that the global model has time to mature before it becomes the primary driver of local updates.

Extended SAFL

We also introduce an "Extended" version of SAFL designed for environments with biased or non-representative data. In this variant, devices measure the performance gap between the global model and their local model. If the gap is excessively large, indicating a potential bias that could "poison" the global consensus, the device reduces its probability of uploading updates to the server. This acts as a decentralized gatekeeper, allowing devices to self-identify when their data might be an outlier.

Experimental Results

The performance of SAFL was evaluated against standard FedAvg and other state-of-the-art techniques using four major benchmarks: MNIST, Fashion-MNIST (FMNIST), CIFAR-10, and Google Speech Commands (GSC). To simulate realistic conditions, data was partitioned non-IID across devices.

Key findings include:

  • Faster Convergence: On the MNIST dataset, SAFL converged two times faster than conventional FedAvg.
  • Improved Accuracy: In early rounds, SAFL showed massive gains. For instance, at the 50th communication round on MNIST, SAFL achieved 94% accuracy compared to FedAvg's 30%. On FMNIST, top-1 accuracy improved by 17% over conventional approaches.
  • Communication Efficiency: The Extended SAFL variant reduced local update uploads by over 30% without sacrificing accuracy, significantly saving bandwidth.
  • Robustness: SAFL consistently outperformed advanced fusion models like IDA (Inverse Distance Aggregation) and FedMA in highly heterogeneous data environments.

Conclusion

SAFL provides a robust framework for federated learning by recognizing that global collaboration is most effective when the global model has reached a certain level of maturity. By allowing local models to "warm up" independently through a simulated annealing schedule, SAFL achieves superior stability and performance in non-IID scenarios. Future work will explore extending this gradual approach to multi-task learning and optimizing the computational overhead for low-power IoT devices.

Summary updated

Abstract

Federated averaging (FedAvg) is a popular federated learning (FL) technique that updates the global model by averaging local models and then transmits the updated global model to devices for their local model update. One main limitation of FedAvg is that the average-based global model is not necessarily better than local models in the early stage of the training process so that FedAvg might diverge in realistic scenarios, especially when the data is non-identically distributed across devices and the number of data samples varies significantly from device to device. In this paper, we propose a new FL technique based on simulated annealing. The key idea of the proposed technique, henceforth referred to as \textit{simulated annealing-based FL} (SAFL), is to allow a device to choose its local model when the global model is immature. Specifically, by exploiting the simulated annealing strategy, we make each device choose its local model with high probability in early iterations when the global model is immature. From extensive numerical experiments using various benchmark datasets, we demonstrate that SAFL outperforms the conventional FedAvg technique in terms of the convergence speed and the classification accuracy.
BibTeX
@article{nguyen2021gradual,
  author = {Luong Trung Nguyen and Junhan Kim and Byonghyo Shim},
  title = {{Gradual Federated Learning with Simulated Annealing}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  doi = {10.1109/tsp.2021.3125137},
}
Figure