pith. sign in

arxiv: 1906.11366 · v1 · pith:GDDKMDJBnew · submitted 2019-06-26 · 💻 cs.DS · cs.LG· math.ST· stat.ML· stat.TH

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

Yihe Dong , Samuel B. Hopkins , Jerry Li This is my paper

Pith reviewed 2026-05-25 14:43 UTC · model grok-4.3

classification 💻 cs.DS cs.LGmath.STstat.MLstat.TH
keywords robust mean estimationoutlier detectionquantum entropyhigh-dimensional statisticsalgorithmic robustness
0
0 comments X

The pith

Quantum entropy regularization yields the first nearly-linear time algorithm for optimal robust mean estimation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces QUE-scoring, an outlier scoring method that relies on quantum entropy regularization. For the robust mean estimation problem, where an adversary corrupts an epsilon fraction of n samples in d dimensions, this produces the first algorithm that achieves the statistically optimal error rate while running in Õ(nd) time. Prior fastest methods required Õ(min(nd/ε^6, nd²)) time. For outlier detection the same scoring rule is shown through experiments to assign higher scores to corrupted points more reliably than earlier heuristics on both synthetic and real data.

Core claim

QUE-scoring based on quantum entropy regularization produces an outlier score that suffices to filter corruptions at the optimal statistical rate while permitting a nearly-linear time filtering procedure, giving the first algorithm for robust mean estimation that is simultaneously statistically optimal and Õ(nd) in all parameters.

What carries the argument

QUE-scoring, the outlier score obtained by minimizing a quantum-entropy-regularized objective over the empirical distribution.

If this is right

  • Robust mean estimation can now be solved in time linear in the input size while matching information-theoretic error bounds.
  • The same scoring rule extends directly to the outlier detection task and can be evaluated on any finite data set.
  • Any downstream procedure that consumes a robust mean estimate can inherit both the statistical guarantee and the improved speed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the regularization can be computed via standard convex optimization primitives, the approach may extend to other high-dimensional estimation tasks that rely on filtering.
  • The experimental gains on real data suggest the score may capture geometric structure beyond what is proved for the mean estimation case.

Load-bearing premise

The quantum entropy regularization produces an outlier score whose properties suffice for both the optimal statistical rate and the nearly-linear runtime.

What would settle it

An explicit construction of a distribution and corruption pattern where QUE-scoring either fails to achieve the optimal error rate or requires superlinear time in d or n.

Figures

Figures reproduced from arXiv: 1906.11366 by Jerry Li, Samuel B. Hopkins, Yihe Dong.

