At a Glance

Coordinate maximization of $$\begin{array}{rlrl}& \underset{{\mu }_0,[{\mu }_i,{\nu }_i,{\theta }_i^{\prime }{]}_{i=1}^n}{max}& & \{⟨{\mu }_0,{\theta }_0⟩+\sum _{i=1}^n⟨{\nu }_i,1⟩-A^{\ast }({\mu }_0)-\sum _{i=1}^n{\beta }_i[A^{\ast }({\mu }_i,{\nu }_i)+A({\theta }_i^{\prime })-{\mu }_i^{\mathrm{\top }}{\theta }_i^{\prime }]\}\\ & \text{s.t.}& & ({\mu }_i,{\nu }_i)\in \mathcal{M}(s(x),{\ell }_i(x))& \mathrm{\forall }i=1,\dots ,n\\ & & & {\mu }_i={\mu }_0& \mathrm{\forall }i=1,\dots ,n\\ & & & {\mu }_0\in \mathcal{M}(s(x))\\ & & & {\theta }_i^{\prime }\in \mathrm{\Theta }\end{array}$$

Context

In Hasenclever et al. (2017) the prior is in the base exponential family $$p_0(x)=\exp ({\theta }_0^{\mathrm{\top }}s(x)-A({\theta }_0))$$ Each node $i=1,\dots ,n$ has a partition of the data. Local likelihood ${\ell }_i(x)$ can be formed $${\ell }_i(x)=\sum _{c\in S_i}\log p(y_c\mid x)$$ Posterior can be written as extended exponential family $$\tilde{p}(x)\propto p_0(x)\exp (\sum _{i=1}^n{\ell }_i(x))\propto \exp ({\tilde{\theta }}^{\mathrm{\top }}\tilde{s}(x)-\tilde{A}(\tilde{\theta }))$$ where $$\begin{array}{rlrl}\tilde{s}(x)& =[s(x),{\ell }_1(x),\dots ,{\ell }_n(x)]& & ⟺(\varphi (x),{\mathrm{\Phi }}^1(x),\dots ,{\mathrm{\Phi }}^n(x))\\ \tilde{\theta }& =[{\theta }_0,{\mathbf{1}}_n]& & ⟺(\theta ,{\tilde{\theta }}^1,\dots ,{\tilde{\theta }}^n)\end{array}$$

Aim

Want to learn the posterior distribution $\tilde{p}(x)$. Do this by finding the log-partition function and the mean parameters, which completely specify the posterior distribution. Both can be found altogether by solving the variational problem represented by the convex dual. This problem is difficult to solve, so we solve an approximated problem instead.

Variational Problem

The approximated problem that we need to solve to find the (approximated) mean parameters and the (approximated) log-partition function is $$\begin{array}{rlrl}& \underset{{\mu }_0,[{\mu }_i,{\nu }_i{]}_{i=1}^n}{max}& & \{⟨{\mu }_0,{\theta }_0⟩+\sum _{i=1}^n⟨{\nu }_i,1⟩-A^{\ast }({\mu }_0)-\sum _{i=1}^n{\beta }_i[A^{\ast }({\mu }_i,{\nu }_i)-A^{\ast }({\mu }_i)]\}\\ & \text{s.t.}& & ({\mu }_i,{\nu }_i)\in \mathcal{M}(s(x),{\ell }_i(x))& \mathrm{\forall }i=1,\dots ,n\\ & & & {\mu }_i={\mu }_0& \mathrm{\forall }i=1,\dots ,n\\ & & & {\mu }_0\in \mathcal{M}(s(x))\end{array}$$ Solving this gives an approximation to the posterior that belongs to the exponential family $$\tilde{p}(x)\propto \exp \left(⟨{\theta }_0+\sum _{i=1}^n{\lambda }_i,s(x)⟩\right)$$ Since exponential family is closed under multiplication (adding up the coefficients), we can interpret this approximation as follows. Each ${\lambda }_i$ is the natural parameter of an exponential family approximating the intractable likelihood term in site $i$ given by $\exp ({\ell }_i(x))$.

