Lower Bounds for the Gibbs Sampler over Mixtures of Gaussians


Christopher Tosh, Sanjoy Dasgupta ;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1467-1475, 2014.


The mixing time of a Markov chain is the minimum time t necessary for the total variation distance between the distribution of the Markov chain’s current state X_t and its stationary distribution to fall below some ε> 0. In this paper, we present lower bounds for the mixing time of the Gibbs sampler over Gaussian mixture models with Dirichlet priors.

Related Material