On the Optimality of the Median-of-Means Estimator under Adversarial Contamination

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.

Previous work has theoretically shown the suitability of the MoM estimator in certain contamination scenarios. In particular, the results in [15] provide upper bounds for MoM's error for finite-variance distributions, with rates matching the optimal order in the i.i.d. scenario. In addition, MoM has been shown to be (minimax) optimal for Gaussian distributions since it generalizes the sample median (see e.g., [26], [27, Cor. 1.15]). However, the (minimax) optimality of MoM remains unknown beyond the Gaussian case, as mentioned in [25]. Specifically, previous work on MoM considered a more benign contamination model and only studied the regime with a reduced number of samples, i.e., not the asymptotic bias. Moreover, the limitations of MoM under adversarial contamination remain unknown, as no lower bounds on its error have been established.

This paper provides upper and lower error bounds for the MoM estimator for multiple classes of distributions under adversarial contamination (see Table 1). In particular, the results reveal that MoM is (minimax) optimal for heavy-tailed and symmetric distributions, but sub-optimal for lighttailed distributions. Specifically, the main contributions in the paper are as follows:

• We prove that MoM is optimal under adversarial contamination 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 obtain upper bounds for the error of MoM in the classes of sub-exponential and sub-Gaussian distributions, which improve upon those established for the finite variance case.

• We obtain lower bounds for MoM that match the order of the presented upper bounds. In particular, we prove that MoM cannot fully exploit light tails and is sub-optimal for subexponential distributions.

• We prove that MoM is optimal under adversarial contamination in a class of symmetric distributions that includes Gaussians and heavy-tailed distributions such as Student's t.

The rest of this paper is organized as follows. Section 2 describes the problem of mean estimation under adversarial contamination. In Section 3, we present the optimality results for distributions with finite variance, and infinite variance with finite absolute (1 + r)-th moment. In Section 4, we present error bounds for MoM for light-tailed distributions, where we obtain improved orders compared to the finite variance case. In Section 5, we prove that MoM attains even better orders in a class of symmetric distributions. All proofs are deferred to Appendices A and B. Finally, we illustrate the results in the paper with numerical experiments in Appendix C.