1 Introduction↩︎

A fundamental task in high-dimensional statistics is to recover a hidden signal buried in a large, noisy dataset. Alongside the information-theoretic question of determining the weakest signal strength at which recovery is possible by any estimator, the high dimensionality of these problems introduces a computational challenge: whether recovery can be achieved by an efficient algorithm of practical runtime. When there is a gap between the signal strength needed for information-theoretic recovery and that needed for computationally efficient recovery, we say there is a statistical–computational gap. Understanding the nature of such gaps is one of the central goals of high-dimensional statistics and average-case complexity.

In this work, we study three closely-related models in which a signal is buried in a random tensor or random hypergraph, each exhibiting a statistical–computational gap:

• Planted dense subhypergraph: For a sparsity parameter \(\rho\in [0,1]\) and edge probabilities \(0\leq q_0\leq q_1\leq 1\), we observe an \(r\)-uniform random hypergraph whose adjacency tensor \(Y\) is generated as follows. Draw \(\theta\in \{0,1\}^n\) with i.i.d.\(\Ber(\rho)\) entries. Conditional on \(\theta\), independently for each hyperedge \(e=\{i_1,\ldots,i_r\}\) of distinct vertices, draw \[Y_{e}\sim \Ber\bigg(q_0+(q_1-q_0)\prod_{j=1}^{r}\theta_{i_j}\bigg).\] Thus, hyperedges whose vertices all lie in the planted set \(\{1\leq i\leq n:\theta_i=1\}\) appear with probability \(q_1\), while all other hyperedges appear with background probability \(q_0\).

• Sparse tensor PCA: For a sparsity parameter \(\rho\in [0,1]\) and signal-to-noise parameter \(\la\geq 0\), we observe the \(r\)-th order random tensor \[Y= \lambda\theta^{\otimes r}+W\,,\] where the planted signal \(\theta\in \{0,1\}^n\) has i.i.d.\(\Ber(\rho)\) entries and \(W\in (\R^n)^{\otimes r}\) is a Gaussian noise tensor with i.i.d.entries \(W_{i_1,\ldots,i_r}\sim \cN(0,1)\).

• Tensor PCA with general prior: This is the standard model of a low-rank tensor corrupted by Gaussian noise. We again observe \(Y= \lambda\theta^{\otimes r}+W\), but now the planted signal \(\theta\) has i.i.d.entries drawn from a general prior \(\pi\) with mean \(0\) and variance \(1\).

In each model, we consider the asymptotic regime \(n\to\infty\). The parameters \(\rho\), \(\la\), \(q_0\), and \(q_1\) may scale with \(n\), while the tensor order \(r\) and the prior \(\pi\) are held fixed. All model parameters are assumed known to the statistician.

All three models have been studied extensively in the literature. In particular, statistical–computational gaps in hypothesis testing (a.k.a. detection) task—testing whether observation \(Y\) is drawn from the planted distribution as defined above or from a pure noise distribution—has been studied for all three models (we refer to [1]–[3] for extensive literature on detection) and is by now relatively well-understood.

The present work instead focuses on the estimation task: given the observed data \(Y\), recover the latent signal \(\theta\).³ Estimation has also received significant attention—we defer a thorough literature review to the discussion of each model below. In particular, for the matrix case \(r=2\), [4] pinned down sharp computational thresholds for the corresponding matrix versions of all three models. However, for tensor/hypergraph models \(r\geq 3\), the picture is much less complete, and clarifying it motivates the present work. A central question we address is

What are the limits of computationally efficient estimation in these tensor and hypergraph models, and can the exact boundary be pinned down?

For tensor PCA with a fixed prior, it is widely believed that there is a smooth tradeoff between signal and runtime [2], [5], [6]. For sparse tensor PCA and planted dense subhypergraph, by contrast, the form of the threshold has been unclear. To study this question, we employ the low-degree polynomial framework described in the next subsection. Perhaps surprisingly, we show that a sharp phase transition occurs in these two models for low-degree polynomial estimation when \(\rho \gg n^{-1/2}\), with a critical signal-to-noise ratio that we determine explicitly. In the complementary regime \(\rho\ll n^{-1/2}\) of planted dense subhypergraph, we establish the estimation hardness predicted by previous work, resolving an open question of [4], [7]; this result is new even in the graph case \(r=2\).

1.1 Low-degree estimation framework↩︎

Each of the three models described above is an average-case problem: the goal is to find an estimator that runs in polynomial time and recovers the signal with high probability when the input \(Y\) is sampled from the model, rather than an estimator that succeeds uniformly over all inputs. Proving unconditional computational lower bounds for such problems—for instance, showing that no polynomial-time algorithm can estimate \(\theta\) with probability \(1-o(1)\) as \(n\to\infty\)—appears beyond the reach of current complexity theory, so one seeks evidence for hardness through a variety of restricted computational frameworks and structural barriers. Prominent examples include the sum-of-squares hierarchy [8], the statistical query model [9], reductions from conjecturally hard problems [10], and geometric obstructions based on the overlap gap property [11]. Among these, the low-degree polynomial framework has been successful, with a strong track record of correctly predicting the computational thresholds in average-case inference problems.

The low-degree framework was first developed for detection [5], [12], where the central object is the low-degree likelihood ratio [2]. Its estimation analog was introduced by Schramm and Wein [7], who defined the low-degree MMSE as the smallest mean-squared error achievable by a polynomial estimator of degree at most \(D\). Suppose that the goal is to estimate a scalar \(x\) from the observed data \(Y\): in planted dense subhypergraph and sparse tensor PCA, \(x\) will be the first coordinate of the signal \(\theta_1\). The degree-\(D\) minimum-mean-squared-error (MMSE) is defined by \[\label{eq:def:low:MMSE} \MMSE_{\leq D} := \inf_{\substack{f \in \RR[Y] \\ \deg(f) \le D}} \EE\!\big[(f(Y)-x)^2\big]\,,\tag{1}\] where \(\RR[Y]\) denotes the space of multivariate polynomials in the entries of \(Y\), i.e. \((Y_{i_1,\ldots, i_r})_{i_1,\ldots, i_r\in [n]}\).⁴ A useful benchmark is the degree-\(0\) case, where \(\MMSE_{\leq 0}\) is the error of the trivial estimator \(f(Y)=\E[x]\), so that \(\MMSE_{\leq 0}=\Var(x)\). Accordingly, \(\MMSE_{\leq D}\geq (1-o(1))\MMSE_{\leq 0}\) says that degree-\(D\) polynomials have, asymptotically, no better performance than trivial estimation. This is the form of hardness that we establish, with degrees as large as \(D=n^{\delta}\) for some constant \(\delta>0\).

For the types of average-case problems considered here, degree-\(O(\log n)\) polynomials are often already rich enough to match the performance of the best currently known polynomial-time algorithms. Consequently, when one can show that polynomials of super-logarithmic degree fail, this is typically viewed as evidence that no polynomial-time algorithm should succeed. In this sense, the term “low-degree” usually refers to degree-\(O(\log n)\). More generally, the guiding heuristic is that degree-\(D\) polynomials correspond to algorithms with runtime \(n^{\widetilde{O}(D)}\) where \(\widetilde{O}(\cdot)\) suppresses poly-logarithmic factors in \(n\). This heuristic was formalized in work of Hopkins [1] for detection problems, but it is now known not to hold in full generality [13]. Determining the correct general formulation remains an active open problem; see the recent survey [3] for a broader discussion of how low-degree lower bounds should be interpreted. Nonetheless, the framework’s predictions have consistently matched the conjectured thresholds for natural high-dimensional models such as planted clique [7] and community detection [4], and we accordingly view our lower bounds as strong evidence for computational hardness.

1.2 Our contributions↩︎

1.2.1 Planted dense subhypergraphs↩︎

We briefly describe our main results for planted dense subhypergraph; the formal statements appear in Section 2. Consider the \(r\)-uniform planted dense subhypergraph model described above, with sparsity \(\rho\), background edge probability \(q_0\), and planted edge probability \(q_1\). The behavior of low-degree estimation differs markedly depending on whether the planted set is large, of size \(\gg\sqrt{n}\), or small, of size \(\ll\sqrt{n}\), and we address these two regimes separately. For ease of exposition, we restrict to the polynomial scaling \[\rho=n^{\xi-1}\,,\qquad q_1=n^{-a}\,,\qquad q_0=n^{-b}\] with \(0<a\leq b\) and \(\xi,a,b\) fixed. Our first main result identifies a sharp phase transition when \(\xi>1/2\), in terms of the signal-to-noise ratio \[\SNR:=\frac{e }{(r - 2)!}\frac{(n\rho^2)^{r-1}(q_{1} - q_{0})^{2}}{q_{0}(1 - q_{0})}\,.\]

Observe that the trivial estimator \(f(Y) = \E[\theta_1] = \rho\) has error \(\MMSE_{\le 0} = \rho - \rho^2\). Part (a) says that when \(\SNR \le 1 - \eps\), estimating \(\theta_1\) with polynomials in \(Y\) of degree-\(n^{2\xi - 1}\) is asymptotically no better than trivial estimation. Part (b) says that when \(\SNR \ge 1 + \eps\), a degree-\(O(\log n)\) polynomial has error \(o(\rho)\). Since \(\E\theta_1=\rho\), an error of \(o(\rho)\) means that the planted set is recovered almost perfectly. In Theorem 7 below, we turn this polynomial into a polynomial-time algorithm using the color coding trick [14]. Thus, the sharp transition at \(\SNR = 1\) from hard to easy may be viewed as a computational version of the all-or-nothing phenomenon [15]–[17]. Our theorem holds for all \(r \ge 2\) with critical constant \(e/(r-2)!\), recovering the result of Sohn and Wein [4] in the graph case \(r = 2\). For all \(r \geq 2\), the polynomial-time algorithm achieving this threshold appears to be new. See Section 2.1 for further discussion and comparison with prior work.

Theorem 1-(b) also holds for \(\rho \le n^{-1/2}\) (see Theorem 3), but in this regime the following result gives the correct computational scale.

Reading parts \((a)\) and \((b)\) as before, Theorem 2 identifies the computational boundary for estimation as the curve \(a=b\xi\), resolving a question (for \(r=2\)) raised by Schramm and Wein [7] and reiterated by Sohn and Wein [4]. For detection, the analogous low-degree hardness was established by Dhawan, Mao, and Wein [18]. The proof relies on a new conditioning argument tailored to low-degree estimation, which we expect to be of independent interest. See Section 2.1 for further discussion and Section 3.2 for an overview of the proof.

1.2.2 Other models↩︎

For sparse tensor PCA, we prove an analogous sharp phase transition for low-degree estimation in the regime \(\rho\gg n^{-1/2}\). The relevant signal-to-noise ratio is \(\widetilde{\SNR}=\frac{e(n\rho^2)^{r-1}\la^2}{(r-2)!}\). In particular, when \(n^{-1/2}\ll \rho\ll 1\), if \(\widetilde{\SNR}<1\), then degree-\(n^{\delta}\) polynomials cannot asymptotically improve upon the trivial estimator \(f(Y)=\rho\). On the other hand, if \(\widetilde{\SNR}>1\), then there exists a polynomial of degree-\(O(\log n)\) that achieves near-perfect recovery. As in the planted dense subhypergraph model, this estimator can be converted into a polynomial-time algorithm. For \(r=2\), the same low-degree phase transition was established by Sohn and Wein [4], and matching polynomial-time recovery at the same threshold was achieved by the AMP algorithm of Hajek, Wu, and Xu [19]. For \(r \ge 3\), the threshold was predicted heuristically, via an AMP analysis, by Corinzia et al. [20]; our contribution gives the first rigorous evidence for \(r\geq 3\), establishing both low-degree hardness below the threshold and a polynomial-time recovery algorithm above it.

For tensor PCA with general prior (\(r\geq 3\)), the prediction is qualitatively different: it is expected that there is a smooth tradeoff between the degree \(D\) and the signal strength for weak recovery, rather than a sharp threshold. Earlier work [1], [2], [5], [6] predicts that detection requires \(\lambda\asymp n^{-r/4}D^{-(r-2)/4}\). We rigorously establish the corresponding low-degree estimation lower bound for a broad class of priors \(\pi\), which includes all sub-exponential distributions: if \(\lambda\lesssim n^{-r/4}D^{-(r-2)/4}\), then degree-\(n^{\delta}\) polynomials cannot asymptotically improve upon trivial estimation. For the Rademacher prior, the analogous detection lower bound was proved by Kunisky, Wein, and Bandeira [2], and for the spherical prior, the corresponding estimation lower bound was proved by Kunisky, Moore, and Wein [6] (among other results). Our work treats a general class of independent priors under mild moment assumptions, via a different proof method based on cumulant bound of Schramm and Wein [7].

2 Main results↩︎

In all the models we consider, the observation is an order-\(r\) tensor \(Y \in (\R^n)^{\otimes r}\) and the estimand is a scalar \(x \in \R\); the specific choice of \(x\) will be given for each model in the subsections that follow. Recall from 1 that \(\MMSE_{\leq D}\) is the smallest mean-squared error achievable by polynomials in \(Y\) of degree at most \(D\). It is convenient to work with the low-degree correlation. Let \(\R_D[Y]\) denote the space of all (multivariate) polynomials in \(Y\) with degree at most \(D\), i.e. \(f \in \R[Y]\) with \(\deg(f) \leq D\), and define \[\label{eq:def:Corr} \Corr_{\leq D} := \sup_{f \in \R_D[Y]} \frac{\E[f(Y) \cdot x]}{\sqrt{\E[f(Y)^2]\E[x^2]}} \in [0, 1]\,.\tag{2}\] The two quantities are related by the following identity.

