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 a...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-03
Main Authors: Diakonikolas, Ilias, Kane, Daniel M, Pittas, Thanasis, Zarifis, Nikos
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Lower bounds
Polynomials
Samples
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422