Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
Mirrored from arXiv — Machine Learning for archival readability. Support the source by reading on the original site.
Computer Science > Machine Learning
Title:Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
Abstract:We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.
| Subjects: | Machine Learning (cs.LG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Probability (math.PR); Statistics Theory (math.ST) |
| MSC classes: | 60C05, 68Q87, 68Q17 |
| Cite as: | arXiv:2606.05266 [cs.LG] |
| (or arXiv:2606.05266v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2606.05266
arXiv-issued DOI via DataCite (pending registration)
|
Access Paper:
- View PDF
- HTML (experimental)
- TeX Source
Current browse context:
References & Citations
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
More from arXiv — Machine Learning
-
The Evaluation Blind Spot: A Stereological Theory of Benchmark Coverage for Large Language Models
Jun 5
-
ERRORQUAKE: Heavy-Tailed Error Severity Distributions in Open-Weight Large Language Models
Jun 5
-
Staged Factorial Screening for Budget-Constrained Micro-Pretraining
Jun 5
-
PyCC.id: A package for hypothesis-driven equation discovery with structural identifiability
Jun 5
Discussion (0)
Sign in to join the discussion. Free account, 30 seconds — email code or GitHub.
Sign in →No comments yet. Sign in and be the first to say something.