Georgia Institute of Technology College of Sciences

Several constructions of the estimators of the mean of a random variable that admit sub-Gaussian deviation guarantees and are robust to adversarial contamination under minimal assumptions have been suggested in the literature. The goal of this talk is to discuss the size of constants appearing in the bounds, both asymptotic and non-asymptotic, satisfied by the median-of-means estimator and its analogues. We will describe a permutation-invariant version of the median-of-means estimator and show that it is asymptotically efficient, unlike its “standard" version. Finally, applications and extensions of these results to robust empirical risk minimization will be discussed.