Almost-Optimal Local-Search Methods for Sparse Tensor PCA

Conor Sheehan; Ilias Zadik; Konstantinos Tsirkas; Max Lovig

REVIEW 2 major objections 4 minor 1 cited by

Almost-Optimal Local-Search Methods for Sparse Tensor PCA

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.'

desk verdict 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. read the letter →

arxiv 2506.09959 v1 pith:EABKKO6G submitted 2025-06-11 math.ST cs.DSstat.MLstat.TH

Max Lovig , Conor Sheehan , Konstantinos Tsirkas , Ilias Zadik This is my paper · ORCID

classification math.STcs.DSstat.MLstat.TH MSC 62H2568W20

keywords sparsetensorPCAlocalsearchrandomizedgreedyrandomthresholdscomputational-statisticalgapexactrecoveryGaussiancloningplantedsignal

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

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

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

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

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

Referee Report

2 major / 4 minor

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.

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 (2)

[§6.2, Lemma 6.2(B)] 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.
[§6.1, proof of Theorem 6.1 (spanning tree)] 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.

minor comments (4)

[§6.2, Lemma 6.2(B)] The statement contains a typo: 'd_H(σ′,θ)=d_H(σ′,θ)−1' should read 'd_H(σ′,θ)=d_H(σ,θ)−1'.
[Abstract] In the abstract, 'rather that if and only if' should be 'rather than if and only if'.
[§3, Simulations] The text references Figures 1–6 by number, but the figures are not embedded in the submitted text; the final version should include them.
[§8.5, proof of Lemma 8.4] In Step 2, case (b)(iii), the displayed lower bound contains the misspelling 'C Aignal'; this should be 'C_Signal'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main derivations are internally self-contained and the cited self-work is a general graph-theoretic tool, not the target result.

full rationale

The paper's central claims are proved from the Gaussian observation model (1.1) via explicit landscape lemmas (Lemmas 4.6-4.8, 6.2-6.5), concentration arguments, and the internally proved Subset Gaussian Cloning theorem (Theorem 7.2). The derived thresholds in (3.1) are analytic consequences of the analysis of the random-threshold variants rather than parameters fitted to the simulations; the simulations are used as auxiliary validation, not as inputs to the proofs. The only potentially load-bearing citation to overlapping authors is Theorem 2.3 of [CSZ24], invoked in the proof of Theorem 6.1 as a black-box convergence theorem for randomized greedy on a graph satisfying a spanning-tree drift condition. That theorem is general and parameter-free in the relevant sense: it does not state or assume the sparse tensor PCA recovery target, and its applicability depends on the paper's own construction of the spanning tree. Hence the citation is independent mathematical support rather than a re-derivation of the target claim. The boundary issue raised about Lemma 6.2(B) at ||sigma||_0 = 3k/2 is a potential correctness gap in the proof, not a circularity: it concerns whether the stated neighbor lower bound holds within the constrained graph, not whether an output is equivalent to an input by definition.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted to data: the algorithmic constants are asymptotic and can be taken sufficiently large. The central proof rests on the generative model, standard concentration inequalities, one imported mixing theorem from the authors' earlier work, and the conjectured planted-clique benchmarks for the word 'optimal'. No new physical or statistical entities are postulated; the random-threshold mechanism is an algorithmic construction with a checkable Gaussian-cloning lemma.

free parameters (4)

regularization strength γ = Θ(√log n) in Theorems 2.1 and 2.5, Θ(log n) in Theorem 2.7
Chosen as a sufficiently large constant multiple of a logarithmic scale; no data fitting is performed.
posterior exponent β = r in the sparse regime, (r+1)/2 in the dense regimes
Hand-chosen to balance the signal and noise terms in the Hamiltonian; not estimated from data.
norm cap 3k/2 = 3k/2
Proof device bounding the state space in Algorithm 4 and Theorem 6.1; simulations indicate it may not be necessary.
threshold budget M = log^4 n and 25 log(3n) in the two stages; Θ(log n) in Theorem 8.1
Polylogarithmic counts needed for the Gaussian cloning variance and coupon-collector arguments; chosen by hand, not data-dependent.

