# Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?

arXiv: https://arxiv.org/abs/2003.00816 · HTML: https://mlsanity.com/paper/2003.00816/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2020.

## Built on by (most cited first, 11 of 11)

- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharing](https://mlsanity.com/paper/2303.10695/) (2023)
- [Autonomy and Intelligence in the Computing Continuum: Challenges, Enablers, and Future Directions for Orchestration](https://mlsanity.com/paper/2205.01423/) (2022)
- [Understanding A Class of Decentralized and Federated Optimization Algorithms: A Multi-Rate Feedback Control Perspective](https://mlsanity.com/paper/2204.12663/) (2022)
- [Robust Online Learning over Networks](https://mlsanity.com/paper/2309.00520/) (2023)
- [Online Distributed Learning with Quantized Finite-Time Coordination](https://mlsanity.com/paper/2307.06620/) (2023)
- [Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting](https://mlsanity.com/paper/2605.06971/) (2026)
- [Learning-based primal-dual optimal control of discrete-time stochastic systems with multiplicative noise](https://mlsanity.com/paper/2506.02613/) (2025)
- [Distributed Optimization with Streaming Data: A Temporal Weighting Perspective](https://mlsanity.com/paper/2608.09565/) (2026)

## Abstract (arXiv)

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.