Back

Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data

Felix SattlerSimon WiedemannKlaus-Robert MüllerWojciech Samek

article2019IEEE Transactions on Neural Networks and Learning Systems1,721 citations

Introduces Sparse Ternary Compression, a bidirectional compression framework that significantly reduces federated learning bandwidth requirements while outperforming Federated Averaging on heterogeneous, non-IID client data.

Listen

Federated learning enables multiple edge devices, such as smartphones and smart appliances, to collaboratively train machine learning models without transferring private user data to a centralized server. While this preserves privacy, exchanging full model updates across millions of devices creates massive network communication overhead, often reaching petabytes of data transfers. Furthermore, existing data compression techniques fail in real-world deployments because user data across devices is highly uneven and non-identically distributed, device participation is intermittent, and memory constraints force training on very small batches.

The article evaluates these shortcomings and demonstrates a new framework called Sparse Ternary Compression. The primary objective is to create a robust communication protocol that drastically reduces both upload and download data volumes while maintaining stable model training under realistic edge conditions.

The researchers conducted extensive simulations across four distinct learning tasks, including image classification, speech recognition, and sequential pattern processing. They systematically benchmarked their proposed method against established industry baselines, specifically federated averaging and sign-based gradient quantization. The evaluations tested challenging conditions such as extreme data skew, varying device participation rates from 5% to 100%, and batch sizes as small as a single sample.

The evaluation produced four central findings. First, existing approaches degrade severely under realistic conditions: federated averaging experiences severe slowdowns, and sign-based methods fail to converge entirely when local data is non-identically distributed. Second, the proposed framework maintains high stability, achieving up to 79.5% accuracy in extreme non-identical data scenarios where competing methods failed. Third, the framework achieves dramatic bandwidth savings, cutting communicated data by roughly a factor of 200 compared to uncompressed baselines and requiring far less data than federated averaging. Finally, the framework tolerates tiny batch sizes and low client participation rates without losing convergence stability.

These findings suggest that organizations deploying edge learning systems should shift away from low-frequency, large-payload updates toward high-frequency, highly compressed updates. Adopting this approach substantially reduces network bandwidth costs, lowers energy consumption on battery-powered devices, and mitigates the risk of training failures caused by heterogeneous data. Additionally, the analysis demonstrates that standard optimization enhancements, such as momentum, should generally be avoided in decentralized edge environments because they destabilize training when local batches are small or device participation is low.

Engineering and data science teams should consider adopting sparse ternary compression protocols for bandwidth-constrained, metered, or battery-dependent edge environments. Conversely, standard federated averaging should be reserved for high-latency networks where communication round trips are the primary cost bottleneck. Before full-scale deployment, teams should conduct pilot tests to calibrate specific compression ratios against target accuracy and device latency budgets.

While empirical results across the tested benchmarks provide high confidence in the framework's mathematical stability and efficiency, the evaluation relies on simulated edge distributions rather than live mobile fleet deployments. Practitioners should anticipate that real-world network fluctuations and hardware heterogeneity could introduce additional operational overhead.

Fraunhofer Heinrich Hertz InstituteKorea UniversityMax Planck Institute for InformaticsTechnische Universität Berlincollaborative learningcommunication overheadscompression methodscommunication-efficient federated learningprivacy-preserving collaborative learninggradient compression
arXiv: 1903.02891
  • Paper: SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, Sai Praneeth Karimireddy et al. (2019). This paper addresses client drift in heterogeneous federated learning using control variates, offering an alternative algorithmic optimization strategy to the source's compression-based approach.
  • Paper: Adaptive Federated Optimization, Sashank Reddi et al. (2020). This work extends federated optimization to adaptive server-side optimizers (FedAdam, FedAdagrad), improving convergence behavior across heterogeneous clients.
  • Paper: Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization, Jianyu Wang et al. (2020). This paper investigates objective inconsistency arising from heterogeneous local updates and proposes normalized averaging schemes that build beyond basic federated averaging and compression.
  • Paper: Model-Contrastive Federated Learning, Qinbin Li et al. (2021). This paper introduces model-contrastive learning to correct local model drift caused by non-i.i.d. data, extending solutions for statistical heterogeneity in federated systems.
  • Paper: Advances and Open Problems in Federated Learning, Peter Kairouz et al. (2019). This broad survey comprehensively synthesizes open challenges in communication efficiency, statistical heterogeneity, and system design highlighted by earlier algorithmic works.
