$\displaystyle=G(\mathbf{p}^{*})-\sum_{i}w_{i}G(\mathbf{p}_{i})+\sum_{i}w_{i}\left\langle\mathbf{g}(\mathbf{p}_{i}),\mathbf{p}_{i}-\mathbf{p}^{*}\right\rangle+\mu_{j}$
$\displaystyle=\sum_{i}w_{i}D_{G}(\mathbf{p}^{*}\parallel\mathbf{p}_{i})+\mu_{j}.$

The second-to-last step follows from the fact that
$\left\langle\lambda\mathbf{1}_{n},\boldsymbol{\delta}_{j}-\mathbf{p}^{*}\right\rangle=0$
and $\left\langle\boldsymbol{\mu},\mathbf{p}^{*}\right\rangle=0$, and the last
step follows by the definition of Bregman divergence. Since $\mu_{j}=0$ for
every $j$ such that $p^{*}_{j}>0$ (of which there is at least one), the
minimum of $u(\mathbf{p}^{*};j)$ over $j$ is achieved simultaneously for all
$j$ with $p^{*}_{j}>0$, and this minimum is equal to
$\sum_{i}w_{i}D_{G}(\mathbf{p}^{*}\parallel\mathbf{p}_{i})$. This quantity is
non-negative, and positive except when all $\mathbf{p}_{i}$’s with positive
weights are equal.

Finally we show that $\mathbf{x}=\mathbf{p}^{*}$ maximizes
$\min_{j}u(\mathbf{x};j)$. Suppose that for some report $\mathbf{q}$ we have
that $\min_{j}u(\mathbf{q};j)\geq\min_{j}u(\mathbf{p}^{*};j)$. Then
$u(\mathbf{q};j)\geq u(\mathbf{p}^{*};j)$ for _every_ $j$ such that
$p^{*}_{j}>0$. But this means that the expected score (according to $s$) of an
expert who believes $\mathbf{p}^{*}$ is larger if the expert reports
$\mathbf{q}$ than if the expert reports $\mathbf{p}^{*}$. This contradicts the
fact that $s$ is proper. ∎

######  Remark 5.3.2.

We can reformulate Theorem 5.3.1 as follows: suppose that an agent has access
to forecasts $\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ and needs to issue a
forecast, for which the agent will be scored using a proper scoring rule $s$.
The agent can improve upon selecting an expert at random according to weights
$w_{1},\dots,w_{m}$, no matter the outcome $j$, by reporting $\mathbf{p}^{*}$.
This improvement is the same no matter the outcome – so long as the outcome is
assigned positive probability by $\mathbf{p}^{*}$ – and is a strict
improvement unless all forecasts with positive weights are the same.

######  Remark 5.3.3.

Theorem 5.3.1 is closely related to work by [263] that establishes a
connection between entropy maximization and worst-case expected loss
minimization. Their work studies a generalized notion of entropy functions
that, for the case of a proper scoring rule $s$, is equal to the negative of
the expected score function $G$. They show that the forecast $\mathbf{x}$ that
maximizes entropy (minimizes $G$) also maximizes an expert’s worst-case score
(over outcomes $j$). Considering instead the entropy function $\left\langle
x,\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})\right\rangle-G(\mathbf{x})$ yields
results that are very similar to our Theorem 5.3.1. In particular, if
$\mathcal{D}$ is a closed set or an open set, then the max-min result in
Theorem 5.3.1 can be derived from [263, Theorem 5.2] and [263, Theorem 6.2],
respectively. However, our proof below captures cases that their results do
not address. See also [214, Lemma 1], from which (upon considering the scoring
rule with expected score function $G(\mathbf{x})-\left\langle
x,\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})\right\rangle$) yields the
simultaneity result of Theorem 5.3.1 if $\mathbf{p}^{*}$ lies in the interior
of $\Delta_{n}$.

###  5.4 Convex losses and learning expert weights

Thus far, when discussing QA pooling, we have regarded expert weights as
given. Where do these weights come from? As demonstrated by the results in
this section, if the proper scoring rule $s$ has convex exposure (see
Definition 5.2.10), these weights can be learned from experience. This
learning property for weights falls out of the following key observation,
which states that an agent’s score is a concave function of the weights it
uses for the experts.

######  Theorem 5.4.1.

Let $s$ be a proper scoring rule with convex exposure and forecast domain
$\mathcal{D}$, and fix any
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}\in\mathcal{D}$. Given a weight vector
$\mathbf{w}=(w_{1},\dots,w_{m})\in\Delta_{m}$, define the _weight-score_ of
$\mathbf{w}$ for an outcome $j$ as

$\text{WS}_{j}(\mathbf{w}):=s\left(\sideset{}{{}_{\mathbf{g}}}{\bigoplus}_{i=1}^{m}(\mathbf{p}_{i},w_{i});j\right).$

Then for every $j\in[n]$, $\text{WS}_{j}(\mathbf{w})$ a concave function of
$\mathbf{w}$.

###### Proof.

Let $\mathbf{v}$ and $\mathbf{w}$ be two weight vectors. We wish to show that
for any $c\in[0,1]$, we have

$\text{WS}_{j}(c\mathbf{v}+(1-c)\mathbf{w})-c\text{WS}_{j}(\mathbf{v})-(1-c)\text{WS}_{j}(\mathbf{w})\geq
0.$

Recall the notation $\mathbf{p}^{*}_{\mathbf{w}}$ from Definition 5.2.5. Note
that

$\mathbf{g}(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}})=\sum_{i=1}^{m}(cv_{i}+(1-c)w_{i})\mathbf{g}(\mathbf{p}_{i})=c\mathbf{g}(\mathbf{p}^{*}_{\mathbf{v}})+(1-c)\mathbf{g}(\mathbf{p}^{*}_{\mathbf{w}}).$
(5.5)

We have

$\displaystyle\quad\text{WS}_{j}(c\mathbf{v}+(1-c)\mathbf{w})-c\text{WS}_{j}(\mathbf{v})-(1-c)\text{WS}_{j}(\mathbf{w})$
$\displaystyle=s(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}};j)-cs(\mathbf{p}^{*}_{\mathbf{v}};j)-(1-c)s(\mathbf{p}^{*}_{\mathbf{w}};j)$
$\displaystyle=G(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}})+\left\langle\mathbf{g}(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}),\boldsymbol{\delta}_{j}-\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}\right\rangle$
$\displaystyle\qquad-c(G(\mathbf{p}^{*}_{\mathbf{v}})+\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{v}}),\boldsymbol{\delta}_{j}-\mathbf{p}^{*}_{\mathbf{v}}\right\rangle)-(1-c)(G(\mathbf{p}^{*}_{\mathbf{w}})+\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{w}}),\boldsymbol{\delta}_{j}-\mathbf{p}^{*}_{\mathbf{w}}\right\rangle)$
$\displaystyle=G(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}),\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}\right\rangle$
$\displaystyle\qquad-c(G(\mathbf{p}^{*}_{\mathbf{v}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{v}}),\mathbf{p}^{*}_{\mathbf{v}}\right\rangle)-(1-c)(G(\mathbf{p}^{*}_{\mathbf{w}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{w}}),\mathbf{p}^{*}_{\mathbf{w}}\right\rangle)$

Step 1 follows from the definition of WS. Step 2 follows from Equation 5.2.
Step 3 follows from Equation 5.5, and specifically that the inner product of
each side with $\boldsymbol{\delta}_{j}$ is the same (so the
$\boldsymbol{\delta}_{j}$ terms cancel out, leaving a quantity that does not
depend on $j$). Continuing where we left off:

$\displaystyle\quad\text{WS}_{j}(c\mathbf{v}+(1-c)\mathbf{w})-c\text{WS}_{j}(\mathbf{v})-(1-c)\text{WS}_{j}(\mathbf{w})$
$\displaystyle=G(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}})-c\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{v}}),\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}\right\rangle-(1-c)\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{w}}),\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}\right\rangle$
$\displaystyle\qquad-c(G(\mathbf{p}^{*}_{\mathbf{v}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{v}}),\mathbf{p}^{*}_{\mathbf{v}}\right\rangle)-(1-c)(G(\mathbf{p}^{*}_{\mathbf{w}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{w}}),\mathbf{p}^{*}_{\mathbf{w}}\right\rangle)$
$\displaystyle=c(G(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}})-G(\mathbf{p}^{*}_{\mathbf{v}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{v}}),\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}-\mathbf{p}^{*}_{\mathbf{v}}\right\rangle)$
$\displaystyle\qquad+(1-c)(G(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}})-G(\mathbf{p}^{*}_{\mathbf{w}})-\left\langle\mathbf{g}(\mathbf{p}^{*}_{\mathbf{w}}),\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}-\mathbf{p}^{*}_{\mathbf{w}}\right\rangle)$
$\displaystyle=cD_{G}(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}\parallel\mathbf{p}^{*}_{\mathbf{v}})+(1-c)D_{G}(\mathbf{p}^{*}_{c\mathbf{v}+(1-c)\mathbf{w}}\parallel\mathbf{p}^{*}_{\mathbf{w}})\geq
0.$

Step 4 again follows from Equation 5.5. Step 5 is a rearrangement of terms.
Finally, step 6 follows from the definition of Bregman divergence, and step 7
follows from the fact that Bregman divergence is always non-negative. This
completes the proof. ∎

######  Remark 5.4.2.

Theorem 5.4.1 can be stated in more generality: $s$ need not have convex
exposure; it suffices to have that for the particular
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}$, the QA pool of these forecasts exists
for every weight vector.

Beyond Theorem 5.4.1’s instrumental use for no-regret online learning of
expert weights (Theorem 5.4.5 below), the result is interesting in its own
right. For example, the following fact – loosely speaking, that QA pooling
cannot benefit from weight randomization – follows as a corollary. (Recall the
definition of $\mathbf{p}_{\mathbf{w}}^{*}$ from Definition 5.2.5.)

######  Corollary 5.4.3.

Consider a randomized algorithm $A$ with the following specifications:

  * •

Input: a proper scoring rule $s$ with convex exposure, expert forecasts
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}$.

  * •

Output: a weight vector $\mathbf{w}\in\Delta_{m}$.

For any input $s,\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ and for every $j$, we
have

$s(\mathbf{p}^{*}_{\mathbb{E}_{A}\left[\mathbf{w}\right]};j)\geq\mathbb{E}_{A}\left[s(\mathbf{p}^{*}_{\mathbf{w}};j)\right],$

where $\mathbf{p}^{*}_{\mathbf{x}}$ denotes the QA pool of
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ with weight vector $\mathbf{x}$.

######  Remark 5.4.4.

Theorem 5.4.1 would _not_ hold if the pooling operator in the definition of WS
were replaced by linear pooling or by logarithmic pooling.131313For a
counterexample to logarithmic pooling, consider $n=2$, let $s$ be the
quadratic scoring rule, $p_{1}=(0.1,0.9)$, $p_{2}=(0.5,0.5)$, $j=1$,
$\mathbf{v}=(1,0)$, $\mathbf{w}=(0,1)$, and $c=\frac{1}{2}$. For a
counterexample to linear pooling, consider $n=2$, let $s$ be given by
$G(p_{1},p_{2})=\sqrt{p_{1}^{2}+p_{2}^{2}}$ (this is known as the _spherical_
scoring rule), $p_{1}=(0,1)$, $p_{2}=(0.2,0.8)$, $j=1$, $\mathbf{v}=(1,0)$,
$\mathbf{w}=(0,1)$, and $c=\frac{1}{2}$. This is an advantage of QA pooling
over using the linear or logarithmic method irrespective of the scoring rule.

We now state the no-regret result that we have alluded to. This result is
quite strong in that it does not merely achieve low regret compared to the
best _expert_ , but in fact compared to the best possible _weighted pool of
experts_ in hindsight. This is a substantial distinction, as it is possible
for a mixture of experts to substantially outperform any individual expert.

######  Theorem 5.4.5.

Let $s$ be a bounded proper scoring rule with convex exposure and forecast
domain $\mathcal{D}$. For time steps $t=1\dots T$, an agent chooses a weight
vector $\mathbf{w}^{t}\in\Delta_{m}$. The agent then receives a score of

$s\left(\sideset{}{{}_{\mathbf{g}}}{\bigoplus}_{i=1}^{m}(\mathbf{p}_{i}^{t},w_{i}^{t});j^{t}\right),$

where $\mathbf{p}_{1}^{t},\dots,\mathbf{p}_{m}^{t}\in\mathcal{D}$ and
$j^{t}\in[n]$ are chosen adversarially. By choosing $\mathbf{w}^{t}$ according
to Algorithm 6 (online gradient descent on the experts’ weights), the agent
achieves $O(\sqrt{T})$ regret in comparison with the best weight vector in
hindsight. In particular, if $M$ is an upper bound141414This bound $M$ exists
because $s$ is bounded by assumption, and so $\mathbf{g}$ is also bounded
(this follows from Equation 5.2). on $\left\lVert\mathbf{g}\right\rVert_{2}$,
then for every $\mathbf{w}^{*}\in\Delta_{m}$ we have

$\sum_{t=1}^{T}s\left(\sideset{}{{}_{\mathbf{g}}}{\bigoplus}_{i=1}^{m}(\mathbf{p}_{i}^{t},w_{i}^{*});j^{t}\right)-s\left(\sideset{}{{}_{\mathbf{g}}}{\bigoplus}_{i=1}^{m}(\mathbf{p}_{i}^{t},w_{i}^{t});j^{t}\right)\leq
3\sqrt{m}M\sqrt{T}.$

$\mathbf{w}^{1}\leftarrow(1/m,\dots,1/m)$;

for  _$t=1$ to $T$_ do

$\eta_{t}\leftarrow\frac{1}{M\sqrt{mt}}$;

Play $\mathbf{w}^{t}$ and observe loss $L^{t}(\mathbf{w}^{t})$;

$\tilde{\mathbf{w}}^{t+1}\leftarrow\mathbf{w}^{t}-\eta_{t}\nabla
L^{t}(\mathbf{w}^{t})$;

$\mathbf{w}^{t+1}\leftarrow$ projection of $\tilde{\mathbf{w}}^{t+1}$ onto
$\Delta_{m}$;

end for

ALGORITHM 6 Online gradient descent algorithm for Theorem 5.4.5

Algorithm 6, referenced in the theorem statement, is an application of the
standard online gradient descent algorithm (see e.g. [270, Theorem 3.1]) to
our particular setting. In our context, the loss function is
$L^{t}(\mathbf{w})=-\text{WS}_{j^{t}}(\mathbf{w})$, where WS is as in Theorem
5.4.1, relative to forecasts $\mathbf{p}_{1}^{t},\dots,\mathbf{p}_{m}^{t}$. We
defer the proof of Theorem 5.4.5 to Appendix B.1. The proof amounts to
applying the standard bounds for online gradient descent, though with an extra
step: we use the bound $M$ on $\left\lVert\mathbf{g}\right\rVert$ to bound the
gradient of the loss as a function of expert weights.

###  5.5 QA pooling connects two notions of overconfidence

Overconfidence is a well-studied phenomenon in which forecasters are
systematically biased toward reporting probabilities that are too extreme. For
example, suppose that an expert assigns probabilities to a large number of
events, and that, among those events to which the expert assigns a 1%
probability, 10% end up happening. This is a sign of overconfidence: the
expert’s forecasts would be better if all of their forecasts of 1% were
systematically increased.

What, formally, is meant by overconfidence? Arguably, a definition of
overconfidence ought to depend on the proper scoring rule used to elicit or
grade the expert’s forecast. This is because – as we have already discussed –
a proper scoring rule expresses a subjective opinion about which probabilistic
distinctions are important. If an expert assigns a 0.01% probability to an
outcome that has a 1% chance of occurring, is this a larger mistake than if
the expert assigns a 40% probability to an outcome that has a 41% chance of
occurring? The logarithmic scoring rule says yes; the quadratic scoring rule
says no.151515Formally, recall that the Bregman divergence from the true
probability to the reported forecast with respect to the expected score
function $G$ measures the score that the expert loses out on due to their
inaccuracy. We have $D_{G_{\text{log}}}(1\%\parallel 0.01\%)\gg
D_{G_{\text{log}}}(41\%\parallel 40\%)$, whereas
$D_{G_{\text{quad}}}(1\%\parallel 0.01\%)\approx
D_{G_{\text{quad}}}(41\%\parallel 40\%)$.

In this section, we present two definitions of overconfidence with respect to
a proper scoring rule. The first definition is natural and well-motivated, but
(to our knowledge) has not previously appeared in the literature. The second
definition adapts a standard notion of overconfidence to respect the intuition
of the previous paragraph by making use of QA pooling. We then prove that the
two definitions are equivalent.

