(51)

Since both $f_{\boldsymbol{\gamma}_{\star}}(x_{1}^{n})$ and
$\mathbb{P}\left(x_{n+1}=1\mid x_{n}\right)$ are linear functions of $x_{n}$,
equating them for all vallues of $x_{n}\in\\{0,1\\}$ implies that the
respective coeffecients in these functions in Eq. (50) and Eq. (51) are also
equal, i.e.

$\displaystyle\sigma\left(b-\frac{e^{2}}{2}\right)$ $\displaystyle=p,$
$\displaystyle\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)-\sigma\left(b-\frac{e^{2}}{2}\right)$
$\displaystyle=1-p-q,$

and hence

$\displaystyle\sigma\left(b-\frac{e^{2}}{2}\right)=p,\quad\sigma\left(2e^{2}w|w|)+b+\frac{e^{2}}{2}\right)=1-q.$
(52)

Since $\sigma(z)=y$ for $y\in(0,1)$ implies $z=\log\frac{y}{1-y}$, Eq. (52)
can be rewritten as

$\displaystyle b-\frac{e^{2}}{2}=\log\frac{p}{1-p},\quad
2e^{2}w|w|+b+\frac{e^{2}}{2}=\log\frac{1-q}{q}.$

Using
$2e^{2}w|w|+b+\frac{e^{2}}{2}=e^{2}(1+2w|w|)+b-\frac{e^{2}}{2}=e^{2}(1+2w|w|)+\log\frac{p}{1-p}$
in the second equality above, we obtain

$\displaystyle\begin{split}b-\frac{e^{2}}{2}&=\log\frac{p}{1-p},\\\
e^{2}(1+2w|w|)&=\log\frac{1-q}{q}+\log\frac{1-p}{p}=\log\frac{(1-p)(1-q)}{pq}.\end{split}$
(53)

Thus $\boldsymbol{\gamma}_{\star}\in\mathbb{R}^{3}$ is a global minimum for
$L(\cdot)$ if and only if it satisfies Eq. (53) (note that it’s already a
critical point, as established in Thm. 6). Thus, the set of all global minimum
$\boldsymbol{\Gamma}_{\star}(p,q)$ is given by

$\displaystyle\boldsymbol{\Gamma}_{\star}(p,q)\triangleq\left\\{\boldsymbol{\gamma}_{\star}=(e,w,b)\in\mathbb{R}^{3}:e^{2}(1+2w|w|)=\log\frac{(1-p)(1-q)}{pq},\,b-\frac{e^{2}}{2}=\log\frac{p}{1-p}\right\\}.$

Since the prediction $f_{\boldsymbol{\gamma}_{\star}}(\cdot)$ equals the
Markov kernel for any
$\boldsymbol{\gamma}_{\star}\in\boldsymbol{\Gamma}_{\star}$, it follows from
Thm. 4 (or [23, Lemma 1]) that $L(\boldsymbol{\gamma}_{\star})=H(x_{n+1}\mid
x_{n})$, the entropy rate of the Markov chain.

(ii) Set of local minima and saddle points.

Define $\boldsymbol{\Gamma}_{\mathrm{min}}(p,q)\subseteq\mathbb{R}^{3}$ and
$\boldsymbol{\Gamma}_{\mathrm{sad}}\subseteq\mathbb{R}^{3}$ as follows:

$\displaystyle\boldsymbol{\Gamma}_{\mathrm{min}}(p,q)$
$\displaystyle\triangleq\left\\{\boldsymbol{\gamma}_{\mathrm{min}}=(e,w,b)\in\mathbb{R}^{3}:e=0,(p+q-1)(1+2w|w|)>0,b=\log\frac{p}{q}\right\\},$
$\displaystyle\boldsymbol{\Gamma}_{\mathrm{sad}}(p,q)$
$\displaystyle\triangleq\left\\{\boldsymbol{\gamma}_{\mathrm{sad}}=(e,w,b)\in\mathbb{R}^{3}:e=0,(p+q-1)(1+2w|w|)\leq
0,b=\log\frac{p}{q}\right\\}.$

To show that $\boldsymbol{\Gamma}_{\mathrm{min}}$ is the set of all bad local
minima for $L(\cdot)$, we first show that any
$\boldsymbol{\gamma}_{\mathrm{min}}\in\boldsymbol{\Gamma}_{\mathrm{min}}$ is a
bad local minimum and then show that every bad local minimum should belong to
$\boldsymbol{\Gamma}_{\mathrm{min}}$. Similarly for
$\boldsymbol{\Gamma}_{\mathrm{sad}}$. We start with the local minima.

Let
$\boldsymbol{\gamma}_{\mathrm{min}}=(e,w,b)\in\boldsymbol{\Gamma}_{\mathrm{min}}$.
Recall that $\boldsymbol{\gamma}_{\mathrm{min}}$ is a stationary point (Thm.
6), i.e.

$\displaystyle\nabla L(\boldsymbol{\gamma}_{\mathrm{min}})=0.$

Rearragning the order of scalars and writing
$\boldsymbol{\gamma}_{\mathrm{min}}=(b,e,w)$, from Lemma 4, the Hessian of the
loss at $\boldsymbol{\gamma}_{\mathrm{min}}$ is

$\displaystyle\nabla^{2}L(\boldsymbol{\gamma}_{\mathrm{min}})=\pi_{0}\pi_{1}\begin{bmatrix}1&0&0\\\
0&2(p+q-1)(1+2w|w|)&0\\\ 0&0&0\end{bmatrix}.$ (54)

By definition, $\boldsymbol{\gamma}_{\mathrm{min}}=(b,e,w)$ satisfies
$(p+q-1)(1+2w|w|)>0$. Thus its Hessian in Eq. (54) has a block diagonal
structure of the form $\begin{bmatrix}\boldsymbol{H}_{b,e}&0\\\
0&0\end{bmatrix}$ where $\boldsymbol{H}_{b,e}$ has both the eigen values
positive, and hence positive-definite. In other words,
$\boldsymbol{\gamma}_{\mathrm{min}}$ is a local minimum for $L(\cdot)$ in the
$(b,e)\in\mathbb{R}^{2}$ space for any fixed $w$ in the set. Interestingly,
using the continuity argument and the fact that $L(b=\log\frac{p}{q},e=0,w)$
is constant in $w\in\mathbb{R}$, we can essentially follow the same steps as
in proof of Theorem 2 in [23, Appendix B.3] (Thm. 5 above) to show that
$\boldsymbol{\gamma}_{\mathrm{min}}=(b,e,w)$ is a also local minimum for
$L(\cdot)$ in the full parameter space $\mathbb{R}^{3}$. This establishes that
$\boldsymbol{\gamma}_{\mathrm{min}}$ is a local minimum for $L(\cdot)$.

For the saddle points, let
$\boldsymbol{\gamma}_{\mathrm{sad}}=(e,w,b)\in\boldsymbol{\Gamma}_{\mathrm{sad}}$.
We have that $\boldsymbol{\gamma}_{\mathrm{sad}}$ is a stationary point (Thm.
6) and Lemma 4 implies its Hessian (after rearraging the order of scalars as
above with $\boldsymbol{\gamma}_{\mathrm{sad}}=(b,e,w)$) is:

$\displaystyle\nabla^{2}L(\boldsymbol{\gamma}_{\mathrm{sad}})=\pi_{0}\pi_{1}\begin{bmatrix}1&0&0\\\
0&2(p+q-1)(1+2w|w|)&0\\\ 0&0&0\end{bmatrix}.$ (55)

If $w\neq-\frac{1}{\sqrt{2}}$, $(p+q-1)(1+2w|w|)<0$ for any
$\boldsymbol{\gamma}_{\mathrm{sad}}\in\boldsymbol{\Gamma}_{\mathrm{sad}}$, and
hence the Hessian $\nabla^{2}L(\boldsymbol{\gamma}_{\mathrm{sad}})$ in Eq.
(55) as both positive, negative, and zero eigen values. Thus
$\boldsymbol{\gamma}_{\mathrm{sad}}$ is a saddle point for $L(\cdot)$. Using a
neighborhood argument, we can similarly argue for $w=\frac{1}{\sqrt{2}}$ to
establish that it’s also a saddle point. Now we compute the loss value.

For any
$\boldsymbol{\gamma}_{\mathrm{min}}=(e,w,b)\in\boldsymbol{\Gamma}_{\mathrm{min}}$
or
$\boldsymbol{\gamma}_{\mathrm{sad}}=(e,w,b)\in\boldsymbol{\Gamma}_{\mathrm{sad}}$,
we have that $e=0$ and $b=\log\frac{p}{q}$. Thus for
$\boldsymbol{\gamma}=\boldsymbol{\gamma}_{\mathrm{min}}$ or
$\boldsymbol{\Gamma}_{\mathrm{sad}}$, the prediction probability in view of
Eq. (3) is

$\displaystyle\mathbb{P}_{\boldsymbol{\gamma}}(x_{n+1}=1\mid
x_{1}^{n})=\sigma\left(e^{2}(1+2w|w|)\,x_{n}+b-\frac{e^{2}}{2}\right)=\sigma(b)=\frac{p}{p+q}=\mathbb{P}\left(x_{n+1}=1\right),$

the marginal distribution. Substituting this equality in the definition of
cross-entropy loss $L(\cdot)$ in Eq. (1) and the fact that
$\mathbb{P}\left(x_{n+1}=1\right)=\frac{p}{p+q}=\pi_{1}$, following the same
steps as in [23, Appendix B.3], we obtain

$\displaystyle L(\boldsymbol{\gamma})=$
$\displaystyle-\frac{1}{N}\sum_{n\in[N]}\mathbb{E}_{x_{1}^{n+1}}[x_{n+1}\cdot\log
f_{\boldsymbol{\gamma}}(x_{1}^{n})+(1-x_{n+1})\cdot\log(1-f_{\boldsymbol{\gamma}}(x_{1}^{n}))]$
$\displaystyle=-\frac{1}{N}\sum_{n\in[N]}\mathbb{E}_{x_{1}^{n+1}}\left[x_{n+1}\cdot\log\pi_{1}+(1-x_{n+1})\cdot\log\pi_{0}\right]$
$\displaystyle=\frac{1}{N}\sum_{n\in[N]}\left[-\pi_{1}\log\pi_{1}-\pi_{0}\log\pi_{0}\right]$
$\displaystyle=H(\boldsymbol{\pi})=H(x_{n+1}).$

Thus
$L(\boldsymbol{\gamma}_{\mathrm{min}})=L(\boldsymbol{\gamma}_{\mathrm{sad}})=H(x_{n+1})$.
To see that $H(x_{n+1}\mid
x_{n})=L(\boldsymbol{\gamma}_{\star})<L(\boldsymbol{\gamma}_{\mathrm{min}})=L(\boldsymbol{\gamma}_{\mathrm{sad}})=H(x_{n+1})$
for any global minimum $\boldsymbol{\gamma}_{\star}$, observe that the gap

$\displaystyle
L(\boldsymbol{\gamma}_{\mathrm{min}})-L_{\star}=H(x_{n+1})-H(x_{n+1}|x_{n})=I(x_{n};x_{n+1})\geq
0,$

where $I(x_{n};x_{n+1})$ is the mutual information between $x_{n}$ and
$x_{n+1}$ [11]. Hence the optimality gap equals zero if and only if the mutual
information equals zero, which happens when $x_{n}$ and $x_{n+1}$ are
independent, i.e. $\mathbb{P}\left(x_{n+1}=1\mid x_{n}\right)$ doesn’t depend
on $x_{n}$. Since $\mathbb{P}\left(x_{n+1}=1\mid x_{n}\right)=(1-p-q)x_{n}+p$
from Eq. (50), this happens only when $p+q=1$ which contradicts the theorem
assumption that $p+q\neq 1$. Hence $H(x_{n+1}\mid
x_{n})=L(\boldsymbol{\gamma}_{\star})<L(\boldsymbol{\gamma}_{\mathrm{min}})=L(\boldsymbol{\gamma}_{\mathrm{sad}})=H(x_{n+1})$.