Cover for Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data

Abstract

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.

Topics

collaborative learningcommunication overheadscompression methodsdeep learningfederated learninglearning environmentsparetoprivacy preservingapplication servers

Keywords

communication-efficient federated learningprivacy-preserving collaborative learninggradient compressionprobabilistic quantizationstochastic gradient descentcatastrophic forgettingsparsification methodsconvergence guarantees

Table of Contents

  • I Introduction
  • II Challenges of the Federated Learning Environment
  • III Related Work
  • IV Limitations of existing compression methods
  • IV-A Preliminary Experiments
  • IV-B Results
  • V Sparse Ternary Compression
  • V-A Extending to Downstream Compression
  • V-B Weight Update Caching for Partial Client Participation
  • V-C Eliminating Redundancy
  • VI Experiments
  • VI-A Momentum in Federated Optimization
  • VI-B Non-iid-ness of the Data
  • VI-C Robustness to other Parameters of the Learning Environment
  • VI-D Communication-Efficiency
  • VII Lessons Learned
  • VIII Conclusion
  • References
  • A Encoding and Decoding
  • B Data Splitting
  • C Combining Sparsity and Delay
  • D Results: Learning Environments

Knowls

  1. Knowl 1 — Sparse Ternary Compression Operator

    algorithm

    Sparse Ternary Compression (STC) compresses a weight update tensor by selecting top-kk elements by absolute magnitude and quantizing their values to a single positive or negative mean magnitude, producing a ternary representation with elements in {−μ,0,+μ}\{-\mu, 0, +\mu\}.

    Given a flattened parameter update tensor T∈RnT \in \mathbb{R}^n and a sparsity parameter p∈(0,1]p \in (0, 1], the operator STCp(T)\text{STC}_p(T) is computed as follows:

    Input: Flattened tensor T∈RnT \in \mathbb{R}^n, sparsity parameter p∈(0,1]p \in (0, 1]
    Output: Sparse ternary tensor T∗∈{−μ,0,+μ}nT^* \in \{-\mu, 0, +\mu\}^n
    k←max⁡(⌊np⌋,1)k \leftarrow \max(\lfloor n p \rfloor, 1)
    v←topk(∣T∣)v \leftarrow \text{top}_k(|T|)
    mask←(∣T∣≥v)∈{0,1}n\text{mask} \leftarrow (|T| \ge v) \in \{0, 1\}^n
    Tmasked←mask⊙TT^{\text{masked}} \leftarrow \text{mask} \odot T
    μ←1k∑i=1n∣Timasked∣\mu \leftarrow \frac{1}{k} \sum_{i=1}^n |T^{\text{masked}}_i|
    return T∗←μ×sign(Tmasked)T^* \leftarrow \mu \times \text{sign}(T^{\text{masked}})

    Here, topk(∣T∣)\text{top}_k(|T|) denotes the kk-th largest absolute value in TT, and ⊙\odot represents elementwise multiplication. While standard top-kk sparsification with 32-bit floating-point non-zero values has an update entropy of

    Hsparse=−plog⁡2(p)−(1−p)log⁡2(1−p)+32pH_{\text{sparse}} = -p \log_2(p) - (1-p)\log_2(1-p) + 32p

    the ternarized STC update reduces the per-parameter entropy to

    HSTC=−plog⁡2(p)−(1−p)log⁡2(1−p)+pH_{\text{STC}} = -p \log_2(p) - (1-p)\log_2(1-p) + p

    At a sparsity rate of p=0.01p = 0.01, ternarization yields an additional compression factor of HsparseHSTC≈4.414\frac{H_{\text{sparse}}}{H_{\text{STC}}} \approx 4.414 over magnitude sparsification alone without degrading convergence speed or model accuracy.

  2. Knowl 2 — Federated Learning with Bidirectional STC and Residual Accumulation

    algorithm

    To prevent communication bottlenecks in federated learning where clients communicate via an intermediate parameter server, STC is applied bidirectionally to both client-to-server uploads and server-to-client broadcasts. Both clients and the server maintain local error-accumulation residuals to store non-communicated gradient residuals across rounds.

    Input: Initial parameters W∈RdW \in \mathbb{R}^d, number of rounds TT, participating client set size NN, batch size bb, upload sparsity pupp_{\text{up}}, download sparsity pdownp_{\text{down}}
    Output: Trained master model W∈RdW \in \mathbb{R}^d
    Initialize local weights Wi←WW_i \leftarrow W, local residuals Ri←0∈RdR_i \leftarrow 0 \in \mathbb{R}^d for all clients i=1,…,Ni = 1, \dots, N
    Initialize server residual R←0∈RdR \leftarrow 0 \in \mathbb{R}^d
    for t=1,…,Tt = 1, \dots, T do
        Sample participating client subset It⊆{1,…,N}I_t \subseteq \{1, \dots, N\}
        for each client i∈Iti \in I_t in parallel do
            msg←downloadS→Ci()\text{msg} \leftarrow \text{download}_{S \to C_i}()
            ΔW←decode(msg)\Delta W \leftarrow \text{decode}(\text{msg})
            Wi←Wi+ΔWW_i \leftarrow W_i + \Delta W
            ΔWi←Ri+SGD(Wi,Di,b)−Wi\Delta W_i \leftarrow R_i + \text{SGD}(W_i, D_i, b) - W_i
            ΔW~i←STCpup(ΔWi)\tilde{\Delta W}_i \leftarrow \text{STC}_{p_{\text{up}}}(\Delta W_i)
            Ri←ΔWi−ΔW~iR_i \leftarrow \Delta W_i - \tilde{\Delta W}_i
            msgi←encode(ΔW~i)\text{msg}_i \leftarrow \text{encode}(\tilde{\Delta W}_i)
            uploadCi→S(msgi)\text{upload}_{C_i \to S}(\text{msg}_i)
        Server gathers {ΔW~i∣i∈It}\{\tilde{\Delta W}_i \mid i \in I_t\}
        ΔW←R+1∣It∣∑i∈ItΔW~i\Delta W \leftarrow R + \frac{1}{|I_t|} \sum_{i \in I_t} \tilde{\Delta W}_i
        ΔW~←STCpdown(ΔW)\tilde{\Delta W} \leftarrow \text{STC}_{p_{\text{down}}}(\Delta W)
        R←ΔW−ΔW~R \leftarrow \Delta W - \tilde{\Delta W}
        W←W+ΔW~W \leftarrow W + \tilde{\Delta W}
        msg←encode(ΔW~)\text{msg} \leftarrow \text{encode}(\tilde{\Delta W})
        broadcastS→Ci(msg)\text{broadcast}_{S \to C_i}(\text{msg}) to participating clients
    return WW

    When download sparsity pdownp_{\text{down}} and upload sparsity pupp_{\text{up}} are of the same order of magnitude, compressing downstream communication reduces final model accuracy by at most 2%2\% to 3%3\% compared to uncompressed downstream broadcast across both i.i.d. and non-i.i.d. client data.

  3. Knowl 3 — Convergence Rate of Sparse Ternary Compression for Strongly Convex Objectives

    theoretical result

    An operator comp:Rd→Rd\text{comp}: \mathbb{R}^d \to \mathbb{R}^d is a kk-contraction if there exists 0<k≤d0 < k \le d such that for all x∈Rdx \in \mathbb{R}^d,

    E∥x−comp(x)∥22≤(1−kd)∥x∥22\mathbb{E}\|x - \text{comp}(x)\|_2^2 \le \left(1 - \frac{k}{d}\right) \|x\|_2^2

    The sparse ternary compression operator STCk\text{STC}_k is a k~\tilde{k}-contraction with effective contraction parameter

    k~=∥topk(x)∥12k∥x∥22d\tilde{k} = \frac{\|\text{top}_k(x)\|_1^2}{k \|x\|_2^2} d

    where 0<k~≤d0 < \tilde{k} \le d, topk(x)\text{top}_k(x) contains the kk elements of xx with largest absolute values, and dd is the parameter dimensionality.

    For any LL-smooth, μ\mu-strongly convex objective function f:Rd→Rf: \mathbb{R}^d \to \mathbb{R} with bounded gradient variance E∥∇f(W)∥22≤G2\mathbb{E}\|\nabla f(W)\|_2^2 \le G^2, optimizing with STC and error accumulation residuals across TT iterations yields the convergence bound

    E[f(WT)]−f∗≤O(G2μT)+O(d2k~2G2Lμ2T2)+O(d3k~3G2μT3)\mathbb{E}[f(W_T)] - f^* \le \mathcal{O}\left(\frac{G^2}{\mu T}\right) + \mathcal{O}\left(\frac{d^2}{\tilde{k}^2} \frac{G^2 L}{\mu^2 T^2}\right) + \mathcal{O}\left(\frac{d^3}{\tilde{k}^3} \frac{G^2}{\mu T^3}\right)

    Consequently, for total iteration counts T∈Ω(dk~(Lμ)1/2)T \in \Omega\left(\frac{d}{\tilde{k}}\left(\frac{L}{\mu}\right)^{1/2}\right), the optimization error is dominated by the leading term O(G2μT)\mathcal{O}\left(\frac{G^2}{\mu T}\right), matching the asymptotic convergence rate of uncompressed stochastic gradient descent.

  4. Knowl 4 — Optimal Golomb Encoding for Compressed Sparse Ternary Updates

    model/method

    Communicating a sparse ternary tensor produced by STC requires transmitting the non-zero positions, one scale factor μ∈R+\mu \in \mathbb{R}^+, and 1 bit per non-zero coordinate to indicate sign (+μ+\mu or −μ-\mu). Assuming a uniform random sparsity pattern over model dimensionality ∣W∣|W|, the index distance between consecutive non-zero elements follows a geometric distribution with success probability equal to the sparsity rate pp.

    The optimal Golomb code parameter b∗b^* for geometrically distributed distances with parameter pp is

    b∗=1+⌊log⁡2(log⁡(ϕ−1)log⁡(1−p))⌋b^* = 1 + \left\lfloor \log_2\left(\frac{\log(\phi - 1)}{\log(1 - p)}\right) \right\rfloor

    where ϕ=5+12\phi = \frac{\sqrt{5} + 1}{2} is the golden ratio. The resulting average number of bits required to encode each non-zero position is

    bˉpos=b∗+11−(1−p)2b∗\bar{b}_{\text{pos}} = b^* + \frac{1}{1 - (1 - p)^{2^{b^*}}}

    For a sparsity rate of p=0.01p = 0.01, this yields bˉpos≈8.38\bar{b}_{\text{pos}} \approx 8.38 bits per non-zero weight update, achieving a ×1.9\times 1.9 compression factor over standard 16-bit uncompressed integer difference index encoding.

  5. Knowl 5 — Communication Volume to Target Accuracy Across Federated Learning Tasks

    data/table

    The table below compares the total uploaded and downloaded data volumes in megabytes (MB) required to reach fixed target accuracies on three benchmarks in an i.i.d. federated learning environment with 100 clients, 10% client participation per round, and local batch size 20: VGG11* on CIFAR-10 (target accuracy 84%), a 4-layer CNN on Speech Commands Keyword Spotting (KWS, target accuracy 90%), and a 2-layer LSTM on Fashion-MNIST (target accuracy 89%).

    Compression Method VGG11*@CIFAR CNN@KWS LSTM@F-MNIST
    Acc. = 0.84 Acc. = 0.90 Acc. = 0.89
    Baseline (uncompressed) 36696 MB / 36696 MB 5191 MB / 5191 MB 2422 MB / 2422 MB
    signSGD 1579.5 MB / 6937.6 MB 925.17 MB / 4063.6 MB 123.31 MB / 541.6 MB
    FedAvg n=25n = 25 3572.7 MB / 3572.7 MB 301.67 MB / 301.67 MB 174.79 MB / 174.79 MB
    FedAvg n=100n = 100 1606.3 MB / 1606.3 MB 617.3 MB / 617.3 MB 83.94 MB / 83.94 MB
    FedAvg n=400n = 400 n.a. 350.78 MB / 350.78 MB 86.53 MB / 86.53 MB
    STC p=1/25p = 1/25 118.43 MB / 1184.3 MB 43.57 MB / 435.7 MB 8.84 MB / 88.4 MB
    STC p=1/100p = 1/100 202.2 MB / 2022 MB 31.0 MB / 310 MB 12.1 MB / 121 MB
    STC p=1/400p = 1/400 183.9 MB / 1839 MB 14.8 MB / 148 MB 7.9 MB / 79 MB

    A value of "n.a." denotes failure to reach the target accuracy within the allowed iteration budget. On CIFAR-10, STC (p=1/400p=1/400) reduces upload communication to 183.9 MB, achieving a ×199.5\times 199.5 reduction compared to uncompressed SGD (36,696 MB) and an 8.7×8.7\times reduction compared to FedAvg with n=100n=100 (1,606.3 MB), while FedAvg with high communication delay (n=400n=400) fails to converge to the target accuracy.

  6. Knowl 6 — Server-Side Update Caching for Partial Client Participation

    model/method

    When client participation is partial, clients that were inactive for multiple rounds become desynchronized from the current global master model W(T)W^{(T)}. To keep clients synchronized without transmitting the full dense model, the parameter server caches partial sums of consecutive compressed updates:

    P(s)=∑t=1sΔW~(T−t)for s=1,…,τP^{(s)} = \sum_{t=1}^s \tilde{\Delta W}^{(T-t)} \quad \text{for } s = 1, \dots, \tau

    along with the global master model W(T)=W(T−τ−1)+∑t=1τΔW~(T−t)W^{(T)} = W^{(T-\tau-1)} + \sum_{t=1}^\tau \tilde{\Delta W}^{(T-t)}.

    A client reconnecting after skipping s≤τs \le \tau communication rounds downloads the cached sparse accumulated update P(s)P^{(s)} rather than the entire parameter tensor. For general sparse updates, the entropy of the accumulated update scales linearly with the delay period τ\tau:

    H(P(τ))≤τH(P(1))=τH(ΔW~(T−1))H(P^{(\tau)}) \le \tau H(P^{(1)}) = \tau H(\tilde{\Delta W}^{(T-1)})

    If a client skips more than τ\tau rounds such that τH(ΔW~)>H(W)\tau H(\tilde{\Delta W}) > H(W), the client falls back to downloading the full model W(T)W^{(T)}.

  7. Knowl 7 — Gradient Sign Incongruence Failure Mode of signSGD on Non-i.i.d. Data

    theoretical result

    The convergence failure of signSGD on non-i.i.d. client partitions is explained by the behavior of the gradient sign congruence metric αw(k)\alpha_w(k), defined as the probability that the sign of a local minibatch gradient gwk=1k∑i=1k∇wl(xi,W)g_w^k = \frac{1}{k}\sum_{i=1}^k \nabla_w l(x_i, W) at parameter ww matches the sign of the true full-batch gradient gwg_w over the entire training distribution DD:

    αw(k)=P[sign(gwk)=sign(gw)]\alpha_w(k) = \mathbb{P}\left[\text{sign}(g_w^k) = \text{sign}(g_w)\right]

    The network-wide average congruence is given by

    α(k)=1∣W∣∑w∈Wαw(k)\alpha(k) = \frac{1}{|W|} \sum_{w \in W} \alpha_w(k)

    Under an i.i.d. data distribution, α(k)\alpha(k) increases rapidly toward 1 as the batch size kk grows, providing consistent gradient directions. Under non-i.i.d. data distributions (where batches contain samples restricted to single classes), α(k)\alpha(k) remains near random chance (α(k)≈0.51\alpha(k) \approx 0.51) regardless of how large the batch size kk is made. Consequently, compressed updates produced by signSGD remain uncorrelated with the true descent direction on non-i.i.d. data, causing optimization to plateau or diverge.

  8. Knowl 8 — Robustness of STC vs. Federated Averaging under Non-i.i.d. Partitions

    empirical result

    When evaluated on VGG11* trained on CIFAR-10 across varying degrees of class non-i.i.d.-ness (where each client holds data from c∈{1,2,3,5,10}c \in \{1, 2, 3, 5, 10\} out of 10 total classes):

    1. At full client participation (10 out of 10 clients), STC (p=1/400p = 1/400) maintains 79.5%79.5\% validation accuracy in the extreme non-i.i.d. setting (c=1c = 1 class per client), whereas Federated Averaging (n=400n = 400) drops to 10.0%10.0\% accuracy (random guessing) and signSGD completely fails to converge.
    2. At partial client participation (10 out of 100 clients), STC achieves 53.2%53.2\% accuracy under c=1c = 1 and 78.0%78.0\% under c=2c = 2, whereas Federated Averaging fails to exceed 10.0%10.0\% under c=1c = 1 and reaches only 38.5%38.5\% under c=2c = 2.
    3. STC consistently outperforms Federated Averaging across all non-i.i.d. regimes because frequent sparse communication prevents weight divergence between local client models, whereas local multi-step SGD without synchronization causes client models to drift into conflicting parameter trajectories.

  9. Knowl 9 — Robustness of STC to Extreme Small Local Batch Sizes

    empirical result

    On memory-constrained edge devices where SGD must be executed with very small local batch sizes b∈{1,2,5,20,100}b \in \{1, 2, 5, 20, 100\}:

    1. When training VGG11* on CIFAR-10 with 10 clients holding an i.i.d. partition of data for 20,000 iterations, STC (p=1/400p=1/400) maintains 63.8%63.8\% accuracy at batch size b=1b=1, whereas Federated Averaging (n=400n=400) degrades to 39.2%39.2\% accuracy.
    2. Under a non-i.i.d. partition (c=2c=2 classes per client) at b=1b=1, STC achieves 58.1%58.1\% accuracy, while Federated Averaging achieves only 14.2%14.2\%.
    3. Federated Averaging accumulates high stochastic gradient noise over its nn local steps when batch sizes are small, destabilizing local trajectories before averaging. STC communicates after every mini-batch step with residual accumulation, insulating the optimization trajectory against small-batch noise.

  10. Knowl 10 — Detrimental Effects of Momentum in Heterogeneous Federated Learning

    empirical result

    While classical momentum SGD (m=0.9m=0.9) accelerates convergence in centralized or i.i.d. distributed settings with large batches, adding momentum to STC or Federated Averaging degrades performance under three conditions:

    1. Small batch sizes (b<20b < 20), where momentum amplifies stochastic gradient noise across iterations.
    2. Low client participation fractions (e.g., 5 out of 100 or 400 clients), where local client momentum buffers become stale between participation rounds.
    3. Non-i.i.d. client data partitions (c<5c < 5 classes per client), where stale momentum vectors accumulate gradients biased toward local class distributions and pull the global model away from consensus.

    In contrast, signSGD requires momentum to converge at all, but remains strictly inferior to momentum-free STC in non-i.i.d. and low-participation settings.

  11. Knowl 11 — Total Bit Communication Complexity Model for Federated Learning

    equation

    The total volume of bits bup/downb^{\text{up/down}} uploaded and downloaded by each client during federated optimization is governed by the relation

    bup/down∈O(Niter×f×∣W∣×(H(ΔWup/down)+η))b^{\text{up/down}} \in \mathcal{O}\left(N_{\text{iter}} \times f \times |W| \times \left(H(\Delta W^{\text{up/down}}) + \eta\right)\right)

    where:

    • Niter∈N+N_{\text{iter}} \in \mathbb{N}^+ is the total number of local gradient evaluations (forward-backward passes) executed by the client,
    • f∈(0,1]f \in (0, 1] is the communication frequency per local iteration (f=1/nf = 1/n for communication delay methods with nn local iterations),
    • ∣W∣∈N+|W| \in \mathbb{N}^+ is the total number of scalar parameters in the model architecture,
    • H(ΔWup/down)≥0H(\Delta W^{\text{up/down}}) \ge 0 is the entropy in bits of the exchanged upload or download weight updates, and
    • η≥0\eta \ge 0 is the coding inefficiency (the difference between the practical codeword length and the Shannon entropy lower bound).

    Reducing communication overhead requires either lowering communication frequency ff, reducing update entropy H(ΔW)H(\Delta W) through lossy sparsification and quantization, or minimizing coding overhead η\eta via entropy coding.

