Computational foundations: factorization, KL, and optimization

If $P\ll ̸Q$, [F1] gives $D(P\mathrm{\parallel }Q)=+\mathrm{\infty }$. If $P\ll Q$ but $D(P\mathrm{\parallel }Q)=+\mathrm{\infty }$, nonnegativity is immediate. It remains to consider $P\ll Q$ with finite divergence; let $r=dP\mathrm{/}dQ$.

Put $\phi (0)=0$ and $\phi (t)=t\log t$ for $t>0$. By [F5] and [F7], ${\phi }^{\mathrm{\prime }\mathrm{\prime }}(t)=1\mathrm{/}t>0$ for $t>0$, so [F8] makes $\phi$ convex on $(0,\mathrm{\infty })$. Its continuity at zero is part of [F1]; taking limits in the convexity inequality as a positive endpoint tends to zero extends convexity to $[0,\mathrm{\infty })$.

Define $g(t):=t\log t-t+1$ for $t>0$ and $g(0):=1$. For $s>1$, set $c=(1+s)\mathrm{/}2$. By [F11], $\log s={\int }_1^{c}du\mathrm{/}u+{\int }_c^{s}du\mathrm{/}u$. On $[1,c]$, $1\mathrm{/}u\le 1$, while on $[c,s]$, $1\mathrm{/}u\le 1\mathrm{/}c<1$; [F9] and [F24] give $\log s<s-1$. For $0<s<1$, set $c=(1+s)\mathrm{/}2$. By [F11], $\log s=-{\int }_s^{1}du\mathrm{/}u=-({\int }_s^{c}du\mathrm{/}u+{\int }_c^{1}du\mathrm{/}u)$. On $[s,c]$, $1\mathrm{/}u\ge 1\mathrm{/}c>1$, and on $[c,1]$, $1\mathrm{/}u\ge 1$; [F9] and [F24] give $\log s<s-1$. The integrands and comparison constants are integrable on these compact intervals by [F10]. Equality holds at $s=1$. Applying this inequality to $s=1\mathrm{/}t$ and using [F6] gives $t\log t\ge t-1$, strictly unless $t=1$. Hence $g\ge 0$ and its only zero is $1$.

For the normalized-density clause on the measure space [F13], put $P:=q\mu$ and $Q:=\pi \mu$. By [F17], $\int \pi d\mu =Z^{-1}\int \gamma d\mu =1$; hence [F15] and [F14] make $P$ and $Q$ probability measures.

If $Q(E)=0$, [F15] gives ${\int }_E\pi d\mu =0$, hence ${\int }_E\gamma d\mu =0$ because $Z$ is finite and positive, using [F17]. By [F12], $\gamma =0$ $\mu$-almost everywhere on $E$. The support hypothesis on $q$ then gives $P(E)=0$, so $P\ll Q$. Define $\rho :[0,\mathrm{\infty }]\to [0,\mathrm{\infty }]$ by $\rho (t)=1\mathrm{/}t$ for finite $t>0$ and $\rho (0)=\rho (+\mathrm{\infty })=0$. For $a<0$, $\{\rho >a\}=[0,\mathrm{\infty }]$; for $a=0$ it is $(0,\mathrm{\infty })$; and for $a>0$ it is $(0,1\mathrm{/}a)$. These are Borel by [F18], so [F19] makes $\rho$ Borel. By [F20]–[F21], $r:=q\rho (\pi )$ is measurable and equals $q\mathrm{/}\pi$ on $\{\pi >0\}$ and zero on $\{\pi =0\}$. For every measurable $E$, [F16] gives ${\int }_{E}rdQ={\int }_{E}r\pi d\mu ={\int }_{E}qd\mu =P(E),$ because $q=0$ $\mu$-almost everywhere on $\{\pi =0\}$. Thus $r=dP\mathrm{/}dQ$.

By [F2] with $E$ equal to the whole space, $\int rdQ=P(\mathrm{\Omega })=1$. The negative part of $r\log r$ is finite by [F1], so finiteness of $D(P\mathrm{\parallel }Q)$ also makes its positive part finite. Thus $r$ and $r\log r$ are integrable with respect to the probability measure $Q$. The Radon–Nikodym representative here is the one whose selection is covered by [A1].

