Calibrated Probabilistic Forecasts for Arbitrary Sequences
Authors: Charles Marx
Volodymyr Kuleshov
Stefano Ermon
Venue: Accepted by TMLR ()

Abstract: Real-world data streams can change unpredictably due to distribution shifts, feedback loops and adversarial actors, which challenges the validity of forecasts. We present a forecasting framework ensuring valid uncertainty estimates regardless of how data evolves. Leveraging the concept of Blackwell approachability from game theory, we introduce a forecasting framework that guarantees calibrated uncertainties for outcomes in any compact space (e.g., classification or bounded regression). We extend this framework to recalibrate existing forecasters, guaranteeing calibration without sacrificing predictive performance. We implement both general-purpose gradient-based algorithms and algorithms optimized for popular special cases of our framework. Empirically, our algorithms improve calibration and downstream decision-making for energy systems.

Published in Transactions on Machine Learning Research (03/2025)
Calibrated Probabilistic Forecasts for Arbitrary Sequences
Charles Marx Deportment of Computer Science Stanford University
clmarz@cs.stan/frrdcoo
Volodymyr Kuleshov
kuleshov@cornelll.ce
Department of Computer Science Cornell Tech
Stefano Ermon
ermon@cs.stanfordd edu
Deportment of Computer Science Stanford University
Reviewed OpenReview: https: oppnrrvvepeerevieuu net/ forum? id= 1u
Abstract
Real-world data streams can change unpredictably due to distribution shifts, feedback loops and adversarial actors, which challenges the validity of forecasts. We present forecasting framework ensuring valid uncertainty estimates regardless of how data evolves. Leveraging the concept of Blackwell approachabilitty from game theory, we introduce forecasting framework that guarantees calibrated uncertainties for outcomes in any compact space (e.g., classification or bounded regression). We extend this framework to recalibrate cxisting forecasters, guarantecing calibration without sacrificing predictive performance. We implement both general-purpose gradient- based algorithms and algorithms optimized for popular special cases of our framework. Empirically, our algorithms improve calibration and downstream decision-makinn for energy systems.
1 Introduction
Machine learning models are often used in settings where data changes unpredictably after deployment. For example, in modical diagnosis, cpidemiological trends can induce distribution shifts, altering the prevalence of diseases in a population. Furthermore, a model's predictions can impact future observations through feedback such as in financial forecasting (De Long et al. 1990), adaptive experimentation (Deshpande & Kuleshov 2021), preventative medicine (Adam et al. 2020). and predictive policing (Ensign al. (0188) where the model's deployment induces nonstationarity in future data. Even more challenging, in settings such security, regulation, and game playing, data may be chosen adversarially to invalidate predictions.
Accurate uncertainty estimates are crucial for informed decision-making in dynamic environments. This work addresses the challenge of maintaining forecast reliability despite adversarial or unpredictable data shifts. Take for example, an electrical grid operator tasked with using energy generation and load forecasts ensure reliable energy supply. Uncertainty estimates are nceded to evaluate the risk of different management decisions, allowing the operator to guard against unfavorable outcomes. Additionally, providing probabilistic forecasts opposed to only suggesting decisions allows the operator to incorporate domain knowledge into the decision process.
To address the need for uncertainty estimation with nonstationary data, we consider probabilistic forecasting task for an arbitrary (potentially adversarial) data stream. This raises the question: How can we argue for the validity of probabilistic forecasts for events that may be unrelated to past observations, or even deterministically chosen invalidate predictions? One approach is appeal to calibration, which says that in the long run, the observed frequency of event should match its probability under the forecasts DDwid 1982. Foster &

---

