Computer Science Mathematics
Computer Science-2021.gz:143369
Computer Science Mathematics
1ef0d3a19fb2a9063e803fa97bbaca94ee518565
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 $\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.


Introduction
In the Tensor PCA testing problem, one is given a dataset consisting of n i.i.d. tensors T 1:n ∈ k R d , k ≥ 2, and the goal is to determine if the tensors were drawn from the null hypothesis D 0 , D 0 : (T i ) j1,j2,...,j k i.i.d.
∼ N (0, 1) ∀ j 1 , j 2 , . . . , j k ∈ [d], ∀ i ∈ [n], or from a distribution in the composite alternate hypothesis, where under the alternate hypothesis D V the entries of the tensor are distributed as In the Tensor PCA estimation problem, given a dataset T 1:n sampled i.i.d. from an unknown distribution D ∈ D, the goal is to estimate the signal tensor E D T = V / √ d k . When k = 2, this model is called the Spiked Wigner Model and is often attributed to Johnstone [20], who introduced a variant of this model as a non-null model for Principal Component Analysis. For general k, this model was introduced by Richard and Montanari [27] 1 , who envisioned this model as stylized setup to study statistical and computational phenomena occurring in higher order moment based estimators for fitting latent variable models [2]. In these applications, a suitable sample moment tensor can also be decomposed as a sum of a low rank population tensor, which contains information about parameters of interest, and a random tensor arising due to finite sample fluctuations.
The most striking feature of the Tensor PCA problem is that it exhibits a large gap between the information theoretically optimal performance and the performance achieved by computationally efficient estimators when k > 2.
Estimating the mean of a Gaussian tensor in general requires n ≍ d k samples. However, in the Tensor PCA problems since the mean is low rank, the information theoretic sample complexity requirement is n ≍ d. For example, when the signal tensor is symmetric, it is known that there exists a critical value β ⋆ k such that if n < (β ⋆ k − o d (1)) · d, then it is information theoretically impossible to solve the Tensor PCA testing or estimation problems [24]. On the other hand, the results of Richard and Montanari [27] imply the existence of another threshold β ♯ k such that if n > (β ♯ k + o d (1)) · d, then tests and estimators based on the maximum likelihood value: have a non-trivial testing and estimation performance. When k > 2, no computationally efficient algorithm to solve the optimization problem in Eq. 1 is known. Richard and Montanari have proposed a computationally tractable relaxation of the optimization problem that flattens the mean tensor T into a d ⌈ k 2 ⌉ ×d ⌊ k 2 ⌋ matrix and uses the largest singular value and vector of the resulting matrix for testing and estimation respectively. This procedure requires n d k 2 to solve the testing and estimation problems [16,32]. To this date no known computationally efficient procedure improves on the performance of the Richard-Montanari spectral method. Consequently it is conjectured that any computationally efficient testing or estimation procedure requires n d k 2 samples. While proving this conjecture remains a challenging open problem, recent works have exhibited some evidence that lend credibility to this conjecture.
In this paper, we study lower bounds on a class of algorithms for Tensor PCA: those that can be implemented in Statistical Query (SQ) computational model introduced by Kearns [21]. In the SQ Model, the estimation or testing procedure does not have direct, unrestricted access to the data T 1:n generated from the unknown distribution D ∈ D ∪ {D 0 }, but instead can access the data only through an oracle. The algorithm can query the oracle with a statistic q of interest, and the oracle returns an estimate of the expected value of the statistic E D q(T ). The response of the oracle, denoted byÊ D q(T ), has an error guarantee comparable to the error guarantee of the mean of the statistic on the dataset, but can be otherwise arbitrary (see Definition 1); that is, The SQ framework to study computational-statistical gaps aims to show that in the regime where no polynomial time estimators are known for the learning problem, no SQ algorithm can solve the learning problem after making only polynomially many queries. We emphasize that a successful SQ algorithm must work with an arbitrary oracle whose errors |Ê D q(T ) − E D q(T )| are possibly adversarial but do satisfy the requirement of Eq. 2, and not just the most natural sample mean oracle which estimates E D q(T ) by the empirical mean of q(·) on n samples drawn from D. This strong robustness requirement which is expected in the SQ model is what makes it possible to prove strong lower bounds in this model. At the same time, one hopes that though most practical procedures require direct access to the samples T 1:n , they are essentially computing certain adaptively chosen statistics q on the dataset. Moreover, one hopes that their analysis only relies on the fact that the sample mean of these statistics satisfies an error guarantee of the form given in Eq. 2. It would then be possible to implement these procedures in the SQ model without any degradation in their performance and hence, lower bounds proved in the SQ model would apply to these procedures. Indeed, these hopes have been realized in a number of problems which exhibit statistical-computational gaps. Two notable examples are the Planted Clique problem [13] and sparse PCA [29]. Both of these problems exhibited a gap between the information theoretically optimal performance and the performance of the best known polynomial time estimator. The performance of the best known polynomial time estimator can be achieved in the SQ model and moreover is the best possible performance in the SQ model. Hence, for these problems the SQ Model provides a framework to prove lower bounds on the sample complexity of a class of computationally tractable estimators which include the best known estimators for this problem. Furthermore, the SQ lower bounds for these problems provide an intuitive mechanistic explanation for the observed statistical-computational gap based on the informational structure of the problem: In order to declare that the unknown distribution D ∈ D, an SQ algorithm must rule out all alternate hypothesis D 1 ∈ D by asking queries such that |Ê D q(T ) − E D1 q(T )| is more than the finite sample fluctuations expected from n samples. The SQ lower bound proceeds by exhibiting an exponentially large (in d) collection of distributions H ⊂ D such that even the single most powerful query is able to rule out only a small fraction of the distributions in H (more precisely, o(d −t ) fraction for any t ∈ N). Consequently, any SQ algorithm must make a superpolynomial number of queries to solve these problems in the regimes where they are believed to be computationally hard. More recently, SQ lower bounds have also been used to reason about computational hardness of various robust estimation problems [10,11]. We also refer the reader to the recent review article on the SQ model [26].

Problem Definition and the Statistical Query Model
Recall that in the alternative hypothesis for Tensor PCA, ET = V / √ d k , where V is a rank-1 tensor with V = √ d k . Hence we can write V as: In the standard symmetric version of Tensor PCA introduced by Richard and Montanari, one further assumes v 1 = v 2 = · · · = v k . However, the completely asymmetric version where this constraint is not enforced is also common in the literature [32,31]. It turns out that the asymmetric Tensor PCA problems are harder to solve for SQ algorithms that make only polynomially many queries. In order to get more insight into this phenomena, in this paper, we study a generalization of Tensor PCA to incorporate partial symmetries where only some of the v i 's are identical. This interpolates between symmetric Tensor PCA on one end and completely asymmetric Tensor PCA on the other end. The generalization is parametrized by integers k, K ∈ N with K ≤ k and a labelling function π : [k] → [K] such that, under the alternate hypothesis, For example, if k = 3, K = 2 and π(1) = π(2) = 1, Hence, we define the composite alternative hypothesis: In order to prove the strongest possible lower bounds, we will assume the algorithm knows the labelling function π.
In the (generalized) Tensor PCA testing problem, the testing algorithm is given data T 1:n sampled i.i.d. from some unknown D ∈ {D 0 } ∪ D(π) and has to decide if D = D 0 or D ∈ D(π). In the (generalized) Tensor PCA estimation problem, the data is generated from an unknown D ∈ D(π) and one seeks to estimate E D T with small error. We study tests and estimators for Tensor PCA in the Statistical Query framework, where the algorithm can access the data only through the VSTAT oracle introduced by Feldman et al. [13].
Definition 1 (VSTAT oracle for Tensor PCA). For any D ∈ {D 0 } ∪ D(π) and any n ∈ N, VSTAT D (n) is an oracle that, when given as input an arbitrary function q : k R d → [0, 1], returns an estimateÊ D q(T ) of the expectation E D q(T ) with the error guarantee: The parameter n is known as the effective sample size of the oracle.
The rational for defining the oracle in this way is that the error guarantee of the oracle given in Eq. 3 is comparable to the error guarantee obtained if one estimated E D q(T ) with its sample average on a dataset of size n drawn from the distribution D. This is also why the parameter n in VSTAT D (n) is interpreted as the effective sample size. Our goal is to understand how large must the effective sample size n be for there to exist an SQ algorithm to solve the Tensor PCA testing problem by making only polynomial number of queries in the following sense: Definition 2 (Tensor PCA Testing in the SQ Model). An algorithm A solves the Tensor PCA testing problem in the SQ model with n samples and B queries if, for any D ∈ {D 0 } ∪ D(π) (unknown to A), given access to an arbitrary VSTAT D (n) oracle, A correctly decides if D = D 0 or D ∈ D(π) after making at most B (possibly adaptive) queries to VSTAT D (n).

