Introduction
In machine learning, models typically rely on the "empirical mean" to estimate risk and update parameters. However, the empirical mean is notoriously fragile: it breaks down if the data has "heavy tails" (frequent extreme values) or if the dataset is "contaminated" by outliers (malicious or noisy data points).
While the Median-of-Means (MoM) estimator is a well-known fix for heavy-tailed data, its behavior under the $\epsilon$-contamination model—where a fraction $\epsilon$ of the data is arbitrary garbage—has historically been less understood. Specifically, there was a lack of clear generalization bounds (guarantees on how well a model will perform on new data) for MoM when applied to $U$-statistics. $U$-statistics are crucial for pairwise learning tasks, such as ranking and metric learning, where the loss depends on pairs of observations. Because a single outlier can corrupt many pairs, proving robustness in this setting is mathematically challenging.
This paper provides a rigorous theoretical framework for the MoM estimator in the presence of outliers. It proves that MoM can handle up to 50% data contamination and extends these robustness guarantees to complex pairwise learning tasks through a novel algorithm called MoU-GD.
Methods: The Median-of-Means Approach
The authors analyze the MoM estimator, which provides a robust alternative to the standard empirical mean. The process works in three simple steps:
- Partition a dataset into $K$ disjoint blocks.
- Calculate the empirical mean of each block.
- Take the median of those block means.
By focusing on the median, the algorithm effectively "ignores" the blocks containing outliers. In pairwise learning, this "sane block advantage" is crucial because it prevents a few bad data points from corrupting the entire gradient signal.
Key Innovations
- Calibration Mapping ($\alpha$): To optimize the estimator, the authors introduce a mapping function $\alpha(\epsilon)$ to help choose the ideal number of blocks $K$. This allows practitioners to balance the trade-off between estimation accuracy and the range of confidence levels based on the expected contamination rate.
- Median-of-$U$-statistics (MoU): The paper extends the MoM principle to $U$-statistics. Instead of simple block means, the algorithm computes $U$-statistics on each block and takes the median, enabling robust pairwise learning.
- MoU-Gradient Descent (MoU-GD): The authors propose a robust optimization algorithm. In each step of gradient descent, the data is partitioned, gradients are calculated for each block, and only the gradient from the "median" block (the one with the median risk) is used to update the model parameters.
Key Insights and Results
Theoretical Guarantees
- The 50% Breakdown Point: Theoretically, MoM can remain accurate even if nearly 50% of the blocks are contaminated by outliers. This is a massive improvement over standard means, which can be ruined by a single outlier.
- Encapsulating Outliers: The authors' new bounds "encapsulate" the impact of outliers into constant terms. This means that as the dataset grows ($n$ increases), the error still shrinks at the optimal rate ($1/\sqrt{n}$), even if the data is messy.
- Sub-Gaussian Performance: Even if the underlying data distribution is not "nice" (i.e., not sub-Gaussian), the MoM estimator behaves as if it were, providing high-confidence guarantees that the empirical mean cannot offer.
- Generalization Bounds: The paper provides the first generalization bound for pairwise learning with outliers using MoM, utilizing Vapnik-Chervonenkis (VC) dimension theory.
Empirical Success
To test these theoretical claims, the authors conducted metric learning experiments using the classic Iris dataset, intentionally adding 10% outliers drawn from a uniform distribution to confuse the learner.
In these experiments, MoU-GD significantly outperformed standard Gradient Descent. While standard GD's performance collapsed due to the 10% contamination, MoU-GD achieved test performance nearly identical to a model trained on perfectly clean data.
Limitations and Future Work
While powerful, the MoM approach has a few limitations:
- Knowledge of $\epsilon$: To choose the "perfect" number of blocks $K$, one ideally needs to know the proportion of outliers $\epsilon$. While the authors show that overestimating $\epsilon$ is safe, it leads to slightly less efficient bounds.
- Computational Complexity: While univariate MoM is fast, extending these ideas to very high-dimensional multivariate settings can be computationally expensive, which remains a common hurdle for robust estimators.
- Stricter Requirements for Multisample MoU: For tasks involving two different datasets (multisample $U$-statistics), the robustness requirement is stricter ($\epsilon_X + \epsilon_Y < 1/2$), suggesting room for further theoretical refinement in multi-distribution settings.
Summary updated