High-Dimensional Calibration from Swap Regret

arXiv:2505.21460v2 Announce Type: replace Abstract: We study online calibration of multi-dimensional forecasts over an arbitrary convex set P subset R^d relative to an arbitrary norm |dot|. 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 |dot|_* unit norm ball, then one can obtain epsilon-calibrated forecasts after T = exp(ilde O(rho/epsilon^2)) rounds. When P is the d-dimensional simplex and |dot| is the ell_1-norm, the O(sqrt{Tlog d}) experts regret bound yields epsilon-calibrated forecasts after T = exp(ilde O(log d/epsilon^2)) = d^{ilde 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 |dot|. 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 geq exp(poly(1/epsilon)) (assuming d geq 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.

Source: arXiv cs.LG | 2026-08-12