Optimal Multiclass U-Calibration Error and Beyond
Authors: Haipeng Luo
Spandan Senapati
Vatsal Sharan
Venue: NeurIPS 2024 poster (2024)
Keywords: Multiclass U-calibration
Pseudo Multiclass U-calibration
Minimax Regret
Follow-the-Perturbed-Leader
Primary area: online_learning
TL;DR: We prove optimal regret bounds for multiclass U-calibration, thereby resolving an open problem raised by Kleinberg et al. (2023).

Abstract: We consider the problem of online multiclass U-calibration, where a forecaster aims to make sequential distributional predictions over $K$ classes with low U-calibration error, that is, low regret with respect to all bounded proper losses simultaneously.
    Kleinberg et al. (2023) developed an algorithm with U-calibration error $\mathcal{O}(K\sqrt{T})$ after $T$ rounds and raised the open question of what the optimal bound is.
    We resolve this question by showing that the optimal U-calibration error is $\Theta(\sqrt{KT})$ --- we start with a simple observation that the Follow-the-Perturbed-Leader algorithm of Daskalakis and Syrgkanis (2016) achieves this upper bound, followed by a matching lower bound constructed with a specific proper loss (which, as a side result, also proves the optimality of the algorithm of Daskalakis and Syrgkanis (2016) in the context of online learning against an adversary with finite choices).
  We also strengthen our results under natural assumptions on the loss functions, including $\Theta(\log T)$ U-calibration error for Lipschitz proper losses, $\mathcal{O}(\log T)$ U-calibration error for a certain class of decomposable proper losses, U-calibration error bounds for proper losses with a low covering number, and others.

Optimal Multiclass U-Calibration Error and Beyond
Haipeng Luo" University of Southern California Haipengl@use @usc.edu
Spandan Senapati" University of Southern California ssenapat@usc. .dd
Vatsal Sharan"
University of Southern California vsharandusc.cm edu
Abstract
We consider the problem of online multiclass U-calibration, where forecaster aims to make sequential distributional predictions over K classes with low calibration error, that is, low regret with respect to all bounded proper losses simultaneously. Kleinberg et al. (2023) developed an algorithm with U-calibration error O(K /T) after T' rounds and raised the open question what the optimal bound is. We resolve this question by showing that the optimal U-calibration error is @(v (KT)=-
start with a simple observation that the Leader algorithm of Daskalakis and Syrgkanis (2016) achieves this upper bound, followed by matching lower bound constructed with specific proper loss (which, as a side result, also proves the optimality of the algorithm of Daskalakis and Syrgkanis (2016) in the context of online learning against adversary with finite choices). We also strengthen our results under natural assumptions on the loss functions, including Ollog T' U-calibration error for Lipschitz proper losses, Ollog T) U-calibration error for a certain class of decomposable proper losses, U-calibration error bounds for proper losses with low covering number, and others.
1
Introduction
We consider the fundamental problem of making sequential probabilistic predictions over an outcome (e.g.. predicting the probability of tomorrow's 's weather being sunny, cloudy, rainy). Specifically, each time = 1,..., T' a forecaster/learer predicts Pt E Ax, where Åx denotes the probability simplex over outcomes. At the same time, an adversary decides the true outcome, encoded by one-hot vector y: E & := {ei...., ex where e; denotes the i-th standard basis vector of R The forecaster observes yt at the end time t.
popular approach to measure the performance of a forecaster is to measure her regret against the best fixed prediction in hindsight. Fixing some loss function é AK x E + R, the regret of the fore- caster's predictions with respect l defined REG; Σ {(p:. yr) - -inff Σt= C(p. y:). Perhaps the most common class of loss functions to evaluate forecaster are proper loss functions. loss function is proper if E EEy=p!' (p. y) < Ey-pp!e (ipp.y)) y)] ] for all p.p' E A Hence proper loss functions incentivize the forecaster to predict the true probability of the outcome (to the best of their knowledge). We will focus on proper loss functions in this work.
T
Note, however, that regret is measured with respect to Specific loss function f. is unclear which proper loss one should minimize over for the specific application at hand and there could even
Author ordering is alphabetical.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

