Loss minimization and parameter estimation with heavy tails
This addresses robust statistical estimation for practitioners dealing with non-subgaussian data, though it is incremental as it builds on existing median-of-means techniques.
The paper tackles the problem of parameter estimation and loss minimization under heavy-tailed distributions by proposing a generalization of the median-of-means estimator, achieving a constant factor approximation to optimal least squares loss with only $ ilde{O}(d\log(1/δ))$ samples for $d$-dimensional linear regression.
This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the technique can be used for approximate minimization of smooth and strongly convex losses, and specifically for least squares linear regression. For instance, our $d$-dimensional estimator requires just $\tilde{O}(d\log(1/δ))$ random samples to obtain a constant factor approximation to the optimal least squares loss with probability $1-δ$, without requiring the covariates or noise to be bounded or subgaussian. We provide further applications to sparse linear regression and low-rank covariance matrix estimation with similar allowances on the noise and covariate distributions. The core technique is a generalization of the median-of-means estimator to arbitrary metric spaces.