CS Paper Radar

A Matching Lower Bound for Online Smooth Calibration

Kaixuan Ji, Quanquan Gu

cs.LG stat.ML ·submitted 2026-11-11 23:13 UTC · v2
theory

Abstract

We study smooth calibration error in sequential binary prediction, a measure of how far probabilistic forecasts are from being calibrated that is robust to small perturbations of the forecasts. The minimax smooth calibration error is known to lie between $Ω(T^{1/3})$ and $O(\sqrt T)$(Qiao and Zheng, 2024), where $T$ is the number of rounds. We close this gap for both adaptive and oblivious adversaries. We construct an adaptive adversary whose outcome mean moves with the forecaster's cumulative residual, which makes compensating for past residuals costly and forces every forecaster to incur $Ω(\sqrt T)$ expected smooth calibration error. Simulating this adversary against the forecaster's average prediction yields an oblivious adversary with the same guarantee. These lower bounds match the known $O(\sqrt T)$ upper bound up to universal constants, and are therefore minimax optimal. Our results also imply matching $Θ(\sqrt T)$ bounds for calibration distance and lower calibration distance. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

Closest papers

Nearest neighbours by meaning across the whole index.

Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$

cs.DS stat.MLcs.GTcs.LG ·2026-10-06 ·Eric Dai, Maxwell Fishelson
similarity 0.70
Abstract

Probability forecasts are calibrated when predicted probabilities match empirical outcome frequencies: among events assigned a probability $p$, we'd hope that the fraction of positive outcomes is close to $p$. We study the problem of sequential forecasting of binary outcomes. The classical $O(T^{2/3})$ bound on expected cumulative $\ell_1$-calibration error established by Foster and Vohra stood for over two decades until Dagan et al. reduced the exponent $2/3$ by an unspecified constant. We establish a new two-phase recursive labeling strategy for the sign-preservation-with-reuse game that yields the bound $O(n^αt^β)$ for all choices of space and time. We then sharpen the reduction from upper bounds on sign preservation to calibration by modifying the equivalence of Dagan et al. to use only $O(\log T)$ instances of the sign-preservation-with-reuse game. This lets us establish an explicit bound of $O(T^{0.662942288})$, the first explicit exponent below $2/3$ for sequential calibration, by combining both improvements and choosing explicit feasible parameters.

0.28

Sharp Integrality Gaps in Calibration Distance

cs.LG math.PR ·2026-10-05 ·Zinan Wang, Xinhao Yang
theory similarity 0.65
Abstract · 38 pages

We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absolute-change cost. We sharpen the offline comparison C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem 2) to the sharp worst-case order Theta(T^(1/3)). If Delta_T is the supremum of C - L over length-T inputs, then T^(1/3)/1000 <= Delta_T <= 41T^(1/3) for T >= 216. The upper bound holds for every input, while each T >= 216 has a rational lower-bound input. For every input with m distinct forecasts, C <= L + m, and the unrestricted-sample worst-case sparse order is Theta(m). For rational forecasts and accuracy, with binary-encoded multiplicities of separately assignable unit identities, a grid-free polynomial-bit-time procedure returns B <= L <= U, U - B < eta, and an exactly calibrated compact repair of cost at most U + m <= L + m + eta.

0.39

High-dimensional online calibration from harmonic weights

cs.LG stat.ML ·2026-10-06 ·Maxwell Fishelson, Mehryar Mohri
similarity 0.65
Abstract

We study the online calibration of multidimensional forecasts over an arbitrary convex set $Y\subseteq\mathbb{R}^d$ relative to an arbitrary error norm $\|\cdot\|_{L}$. For forecasting $d$ binary outcomes simultaneously ($Y=[0,1]^d$), we give the first algorithm that achieves $\varepsilon$-calibration in a number of rounds that is polynomial in $d$ for every fixed accuracy. It requires $d^{O(1/\varepsilon)}$ rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting ($Y=Δ_d$), we obtain the same $d^{O(1/\varepsilon)}$ rate, improving the $d^{\widetilde{O}(1/\varepsilon^2)}$ bounds of Peng and Fishelson et al. Our algorithm is simple: on each round, it outputs a harmonically weighted distribution over harmonically smoothed past outcomes. The same algorithm works for every forecast set and norm. More generally, it achieves $\varepsilon$-calibration after $\exp(O(γ(Y,L)/\varepsilon))$ rounds, where $γ(Y,L)$ is a geometric parameter defined by a matrix discrepancy problem. The harmonic weights are motivated by the fact that the discrete Hilbert transform matrix achieves the optimal discrepancy up to a universal constant, simultaneously for every $L$. This optimality result may be of independent interest.