Now we finally show that $\boldsymbol{\Gamma}_{\mathrm{min}}$ and
$\boldsymbol{\Gamma}_{\mathrm{sad}}$ are the only set of bad local minima and
saddle points respectively. Let $\boldsymbol{\gamma}$ is a bad local minimum
for $L(\cdot)$. By definition, it’s also a critical point. Recall from Thm. 6
that any stationary point $\boldsymbol{\gamma}=(e,w,b)$ for the loss
$L(\cdot)$ satisfies that either
$\boldsymbol{\gamma}\in\boldsymbol{\Gamma}_{\star}$,
$\boldsymbol{\gamma}\in\boldsymbol{\Gamma}_{\mathrm{min}}$, or
$\boldsymbol{\gamma}\in\boldsymbol{\Gamma}_{\mathrm{sad}}$. Clearly
$\boldsymbol{\gamma}\not\in\boldsymbol{\Gamma}_{\star}$, as
$\boldsymbol{\Gamma}_{\star}$ is the set of all global minima. Similarly,
$\boldsymbol{\gamma}\not\in\boldsymbol{\Gamma}_{\mathrm{sad}}$ as every point
in $\boldsymbol{\Gamma}_{\mathrm{sad}}$ is a saddle point for the loss
$L(\cdot)$ as established above. Hence
$\boldsymbol{\gamma}\in\boldsymbol{\Gamma}_{\mathrm{min}}$. Thus every bad
local minimum in $\mathbb{R}^{3}$ belongs to
$\boldsymbol{\Gamma}_{\mathrm{min}}$. This coupled with the fact above that
$\boldsymbol{\Gamma}_{\mathrm{min}}$ is a set of bad local minima implies
$\boldsymbol{\Gamma}_{\mathrm{min}}$ is indeed the set of all bad local
minima. The proof for $\boldsymbol{\Gamma}_{\mathrm{sad}}$ is similar.

∎

###  J.2 Proof of Thm. 6

###### Proof.

Let $\boldsymbol{\gamma}=(e,w,b)\in\mathbb{R}^{3}$ be such that $\nabla
L(\boldsymbol{\gamma})=\left(\frac{\partial L}{\partial e},\frac{\partial
L}{\partial w},\frac{\partial L}{\partial b}\right)^{\top}=0$. By Lemma 3, we
have

$\displaystyle\frac{\partial L}{\partial e}$
$\displaystyle=\mathbb{E}_{X}\left[(f_{1}X+f_{2})(2X(1+2w|w|)-1))\right]\cdot
e=0,$ (56) $\displaystyle\frac{\partial L}{\partial w}$
$\displaystyle=\mathbb{E}_{X}\left[(f_{1}X+f_{2})X\right]\cdot 4e^{2}|w|=0,$
(57) $\displaystyle\frac{\partial L}{\partial b}$
$\displaystyle=\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,$ (58)

where $X\sim\mathrm{Bern}(p/(p+q))$,
$f_{1}=\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b-\frac{e^{2}}{2}\right)+p$,
and $f_{2}=\sigma\left(b-\frac{e^{2}}{2}\right)-p$. Our goal is to now show
that Eqs. (56)-(58) hold only if either $(e=0,b=\log\frac{p}{q})$ or
$(f_{1}=0,f_{2}=0)$. We consider two cases corresponding to $e=0$ and $e\neq
0$.

(i): $e=0$. If $e=0$, we readily see that $\frac{\partial L}{\partial
e}=\frac{\partial L}{\partial e}=0$. Further, $f_{1}=p+q-1$ and
$f_{2}=\sigma(b)-p$. Hence, Eq. (58) implies that

$\displaystyle\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=(p+q-1)\mathbb{E}[X]+\sigma(b)-p=(p+q-1)\frac{p}{p+q}+\sigma(b)-p=\sigma(b)-\frac{p}{p+q}=0,$

which implies that $b=\log\frac{p}{q}$. Since $w\in\mathbb{R}$ is arbitrary,
we see in this case that

$\displaystyle\boldsymbol{\gamma}$
$\displaystyle\in\left\\{(e,w,b)\in\mathbb{R}^{3}:e=0,(p+q-1)(1+2w|w|)>0,b=\log\frac{p}{q}\right\\}\bigcup$
$\displaystyle\hskip
20.00003pt\left\\{(e,w,b)\in\mathbb{R}^{3}:e=0,(p+q-1)(1+2w|w|)<0,b=\log\frac{p}{q}\right\\},$
$\displaystyle=\boldsymbol{\Gamma}_{\mathrm{min}}\cup\boldsymbol{\Gamma}_{\mathrm{sad}}.$

(ii): $e\neq 0$. Suppose $e\neq 0$. Here we show that $f_{1}=f_{2}=0$ and
hence $\boldsymbol{\gamma}\in\boldsymbol{\Gamma}_{\star}$. We consider two
cases corresponding to $w\neq 0$ and $w=0$. Let $w\neq 0$. Since both $e\neq
0$ and $w\neq 0$, and $X=X^{2}$ in Eq. (57) with
$\mathbb{E}[X]=\pi_{1}=\frac{p}{p+q}>0$, we obtain that

$\displaystyle\mathbb{E}_{X}[f_{1}X^{2}+f_{2}X]=(f_{1}+f_{2})\mathbb{E}[X]=(f_{1}+f_{2})\pi_{1}=0,$

and hence $f_{1}+f_{2}=0$. Further Eq. (58) implies that
$f_{1}\pi_{1}+f_{2}=0$. Together, this implies $f_{1}=f_{2}=0$.

Now suppose $w=0$. From Eq. (58), we have that
$\mathbb{E}[f_{1}X+f_{2}]=f_{1}\pi_{1}+f_{2}=0$. Since $e\neq 0$, Eq. (56)
yields

$\displaystyle\mathbb{E}_{X}\left[(f_{1}X+f_{2})(2X-1))\right]=2\mathbb{E}_{X}\left[(f_{1}X+f_{2})X\right]=2\pi_{1}(f_{1}+f_{2})=0.$

So $f_{1}=f_{2}=0$ in this case too. Thus we have showed that whenever $e\neq
0$, we have $f_{1}=f_{2}=0$. Recalling the expressions for $f_{1}$ and
$f_{2}$,

$\displaystyle f_{2}$
$\displaystyle=\sigma\left(b-\frac{e^{2}}{2}\right)-p=0\Rightarrow
b-\frac{e^{2}}{2}=\log\frac{p}{1-p},$ (59) $\displaystyle f_{1}$
$\displaystyle=\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b-\frac{e^{2}}{2}\right)+p=\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1=0,$

and hence,

$\displaystyle 2e^{2}w|w|+b+\frac{e^{2}}{2}=\log\frac{1-q}{q}.$

Substituting $b-\frac{e^{2}}{2}=\log\frac{p}{1-p}$ in the above equation,

$\displaystyle
2e^{2}w|w|+e^{2}+b-\frac{e^{2}}{2}=2e^{2}w|w|+e^{2}+\log\frac{p}{1-p}=\log\frac{1-q}{q},$

and thus,

$\displaystyle e^{2}(1+2w|w|)=\log\frac{(1-p)(1-q)}{pq}.$ (60)

In view of Eq. (59) and Eq. (60), we have that
$\boldsymbol{\gamma}=(e,w,b)\in\boldsymbol{\Gamma}_{\star}$.

Together, we have shown that whenever $\nabla L(\boldsymbol{\gamma})=0$, we
have
$\boldsymbol{\gamma}\in\boldsymbol{\Gamma}_{\star}\cup\boldsymbol{\Gamma}_{\mathrm{min}}\cup\boldsymbol{\Gamma}_{\mathrm{sad}}$.
Since
$\boldsymbol{\Gamma}_{\star}\cup\boldsymbol{\Gamma}_{\mathrm{min}}\cup\boldsymbol{\Gamma}_{\mathrm{sad}}\subseteq\left\\{\boldsymbol{\gamma}:\nabla
L(\boldsymbol{\gamma})=0\right\\}$, we are done. ∎

##  Appendix K Proofs of technical lemmas in App. D

###  K.1 Proof of Lemma 2

###### Proof.

Recall from Eq. (14) that the cross-entropy loss $L(\cdot)$ is defined as

$\displaystyle L(\boldsymbol{\gamma})$
$\displaystyle=-\frac{1}{N}\sum_{n\in[N]}\mathbb{E}_{x_{1}^{n+1}}[x_{n+1}\cdot\log
f_{\boldsymbol{\gamma}}(x_{1}^{n})\,+(1-x_{n+1})\cdot\log(1-f_{\boldsymbol{\gamma}}(x_{1}^{n}))],$
(61)

where
$f_{\boldsymbol{\gamma}}(x_{1}^{n})=\sigma(\mathrm{logit}_{n})=\sigma\left(e^{2}(1+2w|w|)\,x_{n}+b-\frac{e^{2}}{2}\right)$
from Eq. (3). For any $Y\in\\{0,1\\},Z\in\mathbb{R}$, using the fact that
$1-\sigma(Z)=\sigma(-Z)$, we have

$\displaystyle\begin{split}-\left[Y\log\sigma(Z)+(1-Y)\log(1-\sigma(Z))\right]&=-\left[Y\log\sigma(Z)+(1-Y)\log\sigma(-Z)\right]\\\
&\stackrel{{\scriptstyle(a)}}{{=}}Y\log(1+\exp(-Z))+(1-Y)\log(1+\exp(Z))\\\
&=\log\left(1+\exp(-(2Y-1)Z)\right)\\\
&\stackrel{{\scriptstyle(b)}}{{=}}\ell_{\mathrm{log}}\left((2Y-1)Z\right),\end{split}$
(62)

where $(a)$ and $(b)$ follow from the definitions of sigmoid and the logistic
functions:
$\sigma(z)=\frac{1}{1+\exp(-z)},\,\ell_{\mathrm{log}}(z)=\log(1+\exp(-z))$ for
$z\in\mathbb{R}$. Substituting $Y=x_{n+1}\in\\{0,1\\}$ and
$Z=\mathrm{logit}_{n}\in\mathbb{R}$ in Eq. (62), Eq. (61) simplifies to

$\displaystyle
L(\boldsymbol{\gamma})=\frac{1}{N}\sum_{n\in[N]}\mathbb{E}[\ell_{\mathrm{log}}\left((2x_{n+1}-1)\cdot\mathrm{logit}_{n}\right)].$

Since $\mathrm{logit}_{n}$ is only a function of $x_{n}$, the above
expectation is over the distribution of the pairs $(x_{n},x_{n+1})$, which for
all $n\in[N]$ have the same law as a pair of random variables $(X,Y)$ with
$X\sim\boldsymbol{\pi}\equiv\mathrm{Bern}(p/(p+q))$ and
$Y|X\sim\boldsymbol{P}(p,q)$, the Markov kernel. Hence the above equality can
be rewritten using the definition of $\mathrm{logit}_{n}$ as

$\displaystyle
L(\boldsymbol{\gamma})=\frac{1}{N}\sum_{n\in[N]}\mathbb{E}[\ell_{\mathrm{log}}\left((2x_{n+1}-1)\cdot\mathrm{logit}_{n}\right)]=\mathbb{E}_{X,Y}\left[\ell_{\mathrm{log}}\left((2Y-1)\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right)\right].$

∎

###  K.2 Proof of Lemma 3

###### Proof.

With $\boldsymbol{\gamma}=(e,w,b)$ and $\theta$ denoting either of the scalars
$e,w$, or $b$, we have from [23, Lemma 2] that the gradient of the loss
$L(\cdot)$ is given by

$\displaystyle\nabla_{\theta}L(\boldsymbol{\gamma})$
$\displaystyle=-\frac{1}{N}\sum_{n\in[N]}\mathbb{E}_{x_{1}^{n+1}}\left[(x_{n+1}-f_{\boldsymbol{\theta}}(x_{1}^{n}))\cdot\nabla_{\theta}\,\mathrm{logit}_{n}\right],$
(63)

where
$f_{\boldsymbol{\gamma}}(x_{1}^{n})=\sigma(\mathrm{logit}_{n})=\sigma\left(e^{2}(1+2w|w|)\,x_{n}+b-\frac{e^{2}}{2}\right)$.
Using the same argument as in the proof of Lemma 6, we can replace the
expecatations in Eq. (63) with that of a pair of random variables $(X,Y)$ with
$X\sim\boldsymbol{\pi}\equiv\mathrm{Bern}(p/(p+q))$ and
$Y|X\sim\boldsymbol{P}(p,q)$, the Markov kernel. That is,

$\displaystyle\nabla_{\theta}L(\boldsymbol{\gamma})$
$\displaystyle=-\mathbb{E}_{X,Y}\left[\left(Y-\sigma\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right)\cdot\nabla_{\theta}\,\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right].$
(64)

