Faster Algorithms for High-Dimensional Robust Covariance Estimation

Abstract

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=\tilde{\Omega }(d^2/{\epsilon }^2)$ samples from a $d$-dimensional Gaussian distribution, an $\epsilon$-fraction of which may be arbitrarily corrupted, our algorithm runs in time $\tilde{O}(d^{3.26})/\mathrm{poly}(\epsilon )$ and approximates the unknown covariance matrix to optimal error up to a logarithmic factor. Previous robust algorithms with comparable error guarantees all have runtimes $\tilde{\Omega }(d^{2\omega })$ when $\epsilon =\Omega (1)$, where $\omega$ is the exponent of matrix multiplication. We also provide evidence that improving the running time of our algorithm may require new algorithmic techniques.

References in corpus (3)

• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• High Dimensional Robust Sparse Regression
• Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Cited by in corpus (10)

• Generalized Resilience and Robust Statistics
• Robust estimation via generalized quasi-gradients
• Robust and Differentially Private Mean Estimation
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
• On Robust Mean Estimation under Coordinate-level Corruption
• Robust Estimation of Covariance Matrices: Adversarial Contamination and Beyond
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion
• Adversarial robust weighted Huber regression
• Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time