  We study the problem of learning a latent variable model from a stream of
data. Latent variable models are popular in practice because they can explain
observed data in terms of unobserved concepts. These models have been
traditionally studied in the offline setting. In the online setting, on the
other hand, the online EM is arguably the most popular algorithm for learning
latent variable models. Although the online EM is computationally efficient, it
typically converges to a local optimum. In this work, we develop a new online
learning algorithm for latent variable models, which we call SpectralLeader.
SpectralLeader always converges to the global optimum, and we derive a
sublinear upper bound on its $n$-step regret in the bag-of-words model. In both
synthetic and real-world experiments, we show that SpectralLeader performs
similarly to or better than the online EM with tuned hyper-parameters.
