CS Paper Radar

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

Eric Dai, Maxwell Fishelson

cs.DS stat.MLcs.GTcs.LG ·submitted 2026-10-06 02:17 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Matching Lower Bound for Online Smooth Calibration

cs.LG stat.ML ·2026-11-11 ·Kaixuan Ji, Quanquan Gu
theory similarity 0.70
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.

0.11

Sharp Integrality Gaps in Calibration Distance

cs.LG math.PR ·2026-10-05 ·Zinan Wang, Xinhao Yang
theory similarity 0.63
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

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.62
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

Optimal No-Regret Learning for Repeated Prophet Inequality

cs.LG ·2026-09-20 ·Kun Wang
theory similarity 0.61
Abstract

We study repeated prophet inequalities under prefix feedback. In each of $T$ rounds, a learner encounters fresh values drawn independently from $n$ boxes with unknown $[0,1]$-supported distributions in a fixed order and must irrevocably accept one, observing only the prefix up to its stopping box. Regret is measured against the optimal stopping policy that knows the distributions. We give an efficient algorithm achieving $\widetilde O(\sqrt{T})$ expected regret, matching the lower bound up to logarithmic factors. Our algorithm explores directly through near-optimal policies, combining empirical backward induction with box-specific reach bonuses. A relative-drop aggregation rule then exploits the nesting structure of observed prefixes to preserve exploration, thereby removing the polynomial dependence on the box number $n$. This resolves an open question posed by Liu et al. (2025).

0.27

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

cs.IT cs.LG ·2026-08-27 ·Vaneet Aggarwal
theory similarity 0.61
Abstract

We study sequential prediction of binary marks whose log-odds are a linear function of all past inputs. The inputs are independent uniform signs. The coefficient of the input observed $j$ steps earlier is unknown, but its absolute value is at most a known number $r_j$, and $\sum_j r_j\le B$. A learner is judged by its expected cumulative log loss in excess of the loss of the true conditional probabilities. We show that for every such sequence $r$ and every horizon $T$, the minimax value of this regret lies between $c\,Γ_T(r)/\max\{1,B^2\}$ and $\frac12Γ_T(r)$, where $Γ_T(r)=\sum_{j\le T}\log(1+(T-j+1)r_j^2)$ and $c$ is an absolute constant. The term for lag $j$ combines the size bound $r_j$ with the number $T-j+1$ of rounds in which that lag influences a prediction, and no monotonicity or other regularity of $r$ is needed. The upper bound is attained by a Bayesian mixture with independent Gaussian priors. For the lower bound, we apply the van Trees inequality at each prediction step and then bound the expected log-determinant of the random matrix whose rows are the lagged input vectors. We also characterize when $\frac12$ is the exact leading constant: for envelopes with a common bound $B$, possibly changing with $T$, the regret is asymptotic to $\frac12Γ_T(r)$ if and only if $\sum_{j\le T}\min\{1,(T-j+1)r_j^2\}=o(Γ_T(r))$. This gives, for example, $\log^2(A^2T)/(8α)$ for $r_j=Ae^{-αj}$, whereas for $r_j=Aj^{-s}$ with $s>1$ the regret is of order $T^{1/(2s)}$ and its ratio to $Γ_T(r)$ stays below $\frac12$. Finally, for a known horizon, an online Newton predictor with features scaled by $r_j$ attains regret of order $Γ_T(r)$ with polynomial computation per round.

0.10

No-Regret Language Generation

cs.LG stat.ML ·2026-10-16 ·Jiaxun Li, Vinod Raman, Ambuj Tewari
similarity 0.59
Abstract

We introduce no-regret generation, which requires a generator to make a sublinear number of mistakes uniformly over all demonstration sequences and compatible target languages. We also formulate an agnostic variant that allows arbitrary demonstrations that may not be compatible with any languages. For both settings, we introduce tree-based mistake-forcing dimensions that exactly characterize finite-horizon minimax complexity and establish necessary and sufficient conditions for no-regret generation. Our characterizations reveal a rich spectrum of generation rates: up to constant rescaling, every admissible nondecreasing profile is attainable in both the realizable and agnostic settings. Finally, we connect generation complexity to online prediction: for language classes of finite Littlestone dimension \(d\), we obtain realizable mistake bounds of \(O(d\log(1+T/d))\) and agnostic regret bounds of \(O(\sqrt{dT\log(1+T/d)})\). The realizable bound is optimal up to universal constants.

0.21

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

cs.LG stat.ML ·2026-09-23 ·Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta +2 more
similarity 0.59
Abstract

Prediction with expert advice is a fundamental problem in online learning. When the time horizon $T$ is known in advance, the minimax cumulative regret over $n$ experts is asymptotically $\sqrt{\frac{T \ln n}{2}}$. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to $T$, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time $t$, the best known guarantee has been $\sqrt{t \ln n}$---a factor of $\sqrt{2}$ worse---and it has remained unknown whether this factor of $\sqrt{2}$ is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies $R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$ simultaneously for every $t \ge 1$.

0.33

High-Probability Regret Bounds for Feel-Good Thompson Sampling

cs.IT stat.MLcs.LG ·2026-10-14 ·Xuheng Li, Qingyue Zhao, Quanquan Gu
similarity 0.59
Abstract · 22 pages

Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

0.19