  Decentralized optimization over time-varying graphs has been increasingly
common in modern machine learning with massive data stored on millions of
mobile devices, such as in federated learning. This paper revisits and extends
the widely used accelerated gradient tracking. We prove the $\cal
O(\frac{\gamma^2}{(1-\sigma_{\gamma})^2}\sqrt{\frac{L}{\epsilon}})$ and $\cal
O((\frac{\gamma}{1-\sigma_{\gamma}})^{1.5}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$
complexities for the practical single loop accelerated gradient tracking over
time-varying graphs when the problems are nonstrongly convex and strongly
convex, respectively, where $\gamma$ and $\sigma_{\gamma}$ are two common
constants charactering the network connectivity, $\epsilon$ is the desired
precision, and $L$ and $\mu$ are the smoothness and strong convexity constants,
respectively. Our complexities improve significantly on the ones of $\cal
O(\frac{1}{\epsilon^{5/7}})$ and $\cal
O((\frac{L}{\mu})^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon})$
proved in the original literature only for static graph. When combining with a
multiple consensus subroutine, the dependence on the network connectivity
constants can be further improved. When the network is time-invariant, our
complexities exactly match the lower bounds without hiding any poly-logarithmic
factor for both nonstrongly convex and strongly convex problems.