Published in Transactions on Machine Learning Research (03/2025)
Vohra 1998 Vovk al 2005 In other words, in hindsight the data stream should resemble samples drawn from the forecasted distributions.
In this work, we study the scope of calibration guarantees that can be provided for forecasts of (potentially) adversarial data. We consider a stream of outcomes on any compact metric space, encapsulating both classification tasks and regression for bounded outcomes. Building on a stream of work connecting calibration to Blackwell approachability (Blackwell, 1956; Foster, 1999; Abernethy et al.) 2011 Perchet, 2013), we model the forecasting task zero-sum game played between the Forecaster and Nature. We design the payoff (i.e., "win condition") of this game to measure the calibration and predictive performance of the forecasts. This allows us to give a general thcoretical procedure to enforee any form of calibration that meets mild regularity conditions. This procedure and its accompanying calibration guarantees serve as proof that most popular forms of calibration can be enforced without any assumptions about how the data stream evolves, with miscalibration decaying in time as O(1/VT) However, implementing this procodure is in some cases computationally hard. Thus, we study particular forms of calibration which can be guaranteed by tractable algorithms, and give gradient-based algorithms that offer greater generality the cost. of worse guarantees. This allows us to enforce new forms of calibration in online settings, such as decision calibration (Zhao et al. 2021b) and distribution calibration (Song et al. 2019 Furthermore, we can combine multiple notions of calibration, for example simultancously enforcing moment- matching and quantile calibration.
Robustness to adversarial data is valuable since it alleviates the need to make unverifiable assumptions about the future. However, most real-world data is not truly adversarial: it unlikely that nature is conspiring to choose the weather to invalidate weather forecasts. Many forecasters make assumptions that are approximately valid and, as result, make more accurate predictions. A good forecasting strategy should be able to benefit from this domain knowledge. Thus, we also apply our methodology as post-processing procedure to achieve no-regret recalibration for existing forecasters; given a set of expert forecasters and a scoring rule, we construct forecasts that asymptotically match the score of the best forecaster, while also guarantecing calibration.
Our main ributioooo are:
1. We propose a unifying framework for calibration in online learning, describing how many forms of calibration can be expressed as payoffs in repeated game.
2. We provide finite-sample calibration guarantees via a theo forecasting procedure that applies to any form of calibration fitting into our framework.
3. We introduce ORCA, a novel gradient-based algorithm to implement the forecasting procodure, and efficient algorithms optimized for specific forms of calibration.
4. We perform two empirical studies applying ORCA to recalibrate forecasters on regression tasks, demon- strating its ability to improve both calibration and downstream decisions.
2 Problem Setting
Consider probabilistic forecasting task, where the goal of the Forecaster is to give a probability distribution for the next outcome in a sequence (e.g., the weather tomorrow). At each time step /.- = 1,2,..., Nature reveals features E X (e.g., today's temperature and air pressure). Next, Forecaster chooses a forecast pt in A()), the space of probability distributions over an outcome space y. Finally, Nature reveals the outcome ye E V. The outcome space y is assumed to be a compact metric space, such as a finite set labels in classification or bounded interval regression, We make no assumptions about the feature space X.
Online Learning Forecaster has access the history and the features when choosing the forecast pt = Forecaster(hh--1,z))) where h-11 represents the history of all data and forecasts through time - 1. Nature then observes the forecast before choosing the outcome y4 = Nature(hu-1,25 2t, We allow for the possibility that Nature acts adversarially, choosing whichever outcome is least. favorable for Forecaster. In this sense, the task can be viewed as a zero-sum repeated game played between Forecaster and Nature. The generality of the online learning paradigm mcans our algorithms and thcorctical results apply for any sequence of features and outcomes (zt, Ve) over X V. In particular, our guarantees hold for nonstationary data generating processes arising due to distribution shifts, feedback loops, time series, and adversarial actors.
2

---

Published in Transactions on Machine Learning Research (03/2025)
Calibration A notion of calibration represents property would expect to observe if each outcome V were sampled independently from the forecast pt. For example, suppose y/ E {0, 1) is binary and Pt E [0. 1] is a forecasted probability that y/: = 1. In the batch setting, where {(z,, yr) 3t) Y==1 are i..d. random variables (e.g., a held-out test datasct), binary distribution calibration says that ( = 1 pt = p) 2 p for all forecasts p E ())) that occur sufficiently often. In the online setting, outcomes are an arbytrary sequence and not nocessarily random variables, so the probabilistic definition is not well-defined. Instcad, we define calibration analogously via empirical frequencies
1 1 (1- 1, R.P.
lim T-000
Ete1 1
where the indicator variable { is 1 if the event E occurs and 0 otherwise (Vovk et al. 2005 The indicator {pr x p} is a continuous approximation to the function II flpe pl S }} for small e (see Section for discussion). In words, Equation [ says that when the forecast Pr is close to any fixed value p. the fraction of times that y/ approaches p. Calibration requires that this holds for all p E [o, 1] such that pt = p with nonzero frequency in the limit of large T, i.e., lim inf T Σ (pr = p) > 0.
1
Blackwell Approachability Blackwell's Approachability Theorem gives sufficient conditions under which player in a repeated zero-sum game can control vector-valued payoff, when averaged over the rounds of the game. In each round, t = 1,,,.... two players, Forecaster and Nature, sequentially choose actions ae A and b, E B, respectively, yielding vector-valued payoff x xa, by) RT Forecaster's goal is to drive the average payoff दт + Ei= x(a,, by) towards target set C RTh, while Nature trics to prevent this. The distance between the average payolf and the target set is defined as d(FT, E) infage || - -||- A set & is approachable if Forecaster
ensure that d( + 0 as T 00, regardless of Nature's strategy. For our purposes, the target set is the origin & {0]. Blackwell (1566) showed that Eg is approachable if Forecaster can ensure the payoff lies in a halfspace defined by the average payoff, regardless of Nature's action:
inf sup (F(a,b), S0, VT E
(2)
aEA bEB
3 The Forecasting Game
In this section, we express popular forms of calibration as the average payoff in a zero-sum game played between Forecaster and Nature. Forecaster's actions are distributions p E A()), and Nature's actions are outcomes y y. In subsequent sections, show how to achieve these notions of calibration from unified theoretical (Section 4 and algorithmic (Section 5) perspective.
Procedure Probabilistic Forecasting
for 1,2,
Nature reveals features I2 E X' Forecaster predicts distribution Pt E A()) Nature reveals outcome Yl E y
Forecaster receives payoff π ((I,, V.) E H.
end for
The payoff क (xF Pt, ye) reflects the error of the forecast Pe for features ia and outcome ye, and takes values in an arbitrary Hilbert space H (e-g., a scalar or vector). The average payoff up to time T denoted as मा = + Ei= Pt, We are interested in the inner product norm | = / ( TT) n which for vector-valued payoffs is the familiar Euclidean norm.
Definition 3.1. The misculibration of forecasts P1.P2..... for features 3T, T2, ET and outcomes F1, yr with respect to a payoff π is the norm of the average payoff, || A sequence of forecasts is calibrated if the miscalibration vanishes, that is | + T + co.
We now give concrete examples of how calibration can be encoded as payoff to demonstrate the versatility of Procedure 1 as abstraction for calibration.
3

---

Published in Transactions on Machine Learning Research (03/2025)
Binary Calibration As a simple example, consider binary label indicating whether it rains (y = 1) or not (y- 0). Forecaster wants to ensure that on days she predicts rain with probability p. the observed frequency of rain is also p. We use vector payoff indexed by a discrete set of probabilities p E [0, 1], with entries ( Pt. Pt. = 1 {pr R p} (yt- - p). This induces the miscalibration measure || = Ep p (_x.T) - p)² where Np.T is the number of days Ps p and fp. is the frequency of the event Ye 1 when Pt 2 p, up to day T. This closely resembles the Expected Calibration Error (Guo et al. 2017). except using L2 norm on the errors instead of an L1 norm.
Quantile Calibration In regression setting, let Pt be the predicted distribution for the daily high temperature Yt E R. Quantile calibration requires that for any quantile E [o, 1] (e.g., the median), the proportion of days yt falls below the q-quantile of Pt is g (e.g. half the time). We use a vector payoff indexed by discrete set of quantiles q, given by (2, Pt, Me) = (Fp, (y+) S q} - q, where Fp, is the edf of pr- The induced miscalibration measure, known as the Quantile Calibration Error (Kuleshov el. al. 2018), is || = Eg (fg.r - - where fgr is the frequency of the event Fp, (yx) S q up to day T.
Moment Matching Beyond binary and quantile calibration, different notions of faithfulness are relevant. depending the intended use or interpretation of the forecast. For example, if temperature forecasts are used to predict the mean or variability of the temperature over a period, it is crucial for the averaged moments of the forecasts to match those of the data. This can be measured using the payoff (T( Pt. M1) = Ey- [v*] vi indexed by moments i E (1. The induced miscalibration metric || measures the squared error in the forecasted moments. We can match additional moments of the forecasts and data with k >>>>> 2, eventually requiring that the marginal distributions match exactly when k goes to co.
Decision Calibration Forecasts directly influence decision- decision-makinn in areas such as adaptive experimental
design (Desppande et al., 2024), model predictive control (Garcia et al., 1989). and model-based reinforcement learning (Malik et al.j 2019). In these scenarios, decision-makers must trust that forecasts accurately reflect the utility of each available action A. For instance, to evaluate whether forecasts systematically undervalue overvalue any action, can use the payoff (a Pc, 3/) = Eyrop, u(a, y, xz) u(a, yt, 24), indexed by actions a E A, where u(a, v. is the utility of action a with outcome in context x. A decision-maker should also be concerned if she experiences swap regret (Blum & Mansour 2007). wherein she could increase her utility by swapping all occurrences of some action a with another action d'. This possibility can be measured using the payoff indexed by pairs of actions (a, a'), given by Ta, (It, Pt, Me) = 1 {a' = 6(p,,,)) (Eyrp, [u(a, y, 2121)] u(a. yr, zt)), where 8(pr, is the Bayes optimal action when y is distributed according to Pt with context It. By controlling these notions of calibration, Forecaster can accurately evaluate the average utility of each action and make decisions with vanishing swap regret.
A General Recipe The above payoffs have shared structure, which can be abstracted into general payoff function of the form ( p.3) c(x, p) @ (Eyrop [ur(y/)] - w(y)), where e and w are vector-valued functions and 8 is the outer product. Here, w is a "witness function" " specifying the quantitics that should match on average between the forecasts and outcomes, and e is a "conlext function" specifying the conditioning events under which the quantitics should match. Under weak conditions (see Appendix A), calibration can be achieved online for any payoff of this form.
4 Winning the Forecasting Game with Provable Calibration
In the previous section, we described how calibration can be expressed using payoff functions. In this section, use this framework to describe a general forecasting strategy that guarantees miscalibration decreases O(1/VT). Furthermore, we provide a unified approach to enforce multiple forms of calibration simultancously. Our strategy requires solving an optimization problem which is computationally hard for some forms of calibration. In Section we propose an inexact but tractable approach using gradient-based optimization.
Our work builds on a recent stream of work that leverages Blackwell approachability and relatod fixed- poodt theorems to study calibration in online learning (Perchet 2013 Vovk et al., 22055: Abernethy et al.) 2011 Lee
et al.
2022 Gupta & Ramdas 2022
Noarov & Roth 2023 Our primary theoretical contributions are twofold.
4

---

Published in Transactions on Machine Learning Research (03/2025)
In Section 411 we establish general conditions for achieving calibration, accommodating arbitrary compact outcome spaces and nonconvex calibration metrics. In Section 4.2. we describe framework to simultaneously achieve multiple measures of calibration and performance with a unified optimization procedure. Proofs for all results can be found in Appendix
4.1 An Existence Result for Online Calibration
First, we introduce three mild assumptions about the payoff function that underpin our main results. I
Condition (Boundedness). The norm of the payoff is bounded by B pe || P. vill <00. Condition 2 (Consistency). The expected payoff is zero when the outcome is drawn from the forecost: Lynp [π( p. v)] = 0, Vz Xp E A(Y).
Condition 3 (Continuity). The payoff is continuous function of the forecast p (x.,p.)) A()) under the Wasserstein metric, Vr E x., V.
The first condition ensures that a single bad prediction has bounded impact on the cumulative miscalibration. The second condition encodes the requirement that calibration measure is optimized by perfect forecast. The third condition requires that the payoff is continuous. For any discontinuous payoff, continuity can be achieved by smoothing the payoff an arbitrarily small scale.
Our main result follows from two observations. The first observation is a simple argument that bounds miscalibration in terms of the inner product between the current and average payoff. Proposition 4.1. If the payoff is bounded (Condilion then
B < T
2 T
|
Σ
Ta 1 (Ft (r,))t
(3)
Proposition 4.1
implies that if we can ensure the inner product in Equation nonpositive, then miscalibration
will decrease as || < R. The second observation guarantees that this inner product be made nonpositive, regardless of Nature's play.
Proposition 4.2. If the payoff is consistent (Condition 2 and continuous (Condition 3 then for all and x E X, there erists forecast p A(V) such that
max (T, (T, S. yEY
(4)
Proposition 4.2 is proven by using continuity to invoke the Ky Fan minimax incquality, and consistency to ensure that the resulting bound is nonpositive. Together, these results suggest. a forecasting strategy which we formalize in Algorithm [ play forecasts satisfying the halfspace condition of Equation 4 making the second term of Equation nonpositive, and guaranteeing that || < S.
Identifying the specific forecast that satisfies the halfspace inequality Equation can be difficult. For now, assume access to oracle HalfSpaceOraale(zz.c) that returns a forecast p satisfying Equation This oracle is tasked with solving the following minimax optimization problem over p:
min max (T(...P.)) m.). pEA()) yEy
(5)
whose optimal solution p. is guaranteed by Proposition implementation of the oracle to Section 5
4.2
to achieve (IT Vt), O. We defer the
Theorem 4.3. If the payoff satisfies Conditions
3 then Algorithm
i has miscalibration bounded by
| < B/T for any sequence (
Theorem 4.3 follows directly from Propositions and 4.2 and gives a finite-sample calibration guarantee.
Importantly, we make no convexily assumptions about the payolI, and allow for payolls in a Hilbert space, which is usefuul for infinite dimensional payoffs that arise in regression. Thus, this generalizes existing results that require discrete outcomes and a bilincar payoff (c.g., VVok et al. 2005 Kakade & Foster 20088.. In conclusion, we can achieve general notions of calibration for nonstationary data caused by foedback loops, distribution shifts, time series, and adversarial environments.
5

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm Blackwell Porecasting
Require: Payoff HalfSpacoOracle
To +- 0H
1/ Initialize avg payoff as zero
for t= 1,2.... do
Nature reveals features I; E X
for a distribution Pt that satisfies the inequality Announce forecast Pt, observe outcome yt, and receive payoff (x,, Pt, vc) // Update wvg payoll
Query HallSpaccOraall((11111
maxyey (-1 x (F y)
T. f- [-1 ? Th + (te, Wt)
end for
4.2 Multi-Objective and No- Jo-Regret Recalibration
Robustness adversarial data allows avoid making assumptions about the data generating process. However, in practice most forecasting tasks not truly adversarial; Nature is most likely not conspiring for the weather to contradict weather forecasts. In this section, we describe how to apply Algorithm D as post-processing step for another forecaster. This allows us to take advantage of the inductive biases and valid assumptions of other forecasters, while maintaining guarantees if those assumptions fail. Our work extends recalibration techniques from the offline setting (e.g.. Kuleshov et al., 2018 Marx et al. 2024) to nonstationary data. recent stream of work on "calibeating" studies recalibration in the online setting (Foseer & Hart 2023), and perhaps most relevant our work Lee et al. (2022). The most significant differences between Lee al. (2022 and our work that give deterministic forecasts and do not require discretization.
Specifically, our goal is to guarantee calibration while simultaneously achieving loss comparable to known expert forecasters. We begin by defining a standard notion of regret. Let ((p, y) be a bounded and contimuous real-valued proper scoring rule, where smaller values indicate a better forecast. We are given expert forecasters, whose forecasts at each step are provided as features x (sI,..., Here, x; E A()) is a distribution representing the forecast made by expert i. The regret with respect to the best performing expert is given by
T E(p m.
T Σ
Σ R = T
min 18isk
(6)
We can bound this regret term in the framework of Blackwell approachability via the k-dimensional payoff whose ith entry the excess loss relative to the ith expert, n RBG (M,P.9) = E(p. v) f(x,,)) y)- The norm of the average payoff then satisfies
REG RT
(c,
- REG
(x.p.v)ll R2
Thus, we can treat the regret as simply another payoff that we optimize using Algorithm | See Appendix A.1 for the details of this comparison. To achieve calibration with no-regret guarantee, we note that Forecaster control multiple payoffs simultaneously with the same O(1/VT) time dependency.
Proposition 4.4. Let (I),,..,, (n) be n payoff functions laking values in Hilberl spaces Hi,..., Hn...,,,,,,, re- spectively. Suppose each payoff ((0 satisfies the Conditions 13 with bound B, Applying Algorithm - to 7 1t IE Bi, and using the normalized payoff
the direct sum payoff (1)) @ ... + (1) ensures E
x1) ① ... + (1) ensures | I. < nB, for sis n.
Thus, we can match the performance up to an 0 /T) gap of any expert forecaster, while guarantecing multiple forms of calibration.

---

Published in Transactions on Machine Learning Research (03/2025)
5 Algorithms
In the previous section, we gave calibration guarantees for a forecasting strategy that assumed access to an oracle solution to a minimax optimization problem. In this section we describe algorithms to implement this oracle. Since this optimization problem is PPAD-hard in some cases (Hazan & Kakade 2012). an efficient algorithm must compromise on either generality or the strength of the guarantees. We consider both approaches, first giving a general gradient-based optimization strategy without strong guarantees, and then providing tractable oracles for specialized payoffs.
5.1 Gradient-Based Blackwell Forecasting
Tractable half-space oracles are attractive in that they guarantee calibration. However, there are two important outstanding limitations: first, some payoff functions do not admit tractable oracles, as indicated by computational hardness results (Hazan & Kakade 2012). Sccond, it is not casy to combine tractable oracles for individual payofls into oracles for multiple payolis; given two payoff functions TI and T2 each with a tractable oracle, it is not clear how to use the oracles to construct a tractable oracle for Tı @ T2- To mitigate these issues, we introduce Online Regression Calibration against an Adversary (ORCA), a gradient-based approach for solving the oracle minimax problem. ORCA iteratively optimizes an upper bound on the miscalibration (i.e., the minimax inner product). Tf that upper bound drops below zero, we can control miscalibration. If the upper bound remains positive because we fail to identify global optimum of the nоnconvex oplimization problem, then we play the best identified forecast, with miscalibration limited by the identified upper bound. Thus, while ORCA does not guarantee calibration, we know before observing the outcome whether it is possible for the miscalibration to worsen. Additionally, we can casily combine multiple payoffs by concatenating them, without needing to adjust the optimization algorithm.
Parameterizing the Forecasts We introduce two parameterized families of distributions over the outcome space: one for the forecast distributions and one for the adversarial outcome distributions. The forecast lamily is given by P {Po 0 E Ø}, and should be flexible enough to approximate any outcome distribution to guarantee the existence of solution to the half-space oracle problem. For example P could be neural network that represents the PDF or CDF of the forecast, or a parametric family of mixture distributions (e.g., 8 encodes the means, variances, and mixture weights of a Gaussian mixture). Note that the parameters describe a distribution Po over the outcome space, not model weights mapping inputs to distribution.
To enable efficient gradient-based optimization, we give Nature the option to play a randomized outcome, represented by distribution q E A()). Since Nature plays last in each round, this does not affect the optimal solution to the minimax problem. The adversary family Q {9s E dagk : & E R 5x 2 0, T 1} is chosen to be mixture distribution with fixed components (q)...., ,K) for th A()), and flexible mixture weights (e.....,kk) Similarly, the adversary family should be flexible enough to approximate any distribution over the outcome space, to ensure the oracle does not underestimate the worst-case miscalibration.
Gradient-Based Optimization Each single forecast requires solving an optimization problem over the forecast family. However, note that this optimization is over relatively small space on the order of the 10's or 100's of parameters composing 0. Using the above parameterizations, we write the half-space oracle task (Equation as
min max pEAD) yEy
T
min max E [(TT-- 7 (F.,, PEA()) (EA()) you
(8)
min max Σ K BEB AEAL-1
Øk y-g
[ (x,, Pe- 8))]
(9)
is the probability simplex. The first equality holds because the worst-case outcome is equivalent to the worst-case oulcome distribution, due to the linearity of the expectation. The second (approximate) equality replaces the full space of distributions with the parameterized families we will optimize over. When the components 4s are Dirac measures (making 9s a Categorical distribution), we can compute the expectation analytically. In general, we can also approximate the expectation using Monte Carlo simulation. Now, the inner maximization problem is linear program (IP) in the mixture weights o,
where A = fo E : 0,
7

---

// Initialize aug payoff as zero Published in Transactions on Machine Learning Research (03/2025)
which can solve in (K33.)) time (Amos & Kolter 2017). When solving the outer minimization problem. we differentiate through the LPP solution using differentiable convex optimization solvers (Agrawal et al.) 2019). We now have a minimization task over 0 with differentiable objective, which we can optimize using standard gradient- based optimizers such as Adam (Kingma & Ba. 2014). The full forecasting strategy for ORCA summarized in Algorithm
The Impacts of Approximation Since exact optimization of Equation replaced the sets over which we perform the maximization (Nature's task) and the minimization (Forecaster's task) with parameterized familics. The approximation of the maximization weakens Nature, which may lead to underestimale the cost of the worst-case oulcome. However, the impact of this approximation be bounded. Let Nature's optimal score be denoted by A" := maXgEA()) youg
S is intractable, in Equation we
I ( P. y)l], and
Nature's optimal realizable score be denoted by A max E de E - v) Let Sa. yo-ax an e-net of y, meaning Additionally, suppose that the payoff I (2, (x,,,))
be the support of each distribution qu in ion 9 Denote the greatest diameter of these supports by d == maxk=l.... diam(S&), and denote their union by S S Suppose that
that for all y E ) there cxists some S such that |ly s|| S is L-Lipschitz in y for all X and p E A()). Then, it is easy to show that 0 S A' - A I (d+c)L 11 This bound controls the error in our estimate of the worst-case miscalibration for any particular forecast.
Conversely, the approximation of the minimization in Equation weakens Forecaster. If the forecast family is not sufficiently expressive, then we may overlook the best forecast. However, note that this approximation does not weaken Nature, so while this approximation can prevent us from identifying the optimal worst-case miscalibration guarantee, the validity of the guarantee do identify preserved.
Algorithm ORCA:
Gradient-Based Blackwell Forecasting
Require: Payoff म, Forecast set P, Adversary set Q No + 0z
for t= = 1, do
Nature reveals features Iz E X Initialize Pa, P while not converged do
Compute (0;; 2, R), the worst-case miscalibration for pe, from the LP solver.
// Equution
Update 8, using gradient-basod optimization to minimize (0,; Q)
end while
Announce forecast Pe., observe outcome and receive payoff T2,, Pt, Mt)
H. f L + (s..
1/ Update ang payoff
end for
5.2 Algorithms for Specialized Notions of Calibration
Algorithm 2 is easy to implement, works with any differentiable payoff, supports no-regret recalibration, and performs well in practice. For many definitions of calibration, we can also design specific half-space oracles that provably achieve the desired notion of calibration, but they need to be handcrafted for each calibration type (sce Appendix Ch.
There erist half-space oracles for quantile calibration, distribution calibration, moment-based calibration, and decision calibration, which provably solve the half-space problem.
Theorem 5.1.
The time and space complexity for each algorithm is typically O(1/c²) for some k: > 0 (c.g., the number of moments); see Appendix C In simple settings (binary calibration and adaptive conformal inference), we provide O(log(1/e) ))) algorithms. In general, the exponential dependence on & is inevitable, as even for k-class classification, the optimization problem PPAD-hard (Hazan & Kakade 2012).
Additionally, in Appendix D we include results for specialized algorithms for no-regret recalibration, which guarantee convergence at the cost of added complexity.
8

---

Published in Transactions on Machine Learning Research (03/2025)
wind
sunspot
Forecaster
QCE
SMAPE
QCE
SMAPE
Cumulative Quantlle Callbration Error
0.5
stochastic gradient trees
0.163
0.403
0.100
0.505
isotonic
0.246
0.554
0.242
1.081
ORCA (ours)
0.013
0.405
0.045
0.513
stochastic gradient trees
neural network
0.142
0.353
0.048
network
F isotomic
0.121
0.567
Hoelfding free
ORCA (ours)
0.083
0.307
0.042
0.453
merginal
ORCA
Hoetfding tree
0.212
0.545
0.072
0.432
+ isotonic
0.186
0.428
0.116
1.061
+ ORCA (ours)
0.016
0.431
0.040
0.479
marginal
0.126
0.545
0.046
0.534
+ isotonic
0.094
0.359
0.084
1.016
+ ORCA (ours)
0.017
0.391
0.040
0.576
0.0
60
100
Step
Table 1: Comparison of two recalibration techniques, isotonic (Kuleshov et al. 2018) and ORCA (ours) real-world data. The goal is to reduce miscalibra- tion (QCE), while maintaining predictive performance (SMAPE). The best value is bolded and values within 10% of best are underlined.
Figure 1: Comparison of cumulative quantile cali- bration error (QCE) for ORCA and basclines under adversarially generated data crafted to maximize QCE for each method. Results are averaged over 10 runs, with solid lines showing the mean QCE and shaded regions indicating one standard deviation.
6 Experiments
We perform three experiments to evaluate the ability of ORCA to recalibrate forecasts on regression tasks. the first experiment, we test whether ORCA can improve calibration without worsening predictive performance for four different online learning models on two regression tasks. In the second experiment, we apply ORCA to data that is adversarially selected to maximize miscalibration. In the third experiment, simulate decision task for wind farm operator test whether ORCA improves downstream decision-making,
6.1 Recalibrating Online Learners
Expert Forecasters We recalibrate forecasts from four online learning algorithms implemented in the River online learning library (Montiel et al.] 2021). namely stochastic gradient trees (Gouk et al. 2019), a neural network, Hoeffding adaptive trees BBfet & Gavalda 2009). and a naive forecaster that predicts the distribution of historical outcomes.
ORCA Implementation We apply ORCA to recalibrate the predictions of each expert forecaster. We parameterize the action spaces of Forecaster and Nature for the minimax optimization task both as piece- wise constant densities 50 evenly-spaced subsets of the outcome space. We find that using similar parametrizations for Forecaster and Nature is important for preventing them from leveraging limitations in each other's expressive capacity. For the payoff function, we use combined payoff enforcing quantile calibration, no-regret for the Continuous Ranked Probability Score (CRPS) and Mean Squared Error (MSE) metrics, and moment-matching for the first two moments. We perform 400 update steps with the Adam optimizer (Kingma & Ba 2014 to solve the minimax optimization task.
Datasets We consider two regression tasks. The wind dataset consists of hourly wind energy generation in ERCOT for the year of 2022 (of Texas 2022). The sunspot dataset (Clette et al.) 2014 is standard forecasting benchmark where the lask is lo predict the total monthly sunspots. For each dalaset, we forecast. for 1000 time steps, using lag features from the previous 24 steps.
Metrics We evaluate predictive performance using the Symmetric Mean Absolute Percentage Error (SMAPE), defined as SMAPE = $ - Tprl w/ 2 where dr is the mean of the forecast Pt- We evaluate calibration using the Quantile Calibration Error (QCE). For the set of test quantiles (0.01, 0.02. ... 0.99),
Iy -

---

Published in Transactions on Machine Learning Research (03/2025)
Bagging Trees
Recallbrated
Decision Loss
0.8
0.5
0.4
20
40
60
80
Day
Figure 2: Comparison of the decision loss incurred by decisions based on expert forecasts before and after recalibration with ORCA. The solid line indicates the instantaneous decision loss at each step, and the dashed line indicates the mean value over the entire period. Lower values are better.
the QCE defined as -CE=Eneh (Ja.T x)²; where Jar is the frequency of the event F,, (y:) S g up to day T. The QCE checks whether y/ exceeds each quantile of the forecasts with the expected frequency.
Bascline Comparison We compare ORCA to isotonic recalibration Kuleshov et al. 2018 a popular technique for recalibrating predictions in a batch setting. At each time step 4, we fit. an isotonic recalibrator based on the data up to time and apply to recalibrate the expert forecast at time +
Results The experimental results are displayed in Table I We find that ORCA significantly improved calibration error, while minimally impacting predictive performance. Applying ORCA improved calibration in all 8 of the settings we tested, decreasing QCE by between 13% and 92% depending on the dataset and model. ORCA minimally impacted SMAPE, increasing SMAPE by less than 10% in 7 out of 8 cases, and even decreasing it in 2 cases. ORCA consistently outperformed isotonic recalibration in terms of QCE across all datasets and models.
6.2 Adversarial Prediction Task
In addition to real-world datasets, we evaluate ORCA on adversarially generated data. We consider a regression task for outcomes in the unit interval y = [o, 1], and with no features 2t. In each round t, Forecaster predicts distribution Pt A()), then Nature deterministically chooses the outcome Yt maximize the quantile calibration error (QCE) for that forecast. The goal of the forecaster is to minimize the QCE, so this is a zero-sum game between Forecaster and Nature.
Whereas ORCA is used to recalibrate other forecasters in Section here ORCA receives no other forecast. as input. The forecast parameterization is the same as in Scction 6.1 and the payoff function enforces quantile calibration error. The results of the adversarial prediction experiment are shown in Figure I We observe that ORCA consistently achieves lower QCE than the baselines we consider.
6.3 Wind Farm Decision Task
In this experiment, we demonstrate how ORCA can be used to inform downstream decisions with decision calibration. We design an experiment similar to (Zhao et al. 2021a). in which a wind farm operator submits a future generation plan to grid operator each day. On each day, the operator announces commitment at e R for cach hour i = 1,... 24 of the next 24-hour period, and receives a penalty depending on the deviation between the offered and actual generation, given by E(ae. v+) 24 X) (3) (
- ++++11 A) 1 "
10

---

Published in Transactions on Machine Learning Research (03/2025)
Given probabilistic forecast for energy generation over each of the next 24 hours, we choose the set of commitments that minimize the expected loss under the forecasted distributions. We then compare the decision losses incurred by a bagging trees forecaster to those incurred by forecasts recalibrated using ORCA. The results of the decision-making experiment are displayod in Figure 2 We observe that applying ORCA consistently improves the reamstream decision loss.
7
Related Work
Calibration has been studied in both online and offline machine learning. In the offline setting, calibration measures have been designed for a variety of data types and applications, inchuding quantile calibration (Kuleshov et al., 2018); binary calibration (Song et al.) 2019). decision calibration (Zhao et al. 2021b), threshold calibration (Sahoo et al.) [202]), marginal calibration (Gnciting et al.] 2007), kernel calibration (Widmann al.] 2022), and local calibration (Luo et al., (022). Conversely, existing work in the online setting focuses binary calibration, with few notable exceptions discussed below. Our work can be viewed as extending the breadth of calibration mcasures defined in the offline setting to the online setting.
Interest in calibrated online forecasting dates back to the 1980's
Dawid
1982).
An existing line of work
studies calibration for classification tasks (Abernethy et al. 2011 Gupta & Ramdas
2022 Okoroafor et al.
2023
Foster & Vohra 1998 Kakade & Foster 2008 Perchet 2013 Vovk et al., 2005 Kuleshov Ermon
2017), where connections between calibration and Blackwell's approachability theorem Blackwell] 1956) are
well-known. Furthermore, Okoroafor et al. (2023) give methods for no-regret recalibration in classification.
Foster & Hart 2
introduce calibeating, method for improving calibration while maintaining sharpness, therefore improving performance as mcasured by a proper scoring rule. Many previous analyses (e.g.,
Abernethy et al. 2011 Gupta & Ramdas 2022 Perchet 2013) leverage the bilinearity of the payoff function in classification tasks to invoke a fixed point theorem such as von Neumann's minimax theorem (Von Neumann & Morgenstern, 1947) or Sion's minimax theorem (Sion 1958). Similarly, the proposed algorithms in these works tend to be specialized to a specific form of calibration and data, In contrast, study nonconvex payoffs, such as for quantile calibration in regression, necessitating the new existence criteria we derive. Furthermore, computational hardness results in this general sctting motivate ORCA, our gradient-based calibration method. ORCA can easily be applied to any differentiable payoff or combination of payoffss making it more broadly applicable than existing specialized methods.
Okoroafor et al.) 2023
Noarov & Roth 2023 is also closcly related to our work, as they study general class of calibration measures that satisfy an elicitability criterion. Two important distinctions between our work and Noarov & Roth (023) are that they require randomized forecasts while we give deterministic forecasts, and they discretize the forecast space while we use continuous forecast space. Other recent work extends online calibration to
include multicalibration (Gupta et al.
2021
Bastani et al. 2022 Lee et al., 2022 Garg et al. 2024] and
conformal prediction (Gibbs & Candes
2021
Angelopoulos et al. 2023
8 Conclusion
This work presents a novel framework for calibrated probabilistic forecasting for sequences over any compact outcome space. To implement our framework, we introduce generally-applicable gradient- based algorithms and provide specialized algorithms for common forecasting scenarios. Empirically, we find that our methods improve calibration and decision-making when used for recalibration in energy systems. Investigating the
connections between Blackwell forecasting, multicalibration /Gupta et al. 2021 Noarov & Roth 2023 and
omnicalibration (Garg et al. 2024) is an interesting direction for future work.
For example, the Expected Calibration Error (Guo et al., 2017) is discontimuous due to the binning of the forecasts, and no-regret rocalibration with respect to the nogative log likelihood yields an unbounded payoff. Discontinuity issues can be mitigated by applying miniscule kernel smoothing to the payoff function (c.g., assigning a forecast near a discontinuity partially in each neighboring bin) and boundedness issues can be mitigated by clipping-
Limitations Some common calibration metrics do not satisfy Conditions 13 3
11

---

Published in Transactions on Machine Learning Research (03/2025)
Additionally, while theoretical results apply to nondifferentiable payoffs, in practice ORCA requires differentiability to facilitate gradient-based optimization. Smoothing nondifferentiable payoffs creates a deviation between the objective being optimized and the true calibration objective. In practice, we find that this distinction is small enough that performance is not significantly impacted.
Broader Impacts Uncertainty estimates, and particularly those that hold under weak assumptions, support the responsible and safe deployment of machine learning systems. We hope this work enables broader adoption of uncertainty-awan decision processes by providing generally applicable calibration methods. Still, calibration is property of collections of predictions, and should be used cautiously when considering individual prediction.
References
Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 27-46- 46. JMLR Workshop and Conference Proceedings, 2011.
George Alexandru Adam, Chun-Hao Kingsley Chang, Benjamin Haibe-Kains, and Anna Goldenberg. Hidden risks of machine learning applied to healthcare: unintended feedback loops between models and future data causing model degradation. Machine Learning for Healthcare Conference, pp. 710 731. PMLR, 2020.
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. Tn International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Anastasios N Angelopoulos, Emmanuel J Candes, and Ryan J Tibshirani. Conformal pid control for time serics prediction. arXiv preprint arXiv:2307.1688) 2023.
Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances in Newral Information Processing Systems, 35:29362 35:29362-29873, 2022.
Albert Bifet and Ricard Gavalda. Adaptive learning from evolving data streams. In Advances in Intelligent Dala Analysis VIII: 8th International Symposium on Intellignt Dala Analysis, IDA 2009, Lyon, France, August 31-September 2, 2009. Proceedings 8, pp. 249 260. Springer, 2009.
Patrick Billingsley. Probabilily and measure. John Wiley & Sons, 2017.
David Blackwell. An analog of the minimax theorem for vector payoffs. 1956.
Avrim Bhum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Frédéric Clette, Leif Svalgaard, José M Vaquero, and Edward W Cliver. Revisiting the sunspot number: A 400-year perspective on the solar cycle. Space Science Reviews, 186:35 103, 2014.
A Philip Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77(379): 605-610, 1982.
Bradford De Long, Andrei Shleifer, Lawrence Summers, and Robert Waldmann. Positive feedback investment strategies and destabilizing rational speculation. the Journal of Pinance, 45(2):379 395, 1990.
Shachi Deshpande and Volodymyr Kuleshov. Calibrated uncertainty estimation improves bayesian optimization. arXiv preprint arXie:2112.00 02.01220.26.,.. 2021.
Shachi Deshpande, Charles Marx, and Volodymyr Kuleshov. Online calibrated and conformal prediction improves bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pp. 1450-1455 PMI.R, 2024.
12

---

Published in Transactions on Machine Learning Research (03/2025)
Danielle Ensign, Sorelle A Friedler, Scott Neville, Carlos Scheidegger, and Suresh Venkatasuuramaniin. Runaway feedback loops in predictive policing. In Conference on fairness, accounlabilily and transparency, pp. 160 171. PMLR, 2018.
Ky Fan. A minimax inequality and applications. Inequalities,
1972.
Dean P Foster. proof of calibration via blackwell's approachability theorem. Gomes and Economic Behavior, 29(1-2):73-75, 1999.
Dean P Foster and Sergiu Hart. "calibeating": Beating forecasters at their own game. Theoretical Economics, 18(4):14411147, 2023.
Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, (5(2):379-399) 1998.
Carlos E Garcia, David M Prett, and Manfred Morari. Model predictive control: Theory and practice a survey. Automatica, 25:3):335 348, 1989.
Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicalibration and omnipreddccion. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2725-2792. SIAM, 2024.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1660-166 -676, 2021.
Tilmann Gneiting, Fadoua Balabdaoui, and Adrian E Raftery. Probabilistic forecasts, calibration and sharpness. Journal of the Royal Statistical Society Series B: Statistical Methodology, 69(2):243 244-2668, 2007.
Henry Gouk, Bernhard Pfahringer, and Eibe Frank. Stochastic gradient trees. In Asian Conference on Machine Learning, pp.
PMLR, 2019.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. Tn International conference on machine learning, pp. 1321 13300. PMLR, 2017.
Chirag Gupta and Aaditya Ramdas. Faster online calibration without randomization: interval forecasts and the power of two choices. In Conference On Learning Theory, pp. 4283 4309. PMLR, 2022.
Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M Pai, and Aaron Roth. Online multivalid learning: Means, moments, and prediction intervals. arXiv preprint 0rXiv:2101.01333 2021.
Elad Hazan and Sham M Kakade. (weak) calibration is computationally hard. In Conference Learning Theory, pp. 3 1. JMLR Workshop and Conference Proceedings, 2012.
Sham M Kakade and Dean P Foster. Deterministic calibration and nash cquilibrium. Journal of Computer and System Sciences, 74(1):115 130, 2008.
Diedcrik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint wrXii:1112.6940 2014.
Volodymyr Kuleshov and Stefano Ermon. Estimating uncertainty online against an adversary. In Thirty- First Thisty-First AAAT Conference on Arlificial Intelligence, 2017.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. In International conference on machine learning, pp. 2796-2800 PMLRR 2018.
Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Newral Information Processing Systems, 35:29051- 29063, 2022.
Rachel Luo, Aadyot Bhatnagar, Yu Bai, Shengjia Zhao, Huan Wang, Caiming Xiong, Silvio Savarese, Stefano Ermon, Edward Schmerling, and Marco Pavone. Local calibration: metrics and recalibration. In Uncertainty in Artificial Intelligence, pp. 1286 1286-1295. PMI.R, 2022.
13

---

Published in Transactions on Machine Learning Research (03/2025)
Ali Malik, Volodymyr Kuleshov, Jiaming Song, Danny Nemer, Harlan Seymour, and Stefano Ermon. Calibrated model-based deep reinforcement. learning. In International Conference on Machine Learning, pp. PMLR, 2019.
Charlie Marx, Sofian Zalouk, and Stefano Ermon. Calibration by distribution matching: Trainable kernel calibration metrics. Advances in Neural Information Processing Systems, 36, 2024.
Jacob Montiel, Max Halford, Saulo Martiello Mastelini, Geoffrey Bolmier, Raphael Sourty, Robin Vaysse, Adil Zouitine, Heitor Murilo Gomes, Jesse Read, Talel Abdessalem, al. River: machine learning for streaming data in python. 2021.
Georgy Noarov and Aaron Roth. The statistical scope of multicalibration. In International Conference on Machine Learning, pp. 26283 26310. PMLR, 2023.
Electric Reliability Council of Texas. Ercot wind generation data. http://www..roo.om//rrrnnn/egeee 2022.
Princewill Okoroafor, Robert Kleinberg, and Wen Sun. Faster recalibration of an online predictor via approachability. arXiv preprint ar orXi::2310.1700, 2023.
Vianney Perchet. Approachability, regret and calibration; implications and equivalences. ar preprint urXiv:1301.2066 2013.
Roshni Sahoo, Shengjia Zhao, Alyssa Chen, and Stefano Ermon. Reliable decisions with threshold calibration. Advances in Neural Information Processing Systems, 34:1831- 1844, 2021.
Maurice Sion. On general minimax theorems. 1958.
Hao Song, Tom Dicthe, Meelis Kull, and Peter Flach. Distribution calibration for regression. In International Conference on Machine Learning, pp. 5897 5906. PMLR, 2019.
Cédric Villani. Optimal transport: Old and new. 2008.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior, 2nd rev. 1947.
Vladimir Vovk, Akimichi Takemura, and Glenn Shafer. Defensive forecasting. In International Workshop on Artificial Intelligence and Statistics, pp. 365-372. PMLR, 2005.
Charles Walkden. MATHA1112/61112 Lecture Notes: Probability measures compact metric spaces, May 2016.
David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests boyond classification. arXiv preprinl ar Xiv:22200. 13355, 2022.
Changlei Zhao, Can Wan, and Yonghua Song. Cost-oriented prediction intervals: On bridging the gap between forecasting and decision. IEEE Transactions on Power Systems, 37(4)30048-300 3062, 2021a.
Shengjia Zhao, Tengyu Ma, and Stefano Ermon. Individual calibration with randomized forecasting. In International Conference on Machine Learning, pp. 11387- 11397. PMLR, 2020.
Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. Calibrating predictions decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems, 34:22313 22324, 2021b.
Johanna F Ziegel and Tilmann Gneiting. Copula calibration. 2014.
14

---

Published in Transactions on Machine Learning Research (03/2025)
A Proofs
We first prove two useful lemmas.
Proposition A.1. If the payoff is bounded (Condition 1 then
B T
2
ক 2
+
T T (Fe: vc))
(3)
T
Proof. We proceed by deriving a recursive form for
|
T
1
| 12
ØT-1 +
nT
(10)
T
1
T 1
||
11
1
| 11
2(T 2(T-1)
1, TTHH
(11)
T
T
T
Multiplying through by T have
T | (T- 11-1 1)² ||
11 + || + +
1) (1
(12)
Note that this is a recursion over pr == 2 | 11
Unrolling this recursion gives
2 | H
| 12 +
>
-1- 1)
(13)
t=1
Finally, dividing through by 1 and using the boundedness of nr gives the desired result:
1
T
7
T
2
+ T
Σ (t - 1) (T,
(14)
t=1
1=1
B
2
(15)
T
0
Proposition A.2. If the payoff is consistent (Condition and continuous (Condition 3) then for all π E H and x E X, there erists forecast A(Y) such that
max
yEy (म. (I, n) < 0.
(4)
Proof. Abusing notation, we write the expected payoff for an outcome y distributed according to distribution g A(Y)
T p.9) == Eyng [ (x.p.9]]
(16)
The only randomness in Equation equation 16 is due to y. Observe that exchanging the worst-case y E y for the worst-case distribution q E A()) does not change the value of the minimax game:
min max (,, (x. = min max (,, pEAD) yEy
(17)
(EA())
To see that the LHS is not greater than the RHS, note that ((, P. y) can be represented as ( p, 6,), where b is a Dirac distribution at y. To see that the RHS is not greater than the LHS, note that the objective value TT. p. q)) lincar in q, so the objective value will always be maximizod by Dirac distribution.
Next, apply the Ky Fan Minimax Inequality Fan 1972 to upper bound the RHS.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Theorem A.3 (Ky Fan Minimax Inequality Fan 1972 ). Let A()) be nonempty compact conver subset of Hausdorff topological vector space, and let g: A ()) A()) + R be a function such that:
p p q) is louer-semicontinuuus for all q E A
- g(p.9) q) is quasi- coasi-concave for all E A())
Then
min max ( S max g(g.9) PEA())
(18)
9Ea()))
We apply the Ky Fan Minimax Inequality to the function g(p. q) == (T,, (x. Our assumption that the payoff is mean-zero implies that π[, 0, = 0, so for all E A()) we have ((q.g) = (F, (T, 0)H = 0.
Thus, the lemma proven once we meet the conditions of the Ky Fan Minimax Inequality. Namely, we must show that (()) is nonempty compact convex subset of a Hausdorff topological vector space, and that g(p.g) is lower-seniiconinuuuss in its first argument and quasi-concave in its second argument.
We first show that A()) is nonempty compact convex subset of Hausdorff topological vector space. The space of signed measures on Y' is Hausdorff topological vector space when endowed with the weak" topology. The set of probability measures A()) is a subset of the space of signed measures, and it is an elementary result of probability theory that this set is nonempty and convex (see, e.g., Billingsley 2017). The compactness of
A()) follows from our assumption that y is a compact metric space (Walkden 2016 Theorem 10.2).
All that remains is to show that g(p, 9) is lower-semicontinnous in its first argument and quasi-concave in its second argument. Note that g(,.g) q) is lincar, and therefore quasi-concave, in its second argument due to its construction
expectation. Lastly, note that Wasserstein convergence is equivalent to weak" convergence on a Polish space (Villani 2008 Theorem 6.9), so our assumption that g(p, q) is Wasserstein contimuous in its first argument implies lower-semicontinityy in the weak" topology. Thus, the result follows by application of the Ky Fan Minimax Inequality.
Theorem 4.3. If the payoff satisfies Conditions T < B/T for any sequence ((x1,)))
3 then Algorithm has miscalibration bounded by
Proof. The thcorem follows directly from Lemmas and
4.2
For each time step f, Lemma 4.2 guarantees implies that any
the existence of a forecast pt such that maxzey (T ग (Tt. Pt, 9c)) I O. Next, Lemma forecasting strategy which plays such a forecast ps achieves
B
T
Tr H
(m-11 Te)
T
T
B
T
Taking the square root of both sides yields the desired result.
Proposition A.4. Let ,!!),...,???! T()) be n payoff functions taking values in Hilbert spaces Hı,... Hns
respectively. Suppose each payoff (0) salisfies the Conditions 7 with bound B, Applying Algorillum 7 to
the direct sum payoff (11) @ ... + π (n) ensures Σ T H.
S E Bi, and using the normalized payoff
x
B. @ ... + x(1) B,
ensures
| H. < B.
+ for 1 ssiin n.
Proof. The proposition includes two inequalities. Define the concatenated payoff (1mm) := [ (1)) taking values in the direct sum Hilbert space HT = +i= H,, Note that π ((mm) inherits all the conditions of Theorem 4.3 from the component payoffs, but with the payoff bound BT = Σi B, Thus, the first inequality direct result of Theorem 4.3. To see the second inequality, we first define a normalized payoff ((1m) = (())/B,,.... x(m)/Bm] where each component payoff has norm at most 1. Applying the first.
16

---

Published in Transactions on Machine Learning Research (03/2025)
(1mm) inequality, we get that l|pr have for all s n that 지 173.
P Di=1 nBB T
S g. Since each term of the sum is nonnegative, we |
(2)
11 Ri. /
A.1 An Extension to the Existence Theorem for Semi-Consistent Payoffs
Note that n REG Section does not satisfy consistency (Condition P]: which requires that Ey-p (1 P: v)] = 0, Yx E X, Vp e AV"). Thus, we introduce a weaker condition the positive component of the excess loss, since negative excess loss (i.e., outperforming the experts) is not problematic. Note that Condition 4 applies to I RREG due to the propriety of the scoring rule; the true distribution has expected loss no greater than any other forecast.
( (Condition E.. which allows us control
R is semi-consistent if vector-valued payoff T(.,p,)) E gup [mi(x, p. y)] S 0, for all i (1....,m) p E A(V), and x E X.
Condition 4 (Semi-consissenery)
Proposition A.5. If vector-valued payoff function satisfies Conditions
1
3 and 4 then Algorithm
achieves (TT)) 1| < B/T for any sequence (e),,,)) where (अT)"
( ,.... (mm,r)+) for
(T.))* = max (0, T.))) is the positive part.
The proof of Proposition A.5 is almost identical to the proof of Theorem 4.3 with the average payoff replaced by its positive part. Applying Proposition A.5 to REG gives the no-regret guarantoe that Rr S vnB, where /T
By = supp.y {p,, v). Thus, we achieve the same O(I/VT) regret rate.
B Calibration Payoffs
Below, we introduce additional payoff for full distribution calibration, and add details to for additional precision for the quantile calibration payoff.
Distribution Calibration Distribution calibration states that across all time stops t with the same forecast P, the distribution of outcomes should match the forecast. (Song et al.) 2019). In the batch setting, where the outcome y and forecast p are random variables, distribution calibration can be written as (y p) ~ p. For example, when forecasting the daily high temperature, days the forecast is Gaussian distribution with mean C and variance C,C, the observed high temperatures should be roughly Gaussian with the same mean and variance. To define distribution calibration in the online setting using payoffs, we use a vector-based payoff indexed by a discrete set of distributions E ( given by Tp(Tt, Pt, Pt, = 1 {pr x p} (Fy, Fstr.)), where Fp. and Fatue are the odfs for the forecast and a Dirac measure at Yt, respectively. Note that a fine discretization of the space of distributions A())) will grow exponentially in size as y grows, highlighting the computational hardness of distribution calibration.
Quantile Calibration Since distribution calibration is often too difficult to impose in regression primarily due to the need for a conditioning event for each distribution -uuntille calibration is a popular weaker alternative, requiring that the quantiles of forecasts are accurate, on average. That is, the outcome ye should be less than or equal to the a-quantile of the forecast with frequency a, for all a E [o, 1] (e.g,, V: should exceed the forecasted median half the time). Formally, quantile calibration states that lim + Ei= {u,- < Quantile(pr, }}} = for all a E [0, Quantile calibration enforces the law of probability that the probability integral transform (PIT) of a continuous random variable follows a uniform distribution on the unit interval. In a batch setting where the outcomes are i.i.d. random variables and if the forecasts and ground-truth distributions are continuous, the payoff na (1, p. y) = 1 {u S Quantile(pr, a)) a, indexed by a E [0, 1], suffices to measure quantile miscalibration. To handle the case where there are discontinuitees in the edf of the forecast, allow forecasts over strict superset of the outcome space and lincarize across discontinuitics in the forccasted CDF (sce Ziegel & Gnciiing (2014) for similar approach in the batch setting), yielding the payoff
na (a p) = X1 -0
sa
(19)
-a where at = inf fal E Rango(F,) ): : a' 2a), a- = sup fa' e Range Fp) a' sa), and \ = (a a)/(at -
17

