mlsanityData to 14 Oct 2026

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

arXiv 2510.07867 ↗First posted 9 Oct 2025stat.ML cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 15 of its 42 references that are in the map. First posted on arXiv 9 Oct 2025.

Builds on

15 of 42 references.

References · 15

  1. 2017BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chaincited by 1,106
  2. 2017Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoningcited by 1,055
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  5. 2018Stronger Data Poisoning Attacks Break Data Sanitization Defensescited by 135
  6. 2018Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attackscited by 81
  7. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  8. 2015Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Modelcited by 47
  9. 2022Support Vector Machines under Adversarial Label Contaminationcited by 17
  10. 2017Distributed Statistical Estimation and Rates of Convergence in Normal Approximationcited by 15
  11. 2018MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Meanscited by 9
  12. 2020Robust Kernel Density Estimation with Median-of-Means principlecited by 9
3 more
  1. 2013Tight Lower Bound on the Probability of a Binomial Exceeding its Expectationcited by 7
  2. 2020K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Meanscited by 7
  3. 2023Efficient median of means estimatorcited by 7

Built on by

Not cited yet.