mlsanityData to 7 Oct 2026

Faster Algorithms for High-Dimensional Robust Covariance Estimation

arXiv 1906.04661 ↗First posted 11 Jun 2019cs.LG cs.DS math.STcited by 28

Not on the map. Why?

Abstract (arXiv)

We study the problem of estimating the covariance matrix of a high-dimensional distribution when a small constant fraction of the samples can be arbitrarily corrupted. Recent work gave the first polynomial time algorithms for this problem with near-optimal error guarantees for several natural structured distributions. Our main contribution is to develop faster algorithms for this problem whose running time nearly matches that of computing the empirical covariance. Given N = tildeOmega(d2/ε2) samples from a d-dimensional Gaussian distribution, an ε-fraction of which may be arbitrarily corrupted, our algorithm runs in time tildeO(d3.26)/poly(ε) and approximates the unknown covariance matrix to optimal error up to a logarithmic factor. Previous robust algorithms with comparable error guarantees all have runtimes tildeOmega(d2 ω) when ε = Omega(1), where ω is the exponent of matrix multiplication. We also provide evidence that improving the running time of our algorithm may require new algorithmic techniques.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 6; 2023: 8; 2024: 3; 2025: 3; 2026: 1.

28 papers.

Sort:

  1. 2021SPECTRE: Defending Against Backdoor Attacks Using Robust Statisticscited by 123
  2. 2021Robust and Differentially Private Mean Estimationcited by 66
  3. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  4. 2023From Robustness to Privacy and Backcited by 27
  5. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  6. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  7. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  8. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  9. 2023Robust Nonparametric Regression under Poisoning Attackcited by 11
  10. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  11. 2021Robust Estimation for Random Graphscited by 8
  12. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
16 more
  1. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  2. 2022Efficient List-Decodable Regression using Batchescited by 5
  3. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  4. 2023Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Errorcited by 4
  5. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
  6. 2021Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Timecited by 1
  7. 2022Nearly minimax robust estimator of the mean vector by iterative spectral dimension reductioncited by 1
  8. 2023Robust empirical risk minimization via Newton's methodcited by 1
  9. 2024A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimationcited by 1
  10. 2025Adversarial Robustness of Nonparametric Regressioncited by 1
  11. 2023Sparse Mean Estimation in Adversarial Settings via Incremental Learningcited by 0
  12. 2023Bayesian Reinforcement Learning for Automatic Voltage Control under Cyber-Induced Uncertaintycited by 0
  13. 2024Iterative thresholding for non-linear learning in the strong varepsilon-contamination modelcited by 0
  14. 2025Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussianscited by 0
  15. 2025Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programmingcited by 0
  16. 2026Computable Bernstein Certificates for Cross-Fitted Clipped Covariance Estimationcited by 0