For both definitions, we consider the following setting: an expert forecasts
$\mathbf{p}^{1},\dots,\mathbf{p}^{N}\in\Delta_{n}$ for $N$ events. Outcomes
$j^{1},\dots,j^{N}\in[n]$ are realized. We are defining what it means for the
expert to be overconfident on this sample of $N$ events.161616We define
overconfidence with respect to a particular realization of the outcomes (as
opposed to on average over realizations) so that our definitions do not
require a prior over the probabilities of the outcomes.

The first definition uses a quite simple principle: _an overconfident expert
expects a larger score than they will receive._

######  Definition 5.5.1 (Expected score definition of overconfidence).

Suppose that an expert forecasts
$\mathbf{p}^{1},\dots,\mathbf{p}^{N}\in\Delta_{n}$, and outcomes
$j^{1},\dots,j^{N}\in[n]$ are realized. The expert is _expected-score
overconfident_ with respect to a proper scoring rule $s$ (with expected score
function $G$) if their expected score exceeds their actual score:

$\sum_{k=1}^{N}G(\mathbf{p}^{k})>\sum_{k=1}^{N}s(\mathbf{p}^{k};j^{k}).$ (5.6)

On a basic level, the intuition behind Definition 5.5.1 is straightforward: an
overconfident expert will overestimate their score. But to gain some further
intuition, recall Figure 2.1 (repeated here). It shows the score of an expert
who reports a probability of $x=40\%$, under the No outcome (the red dot on
the left) and under the Yes outcome (the red dot on the right). Suppose that,
in the setting of Definition 5.5.1, an expert reports 40% for all $N$ events.
Then the expert expects a score of $G(0.4)$ per event on average: more than
that under a No outcome (assuming $G$ is symmetric about $0.5$, as shown) and
less than that under a Yes outcome, but $G(0.4)$ on average.

If in fact 40% of the events happen, then the expert is correctly calibrated:
neither over- nor underconfident. Their total score will be $N\cdot G(0.4)$
and so the left-hand side of Equation 5.6 will equal the right-hand side. If
only 20% of the events happen, then the expert is underconfident (should have
assigned more extreme probabilities) – and indeed, the expert’s total score
will be _higher_ than the expert expects. And if more than 40% of the events
happen, then the expert is overconfident, and indeed, that is the case in
which Equation 5.6 holds.

Our second definition also uses a simple principle: _an overconfident expert
would be better off assigning less extreme probabilities._ This basic notion
has previously appeared in the literature. For example, [336] uses the
following definition: an expert is overconfident with respect to a proper
scoring rule if shrinking all of the expert’s forecasts toward the uniform
distribution by some positive constant factor will improve the expert’s score.
Formally, an expert is overconfident by this definition if there exists
$w\in(0,1)$ such that

$\sum_{k}s\left(w\mathbf{p}^{k}+(1-w)(1/n,\dots,1/n);j^{k}\right)>\sum_{k}s(\mathbf{p}^{k};j^{k}).$

Our definition is similar in spirit, but importantly different: why shrink the
expert’s report toward the uniform distribution by a constant factor? Again,
it seems that the correct form of shrinkage ought to depend $s$. Perhaps the
quadratic score treats 26% as being equally far from 2% as it is from 50% (and
so shrinking 2% halfway toward 50% would produce a result of 26%), but the log
score certainly does not: shrinking 2% halfway toward 50% “with respect to”
the log scoring rule should give something much less than 26%. And so our
definition instead uses the exposure function $\mathbf{g}$ of $s$. Much as QA
pooling averages the exposures of the experts’ forecasts, our method of
shrinking a forecast is to average its exposure with the zero vector.
Intuitively this means uniformly making the forecast “more indifferent” to the
eventual outcome.

######  Definition 5.5.2.

For a proper scoring rule $s$, we define $\text{Shrink}_{s}(\mathbf{p},w)$ to
be the forecast $\mathbf{p}^{*}$ such that $w\mathbf{g}(\mathbf{p})$ is a
subgradient of $G$ at $\mathbf{p}^{*}$, where $\mathbf{g}$ is the exposure
function of $s$.

Note that $\text{Shrink}_{s}(\mathbf{p},1)=\mathbf{p}$, i.e. $w=1$ means no
shrinkage (whereas $w=0$ means complete shrinkage).

######  Remark 5.5.3.

In the case that there exists $\mathbf{q}$ such that
$\mathbf{g}(\mathbf{q})=0$ – i.e. a forecast $\mathbf{q}$ such that the score
of $\mathbf{q}$ does not depend on the outcome – we have

$\text{Shrink}_{s}(\mathbf{p},w)=(\mathbf{p},w)\oplus(\mathbf{q},1-w).$

For this reason, we will refer to $\text{Shrink}_{s}$ as _QA shrinkage_ with
respect to $s$. Such a $\mathbf{q}$ typically exists for proper scoring rules
that are used in practice. Indeed, for any proper scoring rule that treats all
outcomes symmetrically, $\mathbf{q}$ is simply the uniform distribution
$(1/n,\dots,1/n)$. In particular, QA shrinkage with respect to the quadratic
scoring rule is equivalent to averaging with the uniform distribution. That
is, in the case of $s_{\text{quad}}$, our definition coincides with that of
[336]. On the other hand, QA shrinkage with respect to $s_{\text{log}}$ is
equivalent to taking a logarithmic pool of the forecast with the uniform
distribution.

######  Definition 5.5.4 (QA shrinkage definition of overconfidence).

Suppose that an expert forecasts
$\mathbf{p}^{1},\dots,\mathbf{p}^{N}\in\Delta_{n}$, and outcomes
$j^{1},\dots,j^{N}\in[n]$ are realized. The expert is _QA-shrinkage
overconfident_ with respect to a proper scoring rule $s$ if for some
$w\in(0,1)$, we have

$\sum_{k=1}^{N}s(\text{Shrink}_{s}(\mathbf{p}^{k},w);j^{k})>\sum_{k=1}^{N}s(\mathbf{p}^{k};j^{k}).$
(5.7)

We can now state our main theorem, which is that (under some weak assumptions
about $s$) these two definitions are the same.

######  Theorem 5.5.5.

Let $s$ be a proper scoring rule with convex exposure, for which there is a
$\mathbf{q}\in\Delta_{n}$ such that $\mathbf{g}(\mathbf{q})=\mathbf{0}$.
Suppose that an expert forecasts
$\mathbf{p}^{1},\dots,\mathbf{p}^{N}\in\Delta_{n}$, and outcomes
$j^{1},\dots,j^{N}\in[n]$ are realized. The expert is expected-score
overconfident with respect to $s$ if and only if they are QA-shrinkage
overconfident with respect to $s$.

###### Proof.

First, observe that by using the Savage representation of $s$, we may rewrite
the condition for expected-score overconfidence (Equation 5.6) as

$\sum_{k=1}^{N}\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\mathbf{p}^{k}\right\rangle<0.$

We now show that Definition 5.5.4 is equivalent. By Remark 5.5.3, we may write
$\text{Shrink}_{s}(\mathbf{p}^{k},w)=(\mathbf{p}^{k},w)\oplus(\mathbf{q},1-w)$,
where $\mathbf{q}$ is as in the theorem statement. Furthermore, because $s$
has convex exposure, Equation 5.4 tells us that
$\mathbf{g}(\text{Shrink}_{s}(\mathbf{p}^{k},w))=w\mathbf{g}(\mathbf{p}^{k})$.

We now use Theorem 5.4.1, which tells us that for all $k$, the quantity

$s\left((\mathbf{p}^{k},w)\oplus_{s}(\mathbf{q},1-w);j^{k}\right)$

is concave in $w$. This means that the left-hand side of Equation 5.7 is a
concave function (call it $f$) of $w$. On the other hand, the right-hand side
of Equation 5.7 is $f(1)$. The question of whether there exists $w\in(0,1)$
such that $f(w)>f(1)$ is therefore equivalent to the question of whether the
derivative of $f$ at $w=1$ is negative.171717Or more precisely, the left
derivative, since $f$ is only defined on $[0,1]$. To evaluate this derivative,
we note that

$\displaystyle s(\text{Shrink}_{s}(\mathbf{p}^{k},w);j^{k})$
$\displaystyle=G(\text{Shrink}_{s}(\mathbf{p}^{k},w))+\left\langle\mathbf{g}(\text{Shrink}_{s}(\mathbf{p}^{k},w)),\boldsymbol{\delta}_{j^{k}}-\text{Shrink}_{s}(\mathbf{p}^{k},w)\right\rangle$
$\displaystyle=G(\text{Shrink}_{s}(\mathbf{p}^{k},w))+w\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\text{Shrink}_{s}(\mathbf{p}^{k},w)\right\rangle.$

Therefore, we have

$\frac{\partial s(\text{Shrink}_{s}(\mathbf{p}^{k},w);j^{k})}{\partial
w}=\frac{\partial G(\text{Shrink}_{s}(\mathbf{p}^{k},w))}{\partial
w}+\frac{\partial\left(w\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\text{Shrink}_{s}(\mathbf{p}^{k},w)\right\rangle\right)}{\partial
w}.$

Considering $\text{Shrink}_{s}(\mathbf{p}^{k},w)$ as a function from $[0,1]$
to $\mathbb{R}^{n}$, let $\mathbf{J}(w)$ be its Jacobian, i.e. the vector of
partial derivatives of the $n$ coordinates with respect to $w$. Applying the
rules of differentiation, we have that

$\displaystyle\frac{\partial
s(\text{Shrink}_{s}(\mathbf{p}^{k},w);j^{k})}{\partial w}$
$\displaystyle=\left\langle\mathbf{g}(\text{Shrink}_{s}(\mathbf{p}^{k},w)),\mathbf{J}(w)\right\rangle+\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\text{Shrink}_{s}(\mathbf{p}^{k},w)\right\rangle$
$\displaystyle\quad-w\left\langle\mathbf{g}(\mathbf{p}^{k}),\mathbf{J}(w)\right\rangle.$

Now, we are specifically interested in the derivative at $w=1$. Plugging in
$w=1$, we have

$\frac{\partial s(\text{Shrink}_{s}(\mathbf{p}^{k},w);j^{k})}{\partial
w}\mid_{w=1}=\left\langle\mathbf{g}(\mathbf{p}^{k}),\mathbf{J}(1)\right\rangle+\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\mathbf{p}^{k}\right\rangle-\left\langle\mathbf{g}(\mathbf{p}^{k}),\mathbf{J}(1)\right\rangle=\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\mathbf{p}^{k}\right\rangle.$

Recalling that the expert is QA-shrinkage overconfident if and only if the
derivative of $f$ at $w=1$ is negative, this is the case if and only if

$\sum_{k=1}^{N}\left\langle\mathbf{g}(\mathbf{p}^{k}),\boldsymbol{\delta}_{j^{k}}-\mathbf{p}^{k}\right\rangle<0.$

As we have already showed, this is the case precisely when the expert is
expected-score overconfident. This completes the proof. ∎

###  5.6 Axiomatization of QA pooling

In this section, we aim to show that the class of all quasi-arithmetic pooling
operators is a natural one, by showing that these operators are precisely
those which satisfy a natural set of axioms.

[277, 301] independently considered the class of quasi-arithmetic means. Given
an interval $I\subseteq\mathbb{R}$ and a continuous, injective function
$f:I\to\mathbb{R}$, the _quasi-arithmetic mean with respect to $f$_, or _$f$
-mean_, is the function $M_{f}$ that takes as input $x_{1},\dots,x_{m}\in I$
(for any $m\geq 1$) and outputs

$M_{f}(x_{1},\dots,x_{m}):=f^{-1}\left(\frac{f(x_{1})+\dots+f(x_{m})}{m}\right).$

For example, the arithmetic mean corresponds to $f(x)=x$; the quadratic to
$f(x)=x^{2}$; the geometric to $f(x)=\log x$; and the harmonic to
$f(x)=\frac{-1}{x}$.

Kolmogorov proved that the class of quasi-arithmetic means is precisely the
class of functions $M:\bigcup_{m=1}^{\infty}I^{m}\to I$ satisfying the
following natural properties:181818Nagumo also provided a characterization,
though with slightly different properties.

  1. (1)

$M(x_{1},\dots,x_{m})$ is continuous and strictly increasing in each variable.

  2. (2)

$M$ is symmetric in its arguments.

  3. (3)

$M(x,x,\dots,x)=x$.

  4. (4)

$M(x_{1},\dots,x_{k},x_{k+1},\dots,x_{m})$ =
$M(y,\dots,y,x_{k+1},\dots,x_{m})$, where $y:=M(x_{1},\dots,x_{k})$ appears
$k$ times on the right-hand side. Informally, a subset of arguments to the
mean function can be replaced with their mean.

The four properties listed above can be viewed as an _axiomatization_ of
quasi-arithmetic means.

Our notion of quasi-arithmetic pooling is exactly that of a quasi-arithmetic
mean, except that it is more general in two ways. First, it allows for weights
to accompany the arguments to the mean. Second, we are considering quasi-
arithmetic means with respect to _vector-valued_ functions $\mathbf{g}$. In
the $n=2$ outcome case, $\mathbf{g}$ can be considered a scalar-valued
function since it is defined on a one-dimensional space (see Remark 5.2.4 for
details); but in general we cannot treat $\mathbf{g}$ as scalar-
valued.191919Another difference is that in the $n=2$ case, we are restricting
$\mathcal{D}$ to be an interval from $0$ to $1$, though this is not a
fundamental difference for the purposes of this section.

Our goal is to extend the above axiomatization of quasi-arithmetic means in
these two ways: first (in Section 5.6.1) to include weights as arguments, and
second (in Section 5.6.2) to general $n$ (while still allowing arbitrary
weights).

####  5.6.1 Generalizing to include weights as arguments

The objects that we will be studying in this section are ones of the form
$(p,w)$, where $w\geq 0$ and $p\in\mathcal{D}$. In this subsection,
$\mathcal{D}$ is a two-outcome forecast domain, whose elements we will
identify with by the probability of the first outcome (see Remark
5.2.4).202020Proper scoring rules for two outcomes can have four possible
forecast domains: $[0,1]$, $[0,1)$, $(0,1]$, and $(0,1)$. We will fix the set
$\mathcal{D}$ for the remainder of the subsection. Our results generalize to
any interval of $\mathbb{R}$ (as in Kolmogorov’s work), but we focus on
forecast domains since that is our application.

######  Definition 5.6.1.

A _weighted forecast_ is an element of $\mathcal{D}\times\mathbb{R}_{>0}$: a
probability and a positive weight. Given a weighted forecast $\Pi=(p,w)$ we
define $\text{pr}(\Pi):=p$ and $\text{wt}(\Pi):=w$.

We will thinking of the output of pooling operators as weighted forecasts.
This is a simple extension of our earlier definition of quasi-arithmetic
pooling (Definition 5.2.5), which only output a probability.

######  Definition 5.6.2 (Quasi-arithmetic pooling with arbitrary weights
($n=2$)).

Given a continuous, strictly increasing function $g:\mathcal{D}\to\mathbb{R}$,
and weighted forecasts $\Pi_{1}=(p_{1},w_{1}),\dots,\Pi_{m}=(p_{m},w_{m})$,
define the _quasi-arithmetic pool_ of $\Pi_{1},\dots,\Pi_{m}$ with respect to
$g$ as

$\sideset{}{{}_{g}}{\bigoplus}_{i=1}^{m}(p_{i},w_{i}):=\left(g^{-1}\left(\frac{\sum_{i}w_{i}g(p_{i})}{\sum_{i}w_{i}}\right),\sum_{i}w_{i}\right).$

######  Remark 5.6.3.

The equivalence of this notion to our earlier one uses the fact that all
(continuous) proper scoring rules for binary outcomes have convex exposure
(Proposition B.3.1), so the relationship between $g(p^{*})$ and $g(p)$ may be
written as in Equation 5.4.

In the case that $\sum_{i}w_{i}=1$, Definition 5.6.2 reduces to Definition
5.2.5. In general, by linearly scaling the weights in Definition 5.6.2 to add
to $1$, we recover quasi-arithmetic pooling as previously defined.

We find the following fact useful.

######  Proposition 5.6.4.

Given two continuous, strictly increasing functions $g_{1}$ and $g_{2}$,
$\oplus_{g_{1}}$ and $\oplus_{g_{2}}$ are the same if and only if
$g_{2}=ag_{1}+b$ for some $a>0$ and $b\in\mathbb{R}$.

###### Proof.

