Fast Mean Estimation with Sub-Gaussian Rates

2019/02/06 by Yeshwanth Cherapanamjeri, Cherapanamjeri, Yeshwanth, Nicolas Flammarion +3 · 1 citation
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1902.01998

openalex publication_date 2019/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose an estimator for the mean of a random vector in ℝ^d that can be computed in time O(n⁴+n²d) 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.

Citations

• Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression

Cited by

• Improved Concentration for Mean Estimators via Shrinkage

Related

• Mean Estimation with Sub-Gaussian Rates in Polynomial Time
• A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
• Sub-Gaussian estimators of the mean of a random vector
• Robust subgaussian estimation of a mean vector in nearly linear time
• Optimal Sub-Gaussian Mean Estimation in ℝ