In decentralized learning, there is no central server. Each machine trains on its own data and repeatedly averages its model with its immediate neighbors in a communication network, a step called gossip. The theory of how network shape affects this process almost always assumes each machine draws fresh, independent samples. Real deployments look different: traffic sensors, epidemic trackers and robots see streams in which today's data closely resembles yesterday's. That matters because gossip and time do the same job. Both average away noise. When a node's stream changes slowly, averaging over time removes little of its slowly drifting noise, so averaging over space, through the network, has to do the work instead. Our central claim is that the cost of a sparse network depends on how slowly the local streams forget their past. We predict that a ring or grid which is harmless on i.i.d. data becomes the dominant error source on slowly mixing streams.
We propose to make this precise and use it. The gossip step is treated as a graph filter, a polynomial in the network's connectivity matrix whose response at each "graph frequency" says how strongly that pattern of disagreement between nodes is suppressed. This makes decentralized SGD on streams a space-time filter acting on gradient noise. That view yields a topology measure that accounts for temporal correlation. It also yields a design: learned gossip filters, constrained so they stay stable when links fail and transfer from small training networks to much larger deployments.
Core Claim
Consider a linearized (locally quadratic) model of decentralized SGD in which each step applies the gossip filter $h(S)=\sum_{k=0}^{K} a_k S^k$. Here $S$ is the normalized Laplacian of the communication graph, $K$ is the number of neighbor exchanges per step, $\eta$ is the step size and $\mu$ is the local curvature. Suppose node gradient noise has temporal power spectral density $\Phi(\omega)$, meaning the noise energy at temporal frequency $\omega$. Slowly mixing streams concentrate this energy near $\omega=0$. The stationary disagreement-plus-noise error then decomposes over graph eigenvalues $\lambda_j$ and temporal frequencies:
$$\mathcal{E}(h)\;\approx\;\sum_{j}\int_{-\pi}^{\pi}\frac{\eta^{2}\,\Phi(\omega)}{\big|1-(1-\eta\mu)\,h(\lambda_j)\,e^{-i\omega}\big|^{2}}\,\frac{d\omega}{2\pi}.$$
This is the standard transfer-function computation for a linear recursion driven by stationary noise. It recovers a Vogels-style "effective number of neighbors" when $\Phi$ is flat, which is the i.i.d. case. When $\Phi$ peaks at $\omega\approx 0$, the integrand is largest exactly where $h(\lambda_j)$ stays close to one for small nonzero $\lambda_j$, the slowly varying disagreement modes that sparse graphs have in abundance. Three testable consequences follow. First, the penalty of sparse versus dense topologies should grow with the stream's mixing time. Second, the best gossip filter depends on $\Phi$, not on the graph alone. Third, neither the spectral gap nor the i.i.d. effective-neighbors measure should predict error rankings across mixing regimes as well as $\mathcal{E}(h)$ does.
A structural observation links this to graph neural network stability. A good consensus filter must equal one at $\lambda=0$ and fall quickly just above it. The integral Lipschitz condition of Stability of Graph Neural Networks to Relative Perturbations, $|h'(\lambda)|\le L/\lambda$, allows exactly this: steep slopes near zero and flatness at high frequencies. That paper uses the condition to guarantee bounded output change under relative edge perturbations. In our setting, the same constraint costs little consensus quality and in return makes the gossip operator provably robust to link drops and rewiring. That is the property a deployed peer-to-peer system needs.
Relation to Prior Work
The motivating evidence comes from three lines of decentralized-learning theory, all built for i.i.d. data:
- Spectral-gap rates. Distributed Dual Averaging In Networks and A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning tie convergence to the spectral gap.
- Effective number of neighbors. Beyond spectral gap: the role of the topology in decentralized learning shows that local variance reduction, measured by an effective number of neighbors, explains performance better than the spectral gap. It explicitly leaves non-i.i.d. data open. Our quantity is its direct extension to temporally colored noise.
- Collapse with many clients. Which mode is better for federated learning? Centralized or Decentralized finds that sparse decentralized learning suffers a performance collapse as the client count grows unless connectivity scales appropriately.
- Generalization of asynchronous gossip. Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD bounds the generalization error of asynchronous decentralized SGD through the second eigenvalue.
None of these models temporal dependence. We expect it to shift the collapse threshold.
On the dependent-data side, Sharper Bounds for Uniformly Stable Algorithms with Stationary Mixing Process obtains optimal-rate generalization bounds for stable algorithms on mixing sequences, extending Stability Bound for Stationary Phi-mixing and Beta-mixing Processes. Both are single-machine results, and we reuse their buffer-zone decoupling technique. Space-Time Graph Neural Networks supplies the space-time shift operator and integral Lipschitz stability proofs. However, it trains centrally by imitation, and its proofs assume a static graph. We apply the space-time view to the optimizer's own communication rather than to a predictive model.
Deep unfolding, meaning turning iterations of an algorithm into trainable layers, supplies the learning method. Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation shows that unrolled graph operators transfer from 20 to 30 transceiver pairs. Improving Federated Aggregation with Deep Unfolding Networks learns aggregation weights, but at a central server. We unfold gossip itself, fully peer-to-peer. Size transfer is supported by the graphon results of A graphon-signal analysis of graph neural networks and Ruiz et al.: filters with size-independent coefficients and normalized aggregation converge to a limit object as graphs grow.
Research Program
The work has three parts.
Analysis. We derive $\mathcal{E}(h)$ rigorously for strongly convex quadratics with stationary, linearly generated noise. We then extend it to a generalization bound by combining the topology-dependent stability argument of Deng et al. with the buffer-zone decoupling of Fu et al. The target is a bound in which the effective sample size is jointly discounted by mixing time and by the filter's response on low graph frequencies. We will state honestly where the non-convex case remains empirical, as it does in Vogels et al.
Learned filters. We learn the coefficients $a_k$ by unrolling $T$ steps of decentralized SGD on small graphs (16 to 32 nodes). The objective is final consensus-model loss. Two constraints are imposed:
- a fixed communication budget of $K$ exchanges per step;
- an integral Lipschitz penalty on $h'(\lambda)$, following Gama et al.
We train two variants. The temporally blind variant is trained on i.i.d. noise. The temporally aware variant is trained on streams with a given mixing time and, optionally, conditions $a_k$ on a cheap local autocorrelation estimate.
Stability under change. We prove that, under relative edge perturbations of size $\epsilon$, the change in $\mathcal{E}$ is $O(L\epsilon)$ per gossip layer. The proof transfers Gama's operator bound through the error recursion. We then test whether this survives time-varying graphs, which is the gap left by the ST-GNN proofs.
Baselines
Naive reference. Decentralized SGD with Metropolis gossip weights and one exchange per step, as analyzed by Xiangru Lian et al.. A centralized SGD run serves as an upper reference.
Strongest existing competitor. Decentralized SGD with $K$ repeated gossip exchanges or a Chebyshev-accelerated polynomial of the same degree. This is the strongest competitor because it is exactly a hand-designed filter in our class with the same communication cost, so any gain must come from adapting to $\Phi$ rather than from more communication. The file contains no paper for Chebyshev gossip, so we implement it from its standard definition with the spectral gap supplied exactly. That gives it an advantage our method lacks.
Other competitors.
- Gradient tracking, as in Kun Yuan et al., which is known to be topology-sensitive.
- Epidemic Learning: Boosting Decentralized Learning with Randomized Communication. We run it both with all-to-all routing, its stated assumption, and restricted to physical neighbors.
- Fed-TREND from Tackling Data Heterogeneity in Federated Time Series Forecasting, as a server-assisted reference.
Fairness. All methods share data splits, model architecture, and vectors transmitted per node per step, and each gets an equal hyperparameter search budget over step size and schedule.
Reported numbers. No reported result was found on Lacuna for decentralized SGD or Chebyshev gossip on MOBINS or comparable networked streams. Fed-TREND is reported to beat centralized training on 6 of 8 forecasting datasets, but the file gives no metric values. We therefore establish all baseline numbers ourselves.
What counts as beating them. Lower test error at matched communication on slowly mixing streams, with no loss on i.i.d. streams, and transfer to graphs eight or more times larger without retraining.
Ablations. Three ablations isolate the key ingredients:
- the unconstrained learned filter, which isolates the integral Lipschitz constraint and should match it on the training graph but degrade more under link drops;
- the temporally blind filter, which isolates the temporal awareness and should match it on i.i.d. data but lose on slow streams;
- filters trained directly on the large test graph, which provides a transfer ceiling.
Why not just…?
Why not just shuffle a local replay buffer to break temporal correlation? This is the most serious threat. A buffer much longer than the mixing time does restore near-i.i.d. sampling. It costs memory proportional to the mixing time, and under drift it trains on stale data. We include buffers of several sizes at matched memory. If a modest buffer erases the sparse-topology penalty on MOBINS, then the core claim holds only for memory-constrained or nonstationary nodes, and we will report it that way.
Why not just use more gossip rounds or Chebyshev acceleration? These are fixed filters chosen from the graph spectrum alone. Our analysis says the optimal filter also depends on $\Phi$. The temporally aware versus Chebyshev comparison at equal $K$ settles whether that dependence matters in practice. A null result would still validate $\mathcal{E}$ as a predictor while showing that learning adds nothing.
Why not just randomize peers, as Epidemic Learning does? Random peers make the effective graph an expander, which helps. But they require arbitrary routing, which the file notes fails under physical edge constraints. Multi-hop routing of random pairs consumes the same communication budget we give to $K$ exchanges, and the neighbor-restricted run tests exactly this.
Why not just use the i.i.d. effective number of neighbors? We test it as a predictor. If its rank correlation with measured error equals ours across mixing regimes, the temporal extension is unnecessary.
Proposed Experiments
Synthetic grid experiment. Nodes observe vector autoregressive streams with controlled mixing time, including the non-white linear dynamics of Efficient and passive learning of networked dynamical systems driven by non-white exogenous inputs. We sweep a grid of topology (ring, torus, random geometric, exponential, complete) by mixing time by node count from 16 to 1024. The decisive check is a Spearman correlation between measured error and three predictors: spectral gap, i.i.d. effective neighbors, and $\mathcal{E}(h)$. The core claim predicts that only $\mathcal{E}(h)$ stays well correlated as mixing time grows, and that the sparse-versus-dense gap widens with mixing time.
Real-data experiment. Forecasting on the transportation and epidemic networks of Mobility Networked Time-Series Forecasting Benchmark Datasets. Each region is a learning node, the physical adjacency is the communication graph, and we report mean absolute error at matched communication.
Transfer and robustness. Filters trained on 16-node graphs are deployed on 256 and 1024 nodes, with random link drops at rate $\epsilon$ and with time-varying graphs. The theory predicts error degradation roughly linear in $\epsilon$ for the constrained filter and visibly faster for the unconstrained one.
Generalization test. On streams of fixed length, we compare the test-train gap against the combined mixing-and-topology bound. The question is whether the gap moves with mixing time and spectral response in the predicted directions, even if constants are loose.
References
- Stability of Graph Neural Networks to Relative Perturbations
- Distributed Dual Averaging In Networks
- A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
- Beyond spectral gap: the role of the topology in decentralized learning
- Which mode is better for federated learning? Centralized or Decentralized
- Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD
- Sharper Bounds for Uniformly Stable Algorithms with Stationary Mixing Process
- Stability Bound for Stationary Phi-mixing and Beta-mixing Processes
- Space-Time Graph Neural Networks
- Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation
- Improving Federated Aggregation with Deep Unfolding Networks
- A graphon-signal analysis of graph neural networks
- Graphon Neural Networks and the Transferability of Graph Neural Networks
- Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
- Epidemic Learning: Boosting Decentralized Learning with Randomized Communication
- Tackling Data Heterogeneity in Federated Time Series Forecasting
- Efficient and passive learning of networked dynamical systems driven by non-white exogenous inputs
- Mobility Networked Time-Series Forecasting Benchmark Datasets