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

arXiv1906.11366MaRDI QIDQ6321124

Jerry Li, Samuel B. Hopkins, Yihe Dong

Publication date: 26 June 2019

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 $varepsilon$-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 $widetildeO(nd)$ in all parameters, improving on the previous fastest running time $widetildeO(min(nd/varepsilo{n}^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 .

Has companion code repository: https://github.com/twistedcubic/que-outlier-detection

This page was built for publication: Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321124)