On the $P$-full-measure subset of $\{q>0\}$ where $\gamma >0$, we have $\pi =\gamma \mathrm{/}Z>0$ and $\mathrm{\ell }:=\log r=\log q-\log \gamma +\log Z$. Where $q=0$, the KL logarithm $\mathrm{\ell }$ is defined to be zero. By [F23], $q\mathrm{\mid }\mathrm{\ell }\mathrm{\mid }\le q\mathrm{\mid }\log q\mathrm{\mid }+q\mathrm{\mid }\log \gamma \mathrm{\mid }+q\mathrm{\mid }\log Z\mathrm{\mid }$ almost everywhere. The right-hand side has finite integral by the hypotheses and $\int q=1$; hence [F16] gives $\int \mathrm{\mid }\mathrm{\ell }\mathrm{\mid }dP=\int q\mathrm{\mid }\mathrm{\ell }\mathrm{\mid }d\mu <\mathrm{\infty }$. By [F1], [F16], and [F22], applying [F16] to the positive and negative parts of $\mathrm{\ell }$ gives $D(P\mathrm{\parallel }Q)=\int \log rdP=\int q(\log q-\log \gamma +\log Z)d\mu \mathrm{.}$ Using $\int qd\mu =1$ and rearranging proves the identity.

Apply [F3] on $(\mathrm{\Omega },\mathcal{A},Q)$ to $r$ and $\phi$. Steps 2.1 and 1.2 check its integrability and convexity hypotheses, and $\int rdQ=1$ by step 2.1. Therefore $0=\phi (1)=\phi \text{\hspace{0.17em}⁣}(\int rdQ)\le \int \phi (r)dQ=D(P\mathrm{\parallel }Q)\mathrm{.}$

The representative $r$ is finite-valued and measurable by [F1], and $\phi (r)$ is measurable there; the arithmetic measurability result [F21] therefore makes $g(r)=\phi (r)-r+1$ measurable. It is nonnegative by step 1.3. By step 2.1, $r,\phi (r)\in L^1(Q)$, and $1\in L^1(Q)$ because $Q$ is a probability measure. Linearity [F25] now gives $g(r)\in L^1(Q)$ and $\int g(r)dQ=\int \phi (r)dQ-\int rdQ+\int 1dQ=D(P\mathrm{\parallel }Q)-1+1=D(P\mathrm{\parallel }Q)\mathrm{.}$ Thus if $D(P\mathrm{\parallel }Q)=0$, [F12] applies to the measurable nonnegative integrand and gives $g(r)=0$ $Q$-almost everywhere. By step 1.3, $r=1$ $Q$-almost everywhere, and the Radon–Nikodym identity [F2] gives $P(E)=Q(E)$ for every measurable $E$. Conversely, if $P=Q$ then $r=1$ almost everywhere and [F1] gives $D(P\mathrm{\parallel }Q)=0$.

Step 2.2 identifies the normalized-density divergence as finite, and step 3.1 proves it is nonnegative. Therefore $\int q(\log \gamma -\log q)d\mu \le \log Z$, as claimed.

Fix $\theta$ and let ${\mathcal{D}}_{\theta }$ be the collection of subsets $E\subseteq \mathrm{\Theta }\times \mathsf{X}\times \mathsf{Z}$ whose section $E_{\theta }:=\{(x,z):(\theta ,x,z)\in E\}$ belongs to $\mathcal{A}\otimes \mathcal{C}$. Sections commute with complements and countable unions, so ${\mathcal{D}}_{\theta }$ is a sigma-algebra. It contains each measurable rectangle $T_0\times A_0\times C_0$, whose section is $A_0\times C_0$ if $\theta \in T_0$ and empty otherwise. By [F12], every product-measurable set has a measurable section. Applying this to preimages of Borel sets shows that $p_{\theta }(x,z):=p(\theta ,x,z)$ is product-measurable. For complex $h$, first compose with the continuous Borel coordinate maps $\mathrm{Re},\mathrm{Im}:\mathbb{C}\to \mathbb{R}$; the same section argument makes both $\mathrm{Re}{h}_{\theta }$ and $\mathrm{Im}{h}_{\theta }$ measurable, hence $h_{\theta }$ is complex-measurable.

By [F13], choose a measurable exhaustion $Z_n\uparrow \mathsf{Z}$ with $\mu (Z_n)<\mathrm{\infty }$. On $S:=\mathrm{\Theta }\times \mathsf{X}$, the constant assignment $K(s,B):=\mu (B)$ is a measure kernel: each section is $\mu$ and each evaluation map is constant. The same exhaustion makes it uniformly sigma-finite by [F2].

