PaperlayerView exact revision on arXiv

Source-linked AI summary

Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data

Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi

arXiv:2102.04761v2cs.LG

TL;DR

Heterogeneous client data makes decentralized deep-learning optimization difficult and can hurt generalization. The paper proposes Quasi-Global momentum, which approximates the global optimization direction locally without extra communication. Its experiments report strong performance across heterogeneity levels, with consistent findings on ImageNet-32.

  • Problem

    Heterogeneous client datasets create diverse local objectives that can destabilize decentralized optimization and reduce generalization.

    Source: §1 · p. 1

  • Method

    Quasi-Global momentum locally approximates the global optimization direction to mitigate heterogeneous-data difficulties without extra communication overhead.

    Source: §1 · p. 2

  • Results

    QG-DSGDm-N significantly outperforms strong competitors across CIFAR-10 heterogeneity levels, with consistent observations on ImageNet-32.

    Source: §5.2 · p. 8

  • Takeaways & Limitations

    A gap from centralized training remains, and the authors consider closing it critical for wider decentralized-learning adoption.

    Source: Conclusion · p. 9

    Specializing the results to federated learning is beyond the paper’s scope, and adapting some recent federated-learning techniques to gossip-based decentralized learning is non-trivial.

    Source: §2 · p. 2

Abstract

from arXiv · show

Decentralized training of deep learning models is a key element for enabling data privacy and on-device learning over networks. In realistic learning scenarios, the presence of heterogeneity across different clients' local datasets poses an optimization challenge and may severely deteriorate the generalization performance. In this paper, we investigate and identify the limitation of several decentralized optimization algorithms for different degrees of data heterogeneity. We propose a novel momentum-based method to mitigate this decentralized training difficulty. We show in extensive empirical experiments on various CV/NLP datasets (CIFAR-10, ImageNet, and AG News) and several network topologies (Ring and Social Network) that our method is much more robust to the heterogeneity of clients' data than other existing methods, by a significant improvement in test performance ($1\% \!-\! 20\%$). Our code is publicly available.

1. Introduction

Decentralized learning keeps data distributed and enables peer-to-peer training, but heterogeneous client datasets can destabilize optimization and harm generalization. The paper studies these effects and proposes Quasi-Global momentum to improve decentralized training without extra communication overhead.

1. Introduction

  • Decentralized methods communicate peer-to-peer without a central coordinator, supporting scalable training and privacy-preserving applications where data remains on clients.Source: §1 · p. 1
  • Heterogeneous client data creates diverse local objectives, slowing and destabilizing global convergence and reducing generalization; Figure 1 illustrates this with α-controlled CIFAR-10 client allocations.Source: §1 · p. 1, Figure 1 · p. 2
  • The authors find that heterogeneity hinders local-momentum acceleration, while globally synchronizing momentum improves optimization and generalization but raises communication costs and violates decentralization.Source: §1 · p. 1
  • Quasi-Global momentum locally approximates the global optimization direction without extra communication, stabilizing training and improving generalization under high data heterogeneity.The paper also proposes QG-DSGDm and QG-DSGDm-N and reports greater robustness to heterogeneity than existing methods.Source: §1 · p. 2
  • The paper examines algorithms across heterogeneity levels and network topologies, proves convergence, and investigates normalization alternatives because Batch Normalization is vulnerable to non-i.i.d. local data.Source: §1 · p. 2

2. Related Work

Related work covers decentralized optimization, communication efficiency, momentum, and normalization for distributed learning. The authors distinguish their heterogeneous-data focus from prior methods and note that federated-learning specialization is outside this paper’s scope.

2. Related Work

  • Decentralized optimization uses gossip averaging to reach consensus and is studied for scalability, communication efficiency, and data locality; federated learning can be viewed as a star-topology variant, but its specialization is outside this work’s scope.Source: §2 · p. 2
  • Methods such as D2/Exact-diffusion and gradient tracking aim to remove heterogeneity’s theoretical influence, but their deep-learning convergence and generalization advantages remain unclear.Source: §2 · p. 2
  • Communication-efficiency work explores compression, multiple local updates, and topology design.Source: §2 · p. 3
  • Prior distributed momentum methods often use local buffers on homogeneous data; periodic synchronization or SlowMo adds communication, while this paper claims its method adds none and outperforms existing methods.Source: §2 · p. 3
  • Batch Normalization can fail with heterogeneous local data because activation statistics differ; prior remedies include Group Normalization and changes to synchronization of BN weights or statistics.Source: §2 · p. 3

3. Method

QG-DSGDm replaces locally accumulated momentum with a communication-free approximation of the global optimization direction to stabilize learning on heterogeneous data. The section defines its setting, establishes convergence under stated assumptions, and relates the method to prior approaches.

