Tight Convergence Rates for Online Distributed Linear Estimation withAdversarial Measurements
Nibedita Roy, Vishal Halder, Gugan Thoppe, Alexandre Reiffers-Masson, Mihir Dhankshiru, Naman Naman, Alexandre Azor · HAL (Le Centre pour la Communication Scientifique Directe) · 2026
Robustness to adversarial attacks in online distributed learning within a single parameter server and multiple worker node framework is a critical research area. Traditional methods for this setup achieve resilience through a two-step process in each iteration. First, all worker nodes synchronize to compute and communicate identical quantities, such as gradients at a shared point, to the server. Then, the server uses a robust aggregate of these quantities---obtained via techniques like the median or trimmed mean---to update its solution estimate. However, this approach falls short in applications like network tomography, where the measurements across different nodes are sporadic and heterogeneous. A novel two-timescale algorithm was recently proposed to deal with such scenarios. In this study, we establish that its convergence rate is \(O(1/\sqrt{n})\), which is optimal for non-strongly convex optimization. Separately, due to the sporadic nature of data, it is inevitable that this rate expression degrades when more honest agents are incorporated into the system. For a fixed number of adversaries, our work reveals that this degradation is of order $O(\sqrt{N}),$ where $N$ is the number of worker nodes.Lastly, we demonstrate the applicability of this algorithm and our theoretical results to network tomography.