Dimension-Free Decision Calibration for Nonlinear Loss Functions
Authors: Jingwu Tang
Jiayun Wu
Steven Wu
Jiahao Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: Calibration
Uncertainty Quantification
Decision Making
Primary area: learning theory

Abstract: When model predictions inform downstream decisions, a natural question is under what conditions can the decision-makers simply respond to the predictions as if they were the true outcomes. The recently proposed notion of decision calibration addresses this by requiring predictions to be unbiased conditional on the best-response actions induced by the predictions. This relaxation of classical calibration avoids the exponential sample complexity in high-dimensional outcome spaces.
However, existing guarantees are limited to linear losses. A natural strategy for nonlinear losses is to embed outcomes $y$ into an $m$-dimensional feature space $\phi(y)$ and approximate losses linearly in $\phi(y)$. Yet even simple nonlinear functions can demand exponentially large or infinite feature dimensions, raising the open question of whether decision calibration can be achieved with complexity independent of the feature dimension $m$. We begin with a negative result: even verifying decision calibration under standard deterministic best response inherently requires sample complexity polynomial in $m$. 
To overcome this barrier, we study a smooth variant where agents follow quantal responses. This smooth relaxation admits dimension-free algorithms: given $\mathrm{poly}(|\mathcal{A}|,1/\epsilon)$ samples and any initial predictor $p$, our introducded algorithm efficiently test and achieve decision calibration for broad function classes which can be well-approximated by bounded-norm functions in (possibly infinite-dimensional) separable RKHS, including piecewise linear and Cobb–Douglas loss functions.

Published as a conference paper at ICLR 2026
DIMENSION-FREE DECISION CALIBRATION FOR NON- LINEAR LOSS FUNCTIONS
Jingwu Tang, Jiayun Wu, Zhiwei Steven Wu, Jiahao Zhang
School of Computer Science
Camegie Mellon University Pittsburgh, PA 15213, USA
(jingwut, i zstevenwu, jiahaoz4] @m edu
ABSTRACT
When model predictions inform downstream decisions, a natural question un- der what conditions can the decision-makers simply respond to the predictions as if they were the true outcomes. The recently proposed notion of decision cali- bration (Zhao et al., 2021) addresses this by requiring predictions to be unbiased conditional on the best-response actions induced by the predictions. This relax- ation of classical calibration avoids the exponential sample complexity in high- dimensional outcome spaces. However, existing guarantees are limited to linear losses. A natural strategy for nonlinear losses is to embed outcomes into m-dimensional feature space o(y) and approximate losses linearly p(y). Yet even simple nonlinear functions can demand exponentially large infinite fea- ture dimensions, raising the open question of whether decision calibration can be achieved with complexity independent of the feature dimension gin with a negative result: even verifying decision calibration under standard deterministic best response inherently requires sample complexity polynomial in m. To overcome this barrier, we study a smooth variant where agents fol- low quantal responses. This smooth relaxation admits dimension-free algorithms: given (IA) 1/c) samples and any initial predictor p. our introducded algo- rithm efficiently test and achieve decision calibration for broad function classes which can be well-approximated by bounded-norm functions in (possibly infinite- dimensional) separable RKHS, including piecewise linear Cobb-Douglas loss functions, and any Lipschitz differentiable functions.
We be-
INTRODUCTION
Machine learning models increasingly underpin decisions in high-stakes scenarios, such med- ical diagnosis and financial forecasting. In these settings, model predictions inform downstream decision-maken who act to optimize their utilities. Formally, there is underlying distribution D over the spaces of covariates X' and outcomes V and the goal is to learn a predictor p: X' - y that supports decision-making
Given an action set A. decision-maker follows decision rule k X' - A (AA) that utilizes predictions to minimize the expected loss incurred by a loss function A IR. Often, these scenarios encompass not just a single, known loss function but rather broad class of potential loss functions L. For instance, different stakeholders in healthcare might prioritize different aspects of the outcome, while financial investors vary their tolerance for risk.
When should decision-makee maker treat prediction p(x) as if it were the true outcome y? Calibration provides a principled answer. A predictor calibrated conditioned on every output value v, the true outcome is on average equal to c. That is, E[ p(X) v|
While calibration can be trivially achieved with a constant predictor p(x) = E|Y], such predictors are uninformative. In practice, calibration is often enforced via post-processing to simultaneously recalibrate the model and reduce its mean square error of prediction. If the loss function E(a, y)
'lll authors are listed in alphabetical order.

---

Published as a conference paper at ICLR 2026
is linear in y, Decision-makers treat predictions reliable substitutes for outcomes. Best sponses computed from calibrated predictions are indeed optimal actions for true outcomes, given the information from p(X) (Foster & Vohra, 1999; Noarov et al., 2023). However, achieving cali- bration high-dimensional outcome spaces is computationally and statistically intractable, because it requires exponentially many samples verify the unbiasedness of prediction over exponentially many events of {p(x) F} (Gopalan et al., 2024a).
To circumvent this curse of dimensionality, Zhao et al. (2021) introduced the weaker notion of decision calibration. Unbiased predictions are only required for events relevant to action selection. As result, decision calibration ensures that predictions p(z) yield loss estimates that are statistically indistinguishable from the true losses from the perspective of decision- makers. For a loss function l E L. and a decision rule k, a predictor p decision calibrated if
E(r.)))-BBB--(()) [a(a, y)] ((rra))-BBu-(())B [K(a, p(z))]
Notably, both the verification and the post-procsssing algorithm for decision calibration cost poly- nomial time under high-dimensional settings. We defer additional discussion of related work to Appendix E.
However, prior work on calibration for decision-making (e.g., Foster & Vohra (1999); Zhao et al. (2021); Noarov et al. (2023)) have focused primarily on linear loss functions. Linearity is crucial for optimality of best-response actions to calibrated predictions. Yet, many real-world decision-making scenarios naturally involve non-linearities. For example, risk-averse investors penalize large losses more heavily. Clinicians have risk-sensitive objectives that assign greater weight to severe medical outcomes.
A natural strategy is to linearize loss functions through a feature expansion y + H. such that the loss function l(a, y) be expressed (or well approximated) linear operator in the higher-dimensional space H:
E(a, v) (re(a), d(1))
In this paper, we learn a decision calibrated predictor p : X' - such that p(x) induces loss estimates indistinguishable from those of é(y). However, practical loss function classes-such as certain subclasses of Lipschitz cunetions-typicaal ture expansion. Since prior results on decision calibration (e.g.. Zhao et al. (2021)) have sample complexity polynomial the outcome dimension, standard decision calibration becomes computa- tionally and statistically intractable when applied to these high-dimg sigh-dimessionll feature expansions. To address this challenge, we develop the framework of dimension free decision calibration, which ex- tends decision calibration to broad classes of non-linear loss functions without incurring dependence of sample complexity on the dimension of the feature space H.
require exponentially large dimensions of fea-
Our contributions.
1. Lower bound under deterministic best response. The standard "hard-max" best response de- cision rule selects the action which minimizes the loss assuming the outcome perfectly pre- dicted. For a m-dimensional feature space H. we show that auditing decision calibration requires ((ym) samples. The lower bound is proved by constructing two nearly indistinguishable dis- tributions-one decision calibrated and the other miscalibrated-uuiin the fact that there exist d points that can be shattered by halfspaces in a d'diimensional space. To the best of our knowl- edge, this is the first lower bound of statistical complexity established for decision calibration. Our lower bound provides evidence that non-trivial dimension free decision calibration algo- rithms do not exist under the deterministic best response decision rule, motivating our adoption of a smooth decision rule.
2. Dimension-free auditing under smooth best response. We then consider quantal response, smooth optimal decision rule that stochastically select actions according to loss estimates. Quan- tal response has been extensively studied in economics and decision theory (McFadden et al., 1976; McKelvey & Palfrey, 1995), as it naturally captures bounded rationality and accounts for probabilistic decision-making
e Blrr(c))pp(=)
(x, a) = En plrr--rr"))
For quantal responses, we show that there exists a dimension-free auditing algorithm. With high probability, it can identify loss function witnessing e/2-decision calibration error whenever
2

---