Now we define the error term
$\mathcal{E}(X,Y)\triangleq-\left(Y-\sigma\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right)$.
Our goal is to show that $\mathbb{E}[\mathcal{E}(X,Y)\mid X]=f_{1}X+f_{2}$,
where
$f_{1}\triangleq\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b-\frac{e^{2}}{2}\right)+p$,
and $f_{2}\triangleq\sigma\left(b-\frac{e^{2}}{2}\right)-p$, which suffices to
prove the lemma. To this end, using the fact that $X\in\\{0,1\\}$, we have

$\displaystyle\mathcal{E}(X,Y)$
$\displaystyle=-\left(Y-\sigma\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right)$
$\displaystyle=-\left(Y-X\cdot\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)-(1-X)\cdot\sigma\left(b-\frac{e^{2}}{2}\right)\right)$
$\displaystyle=-Y+X\left(\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)-\sigma\left(b-\frac{e^{2}}{2}\right)\right)+\sigma\left(b-\frac{e^{2}}{2}\right).$

Now taking the conditional expectation with respect to $X$ and using the fact
that $\mathbb{E}[Y|X]=\mathbb{P}\left(Y=1\mid X\right)=(1-p-q)X+p$ (since
$Y|X\sim\boldsymbol{P}(p,q)$), we have

$\displaystyle\mathbb{E}[\mathcal{E}(X,Y)\mid X]$
$\displaystyle=-(1-p-q)X-p+X\left(\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)-\sigma\left(b-\frac{e^{2}}{2}\right)\right)+\sigma\left(b-\frac{e^{2}}{2}\right)$
$\displaystyle=X\left(\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b-\frac{e^{2}}{2}\right)+p\right)+\sigma\left(b-\frac{e^{2}}{2}\right)-p$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}f_{1}X+f_{2},$

where $(a)$ follows from the definition of $f_{1}$ and $f_{2}$ above. Thus Eq.
(64) simplifies to

$\displaystyle\nabla_{\theta}L(\boldsymbol{\gamma})=\mathbb{E}_{X}\left[(f_{1}X+f_{2})\cdot\nabla_{\theta}\,\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right].$

Letting $\theta=e,w$, and $b$ in the above equation, we finally obtain the
individual gradients:

$\displaystyle\frac{\partial L}{\partial e}$
$\displaystyle=\mathbb{E}_{X}\left[(f_{1}X+f_{2})(2X(1+2w|w|-1))\right]\cdot
e,$ $\displaystyle\frac{\partial L}{\partial w}$
$\displaystyle=\mathbb{E}_{X}\left[(f_{1}X+f_{2})X\right]\cdot 4e^{2}|w|,$
$\displaystyle\frac{\partial L}{\partial b}$
$\displaystyle=\mathbb{E}_{X}\left[f_{1}X+f_{2}\right].$

∎

###  K.3 Proof of Lemma 4

###### Proof.

Slightly changing the variable order, for any
$\boldsymbol{\gamma}=(b,e,w)\in\mathbb{R}^{3}$, we define

$\displaystyle\boldsymbol{H}(\boldsymbol{\gamma})\triangleq\nabla^{2}L(\boldsymbol{\gamma})=\begin{bmatrix}\frac{\partial^{2}L}{\partial
b^{2}}&\frac{\partial^{2}L}{\partial b\partial
e}&\frac{\partial^{2}L}{\partial b\partial w}\\\ &&\\\
\frac{\partial^{2}L}{\partial e\partial b}&\frac{\partial^{2}L}{\partial
e^{2}}&\frac{\partial^{2}L}{\partial e\partial w}\\\ &&\\\
\frac{\partial^{2}L}{\partial w\partial b}&\frac{\partial^{2}L}{\partial
w\partial e}&\frac{\partial^{2}L}{\partial w^{2}}\\\
\end{bmatrix}\in\mathbb{R}^{3\times 3}.$ (65)

Recall that for any
$\boldsymbol{\gamma}_{\mathrm{min}}\in\boldsymbol{\Gamma}_{\mathrm{min}}$ and
$\boldsymbol{\gamma}_{\mathrm{sad}}\in\boldsymbol{\Gamma}_{\mathrm{sad}}$, we
have $e=0$ and $b=\log\frac{p}{q}$. Now we compute the second derivatives of
$L$ with respect to any $\boldsymbol{\gamma}=(b=\log\frac{p}{q},e=0,w)$. We
start with the first derivatives. By Lemma 7, the gradients are

$\displaystyle\begin{split}\frac{\partial L}{\partial
b}&=\mathbb{E}_{X}\left[f_{1}X+f_{2}\right],\\\ \frac{\partial L}{\partial
e}&=\mathbb{E}_{X}\left[(f_{1}X+f_{2})(2X(1+2w|w|)-1))\right]\cdot e,\\\
\frac{\partial L}{\partial w}&=\mathbb{E}_{X}\left[(f_{1}X+f_{2})X\right]\cdot
4e^{2}|w|,\end{split}$ (66)

where

$\displaystyle f_{1}$
$\displaystyle\triangleq\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b-\frac{e^{2}}{2}\right)+p,$
$\displaystyle f_{2}$
$\displaystyle\triangleq\sigma\left(b-\frac{e^{2}}{2}\right)-p.$

From Eq. (66), we see that the second derivaties of $L$ depend on the first-
derivatives of $f_{1}$ and $f_{2}$, which we now compute. Recall that the
derivative of the sigmoid function obeys
$\sigma^{\prime}(z)=\sigma(z)(1-\sigma(z))=\sigma(z)\sigma(-z)$ for any
$z\in\mathbb{R}$. Now the gradients of $f_{1}$ and $f_{2}$ with respect to
$b,e$, and $w$ are

$\displaystyle\frac{\partial f_{1}}{\partial b}$
$\displaystyle=\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)\sigma\left(-2e^{2}w|w|-b-\frac{e^{2}}{2}\right)-\sigma\left(b-\frac{e^{2}}{2}\right)\sigma\left(-b+\frac{e^{2}}{2}\right),$
$\displaystyle\frac{\partial f_{2}}{\partial b}$
$\displaystyle=\sigma\left(b-\frac{e^{2}}{2}\right)\sigma\left(-b+\frac{e^{2}}{2}\right),$
$\displaystyle\frac{\partial f_{1}}{\partial e}$
$\displaystyle=(4ew|w|+e)\,\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)\sigma\left(-2e^{2}w|w|-b-\frac{e^{2}}{2}\right)+e\,\sigma\left(b-\frac{e^{2}}{2}\right)\sigma\left(-b+\frac{e^{2}}{2}\right),$
$\displaystyle\frac{\partial f_{2}}{\partial e}$
$\displaystyle=(-e)\,\sigma\left(b-\frac{e^{2}}{2}\right)\sigma\left(-b+\frac{e^{2}}{2}\right),$
$\displaystyle\frac{\partial f_{1}}{\partial w}$ $\displaystyle=(4e^{2}\cdot
w\mathrm{sign}(w))\,\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)\sigma\left(-2e^{2}w|w|-b-\frac{e^{2}}{2}\right),$
$\displaystyle\frac{\partial f_{2}}{\partial w}$ $\displaystyle=0.$

Using the fact that $\sigma\left(\log\frac{p}{q}\right)=\frac{p}{p+q}=\pi_{1}$
and $\sigma\left(-\log\frac{p}{q}\right)=\frac{q}{p+q}=\pi_{0}$, the above
gradients evaluated for any $\boldsymbol{\gamma}=(b=\log\frac{p}{q},e=0,w)$
further reduce to

