Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements
This work addresses robustness and efficiency in distributed sensing for applications like network tomography, but it is incremental as it builds on previous asymptotic results to provide finite-time analysis.
The paper tackles the problem of distributed linear estimation with adversarial measurements and asynchrony, establishing tight non-asymptotic convergence rates for mean estimation under a null-space-property-like condition and identifying conditions for partial recovery when exact recovery fails.
We study mean estimation of a random vector $X$ in a distributed parameter-server-worker setup. Worker $i$ observes samples of $a_i^\top X$, where $a_i^\top$ is the $i$th row of a known sensing matrix $A$. The key challenges are adversarial measurements and asynchrony: a fixed subset of workers may transmit corrupted measurements, and workers are activated asynchronously--only one is active at any time. In our previous work, we proposed a two-timescale $\ell_1$-minimization algorithm and established asymptotic recovery under a null-space-property-like condition on $A$. In this work, we establish tight non-asymptotic convergence rates under the same null-space-property-like condition. We also identify relaxed conditions on $A$ under which exact recovery may fail but recovery of a projected component of $\mathbb{E}[X]$ remains possible. Overall, our results provide a unified finite-time characterization of robustness, identifiability, and statistical efficiency in distributed linear estimation with adversarial workers, with implications for network tomography and related distributed sensing problems.