PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust and Communication-Efficient Federated Learning from Non-IID Data

Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, Wojciech Samek

arXiv:1903.02891v1cs.LGcs.AIcs.DCstat.ML

TL;DR

Federated Learning needs communication-efficient methods that handle two-way communication and realistic non-IID client data, where existing compression methods are limited. This paper proposes Sparse Ternary Compression (STC), which compresses upstream and downstream updates, and finds it more robust and faster-converging than Federated Averaging across challenging settings.

  • Problem

    Existing compression methods provide limited Federated Learning support because they may omit downstream compression or rely on IID client data assumptions.

  • Method

    STC compresses both upstream and downstream communication through sparsification, ternarization, error accumulation, and optimal Golomb encoding.

  • Results

    Across varied datasets, architectures, and Federated Learning conditions, STC is more robust and converges faster than Federated Averaging.

  • Takeaways & Limitations

    STC is a communication protocol suited to Federated Learning environments with non-IID data, small mini-batches, or low client participation.

  • Takeaways & Limitations

    Non-IID local data can invalidate existing convergence guarantees and substantially degrade the practical performance of communication-efficient training methods.

Abstract

from arXiv · show

Federated Learning allows multiple parties to jointly train a deep learning model on their combined data, without any of the participants having to reveal their local data to a centralized server. This form of privacy-preserving collaborative learning however comes at the cost of a significant communication overhead during training. To address this problem, several compression methods have been proposed in the distributed training literature that can reduce the amount of required communication by up to three orders of magnitude. These existing methods however are only of limited utility in the Federated Learning setting, as they either only compress the upstream communication from the clients to the server (leaving the downstream communication uncompressed) or only perform well under idealized conditions such as iid distribution of the client data, which typically can not be found in Federated Learning. In this work, we propose Sparse Ternary Compression (STC), a new compression framework that is specifically designed to meet the requirements of the Federated Learning environment. Our experiments on four different learning tasks demonstrate that STC distinctively outperforms Federated Averaging in common Federated Learning scenarios where clients either a) hold non-iid data, b) use small batch sizes during training, or where c) the number of clients is large and the participation rate in every communication round is low. We furthermore show that even if the clients hold iid data and use medium sized batches for training, STC still behaves pareto-superior to Federated Averaging in the sense that it achieves fixed target accuracies on our benchmarks within both fewer training iterations and a smaller communication budget.

I. INTRODUCTION · II. CHALLENGES OF THE FEDERATED LEARNING ENVIRONMENT

Federated Learning enables privacy-preserving collaborative deep-learning model training without centralizing participants’ data, but communicating full model updates creates severe overhead. Its distinctive constraints—non-IID and unbalanced data, large and partially participating client populations, parameter-server communication, and limited device resources—impose requirements that existing methods do not jointly satisfy.

  • I. INTRODUCTION: Privacy concerns are especially strong for IoT data collected in private environments, where centralized processing risks leakage and misuse.The passage frames data centralization as a high-risk option for end-user privacy.
  • I. INTRODUCTION: Federated Learning lets multiple parties jointly train a deep-learning model on combined data without revealing local data to a centralized server.Clients exchange model updates rather than training data; the protocol synchronizes, locally updates, and averages models.
  • I. INTRODUCTION: Full model updates can reach gigabytes, and every participating client communicates one such update during every training iteration.The resulting overhead accumulates across multiple hundred thousands of training iterations.
  • I. INTRODUCTION: With model size and iterations fixed, communication can be reduced by lowering frequency, update entropy through lossy compression, or encoding inefficiency.The communication expression identifies frequency, update entropy, and encoding inefficiency as the three available levers.
  • II. CHALLENGES OF THE FEDERATED LEARNING ENVIRONMENT: Local datasets are typically unbalanced and non-IID because clients collect data according to their own environments and usage patterns.Both dataset size and distribution can vary heavily across clients.
  • II. CHALLENGES OF THE FEDERATED LEARNING ENVIRONMENT: Federated Learning may involve multiple millions of clients, making direct update communication and aggregation infeasible because workload scales linearly with client count.An intermediate parameter server therefore becomes unavoidable, reducing each client’s communication to one upload and one download per round.
  • II. CHALLENGES OF THE FEDERATED LEARNING ENVIRONMENT: Partial participation and limited battery and memory constrain Federated Learning devices, requiring few gradient evaluations and potentially very small batch sizes.Clients may disconnect, run out of battery, or stop contributing, while SGD memory footprint grows linearly with batch size.
  • II. CHALLENGES OF THE FEDERATED LEARNING ENVIRONMENT: A communication-efficient Federated Learning algorithm must compress both directions, tolerate non-IID, small-batch, and unbalanced data, and handle many clients with partial participation.The paper states that existing methods satisfy neither all three requirements nor the combined robustness and communication demands.

