arXiv:2603.26029 · v4

Statistical and Computational Limits for Cumulant Tensor Inference: A Regime in Which Efficient Detection Is Harder Than Efficient Estimation

首次提交 2026-03-27 10:59

版本更新 2026-11-03 03:18

雷达观测 2026-11-04 23:40

摘要

We study estimation and detection of high-order cumulant tensors from $n$ i.i.d. observations of a $p$-dimensional random vector, with performance measured in the tensor spectral norm. Under sub-Gaussianity, we show that the minimax rate for estimating the order-$d$ cumulant tensor is $\sqrt{p/n}\wedge 1$. In contrast to covariance estimation, the natural plug-in estimator obtained by replacing population moments in the moment--cumulant formula with sample moments, which we call the sample cumulant tensor, is generally not rate-optimal for $d\ge 3$, and we construct an estimator that attains the minimax rate. On the computational side, we study testing whether the $d$-th order cumulant tensor vanishes after whitening. We provide evidence, under a model-specific low-degree conjecture, that detection is computationally hard when $n\ll p^{d/2}$. At the same time, we identify a regime in which an efficiently computable estimator achieves error smaller than the separation at which polynomial-time tests can reliably distinguish the null from the alternative under the same conjecture. This reveals an unusual reverse detection--estimation gap: computationally efficient detection can be harder than computationally efficient estimation. The underlying reason is that the relevant loss, tensor spectral norm, is itself NP-hard to compute, creating a new form of computational--statistical gap.