We study the problem of estimating the mean of an identity covariance
Gaussian in the truncated setting, in the regime when the truncation set comes
from a low-complexity family $\mathcal{C}$ of sets. Specifically, for a fixed
but unknown truncation set $S \subseteq \mathbb{R}^d$, we are given access to
samples from the distribution $\mathcal{N}(\boldsymbol{ \mu}, \mathbf{ I})$
truncated to the set $S$. The goal is to estimate $\boldsymbol\mu$ within
accuracy $\epsilon>0$ in $\ell_2$-norm. Our main result is a Statistical Query
(SQ) lower bound suggesting a super-polynomial information-computation gap for
this task. In more detail, we show that the complexity of any SQ algorithm for
this problem is $d^{\mathrm{poly}(1/\epsilon)}$, even when the class
$\mathcal{C}$ is simple so that $\mathrm{poly}(d/\epsilon)$ samples
information-theoretically suffice. Concretely, our SQ lower bound applies when
$\mathcal{C}$ is a union of a bounded number of rectangles whose VC dimension
and Gaussian surface are small. As a corollary of our construction, it also
follows that the complexity of the previously known algorithm for this task is
qualitatively best possible.

在截断设置下，通过统计查询 (SQ) 下界和超多项式的信息计算差，我们研究了估计截断恒等协方差高斯分布的均值问题。