Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
复制标题
DOI：
--
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Haroon Raja;W. Bajwa
中科院分区：
文献类型：
--
作者：
Haroon Raja;W. Bajwa
本文研究了在流环境下由独立的、同分布的数据样本估计协方差矩阵的主特征向量的问题。在许多当代应用中，数据的流速率可能很高，以至于单个处理器无法在新样本到达之前完成现有特征向量估计方法的迭代。本文提出并分析了经典Krasulina方法的一种分布式变体（D-Krasulina），该方法通过在多个处理节点上分配计算负载来跟上高数据流速率。分析表明，在适当的条件下，D-Krasulina以有序最优的方式收敛于主特征向量；即在所有节点上接收到$M$样本后，其估计误差可为$O(1/M)$。为了减少网络通信开销，本文还开发和分析了D-Krasulina的一个小批量扩展，称为DM-Krasulina。对DM-Krasulina的分析表明，在适当的条件下，即使由于通信延迟而不得不丢弃网络中的一些样本，DM-Krasulina也可以实现有序最优估计错误率。最后，在合成数据和实际数据上进行了实验，以验证D-Krasulina和DM-Krasulina在高速率流设置下的收敛行为。
This paper considers the problem of estimating the principal eigenvector of a covariance matrix from independent and identically distributed data samples in streaming settings. The streaming rate of data in many contemporary applications can be high enough that a single processor cannot finish an iteration of existing methods for eigenvector estimation before a new sample arrives. This paper formulates and analyzes a distributed variant of the classical Krasulina's method (D-Krasulina) that can keep up with the high streaming rate of data by distributing the computational load across multiple processing nodes. The analysis shows that---under appropriate conditions---D-Krasulina converges to the principal eigenvector in an order-wise optimal manner; i.e., after receiving $M$ samples across all nodes, its estimation error can be $O(1/M)$. In order to reduce the network communication overhead, the paper also develops and analyzes a mini-batch extension of D-Krasulina, which is termed DM-Krasulina. The analysis of DM-Krasulina shows that it can also achieve order-optimal estimation error rates under appropriate conditions, even when some samples have to be discarded within the network due to communication latency. Finally, experiments are performed over synthetic and real-world data to validate the convergence behaviors of D-Krasulina and DM-Krasulina in high-rate streaming settings.