Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a stochastic EM algorithm. Specifically, the authors use a minibatch to approximate the data and use samples obtained from Metropolis-Hasting (MH) to approximate the likelihood component per datum. The proposed method is tested on a synthetic dataset and several UCI datasets.
main_review: The main contribution of this paper is the proposed likelihood component approximation using MH, as using minibatch to approximate the dataset is pretty common in ML. The empirical results of the proposed method seem promising, but I have some concerns about the methodology.

It is known that MCMC needs a burn-in phase in order to produce samples from the correct distribution. The proposed algorithm only runs M steps where M needs to be small enough to save computation. It is hard to believe the samples are from the right distribution. Moreover, the algorithm collects consecutive samples thus the samples will be highly correlated. What is the acceptance probability of MH? It seems that these will introduce bias to the approximation. Besides introducing bias, how is the variance of this approximation?

In summary, the idea is reasonable and there seems empirical performance. But the methodology is not very sound.  

limitations_and_societal_impact: The paper does not contain this part.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a stochastic approximation to the E-step of the EM algorithm to reduce the computational cost of fitting mixture models when the number of components $K$ is large. Specifically, the paper proposes using $M << K$ samples of the latent variables $z$ from a Metropolis-Hasting (MH) sampler to approximate the E-step. This lets us only use $M$ likelihood evaluations instead of $K$ for each observation in the E-step. The paper compares there proposed method against other EM-based methods on Gaussian mixture models on synthetic data, and sum product  transform networks and non-volume preserving flows on 19 UCI datasets. 
main_review: This paper should be rejected.

Originality: the combination of MH-sampler and EM appears new, specifically only sampling $M << K$ points to avoid evaluating the likelihood $K$ times for each point. The paper focus primarily on EM methods, but does not discuss comparisons with variational inference (both EM and VI are variational methods that maximize the ELBO).

Quality: the paper is mostly correct. I have a few small concerns: 
For Section 4.1, initializing MH sampler $z_i$ from the last sampled $z_i$ (to avoid using a burnin) seems reasonable, but for large N relative to minibatch size B, isn't it possible the last sampled $z_i$ could be very stale (if $i$ hasn't been selected in a minibatch for a long time)?
For Section 6.1 line 227, doesn't the GMM have an analytic closed form solution for $\theta$ given $x,z$? Why resort to gradient based optimization?
For Section 6.3. I do not know if a large $\Delta \mathcal{L}^{test}$ is meaningful or not. Especially for large $K$. How do you interpret this practically? And for models with $K=16384$ do we expect convergence given the # iteration, $M$ and $N$? 
In the conclusion line 316, MH when *run to convergence* ensures sampling from the proper posterior, here we explicitly are only taking $M = 2$ steps. How does this approximation affect the accuracy vs runtime tradeoff? For more complex models, where the runtime benefit of avoiding likelihood computations is larger, but this approximation is less accurate does this algorithm help or hurt?

Clarity: The paper's writing and organization is okay, but the paper could use additional editing to improve grammar + use more professional/less casual tone. For example: the paragraph around line 77.
  
Significance: Why are we interested in fitting mixture models with large $K$? 

Other notes:
* line 49: mdoels -> models
* order of $TKND$ in $O(TKND)$ isn't consistent throughout
* not necessary, but would be nice to include comparisons against gibbs sampling or VI to make the experiments stronger. 
limitations_and_societal_impact: N/A.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new method for scalably fitting mixture models. The authors tackle the problem of fitting with a large number of mixture components. While there exist some works handling this problem, these methods are all limited to mixtures of exponential family distributions, whereas the authors’ method applies to generic mixture models (as long as the model provides a likelihood p(data point i | cluster k)). They do so by proposing a modified version of the EM algorithm: instead of exactly computing the expectations in the E step, the authors propose to use a Metropolis Hastings algorithm to approximate the required expectations. In experiments, the authors show that their method (1) outperforms pre-existing large-K methods (where such previous applications are applicable), and (2) show that their method outperforms standard stochastic gradient descent in settings where other large-K methods are not applicable. The authors’ method seems to work well, but I have a few clarification questions about the technical ideas behind the proposed algorithm and its empirical evaluation. Currently, I put a borderline score for the paper, but I’m definitely open to increasing it after discussion.
main_review: ---------------------------------------------