For our lower bounds, we rule out weak recovery. We say that weak recovery is achievable by degree-\(D\) polynomials if \(\MMSE_{\leq D} \leq (1 - \Omega(1))\MMSE_{\leq 0}\). Since \(\MMSE_{\leq 0} = \Var(x)\), this means that there exists a polynomial of degree at most \(D\) that improves on the trivial estimator \(f(Y) = \E[x]\) by a constant fraction. By Fact [fact:corr:mmse], weak recovery implies \(\Corr_{\leq D} = \Omega(1)\), so \(\Corr_{\leq D} = o(1)\) rules out weak recovery. Our hardness results establish the latter for degrees as large as \(D = n^{\delta}\) for some constant \(\delta > 0\).

For our upper bounds, we establish the stronger property of strong recovery: there exists a polynomial \(f \in \R_D[Y]\) with \(\E[(f(Y) - x)^2] = o(\Var(x))\), equivalently \(\MMSE_{\leq D} = o(\MMSE_{\leq 0})\), or by Fact [fact:corr:mmse], \(\Corr_{\leq D} = 1 - o(1)\). We achieve this with polynomials of degree \(D = O(\log n)\).

2.1 Planted dense subhypergraph↩︎

We briefly recall the planted dense subhypergraph model introduced in Section 1. Given parameters \(\rho\in (0,1)\) and \(0<q_0< q_1\leq 1\)⁵ the latent signal \(\theta = (\theta_i)_{i \in [n]}\) has i.i.d. \(\Ber(\rho)\) entries. Conditioned on \(\theta\), independently for each hyperedge \(e=\{i_1,\ldots,i_r\}\) of distinct vertices, we draw \(Y_{e}\sim \Ber(q_0+(q_1-q_0)\prod_{j=1}^{r}\theta_{i_j})\). The goal is to estimate \(x = \theta_1\). Define \[\lambda := \frac{q_1 - q_0}{\sqrt{q_0(1 - q_0)}}\,.\]

The upper bound in Theorem 3-(b) can be converted into a polynomial-time recovery algorithm via the color coding trick [12], [14], [21]; see Section 9 for the explicit algorithm and its recovery guarantee.

2.1.0.1 Discussion

The planted dense subhypergraph problem has extensive literature. For \(r=2\), it reduces to planted dense subgraph model, which has been studied from both statistical and computational perspectives. Statistical limits, both the information-theoretic threshold and performance of the maximum likelihood estimator, are established in [22]–[25]. On the computational side, hardness has been studied through low-degree polynomial lower bounds for detection [18] and for estimation [4], [7], and through average-case reductions [10], [26]. There are also positive algorithmic results [24], [27]–[29]. The special case \(r=2, q_1=1\) is the planted clique problem [30]–[35], a canonical benchmark for average-case hardness and a base for establishing reduction-based hardness in many inference problems [10], [36], [37]. For \(r \geq 3\), relatively less is known. The special case \(q_1 = 1\) is the hypergraphic planted clique problem; we refer to [38] for a discussion of open problems related to its average-case hardness. For general \(q_1 < 1\), statistical limits for weak recovery were determined by Yuan and Shang [39].

On the computational side, Luo and Zhang [40] studied the regime \(\rho\geq n^{-1/2}\) from both directions: on the hardness side [40] rules out low-degree estimation under the condition \(\SNR \leq n^{-\delta}\) for a fixed \(\delta > 0\) as \(n\to\infty\), and on the algorithmic side [40] proves that an aggregated-SVD recovers the planted set \(\{i \in [n] : \theta_i = 1\}\) exactly once \(\SNR \geq c\) for some constant \(c > 0\).⁶ Theorem 3 improves their result by determining the threshold at constant-level: estimation is low-degree hard for \(\SNR < 1\), with a matching upper bound for \(\SNR > 1\), locating the critical point with constant \(e/(r-2)!\). While preparing this paper, we became aware that the same value was predicted by the heuristic AMP analysis of Corinzia, Penna, Szpankowski, and Buhmann [20] (see the discussion after Theorem 5 for sparse tensor PCA). Theorem 7 in Section 2.4 lifts the upper bound in part (b) to a polynomial-time algorithm via a color-coding trick [12], [14], [21], achieving almost-exact recovery, which appears to be the first to attain this sharp threshold for all \(r \geq 2\). Whether its guarantee can be strengthened to exact recovery is an interesting question.

We expect the degree condition \(D^{r-1} \leq 1/(C\lambda^2)\) in Theorem 3-(a) to be optimal. A brute-force search over \(\ell\)-element subsets of \([n]\) with \(\ell =\widetilde{O}(\lambda^{-2/(r-1)})\) yields a recovery algorithm of \(\theta_1\) with runtime \(\exp(\widetilde{O}(\lambda^{-2/(r-1)}))\) (where \(\widetilde{O}\) hides the polylogarithmic factors), which is an adaptation of the subexponential time algorithms for the spiked Wigner model [41] and sparse tensor PCA [42]. This matches our lower bound under the degree-runtime heuristic (Section 1.1). See the discussion following Theorem 5 for the analogous matching in sparse tensor PCA.

In the regime \(\rho \leq n^{-1/2}\), the best known algorithm for the planted dense subgraph (\(r = 2\)) is the caterpillar-counting algorithm of Bhaskara et al. [27], which succeeds for \(a < b\xi\). The matching hardness, however, was only partially understood: Schramm and Wein [7] established low-degree estimation hardness in the region \(a > b/2\), leaving open the gap \(b/2>a >b \xi\). Whether estimation hardness extends throughout \(a > b\xi\), or whether a better algorithm could succeed up to \(a < b/2\), was raised as an open question in [7] and reiterated by Sohn and Wein [4]. For the corresponding detection task, Dhawan, Mao, and Wein [18] had established hardness throughout \(a > b\xi\); this does not settle the estimation question, however, as low-degree estimation hardness does not formally follow from its detection counterpart and is generally more delicate to establish. In fact, recent work by Tang, Han, and Zhang [43] shows that in a certain tensor cumulant inference problem, there are regimes in which computationally efficient estimation is possible while the detection task is low-degree hard.

Theorem 4 resolves this question, identifying the estimation boundary as \(a = b\xi\): part (a) shows low-degree estimation hardness for \(a > b\xi\), and part (b) establishes the existence of a matching low-degree estimator for \(a < b\xi\). The proof of part (a) relies on a conditioning argument adapted to low-degree estimation. Conditioning arguments were previously developed for detection [18], [44], [45]; we develop the analogous technique for estimation hardness, which may be useful in other models where rare events inflate the unconditional moments. We remark that our proof can track the precise dependence on \(\rho, q_0, q_1\), giving a quantitative hardness statement (see Remark [rem:small:hypergraph:quantitative]).

We also note that the computational boundary \(a = b\xi\) in Theorem 4 admits an interpretation in terms of the modified Kesten–Stigum threshold introduced by Chin, Mossel, Sohn, and Wein [46] for the sparse stochastic block model (SBM) [47]; see [48] for a survey of the model. While the planted dense subgraph model has a single planted community of size roughly \(n\rho = n^\xi\), replacing this with \(q = 1/\rho = n^{1-\xi}\) symmetric communities of the same size, where each within-community (resp. between-community) edge is drawn with probability \(q_1\) (resp. \(q_0\)), yields the analogous sparse SBM. In the regime \(q\to\infty\), the two relevant parameters are the average degree of the entire graph \(d \equiv n q_0 = n^{1-b}\) and the average degree of each community \(d\lambda_1 \equiv n^\xi q_1 = n^{\xi - a}\) (up to a \(1+o(1)\) factor). The classical Kesten–Stigum threshold \(d\lambda_1^2 = 1\) [49] governs efficient weak recovery in the SBM with a constant number of communities [4], [50]–[52]. In the sparse regime \(q \gg \sqrt{n}\), [46] showed that efficient weak recovery is possible above a modified threshold in which the exponent \(2\) is replaced by \(1/\chi\), where \(\chi\) is defined by \(q = n^\chi\), so \(\chi = 1 - \xi\). Namely, this threshold is given by \(d\lambda_1^{1/\chi}=1\) (hiding \(\log d\) factors), or equivalently \(d\lambda_1 = d^\xi\). Substituting our parameters yields \(n^{\xi - a} = n^{\xi(1 - b)}\), i.e. \(a = b\xi\), recovering the threshold curve of Theorem 4. The corresponding low-degree estimation lower bound for the SBM was established by Carpentier, Giancola, Giraud, and Verzelen using an almost-orthogonal basis approach [53] (see also [54]), which is a different method from the conditioning argument used here. This correspondence was one of the motivations for our study of the \(\rho\leq n^{-1/2}\) regime.

2.2 Sparse tensor PCA↩︎

We first introduce a symmetric version of the sparse tensor PCA model defined in Section 1, in which the Gaussian noise tensor is replaced by its symmetrization.

The asymmetric model in Section 1 is equivalent to the symmetric model from the estimation perspective: Lemma 27 in the appendix shows that the degree-\(D\) MMSE under the asymmetric model of Section 1 matches that under Definition 1 after the substitution \(\lambda \mapsto \sqrt{r!}\lambda\). In particular, when \(\rho = o(1)\), the sharp threshold of Theorem 5 below corresponds to \(er(r-1)n^{r-1}\rho^{2r-2}\lambda^2 = 1\) in the asymmetric model.

2.2.0.1 Discussion

When specialized to \(r = 2\), sparse tensor PCA is known as the planted submatrix model, and estimation has been studied from both statistical [55]–[57] and computational [4], [7], [58] perspectives. In particular, Theorem 5 specialized to \(r=2\) recovers [4].

For \(r \geq 3\), the statistical limits of estimation are well-understood [16], [40], [59]. In particular, Niles-Weed and Zadik [16] establish (with a slightly different prior where exactly \(k=n\rho\) entries in \(\theta\) are non-zero) an all-or-nothing phenomenon: for \(\rho=o(1)\), there exists a threshold \(\lambda_{\mathrm{stat}} = \sqrt{\frac{2\log(1/\rho)}{n^{r-1}\rho^{r-1}}}\) such that if \(\lambda \leq (1-\eps)\lambda_{\mathrm{stat}}\) then the estimation of \(\theta\) is information-theoretically impossible, whereas if \(\lambda \geq (1+\eps)\lambda_{\mathrm{stat}}\), then the Bayes optimal estimator achieves asymptotically perfect estimation.

By contrast, much less is known about the limits of computationally efficient estimation for \(r\geq 3\). To simplify the exposition, we specialize to the case where \(\rho = n^{\xi - 1}\) for a fixed \(\xi \in [1/2, 1)\). Luo and Zhang [40] showed that an efficient aggregated-SVD procedure succeeds for \(\lambda > \lambda_{\mathrm{alg}} = \Theta(n^{(1/2-\xi)(r - 1)})\), and [40] gives a matching exponent-level lower bound conditional on the planted dense subhypergraph recovery conjecture. Together, these results pin down the threshold for computationally efficient estimation at the exponent level, but do not determine its sharp value at the level of constants. Nonetheless, these results reveal a substantial statistical–computational gap: \(\lambda_{\mathrm{alg}}/\lambda_{\mathrm{stat}} = \widetilde{\Theta}(\rho^{-(r-1)/2})\).

A variety of algorithmic classes have been studied in connection with sparse tensor PCA. Low-temperature local reversible MCMC algorithms have been shown to fail to reach \(\lambda_{\mathrm{alg}}\) [60], only succeeding above \(\lambda_{\mathrm{MCMC}} = \widetilde{\Theta}(n^{(1-3\xi/2)(r-1)})\). A broader class of local search algorithms has subsequently been shown to reach \(\lambda_{\mathrm{alg}}\) up to polylogarithmic factors [61]. A recent related work by Tsirkas, Wang, and Zadik [62] considers a variant of sparse tensor PCA with a symmetric Rademacher prior on \(\theta\), establishing low-degree hardness for the full-tensor estimand via a different approach based on the Franz–Parisi potential from statistical physics [63], [64]. Since their result is more closely related to tensor PCA with a general prior, we defer a detailed discussion of their techniques to the paragraph following Theorem 6.

Prior to our result, the sharp threshold was conjectured in the approximate message passing (AMP) literature. Based on a heuristic argument analyzing the fixed points of the state evolution of the AMP algorithm, Corinzia, Penna, Szpankowski, and Buhmann [20] predicted that the estimation threshold is given by \(\frac{en^{r - 1} \rho^{2r - 2} \lambda^{2}}{(r - 2)!}=1\). Their analysis is stated for a fixed-\(k\) prior, with \(k\) corresponding to our \(n\rho\): in their normalized signal-to-noise ratio \(\SNR := \lambda\sqrt{\binom{k}{r}/(2k\log n)}\), their conjectured threshold reads \(\SNR_{\mathrm{AMP}} = \sqrt{\frac{1}{2e}\lPa\frac{n}{k}\rPa^{r-1}\frac{1}{r(r-1)\log n}}\), which converts back to the condition above up to a \(1+o(1)\) factor.