Definition 3 (Tensor PCA Estimation in the SQ Model
). An algorithm A solves the Tensor PCA estimation problem in the SQ model with n samples and B queries if, for any D ∈ D(π) (unknown to A), given access to an arbitrary VSTAT D (n) oracle, A returns an estimateV such that after making at most B (possibly adaptive) queries to VSTAT D (n).
The sample complexity of Tensor PCA in the Statistical Query depends on some structural properties of the labelling function π. For any i ∈ [K], let s i be the number of times label i is used in the labelling function π: The sample complexity of Tensor PCA depends crucially on the number of labels that are used an odd number of times. We denote this parameter by o and call it the oddness parameter of the labelling function π, i.e., o = |{i ∈ [K] : s i is odd}|. Note that o ∈ {0, 1, . . . , k}.

Our Contribution
Our main result is the following SQ lower bound for Tensor PCA. Then for any L ∈ N, there exists a positive constant c 1 (k, L, ǫ, C 0 ) > 0 depending only on k, L, ǫ, C 0 and a finite constant C 1 (k, L, ǫ) < ∞ depending only on k, L, ǫ such that for all d ≥ C 1 (k, L, ǫ), any SQ algorithm that solves any of the above problems must make at least c 1 (k, L, ǫ, C 0 ) · d L queries.
We also design optimal SQ procedures, which show that the above lower bounds are tight.
Theorem 2. There exist SQ algorithms that make O(d k · log(n)) queries and solve: 1. The Tensor PCA testing problem with o = 0 provided n ≫ √ d k .
3. The Tensor PCA testing and estimation problems with o ≥ 1 provided n ≫ √ d k+o .
Our results have the following implications: 1. As mentioned previously, when k ≥ 3, no known computationally efficient algorithm is able to leverage the low rank structure in Tensor PCA optimally. Our results show that SQ algorithms also do not work in the conjectured hard phase d n ≪ √ d k .
The SQ framework leverages the adversarial corruptions in the query responses to prove strong lower bounds. However, our result shows that these adversarial corruptions have the unintended effect of making the SQ lower bounds too pessimistic: 2. When k = 2, the estimator based on the best rank-1 approximation to T is able to effectively leverage the low dimensional structure and attain the information theoretic sample complexity in polynomial time. In contrast, SQ estimators with polynomial query complexity are ineffective at taking advantage of this low dimensional structure and require as many samples as in the case when the mean is unstructured (n d 2 ).
3. When k ≥ 3, SQ estimators with polynomially many queries are still less effective than known polynomial time algorithms in taking advantage of the low rank structure, however now, the effectiveness of SQ procedures depends crucially on the underlying symmetry of the mean tensor. They are least effective when the mean tensor is completely asymmetric, where they require as many samples as in the unstructured case (n d k ).
4. When o = 0 (e.g., even-order symmetric Tensor PCA), the problem exhibits an estimation-testing gap in the SQ model: in the regime √ d k n ≪ √ d k+2 testing is possible but estimation is not. No such testing-estimation gap is seen outside the SQ model.
The ineffectiveness of SQ algorithms seems connected to the fact that leveraging the low rank structure requires solving stochastic non-convex optimization with adversarial, inexact gradient oracles. The results of Feldman et al. [14] show that stochastic convex optimization problems based on n samples (such as the least squares problem) can be solved with restricted access to a VSTAT(n) oracle with no degradation in performance. In contrast, our estimation lower bound for the symmetric spiked Wigner problem (k = 2, o = 0, ET = v 0 v T 0 ) exhibits a canonical, benign stochastic non-convex optimization problem: max v =1 E v, T v which cannot be solved with a VSTAT(n) oracle without a degradation in sample complexity compared to its empirical version: max v =1 v, T v . This rules out non-convex extensions to the results of Feldman et al. [14] without a worse dependence on problem parameters. This suboptimality of SQ algorithms seems to arise because random initialization starts close to a saddle point of the population objective. In the spiked Wigner case, the n sample empirical gradient at initialization , the noise g is randomly oriented, g, v 0 ≈ n −1/2 , and hence when n ≫ d, the signal part dominates the noise part in the projection of the gradient along v 0 at initialization. This signal is amplified in the subsequent iterations of the power method. In contrast, when a VSTAT(n) oracle is used, the approximate gradient is of the form 2 v 0 , v init v 0 + 2g, where g 2 ≈ g 2 ≈ d/n; but the noise vectorg is no longer randomly oriented and can be adversarially chosen to cancel out the signal unless n ≫ d 2 .
Given that SQ algorithms are suboptimal for Tensor PCA, one might wonder why one should care about SQ lower bounds for Tensor PCA. Indeed, the SQ prediction of the threshold for hardness of Tensor PCA is nowhere near the correct (conjectured) threshold, so SQ lower bounds are not evidence for the computational hardness of the problem. We believe that SQ lower bounds for Tensor PCA are still useful for two reasons. (1) Currently, there are several frameworks to predict computational-statistical gaps including SQ lower bounds, Hopkins' Low Degree method [19,22], reductions from other hard problems [5], and statistical physics heuristics like failure of Belief Propagation [30]. We believe it is of interest to report successes and failures of these frameworks in canonical problems to understand their relative strengths and weaknesses. (2) SQ lower bounds are also useful even beyond the study of computational-statistical gaps. SQ algorithms are robust since they can't use specialized properties of finite sample fluctuations implied by model assumptions. This is desirable in practice, and it is of interest to understand how the sample complexity changes under some natural deviations from model assumptions.

