No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling
Authors: Eric Neyman
Tim Roughgarden
Venue: NeurIPS 2023 poster (2023)
Keywords: Logarithmic pooling
online learning
no-regret learning
calibrated experts
online mirror descent
prediction with expert advice
TL;DR: We present a no-regret algorithm that learns weights for a logarithmic pool of expert forecasts, under the condition that the forecasts are calibrated.

Abstract: 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 the fundamental and practical aggregation method known as *logarithmic pooling* -- a weighted average of log odds -- which is in a certain sense the optimal choice of pooling method if one is interested in minimizing log loss (as we take to be our loss function). 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.

No- Learning with Unbounded Losses: The Case of Logarithmic Pooling
Eric Neyman
Tim Roughgarden Columbia University New York, NY 10027
Columbia University
New York, NY 10027
eric. neyman@columbia edu
tim. wwt..roogggaaddn@gmill.coo
Abstract
For each of I'' time steps, experts report probability distributions comes; we wish to learn to aggregate these forecasts in way that attains a no-regret guarantee. We focus the fundamental and practical aggregation method known as logarithmic pooling - a weighted average of log odds which sense the optimal choice of pooling method if one interested in minimizing log loss (as we take to be our loss function). We consider the problem of learning the best set of parameters (i.e. expert weights) in 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 large amount of flexibility. In this setting, we present an algo- rithm based on online mirror descent that learns expert weights in a way that attains (vT log 7') expected regret as compared with the best weights in hindsight.
out-
certain
Introduction
1.1 Logarithmic pooling
Suppose that experts report probability distributions p'....,,''' E A over disjoint, exhaustive outcomes. We are interested aggregating these distributions into single distribution p task known probabilistic opinion pooling. Perhaps the most straightforward way to do this is to take the arithmetic mean, also called the linear pool: p m E.
While commonly studied and frequently used, the linear pool is by no means the definitive opinion pooling method. The choice of pooling method ought to depend on context, and in particular on the loss function with respect to which forecasts are assessed. [Nymann and Roughgarden (2023) showed a correspondence between proper loss functions and opinion pooling methods, which they termed quasi-arinn araas--rithmmttic (QA) pooling with respect to loss function. Specifically, the QA pool with respect to loss is the forecast that guarantees the largest possible overperformance (as judged by the loss function) compared with the strategy of choosing random expert to trust!?
In this work we will be using log loss function. The QA pooling technique with respect to the log loss is known as logarithmic pooling. Instead of averaging the experts' forecasts, logarithmic pooling averages the experts' log odds (i.e. logits). Put otherwise, the logarithmic pool is defined by
pj -= (p))
'oore formally, the QA pool maximizes the minimum (over possible outcomes) improvement in the loss.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

for all events j [n]] where e is normalizing constant to ensure that the probabilities add to 1. While the linear pool an arithmetic mean, the logarithmic pool behaves much more like geometric mean. For instance, the logarithmic pool of (0.001, 0.999) and (0.5, 0.5) with equal weights is approximately (0.03, 0.97).
The logarithmic pool has been studied extensively because of its naturalness (Genest 1984 Genest
and Zidek 1986 Givens and Roback 1999 Poole and Raftery 2000 Kascha and Ravazzolo 2008
Rufo et al. 2012; Allard et al. 22012). Logarithmic pooling can be interpreted as averaging experts
Bayesian evidence (eymann and Roughgarden 2023 $A). It also the most natural pooling method
that satisfies external Bayesianaliry, meaning roughly that it does not matter whether a Bayesian update is applied to each expert's 's forecast before aggregation, or if instead the Bayesian update is applied to the pooled forecast (Genest] 1984). Logarithmic pooling can also be characterized as the pooling method that minimizes the average KI. divergence the experts' reports (Abbas) (2009). Finally, empirical work has found logarithmic pooling performs very well on real-world data (Satopaä et al. 2014. Sevilla 2021).
1.2 Logarithmic pooling with weighted experts
Forecast aggregators often assign different weights to different experts. e.g. based on each expert's level of knowledge or track record (Tetlock and Gardner 2015). There is principled way to include weights wi...., W; (summing 1) in the logarithmic pool, namely:
(w) c(w) (T)
where c(w) is again normalizing constant that now depends on the weights f This more general notion continues to have all of the aforementioned natural properties.
The obvious question is: how does one know what these weights should be? Perhaps the most natural answer is to weight experts according their past performance. Finding appropriate weights for experts is thus an online learning problem. This learning problem is the focus of our work.
1.3 Choosing the right benchmark
Our goal 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 (i.c. the loss function most closely associated with this pooling method). 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 way that depends on forecasts output an essentially arbitrary function of the forecasts, and thus may do something other than learn optimal weights for logarithmic intentions
pooling. For example, suppose that 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. P1 (90%, 10%) and P2 = (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.
n 2 and an aggregator wishes to subvert
One might suggest the following setup: at each time step, the algorithm selects weights for each expert. Subsequently, adversary chooses each expert's forecast and the outcome, after which the algorithm and each expert incur log loss. Unfortunately - due to the unboundedness of log loss and the behavior of logarithmic pooling vanishing regret guarantees in this setting are impossible.
'eere it not for the normalizing constant, the log loss incurred by the logarithmic pool p1 (w) would be linear function of the weights. However, the c(w) term significantly complicates this picture.

---

Example 1.1. Consider the case of m = n 2. Without loss of generality, suppose that the algorithm assigns Expert 1 weight u 2 0.5 in the first time step. The adversary chooses reports (e-1.1 - e for Expert I and 2.22 2) for Expert 2, and for Outcome 1 to happen. The logarithmic pool of the forecasts turns out to be approximately (c-wT" 1
e-=T") ). so the algorithm incurs log loss of approximately wT 2 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), the algorithm cannot catch up.
What goes wrong in Example 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, am expert assigns 10% chance to 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. The adversary retains full control over correlations between forecasts and outcomes, subject to the 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 's regret.
Why impose this constraint, instead of a different one? Our reasons are twofold: theoretical and empirical. From theoretical standpoint, the assumption that experts are calibrated is natural because experts who form Bayesian rational belief's based on evidence will be calibrated, regardless of how much or how little evidence they have. The assumption is also motivated we model experts as learners rather than Bayesian agents: even if forecaster starts out completely uninformed, they can quickly become calibrated domain simply by observing the frequency of events (Foster and Vohra 1997).
Second, recent work has shown that modern deep neural networks are calibrated when trained proper loss function such as log loss. This is true for a variety of tasks, including image classification (Minderer et al.) 2021 Hendrycks et al., 2020) and language modeling (Kadavath al., 2022 Desai and Durrett 2020 OpenAl 2023); see (Blasiok et al. 2023) for a review of the literature. We may wish use an ensemble of off-the-shele 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 lincar pool of roughly (25%, 75%). If Expert I 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, is sensible for the aggregate to point to Outcome over Outcome 1 with a fair amount of confidence.
As another example, suppose that Expert reports (0.04%, 49.98%, 49. 49.98% and Expert 2 reports (49.98%, 0.04%, 49.98%) ) (a natural interpretation: Expert found strong evidence against Outcome i and Expert found strong evidence against Outcome 2). If both experts calibrated, 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 paper 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.
3

---

1.4 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(V log I') with the number of time steps T. Our algorithm uses online mirror descent (OMD) with the Tsallis entropy regularizer R(w)- = (wf + ...................... w and step size 1y 83 the regret bound.
VTlaT' where any choice of a E (0, 1/2) attains
Our proof has two key ideas. One is to use the calibration property show that the gradient of loss with respect to the weight vector is likely to be small (Section 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 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 indeed small, then this potential function decreases in value each time step. This allows to upper bound the algorithm's 's regret by the initial value of the potential function.
This potential argument is important component of the proof. A naive 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(VTlog 7) regret bound. In particular, an adversary force large accumulation of regret if some experts' weights 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 A.8). We also show in Appendix that no OMD algorithm with constant step size attain expected regret better than ((VT).
2 Related work
2.1 Probabilistic opinion pooling
There has been substantial mathematical work on probabilistic opinion pooling (i.e. forecast aggrega- tion) since the 1980s. One line of work is axiomatic in nature: motivating opinion pooling methods by describing axioms that they satisfy. For example, logarithmic pooling satisfies unanimity preservation and external Bayesianality (Genest) 1984). There has also been work on Bayesian approaches to pooling, e.g. under the assumption that experts' signals are drawn from some parameterized class of distributions (Winkler 1981 Lichtendahl et al. 2017).
Neyman and Roughgarden (202)) show that every proper loss function has an associated pooling method (the QA pool with respect to the loss function), which is the forecast that guarantees the largest possible overperformance (as judged by the loss function) compared with the strategy of choosing random expert to trust. This mapping is bijection: pooling method is QA pooling with respect to some proper loss function if and only if it satisfies certain natural axioms.
2.2 Online prediction with expert advice
In the subfield of prediction with expert advice, for time steps, experts report "predictions" from a decision space D (often, in our case, the space of probability distributions over set of outcomes). forecaster must then output their own prediction from D. Then, predictions are assessed according to loss function. See Cesa- -ieachiianchi and Lugosi (206)) for 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(VT) regret for bounded, convex losses, but it is sometimes possible to do

---

