Adversary-Resilient Distributed Estimation using Intermittent and Heterogeneous Data with Application to Network Tomography
Abstract
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.
Domains
Computer Science [cs]Origin | Files produced by the author(s) |
---|