Practical estimation of the optimal classification error with soft labels and calibration
Authors: Ryota Ushio
Takashi Ishida
Masashi Sugiyama
Venue: ICLR 2026 Poster (2026)
Keywords: Bayes error
irreducible error
uncertainty quantification
soft labels
calibration
evaluation
Primary area: datasets and benchmarks
TL;DR: We propose a practical and theoretically grounded method for estimating the best achievable error rate in binary classification from (potentially corrupted) soft labels.

Abstract: While the performance of machine learning systems has experienced significant improvement in recent years, relatively little attention has been paid to the fundamental question: to what extent can we improve our models? This paper provides a means of answering this question in the setting of binary classification, which is practical and theoretically supported. We extend a previous work that utilizes soft labels for estimating the Bayes error, the optimal error rate, in two important ways. First, we theoretically investigate the properties of the bias of the hard-label-based estimator discussed in the original work. We reveal that the decay rate of the bias is adaptive to how well the two class-conditional distributions are separated, and it can decay significantly faster than the previous result suggested as the number of hard labels per instance grows. Second, we tackle a more challenging problem setting: estimation with _corrupted_ soft labels. One might be tempted to use calibrated soft labels instead of clean ones. However, we reveal that _calibration guarantee is not enough_, that is, even perfectly calibrated soft labels can result in a substantially inaccurate estimate. Then, we show that isotonic calibration can provide a statistically consistent estimator under an assumption weaker than that of the previous work. Our method is _instance-free_, i.e., we do not assume access to any input instances. This feature allows it to be adopted in practical scenarios where the instances are not available due to privacy issues. Experiments with synthetic and real-world datasets show the validity of our methods and theory. The code is available at https://github.com/RyotaUshio/bayes-error-estimation.

Published as a conference paper at ICLR 2026
PRACTICAL ESTIMATION OF THE OPTIMAL CLASSIFI- CATION ERROR WITH SOFT LABELS AND CALIBRATION
Ryota Ushio Takashi Ishida Masashi Sugiyama?.
1 The University of Tokyo, Tokyo, Japan
2 RIKEN AIP, Tokyo, Japan
fushio@ms ishidi da@, sugi yama wo wtt.kuuutokkooooo
ABSTRACT
While the performance of machine learning systems has experienced significant improvement in recent years, relatively little attention has been paid to the fun- damental question: to what extent vides a means of answering this question in the setting of binary classification, which is practical and theoretically supported. We extend previous work that utilizes soft labels for estimating the Bayes error, the optimal error rate, in two important ways. First, we theoretically investigate the properties of the bias of the hard-label-based estimator discussed in the original work. We reveal that the decay rate of the bias adaptive to how well the two class-conditional dis- tributions are separated, and it can decay significantly faster than the previous result suggested as the number of hard labels per instance grows. Second, we tackle more challenging problem setting: estimation with corrupted soft la- bels. One might be tempted to use calibrated soft labels instead of clean ones. However, reveal that calibration guarantee is not enough, that is, fectly calibrated soft labels can result in substantially inaccurate estimate. Then, we show that isotonic calibration can provide statistically consistent estima- tor under an assumption weaker than that of the previous work. Our method is instance-free, i.e., we do not assume access any input instances. This feature allows it to be adopted in practical scenarios where the instances are not available due to privacy issues. Experiments with synthetic and real-world datasets show the validity of our methods and theory. The code is available at pttppp///g..ta...ccocc//ooaattte
improve our models? This paper pro-
per-
INTRODUCTION
It is common practice in the field of machine learning research to assess the performance of newly proposed algorithm using one or more metrics and compare them to the previous state-of- the-art (SOTA) performance show its effectiveness (Neu 2024 Int 2025a b). In classification, arguably the most common one is the error rate, i.c., the expected frequency of misclassification for future data.
While the SOTA performance continues to improve for wide range of benchmarks over time, there is limit on the prediction performance that any machine learning model can achieve, which is determined by the underlying data distribution. It is important to know this limit, or the best achievable performance. For example, if the current SOTA performance is close enough to the limit, there is no point in seeking further improvement. It is not only wasteful in terms of time and financial resources but also harmful to the environment, since large-scale machine learning models are notorious for their high energy consumption (Strubell al. 2020 Luccioni al.) 2023)) Knowing the best possible performance also provides a practical check for test-set overfitting (Recht al.] 2018: Ishida et al.) 2023): if model's score the test approaches or exceeds the upper bound, it may be a signal of the model directly training on the test set.
In classification, the best achievable error rate for given data distribution is called the Bayes error, and the estimation of the Bayes error has a rich history of research (Fukunaga and Hostetler 1975
Devijver 1985 Berisha al. 2014 Moon et al. 2018 Noshad et al. 2019 Theisen et al. 2021

---

Published as a conference paper at ICLR 2026
Ishida al. 2023 Jeong et al.
2023). In the case of binary classification, the existing approaches can be roughly categorized into two groups: the majority of estimation from instance-label pairs
(T), 01) )............................) (z Mn X' {0,1) (Fukunaga and Hostetler 1975 Devijver 1985 Berisha et al., et al. 2021). where X is the space of instances, and the recently proposed methods of estimation from soft labels 7,--... 7/, E [0, 1] (Ishida et al.,
2014 Moon et al. 2018 Noshad et al.
2023 Jcong et al.) 2023). A soft label is a special type of supervision that represents the posterior x = Ii), i {I,...,,) n). and it quantifies the uncertainty of class labels associated with each instance 24. The strength of the methods proposed in (Ihhida al., 2023) Jeong al.] 2023) based on soft labels is that they are instance-free, i... they do not require access to the instances { Since the instances themselves are not used for estimation, these methods do not suffer from the curse of dimensionality even when dealing with very high- dimensional data. Moreover, the instance-free property is practically valuable since it makes the methods easy to apply to real-world problems, such as medical diagnoses, where the instances are often inaccessible due to privacy concerns. However, these methods have a crucial limitation: they assume that we have direct access to clean soft labels rj = Pyy = x = æ;), which only an oracle would know. Ishida et al. (023) also discussed scenario where each soft label n)s is approximated by an average fj = 1 Σ y of m hard labels y (1) y; per instance. They showed that, for a fixed number n of samples, the bias of the resulting estimator approaches zero as m tends to infinity. However, their bound on the bias is prohibitively large for practical values of m, and thus the theoretical guarantee for this estimator is weak.
class probability 7h Ply
Another issue is labeling distribution shift. For example, whereas the images in the original CIFAR-10 dataset (Krizhevsky) 2009) can be regarded as though they were annotated be- fore they were downscaled, the images in the CIFAR-1OH dataset (Peterson et al. 2019) were annotated after downscaling, making the task more challenging and thus increasing label un- certainty. Given that the Bayes error can be interpreted as the average label uncertainty, we will get an unreasonably high estimate of the Bayes error if we just plug the soft labels in CIFAR- 10H into their estimator, as shown in Fig. In general, a similar issue can arise due to subjectivity of human soft labelers, the bias of using large language models (LLMs) as annotators Gilardi et al. 2023 Tjuatja et al., 2024). Recent work has explored a range of techniques to obtain soft labels and confidence scores from LLMs, but constructing high-quality soft label remains to be a challenge (Xie et al., 2024] Kadavath et al. 2022 Argyle et al. 2023). This distortion issue due to the distribution shift was also mentioned by Ishida al. (202)) but solution was shown
Test error of Estimated
Bayes error
0.0
0.1
0.2
0.3
0.4
0.5
Error rate (%)
Figure 1: The Bayes error estimated with the method IsIida et al. (2023) is larger than the test error of a Vision Transformer (Dosovitskiy et al., 2021).
in their paper.
Contribution of this paper We extend the previous work by Ishida al. (023) that utilizes soft labels for estimating the Bayes error, the optimal error rate, in two important ways.
First, we deepen the theoretical understanding of the bias of the hard-label-based estimator discussed in the original work. Specifically, we show that the decay speed of the bias depends on how well the two conditonnii distributions are separated, and can approach zero significantly faster than the previous result suggested as the number m of hard labels per instance grows.
Second, we discuss new, more challenging problem of estimation from corrupted soft labels. In this scenario, we are given distorted version of the clean soft labels. The distortion can arise from shifted labeling distribution or subjectivity of human/LLL,, soft labelers. It reflects many real-word world problems including the estimation of best achievable performances for benchmark datasets and esti-
'For more information, CIFAR-10 was curated as follows. First, images for each class were collected by searching for the class label or its hyponym the Internet. Second, the images were downscaled to 32 x 32. Finally, human labelers were asked to filter out mislabeled images. On the other hand, CIFAR- IOFAR-IOH is soft- labeled version of CIFAR- 10, ie.. it consists of 10,000 test images of the CIFAR- 10 test set along with their soft labels. Each soft label was obtained as an average of 47 63 hard labels, which were collected by asking human labelers to answer which class the downscaled image helongs to. As result, the labeling processes are significantly different between these datasets.
2

---

