Improved Distributed Principal Component Analysis

By Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, David P. Woodruff. 2014

158 citations recorded by the source corpus.

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 Component Analysis (PCA), in which the servers would like to compute a low dimensional subspace capturing as much of the variance of the union of their point sets as possible. Given a procedure for approximate PCA, one can use it to approximately solve problems such as k-means clustering and low rank approximation. The essential properties of an approximate distributed PCA algorithm are its communication cost and computational efficiency for a given desired accuracy in downstream applications. We give new algorithms and analyses for distributed PCA which lead to improved communication and computational costs for k-means clustering and related problems. Our empirical study on real world data shows a speedup of orders of magnitude, preserving communication with only a negligible degradation in solution quality. Some of these techniques we develop, such as a general transformation from a constant success probability subspace embedding to a high success probability subspace embedding with a dimension and sparsity independent of the success probability, may be of independent interest.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “There are solutions to specific problems like mean estimation [17, 32], component analysis [23], clustering [6], sparse regression [18] and boosting [7].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “As datasets continue to increase in size, and parallel computing platforms becoming more and more common (from multiple cores on a single CPU to large-scale and geographically distributed computing grids), distributed learning and optimization methods have been the focus of much research in recent y”
Distributed low rank approximation of implicit functions of a matrix (2016, methodology): “PCA in the distributed model has been studied in a number of previous works, including [5], [6], [7], [8], [9].”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, methodology): “Our random projection result gives the lowest communication relative error distributed algorithm for k-means, improving on [34, 6, 30].”
Communication-Optimal Distributed Clustering (2016, background): “, [3, 4, 9]), no provable lower bounds in either model existed, and our main contribution is to show that previous algorithms are optimal.”
Communication and Memory Efficient Testing of Discrete Distributions (2019, methodology): “Other learning tasks has been studied as well in the distributed setting, including regression Zhu and Lafferty (2018) and PCA Kannan et al. (2014); Liang et al. (2014).”
Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis (2017, unknown): “Beyond the results described so far, [15, 5] studied distributed algorithms for PCA in a deterministic setting in which the partition of the data across machines is arbitrary and communication is measured in terms of number of transmitted bits.”
Decoding the Deep: Exploring Class Hierarchies of Deep Representations Using Multiresolution Matrix Factorization (2017, background): “Devising such block-structured kernels was the original motivation for several local low-rank and hierarchical factorizations [27, 4, 20, 38].”
Communication-Efficient Distributed Learning of Discrete Probability Distributions (2017, background): “In recent years, a number of statistical estimation problems have been algorithmically studied in the distributed setting [3, 16, 15, 40, 21, 30, 24, 33, 5, 29].”
Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, methodology): “Applications to important algorithms such as Principal Component Analysis were investigated in (Fan et al., 2017; Liang et al., 2014), among others.”