DCD-PSGD and ECD-PSGD (Difference-Compression and Extrapolation-Compression Decentralized Parallel SGD)
Algorithms AIMech:DcdPsgdAndEcdPsgdCompressedDecentralizedParallelStochasticGradientDescent DRAFT
Aliases: DCD-PSGD and ECD-PSGD, Difference Compression D-PSGD and Extrapolation Compression D-PSGD, Communication-Compressed Decentralized Parallel SGD
A pair of communication-compressed decentralized parallel stochastic gradient descent algorithms over doubly stochastic gossip graphs W (Tang et al. 2018, Section 4, Algorithms 1-2) that overcome the divergence of naive model-compression gossip by maintaining local neighbor replicas x_tilde_t^{(j)} and compressing either: (1) the iterate difference z_t^{(i)} = x_{t+1/2}^{(i)} - x_t^{(i)} via x_{t+1}^{(i)} = x_t^{(i)} + C(z_t^{(i)}) in Difference Compression D-PSGD (DCD-PSGD, Algorithm 1), or (2) the time-extrapolated state z_t^{(j)} = (1 - 0.5 t) x_{t-1}^{(j)} + 0.5 t x_t^{(j)} reconstructed as x_tilde_t^{(j)} = (1 - 2 / t) x_tilde_{t-1}^{(j)} + (2 / t) C(z_t^{(j)}) in Extrapolation Compression D-PSGD (ECD-PSGD, Algorithm 2).
Identity Notes & Concept Scope
Distinct from Choco-SGD and Choco-Gossip (AIMech:ChocoSgdAndChocoGossipDecentralizedCompressedOptimization, Koloskova, Stich, & Jaggi 2019), which introduce a consensus stepsize gamma in (0, 1] on the gossip step x_{t+1} = x_t - eta g_t + gamma sum_j w_{ij} (x_hat_j - x_hat_i) to support biased contractive compressors, whereas DCD-PSGD applies full-weight gossip W to unbiasedly compressed differences and ECD-PSGD uses harmonic O(1/t) extrapolation-averaging.
Claims & Grounded Evidence
4 Claims
Mechanism
#r425-dcd-psgd-spectral-compression-threshold-and-linear-speedup
In DCD-PSGD (Algorithm 1), compressing the model difference z_t^{(i)} = sum_j x_t^{(j)} W_{ij} - gamma g_t^{(i)} - x_t^{(i)} causes the compression error to vanish as x_{t+1/2}^{(i)} - x_t^{(i)} -> 0, achieving the O(1 / sqrt(n T)) non-convex linear speedup rate whenever the relative compression noise ratio alpha satisfies the spectral stability condition (1 - rho)^2 - 4 mu^2 alpha^2 > 0 (where rho = max_{i>=2} |lambda_i(W)| and mu = max_{i>=2} |1 - lambda_i(W)|, Theorem 1, Corollary 2).
Mechanism
#r425-ecd-psgd-harmonic-extrapolation-arbitrary-compression-convergence
When compression is too aggressive for DCD-PSGD ((1 - rho)^2 - 4 mu^2 alpha^2 <= 0), ECD-PSGD (Algorithm 2) compresses z_t^{(j)} = (1 - 0.5 t) x_{t-1}^{(j)} + 0.5 t x_t^{(j)} and updates x_tilde_t^{(j)} = (1 - 2/t) x_tilde_{t-1}^{(j)} + (2/t) C(z_t^{(j)}), which satisfies the exact noiseless identity x_tilde_t^{(j)} = x_t^{(j)} when C(z) = z (Lemma 11) and damps compression noise variance by O(1 / t) (E||x_tilde_t^{(j)} - x_t^{(j)}||^2 <= O(1 / t), Lemma 12), guaranteeing O(1 / sqrt(n T)) convergence for arbitrarily large compression noise (Theorem 3, Corollary 4).
Limitation
#r425-neighbor-replica-memory-and-unbiased-compressor-limitation
Both DCD-PSGD and ECD-PSGD assume unbiased stochastic compression operators (E[C(z)] = z) and require each worker i to store local replicas x_tilde_t^{(j)} (or their weighted sum) for its connected graph neighbors j.
Application
#r425-decentralized-resnet20-cifar10-ring-topology-training-application
Applied to decentralized ring-topology training of ResNet-20 on CIFAR-10 with stochastic quantization, outperforming naive model-compression D-PSGD and centralized QSGD at low network bandwidth.
⚠️ Curated Limitations & Negative Results
- DCD-PSGD diverges when the relative compression noise alpha exceeds the spectral threshold (1 - rho) / (2 mu).
- ECD-PSGD's extrapolation step amplifies transient stochastic gradient variance by a constant factor when x_t - x_{t-1} is large.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | DCD-PSGD and ECD-PSGD are communication-compressed decentralized stochastic gradient optimization algorithms closely related to decentralized federated learning. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r425-primary-pdf
|
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, Ji Liu
|
primary paper
full_text
|
ID: https://papers.nips.cc/paper/2018/hash/2b8a61594b1f4c4db0902a8a395ced93-Abstract.html
sha256:430f3f305e80…
|
r425-arxiv-abs
|
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, Ji Liu
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1803.06443
sha256:c46ead1de7b7…
|
r425-metadata-cr
|
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, Ji Liu
|
primary paper
abstract_only
|
ID: https://papers.nips.cc/paper/2018/hash/2b8a61594b1f4c4db0902a8a395ced93-Abstract.html
sha256:78e1ac5ab66f…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T08:28:00Z
Updated: 2026-10-19T08:28:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories