Decentralized Optimization via Consensus and Double Averaging

This direction is merged into another direction: topology-dependent convergence. Its last version stays readable and citable here.

Version 1 of 117 papers17 conceptsfrozen 2026-10-04

In traditional distributed learning, a central parameter server acts as a conductor, collecting gradients from workers and broadcasting updated models. While simple, this "hub-and-spoke" architecture creates communication bottlenecks and single points of failure. The research direction of decentralized optimization removes the conductor entirely. Instead, agents occupy a graph where they only communicate with their immediate neighbors.

The challenge is intuitive: how can a collection of agents reach a global consensus on an optimal model when no single agent sees the whole picture?

The Core Mechanism: Consensus through Local Averaging

The fundamental building block of these algorithms is the consensus step. At each iteration, an agent performs two tasks: it updates its local model based on its own data, and it "mixes" its model with those of its neighbors.

As Alejandro Ribeiro and Aryan Mokhtari demonstrate in DSA: Decentralized Double Stochastic Averaging Gradient Algorithm, this mixing acts as a communication-driven regularizer. By repeatedly averaging local parameters, information propagates through the network like a dye diffusing in water. Eventually, the local estimates converge to a single global value.

However, simple averaging is often slow. To achieve the "gold standard" of linear convergence—where the error drops exponentially—researchers have introduced Double Averaging.

Why Double Averaging Works

The "Double" in Double Averaging refers to tracking two distinct quantities simultaneously:

  1. Spatial Averaging: Reaching consensus across the network (the "space" of agents).
  2. Temporal Averaging: Reducing the variance of stochastic gradients over time.

In stochastic optimization, the "noise" from sampling small batches of data prevents agents from finding the exact optimum. Hoi To Wai, Zhuoran Yang, and Mingyi Hong apply this to reinforcement learning in Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization. By maintaining a running average of historical gradients (variance reduction) while simultaneously averaging parameters with neighbors (consensus), agents can cancel out local noise and move toward the global solution as if they had access to the entire dataset.

The Topology Bottleneck

A recurring theme across this literature is that the network topology is the primary determinant of speed. The "spectral gap" of the graph—a measure of how well-connected the nodes are—dictates how many communication rounds are needed for a local update to "reach" the rest of the network.

Beyond Simple Minimization

This decentralized framework is remarkably versatile, extending far beyond standard supervised learning:

  • Saddle Point Problems: For training GANs or robust models, Weijie Liu and Asuman E. Ozdaglar developed DPPSP, which uses a proximal point method to stabilize the "push-and-pull" between competing objectives in a decentralized setting.
  • Optimal Transport: Cesar A Uribe and Angelia Nedich demonstrated in Distributed Computation of Wasserstein Barycenters Over Networks that agents can find the "average" of probability distributions (barycenters) by communicating dual variables, achieving an optimal $O(1/k^2)$ convergence rate.
  • Feature Partitioning: While most methods assume data is split by samples, Cristiano Gratton and colleagues explored Decentralized Optimization with Distributed Features, where different agents hold different attributes of the same data points, using dual-domain consensus to solve non-smooth problems like Elastic-Net.

By combining local computation with clever spatial and temporal averaging, these algorithms prove that a central controller is not a requirement for global intelligence, but rather a design choice that can be bypassed for better scalability and privacy.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_decentralized_optimization_via_consensus_0e7a927f,
  title = {Decentralized Optimization via Consensus and Double Averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-optimization-via-consensus-and-double-averaging/rdr_0e7a927f4c954feda4909609c40dc00d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_decentralized_optimization_via_consensus_0e7a927f_v1,
  title = {Decentralized Optimization via Consensus and Double Averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-optimization-via-consensus-and-double-averaging/rdr_0e7a927f4c954feda4909609c40dc00d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}