This means that the conditions on $\mathbf{g}$ in Definition B.2.2 are
precisely those necessary to let $\mathbf{g}$ be any function that it could be
in our original definition of quasi-arithmetic pooling (Definition 5.2.5). Our
new definition is thus equivalent to the old one (after normalizing weights to
add to $1$).

We now discuss our axioms for pooling operators that will again capture the
class of QA pooling operators. We will keep the weight additivity,
commutativity, associativity, and idempotence verbatim from our discussion of
the $n=2$ case. We will slightly strengthen the continuity argument (see
below).

We will also add a new axiom, _subtraction_ , which states that if
$\Pi_{1}\oplus\Pi_{2}=\Pi_{1}\oplus\Pi_{3}$ then $\Pi_{2}=\Pi_{3}$.
Subtraction in the $n=2$ case follows from monotonicity; in this case,
however, we the subtraction axiom will help us state the monotonicity axiom.
In particular, it allows us to make the following definition, which
essentially extends the notion of pooling to allow for negative weights.

######  Definition B.2.5.

Let $\oplus$ be a pooling operator satisfying weight additivity,
commutativity, associativity, and subtraction. Fix
$\mathbf{p}_{1},\dots,\mathbf{p}_{k}\in\mathcal{D}$. Define a function
$\mathbf{p}:\Delta_{k}\to\mathcal{D}$ (with
$\mathbf{p}_{1},\dots,\mathbf{p}_{k}$ serving as implicit arguments) defined
by

$\mathbf{p}(w_{1},\dots,w_{k})=\text{pr}\left(\bigoplus_{i=1}^{k}(\mathbf{p}_{i},w_{i})\right).$

We extend the definition of $\mathbf{p}$ to a partial function on $H_{k}(1)$,
as follows: given input $(w_{1},\dots,w_{k})$, let $S\subseteq[k]$ be the set
of indices $i$ such that $w_{i}<0$ and $T\subseteq[k]$ be the set of indices
$i$ such that $w_{i}>0$. We define $\mathbf{p}(w_{1},\dots,w_{k})$ to be the
$\mathbf{q}\in\mathcal{D}$ such that

$(\mathbf{q},1)\oplus\left(\bigoplus_{i\in
S}(\mathbf{p}_{i},-w_{i})\right)=\bigoplus_{i\in T}(\mathbf{p}_{i},w_{i}).$

Note that $\mathbf{q}$ is not guaranteed to exist, which is why we call
$\mathbf{p}$ a partial function. However, if $\mathbf{q}$ exists then it is
unique, by the subtraction axiom.

We can now state the full axiomatization, including the monotonicity axiom.

######  Definition B.2.6 (Axioms for pooling operators).

For a pooling operator $\oplus$ on $\mathcal{D}$, we define the following
axioms.

  1. 1.

Weight additivity:
$\text{wt}(\Pi_{1}\oplus\Pi_{2})=\text{wt}(\Pi_{1})+\text{wt}(\Pi_{2})$ for
every $\Pi_{1},\Pi_{2}$.

  2. 2.

Commutativity: $\Pi_{1}\oplus\Pi_{2}=\Pi_{2}\oplus\Pi_{1}$ for every
$\Pi_{1},\Pi_{2}$.

  3. 3.

Associativity:
$\Pi_{1}\oplus(\Pi_{2}\oplus\Pi_{3})=(\Pi_{1}\oplus\Pi_{2})\oplus\Pi_{3}$ for
every $\Pi_{1},\Pi_{2},\Pi_{3}$.

  4. 4.

Continuity: For every positive integer $k$ and
$\mathbf{p}_{1},\dots,\mathbf{p}_{k}$, the quantity333The continuity axiom is
only well-defined conditioned on $\oplus$ being associative, which is fine for
our purposes. We allow a proper subset of weights to be zero by defining the
aggregate to ignore forecasts with weight zero.

$\text{pr}\left(\bigoplus_{i=1}^{k}(\mathbf{p}_{i},w_{i})\right)$

is a continuous function of $(w_{1},\dots,w_{k})$ on $\mathbb{R}_{\geq
0}^{k}\setminus\\{\mathbf{0}\\}$.

  5. 5.

Idempotence: For every $\Pi_{1}$ and $\Pi_{2}$, if
$\text{pr}(\Pi_{1})=\text{pr}(\Pi_{2})$ then
$\text{pr}(\Pi_{1}\oplus\Pi_{2})=\text{pr}(\Pi_{1})$.

  6. 6.

Subtraction: If $\Pi_{1}\oplus\Pi_{2}=\Pi_{1}\oplus\Pi_{3}$ then
$\Pi_{2}=\Pi_{3}$.

  7. 7.

Monotonicity: There exist vectors
$\mathbf{p}_{1},\dots,\mathbf{p}_{n}\in\mathcal{D}$ such that $\mathbf{p}$ (as
in Definition B.2.5) is a strictly cyclically monotone function from its
domain to $\mathbb{R}^{n}$.

This monotonicity axiom essentially extends our previous monotonicity axiom
(in Definition 5.6.5) to a multi-dimensional setting. It states that there are
$n$ “anchor points” in $\mathcal{D}$ such that the function $\mathbf{p}$ from
weight vectors to $\mathcal{D}$ that pools the anchor points with the weights
given as input obeys a notion of monotonicity (namely cyclical monotonicity).
Informally, this means that the vector of weights that one would need to give
to the anchor points in order to arrive at a forecast $\mathbf{p}$
“correlates” with the forecast $\mathbf{p}$ itself.

We now state the main theorem of our axiomatization.

######  Theorem B.2.7.

A pooling operator satisfies the axioms in Definition B.2.6 if and only if it
is a QA pooling operator as in Definition B.2.2.444Recall that Definition
B.2.2 is narrower than Definition 5.2.5, since it excludes QA pools with
respect to scoring rules that do not have convex exposure. Without convex
exposure, the associativity, subtraction, and monotonicity axioms may be
violated. For example, consider $\Pi_{i}=(\boldsymbol{\delta}_{i},1)$ for
$i=1,2,3$, for the scoring rule with expected score function
$G(\mathbf{x})=x_{1}^{4}+x_{2}^{4}+x_{3}^{4}$. We have that
$(\Pi_{1}\oplus_{\mathbf{g}}\Pi_{2})\oplus_{\mathbf{g}}\Pi_{3}=((1/2,1/2,0),2)\oplus_{\mathbf{g}}(\boldsymbol{\delta}_{3},1)\approx((0.182,0.182,0.635),3)$,
whereas
$\Pi_{1}\oplus_{\mathbf{g}}(\Pi_{2}\oplus_{\mathbf{g}}\Pi_{3})=((0.635,0.182,0.182),3)$.

###### Proof.

We begin by noting the following fact, which follows from results in [322,
§26].

######  Proposition B.2.8.

A strictly cyclically monotone function
$\mathbf{g}:\mathcal{D}\to\mathbb{R}^{n}$ is injective, and its inverse
$\mathbf{g}^{-1}$ is strictly cyclically monotone and continuous.555Why can’t
we apply this result again to $\mathbf{g}^{-1}$ to conclude that $\mathbf{g}$
is continuous, even though we did not assume it to be? The reason is that the
proof of continuity relies on the convexity of $\mathcal{D}$; if $\mathbf{g}$
is discontinuous then the domain of $\mathbf{g}^{-1}$ may not be convex (or
even connected), so we cannot apply the result to $\mathbf{g}^{-1}$.

We provide a partial proof below; it relies on the following observation.

######  Remark B.2.9.

We can instead write the condition as

$\sum_{i=1}^{k}\left\langle\mathbf{g}(\mathbf{x}_{i})-\mathbf{g}(\mathbf{x}_{i-1}),\mathbf{x}_{i}\right\rangle\geq
0.$

This is equivalent to the condition in Definition B.2.3, because it is the
same statement (with rearranged terms) when the $\mathbf{x}_{i}$’s are listed
in reverse order.

###### Proof.

First, suppose that $\mathbf{g}(\mathbf{x})=\mathbf{g}(\mathbf{y})$. Then

$\mathbf{g}(\mathbf{x})(\mathbf{x}-\mathbf{y})+\mathbf{g}(\mathbf{y})(\mathbf{y}-\mathbf{x})=0.$

Since $\mathbf{g}$ is _strictly_ cyclically monotone, this implies that
$\mathbf{x}=\mathbf{y}$. (Note that we only use two-cycle monotonicity.)

We now show that $\mathbf{g}^{-1}$ is strictly cyclically monotone. That is,
we wish to show that

$\sum_{i=1}^{k}\left\langle\mathbf{x}_{i},\mathbf{g}^{-1}(\mathbf{x}_{i})-\mathbf{g}^{-1}(\mathbf{x}_{i-1})\right\rangle>0$

for any $\mathbf{x}_{1},\dots,\mathbf{x}_{k}=\mathbf{x}_{0}$ that are not all
the same. (See Remark B.2.9.) By the cyclical monotonicity of $\mathbf{g}$, we
have that

$\sum_{i=1}^{k}\left\langle\mathbf{g}(\mathbf{p}_{i}),\mathbf{p}_{i}-\mathbf{p}_{i-1}\right\rangle>0$

(the strictness of the inequality follows by the injectivity of $\mathbf{g}$:
if $\mathbf{x}_{i}\neq\mathbf{x}_{j}$ then
$\mathbf{p}_{i}\neq\mathbf{p}_{j}$). This means that

$\sum_{i=1}^{k}\left\langle\mathbf{x}_{i},\mathbf{g}^{-1}(\mathbf{x}_{i})-\mathbf{g}^{-1}(\mathbf{x}_{i-1})\right\rangle>0,$

as desired. As for continuity, we defer to [322, Theorem 26.5]. ∎

Back to the proof of Theorem B.2.7, we first prove that any such
$\oplus_{\mathbf{g}}$ satisfies the stated axioms. Weight additivity,
commutativity, associativity, and idempotence are clear. Continuity follows
from the formula

$\text{pr}((\mathbf{p}_{1},w_{1})\oplus_{\mathbf{g}}(\mathbf{p}_{2},w_{2}))=\mathbf{g}^{-1}\left(\frac{w_{1}\mathbf{g}(\mathbf{p}_{1})+w_{2}\mathbf{g}(\mathbf{p}_{2})}{w_{1}+w_{2}}\right),$

noting that $\mathbf{g}^{-1}$ is continuous by Proposition B.2.8. Likewise,
subtraction follows from the fact that $\mathbf{g}$ is injective (by
Proposition B.2.8), as is $\mathbf{g}^{-1}$ (likewise). Monotonicity remains.

The range of $\mathbf{g}$ contains an open subset666This follows from the
invariance of domain theorem, which states that the image of an open subset of
a manifold under an injective continuous map is open. of $H_{n}(0)$, so in
particular it contains the vertices of some translated and dilated copy of the
standard simplex. That is, there are $n$ points
$\mathbf{x}_{1},\dots,\mathbf{x}_{n}$ in the range of $\mathbf{g}$ for which
there is a positive scalar $a$ and vector $\mathbf{b}$ such that
$a\boldsymbol{\delta}_{i}+\mathbf{b}=\mathbf{x}_{i}$ for every $i$. (Here
$\boldsymbol{\delta}_{i}$ is the $i$-th standard basis vector in
$\mathbb{R}^{n}$.) We will let $\mathbf{p}_{i}$ be the pre-image of
$\mathbf{x}_{i}$ under $\mathbf{g}$, so that
$\mathbf{g}(\mathbf{p}_{i})=a\boldsymbol{\delta}_{i}+\mathbf{b}$.

Observe that for any $\mathbf{w}$ in the domain of $\mathbf{p}$, we have

$\mathbf{g}(\mathbf{p}(\mathbf{w}))=\sum_{i=1}^{n}w_{i}\mathbf{g}(\mathbf{p}_{i})=\sum_{i=1}^{n}w_{i}(a\boldsymbol{\delta}_{i}+\mathbf{b})=a\mathbf{w}+\mathbf{b},$

so

$\mathbf{p}(\mathbf{w})=\mathbf{g}^{-1}(a\mathbf{w}+\mathbf{b}).$

We have that $\mathbf{g}^{-1}$ is strictly cyclically monotone (by Proposition
B.2.8), and it is easy to verify that for any strictly cyclically monotone
function $\mathbf{f}$ and any $a>0$ and $\mathbf{b}$,
$\mathbf{f}(a\mathbf{x}+\mathbf{b})$ is a strictly cyclically monotone
function of $\mathbf{x}$. Therefore,
$\mathbf{p}(\mathbf{w})=\mathbf{g}^{-1}(a\mathbf{w}+\mathbf{b})$ is strictly
cyclically monotone, as desired.

Now we prove the converse. Assume that we have a pooling operator $\oplus$
satisfying the axioms in Definition B.2.6. We wish to show that $\oplus$ is
$\oplus_{\mathbf{g}}$ for some $\mathbf{g}:\mathcal{D}\to H_{n}(0)$.

For the remainder of this proof, let $\mathbf{p}_{1},\dots,\mathbf{p}_{n}$ be
vectors certifying the monotonicity of $\oplus$, and let $\mathbf{p}(\cdot)$
be as in Definition B.2.5.

For any $\mathbf{q}\in\mathcal{D}$, let
$\mathbf{g}(\mathbf{q}):=\mathbf{w}-\frac{1}{n}\mathbf{1}_{n}$, where
$\mathbf{w}\in H_{n}(1)$ is such that $\mathbf{p}(\mathbf{w})=\mathbf{q}$ and
$\mathbf{1}_{n}$ is the all-ones vector. This raises the question of well-
definedness: does this $\mathbf{w}$ necessarily exist, and if so, is it
unique? The following claim shows that this is indeed the case.

######  Claim B.2.10.

The function $\mathbf{p}$, from the subset of $H_{n}(1)$ where it is defined
to $\mathcal{D}$, is bijective.

###### Proof.

The fact that $\mathbf{p}$ is injective follows from the fact that it is
strictly cyclically monotone (see Proposition B.2.8). We now show that
$\mathbf{p}$ is surjective.

Let $\mathbf{q}\in\mathcal{D}$. Define the function
$\tilde{\mathbf{p}}:\Delta_{n+1}\to\mathcal{D}$ by

$\tilde{\mathbf{p}}(w_{1},\dots,w_{n+1}):=\text{pr}\left(\left(\bigoplus_{i=1}^{n}(\mathbf{p}_{i},w_{i})\right)\oplus(\mathbf{q},w_{n+1})\right).$

Since $\tilde{\mathbf{p}}$ is a continuous map777By the continuity axiom; here
we use the more generalized form we stated earlier. from $\Delta_{n+1}$ (an
$n$-dimensional manifold) to $\mathcal{D}$ (an $(n-1)$-dimensional manifold),
$\tilde{\mathbf{p}}$ is not injective.888This follows e.g. from the Borsuk-
Ulam theorem. So in particular, let
$\mathbf{w}_{1}\neq\mathbf{w}_{2}\in\Delta_{n+1}$ be such that
$\mathbf{\tilde{p}}(\mathbf{w}_{1})=\mathbf{\tilde{p}}(\mathbf{w}_{2})$. That
is, we have

$\left(\bigoplus_{i=1}^{n}(\mathbf{p}_{i},w_{1,i})\right)\oplus(\mathbf{q},w_{1,n+1})=\left(\bigoplus_{i=1}^{n}(\mathbf{p}_{i},w_{2,i})\right)\oplus(\mathbf{q},w_{2,n+1}).$
(B.2)

Observe that $w_{1,n+1}\neq w_{2,n+2}$; for otherwise it would follows from
the subtraction axiom that two different combinations of the
$\mathbf{p}_{i}$’s would give the same probability, contradicting the fact
that $\mathbf{p}$ is injective. Without loss of generality, assume that
$w_{1,n+1}>w_{2,n+1}$. We can rearrange the terms in Equation B.2 to look as
follows.

$(\mathbf{q},w_{1,n+1}-w_{2,n+1})\oplus\left(\bigoplus_{i\in
S}(\mathbf{p}_{i},v_{i})\right)=\bigoplus_{i\in T\subseteq[n]\setminus
S}(\mathbf{p}_{i},v_{i})$

for some positive $v_{1},\dots,v_{n}$. By the distributive property, we may
multiply all weights by $\frac{1}{w_{1,n+1}-w_{2,n+1}}$. The result will be an
equation as in Definition B.2.5, certifying that $\mathbf{q}$ is in the range
of the function $\mathbf{p}$, as desired. ∎

We return to our main proof, now that we have shown that our function
$\mathbf{g}(\mathbf{q}):=\mathbf{w}-\frac{1}{n}\mathbf{1}$, where
$\mathbf{w}\in H_{n}(1)$ is such that $\mathbf{p}(\mathbf{w})=\mathbf{q}$, is
well-defined. In fact, we can simply write
$\mathbf{g}(\mathbf{q})=\mathbf{p}^{-1}(\mathbf{q})-\frac{1}{n}\mathbf{1}$.
(The vector $\frac{1}{n}\mathbf{1}$ is fairly arbitrary; it only serves the
purpose of forcing the range of $\mathbf{g}$ to lie in $H_{n}(0)$ instead of
$H_{n}(1)$.)

We first show that the equation that defines $\oplus_{\mathbf{g}}$ holds –
that is, that if
$(\mathbf{q}_{1},v_{1})\oplus(\mathbf{q}_{2},v_{2})=(\mathbf{q},v_{1}+v_{2})$
(with $v_{1},v_{2}\geq 0$, not both zero), then

$\mathbf{g}(\mathbf{q})=\frac{v_{1}\mathbf{g}(\mathbf{q}_{1})+v_{2}\mathbf{g}(\mathbf{q}_{2})}{v_{1}+v_{2}}.$

