Stochastic Coded Federated Learning with Convergence and Privacy Guarantees

Yuchang Sun, Jiawei Shao, Songze Li, Yuyi Mao, Jun Zhang

Introduction

Federated Learning (FL) enables collaborative model training across decentralized devices without exposing raw data. However, real-world deployments are often hindered by two major obstacles: the straggler effect, where slow devices delay the entire training process, and the privacy-efficiency tradeoff, where methods to mitigate stragglers often compromise data privacy or model accuracy.

Stochastic Coded Federated Learning (SCFL) is a novel framework designed to overcome these hurdles. By integrating "coded" data to compensate for straggler devices and employing a noise-canceling aggregation step, SCFL accelerates convergence while providing formal privacy guarantees through Mutual Information Differential Privacy (MI-DP).

The SCFL Framework

The SCFL approach consists of three primary stages designed to optimize both speed and security:

  1. Coded Data Preparation: Clients generate a "coded" version of their local datasets by applying random linear combinations and adding Gaussian noise. These privacy-preserved coded datasets are uploaded to the central server once before training begins.
  2. Dual-Track SGD: During training, the server remains active. While available clients compute stochastic gradients on their raw local data, the server simultaneously computes gradients on the coded datasets it holds to "fill in" for straggling clients.
  3. Unbiased Aggregation: To counteract the bias introduced by noise in the coded data, the authors developed a "make-up term." This term is added during model aggregation to ensure the global gradient estimate remains unbiased, maintaining the integrity of the training path.

Performance Analysis

The framework was evaluated on MNIST and CIFAR-10 datasets, simulated across 20 edge devices with non-IID data distributions and varying computational speeds.

Test Accuracy vs. Latency on the MNIST dataset, comparing SCFL against various baselines.

As shown in the latency results, SCFL significantly outperforms traditional methods like CFL-FB (Full-Batch Coded FL) and FL-PMA (which simply drops stragglers). By utilizing mini-batches and retaining information from all clients via coded data, SCFL achieves high accuracy much faster than its counterparts.

Privacy-Utility Tradeoff

A key contribution of SCFL is its formalization of the relationship between privacy (noise level), coded data size, and convergence rate. Unlike standard Differential Privacy (DP) methods that treat noise as a pure error source, SCFL's bias correction allows for a more efficient use of the privacy budget.

Test Accuracy vs. Privacy Budget (ε) on the MNIST dataset.

Experimental results demonstrate that SCFL provides a superior privacy-performance tradeoff compared to baselines like DP-CFL. By continuing to leverage client-side resources while using the server as an active participant, SCFL maintains higher accuracy for the same privacy budget.

Conclusion and Future Work

SCFL represents a significant step forward in making Federated Learning practical for heterogeneous networks. While currently optimized for linear regression tasks, the framework demonstrates the power of combining coded computing with stochastic optimization. Future research will focus on extending these techniques to non-linear Deep Neural Networks and reducing the initial communication overhead associated with coded data transmission.

Summary updated

BibTeX
@inproceedings{sun2022stochastic,
  author = {Yuchang Sun and Jiawei Shao and Songze Li and Yuyi Mao and Jun Zhang},
  title = {{Stochastic Coded Federated Learning with Convergence and Privacy Guarantees}},
  booktitle = {ISIT},
  year = {2022},
  doi = {10.1109/isit50566.2022.9834445},
}
Figure