In this work, we consider the decentralized optimization problem in which a network of $n$ agents, each possessing a smooth and convex objective function, wish to collaboratively minimize the average of all the objective functions through peer-to-peer communication in a directed graph. To solve the problem, we propose two accelerated Push-DIGing methods termed APD and APD-SC for minimizing non-strongly convex objective functions and strongly convex ones, respectively. We show that APD and APD-SC respectively converge at the rates $O\left(\frac{1}{k^2}\right)$ and $O\left(\left(1 - C\sqrt{\frac{\mu}{L}}\right)^k\right)$ up to constant factors depending only on the mixing matrix. To the best of our knowledge, APD and APD-SC are the first decentralized methods to achieve provable acceleration over unbalanced directed graphs. Numerical experiments demonstrate the effectiveness of both methods.

翻译：在这项工作中,我们考虑了分散式优化问题,即一个由美元代理商组成的网络,每个代理商都拥有平稳和平稳的目标功能,希望通过一个定向图表,通过对等对等通信将所有目标功能的平均值最小化。为了解决问题,我们建议了两种加速推进DIGing方法,即APD和APD-SC,分别用于尽量减少非强烈对等客观功能和强烈对流功能。我们表明APD和APD-SC分别以美元对齐(fleft) (fraft) (1-C\qrt\k ⁇ k ⁇ 2 ⁇ right) 和 $Oleft(left(1 - C\sqrt\frac\\\\\\lä\\\\\\\\lä\\\\\right) 和 right) 等利率趋同于恒定因素,但仅取决于混合矩阵。据我们所知,APD和APD-SC是第一个在不平衡定向图形上实现可预见加速度加速的分散化方法。Nucal 实验证明了这两种方法的有效性。