Coverage note — None was omitted; all primary contributions, algorithm specifications, theoretical contraction/convergence theorems, coding schemes, and empirical benchmark evaluations from the paper are fully covered.

References

  1. 1.R. Taylor, D. Baron, and D. Schmidt, “The world in 2025: 8 Predictions for the next 10 years,” in Proc. 10th Int. Microsyst., Packag., Assembly Circuits Technol. Conf. (IMPACT), 2015, pp. 192–195.
  2. 2.S. Wiedemann, K.-R. Müller, and W. Samek, “Compact and com- putationally efficient representation of deep neural networks,” IEEE Trans. Neural Netw. Learn. Syst., to be published. doi: 10.1109/TNNLS. 2019.2910073.
  3. 3.S. Wiedemann, A. Marban, K.-R. Müller, and W. Samek, “Entropy- constrained training of deep neural networks,” in Proc. IEEE Int. Joint Conf. Neural Netw. (IJCNN), 2019, pp. 1–8.
  4. 4.Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” Nature, vol. 521, pp. 436–444, May 2015.
  5. 5.A. Karpathy and L. Fei-Fei, “Deep visual-semantic alignments for generating image descriptions,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), Jul. 2015, pp. 3128–3137.
  6. 6.S. Bosse, D. Maniry, K.-R. Müller, T. Wiegand, and W. Samek, “Deep neural networks for no-reference and full-reference image quality assessment,” IEEE Trans. Image Process., vol. 27, no. 1, pp. 206–219, Jan. 2018.
  7. 7.A. Karpathy, G. Toderici, S. Shetty, T. Leung, R. Sukthankar, and L. Fei-Fei, “Large-scale video classification with convolutional neural networks,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), Jun. 2014, pp. 1725–1732.
  8. 8.I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” in Proc. Adv. Neural Inf. Process. Syst., 2014, pp. 3104–3112.
  9. 9.W. Samek, T. Wiegand, and K.-R. Müller, “Explainable artificial intelligence: Understanding, visualizing and interpreting deep learning models,” ITU J., ICT Discoveries, vol. 1, no. 1, pp. 39–48, 2018.
  10. 10.H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” 2016, arXiv:1602.05629. [Online]. Available: https://arxiv.org/abs/1602.05629
  11. 11.E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” 2018, arXiv:1807.00459. [Online]. Available: https://arxiv.org/abs/1807.00459
  12. 12.K. Bonawitz et al., “Practical secure aggregation for privacy-preserving machine learning,” in Proc. ACM SIGSAC Conf. Comput. Commun. Secur., 2017, pp. 1175–1191.
  13. 13.S. Hardy et al., “‘Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption,” 2017, arXiv:1711.10677. [Online]. Available: https://arxiv.org/abs/1711.10677
  14. 14.M. Abadi et al., “Deep learning with differential privacy,” in Proc. ACM SIGSAC Conf. Comput. Commun. Secur., 2016, pp. 308–318.
  15. 15.K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), Jun. 2016, pp. 770–778.
  16. 16.G. Huang, Z. Liu, K. Q. Weinberger, and L. van der Maaten, “‘Densely connected convolutional networks,” in Proc. IEEE CVPR, vol. 1, Jun. 2017, no. 2, p. 3.
  17. 17.F. Sattler, S. Wiedemann, K.-R. Müller, and W. Samek, “‘Sparse binary compression: Towards distributed deep learning with minimal communication,” in Proc. IEEE Int. Joint Conf. Neural Netw. (IJCNN), 2019, pp. 1–8.
  18. 18.K. Bonawitz et al., “‘Towards federated learning at scale: System design,” 2019, arXiv:1902.01046. [Online]. Available: https://arxiv. org/abs/1902.01046
  19. 19.W. Wen et al., “‘TernGrad: Ternary gradients to reduce communication in distributed deep learning,” 2017, arXiv:1705.07878. [Online]. Available: https://arxiv.org/abs/1705.07878
  20. 20.D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” in Proc. Adv. Neural Inf. Process. Syst., 2017, pp. 1707–1718.
  21. 21.H. Wang, S. Sievert, Z. Charles, D. Papailiopoulos, S. Liu, and S. Wright, “‘ATOMO: Communication-efficient learning via atomic sparsification,” 2018, arXiv:1806.04090. [Online]. Available: https://arxiv. org/abs/1806.04090
  22. 22.J. Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar, “signSGD: Compressed optimisation for non-convex problems,” 2018, arXiv:1802.04434. [Online]. Available: https://arxiv.org/abs/1802.04434
  23. 23.A. F. Aji and K. Heafield, “‘Sparse communication for distributed gradient descent,” 2017, arXiv:1704.05021. [Online]. Available: https://arxiv. org/abs/1704.05021
  24. 24.N. Strom, “‘Scalable distributed DNN training using commodity GPU cloud computing,” in Proc. 16th Annu. Conf. Int. Speech Commun. Assoc., 2015, pp. 1488–1492.
  25. 25.Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally, “Deep gradient compression: Reducing the communication bandwidth for distributed training,” 2017, arXiv:1712.01887. [Online]. Available: https://arxiv.org/abs/1712.01887
  26. 26.Y. Tsuzuku, H. Imachi, and T. Akiba, “‘Variance-based gradient compression for efficient distributed deep learning,” 2018, arXiv:1802.06058. [Online]. Available: https://arxiv.org/abs/1802.06058
  27. 27.J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “‘Federated learning: Strategies for improving communication efficiency,” 2016, arXiv:1610.05492. [Online]. Available: https://arxiv.org/abs/1610.05492
  28. 28.K. Simonyan and A. Zisserman, “‘Very deep convolutional networks for large-scale image recognition,” 2014, arXiv:1409.1556. [Online]. Available: https://arxiv.org/abs/1409.1556
  29. 29.J. Bernstein, J. Zhao, K. Azizzadenesheli, and A. Anandkumar, “signSGD with majority vote is communication efficient and byzantine fault tolerant,” 2018, arXiv:1810.05291. [Online]. Available: https://arxiv.org/abs/1810.05291
  30. 30.A. Krizhevsky, V. Nair, and G. Hinton. (2014). The CIFAR-10 Dataset. [Online]. Available: http://www.cs.toronto.edu/kriz/cifar.html
  31. 31.Y. LeCun. (1998). The MNIST Database of Handwritten Digits. [Online]. Available: http://yann.lecun.com/exdb/mnist/
  32. 32.Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra, “‘Federated learning with non-IID data,” 2018, arXiv:1806.00582. [Online]. Available: https://arxiv.org/abs/1806.00582
  33. 33.S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “‘Sparsified SGD with memory,” in Proc. Adv. Neural Inf. Process. Syst., 2018, pp. 4447–4458.
  34. 34.S. Golomb, “‘Run-length encodings (corresp.),” IEEE Trans. Inf. Theory, vol. 12, no. 3, pp. 399–401, Jul. 1966.
  35. 35.S. Ioffe, “‘Batch renormalization: Towards reducing minibatch dependence in batch-normalized models,” in Proc. Adv. Neural Inf. Process. Syst., 2017, pp. 1945–1953.
  36. 36.P. Warden, “‘Speech commands: A dataset for limited-vocabulary speech recognition,” 2018, arXiv:1804.03209. [Online]. Available: https://arxiv.org/abs/1804.03209
  37. 37.H. Xiao, K. Rasul, and R. Vollgraf, “‘Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms,” 2017, arXiv:1708.07747. [Online]. Available: https://arxiv.org/abs/1708.07747
  38. 38.I. J. Goodfellow, M. Mirza, D. Xiao, A. Courville, and Y. Bengio, “‘An empirical investigation of catastrophic forgetting in gradient-based neural networks,” 2013, arXiv:1312.6211. [Online]. Available: https://arxiv.org/abs/1312.6211

