Statistical Query Lower Bounds for Tensor PCA

Abstract

In the Tensor PCA problem introduced by Richard and Montanari (2014), one is given a dataset consisting of $n$ samples ${\mathbf{T}}_{1:n}$ of i.i.d. Gaussian tensors of order $k$ with the promise that $\mathbb{E}{\mathbf{T}}_1$ is a rank-1 tensor and $\Vert \mathbb{E}{\mathbf{T}}_1\Vert =1$. The goal is to estimate $\mathbb{E}{\mathbf{T}}_1$. This problem exhibits a large conjectured hard phase when $k>2$: When $d\lesssim n\ll d^{\frac{k}{2}}$ it is information theoretically possible to estimate $\mathbb{E}{\mathbf{T}}_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 $\mathbb{E}{\mathbf{T}}_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 $\mathbb{E}{\mathbf{T}}_1=0$ or $\mathbb{E}{\mathbf{T}}_1\ne 0$ with polynomially many queries but not estimate $\mathbb{E}{\mathbf{T}}_1$. Our proofs rely on the Fourier analytic approach of Feldman, Perkins and Vempala (2018) to prove sharp SQ lower bounds.

References in corpus (13)

• Statistical physics of inference: Thresholds and algorithms
• A statistical model for tensor PCA
• Algorithmic thresholds for tensor PCA
• Tensor principal component analysis via sum-of-squares proofs
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm
• Statistical Queries and Statistical Algorithms: Foundations and Applications
• Dealing with Range Anxiety in Mean Estimation via Statistical Queries
• On Mean Estimation for General Norms with Statistical Queries

Cited by in corpus (3)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Clustering a Mixture of Gaussians with Unknown Covariance