Abstract
In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of applications---distributed estimation in sensor networks, fitting models to massive data sets, and distributed control of multi-robot systems, to name a few---significant advances have been made towards the development of robust, practical algorithms with theoretical performance guarantees. This paper presents an overview of recent work in this area. In general, rates of convergence depend not only on the number of nodes involved and the desired level of accuracy, but also on the structure and nature of the network over which nodes communicate (e.g., whether links are directed or undirected, static or time-varying). We survey the state-of-the-art algorithms and their analyses tailored to these different scenarios, highlighting the role of the network topology.
Introduction
In traditional centralized optimization, a single master node collects data from all agents, computes a gradient, and sends updates back. While straightforward, this creates a massive communication bottleneck and a single point of failure. Decentralized optimization addresses these issues by allowing agents to communicate only with their immediate neighbors. However, this introduces a "network penalty" where the speed of reaching a global solution is limited by the efficiency of information diffusion through the specific graph structure.
Problem Formulation and Network Topologies
The core challenge in decentralized optimization is quantifying the tradeoff between local computation (calculating gradients) and global communication (averaging values with neighbors). The efficiency of this process is heavily dependent on the network's connectivity.
The survey evaluates performance across various graph topologies, which serve as benchmarks for the field:
- Path/Cycle Graphs: Characterized by highly restrictive, linear connectivity.
- 2D Grids and Tori: Common in physical sensor deployments.
- Star Graphs: One central hub with many leaves, simulating a master-worker setup.
- Expander Graphs: Sparse but highly connected graphs that are mathematically optimal for fast information spread.
- Random Graphs: Such as Erdős-Rényi and Geometric random graphs, which model ad-hoc wireless networks.
Algorithmic Frameworks
Several foundational and state-of-the-art algorithmic frameworks are surveyed:
- Decentralized Subgradient Method: Nodes perform a local gradient step and average results with neighbors.
- Metropolis-Hastings Weighting: A method for assigning weights in undirected graphs to ensure correct average consensus.
- Push-Sum Algorithm: Essential for directed graphs where communication may be one-way. It uses a ratio of two running sums to track information "mass."
- EXTRA and Gradient Tracking: "Second-generation" algorithms that achieve geometric convergence for strongly convex problems by tracking gradient history to cancel steady-state errors.
Key Insights and Scaling Laws
The paper provides concrete scaling laws for convergence time to reach $\epsilon$-accuracy:
- The Spectral Gap: The second-largest eigenvalue of the communication matrix determines speed. Graphs with more bottlenecks (like long paths) converge slower.
- Price of Decentralization: For general convex functions, decentralized methods match the $O(1/\sqrt{T})$ rate of centralized methods, but with an error constant scaled by network connectivity.
- Topology-Specific Scaling:
- Complete Graphs: Convergence is $O(1)$ relative to $n$, behaving like centralized systems.
- Expander Graphs: Highly efficient, scaling with $O(\log(1/\epsilon))$.
- Path Graphs: The worst case, scaling quadratically with the number of nodes ($O(n^2)$).
Limitations and Future Directions
While significant progress has been made, several challenges remain:
- Asynchrony and Delays: Most rigorous bounds assume synchronization, which is difficult to maintain in massive real-world networks.
- Communication Efficiency: There is a need for methods where agents perform multiple local steps before communicating to reduce overhead.
- Non-Convexity: Most current theory focuses on convex optimization. Extending these guarantees to non-convex deep learning is a major frontier.
Summary updated