Federated Learning with Compression: Unified Analysis and Sharp Guarantees

Motivation

• Periodic averaging reduces communication rounds by trading them for local computation, while quantization and sparsification reduce the size of communicated messages.Local SGD alternates a fixed number of local updates with synchronization and is described as retaining the convergence rate of its fully synchronous counterpart while reducing communication rounds.Source: §1 · p. 1

Research gap

• Despite progress on both approaches, their simultaneous use in federated learning remains poorly understood, especially for heterogeneous data and non-convex objectives.Prior analyses mostly focus on homogeneous data, and reducing synchronization frequency alone is not generally improvable.Source: §1 · pp. 1–2

Homogeneous local distributions

• For homogeneous data, a quantized federated-averaging variant has novel convex rates and improves prior bounds for general non-convex and strongly convex objectives.The paper also reports improved communication-round complexity bounds relative to non-compressed counterparts.Source: §1 · p. 2, Table 1 · p. 2

Heterogeneous local distributions

• For heterogeneous data, FedCOMGATE combines compression with local gradient tracking and improves reported rates for non-convex and strongly convex objectives, with novel rates for general convex objectives.The method establishes rates for general non-convex, strongly convex or PL, and convex objectives; the paper also reports best-known perfect-communication rates for convex and non-convex settings.Source: §1 · pp. 2–3, Table 2 · p. 3

Experiments

• Experiments on real federated datasets are reported as verifying the theoretical results and demonstrating the practical efficacy of the proposed methods.Source: §1 · p. 3

• Users collaboratively learn a global model without exchanging data points, communicating only through a central server connected to every user.Source: §2 · p. 3
• Each user’s local objective is its expected loss over data points drawn from that user’s probability distribution.Source: §2 · p. 3
• The analysis considers homogeneous users with identical distributions and loss functions, and heterogeneous users whose distributions and loss functions may differ.Source: §2 · p. 3

3 Federated Averaging with Compression2

• FedCOM is designed for homogeneous users and uses compressed uplink messages plus periodic averaging to reduce communication overhead.It performs τ local SGD updates between communication rounds, then sends compressed local updates to the server.Source: §3 · p. 4
• Unlike FedAvg [53] and FedPAQ, FedCOM blends the previous global model with the average of updated local models using a global learning rate γ.Setting γ = 1 recovers FedPAQ; removing compression as well recovers FedAvg.Source: §3 · pp. 4–5
• FedCOM's added global-model weighting and properly chosen γ improve FedPAQ's complexity bounds for strongly convex and non-convex settings.With perfect communication, the update is equivalent to a global SGD step toward the average aggregated local gradient directions, with stepsize ηγ.Source: §3 · p. 5

4 Compressed Local SGD with Local Gradient Tracking

• FedCOMGATE addresses heterogeneous data by tracking an estimate of the global gradient direction, unlike FedCOM’s reliance on local SGD directions.The method also requires the server to broadcast the average of local updates so nodes can estimate that direction.Source: §4 · p. 5
• Each worker’s tracker estimates the local–global gradient-direction difference, and corrected local updates use fresh stochastic gradients across τ rounds.The tracker stays fixed during the τ local updates.Source: §4 · p. 5
• Compared with SCAFFOLD [22], FedCOMGATE uses compressed signals and no extra control variable; without quantization, it generalizes VRL-SGD [30].The authors say this makes extension of the convergence analysis to device sampling straightforward, though they omit that analysis here.Source: §4 · p. 6
• FedCOM improves the quantization-noise dependence of all homogeneous communication-round bounds versus DIANA and VR-DIANA.The comparison also reports improved quantization-noise dependence for deterministic homogeneous bounds.Source: Table 3 · p. 6, §4 · p. 7
• FedCOMGATE similarly improves heterogeneous communication-round bounds versus DIANA and VR-DIANA, except for the strongly convex case.For that exception, FedCOMGATE’s result is for the PL condition, which also covers the strongly convex case; deterministic heterogeneous bounds show the same exception.Source: Table 3 · p. 6, §4 · p. 7

5 Convergence Analysis

• The analysis assumes differentiable L-smooth local objectives with a lower-bounded global optimum and an unbiased compressor whose error variance is at most q times the squared input norm.These assumptions are used throughout; cited examples of qualifying compression schemes include quantization and sparsification approaches [5] [17].Source: §5 · p. 7