Clearly if $g_{2}=ag_{1}+b$ for some $a>0$ and $b\in\mathbb{R}$ then
$\oplus_{g_{1}}$ and $\oplus_{g_{2}}$ are the same. For the converse, suppose
that no such $a$ and $b$ exist. Let $x<y$ be such that $g_{1}$ and $g_{2}$ are
not equal (even up to positive affine transformation) on $[x,y]$. Let
$g_{2}^{\prime}$ be the positive affine transformation of $g_{2}$ that makes
it equal to $g_{1}$ at $x$ and $y$, and let $z\in(x,y)$ be such that
$g_{1}(z)\neq g_{2}^{\prime}(z)$. Let $\alpha$ be such that $g_{1}(z)=\alpha
g_{1}(x)+(1-\alpha)g_{1}(y)$. Then
$(x,\alpha)\oplus_{g_{1}}(y,1-\alpha)=(z,1)$, but
$(x,\alpha)\oplus_{g_{2}}(y,1-\alpha)\neq(z,1)$, so $\oplus_{g_{1}}$ and
$\oplus_{g_{2}}$ are different. ∎

We now define properties (i.e. axioms) of a pooling operator $\oplus$, such
that these properties are satisfied if and only if $\oplus$ is $\oplus_{g}$
for some $g$. Our axiomatization will look somewhat different from
Kolmogorov’s, in part because we choose to define $\oplus$ as a binary
operator that (if it satisfies the associativity axiom) extends to the $m$-ary
case. This is a simpler domain and will simplify notation. In Appendix B.2 we
exhibit an equivalent set of axioms that more closely resembles Kolmogorov’s.

######  Definition 5.6.5 (Axioms for pooling operators ($n=2$)).

For a pooling operator $\oplus$ on $\mathcal{D}$ (i.e. a binary operator on
weighted forecasts), 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 $p_{1},p_{2}$, the quantity212121We allow one weight to
be $0$ by defining $(p,w)\oplus(q,0)=(q,0)\oplus(p,w)=(p,w)$.
$\text{pr}((p_{1},w_{1})\oplus(p_{2},w_{2}))$ is a continuous function of
$(w_{1},w_{2})$ on $\mathbb{R}_{\geq 0}^{2}\setminus\\{(0,0)\\}$.

  5. 5.

Idempotence: For every $\Pi_{1},\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.

Monotonicity: Let $w>0$ and let $p_{1}>p_{2}\in\mathcal{D}$. Then for
$x\in(0,w)$, the quantity $\text{pr}((p_{1},x)\oplus(p_{2},w-x))$ is a
strictly increasing function of $x$.

The motivation for the weight additivity axiom is that the weight of a
weighted forecast can be thought of as the _amount of evidence_ for its
prediction. When pooling weighted forecasts, the weight of an individual
forecast can be thought of as the strength of its vote in the aggregate.

The monotonicity axiom essentially states that if one pools two forecasts with
different probabilities and a fixed total weight, then the larger the share of
the weight belonging to the larger of the two probabilities, the larger the
aggregate probability.

We now state and prove this section’s main result: these axioms describe the
class of QA pooling operators.

######  Theorem 5.6.6.

A pooling operator is a QA pooling operator (as in Definition 5.6.2) with
respect to some $g$ if and only if it satisfies the axioms in Definition
5.6.5.222222 As we mentioned, for an associative pooling operator $\oplus$,
$\Pi_{1}\oplus\Pi_{2}\dots\oplus\Pi_{m}$ is a well-specified quantity, even
without indicating parenthesization. This lets us use the notation
$\bigoplus_{i=1}^{m}\Pi_{i}$. This is why the statement of Theorem 5.6.6 makes
sense despite pooling operators not being $m$-ary by default.

We will use $\oplus$ (without a $g$ subscript) to denote an arbitrary pooling
operator that satisfies the axioms in Definition 5.6.5. Before presenting the
proof of Theorem 5.6.6, we will note a few important facts about weighted
forecasts and pooling operators. First, we find it natural to define a notion
of multiplying a weighted forecast pair by a positive constant.

######  Definition 5.6.7.

Given a weighted forecast $\Pi=(p,w)$ and $c>0$, define $c\Pi:=(p,cw)$.

Note that $m\Pi=\bigoplus_{i=1}^{m}\Pi$ for any positive integer $m$, by
idempotence; this definition is a natural extension to all $c>0$. We note the
following (quite obvious) fact.

######  Proposition 5.6.8.

For every weighted forecast $\Pi$ and $c_{1},c_{2}>0$, we have
$c_{1}(c_{2}\Pi)=(c_{1}c_{2})\Pi$.

A natural property that is not listed in Definition 5.6.5 is _scale
invariance_ , i.e. that
$\text{pr}((p_{1},w_{1})\oplus(p_{2},w_{2}))=\text{pr}((p_{1},cw_{1})\oplus(p_{2},cw_{2}))$
for any positive $c$; or, equivalently, that
$c(\Pi_{1}\oplus\Pi_{2})=c\Pi_{1}\oplus c\Pi_{2}$. This in fact follows from
the listed axioms.

######  Proposition 5.6.9 (Distributive property/scale invariance).

For every $\Pi_{1},\Pi_{2}$ and any operator $\oplus$ satisfying the axioms in
Definition 5.6.5, we have $c(\Pi_{1}\oplus\Pi_{2})=c\Pi_{1}\oplus c\Pi_{2}$.

###### Proof.

First suppose $c$ is an integer. Then

$c\Pi_{1}\oplus
c\Pi_{2}=\bigoplus_{i=1}^{c}\Pi_{1}\oplus\bigoplus_{i=1}^{c}\Pi_{2}=\bigoplus_{i=1}^{c}(\Pi_{1}\oplus\Pi_{2})=c(\Pi_{1}\oplus\Pi_{2}).$

Here, the first and last steps follow by weight additivity and idempotence.
Now suppose that $c=\frac{k}{\ell}$ is a rational number. Let
$\Pi_{1}^{\prime}=\frac{1}{\ell}\Pi_{1}$ and
$\Pi_{2}^{\prime}=\frac{1}{\ell}\Pi_{2}$. We have

$\frac{k}{\ell}(\Pi_{1}\oplus\Pi_{2})=\frac{k}{\ell}(\ell\Pi_{1}^{\prime}\oplus\ell\Pi_{2}^{\prime})=\frac{k}{\ell}\cdot\ell(\Pi_{1}^{\prime}\oplus\Pi_{2}^{\prime})=k(\Pi_{1}^{\prime}\oplus\Pi_{2}^{\prime})=k\Pi_{1}^{\prime}\oplus
k\Pi_{2}^{\prime}=\frac{k}{\ell}\Pi_{1}\oplus\frac{k}{\ell}\Pi_{2}.$

Here, the second and second-to-last steps follow from the fact that the
distributive property holds for integers.

Finally, make use of the continuity axiom to extend our proof to all positive
real numbers $c$. In particular, it suffices to show that
$\text{pr}(\Pi_{1}\oplus\Pi_{2})=\text{pr}(c\Pi_{1}\oplus c\Pi_{2})$. Let $p$
be the former quantity; note that $\text{pr}(r\Pi_{1}\oplus r\Pi_{2})=p$ for
positive rational numbers $r$. Since the rationals are dense among the reals,
it follows that for every $\epsilon>0$, we have
$\left\lvert\text{pr}(c\Pi_{1}\oplus c\Pi_{2})-p\right\rvert\leq\epsilon$.
Therefore, $\text{pr}(c\Pi_{1}\oplus c\Pi_{2})=p$. This completes the proof. ∎

Armed with these facts, we present a proof of Theorem 5.6.6.

###### Proof of Theorem 5.6.6.

We first prove that any QA pooling operator $\oplus_{g}$ satisfies the axioms
in Definition 5.6.5. Weight additivity, commutativity, and idempotence are
trivial. Associativity is also clear: given $\Pi_{1}=(p_{1},w_{1})$ and
likewise $\Pi_{2},\Pi_{3}$, we have

$\displaystyle g(\text{pr}((\Pi_{1}\oplus_{g}\Pi_{2})\oplus_{g}\Pi_{3}))$
$\displaystyle=\frac{(w_{1}+w_{2})g(\text{pr}(\Pi_{1}\oplus_{g}\Pi_{2}))+w_{3}g(p_{3})}{(w_{1}+w_{2})+w_{3}}$
$\displaystyle=\frac{(w_{1}+w_{2})\frac{w_{1}g(p_{1})+w_{2}(p_{2})}{w_{1}+w_{2}}+w_{3}g(p_{3})}{w_{1}+w_{2}+w_{3}}=\frac{w_{1}g(p_{1})+w_{2}g(p_{2})+w_{3}g(p_{3})}{w_{1}+w_{2}+w_{3}}$

and likewise for $g(\text{pr}(\Pi_{1}\oplus_{g}(\Pi_{2}\oplus_{g}\Pi_{3})))$,
so
$\text{pr}((\Pi_{1}\oplus_{g}\Pi_{2})\oplus_{g}\Pi_{3})=\text{pr}(\Pi_{1}\oplus_{g}(\Pi_{2}\oplus_{g}\Pi_{3}))$
(since $g$ is strictly increasing and therefore injective). The fact that the
weights are also the same is trivial. Continuity follows from the fact that

$\text{pr}(\Pi_{1}\oplus_{g}\Pi_{2})=g^{-1}\left(\frac{w_{1}g(p_{1})+w_{2}g(p_{2})}{w_{1}+w_{2}}\right)$

is continuous in $(w_{1},w_{2})$ (when $w_{1},w_{2}$ are not both zero). Here
we are using the fact that $g$ is _strictly_ increasing, which means that
$g^{-1}$ is continuous.

Finally, regarding the monotonicity axiom, for any fixed $w$ and $p_{1}>p_{2}$
(as in the axiom statement), we have

$g(\text{pr}((p_{1},x)\oplus_{g}(p_{2},w-x)))=\frac{xg(p_{1})+(w-x)g(p_{2})}{x+w-x}=\frac{xg(p_{1})+(w-x)g(p_{2})}{w}.$

Since $p_{1}>p_{2}$, we have $g(p_{1})>g(p_{2})$, so the right-hand side
strictly increases with $x$. Since $g^{-1}$ is also strictly increasing, it
follows that $\text{pr}((p_{1},x)\oplus_{g}(p_{2},w-x))$ strictly increases
with $x$.

The converse – that every pooling operator satisfying the axioms in Definition
5.6.5 is $\oplus_{g}$ for some $g$ – works by constructing $g$ by fixing it at
two points and constructing $g$ at all other points. Right now we show how to
do this when the forecast domain is $[0,1]$; see the proof of Theorem B.2.7
for the argument in full generality.

Let $\oplus$ be a pooling operator that satisfies our axioms. Define $g$ as
follows: let $g(0)=0$ and $g(1)=1$. For $0<p<1$, define $g(p)=w$ where
$(1,w)\oplus(0,1-w)=(p,1)$. (This $w$ exists by continuity and the
intermediate value theorem; it is unique by the “strictly” increasing
stipulation of monotonicity.) Note that $g$ is continuous and increasing by
monotonicity.232323As a matter of fact, $g$ is strictly increasing because it
is impossible for $g(p_{1})$ to equal $g(p_{2})$ for $p_{1}\neq p_{2}$, as
that would mean that $(1,g(p_{1}))\oplus(0,1-g(p_{1}))=(p_{1},1)=(p_{2},1)$.
Another way to look at this is that it comes from the fact that
$(1,w)\oplus(0,1-w)$ is continuous in $w$ by the continuity axiom. In a sense,
the _continuity_ of $g$ corresponds to the _strictness_ of increase in the
monotonicity axiom and the _strictness_ of increase of $g$ corresponds to the
_continuity_ axiom.

We wish to show that for any $\Pi_{1}=(p_{1},w_{1})$ and
$\Pi_{2}=(p_{2},w_{2})$, we have that
$\Pi_{1}\oplus\Pi_{2}=\Pi_{1}\oplus_{g}\Pi_{2}$. Clearly the weight of both
sides is $w_{1}+w_{2}$, so we wish to show that the probabilities on each side
are the same. We have242424Steps 3 and 7 uses the distributive property
(Proposition 5.6.9).

$\displaystyle\text{pr}(\Pi_{1}\oplus\Pi_{2})$
$\displaystyle=\text{pr}(w_{1}(p_{1},1)\oplus w_{2}(p_{2},1))$
$\displaystyle=\text{pr}(w_{1}((1,g(p_{1}))\oplus(0,1-g(p_{1})))\oplus
w_{2}((1,g(p_{2}))\oplus(0,1-g(p_{2}))))$
$\displaystyle=\text{pr}(w_{1}(1,g(p_{1}))\oplus w_{1}(0,1-g(p_{1}))\oplus
w_{2}(1,g(p_{2}))\oplus w_{2}(0,1-g(p_{2})))$
$\displaystyle=\text{pr}((1,w_{1}g(p_{1}))\oplus(0,w_{1}(1-g(p_{1})))\oplus(1,w_{2}g(p_{2}))\oplus(0,w_{2}(1-g(p_{2}))))$
$\displaystyle=\text{pr}((1,w_{1}g(p_{1})+w_{2}g(p_{2}))\oplus(0,w_{1}(1-g(p_{1}))+w_{2}(1-g(p_{2}))))$
$\displaystyle=\text{pr}\left(\frac{1}{w_{1}+w_{2}}((1,w_{1}g(p_{1})+w_{2}g(p_{2}))\oplus(0,w_{1}(1-g(p_{1}))+w_{2}(1-g(p_{2}))))\right)$
$\displaystyle=\text{pr}\left(\left(1,\frac{w_{1}g(p_{1})+w_{2}g(p_{2})}{w_{1}+w_{2}}\right)\oplus\left(0,\frac{w_{1}(1-g(p_{1}))+w_{2}(1-g(p_{2}))}{w_{1}+w_{2}}\right)\right),$

which by definition of $g$ is equal to the probability $p$ such that
$g(p)=\frac{g(p_{1})w_{1}+g(p_{2})w_{2}}{w_{1}+w_{2}}$. That is,
$\text{pr}(\Pi_{1}\oplus\Pi_{2})=\text{pr}(\Pi_{1}\oplus_{g}\Pi_{2})$.

Showing that $\oplus$ and $\oplus_{g}$ are equivalent for more than two
arguments is now trivial:

$\sideset{}{{}_{\mathbf{g}}}{\bigoplus}_{i=1}^{m}\Pi_{i}=\Pi_{1}\oplus_{g}\Pi_{2}\oplus_{g}\Pi_{3}\dots\oplus_{g}\Pi_{m}=\Pi_{1}\oplus\Pi_{2}\oplus_{g}\Pi_{3}\dots\oplus_{g}\Pi_{m}=\dots=\bigoplus_{i=1}^{m}\Pi_{i}.$

(Here we are implicitly using the fact that $\oplus_{g}$ is associative, as we
proved earlier.) This completes the proof. ∎

####  5.6.2 Generalizing to higher dimensions

In Appendix B.2.1, we generalize our axioms from $n=2$ outcomes to arbitrary
values of $n$. An important challenge is extending the monotonicity axiom: in
higher dimensions, what is the appropriate generalization of an increasing
function? We show that the correct notion is _cyclical monotonicity_ , which
we define and discuss. We then present our axiomatization (Definition B.2.2)
and prove that the axioms constitute a characterization of the class of QA
pooling operators (Theorem B.2.7). On a high level, the proof is not
dissimilar to that of Theorem 5.6.6, though the details are fairly different
and more technical.

In conclusion, in Definition 5.6.5 we made a list of natural properties that a
pooling operator may satisfy. Theorem 5.6.6 shows that the pooling operators
satisfying these properties are exactly the QA pooling operators. In Appendix
B.2.1, we generalize this theorem to higher dimensions, thus fully
axiomatizing QA pooling. This result gives us an additional important reason
to believe that QA pooling with respect to a proper scoring rule is a
fundamental notion.

###  5.7 Conclusions and future directions

While in this work we have focused on proper scoring rules for eliciting
probability distributions over possible outcomes, scoring rules can be used to
elicit various other properties, such as the expectation or the median of a
random variable [335, 258, 286]. The topic of _property elicitation_ studies
such scoring rules. The Savage representation of a proper scoring rule
generalizes to arbitrary linear properties [248, Theorem 11]. That is,
consider a random variable (or $n$-tuple of random variables) $X$ and a convex
function $G$ whose domain is (a superset of) the possible values of $X$. If
$\mathbf{p}$ is an expert’s forecast for $\mathbb{E}\left[X\right]$ and
$\mathbf{x}$ is the realized outcome, then the scoring rule
$s(\mathbf{p};\mathbf{x}):=G(\mathbf{p})+\left\langle\mathbf{g}(\mathbf{p}),\mathbf{x}-\mathbf{p}\right\rangle$
is proper.252525In the setting of this work, $X$ is the vector of random
variables where the $j$-th variable is $1$ if outcome $j$ happens and $0$
otherwise, and $\mathbf{x}=\boldsymbol{\delta}_{j}$ where $j$ is the outcome
that happens. Modulo a fairly straightforward generalization, all proper
scoring rules for $\mathbb{E}\left[X\right]$ take this form (see Section
2.1.3).