III. RELATED WORK · IV. LIMITATIONS OF EXISTING COMPRESSION METHODS · A. Preliminary Experiments

Existing distributed-learning compression methods reduce communication through delayed communication, sparsification, or quantization, but many leave downstream communication uncompressed and rely on iid data assumptions. Preliminary experiments use a simplified VGG11 on CIFAR-10 with 10 federated clients and compare iid with class-restricted non-iid data splits.

  • III. RELATED WORK: Communication-delay methods reduce communication frequency; Federated Averaging performs multiple local SGD iterations before communicating updates.Communication can be delayed up to 100 iterations without significantly affecting convergence speed on different convolutional and recurrent architectures, provided client data are suitably distributed.
  • III. RELATED WORK: Sparsification methods restrict updates to a small parameter subset; threshold-based gradients can achieve upstream compression rates of up to 3 orders of magnitude.Gradients below the threshold are accumulated in a residual rather than sent to the server.
  • III. RELATED WORK: Dense quantization methods restrict updates to fewer values, including signSGD’s binary gradients and stochastic methods such as TernGrad, QSGD, and ATOMO.signSGD reduces update bit size by ×32 and compresses downloads through majority-vote aggregation.
  • III. RELATED WORK: Only Federated Averaging and signSGD compress both upstream and downstream communication; other listed methods leave server-to-client communication uncompressed.This limits their utility in the Federated Learning setting.
  • IV. LIMITATIONS OF EXISTING COMPRESSION METHODS: Most related work assumes iid client data, an assumption that is generally invalid in Federated Learning, where individual client gradients are biased toward local datasets.Federated Learning can generally only hope for unbiasedness in the mean across clients.
  • IV. LIMITATIONS OF EXISTING COMPRESSION METHODS: Non-iid local data violate the assumptions behind existing convergence guarantees and dramatically affect the practical performance of communication-efficient distributed-training algorithms.The affected guarantees include those formulated for TernGrad, QSGD, and ATOMO-related methods.
  • A. Preliminary Experiments: Preliminary experiments train a simplified 11-layer VGG11 network on CIFAR-10 in a Federated Learning setup with 10 clients and balanced, non-overlapping data splits.The iid split is random and equally sized; non-iid (m) assigns each client samples from exactly m dataset classes.
  • A. Preliminary Experiments: The experimental model removes dropout and batch normalization and halves the original VGG11’s convolutional-filter counts and fully connected-layer sizes.This defines the simplified VGG11* architecture used in the preliminary setup.

B. Results · V. SPARSE TERNARY COMPRESSION

Existing compression methods generally fail to combine robustness to non-IID data with downstream communication compression. STC builds on top-k sparsification by adding downstream compression, client caching, quantization, and lossless coding.

  • B. Results: All compression methods converge comparably quickly on IID data but suffer considerably under non-IID training.This pattern also appears for logistic regression, not only the other evaluated model.
  • B. Results: Federated Averaging suffers considerably from non-IID data, with prior work reporting accuracy drops of up to 55% versus IID environments.The cited explanation is increased weight divergence between clients.
  • B. Results: SignSGD has worse non-IID stability: it completely fails to converge on CIFAR and plateaus at substantially degraded accuracy on logistic regression.The passage attributes this sensitivity to unreliable gradient signs from individual batches.
  • B. Results: At batch size 1, the average gradient-sign congruence is α(1) = 0.51, only slightly above random.For non-IID batches, increasing batch size does not make gradient signs increasingly accurate.
  • B. Results: Top-k sparsification is the most robust existing method under non-IID data, converging reliably for single-class clients on CIFAR and without slowing on MNIST logistic regression.Its stochastic-gradient noise is not amplified by quantization, unlike signSGD.
  • B. Results: Top-k sparsification remains limited for Federated Learning because it directly compresses only upstream communication.The results summary states that no existing method combines downstream compression with proper non-IID performance.
  • V. SPARSE TERNARY COMPRESSION: STC addresses these limitations by adding downstream compression and caching for synchronization during partial client participation.It further improves efficiency through quantization and optimal lossless coding of weight updates.

A. Extending to Downstream Compression · B. Weight Update Caching for Partial Client Participation

