mlsanityData to 7 Oct 2026

Robust subgaussian estimation of a mean vector in nearly linear time

arXiv 1906.03058 ↗First posted 7 Jun 2019math.ST math.OC stat.THcited by 37

Not on the map. Why?

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].

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

37 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. 2022On the Impossible Safety of Large AI Modelscited by 27
  5. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  6. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  7. 2024High-probability minimax lower boundscited by 11
  8. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  9. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  10. 2024On Goodhart's law, with an application to value alignmentcited by 9
  11. 2023Huber-Robust Confidence Sequencescited by 7
  12. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
25 more
  1. 2022Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithmcited by 6
  2. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  3. 2022Robust Methods for High-Dimensional Linear Learningcited by 5
  4. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  5. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  6. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  7. 2026Robust Mean Estimation under Quantizationcited by 4
  8. 2022Robust supervised learning with coordinate gradient descentcited by 3
  9. 2022Robust Estimation for Nonparametric Families via Generative Adversarial Networkscited by 3
  10. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  11. 2024A provable initialization and robust clustering method for general mixture modelscited by 2
  12. 2024Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Errorcited by 2
  13. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  14. 2021Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Timecited by 1
  15. 2022Nearly minimax robust estimator of the mean vector by iterative spectral dimension reductioncited by 1
  16. 2023Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Normcited by 1
  17. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  18. 2022An Efficient Minimax Optimal Estimator For Multivariate Convex Regressioncited by 0
  19. 2022A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noisecited by 0
  20. 2022Robustifying Markowitzcited by 0
  21. 2023Online Heavy-tailed Change-point detectioncited by 0
  22. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  23. 2024Heavy-tailed Contamination is Easier than Adversarial Contaminationcited by 0
  24. 2025Robust Estimation Under Heterogeneous Corruption Ratescited by 0
  25. 2026Mean Testing under Truncation beyond Gaussiancited by 0