Intuitively, Definition 2.1 requires the function ((a, .) y - R to be uniformly approximated by functions 9a : y - that are linear in some feature space for any a. We provide two families of feature Published as a conference paper at ICLR 2026
the predictor has e-decision calibration error, using only poly([A), 1/c, 3/,,3) samples, independent of m. This sharp dimension-fi guarantee achieved through carefully designed pseudometric that projects loss vectors in -ighenimesiooall space into mne-dimnsioonal space. By exploiting the smoothness of the quantal response, the covering number under this pseudometric remains bounded, whereas the covering number under the standard metric would be infinite when is unbounded.
Dimension-free algorithm for decision calibration. Building on this auditing tool, we de- sign patching procedure that post-processes any predictor into that is e-decision calibrated, without worsening its mean square error. This guarantee applies broadly to function classes rep- resentable well-approxxmmtee by bounded-nowd linear, Cobb-Douglas functions, and more generally, any Lipschitz differentiable functions. No- tably, in terms of e-dependence, our algorithm improves upon the finite- sample version of the algorithm in Zhao et al. (2021). Our sample complexity scales as 1/e",, compared to 1/e" in their algorithm.
functions in RKHS, including piecewise
PRELIMINARIES
Notations We consider the prediction problem for decision making with context space X' and a compact convex outcome space y S IRd Let denote the distribution over X' x V Given any dataset D {( y=) that is drawn i.i.d from D and any function v X x y + R, define the empirical expectation as En(bb(,, v)l = Di=1 vi( y:). For any integer n, we use [v]] to denote the class [1....,n) .n..
2.1 LOSS FUNCTIONS AND UNIFORM APPROXIMATIONS
We model downstream decision makers as having a finite action space .A and a loss function Axy- [0, 1]. which maps action-outcome pair bounded loss. Let L denote family of such loss functions. To handle nonlinear losses, we adopt a standard approach of approximating them via feature mapping y H. where H. is (possibly defiite-dimensionall feature space. The idea is to approximate each E C by a linear function of e(y). Once this approximation is established, we show the following sections that decision calibration becomes achievable for such loss classes. When the feature space is kmite-dimensional we write H Rd with dim( m < cc. We also consider the case where is a separable reproducing kernel Hilbert space (RKHS), which has a countable orthonormal basis, and dim can be
We formally define this approximation framework as follows:
Definition 2.1. Let & : H be feature map and L a family loss functions. We say that é provides a (H), --nnf-uno approximation to L if for every & E L. there exists a function Te A H. such that ((r(()). ((y)) f(a. y)1 S. e and [[re(a)llx S for all E and y Y.
functions from the economies literature as examples that are linear in space in Appendix
2.2 PREDICTORS AND LOSS ESTIMATORS
We define the notion of predictor given feature mapping function p X + H. interpreted as estimating the conditional expectation B[ø(y) x). Since the feature space H can be high-dimensional even mnfiite-dimensional. the predictor p(x) can be complex and may lack an intuitive interpretation for downstream decision makers.
H. predictor is
To address this, we do not expose the predictor directly. Instead, we use to construct loss estimator fp. which takes input context x, an action and loss function f, and outputs an estimate of the expected loss f(a, y) given x. We formalize this notion below:
Definition 2.2 (Loss Estimator). A loss estimator function f X x Ax R. For any context I E X, action a E A, and loss function E C. the output f(z, a, E) estimates the expected loss E(((a, v) xc)
3

---

Published as a conference paper at ICLR 2026
Although the definition of f does not require explicit association with a predictor, in approach the learned loss estimator is implicitly derived from an underlying predictor p. Specifically, when such a predictor is maintained, the loss estimator takes the form fp E) (rz(a), p(z)), where re(a) is the coefficient vector associated with the loss function E, as defined previously.
2.3 DECISION RULES AND DECISION CALIBRATION
In ideal setting, if a decision maker with loss function has access to the full distribution D. they can compute and play the optimal action: a' = arg min.e.4 Eple(a, y)]. However, in practice, decision makers do have access to the full distribution. Instead, they rely on the loss estimator f to make decisions. Given a context the decision maker queries the estimated loss f(z, a, E) for each action a A and selects an action accordingly.
We formalize the decision maker's behavior via a decision rule, which is function h : X' A + [0. 1]. representing the probability of selecting action given context x. A common strategy is to select the action that minimizes the estimated expected loss:
Definition 2.3 (Optimal Decision Rule). For a given loss function and loss estimator f, the optimal decision rule is defined as:
if = arg argmina E. [xx ,), kz,((z,a) = {
otherwise.
We also consider a smoothed version of the optimal decision rule, commonly referred to as the quantal response model in economics and decision theory. The quantal response model has been extensively studied in the literature (see e.g.. (McFadden et al., 1976; McKelvey & Palfrey, 1995)).
Definition 2.4 (Smooth Optimal Decision Rule). For a loss function f, loss estimator J, and inverse- temperature parameter B > 0, the smoothed optimal decision rule is defined as:
6 (8f(2,0,8)
kg,e(I,a) a) = Ev E
For convenience, we sometimes use k(x) to denote the probability distribution over actions induced by a decision rule We now restate the definition of decision calibration, originally introduced by Zhao et al. (2021), with our notion of the loss estimator:
Definition 2.5 (Decision Calibration). Let be a class loss functions and be a class of decision rules. A loss estimator is said to be (C, deciiiioo calibrated if for every & L and every decision rule k E X.
B( y)1 =
(1)
We define the decision calibration error as: decCF=2,(()== = sup ((te.))DDDB (C(a, y)] B( Ban (S a, 0)]-
REC, KEK
We say that a loss estimator is KC, deecciionn calibrated if (f)
To interpret equation 1, the left-hand side represents the true expected loss incurred when the agent follows the decision rule k, while the right- hand side represents the estimated expected loss based solely on the loss estimator f. The agent can compute this estimate without access to the true outcome y. Intuitively, decision calibration ensures that the estimator / accurate across all relevant loss functions and decision rules.
We use KC == (kelf E C} to denote the class of decision rules induced by any loss function E under the best response decision rule. Similarly. we use Kzn, := {īelee E L} to denote the class of decision rules induced by any loss function E L under the smooth best response decision rule.
We now discuss how the uniform approximation can help to achieve decision calibration. Let Es denote the class of loss functions for which the feature mapping o y - H gives (dim (H), G)- uniform approximations and let E. = {ê: : E(a, y) = re(a) )(y)} denote the associated class of linear functions. Then given any predictor p X > H. we define the loss estimator fp as
f,(x, (re(a), p()))
4

---

Published as a conference paper at ICLR 2026
for any context X, action A and loss function 8 Lg. The following lemma shows that if the loss estimator fp e/ e/2-decision calibrated for class L.. it is e-decision calibrated for class Cs- Lemma 2.1. Let L.g denote the class of loss functions for which the feature mapping & y - H gives (dim(H.,, X, --uniform approximations and let Ls {é : E(a,y) y) = re(a)- } denote the associated class of linear functions. For any predictor p : - H. any class of decision rule K. and the loss estimator fp (L,, calibrated.
calibrated, then fp is (Cos K, c)-diiiio
This lemma implies that, to obtain e-decision calibrated predictor for the function class C.x, it suffices to construct an e/2-decision calibrated predictor for its uniform approximation class.
LOWER BOUND UNDER DETERMINISTIC OPTIMAL DECISION RULE
In this section, we investigate whether a dimension algorithm for decision calibration is possible under the optimal decision rule. We establish statistical lower bound on the sample complexity of testing approximate decision calibration. In particular, we show that any algorithm requires at least M d) samples to determine whether a predictor is decision calibrated. To the best of our knowledge, this provides the first lower bound result for decision calibration.
Note that we choose not to prove a lower bound for computing a decision-calibratee predictor di- constant predictor always outputting the mean outcome
rectly because trivial solutions Suuth -[an satisfy both decision and full calibration.
To prove lower bound, consider simple setting where the number of actions [A] 2, the feature mapping is Φ(y) = y, the class of loss functions is linear LLN = {E Va, 3rr(a), [ S y,) (re(a), y)} with their corresponding optimal decision rules KELIN. Our result shows that distinguishing whether predictor (and its induced loss estimator f) CCLIN,KC,Ls Oddecciion calibrated versus not (LLIN, K e)-deiiso calibrated requires sample complexity that depends polynomially on the dimension of V. Since the proof involves con- structing multiple distributions, we will slightly abuse notation and add another argument for in the definition of decision calibration error, that is
(I,
sup &EC,
((a, v)]
()]-
For simplicity, consider the special case where X' y and the predictor i the identity function, ie., p(z) = x, and so input data take the form (p(x1). v1). (p(x2), (p(x2),92),.. (p(In); (n)))...) Now we ready present the lower bound result:
Theorem 3.1. Let
(0.1/3), Y -y Ey BRd S 1}. and fo be the loss esti- mator induced by some predictor p: X +. Let A be any algorithm that takes samples (p(x1), v1), (p(x2), (.....,((((z,, (. Yn) drawn i..dd. from distribution D. Suppose that A is guar- anteed to output "accept" with probability at least 2/3 whenever decCE (f,D) 0 and guaranteed to outpul "reject" with probability at least 2/3 whenever decCE,L.ns, KLAN D) Z
c. Then the sample size n 2 ((Vd).
The proof of Theorem 3.1 follows an indistinguishability argument akin to that of Gopalan et al. (2024a): given predictor p. we construct nearly identical distributions, D, and D2. such that only Dj satisfies decision calibration. We show that distinguishing which of the two distributions generated the data requires least (2vm) samples. However, our setting departs significantly from Gopalan et al. (2024a), who study lower bounds for full calibration, which is stronger than decision calibration. As a result, our construction of D2 and D: differs substantially and leverages the geometry of best response regions. When the action set A consists of two actions, these regions correspond to half-spaces of the form (())) > 0J. The core idea behind constructing D2 is to introduce a subtle bias in the outcomes--pecifficall a deviation (y p(r))- is statistically difficult to distinguish from pero-mean label noise. Simultaneously. using a "shattering argument" show the existence of loss function such that the associated half-space
from VC theory, captures a biased region. Consequently, the predictor p fails to satisfy decision calibration under Dz, We leave the formal proof of Theorem 3.1 in Appendix I.
5

---

Published as a conference paper at ICLR 2026
This lower bound result also exhibit barrier result for dimension-frt algorithm for achieving decision calibration under the deterministic optimal decision rule. All existing decision calibration algorithms with provable guarantees proceed by iteratively post-processing A key component of these algorithms is the auditing step, which, in each iteration, identifies loss functions that witness large decision calibration error whenever the predictor is not calibrated, and returns nothing when the predictor is already calibrated (Zhao et al., 2021; Gopalan et al., 2022b; 2024a). Note that any auditing algorithm will necessarily require ((vd) sample complexity based on Theorem 3.1.
initial predictor Po-
AUDITING OF DECISION CALIBRATION FOR FUNCTIONS IN RKHS
In Section 3, we showed that under the optimal decision rule, impossible to even determine whether predictor is decision calibrated. This provides strong evidence that it is unlikely that non-trivial decision calibrated predictor can learned with sample complexity independent of the dimension We present first positive result. By instead focusing on the smooth optimal decision rule, it becomes possible to design an algorithm with sample complexity independent of m. In this section, first address the auditing problem that is, identifying a pair of loss functions (E, (') that violate decision calibration and show that this can be achieved with sample complexity independent of m.
We focus on the auditing problem for functions in RKHS, since RKHS is the most general feature space considered in our paper. In detail, let H denote RKHS associated with the kernel function K : y x y + R. From now on, for simplicity we restrict attention to loss functions H with bounded norms, that is, define Lx {e: Va, ((a,) -) E H. [le(a, -)Ilx S R. From Lemma 2.1, the result will naturally generalize to the loss function classes that cannot be exactly represented by bounded norm functions in H. but well approximated by them (while having an extra approximation error in the eиror bound). For consistency of notation, we use (e( to denote {(a -). Let Φ : y + H
be the feature mapping induced by kernel K, i.e. (0y) K (y, .) and assume that [|((()]] S R2-
To ensure the loss estimator is computationally realizable, we constrain all predictors p P + H to lie in the span of finitely many feature mappings.
N
p(z) Σ (x())())))
where Np is the number of samples for estimation and a; X - R is coefficient function for any E [Np]] For any predictor the aforementioned form, we can define the loss estimator fp as fp(x, a, f) (re(a), (re(a),p(x)),, Ein (z)))((a,)))
We focus on the smoothed decision rule ky,., defined in Definition 2.4. Let Ken, denote the class of such smoothed decision rules. We first show that decision calibration (Definition 2.5) for fp has an cquivalent but more intuitive formulation.
Lemma 4.1. For a loss estimator fp derived from the predictor p. it is (Lu, Kews de-diiiio cali- brated if and only if
A Σ
sup E.
B(Z,y)<
(re(a), (()))),()) p(x)) p(x))
SE.
An auditing algorithm is supposed to verify decision calibration with finite samples. In particular,
the auditing problem asks whether can witness a violation of decision calibration by explicitly presenting pair of loss functions (L) that exposes miscalibration according to Equation (3).
Definition 4.1 (Auditing). An c-auditing algorithm (or c-auditor) takes (p(x1). 1), v..,...(pl ().(((())))))))))))))))))))))( yn)
as inpul, when decCE( D) 2 e, with probability 8, it witnesses a pair of loss functions such that
LA
E (D
Σ
(re(a), o(v) - f
2 2//2.

---

Published as a conference paper at ICLR 2026
As the first step of developing dimension frre auditing algorithm, establish uniform vergence bound for the audited error of decision calibration. The upper bound is polynomial with respect |A] and i/c, while being independent of the dimension of H. We consider function class parameterized by a pair of losses (f, ()), which collects all the possible calibration gap functions.
LAI
G = [are e, E LH}, where (p(())
Σ (rela), olv) p())) (4)
a=l
We establish the uniform convergence property for G by showing that the covering number of G remains bounded, even when H. is infiiitedimmesiional. Formally, we state the following theorem.
Theorem 4.1. Let D ((11131),..... (In, Yn) be the dataset where (I,, Us) is drawn i.i.d. from D. Given any predictor p X + H. for the function class 9 defined in Equation (4), we have that
sup B(x.)) e (p(z), <(v))] - pla.))-plu.c(()))). S o o
Ci (2n) + 1og(1/0)
d Eg
n2
where C1 = = ||| B and C2 = R2
Proof sketch. By standard Rademacher argument, it suffices to prove class G has dimension free finite Rademacher complexity. Since each function in the class is parameterized by pair of loss functions E, e E Cr. Dudley's chaining technique implies that it is enough to upper bound the covering number N (C4 Lrs, T.g (Pn).e) where P, is the uniform distribution over dataset and Lg (Pr) is defined as
18 (E(P)) ((,E,)
(ge (p(x)) ge ez ( o(v)))
In order to bound the covering number N(CH x Cn. LP observe that for any l E Cu and any a E A, re(a) is in the Hilbert ball B(Ry) with radius R1 since [|re(a)] S Rj. This allows us to connect the covering number we want to bound to a known finite covering number ((B(R)), dp, e) where P is an arbitrary distribution on the Hilbert ball and dp defined as
d(re, re, (a)) /Ex-P (re, (a) TE, (a), xy3]
where X a random sample in the Hilbert ball drawn from distribution P. Intuitively, de first projects the differences 0 - 0' along random direction given by the prediction of random example p(X) and then measures the distances in this projected one-dimensional space. For the formal proof, Appendix K.
As corollary of Theorem 1.1, we can develop an ERM oracle that serves as an auditing algorithm. The loss function of the ERM defined as
IA
DDeeCaale (e,l" xx y) = gt,e (p(x) o(v))
Σ (re(a), (()) - -()))(())))))))))) -x
Theorem 4.2 (ERM as Auditing Algorithm). Let D (1 vi),... (Ins Hn)3 be the dataset that each data point is drawn i..dd. from D, given any predictor p X - H. the ERM algorithm that outputs
i t arg max E.
Σ
L Dzs v:).
1=1
when Z RR ERM algorithm is e-auditor.
In fact, solving ERM is stronger than solving the auditing problem. Auditing does not require identifying the pair of loss functions that maximizes the empirical decision calibration error; it suffices to find a pair for which the empirical enror is large enough to certify that the true expected decision calibration error exceeds e/2 (Definition 4.1). To avoid potential misinterpretation. our algorithm Algorithm assumes only the existence of an auditing oracle, rather than requiring an ERM oracle.

