Topology-Shaped Overdispersion in Decentralized Langevin Sampling

When many machines jointly draw samples from a Bayesian posterior without a central server, each machine typically runs a Langevin sampler. That is a noisy gradient method that, with the right amount of injected Gaussian noise, wanders through parameter space in proportion to posterior probability. The machines average their parameters with their immediate neighbors once per step. Existing analyses of these single-loop samplers ask whether the network average reaches the right distribution, and they answer in terms of the graph's spectral gap. This proposal argues that the quantity practitioners actually use is each machine's own samples, which it uses for local predictions and uncertainty estimates. Those samples are systematically too spread out. Each node injects independent noise, and one round of neighbor averaging per step cannot erase the part of that noise that disagrees across nodes.

The proposal's central claim is that this excess spread is set by how often a random walk on the communication graph returns to its starting node. It is not set by the spectral gap. As a result, it scales differently with step size on rings, grids, and expanders. It can be removed at zero extra communication by drawing the injected noise from a seed shared across the network, which is a design choice no existing decentralized sampler makes. If the claim holds, it supplies the sampling counterpart to the "beyond spectral gap" story in decentralized optimization. It also gives a concrete recipe for calibrated per-node posteriors.

Core Claim

Consider the update used, up to scaling conventions, by Decentralized Langevin Dynamics for Bayesian Learning (D-ULA) and by Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo. In this update each node mixes its neighbors' parameters with weights $W$, takes a gradient step of size $\eta$, and adds independent Gaussian noise of variance $2\eta$. Write each node's parameter as the network mean plus a disagreement term. For a quadratic posterior in which each node feels curvature $\mu$, the disagreement is a linear recursion driven by the component of the noise orthogonal to consensus. Its stationary variance at node $i$, per coordinate, is

$$\sigma_i^2(\eta) = 2\eta \sum_{k \ge 0} (1-\eta\mu)^{2k} \big[(W-J)^{2k}\big]_{ii},$$

where $J = \mathbf{1}\mathbf{1}^\top/n$ is the exact-averaging matrix. The bracketed term is a return probability of the lazy random walk defined by $W$, minus the uniform part. Node $i$'s samples therefore follow the target distribution blurred by a Gaussian of variance $\sigma_i^2$.

The blur behaves differently across graph types:

  • Expanders and dense graphs. Return probabilities vanish geometrically, so $\sigma_i^2 = O(\eta)$.
  • Rings. Return probabilities decay like $k^{-1/2}$, the one-dimensional recurrence of random walks. The sum is cut off only by the curvature factor, so $\sigma_i^2 \sim \sqrt{\eta/\mu}$. Measured against a target variance of order $1/\mu$, the relative overdispersion is $\sqrt{\eta\mu}$ rather than $\eta\mu$.
  • Two-dimensional grids. These sit in between, with a logarithmic factor.
  • Infinite rings. The quantity stays finite even though the spectral gap is exactly zero.
  • Stars. The leaves have high return probability through the hub, so stars can look worse than rings despite their larger spectral gap.

These predictions mirror, for sampling, what Beyond spectral gap: the role of the topology in decentralized learning showed for optimization. That paper found that rings beat stars in practice and that infinite graphs still learn. It replaced the spectral gap with an "effective number of neighbors" built from random-walk variance reduction. The proposal's second claim is that this effective-neighbor quantity, or the return-probability sum above, predicts per-node calibration of decentralized samplers, and the spectral gap does not.

The third claim concerns the remedy. Suppose every node draws its Gaussian increment from a pseudo-random generator seeded identically across the network, and rescales the gradient so that the mean chain still targets the global posterior. The thermal noise then lies entirely in the consensus direction, and $\sigma_i^2$ from noise is zero. Disagreement is then caused only by data heterogeneity, which gradient tracking is designed to cancel.

Shared noise also bears on an unresolved concern about tracked samplers. In DIGing-SGLD, the tracking variable is updated with gradient differences evaluated at consecutive noisy iterates. It therefore inherits thermal noise that differs across nodes, and its effect on the stationary law has not been characterized. With shared noise, those differences are driven by a common increment, and only differences in local curvature leak through. The claim is not that shared randomness is a deep trick. It is that the bias it removes is real, topology-shaped, and currently invisible in a literature that evaluates the network mean.

