Concept · 1 paper · updated 2026-11-12
Gradient tracking
Decentralised estimation of a sum of local gradients. Each agent keeps a running estimate of the network-wide gradient, mixes it with its neighbours and swaps in fresh local gradients, so all agents reach one target without a central node. Needs a connected graph and per-sample memory.
optimizationdecentralized-optimizationmulti-agent
Markdown3 min read
AI-compiled overview, updated 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
Overview
Several agents each hold a local gradient, and the goal is the gradient of their average, without a central node that collects the data [arxiv:1806.00877 §1, §3]. Each agent keeps a tracker: its own estimate of that network-wide average. Two steps repeat. The tracker is averaged with the trackers of the agent's neighbours over the communication graph. The agent then adds the change in its own local gradient since it last used the same sample. The trackers approximate the average gradient, and the agents' iterates are pulled towards one common point 1806.00877 §3, eq. 13.
When each local term is itself an average over many samples, the tracker also tracks over time. The agent stores the last gradient for every sample. When a sample is visited again, its stored value is replaced, not added to 1806.00877 §3, alg. 1. The paper's analysis uses this stored-sample form.
The invariant that the method relies on is that the network average of the trackers equals the average, over all agents and samples, of the most recent stored gradient 1806.00877 §3, lem. 1.
This page covers only the cards compiled so far. It does not survey other gradient-tracking methods.
Variants
Primal-dual tracking with stored samples (PD-DistIAG)
The paper applies the idea to decentralised policy evaluation with a linear value function, where each agent observes only its own reward. The problem is a saddle point: a shared value parameter is minimised while one dual vector per agent is maximised 1806.00877 §2, eq. 10. Each agent runs two trackers. The primal tracker mixes over neighbours and uses the stored-sample replacement. The dual tracker is local, so it only uses the replacement over time 1806.00877 §3, eq. 13, eq. 14. Card: PD-DistIAG (Wai et al.).
Under the paper's assumptions, the averaged iterates converge linearly on a connected graph. Theorem 1 gives the dual step as a fixed multiple of the primal step, and asks only that the primal step be sufficiently small. It does not give an explicit value 1806.00877 §3.1, thm. 1. The paper's experiments use one stated step-size setting, which is not the theorem's multiple 1806.00877 §3.1, §4.
When to use which
Only one paper is covered, so the choice is between this method and a simpler one. Use the constraints below to decide.
| Situation | Use | Why |
|---|---|---|
| Agents must not send rewards or raw data to a central node, and the graph is connected | Stored-sample tracking (PD-DistIAG) | Linear convergence is proved for connected graphs 1806.00877 §3.1, thm. 1 |
| Memory per agent is tight, or each agent holds many samples | Budget memory first | Storage is 2Md reals per agent, with M samples and feature dimension d 1806.00877 §3. The paper's own run (M=5000, d=300) therefore needs 3 million reals per agent |
| Communication is expensive and the feature dimension is large | Expect a high cost | Each iteration exchanges primal iterates and trackers with neighbours. The paper calls this costly and leaves fewer exchanges as future work 1806.00877 §3 |
| Samples cannot be guaranteed to recur regularly | Not covered as analysed | The proof needs every sample visited at least once in each window of M iterations. Independent draws with replacement may break this 1806.00877 §3.1 |
| Graph is a ring, not a random graph | Expect slower early convergence | With N=500 and M=500 the ring converges more slowly 1806.00877 app. B, fig. B.2. With M=5000 the ring and the random graph are nearly identical 1806.00877 app. B, fig. B.3 |
Stated assumptions for the convergence result 1806.00877 §3.1: every sample is visited regularly (A1), and the sample matrix is full rank with an invertible covariance matrix (A2). The paper also reports results only on simulated networks, with no delays or failures 1806.00877 §4.
Implementation sketch
Language-agnostic pseudocode of the PD-DistIAG core. Rows are agents, W is
doubly stochastic and zero on non-edges. The dual step is a fixed multiple of
the primal step, as in Theorem 1.
# theta, w: primal and dual per agent (N, d)
# s, d_tr: primal and dual trackers per agent (N, d)
# memo_s, memo_d: last stored gradient per agent and sample (N, M, d)
for t = 1, 2, ...:
# All agents use the same sample index at each step [alg. 1]
p = sample_index(t)
# Fresh local gradients on sample p, one row per agent [eq. 10]
g_s = primal_grad(theta, w, p)
g_d = dual_grad(theta, w, p)
# Mix the old primal tracker, then swap in the new gradient [eq. 13]
s = W @ s + (g_s - memo_s[:, p]) / M
# Dual tracker is local: swap in only, no mixing [eq. 14]
d_tr = d_tr + (g_d - memo_d[:, p]) / M
memo_s[:, p] = g_s
memo_d[:, p] = g_d
# Consensus step on theta, ascent step on w [eq. 15]
theta = W @ theta - gamma1 * s
w = w + gamma2 * d_trContradictions
None known. Only one paper is covered. Inside that paper, the step-size setting used in its experiments differs from the theorem's multiple of the primal step, and the paper does not say which one the experiments used 1806.00877 §3.1, §4.
Papers
- PD-DistIAG (Wai et al.): introduces PD-DistIAG, which tracks the gradient over neighbours and over stored samples, with a linear convergence proof on connected graphs.
Source and license
Compiled from the papers listed on this page, all published under CC BY, CC BY-SA or CC0, with citations. See each paper's page for its authors and license.