Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs
针对有向图上的分布式优化问题，提出了两种加速梯度跟踪方法APD和APD-SC，分别适用于非强凸和强凸目标函数，收敛速度与集中式方法相当，数值实验验证了有效性。
.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 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 \(O({\frac{1}{k^2}})\) and \(O({({1 - C\sqrt{\frac{\mu }{L}}})^k})\), 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.Keywordsdecentralized optimizationNesterov's accelerated gradientdirected graphMSC codes90C2590C30