For fixed $\theta$, step 1.1 makes $p_{\theta }$ product-measurable, so Tonelli [F4] gives ${\int }_{\mathsf{X}}m(\theta ,x)\nu (dx)={\int }_{\mathsf{X}\times \mathsf{Z}}{p}_{\theta }(x,z)d(\nu \otimes \mu )=1$ by [F1]. Thus $m(\theta ,\cdot )$ is a probability density. Also $E_{\theta }:=\{(x,z):p_{\theta }(x,z)=\mathrm{\infty }\}$ is measurable. For every positive integer $n$, $n{\mathbf{1}}_{E_{\theta }}\le p_{\theta }$, so [F6] gives $n(\nu \otimes \mu )(E_{\theta })\le 1$. Since this holds for every $n$, [F7] implies $(\nu \otimes \mu )(E_{\theta })=0$.

The function $p$ is nonnegative and product-measurable by [F1]. Under the finite-product identification $S\times \mathsf{Z}=(\mathrm{\Theta }\times \mathsf{X})\times \mathsf{Z}$ from [F12], apply [F3] to the constant kernel $K$ from step 1.2. It follows that $s\mapsto \int p(s,z)\mu (dz)=m(s)$ is measurable on $S$.

For fixed $\theta$, write $u_{\theta }=\mathrm{Re}{h}_{\theta }$ and $v_{\theta }=\mathrm{Im}{h}_{\theta }$. Define the finite-valued measurable function ${\tilde{p}}_{\theta }:=p_{\theta }{\mathbf{1}}_{\{p_{\theta }<\mathrm{\infty }\}}$ and then $H_{\theta }:=u_{\theta }{\tilde{p}}_{\theta }+i{v}_{\theta }{\tilde{p}}_{\theta }\mathrm{.}$ By [F11] this is complex-valued product-measurable; it is defined to be zero on the null set where $p_{\theta }=\mathrm{\infty }$. It agrees with $h_{\theta }{p}_{\theta }$ off that null set, and the assumed absolute integrability gives $\int \mathrm{\mid }{H}_{\theta }\mathrm{\mid }d(\nu \otimes \mu )<\mathrm{\infty }$. Fubini [F5] applies to this $L^1$ representative and gives ${\int }_{\mathsf{X}\times \mathsf{Z}}{H}_{\theta }d(\nu \otimes \mu )={\int }_{\mathsf{X}}({\int }_{\mathsf{Z}}{H}_{\theta }(x,z)\mu (dz))\nu (dx)={\int }_{\mathsf{Z}}({\int }_{\mathsf{X}}{H}_{\theta }(x,z)\nu (dx))\mu (dz),$ with its zero assignment on exceptional null sections. Since $H_{\theta }=hp$ almost everywhere on the fixed-$\theta$ product space, these are the asserted exchanges for $hp$.

Let $E:=\{x:m(\theta ,x)=\mathrm{\infty }\}$, measurable by step 2.2. For each positive integer $n$, $n{\mathbf{1}}_E\le m(\theta ,\cdot )$, so [F6] and step 2.1 give $n\nu (E)\le 1$. Since this holds for every $n$, [F7] forces $\nu (E)=0$. If $0<m(\theta ,x)<\mathrm{\infty }$, division by that scalar and the definition of $m$ give $\int q(z\mid \theta ,x)\mu (dz)=m(\theta ,x)\mathrm{/}m(\theta ,x)=1$. The valid-fibre set $V=m^{-1}((0,\mathrm{\infty }))$ is measurable by step 2.2 and [F8]. For measurability, define $\rho :[0,\mathrm{\infty }]\to [0,\mathrm{\infty }]$ by $\rho (t)=1\mathrm{/}t$ for finite $t>0$ and $\rho (0)=\rho (+\mathrm{\infty })=0$. For $a<0$, $\{\rho >a\}=[0,\mathrm{\infty }]$; for $a=0$ it is $(0,\mathrm{\infty })$; and for $a>0$ it is $(0,1\mathrm{/}a)$. These sets are Borel by [F8], so [F9] makes $\rho$ Borel. By [F10], $\rho \circ m$ is measurable on $\mathrm{\Theta }\times \mathsf{X}$. Pulling it back along the measurable coordinate projection from the finite product space, which is measurable by [F12], gives a product-measurable function; multiplying by $p$ preserves measurability by [F11]. This product restricts to $q=p\mathrm{/}m$ on $V\times \mathsf{Z}$, so $q$ is measurable on the valid-fibre set.

Steps 2.2, 2.1, 3.2, and 3.1 prove the marginal measurability, normalization, valid-fibre density, and integrable-exchange clauses.