In the regime \(n^{-1/2} \ll \rho \ll 1\), Theorem 5 establishes a computational all-or-nothing phenomenon [15]: if \(\frac{en^{r-1}\rho^{2r-2}\lambda^2}{(r-2)!} \leq 1-\eps\), no polynomial of degree-\(n^{C}\) (for some \(C=C(r,\eps)>0\)) achieves correlation \(\omega(\sqrt{\rho})\) with \(\theta_1\); once \(\frac{en^{r-1}\rho^{2r-2}\lambda^2}{(r-2)!} \geq 1+\eps\), a polynomial of degree-\(O_{r,\eps}(\log n)\) achieves near-perfect recovery of \(\theta_1\). By contrast, in the highly sparse regime \(\rho \ll n^{-1/2}\), we do not expect the same phenomenon: exact recovery is already achieved in polynomial time at \(\lambda \gg 1\) (where \(\gg\) hides a \(\polylog(n)\) factor) by thresholding the \(n\rho\) largest values among the diagonal entries \((Y_{i,i,\ldots,i})_{i \in [n]}\) (see [42]), which is a tensor analog of diagonal thresholding for planted submatrix \(r=2\) [65]. More generally, Choo and d’Orsi [42] construct a family of estimators parameterized by an integer \(t \geq 1\), achieving almost-exact recovery with runtime \(O_r(n^{r+t})\) whenever \(\lambda \geq \widetilde{\Omega}(t^{-(r-1)/2})\). Equivalently, this requires \(t \geq \widetilde{\Omega}(\lambda^{-2/(r-1)})\), giving runtime \(\exp\{\widetilde{O}(\lambda^{-2/(r-1)})\}\). Recalling the heuristic correspondence between degree and runtime discussed in the introduction, our condition \(D^{r-1}\lambda^2 \lesssim 1\)—equivalently, \(D \lesssim \lambda^{-2/(r-1)}\)—coincides with this runtime. Therefore, our lower bound suggests that below the sharp threshold, runtime \(\exp\{\widetilde{\Omega}_{r}(\lambda^{-2/(r-1)})\}\) is required. This shows optimality of the algorithms of [42] by pinning down the precise degree-\(\Omega_r(\lambda^{-2/(r-1)})\).

2.3 Tensor PCA with general prior↩︎

We now consider tensor PCA with a general prior \(\pi\) on the entries of \(\theta\). As in Definition 1 for sparse tensor PCA, we work with the symmetric variant: the observation is \(Y = \lambda\,\theta^{\otimes r} + \Wsy\) with \(\theta \in \R^n\) having i.i.d.entries \(\theta_i \sim \pi\) and \(\Wsy\) the symmetrized standard Gaussian tensor. The asymmetric model defined in Section 1 is equivalent to this symmetric model from an estimation perspective. Indeed, the degree-\(D\) MMSE under the asymmetric model matches that under the symmetric model after the substitution \(\lambda \mapsto \sqrt{r!}\lambda\) (see Lemma 27 in the appendix). The goal is to estimate \(x = \prod_{i=1}^{m} \theta_i\) for a fixed \(m \geq 2\).

2.3.0.1 Discussion

For \(r=2\), tensor PCA with general prior is called the spiked Wigner model and is known to exhibit a sharp threshold at the BBP phase transition \(\lambda=1\) [66] for low-degree estimation [4]. The spiked Wigner model has been extensively studied from both statistical [67]–[69] and computational [70]–[72] perspectives; see [73] for a survey.

For \(r \geq 3\), the statistical thresholds for weak recovery and detection have been established for various priors [59], [74]–[76]. In particular, for odd \(r\) and i.i.d. prior \(\pi\) with bounded support, Lesieur, Miolane, Lelarge, Krzakala, and Zdeborová [74] establish a sharp threshold for weak recovery at \(\lambda_{\mathrm{stat}} = \Theta_r(n^{-(r-1)/2})\).

On the other hand, the best known algorithms require \(\lambda \gtrsim n^{-r/4}\): tensor unfolding succeeds for \(\lambda > (1+o(1)) n^{-r/4}\) [77], [78]; degree-\(4\) sum-of-squares for \(\lambda \gg n^{-3/4}\) when \(r=3\) [79]; spectral methods based on Kikuchi Hessian [80] and Langevin dynamics [81] at \(\lambda \gg n^{-r/4}\). These match the leading order of our lower bound \(\lambda \lesssim n^{-r/4} D^{-(r-2)/4}\) at constant \(D\). Recently, for the Rademacher prior and for all sufficiently large \(m\), Li [82] constructed a family of low-degree polynomial estimators with degree \(D=m\log n\) achieving weak recovery at \(\lambda \gtrsim n^{-r/4}m^{-(r-2)/4}\). In particular, the threshold at which their estimators succeed exhibits the same dependence on \(n\) and \(D\) as our lower bound, up to polylogarithmic factors.

In the low-degree polynomial framework, the optimal degree–signal tradeoff \(\lambda \asymp n^{-r/4} D^{-(r-2)/4}\) was established for detection (with Rademacher prior) by Kunisky, Wein, and Bandeira [2]. Prior to our work, the corresponding lower bound for weak recovery had been established in the spherical prior case, where \(\theta\) is drawn uniformly from \(\{\theta \in \R^n : \|\theta\| = \sqrt{n}\}\), by Kunisky, Moore, and Wein [6]. They proved that, for odd \(r \geq 3\), no polynomial of degree \(D = O_r(n^{1/2})\) achieves weak recovery whenever \(\lambda = O_r(n^{-r/4}D^{-(r-2)/4})\), exploiting the orthogonal invariance of the prior. To do so, [6] introduced a new notion of tensor cumulants, expecting that the framework of [7] alone does not yield the precise dependence of \(\lambda\) on \(D\). Somewhat surprisingly, Theorem 6 obtains the conjecturally correct dependence \(\lambda = O_r(n^{-r/4}D^{-(r-2)/4})\) directly via the cumulant approach of Schramm and Wein [7] for the broad class of i.i.d. priors with bounded moments. Our result, however, holds only over a more restricted range of \(D\) than \(O_r(n^{1/2})\) due to the technical condition \(\lambda D^{(6\nu+3)r/2} \leq 1/C\) in Theorem 6, which is likely a proof artifact.

In recent and concurrent work, Tsirkas, Wang, and Zadik [62] develop a rigorous connection between the Franz–Parisi (FP) potential from statistical physics [63], [64] and low-degree MMSE for a broad class of Gaussian additive models. Their main result establishes that, in this class, the monotonicity of the annealed FP potential is equivalent to low-degree MMSE hardness; as one application, they obtain low-degree MMSE hardness for estimating the rank-one tensor \(\theta^{\otimes r}\) in tensor PCA with i.i.d. Gaussian priors [62].⁷ For the Gaussian prior \(\pi = \cN(0, 1)\), the moment condition in Theorem 6 is satisfied with \(\nu = 1/2\). Thus, our result implies hardness for all polynomials of degree \(D = O(n^{r/(11r+2)})\) at \(\lambda =c n^{-r/4} D^{-(r-2)/4}\), where \(c=c_r>0\) is a small enough constant, while [62] gives hardness for \(D = \widetilde{o}(n^{1/2})\) at \(\lambda = \widetilde{O}_r(n^{-r/4} D^{-r/4})\). Their bound covers a larger degree range but is loose by \(\textrm{polylog}(n)\) factors and a factor \(D^{1/2}\) in \(\lambda\). It would be interesting to determine the largest exponent \(\delta\) for which our hardness bound extends to degree \(D = n^{\delta}\).

2.4 Efficient algorithm for estimation↩︎

Although Theorem 3-(b) and Theorem 5-(b) establish the existence of degree-\(O_{r,\eps}(\log n)\) polynomials achieving near-perfect correlation with the estimand \(x=\theta_1\) above the sharp thresholds, a naive evaluation of these polynomials would take \(n^{O_{r,\eps}(\log n)}\) time. The polynomials in our proofs are, however, tree-shaped: each is indexed by a hypertree (see Definition 2) on \(k = O_{r,\eps}(\log n)\) vertices. For such tree-shaped polynomials, the color-coding trick of Alon, Yuster, and Zwick [14] gives a randomized polynomial-time implementation. Namely, we randomly color the \(n\) vertices using \(k\) colors and restrict the sum to colorful hypertrees, i.e., hypertrees whose \(k\) vertices receive distinct colors. For a fixed hypertree, this occurs with probability \(q=k!/k^k=n^{-O(1)}\). After rescaling by \(1/q\), the colorful count is an unbiased estimator of the original tree-shaped polynomial. Moreover, the total colorful weighted count can be computed in polynomial time by dynamic programming over the tree structure. Averaging over \(n^{\Omega(1)}\) independent colorings reduces the additional variance from the coloring randomness, yielding a randomized polynomial-time estimator with the same asymptotic correlation. These techniques are by now standard; see, e.g., [12], [14], [21], and similar color-coded approximations were used by Li [82] to obtain polynomial-time algorithms for tensor PCA with the Rademacher prior.

Through this color coding trick, we prove the following theorem in Appendix 9 by turning our low-degree upper bound into an efficient algorithm.

To describe the algorithm, we first introduce the notion of a hypertree.

The polynomial used to establish the upper bounds in Theorem 3-(b) and Theorem 5-(b) is an average of tree-shaped polynomials indexed by the following class of hypertrees.

Equivalently, \(\alpha \in \sT_\ell\) is a rooted hypertree (with root vertex \(1\)) consisting of two disjoint rooted hypertrees of \(\ell\) edges each, each attached to vertex \(1\) by a root-incident edge.

We remark that the Preprocessing step in Algorithm 2 is only needed for our proof: it replaces each edge of \(Y\) independently with probability \(1-p\) by an independent \(\Ber(q_0)\) draw, reducing the effective signal-to-noise ratio to \(\lambda_\star = p\lambda\). As larger \(\lambda\) only makes estimation easier, this is most likely a proof artifact, and is not needed. This step is included because the proof of Theorem 3-(b) assumes \(\lambda = \lambda_\star\), so Algorithm 2 is modified to reflect this change. Since preprocessing all edges naively takes \(\binom{n}{r} \leq n^r\) time, this step does not affect the final algorithmic runtime guarantee.

The score computation in Algorithm 3 below performs a dynamic program on each \(H \in \sH_\ell\). For any rooted hypertree \(H\) with root vertex \(r_H\), the associated bipartite incidence tree \(I\) has node set \(V(H) \sqcup E(H)\), with each vertex-node \(v\) adjacent to every edge-node \(e\) containing \(v\), and is rooted at \(r_H\); the hypertree property of \(H\) ensures that \(I\) is itself a rooted tree. For each vertex-node \(v \in V(I)\), let \(\ch(v)\) denote its child edge-nodes, and for each edge-node \(e \in E(I)\), let \(\ch(e) = (v_1, \ldots, v_{r-1})\) denote its child vertex-nodes in an arbitrary fixed ordering. For each node \(a\) of \(I\), let \(H_a\) denote the rooted sub-incidence tree below \(a\), and write \(\vtx(H_a)\) for the set of vertex-nodes of \(H_a\); when \(a\) is an edge-node, this excludes the parent vertex-node of \(a\).

3 Proof techniques↩︎

We now outline the techniques used to derive our low-degree lower bounds. For tensor PCA with a general prior, we use the cumulant expansion approach of [7]. For planted dense subhypergraph and sparse tensor PCA with \(\rho\geq n^{-1/2}\), we use the orthogonal expansion approach of [4]. For planted dense subhypergraph with \(\rho\leq n^{-1/2}\), we introduce a conditional version of this method, namely orthogonal expansion with conditioning. To explain it, we first revisit the approach of [4], and then describe the modifications needed to incorporate conditioning.

3.1 Orthogonal expansion approach by [4]↩︎

Recall that our lower bounds aim to establish \(\Corr_{\leq D}=o(1)\) for some \(D=n^{\Omega(1)}\). The orthogonal expansion approach by [4] provides a systematic way to upper bound \(\Corr_{\leq D}\) via the following three steps.

Step 1: Choose a basis for \(\R_D[Y]\). Select a collection \((\phi_\alpha(Y))_{\alpha\in \GGG}\) that spans \(\R_D[Y]\), where \(\GGG\) is a suitable index set—in our applications, this will be (multi)-hypergraphs with at most \(D\) edges. This basis need not be orthogonal; it is used to expand the numerator \(\E[f(Y)\cdot x]\). Writing \(f(Y)=\sum_{\alpha\in \sG}\hat{f}_\alpha\,\phi_\alpha(Y)\), we have \[\E[f(Y)\cdot x]=\sum_{\alpha\in \GGG}c_{\alpha}\hat{f}_{\al}=\langle c\,, \hat{f}\rangle ,\quad\textrm{where}\quad c=(c_{\al})_{\alpha\in \GGG}\equiv (\E[\phi_{\al}x])_{\al\in \GGG}\,.\] For instance, in the planted dense subhypergraph model, we identify the set of all \(r\)-uniform hyperedges on \(n\) vertices with \([N]\), where \(N:=\binom{n}{r}\), and take \(\phi_\alpha(Y)=\prod_{e=1}^N(Y_e-q_0)^{\alpha_e}\) for \(\al=(\al_e)_{e\in [N]}\in \{0,1\}^N\). Note that this is the centered monomial basis under the “null distribution” where \(q_1=q_0\).

Step 2: Introduce an orthonormal family to control \(\E[f(Y)^2]\). The key difficulty in bounding \(\Corr_{\leq D}\) is the denominator \(\E[f(Y)^2]\). Since the entries of \(Y\) are not independent under the planted distribution, there is no obvious orthogonal basis in the space of low-degree polynomials of \(Y\) with respect to which one could expand \(\E[f(Y)^2]\) using Parseval’s identity.

The idea of [4] is to instead work in a larger space: introduce an orthonormal family \((\psi_{\beta\gamma}(W,\theta))_{(\beta,\gamma)\in \PPP}\) that depends on both the “noise” variable \(W\) and the signal \(\theta\), where \(W\) denotes the source of randomness in the observation (e.g., the independent edge variables in the hypergraph model, or the Gaussian noise tensor in tensor PCA). In our applications, since \(W\) and \(\theta\) are independent with independent entries, and it is straightforward to construct such \(\psi_{\beta\gamma}\) by taking the separable form \(\psi_{\beta\gamma}=\psi_{1,\beta}(W)\cdot \psi_{2,\gamma}(\theta)\).

