Measuring Residual Topological Bias in Directed Decentralized Learning

Many devices can train one model together without a central server: each device averages its parameters with its neighbors' and takes gradient steps on its own data. When links are one-way, as they are with uneven transmit power or broadcast-only radios, plain averaging quietly reweights the devices. Well-connected devices count for more and peripheral ones for less, so the swarm optimizes the wrong objective. A family of correction methods is proven to remove this bias. Two examples are push-sum, which sends a scalar "mass" alongside the parameters and divides by it, and power-iteration schemes that estimate each node's influence and rescale by it. The empirical record for these methods is thin. Their validations report test accuracy on CIFAR-style benchmarks over clean, synchronous, simulated graphs. Accuracy is a poor probe of whether bias was removed: an ensemble can score well while effectively ignoring a third of its members.

We propose to measure the bias directly. We add a small set of decoupled "canary" parameters to the model, and give each node a known quadratic target on them. The canaries are mixed through exactly the same communication as the real model. After training, the canary values reveal, by solving a linear system, the effective weight that the procedure placed on every node. This gives an instrument that reads out residual bias as a number. With it we will test a specific prediction: under realistic message loss and asynchrony, methods whose correction relies on conserved mass (push-sum and its descendants) lose their debiasing more than methods that normalize on the receiver side (row-stochastic power-iteration tracking). Accuracy-based benchmarks have so far been unable to show this distinction either way.

Core Claim

The bias-elimination literature gives an exact target, the unweighted objective $\frac{1}{n}\sum_i f_i$. Yet no paper in this area checks whether a trained model reached it rather than some weighted version $\sum_i w_i f_i$. We claim that $w$ can be recovered cheaply and accurately during deep-network training, and that doing so changes conclusions.

Each node $i$ holds a canary target $c_i \in \mathbb{R}^m$, drawn at random with $m \ge n$. The node adds the loss $\tfrac{\mu}{2}\|\theta - c_i\|^2$ on a separate canary block $\theta \in \mathbb{R}^m$. This block shares no parameters with the network, but it is mixed, divided by push-sum mass, or rescaled by influence estimates exactly as every other coordinate is. Suppose the procedure effectively minimizes $\sum_i w_i f_i$ with weights $w_i \ge 0$ summing to one. Then the consensus canary value is $\bar\theta = \sum_i w_i c_i$, and the weights follow from

$$\hat w = \arg\min_{w \ge 0,\ \mathbf{1}^\top w = 1} \|C w - \bar\theta\|^2,$$

where $C$ is the $m \times n$ matrix whose columns are the targets $c_i$. Residual bias is then the total-variation distance between $\hat w$ and the uniform vector, along with the weight assigned to the least-central decile of nodes.

The recovery is exact when the bias is topological, meaning a per-node scale that is the same for every coordinate. That is the case for row-stochastic averaging, where the weights are the stationary distribution $\pi$ of the mixing matrix (Graph balancing for distributed subgradient methods over directed graphs identifies this failure). It is also the case for imperfect push-sum ratios. Methods whose weighting depends on the model state may violate this assumption. Adaptive Moreau weighting is one example. For those methods we cross-check against a second, task-level probe described below.

Research Program

The work has three parts. The first validates the instrument. On static graphs where $\pi$ can be computed exactly from $W$, we check that $\hat w$ recovers $\pi$ for naive row-stochastic decentralized SGD and recovers the uniform vector for exact push-sum. The task-level probe uses CIFAR-10 nodes with planted, known class-prior shifts. A cross-entropy-trained model's average predicted prior on balanced held-out data should move toward the $w$-weighted mixture of node priors. We test whether the two probes agree on rankings across methods. If they do not, the canary is not measuring what the task experiences, and that is reported as a negative result.

The second part stress-tests the corrections. We run directed training in the decentralizepy emulator with three link-level perturbations. The first is independent and bursty packet loss, using a Gilbert-Elliott two-state channel to approximate fading-driven outages of the kind studied in Distributed Consensus Over Wireless Sensor Networks Affected by Multipath Fading. The second is heavy-tailed per-node delays, using the asynchronous directed-graph code in Asy-SGD. The third is stale out-degree knowledge, where senders split mass among neighbors who no longer hear them.

The mechanistic prediction is as follows. Push-sum is debiased only if mass is conserved, because $x_i/y_i$ cancels $\pi_i$ only when $x$ and $y$ suffer identical losses from identical totals. Lost or stale messages therefore leak mass unevenly and reintroduce a weighting. Pull-style row-stochastic methods instead normalize over whatever actually arrived. So we expect PULL-DIAG-GT from Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks to keep $\hat w$ closer to uniform under loss, at the price of the small-divisor instability that paper handles with multi-step gossip. We will log the minimum local divisor ($y_i$ or $\hat\pi_i$) over time, so instability can be tied to bias spikes rather than inferred.

The third part is a small physical check. We will run 16 single-board nodes over Wi-Fi broadcast with deliberately uneven transmit power. This matches the scale that Sparse-Push profiled in simulation. Its purpose is to ask whether the emulator's loss model predicts the measured $\hat w$ within its seed-to-seed spread. This is the cheapest test of whether the emulation findings mean anything physically.

