Recognition: unknown
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
Pith reviewed 2026-05-10 05:39 UTC · model grok-4.3
The pith
Mild low-degree testing bounds yield conditional computational lower bounds for recovery via contiguity and cross-validation.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By combining algorithmic contiguity with a cross-validation reduction that converts successful recovery into a hypothesis test with lopsided success probabilities, mild bounds on low-degree testing advantage are sufficient to obtain conditional computational lower bounds for recovery. The method recovers existing low-degree lower bounds for recovery in planted submatrix, planted dense subgraph, and stochastic block model via substantially simpler arguments, and it furnishes new evidence for conjectured computational thresholds, including the persistence of detection-recovery gaps, in multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer stochastic block模型
What carries the argument
algorithmic contiguity (which equates bounded low-degree advantage with algorithmic indistinguishability) paired with the cross-validation reduction (which maps recovery success to a hypothesis test whose two error probabilities are sufficiently unbalanced).
If this is right
- In the planted submatrix, planted dense subgraph, and stochastic block model, the method recovers prior low-degree recovery lower bounds through a simpler, less combinatorial argument.
- In multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer stochastic block model, the method supplies new evidence that detection-recovery gaps persist at the conjectured computational thresholds.
- Mild control of low-degree advantage is often sufficient to establish computational barriers for recovery across a wide range of high-dimensional statistical models.
Where Pith is reading between the lines
- The same reduction may extend the reach of low-degree methods to additional inference problems where direct unconditional arguments remain technically difficult.
- If the cross-validation step preserves advantage bounds in further models, the approach could provide a unified route to proving both detection and recovery thresholds under a single low-degree heuristic.
- The model-independence suggests the framework could be tested on layered or composite statistical models not covered in the current applications.
Load-bearing premise
The cross-validation reduction converts any recovery algorithm into a hypothesis test whose success probabilities are sufficiently lopsided while preserving the original low-degree advantage bounds without introducing model-specific gaps.
What would settle it
An explicit recovery algorithm that succeeds with high probability in a regime where the low-degree testing advantage remains bounded and the cross-validation step produces only balanced error probabilities would falsify the conditional lower-bound claim.
read the original abstract
The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, the standard approach bounds the low-degree advantage through an explicit orthonormal basis. However, this method does not extend naturally to estimation tasks, and thus fails to capture the \emph{detection-recovery gap phenomenon} that arises in many high-dimensional problems. Although several important advances have been made to overcome this limitation \cite{SW22, SW25, CGGV25+}, the existing approaches often rely on delicate, model-specific combinatorial arguments. In this work, we develop a general approach for obtaining \emph{conditional computational lower bounds} for recovery problems from mild bounds on low-degree testing advantage. Our method combines the notion of algorithmic contiguity in \cite{Li25} with a cross-validation reduction in \cite{DHSS25} that converts successful recovery into a hypothesis test with lopsided success probabilities. In contrast to prior unconditional lower bounds, our argument is conceptually simple, flexible, and largely model-independent. We apply this framework to several canonical inference problems, including planted submatrix, planted dense subgraph, stochastic block model, multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer stochastic block model. In the first three settings, our method recovers existing low-degree lower bounds for recovery in \cite{SW22, SW25} via a substantially simpler argument. In the latter three, it gives new evidence for conjectured computational thresholds including the persistence of detection-recovery gaps. Together, these results suggest that mild control of low-degree advantage is often sufficient to explain computational barriers for recovery in high-dimensional statistical models.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops a general method for conditional computational lower bounds on recovery tasks by combining algorithmic contiguity (Li25) with a cross-validation reduction (DHSS25) that converts any recovery algorithm into a hypothesis test possessing lopsided success probabilities. Mild low-degree testing advantages for the original detection problem are then shown to transfer (up to constants) to the derived test, yielding recovery lower bounds. The framework is applied to planted submatrix, planted dense subgraph, stochastic block model (recovering prior bounds from SW22/SW25 via simpler arguments), and to multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer SBM (providing new evidence for persistent detection-recovery gaps).
Significance. If the cross-validation reduction rigorously preserves low-degree advantage bounds without model-specific gaps, the work supplies a conceptually simpler and largely model-independent route to conditional lower bounds for recovery, extending the low-degree heuristic beyond detection. This would unify explanations for detection-recovery gaps across several canonical models and reduce reliance on delicate combinatorial arguments.
major comments (2)
- [§3] §3 (cross-validation reduction): The transfer of low-degree advantage bounds through sample splitting is asserted to hold up to constants and to be largely model-independent, yet the argument does not explicitly control the weak dependencies induced between the test statistic and held-out data; this control is required to ensure the effective polynomial degree and advantage do not inflate, particularly for the angular synchronization and multi-layer SBM cases whose natural bases are not orthonormal in the same manner as the planted-submatrix case.
- [Theorem 4.3] Theorem 4.3 and its application to multi-layer SBM: The claim that the lopsided success probabilities suffice to obtain a contradiction with algorithmic contiguity is load-bearing for the new lower bounds, but the manuscript provides only a sketch that the reduction preserves the mild low-degree advantage uniformly; an explicit verification that the cross-validation step does not introduce post-hoc restrictions or model-specific gaps is needed to support the uniformity asserted in the abstract.
minor comments (2)
- [Introduction] The introduction would benefit from a short table or paragraph explicitly contrasting the new conditional bounds with the unconditional bounds in SW22/SW25 to clarify the precise gain in generality.
- [§3] Notation for the low-degree advantage (e.g., the precise definition of the polynomial basis after cross-validation) should be restated once in §3 for self-contained reading.
Simulated Author's Rebuttal
We thank the referee for the careful and constructive report. The two major comments both concern the rigor of the cross-validation reduction in transferring low-degree advantages. We address them point by point and agree that additional explicit verification is warranted.
read point-by-point responses
-
Referee: [§3] §3 (cross-validation reduction): The transfer of low-degree advantage bounds through sample splitting is asserted to hold up to constants and to be largely model-independent, yet the argument does not explicitly control the weak dependencies induced between the test statistic and held-out data; this control is required to ensure the effective polynomial degree and advantage do not inflate, particularly for the angular synchronization and multi-layer SBM cases whose natural bases are not orthonormal in the same manner as the planted-submatrix case.
Authors: We agree that the dependence between the low-degree statistic computed on the training split and the held-out data must be controlled explicitly when the underlying basis is not orthonormal. The current write-up in §3 invokes independence of the splits and the lopsided-probability guarantee of the DHSS25 reduction to claim that the advantage transfers up to a universal constant, but does not quantify the covariance terms that arise for non-orthogonal bases. In the revision we will insert a short lemma (placed after the statement of the cross-validation reduction) that bounds the inflation of the low-degree advantage by a factor depending only on the splitting ratio and the operator norm of the basis change; the argument uses the same moment calculations already present for the planted-submatrix case and extends verbatim once the basis is allowed to be non-orthonormal. Explicit verification for multi-frequency angular synchronization and the multi-layer SBM will be included as corollaries. revision: yes
-
Referee: [Theorem 4.3] Theorem 4.3 and its application to multi-layer SBM: The claim that the lopsided success probabilities suffice to obtain a contradiction with algorithmic contiguity is load-bearing for the new lower bounds, but the manuscript provides only a sketch that the reduction preserves the mild low-degree advantage uniformly; an explicit verification that the cross-validation step does not introduce post-hoc restrictions or model-specific gaps is needed to support the uniformity asserted in the abstract.
Authors: The referee is correct that the uniformity claim is essential for the new results on angular synchronization and multi-layer SBM. Theorem 4.3 currently sketches the contradiction by noting that a recovery algorithm with non-trivial overlap produces, via the DHSS25 reduction, a test whose advantage is at least a positive constant times the original low-degree advantage; algorithmic contiguity (Li25) then yields the desired lower bound. The sketch does not, however, rule out the possibility that the cross-validation step imposes additional restrictions that are invisible in the planted-submatrix case but appear in the multi-layer setting. In the revision we will expand the proof of Theorem 4.3 with a self-contained paragraph that verifies the absence of such post-hoc restrictions: we show that the only properties used are (i) the mild low-degree advantage assumption on the original detection problem and (ii) the lopsided success probabilities guaranteed by the reduction, both of which hold uniformly across the models listed in the abstract. No model-specific combinatorial arguments are introduced. revision: yes
Circularity Check
No significant circularity in the derivation chain
full rationale
The paper develops a general conditional lower-bound method by combining algorithmic contiguity (Li25) with a cross-validation reduction (DHSS25) to convert recovery success into a lopsided hypothesis test. No equation or step equates the output bounds to internally fitted parameters, self-defined quantities, or renamings of the input low-degree advantage; the low-degree bounds remain external inputs, and the new contribution is the model-independent transfer argument plus applications that recover prior results or supply new evidence for conjectured gaps. Self-citations are present but do not reduce the central claim to an unverified loop or tautology.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The cross-validation reduction converts recovery success into a hypothesis test with sufficiently lopsided probabilities under the problem models considered.
- domain assumption Mild bounds on low-degree testing advantage are available or can be established independently for the target models.
Reference graph
Works this paper leans on
-
[1]
arXiv preprint arXiv:2504.20539 , year=
arXiv preprint, arXiv:2504.20539. [BKW20] Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational hardness of cer- tifying bounds on constrained PCA problems. InProceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), pages 78:1–78:29. Schloss Dagstuhl-Leibniz-Zentrumf¨ ur Infor- matik,
-
[2]
Algorithmic thresholds for tensor PCA
[BGJ20] G´ erard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor PCA. Annals of Probability, 48(4):2052–2087,
2052
-
[3]
[BC20+] Sharmodeep Bhattacharyya and Shirshendu Chatterjee. General community detection with op- timal recovery conditions for multi-relational sparse networks with dependent layers. arXiv preprint, arXiv:2004.03480. [BJR07] B´ ela Bollob´ as, Svante Janson, and Oliver Riordan. The phase transition in inhomogeneous random graphs.Random Structures and Algo...
-
[4]
Low- degree lower bounds via almost orthonormal bases
[CGGV25+] Alexandra Carpentier, Simone Maria Giancola, Christophe Giraud, and Nicolas Verzelen. Low- degree lower bounds via almost orthonormal bases. arXiv preprint, arXiv:2509.09353. [CGV25+] Alexandra Carpentier, Christophe Giraud, and Nicolas Verzelen. Phase transition for stochastic block model with more than √ncommunities. arXiv preprint, arXiv:2509...
-
[5]
Fundamental limits of community detection in contextual multi-layer stochastic block models
[GHL26+] Shuyang Gong, Dong Huang, and Zhangsong Li. Fundamental limits of community detection in contextual multi-layer stochastic block models. arXiv preprint, arXiv:2602.08173. [HWX15] Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. InProceedings of the 28th Annual Conference on Learning Theo...
-
[6]
A greedy anytime algorithm for sparse PCA
[HSV20] Guy Holtzman, Adam Soffer, and Dan Vilenchik. A greedy anytime algorithm for sparse PCA. InProceedings of the 33rd Annual Conference on Learning Theory (COLT), pages 1939–1956. PMLR,
1939
-
[7]
Low-degree method fails to predict robust subspace recovery
[JV26+] He Jia and Aravindan Vijayaraghavan. Low-degree method fails to predict robust subspace recovery. arXiv preprint, arXiv:2603.02594. [JL09] Iain M. Johnstone and Yu A. Lu. On consistency and sparsity for principal components analysis in high dimensions.Journal of the American Statistical Association, 104(486):682–693,
-
[8]
Perturbative construc- tion of mean-field equations in extensive-rank matrix factorization and denoising.Journal of Statistical Mechanics: Theory and Experiment, 2022(8):083301,
[MKMZ22] Antoine Maillard, Florent Krzakala, Marc M´ ezard, and Lenka Zdeborov´ a. Perturbative construc- tion of mean-field equations in extensive-rank matrix factorization and denoising.Journal of Statistical Mechanics: Theory and Experiment, 2022(8):083301,
2022
-
[9]
Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
[MSS25b] Elchanan Mossel, Allan Sly, and Youngtak Sohn. Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 2062–2073. ACM,
2062
-
[10]
[PWBM16+] Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, and Ankur Moitra. Optimality and sub- optimality of PCA for spiked random matrices and synchronization. arXiv preprint, arXiv:1609.05573. [PWBM18a] Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, and Ankur Moitra. Optimality and sub-optimality of PCA I: Spiked random matrix models.Annals ...
-
[11]
Spectral clustering and the high-dimensional stochastic block model.Annals of Statistics, 39(4):1878–1915,
[RCY11] Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic block model.Annals of Statistics, 39(4):1878–1915,
1915
-
[12]
[Wein25+] Alexander S. Wein. Computational complexity of statistics: New insights from low-degree poly- nomials. arXiv preprint, arXiv:2506.10748. [WEM19] Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi hierarchy and tensor PCA. InProceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1446–1468. IEEE,
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.