TL;DR
This paper introduces FedRTS, a novel federated learning framework that uses Combinatorial Thompson Sampling (CTS) to dynamically prune neural network models. FedRTS significantly improves robustness and efficiency in federated learning by addressing issues like greedy adjustments, unstable topologies, and high communication costs, leading to state-of-the-art performance.
What Problem Does This Paper Address?
Federated Learning (FL) allows collaborative model training across distributed devices without sharing raw data. However, training deep learning models in FL is computationally and communication-intensive, straining resource-constrained edge devices. While neural network pruning can reduce model size and computational demands, traditional pruning methods are often too resource-intensive for FL. Existing federated pruning methods try to address this by dynamically adjusting model sparsity during training. However, these methods suffer from three main issues:
- Greedy Adjustments: They rely on myopic, aggregated information from a small subset of clients, ignoring data from unseen clients and prior knowledge, leading to suboptimal decisions.
- Unstable Topologies: Deterministic adjustments based on potentially unstable aggregated data can result in fluctuating model structures.
- Communication Inefficiency: Transmitting extensive auxiliary data, like full gradients, for topology updates incurs high communication costs.
These challenges hinder the effectiveness of federated pruning, especially in scenarios with heterogeneous data distributions and unreliable client availability.
Methods
The core innovation of FedRTS is its Thompson Sampling-based Adjustment (TSAdj) mechanism, which reframes federated pruning as a Combinatorial Multi-Armed Bandit (CMAB) problem. Instead of making deterministic decisions based on immediate, potentially unstable information, TSAdj uses probabilistic decisions informed by stable and farsighted information.
Key aspects of TSAdj include:
- Probabilistic Decision Making: TSAdj models the importance of each parameter (link) as a Beta distribution. It samples from these distributions to probabilistically select which parameters to prune or reactivate, leading to more stable topology adjustments.
- Farsighted Information: It leverages both aggregated information from participating clients and individual client information (through a fusion mechanism) to make more informed decisions, mitigating the impact of partial client participation.
- Reduced Communication Overhead: Clients upload only the indices of top gradients for inactive weights, rather than the full gradients. This significantly reduces communication costs compared to methods that require sending dense gradients.
- Two-Loop Training: FedRTS employs a standard two-loop training process: an inner loop for weight updates with a fixed topology and an outer loop for topology adjustment using TSAdj.
Datasets
The paper evaluates FedRTS on a variety of datasets across computer vision and natural language processing tasks:
- Computer Vision: CIFAR-10, CINIC-10, TinyImageNet, and SVHN.
- Natural Language Processing: TinyStories (using the GPT-2-32M model).
Key Insights and Ideas
- Thompson Sampling for Robustness: Applying Thompson Sampling to topology adjustment in federated pruning is a novel approach that significantly enhances model robustness and stability by embracing probabilistic decision-making.
- Fusion of Global and Local Information: Combining aggregated client data with individual client insights (via the trade-off ratio γ) is crucial for effective topology adjustment, especially in heterogeneous environments.
- Gradient Index Uploads are Sufficient: Transmitting only the indices of top gradients, rather than the full gradients, is an effective strategy to drastically reduce communication overhead without sacrificing performance.
- CMAB Framework is a Good Fit: Framing federated pruning as a CMAB problem provides a powerful theoretical lens to analyze and address the inherent challenges of dynamic topology adjustment.
Key Results
FedRTS demonstrates state-of-the-art performance across various benchmarks:
- Accuracy Improvement: On CIFAR-10 with ResNet18, FedRTS achieved a 5.1% accuracy improvement over the best baseline methods.
- Communication Cost Reduction: FedRTS significantly reduces communication costs, achieving a 33.3% reduction in some scenarios. For example, on CINIC-10, it achieved 48% of the training FLOPs and communication cost of the best baseline (FedMef).
- Robustness to Heterogeneity and Availability: FedRTS consistently outperforms baselines in highly heterogeneous data settings and under low client availability scenarios, highlighting the stability of its topology adjustments.
- NLP Performance: In NLP tasks (TinyStories), FedRTS achieved better perplexity scores than all baselines, even surpassing full-size FedAVG at low-density levels.
Limitations and Future Work
The authors acknowledge the following limitations:
- Independence Assumption: The theoretical analysis relies on the assumption of independent importance scores (e.g., weight magnitudes). While empirical evidence supports this, real-world weights may exhibit only asymptotic independence, creating a minor gap between theory and practice. Alternative metrics like Fisher information are too computationally expensive for FL.
- Mean-Field Approximation: The validity of the mean-field approximation used in the theoretical analysis weakens for very small models, though this has minimal practical impact as such models can often be trained directly on-device.
- Fairness and Bias: Dynamically adjusting model structure based on global feedback might unintentionally bias the model towards data-rich or majority-class clients in highly heterogeneous settings.
- Security/Privacy: While communication costs are reduced, sharing top gradient indices might still leak sensitive information.
Future work could explore integrating FedRTS with fairness-aware regularization and continual learning techniques to mitigate bias. Investigating the societal implications of deploying FedRTS at scale, especially in applications where model sparsity might affect predictive reliability, is also suggested.
Summary updated