论文标题
通过避开更强的校准下限
Stronger Calibration Lower Bounds via Sidestepping
论文作者
论文摘要
我们考虑一个在线二进制预测设置，预报员一一观察$ t $ bits的序列。在揭示每个位之前，预报员预测了位$ 1 $的概率。预报器被称为良好的校准，如果对于[0，1] $中的每个$ p \，则在$ n_p $ bit中，预报员预测概率$ p $，实际的数量$ m_p $的确等于$ p \ p \ p \ cdot n_p $。定义为$ \ sum_p | m_p -p n_p | $的校准误差量化了预报员偏离良好校准的程度。早就知道，即使选择对手，也可能基于先前的预测，即使选择位，也可以达到$ O（T^{2/3}）$校准错误。但是，除了从独立的公平硬币翻转的微不足道示例中，$ω（\ sqrt {t}）$在下边界几乎没有人知道。 在本文中，我们证明了$ω（t^{0.528}）$在校准误差上绑定的$，这是第一个超级 - $ \ sqrt {t} $下限为此设置，从而获得了我们的最佳知识。我们工作的技术贡献包括两种下边界技术，即早期停止和避开，这规避了以前阻碍了强大校准下限的障碍。我们还提出了预测设置的抽象，称为标志保护游戏，这可能具有独立的兴趣。该游戏的状态空间比完整的预测设置要小得多，并且可以进行更简单的分析。 $ω（t^{0.528}）$下限是从一般还原定理中遵循的，该定理将标志性保护的游戏值转换为校准误差的下限。
We consider an online binary prediction setting where a forecaster observes a sequence of $T$ bits one by one. Before each bit is revealed, the forecaster predicts the probability that the bit is $1$. The forecaster is called well-calibrated if for each $p \in [0, 1]$, among the $n_p$ bits for which the forecaster predicts probability $p$, the actual number of ones, $m_p$, is indeed equal to $p \cdot n_p$. The calibration error, defined as $\sum_p |m_p - p n_p|$, quantifies the extent to which the forecaster deviates from being well-calibrated. It has long been known that an $O(T^{2/3})$ calibration error is achievable even when the bits are chosen adversarially, and possibly based on the previous predictions. However, little is known on the lower bound side, except an $Ω(\sqrt{T})$ bound that follows from the trivial example of independent fair coin flips. In this paper, we prove an $Ω(T^{0.528})$ bound on the calibration error, which is the first super-$\sqrt{T}$ lower bound for this setting to the best of our knowledge. The technical contributions of our work include two lower bound techniques, early stopping and sidestepping, which circumvent the obstacles that have previously hindered strong calibration lower bounds. We also propose an abstraction of the prediction setting, termed the Sign-Preservation game, which may be of independent interest. This game has a much smaller state space than the full prediction setting and allows simpler analyses. The $Ω(T^{0.528})$ lower bound follows from a general reduction theorem that translates lower bounds on the game value of Sign-Preservation into lower bounds on the calibration error.