Citation

MLA
Sattler, F., et al. “Robust and Communication-Efficient Federated Learning from Non-IID Data”. arXiv, 2019, http://arxiv.org/abs/1903.02891v1.
APA
Sattler, F., Wiedemann, S., Müller, K.-R., & Samek, W. (2019). Robust and Communication-Efficient Federated Learning from Non-IID Data. arXiv. http://arxiv.org/abs/1903.02891v1
Chicago
Sattler, F., S. Wiedemann, K.-R. Müller, and W. Samek. 2019. “Robust and Communication-Efficient Federated Learning from Non-IID Data”. arXiv. http://arxiv.org/abs/1903.02891v1.
Harvard
Sattler, F. et al. (2019) “Robust and Communication-Efficient Federated Learning from Non-IID Data”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1903.02891v1.
Vancouver
1. Sattler F, Wiedemann S, Müller K-R, Samek W (2019) Robust and Communication-Efficient Federated Learning from Non-IID Data. arXiv

BibTeX

@article{sattler2019robust,
  title = {Robust and Communication-Efficient Federated Learning from Non-IID Data},
  author = {Sattler, Felix and Wiedemann, Simon and Müller, Klaus-Robert and Samek, Wojciech},
  year = {2019},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1903.02891v1},
  eprint = {1903.02891}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF