Principal Component Analysis and Higher Correlations for Distributed Data

By R. Kannan, Santosh Srinivas Vempala, David P. Woodruff. 2013

90 citations recorded by the source corpus.

We consider algorithmic problems in the setting in which the input data has been partitioned arbitrarily on many servers. The goal is to compute a function of all the data, and the bottleneck is the communication used by the algorithm. We present algorithms for two illustrative problems on massive data sets: (1) computing a low-rank approximation of a matrix $A=A^1 + A^2 + \ldots + A^s$, with matrix $A^t$ stored on server $t$ and (2) computing a function of a vector $a_1 + a_2 + \ldots + a_s$, where server $t$ has the vector $a_t$; this includes the well-studied special case of computing frequency moments and separable functions, as well as higher-order correlations such as the number of subgraphs of a specified type occurring in a graph. For both problems we give algorithms with nearly optimal communication, and in particular the only dependence on $n$, the size of the data, is in the number of bits needed to represent indices and words ($O(\log n)$).

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Communication lower bounds for statistical estimation problems via a distributed data processing inequality (2015, background): “A lot of recent work has been devoted to design communication-eﬃcient learning algorithms [DAW12, ZDW13, ZX15, KVW14, LBKW14, SSZ14, LSLT15].”
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).”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “s] A t, we would like for each player to compute the same rank-k projection matrix WWT ∈Rd×d, for which kA −AWWTk2 F ≤(1 + ε)kA −Akk2F . We presented a protocol due to Kannan, Vempala, and the author [68] which obtained O(sdk/ε) + poly(sk/ε) words of communication for solving this problem. In [68] a”
Communication-Efficient Distributed Statistical Inference (2016, background): “…distributed inference has begun to emerge, both in a frequentist setting (Duchi, Agar-wal, and Wainwright 2012; Zhang, Duchi, and Wainwright 2013; Kannan, Vempala, and Woodruff 2014; Kleiner et al. 2014; Shamir, Srebro, and Zhang 2014; Mackey, Talwalkar, and Jordan 2015; Zhang and Lin 2015a; Lee…”
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].”
Tighter Low-rank Approximation via Sampling the Leveraged Element (2014, methodology): “Note that, such a model is now standard for this problem and was most recently studied by [15].”
Distributed low rank approximation of implicit functions of a matrix (2016, methodology): “The result also improves an Ω̃(skd) lower bound shown in [7] to Ω̃(max(skd, 1/ε(2))).”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “In the column-partition distributed model, there are many existing protocols using O ( skmε − 1 ) words of communication [24, 6, 33, 26, 30, 9], and the protocols work in very different ways: that of [24, 6] is based on coresets, while that of [33, 26] is based on adapting a streaming algorithm to…”
Subspace Embeddings for the Polynomial Kernel (2014, unknown): “5 of [9] that ‖UWWUφ(A)−φ(A)‖F ≤ (1 + )‖φ(A)− [φ(A)]k‖F .”
Improved Distributed Principal Component Analysis (2014, background): “Most closely related to our work is [9, 12].”
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].”