Communication-efficient distributed eigenspace estimation with arbitrary node failures
We develop an eigenspace estimation algorithm for distributed environments
with arbitrary node failures, where a subset of computing nodes can return
structurally valid but otherwise arbitrarily chosen responses. Notably, this
setting encompasses several important scenarios that arise in distributed
computing and data-collection environments such as silent/soft errors, outliers
or corrupted data at certain nodes, and adversarial responses. Our estimator
builds upon and matches the performance of a recently proposed non-robust
estimator up to an additive $\tilde{O}(\sigma \sqrt{\alpha})$ error, where
$\sigma^2$ is the variance of the existing estimator and $\alpha$ is the
fraction of corrupted nodes.