在对抗性干扰和异步通信下，实现分布式线性估计的精准收敛
Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements
- 基于两尺度ℓ₁最小化，设计抗干扰分布式估计算法
- 首次给出非渐近收敛速率，证明在特定条件下可稳定恢复均值
- 适用于网络拓扑推断等对鲁棒性要求高的传感场景
研究在分布式参数-服务器-工作节点架构中对随机向量 $X$ 的均值估计问题。每个工作节点 $i$ 观测到 $a_i^ op X$，其中 $a_i^ op$ 是已知感知矩阵 $A$ 的第 $i$ 行。主要挑战来自对抗性测量和异步性：部分工作节点可能发送被污染的数据，且工作节点激活异步——任意时刻仅一个节点活跃。此前工作提出一种两尺度 ℓ₁ 最小化算法，并在 $A$ 满足类似零空间性质的条件下建立了渐近可恢复性。本文在相同条件下，首次建立紧致的非渐近收敛速率。同时识别出 $A$ 的更宽松条件，在此条件下精确恢复可能失败，但 $\mathbb{E}[X]$ 的投影分量仍可恢复。总体结果为带有对抗性工作节点的分布式线性估计提供了统一的有限时间分析，涵盖鲁棒性、可辨识性与统计效率，对网络拓扑推断等分布式传感问题具有重要意义。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。