Stochastic variational inference makes it possible to approximate posterior distributions induced by large datasets quickly. The algorithm relies heav-ily on the use of fully factorized variational dis-tributions. However, this “mean-field ” indepen-dence approximation introduces bias. We show how to relax the mean-field approximation to al-low arbitrary dependences between global pa-rameters and local hidden variables, reducing both bias and sensitivity to local optima. 1