Communication-efficient distributed eigenspace estimation with arbitrary node failures
This addresses robustness in distributed computing for applications like data analysis, though it appears incremental as it builds on an existing estimator.
The paper tackles the problem of eigenspace estimation in distributed environments where nodes can fail arbitrarily, including due to errors, outliers, or adversarial actions, and develops an estimator that matches the performance of a non-robust estimator up to an additive error term dependent on variance and corruption fraction.
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}(σ\sqrtα)$ error, where $σ^2$ is the variance of the existing estimator and $α$ is the fraction of corrupted nodes.