be multiple applications with different loss functions which use the forecasters's 's prediction. Could it be possible for a forecaster to simultaneously enjoy low regret with respect to all proper loss functions? This questions was raised in the interesting recent work of Kleinberg et al. (2023). They propose the notion of U-calibration error UCal == EE [suPrez REG,] (and a weaker version pseudo U-calibration error PUCal == Suprec B[REG)] for family of proper loss functions L. A forecaster with low U-calibration error thus enjoys good performance with respect to all loss functions in L simultaneously. Unless explicitly mentioned, we shall let L denote the set of all bounded (in [I), proper losses (as in Kleinberg et al. (2023)), and drop the subscript in UCalg and PUCalg for convenience.
The simplest way to get low U-calibration error is via the classical notion of low calibration er- for (Dawid, 1982), defined as Cal == Epe p. calibration error guarantees that whenever she makes prediction p. the empirical distribution of the true outcome is indeed close to p. Kleinberg et al. (2023) prove that PUCal - UCal O(Cal) and thus a well-calibrated forecaster must have small U-calibration error. However, getting low calibration error is difficult and faces known barriers: the best existing upper bound on Cal is ( x (Blum et al., 2008), and there is I2 lower bound (for K = 2) (Qiao and Valiant, 2021). Therefore, a natural question ask if it is possible to side-step calibration and directly get low U-calibration error. Kleinberg et al. (2023) answer this in the affirmative, and show that there exist simple and efficient algorithms with UCal ((VT) for K = 2 and PUCal = O(V)T) for general K. This provides strong -heeorent motivation for considering U-calibration error as opposed to calibration error; we refer the reader to Kleinberg et al. (2023) for further discussion.
yr)ll Intuitively. a forecaster with low
Following up Kleinberg et al. (2023), this paper addresses the following question that was left open in their work: "What is the minimax optimal multiclass U-calibration error?" We give a complete answer this question (regarding PUCal) by showing matching upper and lower bounds. Moreover, we identify several broad sub-classes of proper losses for which much smaller U-calibration error is possible. Concretely, our contributions are as follows.
1.1 Contributions and Technical Overview
First, we show that the minimax optimal value of PUCal is @(vKT):
In Section 3.1, we start by showing that simple modification to the noise distribution of the Nollow-the-Pertureed--ea Leader (FTPL) algorithm of Kleinberg et al. (2023) improves their PUCal = O(KVT) bound to KT). In fact, our algorithm coincides with that of Daskalakis and Syrgkanis (2016) designed for online learning setting with fixed loss function and an adversary with only finite choices. The reason that it works for any proper losses simultaneously in our problem is because for any set of outcomes, the empirical risk minimizer with respect to any proper loss is always the average of the outcomes (c.f. property (I)).
We then show in Section 3.2 that there exists one particular proper loss such that any algorithm has to suffer REG, = ! / VKT) in the worst case, hence implying PUCal = 92 (T) While our proof follows standard randomized argument, the novelty lies in the construction of the proper loss and the use of an inti-concentration incquality to bound the expected loss of the benchmark. We remark that, as a side result, our lower bound also implies the optimality of the FTPL algorithm of Daskalakis and Syrgkanis (2016) in their setting, which is unknown before to our knowledge.
While Kleinberg et al. (2023) only consider PUCal for general K, we take a step forward and further study the stronger measure UCal (recall PUCal < UCal). We start by showing an upper bound on UCalg. for the same FTPL algorithm and for any loss class L' with a finite covering number. Then, we consider an even simpler algorithm, Follow-the-Leader (FTL). which is deterministic and makes UCal and PUCal trivially equal, and identify two broad classes of loss functions where FTL achieves logarithmic U-calibration error, an exponential improvement over the worst case:
In Section 4. I, we show that for the class LG of G-Lipschitz bounded proper losses (which includes standard losses such as the squared loss and spherical loss), FTL ensures PUCalçe = UCalço = O log T).
We further show that all algorithms must suffer PUCal = 2(log T). While we prove this lower bound using the standard squared loss that is known to admit G(log T') regret in many online

---

learning settings (e.g., Abernethy et al. (2008)), to our knowledge it has not been studied in our setting where the learner's decision set a simplex and the adversary has finite choices. Indeed, our proof is also substantially different from Abernethy et al. (2008) and is one of the most technical contributions of our work.
Next, in Section 4.2, we identify class Leee of losses that are decomposable over the K outcomes and additionally satisfy some mild regularity conditions, and show that FTL again achieves PUCal = UCal = (log T) (ignoring other dependence). This class includes losses induced by certain family of Tsallis entropy that are not Lipschitz. The key idea of our proof is to show that even though the loss might not be Lipschitz, its gradient grows at controlled rate.
Given these positive results on FTL, one might wonder whether FTL is generally good algorithm for any proper losses. We answer this question in the negative in Section 4.3 by showing that there exists a bounded proper loss such that the regret of FTL is ((T).. This highlights the need of using FTPL one cares about all proper losses (or at least losses not in LG or Edec).
1.2 Related Work
For calibration, Foster and Vohra (1998) proposed the first algorithm for the binary setting with an (expected) O(Tå) calibration error (see also Blum and Mansour (2007) and Hart (2022) for a different x
proof of the result). In the multiclass setting, Blum et al. (2008) have shown an ((TxT]) x calibration error. Several works have studied other variants of calibration error, such as the most recently proposed Distance to Calibration (Blasiok et al., 2023; Qiao and Zheng, 2024; Arunachaleswaran et al., 2024); see the references therein for other earlier variants.
A recent research trend, initiated by Gopalan et al. (2022), has centered around the concept of simultancous loss minimization, also known as omniprediction. Garg et al. (2024) study an online adversarial version of it, and U-calibration can be seen as special non-contextual case of their setting with only proper losses considered. Their results, however, are not applicable here due to multiple reasons: for example, they consider only the binary case (K" = 2), and their algorithm is either only designed for Lipschitz convex loss functions or computationally inefficient. We also note that omniprediction has been shown to have surprising connection with multicalibration (Hébert-Johnson et al., 2018), a multi-group fairness notion, making it an increasingly important topic (Gopalan et al., 2022; Blasiok et al., 2024; Gopalan et al., 2023a,b).
2 Preliminaries
Notation:
We use lowercase bold alphabets to denote vectors. N. N>o denote the set of positive, non-negative integers respectively. For any m N, [m] denotes the index set {1..... [1....,m} m]. We use
AK to denote the (K - -i-diemnsio simplex, i.e., Ax {p E R p; 2 0, ΣK Pi 1}. The i-th standard basis vector (dimension inferred from the context) is denoted by e,, and we use E to represent the set fei....,
,......,er eek }ot of all basis vectors of R By default, ||.I| denotes the Eg norm.
Proper Losses: Throughout the paper, we consider the class of bounded proper losses = AR:AR & - [-1, l is proper] or subset of it. We emphasize that convexity (in the first argument) is never needed in our results. As mentioned, a loss is proper if predicting the true distribution from which the outcome is sampled from gives the smallest loss in expectation, that is, Ey>p!e(p, y)] < Ey-ple(p', y) for all p' E Ak.
For proper loss f, we refer to e(p y) as its bivariate form. The univariate form of É is defined as ((p) == [ y)]. It turns out that a loss is proper only if its univariate form is concave. Moreover, one construct proper loss using concave univariate form based the following characterization lemma.
Lemma 1 (Theorem 2 of Gneiting and Raftery (2007)). A loss f: AK X R is proper if and only if there exists a concave function I such that E(p, y) = f(D) + (gp. 1ppyy1a - p) for all p E Ax, y E E, where Ip denotes subgradient of I al p. Also, I is the univariate form of f.
We provide several examples of proper losses below:
3

---

The spherical loss is v( (p.z), which is V -iiischhit (Proposition B.1) but non-comvex lpl
in p. Its univariate form is E(p) |ppl-
The squared loss (also known as the Brier score) is {(p, y) = 3 lpp yl1 which is clearly 2-Lipschitz and convex in p. Its univariate form {pp
||||
K Generalizing the squared loss, we consider the univariate form ((p) -êx =i=1 P for > 1 and some constant čx > 0, which the Tsallis entropy and is concave. The induced proper loss {p. y) = čx (a - 1) E pf - δ E 1 yi. which is not Lipschitz for a E (1, P;
The following fact is critical for U-calibration: for any n E N and sequence of outcomes yI...., Yn E &, the mean forecaster is always the empirical risk minimizer for any proper loss & (the proof is by definition and included in Appendix B for completeness):
1 Σ y E argmin PEAK
1 Σ ((p.y,).
(1)
Problem Setting: As mentioned, the problem we study follows the following protocol: at each time .,. a forecaster predicts a distribution pt E AK over K possible outcomes, and at the same time, adversary decides the true outcome encoded by a one-hot vector y: E E, which is revealed to the forecaster at the end of time t.
For a fixed proper loss function f, the regret of the forecaster is defined as: REG, = ET ( Vi)
inf PEAK Et= f(p. yt), which, according to property (I), can be written as E ((p y:)
Et ((B, y.) where 3 = / Σ 1 y/: is simply the empirical average of all outcomes.
Our goal is to ensure low regret against class of proper losses simultaneously. We define U- calibration error as UCalz = E [suprec REG₂] and pseudo U-calibration error as PUCal =
supte c. E/RPEgE//RRA E[RGG]] for family of loss functions L. Unless explicitly mentioned, L denotes the set of all bounded (in [-1, 1) proper losses and is dropped from the subscripts for convenience.
Oblivious Adversary versus Adaptive Adversary: As is standard in online learning, oblivious adversary decides all outcomes y1..... yr ahead of the time with the knowledge of the forecaster's algorithm (but not her random seeds), while adaptive adversary decides each ye with the knowledge of past forecasts pI..... Pr-1- covering number), all our upper bounds hold for the stronger adaptive adversary, and all our lower bounds hold for the weaker oblivious adversary (which makes the lower bounds stronger).
Except for one result (upper bound on UCal for a class with low-
3 Optimal U-calibration Error
In this section, we prove that the minimax optimal pseudo U-calibration error is ((v KT).
3.1 Algorithm
As mentioned, our algorithm makes a simple change to the noise distribution of the FTPL algorithm of Kleinberg et al. (2023) and in fact coincides with the algorithm of Daskalakis and Syrgkanis (2016) designed for a different setting. To this end, we start by reviewing their setting and algorithm. Specifically, Daskalakis and Syrgkanis (2016) consider the following online learning problem: at each time E [T), a learner chooses an action a; E A for some action set A: at the same time, an adversary selects an outcome 0, from a finite set θ = _ 0xh of size K; finally, the learner observes O, and incurs loss h(,, 0,) for some arbitrary loss function h A θ [-1, 1] that is fixed and known to the learner. Daskalakis and Syrgkanis (2016) propose the following FTPL algorithm: at each time f, randomly generate a set of hallucinated outcomes, where the number of each possible outcome Ó for i E [K] follows independently a geometric distribution with parameter / KK /T. and then output the empirical risk minimizer using both the true outcomes and the hallucinated outcomes as the final
action a, Formally, a; E argmin Σi= Yr, 0.) where Y,, = I(s < II 0₂ = 0.H + m
Herr, the scaling constant čx is such that ((p y) E 1..

---

Algorithm FTPL with geometric noise for U-calibration
1:
for 1= I,...,
2:
For each E [K], sample m4,s independently from geometric distribution with parameter VK/T, and compute Y,, = {s < y/+ e;Hl + Ma,i.
3: Predict p: Ax such that Pt,i Yt.// Σ Yi,k, and observe the true outcome y/ E.
4:
end for
and m is iid. sample of a geometric distribution with parameter VK/T. This simple algorithm enjoys the following regret guarantee.
Theorem (Appendix F.3 of Daskalakis and Syrgkanis (2016)). The FTPL algorithm described
above satisfies the following regret bound: E. Ei= haa, 0.) infae. Ei= Maa, 0.) S 4VTT,
where the expectation is taken over the randomness of both the algorithm and the adversury.
Now we are ready to discuss how to apply their algorithm to our multiclass U-calibration problem. Naturally, we take A AK and e = E. What h should we use when we care about all proper losses? It turns out that this does not matter (an observation made by Kleinberg et al. (2023) already): according to property (1), the mean forecaster taking into account both the true outcomes and the hallucinated ones (that is, Pt.s = Yus// Ek= Yí,e) is a solution of argmin peAx ΣK Yi,h(pp, e;) for any proper loss L! This immediately leads to the following result.
Corollary 1. Algorithm ensures PUCal < KVKT against any adaptive adversary.
We remark that the only difference of Algorithm compared to that of Kleinberg et al. (2023) is that My, is sampled from a geometric distribution instead of a uniform distribution in {0, I,.., [VT] }. Using such noises that are skewed towards smaller values leads to better trade-off between the stability of the algorithm and the expected noise range, which is the key to improve the regret bound from TT) to OVVKT).
3.2 Lower Bound
We now complement the upper bound of the previous section with a matching lower bound. Similar to the Multi-Armed Bandit problem, the regime of interest is T 2(K).
Theorem 2. There exists a proper loss l with range [-1, 1] such that the following holds: for any online algorithm ALG, there exists a choice of y...... yr by an oblivious adversary such that the expected regret E REG of ALG is Q(vKT) when T 2 12K.
We defer to the proof to Appendix C and highlight the key ideas and novelty here. First, the proper loss we use to prove the lower bound takes the following univariate form E(p) - Σ Ip: which is in fact direct generalization of the so-called "V-shaped loss" studied in Kleinberg al. (2023) for the binary case. More specifically, they show that in the binary case, V-shaped losses are the "hardest" in the sense that low regret with respect all V-shaped losses directly implies low regret with respect to all proper losses (that is, low U-calibration error). On the other hand, they also prove that this is not true for the general multiclass case. Despite this fact, here, we show that V-shaped loss is still the "hardest" in the multiclass case in a different sense: it is the hardest loss for any algorithm with PUCal (VKT))
K
With this loss function, we then follow standard probabilistic argument and consider a randomized oblivious adversary that samples yI...., Yr i.i.d. from the uniform distribution over E. For such an adversary, argue the following: (a) the expected loss incurred by ALG is non-negative, i.e.,
E Et=1 e(pe, v.)] > 0, where the expectation is taken over yi...., yr and any internal randomness
in ALG; (b) the expected loss incurred by the benchmark is bounded as JE inf inf Σt= C(p, v1) <
-ev KT for some universal positive constant c, where the expectation over yi..... yr. Together, this implies that the expected regret ALG least KTT in this randomized environment, which further implies that there must exist one particular sequence of Vi.....B1 yr such that the expected
5

---

regret of ALG is at least eVKT, finishing the proof. We remark that our proof for (b) is novel and based on an anti-concentration inequality for Bernoulli random variables (Lemma A.4).
We discuss some immediate implications of Theoremm 2 below. First, it implies that in the online learning setting of Daskalakis and Syrgkanis (2016) where the adversary has only K choices (formally defined in Section 3.1), without further assumptions on the loss function, their FTPL algorithm is minimax optimal. To our knowledge this unknown before.
Second, since PUCal = sup, [[ 2 E[REGe] for any E' C, Theorem 2 immediately implies a 52( (T)) lower bound on the pseudo multiclass U-calibration error. In fact, since UCal 2 PUCal, the same lower bound holds for the actual U U-calibration error.
Corollary 2. For any online forecasting algorithm, there exists oblivious adversary such that UCal 2 PUCal (VKTT).
3.3 From PUCal to UCal
We now make an attempt to bound the U-calibration error UCal of Algorithm for an oblivious adversary. Specifically, since the perturbations are sampled every round and the adversary oblivious, using Hoeffding's 's inequality it is straightforward to show that for a fixed E and fixed ó E (0, 1), the regret of Algorithm 1 with respect to É satisfies REG, < 4VKT + /2T (1/) with probability (see Hutter et al. (2005, Section 9) or Lemma D.1). Therefore, for finite subset L' of C. taking a union bound over all & E L' gives suprer REG, I 4VKT + /2T log (5'1/8) with probability at least
at least
5. Picking 8 = 1 T/ and using the boundedness of losses, we obtain UCalg < 2 + KTT KT v 2T log (T [2']). In Appendix D, generalize this simple argument to any infinite subset L of with a finite e-covering number M (CC, e ooo)l and prove for any > 0,
UCale 2 4cT + KVVT + v log (T M(C', I1-11a)))
(2)
Using this bound, we now give a concrete example of simple parameterized family L' C for which UCalg (VKTT= VTlog log')) Consider the parameterized class
C' = (al (p. y) + (1-a1) (2- y)|a e [0,
where (p, y), 62 3) L are two fixed bounded and proper losses. is straightforward to verify that (p. = (l, y) + (1 (2 y) L. therefore L' C L.
To obtain E (0, 1) cover for L', consider the set = (0, e,..,, 1-,,, e, 13 which partitions the interval [0. 1] to smaller intervals each of length e. For each a E [0, 1]. let ca E C denote (break ties arbitrarily). Clearly, |a 1 ca S Next, consider the function
the closest point
Io (p, y) == C y) + (1 -ca) (p, y). The class
E [0, 1]} is clearly a 2e cover of L' with size 1. Thus, e: = ( It then follows from (2) that
UCal 0 -0 C KT
(Tlog + 2 -0(KT + Tlgg
on choosing e = T.. On the other hand, in subsection 4.3 we shall argue that for this class with a specific example of &2, FTL suffers linear U-calibration error (that is, UCaler R(T)).
1.
Improved Bounds for Important Sub-Classes
In this section, we show that it is possible to go beyond the O KT) U-calibration error for several broad sub-classes of L that include important and common proper losses. These results achieved by an extremely simple algorithm called Pollow-the-Leade (FTL), which at time > 1 forecasts'
P: Σ
yt argmin PEAK
Σ lp. y.).
(3)
'The forecast time f 1 can be arbitrary.

---

that is, the average of the past outcomes. For notational convenience, we define nu = Ex= 3/s so that FTL predicts P: = プ with 1,5 being the count of outcome before time t.
Importantly, since FTL is a deterministic algorithm, it's PUCal and UCal are always trivially the same. Moreover, there is also no distinction between oblivious adversary and an adaptive adversary because of this deterministic nature.
4.1 Proper Lipschitz Losses
In this section, we show that (llog T) is the minimax optimal bound for PUCal and UCal for Lipschitz proper losses. Specifically, we consider the following class of G-Lipschitz proper losses
LG = ElE E (((p.)) E(p', y)1 s G lp - p'll Vp. E AAK.E
As discussed in Section 2, the two common proper losses, squared loss and spherical loss, are both in LG for some G. Note that the class of LG rich since according to Lemma it corresponds the class of concave univariate forms that are Lipschitz and smooth (see Lemma B.2). We now show that FTL enjoys logarithmic U-calibration error with respect Lc.
Theorem The regret of For learning any LG most 2 + 2G log T. Consequently, FTL ensures PUCalça = UCal = O log T).
Proof. Using the standard Be-the-Leader lemma (see e.g.. (Orabona, 2019, Lemma 1.2)) that says Ei ((p++1, S pesx Σt=1 ((p: yr), the regret FTL can be bounded as
REG, 2
Σ U(p yr) e(p:11 9b) 2 G
Σ pp P.+1
where the second inequality is because l E Lo. Next, since pt
7h-11 --T
and p++1
24 we obtain
T n
REG; 52+G>
n; = 2
nhe y/ t(t -
2 + 2G
Σ
t t-1 t
t
2= t'
2=
2=2
where the equality follows since n. 74-1 + ye and the last inequality follows from the triangle inequality and ||l S
|1h = I - Finally, since Et S _dz log T. we obtain
REG, < 2 + 2G log T, which completes the proof.
closer look at the proof reveals that global Lipschitzness over the entire simplex AK is in fact not necessary. This is because, for example, in the term E(Pt: e,) - {(p++1 e,) for some E [K]. by the definition of FTL the corresponding coordinates pt, and Pt+1, are almost always at least L/T, with only one exception which is when t is the first time we have y:: ignore since the regret incurred is at most a constant. This means that having local Lipschitzness in certain region is enough;
and which we can
Lemma E. for details. Note that the loss induced by the Tsallis entropy (mentioned in Section 2) is exactly one such example where global Lipschitzness does not hold but local Lipschitzness does. We defer the concrete discussion of the regret bounds of FTL on this example to Section 4.2 (where yet another different analysis is introduced).
In the rest of this subsection, we argue that no algorithm can guarantee regret better than 2(log T) for one particular Lipschitz proper loss, making FTL, minimax optimal for this class.
Theorem 4. There exists a proper Lipschitz loss l such that: for any algorithm ALG, there exists choice of y Yr by oblivious adversary such that the expected regret of ALG is 2(log T)-
The loss we use in this lower bound is simply the squared loss E(p. y) = lpp-llll y1 with K While squared loss is known to admit (loog regret in other online learning problems such as that from Abernethy et al. (2008), as far as we know there no study on our setting where the decision set is the simplex and the adversary has only finite choices. It turns out that this variation brings significant technical challenges, and our proof substantially different from that of Abernethy et al. (2008). We defer the details to Appendix F and discuss the key steps below.
7

---

Since squared loss is convex in by standard arguments it suffices to consider deterministic algorithms only (see Lemma F.I). Moreover, for deterministic algorithms, there is no difference between an oblivious adversary and an adaptive adversary so that the minimax regret can be written as
Step 1:
T Σ E(pt. yr) - inf PEAx t=1
T (p: (p..v)) 8i)
VAL inf sup inf sup Pre Er
Σ
PIEAK yI
To solve this, further define Vn,r recursively Vn,r inf pefpex suPyEr Vntur-1 E(p. y) with
Vn. = - pnx Σ n,l(p, e:), so that VAL is simply Vo,r.
Step 2: Using the minimax theorem, further show that Va,r SuPqEA> Σi=1 q: 1a;
{(q) where the univariate form ((q) is 1 10-11g] ||ll/ (as mentioned in Section 2). Recall that we consider only the binary case K 2, so is straightforward to give an analytical form of the solution the maximization over q E Ax. Specifically, writing Vn.r = mg), as Vns.m2.r to make notation concise, we show
V2 (Vi (Vi-))) + Vighe
if V/2 -2,
Vna Vnn.ager
if - 2 < V1 - V/2 S 2
V1
i 1/2 2,
where V1 and V/2 are shorthands for V Vnn +1 and VnL m2, respectively. Next, by an induction on r we show that for all valid n1, n2, r it holds that -2 < V - 1/2 I 2 (Lemma E2),
therefore Vn, Vai, is always equal to (V1-V,)²
Vi+12
Step By an induction on r again, we show that Vay.ng exhibits special structure of the form
(ni - n2)² Ur T
2n1
+ Ur:
where {ur and {er - are recursively defined via u,+1 ur (u, + 4)² and u1+1
u. + u + r+1
7 2 with up = ti 0 (Lemma F.3). Since VAL = Vo.0.T = UT, it remains to show
2
VT 22oog T), which is done via two technical lemmas F.4 and F.5.
4.2 Decomposable Losses
Next, we consider another sub-class proper losses that necessarily Lipschitz. Instead, their univariate form is decomposable over the K outcomes and additionally satisfies mild regularity condition. Specifically, we define the following class
Live fEEC ((p)
Σ (.(p)) where each & is twice continuously differentiable in (0, }
Both the squared loss and its generalization via Tsallis entropy discussed Scction 2 are elearly in this class Ldtes with the latter being non- non-Lipschitz when E (1,2), The spherical loss, however, is not decomposable and thus not in Cdee. We now show that FTL achieves logarithmic regret against any l E Laee (see Appendix G for the full proof).
Theorem 5. The regret of FTL learning any E E Ldee is at most 2K + (K + 1) + log for some universal constant 33 which only depends on and K. Consequently, FTL ensures PUCal
UCalc O(Suptec.. K log T).
Proof Sketch. We start by showing certain controlled growth rate of the second derivative of the univariate form (see Appendix H for the proof).
Lemma 2. For a function that is concave, Lipschitz. and bounded over [0, and twice continuously differentiable over (0, 1), there exists constant >> O such that [p)l max (p) 1-p) for all
p E (0,1).
8

---

Note that according to Lemma 1, each & must be concave, Lipschitz, and bounded, for the induced loss be proper and bounded. Therefore, using Lemma 2, there exists constant e; > 0 such that (p) I C2 max (p' I-p for each i. The rest of the proof in fact only relies on this property; in other words, the regret bound holds even if one replaces the twice continuous differentiaaility condition with this (weaker) property.
More specifically, for each i [K], let T, = [41,1,....... 4.a: C [T] be the subset rounds where the true outcome is i (which could be empty). Then, using the Be-the-Leader lemma again and trivially bounding the regret by its maximum value for the (at most K) rounds when an outcome appears for the first time, obtain
K Σ
REG; S 2K +
E(pr. e.) -(p(+11,)) (ETA(()))
E
de,
By using the characterization result in Lemma 1, we then express (pr e,) and ((P+11; e,) in terms of the univariate forms {p:), ((pt+1). and their respective gradients Vl(p:), V((pt+1). Next, using the concavity of l,, the Mean Value Theorem, and Lemma 2, we argue that
K
(1
1 1 ENj
8 S
Bes |P+1, Pe.ll max
(4)
1- 1-
for some & that is a convex combination of Pt and P4+1, and constant Se, čg Cs (Ōx is the scaling constant such that E(p) čK Σ (p:)). To bound (4), we consider the terms 1 and |P++11-PiuLl individually and find that they always bounded by either ne-1, I-Er,j to the update rule of FTL. Thus, we obtain
E1,
or 1 according
K
K Σ
1
REG; S 2K + (e(S + S2), where S = Σ
S2
T4--1
t-
i=
(ET.)(,,,))
1=1
and B: ΣK which finishes the proof.
1 Se,s Finally, direct calculation shows S < K(1 + log T) and S2 S 1 + log T,
To showcase the usefulness of this result, we go back to the Tsallis entropy example.
Corollary 3. For any loss with univariate form {(p) = -ēx Ei Pf for a E (1, 2) (the constant ēK is such that the loss has range [-1, 1), FTL ensures REG, Olūxa(a - K log T).
Proof. As mentioned, our proof of Theorem 5 only relies on Lemma 2, and it is straightforward to verify that for the loss considered here, one can take the constant in Lemma to be a(a 1), and thus the regret of FTL is O(K Be log with 3 = Kēxa 1).
On the other hand, if one were to use the proof based on local Lipschitzness (mentioned in Section 4.1 and discussed in Appendix E), one would only obtain regret bound of order O + a 1)72-9 log T), which is much worse (especially for small a). Finally, we remark that for a 2 2, the bivariate form Lipschitz, and thus FTL. also ensures logarithmic regret according to Theorem 3.
4.3 FTL Cannot Handle General Proper Losses
Despite yielding improved regret for Lipschitz and other special classes of proper losses, unfortunately, FTL is not good algorithm in general when dealing with proper losses, as shown below.
Theorem There exists a proper loss and choice of of y..... yr by an oblivious adversary such that the regret REG; of FTL is Q(T).
Proof. The loss we consider is in fact the same V-shaped loss used in the proof of Theorem 2 that shows all algorithms must suffer 2 VKT) regret. Here, we show that FTL even suffers linear regret

---

for this loss. Specifically, it suffices to consider the binary case K = 2 and the univariate form + P2-
E(p) - (|p)
-11)- - Using Lemma 1, we obtain the following bivariate form:
((p (p.e1)=-- - sign pr 2): ((p,e2) = - - sign P2 2 P2-2)
where the sign function is defined as sign(x) if x 0; -1 if < 0 = 0. Therefore, ((p, e1) is equal to if < :; 0
2: if 2 2. SSiillrrl,, e2),e2) is equal to if P1 S 3: 0 p1 2: if pı 2- Let T be and yt C1 if odd, and e2 otherwise. For such a sequence y1,...., yr, the benchmark selects 3 = 7 Σ y:: = 112: (..22 and incurs cost. On the
other hand, FTL chooses =1 1 1 when t is odd, and | 1[--1 otherwise. Thus, the regret of FTL is REG, E. Epp, C2) T. This completes the proof.
1-2
Consider the parametrized class in subsection 3.3, let K = f2(p. y) correspond to the V-shaped loss in Theorem 6, and consider any (p, y) It follows from Theorem that REG,, = ((T) when = O, therefore UCalg = [0 REG,, S2(T), whereas Algorithm ensures UCalg O(
5 Conclusion and Future Directions
In this paper, we give complete answers to various questions regarding the minimax optimal bounds on multiclass U-calibration error, notion of simultaneous loss minimization proposed by (Kleinberg et al., 2023) for the fundamental problem of making online forecasts on unknown outcomes. We not only improve their PUCal = OT) upper bound and show that the minimax pseudo U-calibration ,. but also further show that logarithmic U-calibration error can be achieved by an
eгror is extremely simple algorithm for several important classes of proper losses.
There are many interesting future directions, including 1) understanding the optimal bound on the actual U-calibration error UCal, 2) generalizing the results losses that necessarily proper, and 3) studying the contextual case and developing more efficient algorithms with better bounds compared to those in the recent work of Garg et al. (2024).
Acknowledgements
We thank mathoverflow user mathworker21 for their help in formulating and proving Lemma F.5. Haipeng Luo supported by NSF award 1943607 and a Google Research Scholar Award, and Vatsal Sharan was supported by NSF CAREER Award CCF-2239265 and an Amazon Research Award. Any opinions, findings, and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views of Amazon.
References
Abernethy, J., Bartlett, P. L., Rakhlin, A., and Tewari, A. (2008). Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 1 annual conference on learning theory, pages 414 424.
Arunachaleswaran. F. R., Collina, N., Roth, A., and Shi, M. (2024). An elementary predictor obtaining 2/ distance calibration. arXiv preprint a4Xiv:240..11410.
Blasiok. J., Gopalan, P., Hu, L., Kalai, A. T., and Nakkiran, P. (2024). Loss Minimization Yields Multicalibration for Large Neural Networks. Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPlcs), pages 17:1-17:21, Dagstuhl, Germany, Schloss Dagstuhl Leibniz-Zentrum für Informatik.
Guruswami, V., editor, 15th Innovations in
Blasiok, J., Gopalan, P., Hu, L.., and Nakkiran, P. (2023). A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1727-1740.
10

---

Blum, A., Hajiaghayi, M., Ligett, K., and Roth, A. (2008). Regret minimization and the price of total anarchy. In Proceedings of the fortieth annual ACM symposium Theory of computing, pages 373-382.
Blum, A. and Mansour, Y. (2007). From external to internal regret. Journal of Machine Learning Research, 8(6).
Daskalakis, C. and Syrgkanis, V. (2016). Learning in auctions: Regret is hard, envy is easy. In 2016 ieee 57th annual symposium foundations of computer science (focs), pages 219-225 228. IEEE.
Dawid, A. (1982). The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):605661M
Foster, D. P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika, 85(2):379-390.
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
SIAM.
Gneiting, T. and Raftery, A. E. (2007). Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-377
Gopalan, P., Hu, L., Kim, M. P., Reingold, O., and Wieder, U. (2023a). Loss Minimization Through the Lens Of Outcome Indistinguishabiity. In Tauman Kalai, Y., editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1-60:20, Dagstuhl, Germany. Schloss Dagstuhl Leibniz-Zentrum für Informatik.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. (2022). Omnipredictors. In Braverman, M., editor, 13th Innovations Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 79:1-79:21, Dagstuhl, Germany. Schloss Dagstuhl Leibniz-Zeetrrum für Informatik.
Gopalan, P., Kim, M. P., and Reingold, O. (2023b). Swap agnostic learning, or characterizing om- niprediction via multicalibration. In Whirty-sevents Conference Neural Information Processing Systems.
Hart, S. (2022). Calibrated forecasts: The minimax proof. arXiv preprint arXiv:2209.05863.
Hébert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. (2018). Multicalibration: Calibration for the coomputaiionally-ddenffii pages 1939-1948. PMLR.
masses. In International Conference on Machine Learning.
Hutter, M., Poland, J., et al. (2005). Adaptive online prediction by following the perturbed leader.
Klein, P. and Young, N. (1999). On the number of iterations for dantzig-wolfe optimization and covering approximation algorithms. In International Conference on Integer Progranming and Combinatorial Optimization, pages 320-327 Springer.
Kleinberg, B., Leme, R. Schneider, J., and Teng. Y. (2023). U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory, pages 5143-5145. PMLR.
Orabona, (2019). A modern introduction to online learning. arXiv preprint arXiv:
Qiao, M. and Valiant, G. (2021). Stronger calibration lower bounds via sidestepping. Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 456-466.
Qiao, M. and Zheng, L. (2024). On the distance from calibration in sequential prediction. arXiv preprint arXiv:2402.07458.
Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press.

---

A
Concentration and Anti-Concentration Inequalities
Lemma A.1 (Markov's inequality). For a non-negative random variable X, and any a O, we have P(X 2 a) < _|X]
Lemma A.2 (Khintchine's inequality). Let C1....,6 er be i.i.d. Rademacher random variables, i.e. P(q: = +1) = F(G: = -1) for all i E [T]. Then,
T
T
1
E
E
V2
Y=1
for any .1,..., 2T E R.
Lemma A.3 (Hoeffding's inequality). Let X1,..., Xx be independent random variables satisfying a, S X; S for all i E (T]. Then, for any > O, we have
2c
P
Xr
B[X.) 2
S Sexp
.and
> (b: a:)²
2
P
Σ
- S -c) exp
E/=1 (bi - a,)²
Lemma A.4 (Reverse Chermoff bounds). (Klein and Young, 1999, Lemma 5.2) Let X = DT X; be the average T i.i.d. Bernoulli random variables X ; XT with E[X,] p.for all i [7]. e E (0, dl, E (0, [] are such that epp 2 3, then
P(X s c)p) 2 exp( 9222p)) 22X2(100)) 2 exp(-9c²pT)
B Deferred Proofs for Proper Losses
Lemma B.1. For proper loss E(p, y). the following holds true for any n E N and yi...., Yn E E:
a y: argmin
DEAK n E(p.g).
n
Proof. Let B == 1 Σn i= Yr. Since l is proper, Ey b)1 S Ey~ole(p', y)l for all p' e AR.
Notably, for any p E A K, have
B, e.)
1
ΣΣ
lyy eeje(pp e.)
|y ejj((p e;)
1 n Σ l (p.,j)) vj).
n
n j=1i=1
i=1j=1
Thus,
S E 0(',, yj) for any p' Ak. This completes the proof.
Lemma B.2. Let {(p) be differentiable and concave, a-Lipschitz function over K such that
(((p) is B-Lipschitz over Ag. Then, E(p. y) is proper and (2o + Lipsccit in E D for each
y E.
Proof. Since {(p) is concave, it follows from Lemma 1 that E(p, 8) is proper. To prove the second part, without any loss of generality, assume that y = e1. For any p. p' E Ak. we have
(pp E1) f(p' e1)
((p) + (Vi(p), p) (l(p') + (Vi(D'), - -'') Sa pa v,((p') ((p. V((p)) (p', v((p'))
< (a (p' p. V((p')) + (p. Ve(p') - V((p))
((a+3)lp--p) 1p pl /v(p')|l lell /V(p'') v(()))
2(a p p
12

---

where the first equality follows from Lemma 1; the first inequality follows from the Lipschitzness of the second inequality follows from the Lipschitzness of Vε(p); the third inequality follows from the Cauchy-Schwand inequality; the final inequality follows since |pp|| s 1 and VŁ(p) is Lipschitz. This completes the proof.
Proposition B.1. The spherical loss -i-pssschir
Proof. We shall show that [[ g)ll I VK for all E E.P E Ag. where the gradient is taken with respect the first argument. Without any loss of generality, assume y E1, thus E(p, y)
Pt. It is easy to obtain the following: pil
dl(p.y) y)
|p
pi
at(p. y)
PiPt
for all i 2.
Öp1
[pl
0p;
||||
Thus, [V((pee))] 1 y (llll
E 2
1p V (1pll -pî)
1 p
S VK,
where the last inequality follows the Cauchy-Schward inequality.
C Proof of Theorem 2
Theorem 2. There exists a proper loss l with range [-1, 1] such that the following holds: for any online algorithm ALG, there exists choice of y...... yr by an oblivious adversary such that the expected regret E REG) of ALG is ((VKT) when T 2 12K.
Proof. Consider the function defined as
K {(p) = 2
p:
K
1=1
It follows from Lemma that the bivariate form of is C(p, y) E(p) + (gp. y). where Dp denotes subgradient of {(p) at p. For the choice of f. 9. signn(p, k)), where the sign function defined as sign(z) = 1 0; -1 x < 0: 0 i = O. We first show that C(p y) E [-1, 1]. Without any loss of generality, assume y e1. Therefore.
1
K
K Σ
)
(pp.e
2
pj
K
(1-P))sige Jsign
P1
pisign
pi
K
K
1
1
2
P1
K
- (1 - ssign
P1
K
+
sigi
pi
K
pi
K
1=2
K
1
1
1
sign
P1
+
sign
pi
2
K
K
K
K
1=2
then trivial to note that p = El corresponds to a minimum, with value E(e), ei)
K K-1, K
[0, . corresponds to maximum, with value K-1
K
Next, we consider randomized oblivious adversary which samples y1...., yr from the uniform distribution over For such an adversary, we shall show that E[REG] = Q(VKT). We overload the notation and use ALG to denote the internal randomness of the algorithm until time / (inclusive). In particular, this notation succintly represents both deterministic and randomized algorithms (p: could be sampled from distribution D.). Similarly, ALG, shall denote the randomness at time t.
13

---

With this notation, in the constructed randomized environment, the expected cost of ALG is
T
ppe. mn)
E(pt. v.)
EALG . Ur
BALG 81... B..... (e(p,, yt)l
BALG v. BALG. L((:, (e)PP:.:))ALLL.--11 M1..... 91
BALG wh. BALG. B1 V1...... -
K f(p ei) 20,
EALG 1 EALG.
Σ K
where in the first equality have made the randomness explicit; the second equality follows from the linearity of expectations; the third equality follows from the law of iterated expectations; the fourth equality follows because ALG, is independent of y: (Pr is chosen without knowing y:) and vice-versa (ye is sampled uniformly randomly from E); the fifth equality follows by expanding out the expectation; the first inequality follows since Σ e(p, ex) 2 0 for any p E AK- This is because,
9p: K 1K - -D)
Σ ((p,e,) K((p) +
9p e; p) K ((D)
where 1g denotes the K-dimensional vector of all ones. Next, since {(p) is concave over Ax. the term above can be lower bounded by KE ( 1x) =0
Next, the expected regret of ALG can be lower bounded in the following manner:
T
E [REG2]
EALGH. M.................
Σ E(p vi)
inf PEAN
Σ
c(p yi)
2 - Eg "y... Ur
inf PEAK
C(p, yr)
1=1
T
--Ey....,y
Yt Yt
(5)
where the first inequality follows since the expected cost ALG non-negative, and the benchmark independent of ALG; the second equality follows from property 1. In the next steps, deal with the expectation in (5). Sample yı. yr from & and let Mı. 7kK denote the counts of the K
basis vectors, i.c., Kjj E [T]
y
e.H. Clearly, Σ = T.. Let n [ ng] collect
these counts. Then, 5 -t=1 D:
7
7 n. and
Σ
Yr Y
n, e;
K
T . ))
1
Σ
n44
T n
+
9
E;
K
1
T
Tt
-n
=
Σ
T
2
K
14

---

Thus, the term in (5) equals 2 multinomial distribution with event probability equal arrive at
Em......
Ei=1
K
n.
T
K
where ..,...,, nk are sampled from
Further, using the linearity of expectations
K
T
K 2
T Σ X. E[X,]
E REG 2
Emg
74
where X, is a Bernoulli random variable with mean K using an anti-concentration bound on Bernoulli random variables. particular, applying Lemma A.4, we obtain
Next, we bound E
D X - [[X,]
T E[X,]
9a K T
Σ X,
Za 2 2exp
(-T
t=1
for any a E (Lemma A. we have
V
37
T 2K
When T 12K, this interval non-empty. From the Markov's inequality
T Xx x E[X,] 2a)
E
Σ
X.
B[x,]
2 aTP
for any a 0. Setting a Thus,
3T K
we arrive at | X2 - -[X 2 2V3exp(-27)
[|EGG V3exp(-27))KK)
which completes the proof.
Remark C.1. For K 2. the use of Lemma A.4 can be sidestepped via the use of Khintchine inequality. Indeed, in this case have
T
T
E E
2
En
E
Σ
where El,..., ET are i..dd Rademacher random variables, and the last inequality follows from Khintchine's 's inequality (Lemma A.2).
D Bounding the (Actual) Multiclass U-Calibration Error
In this section, we bound the U-calibration error UCalg for subclasses L' of L with finite covering number. We begin with deriving high probability bound on the regret of Algorithm
Lemma D.1. Fix some & E L. Then, for any E (0, 1), the regret of Algorithm satisfies
1
REG S KV
2T log
8
with probability at least
Proof. Define the random variable X, = e(pt, V:), thus X, [-1.1]. Since the adversary is
oblivious and m4.1....; M,,K k are sampled every round independently. ....... Xy are independent. Applying Hoeffdings inequality (Lemma A.3), for any > O. we have
IP
E(p.. 31) -E [(((p, vi)]
< exp
2T
which implies that P (REG,
E REG. < c) 2 exp
(-27)
)
Let 8 exp
Then,
-2T)
2T
1 1 1 8.
P REG; R|EG < 27 log
Finally, applying the result of Theorem to bound E R|EGG completes the proof.
15

---

Using this high probability bound, we first bound UCalg when L' is a finite subset of L. Lemma D.2. Fix subset L' C C with |C'| < co. Algorithm ensures
UCalø $ KT
2T log (T)...
Proof. For any & C, let & denote the event that REG, & 4VKT+y/// 2T log (t) From Lemma D.I,
P (EE) 1- 5. Let suprec REGg, Thus, the probability that S is bounded by the same quantity P (E)) which can be bounded as
IP (()rec)
(ULEC: 8/) 21
-(E))= = P(E) 14' -
REC
EEE'
where the first equality follows from De-Morgan's law; the first inequality follows from the union bound; the last inequality is because IP (Et) 2 1 8. Setting 8 πie we obtain
IP REG, S LVVKT KT
2T log (T (2)
21-3 T
REL
=I
Note that, EES (PAEE [S + P(ATE [8) where A denotes the event that S A. Using the facts E [ < A, P P(A) I and AS) v 27 since l E [-1, we have
S 24
which completes the proof.
Before proceeding further, first define the notion of cover and covering numbers.
Definition D.1 (Cover and Covering Number). The e-cover of function class F defined over domain a function class C. such that, for any f F there exists g C. such that sup=ex [f(x) - g(x)) < The covering number M(F,e;ll (l-lee) is then defined as M(F, 6, 11-1lo0) = min {[C,) Ce is an e-cover of F), i.e., the size of the minimal cover.
The ||-1bs in the notation M(F,e, 6; |1-l is used to represent the fact that the "distance" between two functions f.g is measured with respect to the ||-Ilac norm, i.e., sup=ex' [f(x)) g(x))]. Such a definition can be generalized to more general distance metrics/pseudo-meete our purposes. Note that the cover C, in Definiton D. is not necessarily a subset of F. We refer to Wainwright (2019) for an exhaustive treatment of cover and covering numbers of different classes F's.
but is not required for
Let C, be minimal e-cover of F. For each Ce, let Sg.e be the collection of functions f E Fucch that g a representative of f. i.e.,
Sg.e {SEF) sup (f(x) - sej
(6)
ØEX
Clearly, UgEC.S,, F. For each Sg.e, fix a fleod Sg, (chosen arbitrarily) as a "leader". Let Llead,F denote the collection of these leaders. It is clear that LLeeddFF S |c.| = M (F,esillllla)
In the following lemma, generalize the result of Lemma D.2 to the infinite subset L. Our proof is based on applying the result of Lemma D.2 to the leader set L'
when L' is a possibly
Lemma D.3. Fix a subset L' C L with covering number M(C', l| I1-l Then, the sequence of forecasts made by Algorithm 1 satisfies for any > O,
UCalg 22+46T KT
2T log (T PMMM((''s 11-1
Proof. Let C. be an e-cover of L' of size M ('C,',, (1-1loc) and Llead C L' be the corresponding leader Applying Lemma D.2, we have
E
sup REG, LEE
< 2 KT
/2T log Licad) < 2 KT /2T
16

---

Now, fix any & L' and let E Ce be the representative of f. and l' correspond to the leader of the partition Sge that belongs to. By definition we have the following:
(g(p, y) pp. y) S, (g(p.y) y) (pp y) Se
for all p E A E E. Therefore, it follows from the triangle inequality that [e(p, y) (p. y) 2e. As usual, let / 1 Et=1 denote the empirical average of the outcomes. Then,
E(pr, y:) 8(3, y.) = El (p,, ye) (33 y.) 4e = REG, S REG + 4eT.
Taking supremum with respect to l on both sides, followed by expectation, we obtain
E sup REG;
- E sup REG,
4eT' 2 4eT + 4VKK + / log PMM((C, l)
LEEC
Leer
which finishes the proof.
E Regret of FTL for Locally Lipschitz Functions
Lemma E.1. Suppose for loss function t, there exists constant G f 1] such that for each
i E [K], [(p, e;) is locally Lipschitz in the sense that |e(p, e,) - f(p', ei) S G4+,11 llp - pp for all p.p' E AR such that pi,rl E [7,1] 2K + G1 + log T).
1]. Then, the regret of FTI. with respect to this loss is at most
Proof. Using the Leader lemma, we know that the regret of FTL be bounded as REG S 2 Σi E122mm=e. {(p,, e,) ((p++1,,;) Assume that &. S of size m S K contains all the outcomes chosen by the adversary over T rounds, i.e., yr E &m for E [T]. For each e, & let k; denote the total number of time instants i such that y, and let T, = (1i,1,..., li,,) denote those time instants. Then, we have
REG, 22+
Σ
Σ
((p,, e;) E(p
mm 122:2
S 2m +
((pr,e)) ((p:+1.;),
CLEE (ET.)(
where the last inequality follows by bounding ((pr,e;) - ((p+11, ei) with 2 for all the I's where an outcome appears for the first time. For each e, &m and for all tr, we have Pt,i ne-1. 2 1 Therefore,
REG, < 2m G(+.1)
Σ
Σ
|p: Pi+1ll
e.E8m (ET.)(Aa)
2m + + G[1.1]
Σ
Σ
n--
n2
t-1
E,
(ET))
Proceeding similar to the proof of Theorem 3, we can show that
T 1 Σ!ーΣ!!
REG; S 2m + G[+.1) Σ Σ
1
2m + G
Σ i
t
tia1
E: LET.
E.EEm
2K - G + log T')
where the last inequality follows by dropping the negative term, m & K, and E ] S S 1
log T. This completes the proof.
Example F.I. Consider for instance the loss whose univariate form E(p) -ēx Et=
P.t where (1, 2), and čK > 0 is normalizing constant (which only depends on K) ensure that É(p, y)
17

---

is bounded in [-1,1]. Clearly, E(p) is concave and thus the induced loss E(p, y) is proper as per Lemma 1. For the chosen E(p), f(p,e) given by
P p.V(p()) = (1 (1- a) Σ 2=
K
K Σ 1=1
+ app opp-1)
+1 -1
Pi
(
It is easy to verify that Vit(p, e1) = - ala 2 p1) and V;l(p, = -xx a(1 o)p for all i > 1. Thus. for large T, G(z.1] is of order O - 11)xx T2-a). This yields regret bound O(K + a(a - 1) log )) which for a (g. 2) is better (with respect to T)
than the O(vKT) bound obtained in Theorem 1.
F Proof of Theorem 4
Theorem 4. There exists a proper Lipschitz loss E such that: for any algorithm ALG, there exists choice of y...... Yr by oblivious adversary such that the expected regret of ALG is 22 T)
As mentioned, the loss use in this lower bound construction is the squared loss ((p. y) |pp - y/l² (we ignore the constant 1/2 here for simplicity, which clearly does not affect the proof). clearly convex in p for any y. The univariate form of the loss is
K Σ i=1
{(p = Ey-ple(p.p))) v)] = Pr - eall = =lll? + 2
Ps (p) = 1 -lpp1?
i=1
now follow the three steps outlined Section 4.1.
Step 1: First, it is well-known that for convex losses, deterministic algorithms are as powerful as randomized algorithms. Formally, let Arand and Ader be the class randomized algorithms and deterministic algorithms respectively for the forecasting problem. Then the following holds:
Lemma F.1. For any loss E(p.y) y) that is convex in E A for any y E E, we have
inf ALGE
sup UE
IE [REG]]]
inf sup REGg. ALGE yI....rrE
Proof. The direction "=" is trivial since Ader C Avond- For the other direction, it suffices show that for any randomized algorithm ALG E Avand, one can construct deterministic algorithm ALG' E Ader such that, for any fixed sequence yi...., , yr E, the expected regret of AL G is lower bounded by the regret of ALG'. To do so, it suffices to let ALG' output the expectation of the randomized output of ALG at each time Since the loss if convex, by Jensen's inequality, the loss of ALG' most the expect loss of ALG. This finishes the proof.
Since there is no difference between an oblivious adversary and an adaptive adversary for deterministic algorithms, inf sup, supy..... yr. REG, can be written as
VAL <<
Y Σ E(p yi)
inf sup PIEAK MEEE/
inf Σ (p. y1)
PEAK
where ((inf e sup suppes))
shorthand for the iterated expression
inf sup inf sup PIAA # EL PHEAK PIEAK 3E
inf sup inf sup Pr- yr EE EA vr
Let n E NK be vector such that n, represents the cumulative number of the outcome i, and E {0, .0....,T'} represent the number of remaining rounds. For any and such that ||n|]| + T. define Vn,r recursively as
Vn,r inf sup Vnty.r-1 + E(p. y)
PeAx yEE
with Vn.0 innfPEAx Σ nll(p, e.). is then clear that VAL is simply Vo.T-
18

---

Step 2: We proceed to rewrite and simplify Vn,r as follows:
Vn,r inf sup Vn Vn-yyr-1 + E(p.y) y)
(8)
pEAk yEE
inf sup By-q Dnty, + ((p v)
pEAx qeak
sup inf
By-q Nntyrr-1 + {(p
qeAx pEAx
K
sup inf
Σ
qi +
qedx PEAK i=1
K
sup inf gEdx pEAx i=1
Σ
qi V - (V(l)) -p))
K
sup inf geáx PEAK
Σ
q:
(V((p).q-)) --p))
K Σ - + E(q): qEAK
sup
where the second equality follows since Eyruq -n-y.r-1- + ((p. is linear function in and the infimum/supremum of linear function attained at the boundary; the third equality follows from the minimax theorem as Ey-q -n+yrr- + É(p, y) is convex in p and concave in q, the final equality because {(p) + (Vt(p). 9 p) 2 E(q) which follows from the concavity of the univariate form of l, and equality is attained at q.
Throughout the subsequent discussion, we consider K = 2 and use the concrete form of the squared loss. Writing V(n m2).r as Vai.,g,r for simplicity, we simplify the recurrence to
V Vni.ag.r sup qi Vi 1ai+1,ng.-- + q2 vn
of 42
sup V/2 + (V1 - (V)--))--- - 2(q² q), vc(0.1]
where V1, 1/2 is shorthand for Vn, -1 Vnj.ngtlr-1 respectively. It straightforward to show via the KKT conditions that
V/2
if - 1/2 -2,
sup 1/2 + (V1 V2)g 2(q² 9) (E
11 [2)=
+
+
if < V1 1/2 S 2, (R)
8
2
1/1
in - 1/2 > 2.
Thus, (R) (with V1, 1/2 replaced by 1. 1: Vnn 12t.n11 represents the recurrence we wish to solve for to obtain Vo,aT- The base case of (R) is the following:
Vn.r-n.0 = (
12
n
n
11
(9)
which holds for all n such that 0 < n < T. In the next lemma we show that -2 V1 V/2 S 2, therefore, it is sufficient to solve the recursion (R) corresponding this case only.
Lemma F.2. The recurrence (R) is also equal the following:
(V -1 - Vn V Vnyt + Vn, Vng.agtlr--
V Vnn
(R))
8
2
2
Proof. It suffices to show that the condition |Mr+ti Vnn mh - S always holds.
Rewriting n2 + 1 as n2 and r as r, this is equivalent to showing
Vnn.e2.r Vn, 1,m,,
(10)
for all n, n2, r such that ny + ni + = T, and the arguments in (10) are well defined, i.e., 0 < ni < T r 1, and < no < T We prove this by an induction on
19

---

Base Case: This corresponds to r = 0. For 0 S n =T - 1, n.,T-n.n - Vn-1,T-n-11 is equal to
2T
n ++ 1
n2 + 1
-
|
= 2 1-
2n -
2
1 T S 2,
T
T
T
which verifies the base case.
Induction Hypothesis: Fix a ke E (1,..., T): assume that (10) holds for k 1.
Induction Step: We show that (10) holds for r = It follows from (R) and the induction hypothesis that
1 (V (Vns+imand-1 - Vn, v + +11 + Vna 1h..-22a -2
V Voi
8
2
Vn +1m (v +2 Vns +1m 2)² Val lAk-1 + +1n+
1 8
2
2
Let 01
= Vai 1,2 = L, 03 == L, A = V L.
V nn..na.k Subtracting the equations above and expressing terms of the defined quantities, we obtain
01 02
(01
(z2)
02 a3
(a2 0x3)
A
8
01 03
(0) 0r)
(o1 + 03 202)
8
I + y
(x + 3) (I
+
(x + 2)² (y 2)
8
where we have defined x == (r) 022 == 02 0g. It follows from the induction hypothesis that |x|| < lyl < 2, therefore |ا] S Summarizing, we have shown that 111+1, Vai.n2, 2 which completes the proof via induction.
Step 3: Since 71 + n2 +r= we may express Vny,ag.r in terms of nı, n2, and T. In the next lemma, we show that Vni.zgir exhibits a very special structure when expressed in this manner; this allows us reduce Vu,oTr to solving a one dimensional recurrence.
Lemma F.3. For all n1, B2 such that n1, n2 2 0, and n + = T - r, it holds that
(n1 - n2)
2n1
Vny
2 Up
+ Cr:
(11)
T
where (ur)7-o ) - are sequences that depend only on T, and are defined by the following recurrences:
U4 + 7
1
Ur
T + 1
Uy Ur +
1r41
- U
+
(12)
2
T
2
for all 0 STST- 1, with uy 0o
Proof. Similar to Lemma F.2, the proof shall follow by an induction on
Base Case: For 0, it follows from (9) that V Vnimg.0 2nin2 Un = Up = 0.
which is consistent with (11) and T
Induction Hypothesis: Fix a k E (o...., T 1}. Assume that (11) holds for k.
Induction Step: We show that (11) holds for
From Lemma F.2, we have
V + Vay+ Vay+1.n.k 1.g. Vaj. Vny.ag.k+1 (Vny+ 1,
(13)
2
2
follows from the induction hypothesis that
Voy+I.ng. (nl 122)²
2(n1 + 1) 122
Ukk
+ Uk:
2
T
(nl 722 - 1)2
2n1 (nz + 1)
V m1,k2+1k
+ Uk.
2
T
20

---

Define 8 = +1 Vna m2
and o = Vna +1,mz + Vun Subtracting the equations
above, we obtain
(n1 + 122)2 2 (n1 - n2 1)2
uu + 2n1 (n2 + 1) 2(n1 + 1) m2
T
= 2(m1 - 122)
uk + TT)
Adding the equations above, we obtain
[n1 + n22)2 + (m -n2 1)2
2n1 (n2 + 1) + 2(n
+ 12) n2 20R
Uu
2
T
4m1m2
2(m
+ 122
((n1 -m2)² + 1) un
+ 20%
T
T
4nt
2(r + 1)
(n1 n2)² 2- u1
+ us
20k
2,
T
where the last equality follows since nı + n2 = T - 1. Expressing mn terms of 6, a.
we have V kn1m
8²
2.4 Substituting 8, we obtain
(n1 n22
22
Uk
(r+ (r+1) 1)
VRa Vn
uk +
uk + T
+
+
+
2
T
2
T
2
(ni1 n12)
2n 122
Mk++1
+ Uk++1
T
which completes the induction step. The proof is hence complete by induction.
Since VAL Vo.o. vT. it only remains to bound vr. Note that the recursion describing is coupled with u. However, since we only want to bound UT, we can sum the recursion describing v to obtain
1 (c.+1 n,)) = Σ u
-
T 1 2
Eup u Eu++1 r=0
Σ
Moreover, since the summation with respect telescopes and Un 0, we have
T-1
Σ Ur +1
vr = 2
Therefore, it remains to bound Σ T-- Uy Define a, = ur + 1 so that By = 1 - a,, The
T
2
recurrence (12) describing u reduces to 0,41 = + a² for all 0 S r s T - with ap 1. In the next result, obtain bounds ar.
Lemma E4. For all
T it holds that o, T-p
Proof. As usual, the proof shall follow by an induction on r. Since ag = 7. the base case trivially
satisfied. Fix a k E (o...., 2}. and assume that as S T-k- Since 0g+1 = a + az we have
T-k+1 (T 1=)2-1
a++1 < k)² + T (T - k)2 (T k)) T k
< T - k 1
This completes the induction step.
Lemma F.5. For all SrST 1, it holds that o, T-r+logT Furthermore,
T-1
T
Σ
a, > log
+ 2(logT).
log T +
21

---

Proof. According to Lemma F.4, we can write a, T-r+b, for some non-negative sequence { with bo O. We next obtain the recurrence describing {6, J. In particular, since ar+1 a, + 1). we have
T (r+ --r+b, ( - (T- +1)
which on simplifying (by multiplying both sides with (T' (r+ 1) + bx+1) b,)) yields
+ b, br-1
by+1 by T r r b,
(14)
Next, we shall show by an induction on r that b, S =1=0 T- for all 0 S - Since
the base case trivially satisfied. Fix a k -0,....: 2) and assume that by S Σ - We consider cases depending whether not by-1 > by- If by-1 by, the induction step holds trivially. If bb+1 2 bR, it follows from the recurrence (14) that
1
b S by + T l: bb S by +
T
2=0
which completes the induction step. 0 T - 1. It then follows that
Therefore, we have established that b, S Ei= T- for all
T Σ 1=0
T dz log T,
6,
T
2
for all < ST 1, which translates ar T-r+log This completes the proof of the first part
of the lemma. With this lower bound on ar, can lower bound Σ/=1 a,
T-1
Σ a Σ r=0
T-1
- log Σ it logT
dz
log
T log + +1).
+ =+log
which is Q(log T') for a large T. This completes the proof.
To conclude, have shown
T-1
T-1 22log
VAL = Vo,0. = =0
1
Σ
+ 11
Σ
2 r=0
1=
proving Theorem 4.
G Proof of Theorem'
Theorem 5. The regret of For learning any & E Laee is most 2K + (K + 1)3e(1 log Io) some universal constant 33 which only depends on and K. Consequently, FTL ensures PUCal UCal O(Suprec... 33) log T).
Proof. We work with the notation established in the proof of Lemma E. The regret FTL can be bounded
REG S 2m +
Σ Σ
C(p:, e;) - e(pr+1,
E:
51,2
In the subsequent steps, we shall bound 8 We begin in the following manner.
dz.; = E(p.) + (e: Ps, Ve(p.)) ((p++1) (e: P++1, V((p+t))
E(p.) ((p(1)) -
(prsi, V((p++)) (p., V((p:))
S [V(pp)) (VEpp (p:. v((p..1) - V((p.)),
22

---

where the first equality follows from Lemma 1; the first inequality follows since E(p.) S ((p++1) (V((p:1)).P) Pet1) which follows from the concavity of l. Next, by the Mean Value Theorem,
V((p++1) Ve(p.) (pp + o(pe+1 - P:)) (pe41 - -Pc)
for some v E [0, 1]. Note that Pt.j = --1 - = no 1.t1 (since y: = e;), therefore Pr+1,i 2
Pt. Let & = Pr + up -P:). Then,
[(((:)) [V((p=1)): = ( ((E))) P.-
where (V)((E))) denotes the i-th row of (V2R(E))]; we arrive at
,,, - (IV P Pe+1) (pu+1 Ps, V-((E)))))
vi,)(E)) (p4+1. Pc,s) + Σ
Pa.j (EE(EE)) (p(+1.f - Pt.))
j=1
& Vi,C(E)) (D0+1. -p,1) + Σ Pt." Viz((E)) (P(41. - Ph.)
V ((E)) -(Pp)-(p-- P+415)l.
(15)
where the first equality follows since Pc+1,i 2 Pt, and (E, S O; the second inequality follows by dropping the term Pt. (E,) (pt+1, - Pt,)) which is non-positive; the final inequality is because, for j * i, we have P++1,j Pi-Li and pt.j
therefore P++1,j S Pt.j. and bounding 1-1
Pt.i S
To proceed with the further bounding, we apply Lemma and utilize the growth condition on the (E))(E)) čK Cy max Ei..' T-Ei. for some constant ej > and all j E [K] (here ēx is the scaling constant such that {(p) = ēσ Σx (pi)). Let Be,j = õg cg. Using the bound
Hessian
on V (E::) to bound the term in (15), we obtain
K
1
)
8
S
Bes
max
P - P(+15l. Enr
(16)
Evj""
1
1=1
Next, shall bound the terms Ti Pea To Pt-ta-Pe. Ts PPe11. and Ta
Ex,
1-fr.
Poa- where the index j in and T4 runs over j # i. Note that,
1-Sty
De+ Pr.i
Pr+1,
Pt.i
11--1,4
Ti Pt.i + 2 P Pt.s)
Pt.i
74-1,i
14-1,1
Th
where the first equality follows from the definition of & the first inequality follows since P1+1,6 2 Pt. and [0, 1). Similarly,
P1+1. - Pt.
Pi+1. Pt.
T2
Pt,i
v(p+11, pe.s)
1 P++
14-1, + 14-1,i
t t-
t t- 1 - 11-1,
t
11-1,
1
where the first inequality follows since P141,1 2 Pt.i. For Ta, we have
PelLi
1
Ta
Pt.j
1
Petli
-
t
1'
Pc.s
23

---

where the inequality follows since v E [0, 1]. Finally, we bound T1 as
Pet-ia
T4 (1+
Pe.
7g-15
1
Pe+li
t- n1-1.
Rt-1,2
Pe.j
Phi
R1-1.5
where the final inequality is because Σ K T4, and substituting them back in (16), get
Ei=1
me-1,5 - 1. Collecting the bounds T1, T2, Ts. and
t 2-11-
òe, Σ Bes max
S
B
11
14-1,1
Summing over all f, we obtain REG, S 2m Be(S] +2), where S1 = -ereE EIETIME 1.2
S2 = 3 Eejee, Eler(on)) - and BR Σ Be.s- Note that the subscript in Be denotes that the constant is dependent on the loss and only depends and K. We bound Si as
=
Σ
S m
S m(1 log T) 2 K(1 + +og T)g
C.EE
1=1
Next, note that S < E
< 1 + log T. Thus, S + + < (K 1)(1 + log T), which yields
REG, < 2K (K 1)3a(1 + log T). This completes the proof.
H Proof of Lemma 2
Lemma 2. For a function that is concave, Lipschitz, and bounded over [0, 1] and twice continuously
differentiable over (0, 1), there exists a constant e > 0 such that (f) S c max (1) +-p)) for all p E (0.
Proof. Since f is twice differentiable, if (p)) does not approach infinity at the boundary of [0, 1], then there nothing prove. In the rest of the proof, we assume that [f"(p) approaches infinity both when approaches ( and when approaches 1 (the case when it only approaches infinty at one side exactly the same).
Using a technical result from Lemma H.1, there exists an én E (0, 1) such that for any E 60),
(p) (f) f
for some E [p, 1], which can be further bounded by
(g) f'( (g) + (f'(0) < suPre(o.1) (f'
< e max 1
5 (111)
1
p
P
with C = sup [f'()) (finite due to f being Lipschitz). Similarly, there exists E (0,1) such that for any E1, 1),
[r"(~) (1)
1-9
for some [0,p], which is further bounded by
(1) l'(4) [[(1))++1') S max 1-p
1
p'1-p)
p
Finally, for any p (Eo, E1), we trivially bound (p) as
[f"(p) < max (11-))
(f"
('1-p) (E(en.1-e1)
sup max 4 I
where 02 finite since f is twice continuously differentiable in (0, 1). Setting max finishes the proof.
24

---

Lemma H.1. Let f satisfy the conditions of Lemma 2 and additionally lim If (p) co and lim, pim--11 (p) cc. Then there exists 6o E (0.1) such that for any p (0, Enl. we have (q (0) = (p)g for some q E [p.1] 1]. Similarly, there exists (0,1) such that for any PEl 1) we have (1(1) - (4) (p) q) for some q E [0.p]-
Proof. For simplicity, we only prove the first part of the lemma since the proof of the sec- ond part follows the same argument. Since f twice continuously differentiable in (0, 1) and limp-vo (p)l oo, there exists concave, this is equivalent to f" being increasing in (0,c).
1) such that [ is decreasing in (0, Since f is
Now, applying Mean Value Theorem, we know that there exists 6o E (0, c| such that fe (( ("(C))c c. remains to prove that for any p E (0, col. the function g(g) = (' (0) (m)g has root in p, 1]. This is true because
g(p) = -"0
(f - f" -
where the equality by Mean Value Theorem again for some point { E [0, p) and the inequality holds since f is increasing in (0, c). On the other hand, we have
g(t) (e) - ('() - ("( (""())))=00)'
2 0,
where the equality holds by the definition of cn and the inequality holds since again f increasing in (0, e]. Applying the Intermediate Value Theorem then shows that 9(4) has root in [p, e]. which finishes the proof.
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 key contributions of the paper are summarized in the abstract and more details can be found in Section
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 the paper and important assumptions and limitations. A No or
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 of the work performed by the authors?
Answer: [Yes]
Justification:
Refer to Sections and
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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
25

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution 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 be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In every section, the assumptions clearly specified, and each lemma/theorem has a proof which can be found the appendix.
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 proofs can either appear in the main paper 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same datasct, provide access to the model. In general. releasing code and data is often
26

---

reproducible, they one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access 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 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 to reproduce that algorithm.
(b) If the contribution is primarily new 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 way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe 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., to registered users), but it should be possible for other researchers have some path 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?
Answer: [NA]
Justification:
The paper does not have any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
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 NeurlPS code and data submission guidelines (https: / //wpps.ccc////////////
wwriiissiiopiicyoyo. for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments 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 as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not have any experiments.
Guidelines:
27

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error 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 execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://nneuipppeeee httprrpp.....ppplttthcccciieeeee
Answer: [Yes]
Justification: The authors have carefully reviewed the NeurlPS Code Ethics and thereby confirm that this work agrees with it.
28

---

Guidelines:
The answer NA means that the authors have not 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 their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper does not pose any societal impacts.
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 unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 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 as 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 ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to 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. Licenses for existing assets
29

---

Question: 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?
Answer: [NA]
Justification: The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does not use 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 (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.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, paperswithcom thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged to reach out 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 does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model 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 does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
30

---

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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing 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 expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
31


Reviews:
[{"review_id": "hiNY59HfuR", "reviewer": "Reviewer_aUK6", "summary": "This works considered the the problem of making sequential non-contextual probabilistic predictions over $K$ classes with low U-calibration error.\nThe authors improved the upper bounds for U-calibration error from $O(K\\sqrt{T})$ to $O(\\sqrt{KT})$ after $T$ rounds, and they showed an existing algorithm, Follow-the-Perturbed-Leader (FTPL), achieves this upper bound.\nThe also proved a matching lower bound, and shows the optimality of FTPL.\nFurther, they provided strengthened bounds of $\\Theta(\\log T)$ under various additional assumptions on the proper losses.", "questions": "- L25: Based on the regret definition, it seems the it can be negative because the best prediction in hindsight is fixed for all time steps? For example, an oracle $p = \\arg\\min_p \\sum_{t=1}^{T} \\ell(p, y_t)$ achieves 0 regret, and an oracle  $p_t = y_t$ for all $t$ has negative regret.\n- L124: is the condition \"if and only if\"? See the interpretation immediately after Theorem 2 Gneiting and Raftery (2007): \"Phrased slightly differently, a regular scoring rule S is proper if and only if the expected score function G(p) = S(p,p) is convex on Pm\".\n- In Section 3.1, would it be nice to accompany the algorithm description and theoretical guarantees by some intuition why this randomized algorithm works? For readers not familiar with FTPL, a naive forecast would be to just predict the class frequency $\\boldsymbol{\\beta}$ up to the current time step. Why is it worse than FTPL and what is the intuition behind the randomization in the algorithm?\n- In Section 3.1, is it better to use the notation system established in previous sections to translate the FTPL algorithm in Daskalakis and Syrgkanis (2016)? For example, I think both are fine, just curious which one is more accepted.\n- L181: dose -> does", "limitations": "Limitations are addressed theoretically in Section 4.3.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper is well written and the logic is easy to follow.\n- This paper makes original and significant contribution by improving the upper bound, providing an algorithm, and proves a matching lower bound. In a sense, this paper solves the problem of online probabilistic multiclass predictions with U-calibration error.\n- The mathematical development is sound and rigorous.", "weaknesses": "No outstanding weakness. Typos and questions are given under questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your comments and evaluation of the manuscript. Your questions are addressed below:\n\n>L25: Based on the regret definition, it seems the it can be negative because the best prediction in hindsight is fixed for all time steps? For example, an oracle $p = \\text{arg}\\min_p\\sum_{t = 1} ^ {T} \\ell(p, y_{t})$ achieves 0 regret, and an oracle $p_{t} = y_{t}$ for all $t$ has negative regret.\n\nYes, you are correct. The regret can potentially be negative (which is true for most online learning problems), but that only happens when the adversary is very weak.\n\n>L124: is the condition \"if and only if\"? See the interpretation immediately after Theorem 2 Gneiting and Raftery (2007): \"Phrased slightly differently, a regular scoring rule $S$ is proper if and only if the expected score function $G(p) = S(p,p)$ is convex on $\\mathcal{P}_m$\".\n\nThat’s right. The condition is “if and only if”. Although line 124 conveys one direction, the subsequent lines (125, 126) combined with 124 convey the “if and only if” part.\n\n>In Section 3.1, would it be nice to accompany the algorithm description and theoretical guarantees by some intuition why this randomized algorithm works? For readers not familiar with FTPL, a naive forecast would be to just predict the class frequency $\\beta$ up to the current time step. Why is it worse than FTPL and what is the intuition behind the randomization in the algorithm?\n\nThe naive forecast you mentioned is exactly FTL, which we show suffers linear regret for a certain V-shaped loss in Theorem 6. From its proof, one can see that the intuition is that FTL is unstable in the sense that $\\ell(p_t, y_t) - \\ell(p_{t+1}, y_t)$ can be as bad as $\\Omega(1)$. On the other hand, by introducing randomness, FTPL stabilizes the algorithm and avoids this issue.\n\n>In Section 3.1, is it better to use the notation system established in previous sections to translate the FTPL algorithm in Daskalakis and Syrgkanis (2016)? For example, I think both are fine, just curious which one is more accepted.\n\nWe are not sure what you meant, unfortunately. We have indeed followed the approach of introducing the FTPL algorithm in Daskalaskis and Syrgkanis (2016) using their notations and then mapping the notations to our context. Please let us know what is the other usage of notation that you want to compare this to.\n\n>L181: dose -> does\n\nThank you for pointing out the typo. We shall correct this in the subsequent revisions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XTh8Lp8836", "reviewer": "Reviewer_PchL", "summary": "This paper closes an open problem regarding U calibration, left by Kleinberg et al. (2023). It is shown that a modified version of Kleinberg et al's algorithm recovers a classical FTPL algorithm of Daskalakis and Syrgkanis (2016), which improves the pseudo U calibration error in Kleinberg et al (2023) from $O(K\\sqrt{T})$ to the optimal rate $O(\\sqrt{KT})$. Then, the paper considers several special classes of proper losses, and shows that FTL guarantees $O(\\log T)$ U calibration error. Finally, it is shown that although FTL works in such special cases, FTPL is necessary in general.", "questions": "The follow up questions I'm interested in are already discussed by the authors as future directions. The discussed directions there make sense.", "limitations": "Societal impact not applicable due to the theoretical nature.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is a very solid and comprehensive contribution to the theory of U calibration. It answers an open problem left from an already amazing prior work, and complements the existing generic theory by several interesting special cases. Although the proposed algorithm is a small modification from Kleinberg et al. (2023), the established equivalence to the classical results of Daskalakis and Syrgkanis is novel. The intuition and the analysis are both quite natural. Various extensions are thoroughly analyzed, and the presentation is exceptionally clear.", "weaknesses": "This is one of the rare cases where finding a weakness is hard. One thing I might say is the lack of operational impact. Although U calibration is a relatively new framework, the intuition of the proper losses and the fact that FTL & FTPL work well somewhat suggest that it is more of a new way to look at existing online learning algorithms, rather than a new framework to design different online learning algorithms. This will arguably limit the impact of such results in the broader ML community, which is my reason for not giving the paper an even higher score. \n\nHowever, I would say such practical limitation is quite common in recent learning theory papers. Based on the technical quality, this paper is still a very good contribution to learning theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your comments and evaluation of the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uzxPq9Z1G3", "reviewer": "Reviewer_Uz2D", "summary": "This paper studies the calibrating for multiclass distribution forecasting while considering all proper functions simultaneously and contributes minimax optimal errors for a variety of settings.", "questions": "Major Questions:\n- Page 2 Line 42: isn't p from a continuum, how is a sum over p defined?\n- Page 5 Line 208: how is (a) claimed? Explain.\n\nMinor Questions:\n- Page 2 Line 39: what do you insert instead of dropped notations?\n- Page 8 Line 322: why 2K?\n\nSuggestions:\n- Page 6 Line 228: check grammar.\n- Page 7 Line 280: missing comma.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: \nThe work is a novel combination of known techniques, especially Kleinberg et al. (2023). \nIt is clarified how this work differs from previous contributions. \nThe related work is somewhat adequately cited. \n\nQuality: \nThe submission technically sound. \nThe claims are generally well supported by theoretical analysis. \nThe methods used are appropriate. \nThis is a complete piece of work answering a recent open problem. \nThe authors are more or less careful and honest about evaluating their work, and placing it in the literature. \n\nClarity: \nThe submission is clearly written and well organized. \n\nSignificance: \nThe results are important in the sense that it conclusively generates optimal approaches for a multitude of scenarios. \nOther researchers and practitioners are likely to use the ideas and build on them, as this work did, possibly for integration into machine learning applications. \nIt advances the state of the art in a demonstrable way through theoretical analysis, performance bounds and open problem answers. \nIt provides unique conclusions about existing methods and some unique theoretical approaches.", "weaknesses": "Originality: \nThe tasks or methods do not really stand out as new, more emphasis what the work introduces would help. \n\nClarity: \nIt is a bit lacking at times in adequately informing the reader regarding the contents, especially towards the end (pages 8 and 9). \n\nSignificance:\nThe difficulty of the task the submission addresses (demonstrably in a better way than the previous works) is questionable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your comments and evaluation of the manuscript. Regarding the weakness in originality and significance, we would like to highlight that our Theorem 4, an $\\Omega(\\log T)$ lower bound for any algorithm when learning with the squared loss, is the most technical part of our manuscript and requires substantially new ideas. As we point out after Theorem 4, while squared loss is known to admit $\\Theta(\\log T)$ regret in other online learning problems such as that from Abernethy et al. (2008), as far as we know there is no study on our setting where the decision set is the simplex and the adversary has only finite choices. We believe that this result is particularly original and significant.\n\nYour other questions are addressed below:\n\n**Major Questions:**\n> Page 2 Line 42: isn't p from a continuum, how is a sum over p defined?\n\nNote that even though $p$ is from a continuum, there are at most $T$ non-zero summands in this summation since there are at most $T$ different forecasts ($p_{t}$). This is why the notation $\\sum_{p\\in \\Delta_K}$ is well defined and in fact standard in the calibration literature.\n\n> Page 5 Line 208: how is (a) claimed? Explain.\n\nThe exact reasoning can be found in Lines 474-481, but the intuitive explanation is simply that by the properness of the V-shaped loss, it is straightforward to see that predicting a uniform distribution at each time $t$ is in expectation the optimal choice for the learner in this environment (where the outcome is also uniform over $\\{e_1, \\ldots, e_K\\}$), and this optimal strategy has exactly 0 loss.\n\n**Minor Questions:**\n\n> Page 2 Line 39: what do you insert instead of dropped notations?\n\nAs we mention in Lines 38 and 39, whenever the subscript is dropped, both UCal and PUCal are to be thought of with respect to the class of all proper losses, for which we use the notation $\\mathcal{L}$. Whenever a different subscript $\\mathcal{L}’$ appears, both quantities are defined with respect to that specific class of losses, which would be clear from the context.\n\n> Page 8 Line 322: why $2K$?\n\nAt every time when a new label is chosen by the adversary, we bound the regret trivially by $2$ since $\\ell$ is bounded in $[-1, 1]$. Since the number of distinct labels is $K$, this contributes at most $2K$ to the overall regret.\n\n**Suggestions**: Thank you for the suggestions. We shall do the needful in the subsequent revisions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rTeL96Otwc", "reviewer": "Reviewer_jtgy", "summary": "This paper studies online forecasting algorithms for achieving multiclass U-calibration. In the standard setting of online forecasting, a forecaster must produce a prediction p_t each day for an event with K possible outcomes (p_t is a distribution over K outcomes). The event then occurs (with outcome x_t), and the forecaster must suffer some loss L(p_t, x_t). The forecaster wants to minimize their total loss over all T rounds (or alternatively, their regret compared to the best fixed prediction in hindsight).\n\nTraditionally, L is chosen to be a specific proper scoring rule (e.g., the quadratic loss). But you may wish to produce predictions that are good for any proper scoring rule L (and hence that induce low regret for any downstream agent). The U-calibration error (introduced by Kleinberg et al. in an earlier paper) is the maximum regret of the forecaster with respect to some bounded proper scoring rule. Kleinberg et al. constructed a randomized online forecaster that achieves O(K * sqrt(T)) U-calibration error for the K outcome case and posed an open question of whether this is tight.\n\nThis paper does the following:\n1. They provide an algorithm that achieves O(sqrt(KT)) U-calibration error, and proves that this is tight (in fact, that there is a single proper scoring rule where any forecaster must incur Omega(sqrt(KT)) regret).\n2. They then show that there are specific subclasses of loss functions where it is possible to get much stronger U-calibration bounds (for the modified definition of U-calibration only looking at these losses). E.g, for Lipschitz-bounded proper scoring rules and decomposable proper scoring rules, it is possible to get O(log T) U-calibration bounds. Also worth noting is that these bounds hold for a slightly stronger form of U-calibration (the previous bounds mentioned are all for “pseudo U-calibration”, whereas these are for actual U-calibration, the difference being swapping the order of taking the max over loss functions and taking the expectation over the algorithm’s randomness). \n\nKleinberg et al.’s randomized forecaster is based on a modification of follow-the-perturbed-leader to the forecasting setting. The optimal O(sqrt(KT)) algorithm presented in this paper also builds off this FTPL approach, but uses a different perturbation distribution (geometric instead of uniform) to achieve sqrt(K). The stronger bounds follow from showing that the deterministic Follow-The-Leader algorithm works for these subclasses of losses.", "questions": "No specific questions, feel free to reply to anything in the review.", "limitations": "Authors have adequately addressed limitations.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Evaluation:\n\nMulticlass prediction is an important problem where you often want guarantees for downstream agents. The standard solution to this -- calibration -- is notoriously hard to achieve in multiclass settings (e.g., in the online setting calibration bounds for d-dimensional outcomes often scale as O(T^{1 - 1/(d+2)}), so it is important to understand alternate guarantees (such as U-calibration) which are tractable but guarantee the same outcome. This paper almost entirely resolves a very natural open problem about U-calibration understanding the optimal U-calibration rates for multiclass calibration (the only thing left open really being a somewhat technical distinction of what is possible for “pseudo-U-calibration” vs “U-calibration”). As such, I found this paper very interesting and would expect it to be of interest to many NeurIPS attendees interested in online learning and/or calibration.\n\nOne possible criticism of this paper is that it doesn’t do too much that it is entirely novel from a technical perspective -- e.g., the main result follows from an observation that an FTPL variant analyzed by Daskalakis and Syrgkanis in 2016 can be immediately applied to the FTPL forecaster introduced by Kleinberg et al. to get the O(sqrt(KT)) calibration result. But personally I think that this is a very nice observation (and it is actually nice that the result is so simple). Similarly, it is not too surprising that FTL is good for some subclass of losses (as FTL is known to get logarithmic regret for e.g. strongly convex OCO), but I also think this is a very nice observation to point out.", "weaknesses": "See previous section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your comments and evaluation of the manuscript. About your comment on the technical perspective, we would like to highlight a result that seems to be overlooked by the reviewer (since it is not mentioned in the summary of the review): our Theorem 4, an $\\Omega(\\log T)$ lower bound for any algorithm when learning with the squared loss, is the most technical part of our manuscript and requires substantially new ideas. As we point out after Theorem 4, while squared loss is known to admit $\\Theta(\\log T)$ regret in other online learning problems such as that from Abernethy et al. (2008), as far as we know there is no study on our setting where the decision set is the simplex and the adversary has only finite choices. We believe that this result is particularly original and significant.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the recently developed setting of multiclass U-Calibration (which is a metric that is weaker in some sense than the classical calibration metric, but still has many implications of interest in forecasting, prediction and decision making, and can be achieved at a faster rate in $$T$$ than calibration), and provides the optimal rate in the number of classes $$K$$ through a novel connection to the FTPL algorithm of Daskalakis and Syrgkanis (2016) for the upper bound along with a matching lower bound. Adaptive, faster rates are also provided for special cases (Lipschitz proper losses, decomposable proper losses, low covering number, etc.). All the reviewers are very enthusiastic about this contribution, and I wholeheartedly share their opinion -- this is an important problem that is solved through a remarkably simple connection.
Decision: Accept (poster)