Related Work
Studies of Computational-Statistical Gap in Tensor PCA: A number of works have investigated the computationalstatistical gap in Tensor PCA. Arous et al. [4] have shown that in the information theoretic regime n ≍ d, the expected number of local maximizers of the maximum likelihood optimization problem (Eq. 1) is exponentially large. These local maximizers can potentially trap gradient based methods. Arous et al. [3] have shown that when n ≫ d k−1 , Langevin Dynamics succeeds in solving Tensor PCA and that this is essentially tight for Langevin Dynamics to work. Sum of Squares relaxations for Tensor PCA have been analyzed [16,17,18,6] and it is known that computationally efficient sum-of-squares based procedures match the performance of the Richard-Montanari spectral estimator but fail to improve on it. Moreover, these works suggest a general heuristic calculation known as the Low Degree method [19,22] to predict computational-statistical gaps which consistently reproduces widely believed average case hardness conjectures for a number of problems including Tensor PCA. Another popular way to provide evidence for hardness of a particular problem is via reductions, i.e., to show that solving it would lead to algorithms to solve another problem which is widely believed to be hard. Reductions were introduced to reason about the hardness of statistical inference problems in the seminal work of Berthet and Rigollet [5]. In the specific case of Tensor PCA, it has been shown that hardness of Hypergraph Planted Clique implies the hardness of Tensor PCA [31,9].
Our results reveal a gap between the optimal sample complexity of Tensor PCA for polynomial query SQ algorithms and computationally efficient algorithms. A well known example of this situation is efficient learning of parity functions (in a noise-free setting), which is possible using the Gaussian elimination algorithm, but not using SQ algorithms [8]. Apart from this, we are aware of at least two other instances where SQ algorithms are suboptimal in comparison to some computationally efficient and noise tolerant procedure, which we discuss next.
Planted Satisfiability: Feldman et al. [15] study a broad class of planted random planted constraint satisfaction problems in which an unknown assignment σ ⋆ ∈ {0, 1} d is fixed and we observe n clauses C 1 , C 2 , . . . , C n drawn independently and uniformly at random from a family of clauses C, conditioned on σ ⋆ being a satisfying assignment for the clause. The goal is to identify the planted assignment σ ⋆ . When C is the set of all XOR expressions involving k variables, the problem is called the planted k-XOR-SAT problem and exhibits a large computational-statistical gap: observing n d log(d) clauses is information theoretically sufficient to identify the planted assignment σ ⋆ with high probability. However, all noise-tolerant and computationally efficient methods require n d k 2 clauses. On the other hand, Feldman et al. [15] show that SQ algorithms fail unless n d k . Moreover, this work introduces the Fourier analytic approach to prove SQ lower bounds that we rely on. Previous approaches for proving SQ lower bounds [13] are only able to show a weaker sample complexity lower bounds of n d k 2 for k-XOR-SAT as well as k-Tensor PCA. This work also proposes a hierarchical generalization of the VSTAT(n) oracle for satisfiability problems known as the MVSTAT(n, ℓ) oracle where ℓ is a parameter controlling the strength of the oracle. The oracle is designed such that, for a well-chosen value of ℓ, it is possible to implement a particular d k 2 sample complexity estimator for k-XOR-SAT without any degradation in performance.

Matrix Mean Estimation:
The recent work Li et al. [23] studies mean estimation on general normed spaces. Their results on matrix mean estimation with respect to the operator norm ( · op ) are particularly relevant for our problem. In this problem, one is given n samples X 1 , X 2 , . . . , X n of d×d matrices sampled i.i.d. from some distribution supported on unit operator norm ball, and the goal is to estimate EX with an error of ǫ = 0.1 in operator norm. By the matrix Bernstein inequality [28], when n log(d), the empirical average of the matrices X satisfies X − EX op ≤ 0.1. On the other hand, Li et al. show that in the SQ model one requires n d samples to solve this problem. Though their results are stated for unstructured matrix mean estimation, the hard distribution they construct is supported on highly sparse Boolean matrices with a low rank expectation. Thus, after a suitable change of scale, their hard instance also shows n d 2 sample complexity lower bound in the SQ model for a non-Gaussian variant of low rank matrix mean estimation. Their proof also relies on the Fourier analytic approach of Feldman et al. [15].

Notation
Common Sets: R, N, N 0 denote the set of real numbers, natural numbers and non-negative integers respectively. We denote the finite set {1, 2 . . . , k} by [k]. The set k R d denotes the set of all d × d × · · · × d tensors with real entries.
The set k N d 0 denotes the set of all d × d × · · · × d tensors with non-negative integer entries.
Vectors, Matrices and Tensors: We denote vectors, matrices and tensors with bold face letters. We denote the d dimension vectors (1, 1, . . . , 1) and (0, 0, . . . , 0) as 1 d and 0 d . We will omit the subscript d when it is clear from the context. For vectors, · and · 1 denote the Euclidean (ℓ 2 ) norm and the ℓ 1 norm respectively. For vectors a, b ∈ R d , a, b denotes the standard Euclidean inner product d i=1 a i b i . These norms and inner product are analogously defined for matrices and tensors by stacking their entries into a single vector. For a tensor T ∈ k N d 0 , we define the map SUM (T , l) : → R d which computes the partial sum of the entries of T along all modes except mode l: Likewise we define PARITY (·, ·) : , 1} d as follows: T j1,j2...j l−1 ,i,j l+1 ...j k .
In the above display, ⊕ denotes addition modulo 2.
Given a labelling function π : [k] → [K], which assigns each mode l ∈ [k] to a label π(l) ∈ K, we can combine the partial sums which leave out modes with the same label by adding them. This defines a map SUM π (T , i) : Analogously, we combine the partial parities which leave out modes with the same label via the map PARITY π (T , i) : For a tensor T , the support of T is Special Distributions: N (µ, Σ) denotes the multivariate Gaussian distribution with mean µ and covariance matrix Σ. Pois (λ) denotes the Poisson distribution with rate λ ≥ 0. Mult (n, k) denotes the Multinomial distribution governing the random vector that counts the occurrences of 1, 2, . . . , k when a fair k-faced die is independently thrown n times. For a finite set S, Unif (S) denotes the uniform distribution on S, and Unif ({±1}) is also called the Rademacher distribution.
Asymptotic Order Notation: We use the following notation to describe the behaviour of positive sequence f (d) and Miscellaneous: For real numbers a, b, a ∨ b denotes the maximum of a, b. For a vector v ∈ R d and a vector c ∈ N d 0 , we define the entry-wise factorial and the entry-wise powering notations: We also use the natural extension of the above entry-wise operators to the case when a, c are tensors.

Proof Overview for Theorem 1
For Tensor PCA with the labelling function π, we consider the following prior on Note that for any realization of V , D V ∈ D(π). Standard results on the SQ framework (developed in Feldman et al. [15], reviewed in Appendix A) show that the minimal possible query complexity of an SQ algorithm that solves the Tensor PCA testing problem with n samples is determined by the asymptotics of the following quantity: The intuition for this is as follows. Consider a fixed realization of the r.v. V . Suppose for a query q, we have Then given a response from an arbitrary VSTAT D (n) oracle, one can distinguish if | is more than the size of the error introduced by the VSTAT D (n) oracle. In this situation, we say that the query q has resolved the alternative hypothesis D V . In order to solve the composite hypothesis testing problem of distinguishing D = D 0 or D ∈ D(π), one must ask queries to resolve at least every hypothesis D V for every possible realization of V . Note that for a query q, the quantity ∆(q; D 0 ) measures the information content of a single query: the fraction of realizations of V that are resolved by the query q. In order to minimize the number of queries asked, one should ask powerful queries: single queries which resolve a large fraction of hypotheses in one go. Hence, in order to show that no SQ algorithm can solve Tensor PCA with polynomially many queries it is sufficient to show that any single query resolves at most o(d −t ) fraction of possible realizations of V ∀ t ∈ N.
For the estimation problem, we extend standard results about SQ lower bounds to show that the number of queries that need to be made to solve the estimation problem with n samples is governed by the asymptotics of a quantity analogous to object in Eq. 8 with a small change: the measure D 0 can be replaced by an arbitrary measure on D ⋆ on k R d . For most cases, choosing D ⋆ = D 0 suffices. In other cases we will choose To analyze Eq. 8, we use a key idea of Feldman et al. [15]: is a function of Boolean random vectors v 1 , v 2 , . . . , v K , and Hypercontractivity Theorems can be used to control its moments and concentration properties. Implementing this approach requires an understanding of the Fourier spectrum of E Dv π(1) ⊗···⊗v π(k) q(T ) − E D0 q(T ), which is possible due to the additive Gaussian structure of Tensor PCA. This structure is also leveraged in the Low Degree method for predicting computational-statistical gaps [19,22]. This results in the following proposition, which is proved in Appendix B.
Proposition 1. Let ǫ > 0, u ∈ N, u ≥ 2 be arbitrary. For the reference distribution D 0 , and for any query q with E D0 q 2 (T ) = 1, we have, where the coefficients p π (l 1 , l 2 , . . . , l K ) are defined as follows: For the reference measure D(π), for any query q such that E D(π) q 2 (T ) = 1, we have, where the coefficients p π (l 1 , l 2 , . . . , l K ) are defined as follows:

