In the realm of networked optimization, a long-standing consensus has favored primal-dual methods for their ability to eliminate steady-state bias in static problems. However, recent research titled "Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?" challenges this assumption. The authors demonstrate that in dynamic environments—where the target is constantly moving—simpler primal approaches can often take the lead.
The Challenge of Decentralized Dynamic Optimization
Decentralized dynamic optimization involves a network of agents (e.g., sensors or robots) collaborating to track a moving target. Each agent possesses a time-varying local objective function, and the goal is to minimize the sum of these functions across the network in real-time.
In static optimization, primal-dual methods like Decentralized Gradient Tracking (DGT), EXTRA, or ADMM are considered superior to primal methods like Diffusion or Gradient Descent. Primal methods typically suffer from a "steady-state error" when using a constant step size, whereas primal-dual methods utilize auxiliary variables to cancel out local biases and achieve exact convergence. The critical question posed by this paper is whether this superiority persists when the optimization target is in flux.
Theoretical Comparison: Diffusion vs. DGT
The researchers conducted a head-to-head comparison between two representative algorithms:
- Diffusion (Primal): Agents perform a local gradient step and average results with neighbors.
- Decentralized Gradient Tracking (DGT, Primal-Dual): Agents maintain an estimate of the global gradient to cancel local biases.
The study focuses on the "steady-state tracking error," influenced by several key factors:
- Solution Drift ($\Delta_x$): The speed at which the optimal solution moves.
- Gradient Drift ($\Delta_g$): The rate of change of gradients at the optimal solution.
- Gradient Magnitude ($D$): The average magnitude of the optimal gradients.
- Network Connectivity ($\beta$): Represented by the spectral gap; a $\beta$ near 1 indicates poor connectivity.
Key Insights: The Bias-Drift Trade-off
The core finding is a fundamental trade-off between bias and drift. While DGT successfully removes error caused by gradient magnitude ($D$)—the primary advantage in static settings—it introduces a new error term related to gradient drift ($\Delta_g$).
Furthermore, DGT exhibits significantly higher sensitivity to network topology. The error term for solution drift in DGT is magnified by $\frac{1}{(1-\beta)^2}$, whereas in Diffusion, it is only $\frac{1}{1-\beta}$. On poorly connected networks, such as large rings, DGT's performance can degrade rapidly while Diffusion remains robust.
As summarized in the table above, the "better" algorithm is highly context-dependent. Diffusion is preferred when the target moves quickly or the network is sparse, while DGT may still excel if the target moves slowly and the network is well-connected.
Experimental Results
The theoretical findings were validated through synthetic experiments, including Dynamic Least-Squares and Dynamic Average Consensus across various network topologies.
Quantitative Findings: * Network Scaling: In scenarios where the solution moves along a circular path, Diffusion significantly outperformed DGT as the network size increased (making $\beta$ closer to 1). * Drift Dominance: When gradient drift ($\Delta_g$) exceeded gradient magnitude ($D$), Diffusion proved superior even on well-connected random networks. * Static-like Scenarios: DGT only outperformed Diffusion when gradient magnitude was the dominant error source—essentially when the problem behaved more like a static optimization task.
Conclusion and Future Directions
This research provides a clear taxonomy for algorithm selection in decentralized dynamic optimization. It highlights that the complexity of primal-dual methods can become a liability in rapidly changing environments or poorly connected networks. Future work may explore whether these insights extend to non-convex problems, such as training neural networks on moving data streams, and whether adaptive step-size strategies can mitigate DGT's sensitivity to network topology.
Summary updated