Assuming \(Y\) is measurable with respect to \((W,\theta)\), the orthonormality condition \(\E[\psi_{\beta\gamma}\,\psi_{\beta'\gamma'}]=\In\{(\beta,\gamma)=(\beta',\gamma')\}\) allows one to lower-bound \(\E[f(Y)^2]\) via Bessel’s inequality \[\label{eq:Bessel} \begin{align} &\E[f(Y)^{2}] \geq \sum_{(\beta,\gamma) \in \PPP} \Big(\E\big[f(Y)\psi_{\beta\gamma}(W,\theta)\big]\Big)^{2} = \big\|M \hat{f}\big\|^{2}\,,\quad\textrm{where} \\ &M=(M_{\be\ga,\al})_{(\be,\ga)\in \PPP, \al\in \GGG}\equiv (\E[\phi_{\al}(Y)\psi_{\be\ga}(W,\theta)])_{(\be,\ga)\in \PPP, \al\in \GGG}\,. \end{align}\tag{3}\] Combining 3 with the Cauchy Schwarz inequality yields the following dual bound.

The power of Proposition [prop:duality] is that any \(u\) satisfying \(M^\top u =c\) may be viewed as a dual certificate for upper bounding \(\Corr_{\leq D}\). By having a rich enough family \((\psi_{\be\ga})\), we have freedom to construct \(u\). Such an approach is particularly effective for proving very accurate bounds on \(\Corr_{\leq D}\) leading to a sharp phase transition for many models, as seen in Theorem 3 and 5.

Step 3: Reduce to “good” graphs and construct \(u\). The final step is to find \(u\) satisfying \(M^\top u=c\) with small enough norm by eliminating “uninformative” terms. To illustrate, consider the planted dense subhypergraph model with \((\phi_{\al})_{\al\in \GGG}\) and \((\psi_{\be\ga})_{(\be,\ga)\in \PPP}\) constructed above. For any \(u\) such that \(M^\top u =c\) with small enough norm, we expect that the function \(\sum_{\be\ga}u_{\be\ga}\psi_{\be\ga}\) must be close to \(f_\star\), the projection of \(x=\theta_1\) onto \(\R_D[Y]\). Thus, intuitively, for \(\be\) which doesn’t contain vertex \(1\) or is not connected, the value \(u_{\be\ga}\) must be small. The following lemma guarantees that such terms can actually be set to \(0\) by exploiting linearity in the system \(M^\top u =c\).

For planted dense subhypergraphs, we will set \(\GGG_\star\) to be the all connected hypergraphs \(\al\) containing the vertex \(1\) (cf. Definition 5), and \(\PPP_\star\) to be all collection \((\be,\ga)\) such that \(\be\in \GGG_\star\) and \(\ga\) such that its support is included in vertices of \(\be\). Lemma 9 verifies the condition ?? holds.

Lemma 1 is a crucial step in the orthogonal expansion approach by [4] since in both the construction of \(u\) such that \(M^\top u =c\) and the bounding step of \(\|u\|\) it allows us to consider only a much smaller set \(\PPP_\star\). For example, in the planted dense subhypergraphs above, the size of \(|\PPP_\star|\) is at least \(n^{-1}\) factor smaller than \(|\PPP|\) due to the condition that vertex \(1\) must be included.

Finally, we remark that in applying this orthogonal expansion approach to the planted dense subhypergraph with \(\rho\geq n^{-1/2}\) and sparse tensor PCA, the \(r\geq 3\) case requires new combinatorial estimates when bounding \(\|u\|\). For \(r=2\), a connected graph always contains a spanning tree, which was one of the main facts in the \(r=2\) case [4]. However, the analog fails for \(r\geq 3\): a connected hypergraph need not contain a hypertree (cf. Definition 2). A spanning hypertree on \(k\) vertices exists only if \(k\equiv 1\pmod{r-1}\), and even this is not sufficient—whether one exists depends on how the edges overlap, not merely on the vertex and edge counts. To pin down the sharp threshold in Theorem 3, we therefore derive a sufficiently tight upper bound on the number of connected hypergraphs with a given number of vertices and hyperedges, which appears to be new.

3.2 Orthogonal expansion approach with conditioning↩︎

For the planted dense subhypergraph model with \(\rho \leq n^{-1/2}\) (i.e. \(\xi\leq 1/2\)), the orthogonal expansion approach in Section 3.1 is insufficient to establish hardness throughout \(a>b\xi\). The difficulty is that when \(a<b/2\), there exists rare configurations of \(Y\) that make \(c_{\alpha} \equiv \E[\phi_{\al}(Y)\theta_1]\) substantially greater than its typical value whenever the hypergraph \(\alpha\) is ‘dense’; that is, has many hyperedges relative to its number of vertices. This in turn inflates the norm of the dual certificate \(u\). A similar phenomenon was observed by Dhawan, Mao, and Wein [18] who considered detection of the planted dense subhypergraph; for this reason, they considered a conditioning approach to the low-degree likelihood ratio.

Similar to the approach of [18], we introduce a method for incorporating conditioning into the orthogonal expansion. Let \(\cE_{\star}\) be a ‘good’ event, chosen so that \(\cE_{\star}\) occurs with high probability, but rules out the rare configurations which cause inflating \(c_{\alpha}=\E[\phi_{\al}(Y)\theta_1]\) than the typical value of \(\phi_{\al}(Y)\theta_1\). For a polynomial estimator \(f \in \R_D[Y]\), we split the numerator in the low-degree correlation as \[|\E[f(Y) \cdot x]| \leq |\E[f(Y) \cdot x \In_{\cE_{\star}}]| + |\E[f(Y) \cdot x \In_{\cE_{\star}^{c}}]|\,.\] We control the two terms on the RHS separately. Roughly speaking, the first term is handled by applying the orthogonal expansion method restricted to the event \(\cE_{\star}\), and the second term is controlled using Cauchy Schwarz, leveraging the fact that \(\cE_{\star}\) occurs with high probability. Define \[\begin{align} &\widetilde{c} = (\widetilde{c}_{\alpha})_{\alpha \in \sG} \equiv (\E[\In_{\cE_{\star}}\phi_{\alpha}(Y)x])_{\alpha \in \sG}\,, \quad\textrm{and} \\ &\widetilde{M} = (\widetilde{M}_{\beta\gamma, \alpha})_{(\beta, \gamma)\in \sP, \alpha \in \sG} \equiv (\E[\In_{\cE_{\star}}\phi_{\alpha}(Y)\psi_{\beta \gamma}(W,\theta)])_{(\beta, \gamma) \in \sP, \alpha \in \sG}\,. \end{align}\]

Proposition [prop:orthogonal:expansion:conditioning] reduces the problem of establishing a lower bound to two tasks. First, one must determine an event \(\cE_{\star}\) for which \(\E[x^{2}\In_{\cE_{\star}^{c}}]=o(\E[x^2])\). Second, one needs to construct a solution to the conditioned linear system with small enough norm.

The main technical difficulty lies in the second task. Although conditioning on \(\cE_{\star}\) reduces \(\widetilde{c}_{\alpha}\) to its typical scale, it introduces dependencies between disconnected hypergraphs that were otherwise absent in the unconditioned analysis. Crucially, this breaks Step 3 in the orthogonal expansion. In particular, the reduction to good graphs (Lemma 1) no longer applies and we cannot simply set \(u_{\beta \gamma} = 0\) for uninformative pairs \((\beta, \gamma) \not \in \sP_{\star}\). Nevertheless, we prove that the conditioned system retains enough structure to admit a tractable analysis. The key property is that the independence of the entries \((\theta_{i})_{i\leq n}\) under the prior allows us to choose \((\psi_{\beta \gamma})_{(\be,\ga)\in \mathscr{P}}\) in such a way that we have for any fixed \(\al,\be\in \GGG\) (see Eq. ?? ) \[\sum_{\gamma: (\beta, \gamma) \in \sP} \left(-\sqrt{\frac{\rho}{1-\rho}}\right)^{|\ga|}\widetilde{M}_{\beta\gamma, \alpha} = 0 \qquad\textrm{unless \beta is a union of connected components of \al}\,. \label{eq:key:identity:ansatz}\tag{6}\] This identity suggests the dual certificate of the form \[u_{\beta \gamma} = \left(-\sqrt{\frac{\rho}{1-\rho}}\right)^{|\ga|} \cK(\beta)\] where \(\cK: \sG \to \R\) is determined by a recursion over hypergraphs. Substituting this form into \(\widetilde{M}^{\top}u=\widetilde{c}\) and applying the identity, the system reduces to a recursion in which \(\cK(\alpha)\) is determined by \(\widetilde{c}_{\alpha}\) together with the values \(\cK(\beta)\) over the proper unions of connected components \(\beta\) of \(\alpha\). Since each such \(\beta\) has fewer connected components than \(\alpha\), the recursion is well-defined and solves explicitly, and the resulting \(\cK(\alpha)\) inherits the scale of \(\widetilde{c}_{\alpha}\), up to a combinatorial factor counting the connected components of \(\alpha\).

Notations The symbols \(\R\), \(\N\) denote the set of all real numbers and non-negative integers, respectively. We include \(0 \in \N\) by convention. We let \([n]:=\{1,\ldots, n\}\) for \(n=1,2,\ldots\).

For an index set \(\Lambda\), and vectors \(x = (x_{i})_{i\in \Lambda}, y = (y_{i})_{i\in \Lambda}\in \R^{\Lambda}\), we write \(x \leq y\) if \(x_{i} \leq y_{i}\) for all \(i \in \Lambda\). We will identify subsets of \([n]\) with binary vectors of length \(n\) in the natural way. That is, if \(A \subseteq [n]\), then we identify it with the binary vector \(\gamma\) such that \(\gamma_{i} = 1\) whenever \(i \in A\) and \(\gamma_{i} = 0\) otherwise. Therefore, the relation \(\gamma \leq A\) means that \(\gamma_{i} = 1\) only when \(i \in A\). We use the subscript notation \(\gamma_{A}\) to denote the subvector of \(\gamma\) whose indices are in \(A\).

For a hyperedge \(e=(i_1,\ldots, i_r)\) of a hypergraph, let \(V(e)=\{i_1,\ldots, i_r\}\) denote the vertices that participate in the hyperedge \(e\). We will use the multi-index notation with superscripts where, for \(\theta \in \{0,1\}^n\) and \(\gamma \subseteq [n]\), we write \(\theta^{\gamma}=\prod_{i=1}^{n}\theta_i^{\gamma_i}\). For \(Y\in \R^{N}\) and \(\alpha \in \N^{N}\), we write \(Y^{\alpha}:=\prod_{e=1}^{N}Y_e^{\alpha_e}\). We denote \(\R_D[Y]\) as the set of all polynomials in the entries of \(Y\) with degree at most \(D\).

We identify the collection of all \(r\)-uniform simple hyperedges on \([n]\) with \(\binom{[n]}{r} = \{e \subseteq [n]: |e| = r\}\), and the collection of all \(r\)-uniform multi-hyperedges on \([n]\) with \(\mc=\{e=(i_1,\ldots i_r)\in [n]^{r}:i_1\leq i_2\leq \ldots \leq i_r\}\) (multi-choose notation). Note that \(\alpha \in \{0,1\}^{\binom{[n]}{r}}\) can be viewed as an \(r\)-uniform hypergraph on the vertices \([n]\) where the hypergraph includes the hyperedge \(e\in \binom{[n]}{r}\) if and only if \(\alpha_{e} = 1\). Similarly any \(\alpha \in \N^{\mc}\) can be viewed as an \(r\)-uniform multi-hypergraph on the vertices \([n]\) where the multigraph has \(\alpha_{e}\) copies of the hyperedge \(e\) for all \(e\in \mc\). We let \(V(\alpha) \subseteq [n]\) denote the set of non-isolated vertices of \(\alpha\). We let \(E(\al)\) denote the edge set of \(\al\), i.e. the multi-set of \((i_1,\ldots, i_r)\) with \(i_1\leq \ldots \leq i_r\) corresponding to the edges of the multi-hypergraph \(\al\).

For a parameter \(a\), we use the asymptotic notation \(O_{a}(\cdot)\) and \(o_{a}(\cdot)\), etc., to suppress constant multiplicative factors that depend only on \(a\). We use \(\widetilde{O}_{a}(\cdot)\) and \(\widetilde{o}_{a}(\cdot)\), etc., to suppress multiplicative constants as well as polylogarithmic factors.

Acknowledgments↩︎

We thank Alexander S. Wein for discussions that helped inspire the framework in Section 3.2.

Organization↩︎

The remainder of the paper is organized as follows. Section 4 proves the estimation lower bound for sparse tensor PCA (Theorem 5-(a)). Section 5 treats the planted dense subhypergraph model: the large planted set regime (Theorem 3-(a)) in Section 5.2, and the small planted set regime (Theorem 4-(a)) via the conditioning argument in Section 5.3. Section 6 proves the estimation lower bound for tensor PCA with a general prior (Theorem 6). Section 7 establishes the matching upper bounds (Theorems 5-(b), 3-(b), and 4-(b)). We defer analysis of the polynomial-time recovery algorithms to the appendix.

4 Sparse tensor PCA↩︎

This section is devoted to the proof of Theorem 5-(a). We will follow the orthogonal expansion approach outlined in Section 3.1. If \(\rho=0\) then \(\theta=0\) almost surely and the result is trivial, so we assume \(\rho > 0\) without loss of generality. We index the basis and the orthonormal family by \[\sG = \{\alpha \in \N^{\mc}: |\alpha| \leq D\}\,, \qquad \sP = \sG \times \{0, 1\}^{n}\,.\] That is, \(\sG\) consists of all \(r\)-uniform multi-hypergraphs (with no isolated vertices) having at most \(D\) edges, counting multiplicities.

