Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters
Abstract
This paper addresses the problem of designing distributed optimization algorithms. Different to existing methods that usually give sufficient conditions and conservative convergence rates, we propose a framework for determining the exact worst-case convergence rate. The worst-case convergence is defined over the set of μ-strongly convex and L-Lipschitz objective functions and the set of connected graphs with given algebraic connectivity. Focusing on the Distributed Inexact Gradient Tracking (DIGing)--an algorithm widely deployed in applications and extensively studied in recent years, we develop a systematic design methodology by integrating techniques from graph signal processing and robust control theory. First, we present a novel decomposition structure that enables partial subsystem decoupling. Then we derive explicit formulas for the exact worst-case convergence rate and the corresponding parameters. Numerical experiments validate the correctness and effectiveness of our theoretical results.
Related
- Linear convergence rate analysis of Proximal-Tracking for nonsmooth distributed optimization
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- Distributed Cross-Layer Optimization for Covert Multi-Hop, Multi-Modal Networks: Exponentially Fast Convergence and Robust Tracking
- Average Energy Dissipation Rates of Implicit-Explicit Runge-Kutta Methods for Gradient Flow Problems
- Gradient Growth for Vlasov-Poisson in background charge distributed by Desingularized Dirac Delta
BibTeX
@misc{tian2026optimal,
title = {{Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters}},
author = {Qiuchen Tian and Li Chai and Jinming Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20265},
eprint = {2609.20265},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20265},
}
RIS
TY - UNPB
TI - Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters
AU - Qiuchen Tian
AU - Li Chai
AU - Jinming Xu
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20265
UR - https://arxiv.org/abs/2609.20265
AB - This paper addresses the problem of designing distributed optimization algorithms. Different to existing methods that usually give sufficient conditions and conservative convergence rates, we propose a framework for determining the exact worst-case convergence rate. The worst-case convergence is defined over the set of μ-strongly convex and L-Lipschitz objective functions and the set of connected graphs with given algebraic connectivity. Focusing on the Distributed Inexact Gradient Tracking (DIGing)--an algorithm widely deployed in applications and extensively studied in recent years, we develop a systematic design methodology by integrating techniques from graph signal processing and robust control theory. First, we present a novel decomposition structure that enables partial subsystem decoupling. Then we derive explicit formulas for the exact worst-case convergence rate and the corresponding parameters. Numerical experiments validate the correctness and effectiveness of our theoretical results.
ER -