better. For example, if the loss function is bounded and exp-coneave then logarithmic regret in T is attainable (Cesa-Bianch)) and Lugosi 2006 $3.3).
Portfolio theory studies optimal stock selection for maximizing return on investment, often a no-regret setting. Cover (1991) introduced the "universal portfolio" algorithm, which, for each of I' time steps, selects portfolio (convex combination of stocks). Our setting translates naturally to Cover's: experts play the role of stocks, and the return of 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 hindsight (Cover and Ordentlich 1996]; in our terms, this means that logarithmic regret (for log loss) is attainable for the linear pooling of experts. We refer the reader (Li and Hoi 2014) for a survey of this area.
To our knowledge, learning weights for logarithmic pooling has not been previously studied. As shown in Example [.T] it is possible achieve vanishing regret if the setting is fully adversarial. We relax our setting by insisting that the experts be calibrated (see Section (.1). To our knowledge, online prediction with expert advice has also not previously been studied under this condition.
3 Preliminaries
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 p',.... ...., , over outcomes. We will use J to denote the random variable corresponding to the outcome, i.e. J takes values in [r²].
Definition 3.1. Consider a joint probability distribution P over experts' reports and the outcome We say that expert is calibrated if for all p E A and j E [n]. we have that
P P 1p
Pj-
That is, expert i is calibrated if the probability distribution of J conditional on their report p is precisely p'. We say that IP satisfies the calibration property if every expert is calibrated.
The key intuition behind the usefulness of calibration is that if an expert claims that outcome is very unlikely, this is strong evidence that the outcome is in fact unlikely. In Section 4.4 we will use the calibration property to show that the gradient of the loss with respect to the weight vector likely to be relatively small at each time step.
3.2 Our online learning setting
The setting for our online learning problem is as follows. For each time step t E [T]:
Our algorithm reports weight vector w( A.
(2) An adversary (with knowledge of w²) constructs probability distribution P. over reports and the outcome, that satisfies the calibration property.
(3) Reports p*1 ..... f.m and outcome j are sampled from P.
(4) The loss of a weight vector w is defined as L'(w): == - (w)), the log loss of the logarithmic pool of gfi,,..,p'" p with weights w. Our algorithm incurs loss T.((w*)
We define the regret of our algorithm
T Regret- Σ D'(w") [=1
T
Σ L'(w). WEA
min
[=1
That is, the benchmark for regret the best weight vector 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)
3 An equivalent, more mechanistic formulation views P instead as joint probability distribution over signals received by each expert (i.e. the expert's private knowledge) and the outcome. Such a probability distribution known as an information structure, see (Bergemann and Morris 2019). Each expert computes their belief' from their signal.
5

---

Even subject to the calibration property, the adversary has 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 function of the number of experts), whereas the calibration property imposes mere linear number of constraints
3.3 Our algorithm
We use Algorithm D to accomplish this goal. The algorithm is online mirror descent (OMD) on the weight vector. Fix any a E (0, 1/2). We use the regularizer
R(w)
w
This is known as the Tsallis entropy regularizer; see e.g. (Zimmert and Seldin 2021) for previous use in the online learning literature. We obtain the same result (up multipiicative factor that depends on a)) regardless of the choice of a. Because no choice a stands out, we prove our result for all (0, 1/2) simultancously.
We will generally use step size 1j = Vn 12m(21a)/2m However, in the (unlikely, as we show) event that some expert's 's weight becomes unusually small, we will reduce the step size.
ALGORITHM 1: OMD algorithm for learning weights for logarithmic pooling
R(w) = [ff + ..... w
/* Any E (0,1/2) will work +/
f VTnTT 12m(4+))/2n)
w! - (1/m,.... 1/m);
for t to T do
n I min;((u{))) then
11 min(n:-1,7))
else
7) min(n-1.. min, w!): Edge case; happens with low probability
end
Observe loss function L'; /* L' is chosen as described in Section 3.2 +/ Define 1+1 such that V VR(W (+)) = R Th (ww)
end
In Appendix we prove that Algorithm is efficient, taking ((m)) time per time step.
Theorem
3.2 formally states our no-regret guarantee.
Theorem 3.2. For any adversarial strategy, the expected regre of Algorithm 1 is most
o (m
4
Proof of no-regret guarantee
In this section, we prove Theorem 3.2
4.1 Outline of proof
We use the following fact. which follows from a more general statement about how losses relate to their associated quasi-arithmetic pools.
*This follows from the perspective of the adversary choosing an information structure from which experts' signals drawn, also alluded in the previous footnote. The information structure specifies the probability every possible combination signals received by the experts, and the number experts. The calibration property imposes linearly many constraints on this space. 'The given asymptotics assume that I' > m, ie. ignore terms that are lower-order in T.
dimension that exponential

---

Proposition 4.1 (Follows from Neyman and Roughgarden, 2023 be forecasts over outcomes, j E n be an outcome, and w A th be a weight vector. Let p" (w) be the logarithumic pool of the forecasts with weight vector w and let [(w) == -1---1nn (n(p be the log loss of (w) if Outcome j is realized. Then L is convex function.
Theorem 5.1)). Letp'..... pm
In particular, all of our loss functions L' are convex, which means that standard regret bounds apply. In particular, to bound the expected regret of Algorithm we will use well-known regret bound for follow the regularized leader (FTRL) with linearized losses (Hazan 2021
Lemma 5.3), which in our
case is equivalent to OMD
Lemma 4.2 (Follows from (Hazan 2021 is at most
Lemma 5.3)). nf fj all i, the regret of Algorithm 7
T VL'(w") (w" -w!t1).
max R(w)- - min R(w) wEAm
+
" WEAM
Informally, this bound means that if the vectors (w'(w") are small in magnitude, our regret is also small. Conversely, if some Vw'(w") 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 very low probability to the correct outcome), since the loss would then be steeply increasing as a function of that expert's 's weight. Fortunately, the calibration property guarantees this to be unlikely. Specifically, define the small gradient assumption as follows.
Definition 4.3. Define 7 := 12n T The small gradient assumption holds for a particular run of Algorithm iif for every & E [2] and [m]] we have
?
S O.I''(w') Syy
w
where 0 denotes the partial derivative with respect to the i-th weight
In Section 4.4
we prove that the small gradient assumption is very likely to hold. This is 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 's regret. We then 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 hold.
In Sections 4.2 and 4.3] we bound regret under the condition that the small gradient assumption holds. We show that under the assumption, for all i, we have (wf) 2 n7. Consequently, 1j
JThT 12m at all time steps, so we can apply Lemma 4.2 The first term in the bound is O(1/n) O(vT log T'. As for the summation term, upper bound it by keeping track of the following quantity:
(0()= = Σ VI*(w") (w" w + 19m2 102222n(TTT - 1) - 44 Σ In w 1+1
i=1
The first term is exactly the summation in Lemma 4.2 up2 up through step t. The 19m??2n is something akin to an upper bound on the value of L'(w") (w' wf+1) at 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 vof). However, attaining 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, (t() necessarily decreases with t. This argument, which we give in Section 4.3 is another key conceptual step, and is arguably the heart of the proof. Since (TT) is equal to the summation term in Lemma 4.2 (plus a positive number), and (0) 2 ((T), the summation term is less than or equal to (0)) which is at most (( (3-))22 /T log T). This completes the proof.
'This equivalence is due to our choice of regularizer, as we never need to project w'. "ee Equation for expression of this quantity in terms of the experts' reports and weights.
7

---

4.2 Bounds on w' 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 A
Lemma 4.4. Consider a particular run of Algorithm I
Let Ç be constant such that S
(,T'(w") - for all i,t. Then for every i,t, L, we have
(wi) - ( ! +1) mis S (w S (wx)a-1+
ming wk +1) mes.
Furthermore, if S (1 - a) (we)) for all then for every we have (ut+l)a-1 ja- s (w))a-1+ (m 1)m..
Intuitively, this result states that when the gradient update is small, w ++1 is not too different from wt. Note that the lower bound - that we place on the gradient is not a simple Lipschitz bound w!!
but instead depends w/: this makes the bounds in Lemma 4.4 less straightforward to prove. In particular, we bound each component wf individually, using bounds on the gradient of the loss for all other components and convexity arguments.
Lemma 4.4 can be translated into bounds on each wi and on the change between wi and w
Corollary 4.5. Under the small gradient assumplion, for sufficiently large T we have for all i E [m]. (T) that:
(#1) (w 2 4ny and w 107m
1 1-11(2(a-1)),
(#2) -32( 1 S w/ with < 2( 2(wo)) + 1)77.
defer the proof Corollary 4.5 to Appendix A The key idea for [#1 is to proceed by induction on / on the two sub-statements parallel: so long as (wi) 2 2 4my, we may use the second part of Lemma 4.4 with Ç y to bound (w: (a-++)a-1 in terms of (m:{)== which we can leverage to prove both stteemttteents for 1. #2 then follows from (#T) routine (though nontrivial) algebra.
Armed with the bounds of Corollary 4.5 we are now able to show that under the small gradient assumption, Algorithm T attains vanishing regret.
4.3 Bounding regret under the small gradient assumption
Assume the small gradient assumption. Note that since 4y 2 1, by Corollary 4.5
(11) we have that
t = 77 for all This means that we may apply the bound Lemma 4.2 and in particular we have
1 ( max R(w)- min R( H((w) 17 W.A.
1
m
m 1-a
12 m /2 nv nn In..
=
WEA"
It remains to bound the summation component of the regret bound in Lemma 4.2 the following lemma, which we alluded in Section 4.1 the heart of the proof of Theorem 3.2
To do so, we prove
Lemma 4.6. Fort {0, (0.1...., T}, let
1 p(t) = Σ VL"(w") (w" - w (++1)++ + 19m2?2n(T -) 4y Σ In w/ 4+
Under the small gradient assumption, for sufficiently large T, sp(t) is decreasing function of To prove this claim, consider a particular E [T'] We may write
m
*(1) - p0( 1)
Σ
((wf - w (w") 19m72 + 41 - In w11)
(1)
8

---

and we wish to show that this quantity is negative. In fact, we show that the contribution from every i E [m]] is negative. The key idea is to consider two cases: w V w and w 2 wef- In each case, Corollary 4.5 provides an upper bound on the magnitude of the difference between wf and w If wft! S w then the first and third terms in the summation are positive but small, and are dominated by the middle term. If w 2 w/ 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 (.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 is negative.
Proof. First assume that w have
w I O. Note that by combining (#1) and (#2) of Corollary 4.5
w + ! (2(w 1/7 < Stot.
By the small gradient assumption we have that
(mf w³ w2 (.,''' s Mw w!)
On the other hand, we have
4ryIn wi - In (nt -y In 1 wf+1 w!
(+1 w!)
w
for T large enough. (Here we use that wi / I Suf and that In(1 + x) 2 for x S 8.) Thus, the first and third terms in Equation T are net negative; meanwhile, the second term is also negative, so the expression is negative.
Now assume that wi - -wft1 2 O. Again by the small gradient assumption, we have that - (w]-wtt110+ w,/'),,L'' S ( - w s 2(m +
< 3mm 2
and
4y(In In wn -4yl1 In (1- (1- w wi+t1
s 41 2(m + 1 ()
wi
4 In(1 2(m + 1)m) S - In(1 3mmr) S 16mm7?
2
for T sufficiently large, where in the last step we use that In(1 - z) 2 $ for x > 0 sufficiently small (and we have l 3mapy = 0). Since 16 +-3 3 < 19, the right-hand side of Equation is negative. This concludes the proof.
Corollary 4.7. For sufficiently large T, under the small gradient assumption, the regret of Algorithm at most (240- + 12) m3 (2330))//yyTT//
Proof. We have already bounded the first term in the regret bound in Lemma 4.2 It remains only
to bound the second term. This term is exactly equal to (T)) + 47 Σ In lnw! S (TT), and (P(T S (0)), by Lemma 4.6 We have
m
((0) = 19m2?2nfI'' + 4mz In m I 20m2?2n1
for sufficiently large T. Plugging in y 12n In T and 17 V 12m +003/ concludes the proof.
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 The key lemma is bound on the probability that the small gradient assumption fails by a given margin:

---

Lemma 4.8. For any weight vector w, E (m²) and < 2 0. we have that
P P(o.((w) 2 5] S ne-
(2)
and
P (,L(W) S
5 S mn? C/n Wi
(3)
Note that plugging in Ç (- Y yields a bound of mT + mn²e- on the probability that the
small gradient assumption fails hold. (Since 7 12n In T, this quantity is the order of T-11)
The proof of Lemma 4.8 is the only part of the proof Theorem (32 that uses the calibration property. While we defer the full proof to Appendix A we highlight how the calibration property is used to prove Equation 2 In brief, it is straightforward to show that 0,L(w) S In pj. where J is the
random variable corresponding to the realized outcome 8 Therefore, we have
IP [[0,(w)) 2 c] s P Imp 2 5 = P pp'
Se =
Σ ==1
PP J =
& se9
Σ P sp m/ S { 3=1
$ Σ
P =
S $ S ne ne
j=1
where the last step follows by the calibration property, thus proving Equation
2
Combining Lemma 4.8 with an analysis of our algorithm using the standard regret bound for online mirror descent (Orabona 202T, Theorem 6.8) gives us the following result as a corollary.
Corollary 4.9. The expected total regret of our algorithm conditional on the small gradient assump- tion not holding, times the probability of this event, is at most ((T(5-a)(0-a)-10)
follows that the contribution to expected regret from the case that the small gradient assumption does not hold is Ö(T-"), which is negligible. Together with Corollary 4.7 (which bounds regret under the small gradient assumption), this proves Theorem 3.2 As matter of fact, Theorem 3.2 holds even if experts are only approximately calibrated. As with other details of this section, we refer the reader to Appendix A
5 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 I.Ip. 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 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 fully adversarial setting, the calibration property allows for stronger results.
Another important direction for future work is learning weights for other pooling methods. In particular, because of the close connection between a proper loss function and its associated quasi- arithmetic pool, it is natural to ask for which proper loss functions is possible achieve vanishing regret when learning weights for guasi-arithmetic pooling with respect to the loss function. (Neyman and Roughgarden| 2023] $5) showed that the loss of quasi- arithmetic pool is convex in the experts' weights, and therefore the usual no-regret algorithms (e.g. online gradient descent) guarantee O(vT) regret- so long as the loss function is bounded. In this work, we extended their result to the log loss (with the associated QA pooling method, i.e. logarithmic pooling.) Extending our techniques to other unbounded loss functions is a promising avenue for future exploration.
'Writing out the expression for L(w) and differentiating leaves us with - In p} plus negative term see Equation g
10

---

Acknowledgments and Disclosure of Funding
Funding in direct support of this work: NSF grant DGE-2036197; NSF grant CCF-2006737, and ARO grant W91 IN1111110224
We would like to thank Christian Kroer, Rafael Frongillo, and Bo Waggoner for discussion.
References
Ali E. Abbas. 2009. A Kullback-Leibler View of Linear and Log-Linens Pools. Decision Analysis 6, 1 (3 2009), 25-37. https:://doi.org/10.. /dwca. 1080. 0133
Allard, Comunian, and Philippe Renard. 2012. Probability aggregation methods in geoscience. Mathematical Geosciences 44, 5 (2012), 545-581.
Dirk Bergemann and Stephen Morris. 2019. Information Design: A Unified Perspective. Journal of Economic Literature 57, 2019), 44-95. httpa://doi. 101../.1/1.//1...1111111
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. 2023, When Does Optimizing Proper Loss Yield Calibration? CoRR abs/2305. 18764 (2023). https://doii org/10..//0 48550/
arXiv 230...330..10 18764 arXiv:2305. 18764
Nicolò Cesa-Bianchi and Gábor Lugosi. 2006. Prediction, Learning, and Games.
https:
//dps:://oii //doi
org/10. 1017 /CB/9//0000110589880
Thomas M. Cover. 1991.
Universal Portfolios.
Mathematical Finance 1,
(1991), 1-29.
1111/j 1467-9965. 1991. t.b00002.2...
Thomas M. Cover and Erik Ordentlich. 1996. Universal with side information. IEEE Trans.
Inf. Theory 42, 2 (1996), 348-363.
485708
Shrey Desai and Greg Durrett. 2020. Calibration of Pre-trained Transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (Eds.). Association for Computational Linguistics, 295-302. ntttp::/ddi..rgg: 10. 10w.1/166/vvv/00
emn 1p mai...in.111
Dean P. Foster and Rakesh V. Vohra. 1997. Calibrated Learning and Correlated Equilibrium. Games and Economic Behavior 21, 1 (1997), 40-55. https://ddi..org/11 10. 2006//gmme. 1997.0500
Christian Genest. 1984. A Characterization Theorem for Externally Bayesian Groups. Ann. Statist. 12, 3 (09 1984), 1100-1105. htttps://doi.org// 12t.://11////////01100
Christian Genest and James V. Zidek. 1986. Combining Probability Distributions: A Critique and an
Annotated Bibliography. Statist. Sei. 1, (1986), 114-135. http://www.jsstor org/ stable/ 2245510
Geof H. Givens and Paul J. Roback. 1999. Logarithmic Pooling of Priors Linked by Deterministic Simulation Model. Journal of Computational and Graphical Statistics 8, 3 (1999), 452-478.
http://www. http::wwww...t.................t www.rrorgg/ttbbeeeeeeee.
Elad Hazan. 2021. Introduction to Online Convex Optimization. CoRR abs/ 1909.05207 (2021).
arXiv:1909.05209 http::/arxixn www.aaawwww.a..oaaaaooooooo http://aaaii..orrgb////9... httg://b///99.00999 05207
Dan Hendrycks, Norman Mu, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Laksh- minarayanan. 2020. AugMix: A Simple Data Processing Method Improve Robustness and Uncertainty. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. httpp::/openreview.nee wwtp::iwwwwwe.e..ieeeeeee
S1 S1gmrxHFvB xHFvB

---

Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds Nova DasSarma, Eli Tran-Johnsnn, Scott Johnston, Sheer El Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. 2022. Language Models (Mostly) Know What They Know, CoRR (ss/22007.0522) (2022). https://doi. org/ 10. 4..550/5aaaiv 2207 05221 arXiv:2207.05:. .05221
Christian Kascha and Francesco Ravazzolo, 2008. Combining inflation density forecasts. Working Paper 2008/22. Norges Bank. https://idess www.r. /tt////no////// hooo//opaap//00...... html
Bin Li and Steven C. H. Hoi. 2014, Online portfolio selecttinniiossletoonn A survey. ACM Comput. Surv. 46, (2014), 35:1-35:36. http:::/2ol..rr//0111/////333331
Kenneth C. Lichtendahl, Yael Grushka-Cockayn. Victor Richmond R. Jose, and Robert L. Winkler. 2017. Extremizing and Anti-Extremizing in Bayesian Ensembles of Binary-Event Forecasts. ERN: Forecasting Techniques (Topie) (2017).
Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. 2021. Revisiting the Calibration of Modern Neural Net- works. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 15682-15694. https://proceedingg: 4450033900002466775efffaaa222233
Eric Neyman and Tim Roughgarden. 2023. From Proper Scoring Rules to Max Ftrrmalrraai Aggregation. Operations Research (Jan. 2023). https://doi. org/ 10. www.://pwp...........
Forecast
OpenAl. 2023, GPT-4 Technical Report. CoRR abs/2303.08774 (2023). https://doi.org//0
48550/ar aivv. 2303 2303.08774 arXiv:2303.0877
Francesco Orabona. 2021. A Modern Introduction to Online Learning, CoRR abs/1912.13213 (2021).
1IXVv1191..13213 http: http:p///aii...oog/bbb/11212 19tp//1111.1111
David Poole and Adrian E. Raftery. 2000. Inference for Deterministic Simulation Models: The
Bayesian Melding Approach. J. Amer. Statist. Assoc. 95, 452 (2000), 1244-1255. https
//doi.org/10. 10101000010000100111111111001111 459. 2000. 10474324
Marfa Rufo, Jacinto Martín, and C. Pérez. 2012. Log-Linear Pool Combine Prior Distributions: A Suggestion for a Calibration-Batt Approach. Bayesian Analysis 7 (06 2012), 1-28. https
//doi.org/// 10. 1214/12-BAA
Ville Satopää, Jonathan Baron, Dean Foster, Barbara Mellers, Philip Tetlock, and Lyle Ungar. 2014. Combining multiple probability predictions using simple logit model. International Journal of Forecasting 30 (04 2014), 344-356.
10joo//fooe..o.ocaatttt 201. 20133.9 .99
009
Jaime Sevilla. 2021. When pooling forecasts, use the geometric mean of odds.
https://forum http://fforuo.ffetiiiiooco www.:effeeeeettuiiis....m. org hwtgg//osss/sssee shijcjmnoAACcceL2)) When-pooling forecasts use- the gewmetric mean of odds
Shai Shalev-Shward 2007. Online Learning: Theory, Algorithms, and Applications. Ph. D. Disserta- tion.
Tetlock and D. Gardner. 2015. Superforecastiing: The Art and Science of Prediction. Random House. https: httpps:/bboks..go httpee////booossooglleoooo htt.ee/.ooomooooeesecca555ooo..
Robert L. Winkler. 1981. Combining Probability Distributions from Dependent Information Sources.
Management Science 27, 4 (1981), 479 488. http::/www.jjs jstor wwwgsstaalee/611s...
Julian Zimmert and Yevgeny Seldin. 2021. Tsallis-INF: An Optimal Algorithm for Stochastic and
Adversarial Bandits. J. Mach. Learn. Res. 22 (2021), 28:1-28:49.
http: //jmrr./ org. /
v22 19- mm1
12

---

A Omitted Proofs
Efficiency of Algorithm The only nontrivial step of the algorithm is finding the weight vector satisfying the equation on the last line of the algorithm. To do so, it is first necessary to compute the gradient of the loss. This gradient, given by Equation Bieloow can clearly be computed in time O(mn). After that, it is necessary to find the weight vector w that satisfies the equation on the last line. This can be done efficiently through local search: the goal amounts to find weights (wi...., Wm) w is equal to a target vector (call it v) plus a constant e times the all-ones vector. That is, we need to simultaneously solve the equation wo a--1 = U; + c for all i, with weights that add to 1. (Here, the eù knowns and the w; and are unknowns.)
such that the vector (w]
We start by finding c, by solving the equation ( + c) 1. Such c exists because the left-hand side of this equation is continuous and monotone decreasing, going from infinity to zero as ranges from min; to infinity. We can solve for very efficiently, e.g. with Newton's 's method. Once we know c, we know each w;: we have w; time.
(v3 + c))/(a-1), Thus, Algorithm I takes (mm)
Proof of Lemma 4.4. Fix any f. Note that since the space of possible weights is Am, it is most natural to think of R function from m to IR, / i.e. R.T modulo translation by the all-ones vector (which is orthogonal to A in R'), That is, V (R(w)=
- ((w))=-1 ..... (wm)a=)), where this vector may be thought of as modulo translation by the all-ones vector. Nevertheless, we find convenient to define 0, R.W( == - -w,) We define O,L' (w()) similarly (see Section 4.4).
Define h R.T have coordinates h, == a.R(w") (,O,L'(w"), Per the update rule, have that h4 = R(w++1) mod 7. We have
TE = -ww)) +
DcS
- (wi) no = 0,R(w") 7o5 S h4 S O,R((')
(4)
w
Applying the first and last claims of Lemma A. (below) with a = 1, v = w', K 7o5, and g we have that there exists a unique K such that
m
(-h4 + +) 1)( Σ
and in fact that -ToS S <e mnG. (Equation 4 is relevant here because it is equivalent to the
of !n! S 9 S of + conditions in Lemma A.1 This is also where we use that 17.5 S (1 (1=a)((w()))
" which is equivalent to k S a²uutI.) The significance of this fact is that (-h; + c) 1/(-1) is precisely wit1, since (in Rn) we have that (.... 0.[(w(+1) = h - c for some c, and in particular this must be such that E, wtt1 1 In particular, this means that for all i, we have
= -h; + c S (wf)a-1 + + + ming Wk
1
Mi (w))a-1 + (-1
minng we + 1) mes.
Here, the inequality comes from the left inequality of Equation and the fact that e S ming w MC. If also have that m755 N (1 (w))) then the last claim of Lemma A.1 gives us that
(w = h4 S (w))a-1 + ne + mmc5 = (me() mm (m - 1)mG.
Similarly, we have
Ih n. = (ww)a-1
1 ! + mn.
(w (a(+1)a-1= ----- -hi + c> (w/)a-1_
w!
Lemma A.1. Let -1 < 0 and R.. There is a unique e R such that E,(9, ta =1.
Furthermore, let v E A and k 2 0. Then:
1f of + k for all i, then K..
. If of 2 for all i, then min, v5*
13

---

And if. furthermore, S a²o for all i, then c S mk.
Proof. Observe that Ei + e)2/a is continuous, monotone decreasing function (- min; Di, o0); the range the function on this interval is (0, oo). Therefore, there is a unique E (- min; yi, o6) such that the sum equals 1.
We now prove the first bullet. Since 1//a decreases in a and S of + K, we have that
- +
c) o)
Σ (uf + k c)
Suppose for contradiction that -K. Then of K < 2 for all so
+0
(1s))
Σ 2 =1
This is contradiction, so fact e 2 -.
The first claim of the second bullet is analogous. Since ///aa decreases in x and 2 ug kii, we have that
1/0
1 - cc
+c
(5)
1/3
Suppose for contradiction that for every i. Then of
+c>
us for all so
us
1/a
Σ
U
c
Σ
m 1=
This is contradiction, so in fact
minn ui
We now prove the second claim of the second bullet. To do so, we note the following technical lemma (proof below).
Lemma A.2. For - < < 0 and K. O, the function f(x) (I E/2 + c) 1/a is defined and concave at any value of 0 such that a² za+
K.
Since for general concave function it holds that m inequality follows from Lemma A.2
Dm f(x;)
Σn x.)). the following
1/a
1/a
[(1)
Σ
a
K
+
S m
1
km
+
Vi
(Here we are using the fact that E; 24 = 1.) Now, combining this fact with Equation 5
we have that
1/a
km +c)
21
1
km +
80 c < mK, as desired.
Proof of Lemma A.2 To show that is defined for any z such that a² at1 > need show that + 0 for such values of æ. This is indeed the case:
K
+ c
c22
a²x0 +c= (1 d²)x= +c>c20.
Now show concavity, We have
("(x) 1 1 -a
((1+ 1 1 (x +e)
1/a-2
arr-1
x )²² -((0 +c)
1/a-1
aala - 12 2x x3
-a
x²
14

---

so we wish to show that
(x-
1 x2
K
+
1/a-2
at
+
Ai
x²²
+c)
1/a-1
a(a - 1) 1)xa=2
2x' x
x
xx2
for every a such that x²
a1
2 k. Fix any such a, and let ममبي (so 0 S S a²). We have
a
(1 a)aaaaa ddd2 0 00
(1 - aa +dj² < -a(1 - dd(aaa 1) 2d)
(rearrange terms)
(multiply by x
(a+d)* $ ((1 ((1-d)=))(ad (a(a- - - 2d)
1
(a+ (d+d)2=" V ((1- - (1'- + c)(a(a 1) 10-00 -2d)
(c(a(a - 1) - 2dd) 2 0)
1
((a + d))=-113 $ ((1 d)x² + c)(a(a- 1) 2d)xz=²
(multiply by xa
az +
x x²
x
k +0) a(a 1)---
2k'
(substitute d = KE -
x.3
Note that the fifth line is justified by the fact that c 2 0 and a(a - 1) 2 2d (because a² 2 d and
-a a² 2 d). Now, multiplying both sides by (a k + c) 1/a-2 completes the proof.
Proof of Corollary 4.5. Note that ryy VTm0+oyy and also that 1/ S 1) for all t; we will be using these facts.
To prove (#1), proceed by induction t. In the case of 1, all weights are 1 1/m, the claim holds for sufficiently large T.. Now assume that the claim holds for generic t < T; we show it for ++1.
7. By the small gradient assumption, we may use Lemma 4.4 with Ç (= = By the inductive hypothesis (and the fact that 1/2 I 1)), we may apply the second part of Lemma 4.4:
(w s (wt) + (m + 1)m S ... S (1/m)a-1 + t(m + 1)my S (1/m) (T 1) + +1)
S 3m /T.
mll+a)/2
Since =1 < a O, this means that w 2 2
1 _ (1/(2((-11))
10mm
We also have that
(2/(2(a-11)
4
T 1/2 41py
(10/m)a
ml
for T' sufficiently large, since 1 (#1).
-1 This completes the inductive step, and thus the proof of
To prove (#2), we use the following technical lemma (see below for the proof).
Lemma A.3. Fix x >> 0 and -1 < a < Let f(y) = (a + y))a/a Then for all y > Ix", we have
f(y) < -1
(6)
for all -1 < c for all c S y S 0, we have
fly) x < (1 1/-1
We apply Equation
o to w (m + 1)m, and a = a- 1. This tells us that
wf w ++1 < w/ ((w{) + (m
< 2(w 2- + 1)7y.
15

---

The first step follows by the second part of Lemma 4.4 and the fact that S The second step follows from Equation 6 and uses the fact that r-a 2.
For the other side of (#2), we observe that since by (#1) we have (wf)² 2 4nyy, follows that (w (w) 1)77, and + + my 2 (ww))= Therefore, can apply Equation 7 to 1, and c. = - This tells us that
w/, J ! + 177,
w w++1
! 1 (wt)a-1
- (1)
+ +1) 177
1/(a-1)
= = =6(
(1)
+1) my wt
S 32
This completes the proof.
Proof of Lemma
A.3
For all y > -x we have
f'v)) - [a20 + t)
and
("(y) _ (1-1) ( 4y)l/a-2
a a
so f' is increasing. Thus, for positive values of y we have
(0) < f(u) f()) f(y) - < (1v)
y
y
and for negative values of we have
('()) f(v) f(0)
f(y) xx S (0))
Regardless of whether y is positive or negative, this means that x - f(v) < -)'(((()) -- at-ay
Now, let -1 < c S 0 and suppose that cr S y S O. Since f' is increasing, we have that
f(()) 2 ((x0)) = ((1 1))=)//00-11111 2 (1+
80
f(y) - of (v) v (1 + 1/2 1/
Proof of Lemma 4.8. We first derive an expression for a,[(w) given expert reports p²,... pm" where L(w) is the log loss the logarithmic pool p'(w) (w) of p .p......pp" p. with weights w, and is the realized outcome. We have
(it ) -0,
0,L(w)= = - ln
(pt)am = 0 In
II
0, In
[I k=
F=1 Rm1
Σ Σl= In p/
I (p))
In p3 = [r((w) Impi - Impj.
(8)
Σ 2F
122 ym
"It should be noted that VL(w) is most naturally thought living R' RT (T(1.. ). i.e. m-dimensional space modulo translation by the all-ones vector, since w lives in place that orthogonal to the all-ones vector. As an arbitrary but convenient convention, we define 0; (ww) to be the specific value derived below, and define the small gradient assumption accordingly.
16

---

Equation (2) now follows fairly straightforwardly. Equation 8tells us that d;L(w) - 15-1n -n where is the random variable corresponding to the realized outcome. Therefore, we have
IP [[,L(W) 2 c] Inp
2 {) P
[p's
Se
Σ 5=1
& 55- P pP-=j
P P 121 Se e 9
S Σ
P[j=jllb
S e E S ne
j=1
where the last step follows by the calibration property. This proves Equation (2).
We now prove Equation (3). The proof has similar idea, but is somewhat more technical. We begin by proving the following lemma; we again use the calibration property in the proof.
Lemma A.4. For all q, we have
P Viji
p) S q] S mnq.
Proof. Let J be the random variable corresponding to the index of the outcome that ends up happening. We have
P Paj
pp
S Ei p s = Σ P j
s
jELn
Σ
Σ
P[J=j 1 5
jEIn ie m
Σ
5 P < < Σ Σ 1.g
mmng
jE [m] FE|m]
jE(n) [c(m]
where the fact that P [J= j p3 ك q
$ q follows by the calibration property.
Corollary A.S. For any reports p² ..... pd weight vector w, E [m]] and j E [n]], we have
(p)) we
P
pj(w)
< mng.
Proof. We have
(p))
)
Now, assuming that there is an &succ that for every & we have pt q, the denominator greater than g, in which case we have p) (w) < (pi)", Therefore, if pw()) 2 (p)) it follows that for
every & there is le such that p S q. By Lemma A.4 this happens with probability at most mng.
We now use Corollary A.5 to prove Equation (3). Note that the equation is trivial for Ç < so we assume that ( 2 n. By setting g == we may restate Equation (3) as follows: for any q S 4. any i [m], and any weight vector w,
O.L(w) < nn 1/q
PP
mn²g.
W,
(Note that the condition < is equivalent to Ç (2 n.) We prove this result. From Equation g we have
n
O,L(w) Dp
(w) In (w) - Inp 2 Σ py (w) (w)(s)
17

---

Now, it suffices to show that for each j E [n]], the probability that (,(w) pn I lu Ing is at most mnn: the desired result will then follow by the union bound. By Corollary A.5 have that
w.
for each j we
(p)) ) lnp} S mnq.
IP Py(w)
S
Additionally, we know for a fact that py (w) Iups 2 In pz (since ps (w) 1), so in fact
I max ( In In Inp3)
P (e(w)lpps
S mnn-
remains only to show that max
(p)) In DJ, pp
pz g2/w, then this clearly true,
< q mi
since in that case p) 2 Ing
Now suppose that pj
q//wi, Observe that == In æ decreases on
ar
(0, e 1/:)), ) and that (since q S ( we have q 1/mx S se-1/w Therefore.
(p)) ) In
(g (g) In gt Ing Wy
q
This completes the proof of Equation (3), and thus Lemma 4.8.
The following lemma lower bounds the regret of Algorithm function of 5- Lemma A.6. Consider a run of Algorithm 1. Let Ç be such that -aat-S The total regret is at most o 020000000-000000000----
S S O,L'((')) S for all i,t. w
Proof of Lemma A.6
A.6
We first bound ut for all i, t.. From Lemma 4.4, we have that
(w too- s (wf)a-1+ min: w + +1) ne S (w!)a-1 + 2G.
Here we use that min, wi + 1 S min, and that S min, wi. Therefore, we have that
(wf)a-1 (w:-1) - + Thus, wf 2 (m--o 2(o)) > ((((T))/(-1)) for all i,
m 1m 2C 1) m - 2ÇT.
We now use the standard regret bound for online mirror descent, see e.g. Orabonal 2021 6.8):
Theorem
Regret S max Bu(u w²)
T
Σ
VL [T'((w)
2A
where Bz((:)) is the Bregman divergence of with respect to R, u the optimal (overall loss- minimizing) point, À is constant such that R is X-strongly convex with respect norm of our choice over m,, and I|. is the dual norm of the aforementioned norm.
Note that for any x E Th we have
max (x(V;x) max R(v) - R(x) VR(x) (v x) 5 m 1- vEAm
(min
0-1
V
In the last step, we use the fact that vR(x) = (x a-1 ,..., S - ) (all of these coordinates are positive), so - -VX(x) (1f and add to 1.
(o--1)-v. and that all coordinates of v are non-negative
Therefore, given our bound on wi. we have that this first component of our regret bound 9 at most
!ml-a + m 1 a + 2(T)
5o
ST
0
ÇT (CT))/(-1I)
((T7)(2-0)((-o))
7/
a
Tm
18

---

To bound the second term, we choose to work with the 4 norm. To show that R is X-convex it suffices to show that for all x, y E Am we have
y 2 Ilyll where 4 R the Hessian of R (Shale--Swwartz 2007 Lemma 14) (see also (Oraoona 2021 Theorem 4.3)). Equivalently, we wish to find a À such that
(1 (1-a) Σ
2 y A.
Since x; 2 for all i, the left-hand side at least (1 - a) Ei
1 so -= suffices.
Now, given 0 E IR.h, we have ||0||. maxx:||xx|s| 0 x. In the case of the & primal norm, the dual norm is the largest absolute component of Thus, we have
so (c(TT)/a-a) = =0 - | S oof
Since Nn - 1/2)), we have that the second component our regret bound is most
o
(T. O
TT.T711 1-2 -22-
O (100-
This component dominates our bound on the regret of the first component, in both & and T. This concludes the proof.
Proof of Corollary 4.9
Let Z be the minimum value of Ç such that
c mn 1 (., S for all i,
Note that by Lemma 4.8, we have that
(mn"e & + ne =n==)) 2m
i=1
Let be the constant hidden in the big-O O of Lemma A.6 i.e. a constant (dependent on m, n, and a)) such that
Regret S 112222-0/00-0))0000
Let r(z,T) be the expression on the right-hand side. The small gradient assumption not holding is equivalent to Z >> 12n T, or equivalently, r(Z, T) > r(12n In T, T). The expected regret of our algorithm conditional on the small gradient assumption not holding, times the probability of this event, is therefore at most the expected value of r(Z, 7) conditional on the value being greater than r(12m In T, T), times this probability. This equal to
r(12n In T,T) P > 1n +
P (2()) 2 x] dx
(12a1777
1(n P 2 kn
/. - 1 (1 2m T
Σ 0 -000:/00000000000000000000---0 k=11
as desired. (The first inequality follows by matching the first term with the h = 11 summand and upper-bounding the integral with subsequent summands, noting that r((k: 1)n In T, 2 1.) O
Note that 5-a - 10 < 1-1/2 - 10 = -1. Therefore, the contribution to expected regret from the I-a
case that the small gradient assumption does not hold is Ô(T-1), which is negligible. Together with Corollary 4.7 (which bounds regret under the small gradient assumption), this proves Theorem 3.2.
We now extend Theorem 3.2 by showing that the theorem holds even if experts are only approximately calibrated.
Definition A.7. For T 2 1, we say that expert is r-calibrated for all E A and j E [n]], we have that P [J = =p] S Tpp. We say that IP satisfies the T-approximate calibration property if every expert is r-calibrated.
19

---

Corollary A.8. For any т, Theorem 3.2 holds even if the calibration property is replaced with the T-approximate calibration property.
(Note that the t is subsumed by the big-O notation in Theorem 3.2; Corollary A.8 does not allow
experts to be arbitrarily miscalibrated.)
Technically, Corollary A.8 is corollary of the proof of Theorem 3.2, rather than a corollary of the theorem itself
Proof. We only used the calibration property in the proofs of Equations (2) and (3). In the proof of Equation (2), we used the fact that IP = j pj S e e S e S; the right-hand side now becomes Te-S, and so the right-hand side of Equation (2) changes to Tne- Similarly, in the proof of Equation (3), we use the calibration property the proof Lemma A.4 the right-hand side of the lemma changes 7mnq, and correspondingly Equation (3) changes to rmn?e (/".
Lemma 4.8 is only used in the proof of Corollary where 2m is replaced by 2rm 2 TT. Since is constant, Corollary 4.9 holds verbatim.
L
B D(VT) Lower bound
We show that no OMD algorithm with a constant step size substantially outperforms Algorithm 1. Theorem B.1. For every strictly convex function R: : Am + that is continuously twice differen- tiable at its minimum, and n7 2 0, online mirror descent with regularizer R. and constant step size incurs 22( / TT) 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 (convex) function of w, and similarly for the losses at each time step. We assume that R' (0.5) O; this allows us to assume that w1 = 0.5 and does not affect the proof idea.
is straightforward to check that if Experts I and 2 assign probabilities p and }. respectively, to the correct outcome, then
(1 p)" L'(w)= = ndd + (1 - p)
1-P
In
p
If roles are reversed (they say 1 and respectively) then
p) 1
1 1-p
L'(w) pl-w + - p)
We first prove the regret bound if 7 is small (1 - 1/2.) Consider the following setting: Expert I always reports (50%, 50%): Expert always reports (90%, 10%); and Outcome happens with probability 90% at each time step. It is a matter of simple computation that:
T.' (w) < 2 matter the outcome the value of
. If w 0.4, then (7() $ 0.8.
The first point implics that (w;,) 2 -2nt for all t. follows from the second point that the algorithm will output weights that will result in aggregate probability of less than 80% for values of such that 22p 2 (0(004), i.e. for < (0.4). Each 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 ((1/n) = ((VT).
2n
Fun fact: the technical term for a corollary to proof is a porism. While Algorithm does always have constant step size, does with high probability. The examples that prove Theorem B.I cause ((vTT) regret in the typical case, rather than causing unusually large regret in an atypical case. This makes our comparison of Algorithm to this class fair.
20

---

Now we consider the case in which 7 is large (n 2 vT). 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 lower weight (breaking ties arbitrarily).
We will show that our algorithm incurs {2(n) regret compared to always choosing weight 0.5. Suppose without loss of generality that at given time step Expert is informed (so w 0.5). Observe that
L(w") L(0.5) -00.5 w') ) (0.5) O -w)²)
v1 - P -0.5 w vp vI-p In 1 O((0.5 w))
where p is the probability that Expert 1 assigns the event that happens (so p 0.9 with probability 0.9 and = 0.1 with probability 0.1). 1). This expression is (up to lower order terms) equal to c(0.5-w' p 0.9 and -3c(0.5 w²) if p 0.1, where e 0.55. This means that an expected regret (relative to w 0.5) of 0.6c(0.5 - w²) (up to lower order terms) is incurred.
Let D be such that RS (w) D for all w such that |we 0.5 < T (Such D exists because R is T we just showed that an expected regret
continuously twice differentiable at 0.5.) If Iww 0.5| 2 32
(relative to 0.5) of vT show that | 0.5 2
is incurred. On the other hand, suppose that lw 0.5|
/T We
4D
VT
10
To see this, note that ['(w")) 2 0.5, we have that [R( - R' R'(w")) > 0.5m. We also have that D / w0| > Rt' (w Rt' (w"" )|. so D w wol 2 0.5m) Therefore, /w wol >
2D 2 VT which means that | 0.5 2
/T
2D
4n
This means that an expected regret (relative to w
is incurred on at least half of time steps. Since D constant, it follows that total regret of least ((v is incurred, as desired.
0.5) of Ω
4D
21


Reviews:
[{"review_id": "GhCkPp2n0g", "reviewer": "Reviewer_2zyV", "summary": "The paper studies no-regret learning in the setting of logarithmic pooling of experts with the logarithmic loss. In this setting, there is a set of experts each outputting a distribution $p_i^{t}$ over outcomes in some finite set $Y$. The task of the learner is to output a vector $w^{t}$. An outcome $y$ in $Y$ is then observed and the learner suffers loss $\\sum_i w^{t}_i  \\log p^{t}_i (y)$ where the sum is over the experts. The loss is then compared to the best choice of weights $w$ in hindsight. Under an additional assumption that the expert probabilities are \"calibrated\" (which the paper argues is necessary), the paper presents $\\sqrt{T}$ regret algorithm. Further, the paper is the first to consider regret in the logarithmic pooling setting and to connect calibration of experts to regret in this setting.", "questions": "- It would be very helpful to elaborate the usual setting of learning with the log loss for comparison since that is well established area of online learning and information theory. The reason this would be helpful is that in the usual setting the actions are unrestricted but it turns out to be (essentially) optimal to consider \"linear pooling\". The fact that linear pooling comes up naturally in that setting would be a good constrast and good place to compare linear and logarithmic pooling.  \n- The comment about linear pooling and logarithmic regret needs to be considered a bit more carefully. In the usual notion, the learner does not compete against all convex combinations of experts. In fact, there can be polynomial difference between the two cases.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contributions of the paper in my opinion is the initiation of study of logarithmic pooling + logarithmic loss to the study of online learning. The paper justifies this setting by noting various nice properties this method of aggregation is known to satisfy. Further the relationship of calibration to the regret in this setting is also interesting. It is the key condition under which their algorithm has non-trivial regret.", "weaknesses": "The main issue I have with the setting is that beyond the presentation in terms of pooling, this setting seems like an instance of standard online linear optimization. As the paper notes the main difference here is the apriori unbounded sizes of the loss vectors. Viewed in this light calibration is the same as assuming that the losses are bounded ( ). The issue really is whether this is a priori clear or not. The point that makes me lean towards the fact that the calibration is \"just assuming\" boundedness is that no average notion of calibration (for example calibration on average across time steps) seems to be sufficient (it seems that the counterexample can be modified to be calibrated on average). Thus, the interpretation just as having \"good experts\" is less clear and seems more like assuming bounded losses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these comments. A few points and clarifications:\n\n* We disagree that our setting is an instance of *linear* optimization. The log loss of a forecast is not a linear function of the forecast, nor of the weights that the aggregator assigns to the various experts.\n* We disagree that the calibration property places a bound on the losses of the experts (or of the aggregate forecast). That’s because an expert’s forecast could assign an arbitrarily small probability to some outcome -- and if that outcome happens, then they could realize an arbitrarily large loss. The calibration property does guarantee that the probability of this occurring is small: in particular, that the probability of loss $\\ell$ is only $\\exp(-\\ell)$. The fact that losses in our setting are stochastic, even if bounded in expectation, complicates the analysis and makes it far from obvious that standard learning algorithms for finding the best mixture of forecasters can be successful in our setting.\n* We would conjecture that our results could be adapted to go through for experts that are calibrated on average. The natural notion of calibration-on-average would look something like: when an expert assigns a 1% chance to an outcome, when averaged across time steps it is the case that the probability of the outcome is 1%. (Perhaps on some time steps it is 2% and on others it is 0%, but on average it’s 1%.) It seems that Example 1.1 cannot be adapted to the case of calibrated-on-average experts. For example, if the adversary chooses for an expert to assign $\\exp(-T)$ probability to some outcome, then the probability of that outcome occurring is at most $T \\exp(-T)$, since there are T time steps over which the expert must be calibrated on average. This is up from $\\exp(-T)$ in the case of calibration at each time step, but still very small.\n\nHere are our answers to the two questions:\n\n* Thanks for prompting us to further justify logarithmic pooling. We do so in the global rebuttal (Question 2). To summarize, we believe that logarithmic pooling contrasts favorably to linear pooling in the context of calibrated experts. This is because logarithmic pooling “takes more seriously” confident forecasts from experts. Imagine two calibrated experts and three outcomes. Suppose that Expert 1 has strong evidence against Outcome 1, and so reports (0.04%, 49.98%, 49.98%), and that Expert 2 has strong evidence against Outcome 2, and so reports (49.98%, 0.04%, 49.98%). Accounting for both experts’ evidence would mean placing low probabilities on the first two outcomes and most probability mass on the third outcome. Logarithmic pooling successfully does this, returning (2.7%, 2.7%, 94.6%). By contrast, linear pooling would return (25.01%, 25.01%, 49.98%).\n* Thanks for pointing this out. On lines 152-153, we are referring to the subsection titled “A Mixture Forecaster for Exp-concave Losses” of [Cesa-Bianchi and Lugosi, 2006], specifically Theorem 3.3, which addresses the setting of competing with the best (linear) mixture of forecasters. That section addresses bounded, exp-concave loss functions. The log loss is not bounded, and we cited [Cover, 1991] for the log loss. Upon a closer look, it seems that [Cover, 1991] (cited on line 154) attains logarithmic regret in a slightly different setting (closer to the standard online convex optimization setting that of learning a mixture of experts). Do you know of a source that proves a no-regret guarantee in the prediction with expert advice setting, when choosing weights for a linear pool to compete with the best linear pool in hindsight? If not, and if we cannot find such a source, then we will take care to clarify the difference between our setting and that of [Cover, 1991].\n"}, {"review_id": "m5k7ysR9v9", "reviewer": "Reviewer_RmFD", "summary": "This paper investigates the logarithmic pooling method for minimizing log loss and introduces the OMD algorithm utilizing Tsallis entropy as a regularizer to update weights for the logarithmic pooling method. By assuming calibrated forecasts, the paper demonstrates that the proposed algorithm ensures a sub-linear regret. Additionally, this paper establishes a corresponding lower bound, indicating that their regret bound is optimal in terms of its dependence on the number of time steps $T$.", "questions": "1. How about the efficiency of the algorithm? Can the algorithm be executed efficiently?\n2. Why there is no need to project our decision, as stated in footnote 5?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Learning weights for logarithmic pooling studied in this paper is novel as far as I know, which appears to be a crucial direction, particularly due to its natural alignment with log loss.\n2. The results and methodologies presented in this paper seem to be novel and the techniques used in this paper may be of independent interest to the community.\n3. This paper is well-written. The algorithm is well-motivated, and the theorems presented are rigorous and sound.", "weaknesses": "1. It is important to include a discussion of the relevant literature on online portfolio selection in the related work, as it addresses a similar problem to this paper, namely learning parameters using log loss.\n2. It is worth noting that the lower bound only applies to OMD with a constant step size, which may limit its effectiveness. Additionally, the optimality regarding the number of experts (m) and outcomes (n) should be discussed in this paper.\n3. Providing a more intuitive explanation for the choice of Tsallis entropy as the regularizer would enhance the paper's clarity and value.\n4. This paper can be improved by presenting a detailed example to illustrate the significance of the logarithmic pooling method with log loss.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these comments. We address the comments in the “Weaknesses” and “Questions” sections.\n\nWeaknesses:\n1. Thanks for the suggestion -- we agree, and will take care to do so in the final version, should our paper be accepted. We already cite [Cover, 1991] (“Universal Portfolios”), but that’s just a start. Are there particular papers that you would recommend citing?\n2. We agree that this is a limitation of our work, though we would like to highlight Footnote 3 from our supplement: “While Algorithm 1 does not always have a constant step size, it does so with high probability. The examples that prove [our lower bound] 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 1 to this class [of constant step size OMD algorithms] fair.”\n3. Thanks -- we agree. Here’s a brief intuition for our choice of Tsallis entropy. The natural first online learning algorithm to try for our problem is OMD with the negative entropy regularizer; this is equivalent to Hedge, which is a variant of multiplicative weights. Unfortunately, when attempting to use the negative entropy regularizer, we could not rule out a failure mode in which two experts alternate in making big mistakes (assigning very low probabilities to the eventual outcome) in a way that causes nearly all weight to be assigned to the mistaken expert. For example, Expert 1 makes a big mistake that causes 99% of the weight to be on Expert 2 in the next round. Then, Expert 2 makes a big mistake that causes 99.99999% of the weight to be on Expert 1 in the next round. Then Expert 1 makes a big mistake that causes 99.99999999999999999% of the weight to be on Expert 2 in the next round, and so on. This failure mode is more plausible with the negative entropy regularizer than with Tsallis entropy, because Tsallis entropy is “steeper” near the boundary of the simplex, which makes it difficult for OMD to end up assigning nearly all weight to a single expert. However, we do not have a formal proof that the negative entropy regularizer cannot be made to work.\n4. Thanks -- we would be happy to add an example. Here’s a simple example: consider two experts and two outcomes. Expert 1 reports the distribution (98%, 2%); Expert 2 reports (50%, 50%). With equal weights, the logarithmic pool of these forecasts is (87.5%, 12.5%). The log loss is then 0.134 if Outcome 1 happens and 2.079 if Outcome 2 happens.\n\nQuestions:\n1. Yes, the algorithm is efficient, as we argue below. We can include this argument in the final version.\n\nThe only nontrivial step is finding the weight vector satisfying the equation on the last line of the algorithm. To do so, it is first necessary to compute the gradient of the loss. See Equation (5) in the supplement for a formula for the gradient of the loss, which makes it clear that the gradient can be computed in time $O(mn)$. After that, we need to find the weight vector $\\mathbf{w}$ that satisfies the equation on the last line.\n\nThis can be done efficiently through local search: essentially, the goal is to find weights $(w_1, \\dots, w_m)$ such that the vector $(w_1^{\\alpha - 1}, \\dots, w_m^{\\alpha - 1})$ is equal to a target vector $\\mathbf{v}$ plus a constant $c$ times the all-ones vector. That is, we need to simultaneously solve the equation $w_i^{\\alpha - 1} = v_i + c$ for all $i$, with weights that add up to 1. (Here, the $v_i$ are knowns and the $w_i$ and $c$ are unknowns.)\n\nWe start by finding $c$, by solving the equation $\\sum_i (v_i + c)^{1/(\\alpha - 1)} = 1$. Such a $c$ exists because  the left-hand side of this equation is continuous and monotone decreasing and goes from infinity to zero as $c$ ranges from $-\\min_i v_i$ to infinity. We can solve for $c$ very efficiently, e.g. with Newton’s method. Once we know $c$, we know each $w_i$: we have $w_i = (v_i + c)^{1/(\\alpha - 1)}$. This algorithm thus takes $O(mn)$ time.\n\n2. In general, projecting the weight vector is necessary when there is no weight vector such that the gradient of R at that weight vector is equal to the target vector. However, every vector is attested as the gradient of R somewhere. We prove this in our answer to your previous question by exhibiting an algorithm for finding the weight vector."}, {"review_id": "MRlyODGzdN", "reviewer": "Reviewer_n3Hc", "summary": "Summary of the paper\n====================\n* The prediction setting explored in this work is harder than the usual \"prediction with experts advice\" (henceforth abbreviated PwE) setting (e.g. as in the Cesa-Bianchi and Lugosi book), since the learner is required to reveal the expert weights (w_t) *before* observing the expert advice (adversarially chosen by the environment) and the outcome (in the standard PwE model, the mixture prediction is to be done before observing the outcome but after observing the advice). This is crucial for the lower-bound in Example 1.1.\n* The form of weighted logarithmic pooling considered in this paper to aggregate the advice of the experts (Lines 47-48) is also natural and considered in the previous literature (as minimizing weighted average KL divergence to the expert advice, having external Bayesianality, maintaining log-concavity of densities etc).\n* The algorithm proposed is again efficient and well-studied in the literature; online mirror descent with the Tsallis entropy regularizer (as in Zimmert and Seldin, 2018).\n* To beat the lower-bound (Example 1.1) and achieve sublinear regret, the condition imposed on the adversarial joint-sampling of expert advices and outcome is that the all the experts must be calibrated (for each expert, the conditional probability of the outcome conditioned on that expert's advice must match the advice distribution).\n* With the calibration assumption and an appropriate step-size schedule, OMD+Tsallis is shown to achieve $\\tilde{O}(\\sqrt{T} \\log T)$ regret (for $T \\gg m$).", "questions": "* Lines 66-70 show how forcing the aggregator to predict before seeing the expert forecasts disallows some form of manipulation by the aggregator (mimicking a linear mixture). Could you please elaborate on why such a situation should be disallowed (when using the aggregator for either theoretical or practical purposes)?\n* Could you please provide some discussion on why calibration is still practical in the PwE setting when the experts are learners which are decoupled from the adversarial generation of outcomes (i.e. the expert $i$ has fix the forecast distribution $p^i_t$ at time $t$ before seeing the adversarial outcome $j_t$)?", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The adversarial prediction setting explored in this work is harder than the usual PwE setting. The form of weighted logarithmic pooling considered is well-studied in the literature (especially in the context of combining Bayesian priors) and this work seems to give the first non-trivial online adversarial prediction regret bound for the logarithmic pooling with respect to the the log loss (to the best of my knowledge).\n* The algorithm proposed (OMD with Tsallis regularizer) is efficient and well-studied in the literature.\n* The calibration condition proposed for the experts is extensively studied in the Bayesian inference literature (in the sense that Bayesian posteriors are naturally calibrated).\n* Quite a bit of detail has been provided for the proofs in the main paper, and these are reasonably sound and well-written.", "weaknesses": "* Not much motivation is given for the harder adversarial setting (requiring the aggregator to predict the weights before seeing the expert forecasts).\n* While the calibration condition is well-motivated in the existing literature w.r.t Bayesian posteriors, the authors have not provided sufficient motivation for why it is practical when treating experts as learners (in a prediction-with-expert-advice setting). It may be particularly problematic when the experts are learners/prediction models which are decoupled from the generation of the adversarial outcomes. With the log loss, no-regret online predictors are of course possible even with adversarial outcomes (using the Laplace or Krichevsky-Trofimov estimators for instance, as in the Cesa-Bianchi and Lugosi book Chapter 9), but it may not be very useful to aggregate such no-regret experts with logarithmic pooling.\n* There are no experimental results in the paper, nor are any practical applications discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these comments. A few responses:\n- Regarding the first weakness (and first question), see our response to “Question 3” in the global rebuttal. Briefly, we argue that our goal is to study logarithmic pooling, and by allowing the aggregator to pick weights after seeing forecasts (i.e. allowing the weights to depend on the forecasts), the aggregation method becomes arbitrary, rather than being logarithmic pooling. Our setting is analogous to the well-studied setting of choosing weights for the optimal linear pool (see e.g. [Cesa-Bianchi and Lugosi, 2006, Section 3.3]), but for logarithmic pooling instead of linear pooling.\n- We further justify our modeling choices (the calibration property and logarithmic pooling) in the global rebuttal. Briefly, we argue that the calibration property often holds in practice (e.g. in modern deep neural networks) and so studying prediction with advice from calibrated experts from a theoretical standpoint is well-motivated. We then argue that logarithmic pooling makes particular sense when experts are calibrated, because logarithmic pooling “takes more seriously” confident forecasts from experts, as compared with linear pooling.\n- In response to the second question: in addition to theoretical reasons to expect experts to be calibrated (see e.g. [Foster and Vohra, 1997] or [Blasiok et al., 2023] (“When Does Optimizing a Proper Loss Yield Calibration?”)), in practice we see calibration in a variety of settings. For example, modern deep neural networks are usually calibrated (see the discussion in the global rebuttal). This raises the question: how can we adapt the standard theoretical model of online prediction with expert advice -- which by default gives full power to the adversary -- to model calibrated experts? Our model attempts to do this by still giving the adversary a lot of power while constraining it just enough to guarantee that experts are calibrated."}, {"review_id": "Gg1hhwtfzQ", "reviewer": "Reviewer_XNSv", "summary": "This paper studies the logarithmic pooling method for prediction using expert advice. At each step, $m$ experts report distributions $p^1, p^2, \\ldots, p^m$ over a size-$n$ domain. The goal is to make predictions with a vanishing regret in terms of the log loss.\n\nThe usual logarithmic pooling returns an aggregated distribution $p^*$ such that each $p^*(j)$ is proportional to $\\prod_{i=1}^m[p^i(j)]^{1/m}$, the geometric mean of the predicted probabilities. This paper considers a generalization in which the exponent for each expert is replaced by $w_1, w_2, \\ldots, w_m$ that sum up to 1 (instead of $1/m$ identically), and the goal is to learn the right set of weights to achieve a low regret.\n\nFormally, each round of the prediction proceeds as follows: First, algorithm selects weights. Then, adversary chooses the experts' forecasts and the outcome subject to a *calibration* condition. The two steps are in sequential order, so that the forecaster is prevented from outputting an arbitrary distribution.\n\nThe main result of the paper (Theorem 3.2) states that the regret can be upper bounded by roughly $m^{3/2}n\\sqrt{T}\\log T$ in the $T \\gg m, n$ regime. The algorithm uses online mirror descent with the Tsallis entropy regularizer.", "questions": "- The setting assumes that the adversary chooses the forecasts and outcome after seeing the weights selected by the algorithm. If both parties act simultaneously, would the setting become significantly easier? (In particular, the obstacle of Example 1.1 still seems to be there?)\n- What if the weights don't need to sum up to 1? Would that change the expressivity of the aggregation? (Multiplying $w_1, \\ldots, w_m$ by the same factor seems to give a different distribution.)\n- Lines 63--70 argue that we need to keep the algorithm from seeing the experts' advice, so that the algorithm cannot \"output an essentially arbitrary function of the forecasts\". What would be the practical motivation/justification of this choice?", "limitations": "The main limitations are the assumptions made regarding the setting (e.g., the adversarial choices of outcomes and forecasts must satisfy the calibration condition). These have been clearly pointed out in the abstract and introduction and, the assumptions are formally stated in the paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem setting is quite natural and well-motivated. The authors did a good job in explaining why certain assumptions are necessary by providing illustrative examples. While the solution is based on online mirror descent, the analysis of the algorithm requires several new ideas that seem to be non-trivial and of independent interest.", "weaknesses": "- The scope of the setting is limited to logarithmic pooling and the log loss.\n- The tightness of the bound is unclear; an $\\Omega(\\sqrt{T})$ lower bound is proved for a restricted class of algorithms, while the polynomial dependence on $m$ and $n$ might be sub-optimal.\n- Several aspects of the setting don't seem sufficiently convincing; see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these comments. In response to the questions:\n- Question 1: Our interpretation of this question is: what would happen if we changed our setting so that the aggregation algorithm chooses weights at the same time as the adversary chooses the probability distribution, such that neither has knowledge of the other’s choice? In that case, we would seemingly end up with a game in which optimal play may involve randomized strategies. You are correct that without the calibration property, the obstacle of Example 1.1 remains. (The adversary chooses which expert reports the extreme report at random, and then the bad outcome of the example happens with probability 50%.) It would be interesting to analyze this game in the presence of the calibration property, though somewhat less standard. The setting would be less adversarial than ours, and we are able to exhibit a no-regret algorithm even in our (more adversarial) setting.\n- Question 2: Yes -- by allowing weights that do not sum to 1, new aggregate forecasts may be obtained.  Logarithmic pooling with weights adding to a constant other than 1 is attested in the literature; see e.g. [Satopaa et al., 2013] (“Combining multiple probability predictions using a simple logit model”). We conjecture that our techniques can be extended to find weights for logarithmic pooling in this broader setting, though doing so appears to be nontrivial.\n- Question 3: See our response to (3.) in the global rebuttal. Briefly, we argue that our goal is to study logarithmic pooling, and by allowing the aggregator to pick weights after seeing forecasts (i.e. allowing the weights to depend on the forecasts), the aggregation method becomes arbitrary, rather than being logarithmic pooling. Our setting is analogous to the well-studied setting of choosing weights for the optimal linear pool (see e.g. [Cesa-Bianchi and Lugosi, 2006, Section 3.3]), but for logarithmic pooling instead of linear pooling."}]

Author rebuttal:
We would like to thank all reviewers for their thoughtful comments. In this global rebuttal, we will address three recurring questions:

1. Some reviewers were interested in further justification of the calibration property.
2. Some reviewers were interested in further justification of using logarithmic pooling to aggregate experts’ forecasts, especially in light of the fact that low regret is attainable with a simple weighted average (as we mention in lines 153-154).
3. Some reviewers asked for further explanation of lines 63-70, in which we argue that at each time step, the algorithm should choose the experts’ weights without seeing the forecasts.

In the paper, we note some theoretical and empirical considerations that justify logarithmic pooling (lines 27-43) and present the calibration property as a natural condition under which there is hope for low regret in the face of challenges presented by requiring logarithmic pooling. In this rebuttal, we present an additional and orthogonal justification: we first justify the calibration property and then justify logarithmic pooling as a particularly sensible aggregation method for calibrated experts. To briefly summarize:

1. In practice, modern deep neural networks are calibrated. Our work addresses the aggregation of such networks’ outputs from a theoretical standpoint by balancing the desire for worst-case guarantees (as is typical for theory) with practical observations about neural networks’ performance.
2. Logarithmic pooling makes sense *in particular* when experts are calibrated, because it takes confident predictions seriously, especially as compared with linear pooling.
3. Learning optimal weights for linear pooling is a well-studied question. Our argument in favor of logarithmic pooling suggests addressing the same question for logarithmic pooling. However, if the weights to a logarithmic pool are allowed to depend on the forecasts, then the aggregation method is no longer a logarithmic pool; it can be an arbitrary function.

Elaborating point by point:

1. In lines 85-89, we give two theoretical justifications for the calibration property. Here we note another justification: in practice, modern deep neural networks are well-calibrated when trained on a proper loss function such as log loss. This is true for a variety of tasks, including image classification and language modeling. (See e.g. [Blasiok et al., 2023] (“When Does Optimizing a Proper Loss Yield Calibration?”) or [Kadavath et al., 2022] ("Language Models (Mostly) Know What They Know").)

Now, suppose that we wish to use an ensemble of off-the-shelf neural networks for some prediction or classification task. We trust the networks to be calibrated, but we may not know beforehand which networks have the highest levels of expertise. (As an extreme example, suppose there are a thousand classes, all equally likely. A network that always assigns 100% probability to the correct class has more expertise than a network that always assigns a uniform distribution over the classes, even though both are calibrated.) Learning to aggregate these networks’ forecasts is well-motivated and nontrivial. The standard fully adversarial setting is one reasonable (and well-trodden) theoretical approach to this problem. However, integrating the empirical observation that neural networks are well-calibrated into the theoretical analysis yields a new, well-motivated setting with the potential for stronger results than are possible without assuming calibration.

2. In lines 27-43, we gave a few theoretical and empirical justifications for using logarithmic pooling. We believe that logarithmic pooling makes *particular* sense when the experts are calibrated. Intuitively, this is because the logarithmic pool pulls the aggregate toward more confident forecasts. We give one example in lines 32-33: 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 roughly (3%, 97%). This makes more sense than the linear pool (i.e. arithmetic average), which would be roughly (25%, 75%): if Expert 1 is calibrated (as we have assumed and justified above), then a (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. An aggregate of very strong evidence for Outcome 2 with no evidence either way ought to still be fairly strongly in favor of Outcome 2. (Indeed, there is a natural interpretation of logarithmic pooling in terms of averaging experts’ Bayesian *evidence*; see [Neyman and Roughgarden, 2023].)

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 assign nearly all probability to Outcome 3. Linear pooling does not accomplish this; meanwhile, logarithmic pooling returns roughly (2.7%, 2.7%, 94.6%), which is much more sensible.

3. The problem of choosing weights for a *linear* pool to compete with the best weights in hindsight is well-studied (see e.g. [Cesa-Bianchi and Lugosi, 2006, Section 3.3]). Above, we justified the logarithmic pool as a better alternative to linear pooling in the case of calibrated experts. It is then natural to study the analogous problem for logarithmic pooling in place of linear pooling; this is the problem we study. If the algorithm’s weights were allowed to depend on the experts’ forecasts, the resulting probability distribution (as a function of experts’ forecasts) might look nothing like logarithmic pooling. If the algorithm is to compete with the benchmark of a “best possible logarithmic pool”, it makes sense to restrict the algorithm to (weighted) logarithmic pools of the experts’ reports.

Meta-review: This paper considers online learning with logarithmic pooling and introduces the first sqrt(T) regret bound. The authors are encouraged to take into account the promised changes (in particular clarification regarding relationship to online linear optimization).
Decision: Accept (poster)