论文标题
张量PCA的统计查询下限
Statistical Query Lower Bounds for Tensor PCA
论文作者
论文摘要
在Richard and Montanari（2014）引入的张量PCA问题中，一个数据集由$ n $ samples组成$ \ mathbf {t} _ {1：n} $ of I.I.D.。订单$ k $的高斯张量，并承诺$ \ mathbb {e} \ mathbf {t} _1 $是rank-1 tensor，$ \ | \ | \ | \ m rathbb {e} \ mathbf {t} _1 _1 \ | = 1 $。目标是估计$ \ mathbb {e} \ mathbf {t} _1 $。当$ k> 2 $：当$ d \ lyssim n \ ll d^{\ frac {k} {2}} $当$ d \ lyssim n \ ll d^{2}} $时，从理论上讲是可以估计的信息可以估算$ \ mathbb {e} \ mathbf {t} _1 $，但无知的polynomial extorator nosector。我们对统计查询（SQ）模型中最佳样品复杂性进行了彻底的分析，并表明具有多项式查询复杂性的SQ算法不仅无法在猜测的硬阶段求解张量PCA，而且与某些多项估算器相比，具有严格的亚次级样品复杂性，例如严格的亚次级样品复杂性。我们的分析表明，SQ模型中的最佳样本复杂性取决于$ \ mathbb {e} \ Mathbf {t} _1 $是对称的。对于对称的，甚至是订单张量，我们还隔离了样本量制度，可以在其中测试如果$ \ Mathbb {e} \ MathBf {t} _1 = \ MathBf {0} $或$ \ Mathbb {e} $ \ mathbb {e} \ mathbf {t} _1 $。我们的证明依赖于费尔德曼，珀金斯和Vempala（2018）的傅立叶分析方法证明了SQ的尖锐下限。
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 $\|\mathbb{E} \mathbf{T}_1\| = 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 = \mathbf{0}$ or $\mathbb{E}\mathbf{T}_1 \neq \mathbf{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.