$\displaystyle\begin{split}\frac{\partial f_{1}}{\partial
b}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial f_{2}}{\partial
b}\bigg{\rvert}_{\boldsymbol{\gamma}}=\pi_{0}\pi_{1},\\\ \frac{\partial
f_{1}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial
f_{2}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\\\ \frac{\partial
f_{1}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial
f_{2}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}=0.\end{split}$ (67)

Now substituting Eq. (67) when computing the second-derivatives of $L$ in Eq.
(66), we obtain

$\displaystyle\begin{split}\frac{\partial^{2}L}{\partial
b^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial b}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial
b}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=\pi_{0}\pi_{1},\\\
\frac{\partial^{2}L}{\partial b\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=0,\\\
\frac{\partial^{2}L}{\partial b\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=0,\\\
\frac{\partial^{2}L}{\partial
e^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[(f_{1}X+f_{2})(2X(1+2w|w|)-1))\right]\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[(2f_{1}(1+2w|w|)-f_{1}+2f_{2}(1+2w|w|)X-f_{2}\right]\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[(f_{1}(1+4w|w|)+f_{2}(2+4w|w|)X-f_{2}\right]\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=(f_{1}(1+4w|w|)+f_{2}(2+4w|w|))\pi_{1}-f_{2}\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\stackrel{{\scriptstyle(a)}}{{=}}((p+q-1)(1+4w|w|)-\pi_{1}(p+q-1)(2+4w|w|))\pi_{1}+\pi_{1}(p+q-1)\\\
&=\pi_{1}(p+q-1)\left(1+4w|w|-\pi_{1}(2+4w|w|)+1\right)\\\
&\stackrel{{\scriptstyle(b)}}{{=}}2\pi_{1}\pi_{0}(p+q-1)(1+2w|w|),\end{split}$
(68)

where $(a)$ follows from the fact that
$f_{1}|_{\boldsymbol{\gamma}}=p+q-1,f_{2}|_{\boldsymbol{\gamma}}=\sigma(b)-p=\frac{p}{p+q}-p=\frac{-p}{p+q}(p+q-1)=-\pi_{1}(p+q-1)$
and $(b)$ from $1-\pi_{1}=\pi_{0}$. Returning to the remaining second
derivatives,

$\displaystyle\begin{split}\frac{\partial^{2}L}{\partial e\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
e}\left(\mathbb{E}[(f_{1}X+f_{2})X]\cdot
4e^{2}|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\frac{\partial}{\partial e}\left(\mathbb{E}[(f_{1}+f_{2})X]\cdot
4e^{2}|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\frac{\partial}{\partial e}\left((f_{1}+f_{2})\cdot
4\pi_{1}e^{2}|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\frac{\partial}{\partial
e}\left(\left(\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1\right)\cdot
4\pi_{1}e^{2}|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\left(\frac{\partial}{\partial
e}\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)\right)4\pi_{1}e^{2}|w|\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\hskip
30.00005pt+\left(\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1\right)\cdot\frac{\partial}{\partial
e}(4\pi_{1}e^{2}|w|)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\ &=0,\\\
\frac{\partial^{2}L}{\partial
w^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
w}\left(\mathbb{E}[(f_{1}X+f_{2})X]\cdot 4e^{2}|w|\right)\\\
&=\left(\frac{\partial}{\partial w}\mathbb{E}[(f_{1}X+f_{2})X]\cdot
4|w|\right)e^{2}\bigg{\rvert}_{\boldsymbol{\gamma}}\\\ &=0.\end{split}$ (69)

Congregating all the second derivatives from Eq. (68) and Eq. (69) into the
Hessian $\boldsymbol{H}(\boldsymbol{\gamma})$ in Eq. (65), we finally obtain

$\displaystyle\boldsymbol{H}(\boldsymbol{\gamma})=\pi_{0}\pi_{1}\begin{bmatrix}1&0&0\\\
0&2(p+q-1)(1+2w|w|)&0\\\ 0&0&0\end{bmatrix}.$

∎

##  Appendix L Proofs of lemmas in App. E

###  L.1 Proof of Lemma 5

###### Proof.

Recall from Lemma 2 that for any $\boldsymbol{\theta}=(e,w)\in\mathbb{R}^{2}$
and $b\in\mathbb{R}$, we have

$\displaystyle
L(\boldsymbol{\theta},b)=\mathbb{E}_{X,Y}\left[\ell_{\mathrm{log}}\left((2Y-1)\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right)\right].$

Since $\ell_{\mathrm{log}}(\cdot)$ is a convex function, $Y\in\\{0,1\\}$ and
thus $2Y-1\in\\{\pm 1\\}$, the convexity of $L$ in $b$ follows from the
following fact:

$\displaystyle\frac{\partial^{2}L}{\partial
b^{2}}=\mathbb{E}_{X,Y}\left[\ell_{\mathrm{log}}^{\prime\prime}\left((2Y-1)\left(e^{2}(1+2w|w|)X+b-\frac{e^{2}}{2}\right)\right)\right]\geq
0.$

To find the optimal $b_{\star}$, we set the gradient $\frac{\partial
L}{\partial b}=0$. Thus from Lemma 3, we obtain

$\displaystyle\frac{\partial L}{\partial b}$
$\displaystyle=\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,$ $\displaystyle
f_{1}=\sigma\left(2e^{2}w|w|+b+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b-\frac{e^{2}}{2}\right)+p,f_{2}$
$\displaystyle=\sigma\left(b-\frac{e^{2}}{2}\right)-p.$

Substituting $E\triangleq e^{2}(1+2w|w|)$, $B\triangleq b-\frac{e^{2}}{2}$,
and $\mathbb{E}[X]=\pi_{1}=p/(p+q)$ in the above equations,

$\displaystyle\pi_{1}\left(\sigma(E+B)+q-1-\sigma(B)+p\right)+\sigma(B)-p=\pi_{1}\cdot\sigma(E+B)+\pi_{0}\cdot\sigma(B)+\frac{p(p+q-1)}{p+q}-p=0.$

Further simplifying,

$\displaystyle\pi_{0}\cdot\sigma(B)=\pi_{1}\cdot(1-\sigma(E+B))=\pi_{1}\cdot\sigma(-E-B).$

In other words,

$\displaystyle\frac{(1+\exp(-B))^{-1}}{(1+\exp(E+B))^{-1}}=\frac{\pi_{1}}{\pi_{0}}=\frac{p}{q}\Rightarrow\frac{1+\exp(E)\exp(B)}{1+\exp(-B)}=\frac{p}{q}.$

Defining $x\triangleq\exp(B)$ and $A\triangleq\exp(E)$, we thus obtain the
following quadratic equation in $x$ and its corresponding roots:

$\displaystyle Ax^{2}-x\left(\frac{p}{q}-1\right)-\frac{p}{q}=0\Rightarrow
x=\frac{1}{2A}\left[\frac{p}{q}-1\pm\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
A}\right].$

Since $x>0$, we take the root corresponding to the addition choice above and
resubstituting $x=\exp(b-\frac{e^{2}}{2})$ and $A=\exp(e^{2}(1+2w|w|))$, we
obtain the final expression for $b_{\star}$. In particular, if $e=0$, it is
easy to see that $A=1$ and hence $x=\exp(b_{\star})=\frac{p}{q}$, implying
$b_{\star}=\log\frac{p}{q}$. Similarly, if $A=\frac{(1-p)(1-q)}{pq}$, it’s
straightforward to see that $\exp(b_{\star}-e^{2}/2)=\frac{p}{1-p}$ and hence
$b_{\star}-e^{2}/2=\log\frac{p}{1-p}$. ∎

###  L.2 Proof of Lemma 6

###### Proof.

The proof directly follows from Lemma 2 by substituting $b=b_{\star}$. ∎

###  L.3 Proof of Lemma 7

###### Proof.

By Danskin’s theorem [12], it follows that for
$b_{\star}=\mathop{\operatorname{argmin}}_{b\in\mathbb{R}}L(\boldsymbol{\theta},b)$
and $L(\boldsymbol{\theta})=L(\boldsymbol{\theta},b_{\star})$, we have
$\nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta})=\nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta},b_{\star})$.
Using the gradient expressions of $L(\boldsymbol{\theta},b)$ w.r.t
$\boldsymbol{\theta}$ from Lemma 3, and using the fact that $\frac{\partial
L}{\partial b}=\mathbb{E}[f_{1}X+f_{2}]$ at $b=b_{\star}$, the claim follows.
∎

###  L.4 Proof of Lemma 8

###### Proof.

Since $L(\boldsymbol{\theta})=L(\boldsymbol{\theta},b_{\star})$ where
$b_{\star}=\mathop{\operatorname{argmin}}_{b\in\mathbb{R}}L(\boldsymbol{\theta},b)$,
the identity in Eq. (32) about the Hessian of the loss $L$ with respect to
$\boldsymbol{\theta}$ follows from the classical result of [28, Lemma 2.2]
about second-derivatives of extremal-value functions. Finally Eq. (33) follows
from substituting the full Hessian in $\mathbb{R}^{3\times 3}$ from Lemma 4 in
this identity. ∎

##  Appendix M Proofs of lemmas in App. F

###  M.1 Proof of Lemma 9

###### Proof.

Denote $(e_{t},w_{t})=(e,w)$ with the dependence on time implicitly assumed.
Then by the definition of GF and the gradient expressions in Lemma 7, we have
that

$\displaystyle\odv{e}{t}$ $\displaystyle=-\frac{\partial L}{\partial
e}(\boldsymbol{\theta}_{t})=-2\mathbb{E}[(f_{1}X+f_{2})X]\cdot(1+2w|w|)e,$
(70) $\displaystyle\odv{w}{t}$ $\displaystyle=-\frac{\partial L}{\partial
w}(\boldsymbol{\theta}_{t})=-\mathbb{E}[(f_{1}X+f_{2})X]\cdot 4e^{2}|w|.$ (71)

Dividing Eq. (70) by $(1+2w|w|)e$ and Eq. (71) by $4e^{2}|w|$, we have

$\displaystyle\frac{1}{1+2w|w|}\odv{e}{t}=\frac{1}{2e|w|}\odv{w}{t}\Rightarrow
e\odv{e}{t}=\left(w+\frac{1}{2|w|}\right)\odv{w}{t}.$

Noting that $\odv{}{t}(\mathrm{sign}(w)\cdot\log|w|)=\frac{1}{|w|}\odv{w}{t}$,
the above equation can be rewritten as

$\displaystyle\odv{}{t}\left(e^{2}-w^{2}-\mathrm{sign}(w)\cdot\log|w|\right)=0.$

Thus defining $\mathcal{E}(e,w)=e^{2}-w^{2}-\mathrm{sign}(w)\cdot\log|w|$ for
$w\neq 0$, the above equation implies
$\mathcal{E}(\boldsymbol{\theta}_{t})=\mathcal{E}(\boldsymbol{\theta}_{0})$
for $\boldsymbol{\theta}_{0}=(e_{0},w_{0})$ with $w_{0}\neq 0$. On the other
hand, it’s easy to see that if $w_{0}=0$, Eq. (71) implies $\odv{w}{t}=0$ at
$t=0$ and hence $w_{t}=0$ for all $t\geq 0$. ∎

###  M.2 Proof of Lemma 10

###### Proof.

To prove the convergence of the trajectory $(\boldsymbol{\theta}_{t})_{t\geq
0}$, we use the classical result due to Łojasiewicz [1, Theorem 2.2] which
gurantees the convergence of gradient flow for real analytic functions, as
long as the trajectory is bounded. Hence we first show the boundedness of the
trajectory.

(i) $(\boldsymbol{\theta}_{t})_{t\geq 0}$ is bounded.

We consider the cases $\boldsymbol{\theta}_{0}\in\operatorname{e-axis}$ and
$\boldsymbol{\theta}_{0}\in\mathbb{R}^{2}\setminus\operatorname{e-axis}$
separately.

Let’s suppose $\boldsymbol{\theta}_{0}=(e_{0},w_{0})\in\operatorname{e-axis}$,
i.e. $w_{0}=0$. Thus it follows from Lemma 9 that $w_{t}=0$ for all $t\geq 0$.
That is, the trajectory always stays on the $\operatorname{e-axis}$ and it
suffices to track $(e_{t})_{t\geq 0}$ and show that they are bounded. To this
end, we show that if $e_{0}>0$, we have $\odv{e}{t}<0$ and if $e_{0}<0$, we
have $\odv{e}{t}>0$ for all $t\geq 0$, which establishes our claim. We have
from the GF and Lemma 7 that

$\displaystyle\odv{e_{t}}{t}$ $\displaystyle=-\frac{\partial L}{\partial
e}(e_{t},w_{t}=0)=-2\mathbb{E}_{X}\left[(f_{1}X+f_{2})X\right]e_{t}=-2\pi_{1}(f_{1}+f_{2})e_{t},$
(72)

and

$\displaystyle f_{1}+f_{2}$
$\displaystyle=-\frac{f_{2}}{\pi_{1}}+f_{2}=-\frac{\pi_{0}}{\pi_{1}}f_{2}=-\frac{\pi_{0}}{\pi_{1}}\left[\sigma\left((b_{\star})_{t}-\frac{e_{t}^{2}}{2}\right)-p\right]$
$\displaystyle=-\frac{\pi_{0}}{\pi_{1}}\left[\left(1+\exp\left(-(b_{\star})_{t}+\frac{e_{t}^{2}}{2}\right)\right)^{-1}-p\right]$
$\displaystyle=-\frac{\pi_{0}}{\pi_{1}}\left[\left(1+\frac{2x_{t}}{\frac{p}{q}-1+\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
x_{t}}}\right)^{-1}-p\right],\quad x_{t}\triangleq\exp(e_{t}^{2}).$ (73)

Defining

$\displaystyle
g(x)\triangleq\frac{2x}{\frac{p}{q}-1+\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
x}},$ (74)

and substituting Eq. (74) and Eq. (73) in Eq. (72), we obtain

$\displaystyle\odv{e_{t}}{t}=2\pi_{0}\left(\frac{1}{1+g(x_{t})}-p\right)\cdot
e_{t}.$ (75)

Since $x_{t}=\exp(e_{t}^{2})=\exp(-e_{t}^{2})$, in view of Eq. (75), with out
loss of generality, we can assume that $e_{0}>0$ and show that
$\odv{e_{t}}{t}<0$ for all $t\geq 0$. That is, the RHS Eq. (75) is negative.
Note that $x_{t}\geq 1$ since $x_{t}=\exp(e_{t}^{2})$ and $g(x_{t})>0$ since
the denominator
$\frac{p}{q}-1+\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
x_{t}}>\frac{p}{q}-1+\frac{p}{q}+1=2\cdot\frac{p}{q}>0$. Further
$g(1)=\frac{q}{p}$ and $\lim_{x\to\infty}g(x)=\infty$. If we show that $g(x)$
is increasing in $x$ for $x\geq 1$, it implies
$\frac{1}{1+g(x)}-p<\frac{1}{1+g(1)}-p=\frac{1}{1+\frac{q}{p}}-p=-\frac{p}{p+q}(p+q-1)<0$.
Thus the gradient in Eq. (75) remains negative starting at $t=0$ and hence the
sequence $(e_{t})_{t\geq 0}$ will be bounded. Now it remains to show
$g(\cdot)$ is increasing, i.e. $g^{\prime}(\cdot)>0$. Defining
$C=\left(\frac{p}{q}-1\right)/\left(2\sqrt{\frac{p}{q}}\right)$ and $D=C^{2}$,
we have that $g(x)$ upto a postive scaling is

$\displaystyle g(x)=\frac{x}{C+\sqrt{x+D}}.$

Hence

$\displaystyle g^{\prime}(x)$
$\displaystyle=\frac{C+\sqrt{x+D}-\frac{x}{2\sqrt{x+D}}}{(C+\sqrt{x+D})^{2}}.$

Thus it suffices to show that $h_{1}(x)\triangleq
C+\sqrt{x+D}>h_{2}(x)\triangleq\frac{x}{2\sqrt{x+D}}$ for $x\geq 1$. Note that
$h_{1}(1)-h_{2}(1)$ is given by

$\displaystyle h_{1}(1)-h_{2}(1)$
$\displaystyle=\frac{\frac{p}{q}-1}{2\sqrt{\frac{p}{q}}}+\sqrt{1+\left(\frac{\frac{p}{q}-1}{2\sqrt{\frac{p}{q}}}\right)^{2}}-\frac{1}{2\sqrt{1+\left(\frac{\frac{p}{q}-1}{2\sqrt{\frac{p}{q}}}\right)^{2}}}$
$\displaystyle=\sqrt{\frac{p}{q}}-\frac{\sqrt{\frac{p}{q}}}{1+\frac{p}{q}}$
$\displaystyle>0.$

Now we show that $h^{\prime}(x)>h_{2}^{\prime}(x)$ for all $x\geq 1$ which
implies that $h_{1}(x)>h_{2}(x)$ for all $x\geq 1$, thus establishing our
claim. To this end, we have that

$\displaystyle h^{\prime}_{1}(x)-h^{\prime}_{2}(x)$
$\displaystyle=\frac{1}{2\sqrt{x+D}}-\frac{\sqrt{x+D}-\frac{x}{2\sqrt{x+D}}}{2(x+D)}$
$\displaystyle=\frac{x}{2\sqrt{x+D}(x+D)}>0.$

This proves our claim that $g(\cdot)$ is increasing and hence $(e_{t})_{t\geq
0}$, and consequently $(\boldsymbol{\theta}_{t})_{t\geq 0}$, is bounded when
$\boldsymbol{\theta}_{0}\in\operatorname{e-axis}$.