Our definition of QA pooling extends verbatim to the setting of eliciting
linear properties. In this more general setting, for any proper scoring rule
that has convex exposure, it remains the case
$\mathbf{g}(\mathbf{p}^{*})=\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})$; as a
consequence, Theorems 5.3.1, 5.4.1, 5.4.5, and 5.5.5 generalize.

We now discuss several promising directions for future work. First: as we
discussed in Section 2.2.3, it is natural to generalize QA pooling by dropping
the requirement that weights add to $1$. In Section 2.4, we gave a Bayesian
justification for linear pooling with arbitrary weights, and gave a different
and novel Bayesian justification for logarithmic pooling with arbitrary
weights. This raises a few questions:

  * •

Which of our results generalize if the requirement that weights add to $1$ is
dropped? Note that dropping this requirement means that the idempotence axiom
of Section 5.6 is no longer satisfied. Is there an axiomatization that
characterizes the class of all generalized QA pools?

  * •

Just as we gave Bayesian justifications for generalized linear and logarithmic
pooling, is there a Bayesian justification for generalized QA pooling with
respect to an arbitrary proper scoring rule? What does it look like?

Second: it is natural to wonder about connections to prediction markets. After
all, a prediction market is a mechanism for eliciting forecasts from multiple
experts and aggregating them! As mentioned in Section 5.1.4, QA pooling can be
interpreted in terms of cost function markets: if $\mathbf{q}_{i}$ denotes the
quantity of shares that each expert would buy in order to bring a market into
line with the expert’s beliefs, then the QA pool of the experts’ beliefs is
the probability distribution corresponding to the quantity vector
$\mathbf{q}^{*}:=\sum_{i}w_{i}\mathbf{q}_{i}$. This follows from [181, Eq.
22]; the underlying reason is the convex duality between an expected score
function $G$ and the corresponding cost function $C$. Exploring this
connection further may yield insights into forecast aggregation through market
mechanisms.

Third: some of our results may be able to be extended or generalized. In fact,
we do so in Chapter 6, where we relax the assumption made in Theorem 5.4.5
that the scoring rule is bounded. Additionally, many of our theorem statements
depend on the convex exposure property, but it is possible that some of our
definitions and theorem statements could be modified so as to not require this
assumption.

QA pooling connects forecast elicitation and aggregation in a way that seems
quite fundamental. Further research in this area may yield important insights.

## Learning weights for logarithmic pooling

_This chapter presents “No-Regret Learning with Unbounded Losses: The Case of
Logarithmic Pooling”[305]. It assumes knowledge of logarithmic pooling,
presented in Section 2.2.1. Background on proper scoring rules (Section 2.1),
as well as on information structures (Section 2.3), is useful for context but
not required. Additionally, Chapter 5 is useful for context, as this work
builds on it directly._

_Summary:_ For each of $T$ time steps, $m$ experts report probability
distributions over $n$ outcomes; we wish to learn to aggregate these forecasts
in a way that attains a no-regret guarantee. We focus on logarithmic pooling,
which is in a certain sense the optimal choice of pooling method if one is
interested in minimizing log loss (see Theorem 5.3.1). We consider the problem
of learning the best set of parameters (i.e. expert weights) in an online
adversarial setting. We assume (by necessity) that the adversarial choices of
outcomes and forecasts are consistent, in the sense that experts report
calibrated forecasts. Imposing this constraint creates a (to our knowledge)
novel semi-adversarial setting in which the adversary retains a large amount
of flexibility. In this setting, we present an algorithm based on online
mirror descent that learns expert weights in a way that attains
$O(\sqrt{T}\log T)$ expected regret as compared with the best weights in
hindsight.

###  6.1 Introduction

####  6.1.1 Learning expert weights for logarithmic pooling

In Section 2.2, we motivated logarithmic pooling as a natural method of
forecast aggregation that has compelling theoretical properties and works well
in practice. To recall, the logarithmic pool of forecasts
$\mathbf{p}^{1},\dots,\mathbf{p}^{m}\in\Delta_{n}$ with weight vector
$\mathbf{w}\in\Delta_{m}$ is defined by

$p^{*}_{j}(\mathbf{w})=c(\mathbf{w})\prod_{i=1}^{m}(p^{i}_{j})^{w_{i}},$

for all $j\in[n]$, where $c(\mathbf{w})$ is a normalizing constant (that
depends on the weights).

But where do the expert weights come from? That is, how should an aggregator
determine what weight to assign to each expert? It is common for the
aggregator to learn the correct vector of weights over time, based on the
experts’ track record [344]. Learning expert weights over time is a sequential
decision making problem: for each of $T$ time steps, experts submit forecasts
to the aggregator, and the aggregator aggregates them using logarithmic
pooling, with weights that the aggregator chooses. Then an outcome is realized
and the aggregator receives a score depending on the accuracy of the aggregate
forecast. The aggregator adjusts expert weights for the next time step,
perhaps increasing the weights of experts who did well while decreasing the
weights of experts who did poorly.

This problem falls into the well-studied and wide-reaching field of online
learning – and more specifically, online prediction with expert advice [212].
Generally, algorithms for online learning problems are assessed based on their
_regret_ relative to some baseline. In our case, the natural baseline is the
best possible weight vector in hindsight. That is, we are looking for a weight
selection algorithm whose overall performance over the $T$ time steps is
guaranteed to be almost as good as using the best weight vector
$\mathbf{w}^{*}$ in hindsight.

We previously discussed online learning of expert weights in Chapter 5. In
that chapter, we introduced _quasi-arithmetic (QA) pooling_ as a way of
aggregating forecasts with respect to a given proper scoring rule $s$.
Specifically, the QA pool with respect to a proper scoring rule $s$ is the
forecast that guarantees the largest possible expected overperformance (as
judged by the scoring rule) compared with the strategy of choosing a random
expert to trust.111More formally, the QA pool maximizes the minimum
improvement in the score (over possible outcomes). We saw that QA pooling with
respect to the quadratic scoring rule is linear pooling (averaging the
experts’ forecasts), while QA pooling with respect to the logarithmic scoring
rule is logarithmic pooling.

In Section 5.4, we gave an algorithm for online-learning expert weights for QA
pooling with respect to any bounded proper scoring rule $s$. The algorithm had
the property that, asymptotically with the number of time steps $T$, the
average score of the algorithm (according to $s$) was guaranteed to be almost
as large as the average score of an aggregator who chose the best vector of
weights in hindsight. In online learning terminology, this means that the
algorithm has _vanishing regret_ (or, synonymously, _no regret_).

However, the log scoring rule is not bounded, so the aforementioned result
does _not_ give a no-regret algorithm for learning weights for logarithmic
pooling (if regret is defined with respect to the log scoring rule). The
purpose of this chapter is to fill that gap.

_A note on terminology:_ In this chapter, we will use the _log loss_ instead
of the log score, as is standard in the learning literature. The log loss is
simply the negative of the log score: while the log score of the forecast
$\mathbf{p}$ under outcome $j$ is $\ln(p_{j})$, the log loss is $-\ln(p_{j})$.

####  6.1.2 Choosing the right benchmark

In Chapter 5, we established a connection between the log loss and logarithmic
pooling, arguing that if the log loss is used for elicitation, then it makes
sense to use logarithmic pooling for aggregation. The goal of this work is to
develop an algorithm for learning weights for logarithmic pooling in a way
that achieves vanishing regret as judged by the log loss function. Within the
field of online prediction with expert advice, this is a particularly
challenging setting. In part, this is because the losses are potentially
unbounded. However, that is not the whole story: finding weights for _linear_
pooling, by contrast, is a well-studied problem that has been solved even in
the context of log loss. On the other hand, because logarithmic pooling
behaves more as a geometric than an arithmetic mean, if some expert assigns a
very low probability to the eventual outcome (and the other experts do not)
then the logarithmic pool will also assign a low probability, incurring a
large loss. This makes the combination of logarithmic pooling with log loss
particularly difficult.

We require that our algorithm not have access to the experts’ forecasts when
choosing weights: an algorithm that chooses weights in a way that depends on
forecasts can output an essentially arbitrary function of the forecasts, and
thus may do something other than learn optimal weights for logarithmic
pooling. For example, suppose that $m=n=2$ and an aggregator wishes to subvert
our intentions and take an equally weighted _linear_ pool of the experts’
forecasts. Without knowing the experts’ forecasts, this is impossible; on the
other hand, if the aggregator knew that e.g. $\mathbf{p}_{1}=(90\%,10\%)$ and
$\mathbf{p}_{2}=(50\%,50\%)$, they could assign weights for logarithmic
pooling so as to produce the post-hoc desired result, i.e. $(70\%,30\%)$. We
wish to disallow this.

One might suggest the following setup: at each time step, the algorithm
selects weights for each expert. Subsequently, an adversary chooses each
expert’s forecast and the outcome, after which the algorithm and each expert
incur a log loss. Unfortunately – due to the unboundedness of log loss and the
behavior of logarithmic pooling – vanishing regret guarantees in this setting
are impossible.

######  Example 6.1.1.

Consider the case of $m=n=2$. Without loss of generality, suppose that the
algorithm assigns Expert 1 a weight $w\geq 0.5$ in the first time step. The
adversary chooses reports $(e^{-T},1-e^{-T})$ for Expert 1 and
$\left(\frac{1}{2},\frac{1}{2}\right)$ for Expert 2, and for Outcome 1 to
happen. The logarithmic pool of the forecasts turns out to be approximately
$(e^{-wT},1-e^{-wT})$, so the algorithm incurs a log loss of approximately
$wT\geq 0.5T$, compared to $O(1)$ loss for Expert 2. On subsequent time steps,
Expert 2 is perfect (assigns probability $1$ to the correct outcome), so the
algorithm cannot catch up.

What goes wrong in Example 6.1.1 is that the adversary has full control over
experts’ forecast _and_ the realized outcome, and is not required to couple
the two in any way. This unreasonable amount of adversarial power motivates
assuming that the experts are _calibrated_ : for example, if an expert assigns
a 10% chance to an outcome, there really is a 10% chance of that outcome
(conditional on the expert’s information).

We propose the following setting: an adversary chooses a joint probability
distribution over the experts’ beliefs and the outcome – subject to the
constraint that each expert is _calibrated._ Loosely speaking, this means that
each expert correctly assesses the probability each outcome based on the
information they have: if an expert reports $\mathbf{p}$, then each event $j$
really does have a probability $p_{j}$ of happening, based on the expert’s
information. (We formally define calibration in Section 6.3.1.) The adversary
retains full control over correlations between forecasts and outcomes, subject
to this calibration property. Subsequently, nature randomly samples each
expert’s belief and the eventual outcome from the distribution. In this
setting, we seek to prove upper bounds on the expected value of our
algorithm’s regret.

Why impose this constraint, instead of a different one? Our reasons are
twofold: theoretical and empirical. From a theoretical standpoint, the
assumption that experts are calibrated is natural because experts who form
Bayesian rational beliefs based on evidence will be calibrated, regardless of
how much or how little evidence they have. The assumption is also motivated if
we model experts as learners rather than Bayesian agents: even if a forecaster
starts out completely uninformed, they can quickly become calibrated in a
domain simply by observing the frequency of events [242].

Second, recent work has shown that modern deep neural networks are calibrated
when trained on a proper loss function such as log loss. This is true for a
variety of tasks, including image classification [298, 271] and language
modeling [274, 235, 311]; see [206] for a review of the literature. We may
wish to use an ensemble of off-the-shelf neural networks for some prediction
or classification task. If we trust these networks to be calibrated (as
suggested by recent work), then we may wish to learn to ensemble these experts
(models) in a way that has strong worst-case theoretical guarantees under the
calibration assumption.

Logarithmic pooling is particularly sensible in the context of calibrated
experts because it takes confident forecasts “more seriously” as compared with
linear pooling (simple averaging). If Expert 1 reports probability
distribution $(0.1\%,99.9\%)$ over two outcomes and Expert 2 reports
$(50\%,50\%)$, then the logarithmic pool (with equal weights) is approximately
$(3\%,97\%)$, as compared with a linear pool of roughly $(25\%,75\%)$. If
Expert 1 is calibrated (as we are assuming), then the $(0.1\%,99.9\%)$
forecast entails very strong evidence in favor of Outcome 2 over Outcome 1.
Meanwhile, Expert 2’s forecast gives no evidence either way. Thus, it is
sensible for the aggregate to point to Outcome 2 over Outcome 1 with a fair
amount of confidence.

As another example, suppose that Expert 1 reports $(0.04\%,49.98\%,49.98\%)$
and Expert 2 reports $(49.98\%,0.04\%,49.98\%)$ (a natural interpretation:
Expert 1 found strong evidence against Outcome 1 and Expert 2 found strong
evidence against Outcome 2). If both experts are calibrated, a sensible
aggregate should arguably assign nearly all probability to Outcome 3.
Logarithmic pooling returns roughly $(2.7\%,2.7\%,94.6\%)$, which (unlike
linear pooling) accomplishes this.

Since we are allowing our algorithm to learn the optimal logarithmic pool,
perhaps there is hope to compete not just with the best expert in hindsight,
but the optimally weighted logarithmic pool of experts in hindsight. We will
aim to compete with this stronger benchmark.

This work demonstrates that the “calibrated experts” condition allows us to
prove regret bounds when no such bounds are possible for an unrestricted
adversary. While that is our primary motivation, the relaxation may also be of
independent interest. For example, even in settings where vanishing regret is
attainable in the presence of an unrestricted adversary, even stronger regret
bounds might be achievable if calibration is assumed.

####  6.1.3 Our main result

Is vanishing regret possible in our setting? Our main result is that the
answer is yes. We exhibit an algorithm that attains expected regret that
scales as $O(\sqrt{T}\log T)$ with the number of time steps $T$. Our algorithm
uses online mirror descent (OMD) with the _Tsallis entropy regularizer_
$R(\mathbf{w})=\frac{-1}{\alpha}(w_{1}^{\alpha}+\dots+w_{m}^{\alpha})$ and
step size $\eta\approx\frac{1}{\sqrt{T}\ln T}$, where any choice of
$\alpha\in(0,1/2)$ attains the regret bound.

Our proof has two key ideas. One is to use the calibration property to show
that the gradient of loss with respect to the weight vector is likely to be
small (Section 6.4.4). This is how we leverage the calibration property to
turn an intractable setting into one where – despite the unboundedness of log
loss and the behavior of logarithmic pooling – there is hope for vanishing
regret.

The other key idea (Section 6.4.3) involves keeping track of a function that,
roughly speaking, reflects how much “regret potential” the algorithm has. We
show that if the aforementioned gradient updates are indeed small, then this
potential function decreases in value at each time step. This allows us to
upper bound the algorithm’s regret by the initial value of the potential
function.

This potential argument is an important component of the proof. A naïve
analysis might seek to use our bounds on the gradient steps to myopically
bound the contribution to regret at each time step. Such an analysis, however,
does not achieve our $O(\sqrt{T}\log T)$ regret bound. In particular, an
adversary can force a large accumulation of regret if some experts’ weights
are very small (specifically by making the experts with small weights more
informed than those with large weights) – but by doing so, the small weights
increase and the adversary “spends down” its potential. Tracking this
potential allows us to take this nuance into consideration, improving our
bound.

We extend our main result by showing that the result holds even if experts are
only approximately calibrated: so long as no expert understates the
probability of an outcome by more than a constant factor, we still attain the
same regret bound (see Corollary 6.4.11). We also show in Section 6.5 that no
OMD algorithm with a constant step size can attain expected regret better than
$\Omega(\sqrt{T})$.

###  6.2 Related work

In the subfield of _prediction with expert advice,_ for $T$ time steps,
experts report “predictions” from a decision space $\mathcal{D}$ (often, as in
our case, the space of probability distributions over a set of outcomes). A
forecaster must then output their own prediction from $\mathcal{D}$. Then,
predictions are assessed according to a loss function. See [212] for an survey
of this field.

We are particularly interested in _mixture forecasters_ : forecasters who,
instead of choosing an expert to trust at each time step, aggregate the
expert’ reports. Linear mixtures, i.e. convex combinations of predictions,
have been especially well-studied, generally with the goal of learning weights
for the convex combination to compete with the best weights in hindsight.
Standard convex optimization algorithms achieve $O(\sqrt{T})$ regret for
bounded, convex losses, but it is sometimes possible to do better. For
example, if the loss function is bounded and exp-concave, then logarithmic
regret in $T$ is attainable [212, §3.3].

