On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
This addresses the robustness of statistical estimators for machine learning applications where data may be adversarially corrupted, providing theoretical guarantees for specific distribution classes.
The paper tackled the problem of determining the optimality of the Median-of-Means estimator under adversarial contamination, showing it is minimax optimal for distributions with finite variance or infinite variance and finite absolute moments, but sub-optimal for light-tailed distributions.
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.