Now let’s assume that
$\boldsymbol{\theta}_{0}=(e_{0},w_{0})\in\mathbb{R}^{2}\setminus\operatorname{e-axis}$.
Since $(\boldsymbol{\theta}_{t})_{t\geq
0}\subseteq\mathbb{R}^{2}\setminus\operatorname{e-axis}$, it follows that the
loss $L(\cdot)$ is analytic on the trajectory (since the logistic function is
analytic), and hence by [1, Theorem 2.2], it follows that
$\lim_{t\to\infty}\|\boldsymbol{\theta}_{t}\|$ exists. Now we show that
$\lim_{t\to\infty}\|\boldsymbol{\theta}_{t}\|\neq\infty$, which implies the
desired result about boundedness. To show
$\lim_{t\to\infty}\|\boldsymbol{\theta}_{t}\|\neq\infty$, we show that there
exists a large $B>0$ such that for any
$\boldsymbol{\theta}_{t}=(e,w)\in\mathbb{R}^{2}$ with $\|(e,w)\|\geq B$ , the
velocity vector $\odv{\boldsymbol{\theta}}{t}$ points inwards into the ball of
radius $B$ and thus the trajectory always stays inside this ball, and hence
bounded. To establish this, let’s denote $(e_{t},w_{t})=(e,w)$ with the
dependence on time implicitly assumed. Then by the definition of GF and the
gradient expressions in Lemma 7, we have that

$\displaystyle\odv{e}{t}$ $\displaystyle=-\frac{\partial L}{\partial
e}(\boldsymbol{\theta}_{t})=-2\mathbb{E}[(f_{1}X+f_{2})X]\cdot(1+2w|w|)e$ (76)
$\displaystyle\odv{w}{t}$ $\displaystyle=-\frac{\partial L}{\partial
w}(\boldsymbol{\theta}_{t})=-\mathbb{E}[(f_{1}X+f_{2})X]\cdot 4e^{2}|w|,$ (77)

where
$f_{1}=\sigma\left(2e^{2}w|w|+b_{\star}+\frac{e^{2}}{2}\right)+q-1-\sigma\left(b_{\star}-\frac{e^{2}}{2}\right)+p$,
and $f_{2}=\sigma\left(b_{\star}-\frac{e^{2}}{2}\right)-p$ with
$\pi_{1}f_{1}+f_{2}=0$. Given that only $\odv{e}{t}$ flips in sign under the
transformation $(e,w)\mapsto(-e,w)$, with out loss of generality we can assume
$e>0$. Now let’s also assume $w>0$. Thus, in view of Eq. (76) and GF, to show
that the derivative points inwards, it suffices to show that
$\mathbb{E}[(f_{1}X+f_{2})X]>0$ for reasonably large $B$ with $\|(e,w)\|=B$.
Similar to Eq. (73) and Eq. (74) above, using the relation
$\pi_{1}f_{1}+f_{2}=0$, we obtain

$\displaystyle\mathbb{E}[(f_{1}X+f_{2})X]=\pi_{1}(f_{1}+f_{2})=-\pi_{0}\left(\frac{1}{1+g(x)}-p\right),\quad
x\triangleq\exp(e^{2}(1+2w|w|)).$ (78)

Using the fact that $g(x)$ is increasing for $x\geq 1$ with
$\lim_{x\to\infty}g(x)=\infty$, and $|w|=w>0$, we can chose a $B>0$ such that
for any $\|(e,w)\|\geq B$, in Eq. (78) we have $1/(1+g(x))<p$ and hence
$\mathbb{E}[(f_{1}X+f_{2})X]>0$. This finishes the proof of our claim. The
proof for $w<0$ is similar, where we make use of the fact that
$\lim_{x\rightarrow 0}g(x)=0$ to show $\mathbb{E}[(f_{1}X+f_{2})X]<0$ for
$e,w$ reasonably large.

(ii)
$\lim_{t\to\infty}\boldsymbol{\theta}_{t}=\boldsymbol{\theta}_{\mathrm{lim}}$.
Since the logistic function $\ell_{\mathrm{log}}(\cdot)$ is analytic, it
follows from Lemma 6 that the loss $L(\boldsymbol{\theta})$ is analytic too
whenever $w\neq 0$. On the other hand, when $w=0$, it’s easy to see that $L$
is an analytic function of $e\in\mathbb{R}$. By Lemma 9, we know that if
$w_{0}\neq 0$, $w_{t}\neq 0$ and if $w_{0}=0$, $w_{t}=0$ for all $t\geq 0$.
Thus the loss is analytic on the trajectory for all $t\geq 0$. Since the
trajectory is bounded, it follows from Łojasiewicz’s theorem [1, Theorem 2.2]
that there exists a $\boldsymbol{\theta}_{\mathrm{lim}}\in\mathbb{R}^{2}$ such
that
$\lim_{t\to\infty}\boldsymbol{\theta}_{t}=\boldsymbol{\theta}_{\mathrm{lim}}$.

(iii) $\lim_{t\to\infty}\|\nabla L(\boldsymbol{\theta}_{t})\|=\|\nabla
L(\boldsymbol{\theta}_{\mathrm{lim}})\|=0$. Since the trajectory is bounded,
it follows from [2, Theorem 2] that the gradient converges to zero, i.e.
$\lim_{t\to\infty}\|\nabla L(\boldsymbol{\theta}_{t})\|=0$. Since $\nabla
L(\cdot)$ is a continuous function and
$\lim_{t\to\infty}\boldsymbol{\theta}_{t}=\boldsymbol{\theta}_{\mathrm{lim}}$,
we have $\lim_{t\to\infty}\|\nabla L(\boldsymbol{\theta}_{t})\|=\|\nabla
L(\boldsymbol{\theta}_{\mathrm{lim}})\|=0$.

∎

###  M.3 Proof of Lemma 11

###### Proof.

Since the energy function $\mathcal{E}(\cdot,\cdot)$ in Eq. (48) is a
continuous function in $\mathbb{R}^{2}\setminus\operatorname{e-axis}$, and any
trajectory $(\boldsymbol{\theta}_{t})_{t\geq 0}$ with intialization
$\theta\in\mathbb{R}^{2}\setminus\operatorname{e-axis}$ stays in
$\mathbb{R}^{2}\setminus\operatorname{e-axis}$ for all $t\geq 0$ (Lemma 9), it
follows that
$\lim_{t\to\infty}\mathcal{E}(\boldsymbol{\theta}_{t})=\mathcal{E}(\boldsymbol{\theta}_{\mathrm{lim}})=\mathcal{E}(\boldsymbol{\theta}_{0})$.
As $\nabla L(\boldsymbol{\theta}_{\mathrm{lim}})=0$ from Lemma 10, it follows
that $\boldsymbol{\theta}_{\mathrm{lim}}$ lies at the intersection of the
contour line $\mathcal{E}(e,w)=\mathcal{E}_{0}$ with the set of critical
points of $L$ in $\mathbb{R}^{2}$.

On the other hand, if $\boldsymbol{\theta}_{0}\in\operatorname{e-axis}$, we
have $\boldsymbol{\theta}_{t}\in\operatorname{e-axis}$ from Lemma 9 for all
$t\geq 0$. Hence $\boldsymbol{\theta}_{\mathrm{lim}}\in\operatorname{e-axis}$.
∎

###  M.4 Proof of Lemma 12

###### Proof.

Recall that $f:\mathbb{R}\setminus\\{0\\}\to\mathbb{R}$, defined as
$f(w)\triangleq\mathcal{E}(e=0,w)=-(w^{2}+\mathrm{sign}(w)\cdot\log|w|)$. If
$w<0$, we have

$\displaystyle f(w)$ $\displaystyle=-(w^{2}-\log(-w)),\quad
f^{\prime}(w)=-2w+\frac{1}{w}.$

Hence $f^{\prime}(w)\geq 0$ for $w\in(-\infty,-{1}/{\sqrt{2}}]$ and
$f^{\prime}(w)\leq 0$ for $w\in[-{1}/{\sqrt{2}},0)$ with
$f^{\prime}(-\frac{1}{\sqrt{2}})=0$. It’s also straightforward to see that
$\lim_{w\rightarrow-\infty}f(w)=-\infty$, $\lim_{w\rightarrow
0^{-}}f(w)=-\infty$, and $f(-1/\sqrt{2})=\mathcal{E}_{\mathrm{sad}}$ (by the
definition of $f$). This establishes (i), (ii), and (iii).

On the other hand, for $w>0$, we have $f(w)=-(w^{2}+\log w)$ and
$f^{\prime}(w)=-(2w+1/w)$. Hence $f$ is monotonically decreasing for $w>0$
with $\lim_{w\rightarrow 0^{+}}f(w)=\infty$ and
$\lim_{w\rightarrow\infty}f(w)=-\infty$. Note that $w=0$ acts as an energy
barrier since $\lim_{w\rightarrow 0^{-}}f(w)=-\infty$ whereas
$\lim_{w\rightarrow 0^{+}}f(w)=\infty$. ∎

##  Appendix N Proofs of lemmas in App. G

###  N.1 Proof of Lemma 13

###### Proof.

First we recall the loss with the bias $L(\boldsymbol{\theta},b)$ from Eq.
(41):

$\displaystyle L(\boldsymbol{\theta},b)$
$\displaystyle=\mathbb{E}_{X,Y}\left[\ell_{\mathrm{log}}\left((2Y-1)\cdot\mathrm{logit}_{X}(\boldsymbol{\theta},b)\right)\right],$

where
$\mathrm{logit}_{X}(\boldsymbol{\theta},b)=e^{2}\left[\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b$
with $\boldsymbol{\theta}=(e,w,a)$. Using the fact that
$\ell_{\mathrm{log}}^{\prime}(z)=\sigma(z)-1$ and $2Y-1\in\\{\pm 1\\}$, we
have for any $\theta\in\\{e,w,a,b\\}$ that

$\displaystyle\nabla_{\theta}L=\mathbb{E}\left[\left(\sigma((2Y-1)\cdot\mathrm{logit}_{X})-1\right)(2Y-1)\cdot\nabla_{\theta}\mathrm{logit}_{X}\right]=\mathbb{E}\left[\left(\sigma(\mathrm{logit}_{X})-Y\right)\cdot\nabla_{\theta}\mathrm{logit}_{X}\right].$
(79)

Now we simplify $\sigma(\mathrm{logit}_{X})$ using the fact that
$X\in\\{0,1\\}$:

$\displaystyle\begin{split}\sigma(\mathrm{logit}_{X})&=\sigma\left(e^{2}\left[\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\\\
&=X\underbrace{\sigma\left(e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)}_{\triangleq\phi_{1}}\\\
&+(1-X)\underbrace{\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)}_{\triangleq\phi_{0}}\\\
&=X\phi_{1}+(1-X)\phi_{0}\\\ &=X(\phi_{1}-\phi_{0})+\phi_{0}.\end{split}$

Thus the gradients in Eq. (79) are given by

$\displaystyle\begin{split}\nabla_{\theta}L&=-\mathbb{E}\left[\left(Y-X(\phi_{1}-\phi_{0})-\phi_{0}\right)\nabla_{\theta}\mathrm{logit}_{X}\right]\\\
&=-\mathbb{E}_{X}\left[\mathbb{E}_{x_{1}^{n+1}}\left[\left(\mathbb{E}[Y\mid
X]-X(\phi_{1}-\phi_{0})-\phi_{0}\right)\nabla_{\theta}\mathrm{logit}_{X}\right]\right]\\\
&=-\mathbb{E}_{X}\left[\left(\left(1-p-q\right)X+p-X(\phi_{1}-\phi_{0})-\phi_{0}\right)\nabla_{\theta}\mathrm{logit}_{X}\right]\\\
&=-\mathbb{E}_{X}\left[\left(\left(\underbrace{1-p-q-\phi_{1}+\phi_{0}}_{f_{1}}\right)X+\underbrace{p-\phi_{0}}_{f_{2}}\right)\nabla_{\theta}\mathrm{logit}_{X}\right]\\\
&=-\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\nabla_{\theta}\mathrm{logit}_{X}\right].\end{split}$
(80)

Now we compute the individual gradients with respect to $e,w,a$ and $b$.
Recall that

$\displaystyle\begin{split}\mathrm{logit}_{X}&=e^{2}\left[\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b.\end{split}$

Thus,

$\displaystyle\begin{split}\nabla_{e}\mathrm{logit}_{X}&=2e\left[\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]\\\
&+e^{2}\left[2ae\left(X-\frac{1}{2}\right)\left(1+2w|w|\right)+w\mathrm{sign}\left(w\left(1+ae^{2}\right)\right)(2ae)\right]\\\
&=2e\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+2ew|w(1+ae^{2})|\\\
&+2e^{3}a\left(X-\frac{1}{2}\right)\left(1+2w|w|\right)+2e^{3}aw\mathrm{sign}\left(w\left(1+ae^{2}\right)\right)\\\
&=2e\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+2e^{3}a\left(X-\frac{1}{2}\right)\left(1+2w|w|\right)\\\
&+2ew|w(1+ae^{2})|+2e^{3}aw\mathrm{sign}\left(w\left(1+ae^{2}\right)\right).\end{split}$

Substituting the above equation in Eq. (80), we obtain

$\displaystyle\begin{split}\nabla_{e}L&=-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\right)\cdot
2e\left(1+ae^{2}\right)\left(1+2w|w|\right)\\\
&-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\right)\cdot
2e^{3}a\left(1+2w|w|\right)\\\
&-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\right]\right)\cdot
2ew|w(1+ae^{2})|\\\
&-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\right]\right)\cdot
2e^{3}aw\,\mathrm{sign}\left(w\left(1+ae^{2}\right)\right).\end{split}$