Figure 1
Figure 1. Figure 1: (a-f): We plot the difference between ROCAUC performance of QUE and naive spectral (a-c), `2 scoring (d-f) on all three data sets, as α varies. Error bars represent one empirical standard deviation in 20 trials. Note that in all three cases the mean improvement in ROCAUC score given by QUE is at least one standard deviation above 0 for a wide range of α. Observe also that in synthetic data (which most clos… view at source ↗
Figure 2
Figure 2. Figure 2: ROCAUC scores on InternetAds dataset from [5]. Note that [PITH_FULL_IMAGE:figures/full_fig_p037_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: We plot histograms of the following collection [PITH_FULL_IMAGE:figures/full_fig_p037_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: We plot the improvement of ROCAUC scores of our approximate [PITH_FULL_IMAGE:figures/full_fig_p038_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Similar to above, these show the improvement of ROCAUC scores of our approximate [PITH_FULL_IMAGE:figures/full_fig_p039_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Scores under approximate whitening with 30% of eigenvalues and eigenvectors, as well as using a [PITH_FULL_IMAGE:figures/full_fig_p039_6.png] view at source ↗
read the original 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 $\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 https://github.com/twistedcubic/que-outlier-detection .

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper introduces QUE-scoring, an outlier scoring method based on quantum entropy regularization. For robust mean estimation under adversarial corruption, it claims the first algorithm achieving optimal error rates together with nearly-linear runtime Õ(nd) in all parameters, improving on the prior fastest runtime of Õ(min(nd/ε⁶, nd²)). For outlier detection it reports that QUE-scoring outperforms prior methods on synthetic and real data, with accompanying code release.

Significance. If the stated guarantees hold, the work supplies the first nearly-linear-time algorithm for high-dimensional robust mean estimation that simultaneously attains the information-theoretically optimal error rate; this removes a long-standing computational-statistical gap in the area. The experimental evaluation of QUE-scoring for outlier detection supplies reproducible evidence of practical improvement. The public code release for the experiments is a clear strength.

minor comments (2)
  1. [Abstract] The abstract states the runtime as Õ(nd) 'in all parameters'; verify that the full runtime analysis in the body explicitly accounts for the dependence on the failure probability δ and the corruption fraction ε (typically hidden inside the Õ notation).
  2. Notation for the quantum entropy regularizer and the resulting score function should be introduced once in a dedicated preliminary subsection and then used consistently; occasional re-definition risks minor confusion for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the recognition of the significance of achieving optimal error rates with nearly-linear runtime for robust mean estimation, and the recommendation to accept. We are also grateful for the acknowledgment of the experimental evaluation and code release for outlier detection.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces QUE-scoring via quantum entropy regularization as an independent construction and supplies explicit derivations for its outlier scoring properties, the filtering procedure, and the runtime analysis. These establish the optimal error rate and Õ(nd) runtime under the stated distributional assumptions without reducing any load-bearing claim to a self-definition, a fitted input renamed as prediction, or a self-citation chain. No equations or steps in the provided material exhibit the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work relies on the standard ε-corruption model in robust statistics and introduces QUE-scoring as a new regularization technique; no free parameters or additional invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Data consists of n independent samples from a distribution on R^d with an ε-fraction adversarially corrupted.
    This is the standard setup stated for both robust mean estimation and outlier detection problems.
invented entities (1)
  • QUE-scoring no independent evidence
    purpose: Outlier scoring via quantum entropy regularization
    New scoring method introduced to enable both the theoretical algorithm and the empirical improvements.

pith-pipeline@v0.9.0 · 5755 in / 1143 out tokens · 23047 ms · 2026-05-25T14:43:57.855900+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Unified Approach to Robust Mean Estimation

    stat.ML 2019-07 unverdicted novelty 7.0

    A connection between Huber's contamination and heavy-tailed models yields unified robust mean estimators that are both computationally efficient and statistically optimal under certain conditions.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Robust estimators in high-dimensions without the computational intractability

    Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing , 48(2):742–864, 2019

    work page 2019

  2. [2]

    Agnostic estimation of mean and covariance

    Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 665–674. IEEE, 2016

    work page 2016

  3. [3]

    High-dimensional robust mean estimation in nearly-linear time

    Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2755–2771. SIAM, 2019

    work page 2019

  4. [4]

    Being robust (in high dimensions) can be practical

    Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 999–1008. JMLR. org, 2017

    work page 2017

  5. [5]

    On the evaluation of unsupervised outlier detection: mea- sures, datasets, and an empirical study

    Guilherme O Campos, Arthur Zimek, J¨ org Sander, Ricardo JGB Campello, Barbora Micenkov´ a, Erich Schubert, Ira Assent, and Michael E Houle. On the evaluation of unsupervised outlier detection: mea- sures, datasets, and an empirical study. Data Mining and Knowledge Discovery , 30(4):891–927, 2016

    work page 2016

  6. [6]

    The multiplicative weights update method: a meta- algorithm and applications

    Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Computing , 8(1):121–164, 2012

    work page 2012

  7. [7]

    Rejection of outliers

    Frank J Anscombe. Rejection of outliers. Technometrics, 2(2):123–146, 1960

    work page 1960

  8. [8]

    A survey of sampling from contaminated distributions

    John W Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pages 448–485, 1960

    work page 1960

  9. [9]

    Robust estimation of a location parameter

    Peter J Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pages 492–518. Springer, 1992

    work page 1992

  10. [10]

    Mathematics and the picturing of data

    John W Tukey. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975 , volume 2, pages 523–531, 1975

    work page 1975

  11. [11]

    Principled approaches to robust machine learning and beyond

    Jerry Zheng Li. Principled approaches to robust machine learning and beyond. PhD thesis, Massachusetts Institute of Technology, 2018

    work page 2018

  12. [12]

    Robust Learning: Information Theory and Algorithms

    Jacob Steinhardt. Robust Learning: Information Theory and Algorithms . PhD thesis, Stanford Univer- sity, 2018

    work page 2018

  13. [13]

    Faster algorithms for high-dimensional robust covariance estimation

    Yu Cheng, Ilias Diakonikolas, Rong Ge, and David Woodruff. Faster algorithms for high-dimensional robust covariance estimation. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019)

    work page 2019

  14. [14]

    Robust subgaussian estimation of a mean vector in nearly linear time

    Guillaume Lecu´ e and Jules Depersin. Robust subgaussian estimation of a mean vector in nearly linear time. arXiv preprint arXiv:1906.03058 , 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1906

  15. [15]

    Sub-gaussian estimators of the mean of a random vector

    G´ abor Lugosi, Shahar Mendelson, et al. Sub-gaussian estimators of the mean of a random vector. The Annals of Statistics , 47(2):783–794, 2019

    work page 2019

  16. [16]

    Identification of outliers , volume 11

    Douglas M Hawkins. Identification of outliers , volume 11. Springer, 1980

    work page 1980

  17. [17]

    A unified notion of outliers: Properties and computation

    Edwin M Knorr and Raymond T Ng. A unified notion of outliers: Properties and computation. In KDD, volume 97, pages 219–222, 1997. 40

    work page 1997

  18. [18]

    Algorithms for mining distancebased outliers in large datasets

    Edwin M Knox and Raymond T Ng. Algorithms for mining distancebased outliers in large datasets. In Proceedings of the international conference on very large data bases , pages 392–403. Citeseer, 1998

    work page 1998

  19. [19]

    Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures

    Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 73–84. IEEE, 2017

    work page 2017

  20. [20]

    Spectral sparsification and regret minimization beyond matrix multiplicative updates

    Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 237–245. ACM, 2015

    work page 2015

  21. [21]

    Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP) , pages 1532–1543, 2014

    work page 2014

  22. [22]

    May 2019

    https://en.wikipedia.org/wiki/Wikipedia:Today’s_featured_article/May_2019. May 2019. Wikimedia Foundation

    work page 2019

  23. [23]

    Efficient algorithms for mining outliers from large data sets

    S Ramaswamy, R Rastogi, and K Shim. Efficient algorithms for mining outliers from large data sets. Proceedings of the ACM international conference on management of data (SIGMOD) , pages 427–438, 2000

    work page 2000

  24. [24]

    Efficient algorithms for mining outliers from large data sets

    MM Breunig, HP Kriegel, R Ng, and J Sander. Efficient algorithms for mining outliers from large data sets. Proceedings of the ACM international conference on management of data (SIGMOD) , pages 93–104, 2000

    work page 2000

  25. [25]

    A fast algorithm for the minimum covariance determinant estimator

    Peter J Rousseeuw and Katrien Van Driessen. A fast algorithm for the minimum covariance determinant estimator. Technometrics, 41(3):212–223, 1999

    work page 1999

  26. [26]

    Isolation forest

    Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In 2008 Eighth IEEE International Conference on Data Mining , pages 413–422. IEEE, 2008

    work page 2008

  27. [27]

    Scikit-learn: Machine learning in python

    Fabian Pedregosa, Ga¨ el Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. Journal of machine learning research , 12(Oct):2825–2830, 2011

    work page 2011

  28. [28]

    How Hard Is Robust Mean Estimation?

    Samuel B Hopkins and Jerry Li. How hard is robust mean estimation? arXiv preprint arXiv:1903.07870, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  29. [29]

    Extensions of lipschitz maps into banach spaces

    William B Johnson, Joram Lindenstrauss, and Gideon Schechtman. Extensions of lipschitz maps into banach spaces. Israel Journal of Mathematics , 54(2):129–138, 1986

    work page 1986

  30. [30]

    Hanson-wright inequality and sub-gaussian concentration

    Mark Rudelson, Roman Vershynin, et al. Hanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013

    work page 2013

  31. [31]

    Fast sdp algorithms for constraint satisfaction problems

    David Steurer. Fast sdp algorithms for constraint satisfaction problems. In Proceedings of the twenty- first annual ACM-SIAM symposium on Discrete Algorithms , pages 684–697. Society for Industrial and Applied Mathematics, 2010

    work page 2010

  32. [32]

    A new scaling and squaring algorithm for the matrix exponential

    Awad H Al-Mohy and Nicholas J Higham. A new scaling and squaring algorithm for the matrix exponential. SIAM Journal on Matrix Analysis and Applications , 31(3):970–989, 2009

    work page 2009

  33. [33]

    The fast johnson–lindenstrauss transform and approximate nearest neighbors

    Nir Ailon and Bernard Chazelle. The fast johnson–lindenstrauss transform and approximate nearest neighbors. SIAM Journal on computing , 39(1):302–322, 2009

    work page 2009

  34. [34]

    Practical and optimal lsh for angular distance

    Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal lsh for angular distance. In Advances in Neural Information Processing Systems , pages 1225–1233, 2015. 41

    work page 2015

  35. [35]

    An introduction to matrix concentration inequalities

    Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends R⃝ in Machine Learning, 8(1-2):1–230, 2015. A Deferred details from Section 2 A.1 Proof of Lemma 2.3 The algorithm is straightforward: choose a random point in S, and check if strictly more than n/2 points lie within a ball of radius 2 r around this point. If ...

    work page 2015