3.2. QG-DSGDm Algorithm

  • On heterogeneous data, local momentum can improve convergence toward the global-minimum neighborhood yet produce unstable, oscillating trajectories.The illustration uses two workers with different local minima and uniform averaging after each local update.Source: §3.2 · pp. 3–4, Figure 2 · p. 4
  • Synchronizing local momentum buffers improves performance by 1%−5% in the reported Table 5 comparison, but adds communication and violates the decentralized setup.The comparison is between row 3 and row 7 in Table 5.Source: §3.2 · p. 4
  • QG-DSGDm uses a quasi-global momentum buffer, formed from consecutive synchronized models, to approximate the global direction without extra communication and reduce local-direction drift.The method combines this buffer with local stochastic gradients.Source: §3.2 · p. 4

3.3. Convergence Analysis

  • Under Assumption 1, QG-DSGDm has a non-convex convergence guarantee whose iteration bound has linear speedup in worker count, independent of communication topology.The analysis also states that its data-heterogeneity drift term matches the tightest analysis of DSGD without momentum.Source: §3.3 · p. 5
  • The convergence theorem constrains β but not μ; the paper reports that QG-DSGDm performs well in practice even when the β constraint is violated.Source: §3.3 · p. 5

3.4. Connection with Other Methods

  • Unlike MimeLite, QG-DSGDm forms its direction from consecutive synchronized models; unlike SlowMo, it interacts with local updates and uses consecutive models rather than τ ≫1 steps.MimeLite uses full-batch gradients on a previously synchronized model; the paper describes SlowMo and QG-DSGDm as orthogonal.Source: §3.4 · p. 5

4. Understanding QG-DSGDm

The paper examines QG-DSGDm through an isolated consensus problem and a single-worker optimization case. These analyses report faster consensus than gossip averaging and connect the single-worker method to Quasi-Hyperbolic Momentum.

4.1. Faster Convergence in Average Consensus

  • In the averaging-consensus problem isolated from learning by removing gradients and step size, QG-DSGDm can quickly reach a critical consensus distance (for example, 10^-2), compared with standard gossip averaging.Source: §4.1 · p. 6

4.2. QG-DSGDm (Single Worker Case) Recovers QHM

  • With one worker, QG-DSGDm simplifies to QG-SGDm, which recovers Quasi-Hyperbolic Momentum when β̂ = μ + (1 − μ)β.SGDm is a special case obtained by setting μ=0.Source: §4.2 · p. 6
  • On the Rosenbrock function, QG-SGDm has a less oscillatory optimization trajectory than SGDm.The comparison is described for the single-worker case.Source: §4.2 · p. 6
  • QG-SGDm has a larger effective step-size than SGDm in the single-worker CIFAR-10 comparison, which the paper says explains performance gains.Source: §4.2 · p. 6

5. Experiments

The experiments evaluate decentralized optimization under varying data heterogeneity, datasets, models, and network topologies. QG momentum generally improves performance over competing decentralized methods, with reported gains across heterogeneous settings and optimizer variants.

5.1. Setup

  • The experiments cover CIFAR-10, ImageNet-32, ImageNet, and AG News using ResNet, VGG, or DistilBERT models, with three-seed averages generally reported.CV training uses SGD and NLP uses Adam; the decentralized variants are adapted from these base optimizers.Source: §5.1 · pp. 6–7

5.2. Results

  • For CIFAR-10 and ImageNet, ResNet with EvoNorm outperforms its GroupNorm counterpart across algorithms, heterogeneity degrees, and topologies.The authors present EvoNorm as an effective alternative to batch normalization for CNNs trained on heterogeneous distributed data.Source: §5.1 · p. 7, §5.2 · p. 8
  • QG-DSGDm-N significantly outperforms strong competitors across all tested CIFAR-10 heterogeneity levels, with larger benefits at higher non-i.i.d. degrees.The comparison covers Ring and Social Network topologies; the ImageNet(-32) results are reported as consistent.Source: Table 1 · p. 7, §5.2 · p. 8, Table 3 · p. 8
  • QG-DAdam is preferable to decentralized Adam on AG News DistilBERT fine-tuning and CIFAR-10 ResNet-EvoNorm-20 training.The authors leave a better adaptation and theoretical proof for future work.Source: §5.2 · p. 8, Table 6 · p. 9
  • Quasi-global momentum also generalizes to time-varying directed topologies on ImageNet, while D2 and Gradient Tracking methods do not achieve comparable test performance to QG-DSGDm-N on CIFAR-10.D2 requires a constant learning rate that does not fit stage-wise schedules, and the improved D2+ still performs far behind the proposed scheme.Source: §5.2 · pp. 8–9
  • In the ablation study, quasi-global momentum variants outperform other decentralized methods without extra communication, while synchronizing buffers or gradients yields only marginal gains.The reported comparison excludes the centralized upper bound; tuning the DSGDm-N momentum factor does not resolve heterogeneity-related training difficulty.Source: §5.2 · p. 9, Table 5 · p. 9

