# Robust subgaussian estimation of a mean vector in nearly linear time

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2019.

## Built on by (most cited first, 30 of 37)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [On Goodhart's law, with an application to value alignment](https://mlsanity.com/paper/2410.09638/) (2024)
- [Huber-Robust Confidence Sequences](https://mlsanity.com/paper/2301.09573/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (2022)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Robust Mean Estimation under Quantization](https://mlsanity.com/paper/2601.07074/) (2026)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Robust Estimation for Nonparametric Families via Generative Adversarial Networks](https://mlsanity.com/paper/2202.01269/) (2022)
- [Robust Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)
- [Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error](https://mlsanity.com/paper/2410.17230/) (2024)
- [The Broader Landscape of Robustness in Algorithmic Statistics](https://mlsanity.com/paper/2412.02670/) (2024)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)
- [Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm](https://mlsanity.com/paper/2303.07287/) (2023)
- [Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates](https://mlsanity.com/paper/2408.09891/) (2024)

## Abstract (arXiv)

We construct an algorithm, running in time tildemathcal O(N d + uK d), which is robust to outliers and heavy-tailed data and which achieves the subgaussian rate from [Lugosi, Mendelson] beginequationlabeleq:introsubgausrate √fracrm Tr(Sigma)N+√frac||Sigma||opKN endequationwith probability at least 1-exp(-c0K)-exp(-c1 u) where Sigma is the covariance matrix of the informative data, K∈1, ldots, K is some parameter (number of block means) and u>0 is another parameter of the algorithm. This rate is achieved when K≥ c1 |mathcal O| where |mathcal O| is the number of outliers in the database and under the only assumption that the informative data have a second moment. The algorithm is fully data-dependent and does not use in its construction the proportion of outliers nor the rate above. Its construction combines recently developed tools for Median-of-Means estimators and covering-Semi-definite Programming [Chen, Diakonikolas, Ge] and [Peng, Tangwongsan, Zhang].