基于双重污染与异质批次的高维鲁棒均值估计

arXiv:2602.20698v2 公告类型：替换 摘要：现代数据系统通常需要汇总多个来源的信息：其中一些来源可能完全不可信，而其余被认为可靠的来源仍可能受到少量污染。我们研究这一实际场景下的鲁棒均值估计，并通过双重污染模型对其进行形式化描述：样本分配给 $N$ 个用户，每个用户拥有 $n$ 个样本。其中，比例为 $\varepsilon$ 的用户可能受到任意污染，而其余每个“良好”用户仍有比例为 $\alpha$（$\alpha>0$）的样本受到污染。目标是以较小的 $\ell_2$ 误差估计未知均值 $\mu$。这一场景具有挑战性，因为我们必须处理两类对抗性污染：用户级污染和样本级污染。当未知分布的协方差矩阵以单位矩阵为上界时，我们设计了一种平方和（SoS）算法，只要样本总数满足 $nN=\widetilde{\Omega}(d/\alpha)$，就能以至少 $2/3$ 的概率实现 $\sqrt{\alpha}$ 的 $\ell_2$ 误差。在温和条件下，其估计误差和样本复杂度均达到极小极大最优。相比之下，将全部 $nN$ 个样本视为受到比例为 $(\varepsilon+\alpha)$ 的污染，并应用标准鲁棒均值估计方法，只能实现 $\sqrt{\varepsilon+\alpha}$ 的误差。因此，我们的新算法消除了不可信用户的不利影响，达到了如同仅存在样本级污染时的最优误差。此外，我们的 SoS 算法还可扩展至异质场景，其中每个用户的局部均值还可能发生 $\ell_2$ 距离为 $\sqrt{\beta}$ 的额外偏移。我们证明，当 $nN=\widetilde{\Omega}(d/(\alpha+\beta))$ 时，可以至少 $2/3$ 的概率实现 $O(\sqrt{\alpha+\beta})$ 的误差。