Conclusion

The conclusion reports that data heterogeneity destabilizes decentralized training and degrades performance, while the proposed momentum-based algorithm stabilizes training and improves accuracy. The appendix also visualizes the Social Network topology used in the main paper.

Conclusion

  • The proposed momentum-based algorithm stabilizes training and, especially in mildly heterogeneous settings, yields a 10–20% increase in accuracy, though a gap from centralized training remains.The authors identify closing that gap as important for wider adoption of decentralized learning.Source: Conclusion · p. 9

A.1. Visualization for Communication Topologies

  • Figure 7 visualizes the Social Network topology evaluated in the main paper.It is generated from the Davis Southern women graph in NetworkX.Source: §A.1 · p. 14, Figure 7 · p. 14

A.2. Visualization of Non-IID Local Data

The appendix describes a Dirichlet-based scheme for synthesizing non-i.i.d. client data and visualizes the resulting partitions for the considered datasets. It also points to the algorithm description for the quasi-global Adam variant.

A.2. Visualization of Non-IID Local Data

  • The client-data partition scheme draws a class distribution from Dir(αp), where α controls similarity across clients: as α approaches zero, each client holds examples from one random class.As α approaches infinity, clients share the prior distribution.Source: §A.2 · p. 14
  • Figures 8 and 9 visualize partitioned local data across client counts, datasets, and Dirichlet α values, with dot sizes indicating samples per class.The visualizations cover CIFAR-10 and ImageNet(-32), plus AG News and SST-2 on 16 clients.Source: §A.2 · p. 14, Figure 8 · p. 15, Figure 9 · p. 15

B.1. Detailed Algorithm Description

  • The quasi-global momentum variant of Adam is detailed as QG-DAdam in Algorithm 2.Source: §B.1 · p. 16

B.2. Difference between DMSGD and QG-DSGDm

The appendix contrasts DMSGD’s momentum-buffer update with QG-DSGDm and notes that QG-DSGDm’s single-worker forms connect to established momentum methods. These reductions show how its parameters recover SGDm or SGDm-N in specified cases.

B.2. Difference between DMSGD and QG-DSGDm

  • DMSGD and QG-DSGDm use different momentum-buffer update schemes, and DMSGD is based on heavy-ball momentum while QG-DSGDm extends to heavy-ball, Nesterov, and Adam variants.Source: §B.2 · p. 19

B.3.1. CONNECTIONS BETWEEN SGDM AND QG-DSGDM

  • In the single-worker case, QG-SGDm recovers QHM, and SGDm is a special case of its update when μ=0.The appendix also relates QG-SGDm/QHM to SGDm-N with a learning-rate rescaling.Source: §B.3.1 · pp. 19–20, §B.3.2 · p. 20

B.3.2. CONNECTIONS BETWEEN SGDM-N AND QG-SGDM

  • The appendix derives QG-SGDm as equivalent to SGDm-N under learning-rate rescaling, with equivalent iterate sequences under the stated zero-initialized momentum condition.Source: §B.3.2 · pp. 20–21

B.3.3. THE SIMPLIFICATION OF QG-DSGDM-N ON SINGLE WORKER CASE

  • For the single-worker QG-DSGDm-N simplification, setting μ=0 recovers SGDm-N.The appendix defines the transformed momentum parameter as β̂ := μ + (1 − μ)β.Source: §B.3.3 · p. 21

C. Global Convergence Rate Proofs

The proof analyzes a virtual SGD-style sequence and bounds its distance from the real iterates. It combines progress and error bounds to establish convergence results under stated smoothness, stochastic-gradient, and mixing assumptions.

C. Global Convergence Rate Proofs

  • The stated conditions include lower-bounded smooth losses, unbiased stochastic gradients with bounded variance, and a doubly stochastic mixing matrix.The strongly-convex progress result additionally assumes that the local functions are strongly convex.Source: C. Global Convergence Rate Proofs · pp. 22–23
  • The proof tracks a virtual sequence with an SGD-style update and bounds its distance from the real sequence of iterates.The virtual sequence makes the analysis tractable while the real iterates are shown to remain close.Source: C. Global Convergence Rate Proofs · p. 22
  • Each virtual step balances stochastic-gradient error, consensus error, and momentum error.Consensus error measures node disagreement; momentum error measures disagreement between each node's momentum and the across-node average.Source: C. Global Convergence Rate Proofs · pp. 23, 25, 26
  • The analysis combines non-convex and strongly-convex one-step progress lemmas with a non-convex convergence-rate theorem.The theorem uses a selected step size, but the supplied passages do not state its rate explicitly.Source: C. Global Convergence Rate Proofs · pp. 23, 28