Published as a conference paper at ICLR 2026
mation from soft labels obtained from subjective confidence. One might be tempted to use calibrated soft labels in place of clean ones. However, we reveal that calibration guarantee is not enough, i.c., even perfectly calibrated soft labels can result in substantially inaccurate Bayes error estimate, which highlights the importance of choosing appropriate calibration algorithms. Then, we show that classical calibration algorithm called isotonic calibration (Zadrozny and Elkan (202)) can provide a statistically consistent estimator as long as the original soft labels are correctly ordered.
2
FINE-GRAINED ANALYSIS OF THE BIAS
We first explain the preliminaries for this section and then present our main results.
2.1 PRELIMINARIES
Formulation and notations Let X' Rd and y be the spaces of instances and output labels, respectively. In this paper, we confine ourselves to binary classification problems and thus we set y' = 10. Classes and 0 are also called the positive and negative classes, respectively. Let be a distribution over X' x y and (zz, y) be pair of random variables following F, where x E E is an input instance and y E {0. is the corresponding class label. Throughout this paper, 21...... In are i.i.d. samples drawn from the marginal distribution Pxx over the input space X. We denote by Pl, Fo two class-conditional distributions over the input space X given y/ = and y = O, respectively. Note that Px OP1 + (1 O).o. where 0 == Ply 1) E (0, 1) is the base rate. n(2)) is the clean soft label for an instance x, i.e., the posterior probability P(y = x) of y = given x. The expectation and the variance with respect to the marginal Px are denoted by E and Var, respectively.
For any positive integer n, we denote [n]] [1,....n)) n). An indicator function is denoted by [-]- Given a sequence of n random variables 21,..-, 2n. we use a shorthand 21:81 = (21,.... 2.). For Ja Rdd and E E Rdxd ((,, Σ) is the Gaussian distribution with mean μ and covariance E.
Estimating the best possible performance with soft labels Among the most commonly used performance measures would be the error rate. The error rate of classifier h X + y is defined as Err(h) := E(z,))~ [1] [y * h+(r)]]. where (a, y) is a test instance-label pair drawn independently of training data. The best possible error rate Err" = inf Err(h) is called the Bayes error
(Mohri al. 2018
Recall that ())) = Pyy= 1 r). Ishida et al. 2023) proposed a direct approach to estimating the Bayes error Err" assuming access to the soft labels (r(x))]== rather than instance-label pairs {Z v:)) Its derivation is outlined follows. First. it is well-known that the Bayes error can be expressed as Err" = Ex- [min (n((), 1 - (=))] (Cover) 1968). Replacing the expectation with sample average over { they obtained an unbiased estimator
1 min (%/ - n n
Err (1p:.)
(1)
where n7 = =2x))) It is also statistically consistent, or more specifically, for any 8 (0. 1), with probability at least 1 - 5, we have Err" (77m.) - Err" log(2/0)
81s
In practical terms, the instance-free nature of this method exhibits considraabe advantages over ex- isting methods described in Appendix A despite its simplicity. It can be applied to settings where input instances themselves are unavailable, e.g., due to privacy issues. On the other hand, one of the crucial drawbacks of this method is that clean soft labels are usually inaccessible in practice. Therefore, we have no choice but to substitute some estimates for them. Ishida et al. (2023) also con- sidered a setting where γ) is approximated by an average of hard labels 77. := ΣØ= y, where (1) 9 ..... yi (m)) are m hard labels each of which is drawn independently from the posterior distribu- tion of the class labels given the instance z4. In practice, y ......? (mm) could be collected by asking m different human labelers to answer whether x, belongs to class 1. CIFAR-10H (Peterson et al.
Thee infimum taken over all measurable functions.
3

---

Published as a conference paper at ICLR 2026
2019) and Fashion-MNIST-H (Ishida et al. 2023) examples of dataset constructed as such. By plugging ?/s in place 7h, they obtained the estimator Err (fmm) = - min ( mn.. They showed that the bias is bounded as
loog(2n (2g
E Err (mn.) Err"
2/m
and thus vanishes as mn - OC given n fixed. However, the rate Ô (1/v /m) is quite slow given that m is typically much smaller than For example, in the case of the CIFAR-IOH dataset, each image is given only around 50 hard labels. Later in Section [.2] we will show that this rate can be significantly improved for well-conditioned distributions. In addition, the second term on the right- hand side of (2 increases as n grows, which appears to be unnatural. We also show that the bias can be upper-bounded by quantity irrelevant
2.2 MAIN RESULTS
Improved bound on the bias The following theorem provides a new bound on the bias of the estimator Err" (Tmm). The proofs for all results in this section can be found in Appendix B
Theorem 1. We have
(n(x))())) m
E
min
E
Err (iLm))
Err* S 0,
(3)
xxxx
2m
where Lgr(()) is g(1-g) 12q-1 if + 0.5 and xc: if 0.5.
First of all, we note that our upper bound does not contain unlike the existing result 2 by Ishida
et al. (2023). More importantly, our bound (3) indeed improves upon theirs (Proposition We only
need weaker version of (3) to show the improvement:
E
Err (mi..)
Err" S 0.
Although the [n((((())) term in the left-hand side of 3 is unnecessary to improve the previous result shows the graph of the function LE (p). takes a near-zero value when p is close to 0 or 1 and diverges to infinity that (1)(a) is large for instances close to the Bayes-optimal decision boundary 77x)) = 0.5, while it is close to zero for instances far away from it. Therefore, the rate at which the bias decays can be understood as mixture of the fast rate 1/m and the slower rate 1/ym, whose weights are determined by how well the two classes are separated. We validate this with numerical expeirments in Appendix
( it provides further insights. Fig. Appendix
- 0.5. This means
Well-separated cases Here we note that real-world datasets often have well-separated classes; see, e.g., Fig. in Appendix B If the two classes are perfectly separated, the bias can decay at the fast rate (1/m), opposed to the worst cases rate O(1/ /m).
Corollary 1. Suppose there exists a constant > Then, have
O such that (n(x) 0.5 2 c holds almost surely.
4c2
S
ErT" (hmm))
Err" S O.
Scm
The assumption of Corollary is satisfied by, for example, the following distribution.
Example (Perfectly separated distributions with label noise). Consider two continuous distribu- tions Fo, Fi over X' with disjoint supports. An instance-label pair (x. y) is generated as follows. First, an index is selected from 10,1} with equal probability. Given k. x and y are generated conditionally independently as follows: (i) The instance is sampled from Fe. (ii) The label is set to 1 with conditional probability z/ and & with conditional probability v, where v + 0.5. Then, the assumption of Corollary is satisfied for -v50.55 0.5/.
Computable bound for general cases Our results so far (Theorem I and Corollary I provide tigher bounds and more detailed perspective the bias. However, a downside of those results is that, in order to compute the numerical values of the lower bounds directly, we need to know some characteristics of the data distribution that might not be available in most practical scenarios. The good news is that we can still derive a computable bound that only requires an upper bound on the Bayes error, e.g., the error rate of the SOTA model, from Theorem
4

---

Published as a conference paper at ICLR 2026
Corollary 2. Assume that Err" & E. Then, we have - mm) where
S E Err (mm=.)
Err" - 0,
((1 - ()
+ min (1
E t
B(E, = inf tE(0,1/2)
(5)
2t
V
2m
The function BEE, m) can be computed numerically without any information about the data distribution, except for an upper bound of the Bayes error; F. Fig. shows the magnitude of our lower bound, BEF, m.), for various values of E' (the blue line). It also shows the existing bias bound by Ishida et al. (2023) (the or- ange line). This comparison demonstrates that Corol- lary is substantial improvement over the existing result across the entire range the parameter E.
10a
Maximum bias
10-2
10
(8(E, m))
Let take the binarized CIFAR-10 10 test set example. consists n = 10000 instances, each of which has soft label obtained the average of around m = 50 hard labels from the CIFAR-IOH dataset. As the parameter E, we can the Vision Transformer (Dosovitskiy et al. 2021)'s s empirical er- ror rate of 0.0005 reported by Ishida al. (2023), which is shown by the black dashed line in Fig. While the existing bound suggests the bias of the hard-
Ishida et (2023)
10
10-1
10
10-1
Figure 2: A comparison of our bias bound (Corollary (2) and the existing bound by Ishida et al. (2023) with n = 10000, m = 50. The dashed line indicates the test error (0.05%) of the SOTA model for the bina- rized CIFAR-10 dataset, which we can use as E' in Corollary 2 Our bound is over 200 times tighter than the existing one in this setup.
label-based estimator Err" (7mm) could be as large as 0.557, our bound reveals the estimator is not that bad; indeed, it implies the bias is never larger than 0.00276. In this case, our result is over 200 times tighter than theirs.
Theorem also implies the estimator Err" (7i:n) is statistically consistent; see Corollary for de- tails.
ESTIMATION FROM CORRUPTED SOFT LABELS
This section tackles a more challenging setting where we do not have access to the true posterior probability 7). This setting reflects many real-world problems, such in medical diagnosis where doctor's ' subjective confidence in their decision can be regarded as a soft label, or when practition- ers provide automated soft labels with LLMs in place of human annotators. However, there is no guarantee that it exactly reflects the true underlying probability.
In this section, consider a problem setting where each instance n, is given a real number ïj [0, 1], which is expected to approximate the clean soft label in some sense but not necessarily identical 7/- We call {i corrupted soft labels. How can we estimate the Bayes error when only corrupted soft labels are available instead of clean ones? Estimation with provable guarantee will be impossible without some assumption on the quality of the soft labels. Then, what guarantee can be provided under what assumption?
3.1 PRELIMINARIES
In addition to the preliminaries introduced in Section 2.1 we briefly review few more required for the discussion this section.
Calibration
Predicting accurate class labels is not always sufficient in classification problems. often crucial to obtain reliable probability estimates, especially high-stakes applications cluding personalized medicine (Jiang et al.] 2012) and meteorological forecasting (Murphy 1973
DeGroot and Fienberg 1983).
"See Scction 4.1 for details.
5

---

Published as a conference paper at ICLR 2026
A popular notion to capture the quality of probability estimates is calibration. A probabilistic classi- fier is said to be well-calibrated the predicted probabilities closely match the actual frequencies of the class labels (Kull et al. 2017), i.c., c(x) E ly c(x)] almost surely. While one might hope that a perfectly calibrated output c(x:) matches the posterior probability IF [y æ] P(y = xt) it is not necessarily true. Indeed, calibration is weaker notion and just necessary condition for c(z) = E ly æ]. For example, even a constant predictor c(x) = P (y = 1) is well-calibrated []] although can be far from P (y 2)).
It is known that many machine learning models, including modern neural networks, are not cali- brated out of the box (Zadrozny and Elkan 2001] Guo et al.] 2017). Therefore, their outputs have to be recalibrated in post-processing. and various methods have been proposed to achieve this goal. They can be roughly categorized into two groups, namely parametric and nonparametrie methods. The former includes Platt scaling (Platt 1999), also known as logistic calibration (Kull et al., 2017), and beta calibration (Kull et al. 2017]. Among the latter category are histogram binning Zadrozny and Elkan 2001) and isotonic calibration (Zadrozny and Elkan 2002). Each of these methods quires a dataset (C,, y:) } to obtain a function that takes the output of an uncalibrated predictor e
and transforms it into reliable probability estimate. This function is sometimes called calibration map (uull et al. 2017 2019). Here, c = c(x;) is the output of c for an instance 2i, and ys is the corresponding class label. To avoid overfitting, each (Jri, needs to be sampled independently of the training set used to obtain the predictor c.
Isotonic calibration Here, we briefly describe the algorithm of isotonic calibration Zadrrzzy and Elkan 2002). arguably one of the most commonly used nonparametrie recalibration meth- ods, as it plays important role in this paper. Suppose dataset {(a, w)) is given. The algorithm proceeds as follows. First, the dataset (c1, 11),..., (Cn, Vhe) is reordered into (c()), B(1)) ,..., (Cin), W(n) so that the resulting sequence ((1))...,, ((n) of outputs becomes non- decreasing. Then, we find a non-decreasing sequence 0 I (1) S ... S dn) S such that
minimizes the squared error Ei=1 (MO) - <(1) Finally, for each i [n]] dis is assigned as the calibrated version of C(s). This procedure is special case of isotonic regression, one of the most well-studied shape-constrained regression problems.
3.2 PROPOSED METIIOD
We propose a simple approach where we first calibrate the corrupted soft labels and then plug them into the formula (T) for clean soft labels. Although calibration was originally developed for trans- forming the output scores of classifiers into reliable probability estimates, here we suggest using it for corrupted soft labels. We assume that, for each [m]. we are given a corrupted soft la- bel ij. E [0, 1] and a single hard label Vi [0, }} sampled from the true posterior distribution Pyy x = 2.)). We use the hard labels { to calibrate the soft labels { using some calibration algorithm A. We write TH to represent the resulting calibrated soft labels. Finally, we
estimate the Bayes error Err" by Err" (fd.) 1 Σ._ min { 1 }
min
However, as we mentioned earlier, even perfect calibration does not necessarily imply that the re- sulting soft labels are accurate estimates of the clean soft labels. A simple example illustrates this limitation:
Example 2. Consider drawing instances from mixture of two distributions over X' with disjoint supports, and let us set the mixture rate 0 to be 0.5. The true Bayes error is trivially 0. If A is a calibration algorithm that produces constant soft labels गzK 0 0.5 for all [m]. it indeed achieves perfect calibration. However, the resulting estimate of the Bayes error is min {6, 1 0} = 0.5, which deviates significantly from the true value O.
Therefore, estimation with a provable guarantee will not be possible for arbitrary calibration algo- rithms or without any assumptions on the soft labels. What calibration algorithm can achieve reliable estimation under what assumption? In Section 3.3 we provide the first answer to this question.
'If c(z) takes the constant value PP (y 1) for all x, E. [g c(x)] is equal to E [v] TP (yr 1) since it is conditional expectation conditioned by a constant.

---

Published as a conference paper at ICLR 2026
3.3 THEORETICAL GUARANTEE FOR ISOTONIC CALIBRATION
Here, we propose choosing isotonic calibration (Zadrozyy and Elkan 2002) as the calibration algo- rithm A and indentify a condition under which we can consistently estimate the Bayes with our method. Specifically, we estimate the Bayes error by the following procedure:
Reorder (m,, ..., (7 Un) into (ūt)) M(1) ..... (ī(m): M(m)) so that the resulting se- quence (1)))- Mn) of outputs becomes non- non-decreasing.
iii) Find a non-decreasing sequence
I
1 (m) S such that it minimizes
the squared error 1 EE=1 ((()) - ploo (()
This gives us isotonic-calibrated soft labels
(1)--...
Pleo
Tso (n))
(iii) Estimate the Bayes error as Err (Tix) = E min
ciso (G)
1so (()
The next theorem the main theoretical result of this section, which states that we can construct consistent estimator of the Bayes error using isotonic calibration as long the soft labels' order is preserved. The use of isotonic regression allows us to provide a solid theoretical guarantee without making parametric assumptions
how corruption occurs. See Appendix for the proof.
Theorem 2. Suppose that there exists an increasing function f such that ñj. f(n) almost surely. Then, for any E (0, 1), with probability least 1 5, we have
1 n//3
log log(110g (1/8)
Err Brr"(77n)) Err"
SC
where C. > 0 is constant.
Note that the assumption Theorem 2 is a relaxation of the availability clean soft labels since take the identity map as when it: πą- In other words, the original work by Ishida et al. (2023) assumes that we have access to the exact values of the clean soft labels, whereas our proposed method only requires the knowledge of their order.
Furthermore, our result can be extended to the case where the corruption involves random noise.
Theorem 3. Assume each corrupted soft label ii is generated as ij; f())) + E where differentiable function such that f' > for some constant O and is a zero-mean random variable with variance < o². Then, for any ô (0, 1), with probability at least we have
log
Err² (m)) Err" SC (
n//3 +
71
where C² is a constant.
think of the situation studied in Section 2 but with corrupted label- ing distribution skewed by some function f. For each = 1,..., n1, the resulting posterior dis- tribution be seen Bernoulli distribution with mean f(x). Then, draw hard labels v/ "!....., from that distribution. We can then approximate the unknown soft label 7) by the average m Σド= 1/5
As example,
(i) of the hard labels and plug into our estimator. In this case, the randomness over the hard labels translates to additive noise with standard deviation at most o 2/m
A limitation of Theorem B is that it cannot be applied to f whose derivative can be arbitrarily small. Roughly speaking, it is because small fluctuation in the function value can translate large devi- ation in the inverse function value if the function is too "flat." We have not yet reached theoretical understanding of how much violating this assumption hurts the estimation accuracy. However, in our empirical study with synthetic data (Appendix D.2). the results suggest that our method can perform well even for such corruption functions. An interesting finding that beta calibration (Kull though it is well-specified parametric calibrator in exper-
et al. (2017)) performs poorly imental setting. This fact suggests that choosing appropriate calibration methods, such as isotonic calibration, is indeed crucial in our algorithm design. See Appendix D.2 for details.
7

---

