C-DIEGO: An Algorithm with Near-Optimal Sample Complexity for Distributed, Streaming PCA
C-DIEGO: An Algorithm with Near-Optimal Sample Complexity for Distributed, Streaming PCA
复制标题
DOI：
10.1109/ciss56502.2023.10089668
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Muhammad Zulqarnain;Arpita Gang;W. Bajwa
中科院分区：
文献类型：
--
作者：
Muhammad Zulqarnain;Arpita Gang;W. Bajwa
许多下游机器学习算法的准确性与具有不相关特征的训练数据有关。由于现代数据通常在本质上是流式的，地理上是分布式的，并且具有很大的维度，因此在这种情况下应用不相关的特征学习和降维技术是至关重要的。主成分分析（PCA）是一种最先进的工具，通过将数据投影到总体协方差矩阵的特征向量上，同时产生不相关的特征并降低数据维度。本文介绍了一种新的算法，称为C-DIEGO的广义Oja（C-DIEGO），这是基于Oja的方法，估计分布，流设置中的人口协方差矩阵的主特征向量。该算法考虑了一个分布式网络的任意连接的节点没有一个中央协调员，并假设数据样本连续到达各个节点的流式方式。本文证明了如果网络中的节点在每次算法迭代中有足够的共识轮数，C-DIEGO可以达到阶最优的收敛速度。数值结果也报告中的文件，展示了所提出的算法的有效性。
The accuracy of many downstream machine learning algorithms is tied to the training data having uncorrelated features. With the modern-day data often being streaming in nature, geographically distributed, and having large dimensions, it is paramount to apply both uncorrelated feature learning and dimensionality reduction techniques in this scenario. Principal Component Analysis (PCA) is a state-of-the-art tool that simultaneously yields uncorrelated features and reduces data dimensions by projecting data onto the eigenvectors of the population covariance matrix. This paper introduces a novel algorithm called Consensus-DIstributEd Generalized Oja (C-DIEGO), which is based on Oja's method, to estimate the dominant eigenvector of a population covariance matrix in a distributed, streaming setting. The algorithm considers a distributed network of arbitrarily connected nodes without a central coordinator and assumes data samples continuously arrive at the individual nodes in a streaming manner. It is established in the paper that C-DIEGO can achieve an order-optimal convergence rate if nodes in the network are allowed to have enough consensus rounds per algorithmic iteration. Numerical results are also reported in the paper that showcase the efficacy of the proposed algorithm.