Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs
Zhuoqing Song, Lei Shi, Shi Pu, Ming Yan · SIAM Journal on Optimization · 2024
Abstract. We consider the decentralized optimization problem, where a network of [Formula: see text] 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 Accelerated Push-DIGing (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 [Formula: see text] and [Formula: see text], 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.