High-Dimensional Calibration from Swap Regret

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{\rho T})$ worst-case regret after $T$ rounds when actions are drawn from $\mathcal{P}$ and losses are drawn from the dual $\Vert \cdot {\Vert }_{\ast }$ unit norm ball, then it is also possible to obtain $ϵ$-calibrated forecasts after $T=\exp (O(\rho /{ϵ}^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})$ 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 $\rho$ -- 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. The resulting algorithm is highly efficient and plays a distribution over simple averages of past observations in each round.

Finally, we prove that any online calibration algorithm that guarantees $ϵT$ ${\ell }_1$-calibration error over the $d$-dimensional simplex requires $T\ge \exp (\mathrm{poly}(1/ϵ))$ (assuming $d\ge \mathrm{poly}(1/ϵ)$). This strengthens the corresponding $d^{\Omega (\log 1/ϵ)}$ lower bound of Peng 2025, and shows that an exponential dependence on $1/ϵ$ is necessary.