Before proceeding to the proof, we make the following simplification. Observe that the entries of the symmetrized noise tensor \(\Wsy\) in Definition 1 with repeated indices have inflated variance relative to those entries having only distinct indices (see e.g. Proposition B.1 of the arXiv version of [6]). It is convenient to instead consider a noise-reduced symmetric tensor \(Z\) whose entries are i.i.d. \(\cN(0, 1)\) random variables, up to symmetry. That is, \(Z_{e} \stackrel{iid}{\sim} \cN(0, 1)\) for \(e \in \mc\). Accordingly, we shall work with the noise-reduced observation \[\Ynr = \lambda \theta^{\otimes r} + Z\,.\] Throughout, as we work exclusively with the noise-reduced model, we abuse notation and simply write \(Y \equiv \Ynr\). It is sufficient to prove a lower bound for this noise-reduced model, since the noise-inflated tensor can be simulated by adding independent Gaussian noise, which in turn can be simulated by a polynomial; see [7].

4.1 Construction of the dual certificate↩︎

We begin by specifying the basis \((\phi_\alpha)_{\alpha\in\sG}\) and the orthonormal family \((\psi_{\beta\gamma})_{(\beta,\gamma)\in\sP}\). Write \(N := \mc\) and let \(\{h_k\}_{k\in\N}\) denote the univariate Hermite polynomials, normalized so that \(\deg(h_k)=k\) and \(\E[h_k(G)\,h_\ell(G)]=\In_{k=\ell}\) for \(G\sim\cN(0,1)\) (see e.g. [84]). The corresponding multivariate Hermite polynomials are \(H_\alpha(y) = \prod_{e=1}^{N} h_{\alpha_e}(y_e)\), where \(y\in (\R^n)^{\otimes r}\) and \(\alpha \in \sG\). For \(\al,\be\in \GGG\) and \(\ga\in \{0,1\}^n\), we set \[\phi_{\alpha}(Y)= H_{\alpha}(Y)\,, \quad \psi_{\beta \gamma} = \psi_{\beta \gamma}(Z, \theta) = H_{\beta}(Z) \lPa \frac{\theta - \rho}{\sqrt{\rho(1 - \rho)}} \rPa^{\gamma}\,.\] Note that \((\phi_{\al})_{\al\in \GGG}\) forms a basis of \(\R_D[Y]\). Moreover, as \(Z\) and \(\theta\) are independent, and both the Hermite polynomials and the centered Bernoulli monomials are orthonormal in their respective \(L^2\) spaces, the family \((\psi_{\beta\gamma})\) is orthonormal.

As outlined in Step 3 in Section 3.1, we isolate the sets \(\GGG_\star\) and \(\PPP_\star\) in order to use Lemma 1. Recall that a multi-hypergraph is connected if every pair of vertices is connected by a path of hyperedges (see Definition 2).

Having Lemma 3 in hand, we construct the dual certificate \(u\) as \[u_{\beta \gamma} = \left(-\sqrt{\frac{\rho}{1 - \rho}} \right)^{|\gamma|}c_{\beta}\,,\quad \textrm{for}\quad (\be,\ga)\in \PPP_\star\,, \label{eq:sparse:PCA:solution}\tag{7}\] and set \(u_{\be\ga}=0\) if \((\be,\ga)\notin \PPP_\star\).

4.2 Counting connected hypergraphs↩︎

We next derive the necessary combinatorial estimates to bound \(\|u\|\). To motivate these estimates, since \(u\) in 7 satisfies \(M^{\top}u=c\) by Lemma 4, we have by Proposition [prop:duality] that \[\begin{align} \rho \cdot \Corr_{\leq D}^2\leq \|u\|^2 &=\left(c_{0}^{2} \sum_{\gamma \subseteq \{1\}} \lPa \frac{\rho}{1 - \rho} \rPa^{\gamma} + \sum_{\alpha \in \GGG_\star\setminus\{0\}} c_{\alpha}^{2} \sum_{\gamma \subseteq V(\alpha)} \lPa \frac{\rho}{1 - \rho} \rPa^{\gamma}\right)\\ &=\frac{\rho^2}{1-\rho}+\sum_{\al\in \GGG_\star\setminus\{0\}}\frac{\la^{2|\al|}\rho^{2|V(\al)|}}{\al!}\left(1+\frac{\rho}{1-\rho}\right)^{|V(\al)|}\,. \end{align}\] Let \(\hat{\rho} = \frac{\rho}{\sqrt{1-\rho}}\). Then, with the crude bound \(\al!\geq 1\), we have the following. Every good \(\alpha\in\sG_\star\setminus\{0\}\) is a connected multi-hypergraph on some \(k\geq r\) vertices (one of which is vertex \(1\)) with some \(\ell\geq 1\) edges. Summing over vertex count, edge count, and vertex labels, \[\label{eq:bound:corr:sparse:PCA} \rho \cdot \Corr^2_{\leq D}\leq \hat{\rho}^2\bigg(1+\sum_{\al\in \GGG_\star\setminus\{0\}}\hat{\rho}^{2|V(\alpha)| - 2} \lambda^{2|\alpha|}\bigg)\leq \hat{\rho}^2\bigg(1+\sum_{k = r}^{rD} \sum_{\ell = \ell_k}^{D} \binom{n - 1}{k - 1}N_{k, \ell}^{\mathrm{mult}} \hat{\rho}^{2k - 2} \lambda^{2\ell}\bigg)\,,\tag{8}\] where \[\ell_k = \lceil(k-1)/(r-1)\rceil\] is the minimum number of edges in a connected \(r\)-uniform hypergraph on \(k\) vertices, and \(N_{k,\ell}^{\mathrm{mult}}\) denotes the number of connected \(r\)-uniform multi-hypergraphs on \([k]\) with \(\ell\) edges, allowing self-loops.

To bound the sum in 8 below the sharp threshold, we need sufficiently tight estimates on \(N_{k,\ell}^{\mathrm{mult}}\) as a function of \(k\) and \(\ell\). The strategy is to compare multi-hypergraph counts first to simple hypergraph counts, and then to the number of hypertrees (see Definition 2). Recall that a hypertree is any connected and acyclic \(r\)-uniform hypergraph having the property that any two of its edges share at-most a single vertex in common.

We will need a count of labeled hyperforests—disjoint unions of hypertrees—in which each tree has a distinguished vertex designated as its root. An \(r\)-uniform hyperforest on \([k]\) with \(t\) connected components (each a hypertree) has \(\ell = (k-t)/(r-1)\) edges.

We next compare \(N_{k,\ell}^{\mathrm{mult}}\) to \(N_{k,\ell}\), and then \(N_{k,\ell}\) to \(N_k\), which we treat as the baseline.

4.3 Proof of Theorem 5-(a)↩︎

5 Planted dense subhypergraph↩︎

This section is devoted to the proof of Theorem 3-(a) for \(\rho \geq n^{-1/2}\) and Theorem 4-(a) for \(\rho \leq n^{-1/2}\). Theorem 2 is a restatement of Theorem 4 in terms of \(\MMSE\) (cf.Fact [fact:corr:mmse]). Theorem 1 in turn follows from Theorem 3: for the lower bound it suffices to take \(\SNR = 1-\eps\), raising \(q_1\) if necessary, since \(\MMSE_{\leq D}\) is monotonically decreasing in \(q_1\) (see [7]). Setting \(\SNR = 1-\eps\) corresponds to \(\la^2 = C(\eps,r)/(n^{r-1}\rho^{2r-2})\), so that the degree condition \(D^{r-1} \leq 1/(C\la^2)\) in Theorem 3-(a) becomes \(D \lesssim n\rho^2 = n^{2\xi-1}\), which is the degree range in Theorem 1.

5.1 Setup and notation↩︎

We introduce some notation specific to the planted subhypergraph model. Let \[S = \{i\in[n]:\theta_i=1\} \qquad \textrm{and} \qquad K_S = \{e\in[N]:\theta_i=1\;\forall\,i\in V(e)\}\] denote the planted vertex set and the complete \(r\)-uniform hypergraph on \(S\), respectively. We write \(K_S^c = [N]\setminus K_S\) for its complement. The planted hypergraph \(X\) is the random subhypergraph of \(Y\) induced by the planted vertices, i.e., \(V(X)=S\) and \(E(X)=\{e\in K_S:Y_e=1\}\). We use \(\E\nolimits_\theta[\cdot]\) to denote expectation conditional on \(\theta\).

The index sets for the basis and orthonormal family are \[\sG \;=\; \{\alpha\in\{0,1\}^{N}:|\alpha|\leq D\}\,, \qquad \sP \;=\; \{(\beta,\gamma)\in\sG\times\{0,1\}^n:\gamma\subseteq V(\beta)\cup\{1\}\}.\] Note that \(\sG\) now consists only of simple hypergraphs with at most \(D\) edges and \(\sP\) has the extra constraint that \(\gamma\subseteq V(\be)\cup\{1\}\), in contrast to the multi-hypergraphs used in Section 4.

5.2 Large planted dense subhypergraph↩︎

This section is devoted to the proof of Theorem 3-(a). As in the sparse tensor PCA model, we follow the orthogonal expansion approach of Section 3.1. Define the polynomials in \(Y\) \[\phi_{\alpha} = \phi_{\alpha}(Y) = (Y - q_{0})^{\alpha}\,.\] Note that \((\phi_{\al})_{\al\in \GGG}\) forms a basis of \(\R_D[Y]\). For \((\be,\ga)\in \PPP\), define the polynomials in \((Y,\theta)\) \[\psi_{\beta \gamma} = \psi_{\beta \gamma}(Y, \theta) = \lPa \frac{\theta - \rho}{\sqrt{\rho(1 - \rho)}} \rPa^{\gamma} \prod_{e \in K_{S}} \lPa \frac{Y_{e} - q_{1}}{\sqrt{q_{1}(1 - q_{1})}} \rPa^{\beta_{e}} \prod_{e \not \in K_{S}} \lPa \frac{Y_{e} - q_{0}}{\sqrt{q_{0}(1 - q_{0})}} \rPa^{\beta_{e}}\,.\] Using the conditional independence of the entries of \(Y\) given \(\theta\), it is straightforward to see that \((\psi_{\beta\gamma})_{(\beta,\gamma)\in \PPP}\) forms an orthonormal family (see e.g. [4]).

The notion of good graph carries over from the sparse tensor PCA model (Definition 4), with the only change being that \(\sG\) now consists of simple hypergraphs rather than multi-hypergraphs. We restate the definition for convenience.

By Lemmas 1 and 9, it suffices to find \(u\) supported on \(\sP_\star\) solving \(M^{\top}u=c\). The proposed dual certificate is \[\label{eq:hypergraph:solution} u_{\beta \gamma} = (-1)^{|\gamma|} \lPa \frac{\rho}{1 - \rho} \rPa^{\frac{1}{2}|\gamma|}(q_{0}(1 - q_{0}))^{-\frac{1}{2}|\beta|}c_{\beta}\,.\tag{10}\] This dual certificate has the same structure as in the sparse PCA model; see 7 .

5.3 Small planted dense hypergraph↩︎

In this section, we prove Theorem 4-(a). In particular, we fix \(\xi\in (0,1/2]\) and \(0<a<b\), and set \[\rho = n^{\xi - 1}\,\,, \quad q_{0} = n^{-b}\,\,, \quad q_{1} = n^{-a}\,.\] Note that by Theorem 3-(a) established in the previous section, there exists \(C=C_r>0\) such that if \(n^{r-1}\rho^{2r-2}\frac{(q_1-q_0)^2}{q_0(1-q_0)}\leq 1/C_r\) and \(D^{r-1}\frac{(q_1-q_0)^2}{q_0(1-q_0)}\leq 1/C_r\), then \(\Corr_{\leq D}\leq Cn^{-\frac{\xi}{2}}\). It follows that if \(2a-b>0\), then there exists \(\delta=\delta(a,b)\) such that \(\Corr_{\leq D}\lesssim n^{-\frac{\xi}{2}}\). Thus, throughout this section, we focus on the other regime, where \[\label{eq:assume:small:PDS} b \geq 2a \qquad \text{and} \qquad a>b\xi\,.\tag{12}\]

5.3.1 High probability event↩︎

We fix a constant \(\delta=\delta(r,a,b,\xi) \in (0, 1)\) whose value will be determined later in Eq. 28 below. We recall the notion of ‘dense’ graph, which appeared in [18] for proving detection hardness.

Recall that \(X\) denotes the planted hypergraph. Consider the event, \[\cE \equiv \cE_D = \{\text{every subgraph of X with at most D edges is sparse.}\}\] The next lemma, an estimation analog of [18], shows that the event \(\cE\) holds with high probability, even after fixing a small subset of \(\theta\). For a subset \(A \subseteq [n]\), recall \(\theta_A\equiv (\theta_{i})_{i \in A}\).

For the rest of this section, we assume \(D\leq n^{\eps}\) for \(\eps>0\) appearing in Lemma 10. We further assume \(\eps < \xi\) so that \(|V(\alpha) \cup \{1\}| \leq rn^{\eps}+1 \leq n^{\xi}\) for \(\al \in \sG\) and \(n\) sufficiently large. In particular, Lemma 10 implies that \[\label{eq:event:probability:below:by:1:2} \min_{\substack{\alpha \in \sG \\ \sigma \in \{0, 1\}^{V(\al)\cup\{1\}}}} \P(\cE \mid \theta_{V(\al)\cup\{1\}} = \sigma)\geq \frac{1}{2}\,.\tag{13}\]

5.3.2 Linear system with conditioning↩︎

