Home / Curated / Algorithms / DeTAG Decentralized Stochastic Gradient Tracking with By-Phase Accelerated Gossip

DeTAG Decentralized Stochastic Gradient Tracking with By-Phase Accelerated Gossip

Algorithms AIMech:DetagDecentralizedStochasticGradientTrackingWithByPhaseAcceleratedGossip DRAFT

Aliases: DeTAG, Decentralized Stochastic Gradient Tracking with By-Phase Accelerated Gossip, By-Phase Accelerated Gossip Gradient Tracking

A decentralized stochastic non-convex optimization algorithm (DeTAG) that partitions training into phases of length R, concurrently executing R steps of momentum-accelerated gossip z_{r+1,i} = (1 + eta) sum_{j in N_i U {i}} z_{r,j} W_{ji} - eta z_{r-1,i} with eta = (1 - sqrt(1 - lambda^2)) / (1 + sqrt(1 - lambda^2)) on both the model replica x_tilde and gradient tracker y while accumulating B*R stochastic gradient queries at the fixed phase point x_{k,i}, and updating x_{k+1} = AG_R(x_k - alpha * y_k) and y_{k+1} = AG_R(y_k + g_tilde_k - g_tilde_{k-1}) at each phase boundary to achieve near-minimax-optimal sample and communication complexity.

Identity Notes & Concept Scope Introduced by Yucheng Lu and Christopher De Sa (ICML 2021, PMLR Vol. 139, pp. 7111-7123; arXiv:2006.08085). Distinct from standard Decentralized Stochastic Gradient Tracking (DSGT / GT-DSGD, Pu & Nedic 2020; Zhang & You 2019; Xin et al. 2021), which corresponds to the unaccelerated single-step special case R = 1, eta = 0 and incurs suboptimal O((1 - lambda)^(-3)) spectral-gap dependence; and distinct from RelaySum / RelaySGD (Vogels et al., NeurIPS 2021, Round 549), which routes unattenuated sums over spanning trees rather than running by-phase Chebyshev-accelerated gossip with gradient tracking on arbitrary doubly-stochastic gossip matrices.

Claims & Grounded Evidence

4 Claims

Mechanism #detag-by-phase-accelerated-gossip-and-gradient-tracker-mechanism

Within each phase k of R iterations, each worker i simultaneously accumulates R stochastic gradient batches g_(k) at fixed parameters x_{k,i} while applying R steps of Accelerated Gossip AG(z, W) with extrapolation weight eta = (1 - sqrt(1 - lambda^2)) / (1 + sqrt(1 - lambda^2)) to both the model replica x_tilde and gradient tracker y, contracting consensus error by factor rho = (1 - sqrt(1 - lambda_2(W)))^R before performing the phase-end tracker update y_{t+1,i} <- y_{t+1,i} + g_(k) - g_(k-1).

supports Source: Optimal Complexity in Decentralized Training · Locator: Section 6 Algorithms 2-3 & Appendix B.4 Equations (52)-(61), pp. 9-10, 24

Scope #detag-near-optimal-nonconvex-sample-and-communication-complexity-scope

For L-smooth non-convex objectives with bounded initial heterogeneity (1/n) sum_i ||grad f_i(0) - grad f(0)||^2 <= varsigma_0^2 and gossip second eigenvalue lambda, setting phase length R = max((1/2) log n, (1/2) log(varsigma_0^2 T / (Delta * L))) / sqrt(1 - lambda) enables DeTAG to reach an epsilon-stationary point in O(Delta * L * sigma^2 / (n * B * epsilon^4) + Delta * L * log(n + varsigma_0 * n / (epsilon * sqrt(Delta * L))) / (epsilon^2 * sqrt(1 - lambda))) iterations, matching the information-theoretic lower bound of Corollary 1 up to a logarithmic factor.

supports Source: Optimal Complexity in Decentralized Training · Locator: Section 4 Theorem 1 & Corollary 1, Section 6 Theorem 3, Table 2, pp. 3, 7, 10

Limitation #detag-phase-length-and-spectral-gap-tuning-limitation

Requires tuning or estimating the gossip acceleration parameter eta (which depends on the second largest eigenvalue lambda of W) and the phase length R, and holds the model query point x_{k,i} fixed across the R inner steps of each phase.

supports Source: Optimal Complexity in Decentralized Training · Locator: Section 6 Understanding the phase length R & Appendix A.1-A.2, pp. 10, 18-19

Application #detag-unshuffled-cifar-sparse-graph-training-application

Applied to decentralized training of LeNet on unshuffled non-IID CIFAR-10 and ResNet-20 on CIFAR-100 across sparse ring topologies with small spectral gaps (1 - lambda down to 4e-4).

supports Source: Optimal Complexity in Decentralized Training · Locator: Section 7 Experiments, Figures 2-3, pp. 10-12

⚠️ Curated Limitations & Negative Results

Requires a doubly-stochastic gossip matrix W and tuning of the phase length R and acceleration weight eta.
Accumulates gradients at a fixed phase iterate x_{k,i} across R steps unless modified with heuristic local steps.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	AIO:FederatedLearning covers distributed training over local datasets, whereas DeTAG is a serverless decentralized stochastic gradient-tracking algorithm with R-step Chebyshev-accelerated gossip phases.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r552-primary-pdf`	Optimal Complexity in Decentralized Training Yucheng Lu, Christopher De Sa	primary paper full_text	ID: https://dblp.org/rec/conf/icml/LuS21 sha256:720a7e94166b…
`r552-arxiv-abs`	Optimal Complexity in Decentralized Training (arXiv abstract) Yucheng Lu, Christopher De Sa	primary paper abstract_only	ID: https://arxiv.org/abs/2006.08085 sha256:310417162cf8…
`r552-metadata-cr`	Optimal Complexity in Decentralized Training (Crossref metadata) Yucheng Lu, Christopher De Sa	primary paper abstract_only	ID: https://dblp.org/rec/conf/icml/LuS21 sha256:f37c01f632ed…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:35:00Z

Updated: 2026-10-19T10:35:00Z

Source File: data/curated/DetagDecentralizedStochasticGradientTrackingWithByPhaseAcceleratedGossip.yaml · Schema: curated_concept.yaml

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