Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing

Shenglong Zhou, Kaidi Xu, Geoffrey Ye Li

TL;DR

The paper introduces CEPS, a novel algorithm for Sparse Decentralized Federated Learning (SDFL) that drastically reduces communication overhead by using one-bit compressive sensing. By combining model sparsity, periodic communication, and differential privacy, CEPS achieves high training accuracy with 90% less data transmission than traditional decentralized methods while maintaining rigorous privacy guarantees.

What Problem Does This Paper Address?

Federated Learning (FL) typically relies on a central server to aggregate model updates. Decentralized Federated Learning (DFL) removes this single point of failure by allowing nodes (like mobile devices or hospitals) to communicate directly with their neighbors. However, DFL faces three major hurdles:

  1. Communication Bottlenecks: Constantly exchanging high-dimensional model parameters across a network is slow and expensive.
  2. Privacy Risks: Even without sharing raw data, exchanging model gradients can leak sensitive information.
  3. Stragglers: In a real-world network, some nodes are slower or have poorer connections than others, which can stall the entire training process.

This paper seeks to solve all three simultaneously by enforcing model sparsity and using extremely compressed communication.

Methods

The authors propose the CEPS (Communication-Efficient and Private method for SDFL) algorithm. Its core components include:

  • Sparse DFL (SDFL): The optimization problem is formulated with an $L_0$-norm constraint, forcing the learned model to be sparse. This isn't just for efficiency; sparsity is a prerequisite for the compression technique used.
  • One-Bit Compressive Sensing (1BCS): This is the "secret sauce." Instead of sending 64-bit floating-point numbers for every model parameter, nodes send only the sign (1 bit) of the values. The receiving node then uses a reconstruction algorithm (GPSP) to recover the sparse vector.
  • Inexact ADM Framework: The algorithm uses an Inexact Alternating Direction Method to solve the underlying optimization problem, allowing for closed-form solutions that are computationally "cheap" for the local devices.
  • Differential Privacy (DP): To prevent data leakage, the algorithm integrates the Gaussian mechanism, adding calibrated noise to gradients before they are processed for sharing.
  • Partial Participation & Asynchrony: Nodes only communicate with a subset of neighbors and do so at specific intervals ($\kappa_i$), allowing the system to ignore "stragglers" without stopping the clock.

Datasets

The researchers evaluated CEPS using both synthetic and real-world benchmarks:

  • Synthetic Linear Regression: A controlled environment where the "ground truth" model is known to be sparse.
  • 'qot' (Qsar oral toxicity): A dataset from the UCI repository used for logistic regression tasks ($n=8,992$ features).
  • 'rls' (real-sim): A large-scale dataset from Libsvm ($n=72,309$ features) used to test the algorithm's scalability.

Key Insights and Ideas

  • Consensus via Signs: The most surprising insight is that decentralized nodes can reach a high-accuracy consensus even when they only know the direction (the sign) of their neighbors' updates, provided the underlying model is sparse.
  • Sparsity as an Enabler: Usually, sparsity is seen as a way to save memory. Here, it is the mathematical enabler that allows 1-bit signals to be reconstructed into meaningful vectors.
  • Communication vs. Computation Trade-off: While 1BCS decoding requires more local CPU power than simple addition, the authors argue this is a winning trade-off because communication (bandwidth) is typically the primary bottleneck in distributed systems.
  • Robustness to Noise: The integration of Differential Privacy shows that while small $\epsilon$ values (high privacy) cause fluctuations in the objective function, the decentralized nature of the network eventually "smooths out" this noise to reach convergence.

Key Results

  • 90% Reduction in Data: CEPS-1BCS achieved a substantial reduction in data transmission volume (DTV) compared to standard D-PSGD, saving at least 90% of communication overhead.
  • Faster Convergence: In terms of communication rounds, CEPS consistently required fewer rounds to reach the target accuracy than competing methods like DFedAvgM or DFedSAM.
  • Scalability: As the number of nodes ($m$) increased from 32 to 128, the performance gap between CEPS and traditional methods widened, proving its effectiveness for larger networks.
  • Privacy Preservation: The authors provided rigorous theoretical proofs for $(\epsilon, \delta)$-differential privacy, ensuring that the efficiency gains don't come at the cost of security.

Limitations and Future Work

  • Sparsity Requirement: The algorithm's efficiency relies heavily on the model being sparse. If the underlying task requires a dense model (like some deep neural networks), the 1BCS reconstruction might fail or lose accuracy.
  • Local Decoding Overhead: Although the authors mention the decoding complexity is manageable, it still adds a computational burden to the edge devices which might be an issue for extremely low-power hardware.
  • Extension to Non-Convex Models: The current work focuses on linear and logistic regression (convex/strongly convex problems). Future work could explore how these 1-bit techniques translate to complex non-convex architectures like Transformers or CNNs.

Summary updated

BibTeX
@inproceedings{zhou2024communication,
  author = {Shenglong Zhou and Kaidi Xu and Geoffrey Ye Li},
  title = {{Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing}},
  booktitle = {VTC Spring},
  year = {2024},
  doi = {10.1109/vtc2024-spring62846.2024.10683577},
}
Figure