[edit]
Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2712-2737, 2020.
Abstract
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(√nlnnm) with high probability when m=Ω(√nlnn), slightly improving existing bounds for this range of m. We further prove lower bounds, showing that the error is Ω((nm4)1/2) when m is between Ω(lnn) and O(n1/4), and the error is Ω((nm4)1/6) when m is between Ω(n1/4) and O(n1−ϵ) for an arbitrarily small ϵ>0, improving existing lower bounds and extending to a wider range of m.