Computer Science Seminar Speaker: Somnath Chakraborty, Ruhr Universitat Date: Tuesday, 23 April 2024 Time: 11:45 AM Venue: Seminar Hall Learning mixture of Gaussians: a noisy coupon collector's problem Somnath Chakraborty Ruhr Universitat. 230424 Abstract Suppose that M is an unknown finite point set in R^d. Suppose ω is some distribution on M, and γ is the standard ddimensional Gaussian. Let X_ω and X_γ are independent random variables whose distributions are ω and γ, respectively. Can we devise an efficient randomized algorithm that, given small e,δ > 0, and independent random samples of X_ω + X_γ, outputs a distribution ˆω such that support of ˆω is a finite point set ˆM, having same cardinality as M, and within distance e from M, and sup_{m∈M} ω(m) − ˆω(π(m)) is ‘small’ for some bijection π : M → ˆM, with success probability at least 1 −δ? The problem can be interpreted as a noisy version of the popular coupon collector's problem. It's solution requires that we findapproximation of the centers of the underlying mixture of identical spherical gaussians, and good approximation of the weights, and in turn, this requires the centers to be wellseperated. We do this in the regime when the number of centers is exponential in the dimension, using polynomially many computational steps (as a function of the number of centers). In the nonconstant dimension our bound on minimum separation of the centers was not known earlier. This is based on joint work with Hariharan Narayanan.
