Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model

摘要

In the setting of entangled single-sample distributions, the goal is to estimate some common parameter shared by a family of $n$ distributions, given one single sample from each distribution. This paper studies mean estimation for entangled single-sample Gaussians that have a common mean but different unknown variances. We propose the subset-of-signals model where an unknown subset of $m$ variances are bounded by 1 while there are no assumptions on the other variances. In this model, we analyze a simple and natural method based on iteratively averaging the truncated samples, and show that the method achieves error $O left(rac{sqrt{nln n}}{m}ight)$ with high probability when $m=Omega(sqrt{nln n})$, slightly improving existing bounds for this range of $m$. We further prove lower bounds, showing that the error is $Omegaleft(left(rac{n}{m^4}ight)^{1/2}ight)$ when $m$ is between $Omega(ln n)$ and $O(n^{1/4})$, and the error is $Omegaleft(left(rac{n}{m^4}ight)^{1/6}ight)$ when $m$ is between $Omega(n^{1/4})$ and $O(n^{1 - epsilon})$ for an arbitrarily small $epsilon>0$, improving existing lower bounds and extending to a wider range of $m$.