How Robust is the Median-of-Means? Concentration Bounds in Presence of Outliers

Pierre Laforgue, Guillaume Staerman, Stéphan Clémençon

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.

The Median-of-Means (MoM) estimator process.

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.

Theoretical constants and bounds as a function of the outlier ratio $\epsilon$.

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

Abstract

In contrast to the empirical mean, the Median-of-Means (MoM) is an estimator of the mean $\theta$ of a square integrable r.v. $Z$, around which accurate nonasymptotic confidence bounds can be built, even when $Z$ does not exhibit a sub-Gaussian tail behavior. Thanks to the high confidence it achieves on heavy-tailed data, MoM has found various applications in machine learning, where it is used to design training procedures that are not sensitive to atypical observations. More recently, a new line of work is now trying to characterize and leverage MoM's ability to deal with corrupted data. In this context, the present work proposes a general study of MoM's concentration properties under the contamination regime, that provides a clear understanding of the impact of the outlier proportion and the number of blocks chosen. The analysis is extended to (multisample) $U$-statistics, i.e. averages over tuples of observations, that raise additional challenges due to the dependence induced. Finally, we show that the latter bounds can be used in a straightforward fashion to derive generalization guarantees for pairwise learning in a contaminated setting, and propose an algorithm to compute provably reliable decision functions.
BibTeX
@misc{laforgue2020how,
  author = {Pierre Laforgue and Guillaume Staerman and Stéphan Clémençon},
  title = {{How Robust is the Median-of-Means? Concentration Bounds in Presence of Outliers}},
  year = {2020},
  eprint = {2006.05240},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.05240},
}
Figure