In decentralized learning, a network of agents collaborates to train a model without a central coordinator. Each agent holds local data and only communicates with its immediate neighbors. While this architecture offers privacy and scalability, it introduces a fundamental tension: agents want to optimize their local models, but they also need to stay in sync with the rest of the network.
When agents prioritize local optimization over communication, they "drift" apart, leading to model inconsistency. To solve this, researchers have moved beyond simple one-to-one message passing toward Multi-Step and Accelerated Gossip—techniques that treat communication as an inner optimization loop to make sparse networks behave like fully connected ones.
The Consensus Bottleneck
The primary challenge in decentralized systems is the "consensus error." As Yifan Shi, Li Shen, and their colleagues note in Improving the Model Consistency of Decentralized Federated Learning, local models drift apart because of data heterogeneity (non-IID data) and sparse network connectivity.
If an agent performs many local gradient updates before talking to a neighbor, it moves deep into a local minimum that might be far from the global optimum. Standard decentralized stochastic gradient descent (DSGD) tries to fix this by averaging parameters with neighbors after every step. However, in large or sparse networks (like a ring or a line), information travels slowly. A "good" update from one side of the network might take hundreds of iterations to reach the other side.
Multi-Step Gossip: Talking More to Learn Faster
The most direct way to fix this bottleneck is to increase the frequency of communication relative to computation. This is known as Multi-Step Gossip (MGS) or multi-consensus.
Instead of one communication round per gradient update, algorithms like DFedSAM-MGS and NEAR-DGD perform $K$ rounds of gossip for every one gradient step. As Abolfazl Hashemi, sujay sanghavi, and Inderjit S Dhillon demonstrate in On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization, this approach effectively reduces the "error floor." By reaching a higher degree of consensus before the next optimization step, the network prevents the divergence that typically plagues decentralized systems.
Intuition suggests that more communication is always better, but it comes at a cost. However, Kun Yuan and colleagues show in Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization that multi-step gossip can actually simplify the algorithm. It can eliminate the need for "gradient tracking"—a memory-intensive technique used to correct local bias—because the repeated averaging is powerful enough to keep agents synchronized even in heterogeneous environments.
Accelerated Gossip: Momentum for Communication
If multi-step gossip is about "talking more," Accelerated Gossip is about "talking smarter." Just as momentum accelerates gradient descent by using the history of updates, accelerated gossip uses the history of messages to speed up the spread of information.
Standard gossip is a diffusion process, which is notoriously slow. To bypass this, researchers like Yucheng Lu and Christopher De Sa introduced DeTAG, which uses Chebyshev-accelerated gossip. This method uses a specific sequence of weighted averages that allows information to propagate across the network's diameter much faster than simple linear averaging.
The intuition here is mathematical: the convergence of gossip depends on the "spectral gap" of the network graph. Accelerated gossip protocols, as explored by Dmitry Kovalev and Peter Richtárik in Lower Bounds and Optimal Algorithms..., effectively "stretch" this gap, making a sparse network feel as well-connected as a dense one.
Other forms of acceleration include:
- Momentum-based Gossip: Cesar A Uribe and Mohammad Taha Toghani show in Scalable Average Consensus with Compressed Communications that adding a heavy-ball momentum term to the gossip step can transform the convergence rate's dependency on network size from quadratic to linear.
- Dual-Level Momentum: In Distributed Solution of Large-Scale Linear Systems..., Navid Azizan and Salman Avestimehr propose applying momentum at both the local worker level and the global aggregation level, achieving a square-root improvement in convergence speed.
Stability in Complex Landscapes
These high-frequency or accelerated communication strategies are not just for speed; they are often a requirement for stability in complex optimization tasks.
For example, when optimizing on non-convex manifolds (like the Stiefel manifold used in PCA), agents must stay within a "proximally smooth" region to ensure the math holds. Shixiang Chen and Mingyi Hong demonstrate in Decentralized Riemannian Gradient Descent... that multi-step consensus is critical here. It keeps agents tightly coupled so that the curvature of the manifold doesn't throw them into divergent directions.
Similarly, in directed graphs where communication is one-way, the network can become numerically unstable. Liyuan Liang and Kun Yuan found that increasing communication rounds suppresses the "consensus error" more aggressively than the "gradient noise" grows, allowing decentralized systems to achieve near-optimal complexity even on poorly connected directed topologies.
Summary of Intuition
If you think of decentralized optimization as a group of people trying to find the lowest point in a foggy mountain range while holding hands:
- Standard Gossip is like only checking in with your neighbor occasionally. If you walk too fast, you'll pull apart.
- Multi-Step Gossip is like stopping to talk for several minutes for every one step you take. You move slower per step, but you never lose your grip.
- Accelerated Gossip is like using a megaphone and a memory of where everyone was a minute ago to predict where they are now. It allows the person on the far left of the line to feel the movement of the person on the far right almost instantly.