mlsanityData to 7 Oct 2026

Mean Estimation with Sub-Gaussian Rates in Polynomial Time

arXiv 1809.07425 ↗First posted 19 Sep 2018math.ST cs.DS stat.THcited by 33

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 12; 2023: 5; 2024: 5; 2025: 1; 2026: 2.

33 papers.

Sort:

  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  4. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  5. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  6. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
  7. 2021Near-Optimal Quantum Algorithms for Multivariate Mean Estimationcited by 16
  8. 2021Quantum Sub-Gaussian Mean Estimatorcited by 15
  9. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  10. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  11. 2024High-probability minimax lower boundscited by 11
  12. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
21 more
  1. 2022List-Decodable Covariance Estimationcited by 8
  2. 2023Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptionscited by 7
  3. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  4. 2022Higher degree sum-of-squares relaxations robust against oblivious outlierscited by 6
  5. 2022Robust Methods for High-Dimensional Linear Learningcited by 5
  6. 2022Efficient List-Decodable Regression using Batchescited by 5
  7. 2023Finite-Sample Symmetric Mean Estimation with Fisher Information Ratecited by 5
  8. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  9. 2022Robust supervised learning with coordinate gradient descentcited by 3
  10. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  11. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  12. 2024The Empirical Mean is Minimax Optimal for Local Glivenko-Cantellicited by 2
  13. 2024Robust Gradient Descent for Phase Retrievalcited by 2
  14. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  15. 2026RoPoLL: Robust Panel of LLM Judgescited by 2
  16. 2022Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Modelscited by 0
  17. 2022A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noisecited by 0
  18. 2022Robustifying Markowitzcited by 0
  19. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  20. 2025Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Pointcited by 0
  21. 2026Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Boundcited by 0