Simultaneous Swap Regret Minimization via KL-Calibration
Authors: Haipeng Luo
Spandan Senapati
Vatsal Sharan
Venue: NeurIPS 2025 spotlight ()
Keywords: Calibration
KL-Calibration
Swap Regret
Primary area: theory
TL;DR: We propose a novel calibration measure, referred to as (pseudo) KL-Calibration, and leverage it to establish several new bounds on the swap regret for a range of significant loss functions.

Abstract: Calibration is a fundamental concept that aims at ensuring the reliability of probabilistic predictions by aligning them with real-world outcomes. There is a surge of studies on new calibration measures that are easier to optimize compared to the classical $\ell_1$-Calibration while still having strong implications for downstream applications. One recent such example is the work by Fishelson et al. (2025) who show that it is possible to achieve $\tilde{\mathcal{O}}(T^{1/3})$ pseudo $\ell_{2}$-Calibration error via minimizing pseudo swap regret of the squared loss, which in fact implies the same bound for all bounded proper losses with a smooth univariate form. In this work, we significantly generalize their result in the following ways: (a) in addition to smooth univariate forms, our algorithm also simultaneously achieves $\tilde{\mathcal{O}}(T^{1/3})$ swap regret for any proper loss with a twice continuously differentiable univariate form (such as Tsallis entropy); (b) our bounds hold not only for pseudo swap regret that measures losses using the forecaster's distributions on predictions, but also hold for the actual swap regret that measures losses using the forecaster's actual realized predictions.
    
 We achieve so by introducing a new stronger notion of calibration called (pseudo) KL-Calibration, which we show is equivalent to the (pseudo) swap regret with respect to log loss. We prove that there exists an algorithm that achieves $\tilde{\mathcal{O}}(T^{1/3})$ KL-Calibration error and provide an explicit algorithm that achieves $\tilde{\mathcal{O}}(T^{1/3})$ pseudo KL-Calibration error. Moreover, we show that the same algorithm achieves ${\mathcal{O}}(T^{1/3} (\log T) ^ {-\frac{1}{3}}\log (T/{\delta}))$ swap regret with probability at least $1-\delta$ for any proper loss with a smooth univariate form, which implies $\tilde{\mathcal{O}}(T^{1/3})$ $\ell_2$-Calibration error. A technical contribution of our work is a new randomized rounding procedure and a non-uniform discretization scheme to minimize the swap regret for log loss.

