Risk minimization by median-of-means tournaments

Source 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.