Hoffman 2022 - Appendix - Hogwild Counterexample and Hessian Identity Proof

Summary

Two appendices with full arguments: (D) a two-bit XOR kernel that is exactly valid when applied one state at a time but collapses to the absorbing state $(0,0)$ when applied to both states simultaneously, showing why “hogwild” ECA is invalid; (E) a proof that ${\mathbb{E}}_p[-{\nabla }^2\log p]={\mathbb{E}}_p[(\nabla \log p{)}^{\top }\nabla \log p]$ under boundary-vanishing conditions.

Overview

These justify two design constraints of MEADS: fold-based parallel ECA (Hoffman 2022 - Ensemble-Chain Adaptation and Parallelism) and estimating the Hessian from gradients (Hoffman 2022 - MEADS Heuristics - Step Size, Damping, Drift and Eigenvalue Estimation).

Main Content

Appendix D: hogwild adaptation fails

Two independent uniform bits $x_0,x_1\in \{0,1\}$, $p(x)=\frac{1}{4}$. Kernel for updating one state given the other: $x_i^{\prime }=\text{XOR}(x_i,x_{1-i})$.

• One at a time is valid. Holding $x_{1-i}$ fixed, the two possible maps ($\text{XOR}(x_i,0)=x_i$ and $\text{XOR}(x_i,1)=1-x_i$) are both reversible with respect to the uniform distribution, so alternating updates leave the uniform distribution invariant.
• Simultaneous (hogwild) is wrong. $x_0^{\prime }=\text{XOR}(x_0,x_1)=x_1^{\prime }$, so after one iteration the two states are identical; another iteration sends both to 0 ($\text{XOR}(0,0)=\text{XOR}(1,1)=0$). After two iterations the chain is stuck in absorbing state $x_0=x_1=0$.
• The one-at-a-time chain is neither ergodic nor aperiodic, which can be fixed by occasionally (probability 0.01) applying a kernel that resamples $x_0,x_1$ uniformly; the hogwild version then still has a stationary distribution heavily biased toward $x_0=x_1=0$ since resampling is rare.

import random
def run(hogwild, steps=20000, p_reset=0.01):
    x=[random.randint(0,1), random.randint(0,1)]; zeros=0
    for _ in range(steps):
        if random.random()<p_reset: x=[random.randint(0,1), random.randint(0,1)]
        elif hogwild: x=[x[0]^x[1], x[1]^x[0]]
        else:
            i=random.randint(0,1); x[i]=x[i]^x[1-i]
        zeros += (x==[0,0])
    return zeros/steps
print(run(False), run(True))   # about 0.26 vs about 0.99: hogwild is badly biased

(The snippet is a direct implementation of the appendix description; the one-at-a-time version targets 0.25 for the state $(0,0)$.)

Appendix E: expected negative Hessian equals expected score outer product (eq. 10)

Let $p$ be twice differentiable almost everywhere and continuous, with $p({\theta }_i\mid {\theta }_{\setminus i})\to 0$ as $|{\theta }_i|\to \infty$ for each $i$. Then

$$-\int p(\theta ){\nabla }^2\log p(\theta )d\theta =\int p(\theta )(\frac{\partial \log p}{\partial \theta }{)}^{\top }\frac{\partial \log p}{\partial \theta }d\theta .$$

Proof. Since ${\nabla }^{2}p=\frac{\partial }{\partial \theta }(p\nabla \log p)=p[(\partial \log p/\partial \theta {)}^{\top }(\partial \log p/\partial \theta )+{\nabla }^2\log p]$ (eq. 11), it suffices to show $\int {\nabla }_{{\theta }_i,{\theta }_j}^{2}pd\theta =0$ for all $i,j$. For $i\ne j$: write $\int {\nabla }_{{\theta }_i}{\nabla }_{{\theta }_j}pd\theta =\int p({\theta }_{\setminus i,j})\int {\nabla }_{{\theta }_i}p({\theta }_i\mid {\theta }_{\setminus i,j})[{\int }_{-\infty }^{\infty }{\nabla }_{{\theta }_j}p({\theta }_j\mid {\theta }_{\setminus j})d{\theta }_j]\cdots =0$, because ${\int }_{-\infty }^{\infty }{\nabla }_{{\theta }_j}p({\theta }_j\mid {\theta }_{\setminus j})d{\theta }_j=0$ by the fundamental theorem of calculus and the vanishing boundary condition. For $i=j$: $\int {\nabla }_{{\theta }_i}{\nabla }_{{\theta }_i}pd\theta =\int p({\theta }_{\setminus i}){\int }_{-\infty }^{\infty }{\nabla }_{{\theta }_i}{\nabla }_{{\theta }_i}p({\theta }_i\mid {\theta }_{\setminus i})d{\theta }_{i}d{\theta }_{\setminus i}=0$ because the first derivative also vanishes at $\pm \infty$. $\square$

One-dimensional sanity check

For $p=\mathcal{N}(0,{\sigma }^2)$: $\nabla \log p=-\theta /{\sigma }^2$, ${\nabla }^2\log p=-1/{\sigma }^2$. Then $-\mathbb{E}[{\nabla }^2\log p]=1/{\sigma }^2$ and $\mathbb{E}[(\nabla \log p{)}^2]=\mathbb{E}[{\theta }^2]/{\sigma }^4=1/{\sigma }^2$. The two sides agree, and $1/{\sigma }^2$ is the ${\lambda }_{\max }(H)$ that MEADS wants for the step size.

Connections

Hoffman 2022 - MEADS - Overview lists where each appendix is used. For the importance of boundary decay in funnels (where it can fail numerically) see Betancourt 2015 - Hierarchical Geometry and the Funnel.

See Also

Hoffman 2022 - Ensemble-Chain Adaptation and Parallelism, Hoffman 2022 - MEADS Heuristics - Step Size, Damping, Drift and Eigenvalue Estimation