Asymptotics of Combinatorial Coefficients p π and p π
Proving sharp SQ lower bounds for Tensor PCA requires a tight asymptotic analysis of the combinatorial coefficients p π and p π . In order to illustrate why this requires a delicate analysis, we consider the following natural bound: where the last step follows from e = 1 + 1/1! + 1/2! + · · · . This estimate diverges exponentially with d k and is too weak for our analysis. In order to obtain tight estimates, we rely on a natural a probabilistic interpretation of the coefficients p π as a certain Poisson probability. Let C be a random tensor in k N d 0 whose entries are sampled independently as C i1,i2,...,i k Recalling the formula for the probability mass function of the Poisson distribution (Fact 7), we have Analogously, This interpretation already shows that p π ≤ 1 and p π ≤ 1, which is much better than the trivial estimate in Eq. 10. We obtain tighter bounds by taking into account the parity constraints using the following conditional independence structure in Poisson random tensors.
Proposition 2. Let C be a Poisson random tensor sampled as above. Then, we have The proof of this property can be found in Appendix F. The following result provides an exact formula for the prob- ) which in principle allows us to compute the complete asymptotic expansion for these probabilities for large d.
Rademacher distributed and independent of C. Let X i denote the mean of the entries of the random vector X i . Then, where s 1:K were defined previously in Eq. 4.
The proof of this lemma uses the following simple observation. Let Y be an arbitrary random variable taking values in N 0 . Let X be a Rademacher random variable independent of Y . Then, Appealing to this observation, we have, The expectation with respect to C can now be evaluated by conditioning on C 1 and using Proposition 2 along with the formula for the moment generating function for the Poisson and Multinomial distributions. A complete proof is provided in Appendix C.1. The advantage of the formula given in Lemma 1 is that it reduces the analysis of a combinatorial expression to controlling moments of subgaussian random variables. By expanding the exponential in Eq. 11 to a suitable order and using the fact that √ d · X i are 1-subgaussian results in the following sharp upper bounds on the combinatorial coefficients p π (l 1 , l 2 . . . l K ) and p π (l 1 , l 2 . . . l K ). Proposition 3. The coefficients p π (l 1 , l 2 . . . l K ) satisfy the following estimates: For any l 1 , l 2 . . . , l K ∈ N 0 , we have, p π (l 1 , l 2 , . . . , l K ) ≤ p π (l 1 , l 2 , . . . , l K ) and, in the special case l 1 = l 2 = · · · = l K = 0, we have, p π (0, 0, . . . , 0) ≤ C k d k . In the above equations, C k denotes a universal constant that depends only on k.
The proof of this Proposition can be found in Appendix C.2. Theorem 1 now follows immediately by substituting the above upper bounds on p π and p π in Proposition 1 with ǫ ≍ n − 1 2 . More details can be found in Appendix D.

Optimal Statistical Query Procedures
Theorem 2 claims the existence of SQ algorithms which achieve the lower bounds proved in Theorem 1. A complete description of these procedures can be found in Appendix E. Interestingly, these procedures do not try and solve either the maximum likelihood problem or its spectral relaxation. Instead, these procedures leverage the "Partial Trace" technique used by Hopkins et al. [17], Anandkumar et al. [1], Biroli et al. [7] to compress the empirical mean tensor in symmetric Tensor PCA into a vector or a matrix, and incur only a modest decrease in the signal-to-noise ratio. To implement these estimators in the SQ model, we leverage on the following result.
Fact 1 (SQ Scalar Mean Estimation; 12). There exists a SQ algorithm that given parameters ξ, B > 0, a query function q : k R d → R and access to an arbitrary after making at most 3 log(4nB/ξ 2 ) queries.
We describe the optimal SQ algorithms in the following illustrative special cases.
Even order, Symmetric Tensor PCA Testing: In this case, k = 2l for some l ∈ N and K = 1. The procedure uses Fact 1 to estimate the mean of the query T j1,j1,j2,j2...,j l ,j l .
It is easy to check that when D is in the alternative hypothesis, q(T ) ∼ N 1, √ d k and when D = D 0 , then Consequently when n ≫ √ d k , the error guarantee of the estimate from Fact 1 is small enough to ensure that null and alternate hypothesis are distinguishable.
Completely Asymmetric Tensor PCA: In this case K = k. The optimal procedure simply estimates the mean of each entry of the tensor using Fact 1. The resulting tensor of mean estimates is used as an estimate of the signal tensor for the estimation problem and its norm is used to solve the testing problem. Since the errors of a VSTAT(n) oracle can be adversarial, the error in each entry can add up. Consequently, this approach works only when n ≫ d k .
Partially Symmetric Tensor PCA: The general case can be handled by a combination of the above techniques. At a high level, the signal tensor can be written as a outer product of a compressible part and an incompressible part. In the first step, a partial trace is used to compress the tensor by eliminating the compressible part. The mean of the incompressible part is estimated entry-wise using Fact 1. The reduction in the size of the tensor during the compression phase ensures that the accumulation of adversarial SQ errors is minimized. The estimate of the incompressible part can be used to construct a test or to recover the compressible part of the signal tensor.

