Stronger calibration lower bounds via sidestepping
Authors:
Open Access
- 15 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 456-466
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 ∈ [0, 1], among the np bits for which the forecaster predicts probability p, the actual number of ones, mp, is indeed equal to p · np. The calibration error, defined as ∑p |mp − p np|, quantifies the extent to which the forecaster deviates from being well-calibrated. It has long been known that an O(T2/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 Ω(√T) bound that follows from the trivial example of independent fair coin flips. In this paper, we prove an Ω(T0.528) bound on the calibration error, which is the first super-√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 Ω(T0.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.Keywords
All Related Versions
Funding Information
- NSF (National Science Foundation) (CCF-1704417,AF-1813049)
- Office of Naval Research (N00014-18-1-2295)
- DOE U.S. Department of Energy (DE-SC0019205)
This publication has 9 references indexed in Scilit:
- Forecast Hedging and CalibrationJournal of Political Economy, 2021
- Non-asymptotic calibration and resolutionTheoretical Computer Science, 2007
- Calibration with Many Checking RulesMathematics of Operations Research, 2003
- Any Inspection is ManipulableEconometrica, 2001
- An Easier Way to CalibrateGames and Economic Behavior, 1999
- A Proof of Calibration via Blackwell's Approachability TheoremGames and Economic Behavior, 1999
- Asymptotic calibrationBiometrika, 1998
- The Well-Calibrated BayesianJournal of the American Statistical Association, 1982
- VERIFICATION OF FORECASTS EXPRESSED IN TERMS OF PROBABILITYMonthly Weather Review, 1950