Relation to Prior Work

Two lines of work motivate the gap.

The first is the decentralized Langevin family. D-ULA proves convergence with decaying steps and reports a "collaboration dividend" in network size. DE-SGLD/DE-SGHMC proves linear convergence to a neighborhood whose size depends on the spectral gap. DIGing-SGLD and Generalized EXTRA SGLD add tracking or difference-of-updates corrections to remove heterogeneity bias. All four inject independent noise per node and state guarantees in spectral-gap terms. None isolates per-node thermal disagreement as a separate error from heterogeneity drift. This proposal keeps their single-loop structure and their tracking mechanisms and changes only the noise.

The second motivating paper is Beyond spectral gap. It supplies both the empirical tension (ring outperforming star) and the analytical tool (random-walk variance reduction), which this proposal transplants from gradient noise to thermal noise.

The method borrows from single-loop optimization. The SUDA analysis separates consensus error from tracking error and shows that bias-correction methods have much milder topology dependence than earlier proofs suggested, for example transient time $O(n^3/(1-\lambda)^2)$ for Exact Diffusion against $O(n^3/(1-\lambda)^4)$ for decentralized SGD. This proposal uses the same two-error decomposition with an added thermal channel.

Two other works are adjacent but differ in mechanism. Client-Only Distributed MCMC avoids Langevin noise entirely through a blocked Gibbs sampler over a coupled augmented target. It requires bipartite or tree graphs and exact local conditionals, which limits it to conjugate-like models; it remains a strong reference on Gaussian targets. Decentralized Metropolis-adjusted HMC fights bias with Taylor-approximated acceptance and Hessian tracking. This costs extra communication and has no ergodicity proof. Our fix sends nothing extra.

One paper constrains the design: Which mode is better for federated learning? documents performance collapse on sparse topologies as client count grows. We test whether the per-node overdispersion term is a sampling analogue of that collapse.

A caveat on scaling conventions: the cited samplers differ in how they scale local gradients and noise. The derivation will be redone for each sampler's exact update rather than assumed to transfer.

Research Program

The analytical part has three steps:

  1. Derive $\sigma_i^2$ exactly for quadratic targets under D-ULA-style, DIGing-style, and EXTRA-style updates. For the tracked variants, this requires a joint recursion for disagreement and tracking error that includes the thermal channel Gap 1 points to.
  2. Prove the recurrence-driven scalings ($\eta$, $\eta\log(1/\eta)$, $\sqrt{\eta}$ for expander, 2-D grid, ring).
  3. Extend to strongly log-concave targets by perturbation, following the Wasserstein-perturbation style of Generalized EXTRA SGLD.

Non-convex targets are treated empirically only.

The algorithmic part is shared-seed noise with a mixing parameter $\rho \in [0,1]$. The injected increment is $\sqrt{\rho}$ times a shared draw plus $\sqrt{1-\rho}$ times a private draw, with gradient scaling adjusted so the mean chain's temperature is unchanged. At $\rho=0$ we recover existing samplers. At $\rho=1$ the nodes behave as one chain. Intermediate $\rho$ trades per-node calibration against the diversity of $n$ partially independent particles, which may matter for multimodal posteriors and is plausibly the source of D-ULA's collaboration dividend.

We also give a locally computable estimate of $\sigma_i^2$. Nodes run a few gossip rounds on random probe vectors to estimate return probabilities. This lets practitioners either choose $\rho$ or deflate reported uncertainties when they keep private noise.

Baselines

The naive reference point is plain single-loop decentralized SGLD with independent noise, as in DE-SGLD and D-ULA. It is run with the same mixing matrix, step-size grid, mini-batch size, and iteration budget as every other method. For MNIST, D-ULA reports test accuracy of about 98.4% against about 98.1% for point-estimate SGD. We will reproduce rather than quote this number, since our evaluation centers on calibration, not accuracy.

