Can Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization?

Kun Yuan, Wei Xu, Qing Ling

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:

  1. Diffusion (Primal): Agents perform a local gradient step and average results with neighbors.
  2. 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.

Comparison of tracking error bounds and algorithm selection based on drift scenarios.

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.

Tracking error of Diffusion vs. DGT on cyclic networks with varying sizes (n=5 and n=100).

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

Abstract

In this paper, we consider the decentralized dynamic optimization problem defined over a multi-agent network. Each agent possesses a time-varying local objective function, and all agents aim to collaboratively track the drifting global optimal solution that minimizes the summation of all local objective functions. The decentralized dynamic optimization problem can be solved by primal or primal-dual methods, and when the problem degenerates to be static, it has been proved in literature that primal-dual methods are superior to primal ones. This motivates us to ask: are primal-dual methods necessarily better than primal ones in decentralized dynamic optimization? To answer this question, we investigate, and compare convergence properties of the primal method, diffusion, and the primal-dual approach, decentralized gradient tracking (DGT). Theoretical analysis reveals that diffusion can outperform DGT in certain dynamic settings. We find that DGT, and diffusion are significantly affected by the drifts, and the magnitudes of optimal gradients, respectively. In addition, we show that DGT is more sensitive to the network topology, and a badly-connected network can greatly deteriorate its convergence performance. These conclusions provide guidelines on how to choose proper dynamic algorithms in various application scenarios. Numerical experiments are constructed to validate the theoretical analysis.
BibTeX
@article{yuan2020can,
  author = {Kun Yuan and Wei Xu and Qing Ling},
  title = {{Can Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization?}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  doi = {10.1109/tsp.2020.3011640},
}
Figure