Published as a conference paper at ICLR 2026
4 EXPERIMENTS
In this section, we present experimental results where we estimate the Bayes error of synthetic and real-world datasets using our proposed method.
4.1 EXPERIMENTAL SETTINGS
The methods employed in this experiment were the following: (i) clean: the estimator with clean soft labels, i.e., Err (Maa), (ii) ha rd: the estimator with approximate soft labels obtained as averaged hard labels, i.e., Err" (7mm), (iii) corrupted: the estimator with corrupted soft la- bels, i.e., Err* (Tm.), and (iv) the estimator with soft labels obtained by calibrating the corrupted soft labels, i.e., Err" (. We used the following calibration algorithms A: isotonic calibration (isotonic; Zadrozny and Elkan (2002)). uniform-mass histogram binning (Zadrozny and Elkan 2001) with 10, 25, 50 and 100 bins (hist-10, hist-25, hist-50 and hist-100), beta cal- ibration (beta; Kull et al. (2017)) its variants with restricted parameters (beta-am, beta-ab and beta-a; see Appendix D.3.2 for details), and the classic Platt scaling (platt: Platt (199)).
Platt
We used the following synthetic and real-world datasets.
Synthetic dataset We generated a two-dimensional synthetic dataset of size n = 10. 000 from a Gaussian mixture Px 0.6 Po + 0.4 PI, where P. N ((0, 0) .2), P1 N ((2,2) I2) and la is the d-by-d identity matrix. We used m = 50 hard labels per instance in the hard setup. For each [n). we generated the corrupted version 7is of the soft label тy by î fm1; 0.7).
1+ 11- (1 (/1-))))))
1/a 1-b -1
where a b)
<<<<<<< < a> and 0 < b < 1. The function f
the inverse function of the two-parameter beta calibration map (Kull al. 2017) and can express various continuous increasing transformations on the interval (0, 1) depending on the parameters and b. Fig. 3 shows the graph of the corruption function f. As can be seen the figure, it pushes probability values away from zero one, making the soft labels "unconfident." It also distorts soft labels so that 7ı 0.5 mapped to ij f(n) b. Note that f satisfies the assumption of Theorem since it is increasing. We also explored other sets of parameters and other types of 2
corruption; see Appendix for details.
CIFAR-10 The second dataset is the test set of CIFAR-10 (Krizheskyy 2009) with soft labels taken from the CIFAR- 10H dataset (Peterson et al.] (219).. Since they originally multi-clan datasets, we reconstructed a binary dataset by relabeling the animal- related classes (bird, cat, deer, dog, frog and horse) as positive and the rest as negative, similarly to what Ishida et al. (2023) did their experiments. Recall that the CIFAR-1OH soft labels can be considered to be corrupted because of the mismatched labeling dis- tributions, as mentioned in Section D We compared the esti- mated Bayes eтror with the test error of a Vision Transformer (ViT) (Dosovitskiy et al. 202T) on this dataset reported by [shida al. 2023), which is 0.05%.
0.6
0.4
0.2
0.0
1.0
Fashion-MNIST We also used the MaSSI dataset (iiao et al., 2017) and its soft-labeled counterpart, Fashion- MNIST-H (Ishida al. 2023). Following [shida et al. (2023). we binarized the dataset by treating T-shirt/lp, pullover, dress, coal and shirt as the positive class. The rest proceeded similarly to the CIFAR-10 experiment except that newly trained a ResNet- 18 (He et al. 2016) in place of the VIT. Details such as training parameters can be found in Appendix
Figure 3: The corruption
function f(: a, b) with pa-
rameters a = 2, b = 0.7.
ChaosNLI ChaosNLI (Nie al. 2020 Zhou al. 2022) is natural language processing dataset with 100 hard labels per data point. It consists of three sub-datasets: SNLI (n = 1, 1,44,,, MNLI (n 1, 599) and AbductiveNLI (n 532).
ICLR peer-review datasets We also put together a new dataset, which consists of n = 32, 829 instances of peer-review results for the past ICLR conferences. Peer-review be considered as
8

---

Published as a conference paper at ICLR 2026
33.5-
2.55
23.0 12.5
2.0
Extimated Bayes
Estimated
Estimate
compated
Bvrtzon
march
butad
(a) Synthetic dataset
(b) CIFAR-I0
(c) Pashion-MNIST
Figure 4:
The estimated Bayes enror for the synthetic dataset, CIFAR-10. and Fashion-MNIST obtained with various methods. Error bars denote 95% bootstrap confidence intervals. For CIFAR- 10, the VIT test error is indicated by horizontal dashed line, while for Fashion-MNIST the dashed line marks the ResNet-18 test error.
a binary classification task (accept/reject). We used our dataset to estimate the Bayes error of the ICLR reviews, which is the probability that the ideal, most competent possible reviewer mistakenly rejects a good paper or accepts a bad paper. It can be regarded as representing the inherent difficulty of the review task. For each paper submission T2, utilized the OpenReview API retrieve the averaged score s; weighted by the confidences of the reviewers and the final decision yı accept (vi or reject (y: = 0). We then obtained corrupted soft label 7j for x; by normalizing the averaged score 8; to fit into [0. 1]. We merged data from ICLR 2017-2025 to construct a dataset 32, 829 examples, each of which has a corrupted soft label (i.c., normalized average score) and a single hard label (i.e., final decision) for calibration S
consisting of
4.2 ESTIMATION OF THE BAYES ERROR
Here, we estimated the Bayes error of the above-mentioned datasets using the methods described in Section 4.1 We used 1, 000 bootstrap resamples compute a 95% confidence interval for each method. Note that, for real-world datasets, we could not experiment with the clean setup as clean soft labels are unavailable. Therefore, we conducted our experiment only for /plaat treating the given soft labels as corrupted 6
corrupted/ssof sot www.eeddissoiiiiio
Results Fig. shows the results of the experiments with the synthetic, CIFAR-I0 and Fashion- MNIST datasets. The full results including those for the ChaosNLI and ICLR peer-review datasets can be found in Appendix D.3.3 The black dashed lines in Fig. 4b and Fig. 4c indicate the test eтror of classifier trained for each dataset as reference. As expected, the underconfidence of the corrupted soft labels resulted in severe overestimation of the Bayes error. All the calibration methods (i disotonic c, hist-x, beta* * and platt) t) produced far more reasonable estimates com- pared with the baseline corrupted. For Fashion-MNISS failed to offer reasonable estimates, as can be seen in Fig. Ac Specifically, hist-22 22 resulted in Bayes error estimate substantially larger than the ResNet's 's test error. This may highlight the neces- sity for carefully chosen calibration method, isot onic, beta* and platt produced reasonable estimates in these settings.
however, histogram binning sometimes
mentioned in Section 3.2 On the other hand,
4.3 COMPARING CALIBRATION ALGORITHMS USING FEEBEE
For real-world datasets, it is hard to conclude which calibration algorithm the best just from the above results, since the true Bayes error is unknown. To address this limitation, here we compared various calibration algorithms using FeeBee (Renggli et al. (02T). real-world evaluation frame- work for Bayes eтror estimators. The key idea of FeeBee is to inject various levels of synthetic label noise and see the estimator is able to track the resulting changes in the Bayes error; the estimator
We also conducted experiments with single-year datasets (ICLR2017, .... ICLR2025). The results deferred to Appendix due space limitations.
'Atthough we could run hard experiments with m = using the hard labels from the CIFAR-10 test set, they would not produce any meaningful estimates of the Bayes error hecause min {v. 1 y} = 0 for both y and 1.

---

Published as a conference paper at ICLR 2026
Table 1: FeeBee scores of calibration algorithms across real-world datasets (lower better). The best scores for each dataset are highlighted in bold.
Dataset
Algorithm
CIFAR-10
Fashion-MNIST
SNLI
MNLI
AbductiveNLI
ICLR2017-2025
isctonic
0.1131
0.1200
0.1025
0.0908
0.0721
0.0276
min.
0.1644
0,1568
0.1117
0.0941
0.0944
0.0660
hiat
max.
0.1670
0.1592
0.1163
0.0986
0.0979
0,0670
beta
0.1701
0,1782
0.1167
0.0966
0.1306
0,0565
0.1694
0.1792
0.1138
0.0971
0.1270
0.0562
beta
0.1698
0,1806
0.1168
0.0974
0.1263
0.0556
bata-a
0.1702
0.1785
0.1144
0.0995
0.1254
0.0551
platt
0.1677
0.1659
0.1297
0.1106
0.1095
0.0610
penalized if fails do As result, the lower the FeeBee score is, the better the estimator is. FeeBee provides a practical way to evaluate Bayes error estimators on real-world datasets without requiring knowledge of the true Bayes error rates. Appendix D.4.1 dedicated a more detailed review of the FeeBee framework.
For each dataset, compared the FeeBee scores of the following calibration algorithms: iso- tonic calibration (isotonic) c), histogram binning (hist), beta calibration (beta) and its variants (beta-am, beta-ab and beta-a), and Platt scaling (platt). For histogram binning, we tested various numbers of bins (10, 15, 20..... 7. where n is the number of data points) and reported the best and the worst scores among them. See Appendix D.4.2 for more details on the experimental settings.
Results As shown in Table isotonic calibration (i (isotonic) performed the best among the calibration methods across all datasets, often by large margin. It strongly supports choice of isotonic calibration as the soft label calibrator for Bayes error estimation. solid theoretical guarantee (Theorem 2 and Theorem 3 but also has been shown perform the best empirically for various real-world datasets. This again highlights that choosing an appropriate calibration algorithm key to successful estimation of the Bayes error.
not only has a
CONCLUSION AND DISCUSSION
We discussed the estimation of the Bayes error in binary classification. In Section 2 we significantly improved the existing bound on the bias of the hard-label-basee estimator. We also revealed that the decay rate of the bias depends on how well the two class clus-connitional distributions are separated, and it can decay challenging problem of Bayes error estimation from corrupted soft labels and proposed an estimator based on calibration. After presenting an example highlighting the importance of choosing appro- priate calibration algorithms, using isotonic calibration as long as the original soft labels are correctly ordered. Then, our theory was validated by numerical experiments with synthetic and real-world datasets in Section
much faster rate than the previous result suggested. In Section 3 we tackled
proved that
construct statistically consistent estimator
Finally, we discuss possible future directions. An important one is the extension to multi-class prob- lems. Investigating theoretical guarantees for calibration algorithms other than isotonic calibration (e.g., histogram binning) is another interesting direction.
ACKNOWLEDGMENTS
RU supported by the RIKEN Junior Research Associate Program, TI was supported by KAK- ENHI Grant Number 22K17946, and MS was supported by JST ASPIRE Grant Number JPM- JAP2405.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All the information needed to reproduce the experimental results in this paper is fully disclosed in the body text, the appendices, and the source code in the supplementary material or our GitHub repository. The body text and the appendices clearly explain the experimental settings. The supple- mentary material and the GitHub repository provide all the source code to run the experiments and the README. md file containing the instructions required to reproduce the experimental results. The appendices contain the proofs for all the theoretical results in this paper. We also made sure it is clear what assumptions are made in each theorem, proposition, lemma, and corollary.
REFERENCES
Lisa P Argyle, Ethan C Busby, Nancy Fulda, Joshua R Gubler, Christopher Rytting, and David Wingate, Out one, many: Using language models to simulate human samples. Political Anal- ysis, 31())3377-31, 2023.
Miriam Ayer, H. Daniel Brunk, George M. Ewing, William T. Reid, and Edward Silverman. empirical distribution function for sampling with incomplete information. The Annals of Mathe- matical Statistics, pages 641-647, 1955.
Pierre C. Bellec. Sharp oracle inequalities for least squares estimators in shape restricted regression. The Annals of Statistics, 46(2):745-780, 2018.
Pierre C. Bellec and Alexandre B. Tsybakov. Sharp oracle bounds for monotone and convex regres- sion through aggregation. The Journal of Machine Learning Research, 1161198991922 2015.
Visar Berisha, Alan Wisler, Alfred O. Hero, and Andreas Spanias. Empirically estimable classifica- tion bounds based on new divergence measure. arXiv preprint 1rXiv:1412.65344 2014.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford University Press, 2013.
Sabyasachi Chatterjee and John Lafferty. Adaptive risk bounds in unimodal regression. Bernoulli, 25(1):1-25, 2019.
Sabyasachi Chatterjee, Adityanand Guntuboyina, and Bodhisattva Sen. On risk bounds in isotonic and other shape restricted regression problems. The Annals of Statistics, 43(4):1774-1800, 2015.
Sourav Chatterjee. A new perspective least squares under convex constraint. The Annals of Statistics, pages 1340-2381 2014.
Thomas Cover. Nearest neighbor pattern classification. IEEE Trans. Information Theory, 4(5): 515-516, 1968.
Morris H. DeGroot and Stephen E. Fienberg, The comparison and evaluation of forecasters. Journal of the Royal Statistical Society: Series D (The Statistician), 32(1-2):12 12,222, 1983.
Pierre A. Devijver. A multiclass, k-NN approach to Bayes risk estimation. Pattern Recognition Letters, 3(1):16,, 1985.
Persi Diaconis and Susan Holmes. Three examples of Monte-Carlo Markov chains: At the interface between statistical computing, computer science, and statistical mechanics. In Discrete probabil- ity and algorithms, pages 43-56. Springer, 1995.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations, 2021.
Keinosuke Fukunaga and L. Hostetler. K-nearest- neighbbr Bayes-risk estimation. IEEE Transac- fions Information Theory, 2163)225-- 1975.

---

Published as a conference paper at ICLR 2026
Fuchang Gao and Jon A. Wellner. Entropy estimate for high-dimensional monotonic functions. Journal of Multivariatee Analysis, 98(9):1551-1764, 2007.
Xiang Gao, Meera Sitharam, and Adrian E Roitberg. Bounds on the Jensen gap, and implications for mean-concentratted distributions. The Australian Journal of Mathematical Analysis and Ap- plications, 16(2):1-16. 2019.
Alexandra Gessner, Oindrila Kanjilal, and Philipp Hennig. Integrals over Gaussians under linear domain constraints. In International Conference on Artificial Intelligence and Statistics, pages 2764 2774.. PMLR, 2020.
Fabrizio Gilardi, Meysam Alizadeh, and Maël Kubli. Chatgpt outperforms crowd workers for text- annotation tasks. Proceedings of the National Academy of Sciences, 120(30):e2335016122 2023.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In International Conference Machine Learning, pages 1321-1330. PMLR, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
dean-Baptiss Hiriart-Urutty and Claude Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals. Springer Berlin, Heidelberg, 1993.
Proceedings of the 13th International Conference on Learning Representations (ICLR 2025), Sin-
gapore. April 2025a. International Conference Learning Representations. URL https:
Ficlrr.ce/Coferren.ess//// 2025 Conference dates: April 24-28 2025.
Proceedings of the 42nd International Conference on Machine Learning (ICML 2025), Vancouver, BC, Canada, July 2025b. International Machine Learning Society. WtRlhttps:/// //tp:///mmmmmmmmmmmmm//////..... ceml. cc/ Conference dates: July 13-19 2025.
Takashi Ishida, Ikko Yamane, Nontawat Charoenphakdee, Gang Niu, and Masashi Sugiyama. the performance of my deep network too good to be true? A direct approach to estimating the Bayes error in binary classification. In International Conference on Learning Representations, 2023.
Minoh Jeong, Martina Cardone, and Alex Dytso. Demystifying the optimal performance of multi- class classification. In Thirty-eevntth Conference Neural Information Processing Systems, 2023.
Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila Ohno-Machado. Calibrating predictive model estimates to support personalized medicine. Journal of the American Medical Informatics Asso- ciation, 19(2):263 274,, 2012.
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Satfield-Dodde Nova DasSarma, Eli Tran-Johnson et al. Language mod- els (mostly) know what they know, arXiv preprint arXiv:2207.060 02220, 2022.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1-2):81-93, 1938.
Durk P. Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1xl convolutions.
Advances in Neural Information Processing Systems, 31, 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical repoott, University of Toronto, 2009.
Meelis Kull, Telmo Silva Filho, and Peter Flach. Beta calibration: A well-founded and easily implemented improvement on logistic calibration for binary classifiers. In Artificial Intelligence and Statistics, pages 623-631. PMLR, 2017.
Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining call-cali multi-class probabilities with dirichlet calibration. Advances in Neural Information Processing Systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2026
Ananya Kumar, Percy S. Liang. and Tengyu Ma. Verified uncertainty calibration. Advances in Neural Information Processing Systems, 32, 2019.
Alexandra Sasha Luccioni, Sylvain Viguier, and Anne-Laure Ligozat. Estimating the carbon foot- print of bloom, 176b parameter language model. Journal of Machine Learning Research, 24 (253):1-15, 2023.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning, 2nd Edition. MIT press, 2018.
Kevin R. Moon, Kumar Sricharan, Kristjan Greenewald, and Alfred O. Hero IlI. Ensemble estima- tion of information divergence. Entropy, 20(8):560, 2018.
Allan H. Murphy, A new vector partition of the probability score. Journal of Applied Meteorology and Climatology, 12(4):595-600 1973.
Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS 2024), Vancouver, BC, Canada, December 2024. Neural Information Processing Systems Foundation. Conference dates: December 10-15
URL htttp::/neuripps: / 2024.
Yixin Nie, Xiang Zhou, and Mohit Bansal. What can we learn from collective human opinions natural language inference data? In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguisties, 2020.
Morteza Noshad, Li Xu, and Alfred Hero. Learning to benchmark: Determining best achievable misclassification error from training data. arXiv preprint arXiv:1909.07192 2019.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lak- shminarayanan. Normalizing flows for probabilistic modeling and inference. The Journal of Machine Learning Research, 22(1):2617-2680 2021.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825- 2830, 2011.
Joshua C. Peterson, Ruairidh M. Battleday, Thomas L. Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. Proceedings of the IEEE/CVF International Conference Computer Vision, pages 9617-9626, 2019.
John Platr. Probabilistic outputs for support vector machines and comparisons to regularized likeli- hood methods. Advances in Large Margin Classifiers, 10(3):61-74, 1999.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do CIFAR-10 classi- fiers generalize to CIFAR-10? arXiv preprint
2018.
Cedric Renggli, Luka Rimanic, Nora Hollenstein, and Ce Zhang. Evaluating bayes error estimators on real-world datasets with feebee. Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
T. Robertson, E.T. Wright, and R. Dykstra. Order Restricted Statistical Inference. Probability and Statistics Series. Wiley, 1988. ISBN 9780471917878.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for modern deep learning research. Proceedings of the AAAI Conference on Artificial Intelligence, 1693-19666 2020.
Ryan Theisen, Huan Wang, Lav R. Varshney, Caiming Xiong, and Richard Socher. Evaluating state-of-the-art classification models against Bayes optimality. Advances in Neural Information Processing Systems, 34:9367-9377 2021.
Lindia Tjuatja, Valerie Chen. Tongshuang Wu, Ameet Talwalkwar, and Graham Neubig. Do LLMs exhibit human-like response biases? a case study in survey design. Transactions of the Association for Computational Linguistics, 12, 2024.
13

