PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Learning with Compression: Unified Analysis and Sharp Guarantees

Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, Mehrdad Mahdavi

arXiv:2007.01154v2cs.LGcs.DCstat.ML

TL;DR

Federated learning must reduce communication rounds and message sizes, but the interaction between periodic averaging and compression is not well characterized, especially with heterogeneous data. The paper analyzes compressed local-SGD variants, using local gradient tracking for heterogeneity, and reports improved convergence guarantees and fewer communication rounds than state-of-the-art compressed federated methods in both settings. These claims are supported by theoretical and numerical evaluations on real federated datasets.

  • Problem

    Communication is a bottleneck, and the relationship between compression and periodic averaging remains insufficiently understood, particularly for heterogeneous data distributions.

  • Method

    The paper analyzes periodic local-SGD variants with compressed communication for homogeneous and heterogeneous settings, adding local gradient tracking for heterogeneous data.

  • Results

    The proposed methods theoretically and numerically require fewer communication rounds than state-of-the-art federated algorithms using compression in both homogeneous and heterogeneous settings.

  • Takeaways & Limitations

    Compressed periodic averaging can retain attainable guarantees across homogeneous and heterogeneous federated settings when paired with the proposed algorithmic variants.

  • Takeaways & Limitations

    FedCOM’s performance is not satisfactory in heterogeneous settings because its updates depend heavily on local SGD directions, motivating gradient tracking.

Abstract

from arXiv · show

In federated learning, communication cost is often a critical bottleneck to scale up distributed optimization algorithms to collaboratively learn a model from millions of devices with potentially unreliable or limited communication and heterogeneous data distributions. Two notable trends to deal with the communication overhead of federated algorithms are gradient compression and local computation with periodic communication. Despite many attempts, characterizing the relationship between these two approaches has proven elusive. We address this by proposing a set of algorithms with periodical compressed (quantized or sparsified) communication and analyze their convergence properties in both homogeneous and heterogeneous local data distribution settings. For the homogeneous setting, our analysis improves existing bounds by providing tighter convergence rates for both strongly convex and non-convex objective functions. To mitigate data heterogeneity, we introduce a local gradient tracking scheme and obtain sharp convergence rates that match the best-known communication complexities without compression for convex, strongly convex, and nonconvex settings. We complement our theoretical results and demonstrate the effectiveness of our proposed methods by several experiments on real-world datasets.

1 Introduction

Federated learning faces communication bottlenecks from both synchronization frequency and message size, while the interaction between periodic averaging and compression remains insufficiently understood, especially under heterogeneous data. The paper analyzes compressed local-SGD variants for homogeneous and heterogeneous settings, reporting improved convergence guarantees and empirical efficacy.

  • Motivation: Communication costs arise from both the number of communication rounds and the amount of data exchanged per round.Periodic averaging reduces rounds by trading communication for local computation, while compression reduces message size.
  • Research gap: The interaction between compression and periodic averaging remains poorly understood, particularly for heterogeneous federated data.Most existing analyses focus on homogeneous data distributions.
  • Approach: The paper introduces and analyzes compressed local-SGD variants for both homogeneous and heterogeneous data distributions.The methods use quantized or sparsified communication, with local gradient tracking for heterogeneous settings.
  • Results: For heterogeneous settings, local gradient tracking yields convergence rates that improve state-of-the-art compressed methods, while experiments on real federated datasets demonstrate practical efficacy.The heterogeneous comparison is summarized in Table 2.
  • Results: In homogeneous settings, the quantized federated-averaging analysis improves known bounds for general non-convex and strongly convex objectives and provides novel rates for general convex objectives.The comparison is summarized in Table 1 using communication complexity parameters including m, q, κ, ϵ, R, and τ.

2 Problem Setup

The paper studies federated learning in a server-mediated architecture where users collaboratively optimize a global model without sharing data points. Local objectives are expected losses under user-specific data distributions, allowing both homogeneous and heterogeneous settings.

  • Federated architecture: Users collaboratively learn a global model without exchanging their data points, communicating only through a central server.The architecture contains m users connected to a central unit.
  • Local objectives: Each user’s local objective is the expected loss over its own data distribution and loss function.The distribution P_j generates local data, while the loss measures model performance on those samples.
  • Data settings: The analysis considers homogeneous users with identical distributions and loss functions as well as heterogeneous users whose distributions or losses may differ.User data distributions are not required to be identical.

3 Federated Averaging with Compression2