Now we compute the derivative with respect to $w$.

$\displaystyle\begin{split}\mathrm{logit}_{X}&=e^{2}\left[\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\\\
\Rightarrow\nabla_{w}\mathrm{logit}_{X}&=2e^{2}\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(|w|+\mathrm{sign}\left(w\right)w\right)\\\
&+e^{2}\left[|w(1+ae^{2})|+w\left(1+ae^{2}\right)\mathrm{sign}\left(w\left(1+ae^{2}\right)\right)\right]\\\
\Rightarrow\nabla_{w}L&=-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\right)2e^{2}\left(1+ae^{2}\right)\left(|w|+\mathrm{sign}\left(w\right)w\right)\\\
&-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\right]\right)e^{2}\left[|w(1+ae^{2})|+w\left(1+ae^{2}\right)\mathrm{sign}\left(w\left(1+ae^{2}\right)\right)\right].\end{split}$

Similarly, for $a$:

$\displaystyle\begin{split}\mathrm{logit}_{X}&=e^{2}\left[\left(X-\frac{1}{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\\\
\Rightarrow\nabla_{a}\mathrm{logit}_{X}&=e^{4}\left(X-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)\\\
&+e^{4}w^{2}\mathrm{sign}\left(w(1+ae^{2})\right)\\\
\Rightarrow\nabla_{a}L&=-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\right)e^{4}\left(1+2w|w|\right)\\\
&-\left(\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\right]\right)e^{4}w^{2}\mathrm{sign}\left(w(1+ae^{2})\right).\end{split}$

Finally, since $\nabla_{b}\mathrm{logit}_{X}=1$, it follows from Eq. (80) that

$\displaystyle\begin{split}\nabla_{b}L&=-\mathbb{E}\left[f_{1}X+f_{2}\right].\end{split}$
(81)

For the optimal $b_{\star}$, we have $\nabla_{b}L=0$ and hence
$\mathbb{E}\left[f_{1}X+f_{2}\right]=0$, simplifying the expressions for the
gradients of $e,w$, and $a$ above. In fact, there exists a closed form
expression for $b_{\star}$ in terms of $e,w$, and $a$. Recall from Eq. (80)
that

$\displaystyle\begin{split}-f_{1}&=\sigma(z_{1})-\sigma(z_{2})+p+q-1,\\\
-f_{2}&=\sigma(z_{2})-p,\\\ z_{1}&\triangleq
e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b,\\\
z_{2}&\triangleq
e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b.\end{split}$
(82)

Substituting Eq. (82) in Eq. (81) and setting the gradient to zero there, we
have

$\displaystyle\begin{split}-\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]&=\left(\sigma(z_{1})-\sigma(z_{2})+p+q-1\right)\mathbb{E}[X]+\sigma(z_{2})-p\\\
&=(\sigma(z_{1})-\sigma(z_{2})+p+q-1)\pi_{1}+\sigma(z_{2})-p=0.\end{split}$

Simplifying,

$\displaystyle\begin{split}(\sigma(z_{1})-\sigma(z_{2})+p+q-1)\pi_{1}&=p-\sigma(z_{2})\\\
\Rightarrow\left(\sigma(z_{1})-1\right)\pi_{1}-\sigma(z_{2})\pi_{1}+p&=p-\sigma(z_{2})\\\
\Rightarrow\left(\sigma(z_{1})-1\right)\pi_{1}&=\sigma(z_{2})(\pi_{1}-1)\\\
\Rightarrow\frac{\sigma(z_{2})}{1-\sigma(z_{1})}&=\frac{\pi_{1}}{1-\pi_{1}}=\frac{p}{q},\end{split}$

Using the definition of the sigmoid function and rearranging,

$\displaystyle\begin{split}\frac{1+\exp(z_{1})}{1+\exp(-z_{2})}&=\frac{p}{q}\\\
\Rightarrow\exp(z_{1})+1&=\frac{p}{q}\left(1+\exp(-z_{2})\right)\\\
\Rightarrow\exp(2z_{1})+\exp(z_{1})&=\frac{p}{q}\exp(z_{1})+\frac{p}{q}\exp(z_{1}-z_{2})\\\
\Rightarrow(\exp(z_{1}))^{2}+\exp(z_{1})(1-\frac{p}{q})-\frac{p}{q}\cdot\exp(z_{1}-z_{2})&=0.\end{split}$
(83)

By definitions of $z_{1}$ and $z_{2}$ in Eq. (82), we have
$z_{1}-z_{2}=e^{2}(1+ae^{2})(1+2w|w|)$ and thus
$A\triangleq\exp(z_{1}-z_{2})=\exp(e^{2}(1+ae^{2})(1+2w|w|))$. Thus the
quadratic equation in Eq. (83) simplifies to

$\displaystyle(\exp(z_{1}))^{2}+\exp(z_{1})(1-\frac{p}{q})-\frac{p}{q}\cdot A$
$\displaystyle=0.$

On solving the quadratic equation for $\exp(z_{1})$:

$\displaystyle\exp(z_{1})$
$\displaystyle=\frac{1}{2}\left[\frac{p}{q}-1+\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
A}\right]$ $\displaystyle\Rightarrow z_{1}$
$\displaystyle=\log\left(\frac{1}{2}\left[\frac{p}{q}-1+\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
A}\right]\right)$ $\displaystyle\Rightarrow b_{\star}$
$\displaystyle=\log\left(\frac{1}{2}\left[\frac{p}{q}-1+\sqrt{\left(\frac{p}{q}-1\right)^{2}+4\cdot\frac{p}{q}\cdot
A}\right]\right)$
$\displaystyle\quad-e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right].$

Note that when $a=0$ above, we recover the expression for the optimal bias in
Lemma 5. This concludes the proof.

∎

###  N.2 Proofs of Thm. 9 and Thm. 10

We prove Thm. 9 and Thm. 10 below. Note that Thm. 10 directly follows from the
former by removing the bias $b$, since for any critical point
$\boldsymbol{\gamma}=(e,w,b,a)\in\mathbb{R}^{4}$ with $\nabla
L(\boldsymbol{\gamma})=0$, the bias $b$ is already the optimal one
corresponding to $\boldsymbol{\theta}=(e,w,a)\in\mathbb{R}^{3}$, i.e.
$b=b_{\star}(\boldsymbol{\theta})=\mathop{\operatorname{argmin}}_{b\in\mathbb{R}}L(\boldsymbol{\theta},b)$.
This is similar to the proof of Thm. 1, which follows from Thm. 7.

Now we prove Thm. 9.

###### Proof.

We characterize the set of global minima first.

Set of all global minima. Let $\boldsymbol{\gamma}_{\star}\in\mathbb{R}^{4}$
be arbitrary. From [23, Lemma 1], we have that $\boldsymbol{\gamma}_{\star}$
is a global minimum for the loss $L(\cdot)$ in Eq. (23) if and only if its
prediction probability satisfies
$f_{\boldsymbol{\gamma}_{\star}}(x_{1}^{n})=\mathbb{P}\left(x_{n+1}=1\mid
x_{n}\right)$, the Markov kernel. Since the input
$\\{x_{n}\\}_{n=1}^{N}\sim(\boldsymbol{\pi}(p,q),\boldsymbol{P}(p,q))$, we
have that

$\displaystyle\mathbb{P}\left(x_{n+1}=1\mid
x_{n}\right)=(1-x_{n})p+x_{n}(1-q)=(1-p-q)x_{n}+p.$ (84)

On the other hand, by definition, from Eq. (3),
$f_{\boldsymbol{\gamma}_{\star}}(x_{1}^{n})=\sigma\left(e^{2}\left[\left(x_{n}-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)$,
where $\boldsymbol{\gamma}_{\star}=(e,w,b,a)$. Since $x_{n}\in\\{0,1\\}$, this
can be further simplified to

$\displaystyle\begin{split}f_{\boldsymbol{\gamma}_{\star}}(x_{1}^{n})&=\sigma\left(e^{2}\left[\left(x_{n}-\frac{1}{2}\right)\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\end{split}$
$\displaystyle\begin{split}&=x_{n}\sigma\left(e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\\\
&\quad+(1-x_{n})\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\end{split}$
$\displaystyle\begin{split}&=x_{n}\sigma\left(e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\\\
&\quad-
x_{n}\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\\\
&\quad+\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right).\end{split}$
(85)

Since both $f_{\boldsymbol{\gamma}_{\star}}(x_{1}^{n})$ and
$\mathbb{P}\left(x_{n+1}=1\mid x_{n}\right)$ are linear functions of $x_{n}$,
equating them for all vallues of $x_{n}\in\\{0,1\\}$ implies that the
respective coeffecients in these functions in Eq. (84) and Eq. (85) are also
equal, i.e.

$\displaystyle\begin{split}1-p-q&=\sigma\left(e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)\\\
&\quad-\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right),\\\
p&=\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right),\end{split}$
(86)

and hence

$\displaystyle\begin{split}\sigma\left(e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)&=1-q,\\\
\sigma\left(e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b\right)&=p.\end{split}$
(87)

Since $\sigma(z)=y$ for $y\in(0,1)$ implies $z=\log\frac{y}{1-y}$, Eq. (87)
can be rewritten as

$\displaystyle
e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b$
$\displaystyle=\log\frac{1-q}{q},$ $\displaystyle
e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b$
$\displaystyle=\log\frac{p}{1-p}.$

Adding and subtracting the above two equations, we obtain

$\displaystyle\begin{split}e^{2}w|w(1+ae^{2})|+b&=\frac{1}{2}\log\frac{p(1-q)}{q(1-p)},\\\
e^{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)&=\log\frac{(1-q)(1-p)}{pq}.\end{split}$
(88)

Thus $\boldsymbol{\gamma}_{\star}\in\mathbb{R}^{4}$ is a global minimum for
$L(\cdot)$ if and only if it satisfies Eq. (88). It’s easy to see that
$\boldsymbol{\gamma}_{\star}$ is already a critical point for $L$ as Eq. (86)
is equivalent to $f_{1}=f_{2}=0$ in Lemma 13. Thus, the set of all global
minimum $\boldsymbol{\Gamma}_{\star}(p,q)$ is given by

$\displaystyle\boldsymbol{\Gamma}_{\star}(p,q)\triangleq\\{\boldsymbol{\gamma}_{\star}=(e,w,b,a)\in\mathbb{R}^{4}$
$\displaystyle:e^{2}w|w(1+ae^{2})|+b=\frac{1}{2}\log\frac{p(1-q)}{q(1-p)},\,$
$\displaystyle\quad
e^{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)=\log\frac{(1-q)(1-p)}{pq}\\}.$

Since the prediction $f_{\boldsymbol{\gamma}_{\star}}(\cdot)$ equals the
Markov kernel for any
$\boldsymbol{\gamma}_{\star}\in\boldsymbol{\Gamma}_{\star}$, it follows from
Thm. 4 (or [23, Lemma 1]) that $L(\boldsymbol{\gamma}_{\star})=H(x_{n+1}\mid
x_{n})$, the entropy rate of the Markov chain. Now we characterize the
remaining set of stationary points.

Non-global-min critical points. For any critical point
$\boldsymbol{\gamma}=(e,w,a,b)\in\mathbb{R}^{4}$, we have from the gradient
expressions in Lemma 13 that (denoting $-f_{1}$ and $-f_{2}$ from the lemma as
$f_{1}$ and $f_{2})$ respectively)

$\displaystyle\begin{split}\frac{\partial L}{\partial
b}&=\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,\\\ \frac{\partial L}{\partial
e}&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e\left(1+ae^{2}\right)\left(1+2w|w|\right)\\\
&\quad+\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e^{3}a\left(1+2w|w|\right)=0,\\\
\frac{\partial L}{\partial
w}&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e^{2}\left(1+ae^{2}\right)\left(|w|+\mathrm{sign}\left(w\right)w\right)=0,\\\
\frac{\partial L}{\partial
a}&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]e^{4}\left(1+2w|w|\right)=0.\end{split}$
(89)

From Eq. (89), we have that $\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0$. If
$\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]=\mathbb{E}[(f_{1}X+f_{2})X]=0$,
we have that $f_{1}=f_{2}=0$, implying $\boldsymbol{\gamma}$ is a global
minimum. Hence without loss of generality, assume that
$\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\neq
0$. Then we can partition the above set of equations into the following
regions of stationarity:

  1. (i)

