High-Dimensional Calibration from Swap Regret
Authors: Maxwell Fishelson
Noah Golowich
Mehryar Mohri
Jon Schneider
Venue: NeurIPS 2025 oral ()
Keywords: Calibration
Swap Regret
Online Learning
Primary area: theory
TL;DR: An algorithm for calibrating forecasts of high-dimensional outcomes.

Abstract: We study the online calibration of multi-dimensional forecasts over an arbitrary convex set $\mathcal{P} \subset \mathbb{R}^d$ relative to an arbitrary norm $\Vert\cdot\Vert$. We connect this with the problem of external regret minimization for online linear optimization, showing that if it is possible to guarantee $O(\sqrt{\rho T})$ worst-case regret after $T$ rounds when actions are drawn from $\mathcal{P}$ and losses are drawn from the dual $\Vert \cdot \Vert_*$ unit norm ball, then it is also possible to obtain $\epsilon$-calibrated forecasts after $T = \exp(O(\rho /\epsilon^2))$ rounds. When $\mathcal{P}$ is the $d$-dimensional simplex and $\Vert \cdot \Vert$ is the $\ell_1$-norm, the existence of $O(\sqrt{T\log d})$ algorithms for learning with experts implies that it is possible to obtain $\epsilon$-calibrated forecasts after $T = \exp(O(\log{d}/\epsilon^2)) = d^{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 $\mathcal{P}$ and $\Vert \cdot \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. 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(\mathrm{poly}(1/\epsilon))$ (assuming $d \geq \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.

High-Dimensional Calibration from Swap Regret
Maxwell Fishelson" maxfishdmit. edu
Noah Golowich nzgōmit. edu
Mehryar Mohri! mohri@google.. com
Jon Schneider jachnei @google jschne@@google..o com
Abstract
We study the online calibration of multi-dimensional forecasts over arbitrary convex set P C TRd relative to an arbitrary norm ||-I1- We connect this with the problem of external regret minimization for online linear optimization, showing that it is possible to guarantee D(yp')) worst-case regret after I' rounds when actions are drawn from P and losses are drawn from the dual ||-I1, unit norm ball, then it is also possible obtain e-calibrated forecasts after T exp exp(O(p/e ((pppe)))))))))))))))(()))) rounds. When P is the d-dimensional simplex and ||-|| is the -norm,, the existence (v Tog regret algorithms for learning with experts implies that it is possible to obtain e-calibrated forecasts after = exp(O d/²") = doa/e") rounds, recovering recent result of [Pen25].
Interestingly, algorithm obtains this guarantee without requiring access any online linear optimization subroutine or knowledge of the optimal rate p- in fact, show that
our algorithm is identical for every setting of P and ||-I|- Instead, the optimal regularizer for the above OLO problem can be used to upper bound the above calibration error by swap regret, which the recent TreeSwap algorithm (DDDFG24, PR24]) with Follow-The-Laee subroutine. The resulting algorithm is highly efficient and plays distribution over simple averages of past observations in each round.
then minimize by running
as a
Finally, we prove that any online calibration algorithm that guarantees éT' l calibration error over the d-dimensional simplex requires T 2 exp(poly(1/e)) (assuming d 2 poly(1 (1/e)). This strengthens the corresponding d 1/e) lower bound of [Pen25], and shows that exponential dependence 1/c is necessary.
Introduction
Consider the problem faced by forecaster who must report probabilistic predictions for sequence of events (e.g. whether will rain not tomorrow). One of the most common methods to evaluate the quality of such a forecaster is to verify whether they are calibrated: for example, does it indeed rain with probability 40% on days where the forecaster makes this prediction? In addition to calibration being natural property to expect from predictions, several applications across machine learning, fairness, and game theory require the ability to produce online calibrated predictions [ZME20, GPSW17, HJKRR18, FV97].
When events have binary outcomes, calibration can be quantified by the notion of expected calibration error, which measures the expected distance between a prediction made by forecaster and the actual empirical probability of the outcome on the days where they made that prediction. seminal result by Foster and Vohra [FV98], it was proved that it is possible for online forecaster to efficiently
MIT.
MIT. Supported by NSF Graduate Research Fellowship and Fannie Hertz Foundation Graduate Fellowship.
*Google Research and Courant Institute of Mathematical Sciences, New York.
Google Research.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

guarantee a sublinear calibration error of O(T2/3) against any adversarial sequence of T binary events. Equivalently, this can be interpreted as requiring at most O 3) rounds of forecasting to guarantee an per-round calibration error on average.
However, many applications require forecasting sequences of multi-diimensional outcomes. The previous definition of calibration eгror easily extends to the nulti-dimensional setting where pre- dictions and outcomes belong to d-dimensional convex set P IR Specifically, if a forecaster makes a sequence of predictions Pi, ................................ ........ E P for the outcomes yı, 92,..., Vr E P, their ||-II- -allbaabirraioon error (for any norm |I-I] over IR is given by
Callg T
=
Σ 1=1
lIp
Upp
where Up, is the average of the outcomes y/ on rounds where the learner predicted pt-
The algorithm of Foster and Vohra extends to the multidimensional calibration setting, but at the cost of producing bounds that decay exponentially in the dimension d. In particular, their algorithm only guarantees that the forecaster achieves average calibration error of after (1/e)a(d) rounds. Until recently, no known algorithm achieved a sub-exponential dependence on d in any non-trivial instance of multi-dimensional calibration.
In 2025, [Pen25] presented new algorithm for digh-dimensional calibration, demonstrating that possible to obtain & f-caalibration rates of eT in (0(1/e)) rounds for predictions over the d-dimensional simplex (i.e., multi-class calibration). In particular, this is the first known algorithm achieving polynomial calibration rates in d for fixed constant e. [Pen25] complements this with a lower bound, showing that in the worst case (log 1/c) rounds are necessary to obtain this rate (implying that a fully polynomial bound poly(d, 1/c) is impossible).
1.1 Our results
Although the algorithm of [Pen25] simple to describe, analysis fairly nuanced and tailored to fi-calibration over the simplex (e.g., by analyzing the KL divergence between predictions and distributions of historical outcomes). We present a very similar algorithm (TreeCal) for multi- dimensional calibration over arbitrary convex set P C Rd, but with simple, unified analysis that provides simultaneous guarantees for calibration with respect to any norm [|-||. [].. In particular, we prove the following theorem.
Theorem 1.1 (Informal restatement of Corollary C.5). Fix a convex set P and a norm || ||. Assume there exists a function R : P - R that 1-strongly-come with respect to || and has range (maxzep R(x)= milppp R(x)) at most p. Then TreeCal guarantees that the calibration error of its predictions bounded by Call: S ET for Z (P))m//pPP))))/e)
Interestingly, the function R(p) and parameter p appearing in the statement of Theorem 1.1 have an independent tearning- interpretation: if we consider the online linear optimization problem where a learner plays actions in P and the adversary plays linear losses that are unit bounded the dual norm Il. then it is possible for the learner to guarantee regret bound of at most O( ppT) by playing Follow- Follow-The-Ree The- -ete-Rerariized--- Leaderr (FTRL) with R(p) as a regularizer. In fact, since universality results for mirror descent guarantee that some instantiation of FTRL achieves near-optimal rates for online linear optimization (as long as the action and loss sets are centrally convex) [SST11, 11, GSJ24), this allows to relate the performance of Theorem 3.1 directly to what rates are possible in online linear optimization.
Corollary 1.2 (Informal restatement of Corollary C.6). Let P C Idd be a centrally symmetric convex set, and let C = (y E Rd ||y||. I 1} for some norm |1-1]. Then if there exists an algorithm for online linear optimization with action set P and loss set C that incurs regret at most O(VPT), TreeCal guarantees that the calibration ervor of its predictions is bounded by Cal < cT for T> (diam (I(m )(oo))))))
I-ll
Theorem 1.1 and corollary allow us to immediately recover several existing and novel bounds on calibration error in a variety of settings:

---

