Exact coordinate updates are monotone and finite sweeps have a call bound

Fix any admissible replacement $r_j$ and form $u=r_j{q}_{-j}$. Tonelli [F5] gives $\int ud\mu =1$, and the product rectangle formula [F4] gives ${\mathbb{P}}_u:=u\mu ={⨂}_{k=1}^m(u_k{\mu }_k)$ is the product probability. Each coordinate density $u_k$ is positive and finite almost surely under its factor law; put $X_k=\log u_k(Z_k)$ and $S=\log u(Z)={\sum }_{k=1}^m{X}_k$. By [F1], ${\mathbb{E}}_u\mathrm{\mid }S\mathrm{\mid }=\int u\mathrm{\mid }\log u\mathrm{\mid }d\mu <\mathrm{\infty }$. Fix $j$ and put $R={\sum }_{k\mathrm{\ne }j}{X}_k$, which is finite almost surely under the product of the other factor laws. Since $\{\mathrm{\mid }R\mathrm{\mid }\le n\}$ increases to a full-measure set, choose an integer $K$ for which $p:={\mathbb{P}}_u(\mathrm{\mid }R\mathrm{\mid }\le K)>0$. Product integration from [F5] and [F6] then gives $p\int u_j\mathrm{\mid }\log u_j\mathrm{\mid }d{\mu }_j={\int }_{\{\mathrm{\mid }R\mathrm{\mid }\le K\}}\mathrm{\mid }{X}_j\mathrm{\mid }d{\mathbb{P}}_u\le \int \mathrm{\mid }S\mathrm{\mid }d{\mathbb{P}}_u+Kp<\mathrm{\infty }$, using $\mathrm{\mid }{X}_j\mathrm{\mid }\le \mathrm{\mid }S\mathrm{\mid }+\mathrm{\mid }R\mathrm{\mid }$ on that event. Thus every factor log is integrable; the same argument applies to the current factor and to $q_j^{\ast }$ because their products are admissible.

For each admissible replacement $u_j$, [F1] makes $u\log \gamma$ absolutely integrable. Fubini [F7] applies also to $u\mathrm{\mid }\log \gamma \mathrm{\mid }$, so $\int u_j\mathrm{\mid }{h}_j\mathrm{\mid }d{\mu }_j<\mathrm{\infty }$ and exchanging the $j$ and $-j$ integrals gives $\int u\log \gamma d\mu =\int u_j{h}_{j}d{\mu }_j$. By step 1.1, all factor log terms are integrable, so $\log u=\log u_j+\log q_{-j}$ almost surely and $\mathrm{ELBO}(u_j{q}_{-j})=\int u_j{h}_{j}d{\mu }_j-\int u_j\log u_{j}d{\mu }_j-\int q_{-j}\log q_{-j}d{\mu }_{-j}$. The final term is constant over coordinate replacements.

Write $q_j^{\ast }=e^{h_j}\mathrm{/}{c}_j$. If $q_j^{\ast }=0$, then $h_j=-\mathrm{\infty }$ almost everywhere on that set. For any admissible $r_j$, step 2.1 makes $\int r_j\mathrm{\mid }{h}_j\mathrm{\mid }d{\mu }_j<\mathrm{\infty }$, hence $r_j=0$ almost everywhere there. Thus $r_j{\mu }_j\ll q_j^{\ast }{\mu }_j$. On $\{q_j^{\ast }>0\}$ the ratio $r_j\mathrm{/}{q}_j^{\ast }$ is measurable, and for every measurable $A$, ${\int }_A(r_j\mathrm{/}{q}_j^{\ast })d(q_j^{\ast }{\mu }_j)={\int }_{A\cap \{q_j^{\ast }>0\}}{r}_{j}d{\mu }_j={\int }_A{r}_{j}d{\mu }_j$, so it is the Radon–Nikodym density.

By [A1] and [F8], $D(r_j{\mu }_j\mathrm{\parallel }{q}_j^{\ast }{\mu }_j)=\int r_j\log (r_j\mathrm{/}{q}_j^{\ast })d{\mu }_j=\int r_j\log r_{j}d{\mu }_j-\int r_j{h}_{j}d{\mu }_j+\log c_j$. All terms are finite by step 1.1 and step 2.1. Also $\int q_j^{\ast }{h}_j-\int q_j^{\ast }\log q_j^{\ast }=\log c_j$. Subtracting the ELBO expressions in step 2.1 therefore gives $\mathrm{ELBO}(q_j^{\ast }{q}_{-j})-\mathrm{ELBO}(r_j{q}_{-j})=D(r_j{\mu }_j\mathrm{\parallel }{q}_j^{\ast }{\mu }_j)\ge 0$ by [F9]. Hence $q_j^{\ast }$ is an attained exact coordinate maximizer.

The current factor $q_j$ is itself an admissible replacement. Taking $r_j=q_j$ in step 3.2 proves that the update does not decrease ELBO.

By [F3], the procedure has at most $N$ sweeps and at most $m$ coordinate-update blocks in each sweep. An unavailable result returns immediately, so every run is either a prefix ending at that branch or a run through all $N$ sweeps. Since $N$ and $m$ are finite, under [A2] it returns after at most $Nm$ calls. The call-count complexity is therefore $O(Nm)$; no cost for evaluating an individual call is asserted.