Let $\mathbf{w}_{1},\mathbf{w}_{2}\in H_{n}(1)$ be such that
$\mathbf{q}_{1}=\mathbf{p}(\mathbf{w}_{1})$ and
$\mathbf{q}_{2}=\mathbf{p}(\mathbf{w}_{2})$. It is intuitive that
$\mathbf{q}=\mathbf{p}\left(\frac{v_{1}\mathbf{w_{1}}+v_{2}\mathbf{w_{2}}}{v_{1}+v_{2}}\right)$,
but we show this formally.

######  Claim B.2.11.

Given $\mathbf{q}_{1},\mathbf{q}_{2}\in\mathcal{D}$ with
$\mathbf{q}_{1}=\mathbf{p}(\mathbf{w}_{1}),\mathbf{q}_{2}=\mathbf{p}(\mathbf{w}_{2})$,
and $0\leq\alpha\leq 1$, we have

$\mathbf{p}(\alpha\mathbf{w}_{1}+(1-\alpha)\mathbf{w}_{2})=(\mathbf{q}_{1},\alpha)\oplus(\mathbf{q}_{2},1-\alpha).$

###### Proof.

Note that

$\displaystyle(\mathbf{q}_{1},1)\oplus\left(\bigoplus_{i:w_{1,i}<0}(\mathbf{p}_{i},w_{1,i})\right)$
$\displaystyle=\bigoplus_{i:w_{1,i}>0}(\mathbf{p}_{i},w_{1,i})$
$\displaystyle(\mathbf{q}_{2},1)\oplus\left(\bigoplus_{i:w_{2,i}<0}(\mathbf{p}_{i},w_{2,i})\right)$
$\displaystyle=\bigoplus_{i:w_{2,i}>0}(\mathbf{p}_{i},w_{2,i}).$

Applying the distributive property to the two above equations with constants
$\alpha$ and $1-\alpha$, respectively, and adding them, we get that

$\displaystyle\left(\mathbf{q}_{1},\alpha\right)\oplus\left(\mathbf{q}_{2},1-\alpha\right)\oplus\left(\bigoplus_{i:w_{1,i}<0}(\mathbf{p}_{i},\alpha
w_{1,i})\right)\oplus\left(\bigoplus_{i:w_{2,i}<0}(\mathbf{p}_{i},(1-\alpha)w_{2,i})\right)$
$\displaystyle=\left(\bigoplus_{i:w_{1,i}>0}(\mathbf{p}_{i},\alpha
w_{1,i})\right)\oplus\left(\bigoplus_{i:w_{2,i}>0}(\mathbf{p}_{i},(1-\alpha)w_{2,i})\right).$

We have that
$\left(\mathbf{q}_{1},\alpha\right)\oplus\left(\mathbf{q}_{2},1-\alpha\right)=(\mathbf{q},1)$.
It follows (after rearranging terms, from Definition B.2.5) that
$\mathbf{q}=\mathbf{p}\left(\frac{v_{1}\mathbf{w_{1}}+v_{2}\mathbf{w_{2}}}{v_{1}+v_{2}}\right)$.
∎

Applying Claim B.2.11 with $\alpha=\frac{v_{1}}{v_{1}+v_{2}}$, we find that

$\mathbf{g}(\mathbf{q})=\frac{v_{1}\mathbf{w_{1}}+v_{2}\mathbf{w_{2}}}{v_{1}+v_{2}}-\frac{1}{n}\mathbf{1}=\frac{v_{1}\left(\mathbf{g}(\mathbf{q}_{1})+\frac{1}{n}\mathbf{1}\right)+v_{2}\left(\mathbf{g}(\mathbf{q}_{2})+\frac{1}{n}\mathbf{1}\right)}{v_{1}+v_{2}}-\frac{1}{n}\mathbf{1}=\frac{v_{1}\mathbf{g}(\mathbf{q}_{1})+v_{2}\mathbf{g}(\mathbf{q}_{2})}{v_{1}+v_{2}},$

as desired.

It remains to show that $\mathbf{g}$ is continuous, strictly cyclically
monotone, and has convex range. By the monotonicity axiom, $\mathbf{p}$ is
strictly cyclically monotone. It follows by Proposition B.2.8 that its inverse
its continuous and strictly cyclically monotone. Therefore, $\mathbf{g}$ is
continuous and cyclically monotone (as it is simply a translation of
$\mathbf{p}^{-1}(\mathbf{q})$ by $\frac{1}{n}\mathbf{1}$).

Finally, to show that $\mathbf{g}$ has convex range, we wish to show that
$\mathbf{p}^{-1}$ has convex range; or, in other words, that the domain on
which $\mathbf{p}$ is defined is convex. And indeed, this follows
straightforwardly from Claim B.2.11. Let $\mathbf{w}_{1},\mathbf{w}_{2}$ be in
the domain of $\mathbf{p}$, with
$\mathbf{p}(\mathbf{w}_{1})=\mathbf{q}_{1},\mathbf{p}(\mathbf{w}_{2})=\mathbf{q}_{2}$.
Then for any $0\leq\alpha\leq 1$, we have that

$\mathbf{p}(\alpha\mathbf{w}_{1}+(1-\alpha)\mathbf{w}_{2})=(\mathbf{q}_{1},\alpha)\oplus(\mathbf{q}_{2},1-\alpha),$

so in particular $\alpha\mathbf{w}_{1}+(1-\alpha)\mathbf{w}_{2}$ is in the
domain of $\mathbf{p}$. This concludes the proof. ∎

###  B.3 The convex exposure property

Several of our results have been contingent on the convex exposure property.
In this e-companion, we consider when the convex exposure property holds. Our
first result is that it always holds in the case of a binary outcome (i.e.
$n=2$).

######  Proposition B.3.1.

If $n=2$, every (continuous) proper scoring rule has convex exposure.

###### Proof.

Consider a proper scoring rule $s$ with forecast domain $\mathcal{D}$. Since
$\mathcal{D}$ is connected and $\mathbf{g}$ is continuous on $\mathcal{D}$,
the range of $\mathbf{g}$ over $\mathcal{D}$ is connected. In the $n=2$
outcome case, the range of $\mathbf{g}$ lies on the line
$\\{(x_{1},x_{2}):x_{1}+x_{2}=0\\}$, and a connected subset of a line is
convex. ∎

As we shall see, the convex exposure property holds for nearly all of the most
commonly used scoring rules even in higher dimensions.

(A note on notation: in this section we use $p_{j}$ instead of $p(j)$ to refer
to the $j$-th coordinate of a probability distribution $\mathbf{p}$.)

We now show that scoring rules that – like the logarithmic scoring rule – “go
off to infinity” have convex exposure.

######  Proposition B.3.2.

Let $s$ be a proper scoring rule whose forecast domain is the interior of
$\Delta_{n}$, such that for any point $\mathbf{x}$ on the boundary of
$\Delta_{n}$, and for any sequence $\mathbf{x}_{1},\mathbf{x}_{2},\dots$
converging to $\mathbf{x}$,
$\lim_{k\to\infty}\left\lVert\mathbf{g}(\mathbf{x}_{k})\right\rVert_{2}=\infty$.999[181]
say that $G$ is a _pseudo-barrier function_ if this condition is satisfied.
Then $s$ has convex exposure.

This is a statement of convex analysis – namely that if
$\left\lVert\mathbf{g}\right\rVert_{2}$ approaches $\infty$ on the boundary of
a convex set, then the range of $\mathbf{g}$ is convex (assuming $\mathbf{g}$
is the gradient of a differentiable convex function). See [322, Theorem 26.5]
for the proof. In non-pathological cases, the basic intuition is that _every_
$\mathbf{v}\in\\{\mathbf{x}:\sum_{i}x_{i}=0\\}$ is the gradient of $G$ at some
point. In these cases, $\nabla G(\mathbf{x})=\mathbf{v}$ where $\mathbf{x}$
minimizes $G(\mathbf{v})-\left\langle\mathbf{v},\mathbf{x}\right\rangle$; the
$\lim_{k\to\infty}\left\lVert g(\mathbf{x}_{k})\right\rVert_{2}=\infty$
condition means that this minimum does not occur on the boundary of
$\Delta_{n}$.

######  Corollary B.3.3.

The following scoring rules have convex exposure:

  * •

The logarithmic scoring rule.

  * •

The scoring rule given by $G(\mathbf{p})=-\sum_{j}p_{j}^{\gamma}$ for
$\gamma\in(0,1)$.

  * •

The scoring rule given by $G(\mathbf{p})=-\sum_{j}\ln p_{j}$, which can be
thought of as the limit of the $G$ in the previous bullet point as $\gamma\to
0$.101010This is a natural way to think of this scoring rule because $\nabla
G(\mathbf{p})=-(p_{1}^{-1},\dots,p_{n}^{-1})$.

  * •

The scoring rule $hs$ given by $G_{hs}(\mathbf{p})=-\prod_{j}p_{j}^{1/n}$.

##### The $hs$ scoring rule

The last of these scoring rules is a generalization of the scoring rule
$hs(q)=1-\sqrt{\frac{1-q}{q}}$ used by [202] as part of proving their minimax
theorem for randomized algorithms.111111Here we are using the shorthand
notation for the $n=2$ outcome case discussed in Remark 3.5 of the main
article. The authors used this scoring rule as a key ingredient in their
minimax theorem for randomized algorithms. The key property of the scoring
rule was a result about its _amplification_ [202, Lemma 3.10]. The authors
define a _forecasting algorithm_ to be a generalization of a randomized
algorithm that outputs an estimated _probability_ that an output should be
accepted. Then, roughly speaking, the authors show that given a forecasting
algorithm $R$, it is possible to create a forecasting algorithm $R^{\prime}$
that has a much larger expected score from the scoring rule $hs$ by combining
running $R$ a small number of times and combining the outputs. This is an
important new result in theoretical computer science and suggests that $hs$
deserves more attention.

Since additive and multiplicative constants are irrelevant, we may treat
$hs(q)=-\frac{1}{2}\sqrt{\frac{1-q}{q}}$. Observe that (in the case of two
outcomes), the expected score $G_{hs}$ on a report of $q$ is

$G_{hs}(q)=q\left(-\frac{1}{2}\sqrt{\frac{1-q}{q}}\right)+(1-q)\left(-\frac{1}{2}\sqrt{\frac{1-q}{q}}\right)=-\sqrt{q(1-q)}.$

That is, $G_{hs}$ is precisely negative the geometric mean of $q$ and $1-q$.
This motivates us to generalize $hs$ to a setting with $n$ outcomes by setting

$G_{hs}(\mathbf{p}):=-\prod_{i=1}^{n}p_{i}^{1/n}.$

It should not be obvious that this function is convex, but it turns out to be;
this is the precise statement of an inequality known as Mahler’s inequality
[352].

Next we note that the quadratic scoring rule has convex exposure, since its
exposure function $\mathbf{g}(\mathbf{p})=2\mathbf{p}$ (modulo
$\mathbf{1}_{n}$ as discussed in Remark 3.12 of the main article) maps any
convex set to a convex set.

######  Proposition B.3.4.

The quadratic scoring rule has convex exposure.

_Spherical_ scoring rules – the third most studied proper scoring rules, after
the quadratic and logarithmic rules – also have convex exposure.

######  Definition B.3.5 (Spherical scoring rules).

[258, Example 2] For any $\alpha>1$, define the _spherical scoring rule with
parameter $\alpha$_ to be the scoring rule given by

$G_{\text{sph},\alpha}(\mathbf{p}):=\left(\sum_{i=1}^{n}p_{i}^{\alpha}\right)^{1/\alpha}.$

If the “spherical scoring rule” is referenced with no parameter $\alpha$
given, $\alpha$ is presumed to equal $2$.

######  Proposition B.3.6.

For any $\alpha>1$, the spherical scoring rule with parameter $\alpha$ has
convex exposure.

###### Proof.

Fix $\alpha>1$. We will write $G$ in place of $G_{\text{sph},\alpha}$. We
have121212As discussed in Remark 3.12 of the main article, the range of
$\mathbf{g}$ should be thought of as modulo $T(\mathbf{1}_{n})$. However, we
find it convenient for this proof to think of it as lying in $\mathbb{R}^{n}$
and project later.

$\mathbf{g}(\mathbf{p})=\left(\sum_{j=1}^{n}p_{j}^{\alpha}\right)^{(1/\alpha)-1}(p_{1}^{\alpha-1},\dots,p_{n}^{\alpha-1}).$
(B.3)

Now, define the _$n$ -dimensional unit $\beta$-sphere_, i.e.
$\\{\mathbf{x}:\sum_{j}x_{j}^{\beta}=1\\}$, and define the _$n$ -dimensional
unit $\beta$-ball_ correspondingly (i.e. with $\leq$ in place of $=$). The
range of $\mathbf{g}$ is precisely the part of the $n$-dimensional unit
$\frac{\alpha}{\alpha-1}$-sphere with all non-negative coordinates. Indeed, on
the one hand, for any $\mathbf{p}$ we have

$\sum_{j}g_{j}(\mathbf{p})^{\alpha/(\alpha-1)}=\left(\sum_{j}p_{j}^{\alpha}\right)^{-1}\cdot\sum_{j}p_{j}^{\alpha}=1$

(where $g_{j}(\mathbf{p})$ denotes the $j$-th coordinate of
$\mathbf{g}(\mathbf{p})$ as in Equation B.3). On the other hand, given a point
$\mathbf{x}$ on the unit $\frac{\alpha}{\alpha-1}$-sphere with all non-
negative coordinates,

$\mathbf{p}=\left(\sum_{j}x_{j}^{1/(\alpha-1)}\right)^{-1}\left(x_{1}^{1/(\alpha-1)},\dots,x_{n}^{1/(\alpha-1)}\right)$

lies in $\Delta_{n}$ and satisfies $\mathbf{g}(\mathbf{p})=\mathbf{x}$.

The crucial point for us is that for $\beta>1$, the unit $\beta$-ball is
convex. This means that for any such $\beta$, the convex combination of any
number of points on the unit $\beta$-sphere will lie in the unit $\beta$-ball.
Since $\frac{\alpha}{\alpha-1}>1$ for $\alpha>1$, we have that for arbitrary
$\mathbf{p},\mathbf{q}\in\Delta_{n}$ and $w\in[0,1]$,
$w\mathbf{g}(\mathbf{p})+(1-w)\mathbf{g}(\mathbf{q})$ lies in the unit
$\beta$-ball – in fact, in the part with all non-negative coordinates. Now,
consider casting a ray from this convex combination point in the positive
$\mathbf{1}_{n}$ direction. All points on this ray are equivalent to this
point modulo $T(\mathbf{1}_{n})$, and this ray will intersect the unit
$\beta$-sphere at some point $\mathbf{x}$ with all non-negative coordinates.
The point $\mathbf{p}\in\Delta_{n}$ with $\mathbf{g}(\mathbf{p})=\mathbf{x}$
satisfies

$\mathbf{g}(\mathbf{p})=\mathbf{g}(\mathbf{p})+(1-w)\mathbf{g}(\mathbf{q}).$

This completes the proof. ∎

######  Remark B.3.7.

The above proof gives a geometric interpretation of the QA pooling with
respect to the spherical scoring rule, particularly for $\alpha=2$. In the
$\alpha=2$ case, pooling amounts to taking the following steps:

  1. (1)

Scale each forecast so it lies on the unit sphere.

  2. (2)

Take the weighted average of the resulting points in $\mathbb{R}^{n}$.

  3. (3)

Shift the resulting point in the positive $\mathbf{1}_{n}$ direction to the
unique point in that direction that lies on the unit sphere.

  4. (4)

Scale this point so that its coordinates add to $1$.

Finally we consider the parametrized family known as _Tsallis scoring rules_
[346].

######  Definition B.3.8 (Tsallis scoring rules).

For $\gamma>1$, the _Tsallis scoring rule with parameter $\gamma$_ is the rule
given by

$G_{\text{Tsa},\gamma}(\mathbf{p})=\sum_{j=1}^{m}p_{j}^{\gamma}.$

Setting $\gamma=2$ above yields the quadratic scoring rule. Note also that we
have already addressed the scoring rule given by
$G(\mathbf{p})=\pm\sum_{j}p_{j}^{\gamma}$ for $\gamma\leq 1$ (except
$\gamma=0,1$, which are degenerate), with the sign chosen to make $G$ convex:
these scoring rules have convex exposure by Proposition B.3.2. The following
proposition completes our analysis for this natural class of scoring rules.

######  Proposition B.3.9.

For $\gamma\leq 2$, the Tsallis scoring rule with parameter $\gamma$ has
convex exposure. For $\gamma>2$, this is not the case if $n>2$.

###### Proof.

Fix $\gamma>1$. We will write $G$ in place of $G_{\text{Tsa},\gamma}$. Up to a
multiplicative factor of $\gamma$ that we are free to ignore, we have

$\mathbf{g}(\mathbf{p})=(p_{1}^{\gamma-1},\dots,p_{n}^{\gamma-1}).$

Let $\mathbf{p},\mathbf{q}\in\Delta_{n}$ and $w\in[0,1]$. We wish to find an
$\mathbf{x}\in\Delta_{n}$ such that
$\mathbf{g}(\mathbf{x})=w\mathbf{g}(\mathbf{p})+(1-w)\mathbf{g}(\mathbf{q})$,
i.e.

$wp_{j}^{\gamma-1}+(1-w)q_{j}^{\gamma-1}+c=x_{j}^{\gamma-1},$

for all $j\in[n]$, for some $c$. Since $\sum_{j}x_{j}=1$, this $c$ must
satisfy

$\sum_{j}(wp_{j}^{\gamma-1}+(1-w)q_{j}^{\gamma-1}+c)^{1/(\gamma-1)}=1.$ (B.4)

Let
$h(x):=\sum_{j}(wp_{j}^{\gamma-1}+(1-w)q_{j}^{\gamma-1}+x)^{1/(\gamma-1)}$.
Note that $h$ is increasing in $x$.

First consider the case that $\gamma\leq 2$. By concavity, we have that
$wp_{j}^{\gamma-1}+(1-w)q_{j}^{\gamma-1}\leq(wp_{j}+(1-w)q_{j})^{\gamma-1}$.
This means that

