Sample Complexity of Forecast Aggregation
Sample Complexity of Forecast Aggregation
复制标题
DOI：
--
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Tao Lin;Yiling Chen
中科院分区：
文献类型：
--
作者：
Tao Lin;Yiling Chen
我们考虑贝叶斯预测聚合模型，其中$n$专家，观察一个未知的二进制事件的私人信号后，报告他们的后验信念的事件的主体，谁然后聚合成一个单一的预测报告的事件。专家的信号和事件的结果遵循委托人未知的联合分布，但是委托人可以访问i.i.d.从分布中提取“样本“，其中每个样本是专家的报告（不是信号）和事件的实现的元组。使用这些样本，主要的目的是找到一个近似最优的聚合器，其中最优性是衡量聚合预测和实现事件之间的预期平方距离。我们证明了这个问题的样本复杂度至少是$\tilde \Omega（m^{n-2} / \varepsilon）$任意离散分布，其中$m$是每个专家的信号空间的大小。这个样本的复杂度随着专家数量n的增加而呈指数级增长。但是，如果专家的信号是独立的，以事件的实现为条件，那么样本的复杂度就会显著降低，为O（1 /2），不依赖于n。我们的结果可以推广到非二元事件。我们的研究结果的证明使用减少分布学习问题，并揭示了一个事实，即预测聚合几乎是一样困难的分布学习。
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.