assumptions (4)

domain assumption Sparse tensor PCA generative model (1.1): Y = λ/k^{r/2} θ^{⊗r} + W with i.i.d. standard Gaussian entries.
All algorithms and proofs are stated for this model; the paper does not address other noise distributions.
standard math Theorem 2.3 of [CSZ24], the canonical-paths mixing bound for randomized greedy with Hamiltonian increase conditions, is valid.
Invoked in the proof of Theorem 6.1 to bound the number of iterations needed to boost weak correlation; not reproved in this paper.
standard math Hanson-Wright inequality (Lemma 6.7 of [RV13]) and Gaussian maximum concentration (Lemmas 9.1 and 9.2) hold as stated.
Used throughout Sections 5 through 8 to control Gaussian noise terms.
domain assumption Conjectured algorithmic thresholds λ_ALG(B) and λ_ALG(R) from planted-clique reductions are the right benchmarks for 'almost-optimal'.
The theorems prove upper bounds at these thresholds; they do not prove that no polynomial-time method can do better, so the optimality framing relies on the conjectured lower bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Almost-Optimal Local-Search Methods for Sparse Tensor PCA." pith.science (2026). https://pith.science/paper/EABKKO6G

@misc{pith2026250609959,
  author       = {Pith},
  title        = {Pith review of: Almost-Optimal Local-Search Methods for Sparse Tensor PCA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EABKKO6G}},
  note         = {Machine review of arXiv:2506.09959}
}

read the original abstract

Local-search methods are widely employed in statistical applications, yet interestingly, their theoretical foundations remain rather underexplored, compared to other classes of estimators such as low-degree polynomials and spectral methods. Of note, among the few existing results recent studies have revealed a significant "local-computational" gap in the context of a well-studied sparse tensor principal component analysis (PCA), where a broad class of local Markov chain methods exhibits a notable underperformance relative to other polynomial-time algorithms. In this work, we propose a series of local-search methods that provably "close" this gap to the best known polynomial-time procedures in multiple regimes of the model, including and going beyond the previously studied regimes in which the broad family of local Markov chain methods underperforms. Our framework includes: (1) standard greedy and randomized greedy algorithms applied to the (regularized) posterior of the model; and (2) novel random-threshold variants, in which the randomized greedy algorithm accepts a proposed transition if and only if the corresponding change in the Hamiltonian exceeds a random Gaussian threshold-rather that if and only if it is positive, as is customary. The introduction of the random thresholds enables a tight mathematical analysis of the randomized greedy algorithm's trajectory by crucially breaking the dependencies between the iterations, and could be of independent interest to the community.

Figures

Figures reproduced from arXiv: 2506.09959 by the authors.

