arXiv：cs.LG· Eric Dai, Maxwell Fishelson·· 4 小时前AI 评分33
序列校准突破 T^{2/3}：首个显式指数 O(T^{0.662942288}) 上界
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
AI 导读
研究者为符号保持复用博弈提出两阶段递归标注策略，得到 O(n^α t^β) 界，并将 Dagan 等人的归约改为仅用 O(log T) 次博弈调用，从而给出序列校准的显式上界 O(T^{0.662942288})。这是序列 ℓ1 校准误差中首个低于经典 Foster-Vohra O(T^{2/3}) 的显式指数。
正文
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^{\alpha}t^\beta)$ 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.
| Subjects: | Machine Learning (stat.ML); Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07623 [stat.ML] |
| (or arXiv:2610.07623v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07623 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Maxwell Fishelson [view email]
[v1]
Tue, 6 Oct 2026 02:17:23 UTC (41 KB)
来源：arXiv：cs.LG · arxiv.org