Statistical Query Lower Bounds for Tensor PCA
share
In the Tensor PCA problem introduced by Richard and Montanari (2014), one is given a dataset consisting of n samples π_1:n of i.i.d. Gaussian tensors of order k with the promise that πΌπ_1 is a rank-1 tensor and πΌπ_1 = 1. The goal is to estimate πΌπ_1. This problem exhibits a large conjectured hard phase when k>2: When d β² n βͺ d^k/2 it is information theoretically possible to estimate πΌπ_1, 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 πΌπ_1 is symmetric or not. For symmetric, even order tensors, we also isolate a sample size regime in which it is possible to test if πΌπ_1 = 0 or πΌπ_1 β 0 with polynomially many queries but not estimate πΌπ_1. Our proofs rely on the Fourier analytic approach of Feldman, Perkins and Vempala (2018) to prove sharp SQ lower bounds.
READ FULL TEXT