PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Learning with Non-IID Data

Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, Vikas Chandra

arXiv:1806.00582v2cs.LGstat.ML

TL;DR

Federated learning can lose accuracy when clients hold non-IID data, especially highly skewed class distributions. This paper links the loss to weight divergence measured by EMD and proposes globally shared data, showing accuracy reductions of up to ~55%.

  • Problem

    Federated learning must address unrealistic IID assumptions because clients’ local data distributions can be non-IID.

  • Method

    The paper relates weight divergence to class-distribution EMD and proposes sharing a small dataset containing examples from each class.

  • Results

    Up to ~55% accuracy reduction occurs for neural networks trained on highly skewed non-IID data.

  • Takeaways & Limitations

    Globally shared data offers a solution for federated learning with non-IID data, with its size and distribution tunable to the application.

  • Takeaways & Limitations

    The strategy’s globally shared dataset size and random distributed fraction must be tuned for the problem and application.

Abstract

from arXiv · show

Federated learning enables resource-constrained edge compute devices, such as mobile phones and IoT devices, to learn a shared model for prediction, while keeping the training data local. This decentralized approach to train models provides privacy, security, regulatory and economic benefits. In this work, we focus on the statistical challenge of federated learning when local data is non-IID. We first show that the accuracy of federated learning reduces significantly, by up to 55% for neural networks trained for highly skewed non-IID data, where each client device trains only on a single class of data. We further show that this accuracy reduction can be explained by the weight divergence, which can be quantified by the earth mover's distance (EMD) between the distribution over classes on each device and the population distribution. As a solution, we propose a strategy to improve training on non-IID data by creating a small subset of data which is globally shared between all the edge devices. Experiments show that accuracy can be increased by 30% for the CIFAR-10 dataset with only 5% globally shared data.

1 Introduction

Federated learning enables local model training on edge devices, but its statistical challenge arises because IID sampling is important for unbiased stochastic gradients while local data is not necessarily IID. The paper attributes accuracy reduction to weight divergence and bounds it using the earth mover’s distance between client and population class distributions.

  • Background: Federated learning extends local inference to local training, with FedAvg demonstrated on CNNs for MNIST and CIFAR-10 and LSTMs for language data.FedAvg was introduced as a federated training algorithm and shown to be robust on these benchmark datasets.
  • Challenges: Federated learning faces communication challenges from transferring large deep-network weights, device dropout, synchronization latency, and resource constraints.Prior work addressed these issues through secure aggregation and communication compression.
  • Challenges: IID sampling is important because it makes stochastic gradients unbiased estimates of the full gradient, creating a statistical challenge when local edge-device data cannot reasonably be assumed IID.The paper distinguishes this statistical challenge from federated learning’s communication challenges.
  • Contributions: The paper attributes accuracy reduction to weight divergence between training processes with identical initialization and bounds that divergence using EMD between client and population class distributions.The bound quantifies how differences in class distributions across devices relate to divergence in learned weights.

2 FedAvg on Non-IID data

FedAvg achieves SGD-level test accuracy on IID data but suffers significant accuracy reductions on non-IID data, with the largest reduction occurring under the most extreme 1-class partitioning. Increasing local epochs from E = 1 to E = 5 does not reduce the loss in these non-IID experiments.

  • IID experiments: FedAvg achieves SGD-level test accuracy for IID data across MNIST, CIFAR-10, and KWS.For CIFAR-10, FedAvg with B = 10 reaches 82.62%, compared with 84.14% for SGD with B = 100.
  • Non-IID experiments: Significant test-accuracy reduction occurs for FedAvg on non-IID data compared with SGD using matched batch sizes.The reduction is summarized in Table 1.
  • Non-IID experiments: The maximum accuracy reduction occurs under the most extreme 1-class non-IID partitioning.In this setting, each client receives data from only a single class.
  • Non-IID experiments: E = 5 local epochs does not reduce the loss compared with E = 1 in the non-IID experiments.The convergence curves mostly overlap for E = 1 and E = 5.

3 Weight Divergence due to Non-IID Data

Weight divergence increases as client data become more non-IID and is driven by the distance between each client’s class distribution and the population distribution, quantified by EMD. Across MNIST, CIFAR-10, and KWS, larger EMD produces greater weight divergence and lower FedAvg test accuracy.

  • Observed weight divergence: Weight divergence increases across all layers from IID to 2-class non-IID to 1-class non-IID data.This links greater divergence to increasingly skewed client data distributions.
  • Source of divergence: The root cause of weight divergence is the distance between each client’s data distribution and the population distribution, evaluated by earth mover’s distance (EMD).With identical initialization, this probability-distance term becomes the root cause of divergence.
  • Source of divergence: When clients start from the same initialization, EMD drives weight divergence, with its impact affected by learning rate η and synchronization interval T.Different initializations can also produce large divergence even when the data is IID.
  • Empirical validation: Across MNIST, CIFAR-10, and KWS, weight divergence in each layer increases with EMD, with stronger effects in the first convolutional and last fully connected layers.The maximum divergence is significantly higher for CIFAR-10 than for MNIST and KWS, partly because of gradient terms and CNN architectures.
  • Empirical validation: 6.53%, 37.03%, and 40.21% are the maximum accuracy reductions for MNIST, CIFAR-10, and KWS, respectively, as EMD increases.For all three datasets, test accuracy decreases with EMD, and the decline becomes larger as data become more non-IID.