We now implement the orthogonal expansion approach with conditioning \(\cE\) described in Section 3.2. The index sets \(\sG\) and \(\sP\), the basis \((\phi_\alpha)_{\alpha\in\sG}\), and the orthonormal family \((\psi_{\beta\gamma})_{(\beta,\gamma)\in\sP}\) remain as defined in Section 5. By Proposition [prop:orthogonal:expansion:conditioning], it suffices to determine a solution \(u\) to the modified system \(\widetilde{M}^\top u = \widetilde{c}\), where \[\wc_{\alpha} = \E[\phi_{\alpha} \theta_1 \In_{\cE}]\,, \qquad \wM_{\beta \gamma, \alpha} = \E[\phi_{\alpha} \psi_{\beta \gamma} \In_{\cE}]\,,\] with \(\|u\|\) sufficiently small. The conditioning controls the contribution from dense subgraphs, but introduces a complication: disconnected components of \(Y\) may no longer be independent conditional on the event \(\cE\), so the reduction to good graphs (Lemma 9) no longer applies. The key challenge is to show that the coefficients \(u_{\beta\gamma}\) for disconnected \(\beta\) are sufficiently small, decaying fast enough in the number of connected components of \(\be\).

5.3.2.1 Candidate dual certificate

In the unconditional setting of Section 5, the dual certificate was constructed so that the summation over \(\gamma\) vanishes for all proper good subgraphs \(\beta\lneq\alpha\), via the identity 11 . That cancellation relied on \(\alpha\) being good (connected, containing vertex \(1\)). The reduction to good graphs is no longer available in this conditioned setting. The identity 11 nonetheless remains useful: it shows that the summation over \(\gamma\) localizes to the set \(\sC_\alpha\) of unions of connected components of \(\alpha\), enabling a recursive construction of a candidate dual certificate.

Having Lemma 11 in hand, we search for a dual certificate \(u\) of the form, \[u_{\beta \gamma} = \lPa -\sqrt{\frac{\rho}{1 - \rho}} \rPa^{|\gamma|}(q_{0}(1 - q_{0}))^{-|\be|/2} \cF(\beta)\,. \label{eq:small:hypergraph:ansatz}\tag{18}\] for a function \(\cF: \sG \rightarrow \R\) to be determined. Substituting 18 into the modified system \(\widetilde{M}^\top u = \widetilde{c}\) and applying Lemma 11 gives the following corollary.

The squared norm of the dual certificate \(u\) given in Corollary 2 is \[\|u\|^{2} = \sum_{\alpha \in \sG} \frac{\cF(\alpha)^{2}}{(q_{0}(1 - q_{0}))^{|\alpha|}} \sum_{\gamma \subseteq V(\alpha) \cup \{1\}} \lPa \frac{\rho}{1 - \rho} \rPa^{|\gamma|} = \sum_{\alpha \in \sG} \frac{\cF(\alpha)^{2}}{(q_{0}(1 - q_{0}))^{|\alpha|}(1 - \rho)^{|V(\alpha) \cup \{1\}|}} =: \sum_{\alpha \in \sG} \cK(\alpha)\,,\] where the second equality uses the identity \(\sum_{\gamma\subseteq A}(\rho/(1-\rho))^{|\gamma|}=(1-\rho)^{-|A|}\). We separate the last summation on the RHS as \[\label{eq:bound:u:in:terms:of:Xi} \|u\|^2=\sum_{\text{\alpha is sparse}} \cK(\al) + \sum_{\text{\alpha is dense}} \cK(\al)=:\Xi_{\textsf{sparse}}+\Xi_{\textsf{dense}}\,.\tag{19}\] where \(\Xi_{\mathsf{sparse}}\) and \(\Xi_{\mathsf{dense}}\) denote the contribution from sparse and dense \(\al\), respectively.

To bound \(\|u\|^2\), we require pointwise estimates on \(|\cF(\alpha)|\). The appropriate bound depends on whether \(\alpha\) is sparse or dense (see Definition 6). We introduce two reference quantities: \[\label{eq:def:s:d} s_{\alpha} := \rho^{|V(\alpha)|}(2q_{1})^{|\alpha|}\,,\qquad d_{\alpha} := \rho^{|V(\alpha)|}D^{m_{\alpha}}q_{0}^{|\alpha|} \lPa \frac{2q_{1}}{q_{0}} \rPa^{m_{\alpha}}\,.\tag{20}\] We will show that, up to an additional complexity factor, \(\cF(\alpha)\) is comparable to \(s_{\alpha}\) when \(\alpha\) is sparse and \(\cF(\alpha)\) is comparable to \(d_{\alpha}\) when \(\alpha\) is dense. An observation that we will repeatedly use is \[\label{eq:observation:alpha:sparse} \textrm{\al is sparse}\implies s_{\al}\le d_{\al}\,.\tag{21}\] Another crucial observation is that if \(\al\) is dense with \(|\al| \gg m_{\al}\), then \(d_{\al} \ll s_{\al}\) for \(D \leq n^{\eps}\) and small enough \(\eps\). The improvement from \(s_{\al}\) to \(d_{\al}\) comes from conditioning on \(\cE\), which ensures that at most \(m_\alpha\) edges of \(\alpha\) lie inside the planted hypergraph \(X\); the remaining \(|\alpha|-m_\alpha\) edges lie outside \(X\) and contribute \(q_0\) each, giving the scale \(d_\alpha\). We begin by bounding \(\widetilde{c}_\alpha\) and \(H_{\beta \alpha}\) in terms of \(s_\alpha\) and \(d_{\alpha}\), depending on whether or not \(\alpha\) is dense. Afterwards, we use the recursion ?? to bound \(\cF(\alpha)\). We remark that when \(1\notin V(\al)\), the extra factor of \(\rho\) in the bound of \(|\wc_{\al}|\) in the next lemma plays an important role for showing that graphs not containing vertex \(1\) contribute negligibly to \(\|u\|^2\).

We next bound \(\mathcal{F}(\al)\) by the complexity function \(\cH: \sG \rightarrow \R_{\geq 0}\) defined recursively as \[\cH(\alpha) = 2 + 2\sum_{\beta \in \sC_{\alpha} \setminus \{\alpha\}} \cH(\beta)\,,\qquad \cH(\al)=2~~\textrm{if \al is connected.}\]

5.3.3 Bounding the norm \(\|u\|\)↩︎

Recall that \(\|u\|^2\leq \Xi_{\mathsf{sparse}}+\Xi_{\mathsf{dense}}\) from 19 . To finish the proof of Theorem 4-(a), we bound \(\Xi_{\mathsf{sparse}}\) and \(\Xi_{\mathsf{dense}}\) separately.

6 Tensor PCA with a general prior↩︎

In this section we prove Theorem 6. Throughout, we fix a prior distribution \(\pi\) satisfying \(\E[\pi]=0\), \(\E[\pi^2]=1\), and \(\E[|\pi|^t]\leq (K_0t)^{\nu t}\) for all \(t\geq 1\), where \(K_0>0\) and \(\nu\geq 0\) are constants depending only on \(\pi\). The estimand is \(x = \prod_{i=1}^m\theta_i\) for a fixed integer \(m\geq 2\). As noted in the case of sparse tensor PCA model, for technical convenience, we shall work with the symmetrized tensor \(Y\equiv\Ysy\) and prove statements for the symmetric model. All of our results transfer to the non-symmetric model; see Lemma 27 for the correspondence.

However, unlike the sparse tensor PCA and planted dense subhypergraph models, where the orthogonal expansion approach is used, here the cumulant expansion by Schramm and Wein [7] suffices. This approach bounds the low-degree correlation directly in terms of joint cumulants of the signal and observation (this can be viewed as a special case of the orthogonal expansion approach; see Remark [rem:cumulant]): \[\label{eq:correlation:cumulant:bound} \Corr_{\leq D}^2 \leq \sum_{|\alpha|\leq D}\frac{\kappa_\alpha^2}{\alpha!}\,,\tag{29}\] where the sum ranges over all multi-hypergraphs \(\alpha\in\N^{\mc}\) with at most \(D\) edges and \(\kappa_\alpha\) is the joint cumulant \[\label{eq:cumulant:def} \kappa_\alpha = \E[x\,X^\alpha] - \sum_{0\leq\beta\lneq\alpha}\binom{\alpha}{\beta}\E[X^{\alpha-\beta}]\,\kappa_\beta\,.\tag{30}\]

6.1 Reduction to good graphs↩︎

For \(\al\in \N^{\mc}\), define \[\bar{\alpha} := \alpha + \In_{[m]}\] as the graph obtained by adding the \(m\)-hyperedge \(\{1, \ldots, m\}\) to \(\alpha\). Note that, unlike \(\al\), \(\bar{\al}\) is not \(r\)-uniform unless \(m=r\).

6.2 Bounding the cumulants↩︎

We introduce three quantities necessary to bound \(|\kappa_\alpha|\) for good graphs. For \(\al\in \N^{\mc}\), define the number of excess edges \[\delta(\alpha) = \sum_{\substack{i \in V(\alpha) \\ \deg_{\alpha}(i) \geq 3}} \deg_{\alpha} (i)\,,\] and define the complexity function \(\HH(\al)\) via the recursion \[\label{eq:def:H} \HH(\alpha) = \sum_{\substack{\beta \lneq \alpha \\ \text{\beta is good}}} \binom{\alpha}{\beta} \cH(\beta)\,,\qquad \cH(0)=1\,.\tag{31}\] Finally, for an integer \(t\geq 1\), define \[M(t) = \max_{0 \leq s \leq t} \E[|\pi|^{s}]\,.\] Observe that \(M(\cdot)\) satisfies the sub-multiplicative property \(M(s)M(t) \leq M(s + t)\) by Hölder’s inequality. Furthermore, the moment condition on the prior \(\pi\) implies that \(M(t) \leq (Kt)^{\nu t}\) for some constant \(K > 0\). The following lemma is a generalization of \(r=2\) case in [4].

The proof of Proposition [prop:general:PCA:bound:H] parallels the \(r=2\) case established in [4]. The main new ingredient for \(r\geq 3\) is the following lemma, which controls how the quantity \(r|\al|-2|V(\al)|+m\) decreases when an edge is removed.

6.3 Proof of Theorem 6↩︎

7 Estimation upper bounds↩︎

7.1 Sparse tensor PCA↩︎

This section is devoted to the proof of Theorem 5-(b). As in the lower bound, we work with a noise-reduced symmetric tensor \(Z=(Z_e)\) whose entries are independent, up to symmetry, with distribution \(Z_e \sim \cN(0, 1)\) for \(e \in \mc\). Our estimator depends only on entries with distinct indices, and thus any results proved for this estimator under the noise-reduced model transfer directly to the noise-inflated model.

7.1.1 Constructing the estimator↩︎

Our candidate estimator is based on a weighted sum of the number of trees of a prescribed size and structure. Throughout, we assume \[\label{eq:thm:PCA:b:assumptions} \frac{en^{r - 1} \rho^{2r - 2} \lambda^{2}}{(r - 2)!} \geq 1 + \eps, \quad \rho = \omega(n^{-1} \log^{6 + 3/(r-1)}{n}), \quad \rho = o(\log^{-6(r-1) - 3}{n})\tag{37}\] and fix this \(\eps>0\) throughout this section. We also let \[\label{eq:choice:k:ell} \ell = \left\lceil \frac{4}{\eps}\log(1/\rho)\right\rceil\,,\qquad k= (r-1)\ell+1\,,\tag{38}\] and let \(\sT \equiv \sT_{\ell}\) (see Definition 3). Recall that any \(\alpha \in \sT\) is a tree, rooted at vertex \(1\), consisting of two disjoint rooted trees whose roots are attached to the distinguished vertex \(1\) by two root-incident edges. Note that every such \(\alpha\) has exactly \(2\ell + 2\) edges and \((r-1)(2\ell+2)+1=2k + 2r - 3\) vertices.

