High-Dimensional Calibration from Swap Regret

The paper considers the problem of online calibration of multidimensional outcomes over an arbitrary convex set $\mathcal{P}$. More formally, at time $t \in [T]$, the forecaster specifies a distribution $x_{t} \in \Delta(\mathcal{P})$, the adversary responds with $y_{t} \in \mathcal{P}$, and the forecaster is penalized by the calibration error measured with respect to a distance function $D$ as $\frac{1}{T}\sum_{p \in \mathcal{P}} \left(\sum_{t = 1} ^ {T} x_{t}(p)\right) D(\nu_{p}, p)$, where $\nu_{p} = \frac{\sum_{t = 1} ^ {T} x_{t}(p) y_{t}}{\sum_{t = 1} ^ {T} x_{t}(p)}$ corresponds to the empirical average of the predictions conditioned on the rounds where the prediction made is $p$. Prior work by Peng'25 proved that $\ell_{1}$-Calibration error (corresponding to $D(p, q) = ||p - q||$) can be achieved after $T = d^{\mathcal{O}(\frac{1}{\varepsilon ^ {2}})}$ rounds when $\mathcal{P} = \Delta_{d}$ is the simplex and $y_{t}$'s correspond to the cannonical basis vectors. Moreover, Peng'25 also showed that $T = d^{\Omega \left(\log \frac{1}{\varepsilon}\right)}$ rounds are necessary to achieve at most $\varepsilon$ $\ell_{1}$-Calibration error. Following up on Peng's work, the current paper does the following:

(1) It proposes an algorithm (TreeCal), which essentially coincides with Peng's algorithm, and establishes a more general result that if OLO (over $\mathcal{P}$) can be achieved in $\mathcal{O}(\sqrt{\rho T})$ external regret, then $\ell_{1}$-Calibration error can be achieved after $\left(\frac{\text{diam}(\mathcal{P})}{\varepsilon}\right) ^ {\mathcal{O}(\frac{\rho}{\varepsilon ^ {2}})}$ rounds. This recovers the result of Peng'25 by setting $\rho = \log d$, which follows from the regret guarantee of Hedge in learning with expert advice.

(2) It improves Peng's lower bound, showing that for $d \ge \text{poly}(\frac{1}{\varepsilon})$, $T = \exp(\text{poly}(\frac{1}{\varepsilon}))$ rounds are necessary to achieve at most $\varepsilon$ $\ell_{1}$-Calibration error. This shows that an exponential dependence on $\frac{1}{\varepsilon}$ is necessary and precludes the existence of bounds of the form $d^{\log \frac{1}{\varepsilon}}$ which were allowed in Peng's work.

This paper studies online calibration when the events and forecasts live in a high-dimensional space. The authors show that if $\rho$ is the rate of OLO under a convex set with certain norm, then there is a simple forecasting algorithm that achieves $(diam(P)/\epsilon)^{O(\rho/\epsilon)}$ calibration error. This result recovers [Peng 25] when norm is L-1 and set is d-dimensional simplex. They also establish a lower bound that improves the lower bound of Peng 25.

The technical approach consists of two main components:

1. Following [LSS25, KFO+25], the authors connect calibration (with bregman divergence as distance measure) to full swap regret with losses chosen as bregman divergence from the events $x_t$. on the one hand, this connection allows them to inherit the guarantees from the TreeSwap algorithm [DDFG24]. On the other hand, it provides an upper bound on the calibration error when using squared norm as the distance measure.
2. The authors show that the TreeCal algorithm [Peng25] can be recovered as a special case of TreeSwap with FTL as the base algorithm. They provide a novel and simplified analysis of TreeCal's calibration bounds by examining its difference from TreeSwap with BTL, resulting in a clean analysis that works for arbitrary norms and prediction sets.

The paper studies an online calibration problem. Unlike previous works which mostly focus on 1-dim online calibration, this work focuses on a high-dimensional setting where the goal here is to produce a sequence of multi-dimensional forecasts that minimizes the calibration error.

The main result of is an online algorithm that can guarantee vanishing calibration error relative to an arbitrary norm.

The paper consdiers the problem of issuing calibrated forecasts in d-dimensional Euclidean space. It develops the TreeCal algorithm, and analyses its average calibration error as function of the number of rounds. The proof goes through swap regret. A lower bound is also provided. Lower and upper bounds are exponentials of polynomials in 1/epsilon, though with different powers.

The paper studies the online calibration problem in high dimension setting. In the task of online calibration, there is a sequence of $T$ days and the algorithm needs to make a prediction $p_t$ at the beginning of each day $t$, then the nature (or the adversary) picks an outcome $i_t\in [d]$. The hope is that the algorithm is calibrated, roughly meaning that on average, the time that it predicts $p$, the empirical average is also $p$. The calibration error is mostly measured in $\ell_1$ distance in the literature, but other distance metric is well motivated as well.

The main contribution are two folds:

(1) On the algorithmic side, the paper generalizes the previous work of (Peng 2025) and gives a generic reduction from swap regret / external regret to calibration. In particular, the paper shows that whenever there exists an online linear optimization algorithm that has $O(\sqrt{\rho T})$ worst case regret, then for the corresponding calibration problem, it gives an $\epsilon$-calibrated algorithm after $T = \exp(O(\rho/\epsilon^2))$. For the most studied $\ell_1$ calibration, this matches the previous algorithm of (Peng 2025), for $\ell_2$ calibration, it gives a new results that otabin $\eps$-$\ell_2$ calibration in $(1/\epsilon)^{O(1/\epsilon^2)}$ days.

(2) On the lower bound side, the algorithm gives improved lower bound, showing that any online calibration algorithm that guarantees $\eps$ $\ell_1$ calibration error requires $T = \min \{\exp(\poly(d), \poly(\epsilon))\}$ days, this improves the previous lower bound of $d^{\Omega(\log(1/\epsilon))}$ of (Peng 2025). The lower bound is obtained via a smart reduction to the previous generic lower bound for swap regret minimization.

The paper considers the problem of high-dimensional online calibration. The recent work of Peng'25 showed a very surprising result that d-dimensional L1 calibration to error eps is achievable in d^(1/eps^2) steps. This is surprising, since in d dimensions the discretization of the simplex is of size exponential in d, and previous approaches required exp(d) steps. This paper recovers, and also significantly improves on this result from Peng'25 in many ways. The paper shows a bound which extends to other metrics beyond L1, such as L2 distance. Interestingly, the same algorithm can simultaneously achieve low calibration error simultaneously for all multiple norms. The paper gives a generic reduction from swap regret / external regret to calibration, and shows that the TreeCal algorithm introduced in Peng'25 is a special case of the earlier TreeSwap algorithm. This perspective on calibration is novel, significant and impactful. It greatly clarifies and helps understand the landscape of algorithms, and relations between different problems in this space. The paper also shows a stronger lower bound, showing that exp(poly(1/eps)) rounds are necessary, an exponential improvement over the lower bound in Peng'25.

The reviewers all found the paper to be very well written. It gives the reader a good lay of the land with respect to previous results, and also provides sufficient intuition for the results.

I believe that the results here are highly significant and of significant interest to a broad audience, and hence recommend that the paper be selected for an oral presentation. An oral presentation would give the broad Neurips audience exposure to recent advances in calibration, including the strong connections to swap regret pointed out in this work. I also encourage the authors to also use the presentation as an opportunity to introduce the work of Peng'25 to the audience.