Recent Theoretical Advances in Decentralized Distributed Convex Optimization

Eduard Gorbunov, Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, Alexander GasnikovSpringer Optimization and its Applications 2022 · DOI · arXiv · OpenAlex

This paper provides a high-level synthesis of the major breakthroughs in decentralized distributed convex optimization achieved between 2016 and 2021. It bridges the gap between classical centralized optimization and decentralized environments where nodes in a network must collaborate to solve a global problem using only local information and peer-to-peer communication.

Problem Formulation

In large-scale machine learning and sensor networks, the objective is often to solve a problem of the form: $$\min_{x} f(x) = \frac{1}{m} \sum_{i=1}^m f_i(x)$$ where each function $f_i$ is known only to a specific node $i$ in a network.

In a centralized setup, a master server coordinates with all nodes, which often creates a communication bottleneck. In a decentralized setup, nodes only communicate with their immediate neighbors. The challenge is to optimize two primary metrics:

  1. Oracle Complexity: The number of local gradients or function evaluations each node must compute.
  2. Communication Complexity: The number of message exchange rounds required to reach a consensus on the global solution.

Until recently, a significant gap existed between theoretical lower bounds (the mathematical "speed limits") and the performance of known decentralized algorithms. This survey explains the mechanisms behind the new generation of methods that have finally closed this gap.

Methodological Pillars

The authors categorize recent algorithms (such as EXTRA, DIGing, Mudag, and APAPC) by their reliance on several core mathematical techniques:

  • Consensus via Mixing: Utilizing Laplacian matrices and gossip protocols to ensure all nodes eventually converge on the same solution vector $x$.
  • Acceleration: Applying Nesterov’s or Chebyshev’s acceleration to enhance the speed of both the optimization steps and the consensus process.
  • Lan’s Sliding Algorithm: A critical technique that allows algorithms to "slide" between different scales. It enables performing multiple local gradient steps (computation) for every communication round, ensuring both complexities stay near-optimal.
  • The Penalty Trick: Reformulating the decentralized consensus constraint as a penalty term, effectively transforming a constrained problem into a composite smooth and non-smooth problem that is more tractable.
  • Dual Approaches: For problems that are non-smooth in the primal space (e.g., Wasserstein Barycenters), moving to the dual space often reveals a smooth, strongly convex structure suitable for fast, accelerated gradient methods.

Key Theoretical Results

The survey summarizes the current state-of-the-art performance across various function classes. A primary insight is the Communication-Computation Separation: by using "Sliding" techniques, researchers have decoupled these two costs, hitting the lower bounds for both simultaneously.

Complexity bounds for decentralized optimization across different function classes.

For smooth, strongly convex problems, the optimal communication complexity is established as $\tilde{O}(\sqrt{L/\mu} \chi)$, where $\chi$ represents the network's condition number (a measure of connectivity).

In stochastic settings, the paper highlights that the number of oracle calls per node can be reduced to $O(\sigma^2 / (m\mu\epsilon))$. This achieves a "linear speedup," where the computational workload is divided perfectly among the $m$ nodes in the network.

Complexity bounds for stochastic decentralized optimization showing linear speedup.

Limitations and Future Directions

While theoretical gaps have been closed for many convex scenarios, several frontiers remain:

  • Non-Convexity: Decentralized optimization for non-convex landscapes, such as those found in deep neural networks, lacks the same level of rigorous theoretical guarantees.
  • Directed Graphs: Most optimal results assume undirected (symmetric) communication. Extending these to directed graphs remains an active area of research.
  • Asynchrony: Real-world systems are often asynchronous, which adds significant complexity to consensus proofs compared to the synchronized rounds assumed in many of these theoretical models.
  • Hidden Constants: While the "Big-O" complexity is optimal, the hidden constants in accelerated methods can be large, meaning "theoretically slower" algorithms may still perform better in small-scale practical applications.

Summary updated

BibTeX
@inproceedings{gorbunov2022recent,
  author = {Eduard Gorbunov and Alexander Rogozin and Aleksandr Beznosikov and Darina Dvinskikh and Alexander Gasnikov},
  title = {{Recent Theoretical Advances in Decentralized Distributed Convex Optimization}},
  booktitle = {Springer Optimization and its Applications},
  year = {2022},
  doi = {10.1007/978-3-031-00832-0\_8},
}
Figure