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

arXiv: https://arxiv.org/abs/2510.07867 · HTML: https://mlsanity.com/paper/2510.07867/

## 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 (most cited first, 15 of 15)

- [BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain](https://mlsanity.com/paper/1708.06733/) (2017)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks](https://mlsanity.com/paper/1803.06975/) (2018)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Support Vector Machines under Adversarial Label Contamination](https://mlsanity.com/paper/2206.00352/) (2022)
- [Distributed Statistical Estimation and Rates of Convergence in Normal Approximation](https://mlsanity.com/paper/1704.02658/) (2017)
- [MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means](https://mlsanity.com/paper/1802.04784/) (2018)
- [Robust Kernel Density Estimation with Median-of-Means principle](https://mlsanity.com/paper/2006.16590/) (2020)
- [Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation](https://mlsanity.com/paper/1306.1433/) (2013)
- [K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means](https://mlsanity.com/paper/2002.03899/) (2020)
- [Efficient median of means estimator](https://mlsanity.com/paper/2305.18681/) (2023)

## 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.