  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.