D.1. Results on Distributed Average Consensus Problem

The appendix tests average consensus across communication topologies and scales. Even without gradient updates, QG-DSGDm converges to high relative precision faster than normal gossip.

D.1. Results on Distributed Average Consensus Problem

  • Without gradient updates, QG-DSGDm still reaches high relative precision faster than normal gossip across the tested topologies and scales.Figure 10 reports the average-consensus comparison.Source: Figure 10 · p. 30, §D.1 · p. 30

D.2. Results on 2D Illustration

These experiments examine QG momentum's behavior in illustrations, single-worker training, toy optimization, and decentralized CV settings. They report more stable optimization in several comparisons and test QG-DSGDm-N across topology scales and tuning variants.

D.2. Results on 2D Illustration

  • Under heterogeneous data, local momentum in SGDm remains affected by oscillation across momentum-factor choices, while QG-SGDm trades stabilization against convergence speed through β.The experiments set μ := β, which may lead to undesirable behavior.Source: §D.2 · p. 30, Figure 11 · p. 31

D.3. Understanding QG-DSGDm and QG-DSGDm-N on the Single Worker Case

  • On ResNet-20/CIFAR-10, Nesterov variants outperform HeavyBall variants with BN and GN, with larger gains when optimization is challenging, such as with GN.Excluding weight decay is detrimental to final generalization, and QG-SGDm-N benefits more when optimization is fragile or unstable.Source: §D.3 · p. 32, Figure 12 · p. 32, Figure 13 · p. 33

D.4. Understanding QG-DSGDm on the Single Worker Case via Toy Function

  • On two toy functions, QG-SGDm's optimization trajectory shows less oscillation than Heavy-ball momentum SGD's trajectory.The comparisons use the Rosenbrock function and a non-convex toy problem.Source: §D.4 · p. 35, Figure 15 · p. 35

D.5. The Learning Curves on CV tasks

  • Figure 17 presents ResNet-EvoNorm-20/CIFAR-10 learning curves across non-i.i.d. degrees and Ring and Social topologies.The supplied passage describes the curves' scope but does not report their outcomes.Source: §D.5 · p. 36, Figure 17 · p. 37

D.6. The Ineffectiveness of Tuning Momentum Factor for DSGDm-N

  • Tuning DSGDm-N's momentum factor does not alleviate training difficulty caused by heterogeneity.Figure 18 compares its learning-rate and momentum combinations with QG-DSGDm-N using a tuned learning rate and default momentum factor 0.9.Source: §D.6 · p. 36, Figure 18 · p. 37

D.7. The Superior Performance of QG-DSGDm-N Generalize Different Topology Scales

  • Quasi-global momentum shows a predominant performance gain across topology scales (n); test top-1 accuracy for ResNet-EvoNorm-20 on CIFAR-10 was evaluated across non-i.i.d.-ness settings, averaging three seeds with sufficient learning-rate tuning.Source: §D.7 · p. 36, Table 7 · p. 36

D.8. Multiple-step QG-DSGDm-N variant

  • For the multiple-step QG-DSGDm-N variant, tuning τ does not yield a significant performance gain.Table 8 reports the ablation for ResNet-EvoNorm-20 on CIFAR-10, averaged over three seeds with tuned learning rate.Source: §D.8 · p. 38, Table 8 · p. 38

D.9. Comparison with D2 and Gradient Tracking (GT) methods

The comparison distinguishes QG-DSGDm from D2 and gradient tracking (GT) in their update designs and communication. The authors report that QG-DSGDm-N outperforms GT by a large margin and that D2's update presents difficulties with learning-rate decay.

D.9. Comparison with D2 and Gradient Tracking (GT) methods

  • D2 and GT do not include momentum in their algorithm design or theoretical analysis, unlike QG-DSGDm's quasi-global momentum approach.The authors also distinguish QG-DSGDm's update from D2's update.Source: §D.9 · p. 38
  • D2 requires a constant learning rate, which the authors say does not fit stage-wise learning-rate schedules used in state-of-the-art deep learning.They state the D2 update would break during learning-rate decay if the model difference reaches a factor of 10η.Source: §D.9 · p. 38
  • QG-DSGDm-N outperforms GT by a large margin; GT requires an extra communication step per update to approximate the global average of local gradients.The authors note GT may offer more benefit in the extreme low-training-loss regime, while their focus is test performance.Source: §D.9 · p. 38

Related papers

Loading 2102.04761v2…