Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm

Liyuan Liang, Xinmeng Huang, Ran Xin +1

This paper investigates the influence of directed networks on decentralized stochastic non-convex optimization associated with column-stochastic mixing matrices. Surprisingly, we f…