High-Dimensional Calibration from Swap Regret
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912398315618304 |
|---|---|
| author | Fishelson, Maxwell Golowich, Noah Mohri, Mehryar Schneider, Jon |
| author_facet | Fishelson, Maxwell Golowich, Noah Mohri, Mehryar Schneider, Jon |
| contents | We study the online calibration of multi-dimensional forecasts over an arbitrary convex set $\mathcal{P} \subset \mathbb{R}^d$ relative to an arbitrary norm $\Vert\cdot\Vert$. We connect this with the problem of external regret minimization for online linear optimization, showing that if it is possible to guarantee $O(\sqrt{ρT})$ worst-case regret after $T$ rounds when actions are drawn from $\mathcal{P}$ and losses are drawn from the dual $\Vert \cdot \Vert_*$ unit norm ball, then it is also possible to obtain $ε$-calibrated forecasts after $T = \exp(O(ρ/ε^2))$ rounds. When $\mathcal{P}$ is the $d$-dimensional simplex and $\Vert \cdot \Vert$ is the $\ell_1$-norm, the existence of $O(\sqrt{T\log d})$-regret algorithms for learning with experts implies that it is possible to obtain $ε$-calibrated forecasts after $T = \exp(O(\log{d}/ε^2)) = d^{O(1/ε^2)}$ rounds, recovering a recent result of Peng (2025).
Interestingly, our algorithm obtains this guarantee without requiring access to any online linear optimization subroutine or knowledge of the optimal rate $ρ$ -- in fact, our algorithm is identical for every setting of $\mathcal{P}$ and $\Vert \cdot \Vert$. Instead, we show that the optimal regularizer for the above OLO problem can be used to upper bound the above calibration error by a swap regret, which we then minimize by running the recent TreeSwap algorithm with Follow-The-Leader as a subroutine.
Finally, we prove that any online calibration algorithm that guarantees $εT$ $\ell_1$-calibration error over the $d$-dimensional simplex requires $T \geq \exp(\mathrm{poly}(1/ε))$ (assuming $d \geq \mathrm{poly}(1/ε)$). This strengthens the corresponding $d^{Ω(\log{1/ε})}$ lower bound of Peng, and shows that an exponential dependence on $1/ε$ is necessary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21460 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | High-Dimensional Calibration from Swap Regret Fishelson, Maxwell Golowich, Noah Mohri, Mehryar Schneider, Jon Machine Learning Data Structures and Algorithms Computer Science and Game Theory We study the online calibration of multi-dimensional forecasts over an arbitrary convex set $\mathcal{P} \subset \mathbb{R}^d$ relative to an arbitrary norm $\Vert\cdot\Vert$. We connect this with the problem of external regret minimization for online linear optimization, showing that if it is possible to guarantee $O(\sqrt{ρT})$ worst-case regret after $T$ rounds when actions are drawn from $\mathcal{P}$ and losses are drawn from the dual $\Vert \cdot \Vert_*$ unit norm ball, then it is also possible to obtain $ε$-calibrated forecasts after $T = \exp(O(ρ/ε^2))$ rounds. When $\mathcal{P}$ is the $d$-dimensional simplex and $\Vert \cdot \Vert$ is the $\ell_1$-norm, the existence of $O(\sqrt{T\log d})$-regret algorithms for learning with experts implies that it is possible to obtain $ε$-calibrated forecasts after $T = \exp(O(\log{d}/ε^2)) = d^{O(1/ε^2)}$ rounds, recovering a recent result of Peng (2025). Interestingly, our algorithm obtains this guarantee without requiring access to any online linear optimization subroutine or knowledge of the optimal rate $ρ$ -- in fact, our algorithm is identical for every setting of $\mathcal{P}$ and $\Vert \cdot \Vert$. Instead, we show that the optimal regularizer for the above OLO problem can be used to upper bound the above calibration error by a swap regret, which we then minimize by running the recent TreeSwap algorithm with Follow-The-Leader as a subroutine. Finally, we prove that any online calibration algorithm that guarantees $εT$ $\ell_1$-calibration error over the $d$-dimensional simplex requires $T \geq \exp(\mathrm{poly}(1/ε))$ (assuming $d \geq \mathrm{poly}(1/ε)$). This strengthens the corresponding $d^{Ω(\log{1/ε})}$ lower bound of Peng, and shows that an exponential dependence on $1/ε$ is necessary. |
| title | High-Dimensional Calibration from Swap Regret |
| topic | Machine Learning Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.21460 |