Effect of Noise Variance
In the formulation of Tensor PCA that we study in this paper, we assume that the noise variance is 1. It is natural to study formulations where the noise variance σ 2 is a parameter that is allowed to depend on n, d. More formally in the problem TPCA(n, d, σ 2 ) testing problem, one is given a dataset consisting of n i.i.d. tensors T 1:n ∈ k R d , k ≥ 2, and the goal is to determine if the tensors were drawn from the null hypothesis D 0 , or from a distribution in the composite alternate hypothesis, where under the alternate hypothesis D V the entries of the tensor are distributed as In the TPCA(n, d, σ 2 ) estimation problem, given a dataset T 1:n sampled i.i.d. from an unknown distribution D ∈ D(σ 2 ), the goal is to estimate the signal tensor When allowed unrestricted access to the dataset the testing and estimation problems TPCA(n 1 , d 1 , σ 2 1 ) and TPCA(n 2 , d, σ 2 2 ) are statistically and computationally equivalent if σ 2 1 /n 1 = σ 2 2 /n 2 because of the following observation.
Moreover, this sampling mechanism is computationally efficient.
Proof. Note that one can make the transformation (n 1 , σ 2 1 ) → (n 2 , σ 2 2 ) in two steps: . Hence, it is sufficient to show that given n samples from D V (σ 2 ) one can generate 1 sample from D V (σ 2 /n) and vice-versa. Note that if T 1:n Hence to generate a sample from D V (σ 2 /n) one can compute the empirical average of the n samples from D V (σ 2 ).
For the other direction, we observe that since the empirical average is a sufficient statistic for the mean parameter V of a Gaussian distribution (with known variance), the conditional law of T 1:n given T does not depend on the mean parameter V . Hence given one sample from D V (σ 2 /n) (i.e., T ) one can generate n samples T 1:n by sampling from this conditional law without the knowledge of V . Furthermore since T 1:n , T are jointly Gaussian, this conditional law is Gaussian and hence this procedure is computationally efficient.
Given the above observation, a natural question is whether the above equivalence is preserved when one can only access the data via an SQ oracle. Formally let consider a pair of distributions (D 1 , D 2 ) such that: One can ask the question: Given access to a VSTAT D1 (n 1 ) can one simulate a VSTAT D2 (n 2 ) oracle and vice-versa? This would allow us to use SQ algorithms designed for TPCA(n 2 , d, σ 2 2 ) to solve TPCA(n 1 , d, σ 2 1 ) and vice-versa and lower bounds proved for one problem would have implications for the other problem.
Observation 2. Suppose that σ 2 2 = σ 2 1 · S for some S ∈ N. Then given access to a VSTAT D1 (n 1 ) oracle can one simulate a VSTAT D2 (n 2 ) oracle with: Furthermore, this simulation makes at most 9 log(n 1 S) queries to the VSTAT D1 (n 1 ) oracle to respond to one query for the VSTAT D2 (n 2 ) oracle.
be the query for the VSTAT D2 (n 2 ) oracle. We define a new query Q as follows: We compute the mean of Q and bound its variance (under the distribution D 1 ): where equality (a) follows from the Tower Property and inequality (b) follows from the fact that conditioning reduces variance. By Fact 1 one can compute an estimateQ by making at most 9 log(n 1 S) queries which has the error guarantee (we set ξ = (2n 2 ) −1 ): As a consequence of Observation 2, the SQ lower bounds proved for TPCA(n, d, 1) in Theorem 1 can be lifted to lower bounds for TPCA(n, d, σ 2 ) provided σ 2 ≥ Ω d (1). 3. The Tensor PCA testing and estimation problems with o ≥ 1 provided n ≫ σ 2 √ d k+o .
Proof. The lower bounds follow by a proof by contradiction: if there is a polynomial query SQ algorithm which beats the claimed lower bounds for TPCA(n, d, σ 2 ) one can use it to solve TPCA(n, d, 1) using the simulation argument in Observation 2 with a sample complexity n which beats the lower bounds in Theorem 1. For the upper bound, it is straightforward to extend the analysis of the optimal SQ procedures described in Section E to arbitrary noise level σ 2 .
Remark 1. One can show that Corollary 1 holds for any σ 2 ≥ Ω d (1) (i.e., the constant 1 is not special). This is because the proof of Theorem 1 works for any constant σ 2 (not necessarily equal to 1).
Observation 2 shows that an oracle with a larger sample size and a larger noise level is no stronger than an oracle with a smaller sample size and a proportionally smaller noise level. However the converse of this does not hold. Proof. Consider the query q: Lemma 2.1 in Richard and Montanari [27] shows that if σ 2 = c/d for a small enough constant c, then we have: Furthermore Lemma 2.1 and 2.2 of Richard and Montanari show that: for some constant C > 0. Consequently, by Fact 1 we can obtain an estimateÊ D q(T ) such that |Ê D q(T )−E D q(T )| ≤ 0.1 after making O d (1) queries to a VSTAT D (n) oracle with n = O d (1) and hence solve the testing problem.
The above observation shows that the assumption that σ 2 2 ≥ 1 cannot be completely removed Corollary 1. Note that n ≥ Ω d (1) is information theoretic requirement on the sample size to solve TPCA(n, d, σ 2 ) testing problem with σ 2 = Θ d (1/d) and no known polynomial-time estimator achieves this sample complexity. Hence when σ 2 = Θ d (1/d), SQ algorithms are so powerful that they completely fail to capture the conjectured computational-statistical gap and it is, in fact, possible to implement computationally intractable estimators in the SQ model.
The discussion in this section suggests that there is a possibility that for some well chosen setting of 1/d ≪ σ 2 ≪ 1, the SQ lower bound may match the conjectured statistical-computational gap for all variants of Tensor PCA. We have not pursued this direction in our work because of the following reasons: 1. We believe that the setting σ 2 = Θ d (1) is the most natural setting to study Tensor PCA in the SQ model. This is because Tensor PCA was intended to be a stylized setup to understand tensor based methods to fit latent variable models [27]. For example, consider estimating parameter µ given data .
In these applications one observes several i.i.d. samples such that the signal-to-noise ratio per sample, measured by µ 2 /σ 2 is Θ d (1) and a sample size of n ≍ d (the dimension of the parameter) is information theoretically necessary and sufficient. In Tensor PCA since the signal tensor has norm ET = 1, this suggests the natural setting of σ 2 = Θ d (1) which is why we chose to study the TPCA(n, d, 1) formulation. In contrast TPCA(n, d, 1/d) seems very different from the situation arising in applications since the signal-to-noise ratio per sample diverges with d.
2. Setting σ 2 in a post-hoc manner to reproduce a widely believed computational-statistical gap does not seem like a satisfactory fix to the SQ model since this doesn't provide a framework to predict computational-statistical gaps in new problems.

Conclusion
In this paper, we studied the Tensor PCA problem in the Statistical Query model. We found that SQ algorithms not only fail to solve Tensor PCA in the conjectured hard phase, but they also have a strictly sub-optimal complexity compared to some polynomial time estimators such as the Richard-Montanari spectral estimator. Our analysis revealed that the optimal sample complexity in the SQ model depends on whether ET is symmetric or not. Furthermore, we isolated a sample size regime in which only testing, but not estimation, is possible for the symmetric and even-order Tensor PCA problem in the SQ model.

Acknowledgements
DH was partially supported by NSF awards CCF-1740833, DMR-1534910, and IIS-1563785, a Google Faculty Research Award, and a Sloan Fellowship.

A Framework for Statistical Query Lower Bounds
In this section, we review a few standard definitions and results used to prove SQ Lower bounds. First we review the notion of statistical dimension defined by Feldman et al. [15].
In our lower bounds, we will consider the following natural candidate for H: Our lower bounds rely on the following result which shows that the statistical dimension SDN(D ⋆ , H, ǫ) is a lower bound on the query complexity of any SQ algorithm.
Proposition 4 (15). Consider the Tensor PCA testing problem with labelling function π. Let H be any arbitrary finite subset of D(π). Any algorithm A that solves the Tensor PCA testing problem with labelling function π must make at least SDN D 0 , H(π), (3n) − 1 2 queries. Furthermore, any SQ algorithm that solves the Tensor PCA estimation problem must make at least 0.5 · SDN D ⋆ , H(π), (3n) − 1 2 queries, where D ⋆ is an arbitrary reference measure (not necessarily D 0 ).
The claim of the above proposition for the testing problem is due to Feldman et al. [15,Theorem 7.1]. Much of the literature on SQ lower bounds focuses on testing problems. However, in the context of Tensor PCA, there are subtle differences between the testing and estimation problems in the SQ model. This requires us to extend the result of Feldman et al. to estimation problems in order to obtain the second claim of the above proposition. Since the proof is based on standard arguments involved in SQ lower bounds, we have relegated the proof to the later Appendix G.
Note in order to obtain lower bounds for the estimation problem we are free to choose D ⋆ . The natural choice of D ⋆ = D 0 will be sufficient to obtain tight lower bounds for most cases. For the remaining cases we will choose D ⋆ = D(π) which is a natural 'average' of all distributions in H(π).
The following lemma presents a lower bound on the statistical dimension. Similar results are implicit in various previous works on SQ lower bounds [15].
The proof of the above lemma can also be found in Appendix G.

