# Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials arXiv: https://arxiv.org/abs/2211.05274 · HTML: https://mlsanity.com/paper/2211.05274/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 57 of its 101 references that are in the map. - First posted on arXiv 10 Nov 2022. ## Builds on (most cited first, 30 of 57) - [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016) - [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016) - [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) - [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020) - [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017) - [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019) - [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) - [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018) - [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022) - [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019) - [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020) - [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020) - [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015) - [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017) - [Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models](https://mlsanity.com/paper/1902.00139/) (2019) - [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018) - [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021) - [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013) - [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014) - [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014) - [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015) - [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016) - [On the Optimization Landscape of Tensor Decompositions](https://mlsanity.com/paper/1706.05598/) (2017) - [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013) - [The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures](https://mlsanity.com/paper/1311.2891/) (2013) ## Built on by (most cited first, 6 of 6) - [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024) - [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023) - [Towards Quantum Tensor Decomposition in Biomedical Applications](https://mlsanity.com/paper/2502.13140/) (2025) - [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024) - [A large deviation view of stationarized fully lifted blirp interpolation](https://mlsanity.com/paper/2506.19273/) (2025) - [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025) ## Abstract (arXiv) Suppose we are given an n-dimensional order-3 symmetric tensor T ∈ (ℝn)otimes 3 that is the sum of r random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when r lesssim n2 but polynomial-time algorithms are only known in the regime r ll n3/2. Similar "statistical-computational gaps" occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a "planted versus null" testing problem. We consider a model for random order-3 tensor decomposition where one component is slightly larger in norm than the rest (to break symmetry), and the components are drawn uniformly from the hypercube. We resolve the computational complexity in the LDP model: O(log n)-degree polynomial functions of the tensor entries can accurately estimate the largest component when r ll n3/2 but fail to do so when r gg n3/2. This provides rigorous evidence suggesting that the best known algorithms for tensor decomposition cannot be improved, at least by known approaches. A natural extension of the result holds for tensors of any fixed order k ≥ 3, in which case the LDP threshold is r ~ nk/2.