The paper extends sparse communication to server-to-client updates and introduces server-side caching for synchronizing clients that participate intermittently. Downstream sparsification remains effective when upload and download sparsity are comparable, while caching makes synchronization downloads scale with skipped rounds.

  • A. Extending to Downstream Compression: When client uploads are sparse, aggregated downstream updates can become dense as participating clients accumulate, especially beyond the inverse sparsity 1/p.The number of non-zero downstream elements grows linearly with participating clients in the worst case.
  • A. Extending to Downstream Compression: The proposed extension applies the same compression mechanism at the server to compress downstream communication, using separate client-side and server-side residual updates.This modifies the update rule while preserving sparse communication in both directions.
  • A. Extending to Downstream Compression: Upload-and-download compression can be represented as upload compression with generalized masks formed by the Hadamard product of client and server masks.The resulting behavior is predicted to resemble top-k sparsification with increased sparsity.
  • A. Extending to Downstream Compression: For VGG11 on CIFAR10 with 5 clients, comparable upload and download sparsity reduced accuracy by at most two percent in both iid and non-iid settings.The experiment ran for 10000 iterations at different upload and download compression rates.
  • B. Weight Update Caching for Partial Client Participation: Partial client participation creates synchronization challenges because clients download compressed updates rather than the full global model.The challenge arises when only a fraction of the client population participates in each communication round.
  • B. Weight Update Caching for Partial Client Participation: The server caches partial sums of recent updates, allowing returning clients to download either a cached partial sum or the current global model according to their delay.This mechanism reduces client workload while restoring synchronization.
  • B. Weight Update Caching for Partial Client Participation: For general sparse updates, synchronization download size grows linearly with skipped rounds, whose average is 1/η, while signSGD grows logarithmically with the delay period.The linear growth is considered tolerable because downlink communication usually has greater bandwidth and lower cost than uplink communication.

C. Eliminating Redundancy

This section removes communication redundancy by combining sparsification with ternarization and lossless encoding. STC represents updates sparsely and ternarily, optimally encodes nonzero positions, and applies the resulting compression upstream and downstream.

  • Combining Sparsity with Binarization: Regular top-k sparsification wastes compression because transmitted nonzero elements remain at full precision; combining sparsity with quantization yields higher compression gains.The method quantizes the remaining nonzero elements rather than transmitting them at full precision.
  • Combining Sparsity with Binarization: STC quantizes the top-k nonzero elements to the mean population magnitude, producing a ternary tensor with values {−µ, 0, µ}.The quantization procedure is formalized in Algorithm 1.
  • Combining Sparsity with Binarization: At p = 0.01, ternarization provides Hsparse/HST C = 4.414 additional compression over regular sparsification.Achieving the same compression with pure sparsification would require increasing the sparsity rate by approximately the same factor.
  • Lossless Encoding: For p = 0.01, Golomb encoding reduces position representation to b̄pos = 8.38 bits, yielding ×1.9 compression over naive 16-bit distance encoding.The encoding exploits approximately geometrically distributed distances between nonzero elements.
  • Lossless Encoding: The complete STC framework compresses updates in both upstream and downstream communication through sparsification, ternarization, and optimal encoding.Updates are encoded before upload and before download.

VI. EXPERIMENTS

The experiments evaluate STC against Federated Averaging and signSGD across four learning tasks and varied Federated Learning environments. The base setup uses 100 clients, 10% participation, batch size 20, and equally sized client datasets spanning 10 classes, while STC compresses uploads and downloads by roughly ×1050.

  • Experimental scope: STC is evaluated against Federated Averaging and signSGD across four learning tasks and a wide variety of Federated Learning environments.The benchmarks cover image classification and speech recognition using differently sized convolutional and recurrent neural networks.
  • Benchmark emphasis: The primary discussion focuses on VGG11* trained on CIFAR, while the described phenomena carry over to the other benchmarks.Supporting experimental results for the remaining tasks are provided in the appendix.
  • Compression methods: At sparsity rate p = 1/400, STC compresses both upload and download updates by roughly ×1050.This is compared with Federated Averaging at an equivalent delay period of n = 400 iterations and signSGD with coordinate-wise step-size δ = 0.0002.
  • Learning environment: The base Federated Learning configuration contains 100 clients, 10% participation, local batch size 20, and equally sized client datasets with samples from 10 classes.These hyperparameters are used by default unless an experiment explicitly specifies otherwise.

A. Momentum in Federated Optimization

