Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis

By Dan Garber, Ohad Shamir, Nati Srebro. 2017

45 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

How researchers see this paper

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

In Computational Mechanics

1. Ji Liu
2. Hanlin Tang
3. Tong Zhang
4. Xiangru Lian
5. Khaled Ben Letaief
6. Yuanming Shi
7. Kai Yang
8. Tao Jiang

In Computer Networks and Communications

1. Hanlin Tang
2. Tong Zhang
3. Ji Liu
4. Xiangru Lian
5. Yuanming Shi
6. Khaled Ben Letaief
7. Tao Jiang
8. Kai Yang

In Statistics and Probability

1. Ji Liu
2. Xiangru Lian
3. Khaled Ben Letaief
4. Tao Jiang
5. Kai Yang
6. Yuanming Shi
7. Hanlin Tang
8. Tong Zhang

Citations in the corpus

• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “Some extension of communication efficient distributed learning, such as differentially private optimization (Agarwal et al., 2018), optimization on manifolds (Saparbayeva et al., 2018), compressed PCA (Garber et al., 2017), are also studied recently.”
• Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “[169] proposed a stochastic distributed algorithm to solve the principal component analysis problem, which gives considerable acceleration in terms of communication rounds over previous distributed algorithms.”