$\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,e=0,$

  2. (ii)

$\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,e\neq 0,1+ae^{2}=0,1+2w|w|=0.$

Slightly changing the variable order, for any
$\boldsymbol{\gamma}=(b,e,w,a)\in\mathbb{R}^{4}$, we define

$\displaystyle\boldsymbol{H}(\boldsymbol{\gamma})\triangleq\nabla^{2}L(\boldsymbol{\gamma})=\begin{bmatrix}\frac{\partial^{2}L}{\partial
b^{2}}&\frac{\partial^{2}L}{\partial b\partial
e}&\frac{\partial^{2}L}{\partial b\partial w}&\frac{\partial^{2}L}{\partial
b\partial a}\\\ &&\\\ \frac{\partial^{2}L}{\partial e\partial
b}&\frac{\partial^{2}L}{\partial e^{2}}&\frac{\partial^{2}L}{\partial
e\partial w}&\frac{\partial^{2}L}{\partial e\partial a}\\\ &&\\\
\frac{\partial^{2}L}{\partial w\partial b}&\frac{\partial^{2}L}{\partial
w\partial e}&\frac{\partial^{2}L}{\partial
w^{2}}&\frac{\partial^{2}L}{\partial w\partial a}\\\ &&\\\
\frac{\partial^{2}L}{\partial a\partial b}&\frac{\partial^{2}L}{\partial
a\partial e}&\frac{\partial^{2}L}{\partial a\partial
w}&\frac{\partial^{2}L}{\partial a^{2}}\\\ \end{bmatrix}\in\mathbb{R}^{4\times
4}.$ (90)

Recall that

$\displaystyle\begin{split}f_{1}&=\sigma(z_{1})-\sigma(z_{2})+p+q-1,\\\
f_{2}&=\sigma(z_{2})-p,\\\ z_{1}&\triangleq
e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b,\\\
z_{2}&\triangleq
e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b.\end{split}$

From Eq. (89), we see that the second derivaties of $L$ depend on the first-
derivatives of $f_{1}$ and $f_{2}$, which we now compute. Recall that the
derivative of the sigmoid function obeys
$\sigma^{\prime}(z)=\sigma(z)(1-\sigma(z))=\sigma(z)\sigma(-z)$ for any
$z\in\mathbb{R}$. Now the gradients of $f_{1}$ and $f_{2}$ with respect to
$b,e,w$ and $a$ are

$\displaystyle\begin{split}\frac{\partial f_{1}}{\partial
b}&=\sigma(z_{1})\sigma(-z_{1})-\sigma(z_{2})\sigma(-z_{2}),\\\ \frac{\partial
f_{2}}{\partial b}&=\sigma(z_{2})\sigma(-z_{2}),\\\ \frac{\partial
f_{1}}{\partial
e}&=\sigma(z_{1})\sigma(-z_{1})\left\\{2e\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]\right\\}\\\
&\quad+\sigma(z_{1})\sigma(-z_{1})\left\\{2ae^{3}\left[\frac{1}{2}\left(1+2w|w|\right)+w|w|\mathrm{sign}(1+2w|w|)\right]\right\\}\\\
&\quad-\sigma(z_{2})\sigma(-z_{2})\left\\{2e\left[-\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]\right\\}\\\
&\quad-\sigma(z_{2})\sigma(-z_{2})\left\\{2ae^{3}\left[-\frac{1}{2}\left(1+2w|w|\right)+w|w|\mathrm{sign}(1+2w|w|)\right]\right\\}\\\
\frac{\partial f_{2}}{\partial
e}&=\sigma(z_{2})\sigma(-z_{2})\left\\{2e\left[-\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]\right\\}\\\
&\quad+\sigma(z_{2})\sigma(-z_{2})\left\\{2ae^{3}\left[-\frac{1}{2}\left(1+2w|w|\right)+w|w|\mathrm{sign}(1+2w|w|)\right]\right\\}\\\
\frac{\partial f_{1}}{\partial
w}&=\sigma(z_{1})\sigma(-z_{1})\left\\{2e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)|w|+|w||1+ae^{2}|\right]\right\\}\\\
&\quad-\sigma(z_{2})\sigma(-z_{2})\left\\{2e^{2}\left[-\frac{1}{2}\left(1+ae^{2}\right)|w|+|w||1+ae^{2}|\right]\right\\},\\\
\frac{\partial f_{2}}{\partial
w}&=\left\\{2e^{2}\left[-\frac{1}{2}\left(1+ae^{2}\right)|w|+|w||1+ae^{2}|\right]\right\\},\\\
\frac{\partial f_{1}}{\partial
a}&=\sigma(z_{1})\sigma(-z_{1})\left\\{e^{4}\left[\frac{1}{2}\left(1+2w|w|\right)+w|w|\mathrm{sign}\left(1+ae^{2}\right)\right]\right\\}\\\
&\quad-\sigma(z_{2})\sigma(-z_{2})\left\\{e^{4}\left[-\frac{1}{2}\left(1+2w|w|\right)+w|w|\mathrm{sign}\left(1+ae^{2})\right)\right]\right\\},\\\
\frac{\partial f_{2}}{\partial
a}&=\sigma(z_{2})\sigma(-z_{2})\left\\{e^{4}\left[-\frac{1}{2}\left(1+2w|w|\right)+w|w|\mathrm{sign}\left(1+ae^{2}\right)\right]\right\\}.\end{split}$
(91)

Now we characterize the first set of critical points.

(i) Stationary points with $\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,e=0.$
When $e=0$, we have that $z_{1}=z_{2}=b$. Hence,

$\displaystyle f_{1}$ $\displaystyle=\sigma(b)+p+q-1-\sigma(b)=p+q-1,$
$\displaystyle f_{2}$ $\displaystyle=\sigma(b)-p.$

Thus,
$\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=\left(p+q-1\right)\mathbb{E}_{X}\left[X\right]+\sigma(b)-p=\left(p+q-1\right)\pi_{1}+\sigma(b)-p=0$.
Rearranging and simplifying, $\sigma(b)=\frac{p}{p+q}$ and hence
$b=\log\frac{p}{q}$. Using the fact that
$\sigma\left(\log\frac{p}{q}\right)=\frac{p}{p+q}=\pi_{1}$ and
$\sigma\left(-\log\frac{p}{q}\right)=\frac{q}{p+q}=\pi_{0}$, the above
gradients evaluated for any $\boldsymbol{\gamma}=(b=\log\frac{p}{q},e=0,w,a)$
further reduce to

