Stochastic variational inference (SVI) enables approximate posterior inference with large data sets for otherwise intractable models, but like all variational inference algorithms it suffers from local optima. Deterministic annealing, which we formulate here for the generic class of conditionally conjugate exponential family models, uses a temperature parameter that deterministically deforms the objective, and reduce this parameter over the course of the optimization to recover the original variational set-up. A well-known drawback in annealing approaches is the choice of the annealing schedule. We therefore introduce multicanonical variational inference (MVI), a variational algorithm that operates at several annealing temperatures simultaneously. This algorithm gives us adaptive annealing schedules. Compared to the traditional SVI algorithm, both approaches find improved predictive likelihoods on held-out data, with MVI being close to the best-tuned annealing schedule.