|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
16 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Precise Error Rates for Computationally Efficient Testing | | Ankur Moitra
; Alexander S. Wein
; | | Date: |
1 Nov 2023 | | Abstract: | We revisit the fundamental question of simple-versus-simple hypothesis
testing with an eye towards computational complexity, as the statistically
optimal likelihood ratio test is often computationally intractable in
high-dimensional settings. In the classical spiked Wigner model (with a general
i.i.d. spike prior) we show that an existing test based on linear spectral
statistics achieves the best possible tradeoff curve between type I and type II
error rates among all computationally efficient tests, even though there are
exponential-time tests that do better. This result is conditional on an
appropriate complexity-theoretic conjecture, namely a natural strengthening of
the well-established low-degree conjecture. Our result shows that the spectrum
is a sufficient statistic for computationally bounded tests (but not for all
tests).
To our knowledge, our approach gives the first tool for reasoning about the
precise asymptotic testing error achievable with efficient computation. The
main ingredients required for our hardness result are a sharp bound on the norm
of the low-degree likelihood ratio along with (counterintuitively) a positive
result on achievability of testing. This strategy appears to be new even in the
setting of unbounded computation, in which case it gives an alternate way to
analyze the fundamental statistical limits of testing. | | Source: | arXiv, 2311.00289 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER