Can I read Precise Error Rates for Computationally Efficient Testing on EtoBox?

Precise Error Rates for Computationally Efficient Testing by Ankur Moitra, Alexander S. Wein is a book available to read on EtoBox.

What is Precise Error Rates for Computationally Efficient Testing about?

The Annals of Statistics, 2025, Vol. 53, No. 2, 854-878We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye toward computational complexity, as the statisticallyoptimal likelihood ratio test is often computationally intractable in highdimensional settings. In the classical spiked Wigner model with a generali.i.d. spike prior, we show (conditional on a conjecture) that an existing testbased on linear spectral statistics achieves the best possible trade-off curvebetween type-I and type-II error rates among all computationally efficienttests, even though there are exponential-time tests that do better. This result isconditional on an appropriate complexity-theoretic conjecture, namely a natural strengthening of the well-established low-degree conjecture. Our resultshows that the spectrum is a sufficient statistic for computationally boundedtests (but not for all tests).To our knowledge, our approach gives the first tool for reasoning aboutthe precise asymptotic testing error achievable with efficient computation.The main ingredients required for our hardness result are a sharp bound onthe norm of the low-degree likelihood ratio along with (coun

Author

Ankur Moitra, Alexander S. Wein

Published

2025

Language

EN