Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization

Abstract

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 the widely used accelerated gradient tracking and extends it to time-varying graphs. We prove that the practical single loop accelerated gradient tracking needs $O((\frac{\gamma }{1-{\sigma }_{\gamma }}{)}^2\sqrt{\frac{L}{\epsilon }})$ and $O((\frac{\gamma }{1-{\sigma }_{\gamma }}{)}^{1.5}\sqrt{\frac{L}{\mu }}\log \frac{1}{\epsilon })$ iterations to reach an $\epsilon$-optimal solution 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, $L$ and $\mu$ are the smoothness and strong convexity constants, respectively, and one iteration corresponds to one gradient oracle call and one communication round. Our convergence rates improve significantly over the ones of $O(\frac{1}{{\epsilon }^{5/7}})$ and $O((\frac{L}{\mu }{)}^{5/7}\frac{1}{(1-\sigma {)}^{1.5}}\log \frac{1}{\epsilon })$, respectively, which were proved in the original literature of accelerated gradient tracking only for static graphs, where $\frac{\gamma }{1-{\sigma }_{\gamma }}$ equals $\frac{1}{1-\sigma }$ when the network is time-invariant. When combining with a multiple consensus subroutine, the dependence on the network connectivity constants can be further improved to $O(1)$ and $O(\frac{\gamma }{1-{\sigma }_{\gamma }})$ for the gradient oracle and communication round complexities, respectively. When the network is static, by employing the Chebyshev acceleration, our complexities exactly match the lower bounds without hiding any poly-logarithmic factor for both nonstrongly convex and strongly convex problems.

Correct one typo in Algorithm 1: ${\mathcal{N}}_{(i)}$ -> ${\mathcal{N}}_{(i)}^k$

References in corpus (12)

• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• Multi-consensus Decentralized Accelerated Gradient Descent
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
• Decentralized Optimization On Time-Varying Directed Graphs Under Communication Constraints

Cited by in corpus (5)

• Recent theoretical advances in decentralized distributed convex optimization
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
• Optimal Gradient Tracking for Decentralized Optimization