$h(0)=\sum_{j}(wp_{j}^{\gamma-1}+(1-w)q_{j}^{\gamma-1})^{1/(\gamma-1)}\leq\sum_{j}(wp_{j}+(1-w)q_{j})=1.$

On the other hand, $\lim_{x\to\infty}h(x)=\infty$. Since $h$ is continuous,
there must be some $x\in[0,\infty)$ such that $h(x)=1$; call this value $c$.
Then let

$x_{j}=(wp_{j}^{\gamma-1}+(1-w)q_{j}^{\gamma-1}+c)^{1/(\gamma-1)}.$

Then every $x_{j}$ is nonnegative and $\sum_{j}x_{j}=1$, so we have succeeded.

Now consider the case that $\gamma>2$, and consider as a counterexample
$\mathbf{p}=(1,0,\dots,0)$, $\mathbf{q}=(0,1,0,\dots,0)$, and $w=\frac{1}{2}$.
To satisfy Equation B.4, we are looking for $c$ such that

$h(c)=2\left(\frac{1}{2}+c\right)^{1/(\gamma-1)}+(n-2)c^{1/(\gamma-1)}=1.$

Note that $h(0)=2\cdot 2^{-1/(\gamma-1)}=2^{(\gamma-2)/(\gamma-1)}>1$, so
$c<0$ (as $h$ is increasing). But in that case $x_{j}^{\gamma-1}<0$ for any
$j\geq 3$, a contradiction (assuming $n>2$). ∎

Note that because $\nabla
G_{\text{Tsa},\gamma}(\mathbf{p})=(p_{1}^{\gamma-1},\dots,p_{n}^{\gamma-1})$
(up to a constant factor), QA pooling with respect to the Tsallis scoring rule
can be thought of as an appropriately scaled coordinate-wise
$(\gamma-1)$-power mean. For $\gamma=2$ it is the coordinate-wise arithmetic
average. For $\gamma=3$ it is the coordinate-wise root mean square, but with
the average of the squares scaled by an appropriate additive constant so that,
upon taking the square roots, the probabilities add to $1$. (However, as the
Tsallis score with parameter $3$ does not have convex exposure, this is not
always well-defined.)

In Corollary B.3.3 we mentioned that the scoring rule given by
$G(\mathbf{p})=-\sum_{j}\ln p_{j}$ can be thought of as an extension to
$\gamma=0$ of (what we are now calling) the Tsallis score, because the
derivative of $\ln x$ is $x^{-1}$. QA pooling with respect to this scoring
rule is, correspondingly, the $-1$-power mean, i.e. the harmonic mean. This
pooling method is appropriately referred to as _harmonic pooling_ , see e.g.
[234, §4.2].

Finally, we note that the logarithmic scoring rule can likewise be thought of
as an extension of the Tsallis score to $\gamma=1$, in that the second
derivative of $x\ln x$ is $x^{-1}$. It is likewise natural to call the
geometric mean the $0$-power mean; notice that logarithmic pooling is
precisely an appropriately scaled coordinate-wise geometric mean.

##  Appendix C Details omitted from Chapter 6

###  C.1 Efficiency of Algorithm 3

The only nontrivial step of the algorithm is finding the weight vector
satisfying the equation on the last line of the algorithm. To do so, it is
first necessary to compute the gradient of the loss. This gradient, given by
Equation C.2 below, can clearly be computed in time $O(mn)$. After that, it is
necessary to find the weight vector $\mathbf{w}^{t+1}$ that satisfies the
equation on the last line. This can be done efficiently through local search:
the goal amounts to find weights $(w_{1},\dots,w_{m})$ such that the vector
$(w_{1}^{\alpha-1},\dots,w_{m}^{\alpha-1})$ is equal to a target vector (call
it $\mathbf{v}$) plus a constant $c$ times the all-ones vector. That is, we
need to simultaneously solve the equation $w_{i}^{\alpha-1}=v_{i}+c$ for all
$i$, with weights that add to $1$. (Here, the $v_{i}$ are knowns and the
$w_{i}$ and $c$ are unknowns.)

We start by finding $c$, by solving the equation
$\sum_{i}(v_{i}+c)^{1/(\alpha-1)}=1$. Such a $c$ exists because the left-hand
side of this equation is continuous and monotone decreasing, going from
infinity to zero as $c$ ranges from $-\min_{i}v_{i}$ to infinity. We can solve
for $c$ very efficiently, e.g. with Newton’s method. Once we know $c$, we know
each $w_{i}$: we have $w_{i}=(v_{i}+c)^{1/(\alpha-1)}$. Thus, Algorithm 1
takes $O(mn)$ time.

###  C.2 Details omitted from Section 6.4

See 6.4.4

###### Proof.

Fix any $t$. Note that since the space of possible weights is $\Delta_{m}$, it
is most natural to think of $\nabla R$ as a function from $\Delta_{m}$ to
$\mathbb{R}^{m}/T(\mathbf{1}_{m})$, i.e. $\mathbb{R}^{m}$ modulo translation
by the all-ones vector (which is orthogonal to $\Delta_{m}$ in
$\mathbb{R}^{m}$). That is, $\nabla
R(\mathbf{w})=-((w_{1})^{\alpha-1},\dots,(w_{m})^{\alpha-1})$, where this
vector may be thought of as modulo translation by the all-ones vector.
Nevertheless, we find it convenient to define
$\partial_{i}R(\mathbf{w}):=-(w_{i})^{\alpha-1}$. We define
$\partial_{i}L^{t}(\mathbf{w})$ similarly (see Section 6.4.4).

Define $\mathbf{h}\in\mathbb{R}^{m}$ to have coordinates
$h_{i}:=\partial_{i}R(\mathbf{w}^{t})-\eta_{t}\partial_{i}L^{t}(\mathbf{w}^{t})$.
Per the update rule, we have that $h_{i}\equiv R(\mathbf{w}^{t+1})\mod
T(\mathbf{1}_{m})$. We have

$-(w_{i}^{t})^{\alpha-1}-\eta_{t}\zeta=\partial_{i}R(\mathbf{w}^{t})-\eta_{t}\zeta\leq
h_{i}\leq\partial_{i}R(\mathbf{w}^{t})+\frac{\eta_{t}\zeta}{w_{i}^{t}}=-(w_{i}^{t})^{\alpha-1}+\frac{\eta_{t}\zeta}{w_{i}^{t}}$
(C.1)

Applying the first and last claims of Lemma C.2.1 (below) with $a=\alpha-1$,
$\mathbf{v}=\mathbf{w}^{t}$, $\kappa=\eta_{t}\zeta$, and
$\mathbf{g}=-\mathbf{h}$, we have that there exists a unique $c\in\mathbb{R}$
such that

$\sum_{i=1}^{m}(-h_{i}+c)^{1/(\alpha-1)}=1,$

and in fact that $-\eta_{t}\zeta\leq c\leq m\eta_{t}\zeta$. (Equation C.1 is
relevant here because it is equivalent to the
$v_{i}^{a}-\frac{\kappa}{w_{i}^{t}}\leq g_{i}\leq v_{i}^{a}+\kappa$ conditions
in Lemma C.2.1. This is also where we use that
$\eta_{t}\zeta\leq(1-\alpha)^{2}(w_{i}^{t})^{\alpha}$, which is equivalent to
$\kappa\leq a^{2}v_{i}^{a+1}$.) The significance of this fact is that
$(-h_{i}+c)^{1/(\alpha-1)}$ is precisely $w_{i}^{t+1}$, since (in
$\mathbb{R}^{m}$) we have that
$\left(\partial_{i}R(\mathbf{w}^{t+1}),\dots,\partial_{i}R(\mathbf{w}^{t+1})\right)=\mathbf{h}-c\cdot\mathbf{1}$
for _some_ $c$, and in particular this $c$ must be such that
$\sum_{i}w_{i}^{t+1}=1$. In particular, this means that for all $i$, we have

$(w_{i}^{t+1})^{\alpha-1}=-h_{i}+c\leq(w_{i}^{t})^{\alpha-1}+\eta_{t}\zeta+\frac{1}{\min_{k}w_{k}}\eta_{t}\zeta=(w_{i}^{t})^{\alpha-1}+\left(\frac{1}{\min_{k}w_{k}}+1\right)\eta_{t}\zeta.$

Here, the inequality comes from the left inequality of Equation C.1 and the
fact that $c\leq\frac{1}{\min_{k}w_{k}}\eta_{t}\zeta$. If we also have that
$\eta_{t}\zeta\leq(1-\alpha)^{2}(w_{i}^{t})^{\alpha}$, then the last claim of
Lemma C.2.1 gives us that

$(w_{i}^{t+1})^{\alpha-1}=-h_{i}+c\leq(w_{i}^{t})^{\alpha-1}+\eta_{t}\zeta+m\eta_{t}\zeta=(w_{i}^{t})^{\alpha-1}+(m+1)\eta_{t}\zeta.$

Similarly, we have

$(w_{i}^{t+1})^{\alpha-1}=-h_{i}+c\geq(w_{i}^{t})^{\alpha-1}-\frac{\eta_{t}\zeta}{w_{i}^{t}}-\eta_{t}\zeta=(w_{i}^{t})^{\alpha-1}-\left(\frac{1}{w_{i}^{t}}+1\right)\eta_{t}\zeta.$

∎

######  Lemma C.2.1.

Let $-1<a<0$ and $\mathbf{g}\in\mathbb{R}^{m}$. There is a unique
$c\in\mathbb{R}$ such that $\sum_{i}(g_{i}+c)^{1/a}=1$. Furthermore, let
$\mathbf{v}\in\Delta_{m}$ and $\kappa\geq 0$. Then:

  * •

If $g_{i}\leq v_{i}^{a}+\kappa$ for all $i$, then $c\geq-\kappa$.

  * •

If $g_{i}\geq v_{i}^{a}-\frac{\kappa}{v_{i}}$ for all $i$, then
$c\leq\frac{\kappa}{\min_{i}v_{i}}$.

    * –

And if, furthermore, $\kappa\leq a^{2}v_{i}^{a+1}$ for all $i$, then $c\leq
m\kappa$.

###### Proof.

Observe that $\sum_{i}(g_{i}+c)^{1/a}$ is a continuous, monotone decreasing
function on $c\in(-\min_{i}g_{i},\infty)$; the range of the function on this
interval is $(0,\infty)$. Therefore, there is a unique
$c\in(-\min_{i}g_{i},\infty)$ such that the sum equals $1$.

We now prove the first bullet. Since $x^{1/a}$ decreases in $x$ and $g_{i}\leq
v_{i}^{a}+\kappa$, we have that

$1=\sum_{i}(g_{i}+c)^{1/a}\geq\sum_{i}(v_{i}^{a}+\kappa+c)^{1/a}.$

Suppose for contradiction that $c<-\kappa$. Then
$v_{i}^{a}+\kappa+c<v_{i}^{a}$ for all $i$, so

$\sum_{i}(v_{i}^{a}+\kappa+c)^{1/a}>\sum_{i}(v_{i}^{a})^{1/a}=\sum_{i}v_{i}=1.$

This is a contradiction, so in fact $c\geq-\kappa$.

The first claim of the second bullet is analogous. Since $x^{1/a}$ decreases
in $x$ and $g_{i}\geq v_{i}^{a}-{\kappa}{v_{i}}$, we have that

$1=\sum_{i}(g_{i}+c)^{1/a}\leq\sum_{i}\left(v_{i}^{a}-\frac{\kappa}{v_{i}}+c\right)^{1/a}.$
(C.2)

Suppose for contradiction that $c>\frac{\kappa}{v_{i}}$ for every $i$. Then
$v_{i}^{a}-\frac{\kappa}{v_{i}}+c>v_{i}^{a}$ for all $i$, so

$\sum_{i}\left(v_{i}^{a}-\frac{\kappa}{v_{i}}+c\right)^{1/a}<\sum_{i}(v_{i}^{a})^{1/a}=\sum_{i}v_{i}=1.$

This is a contradiction, so in fact $c\leq\frac{\kappa}{\min_{i}v_{i}}$.

We now prove the second claim of the second bullet. To do so, we note the
following technical lemma (proof below).

######  Lemma C.2.2.

For $-1<a<0$ and $\kappa,c\geq 0$, the function
$f(x)=\left(x^{a}-\frac{\kappa}{x}+c\right)^{1/a}$ is defined and concave at
any value of $x>0$ such that $a^{2}x^{a+1}\geq\kappa$.

Since for a general concave function $f$ it holds that
$\frac{1}{m}\sum_{i=1}^{m}f(x_{i})\leq
f\left(\frac{1}{m}\sum_{i=1}^{m}x_{i}\right)$, the following inequality
follows from Lemma C.2.2:

$\sum_{i}\left(v_{i}^{a}-\frac{\kappa}{v_{i}}+c\right)^{1/a}\leq
m\left(\left(\frac{1}{m}\right)^{a}-\kappa m+c\right)^{1/a}.$

(Here we are using the fact that $\sum_{i}v_{i}=1$.) Now, combining this fact
with Equation C.2, we have that

$\displaystyle m\left(\left(\frac{1}{m}\right)^{a}-\kappa m+c\right)^{1/a}$
$\displaystyle\geq 1$ $\displaystyle\left(\frac{1}{m}\right)^{a}-\kappa m+c$
$\displaystyle\leq\left(\frac{1}{m}\right)^{a}$

so $c\leq m\kappa$, as desired. ∎

###### Proof of Lemma C.2.2.

To show that $f$ is defined for any $x$ such that $a^{2}x^{a+1}\geq\kappa$, we
need to show that $x^{a}-\frac{\kappa}{x}+c>0$ for such values of $x$. This is
indeed the case:

$x^{a}-\frac{\kappa}{x}+c\geq x^{a}-a^{2}x^{a}+c=(1-a^{2})x^{a}+c>c\geq 0.$

Now we show concavity. We have

$f^{\prime\prime}(x)=\frac{1}{-a}\left(\left(1+\frac{1}{-a}\right)\left(x^{a}-\frac{\kappa}{x}+c\right)^{1/a-2}\left(ax^{a-1}+\frac{\kappa}{x^{2}}\right)^{2}-\left(x^{a}-\frac{\kappa}{x}+c\right)^{1/a-1}\left(a(a-1)x^{a-2}-\frac{2\kappa}{x^{3}}\right)\right)$

so we wish to show that

$\left(1+\frac{1}{-a}\right)\left(x^{a}-\frac{\kappa}{x}+c\right)^{1/a-2}\left(ax^{a-1}+\frac{\kappa}{x^{2}}\right)^{2}\leq\left(x^{a}-\frac{\kappa}{x}+c\right)^{1/a-1}\left(a(a-1)x^{a-2}-\frac{2\kappa}{x^{3}}\right)$

for every $x$ such that $a^{2}x^{a+1}\geq\kappa$. Fix any such $x$, and let
$d=\frac{\kappa}{x^{a+1}}$ (so $0\leq d\leq a^{2}$). We have

$\displaystyle d$ $\displaystyle\leq a^{2}$ $\displaystyle(1+a)(a^{2}-d)d$
$\displaystyle\geq 0$ $\displaystyle(1-a)(a+d)^{2}$
$\displaystyle\leq-a(1-d)(a(a-1)-2d)$ (rearrange terms)
$\displaystyle\left(1-\frac{1}{a}\right)(a+d)^{2}x^{a}$
$\displaystyle\leq((1-d)x^{a})(a(a-1)-2d)$ (multiply by $\frac{x^{a}}{-a}$)
$\displaystyle\left(1-\frac{1}{a}\right)(a+d)^{2}x^{a}$
$\displaystyle\leq((1-d)x^{a}+c)(a(a-1)-2d)$ ($c(a(a-1)-2d)\geq 0$)
$\displaystyle\left(1-\frac{1}{a}\right)((a+d)x^{a-1})^{2}$
$\displaystyle\leq((1-d)x^{a}+c)(a(a-1)-2d)x^{a-2}$ (multiply by $x^{a-2}$)
$\displaystyle\left(1-\frac{1}{a}\right)\left(ax^{a-1}+\frac{\kappa}{x^{2}}\right)^{2}$
$\displaystyle\leq\left(x^{a}-\frac{\kappa}{x}+c\right)\left(a(a-1)x^{a-2}-\frac{2\kappa}{x^{3}}\right).$
(substitute $d=\kappa x^{-a-1}$)

Note that the fifth line is justified by the fact that $c\geq 0$ and
$a(a-1)\geq 2d$ (because $a^{2}\geq d$ and $-a>a^{2}\geq d$). Now, multiplying
both sides by $\left(x^{a}-\frac{\kappa}{x}+c\right)^{1/a-2}$ completes the
proof. ∎

See 6.4.5

###### Proof.

Note that $\eta\gamma=\frac{1}{\sqrt{T}m^{(1+\alpha)/2}}$ and also that
$\eta_{t}\leq\eta$ for all $t$; we will be using these facts.