Updates

The tilted distribution in each node is given by $$p_i(x)\propto \exp (⟨{\theta }_0+\sum _{j=1}^n{\lambda }_j-\frac{{\lambda }_i}{{\beta }_i},s(x)⟩+⟨\frac{1}{{\beta }_i},{\ell }_i(x)⟩)$$ Therefore at each iteration we compute the mean parameters of the tilted distribution $$({\mathbb{E}}_{p_i}[s(X)],{\mathbb{E}}_{p_i}[{\ell }_i(X)])=({\mu }_i,{\nu }_i)$$ and then perform moment matching by adjusting ${\lambda }_i$ $${\lambda }_i^{\text{new}}⟵{\mathrm{\nabla }}_{{\mu }_i}{A}^{\ast }({\mu }_i)-{\theta }_0-\sum _{j\ne i}{\lambda }_j$$

In practice, to avoid oscillations, we add some damping $${\lambda }_i^{\text{new}}⟵\alpha {\lambda }_i+(1-\alpha )({\mathrm{\nabla }}_{{\mu }_i}{A}^{\ast }({\mu }_i)-{\theta }_0-\sum _{j\ne i}{\lambda }_j)\text{where }\alpha \in [0,1]$$ Notice that here ${\mathrm{\nabla }}_{{\mu }_i}{A}^{\ast }({\mu }_i)$ is the natural parameter corresponding to the mean parameter ${\mu }_i$.

Stochastic Natural-Gradient Expectation Propagation

The only difficult step is to compute the mean parameters of the tilted distribution $${\mathbb{E}}_{p_i}[(s(X),{\ell }_i(X)]$$ because ${\ell }_i(x)$ are intractable. For this reason, authors derive an alternative to EP and PowerEP. Basically they introduce additional auxiliary natural parameter vector ${\theta }^{\prime }$, obtaining a new variational objective function. $$\begin{array}{rlrl}& \underset{{\mu }_0,[{\mu }_i,{\nu }_i,{\theta }_i^{\prime }{]}_{i=1}^n}{max}& & \{⟨{\mu }_0,{\theta }_0⟩+\sum _{i=1}^n⟨{\nu }_i,1⟩-A^{\ast }({\mu }_0)-\sum _{i=1}^n{\beta }_i[A^{\ast }({\mu }_i,{\nu }_i)+A({\theta }_i^{\prime })-{\mu }_i^{\mathrm{\top }}{\theta }_i^{\prime }]\}\\ & \text{s.t.}& & ({\mu }_i,{\nu }_i)\in \mathcal{M}(s(x),{\ell }_i(x))& \mathrm{\forall }i=1,\dots ,n\\ & & & {\mu }_i={\mu }_0& \mathrm{\forall }i=1,\dots ,n\\ & & & {\mu }_0\in \mathcal{M}(s(x))\\ & & & {\theta }_i^{\prime }\in \mathrm{\Theta }\end{array}$$ The key is that maximizing this new objective with respect to the auxiliary variables ${\theta }^{\prime }$ yields the original problem. To solve this new variational problem they introduce Lagrange multipliers and switch to the dual problem. $$\begin{array}{rlrl}& \underset{[{\theta }_i^{\prime }{]}_{i=1}^n}{max}\underset{[{\lambda }_i{]}_{i=1}^n}{min}& & A({\theta }_0+\sum _{i=1}^n{\lambda }_i)+\sum _{i=1}^n{\beta }_i[A_i({\theta }_i^{\prime }-\frac{{\lambda }_i}{{\beta }_i},\frac{1}{{\beta }_i})-A({\theta }_i^{\prime })]\\ & \text{s.t.}& & {\theta }_i^{\prime }\in \mathrm{\Theta }\mathrm{\forall }i=1,\dots ,n\end{array}$$