Momentum substantially changes convergence behavior across Federated Averaging, STC, and signSGD, but its effect differs by method and learning environment. SignSGD consistently benefits from momentum, whereas STC and Federated Averaging show mixed effects.

  • Experimental setup: After 20000 training iterations, the study compares final accuracy for Federated Averaging, STC, and signSGD across multiple Federated Learning environments.The experiments use Federated Averaging with n = 400 and STC with p = 1/400.
  • Momentum effects: Momentum m = 0.9 significantly influences the convergence behavior of the compared compression methods.Dashed lines denote momentum optimization, while solid lines denote classical SGD.
  • Momentum effects: signSGD always performs distinctly better when momentum is enabled, while the effects on STC and Federated Averaging are less clear.The benefit or harm of momentum depends on parameters of the learning environment.
  • Comparison protocol: The comparison retains whichever momentum setting—on or off—performs better for each method.The worse version of each method is ignored in subsequent comparisons.

B. Non-iid-ness of the Data · C. Robustness to other Parameters of the Learning Environment

STC is more robust than Federated Averaging and signSGD across non-IID data and several constrained Federated Learning environments. Its advantages persist with small batches, low participation, and unbalanced client datasets.

  • B. Non-iid-ness of the Data: STC outperforms Federated Averaging and signSGD across all tested levels of data iid-ness, with the largest advantage when clients hold fewer than five classes.With exactly one class per client, STC without momentum still achieves 79.5% accuracy.
  • C. Robustness to other Parameters of the Learning Environment: STC without momentum consistently dominates Federated Averaging across all tested benchmarks and learning environments.The comparison covers experiments training VGG11* on CIFAR for 20000 iterations under varied Federated Learning conditions.
  • C. Robustness to other Parameters of the Learning Environment: Momentum significantly slows convergence in the local-batch-size experiments.The batch-size analysis examines communication-efficient Federated Learning techniques on VGG11* trained on CIFAR.
  • C. Robustness to other Parameters of the Learning Environment: At batch size 1, STC reaches 63.8% accuracy while Federated Averaging reaches 39.2% after 20000 training iterations.Small batch sizes substantially impair Federated Averaging, whereas STC is described as more robust.
  • C. Robustness to other Parameters of the Learning Environment: With only 5 out of 400 clients participating per round, STC without momentum reaches 68.2% accuracy while Federated Averaging stagnates at 42.3%.For IID client data, STC is less affected by reduced participation than Federated Averaging.
  • C. Robustness to other Parameters of the Learning Environment: The unbalancedness experiments fix α = 0.1, vary γ between 0.9 and 1.0, and use participation of only 5 out of 200 clients.Final accuracy is evaluated after 20000 iterations across these γ values.
  • C. Robustness to other Parameters of the Learning Environment: All methods converge reliably under unbalanced client data, while Federated Averaging’s accuracy slightly decreases as balancedness increases.The authors attribute this behavior partly to rare participation by large clients balancing rounds involving smaller clients.

D. Communication-Efficiency · VII. LESSONS LEARNED · VIII. CONCLUSION

Under an iid, moderate-batch setup favoring Federated Averaging and signSGD, STC substantially reduces communication to target accuracy. The lessons and conclusion emphasize STC’s robustness to non-IID data, small batches, and low participation, with high-frequency low-volume communication suited to constrained federated environments.

  • D. Communication-Efficiency: The communication comparison uses iid clients holding 10 classes and a moderate batch size of 20, a setup designed to favor Federated Averaging and signSGD.Training continues until the target accuracy is reached or the iteration budget is exhausted.
  • D. Communication-Efficiency: STC at p = 0.0025 communicates 183.9 MB on CIFAR, reducing communication 199.5× versus the 36696 MB baseline and requiring less than Federated Averaging with n = 100.The comparison measures upstream and downstream communication needed to reach a target accuracy.
  • D. Communication-Efficiency: Figure 11 summarizes accuracy after 20000 iterations and communication required to reach 84% validation accuracy on CIFAR.The figure compares Federated Averaging and STC across three learning-environment configurations and under iid, moderate-batch conditions.
  • VII. LESSONS LEARNED: STC distinctively outperforms Federated Averaging when clients hold non-iid data across the reported Federated Learning environments.The paper cites multiple experiments supporting this conclusion.
  • VII. LESSONS LEARNED: STC also outperforms Federated Averaging when clients use small mini-batches, including when client data is iid.This is especially relevant when hardware constraints limit local batch sizes.
  • VIII. CONCLUSION: Federated Learning for mobile and IoT applications is challenging because the learning environment’s properties generally cannot be controlled.This motivates methods that remain effective under varied client and communication conditions.
  • VIII. CONCLUSION: Federated Averaging’s convergence speed drastically decreases with non-iid data, small mini-batches, or participation by only a small fraction of clients per round.The observation spans multiple datasets and model architectures.
  • VIII. CONCLUSION: STC uses high-frequent low-volume rather than low-frequent high-volume communication, making it particularly suited to low-latency, low-bandwidth client-server channels.The paper presents this as an alternative paradigm for communication-efficient federated optimization.

