Efficient Sequential Calibration with O(T^{2/3-epsilon}) Error Bound

arXiv:2607.12928v1 Announce Type: new Abstract: We study the online binary sequential calibration problem. A recent breakthrough by itet{dagan2024breaking} overcomes the classical (T^{2/3}) barrier for calibration error. Building on this result, we present an efficient randomized forecaster that achieves an expected calibration error (O(T^{2/3-arepsilon})) for some constant (arepsilon>0). Our forecaster combines the extsc{SPR-Calibration} procedure itep{dagan2024breaking} with an outer Blackwell-style correction layer. The extsc{SPR-Calibration} procedure controls calibration with respect to a surrogate sequence of conditional-mean estimates, while the correction layer controls the additional error incurred when these surrogates are used to approximate the true outcomes. The analysis decomposes the total calibration error into the surrogate calibration error and the residual discrepancy between the surrogate sequence and the true outcomes. The former is bounded by the extsc{SPR-Calibration} guarantee in itet{dagan2024breaking}, and the latter is controlled using a quadratic potential argument together with the sparsity of the extsc{SPR-Calibration} forecaster.

Related

• From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs
• SLO-Guard: Crash-Aware, Budget-Consistent Autotuning for SLO-Constrained LLM Serving
• EMA: Efficient Model Adaptation for Learning-based Systems

Source: arXiv cs.LG | 2026-07-15