Statistical Query Lower Bounds for Tensor PCA

In the Tensor PCA problem introduced by Richard and Montanari (2014), one is given a dataset consisting of n samples T-1:n of i.i.d. Gaussian tensors of order k with the promise that ET1 is a rank-1 tensor and parallel to ET1 parallel to = 1. The goal is to estimate ET1. This problem exhibits a large conjectured hard phase when k > 2: When d less than or similar to n << d(k/2) it is information theoretically possible to estimate ET1, but no polynomial time estimator is known. We provide a sharp analysis of the optimal sample complexity in the Statistical Query (SQ) model and show that SQ algorithms with polynomial query complexity not only fail to solve Tensor PCA in the conjectured hard phase, but also have a strictly sub-optimal sample complexity compared to some polynomial time estimators such as the Richard-Montanari spectral estimator. Our analysis reveals that the optimal sample complexity in the SQ model depends on whether ET1 is symmetric or not. For symmetric, even order tensors, we also isolate a sample size regime in which it is possible to test if ET1 = 0 or ET1 not equal 0 with polynomially many queries but not estimate ET1. Our proofs rely on the Fourier analytic approach of Feldman et al. (2018) to prove sharp SQ lower bounds.

Automated summary

In the study of the Tensor PCA problem within the Statistical Query model, a sharp analysis was conducted on the optimal sample complexity. It was found that for symmetric even-order tensors, it is possible to test if ET1 = 0 or ET1 ≠ 0 with polynomially many queries, but not estimate ET1.