Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

On Medians of (Randomized) Pairwise Means

Abstract : 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.
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Stephan Clémençon Connect in order to contact the contributor
Submitted on : Sunday, February 2, 2020 - 1:05:01 PM
Last modification on : Thursday, January 20, 2022 - 3:42:20 AM
Long-term archiving on: : Sunday, May 3, 2020 - 1:00:37 PM


Files produced by the author(s)


  • HAL Id : hal-02463910, version 1


Pierre Laforgue, Stéphan Clémençon, Patrice Bertail. On Medians of (Randomized) Pairwise Means. 36th International Conference on Machine Learning,, 2019, Longbeach, United States. ⟨hal-02463910⟩



Record views


Files downloads