Optimal Multiclass U-Calibration Error and Beyond

Authors: haipeng  luo
spandan  senapati
vatsal  sharan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:37:22

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.

Main paper: 
 introduction: 
 We consider the fundamental problem of making sequential probabilistic predictions over an outcome (e.g., predicting the probability of tomorrow's weather being sunny, cloudy, or rainy). Specifically, at each time t = 1, . . . , T , a forecaster/learner predicts p t ∈ ∆ K , where ∆ K denotes the probability simplex over K outcomes. At the same time, an adversary decides the true outcome, encoded by a one-hot vector y t ∈ E := {e 1 , . . . , e K }, where e i denotes the i-th standard basis vector of R K . The forecaster observes y t at the end of time t.A 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 ℓ : ∆ K × E → R, the regret of the forecaster's predictions with respect to ℓ is defined as REG ℓ := T t=1 ℓ(p t , y t )-inf p∈∆ K T t=1 ℓ(p, y t ). Perhaps the most common class of loss functions to evaluate a forecaster are proper loss functions. A loss function is proper if E y∼p [ℓ(p, y) ] ≤ E y∼p [ℓ(p ′ , y)] for all p, p ′ ∈ ∆ K . 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.Note, however, that regret is measured with respect to a specific loss function ℓ. It is unclear which proper loss one should minimize over for the specific application at hand -and there could even be multiple applications with different loss functions which use the forecasters'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 L := E [sup ℓ∈L REG ℓ ] (and a weaker version pseudo U-calibration error PUCal L := sup ℓ∈L E[REG ℓ ]) for a 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 [-1, 1]) proper losses (as in Kleinberg et al. (2023) ), and drop the subscript in UCal L and PUCal L for convenience.The simplest way to get low U-calibration error is via the classical notion of low calibration error (Dawid, 1982) , defined as Cal := p∈∆ K ∥ t;pt=p (p -y t )∥ 1 . Intuitively, a forecaster with low calibration error guarantees that whenever she makes a 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 O(T K K+1 ) (Blum et al., 2008) , and there is a Ω(T 0.528 ) lower bound (for K = 2) (Qiao and Valiant, 2021) . Therefore, a natural question to ask is 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 = O( √ T ) for K = 2 and PUCal = O(K √ T ) for general K. This provides a strong decision-theoretic motivation for considering U-calibration error as opposed to calibration error; we refer the reader to Kleinberg et al. (2023) for further discussion.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 to 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.First, we show that the minimax optimal value of PUCal is Θ( √ KT ):• In Section 3.1, we start by showing that a simple modification to the noise distribution of the Follow-the-Perturbed-Leader (FTPL) algorithm of Kleinberg et al. (2023) improves their PUCal = O(K √ T ) bound to O( √ KT ). In fact, our algorithm coincides with that of Daskalakis and Syrgkanis (2016) designed for an online learning setting with a 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 (1)).• We then show in Section 3.2 that there exists one particular proper loss ℓ such that any algorithm has to suffer REG ℓ = Ω( √ KT ) in the worst case, hence implying PUCal = Ω( √ KT ). While our proof follows a standard randomized argument, the novelty lies in the construction of the proper loss and the use of an anti-concentration inequality 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 UCal L ′ 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.1, we show that for the class L G of G-Lipschitz bounded proper losses (which includes standard losses such as the squared loss and spherical loss), FTL ensuresPUCal L G = UCal L G = O(G log T ).We further show that all algorithms must suffer PUCal L G = Ω(log T ). While we prove this lower bound using the standard squared loss that is known to admit Θ(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 is 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 a class L dec of losses that are decomposable over the K outcomes and additionally satisfy some mild regularity conditions, and show that FTL again achieves PUCal = UCal = O(log T ) (ignoring other dependence). This class includes losses induced by a 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 a controlled rate.• Given these positive results on FTL, one might wonder whether FTL is generally a 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 if one cares about all proper losses (or at least losses not in L G or L dec ).For calibration, Foster and Vohra (1998) proposed the first algorithm for the binary setting with an (expected) O(T3 ) calibration error (see also Blum and Mansour (2007) and Hart (2022) for a different proof of the result). In the multiclass setting, Blum et al. (2008) have shown an O(T K K+1 ) calibration error. Several works have studied other variants of calibration error, such as the most recently proposed Distance to Calibration (Błasiok 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 simultaneous loss minimization, also known as omniprediction. Garg et al. (2024) study an online adversarial version of it, and U-calibration can be seen as a 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 a 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; Błasiok et al., 2024; Gopalan et al., 2023a,b) . 
preliminaries: 
 Notation: We use lowercase bold alphabets to denote vectors. N, N ≥0 denote the set of positive, non-negative integers respectively. For any m ∈ N, [m] denotes the index set {1, . . . , m}. We use∆ K to denote the (K -1)-dimensional simplex, i.e., ∆ K := {p ∈ R K | p i ≥ 0, K i=1 p i = 1}. The i-th standard basis vector (dimension inferred from the context) is denoted by e i , and we use E to represent the set {e 1 , . . . , e K } of all basis vectors of R K . By default, ∥•∥ denotes the ℓ 2 norm.Proper Losses: Throughout the paper, we consider the class of bounded proper lossesL := {ℓ : ∆ K × E → [-1, 1] | ℓ isproper} or a 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,E y∼p [ℓ(p, y)] ≤ E y∼p [ℓ(p ′ , y)] for all p, p ′ ∈ ∆ K .For a proper loss ℓ, we refer to ℓ(p, y) as its bivariate form. The univariate form of ℓ is defined as ℓ(p) := E y∼p [ℓ(p, y) ]. It turns out that a loss is proper only if its univariate form is concave. Moreover, one can construct a proper loss using a concave univariate form based on the following characterization lemma.Lemma 1 (Theorem 2 of Gneiting and Raftery (2007) ). A loss ℓ : ∆ K × E → R is proper if and only if there exists a concave function f such that ℓ(p, y) = f (p) + ⟨g p , y -p⟩ for all p ∈ ∆ K , y ∈ E, where g p denotes a subgradient of f at p. Also, f is the univariate form of ℓ.• The spherical loss is ℓ(p, y) = -⟨p,y⟩ ∥p∥ , which is√ K-Lipschitz (Proposition B.1) but non-convex in p. Its univariate form is ℓ(p) = -∥p∥.• The squared loss (also known as the Brier score) is ℓ(p, y) = 1 2 ∥p -y∥ 2 , which is clearly 2-Lipschitz and convex in p. Its univariate form is ℓ(p) = 1 -∥p∥ 2 .• Generalizing the squared loss, we consider the univariate form ℓ(p) = -c K K i=1 p α i for α > 1 and some constant cK > 0, which is the Tsallis entropy and is concave. The induced proper loss is ℓ(p, y) = cK (α -1)K i=1 p α i -cK α K i=1 p α-1 i y i , which is not Lipschitz for α ∈ (1, 2). *The following fact is critical for U-calibration: for any n ∈ N and a sequence of outcomes y 1 , . . . , y n ∈ 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):EQUATIONProblem Setting: As mentioned, the problem we study follows the following protocol: at each time t = 1, . . . , T , a forecaster predicts a distribution p t ∈ ∆ K over K possible outcomes, and at the same time, an adversary decides the true outcome encoded by a one-hot vector y t ∈ E, which is revealed to the forecaster at the end of time t.For a fixed proper loss function ℓ, the regret of the forecaster is defined as: REG ℓ := T t=1 ℓ(p t , y t )inf p∈∆ K T t=1 ℓ(p, y t ), which, according to property (1), can be written as T t=1 ℓ(p t , y t ) -T t=1 ℓ(β, y t ) where β := 1 T T t=1 y t is simply the empirical average of all outcomes. Our goal is to ensure low regret against a class of proper losses simultaneously. We define Ucalibration error as UCal L = E [sup ℓ∈L REG ℓ ] and pseudo U-calibration error as PUCal L = sup ℓ∈L E[REG ℓ ] for a 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.As is standard in online learning, an oblivious adversary decides all outcomes y 1 , . . . , y T ahead of the time with the knowledge of the forecaster's algorithm (but not her random seeds), while an adaptive adversary decides each y t with the knowledge of past forecasts p 1 , . . . , p t-1 . Except for one result (upper bound on UCal for a class with lowcovering 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).Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Refer to Sections 1 and 5. 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-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.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
