Accelerating Convergence in Decentralized Optimization

100 concepts101 papers2 proposals

In decentralized optimization, a network of agents seeks to minimize a global objective function—often a sum of local cost functions—without a central coordinator. While this architecture offers privacy and robustness, it introduces a fundamental performance penalty. Agents must not only optimize their local models but also reach a consensus with their neighbors, a dual requirement that frequently leads to slow, sublinear convergence rates.

The Consensus Penalty and Subgradient Limitations

The primary bottleneck in decentralized systems is the "consensus penalty." In a centralized setting, a single processor has immediate access to all data. In a decentralized network, information must diffuse through the topology. Ghosh 0001 et al. demonstrate that even when networks self-tune their communication weights using decentralized subgradient methods, the convergence speed in terms of iteration count remains inherently slow.

This slowness is often tied to the reliance on first-order subgradient methods. As David Mateos‐Núñez notes, these methods typically exhibit a convergence rate of $O(1/\sqrt{t})$, which is significantly slower than the accelerated or second-order techniques used in centralized optimization. This rate is theoretically optimal for general subgradient descent but becomes a practical liability in time-sensitive applications like robotics or power grid management, where Emil Klintberg argues that rapid solutions are essential.

The Stability-Speed Trade-off

A recurring challenge in decentralized optimization is the choice of step size. To ensure that agents eventually reach an exact consensus, especially over dynamic or directed networks, many traditional algorithms employ diminishing step sizes. However, Nedic et al. and Jiang et al. point out that this approach forces the algorithm into a sublinear convergence regime.

To bypass this, researchers have introduced mechanisms like integral feedback. Shahrampour et al. show that by adding a "memory" of past disagreements, agents can achieve exact consensus using constant step sizes, which significantly improves the optimization velocity compared to diminishing-step methods.

Bridging the Gap to Linear Convergence

The transition from sublinear to linear (geometric) convergence is a major focus for improving decentralized efficiency. Several strategies have emerged to achieve this:

  • Variance Reduction: Stochastic decentralized methods were historically limited by gradient noise. Ribeiro et al. introduced DSA, the first stochastic decentralized method to achieve linear convergence by bridging the gap between stochastic efficiency and deterministic speed. More recently, Peng et al. achieved linear convergence in Byzantine-robust settings by integrating variance reduction techniques like SAGA.
  • Gradient Tracking and Surrogation: Algorithms like SONATA, proposed by Sun 0003 et al., use surrogate functions and gradient tracking to allow for more sophisticated local updates, accelerating convergence particularly when agent data is similar.
  • Primal-Dual Methods: By framing the consensus requirement as a constraint, researchers use primal-dual strategies to reach the optimum faster. Sayed et al. demonstrated that their PED² strategy achieves linear convergence even for non-smooth global coupling functions.

Momentum and Second-Order Acceleration

In centralized optimization, Nesterov’s acceleration and the "heavy-ball" method are standard for speeding up convergence. Bringing these to decentralized networks requires careful discretization of the underlying dynamical systems. Zhang et al. derived a decentralized algorithm by discretizing the heavy-ball ODE, achieving accelerated rates for strongly convex problems. Similarly, Annie I. Chen combined Nesterov-type acceleration with a multi-step consensus stage to reach an $O(1/t)$ rate, a significant jump over the standard $O(1/\sqrt{t})$.

For even higher performance, second-order methods exploit the curvature of the objective function. Emil Klintberg discovered that the Hessian of the dual function in many multi-agent problems is "numerically banded." By exploiting this structure, one can achieve near-quadratic convergence speeds, drastically reducing the communication rounds required compared to first-order methods.

Scaling and Communication Efficiency

Finally, the way updates are aggregated affects convergence. Ma et al. observed that traditional averaging dilutes the contribution of individual workers as the cluster size grows. Their COCOA+ framework allows machines to "add" updates instead, enabling "strong scaling" where convergence speed does not degrade with the addition of more machines. This is complemented by work on communication compression; the authors of a recent study on compressed communication showed that linear convergence can be maintained even when messages are heavily quantized, effectively providing communication efficiency "for free" without sacrificing the total number of rounds.

Key Foundational Work

Gossip algorithms: design, analysis and applications (2005) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_slow_convergence_in_decentralized_optimi_1a1fb1e5,
  title = {slow convergence in decentralized optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/slow-convergence-in-decentralized-optimization/rdr_1a1fb1e507ea4cfd9df79882e41cfad0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_slow_convergence_in_decentralized_optimi_1a1fb1e5_v1,
  title = {slow convergence in decentralized optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/slow-convergence-in-decentralized-optimization/rdr_1a1fb1e507ea4cfd9df79882e41cfad0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake