# Mean Estimation with Sub-Gaussian Rates in Polynomial Time

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2018.

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

- [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)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [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)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Finite-Sample Symmetric Mean Estimation with Fisher Information Rate](https://mlsanity.com/paper/2306.16573/) (2023)
- [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 Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)
- [The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli](https://mlsanity.com/paper/2410.02835/) (2024)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)
- [The Broader Landscape of Robustness in Algorithmic Statistics](https://mlsanity.com/paper/2412.02670/) (2024)
- [RoPoLL: Robust Panel of LLM Judges](https://mlsanity.com/paper/2606.30931/) (2026)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)
- [Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound](https://mlsanity.com/paper/2603.06851/) (2026)
- [Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models](https://mlsanity.com/paper/2206.02455/) (2022)

## Abstract (arXiv)

We study polynomial time algorithms for estimating the mean of a heavy-tailed multivariate random vector. We assume only that the random vector X has finite mean and covariance. In this setting, the radius of confidence intervals achieved by the empirical mean are large compared to the case that X is Gaussian or sub-Gaussian. We offer the first polynomial time algorithm to estimate the mean with sub-Gaussian-size confidence intervals under such mild assumptions. Our algorithm is based on a new semidefinite programming relaxation of a high-dimensional median. Previous estimators which assumed only existence of finitely-many moments of X either sacrifice sub-Gaussian performance or are only known to be computable via brute-force search procedures requiring time exponential in the dimension.