Concentration study of M-estimators using the influence function

Abstract

We present a new finite-sample analysis of M-estimators of locations in ${\mathbb{R}}^d$ using the tool of the influence function. In particular, we show that the deviations of an M-estimator can be controlled thanks to its influence function (or its score function) and then, we use concentration inequality on M-estimators to investigate the robust estimation of the mean in high dimension in a corrupted setting (adversarial corruption setting) for bounded and unbounded score functions. For a sample of size $n$ and covariance matrix $\Sigma$, we attain the minimax speed $\sqrt{Tr(\Sigma )/n}+\sqrt{\Vert \Sigma {\Vert }_{op}\log (1/\delta )/n}$ with probability larger than $1-\delta$ in a heavy-tailed setting. One of the major advantages of our approach compared to others recently proposed is that our estimator is tractable and fast to compute even in very high dimension with a complexity of $O(nd\log (Tr(\Sigma )))$ where $n$ is the sample size and $\Sigma$ is the covariance matrix of the inliers. In practice, the code that we make available for this article proves to be very fast.

References in corpus (11)

• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• A New Perspective on Robust $M$-Estimation: Finite Sample Theory and Applications to Dependence-Adjusted Multiple Testing
• Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
• Fast Mean Estimation with Sub-Gaussian Rates
• Robust estimation via generalized quasi-gradients
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability
• Excess risk bounds in robust empirical risk minimization
• How Hard Is Robust Mean Estimation?
• Lecture Notes: Selected topics on robust statistical learning theory
• Robust subgaussian estimation of a mean vector in nearly linear time
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization

Cited by in corpus (1)

• On Weighted Multivariate Sign Functions