REVIEW 2 cited by
High dimensional online calibration in polynomial time
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require $\exp(d)$ days to achieve non-trivial calibration. In this work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy $\epsilon > 0$, our forecaster becomes $\epsilon$-calibrated after $T = d^{O(1/\epsilon^2)}$ days. We complement this result with a lower bound, proving that at least $T = d^{\Omega(\log(1/\epsilon))}$ rounds are necessary to achieve $\epsilon$-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12]. Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows.
Forward citations
Cited by 2 Pith papers
-
High-Dimensional Calibration from Swap Regret
TreeCal achieves epsilon-calibration over arbitrary convex sets and norms in (diam/eps)^{O(rho/eps^2)} rounds, and a new lower bound shows exp(poly(1/eps)) rounds are necessary for l1-calibration on the simplex.
-
Calibration through the Lens of Indistinguishability
A survey arguing that calibration error is best understood as the degree to which two worlds, the predictor's and nature's, can be distinguished, and that this view unifies ECE, smooth calibration, CDL, and distance t...
Discussion (0). Sign in to comment.