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
$\widetilde{O}(nd)$ in all parameters, improving on the previous fastest
running time $\widetilde{O}(\min(nd/\varepsilon^6, nd^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
this https URL .

本文研究高维鲁棒统计中的两个问题：鲁棒均值估计和异常值检测。我们提出了一种新的异常值评分方法，称之为 QUE 评分，它基于量子熵正则化，可以显著提高异常值检测的性能。在鲁棒均值估计方面，我们的算法具有最优误差率和近似线性的运行时间，改善了之前最快运行时间的算法。