To prove (#1), we proceed by induction on $t$. In the case of $t=1$, all
weights are $1/m$, so the claim holds for sufficiently large $T$. Now assume
that the claim holds for a generic $t<T$; we show it for $t+1$.

By the small gradient assumption, we may use Lemma 6.4.4 with $\zeta=\gamma$.
By the inductive hypothesis (and the fact that $\eta_{t}\leq\eta$), we may
apply the second part of Lemma 6.4.4:

$\displaystyle(w_{i}^{t+1})^{\alpha-1}$
$\displaystyle\leq(w_{i}^{t})^{\alpha-1}+(m+1)\eta\gamma\leq\dots\leq(1/m)^{\alpha-1}+t(m+1)\eta\gamma.$
$\displaystyle\leq(1/m)^{\alpha-1}+\frac{(T-1)(m+1)}{m^{(1+\alpha)/2}\sqrt{T}}\leq
3m^{(1-\alpha)/2}\sqrt{T}.$

Since $\frac{-1}{2}<\alpha-1<0$, this means that
$w_{i}^{t}\geq\frac{1}{10\sqrt{m}}T^{1/(2(\alpha-1))}$.

We also have that

$(w_{i}^{t+1})^{\alpha}\geq\frac{1}{(10\sqrt{m})^{\alpha}}T^{\alpha/(2(\alpha-1))}\geq\frac{4}{m^{(1+\alpha)/2}}T^{-1/2}=4\eta\gamma$

for $T$ sufficiently large, since $\frac{\alpha}{2(\alpha-1)}>\frac{-1}{2}$.
This completes the inductive step, and thus the proof of (#1).

To prove (#2), we use the following technical lemma (see below for the proof).

######  Lemma C.2.3.

Fix $x>0$ and $-1<a<0$. Let $f(y)=(x^{a}+y)^{1/a}$. Then for all $y>-x^{a}$,
we have

$x-f(y)\leq\frac{-1}{a}x^{1-a}y$ (C.3)

and for all $-1<c\leq 0$, for all $cx^{a}\leq y\leq 0$, we have

$f(y)-x\leq\frac{1}{a}(1+c)^{1/a-1}x^{1-a}y.$ (C.4)

We apply Equation C.3 to $x=w_{i}^{t}$, $y=(m+1)\eta\gamma$, and $a=\alpha-1$.
This tells us that

$w_{i}^{t}-w_{i}^{t+1}\leq
w_{i}^{t}-((w_{i}^{t})^{\alpha-1}+(m+1)\eta\gamma)^{1/(\alpha-1)}\leq
2(w_{i}^{t})^{2-\alpha}(m+1)\eta\gamma.$

The first step follows by the second part of Lemma 6.4.4 and the fact that
$\eta_{t}\leq\eta$. The second step follows from Equation C.3 and uses the
fact that $\frac{1}{1-\alpha}>2$.

For the other side of (#2), we observe that since by (#1) we have
$(w_{i}^{t})^{\alpha}\geq 4\eta\gamma$, it follows that
$\frac{1}{2}(w_{i}^{t})^{\alpha}\geq(w_{i}^{t}+1)\eta\gamma$, and so
$\left(\frac{1}{w_{i}^{t}}+1\right)\eta\gamma\leq\frac{1}{2}(w_{i}^{t})^{\alpha-1}$.
Therefore, we can apply Equation C.4 to $x=w_{i}^{t}$,
$y=-\left(\frac{1}{w_{i}^{t}}+1\right)\eta\gamma$, $a=\alpha-1$, and
$c=-\frac{1}{2}$. This tells us that

$\displaystyle w_{i}^{t+1}-w_{i}^{t}$
$\displaystyle\leq\left((w_{i}^{t})^{\alpha-1}-\left(\frac{1}{w_{i}^{t}}+1\right)\eta\gamma\right)^{1/(\alpha-1)}-w_{i}^{t}\leq
16(w_{i}^{t})^{2-\alpha}\left(\frac{1}{w_{i}^{t}}+1\right)\eta\gamma$
$\displaystyle\leq 32(w_{i}^{t})^{1-\alpha}\eta\gamma.$

This completes the proof. ∎

###### Proof of Lemma C.2.3.

For all $y>-x^{a}$, we have

$f^{\prime}(y)=\frac{1}{a}(x^{a}+y)^{1/a-1}$

and

$f^{\prime\prime}(y)=\frac{1}{a}\left(\frac{1}{a}-1\right)(x^{a}+y)^{1/a-2}>0,$

so $f^{\prime}$ is increasing. Thus, for positive values of $y$ we have

$f^{\prime}(0)\leq\frac{f(y)-f(0)}{y}=\frac{f(y)-x}{y}\leq f^{\prime}(y)$

and for negative values of $y$ we have

$f^{\prime}(y)\leq\frac{f(y)-f(0)}{y}=\frac{f(y)-x}{y}\leq f^{\prime}(0).$

Regardless of whether $y$ is positive or negative, this means that
$x-f(y)\leq-yf^{\prime}(0)=\frac{-1}{a}x^{1-a}y$.

Now, let $-1<c\leq 0$ and suppose that $cx^{a}\leq y\leq 0$. Since
$f^{\prime}$ is increasing, we have that

$f^{\prime}(y)\geq
f^{\prime}(cx^{a})=\frac{1}{a}((1+c)x^{a})^{1/a-1}=\frac{1}{a}(1+c)^{1/a-1}x^{1-a},$

so

$f(y)-x\leq yf^{\prime}(y)\leq\frac{1}{a}(1+c)^{1/a-1}x^{1-a}y.$

∎

See 6.4.8

###### Proof.

We first derive an expression for $\partial_{i}L(\mathbf{w})$ given expert
reports $\mathbf{p}^{1},\dots,\mathbf{p}^{m}$, where $L(\mathbf{w})$ is the
log loss of the logarithmic pool $\mathbf{p}^{*}(\mathbf{w})$ of
$\mathbf{p}^{1},\dots,\mathbf{p}^{m}$ with weights $\mathbf{w}$, and $j$ is
the realized outcome. We have111It should be noted that $\nabla L(\mathbf{w})$
is most naturally thought of as living in $\mathbb{R}^{m}/T(\mathbf{1}_{m})$,
i.e. $m$-dimensional space modulo translation by the all-ones vector, since
$\mathbf{w}$ lives in a place that is orthogonal to the all-ones vector. As an
arbitrary but convenient convention, we define $\partial_{i}L(\mathbf{w})$ to
be the specific value derived below, and define the small gradient assumption
accordingly.

$\displaystyle\partial_{i}L(\mathbf{w})$
$\displaystyle=-\partial_{i}\ln\frac{\prod_{k=1}^{m}(p^{k}_{j})^{w_{k}}}{\sum_{\ell=1}^{n}\prod_{k=1}^{m}(p^{k}_{\ell})^{w_{k}}}=\partial_{i}\ln\left(\sum_{\ell=1}^{n}\prod_{k=1}^{m}(p^{k}_{\ell})^{w_{k}}\right)-\partial_{i}\ln\left(\prod_{k=1}^{m}(p^{k}_{j})^{w_{k}}\right)$
$\displaystyle=\frac{\sum_{\ell=1}^{n}\ln
p^{i}_{\ell}\cdot\prod_{k=1}^{m}(p^{k}_{\ell})^{w_{k}}}{\sum_{\ell=1}^{n}\prod_{k=1}^{m}(p^{k}_{\ell})^{w_{k}}}-\ln
p^{i}_{j}=\sum_{\ell=1}^{n}p^{*}_{\ell}(\mathbf{w})\ln p^{i}_{\ell}-\ln
p^{i}_{j}.$ (C.5)

Equation 6.2 now follows fairly straightforwardly. Equation C.2 tells us that
$\partial_{i}L(\mathbf{w})\leq-\ln p^{i}_{J}$, where $J$ is the random
variable corresponding to the realized outcome. Therefore, we have

$\displaystyle\text{Pr}\left[\partial_{i}L(\mathbf{w})\geq\zeta\right]$
$\displaystyle\leq\text{Pr}\left[-\ln
p_{J}^{i}\geq\zeta\right]=\text{Pr}\left[p_{J}^{i}\leq
e^{-\zeta}\right]=\sum_{j=1}^{n}\text{Pr}\left[J=j\enskip\&\enskip
p_{j}^{i}\leq e^{-\zeta}\right]$
$\displaystyle=\sum_{j=1}^{n}\text{Pr}\left[p_{j}^{i}\leq
e^{-\zeta}\right]\text{Pr}\left[J=j\mid p_{j}^{i}\leq
e^{-\zeta}\right]\leq\sum_{j=1}^{n}\text{Pr}\left[J=j\mid p_{j}^{i}\leq
e^{-\zeta}\right]\leq ne^{-\zeta},$

where the last step follows by the calibration property. This proves Equation
6.2.

We now prove Equation 6.3. The proof has a similar idea, but is somewhat more
technical. We begin by proving the following lemma; we again use the
calibration property in the proof.

######  Lemma C.2.4.

For all $q$, we have

$\text{Pr}\left[\forall j\exists i:p^{i}_{j}\leq q\right]\leq mnq.$

###### Proof.

Let $J$ be the random variable corresponding to the index of the outcome that
ends up happening. We have

$\displaystyle\text{Pr}\left[\forall j\exists i:p^{i}_{j}\leq q\right]$
$\displaystyle\leq\text{Pr}\left[\exists i:p^{i}_{J}\leq
q\right]=\sum_{j\in[n]}\text{Pr}\left[J=j\enskip\&\enskip\exists
i:p^{i}_{j}\leq q\right]$
$\displaystyle\leq\sum_{j\in[n]}\sum_{i\in[m]}\text{Pr}\left[J=j\enskip\&\enskip
p^{i}_{j}\leq q\right]$
$\displaystyle=\sum_{j\in[n]}\sum_{i\in[m]}\text{Pr}\left[p^{i}_{j}\leq
q\right]\text{Pr}\left[J=j\mid p^{i}_{j}\leq
q\right]\leq\sum_{j\in[n]}\sum_{i\in[m]}1\cdot q=mnq,$

where the fact that $\text{Pr}\left[J=j\mid p^{i}_{j}\leq q\right]\leq q$
follows by the calibration property. ∎

######  Corollary C.2.5.

For any reports $\mathbf{p}^{1},\dots,\mathbf{p}^{m}$, weight vector
$\mathbf{w}$, $i\in[m]$, and $j\in[n]$, we have

$\text{Pr}\left[p^{*}_{j}(\mathbf{w})\geq\frac{(p^{i}_{j})^{w_{i}}}{q}\right]\leq
mnq.$

###### Proof.

We have

$p^{*}_{j}(\mathbf{w})=\frac{\prod_{k=1}^{m}(p_{j}^{k})^{w_{k}}}{\sum_{\ell=1}^{n}\prod_{k=1}^{m}(p_{\ell}^{k})^{w_{k}}}\leq\frac{(p_{j}^{i})^{w_{i}}}{\sum_{\ell=1}^{n}\prod_{k=1}^{m}(p_{\ell}^{k})^{w_{k}}}.$

Now, assuming that there is an $\ell$ such that for every $k$ we have
$p^{k}_{\ell}>q$, the denominator is greater than $q$, in which case we have
$p^{*}_{j}(\mathbf{w})<\frac{(p^{i}_{j})^{w_{i}}}{q}$. Therefore, if
$p^{*}_{j}(\mathbf{w})\geq\frac{(p^{i}_{j})^{w_{i}}}{q}$, it follows that for
every $\ell$ there is a $k$ such that $p^{k}_{\ell}\leq q$. By Lemma C.2.4,
this happens with probability at most $mnq$. ∎

We now use Corollary C.2.5 to prove Equation 6.3. Note that the equation is
trivial for $\zeta<n$, so we assume that $\zeta\geq n$. By setting
$q:=e^{\frac{-\zeta}{n}}$, we may restate Equation 6.3 as follows: for any
$q\leq\frac{1}{e}$, any $i\in[m]$, and any weight vector $\mathbf{w}$,

$\text{Pr}\left[\partial_{i}L(\mathbf{w})\leq-\frac{n\ln
1/q}{w_{i}}\right]\leq mn^{2}q.$

(Note that the condition $q\leq\frac{1}{e}$ is equivalent to $\zeta\geq n$.)
We prove this result.

From Equation C.2, we have

$\partial_{i}L(\mathbf{w})=\sum_{j=1}^{n}p^{*}_{j}(\mathbf{w})\ln
p^{i}_{j}-\ln p^{i}_{j}\geq\sum_{j=1}^{n}p_{j}(\mathbf{w})\ln p^{i}_{j}.$

Now, it suffices to show that for each $j\in[n]$, the probability that
$p_{j}(\mathbf{w})\ln p^{i}_{j}\leq-\frac{\ln 1/q}{w_{i}}=\frac{\ln q}{w_{i}}$
is at most $mnq$; the desired result will then follow by the union bound. By
Corollary C.2.5, for each $j$ we have that

$\text{Pr}\left[p_{j}(\mathbf{w})\ln
p_{j}^{i}\leq\frac{(p_{j}^{i})^{w_{i}}}{q}\ln p_{j}^{i}\right]\leq mnq.$

Additionally, we know for a fact that $p_{j}(\mathbf{w})\ln p^{i}_{j}\geq\ln
p^{i}_{j}$ (since $p_{j}(\mathbf{w})\leq 1$), so in fact

$\text{Pr}\left[p_{j}(\mathbf{w})\ln
p_{j}^{i}\leq\max\left(\frac{(p_{j}^{i})^{w_{i}}}{q}\ln p_{j}^{i},\ln
p_{j}^{i}\right)\right]\leq mnq.$

It remains only to show that $\max\left(\frac{(p_{j}^{i})^{w_{i}}}{q}\ln
p_{j}^{i},\ln p_{j}^{i}\right)\geq\frac{\ln q}{w_{i}}$. If $p_{j}^{i}\geq
q^{1/w_{i}}$ then this is clearly true, since in that case $\ln
p_{j}^{i}\geq\frac{\ln q}{w_{i}}$. Now suppose that $p_{j}^{i}<q^{1/w_{i}}$.
Observe that $\frac{x^{w_{i}}}{q}\ln x$ decreases on $(0,e^{-1/w_{i}})$, and
that (since $q\leq\frac{1}{e}$) we have $q^{1/w_{i}}\leq e^{-1/w_{i}}$.
Therefore,

$\frac{(p_{j}^{i})^{w_{i}}}{q}\ln
p_{j}^{i}\leq\frac{(q^{1/w_{i}})^{w_{i}}}{q}\ln q^{1/w_{i}}=\frac{\ln
q}{w_{i}}.$

This completes the proof of Equation 6.3, and thus of Lemma 6.4.8. ∎

The following lemma lower bounds the regret of Algorithm 3 as a function of
$\zeta$.

######  Lemma C.2.6.

Consider a run of Algorithm 3. Let $\zeta$ be such that
$-\frac{\zeta}{w_{i}^{t}}\leq\partial_{i}L^{t}(\mathbf{w}^{t})\leq\zeta$ for
all $i,t$. The total regret is at most

$O\left(\zeta^{2(2-\alpha)/(1-\alpha)}T^{(5-\alpha)/(1-\alpha)}\right).$

###### Proof.

We first bound $w_{i}^{t}$ for all $i,t$. From Lemma 6.4.4, we have that

$(w_{i}^{t+1})^{\alpha-1}\leq(w_{i}^{t})^{\alpha-1}+\left(\frac{1}{\min_{i}w_{i}^{t}}+1\right)\eta_{t}\zeta\leq(w_{i}^{t})^{\alpha-1}+2\zeta.$

Here we use that $\frac{1}{\min_{i}w_{i}}+1\leq\frac{2}{\min_{i}w_{i}}$ and
that $\eta_{t}\leq\min_{i}w_{i}$. Therefore, we have that

$(w_{i}^{t})^{\alpha-1}\leq(w_{i}^{t-1})^{\alpha-1}+2\zeta\leq\dots\leq
m^{1-\alpha}+2\zeta(t-1)\leq m^{1-\alpha}+2\zeta T.$

Thus, $w_{i}^{t}\geq(m^{1-\alpha}+2\zeta T)^{1/(\alpha-1)}\geq\Omega((\zeta
T)^{1/(\alpha-1)})$ for all $i,t$.

We now use the standard regret bound for online mirror descent, see e.g. [312,
Theorem 6.8]:

$\text{Regret}\leq\max_{t}\frac{B_{R}(\mathbf{u};\mathbf{w}^{t})}{\eta_{T}}+\frac{1}{2\lambda}\sum_{t=1}^{T}\eta_{t}\left\lVert\nabla
L^{t}(\mathbf{w}^{t})\right\rVert_{*}^{2}$ (C.6)

where $B_{R}(\cdot;\cdot)$ is the Bregman divergence of with respect to $R$,
$\mathbf{u}$ is the optimal (overall loss-minimizing) point, $\lambda$ is a
constant such that $R$ is $\lambda$-strongly convex with respect to a norm of
our choice over $\Delta_{m}$, and $\left\lVert\cdot\right\rVert_{*}$ is the
dual norm of the aforementioned norm.

Note that for any $\mathbf{x}\in\Delta_{m}$, we have

$\max_{\mathbf{v}\in\Delta_{m}}B_{R}(\mathbf{v};\mathbf{x})=\max_{\mathbf{v}\in\Delta_{m}}R(\mathbf{v})-R(\mathbf{x})-\left\langle\nabla
R(\mathbf{x}),\mathbf{v}-\mathbf{x}\right\rangle\leq\frac{m^{1-\alpha}}{\alpha}+(\min_{i}x_{i})^{\alpha-1}.$

In the last step, we use the fact that $-\nabla
R(\mathbf{x})=(x_{1}^{\alpha-1},\dots,x_{m}^{\alpha-1})$ (all of these
coordinates are positive), so $-\left\langle\nabla
R(\mathbf{x}),\mathbf{v}-\mathbf{x}\right\rangle\leq\left\langle(x_{1}^{\alpha-1},\dots,x_{m}^{\alpha-1}),\mathbf{v}\right\rangle$,
and that all coordinates of $\mathbf{v}$ are non-negative and add to $1$.

Therefore, given our bound on $w_{i}^{t}$, this first component of our regret
bound (C.6) is at most

$\frac{1}{\eta_{T}}\left(\frac{m^{1-\alpha}}{\alpha}+m^{1-\alpha}+2\zeta
T\right)\leq O\left(\frac{\zeta T}{\eta_{T}}\right)\leq O\left(\frac{\zeta
T}{(\zeta T)^{1/(\alpha-1)}}\right)=O\left((\zeta
T)^{(2-\alpha)/(1-\alpha)}\right).$

To bound the second term, we choose to work with the $\ell_{1}$ norm. To show
that $R$ is $\lambda$-convex it suffices to show that for all
$\mathbf{x},\mathbf{y}\in\Delta_{m}$ we have
$\left\langle(\nabla^{2}R)(\mathbf{x})\mathbf{y},\mathbf{y}\right\rangle\geq\lambda\left\lVert\mathbf{y}\right\rVert^{2}$,
where $\nabla^{2}R$ is the Hessian matrix of $R$ ([339, Lemma 14]; see also
[312, Theorem 4.3]). Equivalently, we wish to find a $\lambda$ such that

$(1-\alpha)\sum_{i}x_{i}^{\alpha-2}y_{i}^{2}\geq\lambda.$

Since $x_{i}^{\alpha-2}\geq 1$ for all $i$, the left-hand side is at least
$(1-\alpha)\sum_{i}y_{i}^{2}\geq\frac{1-\alpha}{m}$, so
$\lambda=\frac{1-\alpha}{m}$ suffices.

Now, given $\mathbf{\theta}\in\mathbb{R}^{m}$, we have
$\left\lVert\mathbf{\theta}\right\rVert_{*}=\max_{\mathbf{x}:\left\lVert\mathbf{x}\right\rVert\leq
1}\left\langle\mathbf{\theta},\mathbf{x}\right\rangle$. In the case of the
$\ell_{1}$ primal norm, the dual norm is the largest absolute component of
$\mathbf{\theta}$. Thus, we have

$\left\lVert\nabla
L^{t}(\mathbf{x}^{t})\right\rVert_{*}\leq\frac{\zeta}{w_{i}^{t}}\leq
O\left(\zeta(\zeta
T)^{1/(1-\alpha)}\right)=O\left(\zeta^{(2-\alpha)/(1-\alpha)}T^{1/(1-\alpha)}\right).$

Since $\eta_{t}\leq O(T^{-1/2})$, we have that the second component of our
regret bound (C.6) is at most

$O\left(T\cdot
T^{-1/2}\cdot\zeta^{2(2-\alpha)/(1-\alpha)}T^{2/(1-\alpha)}\right)\leq
O\left(\zeta^{2(2-\alpha)/(1-\alpha)}T^{(5-\alpha)/(1-\alpha)}\right).$

This component dominates our bound on the regret of the first component, in
both $\zeta$ and $T$. This concludes the proof. ∎

See 6.4.9

###### Proof.

Let $Z$ be the minimum value of $\zeta$ such that
$-\frac{\zeta}{w_{i}^{t}}\leq\partial_{i}L^{t}(\mathbf{w}^{t})\leq\zeta$ for
all $i,t$. Note that by Lemma 6.4.8, we have that

$\text{Pr}\left[Z\geq
x\right]\leq\sum_{i=1}^{m}\sum_{t=1}^{T}(mn^{2}e^{-\frac{x}{n}}+ne^{-x})\leq
2m^{2}n^{2}Te^{-\frac{x}{n}}.$

Let $\mu$ be the constant hidden in the big-O of Lemma C.2.6, i.e. a constant
(dependent on $m$, $n$, and $\alpha$) such that

$\text{Regret}\leq\mu Z^{2(2-\alpha)/(1-\alpha)}T^{(5-\alpha)/(1-\alpha)}.$

Let $r(Z,T)$ be the expression on the right-hand side. The small gradient
assumption not holding is equivalent to $Z>12n\ln T$, or equivalently,
$r(Z,T)>r(12n\ln T,T)$. The expected regret of our algorithm conditional on
the small gradient assumption _not_ holding, times the probability of this
event, is therefore at most the expected value of $r(Z,T)$ conditional on the
value being greater than $r(12n\ln T,T)$, times this probability. This is
equal to

$\displaystyle r(12n\ln T,T)\cdot\text{Pr}\left[Z>12n\ln
T\right]+\int_{x=r(12n\ln T,T)}^{\infty}\text{Pr}\left[r(Z,T)\geq x\right]dx$
$\displaystyle\leq\sum_{k=11}^{\infty}r((k+1)n\ln
T,T)\cdot\text{Pr}\left[Z\geq kn\ln T\right]$
$\displaystyle\leq\sum_{k=11}^{\infty}\mu\cdot((k+1)n\ln
T)^{2(2-\alpha)/(1-\alpha)}T^{(5-\alpha)/(1-\alpha)}\cdot 2m^{2}n^{2}T\cdot
T^{-k}$
$\displaystyle\leq\sum_{k=11}^{\infty}\tilde{O}(T^{1+(5-\alpha)/(1-\alpha)-k})=\tilde{O}(T^{(5-\alpha)/(1-\alpha)-10}),$

as desired. (The first inequality follows by matching the first term with the
$k=11$ summand and upper-bounding the integral with subsequent summands,
noting that $r((k+1)n\ln T,T)\geq 1$.) ∎

Note that $\frac{5-\alpha}{1-\alpha}-10\leq\frac{5-1/2}{1-1/2}-10=-1$.
Therefore, the contribution to expected regret from the case that the small
gradient assumption does not hold is $\tilde{O}(T^{-1})$, which is negligible.
Together with Corollary 6.4.7 (which bounds regret under the small gradient
assumption), this proves Theorem 6.3.3.

##  Appendix D Details omitted from Chapter 8

###  D.1 Details omitted from Section 8.2

In Section 8.2, we claimed that a positive measure of $n\times n$ information
structures satisfy rectangle substitutes. To formalize this claim, we choose a
natural measure over $n\times n$ information structures, specified via the
following probability distribution over the values of $Y$ and
$\mathbb{P}[\sigma,\tau]$:

  * •

Alice has signals labeled $\sigma_{0},\dots,\sigma_{n-1}$; Bob has signals
labeled $\tau_{0},\dots,\tau_{n-1}$. Correspondingly, there are $n^{2}$ states
which we identify with the pair $(i,j)$. For each $i,j$, whenever
$\sigma=\sigma_{i}$ and $\tau=\tau_{j}$, $Y=y(i,j)$ where $y(i,j)$ is
uniformly random in $[0,1]$.

  * •

The probability distribution over states $(i,j)$ is selected uniformly from
the space of probability distributions over $n^{2}$ states.

######  Theorem D.1.1.

For every $n$, a positive measure of $n\times n$ information structures (per
the above measure) satisfy the rectangle substitutes condition.

###### Proof.

The proof is conceptually quite simple. It suffices to exhibit an information
structure in which the weak substitutes condition (i.e. Equation 8.1) holds
_strictly_ for every $S,T$ such that $\left\lvert S\right\rvert,\left\lvert
T\right\rvert\geq 2$. It then follows that for a sufficiently small $\delta$,
every information structure in the $\delta$-ball around this one111We can for
example define the distance between information structures $\mathcal{I}$ and
$\mathcal{I}^{\prime}$ as
$\sum_{i,j}(y(i,j)-y^{\prime}(i,j))^{2}+(\mathbb{P}[(i,j)]-\mathbb{P}^{\prime}[(i,j)])^{2}$.
also satisfies rectangle substitutes, completing the proof.222This uses the
continuity of the terms in Equation 8.1. Note that the continuity of
conditional expectations relies on the conditioning events having positive
probability, as is the case in the information structure that we exhibit. Note
also that we need not concern ourselves with cases in which $\left\lvert
S\right\rvert=1$ or $\left\lvert T\right\rvert=1$, since in those cases the
equation is necessarily an equality.

The information structure $\mathcal{I}$ that we exhibit is as follows: choose
any increasing, strictly concave function $f:[0,2(n-1)]\to\mathbb{R}$ (for
example, $f(x)=\sqrt{x}$). Let $y(i,j)=\frac{i+j}{2n}$, and let
$\mathbb{P}[(i,j)]$ be proportional to $\epsilon^{f(i+j)}$.

For convenience, define the _substitutes slack_ of an information structure to
be the additive margin by which the information structure satisfies weak
substitutes, i.e. the right-hand side of Equation 8.1 minus the left-hand side
for $S=\mathcal{S}$ and $T=\mathcal{T}$.

Fix a particular $S$ and $T$ such that $\left\lvert S\right\rvert,\left\lvert
T\right\rvert\geq 2$. We wish to show that for sufficiently small positive
values of $\epsilon$, Equation 8.1 holds strictly. We will show that the
substitutes slack of $\mathcal{I}\mid_{S,T}$, i.e. $\mathcal{I}$ restricted to
$S\times T$, is positive when $\epsilon$ is sufficiently small.

In order to prove this, we first consider the following (different)
information structure for values
$v,a,a^{\prime},b,b^{\prime},c,x,x^{\prime},y,y^{\prime}$ (obeying comparisons
that we specify below). Each row corresponds to a possible signal value
$\sigma$ for Alice, and each column a possible signal value $\tau$ for Bob.

$Y=\begin{bmatrix}v&v+b&b^{\prime}\\\ v+a&v+a+b&-\\\
a^{\prime}&-&-\end{bmatrix}\qquad\text{with probability proportional
to}\qquad\begin{bmatrix}1&y&y^{\prime}\\\ x&cxy&0\\\
x^{\prime}&0&0\end{bmatrix}$

In this information structure, suppose that $x^{\prime}\leq x\ll 1$;
$y^{\prime}\leq y\ll 1$; and $1\ll c\leq\frac{1}{x},\frac{1}{y}$ (so $xy\ll
cxy\leq x,y$). It can be verified (e.g. with a computer algebra system) that
the substitutes slack of this information structure is $2abcxy+O(xy)$.

We will transform this information structure into $\mathcal{I}_{S,T}$ while
(approximately) preserving substitutes slack. To foreshadow the
correspondence, define $i_{S}$ and $i^{\prime}_{S}$ be the smallest and second
smallest values of $i$ such that $\sigma_{i}\in S$, and define $j_{T}$ and
$j^{\prime}_{T}$ analogously. The rows of the information structure above will
correspond to $\sigma=\sigma_{i_{S}},\sigma_{i^{\prime}_{S}}$, and all other
values of $\sigma\in S$, in that order; the columns will correspond to
$\tau=\tau_{j_{T}},\tau_{j^{\prime}_{T}}$, and all other values of $\tau\in
T$, in that order.

Set $x:=\epsilon^{f(i_{S}^{\prime}+j_{T})-f(i_{S}+j_{T})}$,
$y:=\epsilon^{f(i_{S}+j^{\prime}_{T})-f(i_{S}+j_{T})}$, and
$c:=\epsilon^{f(i_{S}+j_{T})+f(i^{\prime}_{S}+j^{\prime}_{T})-f(i_{S}+j^{\prime}_{T})-f(i^{\prime}_{S}+j_{T})}$,
so that $cxy=\epsilon^{f(i^{\prime}_{S}+j^{\prime}_{T})-f(i_{S}+j_{T})}$. Note
that these values satisfy the aforementioned inequalities involving $x$, $y$,
and $c$. (The fact that $1\ll c$ follows from the strict concavity of $f$.)
Set $v:=\frac{i_{S}}{2n}$, $a:=\frac{i^{\prime}_{S}-i_{S}}{2n}$, and
$b:=\frac{j^{\prime}_{T}-j_{T}}{2n}$. Set $x^{\prime}$ so that
$\mathbb{P}[i>i^{\prime}_{S}\mid i\in
S,j=j_{T}]=\frac{x^{\prime}}{1+x+x^{\prime}}$ and $y^{\prime}$ so that
$\mathbb{P}[j>j^{\prime}_{T}\mid i=i_{S},j\in
T]=\frac{y^{\prime}}{1+y+y^{\prime}}$. We set
$a^{\prime}:=\mathbb{E}\left[y(i,j_{T})\mid i>i^{\prime}_{S},i\in S\right]$
and set $b^{\prime}:=\mathbb{E}\left[y(i_{S},j)\mid j>j^{\prime}_{T},j\in
T\right]$.

We now make the following transformation to this information structure: we
replace the third row with $\left\lvert S\right\rvert-2$ rows, each
corresponding to a different $i>i^{\prime}_{S}$. As before, each signal will
only be possible in conjunction with Bob’s first signal; the value of $Y$ for
the signal corresponding to $\sigma_{i}$ in $\mathcal{I}$ will be
$\frac{i+j_{T}}{2n}$, and the probability will be $\mathbb{P}[(i,j_{T})]$.
Note that this simply “splits” Alice’s third signal into multiple (more
informative) signals while preserving the total probability and expectation
(this is due to how we picked $a^{\prime},b^{\prime},x^{\prime},y^{\prime}$
above). This does not affect the substitutes slack of the information
structure, because the value of Bob’s signal does not change as a result of
the transformation (regardless of whether Alice’s signal is known).

We make the same transformation but this time to Bob, replacing the third
column with $\left\lvert T\right\rvert-2$ columns. The transformation is
otherwise analogous, and the substitutes slack again does not change.

Finally, in our last transformation we make this information structure match
$\mathcal{I}$ exactly. Note that the information structures already match in
the first row $(i=i_{S})$, and in the first column $(j=j_{T})$, and in the
(second row, second column) entry ($(i,j)=(i^{\prime}_{S},j^{\prime}_{T})$).
All other entries in $\mathcal{I}$ have probabilities that are $o(cxy)$
(recall that
$cxy=\epsilon^{f(i^{\prime}_{S}+j^{\prime}_{T})-f(i_{S}+j_{T})}$). As a
consequence, adding these entries to the information structure that we are
transforming only changes the substitutes slack by $o(cxy)$.

Therefore, $\mathcal{I}$ has substitutes slack
$2abcxy+o(cxy)\geq\frac{2}{n^{2}}\epsilon^{f(i^{\prime}_{S}+j^{\prime}_{T})-f(i_{S}+j_{T})}(1+o(1))$.
This is positive for $\epsilon$ sufficiently small, as desired.

We complete the proof by setting $\epsilon$ to be such that it is sufficiently
small (in the above argument) for all $S,T$ such that $\left\lvert
S\right\rvert,\left\lvert T\right\rvert\geq 2$. ∎

###  D.2 Details omitted from Section 8.3

######  Proposition D.2.1.

Consider the following protocol, parametrized by $\epsilon>0$. Alice and Bob
send their initial expectations to each other, rounding to the nearest
multiple of $\epsilon$. This protocol entails communicating $O(\log
1/\epsilon)$ bits. At the end of the protocol, Alice and Bob
$\epsilon^{2}/2$-agree and are $\epsilon^{2}$-accurate (with respect to
$G(x)=x^{2}$).

###### Proof.

Let $S$ be the set of possible signals of Alice at the end of the protocol
which are consistent with the protocol transcript, and define $T$ likewise for
Bob. Recall that we use $\mathcal{S}$ and $\mathcal{T}$ to denote the sets of
all of Alice’s and Bob’s possible signals, respectively. We have

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\right]\leq\mathbb{E}\left[(\mu_{\sigma}-\mu_{S})^{2}\right]\leq\epsilon^{2},$

since $\mu_{\sigma}$ and $\mu_{S})$ are guaranteed to be within $\epsilon$ of
each other by construction. Thus, Bob is $\epsilon^{2}$-accurate, and likewise
for Alice. By the $\frac{1}{2}$-approximate triangle inequality for
$G(x)=x^{2}$ (see Section 8.4), it follows that Alice and Bob
$\epsilon^{2}/2$-agree. ∎

###  D.3 Details omitted from Section 8.4

######  Proposition D.3.1.

Let $G$ be a differentiable convex function on the interval $[0,1]$. For all
$0\leq a\leq b\leq 1$, we have

  1. (i)

$\frac{1}{2}(D_{G}(a\parallel x)+D_{G}(b\parallel x))\geq\text{JB}_{G}(a,b)$
for every $x\in[0,1]$.

  2. (ii)

$\text{JB}_{G}$ satisfies the reverse triangle inequality: for every
$x\in[a,b]$, we have
$\text{JB}_{G}(a,x)+\text{JB}_{G}(x,b)\leq\text{JB}_{G}(a,b)$.

  3. (iii)

For all $a\leq a^{\prime}\leq b^{\prime}\leq b$, we have
$\text{JB}_{G}(a^{\prime},b^{\prime})\leq\text{JB}_{G}(a,b)$.

  4. (iv)

For a random variable $X$ supported on $[a,b]$, we have

$\mathbb{E}\left[D_{G}(X\parallel\mathbb{E}\left[X\right])\right]=\mathbb{E}\left[G(X)\right]-G(\mathbb{E}\left[X\right])\leq
2\text{JB}_{G}(a,b).$

###### Proof.

Fact (i) follows from Proposition 2.1.8. Regarding Fact (ii), without loss of
generality assume that $x\leq\frac{a+b}{2}$ and that
$G(x)=G\left(\frac{a+b}{2}\right)$ (uniformly adding a constant to the
derivative of $G$ does not change any Jensen-Bregman divergence, hence the
second assumption). Then $G\left(\frac{a+x}{2}\right)\geq G(x)$, so
$\text{JB}_{G}(a,x)\leq\frac{G(a)-G(x)}{2}$. Since
$\frac{b+x}{2}\geq\frac{a+b}{2}$, we also have that
$G\left(\frac{b+x}{2}\right)\geq G(x)$, so
$\text{JB}_{G}(b,x)\leq\frac{G(b)-G(x)}{2}$. Thus, we have

$\text{JB}_{G}(a,x)+\text{JB}_{G}(b,x)\leq\frac{G(a)+G(b)}{2}-G(x)=\frac{G(a)+G(b)}{2}-G\left(\frac{a+b}{2}\right)=\text{JB}_{G}(a,b).$

Fact (iii) follows from Fact (ii): we have

$\text{JB}_{G}(a,b)=\text{JB}_{G}(a,a^{\prime})+\text{JB}_{G}(a^{\prime},b^{\prime})+\text{JB}_{G}(b^{\prime},b)\geq\text{JB}_{G}(a^{\prime},b^{\prime}).$

Regarding the equality in Fact (iv), we have

$\displaystyle\mathbb{E}\left[D_{G}(X\parallel\mathbb{E}\left[X\right])\right]$
$\displaystyle=\mathbb{E}\left[G(X)-G(\mathbb{E}\left[X\right])-(X-\mathbb{E}\left[X\right])G^{\prime}(\mathbb{E}\left[X\right])\right]$
$\displaystyle=\mathbb{E}\left[G(X)-G(\mathbb{E}\left[X\right])\right]=\mathbb{E}\left[G(X)\right]-G(\mathbb{E}\left[X\right]),$

where the first step follows from the fact that
$\mathbb{E}\left[(X-\mathbb{E}\left[X\right])G^{\prime}(\mathbb{E}\left[X\right])\right]=G^{\prime}(\mathbb{E}\left[X\right])\mathbb{E}\left[X-\mathbb{E}\left[X\right]\right]$,
and $\mathbb{E}\left[X-\mathbb{E}\left[X\right]\right]=0$.

Regarding the inequality in Fact (iv), without loss of generality assume that
$\mathbb{E}\left[X\right]\leq\frac{a+b}{2}$. By convexity we have that

$G\left(\frac{a+b}{2}\right)\leq\frac{\frac{b-a}{2}}{b-\mathbb{E}\left[X\right]}G(\mathbb{E}\left[X\right])+\frac{\frac{a+b}{2}-\mathbb{E}\left[X\right]}{b-\mathbb{E}\left[X\right]}G(b),$

so

$\displaystyle\text{JB}_{G}(a,b)$
$\displaystyle=G(a)+G(b)-2G\left(\frac{a+b}{2}\right)$ $\displaystyle\geq
G(a)+G(b)-\frac{b-a}{b-\mathbb{E}\left[X\right]}G(\mathbb{E}\left[X\right])-\frac{a+b-2\mathbb{E}\left[X\right]}{b-\mathbb{E}\left[X\right]}G(b)$
$\displaystyle=G(a)+\frac{\mathbb{E}\left[X\right]-a}{b-\mathbb{E}\left[X\right]}G(b)-\frac{b-a}{b-\mathbb{E}\left[X\right]}G(\mathbb{E}\left[X\right])$
$\displaystyle=\frac{b-a}{b-\mathbb{E}\left[X\right]}\left(\frac{b-\mathbb{E}\left[X\right]}{b-a}G(a)+\frac{\mathbb{E}\left[X\right]-a}{b-a}G(b)-G(\mathbb{E}\left[X\right])\right)$
$\displaystyle\geq\frac{b-\mathbb{E}\left[X\right]}{b-a}G(a)+\frac{\mathbb{E}\left[X\right]-a}{b-a}G(b)-G(\mathbb{E}\left[X\right])\geq\mathbb{E}\left[G(X)\right]-G(\mathbb{E}\left[X\right]).$

In the last step we use the fact that for a convex function $f$ and a random
variable $X$ defined on an interval $[a,b]$ with mean $\mu$, the maximum
possible value of $\mathbb{E}\left[f(X)\right]$ is attained if $X$ is either
$a$ or $b$ with the appropriate probabilities. ∎

See 8.4.8

###### Proof.

Suppose that Alice and Bob do not $\epsilon$-agree at time step $t$, and
without loss of generality assume that the next turn (number $t+1$) is
Alice’s. We begin by observing that, by Proposition D.3.1 (i), we have

$\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})+D_{G}(\mu_{S_{t}\tau}\parallel\mu_{S_{t}T_{t}})\right]\geq
2\mathbb{E}\left[\text{JB}_{G}(\mu_{\sigma
T_{t}},\mu_{S_{t}\tau})\right]>2\epsilon.$