**Figure 3.** Randomized greedy for Sparse 3-Tensor PCA [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

**Figure 5.** Two-stage algorithm for sparse 3-tensor PCA [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗

Figures from the paper (1 more)

**Figure 7.** Figure 7: A cartoon visualization of the covering sets {ℐ1, . . . , ℐ𝑚} which divide the stochastic process into easier to handle “chunks”. We also see how event 𝒜, represented abstractly by the red arrow, is implied by the sequence of events ℰ = ∪𝑖ℰ𝑖 , each with a blue arrow. …

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
math.ST 2025-06 accept novelty 2.0 of 10

A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

40 extracted references · 35 canonical work pages · cited by 1 Pith paper

[1]

Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,

Milton Abramowitz. Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables, . Dover Publications, Inc., USA, 1974

work page 1974
[2]

Homotopy analysis for tensor pca

Anima Anandkumar, Yuan Deng, Rong Ge, and Hossein Mobahi. Homotopy analysis for tensor pca. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research , pages 79--104. PMLR, 07--10 Jul 2017

work page 2017
[3]

Algorithmic thresholds for tensor pca

G \'e rard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor pca. The Annals of Probability , 48(4):2052--2087, 2020

work page 2020
[4]

High-dimensional analysis of semidefinite relaxations for sparse principal components

Arash A Amini and Martin J Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE international symposium on information theory , pages 2454--2458. IEEE, 2008

work page 2008
[5]

Free energy wells and overlap gap property in sparse pca

G \'e rard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse pca. Communications on Pure and Applied Mathematics , 76(10):2410--2473, 2023

work page 2023
[6]

Reducibility and computational lower bounds for problems with planted sparse structure

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory , pages 48--166. PMLR, 2018

work page 2018
[7]

Concentration Inequalities: A Nonasymptotic Theory of Independence

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press, 2013

2013
[8]

Tony Cai, Tengyuan Liang, and Alexander Rakhlin

T. Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Computational and statistical boundaries for submatrix localization in a large noisy matrix . The Annals of Statistics , 45(4):1403 -- 1430, 2017

work page 2017

Show all 40 references

[9]

Almost-linear planted cliques elude the metropolis process

Zongchen Chen, Elchanan Mossel, and Ilias Zadik. Almost-linear planted cliques elude the metropolis process. Random Structures & Algorithms , 66(2):e21274, 2025

2025
[10]

On the low-temperature mcmc threshold: the cases of sparse tensor pca, sparse regression, and a geometric rule, 2024

Zongchen Chen, Conor Sheehan, and Ilias Zadik. On the low-temperature mcmc threshold: the cases of sparse tensor pca, sparse regression, and a geometric rule, 2024

2024
[11]

The power of two matrices in spectral algorithms for community recovery

Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon. The power of two matrices in spectral algorithms for community recovery. IEEE Transactions on Information Theory , 70(5):3599--3621, 2023

2023
[12]

Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures

Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 73--84. IEEE, 2017

2017
[13]

Message-passing algorithms for compressed sensing

David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences , 106(45):18914--18919, 2009

2009
[14]

Statistical algorithms and a lower bound for detecting planted cliques

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM) , 64(2):1--37, 2017

2017
[15]

Finding hidden cliques in linear time

Uriel Feige and Dorit Ron. Finding hidden cliques in linear time. Discrete Mathematics & Theoretical Computer Science , DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), Jan 2010

2010
[16]

A unifying tutorial on approximate message passing

Oliver Y Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J Samworth. A unifying tutorial on approximate message passing. Foundations and Trends in Machine Learning , 15(4):335--536, 2022

2022
[17]

Finding planted cliques using markov chain monte carlo, 2023

Reza Gheissari, Aukosh Jagannath, and Yiming Xu. Finding planted cliques using markov chain monte carlo, 2023

2023
[18]

Probability and random processes

Geoffrey Grimmett and David Stirzaker. Probability and random processes . Oxford University Press, Oxford; New York, 2001

2001
[19]

Sparse high-dimensional linear regression

David Gamarnik and Ilias Zadik. Sparse high-dimensional linear regression. estimating squared error and a phase transition. The Annals of Statistics , 50(2):880--903, 2022

2022
[20]

The landscape of the planted clique problem: Dense subgraphs and the overlap gap property

David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property. The Annals of Applied Probability , 34(4):3375--3434, 2024

2024
[21]

Hardy, J.E

G.H. Hardy, J.E. Littlewood, and G. Pólya. Inequalities . Cambridge University Press, 1st edition, 1934

1934
[22]

A robust spectral algorithm for overcomplete tensor decomposition

Samuel B Hopkins, Tselil Schramm, and Jonathan Shi. A robust spectral algorithm for overcomplete tensor decomposition. In Conference on Learning Theory , pages 1683--1722. PMLR, 2019

2019
[23]

Large cliques elude the metropolis process

Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms , 3(4):347--359, 1992

1992
[24]

Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan

Norman L. Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan. Continuous Univariate Distributions . Wiley Series in Probability and Statistics. John Wiley & Sons, New York, 2 edition, October 1994. 2nd edition

1994
[25]

On consistency and sparsity for principal components analysis in high dimensions

Iain M Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. Journal of the American Statistical Association , 104(486):682--693, 2009

2009
[26]

Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio

Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages 1--50. Springer, 2019

2019
[27]

Drift Analysis , pages 89--131

Johannes Lengler. Drift Analysis , pages 89--131. Springer International Publishing, Cham, 2020

