Metraipolis › archive › dc_bd870237ec60
From Weak to Strong Testing in Gaussian Models — arXiv:2609.36050
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.36050
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:02:29.794Z
- SHA-256 of the archived text
2b34ec55c8d3ce9820ffbe912bacc884bf278b4c3756fa0c2f3750cd3c0f3059- Stable URL of this page
https://metraipolis.com/documento/dc_bd870237ec60
How to cite
From Weak to Strong Testing in Gaussian Models — arXiv:2609.36050 — arXiv (en), https://arxiv.org/abs/2609.36050 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bd870237ec60 (Metraipolis archive dc_bd870237ec60, sha256 2b34ec55c8d3ce9820ffbe912bacc884bf278b4c3756fa0c2f3750cd3c0f3059)
BibTeX
@misc{dcbd870237ec60,
title = {From Weak to Strong Testing in Gaussian Models — arXiv:2609.36050},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.36050},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bd870237ec60; sha256 2b34ec55c8d3ce9820ffbe912bacc884bf278b4c3756fa0c2f3750cd3c0f3059},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36050. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the computational complexity of hypothesis testing in the spiked Wigner model, a prototypical model for detecting low-rank structure in a large random matrix. Below the "BBP" eigenvalue transition, it is expected that strong detection --- with both type I and II errors vanishing --- requires exponential time. Assuming this as a conjecture, we determine the limits of polynomial-time weak detection, exactly characterizing the possible tradeoffs between type I and II errors. Specifically, the optimal tradeoff is achieved by a particular linear spectral statistic. Thus, the question of weak detection is entirely reduced to that of strong detection. The proof builds on ideas of Nagda-Raghavendra (2025) and Moitra-Wein (2025). The low-degree likelihood ratio (LDLR) plays a key role: any test that slightly beats the LDLR can be boosted to have an even higher success probability. This leads us to establish a computational analogue of the Neyman-Pearson lemma for a subclass of additive Gaussian models: for a given super-polynomial runtime, the best possible tradeoff between type I and II errors is either the one achieved by thresholding the LDLR, or the trivial tradeoff that results from strong detection. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.ST). Categorie arXiv: Statistics Theory (math.ST) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2609.36050 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T17:35:36.896Z dalla pagina https://arxiv.org/catchup/math.ST/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).