2025/05/27 by Maxwell Fishelson, Fishelson, Maxwell, Noah Golowich +5 · 1 voice · 2 citations
Computer Science · #Neural Networks and Applications #cs.DS #cs.GT #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2505.21460
openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the online calibration of multi-dimensional forecasts over an arbitrary convex set P ⊂ ℝd relative to an arbitrary norm \Vert⋅\Vert. 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 \Vert ⋅ \Vert_* unit norm ball, then it is also possible to obtain ε-calibrated forecasts after T = exp(O(ρ/ε2)) rounds. When P is the d-dimensional simplex and \Vert ⋅ \Vert is the ℓ1-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/ε2)) = dO(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 P and \Vert ⋅ \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 ℓ1-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.