Therefore, either $\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{2\epsilon}{3}$ or
$\mathbb{E}\left[D_{G}(\mu_{S_{t}\tau}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{4\epsilon}{3}$.

##### Case 1:

$\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{2\epsilon}{3}$. Let us use
“hi,” “lo,” and “md” to denote the events that Alice says “high,” Alice says
“low,” and Alice says “medium,” respectively. We have

$\displaystyle\frac{2\epsilon}{3}$
$\displaystyle\leq\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\right]=\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\mid S_{t},T_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi or lo}}\mid
S_{t},T_{t}\right]\right]+\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{md}}\mid
S_{t},T_{t}\right]\right]$
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi or lo}}\mid
S_{t},T_{t}\right]\right]+\frac{\epsilon}{2},$

where “$\mid S_{t},T_{t}$” is short for “$\mid\sigma\in S_{t},\tau\in T_{t}$,”
a notation we use throughout the proof. We thus have

$\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi}}\mid
S_{t},T_{t}\right]\right]+\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{lo}}\mid
S_{t},T_{t}\right]\right]\geq\frac{\epsilon}{6}.$ (D.1)

We now make use of the following lemma.

######  Lemma D.3.2.

Suppose that turn $t+1$ is Alice’s. Let “hi” denote the event that Alice says
“high.” Let $\alpha:=\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi}}\mid
S_{t},T_{t}\right]$. Then

