arXiv:2602.20698cs.LG2026-02

在高维数据中,如何从混有恶意用户和异质数据的批量数据里准确估算均值?

High-Dimensional Robust Mean Estimation with Untrusted Batches

  • 提出基于平方和(SoS)的算法,应对批量数据中的双重污染:部分用户完全恶意,其余数据存在均值偏移或样本级扰动。
  • 实现最小最优误差率 $O(\sqrt{\varepsilon/n} + \sqrt{d/nN} + \sqrtα)$,证明批量结构可抑制恶意影响。
  • 适用于高维场景下的可信协同学习,尤其适合对数据来源不可信但需稳定估计的系统设计者。

我们研究在协作环境中高维均值估计问题,其中 $N$ 个用户以大小为 $n$ 的批次贡献数据。学习者需从一组统计异质且可能恶意的数据源中恢复真实分布 $P$ 的均值 $μ$。我们通过双重污染模型形式化该挑战:$\varepsilon$ 分数的用户完全恶意,其余“良好”用户提供的数据来自与 $P$ 相关但偏离程度由参数 $α$ 控制的分布。不同于以往工作在离散场景下用总变差距离衡量偏差,我们在连续高维环境下考虑两种自然偏差模型:(1) 良好批次来自均值偏移 $\sqrtα$ 的分布;(2) 每个良好批次中有 $α$ 分数的样本被恶意扰动。特别地,第二种模型在高维中带来新挑战:即使少量样本级扰动,也能任意改变经验均值与协方差。我们提出两个基于平方和(SoS)的算法,以应对这种分层污染。算法达到最小最优误差率 $O(\sqrt{\varepsilon/n} + \sqrt{d/nN} + \sqrtα)$,表明尽管异质性 $α$ 是固有的统计难度,但恶意用户的干扰因批内平均被抑制 $1/\sqrt{n}$ 倍。

原文摘要 · Abstract (English)

We study high-dimensional mean estimation in a collaborative setting where data is contributed by $N$ users in batches of size $n$. In this environment, a learner seeks to recover the mean $μ$ of a true distribution $P$ from a collection of sources that are both statistically heterogeneous and potentially malicious. We formalize this challenge through a double corruption landscape: an $\varepsilon$-fraction of users are entirely adversarial, while the remaining ``good'' users provide data from distributions that are related to $P$, but deviate by a proximity parameter $α$. Unlike existing work on the untrusted batch model, which typically measures this deviation via total variation distance in discrete settings, we address the continuous, high-dimensional regime under two natural variants for deviation: (1) good batches are drawn from distributions with a mean-shift of $\sqrtα$, or (2) an $α$-fraction of samples within each good batch are adversarially corrupted. In particular, the second model presents significant new challenges: in high dimensions, unlike discrete settings, even a small fraction of sample-level corruption can shift empirical means and covariances arbitrarily. We provide two Sum-of-Squares (SoS) based algorithms to navigate this tiered corruption. Our algorithms achieve the minimax-optimal error rate $O(\sqrt{\varepsilon/n} + \sqrt{d/nN} + \sqrtα)$, demonstrating that while heterogeneity $α$ represents an inherent statistical difficulty, the influence of adversarial users is suppressed by a factor of $1/\sqrt{n}$ due to the internal averaging afforded by the batch structure.

高维估计鲁棒学习批量数据对抗攻击

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。