---

Published as a conference paper at ICLR 2026
Aad W. Van Der Vaart and Jon A. Wellner. Weak convergence and empirical processes: With applications to staristics. Springer, 1996.
Ramon van Handel. APC 550: Probability in high dimension. Lecture Notes, Princeton University, 21, 2016. URL https:h/twb math. pr porrncetton. www.//van/AACS50.... pdf
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, C J Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-222 2722, 2020. doi: 10.1038/s4 (0t////1599--011 022---019-08862-
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Zhihui Xie, Jizhou Guo, Tong Yu, and Shuai Li. Calibrating reasoning in language models with internal consistency. In The Thirtty-ighth Annual Conference Neural Information Processing Systems, 2024.
Fan Yang and Rina Foygel Barber. Contraction and uniform convergence of isotonic regression. Electronic Journal of Statistics, 13:646-677, 2019.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In International Conference on Machine Learning, volume 1, pages 609-616, 2001.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. In Proceedings of the eighth ACM SIGKDD International Conference Knowl- edge Discovery and Data Mining, pages 694-699, 2002.
Cun-Hui Zhang, Risk bounds in isotonic regression. The Annals of Statistics, 30(2):528 522-555,, 2002.
Xiang Zhou, Yixin Nie, and Mohit Bansal. Distributed nli: Learning to predict human opinion dis- tributions for language reasoning. In Findings of the Association for Computational Linguistics: ACL 2022, Association for Computational Linguistics, 2022.
14

---

Published as a conference paper at ICLR 2026
THE USE OF LARGE LANGUAGE MODELS
We used OpenAl's ChatGPT and Codex for the following assistance purposes:
Detect grammatical errors and improve clarity.
Assist in writing the code for generating the figures in the paper.
A RELATED WORK
Estimation of the Bayes error Err" (see Section 2.1 for the definition) is a classical problem in the field of machine learning and pattern recognition. Existing methods for Bayes error estimation can be categorized based on the type of data used, specifically as either instance-label pair-based or soft basel-based estimation.
Most of the existing methods require a dataset {I y1 1:) composed of instances I; X' paired with their respective labels y {0, 1). Assuming the two class-conditionns distributions of instances have densities satisfying certain conditions, [Berisha et al. (2014), Moon al.) (2018) and [Nshadd et al. (2019) proposed approaches based on the estimation of [ddivergence between the class-conditional densities. Specifically, Berisha et al. (2014) and Moon et al.] (2018) sug- gested estimating upper lower bounds and thus their methods suffer from relatively large biases. Although Noshad et al.] (2019) succeeded in estimating the exact Bayes error instead of bounds on it, they assumed that the class-conditional densities Po. P1 Hölder-continuon and satisfy 0 < T. S P. S U (i = 0, 1) for some constants and U, and their estimator requires the knowledge of the values of these constants, which can be unpractical.
On the other hand. Theisen et al.] (2021) proposed a Bayes error estimation method based on nor- malizing flow models (Papamakarios al., 202 Kingma and Dhariwal 2018). They first showed that the Bayes error is invariant under invertible transformations. Using this result, they suggested approximating the data distribution with normalizing flow and then computing the Bayes error for its base Gaussian distribution, which can be done using the -iancnis scheme (Diaconis and Holmes 1995 Gessner al. (020).. One of the drawbacks of their approach is that it is prohibitively memory-intensiee for high digenssiin data, as mentioned in their paper.
integration
The method proposed by [shida et al. (2023), described in Section 2.1 was unique in that it utilized the soft labels 17; n(x;) instead of the instances z; themselves. Jeong et al. (2023) extended the approach of Ishida et al. (2023) to the estimation of the Bayes error in multi-class classification problems.
B SUPPLEMENTARY FOR SECTION 2
B. PROOF OF THEBREM I
z. For each i = 1,...,d, d, let p. 1 EØ= z(1) where ,!.,...,,!!"
zmm) E {0. 1} are independent
Bernoulli random variables with mean Pt. For of notation, denote P . Pa) and Noting that [p] = p. P is an unbiased and consistent estimator of p.
p =
Suppose that would like estimate the value d(p) for some function 1 + R. It is natural to consider a plug-in estimator ((P). We can evaluate its bias E [o()) ((p) = E [p()) - & (E (
using a sharpened version of Jensen's inequality by Gao al. 2019
Lemma 1. Suppose & is differentiable μ. Then, we have
inl 2 1(2))
d
sup supzyy 22 h(2) d
Σ
pc(1 - p:) < (p()) - x(p) <
Σ pz(1 - p:).
(8)
1=1
where
M(2) = 6(2) - 0(4) Vo(H) (z
(9)
2 11
15

---

Published as a conference paper at ICLR 2026
Proof. For any i.j [d], we have
1
B -p) -py) = Ps(1 ps)oss.
(10)
where 6ig = = =] is the Kronecker delta. This implies
tr (Cov [p]
Σ
pc pp).
(11)
Now, we can apply (2.4) in Gao al. (2019) to conclude the proof
It is often the that the function in question is Lipschitz continuous. For example, every convex function is locally Lipschitz on any convex compact subset of the relative interior of its domain (see e.g. Efiriart-Urruty and Lemaréchal 1993. Theorem 3.1.2 in Chapter IV). In such cases, we can derive another type of bound based on Lipschitzness.
Lemma (Lipschitzness-aaed bounds for the bias). If L-Lipschitz with respect the 1-norm, we have
[[(O)] - kvp) S Ldy
(12)
2m
Proof. First of all, it holds that
E
[o(p)
<(p)
< - <p))]
(13)
<LE
Pp p:l
(by Lipschitzness)
(14)
d E pp - psll
L
(15)
1=1
Each summand can be bounded by integrating Hoeffding's tail bound (see, e.g. Theorem 2.2.6 of Vershynin 2018)):
P1
pil]
P (Ip: Pi 2 1) dl
(16)
0
S
2 2exp( -2mt² dt
(17)
π
(18)
V
2m
Hence the result follows.
Lemma 2 suggests that the bias is at most O(1/vm), whereas Lemma indicates a faster conver- gence rate of (11/m) whenever the supremum and infimum are finite.
Now, define
(Er (2) min (2, - 2)
(19)
for = [0, 1]. We choose & Φee and apply Lemma and Lemma 2 show the following lemma.
Lemma 3. For each E [d], we have
S Eden (P:) - dEn s 0.
(20)
2m
Furthermore, if + 0.5, holds that
(1 Pt)
< E. (o (Pi) (pr((p))
(21)
m 2p; - 1
AIthooghh Gao et al. 2019) only discusses the univariate case, it is straightforward to extend the result to the multivariate case.
16

---

Published as a conference paper at ICLR 2026
Proof. The lower bound of the first inequality is direct consequences of Lemma 2 and the fact that Oer is 1-Lipschitz. The upper bound follows from the concavity ΦEr and the classic Jensen inequality.
To prove the second inequality, we first assume 0 S Pj < 0.5. For any 2 E [0, 1] \ {p:), we have
for 2 E [0, 0.5).
(z) HEe (p.) (z pi)
h(z)
2z (2
(22)
(z - p2)²
for = E 00.5 1),
pa) )
and thus
1
S <h(z)= S O.
(23)
1 - 2p:
Therefore, Lemma implies
(1 Ps)
S E IPE (P:) (E)((1) S O. m(1 2p;)
(24)
Next, assume 0.5 P; 1. A similar argument proves 2p. <h(2) and
(. P&)
< ( Øer (pt) $ 0.
(25)
m2p; - 1)
Combining (4 and 25
proves the second bound.
Note that Lemma can be rewritten as
min
Leee (p:) m
π 2m
S
J0E (pr) - (EL S 0,
(26)
where
q(1 q) 12q - 1|
if q + 0.5.
LE =
(27)
+00
- 0.5.
5 shows the graph of the function Leee- Finally, Theorem is proved as follows.
Proof of Theorem 7 Conditioning on x, let (1 m with mean n(x) and f be their average m ΣØ= y (0), Then, Lemma gives
1==1 be independent Bernoulli random variables
min
LEA (n(x))
π
Jd (7) x] (n(()) S O.
(28)
m
2m
By taking expectation over æ, we obtain
LE (T()))
min
pvrr (7) E (n(x)) S..
(29)
m
2m
Now the claim follows since E
Err (Mi..)
E [e (7) and Frr E [d (17x:))
B.2 PROOFS FOR OTHER RESULTS
B.2.1 SUPERIORITY OF THEOREM OVEE THE EXISTING RESULT
Proposition 1. Theorem T is tighter than the existing result by Ishida et al. (203) (023)for for all n, m 2
17

---

Published as a conference paper at ICLR 2026
10
8
6
LErr(q)
4
2
0
0.0
0.5
1.0
q
Figure 5: The graph of the function LEre.
6000
5000
Number of samples
4000
3000
2000
1000
0
0-0.2
0.2-0.4
0.4-0.6
0.6-0.8
0.8-1.0
Soft labels for the positive class
Figure 6: The distribution of the soft labels for the positive class in the binarized CIFAR-10H dataset (see Section for details). You can see the two classes are very well-separated.
Proof. Our upper bound is of course smaller than the upper bound in (2.. As for the lower bounds, we can see that the condition
1
log(2n 2n m) m)
+
(30)
2m
2/m m
m
equivalent
2
V2T
n m 2 exp
(31)
2
2
The rinht-hand side is less than 1 31 always holds.
n
18

---

Published as a conference paper at ICLR 2026
B.2.2
FASTER DECAY RATE OF THE BIAS WELL-SEPARATED CASES (COROLLARY & EXAMPLE
Proof of Corollary 7 By the assumption, we have
(n(x)) = 77xx) T(x))
I 1/4 - e²
(32)
2 (1) 0.5|
2c
almost surely. Combining this with Theorem T we obtaín the result.
Proof of Example 7 Let fo, fi be the densities of Fo, respectively. From the data generation model, we can see that
n1x) = pf((z) + (1 (1-
(33)
fo(x) + (i(z)
for any X' such that fo(æ)) > or f1(x) 0. Since the supports of Fi are disjoint,
assume that
fo(x) >0 f1(x) =0 f1(e) >0 fo(x) =0 for any x X.
(34)
which implies
v
if fo(x) 0,
n(x)= = {1 - if fi 0.
(35)
Therefore, it holds that
In(x) 0.5| = 1V - 0.5| = <>>>>0
(36)
almost surely.
B.2.3 COMPUTABLE BOUND OF THE BIAS (COROLLARY
Lemma 4. If Err" & E, we have
IP (PEn (n(()) 2 S min {
1, E
(37)
for any t 1/.1
Proof. Since Φgr (77(=) ( is non-negative random variable with mean E [[E))(())))
Err",
Markov's inequality gives
Err"
E
PP ((bE(()(z)) 2
(38)
for any t O.
Proof of Corollary 2
Let z (n(()) Since
(1x n7(x))
2(1 - 2) 1 2z
(39)
x)) - 11
we have
(x) (xx))
((1-1) 1)
(40)
(2n(x) - 11
1 2t
z < 4. Therefore,
LEee(n(()) (n((x))
min
V 2m
(41)
m
<
E
π
1 [[2 2 t
+ m 1 1 2t
1(1 1)
1 [2 <|]
(42)
2m
<
π
P 2 1)
+
1 ((1 (1-
1.
(43)
2m
1 2
By using Lemma
we obtain
LEer (n(x))
π
E
t(1 t)
E
min
(44)
m
2m
2m
t
m
1 1- 2t
Combining this with Theorem yiills the result.
19

---

Published as a conference paper at ICLR 2026
B.2.4 STATISTICAL CONSISTENCY
Corollary 3.
(i) For any ò (0, 1), with probability least 8, we have
log(2/5)
Err" (mmm) Err"
(45)
2n
2m
(ii) Suppose there exists constant 0 such that (n(x) 0.5| for any 5 (0, 1), with probability at least we have
c holds almost surely. Then,
1og(2/8)
4c²
Err (mmmm) - 2
(46)
2n
8cm
Proof. By Hoeffding's inequality, we have
Err" (Tim) - E Frr (7i=.)
(47)
Err" (fi:n)
E
Err (mim)
Err (Mia))
Err"
(48)
log (2g(2/6)
E
Err (7mm)
Err"
(49)
2n
with probability greater than Corollary [
8.
By upper-bounding the second term using Theorem and
we obtain 45 and (46). respectively.
B.3 NUMERICAL EXPERIMENTS
Here, we examine the validity of our theory using synthetic datasets composed instances drawn from the following distributions R
(a) The Gaussian mixture Px = 0.5 IPo + 0.5 P. with P. = N ((0,0), T2) and P; ((2,2) 2), 12).
(b) The Gaussian mixture Fx 0.5 P.55 with the completely overlapping components Po P, N ((0, 0), I2).
(c) The distribution with label flips discussed in Example We set the label flip rate to v 0.1 and use the uniform distributions over [0, 1)² and [1, 2)² Fo and Fi, respectively.
Note that the "perfect separation" assumption of Corollary D is met only by (c). For each 10, 25, 50, 100, 250, 500, 1000, we perform the following procedure 1000 times:
ii) Sample n 2000 instances from one the distributions (a), (b) and (c).
(ii) For each instance T4g generate hard labels " ..... y; (m) from the posterior class distri-
bution F(y) r²) and compute the approximate soft label f7. 1. -
(5)
(iii) Compute the estimate Err" (f1:)).
Then, we approximate the expectation E
Err" (Tmm) by the average of the 1000 estimates to cal-
culate the bias
Err"
(mm..) Err"
Fig. 7 is log-log plot showing the empirical bias (the blue solid line) function of for each
setup. The corresponding theoretical bound 3 is also shown by the black dashed line T0 We note
This experiment takes around hour for each distribution
CPU.
Note that choice hase distributions. F. does not matter as long as they satisfy assumption
hecause is determined solely by the label flip rate see (35
The expectation E min (nce))())
is approximated by the sample average 20000 data
2mm
points.
20

---

Published as a conference paper at ICLR 2026
that the empirically observed bias is smaller than the theoretical bound in all the setups expected. Our theory accurately predicts the decay of the bias, especially in (a) and (b). If we fit a function of the form m" to bias curve, the slope of its graph corresponds to the exponent p. The slopes obtained by least-squares fitring are -0.9066 for (a). -0.4970 for (b), and -0.4228 for (c). Recall that, the two class-conditional distributions were completely overlapping with each other in (b). Thus the slope close to -0.5 is as expected. What is somewhat interesting is the result for (a). Although this setup does satisfy the perfect separation assumption of Corollary [ the observed bias decay is approximately proportional to m It suggests that the "fast" m term dominates the "slow" m m--12 term. As for (c), examining the slope -0.4228 will not make much sense as the shape of the graph Fig. 7c is far from being straight line.
10
100
100
10-1
10-1
10-1
10
10
10
10
10
10:3
Blas
Bias
10
10-4
10-5
10-5
10-5
10
10-6
10-6
10
10 7
10
102
103
10a
10
103
10a
102
10a
m
m
m
(a)
(c)
Figure 7: The bias of the hard-label-based estimator Err" (7)m as function of the number of hard labels per sample. The blue solid lines indicate the experimental results while the black dashed lines indicate the theoretical upper bounds in Theorem [
C SUPPLEMENTARY FOR SECTION 3
In this section, we present the proof of Theorem Appendix C.I binary isotonic regression (Proposition 2) well useful lemma for general shape-constrained nonparametric regression problems (Lemma)) Then, we employ these results to prove the theorem in Appendix C.2
presents new risk bound for
C.1 RISK BOUND FOR BINARY ISOTONIC REGRESSION
C.I.1 NONPARAMETRIC REGRESSION AND ISOTONIC REGRESSION
Here, we introduce general nonparametric regression problems where aim to estimate the under- lying signal from noisy observations. Then, we describe the isotonic regression setting.
Let be set. Assume that, for each design point 4 E TT 1,...,n, n, we observe
y = fz) +
(50)
where : R is the unknown regression function and & R are independent and mean-zer noise variables. A natural estimator would be the least squares estimator (LSE)
arg min
Σ (ys f i=1
(51)
JEF
21

---

Published as a conference paper at ICLR 2026
where FF is some pre-defined function class. In the fixed design setting, the quality of an estimator is evaluated by the e² risk
n Σ ((t))
(52)
Under this criterion, estimators are evaluated only on the fixed design points i, estimating the function f is equivalent to estimating the sequence/vector μl = (f. R".
From this perspective, the regression problem can be reformulated as follows. Our observation is an n--dimensional random vector y = (y/,... . Dn.) E R of the form
y = 1 +
(53)
Here μ = (MI M.) E R is the unknown signal and & (EI E R is centered noise vector whose elements are independent. Let K C Rd be a closed convex subset from which we choose our estimates, which corresponds to the function class JF the function estimation formu- lation described above. Often it is assumed that the true signal indeed belongs to K. However, in our results in Appendix [C.I] we allow model misspecification, i.c., we do not assume μ K. The LSE fi is the Euclidean projection of onto K:
j arg min| u112.
(54)
uEK
Isotonic regression Isotonic regression is special case where we choose K to be the collection Mn of all non-decreasing sequences of length
Mn {u R" U1 .... un)
(55)
Note that M, is closed convex cone. Here the goal is to estimate isotonic, monotonic, signals from noisy observations. Recall that the LSE ç is the Euclidean projection of the observation vector y onto M,.
mingmnnn -ull2-
(56)
u.M,
It has the following explicit representation (Robertson et al. 1988), which is known as the min-max formula:
T4 min max Dkd.
,,...
(57)
12t kgi
where Ikel := T-k++ Eisk Wi the average of ye Vt. pool adjacent violators (PAV) algorithm (Ayer al. 1955).
It can be efficiently computed with the
We are interested in evaluating the risk 1 f 14 of the LSE f., which has been extensively
studied in the literature (e.g. ZZang 2002 Chatterjee 2014 Chatterjee al., 2015: Bellec and
Tsybakov 2015 Bellee 2018; Yang and Barber) 2019 Chatterjee and Lafferty 2019). We will
cover the results from these existing works later in Appendix C.1.2
C.1.2 REVIEW OF THE EXISTING RISK BOUNDS FOR ISOTONIC REGRESSION
First, we introduce some notions that will be needed below. For each non-decreasing sequence Mn, we denote its total variation by
V Vuu) max 0, min Uy-
(58)
We also let ku)) be the number of constant pieces u. In other words, k(u) is the number of the inequalities u4 I 4,41 that strict, so the sequence w1, th, has k(()) jumps in total.
For the cases where j Mn and the noises have bounded variance E [$] < o², the following bound on the expected risk was proven by Zhang (2022):
sc a (H) n
2/3 o² log(en)
E
(59)
where C < 12.3 is absolute constant. Chatterjee et al. while providing another type of risk bound
2015) showed this 2/3 rate is minimax,
a u
E
p2
14
<
6
min WEM,
u
log
en
(60)
k(u
22

---

Published as a conference paper at ICLR 2026
under the assumptions that μ E Mn and & are iid. with finite variance E [ adaptive, unlike (59). in the sense that gives a parametric rate n-1/2 up to logarithmic factors when the true signal şa is well-approximated by some u E MM, with small k(u) (i.e., a piecewise constant sequence with not too many pieces). Later, [Bllle (2018) showed two types of bounds, improving the previous results in the case of i.idd. Gaussian noise & N(0 o00,022, In). In the first result, they proved that, with probability greater than 1 - --- we have
o². 60 is
1 1 1u12
10111113 + 2co? [ + (())
( on
2/3
4
min wEM.
(61)
where is an absolute constant. A corresponding bound in expectation also can be derived by integrating this high-probbbility bound. The second result is that, with probability at least we have
Eli 11 <
min u.
[ uu- 1
20²k(u)
log
En
2
(62)
k(u)
n
n
A similar in-expectation bound
1 u M1 x²k(u) log en
E
ja n
1al23
min uEM.
(63)
k(u))
also holds. Bellec (2018)'s results, (61) (62) and (63). have several features worth mentioning.
First, their leading constants are 1. For this reason, these bounds are called sharp oracle inequalities. Second, they are valid even under model misspecification, which (59) nor (60) allowed. Third, (61) and (62) were the first oracle inequalities that were shown to hold with high probability, rather than expectation. The last point is especially important for our purpose, i.e., computing confidence intervals. A major drawback of the results by [Bellec] (2018) is that they are restricted to Gaussian noise. Yang and Barber (2019) employed their unique sliding window norm technique to prove the following bound for general sub- Gaussias noise with variance proxy o²:
< 48 (H2(())) log(2n) 2/3 96g² log log2 (2m)
E
(64)
Under model misspecification μa & MM,, (64 still remains valid with μ replaced by its projection onto Mn. A similar high-probability bound also can be derived by almost the same argument, although they did not mention it in their paper.
C.1.3 METRIC ENTROPY BOUNDS FOR ISOTONIC CONSTRAINTS
For real numbers -0 < <<bb<c 0o, define the truncated version of the isotonic cone M,
Mn = (x E R" S œ S ... S In < b).
(65)
Ma b) is not a cone, unlike Mn, but is still a closed convex set. We also define the set of all non-decreasing functions from [0, 1) to [0. 1]:
M ( [0. 1) ~ [0, 1] is non-decreasing).
(66)
Let (F, I1-11) be subset of normed function space. Given two functions I, u E F with ||u ||| S s,
the set
ff
(67)
is called an e-bracket Van Der Vaart and Wellner 1996). The e-bracketing number (FF F,, =l) of (F, I1-l]) is the smallest number of s-brackets needed to cover F. The logarithm of bracketing numbers called bracketing entropy.
Van Der Vaart and Wellner ( (1996, Theorem 2.7.5) and Gao and Wellner 2007 Theorem 1.1) proved the e-bracketing entropy of M is of order e- i.e.,
log.N 11)),))))) C Ve > O,
(68)
where C, > a universal constant depending only on E (o) and ||-| is the LP norm under Lebesgue measure. Later, Chatterjee (2014) Lemma 4. 20) established tool that enables to
23

---

Published as a conference paper at ICLR 2026
convert the bracketing entropy bound (68) for monotone functions into metric entropy bound for monotone sequences. has been commonly utilized in previous studies (Chatterjee 2014: Bellec 2018 Chatterjee and Lafterty 2019). Although the original result by Chatterree (2014) stated for the Huclidean norm I. 2, results for other p-norms I1- p E [1, oo can be obtained by a similar
argument. We state and prove this generalized version below.
Theorem 4. Take any [1, Then, we have
log (M, ll. Cplb- - Cp(b-a)n'H a)nt/r
(69)
E
for O. Here Op is the same constant in 688
Proof. Without loss of generality, we assume a = 0 and b = 1. First of all, note the general fact that E-covering number upper-bounded by 2e-bracketing number (see, e.g. Van Der Vaart and Wellner 1996.. This, together with the bracketing number bound (68), implies
Cp. 2='
log.N (MM, ll), S log Ni I1 2τ) S
(70)
Therefore, there exists an E-net Ñ of the function class M with log|LV| S
Ce.
Now set 2n /Pr.
2
We will construct 8-net N of the sequence class (,, 1) based on N. To this end, for each monotone sequence (M, 1), we associate it with monotone piecewise constant function Iu E .M of the form
i
1
(x)
ull
x
E
(71)
For each f E Ñ, we check if f can be approximated by Iu for some u (0, 1) so that ||ʃ - gull r. S e. If it can, put one of the corresponding sequences u into N. By construction of N, we have log |N] S log N C.
Next, we confirm N is indeed 8-net of Mn (0, 1). Take any u E (,, 1). Then, since Ñ is a g-net of M and Iu belongs to M,, there exists f E N approximating Iu so that
119u
fl S.
(72)
Now, observe that (22 implies "f E Ñ can be approximated by Ju for some u E M,, 1)," so there is N such that |lʃ 90 L S by the construction of N. So the triangle inequality implies
11gu - gull LP S 11 fll + If go 2e. On the other hand, the left-hand side can be explicitly calculated as follows.
(73)
11gu - goller = (f. ((' )0))
1/p
1/8
i-1 1 8
(u: Us 11
7
1/2
Σ
(u: u;i)p
n
Iuu
(74)
1/pp
Therefore, it follows that, for any u E M, (0, 1), there exists v E N such that
| U|I < 2n 2/Pe = 6,
(75)
which proves N is a 8-net of (0, 1) with respect to p-norm. Thus, we have
log.A(M,, (0, 1), 11ppp 8) < log N < C Cpn
(76)
28
8
n
24

---

Published as a conference paper at ICLR 2026
C.1.4 LEMMA FOR PROVING SHARP ORACLE INEQUALITIES
Here, we present general lemma that we can use to prove sharp oracle inequality for the LSE
T = arg min y u arg min (14 + {) - ull2 uEK
(77)
=EK
under convex constraint K C. R" and a general noise &. Here "sharp" means that the resulting oracle inequality has a leading constant 1. Lemma [5 below is slight extension of the elegant argument given (20 Theorem 2.3), which was given for the i.i.d Gaussian noise setting. In fact, it essentially just deterministic statement, so there is no requirement for the stochastic structure of the noise E. Their key idea was to make use of convexity to obtain stronger basic inequality than usual. Here basic inequality refers to the elementary fact
1 ml I u 11l2 + 2(E, u), Vu E K
(78)
that holds even if K is non-convex. (78) immediately follows from the optimality of fa, i.e.,
y
y ull. Yu E K.
(79)
Now suppose K is convex. Then, the LSE (i.e., the projection of y onto K) satisfies the variational inequality
(u μ. p S O, Yu E K,
(80)
which is an elementary result of convex geometry. Importantly, it implies
112 - 1| u ulī.
Vu E K.
(81)
81 can be seen strengthened version of (79) with the additional term
- 1 u1B..
Therefore
it can be used to derive a stronger version of the basic inequality (78). i...
j 1112 < u 1411 + 2EE, e u) 1 u ul2.
Vu E K
(82)
This is the inequality (2.3) in Bellec 2018). Following their method, we use this fact as the starting point of the proof of Lemma 5 Recall that we do not require ja to belong to K. can be any point in IR, i.e., we allow model misspecification.
Lemma 5 (Localized width and projection). Take any p E (2). Let &, H E RD be arbitrarily fixed vectors and K C R= be a convex set. Suppose that a point u E K and positive numbers t, satisfy
(E, u) < t
Z(u,t)
sup vEK. u1
+ ts.
(83)
Then, the projection fu of μ + onto K satisfies
1 1112 1| 14l13 + (1 + 8)²
(84)
Proof. For ease of notation, let
kpl = (v E K 1| ul1p St).
(85)
Note that Z(u,t) t) sup (E, U.,--u) We break our analysis into two cases.
() If π u|1p S I,, then ñ Ky(u, l). Therefore the basic inequality (82) implies
f μ 2 uu μ
< 2 f u) fl u1 < 22( t) - j u < 2Z, t).
(86)
Now use the assumption
83 to obtain
p|
p 11
Iu
t2 + 2ts < (t + 5)² S
(87)
(ii) Next, suppose ||اe - ullp > t. Letting a := t/llă- - u1|p- we have a E (0, 1). Now take == + az u). Then, the convexity of K implies K, and clearly, have
25

---

Published as a conference paper at ICLR 2026
|/2 |w- =ullp- into the basic inequality (82) to obtain
t, is member of (u.t).
Therefore, we can plug fi a- -
1al12 S 2 12 u)
12
(88)
2 -E,
2
1
u)
(89)
2
12
-(u, t)
(90)
a²
2 7(u,t)
t
(91)
a
α
Z(u, 1)
(92)
where used the assumption
2 1
uu | = t in 900 and 2ab
6² s a² in 92
Now, the
83 readily implics
11 1|u
11122
2 +
S (++ s)²
(93)
Therefore the claim true for both cases.
C.1.5 RISK BOUND FOR BINARY ISOTONIC REGRESSION
In the sequel, we apply the general results stated in the previous sections to investigate the binary
isotonic regression problem. In binary regression, we are given n binary observations y) E {0, 1}. each of which is drawn independently from the Bernoulli distribution with mean μás [0, 1). The noise distribution can be described as
IP (E: = 1 - p4) = 1s: IP (G: -14 = p4..
(94)
Many calibration methods for probabilistic classification, including calibration by isotonic regres- sion (Zadrozny and Hlkan, 2002), can be seen as an instance of binary regression problems. Some authors refer to this setup as the Bernoulli model (Yang and Barber 2019).
To the best of our knowledge, there is no previous work that investigated risk bounds in binary isotonic regression. Here, we derive a new risk bound for this setting. Recall the definitions of the isotonic cone M, and its truncation M, (a. b) (see (55) and 665):
Mn {u E Rd
11 S ... S Un
(95)
(a, = {u E Rd
a S ... S un b3 <oo<a<<<<> 0o).
(96)
From the min-max formula (57). one can observe that the unbounded set M, can be replaced with the bounded closed convex set MM, 1) in binary isotonic regression. In other words, the least squares estimator for the binary isotonic regression problem can be written as
arg min | uul/2 (0.)
(97)
leads to the following result. Proposition 2. With probability at least 1 - ² we have
C'
1/3
2x
2
14
min (0.1. m
-luu 14112
+
(98)
n
where C is an absolute constant. Remark.
(i) Thanks to the replacement of the unbounded set Mn with the bounded set M,, we do not have to go through the additional "pealing" step used in Chatterjee 2014 and Chatterjee and Lafferty (2019).
26

---

Published as a conference paper at ICLR 2026
(ii) This result is valid even under model misspecification.
Proof. For any u E (0, 1) and > 0, let
K (u, t) == {v E Mn 1) |10 - u112 St), Z(u, vEK(u,tt
(99)
sup
(5, u..
(100)
We first control the expectation E [Z(u,t)), t)}. To this end, observe that the process (Xp) (((,))((
where X2 == (5. v u), is a sub-Gaussian process, i.c., for any v1, U2 E T, we have E [X,, =
and
2 01
log E e Xx,)
YA 2 0.
(101)
8
Now combining Dudley's chaining technique (see e.g. metric entropy bound in Theorem gives
van Handel
2016 Corollary 5.25) and the
E (z, () s / J VlogN((Ku, 1), de
< 6 ///' V /Cavi de
-12 1 1/441112
(102)
where C2 is the constant appearing in 68
Moreover, is straightforward to see that, for each fixed u and t. Z(u, t) a convex t-Lipschitz function of g. Therefore, by using Theorem 6.10 in Boucheron al. (2013) together with (102) with probability greater than e- we have
Z(u, 1) S E [u, t)] + W 12C1/2
t/2r.
(103)
Now, define 1* = 4 and observe that we have 12C // < #a for any 2 t"
1/3
Therefore, Lemma yields
j
11l2 S
Iue 111 + (t" 22 1 (Ilu
w112 + + 2z
(104)
with probability least e e= we obtain the result by dividing both sides by n and taking the minimum over all u E (0, 1).
C.2 PROOF OF THEBREM 2
We are just one lemma away from proving our main theorem. The following lemma states that the error between the two estimates with different sets of soft labels can be upper bounded by the root-mean-Se -quare error between them.
Lemma 6. For any set of soft labels (M E [0, 1]", it holds that
Err (v/.)) Err" (m
S
1/ mp
(105)
n1
n
Proof. Since x [0, 1] min (2, x} is 1-Lipschitz, we have
Err" (rri) Err" (m))))
min (1/. n/ min {nH, 1 m73
(106)
(107)
n
The second inequality follows from Jensen's 's inequality.
27

---

Published as a conference paper at ICLR 2026
We can finally prove Theorem 2
Proof. By the triangle inequality, we have
Err'
(Min)
Err"
Err
Err" (m1m) Err" (M1m)) - Err"
(108)
Using Lemma 6 for the first term and Proposition 3.2 of Ishida et al. 2023) for the second term, have
Err (Mi:n) Err" I
1
TTe m²)² +
log(4/6)
(109)
8n
with probability at least - 66/2. Now, we evaluate the first term on the right-hand side by applying Proposition 2 for μ (((())--.77) (n))) Conditioned on {adl--r with probability at least 1 8/2, have
n
(u. mio) + ((
1/3
2 (2g(2/
2
Ciso mh)²
min M,
Σ
+
(110)
Since is increasing and î(( f((a)) ... ([nn) (M(n)), we have 7(1 S .... [m)) i.e.,
E Mn. Therefore, (0.11) Ei=1 (u ma) is zero can choose = (* M.))). As a result, we have
C 1/3
log(2/
Th
1R.) 5
(111)
Plugging
111
into
109
and rewriting 11/3 as C, we have
C
log((2 (2/5)
Err"
(clso (7im)
Err" <
+ 2/
(112)
1/3
with probability at least 1 - 6.
We can also prove an extension the case where random noise is added to the corrupted soft labels.
Proof of Theorem
By the same argument as in the main theorem proof, we have
log(6/8)
Err"
Err" S
n
m²²² +
(113)
8n
with probability at least 1 - 5/3. Also, conditioned on {a with probability at least 8/3. we have
iso m
min 1 Σ (u mhn) (0.1) 1m1
)
+
((9 C'
+
loog(3 (3/83/8)
(114)
Now, under the new assumption, f has an inverse function f-1 which is also differentiable and increasing. Therefore, the mean value theorem gives
E()
(Jro) J'(t())
(115)
for some 40) E (0, 1), which means
min (0.1)
Σ [u: - 72) < 2 min
(u f f- (1
+
2
Σ
(116)
n (0.1)
n 1=1
f(
1=1
28

---

Published as a conference paper at ICLR 2026
Since f-1 is increasing and M()) S [a) the first term vanishes by choosing u, fo (m(o)) By using the assumption that f"
we obtain
min (0,1
Σ [4 76)
cn
(1)
(117)
Since e/ E [0, and E (2/) - の² for each i, the Hoeffding's inequality gives
log
(3/3)))
0²
(118)
2n
with probability at least 8/3.
By combining the above bounds, there exists a constant C" > 0 such that
1og(1/5)
Err" (77:m) - Err" S C"
a 1/3
+
(119)
holds with probability at least
6.
D EXPERIMENTAL DETAILS
We utilized the scikit-learn library (Pedregosa al. 2011). version 1.6.1, for isotonic re- gression. We used the implementation of the histogram binning algorithm provided by the aucertainty-calibratt catpyaaalbaaaaaaaa ion package (version 0.1.4; Kumar et al. 2019). We employed the beta-calibration implementation provided the cal package (version 1.1.0; Kull et 2017). We used the boootst function from the SciPy library (Virtanen et al.) 2020), version 1.13.3, to obtain 95% bootstrap confidence intervals. For each estimation method, the experiment took around 20-30 minutes on a CPU.
For the sake of comparison in Fig. 4c we trained ResNet-18 18 (He et al. for 100 epochs with a batch size of T28 using the Adam optimizer with a learning rate of 0.001. took less than hour.
2016) Fashion-MNIST
Our experiments do not require any special computer resouces. All of them were conducted on the CPU of single Apple MacBook Pro (MI chip, 16GB RAM) except for the ResNet training where we used T4 GPU on Google Colab
D.1 CORRUPTION PARAMETERS
In experiments with synthetic mixture-of mixture-offgaussians data, we used the following corruption function:
1 -
1/a 1 1- .
a) = 1 +
(120)
Fig. shows the graph of fp: a, b) for various values of the parameters and b. As you can see, the parameter a makes the soft labels over-confident when a < leading to an underestimation of Bayes error, and under-confident when 1, causing an overestimation. On the other hand, setting b to values other than 0.5 results in asymmetric, skewed corruption.
We conducted the same experiment as in Fig. 4alfor for various values of and 6. The results are shown Fig, Our calibration-ban based estimators consistently succeed in preventing over- or underestima- tion of the Bayes error across all sets of parameter values.
29

---

Published as a conference paper at ICLR 2026
1.0
1.0
0.8
0.8
fip; a,
0.6
f(p: b,b)
0.6
0.4
0.4
0.2
0.2-
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
p
(a)
0.4, b 0.5
(b)
2, = 0.5
1.0
1.0
0.8
0.8
fl; a, b)
0.6
f(p; a,b)
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
p
(c)
0.4, b == 0.7
(d) = 2, b = 0.7
1.0
1.0
0.8
0.8
flp; a, b)
0.6
flp; (o;a,b) bbbb
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
p
p
(c) 0.4, b 0.9
(f) a = 2, b
0.9
Figure 8: The corruption function f(p; a, b) for various parameters and b.
30

---

Published as a conference paper at ICLR 2026
Estimated Bayes error (%)
Estimated Bayes error (%)
15.0
10.0
2
2.5
0.0
clean
hard
corrupted
isstanic
hist.0
hist25
histSo
histi
beta
clean
hard
compupte
isatonic
hist2
his25
hea50
hist100
beta
(a)
0.4, b 0.5
(b)
2,
0.5
Estimated Bayes error (%)
Estimated Bayes error (%)
17.5
6-
12.5
10.0
7.5-
5.0-
2-
2.5
0.0
clean
hard
corrppted
Isatonic
hist20
hist25
hist50
hist100
beta
dean
hard
cotrupted
Isntonic
hist10
hist25
hist5
histin0
bsta
(c) 0.4, b = 0.7
(d)
2,
= 0.7
Estimated Bayes error (%)
Estimated Bayes error (%)
0-
17.5
15.0
12.5
10.0
7.5
2.
2.5
dean
hard
comupte
Isotanic
hist
hist25
hist5o
hist2 00
dean
hard
compptte
isotonic
hist
hist25
hist50
hist2 00
beta
0.4, b
0.9
2, b
0.9
Figure 9:
The estimated Bayes error for the synthetic dataset with various corruption parameters
and b.
31

---

Published as a conference paper at ICLR 2026
D.2 VIOLATION OF THE ASSUMPTION OF THEOREM
In Section 3
we presented Theorem 3 which provides a theoretical guarantee for our Bayes error estimator based isotonic calibration when the corruption noisy. This result assumes that the derivative of the function I satisfies f" 2 e for some strictly positive constant c. Theoretically, is still unclear what happens when this assumption is violated, i.e., when f' can be arbitrarily close to zero. Here we empirically investigate the effects of such violation using synthetic data.
D.2.1 EXPERIMENTAL SETTINGS
We draw n 10000 data points {=r]==1 from a Gaussian mixture Px 0.6 Po + 0.4 Pi. where Po N ((0, 0), [2), P1 N ((2, 2), I2) For each data point Ig, generate its soft label 17 by sampling n2 = 3, 5, 10, 25, 50, 100 hard labels from the corrupted posterior distribution (e a, b)) and taking their average. In other words, we obtain the soft label for æ; as a draw from Binom m. f (m((z);; a. b)) divided by m. by drawing from Binom f(]((;)) a, b)) and dividing the result by m. By changing the number m of hard labels, we can create different noise levels o O vm the smaller m gets, the greater the noise level becomes. We consider two
sets of conruption parameters: (a. = (2, 0.5) and (a, b) = (0.4, 0.5). As we saw Appendix D.I the former corresponds to under-confident soft labels, and the latter corresponds over-confident soft labels. Note that the former satisfies the assumption of Theorem while the latter does not, i.e., the derivative f' can be arbitrarily small. You see this visually in Fig. g Then, we estimate the Bayes error from these corrupted soft labels 1" using the following methods (which we used in Section 4.1:
corrupted: the estimator with corrupted soft labels, i.e., Err" (m)m).
(ii) The estimator with soft labels obtained by calibrating the corrupted soft labels. We use the following calibration algorithms: isotonic calibration (isotonic) uniform-mar his- togram binning with 10, 25, 50 and 100 bins (hist hist25, hist and hist100), and beta calibration (beta).
As in Section method.
we use 1000 bootstrap resamples to compute 95% confidence interval for each
D.2.2 RESULTS
Fig. shows the estimated Bayes error for various numbers m of hard labels per data point. The black dashed lines indicate the Bayes eтror estimated with clean soft labels, which expected to be a good approximation of the true Bayes error. All the non-parametric calibration methods (isotonic c and hisht perform similarly. However, parametric beta calibration (betaa) performs poorly.
Particularly, when (a. (0.4, 0.5) and the assumption of Theorem violated, the more we add hard labels per data point the worse the estimation performance gets even though the noise level decreases. the large-m (i.e., small noise level) regime, beta calibration goes "too far" and consistently overestimates the Bayes error. On the other hand, isotonic calibration and histogram binning perform consistently well, even for relatively small m. When (a, b) = (2,0.5) 0.5) and the assumption of Theorem 3 is satisfied, the performance of all the methods tends to improve as the noise level decreases. However, isotonic calibration and histogram binning still outperform beta calibration, especially for small m.
These results suggest that isotonic calibration and histogram binning are relatively robust to cor- ruption functions with small derivative, whereas beta calibration is not. It is interesting that beta calibration performs so poorly when it is a well-specified parametric model in a sense, i.e., the cor- ruption function f an inverse function the beta calibration map. This fact suggests that choosing appropriate calibration methods, such as isotonic calibration, is crucial in our algorithm design.
Another interesting thing that corrupted's performance becomes worse the number m of hard labels per data point increases when (a. b) = (2, 0.5). This would be because, as we sample
This is the same distribution as we used in Section 4.1
Ber((p) the Bernoulli distribution with mean p.
32

---

Published as a conference paper at ICLR 2026
Estimated Bayes error (%)
10
corrupted
isotonic
hist10
hist25
hist50
hist100
beta
20
60
80
100
Number of hard labels
(a) 2, b 0.5
12
10
Estimated Bayes error (%)
corrupted
Isotonic
hist10
hist25
2-
hist50
hist100
20
60
80
100
Number of hard labels
(b) a = 0.4, b = 0.5
Figure 10: The Bayes error estimated by directly using corrupted soft labels (corrupted) and by calibrating them (others) for various numbers of hard labels per data point. The 95% bootstrap confidence intervals are shown as shaded regions around each line. The black dashed lines indicate the Bayes error estimated with clean soft labels, which is expected to be good approximation of the true Bayes error.
more hard labels, the resulting soft labels are pulled towards the corrupted posterior mean, which makes them more biased. This result highlights the need to calibrate soft labels.
33

---

Published as a conference paper at ICLR 2026
D.3 FURTHER EXPERIMENTS
In this section, we present additional details and results of the experiments mentioned in Section 4.2
D.3.1 ICLR PEER-REVIEW DATASETS
We put together new datasets, which consist of 32, 829 instances of peer-review results for the past ICLR conferences. Peer-review can be considered binary classification task (accept/reject). We used our datasets to estimate the Bayes errrr the ICLR reviews, which is the probability that the ideal, most competent possible reviewer mistakenly rejects good paper accepts bad paper. can be regarded as representing the inherent difficulty the review task.
For each paper submission we utilized the OpenReview API to retrieve:
3(3) and confidences cl")) by the reviewers (j = L,..., #reviewers)
Scores
The final decision yı: accept (y/- 1) or reject (y: 0)
2, o Σ c0 We can then obtain soft label for æ; by
The averaged score is calculated as
normalizing the averaged score 8; to into [0, 1]. Of course, this soft label fJs should be considered corrupted, apply isotonic calibration (and other calibration algorithms) before using them to estimate the Bayes error.
We merged data from ICLR 2017-2025 construct dataset consisting of 32, 829 examples, each which has a corrupted soft label (i.e., normalized average score) and a single hard label (i.e., final decision) for calibration. We also conducted experiments with single-year datasets (ICLR2017, ICLR2025).
D.3.2 VARIANTS BETA CALIBRATION
Beta calibration is a calibration method with three adjustable parameters a, b, m, and this is what we have been using beta since the initial submission. The beta-x variants are beta calibration with restricted parameters, which were also mentioned in the original beta calibration paper (Kull
et al. 2017):
beta-an masa-aan am: and m are adjustable; b is fixed to b = a.
beta -ab: a and b are adjustable; m is fixed to m = 1/2.
beta-a at only a adjustable; b, m is fixed to = a, m = 1/2.
D.3.3 RESULTS
The full results shown in Fig. 11p For ChaosNLI datasets (SNLI, MNLI, AbductiveNL.I, their GitHub repository provides predictions of some pre-trained models. As a reference value, we show the best error rates among them as the dashed horizontal lines in Figures LTd to IT problem in these experiments is that, especially for real-world (non-synthetic) datasets, it is hard to decide which calibration algorithm the best, since the true Bayes error unknown. We will solve this problem in Appendix D.4
34

---

Published as a conference paper at ICLR 2026
Estimated Bayes error (%)
0.5
Estimated Bayes error
15.0
12.5
0.3
7.5
5.0
0.1
2.5
0.0
clean
hard
comppteed
Isotonic
hat10
hist25
hutto
hist200
beta
bera-am
bets-ab
heta-a plate
corruntedd
istonic
hitt0
his25
hist50
hl
beta
beld-am
beta-ab
bela-
plate
(a) Synthetic (BCa)
(b) CIFAR-I0
3.5
Estimated Bayes error (%)
12
Estimated Bayes error
3.0
10
2.5
2.0
1.5
10
corrupted
0.0
lstranic
hist0
hiat25
hist5
hisc100
bata
bets-arm
bste-abb
ball-9
platt
computed
Isaranic
his1n
hia25
histo
hisc2n0
batt
bels-arn
bettag
bata-aa
platt
(c) Fashion-MNIST MNIST
(d) SNLI
Estimated Bayes error (%)
17.5
Estimated Bayes error (%)
14
12.5
20
10.0
7.5
5.0
2.5
0.0
comuphed
Isotonic
Nisti
hi125
hiss5o
hiscing
Ireta
am
bata
beta
platt
comupted
Isotonic
hiczO
his25
hist50
hist.00 0g
buta
beta-am am
beta-ab
bata
Plart
(e) MNLI
(f) AbductiveNLI
40
Estimated Bayes error (%)
40
Estimated Bayes error
30
10
comruptd
Isotonic
hot20
his25
hat50
hist000
bata
beta-ut am
beta-a
beta-a
platt
corupted
Isotonic
his10
hat25
hls55
his100
bata
beta-am
beta-
betara
Plate
(g) ICLR2017-207
(h) ICLR2017
Figure 11: Estimated Bayes error across various calibration algorithms and datasets.
35

---

Published as a conference paper at ICLR 2026
40
Estimated Bayes error (%)
40
30
Estimated Bayes
10
corupted
Isctoric
hot20
his25
hat50
his1n0
beta
bets-au
beta-i
platt
comppptd
isotonic
his10
his25
hist50
his100
beta
am
beta-ab
betea
plate
beta
ICLR2018
ICIR2019
Estimated Bayes (%6
Estimated Bayes error (%)
30
30
10
10
corrupted
Isotonic
hiat1n
hia255
hiato
hist100
Beta
nata-amm
bett--a ab
bitta-a
platt
computtd
Isaranic
his11
his25
hist0
hisc200
bata
bels-arn
bata-a
platt
betth
(k) ICLR2020
()) ICLR2021
Estimated Bayes error (%)
40
Estimated Bayes error
20
20
comupted
lantonic
hist10
his25
his50
h0s2200
bera
bela-am
beta-sb
betara
Plart
comupted
Isotonic
hACZO
hie25
hist50
hist.00 0g
beta
beta-am am
beta-ab
bata-
Platt
(m) ICLR2022
(n) ICLR2023
40
Estimated Bayes error (%))
40
Estimated Bayes error
30
10
comrupted
Lectonic
hot20
his25
hat50
hist00
bata
beta ammm
beta-ab
beta-a
Platt
corupted
Isotonic
his10
hat25
his55o
his100
bata
beta-am
beta-al
beta-i
Plate
(0) ICLR2024
(p) ICLR2025
Figure 11: Estimated Bayes error across various calibration algorithms and datasets (continued).
36

---

Published as a conference paper at ICLR 2026
D.4 EVALUATING CALIBRATION ALGORITHMS AGAINST REAL- WWOLD DATASETS WITH FEEBEE
In this section, we present the full details and results of the FeeBee experiment described in Sec- tion 4.3 We first review FeeBee (Renggli et al. 2021), a real-world evaluation framework for Bayes estimators. Then, we present experimental results of various calibration algorithms evaluated using FeeBee.
D.4.1 REVIEW FEEBEE
In the long history of the field of Bayes error estimation, evaluation of estimators on real-world datasets has been a challenging task. For synthetic datasets, one can easily compute exact or ap- proximate Bayes eгror rates; however, for real-world datasets, practically impossible to obtain ground-truth Bayes enror rates they depend the unknown data distribution. Of course, it is trivial to obtain a lower bound and an upper bound the Bayes error rate: if we have a classifier with error rate E dataset, then the Bayes error rate should be somewhere between and E. However, such bounds are not informative enough. For example, constant estimators that always return any value between and E technically valid from this perspective, but they are obviously useless in practice.
To address this issue, Renggli al. (2021) proposed an evaluation framework called FeeBee. The key idea of FeeBee is to generate a series of datasets from a given real-world dataset by injecting
various levels of synthetic label noise. To be more specific, for noise level p [0. 1]. FeeBee
generates new dataset by replacing each original label Y with uniformly random label U with probability pt
y, = (1 Z) YY,
(121)
where ~ Bernoullipp) Importantly, there is a simple relationship between the Bayes error rates Err" on the original dataset and Err on the noise-injected dataset:
Err - P. (1 p) Errr.
(122)
Since 0 < Err" < we can derive the following bounds on Err;:
L(p) = f 2 Err S & + (1 -1- (1-P))==(0)
(123)
Based on this observation, FeeBee first generates many noise-injected datasets with different noise levels p E [0, 1], and then evaluates a given Bayes eтror estimator on each of them. Ideally, the resulting estimates Err should lie within the bounds [L(p), U()) given in (123) If the estimates fall outside the bounds, we penalize the estimator by the amount of violation. By aggregating the penalties over all noise levels, we can obtain a single score for the estimator on the given real-world dataset:
FeeBee = [ - + (1AA)--Err
Fir F
dp.
(124)
where (x)+ = max(ar 0}. In practice, the integral can be approximated by finite sum: for sufficiently large N E N, the approximate FeeBee score can be computed as
FeeBee N
[Err - U(o:)) (L(x)- Err,
(125)
1=0
where p: = 1,..,, N). The lower the FeeBee score the better the estimator is. FeeBee provides a practical way to evaluate Bayes error estimators on real-world datasets without requiring knowledge of the true Bayes error rates.
D.4.2 COMPARING CALIBRATION ALGORITHMS USING FEEBER
Here, present experimental results where various calibration algorithms evaluated using the FeeBee framework. We use the following real-world datasets: REFAR-IO/CIFAR Fashion-
MNIST/Fashion-MNIIS.HHH SNLI, MNLI, AbductiveNL., ICLR2017-2022 ICLR2017, ... and
37

---

Published as a conference paper at ICLR 2026
Table 2: FeeBee scores of calibration algorithms across real-world datasets (lower better). The best scores for each dataset are highlighted in bold.
Dataset
Calibration algorithm
CIFAR-10
Rishion-MNISS
SNLI
MNLI
AbductiveNLI
isotonic
0.1131
0.1200
0.1025
0.0908
0.0721
min.
0.1644
0.1568
0.1117
0.0941
0.0944
hist
max.
0,1670
0.1592
0.1163
0.0986
0,0979
bota
0.1701
0.1782
0.1167
0.0966
0.1306
beta-am
0.1694
0.1792
0.1138
0.0971
0.1270
beta-ab
0.1698
0.1806
0.1168
0.0974
0.1263
beta-a
0.1702
0.1785
0.1144
0.0995
0,1254
platt
0. 0.1677
0.1659
0.1297
0.1
0.1095
Dataset
Calibration algorithm
ICLR2017-2025
ICLR2017
ICLR2018
ICLR2019
ICLR2020
isotonic
0.0276
0.0104
0.0195
0.0235
0.0354
min.
0.0660
0.0824
0.0716
0.0702
0.0708
hist
0.0670
0.0852
0.0739
0.0727
0.0738
beta
0.0565
0.0539
0.0536
0.0556
0.0586
beta-am
0,0562
0.0542
0.0567
0.0576
0.0610
beta-ab
0,0556
0,0551
0,0543
0,0584
0,0580
beta-a
0,0551
0,0537
0,0554
0.0570
0,0588
platt
0.0610
0.0544
0.0579
0.0611
0.0682
Dataset
Calibration algorithm
ICIR2021
ICLR2022
ICLR2023
ICIR2024
ICLR2025
isotonic
0,0288
0.0089
0.0092
0.0351
0,0326
min.
0.0688
0.0675
0,0677
0.0653
0.0673
hist
max.
0.0712
0.0693
0.0696
0.0669
0.0686
beta
0.0599
0.0460
0.0487
0.0612
0.0599
beta-am
0.0600
0.0483
0.0482
0.0598
0.0606
beta-ab
0.0595
0.0458
0.0481
0.0606
0.0601
beta-a
0.0592
0.0441
0,0476
0.0604
0.0601
platt
0.0631
0.0520
0,0536
0.0661
0.0656
ICLR2025. For each dataset, we compare the FeeBee scores the following calibration algorithms: isotonic calibration (isotonic), histogram binning (hist), full three-parameter beta calibration (beta), beta calibration with = (beta -am), beta calibration with m (beta-ab). beta calibration with b = a. 1/ (beta-a), and Platt scaling (platt). For histogram binning, we test various numbers of bins (10, 15, 20, .... where is the number of data points) and report the best and the worst scores among them. We set N = 100 for the approximation of FeeBee scores.
Choosing To compute the FeeBee scores, we need to choose classifier error rate E for each dataset. For image classification datasets (CIFAR-10 & Fashion-MNISTT, we use the error rates of Vision Transformer (ViT) models as we have seen in Section 4 For natural language inference datasets (SNLL, MNLI & AbductiveNLD), the ChaosNLI GitHub repository provides predictions of some pre-trained models. We use the best error rates among them as E. For the ICLR peer-review datasets, we do not have any pre-trained models, which is the error rate of a trivial reviewer who rejects any given paper no matter what.
simply set E' to the overall acceptance rate,
The full results shown in Table Isotonic calibration (i (isotonic) performs the best among the calibration methods across all datasets, often by a large margin.
Results
38

---

Published as a conference paper at ICLR 2026
D.5 ORDER BREAKAGE
Theorem 2 and Theorem assume that the corruption function f is order- pedder-reg although the
latter theorem allows random noise to be added after the order-preserving transformation. To analyze how much the estimation performance degrades when the order-preserving assumption is violated, conducted experiments on synthetic datasets where can control the degree of order breakage.
Let f be the corruption function used in 4 We define a new, non-order- non-orddr--resserving corruption fo as follows:
fo sigmoid((ogit((()))) + z), where 2 (N, o²),
(126)
Here, a controls the amount fluctuation added after the order-preserving transformation f. By in- creasing o, can increase the degree of order breakage. We first consider the case where corrupted soft labels are obtained as ii fo (7):). We also consider the "non-monotonic skew + random noise" setting, i.e., we obtain corrupted soft labels as average of m independent hard labels sampled from posteriors skewed by the above non-order non-order-preserving corruption:
1
T
(
iJ
y4
(127)
m
where yr Bernoulli (f:),, 2 ~(
(128)
To quantify the degree of order breakage, we use the Kendall tau (Kendall 1938) between 17: and f=:).. The Kendall tau or Kendall's rank correlation coefficient is non parametric measure of ordinal correspondence or monotonicity between two variables. It takes values in [-1, 1]. If the relationship between two variables is completely increasing, the Kendall tau becomes 1. If they are in a completely decreasing relationship, it takes a value -1. Given the Kendall tau т, the probability of order breakage (in our case, the frequency that we have 1/s S T/j, [o() > fa or vice versa for randomly picked pair i < j) can be obtained as -
We conducted experiments as below using the same Gaussian mixture model as in Section For various order breakage levels dataset containing π = 10, 000 corrupted soft labels generated as 7Ι = fo (Tk) or from m 50 hard labels sampled from posteriors skewed by fo. Fig. shows the estimated Bayes error function of the Kendall tau between 17, and fo (n.). The black dashed line indicates the Bayes error estimated using the clean/true soft labels and is supposed to be good approximation of the true Bayes error.
10 10-9 100 100, we estimated the Bayes error from
As expected, the estimation performance degrades as the degree of order breakage increases (i.e., as the Kendall tau decreases). However, in the noiseless setting (Fig. [2a), all the estimators produced estimates almost indistinguishable from the true Bayes eгтor when the Kendall tau is sufficiently large (say, when т 2 0.95 when the order breakage probability less than 2.5%). For the noisy setting (Fig. 12b). the results are a bit different. Overall, the estimation performance improves as the Kendall tau increases, but for beta calibration and its variants, the estimates never get very close to the true Bayes eтror even when the Kendall tau is nearly 1. Other calibration methods, including isotonic calibration, produced estimates fairly close to the true Bayes error (but not as close as the noiseless setting) for sufficiently high Kendall tau values.
39

---

Published as a conference paper at ICLR 2026
17.5
Estimated Bayes error (%)
12.5
10.0
corrupted
isotonic
hist10
7.5
hist25
hist50
hist100
beta
beta-am
2.5
beta-ab
platt
0.0
0.75
0.80
0.85
0.90
0.95
1.00
Kendall's rank correlation
(a) Non-ordder-peeserving corruption without additional noise.
15.0
Estimated Bayes error (%)
12.5
10.0
corrupted
isotonic
hist10
hist25
hist50
hist100
5.0
beta-am
2.5
beta-ab
beta-a
platt
0.75
0.80
0.85
0.90
0.95
1.00
Kendall's rank correlation
(b) Non-ordeer-preservin corruption with additional noise, i.e., the case where corrupted soft labels obtained by averaging m 50 independent hard labels sampled from posteriors skewed by the non-order- nonsoride-preservinn corruption.
Figure 12: Kendall tau and order breakage synthetic logit Gaussian datasets with and without binomial noise.
40


Reviews:
[{"review_id": "pDUKPUnWkN", "reviewer": "Reviewer_yVpp", "summary": "This paper tackles the fundamental question regarding how to measure bayes error theoretically and practically. Building directly on Ishida et al. (2023)'s instance-free soft-label estimator  \\widehat{\\text{Err}}^*(\\eta_{1:n}) = \\frac{1}{n} \\sum_{i=1}^n \\min\\{\\eta_i, 1 - \\eta_i\\}  (where   \\eta_i = P(y=1 \\mid x_i)  ), the authors make two major advances.\n\nFirst, replacing the prior loose   \\mathcal{O}(1/\\sqrt{m})   bound (with n-dependence), they derive a tighter, adaptive bound (Theorem 1) where bias decay depends on class separability:   \\mathcal{O}(1/m)   for well-separated points  and   \\mathcal{O}(1/\\sqrt{m})   near the boundary.\n\nSecond, they address the underexplored setting of corrupted soft labels   \\tilde{\\eta}_i   which is more practical. The solution: Apply isotonic calibration (Zadrozny & Elkan, 2002) to   \\tilde{\\eta}_i   using one true hard label y_i per instance, yielding   \\widehat{\\text{Err}}^*(\\hat{\\eta}^A_{1:n})  . Theorem 2 proves statistical consistency under the weak order-preservation assumption (  \\tilde{\\eta}_i = f(\\eta_i)   for increasing f), with a new sharp oracle inequality for binary isotonic regression (Proposition 2). Experiments on synthetic data and real benchmarks (CIFAR-10H, Fashion-MNIST-H) validate robustness, outperforming baselines like beta/histogram calibration.\n\nThis instance-free, privacy-preserving framework enables reliable checks on model limits, overfitting, and resource allocation in noisy-label settings.", "questions": "How would the paper's results (e.g., bias decay rates or consistency bounds) differ if Tsybakov's margin assumption were applied instead of the paper's separability condition, and where in the paper would this fit?\n\nJean-Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. Ann.\nStatist., 35(2):608–633, 04 2007.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Theoretical Innovation: Tighter bounds and new isotonic oracle inequality.\n\nPracticality: Instance-free, corruption-robust method for real noise case\n\nImpact: Privacy-preserving for medicine/social data; signals diminishing returns, curbing wasteful scaling.", "weaknesses": "Ordering Assumption Sensitivity: Consistency hinges on monotonic f. More broad assumption would be better.\n\nData Diversity\n\nCalibration Benchmarks: test against other calibration method such as Plat scaling.\n\nBinary Label Scope", "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": "8nYIKxbH5t", "reviewer": "Reviewer_pGnM", "summary": "The paper studies the estimation of the Bayes error. It improves the existing estimates from hard labels and proposes an approach to compute it using corrupted soft labels.", "questions": "Questions:\n\nWhat was the primary challenge involved in obtaining your results (i.e., improvements to Bayes error estimation)? Does the result naturally follow with mainly the application of isotonic regression?\n\n\nSuggestions:\n\nFocus more on the correct type of calibration (i.e., isotonic) and what is different about it for your goals.\n\n\nMinor comments:\n\nPage 5 Line 247: heading typo.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality:\nThe originality arises from applying isotonic regression to the problem of Bayes error estimation to remove the limitation of the need for uncorrupted soft labels.\n\nQuality:\nThe submission seems to be technically correct. It is experimentally rigorous and reproducible.\n\nClarity:\nThe submission is generally clear.\n\nSignificance:\nThe submission presents theoretical novel findings in the form of improved Bayes error estimates.", "weaknesses": "There are not major weaknesses to note so I am leaning towards acceptance.\n\nHowever, it is important to note that the challenges in achieving the results are not glaringly obvious. The novelty may not be as significant as it appears.", "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": "6LPSdYBLw3", "reviewer": "Reviewer_THRQ", "summary": "In this paper, the authors study Bayes error estimation problem under soft label settings. They first provide a deepen theoretical understanding of the existing Bayes error estimator in statistical viewpoint. The second contribution is about the corrupted soft labels, and the main idea of using corrupted one is calibration that places the corrupted soft labels to clean version of soft labels. In particular, isotonic calibration is studied, and the authors provide theoretical understanding of it as well as some experimental results.", "questions": "1. Can the author provide experiment result in more larger datasets?\n2. In figure 4, why hist25 has different behavior?\n3. Could the author provide more intuitive explanation of corollary 2? I do not fully understand it as there is a parameter $E$. $E$ already provide Bayes error, but why do we need bias? In other word, how to estimate $B(E,m)$ without knowing $E$?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This work studies the Bayes error estimation problem that is very important in theory and practice. In theoretical view, the paper provides a better understanding of the existing estimator under soft label. In addition to the soft label case, the authors study how to estimate Bayes error using corrupted soft labels by leveraging calibration. Overall, I think this work is important for ML society, especially for classification problems, in terms of theory.", "weaknesses": "Although I enjoyed reading the paper, I feel this work is too limited in practice. Especially, for the first part of the contribution, we could understand more about the existing estimator, this is still limited to be apply more general setting. Second, I think experiments are not enough to convince the work. The synthetic and those simple benchmark dataset is limited to show the proposed estimators performance in modern ML tasks.", "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": "IHpYf36Zcy", "reviewer": "Reviewer_A2T4", "summary": "This paper proposes extensions to the instance-free Bayes error estimation framework based on soft labels introduced by Ishida et al. (2023). Firstly, the authors provide a deepened theoretical analysis of the bias of the hard-label-based estimator $\\widehat{Err^*}(\\widehat{\\eta}_{1:n})$ by showing that the bias decay rate is adaptive to class separation and can achieve a faster rate $O(1/m)$ than the previously established $O(1/\\sqrt{m})$. This analysis results in a substantially tighter upper bound on the bias from Corollary 2. Secondly,  the authors proposed a method for estimation from corrupted soft labels $\\tilde{\\eta}_i$. The authors demonstrate that naive calibration is insufficient and subsequently propose using isotonic calibration. They prove that this method yields a statistically consistent estimator given the critical assumption that the corruption function $f$ maintains the order of the clean soft labels (i.e., $\\tilde{\\eta}_i = f(\\eta_i)$, where $f$ is increasing). Experiments validate these methods on synthetic and real-world datasets.", "questions": "1.  The result in Theorem 2 relies on the strict assumption of monotonic corruption $\\tilde{\\eta}_i=f(\\eta_i)$. Given that the paper addresses complex real-world corruptions like subjective annotator bias and distribution shift, can you provide a stronger justification or analysis regarding the prevalence of monotonic corruption in these settings? If the monotonicity assumption is violated e.g., if $\\tilde{\\eta}$ does not preserve the order of $\\eta$, how rapidly does the estimator degrade in performance?\n\n2.  The improved bias bounds rely on the class separation. For the binarized CIFAR-10H, the classes are noted to be very well-separated in Fig. 6, which leads to fast decay approaching $O(1/m)$. If the underlying distribution separation is minimal (i.e., $\\eta(x) \\approx 0.5$ for many instances), the bounds revert to $O(1/\\sqrt{m})$. For truly challenging, high-Bayes-error tasks where separation is weak, is the improvement offered by Theorem 1 essentially negligible, forcing practitioners back to the weak bounds? Please clarify the practical significance of this adaptive rate in high-uncertainty scenarios.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The new bounds on the hard-label-based estimator Theorem 1, Corollary 2 are substantially tighter and also address the unnatural dependency on $n$ found in the previous work. This refined analysis provides much stronger confidence in the hard-label estimator when $m$ is small, which is common in practice.\n\n2. The paper successfully reveals that the bias decay rate is adaptive and achieves the desired $O(1/m)$ rate when classes are well-separated. This offers important theoretical insight into the fundamental limits of this estimation method.\n\n3. The manuscript correctly identifies and formalizes the practical challenge of using corrupted soft labels obtained from sources like LLMs or subjective human confidence. The counterexample demonstrating the failure of even perfectly calibrated soft labels in Example 2 is insightful.", "weaknesses": "1. The core theoretical breakthrough in Section 3 relies on the assumption that corruption is monotonic ($\\tilde{\\eta}_i = f(\\eta_i)$). This assumption seems like a major weakness. Any real-world corruption that inverts the relative uncertainty of two close points (e.g., some $\\eta_a$ and $\\eta_b$) would violate this and destroy the theoretical guarantee. This severely undermines the claim of tackling a \"more challenging problem setting\".\n\n2. Using isotonic regression (a classical, non-parametric calibration method) as the primary solution for the corrupted label problem seems incremental, especially since the consistency proof requires such a strong functional assumption.\n\n3. The empirical results (such as Fig. 4, Fig. 10) show that isotonic calibration works well. However, they also show that simple histogram binning often performs comparably, suggesting the specific choice of isotonic calibration might not be essential (or that the synthetic corruption used is too simple). \n\n4. Appendix D.2 highlights that the parametric beta calibration performs poorly, sometimes getting worse as $m$ increases when the assumption $f' \\geq c$ is violated. While this suggests isotonic calibration is robust, it seems unusual that a well-specified parametric model (where the corruption $f$ is related to the inverse beta calibration map) would perform worse than non-parametric alternatives. This demands a deeper theoretical explanation beyond merely noting the violation of Theorem 3's assumption.", "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)