5.1 Convergence of FedCOM in the homogeneous data distribution setting

• In the homogeneous setting, FedCOM’s compression-variance dependence scales down by 1/m, its required local updates scale inversely with the number of machines, and its communication-round dependence on accuracy matches centralized deterministic rates.The analysis covers nonconvex, convex, and strongly convex objectives; for convex objectives the match is up to a log factor.Source: §5.1 · p. 8
• FedCOM’s homogeneous-setting complexity bounds improve on prior compressed federated methods and [5], while its uncompressed communication-round bounds are smaller than best-known rates by a factor of 1/m.The comparison covers convex, strongly convex, and nonconvex settings.Source: §5.1 · p. 8

5.2 Convergence of FedCOMGATE in the data heterogeneous setting

• FedCOMGATE permits heterogeneous local data by assuming unbiased local stochastic gradients with bounded variance and a compression condition described as weaker than gradient-diversity assumptions.For MNIST updates quantized from 32-bit floating point to 8-bit integers, the measured Gq decreases during training and can be negative.Source: §5.2 · p. 9, Figure 1 · p. 9
• FedCOMGATE’s heterogeneous-setting bounds match centralized communication-round dependence on accuracy, and its uncompressed version matches best-known complexity bounds up to a log factor.The compression variance q does not scale down by 1/m in this setting.Source: §5.2 · p. 10
• FedCOMGATE avoids uplink control-variate communication, halving that cost relative to SCAFFOLD, but gradient tracking doubles downlink communication relative to FedAvg.The analysis notes that broadcasting is generally cheaper than uplink communication.Source: §5.2 · p. 10

Heterogeneous data distribution

• With 4× quantization, the paper estimates an 8× communication-cost reduction versus SCAFFOLD while preserving the same convergence rate; uncompressed SCAFFOLD sends at least twice as much.The communication comparison measures client-to-server uplink for CIFAR10 using an MLP with two 500-neuron hidden layers.Source: Figure 3 · p. 11, §6 · p. 11

Homogeneous data distribution

• FedCOM is best suited to homogeneous data and suffers residual error under heterogeneity, motivating gradient tracking in FedCOMGATE.The MNIST comparison contrasts homogeneous client data with a heterogeneous split in which each device has only two classes.Source: Figure 2 · p. 11, §6 · p. 11

Setup

• Experiments used 100 devices for 100 communication rounds across MNIST, CIFAR10, Fashion MNIST, and EMNIST, reporting averaged training loss and global-model test accuracy.The algorithms were implemented with PyTorch’s Distributed library and MPI.Source: §6 · pp. 10–11

Heterogeneous data distribution

• On MNIST and CIFAR10, FedCOMGATE and FedGATE outperform the other algorithms in communication size and convergence rate, especially FedCOMGATE for larger models.The comparison uses communication size and test accuracy against communicated bits; FedCOMGATE is described as especially effective when model size is relatively large.Source: §6 · pp. 11–12, Figure 4 · p. 12

EMNIST dataset

• On EMNIST, FedCOMGATE and FedPAQ converge fastest by communication size and wall-clock time, while all algorithms reach the same final convergence rate because the data are nearly homogeneous.This experiment uses data from 1,000 authors, a sampling ratio k = 0.1, and a fixed learning rate of 0.01.Source: §6 · p. 12, Figure 5 · p. 13
• Client-gradient correlations are broadly homogeneous on EMNIST but concentrated among at most four clients in the two-class-per-client MNIST split, indicating lower EMNIST heterogeneity.The correlations are computed from full-batch gradients on a shared model across 20 clients.Source: §6 · pp. 12–13, Figure 6 · p. 13

7 Conclusion

• The proposed methods theoretically and numerically require fewer server–user communication rounds than state-of-the-art federated algorithms using compression in both homogeneous and heterogeneous settings.They reduce communication overhead through periodic averaging and exchanging compressed signals.Source: §7 · p. 13

Appendix

• The supplementary material includes related work, proofs, convergence analyses for FedCOM and FedCOMGATE, and intermediate-lemma proofs.Its outline places related work in Section A, main-result proofs before convergence analyses in Sections D and E, and intermediate lemmas in Section F.Source: Appendix · p. 14

