Sharp computational lower bounds for valid inference in the intermediate regime

Consider the noisy Tucker tensor completion model with order $m=3$. For each dimension $d\to\infty$, let $T^\star\in\mathbb{R}^{d\times d\times d}$ have multilinear rank $(r_1,r_2,r_3)$ with $r_j=O(1)$, Tucker decomposition $T^\star=C^\star\times_1 U_1^\star\times_2 U_2^\star\times_3 U_3^\star$, incoherent factor matrices, and bounded condition number $\kappa(T^\star)=\lambda_{\max}/\lambda_{\min}\le \kappa_0$, where $\lambda_{\min}:=\min_{j\in\{1,2,3\}}\lambda_{r_j}(M_j(T^\star))$. We observe $n=n(d)$ i.i.d. samples

where $X_i$ is uniformly distributed on the canonical basis tensors $\{e_a\circ e_b\circ e_c: a,b,c\in[d]\}$, and $\xi_i$ are i.i.d. mean-zero noise with variance $\sigma^2$ (e.g. Gaussian or uniformly sub-Gaussian). Let $d^\star=d^3$. For a deterministic indexing tensor $I=I_d\in\mathbb{R}^{d\times d\times d}$, the inferential target is $\theta^\star=\langle T^\star,I\rangle$.

This setup follows Ma & Xia (2024).

The cited paper proves Cram'er-Rao-optimal uncertainty quantification in its analyzed settings, including a rank-one regime. In particular, for rank-one (as treated in-source), with $\mathcal{M}_r$ the rank manifold and $P_{T^\star}(I)$ the tangent-space projection, the asymptotic variance benchmark is

For general multilinear rank $(r_1,r_2,r_3)$, taking this same formula as an information-theoretic optimum is a natural extrapolation but is not established in the source; extending CRLB-sharp characterization to full general-rank settings remains open/challenging.

Define a polynomial-time valid inference procedure as a randomized algorithm running in $\mathrm{poly}(d,n)$ time that outputs $(\widehat\theta,\widehat v)$ such that uniformly over a model class $\mathcal{P}_d$,

Using the source?s computational and statistical benchmark scalings in simplified form (absolute constants and polylog factors suppressed), one gets:

The intermediate regime is where the statistical benchmark holds but the computational benchmark fails (in at least one inequality).