Abstract
The Median-of-Means (MoM) estimator is a robust alternative to the empirical mean, particularly effective for heavy-tailed distributions. This paper investigates its performance under $\epsilon$-contamination, where a fraction of the data is adversarially corrupted. We provide a unified theoretical framework for MoM concentration bounds, extend these results to U-statistics (MoU), and propose a robust gradient descent algorithm (MoU-GD) for empirical risk minimization. Our results show that MoM can tolerate up to 50% contamination, maintaining high accuracy in complex learning tasks where standard methods fail.
Introduction
Estimating the mean of a dataset is a foundational task in machine learning, but the standard empirical mean is notoriously fragile—a single massive outlier can ruin the estimate. While statisticians have long used the Median-of-Means (MoM) estimator to handle heavy-tailed distributions, modern datasets often face $\epsilon$-contamination, where a specific fraction of data is corrupted by faulty sensors or malicious actors. This paper provides a clean, unified study of MoM under contamination and extends it to more complex machine learning scenarios like pairwise learning.
The MoM Estimator
The MoM estimator operates by partitioning a dataset of $n$ points into $K$ disjoint blocks. The empirical mean is calculated for each block, and the final estimate is the median of these block means.
This structure ensures that as long as more than half of the blocks are "clean" (uncorrupted), the median operation will shield the final estimate from extreme values in corrupted blocks.
Theoretical Framework and the 50% Rule
The authors derive explicit mathematical bounds for MoM under $\epsilon$-contamination. A key contribution is the introduction of a mapping function $\alpha(\epsilon)$ that helps calibrate the number of blocks $K$ based on the outlier ratio.
The theory establishes that MoM can handle up to nearly 50% corrupted data ($\epsilon < 1/2$). However, as shown in the theoretical constants, as $\epsilon$ approaches 0.5, the statistical guarantees become less tight, and the constant terms in the bounds (such as $\gamma(\epsilon)$) increase significantly. Choosing $K$ is a delicate balancing act: enough blocks are needed to isolate outliers, but if $K$ is too large, the individual blocks become too small, reducing statistical efficiency.
Extensions: MoU and Robust Gradient Descent
Standard MoM is designed for simple averages. This work extends the principle to U-statistics (MoU)—averages over pairs or tuples of data points—which are crucial for ranking, clustering, and metric learning.
Furthermore, the authors introduce MoU Gradient Descent (MoU-GD) for practical training. At each step, the algorithm partitions the data into blocks, computes the loss for each, and takes a gradient step using only the block with the median loss. While this discards most of the data in each step, it acts as a powerful, automatic shield against outliers during the training process.
Key Results
- Synthetic Stability: In tests where outliers pulled standard estimators arbitrarily far from the truth, MoM and MoU remained unbothered, accurately tracking true values.
- Rescuing Gradient Descent: On the Iris dataset with 10% outliers, standard Gradient Descent failed, while MoU-GD achieved test loss nearly identical to a clean baseline.
- Robust Ranking: Similar success was observed on Boston Housing and Red Wine Quality datasets, where MoU-GD effectively ignored injected outliers to maintain high generalization accuracy.
Limitations
Despite its strengths, MoM requires the practitioner to know the proportion of outliers $\epsilon$ in advance to set $K$ optimally. Additionally, MoU-GD's strategy of using only the median block leads to noisier training trajectories compared to standard methods. Finally, maintaining mathematical independence in multi-sample U-statistics can lead to information loss, as some data pairs must be ignored.
Summary updated