Most distributed machine learning systems nowadays, including TensorFlow and
CNTK, are built in a centralized fashion. One bottleneck of centralized
algorithms lies on high communication cost on the central node. Motivated by
this, we ask, can decentralized algorithms be faster than its centralized
counterpart?
Although decentralized PSGD (D-PSGD) algorithms have been studied by the
control community, existing analysis and theory do not show any advantage over
centralized PSGD (C-PSGD) algorithms, simply assuming the application scenario
where only the decentralized network is available. In this paper, we study a
D-PSGD algorithm and provide the first theoretical analysis that indicates a
regime in which decentralized algorithms might outperform centralized
algorithms for distributed stochastic gradient descent. This is because D-PSGD
has comparable total computational complexities to C-PSGD but requires much
less communication cost on the busiest node. We further conduct an empirical
study to validate our theoretical analysis across multiple frameworks (CNTK and
Torch), different network configurations, and computation platforms up to 112
GPUs. On network configurations with low bandwidth or high latency, D-PSGD can
be up to one order of magnitude faster than its well-optimized centralized
counterparts.

本文研究了去中心化 PSGD 算法的理论复杂度，表明相比于其优化的集中式对应物，去中心化算法在低带宽或高延迟网络配置中可以快上一个数量级，并且需要更少的通信成本。