{"id":"6733457e-a063-42d1-8e6c-abd68938a797","arxiv_id":"2506.09959","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Local search with random Gaussian acceptance thresholds provably recovers planted sparse tensor signals down to the conjectured algorithmic threshold in several sparsity regimes.","lead":"This paper gives local search algorithms that recover planted signals in sparse tensor PCA at signal levels matching the best known polynomial-time methods, closing a known gap for local Markov chains. The key trick is adding random Gaussian thresholds to each accepted move, which breaks dependencies between iterations and makes the trajectory analyzable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6.2(B) promises 2/3(k−⟨σ,θ⟩) support-addition neighbors that leave the norm-constrained state at ∥σ∥0=3k/2, so the drift and spanning-tree proof of Theorem 6.1 is unsupported exactly at the boundary between weak correlation and exact recovery.","rationale":"The paper's positive claims split into several regimes. The sparse k=O(√n) analysis (Section 4) and the Subset Gaussian Cloning construction (Section 7) are structurally coherent and appear to support their respective statements. The dense-binary result, however, is governed by a norm-constrained search, and the boundary of that constraint is exactly where the stated lemmas stop doing the work. Lemma 6.2(B) explicitly promises roughly (2/3)(k−⟨σ,θ⟩) improving support additions, yet for ∥σ∥0=3k/2 no legal additions exist; the proof never checks the cap. Lemma 6.2(A) is invoked in Theorem 6.1 to build a spanning tree on the constrained graph, but (A) only guarantees a neighbor in the unconstrained set Ω̃(C), not in Ω̂(C). Both slips touch the same load-bearing step: converting weak correlation to exact recovery in the binary dense regime. This is an internal proof gap rather than a disagreement with an external conjecture, and it does not affect the sparse-regime or Rademacher-stage results. A direct check of the boundary count plus a two-step drift repair would settle whether the theorem survives; absent that, conditional acceptance remains appropriate. No evidence of circularity or data fitting was found.","tokens_in":91509,"tokens_out":10302,"duration_ms":116602,"concrete_test":"Set k=n^{0.6}, r=3, λ=C_λ n^{(r−1)/2} k^{−r/2+1} √log n, and evaluate Lemma 6.2(B) at a state with ∥σ∥0=3k/2 and ⟨σ,θ⟩=k/8. The proposed witnesses σ+e_i for i∈supp(θ)\\supp(σ) all violate ∥·∥0≤3k/2, so the claimed count is zero. Then attempt the natural repair: prove a two-step drift at the cap (first delete a non-signal coordinate, then add a signal coordinate) and re-derive the 7k/(12n) lower bound used in the proof of Theorem 6.1; if that repair fails, Theorem 2.5 lacks a proof in the boundary regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The dense-binary leg (Theorem 2.5) is proved via Algorithm 4, whose state graph is restricted to {σ∈{0,1}^n : ∥σ∥0≤3k/2, ⟨σ,θ⟩≥k/10}. Lemma 6.2(B) asserts that each σ in this set has at least ⌊2/3(k−⟨σ,θ⟩)⌋ distinct neighbors σ′=σ+e_i with i∈supp(θ)\\supp(σ), all lying in the same constrained set and improving H_{(r+1)/2,γ}. But if ∥σ∥0=3k/2, every such addition satisfies ∥σ′∥0=3k/2+1, so it is not a vertex of the allowed graph; the true count is zero, not Ω(k−⟨σ,θ⟩). The proof in Section 6.2, Case 3, only says the bound follows 'by an identical argument as in Case 2' and never verifies the norm constraint. This is not a corner case: starting from ⟨σ0,θ⟩≥k/8 and ∥σ0∥0≤3k/2, the process can reach the cap while ⟨σ,θ⟩=k/10, precisely where Case 2 of Lemma 6.2(A) would produce only disallowed additions. Theorem 6.1 then uses Lemma 6.2(B) to lower-bound the probability of increasing overlap in the coupling argument, and uses Lemma 6.2(A) to build the spanning tree for the canonical-paths step; Lemma 6.2(A) also only promises a neighbor in the unconstrained set Ω̃(C), not in Ω̂(C). Until the boundary is repaired—for example by showing that deletions of non-signal coordinates at the cap provide the needed drift, or by relaxing the norm constraint—the guarantee that randomized greedy boosts weak correlation to exact recovery at the conjectured threshold is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies local-search methods for sparse tensor PCA. When the sparsity is k=O(√n), it proves that greedy and randomized greedy optimizing a regularized log-posterior H_{r,γ} on the trinary cube, started from a two-coordinate warm start, recover the planted signal at the conjectured threshold λ=ω(k^{r/2}√log n) for both binary and Rademacher priors (Theorem 2.1). In the denser binary regime k=Ω(√n), it proposes a two-stage method: an aggressive greedy peeling step (Algorithm 3) that achieves weak correlation (Theorem 2.4), followed by a norm-constrained randomized greedy step (Algorithm 4) that is claimed to boost weak correlation to exact recovery (Theorem 2.5). In the denser Rademacher regime with odd tensor power r≥3, it introduces randomized greedy algorithms with random Gaussian thresholds (Algorithms 6 and 7) and a homotopy initialization, proving almost-linear-time recovery at the threshold λ=Ω̃(n^{r/4}) (Theorem 2.7). The random-threshold technique is formalized through a 'Subset Gaussian Cloning' lemma (Section 7) that makes the effective noise at each iteration independent, a contribution that may be of independent interest. The paper also includes simulations of the dense binary and trinary cases that appear consistent with the predicted thresholds.","tokens_in":1653,"tokens_out":1680,"duration_ms":111956,"significance":"If all proofs are correct, this is a substantial advance: it would show that simple local search methods can match the conjectured computational threshold for sparse tensor PCA, in contrast to the negative results of CSZ24 for a broad class of low-temperature MCMC methods. The random-threshold mechanism is an original algorithmic idea with potential applications beyond this model. The paper contains several careful, largely self-contained proof components: the sparser-case analysis (Section 4) is detailed, the peeling argument for Algorithm 3 (Section 5) adapts relevant planted-clique techniques to the Gaussian tensor setting, and Theorem 7.2 (Subset Gaussian Cloning) is elegant and checkable. However, the dense-binary leg (Theorem 2.5, via Theorem 6.1) contains a load-bearing gap at the norm boundary, detailed in the major comments below; until that is repaired, the boosting guarantee in the binary dense regime is not established as written.","major_comments":[{"comment":"Lemma 6.2(B) asserts that every σ in Ω̂(C) has at least ⌊2/3(k−⟨σ,θ⟩)⌋ distinct support-addition neighbors σ′=σ+e_i (i∈supp(θ)\\supp(σ)) that lie in Ω̂(C) and improve H. When ∥σ∥0=3k/2, every such addition has ∥σ′∥0=3k/2+1, so it is not a vertex of Ω̂(C); the true number of such neighbors is zero, not Ω(k−⟨σ,θ⟩). The proof in Case 3 of Lemma 6.2 proceeds 'by an identical argument as in Case 2' and never verifies the norm constraint, although Case 2 also does not address it. This is not a corner case: from ⟨σ0,θ⟩≥k/8 and ∥σ0∥0≤3k/2, the process can reach the cap while ⟨σ,θ⟩ is still k/10, precisely where Lemma 6.2(B) would be needed. The coupling argument in the proof of Theorem 6.1 uses Lemma 6.2(B) to lower-bound the probability that ⟨S_t,θ⟩ increases (the paragraph starting 'Next, we show that S_t and \\tilde S_t are coupled...'); without this drift lower bound, the claim that Algorithm 4 boosts weak correlation to exact recovery is unsupported. The authors should either prove that the process has slack below the cap whenever ⟨σ,θ⟩ is small, show that deletions of non-signal coordinates at the cap provide the needed drift, or modify the algorithm or its analysis.","section":"§6.2, Lemma 6.2(B)"},{"comment":"The canonical-paths argument is presented on the constrained graph {σ∈{0,1}^n : ⟨σ,θ⟩≥k/10, ∥σ∥0≤3k/2}. For each σ≠θ in this graph, the proof invokes Lemma 6.2(A) to find a neighbor σ′ with higher H and then sets 'σ′ to be the parent of σ in the tree.' However, Lemma 6.2(A) only guarantees σ′∈Ω̃(C), not that σ′ satisfies the norm constraint ∥σ′∥0≤3k/2 or the overlap constraint ⟨σ′,θ⟩≥k/10. If σ′ violates the norm cap, then the edge (σ,σ′) is not part of the constrained graph, and the spanning tree is not contained in the state space. Consequently, the application of Theorem 2.3 of [CSZ24] is not justified as written. This is a second, independent boundary issue in the same section; both this issue and the counting gap in Lemma 6.2(B) must be repaired before Theorem 2.5 follows from the given proof.","section":"§6.1, proof of Theorem 6.1 (spanning tree)"}],"minor_comments":[{"comment":"The statement contains a typo: 'd_H(σ′,θ)=d_H(σ′,θ)−1' should read 'd_H(σ′,θ)=d_H(σ,θ)−1'.","section":"§6.2, Lemma 6.2(B)"},{"comment":"In the abstract, 'rather that if and only if' should be 'rather than if and only if'.","section":"Abstract"},{"comment":"The text references Figures 1–6 by number, but the figures are not embedded in the submitted text; the final version should include them.","section":"§3, Simulations"},{"comment":"In Step 2, case (b)(iii), the displayed lower bound contains the misspelling 'C Aignal'; this should be 'C_Signal'.","section":"§8.5, proof of Lemma 8.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is ambitious and contains several novel and genuinely interesting ideas, especially the random-threshold method and the Subset Gaussian Cloning lemma. The main concern is the dense-binary proof in Section 6, where the norm-boundary gap in Lemma 6.2(B) and the spanning-tree construction are load-bearing. This is not a minor presentation issue; it affects the stated scope of Theorem 2.5 for k=Ω(√n). The gap appears potentially fixable (for example, by arguing that the process never reaches the cap while overlap is still small, or by adding a deletion move at the cap), but the repair is nontrivial and needs to be verified. I recommend major revision rather than rejection because the rest of the paper contains significant contributions and the central claims are plausible, but the proof of the binary dense regime is not complete as it stands."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a serious paper with one substantial new idea and one load-bearing gap. The sparse-regime results (Theorem 2.1) look right to me: greedy and randomized greedy on the lifted trinary cube, with gamma = Θ(sqrt log n) and the two-coordinate warm start, provably recover the signal at the conjectured λ threshold for both priors. The proof is a careful first-moment argument over the region 𝒜, and I did not find a problem in Section 4. The Gaussian-cloning lemma (Theorem 7.2) is genuinely nice: adding per-coordinate random thresholds breaks the inter-iteration dependence and yields independent Gaussians at the cost of inflating variance by M. That is a real methodological contribution.\n\nThe soft spot is the dense-binary leg, Theorem 2.5 / Algorithm 4. The proof of Lemma 6.2(B) claims that from any σ in the constrained set, there are Ω(k−⟨σ,θ⟩) improving neighbors that add a signal coordinate. But if ∥σ∥0 = 3k/2, every such addition leaves the allowed graph. Lemma 6.2(A) only produces a neighbor in the unconstrained set ̃Ω(C), so the spanning tree used in the canonical-paths argument of Theorem 6.1 is not guaranteed to stay inside the state space. This is not a corner case: the process can hit the norm cap while the overlap is near k/10, exactly where the coupling argument needs Lemma 6.2(B). Without a repair—either allowing deletions at the cap or showing the cap can be relaxed—the boost from weak correlation to exact recovery is not proved as written. I also noticed a small algebra typo in Lemma 8.8's drift calculation, but that is clearly fixable.\n\nThe dense Rademacher result (Theorem 2.7) is harder for me to evaluate in full; the random-threshold machinery is intricate, but the structure is coherent and the simulations match the predicted thresholds. I would not want to bet against it, though I haven't checked every line.\n\nCredit where due: the paper is honest about the limitations (e.g., no dense Rademacher guarantees for even r), cites prior work properly including the CSZ24 lower bound it extends, and does not fit parameters to data. The simulations are illustrative rather than evidence.\n\nWho should read it: anyone working on average-case algorithms, MCMC, or tensor PCA. It deserves a serious referee; the sparse-regime results and the Gaussian-cloning technique are strong enough to warrant careful review even if the dense-binary proof needs major repair. I would engage with it, and I'd expect the authors to fix the boundary case.","headline":"Strong sparse-regime results and a genuinely new random-threshold analysis, but the dense-binary proof has a boundary gap that undermines Theorem 2.5 as written.","tokens_in":92486,"tokens_out":3816,"would_cite":true,"duration_ms":44044,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Simple local-search rules — greedy, randomized greedy, and a random-threshold variant — provably recover the planted signal in sparse tensor PCA at the conjectured computational threshold, closing the earlier 'local-computational gap.'","keywords":["sparse tensor PCA","local search","randomized greedy","random thresholds","computational-statistical gap","exact recovery","Gaussian cloning","planted signal"],"falsifier":"In the dense binary regime with, say, $r=3$ and $k=n^{0.6}$, take a state $\\sigma$ with $\\|\\sigma\\|_0=3k/2$ and $\\langle\\sigma,\\theta\\rangle=k/10$, and for many Gaussian draws of $Y$ count what fraction of the $k-\\langle\\sigma,\\theta\\rangle$ moves that add a signal coordinate increase the Hamiltonian $H_{(r+1)/2,\\gamma}$. Lemma 6.2(B) asserts at least two-thirds of them do; if the measured fraction at the norm boundary falls well below two-thirds, or a simulated boosting run stalls at the cap, the spanning-tree drift the proof relies on remains unjustified.","tokens_in":91261,"feed_emoji":"🎯","tokens_out":12924,"duration_ms":116840,"temperature":0.7,"pith_summary":"This paper asks whether the poor provable performance of local-search methods in sparse tensor PCA is a feature of the problem or an artifact of the algorithms that had been analyzed. Its answer is that natural local rules do reach the conjectured optimum: greedy, randomized greedy, and a new randomized-greedy variant with random acceptance thresholds recover the planted sparse signal exactly at the conjectured computational threshold, matching the best known polynomial-time procedures up to logarithmic factors in every regime the paper treats. That matters because local search is the default tool in applied statistics, and these are the first local methods with provable guarantees at the optimal threshold in regimes where a broad family of local Markov chains had been shown to underperform by polynomial factors. The key mechanism is accepting a proposed move only when the objective gain exceeds a fresh random Gaussian threshold, which breaks the dependence between successive iterations and makes the trajectory analytically tractable.","feed_headline":"Simple local-search rules hit sparse tensor PCA's conjectured limit","feed_subtitle":"Greedy and random-threshold variants provably close the local-method gap, up to log factors.","key_machinery":"The load-bearing object is the regularized Hamiltonian $H_{\\beta,\\gamma}(\\sigma)=\\langle \\sigma^{\\otimes r},Y\\rangle-\\gamma\\|\\sigma\\|_0^\\beta$ on the lifted state spaces $\\{0,1\\}^n$ (binary prior) and $\\{-1,0,1\\}^n$ (Rademacher prior), with neighboring states differing in a single coordinate. In the sparse regime the analysis carves out a 'good region' $\\mathcal{A}$ of states with enough overlap with $\\theta$; inside it every coordinate that disagrees with the signal can be fixed by an improving move and every agreeing coordinate is protected, so the only local maximum of $H$ in $\\mathcal{A}$ is $\\theta$ itself. In the dense binary regime the argument is carried by a greedy peeling process on the truncated tensor $Q=\\max\\{Y,0\\}$, adapted from planted-clique peeling, which first obtains weak correlation. In the hardest regime, the novel mechanism is random-threshold acceptance: a proposed move is accepted only if the Hamiltonian gain exceeds a Gaussian random variable scaled by the Frobenius norm of the tensor difference, realized through a subset-Gaussian-cloning construction that makes the acceptance indicators across iterations independent in law while inflating the effective noise by only a polylogarithmic factor. A homotopy initialization supplies the warm start for the odd-$r$ Rademacher stage.","core_discovery":"On the paper's own terms, the discovery is a set of regime-specific theorems. For $k=O(\\sqrt{n})$ and any tensor order $r\\ge 2$, plain greedy and randomized greedy maximizing the regularized objective $H_{r,\\gamma}(\\sigma)=\\langle \\sigma^{\\otimes r},Y\\rangle-\\gamma\\|\\sigma\\|_0^r$ with $\\gamma=\\Theta(\\sqrt{\\log n})$, started from any two-coordinate state supported inside the signal, output $\\theta$ whenever $\\lambda=\\omega(k^{r/2}\\sqrt{\\log n})$ — the conjectured algorithmically optimal rate under both the binary and Rademacher priors. For binary signals with $k=\\Omega(\\sqrt{n})$, a greedy peeling stage run on the elementwise-truncated tensor produces weak correlation with $\\theta$, and a norm-constrained randomized greedy stage boosts it to exact recovery whenever $\\lambda=\\tilde{\\omega}(n^{(r-1)/2}/k^{r/2-1})$. For Rademacher signals with $k=\\Omega(\\sqrt{n})$ and odd $r\\ge 3$, a two-stage randomized greedy with random Gaussian thresholds, fed by a homotopy initialization, outputs $\\theta$ in $\\Theta(n\\log^4 n)$ iterations when $\\lambda=\\tilde{\\Omega}(n^{r/4})$. Together these assert that simple local rules close the previously documented local-computational gap down to polylogarithmic slack.","pith_inferences":["If the initialization-signal trade-off generalizes beyond this model, it states a design rule for other average-case problems: spend a cheap warm-start step to lift the cosine with the signal as high as possible, and let local search close the remaining gap at the optimal threshold.","The restriction to odd $r$ appears to reflect the homotopy initialization rather than the local-search machinery itself; the paper notes the same two-stage scheme should reach $\\tilde{\\Omega}(n^{r/4})$ for even $r$ given any initialization with cosine at least $n^{-1/4}$, a prediction that could be checked directly in simulations.","A natural stress-test of the random-threshold device is to run the dense Rademacher stage without the injected noise; the paper's analysis predicts a two-phase overlap trajectory (oscillatory, then monotone) at the optimal threshold, and its own small-$n$ simulations show qualitative agreement."],"forward_implications":["In the sparse regime $k=O(\\sqrt{n})$, the required two-coordinate warm start can be found by brute force in $O(n^2)$ time, so the full pipeline is an end-to-end polynomial-time local method at the conjectured threshold for both priors and every $r\\ge 2$.","For dense binary signals, local search succeeds at $\\lambda=\\tilde{\\omega}(n^{(r-1)/2}/k^{r/2-1})$, the same rate as the best spectral procedures; the simulations suggest the norm cap used in the proof is a device rather than a necessity.","For dense Rademacher signals with odd $r\\ge 3$, the two-stage random-threshold method recovers $\\theta$ in almost-linear time $\\Theta(n\\log^4 n)$ at $\\lambda=\\tilde{\\Omega}(n^{r/4})$.","The paper's predicted initialization-signal trade-off, $\\lambda=\\tilde{\\Omega}(\\sqrt{k}/\\cos(S_1,\\theta)^{r-1})$, matches simulations for both vanilla and random-threshold greedy, giving a quantitative rule for how much a warm start lowers the required signal strength.","By breaking the dependence between iterations, the random-threshold technique offers a general template for proving convergence of local search in Gaussian additive models, which the paper suggests could be of independent interest."],"supporting_citations":[{"why":"Documents the local-MCMC threshold gap that this paper closes, and supplies the canonical-paths convergence theorem used to prove the dense-binary boosting stage.","marker":"[CSZ24]"},{"why":"Sets the conjectured algorithmic thresholds for binary and Rademacher sparse tensor PCA that serve as the benchmarks in all regimes.","marker":"[LZ22]"},{"why":"Introduces the homotopy initialization and the noise-injection idea for tensor PCA that the dense Rademacher stage builds on.","marker":"[ADGM17]"},{"why":"Provides the greedy peeling analysis for planted clique that the dense-binary weak-correlation stage adapts to Gaussian tensors.","marker":"[GJX23]"},{"why":"Supplies the two-stage greedy-peeling method for planted clique whose ideas underlie the weak-correlation stage.","marker":"[FR10]"},{"why":"Hanson-Wright-type concentration used inside the spanning-tree argument that boosts weak to exact correlation in the dense binary case.","marker":"[RV13]"}],"fun_headline_variants":["Local search closes local-computational gap in tensor PCA","Random-threshold greedy provably matches tensor PCA limits","Greedy and threshold rules hit sparse tensor PCA barrier","Simple local rules reach conjectured optimal in tensor PCA","Local search closes gap to optimal in sparse tensor PCA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dense-binary proof relies on a count of improving moves that the analysis only establishes away from the $3k/2$ norm boundary; if states sitting exactly on that boundary have materially fewer improving moves, the guarantee that randomized greedy turns weak correlation into exact recovery at the optimal threshold is not established.","fun_headline_variants_meta":{"raw":{"variants":["Local search closes local-computational gap in tensor PCA","Random-threshold greedy provably matches tensor PCA limits","Greedy and threshold rules hit sparse tensor PCA barrier","Simple local rules reach conjectured optimal in tensor PCA","Local search closes gap to optimal in sparse tensor PCA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000218,"raw_usage":{"total_tokens":1509,"prompt_tokens":1083,"completion_tokens":426,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":699,"completion_tokens_details":{"reasoning_tokens":348}},"tokens_in":699,"tokens_out":426,"duration_ms":4614,"temperature":1.0,"reasoning_tokens":348,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:39:25.322480+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"In the dense binary regime with, say, $r=3$ and $k=n^{0.6}$, take a state $\\sigma$ with $\\|\\sigma\\|_0=3k/2$ and $\\langle\\sigma,\\theta\\rangle=k/10$, and for many Gaussian draws of $Y$ count what fraction of the $k-\\langle\\sigma,\\theta\\rangle$ moves that add a signal coordinate increase the Hamiltonian $H_{(r+1)/2,\\gamma}$. Lemma 6.2(B) asserts at least two-thirds of them do; if the measured fraction at the norm boundary falls well below two-thirds, or a simulated boosting run stalls at the cap, the spanning-tree drift the proof relies on remains unjustified.","supporting_citations":[],"review_version":1}