A Additional Related Work

• Additional related work covers periodic local SGD and heterogeneous FedAvg, including convergence, communication strategies, and personalization.The passages cite local SGD work [62], [48], [13] [23] [50] [53] [61], adaptive strategies [13] [32], heterogeneous FedAvg studies [15] [22] [23] [25] [28], and personalization work [10] [11] [31] [36] [47].Source: A Additional Related Work · p. 15
• Related work on communication compression includes quantization, gradient acceleration, sign-based methods, sparsification, error compensation, and sketching.The cited work includes [5] [34] [50], [29], [19],, [2] [35], [4] [49] [52] [58], and [18]; other directions include decentralized compression [24] [43] [46] and exploiting network sparsity [15] [25] [54]. Broader federated-learning perspectives are cited in [20] and [27].Source: A Additional Related Work · p. 15

B Further Experimental Studies and Results

• The supplementary experiments provide details of the Section 6 algorithms and introduce Algorithm 2 variants without compression and with client sampling.The no-compression version is FedGATE; the sampling variant is FedCOMGATE.Source: B Further Experimental Studies and… · p. 15

B.1 Variations of Algorithm 2

• FedGATE adds local gradient tracking without a server control variate, attaining SCAFFOLD’s convergence rate with half its communication size and a 2× communication speedup.Because downlink communication is negligible relative to uplink, FedGATE’s overall communication complexity is close to FedAvg; FedCOMGATE’s is close to FedPAQ. FedGATE and FedCOMGATE implicitly control server-model variance through the variances of local models.Source: §B.1 · p. 16
• FedCOMGATE incorporates client sampling by sending the global model only to a selected subset, reducing per-round communication by aggregating information from fewer clients.The experiments also study sampling’s effect on FedGATE, FedCOMGATE, and other state-of-the-art federated methods.Source: §B.1 · pp. 16–17

B.2 Additional Experiments

• Figure 7 shows FedCOMGATE and FedGATE are more robust to reduced client participation than SCAFFOLD and FedPAQ, although lower participation generally degrades performance at a fixed round count.A lower participation rate reduces communication overhead but may require more rounds to reach a target accuracy.Source: §B.2 · p. 17, Figure 7 · p. 18
• Figure 8 shows sparsification with memory can approach or slightly exceed FedGATE at some compression rates, while a compression ratio of 0.1 incurs residual error.The experiments use MNIST and Fashion MNIST with a two-hidden-layer MLP of 200 neurons per layer.Source: Figure 8 · p. 18, §B.2 · p. 19
• FedCOMGATE’s sparsification memory tracks locally what aggregation misses, but this approach cannot compress downlink broadcasts, whose cost is described as negligible.The local memory supplements gradient tracking and is not communicated to the server.Source: §B.2 · pp. 18–19
• Figure 9 shows that greater quantization noise worsens convergence, while increasing local computations can offset that noise and achieve similar results with fewer communication rounds.The experiments use MNIST; panel (b) holds quantization noise constant while increasing local computations.Source: Figure 9 · p. 19, §B.2 · p. 19

C Some Definitions and Notation

• The appendix defines Polyak–Łojasiewicz and strongly convex functions, then sets notation for full and stochastic gradients, machine-local quantities, sampled mini-batches, and conditional expectation.The stochastic gradient uses a uniformly sampled mini-batch from each data shard.Source: C Some Definitions and Notation · p. 20

D Results for the Homogeneous Setting

• Under Assumption 1 and according to the FedCOM algorithm, Lemma D.2 states that the expected inner product between the stochastic gradient and full-batch gradient can be bounded.Source: D Results for the Homogeneous Setting · p. 22

D.1 Main result for the non-convex setting

• FedCOM(τ, η, γ) has a stated average-squared-gradient bound after τ iterations for general non-convex objectives under Assumptions 1–3 and common initialization.The theorem also imposes a learning-rate condition, but its expression is not present in the supplied passage text.Source: §D.1 · p. 24
• The analysis identifies a condition on ηγ under which the convergence rate yields linear speedup.The supplied passage states ηγ = O(…), but omits the expression after O.Source: §D.1 · p. 25
• For γ = 1 and q = 0, the convergence rate reduces to the rate in [53], which the authors cite as evidence of tightness.The corollary also gives communication complexity and local-update counts, but their expressions are absent from the supplied text.Source: §D.1 · p. 26

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

