Pith. sign in

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

arxiv 2504.09096 v1 pith:22WER43J submitted 2025-04-12 cs.LG cs.DScs.GTstat.ML

classification cs.LGcs.DScs.GTstat.ML
keywords calibrationepsiloncalibrateddaysachieveasymptoticallyforecasterguarantees
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. High-Dimensional Calibration from Swap Regret

    cs.LG 2025-05 conditional novelty 7.0 of 10

    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.

  2. Calibration through the Lens of Indistinguishability

    cs.LG 2025-09 accept novelty 2.0 of 10

    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...

Pith tools