Faster online calibration without randomization: interval forecasts and the power of two choices. (arXiv:2204.13087v2 [cs.LG] UPDATED)

We study the problem of making calibrated probabilistic forecasts for a
binary sequence generated by an adversarial nature. Following the seminal paper
of Foster and Vohra (1998), nature is often modeled as an adaptive adversary
who sees all activity of the forecaster except the randomization that the
forecaster may deploy. A number of papers have proposed randomized forecasting
strategies that achieve an $\epsilon$-calibration error rate of
$O(1/\sqrt{T})$, which we prove is tight in general. On the other hand, it is …

arxiv interval lg power randomization