Data-dependent bounds on network gradient descent

We study a consensus-based distributed stochastic gradient method for distributed optimization in a setting common for machine learning applications. Nodes in the network hold disjoint data and seek to optimize a common objective which decomposes into a sum of convex functions of individual data points. We show that the rate of convergence for this method involves the spectral properties of two matrices: the standard spectral gap of a weight matrix from the network topology and a new term depending on the spectral norm of the sample covariance matrix of the data. This result shows the benefit of datasets with small spectral norm. Extensions of the method can identify the impact of limited communication, increasing the number of nodes, and scaling with data set size.

我们研究一种基于共识的分布式随机梯度方法，用于机器学习应用中常见设置下的分布式优化。网络中的节点持有不相交的数据，并试图优化一个共同的目标，该目标可分解为各个数据点的凸函数之和。我们表明，这种方法的收敛速度涉及两个矩阵的谱特性：来自网络拓扑的权重矩阵的标准谱间隙，以及一个取决于数据样本协方差矩阵的谱范数的新项。这一结果显示了具有小谱范数的数据集的优势。该方法的扩展可以确定有限通信的影响、节点数量的增加以及随数据集大小的缩放情况。