标题： 在对抗污染下的中位数-均值估计量的最优性 显示英文标题

标题： On the Optimality of the Median-of-Means Estimator under Adversarial Contamination

摘要： 中位数-均值（MoM）是一种在机器学习中广泛使用的鲁棒估计器，已知在样本独立同分布的情况下是（最小最大）最优的。 在更严重的情况下，样本可能被一个可以检查和修改数据的对手所污染。 以前的工作已经从理论上证明了MoM估计器在某些污染环境中的适用性。 然而，MoM在对抗污染下的（最小最大）最优性和限制性在高斯情况之外仍不清楚。 在本文中，我们为对抗污染下MoM的误差提供了多个分布类别的上下界。 特别是，我们证明了在具有有限方差的分布类以及具有无限方差和有限绝对$(1+r)$-阶矩的分布类中，MoM是（最小最大）最优的。 我们还提供了与所提出的上界顺序匹配的MoM误差下界，并表明MoM对于轻尾分布是次优的。 显示英文摘要

摘要： The Median-of-Means (MoM) is a robust estimator widely used in machine learning that is known to be (minimax) optimal in scenarios where samples are i.i.d. In more grave scenarios, samples are contaminated by an adversary that can inspect and modify the data. Previous work has theoretically shown the suitability of the MoM estimator in certain contaminated settings. However, the (minimax) optimality of MoM and its limitations under adversarial contamination remain unknown beyond the Gaussian case. In this paper, we present upper and lower bounds for the error of MoM under adversarial contamination for multiple classes of distributions. In particular, we show that MoM is (minimax) optimal in the class of distributions with finite variance, as well as in the class of distributions with infinite variance and finite absolute $(1+r)$-th moment. We also provide lower bounds for MoM's error that match the order of the presented upper bounds, and show that MoM is sub-optimal for light-tailed distributions.