证明中位数均值估计器在对抗污染下对多种分布仍最优
On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
- 将样本分组求均值后取中位数，提升抗干扰能力
- 在方差有限和重尾分布下误差达到理论最优
- 发现轻尾分布中该方法不最优，适合鲁棒性场景
中位数均值（MoM）估计器在独立同分布样本下已被证明是极小极大最优的。但在更严峻的对抗污染场景中，数据可能被有目的修改。此前研究仅在高斯情形下证明其适用性，但其在一般分布下的极小极大最优性及局限性尚不明确。本文针对多类分布给出了MoM误差的上下界：在方差有限的分布类以及具有有限绝对(1+r)阶矩的重尾分布类中，MoM达到极小极大最优；同时构造了与上界同阶的下界，表明其在轻尾分布中次优。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。