Skip to main content

Faster Algorithms for High-Dimensional Robust Covariance Estimation

Publication ,  Conference
Cheng, Y; Diakonikolas, I; Ge, R; Woodruff, DP
Published in: Proceedings of Machine Learning Research
January 1, 2019

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 = Ω(e d2/ε2) samples from a d-dimensional Gaussian distribution, an ε-fraction of which may be arbitrarily corrupted, our algorithm runs in time Oe(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 Ω(e d2ω) when ε = Ω(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.

Duke Scholars

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2019

Volume

99

Start / End Page

727 / 757
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cheng, Y., Diakonikolas, I., Ge, R., & Woodruff, D. P. (2019). Faster Algorithms for High-Dimensional Robust Covariance Estimation. In Proceedings of Machine Learning Research (Vol. 99, pp. 727–757).
Cheng, Y., I. Diakonikolas, R. Ge, and D. P. Woodruff. “Faster Algorithms for High-Dimensional Robust Covariance Estimation.” In Proceedings of Machine Learning Research, 99:727–57, 2019.
Cheng Y, Diakonikolas I, Ge R, Woodruff DP. Faster Algorithms for High-Dimensional Robust Covariance Estimation. In: Proceedings of Machine Learning Research. 2019. p. 727–57.
Cheng, Y., et al. “Faster Algorithms for High-Dimensional Robust Covariance Estimation.” Proceedings of Machine Learning Research, vol. 99, 2019, pp. 727–57.
Cheng Y, Diakonikolas I, Ge R, Woodruff DP. Faster Algorithms for High-Dimensional Robust Covariance Estimation. Proceedings of Machine Learning Research. 2019. p. 727–757.

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2019

Volume

99

Start / End Page

727 / 757