Home / Curated / Algorithms / DIGing and Push-DIGing (Distributed Inexact Gradient Tracking Over Time-Varying Graphs)

DIGing and Push-DIGing (Distributed Inexact Gradient Tracking Over Time-Varying Graphs)

Algorithms AIMech:DigingAndPushDigingDistributedInexactGradientTrackingOverTimeVaryingGraphs DRAFT

Aliases: DIGing and Push-DIGing, Distributed Inexact Gradient Tracking, Push-DIGing

A pair of geometrically convergent distributed gradient tracking algorithms over time-varying graphs (Nedic, Olshevsky, & Shi 2017, Sections 2 and 4, Algorithms 1-2): (1) Distributed Inexact Gradient Tracking (DIGing, Algorithm 1), which updates x(k+1) = W(k) x(k) - alpha y(k) and y(k+1) = W(k) y(k) + nabla f(x(k+1)) - nabla f(x(k)) with y(0) = nabla f(x(0)) over B-connected sequences of doubly stochastic matrices W(k); and (2) Push-DIGing (Algorithm 2), which achieves geometric convergence over time-varying B-strongly-connected directed graphs using column-stochastic matrices C(k) via u(k+1) = C(k)(u(k) - alpha y(k)), v(k+1) = C(k) v(k), x(k+1) = V(k+1)^{-1} u(k+1), and y(k+1) = C(k) y(k) + nabla f(x(k+1)) - nabla f(x(k)).

Identity Notes & Concept Scope Distinct from DSGT and GSGT (AIMech:DsgtAndGsgtDistributedStochasticGradientTracking, Pu & Nedic 2021), which analyze noisy stochastic gradients G(x_k, xi_k) over static expectation-doubly-stochastic graphs, and from Stochastic Gradient Push (AIMech:StochasticGradientPushAndOverlapSgpForDistributedDeepLearning, Assran et al. 2019), which omits the gradient tracker y(k) and achieves sublinear O(1 / sqrt(n K)) convergence rather than global R-linear geometric convergence O(lambda^k) over time-varying directed graphs.

Claims & Grounded Evidence

4 Claims

Mechanism #r431-small-gain-cyclic-loop-and-explicit-geometric-convergence-rate

By modeling the four error sequences (||x - x^*||, ||y - bar_y||, ||bar_y||, ||x(k) - x(k-1)||) in exponentially weighted l_infty^{lambda} norms and bounding their B-step consensus contraction factor delta in [0, 1) (Lemma 3.3), the small-gain theorem (Theorem 3.5) proves that whenever the cyclic product gamma_1 gamma_2 gamma_3 gamma_4 < 1 holds, DIGing converges globally at the explicit R-linear rate O(lambda^k) with lambda = (1 - alpha bar_mu / 1.5)^{1/(2B)}, achieving polynomial complexity O(n^{4.5} bar_kappa^{1.5} ln(1 / varepsilon)) under lazy Metropolis weights (Theorem 3.7, Theorem 3.14, Corollaries 3.15-3.16).

supports Source: Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs · Locator: Section 3 Small-Gain Convergence Analysis (Lemmas 3.3-3.13, Theorem 3.7, Theorem 3.14, Corollaries 3.15-3.16)

Mechanism #r431-push-diging-row-stochastic-similarity-transformation-on-digraphs

In Push-DIGing (Algorithm 2), scaling the column-stochastic matrix C(k) by the diagonal PushSum weight matrix V(k) = diag(v(k)) defines the similarity-transformed matrix tilde_R(k) = V(k+1)^{-1} C(k) V(k) which is strictly row-stochastic (tilde_R(k) 1 = 1, Eq. 4.4), converting the de-biased iterate evolution into x(k+1) = tilde_R(k)(x(k) - alpha V(k)^{-1} y(k)) (Eq. 4.6a) while C(k) preserves 1^T y(k) = 1^T nabla f(x(k)), establishing global R-linear convergence O((lambda_P)^k) over time-varying B-strongly-connected directed graphs (Theorem 4.13).

supports Source: Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs · Locator: Section 4 Push-DIGing for Time-Varying Directed Graphs (Algorithm 2, Equations 4.1-4.8, Lemmas 4.1-4.12, Theorem 4.13)

Limitation #r431-exact-gradient-and-bounded-intercommunication-interval-limitation

Guarantees exact geometric convergence only for deterministic (noiseless) local gradients under bounded B-connected communication intervals and uniform positive lower bounds tau > 0 on nonzero mixing weights.

supports Source: Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs · Locator: Section 2.2 Assumptions 1-4 & Section 4.2 Assumptions 2'-3'

Application #r431-time-varying-wireless-sensor-network-huber-and-logistic-estimation-application

Applied to distributed Huber loss minimization and regularized logistic regression over time-varying undirected and directed multi-agent graphs.

supports Source: Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs · Locator: Section 5 Numerical Experiments (Figures 1-4), pp. 2627-2630

⚠️ Curated Limitations & Negative Results

Requires exchanging two d-dimensional vectors (iterate and gradient tracker) per communication step.
In Push-DIGing, each agent must know its instantaneous out-degree to construct column-stochastic weights.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	DIGing and Push-DIGing are foundational decentralized gradient-tracking optimization algorithms over time-varying undirected and directed networks.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r431-primary-pdf`	Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs Angelia Nedic, Alex Olshevsky, Wei Shi	primary paper full_text	ID: https://doi.org/10.1137/16M1084316 sha256:5b4d942cb487…
`r431-arxiv-abs`	Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (arXiv abstract) Angelia Nedic, Alex Olshevsky, Wei Shi	primary paper abstract_only	ID: https://arxiv.org/abs/1607.03218 sha256:4d61bf09bd7e…
`r431-metadata-cr`	Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (Crossref metadata) Angelia Nedic, Alex Olshevsky, Wei Shi	primary paper abstract_only	ID: https://doi.org/10.1137/16M1084316 sha256:fdc60b7c9b28…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:34:00Z

Updated: 2026-10-19T08:34:00Z

Source File: data/curated/DigingAndPushDigingDistributedInexactGradientTrackingOverTimeVaryingGraphs.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