Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements

Nibedita Roy; Vishal Halder; Gugan Thoppe; Alexandre Reiffers-Masson; Mihir Dhanakshirur; Naman; Alexandre Azor

stat.MLApr 7, 2026

Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements

Authors: Nibedita Roy, Vishal Halder, Gugan Thoppe, Alexandre Reiffers-Masson, Mihir Dhanakshirur, Naman, Alexandre Azor

Organizations: Dept. of Computer Science and Automation, Indian Institute of Science, Bengaluru 560012, India · Department of Computer Science, IMT Atlantique, Plouzané 29280, France

Abstract

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.

Figures & tables

x_{n+1}=\Pi_{\mathcal{X}}\big(x_{n}+\alpha_{n}\ a_{i}\ \textnormal{sign}(y_{n}(i)-a_{i}^{\top}x_{n})\big)

Algorithm 1 Online Algorithm to Estimate

\mathbb{E}[X]

( Ganesh et al., 2023 )

Notation	Asynchronous	Synchronous
$\Delta$	$\sqrt{d\bar{A}^{2}(\bar{\sigma}^{2}+\bar{\mu}^{2})}$	$\sqrt{d\bar{A}^{2}\bar{\sigma}^{2}}$
$C_{N}$	$\dfrac{2(N-m)}{\sqrt{N}}$	$\dfrac{2(N-m)}{N}$

Table 2

Figure 1: Comparison of Algorithm 1 ’s performance with that of existing state of the art robust-aggregator-based methods (see the legend to know the various methods we compare against). Subplots (a), (b), and (c) correspond to the synchronous case, while subplots (d), (e), and (f) correspond to the asynchronous case. In the synchronous-scenario plots, BKT stands for the bucketing variant, while it denotes the buffered variant in the asynchronous case. Subplots (a) and (d) correspond to the case where we update $x_{n}$ in Algorithm 1 using the $1/\sqrt{n+1}$ stepsize and the $x_{n}$ in other methods with the $1/(n+1)^{0.9}$ stepsize. In subplots (b) and (e), we update $x_{n}$ for all methods using the $1/\sqrt{n+1}$ stepsize. In subplots (c) and (f), we multiple $A$ by $10$ (to artificially add heterogeneity) and rerun the experiments with stepsizes as in subplots (b) and (e). Note that the error in all the subplots is obtained by averaging over $10$ runs.

Panel of Figure 2 — Figure 2: Network setup, corresponding path-link matrix, and the matrix $A$ in the associated decomposition.

Distributed Inference

Distributed inference runs machine-learning models across multiple devices or sites to meet compute, latency, memory, privacy, and reliability needs.

See all 74 papers

Byzantine-Robust Distributed Sparse Learning Revisited
May 13, 2026Yuxuan Wang, Lixin Zhang, Kangqiang LiDistributed Training Distributed Optimization
School of Mathematical Sciences, Zhejiang University, Hangzhou, 310027, Zhejiang, China · School of Statistics and Mathematics, Zhejiang Gongshang University, Hangzhou, 310018, Zhejiang, China · Information Center, Hubei Provincial Tobacco Monopoly Administration, Wuhan, 430030, Hubei, China
Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery
Oct 28, 2025Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1Sparse Recovery Adversarial Robustness
IMT Atlantique, Lab-STICC, CNRS UMR 6285, Brest, France · Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Sep 8, 2026Ivan Lau, Jonathan ScarlettMinimax Estimation
National University of Singapore

May 13, 2026J/K move · Enter open · S save

Byzantine-Robust Distributed Sparse Learning Revisited

Yuxuan Wang, Lixin Zhang, Kangqiang Li

School of Mathematical Sciences, Zhejiang University, Hangzhou, 310027, Zhejiang, China · School of Statistics and Mathematics, Zhejiang Gongshang University, Hangzhou, 310018, Zhejiang, China · Information Center, Hubei Provincial Tobacco Monopoly Administration, Wuhan, 430030, Hubei, China

Distributed Training Distributed Optimization Linear Regression Robust Regression Distributed Inference Robust Estimation+1

Open paper AskPDF arXiv

We revisit Byzantine robust distributed estimation for high-dimensional sparse linear models. By combining local

\ell_1

-regularized robust estimation with robust aggregation at the server, the framework applies to pseudo-Huber regression, quantile regression, and sparse SVM. We show that the resulting estimators yield non-asymptotic guarantees and attain near-optimal statistical rates under mild conditions, while remaining communication-efficient. Simulations confirm strong robustness in estimation, support recovery and classification accuracy under various Byzantine attacks.

Abstract

Distributed Inference

Explore similar work

Byzantine-Robust Distributed Sparse Learning Revisited

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff