# Robust Mean Estimation Without Moments for Symmetric Distributions

arXiv: https://arxiv.org/abs/2302.10844 · HTML: https://mlsanity.com/paper/2302.10844/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 21 Feb 2023.

## Builds on (most cited first, 25 of 25)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally](https://mlsanity.com/paper/2110.11853/) (2021)
- [Optimal Mean Estimation without a Variance](https://mlsanity.com/paper/2011.12433/) (2020)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Consistent regression when oblivious outliers overwhelm](https://mlsanity.com/paper/2009.14774/) (2020)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians](https://mlsanity.com/paper/2301.09024/) (2023)

## Abstract (arXiv)

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.