Resource Allocation for Compression-aided Federated Learning with High Distortion Rate

Xuan-Tung Nguyen, Minh-Duong Nguyen, Quoc-Viet Pham, Quang Do Vinh, Won-Joo HwangarXiv 2022 · DOI · OpenReview

TL;DR

This paper tackles the challenge of balancing communication efficiency and model convergence in federated learning (FL) for IoT networks, especially when using lossy compression. They propose a novel framework that optimizes resource allocation by first determining the optimal number of participating IoT devices and then using a coalition game to efficiently assign sub-channels, ultimately minimizing total transmission time.

What Problem Does This Paper Address?

Federated Learning (FL) allows devices to collaboratively train a shared model without sending their raw data to a central server, which is crucial for privacy and efficiency, especially in massive Internet of Things (IoT) networks. However, a major bottleneck is the communication burden: sending model updates between devices and the server can be slow and resource-intensive. To address this, researchers have explored techniques like model compression (quantization, sparsification). The problem is that aggressive compression, while reducing communication load, can introduce "distortion" – information loss that degrades the model's quality and can even lead to training divergence, hindering convergence. Existing methods often struggle to find a sweet spot between communication efficiency and reliable model convergence. This paper aims to bridge this gap by explicitly modeling the relationship between compression distortion, the number of participating devices, and the FL convergence rate, and then optimizing resource allocation to minimize total training time.

Methods

The authors tackle this complex optimization problem by decomposing it into two main stages:

  1. Optimizing the Number of Participating IoT Devices (KSE): They first analyze the trade-off between the number of participating IoT devices (KSE) and the FL convergence rate. They derive a theoretical lower bound for the total communication time (Rmin) as a function of KSE. An algorithm is proposed to find the optimal KSE by searching for the value that minimizes this lower bound. This step is crucial because a well-chosen KSE can mitigate the negative effects of compression distortion and ensure convergence.
  2. Optimizing Resource Allocation via Coalition Game: Once the optimal KSE is determined, the problem shifts to minimizing the communication time for each round. This involves selecting which KSE devices participate and how wireless resources (sub-channels) are allocated among them. To efficiently solve this, they employ a coalition game framework. In this game, IoT devices form "coalitions" (groups) to negotiate sub-channel assignments. The goal is to find an assignment that minimizes the total transmission time for the selected devices, considering that each sub-channel can only be used by one device at a time. This approach aims to achieve a near-optimal solution without the prohibitive complexity of exhaustive search.

Datasets

Not discussed in the paper. The evaluation is based on simulated scenarios with parameters defined in Table I.

Key Insights and Ideas

  • Compression Distortion is a Key Factor: The paper highlights that lossy compression, while beneficial for communication, directly impacts FL convergence through model distortion. This distortion is modeled as a Gaussian distribution with a standard deviation (σ) that is inversely proportional to the square of the number of participating devices (KSE).
  • KSE is a Critical Control Knob: The number of participating IoT devices (KSE) is not just a parameter but a critical lever to control the trade-off. Increasing KSE can help overcome distortion and improve convergence, but there's a point of diminishing returns. Finding the "sweet spot" for KSE is essential.
  • Coalition Game for Efficient Resource Allocation: Using a coalition game for sub-channel assignment is an innovative approach. It allows devices to collaboratively negotiate resource usage, leading to more efficient bandwidth utilization and reduced transmission times compared to simpler fairness-based methods.
  • Decomposition Simplifies Complexity: Breaking down the non-convex optimization problem into two stages (optimizing KSE first, then resource allocation) makes it more tractable and allows for practical algorithmic solutions.

Key Results

  • Theoretical Convergence Bound: The paper provides a theoretical lower bound (Rmin) on the number of communication rounds required for FL convergence, which depends on KSE and other system parameters.
  • Algorithm 1 (KSE Optimization): This algorithm efficiently finds the optimal KSE by searching for the value that minimizes the derived Rmin.
  • Algorithm 2 (Coalition Game): This algorithm, based on a coalition game, efficiently assigns sub-channels to minimize total transmission time.
  • Performance Gains:
    • Figure 1(a) shows that as KSE increases, the FL process tends to converge more reliably, avoiding divergence caused by distortion.
  • Figure 1(b) demonstrates that with KSE around 37-40, convergence is achieved in approximately 250 rounds, indicating an efficient balance.
  • Figure 2(a) shows that the proposed coalition game method significantly reduces total transmission time compared to a bandwidth fairness approach, especially with fewer sub-channels. For instance, with 10 sub-channels, the proposed method takes ~300 seconds, while bandwidth fairness takes ~1300 seconds.
  • Figure 2(b) illustrates that the proposed method's transmission time scales more favorably with increasing KSE compared to bandwidth fairness, which experiences a rapid increase.

Limitations and Future Work

  • Limitations:
    • The paper relies on theoretical assumptions about local loss functions (L-smooth, µ-strongly convex) and bounded stochastic gradient variance.
  • The evaluation is based on simulations, not real-world deployments.
  • The coalition game algorithm's convergence is stated as O(NCGKSE), which might still be computationally intensive for very large networks.
  • Future Work:
    • The authors suggest developing a reinforcement-learning solution to adapt to stochastic IoT networks, which could offer more dynamic and adaptive resource management.
  • Exploring more advanced compression techniques and their impact on FL.
  • Investigating distributed FL architectures beyond a single-server model.

Summary updated

Abstract

Recently, a considerable amount of works have been made to tackle the communication burden in federated learning (FL) (e.g., model quantization, data sparsification, and model compression). However, the existing methods, that boost the communication efficiency in FL, result in a considerable trade-off between communication efficiency and global convergence rate. We formulate an optimization problem for compression-aided FL, which captures the relationship between the distortion rate, number of participating IoT devices, and convergence rate. Following that, the objective function is to minimize the total transmission time for FL convergence. Because the problem is non-convex, we propose to decompose it into sub-problems. Based on the property of a FL model, we first determine the number of IoT devices participating in the FL process. Then, the communication between IoT devices and the server is optimized by efficiently allocating wireless resources based on a coalition game. Our theoretical analysis shows that, by actively controlling the number of participating IoT devices, we can avoid the training divergence of compression-aided FL while maintaining the communication efficiency.
BibTeX
@misc{nguyen2022resource,
  author = {Xuan-Tung Nguyen and Minh-Duong Nguyen and Quoc-Viet Pham and Quang Do Vinh and Won-Joo Hwang},
  title = {{Resource Allocation for Compression-aided Federated Learning with High Distortion Rate}},
  year = {2022},
  eprint = {2206.06976},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.06976},
}
Figure