0.28

Truthful Calibration Measures for Sequential Prediction

cs.DS cs.GTcs.LG ·2026-08-21 ·Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu
top venuetheory similarity 0.64
Abstract · To appear in SODA 2027

Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. On the positive side, we give two general reductions that transform a base calibration measure satisfying a uniform completeness condition into additively and multiplicatively approximately truthful measures, respectively. Applying the multiplicative reduction, for every $0<\varepsilon<1$ we construct a sound and complete calibration measure that is $1+\exp\left(-Ω(T^{1-\varepsilon})\right)$-multiplicatively truthful. This improves the approximate truthfulness guarantee of Haghtalab et al. (2024). We also prove a general transfer theorem showing that the uniform completeness of one calibration measure transfers to another when they are quantitatively related. Using this result, we show that every consistent calibration measure (Blasiok et al., 2023) satisfies uniform completeness and can serve as the base calibration measure to achieve $1 + o(1)$ multiplicative truthfulness.

0.30

Prediction with Expert Advice under Heavy-Tailed Losses

cs.LG stat.ML ·2026-10-10 ·Yuki Shibukawa, Shinji Ito
hot direction similarity 0.61
Abstract · 49 pages

We study prediction with expert advice over $T$ rounds with $K$ experts under heavy-tailed losses whose $(1+ε)$-moment is bounded by $θ>0$ for some $ε\in(0,1]$. In this setting, existing algorithms designed for the case $ε=1$ can be suboptimal when $ε<1$, suffering an additional polynomial dependence on $K$. We characterize the minimax pseudo-regret rate as $Θ((θT)^{\frac{1}{1+ε}}(\log K)^{\fracε{1+ε}})$ and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either $ε$ or $θ$, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither $ε$ nor $θ$ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when $ε$ and $θ$ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.

0.30

Model-Agnostic Online Certificate-Driven Calibration for Time Series Forecasting Under Distribution Shift

cs.LG ·2026-09-25 ·Chenfeng Huang, Zixuan Ma, George Michailidis
top venuehot directionhighly cited similarity 0.61
Abstract · Oral presentation at the 42nd Conference on Uncertainty in Artificial Intelligence (UAI 2026). Published in Proceedings of Machine Learning …

Time series out-of-distribution generalization requires forecasters to remain reliable when deployment dynamics differ from training conditions due to covariate shift, concept shift, and temporal dependence. Probably Approximately Correct Bayesian domain adaptation provides computable certificates by decomposing target risk into a source risk term, a source-to-target mismatch term, and a complexity term, but standard analyses rely on independent sampling and distributional stability, assumptions that are violated in time series by serial dependence and nonstationary shift. We propose a model-agnostic online martingale Probably Approximately Correct Bayesian framework that yields finite-sample certificates under temporal dependence and distribution shift. The certificate replaces independent-sample concentration with martingale concentration that adapts to loss scale and predictable variation. We use the certificate as a surrogate regularizer for online calibration by training a gated residual Bayesian head on top of a fixed forecasting backbone, producing a corrective update that reverts to the backbone prediction when the gate is closed. Online calibration combines a source risk anchor, a posterior-shift penalty, and a time-adaptive mismatch term computed from target windows observed before forecasting. It follows a predict-then-update protocol in which outcomes become available only after forecasting and are used to update subsequent predictions. Experiments across convolutional, attention-based, and large language model-based forecasters show improved stability and accuracy under covariate and concept shift.

0.76

Robust and Learned Online Matching in Growing Trees

cs.DS cs.LGmath.PR ·2026-09-30 ·Marek Gałązka, Hanna Wdowicka
theory similarity 0.60
Abstract · 14 pages, 1 figure, 1 table

We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret $O(\sqrt{n}\log^2 n)$, using $O(n^2\log n)$ arithmetic operations and $O(n)$ stored entries. The exact minimax rate remains open.

0.33

An $Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles

cs.LG stat.ML ·2026-10-27 ·Julien Weibel, Pierre Gaillard, Wouter Koolen, Adrien Taylor
theory similarity 0.60
Abstract

This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as $T^{3/4}$ (where $T$ is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as $T^{3/4}$. We answer that question, proving a universal worst-case regret lower bound $Ω(T^{3/4} m^{-1/4})$ for any projection-free algorithm that makes at most $m$ linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound $O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \})$.

0.12