---

Published as a conference paper at ICLR 2026
5 ALGORITHMS OF DECISION CALIBRATION FOR FUNCTIONS IN RKHS
In this section, we discuss algorithms of decision calibration for functions in RKHS. In Section 5.1, we first present our algorithm SimFreeDeCCl (Algorithm 1) to achieve (Cx, Æexy t)-decision calibration. The patching component of our algorithm is motivated by the weighted calibration framework introduced by Gopalan et al. (2022b), based on the observation that decision calibration can be viewed special case of weighted calibration. However, their algorithmic framework is not directly applicable to our setting, as it patches the predictor in the dinee-dimensionll setting, whereas formulation requires handling more general (potentially snfiitt-dimensiinall) prediction space. We will discuss how to address challenges in the dimnite-dimensional setting.
Zhao et al. (2021) also proposed algorithm for achieving decision calibration under the smooth optimal decision rule in the finite-dimensional setting, given the access to the full data distribution. However, their algorithm does directly extend to the finite-sample tings. In Appendix M, we describe how to adapt their algorithm to achieve provable finite-sampy sample guarantees and extend it the defiiie-dimensiinnn case. Notably, our proposed algorithm achieves sample complexity of Ö(L/e*), which improves upon the ((1/e") sample complexity of the mod- ified version of their algorithm.
lnfnite-dimeesiinall set-
5.1 DIMENSION-FREE DECISION CALIBRATION ALGORITHM
In this section, we propose our algorithm build the connection between decision calibration and weighted calibration. Building on this con- nection, we address the novel challenges of patching the diminte-dimensionll setting and present our algorithm in Section 5.1.2.
(Algorithm 1). In Section 5.1.1,
5.1.1 DECISION CALIBRATION AS WEIGHTED CALIBRATION
We restate the definition of weighted calibration introduced by Gopalan et al. (2022b) and extend to the RKHS setting.
Definition 5.1 (Weighted Calibration Gopalan (2022b)). Let W H - H be a family of functionn.. We define the W-calibration error as
CFw(p) sup (ED((((p(<)) p(x) (v))xll
wEW
say that the loss estimator fp (W, ccalibrrdd if (Pw S
The weighted calibration algorithm follows an iterative template: at round f,
1. Use an auditing algorithm to check whether pt is weeigheed calibrated. If it is, ter- minate the algorithm.
2. If not, identify the weight function wi E W that incurs the largest W-calibration emror.
3. Update the predictor (x) = Pr (x) + we (x))),, where 7) is the step-size hyperpa- rameter.
Next we will show the connection between decision calibration and weighted calibration. By Lemma 4.1, the decision calibration error of a loss estimator fp can be written as
decCE Cn Ren (fz)
((a.))-DEas (((a, v)] E(nn)) If(x, e)]
BELn,kEReH
AAI
sup e.EEC
B
(re(a), ((v))))(() p(z)))
LA (e, p(ar)
sup e,
Be
Σ
Therefore, decision calibration is a special instance Wate- for Wase = {weee (p(()(()) E!AI re(a)),,, a), E LH).
8

---

Published as a conference paper at ICLR 2026
5.1.2 PATCHING IN THE INFINITE- DIMENSIONAL SETTING
The first challenge in the aniiite-dimensionne setting is that we need restrict the predictor in the form of Eq. (2) so that we can use the reproducing property to construct a loss estimator fp. There- fore, in each round once we find l. e that violates the decision calibration, we cannot directly follow the original weighted calibration algorithm template to update the predictor by patching we,44 unless Te, (a) can be explicitly expressed by the linear combination of ((y).
However, note that
M
A (re, (a),), - ((x)))e((zz
re, (x, Φ(v) - pe(s))
E
=
Bl(á(v) pr(x)) (I. (r,
R
Equality holds when re; (a) = (u (x.) (,)r))
a) On
the one hand, once we identify a pair of (le, f)), replacing & with E will make the violation worse On the other hand, rı; (a) can be expressed by the linear combination of Φ(v) (we will use the empirical expectation to approximate the true expectation). Therefore, in each round t, we can use fz update the predictor pt.
Algorithm DimFreeDDCCll
Input: The RKHS kernel K, current predictor po X > H. tolerance and step 0.
1: while supe,y B(EEA) (x(a) ()) (c(x)) > do
2: Find l,, ' such that ( rh, (a)ke (x,,),,) (2,
pr((x))] 3e/4.
3: Define the adjustments
- dr = (t ( pr(=))ko (z, a))l
4: Set P1+1 x - (x) E dea ke (z.
5: Set P1+1 + (B))2) (x)). 1/T)(R2) projects onto Hilbert ball B(
6: end while
Intuitively, the algorithm proceeds as follows. In lines 2-3, we invoke the auditing oracle: if the loss estimator fp is not (Cx, Ken, e)-decision calibrated, we can identify pair (&,, () that the empir- ical decision calibration error exceeds 3e 3//4. In line 4, previously discussed, for (Le, E to define the patching term so that the updated predictor can remain to be explicitly ex- pressed as linear combination of (ty). Lines 5-6 then carry out the patching step. Notably, not perform computations directly with px (z), as it may reside in an anfinite-dimensione space. To address this, we introduce the technique of implicit patching. The key idea is perform patching im- plicitly by maintaining linear representation of the form (.( = E an (t)()))))))) That is, we keep track of the functions og X - IR and the corresponding outcomes yrs for all t and E [N,]. Given this representation, we can efficiently compute the value of the loss estimator fp, (x, a, for any loss function l. Lu as follows fp. a,), = (r((a) En (r(())((a,Bi) Formally, we have the following proposition.
substitute (ei ()
Proposition 5.1. For Algorithm 1, if the input predictor satisfies po(x) = Σn anx ( the for any we have (e():) EN, (x)()))
Given Proposition 5.1. we can perform patching implicitly by keeping track of the coefficients in- stead of directly computing Pt.
Now we are ready to present the main result of this section.
Theorem 5.1. Given any initial predictor Po and tolerance e, Algorithm 1 terminates in T
RC 22
iterations. Given Ō L R R² samples, with probability 5, Algorithm I outputs
0

---

Published as a conference paper at ICLR 2026
predictor pr such that for is (Cu, KEns e) deciisinn calibrated and Bllpp((x) - <(v)l 1 B[l)po(x) (b)
This theorem establishes that Algorithm 1 produces decision-calibrated predictor that preserves the performance of the initial predictor, requiring only finitely many samples that do not depend on the dimension m..
To conclude, this paper investigates when model predictions can be made decision-calibrutee for nonlinear downstream losses, especially when naive embeddings y H p(y) E R make large or infinite. We first show a limitation: under deterministic best responses, even verifying decision calibration can require sample complexity polynomial in m. We then introduce smooth variant and an accompanying algorithm that achieves decision calibration with poly 1/c) samples indepen- dent of m, without degrading the base predictor terms of &g losses, and covers broad nonlinear losses via bounded-norm functions in separable RKHS.
ACKNOWLEDGEMENTS
ZSW was partially supported by NSF CAREER Award, an NSF SaTC grant, and an STTR grant. We thank Aaron Roth for feedback on an earlier draft of this work and Lunjia Hu for helpful suggestions on the lower bound.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of dis- tance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Com- puting, pp. 1727-1740, 2023.
Modibo K Camara, Jason D Hartline, and Aleck Johnsen. Mechanisms for a no-regret agent: Beyond the common prior. In 2020 ieee 6lst annual symposium on foundations of computer science (focs), pp. 259-270. IEEE, 2020.
Natalie Collina, Aaron Roth, and Han Shao. Efficient prior-free mechanisms for no-regrel agents. In Proceedings of the 25th ACM Conference on Economics and Computation, pp. 511-541, 2024.
Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Outcome in- distinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1095-1108, 2021.
Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Beyond bernoulli: Generating random outcomes that cannot be distinguished from nature. In Interna- tional Conference on Algorithmic Learning Theory, pp. 342-380. PMLR, 2022.
Cynthia Dwork, Chris Hays, Nicole Immorlica, Juan Perdomo, and Pranay Tankala. From fair- ness to infinity: butcome-inndisinguistee arXiv:2411 1, 17582, 2024.
(omni) prediction in evolving graphs. arXiv preprint
Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng. Full swap regret and discretized calibration. arXiv preprini arXiv:2502.09332, 2025.
Dean Foster and Rakesh Vohra. Regret in the on-line decision problem. Games and Economic Behavior, 29(1-2)77-35, 1999.
Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multi- calibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2725-2792. SIAM, 2024.
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Om- nipredictors. arXiv preprint arXiv:2109.05389. 2021.
Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishabilit. arXiv preprint 1rXiv:2210.086//4 2022a.
Parikshit Gopalan, Michael P Kim, Mihir A Singhal, and Shengjia Zhao. Low-degree multicalibra- tion. In Conference on Learning Theory, pp. 3193-3234. PMLR, 2022b.
Parikshit Gopalan, Lunjia Hu, and Guy N Rothblum. On computationally efficient multi-class cali- bration. arXiv preprint arXiv:2402.07821, 2024a.
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, and Mihir Sing- hal. Omnipredictors for regression and the approximate rank of convex functions. The Thirty Seventh Annual Conference Learning Theory, pp. 2027-2070. PMLR, 2024b.
Nika Haghtalab, Chara Podimata, and Kunhe Yang. Calibrated stackelberg games:
Learning optimal commitments against calibrated agents. Advances in Neural Information Processing Systems, 36: 61645-61677, 2023.
Lunjia Hu and Yifan Wu. Calibration error for decision making. arXiv preprint arXiv:240.113503, 2024.
Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. U-calibration: Forecasting for unknown agent. In The Thirty Sixth Annual Conference Learning Theeory pp. 5143- 5145. PMLR, 2023.
Jiuyao Lu, Aaron Roth, and Mirah Shi. Sample efficient omniprediction and downstream swap regret for non-linear losses. arXiv preprint arXiv:2502. /2564, 2025.

---

Published as a conference paper at ICLR 2026
Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Optimal multiclass u-calibration and beyond. arXiv preprint arXiv:2405. 19374, 2024.
Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Simultaneous swap regret minimization via kl-calibration. arXiv preprint wrX1v:2502.16387 2025.
David JC MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
Daniel McFadden et al. Quantal choice analysis: A survey. Annals of economic and social mea- surement, 5(4):363-330, 1976.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1);6-38, 1995.
Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High digh-dimmessioal prediction for sequential decision making. arXiv preprint arXiv:2310. 17651, 2023.
Princewill Okoroafor, Robert Kleinberg, and Michael P Kim. Near-optimal algorithms for om- niprediction. arXiv preprint urXiv:2501.17203 2025.
Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In Pro- ceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 456-466, 2021.
Aaron Roth and Mirah Shi. Forecasting for swap regret for downstream agents. In Proceedings of the 25th ACM Conference on Economics and Compulation, pp. 466-488, 2024.
Hal R Varian and Hal R Varian. Microeconomic analysis, volume 3. Norton New York, 1992.
Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. Calibrating predic- tions to decisions: novel approach multi-class calibration. Advances in Neural Information Processing Systems, 34:22313-22324, 2021.
A ETHICS STATEMENT
This work is entirely theoretical and does not involve human subjects, sensitive personal data, or potentially harmful applications. As such, we do not foresee any direct ethical concerns.
B REPRODUCIBILITY STATEMENT
We have provided complete formal definitions, theorems, and proofs in the main text and appendix ensure the reproducibility of our results. All assumptions are explicitly stated, and key lemmas and lower bound constructions detailed. Since contributions theoretical, datasets are involved, and all algorithmic procedures are described in a way that can be unambiguously implemented by others.
C USE OF LARGE LANGUAGE MODELS
We used LLMs solely as writing assistant to polish the presentation and improve readability.
D USEFUL LEMMAS
Lemma D.1 (Property of Traces and Frobenius norms), For any matrix gmxXn the Frobenius norm is defined
n
| =
1=1 ==1==1 1=
We have
12

---

Published as a conference paper at ICLR 2026
1. Tr(AAT) Tr(A" A) ||A||
2. When A, B are square matrices, Tr(AB) VTr(AAT) Tr(BBT) = r|
3. Frobenius norm has submultiplicative property, that is, for any matrix A, B,
||B|| S ||
Theorem D.1 (Hocffding's Inequality for Hilbert Spaces), Let H. be separable Hilbert space. Let X1, .N be independent random elements of H with common mean μ such that ||x,]l Σ B almost surely for any [N]. Let PN = 1
N Ei= X; denote the sample mean. Then for any
E (0, with probability least
2lm(2/))
MÁN al S 2B
N
We will introduce some useful results for proving the uniform convergence guarantee.
Definition D.1 (Covering Numbers). Let (V, d) be a metric space and θ c V. We say {wr C V
is an e-covering of θ if θ c U B(v, e) where B(v,c) := {u E V d(u, )) S c} is the closed ball of radius centered v. The covering number defined as
N(O,d, = min(n: Be-covering of of size n}
Definition D.2 (Rademacher Complexity). Let (21....,2 2n C be sample of points, and function class F of real-valued functions over Z. The Rademacher complexity of F with respect to defined as follows:
1 E, B Rs(F)=
sup Σ (z)) JEF 1=1
n
Theorem D.2, Assume that 21, 2m are i...d. drawn from D, then with probability at least 1 - 6, we have
Dm [Rs(F)) log(2/0)
Σ [(x)) -(a))-EaD(((()))
sup SEF
2m
We consider Hilbert ball B2 for R0 Σ, S 1} Now we introduce the result that upper bounds the covering number of Hilbert balls under some metric induced by probability distribution P. Note that under the common metric (R(),,,, the covering number of the Hilbert balls infinite.
However, under the metric (0, 0*) = v Ex-rl(0 0r, x) the covering number is finite even in the infinite dimensional Hilbert space.
Theorem D.3 (Covering Number of Hilbert Balls MacKay (2003)). P is a distribution on B2, consider the metric (0) / /Ex=rK00 6', 0x There exists universal constant such that for any P, O, we have
log N(B2, dp, 6) S c
Let Pn the empirical distribution, which the uniform distribution over 21, An For a function
class F, we define the metric L (Px)), / (((=))(() - (²) Note that if you plug
P Ps, for the metric de in Theorem D.3, then the metric dp becomes a special case of L (Px)
for f(=) (0, z).
Now we indroduce the Dudley's Theorem which bounds the Rademacher complexity of a function class by its covering number.
Theorem D.4 (Localized Dudley's Theorem). Let S = {.1.-., zn} C Z be sample of points, and function class F of real-valued functioo over Z. For any a 2 O. we have
log N(F L,FFLL55 (Pn),))
Rs(F) < 4a + 12
de.
(5)
13

---

Published as a conference paper at ICLR 2026
E RELATED WORK
Calibration and Decision Making The work most closely related to ours is Zhao et al. (2021), which introduced the concept of decision calibration in the batch setting, where data points are drawn from an underlying distribution. Zhao et al. (2021) primarily examined decision calibration in the context of multi-class classification, where the outcome space Y is finite and the loss functions are linear. Our paper also considers the batch setting, but we significantly extend their framework to broader and more general scenario, allowing the outcome space Y' to be any compact convex set and accommodating non non-linear loss functions. There is a longstanding line of work on cali- bration and decision- making in the adversarial setting, where data are presented adversarially in sequential manner. The seminal work of Foster & Vohra (1999) showed that a decision maker who best responds to calibrated forecasts obtains diminishing internal regret. Similarly to decision cali- bration, there is a line of work in the adversarial setting that tries to achieve some weaker variants of calibration while keeping agents incentivized to treat the predictions as correct (Kleinberg et al. (2023); Fishelson et al. (2025); Luo et al. (2025)). Kleinberg et al. (2023) proposed a notion called U-calibration, which is sufficient for agents to achieve sublinear external regret, bypassing the lower bound of achieving calibration (Qiao & Valiant (2021)). A subsequent work by Luo et al. (2024) gave the optimal bound of multiclass U-calibration. Noarov et al. (2023) studied how to make se- quential predictions for decisiion-makng in the high-dimensional setting, but also relied on the loss functions to be linear. Following the same algorithmic approach as Noarov et al. (2023), Roth & Shi (2024) showed how to produce predictions for agents to best respond and achieve low swap regret. But their regret bound has dependence on the size of the action |AA. Hu & Wu (2024) showed that in the binary setting, the dependence on |A| can be removed while keeping the Ö(vT) regret. There is also work on calibration and decision making in games, such Camara et al. (2020); Haghta- lab et al. (2023); Collina et al. (2024). However, most of these works focus either on linear loss functions or on one-dimensional outcome spaces, whereas our work addresses the more general and challenging setting of nonlinear loss functions over d-dimensional outcomes.
Omniprediction In addition to decision calibration, there is another line of work studying pre- diction and downstream decision making called onniprediction, which was introduced by Gopalan al. (2021). A subsequent Gopalan et al. (2022a) built the connection between omniprediction and outcome indistinguishability (OI), which was introduced by Dwork et al. (2021) in the binary set- ting and was extended the continuous one-dimensional setting by Dwork et al. (2022). In detail, they showed that omniprediction can be achieved by hypothesis OI and decision OI. Decision OI is a weaker notion than decision calibration. While decision Ol requires that predictions be indistin- guishable from the true outcomes with respect to the loss l incurred under the optimal decision rule defined by itself, decision calibration demands this indistinguishabiliyy hold for the loss incurred under the optimal decision rules defined by any loss function 8..
Garg et al. (2024) first studied omniprediction in the adversarial setting. Recently, several papers on omniprediction have leveraged decision Ol to achieve onniprediction efficiently in both batch and adversarial settings. Okoroafor et al. (2025) studied near-optimal omniprediction in the ad- versarial binary setting. Gopalan et al. (2024b) studied how to efficiently achieve omniprediction for nonlinear losses in the one-dimensional batch setting. They proposed the notion called suffi- dimen-iimesiionll feature mapping and inspired our study
cient statistics, which can be viewed on more general feature mapping. Dwork et al. (2024) studied omniprediction in evolving graphs. A very recent work Lu et al. (2025) extended Gopalan al. (2024b) the high-dimensional ad- versarial setting by using a different generalization of the decision OI, first given by Noarov et al. (2023) and used by Roth & Shi (2024). It is worth noting that their work is not directly comparable to ours, even though they also consider d-dimensional nonlinear losses, for the following reasons. First, similar to Gopalan et al. (2024b), their framework to handle nonlinear loss functions assumes a dineesiiinnsi feature mapping, whereas we also address the more general case of infinite- dimensional feature mappings. Second, their focus lies in the adversarial setting, where they employ an online-to-bacch conversion to construct a randomized predictor from scratch that satisfies batch omniprediction. In contrast, our goal is to take an arbitrary predictor as input and output determin- istic predictor that satisfies decision calibration related but fundamentally different notion from omniprediction. Uniform approximation via ditte-dimessional feature mappings has been studied in prior work, such as Gopalan al. (2024b) and Lu et al. (2025), in the contexts of omnipredic-
14

---

Published as a conference paper at ICLR 2026
tion and online decision swap regret. Our formulation generalizes this idea to feature spaces.
Calibration and Reproducing Kernel Hilbert Spaces (RKHS) RKHS has also been introduced in the context of weighted calibration (Gopalan et al., 2022b). Btasiok et al. (2023) and Gopalan et al. (2024a) consider weight functions that are bounded- norm functions an RKHS. However, the role of RKHS in our work is fundamentally different. While these prior works use RKHS for the weight functions, we use to represent the loss functions. Specifically, their approach involves computing the inner product between the weight function and the difference p(æ) y. which preserves the original outcome space. As result, achieving weighted calibration with bounded-nore weights in an RKHS does not translate to decision calibration for non-linear losses.
F LINEAR FUNCTIONS IN RKHS
Example F.1 (Continuous Piecewise Linear Functions). Consider the case y [0, 11. Define family of functions to be G = Ka,e ve E [o, [ka] S R, ligl I R) where
k2y key + (k1- - k2)c csysl.
0 y <c
9k,,
This defines class of piecewise linear functions with an unknown turning point c. Piecewise linear functions of this form have been extensively studied in the economics literature. The function 9h, tq.c can be interpreted as a utility function (or the negative of a loss function), where y denotes the consumption level of particular good. It captures a common economic scenario in which marginal utility decreases once consumption exceeds a threshold c.
Next we show that functions in G are linear in infinite fimiitt-dimensionalll feature space. Let H be the RKHS with kernel
K(y1, y2) min (y1, (y1,92).
Let p(y) = K (y,,, be the feature mapping associated with K. We have
9k. k2.c = (k22(1) + (k1 - 12) k2))(c),
In addition, we have (1) + (k1 --)2 R.
Example F.2 (Cobb-Duue Sobbl-Duglas Functions). Consider the case y = {y E R llull I 1}. Define family of fanctions be {ga> Va E [0, 1] s.l. Exeld ai = 1] where
(a(v) = Cien a.y.
This defines the class of Cobb-Douglas functions exponential form. Cobb-Douglas functions widely used in economics. One interpret 9a. utility function (or the negative of loss function), where yi represents the consumption level of the i-th good and ag is the normalized preference (see Varian & Varian (1992)) for the i-th good for any i [d].
Next, we show that functions in G are linear in an infinite-dimensionnd feature space. Let H. be the RKHS with kernel
K K(y1, v2) = exp( (M1, y2))- Let ((y)= = K(y,)) -) be the feature mapping associated with K. We have
Jo
In addition, we have (Io(a) S Ve.
G No REGRET GUARANTEES OF DECISION CALIBRATION
Now we show why decision calibration is useful, as it gives no regret guarantees for downstream decision makers. We consider the no-type-regret guarantee that is also discussed in Zhao et al. (2021). Informally, no type-regret guarantee ensures that a decision maker with loss function & L, who plays the best response policy under their own loss, will incur expected loss greater than
15

---

Published as a conference paper at ICLR 2026
what they would incur by playing the best response strategy for any other loss function e E L. We derive the no-type-regret guarantee results for decision makers under both the optimal decision rule and the smooth optimal decision rule.
Proposition G.I (No Type Regret under Optimal Decision Rule). If the loss estimator Ip is (C, KC. E) decision calibrated, then any decision maker under optimal decision rule has no regret reporting their true loss function, that is
ve, l' L, -. v)] S B(e.))
2e.
Proof. By definition, when the loss estimator f, (C, Kc,, -ecciiion calibrated, we have
E (a y)]
D( [f E)] +
(a.)) Ba [f a, f]] + (x.)) Bo (z) [A u)] 26; where the first and third inequalities follow from the definition of decision calibration, and the second inequality follows from the optimality ke-
Zhao et al. (2021) proved a similar guarantee for multiclass setting and linear loss function class. We generalize the result the general loss estimator setting.
Now we move on to a similar guarantee for decision makers with the smooth optimal decision rule. For this result the error will have another term ) which is related to the hyperparameter / of unverse-temperatie
This is because the smooth best response rule kę might not strictly lead to a better expected loss than ky, therefore we will need to first relate the loss that the decision maker incurs by playing kyg the loss they incurs by playing the strict optimal decision rule ke, which adds another approximation error term. To prove the result, we will need to use a lemma proposed by Roth & Shi (2024), where they studied swap regret different notion of regret) in the adversarial online setting. Roth & Shi (2024) states the lemma in the setting of a utility function u, and we restate the form of the loss function f.
Lemma G.1 (Roth & Shi (2024)). For any loss estimator J, context and loss function E, we have that
E (x) of a, f)] < Ea a, C)] log(IA|) +1
8
Proposition G.2 (No Type Regret under Smooth Optimal Decision Rule). If the loss estimator Jp is (C, Ke, decisson calibrated, then any decision maker under smooth optimal decision rule has no regret reporting their true loss function, that
log(IA)) +
ve, E L, B
B v\1 + 2c
3
Proof.
Ba +e
BB +e
(Bley) {)] +e log(IAA) +
BB 10 0) + log(lAA) +
/
B a, ()) + log(IA[) +
From the perspective of mechanism design, no-type-regre implies that decision makers have incentives misreport their loss function to the loss estimator.
16

---

Published as a conference paper at ICLR 2026
log((A|) +
(B [e(a, y)1 2c
B
where the first and last inequalities follows from the definition of decision calibration, the second inequality follows from Lemma G.I. the third inequality follows from the optimality of kg, and the fourth inequality follows from the expected loss of playing the optimal decision rule will lead to loss no greater than that when playing the smooth optimal decision rule.
H PROOFS IN SECTION 2
Lemma 2.1. Let Cs denote the class of loss functions for which the feature mapping y H gives (dim,H),, X, -Junfform approximations and let Ês {ē: E(a, y) = re(a)- o(y)} denote the associated class of linear functions. For any predictor p X H. any class of decision rule K. and 0, the loss estimator fg is KC,),K,,,2)ddeeciiiiie calibrated, then fp is (Lo. K, c--diiisoon calibrated.
Proof. We have for any E Lo and any K.
((aa) (Ba (a, 8)] B a, e)] ((ay) (x)) [e y) M(a,y). + Be y) 5 (2,
((ay)) [(a, 9) i(a, v)I + EGa.)- 1( fz(z,,
2
where the last inequality holds because s gives (diim()),A,ee)))-unnfnno apprommatin to La and fo is (Lo, K, e/2)-decision calibrated.
I PROOF OF THE LOWER BOUND IN SECTION 3
As our first step in the proof for Theorem 3.1, we derive an equivalent definition of decision calibra- tion eπrо for binary actions.
Lemma I.1. For linear loss function class and |A| = 2, when loss estimator fp is induced by some predictor p. we have
decCECun.Keun (sp D)
sup rER
|E[y - p(x)) 1 ((r,p(=)) > 0)112+ - p(x])()(() ((r,p(x)) < <0]l.2-
Proof. From the definition of decCE D), have
decCEE ()
sup KELLIN.kEKe,,
D I((a, v) Bum.)..-um
( sup
(a), w) Ban
KEKLNN
sup
B. D.
p()))}
NEK
sup
E ((rr)))
()(r(()). p(x))
E.fELLN
+1((re(a1) - re (10
=su (xtp))
PERI,EELNN
+ +1((r, p(x)) -0((7)()))))))))))))))) (()))
sup
|B(y p(z)) 1((r)(())) 0)[1, |B(y p(z)) 1((r,(()) < <0)l,,
rER4
17

---

Published as a conference paper at ICLR 2026
The first 3 equations is from definition and simple algebra, the fourth equation holds from the defi- nition of optiml decision rule, and the last line holds by Cauchy-Sehwarz Schwarz inequality.
Now we give the proof idea for Theorem 3.1. At a high level, our lower bound follows template similar to that used in the lower bound for high-ding sigh-dimensionl full calibration presented in Gopalan al. (2024a), which investigates the sample complexity required to verify full calibration. To prove Theorem 3.1, we start with a set V = {U1, 22, 22) C 3 where v; = ze; is half of the unit vector with the i-th coordinate being 1/2 and all other coordinates take value O. can be shattered by the function class H = {h: h(v) shattered by H if for every function f S - [-1,1] there exists a hypothesis E H. such that Vx E h(x) = f(z).
(r. E Rd). Formally, set S S X is said to be
Lemma 1.2 (Shattering). V can be shattered by the function class H = (M(b(v) = sign((r, (r, e)), ||r|||11 - 1}.
Proof. Let r = (r() ...., (() E ( Va' Ja We have sign((r, }ee))) = sign(r()). Therefore,
h(v) can arbitarily takes value in {-1,1} at each point v, V, which means V can be shattered by H.
Next we use V to construct candidate distributions with large decision calibration error. Lemma 1.3. For any (a."))..,, o(4) E -ata taba,
2 Let he be the function that for any E [d], it holds that (vi) = +e signn-sg Consider a distribution D₂ and predictor p, such that p(x)
distributed uniformly over V and y = ho (p(x)), then it holds that decCEE Keer (fp, Dz) 2 e.
Proof. Consider o, we use 1 Σd 1(0,) 0 to denote the number of positive coordinates
in C. We have
dec (Sp, D)
sup
|B(y - p(x)) 1 ((r,p(x)) > 0)ll
rERd
+ +|[[(y - p(x)) ((r, 0)112
|[B[(y - -(x))) > 0)(l + |[E[[ p(x))) S <0112
1 > sesign(o))
+
Σ 1(0, < Oesigu((,))))
1e
(d l)c
+
d
d
=6
We now construct two nearly indistinguishable distributions over n data points of prediction- outcome pairs (p(x), denoted by D1, D2 E A(() x ))").. The first distribution D2 is such that the predictor p is perfectly decision calibrated, while the second distribution D2 is a mixture over distributions where p incurs a decision calibration error of e. The goal is to show that telling which of D1 and D2 generates the observations requires a number of samples ((vd).
Let A be an algorithm that receives n samples (p(æ1), y1). ((((2)), V2).... (p(xx). yn) E y² and outputs either "accept" or "reject." Define the joint distribution D1 E A(()' x ")") follows: each p(z;)) is drawn independently and uniformly from a finite set V, and each corresponding y; is independently drawn as y4 p(æ;) + cc1, where the sign is chosen uniformly at random. Let p1 denote the probability that algorithm A accepts p on samples follow Dj.
Next, define the joint distribution D2 A(() x )')") as follows: first, uniformly sample pertur- bation vector a E { V va )d, and then sample each p(x;) independently and uniformly from V. For each i, set y; h (,, where h2 is fixed perturbation function defined by
Intuitively, these two distributions are nearly identical. As long as all predictions p(u, ).... ,(x,),,((,,, distinct, the behavior of D, and D3 is almost indistinguishable. The key difference arises when
18

---

Published as a conference paper at ICLR 2026
two data points share the same prediction value p(æ;,) p(z,): in D1, the outcomes yi and y may differ due to independent noise, while in D2, they are always the same because the mapping ho is fixed once is sampled.
We now formalize this intuition in the following statement.
Lemma L4. Let P1 be the probability that A accepts when the data (ob(z)),1)): .... (p(zn), Yal) D1, and Let p2 be the probability that A accepts when the data ((((T1): y1 y1..... (p(Tn) yn)) D2. Here, the randomness comes from both the inherent randomness in A and the data. Then, it holds that [p P2l S /d.
Proof. Without loss of generality we assume that < | For proving the lemma, we intro- duce another joint distribution over the data points, where we first draw p(=1)...-p(x, uniformly without replacement from V, and then for any i, we independently draw y, = p(x,) + ce; with both probabilities 1/2. We use pa to denote the probability of A accept if the data points follow this joint distribution D3.
Also, when we draw all p(a,) independently uniformly with replacement, we use E to denote the event that p(xx,)))) turn out to be distinct. We have
Pr = - 1/V (n 1)/lvl) 2 1 ((1//d)
For both joint distributions, conditioned on the event F,, the probability that A will accept is exactly P3. Then, we have
Pr[E] Ps p1 S Pr E]]
Pa + (1 Pr(E]).
We also have
Pr Ps S p2 - Pr F
+ (1 - Pr(F))
Therefore, we have
IP - p2l < 1 - Pr - Odn²dd)
(8)
Now we are able to prove Theorem 3.1.
Proof of Theorem 3.1. Consider the case of D1, it can be viewed the data points are drawn inde- pendently from distribution D, where p(x:) is drawn uniformly from V, and y = p(x) + co1 with probability both J. Therefore D2 joint distrbution such that the data points are drawn from distribution such that p calibrated (and therefore decision calibrated). Therefore, have P1 2 2/3.
Consider the case of D2, it can be viewed mixture of distributions indexed by o, where for each distribution, the data points are drawn independently from a distribution D.. where p(x) is drawn uniformly from V, and y (p(x)). The distribution mixture where is drawn uniformly. Therefore,
P2 = 2d
1
Σ
Pr[A accepts D.).
(9)
nE(-1,+1)a
As result, from Lemma I.3, have
< p2
Σ
1/3 1/3.
2d
oE{-1,+1Já
By Lemma 1.4, we know n 2 ((v)).
PROOFS IN SECTION
Lemma 4.1. For loss estimator fp derived from the predictor p. is (Lu, Ken -d-deiision cali- brated if and only if
LA
sup E.
E
(2.0))
Σ
(re(a), o(y) - p( (I, SE
(3)
19

---

Published as a conference paper at ICLR 2026
Proof. By reproducing property, for any t,l' Lns we have
B(x.)))DBB onck R (x) [6(a, w)] - Ble.)) (wo (n a, 01|
M
L
f(a, u)k (
((a
fp (
LAI
B(ayyDD
Σ (e(a,)) f,(z,a,))kk,,, (e
AI
BayyaD
Σ ((e(a)) - (()))))))
BlayyvD
Σ (re(a), ((v) - -(o)))
Theorem 4.2 (ERM as Auditing Algorithm). Let D = {(11, y1),... (Nr, Bn)) be the dataset that each data point is drawn ii.d. from D, given any predictor p X H. the ERM algorithm that outputs
"
i aig E
DeccCal (e, y1).
when n 2 Ó(1A 3), ERM algorithu is an e-auditor.
This follows directly from Theorem 4.1, because when n 2 Ö LA n ), we have
Proof.
LAI
sup E.E
(a
- p(()))
B(
(ri(a), p(x)) (2, $1/2.
From the definition of DeeeCll we know that
1 71 Σ LD Zz,
Σ - -(=))
Here, we can remove the absolute value since L is defined as the ball Lx = {e: Va, l(a, H. [| 1l < R1 which is symmetric by construction.
By triangle inequality, when decCE(J,, D) have
LA
E
Σ
- (
-
2
K UNIFORM CONVERGENCE FOR AUDITING DECISION CALIBRATION WITH SMOOTHED OPTIMAL DECISION RULE
Now we introduce the finite sample analysis for decision calibration under smooth optimal decision
rule.
20

---

Published as a conference paper at ICLR 2026
Theorem K.1. Let D (21,81): (Fas yn.) be the dataset that each data point is drawn i.i.d. from D, with probability at least 8 we have that
LAI
sup E
B(G
Σ
(re(a),(()) -(()))
Al
- -((
(re(a), o()) p(x)))(x)))/pp ex, (I,
(10)
0o 32 R3 log R2 Ron) + log(1/6)
Vn
Note that this bound is independent of d, therefore holds for infinite dimension space.
To prove the theorem, recall that we define the function class G. where each element is a function parameterized by the loss function l and f". The function takes data point as input and output the loss they the agent receives when they respond based on and their true loss to E. detail, we have
LAI
(rr((((),, ()(())
(re(a), - (p. (xr,
(re(a), p(x)) B(f)
ΣIAL E B(E ((x)))())
Now we can show that, the difference between g0,e" e (p(x), (bv)) and g , (p(a), p(v)) is small when e as E and (2 l².
Lemma K.1. Consider the vector offmaa softmax(2) 2); Σ i [[A]] and 2 RlAI, then have
8
Pag for each coordinate
||softma((2) - softmax(>')11 /23112 2'112.
Proof. Then by mean value theorem, we know that
softmax(2) - softmax(z') =
Vsoftmax(2 + +(2 - (2))2)))(== z'tdt.
1=0
By taking the E norm, we have
[ssoftmax))) - softmax(22))1 S
Vsoftmax + 2()))(z (z)())(())))) dt)
Let 2t z (z z')l and pt soltmax(zz). We have Vsoftmax(zz) -3(diag(pi)
P.P!) Then we have
IA(2 - 1A(2-2))11
a.5(2z 2//)
A
Σ a || - 21112
1=1
3 (ps -22)2 + 1 Σ 1ł11= =1112
$41
[A]
Bp: (1 - p3) + 1|12 - 2'112
21

---

Published as a conference paper at ICLR 2026
| v23pill 1| -2112
2/3122 - -2'112-
Lemma K.2. Let g(2, w) = E
Σ - شー W; for any 2, w E RIA, 110/ S 4R R2. we
have 19(2, w) - - w()l S 4V R2 2 12 + 1 w
Proof.
19(2, w) - -g(2','' w')l
IA1
Bzz
A
e 0-8
i=1 e B2t !!
e -B2
|A
1=1
|
Al
B2,
|
B2
|A
B2t
=1 e B2g
W//
1=1
==
A
e
+
Σ
==1
|A
e B2,
wi
Σ j=1
E
32g W
IAI
921
|A|
B21
9z
|AI
Wi
w/
+
Σ
w!
3xg W
Bzy
A
Dzg
1=1
A
e
BBg
1=1
A
(11)
We first bound the first term. We have
M
B2
I
Bz
|
e -2,
W = Σ
(wi wi)
e
32,
Wi-
j=
e B2,
i=1
2 j=1 --
|-4
(12)
S $|w
w' ~0 S 1|w - w w'122
Next, we are going to bound the second term. We have
A
-Ba
A
Bzg
e-
w/
w!
j=1 e -g2
j=1 e
|A
B2g
1=1
B2g
Σ/1 e 82
(13)
|A
e 92,
c B
s 4R Rs
Σ 1=
A
B2g
Σラ 385
From Lemma K.1, we have
3zg
BB
w/
w/
<4V28R -2'1l2-
(14)
Bzg
1
|
Therefore, we know
- < 4 232 - =21l2= + +| w' w'll2-
Lemma K.3. There exists a constant C, such that for any x. y we have
ge (p(z), - 9ea, e (p(z), x(w))
[
[A
<0
Σ
(a) (a), + Σ (e)()))r(())d)))))) -p(s)}
a=1
22

---

Published as a conference paper at ICLR 2026
Proof. Because the norm of p(æ) and Φ(y) is bounded by R2, and the norm of loss vector re(a) is bounded by R1. by Lemma K.2, we know
(p(a), 90,0 (p(x),
Σ (re(a)) re000) p(x))2 (15)
A
<4v23R R2
Σ (a) - -ox +
Therefore, we have
(0a.e (p(x), o(y)) a (p(x),)
AAi
LA (r)(a) (a) o(v) p(x)))
4v 4V/23R1 R2
Σ -
[A
IA
64/2 R7 R3
Σ
(r) rgr p())))) + Σ (()())))) p(x)))
(16)
We can set
max (6482 and thus the lemma is proved.
Lemma K.4. Consider G = (gr,e/Va E A, A,, H. |e(a, )1lx S Ri then have
0o [A
log
2
Proof. By Lemma K.3, we know
ge e (p(a.))
ge,
A
LAI Σ
<0'
Σ - (a)
- (ra
o(v:) p(x:);
The high level idea to construct covers for 2|A Hilbert balls, then we can bound the right-hand side. Then, the Cartisan product of these covers would be cover for the function class G.
By Theorem D.3, Let Lg be the smallest 2|AiC 2 cover of Ore(m) == {re(a))re(a) E H. (Ire()))l -
R1}. we have log Lal S O( cA R R²
Therefore, L ILAEA Lo IILEA La would become
c-cover of LH x Lx under the metric L (Px). We have
Σ log TTal 0
1 2
log [T|| 2
BEA
As we know = max max
(6,36322221 R3, 2), we know
log |T| = 0 [41534
Now prove Theorem K.I.
23

---

Published as a conference paper at ICLR 2026
Proof. Recalling aur (p(x). d(y)) Eaai (re(a).
p(z)))k,, (x, a). we know
Al
Σ
(rela), 04)) p(z)) )
( (2a) - p(x)))
(17)
IA
k (2x, a.,,,)2R,, R2
a=1
2Rg Rz.
Therefore, when 2 R2, we have log N L8 (P) -log(1) From Theorem D.4, know that
Rs(9) S 4a + 12 (0) log L8 de 4a + 12
2R1 R2
log NG, (P c)
de.
n
n
Plugging in log NGC (Pn), = 0 LAP we have
| R R
2R; Ra
(9) < 4a + +0
de
Vn
(18)
SA R
4a +0
(log 2R R2
log a.).
3 Vn
Without loss of generality we set
If
2R, R2, we have Rs(9) s
Vn
LAI n
LAI n
4a S 0
If
< 2R R2,
V/
Vn
|A| R
[A] (
(log (log2Rg R2 - log (0(KRR99913)
))
Rs(g) 50
V2
Vn
Vn
|A
R R log( R3 R2n)
Vn
Then by Theorem D.2, we know with at least probability 1 -8/2
1
g(p( (.p(z.).((u)) -ces)--loo(pc))ooo)
sup
gEg
7
log (2/8)
<2EsnD" [G) +
2n
|A13
R3 log R₁ R2n) + log(1/8)
<0
Vn
Similarly we can bound the Rademacher Complexity of function class G (-ge.e l Lu). and have with probability 1 - 8/2
- ((((t)))
sup gEg
E (lop)())l(())))))))))))))))
[
31 R2 (og
R R2n) + log(1/0)
00
vn
24

---

Published as a conference paper at ICLR 2026
Putting them together, have
1 Σ p(((x)); ((n)) B(ss))-lo((ll).
sup geg
|A log Ri Ran) + log
<0
vn
with probability 1 5.
PROOFS OF SECTION 5
Theorem 5.1. Given any initial predictor po and tolerance e, Algorithm terminates in O Ri iterations. Given Ō A.PRR Q( samples, with probability 6, Algorithm 1 outputs
a predictor pr such that Spr is (CH, Ren, d-decision calibrated and E[]ppr(x) - +x()) s []]ppoxx)-ee -(y))
Proof. If the algorithm does not terminate at round f,we have
a
(2) -p()) >c
sup E
Σ
By uniform convergence property we can find &, ly such that
A
Te, (I,)), o(y) - p(() )
Σ
> 3e/4.
(2, ret (a) R,E((((y) (2)l))))/////) (o, -(x)) (x, a)ll. by Cauchy inequality we have
[AI
Σ ra (a) p(z)) )
Te (((())) ((.) 2B B
3e/4.
Again by uniform convergence,
[A
Te (2) a), -p()) )
E
Σ
> c\/2.
E [I)((())
<1v)
E
(
E [Ip((Z)) (())11]
E (p((x)) - ((v) + Σ deakk (I,
2
[B((o()) p(x)) (I, a)ll El((())
pe(x)) (z, a))
E
dea Key (xc a)
25

---

Published as a conference paper at ICLR 2026
2 1Kc E
dia ke (2, a)
2 nK of R
Setting 17 2R3 we have
?
(ilp((a)(((1110 E E[Ipe4(()) di))l z
4R3
Therefore the algorithm will terminate in most 16 n2 iterations because B[llpo(*) (1)) (2R2)² 4R2.
Proposition 5.1. For Algorithm 1, if the input predictor satisfies Po(z) = E/en (I)())(())s). the for any t, we have Pe(x)) ( an()))())))
Proof. For Algorithm 1, the update in round t is P1+1 TB(R)) (P( + 17 we,e, (P)())) where wt, is the patching term. By induction, it suffices to prove that we,e (Pc(x)) can be explicitly represented by the linear combination of o(y). Let S. (11/s v()) be the set of samples used for auditing. Then we have
LAI
d (z. a) pe (x)) a)ll
(e,,:((((x)) = E
Ës. ((o(v) (e a)l
IIEs [(((v)
By induction, have pe(x)) Em az (1) decision rule keę as
Then compute the smooth optimal
ke (x. a) Evese (lm
e 9 "IN (a(1))((a)))))
Ev'ede
e B AMi (1))))(
Then the norm can be computed as
Bs. (()L)) - pr (x)) w))l
1
R1
(o.. - pa(x(a) (2 a)
ntt
Σ
(pv. Kee lee a) (2/gg a) Pui. - -r((k - p((al)))) 1
n
(ala ()) a).
K (K(hh bby) Σ
arg (2/s K K(yggs 261z)
n
(jE(me)
[E(N..
+
(np(sh)aaslaee)) K (Weeg Mts)
[..
Note that the empirical expectation is a linear combination of o(y).
( (x)) (x, a))
26

---

Published as a conference paper at ICLR 2026
Σ (o(v)))
pi( (1)
The sE|me
p(vh)) - Σ
ars (2(a))((1))))
be (atees a)
sE(me)
jE[Na]
ky (atee a)
any (rs(2//s) (2le a)
Mlves).
n4
JEN, [c(m))
Bringing these components together, (o())))) Ufo(ye)) can be computed. For ease of notion, we let {y(+1.4) Ne-1 be the union of two set of samples mentioned above. By induction we know that the linear representation of pe(a)) + e, e (pt (1)) can be computed. Let (xr) + We,ee (pt())) Eie(N (1)1,
know the linear representation of A. by
The last thing to show that after projection BB(R)) the linear representation can still be computed. We have
Rg
(t))
[1)+1())]l 7
The it suffices to show that the norm is computable. We have
[|p+ (x) = (p++1 (x), (z),,
Σ
(1+2,())0(0111))))
E (1+2)(1))(
iE(Ne-1l
[JE[N+41)
M EXTENSION OF ZHAO ET AL. (2021)'s ALGORITHM
In this section we provide extension to Zhao et al. (2021)'s algorithm on decision calibration under smoothed optimal decision rule. Our extension also adopts a "patching"-sry approach, with the patching component derived from optimization perspective, following the intuition in their work. Consider that we find the pair of l,, E in round that violates the decision calibration. If we let the patching have the following form
Pe+ (2) p<(x)) Ukeg( (x),
we can heuristically minimize
|
((((()) pe(x)) (z, al]|* A|Tlrs
L(U) Σ
(19)
where the first term is trying to decrease the violation of decision calibration and the second term is trying to restrict the norm of so that U can be efficiently approximated with samples. By simple calculation we have
IAI
L(U) = Σ
G. (DUTT) Dall + *LUII
a=1
= || DU | AIUIE
The optimum of the objective is U GT (D + AI)- Note that the optimization objective of Zhao et al. (2021) is just the first term of Eq. (19) without the second regularization term. Conse- quently, the optimum becomes U G D that the norm of U can be unbounded because the
27

---

Published as a conference paper at ICLR 2026
Algorithm 2 Finite-Sample
Adaptation of Zhao et al. (2021)
Input: The RKHS kernel K, current predictor po X H. and tolerance e.
I: t=
2: while 36,, Es' such that E E |A]
=== re, (a (x, a), p(y) p(x))) do
3: Compute 1) RIAIXAA| where Dea' = Rike, (2r, a)kee (2)
4: Define G E xxdim((())) where G2 = [[(((y) (c(z))k;((z a)..
5: Set P1+1 x + (P(R))(((()) + (T I) - (TT()))) projects onto Hilbert ball
((R2)
6: end while
(pseudo)inverse of may not have bounded norm. Therefore, their algorithm does not have finite sample guarantee. Our regularized extension to their algorithm Algorithm 2 can fix this problem. In Algorithm 2, we choose
The following theorem says that Algorithm 2 is also a valid algorithm for decision calibration, but has sample complexity bounds ( worse than ours (
Theorem M.1. Given any initial predictor po and tolerance e, Algorithm ends in T iterations. Given Ö [AI'RR samples, with probability - 6, Algorithm 2 out- puts predictor pr such that fpr eddecisinn calibrated and B(llpr(2) <(v) l| s [x)lp((x) l1)
O LARRER
65
Proof. First have
[
< 2222 VAA.
[AI
[10 +
((1++))-1 1)-1 =
ai + 1) s VIA.
E -()) - -(v)) 1
-2E(((()) wwt.k:/wwww.a000kkoo/o/0ooo00000
-
"d (D+ 1)-
(D+1)=((++1)))) - - a ||
GT | (1+ - -| (D+1)
4/214/ à -G 4R2 ARg1AR (0-
1
TTGGG)) 4Rg
4R2/ G- AR (D-
(D (D-
2
=²
20
[
28

---

Published as a conference paper at ICLR 2026
Therefore, the algorithm terminates in O( rounds. By Theorem D.I, each round requires Ó(1/ct) samples to estimate D and G, resulting in an overall sample complexity of Ó(1/c).
Similarly to Proposition 5.1, we apply the patching in Algorithm 2 implicitly.
29


Reviews:
[{"review_id": "5NUnn2nzFe", "reviewer": "Reviewer_Zo8a", "summary": "Prior work on decision calibration requires that predictions are unbiased conditional on events relevant to action selection under a linear loss function. This paper extends the decision calibration framework to a setting where decision makers to have nonlinear loss functions.", "questions": "N/A", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Most prior work in decision calibration, e.g. Zhao et al 2021, Sahoo et al 2021, focuses on linear losses, so this work makes a contribution to the area by considering nonlinear loss functions.\n\n- This work proposes to approximate nonlinear loss functions using a feature mapping $\\phi: \\mathcal{Y} \\rightarrow \\mathcal{H}$, so that a nonlinear loss function $\\ell(y, a)$ can be approximated by a linear loss function $\\ell^{*}(\\phi(y), a)$. It is quite common and natural to express a nonlinear function through a basis expansion.\n\n- The main theoretical contributions include a lower bound for dimension-free decision calibration, a dimension-free sample complexity guarantee of decision calibration under nonlinear losses and quantal response, and improved sample complexity results for decision calibration.", "weaknesses": "- The introduction could be significantly strengthened by making clear why existing approaches for decision calibration fall short for nonlinear loss functions. In addition, it would also be helpful to emphasize the challenge that arises when moving from linear loss functions to nonlinear loss functions. Is decision calibration more difficult to achieve for nonlinear loss functions because we may require unbiasedness of higher-order moments of the outcome? Is this the motivation for embedding outcomes into a feature space?\n\n- In a related vein, the link between nonlinear loss functions and achieving decision calibration for higher-dimensional outcomes could be made much more clear in the introduction. The abstract of the paper emphasizes moving from linear losses, which are commonly studied in decision calibration, to nonlinear loss functions. So, my initial interpretation was that this paper would focus on a loss functions that depend on higher-order moments of the outcome. However, the introduction very quickly jumps from a discussion of linear losses to a discussion of achieving decision calibration for high-dimensional outcome spaces.  \n\n- Since the authors propose to express a nonlinear function as a linear basis expansion, is it necessary to achieve some calibration notion for predictions of the potentially high-dimensional outcome $\\phi(Y)$. I would expect the sample complexity of decision calibration to depend on the dimension of $\\phi(Y)$ as in Zhao et al, 2021, the sample complexity depends on $C$ the number of classes.  It would helpful to clarify what's different/new about this analysis that allows us to sidestep the dependence on the dimension of $\\phi(Y)$.\n\n- It would be useful to clarify in the introduction why the authors consider under the quantal response, and what limitations are in considering the quantal response rather than just the best response rule.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vSqRTrb85f", "reviewer": "Reviewer_zBGQ", "summary": "The paper proposes improved upper and lower bounds on the problem of decision calibration in the batch setting, when faced with potentially nonlinear losses and/or high/infinite dimensional feature spaces. The contribution is roughly threefold. First, a lower bound is provided, which establishes that under the pure best response decision rule (deterministic selection of the best alternative), a poly(m) complexity in the dimension m is required just to audit for the presence/absence of decision calibration. \n\nSecond, in contrast to the first result, an efficient auditing scheme is developed for various loss classes in RKHS that has complexity independent of the ambient dimension. Third, this dimension-free auditing scheme is extended to provide an efficient dimension-free decision calibration algorithm in this setting.", "questions": "My substantive questions in this case are limited to the issues in the Weaknesses section above. In addition to those, I have observed a fair amount of typos and grammar issues, which would be tedious to list here (but suffice it to say, they are prominent even in the abstract) --- so to improve the writing, these need to be fixed.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This is a good paper; the proposed array of results are both insightful, creating previously unknown separations, and employ a variety of techniques that may be useful for follow-up work.\n\nOn the insights side, it is an important message that decision calibration can be done in a dimension free way; equally important, however, is the complementary message that the dimension-dependence can go away for smooth decision rules but not for the canonical nonsmooth one. This draws distant parallels to other, quite distinct, instances of smooth vs. nonsmooth issues in (regular) (multi)calibration, but is very much a decision-focused phenomenon here.\n\nOn the techniques side, here are a couple that I want to point out. First, extending from the Gopalan et al constructions, that applied to full calibration rather than the decision variant, is not fully trivial and required some careful constructions. Second, on the constructive side, constructing the dimension-free calibration algorithm using the auditing algorithm is also not as straightforward as it may seem; among all else, it required “implicit patching”, a simple but useful trick.", "weaknesses": "I believe this is a good-quality and innovative paper, and only have relatively smaller qualms with it. \n\nFirst, the negative result doesn’t quite fully align with algorithmic impossibility of calibration itself (and I’m not convinced how difficult to solve this misalignment problem is in this context). Briefly (and as quickly mentioned in the corresponding section of the paper), the proof by covering shows that auditing for calibration is not possible to do without incurring a dimension-driven dependence. Given that all existing (decision) calibration algorithms depend on auditing of miscalibration, it is thus possible to conclude that the currently studied ubiquitous algorithmic template doesn’t allow for dimension-free calibration. However, there might ostensibly be an off-chance whereby decision calibration is possible to perform dimension-free by eschewing direct auditing. This off-chance possibility thus represents a gap that must be discussed more prominently; this includes a broader perspective — auditing/testing vs calibration tasks have both come up in the literature before e.g. for vanilla calibration, so are there any insights into how fundamental this gap is to bridge?\n\nSecondly, the paper touches upon the following important consideration, which is to my knowledge fairly novel in the literature: That decision calibration can exhibit tractability separations depending on the nature of the decision rule. In this case, the very least that must be done is to align the presentation and the terminology surrounding the decision rules that are studied. In particular, given that (1) the hard best response rule comes up in the 0-temperature limit of quantal response, and (2) the bounds obtained in the upper bound side for quantal response have an explicit dependence on the inverse temperature beta, it would be clean to define and refer to decision rules throughout the paper in terms of that temperature. (Even on the current terminology level, the quantal response mapping is also called other names such as “smooth” etc. so that can be streamlined.) \n\nIn particular, I would consider the story about the influence of the temperature on the hardness of the problem somewhat fully addressed if the upper bounds involving beta were also accompanied by lower bounds in beta (ignoring other parameters besides beta); matching bounds may be a lot to ask for from the technical perspective, so any, even slow, lower-bounding dependence on beta would suffice to drive the above point home.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lOFQHjTLUL", "reviewer": "Reviewer_F8eW", "summary": "This paper studies decision calibration in high-dimensional space and nonlinear loss functions. The main results in the paper include:\n* Lowerbound for deterministic best response: distinguishing decision calibration requires a sample complexity of $\\Omega(\\sqrt{m})$. \n* Dimension-free decision calibration under smooth best response: under the quantal response model, the paper designs an algorithm that audits decision calibration, where the sample complexity is invariant of dimension. \n* dimension-free audition then leads to a dimension-free algorithm for decision calibration under quantal response.", "questions": "See my comment above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper addresses a well-motivated open problem. The main message in the paper is strong: under smooth best responding, decision calibration can be achieved without dependence on dimensionality. The main technical contribution in the paper is the dimension-free audition result. The algorithm design follows from existing work and the existence of the audition algorithm. \n\nThe paper is well organized. The class of functions considered here seem quite general (including nonlinear losses linearizable or uniformly approximable in an RKHS). It would be great if the authors could include more discussions on the class of loss functions admitted by the problem setup and the dependence on norm. It would also help me if there are examples not admitted in the class, and how decision calibration cannot be achieved.", "weaknesses": "The work builds on established techniques, yet delivers useful results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CCz0zgU6bw", "reviewer": "Reviewer_YoMP", "summary": "The paper studies prediction for downstream decision-making via the lens of decision calibration. Decision calibration requires that predictions are calibrated with respect to a decision-making rule, which incurs loss depending on the prescribed action and label. The paper focuses on non-linear losses that admit (possibly infinite-dimensional) linear representations, e.g. in an RKHS. Prior work on decision calibration handle linear losses and losses with finite-dimensional linear representations. \n\nThe main results are:\n- Under best response, verifying decision calibration requires sample complexity polynomial in the dimension of the prediction space. \n- Under smooth best response, there is an auditing algorithm for losses in RKHS with sample complexity independent of the dimension. \n- The paper then gives an algorithm that post-processes an initial predictor to a decision-calibrated predictor--under smooth best response and for losses in RKHS. The sample complexity is independent of the dimension and scales polynomially in the number of actions and 1/epsilon.", "questions": "- Why is smooth best response able to give stronger results intuitively-speaking? I think it would benefit the paper to add some intuitive explanation behind the separation, e.g. why smooth best response “fixes” the hard example of Theorem 3.1. \n- Can the results under smooth best response be extended to any decision rule that is near-optimal and smooth?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- I think this paper makes solid contributions to the study of calibration for decision-making. The proposed algorithm is a fairly significant extension of previous results. The authors also give a lower bound that has implications for existing calibration algorithms. \n- The technical contribution is a uniform convergence argument for decision calibration under smooth best response.\n- Overall the paper is well-written and the relation to previous work is clear.", "weaknesses": "- The idea of uniformly approximating non-linear losses comes from previous work of Gopalan et al (2024b) and Lu et al (2025) in similar contexts. The algorithmic template follows that of Gopalan et al (2022) and Zhao et al (2021) (but it was not previously clear how to handle the infinite-dimensional case).\n- The uniform approximation framework is introduced but not explicitly used; even the examples in Appendix F seem to have exact representations. It would be nice to spell out the end-to-end decision calibration guarantees for losses that can be uniformly approximated and/or the examples given in Appendix F. \n\nMinor things:\n- The term “feature space” is used for both $X$ and $H$; I would suggest changing one. \n- The decision rule $k$ has domain $X$, but the paper is only concerned with decision rules that are functions of the predictions (or loss estimators), right?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)