Statistical Query Lower Bounds for Learning Truncated Gaussians
<|reference_start|>Statistical Query Lower Bounds for Learning Truncated Gaussians: 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.<|reference_end|>
@article{diakonikolas2024statistical,
    title={Statistical Query Lower Bounds for Learning Truncated Gaussians},
    author={Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis},
    journal={arXiv preprint arXiv:2403.02300},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.02300},
    primaryClass={cs.DS cs.LG math.ST stat.ML stat.TH}
}