# MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2018.

## Built on by (most cited first, 9 of 9)

- [A Prototype-Oriented Framework for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2110.12024/) (2021)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (2022)
- [A Unified Data Representation Learning for Non-parametric Two-sample Testing](https://mlsanity.com/paper/2412.00613/) (2024)
- [Robust Consensus in Ranking Data Analysis: Definitions, Properties and Computational Issues](https://mlsanity.com/paper/2303.12878/) (2023)
- [Optimizing Visual Generative Models via Distribution-wise Rewards](https://mlsanity.com/paper/2607.02291/) (2026)
- [Kernel Quantile Embeddings and Associated Probability Metrics](https://mlsanity.com/paper/2505.20433/) (2025)
- [On the Optimality of the Median-of-Means Estimator under Adversarial Contamination](https://mlsanity.com/paper/2510.07867/) (2025)
- [HOMER: Huber-of-Means for Efficient and Robust Estimation in Hilbert Spaces](https://mlsanity.com/paper/2607.27532/) (2026)

## Abstract (arXiv)

Mean embeddings provide an extremely flexible and powerful tool in machine learning and statistics to represent probability distributions and define a semi-metric (MMD, maximum mean discrepancy; also called N-distance or energy distance), with numerous successful applications. The representation is constructed as the expectation of the feature map defined by a kernel. As a mean, its classical empirical estimator, however, can be arbitrary severely affected even by a single outlier in case of unbounded features. To the best of our knowledge, unfortunately even the consistency of the existing few techniques trying to alleviate this serious sensitivity bottleneck is unknown. In this paper, we show how the recently emerged principle of median-of-means can be used to design estimators for kernel mean embedding and MMD with excessive resistance properties to outliers, and optimal sub-Gaussian deviation bounds under mild assumptions.