Each training step for a variational autoencoder (VAE) requires us to sample from the approximate posterior, so we usually choose simple (e.g. factorised) approximate posteriors in which sampling is an efficient computation that fully exploits GPU parallelism. However, such simple approximate posteriors are often insufficient, as they eliminate statistical dependencies in the posterior. While it is possible to use normalizing flow approximate posteriors for continuous latents, there is nothing analogous for discrete latents. The most natural approach to model discrete dependencies is an autoregressive distribution, but sampling from such distributions is inherently sequential and thus slow. We develop a fast, parallel sampling procedure for autoregressive distributions based on fixed-point iterations which enables efficient and accurate variational inference in discrete state-space models. To optimize the variational bound, we considered two ways to evaluate probabilities: inserting the relaxed samples directly into the pmf for the discrete distribution, or converting to continuous logistic latent variables and interpreting the K-step fixed-point iterations as a normalizing flow. We found that converting to continuous latent variables gave considerable additional scope for mismatch between the true and approximate posteriors, which resulted in biased inferences, we thus used the former approach. We tested our approach on the neuroscience problem of inferring discrete spiking activity from noisy calcium-imaging data, and found that it gave accurate connectivity estimates in an order of magnitude less time.
The development of variational auto-encoders (VAE) (Kingma & Welling, 2014;Rezende et al., 2014) has enabled Bayesian methods to be applied to very large-scale data, by leveraging neural networks, trained by stochastic gradient ascent, to approximate the posterior. Importantly, to perform each stochastic gradient ascent step, we need to sample from the current approximate posterior, restricting us to approximate posteriors in which sampling can be performed rapidly by leveraging parallel GPU computations. As such, most work on VAE's has used factorised approximate posteriors (e.g. Kingma & Welling, 2014;Rezende et al., 2014;Blundell et al., 2015;Higgins et al., 2017;Aitchison et al., 2017), but in many domains of interest we expect the posterior over latents to be highly correlated, not only because the posterior inherits correlations from the prior (e.g. as we might find in a dynamical system), but also because the likelihood itself can induce correlations due to effects such as explaining away (Pearl, 1988a;b). One approach to introducing correlations into the approximate posterior is normalizing flows (Rezende & Mohamed, 2015;Kingma et al., 2016) which transforms variables generated from a simple, often factorised distribution into a complex correlated distribution, in such a way that the determinant of the Jacobian (and thus the probability of the transformed variables) can easily be computed.
However, the normalizing flow approach can only be applied to continuous latents, and there are important problems which require discrete latent variables and correlated posteriors, making efficient and accurate stochastic variational inference challenging. In particular, we consider the neuroscience problem of inferring the correlated spiking activity of neural populations recorded by calcium imaging. Due to the indirect nature of calcium imaging, spike inference algorithms must be used to infer the underlying neural spiking activity (Friedrich et al., 2017;Speiser et al., 2017). Not only does the data naturally give strong explaining away induced anticorrelations (as a spike in nearby timebins produces very similar data), but there are prior correlations induced by synaptic connectivity which induces similar correlations in the approximate posterior.
To address these challenging tasks with discrete latent variables, and correlated approximate posteriors, we considered two approaches. First, we considered applying normalizing flows by transforming our discrete latents into continuous latents, which are thresholded to recover the original discrete variables (Maddison et al., 2016). However, we found that working with continuous variables gave rise to far more scope for mismatch between the approximate and true posteriors than working with discrete variables, and that this mismatch resulted in biased inferences. Instead, we developed a fast-sampling procedure for discrete autoregressive posteriors. In particular, we considered an autoregressive approximate posterior and circumvent the requirement for slow sequential sampling by developing flow-like fixed-point iterations that are guaranteed to sample the true posterior after T iterations, but in practice converge much more rapidly (in our simulations, ∼ 5 iterations), and efficiently exploit GPU parallelism.
Applying the flow-like fixed point iterations to simulated neuroscience problems, we were able to sample from autoregressive approximate posteriors in almost the same time required for factorised posteriors, and at least an order of magnitude faster than sequentially sampling from the underlying autoregressive process, allowing us to realize the benefits of correlated posteriors in large-scale settings.
Normalizing flows provide a way for variational posteriors to go beyond the mean-field assumption and introduce correlations in the posterior for latent variables. Typically, normalizing flows are only defined for continuous distributions, and the authors tackle the issue of creating flexible variational posteriors for discrete latent models. They posit a general autoregressive posterior family for discrete variables or their continuous relaxations. In order to perform variational inference with reparameterization gradients, one needs to have a sample from their variational family and be able to evaluate the density at the sample. The obvious way to sample from this autoregressive variational family is O(T) for T the number of autoregressive time-steps. Instead, they propose a method based off fixed point iterations to compute logits in parallel based off the results of previous iterations to generate an approximate sample. Moreover, they can interpret each iteration as a volume-preserving flow, so they don't have to add any terms to the density. They also use a continuous relaxation of Bernoulli random variables so they can back-propagate through a recognition network. They use their method on synthetic calcium spike data, and show that the correlated posterior is better-suited to handle uncertainty. 
This is certainly original work, and it presents it in a general way. The authors' formulation of the probabilistic model and variational family in equations 6a-7b can be extended to any autoregressive family. As the authors mention, they also do not need to work only with continuous relaxations of Bernoulli random variables, as they can extend it to categorical random variables using something like the Gumbel-Softmax/Concrete distributions.   Although the idea behind parallelizing updates is not inherently elaborate, the authors provide an interesting interpretation as a normalizing flow. 
My main criticism of the paper is the experiments section. The experiments are only performed on synthetic data sets. How do the methods scale to larger data sets? The authors state that iterations of the fixed point procedure converge rapidly in practice, but it seems like it's only been evaluated on these synthetic data sets. It seems like performing K fixed point iterations fixes the dependencies to be in a window of size K, so this may perform worse in practice for models that have long temporal dependencies (or for non-temporal latent discrete random variables where the ordering is not important). 
The experiments also do not seem to evaluate any held-out metrics. The experiments would be stronger by e.g. approximating the marginal held-out loss (perhaps using IWAE or otherwise), since it seems almost guaranteed that more flexible variational families should achieve a tighter bound on the training set (it's possible that there were actually held-out metrics but I missed them, in which case please let me know).
Another criticism of the paper is with the clarity. The authors sometime use notation before/without defining it. For example, T is used without definition it at the beginning of page 2 and N is used without definition at the beginning of section 2.1. It makes it difficult to have intuition for the math as a result of not knowing the definitions. Even things like explicitly stating that k is a timestep index before equation 9 would be helpful. 
More minor notes:
-I got a lot out of Figure 1A. For Figure 1B-E, what is beta? Is there intuition for how these results change as a function of beta?
-When you say Equation 8 in section 2.2 I believe you mean equation 7b.
Overall, there has not been much (if any) work for correlated posterior families for discrete latent variable models, and the authors have provided a promising first step. The next step would be seeing more experimental results for a larger variety of models.
PROS
-Idea is very interesting and novel, with a nice connection to normalizing flows 
-Underexplored area of research, promising first steps.
CONS
-Experiments should be more thorough
-Lack of clarity made it hard to understand at certain points