**Update after discussion with authors and other reviewers**

Thanks to the authors for really engaging in the discussion period. I think it's become clear that some major revisions are needed in order to fully describe / experiment with the proposed E-step approximation. I've actually changed my score to a weak reject because of this. I do want to be clear that this is only because of the limits of the conference review cycle, where reviewers don't see an updated draft. In particular, I think a revision is likely to result in a strong accept, but the revisions are too substantial to accept without seeing them. Just to summarize, there are two things that I think remain:

1. The main issue is the need for a more targeted discussion and experimentation surrounding the proposed E-step approximation. I think the directions in terms of references that the authors have brought up will strengthen things here a lot. And the proposed experiment seems like a great step in the right direction on the empirics front. Personally, I think using a continuing Markov chain between optimization iterations is pretty interesting and surprising, so I really think the paper would be both more complete and more interesting with a deeper investigation of this idea.

2. This is a lot more minor, but I do want to argue a little bit more about the stopping rule used in the experiments. I agree that adding some tolerance $\delta$ will give an extra degree of freedom in the experiments. But, since this is how the method will be used in practice, it seems worth looking into. I don't mean that it's necessary to have a whole extra set of experiments investigating the sensitivity with respect to $\delta$. It's just good to make the experiments as close to reality as possible, and it doesn't seem like there's a strong reason to not make the experiments more realistic in this regard.



---------------------------------------------

I’ve listed my main comments/questions as (A), (B), (C) below.

(A) The use of Monte Carlo to help with an intractable E step is not a new idea, and I think the paper needs more discussion of the related work in this area. For example, see Levine and Casella (2001) (reference below). Ideas from this literature might be helpful for the current paper – e.g. Levine and Casella (2001) recommend updating the Monte Carlo samples from the previous E step via importance sampling, rather than re-running a MCMC method. Still, I don’t know that other work has handled the issue of a high-dimensional parameter space (here, the number of mixture components K is large), which sounds like an important addition over pre-existing work.

(B) I have a few technical questions about the presented algorithm.
1. The hope of the method is that we can effectively approximate the E step by drawing $M \ll K$ samples from the distribution $p(z_i | x_i)$. It seems that in some sense this is automatically impossible – the distribution $p(z_i | x_i)$ has support of size $K$, so we can’t, in general, approximate expectations over this distribution with only $M$ samples. So I think it’s unlikely that, in general, “the chain passes the transition period (the burn-in phase)” as the authors note. Presumably the authors’ method either relies on some regularity conditions (maybe the distribution $p(z_i | x_i)$ is mostly concentrated on a few points?) or maybe performing the M-step with an only approximate objective is fine, or maybe something else is happening. In any case, can the authors clarify with discussion and/or additional experiments what is driving the success of their method?
2. On lines 130-138, I think the authors are proposing to somehow reuse the samples from $p(z_i | x_i)$ between iterations. But the distribution being sampled from is changing from iteration to iteration (i.e. it depends on the parameters $\theta$ estimated from the M-step). What do the authors mean on line 131 when they talk about samples being “recycled over the iterations”?
3. The authors parameterize the mixing weights $\pi_k$ by a $K$ real-valued parameters $\nu_1, \dots, \nu_K$, and then set $\pi_k = e^{\nu_k} / \sum_{l=1}^K e^{\nu_l}$. But this transformation leaves a degree of freedom unconstrained (i.e. scaling all $\nu_k$ by the same constant $c$ will leave the $\pi$’s unchanged), meaning there is no unique optimum of the log-likelihood. This seems potentially undesirable, but maybe isn’t a huge deal.