B Proof of Proposition 1
As a consequence of Proposition 4 and Lemma 2 from the previous section, in order to prove a lower bound on the number of queries required to solve Tensor PCA with n samples, we need to prove an upper bound on the quantity: This section is devoted to the proof of Proposition 1 which provides an analysis of the above quantity.
Proof. Consider any query q such that E D0 q 2 (T ) = 1. Observe that we have the following distributional equivalence: Hence, In the remainder of the proof, for the ease of notation, we will shorthand E v1:K ∼Unif({±1} d ) and P v1:K ∼Unif({±1} d ) simply as E and P.
Step 1: Markov Inequality. By Markov's Inequality, we have, for any u ∈ N, Step 2: Fourier Expansion of E Dv π(1) ···⊗v π(k) q(T ) − E D0 q(T ). Since the second moment of q is bounded, we can expand the query q in terms of the multivariate Hermite polynomials: We refer the reader to Appendix H.2 for definitions and basic properties of this orthonormal basis. By Parseval's identity, we have, The rational of expanding the query in this particular basis is the following elegant property (see Fact 5, Appendix H.2) 2 : After rearranging the terms in the product and recalling the SUM (·, ·), PARITY (·, ·) and entry-wise factorial and powering notations from Eqs. 5, 6 and 7 one obtains the following concise representation of the above formula: In the last step, we used the fact that v i ∈ {±1} d , ∀ i ∈ [K]. Substituting this in the Fourier expansion of q, one obtains the following representation of the bias E Dv π(1) ···⊗v π(k) H c (T ) − E D0 q(T ) as a polynomial in the Boolean vectors v 1 , v 2 , · · · v K : Observing that PARITY (c, l) ∈ {0, 1} d for any c, l we can regroup the terms in the above summation as follows: The above representation will allow us to leverage tools from Fourier analysis over the Boolean hypercube in the following step.
Hence by the ℓ 1 /ℓ ∞ Hölder's inequality: By a relabelling of [d], the expression inside the maximum in the above display depends on r 1 , r 2 · · · r K only through l 1 def = r 1 1 , l 2 def = r 2 1 · · · , l K def = r K 1 . Hence we have, where, Substituting the above bound on the second moment in Eq. 16, we obtain, Finally Markov's inequality (cf. Eq. 13) gives us, This concludes the proof of the proposition for the reference measure D 0 . The result for the reference measure D(π) follows via a similar calculation and we only sketch the argument for this case. Note that if T ∼ D 0 , then, Now consider any query function such that E D(π) q 2 (T ) = 1. This means that: Hence we can expand the function q( V (π) √ d k + ·) in the multivariate Hermite Basis: Hence, Define the tensor V (π) as: Also note that when T ∼ D 0 , then, Hence, Due to the fact that each entry of V (π) is either 1 or marginally Rademacher distributed and EV (π) = V (π), we have, .
Using Fact 5, we can compute, Hence we obtain the following Fourier expansion of the bias E Dv π(1) ⊗v π(2) ···⊗v π(k) q(T ) − E D0 q(T ): From here on wards the arguments made previously for the case when the reference distribution was D 0 can be repeated verbatim and give the second claim of the proposition.

C Asymptotic Analysis of p π and p π
Recall that Proposition 1 showed that the number of queries required to solve the Tensor PCA problems was intimately connected to the asymptotics of the combinatorial coefficients p π (l 1 , l 2 . . . , l K ) and p π (l 1 , l 2 , . . . , l K ). We had also arrived at a probabilistic interpretation of these coefficients as:

and,
p π (l 1 , l 2 , . . . , l K ) where C ∈ k N d 0 was a tensor with i.i.d. Pois d −k entries. This goal of this section is to prove Proposition 3 which provides an upper bound on these combinatorial coefficients. This section is organized as follows: • Section C.1 contains the proof of Lemma C.1 which provides a convenient analytic formula for the probabilities P(PARITY π (C, i) = (1 li , 0) ∀ i ∈ [K]).
• Section C.2 uses this formula to prove Proposition 3.

C.1 Proof of Lemma 1
Proof. The proof of this lemma relies on the following simple observation. Let Y be an arbitrary random variable taking values in N 0 . Let X be a Rademacher random variable independent of Y . Then, Appealing to this observation, we have, Recalling Eq. 5, the above expression can be written as: Hence, In the above display, the Equation marked (a) uses the conditional independence implied by Proposition 2. In the step marked (b), we used the formula for the generating function of a Multinomial distribution (Fact 2). The equality (c) uses the formula for the generating function of a Poisson distribution (Fact 3). This proves the claim of the lemma.

C.2 Proof of Proposition 3
This section is devoted to the proof of Proposition 3. Recall that Lemma 1 relates p π , p π to expectations of the form: Our strategy to analyze the above expectation will to approximate the exponential by its Taylor expansion of a suitable degree. Recalling the independence of the Rademacher vectors X 1 , X 2 · · · X K , this reduces our task to analyze expectations of the form: This is the content of the following intermediate lemma. Otherwise, where C s denotes a constant depending only on s.
Proof. When l + s has odd parity, then X s l i=1 X i is an odd polynomial in X and hence, When l > s, note that X s is a degree s polynomial, and since s < l, it is orthogonal to In order to understand its asymptotics, we decompose X as: Hence, We observe that (using the same argument made previously), when t < l, Z t is a degree t polynomial in X 1 , X 2 . . . X l and hence orthogonal to l i=1 X i : Hence, Next we observe that, where C s denotes a constant depending only on s. Substituting these estimates in the Eq. 17, we obtain, for some constant C s depending only on s. This concludes the proof of the lemma.
We now present the proof of Proposition 3 restated below for convenience.
Case 2: l i ≤ s i i = 1, 2 . . . , K, l 1 ∨ l 2 · · · ∨ l K ≥ 1. Recall that, Since l 1 ∨ l 2 · · · ∨ l K ≥ 1, can remove the condition C 1 ≥ 1: By Lemma 1, we have, Using the bound: we obtain, We note that since l 1 ∨ l 2 · · · ∨ l K ≥ 1, If s i + l i is even for each i ∈ [K], then, Lemma 3 gives us, On the other hand, if s i + l i is odd even for a single i, Lemma 3 gives us, Hence, when l i ≤ s i i = 1, 2 . . . , K, l 1 ∨ l 2 · · · ∨ l K ≥ 1, we have shown, This concludes the analysis for this case.
Case 3: ∃ i : l i > s i . By the case definition, we have, Without loss of generality, we can assume, Let t ≥ 1, t ∈ N be such that: By Lemma 1, we have, We use the bound: x a a! + e|x| t+1 (t + 1)! , |x| ≤ 1. Hence, Since For any a ≤ t, as 1 ≤ ts 1 < l 1 . Hence by Lemma 3, Finally again by Lemma 3, Note that, Hence, If l 1 ∨ l 2 · · · ∨ l K < 2k, we can rely on the better bound (since t ≥ 1): Hence, if ∃ i : l i > s i , then, Combining all of these cases gives us the claim of the proposition.

