Department of Mathematics - Seminar on Statistics - The median of means estimator: old and new

The median of means (MOM) estimator has become a go-to method for problems involving heavy-tailed data and adversarial contamination. Examples include robust versions of mean and covariance estimators, linear regression, and k-means clustering, among others. Achieving the best possible performance fo the MOM estimator in the simplest univariate case has positive implications for many of these problems. In the first part of the talk, we will show how to obtain an efficient version of the MOM estimator that satisfies deviation inequalities with sharp constants assuming that the underlying distributions possesses 2+\epsilon moments, and discuss connections between this question and the theory of U-statistics. 

The second part of the talk will be devoted to the multivariate version of the MOM estimator based on the geometric median. We will demonstrate that for large classes of heavy-tailed distributions, the ``geometric’’ MOM attains sub-exponential or sub-Gaussian deviation guarantees, thus improving the known bounds. New analysis of this estimator reveals interesting connections to the small ball probabilities and some questions about the negative moments of the norms.