4 ms·

They claim that it allows feasible computation of PCA (principal component analysis) on very large datasets. The key idea as I understand it is, instead of usin

They claim that it allows feasible computation of PCA (principal component analysis) on very large datasets. The key idea as I understand it is, instead of using some global technique to solve PCA (SVD), which cannot take advantage of the parallelism of GPU / TPU, they formulate PCA as a multiple-agent problem where each agent is trying individually to optimize its own "goal" (maximally explaining variance and being orthogonal to other "players"). There are two key non-trivialities, one is that the Nash equilibrium of such a formulation is achieved at the solution of "classical" PCA, and the other is that iterative, independent gradient ascent converges to this equilibrium.

eternalban 5y ago
This is my understanding as well. Section 3 sub "A decentralized algorithm" of their paper discusses the computation approach: "In practice we can assign each eigenvector update to its own device (e.g. a GPU or TPU). Systems with fast interconnects may facilitate tens, hundreds or thousands of accelerators to be used. In such settings, the overhead of broadcast(vˆi) is minimal. We can also specify that the data stream is co-located with the update so vˆi updates with respect to its own Xi,t. This is a standard paradigm for e.g. data-parallel distributed neural network training. We provide further details in Section [6]." So a general methodology that permits mapping analysis to "embarrassingly parallel" computational models. Tangent: Given the provenance of PCA (Karl Pearson) this is all a bit ironic ..
bigbillheck 5y ago
> some global technique to solve PCA (SVD), which cannot take advantage of the parallelism of GPU / TPU My reading of https://developer.download.nvidia.com/video/gputechconf/gtc/2019/presentation/s9226-fast-singular-value-decomposition-on-gpus-v2.pdf https://developer.download.nvidia.com/video/gputechconf/gtc/... suggests that it's just the usual modern SVD algorithm, in particular the QR factorization part, that's the limiting factor, and with some thought there are ways to do better.
inciampati 5y ago
Randomized SVD already allows this. Typically the calculation of PCA on a data set around the size that they use (1-100TB) is I/O bound. I work in genomics where this is a common problem. Their solution is interesting, but I'm not really sure if it would be more efficient due to parallelism. Better accuracy is important, but it's also unclear how much that affects the major PCs.

eternalban 5y ago

This is my understanding as well. Section 3 sub "A decentralized algorithm" of their paper discusses the computation approach: "In practice we can assign each eigenvector update to its own device (e.g. a GPU or TPU). Systems with fast interconnects may facilitate tens, hundreds or thousands of accelerators to be used. In such settings, the overhead of broadcast(vˆi) is minimal. We can also specify that the data stream is co-located with the update so vˆi updates with respect to its own Xi,t. This is a standard paradigm for e.g. data-parallel distributed neural network training. We provide further details in Section [6]." So a general methodology that permits mapping analysis to "embarrassingly parallel" computational models. Tangent: Given the provenance of PCA (Karl Pearson) this is all a bit ironic ..

bigbillheck 5y ago

> some global technique to solve PCA (SVD), which cannot take advantage of the parallelism of GPU / TPU My reading of https://developer.download.nvidia.com/video/gputechconf/gtc/2019/presentation/s9226-fast-singular-value-decomposition-on-gpus-v2.pdf https://developer.download.nvidia.com/video/gputechconf/gtc/... suggests that it's just the usual modern SVD algorithm, in particular the QR factorization part, that's the limiting factor, and with some thought there are ways to do better.

inciampati 5y ago

Randomized SVD already allows this. Typically the calculation of PCA on a data set around the size that they use (1-100TB) is I/O bound. I work in genomics where this is a common problem. Their solution is interesting, but I'm not really sure if it would be more efficient due to parallelism. Better accuracy is important, but it's also unclear how much that affects the major PCs.