Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 216 / 4

Write $\pi (x)=\mu (x\mid y)$. Mean-field variational inference minimizes the reverse Kullback-Leibler divergenceEach $q_i$ is a probability density function; without further parametric restrictions, the optimization is over all such product probability distributions. Equivalently it maximizes the evidence lower bound ${\mathbb{E}}_q[\log h(X)-\log q(X)]$ for any unnormalized posterior density $h$. Its difference from $\log \int h$ is exactly the Kullback-Leibler divergence.

Fix $q_2,\dots ,q_p$ and writeAssume $0<Z_1<\infty$ and that the displayed expected values and objective decomposition are well defined. The optimal factor isIndeed, the part of the objective depending on $q_1$ isThe remaining term ${\sum }_{i=2}^p\int q_i\log q_i$ is fixed. Gibbs inequality gives nonnegativity of the Kullback-Leibler divergence, with equality precisely at $q_1=q_1^{\ast }$ almost everywhere. This proves global optimality of that coordinate update; it does not assert global optimality of a sequence of coordinate updates for the full nonconvex product-family problem.

The printed upper index $k$ in the list of remaining coordinates is inconsistent with the dimension $p$; the natural interpretation is $k=p$. Also, if the exponential expression has zero or infinite normalizing constant, or the expected values are undefined, the usual coordinate formula needs additional support or integrability hypotheses. A restricted parametric factor family need not contain this unrestricted optimal factor.

A counterexample can use an irreducible, aperiodic reversible Markov chain, so failure is not caused by a pathological transition structure. Take two binary coordinates, enumerate the four states as $00,01,10,11$, and let $\pi$ be their uniform distribution. Use the Markov kernelIts rows sum to one and it is symmetric, proving detailed balance with $\pi$. Every entry is positive. Let the univariate parametric family be $\tilde{\mathcal{Q}}=\{\mathrm{Bernoulli}(r):0\le r\le 2/5\}$.

For a product initial probability distribution with parameters $r_1,r_2$, additivity of the Kullback-Leibler divergence givesEach summand has derivative $\log (r_i/(1-r_i))<0$ on $(0,2/5]$, so the unique optimum at $t=0$ has $r_1=r_2=2/5$. ThusOn the other hand the allowed initial probability distribution ${\delta }_{00}$, obtained with $r_1=r_2=0$, is sent by one step to $\pi$. Its Kullback-Leibler divergence is zero, the smallest possible value. ConsequentlyThe transition reduces Kullback-Leibler divergence for each input, but may reduce it by different amounts for different inputs. It therefore need not preserve the ordering of competing initial probability distributions, which is exactly why Markov chain variational inference must optimize the initial parameters for its chosen number of steps.

Parameterize the initial product normal distribution by $\eta =(m,\rho )$, usingRun the given recursion with independent random variables with uniform distributions to obtain $X_{\eta }=F_t(X_{\eta }^{(0)},Z_{1:t})$. Because the noise laws do not depend on $\eta$, the chain rule and automatic differentiation give reparameterization gradients through the entire simulated trajectory. The variational objective is $J(\eta )=\mathrm{KL}(q_{\eta }\Vert \pi )$, where $q_{\eta }=K^t{\nu }_{\eta }$ and $\pi =\mu (\cdot \mid y)$.

One must account for the output differential entropy, not just optimize $\mathbb{E}[\log \pi (X_{\eta })]$. Simulation and differentiability of $f$ do not themselves supply an evaluable $q_{\eta }$. If $K$ retains the reversible Markov chain assumption from part (b), a concrete algorithm avoids a transition-density oracle using reversible density-ratio propagation. Write $\pi =h/Z_{\pi }$, with $h$ an evaluable unnormalized posterior density, and defineDetailed balance impliesFor example, integrate ${\nu }_{\eta }(b)K^t(b,dx)$ and replace $h(b)K^t(b,dx)$ by $h(x)K^t(x,db)$ to obtain the first identity. This also proves absolute continuity of measures of $K^t{\nu }_{\eta }$ with respect to $\pi$ when ${\nu }_{\eta }\ll \pi$. An everywhere finite differentiable log-posterior has positive density, so an ordinary product normal distribution has this domination.

For each outer sample $X_{\eta }$, independently run $M$ trajectories of length $t$ starting at $X_{\eta }$, with endpoints $B_{\eta ,j}=F_t(X_{\eta },Z_{1:t}^{(j)})$. These are reverse trajectories because of detailed balance; the same recursion simulates them. Estimate $A_{\eta }(X_{\eta })$ byAverage $\log \hat{A}$ over an outer batch. Compute it stably by a logarithmic sum of exponentials. Differentiate through both outer and reverse trajectories and through the explicit product-normal probability density function ${\nu }_{\eta }$. Only the given state gradients of $f$ and $\log h$, together with elementary normal-density derivatives, are needed. Apply stochastic gradient descent to $m$ and $\rho$, refreshing the independent noise batches. The logarithmic scale parameters keep all variances positive.

This is nested Monte Carlo optimization of the exact objective in the limit of adequately increasing inner and outer sample sizes. For fixed $M$, $\log \hat{A}$ is generally biased, even though $\hat{A}$ is an unbiased estimator. Finite logarithmic moments, suitable uniform integrability, and justified differentiation under the integral sign are needed for consistency and gradient interchange. Under those conditions increasing $M$ and controlling the optimization error yields a justified numerical approximation; nonconvexity prevents a generic guarantee of a global optimum.

There is a real assumption issue: part (c) redefines $K$ without explicitly restating reversibility. The algorithm above uses the reversible interpretation inherited from part (b). For an arbitrary differentiable recursion, one additionally needs access to output densities or a simulatable reverse kernel and regularity of the objective. Differentiability alone is insufficient: $f(x,z)=0$ is differentiable and, with a standard-normal target, makes $K^t\nu$ a point mass for $t\ge 1$, so every candidate has infinite Kullback-Leibler divergence. Thus a universal finite-objective algorithm cannot be justified solely from the literal differentiability assumptions. An invertible recursion with computable density transformations offers a different sufficient route, but invertibility is not stated here.