Robust Estimators are Hard to Compute

72 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Least quantile regression via modern optimization (2013, methodology): “Bernholt (2005a) describe a randomized algorithm for computing the LMS running in O ( n p ) time and O ( n ) space, for ﬁxed p .”
Robust Inference via Generative Classifiers for Handling Noisy Labels (2019, background): “Even though the MCD estimator has several advantages, the optimization (2) is computationally intractable (i.e., NP-hard) to solve (Bernholt, 2006).”
Outlier-robust moment-estimation via sum-of-squares (2017, background): “However, many robust estimators coming out of this research eﬀort are computationally eﬃcient only for low-dimensional distributions (because the running time is say exponential in the dimension d ) [Ber06].”
Mixture models, robustness, and sum of squares proofs (2017, methodology): “compute [13, 39] and the best known algorithms require exp(d) time in general.”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, background): “This curse of dimensionality in the running time holds for essentially all known estimators in robust statistics [8].”
Robust Estimators in High Dimensions without the Computational Intractability (2016, unknown): “Keywords-unsupervised learning, statistical learning, density estimation robust algorithm I. INTRODUCTION”