Paper deep dive
Calibeating Made Simple
Yurong Chen, Zhiyi Huang, Michael I. Jordan, Haipeng Luo
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 99%
Last extracted: 3/26/2026, 2:37:29 AM
Summary
The paper establishes a formal reduction of the 'calibeating' problem—a post-processing task for online probabilistic forecasting—to standard online learning primitives. It proves that calibeating is minimax-equivalent to regret minimization and that multi-calibeating is equivalent to the combination of calibeating and the expert problem. These reductions yield optimal O(log T) rates for mixable losses (like Brier and log losses) and new bounds for general bounded losses, while also providing a meta-algorithm for simultaneous calibeating and calibration.
Entities (6)
Relation Signals (3)
Brier loss → isa → Proper scoring loss
confidence 100% · Throughout, we consider a proper scoring loss... Example 2.2. For Brier loss...
Calibeating → isminimaxequivalentto → Regret minimization
confidence 100% · we first show that calibeating is minimax-equivalent to regret minimization.
Multi-calibeating → isminimaxequivalentto → Expert problem
confidence 100% · multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study calibeating, the problem of post-processing external forecasts online to minimize cumulative losses and match an informativeness-based benchmark. Unlike prior work, which analyzed calibeating for specific losses with specific arguments, we reduce calibeating to existing online learning techniques and obtain results for general proper losses. More concretely, we first show that calibeating is minimax-equivalent to regret minimization. This recovers the $O(\log T)$ calibeating rate of Foster and Hart [FH23] for the Brier and log losses and its optimality, and yields new optimal calibeating rates for mixable losses and general bounded losses. Second, we prove that multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem. This yields new optimal multi-calibeating rates for mixable losses, including Brier and log losses, and general bounded losses. Finally, we obtain new bounds for achieving calibeating and calibration simultaneously for the Brier loss. For binary predictions, our result gives the first calibrated algorithm that at the same time also achieves the optimal $O(\log T)$ calibeating rate.
Tags
Links
- Source: https://arxiv.org/abs/2603.22167v1
- Canonical: https://arxiv.org/abs/2603.22167v1
Trouble viewing inline? Open PDF directly →
Full Text
75,834 characters extracted from source content.
Expand or collapse full text
Calibeating Made Simple Yurong Chen1 Zhiyi Huang2 Michael I. Jordan1,3 Haipeng Luo4 1Inria École Normale Supérieure PSL Research University 2The University of Hong Kong 3University of California Berkeley 4University of Southern California yurong.chen@inria.fr zhiyi@cs.hku.hk jordan@cs.berkeley.edu haipengl@usc.edu Abstract We study calibeating, the problem of post-processing external forecasts online to minimize cumulative losses and match an informativeness-based benchmark. Unlike prior work, which analyzed calibeating for specific losses with specific arguments, we reduce calibeating to existing online learning techniques and obtain results for general proper losses. More concretely, we first show that calibeating is minimax-equivalent to regret minimization. This recovers the O(logT)O( T) calibeating rate of [FH23] for the Brier and log losses and its optimality, and yields new optimal calibeating rates for mixable losses and general bounded losses. Second, we prove that multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem. This yields new optimal multi-calibeating rates for mixable losses, including Brier and log losses, and general bounded losses. Finally, we obtain new bounds for achieving calibeating and calibration simultaneously for the Brier loss. For binary predictions, our result gives the first calibrated algorithm that at the same time also achieves the optimal O(logT)O( T) calibeating rate. 1 Introduction Calibration has attracted growing attention in recent years as a desideratum for probabilistic prediction, motivated by the need to produce reliable probabilities for downstream decision-making [Guo+17]. Despite its appeal as a benchmark for reliability, however, calibration is not necessarily a meaningful test of forecasting expertise. For example, online calibration can be achieved by randomized strategies without any knowledge of the data-generating process [FV98]. Hence, calibration alone cannot distinguish true expertise from uninformative procedures. To quantify and preserve forecasting expertise, [FH23] introduced calibeating in a post-processing setting. In this setting, an external forecaster (e.g., a machine learning model) outputs a probabilistic forecast at each round, and then the learner produces its own forecast based on it. It is known that for proper losses such as the Brier and log losses, the cumulative score can be decomposed into a calibration term, which measures the reliability, and a refinement term, which measures the informativeness and skill. This motivates the question of whether one can improve reliability without sacrificing skill. Calibeating formalizes this goal by requiring the learner’s loss to be as small as the external forecaster’s refinement score (in other words, to “beat” the forecaster by its calibration error). Existing work [FH23, Lee+22] establishes online calibeating guarantees for the Brier and log losses, and studies extensions such as beating multiple forecasters (multi-calibeating) and imposing simultaneous calibration constraints. These results rely on loss-specialized analyses. More broadly, the fundamental statistical difficulty of calibeating and its relationship to standard online-learning problems have remained unclear, leaving open whether known bounds are optimal or how they generalize beyond the Brier and log losses. 1.1 Our Results We study calibeating from an online-learning perspective. Rather than analyzing different losses on a case-by-case basis, we identify simple reductions from (multi-)calibeating to standard online-learning primitives. This yields a “plug-and-play” analysis: by instantiating the reductions with classical online-learning algorithms, we obtain general upper and lower bounds in a modular way. Calibeating == no-regret learning (Section 3). We prove that calibeating is minimax-equivalent to regret minimization. Theorem 3.1 gives a reduction that turns any no-regret learner with regret bound α(T)α(T) into a calibeating algorithm with a corresponding bound that scales with |Q||Q|, the number of distinct external forecast values over T rounds. The reduction exploits the fact that the refinement benchmark decomposes across distinct forecast values, allowing one to treat each corresponding subsequence independently. Instantiating this reduction recovers the O(|Q|logT)O(|Q| T) guarantees for the Brier and log losses from [FH23] and extends them to general mixable losses (Corollary 3.4). We also obtain an O(|Q|T)O( |Q|T) bound for general bounded proper losses (Corollary 3.2). Conversely, Theorem 3.5 provides a matching lower bound that completes the minimax-equivalence. Multi-calibeating == calibeating ++ expert problem (Section 4). Next, we present (in Theorem 4.1) a simple decomposition of multi-calibeating into calibeating and the expert problem: run a separate calibeating subroutine for each forecaster to produce candidate predictions, then aggregate them with an expert algorithm. The resulting multi-calibeating guarantee is the sum of the calibeating bound and the expert regret bound. For mixable losses, we obtain a logarithmic bound of O(logN+|Q(n)|logT)O( N+|Q^(n)| T) (Corollary 4.3), where N is the number of forecasters and Q(n)Q^(n) is the set of distinct forecasts produced by forecaster n. This improves exponentially over the polynomial dependence on N in [FH23] and the polynomial dependence on T in [Lee+22]. We complement this with a lower-bound reduction (Theorem 4.4), showing that multi-calibeating inherits hardness from both the expert problem and the calibeating problem. This yields matching lower bounds for Brier and log losses and shows the tightness of our results (Corollary 4.6). Simultaneous (multi-)calibeating and calibration for Brier loss (Section 5). Finally, we provide new bounds for achieving calibeating and calibration simultaneously. We propose a meta-algorithm that tracks an arbitrary reference algorithm while ensuring calibration (Theorem 5.1). The construction employs two existing online learning primitives: the reduction by [BM07] to enforce calibration via the calibration-swap-regret connection, and a two-expert algorithm by [SNL14] to aggregate the predictions from the Blum–Mansour (BM) reduction and the reference algorithm. Instantiating the reference with the (multi-)calibeating algorithms from the previous sections, for the Brier loss, we obtain for the binary case the optimal logarithmic (multi-)calibeating rate of O(logN+|Q(n)|logT)O( N+|Q^(n)| T) while ensuring a sublinear ℓ2 _2-calibration error of order O~(T) O( T) (Corollary 5.2). This improves the polynomial T-dependence on the calibeating side in [FH23] and improves both sides compared to [Lee+22]. For multi-class outcomes, we derive explicit tradeoffs between (multi-)calibeating and calibration (Corollary 5.3). In particular, at one extreme, we recover the known dependence on T for calibration [FH23, Fis+25] while dropping the |Q(n)||Q^(n)| dependence in [FH23]. For a summary of our results and comparisons with prior work, see Table 1. Table 1: Comparison of prior and our guarantees in N, T, K (the number of outcomes), and |Q||Q| (we assume |Q(n)|=|Q||Q^(n)|=|Q| for simplicity). For simultaneous calibeating and calibration, the first rate is for calibeating and the second for calibration. We omit polynomial dependence on K for presentation clarity, and O~ O omits logarithmic dependence on T. The simultaneous results of [FH23] are only for calibeating (but not multi-calibeating), so we only show results for calibeating for comparison. The results of [Lee+22] are only for binary outcomes. Setting Loss class Prior work This paper Calibeating Mixable – Θ(|Q|logT) (|Q| T) (Cor. 3.4, 3.7) - Brier Θ(|Q|logT) (|Q| T) 11footnotemark: 1 - Log O(|Q|logT)O(|Q| T) 11footnotemark: 1 Bounded – Θ(|Q|KT) ( |Q|KT) (Cor. 3.2, 3.6) Multi- Calibeating Mixable – Θ(logN+|Q|logT) ( N+|Q| T) (Cor. 4.3, 4.6) - Brier O((N+|Q|)logT)O((N+|Q|) T) 11footnotemark: 1 O(NT+|Q|logT)O( NT+|Q| T) 11footnotemark: 1 O~(|Q|(logN)14T34) O( |Q|( N) 14T 34) 22footnotemark: 2 Bounded – Θ(TlogN+|Q|KT) ( T N+ |Q|KT) (Cor. 4.2, 4.5) Calibeating & Calibration Brier - binary O~(|Q|23T13),O~(|Q|23T13) O(|Q| 23T 13), O(|Q| 23T 13) 11footnotemark: 1 O(|Q|logT),O~(T)O(|Q| T), O( T) (Cor. 5.2) - K-class O~(|Q|2K+1TK−1K+1),O~(|Q|2K+1TK−1K+1) O(|Q| 2K+1T K-1K+1), O(|Q| 2K+1T K-1K+1) 11footnotemark: 1 O~(|Q|+TK−1K+1),O~(TK−1K+1) O(|Q|+T K-1K+1), O(T K-1K+1) (Cor. 5.3) 11footnotemark: 1 [FH23], 22footnotemark: 2 [Lee+22] 1.2 Related Work Calibeating. In the seminal work proposing calibeating, [FH23] give online guarantees for the Brier and log losses via a bin-wise estimation viewpoint. They also study extensions to multiple forecasters and to simultaneous calibeating and calibration. [Lee+22] formulate simultaneous multi-calibration and multi-calibeating as an online multi-objective optimization problem, achieving favorable dependence on the number of external forecasters but suboptimal dependence on the time horizon. In comparison, our results are obtained via reductions that connect calibeating to standard online-learning problems. Finally, as an application, [GR23] apply calibeating as a robustness layer on top of online Platt scaling to guarantee adversarial calibration in binary classification while preserving predictive performance. Online recalibration. Online recalibration is studied in the same post-processing setting as calibeating, but it benchmarks performance by proper-loss regret rather than refinement. The goal is to achieve small regret relative to the external forecaster while simultaneously ensuring calibrated predictions [MKE25, DMK24]. For binary classification, [KE17] provide adversarial online guarantees, and [OKS24] obtain improved bounds and explicit regret versus ℓ1 _1-calibration tradeoffs via Blackwell approachability for strictly proper losses. These tradeoffs yield sublinear but typically polynomial-in-T rates. While we focus on the Brier loss in our simultaneous guarantee, we target the stronger refinement benchmark and achieve logarithmic-in-T rates while still ensuring sublinear ℓ2 _2-calibration. Calibration and proper scoring loss. Proper scoring losses admit classical decompositions into a reliability (calibration) term and an informativeness (refinement) term [Daw06, San63, Brö09]. In this spirit, ℓ2 _2-calibration [FV98] and KL-calibration [LSS25] can be viewed as online analogues of the calibration term for the Brier loss and the log loss, respectively; more generally, this motivates defining online calibration measures compatible with arbitrary proper scoring losses. Several calibration notions, including ℓ2 _2-calibration [Fis+25] and KL-calibration [LSS25], have been shown to be equivalent to swap-regret objectives. We exploit this connection in our simultaneous guarantees by enforcing (pseudo-)swap regret via the BM reduction [BM07]. 2 Model We consider an online prediction problem over a finite outcome space with N external forecasts. Let K≥2K≥ 2 be the number of possible outcomes, and ΔK≔p∈ℝ≥0K:∑k=1Kpk=1 _K \p ^K_≥ 0:Σ^K_k=1p_k=1\ be the probability simplex. We let [n][n] denote the set 1,…,n\1,…,n\ for any positive integer n. The outcome space is denoted by ℰ≔ei:i∈[K]⊆ΔKE \e_i:i∈[K]\ _K, where eie_i is the i-th standard basis vector. The interaction proceeds for T rounds. At each round t∈[T]t∈[T], the learner first observes N external forecasts, qt(n)∈ΔKq^(n)_t∈ _K, n∈[N]n∈[N], and makes its own prediction pt∈ΔKp_t∈ _K. The outcome yt∈ℰy_t is then revealed, and the learner incurs loss ℓ(pt,yt) (p_t,y_t). For simplicity, we assume that q1:T≔(qt)t=1Tq_1:T (q_t)^T_t=1 and y1:T≔(yt)t=1Ty_1:T (y_t)^T_t=1 are generated by an oblivious adversary, i.e., they are decided at time t=0t=0 with complete knowledge of the learner’s algorithm (but not its random bits). Throughout, we consider a proper scoring loss ℓ:ΔK×ℰ→ℝ : _K×E , i.e., losses such that for any q∈ΔKq∈ _K, q∈argminp∈ΔKy∼q[ℓ(p,y)]q∈ _p∈ _KE_y q[ (p,y)]. We write ℓ(p,q)≔y∼q[ℓ(p,y)] (p,q) _y q[ (p,y)]. Let ⋅1\·\ denote the indicator function, which equals one if the condition holds and zero otherwise. Given a prediction sequence p1:Tp_1:T and outcome sequence y1:Ty_1:T, for any p∈ΔKp∈ _K, denote the number of times the learner predicts p as nT(p)≔∑t=1Tpt=pn_T(p) Σ^T_t=11\p_t=p\, and the empirical outcome distribution conditioned on prediction p as ρTp(y)≔1nT(p)∑t=1Tpt=p,yt=yρ^p_T(y) 1n_T(p)Σ^T_t=11\p_t=p,y_t=y\ for y∈ℰy , whenever nT(p)>0n_T(p)>0. With these definitions, the cumulative loss, refinement score, and calibration error are defined as follows. Definition 2.1. The cumulative loss of predictions p1:Tp_1:T under outcomes y1:Ty_1:T is LT(p1:T,y1:T)≔∑t=1Tℓ(pt,yt). L_T(p_1:T,y_1:T) Σ^T_t=1 (p_t,y_t)~. The refinement score is RT(p1:T,y1:T)≔∑pnT(p)ℓ(ρTp,ρTp)=∑pminq∈ΔK∑t:pt=pℓ(q,yt). R_T(p_1:T,y_1:T) _pn_T(p) (ρ^p_T,ρ^p_T)= _p _q∈ _K _t:p_t=p (q,y_t)~. Finally, the calibration error is KT(p1:T,y1:T)≔LT(p1:T,y1:T)−RT(p1:T,y1:T). K_T(p_1:T,y_1:T) L_T(p_1:T,y_1:T)-R_T(p_1:T,y_1:T)~. By construction, LT=RT+KTL_T=R_T+K_T and KT≥0K_T≥ 0. Moreover, KTK_T coincides with the full-swap-regret notion of [Fis+25], while RTR_T corresponds to the best-in-hindsight swap-regret benchmark. Indeed, for each prediction p, the refinement term equals the loss of the best constant predictor over rounds with pt=p_t=p. Thus, the refinement score measures the informativeness of the forecasts: sequences that induce finer bins with lower within-bin variability achieve smaller refinement. In contrast, the calibration error measures within-bin reliability, i.e., how close the issued prediction p is to the empirical conditional distribution ρTpρ^p_T on the corresponding subsequence. Proper scoring losses admit a classic decomposition into terms measuring the informativeness (or refinement) of forecasts and their reliability (or calibration) in a probabilistic setting; see, e.g., [Brö09, Daw06]. Definition 2.1 can be seen as the empirical counterparts of these quantities. Example 2.2. For Brier loss ℓ(p,y)=‖p−y‖22 (p,y)=\|p-y\|^2_2, the refinement score equals the weighted sum of within-bin variances, and the calibration error becomes the ℓ2 _2-calibration [FV98], RT(p1:T,y1:T)=∑pnT(p)∑t:pt=p1nT(p)‖ρTp−yt‖22,KT(p1:T,y1:T)=∑pnT(p)‖p−ρTp‖22. R_T(p_1:T,y_1:T)= _pn_T(p) _t:p_t=p 1n_T(p)\|ρ^p_T-y_t\|^2_2~, K_T(p_1:T,y_1:T)= _pn_T(p)\|p-ρ^p_T\|^2_2~. Example 2.3. Denote the Shannon entropy under distribution p to be H(p)=−∑kpklogpkH(p)=- _kp_k p_k. For log loss ℓ(p,y)=−∑k=1Kyklogpk (p,y)=-Σ^K_k=1y_k p_k, the refinement score equals the weighted sum of the Shannon entropy within each bin, and the calibration error becomes the KL–calibration [LSS25], RT(p1:T,y1:T)=∑pnT(p)H(ρTp),KT(p1:T,y1:T)=∑pnT(p)KL(ρTp∥p). R_T(p_1:T,y_1:T)= _pn_T(p)H(ρ^p_T)~, K_T(p_1:T,y_1:T)= _pn_T(p)\,KL(ρ^p_T\|p)~. Motivated by this decomposition, [FH23] compare the learner to the external forecaster’s refinement score and define the notions of calibeating and multi-calibeating. Definition 2.4 (Calibeating and Multi-Calibeating). A learner is α(T)α(T)-multi-calibeating w.r.t. loss ℓ if for any external forecasts q1:T(n)n=1N\q^(n)_1:T\^N_n=1 and outcomes y1:Ty_1:T, the learner’s predictions p1:Tp_1:T satisfy LT(p1:T,y1:T)≤RT(q1:T(n),y1:T)+α(T),∀n∈[N]. L_T(p_1:T,y_1:T)≤ R_T(q^(n)_1:T,y_1:T)+α(T)~,∀ n∈[N]~. (1) We call α(T)α(T) the multi-calibeating rate. We say the learner is multi-calibeating if α(T)=o(T)α(T)=o(T). When (1) holds in expectation over the learner’s randomness, we call α(T)α(T) the expected multi-calibeating rate. When there is only N=1N=1 external forecast, we simply say calibeating. We also introduce another performance measure called calibration. Definition 2.5 (Calibration). A learner is β(T)β(T)-calibrated w.r.t. loss ℓ if for any outcome sequences y1:Ty_1:T (and any external forecasts), the learner’s predictions p1:Tp_1:T satisfy KT(p1:T,y1:T)≤β(T). K_T(p_1:T,y_1:T)≤β(T). (2) We call β(T)β(T) the calibration rate and say the algorithm is calibrated if β(T)=o(T)β(T)=o(T). When (2) holds in expectation over the algorithm’s randomness, we call β(T)β(T) the expected calibration rate. Note that calibeating and calibration are incomparable in general. Calibeating only guarantees that the learner’s loss is no larger than the forecaster’s loss minus the forecaster’s calibration error, i.e., it competes with the external forecaster’s refinement score. The learner’s calibration error might not vanish if it itself attains a low refinement term. 3 Calibeating == No-Regret Learning This section considers the calibeating problem, i.e., when there is only one external forecast every round. Let Q≔qt:t∈[T]Q \q_t:t∈[T]\ denote the set of distinct external forecast values that appear over the horizon.111We also use Q to denote the set of possible external forecast values for lower bound results. [FH23] study the Brier and log losses and give algorithms with calibeating rate of O(|Q|logT)O(|Q| T). We recover and extend their results by reductions to no-regret learning. First, define the regret of predictions p1:Tp_1:T under outcomes y1:Ty_1:T to be RegT(p1:T,y1:T)≔∑t=1Tℓ(pt,yt)−minp∈ΔK∑t=1Tℓ(p,yt). _T(p_1:T,y_1:T) _t=1^T (p_t,y_t)- _p∈ _K _t=1^T (p,y_t)~. We say an algorithm has (expected-)regret of α(T)α(T) if RegT(p1:T,y1:T)≤α(T)Reg_T(p_1:T,y_1:T)≤α(T) always holds (in expectation). The following theorem shows that calibeating reduces to no-regret learning. Theorem 3.1. For any proper loss ℓ and any online algorithm A with regret α(T)α(T), where α is a concave function, Algorithm 1 is |Q|α(T/|Q|)|Q|α(T/|Q|)-calibeating. Proof. The reduction partitions the rounds t∈[T]t∈[T] by the external forecast value qtq_t, and runs an independent copy of the no-regret learner A for each forecast value. Formally, for any external forecast q that appeared at least once, run a separate copy of A, denoted as q A_q, on the subset of rounds ℐq≔t:qt=qI_q \t:q_t=q\. For each subsequence, we have ∑t:qt=qℓ(pt,yt)−minp∈ΔK∑t:qt=qℓ(p,yt)≤α(nT(q)). _t:q_t=q (p_t,y_t)- _p∈ _K _t:q_t=q (p,y_t)≤α(n_T(q))~. Summing up over all the subsequences and by Definition 2.1, we have LT(p1:T,y1:T)−RT(q1:T,y1:T) L_T(p_1:T,y_1:T)-R_T(q_1:T,y_1:T) ≤∑qα(nT(q)) ≤ _qα(n_T(q)) ≤|Q|α(∑qnT(q)|Q|) ≤|Q|α ( _qn_T(q)|Q| ) (Jensen’s inequality) =|Q|α(T|Q|), =|Q|α ( T|Q| )~, which finishes the proof. ∎ Input: Online learner A. 1 for t=1t=1 to T do // prediction 2 Observe external forecasts qt∈ΔKq_t∈ _K. 3 if qt A_q_t is uninitialized then 4 Initialize a fresh copy qt← A_q_t← A. 5 Query qt A_q_t and obtain prediction pt∈ΔKp_t∈ _K. [0.5ex] // update 6 Observe outcome yty_t and incur loss ℓ(pt,yt) (p_t,y_t). 7 Update qt A_q_t with yty_t. Algorithm 1 Calibeating by Bin-Wise No-Regret We note that common regret bounds obtained for standard online algorithms are all concave in T, e.g., they are often of the form O((logT)αTβ)O(( T)^αT^β) for some α>0α>0 and β∈[0,1)β∈[0,1). The algorithm of [FH23] can be recovered as a special case of Theorem 3.1, with the online algorithm being follow–the–leader (FTL) (with a standard interior restriction for the log loss to avoid the unbounded boundary). Moreover, Theorem 3.1 readily obtains O(|Q|KT)O( |Q|KT) for bounded proper losses [LSS24] and O(|Q|logT)O(|Q| T) for mixable losses [HAK07], which encompasses Brier and log losses as special cases. Corollary 3.2. For bounded proper loss ℓ , instantiating the online learner in Theorem 3.1 with the follow-the-perturbed-leader algorithm of [LSS24] yields an algorithm with expected calibeating rate of O(|Q|KT)O( |Q|KT). We note that, inherited from the no-regret guarantees in [LSS24], the algorithm in Corollary 3.2 can actually achieve O(|Q|KT)O( |Q|KT) simultaneously for all bounded proper losses. Definition 3.3. A convex function ℓ(⋅) (·) is η-mixable if for any probability distribution π∈Δ(ΔK)π∈ ( _K), there exists a prediction pπ∈ΔKp_π∈ _K such that e−ηℓ(pπ,y)≥∫e−ηℓ(p,y)π(dp)e^-η (p_π,y)≥ e^-η (p,y)π(dp) holds for all y∈ℰy . Corollary 3.4. For an η-mixable loss ℓ (e.g., Brier and log losses), instantiating the online learner in Theorem 3.1 with exponentially weighted online optimization (EWOO) [HAK07] yields an algorithm with expected calibeating rate of O(|Q|logT)O(|Q| T). Besides the upper bound, we also prove that any lower bound for no-regret learning with a proper loss implies a lower bound for calibeating. Combining with Theorem 3.1, our results show that calibeating is minimax-equivalent to regret minimization. We defer the proof to Section A.1. Theorem 3.5. For any proper loss ℓ , denote the optimal regret bound as β(T)≔infsupy1:T∈ℰTp1:T∼[∑t=1Tℓ(pt,yt)−minp∈ΔK∑t=1Tℓ(p,yt)], β(T) _ A _y_1:T ^TE_p_1:T A [ _t=1^T (p_t,y_t )- _p∈ _K _t=1^T (p,y_t ) ]~, (3) where A ranges over (possibly randomized) online algorithms. Then, every algorithm is at best |Q|β(⌊T/|Q|⌋)|Q|β( T/|Q| )-calibeating. Combining Theorem 3.5 with known regret lower bounds for bounded proper losses [LSS24] and Brier and log losses [CL06] yields the following. Corollary 3.6. There exist bounded proper losses with calibeating rate at least Ω(|Q|KT) ( |Q|KT). Corollary 3.7. For the Brier and log losses, the calibeating rate is at least Ω(|Q|log(T/|Q|)) (|Q| (T/|Q|)). 4 Multi-Calibeating == Calibeating ++ Expert Problem Next, we consider the multi-calibeating problem. [FH23] obtain multi-calibeating rates of O((N+|Q|)logT)O((N+|Q|) T) and O(NT+|Q|logT)O( NT+|Q| T), via Blackwell approachability and online linear regression. [Lee+22] achieve a rate logarithmic in N, but polynomial in T (more precisely, O~(|Q|(logN)14T34) O( |Q|( N) 14T 34) for the optimal choice of parameters). This section presents a simple reduction from multi-calibeating to the expert problem. Via that reduction, we achieve the optimal multi-calibeating rates. Expert Problem. The interaction protocol in this problem is the same as in multi-calibeating: at each round t, the learner observes N expert predictions pt(n)n⊆ΔK \p_t^(n)\_n _K, and makes its own prediction pt∈ΔKp_t∈ _K. An experts algorithm E achieves regret γ(T)γ(T) if for every sequence (pt(1:N),yt)t=1T \(p_t^(1:N),y_t)\_t=1^T, [∑t=1Tℓ(pt,yt)]≤minn∈[N]∑t=1Tℓ(pt(n),yt)+γ(T), [ _t=1^T (p_t,y_t) ]≤ _n∈[N] _t=1^T (p_t^(n),y_t)+γ(T), (4) where the expectation is over the randomness of E. Comparing this definition of regret with the definition of multi-calibeating rate, the only difference is that the latter remaps the experts/forecasters’ predictions optimally, while the former does not. The remapping of each individual forecaster is precisely the problem of calibeating. Hence, we run a separate calibeating algorithm for each forecaster, and use an experts algorithm to aggregate their decision. See Algorithm 2 for a formal description. 1Sub-routines: 2[.5ex] • For each forecaster n∈[N]n∈[N], a separate calibeating algorithm (n) A^(n) (Algorithm 1). • Experts algorithm E [FS97, e.g., Hedge,]. for t=1t=1 to T do // prediction 3 Observe external forecasts qt(1),…,qt(N)∈ΔKq_t^(1),…,q_t^(N)∈ _K. 4 For each n∈[N]n∈[N], query (n) A^(n) with forecast qt(n)q_t^(n) to get its prediction pt(n)∈ΔKp_t^(n)∈ _K. 5 Query E with pt(n)n=1N\p_t^(n)\_n=1^N as the experts’ forecasts, and follow its prediction ptp_t. [0.5ex] // update 6 Observe outcome yty_t and update (n) A^(n) for each n∈[N]n∈[N] with this outcome. 7 Update E with ℓ(pt(n),yt) (p_t^(n),y_t) as the loss of expert n∈[N]n∈[N]. Algorithm 2 Multicalibeating by Expert Aggregation Theorem 4.1. For any loss function ℓ , any calibeating algorithm with rate α(T)α(T), and any experts algorithm with regret γ(T)γ(T), Algorithm 2 is (α(T)+γ(T))(α(T)+γ(T))-calibeating. Proof. By the regret bound of algorithm E, for any n∈[N]n∈[N], we have [LT(p1:T,y1:T)]≤LT(p1:T(n),y1:T)+γ(T). \,[L_T(p_1:T,y_1:T)]≤ L_T(p^(n)_1:T,y_1:T)+γ(T)~. By the calibeating rate of algorithm A, we have LT(p1:T(n),y1:T)≤RT(q1:T(n),y1:T)+α(T). L_T(p^(n)_1:T,y_1:T)≤ R_T(q^(n)_1:T,y_1:T)+α(T). Combining these inequalities yields a multi-calibeating rate of α(T)+γ(T)α(T)+γ(T). ∎ Let Q(n)≔qt(n):t∈[T] Q^(n) \q^(n)_t:t∈[T]\ denote the set of distinct external forecasts made by forecaster n∈[N]n∈[N]. We assume |Q(n)|=|Q| |Q^(n)|=|Q| for all n for simplicity.222Our results also hold when |Q(n)||Q^(n)|s differ across forecasters, and the resulting bounds adapt to specific forecasters. By the regret bounds of Hedge (e.g., [Bub11, Theorems 2.1 and 2.2]), and the calibeating rates in Corollaries 3.2 and 3.4, we get the following corollaries. In contrast to the loss-oblivious property of Corollary 3.2, the algorithm in Corollary 4.2 requires a fixed ℓ , as the experts algorithm relies on the loss values to update. Corollary 4.2. For any bounded proper loss ℓ , there exists an algorithm with an expected multi-calibeating rate of O(TlogN+|Q|KT)O( T N+ |Q|KT). Corollary 4.3. For any η-mixable loss ℓ (e.g., Brier and Log losses), there exists an algorithm with expected multi-calibeating rate of O(logN+|Q|logT)O( N+|Q| T). We show a minimax-equivalence of the two problems. Since now external forecasts are involved, we consider calibeating rates and expert regrets as functions of both the time round and the number of possible distinct external forecast values. Similarly to Q(n)Q^(n), given an instance of the expert problem, let P(n)≔pt(n):t∈[T] P^(n) \p^(n)_t:t∈[T]\ denote the set of possible expert predictions made by expert forecaster n∈[N] n∈[N]. We have the following theorem. Theorem 4.4. For any proper loss ℓ , suppose there exist functions ϕ,λ:ℤ2→ℝφ,λ:Z^2 such that for any T and m, infsup(q1:T,y1:T):∀n,|Q(n)|≤mp1:T∼[LT(p1:T,y1:T)−RT(q1:T,y1:T)]≥ϕ(T,m), _ A _ subarrayc (q_1:T,y_1:T ):\\ ∀ n,|Q^(n)|≤ m subarrayE_p_1:T A [L_T(p_1:T,y_1:T)-R_T(q_1:T,y_1:T) ]≥φ(T,m), where A ranges over all randomized calibeating algorithms, and, infsup(p1:T(1:N),y1:T):∀n,|P(n)|≤mp1:T∼[∑t=1Tℓ(pt,yt)−minn∈[N]∑t=1Tℓ(pt(n),yt)]≥λ(T,m), _ E _ subarrayc(p^(1:N)_1:T,y_1:T):\\ ∀ n,|P^(n)|≤ m subarrayE_p_1:T E [Σ^T_t=1 (p_t,y_t)- _n∈[N]Σ^T_t=1 (p^(n)_t,y_t) ]≥λ(T,m), where E ranges over all randomized expert algorithms. Then, infsup(q1:T(1:N),y1:T):∀n,|Q(n)|≤mp1:T∼[LT(p1:T,y1:T)−minn∈[N]RT(q1:T(n),y1:T)]≥maxϕ(T,m),λ(T,m), _ M _ subarrayc(q_1:T^(1:N),y_1:T):\\ ∀ n,|Q^(n)|≤ m subarrayE_p_1:T M [L_T(p_1:T,y_1:T)- _n∈[N]R_T(q^(n)_1:T,y_1:T) ]≥ \φ(T,m),λ(T,m) \, where M ranges over all multi-calibeating algorithms. By known lower bounds for expert problems when the expert predictions can be arbitrary values [CL06], and that the lower-bound examples can be obtained when the size of distinct expert prediction values is constant, we show the following lower bounds for multi-calibeating, matching the upper bounds. Corollary 4.5. There exist bounded proper losses under which the multi-calibeating rates are at least Ω(TlogN+|Q|KT) ( T N+ |Q|KT). Corollary 4.6. For Brier and log losses, the multi-calibeating rate of any algorithm is at least Ω(logN+|Q|log(T/|Q|)) ( N+|Q| (T/|Q|)). 5 Calibeating and Calibration at the Same Time In this section, we consider the problem of achieving simultaneous calibeating and calibration. Existing approaches focus on the Brier loss. [FH23] obtain simultaneous rates of O~(|Q|2K+1TK−1K+1)) O(|Q| 2K+1T K-1K+1)) via bin refinement and stochastic fixed-point methods, while [Lee+22] obtain O~(|Q|(logN)14T34) O( |Q|( N) 14T 34) in the binary case after parameter tuning. We focus on the Brier loss and provide new and improved bounds for simultaneous calibeating and calibration. Specifically, we provide a meta-algorithm (Algorithm 3) which, for any given external reference algorithm ∗ A^*, keeps careful track of the losses of ∗ A^* while ensuring calibration. Theorem 5.1. For Brier loss, any ε∈(0,1) ∈(0,1), and any reference algorithm ∗ A^*, Algorithm 3 simultaneously guarantees an expected regret of at most O(ε2T)O( ^2T) compared to ∗ A^*, and a calibration rate of at most OK,logT(T+1εK−1log1ε+ε2T)O_K, T( T+ 1 ^K-1 1 + ^2T) with high probability. Here, the OK,logTO_K, T notation hides a factor polynomial in K and logT T for readability. We hide the logT T factors because for the calibration error, the dominant dependence in T is polynomial, and we hide the K factors because the bounds degenerate to the trivial O(T)O(T) when K gets larger and larger. The bounds from previous works are also polynomial in K. Let ∗ A^* be a multi-calibeating algorithm from the previous sections. With ε=logT = TT, for K=2K=2, we obtain the optimal calibeating rate, improving the polynomial-in-T dependence in [FH23]. Corollary 5.2. For Brier loss with binary outcomes, there is an algorithm with an expected multi-calibeating rate of at most O(logN+|Q|logT)O( N+|Q| T), and a calibration rate of at most OK,logT(T)O_K, T( T) with high probability. With ε=(logT)1K+1 =( TT) 1K+1 for K≥3K≥ 3, we achieve the same calibration rate as in [Fis+25, FH23], and drop the |Q|−|Q|-dependence in [FH23]. Corollary 5.3. For Brier loss and K≥3K≥ 3 outcomes, there is an algorithm with an expected multi-calibeating rate of at most OK,logT(logN+|Q|+TK−1K+1)O_K, T( N+|Q|+T K-1K+1), and a calibration rate of at most OK,logT(TK−1K+1)O_K, T(T K-1K+1) with high probability. For K≥3K≥ 3 outcomes, we can also lower the multi-calibeating rate at the cost of raising the calibration rate, by choosing a different ε . Corollary 5.4. For Brier loss and K≥3K≥ 3 outcomes, for any x∈(K−3K−1,K−1K+1]x∈( K-3K-1, K-1K+1], there is an algorithm with expected multi-calibeating rate of at most OK,logT(logN+|Q|+Tx)O_K, T( N+|Q|+T^x), and a calibration rate of at most OK,logT(T(K−1)(1−x)2) O_K, T(T (K-1)(1-x)2) with high probability. 5.1 Algorithm Discretization and rounding. To achieve calibration, it is necessary to focus on a finite set of predictions via discretization. For that, we consider a triangulation of ΔK _K and randomly round each prediction to a vertex of the triangulation (recall that ℓ is fixed to the Brier loss in this section). Lemma 5.5 ([Fis+25]). For any ε∈(0,1) ∈(0,1), there is a subset of predictions ε⊂ΔKK ⊂ _K of size M=|ε|=O(Kε−K+1)M=|K |=O( K\, ^-K+1), and a rounding scheme :ΔK→Δ(ε) H: _K→ (K ) that maps an arbitrary prediction q∈ΔKq∈ _K to a distribution over those in εK , such that for any outcome y∈ℰy , we have s∼(q)[ℓ(s,y)]≤ℓ(q,y)+O(ε2)E_s H(q)\,[ (s,y)]≤ (q,y)+O( ^2). Blum-Mansour reduction. For the connection between calibration and no-swap-regret learning, we employ the well-known reduction by [BM07] with the O(logT)O( T) regret online learning algorithm for Brier loss, e.g., FTL. We present the algorithm and its proof in Section C.2. Lemma 5.6. There is an online algorithm BM A_BM that, in each step t∈[T]t∈[T], first predicts an M×M× M column-stochastic matrix AtA_t, and then observes outcome yty_t and a distribution πt∈Δ(ε) _t∈ (K ), such that for any transformation σ:ΔK→ΔKσ: _K→ _K, ∑t∈[T]pt∼Atπtℓ(pt,yt)≤∑t∈[T]pt′∼πtℓ(σ(pt′),yt)+O(MlogT+ε2T). _t∈[T]E_p_t A_t _t (p_t,y_t)≤ _t∈[T]E_p_t _t (σ(p_t ),y_t)+O (M T+ ^2T )~. Intuitively, we may interpret the column-stochastic matrix AtA_t from algorithm BM A_BM as a suggested remapping from any prediction, so that for any sequence of outcomes yty_t and distributions of predictions πt _t, the remapped/calibrated predictions are competitive against the best remapping σ in hindsight. The standard approach is then to sample a randomized prediction from the stationary distribution of AtA_t (but we will do this step later after mixing AtA_t with another remapping matrix). Interpolating between calibration and multi-calibeating. Besides achieving small swap regret and calibration rate, we also want to follow the reference prediction btb_t from algorithm ∗ A^* to be competitive against this reference algorithm. Observe that following the reference prediction corresponds to remapping every prediction to btb_t, which can be captured by a remapping matrix Bt=(bt,bt,…,bt)∈ℝM×M B_t=(b_t,b_t,…,b_t) ^M× M. To hedge between these two factors, we resort to a lopsided two-expert algorithm lopsided A_lopsided to obtain a weight wt∈[0,1]w_t∈[0,1], and take a linear combination Ct=wtAt+(1−wt)BtC_t=w_tA_t+(1-w_t)B_t as the aggregated remapping. Lemma 5.7 ([SNL14]). There is an algorithm lopsided A_lopsided for the expert problem with two experts, such that the expected regret w.r.t. expert 11 is at most O(TlogT)O( T T), and the expected regret w.r.t. expert 22 is at most O(1)O(1). Finally, we sample a prediction from the stationary distribution of CtC_t, as shown in Algorithm 3. 1Sub-routines: 2[.5ex] • Discretization and rounding algorithm H [Fis+25, see] • Reference algorithm ∗ A^* (Algorithm 1 for calibeating, Algorithm 2 for multi-calibeating). • BM reduction BM A_BM (Algorithm 4). • Lopsided two-expert algorithm lopsided A_lopsided (Algorithm 5). for t=1t=1 to T do // prediction 3 Algorithm BM A_BM predicts AtA_t. 4 Round algorithm ∗ A^*’s prediction with H to get bt∈Δ(ε)b_t∈ (K ), and let Bt=(bt,…,bt)B_t=(b_t,…,b_t). 5 Algorithm lopsided A_lopsided predicts wt∈[0,1]w_t∈[0,1]. 6 Let Ct=wtAt+(1−wt)BtC_t=w_tA_t+(1-w_t)B_t, and πt∈ΔM _t∈ _M be its stationary distribution, i.e., πt=Ctπt _t=C_t _t. 7 Predict pt∼πtp_t _t. [0.5ex] // update 8 Observe outcome yty_t. 9 Update BM A_BM and ∗ A^* based on yty_t and πt _t (applicable to the former). 10 Update lopsided A_lopsided with z∼Atπtℓ(z,yt)E_z A_t _t (z,y_t) and z∼btℓ(z,yt)E_z b_t (z,y_t) as the losses of experts 1 and 2. 11 Algorithm 3 Multi-Calibeating + Calibration 5.2 Analysis: Proof of a weaker version of Theorem 5.1 We will prove a weaker guarantee of pseudo-calibration due to space constraints and defer the rest of the proof to Section C.4. By definition, the expected cumulative loss of Algorithm 3 is LT(p1:T,y1:T)=π1:T[∑t∈[T]zt∼πtℓ(zt,yt)].E\,L_T(p_1:T,y_1:T)=E_ _1:T [ _t∈[T]E_z_t _t (z_t,y_t) ]~. Since πt _t is the stationary distribution of Ct=wtAt+(1−wt)BtC_t=w_tA_t+(1-w_t)B_t, the above further equals ∑t∈[T]zt∼Ctπtℓ(zt,yt) _t∈[T]E_z_t C_t _t (z_t,y_t) =∑t∈[T](wtzt∼Atπtℓ(zt,yt)+(1−wt)zt∼Btπtℓ(zt,yt)) = _t∈[T] (w_t\,E_z_t A_t _t (z_t,y_t)+(1-w_t)\,E_z_t B_t _t (z_t,y_t) ) =∑t∈[T](wtzt∼Atπtℓ(zt,yt)+(1−wt)zt∼btℓ(zt,yt)). = _t∈[T] (w_t\,E_z_t A_t _t (z_t,y_t)+(1-w_t)\,E_z_t b_t (z_t,y_t) )~. By construction, zt∼Atπtℓ(zt,yt)E_z_t A_t _t (z_t,y_t) and zt∼btℓ(zt,yt)E_z_t b_t (z_t,y_t) are the losses of the two-expert problem in round t∈[T]t∈[T]. The lopsided regret bounds of lopsided A_lopsided (Lemma 5.7) give LT(p1:T,y1:T) \,L_T(p_1:T,y_1:T) ≤b1:T[∑t∈[T]zt∼Atπtℓ(zt,yt)]+O(TlogT), _b_1:T [ _t∈[T]E_z_t A_t _t (z_t,y_t) ]+O( T T)~, (5) LT(p1:T,y1:T) \,L_T(p_1:T,y_1:T) ≤b1:T[∑t∈[T]zt∼btℓ(zt,yt)]+O(1). _b_1:T [ _t∈[T]E_z_t b_t (z_t,y_t) ]+O(1)~. (6) Regret w.r.t. ∗ A^*. Recall that btb_t is obtained by rounding the prediction from ∗ A^* with rounding algorithm H. By the O(ε2)O( ^2) rounding error bound of H (Lemma 5.5) and Eq. 6, the regret w.r.t. the reference algorithm ∗ A^* is at most O(ε2T)O( ^2T). Pseudo-calibration. We will prove a weaker guarantee that LT(p1:T,y1:T)≤minσ:ΔK→ΔK∑t=1Tℓ(σ(pt),yt)+O(TlogT+KεK−1logT+ε2T).E\,L_T(p_1:T,y_1:T)≤ _σ: _K→ _KE _t=1^T (σ(p_t),y_t)+O ( T T+ K ^K-1 T+ ^2T )~. This follows from Eq. 5, the guarantee of BM reduction (Lemma 5.6), and that M=O(Kε−K+1)M=O( K ^-K+1) (Lemma 5.5). It is weaker than the original statement as the choice of σ does not depend on the realization of randomness of the algorithm. By contrast, the original statement allows choosing σ based on the realization of randomness. We defer this concentration argument to Section C.4. 6 Conclusion We have revisited calibeating through the lens of online learning and developed a reduction-based framework that connects calibeating and its extensions to standard online-learning notions. This viewpoint enables us to recover and sharpen existing results, extend them to general proper scoring losses, and deliver new matching lower bounds, in a unified and modular way. A natural direction for future work is to push this approach further—both to identify additional achievable guarantees and to improve online forecasting more broadly. Another open question is whether one can simultaneously achieve an O(|Q|logT)O(|Q| T) calibeating rate and O~(T13) O(T 13) calibration for the binary case, matching the best known bounds for each objective, and whether analogous simultaneous guarantees hold beyond the Brier loss. In fact, the meta-algorithm developed in Section 5 suggests a general recipe that may apply more broadly. Whenever one can identify an appropriate discretization of the prediction space, a compatible rounding scheme with controlled loss guarantees, and a mechanism for upgrading pseudo-swap regret to true swap regret, the same framework should yield analogous extensions to other loss functions. Appendix A Omitted Proofs in Section 3 A.1 Proof of Theorem 3.5 See 3.5 Proof. We prove a general result that, for any integers Tq≥T0T_q≥ T_0 with ∑q∈QTq=T _q∈ QT_q=T, we have, infsup(q1:T,y1:T)p1:T∼[LT(p1:T,y1:T)−RT(q1:T,y1:T)]≥∑q∈Qβ(Tq). _ A _ (q_1:T,y_1:T )E_p_1:T A [L_T(p_1:T,y_1:T)-R_T(q_1:T,y_1:T) ]≥ _q∈ Qβ (T_q ). By Yao’s minimax principle, (3) implies that, for any T, there exists a distribution ST∈Δ(ℰT)S_T∈ (E^T) such that miny1:T∼ST[∑t=1Tℓ(pt,yt)−minp∈ΔK∑t=1Tℓ(p,yt)]≥β(T), _ DE_y_1:T _T [ _t=1^T (p_t,y_t )- _p∈ _K _t=1^T (p,y_t ) ]≥β(T), (7) where the minimum is over deterministic online algorithms D. For any q and the corresponding TqT_q, let Sq=STqS_q=S_T_q be the distribution guaranteed by (7) at horizon TqT_q. Define the following distribution SS over pairs(q1:T,y1:T)∈(Q×ℰ)T(q_1:T,y_1:T)∈(Q×E)^T as follows: 1. Choose disjoint index sets ℐqq∈Q\I_q\_q∈ Q with ℐq⊆[T]I_q [T], |ℐq|=Tq|I_q|=T_q and ∪q∈Qℐq=[T] _q∈ QI_q=[T]. Set qt=q_t=q for all t∈ℐqt _q. 2. For each q∈Qq∈ Q, denote the subsequence of outcomes yty_ts that t∈ℐqt _q to be yℐq=(yt)t∈ℐqy_I_q=(y_t)_t _q. Independently sample yℐqy_I_q according to SqS_q. Then by definition and the additivity of sums of expectations, min(q1:T,y1:T)∼S[LT(p1:T,y1:T)−RT(q1:T,y1:T)] _ DE_(q_1:T,y_1:T) [L_T(p_1:T,y_1:T)-R_T(q_1:T,y_1:T) ] =min(q1:T,y1:T)∼S[∑q∈Q(∑t:qt=qℓ(pt,yt)−minp∈ΔK∑t:qt=qℓ(p,yt))] = _ DE_(q_1:T,y_1:T) [ _q∈ Q ( _t:q_t=q (p_t,y_t)- _p∈ _K _t:q_t=q (p,y_t) ) ] =min∑q∈Qyℐq∼Sq[∑t:qt=qℓ(pt,yt)−minp∈ΔK∑t:qt=qℓ(p,yt)] = _ D _q∈ QE_y_I_q S_q [ _t:q_t=q (p_t,y_t)- _p∈ _K _t:q_t=q (p,y_t) ] ≥∑q∈Qminyℐq∼Sq[∑t:qt=qℓ(pt,yt)−minp∈ΔK∑t:qt=qℓ(p,yt)] ≥ _q∈ Q _ DE_y_I_q S_q [ _t:q_t=q (p_t,y_t)- _p∈ _K _t:q_t=q (p,y_t) ] ≥∑q∈Qβ(Tq). ≥ _q∈ Qβ(T_q). Therefore, since a randomized algorithm A is a probability distribution over deterministic algorithms, it holds that minsup(q1:T,y1:T)p1:T∼[LT(p1:T,y1:T)−RT(q1:T,y1:T)] _ A _ (q_1:T,y_1:T )E_p_1:T A [L_T(p_1:T,y_1:T)-R_T(q_1:T,y_1:T) ] ≥min(q1:T,y1:T)∼S[LT(p1:T,y1:T)−RT(q1:T,y1:T)]≥∑q∈Qβ(Tq). ≥ _ AE_(q_1:T,y_1:T) [L_T(p_1:T,y_1:T)-R_T(q_1:T,y_1:T) ]≥ _q∈ Qβ(T_q)~. Choosing balanced Tq∈⌊T/|Q|⌋,⌈T/|Q|⌉T_q∈\ T/|Q| , T/|Q| \ completes the proof. ∎ Appendix B Omitted Proofs in Section 4 B.1 Proof of Theorem 4.4 See 4.4 Proof. First, for any realization of expert predictions pt(n)t∈[T],n∈[N]\p^(n)_t\_t∈[T],n∈[N] and outcomes y1:Ty_1:T, consider the multi-calibeaing problem with the same outcome sequence and the external forecasts qt(n)=pt(n)q^(n)_t=p^(n)_t for any t∈[T]t∈[T] and n∈[N]n∈[N] (Recall that the experts problem and multi-calibeating only differ in the benchmarks). By Definition 2.1, RT(q1:T(n),y1:T)=∑pminu∈ΔK∑t≤T:qt(n)=pℓ(u,yt)≤∑p∑t≤T:qt(n)=pℓ(p,yt)=∑t=1Tℓ(qt(n),yt), R_T(q^(n)_1:T,y_1:T)= _p _u∈ _K _t≤ T:\,q_t^(n)=p (u,y_t)≤ _p _t≤ T:\,q_t^(n)=p (p,y_t)= _t=1^T (q_t^(n),y_t), where the inequality chooses u=pu=p in each bin. Taking minn∈[N] _n∈[N] on both sides yields minn∈[N]RT(q1:T(n),y1:T)≤minn∈[N]∑t=1Tℓ(qt(n),yt). _n∈[N]R_T(q^(n)_1:T,y_1:T)≤\ _n∈[N] _t=1^T (q_t^(n),y_t). Therefore, for any predictions p1:Tp_1:T, LT(p1:T,y1:T)−minn∈[N]RT(q1:T(n),y1:T) L_T(p_1:T,y_1:T)- _n∈[N]R_T(q^(n)_1:T,y_1:T) ≥∑t=1Tℓ(pt,yt)−minn∈[N]∑t=1Tℓ(qt(n),yt) ≥ _t=1^T (p_t,y_t)- _n∈[N] _t=1^T (q_t^(n),y_t) =∑t=1Tℓ(pt,yt)−minn∈[N]∑t=1Tℓ(pt(n),yt), = _t=1^T (p_t,y_t)- _n∈[N] _t=1^T (p^(n)_t,y_t), and multi-calibeating inherits the lower bound of the expert problem. Second, consider the instances where qt(n)=qtq^(n)_t=q_t for all t∈[T]t∈[T], which is equivalent to beating only one external forecaster. Therefore, multi-calibeating inherits the lower bound of the calibeating problem. This completes the proof. ∎ Appendix C Omitted Proofs in Section 5 C.1 Proof of Corollary 5.4 See 5.4 Proof. Let ε2T=Tx ^2T=T^x, then the calibeating rate is O(|Q(n)|logT+Tx)O(|Q^(n)| T+T^x) and ε=Tx−12 =T x-12. The corresponding calibration error is of the order O(TlogT+T(K−1)(1−x)2logT+Tx)O( T T+T (K-1)(1-x)2 T+T^x), which always has greater order than the regret. As the order of calibration error is optimized when x=(K−1)(1−x)2=K−1K+1x= (K-1)(1-x)2= K-1K+1, we consider smaller x with higher T(K−1)(1−x)2T (K-1)(1-x)2 term. The tradeoff follows by solving T(K−1)(1−x)2<T (K-1)(1-x)2<T. ∎ C.2 Algorithm BM A_BM and the proof of Lemma 5.6 1Sub-routines: 2[.5ex] • For each grid action ziz_i, a separate online learner (i) A^(i) (e.g., FTL) • Discretization and rounding algorithm H [Fis+25, see] for t=1t=1 to T do // prediction 3 for i=1i=1 to M do 4 Observe strategy qt(i)∈ΔKq^(i)_t∈ _K from Algorithm (i) A^(i). 5 Round qt(i)q^(i)_t to (qt(i))∈Δ(ε) H(q^(i)_t)∈ (K ). 6 7 Output At=((qt(1)),…,(qt(M)))∈ℝM×MA_t=( H(q^(1)_t),…, H(q^(M)_t)) ^M× M. [1.5ex] // update 8 Receive feedback tuple (yt,πt)(y_t, _t). 9 Update Algorithm (i) A^(i) with loss function πt(i)ℓ(⋅,yt) _t(i) (·,y_t). 10 Subroutine 4 BM A_BM See 5.6 Proof. Denote ε≔z1,…,zMK \z_1,…,z_M\. For any j∈[M]j∈[M] and σ(zj)∈ΔKσ(z_j)∈ _K, we have ∑tπt(j)∑iAt(i,j)ℓ(zi,yt)−∑tπt(j)ℓ(σ(zj),yt) _t _t(j) _iA_t(i,j) (z_i,y_t)- _t _t(j) (σ(z_j),y_t) =∑tπt(j)i∼(qt(j))ℓ(zi,yt)−∑tπt(j)ℓ(σ(zj),yt) = _t _t(j)E_i H(q^(j)_t) (z_i,y_t)- _t _t(j) (σ(z_j),y_t) ≤(a)∑tπt(j)(ℓ(qt(j),yt)+C2ε2)−∑tπt(j)ℓ(σ(zj),yt) (a)≤ _t _t(j) ( (q^(j)_t,y_t)+C_2 ^2 )- _t _t(j) (σ(z_j),y_t) =∑tπt(j)ℓ(qt(j),yt)−∑tπt(j)ℓ(σ(zj),yt)+C2ε2∑tπt(j) = _t _t(j) (q^(j)_t,y_t)- _t _t(j) (σ(z_j),y_t)+C_2 ^2 _t _t(j) ≤(b)C1logT+C2ε2∑tπt(j), (b)≤C_1 T+C_2 ^2 _t _t(j), for some positive constants C1,C2>0C_1,C_2>0, where (a)(a) follows from the definition of the rounding scheme and the upper bound of the rounding error (Lemma 5.5); (b)(b) holds by that FTL has a regret of O(logT)O( T) under the Brier loss. Summing this inequality over all j∈[M]j∈[M], we obtain ∑t=1Ti∼Atπtℓ(zi,yt)−∑t=1Tj∼πtℓ(σ(zj)) Σ^T_t=1E_i A_t _t (z_i,y_t)-Σ^T_t=1E_j _t (σ(z_j)) =∑t=1T∑j=1Mπt(j)∑i=1MAt(i,j)ℓ(zi,yt)−∑j=1Mπt(j)ℓ(σ(zj),yt) = _t=1^T _j=1^M _t(j) _i=1^MA_t(i,j) (z_i,y_t)- _j=1^M _t(j) (σ(z_j),y_t) =MC1logT+C2ε2∑t=1T∑j=1Mπt(j) =MC_1 T+C_2 ^2Σ^T_t=1Σ^M_j=1 _t(j) ≤maxC1,C2(KlogTεK−1+ε2T), ≤ \C_1,C_2\ ( K T ^K-1+ ^2T ), where in the last inequality, we use M=O(KεK−1)M=O( K ^K-1) in Lemma 5.5. ∎ C.3 Algorithm lopsided A_lopsided Input: learning rate η∈(0,12]η∈(0, 12], initial weights s1,1−s1\s_1,1-s_1\ 1 for t=1t=1 to T do // prediction 2 Output weight wt=stst+1−s1w_t= s_ts_t+1-s_1. [1.5ex] // update 3 Receive loss z∼Atπtℓ(z,yt)E_z A_t _t (z,y_t) and z∼btℓ(z,yt)E_z b_t (z,y_t) as the losses of experts 1 and 2, respectively. 4 Compute δt=gt(2)−gt(1) _t=g_t^(2)-g_t^(1) and set st+1=st⋅(1+ηδt)s_t+1=s_t·(1+η _t). Subroutine 5 lopsided A_lopsided[SNL14] C.4 Concentration arguments to finish the proof of Theorem 5.1 We finish the proof of Theorem 5.1 by upper-bounding the true calibration error using bounds of the pseudo-calibration error. For convenience, denote the pseudo-calibration error under an algorithm A to be K~T≔minσ:ΔK→ΔKpt∼[∑t=1Tℓ(pt,yt)−∑t=1Tℓ(σ(pt),yt)] K_T _σ: _K→ _KE_p_t A [Σ^T_t=1 (p_t,y_t)-Σ^T_t=1 (σ(p_t),y_t) ]. The following lemma is a multiclass extension of Theorem 3 in [LSS25], relating K~T K_T to the calibration error. Lemma C.1. For the Brier loss, for discretization with size M and an algorithm A that always predicts the discretization grid points, with probability at least 1−δ1-δ over the randomness in A’s predictions p1,…,pTp_1,…,p_T, we have KT(p1:T,y1:T)≤6K~T+96KMlog4KMδ. K_T(p_1:T,y_1:T)≤ 6 K_T+96KM 4KMδ. Therefore, together with the weaker version proved in Section 5.2 and M=O(1εK−1)M=O( 1 ^K-1), we have KT(p1:T,y1:T) K_T(p_1:T,y_1:T) ≤O(TlogT+1εK−1(K1/2logT+K3/2log4K3/2εK−1)+ε2T−logδ) ≤ O ( T T+ 1 ^K-1 (K^1/2 T+K^3/2 4K^3/2 ^K-1 )+ ^2T- δ ) =OK,logT(T+1εK−1log1ε+ε2T), =O_K, T ( T+ 1 ^K-1 1 + ^2T ), with probability at least 1−δ1-δ. C.5 Proof of Lemma C.1 We first note the following fact on the closed-form of KTK_T and K~T K_T. Fact C.2. For the Brier losses, the calibration error under prediction sequence p1:Tp_1:T and outcome sequence y1:Ty_1:T is KT=∑p∈ΔK∑t=1Tpt=p‖p−ρTp‖22=∑p∈ΔK∑t=1Tpt=p∑k=1K(p(k)−ρTp(k))2, K_T= _p∈ _KΣ^T_t=11\p_t=p\\|p-ρ^p_T\|_2^2= _p∈ _KΣ^T_t=11\p_t=p\Σ^K_k=1 (p(k)- _T^p(k) )^2, where ρTp=∑t:pt=pytnT(p)ρ^p_T= _t:p_t=p y_tn_T(p). The pseudo-calibration error under algorithm A and outcome sequence y1:Ty_1:T is K~T=∑t=1Tp∼Pt[‖p−ρT(p)~‖2]=∑t=1T∑pPt(p)∑k=1K(p(k)−ρ~Tp(k))2, K_T=Σ^T_t=1E_p P_t [\|p- _T(p)\|^2 ]=Σ^T_t=1 _pP_t(p)Σ^K_k=1 (p(k)- ρ^p_T(k) )^2, where Pt(p)P_t(p) is the randomized prediction under algorithm A and ρ~Tp≔∑t=1TytPt(p)∑t=1TPt(p) ρ^p_T Σ^T_t=1y_tP_t(p)Σ^T_t=1P_t(p). Denote the iith grid point by ziz_i in the discretization, and ρTp(k)ρ^p_T(k) as ρi(k)ρ^i(k) for simplicity. For any k∈[K]k∈[K], let KT(k)≔∑i∈[M]∑t=1Tpt=zi(zi(k)−ρi(k))2, K_T(k) _i∈[M]Σ^T_t=11\p_t=z_i\ (z_i(k)-ρ^i(k) )^2, and K~T(k)≔∑i∈[M]∑t=1TPt(zi)(zi(k)−ρ~i(k))2. K_T(k) _i∈[M]Σ^T_t=1P_t(z_i)(z_i(k)- ρ^i(k))^2. We have the following lemma. Lemma C.3. With probability at least 1−δ1-δ, KT(k)≤6K~T(k)+96Mlog4MδK_T(k)≤ 6 K_T(k)+96M 4Mδ. Then, with a union bound across k∈[K]k∈[K], with probability at least 1−δ1-δ, we have KT=∑k=1KKT(k)≤∑k=1K(6K~T(k)+96Mlog4MKδ)=6K~T+96MKlog4MKδ. K_T=Σ^K_k=1K_T(k)≤Σ^K_k=1 (6 K_T(k)+96M 4MKδ )=6 K_T+96MK 4MKδ. C.6 Proof of Lemma C.3 See C.3 While the proof of Lemma C.3 follows almost exactly as the proof of Theorem 3 in [LSS25], we include it here for completeness. Proof of Lemma C.3. The proof relies on the following version of Freedman’s inequality. Lemma C.4 ([Bey+11]). Let Xii=1n\X_i\^n_i=1 be a martingale difference sequence adapted to the filtration ℱ1⊆⋯⊆ℱnF_1 ·s _n, where |Xi|≤B |X_i |≤ B for all i∈[n]i∈[n], and B is a fixed constant. Define :=∑i=1n[Xi2∣ℱi−1]V:= _i=1^nE [X_i^2 _i-1 ]. Then, for any fixed μ∈[0,1B],δ∈[0,1]μ∈ [0, 1B ],δ∈[0,1], with probability at least 1−δ1-δ, we have |∑i=1nXi|≤μ+log2δμ. | _i=1^nX_i |≤ + 2δμ. Fix i∈[M]i∈[M] and define the martingale difference sequence Xt≔yt(k)(Pt(i)−pt=zi)X_t y_t(k)(P_t(i)-1\p_t=z_i\) and Yt≔Pt(i)−pt=ziY_t P_t(i)-1\p_t=z_i\. Observe that |Xt|≤1|X_t|≤ 1, |Yt|≤1|Y_t|≤ 1 for all t. Fix μi∈[0,1] _i∈[0,1]. Applying Lemma C.4 to the sequence X≔Y≔X1:TX Y X_1:T, Y1:TY_1:T and taking a union bound over them, we obtain that with probability at least 1−δ1-δ, |∑t=1Tyt(k)(Pt(i)−pt=zi)|≤μiX+log4δμi,|∑t=1TPt(i)−pt=zi|≤μiY+log4δμi, | _t=1^Ty_t(k) (P_t(i)-1 \p_t=z_i \ ) |≤ _iV_X+ 4δ _i,~ | _t=1^TP_t(i)-1 \p_t=z_i \ |≤ _iV_Y+ 4δ _i, (8) where XV_X, YV_Y are given by X=∑t=1T[Xt2∣ℱt−1]=∑t=1Tyt(k)⋅Pt(i)(1−Pt(i))≤∑t=1TPt(i), and _X= _t=1^TE [X_t^2 _t-1 ]= _t=1^Ty_t(k)· P_t(i) (1-P_t(i) )≤ _t=1^TP_t(i), and Y=∑t=1T[Yt2∣ℱt−1]=∑t=1TPt(i)(1−Pt(i))≤∑t=1TPt(i). _Y= _t=1^TE [Y_t^2 _t-1 ]= _t=1^TP_t(i) (1-P_t(i) )≤ _t=1^TP_t(i). The upper tail ρi(k)−ρ~i(k)ρ^i(k)- ρ^i(k) can then be bounded in the following manner: ρi(k)−ρ~i(k) ρ^i(k)- ρ^i(k) =∑t=1Tyt(k)pt=zi∑t=1Tpt=zi−∑t=1Tyt(k)Pt(i)∑t=1TPt(i) = _t=1^Ty_t(k)1 \p_t=z_i \ _t=1^T1\p_t=z_i\- _t=1^Ty_t(k)P_t(i) _t=1^TP_t(i) ≤(a)∑t=1Tyt(k)pt=zi∑t=1Tpt=zi+μi∑t=1TPt(i)+log4δμi−∑t=1Tyt(k)pt=zi∑t=1TPt(i) (a)≤ _t=1^Ty_t(k)1\p_t=z_i\ _t=1^T1\p_t=z_i\+ _i _t=1^TP_t(i)+ 4δ _i- _t=1^Ty_t(k)1\p_t=z_i\ _t=1^TP_t(i) =∑t=1Tyt(k)pt=zi(∑t=1Tpt=zi)(∑t=1TPt(i))⋅(∑t=1TPt(i)−∑t=1Tpt=zi) = _t=1^Ty_t(k)1\p_t=z_i\ ( _t=1^T1\p_t=z_i\ ) ( _t=1^TP_t(i) )· ( _t=1^TP_t(i)-Σ^T_t=11\p_t=z_i\ ) +μi∑t=1TPt(i)+log4δμi∑t=1TPt(i) = + _i _t=1^TP_t(i)+ 4δ _i _t=1^TP_t(i) ≤(b)∑t=1Tyt(k)pt=zi(∑t=1Tpt=zi)(∑t=1TPt(i))⋅(μi∑t=1TPt(i)+log4δμi) (b)≤ _t=1^Ty_t(k)1\p_t=z_i\ ( _t=1^T1\p_t=z_i\ ) ( _t=1^TP_t(i) )· ( _i _t=1^TP_t(i)+ 4δ _i ) +μi∑t=1TPt(i)+log4δμi∑t=1TPt(i) = + _i _t=1^TP_t(i)+ 4δ _i _t=1^TP_t(i) ≤(c)2μi+2log4δμi∑t=1TPt(i), (c)≤2 _i+ 2 4δ _i _t=1^TP_t(i), where (a) and (b) follow from (8), and (c) follows by yt(k)pt=zi≤pt=ziy_t(k)1\p_t=z_i\ 1\p_t=z_i\. The lower tail can be bounded in an exact manner as ρ~i(k)−ρi(k) ρ^i(k)-ρ^i(k) =∑t=1Tyt(k)Pt(i)∑t=1TPt(i)−∑t=1Tyt(k)pt=zi∑t=1Tpt=zi = _t=1^Ty_t(k)P_t(i) _t=1^TP_t(i)- _t=1^Ty_t(k)1\p_t=z_i\ _t=1^T1\p_t=z_i\ ≤∑t=1Tyt(k)pt=zi+μi∑t=1TPt(i)+log4δμi∑t=1TPt(i)−∑t=1Tyt(k)pt=zi∑t=1Tpt=zi ≤ _t=1^Ty_t(k)1\p_t=z_i\+ _i _t=1^TP_t(i)+ 4δ _i _t=1^TP_t(i)- _t=1^Ty_t(k)1\p_t=z_i\ _t=1^T1\p_t=z_i\ =∑t=1Tyt(k)pt=zi(∑t=1TPt(i))(∑t=1Tpt=zi)⋅(∑t=1Tpt=zi−∑t=1TPt(i)) = _t=1^Ty_t(k)1\p_t=z_i\ ( _t=1^TP_t(i) ) ( _t=1^T1\p_t=z_i\ )· ( _t=1^T1\p_t=z_i\-Σ^T_t=1P_t(i) ) +μi∑t=1TPt(i)+log4δμi∑t=1TPt(i) = + _i _t=1^TP_t(i)+ 4δ _i _t=1^TP_t(i) ≤∑t=1Tyt(k)pt=zi(∑t=1Tpt=zi)(∑t=1TPt(i))⋅(μi∑t=1TPt(i)+log4δμi) ≤ _t=1^Ty_t(k)1\p_t=z_i\ ( _t=1^T1\p_t=z_i\ ) ( _t=1^TP_t(i) )· ( _i _t=1^TP_t(i)+ 4δ _i ) +μi∑t=1TPt(i)+log4δμi∑t=1TPt(i) = + _i _t=1^TP_t(i)+ 4δ _i _t=1^TP_t(i) ≤2μi+2log4δμi∑t=1TPt(i). ≤ 2 _i+ 2 4δ _i _t=1^TP_t(i). Combining both bounds, we have shown that for a fixed μi∈[0,1] _i∈[0,1], |ρi(k)−ρ~i(k)|≤2μi+log4δμi∑t=1TPt(i)|ρ^i(k)- ρ^i(k)|≤ 2 _i+ 4δ _iΣ^T_t=1P_t(i) holds with probability at least 1−δ1-δ. Taking a union bound over all i, with probability 1−δ1-δ, the following holds simultaneously for all i, |∑t=1Tyt(k)(Pt(i)−pt=zi)| | _t=1^Ty_t(k) (P_t(i)-1\p_t=z_i\ ) | ≤μi∑t=1TPt(i)+log4Mδμi, ≤ _i _t=1^TP_t(i)+ 4Mδ _i, (9) |∑t=1TPt(i)−pt=zi| | _t=1^TP_t(i)-1\p_t=z_i\ | ≤μi∑t=1TPt(i)+log4Mδμi, ≤ _i _t=1^TP_t(i)+ 4Mδ _i, (10) |ρi(k)−ρ~i(k)| |ρ^i(k)- ρ^i(k) | ≤2μi+2log4Mδμi∑t=1TPt(i). ≤ 2 _i+ 2 4Mδ _i _t=1^TP_t(i). (11) Consider the function g(μ):=μ+aμg(μ):=μ+ aμ, where a≥0a≥ 0 is a fixed constant. Clearly, minμ∈[0,1]g(μ)=2a _μ∈[0,1]g(μ)=2 a when a≤1a≤ 1, and 1+a1+a otherwise. Minimizing the bound in (11) with respect to μi _i, we obtain |ρi(k)−ρ~i(k)|≤4log4Mδ∑t=1TPt(i), when log4Mδ≤∑t=1TPt(i),2+2log4Mδ∑t=1TPt(i), when log4Mδ>∑t=1TPt(i). |ρ^i(k)- ρ^i(k) |≤ cases4 4Mδ _t=1^TP_t(i), when 4Mδ≤ _t=1^TP_t(i),\\ 2+ 2 4Mδ _t=1^TP_t(i), when 4Mδ> _t=1^TP_t(i). cases Therefore, when ∑t=1TPt(i) _t=1^TP_t(i) is tiny, which is possible if algorithm A does not allocate enough probability mass to the index i, the bound obtained is large making it much worse than the trivial bound |ρi(k)−ρ~i(k)|≤1 |ρ^i(k)- ρ^i(k) |≤ 1 which follows since ρi(k),ρ~i(k)∈[0,1]ρ^i(k), ρ^i(k)∈[0,1] by definition. Based on this reasoning, we define the set ℐ:=i∈[M], s.t. log4Mδ≤∑t=1TPt(i), := \i∈[M], s.t. 4Mδ≤ _t=1^TP_t(i) \, (12) and let ℐ¯≔[M]∖ℐ I [M] . We bound (ρi(k)−ρ~i(k))2(ρ^i(k)- ρ^i(k))^2 as (ρi(k)−ρ~i(k))2≤16log4Mδ∑t=1TPt(i) if i∈ℐ,1 otherwise. (ρ^i(k)- ρ^i(k) )^2≤ cases 16 4Mδ _t=1^TP_t(i)& if i ,\\ 1& otherwise. cases (13) Similarly, |∑t=1TPt(i)−pt=zi| | _t=1^TP_t(i)-1\p_t=z_i\ | can be bounded by substituting the optimal μi _i obtained above in (10); we obtain |∑t=1TPt(i)−pt=zi|≤2log4Mδ∑t=1TPt(i) if i∈ℐ∑t=1TPt(i)+log4Mδ otherwise. | _t=1^TP_t(i)-1\p_t=z_i\ |≤ cases2 4Mδ _t=1^TP_t(i)& if i \\ _t=1^TP_t(i)+ 4Mδ& otherwise. cases (14) Equipped with (13) and (14), we proceed to bound KT(k)K_T(k) in the following manner: KT(k) K_T(k) =∑i∈[M]∑t=1Tpt=zi(zi(k)−ρi(k))2 = _i∈[M] _t=1^T1\p_t=z_i\ (z_i(k)-ρ^i(k) )^2 ≤2∑i∈[M]∑t=1Tpt=zi((zi(k)−ρ~i(k))2+(ρi(k)−ρ~i(k))2), ≤ 2 _i∈[M] _t=1^T1\p_t=z_i\ ( (z_i(k)- ρ^i(k) )^2+ (ρ^i(k)- ρ^i(k) )^2 ), where the inequality holds because (a+b)2≤2a2+2b2(a+b)^2≤ 2a^2+2b^2 for all a,b∈ℝa,b . To further bound the term above, we split the summation into two terms 1,2T_1,T_2 defined as 1 _1 :=∑i∈ℐ∑t=1Tpt=zi((zi(k)−ρ~i(k))2+(ρi(k)−ρ~i(k))2), := _i _t=1^T1\p_t=z_i\ ( (z_i(k)- ρ^i(k) )^2+ (ρ^i(k)- ρ^i(k) )^2 ), 2 _2 =∑i∈ℐ¯∑t=1Tpt=zi((zi(k)−ρ~i(k))2+(ρi(k)−ρ~i(k))2), = _i∈ I _t=1^T1\p_t=z_i\ ( (z_i(k)- ρ^i(k) )^2+ (ρ^i(k)- ρ^i(k) )^2 ), and bound 1T_1 and 2T_2 individually. We bound 1T_1 as 1 _1 ≤(a)∑i∈ℐ(∑t=1TPt(i)+2log4Mδ∑τ=1TPτ(i))((zi(k)−ρ~i(k))2+16log4Mδ∑τ=1TPτ(i)) (a)≤ _i ( _t=1^TP_t(i)+2 4Mδ _τ=1^TP_τ(i) ) ( (z_i(k)- ρ^i(k) )^2+ 16 4Mδ _τ=1^TP_τ(i) ) =∑i∈ℐ∑t=1TPt(i)(zi(k)−ρ~i(k))2+16log4Mδ|ℐ|+ = _i _t=1^TP_t(i) (z_i(k)- ρ^i(k) )^2+16 4Mδ|I|+ 2∑i∈ℐlog4Mδ∑τ=1TPτ(i)((zi(k)−ρ~i(k))2+16log4Mδ∑τ=1TPτ(i)) = 2 _i 4Mδ _τ=1^TP_τ(i) ( (z_i(k)- ρ^i(k) )^2+ 16 4Mδ _τ=1^TP_τ(i) ) ≤(b)∑i∈ℐ∑t=1TPt(i)(zi(k)−ρ~i(k))2+16log4Mδ|ℐ|+ (b)≤ _i _t=1^TP_t(i) (z_i(k)- ρ^i(k) )^2+16 4Mδ|I|+ 2∑i∈ℐ∑τ=1TPτ(i)((zi(k)−ρ~i(k))2+16log4Mδ∑τ=1TPτ(i)) = 2 _i _τ=1^TP_τ(i) ( (z_i(k)- ρ^i(k) )^2+ 16 4Mδ _τ=1^TP_τ(i) ) =3∑i∈ℐ∑t=1TPt(i)(zi(k)−ρ~i(k))2+48log4Mδ|ℐ| =3 _i _t=1^TP_t(i) (z_i(k)- ρ^i(k) )^2+48 4Mδ|I| where (a) follows by substituting the bounds from (13) and (14); while (b) follows since by the definition of ℐI in (12), we have log4Mδ∑τ=1TPτ(i)≤∑τ=1TPτ(i) 4Mδ _τ=1^TP_τ(i)≤ _τ=1^TP_τ(i). Next, we bound 2T_2 as 2 _2 ≤(a)∑i∈ℐ¯(2∑t=1TPt(i)+log4Mδ)((zi(k)−ρ~i(k))2+1) (a)≤ _i∈ I (2 _t=1^TP_t(i)+ 4Mδ ) ( (z_i(k)- ρ^i(k) )^2+1 ) ≤(b)2∑i∈ℐ¯∑t=1TPt(i)(zi(k)−ρ~i(k))2+2∑i∈ℐ¯∑t=1TPt(i)+2log4Mδ|ℐ¯| (b)≤2 _i∈ I _t=1^TP_t(i) (z_i(k)- ρ^i(k) )^2+2 _i∈ I _t=1^TP_t(i)+2 4Mδ| I| ≤(c)2∑i∈ℐ¯∑t=1TPt(i)(zi(k)−ρ~i(k))2+4log4Mδ|ℐ¯| (c)≤2 _i∈ I _t=1^TP_t(i) (z_i(k)- ρ^i(k) )^2+4 4Mδ| I| where (a) follows by substituting the bounds from (13) and (14); (b) follows by bounding (zi(k)−ρ~i(k))2≤1(z_i(k)- ρ^i(k))^2≤ 1; and (c) follows from the definition of ℐI in (12). Collecting the bounds on 1T_1 and 2T_2, we obtain 1+2 _1+T_2 ≤3∑i∈[M]∑t=1TPt(i)(zi(k)−ρ~i(k))2+48log4Mδ|ℐ|+4log4Mδ|ℐ¯| ≤ 3 _i∈[M] _t=1^TP_t(i) (z_i(k)- ρ^i(k) )^2+48 4Mδ|I|+4 4Mδ| I| ≤3K~T(k)+48Mlog4Mδ, ≤ 3 K_T(k)+48M 4Mδ, where the last inequality follows from the definition of K~T(k) K_T(k) and since |ℐ|+|ℐ¯|=M|I|+| I|=M. Since KT(k)≤2(1+2)K_T(k)≤ 2 (T_1+T_2 ), we have shown that KT(k)≤6K~T(k)+96Mlog4Mδ, K_T(k)≤ 6 K_T(k)+96M 4Mδ, with probability at least 1−δ1-δ. This completes the proof. ∎ References [Bey+11] Alina Beygelzimer et al. “Contextual Bandit Algorithms with Supervised Learning Guarantees” In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics 15, Proceedings of Machine Learning Research Fort Lauderdale, FL, USA: PMLR, 2011, p. 19–26 URL: https://proceedings.mlr.press/v15/beygelzimer11a.html [BM07] Avrim Blum and Yishay Mansour “From External to Internal Regret” In Journal of Machine Learning Research 8.47, 2007, p. 1307–1324 URL: http://jmlr.org/papers/v8/blum07a.html [Brö09] Jochen Bröcker “Reliability, sufficiency, and the decomposition of proper scores” In Quarterly Journal of the Royal Meteorological Society 135.643, 2009, p. 1512–1519 DOI: https://doi.org/10.1002/qj.456 [Bub11] Sébastien Bubeck “Introduction to Online Optimization”, 2011 URL: https://w.microsoft.com/en-us/research/publication/introduction-online-optimization/ [CL06] Nicolo Cesa-Bianchi and Gabor Lugosi “Prediction, Learning, and Games” Cambridge University Press, 2006 [Daw06] Philip Dawid “Probability Forecasting” In Encyclopedia of Statistical Sciences New York, NY: WileySons, 2006 [DMK24] Shachi Deshpande, Charles Marx and Volodymyr Kuleshov “Calibrated Regression Against An Adversary Without Regret”, 2024 arXiv: https://arxiv.org/abs/2302.12196 [FH23] Dean Foster and Sergiu Hart “”Calibeating”: beating forecasters at their own game” In Theoretical Economics 18.4, 2023, p. 1441–1474 URL: https://econtheory.org/ojs/index.php/te/article/view/20231441/0 [Fis+25] Maxwell Fishelson et al. “Full Swap Regret and Discretized Calibration” In Proceedings of The 36th International Conference on Algorithmic Learning Theory 272, Proceedings of Machine Learning Research PMLR, 2025, p. 444–480 URL: https://proceedings.mlr.press/v272/fishelson25a.html [FS97] Yoav Freund and Robert E Schapire “A decision-theoretic generalization of on-line learning and an application to boosting” In Journal of Computer and System Sciences 55.1 Elsevier, 1997, p. 119–139 [FV98] Dean P. Foster and Rakesh V. Vohra “Asymptotic calibration” In Biometrika 85.2, 1998, p. 379–390 DOI: 10.1093/biomet/85.2.379 [GR23] Chirag Gupta and Aaditya Ramdas “Online Platt Scaling with Calibeating” In Proceedings of the 40th International Conference on Machine Learning 202, Proceedings of Machine Learning Research PMLR, 2023, p. 12182–12204 URL: https://proceedings.mlr.press/v202/gupta23c.html [Guo+17] Chuan Guo, Geoff Pleiss, Yu Sun and Kilian Q. Weinberger “On Calibration of Modern Neural Networks” In Proceedings of the 34th International Conference on Machine Learning 70, Proceedings of Machine Learning Research PMLR, 2017, p. 1321–1330 URL: https://proceedings.mlr.press/v70/guo17a.html [HAK07] Elad Hazan, Amit Agarwal and Satyen Kale “Logarithmic regret algorithms for online convex optimization” In Machine Learning 69.2 Springer, 2007, p. 169–192 [KE17] Volodymyr Kuleshov and Stefano Ermon “Estimating uncertainty online against an adversary” In Proceedings of the AAAI Conference on Artificial Intelligence 31.1, 2017 [Lee+22] Daniel Lee, Georgy Noarov, Mallesh Pai and Aaron Roth “Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications” In Advances in Neural Information Processing Systems 35 Curran Associates, Inc., 2022, p. 29051–29063 URL: https://proceedings.neurips.c/paper_files/paper/2022/file/ba942323c447c9b9d4b638eadefab9-Paper-Conference.pdf [LSS24] Haipeng Luo, Spandan Senapati and Vatsal Sharan “Optimal Multiclass U-Calibration Error and Beyond” In Advances in Neural Information Processing Systems 37 Curran Associates, Inc., 2024, p. 7521–7551 DOI: 10.52202/079017-0241 [LSS25] Haipeng Luo, Spandan Senapati and Vatsal Sharan “Simultaneous Swap Regret Minimization via KL-Calibration”, 2025 arXiv: https://arxiv.org/abs/2502.16387 [MKE25] Charles Marx, Volodymyr Kuleshov and Stefano Ermon “Calibrated Probabilistic Forecasts for Arbitrary Sequences”, 2025 arXiv: https://arxiv.org/abs/2409.19157 [OKS24] Princewill Okoroafor, Bobby Kleinberg and Wen Sun “Faster Recalibration of an Online Predictor via Approachability” In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics 238, Proceedings of Machine Learning Research PMLR, 2024, p. 4690–4698 URL: https://proceedings.mlr.press/v238/okoroafor24a.html [San63] Frederick Sanders “On Subjective Probability Forecasting” In Journal of Applied Meteorology and Climatology 2.2 Boston MA, USA: American Meteorological Society, 1963, p. 191–201 DOI: 10.1175/1520-0450(1963)002¡0191:OSPF¿2.0.CO;2 [SNL14] Amir Sani, Gergely Neu and Alessandro Lazaric “Exploiting easy data in online optimization” In Advances in Neural Information Processing Systems 27 Curran Associates, Inc., 2014 URL: https://proceedings.neurips.c/paper_files/paper/2014/file/8cfb39d9174128beb141866808bd154e-Paper.pdf