$\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi}}\mid
S_{t},T_{t}\right]\geq\frac{\alpha\epsilon}{8M+2\epsilon}.$

The analogous statement is true if Alice says “low,” and likewise if it is
instead Bob’s turn.

We assume Lemma D.3.2 and return to prove it afterward. This lemma translates
Equation D.1 into a statement about how much Charlie learns. Specifically, we
have that

$\displaystyle\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\right]=\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\mid
S_{t},T_{t}\right]\right]$
$\displaystyle\geq\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi}}\mid
S_{t},T_{t}\right]\right]+\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{lo}}\mid
S_{t},T_{t}\right]\right]$
$\displaystyle\geq\frac{\epsilon}{8M+2\epsilon}(\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{hi}}\mid
S_{t},T_{t}\right]\right]+\mathbb{E}\left[\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t}}\parallel\mu_{S_{t}T_{t}})\cdot\mathbbm{1}_{\text{lo}}\mid
S_{t},T_{t}\right]\right])$
$\displaystyle\geq\frac{\epsilon^{2}}{6(8M+2\epsilon)}.$

##### Case 2:

$\mathbb{E}\left[D_{G}(\mu_{S_{t}\tau}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{4\epsilon}{3}$.
Using the Pythagorean theorem to write the same Bregman divergence in two
ways, we have that

$\displaystyle\mathbb{E}\left[D_{G}(\mu_{S_{t+1}\tau}\parallel\mu_{S_{t+1}T_{t+1}})\right]+\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\right]=\mathbb{E}\left[D_{G}(\mu_{S_{t+1}\tau}\parallel\mu_{S_{t}T_{t}})\right]$
$\displaystyle=\mathbb{E}\left[D_{G}(\mu_{S_{t+1}\tau}\parallel\mu_{S_{t}\tau})\right]+\mathbb{E}\left[D_{G}(\mu_{S_{t}\tau}\parallel\mu_{S_{t}T_{t}})\right]\geq\mathbb{E}\left[D_{G}(\mu_{S_{t}\tau}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{4\epsilon}{3}.$

This means that one of the two summands on the left-hand side is at least
$\frac{2\epsilon}{3}$.

Case 2a:
$\mathbb{E}\left[D_{G}(\mu_{S_{t+1}\tau}\parallel\mu_{S_{t+1}T_{t+1}})\right]\geq\frac{2\epsilon}{3}$.
In that case we have that

$\mathbb{E}\left[D_{G}(\mu_{S_{t+2}T_{t+2}}\parallel\mu_{S_{t+1}T_{t+1}})\right]\geq\frac{\epsilon^{2}}{6(8M+2\epsilon)}$

by the same logic as in Case 1.

Case 2b:
$\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{2\epsilon}{3}\geq\frac{\epsilon^{2}}{12\epsilon}\geq\frac{\epsilon^{2}}{6(8M+2\epsilon)}$.

In each of our cases, we have that

$\displaystyle\mathbb{E}\left[D_{G}(Y\parallel\mu_{S_{t}T_{t}})-D_{G}(Y\parallel\mu_{S_{t+2}T_{t+2}})\right]=\mathbb{E}\left[D_{G}(\mu_{S_{t+2}T_{t+2}}\parallel\mu_{S_{t}T_{t}})\right]$
$\displaystyle=\mathbb{E}\left[D_{G}(\mu_{S_{t+2}T_{t+2}}\parallel\mu_{S_{t+1}T_{t+1}})\right]+\mathbb{E}\left[D_{G}(\mu_{S_{t+1}T_{t+1}}\parallel\mu_{S_{t}T_{t}})\right]\geq\frac{\epsilon^{2}}{6(8M+2\epsilon)}.$

Therefore, the total number of steps until agreement is first reached cannot
be more than

$2\cdot\frac{M}{\frac{\epsilon^{2}}{6(8M+2\epsilon)}}=\frac{24M(4M+\epsilon)}{\epsilon^{2}}.$

This completes the proof. ∎

We now prove Lemma D.3.2.

###### Proof of Lemma D.3.2.

We will restrict our probability space to outcomes where Charlie knows
$S_{t},T_{t}$ at time $t$ (and thus omit “$\mid S_{t},T_{t}$” from here on).
For convenience, we will let $A:=\mu_{\sigma T_{t}}$ be Alice’s expectation (a
random variable) and $c:=\mu_{S_{t}T_{t}}$ be Charlie’s expectation (which is
a particular number in $[0,1]$). We will let
$\epsilon^{\prime}:=\frac{\epsilon}{2}$, so that if Alice says “high” then
Charlie knows that $A>c$ and that $D_{G}(A\parallel c)\geq\epsilon^{\prime}$.

Let $D(x):=D_{G}(x\parallel c)=G(x)-G(c)-G^{\prime}(c)(x-c)$, and let
$\hat{a}_{h}:=\mathbb{E}\left[A\mid\text{hi}\right]$. Note that if Alice says
“high” then $\mu_{S_{t+1}T_{t+1}}=\hat{a}_{h}$. In our new notation, we may
write
$\alpha=\mathbb{E}\left[D(A)\mid\text{hi}\right]\cdot\mathbb{P}[\text{hi}]$,
and we wish to show that
$D(\hat{a}_{h})\cdot\mathbb{P}[\text{hi}]\geq\frac{\alpha\epsilon^{\prime}}{2(M+\epsilon^{\prime})}$.
Put otherwise, our goal is to show that

$\frac{D(\hat{a}_{h})}{\mathbb{E}\left[D(A)\mid\text{hi}\right]}\geq\frac{\epsilon^{\prime}}{2(M+\epsilon^{\prime})}.$

For convenience we will let $B$ denote the quantity on the left-hand side.

Let $a_{\text{hmin}}$ be the number larger than $c$ such that
$D(a)=\epsilon^{\prime}$, so that $A\geq a_{\text{hmin}}$ whenever Alice says
“high.”333If $D(a)<\epsilon^{\prime}$ for all $a>c$ then Alice never says
“high” and the lemma statement is trivial. Observe that since $D$ is convex
(Bregman divergences are convex in their first argument), for a fixed value of
$\hat{a}_{h}$, the value of $\mathbb{E}\left[D(A)\mid\text{hi}\right]$ is
maximized when $A$ is either $a_{\text{hmin}}$ or $1$ (with probabilities
$\frac{1-\hat{a}_{h}}{1-a_{\text{hmin}}}$ and
$\frac{\hat{a}_{h}-a_{\text{hmin}}}{1-a_{\text{hmin}}}$, respectively).
Therefore we have

$B=\frac{D(\hat{a}_{h})}{\mathbb{E}\left[D(A)\mid\text{hi}\right]}\geq\frac{D(\hat{a}_{h})(1-a_{\text{hmin}})}{(1-\hat{a}_{h})\epsilon^{\prime}+(\hat{a}_{h}-a_{\text{hmin}})D(1)}.$
(D.2)

##### Case 1:

$(1-\hat{a}_{h})\epsilon^{\prime}\geq(\hat{a}_{h}-a_{\text{hmin}})D(1)$. In
that case we have

$B\geq\frac{D(\hat{a}_{h})(1-a_{\text{hmin}})}{2(1-\hat{a}_{h})\epsilon^{\prime}}\geq\frac{\epsilon^{\prime}(1-a_{\text{hmin}})}{2(1-\hat{a}_{h})\epsilon^{\prime}}\geq\frac{1}{2}\geq\frac{\epsilon^{\prime}}{2(M+\epsilon^{\prime})}.$

##### Case 2:

$(1-\hat{a}_{h})\epsilon^{\prime}\leq(\hat{a}_{h}-a_{\text{hmin}})D(1)$. In
that case we have

$B\geq\frac{D(\hat{a}_{h})(1-a_{\text{hmin}})}{2(\hat{a}_{h}-a_{\text{hmin}})D(1)}.$
(D.3)

Case 2a: $D(1)\leq\frac{1-c}{\hat{a}_{h}-c}(M+\epsilon^{\prime})$. Then we
have

$B\geq\frac{D(\hat{a}_{h})(1-a_{\text{hmin}})}{2(\hat{a}_{h}-a_{\text{hmin}})\cdot\frac{1-c}{\hat{a}_{h}-c}(M+\epsilon^{\prime})}\geq\frac{\epsilon^{\prime}}{2(M+\epsilon^{\prime})}\cdot\frac{(1-a_{\text{hmin}})(\hat{a}_{h}-c)}{(\hat{a}_{h}-a_{\text{hmin}})(1-c)}.$

(In the last step we again use that $D(\hat{a}_{h})\geq\epsilon$.) Now, it is
easy to verify that the second fraction is at least $1$ (this comes down to
the fact that $a_{\text{hmin}}\geq c$), so we indeed have that
$B\geq\frac{\epsilon^{\prime}}{2(M+\epsilon^{\prime})}$.

Case 2b: $D(1)\geq\frac{1-c}{\hat{a}_{h}-c}(M+\epsilon^{\prime})$. We claim
that for all $x\geq c$, we have that

$D(x)\geq\frac{x-c}{1-c}D(1)-M.$ (D.4)

To see this, suppose for contradiction that for some $x$ we have
$D(x)<\frac{x-c}{1-c}D(1)-M$. Then

$\displaystyle G(x)-G(c)-G^{\prime}(c)(x-c)$
$\displaystyle<\frac{x-c}{1-c}(G(1)-G(c)-G^{\prime}(c)(1-c))-M$
$\displaystyle(1-c)G(x)-(1-c)G(c)$ $\displaystyle<(x-c)G(1)-(x-c)G(c)-(1-c)M$
$\displaystyle G(x)+M$ $\displaystyle<\frac{(1-x)G(c)+(x-c)G(1)}{1-c}.$

On the other hand, we have that both $G(c)$ and $G(1)$ are less than or equal
to $G(x)+M$, by definition of $M$. This means that

$G(1),G(c)<\frac{(1-x)G(c)+(x-c)G(1)}{1-c}$

but this implies that $G(1)<G(c)$ and that $G(c)<G(1)$, a contradiction.

Plugging in $x=\hat{a}_{h}$ into Equation D.4, we find that

$D(\hat{a}_{h})\geq\frac{\hat{a}_{h}-c}{1-c}D(1)-M.$

Plugging this bound into Equation D.3, we get that

$\displaystyle B$
$\displaystyle\geq\frac{\left(\frac{\hat{a}_{h}-c}{1-c}D(1)-M\right)(1-a_{\text{hmin}})}{2(\hat{a}_{h}-a_{\text{hmin}})D(1)}=\frac{1-a_{\text{hmin}}}{2(\hat{a}_{h}-a_{\text{hmin}})}\cdot\frac{\hat{a}_{h}-c}{1-c}\left(1-\frac{M}{\frac{\hat{a}_{h}-c}{1-c}D(1)}\right)$
$\displaystyle\geq\frac{1-a_{\text{hmin}}}{2(\hat{a}_{h}-a_{\text{hmin}})}\cdot\frac{\hat{a}_{h}-c}{1-c}\left(1-\frac{M}{M+\epsilon^{\prime}}\right)\geq\frac{\epsilon^{\prime}}{2(M+\epsilon^{\prime})},$

where in the second-to-last step we use that
$D(1)\geq\frac{1-c}{\hat{a}_{h}-c}(M+\epsilon^{\prime})$ and in the last step
we again use the fact that
$\frac{(1-a_{\text{hmin}})(\hat{a}_{h}-c)}{(\hat{a}_{h}-a_{\text{hmin}})(1-c)}\geq
1$. ∎

See 8.4.16

###### Proof.

We will partition $[0,1]$ into a number $N$ of small intervals
$I_{1}=[x_{0}=0,x_{1})$, $I_{2}=[x_{1},x_{2})$, $I_{3}=[x_{2},x_{3})$, …,
$I_{N}=[x_{N-1},x_{N}=1]$ with certain desirable properties (which we will
describe below). For $k\in[N]$, we will let
$S^{(k)}:=\\{\sigma\in\mathcal{S}:\mu_{\sigma}\in I_{k}\\}$. For a given
$\sigma\in\mathcal{S}$, we will let $k(\sigma)$ be the $k$ such that
$\sigma\in S^{(k)}$.

Our goal is to upper bound the expectation of
$D_{G}(\mu_{\sigma\tau}\parallel\mu_{\tau})$. In pursuit of this goal, we
observe that by Proposition 2.3.12 we have

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{\tau})\right]=\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{S^{(k(\sigma))}\tau})\right]+\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right].$
(D.5)

Now, for any $k$, by applying Equation 8.7 to $S=S^{(k)}$ and $T=\mathcal{T}$,
we know that

$\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k)}})\mid
S^{(k)}\right]\geq\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{S^{(k)}\tau})\mid
S^{(k)}\right].$

(Here, “$\mid S^{(k)}$” is short for “$\mid\sigma\in S^{(k)}$.”) This is our
only use of the rectangle substitutes assumption. Now, taking the expectation
over $k$ (i.e. choosing each $k$ with probability equal to
$\mathbb{P}[\sigma\in S^{(k)}]$), we have that

$\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k(\sigma))}})\right]\geq\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{S^{(k(\sigma))}\tau})\right].$

Together with Equation D.5, this tells us that

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{\tau})\right]\leq\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k(\sigma))}})\right]+\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right].$
(D.6)

Our goal will be to bound the two summands in Equation D.6. We will specify
the boundaries of the intervals $I_{1},\dots,I_{N}$ with this goal in mind.

