# Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 5 Apr 2022.

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

- [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)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [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)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Robust subgaussian estimation of a mean vector in nearly linear time](https://mlsanity.com/paper/1906.03058/) (2019)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Outlier-Robust Sparse Estimation via Non-Convex Optimization](https://mlsanity.com/paper/2109.11515/) (2021)
- [ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels](https://mlsanity.com/paper/1910.10923/) (2019)
- [Confidence regions and minimax rates in outlier-robust estimation on the probability simplex](https://mlsanity.com/paper/1902.04650/) (2019)

## Built on by (most cited first, 1 of 1)

- [Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians](https://mlsanity.com/paper/2301.09024/) (2023)

## Abstract (arXiv)

We study the problem of robust estimation of the mean vector of a sub-Gaussian distribution. We introduce an estimator based on spectral dimension reduction (SDR) and establish a finite sample upper bound on its error that is minimax-optimal up to a logarithmic factor. Furthermore, we prove that the breakdown point of the SDR estimator is equal to 1/2, the highest possible value of the breakdown point. In addition, the SDR estimator is equivariant by similarity transforms and has low computational complexity. More precisely, in the case of n vectors of dimension p -- at most varepsilon n out of which are adversarially corrupted -- the SDR estimator has a squared error of order big(fracr_Sigman + varepsilon2log(1/varepsilon)big)log p and a running time of order p3 + n p2. Here, r_Sigma≤ p is the effective rank of the covariance matrix of the reference distribution. Another advantage of the SDR estimator is that it does not require knowledge of the contamination rate and does not involve sample splitting. We also investigate extensions of the proposed algorithm and of the obtained results in the case of (partially) unknown covariance matrix.