Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection

Abstract

We study two problems in high-dimensional robust statistics: \emph{robust mean estimation} and \emph{outlier detection}. In robust mean estimation the goal is to estimate the mean $\mu$ of a distribution on ${\mathbb{R}}^d$ given $n$ independent samples, an $\epsilon$-fraction of which have been corrupted by a malicious adversary. In outlier detection the goal is to assign an \emph{outlier score} to each element of a data set such that elements more likely to be outliers are assigned higher scores. Our algorithms for both problems are based on a new outlier scoring method we call QUE-scoring based on \emph{quantum entropy regularization}. For robust mean estimation, this yields the first algorithm with optimal error rates and nearly-linear running time $\tilde{O}(nd)$ in all parameters, improving on the previous fastest running time $\tilde{O}(\min (nd/{\epsilon }^6,n{d}^2))$. For outlier detection, we evaluate the performance of QUE-scoring via extensive experiments on synthetic and real data, and demonstrate that it often performs better than previously proposed algorithms. Code for these experiments is available at https://github.com/twistedcubic/que-outlier-detection .

Cited by in corpus (6)

• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics
• Robust Regression Revisited: Acceleration and Improved Estimation Rates
• List-Decodable Mean Estimation in Nearly-PCA Time
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time
• High-Dimensional Robust Mean Estimation via Gradient Descent