Abstract
We study the online calibration of multi-dimensional forecasts over an arbitrary convex set P ⊂ R^d relative to an arbitrary norm ·. We connect this with the problem of external regret minimization for online linear optimization, showing that if it is possible to guarantee O(√ρ T) worst-case regret after T rounds when actions are drawn from P and losses are drawn from the dual · _* unit norm ball, then it is also possible to obtain ε-calibrated forecasts after T = exp(O(ρ /ε²)) rounds. When P is the d-dimensional simplex and · is the ℓ₁-norm, the existence of O(√Tlog d)-regret algorithms for learning with experts implies that it is possible to obtain ε-calibrated forecasts after T = exp(O(logd/ε²)) = d^O(1/ε²) 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 P and · . 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 ℓ₁-calibration error over the d-dimensional simplex requires T ≥ exp(poly(1/ε)) (assuming d ≥ poly(1/ε)). This strengthens the corresponding d^Ω(log1/ε) lower bound of Peng, and shows that an exponential dependence on 1/ε is necessary.