On an intuitive level, we are hoping for two things to be true:

  * •

In order for the first summand to be small, we want $\mu_{\sigma}$ and
$\mu_{S^{(k(\sigma))}}$ to be similar in value. In other words, we want each
interval is “short” (for a notion of shortness with respect to $G$ that we are
about to discuss).

  * •

In order for the second summand to be small, we want
$\mu_{S^{(k(\sigma))}\tau}$ and $\mu_{\tau}$ to be similar in value. In other
words, the estimate of a third party who knows $\tau$ shouldn’t change much
upon learning $k(\sigma)$. One way to ensure this is by creating the intervals
in a way that makes the third party very confident about the value of
$k(\sigma)$ before learning it. Intuitively this should be true because Alice
and Bob approximately agree, so Alice’s estimate is likely to be close to
Bob’s. However, we must be careful to strategically choose the boundaries of
our intervals $x_{1},\dots,x_{N-1}$ so that Alice’s and Bob’s estimates are
unlikely to be on opposite sides of a boundary.444This limits how many
intervals we can reasonably use, which is why we cannot make our intervals
arbitrarily short to satisfy the first of our two criteria.

What, formally, do we need for the first summand to be small? For any $k$, we
have $\mu_{S^{(k(\sigma))}}=\mathbb{E}\left[\mu_{\sigma}\mid\sigma\in
S^{(k)}\right]$. We can apply Proposition D.3.1 (iv) to the random variable
$X=\mu_{\sigma}$ on the probability subspace given by $\sigma\in S^{(k)}$.
Since $X$ takes on values in $I_{k}$, we have that

$\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k)}})\mid
S^{(k)}\right]\leq 2\text{JB}_{G}(I_{k}),$ (D.7)

where $\text{JB}_{G}(I_{k})$ is shorthand for the Jensen-Bregman divergence
between the endpoints of $I_{k}$. Therefore, if $\text{JB}_{G}(I_{k})$ is
small for all $k$, then the first summand (which is an expected value of
$\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k)}})\mid S^{(k)}\right]$
over $k\in[N]$) is also small.

What about the second summand? As per the intuition above, we wish to choose
our boundary points $x_{1},\dots,x_{N-1}$ so that Alice’s and Bob’s estimates
are unlikely to be on opposite sides of any boundary. Let
$\mu_{-}=\min(\mu_{\sigma},\mu_{\tau})$ be the smaller of the two estimates
and $\mu_{+}=\max(\mu_{\sigma},\mu_{\tau})$ be the larger one. We say that
$\mu_{-},\mu_{+}$ _thwart_ a point $x\in(0,1)$ if $\mu_{-}\leq x\leq\mu_{+}$
and $\mu_{-}\neq\mu_{+}$. We define the _thwart density_ of $x$ to be

$\rho(x):=\mathbb{P}[\mu_{-},\mu_{+}\text{ thwart }x].$

Roughly speaking, we will choose $x_{1},\dots,x_{N-1}$ such that $\rho(x_{k})$
is small on average.

We will approach this problem by first creating intervals to satisfy the first
criterion (short intervals), without regard to the second, and then modifying
them to satisfy the second without compromising the first. Formally, we choose
our intervals according to the following algorithm.

  1. 1.

Choose points $0<x_{1}^{\prime}<x_{2}^{\prime}<\dots<x_{N-2}^{\prime}<1$ such
that the $N-1$ intervals thus created all have Jensen-Bregman divergence
between $\beta$ and $\frac{2\beta}{c}$, inclusive, where $\beta$ and $c$ are
as in the statement of Lemma 8.4.16. ($N$ is not pre-determined; it is defined
as one more than the number of intervals created.) (See footnote for why this
is possible.555Define $x_{1}^{\prime}$ so that
$\text{JB}_{G}(0,x_{1}^{\prime})=\frac{2\beta}{c}$ (this is possible because
$\text{JB}_{G}$ is continuous in its arguments). Define $x_{2}^{\prime}$ so
that $\text{JB}_{G}(x_{1}^{\prime},x_{2}^{\prime})=\frac{2\beta}{c}$. Keep
going until an endpoint $x_{N-3}^{\prime}$ is defined such that adding
$x_{N-2}^{\prime}$ as before would leave an interval $(x_{N-2}^{\prime},1)$
with Jensen-Bregman divergence less than $\frac{2\beta}{c}$. Now, instead of
defining $x_{N-2}^{\prime}$ in this way, define it so that
$\text{JB}_{G}(x_{N-3}^{\prime},x_{N-2}^{\prime})=\text{JB}_{G}(x_{N-2}^{\prime},1)$.
Since $\text{JB}_{G}(x_{N-3}^{\prime},1)\geq\frac{2\beta}{c}$, the
$c$-approximate triangle inequality that we have by assumption tells us that
$\text{JB}_{G}(x_{N-3}^{\prime},x_{N-2}^{\prime})=\text{JB}_{G}(x_{N-2}^{\prime},1)\geq\beta$.)

  2. 2.

Let $x_{0}^{\prime}:=0,x_{N-1}^{\prime}:=1$ for convenience. Define
$I_{k}^{\prime}:=[x_{k-1}^{\prime},x_{k}^{\prime}]$. For $k\in[N-1]$, let
$\alpha_{k}:=\inf_{x\in I_{k}^{\prime}}\rho(x)$. Let $x_{k}\in I_{k}^{\prime}$
be such666If the infimum is achieved (e.g. if the space of signals to Alice
and Bob is finite), then we can set $x_{k}:=\arg\min_{x}\rho(x)$. Our
algorithm works in more generality, at the expense of a factor of $2$ in our
final bound. Note that by replacing $2$ with a smaller constant can
arbitrarily reduce this factor. that $\rho(x_{k})\leq 2\alpha_{k}$.

  3. 3.

Return the intervals
$I_{1}=[0,x_{1}),I_{2}=[x_{1},x_{2}),\dots,I_{N}=[x_{N-1},1]$.

ALGORITHM 3 Partitioning $[0,1]$ into intervals $I_{1},\dots,I_{N}$

We begin by observing that for any $k\in[N]$, we have

$\text{JB}_{G}(I_{k})=\text{JB}_{G}(x_{k-1},x_{k})\leq\text{JB}_{G}(x_{k-2}^{\prime},x_{k}^{\prime})\leq\frac{1}{c}(\text{JB}_{G}(x_{k-2}^{\prime},x_{k-1}^{\prime})+\text{JB}_{G}(x_{k-1}^{\prime},x_{k}^{\prime}))\leq\frac{4\beta}{c^{2}}$

where for convenience we define $x_{-1}^{\prime}:=0,x_{N}^{\prime}:=1$.
Therefore, by Equation D.7, we have

$\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k(\sigma))}})\right]\leq\frac{8\beta}{c^{2}}.$
(D.8)

It remains to bound the second summand of Equation D.6,
$\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]$,
which is the bulk of the proof. We proceed in two steps:

  1. (1)

(Lemma D.3.3) We show that $\sum_{k=1}^{N}\alpha_{k}$ is small. This means
that Alice’s and Bob’s estimates are unlikely to lie on opposite sides of some
boundary point $x_{k}$. As a consequence, Bob is highly likely to know
$k(\sigma)$ with a lot of confidence

  2. (2)

(Lemma D.3.6) We bound the second summand as a function of
$\sum_{k=1}^{N}\alpha_{k}$. The intuition is that if $\sum_{k}\alpha_{k}$ is
small, then Bob is highly likely to know $k(\sigma)$ with a lot of confidence,
which means that he does not learn too much from learning $k(\sigma)$.

We begin with the first step; recall our notation
$\mu^{-}:=\min(\mu_{\sigma},\mu_{\tau})$ and
$\mu^{+}:=\max(\mu_{\sigma},\mu_{\tau})$.

######  Lemma D.3.3.

$2\sum_{k=1}^{N}\alpha_{k}\leq 4\left(\frac{\epsilon}{\beta
c}\right)^{1/(1-\log_{2}c)}.$

###### Proof.

We use the following claim, whose proof we provide afterward.

######  Claim D.3.4.

Let $I=[x^{-},x^{+}]$ be any sub-interval of $[0,1]$ and let
$\alpha=\inf_{x\in I}\rho(x)$. Then there is an increasing sequence of points
$z_{0}:=x^{-},z_{1},z_{2},\dots,z_{L-1},z_{L}:=x^{+}$, such that for every
$\ell\in[L]$, $\mathbb{P}[\mu_{-}\leq z_{\ell-1},\mu_{+}\geq
z_{\ell}]\geq\frac{\alpha}{2}$, and where

$L\leq\frac{2}{\alpha}\sum_{\ell\in[L]}\mathbb{P}[\mu_{-}\leq
z_{\ell-1}<\mu_{+}\leq z_{\ell}].$

We apply Claim D.3.4 to the intervals $I_{1}^{\prime},\dots,I_{N-1}^{\prime}$,
with $\alpha=\alpha_{k}$. Let $z_{k,0},\dots,z_{k,L_{k}}$ be the points whose
existence the claim proves, and let
$r_{k}:=\sum_{\ell\in[L_{k}]}\mathbb{P}[\mu_{-}\leq z_{k,\ell-1}<\mu_{+}\leq
z_{k,\ell}]$, so that $L_{k}\leq\frac{2}{\alpha_{k}}r_{k}$. Observe that
$\sum_{k}r_{k}\leq 1$, because the intervals $(z_{k,\ell-1},z_{k,\ell}]$ are
disjoint for all $k,\ell$. We make the following claim (we provide the proof
afterward).

######  Claim D.3.5.

$\sum_{k\in[N-1]}r_{k}\left(\frac{\alpha_{k}}{2r_{k}}\right)^{1-\log_{2}c}\leq\frac{\epsilon}{\beta
c}.$ (D.9)

We may rewrite Equation D.9 as

$\left(\sum_{k\in[N-1]}r_{k}\left(\frac{\alpha_{k}}{2r_{k}}\right)^{1-\log_{2}c}\right)^{1/(1-\log_{2}c)}\leq\left(\frac{\epsilon}{\beta
c}\right)^{1/(1-\log_{2}c)}.$

Recall that $\sum_{k}r_{k}\leq 1$. Scaling the $r_{k}$’s to add to $1$
decreases the left-hand side above, so we may assume that $\sum_{k}r_{k}=1$.
Note that $x^{1-\log_{2}c}$ is convex. Thus, by using a weighted Jensen
inequality on the left-hand side with weights $r_{k}$, we find that

$\frac{1}{2}\sum_{k}\alpha_{k}=\sum_{k}r_{k}\cdot\frac{\alpha_{k}}{2r_{k}}\leq\left(\sum_{k\in[N-1]}r_{k}\left(\frac{\alpha_{k}}{2r_{k}}\right)^{1-\log_{2}c}\right)^{1/(1-\log_{2}c)}\leq\left(\frac{\epsilon}{\beta
c}\right)^{1/(1-\log_{2}c)}.$

This completes the proof of Lemma D.3.3. ∎

###### Proof of Claim D.3.4.

Let $z_{1}=\inf\\{z:\mathbb{P}[\mu_{-}\leq z_{0}<\mu_{+}\leq
z]\geq\frac{\alpha}{2}\\}$, or $x^{+}$ if this number does not exist or is
larger than $x^{+}$. Note that $\mathbb{P}[\mu_{-}\leq
z_{0}<\mu_{+}]\geq\alpha$, as we have $\rho(z_{0})=\mathbb{P}[\mu_{-}\leq
z_{0}<\mu_{+}]+\mathbb{P}[\mu_{-}<z_{0}=\mu_{+}]\geq\alpha$, so if the first
term were less than $\alpha$ we would have some $z^{\prime}>z_{0}$ with
$\rho(z^{\prime})<\alpha$. On the other hand, $\mathbb{P}[\mu_{-}\leq
z_{0}<\mu_{+}<z_{1}]\leq\frac{\alpha}{2}$, since

$\mathbb{P}[\mu_{-}\leq z_{0}<\mu_{+}<z_{1}]=\lim_{z\to z_{1}\text{ from
below}}\mathbb{P}[\mu_{-}\leq z_{0}<\mu_{+}\leq z]$

and if the right-hand side were more than $\frac{\alpha}{2}$ then that would
contradict the definition of $z_{1}$ as an infimum. Therefore,
$\mathbb{P}[\mu_{-}\leq z_{0},\mu_{+}\geq z_{1}]\geq\frac{\alpha}{2}$.

If $z_{1}=x^{+}$, we are done. Otherwise, let
$z_{2}=\inf\\{z:\mathbb{P}[\mu_{-}\leq z_{1}<\mu_{+}\leq
z]\geq\frac{\alpha}{2}\\}$. Then $\mathbb{P}[\mu_{-}\leq z_{1},\mu_{+}\geq
z_{2}]\geq\frac{\alpha}{2}$. Define $z_{3}$ analogously, and so forth.

All that remains to show is the upper bound on $L$. This is where we use the
fact that (by construction) $\mathbb{P}[\mu_{-}\leq z_{\ell-1}<\mu_{+}\leq
z_{\ell}]\geq\frac{\alpha}{2}$. Summing over all $\ell$, we have

$\sum_{\ell\in[L]}\mathbb{P}[\mu_{-}\leq z_{\ell-1}<\mu_{+}\leq
z_{\ell}]\geq\frac{\alpha}{2}L,$

which (after rearranging) completes the proof. ∎

###### Proof of Claim D.3.5.

First note that by construction, $\text{JB}_{G}(I_{k}^{\prime})\geq\beta$ for
all $k$. By repeated use of the $c$-approximate triangle inequality,777We sub-
divide $I_{k}^{\prime}$ into $[z_{k,0},z_{k,L_{k}/2}]$ and
$[z_{k,L_{k}/2},z_{k,L}]$, then subdivide each of these, and so on. we find
that

$\sum_{\ell\in[L_{k}]}\text{JB}_{G}(z_{k,\ell-1},z_{k,\ell})\geq
c^{\left\lceil\log_{2}L_{k}\right\rceil}\text{JB}_{G}(I_{k}^{\prime})\geq
c^{1+\log_{2}\frac{2r_{k}}{\alpha_{k}}}\text{JB}_{G}(I_{k}^{\prime})\geq
c^{1+\log_{2}\frac{2r_{k}}{\alpha_{k}}}\beta=c\left(\frac{2r_{k}}{\alpha_{k}}\right)^{\log_{2}c}\beta.$

On the other hand, we have

$\displaystyle\epsilon$
$\displaystyle\geq\mathbb{E}\left[\text{JB}_{G}(\mu_{\sigma},\mu_{\tau})\right]=\sum_{\sigma,\tau}\mathbb{P}[\sigma,\tau]\text{JB}_{G}(\mu_{\sigma},\mu_{\tau})\geq\sum_{\sigma,\tau}\mathbb{P}[\sigma,\tau]\sum_{\begin{subarray}{c}k,\ell:\mu_{-}\leq
z_{k,\ell-1}\\\ \mu_{+}\geq
z_{k,\ell}\end{subarray}}\text{JB}_{G}(z_{k,\ell-1},z_{k,\ell})$
$\displaystyle=\sum_{k,\ell}\mathbb{P}[\mu_{-}\leq z_{k,\ell-1},\mu_{+}\geq
z_{k,\ell}]\text{JB}_{G}(z_{k,\ell-1},z_{k,\ell})\geq\sum_{k,\ell}\frac{\alpha_{k}}{2}\text{JB}_{G}(z_{k,\ell-1},z_{k,\ell}).$

Here, the third step follows by the reverse triangle inequality (Fact (ii) of
Proposition D.3.1) and the fourth step follows by rearranging the order of
summation.888The case that the space of signals is infinite is identical
except that the summation is replaced by an integral over the probability
space. Combining the last two facts gives us that

$\epsilon\geq\sum_{k}\frac{\alpha_{k}}{2}\cdot
c\left(\frac{2r_{k}}{\alpha_{k}}\right)^{\log_{2}c}\beta=\sum_{k}r_{k}\left(\frac{2r_{k}}{\alpha_{k}}\right)^{\log_{2}c-1}\beta
c,$

which rearranges to the desired identity. ∎

We are now ready to bound the second summand, i.e.
$\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]$,
where $k(\sigma)$ is the $k$ such that Alice’s estimate $\mu_{\sigma}$ lies in
$I_{k}$. For convenience we will define $k(\tau)$ for Bob by analogy as the
$k$ such that $\mu_{\tau}$ lies in $I_{k}$. By Lemma D.3.3 and the preceding
discussion, we know that

$\mathbb{P}[k(\sigma)\neq k(\tau)]\leq 4\left(\frac{\epsilon}{\beta
c}\right)^{1/(1-\log_{2}c)}.$

######  Lemma D.3.6.

Let $Q=\mathbb{P}[k(\sigma)\neq k(\tau)]$. Then

$\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]\leq
2\tilde{G}^{*}(Q).$

The key idea is that because $k(\sigma)=k(\tau)$ with probability near $1$,
learning $k(\sigma)$ is unlikely to make Bob update his estimate much.

###### Proof.

Consider any signal $\hat{\tau}\in\mathcal{T}$ and let
$p(\hat{\tau})=\mathbb{P}[\tau=\hat{\tau}]$. We have999This proof takes sums
over $\hat{\tau}\in\mathcal{T}$ and thus implicitly assumes that $\mathcal{T}$
is finite, but the proof extends to infinite $\mathcal{T}$, with sums over
$\tau$ replaced by integrals with respect to the probability measure over
$\mathcal{T}$.

$\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]=\sum_{\hat{\tau}\in\mathcal{T}}p(\hat{\tau})\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\hat{\tau}}\parallel\mu_{\hat{\tau}})\mid\tau=\hat{\tau}\right].$

Note that
$\mu_{\hat{\tau}}=\mathbb{E}\left[\mu_{S^{(k(\sigma))}\hat{\tau}}\mid\tau=\hat{\tau}\right]$,
so by Proposition D.3.1 we have that

