Measuring Uncertainty Calibration
Authors: Kamil Ciosek
Nicolò Felicioni
Sina Ghiassian
Juan Elenter
Francesco Tonolini
David Gustafsson
Eva Garcia-Martin
Carmen Barcena Gonzalez
Raphaëlle Bertrand-Lalo
Venue: ICLR 2026 Poster (2026)
Keywords: calibration
classification
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We describe principled ways of bounding the calibration error of a classifier.

Abstract: We make two contributions to the problem of estimating the $L_1$ calibration error of a binary classifier from a finite dataset. First, we provide an upper bound for any classifier where the calibration function has bounded variation. Second, we provide a method of modifying any classifier so that its calibration error can be upper bounded efficiently without significantly impacting classifier performance and without any restrictive assumptions. All our results are non-asymptotic and distribution-free. We conclude by providing advice on how to measure calibration error in practice. Our methods yield practical procedures that can be run on real-world datasets with modest overhead.

Published as a conference paper at ICLR 2026
MEASURING UNCERTAINTY CALIBRATION
Kamil Ciosek Nicolò Felicioni
Sina Ghiassian
Juan Elenter Litwin Francesco Tonolini
David Gustafsson
Eva Garcia-Martin Spotify
Carmen Barcena Gonzalez
Raphaëlle Bertrand-Lalo
ABSTRACT
We make two contributions to the problem of estimating the L1 calibration error of binary classifier from a finite dataset. First, we provide an upper bound on the calibration error for any classifier where the calibration function has bounded variation. Second, we provide a method modifying any classifier so that its calibration error can be upper bounded efficiently without significantly impacting classifier performance and without any restrictive assumptions. All our results are non-asymptotic and distribution-free We conclude by providing advice how to measure calibration error practice. Our methods yield practical procedures that can be real-world datasets with modest overhead.
INTRODUCTION
Machine Learning models increasingly used drive decision making in many tasks of practi- cal importance. This process is notoriously susceptible (Cohen & Goldszmidi, (004) to how well model outputs match probabilities of events in the real world, a property known calibration. An important pre-requisite for ensuring good model calibration is the ability to measure it. This paper focuses precisely on this problem.
The most common approach to calibration is to place model outputs into discrete buckets (Zarrozny Eikan 2001, Naeini et al. 2013) Kumar et al., 2019). While this makes the calibration error possible to estimate using elementary tools, it introduces dilemma. If one treats the estimate of the calibration error obtained by bucketing as a proxy for the calibration error of the classifier before the bucketing, the method is notoriously unreliable, producing different answers depending bucketing scheme used (Arrieta-Ibarl Ibarra et al. 2022). On the other hand, one treats the bucketing part of the classifier, classification performance likely to suffer since the bucketing is unknown to the training process
the
Another approach is to frame the problem frequentist hypothesis test with the null hypothesis of zero calibration error (Arrieta-lbarra et al.) 2022 Tygert (023). This type of method statis- tically powerful in detecting deviations from perfect calibration. However, because focuses 'zero-error' null hypothesis, it is primarily designed to decide whether model is (nearly) perfectly colibrated-not quantitatively compare degrees of miscalibration between models Moreover, the proposed cumulative score is not intuitively interpretable and the formal derivation requires the asymptotic regime i.e. large-enough sample size
Contributions We make two contributions to the problem of estimating the L, calibration error of binary classifier from finite data:
1. Certified bounds under bounded variation. We show that if the calibration function has bounded variation, then one can obtain a distribution-Fie non-asymptotic upper bound on calibration error using variant of total variation denoising. This provides the first finite- sample guarantees under such a weak structural assumption.
For example if the classifier neural network, cannot back-propagate through the bucketed outputs.
"One might of course compare test statistics or p-values informally.
Arricta-Iharra Tharra al. 2022) do provide experimental evaluation in the finite-sample regime.

---

