Collapsed variational Bayes for Markov jump processes
Markov jump processes are continuous-time stochastic processes widely used in statistical applications in the natural sciences, and more recently in machine learning. Inference for these models typically proceeds via Markov chain Monte Carlo, and can suffer from various computational challenges. In this work, we propose a novel collapsed variational inference algorithm to address this issue. Our work leverages ideas from discrete-time Markov chains, and exploits a connection between these two through an idea called uniformization. Our algorithm proceeds by marginalizing out the parameters of the Markov jump process, and then approximating the distribution over the trajectory with a factored distribution over segments of a piecewise-constant function. Unlike MCMC schemes that marginalize out transition times of a piecewise-constant process, our scheme optimizes the discretization of time, resulting in significant computational savings. We apply our ideas to synthetic data as well as a dataset of check-in recordings, where we demonstrate superior performance over state-of-the-art MCMC methods.
The authors present a variational inference algorithm for continuous time Markov jump processes. Following previous work, they use "uniformization" to produce a discrete time skeleton at which they infer the latent states.  Unlike previous work, however, the authors propose to learn this skeleton (a point estimate, via random search) and to integrate out, or collapse, the transition matrix during latent state inference.  They compare their algorithm to existing MCMC schemes, which also use uniformization, but which do not collapse out the transition matrix.
While this work is well motivated, I found it difficult to tease out which elements of the inference algorithm led to the observed improvement. Specifically, there are at least four dimensions along which the proposed method differs from previous work (e.g. Rao and Teh, 2014):  (i) per-state \Omega_i vs shared \Omega for all states; (ii) learned point estimate of discretization vs sampling of discretization;  (iii) variational approximation to posterior over latent states vs sampling of latent state sequence; and (iv) collapsing out transition matrix vs maintaining sample / variational factor for it.  That the "Improved MCMC" method does not perform better than "MCMC" suggests that (i) does not explain the performance gap.  It seems difficult to test (ii) explicitly, but one could imagine a similar approach of optimizing the discretization using sample based estimates of the marginal likelihood, though this would clearly be expensive.  
Dimensions (iii) and (iv) suggest two natural alternatives worth exploring. First, an "uncollapsed" variational inference algorithm with a factor for the transition matrix and a structured variational factor on the complete set of latent states U. Indeed, given the discretization, the problem essentially reduces to inference in an HMM, and uncollapsed, structured variational approximation have fared well here (e.g. Paisley and Carin, 2009; Johnson and Willsky, 2014).  Second, it seems you could also collapse out the transition matrix in the MCMC scheme of Rao and Teh, 2014, though it would require coordinate-wise Gibbs updates of the latent states u_t | u_{\neg t}, just as your proposed scheme requires q(U) to factorize over time.  These two alternatives would fill in the gaps in the space of inference algorithms and shed some light on what is leading to the observed performance improvements. In general, collapsing introduces additional dependencies in the model and precludes block updates of the latent states, and I am curious as to whether the gains of collapsing truly outweigh these costs. Without the comparisons suggested above, the paper cannot clearly answer this question. 
Minor comments:
- I found the presentation of MCMC a bit unclear.  In some places (e.g. line 252) you say MCMC "requires a homogeneously dense Poisson distributed trajectory discretization at every iteration."  but then you introduce the "Improved MCMC" algorithm which has an \Omega_i for each state, and presumably has a coarser discretization.   
References:
Paisley, John, and Lawrence Carin. "Hidden Markov models with stick-breaking priors." IEEE Transactions on Signal Processing 57.10 (2009): 3905-3917.
Johnson, Matthew, and Alan Willsky. "Stochastic variational inference for Bayesian time series models." International Conference on Machine Learning. 2014.