Skip to content

Latest commit

 

History

History
53 lines (53 loc) · 2.16 KB

2024-06-30-diakonikolas24b.md

File metadata and controls

53 lines (53 loc) · 2.16 KB
title section abstract layout series publisher issn id month tex_title firstpage lastpage page order cycles bibtex_author author date address container-title volume genre issued pdf extras
Statistical Query Lower Bounds for Learning Truncated Gaussians
Original Papers
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}(\bm{\mu}, \vec{I})$ truncated to the set $S$. The goal is to estimate $\bm{\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.
inproceedings
Proceedings of Machine Learning Research
PMLR
2640-3498
diakonikolas24b
0
Statistical Query Lower Bounds for Learning Truncated Gaussians
1336
1363
1336-1363
1336
false
Diakonikolas, Ilias and Kane, Daniel M. and Pittas, Thanasis and Zarifis, Nikos
given family
Ilias
Diakonikolas
given family
Daniel M.
Kane
given family
Thanasis
Pittas
given family
Nikos
Zarifis
2024-06-30
Proceedings of Thirty Seventh Conference on Learning Theory
247
inproceedings
date-parts
2024
6
30