# Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements

arXiv: https://arxiv.org/abs/2604.06282 · HTML: https://mlsanity.com/paper/2604.06282/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 7 Apr 2026.

## Builds on (most cited first, 13 of 13)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Robust Federated Learning in a Heterogeneous Environment](https://mlsanity.com/paper/1906.06629/) (2019)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Zeno++: Robust Fully Asynchronous SGD](https://mlsanity.com/paper/1903.07020/) (2019)
- [AFLGuard: Byzantine-robust Asynchronous Federated Learning](https://mlsanity.com/paper/2212.06325/) (2022)
- [Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data](https://mlsanity.com/paper/2005.07866/) (2020)
- [Data Encoding for Byzantine-Resilient Distributed Optimization](https://mlsanity.com/paper/1907.02664/) (2019)
- [Online Learning with Adversaries: A Differential-Inclusion Analysis](https://mlsanity.com/paper/2304.01525/) (2023)

## Abstract (arXiv)

We study mean estimation of a random vector X in a distributed parameter-server-worker setup. Worker i observes samples of ai^top X, where ai^top 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 ℓ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 mathbbE[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.