Lottery Aware Sparsity Hunting: Enabling Federated Learning on Resource-Limited Edge

Sara Babakniya, Souvik Kundu, Saurav Prakash, Yue Niu, Salman Avestimehr

TL;DR

Training sparse neural networks in Federated Learning (FL) often leads to a massive drop in accuracy because individual clients can't agree on which weights are important. This paper introduces FLASH, a framework that achieves consensus on "sparsity masks," allowing edge devices to train models with up to 10x less communication and near-baseline accuracy.

What Problem Does This Paper Address?

Federated Learning allows multiple devices (like smartphones or IoT sensors) to collaboratively train a global model without sharing their private data. However, these "edge" devices are often resource-constrained. While sparse learning—training only a small fraction of the model's weights—seems like a perfect fit to save memory and bandwidth, simply applying standard sparse algorithms to FL fails miserably.

The authors identify a fundamental bottleneck: Sparsity Mask Mismatch. In centralized training, a model eventually settles on a specific pattern of important weights (a "winning lottery ticket"). In FL, because clients have different data and limited communication, they never reach a consensus on this pattern. This lack of agreement, especially in deeper layers of the network, causes the global model to struggle or fail to converge entirely.

Naive sparse training in FL shows a significant accuracy gap compared to centralized training.

Methods

The authors propose Federated Lottery Aware Sparsity Hunting (FLASH), a two-stage framework designed to force consensus across the network:

  1. Stage 1: Mask Initialization: The server selects a few clients for a brief "warm-up" period. These clients perform local sparse learning to identify which layers are most sensitive to pruning. The server aggregates these findings to create a global, sensitivity-aware initial mask.
  2. Stage 2: Sensitivity-Aware Training: The framework offers two paths:
  3. SPDST (Sensitivity-driven Pre-defined Sparse Training): The global mask is frozen. Clients only train the weights allowed by the mask. This guarantees perfect consensus.
  4. JMWST (Joint Mask Weight Sparse Training): The mask can evolve, but the server periodically "subsamples" the aggregated updates to maintain a unified global sparsity pattern.

They also introduce hetero-FLASH, which allows clients with different hardware capabilities to participate using different "density budgets" (e.g., a powerful tablet might train 20% of weights while a simple sensor trains only 5%).

Datasets

The researchers evaluated FLASH across several standard computer vision benchmarks and one NLP task:

  • MNIST & FEMNIST: Handwritten digit recognition (standard and federated versions).
  • CIFAR-10 & CIFAR-100: Object recognition in small images.
  • TinyImageNet: A more complex, large-scale image classification task.
  • SST2: Sentiment analysis (used for fine-tuning a BERT-base model).

Experiments were conducted using both IID (Independent and Identically Distributed) and non-IID data partitions to simulate real-world data heterogeneity.

Key Insights and Ideas

  • Consensus is King: The "aha moment" is that weight values matter less than the mask (the architecture of which weights are active). If clients don't agree on the mask, the aggregated global model becomes a noisy mess.
  • Deep Layer Divergence: The lack of consensus is most severe in the deeper layers of a network. These layers have more parameters and lower "pruning sensitivity," giving clients too many ways to be different.
  • The Jaccard Distance Metric: The authors use the Jaccard distance between masks (Sparse Mask Mismatch or SM) to quantify this disagreement. As shown in the heatmap below, centralized training naturally reaches consensus (lower SM), while standard FL does not.
Heatmap showing that centralized training (a) reaches mask consensus over time, while federated learning (b) maintains high disagreement.

Key Results

  • Accuracy Recovery: FLASH significantly closes the gap with unpruned (dense) models. On CIFAR-10, FLASH achieved ~87% accuracy with only 10% of weights, while the previous state-of-the-art (ZeroFL) sat at ~82%.
  • Communication Efficiency: FLASH provides up to 10.26× reduction in communication costs compared to existing sparse FL methods.
  • Robustness to Heterogeneity: In non-IID settings (where clients have very different data), FLASH improved accuracy by up to 10.1% over competing sparse methods at similar density levels.
  • Heterogeneous Support: Hetero-FLASH successfully allowed a mix of devices with different resource budgets to contribute to a single, high-performing global model.

Limitations and Future Work

  • Theoretical Grounding: While the empirical results are strong, the authors note that a formal theoretical understanding of why mask consensus accelerates convergence in FL is still needed.
  • Foundation Models: The current study focuses on ResNet and BERT-base. Testing FLASH on massive "foundation models" (like LLMs) is a logical next step.
  • Hyperparameter Sensitivity: The interval at which masks are updated in the JMWST approach ($r_{int}$) requires careful tuning to balance mask learnability with weight maturity.

Summary updated

Abstract

Edge devices can benefit remarkably from federated learning due to their distributed nature; however, their limited resource and computing power poses limitations in deployment. A possible solution to this problem is to utilize off-the-shelf sparse learning algorithms at the clients to meet their resource budget. However, such naive deployment in the clients causes significant accuracy degradation, especially for highly resource-constrained clients. In particular, our investigations reveal that the lack of consensus in the sparsity masks among the clients may potentially slow down the convergence of the global model and cause a substantial accuracy drop. With these observations, we present \textit{federated lottery aware sparsity hunting} (FLASH), a unified sparse learning framework for training a sparse sub-model that maintains the performance under ultra-low parameter density while yielding proportional communication benefits. Moreover, given that different clients may have different resource budgets, we present \textit{hetero-FLASH} where clients can take different density budgets based on their device resource limitations instead of supporting only one target parameter density. Experimental analysis on diverse models and datasets shows the superiority of FLASH in closing the gap with an unpruned baseline while yielding up to $\mathord{\sim}10.1\%$ improved accuracy with $\mathord{\sim}10.26\times$ fewer communication, compared to existing alternatives, at similar hyperparameter settings. Code is available at \url{https://github.com/SaraBabakN/flash_fl}.
BibTeX
@article{babakniya2023lottery,
  author = {Sara Babakniya and Souvik Kundu and Saurav Prakash and Yue Niu and Salman Avestimehr},
  title = {{Lottery Aware Sparsity Hunting: Enabling Federated Learning on Resource-Limited Edge}},
  journal = {Accepted by TMLR},
  year = {2023},
  url = {https://openreview.net/forum?id=iHyhdpsnyi},
}
Figure