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 metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.telecom-paris.fr/hal-02463910
Contributor : Stephan Clémençon <>
Submitted on : Sunday, February 2, 2020 - 1:05:01 PM
Last modification on : Wednesday, September 16, 2020 - 10:43:36 AM
Long-term archiving on: : Sunday, May 3, 2020 - 1:00:37 PM

File

clemencon19a.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02463910, version 1

Citation

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⟩

Share

Metrics

Record views

60

Files downloads

34