Write \(C \equiv C(r,\eps)\) to denote a constant depending only on \(r\) and \(\eps\) which may vary from line to line. We prove Theorem 5-(b) by showing that the polynomial \(f\) defined by \[f(Y) = \sum_{\alpha \in \sT} Y^{\alpha}\] achieves \(1-o(1)\) correlation. As a first step, compute \(\E[Y^{\al}x]\) by first integrating out the independent Gaussian noise: \[\E[Y^{\alpha}x] = \E[(X + Z)^{\alpha} \theta_{1}] = \E[X^{\alpha} \theta_{1}] = \lambda^{|\alpha|} \E \lBr \theta_{1} \prod_{i \in V(\alpha)} \theta_{i}^{\deg_{i}} \rBr = \lambda^{|\alpha|} \prod_{i \in V(\alpha)} \E[\theta_{i}] = \lambda^{|\alpha|} \rho^{|V(\alpha)|}\,,\] where we used that the entries of \(\theta\) take values in \(\{0, 1\}\). Thus, \[\E[xf(Y)] = \sum_{\alpha \in \sT} \E[Y^{\alpha}x] = |\sT| \rho^{2k + 2r - 3} \lambda^{2\ell + 2}\,. \label{eq:sparse:PCA:upper:bound:numerator}\tag{39}\] It remains to show the second moment is of comparable order to 39 . Expand into three cases: \[\E[f(Y)^{2}] = \sum_{\alpha \in \sT} \E[Y^{2\alpha}] + \sum_{\substack{\alpha, \beta \in \sT \\ \alpha \cap \beta = 0}} \E[Y^{\alpha + \beta}] + \sum_{\substack{\alpha, \beta \in \sT \\ \alpha \cap \beta \neq 0, \alpha \neq \beta}} \E[Y^{\alpha + \beta}]\,. \label{eq:sparse:PCA:upper:bound:second:moment}\tag{40}\] We prove Theorem 5-(b) by showing that this second is asymptotic to \(\Gamma\), where \[\label{eq:def:Gamma} \Gamma := \frac{\E[xf(Y)]^{2}}{\E[x^{2}]} = |\sT|^{2} \rho^{4k + 4r - 7} \lambda^{4\ell + 4}\,.\tag{41}\] Towards this end, we first estimate the size of the set \(\sT\). To form a tree \(\alpha \in \sT\), we can first choose two disjoint vertex sets of size \(k\) from \(\{2,\ldots,n\}\) and form a rooted tree on each. The number of ways to do this is exactly (see Lemma 5) \[\binom{n - 1}{k} \binom{n - k - 1}{k}R_{k, 1}^{2} = \frac{R_{k, 1}^{2}}{k!^{2}} \frac{(n - 1)!}{(n - 2k - 1)!}\,.\] Next, the \(2(r-2)\) non-root leaf vertices in the two root-incident edges are chosen, giving \[\frac{1}{2}\binom{n - 1 - 2k}{r - 2} \binom{n - 2k - r + 1}{r - 2} = \frac{1}{2(r - 2)!^{2}} \frac{(n - 2k - 1)!}{(n - 2k - 2r + 3)!}\] possibilities. Combining these two counts, we obtain \(|\sT| = \frac{1}{2(r - 2)!^{2}} \frac{(n - 1)!}{(n - 2k - 2r + 3)!} \lPa \frac{R_{k, 1}}{k!} \rPa^{2}\). From the assumptions 37 , we have \(\rho = \widetilde{\omega}(1/n)\) which implies \(k=O_\eps(\log{n})\) and consequently \(\frac{(n - 1)!}{(n - 2k - 2r + 3)!}=(1-o(1))n^{2k + 2r - 4}\). With \(2k + 2r - 4 = (r - 1)(2\ell + 2)\), the preceding gives the asymptotic formula \[|\sT| = (1 - o(1)) \frac{n^{(r - 1)(2\ell + 2)}}{2(r - 2)!^{2}} \lPa \frac{R_{k, 1}}{k!} \rPa^{2}\,. \label{eq:asymptotic:tree:counting}\tag{42}\] To bound the second moment, we show that \[\sum_{\substack{\alpha, \beta \in \sT \\ \alpha \cap \beta = 0}} \E[Y^{\alpha + \beta}] = (1+o(1)) \Gamma\,. \label{eq:sparse:PCA:disjoint:trees}\tag{43}\] For any \(\alpha, \beta \in \sT\) with \(\alpha \cap \beta = \emptyset\) and \(v = |V(\alpha) \cap V(\beta) \setminus \{1\}|\) shared non-root vertices, \[\E[Y^{\alpha + \beta}] = \E[Y^{\alpha \triangle \beta}] = \lambda^{|\alpha \triangle \beta|} \rho^{|V(\alpha \triangle \beta)|} = \lambda^{4\ell + 4} \rho^{4k + 4r - v - 7}\,.\] To count the total number of such pairs, we may first choose a set of \(v\) shared vertices; then choose two disjoint vertex sets from the remaining vertices of \(\alpha\) and \(\beta\) are drawn. The number of choices is at most, \[\begin{align} \binom{n - 1}{v} \binom{n - 1 - v}{2k + 2r - 4 - v} \binom{n - 2k - 2r + 3}{2k + 2r - 4 - v} &= \frac{1}{v!(2k + 2r - 4 - v)!^{2}} \frac{(n - 1)!}{(n - 4k - 4r + 7 + v)!} \\ & \leq \frac{n^{(r - 1)(4\ell + 4) - v}}{v!(2k + 2r - 4 - v)!^{2}}\,. \end{align}\] Once the vertex sets have been selected, we partition the vertices into two disjoint subsets, each of size \(k+r-2\), corresponding to its two rooted subtrees together with its root-incident edge. Within each subset, we choose \(r-2\) leaf vertices to be incident to the root, and form a tree on the remaining \(k\) vertices. The number of ways to do this is \[\lPa \frac{1}{2} \binom{2k + 2r - 4}{k + r - 2} \binom{k + r - 2}{k}^{2}R_{k, 1}^{2} \rPa^{2} = \lPa \frac{(2k + 2r - 4)!}{2(r - 2)!^{2}} \lPa \frac{R_{k, 1}}{k!} \rPa^{2} \rPa^{2}\,.\] Combining this count with the calculation for \(\E[Y^{\alpha + \beta}]\) gives \[\begin{align} \sum_{\substack{\alpha, \beta \in \sT \\ \alpha \cap \beta = 0}} \E[Y^{\alpha + \beta}] & \leq \sum_{v \geq 0} \frac{\lambda^{4\ell + 4} \rho^{4k + 4r - v - 7}n^{(r - 1)(4\ell + 4) - v}}{v!(2k + 2r - 4 - v)!^{2}} \lPa \frac{(2k + 2r - 4)!}{2(r - 2)!^{2}} \lPa \frac{R_{k, 1}}{k!} \rPa^{2} \rPa^{2} \\ &= \lambda^{4\ell + 4} \rho^{4k + 4r - 7} \lPa \frac{n^{(r - 1)(2\ell + 2)}}{2(r - 2)!^{2}} \lPa \frac{R_{k, 1}}{k!} \rPa^{2} \rPa^{2} \sum_{v \geq 0} \frac{(n \rho)^{-v}}{v!} \lPa \frac{(2k + 2r - 4)!}{(2k + 2r - 4 - v)!} \rPa^{2}\,. \end{align}\] The prefactor outside the summation is \((1+o(1)) \Gamma\). Using \(\frac{(2k + 2r - 4)!}{(2k + 2r - 4 - v)!} \leq (2k + 2r - 4)^{v} \leq (Ck)^{v}\), the last summation on the RHS is bounded by, \[\sum_{v \geq 0} \frac{1}{v!} \lPa \frac{Ck^{2}}{n \rho} \rPa^{v} \leq \exp \lPa \frac{Ck^{2}}{n\rho} \rPa = 1 + o(1)\,,\] where the last step uses \(k^{2} = o(n\rho)\) when \(\rho = \omega(n^{-1} \log^{6+3/(r-1)}{n})\). The preceding implies 43 , as claimed. Next we show that, \[\sum_{\alpha \in \sT} \E[Y^{2\alpha}] = o(\Gamma)\,. \label{eq:sparse:PCA:identical:copies}\tag{44}\] For the purpose of reusing calculations for the planted dense subhypergraph model, define \[\label{eq:def:eta:zeta} \eta := \lambda^{2}\,,\qquad \zeta := \rho^{r-1}\eta\,.\tag{45}\] We will require an estimate on the second moment of a single tree:

Using Lemma 5 and Stirling’s approximation \(\ell! \leq e\sqrt{2\pi \ell}(\ell/e)^{\ell}\), we have the lower bound \[\frac{R_{k, 1}}{k!} = \frac{k^{\ell - 1}}{\ell!(r - 1)!^{\ell}} \geq \frac{C}{k\sqrt{\ell}} \lPa \frac{e}{(r - 2)!} \rPa^{\ell} \lPa \frac{k}{(r - 1)\ell} \rPa^{\ell} \geq \frac{C}{\ell^{\frac{3}{2}}} \lPa \frac{e}{(r - 2)!} \rPa^{\ell - 1}\,,\] where the last step used the bound \(\frac{k}{(r - 1)\ell} \geq 1\). Combining with the asymptotic formula 42 gives \[|\sT| \geq C\ell^{-3} \lPa \frac{en^{r - 1}}{(r - 2)!} \rPa^{2\ell + 2}\,. \label{eq:asymptotic:tree:lower:bound}\tag{46}\] With this estimate in hand, Lemma 21 then implies \[\frac{1}{\Gamma} \sum_{\alpha \in \sT} \E[Y^{2\alpha}] \leq \frac{1}{\Gamma} \sum_{\alpha \in \sT} (1 + \zeta)^{|\alpha|} = \frac{(1 + \zeta)^{2\ell + 2}}{|\sT| \rho^{4k + 4r - 7} \lambda^{4\ell + 4}} \leq C\rho^{-1} \ell^{3} \lPa \frac{(1 + \zeta)(r - 2)!}{en^{r - 1} \rho^{2r - 2} \lambda^{2}} \rPa^{2\ell + 2}\,.\] To bound the last quantity on the RHS, we shall assume that \[\lambda = \sqrt{\frac{(r - 2)!(1 + \eps)}{en^{r-1}\rho^{2r-2}}}\,. \label{eq:sparse:PCA:upper:bound:assumption}\tag{47}\] This condition on \(\lambda\) can be assumed without loss of generality, because increasing \(\lambda\) only makes estimation easier (see e.g. [7]). Note that the assumption \(\rho = \widetilde{\omega}(1/n)\) guarantees that \(\zeta = \rho^{r - 1} \lambda^{2} = \lPa \frac{C}{n\rho} \rPa^{r-1}=o(1)\). The assumption \(\frac{en^{r - 1} \rho^{2r - 2} \lambda^{2}}{(r - 2)!} \geq 1 + \eps\) then gives \[\rho^{-1} \ell^{3} \lPa \frac{(1 + \zeta)(r - 2)!}{en^{r - 1} \rho^{2r - 2} \lambda^{2}} \rPa^{2\ell + 2} \leq \rho^{-1}\ell^3 \lPa \frac{1+o(1)}{1+\eps} \rPa^{2\ell+2} \leq \rho^{-1} \ell^{3}(1-\eps/4)^{2\ell + 2} \leq \ell^3\rho\,,\] where the last inequality holds by our choice \(\ell=\lceil \frac{4}{\eps} \log(1/\rho)\rceil\). The assumption \(\rho=o(\log^{-6(r - 1) - 3}{n})\) ensures that the RHS of the above display is \(o(1)\), thus proving 44 . Lastly, we show that \[\sum_{\substack{\alpha, \beta \in \sT \\ \alpha \cap \beta \neq 0, \alpha \neq \beta}} \E[Y^{\alpha + \beta}] = o(\Gamma)\,. \label{eq:sparse:PCA:overlapping:trees}\tag{48}\] Bounding this final case is the most technical step of the upper bound. We shall require some additional notation. Given a pair of trees \(\alpha, \beta \in \sT\), the core is the forest \(\gamma = \alpha \cap \beta \cup \{1\}\), where we treat \(\{1\}\) as a connected component of the core even when it is an isolated vertex. Note that since \(\al, \be\) are trees, \(\al\cap\be\) is a forest. If \(\alpha\) and \(\beta\) share a root incident edge, then \(\alpha \cap \beta\) contains vertex \(1\), in which case \(\gamma=\al\cap \be\). If not, then \(\ga\) is the union of \(\al\cap \be\) with isolated vertex \(1\). Fix a pair of trees \(\alpha, \beta \in \sT\) for now. Let

• \(t\) be the number of connected components of the core \(\gamma\) and the components be \(\pi_{1}, \ldots, \pi_{t}\).

• \(a := |\alpha \cap \beta|\) be the total number of edges in the core.

• \(w := |(V(\alpha) \cap V(\beta)) \setminus V(\gamma)|\) be the number of shared vertices not contained in the core.

• \(B_{j} := V(\pi_{j}) \cap V(\alpha \triangle \beta)\) be the vertices where \(\pi_j\) intersects \(\alpha \triangle \beta\), with \(b_{j} = |B_{j}|\). The vertices in \(B := \cup_{j = 1}^{t} B_{j}=V(\al\triangle \be)\cap V(\ga)\) are called branch points. Put \(b = |B|\).

We remark that these quantities are precisely the parameters used in [4] to prove an estimation upper bound for the planted submatrix model.

The next step is to estimate the number of pairs \(\alpha, \beta \in \sT\) giving rise to a realizable tuple of parameters.

Lastly, we require the following structural lemma on trees in \(\sT\), which will allow us to boost the estimate from this case from \(O(\Gamma)\) to \(o(\Gamma)\). Note that, up to this point, it was not necessary to use the special structure of the trees at all.

