# Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity

arXiv: https://arxiv.org/abs/2204.07526 · HTML: https://mlsanity.com/paper/2204.07526/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2022.

## Built on by (most cited first, 12 of 12)

- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations](https://mlsanity.com/paper/2406.11828/) (2024)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensions](https://mlsanity.com/paper/2503.23896/) (2025)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Wasserstein Projection Pursuit of Non-Gaussian Signals](https://mlsanity.com/paper/2302.12693/) (2023)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledge](https://mlsanity.com/paper/2605.12908/) (2026)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)

## Abstract (arXiv)

Tensor PCA is a stylized statistical inference problem introduced by Montanari and Richard to study the computational difficulty of estimating an unknown parameter from higher-order moment tensors. Unlike its matrix counterpart, Tensor PCA exhibits a statistical-computational gap, i.e., a sample size regime where the problem is information-theoretically solvable but conjectured to be computationally hard. This paper derives computational lower bounds on the run-time of memory bounded algorithms for Tensor PCA using communication complexity. These lower bounds specify a trade-off among the number of passes through the data sample, the sample size, and the memory required by any algorithm that successfully solves Tensor PCA. While the lower bounds do not rule out polynomial-time algorithms, they do imply that many commonly-used algorithms, such as gradient descent and power method, must have a higher iteration count when the sample size is not large enough. Similar lower bounds are obtained for Non-Gaussian Component Analysis, a family of statistical estimation problems in which low-order moment tensors carry no information about the unknown parameter. Finally, stronger lower bounds are obtained for an asymmetric variant of Tensor PCA and related statistical estimation problems. These results explain why many estimators for these problems use a memory state that is significantly larger than the effective dimensionality of the parameter of interest.