Fixed point iterations for expectation propagation using energy minimization

Question

EP Primal

In 1, it is finding the EP iterations by solving a saddle-point problem on the energy function. First, the primal is claimed to be $$ \min_{\hat{p}_i} \max_{q} \left[ \sum_i \int_{\mathbf{y}} \hat{p}_i(\mathbf{y}) \log \frac{ \hat{p}_i(\mathbf{y}) }{ t_i(\mathbf{y}) p(\mathbf{y}) } d\mathbf{y}‎ - ‎(n-1) \int_\mathbf{y} q_\theta(\mathbf{y}) \log \frac{q_\theta(\mathbf{y})}{p(\mathbf{y})} d\mathbf{y} \right]‎ $$ ‎with the local moment matching constraints $$ ‎\mathbb{E}_{ q_\theta(\mathbf{y}) }\left[ \phi(\mathbf{y}) \right] = \mathbb{E}_{ \hat{p}_i(\mathbf{y} ) }\left[ \phi(\mathbf{y}) \right]‎, ‎\forall i \quad \quad ‎$$

EP Dual

The dual energy function is the following; $$ ‎\min_{\nu} \max_{\lambda} \left[ (n-1) \log \int_\mathbf{y} p(\mathbf{y}) \exp \left( \nu^\top \phi(\mathbf{y}) \right) d\mathbf{y}‎ - ‎\sum_{i=1}^{n} \log \int_\mathbf{y} \hat{t}_i(\mathbf{y}) p(\mathbf{y}) \exp \left( {\lambda_i}^\top \phi (\mathbf{y}) \right) d\mathbf{y} \right]‎, $$ $$ ‎(n-1) \nu = \sum_i \lambda_i‎. $$

EP fixed point iterations

And using the dual energy function, we should be able to find the fixed point iterations:

Message elimination: Choose a $\tilde{t}_i$ to do approximation with‎. ‎

‎Remove the factor $\tilde{t}_i$ from approximation‎, ‎$\; q_\theta^{-i} = \displaystyle \frac{q_\theta}{ \tilde{t}_i }$ ‎ Belief projection: Project the approximate posterior‎, ‎with $\tilde{t}_i$ replaced with $t_i$‎, ‎on the approximating family‎, ‎$$‎ ‎q^{new}_\theta(\mathbf{y}) = \text{proj}\left( \hat{p}_i(\mathbf{y}) \rightarrow q_\theta(\mathbf{y}) \right)‎, ‎$$‎ ‎where‎, ‎$$‎ ‎\hat{p}_i(\mathbf{y}) = \frac{1}{Z} q_\theta^{-i}(\mathbf{y}) t_i(\mathbf{y})‎, ‎\; \; Z = \int q_\theta^{-i}(\mathbf{y}) \times t_i(\mathbf{y}) d\mathbf{y}‎ ‎$$‎

$‎ \tilde{t}_i = \arg \min_{\tilde{t}_i} \text{KL} \left( \displaystyle \frac{ t_i \prod_{j\neq i} \tilde{t}_j }{ \int t_i \prod_{j \neq i} \tilde{t}_j } \parallel q_\theta(\mathbf{y}) \right) $. ‎

Message update: Compute the new approximating factor‎, ‎$$‎ ‎\tilde{t}_i = Z \frac{ q^{new}_\theta(\mathbf{y}) }{ q_\theta^{-i}(\mathbf{y})‎ } ‎$$‎

Here are the questions:

1. I know how how to derive dual from primal, but it it not clear to me where the primal is coming from.
2. I don't see how can I find the EP iterations from Dual. Any idea?

Answer 1

As far as I can tell, the EP energy function is a bit of a red herring for understanding EP.

Usually, an "energy function" of some iteration decreases at each step (or at least, the update direction is a direction of descent) so that the existence of an energy function (sometimes called a Lyapunov) guarantees that our iteration doesn't move all over the place.

In sharp contrast, the EP energy doesn't have that property. The only property linking the EP energy and the EP iterations is that critical-points (gradient = 0) of the EP energy are also fixed-points of the EP iteration. This isn't a very useful property so I'd rather call the EP energy a pseudo-energy, but that's my own choice.

The one useful property of the EP energy is that it is the quantity you want to use to approximate the normalizing the constant $\int p(x)$ of the target distribution:

$$ \log ( \int p ) \approx \sum \log (\int h_i) - (n-1) \log (\int q) $$

The idea there is quite simple: consider an EP fixed-point $(q_i)_{i \in [1,n]}$ approximating $p = \prod p_i$. You have already found the "Gaussian influence" of each term, and you know want to compute the influence of each $p_i$ on $\int p$. The easiest way is to compare the integral $\int p_i q_{-_i}$ to what it should be: $\int q_i q_{-i}$. Now you multiply all those terms, AND you remember to add an additional $\int \prod q_i$. You finally get:

$$ \int p \approx ( \prod_i \frac\int {p_i q_{-_i}}{\int \prod q_i} ) * \int \prod q_i $$

and that's how the EP pseudo-energy is an approximation of $\log \int p$