Portfolio theory studies optimal stock selection for maximizing return on
investment, often in a no-regret setting. [232] introduced the “universal
portfolio” algorithm, which, for each of $T$ time steps, selects a portfolio
(convex combination of stocks). Our setting translates naturally to Cover’s:
experts play the role of stocks, and the return of a stock corresponds to the
probability that and expert assigns to the eventual outcome. The universal
portfolio algorithm achieves logarithmic regret compared with the best
portfolio in hindsight [233]; in our terms, this means that logarithmic regret
(for log loss) is attainable for the linear pooling of experts. See [290] for
a survey of this area.

To our knowledge, learning weights for _logarithmic_ pooling has not been
previously studied. As shown in Example 6.1.1, it is not possible to achieve
vanishing regret if the setting is fully adversarial. We relax our setting by
insisting that the experts be calibrated (see Section 6.3.1). To our
knowledge, online prediction with expert advice has also not previously been
studied under this condition.

The calibration condition can be equivalently restated as follows: the
experts’ forecasts are based on signals drawn from an information structure –
possibly a different one at each time step – that is unknown to the
aggregator, and experts report accurate probabilities conditional on their
signals (see Remark 6.3.2). [195] investigated online prediction with expert
advice under the assumption that the experts’ signals are drawn from a
particular type of information structure, which they called the “partial
evidence environment.”222Essentially, the partial evidence environment is an
adaptation of the partial information framework (see Section 2.3) to the case
of binary outcomes. There is a set of signals, which are independent
conditional on the outcome, and every expert knows a subset of the signals
(the same subset on each time step). Further, the authors assume that
knowledge of the information structure would allow a perfect aggregator to
infer all relevant information about the experts’ signals from their
forecasts. Under the paper’s assumptions, the Bayesian optimal aggregate is a
generalized logarithmic pool (as introduced in Section 2.2.3), and the authors
show that an aggregator can often learn this optimal aggregate with vanishing
regret. By contrast, we do not make any assumptions about the information
structures, and instead aim to compete not with the optimal aggregate but with
the best weighted mixture of experts in hindsight.

###  6.3 Preliminaries

####  6.3.1 Calibration property

We define calibration as follows. Note that the definition is in the context
of our setting, i.e. $m$ experts reporting probability distributions
$\mathbf{p}^{1},\dots,\mathbf{p}^{m}$ over $n$ outcomes. We will use $J$ to
denote the random variable corresponding to the outcome, i.e. $J$ takes values
in $[n]$.

######  Definition 6.3.1.

Consider a joint probability distribution $\mathbb{P}$ over experts’ reports
and the outcome. We say that expert $i$ is _calibrated_ if for all
$\mathbf{p}\in\Delta_{n}$ and $j\in[n]$, we have that

$\text{Pr}\left[J=j\mid\mathbf{p}^{i}=\mathbf{p}\right]=p_{j}.$

That is, expert $i$ is calibrated if the probability distribution of $J$
conditional on their report $\mathbf{p}^{i}$ is precisely $\mathbf{p}^{i}$. We
say that $\mathbb{P}$ satisfies the _calibration property_ if every expert is
calibrated.

The key intuition behind the usefulness of calibration is that if an expert
claims that an outcome is very unlikely, this is strong evidence that the
outcome is in fact unlikely. In Section 6.4.4 we will use the calibration
property to show that the gradient of the loss with respect to the weight
vector is likely to be relatively small at each time step.

####  6.3.2 Our online learning setting

The setting for our online learning problem is as follows. For each time step
$t\in[T]$:

  1. (1)

Our algorithm reports a weight vector $\mathbf{w}^{t}\in\Delta_{m}$.

  2. (2)

An adversary (with knowledge of $\mathbf{w}^{t}$) constructs a probability
distribution $\mathbb{P}$, over reports and the outcome, that satisfies the
calibration property.

  3. (3)

Reports $\mathbf{p}^{t,1},\dots,\mathbf{p}^{t,m}$ and an outcome $j^{t}$ are
sampled from $\mathbb{P}$.

  4. (4)

The _loss_ of a weight vector $\mathbf{w}$ is defined as
$L^{t}(\mathbf{w}):=-\ln(p^{*}_{j^{t}}(\mathbf{w}))$, the log loss of the
logarithmic pool of $\mathbf{p}^{t,1},\dots,\mathbf{p}^{t,m}$ with weights
$\mathbf{w}$. Our algorithm incurs loss $L^{t}(\mathbf{w}^{t})$.

######  Remark 6.3.2.

An equivalent, more mechanistic definition of calibration views $\mathbb{P}$
instead as a joint probability distribution over signals received by each
expert and the outcome, i.e. as an information structure (see Section 2.3).
Each expert’s probability distribution is then the actual probability
distribution over the outcome conditioned on their signal. We can reinterpret
our online learning setting in light of this view. Specifically, instead of
directly selecting a distribution over the experts’ forecasts and the outcome,
the adversary selects an information structure describing the probability
distribution over the outcome and each expert’s signal. The signals and
outcome are then drawn at random from the information structure, and each
expert’s report is the true probability distribution over the outcome
conditioned on their signal.

Formally, the adversary selects an information structure
$\mathcal{I}_{t}=(\Omega^{t},\mathbb{P}^{t},(\sigma_{1}^{t},\dots,\sigma_{m}^{t}),Y^{t})$,
where $Y^{t}$ is a random variables taking on one of $n$ possible values,
namely the standard basis vectors in $\mathbb{R}^{n}$. Then, nature randomly
samples $\omega^{t}$ according to $\mathbb{P}^{t}$. The outcome $j^{t}$ is the
coordinate in which $Y^{t}(\omega^{t})$ has a $1$, and each expert $i$’s
report $\mathbf{p}^{t,i}$ is
$\mathbb{E}\left[Y^{t}\mid\sigma_{i}^{t}(\omega^{t})\right]$.

We define the _regret_ of our algorithm as

$\text{Regret}=\sum_{t=1}^{T}L^{t}(\mathbf{w}^{t})-\min_{\mathbf{w}\in\Delta_{m}}\sum_{t=1}^{T}L^{t}(\mathbf{w}).$

That is, the benchmark for regret is the best weight vector in hindsight.
Since our setting involves randomness, our goal is to provide an algorithm
with vanishing _expected_ regret against any adversarial strategy, where the
expectation is taken over the sampling in Step (3).

Even subject to the calibration property, the adversary has a large amount of
flexibility, because the adversary retains control over the correlation
between different experts’ forecasts. An unrestricted adversary has
exponentially many degrees of freedom (as a function of the number of
experts), whereas the calibration property imposes a mere linear number of
constraints.333This follows from the perspective of the adversary choosing an
information structure from which experts’ signals are drawn. The information
structure specifies the probability of every possible combination of signals
received by the experts, and thus has dimension that is exponential in the
number of experts. The calibration property imposes linearly many constraints
on this space.

####  6.3.3 Our algorithm

We use Algorithm 3 to accomplish this goal. The algorithm is online mirror
descent (OMD) on the weight vector. Fix any $\alpha\in(0,1/2)$. We use the
regularizer

$R(\mathbf{w}):=\frac{-1}{\alpha}(w_{1}^{\alpha}+\dots+w_{m}^{\alpha}).$

This is known as the Tsallis entropy regularizer; see e.g. [358] for previous
use in the online learning literature. We obtain the same result (up to a
multiplicative factor that depends on $\alpha$) regardless of the choice of
$\alpha$. Because no choice of $\alpha$ stands out, we prove our result for
all $\alpha\in(0,1/2)$ simultaneously.

We will generally use a step size $\eta=\frac{1}{\sqrt{T}\ln
T}\cdot\frac{1}{12m^{(1+\alpha)/2}n}$. However, in the (unlikely, as we show)
event that some expert’s weight becomes unusually small, we will reduce the
step size.

$R(\mathbf{w}):=\frac{-1}{\alpha}(w_{1}^{\alpha}+\dots+w_{m}^{\alpha})$ ;

// Any $\alpha\in(0,1/2)$ will work

$\eta\leftarrow\frac{1}{\sqrt{T}\ln T}\cdot\frac{1}{12m^{(1+\alpha)/2}n}$;

$\mathbf{w}^{1}\leftarrow(1/m,\dots,1/m)$;

for  _$t=1$ to $T$_ do

if  _$\eta\leq\min_{i}((w_{i}^{t})^{\alpha})$_ then

$\eta_{t}\leftarrow\min(\eta_{t-1},\eta)$;

else

$\eta_{t}\leftarrow\min(\eta_{t-1},\min_{i}w_{i}^{t})$ ;

// Edge case; happens with low probability

end if

Observe loss function $L^{t}$ ;

// $L^{t}$ is chosen as described in Section 6.3.2

Define $\mathbf{w}^{t+1}$ such that $\nabla R(\mathbf{w}^{t+1})=\nabla
R(\mathbf{w}^{t})-\eta_{t}\nabla L^{t}(\mathbf{w}^{t})$;

end for

ALGORITHM 3 OMD algorithm for learning weights for logarithmic pooling

In Appendix C, we prove that Algorithm 3 is efficient, taking $O(mn)$ time per
time step.

Theorem 6.3.3 formally states our no-regret guarantee.

######  Theorem 6.3.3.

For any adversarial strategy, the expected regret444The given asymptotics
assume that $T\gg m,n$, i.e. ignore terms that are lower-order in $T$. of
Algorithm 3 is at most

$O\left(m^{(3-\alpha)/2}n\sqrt{T}\log T\right).$

###  6.4 Proof of no-regret guarantee

In this section, we prove Theorem 6.3.3.

####  6.4.1 Outline of proof

We use the following fact, which follows from the fact that the score of a QA
pool of forecasts is concave in the forecasts’ weights (see Chapter 5).

######  Proposition 6.4.1 (Follows from Theorem 5.4.1).

Let $\mathbf{p}^{1},\dots,\mathbf{p}^{m}$ be forecasts over $n$ outcomes,
$j\in[n]$ be an outcome, and $\mathbf{w}\in\Delta_{m}$ be a weight vector. Let
$\mathbf{p}^{*}(\mathbf{w})$ be the logarithmic pool of the forecasts with
weight vector $\mathbf{w}$ and let
$L(\mathbf{w}):=-\ln(p_{j}^{*}(\mathbf{w}))$ be the log loss of
$\mathbf{p}^{*}(\mathbf{w})$ if Outcome $j$ is realized. Then $L$ is a convex
function.

In particular, all of our loss functions $L^{t}$ are convex, which means that
standard regret bounds apply. In particular, to bound the expected regret of
Algorithm 3, we will use a well-known regret bound for follow the regularized
leader (FTRL) with linearized losses [270, Lemma 5.3], which in our case is
equivalent to OMD.555This equivalence is due to our choice of regularizer, as
we never need to project $\mathbf{w}^{t}$.

######  Lemma 6.4.2 (Follows from [270, Lemma 5.3]).

If $\eta_{t}=\eta$ for all $t$, the regret of Algorithm 3 is at most

$\frac{1}{\eta}\left(\max_{\mathbf{w}\in\Delta_{m}}R(\mathbf{w})-\min_{\mathbf{w}\in\Delta_{m}}R(\mathbf{w})\right)+\sum_{t=1}^{T}\left\langle\nabla
L^{t}(\mathbf{w}^{t}),\mathbf{w}^{t}-\mathbf{w}^{t+1}\right\rangle.$

Informally, this bound means that if the vectors $\nabla
L^{t}(\mathbf{w}^{t})$ are small in magnitude, our regret is also small.
Conversely, if some $\nabla L^{t}(\mathbf{w}^{t})$ is large, this may be bad
for our regret bound. We expect the gradient of the loss to be large if some
expert is very wrong (assigns a very low probability to the correct outcome),
since the loss would then be steeply increasing as a function of that expert’s
weight. Fortunately, the calibration property guarantees this to be unlikely.
Specifically, we define the _small gradient assumption_ as follows.

######  Definition 6.4.3.

Define $\gamma:=12n\ln T$. The _small gradient assumption_ holds for a
particular run of Algorithm 3 if for every $t\in[T]$ and $i\in[m]$, we have

$-\frac{\gamma}{w_{i}^{t}}\leq\partial_{i}L^{t}(\mathbf{w}^{t})\leq\gamma,$

where $\partial_{i}$ denotes the partial derivative with respect to the $i$-th
weight.666See Equation C.2 for an expression of this quantity in terms of the
experts’ reports and weights.

In Section 6.4.4, we prove that the small gradient assumption is very likely
to hold. This is a key conceptual step in our proof, as it is where we
leverage the calibration property to prove bounds that ultimately let us bound
our algorithm’s regret. We then use the low likelihood of the small gradient
assumption failing in order to bound the contribution to the expected regret
from the case where the assumption fails to hold.

In Sections 6.4.2 and 6.4.3, we bound regret under the condition that the
small gradient assumption holds. We show that under the assumption, for all
$i,t$ we have $(w_{i}^{t})^{\alpha}\geq\eta$. Consequently,
$\eta=\frac{1}{\sqrt{T}\ln T}\cdot\frac{1}{12m^{(1+\alpha)/2}n}$ at all time
steps, so we can apply Lemma 6.4.2. The first term in the bound is
$O(1/\eta)=O(\sqrt{T}\log T)$. As for the summation term, we upper bound it by
keeping track of the following quantity:

$\varphi(t):=\sum_{s=1}^{t}\left\langle\nabla
L^{s}(\mathbf{w}^{s}),\mathbf{w}^{s}-\mathbf{w}^{s+1}\right\rangle+19m^{2}\gamma^{2}\eta(T-t)-4\gamma\sum_{i=1}^{m}\ln
w_{i}^{t+1}.$

The first term is exactly the summation in Lemma 6.4.2 up through step $t$.
The $19m^{2}\gamma^{2}\eta$ is something akin to an upper bound on the value
of $\left\langle\nabla
L^{t}(\mathbf{w}^{t}),\mathbf{w}^{t}-\mathbf{w}^{t+1}\right\rangle$ at a given
time step (times $T-t$ remaining time steps). This upper bound is not strict:
in particular, large summands are possible when some weights are small
(because of the fact that the lower bound in the small gradient assumption is
inversely proportional to $w_{i}^{t}$). However, attaining a large summand
requires these small weights to increase, thus “spending potential” for future
large summands. The last term keeps track of this potential.

We show that under the small gradient assumption, $\varphi(t)$ necessarily
decreases with $t$. This argument, which we give in Section 6.4.3, is another
key conceptual step, and is arguably the heart of the proof. Since
$\varphi(T)$ is equal to the summation term in Lemma 6.4.2 (plus a positive
number), and $\varphi(0)\geq\varphi(T)$, the summation term is less than or
equal to $\varphi(0)$, which is at most $O(m^{(3-\alpha)/2}\sqrt{T}\log T)$.
This completes the proof.

####  6.4.2 Bounds on $\mathbf{w}^{t}$ under the small gradient assumption

In this section, we state bounds on expert weights and how quickly they change
from one time step to the next, conditional on the small gradient assumption.
We use the following lemma, whose proof we defer to Appendix C.

######  Lemma 6.4.4.

Consider a particular run of Algorithm 3. Let $\zeta$ be a constant such that
$-\frac{\zeta}{w_{i}^{t}}\leq\partial_{i}L^{t}(\mathbf{w}^{t})\leq\zeta$ for
all $i,t$. Then for every $i,t$, we have

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

Furthermore, if $\eta_{t}\zeta\leq(1-\alpha)^{2}(w_{i}^{t})^{\alpha}$ for all
$i$, then for every $i$ we have

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

Intuitively, this result states that when the gradient update is small,
$w_{i}^{t+1}$ is not too different from $w_{i}^{t}$. Note that the lower bound
$-\frac{\zeta}{w_{i}^{t}}$ that we place on the gradient is not a simple
Lipschitz bound but instead depends on $w_{i}^{t}$; this makes the bounds in
Lemma 6.4.4 less straightforward to prove. In particular, we bound each
component $w_{i}^{t}$ individually, using bounds on the gradient of the loss
for all other components and convexity arguments.

Lemma 6.4.4 can be translated into bounds on each $w_{i}^{t}$ and on the
change between $w_{i}^{t}$ and $w_{i}^{t+1}$:

######  Corollary 6.4.5.

