# Tensor cumulants for statistical inference on invariant distributions arXiv: https://arxiv.org/abs/2404.18735 ยท HTML: https://mlsanity.com/paper/2404.18735/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 22 of its 49 references that are in the map. - First posted on arXiv 29 Apr 2024. ## Builds on (most cited first, 22 of 22) - [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019) - [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014) - [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017) - [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020) - [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013) - [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020) - [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015) - [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015) - [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022) - [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014) - [The Kikuchi Hierarchy and Tensor PCA](https://mlsanity.com/paper/1904.03858/) (2019) - [How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA](https://mlsanity.com/paper/1905.12294/) (2019) - [Homotopy Analysis for Tensor PCA](https://mlsanity.com/paper/1610.09322/) (2016) - [Strongly Refuting Random CSPs Below the Spectral Threshold](https://mlsanity.com/paper/1605.00058/) (2016) - [Phase Transitions for Detecting Latent Geometry in Random Graphs](https://mlsanity.com/paper/1910.14167/) (2019) - [Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics](https://mlsanity.com/paper/2004.12063/) (2020) - [Is Planted Coloring Easier than Planted Clique?](https://mlsanity.com/paper/2303.00252/) (2023) - [Spectral Methods from Tensor Networks](https://mlsanity.com/paper/1811.00944/) (2018) - [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022) - [Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks](https://mlsanity.com/paper/2008.13735/) (2020) - [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022) - [Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere](https://mlsanity.com/paper/1611.05998/) (2016) ## Built on by (most cited first, 8 of 8) - [Tensor learning with orthogonal, Lorentz, and symplectic symmetries](https://mlsanity.com/paper/2406.01552/) (2024) - [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025) - [Permutation Equivariant Neural Networks for Symmetric Tensors](https://mlsanity.com/paper/2503.11276/) (2025) - [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025) - [Constructing 3D Rotational Invariance and Equivariance with Symmetric Tensor Networks](https://mlsanity.com/paper/2508.12596/) (2025) - [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025) - [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025) - [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025) ## Abstract (arXiv) Many problems in high-dimensional statistics appear to have a statistical-computational gap: a range of values of the signal-to-noise ratio where inference is information-theoretically possible, but (conjecturally) computationally intractable. A canonical such problem is Tensor PCA, where we observe a tensor Y consisting of a rank-one signal plus Gaussian noise. Multiple lines of work suggest that Tensor PCA becomes computationally hard at a critical value of the signal's magnitude. In particular, below this transition, no low-degree polynomial algorithm can detect the signal with high probability; conversely, various spectral algorithms are known to succeed above this transition. We unify and extend this work by considering tensor networks, orthogonally invariant polynomials where multiple copies of Y are "contracted" to produce scalars, vectors, matrices, or other tensors. We define a new set of objects, tensor cumulants, which provide an explicit, near-orthogonal basis for invariant polynomials of a given degree. This basis lets us unify and strengthen previous results on low-degree hardness, giving a combinatorial explanation of the hardness transition and of a continuum of subexponential-time algorithms that work below it, and proving tight lower bounds against low-degree polynomials for recovering rather than just detecting the signal. It also lets us analyze a new problem of distinguishing between different tensor ensembles, such as Wigner and Wishart tensors, establishing a sharp computational threshold and giving evidence of a new statistical-computational gap in the Central Limit Theorem for random tensors. Finally, we believe these cumulants are valuable mathematical objects in their own right: they generalize the free cumulants of free probability theory from matrices to tensors, and share many of their properties, including additivity under additive free convolution.