Abstract:We study online multicalibration beyond the worst-case. We give a single, efficient algorithm which dynamically interpolates between benign and worst-case sequences by adaptively refining a dyadic grid of prediction values. Its error is controlled by the number of leaves in the refinement tree. Our analysis recovers the known $\widetilde O(T^{2/3})$ worst-case-optimal rate for online multicalibration, while simultaneously automatically adapting to easier instances: in the marginal stochastic setting it obtains a rate of $\widetilde O(\sqrt T)$, and for piecewise-stationary means with $J$ segments its rate is $\widetilde O(\sqrt{JT})$. More generally, the rate depends on a threshold-complexity measure of the predictable mean process relative to the group family. We show that this dependence is tight up to logarithmic factors.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.09273 [cs.LG] |
| (or arXiv:2605.09273v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.09273 arXiv-issued DOI via DataCite (pending registration) |
From: Zhiming Huang [view email]
[v1]
Sun, 10 May 2026 02:45:59 UTC (53 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。