Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
We study the fundamental problem of Principal Component Analysis in a statistical distributed setting in which each machine out of $m$ stores a sample of $n$ points sampled i.i.d. from a single unknown distribution. We study algorithms for estimating the leading principal component of the population covariance matrix that are both communication-efficient and achieve estimation error of the order of the centralized ERM solution that uses all $mn$ samples. On the negative side, we show that in contrast to results obtained for distributed estimation under convexity assumptions, for the PCA objective, simply averaging the local ERM solutions cannot guarantee error that is consistent with the centralized ERM. We show that this unfortunate phenomena can be remedied by performing a simple correction step which correlates between the individual solutions, and provides an estimator that is consistent with the centralized ERM for sufficiently-large $n$. We also introduce an iterative distributed algorithm that is applicable in any regime of $n$, which is based on distributed matrix-vector products. The algorithm gives significant acceleration in terms of communication rounds over previous distributed algorithms, in a wide regime of parameters.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
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 contempo…
Vocal Bursts Intensity PredictionCommunication Efficient Distributed Kernel Principal Component Analysis
Kernel Principal Component Analysis (KPCA) is a key machine learning algorithm for extracting nonlinear features from data. In the presence of a large volume of high dimensional data collected in a distributed fashion, i…
Improved Distributed Principal Component Analysis
We study the distributed computing setting in which there are multiple servers, each holding a set of points, who wish to compute functions on the union of their point sets. A key task in this setting is Principal Compon…
ClusteringComputational EfficiencyDistributed ComputingOptimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms
We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), …
regressionFAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis
Principal Component Analysis (PCA) is a fundamental data preprocessing tool in the world of machine learning. While PCA is often thought of as a dimensionality reduction method, the purpose of PCA is actually two-fold: d…
Dimensionality Reduction