Stronger Calibration Lower Bounds via Sidestepping

Mingda Qiao, Gregory Valiant

TL;DR

For decades, a significant gap existed in our understanding of online calibration: we knew the optimal error was somewhere between $\sqrt{T}$ and $T^{2/3}$. This paper finally breaks the $\sqrt{T}$ floor, proving the first "super-$\sqrt{T}$" lower bound of $\Omega(T^{0.528})$ by introducing clever adversarial strategies called "early stopping" and "sidestepping."

What Problem Does This Paper Address?

In online binary prediction, a forecaster predicts the probability $p$ that a future bit will be 1. We say a forecaster is well-calibrated if, for every probability $p$ they predict, the actual frequency of 1s matches $p$. For example, if a weather app predicts a 70% chance of rain on 100 different days, it should actually rain on exactly 70 of those days.

The calibration error measures how far a forecaster deviates from this ideal. Since the 1990s, we've known that a randomized forecaster can achieve an error of $O(T^{2/3})$ even against an adversarial sequence of bits. However, the best known lower bound was a trivial $\Omega(\sqrt{T})$, which comes from simply flipping fair coins.

The challenge in proving a stronger lower bound is that forecasters can "cheat." They can use coarse-grained binning (grouping different probabilities together to cancel out errors) or backcasting (using future predictions to "cover up" mistakes made in the past). This paper aims to shut down these escape hatches.

Methods

The authors introduce two primary technical innovations to force the forecaster into high-error states:

  1. Early Stopping: To prevent the forecaster from merging different epochs into one large "bin" to average out errors, the adversary monitors the cumulative error. If the error hits a high threshold in the middle of the sequence, the adversary can effectively "stop" the game (or output zeros for the rest of the time), locking in that high error.
  2. Sidestepping: This technique prevents "cover-ups." The adversary chooses future bit probabilities such that if the forecaster tries to fix a past error, they inevitably create a new, equally large error in a different "bin."

To analyze these strategies, the authors propose the Sign-Preservation Game. This is a simplified, discrete abstraction where an adversary chooses "cells" and a forecaster places "+" or "-" signs. A sign is "removed" (covered up) if subsequent moves allow the forecaster to balance the bias. By proving that the adversary can ensure a certain number of signs are "preserved," the authors derive the lower bound for the full prediction setting.

Datasets

As this is a theoretical paper in the field of online learning and game theory, no empirical datasets were used. The results are derived through mathematical proofs and the analysis of the proposed Sign-Preservation game.

Key Insights and Ideas

  • Calibration as Error Management: The paper shifts the perspective from "predicting the next bit" to "managing a portfolio of biases." A smart forecaster isn't just trying to be right; they are trying to ensure their past mistakes don't accumulate.
  • The Power of the Game Abstraction: The Sign-Preservation game is a powerful tool because it strips away the continuous nature of probabilities and focuses on the combinatorial heart of the problem: the order and direction of biases.
  • Tensorization of Games: A key "aha moment" in the proof (Lemma 5) shows that if you can prove a small lower bound for a small game, you can "tensorize" it—essentially nesting the games within each other—to boost the lower bound for much larger sequences.

Key Results

  • The First Super-$\sqrt{T}$ Bound: The authors prove a lower bound of $\Omega(T^{0.528})$. While $0.528$ might seem like a specific, odd number, its importance lies in being strictly greater than $0.5$ ($\sqrt{T}$).
  • General Reduction Theorem: They provide a theorem that translates any lower bound on the Sign-Preservation game value into a lower bound on calibration error. This provides a roadmap for future researchers to potentially reach the $T^{2/3}$ mark.

Limitations and Future Work

The most obvious limitation is the remaining gap: we are now at $T^{0.528}$, but the upper bound remains at $T^{2/3} \approx T^{0.666}$.

The authors suggest two main paths forward:

  1. Closing the Gap: Can the Sign-Preservation game yield a better constant? They note that if a specific version of the game is shown to have a linear value, the lower bound would jump to $T^{0.6}$.
  2. Adaptivity: The current lower bound relies on an adaptive adversary (one that changes strategy based on the forecaster's moves). An open question remains whether a non-adaptive (randomized but fixed) adversary could achieve the same results.
  3. The Converse: Is the $T^{2/3}$ upper bound actually tight, or could a more sophisticated forecaster bring the error down closer to $T^{0.528}$?

Summary updated

Abstract

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.
BibTeX
@inproceedings{qiao2021stronger,
  author = {Mingda Qiao and Gregory Valiant},
  title = {{Stronger Calibration Lower Bounds via Sidestepping}},
  booktitle = {STOC},
  year = {2021},
  doi = {10.1145/3406325.3451050},
}
Figure