Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.09273 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914584314511360 |
|---|---|
| author | Huang, Zhiming Morgenstern, Jamie Roth, Aaron Zhang, Claire Jie |
| author_facet | Huang, Zhiming Morgenstern, Jamie Roth, Aaron Zhang, Claire Jie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09273 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Instance-Adaptive Online Multicalibration Huang, Zhiming Morgenstern, Jamie Roth, Aaron Zhang, Claire Jie Machine Learning 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. |
| title | Instance-Adaptive Online Multicalibration |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2605.09273 |