Model Releases
Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements
arXiv:2604.06282v1 Announce Type: cross Abstract: We study mean estimation of a random vector X in a distributed parameter-server-worker setup. Worker i observes samples of a_i^op X, where $a_
arXiv:2604.06282v1 Announce Type: cross Abstract: We study mean estimation of a random vector X in a distributed parameter-server-worker setup. Worker i observes samples of a_i^op X, where a_i^op is the ith 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 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.
Related
Source: arXiv cs.LG | 2026-04-10