(C) I also have a few questions about the empirical evaluation of the authors’ method.
1. For the purposes of considering an algorithm terminated, the authors stop each algorithm when it reaches 95% of the maximum likelihood value that it will achieve. I have two questions about this. The first is why is this a reasonable metric? Can we be sure that the fitted parameters will not change much as we traverse the last 5% of the loss? Second, this doesn’t necessarily seem like a good way to assess convergence of practical algorithms. In particular, the only way to define this stopping criteria is to first run the algorithm to termination so that we know what the final log likelihood value is, and then go back and stop it 95% of the way there. Can the authors argue that this does not bias the results at all? For example, it could be that it takes much longer for their algorithm to traverse the final 5% of the likelihood than other algorithms.
2. The authors choose a particular annealing schedule for use across all algorithms. How did they choose this schedule? Does it definitely not bias the results in favor of one algorithm or another?
3. Are all the experiments done with multiple random restarts for each method? Figure 1 says that “the results are averaged over five repetitions”, but it’s not clear to me how these repetitions are done. Are these five different random initializations? Or five different runs from the same initialization? Each curve in Figure 1 looks like the run from a single random seed, so it seems to be the latter. I think there should be multiple random seeds used so that we know that, for example, TSAEM (the fastest algorithm to reach its optimum in Figure 1) isn’t just getting unluckily stuck in a local optimum in Figure 1.
4. Why isn’t MHSAEM-TF used in the experiment in Section 6.2? The authors state that it is due to the “favorable computational complexity and simplicity” of MHSAEM-U, but it seems like in Figure 2 the U and TF versions of these algorithms have just about the same performance.
5. Similarly to point #3, are the results in Table 2 run over multiple random restarts? If so, there should be standard errors reported so that we know how significant the differences are.

-----Citations--------

Richard A. Levine and George Casella. Implementations of the Monte Carlo EM Algorithm. Journal of Computational and Graphical Statistics , Sep., 2001, Vol. 10, No. 3

limitations_and_societal_impact: The authors do include a broader impact statement, but it's over the nine page limit. Note that the broader impact statement is supposed to be included within the page limit of the main text.

In their paper checklist, the authors write [N/A] for whether their datasets were obtained with consent and whether their datasets contain personally identifiable information or offensive content. Their datasets were taken from the UCI repository, so presumably neither of these things is true, but that doesn't mean it isn't relevant to this paper. I think a quick appendix about the data used would resolve this issue.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The authors propose a sampling-based method to improve the efficiency of the E-M algorithm on mixture models. The method relies on performing the computations on a reduced number of MCMC-sampled components, rather than all of them.
main_review: The paper is well-structured, and I did not have a problem following the exposition.

The main idea of the paper is straightforward: instead of performing computations over all mixture model components, perform an approximate computation on a smaller number of components sampled via MCMC to reduce the total complexity of E-M. While reasonable, this idea by itself does not constitute a significant contribution, and there is no further theoretical analysis or discussion. The "TF" proposal distribution in section 4.3 could potentially be a novel contribution, but it is only discussed very briefly (see also following comments).

The experimental section, and specifically the two non-synthetic data experiments of sections 6.2 and 6.3, seem to have some major flaws:
- The authors do not even evaluate the previously discussed "TF" proposal in these experiments.
- The experiments seem to have been run with $M = 1$, which means just choosing a single component at random. Whether this choice is uniform or not depends on whether there is a burn-in period or not, which is also not discussed in the paper. I do not see the point in discussing an MCMC method if only a single sample is used in the end.
- I do not understand why there are such big differences in the test likelihood values in Table 2 between the two compared methods. In particular, why would the "SGD" method ever result in so much worse likelihoods? Is it some implicit regularization effect? Is the variance of the likelihood over different repetitions high? Why do the authors not show standard deviations, since their results are over five repetitions?
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: Reviewers are intrigued by the proposed approach to learning mixture models, but voice a number of substantial concerns related to both the clarity and correctness of the technical material on Monte Carlo approximations.  The author response was considered, but for some reviewers, it raised more questions than it answered.  After some discussion, the consensus was that very-major revisions are needed to clearly explain and justify the proposed method, and that such changes require a full review at some future conference.
Decision: Reject