Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
This provides a solution for distributed systems where agents must collaborate efficiently over directed communication networks, representing a significant advance rather than an incremental improvement.
The paper tackles decentralized optimization over unbalanced directed graphs by proposing accelerated gradient tracking methods (APD and APD-SC) for convex and strongly convex functions, achieving convergence rates of O(1/k^2) and O((1 - C√(μ/L))^k) respectively, matching centralized acceleration.
We consider the decentralized optimization problem, where a network of $n$ agents aims to collaboratively minimize the average of their individual smooth and convex objective functions through peer-to-peer communication in a directed graph. To tackle this problem, we propose two accelerated gradient tracking methods, namely APD and APD-SC, for non-strongly convex and strongly convex objective functions, respectively. We show that APD and APD-SC converge at the rates $O\left(\frac{1}{k^2}\right)$ and $O\left(\left(1 - C\sqrt{\fracμ{L}}\right)^k\right)$, respectively, up to constant factors depending only on the mixing matrix. APD and APD-SC are the first decentralized methods over unbalanced directed graphs that achieve the same provable acceleration as centralized methods. Numerical experiments demonstrate the effectiveness of both methods.