High dimensional online calibration in polynomial time
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908315263434752 |
|---|---|
| author | Peng, Binghui |
| author_facet | Peng, Binghui |
| contents | In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require $\exp(d)$ days to achieve non-trivial calibration.
In this work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy $ε> 0$, our forecaster becomes $ε$-calibrated after $T = d^{O(1/ε^2)}$ days. We complement this result with a lower bound, proving that at least $T = d^{Ω(\log(1/ε))}$ rounds are necessary to achieve $ε$-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12].
Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_09096 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | High dimensional online calibration in polynomial time Peng, Binghui Machine Learning Data Structures and Algorithms Computer Science and Game Theory In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require $\exp(d)$ days to achieve non-trivial calibration. In this work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy $ε> 0$, our forecaster becomes $ε$-calibrated after $T = d^{O(1/ε^2)}$ days. We complement this result with a lower bound, proving that at least $T = d^{Ω(\log(1/ε))}$ rounds are necessary to achieve $ε$-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12]. Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows. |
| title | High dimensional online calibration in polynomial time |
| topic | Machine Learning Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2504.09096 |