Sample Complexity of Forecast Aggregation
Authors: Tao Lin
Yiling Chen
Venue: NeurIPS 2023 spotlight (2023)
Keywords: information aggregation
sample complexity
distribution learning
Bayesian forecast aggregation
TL;DR: We give the first sample complexity result for the classical Bayesian forecast aggregation problem.

Abstract: We consider a Bayesian forecast aggregation model where $n$ experts, after observing private signals about an unknown binary event, report their posterior beliefs about the event to a principal, who then aggregates the reports into a single prediction for the event. The signals of the experts and the outcome of the event follow a joint distribution that is unknown to the principal, but the principal has access to i.i.d. "samples" from the distribution, where each sample is a tuple of the experts' reports (not signals) and the realization of the event. Using these samples, the principal aims to find an $\varepsilon$-approximately optimal aggregator, where optimality is measured in terms of the expected squared distance between the aggregated prediction and the realization of the event. We show that the sample complexity of this problem is at least $\tilde \Omega(m^{n-2} / \varepsilon)$ for arbitrary discrete distributions, where $m$ is the size of each expert's signal space.  This sample complexity grows exponentially in the number of experts $n$. But, if the experts' signals are independent conditioned on the realization of the event, then the sample complexity is significantly reduced, to $\tilde O(1 / \varepsilon^2)$, which does not depend on $n$. Our results can be generalized to non-binary events.  The proof of our results uses a reduction from the distribution learning problem and reveals the fact that forecast aggregation is almost as difficult as distribution learning.

