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.

Abstract

We consider the classical statistical learning/regression problem, when the value of a real random variable YY is to be predicted based on the observation of another random variable XX. Given a class of functions F\mathcal F and a sample of independent copies of (X,Y)(X,Y), one needs to choose a function f^\widehat{f} from F\mathcal F such that f^(X)\widehat{f}(X) approximates YY 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