FedCOM combines periodic local SGD with compressed uplink communication and a server update that mixes the previous global model with averaged local updates. Its global learning-rate parameter distinguishes it from standard local-SGD averaging and supports improved complexity bounds.

  • Algorithm: FedCOM performs τ local stochastic-gradient updates between communication rounds and compresses the resulting user updates before aggregation.The server broadcasts the global model, users compute local updates, and compressed signals are returned to the server.
  • Server update: The server updates the global model using a convex combination of the previous model and the average of updated local models.The extra global learning-rate parameter γ controls this combination.
  • Compressed signal: Each compressed signal represents a normalized difference between a user’s initial and final local models, equivalent to aggregated local SGD directions.This makes the communication interpretable as transmitting a compressed local-gradient direction.
  • Relations to prior methods: Setting γ = 1 reduces FedCOM to FedPAQ, while removing compression recovers FedAvg.FedCOM therefore generalizes both methods through its global update and compression choices.
  • Guarantees: With suitable γ, FedCOM improves FedPAQ complexity bounds for strongly convex and non-convex settings.Ignoring quantization, the update can be interpreted as a global SGD step with stepsize ηγ.

4 Compressed Local SGD with Local Gradient Tracking

FedCOMGATE extends compressed local SGD with local gradient tracking for heterogeneous data, using tracked gradient-direction corrections alongside compressed communication. The section contrasts its design with FedCOM, SCAFFOLD, and related methods.

  • FedCOM limitation: FedCOM can perform arbitrarily poorly under heterogeneous data because local gradient directions may differ substantially from the global gradient direction.Its local-gradient updates work well when user distributions are identical but are unreliable when distributions differ.
  • FedCOMGATE design: FedCOMGATE adds local gradient tracking so each node uses an estimate of the global gradient direction for local updates.The tracking sequence is designed to follow the difference between local and global gradient directions.
  • FedCOMGATE design: FedCOMGATE corrects local updates using tracked directions, fresh stochastic gradients, and accumulated quantized gradient information across local steps.The tracked correction remains fixed during a round’s local updates while stochastic gradients are recomputed from fresh samples.
  • Complexity comparisons: The method is evaluated through separate homogeneous and heterogeneous complexity comparisons, including tables that track communication rounds, local updates, and quantization noise.The tables distinguish finite-sum assumptions, device count, and quantization noise in the two distribution settings.
  • Method comparisons: FedGATE removes compression from the same gradient-tracking framework and avoids the server control variate used by SCAFFOLD.FedCOMGATE and FedGATE implicitly control server-model variance through local-model variances.

5 Convergence Analysis

The convergence analysis studies compressed local SGD under smoothness, lower boundedness, unbiased compression, and bounded stochastic-gradient variance. FedCOM obtains improved homogeneous-setting bounds, while FedCOMGATE attains heterogeneous rates comparable to uncompressed methods, with communication trade-offs relative to SCAFFOLD.

  • Assumptions: The analysis assumes smooth, lower-bounded objectives, unbiased compression with variance proportional to q times the squared input norm, and bounded stochastic-gradient variance.These assumptions support the homogeneous and heterogeneous convergence results, with a separate compression condition required for heterogeneity.
  • FedCOM: FedCOM’s homogeneous analysis characterizes local updates and communication rounds for nonconvex, convex, and strongly convex or PL objectives.Theorem 5.1 uses stepsizes depending on L, q, m, τ, and γ.
  • FedCOM: Compression noise in FedCOM’s homogeneous bounds is scaled down by 1/m, and higher local-step counts can compensate for quantization noise.The comparison with q = 0 also reports fewer communication rounds than best-known rates by a factor of 1/m.
  • FedCOM: FedCOM improves prior compressed-method complexity bounds in homogeneous settings and improves the best-known bounds for general nonconvex and strongly convex objectives.The paper also reports novel rates for convex objectives.
  • FedCOMGATE: FedCOMGATE extends the analysis to heterogeneous distributions under local-gradient unbiasedness, bounded variance, and an additional compression condition.Theorem 5.2 covers strongly convex or PL and convex cases, while the text states analogous implications for all three settings.
  • FedCOMGATE: FedCOMGATE’s dependence on ϵ matches centralized update complexity, while its compression variance q does not receive the homogeneous 1/m reduction.Without compression, FedGATE matches best-known heterogeneous complexity bounds up to a log factor.
  • Communication trade-offs: Compared with SCAFFOLD, the method halves uplink communication by omitting control-variate transmission but doubles downlink communication because of gradient tracking.The paper notes that broadcasting is generally cheaper than uplink communication.

6 Experiments

