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.
