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

• URL: http://arxiv.org/abs/2607.12928v1
• Date: Tue, 14 Jul 2026 16:00:29 GMT
• Title: Efficient Sequential Calibration with $O(T^{2/3-ε})$ Error Bound
• Abstract summary: A recent breakthrough by citetdagan2024breaking overcomes the classical (T2/3) barrier for calibration error.<n>We present an efficient randomized forecaster that achieves an expected calibration error (O(T2/3-varepsilon)) for some constant (varepsilon>0)<n>Our forecaster combines the textscSPR-Calibration procedure citepdagan2024breaking with an outer Blackwell-style correction layer.
• Score: 19.221722169368494
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the online binary sequential calibration problem. A recent breakthrough by \citet{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-\varepsilon})\) for some constant \(\varepsilon>0\). Our forecaster combines the \textsc{SPR-Calibration} procedure \citep{dagan2024breaking} with an outer Blackwell-style correction layer. The \textsc{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 \textsc{SPR-Calibration} guarantee in \citet{dagan2024breaking}, and the latter is controlled using a quadratic potential argument together with the sparsity of the \textsc{SPR-Calibration} forecaster.

Related papers

• Optimal Recalibration of an Online Predictor [17.79426749489757]
  We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss.<n>We give an online algorithm that achieves $(varepsilon calibrated varepsilon2)$-recalibration for Lipschitz proper losses in $T approx varepsilon-3$ rounds.<n>We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared
  arXiv  Detail & Related papers  (2026-07-22T02:36:03Z)
• Rethinking Post-Hoc Calibration in Semantic Segmentation [2.8002121919083685]
  Post-hoc calibration offers a practical way to correct confidence estimates without retraining the segmentation model.<n>We study two such issues: first, adding a constant to all logits leaves the softmax probabilities unchanged, but several standard calibrators can still depend on this arbitrary offset.<n>Second, post-hoc calibration is typically fitted by minimizing a likelihood-based objective, whereas segmentation models are trained with task-specific metrics such as Dice.
  arXiv  Detail & Related papers  (2026-07-02T09:01:21Z)
• Adaptive Calibration in Non-Stationary Environments [44.81344039432424]
  We develop a suite of algorithms that achieve adaptive calibration guarantees under multiple calibration measures.<n>Our approach builds on and extends prior work [Hu et al., 2026, Luo et al., 2025], introducing a novel non-uniform partition of the prediction space that allocates finer resolution near the underlying ground truth.
  arXiv  Detail & Related papers  (2026-05-12T04:06:40Z)
• Rethinking Early Stopping: Refine, Then Calibrate [49.966899634962374]
  We present a novel variational formulation of the calibration-refinement decomposition.<n>We provide theoretical and empirical evidence that calibration and refinement errors are not minimized simultaneously during training.
  arXiv  Detail & Related papers  (2025-01-31T15:03:54Z)
• Breaking the $T^{2/3}$ Barrier for Sequential Calibration [26.563792462828726]
  We study the problem of online calibrated forecasting of binary sequences. Foster & Vohra (1998) derived an algorithm with $O(T2/3)$ calibration error after $T$ time steps, and showed a lower bound of $Omega(T1/2)$. Qiao & Valiant (2021) improved the lower bound to $Omega(T0.528)$ by introducing a game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration.
  arXiv  Detail & Related papers  (2024-06-19T16:19:39Z)
• Orthogonal Causal Calibration [55.28164682911196]
  We develop general algorithms for reducing the task of causal calibration to that of calibrating a standard (non-causal) predictive model.<n>Our results are exceedingly general, showing that essentially any existing calibration algorithm can be used in causal settings.
  arXiv  Detail & Related papers  (2024-06-04T03:35:25Z)
• Towards Certification of Uncertainty Calibration under Adversarial Attacks [96.48317453951418]
  We show that attacks can significantly harm calibration, and thus propose certified calibration as worst-case bounds on calibration under adversarial perturbations.<n>We propose novel calibration attacks and demonstrate how they can improve model calibration through textitadversarial calibration training
  arXiv  Detail & Related papers  (2024-05-22T18:52:09Z)
• Classifier Calibration with ROC-Regularized Isotonic Regression [0.0]
  We use isotonic regression to minimize the cross entropy on a calibration set via monotone transformations. IR acts as an adaptive binning procedure, which allows achieving a calibration error of zero, but leaves open the issue of the effect on performance. We show empirically that this general monotony criterion is effective in striking a balance between reducing cross entropy loss and avoiding overfitting of the calibration set.
  arXiv  Detail & Related papers  (2023-11-21T08:45:09Z)
• A Consistent and Differentiable Lp Canonical Calibration Error Estimator [21.67616079217758]
  Deep neural networks are poorly calibrated and tend to output overconfident predictions. We propose a low-bias, trainable calibration error estimator based on Dirichlet kernel density estimates. Our method has a natural choice of kernel, and can be used to generate consistent estimates of other quantities.
  arXiv  Detail & Related papers  (2022-10-13T15:11:11Z)
• Tail-to-Tail Non-Autoregressive Sequence Prediction for Chinese Grammatical Error Correction [49.25830718574892]
  We present a new framework named Tail-to-Tail (textbfTtT) non-autoregressive sequence prediction. Considering that most tokens are correct and can be conveyed directly from source to target, and the error positions can be estimated and corrected. Experimental results on standard datasets, especially on the variable-length datasets, demonstrate the effectiveness of TtT in terms of sentence-level Accuracy, Precision, Recall, and F1-Measure.
  arXiv  Detail & Related papers  (2021-06-03T05:56:57Z)
• Localized Calibration: Metrics and Recalibration [133.07044916594361]
  We propose a fine-grained calibration metric that spans the gap between fully global and fully individualized calibration. We then introduce a localized recalibration method, LoRe, that improves the LCE better than existing recalibration methods.
  arXiv  Detail & Related papers  (2021-02-22T07:22:12Z)
• Calibration of Neural Networks using Splines [51.42640515410253]
  Measuring calibration error amounts to comparing two empirical distributions. We introduce a binning-free calibration measure inspired by the classical Kolmogorov-Smirnov (KS) statistical test. Our method consistently outperforms existing methods on KS error as well as other commonly used calibration measures.
  arXiv  Detail & Related papers  (2020-06-23T07:18:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.