---
kind: concept
slug: gradient-tracking
title: Gradient tracking
summary: >-
  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.
tags: [optimization, decentralized-optimization, multi-agent]
papers: ["1806.00877"]
related: [multi-agent-reinforcement-learning, minimax-optimization, variance-reduced-gradient, decentralized-federated-learning, centralized-training-decentralized-execution]
status: draft
updated_at: 2026-11-12
---

## 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 [arxiv: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
[arxiv: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 [arxiv: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 [arxiv: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
[arxiv:1806.00877 §3, eq. 13, eq. 14]. Card: [PD-DistIAG (Wai et al.)](/papers/1806.00877).

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 [arxiv:1806.00877 §3.1, thm. 1]. The paper's
experiments use one stated step-size setting, which is not the theorem's
multiple [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1806.00877 app. B, fig. B.2]. With M=5000 the ring and the random graph are nearly identical [arxiv:1806.00877 app. B, fig. B.3] |

Stated assumptions for the convergence result [arxiv: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 [arxiv: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.

```pseudocode
# 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_tr
```

## Contradictions

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
[arxiv:1806.00877 §3.1, §4].

## Papers

- [PD-DistIAG (Wai et al.)](/papers/1806.00877): introduces PD-DistIAG, which tracks the gradient over neighbours and over stored samples, with a linear convergence proof on connected graphs.