APPENDIX A ENCODING AND DECODING · APPENDIX B DATA SPLITTING

Appendix A describes encoding sparse ternary updates by transmitting non-zero positions and one sign bit, using Golomb encoding for efficient position representation. Appendix B specifies a client data split with fixed proportions and equal class counts per client.

  • APPENDIX A ENCODING AND DECODING: Sparse ternary updates transmit the positions of non-zero tensor elements plus one bit indicating each element’s sign.The sign is represented as µ or −µ.
  • APPENDIX A ENCODING AND DECODING: Golomb encoding efficiently represents non-zero update positions because their distances are approximately geometrically distributed for large layers.The encoding scheme is provided in Algorithm 3.
  • APPENDIX A ENCODING AND DECODING: Algorithm 3 produces a binary message for Golomb position encoding.The passage identifies the algorithm output as a binary message named msg.
  • APPENDIX A ENCODING AND DECODING: The encoding procedure includes adding repeated binary symbols to the message.Algorithm 3 contains a step beginning with msg.add(1, ..., 1).
  • APPENDIX B DATA SPLITTING: Algorithm 5 distributes training data among clients according to a specified procedure.The resulting client datasets are denoted D_i.
  • APPENDIX B DATA SPLITTING: Each client holds a fixed proportion of the entire training dataset, with |D_i| = ϕ_i|D|.The proportion may vary by client through ϕ_i.
  • APPENDIX B DATA SPLITTING: Each client contains the specified number of classes, expressed as [Classes per Client], across all listed clients.The condition is stated as |{y : (x, y) ∈ D_i}| = [Classes per Client] for i = 1, ..., [Number of Clients].

APPENDIX C COMBINING SPARSITY AND DELAY

On CIFAR with VGG11* and five fully participating clients, Figure 12 compares STC, Federated Averaging, and combinations of sparsity and communication delay after 10000 iterations. In non-iid training, STC at any fixed sparsity rate achieves higher accuracy than Federated Averaging at a comparable communication-delay rate, while sparsity and delay have similar effects in iid training.

  • IID data: In iid training, sparsity and communication delay have a similar effect on convergence speed.This finding comes from the left side of Figure 12’s comparison.
  • Non-IID data: In non-iid training, STC at any fixed sparsity rate achieves higher accuracy than Federated Averaging at a comparable communication-delay rate.This finding comes from the right side of Figure 12’s comparison.
  • Combined compression and delay: Combining sparsity and communication delay is possible and may benefit latency-constrained communication settings.The passage notes this combination as a potentially beneficial use of both techniques.
  • Experimental setup: Figure 12 evaluates accuracy after 10000 iterations for VGG11* on CIFAR with STC, Federated Averaging, and combined sparsity-delay configurations.The comparison uses iid and non-iid Federated Learning environments with 5 clients and full participation.

APPENDIX D RESULTS: LEARNING ENVIRONMENTS

The appendix evaluates compressed communication methods across four learning tasks and varied learning environments using final accuracy after a fixed number of training iterations. The experiments vary client data class diversity, participation fraction, mini-batch size, and local-dataset size balance.

  • Learning environments: Final accuracy is compared across four learning tasks and learning-environment variations after a fixed number of training iterations.The reported comparisons cover different compressed communication methods, with the CIFAR benchmark trends extending to the other benchmarks.
  • Client data heterogeneity: Client data class diversity is evaluated by relating final accuracy to the number of different classes in client datasets.The setups include 10/10 and 10/100 clients, with two and ten classes and batch size 20.
  • Client participation: Client participation is evaluated by relating final accuracy to the client participation fraction.The figure includes VGG11* on CIFAR with 10/100 clients and either two or ten classes.
  • Batch size: Training batch size is evaluated by relating final accuracy to the size of the mini-batches used during training.The setups use two or ten classes with 10/100 clients.
  • Dataset size balance: Local-dataset balance is evaluated by relating final accuracy to the balancedness in size of clients’ local datasets.This comparison is made for different compression methods across the four learning tasks and two learning-environment setups.
Loading 1903.02891v1…