High-Dimensional Calibration from Swap Regret

Abstract

We study online calibration of multi-dimensional forecasts over an arbitrary convex set $P\subset {\mathbb{R}}^d$ relative to an arbitrary norm $|\cdot |$. We connect this to external regret minimization for online linear optimization (OLO): if one can guarantee $O(\sqrt{\rho T})$ worst-case regret after $T$ rounds when actions are drawn from $P$ and losses from the dual $|\cdot {|}_{\ast }$ unit norm ball, then one can obtain $\epsilon$-calibrated forecasts after $T=\exp (\tilde{O}(\rho /{\epsilon }^2))$ rounds. When $P$ is the $d$-dimensional simplex and $|\cdot |$ is the ${\ell }_1$-norm, the $O(\sqrt{T\log d})$ experts regret bound yields $\epsilon$-calibrated forecasts after $T=\exp (\tilde{O}(\log d/{\epsilon }^2))=d^{\tilde{O}(1/{\epsilon }^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 $P$ and $|\cdot |$. 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 (Dagan et al., 2024; Peng and Rubinstein, 2024) 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 $\epsilon T$ ${\ell }_1$-calibration error over the $d$-dimensional simplex requires $T\ge \exp (\mathrm{poly}(1/\epsilon ))$ (assuming $d\ge \mathrm{poly}(1/\epsilon )$). This strengthens the corresponding $d^{\Omega (\log (1/\epsilon ))}$ lower bound of Peng (2025), and shows that an exponential dependence on $1/\epsilon$ is necessary.