Experiments on MNIST, CIFAR10, Fashion MNIST, and EMNIST compare compressed and uncompressed methods under simulated federated communication. FedCOMGATE is especially effective for heterogeneous data and large models, while EMNIST’s lower heterogeneity yields similar final convergence across methods.

  • Experimental setup: Experiments simulate federated learning with 100 devices, 100 communication rounds, and global loss and test accuracy measurements across four image datasets.MNIST and Fashion MNIST use two-hidden-layer MLPs, while other configurations include two-layer MLP models.
  • Data heterogeneity: FedCOM performs best in homogeneous settings but suffers residual error under heterogeneous data, motivating gradient tracking in FedCOMGATE.The heterogeneous MNIST configuration assigns each device data from only two classes.
  • MNIST and CIFAR10: FedCOMGATE and FedGATE outperform FedAvg, FedPAQ, and SCAFFOLD in communication size and convergence rate on MNIST and CIFAR10 comparisons.The reported comparison measures training loss, test accuracy, and communicated uplink bits.
  • MNIST and CIFAR10: FedCOMGATE especially outperforms other algorithms when the model size is relatively large.This result is reported for convergence evaluated against the number of communicated bits.
  • EMNIST: FedCOMGATE and FedPAQ achieve the fastest convergence in communication size and wall-clock time on EMNIST with 1000 authors’ data.All algorithms reach the same final convergence rate because EMNIST is close to homogeneous.
  • EMNIST: Client-gradient correlations are homogeneous on EMNIST but highly heterogeneous on two-class-per-client MNIST, explaining their different experimental behavior.EMNIST clients correlate broadly, whereas MNIST clients correlate strongly with at most four other clients.

7 Conclusion

The paper introduces federated algorithms that combine periodic averaging with compressed communication for both homogeneous and heterogeneous data. It reports theoretically and numerically fewer communication rounds than compressed state-of-the-art federated methods.

  • 7 Conclusion: The paper studies periodic averaging with compressed signals in homogeneous and heterogeneous federated-learning settings.The conclusion distinguishes identical versus differing user distributions and loss functions.
  • 7 Conclusion: The methods require fewer communication rounds than compressed state-of-the-art federated algorithms in both theory and experiments.This conclusion applies to both homogeneous and heterogeneous settings.
  • 7 Conclusion: FedGATE uses local gradient tracking without a server control variate, reducing communicated state relative to SCAFFOLD while retaining its convergence rate.The paper describes the resulting communication speedup as 2× and says overall complexity is close to FedAvg and half of SCAFFOLD.
  • 7 Conclusion: Client sampling is incorporated into FedCOMGATE to reduce per-round communication when only a subset of devices participates.The algorithm uses a participation ratio k and exchanges information with selected clients.

B.2 Additional Experiments

The additional experiments examine client sampling, sparsification with memory, and quantization noise alongside supplementary theoretical lemmas. They show robustness to sampling and near-uncompressed performance at some compression rates, while stronger quantization noise worsens convergence.

  • Client sampling: Lower client participation generally degrades performance at the same communication-round budget, but FedGATE and FedCOMGATE remain comparatively robust.The effect is shown across MNIST and CIFAR10 experiments.
  • Sparsification with memory: FedCOMGATE with sparsification and memory can achieve results almost similar to the uncompressed FedGATE at some compression rates.Memory tracks information lost by sparsification and compensates for compression error.
  • Sparsification with memory: Compression rate Cr = 0.1 produces a visible residual error while reducing communication size and speeding training.The residual error is reported for the sparsified MNIST and Fashion MNIST experiments.
  • Quantization and local computation: Increasing quantization noise degrades the convergence rate, whereas the experiments investigate local computation as a countervailing factor.Figure 9 varies quantization noise and the number of local computations τ on MNIST.
  • Supplementary theory: The supplementary section also provides convergence lemmas for gradient inner products, local-solution distances, and the FedCOM homogeneous analysis.These include Lemmas D.1–D.3 and Lemma D.2 under the stated assumptions.

D.1 Main result for the non-convex setting

This section develops the homogeneous-setting non-convex analysis for FedCOM under stated assumptions and learning-rate conditions. It derives a convergence bound, identifies a linear-speedup regime, and verifies tightness through a special case matching prior work.

  • Main theorem: Theorem D.4 states the non-convex convergence result for FedCOM(τ, η, γ) under Assumptions 1–3 and a learning-rate condition.The theorem covers all local-update times through Rτ − 1.
  • Main theorem: The analysis bounds the average-squared gradient after τ local iterations when local models start from the same point.The global optimum is denoted w(∗) with objective value f(w(∗)).
  • Linear speedup: Choosing ηγ = O(·) yields a linear-speedup regime in the derived convergence bound.The paper explicitly identifies this parameter choice as necessary for linear speedup.
  • Special case: For γ = 1 and q = 0, the convergence rate reduces to the rate obtained in [53], indicating tightness of the analysis.The same special case also gives corresponding communication-complexity and local-update expressions.

