mlsanityData to 7 Oct 2026

Fast Mean Estimation with Sub-Gaussian Rates

arXiv 1902.01998 ↗First posted 6 Feb 2019math.ST cs.DS cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

We propose an estimator for the mean of a random vector in ℝd that can be computed in time O(n4+n2d) for n i.i.d.~samples and that has error bounds matching the sub-Gaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we make no assumptions about higher-order moments. Like the polynomial time estimator introduced by Hopkins, 2018, which is based on the sum-of-squares hierarchy, our estimator achieves optimal statistical efficiency in this challenging setting, but it has a significantly faster runtime and a simpler analysis.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 8; 2023: 6; 2024: 2.

18 papers.

Sort:

  1. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  2. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  3. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  4. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  5. 2022List-Decodable Covariance Estimationcited by 8
  6. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  7. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  8. 2022Robust Methods for High-Dimensional Linear Learningcited by 5
  9. 2023High-dimensional Location Estimation via Norm Concentration for Subgamma Vectorscited by 5
  10. 2023Finite-Sample Symmetric Mean Estimation with Fisher Information Ratecited by 5
  11. 2023Geometry-Aware Adaptation for Pretrained Modelscited by 5
  12. 2022Robust supervised learning with coordinate gradient descentcited by 3
6 more
  1. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  2. 2024The Empirical Mean is Minimax Optimal for Local Glivenko-Cantellicited by 2
  3. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  4. 2022A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noisecited by 0
  5. 2022Robustifying Markowitzcited by 0
  6. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0