Under the small gradient assumption, for sufficiently large $T$ we have for
all $i\in[m],t\in[T]$ that:

  1. (#1)

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

  2. (#2)

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

We defer the proof of Corollary 6.4.5 to Appendix C. The key idea for (#1) is
to proceed by induction on $t$ on the two sub-statements in parallel: so long
as $(w_{i}^{t})^{\alpha}\geq 4\eta\gamma$, we may use the second part of Lemma
6.4.4 with $\zeta=\gamma$ to bound $(w_{i}^{t+1})^{\alpha-1}$ in terms of
$(w_{i}^{t})^{\alpha-1}$, which we can leverage to prove both sub-statements
for $t+1$. (#2) then follows from (#1) by routine (though nontrivial) algebra.

Armed with the bounds of Corollary 6.4.5, we are now able to show that under
the small gradient assumption, Algorithm 3 attains vanishing regret.

####  6.4.3 Bounding regret under the small gradient assumption

Assume the small gradient assumption. Note that since $4\gamma\geq 1$, by
Corollary 6.4.5 (#1) we have that $\eta_{t}=\eta$ for all $t$. This means that
we may apply the bound in Lemma 6.4.2, and in particular we have

$\frac{1}{\eta}\left(\max_{\mathbf{w}\in\Delta_{m}}R(\mathbf{w})-\min_{\mathbf{w}\in\Delta_{m}}R(\mathbf{w})\right)=\frac{1}{\eta}\cdot\frac{m}{\alpha}\left(\frac{1}{m}\right)^{\alpha}=\frac{m^{1-\alpha}}{\alpha\eta}=\frac{12}{\alpha}m^{(3-\alpha)/2}n\sqrt{T}\ln
T.$

It remains to bound the summation component of the regret bound in Lemma
6.4.2. To do so, we prove the following lemma, which we alluded to in Section
6.4.1 as the heart of the proof of Theorem 6.3.3.

######  Lemma 6.4.6.

For $t\in\\{0,1,\dots,T\\}$, let

$\varphi(t):=\sum_{s=1}^{t}\left\langle\nabla
L^{s}(\mathbf{w}^{s}),\mathbf{w}^{s}-\mathbf{w}^{s+1}\right\rangle+19m^{2}\gamma^{2}\eta(T-t)-4\gamma\sum_{i=1}^{m}\ln
w_{i}^{t+1}.$

Under the small gradient assumption, for sufficiently large $T$, $\varphi(t)$
is a decreasing function of $t$.

To prove this claim, consider a particular $t\in[T]$. We may write

$\varphi(t)-\varphi(t-1)=\sum_{i=1}^{m}\left((w_{i}^{t}-w_{i}^{t+1})\partial_{i}L^{t}(\mathbf{w}^{t})-19m\gamma^{2}\eta+4\gamma(\ln
w_{i}^{t}-\ln w_{i}^{t+1})\right)$ (6.1)

and we wish to show that this quantity is negative. In fact, we show that the
contribution from every $i\in[m]$ is negative. The key idea is to consider two
cases: $w_{i}^{t+1}\leq w_{i}^{t}$ and $w_{i}^{t+1}\geq w_{i}^{t}$. In each
case, Corollary 6.4.5 provides an upper bound on the magnitude of the
difference between $w_{i}^{t}$ and $w_{i}^{t+1}$. If $w_{i}^{t+1}\leq
w_{i}^{t}$ then the first and third terms in the summation are positive but
small, and are dominated by the middle term. If $w_{i}^{t+1}\geq w_{i}^{t}$
then the first term may be quite large, because of the asymmetric bound in the
small gradient assumption (and the consequently asymmetric bound in Corollary
6.4.5). However, in this case the contribution of the third term is very
negative, enough to make the overall expression negative. In this sense, the
third term keeps track of unspent potential for future regret, which gets
“spent down” whenever a large amount of regret is realized (as measured by the
first term).

We now prove formally that each term of the summation in Equation 6.1 is
negative.

###### Proof.

First assume that $w_{i}^{t}-w_{i}^{t+1}\leq 0$. Note that by combining (#1)
and (#2) of Corollary 6.4.5, we have

$w_{i}^{t+1}-w_{i}^{t}\leq 32(w_{i}^{t})^{1-\alpha}\eta\gamma\leq 8w_{i}^{t}.$

By the small gradient assumption we have that

$(w_{i}^{t}-w_{i}^{t+1})\partial_{i}L^{t}(\mathbf{w}^{t})\leq\frac{\gamma(w_{i}^{t+1}-w_{i}^{t})}{w_{i}^{t}}.$

On the other hand, we have

$4\gamma(\ln w_{i}^{t}-\ln
w_{i}^{t+1})=-4\gamma\ln\left(1+\frac{w_{i}^{t+1}-w_{i}^{t}}{w_{i}^{t}}\right)\leq\frac{-\gamma(w_{i}^{t+1}-w_{i}^{t})}{w_{i}^{t}}$

for $T$ large enough. (Here we use that $w_{i}^{t+1}-w_{i}^{t}\leq 8w_{i}^{t}$
and that $\ln(1+x)\geq\frac{x}{4}$ for $x\leq 8$.) Thus, the first and third
terms in Equation 6.1 are net negative; meanwhile, the second term is also
negative, so the expression is negative.

Now assume that $w_{i}^{t}-w_{i}^{t+1}\geq 0$. Again by the small gradient
assumption, we have that

$(w_{i}^{t}-w_{i}^{t+1})\partial_{i}L^{t}(\mathbf{w}^{t})\leq\gamma(w_{i}^{t}-w_{i}^{t+1})\leq
2(m+1)\eta\gamma^{2}(w_{i}^{t})^{2-\alpha}\leq 3m\eta\gamma^{2}$

and

$\displaystyle 4\gamma(\ln w_{i}^{t}-\ln w_{i}^{t+1})$
$\displaystyle=-4\gamma\ln\left(1-\frac{w_{i}^{t}-w_{i}^{t+1}}{w_{i}^{t}}\right)\leq-4\gamma\ln(1-2(m+1)\eta\gamma(w_{i}^{t})^{1-\alpha})$
$\displaystyle\leq-4\gamma\ln(1-2(m+1)\eta\gamma)\leq-4\gamma\ln(1-3m\eta\gamma)\leq
16m\eta\gamma^{2}$

for $T$ sufficiently large, where in the last step we use that
$\ln(1-x)\geq-\frac{4}{3}x$ for $x>0$ sufficiently small (and we have
$\lim_{T\to\infty}3m\eta\gamma=0$). Since $16+3\leq 19$, the right-hand side
of Equation 6.1 is negative. This concludes the proof. ∎

######  Corollary 6.4.7.

For sufficiently large $T$, under the small gradient assumption, the regret of
Algorithm 3 is at most
$\left(240+\frac{12}{\alpha}\right)m^{(3-\alpha)/2}n\sqrt{T}\ln T$.

###### Proof.

We have already bounded the first term in the regret bound in Lemma 6.4.2. It
remains only to bound the second term. This term is exactly equal to
$\varphi(T)+4\gamma\sum_{i=1}^{m}\ln w_{i}^{T+1}\leq\varphi(T)$, and
$\varphi(T)\leq\varphi(0)$, by Lemma 6.4.6. We have

$\varphi(0)=19m^{2}\gamma^{2}\eta T+4m\gamma\ln m\leq 20m^{2}\gamma^{2}\eta T$

for sufficiently large $T$. Plugging in $\gamma=12n\ln T$ and
$\eta=\frac{1}{\sqrt{T}\ln T}\cdot\frac{1}{12m^{(1+\alpha)/2}n}$ concludes the
proof. ∎

####  6.4.4 The case where the small gradient assumption fails

It remains to consider the case in which the small gradient assumption does
not hold. This part of the proof consists primarily of technical lemmas, which
we defer to Appendix C. The key lemma is a bound on the probability that the
small gradient assumption fails by a given margin:

######  Lemma 6.4.8.

For any weight vector $\mathbf{w}$, $i\in[m]$, and $\zeta\geq 0$, we have that

$\text{Pr}\left[\partial_{i}L(\mathbf{w})\geq\zeta\right]\leq ne^{-\zeta}$
(6.2)

and

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

Note that plugging in $\zeta=\gamma$ yields a bound of
$mT(ne^{-\gamma}+mn^{2}e^{-\gamma/n})$ on the probability that the small
gradient assumption fails to hold. (Since $\gamma=12n\ln T$, this quantity is
on the order of $T^{-11}$.)

The proof of Lemma 6.4.8 is the only part of the proof of Theorem 6.3.3 that
uses the calibration property. While we defer the full proof to Appendix C, we
highlight how the calibration property is used to prove Equation 6.2. In
brief, it is straightforward to show that $\partial_{i}L(\mathbf{w})\leq-\ln
p_{J}^{i}$, where $J$ is the random variable corresponding to the realized
outcome.777Writing out the expression for $L(\mathbf{w})$ and differentiating
leaves us with $-\ln p_{J}^{i}$ plus a negative term (see Equation C.2).
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, thus proving Equation
6.2.

Combining Lemma 6.4.8 with an analysis of our algorithm using the standard
regret bound for online mirror descent [312, Theorem 6.8] gives us the
following result as a corollary.

######  Corollary 6.4.9.

The expected total regret of our algorithm conditional on the small gradient
assumption _not_ holding, times the probability of this event, is at most
$\tilde{O}(T^{(5-\alpha)/(1-\alpha)-10})$.

It follows that 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.

####  6.4.5 Approximate calibration

Theorem 6.3.3 holds even if experts are only _approximately_ calibrated.

######  Definition 6.4.10.

For $\tau\geq 1$, we say that expert $i$ is _$\tau$ -calibrated_ if for all
$\mathbf{p}\in\Delta_{n}$ and $j\in[n]$, we have that
$\text{Pr}\left[J=j\mid\mathbf{p}^{j}=\mathbf{p}\right]\leq\tau p_{j}$. We say
that $\mathbb{P}$ satisfies the _$\tau$ -approximate calibration property_ if
every expert is $\tau$-calibrated.

######  Corollary 6.4.11.

For any $\tau$, Theorem 6.3.3 holds even if the calibration property is
replaced with the $\tau$-approximate calibration property.

(Note that the $\tau$ is subsumed by the big-$O$ notation in Theorem 6.3.3;
Corollary 6.4.11 does not allow experts to be arbitrarily miscalibrated.)

Technically, Corollary 6.4.11 is a corollary of the _proof_ of Theorem 6.3.3,
rather than a corollary of the theorem itself.888Fun fact: the technical term
for a corollary to a proof is a _porism_.

###### Proof of Corollary 6.4.11.

We only used the calibration property in the proofs of Equations 6.2 and 6.3.
In the proof of Equation 6.2, we used the fact that $\text{Pr}\left[J=j\mid
p_{j}^{i}\leq e^{-\zeta}\right]\leq e^{-\zeta}$; the right-hand side now
becomes $\tau e^{-\zeta}$, and so the right-hand side of Equation 6.2 changes
to $\tau ne^{-\zeta}$. Similarly, the right-hand side of Equation 6.3
changes999Specifically, in the proof of Equation 6.3, we use the calibration
property in the proof of Lemma C.2.4; the right-hand side of the lemma changes
to $\tau mnq$. to $\tau mn^{2}e^{-\zeta/n}$.

Lemma 6.4.8 is only used in the proof of Corollary 6.4.9, where $2m^{2}n^{2}T$
is replaced by $2\tau m^{2}n^{2}T$. Since $\tau$ is a constant, Corollary
6.4.9 holds verbatim. ∎

###  6.5 Lower bound

In this section, we prove a lower bound result for our setting. Specifically,
we show that no OMD algorithm with a constant step size101010While Algorithm 3
does not always have a constant step size, it does so with high probability.
The examples that prove Theorem 6.5.1 cause $\Omega(\sqrt{T})$ regret in the
typical case, rather than causing unusually large regret in an atypical case.
This makes our comparison of Algorithm 3 to this class fair. substantially
outperforms Algorithm 3.

######  Theorem 6.5.1.

For every strictly convex function $R:\Delta_{m}\to\mathbb{R}$ that is
continuously twice differentiable at its minimum, and $\eta\geq 0$, online
mirror descent with regularizer $R$ and constant step size $\eta$ incurs
$\Omega(\sqrt{T})$ expected regret.

###### Proof.

Our examples will have $m=n=2$. The space of weights is one-dimensional; let
us call $w$ the weight of the first expert. We may treat $R$ as a (convex)
function of $w$, and similarly for the losses at each time step. We assume
that $R^{\prime}(0.5)=0$; this allows us to assume that $w_{1}=0.5$ and does
not affect the proof idea.

It is straightforward to check that if Experts 1 and 2 assign probabilities
$p$ and $\frac{1}{2}$, respectively, to the correct outcome, then

$L^{\prime}(w)=\frac{(1-p)^{w}}{p^{w}+(1-p)^{w}}\ln\frac{1-p}{p}.$

If roles are reversed (they say $\frac{1}{2}$ and $p$ respectively) then

$L^{\prime}(w)=-\frac{(1-p)^{1-w}}{p^{1-w}+(1-p)^{1-w}}\ln\frac{1-p}{p}.$

We first prove the regret bound if $\eta$ is small ($\eta\leq T^{-1/2}$).
Consider the following setting: Expert 1 always reports $(50\%,50\%)$; Expert
2 always reports $(90\%,10\%)$; and Outcome 1 happens with probability $90\%$
at each time step. It is a matter of simple computation that:

  * •

$L^{\prime}(w)\leq 2$ no matter the outcome or the value of $w$.

  * •

If $w\geq 0.4$, then $p^{*}_{1}(w)\leq 0.8$.

The first point implies that $R^{\prime}(w_{t})\geq-2\eta t$ for all $t$. It
follows from the second point that the algorithm will output weights that will
result in an aggregate probability of less than $80\%$ for values of $t$ such
that $-2\eta t\geq R^{\prime}(0.4)$, i.e. for
$t\leq\frac{-R^{\prime}(0.4)}{2\eta}$. Each of these time steps accumulates
constant regret compared to the optimal weight vector in hindsight (which with
high probability will be near $1$). Therefore, the expected total regret
accumulated during these time steps is $\Omega(1/\eta)=\Omega(\sqrt{T})$.

Now we consider the case in which $\eta$ is large ($\eta\geq\sqrt{T}$). In
this case our example is the same as before, except we change which expert is
“ignorant” (reports $(50\%,50\%)$ and which is “informed” (reports
$(90\%,10\%)$). Specifically the informed expert will be the one with a lower
weight (breaking ties arbitrarily).

We will show that our algorithm incurs $\Omega(\eta)$ regret compared to
always choosing weight $0.5$. Suppose without loss of generality that at a
given time step $t$, Expert 1 is informed (so $w^{t}\leq 0.5$). Observe that

$\displaystyle L(w^{t})-L(0.5)$
$\displaystyle=-(0.5-w^{t})L^{\prime}(0.5)+O((0.5-w)^{2})$
$\displaystyle=-(0.5-w^{t})\frac{\sqrt{1-p}}{\sqrt{p}+\sqrt{1-p}}\ln\frac{1-p}{p}+O((0.5-w)^{2}),$

where $p$ is the probability that Expert 1 assigns to the event that happens
(so $p=0.9$ with probability $0.9$ and $p=0.1$ with probability $0.1$). This
expression is (up to lower order terms) equal to $c(0.5-w^{t})$ if $p=0.9$ and
$-3c(0.5-w^{t})$ if $p=0.1$, where $c\approx 0.55$. This means that an
expected regret (relative to $w=0.5$) of $0.6c(0.5-w^{t})$ (up to lower order
terms) is incurred.

Let $D$ be such that $R^{\prime\prime}(w)\leq D$ for all $w$ such that
$\left\lvert w-0.5\right\rvert\leq\frac{\sqrt{T}}{4D}$. (Such a $D$ exists
because $R$ is continuously twice differentiable at $0.5$.) If $\left\lvert
w^{t}-0.5\right\rvert\geq\frac{\sqrt{T}}{4D}$, we just showed that an expected
regret (relative to $w=0.5$) of $\Omega\left(\frac{\sqrt{T}}{4D}\right)$ is
incurred. On the other hand, suppose that $\left\lvert
w^{t}-0.5\right\rvert\leq\frac{\sqrt{T}}{4D}$. We show that $\left\lvert
w^{t+1}-0.5\right\rvert\geq\frac{\sqrt{T}}{4D}$.

To see this, note that $\left\lvert L^{\prime}(w^{t})\right\rvert\geq 0.5$, we
have that $\left\lvert R^{\prime}(w^{t+1})-R^{\prime}(w^{t})\right\rvert\geq
0.5\eta$. We also have that $D\left\lvert
w^{t+1}-w^{t}\right\rvert\geq\left\lvert
R^{\prime}(w^{t+1})-R^{\prime}(w^{t})\right\rvert$, so $D\left\lvert
w^{t+1}-w^{t}\right\rvert\geq 0.5\eta$. Therefore, $\left\lvert
w^{t+1}-w^{t}\right\rvert\geq\frac{\eta}{2D}\geq\frac{\sqrt{T}}{2D}$, which
means that $\left\lvert w^{t+1}-0.5\right\rvert\geq\frac{\sqrt{T}}{4D}$.

This means that an expected regret (relative to $w=0.5$) of
$\Omega\left(\frac{\sqrt{T}}{4D}\right)$ is incurred on at least half of time
steps. Since $D$ is a constant, it follows that a total regret of at least
$\Omega(\sqrt{T})$ is incurred, as desired. ∎

###  6.6 Conclusion

In this work, we have considered the problem of learning optimal weights for
the logarithmic pooling of expert forecasts. It quickly became apparent that
under the usual fully adversarial setup, attaining vanishing regret is
impossible (Example 6.1.1). We chose to relax the environment by imposing the
constraint on the adversary that experts must be calibrated. Put otherwise,
the adversary is allowed to choose a joint probability distribution over the
experts’ reports and the outcome however it wants to, so long as the experts’
reports are calibrated, after which the realized reports and outcome are
selected at random from this distribution. To our knowledge, this setting is a
novel contribution to the literature on prediction with expert advice. The
setting may be of independent interest: we have demonstrated that no-regret
bounds are possible in this setting when they are otherwise impossible, and it
seems plausible that even in settings where no-regret bounds are attainable in
a fully adversarial setting, the calibration property allows for stronger
results.

Another important direction for future work is learning weights for
_generalized_ logarithmic pooling: loosely speaking, logarithmic pooling but
without the requirement that weights add to $1$. In Chapter 2, we introduced
generalized logarithmic pooling and exhibited a class of information
structures for which generalized logarithmic pooling is the Bayesian optimal
aggregation method. This raises the natural question of whether our methods
can be adapted to this more general setting.

Finally, we are interested in learning weights for other pooling methods. In
particular, it is natural to ask which proper loss functions $\ell$ have the
property that it is possible to achieve vanishing regret when learning weights
for QA pooling with respect to $\ell$, and under what assumptions. While in
Chapter 5 we showed that no-regret learning is possible for bounded loss
functions, extending our techniques to unbounded loss functions beyond the log
loss is a promising avenue for future exploration.

## Robust aggregation of substitutable signals

_This chapter presents “Are You Smarter Than a Random Expert? The Robust
Aggregation of Substitutable Signals”[304], although the contents of Section
7.3 are original to this thesis. It assumes background on forecast aggregation
methods (Section 2.2) and information structures (Section 2.3). Although the
relevant definitions will be restated, I strongly recommend reading those
sections before reading this chapter in order to gain context and intuition._

_Summary:_ The problem of aggregating expert forecasts is ubiquitous in fields
as wide-ranging as machine learning, economics, climate science, and national
security. Despite this, our theoretical understanding of this question is
fairly shallow. The work discussed in this chapter initiates the study of
forecast aggregation in a context where experts’ knowledge is chosen
adversarially from a broad class of information structures. While in full
generality it is impossible to achieve a nontrivial performance guarantee, we
show that doing so is possible under a condition on the experts’ information
structure that we call _projective substitutes_. The projective substitutes
condition is a notion of informational substitutes: that there are diminishing
marginal returns to learning the experts’ signals. We show that under the
projective substitutes condition, taking the average of the experts’ forecasts
improves substantially upon the strategy of trusting a random expert. We then
consider a more permissive setting, in which the aggregator has access to the
prior. We show that by averaging the experts’ forecasts and then _extremizing_
the average by moving it away from the prior by a constant factor, the
aggregator’s performance guarantee is substantially better than is possible
without knowledge of the prior. Our results give a theoretical grounding to
past empirical research on extremization and help give guidance on the
appropriate amount to extremize.

###  7.1 Introduction

Suppose that you wish to estimate how much the GDP of the United States will
grow next year: perhaps you are making financial decisions and want to know
whether to expect a downturn. You don’t personally know much about the
question – just that the historical average rate of GDP growth has been 3% –
but on the internet you find several forecasts made by machine learning
models. One model predicts 3.5% growth next year; another predicts 1.5%; a
third predicts a downturn: -1% growth. How might you take this information
into account and turn it into one number: your best guess, all things
considered?111Note the difference in setting from Chapters 5 and 6: we are now
interested in aggregating real-valued forecasts, as opposed to probability
distributions.

Because of the ubiquity of its applications, forecast aggregation is of
critical importance to many fields: economics, climate science, public health,
meteorology, ecology, and sociology, to name a few [295]. Despite this, the
theoretical tools we have for understanding this problem are fairly limited.

What should we ask of a framework for comparing competing aggregation methods?
First, for each fixed setup, it should allow us to quantitatively assess an
aggregation method based on its performance relative to a natural benchmark
(analogous to, for example, assessing an online learning algorithm via its
regret with respect to the best fixed action in hindsight, as we saw in
Chapter 6). Second, the framework should be general: rather than evaluating an
aggregation method based on its performance under a particular assumption
about the experts’ information sets, it should assess the method based on its
performance over a broad range of possible setups.

We can model each expert as having partial information over the state of the
world, and thus the quantity being estimated (which we denote $Y$). The
experts’ information sets may overlap in essentially arbitrary ways, which we
formalize using _information structures_ (introduced in Section 2.3).

No aggregation method is simultaneously optimal for every information
structure. As such, it is natural to ask which aggregation method optimizes
worst-case performance over a broad class of information structures. This is
the approach we take, because it has the aforementioned advantages: it
assesses aggregation methods based on their performance, but does so broadly
rather than under specific assumptions.

####  7.1.1 Our results

Without any conditions on the experts’ information structure, no aggregation
strategy can achieve a nontrivial performance guarantee.222For example,
consider the “XOR information structure” in which two experts receive
independent, random bits, and $Y$ is their XOR. See Section 7.2.3 for further
discussion. In this work, we optimize for worst-case performance over all
information structures that satisfy a condition that we call _projective
informational substitutes_. In Section 2.3.2, we introduced the notion of
_informational substitutes:_ that the value of learning an additional signal
has diminishing marginal returns. The projective substitutes condition is a
particular formalization of this concept that builds on the notion of “weak
information substitutes” (Definition 2.3.5), as we will show that the weak
substitutes condition is insufficient for our purposes.333In Section 7.2.5 we
introduce a “secret sharing” information structure that shows that with no
further assumptions beyond the weak substitutes condition, no aggregation
strategy achieves a better performance guarantee than the strategy of choosing
a random expert to trust. Intuitively, substitutable signals allow for
effective aggregation because signal interactions are more predictable, so it
is possible to infer more from forecasts alone without knowing the information
structure.

We consider two settings: the _prior-free setting_ and the _known prior
setting_. In the prior-free setting, an aggregator receives only the experts’
forecasts as input; in the known prior setting, the aggregator additionally
knows the prior, i.e. the overall expected value of $Y$ (3% in our leading
example). In both settings, the expert must then output an aggregate forecast.

One simple strategy is to pick an expert at random and “aggregate” by
outputing that expert’s forecast. In expectation, this aggregate performs at
least as well as the prior; and under the weak substitutes condition, the
strategy does at least $1/m$ times as well as someone who knew every expert’s
signal and the information structure, where $m$ is the number of experts.444We
judge the performance of an aggregation strategy based on its improvement over
the prior. That is, choosing a random expert attains an _approximation ratio_
of $1/m$. Unfortunately, we exhibit an information structure that satisfies
weak substitutes but on which no aggregation strategy can outperform a
$1/m$-approximation (even in the known prior setting).

However, under our slightly stronger assumption of projective substitutes, it
is possible to improve upon this $1/m$ baseline. Thus, while one can ask about
robust aggregation in many different settings, the projective substitutes
condition appears to be a sweet spot: it allows for a broad array of possible
information structures while still allowing at nontrivial performance
guarantees in both the prior-free and known prior settings. These results are
summarized in Figure 7.1.

Figure 7.1: We are interested in the innermost setting, where nontrivial
positive results are possible. Intervals given for each setting indicate
positive and negative results, respectively (and are stated as asymptotic
approximations in $m$, the number of experts, for the innermost setting).

In Section 7.3, we begin our investigation with a surprisingly strong negative
result. Let $m$ be the number of experts. We show that no aggregation strategy
can hope to perform even $\frac{4}{m}$ times as well as someone who knew every
expert’s signal, _even if the aggregation strategy knows the precise
information structure._ We do this by exhibiting a single information
structure (one that satisfies the projective substitutes condition) in which
the optimal aggregate of the experts’ forecasts performs less than
$\frac{4}{m}$ times as well as the optimal aggregate given all experts’
signals. The information structure is quite natural (it is a PIF information
structure – see Definition 2.3.4, also repeated later in this chapter), and so
our $\frac{4}{m}$ bound serves as a basis of comparison for our other results.
How close to this $\frac{4}{m}$ bound can we get with positive results?

In Section 7.4, we investigate the prior-free setting. In this setting, we
show that under the projective substitutes condition, the aggregation strategy
that averages all experts’ forecasts improves upon the random expert strategy,
attaining an approximation guarantee of roughly $1.866/m$. We also show that
our bound is tight for two experts and close to tight for any number of
experts.

In Section 7.5, we investigate the known prior setting. We prove that it is
possible to improve upon the aforementioned guarantee of the prior-free
setting by _extremizing_ the average of the experts’ beliefs, i.e. moving it
away from the prior. Additionally, our results suggest a particular amount by
which to extremize. Specifically, we show that by _linearly_ extremizing –
moving the average of the experts’ forecasts away from the prior by a
particular constant factor555This factor approaches $\sqrt{3}$ as $m$
approaches infinity. (that depends on $m$) – it is possible to attain an
approximation ratio of roughly $2.598/m$. We show that our positive result is
tight for two experts.

The aforementioned results are stated asymptotically in $m$ for convenience;
however, these asymptotics are not our focus. Instead, our goal is to
understand which _methods_ of aggregation work well in which settings. When is
the tried and true method of averaging forecasts about optimal, and when is it
possible to attain a substantial improvement? Table 7.1 and Figure 7.2
summarize our findings for small values of $m$ (which are plausible for many
of the applications that motivate this work). The high-level takeaways are:

  * •

Under the projective substitutes condition, it is possible to improve
substantially upon selecting a random expert simply by averaging the experts’
forecasts.

  * •

When only the forecasts are known, no technique can substantially improve upon
averaging.

  * •

But when the prior is known, extremizing appropriately is substantially better
than averaging, and in fact better than any possible aggregation strategy that
does not use the prior.

  * •

While there is potentially room for improvement on our extremization
technique, one cannot hope for a very substantial improvement in the
projective substitutes setting – even for an aggregator who knows the entire
information structure.

| Weak subs. | Proj. subs. (prior-free) | Proj. subs. (known prior)
---|---|---|---
m | Pos. & neg. | Averaging (positive) | Negative | Extremizing (positive) | Negative
2 | 0.500 | 0.706 | 0.706 | 0.760 | 0.760
3 | 0.333 | 0.520 | 0.556 | 0.596 | 0.750
4 | 0.250 | 0.409 | 0.438 | 0.488 | 0.640
5 | 0.200 | 0.336 | 0.360 | 0.412 | 0.556
6 | 0.167 | 0.285 | 0.306 | 0.356 | 0.490
7 | 0.143 | 0.248 | 0.265 | 0.314 | 0.438
Table 7.1: For $m=2\dots 7$: the approximation ratio guaranteed by choosing a
random expert, which is the best one can do under weak substitutes, followed
by some of our positive and negative results under the projective substitutes
condition. Note that the negative results for the known prior setting hold
even if the aggregator knows the entire information structure, not just the
prior. Figure 7.2: For $m=2\dots 20$: positive and negative results for
approximation ratios under various settings (similar to Table 7.1). Grey: weak
substitutes (matching positive and negative results). Green: projective
substitutes in the prior-free setting (positive). Red: projective substitutes
in the prior-free setting (negative). Blue: projective substitutes in the
known prior setting (positive). Yellow: projective substitutes in the known
prior setting, and in fact the known information structure setting (negative).

####  7.1.2 Related work

##### Robust aggregation

In Chapter 1, we discussed the two most common approaches to theoretical
questions about forecast aggregation: axiomatic approaches and Bayesian ones.
The axiomatic approach seeks to define desirable properties of aggregation
methods, and asks which methods satisfy these properties. By contrast,
Bayesian approaches take a _parametric_ view of aggregation: experts are
modeled as Bayesians whose signals are drawn from a particular parameterized
family of distributions, and an aggregation method is chosen to optimize an
objective function within the model.

Our approach can be thought of as a hybrid of the axiomatic and Bayesian
approaches, blending what we believe to be the most appealing parts of each.
We draw from the Bayesian approach in using information structures as a
formalism for the experts’ knowledge, whereas the goal of producing a single
role that satisfies some global property (in our case, worst-case optimality)
is reminiscent of the axiomatic approach. Our model is non-parametric: rather
than assuming a parameterized family of distributions, we seek to optimize our
aggregation method against a broad class of information structures.

Our work is most similar to [191], which likewise seeks to optimize an
aggregation method against an adversarially selected information structure.
However, the class of information structures that we consider is broader:
while they consider the case of two Blackwell-ordered experts (i.e. two
experts, an unknown one of whom knows strictly more than the other) and two
conditionally independent experts, we consider an arbitrary number of experts
from any information structure that satisfies the projective substitutes
condition. [289] have a similar model, but are also quite restrictive in terms
of the information structures they consider. [310] use a similar model, but
more distantly related: they consider arbitrary decision problems but restrict
the aggregator to a finite number of decisions (just two decisions for many of
their results) – in our setting this would mean forcing the aggregator to
choose among finitely many output choices. Our notion of robustness is also
similar to that of prior-independent algorithm design (see e.g. [268, §3]),
though in a quite different setting.

Another important difference is that most of the previously mentioned work
specifically considers the aggregation of _probabilistic_ forecasts, whereas
we are interested in aggregating expected value forecasts for arbitrary real-
valued quantities.

##### Extremization

In Section 2.2, we discussed the merits of extremization: pushing the average
of the experts’ forecasts away from the prior. Past empirical work has
demonstrated that extremizing the average of the experts’ forecasts often
improves the aggregate forecast [331, 199, 334]. [199] explain this by noting
that any individual forecaster should incorporate the fact that they may be
missing useful information available to other forecasters, and that simply
averaging forecasts would fail to incorporate the full wisdom of the crowd.
Studying aggregation in the context of information structures as well, [334]
note that the forecast average _lacks resolution_ , meaning that its variance
is provably too low, and finds that extremization helps to solve this issue.
[333] note that the more disjoint the experts’ information, the more it makes
sense to extremize. [329] refines this approach, suggesting that the variance
of forecasts be taken into consideration.

However, none of the aforementioned works aim to show that extremization
produces better results across a broad class of information structures;
instead, the authors consider particular structures, such as experts with
correlated Gaussian signals. [334] note that the information structure
framework is in full generality “too abstract to be applied in practice.” On
the other hand, our approach of robust aggregation is able not only to provide
a theoretical justification for extremization, but also to suggest a
particular factor of extremization (Theorem 7.5.1), thus giving rigorous
backing to what had previously been justified either by empirical heuristics
or by optimization over a quite narrow class of information structures.

###  7.2 Key definitions and preliminaries

####  7.2.1 Information structures

We introduced information structures in Section 2.3. Information structures
will be essential to this chapter, so we recommend reviewing that discussion.
For convenience, we restate the definition below.

See 2.3.1

In this chapter, $Y$ will specifically be a real-valued random variable. We
will also assume that $Y$ has finite variance. As usual, we will interpret
each signal $\sigma_{i}$ as belonging to expert $i$.

We also recall the XOR information structure:

See 2.3.8

Just as in Section 2.3, given a subset $A\subseteq[m]$, we define
$Y_{A}:=\mathbb{E}\left[Y\mid\sigma_{i}:i\in A\right]$. That is, $Y_{A}$ is
the random variable whose value is the expectation of $Y$ given the signals of
the experts in $A$. If $A=\\{i\\}$, we write $Y_{i}$ in place of
$Y_{\\{i\\}}$.

####  7.2.2 The Pythagorean theorem

Recall from Section 2.3.3 the Pythagorean theorem:

See 2.3.11

As discussed in Section 2.3.3, random variables can be thought of as vectors
in a Hilbert space with inner product $\left\langle
X,Y\right\rangle:=\mathbb{E}\left[XY\right]$. In this space, uncorrelated
random variables correspond to orthogonal vectors, and conditional
expectations correspond to orthogonal projections. Proposition 2.3.11 is
simply an application of the usual Pythagorean theorem in the context of this
space.

####  7.2.3 Improving on the prior

In this work, we will be taking the perspective of an aggregator who receives
estimates of $Y$ from each expert.666These estimates are each expert’s
expectation of $Y$ conditioned on their signal. The aggregator does not
receive signals from experts. The aggregator then produces an estimate $Z$ of
$Y$ which is as accurate as possible. In particular, we care about the
_robust_ estimation of $Y$: a single estimate that is simultaneously as
accurate as possible across all possible information structures (satisfying
the projective substitutes condition, which we discuss below).

We assess an aggregator’s performance by the squared distance between their
estimate $Z$ and the true value $Y$. That is, the aggregator wishes to
minimize $\mathbb{E}\left[(Y-Z)^{2}\right]$. We define the function $v(Z)$ as
follows to reflect the _quality of $Z$ as an estimate of $Y$_.

######  Definition 7.2.1.

Given an information structure
$\mathcal{I}=(\Omega,\mathbb{P},\boldsymbol{\sigma},Y)$ and a random variable
$Z$, we define

$v(Z):=\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y-Z)^{2}\right].$

Thus, $v(\cdot)$ is the improvement in loss provided by $Z$ over an uninformed
estimate. For example, $v(Y_{\emptyset})=0$ and
$v(Y)=\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]$ is the variance
of $Y$. We cannot possibly hope for any $Z$ such that $v(Z)>Y_{[m]}$, since
$Y_{[m]}$ is the estimate produced by knowing all information that exists.
This motivates comparing $v(Z)$ against the benchmark $v(Y_{[m]})$.

However, the aggregator does not know the underlying information structure –
only the experts’ estimates. Specifically, we will consider two settings:

  1. (1)

The _prior-free setting_ : the aggregator’s estimate is only based on the
experts’ estimates. That is, $Z$ is a function of $Y_{1},\dots,Y_{m}$.

  2. (2)

The _known prior setting_ : the aggregator knows the experts’ estimates and
the prior. That is, $Z$ is a function of $Y_{1},\dots,Y_{m}$ and
$\mathbb{E}\left[Y\right]$.

That is, $Z$ is a function of $m$ real numbers (or $m+1$, in the known prior
setting); we call this function the aggregator’s _aggregation strategy_. The
aggregator’s goal is to come up with an aggregation strategy that performs
well across information structures (we formalize this below).

In the known prior setting, the aggregator can report
$Z=\mathbb{E}\left[Y\right]$; then $v(Z)=0$ (we call this the _trivial
aggregation strategy_). In both settings it is possible to do at least as well
as the trivial aggregation strategy by reporting e.g. $Z=Y_{1}$. On the other
hand, without any conditions on the information structure, it is not always
possible to do strictly better: in the XOR information structure, the
aggregator is guaranteed to receive $Y_{1}=Y_{2}=\frac{1}{2}$, and it is
impossible for the aggregator to improve upon simply reporting the prior of
$\frac{1}{2}$.

####  7.2.4 Informational complements and substitutes

Intuitively, in the XOR information structure, the aggregator is impeded by
the fact that the experts’ signals are informational complements: each signal
(and the estimate it produces) is not valuable by itself, but the two signals
are valuable when taken together. Perhaps if we assume that the experts’
signals are instead informational substitutes, then we will be able to prove
nontrivial guarantees about some aggregation strategies. And so, we recall the
notion of weak informational substitutes from Section 2.3.2.

See 2.3.5

######  Remark 7.2.2.

Equivalently, we can say that $\mathcal{I}$ satisfies weak informational
substitutes if for all $B\subseteq A\subseteq[m]$ and $i\not\in A$, we have

$v(Y_{A\cup\\{i\\}})-v(Y_{A})\leq v(Y_{B\cup\\{i\\}})-v(Y_{B}).$ (7.1)

####  7.2.5 Random expert strategy under weak substitutes

It is not surprising that with no knowledge of the information structure, it
is impossible to outperform the trivial strategy. Perhaps it would be possible
to do better with only a coarse constraint on the information structure. It is
not _a priori_ obvious that this should be possible. However, if $\mathcal{I}$
satisfies weak substitutes, then it is possible to outperform the trivial
strategy by reporting a random expert’s belief:

######  Proposition 7.2.3.

Suppose that $\mathcal{I}=(\Omega,\mathbb{P},\boldsymbol{\sigma},Y)$ satisfies
weak substitutes, and let $Z$ be equal to $Y_{i}$ for a uniformly random
$i\in[m]$ (we call this the _random expert strategy_). Then
$v(Z)\geq\frac{1}{m}v(Y_{[m]})$.

###### Proof.

For $j\in[m]$, plug $A=[j-1],B=\emptyset,i=j$ into Equation 7.1. Adding these
$m$ inequalities (and noting that $v(\emptyset)=0$), we find that
$\sum_{j=1}^{m}v(Y_{j})\geq v(Y_{[m]})$. Therefore, for $Z$ as in the
proposition statement, we have

$v(Z)=\frac{1}{m}\sum_{i=1}^{m}v(Y_{i})\geq\frac{1}{m}v(Y_{[m]}),$

as desired. ∎

Put otherwise, the random expert strategy attains an _approximation ratio_ of
$1/m$.

######  Definition 7.2.4.

Given an information structure
$\mathcal{I}=(\Omega,\mathbb{P},\boldsymbol{\sigma},Y)$ with $m$ experts, the
_approximation ratio_ of a random variable $Z$ is given by the quantity
$v(Z)/v\left(Y_{[m]}\right)$.

The Pythagorean theorem lets us rewrite the approximation ratio in a more
convenient form.

######  Claim 7.2.5.

If a random variable $Z$ depends only on $\sigma_{1},\dots,\sigma_{m}$, the
approximation ratio of $Z$ (i.e. $v(Z)/v(Y_{[m]})$) is equal to

$1-\frac{\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]}{\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]}.$

###### Proof.

We have

$\displaystyle\frac{v(Z)}{v(Y_{[m]})}$
$\displaystyle=\frac{\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y-Z)^{2}\right]}{\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y-Y_{[m]})^{2}\right]}$
$\displaystyle=\frac{\left(\mathbb{E}\left[(Y-Y_{[m]})^{2}\right]+\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]\right)-\left(\mathbb{E}\left[(Y-Y_{[m]})^{2}\right]+\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]\right)}{\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y-Y_{[m]})^{2}\right]}$
$\displaystyle=\frac{\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]}{\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]}=1-\frac{\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]}{\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]}.$

