Risk minimization by median-of-means tournaments

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 $\hat{f}$ from $\mathcal{F}$ such that $\hat{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.