# Risk minimization by median-of-means tournaments

### Gábor Lugosi

Pompeu Fabra University, Barcelona, Spain### Shahar Mendelson

The Australian National University, Canberra, Australia

## Abstract

We consider the classical statistical learning/regression problem, when the value of a real random variable $Y$ is to be predicted based on the observation of another random variable $X$. Given a class of functions $\mathcal F$ and a sample of independent copies of $(X,Y)$, one needs to choose a function $\widehat{f}$ from $\mathcal F$ such that $\widehat{f}(X)$ approximates $Y$ as well as possible, in the mean-squared sense. We introduce a new procedure, the so-called median-of-means tournament, that achieves the optimal tradeoff between accuracy and confidence under minimal assumptions, and in particular outperforms classical methods based on empirical risk minimization.

## Cite this article

Gábor Lugosi, Shahar Mendelson, Risk minimization by median-of-means tournaments. J. Eur. Math. Soc. 22 (2020), no. 3, pp. 925–965

DOI 10.4171/JEMS/937