optimal u-calibration error: 
 In this section, we prove that the minimax optimal pseudo U-calibration error is Θ( √ KT ).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 t ∈ [T ], a learner chooses an action a t ∈ A for some action set A; at the same time, an adversary selects an outcome θ t from a finite set Θ := { θ1 , . . . , θK } of size K; finally, the learner observes θ t and incurs loss h(a t , θ t ) 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 t, randomly generate a set of hallucinated outcomes, where the number of each possible outcome θi for i ∈ [K] follows independently a geometric distribution with parameter K/T , and then output the empirical risk minimizer using both the true outcomes and the hallucinated outcomes as the final Theorem 1 (Appendix F.3 of Daskalakis and Syrgkanis (2016) ). The FTPL algorithm described above satisfies the following regret bound:E T t=1 h(a t , θ t ) -inf a∈A T t=1 h(a, θ t ) ≤ 4 √KT , where the expectation is taken over the randomness of both the algorithm and the adversary. Now we are ready to discuss how to apply their algorithm to our multiclass U-calibration problem. Naturally, we take A = ∆ K and Θ = 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,p t,i = Y t,i / K k=1 Y t,k ) is a solution of argmin p∈∆ K K i=1 Y t,i h(p, e i )for any proper loss h ∈ L! This immediately leads to the following result.Corollary 1. Algorithm 1 ensures PUCal ≤ 4 √ KT against any adaptive adversary.We remark that the only difference of Algorithm 1 compared to that of Kleinberg et al. (2023) is that m t,i is sampled from a geometric distribution instead of a uniform distribution in {0, 1, . . . , ⌊ √ T ⌋}. 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 fromO(K √ T ) to O( √ KT ).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 = Ω(K).Theorem 2. There exists a proper loss ℓ with range [-1, 1] such that the following holds: for any online algorithm ALG, there exists a choice of y 1 , . . . , y T by an oblivious adversary such that the expected regretE[REG ℓ ] of ALG is Ω( √ KT ) when T ≥ 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 ℓ(p) = -1 2 K i=1 p i -1 K , which is in fact a direct generalization of the so-called "V-shaped loss" studied in Kleinberg et 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 to 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 = O( √ KT ).With this loss function, we then follow a standard probabilistic argument and consider a randomized oblivious adversary that samples y 1 , . . . , y T i.i.d. from the uniform distribution over E. For such an adversary, we argue the following: (a) the expected loss incurred by ALG is non-negative, i.e., E T t=1 ℓ(p t , y t ) ≥ 0, where the expectation is taken over y 1 , . . . , y T and any internal randomness in ALG; (b) the expected loss incurred by the benchmark is bounded asE inf p∈∆ K T t=1 ℓ(p, y t ) ≤ -c√ KT for some universal positive constant c, where the expectation is over y 1 , . . . , y T . Together, this implies that the expected regret of ALG is at least c √ KT in this randomized environment, which further implies that there must exist one particular sequence of y 1 , . . . , y T such that the expected regret of ALG is at least c √ KT , 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 Theorem 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 is unknown before.Second, since PUCal = sup ℓ E[REG ℓ ] ≥ E[REG ℓ ′ ] for any ℓ ′ ∈ L, Theorem 2 immediately implies a Ω( √ KT) lower bound on the pseudo multiclass U-calibration error. In fact, since UCal ≥ PUCal, the same lower bound holds for the actual U-calibration error. Corollary 2. For any online forecasting algorithm, there exists an oblivious adversary such that UCal ≥ PUCal = Ω( √ KT ).We now make an attempt to bound the U-calibration error UCal of Algorithm 1 for an oblivious adversary. Specifically, since the perturbations are sampled every round and the adversary is oblivious, using Hoeffding's inequality it is straightforward to show that for a fixed ℓ and a fixed δ ∈ (0, 1), the regret of Algorithm 1 with respect to ℓ satisfies REG ℓ ≤ 4 √ KT + 2T log ( 1 /δ) with probability at least 1 -δ (see Hutter et al. (2005, Section 9) or Lemma D.1). Therefore, for a finite subset L ′ of L, taking a union bound over all ℓ ∈ L ′ gives sup ℓ∈L ′ REG ℓ ≤ 4 √ KT + 2T log ( |L ′ | /δ) with probability at least 1 -δ. Picking δ = 1/T and using the boundedness of losses, we obtainUCal L ′ ≤ 2 + 4 √ KT + 2T log (T |L ′ |).In Appendix D, we generalize this simple argument to any infinite subset L ′ of L with a finite ϵ-covering number M (L ′ , ϵ; ∥.∥ ∞ ) and prove for any ϵ > 0,EQUATIONUsing this bound, we now give a concrete example of a simple parameterized familyL ′ ⊂ L for which UCal L ′ = O( √ KT + √ T log T ).Consider the parameterized classL ′ = {αℓ 1 (p, y) + (1 -α)ℓ 2 (p, y)|α ∈ [0, 1]},where ℓ 1 (p, y), ℓ 2 (p, y) ∈ L are two fixed bounded and proper losses. It is straightforward to verify that ℓ α (p, y) := αℓ 1 (p, y) + (1 -α)ℓ 2 (p, y) ∈ L, therefore L ′ ⊂ L.To obtain an ϵ ∈ (0, 1) cover for L ′ , we consider the set C := {0, ϵ, . . . , 1 -ϵ, 1} which partitions the interval [0, 1] to 1 ϵ smaller intervals each of length ϵ. For each α ∈ [0, 1], let c α ∈ C denote the closest point to α (break ties arbitrarily). Clearly, |α -c α | ≤ ϵ. Next, consider the functiong α (p, y) := c α ℓ 1 (p, y) + (1 -c α )ℓ 2 (p, y). The class {g α (p, y)|α ∈ [0, 1]} is clearly a 2ϵ cover of L ′ with size 1 ϵ . Thus, M (L ′ , ϵ; ∥.∥ ∞ ) = O( 1 ϵ ). It then follows from (2) that UCal L ′ = O ϵT + √ KT + T log T ϵ = O √ KT + T log T on choosing ϵ = 1 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, UCal L ′ = Ω(T )).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 are clearly specified, and each lemma/theorem has a proof which can be found in 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to 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. 