2020
[28]

Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, and David X. Wu. Locally stationary distributions: A framework for analyzing slow-mixing markov chains*. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 203--215, 2024

2024
[29]

Markov chains and mixing times , volume 107

David A Levin and Yuval Peres. Markov chains and mixing times , volume 107. American Mathematical Soc., 2017

2017
[30]

Tensor clustering with planted structures: Statistical optimality and computational limits

Yuetian Luo and Anru R Zhang. Tensor clustering with planted structures: Statistical optimality and computational limits. The Annals of Statistics , 50(1):584--613, 2022

2022
[31]

Randomized Algorithms

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1995

1995
[32]

A statistical model for tensor pca

Andrea Montanari and Emile Richard. A statistical model for tensor pca. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2 , NIPS'14, page 2897–2905, Cambridge, MA, USA, 2014. MIT Press

2014
[33]

Andrea Montanari and Alexander S. Wein. Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation. Probability Theory and Related Fields , 191(1):181--233, Feb 2025

2025
[34]

The all-or-nothing phenomenon in sparse tensor pca

Jonathan Niles-Weed and Ilias Zadik. The all-or-nothing phenomenon in sparse tensor pca. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems , volume 33, pages 17674--17684. Curran Associates, Inc., 2020

2020
[35]

R. B. O'Hara and M. J. Sillanp \"a \"a . A review of Bayesian variable selection methods: what, how and which . Bayesian Analysis , 4(1):85 -- 117, 2009

2009
[36]

Wein, and Afonso S

Amelia Perry, Alexander S. Wein, and Afonso S. Bandeira. Statistical limits of spiked tensor models . Annales de l'Institut Henri Poincaré, Probabilités et Statistiques , 56(1):230 -- 264, 2020

2020
[37]

Hanson-Wright inequality and sub-gaussian concentration

Mark Rudelson and Roman Vershynin. Hanson-Wright inequality and sub-gaussian concentration . Electronic Communications in Probability , 18:1 -- 9, 2013

2013
[38]

L \'e vy Processes and Infinitely Divisible Distributions , volume 68 of Cambridge Studies in Advanced Mathematics

Ken-iti Sato. L \'e vy Processes and Infinitely Divisible Distributions , volume 68 of Cambridge Studies in Advanced Mathematics . Cambridge University Press, Cambridge, UK, 2 edition, December 2013

2013
[39]

Computational barriers to estimation from low-degree polynomials

Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics , 50(3):1833--1858, 2022

2022
[40]

Wainwright, and Michael I

Yun Yang, Martin J. Wainwright, and Michael I. Jordan. On the computational complexity of high-dimensional Bayesian variable selection . The Annals of Statistics , 44(6):2497 -- 2532, 2016

2016

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,

Milton Abramowitz. Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables, . Dover Publications, Inc., USA, 1974

work page 1974

[2] [2]

Homotopy analysis for tensor pca

Anima Anandkumar, Yuan Deng, Rong Ge, and Hossein Mobahi. Homotopy analysis for tensor pca. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research , pages 79--104. PMLR, 07--10 Jul 2017

work page 2017

[3] [3]

Algorithmic thresholds for tensor pca

G \'e rard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor pca. The Annals of Probability , 48(4):2052--2087, 2020

work page 2020

[4] [4]

High-dimensional analysis of semidefinite relaxations for sparse principal components

Arash A Amini and Martin J Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE international symposium on information theory , pages 2454--2458. IEEE, 2008

work page 2008

[5] [5]

Free energy wells and overlap gap property in sparse pca

G \'e rard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse pca. Communications on Pure and Applied Mathematics , 76(10):2410--2473, 2023

work page 2023

[6] [6]

Reducibility and computational lower bounds for problems with planted sparse structure

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory , pages 48--166. PMLR, 2018

work page 2018

[7] [7]

Concentration Inequalities: A Nonasymptotic Theory of Independence

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press, 2013

2013

[8] [8]

Tony Cai, Tengyuan Liang, and Alexander Rakhlin

T. Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Computational and statistical boundaries for submatrix localization in a large noisy matrix . The Annals of Statistics , 45(4):1403 -- 1430, 2017

work page 2017