Risk minimization by median-of-means tournaments

By Gábor Lugosi, Shahar Mendelson. 2016

139 citations recorded by the source corpus.

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 F and a sample of independent copies of (X, Y ), one needs to choose a function f from F such that 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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Robust Aggregation for Federated Learning (2019, methodology): “Robust median-of-means were introduced in [70], with follow ups in [39, 53, 60, 61, 67].”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “…et al. (2015), Nemirovskii et al. (1983), and has been applied to bandit and least square regression problems (Bubeck et al., 2013, Kogler and Traxler, 2016, Lugosi and Mendelson, 2016) as well as problems involving heavy-tailed distributions (Hsu and Sabato, 2016, Lugosi and Mendelson, 2017).”
Convergence rates of least squares regression estimators with heavy-tailed errors (2017, background): “t on the errors, we refer the reader to [7]. It is worthwhile to note that the shortcomings of the LSE quantiﬁed here also rigorously justify the motivation of developing other robust procedures (cf. [4, 14, 15, 18, 19, 24, 35, 36, 45, 46, 47, 57]). Remark 9. Our Theorems 3 and 4 show that the momen”
Robust estimation via robust gradient estimation (2018, background): “Other recent work by Lerasle and Oliveira [31], Lugosi and Mendelson [35] use similar ideas to derive estimators that perform well theoretically, in heavy-tailed situations.”
Robust machine learning by median-of-means: Theory and practice (2017, methodology): “A modiﬁcation of the ERM based on Le Cam’s estimation by tests principle [48, 49] has also been considered in [60, 50].”
Sub-Gaussian estimators of the mean of a random vector (2017, methodology): “The construction of the new estimator is inspired by the technique of “median-of-means tournament”, put forward by the authors in [15].”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “An optimal choice of f̂ for an arbitrary class F was introduced by Mendelson [62], and that choice is also based on median-of-means tournament, though a different tournament than the one defined in [59].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “The coordinate-wise median aggregation subroutine that we consider is related to the median-of-means estimator [52, 31], which has been applied to various robust inference problems [51, 47, 50].”
Learning from MOM’s principles: Le Cam’s approach (2017, methodology): “Theorem 3 is thus an extension of Lugosi and Mendelson (2017) to a non-i.d. corrupted setting for Le Cam’s champion.”
Regularization, sparse recovery, and median-of-means tournaments (2017, methodology): “Just as the tournament procedure from [10] outperforms empirical risk minimization (in fact, the tournament procedure attains the optimal tradeoﬀ between accuracy and conﬁdence under minimal assumptions), the regularized tournament which we present here, outperforms regularized risk minimization.”