Robust Mean Estimation Without Moments for Symmetric Distributions

We study the problem of robustly estimating the mean or location parameter without moment assumptions. We show that for a large class of symmetric distributions, the same error as in the Gaussian setting can be achieved efficiently. The distributions we study include products of arbitrary symmetric one-dimensional distributions, such as product Cauchy distributions, as well as elliptical distributions. For product distributions and elliptical distributions with known scatter (covariance) matrix, we show that given an varepsilon-corrupted sample, we can with probability at least 1-δ estimate its location up to error O(varepsilon √log(1/varepsilon)) using tfracdlog(d) + log(1/δ)varepsilon2 log(1/varepsilon) samples. This result matches the best-known guarantees for the Gaussian distribution and known SQ lower bounds (up to the log(d) factor). For elliptical distributions with unknown scatter (covariance) matrix, we propose a sequence of efficient algorithms that approaches this optimal error. Specifically, for every k ∈ mathbbN, we design an estimator using time and samples tildeO(dk) achieving error O(varepsilon^1-frac12k). This matches the error and running time guarantees when assuming certifiably bounded moments of order up to k. For unknown covariance, such error bounds of o(√varepsilon) are not even known for (general) sub-Gaussian distributions. Our algorithms are based on a generalization of the well-known filtering technique. We show how this machinery can be combined with Huber-loss-based techniques to work with projections of the noise that behave more nicely than the initial noise. Moreover, we show how SoS proofs can be used to obtain algorithmic guarantees even for distributions without a first moment. We believe that this approach may find other applications in future works.