The Markov chain approximations, for example Pagerank algorithm and
the Restricted Boltzmann Machines, and the variational approximations,
like LDA
PageRank and RBMs are not Markov chain approximations, rather they use Markov chains in their implementation. Similarly, LDA (Latent Dirichlet Allocation) is a generative probabilistic model (aka Bayesian hierarchical model) and not a variational approximation. LDA may use variational approximation methods for inference.
Let me take the LDA model as an example. In LDA, a complicated generative model is constructed to learn the topic allocation probabilities of different documents. This is done by assigning prior distributions over different parameters. Inference in such Bayesian models is made on the posterior distribution. That is, having seen the data (in this case the words in each document), the prior probabilities of topic allocation are updated. These updated probabilities are contained in the posterior distribution. This whole setup describes LDA; in other words the generative model completely describes the LDA.
However, to actually use LDA in practice, users need to be able to understand the posterior distribution and access is. As it turns out the posterior distribution is not tractable and thus not available in closed form. So, approximations to this posterior distribution need to be made so that users have actual results from the model. There are two main ways to approximate the posterior distribution 1) Markov chain Monte Carlo (MCMC) 2) Variational approximation.
In MCMC, a Markov chain is constructed such that its limiting distribution is the true posterior distribution. So samples are drawn using such a Markov chain, and after some point, enough samples are obtained so that the posterior distribution can be approximated well. Since this is a sampling based method, every implementation will yield different results. MCMC is an asymptotically exact method because as you get more samples, your estimate of parameters will be exactly the true posterior quantities of interest.
In variational approximations, a general class of distributions is defined. Within this class of distributions, using optimization methods, it is determined which distribution is closest to the posterior distribution of interest. Once this approximate distribution is obtained, it is then treated as the posterior distribution, and inference is made using this approximate distribution. Variational approximations rely heavily on the class of distributions specified in the beginning. The more general the class, the more difficult is the optimization problem. The most restricted the class, the easier is the optimization problem. Variational methods are not exact methods.
The MCMC allows direct optimization of the variational lower bound.
I don'd believe this sentence is correct. MCMC does not do optimization. What is important to understand is that both these methods are computational tools that enable inference and estimation for complicated models. They are not the models themselves. This is why both MCMC and variational approximations can be (and are) used in LDA.
In an effort to explain the working difference, consider the example of a model that yields a posterior distribution that is a $t$ distribution with $5$ degrees of freedom. Our goal say is to estimate the mean of this distribution, which is 0. (In realistic settings we will not know the exact behavior of the posterior).
In MCMC, in order to estimate the mean of this distribution, we (somehow) construct a Markov chain such that when we obtain samples from it say $X_1, X_2, X_3, \dots$, then $X_{\infty}$ will be exactly a draw from $t_5$. Of course, we can't obtain infinite samples, so we say obtain some $n$ samples from this Markov chain, and calculate
$$\dfrac{1}{n} \sum_{i=1}^{n} X_i \to 0 \text{ as $n$ increases} $$
Everytime we draw a sample of size $n$ using this Markov chain, we will get a different number, but it is going to be a good approximation of 0.
In variational approximations, to estimate the mean of this $t_5$ distribtuion, we first have to define a class of distrbutions. Let's say this class of distributions is that of all normal distributions with any mean and variance. That is the class is
$$\{\mu \in \mathbb{R}, \sigma^2 >0 : N(\mu, \sigma^2)\}\,.$$
Using optimization techniques, we try and obtain values of $\mu$ and $\sigma^2$ that yield the closest approximation to a $t_5$ distribution. Say such an approximation technique yield $\mu = 0.05$ and $\sigma^2 = 4$. So my variantional approximation to $t_5$ distribution is a $N(0.05, 4)$ distribution, and the estimate of the mean is then the mean of this normal distribution, which is 0.05. There is no variability here, and the answer is deterministic. However, if we change the class of distributions, we can get a completely different answer.