By linearity of $Df(x)$ and its values on the standard basis, $Df(x)[p]=⟨\mathrm{\nabla }f(x),p⟩$. In the gradient branch, if $\mathrm{\nabla }f(x)\mathrm{\ne }0$, then $Df(x)[-\mathrm{\nabla }f(x)]=-\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}^2<0$ by [F1]. In the Newton branch, write $g=\mathrm{\nabla }f(x)$ and $Hp=-g$. If $g\mathrm{\ne }0$, then $p\mathrm{\ne }0$ by [F4] and $Df(x)[p]=g^{T}p=-p^{T}Hp<0$, since $H$ is symmetric positive definite by [F2] and [F4].

Set $d:=-Df(x)[p]>0$. Fréchet differentiability gives $[f(x+tp)-f(x)]\mathrm{/}t\to -d$ as $t\downarrow 0$. Choose $\delta >0$ small enough that $x+tp\in U$ and this quotient is less than $-d+(1-\alpha )d\mathrm{/}2=-(1+\alpha )d\mathrm{/}2\le -\alpha d$ whenever $0<t<\delta$. Then every such trial satisfies the Armijo test.

The trials are $t_n={\beta }^n$. Put $c={\beta }^{-1}-1>0$. By [F5], ${\beta }^{-n}=(1+c{)}^n\ge 1+nc$, hence $t_n\le (1+nc{)}^{-1}$. By [F6], for any $\delta >0$ some $n$ is large enough that $(1+nc{)}^{-1}<\delta$; thus $t_n\to 0$.

Step 1.2 supplies a positive interval of accepted trial sizes. The geometric sequence shown in step 1.3 eventually tests such a size, so the prescribed loop accepts after finitely many reductions in either algorithm.

Fix $x$ and write $g:=\mathrm{\nabla }f(x)$ and $d:=-g\mathrm{/}L$. Define $\varphi (s):=f(x+sd)$ on $[0,1]$. By [F2]–[F3], ${\varphi }^{\mathrm{\prime }}(s)=⟨\mathrm{\nabla }f(x+sd),d⟩$ on $(0,1)$. The gradient is continuous by [A1], so ${\varphi }^{\mathrm{\prime }}$ is continuous and integrable by [F4]. Applying [F5] gives $f(x-g\mathrm{/}L)-f(x)=-\frac{1}{L}{\int }_0^1⟨\mathrm{\nabla }f(x-sg\mathrm{/}L),g⟩ds\mathrm{.}$ By [A1] and [F6], $\mathrm{\parallel }\mathrm{\nabla }f(x-sg\mathrm{/}L)-g\mathrm{\parallel }\le s\mathrm{\parallel }g\mathrm{\parallel }$, whence $⟨\mathrm{\nabla }f(x-sg\mathrm{/}L),g⟩\ge (1-s)\mathrm{\parallel }g{\mathrm{\parallel }}^2$. Integrating this bound gives $f(x-g\mathrm{/}L)\le f(x)-\frac{\mathrm{\parallel }g{\mathrm{\parallel }}^2}{2L}\mathrm{.}$

By [A2], for every $y$, $f(y)\ge f(x)+⟨g,y-x⟩+\frac{\mu }{2}\mathrm{\parallel }y-x{\mathrm{\parallel }}^2=f(x)-\frac{\mathrm{\parallel }g{\mathrm{\parallel }}^2}{2\mu }+\frac{\mu }{2}{\parallel y-x+\frac{g}{\mu }\parallel }^2\mathrm{.}$ Taking $y=x^{\ast }$ and using nonnegativity of the square yields $\mathrm{\parallel }g{\mathrm{\parallel }}^2\ge 2\mu (f(x)-f^{\ast })$.

Apply steps 1.1 and 1.2 at $x=x_k$ and use [F1]. Then $f(x_{k+1})-f^{\ast }\le f(x_k)-f^{\ast }-\frac{\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}^2}{2L}\le (1-\frac{\mu }{L})(f(x_k)-f^{\ast })\mathrm{.}$ The factor is nonnegative because $\mu \le L$.

The $k=0$ case is equality. For $k=1$, the result is step 2.1 whenever $x_1$ is generated. If $x_{k+1}$ is generated, then $x_k$ was generated and the algorithm made the $k$th update; multiplying the bound at $k$ by $1-\mu \mathrm{/}L\ge 0$ and applying step 2.1 proves it at $k+1$. Induction along generated iterates gives the claim for every generated $k\ge 1$. If the stopping rule fires earlier, no later iterate is asserted.