D Proof of Theorem 1
In this section we show how the various auxiliary results we have proved so far imply Theorem 1.
By Proposition 3, when l 1 ∨ . . . l K ≤ 2k, the upper bound on p π (l 1 , l 2 . . . l K ) is maximized by setting: Recall that the oddness parameter o is precisely the number s i that are odd, hence, max l1,...lK :l1∨...lK ≤2k Hence, we have obtained, Substituting this in Eq. 18, we obtain, provided d ≥ (u − 1) 2k . Now suppose there exist constants C 0 ∈ (0, ∞) and ǫ ∈ (0, k) such that, Consider any L ∈ N and suppose that, We take u = ǫ −1 · (L + (k + o)/4) in Eq. 19. This gives us, where c 1 (k, L, ǫ, C 0 ) > 0 is a constant depending only on k, L, ǫ, C 0 . Hence, by Proposition 4, any SQ algorithm which solves the Tensor PCA testing problem with n samples must make at least c 1 (k, L, ǫC 0 ) · d L queries. In order to obtain an estimation lower bound, we appeal to Proposition 4 which lets us conclude that any SQ algorithm which solves the Tensor PCA estimation problem with n samples must make at least 0.5 · c 1 (k, L, ǫC 0 ) · d L queries.

E Optimal Statistical Query Procedures
In this section we describe SQ procedures that achieve the optimal sample complexity for the Tensor PCA testing and estimation problems. These procedures leverage the "partial trace" technique. This approach was first introduced by Hopkins et al. [17] who used this technique to compress matrices obtained by flattening higher order tensors in the context of symmetric Tensor PCA with k = 3 and some other planted inference problems. A different variant of this technique was used by Anandkumar et al. [1] as a initialization procedure for tensor power method in the context of symmetric Tensor PCA with k = 3. Recent work by Biroli et al. [7] generalized this approach for Symmetric Tensor PCA with arbitrary k.
We show that procedures based on the partial trace technique can be extended to Tensor PCA with partial symmetries and can be implemented in the SQ model via Fact 1. When implemented in the SQ model, these procedures suffer from a degradation in performance (when compared to the non-SQ performance on symmetric Tensor PCA problems from prior work [17,1,7]). However, the lower bounds of the previous section show that this is unavoidable.
We first design an SQ Test for even-order Symmetric Tensor PCA. Proof. Let k = 2l. Consider the query function:

It is easy to check that for any
Consequently, we can use Fact 1 to construct an SQ procedure which returns an estimate of E D q(T ) denoted byÊq(T ) such that, . This requires only O(log(d)) queries. This can be turned into a test for Tensor PCA by declaring The correctness of this test follows by the error guarantee ofÊ D q(T ).
Next we consider testing and estimation in generalized Tensor PCA with partial symmetries. We introduce the notion of the standard form of a labelling function.
If π is in standard form, then for any D ∈ D(π), where E 1 , . . . , E l are rank-1 symmetric matrices with E i = Tr(E i ) = 1 and O is a o-order rank 1 tensor with O = 1.

Lemma 5.
There exists a SQ algorithm which given the knowledge of the labelling function π solves the Tensor PCA estimation problem after making at most O(d k · log(n)) queries provided the sample size n satisfies: Furthermore when o ≥ 1, there is a test based on this estimator that solves Tensor PCA testing problem under the same assumptions on the sample size n.
Proof. Since the algorithm knows the labelling function π, we can assume, without loss of generality that π is in standard form since by applying a suitable permutation to the modes of the tensor, the algorithm can always convert the Tensor PCA problem to the standard form. We define l def = (k − o)/2, where o is the number of labels used an odd number of times by π. We first consider the Tensor PCA estimation problem. Recall that by the definition of standard form, for any D ∈ D(π), Estimating O: We construct an estimator for O by estimating it entry-wise. Consider the query functions: q i1,i2...io (T ) = j1,j2...,j l T j1,j1,j2,j2...j l ,j l ,i1,i2...io .
Estimating E 1:l We estimate E 1 entry-wise by using the queries: Under D ∈ D(π), Hence using Fact 1, we can obtain estimatesÊ D q ab (T ) with the guarantee: We construct an estimator of E 1 , denoted byÊ 1 with entries defined by (Ê 1 ) a,b =Ê D q ab (T ). The error guarantee of this estimator is given by: By Triangle Inequality, When o = 0, the sample size assumption n ≫ √ d k+2 guarantees E 1 −Ê 1 → 0 as d → ∞. When o ≥ 1 since k − o + 2 ≤ k + o, the assumption n ≫ √ d k+o =⇒ n ≫ √ d k−o+2 and hence, E 1 −Ê 1 → 0. By a similar procedure, we can also estimate E 2 , E 3 · · · E l . Hence we have obtained estimatorsÊ 1:l such that, Estimating E D q(T ) We construct an estimator of E D T as: The error of this estimator can be computed as: This proves the claim of the lemma for estimation. For testing we observe that we only need to consider the case o ≥ 1 since Lemma 4 already handles the case o = 0. Hence for any D ∈ D(π), the estimatorÔ satisfies Ô → 1. When D = D 0 , the same analysis can be repeated to show Ô → 0. Hence we construct a test by declaring D = D 0 if Ô ≤ 0.5 and D ∈ D(π) if Ô > 0.5. This test solves the Tensor PCA testing problem for large enough d.

F Poisson Random Tensors
This section is devoted to the proof of Proposition 2 which describes a certain conditional independence structure in Poisson random tensors. We first collect some standard facts regarding the Multinomial and the Poisson distributions which will be useful for our analysis.
Definition 6 (Multinomial Distribution). For any n ∈ N, k ∈ N, the Multinomial Distribution with parameters (n, k) (denoted by Mult (n, k)) is the distribution supported on the set: with the probability mass function given by: (Mult (n, k)) .
Fact 2 (Properties of the Multinomial Distribution). Let X ∼ Mult (n, k) and Y ∼ Mult (m, k) be two independent Multinomial random vectors. Then we have, 1. The generating function of X is given by: 2. The sum X + Y is also a Multinomial random vector with X + Y ∼ Mult (n + m, k).
Definition 7 (Poisson Distribution). The Poisson distribution with parameter λ ≥ 0 denoted by Pois (λ) is the distribution on N 0 with the probability mass function: 2. The sum T = k i=1 X i is also a Poisson random variable with T ∼ Pois (kλ).
3. The conditional distribution of the random vector (X 1 , X 2 . . . , X k ) given T is multinomial: We now prove the conditional independence property of Poisson tensors (Proposition 2) which we have restated below for convenience. Let C be a random tensor in k W d whose entries are sampled independently as follows: Proposition 2. Let C be a Poisson random tensor sampled as above. Then, we have Moreover, conditioned on C 1 , we have Proof. The claim that C 1 ∼ Pois (1) is a direct consequence of the additivity property of the Poisson Distribution (cf. Fact 3.3). We will prove the claim about the conditional distribution of SUM (C, i) given T by induction on the order of the tensor, k.
Base Case, k = 2: Note that in this case C is a d × d matrix. SUM (C, 1) is the vector of row-wise sums and SUM (C, 2) are the column wise sums. We first characterise the distribution of SUM (C, 1) | C 1 . Due to the additivity property of the Poisson distribution (cf. Fact 3.2), Since Next we characterize the conditional distribution of SUM (C, 2) | C 1 , SUM (C, 1). We first observe that, In the last step, we again appealed to the Poisson-Multinomial connection (Fact 3.3). Hence by the additivity property of the Multinomial distribution (Fact 2.2), we obtain, Hence, which proves the proposition for k = 2.
Induction Hypothesis: We assume the claim of the proposition holds for Poisson tensors of order k − 1.