$\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]=\sum_{\hat{\tau}\in\mathcal{T}}p(\hat{\tau})\left(\mathbb{E}\left[G(\mu_{S^{(k(\sigma))}\hat{\tau}})\mid\tau=\hat{\tau}\right]-G(\mu_{\hat{\tau}})\right).$

Let $q(\hat{\tau})=\mathbb{P}[\tau=\hat{\tau},k(\sigma)\neq k(\hat{\tau})]$,
so $\sum_{\hat{\tau}\in\mathcal{T}}q(\hat{\tau})=Q$. Then

$\displaystyle\mathbb{E}\left[G(\mu_{S^{(k(\sigma))}\hat{\tau}})\mid\tau=\hat{\tau}\right]-G(\mu_{\hat{\tau}})=$
$\displaystyle\frac{p(\hat{\tau})-q(\hat{\tau})}{p(\hat{\tau})}\left(\mathbb{E}\left[G(\mu_{S^{(k(\hat{\tau}))}\hat{\tau}})-G(\mu_{\hat{\tau}})\right]\right)+\frac{q(\hat{\tau})}{p(\hat{\tau})}\left(\mathbb{E}\left[G(\mu_{S^{(k(\sigma))}\hat{\tau}})\mid\tau=\hat{\tau},k(\sigma)\neq
k(\hat{\tau})\right]-G(\mu_{\hat{\tau}})\right).$

The second term is at most $\frac{q(\hat{\tau})}{p(\hat{\tau})}M$, since $M$
is the range of $G$. To bound the first term, we note that
$\mu_{S^{(k(\hat{\tau}))}\hat{\tau}}$ cannot differ from $\mu_{\hat{\tau}}$ by
more than $\frac{q(\hat{\tau})}{p(\hat{\tau})-q(\hat{\tau})}$, as otherwise
the average value of $\mu_{S^{(k(\sigma))}\hat{\tau}}$ could not be
$\mu_{\hat{\tau}}$. Therefore,
$\mathbb{E}\left[G(\mu_{S^{(k(\hat{\tau}))}\hat{\tau}})-G(\mu_{\hat{\tau}})\right]$
is bounded by the largest possible difference in $G$-values of two points that
differ by at most $\frac{q(\hat{\tau})}{p(\hat{\tau})-q(\hat{\tau})}$.
Therefore, we have

$\displaystyle\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]$
$\displaystyle\leq\sum_{\hat{\tau}\in\mathcal{T}}p(\hat{\tau})\left(\frac{p(\hat{\tau})-q(\hat{\tau})}{p(\hat{\tau})}\tilde{G}\left(\frac{q(\hat{\tau})}{p(\hat{\tau})-q(\hat{\tau})}\right)+\frac{q(\hat{\tau})}{p(\hat{\tau})}M\right)$
$\displaystyle\leq
QM+\sum_{\hat{\tau}\in\mathcal{T}}(p(\hat{\tau})-q(\hat{\tau}))\tilde{G}\left(\frac{q(\hat{\tau})}{p(\hat{\tau})-q(\hat{\tau})}\right),$

where $\tilde{G}$ is defined as in the statement of Lemma D.3.6. If $G$ is
symmetric on $[0,1]$, then $\tilde{G}(x)=G(0)-G(x)$ for $x\leq\frac{1}{2}$ and
$M$ otherwise. This is a concave function, but $\tilde{G}$ is not in general
concave. However, consider $\tilde{G}^{*}$ as defined in the lemma statement,
so $\tilde{G}(x)\leq\tilde{G}^{*}(x)$ for all $x$. Then

$\displaystyle\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right]$
$\displaystyle\leq
QM+\sum_{\hat{\tau}\in\mathcal{T}}(p(\hat{\tau})-q(\hat{\tau}))\tilde{G}^{*}\left(\frac{q(\hat{\tau})}{p(\hat{\tau})-q(\hat{\tau})}\right)$
$\displaystyle\leq
QM+\left(\sum_{\hat{\tau}\in\mathcal{T}}(p(\hat{\tau})-q(\hat{\tau}))\right)\cdot\tilde{G}^{*}\left(\frac{\sum_{\hat{\tau}\in\mathcal{T}}q(\hat{\tau})}{\sum_{\hat{\tau}\in\mathcal{T}}(p(\hat{\tau})-q(\hat{\tau}))}\right)$
$\displaystyle=QM+(1-Q)\tilde{G}^{*}\left(\frac{Q}{1-Q}\right)\leq
QM+\tilde{G}^{*}(Q)\leq 2\tilde{G}^{*}(Q).$

Here, the second step follows by Jensen’s inequality with terms
$\frac{q(\hat{\tau})}{p(\hat{\tau})-q(\hat{\tau})}$ and weights
$p(\hat{\tau})-q(\hat{\tau})$, the second-to-last step follows from the fact
that $\tilde{G}^{*}$ is convex and $\tilde{G}^{*}(0)=0$, and the last step
follows from the fact that $\tilde{G}^{*}$ is convex and $\tilde{G}^{*}(1)=M$.
∎

Since $Q\leq 4\left(\frac{\epsilon}{\beta c}\right)^{1/(1-\log_{2}c)}$,
combining Lemma D.3.6 with Equation D.8 gives us the following result.

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{\tau})\right]\leq\frac{8\beta}{c^{2}}+2\tilde{G}^{*}\left(4\left(\frac{\epsilon}{\beta
c}\right)^{1/(1-\log_{2}c)}\right).$

Noting that $\tilde{G}^{*}$ is concave and $c^{-1/(1-\log_{2}c)}\leq 2$ (which
is true for all $0<c<1$) completes the proof of Lemma 8.4.16. ∎

###  D.4 Alternative definitions of agreement and accuracy

For arbitrary Bregman divergences, there are several notions of agreement and
accuracy that are worth considering. Before we discuss these, we make a note
about the order of arguments in a Bregman divergence. In our context, it makes
the most sense to talk of the Bregman divergence _from a more informed
estimate to a less informed estimate_. By a “more informed estimate” we mean a
finer-grained one, i.e. one that is informed by more knowledge. For example,
in terms of estimating $Y$ in the context of this work explores, $Y$ is more
informed than $\mu_{\sigma\tau}$, which is more informed than $\mu_{\sigma}$
and $\mu_{S\tau}$, which are each more informed than $\mu_{ST}$, which is more
informed than $\mathbb{E}\left[Y\right]$.

To see that this is the natural order of the arguments, recall that Bregman
divergences are motivated by the property that they elicit the mean (see
Proposition 2.1.8): if an agent who gives an estimate of $x$ for the value of
a random variable $Y$ incurs a loss of $D_{G}(Y\parallel x)$, then the agent
minimizes their expected loss by reporting $x=\mathbb{E}\left[Y\right]$. This
means that the expert ought to report the expected value of $Y$ given the
information that the expert knows.

This means that given two estimates of $Y$, $Z_{1}$ and $Z_{2}$, of which
$Z_{1}$ is more informed, the quantity $D_{G}(Z_{1}\parallel Z_{2})$ has a
natural interpretation: it is the expected amount the expert gains by learning
more and refining their estimate from $Z_{2}$ to $Z_{1}$. This follows by the
Pythagorean theorem:

$\mathbb{E}\left[D_{G}(Z_{1}\parallel
Z_{2})\right]=\mathbb{E}\left[D_{G}(Y\parallel
Z_{2})\right]-\mathbb{E}\left[D_{G}(Y\parallel Z_{1})\right].$

####  D.4.1 Alternative definitions of agreement

One important motivation for using the Jensen-Bregman divergence to the
midpoint as the definition of agreement is that this quantity serves as a
lower bound on the expected amount that Charlie disagrees with Alice and Bob.
Formally:

######  Definition D.4.1.

Let $a$, $b$, and $c$ be Alice’s, Bob’s, and Charlie’s expectations,
respectively (these are random variables on $\Omega$). Alice and Bob
_$\epsilon$ -agree with Charlie_ if
$\frac{1}{2}(\mathbb{E}\left[D_{G}(a\parallel c)+D_{G}(b\parallel
c)\right])\leq\epsilon$.

(This is the order of arguments because Alice and Bob are more informed than
Charlie.) By Proposition D.3.1 (i), we know that if Alice and Bob
$\epsilon$-agree with Charlie then they $\epsilon$-agree.

As it happens the fact that under this (stronger) definition of agreement
implies accuracy under rectangle substitutes follows immediately:

######  Proposition D.4.2.

Let $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information
structure that satisfies rectangle substitutes. For any communication protocol
that causes Alice and Bob to $\epsilon$-agree with Charlie on $\mathcal{I}$,
Alice and Bob are $2\epsilon$-accurate after the protocol terminates.

###### Proof.

Let $S$ be the set of possible signals of Alice at the end of the protocol
which are consistent with the protocol transcript, and define $T$ likewise for
Bob. Recall that Charlie’s expectation is $\mu_{ST}$. We have

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{S\tau})\right]\leq\mathbb{E}\left[D_{G}(\mu_{\sigma
T}\parallel\mu_{ST})\right]\leq\mathbb{E}\left[D_{G}(\mu_{\sigma
T}\parallel\mu_{ST})\right]+\mathbb{E}\left[D_{G}(\mu_{S\tau}\parallel\mu_{ST})\right]\leq
2\epsilon,$

where the first inequality follows by rectangle substitutes and the last
inequality follows because Alice and Bob $\epsilon$-agree with Charlie. ∎

The drawback of Definition D.4.1 is that it is not so much a definition of
Alice and Bob’s agreement with each other, so much as a definition of
agreement with respect to the protocol being run (since Charlie only exists
within the context of the protocol). Put otherwise, it is impossible to
determine whether Alice and Bob $\epsilon$-agree with Charlie simply by
knowing Alice and Bob’s expectations; one must also know Charlie’s
expectation, which cannot be determined from Alice’s and Bob’s expectations.
The question “how far from agreement are Alice and Bob if Alice believes 25%
and Bob believes 30%?” makes sense in the context of $\epsilon$-agreement, but
not in the context of $\epsilon$-agreement with Charlie.

A different notion of agreement, which (like $\epsilon$-agreement) only
depends on Alice’s and Bob’s expectations, uses the _symmetrized Bregman
divergence_ between these expectations: $\frac{1}{2}(D_{G}(a\parallel
b)+D_{G}(b\parallel a))$.

######  Definition D.4.3.

Let $a$ and $b$ be Alice’s and Bob’s expectations, respectively (these are
random variables on $\Omega$). Alice and Bob satisfy _symmetrized
$\epsilon$-agreement_ if $\frac{1}{2}(D_{G}(a\parallel b)+D_{G}(b\parallel
a))$.

By Proposition D.3.1 (iii), we know that if Alice and Bob satisfy symmetrized
$\epsilon$-agreement then they $\epsilon$-agree.

In our context, symmetrized Bregman divergence is less natural than Jensen-
Bregman divergence. This is symmetrized Bregman divergence (unlike Jensen-
Bregman divergence) does not seem to closely relate to our previous discussion
of the Bregman divergence from a more informed to a less informed estimate
being most natural.

####  D.4.2 Alternative notions of accuracy

Our definition of Alice’s accuracy as the expected Bregman divergence from the
truth $\mu_{\sigma\tau}$ to Alice’s expectation seems like the most natural
one. However, one may desire a definition of accuracy that takes both Alice’s
and Bob’s expectations into account, judging the pair’s accuracy based on
their consensus belief, rather than each of their individual beliefs. For
instance, one could say that Alice and Bob are _$\epsilon$ -midpoint-accurate_
if
$\mathbb{E}\left[D_{G}\left(\mu_{\sigma\tau}\parallel\frac{a+b}{2}\right)\right]\leq\epsilon$.
By this definition, Alice’s and Bob’s expectations could individually be far
from the truth, but they are considered accurate because the average of their
expectations is close to correct.

######  Proposition D.4.4.

If Alice and Bob are $\epsilon$-accurate, then they are $2\epsilon$-midpoint-
accurate.

###### Proof.

Observe that for all $a,b,y$ it is the case that

$D_{G}\left(y\parallel\frac{a+b}{2}\right)\leq\max(D_{G}(y\parallel
a),D_{G}(y\parallel b)\leq D_{G}(y\parallel a)+D_{G}(y\parallel b).$

The first inequality is true simply because $\frac{a+b}{2}$ lies in between
$a$ and $b$. Therefore,

$\mathbb{E}\left[D_{G}\left(y\parallel\frac{a+b}{2}\right)\right]\leq\mathbb{E}\left[D_{G}(y\parallel
a)+D_{G}(y\parallel b)\right]\leq 2\epsilon.$

∎

Another natural choice for Alice’s and Bob’s consensus belief is the QA pool
(see [307]). Proposition D.4.4 likewise holds for the QA pool in place of the
midpoint, and indeed holds for any choice of consensus belief that is
guaranteed to lie in between Alice’s and Bob’s expectations. Thus, any such
definition will be weaker than our definition of $\epsilon$-accuracy for Alice
and Bob (up to a constant factor).

To summarize, among the above definitions of agreement, $\epsilon$-agreement
is the weakest; and among the above definitions of accuracy, Alice’s and Bob’s
$\epsilon$-accuracy is the strongest. This is an indication of strength for
Theorem 8.4.15: it starts from a relatively weak premise and reaches a
relatively strong conclusion.

###  D.5 Implications for communication complexity

Our results can be framed in a communication complexity context, where they
imply that “substitutable” functions can be computed with probability
$1-\delta$ (over the inputs) with a transcript length depending only on
$\delta$. This is a nonstandard and weak notion of computing the function, but
sketching the reduction may inspire future work on connections between
substitutes and communication complexity.

In a classic deterministic communication complexity setup (e.g. [321]), Alice
holds $\sigma\in\mathcal{S}$, Bob holds $\tau\in\mathcal{T}$, and the goal is
to compute some function $g:\mathcal{S}\times\mathcal{T}\to\\{0,1\\}$ using a
communication protocol (see Section 8.2.2). Our setting captures this model
when $Y=g(\sigma,\tau)$. Observe that in this case, $Y=\mu_{\sigma\tau}$, i.e.
Alice and Bob’s information together determine $Y$ completely. A communication
protocol defines its output by a function $h:\Pi\to\\{0,1\\}$ where $\Pi$ is
the space of transcripts. We can simply let $h(\pi)=\text{round}(\mu_{ST})$,
i.e. rounding the _ex post_ expectation
$\mathbb{E}\left[Y\mid\pi\right]=\mu_{ST}$ to either zero or one. This is
equivalent to the belief of “Charlie”, or the common knowledge of Alice and
Bob after the protocol is completed.

######  Definition D.5.1 (Rectangle substitutes, $(1-\delta)$-computes).

Given a function $g$ and a distribution $\mathcal{D}$ over
$\mathcal{S}\times\mathcal{T}$, we say $(g,\mathcal{D})$ satisfy _rectangle
substitutes_ if the corresponding information structure with
$Y=g(\sigma,\tau)$ satisfies rectangle substitutes (Definition 8.2.6). We say
a protocol $(1-\delta)$-computes $g$ over $\mathcal{D}$ if, with probability
at least $1-\delta$ over $(\sigma,\tau)\sim\mathcal{D}$, the protocol has
$h(\pi)=g(\sigma,\tau)$.

By our results, under rectangle substitutes $(g,\mathcal{D})$, any agreement
protocol approximately computes $g$ over $\mathcal{D}$. More precisely, using
a fast substitutes-agreement protocol similar to Proposition D.2.1, we obtain
the following.

######  Corollary D.5.2.

Suppose $(g,\mathcal{D})$ satisfy rectangle substitutes. Then for every
$\delta\in(0,1)$, there is a deterministic communication protocol using
$O(\log(1/\delta))$ bits of communication that $(1-\delta)$-computes $g$ over
$\mathcal{D}$.

###### Proof.

In round one, Alice sends her current expectation $\mu_{\sigma}$ rounded to a
multiple of $\epsilon$; call this message $A$. In round two, Bob sends his
updated expectation $\mu_{S\tau}$ rounded to a multiple of $\epsilon$; call
this message $B$. The protocol then halts, and the output is $B$ rounded to
either zero or one. It uses $O(\log(1/\epsilon))$ bits. Let $S,T$ be the
random rectangle associated with the protocol.

By construction, $|\mu_{\sigma}-A|\leq\epsilon$, and $\mu_{S}$ is the
expectation of $Y$ conditioned on $A$, so it follows that
$|\mu_{\sigma}-\mu_{S}|\leq\epsilon$. Using substitutes (just as in
Proposition D.2.1),

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\right]\leq\mathbb{E}\left[(\mu_{\sigma}-\mu_{S})^{2}\right]\leq\epsilon^{2}.$

By construction, $|B-\mu_{S\tau}|\leq\epsilon$. Therefore, by the
$\tfrac{1}{2}$-approximate triangle inequality for squared distance (e.g.
Proposition 8.4.10)),

$\mathbb{E}\left[(\mu_{\sigma\tau}-B)^{2}\right]~{}\leq~{}2\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\right]+2\mathbb{E}\left[(\mu_{S\tau}-B)^{2}\right]~{}\leq~{}2\epsilon^{2}.$

Now, the protocol is incorrect if $|B-\mu_{\sigma\tau}|\geq\tfrac{1}{2}$.
Using Markov’s inequality,

$\displaystyle\mathbb{P}[|B-\mu_{\sigma\tau}|\geq\tfrac{1}{2}]$
$\displaystyle=\mathbb{P}[(B-\mu_{\sigma\tau})^{2}\geq\tfrac{1}{4}]$
$\displaystyle\leq 4\mathbb{E}\left[(B-\mu_{\sigma\tau})^{2}\right]$
$\displaystyle\leq 8\epsilon^{2}.$

Therefore, given $\delta\in(0,1)$, we run the protocol with
$\epsilon=\sqrt{\delta/8}$. The probability of an incorrect output is at most
$\delta$, and we use $O(\log(1/\epsilon)=O(\log(1/\delta))$ bits of
communication. ∎