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.
23-04-24

---

Abstract

Suppose that M is an unknown finite point set in R^d. Suppose ω is some distribution on M, and γ is the standard d-dimensional 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 find-approximation 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 well-seperated. 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.