We are now ready to prove 48 . From Lemmas 22 and 23, the LHS of 48 is at most \[\sum_{a, t, b, w} \rho^{4k + 4r - 6 - 2a(r - 1) - t - w} \lambda^{4\ell + 4 - 2a}(1 + \zeta)^{a} \lPa \frac{\rho + \zeta}{1 + \zeta} \rPa^{\frac{b - t}{r - 1}}C^{t + b + w} \ell^{3b + 2w}n^{1 - t - w} \lPa \frac{en^{r - 1}}{(r - 2)!} \rPa^{4\ell + 4 - a}\,.\] Rearranging and grouping terms together, the above summation is equal to \[\rho^{4k + 4r - 7} \lambda^{4\ell + 4} \lPa \frac{en^{r - 1}}{(r - 2)!} \rPa^{4\ell + 4} \sum_{\substack{a, t \geq 1 \\ b \geq t}} \lPa \frac{en^{r - 1} \rho^{2r - 2} \lambda^{2}}{(1 + \zeta)(r - 2)!} \rPa^{-a} \lPa \frac{C}{n\rho} \rPa^{t - 1} \lPa \frac{C \ell^{3}(\rho + \zeta)}{1 + \zeta} \rPa^{\frac{b - t}{r - 1}} \sum_{w \geq 0} \lPa \frac{C \ell^{2}}{n\rho} \rPa^{w}\,.\] By 46 , the prefactor outside the summation in the above display is at most \(\Gamma\). Furthermore, the assumption \(\rho = \omega(n^{-1} \log^{6 + 3/(r-1)}{n})\) guarantees that \(\ell^2/(n\rho) = o(1)\) and so the summation over \(w\) is bounded by an absolute constant. Hence, we bound the preceding display by \[C\ell^{6} \sum_{\substack{a, t \geq 1 \\ b \geq t}} \lPa \frac{en^{r - 1} \rho^{2r - 2} \lambda^{2}}{(1 + \zeta)(r - 2)!} \rPa^{-a} \lPa \frac{C}{n\rho} \rPa^{t - 1} \lPa C \ell^{3}(\rho + \zeta) \rPa^{\frac{b - t}{r - 1}}\,,\] where we dropped the \(1 + \zeta\) factor in the last term by absorbing it into a constant factor, recalling that \(\zeta = o(1)\). Using the assumption \(\frac{en^{r - 1} \rho^{2r - 2} \lambda^{2}}{(r - 2)!} \geq 1 + \eps\) and taking \(n\) large so that \(\frac{1+o(1)}{1+\eps} \leq 1 -\eps/4\), we obtain \[\sum_{\substack{\alpha, \beta \in \sT \\ \alpha \cap \beta \neq 0, \alpha \neq \beta}} \E[Y^{\alpha + \beta}] \leq C\ell^6 \sum_{\substack{a, t \geq 1 \\ b \geq t}} (1 - \eps/4)^{a} \lPa \frac{C}{n\rho} \rPa^{t - 1} \lPa C \ell^{3}(\rho + \zeta) \rPa^{\frac{b - t}{r - 1}}\,. \label{eq:sparse:PCA:upper:bound:final:case:estimate}\tag{52}\] Recalling 47 , the assumptions \(\rho = o(\log^{-6(r - 1) - 3}{n})\) and \(\rho = \omega(n^{-1} \log^{6 + 3/(r-1)}{n})\) imply that \[C\ell^{3}(\rho + \zeta) \leq C\ell^{3}\rho + \lPa \frac{C\ell^{3/(r-1)}}{n\rho} \rPa^{r-1} = o(1)\,.\] Choose \(n\) sufficiently large so that the \(o(1)\) term on the RHS is at most \(1/2\). Isolate the \(t = 1\) case: \[\begin{align} \sum_{a, b \geq 1} (1 - \eps/4)^{a} \lPa C \ell^{3}(\rho + \zeta) \rPa^{\frac{b - 1}{r - 1}} &= \sum_{a \geq \ell} (1 - \eps/4)^{a} + \sum_{\substack{a \geq 1 \\ b \geq 2}} (1 - \eps/4)^{a} \lPa C \ell^{3}(\rho + \zeta) \rPa^{\frac{b - 1}{r - 1}} \\ & \leq (1 - \eps/4)^{\ell} + O_{r, \eps} \lPa \lPa \ell^3(\rho + \zeta) \rPa^{1/(r-1)} \rPa\,, \end{align}\] where we use Lemma 24 for the \(b = 1\) case on the RHS. For the \(t \geq 2\) case, directly take summation over \(a\) and \(b \geq t\) to obtain \[\sum_{a \geq 1, t \geq 2} \sum_{b \geq t} (1 - \eps/4)^{a} \lPa \frac{C}{n\rho} \rPa^{t - 1} \lPa C \ell^{3}(\rho + \zeta) \rPa^{\frac{b - t}{r - 1}} = O_{r,\eps} \lPa \frac{1}{n\rho} \rPa\,.\] Combining the above casework and recalling that \((1 - \eps/4)^{\ell} \leq \rho\) and \(\zeta=\lPa \frac{C}{n\rho} \rPa^{r-1}\), the RHS of 52 is at most \[\begin{align} & C\ell^6(1-\eps/4)^{\ell} + C\ell^6(\ell^3(\rho+\zeta))^{1/(r-1)} + \frac{C\ell^6}{n\rho} \\ &\leq C\ell^{6}\rho + C\lPa \ell^{6(r - 1) + 3}\rho + C \lPa \frac{\ell^{6 + 3/(r-1)}}{n\rho} \rPa^{r - 1} \rPa^{1/(r-1)} + \frac{C\ell^{6}}{n\rho}\,. \end{align}\] As before, the assumptions on \(\rho\) guarantee that the RHS of the preceding display is \(o(1)\).

7.2 Planted dense subhypergraph↩︎

This section is devoted to the proofs of Theorem 3-(b) and Theorem 4-(b).

7.2.1 Large planted dense hypergraph↩︎

We first consider the more general case without the restriction that \(\rho \leq n^{-1/2}\). In analogy to the proof of our lower bound, the calculations from the planted subtensor model can be reused here.

7.2.2 Small dense planted hypergraph↩︎

Now we specialize to the special scaling regime where, \[\rho = n^{\xi - 1}, \quad q_{0} = n^{-b}, \quad q_{1} = n^{-a}\] for fixed parameters \(\xi \in (0, 1/2]\) and \(a, b \in (0, r - 1)\) with \(a < b\).

As pointed out in the proof of our lower bound for small dense planted hypergraph, the existence of particularly dense graphs will contribute substantially to the correlation in this regime. Thus, our estimator will count these dense graphs, and this motivates the next definition.

8 Equivalence of symmetric and asymmetric models↩︎

Here we formalize the correspondence between the asymmetric and symmetric tensor PCA models.

Let \(\theta \in \R^n\) be a random vector. For a parameter \(\lambda \geq 0\) and \(W \in (\R^n)^{\otimes r}\) a random tensor with independent \(\cN(0, 1)\) entries, we define the asymmetric tensor PCA model as \(Y =\lambda \theta^{\otimes r} + W\). Let \(P\) be the orthogonal projection onto the subspace of symmetric tensors: \[(PX)_{i_1,\ldots,i_r} = \frac{1}{r!} \sum_{\pi \in S_r} X_{i_{\pi(1)},\ldots,i_{\pi(r)}}, \quad \forall X \in (\R^{n})^{\otimes r}\,,\] where \(S_r\) is the set of all permutations of \([r]\). For a given parameter \(\lsy \geq 0\), we let \(\Wsy = \sqrt{r!}PW\) and define the symmetric tensor PCA model as \(\Ysy = \lsy \theta^{\otimes r} + \Wsy\).

Let \(x\) be a scalar estimand, which we assume is \(\theta\)-measurable. For the asymmetric and symmetric model, define accordingly the degree-\(D\) maximum correlation \[\Corr_{\leq D}(\lambda) := \sup_{f \in \R_{D}[Y]} \frac{\E[xf(Y)]}{\sqrt{\E[x^{2}] \E[f(Y)^{2}]}}\,, \quad \Corr_{\leq D}^{\mathsf{sy}}(\lsy) := \sup_{f \in \R_{D}[\Ysy]} \frac{\E[xf(\Ysy)]}{\sqrt{\E[x^2] \E[f(\Ysy)^2]}}\,,\] which we view as functions of \(\lambda\) and \(\lsy\), respectively.

9 Polynomial time algorithmic guarantee↩︎

This section is devoted to the proof of algorithmic guarantee (Theorem 7). Throughout, we shall assume that \(Y\) is generated from the planted dense subhypergraph model; the same proof applies to the symmetric sparse tensor PCA model after substituting the Preprocessing step in Line 2 of Algorithm 2 with Algorithm 4.

Recall that the estimator constructed in Section 7.1.1 counted the number of trees of a certain structure. Let \(\ell=\lceil \frac{4}{\eps}\log(1/\rho) \rceil=O_{\eps}(\log{n})\) be the same as defined in the proof of Theorem 3-(b) (see Section 7.1.1) and write \(k=(r-1)(2\ell+2)+1\) resp. \(\ell_k=(k-1)/(r-1)\) to denote the number of vertices resp. edges in any tree \(\alpha \in \sT\equiv\sT_{\ell}\). Note that \(k\) here differs from the notation used in Section 7.1.1.

We shall also assume that \(\lambda = \frac{q_1-q_0}{\sqrt{q_0(1-q_0)}} = \sqrt{\frac{(r-2)!(1+\eps)}{en^{r-1}\rho^{2r-2}}}\) holds with equality, as was done in the proof of Theorems 3 and 5. We justify this assumption as follows. Let \(p \in [0, 1]\) and suppose \(Y\) is an instance of the planted dense subhypergraph model with parameters \(\rho, q_0, q_1\). Let \(Y_\star\) be the hypergraph obtained by iterating the following procedure: independently, for each \(e = \{i_1,\ldots,i_r\}\), leave \(Y_e\) unchanged with probability \(p\) and with probability \(1-p\) replace \(Y_e\) with the outcome of an independent \(\Ber(q_0)\) random variable. Observe that, conditional on \(\theta\), \[\text{(Y_\star)_e = 1 with probability p(q_0+(q_1-q_0)\theta^{V(e)}) + (1-p)q_0 = q_0 + p(q_1-q_0) \theta^{V(e)}}\] In other words, \(Y_\star\) has the law of an instance of the planted dense subhypergraph model with \(q_1\) decreased to \(q_1' = q_0+p(q_1-q_0) \in [q_0, q_1]\) and the remaining parameters unchanged. In particular, by preprocessing the edges in this way, we may assume that \(q_1\), and thus \(\lambda\), is as small as possible.

For each vertex \(i \in [n]\), let \(\sT^{(i)}\) be the set of trees obtained by relabelling \(1\) as \(i\). That is, letting \(\pi_i\) denote the transposition exchanging vertex \(1\) and \(i\), we let \(\sT^{(i)} = \{(\pi_i(e))_{e \in \alpha}: \alpha \in \sT\}\). Define \[f^{(i)}(Y) = \sum_{\alpha \in \sT^{(i)}} \widetilde{Y}^{\alpha} \quad\textrm{where}\quad\widetilde{Y}=\frac{Y-q_0}{\sqrt{q_0(1-q_0)}}\,,\] and observe that, because the distribution of the planted subhypergraph model is invariant under vertex relabeling, Theorem 3-(b) implies \(\Corr \lPa f^{(i)}(Y), \theta_{i} \rPa = \frac{|\E[\theta_i f^{(i)}(Y)]|}{\sqrt{\E[\theta_i^2] \E[f^{(i)}(Y)^2]}} = 1-o(1)\).

The idea is to replace the tree counts by a color-coded version, obtained by randomly coloring the vertices \([n]\) and counting only those trees \(\alpha \in \sT^{(i)}\) whose vertices receive distinct colors. Let us fix an integer \(t \geq 1\), whose exact value will be determined later (see the proof of Proposition [prop:single:vertex:recovery] below). Let \(c_{1}, \ldots, c_{t}: [n] \rightarrow [k]\) be independent, uniformly random colorings, chosen independently of \((Y, \theta)\) and define \(\xi_{s}(\alpha) = \In_{\text{c_{s} is injective on V(\alpha)}}\). Compute, \[\E[\xi_{s}(\alpha)] = \Pb(\xi_{s}(\alpha) = 1) = \Pb(\text{c_{s} is injective on [k]}) = \frac{k!}{k^{k}} =: q\] for all \(s \in [t]\) and \(\alpha \in \sT^{(i)}\). Next, for each vertex \(i \in [n]\), we define the single color-coded estimator \[f_{s}^{(i)}(Y) = \frac{1}{q}\sum_{\alpha \in \sT^{(i)}} \widetilde{Y}^{\alpha} \xi_{s}(\alpha)\,.\] Letting \(\E_{Y}\) denote the expectation conditional on \(Y\), we calculate \[\E\nolimits_{Y}[f_{s}^{(i)}(Y)] = \frac{1}{q}\sum_{\alpha \in \sT^{(i)}} \widetilde{Y}^{\alpha} \cdot \E\nolimits_{Y}[\xi_{s}(\alpha)] = \sum_{\alpha \in \sT^{(i)}} \widetilde{Y}^{\alpha} = f^{(i)}(Y)\,. \label{eq:single:coloring:unbiased}\tag{53}\] Finally, we define our candidate estimator: \[g^{(i)}(Y) = \frac{1}{t} \sum_{s = 1}^{t} f_{s}^{(i)}(Y)\,.\] Taking summation over \(s=1,\ldots,t\) in 53 shows that \(\E_{Y}[g^{(i)}(Y)] = f^{(i)}(Y)\). Furthermore,

From the preceding, we deduce the following result.

References↩︎

---

1. Email: danielfu1@brown.edu.↩︎

2. Email: youngtaksohn@brown.edu.↩︎

3. For tensor PCA with general prior, when \(r\) is even and \(\pi\) is symmetric, the model is invariant under \(\theta \leftrightarrow -\theta\), so direct estimation of \(\theta\) is impossible. In that case, one instead estimates \(\theta\theta^{\top}\) or \(\theta^{\otimes r}\). Our lower bound in Theorem 6 rules out both forms of recovery.↩︎

4. There is also an equivalent vector analog, in which one minimizes \(\EE[\|f(Y)-\theta\|^2]\) over vector-valued polynomial estimators \(f\) of degree at most \(D\) (see e.g. [7] and [4]).↩︎

5. The assumption \(q_0 <q_1\) is without loss of generality, since the complement hypergraph \(Y' = \mathbf{1} - Y\) is planted dense subhypergraph with \((q_0, q_1)\) replaced by \((1-q_0, 1-q_1)\).↩︎

6. Condition (23) of [40] reads \(\limsup_{n\to\infty}\log_n \SNR \geq 0\) in our normalization, but should be read as \(\SNR \geq c\) for a constant \(c > 0\) based on its proof.↩︎

7. Although their bound is on the vectorized MMSE for estimating the tensor \(\theta^{\otimes r}\), by symmetry of the i.i.d. prior this is equivalent up to a \(1+o(1)\) factor to the scalar MMSE with estimand \(x = \prod_{i=1}^r \theta_i\), since the dominant contribution in the vectorized MMSE comes from the entries of the tensor with all distinct indices.↩︎