Latent variable model: why is the marginal probability of data under the model intractable? I'm reading about Variational auto-encoders, and in section 1.8 they describe a latent variable model $p_\theta(x,z)$ where x are observed and z are hidden variables. They say that the marginal distribution over observed variables for a single datapoint is $p_\theta(x)=\int p_\theta(x,z)dz$. They proceed to say that this integral does not have an analytic solution or efficient estimator. Why is that? why can't we sample some values of z according to its prior and get a decent estimate of the distribution of x?
 A: The apparent simplicity of latent variables marginalization disappears as soon as you consider that $z$ is not necessarily a scalar, but might be a set of (possibly correlated) high-dimensional vectors. In my examples, I will consider the case where $z$ takes discrete values, although these examples readily extend to the case where $z$ is a continuous variable.
Firstly, let's assume we have $T$ i.i.d. observations $x = [x_1,\dots,x_T]$, with corresponding latent variables $z = [z_1,\dots,z_T]$. We also assume that $z_t$ is a scalar which can take $N$ possible values in $\{1,\dots,N\}$. Then the marginal distribution for a single observation can be easily computed:
$$
p_{\theta}(x_t) = \sum_{i=1}^N p_{\theta}(x_t,z_t=i)
$$
Furthermore, if observations are i.i.d., then the probability distribution of the vector $x$ is simply
$$
p_{\theta}(x) = \prod_{t=1}^T p_{\theta}(x_t)
$$
which algorithmic complexity is simply going to scale with $TN$. Fairly ok.
Now, consider that each $z_t$ is not a scalar, but rather a $M$-dimensional vector $z_t = [z_t^{(1)},\dots,z_t^{(M)}]$, where each element $z_t^{(\cdot)}$ can also take $N$ possible values in $\{1,\dots,N\}$. Then
$$
p_{\theta}(x_t) = \sum_{i=1}^N \sum_{j=1}^N \sum_{k=1}^N \cdots p_{\theta}(x_t,z_t^{(1)} = i, z_t^{(2)} = j, z_t^{(3)} = k, \dots)
$$
This time, the algorithmic complexity is going to scale exponentially with $M$. Not ok.
This gets even worse if observations are correlated, e.g. if they are drawn from a Hidden Markov Chain where $p_{\theta}(z) = p_{\theta}(z_1) \prod_{t=2}^T p_{\theta}(z_{t}|z_{t-1})$. The likelihood $p_{\theta}(x)$ can be computed using the Baum-Welch algorithm, which complexity will scale with $TN^{2M}$. Not ok at all.
Since most problems in real life imply high-dimensional latent variables (consider, for instance the problem of Bayesian Model inference, where the vector $\theta$ may contain dozens of parameters), simplicity is the exception, and not the norm. Marginalizing out latent variables is far from being an easy problem in machine learning.