improved bounds for important sub-classes: 
 In this section, we show that it is possible to go beyond the Θ( √ KT ) U-calibration error for several broad sub-classes of L that include important and common proper losses. These results are achieved by an extremely simple algorithm called Follow-the-Leader (FTL), which at time t > 1 forecasts *EQUATIONthat is, the average of the past outcomes. For notational convenience, we define n t = t s=1 y s so that FTL predicts p t = nt-1 t-1 , with n t-1,i being the count of outcome i 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 an oblivious adversary and an adaptive adversary because of this deterministic nature.In this section, we show that Θ(log T ) is the minimax optimal bound for PUCal and UCal for Lipschitz proper losses. Specifically, we consider the following class of G-Lipschitz proper lossesL G := {ℓ ∈ L | |ℓ(p, y) -ℓ(p ′ , y)| ≤ G ∥p -p ′ ∥ , ∀p, p ′ ∈ ∆ K , y ∈ E} .As discussed in Section 2, the two common proper losses, squared loss and spherical loss, are both in L G for some G. Note that the class of L G is rich since according to Lemma 1 it corresponds to 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 to L G .Theorem 3. The regret of FTL for learning any ℓ ∈ L G is at most 2 + 2G log T . Consequently, FTL ensures PUCal L G = UCal L G = O(G log T ).Proof. Using the standard Be-the-Leader lemma (see e.g., (Orabona, 2019, Lemma 1.2 )) that saysT t=1 ℓ(p t+1 , y t ) ≤ inf p∈∆ K T t=1 ℓ(p, y t ), the regret of FTL can be bounded as REG ℓ ≤ 2 + T t=2 ℓ(p t , y t ) -ℓ(p t+1 , y t ) ≤ 2 + G T t=2 ∥p t -p t+1 ∥ ,where the second inequality is because ℓ ∈ L G . Next, since p t = nt-1 t-1 and p t+1 = nt t , we obtainREG ℓ ≤ 2 + G T t=2 n t-1 t -1 - n t t = 2 + G T t=2 n t-1 t(t -1) - y t t ≤ 2 + 2G T t=2 1 t ,where the equality follows since n t = n t-1 + y t and the last inequality follows from the triangle inequality and ∥n t-1 ∥ ≤ ∥n t-1 ∥ 1 = t -1. Finally, sinceT t=2 1 t ≤ T 1 1 z dz = log T , we obtain REG ℓ ≤ 2 + 2G log T , which completes the proof.A closer look at the proof reveals that global Lipschitzness over the entire simplex ∆ K is in fact not necessary. This is because, for example, in the term ℓ(p t , e i ) -ℓ(p t+1 , e i ) for some i ∈ [K], by the definition of FTL the corresponding coordinates p t,i and p t+1,i are almost always at least 1/T , with only one exception which is when t is the first time we have y t = e i and which we can ignore since the regret incurred is at most a constant. This means that having local Lipschitzness in a certain region is enough; see Lemma E.1 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 Ω(log T ) for one particular Lipschitz proper loss, making FTL minimax optimal for this class.Theorem 4. There exists a proper Lipschitz loss ℓ such that: for any algorithm ALG, there exists a choice of y 1 , . . . , y T by an oblivious adversary such that the expected regret of ALG is Ω(log T ).The loss we use in this lower bound is simply the squared loss ℓ(p, y) = ∥p -y∥ 2 with K = 2. While squared loss is known to admit Θ(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. It turns out that this variation brings significant technical challenges, and our proof is substantially different from that of Abernethy et al. (2008) . We defer the details to Appendix F and discuss the key steps below.Step 1: Since squared loss is convex in p, by standard arguments it suffices to consider deterministic algorithms only (see Lemma F.1). Moreover, for deterministic algorithms, there is no difference between an oblivious adversary and an adaptive adversary so that the minimax regret can be written asVAL = inf p1∈∆ K sup y1∈E • • • inf p T ∈∆ K sup y T ∈E T t=1 ℓ(p t , y t ) -inf p∈∆ K T t=1 ℓ(p, y t ) .To solve this, further define V n,r recursively asV n,r = inf p∈∆ K sup y∈E V n+y,r-1 + ℓ(p, y) with V n,0 = -inf p∈∆ K K i=1 n i ℓ(p, e i ), so that VAL is simply V 0,T .Step 2: Using the minimax theorem, we further show that V n,r = sup q∈∆ K K i=1 q i V n+ei,r-1 + ℓ(q) where the univariate form ℓ(q) is 1 -∥q∥ 2 (as mentioned in Section 2). Recall that we consider only the binary case K = 2, so it is straightforward to give an analytical form of the solution to the maximization over q ∈ ∆ K . Specifically, writing V n,r = V (n1,n2),r as V n1,n2,r to make notation concise, we showV n1,n2,r =      V 2 if V 1 -V 2 < -2, (V1-V2) 2 8 + V1+V2 2 + 1 2 if -2 ≤ V 1 -V 2 ≤ 2, V 1 if V 1 -V 2 > 2,where V 1 and V 2 are shorthands for V n1+1,n2,r-1 and V n1,n2+1,r-1 respectively. Next, by an induction on r we show that for all valid n 1 , n 2 , r it holds that-2 ≤ V 1 -V 2 ≤ 2 (Lemma F.2), therefore V n1,n2,r is always equal to (V1-V2) 2 8 + V1+V2 2 + 1 2 .Step 3: By an induction on r again, we show that V n1,n2,r exhibits a special structure of the formV n1,n2,r = (n 1 -n 2 ) 2 2 • u r - 2n 1 n 2 T + v r ,where {u r } T r=0 and {v r } T r=0 are recursively defined viau r+1 = u r + u r + 1 T 2 and v r+1 = ur 2 + v r + r+1 T -1 2 with u 0 = v 0 = 0 (Lemma F.3). Since VAL = V 0,0,T = v T , it remains to show v T = Ω(log T ), which is done via two technical lemmas F.4 and F.5.Next, we consider another sub-class of proper losses that are not necessarily Lipschitz. Instead, their univariate form is decomposable over the K outcomes and additionally satisfies a mild regularity condition. Specifically, we define the following classL dec := ℓ ∈ L ℓ(p) ∝ K i=1 ℓ i (p i )where each ℓ i is twice continuously differentiable in (0, 1) .Both the squared loss and its generalization via Tsallis entropy discussed in Section 2 are clearly in this class L dec , with the latter being non-Lipschitz when α ∈ (1, 2). The spherical loss, however, is not decomposable and thus not in L dec . We now show that FTL achieves logarithmic regret against any ℓ ∈ L dec (see Appendix G for the full proof). Theorem 5. The regret of FTL for learning any ℓ ∈ L dec is at most 2K + (K + 1)β ℓ (1 + log T ) for some universal constant β ℓ which only depends on ℓ and K. Consequently, FTL ensures PUCal Ldec = UCal Ldec = O((sup ℓ∈Ldec β ℓ )K log T ).Proof Sketch. We start by showing a certain controlled growth rate of the second derivative of the univariate form (see Appendix H for the proof).Lemma 2. For a function f that is concave, Lipschitz, and bounded over [0, 1] and twice continuously differentiable over (0, 1), there exists a constant c > 0 such that |f ′′ (p)| ≤ c • max 1 p , 1 1-p for all p ∈ (0, 1).Note that according to Lemma 1, each ℓ i must be concave, Lipschitz, and bounded, for the induced loss to be proper and bounded. Therefore, using Lemma 2, there exists a constant c i > 0 such that|ℓ ′′ i (p)| ≤ c i max 1 p , 1 1-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 differentiability condition with this (weaker) property. More specifically, for each i ∈ [K], let T i := {t i,1 , . . . , t i,ki } ⊂ [T ] be the subset of 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, we obtainREG ℓ ≤ 2K + K i=1 t∈Ti\{ti,1} ℓ(p t , e i ) -ℓ(p t+1 , e i ) δt,i.By using the characterization result in Lemma 1, we then express ℓ(p t , e i ) and ℓ(p t+1 , e i ) in terms of the univariate forms ℓ(p t ), ℓ(p t+1 ), and their respective gradients ∇ℓ(p t ), ∇ℓ(p t+1 ). Next, using the concavity of ℓ i , the Mean Value Theorem, and Lemma 2, we argue thatEQUATIONfor some ξ t that is a convex combination of p t and p t+1 , and constantβ ℓ,i = cK • c i (c K is the scaling constant such that ℓ(p) = cK K i=1 ℓ i (p i )).To bound (4), we consider the terms|pt+1,j -pt,j | ξt,j and |pt+1,j -pt,j | 1-ξt,jindividually and find that they are always bounded by either 1 nt-1,i or 1 t-1 according to the update rule of FTL. Thus, we obtainREG ℓ ≤ 2K + β ℓ (S 1 + S 2 ), where S 1 = K i=1 t∈Ti\{ti,1} 1 n t-1,i , S 2 = K i=1 t∈Ti\{ti,1} 1 t -1 ,andβ ℓ = K i=1 β ℓ,i .Finally, direct calculation shows S 1 ≤ K(1 + log T ) and S 2 ≤ 1 + log T , which finishes the proof.To showcase the usefulness of this result, we go back to the Tsallis entropy example.Corollary 3. For any loss ℓ with univariate form ℓ(p) = -c K K i=1 p α i for α ∈ (1, 2) (the constant cK is such that the loss has range [-1, 1]), FTL ensures REG ℓ = O(c K α(α -1)K 2 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 c in Lemma 2 to be α(α -1), and thus the regret of FTL is O(Kβ ℓ log T ) with β ℓ = Kc K α(α -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 a regret bound of order O(K + cK α(α -1)T 2-α log T ), which is much worse (especially for small α). Finally, we remark that for α ≥ 2, the bivariate form is Lipschitz, and thus FTL also ensures logarithmic regret according to Theorem 3.Despite yielding improved regret for Lipschitz and other special classes of proper losses, unfortunately, FTL is not a good algorithm in general when dealing with proper losses, as shown below. Theorem 6. There exists a proper loss ℓ and a choice of y 1 , . . . , y T by an oblivious adversary such that the regret REG ℓ of FTL is Ω(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 Ω( √ KT ) 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ℓ(p) = -1 2 p 1 -1 2 + p 2 -1 2 .Using Lemma 1, we obtain the following bivariate form:ℓ(p, e 1 ) = - 1 2 sign p 1 - 1 2 , ℓ(p, e 2 ) = - 1 2 sign p 2 - 1 2 ,where the sign function is defined as sign(x) = 1 if x > 0; -1 if x < 0; 0 if x = 0. Therefore, ℓ(p, e 1 ) is equal to 1 2 if p 1 < 1 2 ; 0 if p 1 = 1 2 ; -1 2 if p 1 ≥ 1 2 . Similarly, ℓ(p, e 2 ) is equal to -1 2 if p 1 ≤ 1 2 ; 0 if p 1 = 1 2 ; 1 2 if p 1 ≥ 1 2 .Let T be even and y t = e 1 if t is odd, and e 2 otherwise. For such a sequence y 1 , . . . , y T , the benchmark selects β = 1 T T t=1 y t = [ 1 2 , 1 2 ] and incurs 0 cost. On the other hand, FTL chooses p t = [ 1 2 , 1 2 ] when t is odd, andp t = t 2(t-1) , t-2 2(t-1) otherwise. Thus, the regret of FTL is REG ℓ = T t=2 ℓ(p t , e 2 ) = T4 . This completes the proof.Consider the parametrized class in subsection 3.3, let K = 2, ℓ 2 (p, y) correspond to the V-shaped loss in Theorem 6, and consider any ℓ 1 (p, y) ∈ L. It follows from Theorem 6 that REG ℓα = Ω(T ) when α = 0, therefore UCal L ′ = sup α∈[0,1] REG ℓα = Ω(T ), whereas Algorithm 1 ensuresUCal L ′ = O( √ T log T ).Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of 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 are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for 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 to have some path to reproducing or verifying the results. 
conclusion and future directions: 
 In this paper, we give complete answers to various questions regarding the minimax optimal bounds on multiclass U-calibration error, a 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 = O(K √ T ) upper bound and show that the minimax pseudo U-calibration error is Θ( √ KT ), but also further show that logarithmic U-calibration error can be achieved by an 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 to losses that are not 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) .Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: The paper does not have any experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The paper 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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • 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 out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a best faith effort.12. Licenses for existing assets Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the 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 as the institution conducting the review. 
 
 Appendix: Lemma A.1 (Markov's inequality). For a non-negative random variable X, and any a > 0, we haveP(X ≥ a) ≤ E[X]a . Lemma A.2 (Khintchine's inequality). Let ϵ 1 , . . . , ϵ T be i.i.d. Rademacher random variables, i.e.,P(ϵ i = +1) = P(ϵ i = -1) = 1 2 for all i ∈ [T ]. Then, E T i=1 ϵ i x i ≥ 1 √ 2 T i=1 x 2 i 1 2for any x 1 , . . . , x T ∈ R. Lemma A.3 (Hoeffding's inequality). Let X 1 , . . . , X T be independent random variables satisfyinga i ≤ X i ≤ b i for all i ∈ [T ].Then, for any ϵ > 0, we haveP T t=1 X T -E[X t ] ≥ ϵ ≤ exp - 2ϵ 2 T i=1 (b i -a i ) 2, andP T t=1 X T -E[X t ] ≤ -ϵ ≤ exp - 2ϵ 2 T i=1 (b i -a i ) 2 .Lemma A.4 (Reverse Chernoff bounds). (Klein and Young, 1999 , Lemma 5.2) Let X := 1 T T i=1 X i be the average of T i.i.d. Bernoulli random variables X 1 , . . . , X T with E[X i ] = p for all i ∈ [T ]. If ϵ ∈ (0, 1 2 ], p ∈ (0, 1 2 ] are such that ϵ 2 pT ≥ 3, then P( X ≤ (1 -ϵ)p) ≥ exp(-9ϵ 2 pT ), P( X ≥ (1 + ϵ)p) ≥ exp(-9ϵ 2 pT ).Lemma B.1. For a proper loss ℓ(p, y), the following holds true for any n ∈ N and y 1 , . . . , y n ∈ E:1 n n i=1 y i ∈ argmin p∈∆ K 1 n n i=1 ℓ(p, y). Proof. Let β := 1 n n i=1 y i . Since ℓ is proper, E y∼β [ℓ(β, y)] ≤ E y∼β [ℓ(p ′ , y)] for all p ′ ∈ ∆ K . Notably, for any p ∈ ∆ K , we have K i=1 β i ℓ(p, e i ) = 1 n K i=1 n j=1 1 1[y j = e i ]ℓ(p, e i ) = 1 n n j=1 K i=1 1 1[y j = e i ]ℓ(p, e i ) = 1 n n j=1 ℓ(p, y j ).Thus,1 n n j=1 ℓ(β, y j ) ≤ 1 n n j=1 ℓ(p ′ , y j ) for any p ′ ∈ ∆ K . This completes the proof. Lemma B.2. Let ℓ(p) be a differentiable and concave, α-Lipschitz function over ∆ K such that ∇ℓ(p) is β-Lipschitz over ∆ K . Then, ℓ(p, y) is proper and (2α + 2β)-Lipschitz in p ∈ ∆ K for each y ∈ E.Proof. Since ℓ(p) is concave, it follows from Lemma 1 that ℓ(p, y) is proper. To prove the second part, without any loss of generality, assume that y = e 1 . For any p, p ′ ∈ ∆ K , we haveℓ(p, e 1 ) -ℓ(p ′ , e 1 ) = ℓ(p) + ⟨∇ℓ(p), e 1 -p⟩ -(ℓ(p ′ ) + ⟨∇ℓ(p ′ ), e 1 -p ′ ⟩) ≤ α ∥p -p ′ ∥ + ∇ 1 ℓ(p) -∇ 1 ℓ(p ′ ) -(⟨p, ∇ℓ(p)⟩ -⟨p ′ , ∇ℓ(p ′ )⟩) ≤ (α + β) ∥p -p ′ ∥ + ⟨p ′ -p, ∇ℓ(p ′ )⟩ + ⟨p, ∇ℓ(p ′ ) -∇ℓ(p)⟩ ≤ (α + β) ∥p -p ′ ∥ + ∥p ′ -p∥ ∥∇ℓ(p ′ )∥ + ∥p∥ ∥∇ℓ(p ′ ) -∇ℓ(p)∥ ≤ 2(α + β) ∥p -p ′ ∥ ,where the first equality follows from Lemma 1; the first inequality follows from the Lipschitzness of ℓ; the second inequality follows from the Lipschitzness of ∇ℓ(p); the third inequality follows from the Cauchy-Schwartz inequality; the final inequality follows since ∥p∥ ≤ 1 and ∇ℓ(p) is Lipschitz. This completes the proof.Proposition B.1. The spherical loss is √ K-Lipschitz.Proof. We shall show that ∥∇ℓ(p, y)∥ ≤ √ K for all y ∈ E, p ∈ ∆ K , where the gradient is taken with respect to the first argument. Without any loss of generality, assume y = e 1 , thus ℓ(p, y) = -p1 ∥p∥ . It is easy to obtain the following:∂ℓ(p, y) ∂p 1 = - ∥p∥ 2 -p 2 1 ∥p∥ 3 , ∂ℓ(p, y) ∂p i = p 1 p i ∥p∥ 3 for all i > 2.Thus, ∥∇ℓ(p, e 1 )∥ = 1∥p∥ 3 (∥p∥ 2 -p 2 1 ) 2 + p 2 1 K i=2 p 2 i = 1 ∥p∥ 2 (∥p∥ 2 -p 2 1 ) ≤ 1 ∥p∥ ≤ √ K,where the last inequality follows the Cauchy-Schwartz inequality.Theorem 2. There exists a proper loss ℓ with range [-1, 1] such that the following holds: for any online algorithm ALG, there exists a choice of y 1 , . . . , y T by an oblivious adversary such that the expected regretE[REG ℓ ] of ALG is Ω( √ KT ) when T ≥ 12K.Proof. Consider the function defined asℓ(p) := - 1 2 K i=1 p i - 1 K .It follows from Lemma 1 that the bivariate form of ℓ is ℓ(p, y) = ℓ(p) + ⟨g p , p -y⟩, where g p denotes a subgradient of ℓ(p) at p. For the choice of ℓ, g i = -1 2 sign(p i -1 K ), where the sign function is defined as sign(x) = 1 if x > 0; -1 if x < 0; 0 if x = 0. We first show that ℓ(p, y) ∈ [-1, 1].Without any loss of generality, assume y = e 1 . Therefore,ℓ(p, e 1 ) = 1 2 - K i=1 p i - 1 K -(1 -p 1 )sign p 1 - 1 K + K i=2 p i sign p i - 1 K = 1 2 -p 1 - 1 K -(1 -p 1 )sign p 1 - 1 K + K i=2 p i sign p i - 1 K -p i - 1 K = 1 2 -1 - 1 K sign p 1 - 1 K + 1 K K i=2 sign p i - 1 K .It is then trivial to note that p = e 1 corresponds to a minimum, with value ℓ(e 1 , e 1 ) = -K-1 K ; p = [0, 1 K-1 , . . . , 1 K-1 ] corresponds to a maximum, with value K-1 K . Next, we consider a randomized oblivious adversary which samples y 1 , . . . , y T from the uniform distribution over E. For such an adversary, we shall show that E[REG] = Ω( √ KT ). We overload the notation and use ALG 1:t to denote the internal randomness of the algorithm until time t (inclusive). In particular, this notation succintly represents both deterministic and randomized algorithms (p t could be sampled from a distribution D t ). Similarly, ALG t shall denote the randomness at time t.With this notation, in the constructed randomized environment, the expected cost of ALG isE T t=1 ℓ(p t , y t ) = E ALG 1:T ,y1,...,y T T t=1 ℓ(p t , y t ) = T t=1 E ALG 1:T ,y1,...,y T [ℓ(p t , y t )] = T t=1 E ALG1:t-1,y1,...,yt-1 E ALGt,yt [ℓ(p t , y t )|ALG 1:t-1 , y 1 , . . . , y t-1 ] = T t=1 E ALG1:t-1,y1,...,yt-1 E ALGt E yt [ℓ(p t , y t )|ALG 1:t-1 , y 1 , . . . , y t-1 ] = T t=1 E ALG1:t-1,y1,...,yt-1 E ALGt 1 K K i=1 ℓ(p t , e i ) ≥ 0,where in the first equality we 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 t is independent of y t (p t is chosen without knowing y t ) and vice-versa (y t is sampled uniformly randomly from E); the fifth equality follows by expanding out the expectation; the first inequality follows sinceK i=1 ℓ(p, e i ) ≥ 0 for any p ∈ ∆ K . This is because, K i=1 ℓ(p, e i ) = Kℓ(p) + K i=1 ⟨g p , e i -p⟩ = K ℓ(p) + g p , 1 K • 1 K -p ,where 1 K denotes the K-dimensional vector of all ones. Next, since ℓ(p) is concave over ∆ K , the term above can be lower bounded by Kℓ 1 K • 1 K = 0. Next, the expected regret of ALG can be lower bounded in the following manner:EQUATIONwhere the first inequality follows since the expected cost of ALG is non-negative, and the benchmark is independent of ALG; the second equality follows from property 1. In the next steps, we deal with the expectation in (5). Sample y 1 , . . . , y T from E and let n 1 , . . . , n K denote the counts of the K basis vectors, i.e., n i = |{j ∈ [T ]; y j = e i }|. Clearly,K i=1 n i = T . Let n = [n 1 , . . . , n K ] collect these counts. Then, 1 T T t=1 y t = [ n1 T , . . . , n K T ] = 1 T • n, and T t=1 ℓ 1 T T t=1 y t , y t = K i=1 n i ℓ 1 T • n, e i = K i=1 n i ℓ 1 T • n + g 1 T •n , e i - 1 T • n , = T ℓ 1 T • n = - 1 2 K i=1 n i - T K .Thus, the term in (5) equals1 2 • E n1,...,n K K i=1 n i -T Kwhere n 1 , . . . , n K are sampled from a multinomial distribution with event probability equal to 1 K . Further, using the linearity of expectations we arrive atE[REG ℓ ] ≥ 1 2 K i=1 E ni n i - T K = K 2 • E T t=1 X t -E[X t ] ,where X t is a Bernoulli random variable with mean 1 K . Next, we bound E T t=1 X t -E[X t ] using an anti-concentration bound on Bernoulli random variables. In particular, applying Lemma A.4, we obtainP T t=1 X t -E[X t ] ≥ a ≥ 2 exp - 9a 2 K T for any a ∈ 3T K , T 2K . When T ≥ 12K, this interval is non-empty.From the Markov's inequality (Lemma A.1), we haveE T t=1 X t -E[X t ] ≥ aP T t=1 X t -E[X t ] ≥ a for any a > 0. Setting a = 3T K we arrive at E T t=1 X t -E[X t ] ≥ 2 √ 3 exp(-27) T K . Thus, E[REG ℓ ] ≥ √ 3 exp(-27)√ KT , which completes the proof.Remark C.1. For K = 2, the use of Lemma A.4 can be sidestepped via the use of Khintchine's inequality. Indeed, in this case we haveE[REG ℓ ] ≥ E n n - T 2 = 1 2 • E ϵ1,...,ϵ T T t=1 ϵ t ≥ T 8 ,where ϵ 1 , . . . , ϵ T are i.i.d. Rademacher random variables, and the last inequality follows from Khintchine's inequality (Lemma A.2).In this section, we bound the U-calibration error UCal L ′ for subclasses L ′ of L with a finite covering number. We begin with deriving a high probability bound on the regret of Algorithm 1. Lemma D.1. Fix some ℓ ∈ L. Then, for any δ ∈ (0, 1), the regret of Algorithm 1 satisfiesREG ℓ ≤ 4 √ KT + 2T log 1 δ ,with probability at least 1 -δ.Proof. Define the random variableX t := ℓ(p t , y t ), thus X t ∈ [-1, 1].Since the adversary is oblivious and m t,1 , . . . , m t,K are sampled every round independently, X 1 , . . . , X T are independent. Applying Hoeffdings inequality (Lemma A.3), for any ϵ > 0, we haveP T t=1 ℓ(p t , y t ) -E [ℓ(p t , y t )] ≥ ϵ ≤ exp - ϵ 2 2T , which implies that P (REG ℓ -E[REG ℓ ] ≤ ϵ) ≥ 1 -exp -ϵ 2 2T . Let δ := exp -ϵ 2 2T . Then, P REG ℓ -E[REG ℓ ] ≤ 2T log 1 δ ≥ 1 -δ.Finally, applying the result of Theorem 1 to bound E[REG ℓ ] completes the proof.L ′ when L ′ is a finite subset of L. Lemma D.2. Fix a subset L ′ ⊂ L with |L ′ | < ∞. Algorithm 1 ensures UCal L ′ ≤ 2 + 4 √ KT + 2T log (T |L ′ |).Proof. For any ℓ ∈ L, let E ℓ denote the event that REG ℓ ≤ 4 √ KT + 2T log 1 δ . From Lemma D.1, P (E ℓ ) ≥ 1 -δ. Let S := sup ℓ∈L ′ REG ℓ . Thus, the probability that S is bounded by the same quantity is P (∩ ℓ∈L ′ E ℓ ), which can be bounded asP (∩ ℓ∈L ′ E ℓ ) = 1 -P (∪ ℓ∈L ′ E ′ ℓ ) ≥ 1 - ℓ∈L ′ P (E ′ ℓ ) = ℓ∈L ′ P (E ℓ ) + 1 -|L ′ | ≥ 1 -|L ′ | δ,where the first equality follows from De-Morgan's law; the first inequality follows from the union bound; the last inequality is becauseP (E ℓ ) ≥ 1 -δ. Setting δ = 1 T |L ′ | , we obtain P   sup ℓ∈L ′ REG ℓ ≤ 4 √ KT + 2T log (T |L ′ |) =:∆   ≥ 1 - 1 T . Note that, E [S] = P(A)E [S|A] + P(A ′ )E [S|A ′ ],where A denotes the event that S ≤ ∆. Using the facts E [S|A] ≤ ∆, P(A ′ ) ≤ 1 T , andE [S|A ′ ] ≤ 2T since ℓ ∈ [-1, 1], we have E [S] ≤ 2 + ∆,which completes the proof.Before proceeding further, we first define the notion of cover and covering numbers. The ∥.∥ ∞ in the notation M (F, ϵ; ∥.∥ ∞ ) is used to represent the fact that the "distance" between two functions f, g is measured with respect to the ∥.∥ ∞ norm, i.e., sup x∈X |f (x) -g(x)|. Such a definition can be generalized to more general distance metrics/pseudo-metrics, but is not required for our purposes. Note that the cover C ϵ in Definiton D.1 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.Let C ϵ be a minimal ϵ-cover of F. For each g ∈ C ϵ , let S g,ϵ be the collection of functions f ∈ F such that g is a representative of f , i.e.,EQUATIONClearly, ∪ g∈Cϵ S g,ϵ = F. For each S g,ϵ , fix a f lead ∈ S g,ϵ (chosen arbitrarily) as a "leader". Let L lead,F denote the collection of these leaders. It is clear that|L lead,F | ≤ |C ϵ | = M (F, ϵ; ∥.∥ ∞ ).In the following lemma, we generalize the result of Lemma D.2 to the case when L ′ is a possibly infinite subset of L. Our proof is based on applying the result of Lemma D.2 to the leader set of L ′ . Lemma D.3. Fix a subset L ′ ⊆ L with a covering number M (L ′ , ϵ; ∥.∥ ∞ ). Then, the sequence of forecasts made by Algorithm 1 satisfies for any ϵ > 0,UCal L ′ ≤ 2 + 4ϵT + 4 √ KT + 2T log (T • M (L ′ , ϵ; ∥.∥ ∞ )).Proof. Let C ϵ be an ϵ-cover of L ′ of size M (L ′ , ϵ; ∥.∥ ∞ ) and L lead ⊂ L ′ be the corresponding leader set. Applying Lemma D.2, we haveE sup ℓ∈Llead REG ℓ ≤ 2+4 √ KT + 2T log(T |L lead |) ≤ 2+4 √ KT + 2T log(T • M (L ′ , ϵ; ∥.∥ ∞ )).Now, fix any ℓ ∈ L ′ and let g ∈ C ϵ be the representative of ℓ, and ℓ ′ correspond to the leader of the partition S g,ϵ that ℓ belongs to. By definition we have the following:|g(p, y) -ℓ(p, y)| ≤ ϵ, |g(p, y) -ℓ ′ (p, y)| ≤ ϵfor all p ∈ ∆ K , y ∈ E. Therefore, it follows from the triangle inequality that |ℓ(p, y) -ℓ ′ (p, y)| ≤ 2ϵ. As usual, let β = 1 T T t=1 y t denote the empirical average of the outcomes. Then,ℓ(p t , y t ) -ℓ(β, y t ) ≤ ℓ ′ (p t , y t ) -ℓ ′ (β, y t ) + 4ϵ =⇒ REG ℓ ≤ REG ℓ ′ + 4ϵT.Taking supremum with respect to ℓ ∈ L on both sides, followed by expectation, we obtainE sup ℓ∈L REG ℓ ≤ E sup ℓ∈Llead REG ℓ + 4ϵT ≤ 2 + 4ϵT + 4 √ KT + 2T log (T • M (L ′ , ϵ; ∥.∥ ∞ )),which finishes the proof.Lemma E.1. Suppose that for a loss function ℓ, there exists a constantG [ 1 T ,1] such that for each i ∈ [K], ℓ(p, e i ) is locally Lipschitz in the sense that |ℓ(p, e i ) -ℓ(p ′ , e i )| ≤ G [ 1 T ,1] ∥p -p ′ ∥ for all p, p ′ ∈ ∆ K such that p i , p ′ i ∈ [ 1 T , 1].Then, the regret of FTL with respect to this loss is at most2K + G [ 1 T ,1] (1 + log T ).Proof. Using the Be-the-Leader lemma, we know that the regret of FTL can be bounded as REG≤ 2 + K i=1 t≥2;yt=ei ℓ(p t , e i ) -ℓ(p t+1 , e i ).Assume that E m ⊆ E of size m ≤ K contains all the outcomes chosen by the adversary over T rounds, i.e., y t ∈ E m for all t ∈ [T ]. For each e i ∈ E m , let k i denote the total number of time instants t such that y t = e i and let T i := {t i,1 , . . . , t i,ki } denote those time instants. Then, we haveREG ℓ ≤ 2 + ei∈Em t≥2;yt=ei ℓ(p t , e i ) -ℓ(p t+1 , e i ) ≤ 2m + ei∈Em t∈Ti\{ti,1} ℓ(p t , e i ) -ℓ(p t+1 , e i ),where the last inequality follows by bounding ℓ(p t , e i ) -ℓ(p t+1 , e i ) with 2 for all the t's where an outcome appears for the first time. For each e i ∈ E m and for all t > t i,1 , we have pt,i = nt-1,i t-1 ≥ 1 T . Therefore, REG ℓ ≤ 2m + G [ 1 T ,1] ei∈Em t∈Ti\{ti,1} ∥p t -p t+1 ∥ = 2m + G [ 1 T ,1] ei∈Em t∈Ti\{ti,1} n t-1 t -1 - n t t .Proceeding similar to the proof of Theorem 3, we can show thatREG ℓ ≤ 2m + G [ 1 T ,1] ei∈Em t∈Ti\{ti,1} 1 t = 2m + G [ 1 T ,1] T t=1 1 t - ei∈Em 1 t i,1 ≤ 2K + G [ 1 T ,1] (1 + log T ),where the last inequality follows by dropping the negative term, m ≤ K, andT j=2 1 j ≤T 1 1 z dz = log T . This completes the proof.Example E.1. Consider for instance the loss whose univariate form is ℓ(p) = -c K K i=1 p α i , where α ∈ (1, 2), and cK > 0 is a normalizing constant (which only depends on K) to ensure that ℓ(p, y) is bounded in [-1, 1]. Clearly, ℓ(p) is concave and thus the induced loss ℓ(p, y) is proper as per Lemma 1. For the chosen ℓ(p), ℓ(p, e 1 ) is given byℓ(p, e 1 ) = ℓ(p) + (1 -p 1 )∇ 1 ℓ(p) - K i=2 p i ∇ i ℓ(p) = -c K (1 -α) K i=1 p α i + αp α-1 1 . (7) It is easy to verify that ∇ 1 ℓ(p, e 1 ) = -c K • α(α -1)p α-2 i (1 -p 1 ) and ∇ i ℓ(p, e 1 ) = -c K • α(1 - α)p α-1 i for all i > 1. Thus, for a large T , G [ 1 T ,1] is of order O(α(α -1)c K T 2-α ). This yields a regret bound O(K + α(α -1)c K T 2-α log T ), which for α ∈ ( 3 2 , 2) is better (with respect to T ) than the O( √ KT ) bound obtained in Theorem 1.Theorem 4. There exists a proper Lipschitz loss ℓ such that: for any algorithm ALG, there exists a choice of y 1 , . . . , y T by an oblivious adversary such that the expected regret of ALG is Ω(log T ).As mentioned, the loss we use in this lower bound construction is the squared loss ℓ(p, y) := ∥p -y∥ 2 (we ignore the constant 1/2 here for simplicity, which clearly does not affect the proof). It is clearly convex in p for any y. The univariate form of the loss isℓ(p) = E y∼p [ℓ(p, y)] = K i=1 p i ∥p -e i ∥ 2 = ∥p∥ 2 + 1 -2 K i=1 p i ⟨p, e i ⟩ = 1 -∥p∥ 2 .We now follow the three steps outlined in Section 4.1.Step 1: First, it is well-known that for convex losses, deterministic algorithms are as powerful as randomized algorithms. Formally, let A rand and A det be the class of randomized algorithms and deterministic algorithms respectively for the forecasting problem. Then the following holds: Lemma F.1. For any loss ℓ(p, y) that is convex in p ∈ ∆ K for any y ∈ E, we have Proof. The direction "≤" is trivial since A det ⊆ A rand . For the other direction, it suffices to show that for any randomized algorithm ALG ∈ A rand , one can construct a deterministic algorithm ALG ′ ∈ A det such that, for any fixed sequence y 1 , . . . , y T ∈ E, the expected regret of ALG 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 t. Since the loss if convex, by Jensen's inequality, the loss of ALG ′ is at 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 ALG∈Adet sup y1,...,y T ∈E REG ℓ can be written asVAL = inf pt∈∆ K sup yt∈E T t=1 T t=1 ℓ(p t , y t ) -inf p∈∆ K T t=1 ℓ(p, y t ) ,where inf pt∈∆ K sup yt∈E T t=1 is a shorthand for the iterated expression infp1∈∆ K sup y1∈E inf p2∈∆ K sup y2∈E . . . . . . inf p T -1 ∈∆ K sup y T -1 ∈E inf p T ∈∆ K sup y T ∈E . Let n ∈ N K≥ be a vector such that n i represents the cumulative number of the outcome i, and r ∈ {0, . . . , T } represent the number of remaining rounds. For any n and r such that ∥n∥ 1 + r = T , define V n,r recursively asV n,r = inf p∈∆ K sup y∈E V n+y,r-1 + ℓ(p, y) with V n,0 = -inf p∈∆ K K i=1 n i ℓ(p, e i ). It is then clear that VAL is simply V 0,T .Step 2: We proceed to rewrite and simplify V n,r as follows:V n,r = inf p∈∆ K sup y∈E V n+y,r-1 + ℓ(p, y) (8) = inf p∈∆ K sup q∈∆ K E y∼q [V n+y,r-1 + ℓ(p, y)] = sup q∈∆ K inf p∈∆ K E y∼q [V n+y,r-1 + ℓ(p, y)] = sup q∈∆ K inf p∈∆ K K i=1 q i V n+ei,r-1 + q i ℓ(p, e i ) = sup q∈∆ K inf p∈∆ K K i=1 q i V n+ei,r-1 + q i (ℓ(p) + ⟨∇ℓ(p), e i -p⟩) = sup q∈∆ K inf p∈∆ K K i=1 q i V n+ei,r-1 + ℓ(p) + ⟨∇ℓ(p), q -p⟩ = sup q∈∆ K K i=1 q i V n+ei,r-1 + ℓ(q),where the second equality follows since E y∼q [V n+y,r-1 + ℓ(p, y)] is a linear function in q, and the infimum/supremum of a linear function is attained at the boundary; the third equality follows from the minimax theorem as E y∼q [V n+y,r-1 + ℓ(p, y)] is convex in p and concave in q; the final equality is because ℓ(p) + ⟨∇ℓ(p), q -p⟩ ≥ ℓ(q) which follows from the concavity of the univariate form of ℓ, and equality is attained at p = q.Throughout the subsequent discussion, we consider K = 2 and use the concrete form of the squared loss. Writing V (n1,n2),r as V n1,n2,r for simplicity, we simplify the recurrence toV n1,n2,r = sup q∈∆2 q 1 V n1+1,n2,r-1 + q 2 V n1,n2+1,r-1 + 1 -q 2 1 -q 2 2 = sup q∈[0,1] V 2 + (V 1 -V 2 )q -2(q 2 -q),where V 1 , V 2 is a shorthand for V n1+1,n2,r-1 , V n1,n2+1,r-1 respectively. It is straightforward to show via the KKT conditions thatsup q∈[0,1] V 2 + (V 1 -V 2 )q -2(q 2 -q) =      V 2 if V 1 -V 2 < -2, (V1-V2) 2 8 + V1+V2 2 + 1 2 if -2 ≤ V 1 -V 2 ≤ 2, V 1 if V 1 -V 2 > 2. (R) Thus, (R) (with V 1 , V 2 replaced by V n1+1,n2,r-1 , V n1,n2+1,r-1) represents the recurrence we wish to solve for to obtain V 0,0,T . The base case of (R) is the following:V n,T -n,0 = -T ℓ n T , 1 - n T = 2T • n T • n T -1 (9)which holds for all n such that 0 ≤ n ≤ T . In the next lemma we show that-2 ≤ V 1 -V 2 ≤ 2,therefore, it is sufficient to solve the recursion (R) corresponding to this case only. Lemma F.2. The recurrence (R) is also equal to the following:V n1,n2,r = (V n1+1,n2,r-1 -V n1,n2+1,r-1 ) 2 8 + V n1+1,n2,r-1 + V n1,n2+1,r-1 2 + 1 2 . (R ′ )Proof. It suffices to show that the condition |V n1+1,n2,r-1 -V n1,n2+1,r-1 | ≤ 2 always holds.Rewriting n 2 + 1 as n 2 and r -1 as r, this is equivalent to showing|V n1,n2,r -V n1+1,n2-1,r | ≤ 2 (10)for all n 1 , n 2 , r such that n 1 + n 2 + r = T , and the arguments in (10) are well defined, i.e., 0 ≤ n 1 ≤ T -r -1, and 1 ≤ n 2 ≤ T -r. We prove this by an induction on r.Base Case: This corresponds to r = 0. For 0≤ n ≤ T -1, |V n,T -n,0 -V n+1,T -n-1,0 | is equal to 2T • n T • n T -1 - n + 1 T • n + 1 T -1 = 2 • 1 - 2n + 1 T ≤ 2 • 1 - 1 T ≤ 2,which verifies the base case.Induction Hypothesis: Fix a k ∈ {1, . . . , T }; assume that (10) holds for r = k -1.Step: We show that (10) holds for r = k. It follows from (R) and the induction hypothesis thatV n1,n2,k = 1 8 (V n1+1,n2,k-1 -V n1,n2+1,k-1 ) 2 + V n1+1,n2,k-1 + V n1,n2+1,k-1 2 + 1 2 , V n1+1,n2-1,k = 1 8 (V n1+2,n2-1,k-1 -V n1+1,n2,k-1 ) 2 + V n1+2,n2-1,k-1 + V n1+1,n2,k-1 2 + 1 2 . Let α 1 := V n1+2,n2-1,k-1 , α 2 := V n1+1,n2,k-1 , α 3 := V n1,n2+1,k-1 , ∆ := V n1+1,n2-1,k - V n1,n2,k. Subtracting the equations above and expressing in terms of the defined quantities, we obtain∆ = α 1 + α 2 2 + (α 1 -α 2 ) 2 8 - α 2 + α 3 2 - (α 2 -α 3 ) 2 8 = α 1 -α 3 2 + (α 1 -α 3 ) • (α 1 + α 3 -2α 2 ) 8 = x + y 2 + (x + y) • (x -y) 8 = (x + 2) 2 -(y -2) 2 8 ,where we have definedx := α 1 -α 2 , y := α 2 -α 3 . It follows from the induction hypothesis that |x| ≤ 2, |y| ≤ 2, therefore |∆| ≤ 2. Summarizing, we have shown that |V n1+1,n2-1,k -V n1,n2,k | ≤2 which completes the proof via induction.Step 3: Since n 1 + n 2 + r = T , we may express V n1,n2,r in terms of n 1 , n 2 , and T . In the next lemma, we show that V n1,n2,r exhibits a very special structure when expressed in this manner; this allows us to reduce V 0,0,T to solving a one dimensional recurrence. Lemma F.3. For all n 1 , n 2 such that n 1 , n 2 ≥ 0, andEQUATIONwhere {u r } T r=0 , {v r } T r=0 are sequences that depend only on T , and are defined by the following recurrences:u r+1 = u r + u r + 1 T 2 , v r+1 = u r 2 + v r + r + 1 T - 1 2 (12) for all 0 ≤ r ≤ T -1, with u 0 = v 0 = 0.Proof. Similar to Lemma F.2, the proof shall follow by an induction on r.Base Case: For r = 0, it follows from (9) that V n1,n2,0 = -2n1n2 T , which is consistent with (11) and u 0 = v 0 = 0. Induction Hypothesis: Fix a k ∈ {0, . . . , T -1}. Assume that (11) holds for r = k.Step: We show that (11) holds for r = k + 1. From Lemma F.2, we haveEQUATION)It follows from the induction hypothesis thatV n1+1,n2,k = (n 1 + 1 -n 2 ) 2 2 • u k - 2(n 1 + 1) • n 2 T + v k , V n1,n2+1,k = (n 1 -n 2 -1) 2 2 • u k - 2n 1 • (n 2 + 1) T + v k . Define δ := V n1+1,n2,k -V n1,n2+1,k and σ := V n1+1,n2,k + V n1,n2+1,k . Subtracting the equations above, we obtainδ = (n 1 + 1 -n 2 ) 2 -(n 1 -n 2 -1) 2 2 • u k + 2n 1 • (n 2 + 1) -2(n 1 + 1) • n 2 T = 2(n 1 -n 2 ) • u k + 1 T .Adding the equations above, we obtainσ = (n 1 + 1 -n 2 ) 2 + (n 1 -n 2 -1) 2 2 • u k - 2n 1 • (n 2 + 1) + 2(n 1 + 1) • n 2 T + 2v k = (n 1 -n 2 ) 2 + 1 • u k - 4n 1 n 2 T - 2(n 1 + n 2 ) T + 2v k = (n 1 -n 2 ) 2 • u k - 4n 1 n 2 T + u k + 2v k + 2(r + 1) T -2,where the last equality follows sincen 1 + n 2 = T -k -1. Expressing V n1,n2,k+1 in terms of δ, σ, we have V n1,n2,k+1 = δ 2 8 + σ 2 + 1 2 . Substituting δ, σ, we obtain V n1,n2,k+1 = (n 1 -n 2 ) 2 2 • u k + u k + 1 T 2 - 2n 1 n 2 T + u k 2 + v k + (r + 1) T - 1 2 = (n 1 -n 2 ) 2 2 • u k+1 - 2n 1 n 2 T + v k+1 ,which completes the induction step. The proof is hence complete by induction.Since VAL = V 0,0,T = v T , it only remains to bound v T . Note that the recursion describing v is coupled with u. However, since we only want to bound v T , we can sum the recursion describing v to obtainT -1 r=0 (v r+1 -v r ) = 1 2 • T -1 r=0 u r + 1 T • T -1 r=0 (r + 1) - T 2 = 1 2 • T -1 r=0 u r + 1 .Moreover, since the summation with respect to v telescopes and v 0 = 0, we havev T = 1 2 • T -1 r=0 u r + 1 .T -1r=0 u r . Define a r := u r + 1 T so that v T = 1 2 T -1 r=0 a r . The recurrence (12) describing u reduces to a r+1 = a r + a 2 r for all 0 ≤ r ≤ T -1, with a 0 = 1 T . In the next result, we obtain bounds on a r . Lemma F.4. For all 0 ≤ r ≤ T -1, it holds that a r ≤ 1 T -r .Proof. As usual, the proof shall follow by an induction on r. Since a 0 = 1 T , the base case is trivially satisfied. Fix a k ∈ {0, . . . , T -2}, and assume thata k ≤ 1 T -k . Since a k+1 = a k + a 2 k , we have a k+1 ≤ 1 (T -k) 2 + 1 T -k = T -k + 1 (T -k) 2 = (T -k) 2 -1 (T -k) 2 • 1 T -k -1 ≤ 1 T -k -1 .This completes the induction step.Lemma F.5. For all 0 ≤ r ≤ T -1, it holds that a r ≥ 1 T -r+log T . Furthermore, T -1 r=0 a r ≥ log T log T + 1 + 1 = Ω(log T ).Proof. According to Lemma F.4, we can write a r as 1 T -r+br for some non-negative sequence {b r } with b 0 = 0. We next obtain the recurrence describing {b r }. In particular, since a r+1 = a r (a r + 1), we have1 T -(r + 1) + b r+1 = 1 T -r + b r • 1 T -r + b r + 1 ,which on simplifying (by multiplying both sides withEQUATIONNext, we shall show by an induction on r that b r ≤ r-1 i=01T -i for all 0 ≤ r ≤ T -1. Since b 0 = 0, the base case is trivially satisfied. Fix a k ∈ {0, . . . , T -2} and assume that b k ≤ k-1 i=0 1 T -i . We consider two cases depending on whether or not b k+1 ≥ b k . If b k+1 < b k , the induction step holds trivially. If b k+1 ≥ b k , it follows from the recurrence (14) that b k+1 ≤ b k + 1 T -k + b k ≤ b k + 1 T -k ≤ k i=0 1 T -i ,which completes the induction step. Therefore, we have established that b r ≤ r-1 i=01T -i for all 0 ≤ r ≤ T -1. It then follows that b r ≤ T -2 i=0 1 T -i ≤ T 1 dz z = log T, for all 0 ≤ r ≤ T -1, which translates to a r ≥ 1 T -r+log T .This completes the proof of the first part of the lemma. With this lower bound on a r , we can lower boundT -1 r=0 a r as T -1 r=0 a r ≥ T -1 r=0 1 T -r + log T = T i=1 1 i + log T ≥ T +1 1 dz z + log T = log T log T + 1 + 1 ,which is Ω(log T ) for a large T . This completes the proof.To conclude, we have shownVAL = V 0,0,T = v T = 1 2 T -1 r=0 u r + 1 = 1 2 T -1 r=0 a r = Ω(log T ),proving Theorem 4.Theorem 5. The regret of FTL for learning any ℓ ∈ L dec is at most 2K + (K + 1)β ℓ (1 + log T ) for some universal constant β ℓ which only depends on ℓ and K. Consequently, FTL ensuresPUCal Ldec = UCal Ldec = O((sup ℓ∈Ldec β ℓ )K log T ).Proof. We work with the notation established in the proof of Lemma E.1. The regret of FTL can be bounded asREG ≤ 2m + ei∈Em t∈Ti\{ti,1} ℓ(p t , e i ) -ℓ(p t+1 , e i ) δt,i.In the subsequent steps, we shall bound δ t,i . We begin in the following manner:δ t,i = ℓ(p t ) + ⟨e i -p t , ∇ℓ(p t )⟩ -ℓ(p t+1 ) -⟨e i -p t+1 , ∇ℓ(p t+1 )⟩ = ℓ(p t ) -ℓ(p t+1 ) + [∇ℓ(p t )] i -[∇ℓ(p t+1 )] i + ⟨p t+1 , ∇ℓ(p t+1 )⟩ -⟨p t , ∇ℓ(p t )⟩ ≤ [∇ℓ(p t )] i -[∇ℓ(p t+1 )] i + ⟨p t , ∇ℓ(p t+1 ) -∇ℓ(p t )⟩ ,where the first equality follows from Lemma 1; the first inequality follows since ℓ(p t ) ≤ ℓ(p t+1 ) + ⟨∇ℓ(p t+1 ), p t -p t+1 ⟩ which follows from the concavity of ℓ. Next, by the Mean Value Theorem,∇ℓ(p t+1 ) -∇ℓ(p t ) = ∇ 2 ℓ(p t + v(p t+1 -p t )) • (p t+1 -p t ) for some v ∈ [0, 1]. Note that p t,i = nt-1,i t-1 , p t+1,i = nt-1,i+1 t (since y t = e i ), therefore p t+1,i ≥ p t,i . Let ξ t := p t + v(p t+1 -p t ). Then, [∇ℓ(p t )] i -[∇ℓ(p t+1 )] i = [∇ 2 ℓ(ξ t )] i , p t -p t+1 ,where [∇ 2 ℓ(ξ t )] i denotes the i-th row of [∇ 2 ℓ(ξ t )]; we arrive atEQUATIONwhere the first equality follows since p t+1,i ≥ p t,i and ∇ 2 i,i ℓ(ξ t ) ≤ 0; the second inequality follows by dropping the termp t,i • ∇ 2 i,i ℓ(ξ t ) • (p t+1,i -p t,i) which is non-positive; the final inequality is because, for j ̸ = i, we have p t+1,j = nt-1,j t and p t,j = nt-1,j t-1 , therefore p t+1,j ≤ p t,j , and bounding p t,j ≤ 1.To proceed with the further bounding, we apply Lemma 2 and utilize the growth condition on the Hessian ∇ 2 j,j ℓ(ξ t ) ≤ cK • c j • max 1 ξt,j , 1 1-ξt,j for some constant c j > 0 and all j ∈ [K] (here cK is the scaling constant such that ℓ(p) = cK K i=1 ℓ i (p i )). Let β ℓ,j := cK • c j . Using the bound on ∇ 2 j,j ℓ(ξ t ) to bound the term in (15), we obtainEQUATIONNext, we shall bound the terms T 1 := pt+1,i-pt,i ξt,i, T 2 := pt+1,i-pt,i 1-ξt,i , T 3 := pt,j -pt+1,j ξt,j, and T 4 := pt,j -pt+1,j 1-ξt,j, where the index j in T 3 and T 4 runs over j ̸ = i. Note that,T 1 = p t+1,i -p t,i p t,i + v(p t+1,i -p t,i ) ≤ p t+1,i -p t,i p t,i = n t-1,i + 1 n t-1,i • t -1 t -1 ≤ 1 n t-1,i ,where the first equality follows from the definition of ξ t ; the first inequality follows since p t+1,i ≥ p t,i and v ∈ [0, 1]. Similarly,T 2 = p t+1,i -p t,i 1 -p t,i -v(p t+1,i -p t,i ) ≤ p t+1,i -p t,i 1 -p t+1,i = n t-1,i + 1 t - n t-1,i t -1 • 1 1 - nt-i,i+1 t = t -1 -n t-1,i t • (t -1) • t t -1 -n t-1,i = 1 t -1 ,where the first inequality follows since p t+1,i ≥ p t,i . For T 3 , we haveT 3 = 1 - pt+1,j pt,j 1 + v pt+1,j pt,j -1 = 1 t 1 -v t ≤ 1 t -1 ,where the inequality follows since v ∈ [0, 1]. Finally, we bound T 4 asT 4 = 1 - pt+1,j pt,j 1 pt,j -1 + v pt+1,j pt,j -1 = 1 t t-1 nt-1,j -1 + v t ≤ n t-1,j t • 1 t -1 -n t-1,j ≤ 1 n t-1,i ,where the final inequality is because K j=1 n t-1,j = t -1. Collecting the bounds on T 1 , T 2 , T 3 , and T 4 , and substituting them back in ( 16), we getδ t,i ≤ K j=1 β ℓ,j • max 1 n t-1,i , 1 t -1 ≤ K j=1 β ℓ,j • 1 n t-1,i + 1 t -1 .Summing over all t, we obtain REG ℓ ≤ 2m+β ℓ (S 1 +S 2 ), where S 1 := ei∈Em t∈Ti\{ti,1} 1 nt-1,i , S 2 := ei∈Em t∈Ti\{ti,1} 1 t-1 , and β ℓ := K i=1 β ℓ,i . Note that the subscript in β ℓ denotes that the constant is dependent on the loss ℓ and only depends on ℓ and K. We bound S 1 asS 1 = ei∈Em ki-1 j=1 1 j ≤ m T t=1 1 j ≤ m(1 + log T ) ≤ K(1 + log T ).Next, note that S 2 ≤ T t=1 1 t ≤ 1 + log T . Thus, S 1 + S 2 ≤ (K + 1)(1 + log T ), which yields REG ℓ ≤ 2K + (K + 1)β ℓ (1 + log T ). This completes the proof.Lemma 2. For a function f that is concave, Lipschitz, and bounded over [0, 1] and twice continuously differentiable over (0, 1), there exists a constant c > 0 such that |f ′′ (p)| ≤ c • max 1 p , 1 1-p for all p ∈ (0, 1).Proof. Since f is twice differentiable, if |f ′′ (p)| does not approach infinity at the boundary of [0, 1], then there is nothing to prove. In the rest of the proof, we assume that |f ′′ (p)| approaches infinity both when p approaches 0 and when p approaches 1 (the case when it only approaches infinty at one side is exactly the same).Using a technical result from Lemma H.1, there exists an ϵ 0 ∈ (0, 1) such that for any p ∈ (0, ϵ 0 ],|f ′′ (p)| =|f ′ (q) -f ′ (0)| q for some q ∈ [p, 1], which can be further bounded by|f ′ (q) -f ′ (0)| p ≤ |f ′ (q)| + |f ′ (0)| p ≤ 2 • sup q∈[0,1] |f ′ (q)| p ≤ c 1 max 1 p , 1 1 -p with c 1 := 2 sup q∈[0,1] |f ′ (q)|(finite due to f being Lipschitz). Similarly, there exists an ϵ 1 ∈ (0, 1) such that for any p ∈ [1 -ϵ 1 , 1),|f ′′ (p)| = |f ′ (1) -f ′ (q)| 1 -q for some q ∈ [0, p], which is further bounded by |f ′ (1) -f ′ (q)| 1 -p ≤ |f ′ (1)| + |f ′ (q)| 1 -p ≤ c 1 max 1 p , 1 1 -p .Finally, for any p ∈ (ϵ 0 , 1 -ϵ 1 ), we trivially bound |f ′′ (p)| as|f ′′ (p)| ≤ max 1 p , 1 1 -p sup q∈(ϵ0,1-ϵ1) |f ′′ (q)| max 1 q , 1 1-q c2, where c 2 is finite since f is twice continuously differentiable in (0, 1). Setting c = max(c 1 , c 2 ) finishes the proof.Lemma H.1. Let f satisfy the conditions of Lemma 2 and additionally lim p→0 + |f ′′ (p)| = ∞ and lim p→1 -|f ′′ (p)| = ∞. Then there exists ϵ 0 ∈ (0, 1) such that for any p ∈ (0, ϵ 0 ], we have f ′ (q) -f ′ (0) = f ′′ (p)q for some q ∈ [p, 1]. Similarly, there exists ϵ 1 ∈ (0, 1) such that for any p ∈ [1 -ϵ 1 , 1), we have f ′ (1) -f ′ (q) = f ′′ (p)(1 -q) for some q ∈ [0, p].Proof. For simplicity, we only prove the first part of the lemma since the proof of the second part follows the same argument. Since f is twice continuously differentiable in (0, 1) and lim p→0 + |f ′′ (p)| = ∞, there exists an ϵ ∈ (0, 1) such that |f ′′ | is decreasing in (0, ϵ]. Since f is concave, this is equivalent to f ′′ being increasing in (0, ϵ].Now, applying Mean Value Theorem, we know that there exists ϵ 0 ∈ (0, ϵ] such that f ′ (ϵ) -f ′ (0) = f ′′ (ϵ 0 )ϵ. It remains to prove that for any p ∈ (0, ϵ 0 ], the function g(q) := f ′ (q) -f ′ (0) -f ′′ (p)q has a root in [p, 1] . This is true becauseg(p) = f ′ (p) -f ′ (0) -f ′′ (p)p = (f ′′ (ξ) -f ′′ (p))p ≤ 0,where the equality is by Mean Value Theorem again for some point ξ ∈ [0, p] and the inequality holds since f ′′ is increasing in (0, ϵ]. On the other hand, we haveg(ϵ) = f ′ (ϵ) -f ′ (0) -f ′′ (p)ϵ = (f ′′ (ϵ 0 ) -f ′′ (p))ϵ ≥ 0,where the equality holds by the definition of ϵ 0 and the inequality holds since again f ′′ is increasing in (0, ϵ]. Applying the Intermediate Value Theorem then shows that g(q) has a root in [p, ϵ], which finishes the proof.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 1. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.* The forecast at time t = 1 can be arbitrary. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This works considered the the problem of making sequential non-contextual probabilistic predictions over $K$ classes with low U-calibration error.
The 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.
The also proved a matching lower bound, and shows the optimality of FTPL.
Further, they provided strengthened bounds of $\Theta(\log T)$ under various additional assumptions on the proper losses.
strength_weakness: strength_weakness: No outstanding weakness. Typos and questions are given under questions.
questions: 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.
- 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".
- 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?
- 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.
- L181: dose -> does
limitations: limitations: Limitations are addressed theoretically in Section 4.3.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

However, 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.
questions: 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: limitations: Societal impact not applicable due to the theoretical nature.
paper_summary: paper_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.
strength_weakness: strength_weakness: Originality: 
The tasks or methods do not really stand out as new, more emphasis what the work introduces would help. 

Clarity: 
It is a bit lacking at times in adequately informing the reader regarding the contents, especially towards the end (pages 8 and 9). 

Significance:
The difficulty of the task the submission addresses (demonstrably in a better way than the previous works) is questionable.
questions: questions: Major Questions:
- Page 2 Line 42: isn't p from a continuum, how is a sum over p defined?
- Page 5 Line 208: how is (a) claimed? Explain.

Minor Questions:
- Page 2 Line 39: what do you insert instead of dropped notations?
- Page 8 Line 322: why 2K?

Suggestions:
- Page 6 Line 228: check grammar.
- Page 7 Line 280: missing comma.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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).

Traditionally, 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.

This paper does the following:
1. 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).
2. 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). 

Kleinberg 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.
strength_weakness: strength_weakness: See previous section.
questions: questions: No specific questions, feel free to reply to anything in the review.
limitations: limitations: Authors have adequately addressed limitations.

Comments: comment: Thank you for your response. I have read and considered it, as well as the other reviews and rebuttals. My opinion about the paper is still towards acceptance.
Thank you for your response! I have read the other reviews and comments and maintain my (positive) evaluation.