The strongest gradient-based competitor is DIGing-SGLD with independent noise. It is the only sampler with finite-time Wasserstein guarantees over time-varying graphs, and it already removes heterogeneity bias. We found no reported empirical result on Lacuna for DIGing-SGLD on these benchmarks; its file entry gives only an $O(\log(1/\epsilon)/\epsilon^2)$ iteration complexity and an $O(\sqrt{\eta})$ accuracy neighborhood. Generalized EXTRA SGLD is a second tracked baseline. Both get identical tuning budgets of 20 step-size settings per topology, selected on held-out log-likelihood.

On Gaussian targets, the strongest non-gradient reference is Client-Only Distributed MCMC, which reports a 2-Wasserstein distance of 0.76 within 80 iterations on a 32-dimensional Gaussian over trees and circular networks up to 63 nodes. We run it only where its bipartite requirement holds.

A centralized SGLD chain at matched total gradient evaluations is the gold reference, and long-run full-batch Hamiltonian Monte Carlo provides ground-truth posteriors for the tabular models.

The ablation that isolates the key ingredient is DIGing-SGLD with shared noise versus with private noise, everything else identical, swept over $\rho$. Beating the strongest baseline means two things at matched communication and gradient budget. Per-node 2-Wasserstein distance on Gaussian targets must drop by a margin larger than the seed-to-seed spread. Per-node expected calibration error or negative log-likelihood on tabular and MNIST tasks must improve, with no loss in accuracy.

Why not just…?

Why not just shrink the step size? Overdispersion does fall as $\eta$ falls, but mixing time grows like $1/\eta$. On rings the predicted relative overdispersion falls only as $\sqrt{\eta\mu}$, so halving the error costs four times the iterations rather than two. The experiments plot per-node calibration error against wall-clock iterations for both strategies. If small steps match shared noise at equal cost on the topologies tested, the remedy is not worth having and the contribution reduces to the diagnosis.

Why not just average the nodes' samples at the end, or periodically? This is the real threat. Network averaging removes disagreement exactly, and with heavy thinning it may be cheap. However, exact averaging needs either a server or many gossip rounds per retained sample. Sparse graphs need the most rounds. It also gives calibrated samples only at the moment of averaging, not continuously at each node. We will measure how many gossip rounds per thinned sample are needed to match shared-noise calibration on ring, grid, and exponential graphs. If that overhead is negligible relative to the sampling budget on realistic graphs, we will say so.

Why not just add a thermostat, as in SGNHT or CCAdL? These thermostats regulate the kinetic temperature of a single chain against unknown gradient noise. Gossip overdispersion lives in position space, orthogonal to consensus, and it does not show up as excess kinetic energy in any one node's momentum. We test this directly by running a decentralized momentum sampler with a per-node Nosé-Hoover thermostat. The prediction is that per-node variance inflation persists unchanged.

Proposed Experiments

Synthetic Gaussian targets in 5 and 32 dimensions, the setting of Client-Only Distributed MCMC, give exact per-node 2-Wasserstein distances and variances. Topologies are ring, star, 2-D grid, exponential, and complete graphs, with sizes from 16 to 1024 nodes and step sizes over two decades.

The first decisive check is whether measured per-node variance inflation matches the return-probability formula. We also test whether its log-log slope in $\eta$ is near 1 on expanders and near 1/2 on rings. Across topologies, the effective-neighbor quantity should rank-correlate with measured overdispersion better than the spectral gap does. The sharpest case is the star versus ring ordering, with large rings approximating the infinite-ring limit.

Bayesian logistic regression on UCI Breast Cancer Wisconsin, MAGIC Gamma Telescope, and a9a uses both homogeneous and label-skewed partitions, with full-batch Hamiltonian Monte Carlo as ground truth for posterior marginals. Metrics are per-node marginal variance ratios, test negative log-likelihood, and calibration error.

A Bayesian neural network on MNIST uses the split-label partition of Decentralized Metropolis-adjusted HMC, with SVHN as out-of-distribution data following D-ULA. This tests whether the gain persists in a multimodal regime and whether intermediate $\rho$ helps uncertainty on out-of-distribution data through particle diversity.

The proposal fails if any of three results appear. Measured overdispersion might not track the predicted topology-dependent scaling. The spectral gap might predict per-node calibration as well as return probabilities do. Shared noise might give no per-node calibration gain over tracked samplers with private noise at matched budget.