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).