In the second step, we use the Pythagorean theorem twice: one time we plug in
$A=Y$, $B=Y_{[m]}$, $C=\mathbb{E}\left[Y\right]$, and the other time, $A=Y$,
$B=Y_{[m]}$, $C=Z$. In the third step, we again use the Pythagorean theorem,
plugging in $A=Y$, $B=Y_{[m]}$, $C=\mathbb{E}\left[Y\right]$. ∎

Unfortunately, the following result shows that with no further assumptions, it
is not possible to guarantee an approximation ratio larger than $1/m$:

######  Proposition 7.2.6.

For every $m$, there is an information structure that satisfies the weak
substitutes condition, such that in both the prior-free and known prior
settings, no aggregation strategy attains an approximation ratio greater than
$1/m$ on the information structure.

The key idea is to use Shamir secret sharing [340] to create an
$(m,r)$-threshold scheme for a uniformly random $r\in[m]$. Then $v(\cdot)$ is
additive (and thus submodular) on the subsets of $[m]$, but an aggregator who
only knows the experts’ reports will only be able to recover the secret if
$r=1$.

###### Proof.

Let $p>m$ be a prime. Consider the following information structure (the
_secret sharing information structure_).

  * •

An integer $r\in[m]$ is selected uniformly at random and announced.

  * •