D.2 Main result for the PL/strongly convex setting

The homogeneous PL/strongly convex analysis establishes convergence guarantees for FedCOM and derives communication-round conditions for achieving a target error. The results also identify linear-speedup conditions and a tight communication-complexity comparison.

  • Strongly convex setting: The analysis extends the convergence rate to strongly convex functions.The passage states that the resulting rate is the same for strongly convex functions.
  • Theorem D.7: Theorem D.7 gives a PL or strongly convex convergence guarantee for FedCOM under specified assumptions and learning-rate conditions.The theorem applies over communication rounds indexed by t and requires initialization at a common model.
  • Communication complexity: Achieving error ϵ requires a communication-round budget R characterized by the theorem’s rate.The supplied statement explicitly connects the target error ϵ to the required number of rounds R.
  • Rate improvement: FedCOM improves prior convergence bounds with tuned global and local learning rates when γ ≥ m.The improvement is stated relative to [22] and [40].
  • Complexity comparison: The resulting rate matches the communication and computational complexity of [22] and [30], while using fewer bits per iteration than [22].The paper attributes the bit reduction to not using an additional control variable.

E.2 Main result for the PL/strongly convex setting

FedCOMGATE is analyzed for PL and strongly convex objectives under heterogeneous-data assumptions. The theorem provides a convergence bound, and a parameter choice yields a linear-speedup result with an ϵ-accurate solution.

  • Theorem E.6: Theorem E.6 establishes a PL or strongly convex convergence guarantee for FedCOMGATE under assumptions on smoothness, variance, heterogeneity, and initialization.The theorem is stated for FedCOMGATE(τ, η, γ) under Assumptions 1, 2, 4, 5, and 6.
  • Proof strategy: The analysis uses intermediate bounds, including Lemma E.7, to derive the theorem’s recursive convergence estimate.The supplied proof passages show repeated recursion and use of the condition 30η^2L^2τ^2 ≤ 1.
  • Linear speedup: Corollary E.8 obtains linear speedup by setting η = 1/(2L(q+1)τγ) and γ ≥ √mτ.These parameter choices are stated as the conditions for the linear-speedup result.
  • Convergence bound: The resulting bound includes terms depending on compression noise q, local-update period τ, model count m, and stochastic-gradient variance σ^2.The displayed bound contains these quantities in the supplied theorem derivation.
  • Accuracy target: The corollary states that an ϵ-accurate solution can be obtained by an appropriate choice of the communication and local-computation parameters.The supplied passage introduces the parameter choice needed to attain the target accuracy.

E.3 Main result for the general convex setting

The convex analysis applies FedCOMGATE to a regularized objective and derives an error bound under heterogeneous-data assumptions. A corollary specifies a local-computation scaling for achieving target accuracy.

  • Theorem E.9: Theorem E.9 gives a convex convergence guarantee for FedCOMGATE under Assumptions 1, 2, 4, and 5.The theorem is stated for FedCOMGATE(τ, η, γ) applied to a convex objective.
  • Parameter choice: The theorem uses φ = 1/√(mτ) and η = 1/(2Lγτ(1+q)) in the stated initialization setting.These choices appear directly in the theorem’s supplied conditions.
  • Error bound: The resulting error bound contains terms involving compression noise q, local-update period τ, model count m, γ, G, and σ^2.The supplied bound expressions explicitly include these quantities.
  • Proof connection: Theorem E.9 is connected to the PL analysis by treating the regularized objective as φ-PL.The proof replaces µ with φ after invoking the φ-PL property.
  • Accuracy complexity: For γ ≥ √(mτ), Corollary E.10 states a scaling for τ sufficient to achieve convergence error ϵ.The corollary explicitly links the condition on γ and the target error to the required local-update period.

F.1 Proof of Lemma E.3

The proof of Lemma E.3 decomposes the FedCOMGATE analysis into bounds on stochastic-gradient and local-update terms. It combines variance, sampling, smoothness, and learning-rate conditions to obtain the final inequality.

  • Final combination: The final inequality is obtained by combining Lemmas F.2, F.4, F.5, and F.6 across communication rounds.The proof describes plugging these intermediate bounds into the main recursion.
Loading 2007.01154v2…