The distributed nonconvex optimization problem of minimizing a global cost
function formed by a sum of $n$ local cost functions by using local information
exchange is considered. This problem is an important component of many machine
learning techniques with data parallelism, such as deep learning and federated
learning. We propose a distributed primal--dual stochastic gradient descent
(SGD) algorithm, suitable for arbitrarily connected communication networks and
any smooth (possibly nonconvex) cost functions. We show that the proposed
algorithm achieves the linear speedup convergence rate
$\mathcal{O}(1/\sqrt{nT})$ for general nonconvex cost functions and the linear
speedup convergence rate $\mathcal{O}(1/(nT))$ when the global cost function
satisfies the Polyak--{\L}ojasiewicz (P--{\L}) condition, where $T$ is the
total number of iterations. We also show that the output of the proposed
algorithm with constant parameters linearly converges to a neighborhood of a
global optimum. We demonstrate through numerical experiments the efficiency of
our algorithm in comparison with the baseline centralized SGD and recently
proposed distributed SGD algorithms.

本文提出了一种适用于任意连接通信网络和任何光滑（可能是非凸的）代价函数的分布式原始 - 对偶随机梯度下降（SGD）算法，证明了该算法实现了常数参数的输出线性收敛到全局最优的邻域并展示了实验结果与基线集中式 SGD 和最近提出的分布式 SGD 算法的比较效率。