$\displaystyle\begin{split}\frac{\partial f_{1}}{\partial
b}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial f_{2}}{\partial
b}\bigg{\rvert}_{\boldsymbol{\gamma}}=\pi_{0}\pi_{1},\\\ \frac{\partial
f_{1}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial
f_{2}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\\\ \frac{\partial
f_{1}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial
f_{2}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\\\ \frac{\partial
f_{1}}{\partial a}\bigg{\rvert}_{\boldsymbol{\gamma}}=0,\quad\frac{\partial
f_{2}}{\partial a}\bigg{\rvert}_{\boldsymbol{\gamma}}=0.\end{split}$ (92)

Now substituting Eq. (92) when computing the second-derivatives of $L$ in Eq.
(89), we obtain

$\displaystyle\begin{split}\frac{\partial^{2}L}{\partial
b^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial b}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial
b}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=\pi_{0}\pi_{1},\\\
\frac{\partial^{2}L}{\partial b\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial e}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=0,\\\
\frac{\partial^{2}L}{\partial b\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial w}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=0,\\\
\frac{\partial^{2}L}{\partial b\partial
a}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\frac{\partial
f_{1}}{\partial a}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial
f_{2}}{\partial a}\bigg{\rvert}_{\boldsymbol{\gamma}}\right]=0,\\\
\frac{\partial^{2}L}{\partial
e^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2\left(1+ae^{2}\right)\left(1+2w|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\quad+\underbrace{\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]4e^{2}a\left(1+2w|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}}_{0}\\\
&\quad+\underbrace{\mathbb{E}_{X}\left[\left(\frac{\partial f_{1}}{\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial f_{2}}{\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}\right)\left(X-\frac{1}{2}\right)\right]2\left(1+ae^{2}\right)\left(1+2w|w|\right)}_{0}\\\
&=\mathbb{E}_{X}\left[(2f_{1}(1+2w|w|)-f_{1}+2f_{2}(1+2w|w|)X-f_{2}\right]\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[(f_{1}(1+4w|w|)+f_{2}(2+4w|w|)X-f_{2}\right]\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=(f_{1}(1+4w|w|)+f_{2}(2+4w|w|))\pi_{1}-f_{2}\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\stackrel{{\scriptstyle(a)}}{{=}}((p+q-1)(1+4w|w|)-\pi_{1}(p+q-1)(2+4w|w|))\pi_{1}+\pi_{1}(p+q-1)\\\
&=\pi_{1}(p+q-1)\left(1+4w|w|-\pi_{1}(2+4w|w|)+1\right)\\\
&\stackrel{{\scriptstyle(b)}}{{=}}2\pi_{1}\pi_{0}(p+q-1)(1+2w|w|),\end{split}$
(93)

where $(a)$ follows from the fact that
$f_{1}|_{\boldsymbol{\gamma}}=p+q-1,f_{2}|_{\boldsymbol{\gamma}}=\sigma(b)-p=\frac{p}{p+q}-p=\frac{-p}{p+q}(p+q-1)=-\pi_{1}(p+q-1)$
and $(b)$ from $1-\pi_{1}=\pi_{0}$. Returning to the remaining second
derivatives,

$\displaystyle\begin{split}\frac{\partial^{2}L}{\partial e\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
e}\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]4e^{2}\left(1+ae^{2}\right)|w|\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\left(8e\left(1+ae^{2}\right)|w|+8e^{3}a|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\quad+\mathbb{E}_{X}\left[\left(\frac{\partial f_{1}}{\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial f_{2}}{\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}\right)\left(X-\frac{1}{2}\right)\right]4e^{2}\left(1+ae^{2}\right)\left(|w|\right)\\\
&=0,\\\ \frac{\partial^{2}L}{\partial e\partial
a}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
e}\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]e^{4}\left(1+2w|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]4e^{3}\left(1+2w|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\quad+\mathbb{E}_{X}\left[\left(\frac{\partial f_{1}}{\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial f_{2}}{\partial
e}\bigg{\rvert}_{\boldsymbol{\gamma}}\right)\left(X-\frac{1}{2}\right)\right]e^{4}\left(1+2w|w|\right)\\\
&=0,\\\ \frac{\partial^{2}L}{\partial
w^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
w}\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]4e^{2}\left(1+ae^{2}\right)|w|\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]4e^{2}\left(1+ae^{2}\right)\mathrm{sign}(w)\\\
&\quad+\mathbb{E}_{X}\left[\left(\frac{\partial f_{1}}{\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial f_{2}}{\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}\right)\left(X-\frac{1}{2}\right)\right]4e^{2}\left(1+ae^{2}\right)|w|\\\
&=0,\\\ \frac{\partial^{2}L}{\partial w\partial
a}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
w}\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]e^{4}\left(1+2w|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e^{4}|w|\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\quad+\mathbb{E}_{X}\left[\left(\frac{\partial f_{1}}{\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial f_{2}}{\partial
w}\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\right]e^{4}\left(1+2w|w|\right)\\\
&=0,\\\ \frac{\partial^{2}L}{\partial
a^{2}}\bigg{\rvert}_{\boldsymbol{\gamma}}&=\frac{\partial}{\partial
a}\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]e^{4}\left(1+2w|w|\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e^{4}|w|\bigg{\rvert}_{\boldsymbol{\gamma}}\\\
&\quad+\mathbb{E}_{X}\left[\left(\frac{\partial f_{1}}{\partial
w}\bigg{\rvert}_{\boldsymbol{\gamma}}X+\frac{\partial f_{2}}{\partial
w}\right)\bigg{\rvert}_{\boldsymbol{\gamma}}\right]e^{4}\left(1+2w|w|\right)\\\
&=0.\\\ \end{split}$ (94)

Congregating all the second derivatives from Eq. (93) and Eq. (94) into the
Hessian $\boldsymbol{H}(\boldsymbol{\gamma})$ in Eq. (90), we finally obtain

$\displaystyle\boldsymbol{H}(\boldsymbol{\gamma})=\pi_{0}\pi_{1}\begin{bmatrix}1&0&0&0\\\
0&2(p+q-1)(1+2w|w|)&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\ \end{bmatrix},$

which is identical to the Hessian obtained in the proof of Thm. 7 (App. J.2)
for $e=0$. Thus it follows that
$\boldsymbol{\Gamma}_{\mathrm{min}}(p,q)\subseteq\mathbb{R}^{4}$ and
$\boldsymbol{\Gamma}_{\mathrm{sad}}\subseteq\mathbb{R}^{4}$ defined below are
a set of local minima and saddle points respectively:

$\displaystyle\boldsymbol{\Gamma}_{\mathrm{min}}(p,q)$
$\displaystyle\triangleq\left\\{\boldsymbol{\gamma}_{\mathrm{min}}=(e,w,b,a)\in\mathbb{R}^{4}:e=0,(p+q-1)(1+2w|w|)>0,b=\log\frac{p}{q}\right\\},$
$\displaystyle\boldsymbol{\Gamma}_{\mathrm{sad}}(p,q)$
$\displaystyle\triangleq\left\\{\boldsymbol{\gamma}_{\mathrm{sad}}=(e,w,b,a)\in\mathbb{R}^{4}:e=0,(p+q-1)(1+2w|w|)\leq
0,b=\log\frac{p}{q}\right\\}.$

Now we focus on the remaining set of critical points.

(ii) Stationary points with $\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=0,e\neq
0,1+ae^{2}=0,1+2w|w|=0.$ For this set of points, the Hessian remains undefined
because $\frac{\partial f_{1}}{\partial e},\frac{\partial f_{2}}{\partial
e},\frac{\partial f_{1}}{\partial a},\frac{\partial f_{2}}{\partial a}$ do not
exist (Eq. (91)). This non-existence arises since
$\mathrm{sign}\left(1+ae^{2}\right)$ is undefine $1+ae^{2}=0$. However, even
in this scenario,when $e\neq 0,1+ae^{2}=0,1+2w|w|=0$, we have $z_{1}=z_{2}=b$.
Hence,

$\displaystyle f_{1}$ $\displaystyle=\sigma(b)+p+q-1-\sigma(b)=p+q-1,$
$\displaystyle f_{2}$ $\displaystyle=\sigma(b)-p.$

Thus the expectation term
$\mathbb{E}_{X}\left[f_{1}X+f_{2}\right]=\left(p+q-1\right)\mathbb{E}_{X}\left[X\right]+\sigma(b)-p=\left(p+q-1\right)\pi_{1}+\sigma(b)-p=0$.
Simplifying, $\sigma(b)=\frac{p}{p+q}$, which implies $b=\log\frac{p}{q}$.

We could attempt to understand the characterization of the points on this
manifold through local perturbation analysis. However, in this work, we
classify them as stationary points and leave the comprehensive
characterization for future research. This set of points
$\boldsymbol{\Gamma}_{\mathrm{station}}(p,q)\subseteq\mathbb{R}^{4}$ is
defined as

$\displaystyle\boldsymbol{\Gamma}_{\mathrm{station}}(p,q)$
$\displaystyle\triangleq\left\\{\boldsymbol{\gamma}_{\mathrm{min}}=(e,w,b,a)\in\mathbb{R}^{4}:e\neq
0,1+ae^{2}=0,1+2w|w|=0,b=\log\frac{p}{q}\right\\}.$

This concludes the proof.

∎

###  N.3 Proof of Lemma 14

###### Proof.

Recall from Lemma 13 that for $\boldsymbol{\theta}=(e,w,a)\in\mathbb{R}^{3}$,
we have

$\displaystyle\frac{\partial L}{\partial e}$
$\displaystyle=-\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\cdot
2e\left(1+ae^{2}\right)\left(1+2w|w|\right)$ $\displaystyle\hskip
10.00002pt-\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\cdot
2e^{3}a\left(1+2w|w|\right),$ $\displaystyle\frac{\partial L}{\partial w}$
$\displaystyle=-\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\cdot
2e^{2}\left(1+ae^{2}\right)\left(|w|+\mathrm{sign}\left(w\right)w\right),$
$\displaystyle\frac{\partial L}{\partial a}$
$\displaystyle=-\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\cdot
e^{4}\left(1+2w|w|\right),$

where $X\in\\{0,1\\}$ is a Bernoulli random variable with
$X\sim\mathrm{Bern}(p/(p+q))$, and

$\displaystyle f_{1}$ $\displaystyle\triangleq 1-p-q-\phi_{1}+\phi_{0},\quad
f_{2}\triangleq p-\phi_{0},$ $\displaystyle\phi_{1}$
$\displaystyle\triangleq\sigma\left(e^{2}\left(\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right)+b_{\star}\right),$
$\displaystyle\phi_{0}$
$\displaystyle\triangleq\sigma\left(e^{2}\left(\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right)+b_{\star}\right),$

where the optimal bias $b_{\star}$ is obtained by solving
$\pi_{1}f_{1}+f_{2}=0$. Using the definition of the gradient flow that
$\dot{\boldsymbol{\theta}}=-\nabla L(\boldsymbol{\theta})$ for
$\boldsymbol{\theta}=\boldsymbol{\theta}_{t}$, we have

$\displaystyle\begin{split}\dot{w}=-\frac{L(\boldsymbol{\theta})}{\partial
w}&=\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\cdot
2e^{2}\left(1+ae^{2}\right)\left(|w|+\mathrm{sign}\left(w\right)w\right)\\\
\Rightarrow\frac{\dot{w}}{e^{2}\left(|w|+\mathrm{sign}\left(w\right)w\right)}&=\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2\left(1+ae^{2}\right).\end{split}$
(95)

Similarly for $a$,

$\displaystyle\begin{split}\dot{a}=-\frac{L(\boldsymbol{\theta})}{\partial
a}&=\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]e^{4}\left(1+2w|w|\right)\\\
\Rightarrow\frac{\dot{a}}{e^{4}}&=\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\left(1+2w|w|\right).\end{split}$
(96)

Likewise, for $e$,

$\displaystyle\begin{split}\dot{e}=-\frac{L(\boldsymbol{\theta})}{\partial
e}&=\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2\left(1+ae^{2}\right)e\left(1+2w|w|\right)\\\
&+\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\left(1+2w|w|\right)2e^{3}a.\\\
\end{split}$ (97)

By substituting the expressions of Eq. (95) and Eq. (96) into Eq. (97):

$\displaystyle\begin{split}\dot{e}&=\underbrace{\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2\left(1+ae^{2}\right)}_{Eq.~{}\eqref{eq:del_dw_lin_attn}}e\left(1+2w|w|\right)\\\
&+\underbrace{\mathbb{E}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]\left(1+2w|w|\right)}_{Eq.~{}\eqref{eq:del_da_lin_attn}}2e^{3}a.\end{split}$
(98)

Thus, we obtain

$\displaystyle\begin{split}\dot{e}&=\frac{\dot{w}}{2e^{2}\left(|w|+\mathrm{sign}\left(w\right)w\right)}e\left(1+2w|w|\right)+\frac{\dot{a}}{e^{4}}2e^{3}a.\end{split}$
(99)

On rearranging and simplifying:

$\displaystyle\begin{split}e\dot{e}&=\frac{\dot{w}}{\left(|w|+\mathrm{sign}\left(w\right)w\right)}\left(1+2w|w|\right)+\dot{a}2a\\\
\Rightarrow
e\dot{e}&=\frac{\dot{w}}{2\left(|w|\right)}\left(1+2w|w|\right)+2a\dot{a}.\end{split}$
(100)

Integrating the above equation on both sides:

$\displaystyle\begin{split}\int
e\dot{e}&=\int\frac{\dot{w}}{4\left(|w|\right)}\left(1+2w|w|\right)+\int
2a\dot{a}\\\
\Rightarrow\frac{e^{2}(t)}{2}&=\frac{\mathrm{sign}(w(t))\cdot\log|w(t)|+w(t)^{2}}{2}+a(t)^{2}+\frac{c}{2}\\\
\Rightarrow
e^{2}(t)&=\mathrm{sign}(w(t))\cdot\log|w(t)|+w(t)^{2}+2a(t)^{2}+c.\end{split}$
(101)

Note that here $c\in\mathbb{R}$, is a constant that depends on the initial
conditions. Thus the energy
$\mathcal{E}(\boldsymbol{\theta}_{t})=\mathcal{E}(\boldsymbol{\theta}_{0})$
for $w_{0}\neq 0$.

∎

###  N.4 Proofs of Lemma 16, Lemma 15, and Thm. 3

###### Proof.

We note that the proofs of Lemma 16, Lemma 15 directly follow from that of
their counterparts Lemma 11 and Lemma 10 using Łojasiewicz’s theorem to
characterize the convergence of the gradient flow. Thm. 3 is a direct
consequence of Lemma 16, Lemma 15. ∎

###  N.5 Informal proof of Thm. 11

###### Proof.

[Informal] For $\boldsymbol{\theta}=(e,w,a)$, recall from Lemma 13 that the
derivative of the loss $L$ with respect to $e$ is

$\displaystyle\begin{split}\frac{\partial L}{\partial
e}&=\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e\left(1+ae^{2}\right)\left(1+2w|w|\right)\\\
&\quad+\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X-\frac{1}{2}\right)\right]2e^{3}a\left(1+2w|w|\right),\end{split}$

where

$\displaystyle\begin{split}f_{1}&=\sigma(z_{1})-\sigma(z_{2})+p+q-1,\\\
f_{2}&=\sigma(z_{2})-p,\\\ z_{1}&\triangleq
e^{2}\left[\frac{1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b,\\\
z_{2}&\triangleq
e^{2}\left[\frac{-1}{2}\left(1+ae^{2}\right)\left(1+2w|w|\right)+w|w(1+ae^{2})|\right]+b.\end{split}$

Assuming the initialization is very small, making any product of quantities in
$\boldsymbol{\theta}=(e,w,a,b)$ much smaller than the individual quantities.
Therefore, we can consider these products to be approximately zero. That is,
$\forall x,y\in\boldsymbol{\theta},x\geq xy\And y\geq xy\And xy\approx 0$.
Hence,

$\displaystyle z_{1}$ $\displaystyle=b,$ $\displaystyle z_{2}$
$\displaystyle=b,$ $\displaystyle f_{1}$ $\displaystyle=p+q-1,$ $\displaystyle
f_{2}$ $\displaystyle=\sigma(b)-p.$

Hence the gradient with respect to $e$ is

$\displaystyle\begin{split}\frac{\partial L}{\partial
e}&=2\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)\left(X\right)\right]e.\end{split}$
(102)

Simplifying the expectation term,
$\mathbb{E}_{X}\left[\left(f_{1}X+f_{2}\right)X\right]=(f_{1}+f_{2})\pi_{1}=f_{1}\pi_{1}-f_{1}\pi^{2}=(p+q-1)(\pi_{1}-\pi_{1}^{2})$,
where we used the fact that $b$ is optimal in the above equations,
specifically where $f_{1}\pi_{1}+f_{2}=0$. Thus the gradient flow for the
parameter $e$ is governed by

$\displaystyle\dot{e}=-\frac{\partial L}{\partial e}$
$\displaystyle=-(p+q-1)(\pi_{1}-\pi_{1}^{2})e\Rightarrow
e=e_{0}\exp(-(p+q-1)(\pi_{1}-\pi_{1}^{2})t).$

Since $(p+q-1)(\pi_{1}-\pi_{1}^{2})>0$, $e\rightarrow 0$, which denotes it
converges to the local minima.

∎