Robust subgaussian estimation of a mean vector in nearly linear time

Jules Depersin, Guillaume Lecué

We construct an algorithm, running in time $\tilde{\mathcal{O}}(Nd+uKd)$, which is robust to outliers and heavy-tailed data and which achieves the subgaussian rate from [Lugosi,…