• Under the PL condition, the homogeneous setting leads to the same convergence rate as for strongly convex functions.Source: §D.2 · p. 26

D.3 Main result for the general convex setting

• For general convex f(w), Theorem D.9 analyzes FedCOM on the regularized objective f(w) + φ/2 ∥w∥², with φ = 1/√(mτ).Source: §D.3 · pp. 27–28

Results for the Heterogeneous Setting

• In the heterogeneous setting, Lemma E.1 bounds the averaged stochastic-gradient variance under Assumptions 2, 4, and 5.Source: Results for the Heterogeneous Setting · p. 29
• The heterogeneous analysis also bounds the expected stochastic/full-gradient inner product and gives an update bound when 30η²L²τ² ≤ 1.Source: Results for the Heterogeneous Setting · p. 31

E.1 Main result for the nonconvex setting

• Theorem E.4 gives a nonconvex convergence result for FedCOMGATE under Assumptions 1, 2, 4, and 5, learning-rate conditions, and common initialization.Source: §E.1 · p. 32
• FedCOMGATE has better communication complexity than [22] in bits per iteration because it uses no additional control variable.Source: §E.1 · p. 36

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

• Theorem E.6 establishes a FedCOMGATE convergence result for the strongly convex or PL setting under Assumptions 1, 2, 4, 5, and 6.It also requires a learning rate satisfying the theorem’s condition and identical initialization of all local models at w(0).Source: §E.2 · p. 36
• The intermediate Lemma E.7 applies under Assumptions 1, 2, 4, and 5 when 30η^2L^2τ^2 ≤ 1.Source: §E.2 · p. 37
• For linear speedup, Corollary E.8 sets η = 1/[2L(q+1)τγ] and requires γ ≥ √(mτ).The corollary states that this choice incurs a bound, but the supplied passage does not expose its full expression.Source: §E.2 · p. 41

E.3 Main result for the general convex setting

• For convex f, Theorem E.9 bounds FedCOMGATE iterates over 0 ≤ t ≤ Rτ − 1 under Assumptions 1, 2, 4, and 5.The supplied theorem passage does not include a legible complete bound expression.Source: §E.3 · p. 42
• With all models initialized at w(0), choosing φ = 1/√mτ and η = 1/[2Lγτ(1+q)] yields the stated convergence bound.The corresponding bound is fragmented in the supplied passages, so its full expression cannot be recovered reliably.Source: §E.3 · p. 42
• The proof invokes Theorem E.6 for a φ-PL condition, then rearranges Eq. (92) and replaces μ with φ to obtain an error bound.The excerpt also gives a shorthand-notated bound, but its formula is incomplete across the supplied fragments.Source: §E.3 · p. 42
• Corollary E.10 states that for general convex functions with γ ≥ √mτ, achieving convergence error ε requires a choice of τ; the supplied passage truncates after τ = O.The order expression is not present in the excerpt.Source: §E.3 · p. 43

F.1 Proof of Lemma E.3

• Lemma F.1 establishes an intermediate inequality under Assumptions 1 and 4 and the stated learning-rate condition.Source: §F.1 · p. 44
• The proof bounds terms (I) and (II) of Eq. (99) separately before assembling the bound.The passages introduce separate bounding steps for each term and then plug in intermediate lemmas.Source: §F.1 · pp. 45, 48
• The proof handles r ≥ 1 and r = 0 with Lemmas F.4 and F.5, respectively, then plugs both into Eq. (99).Source: §F.1 · pp. 47–48
• The cited passage says that plugging Lemma F.6 into Eq. (112) yields the following bound, while Lemma F.6 is stated under Assumptions 1, 2, 4, and 5.Source: §F.1 · pp. 50, 52

F.2 Proof of Lemma E.7

• For every communication round, the F.2 proof uses Lemmas F.2 and F.5 to write the corresponding bound.Source: §F.2 · p. 53
• The cited step follows from Lemma F.6 without summation over r.Source: §F.2 · p. 53