A random $(r-1)$-th degree polynomial $P(x)=a_{0}+a_{1}x+\dots+a_{r-1}x^{r-1}$
over $\mathbb{F}_{p}$ is selected, with coefficients chosen uniformly at
random from $\mathbb{F}_{p}$, except that $a_{0}$ is either $-1$ or $1$ (also
uniformly). For each $i\in[m]$, expert $i$ is told $P(i)$.

  * •

The quantity $Y$ is equal to $1$ if $a_{0}=1$ and $-1$ if $a_{0}=-1$.

Note that for a fixed choice of $r$ and for any $A\subseteq[m]$, we have
$Y_{A}=0$ if $\left\lvert A\right\rvert<r$ and $Y_{A}=\pm 1$ if $\left\lvert
A\right\rvert\geq r$. Therefore, for any $A$ we have that $Y_{A}=\pm 1$ with
probability $\frac{\left\lvert A\right\rvert}{m}$ and $0$ otherwise.
Therefore, we have that $v(Y_{A})=\frac{\left\lvert A\right\rvert}{m}$, so
$v(\cdot)$ is additive (and thus submodular). Thus, this information structure
satisfies weak substitutes.

On the other hand, note that with probability $\frac{m-1}{m}$, all experts
report $0$ to the aggregator, in which case the aggregator cannot do better in
expectation than also reporting $0$. Thus, it is impossible for the aggregator
to report an estimate $Z$ with $v(Z)>\frac{1}{m}$, and so an approximation
ratio larger than $\frac{1}{m}$ is not attainable. ∎

The secret sharing information structure is a lottery over $m$ different
information structures, for each of which $v(\cdot)$ is a threshold function:
any $r-1$ experts know nothing ($v(A)=0$ if $\left\lvert A\right\rvert<r$),
while any $r$ experts know everything ($v(A)=1$ if $\left\lvert
A\right\rvert\geq r$). Except for $r=1$, these information structures have
experts that should be intuitively regarded as _complementary_. Indeed, these
structures generalize the XOR information structure (which is the case of
$m=r=2$). This suggests that properties of $v(\cdot)$ as a set function on
$[m]$ are insufficient to capture what we intuitively mean by substitutable
signals. This motivates us to seek a natural but stronger notion of
informational substitutes – one that is well-motivated and not too
restrictive, but which rules out information structures such as this one and
allows an aggregator to outperform the guarantee of the random expert
strategy.

####  7.2.6 Projective substitutes

The following fact helps to motivate our stronger notion of informational
substitutes.

######  Proposition 7.2.7.

The weak substitutes condition may be rewritten as: for any $i$ and
$B\subseteq A$, we have

$\mathbb{E}\left[(Y_{A}-Y_{B})^{2}\right]\geq\mathbb{E}\left[(Y_{A\cup\\{i\\}}-Y_{B\cup\\{i\\}})^{2}\right].$

###### Proof.

By the Pythagorean theorem, we have that

$\mathbb{E}\left[(Y_{A}-Y_{B})^{2}\right]=\mathbb{E}\left[(Y-Y_{A})^{2}\right]-\mathbb{E}\left[(Y-Y_{B})^{2}\right],$

and similarly for the right-hand side. Rearranging terms gives us Equation
2.4. ∎

Intuitively, this interpretation of substitutes says: For any expert $i$, a
set $B$ of experts becomes better at predicting the belief of a superset of
experts $A$ if $i$’s signal is announced. Here, by the _belief_ of a set $T$
of experts we mean the expected value of $Y$ conditioned on all experts’
signals, i.e. $Y_{T}$.

This matches the intuition of substitutes as diminishing marginal returns: if
signal $i$ becomes known, the “information gap” between $A$ and $B$ decreases.

A more general notion of substitutes would require this to hold _even when $A$
is not a supserset of $B$_. That is: for all $i,A,B$, the experts in
$B\cup\\{i\\}$ can collectively predict the belief of $A\cup\\{i\\}$ better
than the experts in $B$ can collectively predict the belief of $A$. This
captures the spirit of diminishing marginal returns in a somewhat broader
context.

Let us formalize the notion of $B$’s prediction of $A$’s belief. By this we
mean the expected value of $Y_{A}$ given the signal outcomes of the experts in
$B$, i.e. $\mathbb{E}\left[Y_{A}\mid\\{\sigma_{i}:i\in B\\}\right]$.

######  Definition 7.2.8.

Given an information structure
$\mathcal{I}=(\Omega,\mathbb{P},\boldsymbol{\sigma},Y)$ for $m$ experts and
subsets $A,B\subseteq[m]$, _$B$ ’s prediction of $A$’s belief_ is defined as
the expected value of $Y_{A}$ given the signal outcomes of the experts in $B$,
i.e.

$Y_{A\to B}:=\mathbb{E}\left[Y_{A}\mid\\{\sigma_{i}:i\in B\\}\right].$

We now state our substitutes definition, which strengthens the weak
substitutes condition.

######  Definition 7.2.9.

An information structure
$\mathcal{I}=(\Omega,\mathbb{P},\boldsymbol{\sigma},Y)$ for $m$ experts
satisfies _projective substitutes_ if for all $A,B\subseteq[m]$ and $i\in[m]$,
we have

$\mathbb{E}\left[(Y_{A}-Y_{A\to
B})^{2}\right]\geq\mathbb{E}\left[(Y_{A\cup\\{i\\}}-Y_{A\cup\\{i\\}\to
B\cup\\{i\\}})^{2}\right].$ (7.2)

The secret sharing information structure does not satisfy projective
substitutes: take $A,B,i$ with $\left\lvert A\right\rvert\geq\left\lvert
B\right\rvert$ (but $A\not\supseteq B$) and $i\in B\setminus A$. On the other
hand, the example below does satisfy projective substitutes.

######  Example 7.2.10.

Consider the following information structure, in which the value of $Y$ is
determined by the values of $\sigma_{1}$ and $\sigma_{2}$. The table on the
left specifies the value of $Y$ depending on the pair of signals, and the
table on the right specifies the probability of each pair of signals. (Note
that the signal values $w,x,y,z$ are arbitrary labels.)

$\left\\{Y=\begin{tabular}[]{c|cc}&$\sigma_{2}=y$&$\sigma_{2}=z$\\\
\hline\cr$\sigma_{1}=w$&0&1\\\
$\sigma_{1}=x$&1&2\end{tabular}\qquad\mathbb{P}=\begin{tabular}[]{c|cc}&$\sigma_{2}=y$&$\sigma_{2}=z$\\\
\hline\cr$\sigma_{1}=w$&0.3&0.2\\\
$\sigma_{1}=x$&0.2&0.3\end{tabular}\right\\}$

Let $A=\\{1\\}$ and $B=\\{2\\}$. It is not difficult to compute that

$Y_{A}=\begin{tabular}[]{c|cc}&$\sigma_{2}=y$&$\sigma_{2}=z$\\\
\hline\cr$\sigma_{1}=w$&0.4&0.4\\\
$\sigma_{1}=x$&1.6&1.6\end{tabular}\qquad\qquad Y_{A\to
B}=\begin{tabular}[]{c|cc}&$\sigma_{2}=y$&$\sigma_{2}=z$\\\
\hline\cr$\sigma_{1}=w$&0.88&1.12\\\ $\sigma_{1}=x$&0.88&1.12\end{tabular}$

For example, in the $(\sigma_{1},\sigma_{2})=(w,y)$ case we have that
$Y_{A}=\frac{0.3\cdot 0+0.2\cdot 1}{0.3+0.2}=0.4$. $Y_{A}$ is then used to
compute $Y_{A\to B}$: for example, in the $(\sigma_{1},\sigma_{2})=(w,y)$ case
we have that $Y_{A\to B}=\frac{0.3\cdot 0.4+0.2\cdot 1.6}{0.3+0.2}=0.88$, as
this is the expected value of $Y_{A}$ conditioned on $\sigma_{2}=y$.

It can be computed that $\mathbb{E}\left[(Y_{A}-Y_{A\to
B})^{2}\right]=0.3456$, whereas
$\mathbb{E}\left[(Y_{A\cup\\{2\\}}-Y_{A\cup\\{2\\}\to
B\cup\\{2\\}})^{2}\right]=\mathbb{E}\left[(Y-Y_{B})^{2}\right]=0.24$, so
Equation 7.2 is satisfied for $A=\\{1\\},B=\\{2\\},i=2$. It can be verified
that Equation 7.2 is in fact satisfied for _all_ $A,B,i$, so this information
structure satisfies projective substitutes.

The projective substitutes definition can be interpreted as describing the
class of information structures in which full information revelation is a
dominant strategy. While in general we are interested in aggregation, not
elicitation, we present the following thought experiment in order to motivate
the projective substitutes condition.

Consider a central party (call them the _elicitor_) who knows the information
structure but does not know the experts’ signals. Experts are truthful, but
may be strategic: they will not lie about their signal, but may decide not to