Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913013163884544 |
|---|---|
| author | Roy, Nibedita Halder, Vishal Thoppe, Gugan Reiffers-Masson, Alexandre Dhanakshirur, Mihir Naman Azor, Alexandre |
| author_facet | Roy, Nibedita Halder, Vishal Thoppe, Gugan Reiffers-Masson, Alexandre Dhanakshirur, Mihir Naman Azor, Alexandre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06282 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements Roy, Nibedita Halder, Vishal Thoppe, Gugan Reiffers-Masson, Alexandre Dhanakshirur, Mihir Naman Azor, Alexandre Machine Learning 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. |
| title | Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2604.06282 |