On some provably correct cases of variational inference for topic models
Variational inference is an efficient, popular heuristic used in the context of latent variable models. We provide the first analysis of instances where variational inference algorithms converge to the global optimum, in the setting of topic models. Our initializations are natural, one of them being used in LDA-c, the most popular implementation of variational inference. In addition to providing intuition into why this heuristic might work in practice, the multiplicative, rather than additive nature of the variational inference updates forces us to use non-standard proof arguments, which we believe might be of general theoretical interest.
The authors prove that variational inference in LDA converges to the ground truth model, in polynomial time, for two different case studies with different underlying assumptions about the structure of the data. In this analysis, the authors employ "thresholded" EM updates which estimate the per-topic word distribution based on the subset of documents where a given document dominates. The proofs, which are provided in a 35-page supplement, require assumptions about the number of words in a document that are uniquely associated with each topic, the number of topics per document, and the number documents in which a given word exclusively identifies a topic.I am not enough of a specialist to evaluate the provided proofs in detail, so I will restrict myself to relatively high level comments. Empirically speaking, variational inference can and does get stuck in local maxima. This suggests that at least some of the assumptions that the authors make will not (always) hold for real-world datasets. As such my intuition is that the authors may have identified a set of conditions under which variational inference in LDA is provably "easy". This in itself is a potentially useful contribution. Assuming the proofs are sound, I would argue for acceptance.## Comments on content- I'm a bit confused about the role of the  parameters, about which the authors appear to make several conflicting statements    > The  Dirichlet parameters do not have a closed form expression and are   > updated via gradient descent.         Do the authors in fact perform emprical Bayes / type II max likelihood   estimation? The statement below suggests otherwise    > In particular, in the E-step, in the large document limit, the first   > term in the update equation for  has a vanishing contribution    The authors further on state that    > These assumptions are a less smooth version of properties of the   > Dirichlet prior. Namely, it's a folklore result that Dirichlet draws   > are sparse with high probability, for a certain reasonable range of   > parameters.    Dirichlet draws are indeed sparse when  << 1.0, but not necessarily when    => 1.0. This is not so much a "folklore result" as a well known   property of the Dirichlet distribution. Indeed, the lemma referenced in   the supplementary material assumes _i = C_i / K^c with c > 1.    The authors assume  can be ignored in EM updates, but at the same time   make assumptions about sparsity. It would appear they are implicitly   making assumptions about the  true generative process of the data, even   when the same values for  are not necessarily used during inference. Can   they comment on this?- What is meant by "if i does not belong to document d" in Algorithm 1?- The exposition in section 4.2 as a whole is somewhat confusing. I would recommend that the authors simply write down their proposed updates, then explain how these updates relate to the ones in [Lee and Seung 2000], and then argue what guarantees apply to these updates.## Comments on style- It would benefit the readability of this paper if the authors would put equations on separate lines (and number them) -- at the very least in those cases where equations require a summation sign. This also eliminates awkward back references like "the first term in the update equation for ".- Similarly, explicitly writing out the generative model, even if well known, never hurts. It avoids vague phrases like "sampled according to a prior distribution ".- There is some confusion of notation between X and w, which are both used to refer to the words in the document set.- There is also some confusion as to the indexing of variables, which in some cases do and in others do not include the document index d.- This is a matter of personal preference, but I would use `discrete` rather than `multinomial` when describing the generative model of LDA.- The words "latent Dirichlet allocation" do not appear in the manuscript. Why did the authors consistently write "topic model" to refer to LDA?## Typos- 131: min -> \min