We consider the classical statistical learning/regression problem, when the value of a real random variable is to be predicted based on the observation of another random variable . Given a class of functions and a sample of independent copies of , one needs to choose a function from such that approximates 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–965DOI 10.4171/JEMS/937