Communication-efficient distributed eigenspace estimation
Communication-efficient distributed eigenspace estimation
复制标题
DOI：
10.1137/20m1364862
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Vasileios Charisopoulos;Austin R. Benson;Anil Damle
中科院分区：
文献类型：
--
作者：
Vasileios Charisopoulos;Austin R. Benson;Anil Damle
分布式计算是扩展机器学习和数据科学算法以处理大量数据的标准方法。在这种情况下，避免机器之间的通信对于实现高性能至关重要。避免通信的一种常见做法是在每台机器上计算局部解或参数估计，然后将结果联合收割机组合起来，而不是分散现有算法的计算;在许多凸优化问题中，即使是简单的局部解平均也可以很好地工作。然而，当局部解不唯一时，这些方案不起作用。谱方法是这些问题的集合，其中解是相关数据矩阵的前导不变子空间的正交基，其仅在旋转和反射之前是唯一的。在这里，我们开发了一个通信高效的分布式算法计算的领先不变子空间的数据矩阵。我们的算法使用了一种新的对齐方案，最大限度地减少了本地解决方案和参考解决方案之间的Procrustean距离，只需要一轮的通信。对于主成分分析（PCA）的重要情况下，我们表明，我们的算法实现了类似的错误率的集中估计。我们提出的数值实验证明了我们提出的算法的有效性，分布式PCA，以及其他问题的解决方案表现出旋转对称性，如节点嵌入的图形数据和频谱初始化的二次感知。
Distributed computing is a standard way to scale up machine learning and data science algorithms to process large amounts of data. In such settings, avoiding communication amongst machines is paramount for achieving high performance. Rather than distribute the computation of existing algorithms, a common practice for avoiding communication is to compute local solutions or parameter estimates on each machine and then combine the results; in many convex optimization problems, even simple averaging of local solutions can work well. However, these schemes do not work when the local solutions are not unique. Spectral methods are a collection of such problems, where solutions are orthonormal bases of the leading invariant subspace of an associated data matrix, which are only unique up to rotation and reflections. Here, we develop a communication-efficient distributed algorithm for computing the leading invariant subspace of a data matrix. Our algorithm uses a novel alignment scheme that minimizes the Procrustean distance between local solutions and a reference solution, and only requires a single round of communication. For the important case of principal component analysis (PCA), we show that our algorithm achieves a similar error rate to that of a centralized estimator. We present numerical experiments demonstrating the efficacy of our proposed algorithm for distributed PCA, as well as other problems where solutions exhibit rotational symmetry, such as node embeddings for graph data and spectral initialization for quadratic sensing.