Risk minimization by median-of-means tournaments

  • Gábor Lugosi

    Pompeu Fabra University, Barcelona, Spain
  • Shahar Mendelson

    The Australian National University, Canberra, Australia
Risk minimization by median-of-means tournaments cover
Download PDF

A subscription is required to access this article.


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–965

DOI 10.4171/JEMS/937