# On Medians of (Randomized) Pairwise Means

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 1 Nov 2022.

## Builds on (most cited first, 6 of 6)

- [A Survey on Metric Learning for Feature Vectors and Structured Data](https://mlsanity.com/paper/1306.6709/) (2013)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics](https://mlsanity.com/paper/1501.02629/) (2015)
- [On aggregation for heavy-tailed classes](https://mlsanity.com/paper/1502.07097/) (2015)

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

- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)
- [On Gossip Algorithms for Machine Learning with Pairwise Objectives](https://mlsanity.com/paper/2603.24128/) (2026)
- [On Finite-sample Concentration of Median of Incomplete U-Statistics](https://mlsanity.com/paper/2606.00661/) (2026)

## Abstract (arXiv)

Tournament procedures, recently introduced in Lugosi & Mendelson (2016), offer an appealing alternative, from a theoretical perspective at least, to the principle of Empirical Risk Minimization in machine learning. Statistical learning by Median-of-Means (MoM) basically consists in segmenting the training data into blocks of equal size and comparing the statistical performance of every pair of candidate decision rules on each data block: that with highest performance on the majority of the blocks is declared as the winner. In the context of nonparametric regression, functions having won all their duels have been shown to outperform empirical risk minimizers w.r.t. the mean squared error under minimal assumptions, while exhibiting robustness properties. It is the purpose of this paper to extend this approach in order to address other learning problems, in particular for which the performance criterion takes the form of an expectation over pairs of observations rather than over one single observation, as may be the case in pairwise ranking, clustering or metric learning. Precisely, it is proved here that the bounds achieved by MoM are essentially conserved when the blocks are built by means of independent sampling without replacement schemes instead of a simple segmentation. These results are next extended to situations where the risk is related to a pairwise loss function and its empirical counterpart is of the form of a U-statistic. Beyond theoretical results guaranteeing the performance of the learning/estimation methods proposed, some numerical experiments provide empirical evidence of their relevance in practice.