Published as a conference paper at ICLR 2026
Lipschitz Smoothness In(x,) nle2)) & 18 m2)
Bounded Variation
Bounded Derivatives
In
In"
bg
A
|
In'l
Fow/short jumps = small (see section
(slandard literature)
[see section
Figure 1: Various assumptions on 17(s) E|Y S = s).
2. Certified bounds via perturbation to enforce smoothness. When no assumption on bounded variation is acceptable, we propose simple perturbation of classifier outputs that guarantees that the calibration function has bounded derivatives. This modification leaves classification performance essentially unchanged, yet enables kernel-based estimator that yields tighter finite-sample bounds on calibration error.
Both approaches are non-asymptotic and fully distribution-free. We complement the theory with experiments synthetic and real datasets, and conclude with actionable advice how measure calibration error in practice.
2
PRELIMINARIES
Calibration Function Consider a function 1) [0, 1] - [0, Denote by p(s) the arbitrary distri- bution of design points (scores). Denote by p(y(s) the Bernoulli distribution with mean ()))). We have (s)) = F Flyl s), and the function v) is called the calibration function.
Datasets Consider an i.dd dataset of tuples {(,, 34)}s ~ p())p(y)s)) The dataset is split into the notations
two index sets generated independently: training T and validation V, where Yr = {y: i E 7). Yv {yr : i E V). ST {& : i E T} and Sy = (8: : E EEVV V). Both these sets generated independently from any data used to train the classifier.
Main Objective
The main objective of this paper is bound the quantity
CE a [ (s)]]
known (Lee et al. 2023) as the L1 expected calibration error, using data from finite (training and validation) datasets. the next section, we describe the proof approach and structural assumptions on 17 that make this possible.
STRUCTURE OF RESULTS
The Need For Assumptions We begin by noting that estimating the quantity [ impossible with- out making structural assumptions on At very minimum, for the expectation in equation to be well-defined, one needs measurability. However, measurability alone is not sufficient to ensure the ability to estimate from finite dataset. In fact,Lee et al. (023) have shown that even continuity (which implies measurability) not sufficient, i.e. that there exist choices of p and continuous such that any estimator of the quantity quantitygiives answer wrong by constant even with infinite data. We therefore need assumptions a different kind. this paper, we focus on two alternatives for what they can be.
we assume that n has bounded variation, which turns out to be enough to bound the calibration error in a theoreti- cally principled way using variant of bucketing (with special process for constructing buckets).
Bounded Variation and Bounded Derivatives Assumptions First, in section 4
We discuss other functionals for measuring calibration and
for picking CE appendix
2

---

Published as a conference paper at ICLR 2026
However, because bounded variation is still relatively weak assumption, it allows for many nearly pathological functions which the bound has to take into account, adversely impacting sample effi- ciency. This motivates to assume has two bounded derivatives. While this assumption ostensibly looks hard to justify, do in fact show that we can always achieve by applying small perturbation to the classifier outputs. We demonstrate in section 7 that this only affects classifier performance in a minimal way in practice. Another possible assumption common in literature is Lipschitz continuity (we compare to Lipschitz bucketing scheme in section 7 All three assumptions are visualized in figure [
look for stronger assumptions. Specifically. in section [5] choose
Lower vs Upper Bounds As side note we remark that, while the techniques we develop work upper bounds
for both upper and lower bounds (with high probability), we focus the presentation since we typically wish to certify that the calibration error is small, not that it is large. We also note that all our results are fully distribution-free i.e. the distribution of scores p(s) can be discrete or continuous or a mixture, without any assumptions.
Main Proof Technique Our proof technique consists in constructing surrogate for 17- We then bound the calibration error as a sum of the calibration error wrt. the surrogate and the error of the surrogate construction process. The construction of the surrogate is different depending on the assumption we are willing to make. Specifically, we use total variation denoising in case of the bounded variation assumption (section 4 and a kernel smoother case of the -erivvivess assumption (section (5).
Concentration In our proof, we also need to quantify concentration of the empirical mean of bounded random variables. We use Bernstein's 's inequality to do that. Because there are several versions literature, we quote the one we used. This version matches the work of Mnih et al. 2008). For sum of i.dd, bounded random variables with mean μ and support on [0. 11, have p S Xn + BB(n, x,), 2 -8,, 5, where X, == E X,, K. = E (X, -.xx),a) Xx) and
2 20 In(3/5) 1n(318)
BB (B, (,
Here, we used the symbol BB to denote the concentration term in the Bemstein bound. We could have equally used Hoeffding incquality here, but Bernstein is slightly sharper.
4 MEASURING CALIBRATION UNDER BOUNDED VARIATION
Bounded Variation To formalize our assumption on 7/. we will need the concept of a Bounded Variation space (DeVore Lorentz 1993). For function f, we can define total variation on the interval / as
TV(J = sup Σ (5(+)1 ((5))))(6s11)
where the supremum taken over the set of all finite sequences 81, 52. contained in the interval 1, We say that the function is of bounded variation, written f BV 1J) when TV(f, [0, 1]) < co. Our theoretical work in this section is based on the assumption that the cal- ibration function 17 satisfies TV [0, 1)) < V for some known constant V.
TV Denoising Under the bounded variation assumption, we want to reconstruct 1) from noisy observations. To do so, it is useful consider the TV denoising estimate ीr.. is obtained by solving the optimization problem
fr arg min
1vr u113 A|Dolll
1E[0. 2
where yr is a vector of labels in the training set and în. is our approximation of on the training set. The matrix D E ((( is defined as:
(Dv): U++1 0i i= 1,2,
(3)
3

---

Published as a conference paper at ICLR 2026
and À 0 is regularization parameter. [Mamen & Van De Geer (1997) the first to have shown results about reconstruction error of similar algorithms, i.e. the difierence between 7/ and
fr. For our purposes, we rely on the fact that, we set = v 8/7 In -(7 in the optimization problem 2 then with probability 1 81 we have
61
1 |/ irll S TVB(
(4)
Here, we denoted by Tr the vector containing the values of 1 on the training set. The term (V1 diminishes if we increase the size of the training set. This result is proven (and a formula for TVB(6, provided) appendix B as corollary [ using proof techniques developed by Hütter & Rigollet 2016). Equation D is useful because it measures how close the reconstruction is to the true 17 on the training set. However, in order to bound the calibration error, we need a similar guarantee the population level, i.c. for scores sampled from p(s). To do this, we first define r for arbitrary scores from its values on the training set
i(s)
(fr).. where i, arg max i E 82 S 8).
We then write bound similar but in expectation
log(2/82)
2 log
E, [In(s) [s)]] S TVB(6)) + (V + +D
(5)
2
T
8g
(TB()2)
where we denoted part of the right-hand side of the bound with the notation (6,, 85), which stands for population transfer bound. See Corollary 2 in Appendix for the proof.
TV Smoothing as Bucketing The function á obtained by TV denoising is piecewise constant. Therefore, legitimate view of the smoothing process is consider it as very special example of a bucketing scheme, where the buckets correspond to the constant pieces of ij.
Bounding the Calibration Error To upper-bound the calibration error, rely simple but powerful idea. First, imagine that the function in the definition of the calibration error ( is known. In that case, we could rely on the Bernstein bound to compute the expectation, using the fact that the absolute value in the definition of the calibration error is bounded in [0. 1]. However, of course in practice 17 not known directly and is observable only via noisy observations. This motivates us to proceed by first obtaining approximation vj to 7) by solving the optimization problem (2) on the training set and then apply Bernstein on the validation set. Note that (2) (and hence ri) computable from the dataset. Intuitively, leads to additional approximation error, which has to be added to the upper bound. Fortunately, the approximation error can be bounded by using equation 4 We now proceed to make this formal.
then the approximation
in place of 17. Of course, this
Proposition 1 (CE Upper Bound under Bounded Variation), Construct the surrogate calibration function i by solving the optimization problem With probability 5, we have
CE <
8: - f(ss)) (isss)lBBB(BII] 8,, of (s o.-R6al)ee)) + TVB(6,) + PTB( 63), Σ REV
where 51 52 83 84 = and d (1x:-e( is the empirical variance of the term |st n((+))
on the validation set.
Proof. We write
- E[[[s-1((3)) < (.[(((s) a|] E+(((s))) 7)5)
(6)
term 1
term II
and bound term I and II separately. We begin by bounding term I. Since the term under expectation
is bounded in [0, 1] and the validation set independent of the training set used to obtain f). use
Bernstein inequality with probability 8, We bound term using equation [ The result follows by
picking the delta terms so that 81 + d2 dg 84 8.

---

Published as a conference paper at ICLR 2026
Proposition 1 is important because it gives handle bounding the calibration error of any classifier with a bounded variation calibration function a form computable from observable quan- tities. Note that the term İ (the total variation of the surrogate) is computable from data (since the TV solution is piecewise constant).
When is Bounded Variation Reasonable? Verifying that a function of bounded variation is impossible to do from finite samples only, even if the samples had not been noisy. However, the result in this section is still useful. This is because, in scenarios of practical relevance, 1) is not a completely arbitrary function but that was obtained from training a classifier. Since the classifier is trying to distinguish positive form negative examples, it not unreasonable to expect that should be monotone increasing. i.e. that higher scores correspond higher chance seeing positive label. It is well known that all monotone functions mapping to [0, 1] have total variation bounded by 1, i.e. we can use V
MEASURING CALIBRATION UNDER BOUNDED DERIVATIVES
In certain scenarios the bounded variation assumption from the previous section is not suitable. This can be for two reasons reasons-either don't 't know the total variation bound V better sample efficiency. In this section, we address this need by providing a method of obtaining guarantees calibration for broad class of classifiers. The main idea is to start with completely arbitrary classifier and modify it in a way which ensures the ability to bound calibration error but does not harm classification performance.
want to achieve
Ensuring Smoothness By Perturbation The modification amounts to perturbing the probability output of the classifier by small amount, specified by the perturbation bandwidth. This can be done either only at inference time or at both inference time and training time, to ensure better per- formance. We experimentally evaluate the effect of the perturbation in section 7 and conclude that there is almost no loss of performance relative to an unmodified classifier for realistic choices of the bandwidth. The calibration function of the perturbed classifier can be written
(>)) = - Morig (Sarig)
(L A:(s Surig) dppSariig Sorig)
k(s Sarig) dpppsspspp (Sp(r))r)))
See Appendix for the derivation of this formula. This expression is a kernel-weighted average of the original calibration function Jonig (, smoothened with the kernel k.
Denote by the amount of the perturbation (the bandwidth). Formally, we define the score output by the perturbed classifier as sample from the probability distribution with the PDF defined by the equation
Kernel Choice
k(s Sarig)
1
sech
Sorig
(8)
Z [SSrigg
where sech is the hyperbolic secant function and the normalizer 2 (Sorig h)) is chosen so that the PDF
integrates to one over [0, 1]. By construction, the perturbed score in the interval [0, 1]. It turns
out that using a perturbation of the form given in equation g has significant benefits over using more conventional choice like the truncated Gaussian. We defer discussion of our motivation for choosing the perturbation to appendix D.2
Bounded Derivatives From Perturbation Crucially, the following Lemma, proved in appendix D shows that the calibration function of the modified classifier has two bounded derivatives, regard- less of the properties of the calibration function before the perturbation.
Lemma 1 (Bounded Derivatives From Perturbation). For any classifier that perturbs its output scores by replacing output Sonig with perturbed output sampled according the PDF in equation funcctooo y is twice differentiable. Moreover its first derivative uniformly bounded 8 the calibration function
by 27 and its second derivative is uniformly bounded by 1 12.
5

---

Published as a conference paper at ICLR 2026
Surrogate of Calibration Function via Nadaraya- Hadaraya-Watson Watson Smoothing Lemma | gives us the derivative bounds that allow us to approximate 7 in principled way, i.c. bound the smoothing error of kernel smoother applied to the dataset. We now define
1' (s()ss;))
1((') = Σ
weld's yii,
wa( = EeT k((8(88))
ET
Then we have:
(9) where gr (s') is fully computable from data and diminishes for 8' in the support of p(s). See Ap- pendix C for proof and the precise formula for gr(')). Unlike the choice of the perturbation kernel k. the choice of the smoothing kernel k' used to construct the surrogate is an implementation de- tail. We use Epanechnikov weights with nearest-neighbor fallback and boundary renormalization, tempered by an exponent = 1.2 before re-normalizing; since only the "weights sum to one" prop- erty matters. One could also explore alternatives to using a kernel smoother. For example, we can see that Lemmal I implies that is Lipschitz with constant 2 and use that to bound the error of bucketing scheme, We do fact compare to this approach as part of our experiments.
Ey, [lñ(s') -n)nn((sss)))) S 9r((').
Bounding The Calibration Error We now use equation 9 to bound the calibration error. Again, we stress that all terms in the bound are possible to estimate from data. Proposition 2 (CE Upper Bound under Bounded Derivatives). Assuming ii is twice differentiable with bounds on the first and second derivative, we have
CE S
(m(x)) sil + LEV
Σ (r((s) +
M
iEV
BB(VI, 81, o -lee. + RBB(V 82, 0² ( (e
with probability 1 (picked so that 81 + 62 8), with the randomness taken over the validation set, conditional on the training set, for constant R that depend on the kernel K.
Proof. We begin by introducing conditioning on the training set. Because the quantity |s - (+)]
doesn't depend on the training set, can write.
E, [|s (s))]] Eg [|s (-))((s)sSSs.. Yrl
Introduce the notation
h(s') = Ey, []A((')) - 7('') = Ey; [| 7(s')
where the last equality holds because
always rename a bound variable. We apply
the triangle inequality to get
IC, [|s (s)) Yrl [ - i(ss) Y7] +E, [M(s)]ST, Yr]
(10) where the last equality is because h(s) doesn't 't depend on Yr. We can now apply the Bernstein inequality twice, once for each term on the right hand side of equation (IO). Note that both terms
E, f()) Yrl + [[(s)
under the expectation are bounded in [0, 1]. Note also that the validation set drawn i.d..
For the first term, invoking Bernstein (with half the probability budget) conditionally on Sr, Yy- This gives us
E, [|s ((s)]]Srr, Yr)
Σ ieV
s.1 + (B (i(s.)
(11)
IV
For the second term in 10P. we proceed analogously as before, this time conditioning on ST and
invoking Lemma 6 In order to apply the Bernstein inequality, we introduce constant R that ensures that 9 E [0 1] for all s'. We get
E,,y, [x) <
Σ
gr(s:)
RBB( 82, 82
(12)
V
TVV
We get the result by plugging terms II]
and
12 into 10 and using the union bound.
For the truncated Fpanechnikov kernel, set R byh+ high where by and by are uniform bounds the first and second derivative of 17.

---

Published as a conference paper at ICLR 2026
Implementation Detail (Cross-Fitting). The theory in the paper is written for fixed split of the data indices into training and validation. In practice, we use K-fold fross-fitting: randomly partition the samples into disjoint folds, and for each fold fit surrogate eta the complement while evaluating only on the validation folds, then we aggregate across folds. This preserves the fixed-split assumption (every validation point is scored by model that did not train it) while reducing variance and making full use of the data
6 RELATED WORK
Bucketing Variants of bucketing were first introduced in meteorology (Murphy & Winkler 1977)
and have been used to approximate the calibration error ever since the ML community started paying attention to calibration (Zadrozny & Hikan 2001 Niculescu- Mizil & Caruana 2005 Naeini al,,
2013 Leathart et al.] [017]] Guo et 2017 Vaicenavicius et al.] 2019) Kumar et al. 2019).
Nixon
ct al. 2019) has criticized vanilla bucketing and proposed alternative binning schemes.
Lipschitz Assumptions Vaicenavicius et al. (2019); Dimitriadis et al. (2023): Futami & Fujisawa (024) used the Lipschitz assumption to get handle variants of the calibration error. However, the assumption was not justified. Our paper is more general in two ways: bounded variation (as in section is far weaker assumption then Lipschitz and our perturbation scheme in section 5 guarantees bounded derivatives (and hence the Lipschitz property) rather than just assuming it.
Zhang al. 2020) assumes Hölder continuity, again without justifying it from first principles.
Kolmogoroff-Smirne and Kuiper Arrieta-Ibarra et al. (2022); Tygert 2023 propose a scheme for measuring calibration based on cumulative sum metrics. By relating these metrics to random walks, possible to derive highly efficient frequentist tests where the null hypothesis represents perfect calibration. Our work is different from these approaches in several ways. First, our measured quantity in equation [ is more interpretable. Second, unlike them, we do not rely on asymptotics of any kind so our result stays theoretically valid for any sample size. Third, our technique can be used to compare two poorly calibrated models with each other while they only support com- parisons against a bascline of perfect calibration. Overall, unlike KS-based metrics, which detect mis-calibration but do not yield interpretable bounds, our approach directly certifies an upper bound on CE.
Impossibility Results Gupta et al. (220)) studied under what conditions calibration guarantees theoretically possible, proving formally that one needs assumptions to get handle on calibration. However, they emphasized binning. On the other hand, our work uses either bounded derivatives via perturbation or a bounded variation assumption, emphasizing reliable, certified measurement of cal- ibration. Another type of impossibility result was provided by Arrieta--bbaat argued that binning requires an infinite number of samples per bin to accomplish both asymptotic consistency and asymptotic power. However, these results were obtained without structural assump- tions on the calibration function 1). In addition, Lee et al. (023) has shown that assuming continuity of 1) not enough, i.e. that there are continuous calibration functions which make calibration error impossible to estimate from finite samples. We circumvent these problems when we introduce our assumptions bounded variation and continuity with bounded derivatives.
et al. (2022), who have
Empirical Studies Dieye et al. (2025) have conducted an empirical study of several calibration metrics and concluded that the log-loss (or the Brier score) are better proxies for measuring calibra- tion than a bucketing-baat based ECE estimate. The methods evaluated by Dieye et al. (2025) were all heuristics (they didn't have non-asymptotic guarantees). Maalej al. (2025) used ECB-type bin- ning in an empirical study of various calibration techniques. Our work is different in that we provide certified upper bounds.
Separation Between Train and Validation Our bounds crucially rely on the separation between the training set (used to learn a surrogate of the calibration function) and the validation set (used to measure the calibration error wrt. the surrogate). On the other hand, Kängsepp al. (2025) interpret
We apply such cross-fitting to all three methods we evaluate.
7

---

Published as a conference paper at ICLR 2026
Trdd
Spam Detection
Cifir
1.0
AT1O0
0.88
AT1ROC
0..5
ATTROC
01.8
2-1
2-1
2.5
2
2.3
2-1
2-1
2:1
2.3
2
2
2-1
2-1
2-
2.
2
2-
potturbation size
postucbation size
posturbation
AUROC (h 0)
AUROC (A = 0)
Figure AUROC under Perturbation
the bin-based ECE as method that performs fitting the test set. While they provide interesting insights on the ECE, unlike our work, they do not provide certified bounds.
7 EXPERIMENTS
Overview of Experiments We perform experiments in two stages. First, we establish that we can afford to perturb classifier outputs by as much as 2-6 for realistic datasets, without significantly impacting AUROC. Second, we use lemma to certify this guarantees bounded derivatives, allowing us to obtain the calibration error up to about 0.02 using about 10" samples. While this may seem like lot of data, we note that estimating the calibration error is an inherently hard problem, which scales poorly with the size of the dataset. In fact, to the best of our knowledge, our estimator is the best currently available approach with certified guarantees for the setting we consider.
Perturbation AUROC In figure 2 we measure the effect of perturbing the output probabilities of a classifier on its classification performance, measured by AUROC. We examine three classifi- cation tasks: IMDB, Spam Detection, where the classifier is fine-tuned version of BERT well as CIFAR where we use a vision transformer. We note that perturbing by h 2-6 costs us almost nothing in terms of AUROC for all three datasets. Note that, obtain figure 2 the neural network loss was modified to account for the fact that we are applying perturbation at inference time. Details of this are explained in appendix F The modification is cheap, meaning that the cost of training the network with the modified loss is virtually the same as using the standard cross-entropy loss. The importance of this experiment lies in the fact that it gives a sound methodology for choosing h (we can choose the largest value that does not cause degradation in AUROC).
Upper Bound Quality vs Sample Size The best way to evaluate an estimator is by comparing to the ground truth, which is unavailable for world datasets. We therefore introduced four synthetic examples of the calibration functions (see heading of figure 3 for definitions). The figure shows the sample efficiency of bounding calibration error, defined as the gap between the probabilistic upper bound and the ground truth of the calibration error. Since we used synthetic datasets for this exper- iment, the ground truth known and we can evaluate the gap exactly. We evaluate four principled methods: our kernel estimator (denoted as NW in the plot), our TV denoising estimator (denoted as TV) and Lipschitz bucketing (denoted as Lip+Bkt in the plot) as well as the ECE heuristic. We observe that all three principled methods are consistent (i.e. the error decreases with increasing dataset size), with NW having the best performance. Interestingly, the ECE heuristic is extremely competitive for the first three choices of synthetic experiments, but fails completely for the fourth, in the sense that the error stays large and does not even decrease with increasing dataset size. This behavior is typical of heuristics they sometimes work well but cannot be counted for reliable estimation. We believe this underscores the importance of certified bounds.
Empirical Rates For Principled Estimators We will now zoom in onto the quantitative behavior of estimators in figure 3 We can see that the log curves are straight lines. We can interpret their slopes as empirical rates. We computed those slopes, obtaining the results shown in Table I We can see that the rates obtained in practice very nearly match the theory. We note that, while
8

---

Published as a conference paper at ICLR 2026
(n
Lit Dkt
NW (1 (.5F))
Lio 0.5)P)
NW (1 2o 264)
Lis+-Bit 33"
NW (1 (111616661 (20)
Lipt-kki (y- 0.00100001111000 sin
(n
TV (e- 037))
DCE (o 9A)")
TV 25 267)
ECE (M as? 2+*)
TV (1 222000)))
BCE (a 0443666 (1
10'
(upper bouzd Eoue CM)
0Pe (upper Iounal Lem C33)
10
10-1
10-3
10
10
doseact s000
dolasct size
Figure 3: Number of Samples Needed to Achieve Gap (Synthetic Data).
Method
Empirical Rate
Theoretical Rate
Assumption bounded derivatives
NW
0.406, -0.213
1/33
TV
0..223. -0.164
-1/4
bounded variation
Lip+Bkt
0.574, -0.346
-1/3
Lipschitz smooth
Table 1: Empirical and theoretical rates for various methods.
NW approach achieves the same rate as Lipschitz bucketing, constants better, meaning produce significantly tighter bounds. Note that TV is still useful in setting where we only want to assume bounded variation.
Real Data Experiments We also wanted to establish how the three bounding techniques work on real data. To do this, we four classification datasets: Amazon Polarity, Civil Comments, Phishing, Yelp Polarity. Since the true calibration error unknown, unlike the earlier figure, we plot the upper bounds on the calibration error directly (see figure 4). It can be seen that NW smoothing again gives the tightest bounds.
Note On Repeats and Statistical Significance We repeated the all experiments on these plots 64 times and report mean performance. Figure doees not contain confidence bars because they are too small be seen. This makes our results statistically significant.
Computational Efficiency All tested algorithms have most log -inear time complexity in prac- tice. For kernel smoothing, our implementation uses a sliding window | giving linear time complex- ity. For TV denoising, we used the ProxTVV library (Barbero & Sra 2011 2018), where the runtime of the 1 denoising variant we use has log-linear complexity. Lipschitz bucketing is linear even with a naive implementation. methods for all dataset sizes up to 10?, generating plot such figure 3
practice, takes about minutes on single VM to run repeats of all
LARGE LANGUAGE MODEL USAGE
Large Language Models (ChatGPT 4, CharGPT and Gemini) were used extensively at all stages in the writing of the paper. Both the theoretical results and the code were verified by the authors. We describe the details of LLM usage in Appendix [
The sliding window method is based the insight that faraway points have near-zero kernel similarity.

---

Published as a conference paper at ICLR 2026
spper bound calltratie ever oper bozad on callbratiie etror tpper boued or collbcottin etror upper bound oc: calleation eroe
Amsoonn Polatity: bounds clttase size (A 2-1)
Arnuzon Polarity: boondds vo datssee size (b 2-1)
1pper calllee Celaaiiionn
10-1
10-2
1M
Civil Comments:: hounds dataset size (b
Civil Commenta:: bounds dataset size
tpper colllcation
10-1
10"1
100
Phishing: bounts dataset size 2-1)
Phishing: bounds dataset size (A 2-7)
spper edilbeation siliiiiiion
10
Yelp Polurity: boundss clotasct size
Polarity: bounds datusrt dioe (1 2-7)
apper millbration
10P
10
10t
NW TV
Lip+BBlt
Figure Upper Bounds vs Dataset Size (Real Data).
PRACTICAL ADVICE
The preferred technique is to apply a small perturbation and use Proposition (works whether or not training aware of the perturbation). perturbations are impossible, assume bounded variation and use Proposition 1 (less sample-efficient. Without either assumption, the problem is intractable practice.
10 CONCLUSIONS
We have proposed two methods for upper bounding the calibration error of a binary classifier and described their tradeoffs. We empirically demonstrated it is possible to certify an upper bound on the calibration
real task of practical importance. We concluded by giving practical advice on how to upper bound calibration error in practice.
11 LIMITATIONS
First, while we focused on binary classifiers, we conjecture that our perturbation technique extends naturally to multiclass calibration (future work). Second, while the sample complexity of our NW method is the best we are aware of, it is still the case that one needs about samples to get certified bound for the L.I-caibbration emror about 10-2
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
We provided full proofs for all our claims. Source code is available at https://gituah.com//ppttff lesearch/calibration.
ETHICS STATEMENT
Our theoretical results make abstract statements about the quality of estimators. For the experiments, we used readily available public datasets. Neither gives rise to ethics concerns.
REFERENCES
Imanol Arrieta-lbarra, Paman Gujral, Jonathan Tannen, Mark Tygert, and Cherie Xu. Metrics of calibration for probabilistic predictions. Journal of Machine Learning Research, 23(351):1-54, 2022.
Álvaro Barbero and Suvrit Sra. Fast newton-type methods for total variation regularization, In Lise Getoor and Tobias Scheffer (eds.), ICML, pp. 313-320. Omnipress, 2011. URL http:
7/dblp.un's uni trier.r... de h///////a conf /ttmcmmmmcmmm//mm html #J Attml##imenezs iimenzsi1
Alvaro Barbero and Suvrit Sra. Modular proximal optimization for multidimensional total-variation
regularization. Journal of Machine Learning Research, 19(56):1-82, 2018. URL http://
jm.r..rg/papper.oo wwt..o//pppprrs111//1o1111
html
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced met- rics for measuring unintended bias with real data for text classification. CoRR, Abss/190300451. 2019.
org/ abs / 9033..33 04561
Ira Cohen and Moises Goldszmidt. Properties and benefits of calibrated classifiers. In European conference on principles of data mining and knowledge discovery, pp. 125-136. Springer, 2004.
CM Da Fonseca and J Petronilho. Explicit inverses of some tridiagonal matrices. Linear Algebra and its Applications, 2001.
Ronald A Vore and George G Lorentz. Constructive approximation, volume 303. Springer Science & Business Media, 1993.
Ndeye Awa Dicye, Giorgio Russolillo, and Ndèye Niang. When standard calibration metries fail in evaluating classifier calibration: A simulation study. In ClaDAG 2025, Naples, Italy, September 2025.
051442455
Timo Dimitriadis, Lutz Dümbgen, Alexander Henzi, Marius Puke, and Johanna Ziegel. Honest calibration assessment for binary outcome predictions. Biometrika, 110(3):663-680, 2023.
Futoshi Futami and Masahiro Fujisawa. Information-theorede generalization analysis for expected calibration error. Advances in Neural Information Processing Systems, 37:84246-8444 2024.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution free binary classification: prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems, 13:3711-3723, 2020.
Jan-Christian Hütter and Philippe Rigollet. Optimal rates for total variation denoising. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), ), 29th Annual Conference on Learning The- ory, volume 49 of Proceedings of Machine Learning Research, pp. 1115-1146, Columbia Univer- sity, New York, New York. USA. 23-26 Jun 2016. PMLR. URL https: htttp:://proceedinggs mlr. press http:////////httteeeeeeee
html
Markus Kängsepp, Kaspar Valk, and Meelis Kull. On the usefulness of the fit-on-test view on evaluating calibration of classifiers. Machine Learning, 114(4):105, 2025.
11

---

Published as a conference paper at ICLR 2026
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. Advances in neural information processing systems, 32, 2019.
Tim Leathart, Eibe Frank, Geoffrey Holmes, and Bernhard Pfahringer. Probability calibration trees.
In Asian conference on machine learning, pp. 145-160. PMLR, 2017.
Donghwan Lee, Xinmeng Huang, Hamed Hassani, and Edgar Dobriban. T-cal: An optimal test for the calibration of predictive models. Journal of Machine Learning Research, 24(335):1-72, 2023. URL http:// wttp:/r.orrpppprs//.2a.
0320 html
Bowen Li. Phishing binary classification. https:/ https://huggingg 2024. Dataset on Hugging Face Hub,
//wggggngfaacceeeccocooo co/ datasets/
aisuko/phishing hta.uk//ppisssssspppaaayyyaaas.s
Aicha Maalej, Ulf Johansson, and Tuwe Lofstrom. Evaluating calibration techniques for reliable predictions. In International Conference on Machine Learning and Soft Computing, pp. 159- 175. Springer, 2025.
Andrew L. Maas, Raymond E. Daly, Peter Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150 150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http:
//www.aclwebt
//www. ac www.wwlwwbbb... http://rrrraanoooooo/11-----0000
Enno Mammen and Sara Van De Geer. Locally adaptive regression splines. The Annals of Statisties, 25(1):387-413, 1997.
Julian John McAuley and Jure Leskovec. From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews. Proceedings of the 22nd international conference on World Wide Web, pp. 897-908, 2013.
Volodymyr Mnih, Csaba Szepesvári, and Jean-Yves Audibert. Empirical bernstein stopping. In Proceedings of the 25th international conference on Machine learning, pp. 672-679, 2008.
Allan H Murphy and Robert L Winkler. Can weather forecasters formulate reliable probability forecasts of precipitation and temperature. National weather digest, 2(2):2-9, 1977.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated proba- bilities using bayesian binning. In Proceedings of the AAAI conference artificial intelligence, volume 29, 2015.
Alexandru Niculescu-Min Mizil and Rich Caruana. Predicting good probabilities with supervised learn- ing. In Proceedings of the 22nd international conference on Machine learning, pp. 625-632, 2005.
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measur- ing calibration in deep learning. In CVPR workshops, volume 2, 2019.
Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill New York, 3rd edition, 1976.
David Schulte, Felix Hamborg, and Alan Akbik. Less is more: Parameter-efficieet selection of in- termediate tasks for transfer learning. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference Empirical Methods in Natural Language Pro- cessing, pp. 1431-94422 Miami, Florida, USA, November 2024. Association for Computational Linguisties. doi: 12..8/65//110024emmlppp/ 2024. emn www.wmnwppmmmmmmmmmmmmmmmaa.mmmm 5297
URL http:::://acaaattoollooo org/
Mark Tygert. Calibration of valuue for calibration and for deviation subpopulation from the full population. Advances in Computational Mathematics, 49(5):70, 2023.
12

---

Published as a conference paper at ICLR 2026
Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön. Evaluating model calibration in classification. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Secooy-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp- 3459 1459-3467. PMLR, 16-18 Apr 2019. URL hat.https:. htth:::://proceednngg ml wtt.mm.......////////. seicenaviciusl9a.fee
Bianca Zadrozny and Charles Elkan. Learning and making decisions when costs and probabilities are both unknown. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 204-213, 2001.
Jize Zhang, Bhavya Kailkhura, and T Yong-Jin Han. Mix-n-match: Ensemble and compositional methods for uncertainty calibration in deep learning. In International conference on machine learning, pp. 11117-11122 PMLR, 2020.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-leve Convolutional Networks for Text Classification. arXiv:1509.01626 [cs], September 2015.
A ALTERNATIVE MEASURES OF CALIBRATION ERROR
Expected Ly norms The Lg calibration erro provides a generalization of the L1 calibration error by measuring deviations between predicted scores and true conditional probabilities using an Ln norm. Formally, it defined as [In))ss) s|']//9, where 7)(s) denotes the calibration function. By varying q, one can adjust the sensitivity to large deviations: higher values of q emphasize larger miscalibration errors, while lower values treat all deviations more uniformly. Among these, the L1 version remains the most interpretable, as it directly quantifies the average absolute discrepancy between predicted probabilities and event frequencies.
Expected KL The expected Kullback-Leibler (KL) divergence, which appears as the cali- bration term in the Murphy decomposition of the cross entropy scoring rules, measures mis- calibration in terms of information loss. It can be viewed (L((Benoull((n())) || Bernoulli(s)). capturing how much the predictive distribution diverges from the true conditional distribution. This quantity is related to the L, calibration error through its nection to total variation distance, since total variation provides a first-order (linear) approximation the KL divergence for small deviations. As with other formulations, the Lj version remains the most interpretable, providing simple and intuitive measure of average miscalibration.
average over scores of
Further Justificaition for LI-CE The L1 calibration error can be justified as a principled measure of calibration through its close connection to the total variation (TV) distance between predictive and true conditional distributions. Specifically, for each score value s, the absolute deviation (n(s) - s equals twice the total variation distance between Bernoulli(n(s) and Bernoulliss). Since total variation admits the dual characterization TV Q2) = sup أ [Eq, [f] Eo.(f]l. it bounds the worst-case difference expectations any bounded decision function f. Consequently, the L, calibration eπгог measures the expected maximal deviation in can arise from using the predictive probabilities & instead of the true conditional probabilities 17()).
quantities that
In this sense, it has direct decision-theoretic interpretation: quantifies how miscalibration distort the expected utility of any bounded decision rule.
B TOTAL VARIATION DENOISING
B. PROBLEM FORMULATION
Given a set of training points 81, $2,..., 8/2[. we introduce the vector notations
{rrk 17(8;). {ūr) = ri(s))-
We use the notation J.g opposed to the more common T.p, hecause denoted probability distribution with the symbol p.
13

---

Published as a conference paper at ICLR 2026
We consider a variant of the classical TV denoising problem where observe binary training data yr E {0, 16,1 1}12) generated according to:
yr, Bernoulli(1r:)) i= 1.2....,
(13)
We can always decompose yr as:
yr 1/ + CT
(14)
where ET E R" is the noise term representing the deviation of our observations from the expected values.
The TV denoising estimate frr is obtained by solving:
îrr arg min Ii
2/7) 11r -11122 \ll Durll
(15)
where E R( -|1]x is the finite difference operator defined as:
(Dir): TIT ;+1 a = 1,2, |7'
(16)
Since the operator D is linear, can be represented as a matrix. We abuse notation slightly, also calling this matrix D. The variable À >> 0 in equation i3 regularization parameter. We will later derive a way to set À optimally as a function of observable quantities.
We note that by assumption, the total variation of the true parameter vector is bounded: ||rrlll S V for some known constant > 0.
B.2 AUXILIARY LEMMAS
We first need establish two useful Lemmas.
Lemma 2. Each row of the matrix D+T has squared 2-norm at most q [T). Here, D+T is the transpose of the Koore-Penross pseudo-inverse of the matrix
Proof. Because D is of full row rank, have D-T first examine the elements of the matrix (DD The matrix DD is tri-diagonal and its inverse
Let us
be computed using the formula derived by Da Fonseca & Petronilho (20I). Using the formula and simplifying gives
{(DDT)"' min(i,.)((T) max(i, (T]
Multiplying by D and again simplifying terms, we get
for j < k
{(D)+ 3k ((DD))
T
for j 2 k
T
The squared-2 norm of row j can be written as:
Σ ((-)))
IT
T
k=
kmj+1
where the last inequality is obtained by simplifying and then considering the worst case j.
Lemma 3. Let noise be defined as in equation (14) Then we simultaneously have
[Te]22 S 41
D elloo S12
with probability 1 where t and ta defined in Lemma
4 The matrix II is defined
Proof. We begin with the bound on |[e]|]. First we use the fact that II
11
to write
[T
Ie|||
-
Σ
||l||
Σ
T
VIT
14

---

Published as a conference paper at ICLR 2026
Now, Ej are centered Bernoulli random variables, hence they Gaussin with parameter 3-
Hence Σ ej is sub-Gaussian with parameter
I
This allows us to write.
T
t = 2 exp {
21
P(
Σ 2 t) - 2 exp
2
1
[2'
Setting the right-hand side to equal 8, we get / have
T7 In 2 87. Hence., with probability 8', we
2
[Tell22 1 In 8
(17)
We now move to bound the term D elloo. Invoking Lemma 2 we know that every row of D+T has squared 2-norm upper bounded by T Also, like before, each element of is sub-Gaussian with parameter 1. Combining these insights, and using the fact that noise terms are independent, the element j of the vector D+Te is sub-Gaussian with parameter
4.
1
12 16"
This allows us to write.
T
t²
8t
st, 2
exp
2
21
[
By the union bound, we have
P(|lD+Tell ella 21 P(max (D+T +)2
21) 2( 1) exp
{
8f2
[T]
Setting the right-hand side to 5", we obtain t v 1 8", we have
In
2(1T)
This means that with probability
8
8"
T
2(
- 1)
DD+ cllcc
In
(18)
8
8"
The result follows by using 17 and (8) bound.
together, setting 8' 8" =8/2 and invoking the union
B.3 PROOF OF MAIN RESULT ON TV DENOISING
Lemma 4. Define ||
11. If we set X tn in the optimizatiio problem then with
probability 8 we have
1
e <
2t + 2t v 27 V + 4t2V
T
T
where 1 / 1 In 1
and
22
4(11-1)
The proof follows the technique proposed by Hütter & Rigollet (016)). explicit.
We make constants
Proof.
Using equation 2b and optimality, we get.
1
IVT -r + Aa| Dirlli S 2/T Ilvr wrll + Dur ll
2n
Using the fact that yr Tyr Ex, we get
1
1
10 mr cr Diz 11 -
||r/l2 11 + + D|rlll
2
2/T)
Expanding the squared term on the left hand side, we get
îr 7r 11
[7 (fr mT) er + 2/T || 12 +
All S 2
ler 12 Dlr
2T
15

---

Published as a conference paper at ICLR 2026
Canceling the term 2/77
||rrl22
21 get
2 |
wr 112 [ (ir - er + A|l Dirlli S X| Dar 1-
Rearranging terms, get
2
S
(irr ( 2irl + D (T]
(19)
We now focus on the term (fr mTr) ET. Denote by II the projection on the null-space of D (the space spanned by the vector of all ones). Noting that D D+ = IT), we write
(fr m E (îr 7r Ie + (frr mT) Ier
(îr mT) D D D
ET + (îr (T) " Iele D
(i mr) || eTlloo Tell>> + 11 ||]|r|
Here, the last inequality follows by using Hölder inequality twice. Invoking Lemma
we get
(ir
mr) Ter <
D(t m1)ll112 + 11( 1221
Plugging back into equation 19 get
2 [
2
Mrr 1rl
D
1T) 11t2 +
(1 - 2\ Dir 2X Drr I [T]
Rearranging terms, we get
2 -
2
T ( mr)ll
D nr) 2\ Dirll 2X|| D Ih
[T]
Using the fact that ( - 11)l11 S | 11a + 1Drrrlll we get
2
[T Ar 1 112 | 10iir mr)lla - i
2NN + D
Setting
10T and canceling terms, we get
6r mrl 2
2 [T'
2
t2
4t2 [
11(r ml)l I
Der + +
Der
D
[T]
|
Using the assumption of bounded total variation, we get D /|1
V, so that
2 [
4 V.
p mr
(1 m/r S
T
T
Denoting e == || ne l12, we have
-2t 4t2 S 0.
This implies
1 + v 412.
Squaring and dividing by (T we get
1
1
<
12 + 21 / 17 + 412V + 17 + 462V
7
T
1
2t + 2t, v 1 + 422V + 462V
T
16

---

Published as a conference paper at ICLR 2026
B.4 MOVING TO THE LI NORM
Using Lemma 4 and the Cauchy-Schwand inequality, we can make the following corollary.
Corollary 1. If we À
to in the optimization problem (2). then with probability 1 we have [T]
1
IT
ir 111 S
26 + 21 / 2 412V + 412V
TVB(6)
where 4
/ 2 go 12
4( 7
and we have denoted the right-hand-side with TVB()).
B.5 BOUNDED VARIATION POPULATION TRANSFER
One limitation of Corollary is that it only holds the training set. We bounded variation to relate this to a population-based expectation. We start by proving the following Lemma.
Lemma 5. Consider a function g : [0, + [0. 1] of bounded variation Vg. Consider a
sample
$1..... 8n sampled from distribution with CDF F and empirical CDF Fas we have the following with probability
1 Σ g(s)) n
2
E.(g(8)]
S VV F FFlloo +
log
2n
Proof. Consider the integral
I gdF ff gdFn
gdF=
[ gdl Fr).
where we introduced the notation
H F Fn. Integrating by parts, obtain
f gdH = Hdg + -(()
where the last two terms vanish because H(1) = 0. This gives
/ ga(FF Fn)) / (F- Fn)dg (())
Taking absolute values, we get
gd([F -P.) Pn) + +1g(0)H((0)
| (F--F)) Fn)dg
Using the fact that g(0) [0, 1], get
/f gd( Fx)) + (H()) 2 1 Fn)dg
By the Hoeffding bound, we have with probability that
H S V 2n log
8
Using the total variation assumption we have,
|f gd( Fw)
< Vg F F,
Combining the last three equaitons, get the desired result.
17

---

Published as a conference paper at ICLR 2026
Note that the term the zero score.
log z/2 in lemma 5 is only needed if F assigns nonzero probability mass to 2n
I
We now combine Lemma 5 with corollary L obtaining bound useful for our problem.
Corollary 2. With probability 1 - 6, where 81 + 82 + d3 =
log(2/02)
Es [In(s) fi())1
((x:) ((s:)+ +V1
log
2/7]
2n
83
KT
STVB(61) by Corollary
ri(s). Apply the DKW theorem to bound the term || Fx al with probability 1 82- Apply the property that Vg V + V by construction (where total variation of r and V/ is the total variation r)).
Proof. Apply Lemma 5 to the function g(s) In(s)
C FINITE DERIVATIVE RESULTS
C.I BOUNDING THE SMOOTHING ERROR UNDER CONTINUITY
Lemma 6 (Smoothing Error). Assume 1j is twice difserentiable with the first and second derivatives uniformly bounded by by and b2 respectively. Consider a fixed design (set of scores 81,..-, ( Denote by k., a nonnegative kernel. Denote by the Nadaraya- Watson smoothed approximation to obtained from dataset of (T) samples, defined as
kin,('))
n(s') = Σ w;(s')8s, w;(ss) Ejer (s)
ET
Then have:
Eyr [l((s') -n(()))(sr) S gr(()))
where
gr (s'))= bi Σ ws'sss - sil + bb Σ
wi((s)(ss' -s)) 1
Σ ws()
21
'ET
iET
iET
Proof. We begin by decomposing the term we want to bound.
n(s') - m7s')= = Σ
wells' (o(d))
(755) +
Σ wo n7s)))
(20)
VE
FT
We will bound the bias and noise term separately. We start with the bias term. Taking the Taylor expansion of around training point st, evaluated at s', we get
ryss) n7(s:) 7/ (s:) s;) + " ( sz)2.
for some (s(s)) Subtracting (7;)) and summing across the training points, we get
Σ (,)(s)((n(s') ns(s)) Σ wn((s'n'(ss)(G st) ((( s:) TET
1 Σ
iET
Bounding, we get
Σ ",,(s)(((s)) ()))))))((8))))))))))))))))))))) Sb Σ w;(s') si b2
Σ
w/ (s'''((s' -2
iET
18

---

Published as a conference paper at ICLR 2026
We now bound the noise term. Applying Jensen's inequality have
Eyr
Σ
(ws - ( ST
Ey,
Σ
(w
(7(ss)
Sr
EE
LET
The term yi (7())) is zero mean and nau-Gaussian with variance most 1/4. Hence we have
Ey,
Σ
ww((s)(ss m(ss))
ST
1
wf(
2
LET
iET
Putting both terms from (20 together, get the result.
D SCORE PERTURBATION
D.1 BOUNDING THE DERIVATIVES OF THE CALIBRATION FUNCTION OF THE MODIFIED CLASSIFIER
We have a dataset of tuples (Sorig, y) where the components are generated as follows.
Sorig ((Sorig)))
y ~ Bernoulli (Morig Samiig(Son)) (Sorig)
Here, p(Song) an arbitrary probability measure for the scores Sorig [0, 1] (it can be discrete, continuous, mixture). The function norig (Sorig) = P(Y 1| Sorig) is the calibration function of the original classifier (before perturbation).
Now, we create new dataset of tuples (Surig: 8, s, where the components are generated by perturbing the original scores:
Sorig p(Sorig)
k(s Surig)
y Bernoulli(naigg (Suri)) Here, for each original score Sorig. k(s Sonig) is probability density function (PDF) on [0, 1], which acts as smoothing kernel. The joint distribution is given by
pl p(aorig 8, 1)
p(Sorig) k(s Sarig Morig (Sorig)
p(s] Ruwe) p(y= || (ecia)
( y = 0) ((
k(s Sorig) (1 Morig (Sorig)
p(s(sres)) p(y=0) sowi))
We are interested in the calibration function of this perturbed classifier, which is the conditional probability p(y = 1|s). To find it, we first compute the marginals:
ply = 1, = f k(s (Soiig (Sorig) dp(sorig)
ply = 0, 0) = 1.¹ k(s) |Sori)) - Morig ( (Sorig) dpp dp((niig)
p(s) = ply = 1) + ply 0,8) f k(s)) (oriy) (Morig (aiig(SSniig (Sarig) + Vori Morig (Sorig) dp( (Sori))
[ k(s sorig) dp(sorig)
This allows us to compute the calibration function the perturbed classifier, which we denote by n(s):
L. Morig (Sorig) ki(s) Socig) dp( Sarig)
n(s) ply 1,
[0, 1].
(21)
p(s)
L. k(s sanig) dp(Song)
This expression is keight-weighted average of the original calibration function Morig (Sorig).
19

---

Published as a conference paper at ICLR 2026
D.1.1 HYPERBOLIC SECANT KERNEL
We use the hyperbolic secant function our kernel. For a fixed bandwidth h 0 and for each Sorig E [0, 1J, we define the sech kernel k(s Sorig):
Z (Soorgg ht) = J. sech
Sorig
ds,
(22)
h
1
s Sorig
k(s Sorig)
sech
(33)
7 (Sorig h)
h
7 (Sorig- h)
First, we find closed form equation for ((Song h) and lower bound of this quantity, which we will use later proofs.
Lemma 7 (Closed form and lower bound for Z (Sarig h)). For any h > O and Sori normalization constant in admits the closed form
[0, 11. the
)) arctan (sinh ( ))}
Sprie
Sorie
Z (Soongg: h)) = arctan sinh
(24)
h
Moreover, ZS 1)) is symmetric about Sorig = 1. strictly maximized at Sorig = 2. and attains its minimum at the endpoints Sorig E 10, In particular,
min (S h) = Z(O, h) = Z(1, h) = arctan sinh (1) h ):)) E[U,1]
(25)
Proof. With the substitution u = (s - Swny)/h (so ds = du), the limits s E [0, 1] become Sorig/ hnn.//,, h, (1 shi] hence
Z (Surig. h) = L/' soch
ds (1-amm)/hh -ong/
Sorig h
soch(u) du.
Using du
d. arctan (sinh u) sech u, we obtain
u= (1-8me)//k
7 (arrg h) = h iestan(sinhun
-==-Bot//
h
arctan
sinh h
Sorig
)) arctan sinh Sorig ))):
which is (24) (we used the oddness of sinh and arctan).
Now, we will find a lower bound for Z. First, differentiate
24 with respect to Sorig:
i ((oorig h)) 1o (-2 sech
Sorig + sech( Sorig = sech( Sorig
Sorig
sech
S
h
h
Since + sech strictly decreasing on [0, oo), we have axee Z (Sorig h) > for Sorig J. Orm (SSuigg h) at Sorig = 2' and dr... (S h)
for Sorig 1. Hence is strictly increasing on [0, 3 and strictly decreasing on 1 1], so its maximum is at Sorig = and its minimum
attained the endpoints Sorig E {0, 1}. Evaluating (44 Sorig
0 or Sodig yields
h )
Z h) = Z(1, h) = h arctan (sin
which is strictly positive for every h 0, proving the uniform lower bound (25).
Now, we show that k(s Sonig) defined in Eq. 23 is a valid probability density function over [0, the following lemma.
Lemma 8. For any given Sorig E [0, 1] and h 0, the function k(s (ooii) defined in Eq. 23 is valid probability density function over [0, 1].
Proof. We must verify two conditions: non-negativity and that the integral over [0, 1] is unity.
20

---

Published as a conference paper at ICLR 2026
(1) Non-negativity. Recall that for any E R, sech(t) (0, 1] is continuous and strictly positive.
Therefore the map - sech (s Sorig) /h) is continuous and strictly positive on [0, 1]. Regarding the normalization constant, we showed in lemma 7 that Z (Sorig, h) > O. Since the numerator in k(s Surig) and the denominator Z( (Sorig h) are both positive, have
[ h)) sech Sorig
1
k(s Sorig)
for all [0. 1].
(2) Unit integral. Using the definition Z (Sorig: 1t)
So k(s (erig) ds Z (Sorig: h:)
1
// sech
Sorig
Z (Soorgg: h2) Z (sorigg h))
ds
1.
Since ki(. Sarig) 2 on [0, 1] and integrates to 1, it a valid probability density function on [0, 1].
Substituting this specific kernel into our general formula gives the explicit sech- rech-perturbed cal- ibration:
L
8 Sorig
flori (Sorig)
sech
dp(Soriz)
Z( h))
n15)
[0,
(26)
Z(Sorig: sech s Sorig
dpl dp(Socig)
h
D.1.2 A UNIFORM BOUND FOR THE FIRST DERIVATIVE
To analyze the smoothness of r7(s), compute its first derivative. Let's define the numerator and denominator of (26) as separate functions:
((s) = S( Morig (Sorig)
sech
s Sorig h
dp( (p((Sr)))s
Z ((Brrig; hi)
D(s) J (Sorngg h) so that 17(5) (ss)D((s). To ensure 17(8) is well-defined, we must show D(s) + O. We show this in the following lemma.
sech
Sorig h
dpí App(Srrg))
Lemma 9 (Positivity of the denominator). For the sech kernel, the denominator D(s) is strictly positive for all 8 E [0, 1] and any probability measure p on [0, 1).
Proof. Fix [0, 1] and h For every Sorig E
[0, we have sech((s Sorig//h) 0 and
Z ((Sorgg h) > 0 (lemma hence
[Sarig) = Z (Surig h) sech Sarig
0 for all Sarig-
Therefore (ss) = Jp.11 (Song) dp(Surig) > O, since the integral of a strictly positive function with respect to probability measure is strictly positive.
Here, provide the derivative of the sech kernel.
Lemma 10 (Derivative of the sech kernel.. For every Sorig E [0, 1], the partial derivative of Bong
sech
with respect is
18- Sorig h
1 h
Sorig
8 Sorig
sech
sech
tanh
for [0, (27)
Ös
=
h
h
21

---

Published as a conference paper at ICLR 2026
Proof. Let u Surig / Since sech 1/ cosh and (cosh u)' sinh
sinh u
sech v
cosh 2 sech u tanh u.
du
By the chain rule with 0 1/h,
Sorig h
8 Sorig
* Sorig
sech
sech
tanh
Os
h
h
which proves (7 for all & [0, 1].
To compute the derivatives of (s)) and Ds)), we need to differentiate under the integral sign. The following lemma provides the justification.
Lemma 11 (Differentiation under the integral sign). The derivatives of ((s) and D(s) can be computed as:
(')s) S Morig (Sorig) Z (s h) Ōs
d sech
Sorig
dp(Soris):
(28)
h
D'(s) Jo.1] Z (8orig h) Is
sech
Sorie
dp(sorie).
(29)
Proof. Let start by focusing N(s). First, need find Ns)). Let's represent N(s) as (s)) Soo11 [Sorig (dp((Sorig) where
s Sorig
f( Sorig s) = fooig (Sorig)
((Sorig: sech
h
Now recall by lemma T0 (using the oddness of tanh),
8 sech
8 Sorig
Sorig
1
8 Sorig
Sorig h for [0, 1].
sech
tanh
h Therefore, we notice that for every s we have
Os
h
i (Sorig s)
1 sech
Sorie /
Sorig
Mooig (Sorig) Z (Sorig.
tanh
Os
h)) T (
/
hZ h)
Recall that Z(Sorig: h) is strictly positive and lower bounded ((Soiig h) 2 h arctan (sinh( from lemma 7 Because of this and the fact that h > 0, we have sup E[0.1 1/h7 h) < cc. Hence g is bounded, so we can apply the dominated convergence theorem (Theorem 11.32 in (Rudin) 1976h), and we may pass the derivative through the integral. An analogous reasoning easily applies to ((s) too.
By the quotient rule, the derivative of 17(s) is:
r/ N' ((s) D(s)²
(30)
Alternative Representation via Covariance. tation. Let's define new probability measure (dSarig) [0, 1] that depends on This measure re-weights the original measure p( Sorig) based on the kernel:
The derivative has an elegant alternative represen-
Z( sech Burte
dp( (p(SSrig).
(31)
D(s)
Note that f W. (dSorg)) D(o) So
1 sech (e
Auds dp( (Sori)
D(e)
D((e)
Now, we use this alternative representation to prove that the derivative 17(s) can be expressed as covariance under w, in the following proposition.
22

---

Published as a conference paper at ICLR 2026
Lemma 12. The derivative of the perturbed calibration function be expressed covariance under the measure Wg (g(dsooo (dSonig):
Morie (Tori(()); (S), tanh (
(S - ))
r/ Cou
[0, 1].
h
Proof. Starting from (30 and writing T(u) tanh (h lemma
together with lemma
10 gives
(s)
MJorig (Surig) (S h) Us
i sech
Sarig
dp( (Sorig)
D(s) D(s) (0.1)
h Ew, Mooig (S)
and
()(s) 1
0 sech Sorie dp(
1 I.,. [T(S)]
D(s) D(s) [0.1]
/ (6 h) 0s
Since n)ss)
N(a)
Ew, Monin (S)), the quotient rule 30 yields
D(s)
(s) (s))) N(s) D'(s)
((s) D(s) D(s)
h Ew, Morig (S)T(S)] + h
E.,, Monig (S) E (T())
h (Eu,, Monig (S) ((S) Ew, Mong Ew (T())
Covsww, Morig (orig(S), (S), tanh s 5 (-5) h ))
h
Because tanh is odd, this is equivalently
Covs-in (Tori((), tanh S-
v/ n'(8)
Using this alternative representation covariance, we provide uniform bound for the first deriva- tive in the following corollary.
Corollary (Uniform Lipschitz bound). For the sech kernel and any bandwidth > O. the per- turbed calibration function 1j is Lipschitz continuous with a constant independent of p and
Lanh(1/h)
sup In)(s)) =E|o.1]
2h
Proof. By lemma 12 ns(s)
Cov Torig (S), r) with T tanh S-z
By Cauchy-
Schwarz, we know that
[Cov(X, Y)I S V(X))(())
where with V(-) indicate the variance of a random variable.
Also, Popoviciu's inequality says that, e [a, 6). then we have a bound for its variance V(Z):
(b ab=
V(Z)
Since Morig (S) E [0, 1] and T E |- (anbh1//), (an)(1/h)), Cauchy-Schwarz plus Popoviciu's
inequality gives
(2 tanh(1/h))*
tanh (1/h2(1/h)
tanh(1/h)
Cov (S),T) < / 4 h
2h
Noticing that tanh(1// (1/h) yields the claim.
23

---

Published as a conference paper at ICLR 2026
D.1.3 SECOND DERIVATIVE AND UNIFORM BOUND
Let us focus now on bounding the second derivative. First, we will find the second derivative of the kernel in the next lemma.
Lemma 13 (Second derivative of the kernel). For every Soria E [0, 1] and > O,
0 0sa
sech
Sorie
1 (-
soch
Sorie
)
2 tanh" 2 Sorig 1).
[0, 1].
h
h
Proof.
Let u
Sorig) //h Using d sech du
sech tanh u and d du tanh sech u,
d²
d
sech u (sech u tanh u) = sech u tanh? a - sech u sech = sech a (2 tanh u 1).
du
du
Chain rule gives the claim.
Now, we justify differentiation under the integral sign for second-order derivatives. Lemma 14 (Diffcrentiation under the integral sign (second order)). For fixed h > 0 and all E
[0, 1].
(s) = -f Morig (Sori))))) Z (Sorig h)
Ø2
sech
8 Sorig
dd((srig):
Os?
h
(*)))= -Yoa (Sonigg h)
2²
sech
8
Sorig
dp(Soris)-
Os2
Proof. Similarly to the proof of lemma 11 we want to apply the dominated convergence theorem.
By lemma 13 the integrands are bounded in absolute value by ^² A²2((eig.h)) Also, we know from
lemma 7 that minggur (Sorig h) h arctan > 0. Thus (Z an integrable dominator, so the dominated convergence theorem applies (theorem 11.32 from (Rudin 1976 allowing differentiation under the integral.
Similarly what shown for the first derivative, show that the second derivative be repre- sented as a covariance under w, in the following lemma.
Lemma 15 (Second derivative in covariance form). Ler T(S) tanh( (سكر) and expecta-
tion/covariance under S ~ Wss where w. is defined as in Eq. 37 We have that:
1 1/2 (Cow (Norig 2T(S)2 - E.,, [(S)) Cov (Tong (S), T(S)))
(*))
Proof. First, notice that, since (ss) 0 (lemma 9p. all ratios are well-defined. By lemma 14 and
lemma 13 using that T(S)2 tanh 2 S-euis tanh 2 Buil SS
(s)
1 Ew, Monig (2T(S)² -1)]
(") 1 h
Ew (T(S)2 1].
D(s)
A2
D(s)
From lemma II and lemma 10
('(s)
D'(s)
N(s)
En (S)
Ew][T(S)],
(](s)
Em,, [Mrrgg (5))
D(s)
D(s)
D(s)
We now use the quotient rule for the second derivative:
n N"D ND" (N'D
ND
N"
D"
- -2(2"
D' Dz
D
D3
D
- D
n D
24

---

Published as a conference paper at ICLR 2026
Substituting the four identities above yields
1
(s)
h Ew, (S)(((()) -1) Ew, Morig (S) Ew, (2T(5)² (((5))-11) -11)
Lu. Morig (S)I(S)]
Lw, Morig (S)] Ew, [T(S)) Eus [T(S)).
h22
Recognizing covariances,
E[n(2r(5))-1) [/ooi | [|2T Cov (8), 2T -1), Morig (S) [[Moig (S) E[T(S)) = Cov T(S)).
we obtain
1( (Cov.,, (Norig (S), (S) 1) - Ew, (T()] Cov (Norig (S), T(S))).
(s) 12
Corollary 4 (Uniform second-derivane bound). For the sech kernel and any bandwidth h >> 0,
tanh t1/h2(1/h)
3
sup [n)(s) s
=E(0.1]
h2
2 h2
Proof. Let == lanh(1/h). Then T(S) = tanh [س=
E [T, Hence, by Popoviciu's in-
equality,
Vm, (T(S)) < (2 = 2T(S)² [-1, 27
Vm, (2T(5)² (2
4
Since Monig (S) [0, 1], (Morig (8)) < 1/4. Using Cauchy Schhaa,
(Cov(1, 2T 1) I ((n) V(2T2 $ 7², Cov(n, T)I V Vin) and [E[T]] < r. Therefore, lemma 15 gives
[n)())) v 12
(2 -2 + 27 2
72
3
=
2 h22
2 12
D.2 WHY NOT A TRUNCATED GAUSSIAN?
Another plausible choice for the kernel would have been the (truncated) Gaussian. Let x(t) Le -1/2 and ((1) f Φ(u) du be the standard normal pdf and edf. Fix bandwidth 0. V2x
For each Sorig E [0, 1] define the truncated Gaussian density on [0, 1] centered at Sorigs
Sorig h
Sorig
7 (Sorigg h)) o
E (0, 1),
(32)
k(s] Sorig)
Sorig
(33)
h Z (Sorig h)
However, in this paper decided not to use such kernel because of the rate of its derivative. In particular, we have that:
Sorig
1
k(s Sorig) =
k(s Sorig) =
0s
42
By following similar reasoning to the one done for the sech kernel (using the dominated conver- gence theorem, representing the derivative of r as a covariance, and bounding the covariance), we would have got a bound in the order of O (xt² for the first derivative, which is worse than the one we obtained for the sech kernel (O (+)). For this theoretical reason, we opted for the more suitable sech kernel.
25

---

Published as a conference paper at ICLR 2026
E IMPLEMENTATION DETAILS
Plug-in bandwidth. We pick h (the bandwidth of k') by minimizing one-dimensional proxy built from the d'-dependent terms in the smoothing-error bound (Lemma 6): the bias terms are EieT w)(s') sy and b/8 Eier w;(s') -;)) and the stochastic term is 2 Viveier w,)s) Approximating these sums by their continuous Epanechnikov-kerne moments for locally uniform score density (ignoring boundary effects), with K (u) [ - (²)1((()) S 1] and u -s'- 8)/k' [u]K[ (u) du ' and Σ, ws(s' s;)² = h2a (()) = 11²,,
yields Σ, w;|s' - s;l = h' [||
hence [ bj and b = To b2 in the proxy
f(h) = + + VW
For the stochastic term we use the standard approximation v E w v VI]K (with
|| 2 K())² du 3/5 for Epanechnikov) and take a mildly conservative constant in imple- Setring fh = 0 gives a + 2bh c 33/2 0; multiplying
mentation, giving c
1.15 /
by h/2/2 and substituting t bandwidth as N' f2. We solve by few Newton steps and clip to [10-4, 1/4). This choice is an implementation detail; the theory only requires convex weights summing to one.
Vh' yields the quintic 26 + at j 0, and we recover the
Validation subsampling For speed we evaluate the held-out quantities a uniformly sampled subset V/ S VE per fold, with size min 11000, max 0.05 Each validation point is still scored by model trained without it, so the conditional independence and i..d. assumptions required by the empirical AmpiricallBernstein Bernstein step remain valid; subsampling only increases variance (slightly loosening the bound) and does not alter d-allocation or correctness.
Shift aggregation in bucketing. Here, "bucketing" means uniform bins in score space: for given bucket count B we use an (approximately) equal-width grid over [0, 1] with bin width so 1/B, and the "shift" moves the internal bin boundaries by small fraction of one bin width (while keeping the endpoints at O and 1). This is not quantile/cqual-con count binning. We then evaluate the Lipschitz+hucketing bound for every candidate partition defined by a bucket count B and fractional shift E (O...., R-1] }} (offset r B); using per-candidate confidence level 8/BRR), we take the minimum bound over all (B,r) r). By union bound, this aggregate is valid at overall level
F IMPLEMENTATION OF THE PERTURBATION
One advantage of our perturbation method is that, unlike bucketing, it is compatible with training by back-prop. This means we can perturb during classifier training, increasing resilience to perturbation test time. To do that we change the standard cross entropy loss
L
Σ E log $1,; + (1 E.) so.i
+ Lm
(34)
N
Where yi are the ground-truth binary labels, E log $1, and EE log s0,; are the expectation of the two log perturbed probabilities, computed using Gauss Legendre quadrature in practice.
The loss I.m. directly compares the logits of pairs of samples across classes, ensuring class separa- tion. Specifically,, for each example in a batch, we first consider the logit difference
1 io-
2
where 1 and in denote the logits for the positive and negative classes, respectively. We now restrict attention to near pairs j). defined by the condition Is s < 2h i.e. where the probabilities are close. For each such pair, the margin gap is given by
Pij
26

---

Published as a conference paper at ICLR 2026
The loss penalizes cases where this margin is smaller than the target 2h, using smooth softplus penalty. Formally, the loss is defined as
Lm
1
Σ (i.))N
log(1 + exp(2h- 9is))
|c|
where C' the set of near positive-negative pairs. This formulation encourages the logit difference of positive samples relative to negatives to be at least 2h, thereby pushing the classifier towards maintaining larger decision margin.
G DATASETS
We perform perturbation experiments on three binary classification tasks:
A text data set of movie reviews with associated binary labels for sentiment (pos- itive and negative) (Maas al.) 2011). For this task we fined-tuned pre-trained BERT back-bone with a sequence classification head. We used 1, 0,000 training examples, 250 validation examples and 500 test examples to compute reported metrics.
IMDb:
Spam Detection: text dataset of emails labeled either 'spam' or 'not-spam' [Schulte et al. 2024). As for the IMDb data set, we fined-tuned pre-trained BERT back-bone with a sequence classification head, using 000 training examples, 250 validation examples and 500 test examples.
An image data containing 10 distinct classes: airplane, automobile, bird, cat, deer, dog, frog, horse, ship and truck (Krizhevsky) 2009). We make a binary task on this dataset by grouping means of transport (airplane, automobile, ship, truck) and animals (bird, cat, deer, dog, frog, horse). We fine-tune a pre-trained visual transformer (ViT) with classification head. We use 2500 training examples, 250 validation examples and 500 test examples.
CIFAR-10:
Amazon Polarity: A large-scale text dataset of Amazon product reviews labeled with binary sentiment (positive and negative) (McAuley Leskovec, 2013).
dataset of websites' URLs with binary phishing and not- labels (Li 2024). We fine-tuned BERT-based classifier model with 10000 training examples and 250 validation examples. We then use 500000 examples as test.
Phishing:
Civil Comments: A large data set text comments from an archive of the Civil Comments platform; a commenting plugin for independent news sites (Borkan et al. 2019). In the original set, the comments have a series of scores assigned to them, delving into different aspects of harmfulness and toxicity. We make a binary data based on the parent toxicity score; if this score is greater than O. the label is (toxicity present) and 0 otherwise. As for the phishing data set, we use 10, 000 training examples and 250 validation examples to fine-tune a BERT-based text classifier. We use on 3.8M as test set.
Yelp Polarity: A data set of Yelp reviews, where the star ratings have been binarised (2 3 stars is considered as positive) (Zhang et al.) (2015). We fine-tuned BERT-based classifier model with 10000 training examples and 250 validation examples. We then use 560000 examples as test.
H DETAILS ON THE APPROXIMATION OF THE CALIBRATION FUNCTION
Figure shows the reconstruction of the true calibration function 77 (black) obtained using the NW (blue) and TV (red) techniques, for various sizes of the dataset. Note that increasing the dataset size increases reconstruction fidelity. Also note that the TV denoiser is regularized towards a con- stant function, meaning it achieves limited fidelity near the boundary regions and the bottom of the parabola
Note that the effect diminishes with increased dataset size, as can be expected given the estimator is con- sistent.
27

---

Published as a conference paper at ICLR 2026
Rotorating can caloostion fracticn five. 1DC06 simple
Kettnating the caltorie tructio frows 100R0 exmple
Eletraating the caliiration frnetine fries 1000000 samplie
Figure 5: Reconstruction of the calibration error for various dataset sizes.
I
LLM USAGE
In accordance with the ICLR LLM usage policy, disclose that large language models (LLMs) were used as tools during this project. First, LLMs were employed to draft concise code prototypes from mathematical descriptions (e.g.. turning specification of the bounds into runnable Python). All such code was subsequently scrutinized by the authors; the final implementations and exper- imental results are the product of human verification. Second, LLMs were used in an iterative ideation loop for conceptualizing proofs. The final version of formal statements, proofs, as well as the entirety of the paper's 's exposition were written by humans. Importantly, the paper's central idea-that injecting noise yields smooth calibration function enabling tighter bounds-was con- ceived by human author; LLMs did not originate this insight. LLMs were also used polish the writing and as tools to find relevant related work.
28


Reviews:
[{"review_id": "BvBJTEhLHx", "reviewer": "Reviewer_6rA7", "summary": "The paper proposes two variants of upper-bounded calibration error evaluation methods: bounded variation and bounded derivatives. \nTheir method of bounded derivatives achieves the tightest bound compared to the baseline.", "questions": "1) What are the exact definitions of TVB(delta') in equation (4) and B(delta) in equation (5)?\n\n2) Why was Lipschitz bucketing used in the experiments as the only earlier method to compare with?\n\t* Are there any other methods for comparison, or is Lip+Bkt the only or the best bounded method? \n\t* In row 420, the phrase \"our proposed\" goes with NW but not with TV denoising. This is slightly confusing. I thought TV denoising was also first used in the context of calibration in this paper. Can the TV denoising method be also stated as \"our proposed\"?\n\n3) How do classical calibration evaluation methods such as ECE perform in relation to the proposed methods? It is understandable that ECE does not provide such useful upper bounds, but a comparison would help to understand better the shortcomings of ECE.\n\n4) One usecase of measuring calibration is when comparing different calibration methods and deciding which method works best, by giving the smallest calibration errors. Could the proposed methods be used to rank calibration methods? Would calculating the lower bound in addition to the upper bound be helpful with ranking which calibration method is better?\n\n5) Why is Lip+Bkt not given as an option in practical advice, as it has tighter bounds than TV?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* The paper introduced novel ways to calculate bounds for calibration error. The authors explained these bounds in detail and provided proofs. The explanations in the main part of the paper were very well written, providing most of the necessary intuitions and insights to be able to follow the paper.\n* The related work is well-connected to this work.\n* The experiments complement the paper and showcase that their method is giving the best results.", "weaknesses": "* The paper would have benefitted from illustrations about the difference of $\\eta$ and $\\hat{\\eta}$ for TV denoising and for kernel smoothing. Such illustrations could be done for some moderately non-monotonic function, e.g. with total variation above 1 but below 2. While the descriptions were all understandable for me eventually, I think most readers would benefit from such illustrative figures. There was some space remaining for this (if I understand correctly that LLM usage, reproducibility statement, and ethics statement can be outside the 9-page-limit).\n\n* Some of the notation was not described in equations (4) and (5). In particular, TVB(delta') in Eq.(4) and B(delta) in Eq.(5) have not been explicitly defined. I did not find the explicit definitions in the Appendix either. However, conceptually it is understandable what these terms mean.\n\n* It would also be nice to see experiments about how classical calibration evaluation methods such as ECE perform in relation to the proposed methods. It is understandable that ECE does not provide such useful upper bounds, but a comparison would help to understand better the shortcomings of ECE.\n\n* It was not clearly justified why Lipschitz bucketing was used in the experiments as the only earlier method to compare with. \n\n* Minor issue: at the end of section 3, in the paragraph about Concentration, the notation starts with $\\hat{\\sigma}^2_n$ but then switches to $\\hat{\\sigma}^2_{X_i}$. The latter is confusing, because it does not depend only on a particular $X_i$, but all $X_1,\\dots,X_n$. Hence, I suggest staying with $\\hat{\\sigma}^2_n$.\n\n* The section on related work seems to be a bit out-of-date, with one reference in 2024, but the rest are older. Several works on evaluating classifier calibration published in 2025 have been omitted:\n\nDieye et al (2025). When standard calibration metrics fail in evaluating classifier calibration: A simulation study. In ClaDAG 2025.\n\nKängsepp et al (2025). On the usefulness of the fit-on-test view on evaluating calibration of classifiers. Machine Learning, 114(4), p.105.\n\nMaalej et al (2025). Evaluating Calibration Techniques for Reliable Predictions. In International Conference on Machine Learning and Soft Computing (pp. 159-175)", "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": "oo6dUUz4qT", "reviewer": "Reviewer_UCZs", "summary": "Paper introduces two new approaches for estimating binary classifier output calibration and especially upper bounds for calibration error (CE). These are  derived under bounded variation (with total variation denoising), and perturbation of classifier outputs (with kernel density estimator). Empirical evaluation shows the performance under perturbations (real data), and comparison of proposed bounds against Lipschitz bucketing on gap between the upper bound and true CE (synthetic data) and upper bound tightness (real data) with promising results.", "questions": "- Why upper bounds on real data (Figure 3) is showed only for Amazon polarity set and not for other datasets?\n- Would it be possible to show the performance also against other baselines mentioned in the related works? and with other performance metrics related to calibration accuracy?\n- What is the computational complexity / efficiency of the proposed approaches?\n- Are the results statistically significant? \n\nOther minor comments:\n- expectaiton -> expectation (page 3)\n- Table X (after Figure 3) does not have caption is not referred in the text at all.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed methodologies are generally sound. To my knowledge, the derived estimators are new contributions to binary classification calibration domain. Paper is well-written and new calibration error upper bounds are motivated by the limitation of previous works and literature. Proposed theoretical results are supported by experimental results on both synthetic and real data. Although targeted on very specific classification setup, the contribution could provide useful information for the community, especially for those working on trustworthy ML. Overall, well-defined contributions to specific problem.\n\nSummary of strengths\n- Theoretically sound\n- Motivated by the limitation of previous work\n- Novel contributions (theoretical with techniques that could apply in practice)", "weaknesses": "There are also some weaknesses affecting the clarity of the presentation and significance of the results. First, although the motivation and derivation of the proposed theoretical results seem ok, the presentation could be improved and supported by illustration of the problem at the beginning, including the problem setup and possible limitations of previous work. Second, the experimental evaluation could be more versatile to fully support the proposed techniques, including the comparison with several real datasets (in addition to Figure 3), and other previous approaches presented in the related work section (in addition to Lip+Bkt). Also, different metrics of calibration accuracy and computational efficiency, and statistical significance of the results in comparison, could improve the practicality and the significance of the proposed contributions  and claims.\n\nSummary of weaknesses\n- Lack of illustrative example at the beginning  (motivation of the calibration problem setup, and limitation of previous approaches of vanilla binning etc.)\n- Limitations in experiments (comparison to other previous approaches, performance metrics, computational complexity)", "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": "4VJQhN70xk", "reviewer": "Reviewer_2RhD", "summary": "The paper addresses the problem of estimating the L1 calibration error of a binary classifier from a finite dataset. The paper has two main contributions:\n(1) upper bounds on the calibration error under bounded variation assumptions using a variant of total variation denoising, and \n(2) a perturbation method that enforces bounded derivatives, enabling kernel-based estimation. Both approaches are non-asymptotic and distribution-free.", "questions": "How should h be chosen in practice?\n\nECE uses finite binning and is computationally cheap. How far apart are the derived bounds from ECE estimates?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed methods are non-asymptotic and distribution-free\n- The empirical validation includes both synthetic experiments with known ground truth and real-data experiments. Real-data experiments (Amazon Polarity, CIFAR, IMDB, Spam) demonstrate practical applicability.", "weaknesses": "**Missing related work**\n\nThe paper would benefit from a more complete discussion of recent literature, e.g. \nhttps://proceedings.neurips.cc/paper_files/paper/2020/file/26d88423fc6da243ffddf161ca712757-Paper.pdf also addresses distribution-free calibration in binary classification, establishing fundamental limits and impossibility results in the absence of distributional assumptions.\n\n**Insufficient experimental analysis**\n\nThe experimental section is almost entirely descriptive rather than analytical. It reads more like preliminary notes or a work-in-progress draft than a finished scientific contribution. \nFor example, the paragraph on Real Data Experiment provides only vague descriptive claims without referencing any table/figure, or any scientific insight into why the method performs better.\nThe lack of analysis, missing experimental details, and superficial treatment of results suggest rushed submission.\n\n**Overall presentation of the paper can be improved**\n\nThe paper would benefit from clearer descriptions of tables and figures, explicitly stating what is shown and what conclusions should be drawn. For instance, the table below Figure 3 lacks a caption and is not referenced in the text. \nFootnote 6 appears incomplete, as it does not contain any text. \nSuch inconsistencies and lack of polish suggest insufficient attention to detail in the preparation of the paper and raise concerns about whether similar oversights exist in the rest of the paper.\n\n**Overstating contributions**\n\nThe conclusion that “we empirically demonstrated it is possible to measure calibration error on a real task of practical importance” might be overstated given that the result is an upper bound, not a point estimate. It would be fairer to emphasize certification rather than estimation per se.\n\n**Limitations not discussed**\n\nFor example, the limitation to binary classification is mentioned only in passing, yet this significantly restricts applicability given that most real-world calibration problems are multiclass. A thorough limitations section would strengthen the paper by setting appropriate expectations.", "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)