When P is the d-simplex Aa and ||-I] is the fi-norm, the existence of the negative entropy regularizer R(x) Σ ay log 2; (which is 1-strongly convex w.r.t. the l norm with range p = log d) implies that the & calibration error of TreeCal is at most (1/6) d/+") =
(01//e), This recovers the result of [Pen25].
When P the & ball and ||-Il is the l norm, the Euclidean regularizer (R(x) = [|x]13)
implies a calibration bound of (1/e) (notably, this bound is independent of d).
It should be emphasized here that running TreeCal does not require any online linear optimization subroutine, nor any knowledge of these regularizers R(x) or optimal rates p. TreeCal has no functional dependence on any specific ||-II. It achieves l-ll-calibratioon at the above rate (Theorem 1.1) for all ||-|| simultaneously. The TreeCal algorithm nearly identical to the algorithm of [Pen25] both algorithms initialize tree of sub-forecasters and at each round play a uniform combination of some subset of them (see Figure 1).
The novelty in our analysis stems from the observation that TreeCal is simply a specific instantiation of the TreeSwap swap regret minimization algorithm [DDFG24, PR24] and can be analyzed directly in this way. In particular, our analysis consists of the following steps:
1. First, minimizing calibration error can be reduced to minimizing swap regret, generalizing an idea of [LSS25, FKO+25]. That is. it is possible assign the learner loss functions Le : P + I. at each round such that their calibration error is upper bounded by the gap between the total loss they received, and the minimal loss they could have received after applying an arbitrary "swap function" π P + P to their predictions.
In fact, any strongly convex function R (w.rtt the norm ||-I]) gives rise to such reduction, by setting the loss function (p()) to equal the Bregman divergence Dn(v.pp)
2. Second, the TreeSwap algorithm of [DDFG24, PR24] provides a general recipe for convert- ing external regret minimization algorithms into swap regret minimization algorithms. We obtain TreeCal by plugging in the Follow-The-LLeee Leader algorithm (the learning algorithm which simply always best responds to the current history) into TreeSwap.
3. Instead of analyzing the swap regret bound of TreeSwap with Sallow-The-Leadee (which may not have a good enough external regret bound, as discussed in Section 3.3), we instead analyze the swap regret of TreeSwap with Re-ThheLeader (the fictitious algorithm that best responds to the current history, including the current round). Though it is not possible to actually implement Be-The-Leader due to its clairvoyance, we use it as tool for analysis. We then relate the calibration error of TreeSwap with Be- Re-The-Leader to that of TreeSwap with Follow-The similar predictions.
using the fact that Be- Be-The-Le The-Leader and Follow-The
make
In the above step 1, we will choose R to be |l-l|-norm 1-strongly convex, which guarantees that DR(vlP) 2 lly -u-pp pll Going through the analysis, this actually leads to the stronger guarantee that TreeCal minimizes squared- -orm calibration error.
Theorem 1.3 (Informal restatement of Theorem 3.1). Fix a convex set P and a norm || there exists a function R : P - R that is 1-strongly-conver with respect to || || and has range (maxzep R(x)- - minpep R())) at most p. Then TreeCal guarantees that the calibration ervor of its predictions bounded by Caill T T (Ptami-((P)//e))) (2)ooo)))
||. Assume
Note here we have only singly-cxponente dependence on 1/e. We arrive at Theorem 1.1 as a corollary of this result by simply applying Cauchy- -chhaar. Finally, we strengthen the lower bound of [Pen25] by showing an exponential dependence on 1/e is necessary.
Theorem 1.4 (Informal restatement of Theorem 4.3). There is a sufficiently small constant e > 0 so that the following holds. Fix any > 0, d E N. Then for any T < explc- banfcc-miud'"" min(d-/14 (anddd/,,,.//81)) -1/63), there is an oblivious adversary producing a sequence of outcomes so that any learning algorithm must Il-Il: T incur & -a-caiibratoon error Call
'One minor difference is that the algorithm of [Pen25] regularizes each sub-forecaster by slightly mixing their prediction with the uniform distribution, which TreeCal does not require.
3

---

Unlike the lower bound of [Pen25]. this lower bound requires no specialized construction. Instead, follows from the original observation of [FV98] that any algorithm for online calibration can be used to construct an algorithm for swap regret minimization by simply best responding sequence of calibrated predictions of the adversary's s losses. The existing lower bound for swap regret in (DFG+24) then immediately precludes the existence of sufficiently strong calibration bounds (e.g.. of the form (log 1/e), which was still allowed by the work of [Pen25]).
Using similar technique, in Theorem D.2, show similar lower bound for & calibration, namely that (xpp(2((m))m))e))) (minmmmddd }))) time steps needed to achieve &g calibration error at most T. For e ? this bound tight up polynomial in the exponent.
We discuss additional related work in the appendix.
2 Setup
For positive integer n, we let [0: 10:n. n- 1] denote the sequence 0,1....,m 1, and [n]] denote the sequence 2, We say convex set S IRd is centrally symmetric if S -s E for all 8 E Rd. A norm ||-I| is function corresponding to a convex, bounded, centrally-symmetric S of the form ||||| inf {c E R2ols E cS). The corresponding dual norm is defined |elll
sup {(s, b) ||||| S 1}}.
2.1 Calibration
We consider the following setting of multi-dimensional calibration. Positive integers d E N repre- senting the number of dimensions and T E representing the number rounds are given. We let P C Rd denote bounded convex subset of IRd An adversary and learning algorithm interact for total of 7 timesteps; at each time step E [7]:
The learning algorithm chooses distribution x, A(P) with finite support.
The adversary observes and chooses an outcome Y/ E P.
In order for the learner to be calibrated, we would like the average outcome conditional on the learner making specific prediction be "close" We formalize this as follows. For point p P, we define Up to be the average outcome conditioned on the learner predicting p. that is:
Up = E1=1 (p) y1
T
Σ Ei=1 (p)
Fix distance measure D X + Rzo, namely an arbitrary non-negative valued function on P x P. Given distance measure D, we define the D-calibration error as follows:
( = Σ
Σ
T
xe(e)) D(vp.p).
PEP
In the event that D(p.g) |pp - 4/1 will write Call| |1ll
(x1:1,
Cal (X1:1 Birr), and
define Calll: 12 (XI.T .1.7) analogously.
2.2 Regret minimization
For sequence of actions "I.....P .P and loss functions l..... ,6r R. define
ExtRegy (1:)) = sup ΣΣ 4(p)) ((()))(((pp))
P'EP PEP
'Some authors refer to this setting as "pseudo-calibration or "distributional calibration", reserve the term "calibration" for the setting where the learner is required to randomly select pure forecast pt E P each round instead of distribution. In Appendix E we describe how to extend our results this pure-strategy setting of calibration.

---

For sequence of distributions X1.'. :T E A(P) and loss functions L,, ,6. P + R, we define
FullSwapRegy (X1.1, (:1) sup Σ T:P
((1) t=1 pEP
ΣΣ
(2)
Here, adopt the convention of [FKO*25], referring to the latter quantity as Full Swap Regret to emphasize that we consider all swap transformations π P - P (instead of e.g. just linear transformations T).
Throughout, we consider the performance of regret minimizing algorithms. These algorithms sequen- tially map loss functions f,,- fr to actions p1,"." ,Pr action distributions X1,". Xy with the goal of minimizing the above quantities. We consider the performance these algorithms on adversarially selected loss functions from set L. Abusing notation slightly, for an external regret minimizing algorithm Alg: LT + pm we define
ExtRegr(AIg) = sup ExtRegr (Alg(f1:r)) (1:r)
(3)
ELTECT
and for full swap regret minimizing algorithm Alg: : L A(P)T, we define
FullSwapReg, :- sup fITECT
FullSwapRegy (Alg(l1:T),
We will denote the /th action played by Alg sequence of losses f1.T by Alg, (L1.)) One important subclass of external regret minimization problems is the setting online linear optimization (OLO), where all loss functions in l are linear. Here slightly abuse notation and identify L with subset of Rd (with the understanding that an element E C refers to the linear loss function {(p) = (p, E)). Although we will never actually employ any OLO algorithms themselves, the calibration bounds obtain will be closely related to optimal regret bounds for instances of OLO (we discuss this further in Section 2.4).
2.3 From swap regret to calibration
As noted in [LSS25, FKO+ 25], calibration with distance measure D that corresponds to Bregman divergence can be written as full swap regret with loss functions given by the associated proper scoring rule. Given convex function R - R. the Bregman divergence associated to R. DR P P + R20, is defined as?
Da(vlp) = R(y) R(p) (V R((p)yy
Geometrically, this divergence is defined by taking the hyperplane tangent to R at and computing the difference in height between R and the hyperplane y (see Figure 2).
When viewed as loss function in p. the Bregman divergence DR(ylp) also has the property that is proper scoring rule. This refers to the fact that if y is drawn from some distribution y APP), the optimal response p (to minimize the expected loss Dr(rlp)) is simply the expectation ÿ = Eyy- [y]- In partieular, have the following lemma.
Lemma 2.1. For any y E A(P) and convex function R : P + RR let Ey-ylv]- and R(y) Ey [R(y]]. For all p E P, Eyy-y [DRyllD DR ( p) + R(y) R(g). In particular, E(p) E [DR(ylp)] minimized at p = ÿ at value of R(y) R(y) (Figure 3).
This implies the following connection between full swap regret and calibration.
Lemma 2.2. Fix any convex function R P R. For any sequence of distributions X1, X2. XT E (PP) and outcomes y1, y2. . E P, define the sequence of loss functions ... Ex via tx(p) DR(wel)). Then,
l ....,....
FullSwapReg (xi.,, (IT)) Cal (x1.r, V1rr).
The proofs of Lemmas 2.1 and 2.2 may be found in Appendix B.
In the event that R is not differentiable, we replace the V R((() term with any element of the sub uub-gradient p. When P is open and p the boundary, the V R(p)) term represents the inward directional gradient.
5

---

2.4 Rates and regularization
In order to reduce our general calibration problem to a swap regret minimization problem (via Lemma 2.2), we will need to construct convex function R whose Bregman divergence upper bounds our distance measure. It turns out that the optimal choice of such a function closely related to the design of optimal regularizers for online linear optimization. In this section, we describe this functional optimization problem and detail this connection.
We say that a convex function R: P + R. is a-strongly convex with respect to a given norm ||-I| if for any points y. P E P is the case that R(y) 2 R(p) (V R(p). y p) + ||y pll Equivalently, the Bregman divergence must satisfy DR(VlP) 2 a lly pll². Thus, 11-12-calibration error is bounded by D DR-calibration error if R is Il-l|-norm I-strongly convex.
Our later analysis will need not only R to be strongly convex with respect to our norm, but for the Bregman divergence to have small maximal value. Motivated by this, we will say that a convex function R: - I has rate p with respect to a given norm |I-ll if: (1) R. 1-strongly convex with respect to 1-|1. and (2) the range of the Bregman divergence is at most p. i.c., maxy.peP DR(ylD) S p. We define Rate(P, (P, I1-Il) to be the infimum of the rates of all 1-strongly convex functions R: P R.
As mentioned earlier, we call this quantity a "rate" due to its connection with the optimal re- gret rates for online linear optimization. For a learning algorithm Alg LT - pp, we de- fined (in (3) ExtRegr (Alg) to be the worst-case regret against any sequence f1T of T losses. It is known that for any fixed action set and loss set, the optimal worst-case regret bound is of the form /RateoLo ()- T + o(vT), for some constant Rateolo L). Formally, we define Rateolo lim supr infaig #
One important class of learning algorithms for online linear optimization is the class of Follow- The-RRegllarized-Leee Leader (FTRL) algorithms. Each algorithm in this class is specified by convex "regularizer" function R: P - R. and at round i selects the action pt argmin Σ (p. (a) R(p). The work of [SST11] 1] and [GSJ24] shows that there always exists some instantiation of FTRL which achieves (up to universal constant factor) the optimal regret rate of / (P,t T o( o(VT) defined above. Moreover, the optimal regularizer for this instance can be constructed by solving similar functional optimization problem over strongly convex regularizers R, as described in the following theorem.
Theorem 2.3. Let P and L be centrally symmetric convex sets. Then, if the function R: P - R. strongly-conven with respect to the norm ||- and has range p (i.e. maXpep R(p) minpep R(p) p). then RateoLo (P, L) S p. Conversely, there exists a function R - R that is 1 1-strongly-comee with respect to || lll.. and has range O (RatteoLO(P.L) L)).
Proof. The first result (that RateoLo(P. (P,C) S follows from the standard analysis of FTRL see e.g. Theorem 5.2 in [H 16]. The converse result follows from Theorem 2 of [GSJ24].
Theorem 2.3 allows us to relate the quantity Rate(P, II-II) to the quantity Rateolo (P, C) (where L
chosen be the unit dual norm ball). Note that there is slight difference in the two functional optimization problems defined above the one for Rate []-Il) asks us to bound the range of the Bregman divergence of R, while the one for Rateolo (Po L) asks us to bound the range of R itself. While these two quantities do not directly bound each other (the negative entropy function R(p) =>> Σ P. log P; has bounded range over the simplex but unbounded Bregman divergence), we can nonetheless show that optimal solutions to one problem can be used to construct optimal solutions to the other problem of similar quality.
Lemma 2.4. If the action set P centrally symmetric and Eye E Rd llell. S 1) (i.e. the unit bull in the dual norm to [|-I),, then Rateolo (P, L) @(Rate(P, I1-11)).
3 Main result
We now describe our main algorithm for calibration, TreeCal (Algorithm 1), As we will see, is equivalent to the TreeSwap algorithm for Full Swap Regret minimization (IDDFG24, PR24]; Algorithm 2), where the loss functions are given by appropriate Bregman divergences determined by

---

Lemma 2.2. Moreover, TreeCal is effectively the same as the main algorithm of [Pen25]. However, the perspective that TreeCal can viewed particular instance of TreeSwap (Lemma 3.2) is novel to this work, and it enables us to tackle a much more general set of calibration problems (Theorem 3.1). We first describe the TreeCal and TreeSwap algorithms, then state Theorem 3.1 which establishes our main upper bound for TreeCal, and finally discuss the proof of Theorem 3.1, which uses the TreeSwap algorithm as a tool the analysis.
3.1 Algorithm description
Given some number of rounds T N, TreeCal and TreeSwap sequentially produce distributions X Xy E (P). TreeCal receives from the adversary an outcome sequence y1, "* :rr E P R.
whereas TreeSwap receives loss functions (,, frr
To describe how the algorithms use the adversary's s actions to produce the distributions x,, we need
some additional ntation. The algorithms take input parameters H, L E N satisfying H > 2 and 11-1 < T S H4, We index time steps 1 E [T] via base- H L-tuples: in particular, for E [T], we let lett,...,445 E [0: H 1] be the base H representation of 1; will write
(t1t2 .t).
For all ~ / _ L, for all & E [0 - 1]". let (0( C [T'] represent the interval of times with prefix
k. That is, f E (2) iff k for all i E [1 2]- These intervals may be arranged to form H-ary depth-L tree, where the children of (!()) are r((+1) : ((++1)
((++1
k.H-1'
Both TreeCal and TreeSwap operate by assigning an action ( to each node r()) of the tree, except the root. At time t, both algorithms return the uniform distribution over the actions on the root-to-leaf-t path, namely X2 Unif ((P()) Piita -Pitta }) (see Figure 1). The algorithms
(1)
differ in how the actions Pk are chosen:
(1)
Po
P
(2)
(2)
(2)
(2)
(2)
Poo
Pui
Poz
P10
Pin
(3)
(3)
0000
100
030
01
020
023
200
100
1
Figure 1: Visualization of the state TreeCal/TreeSiáp at time step t (about wal through the algorithm),
For = 3, we depict the intervals I' of the first three non-root levels of the tree (1 = 1, 3). Each rectangular node represents an interval, with sibling nodes separated by red lines. We represent the specific time step via the vertical dashed green line. The yellow intervals it intersects each level correspond to the nodes the moo-to-lcaf-f path. Accordingly, x, will be the uniform distrihution We see that the algorithm has committed to labels of all intervals that started at or before time t, has yet to label the future intervals.
the labels p of these yellow intervals.
* TreeCal (Algorithm 1) assigns actions to nodes as follows. For all 1 < S T,, k E [0:
(8) - 111 h E [0: - 1), at the start of (!l) TreeCal sets Pkk to the average over all y/ that have been observed thus far in the parent interval r (!--1) That is,
Pkh.
Σ
(4)
1E
The more general TreeSwap algorithm (Algorithm also takes a parameter external mngret-minimiiing algorithm Alg, which operates with horizon of length H: we denote the resulting algorithm by TreeSwap.Alg TreeSwap.ALe associates each internal node of the
tree, r(t (((-1) (with < < L), with an instance Alg, denoted Alg ((-1) The subroutine
(1-1) responsible for choosing the actions Pko ... PP{H-1I- does so by
(1) (1)
(1)
Alge
responding to the average losses over each of its child intervals. In particular: the end of
We ignore the truncated branches that exist if < 44
7

---

each child interval r(l) we pass Algg
(l-1) the average loss over that interval. Algg (1-1) then
(1) outputs the action P Pk(b-1) assigned to the next child interval.
3.2 Main result
Theorem 3.1 upper bounds the calibration error of TreeCal with respect to the squared norm 11-11?.
Theorem 3.1 (Main theorem). Let P C Bdd be bounded convex set and ||-]l be an arbitrary norm. Then, TreeCal (Algorithm 1) guarantees that for an arbitrary sequence of oulcomes y1,.... vr the I1-11 calibration error of its predictions X1, ,,,..., XT E (PP) bounded as follows:
P,
Cally (XL:T, V1rT) S cT for T (diam(P)/ve) ((Rate(P (RR (R.-I(()))))))//)
is straightforward derive from Theorem 3.1 via an application of Jensen's inequality an upper bound on the calibration error of TreeCal with respect to the (non-squared) norm |I-| as stated in Theorem 1.1; see Corollary C.5. Appendix E, we additionally consider a variant of TreeCal which plays pure actions in P (i.e., not distributions) by sampling from the distributions for each t [T]. We show that the pure calibration error of this variant can be bounded by a similar quantity to that in Theorem 3.1.
3.3 Outline of the proof of Theorem 3.1
Step 1: Reduction from calibration error swap regret. Let us choose convex function
R P + R given P, II-I] as described in Section 2.4. The first step in the proof of Theorem 3.1 to reduce the problem of minimizing (squared-norm) calibration error to that of minimizing full swap regret for appropriate sequence of loss functions. In particular, for any sequence X1,...,, XT E A(P) and "I,...,UT E S, we have
1-11" (XIT, S CaIP"(XIT, Bir) FullSwapRee (xI.. LIT)) Cal
(5)
where 4, P - IR is the loss function given by (p( == Da(velp): the inequality uses strong convexity of R, and the subsequent equality uses Lemma 2.2.
Step 2: Equivalence with TreeSwap. Thus, it suffices to find an algorithm which minimizies the full swap regret quantity on the right-hand side of (5). Fortunately, the TreeSwap algorithm is known to do exactly this! (See Theorem C.I. from [DDFG24], for a formal statement for the swap regret bound of TreeSwap.) In order to apply the swap regret bound of Theorem C.I, we need to ensure that the TreeCal algorithm is an instantiation of TreeSwap. Alg for an appropriate choice of (a) the loss functions fed as input to TreeSwap and (b) the Alg subroutine. The loss functions have already been defined: given sequence ,),..., lT,, recall that we chose (p) DR(ve (p). Moreover, we let the Alg subroutine be given by Follow-the-Leate
(FTL), which simply chooses an action at each step minimizing the sum of losses up to the previous time step. The following lemma shows that TreeSwap with the losses E, and the FTL subroutine produces the same action distributions as TreeCal:
Lemma 3.2. Let C. IRd be a bounded convex set and let R P - TR. be convex convex function. For a sequence of loss functions f,,-... .HH P + R, define FTL, (fI:H) = arg minpEp Σ (p(). For all sequences of outcomes V1.r E PT,, the action distributions x, produced by TreeCal on yıer equal those produced by TreeSwap.Fr on loss functions (p) = ( for all
The proof of Lemma 3.2 (given in full in the appendix) is straightforward consequence of the fact that the Bregman divergence is a proper scoring rule: the action p E P minimizing an average of Bregman divergences Dn(vlp) is simply the average of the constituent points y (Lemma 2.1).
Step Applying the swap regret bound of TreeSwap to BTL. Finally, we want to apply the main result of [DDFG24] (restated as Theorem C.1) to bound the full swap regret for the iterates x1-7 produced by TreeSwap.Ale Alg, for an appropriate choice of Alg. The most natural way to do so would be to try to directly apply this result in the case when Alg FTL (which corresponds to how we actually implement TreeSwap). However, applying this theorem requires an external regret bound on FTL for an arbitrary sequence of losses. While FTL is known to possess strong external regret
8

---

bounds in some situations (e.g,, when all the loss functions are strongly convex), the loss functions p - Dn(vlp) are not necessarily even convex in p and so it is not priori clear how to establish such bounds.
Instead, the main idea is to consider the FTL but where actions are shifted ahead in time by time step: in particular, the action chosen by BTL at time step h given a sequence ε,, ..,, CH + R is BTLA (41.H) = FTLA+1 (f1:t) argmin Σ E, (p). BTL is not implementable since its action at time step h depends on the (unobserved) loss la at that time step. However, since its regret is always non non-positive (i... ExtReg (BTL) Σ for any H), if we apply Theorem C.I to the algorithm TreeSwap.Bre we get that FullSwapRegr (TreeSwap.BTL) S c as long as T 2 H for any choice of H (the arity (
algorithm BTL, which is the same as
parameter H used in TreeSwap). Using (5), this implies that the calibration error of the iterates produced by TreeSwap. BTL can also be bounded above by e T.
Of course, this result on its own is uninteresting (since BTL is unimplementable, mentioned above). However, the key insight that we can show that the actions chosen by TreeSwap.Br BTL are close to (as measured by the norm []-]]) those chosen by TreeSwap.FF which in turn is equivalent to TreeCal (Lemma 3.2). This closeness is an immediate consequence of the fact that the actions chosen by FTL for our loss functions DR (31 I I-), (2(22))),...... all actions V1, 1/2, E P of the adversary up to the previous time step." In turn, we can use this closeness to show that the calibration error of TreeSwap.FTT FTL is close that of TreeSwap. BTL. This latter part of the argument becomes slightly tricky due to the possibility that different nodes of the tree might output the same action p P; accordingly. we need to work with labeled variant of the action set and bound the swap regret over this labeled variant; see Appendix C for further details.
are simply the empirical average of
4 Lower bound
To prove our calibration lower bound, we make use of the following swap regret lower bound.
Theorem 4.1 (Theorem 4.1 of (DFG+24] 24)). There is sufficiently small constant C1.1 0 that the following holds. Fix any > O. For any E N, there a subset X C [-1, so that the following holds for any T S exp (ca.1 min(d//14 , -1/6)). There is an oblivious adversary producing a sequence u1....,T VT with [|uzl/ S 1 and ||02 S (max(d-13/)) 13/63 for all I, which satisfies the following property. For linear loss functions E(x,v)= (u,x) for vectors u E IRd and x E R.d, any
learning algorithm producing X1...., XT E A()).
T
FullSwapReg, E(2, (1r))
= sup N. +X PEX
Σ Σ (p) ((v1,)) ((,))(p))) 2 e T.
We leverage the classic reduction from swap-regret minimization to calibration [FV98]: by producing calibrated predictions of the upcoming loss and best-responding to it, we can effectively minimize swap regret. This is formalized in the following lemma, proved in Appendix D.
Lemma 4.2. Fix set P C CR,, a norm ||. |]. and write D(p. p²) = ||p -ppppll p'll- Suppose that, for some 0,T N, there is an algorithm which chooses X1,..., Xx A(P)) and which ensures that for every oblivious adversary choosing y1.....yT E P, we have Cal (X1:T, y1:T) S e T. Then for every set 'p' C CRd, there is an algorithum which chooses x1,...,x6, .xy for every oblivious adversary choosing VI...., E P, we have
E A(P') and which ensures that
FullSwapReg, l(, y)rr) S 6 T diam -11 (P').
Combining these two ideas, we demonstrate that algorithm e-calibrated predictions of outcomes on the simplex in < exp(poly(1/e) rounds could be used in Lemma 4.2 to achieve a swap regret algorithm contradicting Theorem 4.1. This gives the following (proved in Appendix D).
An observant reader might note that this same argument also lets provide bounds on the regret of FTL for these losses. One subtlety the analysis is that we obtain better calibration bounds by bounding the distance between the predictions of FTL and BTL in the I|-Il norm rather than in the losses DR (yal I-), and so it is important that we directly analyze TreeSwap. .TL instead of TreeSwap. FTL (the latter causes us to pick up an extra factor related to the smoothness of R).

---

Theorem 4.3. There is a sufficiently small constant > 0 so that the following holds. Write ((p.p') - -lp--l'''' and fix any > 0, d E N. Then for any T S. exple-min minemmnnnnne""" there an oblivious adversary producing a sequence y1..... : Vr E A so that for any learning algorithm
producing XT E A(A4), Call (XLTT VL.) 2 T.
In Theorem D.2 (see Appendix D.2), we show similar lower bound for &g calibration over the unit & ball.
References
[ACRS25] Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, and Mirah Shi. An clementary predictor obtaining distance to calibration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1366-1370. SIAM, 2025.
[AMII]
Jacob Abernethy and Shie Mannor. Does an efficient calibrated forecasting strategy exist? In Proceedings of the 24th Annual Conference Learning Theory, pages 809-812. JMLR Workshop and Conference Proceedings, 2011.
[BGHN23]
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1727-1740, 2023.
[BM07]
Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
[Daw82]
A Philip Dawid. The well-calibrated bayesian. Journal of the American statistical Association, 77(379):605 610, 1982.
[DDF+24] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, and Princewill Okoroafor Breaking the f2/3 barrier for sequential calibration. arXiv preprint arXivv2406. 13668, 2024.
[DDFG24]
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An reficientreduccioonn reduction for large action spaces, In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1216-1222, 2024.
[DFG*24] Constantinos Daskalakis, Gabricle Farina, Noah Golowich, Tuomas Sandholm, and Brian Hu Zhang. A lower bound swap regret in extensive-form games, arXiv preprint arXiv:2406. 1 13116, 2024.
[FH18] Dean Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271-293, 2018.
[FKO+25] Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng. Full swap regret and discretized calibration. arXiv preprint arXiv:2502.09332. 2025.
[FL99]
Drew Fudenberg and David K Levine. An easier way to calibrate. Games and economic behavior, 29 29(1-2):131-137, 1999.
[Fos99]
Dean P Foster. A proof of calibration via blackwell's approachability theorem. Games and Economic Behavior, 29(1 (9)27))73378 1999.
[FV97]
Dean Foster and Rakesh V Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40-55 1997.
[FV98]
Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, 85(2):379-390 1998.
[GJRR24]
Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM- SIAM Symposium on Discrete Algorithmss (SODA), pages 2725-2792 SIAM, 2024.
[GPSW17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1321-1330. PMLR, 06-11 11 Aug 2017.
10

---

[GSJ24]
Khashayar Gatmiry, Jon Schneider, and Stefanie Jegelka. Computing optimal regulariz- ers for online linear optimization. arXiv preprint arXiv:2410.17336, 2024.
[H + 16]
Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-333 2016.
[Har22]
Sergiu Hart. Calibrated forecasts: The minimax proof. arXiv preprinl arXiv:2209.05500 2022.
[HJKRR18)
Ürsula Héhert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Mul- ticalibration: Calibration for the (Comppaationaly-idenffffa
masses. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1939-1948. PMLR, 10-15 Jul 2018.
[HK12]
Elad Hazan and Sham M Kakade. (weak) calibration is computationally hard. In Con- ference on Learning Theory, pages 3-1. JMLR Workshop and Conference Proceedings, 2012.
[HW24]
Lunjia Hu and Yifan Wu. Predict to minimize swap regret for all payoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 244-263. IEEE, 2024.
[KF08]
Sham M Kakade and Dean P Foster. Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences, 74(1):115-13) 1300 2008.
[KLST23]
Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference Learning Theory, pages 5143-5145. PMLR, 2023.
[LSS24]
Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Optimal multiclass u-calibration error and beyond. arXiv preprint arXiv:2405. 193744 2024.
[LSS25]
Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Simultaneous swap regret mini- mization via kl-calibration. arXiv preprint arXiv:2502. /6387, 2025.
[MS10]
Shie Mannor and Gilles Stoltz. geometric proof of calibration. Mathematics of Operations Research, 35(4):721-72) 2010.
[MSA07]
Shie Mannor, Jeff S Shamma, and Gürdal Arslan. Online calibrated forecasts: Memory efficiency versus universality for learning games. Machine Learning, 67:77-115. 2007.
[NRRX23] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xic. High-dimensional prediction for sequential decision making. arXiv preprint arXiv:2310.176. 2023.
[Pen25]
Binghui Peng. High dimensional online calibration in polynomial time. arXiv preprint arXiv:2504.09000 2025.
[PR24]
Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1223-1234, 2024.
[QV21]
Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1556-66677 2021.
[QZ24]
Mingda Qiao and Letian Zheng. On the distance from calibration in sequential predic- tion. In The Thirty Seventh Annual Conference on Learning Theory, pages 4307-4357, PMLR, 2024.
[RS24]
Aaron Roth and Mirah Shi. Forecasting for swap regret for all downstream agents. In Proceedings of the 25th ACM Conference Economics and Computation, pages 466-488, 2024.
[RSTI5] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1-2):111-55) 2015.
[SS11]
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 201

---

[SSTI1]
Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent. Advances neural information processing systems, 24, 2011.
[ZME20] Shengjia Zhao, Tengyu Ma, and Stefano Ermon. Individual calibration with randomized forecasting. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings Machine Learning Research, pages 1 1138--11977. PMLR, 13-18 Jul 2020.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We prove all stated claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
We prove all theorems and lemmas.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
wwwssssssiiiiioooooooi for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //iips.co.. wttpccccppcccccceoccccccccccccct cuubbic/guides /Coeeeummmm ssisnn seiionooiccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tt:://nnuu./eeeeeeee d line??
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : http://een...//eeeeeeeeee /ttpe/rip..c//ooofeeeeeeeeeeeeee / for what should or should be described.
19

---

A Additional Related Work
There is large range of other existing work on online (sequential) calibration [Daw82, FV97, FV98, QV21, DDF+24, Har22, Fos99, FL99, KF08, MSA07, MS10, AMII, HK12, FHI8, LSS24, NRRX23, KLST23, GJRR24, QZ24, ACRS25]. We briefly survey some of these areas below.
Binary outcomes. For binary outcomes (i.e., one-dimensional calibration), classical results of [FV97, Fos99, BM07, AMII] demonstrate that it is possible efficiently guarantee O(T2/3) 41- calibration. The optimal possible rates for f1-calibration remain a major unsolved problem in online learning. Recently [QV21] improved over the naive lower bound of ( (T) by demonstrating a lower bound of Q(T this was further improved (2(70.543) by [DDF't 24]. who also improved on the upper bound, demonstrating the existence of an algorithm with (TT/33-5) calibration for some constant e 0.
Calibration and swap regret. The connection between calibration and swap regret has been acknowledged since the earliest works on swap regret. For example, the earliest algorithms for minimizing swap regret worked by best responding online calibrated predictions [FV97] (later algorithms for swap regret minimization, such as [BM07] and [DDF+ 24] obtain better swap regret bounds by side-stepping the need to generate calibrated predictions). In the other direction, several works minimize calibration via relating it to swap regret that can then be minimized 25, LSS25, AM11, Fos99].
Other forms of calibration. Due to the difficulty of minimizing (high-ding (ighndimmessonna) calibration, there has been a line of work on designing forecasting algorithms that minimize weaker forms of calibration that recover some of the important guarantees of calibration (e.g.. trustworthy-ness by a decision-maker).. These include distance from calibration [BGHN23, QZ24, ACRS25), omni- prediction error / UU-alibrationn [KLST23, LSS24, GJRR24), calibration conditioned on downstream outcomes [NRRX23], and prediction for downstream swap regrel [RS24, HW24]. Other work focuses on minimizing notions of calibration designed to lead to specific classes of equilibria, e.g. weak calibration [HK12], deterministic calibration [KFO8], and smooth calibration [FH18].
B Proofs of preliminary results
(p, R(p))
(u. R(v))
DR(vl p)
(v. (VR(p). p) + R(p))
Figure Geometric depiction of the Bregman divergence from p to y.
Proof of Lemma 2.
= Eyyn (R(y) - R(p) - (VR(p). pil
-R(y) - R(p) (VR(p), -p) p)
DR((Ul)) R(y) R(g)
See Figure 3 for a visual proof.
20

---

(12, N(ya))
(g. R(v)
R(y)
R(y)
(u1, H(y)))))
(v. R(y)
(p. R(p))
Da(ūl p)
(g. (VR(p).g-- (-pp).pp)) H(p))
Figure 3: [Proof of Lemma 2.1] the average Bregman divergence (orange + purple) decomposes into the Jensen error (orange) and the Bregman divergence the mean (purple). For example, when R(p) || DR(vlp) |yy pll and we recover the bias-variance decomposition.
Proof of Lemma 2.2. Fix any E P, and consider the quantity EP
EP E, (Dr(vll)
D DR(uelp") )). By considering the distribution y that has weight (p)/ Σ, (z()) on yts Lemma 2.1 implies that this quantity is maximized when p" = Up (E, X (p) [2, (p))). At this optimal value of p", this quantity can be rewritten as:
Σ (D()((D((ll))) - Dn(vilup))
((())) R(p) (VR(p). Dr -p)) (R(()) R(vp) (VR(vp), Dt -v,)))
Σ [x(())((((p))) - R(p) (VR(p), p)) ((V(m))) VR(p), up)1
Σ Ix(D)D((ypp))) + (R(Ug) VR(() Ex(r)) - -m)
Σ
(x(P)))((Vppp))
(Here the last term vanishes since Exx((p)r)). We therefore have that:
21

---

(ullSwapRgg((io:.4.r)
sup T:P PP
(t( (4(()) ((((())))
pEP
T
E max
xx(p) (Cr(p) (((''))
PEp P
E max pEp EP
xx(p) (Dn(vil) - Dz(yelu)))
1=1
ΣΣ xc(p)D((vslp)) PEP
Calp DR (x (x
Proof of Lemma 2.4. Note that if we define L = (y Rd |llll S 1] to be the unit dual norm ball for some norm ||-I|, then by duality the norm ||-Il corresponding to L is simply the original norm ||-]l- It therefore suffices to show that given 1-strongly convex function R with bounded range it is possible to construct a 1-strongly convex function R' with bounded Bregman divergence (p) (and vice versa).
Assume R(p) 1-strongly convex and satisfies maxpep R(p) - minpep R(p) = p. Define R'(p) 4R (?) (since centrally symmetric, p/2 guaranteed belong to P). then R(p/2) is 1/4-strongly convex, and R' R'(p) is also 1-strongly convex. We claim the maximum Bregman divergence of R' is at most (p). To show this, we first argue that for any 21, E P, (VR( 2 ), 22) I 2p. To see this, note that since R(p) is convex and has range bounded by p. we have that 2 R(p) R(2) 2 (VR(
1-strongly convex,
& ) 2) If we set 2tt22 it then follows that
(VR(2), 22) I 2p. Now, note that
max (u(P) V.PEP
R'(y)) Rp( - (V) p)
R R 2 2
R P2)
VR
p
.9 -P) P)
2
S 9 R ()
VR
P
1 - -P
2 3p.
Conversely, if R(p) is 1-strongly convex and satisfies maXy,peP Du(vlp) p. define R'(p) R(p) - (VR(O), p) R((0) (i.e., subtracting a linear function to make zero a minimizer of R' (p)).. Since R and Rt differ by linear function, R' is also 1-strongly convex. But also, that DR(v10) = R(y)- - R(0) - (VR(0), = R' R'(y); since DR is bounded in range by p. it follows that so is R'.
C Proof of Theorem 3.1
In this section, prove Theorem 3.1. First, in Appendix C.1, introduce slightly stronger notion of calibration error and swap regret to deal with technicality in the proof. We then give the proof of Theorem 3.1.
C.1 Labeled calibration and swap regret
Intuition. Recall that the TreeCal algorithm labels each interval r( of the with some action, Pk E P. At each time step t, the algorithm outputs the uniform distribution over all (1)
22

---

Algorithm 1 (rreCCa((P:)) (H,,H
Require: Action set p C Rd, time horizon T, parameters H, L with T S H
1: for 1.S S T do
2: Write the base- H representation of L 1 as L= = (h1 ... ht), for hy,... hr E (0: H - 1].
3: for S 1 _ L do
4:
Write k = (h1 ... 14-1) 00 11"-11
5:
if h1+1 = = Jy = or then
6:
If hy > O, define "R H²
Ever kih
y/-
7:
(1) Define Pk.h:
(1) hi -i= k, 14 otherwise choose arbitrary Pk,h, E P.
1
(1)
8:
end if
9:
end for
Output the uniform mixture x; == Unif(1ph) ....,
p Phi }), and observe yr-
11: end for
" are all distinct, for 1 E [L].k E [0 H - 1 (as we discuss below, this case is some sense the "worst case"). In this event, each action ph is compared the average outcome over the interval r(). Uk Eier Vt- Formally, this would give
with r()) When evaluating the calibration error, suppose that the actions
k
Cal (XL2, V1r1)
Σ KE(H
D
Uk
(6)
as each level action is selected with 1 mass for HL- rounds.
If it happened that two distinct intervals p(l)) (12)
bzz were assigned the same action p Pk: Pk.
(1) (4)
then the calibration error would be at most the quantity on the right-hand side of (6) (by Jensen's inequality). In particular, rather than having compare p to two potentially distinct quantities D( p), D(7( (12) .)), the mass placed on p would be categorized under the same forecast and we
average of Ok. (1z) and Vizz (12)
would only compare p to an appropriately-weiee
For technical reasons, it will turn out to be necessary to upper bound the "worst case quantity" on the right-hand side of (6) (and analogous version for swap regret), even in the that the actions (1)
Pk are not all distinct. To streamline our notation, we introduce generalization these quantities which apply for arbitrary algorithms, which call labeled calibration error and labeled swap regret.
Formal definitions. Given a convex set C Rd, we define its labeled extension be P P x {0, 1 i.e., elements of P are tuples (p, d), where E {0, 13 is string that is said to label For loss function P + R, we extend its domain to P. the natural way, i.e., (((p, = f(p) for (p, o) E P. Given sequence of distributions over the labeled extension, XI,..., XT E (PP). and loss functions ,,,..., er P IR, we define
FullSwapReg (x.T, L.TT := sup J:
xx(p) (c((p) (c(T()))).
1=1 PEP
In words, the full swap regret of X1.T with respect to LTTT is defined identically in (2) except that the swap function æ can now depend on the label a. In particular, the labeled extension allows us to consider more refined notion of swap regret where identical actions played in different rounds can be swapped (via T)) to different alternatives as long as they have different labels.
In a similar manner we define the calibration error for a sequence of labeled distributions: given Xi...., XT E A(P) and y1, ........1 VT P. we define
T
P(p.o) = Σt= xx((p,
Cal = Σ
Σ 1=1
((..)))
D D(v(no):))
Σne xi((p. ())
(P.O)E
23

---

The main result of [DDFG24] shows that the swap regret of TreeSwap is bounded, even when one labels the action produced at each node of the tree by the node of the tree. This labeled variant of TreeSwap is given in Algorithm 2. It functions exactly as discussed in Section 3.1, except that the distribution x₃ output time step is in A (P) instead of A(P). In particular, each Pk support of x is labeled by the tuple & E H 1]".
(0) P in the
Theorem C.1 (TreeSwap; Theorem 3.1 of [DDFG24D. Suppose that H. L. E M satisfy H 2 and -4-1 < T I H For bounded convex action set E and loss function set C C {E + [0, bj} let Algh - + +pi be any algorithm. Then, the labeled TreeSwap algorithm (Algorithm 2) parametrized by T, H,,, L, Algh oulputs labeled distributions x1..... XT E (PP) satisfying the following: for any sequence f1...., E E,,
[ExtReg (Algh) +
3b
FullSwapReg, (X l1T) ST.
H
L
Algorithm TreeSvap.Alg(P,...7, L), labeled variant (see Appendix C.1)
Require:
Action set P C Rdd convex loss class C (P - RR, no-external regret algorithm Alg, time horizon 7, parameters H, L. with T < 14.
1: For each sequence h1 1--1 U 0 H 1][-1, initialize instance of Alg with time horizon H, denoted Alg --
2: for <L77 T do
3: Write the base- H representation of 1- 1 = (h1 hr), for hi, hr 3 H 17-11
4: for < 1 < L do
5:
Write == (h1 .. .....--41 E 00 H 111--1
6:
if h1+11
= hy = Oo = then
7:
If hy O, define [!1)
khh1-1 मレ E Ever(h
l, E
king
(1) Define PE = Alg ( E P. b The hith action of Algg given the loss
8:
sequence (!)
9: end -,1:h,11'
10: end for
Output the uniform mixture x, == Unif(f(Ph)) (1) .l),..., (L) ( bm.L)t E A(P). and
11:
observe l.-
Each action Pk:
(!) is labeled by the sequence k (see Appendix C.I).
12: end for
C.2 Proof of the main theorem
First, we recall some definitions from Section 3. For all E [0: L), for all k E [H]', let r represent
the interval times with prefix k. That is, t E (()) iff t, = ky for all [1 [.. These intervals
form H-ary depth-L. tree, where the children of r(() are ((+1) - ([+1)
r (1+1)
R(H-1)- In the
(
calibration setting where the learner receives outcomes /1.7, let 1/k r E Ys (as defined
on Line 6 of Algorithm 1). In the swap regret setting where the learner receives loss functions l1.r. Energo & (as defined in Line of Algorithm 2).
let (1)
Finally, recall that for an online learning algorithm Alg with time horizon H, we define its action time step h [H] given losses (,,..., LH P R by Alg (fi,..., (.)). If Alg, only depends on the first g losses, then we will write Al A1g, (f1 (f....., (,....,.g) .g). In the proof of Theorem 3.1 we will consider two algorithms in particular: the first, Follow-The- The-Lederr- (FTL) is defined as follows: for
TTTechiiaalyy, the analysis of [DDFG24) does not analyse the labeled version, but the proof goes through as the only step where labeling changes any of the reasoning in the argument is in Eq. (8) of [DDFG24), where the upper bound written in that equation holds even for the labeled version.

---

l fn..., + R, we have
FTLA (61, (n-1) argmin
(p()
pEP
The second algorithm we consider the Be-The-Leader algorithm (BTL), which defined as follows: for .,...., .,.,. ln + R, we have
BTL (e1, (eI........ (n)
argmin
Σ ((p).
pEP
Note that since BTL, (f):)) depends on the unobserved loss l, at time step h, it is unimplementable. Nevertheless, it will be useful in our analysis.
Next we prove Lemma 3.2, establishing the equivalence of TreeCal and TreeSwap.FIL In fact, we establish the stronger claim, which immediately implies Lemma 3.2.
Lemma C.2. Fix distributions Qo ................................ 9h E (PP), and define (p) Eyrgg [DR(VD))] Then for = k Di Eg-os [v]
each h > 0,
Proof.
The lemma an immediate consequence of Lemma 2.1, noting that
h-1 Ey-a [w]-
(.., ln-1) = argmin (x)
argmin Bo-/0:h-11/0g [D((vip)]]
Σ
pEP 1=0
PEP
1=0
(7)
Proof of Lemma 3.2. At time t, both TreeCal (Line 10 of Algorithm 1) and TreeSvap.FTL (Line 11
of Algorithm 2) select x, = Unif { Phi PPitz: ... tt })). remains to demonstrate that
(1) (2) (L)
both algorithms assign actions pk intervals r( identically. Fixing a choice of I E [4] and
1 E [0: : H - 1 this is an immediate consequence of Lemma C.2 with db. Unif({u: t k,h and the fact that:
(1)
In TreeCal, (1) A EiD KR
!
with u E Uu [uol:
Whereas TreeSwap.FTL, Pk. FTL (E()
k.0 ( with e
E U.uuii(( [Dn(vil)]] (Du(mt
We are now ready to prove Theorem 3.1.
Proof of Theorem 3.1. Fix any convex set P and norm |1-1|, and let R P R be chosen to be 1-strongly convex which has range p > 0. Lemma 3.2 gives that the actions X1...., XyT E A(P) identical to the actions played by TreeSwap. FTL with losses (x(p) Dr p) (Algorithm 2; we are ignoring the labels here). Thus, from here on, it suffices to bound the calibration error of the corresponding distributions ,,. Xy of TreeSwap.FII The actions Pk, (for [4], E [0
H - -1]1 he
:0: -1 H 1)) of TreeSwap.FT satisfy Pk. FTL K.0...... k.h-1)-
(
(1)
( Next, let Pk.h denote the corresponding actions played by TreeSwap.BTL, i.e., Pk, BTL4+1(01)
.............. (c......., 2.) We let x, A(P) denote the (labeled) distribution chosen by
TreeSwap, FTL (Line 11 of Algorithm 2). and let &; A(P) denote the corresponding distribution for TreeSwap.BTT BTLL To be concrete, if t = (.. ... hr),, .r.)). then
x; = Uni (1) hr)...., (plii h1.L))),
x Unif([(P ( h1.)))). (8)
25

---

We state the below claim, whose proof is deferred to the end of the section. (We remark that the primary purpose of introducing labeling is so that it possible to establish Claim C.3.)
Claim C.3. It holds that
2 diimmp) T.
Cal,"" (x1,, KITT,Br) 2Call;"" (RIT, Mir))
(9)
H
The fact that BTL enjoys non-positive external regret (e.g.. ISSII, Lemma 2.1] gives that for an arbitrary sequence of loss functions & P + R, the external regret of BTLH satisfies ExtReg (BTLH) S O. Thus, by Theorem C.I, the swap regret of (the labeled version of) TreeSwapr applied with Algn = BTLy may be bounded as follows: for any sequence of losses fi.....4 tu pl.
(x. (1T) ST. 3p
L
Using Lemma 2 and (9), we get that for an arbitrary sequence y1...., E P,
2 dP)
Cail!"" (x1.r, Vrr)) $2 Call/ Sxrr,urrr +
T
H²
2. dP)
<2 Cal (R1r vir))
T
H²
FullSwapRegr (1.T DR(vIT))) dP)m
T
H²
6p 2 diam .
L +
112
Given any desired accuracy >> choosing 12p/e and /| diam gives that we can guarantee Call!: (X1r) (1:r)) c T as long T H (diam(P)/v()11a)))
Proof of Claim C.3. For each & [T]. write t - 1 = h1h2 ... hy with by E 00: H for all i [L]. and X & are as given in (8). Let us write, for (p, E P.
ΣT X ((D, ((),))) St P(p.o)
((poo) = ΣT (e((p, Vt
(10)
Ex=xx xc((p,
(( (pp, o)) Et,x(((p
Va ΣpEP Et X (e σ)) 3/t
Epep Σt ((((
( Since each Phi...h and each Ph is labeled by h1a in x, and x,, respectively, holds that for each of the form = hy ... by (for some I E [L],, there are unique p. P.p E P so that Vy Mpp.o) = V(g.))
(0)
Technically, need a labeled version of Lemma 2.2, where the distribution are over the labeled set APP): it is immediate to that the proof of Lemma 2.2 extends to the labeled case.
26

---

in particular, we have - (1)
Ph....b. Ph
(0)
We can therefore bound
Ca (XI:T,
2Call 1P (X1:)-91:))
T
Σ
xc((ph hy ... -ii)) 1ph
Phi--.s 11?
(1)
(II)
Σ X (. h1 (....-))))
he))
11 - p(0
Phi--hell
Σ
HL-1
(1 Phy
(1)
12)
Pho
Pho
L
<2
Σ
H1-1
Pha
Phu ||
L
2
Σ
diam(P)2 HL-1
L
1=1 A 1(0.H
2
diam (P)3 HL-1 -L-1
L
(P)
H
where the second-to-last inequality uses that -1
(
|2 S diam(P)2 for all
Phi
Phimn
choices of h ...hi-1 (a consequence of Lemma C.4 and Lemma C.2).
Lemma C.4. Fix any convex set P C Rdd and a convex function P R. Fix sequence
V1. E P, and set
h-1
Ph
Σ t (HI,
Pr
h 1=1
Σ
vh E [M],
as well as Pı E P arbitrarily. Then
Σ 1l 2 < 2 (P)².
Proof. Note that
1
Pr.
Ph
Vi.
h
h(h 1)
i=1
which implies that I| - Phll 11 < x²
dP) 2d)am(P)2.
Applying Cauchy-Schwarz we get the following corollary.
Corollary C.5. Let P C Rd be bounded convex set and ||:I1 be an arbitrury norm. Then, TreeCal
(Algorithm 1) guarantees that for arbitrary sequence of outcomes yı...., ... P. the ||:|| calibration error of its predictions X1,..., XT A(P) is bounded Call. (XLT, (1T) S eT for
T > (diam ((Rate))) ((Rate(P,.llll))))
27

---

Proof.
Using the fact that ΣpEp Ei=1 (p(p) together with Jensen's 's inequality, we have
T
-
(xiT,
Σ pEp
Σ
1115 - pll
T
r=l
1
Σ x((0)
-1lss -1ll-pl1
T
PEP
7 Calll.1 (NrT) S
for T 2 (damm(P)/6)((R()M))))))))) by Theorem 3.1. Thus, Call (xi. vir) S eT for T (iiam(P))e)0((tat)))Mll))) incurring an additional factor of in the exponent constant, as desired.
Finally, for the setting of centrally symmetric P, we can apply Lemma 2.4 to directly relate this regret bound to the optimal possible rate of an online linear optimization problem.
Corollary C.6. Let C Rd be a bounded centrally symmetric convex set and ||-I| be an ar- bitrary norm. Then, TreeCal (Algorithm 1) guarantees that for arbitrary sequence of out- comes yI,...;yT P, the ||-|| calibration error of its predictions X1....,X0 XT A(P) is bounded Call- all- (XI.. S eT for T 2 (P)) (Raaeeoooo
Proof. Follows immediately by applying Lemma 2.4 to Corollary C.5.
D Proofs for Section
In this section, prove lower bounds high-dimensional calibration that tell that in order achieve calibration error at most c T, we need to take 2 exp(poly(1/c) First, in Appendix D.1, we prove lower bound for ê calibration over the d-dimensional simplex, and then, in Appendix D.2, we prove lower bound for & calibration over the unit d-dimensional Euclidean ball.
D.1 Lower bound on L calibration
First, we prove Theorem 4.3 which gives lower bound on é calibration over the simplex P = A
Proof of Lemma 4.2. Fix an algorithm Alg which ensures that Cal P (XI.T W.T) < e in the statement of the lemma. We construct the following algorithm Alg': it simulates Alg, but whenever Alg outputs the distribution x, E A(P), Alg' chooses instead x E APP'), defined by
x((x)== =
Σ PEP:
x1
p' p/=argiin (g.p)
28

---

To simplify notation, we define BR(p) = argmin gepi ().P). It follows that, for any oblivious adversary choosing a (random) sequence yr......7 yr P.
FullSwapRegr ( (.:
sup Σ x:P'-PP
(P') (1ye, p' - x(p')))
P'EP LE|T]
sup Σ x:P' PEp 1E[2]
Σ
(p) (1ye, BR(P) 7 ((B(()))))
sup P:P PEp
Σ x((p)
((pp BR(p) ((BR())))
tE(T]
sup x:P' p
xp(
((2p BR(p) (e00))(((BB(R)))) T(BR(p)) + (p. BR(p) x(BR()))))
PEp
[E(2]
Σ (p) (E(T]
(IL ||BR()) (BR(p))ll-)
x:P' pp
pEP
<diam |-11. (P') (x1:,, y1:r),
where in the final inequality have used the fact that [|BR(p) (BR()))) diam (P').
For p 0, d N, write By = (ir Idd ||>|| S 1} to denote the unit lp norm ball.
To map the lower bound Theorem 4.1 from the |1-II, -norm unit ball By to the simplex and arrive at the desired contradiction using the above lemma, we use the following.
Lemma D.I. Fix d E N, and write D(x,y) y) = ||x yll for x, Rdd Suppose that there is algorithm for calibration over the domain P A 2d4+ which produces X1.7 given the choices of an adversary yır achieving calibration error Cal (XIT, (xI.T,11.)) (i,..)r) S R(T),, for T N. Then there is an algorithm Alg' for calibration over the domain B which produces x given yoo achieving calibration error C (xET:: Vi:T) S R(T)..
Proof of Lemma D.1. We define mapping Φ By + A 1 as follows: for E B C Rd, we define
[1j]]
: :i= 2j - 1, E
((v):
[3:]
:i 2j, j [d]
|
:i 2d +
It is straightforward to see that & has a left inverse v/, defined as follows: for E A 22+11
(=)), = 22:-1 - 225+ i E [d].
so that vi o(y) y for all y E Rd.
We define the algorithm Alg' as follows: given v/ E B C Rd, it defines y, E A 2d+1 by y = ((v)). Alg' then feeds y, into Alg, and if denote the distribution output by Alg at time step by x,, Alg' then plays the push-forward measure x = o X E A(B
Our bound on the calibration enror of Alg gives
Cal (X1:T, V1er)
Σ 1
Ex((p) 1=1
-11 pll R(T),
where 1/p
2x Xx (p)
A2d+1
For p' Bd let denote 1/2
2x x/'1//1 Σls x((x')
Σ (x(p)
NT x((1 (1)
using linearity of vb
Σn x((²')
29

---

We may now bound the calibration error of Alg' by
T
Calp( B1:r) = Σ
Σ
x(609)
111/// p'll2
P'EBY
1=1
Σ Exx(ol)
[[((()))) - +())l
PEA2i+1
(Cal)((x1:T)
Proof of Theorem 4.3. Suppose to the contrary that there was an algorithm Alg which bounded calibration error by eT for T S exp(c- min(d ,c (1))). Then by Lemma D.I, for d' [(d- - 1)/2j there is an algorithm Alg' for calibration on the domain B C IR produces X1. given Vi.r satisfying Cal (x V(r) S c. for any T < exp(c- min min(d'/14 c-1/6)) (116)))))))))))
We now apply Lemma 4.2 for P = B3 C Rdd,, the norm given by the é norm || 1l,, and P = [-1, 1j Note that diam ||11
(P') 1. Then Lemma 4.2 ensures that there is an algorithm Alg" which chooses ..,..., xx E A(P") which ensures that for every oblivious adversary choosing y/...... 3/ B we have FullSwapRegy ((. v(.r) e.
But if S exp(c1.1 min((d)) - (1166)), we have contradiction to Theorem 4.1, thus completing the proof of the theorem.
D.2 Lower bound for &g calibration
Next, we prove a lower bound for & calibration.
Theorem D.2. There sufficiently small constant e > 0 so that the following holds. Write D(p, p²) lpp - p2112 and fix any > 0, d E N. Then any T S explc. exple-min(d>) min(d//is, (1/T)) there is an oblivious adversary producing sequence "1..... .r E B so that for any learning algorithm producing X1. XI. A(B)), (x1.T (1:T) E
Proof. Fix e 0, N. and write ē 8/7, We may assume without loss of generality that d 2-14 so that (in/1 2-1/6] min(d -1/) minnd//u4,_///
d'/14, if this were not the case, we simply use the adversary resulting from 2-14 dimensions and project the forecaster's predictions down into this lower-dimensional subspace, which can only decrease calibration error. Now suppose to the contrary that there was an algorithm Alg which bounded calibration error by e7 for T < exp(c- exp(c-minn( / e -1//3) = exp(c-d!/14). Then by Lemma 4.2 with P = Bd and norm ||-|| = |1-112-
for any subset P' C By we get that there is an algorithm which chooses Xi...., Xyy E A(P') and
which ensures that for every oblivious adversary choosing V1...., Vr E Bd we have
FullSwapRegr (xi.r. (f: B1). ( Br))) T.
(12)
On the other hand, the oblivious adversary of Theorem 4.1 guarantees subset X C. [-1, and an oblivious adversary producing a sequence UI,..., so that
or .r.,.r Rd with |/lll S d 13/14 for all E [T].
(x. (1, UI), ((,))) 2. T.
(13)
as long as T 5 exp(c1.1 - 2/14), We have ||va ll < 11/2-13/14 = 3/7 for all i, and scaling X down by factor of 1/vd (i.e., letting P' = X/vV) and all vectors v; up by factor of G/7 (i.e.. letting of vd vs ensures that any algorithm producing x',...,x? .,-, p' must still have full swap regret
(xllswapReg, ((s of)...., (2,4)))) > E- d 1/14 > 7/6 . =
but now ensures that P' By and that v/g E Bd for all t. By taking C4.1, this contradicts (12).
30

---

E
Pure calibration and pure full swap regret
E.1 Pure calibration
In certain settings of calibration, the learner is required to randomly select pure forecast Pr E P rather than a distribution x; E (P). In these settings, the above definition calibration is instead referred to as "pscudo-calibration" Here, we stick to calling the above calibration, as we believe it to be the more natural definition, and instead refer to this alternative setting as "pure-calibration" The learning task changes follows.
At each time step E [T]:
The learning algorithm chooses distribution x, (PP).
The adversary observes and chooses an outcome l)t E P.
The learner samples Ps
We adjust the definitions of the "pure average outcome" and "pure-calibration acciiirriionaaaccdiingglll accordingly:
ipp = -1=1 [pp pl
y/r
(pir) =
Σ PEP
1 [pr p1 D(ip:)) Σ 1=1
T
Σ 1pp =
Algorithm 3 SampleTreeCallP.I1 L,
Require: Action set P C Rd, time horizon T, repetition parameter S parameters H, L with T/S- $ HL.
1: Instantiate an instance (PeeCal(P,TTS) H,
2: for Si T/SS
3: Let E APP) denote the prediction of TreeCal at step
4: for 1 1 j S do
5: Sample Ps(i-1)+j X,, and observe outcome (s(i-1)+)
6: end for
7: Feed the outcome TJ Σ 1s(1-1)45 to TreeCal.
8:
end for
To obtain a bound on the (expected) pure calibration error, we use slight modification of TreeCal, namely
(Algorithm 3). It functions identically to TreeCal except that for each time step t of TreeCal, it samples S actions from x; each of S contiguous time steps. (Hence, TreeCal is used with time horizon T.).) At a high level, we will use an appropriate concentration inequality to show that the calibration upper bound of Theorem 3.1 implies a pure calibration upper bound for CempleTreeCaa
Theorem E.1 (Pure calibration error). Let P C. cdd be a bounded corvex set and ||:|| be an arbitrary Rd [[fll, 11}. Then, Sample
(Algorithm with an appropriate choice of parameters H, L, S) guarantees that for arbitrary sequence of outcomes n......IT E P, the I|-112 calibration error of its predictions x XT E A(P) is bounded as follows:
norm with unit dual ball :: (f
E [PurrCCll (pir. VIrT s eT, for T2 Rate(C, I1-11.) (diamj (P) (RRtt((I1())))))
Proof. The proof uses Theorem 3.1 together with an appropriate concentration inequality, and closely follows that of [Pen25, Lemma 3.4].
Fix any 1 < S T/S and < I S. and let F 5(1-1)4 denote the o-algebra generated by U1..... -Us(i-1)+HH and Pi,..., PP(i-D-- since TreeCal is deterministic, it follows that X1. XI...., X; E (PP) are F -eaasuurable. For any 1 < & S, we have that, for any p E supp(x;),
E (p US( 1)45) 1[ps(i-1)+) = p
F s(i 1 (p Us((-1)44) x, (p)..
31

---

Fixing any E [T/S], By Lemma E.2 applied to the sequence Ms(i-1)+ 1)4j (p U)((-1)-3)) L 1)+j Pl, for 1 S < S (and the filtration S s((i-1)+)), we see that
S
E
P 1)((-1)-j) ( Σ
= =p]
Σ (p 1)())1)))) x((p) diam (P) 8/8 Rate( I1-11.).
==1
follows by summing over the L values of p E supp(x;) that
E
Vs((-1)45) 1[ps((-1)4) pl
Σ (p us 1)+5) xx(p)
PEP
SL - dddimmijl (P) 8S Rate(C, 11.11.) S Se
(14)
as long as S S.Rate(C.)l I-I diam (P)--1
The guarantee of Corollary C.5 gives that, as long as T/S 2 (diamı)I) (Raee()l)))))))))11)))) then
rys
||l|=-| Call/ (XIIT/S
Σ
Σ
xx)
(p T66
pEP
==1
Tys
8
cT
Σ
xx (p) (p (5((-1)+))
S S
(15)
pEP
J=1
By combining Equations (14) and (15), it follows that for arbitrary adaptive adversary who chooses a sequence y1,-..,9T E P.
E
PureCal|
(pI.T.81.)
=E
M1) 1pp =pl
pEp
T/S
T/S
<E
Σ
95(111)+)) (p)
Σ
((p (5((-1)45)) (1(ps(1-1445 p) xx))))
pEp
<2eT.
The result follows by rescaling and our choice of = ORRate(P,
As example applications of Theorem E.I:
When ||-1| is the & norm and P is the simplex, we have diam (P) = 1, -= {f Rd Il I 1} satisfies Rate( (C, ||+I1_) S (as we can take the function R(x) ||>1)) which
gives that for > (0()/2) we can have E| ||-1| S el'. This result recovers the main upper bound of [Pen25] (Theorem 1.1 therein).
When ||:I| is the Eg norm and P is the unit &2 ball, we have diam (P) = 1, L = {f E Rd llfl S 1) satisfies Rate(C, I1-1.)) < 1 (as can take the function R(z) = || which
gives that for T 2 exp(O(1)e²)). we can have E(PureCat ||.] s eT'
E.2 Sequential law of large numbers
Fix convex P Rdd and norm ||.|| on Rdd. We define
1 Σ p
R, (P, II-II) == sup E,
p
32

---

where the supremum is over all sequences of mappings Pi....: Pn. where p; : (-111)1-1 P. and the expectation is over an i.i.d. sequence of Rademacher random variables Gn).....Gn.
Unif((+1)). The below lemma (essentially contained in [RST15]) establishes martingale law of large numbers for P-valued martingales, in terms of geometrie properties of P and ||-||-
Lemma E.2 (RSST15). Consider a convex set P C. R a norm ||-I| on R2, and let M A denote sequence of random variables adapted to filtration (Fi)ie(n)- Let L {f |l 1) be the unit ball of the dual norm |1-1|. Then
E
Σ
M.
RM | (--1 diam 88 Rate 11-1,)-
Proof. By applying an appropriate translation to P. we can assume that P contains the origin. We apply Theorem 2 of [RST15] with the domain Z equal P and the function class F equal to the class of mappings {= - f) |I]I|, s } indexed by unit-dual norm linear functions on Z. The theorem implies that
Σ EEp(())))))
E
Σ
M₁
E[ 8
22 sup E.
sup [l a
n
-2 R. (1-ID).
Write C ff Rd llf S 1] denote the unit ball for the dual norm II-II.- Proposition 16 of [RST15] gives that, if there is function R L + R which is 1-strongly convex with respect to
||-Il, and which has range P. then R. (P, I1-11) V 2e diam In particular, R., (P, |I-I1) <
diamii-1 (P)
CRate(C.11-1
33


Reviews:
[{"review_id": "AjisHp4Z4s", "reviewer": "Reviewer_Fhoa", "summary": "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.\n\n\nThe main contribution are two folds: \n\n(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.\n\n(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.", "questions": ".", "limitations": ".", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The reduction is very nice and solves long standing open questions. The lower bound is also very nice and smart. I strongly recommend acceptance to NeurIPS.\n\n\nThere are minor suggestions:\n\n(1) It would be good to mention that the approach of (Peng 2025) is also inspired by swap regret minimization.\n\n(2) There is a discussion between distributional calibration and calibration in the appendix, the distinction might seems minor to the authors, but for me (and maybe other readers), then distinction is non-negligible (e.g. in Foster 97, if two forecasters are distributional calibrated, then playing \"best response\" might not lead to correlated equilibrium?). Why not put the discussion earlier. Also, it would be good the mention that the lower bound only holds when the outcome $i_t$ is some distribution but not a single outcome (correct me if I am wrong.)", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and for the helpful suggestions! We will take them into account when preparing the final version of the paper."}, {"review_id": "iEw1kTlUjt", "reviewer": "Reviewer_KJ55", "summary": "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.", "questions": "I am to some degree surprised by the simplicity of the eventual algorithm, and the fact that it is independent of several problem parameters including the Bregman generator and its radius. These are all only required in the analysis. Do the authors understand why it is the case, and would it be plausible that there exists an even simpler direct analysis?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Quality\nI went over the proofs of the main result Section 3, and these are all good.\n\nClarity\nThe paper is written with the reader in mind. At several points does it immediately address questions the reader may have with a remark or footnote, after raising these questions by presenting results. I'm thinking of repeated actions, ranges of Bregman divergences vs their generators, loss vs parameter distance, etc. This makes the paper a pleasant read.\n\nSignificance\nThe improvement in lower and upper bounds for d-dimensional calibration is significant. The method is actually easy to implement, and the contribution of the paper is its design and analysis. \n\nOriginality\nThe originality lies in the analysis. The algorithm itself was already proposed before. The new perspective taken here allows a different bounding technique.", "was_revised": true, "final_justification": "I thank the authors for clarifying that indeed the domain does come into the algorithm, and not just the analysis.", "rebuttal": "Thank you for your positive review. We are not aware of a simpler proof of our main result. Note that while the Bregman regularizer R does not explicitly show up in the final bound, in the definition of Rate the regularizer R is chosen to solve an optimization problem involving the given norm. So the final bound takes the geometry of $\\mathcal{P}$ (as well as the norm) into play."}, {"review_id": "Z9KoeylZ2Q", "reviewer": "Reviewer_EHNL", "summary": "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.\n\nThe main result of is an online algorithm that can guarantee vanishing calibration error relative to an arbitrary norm.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Online high-dimensional calibration is known to be a challenging problem (as the generalization of typical online calibration methods require an exponential number of rounds w.r.t. the dimension). Recently, the work [Pen25] has shown that it is possible to achieve a calibration error rate $\\epsilon T$ in $d^{O(\\ln 1/\\epsilon)}$ rounds when focusing on $\\ell_1$-norm calibration error. This work advances this result with being able to generalize the result for arbitrary $\\|\\cdot\\|$ error. They achieve this with a more simplified and a unified analysis. \n\nI do not have major concern of this work. This work is a theoretical work and I believe that this work would be a good addition to NeurIPS. \n  \nMaybe this question is beyond the scope of this work, but it seems that the exponential  $\\ln(1/\\epsilon)$-dependency in the lower bound not satisfying, would it be possible to break this barrier by considering a smoothed adversary?\n\nMinor points:\n\n1. Line 73, I guess you are referring to Theorem 1.1?\n2. Line 188, where is Figure 3?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. The question regarding a smoothed adversary is a good question for future work. \n\nRegarding line 188: Figure 3 is in the supplemental material (we will correct that point in the final version)."}, {"review_id": "Mzk700Ufvr", "reviewer": "Reviewer_zPv9", "summary": "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.\n\nThe technical approach consists of two main components:\n1. 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.\n2. 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.", "questions": "Please see strengths and weaknesses.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper provides a simplified and unified analysis framework for high-dimensional calibration under arbitrary prediction sets and norms, offering cleaner proofs compared to Peng25. The proposed algorithm achieves calibration without requiring knowledge of the OLO rate or diameter of the prediction set, making it particularly appealing. The new analysis also removes the need to mix the prediction with uniform distribution (as Peng25 did).\n\nWeaknesses:\n\nWhile elegant, the connection between calibration and OLO rates largely combines existing results rather than providing new technical tools: The reduction from calibration (using Bregman divergence) to swap regret builds directly on prior work [LSS25,KFO25], the swap regret part invokes results from [DDFG24], the analysis through BTL and FTL are hinted by [Peng25] (although this paper provides a more general proof that works for any norm and also removes the need of uniform distribution as stablizer), and the connection to OLO rates also directly build on [GSJ24]. That said, the paper brings these separate techniques together into a more unified analysis.", "was_revised": true, "final_justification": "I appreciate the contributions of this paper and am happy to recommend acceptance. The reason for not giving a higher score is that the paper mainly brings together results from different papers rather than introducing new technical tools. That said, I appreciate the simplified and unified analysis it provides, and I believe this paper makes a nice contribution.", "rebuttal": "Thank you for your positive feedback."}, {"review_id": "jlzDmy9ii7", "reviewer": "Reviewer_VeHt", "summary": "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:\n\n(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. \n\n(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.", "questions": "(1) I would appreciate some clarification of the steps spanning lines 993-994 in the appendix. \n\n(2) For this line of work, I find the comparison between the $(\\frac{1}{\\varepsilon}) ^ {\\text{poly}(d)}$ versus $d^{\\text{poly}(\\frac{1}{\\varepsilon}})$ a bit unclear. What is the regime that these bounds are compared against?\n\n(3) As I mentioned in the strengths and weaknesses, the statistical dependence on $\\varepsilon$ as a function of $T$ is rather weak (for swap regret minimization, compare this to the $\\sqrt{T}$ dependence achievable via the BM reduction versus the $\\frac{T}{\\log T}$ achieved by the TreeSwap algorithm) and is inevitable since the current papers results build upon that of Daskalakis et al. I understand that the purpose of this paper and Peng's work was really to resolve the exponential dependence on $d$ for $\\ell_{1}$-Calibration; however, I am curious if the dependence on $T$ can be improved further, i.e., can the $T^{1 - \\frac{1}{d + 1}}$ bound for $\\ell_{1}$-Calibration be improved further? I am also curious if the authors have thought about improved lower/upper bounds for $\\ell_{2}$-Calibration for $d = 2$.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: (1) The perspective that TreeCal is a special case of the TreeSwap algorithm of Daskalakis et al. is novel to this work. In particular, TreeSwap with Follow-the-Leader as the external algorithm yields the TreeCal algorithm. This perspective allows the authors to obtain a set of more general results for an arbitrary $\\mathcal{P}$. \n\n(2) The connection between the achievable bounds on $\\ell_{1}$-calibration and the optimal external regret bound of OLO is particularly interesting. More specifically, the TreeCal algorithm does not utilize any OLO algorithm as a subroutine; however, it still achieves a bound that depends on the optimal regret bound of an OLO instance. \n\n(3) A strength of the paper also lies in its simplicity, e.g., the lower bound for $\\ell_{1}$-calibration follows by existing results and an observation due to Foster and Vohra, however, it is commendable that the authors connect the above results to improve upon Peng's lower bound. The presentation of the algorithm is exceptionally clear, and the paper can be very well understood from the main body.\n\nWeaknesses: The paper is based on observations that were already known and therefore does not offer significant insights from a technical perspective. However, that being said, tying these observations together to derive meaningful results is a major contribution of this work; therefore, I only consider the technical aspect as a minor weakness. Moreover, some of the extensions of the existing results, e.g., the claim that the algorithm of Daskalakis et al. (with the Follow-the-Leader algorithm as a subroutine) achieves the desired bound is not immediately obvious; the analysis argues that the fictitious Be-the-Leader algorithm achieves a particular guarantee and that the predictions made by Follow-the-Leader and Be-the-Leader are close. This introduces other minor technical nuances in the analysis, e.g., working with a labelled tree.\n\nOverall, I find these results quite interesting and recommend acceptance. On the upper bound side, achieving polynomial dependence on $d$ for multidimensional calibration was open for a long till the recent work by Binghui Peng. The current paper improves our understanding of Peng's algorithm by establishing connections with the recent breakthroughs in Swap Regret minimization. The statistical dependence of the error parameter on the number of rounds is weak; however, this is a manifestation of the improvements in swap regret minimization literature. On the lower bound side, the improvement upon Peng's lower bound is quite strong.\n\nBelow is a list of minor typos that I found while reading the main paper and the appendices:\n\n(1) Line 158; the definition of external regret is incorrect.\n\n(2) Line 255; typo in \"notation\".\n\n(3) Line 258; $\\ell$ should range from $1 \\le l \\le L$.\n\n(4) Line 357; \"algorithm $\\epsilon$-calibrated\"; should be \"algorithm producing\" $\\epsilon$-calibrated predictions..\" or something similar;\n\n(5) Line 830; $x - \\frac{z_{1}}{2}$ should be $p - \\frac{z_{1}}{2}$.\n\n(6) In the equations spanning lines 831 and 832: (a) the second equality should have $-\\frac{1}{4} \\left \\langle \\nabla R(\\frac{p}{2}), y - p\\right \\rangle$ (instead of $-\\frac{1}{2}$); (b) the second equality should have $p - y$ in the last term; (c) adjust the constant $3\\rho$ accordingly.\n\n(7) Line 856; \"even in the even\" sounds incorrect.\n\n(8) Line 860; should be $\\mathcal{P} \\times [0, H]^\\star$ instead.\n\n(9) Line 965; fix the \"??\"", "was_revised": true, "final_justification": "I did not have any concerns and continue to vote for acceptance.", "rebuttal": "Thank you for your detailed review. To answer your questions:\n\n(1) We remark that there is a typo in the first line of the proof, it should say $\\phi : B_1^d \\to \\Delta^{2d+1}$. The first equality below line 993 is the definition of calibration error. The following inequality uses the fact that $x_t’(p’) = \\sum_{p : \\psi(p) = p’} x_t(p)$ (by the definition of $x_t’$ as the pushforward of $x_t$ by $\\psi$) together with Jensen’s inequality to split apart the norm into the individual pieces corresponding to the values of $p$ for which $\\psi(p) = p’$. The final inequality uses the fact that $\\psi$ is a $\\ell_1$-contraction on $\\Delta^{2d+1}$. \n\n(2) We are interested in the regime when d is large and epsilon is not too large (e.g., think of eps as a constant or $\\epsilon \\sim 1/\\text{polylog}(d)$). For such parameters, $(1/\\epsilon)^d$ is extremely large, and in particular larger than $d^{1/\\epsilon}$. \n\n(3) Those are great questions for future work!"}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (oral)