×

zbMATH — the first resource for mathematics

Loss minimization and parameter estimation with heavy tails. (English) Zbl 1360.62380
Summary: 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/\delta))\) random samples to obtain a constant factor approximation to the optimal least squares loss with probability \(1-\delta\), 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.

MSC:
62J05 Linear regression; mixed models
62F10 Point estimation
62J07 Ridge regression; shrinkage estimators (Lasso)
PDF BibTeX XML Cite
Full Text: Link