Communication-efficient distributed eigenspace estimation with arbitrary node failures

Vasileios Charisopoulos · Anil Damle

Hall J #815
[ Abstract ]
[ Paper [ Slides [ OpenReview
Wed 30 Nov 2 p.m. PST — 4 p.m. PST

Abstract: 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.

Chat is not available.