DISTRIBUTED GRADIENT TRACKING ACHIEVING THE OPTIMAL WORST-CASE CONVERGENCE RATE OF CENTRALIZED GRADIENT DESCENT: NECESSARY AND SUFFICIENT CONDITIONS AND BEYOND

This paper characterizes the optimal worst-case convergence rate of distributed gradient tracking, revealing its explicit dependence on both the objective functions and the communication network topology. We consider a modified version of the DIGing algorithm that incorporates the adapt-then-combine (ATC) strategy. In the algorithm, a parameter is set to tune the self-loop gain. For $\mu$-strongly convex and $L$-smooth objective functions, we show that $2\varrho (\sqrt{\varrho }+1)/(3\varrho +1)$ is a threshold in the network topology that governs the worst-case convergence performance of the proposed DIGing-ATC algorithm, where $\varrho =L/\mu$. We prove that the algorithm can achieve the optimal worst-case convergence rate $(\varrho -1)/(\varrho +1)$ of centralized gradient descent (CGD) if and only if $\beta /\alpha \le 2\varrho (\sqrt{\varrho }+1)/(3\varrho +1)$, where $\alpha$ and $\beta$ are the smallest nonzero eigenvalue and the largest eigenvalue of the graph Laplacian matrix, respectively. We provide explicit formulas for the corresponding optimal parameters. For connected networks with $\beta /\alpha >2\varrho (\sqrt{\varrho }+1)/(3\varrho +1)$, the optimal rate of CGD can never be reached. In this case, we further show that the achievable optimal worst-case convergence rate can be characterized as a root of a nonlinear equation depending only on $\varrho$ and $\beta /\alpha$, which can be computed efficiently using a bisection method. Our derivations and proofs employ nontrivial techniques, including the small gain theorem, Routh stability criteria, and analytic solutions of inequality-constrained optimization. Simulation results are presented to validate the theoretical convergence rates and demonstrate the practical effectiveness of the proposed algorithm.