Calibeating Made Simple

• URL: http://arxiv.org/abs/2603.22167v1
• Date: Mon, 23 Mar 2026 16:28:07 GMT
• Title: Calibeating Made Simple
• Abstract summary: We show that calibeating is minimax-equivalent to regret.<n>We also prove that multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem.<n>For binary predictions, our result gives the first calibrated algorithm that at the same time also achieves the optimal calibeating rate.
• Score: 75.91049650502048
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study calibeating, the problem of post-processing external forecasts online to minimize cumulative losses and match an informativeness-based benchmark. Unlike prior work, which analyzed calibeating for specific losses with specific arguments, we reduce calibeating to existing online learning techniques and obtain results for general proper losses. More concretely, we first show that calibeating is minimax-equivalent to regret minimization. This recovers the $O(\log T)$ calibeating rate of Foster and Hart [FH23] for the Brier and log losses and its optimality, and yields new optimal calibeating rates for mixable losses and general bounded losses. Second, we prove that multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem. This yields new optimal multi-calibeating rates for mixable losses, including Brier and log losses, and general bounded losses. Finally, we obtain new bounds for achieving calibeating and calibration simultaneously for the Brier loss. For binary predictions, our result gives the first calibrated algorithm that at the same time also achieves the optimal $O(\log T)$ calibeating rate.

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)
• Calibeating for general proper losses: A Bregman divergence approach [10.525701754548102]
  This work introduces a general framework for calibeating based on regret.<n>We consider a large family of proper losses that includes $$-Tsallis losses (for $in [1, 2]$) and Lipschitz losses.
  arXiv  Detail & Related papers  (2026-05-17T05:39:22Z)
• Efficient Calibration for Decision Making [26.81026842833163]
  Hu and Wu (FOCS'24) use this to define an approximate calibration measure called calibration decision loss ($mathsfCDL$)<n>We develop a comprehensive theory of when $mathsfCDL_K$ is information-theoretically and computationally tractable.
  arXiv  Detail & Related papers  (2025-11-17T18:52:00Z)
• Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks [19.642496463491053]
  We revisit online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks.<n>We consider comparing predictors that are robust to small input perturbations, perform well under Gaussian smoothing, or maintain a prescribed output margin.<n>Our algorithms achieve regret guarantees that depend only on the VC dimension and the complexity of the instance space.
  arXiv  Detail & Related papers  (2025-04-14T18:00:23Z)
• 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)
• 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)
• Optimal Multiclass U-Calibration Error and Beyond [31.959887895880765]
  We consider the problem of online multiclass bounds U-calibration, where a forecaster aims to make sequential distributional predictions over $K$ classes with low U-calibration error. We show that the optimal U-calibration error is $Theta(sqrtKT)$.
  arXiv  Detail & Related papers  (2024-05-28T20:33:18Z)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models [33.36787620121057]
  We prove a new generalization bound that shows for any class of linear predictors in Gaussian space. We use our finite-sample bound to directly recover the "optimistic rate" of Zhou et al. (2021) We show that application of our bound generalization using localized Gaussian width will generally be sharp for empirical risk minimizers.
  arXiv  Detail & Related papers  (2022-10-21T16:16:55Z)
• The Devil is in the Margin: Margin-based Label Smoothing for Network Calibration [21.63888208442176]
  In spite of the dominant performances of deep neural networks, recent works have shown that they are poorly calibrated. We provide a unifying constrained-optimization perspective of current state-of-the-art calibration losses. We propose a simple and flexible generalization based on inequality constraints, which imposes a controllable margin on logit distances.
  arXiv  Detail & Related papers  (2021-11-30T14:21:47Z)
• Focal and Efficient IOU Loss for Accurate Bounding Box Regression [63.14659624634066]
  In object detection, bounding box regression (BBR) is a crucial step that determines the object localization performance. Most previous loss functions for BBR have two main drawbacks: (i) Both $ell_n$-norm and IOU-based loss functions are inefficient to depict the objective of BBR, which leads to slow convergence and inaccurate regression results.
  arXiv  Detail & Related papers  (2021-01-20T14:33:58Z)
• MTAdam: Automatic Balancing of Multiple Training Loss Terms [95.99508450208813]
  We generalize the Adam optimization algorithm to handle multiple loss terms. We show that training with the new method leads to fast recovery from suboptimal initial loss weighting.
  arXiv  Detail & Related papers  (2020-06-25T20:27:27Z)
• Calibrated Surrogate Losses for Adversarially Robust Classification [92.37268323142307]
  We show that no convex surrogate loss is respect with respect to adversarial 0-1 loss when restricted to linear models. We also show that if the underlying distribution satisfies the Massart's noise condition, convex losses can also be calibrated in the adversarial setting.
  arXiv  Detail & Related papers  (2020-05-28T02:40:42Z)

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.