Simultaneous Swap Regret Minimization via KL-Calibration
Haipeng Luo" USC haipengl@usc.es
Spandan Senapati"
Vatsal Sharan"
USC ssenapat@usc.edu
USC Ssharan@usc.ee
Abstract
Calibration is fundamental concept that aims ensuring the reliability of proba- bilistic predictions by aligning them with real-world outcomes. There is a surge of studies new calibration measures that easier to optimize compared the classical & I-Calibration while still having strong implications for downstream appli- cations. One such recent example is the work by Fishelson et al. (2025) who show that is possible to achieve (33 pseudo fz-Calibration error via minimizing pseudo swap regret of the squared loss, which in fact implies the same bound for all bounded proper losses with a smooth univariate form. this work, we significantly generalize their result in the following ways: (a) in addition to smooth univariate forms, our algorithm also simultancously achieves (3T) swap regret for any proper loss with twice continuously differentiable univariate form (such as Tsallis entropy); (b) our bounds hold not only for pscudo swap regret that measures losses using the forecaster's distributions on predictions, but also hold for the actual swap regret that measures losses using the forecaster's 's actual realized predictions.
We achieve by introducing KL- Calibrationn, which we show is equivalent to the (pseudo) swap regret with respect to log loss. We prove that there exists an algorithm that achieves (TT/33) KL-Calibration error and provide an explicit algorithm that achieves (3) pseudo KL-Calibration error. Moreover,
stronger notion of calibration called (pseudo)
show that the same algorithm achieves ( 7') log(T/6)) swap regret with probability at least 1 5 for any proper loss with smooth univariate form, which implies (33) &g Eg-Calibration eтror. A technical contribution of our work is new randomized rounding procedure and a non-uniform discretization scheme to minimize the swap regret log loss.
1 Introduction
We consider online calibration - problem of making sequential probabilistic predictions over binary outcomes. Formally, at each time / = 1,.... T, a forecaster randomly predicts pt E [o, 1] while simultancously the adversary chooses yt E {0, 1}. and subsequently the forecaster observes the true label y/- Letting np denote the number of rounds the forecaster predicts pr p. the forecaster's predictions are perfectly calibrated for all E [0, 1]. the empirical distribution of the label conditioned on the forecast being p, i.e., the quantity Pp := Etp.=p 3t/np. matches The
f, C-Calibration error (q 2 1) is then defined as Cal, = Epe(o.1] _T, = (p- pp)²
related concept used in Fishelson et al. (2025) that we call pseudo calibration error measures the er- ror using the forecaster's conditional distribution P, Aoo. at time t, instead of the actual prediction
Pr. More specifically, the pseudo L, Calibbaraii error is defined as PCal,, == Σ Ep-P. (p 7p)
Author ordering is alphabetical.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where Op = ST M.Pp(p)
27-1 P.(p) By not dealing with the random variable pt, pseudo calibration is often
easier to optimize.
Two of the most popular calibration measures are & and f2-Calibration. It has been long known that Cal = ((T2/3) is achievable, and there are some recent breakthroughs towards closing the gap between this upper bound and standard lower bound Calı = S2( (T) (see more discussion in related work). For Eg-Calibration, Foster and Hart (2023) proposed an algorithm based on the concept of "calibeating" that achieves [[[aag] = Ö(T'). Moreover, a recent work by Fishelson et al. (2025) showed that PCal2 O is achievable by establishing equivalence pseudo swap regret of the squared loss and proposing an efficient algorithm based on the well-known Blum-Mansour reduction (Blum and Mansour, 2007) for minimizing pseudo swap regret.
More specifically, given a loss function f [0, 1] x {0, + R. the swap regret of the forecaster is defined as SReg* == [oPoo[0,1]-+0000 SReg where SReg. == Σt= f(pr. V1) ((rr)(())))) y/) measures the difference between the forecaster's 's total loss and the loss of a strategy that always swaps the forecaster's ' prediction via swap function Similarly, pseudo swap regret (Fishelson al., 2025; referred in their work as full swap regret) is defined using the conditional distribution of predictions Pe instead of pt itself: PSReg' == suPo:jo.1]-10.11 PSReg... where PSReg = Σ Ep-p, [e(p, 3t)
(p)())) y1)]. Fishelson et al. (2025) show that it is possible to achieve PSReg" = Ō(T3) when & is the squared loss, which, as we will show, further implies that the same bound holds for any bounded proper loss & with a smooth univariate form (refer to Section 2 for concrete definitions of proper losses and their univariate form).
In this work, we significantly generalize their results by not only recovering their results for pseudo swap regret, but also proving the same Ö(T3) bound for new losses such as log loss and those induced by the Tsallis entropy. Moreover, we prove the same bound (either in expectation high probability) for the actual swap regret, which was missing in Fishelson et al. (2025). To achieve these goals, introduce natural notion of (pseudo) KL- KL-Calibration, where the penalty incurred by the forecaster's 's prediction deviating from the empirical distribution of y (conditioned on the forecast being p) is measured in terms of the KL--divergence. Specifically, the KL-Calibration and the pseudo KL-Calibration incurred by the forecaster are respectively defined as
with
T
T
KLCal= ==
Σ PC PE( t=1
Σ
Ip: = p)KL(pp:)), p), PKLCal = Σ
Epmp, (KL(pn,)))
where KL(g.p) = y gog _ + (1 v) log 1- is the KL-divergence for two Bernoulli distributions with mean q and p respectively. It follows from Pinsker's inequality that KL p) Z (pp p)², therefore, KaCal 2 Cal2 and PKLCal > PCal2, making (pseudo) KL-Calibration stronger measure for studying upper bounds than (pseudo) fz-Calibration.
p
Contributions and Technical Overview Let L denote the class of bounded (in [-1, 1) proper losses. Our concrete contributions are as follows.
In Section 3, start by discussing the implications of (pseudo) KL-Calibration towards minimizing (pseudo) swap regret. In particular, in subsection 3.1, we show for each E E L2, where C2 is the class of bounded proper losses whose univariate form {(p) == Eyypp [((p y)] is twice continuously (PKL In subsection 3.2,
differentiable in (0, 1). we have SReg' = O (KLCal), PSReg* : we show that for each e E Lc. where LG is the class of bounded proper losses with G-smooth univariate form, (pseudo) KL-Calibration implies that SReg' < G Cal, < G Kal, PSReg" < G. PCalz I G. PKLCal. This gives us strong incentives to study PKLCal and KaCal.
In Section 4, we prove that there exists an algorithm that achieves E[ = OT'ss (log 7)$), To achieve so, first realize that (pseudo) KL-Calibration is equivalent to the (pseudo) swap regret of the log loss E(p, v) -y log p - (1 y) log(1 - p). i.e., KL SReg'. PKL PSReg Subsequently, we propose a non-constructive proof for minimizing SReg": our proof is based on swapping the forecaster and the adversary via von-Neumann's 's minimax theorem. Two particularly technical aspects of our proof are the usage of a non uniform discretization, which is contrary to all previous works, and the use of Freedman's 's inequality for martingale difference sequences.

---

We remark that our non-constructive proof is motivated from Hu and Wu (2024), who provide similar proof to show the existence of an algorithm that simultaneously achieves Of v /Tloo T) swap regret for any bounded proper loss. However, compared to Hu and Wu (2024), we use a non uniform discretization, which requires a more involved analysis." Moreover, due to the desired O(T*) nature of our final bounds, we cannot merely use Azuma-Hoeffding that guarantees (VTT) concentration. The aforementioned reasons combined make our analysis considerably non-trin -riviriiil and different than Hu and Wu (2024).
Combined with the implications of Section 3, show the existence of an algorithm that simul- taneously achieves the following bounds E[SReg"]: (a) O(T's (log 7) for the log loss; (b) O (log 2) for each E C2: (c) TG (log T) for each E Lg: and (d) OTT (logT)'s for each & E CVC2 U Ca}. Notably, our result is better than Luo et al. (2024) who studied
the weaker notion of external regret, defined REG suPpejo.1] Σ 2 {(p, y2) E(p.
and showed that the Follow-the-Leade (FTL) algorithm achieves REG = Olog 7) for each L L2 L La. however incurs REG" S2(T) for a specific & E L
In Section 5, we propose explicit algorithm that achieves PKLCal = O & (log T) Similar Fishelson et al. (2025), we utilize the Blum-Mansous reduction for minimizing PSReg' for the log loss. However, our key novelty lies in the usage of a non uniform discretization and a new randomizing rounding procedure (Algorithm 4) for the log loss. Since the log loss is not Lipschitz, we show that the common rounding schemes studied in the literature fail to work for our considered discretization. A natural implication of our result is that, since PSReg" I G PKLCal for any i E La, we recover the result of Fishelson et al. (2025). However, since PSReg" able deal with new losses, and even the log loss which is unbounded.
/ = O(PKLCal)
for any l L2.
Finally, in Appendix E, we show that if we only consider the class of bounded proper losses with a smooth univariate form, our algorithm guarantees
Cal2 = O (TL/3
(log (log - 1og(T/6)) Msrca = = (Io - log(T/6))
with probability at least - where Msr supreca SReg'. This marks the first appearance of a sub-vT high probability bound for classical &g -Calibration via an efficient algorithm.
Related Work Calibration can also be viewed from the lens of simultaneous regret minimization (Kleinberg et al., 2023; Hu and Wu, 2024; Luo et al., 2024). It known from Kleinberg et al. (2023) that & Caalibbrdde forecasts can simultaneously lead to sublinear swap regret for all & E f. where recall that C the class of bounded (in [11, proper losses. However, as shown by Qiao and Valiant (2021); Dagan et al. (2024), for any forecasting algorithm there exists adversary that ensures that Cal (779.55389 thereby sidestepping the goal of achieving the favorable vT style regret guarantee. Despite the limitations of calibration, Hu and Wu (2024) proposed an explicit algorithm that achieves E E'suptec SReg'1 = O(VT Tog Compared to (Hu and Wu, 2024), we show that single algorithm in fact achieves Ö(T²)) swap regret for important subclasses of L and even the log loss, while simultaneously achieving Ö(T+) ) swap regret for any arbitrary Ł L. Notably, the result of Hu and Wu (2024) does not apply to the log loss since does not belong to L. With an appropriate post-processing of the predictions, stronger analogue of simultaneous swap regret minimization has also been studied in the contextual setting (Garg et al., 2024; referred to as swap omniprediction), where the forecaster competes with functions from a hypothesis class F. Notably, in swap omniprediction, both the loss function and the competing hypothesis are parameterized by the predictions themselves. For this, Garg et al. (2024) showed that it is impossible achieve (VTT) swap omniprediction error for the class of convex and Lipschitz loss functions, even in the simplest setting where F contains the constant 0, 1 functions. Additional related work is deferred to Appendix A.
"Our non- non-uniform discretization scheme has appeared before (Kotlowski et al., 2016), albeit in a different context. Its combination with other techniques in our paper results in significantly different approach.
3

---

2 Preliminaries and Background
Notation For m E N. [m] denotes the index set (1,...,, m)) We reserve bold lower-case alphabets for vectors and bold upper-case alphabets for matrices. The notation I[-1 refers to the indicator function, which evaluates to 1 if the condition is true, and 0 otherwise. We use e; to represent the i-th standard basis vector (dimension inferred from context), which is at the i-th coordinate and 0 everywhere else. For any i E N, we use ÅІ to represent the (A- 1)-dimensional simplex. Moreover, we use 1o. to represent the set of all probability distributions over [0. 1]. We use Ft, E, to represent the conditional probability, expectation respectively, where the conditioning is over the randomness till time t - (inclusive). We use (L(p, q). TV(p, q). x q) to represent the KI. divergence, total variation distance, chi-squared distance between two Bernoulli distributions with means p. q. For a set T, its complement is I = Ω2 I where the sample set 52 shall be clear from the context. A twice differentiable function f 'D + R is a-smooth over 'D C R if (*) S a for all E D. A function f W + R is a-exp-concave over convex set W if the function exp(-a (w)) is concave over W. We use the notation (-) to hide lower order logarithmic terms.
Proper Losses A loss e: (0, 1] x {0, 13 - R is called proper if Tyyr (p... y) S Egy-plei (((p'. y) for all p.p' E [0, 1]. Intuitively, a proper loss incentivizes the forecaster to report the true distribution of the label. Throughout the paper, we shall be primarily concerned about the family L (or a subset) of bounded proper losses, i.e., L == {L s.t. is proper and ((p, y) E [-1, 1J for all p E [0, 1 y e {0, 13}, even though our results hold for (and in fact achieved via) the unbounded log loss. For a proper loss E, the univariate form of É is defined as E(p) = By-pp [e(p, v)]. It turns out that the univariate form of a proper loss is concave. Moreover, one can construct proper loss using a concave univariate form based on the following characterization lemma.
Lemma 1 (Theorem in Gneiting and Raftery (2007)), A loss 8: [0. 1] x 10
proper
if and only if there exists concave function f such that l(p. = f(p) + (gp. y y-yy--p p) for all p E [0, 1).y E {0, 1}. where 9p denotes a subgradient of J at p. Also, J is the univariate form of f.
Examples of proper losses include squared loss E(p, y) = (p - u)², log loss {(p,y) y log 1 + (1
y) log T spherical loss E(p. y) = p1+(1-p)(1 etc.
Bregman Divergence For convex function o, let BREG, (x. v) = o(x) - p(y) (0b(y) --
denote the Bregman divergence associated with p. The following lemma is important to our results.
Lemma 2 (Lemma 3.8 in Hu and Wu (2024)). Let u 10, 1] + [-1, 1] be a twice differentiable
concave function.. Then, we have BREG (1. p) = 1 |u" [u"(x)] (f - 1d
Problem Setting As mentioned in Section I, we consider calibration, where the interaction between the forecaster and the ad adversary is according to the following protocol: at each time t = 1....... T. (a)
the forecaster randomly predicts pt E [0, 1] and simultaneously the adversary chooses y/ (0. 1}: (b) the forecaster observes yt- Throughout the paper, we shall consider algorithms that make predictions
Pt that fall in finite discretization C [0. 1). According to (1), the Kl-Caalibatiin, Pseudo
KL-Calibration incurred by the forecaster are KLCal = Epez Σi= Mpp = =p)KL(pp.P) PKLCal PKLCal =
assume that the adversary is oblivious, that i Hpp=pl Pp >x xP((() For simplicity, we
EpezEI 1 (())) p), where P3 > wcl[pppp]
Σ. pp(p)
it selects yi..... at time t = 0 with complete knowledge of the forecaster's algorithm." Our goal is to minimize the (pseudo) KL-Calibration error, which as we show in Section 3, has powerful implications.
As mentioned, the swap regret of the forecaster with respect loss function é againsst a swap function : [0, 1] + [0,1] is SReg', = Et= Epp, Me) (( y)). Swap regret is then defined as SReg = suPo.jo.1]-[[.11 SReg.. Similarly, the pseudo swap regret is PSReg = 10 PSReg where PSReg = Epez ΣT (((p, vi) - (() y:)). We fur- ther define maximum (pseudo) swap regret with respect to the class of bounded proper losses L as
For convenience, we set 0 = 0. This is because if npp 0. the forecast pt p was never made and thus does not contribute to the calibration error.
Howeeer, results generalize directly an adaptive adversary who decides ye based pi..... P
Pt-1.

---

Msrg == suprec SReg'. PMsrg == c PSReg'. For subset of losses L' S L, we define Msrg and PM similarly, with the supremum over f E L'. The usage of l for bounded proper loss, or the log loss (which does not belong to L) shall be clear from the context.
3 Implications of (Pseudo) KL-Calibration
In this section, we discuss the implications of (pseudo) KL-Calibration towards minimizing the (pseudo) swap regret. In particular, we shall show that (pseudo) KL-Calibration upper bounds the following: (a) (P)SReg' for all & E L2 (subsection 3.1); (b) (P)Msrco (subsection 3.2). This gives strong incentive to study (pseudo) KL-Calibration.
The following proposition, which relates (pseudo) swap regret with Bregman Divergence is central to all subsequent results developed in this work.
Proposition 1. For any proper loss & and swap function : [0, - [0, 1], ler BREG be the Bregman divergence associated with the negative univariate form -f. We have
T
SReg.
Σ
Σ
Uy:
-
(EREG_e(Pp.)) - BREG B (p)))
PEZ
1=1
T
e PSReg
Σ PEZ
Σ
Pr(v)
BREG (p))
1=/1
Eis 1p pll where Pp
Eie Pe(plm Furthermore, L1-1Pe(P) Pe(p)
Pp
21-1 -|pt=p]
T
SReg'= ΣΣ P=2!=1
Tp = p) e(pp, PSReg
ΣΣ PEZ
PREG =lpps p)-
The proof of Proposition 1, deferred to Appendix B, follows by an application of Lemma I and is similar Hu and Wu (2024). Two particularly interesting applications of Proposition I are:
, the univariate form is {(p) = -p-p2. and BREG (PE:-e(Pp:P) (pp -0--- 2) Therefore, SReg' = Cal2, PSReg = PCal2.
For the squared loss Epp y) = (p-
For the log loss {(p y) y log 1 + (1 y) log r-p the univariate form is E(p) Ey (((p, v) p lp - (1 - p) log(1 p). Moreover, as can be verified by direct computation, the associated Bregman divergence BREG- p) is exactly equal to KL p). Therefore, we have SReg* KaCal, PSReg = PKLCal. This equivalence between (pseudo) KL-Calibration and (pseudo) swap regret of the log loss shall be our starting tool towards the developments in Sections 4, 5, where bound KLCal, PKLCal respectively.
Note that since PSReg & weaker notions compared to Cal, and KLCal respectively.
[[[Reg'] trivially holds by definition, PCal2 and PKL are indeed
3.1 (Pseudo) KL-Calibration implies (pseudo) swap regret for all L E L2
In this subsection, we show that SReg' OKLCal),, PSReg = O(PKLCal) for each E E L2, where L2 E L s.t. the univariate form E(p) is twice continuously differentiable in (0, 1))-
Note that according to Lemma 1, for all & L. the univariate form must be concave, Lipschitz, and bounded, for the induced loss E(p. y) to be proper and bounded. In addition to these implicit constraints, require the condition that the second derivative 8 (p(p) is continuous in (0, 1). We state several examples of losses that belong to L2. First, the squared loss clearly belongs to C2. since its univariate form f(p) = p p². Second, consider generalization of the squared loss via Tsallis entropy, which corresponds to a loss with the univariate form E(p) -c p=, where we choose a > 1 and the proportionality constant e > 0 is to ensure that the induced loss E(p. y) is in [-1, 1] (refer Lemma 1). We have, E(p. y) c(a 1 1)p² acp" - y, which is in Lz. Third, the spherical loss has the univariate form E(p) vp² + - 2)2 and is also contained in Cz.
5

---

The following lemma, derived by Luo et al. (2024), provides a growth rate on the second derivative of any É E L2 and a key ingredient for our proof of the desired implication.
Lemma (Lemma in Luo al. (2024)). For function that is concave, Lipschitz, and bounded over [0, 1] and twice continuously differentiable over (0, 1), there exists a constant c >> O Such that (p) I c max ( 1 for all E (0,1).
Using this to bound (p)l in the statement of Lemma 2, we immediately obtain the following proposition whose proof can be found in Appendix B.
Proposition 2. Let & E L2. Then, we have BREG-r(Ā. )) = O (KL(P.)) and thus
SReg' =O(KLCa)),
PSReg" O(PKLCll).
Note the constant cy hidden in the O(.) notation in the result above is exactly the constant guaranteed by Lemma 3, which is finite. However, this is not sufficient conclude that supreC, Cg oo (since L2 is infinite), therefore, we do not necessarily guarantee that (P)Msr (defined as c, (P)SReg') is ((P))KLCal) We remark that this is only minor technical issue (that has also implicitly appeared in the prior work of Luo al. (2024)), and our result in Proposition implies that (pseudo) KL- AL-Calibration simultaneously bounds (pseudo) swap regret for all & E L2- This in itself quite meaningful and perfectly aligns with the goal in downstream decision making to guarantee diminishing (swap) regret for all loss functions simultaneously. Henceforth, all subsequent results related to (pseudo) swap regret for L2 are stated similarly. We also remark that Proposition 2 holds more generally for any subclass of proper losses where each loss satisfies the growth rate in Lemma 3. To keep the exposition simple, we only state our results for Cz.
3.2 (Pseudo) KI.-Calibration implies (pseudo) maximum swap regret against LG
We now consider another class Lg. containing proper losses whose univariate form is G-smooth, i... LG {E L s.t. [p"(p)] S G for all p [0, 1]]. Losses that belong to LG include squared loss, spherical loss, Tsallis entropy for a 2 2, etc. Notably, the latter does not lie in Lo for E (1. Using Lemma 2 again, along with the fact PCalz S PKLCal, Calp S KLCal due to Pinsker's inequality, we immediately obtain the following.
Proposition 3. Let é E Lg. Then, we have BREG_:(P, S G(p - p)2 and thus
Msrca S G. Call S G KLCal, PMsr S G PCal2 G PKLCal.
The proof of Proposition 3 is deferred to Appendix B. As already mentioned, Fishelson et al. (2025) proposed an algorithm that achieves PCal, ÖT ), which implies that the same algorithm in fact ensures PMsr (G T5). However, the implications of KLCal, PKL allow us get simultaneous guarantees for a broader subclass of proper losses, particularly, C2 U LG.
4 Achieving KL-Calibration
In this section, prove that there exists algorithm that achieves B[SReg O(T's (log 7) for being the log loss, therefore the same algorithm achieves Eal OT (log & Our proof is non-constructive, since it is based on swapping the adversary and the algorithm via the minimax theorem (Theorem 3 in Appendix C), and deriving a forecasting algorithm in the dual game.
Theorem 1. There exists an algorithm that achieves E[SReg"] O(T's (IogT) &) for the log loss, where the expectation taken over the internal randomness of the algorithm.
The proof of Theorem is quite technical and is deferred to Appendix C. We discuss the key novelty of our proof here. Two particularly technical aspects of our proof are the usage non uniform discretization, which is contrary to all previous works, and the use of Freedman's 's inequality for martingale difference sequences (Lemma 8). In particular, we employ the following discretization scheme: Z =
sin" 2R and K E N is constant to be specified later. For convinience, we set 2g = 0, =k = 1, however, 2o, 2 are not included in the discretization. For our analysis, require discretization scheme that satisfies the following
C [0, 1], where

---

constraints: (a) 2, 24-1 = x for all [K]; (b) (axx( 1:8:1
O x for all Ō(K). The uniform =1(1-1))
i E K - 1]: (c)
Ei=1 K-1
21 = O(K3): and (d) EKT
v=(1==)
discretization 2 x K-11 satisfies (a), (c), (d) above, however, doesn't satisfy (b). As we show in Lemma 6 (Appendix C), our considered non uniform discretization achieves all these required bounds by having finer granularity close to the boundary of [0, 1], thereby making suitable for our purpose. The following steps provide brief sketch of our proof, which is proved for an adaptive adversary and therefore also holds for the weaker oblivious adversary.
Step I We only consider discretized forecasters that make predictions that lie inside Z. Since the strategy space of such forecasters is finite, and that of the adversary is trivially finite, the minimax theorem (Theorem 3) applies, and we can swap the adversary and the algorithm, thereby resulting in the dual game. In this dual game, at every time i, the adversary first reveals the conditional distribution of yr. based which the forecaster predicts Pt. We consider forecaster F which at time t does the following: (a) it computes Pr = Ex(r:]: (b) predicts p: = argmin z lp+ z|. For such a forecaster, we obtain high probability bound on SReg'. e and subsequently bound E[[Reg").
Step II Applying Lemma 8, we show that for each (with n2 n22s))
max (vm (1(11 24)
2 Σ JTp =l( v1) S 2 log 8
2 log
2K
with probability at least 1 - 8KT. Using this, we bound 1 - where pj is a shorthand for Pa. Notably, the bound above dictates separate consideration of i E I and E I (depending on which
term realizes the maximum), where I == {i E [K- - 11; < 2,(1
log 2
2K
Step III Next, we write SReg' as the sum of two terms SReg' Term + Term II, where Term I = Eier (P,L 21), Term II = Eie n,KKL zi), and bound Term I, II individu- ally. Since 2L) I (p;,
(pc=z.) 21[1= we utilize the bound on |p; =i- obtained in the previous step and show that Term II = O 0( T
RT + K log J) Importantly, the use of Freed- man's inequality provides variance term that mitigates the potentially small denominator of logb): t)) Combining, we ob- T + Klog K) log
(p-=2) (1112 Similarly, we show that Term o
R
tain SReg" = O F + (log K) log with probability at least 1 - SKT. Subsequently, bound E[SReg'] by setting = 1/T,, K = T ()o
Equipped with Theorem 1, we prove the following stronger corollary (proof deferred to Appendix C). Corollary 1. There exists an algorithm that achieves the following bounds simultaneously:
|KLCaa]] = ( (logTT) &), E [Msrcal = TT (
E [Msrc,] (T's (log 8)
E [Msrex(coucaa] O (log T) )),
where the expectation is taken over the internal randomness of the algorithm.
Achieving Pseudo KL-Calibration
In this section, we propose an explicit algorithm that achieves PSReg = O (log for the log loss, therefore the same algorithm achieves PKLCal = O (log 8). Our algorithm is based on the well-known Blum-Mansour (BM) reduction (Blum and Mansour, 2007) and extends the idea from Fishelson et al. (2025). First, we employ similar but slightly different non uniform discretization scheme that adds two extra end points žy and ž to the one used in the previous section (for technical reasons):
2 = {zo. 21, .1,..., "..,,,KK -1, zK} where 2p = sin? π
4K" 2 sin? Ti for i E [K- - 1],2k = cos2 π
2K
4K'
7

---

and K E IN is constant to be specified later. The same scheme was used before by Rooij and Erven (2009); Kotlowski al. (2016) for different problems. Since the conditional distribution P, has support over 2, taking supremum over all swap functions a 2 + 2 in Proposition 1, we obtain
ΣΣ Pi()) inf BREG- o())) 2 PSReg" (2 2
sup PSReg PSRegg 2
PEZ 0:2422
K²
where the inequality follows by choosing (p)) argmin BREG- For this choice of a from Kotlowski et al. (2016, page 13), we have BREG- (p)) - (2 22) RT. Therefore,
PSReg' < sup PSReg' + (2 v2) π o:Z-+2
T
(2)
K2
and it suffices to bound sup..z-z PSReg which we do via the BM reduction. Towards this end, we first recall the BM reduction. The reduction maintains K + external regret algorithms .a......A. k At each time t, let qt E AK+ represent the probability distribution over Z output by A,. Let Q: (9t. ........... qt.k be the matrix obtained by stacking the vectors qt, ..... 9t.K as columns. We compute the stationary distribution of Q i.e., a distribution pt E AK+1 over that final distribution of predictions (that is, Pr(2;)
satisfies Q.P. P.- With p. being
Pt.:),
draw a prediction from it and observe Y/-- After that, we feed the scaled loss function pr.s((.,,)))
to A, Let l,; Pt, E IR K+I be scaled loss vector, where ( (()j.8)). ) It then follows from Blum and Mansour (2007, Theorem 5) that sup,: PSReg, Ei REG,, where REG, suP Σ (q.. - e regrets of the K + algorithms. We summarize the discussion so far in Algorithm 1.
Le. (..s).ie i... the pseudo swap regret is bounded by the sum of the external
Algorithm 1 BM for log loss
Initialize: A4 for i E (o...., .....,KK K} and set qı = K+I
K+1
1: for t = 1,...
2: Set Q: 9t .......... kx
3: Compute the stationary distribution of Qt, i.e., pt E 4 that satisfies QiP: Pe:
4: Output conditional distribution Pt, where (2,) (i) and observe yr:
5: for O,.... K
6: Feed the scaled loss function (w,(w) pr, we) to A, (Algorithm 2) and obtain 1
remains to derive the i-th external regret algorithm A, that minimizes REG,- Note that A is required to predict distribution qt over Z and is subsequently fed scaled loss function pt. ye) at each time f. We propose to employ the Exponentially Weighted Online Optimization (EWOO) algorithm along with a novel randomized rounding scheme for A, (Algorithm 2).
EWOO was studied by Hazan et al. (2007) for minimizing the regret sup.gg when W is a convex set, and the loss functions ft's are exp-concave. Since the log loss is 1-exp- concave in p over [0, 1] ((Cesa-Bianchi and Lugosi, 2006, page 46), EWOO; (an instance of EWOO
f((w) [w)
for A,) with functions {f defined as (t,( = ((w, vo) for all w E W, where W = [0, 1] a natural choice.
Next, we derive a bound on the regret of EWOO,, Towards this end, we realize that the scaled log loss (w)(w) = pt, [((,, y1) is 1-exp-concave since exp(- f.:((:))))) = wyPe... (1 - w) (p.. is concave when Pt, E [0, 1]. Appealing to (Hazan et al., 2007, Theorem 7), we then obtain the following:
Lemma 4. The regret of Algorithm 3 satisfies supwew Σ fr,i(wr,)) f..(w)) < log(T + 1).
Note that at each time t, EWOO; outputs Wt,; E [0, 1), however, A, required predict distribution qt E 4K+1 over Z. Thus, we need to perform a rounding operation that projects the output w of EWOO, to a distribution over Z. In Remark 1 in Appendix D, we show that the following two known rounding schemes: (a) rounding W to the nearest
2 and setting qt as the corresponding one-hot vector; (b) the rounding procedure proposed by Fishelson et al. (2025), cannot be applied to our setting since they incur Q(1) change in the expected loss (gr la) l(we, Ve), which is not
8

---

Algorithm 2 The i-th external regret algorithm (A,))
1:
for t= 1,...,7 .
2: Set W0, [0, as the output of EWOO; (Algorithm at time
3: Predict It.i = RROUND (wx,a) (Algorithm 4);
4: Receive the scaled loss function (w,(ww) = Pr.f(Wu, Ur).
Algorithm 3 Exponentially Weighted Online Optimization (EWOO,) with scaled losses
1: for 1,..., T
2: Set weights (e,s(w) = exp --E=iirr())) fna(w)) for all e W;
Swew a wwew ns,
3: Output We,
sufficient to achieve the desired regret guarantee. To mitigate the shortcomings of these rounding procedures, we propose different randomized rounding scheme for the log loss (Algorithm 4) that achieves a O {xz) change in the expected loss, as per Lemma 5.
Lemma 5. Let E [0, 1] and p .pt E Z be neighbouring points in Z such that p S ppt Let q be the random variable that takes value p with probability x
pt p--D and px* with probability (1-pt)
p-p (1-p Then, for all y E {0, 1}. we have E[l(g, y)1 - E(p. v) O ( (Rz)
x p
The high-level idea of the proof as follows: since the log loss convex in p (for any y E {0, 1)). we have ((g, u) E(p.y) y) < 6' (g. y) (q p) = (g-w which is 1 if 1, and 1-
((1-))
y = By direct computation of E and E
1-g we show that E
p
| -15
(p+ - )² max [1-p (11-p)) = result due to Lemmas 6 (Appendix C) and 7 (Appendix D).
K where the last step follows from a technical
Combining everything, we derive the regret guarantee REG, A; (Algorithm 2). follows from Lemma 5 that at any time I, the distribution qr obtained by rounding the prediction wx,s of EWOO, as per Algorithm satisfies (qr.i, La) = E(wi, Me) + O (())). Multiplying with Pt, and summing over all f, we obtain
T Σ qu. e,, e,. = - Pc. Pe:llwi, (t,(((e). +0
Σt= Pe,
K2
ΣT Ph.i
log + Σt Pe,
Σ fu,(wr,) - fes(w) +
= =
< sup wEW
K²
K²
where the last equality follows from Lemma Therefore, the regret REG, of A; satisfies REG, -T
O (log T
Φ² Eim pts). Summinn over all i, we obtain
K
REG; = =0 K Klog T +
K
T
= 0 K log ) T
T
sup PSReg o:z-2
<
K2
Pt.
R2
1=
1=0
t=1
Finally, it follows from (2) that PSReg O (Klog
F))
0 ( (log on choosing
K = K(TT/log log 3 Therefore, we have the main result of this section.
Theorem 2. Choosing K = (T' [oT'/oo'') } Algorithm 1 achieves PKLCal = O (Ir (log
Note that Algorithm requires knowledge of the horizon T to choose the discretization parameter K. However, since (pseudo) KL-Calibration is equivalent to (pseudo) swap regret of the log loss, we can use the doubling trick to avoid the requirement of knowing the time horizon. The analysis of doubling trick for swap regret is exactly identical to that for external regret and is deferred to

---

Algorithm 4 Randomized rounding for log loss (RROUND)
Input: p E [0,1]. 1]. Output: Probability distribution Ak+1i
Scheme: iet E {O,...,... K 1} be such that p E [24, 2411). Output E AK+1, where
1
2++1 p
1 p- and a =0 Vj $ (iū+1}
qi D
2i41 (1 - 2++1)
gi+1
D
2, zi)
with D = 2;(1 ([1=
p-zc
-
being the normalizing constant.
#011 (1-11---- 1
Cesa-Bianche and Lugosi (2006). Moreover, as we show in Appendix D, the overall computation cost of Algorithm over 7 rounds is Ö + T TT)), where ST is the time required to compute the stationary distribution of Qr, which can be obtained efficiently by the method of power iteration; therefore, Algorithm is efficient. In a similar spirit as Corollary 1, we can show Algorithm achieves the following regret bounds simultaneously. The proof is Appendix D and for most part follows similar to Corollary 1, except that we prove and utilize the bounds (a) PCal: S PCal:: (b) for any & E L, PSReg v 4PCal1
Corollary 2. Algorithm achieves the following bounds simultaneously:
PKLCal = OT (log 8) PMsr = O T (log 8)
PMsr = O (log 8) PMsrct(couca) OT (log 7)
We remark that while we do not have a concrete algorithm for KLCal, in Appendix E, we show that we only consider Lg. then our Algorithm or the algorithm of Fishelson et al. (2025) already achieves a O T (log T) log " high probability bound for Msr
Conclusion and Future Directions
In this paper, we introduced new stronger notion of calibration called (pseudo) KL-Calibration which not only allows us to recover results for classical (pseudo) fz-Calibration, but also obtain simultaneous (pseudo) swap regret guarantees for several important subclasses of proper losses. We also derived the first high probability and in-expectation bounds for Calg. Several interesting questions remain, including (1) obtaining an explicit high probability swap regret guarantee for the log loss, similar Section E; (2) improving the T dependence (c.g., to VT as in Hu and Wu (2024)) for a bounded proper loss in Corollaries 1, 2; and (3) studying KL-Calibration in the offline setting.
Acknowledgement
We thank Fishelson, Kleinberg, Okoroafor, Paes Leme, Schneider, and Teng for sharing draft of their paper (Fishelson et al., 2025) with us. HL is supported by NSF award IS-19936077 SS supported by NSF CAREER Award CCF-2239265. VS is supported by NSF CAREER Award CCF-2239265 and an Amazon Research Award. This work was done in part while VS was visiting the Simons Institute for the Theory of Computing.
References
Arunachaleswaran. E. R., Collina, N., Roth, A., and Shi, M. (2025). An elementary predictor obtaining distance to calibration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1366-13777 1370. SIAM. 13
Beygelzimer, A., Langford, J., Li, L.. Reyzin, L., and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings. 22
Blum, A. and Mansour, (2007). From external to internal regret. Journal of Machine Learning Research, 8(6). 2, 8
10

---

Cesa-Bianchi N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press. 8, 10
Dagan, Y., Daskalakis, C., Fishelson, M., Golowich, N., Kleinberg, R., and Okoroafor, (2024). Improved bounds for calibration via stronger sign preservation games. arXiv preprint arXiv:2406. 13668.
Fishelson, M., Kleinberg, R., Okoroafor, P., Paes Leme, R., Schneider, J., and Teng, (2025). Full swap regret and discretized calibration. In Kamath, G. and Loh, P.-L., editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 444-480. PMLR. 1, 2, 3, 6, 7, 10, 20, 22, 26
Foster, D. P. and Hart, S. (2021). Forecast hedging and calibration. Journal of Political Economy,
129(12):3447-34)) 3490. 13
Foster, D. P. and Hart, S. (2023). "calibeating": Beating forecasters at their own game. Theoretical Economics, 18(4):1441-147))
Garg. S., Jung, C.,, Reingold, O., and Roth, A. (2024). Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2725-2792. SIAM. 3, 12
Gneiting, T. and Raftery, A. E. (2007). Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-37..
Hazan, E., Agarwal. A., and Kale, (2007). Logarithmic regret algorithms for online convex optimization. Machine Learning. 69(2):169-19) 192. 8
Hu, L.. and Wu, Y. (2024). Predict to Minimize Swap Regret for All Boonded Tasks In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 244-263, Los Alamitos, CA, USA. IEEE Computer Society. 3, 4, 5, 10
Kleinberg, B., Leme, R. P., Schneider, J., and Teng, Y. (2023). U-calibration: unknown agent. In The Thirty Sixth Annual Conference on Learning T'heory, pages 5143-5145. PMLR. 12, 13, 19, 22
Forecasting for an
Kotlowski, W., Koolen, W. M., and Malek, A. (2016). Online isotonic regression. In Conference on Learning Theory, pages 165-1188. PMLR. 3,
Luo, H., Senapati, S., and Sharan, V. (2024). Optimal multiclass u-calibration error and beyond. In Advances in Neural Information Processing Systems. 3, 6, 12
Okoroafor, P., Kleinberg, R., and Kim, M. (2025). Near-optimal algorithms for omniprediction. arXiv preprint arXiv:2501.17200 12
Qiao, M. and Valiant, G. (2021). Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 456-466.
Qiao, M. and Zheng, I.. (2024). On the distance from calibration in sequential prediction. In Agrawal, S. and Roth, A., editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4307-4357. PMLR. 13
Rooij, S. and Erven, T. (2009). Learning the switching rate by discretising bernoulli sources online. In Artificial Intelligence and Statistics, pages 432-439. PMIR..

---

Contents
1
Introduction
2 Preliminaries and Background
3 Implications of (Pseudo) KL--Calibration
3.1 (Pscudo) KL-Calibration implies (pseudo) swap regret for all & C2
3.2 (Pseudo) Ca-Caaiibatioon implies (pseudo) maximum swap regret against Lg
Achieving KL-Calibration
Achieving Pseudo KL-Calibration
Conclusion and Future Directions
10
Additional Related Work
12
B Deferred proofs in Section 3
13
B.1 Proof of Proposition 1
13
B.2 Proof of Proposition 2.
13
B.3 Proof of Proposition 3
14
Deferred proofs in Section 4
14
C.1 Proof of Theorem
14
C.2 Proof of Corollary
19
D Deferred proofs and discussion in Section 5
19
D.1 Computational cost of Algorithm
19
D.2 Expected loss of common rounding schemes
20
D.3 Proof of Lemma
20
D.4 Proof of Corollary
22
High probability bound for maximum swap regret against La
22
Additional Related Work
Simultaneous regret minimization Kleinberg et al. (2023) proposed U-Calibration, where the goal is to simultaneously minimize the external regret REG for all l e L and provided an algorithm that achieves U-Calibration error UCal == suprec REG" = (VTT). In the multiclass setting with K classes, Luo et al. (2024) proved that the minimax error is O KT)). With an appropriate post- processing of the predictions, the concept of U-Calibration has also been extended the contextual setting (referred to online omniprediction (Garg et al., 2024)). Very recently, Okoroafor et al. (2025) have shown that is possible to achieve ((VT) omniprediction error for family of bounded variation loss functions against hypothesis class FF with bounded complexity, thereby surpassing the limitations of swap omniprediction.
12

---

Weaker notions of calibration Understanding the limitations of online calibration, i.e.. Cal1 ((VT) is impossible, has led to recent line of work aimed at studying weaker notions of calibration which are still meaningful for downstream loss minimization tasks, e-g., continuous calibration (Foster and Hart, 2021), U-Calibration (Kleinberg et al., 2023), distance to calibration (Qiao and al., 2025). Particularly, the last two works considered the
Zheng, 2024; Arunachaleswaran problem of minimizing the distance to calibration (CalDist defined the & distance between forecaster's vector of predictions and that of the nearest perfectly calibrated predictor, and proposed non-constructive, constructive proof respectively that there exists an algorithm that achieves CalDist; O(vT). Since CalDist, S Cal1 S VT. Calg, our Algorithm in fact ensures that CalDist O (log 7' - / (Tog(T/)) with probability least 1 ō, while simultaneously
minimizing swap regret for several subclasses of L.
B Deferred proofs in Section 3
B.1 Proof of Proposition
Proof. For simplicity, we only prove the result for PSReg' since the result for SReg follows by simply replacing (p) with Ipp pl. We have the following chain of equalities:
PSReg
Σ>
Σ Pe(p) v.) ((o(p).
Σ
Σ
Pi(p) (e(p) + (de(p). -p) - -(((()) - -
PEZ t=1
T
Σ PEZ
Σ P((e)
(e(p) + (8(pp), -p - -- o(p)))
(0
t=1
Σ PEZ
Σ ((())
(BREG- - BREG (p)),
where the second equality follows from Lemma 1, while the final equality follows by adding and subtracting (pp). Taking supremum over o: [0, 1] [0, 1]. we obtain
sup PSRegk = =Σ (=10.1
Σ P((r)) t=1
BREEG (0.0]
inf
BREG BREG-e(Øp a(p))
PEZ
Next, realize that BREG, (3r, y) BREG- e(p (p)) = Therefore,
2 since & is convex, and the choice of (p)) 0p leads to
T
PSReg
Σ PEZ
Σ [=1
P((p)
BREG BREG-<(pp.1))
which completes the proof.
B.2 Proof of Proposition
Proof. For simplicity, we only consider the case when S Ô. since the other case follows exactly similarly. Applying the result of Lemma obtain
[" 1e" (6 u)du Sc.
(*+
-- - (p n)du,
BREG-
P
where the inequality follows from Lemma 3. By direct computation, the integral above evaluates to
dp +1 D) f dj
1- P log P + ((--) p) logg 1- KL(ý.p).
p
Therefore, we have BREG r(ū.p) c. KL(İ, p). which completes the proof of the first part of the Proposition. The second part follows by combining the result of Proposition with the result obtained above, and taking supremum over E Lz. This completes the proof.
13

---

B.3 Proof of Proposition
Proof. For simplicity, we only consider the case when p S p. since the other case follows exactly similarly, Applying the result of Lemma 2, we obtain
wd BREG (REG_>(P.)) S (6 (
G (01D- -ali-c((----
1² 1²
G 2 p)
2
The case when p I p follows similarly. Applying the result Proposition 1, taking a supremum over 8 E La, and bounding Cal2, PCalz in terms of KLCal, PKL completes the proof.
C
Deferred proofs in Section 4
C.1 Proof of Theorem
Theorem (Von-Neumann's Minimax Theorem). Let M E RRex for r, E Then,
min max p Mq max min p Mq. qEA,
q.A, PEA,
Proof of Theorem I. We prove stronger statement that the result holds against any adaptive adver- sary. In the forecasting setup, let H = (P--1 U (..,.... ... 1/-11 denote the history till time (exclusive). With complete knowledge about the forecaster's algorithm, adaptive adversary chooses yt depending on H;-1- As mentioned in Section 4, we shall consider forecasters that make predictions which belong to the discretization
Ti 2K
Z = 2K-1,, where sin
and K E N is constant to be specified later. For convinience, we set 2g 0, however, 20: žK are not included the discretization. In Lemma 6, we prove some important facts regarding Z which shall be useful for the subsequent analysis. For deterministic forecaster, is obtained via a mapping Ft-1: : H + Z. Similarly, for a deterministic adversary, Yr obtained via a mapping A-1 H4-1 -> {0, 1}. Therefore, deterministic forecaster can be represented by the sequence of mappings F (F=
(F1...., Fr), and deterministic adversary can be represented by the sequence Given F, A, we let SReg' (F, F, A) denote the swap regret achieved by executing
= F.A.
Let (F') {A} be all possible enumerations of F, A respectively, and ((FF)) (([A) denote the set of all distributions over (F), {4). Then, ()FF)) 2 A({A) distributions over (F), {A} and represent a randomized forecaster, adversary respectively. Note that [FH |{4)] < oc, since the domain and range of each map F,, A, is finite. Therefore, by Theorem 3, we have
min max EF-S.A-a(SRee (F, BEA((F) (EA((A))
max min GF~a.Ana((RRe (F, (EA((A))
For a R, to upper bound the quantity on the right hand side of (3) by u. is sufficient to prove that for any randomized adversary there exists forecaster F that guarantees that E[SReg' (F, S Moreover, swapping the adversary and forecaster allows the forecaster to witness the distribution of yt before deciding pt. Towards this end, we consider a forecaster F which at time does the following: (a) it computes P.: = E.(y:): : (b) predicts p: = argmin sez 15: 2/-
For each i E (1...., ...,,K 1} and n E [T]. let (n) = Σn= Upp = 2/. For convinience, we refer to (T())) n,. Fix ai E KK- 1), and define the sequence X Xr, a follows:
X,, = 0
if > nis
Vt, Pe,
if
S ni.
Here denotes the j-th time instant when the prediction made is pt Observe that the sequence X1......; XT,+ : a martingale difference sequence with X,,1 S for all j E (T). the subsequent steps obtain high probability bound on prefix sums of this sequence.
14

---

Fix E ( E [0, 1], E [0, 1]. Applying Lemma 8, we obtain that the following inequality holds with probability at least 8:
j S (V)(n)) + log 2 8 Vi(n) = n2, 2;) +
where (n(n) 1j=1 ( Pt, (1 - ( To uniformly bound (1(n) in terms of n, we consider the
cases n2 S n; and n > n,. When n S n4, (n) can be bounded terms of 2, as follows
(pe, (1 -Pt,) - -2,(1- - 2;))
j=1
= =n,,(1 zz) +
(Dts z1)
Di, - =z,)
S (1 21)
Pty
2z
In n 2:(1 - 2,) + 2K
π
where the last inequality follows from Lemma 6. When n > n4, we note that Vi(n) = vi(n,) S n (zi(1 - 2:) + x since n > n4.. Therefore, with probability at least we have
a Σ
1
2 8
X3s
S pm (2((1 2x) 2K
log
/
Minimizing the bound above with respect to μ E [0, 1J. we obtain
2 (z - 2;) +
log 3
if 2
log 2
X
I
2k
27 -11-5]+
n
[2 2;) +
2k
z + log otherwise.
Note that when n The bounds obtained for both cases can be combined into the following single bound:
log
we can simply bound n (1-(1-;))
2 log o < 2 log 3.
+11-2)++
n
2
max (v((a((-2)) 21)
X S 2
log
log
2K
which holds with probability least 1 5. Taking a union bound, we obtain that Σj= Xj s
2 logo max (Vr (z,(1 - 2x) + 2k ) log 2 8)
holds simultaneously for all E [K - 1]. n E [T]
with probability at least (K 1)78 > - K78. In particular, setting n = T4y we obtain that
2
max (/n(2tt (z((1 2:)
2
N j.
2 log
log
2K
holds for all E [K following steps we obtain high probabilty bound on SReg' (F, A). This shall be used to bound E[SReg' (FFSReg"(F,A (F) eventually.
- 1] with probability at least
K8T. Equipped with this bound, in the
15

---

We begin by bounding the quantity |24 Pel. which shall be used to obtain the high probability bound on SReg' ( (F,, A). We proceed
2 Pal
Σ
1pp
21( -3e)
n4
1=1
Tp =1(6E wi)
U[p
21((zs Di)
+
Σ
1
n4
max d(41)
5.8
n2
f=1
where for each i [K], define di == 24 24-1. The first inequality above follows from the
Triangle inequality; the second inequality is because, Pt = 24, we must have Pr E [z0, 21
i = 1, Pr E +-1 2c+8++1
2 if - S K 2, and Pr E [=x-2t=--
if K -1 1,
therefore, 1ife Pal & max(di, di+1). For each i E IK - 1], let li == 20 -1-=z 2x
log 3
Next, we write
SReg' (F, A) as
SReg' (Reg((F,A) = Σ (n:K(pp: Σ ni (p).
Term
Term
where I= E [K - 1];n,
tt}. and bound Term I. II individually. We begin by bounding Term
II in the following manner:
Term II Σ
iE7
(pi
(pi - 2i)²
(p: - 2;)²
Σ
2j
1 24
ieī
ne(pi - 2
Σ
21 - 2;)
1E7
2n4
1
1
x1x)
n
(max(di, di+1))²
2j (1 zi)
Tli
1E2
Σ 2n
(max di+1))?
+ 18loog
2
2/ 23) + 11)
24
21)
8
2K
iET
T K2
K 10gg 11)
+
where the first incquality follows since KL(pi, 2)) < (² z;); the second inequality follows from the bound on |z - pi| established above, and since (b² I 2a² 26²; the third inequality follows
from (4); the final equality follows from Lemma 6, particularly, we use the bounds (d::)dd
O 1 and EK- K-1 2 that
2((1-2.) O(K2). To bound Term I, we first note from the proof of Proposition
T
(L 2)=
sup o: 1=1
Σ
1 Upt = =I[p,, vn) E(o(pp), vt)) S n4 log
sin"
2K
where the last inequality is because for the rounds where Pt = Zi, we have
.log 1 ) < max
1
E(pt vr) S max
(log 2; 21
loo
x log
Olog K).
sin?
cos? 2K
2K
(5)
16

---

Moreover, repeating the exact same steps done to bound Term II above, we can also bound (, 2;) as
)
2
n,KL(ps,2)) 21)
2n; 2
(max(dd, d)-1))
1
Σ X3,
2))
74
2
n4
=
R
+ 8
log 8
n;2; 22)
14
1
=
+
log
K²
n,2; 2;)
where the first equality follows from Lemma 6 and (4). Taking minimum of the bounds obtained above, we obtain
min
n. log K,
ni +
[log
1 n1
2
1
X2
- -z))
T4. K2
m:log K, (1ogs 1
2
1
=0
+ min
n1zi(1
- 2z)
=0
T4 K2
+ Vlog K log
1
1
v /1 - 21)
where the final inequality follows since for fixed 0, min(æ, Summing over i E I, we obtain the following bound on Term
g) Va holds for all IR.
Term I O
Σn n.
Vlog K log
Σ iEZ 21 23)
T
K K(log K) log ;)
K2
K2
SEI
where the last equality follows from Lemma 6, particularly, Summarizing, we have shown that
EKI
O(K log K).
Vz((1-25)
T + K(log K)$ log 4) Term II -I=00 = (
T
K log 1
Term o
K2
hold simultaneously with probability at least KT8. Therefore,
T
SReg' (F, =
CReg((F,A))
+ K K(log K) log
(6)
K
with probability least 1 - K78. To bound E[SReg (F) we let E be the event in (6). Therefore,
E[SReg' (F, AA]] E[SReg ()]A) P(E) + E[SReg' (F, A) P(E)
0
T
K(log K) 1 log g
1
+ (K log K) K)r28
K2
T
o
((log K) 8 Tog T + log K
K2
OT3 (log 8).
where the second equality follows by using the high probability bound on SReg' (F, A) obtained
in (6), and bounding E[SReg (F, A) = OT log K), which follows from (5); the third equality
follows by choosing + the final equality follows by choosing = r the proof.
This completes
(log T)
Lemma Fix a & N. Let { be a sequence where 20 1, 1, sin? J for
I.... K- and zg 1. For each i 1,... K, define d: == 2;-1. Then, the following holds:
(a) d, < 2K for all E [K]; (b) (ax))d O R ; (c) ΣKT -[| = OKK2); and (d)
=1(1))))
K-1
O(K K log K).
[=[1==)]
17

---

Proof. By direct computation, we have Ti T(i -1
2-21111 sin2 sin
COS
x(1-1) K
COS
31 K.
sin
π
sin
π
1
2K
2K
2K
K
2
where the second equality follows from the identity sin 0 nos while the last equality follows
from the identity cos cos B = 2 sin a+9 sin 8-a Since sin 0 < A for all @ E R, and bounding
sin < 1, we obtain 24 - 2i-1 5 2k which completes the proof for the first part the lemma.
2
For the second part, we note that
max (d, d;-1)
max (di, dit1)
max (d;, di+1)
4
2 2.)
sin 2K
cos?
m1 2K
sin? X3 K
where the second equality follows from the identity sin 24 = 2 sin O cos 0. follows from (7) that
max(d;, d++1) - sin π 2K
π i K
2 sin
π i (1+2
max sin
K
For simplicity, we assume that K is odd, although a similar treatment can be done for even K, Let 1 I K-1 Then, max(d,, d++1) sin x sin x (i 2)). Observe that 2
sin K (i + 4))
sin K sin
cos A M1 K
sin 2K
sin 2K
C08
+ col.
sin
S
sin
11 K
2K
2K
sin
x K
where the first equality follows from the identity sin(a 3) sin cos B + cos sin B, while the K-1 inequality follows by noting that cot मi & cot for all 1 S $ 2 Finally, since sin x sin
-1), we obtain (dr,d)a)) (sinn 2k 0 n2 ). Next, we consider the case when K+1 <
0os 2
2;(1-a) Then, max(d;, d(+1) = 2
sin (x (i 1)) Repeating similar
analysis as before, we obtain
sin (1 (1) sin
sin 2K
sin 2K sin
2K
C08
cot sin 2K S
sin 32
sin mi
2K
K
which (1) as claimed earlier. Therefore, max (d. completes the proof of (b) above.
0 (Z)) Combining both the cases
2.(1-2))
For (c), similar to (b), we assume for simplicity that K is odd. Then,
K
K-1
Σ
=4
Σ
=8
2
2;)
sin
sin
K
and the summation
can be bounded in the following manner:
sin
K-1
du
sin
K
sim
K
sin
SM K
du
sin
K
sin
XU K
1
K
1
du
sin
K
R
sin
2
1
K
col
O(K2).
sin
K
K
18

---

This completes the proof for (c). Repeating the exact same steps as (c) proves (d). We include the full proof for completeness. Observe that
K-1
K-1 Σ
K-1
1
2
z
2i
and the summation
Σ
can be bounded in the following manner:
sin
zz
K
1
dv
dv.
sin
sin
K
TV sin
K
sin K
sin
T R
sim
π
sin
The integral above evaluates to log (esc
R + cot x)
Therefore, have that
K-1
π
K
π + cot す)
2)
4
+
log esc
O(K log K).
24)
K
K
This completes the proof.
C.2 Proof of Corollary
Proof. Let A be the algorithm guaranteed by Theorem 1. By Pinsker's 's inequality, we get that A guarantees [[[aa2]] = O (log T). Moreover, since Cal S VT Caly (Kleinberg et al., 2023, have E[[alı] s /T-EE(alz) E|Calz] (Kleinberg et al., 2023, Theorem 12) states that for any proper loss f, we have SReg < 4Cah. Therefore, E[SReg"] s 4IE[Cali] = OTT (log T) Combining this with the result of Proposition 2, completes the proof.
Lemma 13), by Jensen's 's inequality
O(T (log (logT) T) Next,
D Deferred proofs and discussion in Section 5
D.1
Computational cost of Algorithm
The cost of Algorithm at every time step is at most O (K2 INT + INT ST), where ST is the time required to compute the stationary distribution of Q₂ and INT denotes the computation required for evaluating the integral
in line 3 of Algorithm 3; the O(K3) cost is incurred in forming the matrix Qt, and all other operations in Algorithm 1 can be carried out in time that is no worse than O(K2). For ST, the stationary distribution of Q: can be computed by the method of power iteration; notably, each iteration shall incur cost O(nnz( Q:)). where nnz (Q:) represents the number of non-zero entries in Q.. Since each column of Q2 has at most two non-zero entries (Algorithm 4 randomizes over two adjacent points in the discretization), nnz(Q,) = O(K). For INT, the integral is over [0, 1] and has a closed-form expression in terms the gamma function T(=) = fo exp(-t))==- di as derived below. Recall that
La wwe,s Jo #t.s(w)dde
fr,(w) pr,e(w., y+) -Pr,i (B/ log (1 8r log(1 - w))
log (w (w-P-sss (1 w) -Pra(l---))
Therefore, (w) = exp (- - fri(ww) -2 v... - w) wi Pr.(11ppp (1-),,, For conve-
nience, let == 1-1 VTPr.i; 8 == Σ1=1 Pr.i(1 (1 wr). Then, fo (w) = So w (1- (w)ddn dw 1,5 B(> + 1, + 1), where B(21,2)) denotes the beta function, defined B(2 22) So t-1 (11
[(a2) for all 21, 22 with 21, 22 > O, have t) dt. Since B(21, 22) r(s)+*))
L. (es(w)) = T( + ()T(6+1)
1
19

---

Similarly,
L. woped(w)dw = L'' w
uu = B(y +2, = + +11
w (1
I' +(7+6+3 6+
Taking ratio of the two integrals above and using the identity 11) = (2), which holds for all with > we obtain
So wpe,(w)dw So Me,
I(r + 1 7+1 (17+1) +6++6+3) 7 0
= (1 8 =+1)
7+1
Clearly, at each time f, both 7 and 8 can be computed in (1) time using the previously memorized values corresponding to time & 1. Therefore, INT O(1). Since K = Ô(T the overall computation cost over T rounds is Ö(T T
D.2 Expected loss of common rounding schemes
We recall the discussion in Section 5: at each time I, EWOO; outputs W4,i [0, 1], however, A, required to predict a distribution qt E K++ over 2. Thus, we need to perform a rounding operation that projects the output W4,; of EWOO; show that the following two known rounding schemes: (a) rounding Wr,i to the nearest E and setting qt i the corresponding one-hot vector; (b) the rounding procedure proposed by Fishelson et al. (2025), cannot be applied to our setting since they incur a Q(11) change in the expected loss (gr,s E,) f(we,s Vt), which is not sufficient to achieve the desired regret guarantee.
distribution over 2. In the remark below,
Remark 1. Let y, = and Wt,; = 2 20 The rounding procedure in (a) above ensures that qt.i = eo with probability one. Therefore, (qr, Li) E(wr,i: yt) = E(20, 1) - e (#0++1 11) log 20 20- 250
Observe that En siu" z
4 cos?
TK 2 + 2 cos x_ Therefore, (gr, la) f(wr, Ve.
sim 5K
2K'
log ( + cos x 2()1). For the chosen example, the rounding procedure (b) sets (0,
(1) = Thus, (gi,s, Es) f(wi,, ((o.1)) e( #0 ,1 log 2
#0
144 cos = 2(1).
log
4k
D.3 Proof of Lemma 5
Proof. Since the log loss E(p,v) v) is convex in p (for any E {0, 1}), we have
Elg. - {(p,v) < (g (g p) (g y) P)
-
if = 1,
1-2
(8)
q(1 9)
yf
Let = 1. Taking expectation on both sides of (8), we obtain E[f(g, w)1 - C(p, v) = 2
To simplify the expressions involved in the computation of IE By direct computation, we have
we define the normalizing factor
P--P D
P-P P1
(1-p))
1 (pt---)(1-)) E D (1-pp) p - D p1p
p P-
P P-p
Similarly, by direct computation, we obtain
p+ +
p P-P-
(xt - p-+-p-) (y +
-
p+(1-pt)
(1-1-p-
p p - )( (1
Therefore,
P
p(1 p)
p p pt p(p + pt) S (p--p-)
(p - - )
E
- 1
P p pt
ppp pt)
p p p(p + p+)
20

---

Next, we let y 0. Taking expectation on both sides of (8), we obtain Ejé(g, v)] E(p,3) = Direct computation yields
1, thus, we require to bound E
pt p
p-p p- -11-p' p-ppppp0 )1 (1--)))))))))) D P p -1p--p111 p+t)
1 p(p - -p
E
q D
Substituting the expression for D obtained above, we obtain
1 -
p11-p1 - p)
(0+ p)(p p-)
E
- -1
1 1-9. p+p pppp + +pt)
P+P D+pp"* pt p(p + +p*)
(pt - pp
p+pP"* p(p + p+)
Let f(p) p p(p + +pt), Since f(p) is linear in p. for any E Ip- ,pt), we have
min(f(p min )) S f(v) S max(f(p f(x))) )). Since f(p = p (1 p f p" (1
pt). we obtain
min (p (1- --,,p"),p- p²)) S <ptp p - p(p + ) s max (p (p - p>), p- (1 -++)
for all p E ,p)t Therefore,
Eg v) - {(p v) S (pt -pp-ppp p- max (- p (1 p²)) =0 1
K2
where the last equality follows from Lemma This completes the proof.
Lemma Fix E N. Let {ai) o be a sequence where 2u sin 2 sin
(2 for
i E [K - 1), and žк = cos? a. аK. For each i I,..., K, define di 2, 21-1. Then, the following &
holds true for all E [K]: (a) =01=1) O (xTz). and (b) 21-1(1=2-11)
&
(x²z
Proof. It follows from Lemma 6 that (a), (b) hold for all 2 s i
K 1. For = 1, since
dj S 21 sin I.. we have
dc
sin
2K
tan 2 π
21
21)
cos
2K'
2K
2K
which is ( for a large K. Similarly, for = K, di sin² 2K Therefore,
cos2
coS
sin
sin
x
S
KK
2K
JK
1
d
sin
2K
ssin π
π
2x( (1 2K)
sin
cos
2K
K
1K
1K
where the equality follows from the identity sin 20 2 sin O cos 0. This completes the proof for (a). For (b), when = 1, we have
dc
sin
2K
= 4sin π
<
π
2u 1 20)
sin
cos
2K
K2
1K
Similarly, when i = K, we have
1 sin
K
2K
tan
2K (1
zK-1)
I sin
cos
2K'
ZK
TK
which is (x+))) for large K. This completes the proof.
21

---

D.4 Proof of Corollary 2
Proof. Since KLCal 2 PCalg, Algorithm 1 ensures that PCal2 = O (log (logT)3). Next, we show that the PCal satisfies (a) PCal, vT PCalz; (b) for any proper loss we have PSReg' 4PCal- The proof is exactly similar to the corresponding variants of (a), (b) above for Cal as shown by Kleinberg al. (2023). For (a), applying the Cauchy-Schwartz inequality, obtain
T ΣΣ Po(p) PEZ ==1
P ΣΣ Pa(p) (p p- ك pE2
ΣΣ PEZ t=1
P.(p)(p - 80)2 VT PCal2.
Towards showing (b), we first rewrite PSReg' = =EpEz E Pe(p) -(Pp..)) which holds for any proper loss as per Proposition 2. Next, we observe that
BREG_ E(p) - ((pp) + aE(D)(Ap - p) - 0l())) - Pp) + 0e(p)( - -p)
S 4 p ppl:
where the first inequality follows since {(p) is concave; the second inequality follows by noting
that {pp 1) - E(p. 0) = dp(p) as per Lemma 1, and since ((p. v) E 1), we have [a((p) s
for all p [0, 1]. Substituting the bound on BREG_+(0p..) p) obtained above into PSReg'.
obtain PSReg" f < 4PCal as desired. Since Algorithm ensures PCal, O (log T) $), we
obtain PSReg = O(T's ()og)))). Combining the above results with Propositions 2, 3 finishes the proof.
E
High probability bound for maximum swap regret against LG
While we do not have a concrete algorithm for KLCal, in this section, we show that if we only consider La, then our Algorithm 1 or the algorithm of Fishelson et al. (2025) already achieves O(G - 7 (log - 3/4 log & high probability bound for Msr To obtain so, we first prove generic high probability bound that relates Calp with PCalg. Subsequently, we instantiate our bound with an explicit algorithm for minimizing PCalz and use the result of Proposition 3. Our high probability bound Theorem 4 independent of the choice of the discretization
Theorem 4. For any algorithm Acat. with probability at least 1 over the randomness in Acal predictions PI.....PT. Pr, we have Calz S. 6PCal2 + 96 |Z| log 4|2]
Our proof of Theorem 4 crucially relies on the following version of Freedman's 's incquality from Beygelzimer et al. (2011). Refer therein for a proof.
Lemma 8. Let Xi...., Xn be martingale difference sequence adapted to the filtration Fi C C Fri where [X,l S B for all i = ,....,,, n, and B is a fixed constant. Define V == >'= |EX [-1]] 1 Then, for any fixed μ E [0, B ,88 [0, 1). with probability at least 8, we have
n
log 2
X <
1
Proof of Theorem 4. Before discussing the proof, introduce some notation. Let 2 be enumerated as Z = {Zo..... 2x} where K = |z| 1. Observe that at time t, Aça can be equivalently described
by the following procedure: (a) it samples i, from the set (0,..., K) with Pr(i, 1) Pi (z,). which we write as Pt, for convenience; (b) forecasts pt Zi,- Clearly, Tpp = 23] = T(ú = a). For
simplicity, denote Pz: = Pi and ~= فü: Under this notation, Pi, Pi be expressed as
ΣJ De = P: 1i
Σr= M.Pr. p:
Σt= Pt,i
We begin by bounding 1p: - A,| using Lemma Fix a E {0..... ; K} and define the martingale
difference sequences X, == yr (Pr. -l/i; il) and Y, = P,, ll i]. Observe that Xx] <
22

---

1. < 1 for all f. Fix 44 E [0, Applying Lemma 8 to the sequences X, Y and taking union
bound (over x, Y), we obtain that with probability at least 6,
log 1 8
log
Σ (Pr, Ili =1) s <uVx
+
E Mii = o) s Sily
(9)
P4
Mx
where Vx, Vy are given by
T
T
Vx = Σ
E [x
= Σ
Vt - .., (r.,(1, -Pr,)) -
and
t=1
1=1
1=1
T
T
T
Vy = Σ
E
[x2
Fr1) = Σ
P Pr.11-Ppp -Pt)) S Σ Po.s
t=1
t=1
The upper tail P: P: can then be bounded in the following manner:
T 11 Ve = i] Σ 11 PeP
Pi A.
Ei= Tie = i]
Et=1 Pt,i
N: E Pi,i + log 2
E 21=1 II =1]
1 veTlie =1]
14
1 T(i =]
EE= Pe,i
Σt y/ lix =i] i]
T
11 ΣT -1=1 Pe,s +
log 8
Σ Pas - -Tii =11]
+
r=1 L|ib :1)
(Ii=1) Prit)
Σ Pe,e
Σt=1 yr i]
T
log 2
14 11=1 Pcçi +
4
14 >
Pe,i
+
-= Tli: :1)
EEi= Pt.s)
bii
Σイ Pa.
[=1
2 log?? 4
S 244 +
Pi Σi= Pr.i"
where the first and second inequalities follow from (9), while the last inequality follows by bounding 11 = i] s Tl i). The lower tail can be bounded in an exact same manner
Σt Per
Σt= Vellie = i] ΣT Tle = i)
6: 5--P. Ps =
Σ Pe.j
T
ΣL Bellli
i| + 14 Σt Pes +
log
1= Tie = i]
14
Σt= Pt.i
Σt=1 llis =
Et=1 ye Ti: =1]
T
H4 ΣT= Pe.s +
log 3.
Σ
T/e = 1 - -Pr.6) +
14
r=l Pr.s) (>"" L16e =il)
Σ1= Pr.j
1=1
ΣØ V/, =
T Pt, +
log 4
14 Σr_ Prçi +
log 4
<
[4
1/.
Σ T
ΣTh lli = il)
EEmn Pes))
Σ1 Pe.i
t=1
2 2oog 1
< 2/4 +
Mi Σt= Pe.s
Combining both the bounds, we have shown that for a fixed μu; E [0, 1]. lp; - -pol S 2p, + 2log
> Pe.
holds with probability at least 1 - 6. Taking union bound over all i, with probability 1-6, 8, we have
23

---

(simultaneously for all 8)
log 4(K+1)
Σ Ye (Pt, li = -))
S F4
Pt,e
14i
T
T
log 1(K+1)
Σ Pui - I1(e =
$ 14
Pt.e
(10)
14i
2 2log 4(K+1)
P: - مo - 2/45 +
(11)
14 Σ Pt.
Consider the function g(v) == p f. where 2 0 is a fixed constant. Clearly, min ((4)
2/ when I 1, and + otherwise. Minimizing the bound in (11) with respect μá, obtain
log +1++1
4(K + 1)
T
lps Pi 4
when log
Pr..
1=1 P.s
1=1
However, when log 4(K+1) 5
Σ Pr.i. we obtain that |A: - A. <
2 20g 111
Σ P.. In particular,
when Σ Pe.i tiny, which is possible Acal does not allocate enough probability mass the index i, the bound obtained is large making it much worse than the trivial bound lop i. s 1 which follows since Ps, 0= E [0, 1] by definition. Based on this reasoning, we define the
4(K 1
I= i E (O..... Kjstt. s.t. (O.....K.........
log 5
<
Peo
(12)
tm
and bound (p: -p:²² as
16log 4(K+1)
ifi E I, otherwise.
(p: Pi) 1
Eim Pe.
(13)
Similarly, ΣT Pe, lis = i1 can be bounded by substituting the optimal μ obtained above in (10); we obtain
2 log 4(K+1) Σt Pa. i EE Pr,s + log 4(K+1)
Σ
Pi,
T(i, = <
(14)
otherwise.
1=1
Equipped with (13), (14), we proceed to bound Caly the following manner:
Caly Σ
The (2 --)pppp))))) < lhe i ((4- (p)² + (p. -pi-))))).
1=0 1=1
t=1
where the inequality is because (a + b)2 < 2a² + 262 for all a, b E R. To further bound the term above, we split the summation into two terms Ti, Tz defined as
T =
li = i| ( 1 7:)2 + (p. -b:)2)
İET t=1
Ta
Σ
Σ
lli ( (z)-p.3 2 (ps p.)2).
iET
24

---

and bound Ti and T2 individually. We bound Ti
4(K + 1)
T
16 log 4(K+1)
Ti
Σ Pt. + +2 log
Σ Pr.
(2i -i)²
Σイ Pr.i
IEI
T
4(K 1)
Σ
Σ
Pes (zs - -p:)² + log
[ +
8
1EZ 1=1
4(K + 1)
16 16log 4(K+1)
log
(2-pa) +
Σ P7.
4(K +1
T
16 lolo 4(K+1)
Peς (2 -p:) + 16loog
I + 2
P Pr
(a--p))
8
Σ Pr.i
iET 1=1
VET ==1
4(K + 1)
3 iEZ
Σ Pa.s (z - px)² + 48448lgg log
where the first inequality follows by substituting the bounds from (13), (14), while the final inequality
follows since by the definition of I in (12), we have v log 4(+1) Σ Pr. ET= Pr.. Next, we bound To as
4(K 11)
)
T2 S
Σ
2
Pes log
pi) +11+11)
1ET
4(K + 1)
2
Pa.s (2 p.)² + Σ Σ
Pe.s + 2 21og
16I t=1
iEI t=1
4(K + 1)
2 2 Σ
Σ
Pi. (z+ - 0.)² + log 8
7
ieī t=1
where the first incquality follows by substituting the bounds from (13), (14); the second inequality follows by bounding (z: 02)² < 1; the final inequality follows from the definition of I (12). Collecting the bounds on Ti and T2, we obtain
K T
4(K 1)
4(K + 1)
Ti + T
Pas (=a Di) + 48 log
[Z] + 4 log
[
5
4(K + 1)
3PCalp + 48(K + 1) log
8
where the last inequality follows from the definition of PCalz and since [Z] + [ = K + 1. Since Cal2 S 2TT T2). we have shown that
Cal2 S 6PCalp + 96(K + log 4(K +
(15)
5
with probability at least 8. This completes the proof.
Instantiating Acal in Theorem 4, we obtain the following corollary.
Corollary 3. On choosing K (T/ log 3 Algorithm 1 ensures that with probability at least 1- over its internal randomness
T (log - log TT) Cal2 0 (Tà
Msrce O (.. (T.TTs(00p - log T)
Furthermore, |[[Clg] 3 (logT) M| = O T (log 3)3).
25

---

Proof. Since Algorithm ensures that PCal2 = = =O( + K log (refer Section 5), we obtain
T
+ K log K 8
Cal2 =0
K logg
R2
T
with probability at least 1 8, which is (1)
log - on substituting K. The high probability
bound on cs follows since Cs
G- Calg. To bound IE [Cal2], we let & denote the that
Cal2 v A, where A = 6PCal2 + 96( K + 1) log 4(K+1) We then have,
[|[al2] = [[Cal2| IP(E) E[Cal] 8] P())(())))))) o
- T K2 K
K K log + 8 T
which is O(T's (log 3) on substituting à = + and K. Note that the second equality above follows
since E(Caly] E] < A and P(E) < 1, Cal2 - T and P(E) < 6. Finally, bounding Msrco S G Cala finishes the proof.
Instantiating Acal with the algorithm of Fishelson et al. (2025), we also obtain the exact same guarantee as Corollary Compared to Algorithm 1, the algorithm Fishelson al. (2025) is more efficient since it uses scaled online gradient descent for the i-th external regret algorithm, which is more efficient than EWOO, On the contrary, it does not posses the generality of Algorithm towards minimizing SReg for all E C2 simultancously.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All relevant details related to claims made in the abstract and introduction either provided the main body or the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Refer Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 sell-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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
27

---

Assumptions are written in the main body and proofs are deferred to the appendix.
Justification:
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 or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
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 of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper is theory work and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 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 NeurIPS 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 it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be 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 deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
28

---

Answer: [NA]
Justification:
The paper is a theory work and 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.. cc/ Stapcc/guides//oodeeee
wwwissssssoolllioeeeooe poliiyy)yy 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.o wttpccccpppccceeeeccec.cccccccct wwwiic/ggg////eeeee /CodeSubmiia
seniibiisssii sesiiissinnne oniioniyl / 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 is a theory work and 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is a theory work and 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.
29

---

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 is a theory work and does not include experiments.
Guidelines:
The answer NA means that the paper does 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 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: : http//eeripp..///
Answer: [Yes]
Justification:
The research abides in every respect with the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theory work and there is no immediate 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.
30

---

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 of 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 is theory work and 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 is theory work and 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 of 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.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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 is theory work and does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the datasettcooeemmodll 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 is a theory work and 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 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 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 pape a theory work and 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 on 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
32

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper is theory work and the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : /ttp//eerpppp//e// ////C//ferencee/222////111 for what should or should be described.
33


Reviews:
[{"review_id": "oYIshzfrDi", "reviewer": "Reviewer_QAmB", "summary": "The paper concerns the problem of online calibration. Its central contribution is the introduction and analysis of (pseudo) KL-Calibration, defined as (pseudo) calibration with respect to the logarithmic loss. The authors prove $\\tilde{O}(T^{1/3})$ bounds on KL-Calibration and provide an explicit algorithm achieving the same rate for pseudo KL-Calibration. Subsequently, using a reduction scheme from KL divergence to other Bregman divergences, the authors extend these bounds to broader classes of losses, including bounded proper losses ($\\mathcal{L}$), twice continuously differentiable losses ($\\mathcal{L}_2$), and $G$-smooth losses ($\\mathcal{L}_G$).", "questions": "What's the total computational complexity of the algorithm proposed in Section 5, based on the BM reduction?\n\nYour algorithm requires knowledge of the time horizon $T$ to select an appropriate discretization level $K$. Is there a straightforward method (such as a doubling trick or similar approach) to avoid this requirement?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- A new concept of (pseudo) KL-Calibration, and proving its equivalence to minimizing (pseudo) swap regret with respect to the log loss.\n- Bounding the (pseudo) swap regret relative to any twice continuously differentiable bounded proper loss by the (pseudo) KL-Calibration\n- Similarly for any $G$-smooth loss, bounding the (pseudo) swap regret by the (pseudo) KL-Calibration with explicit constant $G$ in the bound.\n- Proving the existence of an algorithm achieving $\\tilde{O}(T^{1/3})$ KL-Calibration, along with providing an explicit algorithm achieving the same rate for pseudo KL-Calibration. The authors use an appropriate non-uniform discretization (resulting from the arcsin transform), ensuring that KL divergence values between neighboring discretization points are approximately uniform. This step seems crucial in controlling discretization error.\n- High probability bound for maximum swap regret against smooth losses\n\nOverall, I think the paper makes a significant contribution to the theory of online calibration. It generalizes previous results, particularly those of Fishelson et al. (2025), extending them to a broader class of loss functions, such as those induced by Tsallis entropy and the log loss (KL divergence). I think the main results, particularly the $\\tilde{O}(T^{1/3})$ bounds on (pseudo) swap regrets, represent state-of-the-art advancement. Although many of the findings build upon previous results, the proofs contain sufficient novelty and introduce non-standard techniques that add considerable value to the work. In particular, the authors introduce several interesting tools, such as a non-uniform discretization (used in the past, but in a different context) and novel rounding schemes, which both seem crucial for effectively handling the log loss.\n\nWeaknesses:\nThe only weakness that comes to my mind is that the paper is quite dense with mathematical content and technical detail, making it challenging to follow at times. It feels that without page-limit constraints, the presentation of these results could easily expand to twice the length.\n\nI am a bit uncomfortable with the notation (e.g. in line 31 at page 1, but repeated several times afterwards) $\\sum_{p \\in [0,1]}$, which looks like a sum over uncountably many elements. Is it really a standard notation from past work?", "was_revised": true, "final_justification": "All my questions were positively resolved by the authors' feedback. That is why I am glad to keep my original score (accept).", "rebuttal": "We sincerely thank the reviewer for their positive evaluation of the paper. Below, we provide responses to all your questions.\n\n> I am a bit uncomfortable with the notation (e.g. in line 31 at page 1, but repeated several times afterwards), which looks like a sum over uncountably many elements. Is it really a standard notation from past work?\n\nYes, it is a standard notation from past work. The summation over $p \\in [0, 1]$ is really just over the predictions $p_{1}, \\dots, p_{T}$, since the interaction between the forecaster and the adversary lasts for $T$ rounds.\n\n> What's the total computational complexity of the algorithm proposed in Section 5, based on the BM reduction?\n\nThe cost of the algorithm proposed in Section 5 at every time step is at most $\\mathcal{O}(K ^ {2} + \\text{INT} + \\text{ST})$, where $\\text{ST}$ is the time required to compute the stationary distribution of $Q_{t}$ (ref. Algorithm 3 in Appendix D) and $\\text{INT}$ denotes the computation required for evaluating the integral $\\frac{\\int_{0} ^ {1} w \\mu_{t, i}(w) dw}{\\int_{0} ^ {1} \\mu_{t, i}(w) dw}$ in line 3 of Algorithm 4 (Appendix D); the $\\mathcal{O}(K^{2})$ cost is incurred in forming the matrix $Q_{t}$, and all other operations in Algorithm 3 can be carried out in time that is no worse than $\\mathcal{O}(K^{2})$. For $\\text{ST}$, the stationary distribution of $Q_{t}$ can be computed by the method of power iteration; notably, each iteration shall incur cost $\\mathcal{O}(\\text{nnz}(Q_{t}))$, where $\\text{nnz}(Q_{t})$ represents the number of non-zero entries in $Q_{t}$. Since each column of $Q_{t}$ has at most two non-zero entries (Algorithm 2 randomizes over two adjacent points in the discretization), $\\text{nnz}(Q_{t}) = \\Theta(K)$. For $\\text{INT}$, the integral is over $[0, 1]$ and has a closed-form expression in terms of the gamma function $\\Gamma(z) \\coloneqq \\int_{0} ^ {1} \\exp(-t) t^{z - 1} dt$ as derived below. Recall that \\begin{align*}f_{\\tau, i}(w) = p_{\\tau, i} \\ell(w, y_{\\tau}) = -p_{\\tau, i} (y_{\\tau} \\log w + (1 - y_{\\tau}) \\log (1 - w)) = \\log (w ^ {-y_{\\tau} p_{\\tau, i}} (1 - w) ^ {-p_{\\tau, i} (1 - y_{\\tau})}).\\end{align*} \nTherefore, $\\mu_{t, i}(w) = \\exp\\left(-\\sum_{\\tau = 1} ^ {t - 1} f_{\\tau, i}(w)\\right) =  w^{\\sum_{\\tau = 1} ^ {t - 1} y_{\\tau} p_{\\tau, i}} (1 - w) ^ {\\sum_{\\tau = 1} ^ {t - 1} p_{\\tau, i} (1 - y_{\\tau})}$. For convenience, let $\\gamma \\coloneqq \\sum_{\\tau = 1} ^ {t - 1} y_{\\tau} p_{\\tau, i}, \\delta \\coloneqq \\sum_{\\tau = 1} ^ {t - 1} p_{\\tau, i} (1 - y_{\\tau})$. Then, \\begin{align*}\\int_{0} ^ {1} \\mu_{t, i} (w) dw = \\int_{0} ^ {1} w ^ {\\gamma} (1 - w) ^ {\\delta} dw = \\text{B}(\\gamma + 1, \\delta + 1),\\end{align*} where $\\text{B}(z_{1}, z_{2})$ denotes the beta function, defined as $\\text{B}(z_{1}, z_{2}) \\coloneqq \\int_{0} ^ {1} t ^ {z_{1} - 1} (1 - t) ^ {z_{2} - 1} dt$. Since $\\text{B}(z_{1}, z_{2}) = \\frac{\\Gamma(z_{1}) \\Gamma(z_{2})}{\\Gamma(z_{1} + z_{2})}$ for all $z_{1}, z_{2} > 0$, we have $$\\int_{0} ^ {1} \\mu_{t, i}(w) dw = \\frac{\\Gamma(\\gamma + 1) \\Gamma(\\delta + 1)}{\\Gamma(\\gamma + \\delta + 2)}.$$ Similarly, $$\\int_{0} ^ {1} w \\mu_{t, i}(w) dw = \\int_{0} ^ {1} w ^ {\\gamma + 1} (1 - w) ^ {\\delta} dw = \\text{B}(\\gamma + 2, \\delta + 1) = \\frac{\\Gamma(\\gamma + 2) \\Gamma(\\delta + 1)}{\\Gamma (\\gamma + \\delta + 3)}.$$ Taking ratio of the two integrals above and using the identity $\\Gamma(z + 1) = z \\Gamma (z)$, which holds for all $z > 0$, we obtain \\begin{align*}\n    \\frac{\\int_{0} ^ {1} w \\mu_{t, i}(w) dw}{\\int_{0} ^ {1} \\mu_{t, i}(w) dw} = \\frac{\\Gamma (\\gamma + 2)}{\\Gamma (\\gamma + 1)} \\cdot \\frac{\\Gamma (\\gamma + \\delta + 2)}{\\Gamma (\\gamma + \\delta + 3)} = \\frac{\\gamma + 1}{\\gamma + \\delta + 2} = \\left(1 + \\frac{\\delta + 1}{\\gamma + 1}\\right) ^ {-1}.\n\\end{align*}\nClearly, at each time $t$, both $\\gamma$ and $\\delta$ can be computed in $\\mathcal{O}(1)$ time using the previously memorized values corresponding to time $t - 1$. Therefore, $\\text{INT} = \\mathcal{O}(1)$. Since $K = \\tilde{\\Theta}(T^{\\frac{1}{3}})$, the overall computation cost over $T$ rounds is $\\tilde{\\mathcal{O}}(T^{\\frac{5}{3}} + T \\cdot \\text{ST})$.\n\nWe thank the reviewer for the question and shall update our manuscript accordingly to incorporate the above discussion.\n\n> Your algorithm requires knowledge of the time horizon to select an appropriate discretization level. Is there a straightforward method (such as a doubling trick or similar approach) to avoid this requirement?\n\nYes, the doubling trick can be utilized to avoid this requirement. Since KL-Calibration is equivalent to swap regret of the log loss, we can use the doubling trick to avoid the requirement of knowing the time horizon $T$. The analysis of doubling trick for swap regret is exactly identical to that for external regret.\n\nWe hope that our responses answer your questions. If you have any further questions, please do not hesitate to reach out."}, {"review_id": "UqdenFdBaX", "reviewer": "Reviewer_pP17", "summary": "Calibration measures provide means of quantifying the \"goodness\" of predictions. Typically, calibration is measured as some combination of squared/absolute bias across different level sets of one's predictions. This paper instead proposes to measure bias at each level set of a predictor using KL divergence, which they refer to as KL-calibration (and a variant that, in a sense, averages over the randomness from the sampling of the forecaster's predictions, which they refer to as pseudo KL-calibration).\n\nBecause this calibration measure is stronger than (upper bounds) l2 calibration, the measure is strong enough to provide swap regret guarantees for a broader class of proper losses including log loss; KL calibration ends up being exactly the worst-case swap-regret of log loss. In particular, because KL upper bounds the Bregman divergence of any twice differentiable proper loss, KL calibration also implies bounds on swap regret for every twice-differentiable proper loss.\n\nThe authors first follow the usual Hart's min-max theorem approach to showing the existence of a calibrated forecaster to prove a non-constructive rate for actual KL calibration. The authors claim the technical difficulty of the result is deciding how to discretize the action space of the forecaster (which we need for min-max); rather than using the usual uniform bins, the authors implement some sinusoidal grid. The resulting rate is of the order \\tilde O(T^{1/3}).\n\nFor an explicit forecasting algorithm for pseudo KL calibration, the paper follows the Blum-Mansour reduction using exponential weights and by using a randomized rounding scheme more suited for the non-smooth curvature of log losses. The resulting rate is of the order O(T^{1/3}).", "questions": "My impression of the paper is positive so I don't have any questions in particular for the authors, other than just generally the (mild) weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nI did not check the correctness of the proofs in the Appendix beyond reviewing the sketches in the main body. Nonetheless, the main technical insights seem to be a combination of the following facts 1) KL gives a natural worst-case bound on log loss and twice differentiable losses, 2) standard approaches to showing calibration rate existence and building swap regret algorithms can be adapted even to non-Lipschitz losses with more careful discretization/rounding. Both facts seem reasonable and 1 in particular is a nice observation that the authors give a nice treatment of in this paper.\n\nWeaknesses:\n\nI don't have many specific concerns/weaknesses with the paper, which I generally find to be a nice set of results. If I were to nitpick, I'd note that the paper is written for a very specific and therefore narrow audience of people who work on calibration. The paper—even just the first 68 lines—are not written to be very friendly to a more general audience (though I'm sure this is just an artifact of squeezing a COLT-size paper into the Neurips format).\n\nI think another thing is that for readers that haven't read the Fichelson et al 2025 paper to define pseudo-calibration more formally (specifically calP) and give a more gentle explanation for what intuition one should walk in with about why relaxing to pseudo-notions of calibration allows for the sqrt T - T^{ 1/3} gap (does the noise in realizing the forecasting's predictions in non-pseudo calibration cause one to naively pay some variance term of order sqrt T? why does such a variance term exist, especially if the forecaster only needs to randomized over two very close probabilities?).", "was_revised": true, "final_justification": "I enjoyed the paper and maintain my positive sentiment.", "rebuttal": "We sincerely thank the reviewer for their positive comments and time in evaluating our paper. In the subsequent revisions, we shall make sure to make the presentation of our paper more appealing to the general audience. Below, we answer the question that you raised in the weaknesses section.\n\n> I think another thing is that for readers that haven't read the Fishelson et al. (2025) paper to define pseudo-calibration more formally (specifically $\\text{PCal}$) and give a more gentle explanation for what intuition one should walk in with about why relaxing to pseudo-notions of calibration allows for the $\\sqrt{T}$ - $T^{1/3}$ gap (does the noise in realizing the forecasting's predictions in non-pseudo calibration cause one to naively pay some variance term of order $\\sqrt{T}$? Why does such a variance term exist, especially if the forecaster only needs to randomized over two very close probabilities?).}\n\nGreat question. As you correctly figured out, the intuition behind the improved bound in $\\text{PCal}_{2}$ is that by not taking into account the variance due to the randomness in the predictions, pseudo calibration is often easier to minimize. \n\nFor the other part of the question, the forecasting algorithm of Fishelson et al. or our Algorithm 3 (both of which achieve $\\text{Cal}_2 = \\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$) do not randomize over only two adjacent probabilities. Both the algorithms are based on the BM-reduction, which requires computing the stationary distribution of a matrix $Q_t$, i.e., $p_t \\in \\Delta(K + 1)$ such that $Q_t p_t = p_t$ (subsequently, the forecaster outputs conditional distribution $\\mathcal{P}_t$ with $\\mathcal{P}_t(z_i) = p_t(i)$); the columns of $Q_t$ correspond to the probability distributions output by the $K + 1$ external regret algorithms invoked by the BM-reduction. While each external regret algorithm outputs a probability distribution that is supported on two adjacent probabilities in the discretization ${\\mathcal{Z}}$, the stationary distribution $p_t$ need not necessarily be so. As shown in Fishelson et al. (or our Theorem 2), the resulting algorithm achieves $\\text{PCal}_2 = \\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$. Accounting for the variance in the predictions naively would incur a $\\sqrt{T}$ variance term. However, as we show in Appendix E (Theorem 4), by applying Freedman's inequality this variance term is of the order $\\tilde{\\mathcal{O}}(|\\mathcal{Z}|)$; particularly, we show that $\\text{Cal}_2 \\le 6\\text{PCal}_2 + 96 |\\mathcal{Z}| \\log \\frac{4|\\mathcal{Z}|}{\\delta}$ with probability at least $1 - \\delta$. Substituting $|\\mathcal{Z}| = \\tilde{\\Theta}(T^{\\frac{1}{3}})$, we obtain an improved $\\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ variance bound and $\\text{Cal}_2 = \\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$.\n\nIn summary, relaxing to pseudo calibration does enable achieving the $T^{\\frac{1}{3}}$ rate, however, as we show this does not lead to a $\\sqrt{T}-T^{\\frac{1}{3}}$ ($\\text{Cal}_2$ vs $\\text{PCal}_2$) gap, since the variance term can be carefully controlled by a sophisticated analysis.\n\n**PS**: In light of you mentioning randomization over two very close probabilities, that is certainly true for some calibration algorithms, e.g., the forecaster by Foster (1999), or the forecaster in the expository note by Roth (2022) (ref. Section 3.4 in Chapter 3). However, the former results in $\\text{Cal}_1 = \\tilde{\\mathcal{O}}(T^{\\frac{2}{3}})$ and the latter implies $\\text{Cal}_2 = \\tilde{\\mathcal{O}}(\\sqrt{T})$, both of which do not imply the desired ${T}^{\\frac{1}{3}}$ bound for $\\text{Cal}_2$.\n\nFoster, D. P. (1999). A proof of calibration via Blackwell's approachability theorem. Games and Economic Behavior, 29(1-2), 73-78.\n\nRoth, A. (2022). Uncertain: Modern topics in uncertainty estimation. Unpublished Lecture Notes, 11, 30-31.\n\nWe hope that our response answers your questions. Should you have any more questions, do not hesitate to reach out."}, {"review_id": "kBIkN1WNXN", "reviewer": "Reviewer_24mT", "summary": "This paper studies the problem of online calibrated prediction of Boolean outcomes. They consider (pseudo) KL-Calibration, which they show is equivalent to (pseudo) swap regret for log loss. They further show (pseudo) KL calibration implies (pseudo) L2 calibration and bounded (pseudo) swap regret for any bounded proper loss with a twice differentiable univariate form, as well as bounded swap regret for any proper loss with a G-smooth univariate form. Using their log loss swap regret characterization of KL-calibration, they give a non-constructive proof of the existence of an algorithm with expected KL Calibration error that is $O(T^{1/3}(\\log T)^{5/3})$, improving over recent pseudo L2 calibration error bounds by generalizing the class of losses to which the regret bound applies, as well as giving bounds (via non-constructive argument) for expected swap regret for the log loss (rather than pseudo swap regret).", "questions": "Please see comments above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper studies interesting and important questions about the notions of calibration for which efficient online prediction is feasible, and explores the relationship between several useful notions of (pseudo) swap regret and calibration. The paper makes good progress on these questions by, among other contributions, generalizing recent results to a much broader class of losses. \n\nThe paper is well-written and the new techniques used to obtain their results seem like a nice contribution as well. \n\nThe authors give some examples of losses to which their results apply, but as a reader, I think having some additional discussion of the sorts of problems that give rise to losses covered by their new results would great improve my ability to contextualize the contribution. Log loss and squared error are familiar, but spherical error not as much, and understanding what we can get from generalizing prior results beyond psuedo l2 calibration error to these other losses would be helpful. \nI’d also be interested in seeing some discussion of lower bounds for pseudo swap regret (if there’s anything of note in the literature to discuss).", "was_revised": true, "final_justification": "My appraisal of the paper is positive and I am keeping my score for the reasons given in the original review.", "rebuttal": "We sincerely thank the reviewer for their positive evaluation of the paper. We shall incorporate your suggestions in the subsequent revisions of our paper.\n\n> I think having some additional discussion of the sorts of problems that give rise to losses covered by their new results would great improve my ability to contextualize the contribution. Log loss and squared error are familiar, but spherical error not as much, and understanding what we can get from generalizing prior results beyond psuedo $\\ell_{2}$-calibration error to these other losses would be helpful.\n\nWe agree that the spherical loss $\\ell(p, y) = -\\frac{y p + (1 - y) (1 - p)}{\\sqrt{p ^ {2} + (1 - p) ^ {2}}}$ is less familiar than the log loss and the squared loss. However, it has been previously studied in the literature to evaluate the quality of predictions made by a forecaster (ref. Gneiting and Raftery). Furthermore, the spherical loss has a nice geometric interpretation in terms of a cosine similarity (specifically, $\\ell(p, y) = \\cos(\\pi - \\theta)$, where $\\theta$ is the angle between the vectors $[p, 1 - p]$ and $[y, 1 - y]$), therefore may be useful in problems where angular separation is meaningful. Similarly, other losses mentioned in our paper, e.g., losses induced by the Tsallis entropy have been previously studied in online learning and been used as regularizers in the classical Follow-the-Regularized Leader (FTRL) algorithm (ref. Abernethy et al.).\n\nGneiting, T. and Raftery, A. E. (2007). Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359–378.\n\nAbernethy, J. D., Lee, C., \\& Tewari, A. (2015). Fighting bandits with a new kind of smoothness. Advances in Neural Information Processing Systems, 28.\n\n> I’d also be interested in seeing some discussion of lower bounds for pseudo swap regret (if there’s anything of note in the literature to discuss).\n\nRegarding lower bounds, we would like to mention that the section on related work (line 109 onwards) does mention some lower bounds for $\\text{Cal}_1, \\text{Cal}_2$ (and thus swap regret of the squared loss). In summary, proving lower bounds for online calibration, swap regret is a significantly challenging problem and obtaining the minimax bound is still open, with recent breakthroughs establishing that $\\tilde{\\Omega}(T^{0.54389}) \\le \\mathbb{E}[\\text{Cal}_1] \\le \\tilde{\\mathcal{O}}(T^{\\frac{2}{3} - \\varepsilon})$ (for a sufficiently small $\\varepsilon > 0$) and $\\tilde{\\Omega}(T^{0.08778}) \\le \\mathbb{E}[\\text{Cal}_2] \\le \\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ (Dagan et al., Fishelson et al.).\n\nWe hope that our responses answer your questions. If you have any further questions, please don't hesitate to reach out."}, {"review_id": "UxSi0vZGbA", "reviewer": "Reviewer_vKYY", "summary": "This paper introduces a new notion of calibration based on KL divergence and shows that it is equivalent to swap regret for the log loss. The KL calibration error recovers recent results for the $\\ell_2$ calibration error as a special cases, and extends to a broader class of losses such as the log loss and Tsallis entropy.", "questions": "- The paper focuses on binary outcomes; is there any hope to extend the concept of KL Calibration to multiclass outcomes?\n- An oblivious adversary is assumed but it is claimed that the results generalize to an adaptive adversary. What needs to change in the analysis? Is it significantly more complicated, despite being technically possible?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\nThe paper does a lot of things in what feels like the \"right\" way; $\\ell_p$ calibration has always seemed weird to me because you're measuring distances between probabilities using an $\\ell_p$ norm. The KL Calibration instead measures using a KL divergence, which seems much more natural of a way to measure deviation from a comparator distribution. \n\nSimilarly, most calibration papers seem to discretize $[0,1]$ using a uniform strategy, whereas this work uses (essentially) the nodes of the Chebyshev polynomials, which get more dense near the boundaries, which again just seems like the \"right\" way to discretize $[0,1]$ in this setting. I found these two insights very satisfying. Both of these results involve non-trivial extensions to the existing approaches.\n\n# Weaknesses\n\nThe algorithm achieving KL Calibration is non-constructive, so only the existence is shown but no concrete algorithm is given (though the authors are upfront about this).\n\nMy biggest concern is that the writing is not easy to follow in general and feels quite \"drafty\". Many of the explanations in the main text are essentially proof sketches but with too many details to be helpful as a high-level overview---It sort of feels like it's simultaneously trying to fill space (too many low-level details in the proof sketches) while also trying to save space (cramming many bulky expressions inline).\n\nIn section 4, for example, in Step II it doesn't seem straight-forward how to bound $|z_i-\\rho|$ using the displayed math; is the reader supposed to be able to see the connection here? Or are we supposed to take it at face value for now and defer to the appendix for the specifics? The ambiguity about which details the reader is supposed to understand now vs in the appendix makes these sketches frustrating to read. \n\nSimilarly, in Step III I recognize all of the terms and can follow what's being said, but at the same time I couldn't summarize most of what it said right after reading it, so it's not really serving its intended purpose as a sketch of ideas or giving useful insights about the techniques.\n\nThe full explanations in the appendix, however, generally seemed quite clear to me, so I would be willing to trust that the authors could improve the writing quality between now and the camera-ready.\n\n**Typos etc**\n- 269: \"The bound above dictates separate consideration of $i\\in I$ and $i\\in I$\"", "was_revised": true, "final_justification": "It is an obviously very strong paper with strong results. The writing is a bit sloppy but I trust that it can be cleaned up sufficiently before the camera-ready.", "rebuttal": "We sincerely thank the reviewer for their positive comments and time in evaluating our paper. We shall carefully incorporate your writing suggestions in the subsequent revisions. Below, we provide responses to all your questions.\n\n> The paper focuses on binary outcomes; is there any hope to extend the concept of KL Calibration to multiclass outcomes?\n\nIt is not immediately trivial to extend the concept of KL-Calibration to multiclass outcomes, as we are not familiar with a generalization of the non-uniform discretization to the multiclass setting that still ensures desirable properties. Even more, we are not familiar with an extension of the randomizing rounding procedure for the log loss (utilized to obtain an explicit algorithm for minimizing pseudo KL-Calibration) to the multiclass setting. Moreover, a reason we did not seriously consider the possibility of such an extension to the multiclass setting is that several implications of KL-Calibration towards minimizing swap regret do not necessarily hold. In particular, in the binary setting, the implication $\\text{SReg}^\\ell = \\mathcal{O}(\\text{KCal})$ for each $\\ell \\in \\mathcal{L}_2 \\cup \\mathcal{L}_G$ is derived via Lemma 2, which states that for a proper loss $\\ell$, we have  $\\text{BREG}(\\hat{p}, p) =\\int_p^\\hat{p} |\\ell''(\\mu)| \\cdot (\\hat{p} - \\mu) d\\mu$;  the proof of the above result is based on a basis characterization of proper losses over binary outcomes in terms of V-shaped losses $\\ell_v(p, y) = (v - y) \\cdot \\text{sign}(p - v)$ --- for each proper loss $\\ell$, there exists a non-negative function (specific to $\\ell$) $\\mu: [0, 1] \\to [0, 1]$ satisfying $\\int_0 ^ 1 \\mu(v) dv \\le 2$ and $\\ell (p, y) = \\int_0^1 \\mu(v) \\ell_v (p, y) dv$ (ref. Theorem 8 in Kleinberg et al.). However, a similar characterization of proper losses is not known in the multiclass setting, and in fact cannot exist via the impossibility result in Theorem 20 in Kleinberg et al. \n\nKleinberg, B., Leme, R. P., Schneider, J., & Teng, Y. (2023, July). U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory (pp. 5143-5145). PMLR.\n\n> An oblivious adversary is assumed, but it is claimed that the results generalize to an adaptive adversary. What needs to change in the analysis? Is it significantly more complicated, despite being technically possible?\n\nThe only result for which the analysis becomes simpler with an oblivious adversary is the high probability bound $\\text{Cal}_2 \\le 6 \\text{PCal}_2 + 96 |\\mathcal{Z}| \\log \\frac{4 |\\mathcal{Z}|}{\\delta}$ (Theorem 4 in Appendix E); we use Theorem 4 to derive a high probability bound on the classical $\\ell_2$-Calibration ($\\text{Cal}_2$). Extending the above result for an adaptive adversary is simple, but requires a more involved application of Freedman's inequality, which is outlined below. All other results in our paper apply as is for an adaptive adversary.\n\nIn more detail, Freedman's inequality states that for a martingale difference sequence $X_1, \\dots, X_T$, where $|X_t| \\le B$ for all $t \\in [T]$, we have $|\\sum_{t = 1} ^ {T} X_t| \\le \\mu V_X + \\frac{1}{\\mu} \\log \\frac{2}{\\delta}$ with probability at least $1 - \\delta$, where $V_X = \\sum_{t = 1} ^ {T} \\mathbb{E}_t[X_t ^ {2}]$, $\\mu \\in [0, \\frac{1}{B}]$ is a fixed constant, and $\\delta \\in (0, 1)$. When $V_X$ is a deterministic quantity, the upper bound in the display above can be minimized with respect to $\\mu \\in [0, \\frac{1}{B}]$; the optimal $\\mu^\\star = \\min\\left(\\frac{1}{B}, \\sqrt{\\frac{\\log \\frac{2}{\\delta}}{V_X}}\\right)$.  For the considered martingale difference sequences in Theorem 4 (e.g., one such sequence is $X_t \\coloneqq y_t(\\mathcal{P}_t(i) - \\mathbb{I}[i_t = i]$), the corresponding $V_X$ is deterministic since the adversary is oblivious (note also that our algorithm outputs $\\mathcal{P}_t$ in a deterministic manner). However, when $V_X$ is random (which is indeed the case in Lemma 9), we cannot merely substitute $\\mu^\\star$ in the bound above since $\\mu^\\star$ is random. To circumvent this difficulty, we can partition the feasible interval for $\\mu$ geometrically (e.g., when $B = 2$, we partition to intervals of the form $[\\frac{1}{2^{k + 1}}, \\frac{1}{2^{k}}]$), apply Freedman's inequality within each interval, and subsequently take a union bound over all intervals. Notably, each interval corresponds to a condition on $V_X$ for which the optimal $\\mu$ falls within that interval, and for that interval substituting $\\mu = \\frac{1}{2^{k}}$ or $\\mu = \\frac{1}{2^{k + 1}}$ leads to only a lower-order blow-up in the quantity $\\mu V_X + \\frac{1}{\\mu} \\log \\frac{2}{\\delta}$ compared to substituting $\\mu^\\star$.\n\nWe hope that our responses answer your questions. If you have any further questions, please don't hesitate to reach out."}, {"review_id": "5B2JBtHdgK", "reviewer": "Reviewer_y6ag", "summary": "This work studies online calibration---the problem of making probabilistic predictions on a sequence of $T$ (arbitrary) binary outcomes---with respect to several different calibration measures.\n\nThe main contribution is the introduction of the KL-calibration error (and a \"pseudo\" version thereof). The authors proved that:\n- An $\\widetilde O(T^{1/3})$ KL-calibration error can be guaranteed.\n- An $\\widetilde O(T^{1/3})$ pseudo KL-calibration error can be achieved by an explicit algorithm.\n\nFurthermore, the KL-calibration error (resp., the pseudo version) is shown to upper bound the swap regret (resp., the pseudo swap regret) with respect to every proper scoring rule with a univariate form that is either smooth or twice continuously differentiable. As an application, the results above imply an $\\widetilde O(T^{1/3})$ bound on the $\\ell_2$ calibration error, recovering a recent result of Fishelson, Kleinberg, Okoroafor, Paes Leme, Schneider, and Teng (ALT 2025).", "questions": "I don't have any specific questions.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Online calibraion is a well-studied problem in learning theory. The newly-introduced KL-calibration is a natural calibration measure that has a nice decision-theoretic interpretation in terms of the log loss.\n- More interestingly, KL-calibration simultaneously upper bounds the swap regret with respect to many losses, and enjoys a much faster rate of $T^{1/3}$ compared to the $\\sqrt{T}$ rate shown by [Hu and Wu, FOCS'24] (for all bounded proper losses).\n- In addition, while the proofs use several prior ideas (such as the minimax argument and the Blum-Mansour reduction), they still involve new ideas such as the non-uniform discretization, which might be of independent interest.\n- The writing of the paper is very clear. The authors did a great job in comparing their results to previous ones, as well as adequately crediting the ideas to prior work.\n\nWeaknesses:\n- The results for $\\ell_2$ calibration---arguably the most well-studied measure to which the results in current paper applie---are a bit incremental: Foster and Vohra (1998), Hart (2022), and Fishelson et al. (2025) have already proved that: (1) An $\\widetilde O(T^{1/3})$ $\\ell_2$ calibration error can be achieved (inefficiently); (2) An $\\widetilde O(T^{1/3})$ pseudo $\\ell_2$ calibration error can be achieved (efficiently). So, as far as $\\ell_2$ calibration is concerned, it appears that the only new result is the high-probability bound (Appendix E).\n\nDespite the weaknesses outlined above, this paper presents fairly solid results and is a very nice addition to the recent line of work on online calibration---a problem that is of clear interest to the NeurIPS community. I vote for acceptance.\n\nOther comments / writing suggestions:\n- Line 74: It might be more clear if it is emphasized that the big-O notations hide factors that depend on the loss $\\ell$ (but not $T$), which aligns better with Lines 76-77 for $\\mathcal{L}_G$.\n- Reference [FKOPST25]: The last name of the fourth author would be \"Paes Leme\" instead of \"Leme\". (See the BibTeX file at https://proceedings.mlr.press/v272/fishelson25a.html.)", "was_revised": true, "final_justification": "I did not mention any specific questions in my review, so no response/further discussion was necessary. My evaluation of the paper remains positive after reading the other reviews and the authors' response to them.", "rebuttal": "We sincerely thank the reviewer for their positive evaluation of our work. We shall carefully incorporate your writing suggestions in the subsequent revisions."}]

Author rebuttal:

Meta-review: The paper studies the problem of online calibration. The Authors introduce and analyze KL-calibration, defined with respect to the logarithmic loss. They prove the existence of an algorithm that achieves $\tilde O(T^{1/3})$ KL-calibration, and further provide an explicit algorithm attaining the same rate for the so-called pseudo KL-calibration, which is defined using the forecaster’s conditional distribution instead of the actual prediction in the calibration error. Finally, the results are generalized to a broader class of proper losses.

All Reviewers agree that this is a very solid theoretical paper presenting novel results. Only minor weaknesses were raised, such as the paper being dense and hard to follow, providing only the existence proof for KL-calibration, or the somewhat incremental nature of the results. Nevertheless, the Reviewers unanimously conclude that the results are worth publishing at NeurIPS.
Decision: Accept (spotlight)