4 Proposed Solution

The proposed strategy shares a small, class-uniform global dataset during FedAvg initialization to reduce non-IID effects. On CIFAR-10, it improves test accuracy substantially while allowing the shared-dataset size and client-distributed fraction to be tuned.

  • CIFAR-10 evaluation: ~30% test accuracy improvement is obtained on CIFAR-10 with only 5% globally shared data.This result motivates sharing a small subset globally rather than requiring clients’ full datasets to be shared.
  • Motivation: The strategy targets the sharp test-accuracy decline beyond an EMD threshold by slightly reducing client-to-population distribution divergence.Because client data cannot be controlled, the method distributes a small global subset with a uniform class distribution.
  • Data-sharing strategy: A class-uniform global dataset G is centralized in the cloud, then used with each client’s private data to warm up and train local FedAvg models.A random α portion of G is distributed to each client at initialization, and the cloud aggregates client models.
  • Trade-offs and properties: The shared-dataset size β and distributed fraction α are tunable, and initialization occurs only once, limiting communication concerns without making the separate shared data privacy sensitive.The global dataset is separate from clients’ data, and the trade-offs between test accuracy, β, and α are evaluated on CIFAR-10.
  • CIFAR-10 evaluation: 78.72% test accuracy is achieved as β increases, while β = 10% yields 74.12% versus 44% without data sharing for extreme 1-class non-IID CIFAR-10.The evaluation uses 10 clients with 1-class non-IID data and varies β from 2.5% to 25%.

5 Conclusion

Federated learning is important for privacy-sensitive distributed machine learning, but model-training quality degrades when edge devices observe unique, highly skewed non-IID data. The reported accuracy loss reaches approximately 55% for neural networks, and is explained by weight divergence.

  • 5 Conclusion: Federated learning supports distributed machine learning when data privacy is paramount.The conclusion frames privacy as a central motivation for federated learning.
  • 5 Conclusion: Model-training quality degrades when each edge device observes a unique data distribution.The issue arises from non-IID data across edge devices.
  • 5 Conclusion: ~55% accuracy reduction occurs for neural networks trained on highly skewed non-IID data.The passage reports this as an upper-bound reduction in federated-learning accuracy.
  • 5 Conclusion: Weight divergence explains the accuracy reduction under highly skewed non-IID data.The conclusion identifies weight divergence as the explanation for the observed accuracy loss.

A Appendix · A.1 Test accuracy over communication rounds for a smaller batch size

Figure 8 compares FedAvg and SGD test accuracy across communication rounds under IID and two non-IID settings for MNIST, CIFAR-10, and KWS.

  • A.1 Test accuracy over communication rounds for a smaller batch size: Figure 8 evaluates test accuracy over communication rounds for FedAvg and SGD.The comparison covers IID and non-IID data settings.
  • A.1 Test accuracy over communication rounds for a smaller batch size: The evaluation includes MNIST, CIFAR-10, and KWS datasets.Results are presented separately for each dataset.
  • A.1 Test accuracy over communication rounds for a smaller batch size: The non-IID conditions distinguish 2-class non-IID data from 1-class non-IID data.The figure labels these settings as Non-IID(2) and Non-IID(1), respectively.

A.2 Test accuracy of SGD and FedAvg with IID or non-IID data

The section presents test accuracy results for SGD and FedAvg under IID and non-IID data conditions.

  • The table reports test accuracy for SGD.
  • The table reports test accuracy for FedAvg.
  • The results compare IID and non-IID data settings.

A.3 Proof of Proposition 3.1

The proof of Proposition 3.1 derives a sequence of inequalities from the definition of w(f), the equality between client-aggregate and population class distributions, and a Lipschitz assumption. Later steps invoke additional stated justifications involving inequalities 3 and 4.

  • The proof begins from the definition of w(f).
  • The first inequality uses that the class distribution aggregated across clients equals the population class distribution.
  • The second inequality relies on assuming ∇wEx|y=i[log fi(x, w)] is λx|y=i-Lipschitz.
  • The proof separately states justifications for inequalities 3 and 4, including a condition involving gmax(w(c).
Loading 1806.00582v2…