---

Published in Transactions on Machine Learning Research (03/2025)
C
Oracles
This section introduces half-space oracles designed for specific notions of calibration. Specifically, we focus the following: adaptive conformal inference, quantile calibration, distribution calibration, moment- based distribution calibration, and decision calibration. In each setting, we introduce the definition of calibration, provide a half-space oracle, prove its correctness, and discuss its computational complexity.
C.1 Quantile- Basee Notions of Calibration for Regression Problems
We start with perhaps the simplest setting, which considers forms of calibration defined for regression problems and in which calibration is defined using quantiles. Specifically we look at two approaches of this form: adaptive conformal inference- setting that matches exactly the definition introduced by Gibbs Candes (2021 as well as quantile calibration, an extension full quantile functions.
Preliminaries We introduce both randomzadd and deterministic algorithms. We use the term quasi-randomizer to say that the randomization will be between two forecasts (our outputs) fi, f2 that satisfy Ilfi fell < e, for some small e and according to some norm || II. Our deterministic algorithms will assume the existence of a root finding oraele for a function g x + IR on some closed and compact set X' (e.g., the interval [0,1]) that is guaranteed to have point æ such that g(x)
C.1.1 Adaptive Conformal Inference
Sctup In the setting of adaptive conformal inference, we are given target quantile 3 as well as a quantile function Qe(a) (that could be different at each time step) that targets continuous outcome yt E R. Our goal is to choose at each time step an a, [0, 1] such that the Qc(as) are average the 3-th quantile within error tolerance of > O. In other words, want
T 1ve s Q(a)))(())))))))))))))))))) 3 S
lim T-00
Σ T
Randomized Algorithm We define our algorithm as follows. First, we define a finite of set of possible outputs for over which we will perform randomization. Specifically, we define our action set as A = (a, ....... ass where A a discretization of [0, 1]. i.c., 0 0= au S a; < 0++1 I ass = We will play distributions p E ((A) over the action set. We define our payoffs as follows. Let e<(a) = {ye S Qi(a)}. Let the payoff be indexed by actions Pt assigns to action a. We want the average set of payoffs approach ball of size centered at the origin. Note that this yields valid quantile estimate as defined above.
A, given by n (Pt. M4) = (a) (a) - 3), where (a the probability
In order to achieve this goal using approachability, we need to devisc a half-space oracle that will output at each time step a distribution pt over A such that for any vector of historical payoffs H., we have (Te, n (pc, u)) S 0 for all y.
We construct the following half-space oracle for this goal, given the average payoff me:
If for all a, Te. 0, output on with probability one.
If for all a, Te. < O, output as with probability one.
Otherwise, there will exist an E fI,...,
......,, M} such that sign (T) & sign(Tr,a;1)) Then choose the above a; 4441 and play with probability p, = | [/( [eeee 111 the value a,, and otherwise 0;-1- Then for all y, we have:
Lemma C.1. Let > 1/M. Then the above algorithm half-space oracle for a ball of radius e. Furthermore, the algorithm in log(t) time and (11/e) space.
18

---

Published in Transactions on Machine Learning Research (03/2025)
Proof. First, we explain the time and space complexity of the algorithm. First, the space complexity is ((M) = O()) because > 1/M. The time complexity is O(log(M)) = Olog(()) because we can find an such that (T,, # sign( (or determine that none exists) in (llgg(M) time using binary search.
Next, we prove that in each of the three cases above, the property of the half-space oracle satisfied. Note that:
(e (pt, v)) = ((a) (ex(a:) - + Pt.a,1P(((s--)) (e)(0;+1) (3)
k (es(as) (((+)1)) for a constant &t > 0, by choice of pt
note again that E<(a1) =1 = et(a2) if a1 < 02 therefore the above expression is (Te, π (pt. y)) s 0.
Deterministic Algorithm Our deterministic algorithm is straighttforward extension of the above procodure. We now let the action space A = [0, 1] be equal to the entire unit interval. The payoffs are the same above for each a E A. The algorithm is defined as follows. Denote the average payoff by e: A - R. Then we run the zero-finding oracle and output the zero of e if it exists. Otherwise, either c 2 0, and we output 0 or c S O, in which case we output
Lemma C.2. The above algorithm is deterministic half-space oracle for ball of radius c. Its runtime is equal to that of the root-finding oracle.
Proof. First, note that the above three cases the algorithm are exhaustive for the same reason as in the previous theorem. The two edge cases are handled as before. In the third case (when the root exists), we put all the probability on the root a', and the dot product reduces to:
c. (pe O (yy) = c(a') (ela)))()))
since c(a') is zero (and note that we defined the innor product c- (p. @ π (zy) to generalize to the function c).
C.1.2 Quantile Calibration
Nexl, we are interested in a generalization of the above setting, in which the output of the algorithm is an entire quantile function.
Setup We are given as input a quantile function (a(a) (that could be different at each time step) that targets a continuous outcome yt E that is bounded by values Umin Mmax Our goal is to choose at each time step a recalibrator function R, : [o, 1] - [0, 1] such that the corrected quantile function Q Qe o R, represents valid quantiles within an error tolerance of for all B. In other words, want
f T
lim T-O
D
S ('())) B)
S for all 1> 0.
Deterministic Algorithm Without loss of generality, we can define our action space to consist of quantile functions Q.- We define our payoff's follows. Let e<(a) 1l S Q(a)). Let a(Q, y) ea(a) - a, which is vector indexed by [o, 1]. We want the average set of payoffs to approach a ball of size centered at the origin. Note that this yields valid quantile estimate as defined above.
In order to achieve this goal using approachability, we need to devise a half-space oracle that will output at each time step a Qt such that for any vector of historical payolfs e e IRm we have e T. (T y) S 0 for all y, where (e 8) is the vector of payoffs indexed by A and denotes the inner product.
We construct the following half-space oracle for this goal. Suppose we are given a vector of historical payoffs We root finding-algorthm to find at least one root (or the absence of any root).
19

---

Published in Transactions on Machine Learning Research (03/2025)
If 2 let Q(a) Vmin for all a, and output Q-
If s 0, let ((a) V/max for all a, and output Q-
Otherwise, there a zero a' such that d(a') = 0. Let A be the integral under the curve of for a a a' and let Ag be the integral under the curve for a 2 a'.
If A2 - A, s 0, let Q(a) = Mmin for a S a' and Q(a) = Mmnx for S a'.
If + A₂ 2 0 let (aa Vmax for all a, and output Q.
Tf A + A2 2 0 let (a) Umin for all a, and output Q.
positive and the area under the curve for a 2 a' is negative, let Q(a) = Ymin for a S d' and Q(a) Ymax for a a a'.
Lemma C.3. The above algorithm is a deterministic salf-space oracle for a ball of radius e. Its runtime is equal to that of the root-finding oracle.
Proof. First, note that the above three cases in the algorithm are exhaustive. Next, note that when Q(a) Vmaxx then aQ,,, 2 0 for all y. When Q(a) Vminn then x xQ,, y) for all y. Thus, in each of the first two cases we have (2( - O.
-1 In the third setting, first subcase, by construction we have exactly c .r < A A1 S. The last two subcases follow similarly. Note that computationally, we can distinguish among all these subcases, by performing an inner product with e and obscrving the result. The computational cost of the algorithm is that of running the root finding algorithun and the inner product.
Note that this algorithm is not practical, as it produces Q's that are stop functions. is meant to illustrate the existence of polynomial algorithm in our framework. In practice, one would use our oplinization-based solution.
C.2 Variations of Distribution Calibration
Next, we are going to derive half-space oracles for versions of distribution calibration, both the original version of distribution calibration, as well as more restricted and tractable versions, including decision calibration and our novel formulation of moment-based calibration.
C.2.1 Distribution Calibration via Discretization
Our overall strategy for constructing half-space oracles will be inspired by Kakade & Foster (008)). We first provide a summary of their approach that closely follows their exposition.
Specifically, we will define a discretization of the space of forecasts. For example, the set V could consist. of probability distributions which are specified to a finite number of digits of precision. Essentially, our quasi-randomized approach will output distribution over small number of similar elements of V, and our deterministic approach will play fixed point of this distribution.
More specifically, we will assume that the forecasts live in compact set A (this assumption will have to be verified for each definition of calibration). We then define triangulation of A, i.e., a partition into set of simplices such that any two simplices intersect in either a common face, common vertex, or not at all. Let V be the vertex set of this triangulation. Note that any point p lies in some simplex in this triangulation, and, slightly abusing notation, let (p) be the set of corners for this simplex. We are going to produce a randomized output over these corners.
To formalize this, associate a test function w.(p) with each E V as follows. Each distribution p can be uniquely written as a weighted average of its neighboring vertices, V(p). For v E V(p), let us define the test functions (p) to be these linear weights, so they are uniquely defined by the linear equation p p= >=Envr>) (.)p).
We also define the discretization be sufficiently small: given a target precision we define the discretization such that for all f1, f2 in the same simplex we have || fall <
20

---

Published in Transactions on Machine Learning Research (03/2025)
Deterministic and Quasi-Deterministt Calibration We use the following results from Kakade & Foster (2008). Let pT(p) = + - w., (ft)(tt - -ft)- For E V, define pr(v), function which updates v +++u(()) (T()). We extend this function to arbitrary p by interpolating using the calibration error (T(:): pr(c) = v
between the vertices of the cell that contains p: pr(p) - p Evev (x))
Consider the following pllay the fixed point' algorithm defined by Kakade & Foster (2008). At time 1, we set po(x) = 0 for all v E V. Then each future time T, compute a fixed point of pr-1 and forecast this fixed point.
We will use the following facts
Lemma C.4. For all T, fixed point of pr crists and the forecast fr at time T satisfies Ever wo (f) =
Lemma C.5. The above deterministic algorithm is weakly calibrated in the sense that + lim 00 ET (ffo)() fi) + 0 in the Eo norm for any continuous function w.
Consider now the following quasi-delerministic version of the above algorithm. We start with a forecasting procedure that is weekly calibrated. At time f, that procedure outputs a forecast ft. We define a quasi- deterministic forecast by outputting the vertices v E (ft) of the simplex containing ft, each with probability w. (ft). Recall that we have chosen the discretization such that [lʃi - f2ll <e.
Lemma C.6. The limit of the calibrulion error of the above algorillm as T - oo is at most e.
Next, we will use these tools to establish half-space oracles for our framework.
C.2.2 Moment- Based Distribution Calibration
Sctup In the setting of moment-based calibration, we are trying to forecast each time step continuous label Yt E R and we assume that [yel < B is bounded by B Our goal is to choose each step prediction Pe: o, such that average, our of all the times when we predicted pe, o the mean and the variance of the Ye are also approximately equal pe, 0z. 0z.
Randomized Algorithm We define our action set as A = ((1s for i,j in a grid with M ticks along each dimension). The grid represents our set if simplexes and the ticks on the grid are the vertices V. We will output a probability p over A and sample a forecast ft from We define a set of payoffs as TH,, o, y) = (μ - y, o.o=)"l); thus æ has dimension 2M2. We want the average set of payoffs to approach a ball of size centered at the origin. Note that this yields valid quantile estimate as defined above.
In order to achieve this goal using approachability, we need to devise half-space oracle that will output at each time step distribution Pe over A such that for any vector of historical payoffs E RT, have c (pt O (1)) < 0 for all where Ti (y) is vector of payoffs indexed by A.
We construct the following half-space oracle for this goal. Suppose we are given a vector of historical payoffs c. By the above fixed point lemma,, there must exist a fixed point ft such that Eeev Wo (f)))T-))(()) = O. We can find the cell where fr lives by enumerating the M cells. Then we set Pt, our probability over the A be zero everywhere except at (ft) and equal to w. (fi) everywhere else.
Lemma C.7. Let > 1/M. Then the above algorithm half-space oracle for a ball of radius c. Furthermore, the algorithm runs in c² time and O(1/2) space.
Proof. First, note that our set of possible forecasts is compact, which guarantees that the fixed point exists. Next, we prove that the property of the half-space oracle satisfied. If the fixed point is the interior of a cell, note that:
Tp. Σ (..(ee):-1()) =0
VEV
because ea is defined to be previous vector of average payoffs, which is precisely Pt-1-
21

---

Published in Transactions on Machine Learning Research (03/2025)
Note that there may be edge cases, where the fixed point is at the edge of the grid. Then simply have to enumerate the following edge cases. Suppose that Cajij=0 2 0 for all i (it's fully positive on the left edge of the grid). Then you can find an optimal strategy over μ as in a ld problem over (i,j = 0). Suppose that Co I O for all i (it's fully positive on the right edge) Then you can find an optimal strategy over & as in 1d problem over (i.j = M). Suppose that Cp.i=0.j 2 for all j (it's fully positive on the top edge of the grid) Then you can find an optimal strategy over a as a 1d problem over (i = 0, Suppose that M, S 0 for all j (it's fully positive on the bottom edge) Then you can find an optimal strategy over a in 1d problem over (i (i=00 M.
Next, we explain the above time and space complexity of the algorithm. First, the space complexity is ( 0(1/e)) because e > 1/M. The time complexity is O(M²) = Oce²) because we simply enumerate all the cells.
Deterministic Algorithm The above procedure naturally leads to a natural randomized algorithm, where simply forecast the fixed point. Computationally, implementing this algorithm requires oracle for Brouwer's ' fixed-point problem (in general, this is PPAD-hard).
C.2.3 General Distribution Calibration
We can extend the above approach to more general scttings, where we want to main general notion of distribution calibration. In other words, out of the times when we predict ft, we want the distribution of to look like ft-
Setup We are trying to forecast at each time step l a continuous label Ye E IR and we assume that Weel S B is bounded by B > O. We are going to assume a certain discretization for into partition of M intervals of its domain. Our goal is to choose at each step t a forecast fi such that on average, our of all the times when we predicted y/ we have yt= s fo: this can be roughly viewed as matching probability mass functions.
Randomized Algorithm We define our action set A as discretization of the set of distributions fe- This can represent a discretization of the range of ft into grid of N points. The grid represents our set if simplexes and the ticks on the grid are the vertices V. We will output a probability p over A and sample a forecast fo from p. We define a set of payoffs as xff = f - y, thus π has dimension O(M We want the average set of payoffs to approach a ball of size centered the origin. Note that this yields a valid quantile estimate defined above.
Again, need to devise half-space oracle that will output at each time step distribution pt A such that for any vector of historical payoffs E R", we have e (pt @ me me(v)) s 0 for all y, where ne Te(y) is vector of payoffs indexed by A.
We construct the following half-space oracle for this goal. Suppose we are given a vector of historical payoffs c. By the above fixed point lemma, there must exist a fixed point fe such that Evev w. (f) = O. We can find the cell where fi lives by enumcrating the M cells. Then we set pt, our probability over the A to be zero everywhers except at V(Ja) and equal to (Ji) everywhere else.
Lemma C.8. The above algorithm is a half-space oracle for a boll of radius e.
Proof. First, note that our set of possible forecasts is compact, which guarantees that the fixed point exists.
Next, we prove that the property of the half-space oracle is satisfied. If the fixed point is in the interior of a cell, note that:
o (n ( = Σ (() = 0
VEV
because e defined to be previous vector of average payoffs, which is precisely Pt-1. Edge cases would be handled similarly to the earlier proof.
22

---

Published in Transactions on Machine Learning Research (03/2025)
Note that in most cases, this algorithm would not be computationally tractable. However, that is expected: the problem is in general PPAD-hard. This question of computational tractability is what motivated our previous definition of moment-base based calibration.
Deterministic Algorithm The above procedure naturally leads to natural randomized algorithm, where we simply forecast the fixed point. Computationally, implementing this algorithm, requires accoss to an oracle's for Brower's lixed-point problem (in general, this is PPAD-hard).
D Low Regret Relative to Baseline Classifiers
Here, we show that calibrated forecaster also has small regret relative any bounded proper loss if we use certain construction that combines our algorithm with a baseline forecaster.
D.1 Recalibration Construction
We start with an online forecaster F that outputs uncalibrated forecasts pf at each step; these forecasts are fod into a recalibrator such that the resulting forecasts pz are calibrated and have low regret relative to the baseline forecasts p.-
Setup
Formally, every step 1,2.... ... we have:
1: Forecaster F predicts p."
2: recalibration algorithm produces a calibrated forecast Pt. based on pf-
3: Nature reveals label Y1
4: Based on It, y/s, we update the recalibration algorithm and optionally update H.
Notation We will reuse some of the previously introduced construction based on the work (Kakade & Foster 2008). Specifically, recall that we define a discretization V of the space of forecasts. We assume that the forccasts live in compact set A and we define a triangulation of A, i.c., partition into set of simplices such that any two simplices intersect in either common face, common vertex, or not all. Let V be the vertex set of this triangulation, and let Vip) be the set of corners for this simplex.
Note that each distribution can be uniquely written as weighted average of its neighboring vertices, V(p). For E (p), we define the test functions (n(p) to be these linear weights, so they are uniquely defined by the linear equation p = Evevi (p)u. We also define the discretization to be sufficiently small: given a target precision E > 0 we define the discretization such that for all fI, f2 in the same simplex we have Il. - fell
D.2 Recalibration Algorithm
We are going to define a general meta-algorithm that follows a construction in which we run multiple instances of our calibrated forecasting algorithms over the inputs of F.
More formally, we take the aforementioned partition of the space of forecasts of of F and we associate each simplex with an instance our calibration algorithm Feal (using the same and discretization V). In order compute of: we invoke the subroutine Feal associated with simplex I, containing of (with tics broken arbitrarily). After observing St, we pass it to praal
The resulting procedure produces valid calibrated estimates because each rysal is calibrated subroutine. More importantly the new forecasts do not decrease the predictive performance of F, as measured by proper loss f. In the remainder of this section, we establish these facts formally.
D.3 Theoretical Analysis
Notation Our task to produce calibrated forecasts. Intuitively, we say that a forecast F; is calibrated if for every y E Y, the probability F((y') on average matches the frequency of the event. {y y'). We formalize
23

---

Published in Transactions on Machine Learning Research (03/2025)
this by introducing the ratio
Pr(p) = ΣT Ut 1p.=p
(20)
>t=1 ppmp
Intuitively, we want pr(p) + p, a.s. as T + 2o for all y. In other words, out of the times when the predicted probability for yr is p, the average yr look like p.
The quality of probabilistic forecasts evaluated using proper losses Formally, a loss l(y. p) proper if p arg minger Ey-(n) (g..)) q) Vp P. An example in binary classification is the log-loss (yog(y. y) log(1 p). We will assume that the loss is bounded by B 0.
y log(p)
We measure calibration calibration error Cr. Our algorithms will output discretized probabilities; hence define the error relative to set of possible predictions V
Cr
Σ PEV
Ier (p) - pl
(
7
Σ
0 [p-=p)
(21)
D.3.1 Helper Lemma
In order to establish the correctness of our recalibration procedure, we need to start with a helper lemma. This lemma shows that if forecasts are calibrated, then they have small internal regret.
Lemma D.1. If E is a bounded proper loss, then an (e, caalbbrbat peat a.s. has a small internal regret w.r.t. l and satisfies uniformly over time T the bound
Ript
Σ t=1
p.p (E(y),P)) a(yi, p;)) S 22B(Rr +
(22)
Proof. Let T be fixed for the rest of this proof. Let la = lp-pp. be the indicator of Feal outputting prediction Pt at time 1, let T, Σ le denote the number of time i/N was predicted, and let.
RT Σ De (E(y), E(ye. Pj))
denote the gain (measured using the proper loss E) from retrospectively switching all the plays of action to j. This value forms the basis of the definition of internal regret.
Let T(i, = = Byl = y} denote the total nimber of p; forecasts at times when y: y. Observe that
we have
T
ΣT 1e0 v}
T(i,y) = Σ
lulf1r = =y
Ei=
T,
Σt lui
lill = v}
= q(i yT., + Tí
g((.
Σ Iii
= qí. y) + Ta (pr(p)) - ps),
where g(i. v) (v)). The last equality follows using some simple algebra after adding and subtracting one inside the heses in the second term.
24

---

Published in Transactions on Machine Learning Research (03/2025)
We now use this expression to bound Ry
T
RT,35
Σ lu (c)))..)) e(ye.
Σ T(ú, v) (e(y, ((g.P)))
< Σ uli, (e(y,ps) E(v.P))) + BT, (oT(P)) - pil
$ BT, (pr(p:) -pil.
where in the first inequality, we used ((y,P:) P(y.P;) < Ely,p:) < B, and in the second inequality we used the fact that is a proper loss.
Since internal regret equals RiT max,,; T, we have
pint
1
max Pint
S 2B
T. (pt//N) pal 2B(R +)..
D.4 Recalibrated forecasts have low regret relative to uncalibrated forecasts
Next, we use the above result to prove that the forecasts recalibrated using the above construction have low regret relative to the baseline uncalibrated forecasts.
Lemma D.2 (Recalibration preserves accuracy). Let be bounded proper loss such that E(ye, p) l(y,, Pj) + Be whenever ||p pill e. Then the recalibrated pt a.s. have vonishing t-loss regret relative to pt and we have uniformly:
T
M
1 T Σ
B
T T
<
RT, BBE.
(23)
Proof. By the previous lemma, we know that an algorithm whose calibration error bounded by Ry o(1) also minimizes internal regret al rate of 2BRr, and thus external regret a rale of 2BRr/e /e.
Next, let us use If indicate that Fral called at time We establish our main claim follows:
T Σ E(e. p.)
(e(ve.Pe) E(yer1) Di.e
(E(ye.P)) -((ve 03, + Be
M T RT, + 3Be,
< - B Σ 7
where Ry, is bound on the calibration error of Fyail after T) plays. In the first two incquality, we use our assumption on the loss f. The last inequality follows because Ffa minimizes external regret w.r.t. the constant action pj at rate of BRr, /c.
25

---

Published in Transactions on Machine Learning Research (03/2025)
D.5 Proving that calibration holds under any norm
We want to also give a proof that the recalibration construction described above yields calibrated forecasts. Lemma D.3. If each Fyml is (c, (p) (affppcaabraaedd then the combined algorithm is also (c, Ep)-cabibrated and the following bound holds uniformly over T:
T RT, +e.
CT
(24)
Proof. Let M [V]. Let 1(60
1 where U. lppe Pj npp =p}} and note that Σi= 4,s
2x
(G)
Σラ= 16) Let also / (pi) = 21z1
We
We may write
10
c-
Σtm Meni T
(1)
M
(1) 1.3 yt
CT
ppr(pi) -Pal
2j=1
T
1=
j= (7
Pi
ΣM
j=1
T
M
(
PT
(5)
(p:)
(1)
P
M
(j)
T
PT (p.) -p
(
T (0) Σ
M
T.
j=1
where C+ | (p.) pa (
Ei=1 and in the last line we used Jensen's 's inequality. Plugging in this
bound in the definition of Cr, we find that
N ΣΣ
M
T
M >
T
Cr= Cr, S
T
T
S
T
Rr,
+
1=1 ==
==1
Since each Rr, - 0, the full procedure will be eccllibraeed.
Recall that Ry denotes the rate of convergence of the calibration error Cr. For most online calibration subroutines peal, Ry & f()/vT for some f()). In such cases, we can further bound the calibration error the above lemma as
M L ΣTAO
TTf(c) VTJe
M
fle) VeT
T
J=1
3=1
In the second inequality, set the Tj be equal. Thus, our recalibration procedure introduces an overhead in the convergence rate of the calibration error OT and of the regret relative to baseline forecaster in the carlier lemma.
of Ve
E
Applications: Dacision-Making
Next, we complement our results with formal characterization of some benefits of calibration. Consider decision-taid where wish to estimate value function y x A X + R over set of outcomes V, actions A, and features X. Note that the function could be a loss E a, a) that quantifies the error of an action E A in state z E X' given outcome E y
We assume that given I, the agent chooses an action a(x) according to a decision-making process. This could an action a(x)= = arg min, Ey-d((>>) [f(y, a, x)] that minimizes an expected loss according to the probabilities given by the forccast. The agent then relies on a predictive model H of y estimate the future values v(y, a.) for the decision a(x):
v (x)) = Hy) (w) (o a()),
(25)
We study v(y, a, x) that are monotonically non-increasing or non-decreasing in y. Examples include lincar utilities a(a, y + c(a,a) or their monotone transformations.
26

---

Published in Transactions on Machine Learning Research (03/2025)
Expectations Under Calibrated Models If H was perfect predictive model, could estimate expected values of outcomes perfectly. In practice, inaccurate models can yield imperfect decisions. Surprisingly, our analysis shows that in many cases, calibration (a much weaker condition that having a perfectly specified model H) is sufficient to correctly estimate the value of various outcomes.
Surprisingly, our guarantees can be obtained with weak condition oountioon-qunttlee calibration. Additional requirements are the non-negativity and monotonicity of v. Our result is concentration inequality that shows that estimates of are unlikely to exceed the true average (Zhao et al. 2020).
Theorem E.1. Let M be quantile colibrated model as and let vly, a, a. be a monotonic value function. Then for any sequence (e),,))(=1 and 1, we have:
1 Σ [l((), 2 ru(x)))) 1/r
lim T-000 T
(26)
Proof. Recall that (x) is a distribution over V, with a density Pa: a quantile function Qu, and cdf Fz.
Note that for any and (0, and y' S FF s) we have:
v(x)= / o( ola, ((r))
I V2V
((..),(==))
2 ola,s/. al)))(())))))))())())))))))
(x(dd
v2V
2 su(z. a(x))
The above logic implies that whenever v(x) S so(z, v, a), we have 2 F1 or F2(0) 2 (1 s)) Thus, we have for all I,
((v(Iz) S s
(v)) (1-
Therefore, we can write
T Σ (u(x)) s selz, Vc, at))
1
1 s
T Σ IfF (11) 2 (1 (1-s)) 5)} = =
where the last equality follows because M is calibrated. Therefore, the claim holds in the limit as T - oc
monotonically non-increasing. that case, we can show that whenever y/ > (s)( we have v(x) 2 st(2, "/./(/)))))))) a(())) Thus, whenever v(x) S so(x, y, a), we have y S F (s)
for = 1/ss. The argument similar
or (v) S s. Because, Fz is calibrated, we again have that
T
Σ (u(a)) < sulz,, Vr, at)) <
Σ (3)
T
and the claim holds with r = 1/s.
Note that this statement represents an extension of Markov inequality. Note also that this implies the same result for distribution calibrated model, since distribution calibration implies quantile calibration.
F Additional Experimental Details
Experiments were run on CPU on a MacBook Pro with an M2 chip and 64 GB memory. The results in our experiments were generated using 6 hours of compute.
27