Induction
Step: We now prove the proposition for Tensors of order k. Since we plan to appeal to the induction hypothesis, we define a k − 1 order tensorC by summing over mode k of C: We note that, Hence by the induction hypothesis, we have, We now just need to characterize the distribution of SUM (C, k) | C 1 , SUM (C, 1), SUM (C, 2) . . . SUM (C, k − 1).
We first study its distribution conditioned on a larger σ-algebra: SUM (C, k)|C. Observe that, This shows that, This concludes the induction step and the proof of the proposition.

G Proof of Proposition 4 and Lemma 2
This section is dedicated to missing proofs from Appendix A on the framework for proving SQ lower bounds.

G.1 Proof of Proposition 4
Proof. As mentioned previously, the claim regarding the testing problem is simply Theorem 7.1 of Feldman et al. [15]. The proof of the claim for estimation is a modification of their proof. We define B as: We will prove the contrapositive of this statement: For any SQ algorithm A which makes t < B/2 queries, we will exhibit a D ∈ H(π) and a corresponding VSTAT D (n) oracle which when used to answer queries made by A results in A outputting an estimatorV whose error satisfies V − E D q(T ) ≥ 0.5 and hence A fails to solve the Tensor PCA estimation in the sense of Definition 3. We begin by specifying the adversarial VSTAT D (n) oracle: This oracle avoids committing to a specific D ∈ H(π) in the beginning and simply responds to any query q by the estimate E D⋆ q(T ). After the learning algorithm has exhausted its query budget by asking a sequence of queries q 1 , q 2 . . . , q t and declares an estimatorV , the oracle chooses a D ∈ H(π) to maximize the error of the estimate subject to the constraint that the responses are valid VSTAT D (n) responses. Define the sets: where, Then by the definition of a VSTAT D (n) oracle (Definition 1), for any D such that: the above specified adversarial oracle is a valid VSTAT D (n) oracle. We make the following claims: Claim 1: For all i ∈ [t], |A i | ≤ 2 dK /B Claim 2: There exist D 1 , D 2 such that, D 1 , D 2 ∈ H(π) \ t i=1 A i and E D1 T − E D2 T ≥ 1.
We first assume the above claims are true and prove Proposition 4. By the triangle inequality, Appealing to Claim 2, we obtain, Hence, we have found a D ∈ D(π) and a valid VSTAT D (n) oracle such that, which was the claim of Proposition 2. Finally we provide a proof of the claims made above.
Proof of Claim 1: Exactly the same claim has been proved in the proof of Theorem 7.1 in Feldman et al. [15], so we refer the reader to this paper for the proof.
Proof of Claim 2: As the SQ algorithm makes more and more queries, the set of valid choices of D for the oracle becomes smaller. We can track the set of valid choices of D and the relative distances between them by a sequence of undirected graphs. The initial graph G 0 = (V 0 , E 0 ) has the vertex set and the edge set: Note that for any two connected vertices (u 1 , . . . , u K ) and (v 1 , . . . , v K ): E Du π(1) ···⊗u π(k) T − E Dv π(1) ···⊗v π(k) T 2 = 1 d k u π(1) · · · ⊗ u π(k) − v π(1) · · · ⊗ v π(k) Due to the underlying symmetry between the vertices, it is easy to check that G 0 is a r-regular graph for some r ≥ 1.
Hence |E 0 | = |V 0 | · r/2 = r · 2 Kd−1 . After every query q t , we update the graph as follows: The new graph and E i is the set of remaining edges after all edges which involved a vertex in A i are removed from E i−1 . Since each vertex has at most r edges, we have, Hence, Since t < B/2, |E t | > |E 0 | − r · 2 dK−1 = 0. Hence |E t | ≥ 1, that is, the graph after t queries contains at least one remaining edge. The vertices corresponding to this edge yield distributions D 1 , D 2 satisfying Claim 2.

G.2 Proof of Lemma 2
Proof. In order to show the desired lower bound on SDN(D ⋆ , H(π), ǫ), it is sufficient to verify the implication in Eq. 12 from Definition 4 with m = ǫ 4 · sup q:ED 0 q 2 (T )=1 To this goal consider any S ⊂ H(π) with |S| ≥ m −1 · |H(π)| and any q with E D⋆ q 2 (T ) = 1. First we observe that, Consider any D ∈ H(π). Hence, there exist hypercube vectors v 1 , v 2 , · · · v K ∈ {±1} d such that D = D v π(1) ⊗v π(2) ···⊗v π(k) . We first prove a worst case upper bound on |E D q(T ) − E D⋆ q(T )| when D ⋆ = D 0 : In the above display, in the equation marked (a), we applied Cauchy-Schwarz inequality and in the step marked (b), we noted that under D 0 , the entries of T are i.i.d. N (0, 1) and used the formula for the Gaussian moment generating function. Hence we have obtained, for any D ∈ H(π) An exactly analogous calculation shows that: We can now verify the implication in Eq. 12: In the above display, the step marked (a) is a consequence of Eqs. 20 and 21. This verifies the implication in Eq. 12 and completes the proof of this lemma.

H Fourier Analytic Tools
This section collects some basic facts from Fourier analysis on the Boolean hypercube {±1} d and the Gaussian Hilbert space L 2 (N (0, I d )). Our reference for all these results is the book of O'Donnell [25].

H.1 Fourier Analysis on {±1} d
Consider the class of arbitrary functions f : {±1} d → R: The following is a orthonormal basis for F BOOLEAN (d): The above basis is orthonormal in the following sense: Hence given any function f ∈ F BOOLEAN (d) has a unique representation of the form: The coefficientsf (r) are called the Fourier coefficients of f . This representation satisfies the usual Parseval's identity: For any λ ≥ 1, we define the operator SMOOTH λ [·] : F BOOLEAN (d) → F BOOLEAN (d) as follows: The operator SMOOTH λ [·] smooths a function by down weighting the high degree Fourier coefficients. Hypercontractivity Theorems control L q norm of the random variable SMOOTH λ [f ](Z) in terms of L p norm of f (Z) where Z ∼ Unif {±1} d where q ≥ p for a suitable value of λ. Our results use the (2, q)-Hypercontractivity Theorem stated below.

H.2 Fourier Analysis on the Gauss Space
Consider the functional space L 2 (N (0, I d )) defined as follows: The multivariate Hermite polynomials for a complete orthonormal basis for L 2 (N (0, I d )). These are defined as follows: for any c ∈ N d 0 , define, H ci (z i ).
In the above display, for any k ∈ N 0 , H k are the usual (univariate) orthonormal Hermite polynomials with the property E N (0,1) H k (Z)H l (Z) = 0 : k = l 1 : k = l .
The orthonormality property is inherited by the multivariate Hermite polynomials and we have, Since these polynomials form an orthonormal basis of L 2 (N (0, I d )) any f ∈ L 2 (N (0, I d )) admits an expansion of the form: In the above displayf (c) ∈ R are the Fourier coefficients of f . They satisfy the usual Parseval's relation: A particular desirable property of the univariate Hermite polynomials is the following: for any µ ∈ R, k ∈ N 0 we have, This implies the following property of multivariate Hermite polynomials which will be particularly useful for us: Fact 5. For any µ ∈ R d and any c ∈ N d 0 , we have, In the above display, we are using the following notation: (c i !).