Sample Complexity of Forecast A Aggregation
Tao Lin Harvard University Cambridge, MA 02138 tlinβg. harvard. edu
Yiling Chen
Harvard University Cambridge, MA 02138 yilingâseas harvard.
Abstract
We consider a Bayesian forecast aggregation model where n experts, after observ- ing private signals about unknown binary event, report their posterior beliefs about the event to a principal, who then aggregates the reports into single predic- tion for the event. The signals of the experts and the outcome of the event follow a joint distribution that is unknown to the principal. but the principal has access i...d "samples" from the distribution, where each sample tuple of the ex- perts' reports (not signals) and the realization of the event. Using these samples, the principal aims find an e-approximately optimal aggregator, where optimal- ity is measured in terms of the expected squared distance between the aggregated prediction and the realization of the event. We show that the sample complexity of this problem is least f(m"~2/8 for arbitrary discrete distributions, where is the size of each expert's signal space. This sample complexity grows expo- nentially the number of experts n. But, the experts' signals are independent conditioned on the realization of the event, then the sample complexity is signif- icantly reduced, to ((1/²),, which does not depend on n. Our results can be generalized to non-binary events. The proof of our results uses a reduction from the distribution learning problem and reveals the fact that forecast aggregation is almost as difficult as distribution learning.
Introduction
Suppose you want to know whether will rain tomorrow. A Google search on "weather" returns 40% probability of raining. The weather forecasting app your phone shows 85%. And one of your friends, who is an expert in meteorology, predicts 65%. How do you aggregate these different predictions into single, accurate prediction? This problem is called forecast forecast aggregation or forecast combination 77. 16. 45). It has innumerable applications in fields ranging from economics, statistics, operations research, machine learning, decision theory, and of course, climate science.
straightforward solution forecast aggregation to take the (unweighted) average all experts' forecasts. Simple it is, unweighted average performs surprisingly well in practice, observed by many forecast aggregation works from 1960s to 2020s (c.g., 17. 38, 35, 30, [6. 45, 34I). Natu- rally, when past data of expert forecasts and event outcomes (e.g., historical weather forecasts and outcomes) are available, one may hope to leverage on such data to learn more accurate aggregators. While adjusting the weights of experts in averaging according to their individual historical accuracy has led to improved accuracy for the aggregated prediction [49], interestingly, more sophisticated data-driven methods [23] 35 49 were often outperformed by the unweighted average. The dom- inance of simple aggregators over more sophisticated data-driven methods is observed so often in empirical applications that it is termed "the forecast combination puzzle" 44, p.428).
There are many potential explanations for the forecast combination puzzle
4
23
15
In some
scenarios, the past events are different from the future events in fundamental ways (c.g., geopolitical
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

forecasting) and hence past data may not be informative in predicting the future. Another widely accepted conjecture is that the amount of past data is not large enough for a data-intensive method to perform well. Indeed, the sample sizes in many empirical forecast aggregation works are small under today's 's "big-data" standard (24 in [27]. 69 in [42), 87 dd. 100 in (3)). However, there are aggregation settings where future events are arguably similar to past events and we do have abundant data - for instance, the forecasting of weather, stock prices [21]]. and some forecasting competitions on Kaggldf Such settings are well-suited for data-driven methods. It is hence tempting to ask how many data are needed for data-driven aggregators to achieve high accuracy in these settings.
In this paper, we initiate the study of sample complexity of forecast aggregation, building upon a standard Bayesian forecasting model (37. 48, 24]. In this model, there are n experts who ob- serve private signals about an unknown binary event and make posterior predictions about the event. The experts' signals and the event are jointly distributed according to some underlying unknown distribution (information structure) P. which determines the optimal way to aggregate the experts' predictions. With sample access to the unknown distribution P, we ask the following question:
How many samples do we need to approximately learn the optimal aggregator?
Our model favors the use of data-driven aggregation methods because historical tasks are i.i.d. as future tasks. We show that however, even in this benign model, optimal aggregation in general needs exponentially many samples. One may thus expect that data-driven methods can hardly perform well in more realistic and non-i.id. scenarios. Nevertheless, for some special, yet interesting, families of information structures, the sample complexity of forecast aggregation is significantly lower.
Main results (1) If P can be an arbitrary discrete distribution, then at least ((m"~2/s) samples are needed, and Omm" /E²) samples are sufficient, to learn an E-optimal aggregator with high proba- bility, where m is the number of signals an expert can possibly observe (2) If the experts' signals are conditionally independent, then the sample complexity is exponentially reduced and surprisingly does not depend on the number of experts or the number of signals: ((1/²²) samples are sufficient, and (11/)) samples are necessary, to learn an e-optimal aggregator with high probability.
Main techniques The main technical part of our paper is to prove the ((m""2/E) lower bound on the sample complexity of forecast aggregation for the general case, via a reduction from the distribution learning problem. It is known that learning discrete distribution with support size |S] in total variation distance requires ?((SS//?) samples. By reducing distribution learning to forecast aggregation, we obtain the lower bound on the sample complexity of the latter problem. This reduction highly nontrivial. To do this reduction we define new distribution learning problem that is different from the one in the literature, which is of independent interest. This reduction also reveals an interesting fact: learning aggregate optimally on some distribution is almost as difficult as learning the distribution itself. This is little surprising because one might initially think that aggregation should be casier than distribution learning we show that this is not the case.
Structure of the paper We discuss related works in Section [.1 Section introduces our model. Section 3 includes some preliminaries, including the distribution learning problem, which we will use in the proof. Section the sample complexity for general distributions. Section focuses 2 summarizes how our results can be generalized to
on the conditional independence case. Section non-binary (multi-outcome) events. Section concludes and discusses future directions.
1.1 Related Works
Data-driven aggregation Data-driven approaches to forecast aggregation date back to perhaps the first paper on forecast aggregation 7 and have been standard practice in the literature (see, e.g., surveys [IG. 45) and more recent works [51] 42 4. 47, 22 40)). Many of these works focus on specific weighted average aggregators like linear pooling (weighted arithmetic mean) (51)] and logarithumic pooling (normalized weighted geometric mcan) [42, 40), and the goal is to estimate the optimal weights from data. However, those weighted average aggregators are not necessarily the
httpp://www kaggle. wwt.c/oo//c//eeee forecastin accuracy "The Ó(-) and (2(-) notations omit logarithmic factors.

---

optimal (Bayesian) aggregator unless the underlying information structure satisfies some strict con- ditions (e.g,, experts' forecasts are equal to the true probability of the event plus normally distributed noises [88 ). Our work aims to understand the sample complexity of Bayesian aggregation, namely how many samples are needed to approximate the Bayesian aggregator.
Our work is closely related to recent work 4 on Bayesian aggregation via online learning. For the
case of conditionally independent experts, M shows that the Bayesian aggregator can be approxi-
mated with E = Ó VT. regret. By an online-to-batch conversion, this implics a T = Ō [ sample complexity upper bound for the batch learning setting, Our paper studies the batch learning setting. For the conditional independence case, we obtain an improved bound of (²)).
Robust forecast aggregation Recent works on "robust forecast aggregation" 22 study information aggregation problems where the principal does not know the underlying informa- tion structure. They take worst-case approach, assuming that the information structure is chosen [2 39 or a de- generate maximin aggregator that solely relies random expert's 's opinion [1& 3] In contrast, assume sample access to the unknown information structure. Our sample complexity approach is orthogonal and complementary to the robust forecast aggregation approach.
39.
18 3
also
adversarially. This often leads to negative results: e.g., bad approximation ratio
Sample complexity of mechanism design Our work may remind the reader of long line of research on the sample complexity of revenue maximization in mechanism design (e.g.. [17 20, 36
19 5. 11
29. 10 25, 50, 281). In particular, (28) gives general framework to bound the sample complexity for mechanism design problems that satisfy a "strong monotonicity" property, but this property not satisfied by our forecast aggregation problem. A key observation from this line of works is that the number of samples needed to learn an s-optimal auction for n 2 1 independent bidders is increasing in n, because when there are more bidders, although we can obtain higher revenue, the optimal auction benchmark is also improved. We see similar phenomenon that the sample complexity of forecast aggregation increases with the number of experts in the general case. but not in the case where experts are conditionally independent.
Model
2.1 Forecast Aggregation
There are n 2 experts and one principal. The principal wants predict the probability that
binary event w E Ω = 1) happens (w = 1), based on information provided by the experts. For example, w may represent whether it will rain tomorrow. We present binary events simplify notations. All our results can be generalized to multi-outcome events with [|2] > 2 (see Section 6). We also refer to w as "the state of the world". Each expert 1, ....... n observes some private signal 8; E S; that is correlated with w, where S; denotes the space of all possible signals of expert i. We assume for now that S; is finite, with size |S,| = m. We relax this assumption in Section where we consider conditionally independent signals. Let S = S] X ... x S, be the joint signal space of all experts: S m". Let be a distribution over S Z2 namely, a joint distribution of signals = (81,... .8)) and event w. Since the space S x Ω is discrete, we can use P(-) to denote the probability: P(s.w) w) = w]]. Signals of different experts can be correlated conditioned on w. We assume that each expert i knows the marginal joint distribution of their own signal and w, w)) Neither any expert nor the principal knows the entire distribution P. Each expert i reports to the principal a forecast (or prediction) r; for the event w, which is equal to the conditional probability of w = 1 given their signal $
P(w=1)P(ss w=1) ri = P(w = 1 s:) = Poo=
We note that r; depends on s; and P. but not on w or other experts' signals s.i. Let r (ri,..., rm) [0. 1j denote the reports (joint report) of all experts. We sometimes use r to
*One may wonder whether the experts are willing to report r. = P(w = 1:s:) trahffully. This can be guaranteed by proper scoring rule. For example, we can reward each expert the Brier score C' - Ir. w/ after seeing the realization of w [9]. Each expert maximizes its expected reward by reporting its helief truthfully.
3

---

denote the reports of all experts except i. The principal aggregates the experts' reports T into sin- gle forecast fr) using some aggregation function. or aggregator, f: [0, 1]" [0, 1]. We measure the performance of an aggregator by the mean squared loss:
(f( = Ep (1 w|
(2)
The notation Er[:] makes it explicit that the expectation is over the random draw of (s,w) P followed by letting r; = P(w 8t). We omit P and write E[|] when it is clear from the context.
Let f be the optimal aggregator with respect to P, which minimizes (f()): argmin Lp( = argmin EP [p[[ - wl*]
-
[[0.1]--10.1]
We have the following characterization of f" and Lp(f): f is equal to the Bayesian aggregator, which computes the posterior probability of w given all the reports r = (f1...., .n). And the difference between the loss of f and the loss of f* is equal to their expected squared difference.
Lemma 2.1. The optimal aggregator f and any aggregator f satisfy:
[*(r) = P(w = r). for almost every r. Lp(f) - Lf( = ( (r)
An aggregator f s-optimal (with respect to P) if Lf(f) S Lr(f*)+e. By Lemma 2. this is equivalent to Ep [I](r) [+)](r I e. For an s-optimal f. we also say s s-approximates f*. Definition 2.2. An aggregator E-optimal (with respect P) Ep Ep [If(r) (r) S..
Discussion the benchmark f Our benchmark, the Bayesian aggregator f", is common in the forecast aggregation literature (e.g., (27 26 45). It is stronger than the typical "best expert" benchmark in no-regret learning (e.g., [13 22 but weaker than the "omniscient" aggregator that P(w = 1 s). If there is one-to-one mapping between signals s and reports r, then fomni and f are the same. Otherwise, fomni could be much stronger than f* and an e-approximation to fomni using experts' reports only is not always possible In contrast, an E-approximation to f" is always achievable (in fact, achieved by f" itself). The difference between f" and fomni is known as the difference between "aggregating forecasts" and "aggregating information sets" in the literature (77 p.198-199) (26, p.168-169) [45, p.143].
has access the experts' signals: fomni (8)
2.2 Sample Complexity of Forecast Aggregation
The principal has access to T' i.i.d. samples of forecasts and event realizations drawn from the un- derlying unknown distribution P:
Sr (r ("))),.,,, (rr(),w(()) )) (s(0) (()) P. 1.0 P(w (
(4)
Here, we implicitly regard P as a distribution over (r,w) instead of (s, The principal uses samples Sy to learn an aggregator = f in order to approximate f*. Our main question is:
How many samples are necessary and sufficient for finding an e-optimal aggregator f (with probability at least 1 8 over the random draw samples)?
The answer the above question depends on the family of distributions we interested in. Let P denote family of distributions over S x Ω. It could be the set of all distributions over S x Ω, or in Section 5 we will only consider distributions where the signals are independent conditioned on w. We define the sample complexity of forecast aggregation, with respect to P, formally:
Definition 2.3. The sample complexity of forecast aggregation (with respect to P) the minimum
function (:p(,)) -) of E, 5 (0, 1). such that: Tf > T (E, 8), then for any distribution P E P, with probability least 8 over the random draw of samples Sr from P (and over the randomness of the learning procedure if is randomized), we can obtain an aggregator = ssr satisfying -
They give an XOR example where w = $1 2 Sp. $1 and 82 are i.idd Uniform(O, 1} distributed. The experts always report r. = 0.5, fomui famui(s1,, = w. (r1, 0.5, so L (fommi) 00bu but Lr(")) 0.25 O. No aggregator that uses experts' reports only do better than f*.
"This has been noted by 22. 4 39].

---

The principal is assumed to know the family of distributions P but not the specific distribution P P. There should be least two different distributions in P. Otherwise, the principal knows what the distribution is and there is no need for learning.
3 Preliminaries
In this section, we briefly introduce some notions that will be used in our analysis of the sample complexity of forecast aggregation, including some definitions of distances between distributions, the distribution learning problem, and the distinguishing distributions problem.
Distances between distributions We recall two distance metrics for discrete distributions: the total variation distance and the (squared) Hellinger distance.
Definition 3.1. Let D1, D2 be two distributions on a discrete space X.
The total variation distance between D1 and D2 is drv (D,,D)) = 1/2 Ezex - D2(x))
The squared Hellinger distance between D1 and D2 is di D2) Ex (VDi(z) D2(xz) 1 -xEE (D(())D2(1).
The total variation distance has the following well-known property that upper bounds the difference between the expected values of a fuunction on two distributions:
Fact 3.2. For any function h X [0, 1}. [E h(x)
En Ea-D h(x)] S drv D2).
In Appendix give some properties of the Hellinger distance that will be used in the proofs.
Distribution learning in total variation distance Our analysis of the sample complexity of the forecast aggregation problem will leverage the sample complexity of another learning problem: learning discrete distributions in total variation distance. We review this problem below.
Let D be family of distributions over X. The sample complexity of learning distributions in D within total variation distance is the minimum function T3 (E, 5), such that: if T Z TBV (c, 8), then for any distribution D E D, with probability at least 1 ô ô over the random draw of T samples from D.
obtain (from the T samples) distribution D such that drv (D, D) S.. Let Danl be the set of all distributions over X. Then, THY (e, = O( ( /5). In particular, the upper bound can be achieved by using the empirical estimate e² Demp (which is the uniform distribution over the T samples). The lower bound holds regardless of what learning algorithm is used.
Proposition 3.3 (e.g., 12
Distinguishing distributions Another learning problem that we will leverage on is the problem of distinguishing (Iwo) distributions: given samples from a distribution randomly chosen from (D1, D2). we are to guess whether the samples are from D1 or D2. The sample complexity of distinguishing distributions is characterized by the squared Hellinger distance. is known that least T = 52( (D..) log }) samples are needed to distinguish two distributions with probability
least 1 8. See Appendix A for formal statement of this result.
4 Sample Complexity for General Distributions
In this section we characterize the sample complexity of forecast aggregation for general distribu- tions P. We give exponential (in the number of experts, n) upper bound and exponential lower bound on the sample complexity, as follows:
Theorem 4.1. Let Pan be the set of all distributions over S x Q, with |S| m.. Suppose > 2. The sample complexity of forecast aggregation with respect to Pall is
O mm m 1og(1/6)) 2 (E, 2 2 m R- (log
(5)
This theorem is for 2 2. When there is only one expert (n 1), there is no need to learn to aggregate because the optimal "aggregator" f simply outputs the forecast given by the only expert: (*(r1) P(w (r]) P(w = 1[81) = =ri- The sample complexity is 0 in this case.
5

---

There is gap in the dependency on in the upper bound and the lower bound in Theorem 4.1 We conjecture that the tight dependency on should be (so the lower bound tight). See Section for a detailed discussion of this conjecture, where we show that the dependency on e in the upper bound can be improved to for a large family of distributions.
4.1 Proof of the Upper Bound
In this subsection we prove the O( (== (0="+lor(//0) upper bound Theorem This is a direct
corollary of the distribution learning result introduced in Section R
We regard as distribution over r and w instead of over and w. Then Pis discrete distribution
with support size at most 2m" because each possible report r; E [0, 1] corresponds to some discrete signal 8; in S,. Let Pemp be the empirical distribution of reports and event realizations: Pemp with probability least - ô over the random draw of T O 2m + samples, we have drv(Pemp. P) I E. According to
Uniform (v((), (w())., ), ..... (r(T), w(D)) By Proposition
Fact and by the definition of (f),), we have: for any aggregator f: [0, 1)m - 10,
Pom (f- (p)-)((]]- |
Pemp [1((r) wl - (r((s(r) - w| -
S drv Poomps P) S E.
Therefore, if we pick the empirically optimal aggregator femp argmin, P (f), we get
Lp(feup) S L Pamp (Femp) te S L
which means that femp is 2e-optimal aggregator for P.
4.2 Proof of the Lower Bound
In this subsection we prove the 22 (m mm=== lower bound in Theorem 41 The main idea is reduction from the distribution learning problem (defined in Section 3 for specific family D of distributions over the joint signal space S = Sj x ...... x Sn. We construct a corresponding family of distributions P {PD D 'D3 for the forecast aggregation problem, such that, if we can obtain an e-optimal aggregator for Pp, then we can convert f into a distribution á such that (Tv D) S (VE). We then prove that learning within total variation distance sTV = O(VE) requires Ω m log 1116) 2 m mm===+++((//)))) samples. This gives the sample complexity lower bound for the forecast aggregation problem for P (and hence Pan).
viv
=
We will need family of distributions 'D that satisfies the following three properties:
Definition 4.2. We say a family of distributions DD satisfies
1. B- -niiformlly bounded, if: D(s) 1a
B
Ys VD E D, where B 2 1 is constant.
2. same marginal across distributions, if: for any D, D' E D, any any 8; S, D(s:) D'(s:).
distinct marginals across signals, if: for any D E D, any any 8; # s S, D(x:) # D(s)).
How do we construct the family P? For each distribution E DD we construct distribution Pp as follows: the marginal distribution of w is Uniform 1}. i.e., PD(w 0) = PD(w = =1) conditioning
0, the joint signal is uniformly distributed: PD(s w 0) [s] 1
Vs E S: conditioning on w 1, the joint signal is distributed according to D: Pp(s w 1)
D(s), Vs S. The family P is {Pp D DJ.
We show that if we can obtain s-optimal aggregators for distributions in P, then we can learn the distributions in D within total variation distance (1 + B)² VE, and thus the sample complexity of the former is lower bounded by the sample complexity of the latter:
Lemma 4.3. Let 'D be a family of distributions that satisfies the three properties in Definition Let P (PD D D) be defined above. Then, Tp (e,E)) 2 TTV ((1 ((I+B)2VE VE, 8).

---

Proof sketch of Lemma [.3 The full proof is in Appendix E.1 the definition of Pp. by Bayes' rule, we have
We give sketch here. According to
Pa(w ()
2 Po(elw=1)
((s)
(6)
PP 2
+D(e)
The "distinct marginals across signals" property Definition 4.2 ensures that there is a one-to-one mapping between signal 8; and report rÜ = PD(w = 1 s:), and hence a one-to-one mapping between joint signal s and joint report r. So, the Bayesian aggregator, f satisfies (r) Pp(w
1 l|r) = (n = 1|8)
D(a)
This gives
T/m"+D(a
D(s) = 1 (() m (-)
Suppose we have obtained an e-optimal aggregator for Pn, E.p - ( S E, then we convert f into ń by letting D(s)= = m
f(r) 1-f(r)
The total variation distance between and is:
drv D) = Σ
D(s) - D(s)
1 m
f(r) (r) 1-f"(r)
(8)
2
1-f(r)
SES
.ES
The "B-uniformly bounded property in Definition 4.2 ensures ((s) = 0 (1) which has two
consequences: (1) PD(s) = ) (2) (r) = 0(1, which implies 1-f(rr
f(r)
(((r)
I- =
((I((r) due Lipschitz property of the function - for x O()). These two conse- quences imply
dIv(D, - 0 ( 1 m (f(r) - (+)) = o Σ (
#ES
#ES
= =O(B[(((r)) f (+)]l) Jensen's incquality
-V(V))
So, obtain (D. S ((VE) B).
There is a subtlety, however: In the distribution learning problem we are given samples from D, which are signals (8(0) 1 We need to convert them into the corresponding reports (r(()) }/=1 as
the samples for the forecast aggregation problem. To do this we need to know Pp or D, which we do not know. So, we make use of the "same marginal across distributions" property Definition 4.2
here: because all the distributions D E DD have the same marginal probability D(s,) = D'(s;) (but possibly different joint probabilities ((s) D'ss),, we are able to compute the report
PD(w= =
(()) (=p(s(/w==0+++ (x (==1)
((e
+((())))
separately for each expert without knowing D. since know what the family D is. This allows
us to reduce the distribution learning problem for 'D to the forecast aggregation problem for P.
Then, find family of distributions D that satisfies the three properties in Definition and requires many samples to learn.
Proposition 4.4. There exists a family of distributions DD that satisfies the three properties in Defini-
tion 4.2 (with B = e + 1)) and requires TT (ETV, 8) 02( mn +log((1/8)) samples to learn.
The above sample complexity is smaller than the 22( 1(15)-)og(1/6)) lower bound in Proposition 3.3 because we are restricting to a smaller set of distributions than the set of all distributions over S. The proof of Proposition 4.4 is analogous textbook proof of Proposition 3.3 which uses reductions
cāv
from the distinguishing distributions problem. See details Appendix
Finishing the proof of Theorem 4.1 By Lemma and Proposition 44 plugging in ērv
(1+ + 3 with B = + 1. we obtain the lower bound on the sample complexity of forecast aggregation for P (and hence for Pan):
T) 2 TTV ((1 B)² Ve, 8) 20""
24log(1/8) ((()))))V3))
2 2(m" 2 2
7

---

5 Sample Complexity for Conditionally Independent Distributions
Srove that learning s-optimal aggregators for all discrete distributions needs exponentially many samples. As shown in the proof, this large sample complexity is because the experts' signals can be arbitrarily correlated conditioned on the event w. Accurate estimation of such correlation requires many samples. So, in this section we restrict attentions to the case where the experts' signals are conditionally independent. O log + samples in this case, which does not depend
turns out that an e-optimal aggregator can be learned using only on n. The assumption of discrete signal space can be relaxed here. We also investigate two special and interesting families of conditionally independent distributions that admit an even smaller sample complexity of O log ().
5.1 General Conditionally Independent Distributions
Let P be a conditionally independent distributions over S x Q2 namely, P(s () = II= P(s, (w) for all s S, for w {0. 1). Here, St can be continuous space, in which case, P(- w) represents a density function. We introduce some additional notations. Let p = P(w = 1) be the prior
probability of w 1. For technical convenience we assume p (0, 1). Define
P(w=l) E (0, +o0). - P(w=0)
(9)
We will be working with ratios like T-r. " and " "r a lot in this section. We will use the following characterization of the optimal aggregator f for conditionally independent distributions:
Lemma 5.1 (88). For conditionally independent distribution P. given signals s = (s:) with corresponding reports = (r:)=-1 where r; P(( 1[s;), the posterior probability of w is:
(r( P(w = 1 r) P(w 1)
(10)
I I-re
14p"
(Define = 0f
1-m r4 +00.)
Lemma 5. iippies that one way to learn f* is to simply learn the value of p. If we can learn p with then we can learn p=-1 with accuracy vē and obtain an f that is e-close to f for every possible input r [0, However, by standard concentration inequalities, learning P with accuracy AA requires Ō(z²)
accuracy LE
pe samples, which is larger than the ((}) bound we will prove. The key is that we do not actually need f(r) to be close to f (r) for every r E [0, 1]2: we only need the expectation B[lj(r)- [+)) S 8. This allows us prove smaller sample complexity bound, using a pseudo-dimensing argument.
The main result of this section is that the sample complexity of forecast aggregation with respect to all conditionally independent distributions is between 52(2 log 3) and ( log +):
Theorem 5.2. Let Pand be the set of all conditionally independent distributions over S St Suppose 2 2. The sample complexity of forecast aggregation with respect to Pind is
0 ( log 2 2 Tp.md (5, 2 2(2 log l).
(11)
We provide the main ideas of the proof of Theorem 5.2 here. The upper bound O log d is corollary of our theorem for multi-outcome events (Theorem((..).. so we only give a sketch here. We note that, according to Lemma 5. the optimal aggregator has the form (r(r)
1+ IE
We consider the class of aggregators FF {1 (r) 1+00 I [ associated with J
parameterized by
0 E +oo). The class of loss functions G [9--; : (r, = If has pseudo-dimension Pdim(g) = O(1) By the known result (e.g.. (1 that the mneudo-dimension gives a sample complexity upper bound on the uniform convergence of a class of functions, we conclude that the empirically optimal aggregator in F must be O(E)-optimal on the true distribution (with probability at least - 6). given O 1 (Pdim(G) log 1 + log 1)) 0 1 log 1.) samples.
We prove the 2 log 1) lower bound by reduction from the distinguishing distributions problem (introduced in Section 3). We construct two conditionally independent distributions p1, p2 over
8

---

the space 02 x S that differ by (P), p= has prior (w = 1) 0.5 - 0 + o and pa has prior (2 1) = 0.5 O
- =()) in squared Hellinger distance. Specifically, P!
O the conditional distributions of each signal, (s (w) and (s ww. differ by 0 in
squared Hellinger distance; taking the product of signals, (' (w) and p w) differ by O(e).
The distinguishing distributions problem asks: given I' samples from either pl or P tell which distribution the samples come from. We show that, if we can solve the forecast aggregation problem.
namely, s-approximate (r) 1+p T. - then we can estimate P with accuracy 0 0((5)
and hence distinguish p and p2. But distinguishing pa and pa requires 9 PTT log ()) =
2 [ log () samples. This gives the lower bound we claimed. See details in Appendix F.1
5.2 Strongly and Weakly Informative Experts
While the sample complexity of forecast aggregation for general conditionally independent distribu- tions is O log )g). under further assumptions this bound can be improved. In partieular, we find two special yet natural families of conditionally independent distributions that admit OC log }) sample complexity. In these two cases, the experts are either "very informative" or "very non- informative". Roughly speaking, an expert is "very informative" the conditional distributions of the expert's signal under event w 0 and w = 1 are significantly different, so the expert's prediction ri is away from the prior p. An expert is "very non-informative" if the opposite is true. Intuitively, an expert being informative should help aggregation and hence reduce the sample complexity. In- terestingly though, we show that even if the experts are non-informative the sample complexity of forecast aggregation can also be reduced. See details in Appendix B
6 Extension: Multi-Outcome Events
Our main results regarding the sample complexity of forecast aggregation for binary events (The- orems 41 and 5.2) can be generalized to multi-outcome events with SS2 2. We prove that: for
general distributions, the sample complexity is (0(m") = Ω m +log(1/0)) < Tp(e, <
O [5/mm +log 1/6)(1 = Ō [81m")
x2 ); for conditionally independent distributions, the sample complex- [ log (52
=² ity is ((-) a(d L log ) S (e, S ( log 1 + + log +) )( See Ap-
pendix forr details.
7 Conclusion and Discussion
In this work, showed an exponential gap between the sample complexity of forecast aggregation for general distributions, δg m=))), ), and conditionally independent distributions, (( This gap is due to the need of estimating the conditional correlation between experts in the general case, which is not needed in the conditional independence case. Notably, the bound Ö for conditionally independent distributions does not depend on the number of experts.
We discuss the dependency of the sample complexity on and other directions for future works:
The dependency E An open question left by our work is the dependency of the sample com- plexity on the parameter e. We conjecture that the tight dependency should be (so our lower bounds are tight). This is supported by the following evidence:
Theorem 7.1. For the case of [Ω]] = 2 and for general distributions, if the distribution P has a c.
minimum joint probability min (w)) S P(s,w) > m for some c O, then the sample complexity of forecast aggregation is at most O( mm (n log m + log })) = Ô nm
In particular, this theorem can be applied to distributions that are close to uniform, where P(s, w)) s SKX 2m giving bound of Ö am"" Notably, the set of distributions we constructed in the proof of the Ω m &
lower bound in Theorem 4.1 are also close to uniform. This means that
"This bound has better dependency but worse on n than the O(m²) bound in Theorem 4.

---

dlose-to-unifors distributions have a tight sample complexity bound of the form O (in.m) ) not
@ f(nm)) ). Moreover, since close-to-unife distributions are the "most difficult" distributions to learn in the distribution learning problem, is likely that they are also the most difficult distributions for the forecast aggregation problem, and therefore the tight sample complexity of forecast aggrega-
tion should be determined by the sample complexity for those distributions, which is O f(n.m)
Other future directions
The middle ground between fully correlated experts and conditionally independent experis: An example is the partial evidence model in [4]. Applying [4] results, one show that the sample
complexity of forecast aggregation in the partial evidence model is at most Ó n | Giving a lower bound for the partial evidence model and exploring other intermediate models is open.
Weaker benchmark: Since the Bayesian aggregator needs exponentially many samples to ap- proximate, can we find weaker yet meaningful benchmark with small sample complexity?
Samples vs experts: In reality, obtaining samples of experts' historical forecasts can difficult, while recruiting experts is easy. Can we achieve better aggregation by recruiting more experts instead collecting more samples? How many experts do we need?
Eliciting more information: Previous works information elicitation and aggregation have noticed that better aggregation can achieved by eliciting more information than agents' own predictions. for example, also eliciting each agent's 's prediction about other agents' predictions (e.g.. 41, 47 31, 14).. One can ask whether and how eliciting more information can help to reduce the sample complexity of information aggregation.
Continuous distributions: In our model the random variable w to be predicted is discrete. One study setting where is continuous random variable and the experts report, e.g., the means of their posterior beliefs about w. The results for continuous random variables might be very different from the results in this work.
Other loss functions: We focused on the squared loss E [I)(r)) - w| due to its popularity in machine learning problems and its useful property that the difference between the squared losses of any aggregator and the optimal aggregator is equal to their expected squared differ- ence (Lemma 2. Alternatively, one consider other loss functions like the logarithmic loss E|w log(s(r)) + (1 -w) log(1 (r)() and the absolute loss (rl [w]- There might be some technical challenges in the analysis of sample complexity for those loss functions, though: e.g..
the logarithmic loss can be unbounded [4. 40) and the absolute loss does not enjoy a property
like Lemma
Acknowledgments and Disclosure of Funding
We would like to thank Yannai Gonczarowski, Ariel Procaccia, Milind Tambe, David Parkes, Bo Waggoner, Rafael Frongillo, Grant Schoenebeck, Yuqing Kong, and anonymous reviewers for their helpful comments. This research is based upon work supported in part by the National Science Foundation under grants no. IIS-2007887 and no. 115-2147187.
References
[1] Martin Anthony and Peter L. Bartlett, Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1 edition, November 1999.
[2] Itai Arieli, Yakov Babichenko, and Rann Smorodinsky. Robust forecast aggregation. Proceedings of the National Academy of Sciences, 115(52), December 2018.
[3] Itai Arieli, Yakov Babichenko, Inbal Talgam-Cohen, and Konstantin Zabarnyi. Universally Robust Infor- mation Aggregation for Binary Decisions. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 118 118-116 118, London United Kingdom, July 2023, ACM.
[4] Yakov Babichenko and Dan Garber. Learning Optimal Forecast Aggregation in Partial Evidence Environ- ments, Mathematics of Operations Research, 46(2):228 661, May 2021.
'I particular, 4 studies an online learning setting with logarithmic loss. Their regret bound can be con- verted sample complexity bound by online-to- bathhhhhhhhhhooocooocooooooaahah conversion and the Pinsker's inequality.
10

---

[5] Maria-Florinn F Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mecha- nism design. Advances Neural Information Processing Systems, 29, 2016.
[6] Jonathan Baron, Barbara A. Mellers, Philip E. Tetlock, Eric Stone, and Lyle H. Ungar. Two Reasons Make Aggregated Probability Forecasts More Extreme. Decision Analysis, 11(2):133 145, June 2014.
[7] John M. Bates and Clive W. J. Granger. The Combination of Forecasts. Journal of the Operational Research Sociery, 20(4):451-46) December 1969.
[8] Robert F. Bordley. A Multiplicative Formula for Aggregating Probability Assessments. Management Science, 28(10): 137-1148, 1982. Publisher: INFORMS.
[9] Glean W. Brier. Verification of Forecasts Expressed in Terms of Probability. Monthly Weather Review, 78(1):1-3, January 1950.
[10] Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi Item Mechanisms without Item- Independence: Learnabiiity via Robustness. In Proceedings of the 21st ACM Conference Economics and Computation, pages 715-761, Virtual Event Hungary, July 2020. ACM.
[11] Yang Cai and Constantinos Daskalakis. Learning Multi-Item Auctions with (or without) Samples. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 516-527, Berkeley, CA, October 2017. IEEE.
[12] Clément L. Canonne. A short note on learning discrete distributions, 2020.
[13] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, Cambridge, 2006.
[14] Yi-Chun Chen, Manuel Mueller-Frank, and Mallesh Pai. The Wisdom of the Crowd and Higher-Order Beliefs. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 450-450, London United Kingdom, July 2023. ACM.
[15] Gerda Claeskens, Jan R. Magnus, Andrey L. Vasnev, and Wendun Wang. The forecast combination puzzle: simple theoretical explanation. International Journal of Forecasting, 32(3):754-762, July 2016.
[16] Robert Clemen. Combining forecasts: review and annotated bibliography. International Journal of Forecasting, 5(4):559-583, January 1989.
[17] Richard Colc and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the 46th Amnual ACM Symposium on Theory of Computing STOC '44 pages 243-252, New York, New York, 2014. ACM Press.
[18] Henrique De Oliveira, Yuhta Ishii, and Xiao Lin. Robust Merging of Information. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 341-342, Budapest Hungary, July 2021.
ACM.
[19] Nikhil Devanur, Zhiyi Huang, and Mhristos-Alexandrr Psomas. The sample complexity of auctions with side information. In Proceedings of the forty-eighth annual ACM symposium on Theory of Comput- ing, pages 426-439, Cambridge MA USA, June 2016. ACM.
[20] Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. Revenue maximization with a single samplc. Games and Economic Behavior, 91:318-333, May 2015.
[21] R. Glen Donaldson and Mark Kamstra. Forecast combining with neural networks. Journal of Forecasting, 15(1):49 61, January 1996.
[22] Rafacl Frongillo, Robert Gomez, Anish Thilagar, and Bo Waggoner. Efficient Competitions and Online Learning with Strategic Forecasters. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 479-496, Budapest Hungary, July 2021. ACM.
[23] Véronique Genre, Geoff Kenny, Aidan Meyler, and Allan Timmermann. Combining expert forecasts: Can anything beat the simple average? International Journal of Forecasting, (9(1):188-121,Jaam 2013.
[24] John Geweke and Charles Whiteman. Chapter Bayesian Forecasting, In Handbook of Economic Fore- casting, volume 1, pages 3-80. Elsevier, 2006.
[25] Yannai A. Gonczarowski and S. Matthew Weinberg. The Sample Complexity of Up-to-c Multi- dimensional Revenue Maximization. Journal of the ACM, 68(3):1-22 182, March 2021.
11

---

[26] Clive W. J. Granger. Invited review combining forecasts- -weenty years later. Journal of Forecasting. 8(3):167-173, July 1989.
[27] Clive W. J. Granger and Ramu Ramanathan. Improved methods of combining forecasts. Journal of Forecasting, 122:19772 April 1984.
[28] Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypothe- on product distributions: Auctions, prophet inequalities, and pandora's problem. In Conference on Learning Theory, pages 2248-2288. PMLR, 2021.
[29] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-parameter rev- enue maximization. Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing STOC 2019, pages 662-673, Phoenix, AZ, USA, 2019. ACM Press.
[30] Sunil Gupta and Peter C. Wilton. Combination of Forecasts: An Extension. Management Science, 33(3):356-372, 1987. Publisher: INFORMS.
[31] Yuqing Kong. Yunqi Li, Yubo Zhang, Zhihuan Huang, and Jinzhao Wu. Eliciting Thinking Hierarchy without a Prior. In Advances in Neural Information Processing Systems, volume 35, pages 13329-13344 Curran Associates, Inc., 2022.
[32]
Jasper Lee. Lecture 11: Distinguishing (discrete) distributions, 2020.
[33] Jasper Lee. Lecture 12: Learning Discrete Distribations, 2020.
[34] Spyros Makridakis, Evangelos Spiliotis, and Vassilios Assimakopoulos. The M4 Competition: 100,000 time series and 61 forecasting methods. International Journal of Forecasting, 36(1):54-74, January 2020.
[35] Spyros Makridakis and Robert L. Winkler. Averages of Forecasts: Some Empirical Results. Management Science, (9(9))987-999) September 1983.
[36] Jamie H Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. Ad- vancey in Neural Information Processing Systems, 28, 2015.
[37] Peter A. Morris. Decision Analysis Expert Use. Management Science, 2009): 1974. Publisher: INFORMS.
[38] Paul Newbold and Clive W. J. Granger. Experience with Forccasting Univariate Time Series and the Combination of Forecasts. Journal of the Royal Statistical Society. Series A (Generul), 137(2):131-146, 1974.
[39] Eric Neyman and Tim Roughgarden, Are You Smarter Than a Random Expert? The Robust Aggregation of Substitutable Signals. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 990-1012, Boulder CO USA. July 2022. ACM.
[40] Eric Neyman and Tim Roughgarden. No-regret learning with unbounded losses: The case of logarithmic pooling, arXiv preprint 2 2022.
[41] Dražen Prelec, H. Sebastian Scung, and John McCoy. A solution to the single-question crowd wisdom problem. Nature, 541(7638):532-533 -335,,,,55,,5 January 2017.
[42] Ville A. Satopää, Jonathan Baron. Dean P. Foster, Barbara Mellers, Philip E. Tetlock, and Lyle Ungar. Combining multiple probability predictions using a simple logit model. International Journal of Forecasting, 30(2):344-356 3566, April 2014.
[43] Jeremy Smith and Kenneth F. Wallis. A Simple Explanation of the Forecast Combination Puzzle. Oxford Bulletin of Economics and Statistics, 71(3):331-2 1-531, June 2009.
[44] James H. Stock and Mark W. Watson. Combination forecasts of output growth in a seven-country data set. Journal of Forecasting. 2356)-405-430, September 2004.
[45] Allan Timmermann. Chapter 4 Forecast Combinations. In Handbook of Economic Forecasting, volume 1, pages 135-196. Elsevier, 2006.
[46] Alexandre B. Tsybakov. Introduction to nonparanetric estimation. Springer series in statistics. Springer, New York: London, 2009. OCLC: ocn300399286.
[47] Juntao Wang, Yang Liu, and Yiling Chen. Forecast Aggregation via Peer Prediction. Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, 11):131-142, October 2021.
12

---

[48] Robert L. Winkler. Combining Probability Distributions from Dependent Information Sources. Manage- ment Science, 2784):479-488, 1981. Publisher: INFORMS.
[49] Robert I.. Winkler and Spyros Makridakis. The Combination of Forecasts, Journal of the Royal Statistical Society, Series A (General), 146(2):150, 1983.
[50] Chunxue Yang and Xiaohui Bei. Learning Optimal Auctions with Correlated Valuations from Samples. In Proceedings the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11716-11726. PMLR, July 2021.
[51] Yuhong Yang. Combining Forecasting Procedures: Some Theoretical Results, Econometric Theory. 20(1):176-222, 2004. Publisher: Cambridge University Press.
13

---

A Additional Preliminaries
A.1 Properties of Hellinger Distance
We review some useful properties of the Hellinger distance. First, the Hellinger distance gives upper bounds on the total variation distance:
Fact A.1 (e.g., Lemma 2.3 in (46)).
dIv & (2d
1 (D,, 2 (1 -D,((1,. (This inequality implies the first one.)
Second, we will use the following lemma to upper bound the squared Hellinger distance between two distributions that are close to each other:
Lemma A.2. Let D1 and D2 be two distributions on X satisfying 1 S Then, (D, D2) s 2=²
Da(a) (m)
<1+ Ve X.
Proof. By definition,
(Di D2)
Σ (VDi(s)-VDa(t))
-
- Di(0) (1-v
Di(0)
De(a)
2
(i(r)
DEX
If 1 - s < D2(a)
< 1, then we have (1 -
Dr(x)
2
- - (1-VI-
s) 5(1 (1-(1- (1-s)) = If
1
Di(z)
1 + e 2 (a(
> 1, then we have (1
D2(x)
S (v1+ ((++)) 1)² = = These
(x)
Di(z)
two cases together imply
D2) S
2 -
Σ TE
Third, we will use a property of the Hellinger distance between distributions defined product space. Suppose D1 and D2 are two distributions over a product space x y. They can be de- composed into the marginal distribution of E X and the conditional distribution of y V given x, namely, Dı (x, y) = (x)) De (y]æ)) and D2(x, y) = (x) D2.tte (y/ar) Then, the squared Hellinger distance between D1 and D2 satisfies the following:
Lemma A.3. (2,, < (D1,,, D2.x) + max dfi (D D2y(z). In particular, i and y independent, then (D,, D2) s (D D2.x) d (D1. D2u)-
Proof. By definition,
da(D1, = - Σ Σ
V D((z,))
DEX
= 1 Σ
(1, Σ
V Di.t (x))
FEX
yEyy
Σ
(2) +
Σ (i. (1) (1- E v (1lp) ( D2 De (2)lz)
FEX
TEX
DEY
di (Di,,, D2n) +
Σ
(x) (D..ll D2.2(t))
DEN
S (Di,s (2,) +
D D1. (x) max da (Dille D2.11o) ZE
x
(1 D2,2) + 1. max df (Di.glzv D2.vlu)
x
where the last inequality is because Exex / D1)
(D,, D2.x) S 1.
14

---

Finally, let D&T denote the distribution of T i.id. samples from D, namely, the product of T inde- pendent D's. We have the following lemma that relates di (DDT, D with (D1, D2):
Lemma A.4 (e.g..
32 (H - 1- (D - (D,, D2).
A.2
Distinguishing Distributions
Let D1, D2 be two distributions over discrete space X. A distribution D; is chosen uniformly at random from {Di, D2}. Then, we are given T' samples from D; and want to guess whether the distribution is D, or D2. is known that at least
Q [DD log 5) samples are needed to guess correctly with probability at least 1 - 5, no matter how we guess. Formally:
Lemma A.5 (e.g., (32)). Let E {1,2} be the index of the distribution we guess based on the samples. The probability of making mistake when distinguishing D1 and D2 using T samples, namely Pr[j + = 1 Príj + fili= 1I + Prli # iili = 2}. is at least:
PrIj + 1) 2 2 (D,
Pr[j # d (D.. " 2 - 4TTR (2),,, assuming (
The second item implies that, in order to achieve Príj D2) log 1 48'
S 8. we must have T Z
We provide proof of this lemma for completeness:
Proof. Let D and D denote the distributions of i..dd samples from D1 and D2, respectively. The draw of T samples from D1 D2 equivalent the draw of one sample from D or DT Given one sample from D or D the probability of making mistake when guessing the distribution is at least:
Pr[j * 1
Pr[j = i= 1] + Pr(p = 21)
2
Prij 1 i-
2 i P
1
i 21) [ppr[11 = - - 131)
2
=
2
by Fact 3.2
drv d OT (
(12)
2
We then upper bound (D T) in two ways, which will prove the two items of the lemma, respectively. First, according to first item A. we have
drv D & V2d ,
By Lemma A.4
dn( D2T S vTdu D2). The above two inequalities give dTv D S (n D2). This proves the first item of the lemma.
Second, according to the second item of Fact A. and Lemma A.4 we have
1- 1Gd DE 2 (1 (D )) (1 (D), 2T
Since 1 (D DT = (1 + dD DE dD D) S 2(1
(D D&T)) )), we have
1 1- DT D > -1- Dz)) (.))
1 di
15

---

Plugging into 12, we get
Prij + 7 (1- D2)) 2
When (Di D2) < 1 2 we use the inequality x こ e 2x for 0 < x < 1 to conclude that
Pr[j + 2 (e- (D)
> (D).
B Special Cases: Strongly and Weakly Informative Experts
In this section we investigate two special families of conditionally independent distributions that admit O log }) sample complexity, which is smaller than the O log 24 bound for general conditionally independent distributions. In these two cases, the (signals of) experts are either "very informative" or "very non-informative".
Definition B.1. Let E oo] be a parameter. For an expert i, we say its signal E St is
stronngly informative if either P(a,w==)
P( w=l) 1 147 holds. 2 1 + or ((a
p(s,(um0)
I
7-weakly informative if ト S
Pla:ke=]) S1+7.
P(ac(w=))
An expert is y-strongly (or 7-weakly) informative if all of its signals in S; are 7-strongly (or 7-
weakly) informative
signal s; being y-stronglyy (or y-weakly) informative implies that its corresponding report r; will be "y-away from" (or "y-close to") the prior = P(w 1), in the "1-x and _ ratio form. Specifically, if 8; is y-strongly informative, then from Equation i we have 1-p
P( P( 1 2 (1 7)p or S st.p
(13)
As r gets larger, a y-strongly informative signal (expert) is more informative for predicting whether or 0. This would make aggregation casier. If is w-weklly informative, then:
1 S 1- 1 (1+7)p
(14)
As gets smaller, a w-weally informative signal (expert) is less informative for predicting w, but in this case their report rú will be close to the prior p. which allows us estimate the p -=1 term in the better. Those are some intuitions why both strongly
optimal aggregator (r) 1+p- II I_m.
and weakly informative signals can reduce the sample complexity of forecast aggregation.
Formally, for y-strongly informative experts with not-too-small 7 we have the following result:
Theorem B.2. n 2 32 3olog² 2 and all experts are y-strongly informative with 14> 2 8 2 log 2 then the sample complexity of forecast aggregation is S O cm log 5 +
1 log 8 0 log 4
We remark that the conditions of the theorem, n 2 32 log 2 and 1 2 8/2 2 log 2 are easier to be
12 2.
satisfied when the number of experts increases, if the informativeness parameter of each expert constant or does not decrease with n (which we believe is reasonable assumption given that experts are independent of each other). Also, if y is fixed or increasing, then as increases the sample complexity decreases.
The proof of Theorem B.2 is in Appendix G.I Roughly speaking, we divide each expert's signal set [=)
into two sets, S and S.: signals that are more likely to occur under 1 (i.e., P(e. W=
> +
and under 0 (i.e., P(s.|u=1)
P(s.l==)) S + If the realized is 1, then may expect to see Ω [17-" n)
more S! signals than the S signals from the n experts, because the probabilities of these two types
of signals differ by 22 17-) for each expert. If w is 0 then one may expect to see more S.¹ signals
than the S7 signals. So, by checking which type of signals are more we can tell whether = 0 or
We note that expert can be neither y-stongyly informative nor w-weakly informative for any 7.
16

---

1. To tell whether signal belongs to S or S we compare the corresponding report I-n. with (namely, 1-r 2 (1 + 7)p = s E E and " i-r; I ! = 8 SP), where p is estimated with accuracy I4y using ( pa p )a log 8) samples. Dealing with the case of p < separately, we obtain the bound O em ب2 log
1
log })-
For 7-weakly informative experts with small ,, we have:
Theorem B.3. If all experts are y-weakly informative with 7 1, then the sample complexity of forecast aggregation is S min {o( = log f), O log } which is O log if = (
The O log 28 term in the sample complexity follows from the result for general conditionally independent distributions (Theorem 5.2). The 0 log })) term is proved in Appendix G.2 We give the rough idea here using 7 = 1 as an example. The proof relies the observation that [[II= I-r, w 0] p". Since experts weakly informative, each of their reports I-m. around P in the range 1 P, + 7)p S P (1 + pp]- Taking the product, we have Ih= TL ,e""", which is in bounded range. This allows to Chernoff bound to I-n,
argue that the p" (or p==!) term in the optimal aggregator (r) = 1+ IT. Amr can be esti-
Pt_ The mated, with (ve) accuracy, using only O (VET= log })) = O log }) samples of I T-r. aggregator using the estimate 10-1.f(m) 1+p
turns out to be Ofs)-optimal.
C Extension: Multi-Outcome Events
In this section we generalize our model from binary events to multi-outcome events. The event space now becomes Ω (1, 2. ... [ with [R]] 2. The joint distribution of event E Ω and experts' signals 8 = (s:) E S is still denoted by P. which belongs to some class of distributions P. The size of each expert's signal space is still assumed to be |S, m < +o for general distributions and can be infinite for conditionally independent distributions (where $1...., Sn are independent conditioned on w). After observing signal 8,, expert reports its posterior belief of the event given 8;, which is T; = (ray)sen where Tij = P(w j s.)). An aggregator now is a vector-valued function f = (fy) that maps the joint report r (ra) T = (Fijly to a probability distribution (r) over St where (r( is the aggregated predicted probability for w j. We assume fs(r) 2 0 and Ejeo (r) = The definition of the (expected) loss an aggregator f becomes:
Lp(f) = Ep
Σ [l((r)) 1[ =
1
(15)
JER
is easy to see that the optimal aggregator f argmin, Lr(f) the multi-outcome case still the Bayesian aggregator (this is generalization of Lemma 2.1)
f (ff) Jea,
(r( P(w = (r)
(16)
and the difference between the losses of f and f satisfies
Lp(f) [pff)) Ep
Σ [r(r) - (r)
(17)
jen
So, an s-optimal aggregator f is an aggregator that satisfies Ep
- (7)))
Using T TP(e, 8) samples ((r()) (")) from P, the principal wants to find e-optimal aggregator with probability at least 1 6, for any distribution P in a class P. We give lower bounds and upper bounds on the sample complexity:
Theorem C.1.
The sample complexity of forecast aggregation for multi-outcome events is: Hog((1/)) Hlgg11)))
For the class P of general distributions: 20
< TP((s,))
0 11/m Hlmm++og(1/0)
For the class Pind of conditionally independent distributions: 2og
log 1 < (e 5
O( [2]] log [0] log 1 + 3 log t).
17

---

C.1 Proof of Theorem C11
Before proving the theorem, we note that the loss of any aggregator f satisfying fr(r) 2 0 and Ejen f)(r)= 1 bounded by [0, 2]:
- Σ (f((r) - 1/w = 51 - Σ
(f(r)) 1w= ا S 1+ Σ
f((r) = 2. (18)
JEG
JEN
JEG
Similarly,
0 0 -(b(r)- 2
(19)
JEN
C.1.1 Lower Bounds
The lower bounds directly follow from the lower bounds for the binary case (Theorem and Theorem 5.2) because the binary case is a special case of the multi-outcome case. Specifically, we can regard any binary event distribution
multi-outcome distribution that puts probability only on outcomes [1,2] S Ω. If we can learn an e-optimal aggregator for the multi-outcome case: E[E,en ( 17 (r) < E, then this aggregator satisfies
Σ
(s((r) (()) se
(E(1.2)
-()) +1(1+ 111- f((r)) - (1 - (1-)1 = R22))((0) - se
= - -
So, the aggregator (i() is an 5-optimal aggregator for the binary case.
C.1.2 Upper Bounds
General distributions: the O [2 +og((()) upper bound. The proof for general distributions 2² in the multi-outcome case is the same the proof for general distributions in the binary case (Sec- tion [, except for three differences: (1) P (regarded as a distribution over reports r and event w) now is discrete distribution with support size most [[0mm= (2) the loss (f(r) w² [0, in the binary case is replaced by the loss Eje (fr(r) - [W = .i]² E [0, 2] in the multi-outcome case; (3) the in the binary case is replaced by because the loss is now upper bounded by 2. Thus, the the binary case becomes O( [0]m "0lm"+oon +log(1/6) =0 [Q]m +log(1/)))) in the
bound O m +log(1/6) multi-outcome case.
5²
Conditionally independent distributions: the O 1ogggg log + 1 log 1) upper bound. The 2
sample complexity upper bound for conditionally independent distributions' proved by pseudo- dimension argument. We first show Lemma ( that the optimal aggregator f belongs to some parametric family of aggregators. Then, upper bound the pscudo-ding secudo-dimension of the loss functions associated with this parametric family of aggregators, which will give the desired sample complexity upper bound.
Lemma C.2. For multi-outcome conditionally independent distribution P, given signals a = (s:) with corresponding reports r (r:)² (riz)is where Tij P(w 11);,, the pos-
terior probability of w =j satiisfies
12 P(w=j)
Píj
fT( = Pw = 1
P(w =
Σken P(w=kja- [==
18

---

Proof. By Bayes' rule and the fact that $1..... are independent conditioning on
P(w = ) = Plw I)[ P(s:
= j) i==1 P(s:
w
KEn P(w k)
Tt
k)
|== P(w j)
w
Plw=j)"
ENeR Plw=k)a->
I P(w P(: k)
Plw=j)" (w= w=/)
Plac)
ENER P(w=k)a-> IT
((w ();s((/))))))
P(a.)
P(w=f) [[= Píj
Σken Plw=kja- [ Tik
Since the above expression depends only on r;'s but not on s,'s, we have:
Plw=j -- i==1 Péj
P(w = jsss
Eken Plw=ka-1 Fik
(For the special binary event case,
(r))= = = 1|r)
P(w=1) p-
Pi
P(u=0j=- (1-r:)
P(
Plw=ljo-
P(w=0)
This proves Lemma 5.1
According to Lemma the optimal aggregator f (fz)jen belongs the following family of aggregators, parameterized by 0 (0y)sen 191
0 I -== Tiy
fd (f) sen ()(r) ΣKen Ox
(20)
II Tik
(The optimal aggregator f has parameter 0j ((==)-----) Let G the family of loss functions
associated with F, which is also parameterized by 0 E =R
g = 69 8 (r,w)
Σ ()( - 1lw =11²}
(21)
jEn
We recall the definition of dseudo-dimension of a family of functions:
Definition C.3 (e.g., [... Let H be a family of functions from input space X' to real numbers R. Let
2111,, ,((),..., ,..., ..()) E be inputs. Let ((L), (0),....(' [[(d) E IR be d "thresholds". Let b (1((2), ((d) E
{11 a vector of labels. We say can be generated by H (on inputs (11)
(d) with
thresholds ((2), ((x),... ((dD)) if there exists a function hn E H such that hn(x(()) > (0) if (1)
and hb(x:(1) ((6) if ((())
-1 (namely, sign sign(be(=!()) ((0) = b(0) for every E (1.....00 d).
The pseudo-dimension of H. Pdim(H), is the largest integer d for which there exist d inputs and d thresholds such that all the 2d label vectors in +13,+13a can be generated by H.
Pseudo- dindd--immnsoon gives sample complexity upper bound for the uniform convergence of the em- pirical means of family of functions to their true means:
Theorem C.4 (e.g., [... Let H be a family of functions from X to [0,U] with Pdim(?) = d. For any distribution D X, with probability at least 1 5 over the random draw of
U2 (
U
+ tog 2))
T T=
dd (d.log log
samples ,(.,..,,,??"" from D, we have: for every E H. |EED [(xa]] 7 Et MZ(1)) S S.
We now upper bound the pseudo-dimension of G:
19

---

Lemma C.5. Pdim(g) - ( log (S2)).
Proof. Suppose Pdim (g) = d. By definition, there exist d inputs (r(1), (r()),(()) (....... ...... (() and d thresholds (()) ..... t(d) E IR such that all the 24 label vectors b E {-1, +1}" can be generated by some function gb E G. We will count how many label vectors can actually be generated by g.
Consider the 2-th input (((")w()) and threshold t(0), To simplify notations we omit superscript (f), so we have (r,w) and t. We write a = (R)))en where 3y IT= Téy- For any function g E 9, we have
g (r) = Σ
05Z
1| = =1|
ken OCTI
JEB
Σ
8
2 Σ Eken OKTZ
But
+ 1
ken OKTT
JEN
Σ [(0,z,) JE
ww
OgJI +
Σ
27
(Enen 0xZX)
kE
kE
By definition, the set of parameters that give input (r, w) label "+1" is 10 E R 1 (r(r)ww) > tJ. By the above equation, this set is equal the set
f0 [
[(0ra JEN
2w
EONTA )² 1 Σ EguT1h kE
kE
EE
We note that the above set is the solution set to the quadratic form inequality 0 A0 > 0 for some matrix A E I [|| solution set AT A0 < These two sets share boundary: the solution set to 0 AA O. which a hyper-ellipsoid in @ In other words, the imput (r,w) w) and threshold define hyper-ellipsoid which divides the parameter space Rao into two regions such that all the parameters in one region generate the same label for that input.
Similarly, the set of parameters that give input (r,w) label "-1" is the
(r((), (d)). They define d hyper-ellipsoids in total, dividing the parameter space [R! into several regions. Within each region, all the parameters generate the same label for each input and hence generate the same label vector. So, the number of label vectors that can be generated by all the parameters in RR, is upper bounded by the number of regions. The number of regions divided by d hyper-ellipsoids in R²!. is in the order of (dd!)). Hence, to generate all the 2d label vectors we need (d 2 2d. This gives d S 0(12) log [S])).
Enumerating all inputs (r(1),,(()))
By Theorem C.4 and Lemma C.5 plugging in d = Pdim(() I O([2] log (S2]) and U = 2 (because go (((r.w w) is bounded by [o, 2] according to (8)), we obtain the following: with probability at least
1 - 8 over the random draw of
T T=0( U2
U log
- + +log 4)) = 0 [22 log S (1110
1
+ log 1 3
1 _
d- log
log
EZ
22
samples (T(1),,))))
(x()), ((())) from P. we have for any 9o E EG.
T
Ep [g (r:w)] - - Σ
0 (n(())
(l) Se.
t=l
This is equivalent to for any 8d EF
T
Ep
(f( - 1| = =1|2|
1 (n(()) - 110(() = =1112 Se
T
JEN
1ER
[P((f)- Lp Pomp (f0) Se
where P Pemp is the empirical distribution Uniform ( (1) w())) logic as the proof of the upper bound in Theorem 4.1 (Section 4.1. the empirically optimal aggrega-
(T( (.( (,()),(()) By the same
tor f = argmin T.p_mp (f0) ) is 26-optimal.
20

---

D Missing Proofs from Section
D.1 Proof of Lemma 2.1
To prove the first item (*(r) = P(w = 1 |r), we simply note that
1 argmin E,, [[[[(r)) w/ r
should minimize [[lf(r) w|2 r] for almost every r. This gives f*(r E[w
P(w
1 l
To prove the second item Lp(f) - Lp(f") ---(""))_l(()))((r)))))) f
we note that, by the definition
of Lp(-) and the fact that (*(r = E(w r) proven above,
Lp(f) Lp(f*) B[lf(r) w| (r( w|2]
E[](r)] -
= -221111000000--00000000-+00-2111
=E[f(r)² - 2f(r)
=E[(((r) (r))]]
E
Missing Proofs from Section 4
E.1
Proof of Lemma 4.3
Recall that have family D of distributions over S = S1 x S, satisfying the three properties in Definition 4.2 BB-unifomlly bounded, same marginal across distributions, and distinct marginals across signals). We have constructed from D the family of distributions P (Po D E D) for the forecast aggregation problem as follows:
Pn(w 0) = Pn( = 1) = 2'
Pp(. w 0) Uniform(S).
namely, Pb(s 0)
(22)
|S]
m
Pp(. w= D,
namely, Pp(s w 1) D(s).
We want to show that E-optimal aggregation with respect to P will imply (1+ B1² VE total variation distance learning with respect to D, and hence (e) 2 T ((1 + Ve. 6).
First, we have the following observations about D and P: Fact E.1. For a family of distributions' that satisfies the three properties Definition 4.2
D(a.) which is the same 1. Given signal 8,, expert i's report is r, = PD(w = 1| = +D+()) for all distributions D DD
2. For every expert given different signals s; s'c its reports T; T So, there is one-to- one mapping between s; and r; for every E {l....,n] n] and also a one-to-one mapping between the joint signal ($1...., and the joint report (ri,..., rn).
3. For any joint signal s, with corresponding joint report we have D(s) (=(1)f((r))
(((r)
Proof. We prove the three items one by one:
1. By definition, the marginal distribution of joint signal, PD(s), is
1 m
Pp(s) Pp(w (sP 0) + Pp(w ()Pb(s w w=
+ D(s)
(23)
21

---

Fixing S;, summing over s-; = ($1.......
81-1, ..)) E S -- we get
1 //S_
= ( + D(si))
PD(s)) = 2 m
+
Σ
D(s)
2 m
:ES
So, given signal 8i, expert i reports
r3 = P = s:) P=(w P)pp(s; w -=
D(s;)
(24)
PD(s;) and this is the same for all D E DD since D(s;) = D'(s;) by the "same marginal across distributions" property.
D(s:)
2. Given 8; * s/ by the "distinct marginals across signals" property, we have D(s:) * D(s)). is strictly increasing function æ, it follows that ri # r/. ++
D(a.) and 2_ Since r; = +D(a)
3. According to item 2, there is a one-to-one mapping between & = ($ 8n) and r = (Fi...., Tn); in other words, observing signals $1, .1....: Sn is equivalent to observing reports Th...., Ta- Therefore, by Bayes' rule we have
PD(w P) w
f* PD(w = PD
PD(8)
D(s)
by 22 and 23
(25)
m + D(s)
Rearranging, we obtain D(s)
(r)
m" (1-f (r)
Claim E.2. If we have an aggregator that s-optimal with respect to PD. then we can find a distribution D such that (D. D) B)
Proof. Because D is B-uniformly bounded, from (25) we can verify that (r) satisfies (*(r) <
B I+B So, can assume f(r) I+B as well (if (rr I+B we can let f(r) be I+ this only
B
reduces the approximation error [[ - f*r) Define D by letting D(s) m=(1-f(r)))
f(r)
Vs E S, where is the reports corresponding to s (ef., Fact Then, drv D) is
drv(D. Σ
(Dss) D(s) Σ
f(r) m (1-f((()))
(r)
m=(1--"(r)]
#ES
((r)
(r(r)
2m
1- f(r)
[-f"(r)
Because f(r), and the function has derivative (1-2)² (1+B)² when I B
we have
(D,(D < 2mn
1
(1 + B)²
- fr()))
RES
by 23 < (1 B)²
Pp(s)) [r(r] (1 BY²E,, [1(0)-
AES
By Jensen's inequality (E[X))² < E[ and by the assumption that f is e-optimal, we have (Ep, - Ep, [l((r) - (r)) S Thus,
drv( D) < (1 B)+B
which proves the claim.
Now, we present the reduction from learning D in total variation distance to forecast aggregation (T) for P. We use notations x E S to represent the samples from D. From x(1), ('),...., (7)
we construct the samples (1(1), ())).. (T) (T)) for the forecast aggregation problem. After obtaining solution f to the latter problem, we convert it into solution I to the former. Details are follows:
22

---

Input:
7' i..d. samples x11), ,.... (1) from unknown distribution D E D.
Reduction:
Draw samples w(1), ,... w(') (. For each t .....,
Uniform (0, 1j.
., T. do the following:
If w draw (( Uniform(S).
If w(t) let s(t) xx(t)
For each i, compute rt I +(a"))) Let ((()) = (rf 1....
D(s!")
(8)
3. Feed = = ( ((((2) ()))) )..., , (,(1) ())
to the forecast aggregation problem. Ob-
tain solution f.
Convert into Đ according to Claim
Output: б.
We remark that, in the second step of the reduction, the report r can be computed even D is unknown, because the (s (1)) the same for all D and hence known.
Using the above reduction, we show that the sample complexity e-optimal forecast aggregation for P cannot be smaller than the sample complexity of learning D within total variation distance (1 + B)² VE, which will prove Lemma
First, we verify that the distribution of samples ST in the above reduction exactly the distribution of T samples {(r(1) (,)")))). (r(T), w{})}} from Pp. This is because: (1) the distribution of w(t)) is Uniform((, 1}, as defined in Pn; (2) given (t) 0, the distribution of s(1) is Uniform (S), defined in Pd: (3) given (t) the distribution of s(t) is the same as the distribution of (t), which is D, because the random draws of w()) and (+ are independent; (4)
Proof of Lemma
according Fact F. the report r
( Pn
((()), as desired.
+
Then, by the definition of sample complexity of forecast aggregation, if we are given T Tp 8) samples Sr for the forecast aggregation problem, then with probability at least 1 8 we should be
able to find an c-optimal aggregator f with respect to Pp- According to Claim we can convert f into D such that
dr, S (1+ B)
By the definition of sample complexity T3 (-.8) of distribution learning, T must be least
T2 TTV ((1 B)3
which proves the lemma.
E.2 Proof of Proposition 4.4
To prove Proposition we will construct family of distributions D that satisfies the three proper- ties in Definition 42 and requires TTV 2( mx *Hog(1/5) samples to learn. For simplic- ity, write erv. For technical convenience, assume < 1 5 0.01.
<iv
E.2.1 Part 1: Constructing D
We index the distributions D, E D by 2; the meaning of 2 will be defined later. Without loss of generality, we assume |S,| = m to be an even integer, and denote S; = {1,.... m.) =: S. We will
define D2 to be a distribution over the joint signal space S = S ... x S, 5 (1,...,,m) } In the following we will call joint signal & E S" simply signal. We write a signal (b, æ, y). where b E S and x, y E S. We sort all the m" signals in S"h by the lexicographical
S as
23

---

order, from (1,,..,,1,), (1....,,)) to (m. m). We number the signals from to m"" using
1,
num(s) num(bb v)
{I,...,mm' m"):
to denote their numbers. We divide the whole signal space S" into |sm=?|= = m "buckets", each of size m² and denoted by Bb:
BB { {b, x. y) y.y
E Sm-2
We first define a "base" distribution Dasse then construct the distributions D3 by modifying the probabilities of the base distribution within each bucket Bb. Let is defined as follows:
m The base distribution
D base (8) 2? m)mm(a
m
W
num(a)
W
Because 1 < 1 S mm
+ m
)m
S we have
m" W S em"
(26)
We assign sign [+1,-1) to each bucket Bo. and let be vector of length m" that includes the signs of all buckets:
(=b)Des"
26 2 (+1,-11}
We have 2m n- 2m different 2's in total, and hence 2m different distributions D='s in DD in total. Let
c 20, so that cs Σ 1/2. For each 2, we define D2 as follows: within each bucket Bb. for each element (b, x. E Bp let
Diase (b, x. +
3 if
W
2'
D2(b,z,11 =
Drase b, x. 9)
2NCE
W
if S
m
2
y
(27)
Dasse b, x. V)
if >
m
2: V 3
W
Dasso b, or +
W
if
2: リ>
Claim E.3. The family of distributions DD = (D=)= defined above satisfies the three properties in
Definition B-uniformly bounded with e 1/2, same marginal across distributions, distinct marginals across signals.
Proof. B-uniformly bounded: For any 8, any Dz, by definition,
D2(8) S (sse + CE
m
26
1/2 m
W
m
So, the distribution is B-uniformly bounded with B e 1/2.
Same marginal across distributions: Consider each (s:).) We want to show that Dz(ss) does depend on z, and in fact, (z(s:) Dsaao(Ss). i E {L...., 23, namely, 8; is component of the vector b, then we have
D2(8i)= = Σ 8i))
Σ ΣΣ
D2(b,a,y)
8-IES_,
beST 2:
We notice that, fixing any b. the numbers of #200
and
-600
the summation
W
W
m sy D2 (b, y) are the same. So, they cancel out, and we obtain
D2(8:)
Σ
Drase (b, 1,) = Drasa (8t)-
bES b r=1y=1
If i = namely = then we have:
(2(s)) Σ
De(s
Σ Σ
(b,,,)
8-
bES y=1
24

---

Fixing any b. the numbers of taace W
and
-Sace in the summation Σ (z are the same. W
So, they cancel out, and we obtain
Dz(+i)= = Σ
Dosse (b, 2, 1) = Dase (8i). bESn-2
Finally, if namely 8, y, then by similar argument above we have
Da(+)= BES 2=1
Σ
Dasse (b, x. y) = (base(s))
Distinct marginals across signals: By the "same marginal across distributions" property above have D=(s;) = D (s)). So, to prove "distinct marginals across signals" we only need to prove
Dbase (8i) F Dbase (8)) for 8; # 8/-- Without loss of generality assume 8; < 8/.- By the definition
Dbase 2 3"mmn(o) and the fact that num(si, 8-1) < num(s(,888) for any 8-; E S-i, we have w-
Daase (s:)
Σ
Dasse (S 8 --))<
Σ A
Diase (5 8-1) Dbsse (s)s
8
so Dasse (8i) F Dbase (s1).
E.2.2 Part 2: Sample Complexity Lower Bound of Learning D
Overview We want to prove the proposition that the sample complexity of learning the family of distributions D { defined above is at least TTV (e, (e, Ω m=""== This proof is analogous to a textbook proof of Proposition 3.3 (the sample complexity for learning all distribu- tions), which uses reductions from the distinguishing distributions problem. Roughly speaking, if one can learn the unknown distribution D₂ well then one must be able to guess most of the com- ponents of the sign vector (z6 (=b)bEs>== correctly, mcaning that can distinguish whether the distribution Dz, on bucket Bg is DI,=+1 or D However, since Da and D2,=-1 are "Ols)""lose" to each other, distinguishing them requires (++) samples. average, there are only 0 samples falling into a bucket (because there are m n- buckets in total and the distribution
D2 close uniform). thus need O ((,,-)) Q [ ), which gives logarithmic terms, this proves the proposition.
2 m==
Ignoring
Formal argument First, we note that if we can learn D2 very well, then we can guess the vector correctly for large fraction of its m==2 components. Formally, suppose we obtain from T samples a distribution ò such that dD) S E. We find the distribution D', D, w
(wo)bes E {+1,-1] -1]m" that closest to in total variation distance. By definition, we have (Dw, D) < dDv(D2, D) s e. Hence, by triangle inequality.
drv D.) S drv(Dw, D) + drv d (.D.)) 28.
Let
= = be the number of different components of w and We claim that: Claim E.4. dr D2) 2s implies cm.
5n-2 wb # =b)
2W
Proof. Whenever we have a different component un # 2b, this different component contributes the following to the total variation distance between D., and D2:
1 Σ (b, (...,
2ce
m cs
(28)
2
W
W
(b.
(b.
So, the number of different components of and is at most
dr DD....) ma W
2W
25

---

We first show the 92( ( part in the sample complexity lower bound, and then show the 2 20m=) part. Together, they give the lower bound max(S2 log(1/))
=² ), _2(===)) }} =
S?( "Q""" "q"""=""" (log)(1/))))))) ). Consider the distribution D41 E D whose index is the all "+1" vector and the distribution D-1 DD whose index is the all "-1" vector. According to (88. the total variation
distance between D+1 and D-1 is dDv(D+1,,)) D_1) = -mm= m²ee -mm because +1 and -1 W
W =
have m= different components. Since W S em" (26). we have ( 2 o > 2e. Consider the distinguishing distributions problem (defined in Section 3 where we want distin- guish D+1 and D-1. we can learn from samples a distribution D that is s-close in total variation distance to the unknown distribution D+1 or D-1, then we can perfectly tell whether the unknown distribution is D+1 or D because the two distributions are more than 25-away from each other in total variation distance. Lemma A.3 implies that, to distinguish D+1 and D-1 with probability
log(1/5) 1 5, the number of samples must be at least D Di (Q((D).D..))) 52( log(1/6)). This proves the 2 (og((//)) part.
We then prove the Q m2 part. Suppose we first draw the vector 2 from (+1. 1mmm uniformly at random, then draw T samples from D2. We obtain the Dw as above. Let's consider the expected number different components of w and z this two-step random draw procedure:
E 2, T' sumples
E
Σ
1( + mbm
= Σ
E[ wb3]-
(29)
SES
S
We consider each component E (2 # wb]] in the above summation. Suppose that, within the T samples drawn from Dz, Tb of them fall into the bucket BB, So, To follows the Binomial(T, D(B))) distribution with
D(B))
Σ D2(b,z,y)=
Σ
num((.2..2)
W
(b.w.))B
(b,r.))BB
(Notice that the + Ra0E and 2005 cancel out in the summation and hence (Bb) does not depend on 2.) Let D., denote the "Bo -artp of distribution Dz, namely, D, conditioning on By:
D2(s) Vs E Bb. Dzo (8) D(Bb)'
We think of the random draw of the vector and the T samples follows: first, we draw To from Binomial D (BB))]: second, we draw 2b E (+1.-1) -1) uniformly at random; third, we draw To samples from the conditional distribution Dz, forth, we draw the remaining vector 2_6 and the
remaining T - Tb samples (which are samples outside of Bg). Only writing the first two steps explicitly, we have
E 1(tb + w6
E
E
E
11
F
wb}
2b: To
To
E
E
[1[1120
2bb = +b, wb}
+ 2 B * wp) | 2b II.
F.
2
1
E
Pr
2b + wbb
2b +1, To.
Pr | + wbb 1b -1, (30)
To
2
Claim E.5. For any To.
1/2
Pr
wh
2b = +1,
+ 1/2 Pr [Eb + wb
2bb -1, Tb] N
20E Dee/To, TTb
Proof. We notice that 5 Pr [bb + wb = = +1,76] + Pr [bb + wb 2b = 11 To is the probability that make a mistake when guessing the sign 2b using wb. if (1) 2b is chosen from {-1,+1} uniformly at random; (2) we are given To samples from Dz. (3) we then draw the remaining vector z-b and the remaining samples; (4) finally, we use the Dw computed from all samples to get wb- The steps (3) and (4) define a randomized function that maps the Tb samples of D=, to wa E {0. 17. and therefore, according to the first item of Lemma(A.5) we have
1 Pr [zb + wbb | 26 +1,1b] + Pr [2o * wb 26 - 1, >
TTb
du =1,=+11 D
2
(31)
26

---

Then we consider du (D= We use Lemma A.2 to do so. For any Bo, we have, on the one hand,
D +=0=+1(8)
num(() c8
aum(e) 6E
2 1 2cs,
D =0= (8)
) x)
aum(e) e) C
because
B-h a+b
2 1 2b for a = num(s)
1. On the other hand,
atb
D 11)=+((8)
mum(s) (s) + cs
< 1 + 4es,
D 26 (8)
)um((s c
because 2tth a-b
1
2b a-b
4b for a num(s) 2 and c S 1/2 Therefore, by Lemma A.2
we have
d (D., 2,, D1,=-1) S (4cz)² 802
(32)
Combining 31 and 32 proves our claim.
By 30
and Claim 1:5 we have B[1(=b + wbbl 2 B 2ce To.
Summing over Sm-2,
29
becomes
Σ bESn-2
B[1 wb3L
Σ
E
200
Th
208
Σ
B[VTh)
To
bESn-2
171 n-2
(by Jensen's 's inequality E[
S E[X
2c5
E(bb
Because [[[b]] T D(B))
+ E(brn))
S # m²
we have
Σ B[1(20 # wb}] bega-2
m
20E
Σ bESa-2
V
mmmmm
T
m==
-2cEm n-2 2 V
W m2?ma
T
2
2
(33)
Now, let's consider the probability with which we can obtain D such that drv(D, D2) S e. We will show that this probability most 0.99 < 8 T is less than 10-5
m n-2 e
Recall from
Claim that drv (D, D2) S e implies # = Σ See D {=b & wb) I
So, the probability is cm?
2W
most
Pr Σ be5n-2
11 + wp} <
2W cm3
Pr
Σ
11 = wb} 2 m n- 2W
cm
beSn-2
E
Dbc5n-2
1 ( wb)
(by Markov's inequality)
nn-
2W
cm2
+ 2ccm n- V W 22m
(by
3
nn-
2W
cm?
n + 20mm n-
mm S and m" < W < em" by 26
<
mn-Z
n
2em
1 + 20
eea
2
m 2a
0.99
< 1 -
when c 20, T 1 3.m"=²
n- 2 and 8 0.01. This means that, order to obtain such D with - samples are needed.
probability least 1 - 6, at least 10-5 3, ==-
27

---

F Missing Proofs from Section 5
F.1
Proof of Theorem 5.2 the ( log }) Lower Bound
The proof uses a reduction from the distinguishing distributions problem (defined in Section 3. We construct two conditionally independent distributions Pl, p2 over the space Ω S1
S with each [S,] = 2, S, = {a,b). Given T samples from either pl or P we want to tell which distribution the samples are coming from. We will show that, we can solve the forecast aggregation
problem, then we can distinguish the two distributions (with high probability), which requires T =
Q? (PI.P%)
log }) 2 log })) samples according to Lemma A.5
Let = 32. We assume 1 so that CVE
1 For Pl
we let
1
CvE
(1 1) = 0.5
+
=: =:p².
16n
For P?, we let
1
ove
(= 1) 0.5
=:p².
16n
n
We require that, in the forecast aggregation problem under both distributions pl and P2, whenever expert i sees signal a, 6, she reports
0.5,
O.
respectively. This gives the following conditional probabilitiess (- w)) P2 ( w):
(a w =0] (1 w =1] Fa
p² rb
(b w Pl w 33
2
5m
(34)
(a w =0] (a w= ===]] 1) Fa rb
p2 rb
(2 w = 03 (2
1+ +
20yl
(35)
Given T' samples from the unknown distribution P E (P),,P), each of which is a vector of (t) and all experts' signals s/ {a,b) b). we feed the corresponding reports r!") E {rairo} and (())
to the forecast aggregation problem and obtain a solution f. which is an e-optimal aggregator. We
want to use f to estimate the prior p = P(w = =1) E [x²,p²) so that we can tell apart pl and p2,
Recall from Lemma 5.1 that (r) 1+p"-1 IT. I- where P r-p- Writing p in terms of
(r),,, we have
n
x- fr(r)
-1)
1
In particular, when rv 0.5 for all i (I,....n). we have:
p (rrss) 1,
ro.5 = (0.5, (O.5....,0.3 0.5).
So, we estimate by:
β n-1 V (ra.s)
Now, we want to argue that, if f is e-optimal, then 10 pl is at most O O( Consider the function:
h(x) 1
1,
whose derivative is
T. 1x(x) n 1
2
28

---

By definition, we have
|0 1 -
(36)
Claim F.1. 1 (ro.s) 3.
Proof. For P E (P1, }2), its p
p
satisfies
1-p
0.5
1
VE
n
1 2 p p 2
16n
0.5
16m
n
1
20
n
(1-2(
1 + 20(E))
"
2 -2 20/3) 1
+ 8n
20VE
n
(37)
where in the last three transitions we used the inequalities
1-z I+
2x and (1 - x//n)/ 2
for x E (0, 1) and the fact that cvVE < 16. So,
1
1 2
(ross) = 1 p E
=
1+1
2 3
which proves the claim.
With Claim E. we can without loss of generality assume Y/2 s i(ro.) < as well (otherwise,
can truncate f(ro.5) to this range; this only reduces the approximation error f
Claim F.2. For I I 2 [1(xx)) S n-1
Proof.
1
22 m-1 < 8
[x(x))
Claim F.3. If f is E-optimal, then (ro.s) (ro.s) 2VE.
Proof. If f is e-ottimll, i.e., ( < s, then, by Jensen's inequality [[[*] E[X]²
we have
Ve 2
((r)) (²)
- (ro.s))
(38)
For both PE (P), (P!,P2), we have
P(ro.s) p- P(ro.5 w= +1 +1 -(ro.s w 0)
= =p. P(a w =1 + (1-p) P(a w 0)"
pp. 1 pp) p) (1 8n
20/e
by
1 + + 20vE
2'
Plugging P(ro.s) >
into 38 we get f((o.s) - (ro.s) < <2VE.
From 36 Claim E. Claim F2 and Claim
+ we getet
8
16
pl =
f( 1 (ro.s)
n-1 2 n
c.
n
(39)
Since p i+p as function of p has bounded derivative
(1+p}² $ 1, Equation 339 implies ap
8p
16
1
pl
71
29

---

if we use - = - as an estimate of p. This allows us to tell part Pl and pa because the difference I+3 between p¹ and p² is greater than twice of our estimation error 10 pl:
201E 6AVE
32// > 2 -pp 2 2(n 1) n
64VE
lp'
p²1 1p'-211
π
T2
Therefore, we can tell part Pl and P2 by checking whether p¹ or p² is closer to P.
Finally, we upper bound the squared Hellinger distance between pa and p2, This will give the sample complexity lower bound we want. Claim F.4 di (Pt, P2) I x(Pee)
Proof. For the marginal distributions of w, Pa and P2. according to Lemma A.2 and the fact that dev2
1
20 1 00 ((xx=)) we have
PPPP S 0 (((5))))
(40)
n2
Given w = 0 or 1, we consider the conditional distributions of each S/ s,ww and s.lw For 8; = a, we have
(a w)
1 8n
2ev/
1
+
1
ZevE
12
8n
(a w)
20
20
1
+
n
8n
n
1
+
201/
1
1
2evE
1
20v/
+
20VE
8m
n
8n
n
Acyl
leye
0 VVE)
a-r a+v
2
2x
1
+
8n
n
For 8 = b. we have
12 (b w)
4cv/
+
20y/
4ev
16oVE
8m
11
4n
1 O(cv3).
(2 w)
1 8n
20v/
AcVE
1cvE
+ 16
4n
4n
So, di (P!) N|W0"
p? Pa(i)) can be upper bounded as follows:
(P) s//wrr Pa(
1
(a w))
v P2(a w)
+ (VPi(b w)
2 (2 w)
2
1
(2 W)
2
27 + p² (w) - | p2 w)
PL(b ()
pl (a w)
2/
pi(a w))
1
1 (1
1 o(2VE)
(
1
deve) ) (1- (1-v1- 1/1-OlevE) 27
2
n
4n
n
1
CVE
+ +0 0(ov3)²
(since 1 -I- x) <
0
2
n
n1
(41)
n
Since pl = p! pl 2: and p2 = P2 11=1 23/wr w we have, by Lemma A.3 and Lemma A.4
(P' p2) < dz 1 p2) + max { {
II p2 (2( }
wE(0,1)
1=1
< dz (PL P2) + max
1 n nn- dP (w p
C2E
{ n 0 ( CēE }
40 and 41
<
+ max
n²
w
OcCe).
30

---

Therefore, according to Lemma A.5 to tell apart pl and p2 with probability at least 1 å we need least
1 5) log T= Ω d (P1, p2y
22 1
log 5)
samples. This concludes the proof.
G Missing Proofs from Section B
G.1 Proof Theorem B.2
G.1.1 Additional Notations and Lemmas
We introduce some additional notations and lemmas for the proof. Let pi be the expected average report of all experts conditioning on 0:
_ Σ E Bellw= [P(w= = 8:) e = 0],
E(rs w = 0]
(42)
72
which equal to the expected prediction of given expert i's signal s; where 8s distributed conditioning on = 0, averaged over all experts. Symmetrically, let
1 n
1
11
E[1 rs w==
1] E w= P( 01 8:) wu 1].
(43)
Recall that p P(w- = 1).
Fact G.1. (1 - p) = pリd
Proof. For each expert i, by the law of total expectation and the fact that r, P(w 1|st), we have the following equations:
(1 p) Eir; w + p- Eir w= P(w 0) EEr, w -= P(w = 1) Eir w
= B[ri]
= E,, P [s)] = P(w 1)
Subtracting p from both sides, we get
(1 (1-p) E(r; w = 0] p - = 0.
Averaging over all experts E (I....:n. nn], we conclude that
(1 (ppp) 1
Bir; w = 0] Σ E(1 - -- 0.
L
1=1
Lemma G.2. If (1 p)p1 pdd
5. then the averaging aggregator faug(r) ΣΣ T's is
e-optimal.
Proof. If (1 p)110 p/1 5. then the expected loss of favg is most
Lr(faug) BBlfaog [
= pl [favg (r) 1)2 -= = 1] + (1 - p) (Sevg (r) 0)2
w = 0)
===00 0] S pF [1 fangl (r) w = 1] + (1 --)EE p [ (r) w w==0
pE 1 a
ri w 1] + (1 p) 2) _ Σ ra w
n
1ll + p)
E;
which implies that Sang is coptimal.
31

---

The following lemma says that O log ;)) samples are sufficient to tell whether the mean of random variable is below or above &:
Lemma G.3. Given T = 10 log ii.d. samples , X(T) (T) of a random variable X E [0.1] with unknown mean [E[X] μ. with probability least ô we can tell whether μ or μ 2
This can be done by checking whether the empirical mean ji Ei X is < f or 2 l.c
Proof. If p 2 E, using the multiplicative version of Chernoff bound we have
Pr
j < 3 _ S Pr
4"
3
S
G.ATT 2
S se $ S..
Namely, with probability at least 1 8, it holds that
2
If ja e, then using the additive version of Sntenoff-HHefficee theorem, have
Pr A
<
E
S E D(u-álll))
Pr 1
S Diu+ +1
where (x+llu) = x In E + (1 x) In
1
Using the inequality D(xlly) 2 (=-w)² for S y and
D(ally)= 2 (x-y)² for 2 y. we obtain:
2x
2
(
Pr i < μ
S e
T
32
(G)
Pr A > /
8
e e
T
Se
2(%)
= C
8 < 2
By union bound, with probability least 1 8, we have
8 j 4
Combining the case of μ 2 E and μ e, we conclude that: with probability at least 5,
If p < e, then we must have μ < E.
If ü e, then have μ 2 or p P
2. In either case, we have μ 2 2-
The last lemma we will use shows how to estimate the unknown value of p 2 (ww=1)
P(w=0) with accuracy A using T = O log }) samples. Notice that, if one simply uses the empirical value I ΣT_ (1= Ei=, =0= to estimate p, then by Chernoff bound this needs T = 0 log 1)) samples, which is larger than what we claim by a factor n. This sub-optimality is because one only uses the (t)'s in the samples to estimate p. wasting the reports r s. By using r: (()ss to estimate we can reduce the number of samples by a factor of n. The basic idea is the following: According to E| m|w==] The numerator E| w = 0] and
Fact G.I we have p 1
the denominator E| (1 r4) = 1] can be estimated from samples of r (t) where (()
and 1 respectively. The total number of r: 's is Tn, because we have n experts per sample. This reduces the needed number of samples by a factor of n. Formally:
Lemma G.4. For conditionally independent distribution P, we can estimate =
P(w=1) P(w=0) with
accuracy lp-pl < A (equivalently, & E 1 + A) with probability least - 8 using
T T=O 0 1
1 (1- (1-p)po- n. log + min(p, pp} log 5
32

---

Semel E Ei 11 where #o and #1 are the num-
samples of (w(t), r10 's. by letting )0 -i- (1-1(0) bers of samples with w() = 0 and 1 respectively.
Proof. Recall that p P(w 1), 14,1-11 p P(w- 0), and
T
According to Fact G.
(which
says (1 p) = PH11). we have
140
E
Elr;
w
(44)
P1
E
Consider the following way of estimating from T samples (w!l), r()))= Let #o. #1 be the numbers of samples where (t) = 0, 1, respectively:
#o= Σ 1ww -],
#1 Σ Hwwlt) = =
We let
Ei Ei= ri #o
(45)
Ets(t)
Ei=( -r (1)))
#1
Now, we compare the in 45 and the p in 44 see that #o Enw(n= Ei= ri is an (unbiased)
(1)
estimate of the numerator Σ Flr; -= 0] = npo and that #1 En Ei= ((0) is an
(unbiased) estimate of the denominator - B[1 - ra w= 1] = nus1. We use Chernoff bounds to argue that the accuracy of the two estimates within with high probability if #o and #1 are big enough. Suppose that, when drawing the T samples, we draw all the wif)'s first (and hence #o, #1 are determined), and then draw all the r: '(")ss After all the (') 's are drawn, the r ri' become independent, because the signals 8 (t)ss are conditionally independent given (1) Therefore, we can use Chernoff bounds:
Pr
(t)
1441
> Ampa
< 2e
#2
#o
=0 i=1
Pr
1 Σ
(1
(t)
Anpu
S 2e
# mi 42
tww(
#onaga2
#1nd
Requiring 8 2 2
and 8 2 2e
namely,
3
2
3 log
#o
log
(46)
nn
Au
8'
we have, with probability at least 28, both of the following hold:
Σ
Σ (
(1 A) Jmpo:
Σ (1- (1) (1 A)mnn
(47)
#o fsw
Then, we argue that (46) can be satisfied with high probability if T large enough. This again
done by a Chernoff bound: since E[# = E T r- l(w(t) = = T P(w = j), for j = 0, 1, we have
Ta wx
T 1
Pr Ho T(1 -) T(1 - m)
< 2e
Pr | - Tyl 2 TTD) $ 2e
(48)
So, if we are given
12
log 2
T min (p, - p}
(49)
8
33

---

samples, then we can ensure that with probability at least 1 - 26, it holds #o 2 #1 T7p. Then, in order for (46) to be satisfied, we can let
TT p) and
2
3 ni
2
T p) 2 7HO A
log
Tp
2
log
2
5'
2
A
6
This gives
6
6
2
11-p)ym Pp:
6
2
T max
log 8'
log
log
(1 p0 n2
pμd
(1
p)uo
nn
8
(50)
Both
49) and (50) are satisfied when
6
2
12 min (p. - p}
log 2
T 1 (1 - p) RA²
log
2
To conclude, if we are given T (I-p)po p log
12
log samples, then with proba-
min
bility at least 46, (47 holds, which implics
(1 + A)
(1 A)
10- pl
β E
(1 1)m (1+ P S 41#
s 4A
P
for A <
1
G.1.2 The Proof
We want to show the O cnc en( 14 experts have y-strongly informative signals.
1 log 1 ++ log ()) sample complexity upper bound for the case where
We first use O log })) samples tell whether (1 -1-p) p) ppd < or - pp) = =P41 2 S. We note that
Σ r4 w -- = = =E [I[1fu 1w 0} Σ r.]
(1-p)p P(w 0) E
which is the expectation of the random variable X 1fw 0} 1 Σー rs So, according to Lemma G3 we can tell whether (1 p)pe 2/2 or 2 with probability at least 1 using
O log 4)) samples of X. If (1-11)) (1-p)po ppd < 2.j then according to Lemma G.2 the averaging aggregator Sang (r) 4 E ri is e-optimal. We hence obtained an e-optimal aggregator in this case. So, in the following proof, we assume (1 pP)m0 = p/1 2 5.
For each expert i, let S {s; S. P(a|==)) 2 + > be its set of y-strongly informative P(a]==)
signals that are more likely to be realized under w = 1 than under w = 0. Let S = S \ S {s; E
S P(s.[==))
P=)) } be the set of signals that are more likely to be realized under w 0. Since
ru P(s. (=))
P( w= p by Equation ①. whenever an expert receives a signal in S. its report satisfies
1-ri
2 (1+ t)p Vss E St
(51)
Ti and whenever it receives signal in S,, its report satisfies
r; 1-r; 1T P: Ass E Sp.
(52)
We will use the notation P(S w) = P(s E S. w) = Eness P(s: w), for u E {0,1), 1}.
Given a set of n signals .1,..., 8n. one per expert, we let X number of signals that belong to the St sets, and similarly let x Ei 1(s S2). We have
Ei 1( E 8t) be the total
F
x + X = n. and by definition,
E[X11 w = = Σ P(S w= 2 (1+ w= = + x+ w = 0). (53)
1
E[ w = 0] = Σ
P(S 3 = 0) N (1+7)P(SH) w= = (1+))E(X*) ww 1]. (54)
34

---

Claim G.5. At least one of E[ w 1] and B[x w = 0] is 2 2.
Proof. Suppose on the contrary both E[X' we have
w 1] and E[x w 0]
are < 2. Then, from (54
E E -= 1]
1 1+7 E[x
0] < 2
This implies n. E + x w w ||
2 + = n, a contradiction.
Let {0, 13 be an index such that
n 4
E E
w
(55)
Claim G.5
guarantees that such a u exists. We construct a "hypothetical" aggregator fuypo that, having access to / and [F[X" w). predicts whether = or by counting the number X signals that belong to the S sets and comparing it with its expectations under w = 0 and 1, E[X" w 0] and F[ w 1]. respectively. Specifically, given reports r = (r1,..., rn) as input, with corresponding unobserved signals (51...., Sn), fhypo does the following:
(1) If u = 1, count how many reports ry's satisfy I-r;
r4 2 (1+7)pp: If O, count how many
reports ri 's satisfy I- I T. According to (11 and (52), this number is exactly equal to the number of signals that belong to the S/¹ sets, X
(2) Then, check whether X is closer (in terms of absolute difference) to E[ = u] or E
w). X is closer to B[X" w =u], output fuypo (r) u; otherwise, u.
output fnypo (r)
We claim that fnypo is s-optimal.
Claim G.6. Given 1 2 8 log and E w== u] 2 T' Shypo is e-optimal.
Proof. Given either w 0 1, consider the conditional random draw of signals -1,-... 8n- Be- cause X" = Ei= [s, E S and the random variables 1(s, E }, i = 1,..., n, are [0, 1]- bounded and independent conditioning w, by Hoeffding's inequality we have
Pr x
E
2 w
2e 202
Let
a
2 log
(56)
2=2
Then with probability at least 1 2e
s, it holds
X E[X w| < a.
(57)
Consider the difference between _6
w = u/ and _ "4
w = 1 u]. By
53
and 54 we have
X = 1 - u] -
1
E[x -== = ul
(1-
?
E[x = u].
1+9
By the assumption B[X" = u] 2 4.
E
w = w=l-w w] S E[X" | = u|
1 1+*
7."
By the assumption 1+7 Therefore
2 2 8 2 log we have
2
n
2 8
2 log
4
log - = 4a.
I4y
4
E w = u| -[X" w = 1 u| N
4a.
(58)
Because we already had X E[x | w|| < a (which happened with probability at least - E).
X turns out to be closer to E x w = u] it must that w u; X turns out to be closer
to E[X" w 1 - u] it must be that = u-u. In either case, our output frypo(r) is equal to
35

---

w, having loss O. If | B[x" | w/] < a did not happen, our loss is at most 1. Therefore, the
expected loss of our aggregator fhypa most
[p(hp)))) = I.,, [h([hyyo(()) wi? [|
S BEw (1 e)- 8 =e
Since the expected loss of the optimal aggregator f is non non-negative, fhypo is s-optimal.
In the remaining proof, we show how to use samples to learn a "real" aggregator f that implements the same functionality as the hypothetical aggregator fuypo and hence is e-optimal. We have two learning tasks: First, we need to estimate p. so that we can implement the step (1) of faypo which tells apart
r I 14-P. Second, we need to find an index u E {0, such that E|x" w = u] 2 and estimate E[X" w ul, so that we can implement the step (2) of Shypo which tells whether X is closer to E[X " w ul or [E[X" w = u]. We show that these two tasks can be achieved using O cm 1イ.)² log + E log }) samples, with probability at least 1 (6)).
n T-r, 2 (1 + p)p and I-r;
Task I: estimate / using Ti = 0 sm T+. log 1/4 + 1 log () samples. We want to use samples
to obtain an estimate ý of p such that 145 P (1 + 7)p. So, by checking whether - > ý or - I T4. p. Using Lemma G.4 with 175
T-r; < د we can tell apart - 2 (1 + 7)p and
we obtain f such that
(1
with probability at least - 8 using
1= = ( (p-))oos log 6
1
1
1 0o
1
1
log 1 8)
min 1 p} log 8)
log
En )2
8
samples (recall that we have min 1 - p} 2 (1 p) 110 = 1 2 - The e then satisfies
X < (1+ + 7 1+7
) p
7)) and p> 1 - ) 1+ P.
1
as desired.
Task 2: find such that [[ w u| 7/2 and estimate E[ | w = u], using T2 O log )
samples. First, we show how to use T2 O log })) samples to estimate both [[ w and
E[X" w = 1] with accuracy
2 log By the same argument as in the proof of Lemma G.4
(Equations 48 and 49 we know that with probability at least 28 over the random draws of
12 log
2
T2 min (p. p}
(59)
samples, the numbers of samples (w) ri ,..., 1(())) )'s where (()) = 0 and w(t)) = 1, denoted by #a and #1. i. must satisfy
1 (1 -1- p)
#o
#1 #1 pll..
2
We consider the samples where (1) = =0. There are #on total number of ( (f)ss. Suppose we have
accomplished Task 1. Then, for each r (t)
tell whether the corresponding signal s(0) belongs
(e)))
to S by checking whether -_ < p. So, we can exactly compute the total number of such signals
ii in the f-th sample, x0())) = -t 1 (() E S.), whose expected value is E[x" 3 = 0). Because signals are independent given (t)
= 0. by Hoeffding's 's inequality we have
Pr
Σ
11s E s. - #o w = 0i| 2 #oa $ 2c
20
mon
22
2#
(t) 1
x2
36

---

Plugging in a = Va log 2 and #o 2 (1 pp)T2, we get
x B[x w ol 2 s 2e #o log 5 202---1--000 log ?
Pr
tai(t)
Similarly, considering the samples where w())) = 1, we get
Pr
Σ
x
B[X w= 1] 2 S 2e - #1 log 3 2e log
1=01=1
Therefore, if we require
2 (2/0)
T2 2 min(p,1 - p) log (2/e)
(60)
then with probability least 1 26, both
x E[x w 0]
Σ x
Σ
F[x 3 11 <a
(00
tw(
hold. Namely, 1 Σ 1 x and Ev X1(() #1
are a-accurate estimates of TE] x w 1
and E[X' w = 1]. Equations (59) and (60 together imply that T2 0 min O log .) samples suffice.
log f) 5
Then, we identify an index u E {0, 1} such that E[x" w = ul 2 3. By Claim G.5
there exists
a E {0, with E[X" w = v) 2 z.2 Since
1 #. Et:((t= (((() is an a-accurate estimate of
E[X" w = v/., we must have
Σ (wils)
X 2 E w= 2) - a 2
n
#
2
So, at least one of E f0, 1) must satisfy 1 Eow(n Xu(()) 2 - a. By picking any such
we are guaranteed that E[X" | w = u| 2 #. Eiw(t= Xu(1) 2 2
2a. Given the assumption
32 log 2 in the statement of the theorem, have
1
1
log 2n
71
8"
Hence, X
2a 2
2
2
4.
Finally, as argued above, a-accurate estimate of E| [ = ul is given by
I Etwwn =y x(()).
Constructing f. samples, we construct f that implements the same functionality as fuypo- Let
After accomplishing Tasks and using Ti T = 0 O log 1 + log 7)
1 Σ x
M
-2a,
#a (t)
where 1 Ems Xu(t) is our estimate of E[x" M w u] in Task and / a log?
Claim G.7. E[x w= > M > X = 1 uj] +
Proof. Because 1 #.
Eiw(t) (a(() is an a-accurate estimate of E[x" w u1. we have
1
E w
ul
x a M a.
#u
(iw =u
Recall from Equation 58 that E. x
w =
u]
< X = u] 4a. So.
x
w = 1 u]
x + a - 4a = M a.
(tw
The above two inequalities prove the claim.
37

---

Given reports = (ri..... rx) as imput, we let f do the following:
(1) If u = 1, count how many reports ry 's satisfy I-r; > iú If u = 0, count how many reports
T
7t's is satisfy ب < p. Let this number be X;
(2) Then, check whether X > M or X & M. IfX M, output f(r) = u, otherwise, output f(r) =
We argue that f implements the same functionality as Snypo: (1) Task we got 1750 / < P < (1 + p)p. So, by checking whether I-r, > I < á we can exactly tell whether I-r (1 + (1p))p S P. Hence, have X X", the number of signals that belong to the S sets. (2) Recall from Equation (57) that with probability at least - E, X a-close to its expectation E[x" w]. Then, according to Claim G.7 X > M implies that X is closer to E[X" ww = w]; X < M implies u/. So, implements both of the two steps in flypo Hence, according to Claim G.6 is e-optimal.
that X is closer -[x"
w
G.2 Proof of Theorem B.3
According to Lemma 5.1 the optimal aggregator is
(*
(61)
1+
where p i-pp We claim that an approximately optimal aggregator can be obtained by first esti- mating / from samples and then use the aggregator with the estimate jr:
j(r) = 1+ pm
(62)
Claim G.8. If pp-pl_ < 2vE < n-1 2.
1 then the aggregator f defined above is e-optimal.
Proof. Consider the function g( = 1+p=-1 I1
(where á is the variable and r,'s are con-
stants). We claim that
n- lo (D) <
(63)
4p
To see this, we note that if r; = 0 for some i then g(ه) = 0 and gp) = 0. Otherwise, we let 1-n. < too and take the derivative with respect to P.
1
(p ( v2)
1
('())
(1 pm 11) (n 1)pm-2 -(n - 1) (1 1y)
- (n 1)
+ 0 v
By the AM-GM inequality a+b bzb22 2 2vb we get
1
(n 1) 1
(0) S (n
4p"
2
8
v8
as claimed.
Using 63 we have, for ò 2 G.
n R-1
n1 lp-pl pl
ff)) -
18 1p
(64)
4 Lpin p]
8
So, to obtain e-approximation (()f(r) [T)
c, require
1f(r) (r(r)
Ve. This can be satisfied if the error in estimating p is at most اáا
2/5
p
p n-I'
38

---

(t) We then show how to use 2 log ( samples to estimate the value of with O accuracy, which will give us an e-optimal aggregator according to Claim G.8 Recall from 14 that when signals are 7-weakly informative, the reports always satisfy
r
S 1 T
S (1 (1+1) 7)p.
(65)
1+7
The following observation is the key:
Lemma G.9. For each expert i, we have
E
Pi w
= 0 = p:
E
I-re w = ト
As corollaries, for k conditionally independent reports r we have IE [II 1-r, w =
0| = 1² and E
Il
1-t w =
Proof. Because Ti P(s,(u=l) (from 13 ) we have P[
1-r
Ti Ti
0
P(s: w 0)
P(s: w =
w = 0) p= Σ
P(ss 1)p p.
P(s:
e.ES,
S.ES.
For conditionally independent Ti, ....... Tke we have
Ti
w
E
Ti
w = 0 = pp.
1=1
Similarly, we can prove E 1-1%
and
E
1-n 1
Let A Vs and suppose we are given T 3ym
6e log 3 7
54emm log 3 = 0 log }) samples.
Suppose when drawing the samples we first draw the events (t)'s, s, and then draw the reports 7 ss conditioning on (1() being 0 or 1. After the first step, the numbers of samples with w(() = 0 and ((()) = 1 are determined, which we denote by #o and #1. Since #o + #1 T, one of them must be at least T/2. We argue that whether #o 2 T or #1 2 T we can estimate p1/7 with accuracy 3A. (For simplicity, we assume that 1/7 integer.)
2
If #u 2 T/2, then we consider the #on reports r(("'s in the samples with (t))) 0. We divide these #on reports evenly into #ony groups, each of size 1/7 denoted by ( in a group Gy: because r, (t), are in-
GI...., C.o... Consider the product of 1-, dependent given a 0, by Lemma
G.9 we have
E
= 0| =/1
(t)
1
r( E(
Using (65) and the incquality (1 + 1/7 S e, we have
1 -0th < (1+7)15
(1
2/1 s 17
1 1- 50
5 EG,
Let X, be the random variable <pl/> 10 EG,
From the above equation and in-
1-
equality we have E[X;) 1 and X, E [ 1] C [0, 1]. So, by Chernoff bound,
#onry
X2 E (1= 1
#on742 3e
Taya? Ur
Pr
-=
> 1
2
1 - 22
1 1 8,
Honr
39

---

given our choice of T. Multiplying estimate of p 1/:;
1 #ony Ejary Xj by epl/7, we obtain the following
#ony
1/7 = #omy
E (1+
1-
EGG
Dividing by p2/n, get A E
If #1 2 T/2, then by considering the #in reports in the samples with w0 1, divid- ing them into # i1y groups of size 1/7, HI...., , Hany, and similarly defining random
variable Y, p4/ II. 1
1-r(")
obtain the following estimate of (2)
(8)
- P1 # #
E (1= (1=
r E
Multiplying by pt/7, we get (/7 el
Taking the reciprocal and noticing that
31 when A J. we obtain (2) @ 33 IE
From the discussion above we obtained an estimate ý {po. p1} of p such that (2)1/7 E e1144 Raising to the power of y, and using the inequality (1-x)² 2 1 xy and (1+ S E 1 1+2m for any I 1, we get
E (1#3A)" _ - -32,, e cd0 S - [1-3Ay, 1 647].
In particular, this implies 10-pl < 64y = 2 Then, according to Claim G.8 the aggregator defined by f(r)
is e-optimal. We hence obtained an e-optimal aggregator.
H
Missing Proofs from Section 7
H.1 Proof of Theorem 7.1
Regard P as joint distribution over reports (r1, (f1.-... rw) and the state w, where is sampled by first sampling 8; E St and then letting r; = P(w = 1 18)). Since |S m, there are at most m different values of r; that can be sampled, so there support of P. For each such tuple (r,w), consider the empirical probability of this tuple:
most 2m" different tuples of (r,w) in the
w(r.w)
1 T (=1
Σ
(((r((t), = (r,
By the Chermoff bound, we have
Pr [r[[(rr,)) P(r, w|l AP(r,w) 2e TP(
Using a union bound for all the 2m tuples and the fact that P(r,w) 2 P(s,w) > nn (where E S are some signals that generate r), we have
|i(r, w) ((rw))(Pr,.))) w)] s (P(rww)
(66)
holds for tuples (r, w) except with probability at most
TP(n
sT < 4m e
2m 2c
3m =
3m
4mn
T
log
(67)
cA2 2
40

---

Assuming 666 holds, we consider the "empirical" Bayesian aggregator:
f(r) P(r,w),
P(r)
Since 66
implies P(r,w) () E (1 ().(r w) and P(r) E (1 we have
f(r) 2 1- A P(r,w)
2A
1+ P(r) -1 1 21
and
2A 1+ P(r,W) (1+ 1- A
f(r) - A P(r)
(1+4)0)))))))))
< 2. Putting these two inequalities together:
If(r) - = (r).
We note that this holds for all possible in the support of P. So, the expected approximation error
of f is at most:
( = Σ P(r))(()) (r))
$ Σ P(r)16A25((11
= 16A Σ P(r) P(r,w))
P(r)
w(r,w)²
P(r)2
164
- 16A1
1612
P(r)
P(r)
Letting 16 E. namely A
we have E[lf(r) (r)) S E, so an e-optimal
16.
aggregator. Plugging A
into (67
we obtain the sample complexity
16
3m
48m
m
0 m (n m + log 1 )
log
log
CA2 2
CE
5
c5
41


Reviews:
[{"review_id": "gX897lcUj9", "reviewer": "Reviewer_mdHA", "summary": "This paper studies the problem of forecast aggregation: There are n experts who are each given signals about some unknown binary event, and each output a posterior probability based on these signals. We have access to k such reports (corresponding to k events). The task is to aggregate these reports to produce a prediction that is close to the unknown event in expected squared distance. The paper shows that there is an exponential gap in sample complexity (ie k) between the cases when the experts' signals are independent conditioned on the event, versus the general case. In addition, a (slightly loose) upper bound is provided for the arbitrary case, and a lower bound is provided for the conditionally independent case.", "questions": "- Is it possible to say something about when you expect the signals to be conditionally independent in the real world? For instance, your paper points to a Kaggle dataset - is there any evidence that there is conditional independence there? Do you expect your algorithms to work well on that dataset?\n- Can you draw any connections between (variants of) this problem and distribution testing?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is a very clearly written paper, and it studies an interesting problem. The story of the exponential sample complexity difference in the arbitrary signals vs conditionally independent signal setting is a compelling one. Overall, I think this is an interesting paper that deserves to be accepted to NeurIPS.\n\nMore comments:\n- It studies a natural extension where the aggregator sees multiple samples from each expert. This is a more realistic setting than the one-shot problem.\n- There are natural connections to distribution estimation here that are interesting. For this reason, I think this paper will appeal to the CS theory community.\n- The future directions mentioned are compelling, and will likely lead to several interesting results.", "weaknesses": "I don't see any real weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question 1: \n\nSignals are conditionally independent if they are independent draws from some distributions but the distributions are determined by the unknown state of the world. For example, the unknown state of the world can be the quality of a school, which is either high or low. If the school quality is high, the probability for a student from the school to pass a state exam is 0.9. If the school quality is low, the probability for a student to pass the state exam is only 0.6. This can be viewed as an example of conditionally independent signals, as given the quality of the school, students' exam outcomes are independent draws from a distribution that depends on the true quality of the school. Conditionally independent signals capture many real-world settings where agents have independent observations but the distribution of the observations depends on the state of the world. \n\nWe think Kaggle competitions can be reasonably modeled using conditionally independent signals. However, the dataset contains heterogeneous non-repeated tasks and hence is not a good match for our algorithm, which needs iid repeated tasks.  \n\n\nQuestion 2: \nMany distribution testing problems (e.g., testing whether a distribution is uniform) can be solved by distribution estimation: first use samples to compute the empirical distribution as an estimate of the true distribution, then check whether the empirical distribution satisfies the property we are testing.  This means that distribution estimation is more difficult than (or as difficult as) those distribution testing problems, in the sense that the number of samples needed for distribution testing is <= the number of samples needed for distribution estimation.  Our results show that forecast aggregation for general distributions is essentially as difficult as distribution estimation, so it is also more difficult than those distribution testing problems.  But the forecast aggregation problem for conditionally independent distributions is not directly comparable to distribution estimation and we don't see a direct connection with distribution testing, either.  Nevertheless, testing whether a distribution is conditionally independent is itself a property testing problem. "}, {"review_id": "RStbfDFRIS", "reviewer": "Reviewer_ey4x", "summary": "The paper studies the aggregation of expert opinions in a Bayesian setting for discrete (binary) distributions. The setting further limits each expert to have at most m different opinions, making the problem fully discrete. This reduction enables the analysis of the sampling complexity of the problem, i.e., the minimum number of observed aggregation events (expert opinions and true outcome) required to get an epsilon tight estimate on the true distriution in the total variation norm.", "questions": "Is it essential in the proof that the experts decide on Bayesian arguments? Or does it suffice to assume that each expert always just makes one of m possible reports, i.e., can we focus only on the joint distribution of r^t and omega and ignore s^t?\nIn Section 6, does bigger Omega really reduce the complexity? This is counterintuitive.\nWhat is the source of Theorem 7.1?", "limitations": "The authors clearly state the limitations of their work, are honest and clear about the current mismatch in their bounds in epsilon, and don't oversell their results.\nI do not see potential societal impact.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper approaches the more and more important problem of how to combine different \"expert\" opinions in a thorough and interesting way. It is well written, clear and, as far as I managed to go into detail, correct.\nTheir approach sparks many new ideas on how to approach aggregation problems and opens up interesting questions on the relevance of (historical) data in aggregation.", "weaknesses": "The proof of the lower bound in Section 4.2 doesn't seem intuitive. The mere construction of an example is of course sufficient for a formal proof, but an explanation of why the authors had the idea for this specific construction might be more illuminating.\nThe authors sometimes speak of the \"number of signals an expert can possibly observe.\" Maybe this is better explained as the \"cardinality of the signal the experts observe\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Experts decide on Bayesian arguments?  This is an interesting observation!  Indeed, our results for the case of general distributions do not need the experts to be Bayesian.  It is OK if an expert reports 0.1 even if its posterior belief given signal is 0.8, as long as the expert reports different numbers given different siganls.  What matters is the correlation between all experts' reported numbers and the event outcome.  The principal can learn such correlation from samples and then do aggregation.  However, for the case of conditionally independent distributions, we do need the experts to be Bayesian in order to apply Lemma 5.1 to get the smaller sample complexity upper bound.\n\n2. Does $|\\Omega|$ really reduce the sample complexity?  No.  As we explain in the end of Appendix C, this is an artifact of normalization.  When defining the loss of an aggregator for multi-outcome events, we normalize the loss by dividing $|\\Omega|$ to make sure the loss is bounded in $[0, 1]$.  But for an aggregator that always outputs a probability distribution, its loss is actually bounded by $[0, 1/|\\Omega|]$, causing the illusion that the sample complexity decreases as $|\\Omega|$ increases.  We will change the loss to the unnormalized loss (not dividing $|\\Omega|$) to avoid this confusion. \n\n3. Theorem 7.1.  The source of this theorem is that the minimum joint probability $P(s, \\omega)$ is bounded away from $0$ (by a margin of $c/m^n$ with constant $c$).  In the proof of this theorem (Appendix I) we used the \"empirical Bayes aggregator\" $\\hat f(r) = \\frac{\\hat P(r, \\omega)}{\\hat P(r)}$, namely, the Bayes rule with empirical probability estimated from samples.  For this aggregator to work well, the denominator $\\hat P(r)$ must be away from $0$.  This is guaranteed if the minimum joint probability is away from $0$.  In contrast, Theorem 4.1, which is more general but has a looser upper bound, does not need this assumption."}, {"review_id": "5kTgbbZrjO", "reviewer": "Reviewer_YcHV", "summary": "The paper initiates the study of sample complexity of forecast aggregation under a Bayesian forecasting model. In this problem, n experts, each observe a private signal about an unknown binary event, and then report their posterior beliefs about the event to a principal, who then aggregates the reports into a single prediction. The underlying joint distribution is unknown to the principal, but he has access to i.i.d. samples from the distribution. Using these samples, the principal aims to find an epsilon-approximate optimal aggregator, where optimality is measured in terms of the mean squared error between the aggregated prediction and the real event. The authors show that the sample complexity grows exponentially in the number of experts n, but that if the experts’ signals are conditionally independent, then the sample complexity does not depend on the number of experts at all. They further consider the case of non-binary events and weakly/strongly informative experts.", "questions": "Did you consider using the maximum a posterior optimality measure for the principal? An added explanation on why MSE is a good choice can benefit your work.", "limitations": "The authors adequately addressed the limitations of their work", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is very elegantly written. It presents the setup of the problem clearly, motivates it thoroughly, and initiates an interesting discussion on the fundamental limits of the problem. The proof sketches are quite intuitive and convincing and their implications are reflected and discussed.   ", "weaknesses": "One weakness for me is in the particular choice of mean squared error as an optimality measure. It seems counter-intuitive, given that the experts report their posterior beliefs, which is in essence a minimum error probability optimality measure. It would seem more natural for the principal to look for an aggregation that minimizes the probability of error given the exerts reports. Another weakness is the gap between the upper and lower bounds with respect to epsilon, which might follow from the relatively simple upper bound proposed in the paper. This also bleeds over to the conditionally independent variant. Finally, the choice of averaged squared error as an optimality measure in the multi-outcome events section brings forth quite bizarre looking results. It follows, under this measure, that is the number of events is omega(1/epsilon^2) our task succeeds with zero samples! The authors do clarify this in the appendix, but I would remove it altogether from the paper (or change the measure to additive MSE). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Questions:**\n\nMaximum a posterior (MAP), or posterior mode, is the point estimate $f(r)$ that minimizes the absolute loss $E[ | f(r) - \\omega | ]$.\nWe choose to use the squared loss $E[ | f(r) - \\omega |^2 ]$ instead in our work for a few reasons:\n\n(1) Squared loss is a very popular loss function used in many learning problems.\n\n(2) Squared loss is a proper loss function for eliciting probability distributions.  Our model requires the experts to report posterior beliefs to the principal.  To incentivize the experts to do so, the principal needs to reward the experts according to a proper loss, for example the squared loss $-E[|r_i - \\omega|^2]$.  The experts maximize their expected rewards by reporting their beliefs (posterior distribution of $\\omega$) truthfully to the principal.  (We wrote this in Footnote 3.)  So, to be consistent with the expert's loss, we measure the principal's loss by the squared loss $E[|f(r) - \\omega|^2]$ as well.  A non-proper loss like the absolute loss $-E[|r_i - \\omega|]$, on the other hand, does not elicit the beliefs from the experts.   \n\n(3) Squared loss has the property that the difference between the squared losses of any aggregator and the optimal aggregator can be conveniently written as their expected squared difference: $E[|f(r)-\\omega|^2] - E[|f^*(r)-\\omega|^2] = E[|f(r)-f^*(r)|^2]$ (Lemma 2.1).  This property is used in our sample complexity lower bound argument.  The absolute loss doesn't have this property and its sample complexity lower bound may need a different argument. \n\nWe think it will indeed be interesting to consider other losses as directions of future work, for example the absolute loss $E[|f(r)-\\omega|]$, which is minimized by posterior mode (MAP).\n\n\n**Response to Weaknesses:** \n\nRegarding the ``bizarre looking result\" in the multi-outcome case, this result is indeed an artifact of the use of the *average* squared loss (where we divide the loss by $|\\Omega|$).  (You can see our response to Reviewer ey4x for details.)  We will change the loss to the additive squared loss (not dividing $|\\Omega|$) to avoid this confusion.  Thanks for suggesting this! "}, {"review_id": "SzzU29L70s", "reviewer": "Reviewer_bpux", "summary": "The authors study the problem of forecast aggregation in a Bayesian setting. Here n experts observe an individual signal that is correlated with the truth, and each expert reports their posterior belief to the principal. The principal aggregates these reports and outputs a prediction, whose quality is assessed using square loss. The object of interest is the minimax sample complexity necessary to obtain an additive excess error of $\\epsilon$ compared to the best aggregator that knows the conditional distribution of truth given reports. \n\nThe authors derive results for arbitrary distributions $P(\\omega, s)$ on truth and signals, as well as distributions that factorize as $P(\\omega,s) = P(\\omega) \\prod_i P(s_i|\\omega)$. They show that there is an exponential gap in sample complexity between these two cases, and in the latter case the complexity does not depend on the number of experts $n$. ", "questions": "Have the authors thought about results for alternative loss functions (e.g. different weight for type2 vs type1 errors) or continuous truth/signal distributions where for example the experts report the condition mean of the truth given their signal? ", "limitations": "The authors address limitations. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Well written and appears technically sound\n- Introduces the study of sample complexity to the forecast aggregation literature\n- Interesting and general results that cover multiple natural settings\n- A novel lower bound construction for distribution estimation that allows reduction from estimation to aggregation", "weaknesses": "- Non-matching upper and lower bounds in most cases\n- Main technical difficulty lies in construction of lower bound, the upper bounds don't require significant new ideas\n- Techniques seem limited to the specific loss function + discrete truth/signal setting. Commenting on possible extensions in these directions would be interesting", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Alternative loss functions:**\n\nOur response to Reviewer YcHV mentions several reasons why we focus on the squared loss $E[ | f(r) - \\omega |^2 ]$ in this work.\nWe did think about other loss functions like the logarithmic loss $E[(\\omega \\log(f(r)) + (1-\\omega)\\log(1-f(r)))]$ and the absolute loss $E[ | f(r) - \\omega | ]$.  Some of our techniques for the squared loss can be applied to other loss functions.\n\n*Logarithmic loss:* Because the logarithmic loss can be unbounded, giving an upper bound on its sample complexity is not easy and may need significantly different techniques than our current work.\nFor the lower bound, our results for the squared loss can be applied.  Due to Pinsker's inequality, the logarithmic loss difference is greater than or equal to 2 times the squared loss difference, so if we get an $\\epsilon$-optimal aggregator under the logarithmic loss, then this aggregator is automatically $\\epsilon/2$-optimal under the squared loss. This means that our sample complexity lower bound for the squared loss is automatically a sample complexity lower bound for the logarithmic loss.\n\n*Absolute loss:*  Our upper bound argument for the squared loss can be adapted to the absolute loss.  But the lower bound argument cannot. The squared loss has the property that the difference between the squared losses of any aggregator and the optimal aggregator can be conveniently written as their expected squared difference: $E[|f(r)-\\omega|^2] - E[|f^*(r)-\\omega|^2] = E[|f(r)-f^*(r)|^2]$ (Lemma 2.1).  We use this property in the argument. \nBut the absolute loss $E[ | f(r) - \\omega | ]$ does not have this property, and its sample complexity lower bound may need a different argument.\n\nWe believe that analyzing other loss functions is an interesting direction for future works. \n\n**Continuous signal/truth distribution:**\n\nWe did think about continuous distributions for signal or truth. \nFor continuous signal distribution, our results for conditionally independent distributions do cover this case -- we make no assumption on the signal space.  For not conditionally independent distributions, note that our results show that the sample complexity grows with the size of the discrete signal space.  This means that with a continuous signal space the sample complexity is infinite in the worst case.  So, to obtain a meaningful sample complexity result, one has to make some assumptions on the continuous signal distribution, for example, the distribution belongs to some parameterized family.  Then, one may obtain very different results than the results in this paper, using different techniques. \n\nWith continuous truth distribution, the problem will be very different if the experts only report the posterior means of the truth instead of the posterior distributions of the truth.  And similar to continuous signals, to obtain a meaningful result one has to make some assumptions on the continuous truth distribution.  Depending on different assumptions one may get different results. We believe continuous truth/signal distribution is an interesting direction to explore for future works. "}]

Author rebuttal:

Meta-review: All reviewers are unanimous in their support for this paper. The forecast aggregation problem is no doubt of significant importance, the technical results are solid, and the presentation is excellent. The "path" of this paper, as outlined by potential future works in this direction, is very interesting. This work will be a great contribution to the conference proceedings.
Decision: Accept (spotlight)