Reviews:
[{"review_id": "cEc48uV7oA", "reviewer": "Reviewer_p6eq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is in general clearly written. The perspective of formulating the forecast task as a zero-sum game played between the Forecaster and Nature and leveraging Blackwell approachability to achieve provable calibration is interesting. The algorithms motivated by the theoretical insights are practical and effective as proved by the experiments. I have some minor questions, please see the Requested Changes part for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel framework of calibrated probabilistic forecasts for arbitrary sequence by formulating it as a zero sum game between the forecaster and the nature and leveraging the concept of Blackwell approachability from game theory. \nPractical algorithms are proposed and numerical experiments results show the validity of their proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have some questions:\n1. In equation (2),  the halfspace is defined by the average payoff, then why it's $\\bar{\\pi}$ instead of $\\bar{\\pi}_T$?\n2. “ For any discontinuous payoff, continuity can be achieved by smoothing the payoff on an arbitrarily small scale.” Can you further elaborate on this claim? For example, if the payoff is smoothed, then it is changed. Does this change have any influence?\n3. The regret $R_T$ is defined with respect to the average performance, while in equation (7), $pi^{\\text{REG}}(x,p,y)$ is not an averaged term. Is this a typo, otherwise how to understand it?\n4. I kind of lost at the Recalibration and Theorem 5.2 of section 5.2. Though more details are provided in the appendix, I was wondering why it is placed in section 5.2. Moreover, it seems that recalibration is one of the main contribution of your paper, maybe more discussion in the main context would be better. \n5. In the abstract, how to understand \"accurate uncertainties\" for the recalibrate method?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "i19a0FRHUR", "reviewer": "Reviewer_XmLe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n - _A very general framework._ The paper provides a unifying theoretical framework that encompasses a wide range of calibration measures, making it applicable to diverse forecasting tasks.\n - _Strong finite-sample guarantees._ The authors show that miscalibration decays at a rate of $O(1/\\sqrt{T})$ under mild assumptions, even in nonstationary and adversarial environments.\n - _No-regret recalibration of existing models._ The framework extends to recalibrating forecasts from existing models, ensuring both calibration and no-regret performance while leveraging the inductive biases of these models.\n - _Clear and cohesive presentation_. The paper is well-structured and well-written. The framework and results are presented in a way that feels cohesive and easy to follow. The notation is clear.\n \n## Weaknesses\nThe main weakness of this paper is the limited experimental evaluation.\n\nWhile the authors propose specialized algorithms that solve the half space problem for specific calibration metrics, they provide no experiments that assess their computational feasibility and practical performance. The only experiments focus on the gradient-based method (ORCA). Since ORCA lacks theorethical guarantees, experimental validation is particularly relevant here. However, this method is tested on just one baseline and two datasets, limiting the scope of its evaluation.\n\nThe authors also claim their framework can “achieve general notions of calibration for nonstationary data caused by feedback loops, distribution shifts, time series, and adversarial environments.” While this is supported by their theoretical results, it remains unclear whether this can be achieved in practice using either the specialized algorithms or ORCA.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a unifying framework for miscalibration in probabilistic forecasting. The authors model miscalibration as the average payoff of a zero-sum game between a Forecaster and Nature, where the Forecaster's goal is to drive the average payoff to 0. They show that, under mild conditions, miscalibration decreases at a rate proportional to the inverse square root of the number of rounds. They extend this framework to enable recalibrating forecasters with calibration and no-regret guarantees.\n\nThe optimal forecast is found through a minimax problem where the Forecaster minimizes the worst-case forecast error induced by Nature’s actions. As this problem is computationally hard, the authors propose a general gradient-based method that solves a relaxation of this problem and also derive specialized algorithms for specific forms of calibration, such as quantile or moment-based calibration.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Experiments\n- Add experiments to evaluate:\n  - The specialized oracles derived in Appendix C.\n  - Pathological scenarios with feedback loops, distribution shifts, adversarial environments to test the claimed robustness of the methods.  \n- Expand the evaluation of ORCA by:\n  - Including additional baselines for comparison.\n  - Testing on more datasets.\n\n## Related Work\n- Clarify the contributions relative to the current literature. Is the framework described entirely new? If not, what are the novel aspects compared to existing results and methods?  \n\n## Limitations\n- Add a dedicated section discussing limitations of the proposed algorithms (ORCA and specialized oracles):\n  - For example, ORCA is widely applicable, but its approximate optimization procedure lacks theoretical guarantees.\n  - Are there any forms of calibration not supported by the framework or algorithms?\n  - Discuss the computational feasibility of specialized algorithms. Are they practical for real-world applications?  \n\n## Minor Edits and Addtional Questions\n- The paper reads very well. I suggest adding a paragraph at the end of the introduction to outline the structure of the paper, which would further improve readability.\n- Conditions 1-3 appear very general. Could you provide examples (if any) of common scenarios where these assumptions fail?  \n- In the introduction, you state:  \n  > \"We provide finite-sample calibration guarantees [...] to any form of calibration fitting into our framework.\"\n\n  Are there commonly used forms of calibration that fall outside this framework? If so, these should be explicitly mentioned.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IvYrYfD4hi", "reviewer": "Reviewer_dQat", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not familiar with literature in game theory but to me,\nStrengths\n- The game theory formalism fits many notions of calibration that can be written as pay-offs and is insightful. \n- The proposed gradient method, despite being an approximation, seems perform well, at least not worse than existing methods.\n- The paper is generally clear, and an enjoyable read. Thank you!! \n\nWeakness:\n- The behavior of Algorithm 2 does not seem well understood. I suspect there is a way to quantify loss due to the approximation from equation (8) to (9) and having a residual term in pay-off.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- The author(s) proposed a game-theoretical framework to study calibration in online learning settings. \n- From the framework, the author showed an algorithm can achieve calibration when having access to an oracle. \n- For some notions of calibration, such oracle is accessible, for those not, the author(s) proposed a gradient-based method (ORCA) to approximate.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Could the author comment on how the approximation made from eq (8) to eq (9) might impact the calibration if not showing a result?\n- One thing I am a bit confused about, which might be due to the lack of background, is how the feature $x_t$ enters the theory. It was carried in the pay-off function and as the authors noted so long as the pay-off takes the form that $x$ only in the condition function their theory would carry through. I would imaging a forecaster deciding their $p_t$ partly based on $x_t$, I wonder how this type of dependency is captured in the framework. E.g., as the authors noted in binary distribution, calibration one wants $P(y_t=1|p_t\\approx p)\\approx p$ to happen often. I wonder is there a notion that this also condition on $x_t$? Can something like this be written as the general pay-off the authors worked on?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The author's revision addressed concerns brought up during the reviewing process. In their revision, they:

- Added a new experiment with adversarial data to demonstrate the effects of their proposed method in specialized scenarios
- The authors discussed how the gradient-based relaxation of their method affects performance and computation.
- The authors improved their discussion of limitations.

Even before this revision, the paper was well-structured and clear, discussed theoretical and practical aspects of their algorithm, and brought a new perspective to online calibration. All reviewers agreed that this paper would be more compelling with additional experiments that demonstrated the proposed method (ORCA) in other environments and across more datasets; however the existing results provide evidence for the method.

As is, this paper meets the criteria for acceptance at TMLR.
Decision: Accept (poster)