Timezone: »

 
Spotlight
Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
Yihe Dong · Samuel Hopkins · Jerry Li

Tue Dec 10 10:40 AM -- 10:45 AM (PST) @ West Exhibition Hall A
in Track 2 Session 1 »
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/\e^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.
[ Paper]  [ Poster]  [ Slides] 

Author Information

Yihe Dong (Microsoft)

Machine learning researcher and engineer interested in geometric deep learning, graph representation learning, and natural language processing.

Samuel Hopkins (UC Berkeley)
Samuel Hopkins

*algorithms, theory of machine learning, semidefinite programming, sum of squares method, bicycles. he/him.* I am a mathematician and computer scientist. I am employed as an Assistant Professor at MIT, in the [Theory of Computing](https://toc.csail.mit.edu/) group in the [Department of Electrical Engineering and Computer Science](https://www.eecs.mit.edu/). Previously, I was a [Miller](http://miller.berkeley.edu/) fellow in the [theory group](http://theory.cs.berkeley.edu/) at UC Berkeley, hosted by [Prasad Raghavendra](https://people.eecs.berkeley.edu/~prasad/) and [Luca Trevisan](https://lucatrevisan.github.io/). Before that, I got my PhD at [Cornell](https://www.cs.cornell.edu/research/theory), advised by [David Steurer](http://www.dsteurer.org/).

Jerry Li (Microsoft)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors