DSGT and GSGT (Distributed and Gossip Stochastic Gradient Tracking)
Algorithms AIMech:DsgtAndGsgtDistributedStochasticGradientTracking DRAFT
Aliases: DSGT and GSGT, Distributed Stochastic Gradient Tracking, Gossip Stochastic Gradient Tracking
A family of decentralized stochastic optimization algorithms over doubly stochastic network graphs W (Pu & Nedic 2021, Sections 2 and 4, Equations 4 and 37-39) in which each agent i maintains a local model x_{i,k} and an auxiliary stochastic gradient tracker y_{i,k} initialized at y_{i,0} = g_i(x_{i,0}, xi_{i,0}), updating in synchronous Distributed Stochastic Gradient Tracking (DSGT) via x_{k+1} = W(x_k - alpha_k y_k) and y_{k+1} = W y_k + G(x_{k+1}, xi_{k+1}) - G(x_k, xi_k), or in randomized pairwise Gossip Stochastic Gradient Tracking (GSGT) by activating a single directed wake-up edge (i_k, j_k) per iteration to average iterates and gradient trackers across {i_k, j_k}.
Identity Notes & Concept Scope
Distinct from deterministic DIGing and Push-DIGing (AIMech:DigingAndPushDigingDistributedInexactGradientTrackingOverTimeVaryingGraphs, Nedic, Olshevsky, & Shi 2017), which analyze exact gradients over time-varying B-connected graphs via small-gain theorems, and from D2 (AIMech:D2VarianceReducedDecentralizedTrainingOverHeterogeneousData, Tang et al. 2018), which uses a single-variable two-step recursion X_{t+1} = (2 X_t - X_{t-1} - gamma G_t + gamma G_{t-1}) W requiring lambda_n(W) > -1/3 rather than explicit dynamic average consensus tracking y_{k+1} = W y_k + G_{k+1} - G_k and randomized pairwise gossip GSGT.
Claims & Grounded Evidence
4 Claims
Mechanism
#r428-dynamic-average-tracking-invariant-and-constant-stepsize-linear-speedup
Initializing y_0 = G(x_0, xi_0) under a doubly stochastic mixing matrix W preserves the exact dynamic average conservation bar_y_k = (1/n) 1^T y_k = (1/n) 1^T G(x_k, xi_k) at every iteration k (Lemma 2, Eq. 5); under mu-strong convexity and L-smoothness with constant step-size alpha, the 3x3 error-moment matrix A contracts at rate rho(A) <= 1 - 2 alpha mu Gamma / (Gamma + 1) (Lemma 4, Eq. 10) to a steady-state MSE limsup_{k->infty} (1/n) E[||x_k - 1 x^*||^2] <= (alpha sigma^2 / (mu n)) O(1) + (alpha^2 L^2 sigma^2 / (mu^2 (1 - rho_w)^3)) O(rho_w^2 ||W - I||^2) completely free of inter-agent gradient heterogeneity ||nabla f_i(x^*)||^2 (Theorem 1, Remark 1, Eqs. 11-12).
Mechanism
#r428-diminishing-stepsize-topology-independent-asymptotic-efficiency-and-gsgt
With diminishing step-sizes alpha_k = theta / (m + k) (where theta mu > 1), DSGT achieves the asymptotic mean-squared error 2 theta^2 sigma^2 / (n (theta mu - 1) k) for every agent (minimized at theta = 2 / mu to 8 sigma^2 / (n mu^2 k)), matching centralized stochastic gradient descent independent of the network spectral gap 1 - rho_w (Theorem 2, Remark 3); furthermore, GSGT preserves 1^T y_k = 1^T G(x_k, xi_k) via pairwise edge updates (Eqs. 37-39) and reduces communication volume by O(|E| / n) on well-connected graphs (Section 4, Theorem 3).
Limitation
#r428-doubly-stochastic-mixing-and-dual-message-overhead-limitation
Requires a doubly stochastic mixing matrix W (or symmetric pairwise gossip updates in GSGT) so that 1^T W = 1^T holds, and requires exchanging both the iterate x_{i,k} - alpha_k y_{i,k} and the tracker y_{i,k} across active links.
Application
#r428-decentralized-logistic-regression-and-ridge-regression-sensor-networks-application
Applied to decentralized ridge regression and regularized logistic classification over random Erdos-Renyi, ring, and grid multi-agent networks, eliminating the steady-state heterogeneity bias of decentralized stochastic gradient descent.
⚠️ Curated Limitations & Negative Results
- Doubles per-round communication payload compared to un-tracked D-PSGD because both iterates and gradient trackers are mixed across neighbors.
- In GSGT, the secondary node j_k in each wake-up pair must also evaluate a fresh local stochastic gradient at its updated iterate to preserve exact sum conservation.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | DSGT and GSGT are decentralized stochastic gradient tracking methods that eliminate client data heterogeneity bias without a central server. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r428-primary-pdf
|
Shi Pu, Angelia Nedic
|
primary paper
full_text
|
ID: https://doi.org/10.1007/s10107-020-01487-0
sha256:e0bd98aa5e8b…
|
r428-arxiv-abs
|
Shi Pu, Angelia Nedic
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1805.11454
sha256:4d61bf09bd7e…
|
r428-metadata-cr
|
Shi Pu, Angelia Nedic
|
primary paper
abstract_only
|
ID: https://doi.org/10.1007/s10107-020-01487-0
sha256:7b9492473d76…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T08:31:00Z
Updated: 2026-10-19T08:31:00Z
Source File:
data/curated/DsgtAndGsgtDistributedStochasticGradientTracking.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