β-Stochastic Sign SGD: A Byzantine Resilient and Differentially Private Gradient Compressor for Federated Learning

Ming Xiang, Lili SuarXiv 2022 · arXiv · OpenReview

Abstract

Federated Learning (FL) is a nascent decentralized learning framework under which a massive collection of heterogeneous clients collaboratively train a model without revealing their local data. Scarce communication, privacy leakage, and Byzantine attacks are the key bottlenecks of system scalability. In this paper, we focus on communication-efficient distributed (stochastic) gradient descent for non-convex optimization, a driving force of FL. We propose two algorithms, named Adaptive Stochastic Sign SGD (Ada-StoSign) and β-Stochastic Sign SGD (β-StoSign), each of which compresses the local gradients into bit vectors. To handle unbounded gradients, Ada-StoSign uses a novel norm tracking function that adaptively adjusts a coarse estimation on the $\ell_{\infty}$ of the local gradients - a key parameter used in gradient compression. We show that Ada-StoSign converges in expectation with a rate $O(\log T/\sqrt{T} + 1/\sqrt{M})$, where $M$ is the number of clients. Under bounded gradient assumption, β-StoSign achieves quantifiable Byzantine resilience and privacy assurances, and works with partial client participation and mini-batch gradients which could be unbounded. We corroborate and complement our theories by experiments on MNIST and CIFAR-10 datasets.

Introduction

Federated Learning (FL) allows a central server to train a model using data stored on thousands of private devices (clients) without ever seeing the raw data. However, FL faces three major bottlenecks: communication overhead, data heterogeneity (non-IID), and security/privacy risks. While SignSGD is a popular 1-bit compressor that reduces communication costs by 32x, it often fails to converge when data is highly varied across clients and lacks a clear mathematical convergence rate for non-convex, non-IID scenarios.

Proposed Methodology

This research introduces two distinct algorithms to address these gaps:

Ada-StoSign (Adaptive Stochastic Sign SGD)

Designed for efficiency on heterogeneous data, Ada-StoSign utilizes a Norm Tracking Function. Since sign-based methods discard magnitude information, Ada-StoSign employs a "leveling rule" between the server and clients to estimate the maximum size ($\ell_\infty$ norm) of the gradients. This allows the algorithm to adaptively scale updates, ensuring convergence even when gradients are unbounded.

β-StoSign

This variant is built for adversarial environments. It incorporates a privacy budget (β) and a clipping function. By injecting controlled randomness into the 1-bit compression process, it achieves Differential Privacy and Byzantine Resilience, allowing the system to ignore "poisoned" updates from malicious actors.

Empirical Evaluation

The algorithms were validated using MNIST (Multi-Layer Perceptron) and CIFAR-10 (Convolutional Neural Networks) datasets. Data was partitioned in a non-IID fashion to simulate real-world heterogeneity.

Learning performance comparison and norm tracking visualization for Ada-StoSign across different seeds and batch settings.

As shown in Figure 1, Ada-StoSign (Adaptive B) achieves training performance (loss and accuracy) comparable to FedSGD, which sends full-precision updates. The norm tracking function successfully follows the gradient magnitude, outperforming static scaling factors (constant B).

Key Insights and Results

  • Convergence Speed: Ada-StoSign achieves a convergence rate of $O(\log T / \sqrt{T} + 1/\sqrt{M})$. As the number of clients ($M$) grows, the algorithm speeds up, outperforming previous state-of-the-art sign-based methods.
  • Byzantine Defiance: In experiments with 20 mobile Byzantine clients, β-StoSign outperformed standard defense algorithms like Krum and Geo-Median in maintaining model accuracy.
  • Privacy-Utility Trade-off: The β parameter acts as a dial; increasing it provides stronger privacy and protection against attacks, though it introduces noise that slightly slows learning.

Conclusion

Ada-StoSign and β-StoSign provide a robust framework for communication-efficient FL. By combining 1-bit compression with adaptive norm tracking and stochastic noise, these methods maintain high accuracy while providing mathematical guarantees for privacy and security. Future work includes formalizing the mini-batch theory for Ada-StoSign and further optimizing the communication overhead of norm tracking.

Summary updated

Abstract

Federated Learning (FL) is a nascent decentralized learning framework under which a massive collection of heterogeneous clients collaboratively train a model without revealing their local data. Scarce communication, privacy leakage, and Byzantine attacks are the key bottlenecks of system scalability. In this paper, we focus on communication-efficient distributed (stochastic) gradient descent for non-convex optimization, a driving force of FL. We propose two algorithms, named {\em Adaptive Stochastic Sign SGD (Ada-StoSign)} and {\em $\beta$-Stochastic Sign SGD ($\beta$-StoSign)}, each of which compresses the local gradients into bit vectors. To handle unbounded gradients, Ada-StoSign uses a novel norm tracking function that adaptively adjusts a coarse estimation on the $\ell_{\infty}$ of the local gradients - a key parameter used in gradient compression. We show that Ada-StoSign converges in expectation with a rate $O(\log T/\sqrt{T} + 1/\sqrt{M})$, where $M$ is the number of clients. To the best of our knowledge, when $M$ is sufficiently large, Ada-StoSign outperforms the state-of-the-art sign-based method whose convergence rate is $O(T^{-1/4})$. Under bounded gradient assumption, $\beta$-StoSign achieves quantifiable Byzantine resilience and privacy assurances, and works with partial client participation and mini-batch gradients which could be unbounded. We corroborate and complement our theories by experiments on MNIST and CIFAR-10 datasets.
BibTeX
@misc{xiang2022stochastic,
  author = {Ming Xiang and Lili Su},
  title = {{β-Stochastic Sign SGD: A Byzantine Resilient and Differentially Private Gradient Compressor for Federated Learning}},
  year = {2022},
  eprint = {2210.00665},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.00665},
}
Figure