Relation to Prior Work

The methods under test come from three lines of work. The first is push-sum-based gradient tracking: DEXTRA (DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs), ADD-OPT and D-DGD (On the distributed optimization over directed networks), and ExtraPush (ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks). These works prove convergence to the unweighted optimum but validate on toy problems. The second line extends push-sum to deep learning: Adaptive Weighting Push-SUM, Quantized Decentralized Stochastic Learning over Directed Graphs, and Sparse-Push. These report accuracy, loss, and bits on synchronous simulated graphs with lossless links. The third line is eigenvector tracking with row-stochastic mixing, in PULL-DIAG-GT. All three motivate this proposal. None of them measures the effective objective, and none injects link loss or asynchrony.

Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning argues that deliberate non-uniform weighting can help when data sizes differ. This constrains our framing. Our target is the weighting the designer intended, which is uniform here, or proportional to data size in their setting. The instrument measures deviation from whatever target is specified. Epidemic Learning relies on all-to-all reachability, so it serves only as a reference point outside the constrained-topology regime. The broader validation gap is documented elsewhere, for example by A Local Clustering Algorithm for Massive Graphs, where conservative theoretical parameters underperform in practice. It motivates the stance here but supplies no method.

Baselines

The naive reference is row-stochastic decentralized SGD with no correction. It should recover $\hat w \approx \pi$, which makes it both a lower bound on debiasing and a positive control for the instrument. The second baseline is symmetrized-graph DSGD, which discards one-way links and runs doubly stochastic averaging. It removes bias by construction but loses connectivity, and we measure the cost in time-to-accuracy.

The corrected methods are vanilla push-sum SGD, the SGAP and MSGAP variants of Adaptive Weighting Push-SUM, ADD-OPT gradient tracking, and PULL-DIAG-GT with and without multi-step gossip (MG of 5 and 10). AWPS is the strongest existing push-sum method on deep benchmarks. Its paper reports a 3.34% absolute final-accuracy gain over push-sum SGD on CIFAR-10 with ResNet-18, and wall-clock time roughly 2x faster than gradient tracking such as S-ADDOPT. PULL-DIAG-GT is the strongest receiver-normalized method, with no reported result found on Lacuna for its CIFAR-10 accuracy.

All methods share the same data partitions (Dirichlet α of 0.1 and 1.0), the same ResNet-18, the same graphs (directed exponential, ring, grid, random geometric with power asymmetry at 16, 32, and 64 nodes), the same per-method learning-rate sweep of eight values, and the same perturbation traces replayed from fixed seeds. Comparisons are made at an equal number of transmitted bytes as well as at equal iterations, so multi-step gossip and gradient tracking are charged for their extra traffic.

The ablation that isolates the instrument has two parts. We run each method with the canary block removed, to confirm the canaries do not change accuracy beyond seed noise at the chosen μ. We also run with canaries but on lossless links, to show that any bias appears only under perturbation.

"Beating" has a specific meaning in this study, because the contribution is a measurement. The hypothesis is supported if PULL-DIAG-GT keeps total-variation distance from uniform below that of push-sum and AWPS by more than the 95% seed interval at a 10% loss rate, while their CIFAR-10 accuracies remain within one point of each other. That would show accuracy hides a bias difference.

Why not just…?

Why not just report worst-node or per-node accuracy? Per-node accuracy mixes topological weighting with how hard each node's data is. A peripheral node with easy classes looks well served even if its gradients were ignored. We will compute it alongside $\hat w$ and test whether it detects the planted bias in the naive row-stochastic control, where the true $\pi$ is known. If worst-node accuracy separates methods as well as $\hat w$ does, the instrument is unnecessary, and we will say so.

Why not just compute $\pi$ from the mixing matrix? This works only when the matrix is known and fixed. Under random loss, delays, and stale out-degrees, the effective operator is a product of random matrices that no node observes. Its weighting also depends on how each algorithm's correction interacts with the failures, and that interaction is exactly what is in question. We do use the analytic $\pi$ in the clean setting, as the instrument's ground truth.

Why not just symmetrize the links or use randomized gossip? Symmetrization is a real competitor wherever enough two-way links exist, so it is included as a baseline with a connectivity cost. The lower bound in the PULL-DIAG-GT paper suggests that cost grows as the spectral gap shrinks. Epidemic Learning's assumption that any node can reach any other fails on spatially constrained radios. We restrict its peer sampling to physical neighbors and measure its $\hat w$, rather than assume it debiases.

Decisive Checks

Three outcomes would decide the study. First, on clean graphs the canary recovery should match analytic $\pi$ to within a total-variation distance of 0.02. If not, the instrument fails and the project reduces to the task-level probe. Second, the ranking of methods by residual bias under 10% bursty loss either matches or contradicts their ranking by accuracy, and a mismatch is the main finding. Third, the 16-node physical run either falls inside the emulator's predicted $\hat w$ band or it does not. The third check decides whether simulated validation, the norm in every cited deep-learning paper here, is adequate for this question at all.