Research map / Learning theory and algorithms / Prediction and decision losses

Testable and Actionable Calibration for Full Swap Regret

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Probabilistic calibration · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Soft-Binned Calibration Decision Loss (SCDL), a calibration measure that is fully actionable for full swap regret via a discretized best-response, and achieves near-optimal O(T^{-1/2} log T) testability while being sound, complete, consistent and continuous.

Problem

Calibration measures that are both actionable (bound swap regret for all decision tasks) and testable (accurately estimable from finite samples) do not exist simultaneously; prior measures either weaken actionability or have suboptimal estimation error.

Approach

Define calibration error as a soft-binned version of CDL: randomly round predictions to a grid of size 1/m, compute a swap-regret-style quantity on the rounded distribution, and self-balance m against the rounding error 1/m. Actionability uses the best response applied to rounded predictions, sidestepping the impossibility result for exact best response.

Key results

• SCDL achieves O(T^{-1/2} log T) testability (expected estimation error O(T^{-1/2} log^{3/2} T) for general distributions), improving on the O(T^{-1/3}) of binned/smooth ECE.
• SCDL is fully actionable: SR <= 2 SCDL + 2/m, with a randomized best-response on rounded predictions, and quadratically related to distance to calibration: Omega(DistCal^2) <= SCDL <= O(sqrt(DistCal)).
• Lower bound Omega(T^{-1/2}) shows SCDL is tight up to a log factor; in experiments SCDL has smallest estimation variance in most settings and keeps tracking swap regret when the optimal swap is non-monotone, where Cutoff loses correlation.

Surprising findings

• Cutoff calibration error raised to power alpha is fully actionable only for alpha <= 2/3, which compromises its testability to Omega(T^{-1/3}).

Limitations

• Testability and actionability bounds include log factors (T^{-1/2} log T rather than T^{-1/2}); the gap is only tight up to a logarithmic factor.
• Actionability requires a modified response function (rounding predictions) rather than exact best response, and a factor-4 constant relative to SCDL.

Experimental setup

Metrics: estimation variance correlation with swap regret

Baselines: ECE binned ECE smooth ECE cutoff calibration error smCE^{1/2} CDL

Builds on: Calibration Decision Loss (Hu and Wu) distance to calibration (Błasiok et al.) smooth calibration error cutoff calibration error interval calibration error

Closest papers by meaning

• Simultaneous Swap Regret Minimization via KL-Calibration (NeurIPS 2025 · similarity 0.89)
• Testing Calibration in Nearly-Linear Time (NeurIPS 2024 · similarity 0.86)
• Truthfulness of Calibration Measures (NeurIPS 2024 · similarity 0.86)
• Learning to Decide with AI Assistance under Human-Alignment (NeurIPS 2026 · similarity 0.85)
• High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.85)
• Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.85)